• Author / Uploaded
• Kendall

Citation preview

Dual

Sección 7.8

14. Compra de piezas Un fabricante de automóviles compra alternadores de dos proveedores, X y Y. El fabricante tiene dos plantas, A y B, y requiere exactamente de 7000 alternadores para la planta A y de exactamente 5000 para la planta B. El proveedor X cobra $300 y $320 por los alternadores (incluyendo costos de transporte) A y B, respectivamente. Para estos precios, X requiere que el fabricante de automóviles ordene al menos un total de 3000 unidades; sin embargo, X no puede proveer más de 5000 unidades. El proveedor Y cobra $340 y $280 por cada alternador, A y B, respectivamente, y requiere una orden mínima de 7000 piezas. Determine cómo debe hacer los pedidos de alternadores el fabricante de automóviles para que su costo total sea mínimo. ¿Cuál es el costo mínimo?

utilizarse en este pedido, es el recorte que se desperdicia de este rollo. 48"

15"

15"

15"

3"

FIGURA 7.23

De igual modo, a partir de un rollo de almacenamiento se pueden cortar dos rollos de 15 pulgadas de ancho, un rollo de 10 pulgadas de ancho y otro de 8 pulgadas de ancho. En este caso, el desperdicio sería de 8 pulgadas. La tabla siguiente indica el número de rollos de 15 y 10 pulgadas, junto con el desperdicio, que pueden cortarse a partir de un rollo de almacenamiento: Ancho del rollo

15 pulg 10 pulg

Desperdicio

15. Producción de papel para envoltura Una compañía de papel almacena su papel para envoltura en rollos de 48 pulgadas de ancho, llamados rollos de almacenamiento, y los corta en anchos más pequeños dependiendo de los pedidos de los clientes. Suponga que se recibe un pedido de 50 rollos de papel de 15 pulgadas de ancho y de 60 rollos de 10 pulgadas de ancho. A partir de un rollo de almacenamiento, la compañía puede cortar tres rollos de 15 pulgadas de ancho y un rollo de 3 pulgadas de ancho. (Vea la figura 7.23). Como el rollo de 3 pulgadas de ancho no puede

343

3 0

2 1

1 —

— —

3

8

—

—

(a) Complete las últimas dos columnas de la tabla. (b) Suponga que la compañía tiene suficientes rollos de almacenamiento para cubrir la orden y que al menos 50 rollos de 15 pulgadas de ancho y al menos 60 rollos de 10 pulgadas de ancho de papel para envoltura serán cortados. Si x1, x2, x3 y x4 son los números de rollos de almacenamiento que se cortan en una de las formas descritas en las columnas 1 a 4 de la tabla, respectivamente, determine los valores de las x en tal forma que se minimice el desperdicio total. (c) ¿Cuál es la cantidad mínima de desperdicio total?

Objetivo

7.8 Dual

Presentar de manera informal y luego definir formalmente el dual de un problema de programación lineal.

Existe un principio fundamental, llamado dualidad, que permite resolver un problema de maximización al resolver un problema de minimización relacionado. A continuación, se ilustrará esto. Tabla 7.2 Máquina A

Máquina B

Utilidad por unidad

Manual

1h

1h

$10

Eléctrico

2h

4h

$24

Horas disponibles

120

180

Suponga que una compañía fabrica dos tipos de podadoras para jardín, manuales y eléctricas, y cada una requiere el uso de las máquinas A y B para su producción. En la tabla 7.2 se indica que una podadora manual requiere del uso de A durante 1 hora y de B durante otra hora. Las podadoras eléctricas requieren de A durante 2 horas y de B durante 4 horas. Los números máximos de horas disponibles por mes para las máquinas A y B son de 120 y 180, respectivamente. La utilidad por una podadora manual es de $10 y por una eléctrica es de $24. Suponiendo que la compañía puede vender todas las podadoras que produce, determine la utilidad mensual máxima. Si x1 y x2 son los números de podadoras manuales y eléctricas que se producen por mes, respectivamente, entonces se desea maximizar la función de utilidad mensual P = 10x1 + 24x2 sujeta a x1 + 2x2 ≤ 120 (1) x1 + 4x2 ≤ 180 x1 , x2 ≥ 0

(2)

344

Capítulo 7

Programación lineal

Al escribir las restricciones (1) y (2) como ecuaciones, se tiene (3)

x1 + 2x2 + s1 = 120 y x1 + 4x2 + s2 = 180

donde s1 y s2 son variables de holgura. En la ecuación (3), x1 + 2x2 es el número de horas que utiliza la máquina A. Como hay disponibles 120 horas para A, entonces s1 es el número de horas disponibles que no se utilizan para la producción. Esto es, s1 representa para A la capacidad no usada (en horas). De igual modo, s2 representa la capacidad no utilizada para B. Al resolver este problema por el método simplex, se encuentra que la tabla final es: B x1  x1 1 x2  0 P

0

x2 0 1

s1 2 − 21

s2 −1 1 2

P 0 0

0

8

2

1

R  60 30  

(4)

1320

indicadores

Así, la utilidad máxima mensual es de $1320 y ocurre cuando x1 = 60 y x2 = 30. Ahora, se verá la situación desde un punto de vista diferente. Suponga que la compañía desea rentar sus máquinas A y B. ¿Cuál es la renta mensual mínima que debe cobrar? Ciertamente, si el cobro es muy alto, nadie le rentará las máquinas. Por otra parte, si el cobro es muy bajo, no le convendría rentarlas todo el tiempo. Es obvio que la renta mínima debe ser de $1320. Esto es, el mínimo que la compañía debe cobrar es la utilidad que podría tener utilizando ella misma las máquinas. Podemos llegar a este costo de renta mínimo de manera directa, resolviendo un problema de programación lineal. Sea F el costo de la renta mensual. Para determinar F, se supone que la compañía asigna valores monetarios a cada hora de capacidad ocupada en las máquinas A y B. Sean estos valores y1 y y2, respectivamente, donde y1, y2 ≥ 0. Entonces, el valor mensual de la máquina A es 120y1 y el de la máquina B es 180y2. Por lo tanto, F = 120y1 + 180y2

El valor total del tiempo de máquina para producir una serie de podadoras manuales es 1y1 + 1y2. Esto debe ser al menos igual a los $10 de utilidad que la compañía puede recibir por producir dichas podadoras. Si no, la compañía podría ganar más dinero utilizando el tiempo de la máquina para producir una serie de podadoras manuales. De acuerdo con esto, 1y1 + 1y2 ≥ 10

De igual modo, el valor total del tiempo de máquina para producir una podadora eléctrica debe ser al menos de $24: Por lo tanto, la compañía desea sujeta a

2y1 + 4y2 ≥ 24

minimizar F = 120y1 + 180y2 y1 + y2 ≥ 10

2y1 + 4y2 ≥ 24

(5) (6)

y1 , y2 ≥ 0

Para minimizar F, se maximiza −F. Como las restricciones (5) y (6) tienen la forma a1y1 + a2y2 ≥ b, donde b ≥ 0, se considerará un problema artificial. Si r1 y r2 son variables de excedencia t1 y t2 son variables artificiales, entonces se quiere maximizar W = (−F) − Mt1 − Mt2

Sección 7.8

Dual

345

donde M es un número positivo grande, tal que y1 + y2 − r1 + t1 = 10 2y1 + 4y2 − r2 + t2 = 24

y las y, r y t son no negativas. La tabla simplex final para este problema (con las columnas de las variables artificiales eliminadas y W cambiada a −F) es: B y1  y1 1  y2  0  −F 0

y2 0 1 0

r1 −2

1

60

r2

1 2 − 21

30

−F 0

R 8



 2  −1320

0 1

indicadores

Como el valor máximo de −F es −1320, el valor mínimo de F es −(−1320) = $1320 (como se anticipó). Esto ocurre cuando y1 = 8 y y2 = 2. Por lo tanto, se ha determinado el valor óptimo de un problema de programación lineal (maximización de utilidad) encontrando el valor óptimo de otro problema de programación lineal (minimización del costo de la renta). Los valores y1 = 8 y y2 = 2 podrían haberse anticipado a partir de la tabla final del problema de maximización. En (4), el indicador 8 de la columna s1 significa que en el nivel óptimo de producción, si s1 aumenta una unidad, entonces la utilidad P disminuye en 8. Esto es, 1 hora de capacidad sin uso de A disminuye la utilidad máxima en $8. Entonces, 1 hora de capacidad de A tiene un valor monetario de $8. Se dice que el precio sombra de 1 hora de capacidad de A es de $8. Ahora, recuerde que en el problema de la renta y1 es el valor de 1 hora de capacidad de A. Así, y1 debe ser igual a 8 en la solución óptima para ese problema. De manera similar, como en la columna s2 el indicador es 2, el precio sombra de 1 hora de capacidad de B es de $2, el cual es el valor de y2 en la solución óptima del problema de la renta. Ahora se analizará la estructura de los dos problemas de programación lineal: Minimizar

Maximizar

F = 120y1 + 180y2

P = 10x1 + 24x2

sujeta a

x1 + 2x2 ≤ 120 x1 + 4x2 ≤ 180

y x1 , x2 ≥ 0.

sujeta a (7)

y1 + y2 ≥ 10 2y1 + 4y2 ≥ 24

(8)

y y1 , y2 ≥ 0.

Observe que en (7) las desigualdades son todas ≤, pero en (8) son todas ≥. En el problema de minimización, los coeficientes de la función objetivo son los términos constantes en (7). Los términos constantes en (8) son los coeficientes de la función objetivo del problema de maximización. Los coeficientes de las y1 en (8) son los coeficientes de x1 y x2 en la primera restricción de (7); los coeficientes de las y2 en (8) son los coeficientes de x1 y x2 en la segunda restricción de (7). El problema de minimización es llamado el dual del problema de maximización y viceversa. En general, es posible asociar cualquier problema dado de programación lineal con otro problema de programación lineal llamado su dual. El problema dado se llama primal. Si el primal es un problema de maximización, entonces su dual es un problema de minimización. De manera similar, si el problema primal implica minimización, su dual implica maximización. Cualquier problema primal de maximización puede escribirse en la forma indicada en la tabla 7.3. Observe que no existen restricciones sobre las b.6 El correspondiente problema Si una restricción de desigualdad incluye ≥, al multiplicar ambos lados por −1 se obtiene una desigualdad que incluye ≤. Si una restricción es una igualdad, puede reescribirse en términos de dos desigualdades: una que involucre ≤ y otra que involucre ≥. 6

346

Capítulo 7

Programación lineal

dual de minimización puede escribirse en la forma indicada en la tabla 7.4. De manera similar, cualquier problema primal de minimización puede escribirse en la forma de la tabla 7.4 y su dual es el problema de maximización que se da en la tabla 7.3. Tabla 7.3 Primal (dual) Maximizar Z = c1 x1 + c2 x2 + · · · + cn xn sujeta a a11 x1 + a12 x2 + · · · + a1n xn a21 x1 + a22 x2 + · · · + a2n xn · · · · · · · · · am1 x1 + am2 x2 + · · · + amn xn

y x1 , x2 , . . . , xn ≥ 0

 ≤ b1    ≤ b2     · ·     ·    ≤ bm

(9)

Tabla 7.4 Dual (primal) Minimizar W = b1 y1 + b2 y2 + · · · + bm ym sujeta a a11 y1 + a21 y2 + · · · + am1 ym a12 y1 + a22 y2 + · · · + am2 ym · · · · · · · · · a1n y1 + a2n y2 + · · · + amn ym y y1 , y2 , . . . , ym ≥ 0

 ≥ c1    ≥ c2     · ·     ·    ≥ cn

(10)

Ahora se comparará el primal y su dual en las tablas 7.3 y 7.4. Por conveniencia, cuando aquí se habla de restricciones, se hace referencia a aquéllas mostradas en (9) o (10); no se incluirán las condiciones de no negatividad. Observe que si todas las restricciones del problema primal involucran ≤ (≥), entonces todas las restricciones en su dual involucran ≥ (≤). En la función objetivo del dual, los coeficientes son los términos constantes de las restricciones del primal. De manera similar, los términos constantes en las restricciones del dual son los coeficientes de la función objetivo del primal. La matriz de coeficientes de los lados izquierdos de las restricciones del dual es la transpuesta de la matriz de coeficientes de los lados izquierdos de las restricciones del primal. Esto es, 

a11  a21   ·  ·   · am1

a12 a22 · · · am2

··· ···

···

T  a11 a1n a12 a2n    ·   ·  = ·   ·  · ·  amn a1n

a21 a22 · · · a2n

··· ···

···

 am1 am2   ·   ·  ·  amn

Si el primal involucra n variables de decisión y m variables de holgura, entonces el dual involucra m variables de decisión y n variables de holgura. Debe observarse que el dual del dual es el primal. Existe una relación importante entre el primal y el dual: Si el primal tiene una solución óptima, también la tiene el dual, y el valor óptimo de la función objetivo del primal es el mismo valor óptimo que el del dual. Además, suponga que la función objetivo del primal es Z = c1x1 + c2x2 + ∙ ∙ ∙ + cnxn

Sección 7.8

Dual

347

Entonces, si s1 es la variable de holgura asociada con la i-ésima restricción del dual, entonces el indicador de la columna si de la tabla simplex final del dual es el valor de xi en la solución óptima del primal. Por eso es que puede resolverse el problema primal con sólo resolver el dual. En ocasiones, esto es más conveniente que resolver de manera directa el primal. El vínculo entre el primal y el dual puede expresarse en forma muy sucinta usando notación matricial. Sean   x1  x2     ·  y X=  C = c1 c2 · · · cn  ·   ·  xn

Entonces la función objetivo del problema primal puede escribirse como Z = CX

Además, si se escribe 

a11  a21   · A=  ·  · am1

a12 a22 · · · am2

··· ···

···

 a1n a2n   ·   ·  ·  amn

y



 b1  b2     ·  B=   ·   ·  bm

entonces el sistema de restricciones para el problema primal se transforma en AX ≤ B

AP LÍ Q U E LO u 7. Encuentre el dual del problema siguiente: suponga que una compañía tiene $60 000 para comprar materiales y fabricar tres tipos de dispositivos. La compañía tiene asignadas un total de 2000 horas para tiempo de ensamblado y 120 horas para empacar los dispositivos. La tabla siguiente proporciona los costos, el número de horas y la utilidad por dispositivo de cada tipo: Tipo 1 Tipo 2 Tipo 3 Costo por $300 dispositivo Horas de 20 ensamblado por dispositivo Horas de 3 empacado por dispositivo Utilidad $300

$220

$180

40

20

$200

El problema dual tiene una función objetivo dada por, y su sistema de restricciones es:

W = BTY ATY ≥ CT y

EJEMPLO 1

Y≥0

Determinación del dual de un problema de maximización

Encuentre el dual de: Maximizar Z = 3x1 + 4x2 + 2x3 x1 + 2x2 + 0x3 ≤ 10

2

$200

X≥0

donde se entiende que ≤ (≥), entre matrices del mismo tamaño, significa que la desigualdad abarca cada par de entradas correspondientes. Ahora sea   y1  y2     ·  Y =   ·   ·  ym

sujeta a 1

y

y x1, x2, x3 ≥ 0.

2x1 + 2x2 + x3 ≤ 10

348

Capítulo 7

Programación lineal

Solución: El primal tiene la forma de la tabla 7.3. Así, el dual es

minimizar W = 10y1 + 10y2

sujeta a

y1 + 2y2 ≥ 3

2y1 + 2y2 ≥ 4

0y1 + y2 ≥ 2

y y1, y2 ≥ 0. APL Í Q U E LO u 8. Encuentre el dual del siguiente problema: una persona decide tomar dos diferentes suplementos dietéticos. Cada suplemento contiene dos ingredientes esenciales, A y B, para los cuales existen requerimientos mínimos diarios y cada uno contiene un tercer ingrediente, C, que debe minimizarse.

EJEMPLO 2

Ahora resuelva el problema 1 v Determinación del dual de un problema de minimización

Encuentre el dual de la siguiente función: Minimizar Z = 4x1 + 3x2

sujeta a

3x1 − x2 ≥ 2 x1 + x 2 ≤ 1

Suplemento Suplemento Requerimiento 1 2 diario A B C

20 mg/oz 8 mg/oz 6 mg/oz

6 mg/oz 16 mg/oz 2 mg/oz

−4x1 + x2 ≤ 3

y x1, x2 ≥ 0.

98 mg 80 mg

(11) (12) (13)

Solución: Como el primal es un problema de minimización, se desea que las restricciones

(12) y (13) involucren ≥. (Vea la tabla 7.4). Multiplicando ambos lados de (12) y (13) por −1, se obtiene −x1 − x2 ≥ −1 y 4x1 −x2 ≥ −3. De este modo, las restricciones (11) a la (13) se convierten en 3x1 − x2 ≥ 2 −x1 − x2 ≥ −1 4x1 − x2 ≥ −3

El dual es APL Í Q U E LO u 9. Una compañía produce tres clases de dispositivos que requieren tres diferentes procesos de producción. La compañía ha destinado un total de 300 horas al proceso 1, 400 horas al proceso 2 y 600 horas al proceso 3. La tabla siguiente da el número de horas por dispositivo para cada proceso: Disp. 1

Disp. 2

Disp. 3

Proceso 1

30

15

10

Proceso 2

20

30

20

Proceso 3

40

30

25

Si la utilidad es de $30 por el dispositivo 1, de $20 por el dispositivo 2 y de $20 por el dispositivo 3, use el dual y el método simplex para determinar el número de dispositivos de cada clase que la compañía debe producir con el fin de maximizar la utilidad.

maximizar W = 2y1 − y2 + 3y3

sujeta a

3y1 − y2 + 4y3 ≤ 4

−y1 − y2 − y3 ≤ 3

y y1, y2, y3 ≥ 0. EJEMPLO 3

Ahora resuelva el problema 3 v Aplicación del método simplex al dual

Utilice el dual y el método simplex para sujeta a

y x1, x2, x3 ≥ 0.

maximizar Z = 4x1 − x2 − x3 3x1 + x2 − x3 ≤ 4 x1 + x 2 + x 3 ≤ 2

Solución: El dual es

minimizar W = 4y1 + 2y2

Sección 7.8

sujeta a

Dual

349

3y1 + y2 ≥ 4

(14)

−y1 + y2 ≥ −1

(16)

(15)

y1 + y2 ≥ −1

y y1, y2 ≥ 0. Para utilizar el método simplex se deben tener constantes no negativas en (15) y (16). Al multiplicar ambos lados de estas ecuaciones por −1, se obtiene: (17)

−y1 − y2 ≤ 1

(18)

y1 − y 2 ≤ 1

Como (14) involucra ≥, se requiere de una variable artificial. Las ecuaciones correspondientes de (14), (17) y (18) son, respectivamente, 3y1 + y2 − s1 + t1 = 4

−y1 − y2 + s2

y

=1

y1 − y2 + s3 = 1

donde t1 es una variable artificial, s1 es una variable de excedenci s2 y s3 son variables de holgura. Para minimizar W, se maximiza −W. La función objetivo artificial es U = (−W) − Mt1, donde M es un número positivo grande. Después de hacer los cálculos, encontramos que la tabla simplex final es: B y1  y2 0 s2  0  y1  1

−W

0

y2 1

s1 − 41

− 21

0

s2 0 1

s3 − 43

− 21

−W 0 0

0

− 41

0

1 4

0

0

3 2

0

1 2

1

R 1 4 5 2 5 4

− 11 2

     

indicadores

El valor máximo de −W es −11 , de modo que el valor mínimo de W es 11 . De aquí que el 2 2 valor máximo de Z sea también

s3 son

3 , 2

x2 = 0 y

0 y 21, respectivamente. x3 = 21.

11 . 2

Note que los indicadores de las columnas s1, s2 y

Por lo tanto, el valor máximo de Z ocurre cuando x1 = 23, Ahora resuelva el problema 11 v

En el ejemplo 1 de la sección 7.7 se usó el método simplex para sujeta a:

minimizar Z = x1 + 2x2 −2x1 + x2 ≥ 1 −x1 + x2 ≥ 2

Este estudio muestra la ventaja de resolver el problema dual.

y x1, x2 ≥ 0. La tabla simplex inicial tiene 24 entradas e involucra dos variables artificiales. La tabla del dual sólo tiene 18 entradas y ninguna variable artificial y es más fácil de manipular, como lo mostrará el ejemplo 4. Por lo tanto, puede ser una clara ventaja resolver el dual para determinar la solución del primal. EJEMPLO 4

Uso del dual y del método simplex

Utilice el dual y el método simplex para minimizar Z = x1 + 2x2

350

Capítulo 7

Programación lineal

sujeta a

−2x1 + x2 ≥ 1 −x1 + x2 ≥ 2

y x1, x2 ≥ 0.

Solución: El dual es

maximizar W = y1 + 2y2

sujeta a

−2y1 − y2 ≤ 1 y1 + y 2 ≤ 2

y y1, y2 ≥ 0. La tabla simplex inicial es la tabla I:

TABLA SIMPLEX I variable entrante ↓ B y1 y2 s1 s2 W  s1 −2 −1 1 0 0 1 0 1 0 variable ← s2  1 saliente W −1 −2 0 0 1 indicadores

R Cocientes  1 22÷1=2 0

Después se obtiene la tabla II. TABLA SIMPLEX II B y1 y2 s1 s2 W  s1 −1 0 1 1 0 y2  1 1 0 1 0 W 1 0 0 2 1 indicadores

R  3 2 4

Como en la tabla II todos los indicadores son no negativos, el valor máximo de W es 4. De aquí que el valor mínimo de Z sea también 4. Los indicadores 0 y 2 ubicados en las columnas s1 y s2 de la tabla II, significan que el valor mínimo de Z ocurre cuando x1 = 0 y x2 = 2. Ahora resuelva el problema 9 v

PROBLEMAS 7.8 En los problemas del 1 al 8, encuentre los duales. No los resuelva.

3. Minimizar

1. Maximizar sujeta a

Z = 2x1 + 3x2

sujeta a

x1 + x 2 + x 3 ≥ 8

3x1 − x2 ≤ 4

−x1 + 2x2 + x3 ≥ 2

2x1 + 3x2 ≤ 5 x1 , x2 ≥ 0

x1 , x2 , x3 ≥ 0

4. Minimizar

2. Maximizar sujeta a

Z = 2x1 + x2 − x3 2x1 + 2x2 ≤ 3

−x1 + 4x2 + 2x3 ≤ 5

x1 , x2 , x3 ≥ 0

Z = x1 + 8x2 + 5x3

sujeta a

Z = 8x1 + 12x2 2x1 + 2x2 ≥ 1 x1 + 3x2 ≥ 2

x1 , x2 ≥ 0

Sección 7.8

5. Maximizar sujeta a

Z = x1 − x2

Z = 5x1 + 4x2 sujeta a

−x1 + x2 ≥ 3

2x1 + 3x2 ≤ 6

x1 + x2 ≥ 11

x1 + 4x2 ≤ 10

x1 , x2 ≥ 0

Z = 2x1 + 5x2 − 2x3

x1 , x2 ≥ 0

12. Maximizar Z = 2x1 + 6x2

sujeta a 2x1 − 3x2 + x3 ≤ 7

sujeta a

3x1 − 4x2 − x3 ≥ −1

7. Minimizar

3x1 + x2 ≤ 12

x1 , x2 , x3 ≥ 0

Z = 4x1 + 4x2 + 6x3 sujeta a x1 − x 2 − x3 ≤ 3 x1 − x2 + x3 ≥ 3

8. Minimizar

x1 + x2 ≤ 8 x1 , x2 ≥ 0

13. Minimizar Z = 6x1 + 4x2 sujeta a −x1 + x2 ≤ 1

x1 , x2 , x3 ≥ 0

Z = 5x1 + 4x2 sujeta a

x1 + x2 ≥ 3 x1 , x2 ≥ 0

14. Minimizar Z = 2x1 + x2 + x3

−4x1 + 3x2 ≥ −10 8x1 − 10x2 ≤ 80

sujeta a

x1 , x2 ≥ 0

2x1 − x2 − x3 ≤ 2

En los problemas 9 a 14, resuelva utilizando los duales y el método simplex. 9. Minimizar Z = 2x1 + 2x2 + 5x3 sujeta a x1 − x2 + 2x3 ≥ 2

−x1 − x2 + 2x3 ≥ 4

x1 , x2 , x3 ≥ 0

15. Publicidad Una compañía está comparando los costos de publicidad en dos medios —periódico y radio—. La tabla siguiente muestra el número de personas, por grupo de ingresos, que alcanza cada uno de estos medios por cada unidad monetaria de publicidad.

−x1 + 2x2 + x3 ≥ 3 10. Minimizar

351

11. Maximizar

−x1 + 2x2 ≤ 13

6. Maximizar

Dual

Menos de $40 000

Más de $40 000

Periódico

40

100

Radio

50

25

x1 , x2 , x3 ≥ 0 Z = 2x1 + 2x2

sujeta a x1 + 4x2 ≥ 28 2x1 − x2 ≥ 2 −3x1 + 8x2 ≥ 16 x1 , x2 ≥ 0

La compañía quiere captar al menos 80 000 personas con ingresos menores de $40 000 y al menos 60 000 con ingresos de $40 000 o más. Utilice el dual y el método simplex para determinar las cantidades que la compañía debe gastar en publicidad en periódico y en radio de modo que capte este número de personas con un costo mínimo. ¿Cuál es el costo mínimo de publicidad?