Programacion lineal

2006’1 Pauta I3 -Problema 1 a) [0.5] Por plantear el problema [0.5] Demostrar que admite solución óptima
xij : Cantidad transportada desde la planta i a la ciudad j
Min

∑C

ij

X ij

Min 8 x11 + 6 x12 + 10 x13 + 9 x14 + 9 x 21 + 12 x 22 + 13x 23 + 7 x 24 + 14 x31 + 9 x32 + 16 x33 + 5 x34
s.a.

Oferta

x11 + x12 + x13 + x14 = 35 x 21 + x 22 + x 23 + x 24 = 50 x31 + x32 + x33 + x34= 40

Demanda

x11 + x 21 + x31 = 45 x12 + x 22 + x32 = 20 x13 + x 23 + x33 = 30 x14 + x 24 + x34 = 30

Signo
xij ≥ 0 ∀i, j i = 1,2,3 j = 1,2,3,4

Primera forma: Basta como se mostró en clases, si el problema es balanceado, entonces admite solución óptima Problema Balanceado ∑ Oferta =∑ Demanda =S

35+50+40=42+20+30+30 125=125 Por lo tanto, P) balanceado admite solución óptima
Formaalternativa: i) P no vacío: • Por regla Nor-Oeste existe una solución factible inicial y será calculada en b) ai b j • Otra forma por construcción ~ij = x S
ii)

P Cerrado y Acotado
ai b j S

Desigualdades amplias y xij acotadas por 0 ≤ xi j ≤ min{ai , b j } =
∴ Por (i), (ii) mediante T. B-W P) admite solución óptima.

b) [0.5] Por cada iteración (1) Base factible inicial aplicando ReglaNor-Oeste
35 10 20 20 10 30

Costos
8 9 14 v1 7 6 12 9 v2 10 10 13 16 v3 11 9 u1 1 7 u2 2 5 u3 5 v4 0

Costos Reducidos rij = cij − u i − v j
0 -5 -2 0 0 0 -2 -6 0 8 5 0

X32 entra a la base
35 10 20- ∆ +∆

20+ ∆ 10- ∆

30

∆ =MIN {20,10} =10 X33 deja la base
(2) Nueva base
35 10 10 30 10 30

Costos
8 6 10 9 u1 7 9 12 13 7 u2 8 14 9 16 5 u3 5 v1 v2 v3 v4 1 4 5 0

CostosReducidos rij = cij − u i − v j
0 -5 -2 2 0 0 0 -1 8 0 6 0

X12 entra a la base
35- ∆ + ∆ 10+ ∆ 10- ∆

30 30

∆ =MIN {35,10} =10 X22 deja la base
3) Nueva base
25 10 20 30 10 30

Costos
8 6 10 9 u1 2 9 12 13 7 u2 3 14 9 16 5 u3 5 v1 v2 v3 v4 6 4 10 0

Costos Reducidos rij = cij − u i − v j
0 0 3 0 -2 5 0 0 1 7 4 0

X13 entra a la base
25- ∆ 20+ ∆ 10 +∆ 30- ∆ 30

∆ =MIN {25,30} =25X11 deja la base 4) Nueva base
10 45 10 25 5 30

Costos
8 6 10 9 u1 2 9 12 13 7 u2 5 14 9 16 5 u3 5 v1 v2 v3 v4

4

4

8

0

Costos Reducidos rij = cij − u i − v j
2 0 5 0 3 0 0 0 3 7 2 0

FIN rij ≥ 0 Base Factible actual es óptima
10 45 10 25 5 30

x11 = 0 x31 = 0

x12 = 10 x32 = 10

x13 = 25 x 23 = 5 x33 = 0

x14 = 0 x 24 = 0 x34 = 30

x 21 = 45 x 22 = 0

ˆ v(Ρ) =8 * 0 + 6 * 10 + 10 * 25 + 9 * 0 + 9 * 45 + 12 * 0 + 13 * 5 + 7 * 0 + 14 * 0 + 9 * 10 + 16 * 0 + 5 * 30 = 1020

ˆ v(Ρ) = 1020
c) Dada la restricción adicional, P) ya no tiene la estructura clásica del problema de transporte. Se explotará la estructura de transporte a través del método de Dantzig y Wolfe. Concretamente la restricción adicional será considerada como única restricción decoordinación, de forma que el problema satélite (uno sólo en este caso) tenga la estructura clásica de transporte.

Dantzig-Wofe
mo=1 (nº de restricciones de coordinación) N=0 (nº de satélites) Las matrices del problema maestro son entonces de dimensión (mo+N)x(mo+N)=2x2
x12 + x13 ≤ 30 Restricción adicional, de COORDINACIÒN P Pr oblema de transporte, SATELITE

Solución básica inicial, regla N-0TALQUE A01 P1=0

 35 P11 = 10   

20

20 10

   30  

A01=[0 1 1 0 0 0 0 0 0 0 0 0] β ={S, λ11 ]=I= β -1
30  b =  ; 1

β −1 = I = 

1 0   0 1

(1) PRIMERA ITERACIÓN MAESTRA

Paso 1:
30 30 y o = β −1b = I   =   1 1 Paso 2:

35  0   0   0 10    20 T 1 p11 = c1 P1 = [8 6 10 9 9 12 13 7 14 9 16 5 ]   20    0 0   0  10  30    p11 = 8 * 35 + 9 * 10 + 12 * 20 + 13 * 20 + 16 * 10 + 30 * 5 = 1180 ps = 0 , cos to ho lg ura

π T = PB T β −1 = [ ps
En este caso

p11 ]β −1 = [0 1180 ] = π T

[

αT ]

α T = α = 1180 πT =π =0
SATELITE Min (c T − π 0 A0 ) x − α = c T x − α
Min c T x − 1180, x ∈ Ρ

Se resolvió en la letra b) 10 25   45  2 5 P1 =     10 30 

ˆ v( s ) = 1020 − 1180 =...