IN3701 - Modelamiento y Optimización
CONTROL 2 - PAUTA
Profesor: Fernando Ordóñez
Auxiliares: Germán Silva, Ignacio Villarreal
Ayudantes: Felipe Aguad, Agustı́n Hilcker, Mariana Quiroga, Diego Riveros, Keyla Sandoval, Antonia Villegas
Instrucciones
3 Preguntas, cada pregunta puede recibir una evaluación entre 1.0 y 7.0. La resolución, redacción de las
respuestas y entrega del Control es individual. ¡Muestre su trabajo! Justifique sus respuestas, explique sus
razonamientos.
• El Tiempo estimado de lectura y resolución del Control es de 3 horas.
• El desarrollo del Control debe ser entregados en hojas separadas por pregunta. Cada hoja debe tener su
nombre y el número de la pregunta que corresponde el desarrollo.
PRIMAL Minimizar Maximizar DUAL
≥ bi ≥0
restricciones ≤ bi ≤0 variables −1
a b 1 d −b
= bi Libre =
c d ad − cb −c a
≥0 ≤ cj
variables ≤0 ≥ cj restricciones
Libre = cj
¡Que les vaya bien!
1 P1. Simplex y Sensibilidad
min 3x1 +4x2
s.a. x1 +x2 +4x3 =9
5x1 −2x2 −3x4 = 4
x1 , x2 , x3 , x4 ≥ 0
1. (1.2 ptos) Muestre que la solución con variables basicas x1 y x3 es solución basica factible y óptima.
1
1 4 −1 0 5
R: La matriz asociada a esas variables básicas es B = y su inversa es B = 1 −1 . (0.4
5 0 4 20
puntos)
Recordemos que una base B se dice óptima si:
(a) B −1 b ≥ 0 y
(b) c′ = c′ − c′B B −1 A ≥ 0
1
Veamos si B cumple los criterios de optimalidad.
1
4
9 05 5
Para (a) es hacer la multiplicación 1 = 41 donde notamos que claramente ≥ 0, por lo
−1
4 4 20 20
que la factibilidad la tenemos (0.3 puntos).
Para (b) analicemos los costos reducidos de las variables no básicas (pues las variables básicas tienen
costos reducidos iguales a cero). Estos son los siguientes:
1
0 5 1 6 26
cx2 = 4 − (3, 0) 1 −1 =4+ 5 = 5 ≥0
4 20 −2
1
0 5 0 3
cx4 = 0 − (3, 0) 1 −1 =0+ 5 ≥0
4 20 −1
Por lo que (b) se cumple al tener costos reducidos no negativos (0.3 puntos), juntando con que el punto
es factible por (a) se muestra lo pedido (0.2 puntos).
2. (1.2 ptos) Escriba el problema dual.
R: El dual es:
max 9y1 +4y2
s.a. y1 +5y2 ≤3
y1 −2y2 ≤4
4y1 ≤0
−3y2 ≤0
3. (1.2 ptos) Sea B = AB la matriz de columnas de variables basicas de la parte 1. Sea c el vector de costos.
Calcule y ⊤ = c⊤ −1
B B . Argumente que y es una soluciónóptima para el problema dual.
1
R: Calculemos lo pedido: y ⊤ = c⊤ −1 = (3, 0) 0 5 = (0, 35 ) (0.6 puntos)
BB 1 −1
4 20
Hay que ver, antes de argumentar si y es óptimo dual, si efectivamente es factible. Esto se puede realizar
de manera directa viendo que el punto obtenido no rompe ninguna de las restricciones duales.
Como existe óptimo en el primal se cumple dualidad fuerte, por lo que si y es óptima cumple bT y =
bT B −1 cB = cT x, es decir, los valores objetivos en el óptimo son iguales.
Esto se corrobora también con los datos del problema, viendo que el valor objetivo del óptimo primal es
3x1 = 3 54 = 12
5 .
De y serı́a 4y2 = 4 35 = 12
5 , por lo que tenemos que efectivamente se cumple dualidad fuerte y ası́ concluimos
que y es una solución óptima para el problema dual.
Otro camino era trabajar algebraicamente, viendo que como los elementos de la siguiente igualdad son
escalares, se obtiene lo siguiente trabajando bT y:
bT y = bT B −1 cB = cTB B −1 b = cT x
2
Donde vemos que por dualidad fuerte y dado el y entregado podemos afirmar sin calcular de manera
directa que es esta la solución óptima del dual.
(0.6 puntos por cualquier camino, notando que en ambos se debı́a invocar dualidad fuerte
de manera correcta).
4. (1.2 ptos) ¿Cuál es el rango de cambio del coeficiente b1 = 9 tal que la solución actual siga óptima?
R: Una información importante a tener en cuenta, es que a cambios del vector b, el criterio de optimalidad
no se ve afectado mientras estemos en la misma base, por lo tanto el único criterio que debemos tener en
cuenta es el de factibilidad, es decir, x ≥ 0 (0.3 puntos por notar esto, o por hacer el cálculo y
llegar a la misma conclusión.
Algebraicamente, lo que estamos viendo es que A−1 b (b + θ · e1 ) ≥ 0, donde θ es una tasa de variación, y ei
es un vector unitario con un 1 en la i-esima coordenada.
pero notando que que A−1 −1
b b = xb , se tiene que la condición queda de la forma xb + Ab θ · e1 Sea g igual a
la primera columna de la matriz A−1b , entonces la condición nos queda finalmente
xb + θg ≥ 0
donde reemplazando por los valores obtenidos anteriormente, se obtiene que la ecuación es (0.4 puntos)
4
5 +θ·0≥0
41 1
20 + θ · 4 ≥ 0
La primera claramente no entrega información, pues es verdadera siempre. De la segunda podemos
despejar el θ obteniendo que θ ≥ −41 −41
5 . Ası́, el rango pedido es [ 5 , ∞) (0.5 puntos)
5. (1.2 ptos) ¿Cuanto cambia la función objetivo si el coeficiente b1 = 9 aumenta a 11? Asuma que el cambio
en el lado derecho es factible.
R: Por el concepto de precio sombra sabemos que serı́a 2y1 , y como en el tercer inciso vimos que y1 = 0,
el cambio serı́a nulo.
2 P2. Simplex y dualidad
1. Responda las siguientes preguntas. Para esto considere un problema de forma estándar min cT x : Ax =
b, x ≥ 0. Justifique su respuesta con una demostración, contraejemplo o ejemplo.
(a) (1.5 pto) V/F: Si x∗ es solución óptima degenerada (i.e. al menos una variable basica es =0) entonces
toda base B de esta solución tiene costos reducidos c ≥ 0.
R: Falso. La clave está en el ‘toda base’, ya que esto puede pasar, pero no necesariamente en todas (1
punto). Basta dar un ejemplo donde alguna base en algún problema den costos c̄ < 0 (0.5 puntos
por el ejemplo/demostración).
3
(b) (1.5 pto) V/F: Suponga que el método de Simplex está en la solución x y que luego de 10 iteraciones
está nuevamente en la solución x. En esta situación estos 10 pivotes son degenerados, es decir con
paso θ∗ = 0.
R: Verdadero, es una situación que siempre ocurrirá debido a las caracterı́sticas del problema (1
punto). Hay varias formas de argumentarlo, pero una posible es mediante la demostración contrar-
recı́proca: Sea un pivote no-degenerado, es decir, θ∗ > 0, entonces el punto después de esa iteración
es un x′ < x, con c′ x′ < c′ x. Entonces, como el método de simplex no puede ir a una solución peor,
no podrı́a terminar en x después de 10 iteraciones. Ası́, se verifica la contrarrecı́proca y la afirmación
original es entonces verdadera (0.5 puntos).
(c) (1.5 pto) De un ejemplo donde la perturbación del lado derecho de una restricción solo tiene un lim-
ite inferior para mantener la solución actual óptima. Describa el problema y la cota a la perturbación.
R: Cualquier ejemplo correcto da todo el puntaje, si describen bien el problema pero tiene cota
inerior y superior (debı́a tener solo cota inferior), dar 1 pto solamente. Para ejemplificar, podemos
usar de manera conveniente el problema presentado en la pregunta 1, donde se modificaba el lado
derecho de la primera restricción.
min 3x1 +4x2
s.a. x1 +x2 +4x3 =9
5x1 −2x2 −3x4 = 4
x1 , x2 , x3 , x4 ≥ 0
Algebraicamente, lo que estamos viendo es que A−1 b (b + θ · e1 ) ≥ 0, donde θ es una tasa de variación, y ei
es un vector unitario con un 1 en la i-esima coordenada.
pero notando que que A−1 −1
b b = xb , se tiene que la condición queda de la forma xb + Ab θ · e1 Sea g igual a
la primera columna de la matriz A−1b , entonces la condición nos queda finalmente
xb + θg ≥ 0
donde reemplazando por los valores obtenidos en la pregunta 1, se obtiene que la ecuación es
4
5 +θ·0≥0
41 1
20 + θ · 4 ≥ 0
La primera claramente no entrega información, pues es verdadera siempre. De la segunda podemos
despejar el θ obteniendo que θ ≥ −41 −41
5 . Ası́, el rango pedido es [ 5 , ∞), donde lo importante es notar
que la perturbación al lado derecho únicamente tiene esta cota inferior para mantener la solución actual
óptima.
2. (1.5 pto) Considere el siguiente sistema de desigualdades y ecuaciones
3x1 +ax2 −2x3 ≤ 3
bx1 −5x2 ≥c
x2 ≥ 0, x3 ≤ 0
Encuentre el sistema de desigualdades/ecuaciones alternante para este sistema.
4
R: Nos apoyaremos en el Lema de Farkas para encontrar el sistema alternante para este sistema. Primero,
pasemos el problema que nos entrega el enunciado a forma estándar para tener un problema equivalente
que en caso de cumplirse, sea como la afirmación (a) del Lema. Como x1 es libre lo trabajamos como
− −
x1 = x+ +
1 − x1 con x1 ≥ 0 y x1 ≥ 0. Como x3 tiene una restricción de signo que no va con un problema en
forma estándar, usamos el cambio de variable x3 = −x3 . Además, agregamos variables de holgura para
que queden restricciones de igualdad. Juntando todo esto, el problema queda (0.5 puntos):
3x +
1 −3x −
1 +ax2 +2x3 +x4 =3
bx 1 −bx −
+
1 −5x 2 −x 5 =c
+ −
x1 , x1 , x2 , x3 , x4 , x5 ≥ 0
Con esto tenemos que si el sistema de desigualdades es factible, la afirmación (a) de Farkas se cumple
(Existe
un vector x ∈ Rn ,
x ≥ 0, tal
que
Ax = b) (0.5 puntos por enunciar el lema). En este caso A
3 −3 a 2 1 0 3
= yb= .
b −b −5 0 0 −1 c
Entonces, si existe un vector x ∈ Rn , x ≥ 0, tal que Ax = b, apoyándonos en el Lema de Farkas sabemos
⊺ ⊺
de la forma y A ≥ 0,y b < 0 con la matriz
que su alternante será A y el vector b explicitados arriba.
3 −3 a 2 1 0 3
Quedando: (y1 y2 ) ≥ 0 y (y1 y2 ) < 0. Por el lema de Farkas, sabemos que
b −b −5 0 0 −1 c
exactamente se cumplirá uno de estas desigualdades, de ahı́ la alternancia (0.5 puntos por el resultado
y la conclusión final).
3 Particiónes de proyectos y dualidad
Sea un conjunto de n proyectos N = {1, . . . , n}. El tiempo necesario para realizar un grupo de estos proyectos
puede ser distinto la suma de los tiempos de cada proyecto, debido a tiempos de set up o posibles ahorros. Por
ejemplo, si N = {1, 2, 3}, los tiempos de ejecución pueden ser:
S ∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
T (S) 0 3 5 4 9 6 7 12
El problema de particionar los proyectos en subconjuntos que requieran el menor tiempo de realización es:
X
min T (S)xS
S∈P(N )
(P )
X
s.a. xS = 1 i∈N
S | i∈S
xS ∈ {0, 1} S ∈ P(N )
donde P(N ) = {S | S ⊂ N } son los subconjuntos de N y xS es la decision de seleccionar el conjunto S o no.
1. (1.5 pto) Escriba el problema (P ) para la instancia descrita en la tabla.
R: La idea de este apartado es quitar las sumatorias usando los datos del enunciado. Ası́, se tiene (0.3
5
por cada restricción, 0.4 por la función objetivo, 0.2 por naturaleza de las variables):
min 3x1 + 5x2 + 4x3 + 9x4 + 6x5 + 7x6 + 12x7
s.a. x1 + x4 + x5 + x7 = 1
(P ) x2 + x4 + x6 + x7 = 1
x3 + x5 + x6 + x7 = 1
x1 , x2 , x3 , x4 , x5 , x6 , x7 ∈ {0, 1}
Nota: Alguna gente puede haber escrito x4 como x1,2 , lo cual también está bien. Aplica también para x5 ,
x6 y x7 .
2. (1.5 pto) Encuentre el dual de la relajación lineal del problema escrito en la parte 1.
R: El dual asociado es el siguiente (Si hay algún error en los signos, descontar 0.2. Si hay más
de 3 errores, descontar 0.5):
max y1 + y2 + y3
s.a. y1 ≤ 3
y2 ≤ 5
y3 ≤ 4
(D) y1 + y2 ≤ 9
y1 + y3 ≤ 6
y2 + y3 ≤ 7
y1 + y2 + y3 ≤ 12
y1 , y2 , y3 son libres
3. (1.5 pto) Resuelva la relajación lineal del problema de la parte 1 y su dual. ¿Cuales son las soluciones
primal y dual óptima? ¿Cuál es el valor óptimo? (Hint: resolver problemas por inspección / holgura
complementaria)
R: Notemos por inspección que el óptimo del Primal ocurre cuando se ejecuta los subgrupos {1} y {2, 3},
es decir, x1 = 1 y x6 = 1, resultando en el óptimo x∗ = (1, 0, 0, 0, 0, 1, 0) (0.3 puntos). Luego, planteando
las ecuaciones del THC, se tiene (0.5 puntos):
y1∗ (x1 + x4 + x5 + x7 − 1) = 0 (1)
y2∗ (x2 + x4 + x6 + x7 − 1) =0 (2)
y3∗ (x3 + x5 + x6 + x7 − 1) =0 (3)
x∗1 (y1 − 3) = 0 (4)
x∗2 (y2 − 5) = 0 (5)
x∗3 (y3 − 4) = 0 (6)
x∗4 (y1 + y2 − 9) = 0 (7)
x∗5 (y1 + y3 − 6) = 0 (8)
x∗6 (y2 + y3 − 7) = 0 (9)
x∗7 (y1 + y2 + y3 − 12) = 0 (10)
Reemplazando el óptimo del Primal, sólo sobreviven las ecuaciones (4) y (9). De (4) se obtiene que
y1∗ = 3, mientras que de (9) se obtiene que y2 + y3 = 7. Por ende, la solución del dual es y ∗ = (3, y2∗ , y3∗ ),
con y2∗ , y3∗ ∈ R tales que y2∗ + y3∗ = 7 (0.4 puntos). Reemplazando ambos óptimos en sus respectivos
problemas, se obtiene que el valor óptimo es z = 10 (0.3 puntos).
6
4. (1.5 pto) Escriba el dual para el problema (P ) en el caso genérico.
R: Ahora veremos el caso genérico. Sean los proyectos N = {1, 2, . . . , n}, tenemos entonces el siguiente
dual (0.5 puntos por la función objetivo, 0.7 puntos por la restricción general, 0.3 por la
naturaleza de las variables):
P
max P i∈N yi
(Dgen) s.a. { i∈S yi ≤ T (S)}S∈P(N )
yi son libres, ∀i ∈ N