Optimización en Programación Lineal
Traducido por
ScribdTranslationsOptimización en Programación Lineal
Traducido por
ScribdTranslationsProgramación Lineal
Formulación 1 - Problema de mezcla de productos
Una tienda puede hacer dos tipos de dulces (A y B). Utilizan dos recursos -
harina y azúcar. Para hacer un paquete de A, necesitan 3 kg de harina y 3 kg
de azúcar. Para hacer un paquete de B, necesitan 3 kg de harina y 4 kg de azúcar.
Tienen 21 kg de harina y 28 kg de azúcar. Estos dulces se venden a Rs
1000 y 900 por paquete, respectivamente. Encuentra la mejor mezcla de productos para
maximizar los ingresos.
Deja X1sea el número de paquetes del dulce A hechos
Deja X2sea el número de paquetes de dulces B hechos
Maximizar 1000X1+ 900X2
3X1+ 3X2≤ 21
3X1+ 4X2≤ 28
X1, X2≥ 0
Notatons
Dejar X1sea el número de paquetes de dulce A producidos
Decisión
Deja X2ser el número de paquetes del dulce B hecho variable
Maximizar 1000X1+ 900X2 Función objetivo
3X1+ 3X2≤ 21 Restricciones
3X1+ 4X2≤ 28
X1, X2≥ 0 Restricción de no negatividad
Suposiciones
Proporcionalidad
2. Linealidad
3. Determinista
Formulación 2 - Requerimiento de mano de obra
El requerimiento diario de enfermeras en un hogar de ancianos privado se da en la
siguiente tabla
Hora del día Requerimiento
8 a.m. – 12 p.m. 12
12 del mediodía - 4 de la tarde 15
4 p. m. a 8 p. m. 10
8 pm a 12 de la medianoche 8
12 de la medianoche a 4 de la mañana 6
4 a.m. a 8 a.m. 10
Las enfermeras comienzan a trabajar al inicio del turno (8 a.m., 12 p.m., etc.) y
trabajar durante 8 horas continuas. ¿Cuál es el número mínimo de enfermeras?
¿necesario para satisfacer la demanda diaria?
Deja X1a X6sea el número de enfermeras que comienzan a trabajar a las 8 a.m.
["12 del mediodía","4 de la tarde","8 de la noche","12 de la medianoche","4 de la mañana"]
Minimizar =X1+ X2+ X3+ X4+ X5+ X6
X1+ X2≥ 15
X2+ X3 ≥ 10 Requisito de
período 2
X3+ X4≥ 8 del mediodía a las 4 de la tarde
X4+ X5≥ 6
X5+ X6≥ 10
X6+ X1≥ 12
X1, X2, X3, X4, X5, X6≥ 0
Formulación 3 – Planificación de la Producción
Las demandas durante 2 semanas para un producto son 800 y 1000. En una semana el
la empresa puede producir hasta 700 unidades en tiempo regular a Rs 100/producto.
can employ overtme and product up to an extra 300 units in a week at Rs
120/producto. El costo de transportar un producto de una semana a la siguiente es Rs
15/producto/semana. ¿Cómo deberían producir para satisfacer la demanda en
¿costo mínimo?
Deja X1 ser el número de productos fabricados utilizando regulartme en la semana 1.
Deja X2sea el número de productos fabricados utilizando regulartme en la semana 2.
Deja Y1sea el número de productos fabricados utilizando horas extras en la semana 1.
Deja Y2ser el número de productos fabricados utilizando horas extra en la semana 2.
Dejar Z1ser el número de productos transportados de la semana 1 a la semana 2
Formulación 3 – Planificación de la Producción
Minimizar 100X1+ 100X2 Minimize 100X1+ 100X2+ 120Y1+
+ 120Y1+ 120Y2+ 15Z1 120Y2+ 15( X1+ Y1– 800)
sujeto a Minimizar 115X1+ 100X2+ 135Y1+
X1+ Y1= 800 + Z1; 120Y2- 12000
X1+ Y1- Z1= 800 sujeto a
Z1+ X2+ Y2 = 1000 X1+ Y1≥ 800
X1+ X2+ Y1+ Y2≥ 1800
X1≤ 700
X1≤ 700
X2≤ 700 X2≤ 700
Y1≤ 300 Y1≤ 300
Y2≤ 300 Y2≤ 300
X , X , Y , Y , Z≥ 0 X , X , Y , Y≥ 0
Formulación 4 - Problema de selección de medios
Una empresa quiere anunciar su producto en cuatro medios diferentes: TV,
periódico, sitios web y radio. El alcance por publicidad en estos cuatro
media are 8000, 5000, 3000 and 2000. The cost per advertsement is Rs 4
lakh, 3 lakhs, 2 lakhs y 1.5 lakhs. El número máximo de
advertsements that the company wishes to have in each media is 3, 4, 5, 4.
El presupuesto disponible es de 32 lakhs. ¿Cuántos anuncios hace?
¿La empresa decide en cada medio para maximizar el alcance?
Deja X1ser el número de anuncios en la televisión
Deja X2sea el número de anuncios en el periódico
Deja X3ser el número de anuncios en sitios web
Deja X4ser el número de anuncios en la radio
Formulación 4 – Problema de Selección de Medios
Maximizar 8000X1+ 5000X2+ 3000X3+ 2000X4
sujeto a Alcance
4X1+ 3X2+ 2X3+ 1.5X4≤ 32
Presupuesto
X1≤ 3
X2≤ 4
Límites/contornos
X3 ≤ 5
X4≤ 4
X1, X2, X3, X4≥ 0 No negatividad
Formulación 5 - Problema de la bicicleta
Tres amigos (A, B y C) parten de P hacia Q, que está a 5 km.
lejos. Tienen un ciclo y solo una persona monta un ciclo a la vez.
A, B y C caminan a velocidades de 4, 5 y 6 km/h y pueden
monta en la bicicleta a 7, 8 y 10 km/hora. ¿Cómo viajan así?
¿que los tres lleguen a Q en el primer momento?
Tiempo tomado por A = Minimizar u
Tiempo tomado por B = Sujeto a
Tiempo tomado por C =
Los tres llegan cuando el último
persona alcanza. Minimizar X1, X2, X3, u ≥ 0
el máximo de las tres veces
Formulaton 6 – Problema de servilletas
La necesidad de servilletas en cinco días consecutivos de cena es 100, 60, 80, 90, 70.
Las nuevas servilletas cuestan 60 Rs. Las servilletas enviadas a la lavandería al final de cualquier día se pueden usar desde
A partir del segundo día. El costo de la lavandería es de Rs 20/pañuelo. Encuentra una solución para los pañuelos.
¿problema que minimiza el costo total?
Formulación 6 – Problema de servilletas
Demanda del Día 1 X1≥ 100
Demanda del día 2 – Podemos comprar más de 100 en el día 1 y X1-100 + X2≥ 60
Usa algunas de las servilletas extras en el día 2
X1+ X2≥ 160
Día 3 demanda - servilletas extras del día 2 + X1+ X2– 160 + X3+ Y1≥ 80
nuevas servilletas compradas el día 3
+ napkins received from laundry on day 3 (sent on day 1) X1+ X2+ X3+ Y1≥ 240
Demanda del día 4 - servilletas extras del día 3 + X1+ X2+ X3+ Y1- 240 + X4+ Y2≥ 90
nuevas servilletas compradas el día 4
+ servilletas recibidas de la lavandería en el día 4 (enviadas en el día 2) X1+ X2+ X3+ Y1+ X4+ Y2≥ 330
Formulación 6 – Problema de servilletas
Día 5 demanda – servilletas adicionales
X1+ X2+ X3+ Y1+ X4+ Y2– 330 + X5+ Y3≥ 70
desde el día 4 + nuevas servilletas compradas el día 5
+ servilletas recibidas de la lavandería en el día 5
X1+ X2+ X3+ X4+ X5+ Y1+ Y2 + Y3≥ 400
(enviado el día 3)
Limit on napkins sent to laundry Y1≤ 100, Y2≤ 60, Y3≤ 80
Función objetivo Minimiza 60 (X1+ X2+ X3+ X4+ X5) + 20 (Y1+ Y2+ Y3)
No negatividad X1, X2, X3, X4, X5, Y1, Y2,Y3≥ 0
Formulación 6 – Problema de servilletas
(Formulación general)
Deja que el número de servilletas nuevas compradas en el día i sea XyoDeja que el número de servilletas
enviado a la lavandería al final del día yo seré Yyo
Minimizar c = cost of new napkin
a = costo de lavandería
d = demand
p = días de lavandería
Yyo dyo
Xyo, Yyo, 0.
Formulación 7 – Problema de flujo máximo
10
2 Encuentra el flujo máximo en la red
The arc capacites are given
20 30 5
30
25
1 4 Deja Xijser el flujo en el arco i-j.
35 Sea f el flujo en la red
40 20
3
Las variables son X12, X13, X23, X24, X25, X34, X35y X45
Formulación 7 – Problema de flujo máximo
10 Maximizar f X12≤ 20
2 Sujeto a
X13≤ 40
X12+ X13= f
20 30 5 X23≤ 30
-X12+ X23+ X24+ X25= 0
30 X24≤ 30
25 -X13-X23+ X34+ X35= 0
1 4 X25≤ 10
35 -X24-X34+ X45= 0
40 20 X34≤ 35
X25+ X35 + X45= f
3 X35≤ 20
Maximizar X25+ X35+ X45 X45≤ 25
Sujeto a f, Xij≥ 0.
-X12+ X23+ X24+ X25= 0
-X13-X23+ X34+ X35 = 0
-X24-X34+ X45 = 0
Formulación 8 – Empaquetado en cajas
Se te dan los números 8, 6, 9, 28, 17, 24, 7, 21. Haz el mínimo número de grupos.
de manera que la suma de los números en cada grupo no exceda 45.
Se pueden formar un máximo de 8 grupos. Definimos Yj= 1 si se forma el grupo j
y Xij= 1 si el número i va al grupo j.
Las variables no son continuas y toman valores binarios
Minimizar
Minimizar Y1+ Y2+ Y3+ Y4+ Y5+ Y6+ Y7+ Y8
Formulación 8 - Empaquetado de contenedores
Se te dan los números 8, 6, 9, 28, 17, 24, 7, 21. Forma el menor número de grupos.
de modo que la suma de los números en cada grupo no exceda 45.
X11+ X12+ X13+ X14+ X15+ X16+ X17+ X18= 1
8X11+ 6X21+ 9X31+ 28X41+ 17X51+ 24X61+ 7X71+ 21X81≤ 45A1
Hay 64 + 8 = 72
Xij, Yj= 0,1
Variables y 16 restricciones
Formulación 8 - Empaque de bin
You are given the numbers 8, 6, 9, 28, 17, 24, 7, 21. Make minimum number of groups
de manera que la suma de los números en cada grupo no exceda 45.
Una solución simple sería {8, 6, 9}, {28, 17}, {24, 7}, {21}. Hay 4 grupos. Usando esto
Podemos reducir la Yjvariables a 4 y asignar números a 4 grupos mientras se minimiza el
número de grupos.
La formulación tendría 8x4 + 4 = 36 variables y 8 + 4 = 12 restricciones y es
más simple
Podemos verificar si hay una solución definiendo 3 grupos. La formulación
tendría 8x3 + 3 = 27 variables y 8+3 = 11 restricciones.
A veces, comenzar con una solución proporciona mejores formulaciones para algunos enteros (binarios)
problemas de programación