Investigación Operativa 1.

Capítulo 6. Programación Entera. 1

6.2.5 FUNCIONES LINEALES POR SEGMENTOS

Problema 8A Una empresa fabrica tres productos A, B y C, los cuales requieren de materia prima y espacio de almacenamiento. La información técnica se presenta a continuación:

Recurso Producto A Producto B Producto C Disponibilidad

Materia prima (libras) 4 3 1.5 1600

Espacio (pies cúbicos) 2 3 2 1200

El producto A se vende a 25 soles y el producto B a 20 soles, sin embargo, sus costos de producción dependen de la cantidad producida de acuerdo a las cantidades que se muestran en la siguiente tabla:

Producto A Costo unitario

(S/.)

Producto B Costo unitario

(S/.)

0 – 80 10 0 – 95 9

81 – 150 11 96 – 130 10

151 – 200 13 131 – 180 11

201 – 300 15 181 – 240 13

La utilidad del producto C es de 4 soles y se deben producir al menos 25 unidades.

Formule un modelo de programación lineal entera adecuado a esta situación.

Variables de decisión A: unidades a producir del producto A. B: unidades a producir del producto B. C: unidades a producir del producto C. Restricciones 4A + 3B + 1.5C ≤ 1600 2A + 3B + 2C ≤ 1200 A = A1 + A2 + A3 + A4 A1 ≤ 80 A2 ≤ 70 A3 ≤ 50 A4 ≤ 100

B = B1 + B2 + B3 + B4 B1 ≤ 95 B2 ≤ 35 B3 ≤ 50 B4 ≤ 60 C ≥ 25

Investigación Operativa 1.

Capítulo 6. Programación Entera. 2

Función objetivo

Max z = (25 - 10)A1 + (25 - 11)A2 + (25 - 13)A3 + (25 - 15)A4 + (20 - 9)B1 + (20 - 10)B2 + (20 - 11)B3 + (20 - 13)B4 + 4C Max z = 15A1 + 14A2 + 12A3 + 10A4 + 11B1 + 10B2 + 9B3 + 7B4 + 4C

Rango de existencia A ≥ 0 ; B ≥ 0 ; C ≥ 0 A1 ≥ 0 ; A2 ≥ 0 ; A3 ≥ 0 ; A4 ≥ 0 ; B1 ≥ 0 ; B2 ≥ 0 ; B3 ≥ 0 ; B4 ≥ 0

La solución óptima del modelo es:

Problema 8B Si ahora los costos de producción dependen de la cantidad producida de acuerdo a las cantidades que se muestran en la siguiente tabla:

Producto A Costo unitario

(S/.)

Producto B Costo unitario

(S/.)

0 – 80 10 0 – 95 13

81 – 150 11 96 – 130 11

151 – 200 13 131 – 180 10

201 – 300 15 181 – 240 9

Y las demás condiciones se mantienen iguales.

Formule un modelo de programación lineal entera adecuado a esta situación.

Modelo incorrecto Variables de decisión A: unidades a producir del producto A. B: unidades a producir del producto B. C: unidades a producir del producto C.

Restricciones 4A + 3B + 1.5C ≤ 1600 2A + 3B + 2C ≤ 1200 A = A1 + A2 + A3 + A4 A1 ≤ 80 A2 ≤ 70 A3 ≤ 50 A4 ≤ 100

Investigación Operativa 1.

Capítulo 6. Programación Entera. 3

B = B1 + B2 + B3 + B4 B1 ≤ 95 B2 ≤ 35 B3 ≤ 50 B4 ≤ 60 C ≥ 25 Función objetivo

Max z = (25 - 10)A1 + (25 - 11)A2 + (25 - 13)A3 + (25 - 15)A4 + (20 - 13)B1 + (20 - 11)B2 + (20 - 10)B3 + (20 - 9)B4 + 4C Max z = 15A1 + 14A2 + 12A3 + 10A4 + 7B1 + 9B2 + 10B3 + 11B4 + 4C

Rango de existencia A ≥ 0 ; B ≥ 0 ; C ≥ 0 A1 ≥ 0 ; A2 ≥ 0 ; A3 ≥ 0 ; A4 ≥ 0 ; B1 ≥ 0 ; B2 ≥ 0 ; B3 ≥ 0 ; B4 ≥ 0 La solución óptima de este modelo es, discuta los resultados y emita una conclusión.

Modelo correcto El modelo general es (definición tomada y adaptada de Winston (2005)): Sea f(x) una función lineal por segmentos con puntos de quiebre b1,b2,b3,…bn como se muestra en la gráfica siguiente:

f(X)

b2 b3 b4 …. bn X

f(b4)

f(b3)

f(b2)

(b1 ; f(b1))

Investigación Operativa 1.

Capítulo 6. Programación Entera. 4

Sea X tal que bk ≤ X ≤ bk+1 para k=1,2…n-1. Para algún Zk tal que 0 ≤ Zk ≤ 1; X se

puede expresar así: X = Zkbk + (1 - Zk)bk+1. Como f(x) es lineal para bk ≤ X ≤ bk+1 se

puede escribir:

f(X) = Zkf(bk) + (1 - Zk)f(bk+1) Para formular la función lineal por segmentos en el programa lineal entero mixto sigamos los siguientes pasos: Paso 1

En la función objetivo definamos a f(X) como:

f(X) = Z1f(b1) + Z2f(b2) + Z3f(b3) + … + Znf(bn) Paso 2 Agregamos en las restricciones:

Z1 ≤ Y1

Z2 ≤ Y1 + Y2

Z3 ≤ Y2 + Y3

.

.

.

Zn-1 ≤ Yn-2 + Yn-1

Zn ≤ Yn-1

Y1 + Y2 + Y3 + … + Yn-1 = 1

Z1 + Z2 + Z3 + … + Zn = 1

X = Z1b1 + Z2b2 + Z3b3 + … + Znbn

Paso 3 Agregamos en el rango de existencia

Y = 0 o 1 Z ≥ 0 Apliquemos esta definición al problema 8B, primero es necesario los siguientes cálculos:

Investigación Operativa 1.

Capítulo 6. Programación Entera. 5

Tramo 1: 7B ; 0 ≤ B ≤ 95

Tramo 2: 9B - 190 ; 95 ≤ B ≤ 130

Tramo 3: 10B - 320 ; 130 ≤ B ≤ 180

Tramo 4: 11B -500 ; 180 ≤ B ≤ 240

f(B) = Utilidad(B) =

Y el gráfico de la utilidad(B) es el siguiente:

MCu=20-9=11

MCu=20-10=10

MCu=20-11=9

MCu=20-13=7

(0 ; 0) 95 130 240 B180

Utilidad(B)

f(240) = 2120

f(180) = 1620

f(130) = 980

f(95) = 665

Y el modelo correcto es: Variables de decisión A: unidades a producir del producto A. B: unidades a producir del producto B. C: unidades a producir del producto C.

Función objetivo

Max z = 15A1 + 14A2 + 12A3 + 10A4 + 0Z1 + 665Z2 + 980Z3 + 1480Z4 + 2140Z5 + 4C

Restricciones 4A + 3B + 1.5C ≤ 1600 2A + 3B + 2C ≤ 1200

Investigación Operativa 1.

Capítulo 6. Programación Entera. 6

A = A1 + A2 + A3 + A4 A1 ≤ 80 A2 ≤ 70 A3 ≤ 50 A4 ≤ 100 Restricciones para el producto B cuyo costo es una función lineal cóncava por partes: Z1 ≤ Y1 Z2 ≤ Y1 + Y2 Z3 ≤ Y2 + Y3 Z4 ≤ Y3 + Y4 Z5 ≤ Y4 Y1 + Y2 + Y3 + Y4 = 1 Z1 + Z2 + Z3 + Z4 + Z5 = 1 B = 0Z1 + 95Z2 + 130Z3 + 180Z4 + 240Z5 Rango de existencia Ai ≥ 0 ; i =1 , 2 , 3 , 4 B ≥ 0 ; C ≥ 0 Yi = 0 ó 1 ; j = 1 , 2 , 3 , 4

Zi ≥ 0; j = 1 , 2 , 3 , 4 , 5 Observe en el modelo que no fue necesario diseñar para la utilidad de A un modelo similar al que se diseñó para la utilidad de B porque la utilidad es decreciente por tramos: 15>14>12>10, y a su vez, como las variables A1, A2, A3 y A4 tienen los mismo coeficientes en las restricciones todo hace pensar que el algoritmo preferirá primero A1, luego A2, luego y finalmente A4 orden dado por la utilidad decreciente de los tramos. Sin embargo, sí podríamos plantear para la utilidad A un diseño similar a la de la utilidad B y obtendrá los mismos resultados. ¡Inténtelo! Finalmente, la solución óptima del modelo es: LAST INTEGER SOLUTION IS THE BEST FOUND

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

5128.000

VARIABLE VALUE

Y1 0.000000

Y2 0.000000

Y3 0.000000

Y4 1.000000

A1 80.000000

A2 70.000000

A3 50.000000

A4 8.000000

Z1 0.000000

Z2 0.000000

Z3 0.000000

Z4 0.000000

Investigación Operativa 1.

Capítulo 6. Programación Entera. 7

Z5 1.000000

C 32.000000

A 208.000000

B 240.000000

ROW SLACK OR SURPLUS

2) 0.000000

3) 0.000000

4) 0.000000

5) 0.000000

6) 0.000000

7) 0.000000

8) 92.000000

9) 0.000000

10) 0.000000

11) 0.000000

12) 1.000000

13) 0.000000

14) 0.000000

15) 0.000000

16) 0.000000

NO. ITERATIONS= 18

BRANCHES= 0 DETERM.= 1.000E 0

6.2.1 SECUENCIACIÓN DE MÁQUINAS

Problema 9 Una empresa fabricante de tres tipos de productos tiene cuatro máquinas disponibles para la manufactura de éstos. La secuencia de los procesos de los tres productos en las máquinas es la siguiente: el producto 1 empieza en la máquina 1, luego pasa a la máquina 3 y finalmente a la máquina 4. El producto 2 empieza en la máquina 1, pasa a la máquina 2 y termina en la máquina 3. El producto 3 empieza en la máquina 2 y culmina en la máquina 4. La máquina cuando empieza a procesar un producto lo hace hasta el final, asimismo, cada máquina procesa un producto a la vez. La tabla siguiente muestra los tiempos requeridos por cada tipo de producto en cada máquina. Por especificaciones técnicas, cada producto tiene un tiempo máximo de procesamiento.

Tiempo requerido en la

máquina 1 (minutos)

Tiempo requerido en la

máquina 2 (minutos)

Tiempo requerido en la

máquina 3 (minutos)

Tiempo requerido en la

máquina 4 (minutos)

Tiempo máximo de

procesamiento (minutos por

unidad)

Producto 1 4 - 3 5 18

Producto 2 2 6 1 - 15

Producto 3 - 7 - 4 14

Plantee un problema de PE que indique las secuencias de procesamiento de los productos en las máquinas y que permita completar la elaboración de éstos en el menor tiempo posible.

Investigación Operativa 1.

Capítulo 6. Programación Entera. 8

Solución: La secuencia de procesamiento por producto es la siguiente: Producto 1: Máquina 1 - Máquina 3 - Máquina 4 Producto 2: Máquina 1 - Máquina 2 - Máquina 3 Producto 3: Máquina 2 - Máquina 4 Variables de decisión Xij: instante de inicio de la producción del producto i en la máquina j Donde i = 1, 2, 3 y j = 1, 2, 3, 4 T: tiempo total de procesamiento Donde T = máximo (X14 + 5, X23 + 1, X34 + 4) Función objetivo Minimizar el tiempo tiempo total de procesamiento Min z = T Restricciones El tiempo de procesamiento de cada producto es menor o igual que T X14 + 5 ≤ T T - X14 ≥ 5 X23 + 1 ≤ T T - X23 ≥ 1 X34 + 4 ≤ T T - X34 ≥ 4 Secuencia del producto 1 en cada máquina X13 ≥ X11 + 4 X13 - X11 ≥ 4 X14 ≥ X13 + 3 X14 - X13 ≥ 3 Secuencia del producto 2 en cada máquina X22 ≥ X21 + 2 X22 - X21 ≥ 2 X23 ≥ X22 + 6 X23 - X22 ≥ 6 Secuencia del producto 3 en cada máquina X34 ≥ X32 + 7 X34 - X32 ≥ 7 En la máquina 1 se procesa el producto 1 o el producto 2 X21 ≥ X11 + 4 ó X11 ≥ X21 + 2 X11 - X21 + 4 ≤ 1000 Y1 1000Y1 - X11 + X21 ≥ 4 X21 - X11 + 2 ≤ 1000 (1 - Y1) X21 - X11 + 1000 Y1 ≤ 998 En la máquina 2 se procesa el producto 2 o el producto 3

Investigación Operativa 1.

Capítulo 6. Programación Entera. 9

X32 ≥ X22 + 6 ó X22 ≥ X32 + 7 X22 - X32 + 6 ≤ 1000 Y2 1000 Y2 - X22 + X32 ≥ 6 X32 - X22 + 7 ≤ 1000*(1 - Y2) X32 - X22 + 1000 Y2 ≤ 993 En la máquina 3 se procesa el producto 1 o el producto 2 X23 ≥ X13 + 3 ó X13 ≥ X23 + 1 X13 - X23 + 3 ≤ 1000 Y3 1000 Y3 - X13 + X23 ≥ 3 X23 - X13 + 1 ≤ 1000*(1 - Y3) X23 - X13 + 1000 Y3 ≤ 999 En la máquina 4 se procesa el producto 1 o el producto 3 X34 ≥ X14 + 5 ó X14 ≥ X34 + 4 X34 - X14 + 4 ≤ 1000 Y4 1000 Y4 - X34 + X14 ≥ 4 X14 - X34 + 5 ≤ 1000*(1 - Y4) X14 - X34 + 1000 Y4 ≤ 995 Tiempo máximo de procesamiento para cada producto X14 + 5 ≤ 18 X14 ≤ 13 X23 + 1 ≤ 15 X23 ≤ 14 X34 + 4 ≤ 14 X34 ≤ 10 Rango de existencia

Xij 0; Yi = 0 ó 1 Bibliografía WINSTON, W.. Investigación de Operaciones. Aplicaciones y algoritmos. Cuarta edición. México, Thomson, 2005.

HILLIER, Frederick S. y Gerald J. LIEBERMAN. Introducción a la Investigación de Operaciones. Novena edición. México. Editorial McGraw-Hill, 2010.