Universidad de Concepción

FACULTAD DE INGENIERÍA
DEPARTAMENTO DE INGENIERÍA INDUSTRIAL

Listado 4 - Optimización I (580315)

Teorı́a de Programación Lineal y Dualidad

Ejercicio 1 (En práctica (b)). Indique qué supuesto de la programación lineal no se satisface en cada
restricción. Las variables son x1 , x2 y x3 .
1 2x1 + x2
(a) x1 + + 3x3 ≤ 2 (c) ≥1
x2 x1 + x3
(b) 6x1 + 0.6x2 x3 = 0 (d) x1 ∈ {0, 1}

Ejercicio 2. Grafique la región factible, muestre los puntos extremos y encuentre la solución óptima
(como máximo y como mı́nimo) de los siguientes problemas de acuerdo al método de evaluación de
puntos extremos:

Z = 3x1 + 2x2 Z = 40x1 − 80x2

s.a.: 2x1 + x2 ≤ 18 s.a.: 2x1 + x2 ≤ 1200
(a) 2x1 + 3x2 ≤ 42 (c) 3x1 + 4x2 ≤ 2400
3x1 + x2 ≤ 24 x1 + x2 ≥ 800
x1 , x 2 ≥ 0 x1 , x 2 ≥ 0

Z = 300x1 + 100x2 Z = 6x1 + 9x2

s.a.: 40x1 + 8x2 ≤ 800 s.a.: −3x1 + 2x2 ≤ 6
(b) 10x1 + 5x2 ≥ 320 (d) −x1 + 7x2 ≤ 14
3x1 + 3x2 ≤ 240 3x1 + x2 ≥ 9
x2 ≤ 60 x1 , x 2 ≥ 0

Ejercicio 3. Un comercio dispone de 60 unidades de un producto A que al venderlo obtiene $250.

También dispone de 70 unidades de producto B, que al venderlo obtiene $300. El comercio puede vender
máximo 100 unidades de sus productos. Elaborar un modelo de programación lineal, graficar, decidir si
la región factible es acotada o no acotada, dar un punto extremo, interior y además de dar la solución
óptima.

Ejercicio 4. La compañı́a WorldLight produce dos dispositivos para lámparas (productos 1 y 2) que
requieren partes de metal y componentes eléctricos. La administración desea determinar cuántas unidades
de cada producto debe fabricar para maximizar la ganancia. Por cada unidad del producto 1 se requieren
1 unidad de partes de metal y 2 unidades de componentes eléctricos. Por cada unidad del producto 2
se necesitan 3 unidades de partes de metal y 2 unidades de componentes eléctricos. La compañı́a tiene
300 unidades de partes de metal y 400 de componentes eléctricos. Cada unidad del producto 1 da una
ganancia de $1 y cada unidad del producto 2, hasta 75 unidades, da una ganancia de $2. Cualquier exceso
de 75 unidades del producto 2 no genera ganancia, por lo que fabricar más de esa cantidad está fuera de
consideración.

1. Formule un modelo de programación lineal, explicando brevemente cada variable de decisión definida,
la función objetivo y cada restricción.

2. Utilice el método de evaluación de puntos extremos para resolver este modelo. ¿Cuál es la ganancia
total que resulta?

1
Ejercicio 5 (En práctica). Una siderúrgica debe decidir cómo asignar para la próxima semana, el
tiempo de una fresadora, que es una máquina que toma planchones no terminados de acero como entrada
y produce alguno de los dos siguientes productos semi-terminados: bandas y alambrón. La fresadora tiene
los siguinetes rendimientos para cada producto:
Bandas 200 ton/h
Alambrón 140 ton/h.

Éstos producen también diferentes utilidades:

Bandas $25/ton
Alambrón $30/ton.
Basados en las recientes órdenes de compra, las siguientes cotas superiores establecen la cantidad de
producto a producir:
Bandas 6000 ton
Alambrón 4000 ton.
Para esta semana se dispone de 40h de producción. Ası́, el problema consiste en decidir cuántas toneladas
de bandas y cuántas toneladas de alambrón se debe producir para obtener el mayor beneficio posible.
Formular este problema como un problema de programación lineal, y resolver por el método de evaluación
de puntos extremos.

Ejercicio 6. Una empresa vitivinı́cola ha adquirido recientemente un terreno de 110 hectáreas. Debido a
la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon
Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos,
beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

Variedad Costo (USD/Hect) Beneficio Neto (USD/Hect) Dı́as Hombre/ Hect

Sauvignon Blanc 100 50 10
Chardonay 200 120 30

Suponga que se posee un presupuesto de 10.000 USD y una disponibilidad de 1.200 dı́as hombre durante
el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para
este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para
encontrar la solución óptima y valor óptimo.

Ejercicio 7. Un taller tiene tres (3) tipos de máquinas: A, B y C. El taller puede fabricar dos (2)
productos: 1 y 2. Todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden:
Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

ˆ Las horas requeridas en cada máquina, por unidad de producto

ˆ Las horas totales disponibles para cada máquina, por semana

ˆ La ganancia por unidad vendida de cada producto

Tipo de Máquina Producto 1 Producto 2 Horas disponibles

por semana
A 2 2 16
B 1 2 12
C 4 2 28
Ganancia por 1 1.50
unidad

2
Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación
anterior que permite obtener la máxima ganancia para el taller.

Ejercicio 8. Una compañı́a elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de
hora en labores de armado, 1/8 de hora en labores de control de calidad y 1.2 USD en materias primas.
El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control
de calidad y 0.9 USD en materias primas. Dada las actuales disponibilidades de personal en la compañı́a,
existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada dı́a. El primer
producto descrito tiene un valor de mercado (precio de venta) de 9 USD por unidad y para el segundo este
valor corresponde a 8 USD por unidad. Adicionalmente se ha estimado que el lı́mite máximo de ventas
diarias para el primer producto descrito es de 200 unidades, no existiendo un lı́mite máximo de ventas
diarias para el segundo producto.
Formule y resuelva gráficamente por evaluación de puntos extremos un modelo de Programación Lineal
que permita maximizar las utilidades de la compañı́a.

Ejercicio 9 (En práctica). El siguiente problema de programación lineal no está escrito en forma
canónica: 

 max ct1 x1 + ct2 x2 + ct3 x3
 s.a.: A11 x1 + A12 x2 + A13 x3 ≤ b1



A21 x1 + A22 x2 + A23 x3 ≥ b2




 A31 x1 + A32 x2 + A33 x3 = b3
x1 ≥ 0, x2 ≤ 0, x3 irrestricta


donde cj y bi son vectores columna de parámetros, Aij son matrices de parámetros y xj son vectores
columna de variables de decisión. De forma algebraica, obtenga el dual de este problema, para demostrar
que los problemas primales y duales siguen las reglas establecidas en la siguiente tabla:

PROB. MIN. PROB. MAX.

Variables

≥0 ←→ ≤
Restricc.

≤0 ←→ ≥
irrestricta ←→ =
≥ ←→ ≥0
Restricc.

Variables

≤ ←→ ≤0
= ←→ irrestricta

Ejercicio 10. Decida si las siguientes afirmaciones son verdaderas o falsas. En ambos casos, justifique
su respuesta.

(a) El dual del problema dual da por resultado el primal original.

(b) Si la restricción primal está originalmente en forma de ecuación, la variable dual correspondiente no
necesariamente es irrestricta.

(c) Si la restricción primal es del tipo ≤ la variable dual correspondiente será no negativa si la función
objetivo primal es de maximización.

(d) Si la restricción primal es del tipo capacidad (presupuesto, horas máqina/hombre/Recursos, etc. . . )
la variable dual correspondiente será no negativa si la función primal es de minimización.

(e) Una variable primal irrestricta producirá una restricción dual de igualdad.

3
Ejercicio 11 (En práctica (d)). Escriba el dual de los siguientes problemas de programación lineal:
 

 max −2x1 − x3 
 min 315x1 + 110x2 + 50x3

 s.a.: −x − x + x ≤ −5 15x1 + 2x2 + x3 ≥ 200

1 2 3

 s.a.:
(a) 

 −x1 + 2x2 − 4x3 ≤ −8 (c) 7.5x1 + 2x2 + x3 ≥ 150
 
x1 , x2 , x3 ≥ 0 5x1 + 2x2 + x3 ≥ 120
 



x1 , x2 , x3 ≥ 0




 min −5x1 + 12x2 + 4x3 − 6x4

min 2x1 + x2 − 3x3 s.a.: 8x1 + 2x2 − x3 + 4x4 ≤ 2



 


x1 − 2x2 − x3 ≥ 4 x1 − 2x2 − 2x3 + x4 ≤ −2


 s.a.: 
 (d)
(b) 2x1 + x2 − x3 ≤ 8 
 2x1 − x2 + 2x4 ≥ 3
 
−x1 − x3 ≤ 0 4x1 − 2x2 − x3 = 2

 


 

x1 , x2 ≥ 0, x3 ≤ 0 x1 , x2 ≤ 0, x3 , x4 ≥ 0
 

Ejercicio 12. Encontrar el dual del problema siguiente, reduciéndolo a la mı́nima expresión:


 max r


 Xm

 s.a.: yi = 1
i=1
At y ≥ 1r






 y ≥ 0, r irrestricto

Aquı́, A ∈ Rm×n y 1 = (1, 1, . . . , 1)t ∈ Rn es un vector columna con todas sus componentes iguales a 1.

CCB/RMD/MVH/MBS/JBL/mvh Semestre 2024-1