transporte_2012

Vista previa del material en texto

INVESTIGACIÓN OPERATIVA I 
MÉTODO DE APROXIMACIÓN DE VOGEL 
 
 
 
Carlos Acevedo Correa 
Ingeniero en Industrias de la Madera 
 
 
CONCEPCIÓN - CHILE 
Magister en Ciencia y Tecnología de la Madera 
PROBLEMAS ESPECIALES DE PROGRAMACION LINEAL 
PROBLEMAS DE TRANSPORTE 
Ivàn Santelices Malfanti 
isanteli@ubiobio.cl 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Introducción 
 Los Problemas de Transporte son 
problemas especiales de 
programación lineal que reciben ese 
nombre debido a que muchas de sus 
aplicaciones involucran determinar la 
manera óptima de transportar bienes. 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Introducción 
 Los Problemas de Asignación 
incluyen aplicaciones tales como 
asignar personas a tareas. Aunque 
sus aplicaciones parecen diferir de las 
del problema del transporte, constituye 
un caso particular. 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Introducción 
 Los problemas de transporte y 
asignación son casos particulares de 
un grupo más grande de problemas, 
llamados Problemas de Flujo en 
Redes. 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Problemas de 
Transporte 
Formulación 
General 
Solución 
Inicial 
Factible 
Solución(es) 
Optimas 
Análisis de 
Sensibilidad 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Problemas de Transporte: 
Formulación General 
Para comprender la formulación matemática de estos problemas 
supóngase que “m” fabricas abastecen a “n” almacenes de un 
cierto articulo, donde la fabrica “i” (i= 1….m), tiene una capacidad 
de producción de “Ai” unidades de producto por unidad de 
tiempo; por otra parte el almacén “j” (j= 1….n) requiere “Bj” 
unidades del producto por unidad de tiempo; ademas el costo de 
envío de un pedido de “i” a “j” es directamente proporcional a la 
cantidad enviada, el costo unitario de transporte se designa por 
“Cij”. 
Así, lo que se desea determinar es la cantidad a enviar desde 
cada almacén de modo tal de minimizar los costos totales 
involucrados. 
Por lo tanto definiendo Xij (cantidad enviada de producto desde la 
planta “i” al almacén “j” por unidad de tiempo) el modelo general 
sería: 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Transporte: Formulación General 
Min CT Cij Xij
i
m
j
n
( ) 
 
 
1 1
jiXij
njBjXij
miAiXij
n
j
m
i
,.....0
],1[....
],1[....
1
1







Sujeto a: 
Capacidad 
producciòn 
Demanda almacén. 
No Negatividad 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Transporte: Supuestos 
Supuesto1) Los costos son proporcionales a la cantidad 
 transportada. 
 
Supuesto 2) Todo lo producido es demandado. Matemáticamente 
 esto se representa de la siguiente forma: 
 
 
 
 
 
Nota: 
Esta situación garantiza la existencia de soluciones factibles y optimas. 
 
Ai Bj
j
n
i
m



11
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Transporte: Supuestos 
Si el supuesto número dos no se cumple, son dos las situaciones que 
se pueden presentar: 
 
A) Suma de ofertas  Suma de demandas (exceso de oferta) 
 
  Crear demandante ficticio. 
 
B) Suma de ofertas  Suma de demandas (exceso de demanda) 
 
  Crear un oferente ficticio. 
 
Nota: 
Los costos asociados al los ficticios son cero, y en la práctica si hubiera 
que enviar al demandante ficticio eso se interpreta como excedente de 
producción (inventario); por el otro lado, enviar desde el oferente ficticio 
se interpreta como demanda insatisfecha (perdida). 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
• Si se tiene un conjunto de m clientes 
que demandan bj unidades de un 
producto determinado. Una 
compañía desea satisfacer esas 
demandas desde un cierto conjunto 
de plantas elegidas de n potenciales 
lugares donde se instalarán, cada 
una con capacidad de oferta ai 
unidades . 
• Cij el costo de transporte de una 
unidad desde la planta i-+esima al 
cliente j-èsimo . 
 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
01
D1
03
02
D2
D3
D4
Fabricas Almacenes
La formulación de 
los problemas de 
transporte difieren 
de los modelos 
estándar de P.L. 
Generalmente se 
presentan las 
redes de transporte 
primero, para luego 
darle una forma 
tabular. 
 
Veamos esta idea 
con el ejemplo de 
la compañía 
DALLAS S.A. 
A1 
A2 
A3 
B1 
B2 
B3 
B4 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
PROBLEMA DE TRANSPORTE (Dallas S.A.) 
• Considere el problema que enfrenta el departamento de planificación de 
la compañía DALLAS S.A. ,que tiene tres plantas y cuatro almacenes 
regionales. Cada mes se requiere de una lista de requerimientos de 
cada almacén y se conocen, también las capacidades de producción de 
las plantas. Además se conoce el costo de transporte de cada planta a 
cada almacén. El problema es determinar qué plantas deben abastecer 
a que almacenes de manera que minimicen los costos totales de 
transporte. Consideremos que los costos de transporte entre dos 
ciudades cualquiera, son proporcionales a las cantidades embarcadas. 
Supóngase que las capacidades mensuales de cada planta son 70, 90 y 
180 respectivamente. Los requerimientos de 
cada almacén para el mes de Marzo son: 
50, 80, 70 y 140. Los costos unitarios de 
transporte son los que se muestran en la tabla 
siguiente: 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
PROBLEMA DE TRANSPORTE (Dallas S.A.) 
 
Los costos unitarios de transporte son los que se muestran en 
la Tabla siguiente: 
 
 
 
Planta
1 2 3 4
1 19 30 50 10
2 70 30 40 60
3 40 8 70 20
Almacén
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
MIN C = C11 X11+ C12 X12 + C13 X13 + C14 X14 + C21 X21 + ………+ C34 X34 
 
S/A 
X11 + X12 + X13 + X14 ≤ A1 
X21 + X22 + X23 + X24 ≤ A2 
X31 + X32 + X33 + X34 ≤ A3 
 
X11 + X21 + X31 ≥ B1 
X12 + X22 + X32 ≥ B2 
X13 + X23 + X33 ≥ B3 
X14 + X24 + X34 ≥ B4 
Xij ≥ 0 
 
Así se tiene “m” oferentes y “n” demandantes 
(m=3 y n=4), luego: 
•Hay n x m variables de decisión. 
•n + m restricciones 
•n + m - 1 variables básicas 
Problemas de Transporte: 
Modelo General para 3 oferentes y 4 demandantes: 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Revisando los supuestos, se cumple. 
 
Supuesto1) Los costos son proporcionales a la cantidad 
 transportada. 
 
Supuesto 2) Todo lo producido es demandado. Matemáticamente 
 esto se representa de la siguiente forma: 
 
 
 
 
 
Nota: 
Esta situación garantiza la existencia de soluciones factibles y optimas. 
 
Ai Bj
j
n
i
m



11
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
MIN C = C11 X11+ C12 X12 + C13 X13 + C14 X14 + C21 X21 + ………+ C34 X34 
 
S/A 
X11 + X12 + X13 + X14 = A1 
X21 + X22 + X23 + X24 = A2 
X31 + X32 + X33 + X34 = A3 
 
X11 + X21 + X31 = B1 
X12 + X22 + X32 = B2 
X13 + X23 + X33 = B3 
X14 + X24 + X34 = B4 
Xij ≥ 0 
 
Así se tiene “m” oferentes y “n” demandantes (m=3 y n=4), luego: 
•Hay n x m variables de decisión. 
•n + m restricciones 
•n + m - 1 variables básicas 
Luego estos problemas se pueden expresar en forma tabular de la siguiente 
manera: 
Dado que ,se puede dejar el modelo como: Ai Bj
j
n
i
m



11
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Transporte: Formulación Tabular 
PLANTA ui
1 2 3 4 Ai (oferta)
1 C11 C12 C13 C14 A1 u1
2 C21 C22 C23 C24 A2 u2
3 C31 C32 C33 C34 A3 u3
Bj (Dda.) B1 B2 B3 B4 sumBi=sumAi
vj v1 v2 v3 v4
ALMACEN
ui y vj son variables del problema dual asociado, son claves 
para encontrar la solución a estos problemas 
ui: Variable dual asociada a las restriccionesde oferta del primal 
vj: Variable dual asociada a las restricciones de demanda primal 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Transporte: Formulación Tabular 
PLANTA
1 2 3 4 Ai
1 C11 C12 C13 C14 A1 u1
2 C21 C22 C23 C24 A2 u2
3 C31 C32 C33 C34 A3 u3
Bj B1 B2 B3 B4 sumBi=sumAi
vj v1 v2 v3 v4
ALMACEN
ij es el precio sombra asociado a las variables del problema. 
 es una cantidad “provisoria” a enviar desde i a j. 
 es parte del algoritmo de solución 
Cij ij
Xij ± 
©The McGraw-Hill Companies, Inc., 1998 Irwin/McGraw-Hill 8 
PROBLEMA DE TRANSPORTE (Dallas S.A.) 
PLANTEO 
PLANTA
1 2 3 4 Ai
1 19 30 50 10 70
2 70 30 40 60 90
3 40 8 70 20 180
Bj 50 80 70 140 340
ALMACEN
©The McGraw-Hill Companies, Inc., 1998 Irwin/McGraw-Hill 8 
PLANTA
1 2 3 4 Ai
1 19 30 50 10 70
50 20
2 70 30 40 60 90
20 70
3 40 8 70 20 180
60 120
Bj 50 80 70 140 340
COSTO TOTAL 7430
ALMACEN
PROBLEMA DE TRANSPORTE (Dallas S.A.) 
SOLUCION OPTIMA 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 INTRODUCCIÓN 
MODELO DE TRANSPORTE 
DEMANDANTES OFERENTES 
1 1 
2 2 
m n 
a2 
am 
b2 
a1 b1 
bm 
. 
. 
. 
. 
. 
. 
Xij: cantidad transportada desde la fuente i al destino j 
C11, X11 
Cij, Xij 
Cij: Costo del transporte unitario desde la fuente i al destino j 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 INTRODUCCIÓN 
MODELO DE TRANSPORTE 
El objetivo general es encontrar el mejor plan de 
distribución. 
 
 







 


 
ijij
x
j
b j
i
a i
mjbx
niax
aSujeto
xcZMinimizar
j
m
j
ij
i
n
i
ij
m
i
n
j
ijij
0
....1
....1
:
1
1
1 1
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 INTRODUCCIÓN 
MODELO DE TRANSPORTE 
• PASO 1: 
– DETERMINAR UNA SOLUCIÓN BÁSICA FACTIBLE 
 
• PASO 2 : 
– UTILIZAR CONDICIÓN DE OPTIMALIDAD, PARA 
DETERMINAR LA VARIABLE DE ENTRADA. 
 
• PASO 3: 
– UTILIZAR LA CONDICIÓN DE FACTIBILIDAD, PARA 
DETERMINAR LA VARIABLE DE SALIDA. 
 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 DETERMINACIÓN DE LA 
SOLUCIÓN INICIAL FACTIBLE 
• Dado que el modelo esta 
equilibrado, las soluciones básicas 
factibles son: 
 
𝒏 +𝒎− 𝟏 
• Para encontrar esta solución 
inicial 
– Esquina Noroeste. 
– Costo Mínimo. 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
PASO 1 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
• Este modelo esta relacionado a la 
búsqueda de una posible 
solución optima realizando 
aproximaciones. 
 El resultado de este método es 
una solución inicial factible, que 
servirá como entrada para ser 
evaluada por otro modelo el cual 
vera si esta es la mejor solución 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 MÉTODO DE APROXIMACIÓN DE 
VOGEL 
• Usa información de costos mediante 
el costo de oportunidad para 
determinar una solución inicial 
factible. 
• Se hace una diferencia que es el 
costo adicional por enviar una unidad 
desde el origen actual al segundo 
destino y no al primero. 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 MÉTODO DE APROXIMACIÓN DE 
VOGEL 
• PASO 0: 
– Equilibrar el sistema: 
 
 
 
 
Si suma de ofertas  Suma de demandas (exceso de oferta) 
  Crea demandante ficticio. 
Si suma de ofertas  Suma de demandas (exceso de demanda) 
  Crea un oferente ficticio. 
 
Ai Bj
j
n
i
m



11
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 MÉTODO DE APROXIMACIÓN DE 
VOGEL 
• PASO 1: 
– Para cada FILA y COLUMNA con alguna 
oferta o alguna demanda, determinar la 
diferencia no negativa entre los dos 
costos unitarios más bajos asociados 
con las variables no asignadas: 
“Penalización” o “Costo de 
Arrepentimiento” 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
• PASO 2: 
– Identificar la fila o columna con la mayor 
“Costo de Arrepentimiento”. 
• PASO 3: 
– Asignar lo máximo posible a la ruta no 
usada con el costo más bajo que se 
encuentra en la fila o columna con 
mayor penalización. 
• PASO 4: 
– Ajustar oferta y demanda. Tachar las 
filas o columnas satisfechas, sólo una. 
 
 
 
 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
• PASO 5: 
a) Si queda exactamente una fila o columna 
con cero oferta o demanda. ¡PARAR! 
b) Si queda una fila o columna con una 
oferta o demanda positiva, determinar 
las variables básicas en fila o columna 
por el costo mínimo. ¡PARAR! 
c) Si quedan filas o columnas con una 
oferta o demanda de cero, definir por 
costo mínimo. ¡PARAR! 
d) De lo contrario, volver al paso 1 
 
 
 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
D 1 D 2 D 3 D 4 
Penalización 
O 1 
10 2 20 11 15 
O 2 
12 7 9 20 25 
O 3 
4 14 16 18 10 
5 15 15 15 50 
P 
5 
10 – 2 = 8 
9 – 7 = 2 
14 – 4 = 10 
18 – 11 = 7 16 – 9 = 7 7– 2 = 5 10 – 4 = 6 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
D 1 D 2 D 3 D 4 P 
O 1 
10 2 20 11 15 8 9 
O 2 
12 7 9 20 25 2 2 
O 3 
4 14 16 18 10 10 2 
5 
5 15 15 15 50 
P 6 
- 
 
5 
5 
7 
7 
7 
7 
15 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
D 1 D 2 D 3 D 4 P 
O 1 
10 2 20 11 15 8 9 9 
15 
O 2 
12 7 9 20 25 2 2 11 
O 3 
4 14 16 18 10 10 2 2 
5 
5 15 15 15 50 
P 6 
- 
- 
5 
7 
- 
7 
7 
7 
7 
7 
7 
15 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
D 1 D 2 D 3 D 4 P 
O 1 
10 2 20 11 15 
15 
O 2 
12 7 9 20 25 
15 
O 3 
4 14 16 18 10 
5 
5 15 15 15 50 
P 
0 
10 
5 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
D 1 D 2 D 3 D 4 
O 1 
10 2 20 11 15 
15 0 
O 2 
12 7 9 20 25 
15 10 
O 3 
4 14 16 18 10 
5 5 
5 15 15 15 50 
𝒁 = 𝟏𝟓 × 𝟐 + 𝟎 × 𝟏𝟏 + 𝟏𝟓 × 𝟗 + 𝟏𝟎 × 𝟐𝟎 + 𝟓 × 𝟒 + 𝟓 × 𝟏𝟖 = 𝟒𝟕𝟓 
MÉTODO DE APROXIMACIÓN DE 
VOGEL 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
01
D1
03
02
D2
D3
D4
Fabricas Almacenes
RESPUESTA: 
 
X12 = 15 
X14 = 0 
 (Var.Básica) 
X23 = 15 
X24 = 10 
X31 = 5 
X34 = 5 
 
Z = 475 
 
15 
25 
10 
5 
15 
15 
15 
15 
0 
15 
10 
5 
5 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Ejemplo 2 Método de 
Aproximación Vogel 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Fijarse que en 
este ejemplo las 
celdas usan el 
formato: 
 Cij 
Xij 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Ejemplo Método de 
Aproximación Vogel 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Ejercicios 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
RPG tiene cuatro plantas ensambladoras en Europa. 
Están ubicadas en Leipzig, Alemania (1);Nancy, 
Francia (2); Lieja, Bélgica (3), y Tilburgo, Holanda 
(4). Las máquinas ensambladoras usadas en estas 
plantas se producen en Estados Unidos y se 
embarcan a Europa. Llegaron a los puertos de 
Amsterdan (1), Amberes (2) y El Havre (3). 
Los planes de producción del tercer trimestre (julio a 
septiembre) ya han sido formulados. Los 
requerimientos (la demanda en destinos) de 
motores diesel E-4 son los siguientes: 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Planta Cantidad de 
Motores 
(1) Leipz 400 
(2) Nancy 900 
(3) Lieja 200 
(4) Tilburgo 500 
Puerto Cantidad de 
Motores 
(1) Amsterdan 500 
(2) Amberes 700 
(3) El Hevre 800 
La cantidad disponible de máquinas E-4 
en los puertos (oferta en orígenes) son: 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIORPG 
Desde 
el 
origen 
 
1 
 
2 
 
3 
 
4 
1 12 13 4 6 
2 6 4 10 11 
3 10 9 12 4 
Al destino 
Los costos ($) de transporte de un motor desde un origen a 
un destino son: 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO 
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
500
2 6 4 10 11
700
3 10 9 12 4
800
Demanda 400 900 200 500 2000
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6 2
200 500
2 6 4 10 11 2
700
3 10 9 12 4 5
800
Demanda 400 900 200 500 2000
PENAL. 4 5 6 2
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6 2
200 500
2 6 4 10 11 2
700
3 10 9 12 4 5
800
Demanda 400 900 200 500 2000
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6 6
200 300 500
2 6 4 10 11 2
700
3 10 9 12 4 5
800
Demanda 400 900 200 500 2000
PENAL. 4 5 2
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6 6
200 300 500
2 6 4 10 11 2
700
3 10 9 12 4 5
800
Demanda 400 900 200 500 2000
PENAL. 4 5 2
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6
200 300 500
2 6 4 10 11 2
700
3 10 9 12 4 5
200 800
Demanda 400 900 200 500 2000
PENAL. 4 5 7
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6
200 300 500
2 6 4 10 11 2
700
3 10 9 12 4 5
200 800
Demanda 400 900 200 500 2000
PENAL. 4 5 7
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6
200 300 500
2 6 4 10 11 2
700 700
3 10 9 12 4 1
200 800
Demanda 400 900 200 500 2000
PENAL. 4 5
Plantas
Puertos 1 2 3 4 Oferta PENAL.
1 12 13 4 6
200 300 500
2 6 4 10 11 2
700 700
3 10 9 12 4 1
200 800
Demanda 400 900 200 500 2000
PENAL. 4 5
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700 700
3 10 9 12 4
400 200 800
Demanda 400 900 200 500 2000
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700 700
3 10 9 12 4
400 200 800
Demanda 400 900 200 500 2000
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700 700
3 10 9 12 4
400 200 200 800
Demanda 400 900 200 500 2000
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700 700
3 10 9 12 4
400 200 800
Demanda 400 900 200 500 2000
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 EJERCICIO RPG 
Plantas
Puertos 1 2 3 4 Oferta
1 12 13 4 6
200 300 500
2 6 4 10 11
700 700
3 10 9 12 4
400 200 200 800
Demanda 400 900 200 500 2000
¿Es solución básica factible? n + m - 1 = 6 
𝒁 = 𝟒 × 𝟐𝟎𝟎 + 𝟔 × 𝟑𝟎𝟎 + 𝟒 × 𝟕𝟎𝟎 + 𝟏𝟎 × 𝟒𝟎𝟎 + 𝟗 × 𝟐𝟎𝟎 + 𝟒 × 𝟐𝟎𝟎 
𝒁 = 𝟏𝟐𝟎𝟎𝟎 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Ejercicios 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo 
Un sistema de distribución semanal para un producto tiene las siguientes 
características: 
PLANTA 
CAPACIDAD 
SEMANAL 
DISTRIBUIDOR 
DEMANDA 
SEMANAL 
TALCA 75 Sta, Marta 50 
STGO. 100 Cordoba 50 
 Linares 100 
La siguiente tabla da las perdidas estimadas, por centro de distribución, por 
quedarse corto en los envíos: 
CENTRO Sta, Marta Cordoba Linares 
PERDIDAS(US$/UNIDAD) 2 3 2 
Los costos de transporte en US$ por unidad son los siguientes: 
DESDE \ HACIA Sta, Marta Cordoba Linares 
Talca 3 2 1 
Santiago 4 5 6 
La meta de la compañía es determinar un plan de envío factible que minimice la 
suma de los costos de transporte total y que considere las perdidas estimadas por 
pedidos no surtidos. 
Se pide: Formular como un problema de transporte. 
 Resolver mediante Metodo Optimizante de Transporte 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
PLANTA
Sta. Marta Cordoba Linares Ai
TALCA 3 2 1 75
STGO. 4 5 6 100
FICTICIO 2 3 2 25
Bj 50 50 100 200
DISTRIBUIDOR
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
PLANTA
1 2 3 4 Ai
1 15 17 14 25 40 u1
20 17 3
2 12 11 18 31 25 u2
15 10
3 1 20 30 60 35 u3
35
Bj 20 17 18 45 100
vj v1 v2 v3 v4
ALMACEN
Costo = 3311 
Paso 1: encontrar la Solución Inicial Factible.(ENO) 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 METODO OPTIMIZANTE: este método 
se basa en holguras complementarias 
del problema de transporte original y su 
dual. De esta forma se deberá 
determinar números ui para los 
depósitos y vj para los mercados, tal 
que: 
 ɗij = Cij – ( ui + vj ) 
 
 ɗij = 0 Para toda variable básica 
 (lo mismo que en el simplex) 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 • Si todos los ɗij son positivos, 
significa que el cuadro es la solución 
optima, en caso contrario, existirá 
una variable no básica candidata a 
ingresar a la base, se eligira aquella 
que su costo reducido es el mínimo 
ɗij . 
 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 • Para comenzar el método 
optimizante es necesario escoger la 
columna o fila con mayor cantidad 
de soluciones y asignar ui ó vj igual 
a cero. 
 
• Con estos valores Ui y Vj 
determinamos los costos reducidos: 
 
 ɗij = Cij – ( ui + vj ) 
 
 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
PLANTA
1 2 3 4 Ai
1 15 17 14 25 40 u1
20 17 3
2 12 11 18 31 25 u2
15 10
3 1 20 30 60 35 u3
35
Bj 20 17 18 45 100
vj v1 v2 v3 v4
ALMACEN
 
Sea U1 = 5 
X11 es básica: C11 = U1 + V1  15 = 5 + V1  V1 = 10 
X12 es básica: C12 = U1 + V2  17 = 5 + V2  V2 = 12 
X13 es básica: C13 = U1 + V3  14 = 5 + V3  V3 = 9 
X23 es básica: C23 = U2 + V3  18 = U2 + 9  U2 = 9 
Así sucesivamente 
Paso 2: Definirse un valor arbitrario de ui o vj y a partir de este calcular los 
restantes utilizando la condición que el precio sombra de las v. básicas es cero, 
es decir: ij = Cij – Ui – Vj = 0  Cij = Ui + Vj (para v. basicas) 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
X14 es no básica: 14 = C14 – U1 – V4 = 25-5-22 = -2 
X21 es no básica: 21 = C21 – U2 – V1 = 12-9-10 = -7 
Así sucesivamente. 
Como hay ij negativos se debe iterar, ingresa a la base X31 ya que es 
el mas negativo y se la hace ingresar con un valor igual a “ “. 
Paso 3: calcular para las variables no básicas el valor ij dado por 
 ij = Cij – Ui – Vj = 0 
Si todas las variables no básicas tiene este valor positivo estamos en 
presencia de una solución optima, si una variable no básica tiene este 
valor negativo se debe iterar ingresando a la base la variable no básica 
que tenga el ij màs negativo, así: 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
PLANTA
1 2 3 4 Ai
1 15 17 14 25 40
20 17 3
2 12 11 18 31 25
15 10
3 1 20 30 60 35
 35
Bj 20 17 18 45 100
ALMACEN
Ingresa X31 con un valor igual a , esto provoca un desequilibrio entre las ofertas 
y demandas por lo cual se debe equilibrar sumando y restando  entre las 
variables basicas siguiendo una ruta cerrada y unica. 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
PLANTA
1 2 3 4 Ai
1 15 17 14 25 40
20 -  17 3 +
2 12 11 18 31 25
15 -  10 +
3 1 20 30 60 35
 + 35 - 
Bj 20 17 18 45 100
ALMACEN
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
PLANTA
1 2 3 4 Ai
1 15 17 14 25 40
20- 17 3+
2 12 11 18 31 25
15- 10+
3 1 20 30 60 35
 35-
Bj 20 17 18 45 100
ALMACEN
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
PLANTA1 2 3 4 Ai
1 15 17 14 25 40
20- 17 3+
2 12 11 18 31 25
15- 10+
3 1 20 30 60 35
 35-
Bj 20 17 18 45 100
ALMACEN
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Entra a la base X31 y sale X23, con 𝜃 = 15 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Paso 4: para ver cual variable no básica se convertirá en básica, se debe 
escoger un valor para  que garantice que las variables de decisión se 
mantengan positivas en la base, así se busca: 
Min { 35 , 15 , 20 } 
Luego ingresa X31 con un valor igual a 15 y X23 deja de ser variable básica. 
PLANTA
1 2 3 4 Ai
1 15 17 14 25 40
5 17 18
2 12 11 18 31 25
25
3 1 20 30 60 35
15 20
Bj 20 17 18 45 100
ALMACEN
Costo = 2746 
Así termina una iteración, luego se debe volver al paso 2. 
Problemas Especiales de P.L 
Problemas de Transporte: Ejemplo -- Solución 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Ejercicios 
 
Problema de la Foster Generators 
 Se transporta un producto desde 3 
plantas hasta 4 centros de distribución: 
Origen Planta 
Capacidad de
Producción en 3
meses (unidades)
1 Cleveland 5 000
2 Bedford 6 000
3 York 2 500
Total 13 500
Destino
Centro de
Distribución
Pronóstico de la
demanda a 3
meses (unidades)
1 Boston 6 000
2 Chicago 4 000
3 St. Louis 2 000
4 Lexigton 1 500
Total 13 500
Problema de la Foster Generators 
Costos 
Origen Boston Chicago St Louis Lexigton Producción
Cleveland 3 2 7 6 5000
Bedford 7 5 2 3 6000
York 2 5 4 5 2500
Demanda 6000 4000 2000 1500
13500
13500
Costo por unidad distribuida
Destino
Problema de la Foster Generators 
Representación en Red 
O1 [5000] 
O2 [6000] 
O3 [2500] 
D1 [6000] 
[4000] 
[2000] 
[1500] 
D2 
D3 
D4 
2 
4 
5 
Plantas 
Nodos de Origen 
Centros de Dist. 
Nodos de Destino 
Rutas de 
Distribución 
Arcos 
Planteamiento matemático 
Sea Z el costo total de transporte y sea xij (i=1,2,3;j=1,2,3,4) el 
número de unidades transportadas de la planta i al almacén j. 
)4,3,2,1;3,2,1(0
1500
2000
4000
6000
2500
6000
5000
545232
576723
342414
332313
322212
312111
34333231
24232221
14131211
343332312423
222114131211

++
++
++
++
+++
+++
+++
+++++
++++++
jix
xxx
xxx
xxx
xxx
xxxx
xxxx
xxxx
xxxxxx
xxxxxxZ
ij
nesrestriccio las a Sujeta
Max 
Solución óptima para el problema 
del transporte de la Foster 
Origen Boston Chicago St Louis Lexigton Producción
Cleveland 3500 1500 0 0 5000
Bedford 0 2500 2000 1500 6000
York 2500 0 0 0 2500
Demanda 6000 4000 2000 1500 39500
Unidades que se envían
Destino
COSTO 
Problema General 
 Se refiere (en sentido literal o figurado) a la 
distribución de cualquier bien desde cualquier 
grupo de centros de suministro, llamados 
orígenes a cualquier grupo de centros de 
distribución llamados destinos de manera que se 
minimicen los costos totales de distribución. 
Unidades de un bien, m orígenes, n destinos, 
si recursos en el origen i (nosotros usamos ai), 
demanda dj en el destino j (nosotros usamos bj), 
costo cij por unidad distribuida desde el origen i al 
destino j. 
El modelo general 
1 2 … n Recursos
1 c11 c12 … c1n s1
Origen 2 c21 c22 … c2n s2
… … … … …
m cm1 cm2 … cmn sm
Demanda d1 d2 … dn
Destino
Costo por unidad distribuida

Representación de red para el problema general 
S1 [s1] 
S2 [s2] 
Sm [sm] 
D1 [-d1] 
D2 [-d2] 
Dm [-dm] 
c11 
c12 
c1n c21 
c22 
c2n 
cm1 
cm2 
cmn 
Planteamiento matemático modelo general 
.y para,0
,,...,2,1 para
,,...,2,1 para
a sujeta
min
1
1
1 1
jix
njdx
misx
xcZ
ij
m
j
jij
n
j
jij
m
i
n
j
ijij









 
Variantes del Problema 
1. La oferta total no es igual a la 
demanda total 
2. Maximización en lugar de 
minimización 
3. Capacidades en las rutas o mínimos 
en las rutas 
4. Rutas inaceptables 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
 
88 
PROBLEMAS ESPECIALES DE PROGRAMACION LINEAL 
PROBLEMAS DE ASIGNACION 
Ivàn Santelices Malfanti 
isanteli@ubiobio.cl 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación 
Como ya se sabe, los problemas de transporte son un caso especial de 
P.L. y a la vez un caso especial de transporte son los problemas 
conocidos como de “ASIGNACIÓN”, los que se caracterizan por que la 
oferta y demanda unitaria de cada centro es igual a 1. 
 
Por ser un problema especial o particular también cuenta con una 
metodología propia de resolución conocida como método “Húngaro” o 
“Korug”. 
 
La formulación general de los problemas de asignación se presenta a 
continuación 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
• El problema de asignación es 
un tipo especial de problema de 
programación lineal en el que los 
asignados son recursos 
destinados a la realización de 
tareas. 
 
• Ejemplos: 
 empleados a trabajo 
 máquinas a tareas 
 períodos a tareas 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Supuestos de un problema de asignación 
1. El número de asignados es igual al 
número de tareas (se denota por n). 
(esto puede variar) 
2. Cada asignado se asigna exactamente a 
una tarea. 
3. Cada tarea debe realizarla exactamente 
un asignado. 
4. Existe un costo cij asociado con el 
asignado i (i=1,2,…,n). 
5. El objetivo es determinar cómo deben 
hacerse las asignaciones para minimizar 
los costos totales. 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Modelo General 
Min CT Cij Xij
i
m
j
n
( ) 
 
 
1 1
jiEnterosXij
jiXij
jiXij
njXij
miXij
n
j
m
i
,.....:
,.....1
,.....1,0:
],1[....1
],1[....1
1
1









Sujeto a: 
)y todapara binarias, (
y para,0
jix
jix
ij
ij
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Representación de red para el problema general 
S1 [1] 
S2 [1] 
Sm [1] 
D1 [1] 
D2 
[1] 
Dm [1] 
c11 
c12 
c1n 
c21 
c22 
c2n 
cm1 cm2 
cmn 
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
Oferta
1 2 3 4 Ai
1 3 4 11 6 1
2 7 3 12 8 1
3 3 4 6 11 1
4 14 8 7 6 1
Bj 1 1 1 1 4
Demanda
Paso 1: 
Verificar las condiciones de asignación, además verificar que la suma de ofertas es 
igual a la suma de demandas. Si no se cumple lo anterior se deben agregar tantos 
ficticios como sean necesarios todos con oferta o demanda igual a 1. 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
7 3 12 8
3 4 11 6
3 4 6 11
14 8 7 6
Paso 2: 
Restar el menor elemento o costo de cada fila a los restantes valores del costo de la 
misma fila: 
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
8 2 1 0
0 1 3 8
0 1 8 3
4 0 9 5
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
7 3 12 8
3 4 11 6
3 4 6 11
14 8 7 6
Paso 3: 
Identificar el elemento mas pequeño de cada columna y restarlo de los demás 
elementos de la misma columna, donde los valores ceros indicaran las posibles 
asignaciones factibles para el problema original: 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
8 2 0 0
0 1 2 8
0 1 7 3
4 0 8 5
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
Paso 4: 
Verificar la optimalidad del problema trazando el menor número de líneas rectas 
(horizontales o verticales) de modo tal de cubrir todos loas valores ceros: 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
8 2 0 0
0 1 2 8
0 1 7 3
4 0 8 5
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
0 1 7 3
4 0 8 5
8 2 0 0
0 1 2 8
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
Paso 4: 
Verificar la optimalidad del problema trazando el menor número de líneas rectas 
(horizontales o verticales) de modo tal de cubrir todos loas valores ceros: 
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj1 1 1 1 4
4 0 6 3
0 1 5 1
0 1 0 6
10 4 0 0
Paso 5: 
Prueba de optimalidad, si el número de líneas trazadas es igual al número de filas o 
columnas, indica que puede hacerse una asignación factible y optima en base a los 
valores ceros encontrados. Si el número de líneas es menor que el número de 
columnas o filas, se debe iterar. En nuestro caso debemos iterar, esto se realiza de la 
siguiente manera: 
1. Seleccionar de las celdas no marcadas el menor valor de costo (Crk)  Crk = 2 
2. Restar el Crk en todas las celdas no marcadas y sumarlo en aquellas con doble 
marca (intersección entre rectas). Los demás elementos permanecen igual. 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
8 2 0 0
0 1 2 8
0 1 7 3
4 0 8 5
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
4 0 6 3
0 1 5 1
0 1 0 6
10 4 0 0
Paso 6: 
Aplicar nuevamente la prueba de optimalidad mencionada en el paso 4. 
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
Paso 6: 
Aplicar nuevamente la prueba de optimalidad mencionada en el paso 4. 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
4 0 6 3
0 1 5 1
0 1 0 6
10 4 0 0
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
0 0
0 0
0
0
Paso 7: 
Encontrar la o las asignaciones optimas a partir del cuadro final donde los valores 
cero seran posibles puntos de asignación, es decir aquellas Xij que tomaran valor “1”, 
recordando las restricciones iniciales. 
Problemas Especiales de P.L 
Problemas de Asignación: Método resolución 
1 2 3 4 Ai
1 1
2 1
3 1
4 1
Bj 1 1 1 1 4
1
1
0 1
0 1
Paso 7: 
Encontrar la o las asignaciones optimas a partir del cuadro final donde los valores 
cero seran posibles puntos de asignación, es decir aquellas Xij que tomaran valor “1”, 
recordando las restricciones iniciales. 
Costo Total = 3 + 3 + 6 + 6 = 18 
 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo Propuesto 
LA FAMILIA KLYNE 
Los tres hijos de Joe Klyne, John, Peter y Terri, quieren ganar algún 
dinero para cubrir sus gastos personales durante un viaje organizado 
por la escuela a la Boite “La gata salvaje”. El señor Klyne (que se 
destaca por ser un padre muy liberal) eligió tres tareas para sus hijos: 
podar el césped, pintar la cochera y lavar los automóviles de la familia. 
Para evitar las competencias anticipadas entre hermanos les pidió que 
que presentaran licitaciones (secretas) para lo que ellos creían un 
pago justo para cada una de las tres tareas. Quedaba entendido que 
los tres hijos aceptarían la decisión de su padre en lo concerniente a 
quien desempeñara cada tarea. La tabla siguiente resume las 
licitaciones recibidas: 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo Propuesto 
CANDIDATO PODAR PINTAR LAVAR
JOHN $15.00 $10.00 $9.00
PETER $9.00 $15.00 $10.00
TERRI $10.00 $12.00 $8.00
Basándose en esta información, ¿cómo debe asignar las 
tareas el señor Klyne? 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo -- Solución 
Solución 
1. Objetivo: 
 Minimizar el costo de licitación. 
 
2. Variables de decisión: 
 
 Xij : El hijo “i” realiza la tarea “j”. 
 0 = No participa 
 1 = Si participa 
 i : 1 = John / 2 = Peter / 3 = Terri 
 j : 1 = Podar / 2 = Pintar / 3 = Lavar 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo Propuesto -- 
Solución 
CANDIDATO TAREA
JOHN PINTAR
PETER PODAR
TERRI LAVAR
COSTO TOTAL = $27 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo en clase 
LA COMPETENCIA MORTAL 
Supongase que se tienen 8 candidatos para representar a la 
universidad en 5 pruebas de resistencia al trago en la 
competencia anual interuniversitaria. Por acuerdo de la 
federación se permitirá a cada participante estar en a lo más 
una prueba, además sólo existe presupuesto para enviar un 
representante por prueba. 
 
Se le pide a usted como asesor y experto en el tema, que forme 
el equipo optimo a enviar basado en el siguiente cuadro que 
representa el puntaje asignado a cada candidato en las 
diferentes pruebas. Obviamente se busca maximizar el puntaje 
conjunto de la selección. 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo en clase 
CANDIDATO La descorchada Los cinco litros 20 golpeados La mezcolanza El tinto
veloz al hilo al minuto mortal del demonio
JUAN 75.00 45.00 80.00 73.00 90.00
DANIEL 90.00 40.00 0.00 70.00 68.00
PEDRO 47.00 50.00 63.00 54.00 70.00
LUIS 75.00 75.00 40.00 80.00 30.00
MARIA 40.00 60.00 38.00 91.00 70.00
CARLOS 60.00 40.00 75.00 91.00 87.00
JAVIER 48.00 90.00 75.00 90.00 75.00
JOSE 90.00 68.00 43.00 81.00 45.00
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
8 
Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo en clase -- Solución 
Solución 
1. Objetivo: 
 Maximizar el puntaje del equipo. 
 
2. Variables de decisión: 
 
 Xij : El candidato “i” participa en la prueba “j”. 
 0 = No participa 
 1 = Si participa 
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo en clase -- Solución 
CANDIDATO La descorchada Los cinco litros 20 golpeados La mezcolanza El tinto FICT 1 FICT 2 FICT 3
veloz al hilo al minuto mortal del demonio Ai
JUAN -75.00 -45.00 -80.00 -73.00 -90.00 0.00 0.00 0.00 1
DANIEL -90.00 -40.00 0.00 -70.00 -68.00 0.00 0.00 0.00 1
PEDRO -47.00 -50.00 -63.00 -54.00 -70.00 0.00 0.00 0.00 1
LUIS -75.00 -75.00 -40.00 -80.00 -30.00 0.00 0.00 0.00 1
MARIA -40.00 -60.00 -38.00 -91.00 -70.00 0.00 0.00 0.00 1
CARLOS -60.00 -40.00 -75.00 -91.00 -87.00 0.00 0.00 0.00 1
JAVIER -48.00 -90.00 -75.00 -90.00 -75.00 0.00 0.00 0.00 1
JOSE -90.00 -68.00 -43.00 -81.00 -45.00 0.00 0.00 0.00 1
Bj 1 1 1 1 1 1 1 1 8
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Problemas Especiales de P.L 
Problemas de Asignación: Ejemplo en clase -- Solución 
CANDIDATO Prueba 
Asignada
JUAN 20 golpeados al minuto
DANIEL La descorchada veloz
PEDRO No Participa
LUIS No Participa
MARIA La mezcolanza mortal
CARLOS El tinto del demonio
JAVIER Cinco lts. Al hilo
JOSE No Participa
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 
 
El entrenador de un equipo de natación debe asignar 
competidores para la prueba de 200 metros de relevo 
combinado que irán a las Olimpiadas Juveniles. Como 
muchos de sus mejores nadadores son rápidos en más de 
un estilo, no es fácil decidir qué nadador asignar cada uno 
de los cuatro estilos. Los cinco mejores nadadores y sus 
mejores tiempos (en segundos) en cada estilo son los 
siguientes. 
Problema Natación (Asignación) 
Carlos Cristy David Antony José
Dorso 37.7 32.9 33.8 37 35.4
Pecho 43.4 33.1 42.2 34.7 41.8
Mariposa 33.3 28.5 38.9 30.4 33.6
Libre 29.2 26.4 29.6 28.5 31.1
Tiempo de Nado
Problema Natación (asignación) 
Solución 
Carlos Cristy David Antony José
Dorso 0 0 1 0 0 1 = 1
Pecho 0 0 0 1 0 1 = 1
Mariposa 0 1 0 0 0 1 = 1
Libre 1 0 0 0 0 1 = 1
1 1 1 1 0
<= <= <= <= <=
1 1 1 1 1
TIEMPO Min.
Tiempo de Nado
126.2
Iv
á
n
 S
a
n
te
lic
e
s
 M
a
lf
a
n
ti
 Métodos de Resolución 
ALGEBRAICO 
LINDO (Linear Interactive and Discrete Optimizer) 
Se vera una breve explicación de cómo se puede usar LINDO para 
resolver PPL. Se explicará como se relaciona la información que 
proporciona este software con el estudio del algoritmo SIMPLEX a 
través de un caso practico. Además se vera como el programa ayuda a 
desarrollar el análisis de sensibilidad. 
Max Z = 3x1 + 4x2 - 2x3 + 6.5x4 ….(1) 
 
 S/A 
 x1 + x2 + 3x3 +x4  50 ….(2) 
 2x1 - 3x2 + 4x3 +2x4  45 ….(3) 
 x1 + x3+ x4  60 ….(4) 
 3.5x1 - 2x2 + 4x4  30 ….(5) 
 x1 + 3x4  33.5 ….(6) 
 x1 , x2 , x3  0