MODELO DE PROGRAMACION ENTERA Y BINARIA
Enviado por Kate • 2 de Mayo de 2018 • 4.484 Palabras (18 Páginas) • 585 Visitas
...
S´olo tiene presupuesto para pagar las tasas de solicitud en 3 proyectos.
¿A qu´e 3 proyectos optar?
Beneficio esperado (en miles de euros) que puede obtener a los 3 a˜nos[pic 4]
con cada uno de los proyectos.
Estimaci´on de la probabilidad de que no le concedan cada uno de los[pic 5]
proyectos[pic 6]
Proyecto
1
2
3
4
5
Beneficio (miles euros)
90
150
80
100
120
Probabilidad de rechazo
0.4
0.7
0.4
0.5
0.6
Problema: qu´e proyectos deber´ıa solicitar para obtener un beneficio mayor y asegurarse de que la suma de las probabilidades de rechazo no sea superior a 1.5
---------------------------------------------------------------
Variables de decisi´on:[pic 7]
1, si se solicita el proyecto i,
xi =
---------------------------------------------------------------
0, si no se soliciota el proyecto i.
---------------------------------------------------------------
i = 1, 2, 3, 4, 5
Restricciones:[pic 8]
• L´ımite presupuestario:
x1 + x2 + x3 + x4 + x5 ≤ 3
• Suma de las probabilidades de rechazo no exceda 1.5
0,4x1 + 0,7x2 + 0,4x3 + 0,5x4 + 0,6x5 ≤ 1,5
• Condici´on de variables binarias:
xi ∈ {0, 1}, i = 1, 2, 3, 4, 5
---------------------------------------------------------------
Objetivo: maximizar el beneficio esperado[pic 9]
90x1 + 150x2 + 80x3 + 100x4 + 120x5
¿C´omo cambiar´ıas el modelo anterior si se hubiera pedido que la probabilidad de no obtener ning´un proyecto fuese, a lo sumo, del 10 %?
Si seleccionamos, por ejemplo, los proyectos 1, 2 y 3:
P {no obtener ning´un proyecto} = P {rechazan P1 y P2 y P3} = (0,4)(0,7)(0,4) =⇒
P {no obtener ning´un proyecto} ≤ 0,1 ⇐⇒ (0,4)(0,7)(0,4) ≤ 0,1 ⇐⇒
log((0,4)(0,7)(0,4)) ≤ log(0,1) ⇐⇒ log(0,4) + log(0,7) + log(0,4) ≤ log(0,1)
− log(0,4)x1 − log(0,7)x2 − log(0,4)x3 − log(0,5)x4 − log(0,6)x5 ≥ 1
---------------------------------------------------------------
Se dispone de n objetos para llenar una mochila.
El objeto j tiene un peso pj y tiene una utilidad (valor) cj . La mochila admite un peso m´aximo de b.
El problema consiste en decidir qu´e objetos se introducen en la mochila de forma que se maximice la utilidad de los objetos seleccionados.
Variables:[pic 10]
xj =
---------------------------------------------------------------
1 si el objeto j es seleccionado,
0 en otro caso.
---------------------------------------------------------------
∀j = 1, . . . , n
---------------------------------------------------------------
Restricciones:[pic 11]
• L´ımite de peso de la mochila:
---------------------------------------------------------------
n
X
j=1
---------------------------------------------------------------
pj xj ≤ b
• Condici´on de variables binarias: xj ∈ {0, 1} ∀j = 1, . . . , n
Funci´on objetivo: m´ax[pic 12]
---------------------------------------------------------------
n
X
j=1
---------------------------------------------------------------
cj xj
Se pueden considerar variantes en las que se incluya tambi´en el volumen, etc.
O la posibilidad de que haya m´as de una unidad de cada objeto. En- tonces, las variables ser´ıan xj igual al n´umero de unidades del objeto j seleccionadas.
---------------------------------------------------------------
El modelo de asignaci´on permite asignar eficientemente un conjunto de personas a un conjunto de trabajos, m´aquinas a tareas, coches de polic´ıa a sectores de una ciudad, vendedores a zonas, etc.
El objetivo es minimizar
...