1. No category

Repaso Prueba 2
Ejemplo 1: Programación
Entera
Supongamos que una persona está
interesada en elegir entre un
conjunto de inversiones {1,…,7} y
quiere hacer un modelo 0,1 para
tomar la decisión.
Modelar las siguientes restricciones:
2
Ejemplo 1
i)
No se puede invertir en todas.
Como no nos indican el número mínimo, ni la
cantidad exacta, sólo que no se pueden invertir en
las 7 a la vez, la restricción que nos piden es:
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 + 𝑥7 ≤ 6
3
Ejemplo 1
ii)
Hay que elegir al menos una de
ellas.
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 + 𝑥7 ≥ 1
4
Ejemplo 1
iii) Si se elige la 3 no se puede elegir
la 1.
Si 𝑥3 = 1 entonces 𝑥1 = 0, en este caso indica
que las dos no pueden elegirse juntas:
𝑥1 + 𝑥3 ≤ 1
5
Ejemplo 1
iv) La inversión 4 se puede elegir
sólo si se elige la 2.
Realmente lo que nos indica es que si 𝑥2 = 0
entonces 𝑥4 = 0:
𝑥4 ≤ 𝑥2
6
Ejemplo 1
v)
Se eligen las inversiones 2 y 5 o
ninguna de las dos.
Si se elige la 2 se elige la 5 y si no se elige la 2 no
se elige la 5, es decir hacemos lo mismo con
ambas inversiones:
𝑥2 = 𝑥5
7
Ejemplo 1
vi) Se puede elegir al menos una de
las inversiones 1,2,3 o al menos
dos de entre 2,4,5,6.
Tenemos que
𝑥1 + 𝑥2 + 𝑥3 ≥ 1 𝑜
𝑥2 + 𝑥4 + 𝑥5 + 𝑥6 ≥ 2
8
Ejemplo 1
vi) Se puede elegir al menos una de
las inversiones 1,2,3 o al menos
dos de entre 2,4,5,6.
Usando la formulación “o bien” nos quedaría:
𝑥1 + 𝑥2 + 𝑥3 ≥ 1 − 𝑀𝑦
𝑥2 + 𝑥4 + 𝑥5 + 𝑥6 ≥ 2 − M 1 − y
𝑦 = {0,1}
9
Ejemplo 2: Programación
Entera
Un equipo de gimnasia consta de 6 personas. Hay que escoger 3
de ellas para que participen en la barra de equilibrio y en los
ejercicios de suelo, a la vez. También deben inscribir a 4
personas en cada evento. En la tabla se muestran las
calificaciones que cada gimnasta puede obtener.
Formule un problema de PE para maximizar la calificación total
obtenida por los gimnasta.
Barra de equilibrio
Ejercicios de suelo
Gimnasta 1
8,8
7,9
Gimnasta 2
9,4
8,3
Gimnasta 3
9,2
8,5
Gimnasta 4
7,5
8,7
Gimnasta 5
8,7
8,1
Gimnasta 6
9,1
8,6
10
Ejemplo 2
Definamos las variables:
𝑥𝑖𝑗 =
1 𝑠𝑖 𝑒𝑙 𝑔𝑖𝑚𝑛𝑎𝑠𝑡𝑎 𝑖 − é𝑠𝑖𝑚𝑜 𝑖 = 1, … , 6 𝑝𝑎𝑟𝑡𝑖𝑐𝑖𝑝𝑎 𝑒𝑛 𝑒𝑙 𝑒𝑗𝑒𝑟𝑐𝑖𝑐𝑖𝑜 𝑗 − é𝑠𝑖𝑚𝑜 (𝑗 = 𝑏𝑎𝑟𝑟𝑎, 𝑠𝑢𝑒𝑙𝑜)
0 𝑙𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
𝑀𝑎𝑥 𝑍 = 8,8𝑥11 + 7,9𝑥12 + 9,4𝑥21 + 8,3𝑥22 + 9,2𝑥31 + 8,5𝑥32
+ 7,5𝑥41 + 8,7𝑥42 + 8,7𝑥51 + 8,1𝑥52 + 9,1𝑥61 + 8,6𝑥62
s.a
𝑥11 + 𝑥12 ≤ 2
𝑥21 + 𝑥22 ≤ 2
𝑥31 + 𝑥32 ≤ 2
𝑥41 + 𝑥42 ≤ 2
𝑥51 + 𝑥52 ≤ 2
𝑥61 + 𝑥62 ≤ 2
𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 + 𝑥51 + 𝑥61 = 4
𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 + 𝑥52 + 𝑥62 = 4
11
Ejemplo 3: Programación
Entera
Resolver mediante el método de ramificar y acotar.
𝑀𝑎𝑥 𝑍 = 5𝑥1 + 27𝑥2
𝑠. 𝑎
2𝑥1 + 11𝑥2 ≤ 59
𝑥1 − 𝑥2 ≤ 7
𝑥1 , 𝑥2 ≥ 0 𝑦 𝑒𝑛𝑡𝑒𝑟𝑎𝑠
Solución:
𝑍 = 1895/13
𝑥1 = 136/13 = 10,4615
𝑥2 = 45/13 = 3,4615
Si intentamos redondear
cumpliéndose las restricciones
podríamos dar una solución:
𝑍 = 131
𝑥1 = 10
𝑥2 = 3
12
1
X1=10,4615
Ejemplo 3
X2=3,4615
Z=145,7692
X1≤10
X1≥11
2
X1=10
X2=2,5454
Z=145,7273
X2≤3
3
No factible
X2≥4
4
X1=10
X2=3
Z=131
5
X1=7,5
X2=4
Z=145,5
X1≤7
X1≥8
6
X1=7
X2=4,09
Z=145,4545
X2≤4
7
No factible
X2≥5
13
8
X1=7
X2=4
Z=143
9
X1=2
X2=5
Z=145
Mejor
solución
Ejemplo 4: Dualidad
Dado el siguiente problema primal
max 𝑍 = 3𝑥1 + 8𝑥2 + 6𝑥_3
𝑠. 𝑎
4𝑥1 + 3𝑥2 − 6𝑥3 ≤ 12
−𝑥1 + 𝑥2 ≤ 2
2𝑥1 − 4𝑥2 + 2𝑥3 ≤ 8
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
a)
Obtenga el dual asociado.
b) Sabiendo que la solución primal es 𝑧 = 982, 𝑥1 = 54, 𝑥2 = 56,
𝑥3 = 62 obtenga la solución del dual sin resolver por simplex.
14
Ejemplo 4
a) Obtenga el dual asociado
min 𝑤 = 12𝑦1 + 2𝑦2 + 8𝑦3
𝑠. 𝑎
4𝑦1 − 𝑦2 + 2𝑦3 ≥ 3
3𝑦1 + 𝑦2 − 4𝑦3 ≥ 8
−6𝑦1 + 2𝑦3 ≥ 6
𝑦1 , 𝑦2 , 𝑦3 ≥ 0
15
Ejemplo 4
b) Conocida la solución primal 𝑉𝐵 = 𝑥1 , 𝑥2 , 𝑥3 , 𝐶𝐵 = 3,8,6 ,
el vector de soluciones del problema dual asociado se
determina con 𝜋 = 𝐶𝐵 𝐵−1 , donde la matriz B está formada
por los coeficientes en las restricciones de las variables
básicas 𝑉𝐵 = 𝑥1 , 𝑥2 , 𝑥3
1 9
4
3 −6
𝐵 = −1 1
0 ⇒ 𝐵 −1 = 1 10
1 11
2 −4 2
3
3
3,5
por lo que 𝜋 = 𝐶𝐵 𝐵−1 = 17, 173, 54
Entonces 𝑦1 = 17, 𝑦2 = 173, 𝑦3 = 54
16
Ejemplo 5: Sensibilidad con
Simplex Revisado
Giapetto’s Woodcarving, Inc., fabrica dos tipos de juguetes de
madera: soldados y trenes. Un soldado se vende en U$27 y
requiere U$10 de materia prima. Cada soldado que se fabrica
incrementa la mano de obra variable y los costos globales de
Giapetto en U$14. Un tren se vende en U$21 y utiliza U$9 de su
valor en materia prima. Todos los trenes fabricados aumentan la
mano de obra variable y los costos globales de Giapetto en U$10.
La fabricación de soldados y trenes de madera requiere dos tipos
de mano de obra especializada: carpintería y acabados. Un
soldado necesita dos horas de trabajo acabado y una hora de
carpintería. Un tren requiere una hora de acabado y una hora de
carpintería. Todas las semanas, Giapetto consigue todo el
material necesario, pero solo 100 horas de trabajo de acabado y
80 de carpintería. La demanda de trenes es ilimitada, pero se
venden como mucho 40 soldados por semana.
17
Ejemplo 5
Soldados (X1)
Trenes (X2)
Precio
US$270
US$210
Costo MP
US$100
US$90
Costo MO +
Costos globales
US$140
US$100
Disponibilidad
Horas de
acabado
2
1
100
Horas de
carpintería
1
1
80
Ventas
40
∞
18
Ejemplo 5
a)
Formule un PL para maximizar la ganancia semanal de la empresa
de juguetes. Obtenga la solución sabiendo que en la tabla del
óptimo las VB son [𝑥1 , 𝑥2 , ℎ3 ]
𝑥1 = 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠 𝑓𝑎𝑏𝑟𝑖𝑐𝑎𝑑𝑜𝑠 𝑐𝑎𝑑𝑎 𝑠𝑒𝑚𝑎𝑛𝑎
𝑥2 = 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑡𝑟𝑒𝑛𝑒𝑠 𝑓𝑎𝑏𝑟𝑖𝑐𝑎𝑑𝑜𝑠 𝑐𝑎𝑑𝑎 𝑠𝑒𝑚𝑎𝑛𝑎
𝐹. 𝑂. max 𝑧 = 30𝑥1 + 20𝑥2
𝑠. 𝑎
2𝑥1 + 𝑥2 ≤ 100 𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑎𝑐𝑎𝑏𝑎𝑑𝑜
𝑥1 + 𝑥2 ≤ 80 𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎
𝑥1
≤ 40 𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖𝑝𝑜𝑛 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠
𝑥1 , 𝑥2
≥0
𝑁. 𝑁.
19
La solución es 𝑧 = 1800 𝑈𝑆$, 𝑋1 = 20, 𝑋2 = 60
Ejemplo 5
b) Demuéstrese que la base actual permanecerá óptima en
tanto que los soldados aporten entre 20 y 40 US$ a las
utilidades. Encontrar la nueva solución óptima si los
soldados contribuyen con US$35 a la utilidad.
El nuevo valor de z es 1900 US$
20
Ejemplo 5
c)
¿Para qué valores de la ganancia de la ganancia de los trenes las
VB permanecerán óptimas?
Para aquellos valores que aporten un valor de
[15, 30] en la utilidad.
d) ¿Para qué intervalo de horas de acabado la base actual será
óptima? Encontrar la nueva solución si se dispone de 90 horas de
acabado.
Si cambiamos el coeficiente de la primera restricción en el
intervalo [80, 120] las variables básicas son las mismas.
La nueva solución sería US$1.700
21
Ejemplo 5
e) Demostrar que la nueva base actual seguirá siendo óptima
en tanto la demanda de soldados sea por lo menos de 20.
f)
La empresa considera la opción de fabricar barcos de
juguete. Para un barco se necesitan 2 horas de acabado y
una de carpintería. La demanda no tendría límite y
contribuye con 35 US$ a la utilidad, ¿tendría que producir la
empresa barcos de juguete?
𝑆𝑒𝑎 𝑥3 = 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑏𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑗𝑢𝑔𝑢𝑒𝑡𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑜𝑠 𝑐𝑎𝑑𝑎 𝑠𝑒𝑚𝑎𝑛𝑎.
𝑥3 es variable básica, entonces se producirían barcos de
juguete.
22