320 Capítulo 7 Programación lineal que tiene la forma apropiada. De esta manera, la tabla simplex inicial es la tabla
Views 22 Downloads 0 File size 592KB
320
Capítulo 7 Programación lineal
que tiene la forma apropiada. De esta manera, la tabla simplex inicial es la tabla I: TABLA SIMPLEX I variable entrante ↓ B x1 x2 x3 s1 s2 Z variable ← s1 1 2 0 1 0 0 saliente 2 1 0 1 0 s2 2 Z −3 −4 − 23 0 0 1 indicadores
Cocientes R 10 10 ÷ 2 = 5 10 10 ÷ 2 = 5 0
La variable entrante es x2. Como existe empate para el cociente más pequeño, puede seleccionarse a s1 o a s2 como la variable saliente. Se elige s1. La entrada pivote aparece sombreada. Al aplicar operaciones elementales con renglones se obtiene la tabla II: TABLA SIMPLEX II variable entrante ↓ B x1 x2 x3 s1 s2 Z 1 1 x2 1 0 0 0 2 2 1 −1 1 0 variable ← s2 1 0 saliente Z −1 0 − 23 2 0 1
Cocientes R no hay cociente porque 0 > 0 5 0 0 ÷1 = 0
20
indicadores
La tabla II corresponde a una solución básica factible, en la que una variable básica, s2, es cero. Por lo tanto, la SBF es degenerada. Como existen indicadores negativos, continuamos. La variable que entra ahora es x3, la variable que sale es s2 y el pivote aparece sombreado. Al aplicar operaciones elementales con renglones se obtiene la tabla III: TABLA SIMPLEX III B x1 x2 21 x3 1 Z 21
x2 1
x3 0
s1
s2 0
Z 0
0
1
−1
1
0
3 2
1
0
0
1 2 1 2
indicadores
R 5 0 20
Como todos los indicadores son no negativos, Z es máxima cuando x2 = 5, x3 = 0 y x1 = s1 = s2 = 0. El valor máximo es Z = 20. Observe que este valor es el mismo que el correspondiente de Z en la tabla II. En problemas degenerados, es posible llegar al mismo valor de Z en varias etapas del método simplex. En el problema 7, se le pedirá que lo resuelva utilizando a s2 como la variable que sale en la tabla inicial. Ahora resuelva el problema 7 v Debido a su naturaleza mecánica, el método simplex se adapta con facilidad a computadoras para resolver problemas de programación lineal que incluyan muchas variables y restricciones.
PROBLEMAS 7.4 Utilice el método simplex para resolver los problemas siguientes. 1. Maximizar
sujeta a
2 x1 + x 2 ≤ 8 2x1 + 3x2 ≤ 12
Z = x1 + 2x2
x1 , x2 ≥ 0
Sección 7.4
sujeta a
2. Maximizar sujeta a
x1 + x2 ≤ 6
sujeta a
x1 + x2 ≤ 1
Z = 2x1 + x2 −x1 + x2 ≤ 4
3. Maximizar
x1 , x2 ≥ 0
x1 − 2x2 − x3 ≥ −2 x1 , x2 , x3 ≥ 0
10. Maximizar
Z = −5x1 + 2x2 sujeta a
x1 + x 2 ≤ 2
Z = −x1 + 2x2
x1 − x2 ≤ 3
x1 − x2 ≥ −3
3x 1 + 2 x 2 ≤ 5
x1 ≤ 4
−x1 + 3x2 ≤ 3 4. Maximizar sujeta a
x1 , x2 ≥ 0
Z = 4x1 + 7x2
x1 , x2 ≥ 0 11. Maximizar
Z = x1 + x2 sujeta a 2x1 − x2 ≤ 4
2x1 + 3x2 ≤ 9
−x1 + 2x2 ≤ 6
x1 + 5x2 ≤ 10
5. Maximizar sujeta a
5x1 + 3x2 ≤ 20
x1 , x2 ≥ 0
2x1 + x2 ≤ 10
Z = 2x1 + x2
x1 , x2 ≥ 0
12. Maximizar
x1 − x 2 ≤ 1
5x1 + 4x2 ≤ 20
W = 2x1 + x2 − 2x3 sujeta a
x1 + 2x2 ≤ 8
6. Maximizar sujeta a
−2x1 + x2 + x3 ≥ −2
x1 , x2 ≥ 0
x1 − x2 + x3 ≤ 4
x1 + x2 + 2x3 ≤ 6
Z = 2x1 − 6x2
x1 , x2 , x3 ≥ 0
13. Maximizar
x1 − x 2 ≤ 4
−x1 + x2 ≤ 4
W = x1 − 12x2 + 4x3 sujeta a
x1 + x2 ≤ 6
4x1 + 3x2 − x3 ≤ 1
x1 , x2 ≥ 0
x1 + x2 − x3 ≥ −2
7. Resuelva el problema del ejemplo 2 seleccionando a s2 como la variable saliente en la tabla I. 8. Maximizar sujeta a
Z = 2x1 − x2 + x3 2x1 + x2 − x3 ≤ 4
x1 + x2 + x3 ≤ 2
9. Maximizar
Método simplex
x1 , x2 , x3 ≥ 0
Z = 2x1 + x2 − x3
−x1 + x2 + x3 ≥ −1
x1 , x2 , x3 ≥ 0
14. Maximizar
W = 4x1 + 0x2 − x3 sujeta a
x 1 + x2 + x3 ≤ 6
x1 − x2 + x3 ≤ 10 x1 − x2 − x3 ≤ 4 x1 , x2 , x3 ≥ 0
321
322
Capítulo 7 Programación lineal
15. Maximizar
sujeta a
18. Producción Una compañía fabrica tres productos X, Y y Z. Cada producto requiere tiempo de máquina y tiempo de acabado como se muestra en la tabla siguiente:
Z = 50x1 + 0x2 + 80x3 + 0x4 x1 − x3 ≤ 2
Tiempo de máquina Tiempo de acabado
x1 + x4 ≤ 3
x2 + x3 ≤ 2
X
1 hr
4 hr
Y
2 hr
4 hr
Z
3 hr
8 hr
x3 − x4 ≤ 4
16. Maximizar
sujeta a
x1 , x2 , x3 , x4 ≥ 0
El número de horas de tiempo de máquina y el tiempo de acabado disponibles por mes son 900 y 5000, respectivamente. La utilidad unitaria sobre X, Y y Z es de $6, $8 y $12, respectivamente. ¿Cuál es la utilidad máxima por mes que puede obtenerse? 19. Producción Una compañía fabrica tres tipos de muebles para patio: sillas, mecedoras y sillones. Cada tipo requiere madera, plástico y aluminio como se muestra en la tabla siguiente:
Z = 3x1 + 2x2 − 2x3 − x4 x1 + x3 − x4 ≤ 3
x 1 − x2 + x4 ≤ 6
x1 + x 2 − x 3 + x 4 ≤ 5 x1 , x2 , x3 , x4 ≥ 0
17. Envíos de carga Una compañía de fletes maneja los envíos de dos corporaciones, A y B, que están ubicadas en la misma ciudad. La corporación A envía cajas que pesan 3 lb cada una y tienen un volumen de 2 pies3; B envía cajas de 1 pie3 que pesan 5 lb cada una. Ambas corporaciones envían al mismo destino. El costo de transporte para cada caja de A es de $0.75 y para B es de $0.50. La compañía de fletes tiene un camión con capacidad volumétrica de 2400 pies3 y capacidad máxima de carga de 36 800 lb. En un acarreo, ¿cuántas cajas desde cada corporación debe transportar este camión de modo que el ingreso de la compañía de fletes sea máximo? ¿Cuál es el ingreso máximo?
Objetivo Considerar el método simplex en relación con la degeneración, las soluciones no acotadas y las soluciones óptimas múltiples.
Madera
Plástico
Aluminio
Silla
1 unidad
1 unidad
2 unidades
Mecedora
1 unidad
1 unidad
3 unidades
Sillón
1 unidad
2 unidades
5 unidades
La compañía tiene disponibles 400 unidades de madera, 500 de plástico y 1450 de aluminio. Cada silla, mecedora y sillón se venden en $21, $24 y $36, respectivamente. Suponiendo que todos los muebles pueden venderse, determine la producción necesaria para que el ingreso total sea máximo. ¿Cuál es el ingreso máximo?
7.5 Degeneración, soluciones no acotadas y soluciones múltiples4 Degeneración En la sección anterior se estableció que una solución básica factible se denomina degenerada si, además de contener las de las variables no básicas, una de las variables básicas es 0. Suponga que en una solución básica factible degenerada, x1, x2, x3 y x4 son las variables, donde x1 y x2 son básicas con x1 = 0, x3 y x4 son no básicas y x3 es la variable entrante. La tabla simplex correspondiente tiene la forma
B x1 variable ← x1 1 saliente x2 0
Z
4
Esta sección puede omitirse.
0
variable entrante ↓ x2 x3 x4 0 a13 a14 1 a23 a24
Z 0 0
d1
1
0
d2
indicadores
R 0 0 ÷ a13 = 0 a
d3