programaciÓn lineal onjetivos · 2017. 8. 31. · programación lineal programaciÓn lineal...
TRANSCRIPT
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 problema a formular. ¿ QUE HACER Y EN
QUE CANTIDAD?
Programación Lineal
ENCONTRAR LAS RESTRICCIONES:
DETERMINAR LA FUNCIÓN OBJETIVO:
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
Tipo 1 Tipo 2 Disponibilidad
Mezcla y moldeado 2 3 15
Secado 0 2 6
Horneado 1 1 6
Utilidad 10 12
Modelo Matematico
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).
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.
Programación Lineal
Método Grafico para PL
1º Paso: Llevar a la forma de igualdad las restricciones
1532 21 xx (1)
62 2 x (2)
621 xx (3)
2º Paso: Despejar la variable y, si es posible, de cada ecuación:
12
2
12
6
3
3
25
xx
x
xx
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.
0, 21 xx
Restricciones
1532 21 xx62 2 x
621 xx
Funcion Objetivo
21 1210 xxZMax
( I )
( II )
( III )
R2
R1
R3
A
B
C
D
Zona Factible
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 ):
6
1532
21
21
xx
xx x( -2 )
Entonces la coordenada del Punto C, será:
1532 21 xx
1222 21 xx C ( 3,3 )
32 x
32 x en ( 3 )
3
36
1
1
x
x
7º Paso: Reemplazando cada una de las coordenadas en la función objetivo Z, elegimos el
“mayor resultado” por que estamos MAXIMIZANDO.
YXZ 1210
Si:
0,6
3,3
)3,0(
0,0
D
C
B
A
60012610
66312310
36312010
0012010
xxZ
xxZ
xxZ
xxZ
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
( 1 )
( 3 )
Programación Lineal
SOLUCIÓN BÁSICA
SOLUCIÓN FACTIBLE
SOLUCION ÓPTIMA
EL MÉTODO DE LA M
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
FORMA DE IGUALDAD:
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:
Max z = 10X1 + 12X2
-10X1 -12X2 = 0 2X1 +3X2 +H3 = 15
2X2 +H4 = 6 X1 +X2 +H5 = 6
Es bueno avisarle que, el método que se describe es
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.
Nota: Las variables de holgura representan recursos no utilizados, tal como el tiempo en una máquina, espacio físico, dinero, etc.
Se suman las variables de holgura del lado izq. de la desigualdad. Observe que en la función
objetivo no existen holguras.
Estamos copiando los coeficientes de cada variable y los espacios vacíos se rellenan con
cero.
Programación Lineal
2X1 + 3X2 1
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:
-10X1 -12X2 = 0
2X1 +3X2 +H3 = 15
2X2 +H4 = 6
X1 +X2 +H5 = 6
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 6 6 2 = 3
1 6 6 1 = 6
Para realiza este proceso, utilizaremos un
teorema matemático que dice: “toda desigualdad
se puede convertir en igualdad sumando un
variable al lado izq. de la restricción”
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:
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
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 baja calidad por día. Asimismo, a la compañía le cuesta 100
$us/Día la operación de la mina I y 150
$us/Día la mina II.
Si no existiesen valores negativos en está fila
el Método Simplex termina, interpretamos la
tabla y determinamos la solución.
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
Calidad Producción
Mina I [Ton/Día]
Producción Mina II
[Ton/Día]
Pedido [Ton]
Alta 1 4 80
Mediana 4 4 160
Baja 6 2 120
Costo $us
/Día 100 150
Función objetivo
Minimizar f(x) = 100x1 + 150x2
Sujeto a:
Alta 1x1 + 4x2 ≥ 80 x2 ≥ -1/4 x1 + 20
Mediana 4x1 + 4x2 ≥ 160 x2 ≥ -x1 + 40
Baja 6x1 + 2x2 ≥ 120 x2 ≥ -3x1 + 20
x1 ≥ 0 ; x2 ≥ 0
Gráficamente:
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
Alta
Mediana
Baja -30
-20
-10
0
10
20
30
40
50
60
70
80
90
100
-30 -20 -10 0 10 20 30 40 50 60 70 80 90 100
Zona óptima
Programación Lineal
La forma estándar de este Modelo es: Minimizar Z = 4X1 + X2 + MA1 + MA2 Restricciones: 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
- Z + (4 – 7M)X1 + (1-4M)X2 + MH1 = - 9M
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
Z 4 -7M
1 -4M 0+1M 0+0M 0+0M 0+0M 0 -9M
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
Z 0+0M -1/3 -5/3M
0+1M 0+0M -
4/3+7/3M 0+0M -4 -2M
1 0 1/5 0 3/5 -1/5 3/5
0 1 -3/5 0 -4/5 3/5 6/5
0 0 1 1 1 -1 1
Z 0+0M 0+0M -
1/5+0M 0+0M -8/5+1M 1/5+1M
-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
3X1 +X2 + A1 = 3 4X1 +3X2 - H1 +A2 = 6 X1 +2X2 +H2 = 4
X1 , X2 , H1 , A1 , A2 , H2 ≥ 0
Nota:
En los casos de minimización. En la función objetivo se
asigna a las variables Artificiales un coeficiente positivo que representa una valor muy grande (M).
En casos de maximización se asigna a las Variables
Artificiales un coeficiente negativo (-M).
Nota:
Se iguala la Función Objetivo
al Termino Independiente.
Programación Lineal
SOLUCIÓN X1 = 2/5
X2 = 9/5
A1 = 0
H3 = 1
A2 = 0
H4 = 0
Z = 17/5
Ejemplos Propuestos Resuelva los siguientes problemas de minimización: a) Minimizar Z = 2X1 + 3X2
Restricciones : 2X1 + 2X2 ≤ 30 X1 + 2X2 ≥ 10 X1, X2 ≥ 0
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:
1ro.
Demanda de los clientes 2
do. Capacidad de la planta
3ro.
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.
Planta Ensambladora
Tiendas detallistas ubicadas en
Beni Oruro Tarija Pand
o
Santa Cruz 5 3 2 6
Cochabamba 4 7 8 10
La Paz 6 5 3 8
Nota:
Se obtiene la solución Optima cuando los coeficiente de la
función objetivo son positivos, menos LD
Resp a)
X1 = 0
X2 = 5
H1 = 20
H2 = 0
A3 = 0
Z = 15
Programación Lineal
Paso 1 Diagrama de redes de transporte
Paso 2: (Identificación de Variables) Pueden ser:
xST = x13 = Número de computadoras enviadas desde Santa Cruz hasta Tarija.
Planta Ensambladora
Tiendas detallistas ubicadas en
Beni Oruro Tarija Pand
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:
LaPazdesde
transportedeCosto
Cochabambadesde
transportedeCosto
CruzSantadesde
transportedeCostoMinimizar
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)
O1
D2
O2
D3
O3
D1
D4
Oruro
Beni
Tarija
Pando
1700
2000
1700
Cochabamba
Santa Cruz
La Paz
x11
x12
x13 x14
x31 x32
x33
x34
x21 x22
x23
x24
5
4
6
3
7
5
2
8
3
6
10
8
1700
1000
1500
1200
Orígen
(Salida)
Destino
(Llegada)
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.
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.
Ej. Fila 1 y columna 3, costo de 2 $us.
/Unidad.
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.
Llegada Salida
Beni Oruro Tarija Pando Suminis
tro
Santa Cruz 5
3
2
6
1700
Cochabamba 4 7
8
10 2000
La Paz 6 5
3
8
1700
Demanda 1700 1000 1500 1200
Costo mínimo
de transpor
te
Llegada
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
2
1500 6
1700
200
Cochabamba 4 7
8
10
2000
La Paz 6 5
3
8
1700
Demanda
1700
1000 1500
1200 Costo
mínimo de transporte 0
Programación Lineal
Llegada
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
200 2
1500 6
200
0
Cochabamba 4 7
8
10
2000
La Paz 6 5
3
8
1700
Demanda
1700 1000
0
1200 Costo
mínimo de transporte
800
El siguiente número mayor, es 4, es decir, Fila 1 y Columna 1:
Llegada
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5 3
200 2
1500 6
0
Cochabamba 4 1700 7
8
10 300
2000 300
La Paz 6 5
800 3
8
900 1700
900
Demanda 1700 800
1200 Costo
mínimo de transporte 0 0 0
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
200 2
1500 6
1700
Cochabamba 4
1700 7
8
10 300
2000
La Paz 6 5
800 3
8
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5 3
200 2
1500 6
1700
Cochabamba 4 1700 7
8
10 300
2000
La Paz 6 5
800 3
8
900
1700
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
200 2
1500 6
1700
Cochabamba 4 1700 7
8
10 300
2000
La Paz 6 5
800 3
8
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.
+1 -1
-1
+1
-1
-1
+1
+1
+1
Programación Lineal
Llegada
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5 3
200
2 1500
6
1700
Cochabamba 4 1700 7
8 10 300
2000
La Paz 6 5
800 3 8
900
1700
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
200 2
1500
6
1700
Cochabamba 4 1700 7
8
10 300
2000
La Paz 6 5
800 3 8
900
1700
Demanda
1700
1000
1500
1200 24600
Llegada
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
1000 2
700
6
1700
Cochabamba 4 1700 7
8
10 300
2000
La Paz 6 5
Vacía
3
800
8
900
1700
Demanda
1700
1000
1500
1200 23800
Costo mínimo: 3*100 + 2*700 + 4*1700 + 10*300 + 3*800 + 8*900 = 23800
-1
+5
+4
+0 +2
-1
-1 +1
+1
-1
+1
+1
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
1000
2
700 6
1700
Cochabamba 4 7
8
10 300
2000
La Paz 6 5
3
800 8
900
1700
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
1000
2
700 6
1700
Cochabamba 4 7
8
10 300
2000
La Paz 6 5
3
1500
8
900
1700
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.
700
-1
+1
+1
-1
1700
1700
Programación Lineal
Llegada
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5 3
1000 2
6
1700
Cochabamba 4 7
8 10 300
2000
La Paz 6 5
3
1500
8
900
1700
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5 3
1000 2 6
1700
Cochabamba 4 7
8 10 300
2000
La Paz 6 5
3 1500
8 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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
1000 2
6
1700
Cochabamba 4 7
8
10 300
2000
La Paz 6 5
3
1500
8
200
1700
Demanda
1700
1000
1500
1200 23100
+ 7 – 10 + 6 – 3 = 0 (No aumenta el costo)
700
1700
-1
-1
+1
+1
+1
+1
700
1700
+4
+5
+0
+0 +3
+1
-1
-1
700
1700 +1 -1
+1 -1
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
Salida Beni Oruro Tarija Pando Suministro
Santa Cruz 5
3
700 2
6
1700
Cochabamba 4 7
300
8
10 300
2000
La Paz 6 5
3
1500
8
200
1700
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 Salida
Beni Oruro Tarija Pando Suministro
Santa Cruz
5 u1 + v1
= 5 5 - 0 - 0
= 5
3 u1 + v2 = 3
700
3 - 0 – 3 = 0
2 u1 + v3 = 2
1500
2 - 0 - 2 = 0
6 u1 + v4 =
6 6 - 0 - 6
= 0
1700
Cochabamba 4 1700
u2 + v1 = 4
7 u2 + v2
= 7
8 u2 + v3
= 8
10 300
u2 + v4 = 10
2000
La Paz 6
U3 + v1 = 6
5 800
U3 + v2 = 5
3 U3 + v3 = 3
8 900
U3 + v4 = 8
1700
Demanda
1700
1000
1500
1200 24600
1000
1700
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
f) Hacer cero cualquiera de ellas. Ej. u1 = 0ll y encontrar todos los demás.
u1 + v2 = 3 ==> v2 = 3l
u1 + v2 = 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 Salida
Beni Oruro Tarija Pando Suministro
Santa Cruz 5
+5 3
200 2
1500 6
+0 1700
Cochabamba 4
1700 7
+0 8
+2 10
300 2000
La Paz 6
+4 5
800 3
-1 8
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.
7 Variables y 6 ecuaciones
0
0
Programación Lineal
Problema I
2 4 3
5 5 7
3 9 6
6 – 4 = 22 - 2
0Demanda
2 - 2
0
4–4=0
Planta 3 2 0 2–2=0
Planta 2 4
Suministro
Planta 1 2 2 4–2=2–2=0
Llegada
SalidaCliente 1 Cliente 2 Cliente 3
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.
2 4 3
5 5 7
3 9 6
6 2 48 $us.Demanda 2
4
Planta 3 2 0 2
Planta 2 4
Suministro
Planta 1 2 2 4
Llegada
SalidaCliente 1 Cliente 2 Cliente 3
-1
+1-1
+1
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.
2 4 3
5 5 7
3 9 6
6 2 48 $us.Demanda 2
4
Planta 3 0 2 2
Planta 2 4
Suministro
Planta 1 2 2 4
Llegada
SalidaCliente 1 Cliente 2 Cliente 3
-1
+1-1
+1
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.
2 4 3
5 5 7
3 9 6
6 2 40 $us.Demanda 2
4
Planta 3 2 3 1 2
Planta 2 2 4 2
Suministro
Planta 1 0 2 2 4
Llegada
SalidaCliente 1 Cliente 2 Cliente 3
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
Fábrica
Requerimiento
semanal [Libras]
Cantidad [1000 Lbs.]
VG Tucán
Tiluchi
Madepa 800.000 8 6 7
Texorsa 1.000.000 4 5 3
Textiles “Grigota”
900.000 7 8 9
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 transporte
Cantidad [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
1ro.
Esquematización
2do.
Función objetivo
Min Z = 8x11 + 6x21 + 7x31 + 4 x11 + 5x21 + 3x31
7x11 + 8x21 + 9x31 + 3 x11 + 4x21 + 5x31
8x11 + 9x21 + 8x31
Transportadora Fábrica
1
2
3
Vallegrande
El Tucán
El Tiluchi
2
3
1
4
5
6
Madepa
Texorsa
Textiles Grigota
Kupel
Unigraf
Unitelas
Programación Lineal
3ro.
Verificación del sistema equilibrado
8 4 7 3 8 0
6 5 8 9 9 0
7 3 4 5 8 0
Penaliza ción
3-0=3
4-0=4
3-0=3
4001200 15001000 900Demanda 800
Texorsa
200
800
Madepa
800
Kupel
1200
Suministro
Vallegrande 900 1100 2000
Fábrica
Transp
Textiles
GrigotaUnigraf Unitelas
1800
El Tiluchi 400 2000
El Tucán 400
Penalizar 8-7=1 4-3=17-6=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:
8 4 7 3 8 0
6 5 8 9 9 0
7 3 4 5 8 0
Texorsa
u1+v2
u2+v2
u3+v2
1000
Madepa
u1+v1
u2+v1
800
u3+v1
Kupel
u1+v4
1200
u2+v4
u3+v4
Suministro
Vallegrandeu1+v3
900u1+v5 u1+v6 2000
Fábrica
Transp
Textiles
GrigotaUnigraf Unitelas
1800
El Tiluchi u3+v3
u3+v5
1000u3+v6 2000
El Tucánu2+v3
100
u2+v5
500
u2+v6
400
Demanda 900 1200800 1000 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.
Transporte Destino 5.800.000 5.800.000
Equilibrado
arb u1 = 0
v3 = 7
v4 = 3
9 variables y 8 ecuaciones
u2 + v5 = 9 u5 = 8
u2 + v6 = 0 v6 = -1
u3 + v5 = 8 u3 = 0
u3 + v2 = 3 v2 = 3
u3 + v5 = 8 v1 = 5
u1 + v3 = 7
u1 + v4 = 3
u2 + v1 = 6
u2 + v3 = 8
u2 + v5 = 9
u2 + v6 = 0
u3 + v2 = 3
u3 + v5 = 8
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:
8 4 7 3 8 0
6 5 8 9 9 0
7 3 4 5 8 0
Texorsa
1000
Madepa
800
Kupel
1200
Suministro
Vallegrande 300 500 2000
Fábrica
Transp
Textiles
GrigotaUnigraf Unitelas
1800
El Tiluchi 1000 2000
El Tucán 600 400
Demanda 900 1200800 1000 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
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
8 4 7 3 8 0
6 5 8 9 9 0
7 3 4 5 8 0
Texorsa
1000
Madepa
800
Kupel
1100
100
Vallegrande 900
Fábrica
Transp
Textiles
GrigotaUnigraf Unitelas
El Tiluchi 1000
El Tucán 500 400
Demanda 900 1200800 1000 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
2.000.000
1
2
3
Vallegrande
El Tucán
El Tiluchi
2
3
1
4
5
6
Madepa
Texorsa
Textiles Grigota
Kupel
Unigraf
Unitelas
1.800.000
2.000.000
800.000
1.000.000
900.000
1.200.000
1.500.000
400.000
5.800.000 5.800.000
Programación Lineal
Tercer envío.- Corresponde al cuadro donde se resolvió el problema.
PROBLEMA DE TRANSPORTE
Se quiere transportar desde 3 agencias en el Dpto. de Santa Cruz, a las localidades de Warnes, Cotoca, Samaipata, Montero y Río Grande, un producto alimenticio de primera necesidad.
Se sabe que los costos unitarios de transporte viene dado por:
1
2
3
Vallegrande
El Tucán
El Tiluchi
2
3
1
4
5
6
Madepa
Texorsa
Textiles Grigota
Kupel
Unigraf
Unitelas
2.000.000
1.800.000
2.000.000
800.000
1.000.000
900.000
1.200.000
1.500.000
400.000
5.800.000 5.800.000
1
2
3
Vallegrande
El Tucán
El Tiluchi
2
3
1
4
5
6
Madepa
Texorsa
Textiles Grigota
Kupel
Unigraf
Unitelas
2.000.000
1.800.000
2.000.000
800.000
1.000.000
900.000
1.200.000
1.500.000
400.000
5.800.000 5.800.000
Programación Lineal
4 3 5 2 6
7 6 3 5 7
3 4 5 1 6
Cotoca
x12
x22
x32
El Porvenir x13 x15
Localidades
AgenciasSamaipata Río GrandeMontero
x14
Warnes
x11
Clara Bella x33 x35
Santa Fe x23 x25x24
x34
x21
x31
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
4to.
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.
10 1 1 1 1 25 -
8 8 8 8 8 8 8
14 14 - - - - -
13 13 13 13 - - - -
15
5 10 11
5 10 11
5 9 11
5 9
5 5
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.
de destino 10 12 15 9 46
De\A 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
Demanda 10 12 15 9
Programación Lineal
4 3 5 2 6
7 6 3 5 7
3 4 5 1 6
1000 2
300 1
Suministro Penaliza ción
700 1
3 0Penalizar 1 1 2
300 250 06-oct700 500Demanda 250
Clara Bella 50
Santa Fe 500
250
El Porvenir 200
Localidades
AgenciasSamaipata Río GrandeMontero
300
Warnes Cotoca
200
500
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:
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
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:
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:
Se vuelven a restar los otros valores del valor mínimo, se anulan las filas o columnas que tengan mas de un cero:
Para buscar las soluciones se buscan los ceros que se hayan obtenido pero que no este interceptado con las rectas o filas ya anuladas:
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
Podar Pintar Lavar Resumir
Mauricio 5 0 1 0
Karen 0 6 0 1
Sergio 6 3 3 7
Veronica 3 5 1 3
Podar Pintar Lavar Resumir
Mauricio 5 0 1 0
Karen 0 6 0 1
Sergio 6 3 3 7
Veronica 3 5 1 3
Podar Pintar Lavar Resumir
Mauricio 5 0 1 0
Karen 0 6 0 1
Sergio 3 0 0 4
Veronica 2 4 0 2
Podar Pintar Lavar Resumir
Mauricio 0
Karen 0
Sergio 0 0
Veronica 0
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.
Red del Proyecto
EJEMPLO DE OPTIMIZACIÓN DE UN PROYECTO UTILIZANDO EL MÉTODO DE RUTA CRÍTICA
ACTIVIDAD DESCRIPCIÓN
ACTIVIDAD
PREDECESORA
INMEDIATA
DURACIÓN DE
LA ACTIVIDAD
EN SEMANAS1A 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
Programación Lineal
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
1
2
3
4
6
5
7
8
9 10
1A
2B
5E
4D
3C
6F
7G
8H
9I
Programación Lineal
The Completion Time = 26 Entonces la “ruta crítica” del proyecto está dada por las siguientes actividades:
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:
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.
RUTA CRÍTICA
ACTIVIDAD DESCRIPCIÓN
DURACIÓN DE
LA ACTIVIDAD
EN SEMANAS1A 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
1
2
3
4
6
5
7
8
9 10
1A
2B
5E
4D
3C
6F
7G
8H
9I