FORMULACIÓN DIRECTA

A B
EST) 6 x1 + 16 x2 ≤ 48000
SOL) 12 x1 + 6 x2 ≤ 42000

PIN) 9 x1 + 9 x2 ≤ 36000

Z = 4 x1 + 3 x2 ⇒ Máx

x1 , x2 ≥ 0
 FORMULACIÓN DUAL

EST SOL PIN

A)
B)
FORMULACIÓN DIRECTA
A B
EST) 6 x1 + 16 x2 ≤ 48000
SOL) 12 x1 + 6 x2 ≤ 42000

PIN) 9 x1 + 9 x2 ≤ 36000

Z = 4 x1 + 3 x2 ⇒ Máx

x1 , x2 ≥ 0
 FORMULACIÓN DUAL

EST SOL PIN

A) 6 y1 + 12 y2 + 9 y3 ≥ 4
B)
FORMULACIÓN DIRECTA
A B
EST) 6 x1 + 16 x2 ≤ 48000
SOL) 12 x1 + 6 x2 ≤ 42000

PIN) 9 x1 + 9 x2 ≤ 36000

Z = 4 x1 + 3 x2 ⇒ Máx

x1 , x2 ≥ 0
 FORMULACIÓN DUAL

EST SOL PIN

A) 6 y1 + 12 y2 + 9 y3 ≥ 4
B) 16 y1 + 6 y2 + 9 y3 ≥ 3

Z = 48.000 y1 + 42.000 y2 + 36.000 y3 ⇒ Mín

y1 , y2 , y3 ≥ 0
FORMULACIÓN DIRECTA
A B
EST) 6 x1 + 16 x2 ≤ 48000
SOL) 12 x1 + 6 x2 ≤ 42000

PIN) 9 x1 + 9 x2 ≤ 36000

Z = 4 x1 + 3 x2 ⇒ Máx

x1 , x2 ≥ 0
 FORMULACIÓN DUAL

EST SOL PIN

A) 6 y1 + 12 y2 + 9 y3 ≥ 4
B) 16 y1 + 6 y2 + 9 y3 ≥ 3

Z = 48.000 y1 + 42.000 y2 + 36.000 y3 ⇒ Mín

 FORMULACIÓN DUAL

EST SOL PIN

A) 6 y1 + 12 y2 + 9 y3 ≥ 4
B) 16 y1 + 6 y2 + 9 y3 ≥ 3

Z = 48.000 y1 + 42.000 y2 + 36.000 y3 ⇒ Mín

yi ≥ 0
DIRECTO DUAL

MAX: Z = 4 x1 + 3 x2 MIN: 48.000 y1 + 42.000 y2 + 36.000 y3

6 x1 + 16 x2 ≤ 48000
6 y1 + 12 y2 + 9 y3 ≥ 4
12 x1 + 6 x2 ≤ 42000
16 y1 + 6 y2 + 9 y3 ≥ 3
9 x1 + 9 x2 ≤ 36000
yi ≥ 0
xi ≥ 0
 EST SOL PIN A B

A) 6 y1 + 12 y2 + 9 y3 - y4 = 4
B) 16 y1 + 6 y2 + 9 y3 - y5 = 3

Z = 48.000 y1 + 42.000 y2 + 36.000 y3 ⇒ Mín

yi ≥ 0
 cj 48000 42000 36000 0 0 M M
ck xk Bk A’1 A’2 A’3 A’4 A’5 A’µ1 A’µ2 bi/aij
M y4 4 6 12 9 0.6667
-1 1
M y5 3 16 6 9 -1 1 0.1875
22M 18M 18M
Z =7M -M -M 0 0 zj-cj
-48000 -42000 -36000

ck xk Bk A’1 A’2 A’3 A’4 A’5 A’µ1 A’µ2 bi/aij

M y4 2.875 9.75 5.625 -0.375 -0.375 0.2949

-1 1
48000 y1 0.1875 1 0.375 0.5625 -0.0625 0.0625 0.5

9.75M 5.625M -0.375M -1.375M

Z = 2.875 M +9000 0 -M 0 zj-cj
-24000 -9000 +3000 +3000

ck xk Bk A’1 A’2 A’3 A’4 A’5 A’µ1 A’µ2 bi/aij

42000 y2 0.2949 1 0.5769 -0.1026 -0.0384 0.1026 -0.375 0.5111

48000 y1 0.0769 1 0.3462 0.0384 -0.0769 -0.0384 0.0625 0.2222

-12750
Z = 16076,92 0 0 4846.15 -2461.54 -2076.92 2466-M zj-cj
-M

ck xk Bk A’1 A’2 A’3 A’4 A’5 A’µ1 A’µ2

42000 y2 0.1667 -1.6667 1 -0.1667 0.1667 0.1667 -0.1667

36000 y3 0.2222 2.8889 1 0.1111 -0.2222 -0.1111 0.2222

Z = 15000 -14000 0 0 -3000 -1000 3000-M 1000-M

 TEOREMA FUNDAMENTAL DE
LA DUALIDAD

DIRECTA FINITA ⇔ DUAL FINITA

ZÓPTIMO DIRECTO = ZÓPTIMO DUAL

DEGENERADA ⇔ ALTERNATIVA

INCOMPATIBLE ⇔ POL. ABIERTO

 PROBLEMA DIRECTO

FORMA CANÓNICA FORMA ESTÁNDAR

TRANSFORMACIÓN TRANSFORMACIÓN
SIMÉTRICA ASIMÉTRICA

PROBLEMA DUAL
 DUAL SIMÉTRICO
DIRECTO DUAL
A·X≤B
X≥0
Z = C · X → Máx
 DUAL SIMÉTRICO
DIRECTO DUAL
A·X≤B AT · Y ≥ C
X≥0 Y≥0
Z = C · X → Máx Z = B · Y → Mín
 DUAL SIMÉTRICO
DIRECTO DUAL
A·X≤B AT · Y ≥ C
X≥0 Y≥0
Z = C · X → Máx Z = B · Y → Mín
A·X≥B
X≥0
Z = C · X → Mín
 DUAL SIMÉTRICO
DIRECTO DUAL
A·X≤B AT · Y ≥ C
X≥0 Y≥0
Z = C · X → Máx Z = B · Y → Mín
A·X≥B AT · Y ≤ C
X≥0 Y≥0
Z = C · X → Mín Z = B · Y → Máx
 DUAL ASIMÉTRICO
DIRECTO DUAL
A·X=B
X≥0
Z = C · X → Máx
 DUAL ASIMÉTRICO
DIRECTO DUAL
A·X=B AT · Y ≥ C
X≥0
Z = C · X → Máx Z = B · Y → Mín
 DUAL ASIMÉTRICO
DIRECTO DUAL
A·X=B AT · Y ≥ C
X≥0
Z = C · X → Máx Z = B · Y → Mín

A·X=B
X≥0
Z = C · X → Mín
 DUAL ASIMÉTRICO
DIRECTO DUAL
A·X=B AT · Y ≥ C
X≥0
Z = C · X → Máx Z = B · Y → Mín

A·X=B AT · Y ≤ C
X≥0
Z = C · X → Mín Z = B · Y → Máx
DUAL SIMÉTRICO
MAX: Z = 4 x1 + 3 x 2 – x 3

16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 ≥ 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0
MAX: Z = 4 x1 + 3 x 2 – x 3

16 x1 + 6 x2 + 2 x3 ≤ 480
– 4 x1 – 5 x2 + 7 x3 ≤ – 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0
DIRECTO MAX: Z = 4 x1 + 3 x2 – x3
FORMA
16 x1 + 6 x2 + 2 x3 ≤ 480
CANÓNICA
– 4 x1 – 5 x2 + 7 x3 ≤ – 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0

MIN: Z = 480 y1 - 100 y2 + 500 y3

16 y1 – 4 y2 + 10 y3 ≥ 4
6 y1 – 5 y2 + 8 y3 ≥ 3
2 y1 + 7 y2 – 3 y3 ≥ – 1

yi ≥ 0
DIRECTO MAX: Z = 4 x1 + 3 x2 – x3
16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1+ 5 x2 – 7 x3 ≥ 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0

DUAL MIN: Z = 480 y1 - 100 y2 + 500 y3

16 y1 – 4 y2 + 10 y3 ≥ 4
6 y1 – 5 y2 + 8 y3 ≥ 3
– 2 y1 – 7 y2 + 3 y3 ≤ 1

yi ≥ 0
MAX: Z = 4 x1 + 3 x 2 – x 3

16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 = 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0
MAX: Z = 4 x1 + 3 x 2 – x 3

16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 ≤ 100
4 x1 + 5 x2 – 7 x3 ≥ 100
10 x1 + 8 x2 – 3 x3 ≤ 500
xi ≥ 0
MAX: Z = 4 x1 + 3 x 2 – x 3

16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 ≤ 100
– 4 x1 – 5 x2 + 7 x3 ≤ – 100
10 x1 + 8 x2 – 3 x3 ≤ 500
xi ≥ 0
 MAX: Z = 4 x1 + 3 x2 – x3
DIRECTO
FORMA 16 x1 + 6 x2 + 2 x3 ≤ 480
CANÓNICA
4 x1 + 5 x2 – 7 x3 ≤ 100
– 4 x1 – 5 x2 + 7 x3 ≤ – 100
10 x1 + 8 x2 – 3 x3 ≤ 500
xi ≥ 0

MIN: Z = 480 y1 + 100 y2 – 100 y2’ + 500 y3

16 y1 + 4 y2 – 4 y2’+ 10 y3 ≥ 4
6 y1 + 5 y2 – 5 y2’+ 8 y3 ≥ 3
2 y1 – 7 y2 + 7 y2’ – 3 y3 ≥ – 1

yi ≥ 0
 MAX: Z = 4 x1 + 3 x2 – x3
DIRECTO
16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 = 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0

MIN: Z = 480 y1 + 100 y2 – 100 y2’ + 500 y3

DUAL
16 y1 + 4 y2 – 4 y2’+ 10 y3 ≥ 4
6 y1 + 5 y2 – 5 y2’+ 8 y3 ≥ 3
– 2 y1 + 7 y2 – 7 y2’ + 3 y3 ≤ 1

yi ≥ 0
DUAL ASIMÉTRICO
MAX: Z = 4 x1 + 3 x 2 – x 3

16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 = 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0
 FORMA ESTÁNDAR

MAX: Z = 4 x1 + 3 x2 – x3

16 x1 + 6 x2 + 2 x3 + x4 = 480
4 x1 + 5 x2 – 7 x3 = 100
10 x1 + 8 x2 – 3 x3 + x5 = 500

xi ≥ 0
DIRECTO MAX: Z = 4 x1 + 3 x2 – x3

16 x1 + 6 x2 + 2 x3 ≤ 480
4 x1 + 5 x2 – 7 x3 = 100
10 x1 + 8 x2 – 3 x3 ≤ 500

xi ≥ 0

MIN: Z = 480 y1 + 100 y2 + 500 y3

DUAL
16 y1 + 4 y2 + 10 y3 ≥ 4
6 y1 + 5 y2 + 8 y3 ≥ 3
2 y1 – 7 y2 – 7 3 y3 ≥–1
y1 ≥0
y3 ≥0
 PASAJE
DE TABLA ÓPTIMA DIRECTA
A TABLA ÓPTIMA DUAL
(Y VICEVERSA)
MAX: Z = 4 x1 + 3 x2

Sujeto a:
6 x1 + 16 x2 ≤ 48000
12 x1 + 6 x2 ≤ 42000
9 x1 + 9 x2 ≤ 36000

siendo: x1, x2 ≥ 0 y continuas

0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3
0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

Z = 15.000
0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

y2
y3
Z = 15.000
 0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

42.000 y2 1/6
36.000 y3 2/9
Z = 15.000
 0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

42.000 y2 1/6 1
36.000 y3 2/9 1
Z = 15.000 0 0
x3 x4 x5 x1 x2
 0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

42.000 y2 1/6 -5/3 1 -1/6

36.000 y3 2/9 26/9 1
Z = 15.000 0 0
x3 x4 x5 x1 x2
 0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

42.000 y2 1/6 -5/3 1 -1/6 1/6

36.000 y3 2/9 26/9 1 1/9 -2/9
Z = 15.000 0 0
x3 x4 x5 x1 x2
 0 x3 14.000 1 5/3 -26/9
4 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 15.000 0 0 0 1/6 2/9
y4 y5 y1 y2 y3

42.000 y2 1/6 -5/3 1 -1/6 1/6

36.000 y3 2/9 26/9 1 1/9 -2/9
Z = 15.000 -14.000 0 0 -3.000 -1.000
x3 x4 x5 x1 x2
 xi

Z ⇒ MAX

yj

Z ⇒ MIN
 xi

Z ⇒ MIN

yj

Z ⇒ MAX
 xi
Aj

Z ⇒ MAX

+ _

yj

Z ⇒ MIN
 xi
Aj

Z ⇒ MIN

_ _

yj

Z ⇒ MAX
 xi
λj

Z ⇒ MAX

+ _

yj

Z ⇒ MIN
 xi
λj

Z ⇒ MIN

+ +

yj

Z ⇒ MAX
MIN: Z = x1 + 0,5 x2 + 2 x3

Sujeto a:
3 x1 + 2 x2 + 4 x3 ≤ 3,6
x1 + 0,5 x2 + 2 x3 ≥ 1,2
x1 + x2 + x3 = 1

siendo: x1, x2 , x3 ≥ 0
 1 0,5 2 M
cK xK BK A1 A2 A3 A4 A5 λ
1 x1 0,4 1 2 1 4
0 x5 0,4 -0,5 -1 1 -2
2 x3 0,6 1 1 -1 -3
Z (MIN) = 1,6 -0,5 -1 -2-M
y4 y5 y6 y1 y2 y3

3,6 1,2 1
bK xK BK A’1 A’2 A’3 A’4 A’5 A’6
3,6 y1 1 1 1 -1 1
1 y3 -2 -2 1 4 -3
0 y5 0,5 0,5 -2 1 -1
Z (MAX) = 1,6 0,4 0,4 0,6
x4 x5 x6 x1 x2 x3
 1 0,5 2 M
cK xK BK A1 A2 A3 A4 A5 λ
1 x1 0,4 1 2 1 4
0 x5 0,4 -0,5 -1 1 -2
2 x3 0,6 1 1 -1 -3
Z (MIN) = 1,6 -0,5 -1 -2-M
y4 y5 y6 y1 y2 y3

3,6 1,2 1
bK xK BK A’1 A’2 A’3 A’4 A’5 A’6
3,6 y1 1 1 1 -1 1
1 y3 -2 -2 1 4 3
0 y5 0,5 0,5 -2 1 -1
Z (MAX) = 1,6 0,4 0,4 0,6
x4 x5 x6 x1 x2 x3
 1 0,5 2 M
cK xK BK A1 A2 A3 A4 A5 λ
1 x1 0,4 1 2 1 4
0 x5 0,4 -0,5 -1 1 -2
2 x3 0,6 1 1 -1 -3
Z (MIN) = 1,6 -0,5 -1 -2-M
y4 y5 y6 y1 y2 y3

3,6 1,2 1
bK xK BK A’1 A’2 A’3 A’4 A’5 A’6
3,6 y1 1 1 1 -1 1
1 y3 -2 -2 1 4 3
0 y5 0,5 0,5 -2 1 -1
Z (MAX) = 1,6 0,4 0,4 0,6
x4 x5 x6 x1 x2 x3
 1 0,5 2 M
cK xK BK A1 A2 A3 A4 A5 λ
1 x1 0,4 1 2 1 4
0 x5 0,4 -0,5 -1 1 -2
2 x3 0,6 1 1 -1 -3
Z (MIN) = 1,6 -0,5 -1 -2-M
y4 y5 y6 y1 y2 y3

3,6 1,2 1
bK xK BK A’1 A’2 A’3 A’4 A’5 A’6
3,6 y1 1 1 1 -1 1
1 y3 -2 -2 1 4 -3
0 y5 0,5 0,5 -2 1 -1
Z (MAX) = 1,6 0,4 0,4 0,6
x4 x5 x6 x1 x2 x3
 1 0,5 2 M
cK xK BK A1 A2 A3 A4 A5 λ
1 x1 0,4 1 2 1 4
0 x5 0,4 -0,5 -1 1 -2
2 x3 0,6 1 1 -1 -3
Z (MIN) = 1,6 -0,5 -1 -2-M
y4 y5 y6 y1 y2 y3

3,6 1,2 1
bK xK BK A’1 A’2 A’3 A’4 A’5 A’6
3,6 y1 1 1 1 -1 1
1 y3 -2 -2 1 4 3
0 y5 0,5 0,5 -2 1 -1
Z (MAX) = 1,6 0,4 0,4 0,6
x4 x5 x6 x1 x2 x3
 TEOREMA FUNDAMENTAL DE LA DUALIDAD

DIRECTA FINITA ⇔ DUAL FINITA

ZÓPTIMO DIRECTO = ZÓPTIMO DUAL

DEGENERADA ⇔ ALTERNATIVA

INCOMPATIBLE ⇔ POL. ABIERTO

 cj 3 3 0 0 0
ck xk B A1 A2 A3 A4 A5
0 x3 14.000 1 5/3 -26/9
3 x1 3.000 1 1/6 -1/9
3 x2 1.000 1 -1/6 2/9
Z = 12.000 0 0 0 0* 3/9
ALTERNATIVA

cj 3 3 0 0 0
ck xk B A1 A2 A3 A4 A5
42.000 y2 0 -5/3 1 -1/6 1/6
36.000 y3 3/9 26/9 1 1/9 -2/9
Z = 12.000 -14.000 0 0 -3.000 -1.000

DEGENERADA
 INTERPRETACIÓN
ECONÓMICA
DEL PROBLEMA DUAL
6 y1
6 y1 + 12 y2
6 y1 + 12 y2 + 9 y3
6 y1 + 12 y2 + 9 y3 ≥ 4
 EST SOL PIN
A) 6 y1 + 12 y2 + 9 y3 ≥ 4
 EST SOL PIN
A) 6 y1 + 12 y2 + 9 y3 ≥ 4
B) 16 y1 + 6 y2 + 9 y3 ≥ 3
 EST SOL PIN
A) 6 y1 + 12 y2 + 9 y3 ≥ 4
B) 16 y1 + 6 y2 + 9 y3 ≥ 3

Z = 48.000 y1 + 42.000 y2 + 36.000 y3 ⇒ Mín

 EST SOL PIN A B

A) 6 y1 + 12 y2 + 9 y3 - y4 = 4
B) 16 y1 + 6 y2 + 9 y3 - y5 = 3

Z = 48.000 y1 + 42.000 y2 + 36.000 y3 ⇒ Mín