Programación lineal

Considere el problema de asignación de 3 tipos diferentes (tamaños) de aviones a 4 rutas. La siguiente tabla da la máxima capacidad (el número de aviones disponibles de cada tipo, el número de viajes diarios que cada avión puede hacer en una ruta dada y el número diario de pasajeros esperados para cada ruta, los costos de operación asociados por viaje en las diferentes rutas y se incluye un costo penal (pérdida de utilidad) por no poder otorgarle el servicio al pasajero.
Se tiene un flujo de 6 componentes, A, B, C, D, E y F; siendo el total del flujo 750 unidades, conteniendo respectivamente 100, 150, 120, 90 y 170 unidades de A a E; la propiedad explotable solo es una y tiene los siguientes valores para cada componente: 320, 300, 290, 250, 215 y 190 respectivamente.

1. Considere el problema de asignación de 3 tipos diferentes (tamaños) de aviones a 4 rutas. La siguiente
tabla da la máxima capacidad (el número de aviones disponibles de cada tipo, el número de viajes
diarios que cada avión puede hacer en una ruta dada y el número diario de pasajeros esperados para
cada ruta, los costos de operación asociados por viaje en las diferentes rutas y se incluye un costo
penal (pérdida de utilidad) por no poder otorgarle el servicio al pasajero.

avión
tipo
Capacidad
pasajeros
No.
aviones
No. vuelos diarios a cada ruta
1 2 3 4
1 50 5 3 2 2 1
2 30 8 4 3 3 2
3 20 10 5 5 4 2
Pasajeros esperados diarios 100 200 90 120

avión
tipo
Costo de operación por vuelo ($/vuelo)
1 2 3 4
1 1000 1100 1200 1500
2 800 900 1000 1000
3 600 800 800 900
Costo penal por pasajero 40 50 45 70
a) Formular el problema como un modelo de programación lineal, tal que, determine la
asignación del número de aviones a las rutas el cual deberán minimizar los costos totales del
sistema.
b) Resolver con Solver.
Resolución
1. ¿Qué se desea hacer, minimizar o maximizar?
Se desea minimizar los costos de operación de manera simultánea con la cantidad de
pasajeros para cada avión.
2. Identificación de las variables de decisión.
Sea X
ij el número de aviones tipo i asignado a la ruta j
3. Suposiciones
1. Cada avión asignado a cada ruta estará a su capacidad máxima de pasajeros.
2. Cada avión asignado a la ruta correspondiente, hará el número de vuelos completo.
Así, se identifica la matriz que conforma las variables de decisión para la formulación de la función
objetivo:
Ruta
Avión
1 2 3 4
1 X11 X12 X13 X14
2 X21 X22 X23 X24
3 X31 X32 X33 X34

2. Función Objetivo (F.O.) a minimizar:
34
0
11
min
ij ij
ij
X CX
= =

=

∑∑

Donde C
ij es el costo de operación de cada avión tipo i asignado a la ruta j
X
0=1000X 11+ 1100X 12+ 1200X 13+ 1500X 14+ 800X 21+ 900X 22+ 1000X 23+ 1000X 24+ 600X 31+ 800X 32+
800X
33+ 900X 34
Restricciones:
De disponibilidad,
4
1
ij i
j
Xe
=
≤∑
Donde e
i es la disponibilidad de cada avión tipo i
X
11+ X12+ X13+ X14<=5
X
21+ X22+ X23+ X24<=8
X
31+ X32+ X33+ X34<=10
De demanda diaria por ruta,
4
12 3
1
50 30 20
j j jj
j
X X Xd
=
++ ≥∑

Donde d
j es la demanda de cada ruta j
50X
11 + 30X 21 + 20X 31>=100
50X
12 + 30X 22 + 20X 32>=200
50X
13 + 30X 23 + 20X 33>=90
50X
14 + 30X 24+ 20X 34>=120
De número de viajes diarios por ruta,

ij ij
X m ij≤∀
Donde m
ij es el número máximo de vuelos de cada avión tipo i asignado a la ruta j
X
11<=3 X 12<=2 X 13<=2 X 14<=1
X
21<=4 X 22<=3 X 23<=3 X 24<=2
X
31<=5 X 32<=5 X 33<=4 X 34<=2
De factibilidad

3. 0
ij
X ij≥∀
Estructurar el problema para resolver mediante el método de las grandes M’s para las restricciones
mayor o igual que,


O mediante el programa PL03



Solución
X
11=0 X 12=4 X 13=0.6 X 14=0.4 X 21=0 X 22=0 X 23=0 X 24=2 X 31=5 X 32=0 X 33=3 X 34=2
1000X1+1100X2+1200X3+1500X4+800X5+900X6+1000X7+1000X8+600X9+800X10+800X11+900X12+0 S 1+0 S 2+0 S 3+0 S 4+0 S 5+0 S 6+0 S 7+0 S 8+0 S 9+0S10+0S11+0S12+0S13+0S14+0S15+0S16+0S17+0S18+0S19+1 MA 1+1 MA 2+1 MA 3+1 MA 4+1 MA 5
1X1 +1 X 2+1 X 3+1 X 4 +1 S 1 =5
+1 X 5+1 X 6+1 X 7+1 X 8 +1 S 2 =8
+1 X 9+1 X 1 0+1 X 1 1+1X12 -1S3 +1 A 1 =10
50X1 +3 0 X 5 +2 0 X 9 -1S4 +1 A 2 =100
+5 0 X 2 +3 0 X 6 +20X10 -1S5 +1 A 3 =200
+5 0 X 3 +3 0 X 7 +20X11 -1S6 +1 A 4 =90
+5 0 X 4 +3 0 X 8 +20X12 -1S7 +1 A 5=120
1X1 +1 S 8 =3
+1 X 2 +1 S 9 =2
+1 X 3 +1S10 =2
+1 X 4 +1S11 =1
+1 X 5 +1S12 =4
+1 X 6 +1S13 =3
+1 X 7 +1S14 =3
+1 X 8 +1S15 =2
+1 X 9 +1S16 =5
+1 X 1 0 +1S17 =5
+1 X 1 1 +1S18 =4
+1X12 +1S19 =2
Sujeto a:

4. Costo mínimo: 10940
Se tiene un flujo de 6 componentes, A, B, C, D, E y F; siendo el total del flujo 750 unidades,
conteniendo respectivamente 100, 150, 120, 90 y 170 unidades de A a E; la propiedad explotable solo
es una y tiene los siguientes valores para cada componente: 320, 300, 290, 250, 215 y 190
respectivamente. (a) No teniendo más información que la dada en el punto anterior, y aplicando
métodos algorítmicos, obtenga una propuesta de la mejor secuencia para separar este flujo en cada
uno de sus componentes. (b) Determine: +) El número de flujos totales, +) El número de flujos totales
a manejar algorítmicamente, +) El número de secuencias de separación a analizar, +) El número de
separadores a calcular el costo. (c) Recientemente, obtuvo información adicional que para este tipo
de flujo se ha desarrollado una correlación para el costo que es la siguiente: Co = 130 + 5X + 7X2 -
67/X – lnX. En donde la X es igual a la suma de F
alim dividida entre la Delta de separación elevada
(la delta) a la 0.6. Determine la mejor secuencia de separación. (d) Compare las dos soluciones (a y
c) comentando sus conclusiones.
(a) Tomando como punto de partida las reglas heurísticas de separación:
• Hacer la separación más difícil hasta el final
• Remueva el componente más abundante o la más fácil
• Favorecer diagramas que efectúan separaciones directas.

Componente Cantidad
Propiedad
explotable
Δsep
D 170 215

85
A 150 300
10
F 120 290
100
C 120 190
130
B 100 320
70
E 90 250


Sea c el número de componentes c=6
El número de separaciones mínima es
c-1; 6-1=5

5. (b)
Número de flujos totales,
()1
NFT
2
cc+
=

Número de flujos totales a manejar algorítmicamente,
()1
NFaMA
2
cc−
=
()66 1
NFaMA 15
2
−
= =
Número de secuencias de separación a analizar,
()( )
()
2 1!
NSec
! 1!
c
cc
−
=
−

()( )
()
26 1 !
NSec 42
6! 6 1 !
−
= =
−

Número de separadores a calcular el costo.
()()11
NSepCA
6
cc c−+
=
()()66 1 6 1
NSepCA 35
6
−+
= =


D
A
F
C
B
E
B
E
D
A
F
C
B
E
A
F
C
D
C
A
F
A
F
1
2
3
4
5

6. (c) Teniendo la información del costo, se puede determinar una mejor secuencia de separación

El valor del costo para cada separación es:
2
0
67
130 5 7 ln( )C XX X
X
= + + −−

Donde:
0.6
alim
Sep
F
X=
∆∑

1
()
00.6
750
47.3218 16036.806
100
XC= = =
2
()
00.6
440
30.6056 6834.34986
85
XC= = =
3
()
00.6
310
16.7107 2161.47007
130
XC= = =
4
()
00.6
190
14.8489 1740.46688
70
XC= = =
5
()
00.6
270
67.8209 32661.6532
10
XC= = =


D
A
F
C
B
E
B
E B
E
C
A
F
A
F
1
2
3
4
5
D
A
F
D
C
E
B

7. Ahora, comparando con la primera secuencia propuesta,

1
()
00.6
750
40.4292 11768.4363
130
XC= = =
2
()
00.6
560
38.9526 10940.5268
85
XC= = =
3
()
00.6
190
14.8489 1740.46688
70
XC= = =
4
()
00.6
390
24.6073 4485.75792
100
XC= = =
5
()
00.6
270
67.8209 32661.6532
10
XC= = =



La segunda secuencia de separación propuesta es mejor, debido a que el costo es el mínimo .

D
A
F
C
B
E
B
E
B
E
C
A
F
A
F
1
2
3
4
5
D
A
F
D
C
E
B
0
16036.806C=
0
6834.34986C=
0
2161.47007C=
0
1740.46688C=
0
32661.6532C=

59434.746
Costo Total

D
A
F
C
B
E
B
E
D
A
F
C
B
E
A
F
C
D
C
A
F
A
F
1
2
3
4
5
0
11768.4363C=
0
10940.5268C=
0
1740.46688C=
0
4485.75792C=
0
32661.6532C=

61596.8411
Costo Total