Programación Lineal

PROGRAMACIÓN LINEAL

ONJETIVOS: En el presente tema se quiere proporcionar a los alumnos las habilidades de:
 Expresar matemáticamente mediante objetivos y restricciones una situación real.
 Aplicar diferentes métodos de programación lineal para resolver problemas.
 Analizar y validar la aplicación de los resultados obtenidos mediante los diferente métodos
para satisfacer condiciones definidas.
Programación lineal.- Es una técnica de optimización.
Antecedentes de PL

La programación lineal utiliza un modelo matemático para describir el problema.

Algunos de ejemplos de problemas, en los que la PL ha sido aplicada exitosamente en la

administración de operaciones (IO), son:

 La selección de la mezcla de productos en una fábrica, para tener el mejor uso de las horas
disponibles de la maquinaría y la mano de obra, mientras se maximiza la utilidad de las
empresas.
 La selección de diferentes mezclas de materia prima en los molinos de comida para producir
combinaciones de alimentos terminados al mínimo costo.
 La determinación de un sistema de distribución que minimice el costo total de embarque de
varios almacenes a varias localizaciones de mercado.
 El desarrollo de un programa de producción que satisfaga las demandas futuras para un
producto de una compañía y, al mínimo tiempo, minimice los costos totales de producción e
inventarios.

Los términos clave en la PL son recursos y actividades.

Los ejemplos de recursos son:

 Dinero
 Tipos especiales de maquinarias y equipos
 Vehículos
 Personal
 Tiempo y
 Espacio físico
Los ejemplos de actividades incluyen:
 Inversión de dinero en proyectos específicos
 Publicidad en un medio determinado
 El envío de bienes de cierta fuente a cierto destino
 La producción de un cierto bien

3.2. Modelos Matemáticos

La modelación es sin duda una combinación de arte y ciencia.

COMO PLANTEAR EL MODELO DE PL?

 DEFINIR LAS VARIABLES DE DECISIÓN:

Son las incógnitas del problema
y básicamente consisten en los
niveles de todas las actividades
que pueden llevarse a cabo en el
¿ QUE HACER Y EN
problema a formular.
QUE CANTIDAD?
 Programación Lineal

 ENCONTRAR LAS RESTRICCIONES:

Son diferentes requisitos que debe cumplir
cualquier solución para que pueda llevarse a
cabo. En cierta manera son las limitantes en los
valores de los niveles de las diferentes actividades
(variables).

 DETERMINAR LA FUNCIÓN
OBJETIVO:
Con el objetivo se pretende medir la
efectividad de las diferentes soluciones
factibles que pueden obtenerse y
determinar la mejor solución.

Deberá definirse claramente las unidades

de medición del objetivo, como dinero,
tiempo, etc.

Ejemplo 1
La empresa Concretec produce dos tipos de ladrillos: el tipo 1 y tipo 2 para el cual tienen que
pasar por tres procesos para su terminación que son el de mezclado y moldeado, secado y
horneado. La empresa toma en consideración 100 ladrillos para determinar las utilidades y los
costos. El ladrillo del tipo 1 da una utilidad de Bs.10 y el del tipo 2 de Bs.12. El del tipo 1 necesita
de 2 horas en mezclado y moldeado y de una hora en horneado, el del tipo 2 necesita de 3 horas
en mezclado y moldeado, 2 horas en secado y de una hora en horneado. Cada proceso tiene
limitaciones de horas para la manufacturación que son de 15, 6 y 6 horas respectivamente.
Determinar una política optima de producción para Concretec.

Solución:
Variables de decision Ladrillo tipo 1 x1
Ladrillo tipo 2 x2

Modelo Matematico
Tipo 1 Tipo 2 Disponibilidad
Mezcla y moldeado 2 3 15
Secado 0 2 6
Horneado 1 1 6
Utilidad 10 12
 Programación Lineal

Restricciones
2 x1  3x2  15
2 x2  6
x1  x2  6
x1 , x2  0 Funcion Objetivo
Max Z  10 x 1  12 x 2

 Método Grafico para PL

 1º Paso: Llevar a la forma de igualdad las restricciones
2 x1  3x2  15 (1)
2 x2  6 (2)
x1  x2  6 (3)
 2º Paso: Despejar la variable y, si es posible, de cada ecuación:
2
x2  5  x1
3 (I)
x2  3 ( II )
( III )
x 2  6  x1
 3º Paso: Graficar cada ecuación y sombrear el área que corresponda, hacia arriba o hacia
abajo, a la derecha o a la izquierda, de cada recta.
 4º Paso: Identificar el área o zona factible. Esta es el área común a todas las ecuaciones
de las restricciones.
 5º Paso: Identificar con letra mayúscula, a través de una inspección visual, los vértices del
área factible.

C R2
Zona Factible
B

R1
R3

D
A
 Programación Lineal

 6º Paso: Encontrar las

 coordenadas de los vértices anteriores, en la mayoría de los casos se recurre a la solución
del sistema de ecuaciones y en otros se podrá encontrar estos puntos por simple
inspección visual.

Para el caso del problema, por simple, las coordenadas son:

A ( 0,0 )
B ( 0,3 )
C ( 6,0 )

Resolviendo las ecuaciones ( 1 ) y ( 3 ):

2 x1  3x 2  15 (1)
 x( -2 )
 x1  x 2  6 (3)
Entonces la coordenada del
Punto C, será:
2 x1  3x2  15
 2 x1  2 x2  12 C ( 3,3 )
x2  3

x2  3 en (3)

x1  6  3
x1  3

 7º Paso: Reemplazando cada una de las coordenadas en la función objetivo Z, elegimos el

“mayor resultado” por que estamos MAXIMIZANDO.

Z  10 X  12Y
Si:
A0,0  Z  10 x0  12 x0  0
B (0,3) Z  10 x0  12 x3  36
C 3,3 Z  10 x3  12 x3  66
D 6,0  Z  10 x6  12 x0  60

 Resultado: La función objetivo será máxima en el punto C.

3.3. METODO SIMPLEX (CASO MAXIMIZACION)

Existen software que permiten resolver problemas de PL, pero es útil entender la mecánica del
algoritmo. A continuación definiremos algunos términos importantes:

 VARIABLE DE HOLGURA
 Programación Lineal

SOLUCIÓN BÁSICA
SOLUCIÓN FACTIBLE
SOLUCION ÓPTIMA
EL MÉTODO DE LA M

Nota:
Las variables de holgura representan recursos no utilizados, tal como el tiempo en una
máquina, espacio físico, dinero, etc.

FORMA DE IGUALDAD (FORMA ESTANDAR)

El primer paso del Método Simplex requiere que se convierta cada desigualdad de restricción en
una ecuación. Las restricciones  pueden ser convertidas a ecuaciones al sumar una variable de
holgura, tal como se ilustra a continuación:
PROBLEMA ORIGINAL:
Max z = 10X1 + 12X2
2X1 + 3X2  15
2X2  6
X1 + X2  6
Se suman las variables de holgura del lado izq. de
la desigualdad. Observe que en la función
objetivo no existen holguras.

FORMA DE IGUALDAD:
-10X1 -12X2 = 0
2X1 +3X2 +H3 = 15
2X2 +H4 = 6
X1 +X2 +H5 = 6

Estamos copiando los coeficientes de cada

variable y los espacios vacíos se rellenan con
cero.

TABLA INICIAL
X1 X2 H3 H4 H5 LD
-10 -12 0 0 0 0
2 3 1 0 0 15
0 2 0 1 0 6
1 1 0 0 1 6

METODO SIMPLEX
EJEMPLO 1

Resuelva el siguiente problema de programación lineal utilizando el Método Simplex:

Es bueno avisarle que, el método que se describe es

Max z = 10X1 + 12X2
solamente para maximizar y cuando todas las
restricciones son  (menores iguales).
Si Ud. desea resolver otros tipos de problemas deberá
realizarlos a través de un software.
Consulte a su profesor cualquier duda.
 Programación Lineal

3X2 
1
2X1 +
5
2X2  6
X1 + X2  6
X1, X2  0

1. PASO:
Igualar la Función Objetivo (FO) a cero y llevar a la forma de igualdad a las restricciones:

Para realiza este proceso, utilizaremos un

-10X1 -12X2 = 0
2X1 +3X2 +H3 = 15 teorema matemático que dice: “toda desigualdad
2X2 +H4 = 6 se puede convertir en igualdad sumando un
X1 +X2 +H5 = 6 variable al lado izq. de la restricción”

2. PASO: TABLA INICIAL

Llevar los coeficientes de estas variables a una tabla, tal como se muestra abajo, donde la 1°
fila es la FO y las demás filas son las igualdades del paso anterior:

X1 X2 H3 H4 H5 LD
-10 -12 0 0 0 0
2 3 1 0 0 15
0 2 0 1 0 6
1 1 0 0 1 6

3. PASO:
Ubicar, en la FO el valor más negativo, en nuestro caso este valor corresponde al 12,
observe:

X1 X2 H3 H4 H5 LD
-10 -12 0 0 0 0
2 3 1 0 0 15
0 2 0 1 0 6
1 1 0 0 1 6

4. PASO: ELEMENTO PIVOTE

Marcar la columna del valor anterior y determinar las razones para cada igualdad, para esto
dividir el lado derecho LD entre los coeficientes de la columna marcada (columna X2 en este
caso) de la siguiente manera:

X2 LD
-12 0
3 15 15  3 = 5
2
1
6
6
62=3
61=6


Seleccionar la razón más pequeña, no

negativa, y ubicar el elemento que
corresponda a la columna seleccionada.
 Programación Lineal

5. PASO:
Convertir el ELEMENTO PIVOTE en 1, dividiendo toda la fila por el mismo (dividiremos por 2
en este caso).
X1 X2 H3 H4 H5 LD
-10 -12 0 0 0 0
2 3 1 0 0 15
0/2 2/2 0/2 1/2 0/2 6/2
1 1 0 0 1 6

Entonces tendremos:
X1 X2 H3 H4 H5 LD
-10 -12 0 0 0 0
2 3 1 0 0 15
0 1 0 1/2 0 3
1 1 0 0 1 6

6. PASO:
Convertir todos los elementos de la COLUMNA PIVOTE en cero o positivos, a través de
operaciones en fila. El resultado es:
X1 X2 H3 H4 H5 LD
-10 0 0 6 0 36
2 0 1 -3/2 0 6
0 1 0 1/2 0 3
1 0 0 -1/2 1 3

7. PASO: ¿ES LA SOL. OPTIMA?

Para determinar esto, debemos observar la fila de la FO, y preguntarnos si existen todavía
valores negativos. Observemos la tabla anterior:
X1 X2 H3 H4 H5 LD
-10 0 0 6 0 36
2 0 1 -3/2 0 6
0 1 0 1/2 0 3
1 0 0 -1/2 1 3

Como verá, existe un valor negativo todavía (el 10) y se deberán realizar todos los pasos, otra
vez, a partir del 4° (el cual consiste en determinar el nuevo ELEMENTO PIVOTE)

A continuación se resume todo lo que hemos hecho, más el proceso completo:

TABLA INICIAL:
X1 X2 H3 H4 H5 LD
10 12 0 0 0 0
2 3 1 0 0 15
0 2 0 1 0 6
1 1 0 0 1 6
RESULTADO DE LA PRIMERA ITERACION:
X1 X2 H3 H4 H5 LD
-10 0 0 6 0 36
2 0 1 -3/2 0 6
 Programación Lineal

0 1 0 1/2 0 3
1 0 0 -1/2 1 3
RESULTADO DE LA SEGUNDA ITERACION:
X1 X2 H3 H4 H5 LD
0 0 5 -3/2 0 66
1 0 1/2 -3/4 0 3
0 1 0 1/2 0 3
0 0 -1/2 1/4 1 0
RESULTADO DE LA TERCERA ITERACION:
X1 X2 H3 H4 H5 LD
0 0 2 0 6 66
1 0 -1 0 3 3
0 1 1 0 -2 3
0 0 -2 1 4 0

8. PASO FINAL: INTERPRETACION

Para interpretar se ubican aquellas columnas en las que hubiera 1 y 0 solamente, observe:
RESULTADO DE LA TERCERA ITERACION: Si no existiesen valores negativos en está fila
X1 X2 H3 H4 H5 LD
el Método Simplex termina, interpretamos la
0 0 2 0 6 66
1 0 -1 0 3 3 tabla y determinamos la solución.
0 1 1 0 -2 3
0 0 -2 1 4 0

X1 = 3 X2 = 3 H4 = 0 H3 = 0 H5 = 0
El valor de la FO corresponde al valor de la esquina superior derecha de la tabla anterior:
Z = 66
3.4. METODO SIMPLEX (CASO MINIMIZACIÓN)
Directamente no se lo puede resolver un problema de minimización. No obstante, se lo convierte
en una maximización, haciendo un cambio de variable de la función objetivo (G = -Z) y se resuelve
como si fuera una maximización para “G”, después se cambia a “-Z”.
Para plantear una solución básica factible, tanto en una minimización como en una maximización
se deben considerara el signo de cada restricción siguiendo la siguiente regla:
Signo Variables
= Sumar una variable Artificial
≤ Sumar una variable de Holgura
Sumar una variable Artificial y
≥
restar una variable de Holgura.

Una variable Artificial no tiene un significado físico, contrario a las variables de holgura. Solamente
se utiliza para plantear un solución inicial factible y no debe ser considerada en la solución optima,
es decir no debe tener asignado ningún valor.
Con el objetivo de eliminar dichas variables se realiza la penalización, método que se explica en
los siguientes ejemplos.
Ejemplo
Una compañía carbonífera es propietaria de dos minas, la primera produce como máximo 1 Ton
de carbón de alta calidad, 4 Ton de mediana y 6 Ton de carbón de baja calidad por día; la
segunda mina puede producir como máximo 4 Ton de carbón de alta calidad, 4 de mediana y 2 de
$us
baja calidad por día. Asimismo, a la compañía le cuesta 100 /Día la operación de la mina I y 150
$us
/Día la mina II.
 Programación Lineal

La compañía tiene pedidos de 80, 160 y 120 Ton de carbón de alta, mediana y baja calidad
respectivamente. El problema consiste en determinar cuántos días debe trabajar cada mina para
minimizar los costos de operación.
x1 x2
Producción Producción
Pedido
Calidad Mina I Mina II
[Ton]
[Ton/Día] [Ton/Día]
Alta 1 4 80
Mediana 4 4 160
Baja 6 2 120
$us
Costo /Día 100 150
Función objetivo

Minimizar f(x) = 100x1 + 150x2

Sujeto a:
1
Alta 1x1 + 4x2 ≥ 80 x2 ≥ - /4 x1 + 20
Mediana 4x1 + 4x2 ≥ 160 x2 ≥ -x1 + 40
Baja 6x1 + 2x2 ≥ 120 x2 ≥ -3x1 + 20

x1 ≥ 0 ; x 2 ≥ 0

Gráficamente:
100
90
80
70
60
50
40
Zona óptima
Alta
30
20
10
0
-30 -20 -10 0 10 20 30 40 50 60 70 80 90 100
-10
-20 Mediana
Baja
-30
 Resolver en analíticamente y gráficamente el ejemplo planteado

EJEMPLO
Minimizar Z = 4X1 + X2

Restricciones:
3X1 + X2 = 3
4X1 + 3X2 ≥ 6
X1 + 2X2 ≤ 4
X1, X2 ≥ 0
 Programación Lineal

La forma estándar de este Modelo es: Nota:

En los casos de minimización. En la función objetivo se
asigna a las variables Artificiales un coeficiente positivo
Minimizar Z = 4X1 + X2 + MA1 + MA2 que representa una valor muy grande (M).
En casos de maximización se asigna a las Variables
Restricciones: Artificiales un coeficiente negativo (-M).

3X1 +X2 + A1 = 3
4X1 +3X2 - H1 +A2 = 6
X1 +2X2 +H2 = 4
X1 , X2 , H1 , A1 , A2 , H2 ≥ 0

De las restricciones se despejan las Variables Artificiales:

Restricción 1 A1 = 3 – 3X1-X2
Restricción 2 A2 = 6 – 4X1 – 3X2 + H1

Reemplazando en la Función Objetivo:

Z = 4X1 + X2 + M(3 – 3X1-X2) + M(6 – 4X1 – 3X2 + H1)

Z = 4X1 + X2 +3M -3MX1 – MX2 + 6M – 4MX1 - 3MX2 + MH1
Z = (4 – 7M)X1 + (1-4M)X2 + MH1 + 9M
Nota:
- Z + (4 – 7M)X1 + (1-4M)X2 + MH1 = - 9M Se iguala la Función Objetivo
al Termino Independiente.
Aplicando el Método Simplex

X1 X2 H1 H2 A1 A2 b
3 1 0 0 1 0 3
4 3 -1 0 0 1 6
1 2 0 1 0 0 4
4-
Z 1 -4M 0+1M 0+0M 0+0M 0+0M 0 -9M
7M
1 1/3 0 0 1/3 0 1
0 5/3 -1 0 -4/3 1 2
0 5/3 0 1 -1/3 0 3
-1/3 - -
Z 0+0M 0+1M 0+0M 0+0M -4 -2M
5/3M 4/3+7/3M
1 0 1/5 0 3/5 3/5 -1/5
0 1 -3/5 0 -4/56/5 3/5
0 0 1 1 1 1 -1
- -
Z 0+0M 0+0M 0+0M -8/5+1M 1/5+1M
1/5+0M 18/5+0M
1 0 0 -1/5 2/5 0 2/5
0 1 0 3/5 -1/5 0 9/5
0 0 1 1 1 -1 1
-
Z 0+0M 0+0M 0+0M 1/5+0M -7/5+1M 0+1M
17/5+0M
 Programación Lineal

SOLUCIÓN
X1 = 2/5
Nota:
X2 = 9/5 Se obtiene la solución Optima cuando los coeficiente de la
A1 = 0 función objetivo son positivos, menos LD
H3 = 1
A2 = 0
H4 = 0
Z = 17/5

Ejemplos Propuestos

Resuelva los siguientes problemas de minimización:

X1 = 0
a) Minimizar Z = 2X1 + 3X2 X2 = 5
H1 = 20
Resp a)
Restricciones : 2X1 + 2X2 ≤ 30 H2 = 0
X1 + 2X2 ≥ 10 A3 = 0
X1, X2 ≥ 0 Z = 15

3.4. MODELOS DE TRANSPORTE , TRASBORDO Y ASIGNACIÓN

¿Quién no quisiera gastar lo menos posible, en transportar un producto? Es decir, esto se ha

convertido en un Problema de Transporte. Para ello, es necesario identificar:
ro.
1 Demanda de los clientes
do.
2 Capacidad de la planta
ro.
3 Costo de transporte, desde la planta hasta el cliente.
Para ilustrar bien el problema, desarrollaremos el siguiente problema real.
“La compañía de computación “Cruz SRL”, está distribuida en la red troncal del país. (Santa Cruz -
Cochabamba - La Paz).
La sucursal de Cochabamba, tiene una capacidad de producción anual de 2000 unidades. Cada
una de las otras, pueden producir un máximo de 1700 unidades al año. Estas computadoras, se
venden en cuatro tiendas detallistas del país, ubicados en el Beni, Oruro, Tarija y Pando
respectivamente. Estas tiendas tienen anualmente los siguientes pedidos:
Beni ==> 1700 Computadoras al año
Oruro ==> 1000 Computadoras al año
Tarija ==> 1500 Computadoras al año
Pando ==> 1200 Computadoras al año
Los costos de transporte de la empresa “Cruz SRL”, desde la planta de ensamblado hasta cada
tienda detallista, por cada computadora, viene dada en el siguiente cuadro.
Tiendas detallistas ubicadas
Planta en
Ensambladora Pand
Beni Oruro Tarija
o
Santa Cruz 5 3 2 6
Cochabamba 4 7 8 10
La Paz 6 5 3 8
 Programación Lineal

Paso 1 Diagrama de redes de transporte

Orígen Destino
(Salida) (Llegada)
Beni
5 D1 1700
x11 4
1700 O1 x12 6
3 Oruro
x13
Santa Cruz x14 7 D2 1000
x21 5
x22
2000 O2 x23 2
x24 Tarija
Cochabamba 8
x31 x32 D3 1500
3
x33
6
1700 O3
x34 10 Pando
La Paz 8
D4 1200

Paso 2: (Identificación de Variables) Pueden ser:

xST = x13 = Número de computadoras enviadas desde Santa Cruz hasta Tarija.
Tiendas detallistas ubicadas
Planta en
Ensambladora Pand
Beni Oruro Tarija
o
Santa Cruz x11 x12 X13 x14
Cochabamba x21 x22 X23 x24
La Paz x31 x32 X33 x34
Paso 3: (Identificación de la función objetivo)
Forma verbal:
“Minimizar los costos de transporte desde la planta ensambladora a cada una de
las tiendas de venta”.
Descomposición:
 Costo de transporte   Costo de transporte   Costo de transporte 
Minimizar  
 

 


 desde Santa Cruz   desde Cochabamba   desde LaPaz 
Paso 4: Identificación de las restricciones
“La cantidad transportada no debe exceder la capacidad de la fábrica.”
x11 + x12 + x13 + x14 ≤1700 (Santa Cruz)
x21 + x22 + x23 + x24 ≤ 2000 (Cochabamba)
x31 + x32 + x33 + x34 ≤ 1700 (La Paz)
“La cantidad transportada no debe satisfacer su demanda.”
x11 + x21 + x31 = 1700 (Beni)
x12 + x22 + x32 = 1000 (Oruro)
x13 + x23 + x33 = 1500 (Tarija)
x14 + x24 + x34 = 1200 (Pando)
 Programación Lineal

Paso 5: (Método de solución) Hay muchos métodos en la actualidad, entre los principales
tenemos: a) Esquina Noroeste, b) Matriz mínima, c ) Método de Vogel
Nota.- Los problemas de transporte no equilibrada, se verán más adelante.

Llegada
Suminis
Beni Oruro Tarija Pando
tro
Salida
5 3 2 6
Santa Cruz 1700
1
4 7 8
Cochabamba 0 2000

6 5 3 8
La Paz 1700
Costo
mínimo
Demanda 1700 1000 1500 1200 de
transpor
te

Hay que seguir los siguientes pasos:

Paso 6A: Hallar el plan de transporte inicial
a) Identifique la celda, donde el costo sea el más barato. Si hay más de uno, se elige al azar.
$us.
Ej. Fila 1 y columna 3, costo de 2 /Unidad.

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6 1700
Santa Cruz 1500 200
4 7 8 10
Cochabamba 2000

6 5 3 8
La Paz 1700

1500 Costo
Demanda 1700 1000 1200 mínimo de
0 transporte

b) Envíe cuantas unidades le sea posible en esa celda, siempre y cuando sea el número menor,
entre el suministro y la demanda.
b) Anule la fila o la columna donde el resultado, después de la resta, sea 0 (cero).
c) Si en ambos lugares (suministro y demanda) dan cero, se convierte en un caso especial de
DEGENERACIÓN, que se analizará por separada. (Pg. 14)
Se repite el proceso hasta obtener:

m + n -1 ---> Celdas no vacías y sin ciclo alguno

3 + 4 – 1 = 6 Celdas, no vacías.

Luego se busca el siguiente de menor costo, celda 3, está en fila 1 columna 2.

 Programación Lineal

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6 200
Santa Cruz 200 1500 0
4 7 8 10
Cochabamba 2000

6 5 3 8
La Paz 1700

1000 Costo
Demanda 1700 0 1200 mínimo de
800 transporte

El siguiente número mayor, es 4, es decir, Fila 1 y Columna 1:

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz 200 1500 0

4 1700 7 8 10 2000
Cochabamba 300
300
6 5 3 8 1700
La Paz 800 900
900
1700 800 Costo
Demanda 1200 mínimo de
0 0 0 transporte

El siguiente es el número 5, o sea, fila 3, columna 2; para luego seguir con el número 8, fila 3,
columna 4 y finalmente, el sin valor, marcar el número 10, que está en la fila 2, columna 4. Luego
de ello, como ya no quedan más filas y/o columnas por tachar, queda:

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz 200 1500 1700

4 7 8 10
Cochabamba 1700 300 2000

6 5 3 8
La Paz 800 900 1700

Demanda 1700 1000 1500 1200 24600

Costo total de transporte.

f(x) = 3*200 + 2*1300 + 4*1700 + 10+300 + 5*800 + 8*900 = 24600 $us.
Veamos si estamos en lo correcto:
Cumple con m + n – 1? Si hay 6 celdas no vacías, forman un ciclo? No.
 Programación Lineal

Paso 6B: Prueba de optimabilidad.

Se quiere comprobar, si verdaderamente ese es el costo mínimo de transporte, es decir, si está
bien distribuido el envío.

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz 1700
+1 -1 200 1500

4 1700 7 8 10 +1
Cochabamba 300
2000
6 5 3 8 -1
La Paz 800 1700
900

Demanda 1700 1000 1500 1200 24600

Costo reducido a 5 – 3 + 5 – 8 + 10 - 4 = +5

y esto, qué significa?

Pues que se quiere aumentar en el transporte desde Santa Cruz al Beni, ya que
por cada unidad aumentada, el costo aumenta en 5 $us..
Qué pasa si aumentamos en la otra celda vacía de la fila 1 columna 4?

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz -1 200 1500 1700
+1
4 1700 7 8 10 +1
Cochabamba 300
2000
6 5 3 8 -1
La Paz +1 800 900
1700

Demanda 1700 1000 1500 1200 24600

Costo reducido = 6 – 3 + 5 – 8 = 0

En este caso, no modifica en nada el proceso, así se resuelve para todas las celdas
vacías, quedando el siguiente cuadro.
 Programación Lineal

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz 1500 1700
+5 200
4 1700 7 8 10
Cochabamba +0 +2 300
2000
6 5 3 8
La Paz +4 800 -1 1700
900

Demanda 1700 1000 1500 1200 24600

 La prueba de optimabilidad, consiste en verificar si que no haya salido ningún número

negativo en las celdas vacías. De no ser así (fila 3, columna 3) el plan no es óptimo, es
decir, que existe otro plan que sale más barato que el actual (24600 $us.)
Paso 6C: Cambio hacia un plan de transporte mejorado
Como ya se ha determinado, 24600 $us., no es el costo mínimo, entonces se procede de la
siguiente manera.
a) Identifique el ciclo donde existe el número negativo.
2 + 3 – 2 + 3 – 5 = -1

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 +1 2 -1 6
Santa Cruz 200 1700
1500
4 1700 7 8 10
Cochabamba 300
2000
6 5 3 8
La Paz 800 1700
-1 +1 900

Demanda 1700 1000 1500 1200 24600

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 +1 2 -1 6
Santa Cruz 1000 1700
700
4 1700 7 8 10
Cochabamba 300
2000
6 5 3 8
La Paz 1700
Vacía 800+1 900

Demanda 1700 1000 1500 1200 23800

Costo mínimo: 3*100 + 2*700 + 4*1700 + 10*300 + 3*800 + 8*900 = 23800

 Programación Lineal

b) Calcule nuevamente el costo mínimo y vea que efectivamente, es más barato que el anterior.
c) En función al cambio establecido, vea con los ciclos de las celdas vacías, si efectivamente es
el más barato.
Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 -1 6
Santa Cruz 700 +1 1700
1000
4 7 8 10
Cochabamba 1700 300
2000
6 5 3 8
La Paz 1700
+1
800 900-1

Demanda 1700 1000 1500 1200 23800

+ 6 – 2 + 3 – 8 = + 9 – 10 = -1
Nota.- Fíjese que salió negativo, lo que quiere decir, que existe un plan más barato que
23800.
d) Trasladar el valor más pequeño del ciclo (valor negativo)

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz
1000 700 700 1700

4 7 8 10
Cochabamba 1700 300
2000
6 5 3 8
La Paz 1700
900
1500

Demanda 1700 1000 1500 1200 23100

e) Calcular el costo nuevamente:

3*1000 + 6*700 + 4*1700 + 10*300 + 3*1500 + 8*200 = 23100 $us.
b) Calcular nuevamente los ciclos de las celdas vacías, para ver si siguen saliendo celdas
negativas.
 Programación Lineal

Llegada
Beni Oruro Tarija Pando Suministro
Salida
+1
700 -1
5 3 2 6
Santa Cruz 1000 1700

4 7 8 10 +1
Cochabamba 1700 300 2000
-1 +1 -1
6 5 3 8
La Paz 1700
-1 1500 +1 900

Demanda 1700 1000 1000 1200 23100

+ 5 – 6 + 10 – 4 = + 5
+ 8 – 10 + 8 – 3 = + 3
c) Del mismo modo se busca para las demás celdas vacías, quedando:

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz +5 1000 +1 700 1700

4 7 8 10
Cochabamba 1700 +0 +3 300 2000

6 5 3 8
La Paz +4 +0 1500 200 1700

Demanda 1700 1000 1500 1200 23100

Nota.- Ya no hay valores negativos, lo que quiere decir que 23100 $us., es el costo de
transporte más barato.
¿Hay otras alternativas o rutas que tengan el mismo costo?
Si, son aquellos donde el ciclo da cero (celda vacía), en éste caso existen dos, y son:

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz 700 1700
-11000 +1
4 7 8 10
Cochabamba 1700 300 2000
+1 -1
6 5 3 8
La Paz 1700
1500 200

Demanda 1700 1000 1500 1200 23100

+ 7 – 10 + 6 – 3 = 0 (No aumenta el costo)

 Programación Lineal

Entonces, si aumenta en uno, puedo hacerlo para 10, 100, etc., hasta llegar a mi número
menor del ciclo, en este caso (300); quedando:
Nuevo plan de transporte/mismo costo

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz 700 1000 1700

4 7 8 10
Cochabamba 1700 300 2000
300
6 5 3 8
La Paz 1700
1500 200

Demanda 1700 1000 1500 1200 23100

Costo:
4*1700 + 3*700 + 7*300 + 3*1500 + 6*100 + 8*200= 23100
Como podemos apreciar, cumple con la condición m + n - 1 ≤ al # de celdas no vacías.
Asimismo, las celdas llenas no forman ciclos.
Calculo de costos reducidos mediante el método MODI (Método de Distribución Modificada)
Este método tiene la misma aplicación del ciclo. Para verificar si el costo encontrado efectivamente
es el mínimo, se procede:
a) Se le da una variable (ui) a cada celda de la columna.
b) Se le da una variable (vj) a cada celda de la columna.
c) Se hace un sistema de ecuaciones, utilizando la suma de ambos métodos, igualando con el
número de la celda no vacía.
d) Como el número de ecuaciones es menor al número de variables, se hace cero una de ellas,
en forma arbitraria.

Plan de transporte inicial

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 u1 + v2 2 u1 + v3 6
u1 + v1 =3 =2 u1 + v4 =
=5 6
Santa Cruz 700 1500 1700
5-0-0 6-0-6
=5 3-0– 2-0- =0
3=0 2=0
4 1700 7 8 10 300
u2 + v2 u2 + v3
Cochabamba u2 + v1 u2 + v4 = 2000
=7 =8
=4 10
6 5 800 3 8 900
U3 + v1 U3 +
La Paz U3 + v2 U3 + v4 1700
=6 v3 = 3
=5 =8

Demanda 1700 1000 1500 1200 24600

 Programación Lineal

Ej. Fila 1 columna 1  u1 + v1

Fila 2 columna 3  u2 + v3

e) Armar las ecuaciones de las celdas llenas

u1 + v2 = 3 u2 + v4 = 10
u1 + v3 = 2 u3 + v2 = 5
u2 + v1 = 4 u3 + v4 = 8

7 Variables y 6 ecuaciones

f) Hacer cero cualquiera de ellas. Ej. u1 = 0ll y encontrar todos los demás.
u1 +0v2 = 3 ==> v2 = 3l
u1 +0v2 = 2 ==> v3 = 2l
u3 + v2 = 5 ==> U
u3 + 3 = 5 ==> u3 = 2l
u3 + v4 = 8 ==> V4 = 8 – 2 ==> v4 = 6l
u2 + v4 = 10 ==> u 2 = 10 – 6 ==> u2 = 4l
u2 + v1 = 4 ==> v1 = 4 – 4 ==> v1 = 0l

Quedando como resultado:

Llegada
Beni Oruro Tarija Pando Suministro
Salida
5 3 2 6
Santa Cruz +5 200 1500 +0 1700

4 7 8 10
Cochabamba 1700 +0 +2 300 2000

6 5 3 8
La Paz +4 800 -1 900 1700

Demanda 1700 1000 1500 1200 24600

Nota.- Fíjese que queda ídem al anterior, es decir, sale un número negativo, por lo tanto
24600 $us., no es el costo mínimo, se busca usando el ciclo.

RESOLUCIÓN DE DEGENERACIÓN EN EL ALGORITMO DE TRANSPORTACIÓN

En la solución de matriz mínima, se puede dar el caso en que se ajuste al mismo tiempo, la
demanda y el suministro, porque ambos se anulan. ¿Si esto ocurre, qué se hace?
Veamos el siguiente problema de transportación.
 Programación Lineal

Problema I

Llegada
Cliente 1 Cliente 2 Cliente 3 Suministro
Salida
2 4 3
Planta 1 2 2 4–2=2–2=0

5 5 7
Planta 2 4 4–4=0

3 9 6
Planta 3 2 0 2–2=0

2-2 2-2
Demanda 6–4=2
0 0

Hallar el plan de transporte inicial

1) Buscar el costo de transporte más barato (1.1)
2) Enviar el número mayor en el suministro y la demanda.
3) Restar ese número en ambos lugares.
4) Anular la fila o columna donde dio 0 (cero).
5) Se busca el siguiente número más barato, en este caso, fila 1, columna 3.
6) Se envía a la celda, el número mayor entre el suministro y la demanda (fíjese que son
iguales).
7) Se resta a ambos números y se anula el que da 0 (cero).
Pero en éste caso hay una DEGENERACIÓN, porque ambos dan cero.
¿Qué se hace?
Se sigue la siguiente regla:
1) Tachar la fila, en este caso, fila 1.
2) Elegir cualquier celda de la columna donde esta el problema, en este caso, columna 3. Ej.: Fila
3, columna 3.
3) Se le da un valor de cero, a la celda elegida (considere que no está vacía).
4) Tache la columna observada, en este caso, columna 3.

Continuar con el proceso normal, hasta obtener el siguiente cuadro.

Llegada
Cliente 1 Cliente 2 Cliente 3 Suministro
Salida
2 -1 4 3 +1
Planta 1 2 2 4

5 5 7
Planta 2 4 4

3 9 6
Planta 3 +1
2 0 2
-1

Demanda 2 6 2 48 $us.

Costo mínimo  2 • 2 + 3 • 2 + 5 • 4 + 9 • 2 + 6 • 0

Prueba de optimabilidad (Ciclos en las celdas vacías)

=+3-6+3-2=-2
Significa que hay otro plan, más óptimo que el que se está usando. Elegir el mayor número
negativo del ciclo, en éste caso es 0 (cero) [Fila 3, columna 3]
 Programación Lineal

¿Qué se hace?
Directamente se traslado el 0 (cero) al inicio del ciclo (Fila 3, columna 1) y todo lo demás queda en
su sitio.
Llegada
Cliente 1 Cliente 2 Cliente 3 Suministro
Salida
2 -1 4 +1 3
Planta 1 2 2 4

5 5 7
Planta 2 4 4

3 9 6
Planta 3 +1
0 2 2
-1

Demanda 2 6 2 48 $us.

Costo mínimo  2 • 2 + 3 • 2 + 5 • 4 + 3 • 0 + 9 • 2
Ciclo: + 4 – 2 + 3 – 9 = 7 – 11 = - 4
Lo que quiere decir, que hay un plan más óptimo

Por lo tanto, debemos elegir el mayor número negativo del ciclo. Esta, es otra DEGENERACIÓN.
¿Cuál se elige?
Arbitrariamente, se elige una de las dos; por ejemplo, Fila 3, Columna 2, quedando.
Llegada
Cliente 1 Cliente 2 Cliente 3 Suministro
Salida
2 4 3
Planta 1 0 2 2 4

5 5 7
Planta 2 2 4 2 4

3 9 6
Planta 3 2 3 1 2

Demanda 2 6 2 40 $us.

Costo mínimo  2 • 0 + 4 • 2 + 3 • 2 + 5 • 4 + 3 • 2
Haciendo el análisis de optimabilidad en las celdas vacías, y como no hay celdas con números
negativos, significa que no hay otro plan que salga más barato que 40 $us.; además, no hay
celdas vacías que tengan números iguales a cero, lo que quiere decir, que no existe otro plan que
se pueda llevar a cabo con el mismo costo.
Problema II
La Cámara de Industria y Comercio (CAINCO), tiene una división compuesta de seis fábricas
separadas y esparcidas en los suburbios de Santa Cruz.
Ninguna de las fábricas tiene servicio ferroviario, por lo tanto, los camiones propios de la empresa,
llevan todas las materias primas que suministran los proveedores. Sin embargo, debido a una
huelga de los conductores de camiones de la empresa, varias compañías de camiones, han hecho
proposiciones sobre las cantidades que pueden llevar a las diversas fábricas. Las cotizaciones
para esa situación temporal, son los precios por 1000 libras, expresadas en el siguiente cuadro.
 Programación Lineal

Requerim Cantidad
iento [1000 Lbs.]
Fábrica
semanal Tuc Tilu
[Libras] VG
án chi
Madepa 800.000 8 6 7
Texorsa 1.000.000 4 5 3
Textiles
900.000 7 8 9
“Grigota”
Kupel 1.200.000 3 4 5
0Unigraf 1.500.000 8 9 8
Unitelas 400.000 0 0 0
5.800.000 800 600

CAPACIDAD DE ACARREO SEMANAL

Empresa de Cantidad
transporte [Libras]
Vallegrande 2.000.000
El Tucán 1.800.000
El Tiluchi 2.000.000

Determínese el programa de transporte de menor costo para la CAINCO durante esta situación
temporal
ro.
1 Esquematización

Transportadora Fábrica
1
Madepa

2
Texorsa
1
Vallegrande 3
Textiles Grigota
2
El Tucán 4

3 Kupel

El Tiluchi
5
Unigraf

6
Unitelas
do.
2 Función objetivo
Min Z = 8x11 + 6x21 + 7x31 + 4 x11 + 5x21 + 3x31
7x11 + 8x21 + 9x31 + 3 x11 + 4x21 + 5x31
8x11 + 9x21 + 8x31
 Programación Lineal

ro.
3 Verificación del sistema equilibrado

Transporte Destino
5.800.000 5.800.000
Equilibrado

Fábrica Textiles
Madepa Texorsa Kupel Unigraf Unitelas Suministro Penaliza ción
Transp Grigota
8 4 7 3 8 0
Vallegrande 900 1100 2000 3-0=3

6 5 8 9 9 0
El Tucán 200 1200 400 1800 4-0=4

7 3 4 5 8 0
El Tiluchi 800 800 400 2000 3-0=3

Demanda 800 1000 900 1200 1500 400

Penalizar 7-6=1 4-3=1 8-7=1 4-3=1 8-8=0 0

¿Cumple con  m + n -1 = Número de celdas llenas?

3+6-1=8 Si…!!!
Z = 7•900 + 8•1100 + 5•200 + 4•1200 + 0•400 + 7•800 + 3•800 =6300
+ 8800 + 1000 + 48 =0
+ 5600 0 3200 + 2400 = 32100 $us.
Será el óptimo, resolviendo con ciclos queda:

Fábrica Textiles
Madepa Texorsa Kupel Unigraf Unitelas Suministro
Transp Grigota
8 4 7 u1+v3 3 u1+v4 8 0
Vallegrande u1+v1 u1+v2 u1+v5 u1+v6 2000
900 1200
6 u2+v1 5 8 u2+v3 9 9 u2+v5 0 u2+v6
El Tucán u2+v2 u2+v4 1800
800 100 500 400
7 3 u3+v2 4 5 8 u3+v5 0
El Tiluchi u3+v1 u3+v3 u3+v4 u3+v6 2000
1000 1000

Demanda 800 1000 900 1200 1500 400 30300

Z = 7•800 + 3•11200 + 6•800 + 8•100 + 9•500 + 0•400 + 3•1000 + 8•1000 = 5600

+ 5600 + 3600 + 4800 + 800 = 0
+ 4500 + 3000 + 8000 = 30300 $us.

Buscando los valores de las celdas vacías por MODI

Hacer un sistema de ecuaciones, usando las celdas llenas.

u1 + v3 = 7
u1 + v4 = 3 arb  u1 = 0 9 variables y 8 ecuaciones
u2 + v1 = 6 u2 + v5 = 9  u5 = 8
u2 + v3 = 8
v3 = 7
u2 + v6 = 0  v6 = -1
u2 + v5 = 9 v4 = 3 u3 + v5 = 8  u3 = 0
u2 + v6 = 0
u3 + v2 = 3 u3 + v2 = 3  v2 = 3
u3 + v5 = 8 u3 + v5 = 8  v1 = 5
 Programación Lineal

Usar las ecuaciones de las celdas vacías, con los valores anteriores:
c11  8 – u1 – v1 = 8 – 0 – 5 = 3
c12  4 – u1 – v2 = 4 – 0 – 3 = 1
c15  8 – u1 – v5 = 8 – 0 – 8 = 0
c16  0 – u1 – v6 = 0 – 0 – (-1) = 1
c22  5 – u2 – v2 = 5 – 1 – 3 = 1
c24  4 – u2 – v4 = 4 – 1 – 3 = 0
c31  7 – u2 – v1 = 7 – 0 – 5 = 2
c33  9 – u2 – v2 = 9 – 0 – 7 = 2
c34  5 – u3 – v4 = 5 – 0 – 3 = 2
c36  0 – u2 – v6 = 0 – 0 – (-1) = 1
Como ningún valor da negativo, se demuestra que 30300 es el mínimo costo.

Respuestas >
a) ¿Es verdad que la empresa el TUCAN les lleva materia prima a Madepa, Textiles Grigota y
Unigraf? ¿En que cantidades?
Es verdad, y lo hacen en las siguientes cantidades:
Madepa = 800000 Lbs. Textiles Grigotá = 100000 Lbs. Unigraf = 500000
Lbs.
b) ¿Cuánto aumentaría el envío de 10 unidades transportadas por el Tiluchi, a la fábrica
Madepa?
Es la misma celda c11 = 1*10 = 10 $us. Adicionales.
c) Encuentre el otro u otros envíos con el mismo costo mínimo.
Usando el ciclo de la celda c15 = 0, queda:
Fábrica Textiles
Madepa Texorsa Kupel Unigraf Unitelas Suministro
Transp Grigota
8 4 7 3 8 0
Vallegrande 300 1200 500 2000

6 5 8 9 9 0
El Tucán 800 600 400 1800

7 3 4 5 8 0
El Tiluchi 1000 1000 2000

Demanda 800 1000 900 1200 1500 400 30300

Z = 7•300 + 3•1200 + 8•500 + 6•800 + 8•600 + 0•400 + 3•1000 + 8•1000 = 2100

+ 3600 + 4000 + 4800 + 4800 + 3000 + 8000 = 30300
Z = 30300 $us.  Es otro envío con el mismo costo
 Programación Lineal

Primer envío

1
800.000
Madepa

2
1.000.000
1 Texorsa
2.000.000 Vallegrande
3 900.000
2 Textiles Grigota
1.800.000
El Tucán
1.200.000
4
2.000.000 3 Kupel
El Tiluchi
1.500.000
5
Unigraf

400.000
6
5.800.000 Unitelas 5.800.000
Existe otro envío con el mismo costo en la celda c24 = 0 (Ciclo de color verde)
Efectivamente, será: 4-3+7-8=11-11=0
Fábrica Textiles
Madepa Texorsa Kupel Unigraf Unitelas
Transp Grigota
8 4 7 3 8 0
Vallegrande 900 1100

6 5 8 9 9 0
El Tucán 800 100 500 400

7 3 4 5 8 0
El Tiluchi 1000 1000

Demanda 800 1000 900 1200 1500 30300

De donde:
Z = 7*900 + 3*1100 + 6*800 + 4*100 + 9*500 + 0*400 + 3*1000 + 8*1000
Z = 6300 + 3300 + 4800 + 400 + 4500 + 3000 + 8000
Z = 30300 $us.  Mismo costo
Segundo envío
 Programación Lineal

1
Madepa 800.000

1 2
Texorsa 1.000.000
Vallegrande
2.000.000

2 3 Grigota
Textiles 900.000
El Tucán
1.800.000

3 4
Kupel 1.200.000
El Tiluchi
2.000.000

5
Unigraf 1.500.000

6
Unitelas 400.000

5.800.000
5.800.000

Tercer envío.- Corresponde al cuadro donde se resolvió el problema.

1 800.000
Madepa

2
1.000.000
1 Texorsa
2.000.000
Vallegrande
3 900.000
2 Textiles Grigota
1.800.000
El Tucán
4 1.200.000
3 Kupel
2.000.000
El Tiluchi
5 1.500.000
Unigraf

6 400.000
PROBLEMA DE TRANSPORTE Unitelas
5.800.000
Se quiere transportar desde 3 agencias en el Dpto. de Santa Cruz, a las localidades de Warnes,
5.800.000
Cotoca, Samaipata, Montero y Río Grande, un producto alimenticio de primera necesidad.
Se sabe que los costos unitarios de transporte viene dado por:
 Programación Lineal

Localidades
Warnes Cotoca Samaipata Montero Río Grande
Agencias
4 3 5 2 6
El Porvenir x11 x12 x13 x14 x15
7 6 3 5 7
Santa Fe x21 x22 x23 x24 x25
3 4 5 1 6
Clara Bella x31 x32 x33 x34 x35

La capacidad de envío de cada una de las agencias, es de 70800, 1000 y 300 unidades. El pedido
que se tiene de cada agencia es el siguiente:
Warnes  250
Cotoca  700
Samaipata  500
Montero  300
Río Grande  250
Encuentre el modelo de transporte más económico.
SOLUCIÓN
Función objetivo
Min Z = 4x11 + 3x12 + 5x13 + 2x14 + 6x15
7x21 + 6x22 + 3x23 + 5x24 + 7x25
3x31 + 4x32 + 5x33 + 7x34 + 6x35

Restricciones
1) La cantidad transportada, no debe exceder la capacidad de la agencia.
x11 + x21 + x31 ≤ 250 (Warnes)
x22 + x22 + x32 ≤ 700 (Cotoca)
x13 + x23 + x33 ≤ 500 (Samaipata)
x14 + x24 + x34 ≤ 300 (Montero)
x35 + x25 + x35 ≤ 250 (Río Grande)

2) La capacidad transportada debe satisfacer a las localidades.

x11 + x21 + x31 = 250 (Warnes)
x22 + x22 + x32 = 700 (Cotoca)
x13 + x23 + x33 = 500 (Samaipata)
x14 + x24 + x34 = 300 (Montero)
x35 + x25 + x35 = 250 (Río Grande)

3) La capacidad transportada debe satisfacer a las localidades.

Lógica x11 . . . x35 ≥ 0

Para resolver el problema, usaremos el método Vogel.

 Programación Lineal

to.
4 Método de solución Vogel
Método de asignación por aproximación de Vogel.-
Este método tiene en cuenta los costos al hacerla asignación. Se aplican 5 pasos:

1. Determinar la diferencia entre las dos celdas más bajas en todas las filas y
columnas, incluyendo las ficticias.
2. Identificar la fila o columna con la diferencia más grande. Los vínculos se pueden
romper arbitrariamente.
3. Asignar lo más posible a la celda de menor costo a la fila o columna en la
diferencia más grande.
4. Detener procesos y se completa todos los requerimientos de fila y columna. De lo
contrario proceder con el siguiente paso.
5. Volver a calcular las diferencias entre las dos celdas más bajos que quedan en todas
las filas y columna. Cualquier fila y columna en cero oferta o demanda no se debe
utilizar para calcular otras diferencias. Luego se va al paso dos.

Desde\Hasta E F G H Oferta
A 25 35 36 60 15
B 55 30 45 38 6
C 40 50 26 65 14
D 60 40 66 27 11
Requerim.
10 12 15 9 46
de destino

De\A E F G H Oferta
A 25 35 36 60 15
10 1 1 1 1 25 -
B 55 30 45 38 6 8 8 8 8 8 8 8
C 40 50 26 65 14 14 14 - - - - -
D 60 40 66 27 11 13 13 13 13 - - - -
Demanda 10 12 15 9

15

5 10 11
5 10 11
5 9 11
5 9
5 5
 Programación Lineal

Localidades
Warnes Cotoca Samaipata Montero Río Grande Suministro Penaliza ción
Agencias
4 3 5 2 6
El Porvenir 200 300 200 700 1

7 6 3 5 7
Santa Fe 500 500 1000 2

3 4 5 1 6
Clara Bella 250 50 300 1

Demanda 250 700 500 300 250 06-oct

Penalizar 1 1 2 3 0

Regla general:
M + n – 1 = Nº de celdas llenas  5 + 3 + 1 = 7 celdas
Costo:
Z = 3*20 + 2*300 + 6*200 + 6*500 + 3*500 + 3*250 + 6*50 = 7950 Bs.

ASIGNACION
La asignación consiste en otorgar mejores recursos disponibles para obtener mejores tempos y
menor costo en la distribución de actividades:
Ejemplo:
Los cuatro hijos de Mario Saucedo, Mauricio, Karen, Sergio y Verónica, quieren ganar algún dinero
para cubrir sus gastos personales durante un viaje organizado por la escuela al zoológico local. El
señor Saucedo eligió cuatro tareas para sus hijos: podar el césped, pintar la cochera, lavar el
automóvil de la familia y preparar un resumen de un documental. Para evitar las competencias
anticipadas entre hermanos, les pidió que presentara licitaciones (secretas) para los que ellos
creían que era un pago justo para cada una de las cuatro tareas. Quedaba entendido que los
cuatro hijos aceptarían la decisión de su padre en lo concerniente a quien desempeñaría cada
tarea. La tabla siguiente recibe las licitaciones recibidas:
Podar Pintar Lavar Resumir
Mauricio $ 15 $ 10 $8 $9
Karen $ 10 $ 16 $7 $ 10
Sergio $ 16 $ 13 $ 10 $ 16
Veronica $ 13 $ 15 $8 $ 12

Solución:
Se busca el valor menor de cada una de las tareas, en este caso podar es $10, pintar es $10,
lavar es $7, y resumir es $9.
Podar Pintar Lavar Resumir
Mauricio $ 15 $ 10 $8 $9
Karen $ 10 $ 16 $7 $ 10
Sergio $ 16 $ 13 $ 10 $ 16
Veronica $ 13 $ 15 $8 $ 12
 Programación Lineal

Una vez buscado los valores mínimos se procede a restar cada valor de las mismas tareas
asignadas:
Podar Pintar Lavar Resumir
Mauricio 5 0 1 0
Karen 0 6 0 1
Sergio 6 3 3 7
Veronica 3 5 1 3
El siguiente paso es buscar y anular las filas y columnas que tengan mas de un cero y buscar un
valor mínimo general como en este caso se anulan las dos primeras filas:
Podar Pintar Lavar Resumir
Mauricio 5 0 1 0
Karen 0 6 0 1
Sergio 6 3 3 7
Veronica 3 5 1 3
Se vuelven a restar los otros valores del valor mínimo, se anulan las filas o columnas que tengan
mas de un cero:
Podar Pintar Lavar Resumir
Mauricio 5 0 1 0
Karen 0 6 0 1
Sergio 3 0 0 4
Veronica 2 4 0 2
Para buscar las soluciones se buscan los ceros que se hayan obtenido pero que no este
interceptado con las rectas o filas ya anuladas:
Podar Pintar Lavar Resumir
Mauricio 0
Karen 0
Sergio 0 0
Veronica 0
La solución es la siguiente:
Mauricio tiene que resumir a un costo de $9.
Karen tiene que podar a un costo de $10
Sergio tiene que pintar a un costo de $13
Verónica tiene que lavar a un costo de $8
Teniendo un costo mínimo total de $40
 Programación Lineal

UNIDAD IV

PERT/CPM: Método de la Ruta Crítica

4.1 OBJETIVOS: En el presente tema se pretende que los estudiantes desarrollen las
siguientes habilidades:
 Aplicar diferentes métodos para el diseño de fases de trabajo.
 Desarrollar capacidades para el diseño del control del tiempo de ejecución de
proyectos.

El PERT/CPM fue diseñado para proporcionar diversos elementos útiles de información para
los administradores de proyectos.
Este método expone la ruta crítica de un proyecto; esto es, las actividades que limitan la
duración de un proyecto.
En otras palabras, para lograr que el proyecto se realice pronto, las actividades de la ruta
crítica deberán realizarse pronto.
Por otra parte, si una actividad de la ruta crítica se retrasa, el proyecto como un todo se
retrasará en la misma cantidad.
Las actividades que no están en la ruta crítica tienen una cierta cantidad de holgura; es decir,
pueden empezar más tarde y permiten que el proyecto como un todo se mantenga conforme a
lo programado.
El PERT/CPM identifica estas actividades y la cantidad de tiempo disponible para retardos.

4.2ANTECEDENTES

¿Pero qué significa PERT/CPM?

PERT: Program Evaluation and Review Technique

Maneja tiempos inciertos de las actividades del proyecto.

CPM: Critical Path Method

Maneja tiempos conocidos de las actividades del proyecto.

Actualmente se ha tomado lo mejor de ambos métodos y se han vuelto uno solo, conocido
como Método de la Ruta Crítica.

Objetivo general del Método de la Ruta Crítica

“Que se desee el costo de operación de un proyecto más bajo posible dentro de un tiempo
límite disponible.”

¿Cuáles son sus aplicaciones?

Ejemplos:
 Programación Lineal

Investigación y desarrollo de nuevos productos.

Construcción de plantas, edificios y carreteras.
Diseño e instalación de sistemas nuevos.

¿Cuáles son las preguntas que el PERT/CPM contesta a los tomadores de decisiones?

¿Cuál es el tiempo total para terminar el proyecto?.

¿Cuáles son las fechas programadas de inicio y de terminación para cada una de las
actividades específicas?.
¿Qué actividades son “críticas” y deben terminarse exactamente como se programaron
para mantener el proyecto a tiempo?.
¿Cuánto se pueden retardar las actividades “no críticas” antes de incrementar el tiempo
de terminación del proyecto?.

Procedimiento para llevar a cabo el PERT/CPM

Primero:

Desarrollar una lista de actividades.

Predecesor inmediato: Identifica las actividades que deben haberse terminado

inmediatamente antes de iniciar una nueva actividad.

La información del predecesor inmediato determina si las actividades se pueden terminar en

paralelo (trabajar de manera simultánea), o en serie (terminar una antes de que empiece la
siguiente.

Segundo: Construir la RED

Tercero:
 Programación Lineal

Identificar el tiempo de terminación del proyecto, es decir, identificar la ruta crítica.

Para ello se determina una trayectoria a través de la red, que se define como una secuencia de
nodos conectados que nos lleva desde el nodo inicial hasta el nodo de terminación.
La trayectoria más larga determina el tiempo total requerido para la finalización del proyecto.
Si se retardan las actividades de la trayectoria más larga, la totalidad del proyecto
también se retardará, por lo que la más larga es la “ruta crítica”.

Las actividades de la ruta crítica se conocen como “actividades críticas”.

Ejemplo de optimización de un proyecto utilizando PERT/CPM

Supongamos que se desea llevar a cabo un proyecto de construcción de locales

comerciales para arrendamiento, y para ello se han identificado las siguientes
actividades.

EJEMPLO DE OPTIMIZACIÓN DE UN PROYECTO UTILIZANDO EL MÉTODO DE RUTA CRÍTICA

ACTIVIDAD DURACIÓN DE
ACTIVIDAD DESCRIPCIÓN PREDECESORA LA ACTIVIDAD
INMEDIATA EN SEMANAS
1A Preparar dibujos arquitectónicos ninguna 5
2B Identificar nuevos arrendatarios potenciales ninguna 6
3C Desarrollar prospecto de contrato para los arrendatarios 1 4
4D Seleccionar contratista 1 3
5E Preparar las licencias de construcción 1 1
6F Obtener la aprobación de las licencias de construcción 5 4
7G Llevar a cabo la construcción 4, 6 14
8H Formalizar los contratos con los arrendatarios 2, 3 12
9I Entrada de los arrendatarios 7, 8 2
TOTAL 51

Red del Proyecto

 Programación Lineal

6F
6 7
7G

5E
5 8
4D
9I

3C 8H
2 4 9 10
1A

2B

Utilizando el software “Manager” para resolver el modelo...

PROGRAM: PERT/CPM - PAGE 1 -

***** INPUT DATA ENTERED *****

CPM
------------------------------------------------------------------------
Predecessor
Activity Nodes Activities Duration
------------------------------------------------------------------------
1A 1 -> 2 5.0
2B 1 -> 3 6.0
3C 2 -> 4 1 4.0
4D 2 -> 5 1 3.0
5E 2 -> 6 1 1.0
6F 6 -> 7 5 4.0
7G 7 -> 8 4 6 14.0
8H 4 -> 9 2 3 12.0
9I 8 ->10 7 8 2.0
------------------------------------------------------------------------

Utilizando el software “Manager” para resolver el modelo...

PROGRAM: PERT/CPM - PAGE 1 -

***** PROGRAM OUTPUT *****

The Critical Path (nodes) 1 -> 2 -> 6 -> 7 -> 8 -> 10

The Critical Path (activities) 1-5-6-7–9

A-E-F-G–I
 Programación Lineal

The Completion Time = 26

Entonces la “ruta crítica” del proyecto está dada por las siguientes actividades:

6F
6 7
7G

5E
5 8
4D
9I

3C 8H
2 4 9 10
1A

2B

Actividades críticas del proyecto

En consecuencia, las actividades críticas que no deberán descuidarse, con riesgo de que el
proyecto en su conjunto se retrase son las siguientes:

RUTA CRÍTICA

DURACIÓN DE
ACTIVIDAD DESCRIPCIÓN LA ACTIVIDAD
EN SEMANAS
1A Preparar dibujos arquitectónicos 5
5E Preparar las licencias de construcción 1
6F Obtener la aprobación de las licencias de construcción 4
7G Llevar a cabo la construcción 14
9I Entrada de los arrendatarios 2
TOTAL 26

De cumplirse con ellas sin demora, el tiempo óptimo de terminación del proyecto será de 26
semanas.

Si el tiempo total requerido para terminar el proyecto es demasiado largo...

Deberá tomarse la decisión de dónde y cómo reducir el tiempo de las actividades críticas.
Si se modifica cualquiera de los tiempos de realización de las actividades, los cálculos
de la ruta crítica deberán repetirse para determinar el impacto sobre el programa de actividades
y sobre el tiempo de terminación del proyecto.