• Author / Uploaded
• Omar Morales

Citation preview

24-10-2017

Problemas de Programación Entera Investigación de Operaciones

MASETTO GOMEZ RODOLFO MORALES SANDOVAL OMAR ANTONIO PICHARDO CASAS JULIO CESAR

Problemas de Programación Entera

Problema 12 Una compañía planea abrir unas bodegas en cuatro ciudades; Nueva York, Los Ángeles, Chicago y Atlanta. Desde cada bodega se pueden embarcar 100 unidades por semana. El costo fijo por semana por mantener en operación cada bodega es de 400 dólares para Nueva York, 500 dólares para Los Ángeles, 300 dólares para Chicago y 150 dólares para Atlanta. La región 1 del país requiere 80 unidades por semana, la región 2 demanda 70 unidades por semana y la región 3 necesita 40 unidades por semana. Los costos (sin olvidar los costos de producción y embarque) por enviar una unidad desde una planta a una región se señalan en la tabla 1. Se desea cumplir con las demandas semanales a un costo mínimo, precedente y a las restricciones siguientes: 1. Si se abre la bodega de Nueva York, entonces se debe abrir la bodega de Los Ángeles. 2. Es posible abrir a lo más dos bodegas. 3. Se tiene que abrir la bodega de Atlanta o la de Los Ángeles. Formule un PE que se pueda usar para minimizar los costos semanales de cumplir con las demandas.

Tabla 1 (dólares). Desde

Región 1

Región 2

Región 3

Nueva York

20

40

50

Los Ángeles

48

15

26

Chicago

26

35

18

Atlanta

24

50

35

Primero debemos plantear nuestras variables: Sean: 1. 2. 3. 4.

Nueva York Los Ángeles Chicago Atlanta 𝑋𝑖𝑗 : 𝑈𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑒𝑛𝑣𝑖𝑎𝑑𝑎𝑠 𝑑𝑒𝑠𝑑𝑒 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑖 𝑎 𝑙𝑎 𝑟𝑒𝑔𝑖ó𝑛 𝑗. 𝑌𝑖 : 𝑆𝑖 𝑠𝑒 𝑎𝑏𝑟𝑒 𝑜 𝑛𝑜 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑖. 𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0,1} 𝑐𝑜𝑛 𝑖 = 1,2,3,4. & 𝑗 = 1,2,3.

Problemas de Programación Entera Ahora planteamos nuestro problema de Programación Entera: 𝑴𝒊𝒏 𝒁 = 𝟐𝟎𝑿𝟏𝟏 + 𝟒𝟎𝑿𝟏𝟐 + 𝟓𝟎𝑿𝟏𝟑 + 𝟒𝟖𝑿𝟐𝟏 + 𝟏𝟓𝑿𝟐𝟐 + 𝟐𝟔𝑿𝟐𝟑 + 𝟐𝟔𝑿𝟑𝟏 + 𝟑𝟓𝑿𝟑𝟐 + 𝟏𝟖𝑿𝟑𝟑 + 𝟐𝟒𝑿𝟒𝟏 + 𝟓𝟎𝑿𝟒𝟐 + 𝟑𝟓𝑿𝟒𝟑 + 𝟒𝟎𝟎𝒀𝟏 + 𝟓𝟎𝟎𝒀𝟐 + 𝟑𝟎𝟎𝒀𝟑 + 𝟏𝟓𝟎𝒀𝟒 s.a: 𝑌1 + 𝑌2 + 𝑌3 + 𝑌4 ≤ 2 𝑌1 = 𝑌2 𝑌2 + 𝑌4 = 1 𝑋11 + 𝑋12 + 𝑋13 ≤ 100𝑌1 𝑋21 + 𝑋22 + 𝑋23 ≤ 100𝑌2 𝑋31 + 𝑋32 + 𝑋33 ≤ 100𝑌3 𝑋41 + 𝑋42 + 𝑋43 ≤ 100𝑌4 𝑋11 + 𝑋21 + 𝑋31 + 𝑋41 = 80 𝑋12 + 𝑋22 + 𝑋32 + 𝑋42 = 70 𝑋13 + 𝑋23 + 𝑋33 + 𝑋43 = 40 𝑋𝑖𝑗 𝑒𝑛𝑡𝑒𝑟𝑎𝑠 & 𝑌𝑖 𝑏𝑖𝑛𝑎𝑟𝑖𝑎𝑠

𝑝𝑎𝑟𝑎 𝑖 = 1,2,3,4 ; 𝑗 = 1,2,3

Resolviendo con la herramienta Solver de Excel obtenemos los siguientes resultados:

Variable 𝑍∗ 𝑋22 𝑋23 𝑋41 𝑋43 𝑌2 𝑌4 𝑋11 , 𝑋12 , 𝑋13 , 𝑋21 , 𝑋31 , 𝑋32 , 𝑋33 , 𝑋42 , 𝑌1 , 𝑌3

Valor 4750 70 30 80 10 1 1 0

Interpretando los resultados tenemos que la bodega de Los Ángeles y Atlanta deben abrirse, enviando de Atlanta a la región uno y a la región tres, 80 y 10 unidades por semana respectivamente, y de Los Ángeles a la región dos y tres ,70 y 30 unidades por semana respectivamente. Teniendo un costo mínimo 𝑍 ∗ = 4750 dólares.

Problemas de Programación Entera

Problema 33 La firma financiera Boris Milkem posee seis bienes. El precio de venta esperado (en millones de dólares) por cada bien se presenta en la tabla 2. Si el bien 1 se vende en el año 2, la firma recibe 20 millones de dólares. Para conservar un flujo de efectivo regular, Milkem debe vender por lo menos 20 millones de dólares en el año 1, por lo menos 35 millones de dólares en el año 2 y por lo menos 30 millones de dólares en el año 3. Prepare un PE que Milkem pueda usar para determinar cómo maximizar el rendimiento total de los bienes vendidos durante los tres años siguientes. Al poner en marcha este modelo, ¿Cómo se podría aplicar el concepto de horizonte de planeación rodante?

Tabla 2 (millones de dólares). Bien

Vendido en Año 1

Año 2

Año 3

1

15

20

24

2

16

18

21

3 4

22 10

30 20

36 30

5

17

19

22

6

19

25

29

Primero debemos plantear nuestras variables: 𝑋𝑖𝑗 : 𝑆𝑖 𝑒𝑙 𝑏𝑖𝑒𝑛 𝑖 𝑑𝑒𝑏𝑒 𝑠𝑒𝑟 𝑣𝑒𝑛𝑑𝑖𝑑𝑜 𝑒𝑛 𝑒𝑙 𝑎ñ𝑜 𝑗. 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0,1} 𝑐𝑜𝑛 𝑖 = 1,2,3,4,5,6. & 𝑗 = 1,2,3. Ahora planteamos nuestro problema de Programación Entera. 𝑴𝒂𝒙 𝒁 = 𝟏𝟓𝑿𝟏𝟏 + 𝟐𝟎𝑿𝟏𝟐 + 𝟐𝟒𝑿𝟏𝟑 + 𝟏𝟔𝑿𝟐𝟏 + 𝟏𝟖𝑿𝟐𝟐 + 𝟐𝟏𝑿𝟐𝟑 + 𝟐𝟐𝑿𝟑𝟏 + 𝟑𝟎𝑿𝟑𝟐 + 𝟑𝟔𝑿𝟑𝟑 + 𝟏𝟎𝑿𝟒𝟏 + 𝟐𝟎𝑿𝟒𝟐 + 𝟑𝟎𝑿𝟒𝟑 + 𝟏𝟕𝑿𝟓𝟏 + 𝟏𝟗𝑿𝟓𝟐 + 𝟐𝟐𝑿𝟓𝟑 + 𝟏𝟗𝑿𝟔𝟏 + 𝟐𝟓𝑿𝟔𝟐 + 𝟐𝟗𝑿𝟔𝟑 s.a: 15𝑋11 + 16𝑋21 + 22𝑋31 + 10𝑋41 + 17𝑋51 + 19𝑋61 ≥ 20 20𝑋12 + 18𝑋22 + 30𝑋32 + 20𝑋42 + 19𝑋52 + 25𝑋62 ≥ 35 24𝑋13 + 21𝑋23 + 36𝑋33 + 30𝑋43 + 22𝑋53 + 29𝑋63 ≥ 30 𝑋11 + 𝑋12 + 𝑋13 = 1 𝑋21 + 𝑋22 + 𝑋23 = 1

Problemas de Programación Entera 𝑋31 + 𝑋32 + 𝑋33 = 1 𝑋41 + 𝑋42 + 𝑋43 = 1 𝑋51 + 𝑋52 + 𝑋53 = 1 𝑋61 + 𝑋62 + 𝑋63 = 1 𝑋𝑖𝑗 𝑏𝑖𝑛𝑎𝑟𝑖𝑎𝑠

𝑝𝑎𝑟𝑎 𝑖 = 1,2,3,4,5,6 ; 𝑗 = 1,2,3

Resolviendo con la herramienta Solver de Excel obtenemos los siguientes resultados:

Variable 𝑍∗ 𝑋12 𝑋21 𝑋33 𝑋43 𝑋51 𝑋62 𝑋11 , 𝑋13 , 𝑋22 , 𝑋23 , 𝑋31 , 𝑋32 , 𝑋41 , 𝑋42 , 𝑋52 , 𝑋53 , 𝑋61 , 𝑋63

Valor 144 1 1 1 1 1 1 0

Interpretando los resultados tenemos que el bien uno se debe vender en el año 2, el bien dos en el año 1, el bien tres en el año 3, el bien cuatro en el año 3, el bien cinco en el año 1 y el bien seis en el año 2, con una 𝒁∗ = 144 millones de dólares, la cual es el máximo rendimiento total de los bienes y conservando un flujo de efectivo regular, las cuales fueron nuestras restricciones.

Problema 35 Una planta de generación de energía eléctrica tiene tres calderas. Si una caldera dada está en operación es posible utilizarla para generar una cierta cantidad de vapor (en toneladas) entre el mínimo y el máximo dado en la tabla 3. Se proporciona también el costo de producción de una tonelada de vapor en cada caldera. El vapor proveniente de las calderas se usa para generar energía eléctrica en las tres turbinas. Si operan, cada turbina procesa una cantidad de vapor (en toneladas) entre el mínimo y el máximo que se da en la tabla 4. Se proporciona, asimismo, el costo por procesar una tonelada de vapor y la energía producida por cada turbina. Plantee un PE con el que se pueda minimizar el costo de producir 8000 kwh de energía eléctrica.

Problemas de Programación Entera Tabla 3 (en toneladas). Caldera

Vapor mínimo

Vapor máximo

1 2 3

500 300 400

1000 900 800

Costo/tonelada (dólares) 10 8 6

Tabla 4 (en toneladas). Turbina

Mínimo

Máximo

1 2 3

300 500 600

600 800 900

Kwh por tonelada de vapor 4 5 6

Primero debemos plantear nuestras variables: 𝑋𝑖 : 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑣𝑎𝑝𝑜𝑟 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑜 𝑝𝑜𝑟 𝑙𝑎 𝑐𝑎𝑙𝑑𝑒𝑟𝑎 𝑖 𝑌𝑖 : 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑣𝑎𝑝𝑜𝑟 𝑝𝑟𝑜𝑐𝑒𝑠𝑎𝑑𝑜 𝑝𝑜𝑟 𝑙𝑎 𝑡𝑢𝑟𝑏𝑖𝑛𝑎 𝑗 𝑍𝑖 : 𝑆𝑖 𝑙𝑎 𝑐𝑎𝑙𝑑𝑒𝑟𝑎 𝑖 𝑒𝑠𝑡á 𝑒𝑛 𝑜𝑝𝑒𝑟𝑎𝑐𝑖ó𝑛. 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0, 1} 𝑊𝑖 : 𝑆𝑖 𝑙𝑎 𝑡𝑢𝑟𝑏𝑖𝑛𝑎 𝑖 𝑒𝑠𝑡á 𝑒𝑛 𝑜𝑝𝑒𝑟𝑎𝑐𝑖ó𝑛. 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0, 1} 𝑐𝑜𝑛 𝑖 = 1,2,3. & 𝑗 = 1,2,3. Ahora planteamos nuestro problema de Programación Entera: 𝑴𝒂𝒙 𝒁 = 𝟏𝟎𝑿𝟏 + 𝟖𝑿𝟐 + 𝟔𝑿𝟑 + 𝟐𝒀𝟏 + 𝟏𝟖𝒀𝟐 + 𝟒𝑿𝟑 𝑠. 𝑎: 500𝑍1 ≤ 𝑋1 ≤ 1000𝑍1 300𝑍2 ≤ 𝑋2 ≤ 900𝑍2 400𝑍3 ≤ 𝑋3 ≤ 800𝑍3 300𝑊1 ≤ 𝑌1 ≤ 600𝑊1 500𝑊2 ≤ 𝑌2 ≤ 800𝑊2 600𝑊3 ≤ 𝑌3 ≤ 900𝑊3 𝑋1 + 𝑋2 + 𝑋3 = 𝑌1 + 𝑌2 + 𝑌3 4𝑌1 + 5𝑌2 + 6𝑌3 = 8000

Costo de proceso por (dólares) 2 3 4

Problemas de Programación Entera 𝑋𝑖 , 𝑌𝑖 𝑒𝑛𝑡𝑒𝑟𝑎𝑠 & 𝑍𝑖 , 𝑊𝑖 𝑏𝑖𝑛𝑎𝑟𝑖𝑎𝑠

𝑝𝑎𝑟𝑎 𝑖, 𝑗 = 1 ,2, 3

Resolviendo con la herramienta Solver de Excel obtenemos los siguientes resultados:

Variable 𝑍∗ 𝑋1 𝑋3 𝑌2 𝑌3 𝑊2 𝑊3 𝑍1 𝑍3 𝑋2 , 𝑌1 , 𝑊1 , 𝑍2

Valor 2840 1000 420 520 900 1 1 1 1 0

Interpretando los resultados tenemos que en la caldera 1 se produce una cantidad de vapor de 1000 toneladas, mientras que en la 3 se producen 420. En la turbina 2 se procesan 520 toneladas de vapor, mientras que en la 3 se procesan 900. En la caldera 2 y en la turbina 1 no se realiza producción ni procesamiento de vapor. Con los resultados anteriores, tenemos que el valor óptimo 𝒁∗ que minimiza el costo total de producir 8000 Khw de energía eléctrica es de 2840 dólares.

Problema 36 Una compañía de Ohio, Clevcinn, está constituida por tres subsidiarias. Cada una de ellas tiene su respectiva nómina promedio, fondo de reserva para desempleo y nómina estimada que se da en la tabla 5. (Todos los valores están en millones de dólares.) Cualquier empleador en el estado de Ohio cuya relación nómina de reserva/nómina promedio es menor a 1 debe pagar 20% de su nómina estimada en primas de seguro por desempleo o 10% si la relación es por lo menos de 1. Clevcinn puede unir sus subsidiarias y considerarlas como empleadores separados. Por ejemplo, si la subsidiaria 2 y la 3 se unen, deben pagar entonces 20% de su nómina combinada en primas de seguro por desempleo. Formule un PE con el que se pueda determinar qué subsidiarias deben unirse.

Tabla 5 (en millones de dólares). Subsidiaria 1 2 3

Nómina promedio 300 600 800

Reserva 400 510 600

Nómina estimada 350 400 500

Problemas de Programación Entera Para plantear el problema primeramente definimos las variables sobre las que se va a trabajar. 𝑥𝑖𝑗 : 𝑈𝑛𝑖𝑟 𝑙𝑎 𝑠𝑢𝑏𝑠𝑖𝑑𝑖𝑎𝑟𝑖𝑎 𝑖 𝑐𝑜𝑛 𝑙𝑎 𝑗. 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0, 1} 𝑐𝑜𝑛 𝑖 = 1,2,3. & 𝑗 = 1,2,3. Además, notamos que cuando 𝑖 = 𝑗 significa no unir esa subsidiaria con otra, considerarla por separado, por otra parte 𝑥𝑖𝑗 = 𝑥𝑗𝑖 y tenemos otro caso especial 𝑥123 que implica unir las 3 subsidiarias. Entonces para obtener la función objetivo que llamaremos 𝑍 debemos considerar cada unión posible a partir de los datos de la tabla para obtener lo que se debe pagar de la nómina estimada en cada caso. 𝑍 = 0.1 ∗ 350𝑥11 + 0.2 ∗ 400𝑥22 + 0.2 ∗ 500𝑥33 + 0.1 ∗ 750𝑥12 + 0.2 ∗ 850𝑥13 + 0.2 ∗ 900𝑥23 + 0.2 ∗ 1250𝑥123 𝑍 = 35𝑥11 + 80𝑥22 + 100𝑥33 + 75𝑥12 + 170𝑥13 + 180𝑥23 + 250𝑥123 Otro detalle que considerar es cuando se combina alguna subsidiaria se imposibilitan las demás uniones, lo cual formulara nuestras restricciones. Por lo tanto, el problema de Programación Entera queda como sigue: 𝑴𝒊𝒏 𝒁 = 𝟑𝟓𝒙𝟏𝟏 + 𝟖𝟎𝒙𝟐𝟐 + 𝟏𝟎𝟎𝒙𝟑𝟑 + 𝟕𝟓𝒙𝟏𝟐 + 𝟏𝟕𝟎𝒙𝟏𝟑 + 𝟏𝟖𝟎𝒙𝟐𝟑 + 𝟐𝟓𝟎𝒙𝟏𝟐𝟑 𝑠. 𝑎: 𝑥11 + 𝑥12 + 𝑥13 + 𝑥123 = 1 𝑥12 + 𝑥22 + 𝑥23 + 𝑥123 = 1 𝑥13 + 𝑥23 + 𝑥33 + 𝑥123 = 1 𝑥𝑖𝑗 & 𝑥123 𝑏𝑖𝑛𝑎𝑟𝑖𝑎𝑠

𝑝𝑎𝑟𝑎 𝑖, 𝑗 = 1,2,3

Resolviendo con la herramienta Solver de Excel obtenemos los siguientes resultados:

Variable 𝑍∗ 𝑥12 𝑥33 𝑥11 , 𝑥13 , 𝑥22 , 𝑥23 , 𝑥123

Valor 175 1 1 0

Al interpretar el resultado obtenido observamos que se deben unir la subsidiaria 1 con la 2 y la 3 se debe de tomar por separado ya que esto nos otorga el pago mínimo para la compañía que es de 𝒁∗ = 175.

Problemas de Programación Entera

Problema 39 Huntco elabora salsa de tomate con 5 plantas distintas. La capacidad (en toneladas) de cada planta se encuentra en la tabla 6. La salsa de tomate se almacena en una de 3 bodegas. El costo por tonelada (en cientos de dólares) por producir salsa de tomate en cada planta y embarcarla a cada bodega se proporciona en la tabla 7. Huntco tiene 4 cliente. El costo de embarcar una tonelada de salsa después de cada bodega hasta el lugar del cliente es como se indica en la tabla 8. Cada cliente debe recibir la cantidad (en toneladas) de salsa que se presentan en la tabla 9.

Tabla 6 (en toneladas).

Toneladas

1 300

Planta 3 300

2 200

4 200

5 400

Tabla 7 (en cientos de dólares). Desde Planta 1 Planta 2 Planta 3 Planta 4 Planta 5

Hasta Bodega 2 10 5 6 6 6

Bodega 1 8 7 8 5 7

Bodega 3 12 7 5 7 5

Tabla 8 (en cientos de dólares). Hasta Desde Bodega 1 Bodega 2 Bodega 3

Cliente 1 40 70 80

Cliente 2 80 70 30

Cliente 3 90 60 50

Cliente 4 50 80 60

3 150

4 250

Tabla 9 (en toneladas). Cliente Demanda

1 200

2 300

Problemas de Programación Entera a) Formule un problema de transporte balanceado cuya solución indique la manera de minimizar el costo de cumplir con las demandas de los clientes. b) Modifique este problema si estas son demandas anuales y hay un costo anual fijo por la operación de cada planta y bodega. Estos costos (en miles) se dan en la tabla 10.

Tabla 10 (en miles de dólares). Instalación Planta 1 Planta 2 Planta 3 Planta 4 Planta 5 Bodega 1 Bodega 2 Bodega 3

Costo fijo anual (en miles de dólares) 35 45 40 42 40 30 40 30

Ya que contamos con herramientas lo suficientemente poderosas para resolver el problema con un planteamiento más simplificado se omitirá el balancear el problema por ser algo innecesario al ser capaces de obtener una respuesta optima más precisa de una manera más eficiente. Ahora bien, procedemos a identificar nuestras variables de interés. 𝑥𝑖𝑗 : 𝑇𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑟 𝑑𝑒 𝑙𝑎 𝑝𝑙𝑎𝑛𝑡𝑎 𝑖 𝑎 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑗. 𝑦𝑗𝑘 : 𝑇𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑟 𝑑𝑒 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑗 𝑎𝑙 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑘. 𝑐𝑜𝑛 𝑖 = 1,2,3,4,5. ; 𝑗 = 1,2,3. & 𝑘 = 1,2,3,4. 𝑴𝒊𝒏 𝒁 = 𝟖𝒙𝟏𝟏 + 𝟏𝟎𝒙𝟏𝟐 + 𝟏𝟐𝒙𝟏𝟑 + 𝟕𝒙𝟐𝟏 + 𝟓𝒙𝟐𝟐 + 𝟕𝒙𝟐𝟑 + 𝟖𝒙𝟑𝟏 + 𝟔𝒙𝟑𝟐 + 𝟓𝒙𝟑𝟑 + 𝟓𝒙𝟒𝟏 + 𝟔𝒙𝟒𝟐 + 𝟕𝒙𝟒𝟑 + 𝟕𝒙𝟓𝟏 + 𝟔𝒙𝟓𝟐 + 𝟓𝒙𝟓𝟑 + 𝟖𝟎𝒚𝟏𝟐 + 𝟗𝟎𝒚𝟏𝟑 + 𝟓𝟎𝒚𝟏𝟒 + 𝟕𝟎𝒚𝟐𝟏 + 𝟕𝟎𝒚𝟐𝟐 + 𝟔𝟎𝒚𝟐𝟑 + 𝟖𝟎𝒚𝟐𝟒 + 𝟖𝟎𝒚𝟑𝟏 + 𝟑𝟎𝒚𝟑𝟐 + 𝟓𝟎𝒚𝟑𝟑 + 𝟔𝟎𝒚𝟑𝟒 𝑠. 𝑎: 𝑥11 + 𝑥12 + 𝑥13 ≤ 300 𝑥21 + 𝑥22 + 𝑥23 ≤ 200 𝑥31 + 𝑥32 + 𝑥33 ≤ 300 𝑥41 + 𝑥42 + 𝑥43 ≤ 200 𝑥51 + 𝑥52 + 𝑥53 ≤ 400 𝑦11 + 𝑦21 + 𝑦31 = 200

Problemas de Programación Entera 𝑦12 + 𝑦22 + 𝑦32 = 300 𝑦13 + 𝑦23 + 𝑦33 = 150 𝑦14 + 𝑦24 + 𝑦34 = 250 𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 + 𝑥51 = 𝑦11 + 𝑦12 + 𝑦13 + 𝑦14 𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 + 𝑥52 = 𝑦21 + 𝑦22 + 𝑦23 + 𝑦24 𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 + 𝑥53 = 𝑦31 + 𝑦32 + 𝑦33 + 𝑦34 𝑥𝑖𝑗 𝑦𝑗𝑘 𝑒𝑛𝑡𝑒𝑟𝑎𝑠

𝑝𝑎𝑟𝑎 𝑖 = 1,2,3,4,5 ; 𝑗 = 1,2,3 ; 𝑘 = 1,2,3,4

Resolvemos mediante el Solver de Excel obteniendo los siguientes resultados:

Variable 𝑍∗ 𝑥33 𝑥41 𝑥51 𝑥53 𝑦11 𝑦14 𝑦32 𝑦33 𝑥11 , 𝑥12 , 𝑥13 , 𝑥21 , 𝑥22 , 𝑥23 , 𝑥31 , 𝑥32 , 𝑥42 , 𝑥43 , 𝑥52 𝑦12 , 𝑦13 , 𝑦21 , 𝑦22 , 𝑦23 , 𝑦24 , 𝑦31 , 𝑦34

Valor 42,000 300 200 250 150 200 250 300 150 0 0

A partir de lo cual hallamos las rutas de transporte de mercancías optimas, de la planta 3 a la bodega 3 se deben enviar 300 toneladas, de la planta 4 a la bodega 1 enviar 200 toneladas, de la planta 5 a la bodega 1 otras 250 toneladas y de la planta 5 a la bodega 3 enviar 150 toneladas. De las bodegas a los clientes lo mejor es de la bodega 1 a los clientes 1 y 4 la cantidad demandada, y de la bodega 3 a los clientes 2 y 3 la cantidad demandada. Lo cual nos da un costo mínimo de 𝑍 ∗ = 42,000 cientos de dólares. Para el inciso b) se deben agregar unas restricciones y variables binarias para ajustar los costos de uso de planta y de bodega. 𝑧𝑖 : 𝐿𝑎 𝑝𝑙𝑎𝑛𝑡𝑎 𝑖 𝑠𝑒 𝑒𝑛𝑐𝑢𝑒𝑛𝑡𝑟𝑎 𝑎𝑐𝑡𝑖𝑣𝑎. 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0, 1} 𝑤𝑗 : 𝐿𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑗 𝑠𝑒 𝑑𝑒𝑏𝑒 𝑢𝑠𝑎𝑟. 𝐵𝑖𝑛𝑎𝑟𝑖𝑎 = {0, 1} 𝑐𝑜𝑛 𝑖 = 1,2,3,4,5. & 𝑗 = 1,2,3.

Problemas de Programación Entera 𝑴𝒊𝒏 𝒁 = 𝟖𝒙𝟏𝟏 + 𝟏𝟎𝒙𝟏𝟐 + 𝟏𝟐𝒙𝟏𝟑 + 𝟕𝒙𝟐𝟏 + 𝟓𝒙𝟐𝟐 + 𝟕𝒙𝟐𝟑 + 𝟖𝒙𝟑𝟏 + 𝟔𝒙𝟑𝟐 + 𝟓𝒙𝟑𝟑 + 𝟓𝒙𝟒𝟏 + 𝟔𝒙𝟒𝟐 + 𝟕𝒙𝟒𝟑 + 𝟕𝒙𝟓𝟏 + 𝟔𝒙𝟓𝟐 + 𝟓𝒙𝟓𝟑 + 𝟖𝟎𝒚𝟏𝟐 + 𝟗𝟎𝒚𝟏𝟑 + 𝟓𝟎𝒚𝟏𝟒 + 𝟕𝟎𝒚𝟐𝟏 + 𝟕𝟎𝒚𝟐𝟐 + 𝟔𝟎𝒚𝟐𝟑 + 𝟖𝟎𝒚𝟐𝟒 + 𝟖𝟎𝒚𝟑𝟏 + 𝟑𝟎𝒚𝟑𝟐 + 𝟓𝟎𝒚𝟑𝟑 + 𝟔𝟎𝒚𝟑𝟒 + 𝟑𝟓𝟎𝒛𝟏 + 𝟒𝟓𝟎𝒛𝟐 + 𝟒𝟎𝟎𝒛𝟑 + 𝟒𝟐𝟎𝒛𝟒 + 𝟒𝟎𝟎𝒛𝟓 + 𝟑𝟎𝟎𝒘𝟏 + 𝟒𝟎𝟎𝒘𝟐 + 𝟑𝟎𝟎𝒘𝟑 𝑠. 𝑎: 𝑥11 + 𝑥12 + 𝑥13 ≤ 300𝑧1 𝑥21 + 𝑥22 + 𝑥23 ≤ 200𝑧2 𝑥31 + 𝑥32 + 𝑥33 ≤ 300𝑧3 𝑥41 + 𝑥42 + 𝑥43 ≤ 200𝑧4 𝑥51 + 𝑥52 + 𝑥53 ≤ 400𝑧5 𝑦11 + 𝑦21 + 𝑦31 = 200 𝑦12 + 𝑦22 + 𝑦32 = 300 𝑦13 + 𝑦23 + 𝑦33 = 150 𝑦14 + 𝑦24 + 𝑦34 = 250 𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 + 𝑥51 = 𝑦11 + 𝑦12 + 𝑦13 + 𝑦14 𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 + 𝑥52 = 𝑦21 + 𝑦22 + 𝑦23 + 𝑦24 𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 + 𝑥53 = 𝑦31 + 𝑦32 + 𝑦33 + 𝑦34 𝑦11 + 𝑦12 + 𝑦13 + 𝑦14 ≤ 900𝑤1 𝑦21 + 𝑦22 + 𝑦23 + 𝑦24 ≤ 900𝑤2 𝑦31 + 𝑦32 + 𝑦33 + 𝑦34 ≤ 900𝑤3 𝑥𝑖𝑗 𝑦𝑗𝑘 𝑒𝑛𝑡𝑒𝑟𝑎𝑠 & 𝑧𝑖 𝑤𝑗 𝑏𝑖𝑛𝑎𝑟𝑖𝑎𝑠

𝑝𝑎𝑟𝑎 𝑖 = 1,2,3,4,5 ; 𝑗 = 1,2,3 ; 𝑘 = 1,2,3,4

Resolvemos mediante el Solver de Excel obteniendo los siguientes resultados:

Variable 𝑍∗ 𝑥33 𝑥41 𝑥51 𝑥53 𝑦11 𝑦14

Valor 43,820 300 200 250 150 200 250

Problemas de Programación Entera 𝑦32 𝑦33 𝑧3 𝑧4 𝑧5 𝑤1 𝑤3 𝑥11 , 𝑥12 , 𝑥13 , 𝑥21 , 𝑥22 , 𝑥23 , 𝑥31 , 𝑥32 , 𝑥42 , 𝑥43 , 𝑥52 𝑦12 , 𝑦13 , 𝑦21 , 𝑦22 , 𝑦23 , 𝑦24 , 𝑦31 , 𝑦34 𝑧1 , 𝑧2 , 𝑤2

300 150 1 1 1 1 1 0 0 0

De lo cual rápidamente notamos que la respuesta son las mismas rutas que en el inciso anterior, escribiendo la interpretación en este caso tenemos: Las rutas de transporte de mercancías optimas, de la planta 3 a la bodega 3 se deben enviar 300 toneladas, de la planta 4 a la bodega 1 enviar 200 toneladas, de la planta 5 a la bodega 1 otras 250 toneladas y de la planta 5 a la bodega 3 enviar 150 toneladas. De las bodegas a los clientes lo mejor es de la bodega 1 a los clientes 1 y 4 la cantidad demandada, y de la bodega 3 a los clientes 2 y 3 la cantidad demandada. Así necesitamos activas las plantas 3, 4 y 5 además de utilizar las bodegas 1 y 3. Lo cual nos produce un costo mínimo de 𝑍 ∗ = 43,820 cientos de dólares.