Capítulo 1 - Modelamiento

Vista previa del material en texto

Universidad de los Andes
Facultad de Ingenieŕıa y Ciencias Aplicadas
Apuntes del Curso
Introducción a la Optimización
Índice general
1. Modelamiento en Optimización 4
1.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Problemas clásicos de modelamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. Problemas equivalentes y existencia de óptimos 28
2.1. Introducción a problemas equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2. Existencia de soluciones óptimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3. Convexidad 40
3.1. Introdución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.1. Aplicaciones de la convexidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2. Funciones convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4. Optimización sin restricciones 51
4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5. Optimización con restricciones 54
5.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6. Programación Lineal 62
6.1. Definiciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2. Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2.1. Fase I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2.2. Casos especiales del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.3. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7. Dualidad en Programación Lineal 75
7.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2
8. Programación Lineal Entera 77
8.1. Programación Entera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.1. Algoritmo “Branch & Bound” . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.2. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3
Caṕıtulo 1
Modelamiento en Optimización
1.1. Introducción
En este curso estudiaremos el problema
(P) min{f(x) | x ∈ Ω}.
donde f : ❘n → ❘ y Ω ⊆ ❘n. Diremos que x∗ ∈ Ω es solución de (P) si satisface
f(x∗) ≤ f(x)∀x ∈ Ω.
Denotaremos por v(P ) al valor óptimo del problema y argmin(P ) o bien S(P ) ⊆ ❘n al conjunto
de todas las posibles soluciones, esto es, S(P ) = {x∗ ∈ ❘n | f(x∗) = v(P )}. Por supuesto, el
problema de minimización no siempre tiene solución, por ejemplo, el problema de encontrar x ∈ ❘
que minimice la expresión ex satisface v = 0 pero S = ∅.
La función f se denomina función objetivo, llamaremos conjunto factible o de restricciones al con-
junto Ω, un punto x ∈ Ω se denomina punto factible, si el conjunto Ω es vaćıo diremos que el
problema es infactible.
Si existe una sucesión (xk)k ⊆ Ω satisfaciendo f(xk) → −∞ diremos que el problema es no acotado.
En forma análoga se define el problema de maximización:
(Q) max{f(x) | x ∈ Ω}.
Diremos que x∗ ∈ Ω es solución de (Q) si satisface
f(x∗) ≥ f(x) ∀x ∈ Ω.
Denotaremos por v(Q) al valor óptimo del problema y argmax(Q) o bien S(Q) ⊆ ❘n al conjunto
de todas las posibles soluciones, esto es, S(Q) = {x∗ ∈ ❘n | f(x∗) = v(Q)}. Si existe una sucesión
(xk)k ⊆ Ω satisfaciendo f(xk) →∞ diremos que el problema (Q) es no acotado.
Finalmente, notemos que se cumple minx∈Ω f(x) = −maxx∈Ω{−f(x)}, por lo tanto podemos foca-
lizarnos en estudiar la teoŕıa de los problemas de minimización entendiendo que cualquier resultado
obtenido tiene su análogo para maximización via el cambio en la función objetivo.
1.2. Problemas clásicos de modelamiento
Problema de Producción:
Consideramos una empresa que produce n productos y denotemos por xj la cantidad produ-
cida del producto j ∈ {1, . . . , n}, con un beneficio cj . Sea A ∈ ❘
m×n la matriz de insumos,
4
esto es, Aij denota la cantidad del insumo i ∈ {1, . . . ,m} utilizada para producir el producto
j, supondremos que la cantidad total del insumo i disponible está limitada por bi. Con esto
el problema saber la cantidad a producir obteniendo un máximo beneficio se puede formular
como el siguiente problema de optimización.
max
n
∑
j=1
cjxj
s.a
m
∑
j=1
Aijxj ≤ bi, i = 1, . . . ,m,
xj ≥ 0, j = 1, . . . ,m.
Problema de la Dieta: considere que usted posee un conjunto de n alimentos y denotemos por
xj la cantidad del alimento j a consumir en un periodo de tiempo, cj el costo unitario del
mismo para j = 1, . . . , n. Por indicación del nutricionista usted debe consumir una cantidad
mı́nima, digamos bi, del elemento nutritivo i. Sea A ∈ ❘
m×n la matriz de requerimientos
nutritivos, esto es, Aij denota la cantidad del elemento nutritivo i que posee el alimento j.
con esto el problema de encontrar la distribución de alimentos a consumir a mı́nimo costo
satisfaciendo los requerimientos nutritivos está dado por
min
n
∑
j=1
cjxj
s.a
m
∑
j=1
Aijxj ≥ bi, i = 1, . . . ,m,
xj ≥ 0, j = 1, . . . ,m.
Problema de la Mochila: considere que usted posee un conjunto de n elementos y una mochila
de capacidad máxima W. Supongamos que usted asigna a cada elemento i ∈ {1, . . . , n} un
valor vi, además, supondremos que cada elemento i posee un peso wi. Queremos encontrar
la mejor distribución de elementos que puedo poner en la mochila maximizando el valor
total y respetando las restricciones de capacidad. Denotaremos por xi la variable binaria, que
satisface xi = 1 si el elemento i está en la mochila y xi = 0 si no. El problema se formula
como
max
n
∑
i=1
vixi
s.a
n
∑
i=1
wixi ≤ W
xi ∈ {0, 1}, i = 1, . . . , n.
Problema de Asignación: suponga que usted debe asignar n empleados a n tareas. La disposi-
ción del empleado i a realizar la tarea j es vij , i, j ∈ {1, . . . , n}. Cada tarea debe ser realizada
por un empleado y cada empleado debe realizar una tarea. Considere xij = 1 si al empleado
i se le asigna la tarea j, con i, j ∈ {1, . . . , n}. El modelo de optimización que maximiza las
5
preferencias de los empleados está dado por
max
n
∑
i,j=1
vixi
s.a
n
∑
i=1
xij = 1, ∀j ∈ {1, . . . , n}
n
∑
j=1
xij = 1 ∀i ∈ {1, . . . , n}
xi ∈ {0, 1}, i = 1, . . . , n.
Problema del Vendedor Viajero: consideremos que un vendedor necesita visitar n ciudades,
los costos de transporte para ir de la ciudad i a la ciudad j corresponden a cij con i, j ∈
{1, . . . , n}, i 6= j. Cada ciudad debe ser visitada una y sólo una vez. se pide entregar la ruta
de mı́nimo costo que cumpla las restricciones mencionadas.
Denotaremos por
xij =
{
1 si el vendedor viaja de la ciudad i a la ciudad j, i 6= j.
0 si no.
en este caso la función objetivo a minimizar corresponde al costo total
∑
i6=j
cijxij
como restricciones tenemos que cada ciudad debe ser visitada sólo una vez
∀i ∈ {1, . . . , n},
∑
j 6=i
xij = 1 y ∀j ∈ {1, . . . , n},
∑
j 6=i
xij = 1.
Adicionalmente tenemos que agregar una restricción que prohiba la existencia de subciclos
∑
i∈V,j /∈V
xij ≥ 1 ∀V ⊆ {1, . . . , n}, y 2 ≤ |V | ≤ n− 1.
1.3. Problemas Resueltos
P1 La firma C&M produce y vende tres tipos diferentesde whiskies, Etiqueta Roja, Azul y Negra,
a partir de cuatro maltas conocidas en la disteleŕıa con los nombres de M3, M5, M8, M9. Las
fórmulas empleadas para producir estos whiskies se pueden resumir aśı:
Etiqueta Roja: 50 % de M3 , entre 20-25 % de M5, no más del 20 % de M8 y no más de
10 % de M9.
Etiqueta Azul: no más de 30 % de M3 , al menos un 30 % de M5, un 30% de M8 y no más
de 15 % de M9.
Etiqueta Negra: nada de M3, al menos un 30 % de M5, no más de un 10% de M8 y no
más de 25% de M9.
6
Los suministros de maltas M3, M5, M8 y M9 están limitados a 10.000, 12.500, 15.000 y 15.000
litros, y su costo de producción por litro es 6, 50$, 6, 00$, 5, 25$ y 4, 50$ respectivamente. Los
whiskies C&M Etiqueta Roja, Azul y Negra se venden a los mayoristas a 8$, 6, 50$, y 6$ por
litro, sin impuesto, y la fábrica puede vender todo lo que produce.
Modele el problema anterior como un programa de optimización con restricciones que permita
determinar el tipo de mezclas a utilizar y el nivel de producción, de manera que se obtenga la
mayor utilidad posible. Especifique claramente, variables de decisión, restricciones, naturaleza
de las variables y función objetivo
Solución:
Variables de decisión :
xij : Cantidad de litros de Malta i (i = 3,5,8,9), utilizados en la producción del whiskey j.
Restricciones:
• Suministros de Malta:
x31 + x32 + x33 ≤ 10000 x51 + x52 + x53 ≤ 12500
x81 + x82 + x83 ≤ 15000 x91 + x92 + x93 ≤ 15000
• Formulas para producir whiskey:
Etiqueta Roja:
x31 = 0,5(x31 + x51 + x81 + x91) x51 ≥ 0,2(x31 + x51 + x81 + x91)
x51 ≤ 0,25(x31 + x51 + x81 + x91) x81 ≤ 0,2(x31 + x51 + x81 + x91)
x91 ≤ 0,1(x31 + x51 + x81 + x91)
Etiqueta Azul:
x32 ≤ 0,3
∑
i=3,5,8,9
xi2 x52 ≥ 0,3
∑
i=3,5,8,9
xi2
x82 = 0,3
∑
i=3,5,8,9
xi2 x92 ≤ 0,15
∑
i=3,5,8,9
xi2
Etiqueta Negra:
x33 = 0 x53 ≥ 0,3
∑
i=3,5,8,9
xi3
x83 ≤ 0,1
∑
i=3,5,8,9
xi3 x93 ≤ 0,25
∑
i=3,5,8,9
xi3
• Restricción de positividad:
xij ≥ 0,∀i, j.
Función objetivo:
Costos totales:
6,5(x31 + x32 + x33) + 6(x51 + x52 + x53) + 5,25(x81 + x82 + x83) + 4,5(x91 + x92 + x93)
Beneficio:
8(x31 + x51 + x81 + x91) + 6,5(x32 + x52 + x82 + x92) + 6(x33 + x53 + x83 + x93)
Función objetivo: max{Beneficio− Costos}.
7
P2 La empresa Gasol produce y vende dos tipos de gasolina: corriente y especial. Para ello utiliza
dos tipos de petróleo crudo: liviano y pesado, que tienen un costo de 15 U.M. y 20 U.M. por
barril, respectivamente. Las caracteŕısticas de los dos tipos de petróleo se señalan en la siguiente
tabla:
Petróleo liviano Petróleo pesado
Densidad 0,65 0,85
Octanaje 70 102
Disponibilidad (barriles) 800 600
Costo (UM/barril) 15 20
Las especificaciones exigidas y los precios de venta para los productos finales se muestran en
la siguiente tabla:
Combustible Densidad Octanaje Precio
(kg/lt) (UM/barril)
Gasolina corriente min=0,70 85 25
max =0,75
Gasolina especial min=0,70 94 30
max =0,75
Cada barril puede contener 40 kg de petróleo liviano, o 50 kg de petróleo pesado, o 60 lt de
gasolina.
El octanaje de los combustibles (gasolina) corresponde al promedio ponderado (por el volumen)
de los octanajes de sus componentes (petróleo liviano y pesado).
Formule un modelo programación lineal que permita determinar qué tipo de mezclas utilizar y
cuál debe ser el nivel de producción, de manera que se obtenga la mayor utilidad posible.
Solución:
Variables de decisión :
• x11: kg de petróleo liviano que se debe utilizar en la producción de gasolina corriente.
• x12: kg de petróleo liviano que se debe utilizar en la producción de gasolina especial.
• x21: kg de petróleo pesado que se debe utilizar en la producción de gasolina corriente.
• x21: kg de petróleo pesado que se debe utilizar en la producción de gasolina especial.
Restricciones:
• Densidad Gasolina Corriente: entre 0,7 y 0,75. Recordemos que masa = densidad ·
volumen. Luego, el volumen de petróleo liviano utilizado en la producción de gasolina
corriente: x11/0, 65.
La restricción:
0, 7
(
x11
0, 65
+
x21
0, 85
)
≤ x11 + x21 ≤ 0, 75
(
x11
0, 65
+
x21
0, 85
)
• Densidad Gasolina Especial: entre 0,7 y 0,75.
Volumen de petróleo liviano utilizado en la producción de gasolina especial: x12/0, 65.
8
La restricción:
0, 7
(
x12
0, 65
+
x22
0, 85
)
≤ x11 + x21 ≤ 0, 75
(
x12
0, 65
+
x22
0, 85
)
• Octanaje Gasolina Corriente: mı́nimo 85 octanos.
Volumen de petróleo liviano utilizado en la producción de gasolina especial: x11/0, 65.
La restricción:
85
(
x11
0, 65
+
x21
0, 85
)
≤ 70
x11
0, 65
+ 102
x21
0, 85
• Octanaje Gasolina Corriente: mı́nimo 85 octanos.
Volumen de petróleo liviano utilizado en la producción de gasolina corriente: x11/0, 65.
94
(
x12
0, 65
+
x22
0, 85
)
≤ 70
x12
0, 65
+ 102
x22
0, 85
• Disponibilidad de petróleo liviano: hasta 800 barriles de 40 kg.
x11 + x21 = 800 · 40
• Disponibilidad de petróleo pesado: hasta 600 barriles de 50 kg.
x12 + x22 = 600 · 50
• Naturaleza de las Variables:
x11, x12, x21, x22 ∈ ❘
x11, x12, x21, x22 ≥ 0
Función Objetivo:
• Beneficios: notemos que los datos de Precio por barril y Litros por barril:
[
US
Barriles
Lts
Barriles
]
=
[
US
Lts
]
y dado que las variables están en kilos, utilizamos la fórmula de la densidad:
25
60
(
x11
0, 65
+
x21
0, 85
)
+
30
60
(
x12
0, 65
+
x22
0, 85
)
• Costos: en forma análoga dado que las variables están en kilos, utilizamos la fórmula
de la densidad:
15
40
(x11 + x12) +
20
50
(x21 + x22)
Luego se busca:
max
{
25
60
(
x11
0, 65
+
x21
0, 85
)
+
30
60
(
x12
0, 65
+
x22
0, 85
)
−
15
40
(x11 + x12) +
20
50
(x21 + x22)
}
9
P3 Una empresa transnacional exportadora de frutas que opera en América del Sur desea de-
terminar un plan de distribución de la fruta desde las plantas empacadoras hasta los centros
de distribución, para el peŕıodo de verano. Las plantas se encuentran ubicadas en Rancagua,
San Pablo y Bogotá. El mercado se ha agrupado en cuatro regiones, siendo cada una de ellas
atendida por un distribuidor. Los centros de distribución están localizados en Santiago, Rı́o
de Janeiro, Quito y Caracas. Además, Lima y Mendoza pueden funcionar como puntos in-
termedios de distribución. En la tabla se señalan los costos unitarios de transporte en M$$,
los requerimientos de cada región y la producción de fruta en las plantas, para el peŕıodo de
verano. Se busca formular un modelo de programación lineal que permita minimizar los costos
de transporte.
Oŕıg/Dest Stgo Ŕıo de Janeiro Quito Caracas Lima Mendoza Produc. Capac.
Rancagua 3 20 30 30 10 6 300 0
San Pablo 15 5 35 40 20 12 250 0
Bogotá 45 25 10 12 25 30 200 0
Santiago 0 15 30 48 12 10 0 0
Lima 12 22 8 30 0 15 0 150
Mendoza 10 15 12 35 15 0 0 180
Requerimientos 120 300 80 200 0 0 - -
Solución:
Definiremos los siguientes conjuntos:
• Plantas (P ) = {Rancagua, San Pablo, Bogota}
• Puntos Intermedios (PI) = {Lima, Mendoza}
• Centros de Distribución (CD) = {Santiago, Rio de Janeiro, Quito, Caracas}
• Oŕıgenes (O) = (P ) ∪ (PI) = {Rancagua, San Pablo, Bogota, Lima, Mendoza}
• Destinos (D) = (PI)∪(CD) = {Santiago, Rio de Janeiro, Quito, Caracas, Lima, Mendoza}
Variables:
• xij = toneladas de fruta que van de la ciudad i a la ciudad j. Con i ∈ (O) y j ∈ (D)
Restricciones:
• Para toda planta i, no puede salir más fruta de la que se produce, cpi capacidad
productiva de la planta i.
∀ i ∈ (P ),
∑
j∈(D)
xij ≤ cpi
Ejemplo: para i ∈ (P ), i = Rancagua
∑
j∈(D)
xRancagua,j ≤ 300
10
• Para todo punto intermedio j, lo que entra no puede superar la capacidad de alma-
cenamiento, cai capacidad de almacenamiento del punto intermedio i
∀ j ∈ (PI),
∑
i∈(O)
xij ≤ caj
Ejemplo: para j ∈ (PI), j = Lima
∑
i∈(O)
xi,Lima ≤ 150
• Conservación de Flujo: para todo punto intermedio, no puede salir más fruta de la
que entra
∀z ∈ (PI),
∑
i∈(O)
xiz −
∑
j∈(D)
xzj ≥ 0
Ejemplo: para z ∈ (PI), z = Mendoza
∑
i∈(O)
xi,Mend −
∑
j∈(D)
xMend,j ≥ 0
• Satisfacer la Demanda.∀j ∈ (CD),
∑
i∈(O)
xij = dj
Ejemplo: para j (CD), j = Stgo
∑
i∈(O)
xi,Stgo = 120
• Naturaleza de las Variables:
∀i ∈ (O), j ∈ (CD) xij ≥ 0
Función Objetivo:
min
∑
i∈(O)
∑
j∈(D)
xij · ctij
Donde ctij corresponde a los costos de transporte entre dos ciudades indicados en la tabla.
P4 Considere que Ud. es propietario de una empresa de delivery OptiPizza la cual atiende clientes
durante 16 horas diarias. En esta empresa Ud. posee M trabajadores a su cargo dedicados
a repartir el producto. Se propone organizar un sistema de turnos que satisfaga la demanda.
Consideraremos que un turno corresponde a un bloque de 8 horas continuas de trabajo que
comienza en la hora i y termina en la hora i + 8, por supuesto siempre es posible que dos
o mas turnos se crucen. Suponga que la demanda por hora es conocida y está dada por Di
(Entregas/hora), i = 1, . . . , 16. Suponga además que cada empleado satisface sólo un pedido
por hora y que no puede trabajar mas de 8 horas diarias.
a) Plantee un modelo de optimización lineal entero que permita encontrar la distribución
de los empleados por turno de modo que la cantidad de turnos sea mı́nima y se satisfaga
la restricción de demanda.
11
Indicación: Considere yi ∈ {0, 1} que indica si empieza un turno en la hora i o no.
Considere además xi el número de empleados que entran en la hora i.
b) Como cambia el modelo anterior si cada empleado tarda tres horas para satisfacer un
pedido.
c) Siguiendo las normas laborales, usted decide imponer que el 20% de sus empleados trabaje
horas extra (10 horas en lugar de 8). Reformule el modelo inicial para considerar este caso.
a) Solución:
Variables de decisión :
yi = 1 si empieza un turno en la hora i, 0 en caso contrario.
xi = cantidad de empleados que entran en la hora i.
qi = cantidad de empleados trabajando en la hora i.
Naturaleza de las Variables: xi, qi ∈ ◆, yi ∈ {0, 1}, ∀i = 1, 16
Restricciones:
• Relación de Variables:
qi =
i
∑
θ=i−7
xθ ∀i ∈ {9..,16}
qi =
i
∑
θ=1
xθ ∀i ∈ {1..,8}
• Relación de Variables:
xi ≤ Myi
• Cantidad de Trabajadores:
16
∑
i=1
xi ≤ M
• Satisfacer la Demanda: qi ≥ Di
• No pueden entrar trabajadores después de la hora 10: yi = 0 ∀i ∈ {10..,16}
Función Objetivo:
min
16
∑
i=1
yi
b) La siguiente restricción cambia:
Satisfacer la Demanda:
i
∑
θ=i−7
xθ −Di−1 −Di−2 ≥ Di ∀i ∈ {9..,16},
i
∑
θ=1
xθ −Di−1 −Di−2 ≥ Di ∀i ∈ {3..,8},
x1 ≥ D1, x2 + x1 −D1 ≥ D2
12
c) Es necesario agregar una nueva variable
x+j = Número de empleados que entran en la hora j, y que trabajan 10 horas
Además es necesario agregar algunas restricciones y cambiar otras
Restricción de porcentaje:
9
∑
j=1
x+j = 0,2
9
∑
j=1
(xj + x
+
j )
Restricción Logica: La empresa cierra a la hora 16, por lo tanto no hay horas extras
en el turno 8 y 9
xj + x
+
j ≤ Myi j = 1, . . . , 9
x+8 = 0
x+9 = 0
Restriccion de Demanda:
min{j,9}
∑
i=max{1,j−7}
xi +
min{j,7}
∑
i=max{1,j−9}
x+i ≥ Dj ∀j = 1, . . . , 16
Total de empleados:
9
∑
j=1
xj + x
+
j ≤ M
Naturaleza de las variables:
xj , x
+
j ∈ {0, 1, . . . ,M} j = 1, . . . , 9
yj ∈ {0, 1}
a) Otra alternativa de solución
Variables: yi = 1 si empieza un turno en la hora i, 0 en caso contrario.
xi = cantidad de empleados que entran en la hora i.
Naturaleza de las Variables: xi ∈ ◆, yi ∈ {0, 1}, ∀i
Restricciones:
• Relación de Variables:
xi ≤ Myi
• Cantidad de Trabajadores:
16
∑
i=1
xi ≤ M
13
• Satisfacer la Demanda:
x1 ≥ D1
x1 + x2 ≥ D2
x1 + x2 + x3 ≥ D3
x1 + x2 + x3 + x4 ≥ D4
x1 + x2 + x3 + x4 + x5 ≥ D5
x1 + x2 + x3 + x4 + x5 + x6 ≥ D6
x1 + x2 + x3 + x4 + x5 + x6 + x7 ≥ D7
x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ≥ D8
x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 ≥ D9
x3 + x4 + x5 + x6 + x7 + x8 + x9 ≥ D10
x4 + x5 + x6 + x7 + x8 + x9 ≥ D11
x5 + x6 + x7 + x8 + x9 ≥ D12
x6 + x7 + x8 + x9 ≥ D13
x7 + x8 + x9 ≥ D14
x8 + x9 ≥ D15
x9 ≥ D16
• No pueden entrar trabajadores después de la hora 10: yi = 0 ∀i ∈ {10..,16}
Función Objetivo:
min
16
∑
i=1
yi
b) La siguiente restricción cambia:
Satisfacer la Demanda:
i
∑
θ=i−7
xθ ≥ Di −Di−1 −Di−2 ∀i ∈ {9..,16},
i
∑
θ=1
xθ ≥ Di −Di−1 −Di−2 ∀i ∈ {3..,8},
x1 ≥ D1 x2 + x1 −D1 ≥ D2.
P5 Suponga que usted es el dueño de un laboratorio farmacéutico que produce un único producto
y sabe que debe satisfacer la demanda que enfrenta para los próximos T meses. Esta demanda
la ha estimado en Dt unidades para el mes t.
La empresa tiene un costo fijo de funcionamiento K para cada mes y un costo unitario de
producción de ct. Si decide no producir en un mes no se debe incurrir en el costo fijo, pero
entonces no se puede almacenar producto en bodega durante ese mes.
Además, cuenta con una capacidad máxima de producción de Qmax unidades igual para todos
los peŕıodos, y en cualquier peŕıodo puede decidir cambiar la tecnoloǵıa de producción que
está siendo utilizada, lo cual modificaŕıa los costos unitarios de producción a cat , con c
a
t < ct; y
la capacidad máxima de la empresa a Q′max. La implantación de esta nueva tecnoloǵıa obliga
a la empresa a invertir un monto I.
Cabe destacar que una vez que se ha realizado el cambio tecnológico no es posible regresar a
la tecnoloǵıa original, la inversión es realizada una única vez. Adicionalmente, para satisfacer
14
la demanda usted posee convenios con la competencia que le permiten comprar unidades del
mismo producto terminado a un precio de P , con P > ct para todo t.
Con esta información formule un modelo de programación lineal entera mixta que permita
determinar las acciones que se deben realizar a lo largo del peŕıodo de planificación con el fin
de minimizar los costos en que debe incurrir la empresa para satisfacer la demanda.
Solución:
Variables:
αt: 1 si se decide producir en el mes t, 0 sino.
xt: cantidad de unidades producidas con la tecnoloǵıa antigua en el peŕıodo t.
wt: cantidad de unidades producidas con la tecnoloǵıa nueva en el peŕıodo t.
βt: 1 si se decide cambiar la tecnoloǵıa en el peŕıodo t.
yt: cantidad de unidades compradas a la competencia.
zt: cantidad de unidades en bodega al final del periodo t.
Naturaleza de las Variables: xt, wt, yt, zt ∈ ◆, αt, βt ∈ {0, 1}, ∀t ∈ {1...T}
Restricciones:
• Cambiar a lo más una vez de tecnoloǵıa en el horizonte de evaluación:
T
∑
t=1
βt ≤ 1
• Satisfacer la demanda:
zt−1 + xt + wt + yt ≥ Dt ∀t ∈ {2...T}
• Inventario:
zt = zt−1 + xt + wt + yt −Dt∀t ∈ {2...T}
• Condición inicial almacenamiento:
z1 = x1 + w1 + y1 −D1
• Almacenar sólo si se produce:
zt ≤ αt ·M M >> 1 ∀t ∈ {1...T}
• Producir solamente si se decide hacerlo:
xt + wt ≤ Dt · αt ∀t ∈ {1...T}
• No sobrepasar capacidad con tecnoloǵıa antigua:
xt ≤ Qmax · (1−
t
∑
θ=1
βθ) ∀t ∈ {1...T}
15
• No sobrepasar capacidad con tecnoloǵıa nueva:
xt ≤ Q
′
max ·
t
∑
θ=1
βθ ∀t ∈ {1...T}
Función Objetivo:
min
T
∑
t=1
(K · αt + P · yt + ct · xt + c
a
t · wt + I · βt)
P6 Una empresa familiar se dedica al cultivo de remolacha, trigo y maravilla en 3 parcelas de su
propiedad.
El rendimiento agŕıcola de cada parcela está limitado tanto por la cantidad de tierra cultivable
como por la cantidad de agua asignada para regad́ıo por la comisión de aguas. Los datos
entregados por este organismo son:
Parcela Tierra Cultivable [ha] Asignación de Agua [ m3]
Parcela 1 400 600
Parcela 2 600 800
Parcela 3 300 375
Por otro lado, por distintas razones, la institución superior de agricultura ha establecido un
número máximo de hectáreas que pueden destinarse a cada uno de estos cultivos en las 3
parcelas en conjunto. Los datos asociados son:
Especie Consumo de Agua Cuota Máxima Ganancia Neta
[m3/ha] [ ha] [$/ ha]
Remolacha 3 600 400
Trigo 2 500 300
Maravilla 1 325 100
Si en cada parcela se sembrará la misma proporción de tierra cultivable y es posible cultivarse
cualquier combinación de especies, formule un plan que permita determinar el número de
hectáreas que se debe dedicar al cultivo de las distintas especies en cada parcela, de modo de
maximizarla ganancia neta total para todas las parcelas.
Solución:
Variables de Decisión
xi : Cantidad [ha] de remolacha a cultivar en la parcela i (i = 1, 2, 3)
yi : Cantidad [ha] de trigo a cultivar en la parcela i (i = 1, 2, 3)
zi : Cantidad [ha] de maravilla a cultivar en la parcela i (i = 1, 2, 3)
Restricciones
• Restricción de Tierra disponible por parcela
Parcela 1: x1 + y1 + z1 ≤ 400
Parcela 2: x2 + y2 + z2 ≤ 600
Parcela 3: x3 + y3 + z3 ≤ 300
16
• Restricción Disponibilidad de agua por parcela
Parcela 1: 3x1 + 2y1 + 1z1 ≤ 600
Parcela 2: 3x2 + 2y2 + 1z2 ≤ 800
Parcela 3: 3x3 + 2y3 + 1z3 ≤ 375
• Restricción de Cuota Máxima de cultivo por especie
Remolacha: x1 + x2 + x3 ≤ 600
Trigo: y1 + y2 + y3 ≤ 500
Maravilla 3: z1 + z2 + z3 ≤ 325
• Restricción de misma proporción de tierra cultivable
Parcela 1= Parcela 2: (x1 + y1 + z1)/400 = (x2 + y2 + z2)/600
Parcela 2= Parcela 3: (x2 + y2 + z2)/600 = (x3 + y3 + z3)/300
Parcela 3= Parcela 1: (x3 + y3 + z3)/300 = (x1 + y1 + z1)/400
• Naturaleza de las variables
xi, yi, zi ∈ ❘ , xi, yi, zi ≥ 0 , i = 1, 2, 3 .
Función Objetivo
F = 400(x1 + x2 + x3) + 300(y1 + y2 + y3) + 100(z1 + z2 + z3) .
El problema de optimización consiste en maximizar F bajo las restricciones definidas
previamente.
P7 Un comerciante compra azúcar a granel y vende al detalle. Para venderla tiene dos alternativas:
envases de 1 kilo y envases de 5 kilos. El precio de venta es $300 y $250 por kilo respectivamente,
y en el mercado del azúcar al detalle se pueden vender 20.000 kilos en envases de 1 kilo y 17.000
en envases de 5 kilos. Debido a un contrato anterior se deben entregar 5.000 kilos en envases
de 5 kilos a un determinado cliente. El comerciante se puede abastecer de azúcar desde dos
proveedores. El primero puede vender hasta 15.000 kilos a un precio de $90 por kilo, y el
segundo ofrece la cantidad de azúcar que el comerciante desee, pero a un precio de $110 por
kilo y debido a requerimientos de sus distribuidores el comerciante debe vender menos del tercio
del azúcar en envases de 1 kilo.
Si el precio de los envases y el proceso de envasado son nulos y el comerciante no tiene azúcar
almacenada y vende toda el azúcar que compra, formule un problema de programación lineal
que permita al comerciante decidir cual es el mejor plan de abastecimiento y ventas de modo
de obtener el mayor beneficio en su negocio.
solución:
Variables de Decisión:
xa : cantidad de azúcar vendida en envases de 1 kilo.
xb : cantidad de azúcar vendida en envases de 5 kilos.
y1 : cantidad de azúcar comprada a proveedor 1.
y2 : cantidad de azúcar comprada a proveedor 2.
Restricciones:
17
• No vender más azúcar en envases de 1 kilo que lo que acepta el mercado.
xa ≤ 20.000
• No vender más azúcar en envases de 5 kilos que lo que acepta el mercado.
xb ≤ 17.000
• Satisfacer, al menos, el contrato contráıdo.
xb ≥ 5.000
• Relacionar la cantidad de azúcar que se compra con la que se vende.
y1 + y2 = xa + xb
• No comprar más de lo permitido al cliente 1.
y1 ≤ 15.000
• Cumplir con la condición de vender menos del tercio del azúcar en envases de 1 kilo.
xa ≤
xa + xb
3
• Naturaleza de las variables.
xa, xb, y1, y2 ∈ ❘, xa, xb, y1, y2 ≥ 0 .
Función Objetivo:
F = (300xa + 250xb)− (90y1 + 110y2)
El problema consiste en maximizar F bajo las restricciones dadas en el item anterior.
P8 Una Compañ́ıa Naviera posee una dotación de barcos para el transporte de carga general.
Cada uno de los barcos posee 3 bodegas: una en la proa, otra en el centro y otra en la popa.
La capacidad máxima de estas bodegas son las siguientes
Bodega Peso [tons] Volumen [ m3]
Proa 2.000 100.000
Centro 3.000 135.000
Popa 1.500 30.000
A uno de los barcos se le asignó la carga de tres productos, pudiendo aceptar la totalidad o
parte de la carga y los datos de los productos están dados en la siguiente tabla:
Producto Cantidad Tara Utilidad
[tons] [m3/ton] [$/ ton]
Producto 1 6.000 60 12
Producto 2 4.000 60 16
Producto 3 2.000 25 10
Para mantener la linea de flotación, la proporción entre el peso de la carga y la capacidad de
toneladas en cada bodega debe ser la misma.
Formule un plan que permita distribuir la carga del barco para obtener el máximo de utilidad
total.
Solución:
18
Variables de Decisión:
xi,j : cantidad de toneladas del producto i a almacenar en la bodega j, donde usamos la
asignación
j = 1↔ proa , j = 2↔ centro , j = 3↔ popa .
Restricciones:
• Toneladas disponibles de cada producto.
j = 1,
3
∑
j=1
x1,j ≤ 6.000,
j = 2,
3
∑
j=1
x2,j ≤ 4.000,
j = 3,
3
∑
j=1
x3,j ≤ 2.000.
• Capacidad en toneladas de las bodegas
j = 1,
3
∑
i=1
xi,1 ≤ 2.000,
j = 2,
3
∑
i=1
xi,2 ≤ 3.000,
j = 3,
3
∑
i=1
xi,3 ≤ 1.500.
• Capacidad de volumen de cada bodega
j = 1, 60x1,1 + 50x2,1 + 25x3,1 ≤ 100.000
j = 2, 60x1,1 + 50x2,1 + 25x3,1 ≤ 135.000,
j = 3, 60x1,1 + 50x2,1 + 25x3,1 ≤ 30.000.
• Ĺınea de Flotación
3.000
3
∑
i=1
xi,1 = 2.000
3
∑
i=1
xi,2,
1.500
3
∑
i=1
xi,1 = 2.000
3
∑
i=1
xi,3,
1.500
3
∑
i=1
xi,2 = 3.000
3
∑
i=1
xi,3.
Observe que hay una condición redundante.
• Naturaleza de las variables.
xi,j ∈ ❘, xi,j ≥ 0 , i = 1, 2, 3 , j = 1, 2, 3 .
19
Función Objetivo:
F = 12
3
∑
j=1
x1,j + 16
3
∑
j=1
x2,j + 10
3
∑
j=1
x3,j .
El problema consiste en maximizar F bajo las restricciones anteriores.
P9 Un estudio de grabaciones debe producir un programa radial de una hora de grabación, com-
pletando totalmente los 60 minutos. En el programa, no debe haber más de 3 discursos y 5
ı́temes musicales en total. El tiempo asignado para discursos debe ser no menos que 1/8 del
tiempo asignado a música. La diferencia entre los 60 min. y los ı́temes o discursos debe ser
completada con comentarios, los cuales no pueden durar más de 12 minutos en total.
Si los discursos duran 5 minutos y los ı́temes musicales 8 minutos, determine la cantidad de
discursos e ı́temes de modo que se minimice el tiempo de los comentarios en la grabación.
Solución: Seguimos el formato usual y obtenemos
Variables de Decisión:
d : cantidad de discursos.
m : cantidad de ı́temes musicales.
Restricciones:
• Relación entre los tiempos de discursos e ı́temes musicales
m ≤ 5d .
• Duración de los comentarios
0 ≤ 60− 8m− 5d ≤ 12 .
• Naturaleza de las variables.
d ∈ {0, 1, 2, 3} , m ∈ {0, 1, 2, 3, 4, 5} .
Función Objetivo:
F = 60− 5d− 8m
El problema consiste en minimizar F bajo las restricciones dadas en el item anterior.
P10 Considere el problema de un granjero que se especializa en plantaciones de trigo, máız y re-
molacha en sus 500 acres de tierra. Durante el invierno, él debe decidir cuántos acres dedicar
a cada cultivo.
El granjero sabe que se necesitan al menos 200 toneladas de máız y 240 toneladas de trigo
para alimentar el ganado. Estas cantidades pueden ser cultivadas en la granja o compradas
a un vendedor externo. En caso de que la producción de trigo y máız exceda las necesidades
de alimentación del ganado, la producción por sobre lo requerido se vende en el mercado. Los
precios de venta son US$ 170 y US$ 150 por tonelada de máız y trigo respectivamente. Los
precios de compra son un 40 % superior debido al margen del intermediario y los costos de
transporte.
Por su parte, la remolacha se vende a US$ 36 dólares por tonelada, sin embargo, el gobierno
impone una cuota máxima de producción de remolacha. El exceso de remolacha por sobre la
20
cuota de producción se vende a un precio de US$ 10 por tonelada. La cuota del granjero para
el próximo año es de 6000 toneladas.
Basado en su experiencia, el granjero sabe que el rendimiento de las tierras es de 2.5, 3 y 20
toneladas por acre de máız, trigo y remolacha respectivamente. La tabla 1 resume estos datos
y los costos de plantación de cada cultivo.
Máız Trigo Remolacha
Rendimiento (Ton/Acre) 2.5 3 20
Costo de Plantación (US$/Acre) 150 230 260
Precio Venta (US$) 170 150 36 bajo 6000 Ton / 10 sobre 6000 Ton
Precio Compra (US$) 238 210
Requerimiento Mı́nimo (Unds)200 240
Tabla 1
Plantee un modelo para resolver el problema del granjero que busca maximizar sus ganacias.
Para ello debe decidir cuántos acres dedicar a cada cultivo, cuánto trigo o máız compra o vende
y cuántas toneladas de remolacha vende a precio alto o bajo.
Solución:
Variables de decisión:
x1 = acres destinados a máız.
x2 = acres destinados a trigo.
x3 = acres destinados a remolacha.
w1 = toneladas de máız vendidas.
w2 = toneladas de trigo vendidas.
y1 = toneladas de máız compradas.
y2 = toneladas de trigo compradas.
z1 = toneladas de remolacha vendidas a precio bajo.
z2 = toneladas de remolacha vendidas a precio alto.
Restricciones:
• Disponibilidad de tierras:
x1 + x2 + x3 ≤ 500
• Requerimientos de máız:
2,5x1 + y1 − w1 ≥ 200
• Requerimientos de trigo:
3x2 + y2 − w2 ≥ 240
• Cuota máxima de remolacha a precio alto:
z1 ≤ 6000
• Relación entre las variables de remolacha:
z1 + z2 ≤ 20x3
• Naturaleza de las variables:
xi, yi, wi, zi ≥ 0 ∀i
21
Función Objetivo:
max −150x1 − 230x2 − 260x3 − 238y1 + 170w1 − 210y2 + 150w2 + 36z2 + 10z1
P11 El diseño de minas de tajo abierto para la extracción de mineral se realiza a través de un
modelo de bloques como el que se muestra a continuación.
En este modelo, cada bloque (i, j), con i ∈ {1...n} y j ∈ {1...m}, se caracteriza por la cantidad
de mineral en él (mij) (en [ton mineral/ton extraida]) y el costo de extracción (cij) (en [$/ton
extraida]).
Plantee un modelo de programación lineal que permita decidir qué bloques extraer de modo
que las utiidades sean máximas, si el precio del mineral es p (en [$/ton mineral]) y el ángulo
de talud máximo es 45◦.
Nota: que el ángulo de talud máximo sea 45◦ significa que la profundidad de una columna no
puede ser más de un bloque mayor que la profundidad de las columnas vecinas.
Solución:
Variables de decisión:
xij que vale 1 si el bloque (i, j) es extráıdo, 0 en caso contrario.
Restricciones:
−1 ≤
n
∑
i=1
xij −
n
∑
i=1
xi(j+1) ≤ 1, ∀j ∈ {1...(m− 1)}
n
∑
i=1
xi1 ≤ 1,
n
∑
i=1
xim ≤ 1
Naturaleza: xij ∈ {0, 1}.
Función Objetivo:
max
∑
i,j
(p ·mij − cij)xij
P12 Una próspera compañ́ıa de comercialización de Mermelada necesita decidir cuales de las cuatro
bodegas disponibles utiliza para atender los pedidos de tres áreas geográficas. Las bodegas
están ubicadas en respectivas cuatro ciudades: Santiago, Talca, Chillan, Concepción; y las área
geográficas que serviŕıan se denominan como 1, 2 y 3.
Cada Bodega puede albergar, como máximo, K unidades (contenedores) por semana.
El costo fijo semanal de mantener abierta cada bodega es ci con i= en Santiago, Talca, Chillan,
Concepción. La demanda semanal requerida por cada área es dj con j= en 1,2,3. Los costos de
transporte entre cada bodega y área son tij por unidad transportada.
a) Plantee un modelo lineal que permita seleccionar las bodegas a utilizar, minimizando el
costo total del sistema y satisfaciendo la demanda semanal.
b) Qué restricción agregaŕıa para describir la siguiente situaciones
1) Si la bodega de Santiago es abierta, la bodega de Talca debe ser abierta también.
2) Si se abre la bodega de Talca no se puede abrir Chillán.
22
3) Si la bodega de Talca es abierta, la de Concepción no puede ser abierta y, si la bodega
de Concepción es abierta, la bodega de Talca no puede ser abierta.
4) No se pueden abrir todas y hay que abrir al menos una de ellas.
5) Se abren las bodegas de Santiago y Chillán o ninguna de las dos.
Solución:
a) Formulación del modelo
Variables de decisión:
xi que vale 1 si la bodega i es abierta, 0 en caso contrario.
yij cantidad transportada de la bodega i al área j.
Restricciones:
• Capacidad
∑
j
yij ≤ K · xi ∀i
• Demanda
∑
i
yij = dj ∀j
• Naturaleza
xi ∈ {0, 1} yij ≥ 0
Función objetivo
min
∑
i
xici +
∑
i,j
tijyij
b) Restricciones adicionales
1) Si la bodega de Santiago es abierta, la bodega de Talca debe ser abierta también:
xtalca ≥ xsantiago
2) Si se abre Talca no se puede abrir Chillán: xtalca ≤ 1− xchillan
3) Si la bodega de Talca es abierta, la de Concepción no puede ser abierta y, si la bodega
de Concepción es abierta, la bodega de Talca no puede ser abierta: xtalca +xconce = 1
4) No se pueden abrir todas y hay que abrir al menos una de ellas:
1 ≤ xsantiago + xtalca + xchillan + xconce ≤ 3
5) Se abren las bodegas de Santiago y Chillán o ninguna de las dos: xchillan = xsantiago
P13 Una persona dispone de un capital de 10 millones de pesos que puede invertir en acciones
de las sociedades A, B y C, en una cooperativa agraria, en dos fondos de inversion colectiva
E y F, en una Póliza de Seguros de vida, en Bonos del Estado, en Cédulas Hipotecarias, o
tenerlo en cuenta corriente. Los rendimientos brutos obtenidos son los que se muestran en
la tabla adjunta. Algunas de las inversiones no tienen una rentabilidad asegurada, ya que
los posibles beneficios están sujetos a variaciones del mercado, por lo que esa persona les ha
asociado de forma subjetiva, un cierto riesgo valorado en una escala de 0 a 10 puntos. Las
inversiones en acciones, bonos y cédulas se las administra y custodia su banco cobrándole una
comisión del 0,35 % sobre el valor de la inversión efectuada, mientras que por la gestión y
custodia de los fondos de inversión le cobran un 1% de la inversión. Sobre los rendimientos
brutos percibidos tendrá que pagar un impuesto total del 35%, pero algunas de las inversiones
efectuadas están sujetas a desgravaciones fiscales, según los tipos recogidos en la tabla. Con
23
objeto de aprovechar al máximo las desgravaciones fiscales, a esa persona le interesa invertir en
el seguro de vida, bonos y cédulas unas cantidades tales que la desgravación fiscal total debida
a esos tres conceptos en conjunto no rebase el ĺımite de los 7500 pesos. En la póliza del seguro
de vida quiere invertir quiere invertir entre 1000 y 2500 pesos. Al menos un millón de pesos
lo quiere colocar entre los fondos de inversión colectiva E y F y, además, el riesgo medio de
las inversiones sujetas a éste (acciones, cooperativa y fondos) ponderado por las respectivas
inversiones, no quiere que rebase el ĺımite de 3. ¿Cómo deberá realizar las inversiones para
maximizar el rendimiento neto?
Observación: Rendimiento neto =Rendimiento Bruto − Impuestos − Gastos(gestión admi-
nistración, custodia, etc.) + Desgravación fiscal.
Inversión Rendimientos Riesgo Desgravación fiscal
Brutos % Estimado
Sociedad A 20 5 10 % sobre rendimientos brutos
Sociedad B 15 2 10 % sobre rendimientos brutos
Sociedad C 30 10 10 % sobre rendimientos brutos
Cooperativa Agraria 10 1 5 % sobre rendimientos brutos
Fondo E 15 1 No hay
Fondo F 20 3 No hay
Seguro de Vida No hay No hay 15 % de la inversión efectuada
Bonos del Estado 7 No hay 5 % de la inversión efectuada
Cédulas Hipotecarias 5 No hay 10 % de la inversión efectuada
Efectivo en C/C 1 No hay No hay
Cuadro 1.1: Tabla de inversiones
Solución
Se formulara un modelo lineal (No es necesario, no se pide un modelo en particular).
Sea i ∈ {1, 2, . . . , }. Denotaremos por xi a la cantidad de dinero a invertir en la inversion
i, donde:
Inversión 1: Sociedad A
Inversión 2: Sociedad B
Inversión 3: Sociedad C
Inversión 4: Cooperativa Agraria
Inversión 5: Fondo E
Inversión 6: Fondo F
Inversión 7: Seguro de vida
Inversión 8: Bonos del estado
Inversión 9: Cedulas Hipotecarias
Inversión 10: Efectivo en cuenta corriente
• Naturaleza de las variables de decisión xi:
Posiblemente, xi ∈ ◆ ∪ {0}, i = 1, . . . , 10, sea la opción mas adecuada, sobre to-
do cuande se usa como unidad de medida el peso y por el tipo de moneda existente.
Alternativamente, xi ≥ 0, xi ∈ ◗, xi = 1, . . . , 10, es otra opción si se quiere usar
como unidad de medida ”millon de pesos”.
Finalmente, xi ≥ 0, xi ∈ ❘, i = 1, . . . , 10, es la mejor en terminos teóricos para
24
demostrar existencia de óptimos por ejemplo y en la práctica para la implementación
de un algoritmo eficiente.
Aquiaceptaremos la tercera opción, y la unidad sera el “peso”
• Restricciones:
◦ Cantidad total a invertir
10
∑
i=1
xi ≤ 10000000
◦ Desgravación total fiscal total en seguro de vida, bonos y cedulas.
0,15 · x7 + 0,05 · x8 + 0,1x9 ≤ 7500
◦ Cotas de inversión para seguro de vida.
1000 ≤ x7 ≤ 2500
◦ Inversión minima en fondos.
x5 + x6 ≥ 1000000
◦ Riesgo inversiones
5 · x1 + 2 · x2 + 10 · x3 + x4 + x5 + 3 · x6
x1 + x2 + x3 + x4 + x5 + x6
≤ 3
(Observación: de la restricción anterior x5 + x6 > 0, entonces el cuociente esta
bien definido)
2 · x1 − x2 + 7 · x3 − 2 · x4 − 2 · x5 ≤ 0
• Función objetivo: La función objetivo se obtiene a partir de los rendimientos brutos,
impuestos, gastos y desgravación.
Rendimiento bruto = 0,2·x1+0,15·x2+0,3·x3+0,1·x4+0,15·x5+0,2·x6+0,07·x8+0,05·x9+0,01·x10
Impuestos = 0,35 · (Rendimiento bruto)
Gastos = 0,0035 · (x1 + x2 + x3 + x8 + x9) + 0,01 · (x5 + x6)
Desgravacion = 0,1·(0,2·x1+0,15·x2+0,3·x3)+0,05·(0,1·x4)+0,15·x7+0,05·x8+0,1·x9
Función objetivo:
F (x1, x2, . . . , x10) = Rendimiento bruto− Impuestos−Gastos + Degravacion
25
P14 Se le ha encomendado al Ministerio de Transporte la misión de disminuir la emisión de conta-
minantes por parte de las micros de la capital. Para efectos de esta pregunta asuma que hay
sólo un contaminante que se mide en toneladas y que la meta propuesta consiste en disminuir
la emisión de contaminantes en H toneladas en los próximos T años.
Para conseguir ahorros en emisión de contaminante una micro debe cambiar su tecnoloǵıa
de combustión. Existen J tecnoloǵıas distintas y si la micro i se cambia a la tecnoloǵıa j, el
máximo ahorro posible es Vij por año.
Si bien el máximo ahorro posible es Vij , puede ser conveniente ahorrar menos (en emisión de
contaminante), ya que existe un costo variable asociado al ahorro de contaminante que depende
de cuánto se ahorra. Por la primeras Uij toneladas de contaminantes ahorradas por la micro i
con la tecnoloǵıa j en el peŕıodo t se incurre en un gasto bijt (por tonelada). Por sobre Uij se
debe gastar hijt por tonelada, con hijt mayor que bijt.
Si el cambio de tecnoloǵıa se hace en el peŕıodo t, la respectiva empresa dueña de la micro debe
desembolsar un monto fijo (inversión) de cijt pesos (solo en el peŕıodo t). Cada micro puede
cambiar de tecnoloǵıa a lo más una vez durante los T años y cada empresa k puede gastar un
máximo de Mk pesos en inversiones de este tipo. En total en Santiago hay I micros y se conoce
Sk, el subconjunto de micros que pertenecen a la empresa k.
Construya un modelo lineal mixto que determine cuánto debe ahorrar cada micro en cada
peŕıodo (y con qué tecnoloǵıa) de manera que se cumpla la meta de ahorro en emisión de
contaminante y se minimicen los costos totales.
Indicaciones:
- El monto Mk es sólo aplicable a los costos fijos (inversiones en cambio de tecnoloǵıa).
- Si j corresponde a la tecnoloǵıa actual que posee la micro i, entonces Vij vale cero.
Solución:
Variables:
αijt =
{
1 si la micro i se cambia a la tecnoloǵıa j el periodo t,
0 si no.
xijt = toneladas de contaminante ahorradas por la micro i en el periodo t usando la tecnoloǵıa
j.
yijt = toneladas de contaminante ahorradas por sobre Uij , para la micro i con tecnoloǵıa j en
el periodo t.
Restricciones:
El ahorro está acotado por la tecnoloǵıa de la micro:
xijt ≤ Vij
t
∑
τ=1
αijτ ∀i ∈ I, ∀j ∈ J, ∀t ∈ T.
La meta es ahorrar H toneladas:
∑
i∈I
∑
t∈T
∑
j∈J
xijt ≥ H.
26
Una micro se puede cambiar de tecnoloǵıa solo una vez:
∑
t∈T
∑
j∈J
αijt ≤ 1 ∀i ∈ I.
Presupuesto de inversión:
∑
i∈Sk
∑
t∈T
∑
j∈J
αijk ≤ Mk ∀k ∈ K.
Cantidad ahorrada a por sobre Uij :
(xijt − Uij) ≤ yijt ∀i, j, t.
Naturaleza:
xijt, yijt ≥ 0, αijt ∈ {0, 1} ∀i, j, t.
Función objetivo:
Minimizar
∑
t∈T
∑
i∈I
∑
j∈J
cijt · αijt + bijt · (xijt − yit) + hijt · yijt.
en forma equivalente:
Minimizar
∑
t∈T
∑
i∈I
∑
j∈J
cijt · αijt + bijt · xijt + (hijt − bijt) · yit.
Notamos que, dado que los costos son positivos y por un argumento de optimalidad, se satisface
que en la solución óptima yijt = (xijt−Uij) cada vez que se sobrepasa el nivel de ahorro definido
por Uij . En cambio, si xijt ≤ Uij se cumple que yijt = 0.
Observaciones: En caso que se interprete el enunciado como “la cantidad ahorrada por sobre
Uij tiene un costo de hij por cada tonelada desde 0 hasta xijt” será necesario introducir variables
adicionales.
Variable auxiliar:
βijt =
{
1 si la cantidad ahorrada por la micro i usando tecnoloǵıa j en el periodo t es mayor a Uij
0 si no
Costo de la cantidad ahorrada: Consideremos, x+ijt y x
−
ijt que definen el ahorro por sobre o bajo
Uij respectivamente, para el periodo t.
xijt = x
+
ijt + βijtUij + x
−
ijt,
0 ≤ x+ijt ≤ βijt(Vij − Uij),
0 ≤ x−ijt ≤ (1− βijt)Uij
Con esto la Función objetivo resulta
Minimizar
∑
t∈T
∑
i∈I
∑
j∈J
cijt · αijt + x
−
ijt · bijt + hijt · (x
+
ijt + βijtUij).
27