View
230
Download
2
Category
Preview:
Citation preview
Programacion Lineal: Modelos PLE
CCIR / Matematicas
euresti@itesm.mx
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 1 / 35
Introduccion
Introduccion
En esta lectura se veran como se puede modelar situaciones mediante un modelo
de programacion lineal entera o entera mixta (PLE). Tambien veremos algunos
ejemplos que ilustran como modelar situaciones que nos son lineales, tanto en las
restricciones como en la funcion objetivo, que mediante la introduccion de
variables binarias se pueden convertir a un modelo lineal.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 2 / 35
0-1 Knapsack problem
0-1 Knapsack problem
Suponga que hay n proyectos y que el costo del proyecto i es ci y que por otrolado el valor del proyecto es ai . Cada proyecto se realiza o no, de manera que noes posible realizar una fraccion de el. El presupuesto disponible es limitado y tieneel valor b. El problema de la mochila consiste en elegir un subconjunto deproyectos que maximice el valor obtenido y que no exceda el presupuesto dado:
Maxn∑
i=1
ai xi
sujeto an∑
i=1
ci xi ≤ b
La variable binaria xi sirve para determinar cuando el proyecto i es seleccionado: 0
si no lo es, 1 si sı lo es.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 3 / 35
Ejemplo 1
Ejemplo 1
StockCo considera cuatro inversiones. La inversion 1 proporcionara un valoractual neto (VAN) de 16,000 dolares; la inversion 2 un VAN de 20,000 dolares; lainversion 3 un VAN de 12,000 dolares; y la inversion 4 un VAN de 8,000 dolares.Cada inversion requiere cierto flujo de caja en el momento actual; la inversion 1requiere 5,000 dolares; la inversion 2 requiere 7,000 dolares; la inversion 3 requiere4,000 dolares; y la inversion 4 requiere 3,000 dolares. Se dispone de 14,000dolares para la inversion. Formule y resuelva un modelo PLE para maximizar elVAN obtenido por StockCo.
Variables de Decision:
xi =
{1 si se realiza la inversion i0 otro caso
Objetivo: Maximizar el VAN:Max z = 16, 000 x1 + 20, 000 x2 + 12, 000 x3 + 8, 000 x4
Restricciones:
5, 000 x1 + 7, 000 x2 + 4, 000 x3 + 3, 000 x4 ≤ 14, 000xi = 1 o 0, para i = 1, 2, 3, 4.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 4 / 35
Ejemplo 1
Ejemplo 1
StockCo considera cuatro inversiones. La inversion 1 proporcionara un valoractual neto (VAN) de 16,000 dolares; la inversion 2 un VAN de 20,000 dolares; lainversion 3 un VAN de 12,000 dolares; y la inversion 4 un VAN de 8,000 dolares.Cada inversion requiere cierto flujo de caja en el momento actual; la inversion 1requiere 5,000 dolares; la inversion 2 requiere 7,000 dolares; la inversion 3 requiere4,000 dolares; y la inversion 4 requiere 3,000 dolares. Se dispone de 14,000dolares para la inversion. Formule y resuelva un modelo PLE para maximizar elVAN obtenido por StockCo.
Variables de Decision:
xi =
{1 si se realiza la inversion i0 otro caso
Objetivo: Maximizar el VAN:Max z = 16, 000 x1 + 20, 000 x2 + 12, 000 x3 + 8, 000 x4
Restricciones:
5, 000 x1 + 7, 000 x2 + 4, 000 x3 + 3, 000 x4 ≤ 14, 000xi = 1 o 0, para i = 1, 2, 3, 4.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 4 / 35
Ejemplo 1
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 5 / 35
Ejemplo 1
Modifique el modelo para StockCo para considerar por separado cada una de lassiguientes restricciones:
1 StockCo puede realizar los mas dos inversiones.
2 Si StockCo invierte en la inversion 2, entonces debe tambien invertir en la 1.
3 Si StockCo invierte en la inversion 2, entonces no podra invertir en la 4.
Respuestas
1 Basta anadir al modelo la restriccion: x1 + x2 + x3 + x4 ≤ 2Esto hace que entre todos los proyectos hay a lo mas dos sı’s
2 Basta anadir al modelo la restriccion: x2 ≤ x1
Esto hace que un sı para el proyecto 2 implique un sı para el proyecto 1.
3 Basta anadir al modelo la restriccion: x2 + x4 ≤ 1Esto hace que entre los proyectos 2 y 4 hay a lo mas un sı.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 6 / 35
Ejemplo 1
Modifique el modelo para StockCo para considerar por separado cada una de lassiguientes restricciones:
1 StockCo puede realizar los mas dos inversiones.
2 Si StockCo invierte en la inversion 2, entonces debe tambien invertir en la 1.
3 Si StockCo invierte en la inversion 2, entonces no podra invertir en la 4.
Respuestas
1 Basta anadir al modelo la restriccion: x1 + x2 + x3 + x4 ≤ 2Esto hace que entre todos los proyectos hay a lo mas dos sı’s
2 Basta anadir al modelo la restriccion: x2 ≤ x1
Esto hace que un sı para el proyecto 2 implique un sı para el proyecto 1.
3 Basta anadir al modelo la restriccion: x2 + x4 ≤ 1Esto hace que entre los proyectos 2 y 4 hay a lo mas un sı.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 6 / 35
Ejemplo 2
Ejemplo 2
Gandhi Cloth Co puede fabricar 3 tipos de ropa: camisas, shorts y pantalones.Para poder fabricar la ropa, la companıa debe disponer de la maquinaria adecuadala cual debe rentar. Para fabricar camisas la maquinaria se renta en 200 dolarespor semana; la maquinaria para hacer shorts se renta en 150 dolares por semana;y la maquinaria para hacer pantalones cuesta 100 dolares por semana. Lasiguiente tabla contiene informacion sobre los requerimientos para fabricar la ropaen tela y en horas de trabajo, ası mismo contiene informacion sobre los precios deventa y los costos de la matera primas.
TRABAJO TELA PRECIO VENTA COSTOHoras m2 dolares dolares
Camisa 3 4 12 6Short 2 3 8 4
Pantalon 6 4 15 8
Disponibles 150 160
Suponiendo que los costos de renta son independientes de las cantidades de ropa
a producir, formule y resuelva un modelo PLE para la companıa Gandhi de
manera que maximice sus ganancias semanales.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 7 / 35
Ejemplo 2
Variables de Decision:
x1 = numero de camisas a fabricarx2 = numero de shorts a fabticarx3 = numero de pantalones a fabricarRelativas a la renta de maquinaria:
y1 =
{1 si se fabrican camisas0 otro caso
y2 =
{1 si se fabrican shorts0 otro caso
y3 =
{1 si se fabrican pantalones0 otro caso
Objetivo Maximizar:
z = + (12 x1 + 8 x2 + 15 x3)− (6 x1 + 4 x2 + 8 x3)− (200 y1 + 150 y2 + 100 y3)
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 8 / 35
Ejemplo 2
Restricciones
No exceder el numero de horas disponibles de trabajo3 x1 + 2 x2 + 6 x3 ≤ 150
No exceder la cantidad semanda de tela disponible:4 x1 + 3 x2 + 4 x3 ≤ 160
Si se decide hacer al menos una camisa, debe rentarse la maquinaria dehacer camisas: x1 ≤ M1 y1
Si se decide hacer al menos un short, debe rentarse la maquinaria de hacershorts: x2 ≤ M2 y2
Si se decide hacer al menos una pantalon, debe rentarse la maquinaria dehacer pantalones: x3 ≤ M3 y3
x1, x2, x3 enteros no negativos, y1, y2, y3 1 o 0.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 9 / 35
Ejemplo 2
Para las restricciones anteriores, M1, M2 y M3 son numeros grandes de forma talque un 0 en yi condiciona a que xi = 0 y un 1 en yi no pone restricciones a xi .
Estos valores de Mi son calculables por las restricciones. Por ejemplo, si solo se
hicieran camisas (x2 = 0 y x3 = 0) por las horas de trabajo se debe cumplir que
3 x1 ≤ 150, ası x1 ≤ 50. Por tanto, se puede elegir M1 = 50 o un numero mayor.
De igual manera, si solo se hacen shorts (x1 = 0 y x3 = 0) de la restriccion de
horas de trabajo se tiene que cumplir 2 x2 ≤ 150, y sı x2 ≤ 75. Por tanto, se
puede elegir M2 = 75 o cualquier numero mayor. Si ahora decidimos elegir solo
hacer pantalones (x1 = 0 y x2 = 0) por el numero de horas disponibles se debe
cumplir 6 x3 ≤ 150, y ası x3 ≤ 25. Por tanto, se puede elegir M3 = 25 o cualquier
numero mayor.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 10 / 35
Ejemplo 2
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 11 / 35
Ejemplo 3
Ejemplo 3
Hay seis ciudades (ciudades 1-6) en el Condado Kilroy. El condado debedeterminar en que ciudad construir estaciones de bomberos. El condado quiereconstruir una cantidad mınima de estaciones, pero quiere asegurarse que paracada ciudad hay al menos una estacion que esta a 15 minutos de viaje. Los datosde los tiempos de viaje, en minutos, de una ciudad a otra estan en la siguientetabla. Formule y resuelva un modelo PLE que dira en que ciudades construir unaestacıon de bomberos.
HACIADE Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Ciudad 5 Ciudad 6
Ciudad 1 0 10 20 30 30 20Ciudad 2 10 0 25 35 20 10Ciudad 3 20 25 0 15 30 20Ciudad 4 30 35 15 0 15 15Ciudad 5 30 20 30 15 0 14Ciudad 6 20 10 20 25 14 0
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 12 / 35
Ejemplo 3
Variables de decision:
xi =
{1 si estacion de bomberos en la ciudad i0 si no
Objetivo:
Minimizar el total de estaciones de bomberos: Minimizar∑6
i=1 xiRestricciones
Cubrir a la ciudad 1: Como solo ella misma y la ciudad 2 estan a 15 minutoso menos, entonces la ciudad 1 se cubrirıa teniendo estaciones de bomberosen la ciudad 1 y/o en la ciudad 2: x1 + x2 ≥ 1
Cubrir a la ciudad 2: x1 + x2 + x6 ≥ 1
Cubrir a la ciudad 3: x3 + x4 ≥ 1
Cubrir a la ciudad 4: x3 + x4 + x5 ≥ 1
Cubrir a la ciudad 5: x4 + x5 + x6 ≥ 1
Cubrir a la ciudad 6: x2 + x5 + x6 ≥ 1
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 13 / 35
Ejemplo 3
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 14 / 35
Ejemplo 4
Ejemplo 4
FC-Co considera construir plantas en tres localidades desde donde se proveeranproductos a otras 4 ciudades distintas. La primera de las posibles plantas tendrıauna capacidad de 39 productos y un costo de 91 unidades de capital; la segundatendrıa una capacidad de 35 productos y un costo de 70 unidades de capital; latercera tendrıa una capacidad de 31 productos a un costo de construccion de 24unidades de capital. La ciudad 1 tiene una demanda de 15 productos, la segundade 17, la tercera de 22 y la cuarta ciudad de 12 productos. Determine cuales delas plantas debe construir de manera que se minimice el costo de construccion yel costo por envio total. Suponga que debe proporcionar a las ciudades losproductos requeridos y que no debe exceder las capacidades de las plantas. Loscostos de envio unitarios en unidades de capital desde cada planta a cada ciiudadestan dados en la siguiente tabla.
C1 C2 C3 C4
P1 6 2 6 7P2 4 9 5 3P3 8 8 1 5
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 15 / 35
Ejemplo 4
Variables de decision
yi : variable binaria que indica si la planta i se construye
xi,j : Variable entera que determina cuantos productos se envian desde laplata i a la ciudad j .
Objetivo
Min z =3∑
i=1
cpi · yi +3∑
i=1
4∑j=1
ci,j · xi,j
Restricciones
Cumplir demandas: Para toda ciudad j = 1, 2, 3, 4,∑3
i=1 xi,j ≥ dj
No exceder capacidades: Para toda planta i = 1, 2, 3,∑4
j=1 xi,j ≤ si · yiNaturales: Para toda i = 1, 2, 3, yi es binaria.
Naturales: Para toda i = 1, 2, 3 y para toda j = 1, 2, 3, 4, xi,j es entera.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 16 / 35
Ejemplo 4
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 17 / 35
Restricciones del tipo O BIEN
Restricciones del tipo O BIEN
Para codificar una restriccion del tipo
f (x1, x2, . . . , xn) ≤ 0
o bieng(x1, x2, . . . , xn) ≤ 0
el truco consiste en introducir una variable binaria (0 o 1) y que indica cualrestriccion se cumple, y lo anterior se codifica como
f (x1, x2, . . . , xn) ≤ M yg(x1, x2, . . . , xn) ≤ M (1− y)
donde M es un numero positivo muy grande.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 18 / 35
Ejemplo 5
Ejemplo 5
Dorian Auto considera la fabricacion de 3 tipos de autos: Compacto, mediano, ygrande. En la siguiente tabla se muestran los recursos requeridos y las gananciaspor cada tipo de auto. En la actualidad se cuenta con 600 toneladas de acero y60,000 horas de trabajo. Para que la produccion de un tipo de auto sea factible,hay que fabricar al menos 100 automoviles. Formule un modelo PLE paramaximizar la ganancia de Dorian Auto.
COMPACTO MEDIANO GRANDE
Acero requerido 1.5 ton 3 ton 5 tonTrabajo requerido 30 horas 25 horas 40 horasGancia obtenida 2,000 dolares 3,000 dolares 4,000 dolares
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 19 / 35
Ejemplo 5Variables de Decision
xi= Num de autos i a producir (i = 1 Compacto, i = 2 mediano, i = 3grande)
Objetivo
Max z =3∑
i=1
gi · xi
Restricciones
Recursos:
Acero: 1.5 x1 + 3 x2 + 5 x3 ≤ 600Trabajo: 30 x1 + 25 x2 + 40 x2 ≤ 60, 000
Produccion: 400 ≤ xi o xi = 0
Restricciones naturales xi ≥ 0
Truco:
400 ≤ xi o xi = 0 → f = 400− xi ≤ 0 o g = xi ≤ 0→ (400− xi ) ≤ M yi y xi ≤ M (1− yi )
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 20 / 35
Ejemplo 5
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 21 / 35
Funciones Linealmente Seccionadas
Funciones Linealmente Seccionadas
Suponga una funcion linealmente seccionada en la variable var , f (var); cuyospuntos de ruptura son var = b1, var = b2, . . . var = bn. Para algun k(k = 1, 2, . . . , n − 1) se tiene que
var = zk bk + (1− zk) bk+1
y asıf (var) = zk f (bk) + (1− zk) f (bk+1)
f (bk )
f (var)
f (bk+1)
bk var bk+1
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 22 / 35
Funciones Linealmente Seccionadas
Estrategia de modelacion con variables enteras:
Reemplace:f (var) = z1 f (b1) + z2 f (b2) + · · ·+ znf (bn)
Adicione al modelo las restricciones:
z1 ≤ y1
z2 ≤ y1 + y2
z3 ≤ y2 + y3
...zn−1 ≤ yn−2 + yn−1
zn ≤ yn−1
y1 + y2 + · · ·+ yn−1 = 1z1 + z2 + · · ·+ zn = 1
var = z1 b1 + · · ·+ zn bn
yi = 0 o 1 para i = 1, 2, . . . n − 1, zi ≥ 0 para i = 1, 2, . . . , n
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 23 / 35
Ejemplo 6
Ejemplo 6
La companıa MyCo produce dos tipos de productos que vende a granel, digamos
A y B. Estos productos se basan en una misma materia prima y diferentes
cantidades de mano de obra. El precio de venta de cada kilogramo de A es de 200
pesos y cada kilogramo de B se vende en 250 pesos. Cada kilogramo de A
requiere 4 horas de mano de obra y dos kilogramos de materia prima (1 kilogramo
de materia prima se pierde en el proceso). Cada kilogramo de B requiere 6 horas
de mano de obra y dos kilogramos y medio de materia prima (Un y medio
kilogramos se pierden en el proceso). La companıa dispone de 400 horas de mano
de obra a la semana y la materia prima la compra por semana a un proveedor a
un precio de 50 pesos cada kilogramo, pero por cada kilogramo despues de
comprar 100 recibe un descuento de 5 pesos. El proveedor no puede proporcionar
mas de 200 kilogramos por semana. Suponga que la materia prima no puede ser
almancenada por la companıa. Modele y resuelva mediante PLE la situacion de
MyCo para maximizar sus ganancias semanales.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 24 / 35
Ejemplo 6MODELO
VD
x= total de kg de A a producir
y= total de kg de B a producir
z= total de kg de materia prima a comprar
Objetivo
Maxw = Costo(plan) = ventas − costos = (200 x + 250 y)− C (z)
f (b3) = 9500
f (b2) = 5000
f (b1) = 0b3 = 200b2 = 100b1 = 0
C (z)
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 25 / 35
Ejemplo 6
Las restricciones quedan:
Referente a la materia prima:
Usada = 2 x + 2.5 y ≤ Disponible = z (en kg)
Referente a las horas de mano de obra:
Usada = 4 x + 6 y ≤ Disponible = 400 (en hrs)
La capacidad del proveedor de surtir materia prima
z ≤ 200 (en kg)
Naturales x , y , z ≥ 0
Ahora tenemos el pendiente de la funcion C (z) que no es lineal.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 26 / 35
Ejemplo 6
En este caso, la funcion linealmente seccionada C (z) tiene 3 puntos deruptura: (b1 = 0,C (0) = 0), (b2 = 100,C (100) = 5000) y(b3 = 200,C (200) = 9500). Por tanto, requerimos solo 3− 1 = 2 variablesbinarias yi (y1 y y2) y 3 variables auxiliares zi (z1, z2 y z3). Cambiaremos
C (z) = z1 · f (b1) + z2 · f (b2) + z3 · f (b3)= z1 · 0 + z2 · 5000 + z3 · 9500= 5000 z2 + 9500 z3
y anadiremos al modelo las restricciones:
z1 ≤ y1, z2 ≤ y1 + y2, z3 ≤ y2,y1 + y2 = 1,z1 + z2 + z3 = 1,z = z1 · b1 + z2 · b2 + z3 · b3 = 100 z2 + 200 z3
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 27 / 35
Ejemplo 6
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 28 / 35
Ejemplo 7
Ejemplo 7
Euing Gas produce dos tipos de gasolina (G1 y G2) a partir de dos tipos de
petroleo (P1 y P2). Cada galon de G1 debe contener al menos 50 % de P1, y
cada galon de G2 debe contener al menos 60 % de P1. Cada galon de G1 se
vende 12 centavos de G2 a 14 centavos. Actualmente se disponen 500 galones de
P1 y 1,000 galones de P2. Se pueden comprar 1,500 galones extra de P1 a los
siguientes precios: los primeros 500 a 25 centavos el galon, los siguientes 500 a 20
centavos el galon, y los ultimos 500 a 15 centavos el galon. Modele y resuelva
mediante PLE la situacion de Euing Gas para maximizar sus ganancias.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 29 / 35
Ejemplo 7
Variables de Decision
xij = Num de galones del petroleo i destinados a gasolina j .
Xi = Num de galones del petroleo i usados en total.
Objetivo
Max z = 0.12 (x11 + x21) + 0.14 (x12 + x22)− Costo(X1)
Restricciones
Produccion: X1 = x11 + x12
Produccion: X2 = x21 + x22
Recursos petroleo 2: X2 ≤ 1, 000
Recursos petroleo 1: X1 ≤ 2, 000
Calidad: x11 ≥ 0.5 (x11 + x21)
Calidad: x12 ≥ 0.6 (x12 + x22)
Restricciones naturales xi ≥ 0
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 30 / 35
Ejemplo 7Problema: Costo(X1) es una funcion seccionada
Costo(x) = 0 para 0 ≤ x ≤ 500 (Los primeros 500 ya se tienen)
Costo(x) = 0 + 0.25(x − 500) para 500 ≤ x ≤ 1, 000
Costo(x) = 125 + 0.20(x − 1, 000) para 1, 000 ≤ x ≤ 1, 500
Costo(x) = 125 + 100 + 0.15(x − 1, 500) para 1, 500 ≤ x ≤ 2, 000
Los extremos de la grafica de la funcion costo son: P1(b1 = 0, f (b1) = 0),P2(b2 = 500, f (b2) = 0), P3(b3 = 1000, f (b3) = 125),P4(b4 = 1500, f (b4) = 225), y P5(b5 = 2000, f (b5) = 300): Reemplazaremos:
Costo(X1) por z1 · 0 + z2 · 0 + z3 · 125 + z4 225 + z5 · 300
Adicionaremos al modelo:
z1 ≤ y1, z2 ≤ y1 + y2, z3 ≤ y2 + y3, z4 ≤ y3 + y4, z5 ≤ y4
y1 + y2 + y3 + y4 = 1z1 + z1 + z3 + z4 + z5 = 1
X1 = z1 · 0 + z2 · 500 + z3 · 1, 000 + z4 · 1, 500 + z5 · 2, 000yi binaria para i = 1, 2, 3, 4y zi ≥ 0 para i = 1, 2, 3, 4, 5
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 31 / 35
Ejemplo 7
Codigo LINDO y reporte Euing
MAX 0.12X11+0.12X21+0.14X12+0.14X22-CX1
ST
X1 -X11 - X12=0
X2 -X21 + X22=0
X2 <= 1000
X1 <= 2000
0.5X11 + 0.5X21 - X11 <=0
0.6X12 + 0.6X22 - X12 <= 0
125Z3 + 225Z4 + 300Z5 - CX1=0
Z1 - Y1 <= 0
Z2 - Y2 - Y1 <=0
Z3 - Y3 - Y2 <=0
Z4 - Y4 - Y3 <=0
Z5 - Y4 <= 0
Y1 + Y2 + Y3 + Y4 = 1
Z1 + Z2 + Z3 + Z4 + Z5 = 1
1000Z3 + 1500Z4 + 2000Z5 - X1 <=0
END
INTE Y1
INTE Y2
INTE Y3
INTE Y4
OBJECTIVE FUNCTION VALUE1) 476.0000
VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 0.000000 0.000000Y3 0.000000 0.000000Y4 0.000000 0.000000
X11 1400.000000 0.000000X21 1400.000000 0.000000X12 600.000000 0.000000X22 400.000000 0.000000CX1 0.000000 0.000000X1 2000.000000 0.000000X2 1000.000000 0.000000Z3 0.000000 125.000000Z4 0.000000 225.000000Z5 0.000000 300.000000Z1 0.000000 0.000000Z2 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 -0.2360003) 0.000000 -0.0040004) 0.000000 0.0040005) 0.000000 0.2360006) 0.000000 0.2320007) 0.000000 0.2400008) 0.000000 1.0000009) 1.000000 0.000000
10) 0.000000 0.00000011) 0.000000 0.00000012) 0.000000 0.00000013) 0.000000 0.00000014) 0.000000 0.00000015) 0.000000 0.00000016) 2000.000000 0.000000
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 32 / 35
Restricciones del tipo SI , ENTONCES
Restricciones del tipo SI , ENTONCES
Para codificar una restriccion del tipoSi
f (x1, x2, . . . , xn) > 0
entoncesg(x1, x2, . . . , xn) ≥ 0
el truco consiste en introducir una variable binaria (0 o 1) y que indica cualrestriccion se cumple, y lo anterior se codifica como
−g(x1, x2, . . . , xn) ≤ M yf (x1, x2, . . . , xn) ≤ M (1− y)
donde M es un numero positivo muy grande.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 33 / 35
Ejemplo 8
Ejemplo 8
Hay que realizar cuatro trabajos en una misma maquina. En la tabla siguiente seindica el tiempo requerido por trabajo y la fecha lımite para entregarlo. El retrasode un trabajo es el numero de dıas, despues de la fecha lımite, hasta la laterminacion del trabajo. Si se termina el trabajo a tiempo o antes el retraso escero. Formule y resuelva un modelo PLE para minimizar el retraso total de loscuatro trabajos.
TIEMPO REQUERIDO
PARA TERMINAR (dıas)(ti ) FECHA LIMITE (di )
Trabajo 1 6 Final del dıa 8Trabajo 2 4 Final del dıa 4Trabajo 3 5 Final del dıa 12Trabajo 4 8 Final del dıa 16
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 34 / 35
Ejemplo 8
Variables de decision
yi = dıas de retraso en el trabajo i .
xi = el dıa en el cual el trabajo i se inicia.
Funcion Objetivo Minimizar Z =∑4
i=1 yiRestricciones
Dos trabajos no se pueden empalmar: Para todo i 6= j :
xi + ti ≤ xj o xj + tj ≤ xi → xi + ti − xj ≤ 0 o xj + tj − xi ≤ 0→ xi + ti − xj ≤ M zij y
xj + tj − xi ≤ M (1− zij)
con zij binario.
Contabilizacion del retraso: Si xi + ti > di , entonces yi = xi + ti − di : Deotra manera Si xi + ti − di > 0, entonces yi − xi − ti + di ≥ 0.
xi + ti − di − yi ≤ M wi y xi + ti − di ≤ M(1− wi )
con wi binario.
CCIR / Matematicas Programacion Lineal: Modelos PLE euresti@itesm.mx 35 / 35
Recommended