Ejercicios
1. Maximizar
Z = 3x1 + 4 x2 + 3x3/2
Sujeta a
–x1 – 2x2 ≥ –10 x1 + 2x2 ≤ 10
2x1 + 2x2 + x3 ≤ 10 2x1 + 2x2 + x3 ≤ 10
xi ≥ 0 xi ≥ 0
x1 x2 x3 S1 S2 Z b
S1 1 2 0 1 0 0 10
S2 2 2 1 0 1 0 10
Z –3 –4 –3/2 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 1 2 0 1 0 0 10 10/2 = 5
S2 2 2 1 0 1 0 10 10/2 = 5
Z –3 –4 –3/2 0 0 1 0
Se selecciona S1 o S2
x1 x2 x3 S1 S2 Z b
x2 1/2 1 0 1/2 0 0 5
S2 2 2 1 0 1 0 10
Z –3 –4 –3/2 0 0 1 0
x1 x2 x3 S1 S2 Z b
x2 1/2 1 0 1/2 0 0 5
S2 1 0 1 –1 1 0 0
Z –1 0 –3/2 2 0 1 20
x1 x2 x3 S1 S2 Z b
x2 1/2 1 0 1/2 0 0 5
x3 1 0 1 –1 1 0 0
Z 1/2 0 0 1/2 3/2 1 20
El valor máximo de Z es 20 y ocurre cuando
x1 = 0, x2 = 5, x3 = 0,(y S1 = 1/2, S2 = 3/2)
2. Maximizar
W = x1 – 12 x2 + 4x3
Sujeta a
4x1 + 3x2 –x3 ≤ 1 4x1 + 3x2 –x3 ≤ 1
x1 + x2 – x3 ≥ –2 – x1 – x2 + x3 ≤ 2
–x1 + x2 + x3 ≥ –1 x1 – x2 – x3 ≤ 1
xi ≥ 0 xi ≥ 0
x1 x2 x3 S1 S2 S3 W b
S1 4 3 –1 1 0 0 0 1
S2 –1 –1 1 0 1 0 0 2
S3 1 –1 –1 0 0 1 0 1
W –1 12 –4 0 0 0 1 0
x1 x2 x3 S1 S2 S3 W b
S1 4 3 –1 1 0 0 0 1
S2 –1 –1 1 0 1 0 0 2 2/1 = 2
S3 1 –1 –1 0 0 1 0 1
W –1 12 –4 0 0 0 1 0
x1 x2 x3 S1 S2 S3 W b
S1 3 2 0 1 1 0 0 3
x3 –1 –1 1 0 1 0 0 2
S3 0 –2 0 0 1 1 0 3
W –5 8 0 0 4 0 1 8
x1 x2 x3 S1 S2 S3 W b
S1 3 2 0 1 1 0 0 3 3/3 = 1
x3 –1 –1 1 0 1 0 0 2
S3 0 –2 0 0 1 1 0 3
W –5 8 0 0 4 0 1 8
x1 x2 x3 S1 S2 S3 W b
x1 1 2/3 0 1/3 1/3 0 0 1
x3 –1 –1 1 0 1 0 0 2
S3 0 –2 0 0 1 1 0 3
W –5 8 0 0 4 0 1 8
x1 x2 x3 S1 S2 S3 W b
x1 1 2/3 0 1/3 1/3 0 0 1
x3 0 –1/3 1 1/3 4/3 0 0 3
S3 0 –2 0 0 1 1 0 3
W 0 34/3 0 5/3 17/3 0 1 13
El valor máximo de W es 13 y ocurre cuando
x1 = 1, x2 = 0, x3 = 3,(S1=5/3, S2=17/3, S3 = 0)
3. Maximizar
W = 4x1 + 10 x2 – 6x3 – x4
Sujeta a
x1 ≤ 1 – x3 + x4 x1 + x3 – x4 ≤ 1
– x1 + x2 – x4 ≥ – 2 x1 – x2 + x4 ≤ 2
x1 + x2 – x3 + x4 – 4 ≤ 0 x1 + x2 – x3 + x4 ≤ 4
xi ≥ 0 xi ≥ 0
x1 x2 x3 x4 S1 S2 S3 W b
S1 1 0 1 –1 1 0 0 0 1
S2 1 –1 0 1 0 1 0 0 2
S3 1 1 –1 1 0 0 1 0 4
W –4 –10 6 1 0 0 0 1 0
x1 x2 x3 x4 S1 S2 S3 W b
S1 1 0 1 –1 1 0 0 0 1
S2 1 –1 0 1 0 1 0 0 2
S3 1 1 –1 1 0 0 1 0 4
W –4 –10 6 1 0 0 0 1 0
x1 x2 x3 x4 S1 S2 S3 W b
S1 1 0 1 –1 1 0 0 0 1
S2 2 0 –1 2 0 1 1 0 6
x2 1 1 –1 1 0 0 1 0 4
W 6 0 –4 11 0 0 11 1 40
x1 x2 x3 x4 S1 S2 S3 W b
S1 1 0 1 –1 1 0 0 0 1
S2 2 0 –1 2 0 1 1 0 6
x2 1 1 –1 1 0 0 1 0 4
W 6 0 –4 11 0 0 11 1 40
x1 x2 x3 x4 S1 S2 S3 W b
x3 1 0 1 –1 1 0 0 0 1
S2 3 0 0 1 1 1 1 0 7
x2 2 1 0 0 1 0 1 0 5
W 10 0 0 15 4 0 11 1 44
x1 x2 x3 x4 S1 S2 S3 W b
x3 1 0 1 –1 1 0 0 0 1
S2 3 0 0 1 1 1 1 0 7
x2 2 1 0 0 1 0 1 0 5
W 10 0 0 15 4 0 11 1 44
El valor máximo de W es 44 y ocurre cuando
x1=0, x2=5, x3 =1, x4 =0, (S1=4, S2=0, S3 = 11)
SOLUCIONES NO ACOTADAS
Si no existen cocientes en una tabla simplex,
entonces el problema de programación lineal
tiene una solución NO acotada
Maximizar
Z = 2x1 + 8x2 – 2x3
Sujeta a:
– 10x1 + 12x2 – 4x3 60
– 2x1 + 6x2 + 12x3 24
Maximizar
Z = 2x1 + 8x2 – 2x3
Sujeta a:
– 10x1 + 12x2 – 4x3 60
– 2x1 + 6x2 + 12x3 24
x1 x2 x3 S1 S2 Z b
S1 –10 12 –4 1 0 0 60
S2 –2 6 12 0 1 0 24
Z –2 –8 2 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 –10 12 –4 1 0 0 60
S2 –2 6 12 0 1 0 24
Z –2 –8 2 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 –10 12 –4 1 0 0 60
x2 –1/3 1 2 0 1/6 0 4
Z –2 –8 2 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 –10 12 –4 1 0 0 60
x2 –1/3 1 2 0 1/6 0 4
Z –2 –8 2 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 –6 0 –28 1 –2 0 12
x2 –1/3 1 2 0 1/6 0 4
Z –14/3 0 18 0 4/3 1 32
Maximizar
Z = 5x1 + 6x2 + x3
restricciones
9x1 + 3x2 – 2x3 5
4x1 + 2x2 – x3 2
x1 – 4x2 + x3 3
x1, x2, x3 ≥ 0
SOLUCIONES ÓPTIMAS MÚLTIPLES
En una tabla queda una solución optima, un
indicador igual a cero para variable no básica
sugiere la posibilidad de soluciones óptimas
múltiples.
x1 = a1, x2 = a2, …, xn = an
y
x1 = b1, x2 = b2, …, xn = bn
x1 = (1 – t )a1 + t b1
x2 = (1 – t )a2 + t b2
:
xn = (1 – t )an + t bn
para cualquier t donde 0 ≤ t ≤ 1
Maximizar
Z = 6x1 + 2x2 + x3
restricciones
2x1 + x2 + x3 7
– 4x1 – x2 ≥ –6
x1, x2, x3 ≥ 0
x1 x2 x3 S1 S2 Z b
S1 2 1 1 1 0 0 7
S2 4 1 0 0 1 0 6
Z –6 –2 –1 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 2 1 1 1 0 0 7
x1 1 1/4 0 0 1/4 0 3/2
Z –6 –2 –1 0 0 1 0
x1 x2 x3 S1 S2 Z b
S1 0 1/2 1 1 –1/2 0 4
x1 1 1/4 0 0 1/4 0 3/2
Z 0 –1/2 –1 0 3/2 1 9
x1 x2 x3 S1 S2 Z b
x3 0 1/2 1 1 –1/2 0 4
x1 1 1/4 0 0 1/4 0 3/2
Z 0 0 0 1 1 1 13
x1 = 3/2, x2 = 0, x3 = 4
x1 x2 x3 S1 S2 Z b
x3 –2 0 1 1 –1 0 1
x2 4 1 0 0 1 0 6
Z 0 0 0 1 1 1 13
x1 = 0, x2 = 6, x3 = 1
x1 = (1 – t )3/2 + 0t = 3/2(1 – t )
x2 = (1 – t )0+ 6t = 6t
x3 = (1 – t )4 + 1t = 4 – 3t
para cualquier t donde 0 ≤ t ≤ 1
Maximizar
Z = 4x1 + 3x2 + 2x3 + x4
restricciones
x1 – x 2 5
x2 – x 3 2
x2 – 2x3 + x4 4
x1, x2, x3, x4 ≥ 0
