Ejemplos vARIOS

Fundamentos de Investigacion de Operaciones

Investigacion de Operaciones 1

Programacion Lineal Entera

11 de septiembre de 2003

1. Introduccion

Un LP donde se requiere que todas las variables sean enteras se denomina un problema deprogramacion lineal entera pura. Por ejemplo:

max z = 3x1 + 2x2

s.t. x1 + x2 ≤ 6x1, x2 ∈ Z+

(1.1)

Un LP donde solo algunas variables deben ser enteras se denomina problema de programacionlineal entera mixta. Por ejemplo:

max z = 3x1 + 2x2

s.t. x1 + x2 ≤ 6x2 ≥ 0x1 ∈ Z+

(1.2)

Un LP donde todas la variables deben ser igual a 1 o 0 se denomina problema de programacionlineal binaria. Por ejemplo:

max z = x1 − x2

s.t. x1 + 2x2 ≤ 22x1 − x2 ≤ 1

x1, x2 = {0, 1}

(1.3)

El concepto de relajacion de un problema de programacion lineal entera (IP) juega un rol funda-mental en la resolucion de este tipo de problemas.

Definicion 1 El LP obtenido eliminando todas las condiciones de valores enteros o binarios para lasvariables se denomina Relajacion del LP.

Por ejemplo, la relajacion de (1.1) quedarıa:

max z = 3x1 + 2x2

s.t. x1 + x2 ≤ 6x1, x2 ≥ 0

(1.4)

De la misma forma, la relajacion de (1.3) queda:

1

Segundo Semestre 2003 Programacion Lineal Entera

max z = x1 − x2

s.t. x1 + 2x2 ≤ 22x1 − x2 ≤ 1

x1, x2 ≥ 0

(1.5)

Cualquier IP puede ser visto como el LP relajado mas algunas restricciones adicionales. Por lotanto, el LP relajado es un problema menos restringido, o mas relajado, que el IP. En consecuenciala region factible para cualquier IP debe estar contenida en la region factible del correspondiente LPrelajado. Luego, si el problema es de maximizacion:

El valor optimo de z del LP relajado ≥ El valor optimo de z del IP

Consideremos el siguiente ejemplo:

max z = 21x1 + 11x2

s.t. 7x1 + 4x2 ≤ 13x1, x2 ∈ Z+

(1.6)

La region factible del problema relajado se presenta en la figura 1.1. En este caso, la region factibledel IP lo conforma el siguiente conjunto de puntos: S = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1)}. Eneste caso, mediante la evaluacion y comparacion de los valores de z en los seis puntos factibles esposible determinar el optimo. Luego, la solucion optima de (1.6) es z = 33, x1 = 0, x2 = 3.

0 0,5 1,0 1,5 2,0 2,5 3,00

0,5

1,0

1,5

2,0

2,5

3,0

x1

x2

7x1 +

4x2=13

= punto en la region factible

Figura 1.1: Region Factible del ejemplo 1.6

Si la region factible de la relajacion de un IP puro esta acotada, la region factible del IP consistira enun numero finito de puntos. En teorıa, mediante la enumeracion y la evaluacion de z en cada uno delos puntos es posible encontrar el mejor valor de z. El problema es que si la region factible contienemiles de puntos factibles, la enumeracion completa no es viable desde un punto de vista computacional.

Una segunda opcion para resolver el IP serıa mediante la aproximacion de la solucion obtenida dela relajacion. Por ejemplo si se resolviera la relajacion de (1.6) se obtendrıa: x1 = 13

7, x2 = 0. Redon-

deando esta solucion se obtendrıa: x1 = 2, x2 = 0 como posible solucion optima. Sin embargo estepunto esta fuera de la region factible por lo que no puede ser optimo. Otro candidato a optimo se

2


puede obtener redondeando el valor obtenido de la relajacion hacia abajo: x1 = 1, x2 = 0, valor quetampoco corresponde al optimo real del problema.

Como se ve en este ejemplo, no existen garantıas de que la aproximacion de soluciones del prob-lema relajado corresponda a la solucion optima real del IP. Por lo tanto, no es un enfoque validopara resolver el problema. Como se estudio previamente, el algoritmo Simplex resuelve un LP a partirde una solucion basica factible mejorandola iteracion a iteracion. Luego, en la mayorıa de los casos,Simplex examina solo una porcion de todas las soluciones basales factibles antes de llegar al optimo.En forma analoga, se podrıa esperar que existan algoritmos capaces de resolver un IP iterando de unasolucion factible entera a otra. Lamentablemente, no existen o no son conocidos tales algoritmos. Porlo tanto, como se vera en detalle mas adelante, la resolucion de un IP es mucho mas compleja que laresolucion de su relajacion.

2. Formulacion de IP

Los problema de programacion lineal entera permiten ampliar el espectro de problemas factiblesde plantear como modelos de programacion lineal. A continuacion se veran algunos ejemplos.

2.1. Problema de Asignacion de Capital

Ejemplo 1 Una empresa esta considerando cuatro posibles inversiones. La opcion 1 tiene asociadoun valor actualizado neto (VAN) de US$16000, la opcion 2 tiene un VAN de US$22000, la inversion 3representa un VAN de US$12000 y la inversion 4 posee un VAN de US$8000. Cada inversion requiereun cierto capital inicial: US$5000, US$7000, US$4000 y US$3000, para las inversiones 1, 2, 3 y 4respectivamente. Actualmente la empresa dispone $14000 para invertir. Formule un IP que permitadeterminar la forma de invertir el dinero de forma de maximizar las utilidades.

Las opciones son invertir o no en cada una de las posibilidades. Por lo tanto, conviene emplearvariables de tipo binaria para indicar si se escoge cada opcion:

xj =

{1 se invierte en la opcion j

0 en caso contrario∀ j = 1 . . . 4 (2.1)

La funcion objetivo para el problema queda (en miles):

max z = 16x1 + 22x2 + 12x3 + 8x4 (2.2)

En la expresion (2.2) se verifica que si la opcion j se realiza, entonces xj = 1 y se suma el VANrespectivo al valor de la funcion objetivo. En caso contrario, la variable xj = 0 y no se contabiliza eseaporte. Se sigue la misma logica para construir las restricciones.

Como existe un capital limitado de US$14000 para invertir, se debe satisfacer (en miles):

5x1 + 7x2 + 4x3 + 3x4 ≤ 14 (2.3)

Como no existen otras restricciones, el modelo completo para el problema queda:

max z = 16x1 + 22x2 + 12x3 + 8x4

s.t. 5x1 + 7x2 + 4x3 + 3x4 ≤ 14xj = {0, 1} ∀ j

(2.4)

Supongamos ahora que se agregan las siguientes restricciones al problema original:

3


1. La empresa puede invertir en a lo mas dos opciones.

2. Si la empresa invierte en la opcion 2, tambien debe invertir en 1.

3. Si la empresa invierte en 1, no puede tomar la opcion 4.

4. Solo se puede invertir en 3 si se escoge 1 o 2.

El planteo original del problema (2.4) se ve modificado de la siguiente forma:

1. En este caso basta con agregar la restriccion:

x1 + x2 + x3 + x4 ≤ 2

2. Para incorporar esta restriccion, se debe imponer que si x2 = 1 necesariamente x1 = 1. Luego,se podrıa emplear:

x2 ≤ x1 o x2 − x1 ≤ 0

Si x2 = 1 necesariamente se tendra x1 = 1. Si x2 = 0, x1 podrıa ser 0 o 1. Como no existenindicaciones en ese caso, se satisface el requerimiento de la nueva restriccion.

3. Esta restriccion impone la condicion de que las alternativas 1 y 4 sean excluyentes, en otraspalabras:

x1 + x4 ≤ 1

Como las variables son binarias, no se permite que ambas puedan ser igual a 1.

4. Aquı, la variable x3 puede valer 1 solo si x1 o x2 es igual a 1. No existen restricciones que diganque x1 y x2 sean excluyentes, por lo tanto eventualmente se podrıa escoger ambas. En este casose puede agregar:

x3 ≤ x1 + x2

Luego, basta con tener un 1 a la derecha de la desigualdad para que x3 pueda tomar valor iguala 1. Si se exigiera que deben escogerse 1 y 2 para poder seleccionar 3, la restriccion quedarıa:

2× x3 ≤ x1 + x2

En este caso se requiere tener un 2 a la derecha de la desigualdad para que x3 pueda ser igual auno.

2.2. Problemas de Costo Fijo

Ejemplo 2 Una companıa es capaz de producir tres tipos de prendas: poleras, shorts y pantalones.La fabricacion de cada tipo de prenda requiere de maquinaria especializada. La maquinaria puede serarrendada a los siguientes costos: US$200, US$150 y US$100 al mes en el caso de las poleras, shortsy pantalones respectivamente. La fabricacion de cada prenda requiere las cantidades de tela y manode obra indicadas en la Cuadro 2.1. Cada mes se dispone de 150 horas de mano de obra y 160 yd2

de tela. El costo unitario de produccion y el precio de venta de cada artıculo se muestra en el Cuadro2.2. Formule un IP que permita maximizar el beneficio de la fabrica.

Para plantear el modelo se pueden definir las siguientes variables:

x1 = numero de poleras producidas mensualmentex2 = numero de shorts producidos mensualmentex3 = numero de pantalones producidos mensualmente

(2.5)

4


Mano de Obra [hrs] Tela [yd2]

Poleras 3 4Shorts 2 3

Pantalones 6 4

Cuadro 2.1: Requerimientos de Fabricacion

Precio de Venta US$ Costo Variable US$

Poleras 12 6Shorts 8 4

Pantalones 15 8

Cuadro 2.2: Requerimientos de Fabricacion

Como el costo de arriendo de la maquinaria solo depende de la prenda producida, sera necesarioemplear variables binarias para cuantificar el hecho de arrendar o no cada maquina:

yi =

{1 se arrienda maquinaria para fabricar prendas tipo i

0 en caso contrario∀ j = 1 . . . 3 (2.6)

Para que el modelo funcione, se debe garantizar que:

Si xi > 0 → yi = 1Si xi = 0 → yi = 0

(2.7)

Para ello, se debe incorporar las restricciones de activacion de las variables binarias:

x1 ≤ M1y1

x2 ≤ M2y2

x3 ≤ M3y3

(2.8)

Los valores Mi son valores escalares lo suficientemente grandes de forma que sean una cota superiorpara el valor de xi en el contexto del problema. La restriccion (2.8) activa la variable binaria ya quesi xi > 0, para que la restriccion se pueda satisfacer la variable binaria yi debe ser exactamente iguala 1. En el caso que xi = 0, la variable binaria yi puede o no valer 1 sin afectar la satisfaccion de larestriccion, sin embargo, si la variable binaria valiera 1 se estarıa considerando el costo de arriendode una maquinaria que no se esta empleando. Evidentemente, como el problema es de maximizacionde ganancias, si no es estrictamente necesario cuantificar un costo, el algoritmo de resolucion se en-cargara de hacer que la variable yi = 0 en el optimo. En otras palabras, si el problema no obliga aconsiderar un costo, el algoritmo de resolucion se encargara de no contabilizarlo.

La funcion objetivo correspondera a la diferencia entre los ingresos por venta, menos los costos deproduccion fijos y variables:

z = (12x1 + 8x2 + 15x3)︸︷︷︸

Ingresos por venta

− (6x1 + 4x2 + 8x3)︸︷︷︸

Costos variables

− (200y1 + 150y2 + 100y3)︸︷︷︸

Costos fijos

(2.9)

Por lo tanto, la funcion objetivo a maximizar queda:

z = 6x1 + 4x2 + 7x3 − 200y1 − 150y2 − 100y3 (2.10)

5


A continuacion es preciso construir las restricciones del problema. En este caso existe un disponi-bilidad maxima de mano de obra y de tela. La restriccion de mano de obra queda:

3x1 + 2x2 + 6x3 ≤ 150 (2.11)

y la de tela serıa:

4x1 + 3x2 + 4x3 ≤ 160 (2.12)

Las restricciones (2.11) y (2.12) nos permiten estimar el valor de Mi. Por ejemplo si solo se produ-jeran artıculos de tipo 1, el valor maximo a producir quedarıa controlado por: mın{ 150

3, 160

4}, es decir,

40. Luego, basta con escoger M1 = 40, pero en general podrıa ser cualquier valor mayor. En el caso dex2 controla 160

3y para x3 basta con M3 = 25. En terminos generales los valores de Mi solo deben ser

lo suficientemente grandes para no restringir los valores de xi por lo que se escogera arbitrariamenteM1 = M2 = M3 = 100.

De acuerdo a la seleccion anterior, el modelo final para el problema queda:

max z = 6x1 + 4x2 + 7x3 − 200y1 − 150y2 − 100y3

s.t. 3x1 + 2x2 + 6x3 ≤ 1504x1 + 3x2 + 4x3 ≤ 160

x1 ≤ M1y1

x2 ≤ M2y2

x3 ≤ M3y3

xi ∈ Z+ ∀ i = 1 . . . 3yi = {0, 1} ∀ i = 1 . . . 3

(2.13)

2.3. Problemas de Cubrir Conjuntos

Ejemplo 3 Existen 6 barrios en una ciudad. La Alcaldıa debe determinar como construir estacionesde bomberos. La Alcaldıa desea construir el numero mınimo de estaciones de bomberos de forma deasegurar que al menos una estacion este a menos de 15 minutos de cada barrio. Los tiempos de viajeentre cada barrio de la ciudad se muestra en el Cuadro 2.3. Formule el IP que permita determinarcuantas estaciones deben ser construidas y donde deben estar ubicadas.

HastaDesde Barrio 1 Barrio 2 Barrio 3 Barrio 4 Barrio 5 Barrio 6

Barrio 1 - 10 20 30 30 20Barrio 2 10 - 25 35 20 10Barrio 3 20 25 - 15 30 20Barrio 4 30 35 15 - 15 25Barrio 5 30 20 30 15 - 14Barrio 6 20 10 20 25 14 0

Cuadro 2.3: Tiempo de viaje entre barrios

Para resolver el problema se debe buscar la asignacion del menor numero de estaciones de bomberosde forma de ’cubrir’ un conjunto de Barrios. Para construir el IP, conviene definir las siguientesvariables:

6


xi =

{1 se construye una estacion de bomberos en el barrio i

0 en caso contrario∀ i = 1 . . . 6 (2.14)

De acuerdo a las variables definidas, el total de estaciones a construir queda definido por:

z =6∑

i=1

xi (2.15)

Para construir las restricciones, es preciso obtener del Cuadro 2.3 en que lugares es factible cons-truir la estaciones de bomberos para asegurar que cada barrio quede a menos de 15 minutos de almenos una de ellas. Por ejemplo, para asegurar que al menos una estacion quede a menos de 15 min-utos del Barrio 1 se debe construir en el propio Barrio 1 o bien en el Barrio 2. Siguiendo la mismalogica se construye el Cuadro 2.4.

Barrio Barrios factibles de construccion

1 1, 22 1, 2, 63 3, 44 3, 4, 55 4, 5, 66 2, 5, 6

Cuadro 2.4: Lugares factibles de construccion de estaciones de bomberos

Luego, para asegurar la condicion solicitada para el Barrio 1 se puede agregar:

x1 + x2 ≥ 1 (2.16)

Incorporando las restricciones para los otros barrios se completa el IP:

max z = x1 + x2 + x3 + x4 + x5 + x6

s.t. x1 + x2 ≥ 1 (Barrio 1)x1 + x2 + x6 ≥ 1 (Barrio 2)

x3 + x4 ≥ 1 (Barrio 3)x3 + x4 + x5 ≥ 1 (Barrio 4)x4 + x5 + x6 ≥ 1 (Barrio 5)x2 + x5 + x6 ≥ 1 (Barrio 6)

xi = {0, 1} ∀ i = 1 . . . 6

(2.17)

2.4. Problemas con restricciones excluyentes o no excluyentes

En un modelo matematico puede ocurrir frecuentemente que existan dos o mas restricciones quesean mutuamente excluyentes, por ejemplo sean las restricciones:

f(x1, x2, . . . xn) ≤ 0 (2.18)

g(x1, x2, . . . xn) ≤ 0 (2.19)

7


Si se desea que solo sea satisfecha una de las restricciones, se puede modificar el planteo de lasrestricciones de la siguiente forma:

f(x1, x2, . . . xn) ≤ My (2.20)

g(x1, x2, . . . xn) ≤ M(1− y) (2.21)

donde y es una variable binaria y M es una constante lo suficientemente grande para asegurar que lasrestricciones:

f(x1, x2, . . . xn) ≤ M

g(x1, x2, . . . xn) ≤ M

se satisfacen para toda combinacion de valores de x1, x2, . . . xn. Por lo tanto, si y = 1 se tiene quef ≤ M y g ≤ 0, es decir, solo existe para efectos practicos las restriccion asociada a g. En casocontrario, si y = 0 se tiene que f ≤ 0 y g ≤ M , por lo tanto solo existe la restriccion f en terminospracticos.

Si se deseara que al menos una de las restricciones fuera satisfecha, el planteo quedarıa:

f(x1, x2, . . . xn) ≤ My1

g(x1, x2, . . . xn) ≤ My2

y1 + y2 ≤ 1

donde y1 e y2 son variables binarias independientes. La idea anterior se puede extender a cualquiernumero de restricciones.

Ejemplo 4 Una fabrica de automoviles construye tres tipos de autos: compactos, medianos y grandes.Los requerimientos de materiales, mano de obra y el beneficio obtenido por cada tipo de auto fabricadose muestra en el Cuadro 2.5. Actualmente, la fabrica dispone 6000 toneladas de materiales y 60000horas de mano de obra. Para que la produccion de un tipo de vehıculo sea economicamente factible,se deben producir al menos 1000 unidades de cada tipo que se fabrique. Formule un IP que permitamaximizar el beneficio de la fabrica.

Compacto Mediando Grande

Materiales [T] 1,5 3 5Mano de obra [hr] 30 25 40Beneficio [US$] 2000 3000 4000

Cuadro 2.5: Requerimientos y beneficios por tipo de vehıculo.

Como variables de decision conviene emplear:

xi = numero de automoviles de tipo i fabricados (2.22)

La funcion objetivo queda definida por la combinacion lineal de las variables por sus respectivosbeneficios unitarios (en miles):

max z = 2x1 + 3x2 + 4x3 (2.23)

8


A continuacion se debe agregar la restriccion que obligue a que si se produce un determinado tipode vehıculo, se produzcan como mınimo 1000 unidades, es decir:

xi ≤ 0 o xi ≥ 1000 ∀ i = 1 . . . 3 (2.24)

O bien:

xi ≤ 0 o 1000− xi ≤ 0 ∀ i = 1 . . . 3 (2.25)

Introduciendo la variable binaria yi, las restricciones quedan:

xi ≤ Miyi (2.26)

1000− xi ≤ Mi(1− yi) (2.27)

yi = {0, 1} (2.28)

Un valor posible para Mi se puede obtener a partir de la disponibilidad de materiales y de manode obra, por ejemplo para los vehıculos compactos serıa: M1 = mın{6000

1,5, 60000

30} = 2000. Siguiendo la

misma logica se puede obtener: M2 = 2000 y M3 = 1200.

Por otro lado, se deben incorporar las restricciones relativas a la disponibilidad de materiales ymano de obra:

1,5x1 + 3x2 + 5x3 ≤ 6000 (Materiales)30x1 + 25x2 + 40x3 ≤ 60000 (Mano de Obra)

(2.29)

Finalmente, el IP queda:

max z = 2x1 + 3x2 + 4x3

s.t. x1 ≤ 2000y1

1000− x1 ≤ 2000(1− y1)x2 ≤ 2000y2

1000− x2 ≤ 2000(1− y2)x3 ≤ 1200y3

1000− x3 ≤ 1200(1− y3)1,5x1 + 3x2 + 5x3 ≤ 6000

30x1 + 25x2 + 40x3 ≤ 60000xi ∈ Z+ ∀ i = 1 . . . 3yi = {0, 1} ∀ i = 1 . . . 3

(2.30)

2.5. Problemas con restricciones de tipo si... entonces

En un modelo matematico puede ocurrir que si la restriccion:

f(x1, x2, . . . xn) > 0 (2.31)

se satisface, entonces la restriccion:

g(x1, x2, . . . xn) ≥ 0 (2.32)

9


tenga tambien que satisfacerse, mientras que si f ≤ 0 la restriccion g ≥ 0 pueda o no satisfacerse.Para garantizar esta condicion se pueden incorporar las siguientes restricciones:

−g(x1, x2, . . . xn) ≤ My (2.33)

f(x1, x2, . . . xn) ≤ M(1− y) (2.34)

y = {0, 1} (2.35)

El valor de M debe ser escogido de tal forma que si f ≤ M y −g ≤ M se asegure que todos losvalores de x1, x2, . . . xn satisfagan las restricciones. Si la variable binaria vale cero, se tiene f ≤ M ,en particular f > 0. Por otro lado, si y = 0 se tiene −g ≤ 0 o bien g ≥ 0. En caso contrario, cuandoy = 1 se tiene f ≤ 0, es decir, no se puede cumplir que f > 0. Si y = 1 se tiene −g ≤ M , es decir, secumple si g ≥ 0 o si g < 0.

En suma, si se satisface f > 0, la variable binaria debe valer 1 lo que obliga a satisfacer g ≤ 0.

A modo de ejemplo, supongamos que en el problema de la fabrica de automoviles si se fabricanautos compactos no se pueden fabricar vehıculos de otro tipo. En otras palabras se tiene:

Si x1 > 0 → x2 = x3 = 0 (2.36)

En forma equivalente se tiene:

Si x1 > 0 → x2 + x3 ≤ 0 o − x2 − x3 ≥ 0 (2.37)

Por lo tanto, basta incorporar:

x2 + x3 ≤ My (2.38)

x1 ≤ M(1− y) (2.39)

y = {0, 1} (2.40)

El valor de M no tiene porque ser unico. En este caso, podemos emplear los valores de Mi calculadospreviamente:

x2 + x3 ≤ (M2 + M3)y = 3200y (2.41)

x1 ≤ M1(1− y) = 2000(1− y) (2.42)

y = {0, 1} (2.43)

2.6. Problemas con funciones lineales definidas por tramos

Una funcion lineal definida por tramos corresponde a un conjunto de segmentos rectos. Los puntosdonde se producen cambios de pendiente se denominan puntos de quiebre. Sea f(x) una funcion linealpor tramos con puntos de quiebre b1, b2, . . . bn, para cualquier k = 1, 2, . . . n, bk ≤ x ≤ bk+1. Entonces,para algun numero zk (0 ≤ zk ≤ 1), x puede ser escrito como:

x = zkbk + (1− zk)bk+1 (2.44)

Como f(x) es lineal para bk ≤ x ≤ bk+1, se puede escribir:

10


f(x) = zkf(bk) + (1− zk)f(bk+1) (2.45)

La expresion anterior representa una parametrizacion entre los valores extremos de la funcion enese intervalo, en terminos del parametro zk ≤ 1. La idea geometrica se ilustra en la Figura 2.1.

f(x)

xb1 b2 b3

f(b2)

f(b3)

Figura 2.1: Funcion lineal por tramos

La funcion objetivo puede ser escrita como:

f(x) = z1f(b1) + z2f(b2) + . . . + znf(bn) (2.46)

Evidentemente, se debe cumplir que zk+1 + zk = 1 para algun k. Sea yk una variable binariaauxiliar que indica la presencia de la variable x dentro del intervalo k (k = 1 . . . n − 1). Entonces sepuede escribir las siguientes restricciones:

z1 ≤ y1

z2 ≤ y1 + y2

z3 ≤ y2 + y3

...zn−1 ≤ yn−2 + yn−1

zn ≤ yn−1

(2.47)

Por lo tanto, si la variable x esta en el intervalo k, se tiene yk = 1 y solo zk y zk+1 pueden serdistintas de cero. Evidentemente, la variable x solo puede pertenecer a un intervalo:

y1 + y2 + . . . + yn−1 = 1 (2.48)

Como zk+1 = 1− zk, se debe agregar la restriccion:

z1 + z2 + . . . + zn = 1 (2.49)

De acuerdo a la ecuacion (2.44) se tiene:

x = z1b1 + z2b2 + . . . + znbn (2.50)

Para ilustrar la incorporacion de funciones lineales definidas por tramos consideremos el siguienteejemplo:

11


Ejemplo 5 Una refinerıa produce dos tipos de gasolina a partir de dos tipos de petroleos. Cada galonde gasolina tipo 1 debe contener a lo menos 50% de petroleo 1 y cada galon de gasolina tipo 2 debecontener al menos 60% de petroleo tipo 1. Cada galon de gasolina tipo 1 puede ser vendido a $12 ycada galon de tipo 2 puede ser vendido a $14. Actualmente se dispone de 500 galones de petroleo tipo1 y 1000 galones de petroleo de tipo 2. Se puede comprar hasta 1500 galones adicionales de petroleotipo 1 al siguiente precio: los primeros 500 galones se deben pagar a $25 el galon; los siguientes 500galones se deben pagar a $20 el galon; los siguientes 500 galones se compran a $15 el galon. Formuleun IP que permita determinar la forma de maximizar las utilidades.

Para plantear el modelo se pueden definir las siguientes variables:

x = cantidad de petroleo tipo 1 compradoxij = cantidad de petroleo de tipo i empleado para producir gasolina de tipo j

(2.51)

La funcion objetivo queda:

max z = 12(x11 + x21) + 14(x12 + x22)− c(x) (2.52)

donde:

c(x) =

25x 0 ≤ x ≤ 50025x + 2500 500 ≤ x ≤ 100015x + 7500 1000 ≤ x ≤ 1500

(2.53)

La restriccion relativa a la disponibilidad de petroleo tipo 1 queda:

x11 + x12 ≤ x + 500 (2.54)

La restriccion relativa a la disponibilidad de petroleo tipo 2 queda:

x21 + x22 ≤ 1000 (2.55)

Para obligar que la gasolina tipo 1 tenga al menos un 50% de petroleo tipo 1 se agrega:

x11

x11 + x21

≥ 0,5 (2.56)

Para obligar que la gasolina tipo 2 tenga al menos un 60% de petroleo tipo 1 se agrega:

x12

x12 + x22

≥ 0,6 (2.57)

En la funcion objetivo se reemplaza c(x) por:

c(x) = 0z1 + c(500)z2 + c(1000)z3 + c(1500)z4

c(x) = 12500z2 + 22500z3 + 30000z4

(2.58)

El valor de la variable x se calcula segun:

x = 0z1 + 500z2 + 1000z3 + 1500z4 (2.59)

Las variables continuas zk se relacionan con las binarias yk seun:

z1 ≤ y1

z2 ≤ y1 + y2

z3 ≤ y2 + y3

z4 ≤ y3

(2.60)

12


Ademas se tiene que:

z1 + z2 + z3 + z4 = 1y1 + y2 + y3 = 1

(2.61)

Finalmente se agrega la naturaleza de las variables:

zi ≥ 0 ∀ i = 1 . . . 4yj = {0, 1} ∀ j = 1 . . . 3

xkr ≥ 0 ∀ k × r

(2.62)

3. Resolucion de IP - Metodo de Ramificacion y Acotamiento

El metodo de ramificacion y acotamiento consiste en una tecnica de enumeracion eficiente de lospuntos factibles de subproblemas de un cierto problema original. Evidentemente, si se resuelve larelajacion de un problema de programacion lineal entera pura o mixta y se encuentra que todas lasvariables que deben ser enteras o binarias cumplen la condicion de enteridad, el optimo encontradosera tambien el optimo del IP original. Por ejemplo si se resuelve la relajacion del siguiente problema:

Ejemplo 6max z = 3x1 + 2x2

s.t. 2x1 + x2 ≤ 6x1, x2 ∈ Z+

(3.1)

se obtiene como solucion: x1 = 0, x2 = 6 y z = 12, que corresponde exactamente a la solucion del IPoriginal. Tal como se ve en la Figura 3.1, la region factible del IP es un subconjunto de la relajacion,por lo tanto el optimo del IP no puede ser mejor que el optimo de su relajacion. La generalizacion deesta idea es el principio basico del metodo de ramificacion y acotamiento.

0 1 2 30

1

2

3

4

5

6

x1

x2

2x1+

x2=6

= punto en la region factible

Figura 3.1: Region Factible del ejemplo 3.1

Para ilustrar como opera la tecnica, consideremos el siguiente ejemplo:

Ejemplo 7 Una mueblerıa fabrica mesas y sillas. Una mesa requiere de 1 hora de mano de obra y 9pies cuadrados de madera, una silla requiere de 1 hora de mano de obra y 5 pies cuadrados de madera.Actualmente, la mueblerıa dispone de 6 horas de mano de obra y 45 pies cuadrados de madera. Cada

13


mesa genera una utilidad de US$8, cada silla representa una utilidad de US$5. Formule y resuelva unIP para maximizar el beneficio de la mueblerıa.

Consideremos:

x1 = numero de mesas fabricadasx2 = numero de sillas fabricadas

(3.2)

Como x1 y x2 deben ser enteras, el IP que resuelve el problema queda:

max z = 8x1 + 5x2

s.t. x1 + x2 ≤ 69x1 + 5x2 ≤ 45

x1, x2 ∈ Z+

(3.3)

En primer lugar se resuelve la relajacion del IP, llamaremos a este problema el Subproblema 1:

Subproblema 1:

max z = 8x1 + 5x2

s.t. x1 + x2 ≤ 69x1 + 5x2 ≤ 45

x1, x2 ≥ 0

(3.4)

La resolucion grafica del Subproblema 1 se muestra en la Figura 3.2. En este caso, la solucionoptima corresponde al punto x1 = 15

4= 3,75 y x2 = 9

4= 2,25, con valor de la funcion objetivo z = 165

4.

Como se menciono anteriormente, la solucion del IP no puede ser mejor a la del IP relajado, por loque z = 165

4es una Cota Superior para la funcion objetivo.

0 1 2 3 4 5 60

1

2

3

4

5

6

7

8

9

x1

x2

x1 +

x2 =

6

9x1+5x

2=45

optimo

Figura 3.2: Region Factible del Subproblema 1

El proximo paso es seleccionar una particion de la region factible de la relajacion de forma deintentar obtener la solucion optima del IP. Para ello, arbitrariamente se escoge una variable que nosatisfaga las condiciones del IP, es decir, una variable fraccionaria que deberıa ser entera, por ejemplox1. Como se busca un valor entero para x1 interesa que x1 ≤ 3 o bien que x1 ≥ 4, ya que no puedehaber una solucion factible entera en el intervalo 3 < x1 < 4, en otras palabras se buscan soluciones

14


en los valores enteros mas cercanos al valor fraccionario obtenido. De acuerdo a ello, ramificaremos lavariable x1 definiendo los siguientes subproblemas:

Subproblema 2: Subproblema 1 + restriccion: x1 ≤ 3Subproblema 3: Subproblema 1 + restriccion: x1 ≥ 4

(3.5)

Notese que ambos subproblemas excluyen el valor x1 = 15

4, es decir, la solucion optima de los

subproblemas no puede ser igual al de la relajacion. Por otro lado, como se esta resolviendo unproblema mas restrictivo que la relajacion original el valor de la funcion objetivo no puede ser mejor.

La ramificacion de las variables se ordena en un arbol de ramificacion como se muestra en laFigura 3.3. La region factible del subproblema 2 se muestra en la Figura 3.4. Los puntos extremos dela region factible: D, E, F y G son los candidatos a optimos, evaluando se obtiene: zD = 0, zE = 24,zF = 39 y zG = 30, por lo que la mejor solucion corresponde al punto F (x1 = 3, x2 = 3), con valor dela funcion objetivo: z = 39. En este caso, la solucion obtenida satisface las condiciones de enteridad,por lo que es posible definir como cota superior z = 39.

Subproblema 1z = 165

4

x1 = 15

4

x2 = 9

4

Subproblema 2 Subproblema 3

x1 ≤ 3 x1 ≥ 4

Figura 3.3: Arbol de ramificacion subproblemas 2 y 3

0 1 2 3 4 5 60

1

2

3

4

5

6

7

8

9

x1

x2

x1 +

x2 =

6

9x1+5x

2=45

x1=

3

D E

F

G

Figura 3.4: Region Factible del subproblema 2

Si bien la solucion obtenida del subproblema 2 satisface todas las condiciones del problema, debe-mos completar la ramificacion ya que aun hay esperanzas de obtener una solucion menor o igual al valor

15


optimo del subproblema 1, pero mejor a la cota superior actual. La region factible del subproblema 3se muestra en la figura 3.5. Los puntos extremos de la region factible son: A, B y C, con respectivosvalores de la funcion objetivo: zA = 40, zB = 32 y zC = 41. Por lo tanto el optimo corresponde a:x1 = 4 y x2 = 9

5, valor que no satisface la condicion de enteridad.

0 1 2 3 4 5 60

1

2

3

4

5

6

7

8

9

x1

x2

x1 +

x2 =

6

9x1+5x

2=45

x1=

4

B A

C

Figura 3.5: Region Factible del subproblema 3

Si bien hasta ahora se dispone de una solucion entera con valor de la funcion objetivo de 39, enel subproblema 3 se obtuvo como valor optimo: z = 41. Si bien el subproblema 3 no representa unasolucion factible para el IP, al ramificar a partir de este problema se podrıa esperar un valor de lafuncion objetivo que sea menor o igual a 41 pero que podrıa ser mejor que 39, por lo que no se puededar como finalizada las ramificaciones. De acuerdo a ello, podemos definir dos nuevos subproblemasa partir el subproblema 3. Como la variable x2 = 9

5no es entera, conviene buscar valores con las

siguientes particiones de la region factible: x2 ≤ 1 y x2 ≥ 2. En otras palabras, se deben resolver lossiguientes subproblemas:


(3.6)

El arbol de ramificacion con los dos nuevos subproblemas se muestra en la Figura 3.6. La regionfactible para los subproblemas 4 y 5 se indican en la Figura 3.7. Para el subproblema 4, los nuevoscandidatos a optimos son los puntos H e I, con valores de la funcion objetivo: zH = 37 y zI = 365

9=

40,556. Entre los puntos A, B, H e I, el mejor valor se obtiene para el punto I con x1 = 40

9y x2 = 1.

Respecto del subproblema 5 se observa que no existen puntos que satisfagan simultaneamente lasrestricciones del subproblema 3 y x2 ≥ 2, por lo que tiene solucion imposible.

Como la solucion optima del subproblema 4 es superior a la cota, es necesario volver a ramificarya que eventualmente se podrıa encontrar una solucion que sea menor o igual a z = 365

9, pero mejor

que z = 39. En este caso, la variable no entera es x1 = 40

9, por lo que conviene definir los siguientes

subproblemas:


(3.7)

16



4

x1 = 15

4

x2 = 9

4

Subproblema 2z = 39x1 = 3x2 = 3


5

x1 ≤ 3 x1 ≥ 4


x2 ≤ 1 x2 ≥ 2


0 1 2 3 4 5 60

1

2

3

4

5

6

7

8

9

x1

x2

x1 +

x2 =

6

9x1+5x

2=45

x1=

4

B A

x2 = 2

x2 = 1 IH

Figura 3.7: Region Factible del subproblemas 4 y 5

El nuevo arbol de ramificacion se muestra en la Figura 3.8. Se agregan las nuevas restriccionesreferentes a x1 y se completa la region factible para los subproblemas 6 y 7 en la Figura 3.9. En estecaso, la region factible para el subproblema 6 se reduce al segmento de lınea entre los puntos B y H,con valores para la funcion objetivo de: zB = 32 y zH = 37, por lo que el optimo corresponde al puntoH. Como en el punto H los valores de las variables son enteros, se podrıa pensar que H es un candidatoa optimo. Sin embargo, el valor de la funcion objetivo en H es inferior a la cota definida previamente,por lo que se descarta. En el subproblema 7, el unico punto que satisface todas las restricciones es elpunto A, con valor de la funcion objetivo z = 40. Como en el subproblema 7 el valor de las variableses entero (x1 = 5 y x2 = 0) y dado que el valor de la funcion objetivo es mejor que la cota actual,40 se transforma en la nueva cota. Como el subproblema 6 presenta un valor de la funcion objetivo

17


inferior a la cota, no tiene sentido seguir ramificando pues se ha alcanzado el optimo del IP. El arbolde ramificacion completo se muestra en la Figura 3.10 donde se identifica la solucion optima.


4

x1 = 15

4

x2 = 9

4



5

x1 ≤ 3 x1 ≥ 4


9

x1 = 40

9

x2 = 1

Subproblema 5Imposible

x2 ≤ 1x2 ≥ 2


x1 ≤ 4 x1 ≥ 5


0 1 2 3 4 5 60

1

2

3

4

5

6

7

8

9

x1

x2

x1 +

x2 =

6

9x1+5x

2=45

x1=

4

B A

x2 = 1

x1=

5

H

Figura 3.9: Region Factible del subproblemas 6 y 7

18



4

x1 = 15

4

x2 = 9

4



5

x1 ≤ 3 x1 ≥ 4


9

x1 = 40

9

x2 = 1


x2 ≤ 1x2 ≥ 2



x1 ≤ 4 x1 ≥ 5

Figura 3.10: Arbol de ramificacion final

Ejemplo 8 Considere un problema de programacion lineal entera mixta cuyo objetivo es la maxi-mizacion de una funcion z involucrando las variables binarias x1, x2 y x3 y la variable continuax4 ≥ 0. El Cuadro 3.1 presenta la solucion optima para todos los problemas relajados posibles deobtener (un guion en la columna correspondiente a las variables x1, x2 y x3 significa que la variableesta libre en el problema relajado).

x1 x2 x3 x z x1 x2 x3 x z x1 x2 x3 x z

- - - (0.2,1,0,0) 82.80 0 - - (0,1,0.67,0) 80.67 1 - - (1,0,0,0) 74.00- - 0 (0.2,1,0,0) 82.80 0 - 0 (0,1,0,2) 28.00 1 - 0 (1,0,0,0) 74.00- - 1 (0,0.8,1,0) 79.40 0 - 1 (0,0.8,1,0) 79.40 1 - 1 (1,0,1,0) 63.00- 0 - (0.7,0,0,0) 81.80 0 0 - Imposible - 1 0 - (1,0,0,0) 74.00- 0 0 (0.7,0,0,0) 81.80 0 0 0 Imposible - 1 0 0 (1,0,0,0) 74.00- 0 1 (0.4,0,1,0) 78.60 0 0 1 Imposible - 1 0 1 (1,0,1,0) 63.00- 1 - (0.2,1,0,0) 82.80 0 1 - (0,1,0.67,0) 80.67 1 1 - (1,1,0,0) 62.00- 1 0 (0.2,1,0,0) 82.80 0 1 0 (0,1,0,2) 28.00 1 1 0 (1,1,0,0) 62.00- 1 1 (0,1,1,0.5) 77.00 0 1 1 (0,1,1,0.5) 77.00 1 1 1 (1,1,1,0) 51.00

Cuadro 3.1: Soluciones de todas las relajaciones posibles

Resuelva este problema aplicando la tecnica de ramificacion y acotamiento.

19


En primer lugar se resuelve el problema relajado completo, es decir, se libera el valor de las tresvariables binarias. De acuerdo al Cuadro 3.1, se tiene:

Subproblema 1

x1 = 0.2x2 = 1x3 = 0x4 = 0z = 82.80

(3.8)

En la solucion del subproblema 1 el valor de la variable x1 no satisface la condicion de binaria, porlo tanto se ramifica en funcion de los valores que puede tomar:

Subproblema 2: Subproblema 1 + (x1 = 0)Subproblema 3: Subproblema 1 + (x1 = 1)

(3.9)

De acuerdo al Cuadro 3.1 se tiene:

Subproblema 2

x1 = 0x2 = 1x3 = 0.67x4 = 0z = 80.67

(3.10)

Subproblema 3

x1 = 1x2 = 0x3 = 0x4 = 0z = 74.00

(3.11)

Se obtiene entonces un primer candidato a optimo: x1 = 1, x2 = 0, x3 = 0, x4 = 0 y z =74.00. Seselecciona entonces como cota: z =74.00. El subproblema 2 no representa una solucion factible parael problema original pero posee un valor de la funcion objetivo superior a la cota, por lo que convieneramificar:

Subproblema 4: Subproblema 1 + (x1 = 0) + (x3 = 0)Subproblema 5: Subproblema 1 + (x1 = 0) + (x3 = 1)

(3.12)

De acuerdo al Cuadro 3.1 se tiene:

Subproblema 4

x1 = 0x2 = 1x3 = 0x4 = 2z = 28.00

(3.13)

Subproblema 5

x1 = 0x2 = 0.8x3 = 1x4 = 0z = 79.40

(3.14)

El subproblema 4 presenta una solucion factible, pero muy por debajo de la cota superior por lo quese puede descartar. El subproblema 5 tiene un asociado un valor optimo de la funcion objetivo superior

20


a la cota pero no cumple todas las condiciones del problema original. Dado los valores obtenidos, sedebe ramificar segun los valores posibles de la variable binaria x2:

Subproblema 6: Subproblema 1 + (x1 = 0) + (x3 = 1) + (x2 = 0)Subproblema 7: Subproblema 1 + (x1 = 0) + (x3 = 1) + (x2 = 1)

(3.15)

Los valores optimos para cada subproblema se obtiene del Cuadro 3.1:

Subproblema 6

x1 = 0x2 = 0x3 = 1z = Imposible

(3.16)

Subproblema 7

x1 = 0x2 = 1x3 = 1x4 = 0.5z = 77.00

(3.17)

En este caso, la solucion del subproblema 7 es factible y es mayor que la cota por lo que setransforma en la nueva cota. Como no existe una rama en la que aparezca una solucion no factiblecon valor de la funcion objetivo mejor que la cota actual, la solucion del subproblema 7 es el optimo.El arbol de ramificacion completo se muestra en la Figura 3.11.

21


Subproblema 1x1 = 0.2x2 = 1x3 = 0x4 = 0z = 82.80

Subproblema 2x1 = 0x2 = 1x3 = 0.67x4 = 0z = 80.67

Subproblema 3x1 = 1x2 = 0x3 = 0x4 = 0z = 74.00

x1 = 0 x1 = 1

Subproblema 4x1 = 0x2 = 1x3 = 0x4 = 2z = 28

Subproblema 5x1 = 0x2 = 0.8x3 = 1x4 = 0z = 79.4

x3 = 0 x3 = 1


Subproblema 7x1 = 0x2 = 1x3 = 1x4 = 0.5z = 77

x2 = 0

x2 = 1

Figura 3.11: Arbol de ramificacion completo Ejemplo 8

22


4. Ejercicios

Ejercicio 1 Considere el problema de distribucion de artıculos desde tres centros productores a doscentros consumidores. Los artıculos pueden ser transportados entre cada centro productor y cada centroconsumidor considerando dos rutas posbiles. La utilizacion de cada ruta tiene asociada un costo fijoque es independiente de la cantidad de artıculos transportados por esa ruta. La siguiente tabla presentalas capacidades de produccion, las demandas estimadas, el costo fijo por la utilizacion de cada ruta yel costo de transporte de un artıculo desde cada centro productor a cada centro consumidor.

Destino1 2

Origen Ruta Costo fijo Costo unitario Costo fijo Costo unitario Oferta

1 a 10 3 12 9 200b 20 2 24 8

2 a 15 5 16 12 400b 25 4 32 10

3 a 30 7 18 16 600b 35 6 36 14

Demanda 300 500

Formule un modelo de programacion lineal mixta que permita determinar la cantidad a trans-portar por cada ruta que minimiza el costo total satisfaciendo todas las demandas. Defina claramentevariables, funcion objetivo y restricciones.

Variables:

xijk: Cantidad transportada entre el origen i y el destino j a traves de la ruta k; ∀ i =1, 2, 3; j = 1, 2; k = a, b.

yijk =

1 si la ruta k entre el origen i y el destino j es utilizada0 si la ruta k entre el origen i y el destino j no es utilizada

∀ i = 1, 2, 3; j = 1, 2; k = a, b.

Funcion objetivo:

Min z = 3× x11a + 2× x11b + 9× x12a + 8× x12b +

5× x21a + 4× x21b + 12× x22a + 10× x22b +

7× x31a + 6× x31b + 16× x32a + 14× x32b +

10× y11a + 20× y11b + 12× y12a + 24× y12b +

15× y21a + 25× y21b + 16× y22a + 32× y22b +

30× y31a + 35× y31b + 18× y32a + 36× y32b

Restricciones:

• Ofertas:

23


x11a + x11b + x12a + x12b ≤ 200

x21a + x21b + x22a + x22b ≤ 400

x31a + x31b + x32a + x32b ≤ 600

• Demandas:

x11a + x11b + x21a + x21b + x31a + x31b = 300

x12a + x12b + x22a + x22b + x32a + x32b = 500

• Activacion de variables:

xijk ≤ M × yijk; ∀ i = 1, 2, 3; j = 1, 2; k = a, b

• Valores posibles para las variables:

xijk ≥ 0; ∀ i = 1, 2, 3; j = 1, 2; k = a, b

yijk ∈ {0, 1}; ∀ i = 1, 2, 3; j = 1, 2; k = a, b

Ejercicio 2 Una fabrica se dedica a la produccion de aceite de cocina a partir de aceites vegetalesy aceites no vegetales. Cada aceite requiere un proceso de refinamiento diferente. La fabrica tienecapacidad para refinar 210 litros de aceite vegetal y 260 litros de aceite no vegetal. Los aceites refinadosson mezclados pudiendo venderse a $180 el litro del producto final. No existe perdida de aceite en losprocesos de refinamiento y mezcla y el costo de estos procesos puede ser ignorado. Existe una restricciontecnica relativa a la calidad del aceite producido: en las unidades en que es medida la calidad, esta debeestar entre 3, 5 y 6, 2. Se asume que las calidades de los aceites originales se combinan linealmente.Existen 2 proveedores de aceite, cada uno ofreciendo dos variedades de aceite vegetal y tres variedadesde aceite no vegetal. El Cuadro 4.1 presenta el costo, en pesos, y la calidad de cada aceite ofrecido porcada proveedor:

Aceitesvegetal 1 vegetal 2 no vegetal 1 no vegetal 2 no vegetal 3

Proveedor 1 Costo 115 128 132 109 114Calidad 8,8 6,2 1,9 4,3 5,1

Proveedor 2 Costo 110 130 125 108 116Calidad 8,5 6,4 1,5 4,2 5,2

Cuadro 4.1: Propiedades de los aceites

Existe un costo fijo por ordenar al proveedor 1 de $2,000 y al proveedor 2 de $2,500, independientede la variedad y cantidad de aceite ordenado.

Finalmente, las siguientes condiciones se imponen sobre la produccion de aceite:

24


el producto final no puede estar compuesto de mas de tres variedades de los aceites originales,

cualquier aceite, si es usado, debe usarse por lo menos 30 litros, y

si algun aceite vegetal es usado debe usarse algun aceite no vegetal.

Formule un modelo de programacion lineal mixta que permita determinar la cantidad de cada tipode aceite que debe comprarse a cada proveedor de manera de maximizar las ganancias satisfaciendotodas las condiciones del problema. Defina claramente variables, funcion objetivo y restricciones.

Variables:

xij : Cantidad de aceite tipo i comprada al proveedor j; ∀i = 1, . . . , 5, ∀j = 1, 2

yij =

{1, si se compra aceite tipo i a proveedor j; ∀i = 1, . . . , 5, ∀j = 1, 20, si no

zj =

{1, si se compra a proveedor j; ∀j = 1, 20, si no

wi =

{1, si se compra aceite tipo i; ∀i = 1, . . . , 50, si no

Funcion objetivo (10%):

Max z = 180×5∑

i=1

2∑

j=1

xij − 2,000× z1 − 2,500× z2

−115× x11 − 128× x21 − 132× x31 − 109× x41 − 114× x51

−110× x12 − 130× x22 − 125× x32 − 108× x42 − 116× x52

Restricciones:

• Capacidad de refinamiento:

x11 + x21 + x12 + x22 ≤ 210

x31 + x41 + x51 + x32 + x42 + x52 ≤ 260

• Calidad:

8, 8x11 + 6, 2x21 + 1, 9x31 + 4, 3x41 + 5, 1x51 + 8, 5x12 + 6, 4x22 + 1, 5x32 + 4, 2x42 + 5, 2x52∑5

i=1

∑2

j=1xij

≥ 3, 5

8, 8x11 + 6, 2x21 + 1, 9x31 + 4, 3x41 + 5, 1x51 + 8, 5x12 + 6, 4x22 + 1, 5x32 + 4, 2x42 + 5, 2x52∑5

i=1

∑2

j=1xij

≤ 6, 2

• Activacion de variables:

xij ≤ M × yij ; ∀i = 1, . . . , 2; j = 1, 2

25


• Si se compra a cada proveedor:

5∑

i=1

yij ≤ 5× zj ; ∀j = 1, 2

• Mınimo a comprar:

xij ≥ 30× yij ; ∀i = 1, . . . , 5; j = 1, 2

• Utilizacion aceite tipo i:

2∑

j=1

yij ≤ 2× wi; ∀i = 1, 5

• Cantidad maxima de aceites originales:

5∑

i=1

wi ≤ 3

• Usar algun aceite no vegetal si se usa algun aceite vegetal:

w1 ≤ w3 + w4 + w5

w2 ≤ w3 + w4 + w5

• Valores posibles para las variables:

xij ≥ 0; ∀i = 1, . . . , 5; j = 1, 2

yij ∈ {0, 1}; ∀i = 1, . . . , 5; j = 1, 2

wi ∈ {0, 1}; ∀i = 1, . . . , 5

zj ∈ {0, 1}; ∀j = 1, 2

Ejercicio 3 Teniendo en cuenta el proximo termino de la guerra, la Organizacion de las NacionesUnidas, ONU, continua estudiando futuras polıticas de integracion para el pueblo de Afganistan. Ex-iste un presupuesto de un millon de dolares para la construccion de un maximo de tres escuelas queatenderıan jovenes talibanes y de la alianza del norte. Los talibanes se distribuyen en tres comunidadesen tanto que la alianza del norte se distribuye en dos comunidades. El Cuadro 4.2 presenta la dis-tancia en kilometros que un estudiante de cada comunidad deberıa recorrer para llegar a cada una delas escuelas, la poblacion estudiantil de cada comunidad, la capacidad maxima proyectada para cadaescuela y el costo de construir cada escuela.

Por razones de integracion, la ONU desea que los talibanes tengan una participacion de entre un25% y un 35% en cada escuela construida. Se requiere que cada escuela construida tenga un mınimode 1,000 estudiantes. Por ultimo, se desea que los talibanes se distribuyan por lo menos en dos escuelas.

Considerando que la ONU desea que todos los estudiantes de una misma comunidad asistan a lamisma escuela, formule un modelo matematico que permita minimizar la distancia total recorrida portodos los estudiantes afganos. Defina claramente variables, funcion objetivo y restricciones.

26


Comunidad Comunidad de la CapacidadEscuela taliban alianza del norte maxima Costo

1 2 3 1 2 [personas] [103US$]

1 20 km 12 km 10 km 4 km 5 km 1.500 1502 15 km 18 km 8 km 6 km 9 km 2.000 2203 25 km 17 km 18 km 7 km 3 km 2.500 3504 10 km 13 km 9 km 9 km 4 km 1.800 1805 14 km 28 km 14 km 8 km 7 km 2.800 400

Poblacion 600 550 500 1.200 1.100estudiantil [personas] [personas] [personas] [personas] [personas]

Cuadro 4.2: Distancias entre comunidades y escuelas.

Ejercicio 4 Considere el siguiente modelo de programacion lineal entera mixta:

Max z = 60x1 + 80x2 + 70x3 − 100y1 − 150y2 − 100y3Sujeto a

13x1 + 18x2 + 15x3 ≤ 800

16x1 + 10x2 + 8x3 ≤ 600

x1 + x2 + x3 ≤ 15

x1 − 10y1 ≤ 0

x2 − 10y2 ≤ 0

x3 − 10y3 ≤ 0

x1, x2, x3 ≥ 0

y1, y2, y3 ∈ {0, 1}

El Cuadro 4.3 presenta la solucion optima para todos los problemas relajados posibles de obtener(un guion en la columna correspondiente a las variables y1, y2 e y3 significa que la variable esta libreen el problema relajado).

y1 y2 y3 x z y1 y2 y3 x z y1 y2 y3 x z

0 0 0 (0, 0, 0,0,0,0) 0 1 0 0 (10, 0, 0,1,0,0) 500 - 0 0 (10,0,0,1,0,0) 5000 0 1 (0, 0,10,0,0,1) 600 1 0 1 ( 5, 0,10,1,0,1) 800 - 0 1 (5,0,10, 1

2,0,1) 850

0 0 - (0, 0,10,0,0,1) 600 1 0 - (10, 0, 5,1,0, 12) 800 - 0 - (5,0,10, 1

2,0,1) 850

0 1 0 (0,10, 0,0,1,0) 650 1 1 0 ( 5,10, 0,1,1,0) 850 - 1 0 (5,10,0, 12,1,0) 900

0 1 1 (0,10, 5,0,1,1) 900 1 1 1 ( 0,10, 5,1,1,1) 800 - 1 1 (0,10,5,0,1,1) 9000 1 - (0,10, 5,0, 1

2) 950 1 1 - ( 5,10, 0,1,1,0) 850 - 1 - (0,10,5,0,1, 1

2) 950

0 - 0 (0,10, 0,0,1,0) 650 1 - 0 ( 5,10, 0,1,1,0) 850 - - 0 (5,10,0, 12,1,0) 900

0 - 1 (0, 5,10,0, 12,1) 925 1 - 1 ( 0, 5,10,1, 1

2,1) 825 - - 1 (0,5,10,0, 1

2,1) 925

0 - - (0,10, 5,0,1, 12) 950 1 - - ( 5,10, 0,1,1,0) 850 - - - (0,10,5,0,1, 1

2) 950

Cuadro 4.3: Solucion de todos los problemas relajados posibles

1. Resuelva este problema aplicando la tecnica de ramificacion y acotamiento. Explıque y justifiqueclaramente cada uno de los pasos.

2. Considerando en general la resolucion de problemas de Programacion Lineal Entera, indıque silas siguientes afirmaciones son verdaderas o falsas justificando claramente:

27


a) La solucion optima a un problema de programacion lineal entrega x1 = 2, 58 y x2 = 1, 32.Si x1 y x2 estan restringidas a tomar valores enteros, entonces x1 = 3 y x2 = 1 es unasolucion factible pero no necesariamente optima.

b) Si la relajacion de programacion lineal de un problema de programacion lineal entera tienesolucion posible entonces el problema de programacion lineal entera tiene solucion posible.

c) La solucion entera optima x1 = 3 y x2 = 5 con z = 150 ha sido encontrada para unproblema de programacion lineal entera. Para su relajacion de programcion lineal, el rangode optimalidad para el coefiente c1 esta entre 15 y 30 con un coeficiente actual de 20. Sic1 aumenta a 21 en el problema de programacion lineal entera, el nuevo valor optimo de lafuncion objetivo sera de 153.

28

Ejemplos vARIOS

Education

Transcript of Ejemplos vARIOS