Cap 6 Funciones Lineales Por Segmentos
Click here to load reader
description
Transcript of Cap 6 Funciones Lineales Por Segmentos
![Page 1: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/1.jpg)
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
![Page 2: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/2.jpg)
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
![Page 3: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/3.jpg)
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))
![Page 4: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/4.jpg)
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:
![Page 5: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/5.jpg)
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
![Page 6: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/6.jpg)
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
![Page 7: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/7.jpg)
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.
![Page 8: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/8.jpg)
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
![Page 9: Cap 6 Funciones Lineales Por Segmentos](https://reader038.fdocumento.com/reader038/viewer/2022100509/563dbb82550346aa9aadcca0/html5/thumbnails/9.jpg)
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.