Download - Ejercicios de Programación Matemática
Ejercicios de Programacion
Matematica
Christian Villalobos
ultima revision: 7 de agosto de 2009
2
C O M M O N S D E E D
Reconocimiento-NoComercial-SinObraDerivada 2.0 Chile
Usted es libre de:
copiar, distribuir y comunicar publicamente la obra
Bajo las condiciones siguientes:
Reconocimiento. Debe reconocer y citar al autor original.
No comercial. No puede utilizar esta obra para fines comerciales.
Sin obras derivadas. No se puede alterar, transformar o generaruna obra derivada a partir de esta obra,
Al reutilizar o distribuir la obra, tiene que dejar bien claro los terminosde la licencia de esta obra.
Alguna de estas condiciones puede no aplicarse si se obtiene el permisodel titular de los derechos de autor.
Los derechos derivados de usos legıtimos u otras limitaciones no seven afectados por lo anterior.
Indice general
1. Metodo de Doble Descripcion 5
2. Metodo Simplex Revisado 41
3. Fase I del Metodo Simplex 57
4. Simplex con Inversa de Base Explıcita 75
5. Simplex con Cotas 95
6. Problema de Transporte 119
7. Simplex de Redes 135
8. Flujo Maximal en Redes 153
9. Metodo de Dantzig-Wolfe 159
10.Dualidad en Programacion Lineal 189
11.Programacion Entera 195
3
4 INDICE GENERAL
Capıtulo 1
Metodo de Doble
Descripcion
Ejercicio 1.1 M.D.D. (Artıculo de Poliedros)
Considere el siguiente poliedro convexo cerrado P definido por el sistema dedesigualdades no-homogeneas:
x1−x2+x3−x4+x5 ≥ 1
x1− −x4+x5 ≥ 1
x2+x3 −x5 ≥−1
−x1 +x4−x5 ≥−1
−x1−x2 ≥−1
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥ 0
x5 ≥ 0
Determine mediante el Metodo de Doble Descripcion (M.D.D), una represen-tacion parametrica esencial de P , en funcion de los puntos y direcciones extremasde P .
5
6 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Primero se debe homogeneizar el sistema:
x1−x2+x3−x4+x5−x6 ≥ 0
x1− −x4+x5−x6 ≥ 0
x2+x3 −x5+x6 ≥ 0
−x1 +x4−x5+x6 ≥ 0
−x1−x2 +x6 ≥ 0
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥ 0
x5 ≥ 0
x6 ≥ 0
El primer cuadrante, definido por las restricciones de no-negatividad de lasvariables, nos permiten formar el Tableau inicial:
(1) (2) (3) (4) (5) (6)
x1 1 0 0 0 0 0x2 0 1 0 0 0 0x3 0 0 1 0 0 0x4 0 0 0 1 0 0x5 0 0 0 0 1 0x6 0 0 0 0 0 1
→ A1x 1 −1 1 −1 1 −1
Segundo Tableau:
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)
x1 1 0 0 1 0 0 1 0 0 1 0 0x2 0 0 0 1 1 1 0 0 0 0 0 0x3 0 1 0 0 1 0 0 1 0 0 1 0x4 0 0 0 0 0 0 1 1 1 0 0 0x5 0 0 1 0 0 1 0 0 1 0 0 1x6 0 0 0 0 0 0 0 0 0 1 1 1
A1x 1 1 1 0 0 0 0 0 0 0 0 0→ A2x 1 0 1 1 0 1 0 −1 0 0 −1 0
7
Tercer Tableau:
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
x1 1 0 0 1 0 0 1 0 1 0x2 0 0 0 1 1 1 0 0 0 0x3 0 1 0 0 1 0 0 0 0 0x4 0 0 0 0 0 0 1 1 0 0x5 0 0 1 0 0 1 0 1 0 1x6 0 0 0 0 0 0 0 0 1 1
A1x 1 1 1 0 0 0 0 0 0 0A2x 1 0 1 1 0 1 0 0 0 0
→ A3x 0 1 −1 1 2 0 0 −1 1 0
Cuarto Tableau:
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (S)
x1 1 0 1 0 0 1 1 0 0 0 0 1x2 0 0 1 1 1 0 0 0 0 0 1 0x3 0 1 0 1 0 0 0 0 1 1 1 0x4 0 0 0 0 0 1 0 0 0 1 2 1x5 0 0 0 0 1 0 0 1 1 1 2 1x6 0 0 0 0 0 0 1 1 0 0 0 1
A1x 1 1 0 0 0 0 0 0 2 1 0 0A2x 1 0 1 0 1 0 0 0 1 0 0 0A3x 0 1 1 2 0 0 1 0 0 0 0 0
→ A4x −1 0 −1 0 −1 0 0 0 −1 0 0 0
Quinto Tableau:
(1) (2) (3) (4) (5) (6) (7)
x1 0 0 1 1 0 0 0x2 0 1 0 0 0 0 1x3 1 1 0 0 0 1 1x4 0 0 1 0 0 1 2x5 0 0 0 0 1 1 2x6 0 0 0 1 1 0 0
A1x 1 0 0 0 0 1 0A2x 0 0 0 0 0 0 0A3x 1 2 0 1 0 0 0A4x 0 0 0 0 0 0 0
→ A5x 0 −1 −1 0 1 0 −1
8 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Sexto Tableau:
(1) (2) (3) (4) (5) (6) (7)
x1 0 1 0 0 0 1 0x2 0 0 0 0 1 0 1
x3 1 0 0 1 1 0 1 (∗)
x4 0 0 0 1 0 1 2
x5 0 0 1 1 1 1 3 (∗)
x6 0 1 1 0 1 1 1 (∗)
A1x 1 0 0 1 0 0 0A2x 0 0 0 0 0 0 0A3x 1 1 0 0 2 0 0A4x 0 0 0 0 0 0 0A5x 0 0 1 0 0 0 0
donde las ecuaciones (∗) son redundantes.
Ası, el conjunto de generadores del cono homogeneo determinado por elsistema de inecuaciones homogeneas es:
001000
,
10000
1
,
00001
1
,
001110
,
01101
1
,
10011
1
,
01123
1
.
Los puntos extremos del poliedro ∆ son:
P 1 =1
1
10000
=
10000
, P 2 =1
1
00001
=
00001
, P 3 =1
1
01101
=
01101
,
P 4 =1
1
10011
=
10011
y P 5 =1
1
01123
=
01123
;
y las direcciones asintoticas del cono C:
C1 =
00100
y C2 =
00111
.
9
Como las restricciones de no-negatividad asociadas a las variables 3, 5 y 6son redundantes, el sistema original se puede escribir como:
x1−x2+x3−x4+x5 ≥ 1
x1− −x4+x5 ≥ 1
x2+x3 −x5 ≥−1
−x1 +x4−x5 ≥−1
−x1−x2 ≥−1
x1 ≥ 0
x2 ≥ 0
x4 ≥ 0.
10 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Ejercicio 1.2 (†)
Dado el conjunto de puntos de R :
{(
33
)
,
(
52
)
,
(
13
)
,
(
21
)
,
(
27
)}
, se pide
determinar un sistema de desigualdades esenciales que defina, de manera equi-valente, el poliedro convexo cerrado P , P = ∆ + C, dado por la suma de la en-voltura convexa de estos puntos (es decir, el poliedro convexo cerrado acotado∆) y el cono poliedrico homogeneo C generado por las direcciones extremas
dadas:
{(
12
)
,
(
21
)}
.
Solucion
Es inmediato que el primer punto es igual a la suma del cuarto punto, masla primera direccion extrema, ası que lo eliminaremos del conjunto de puntosque define ∆1.
El poliedro en cuestion claramente no contiene el origen. Ası, es necesariouna traslacion de puntos al origen. En este caso se trasladara el punto (2, 1)T
al origen. Haciendo el siguiente cambio de coordenadas:
y1 = y1 − 2
y2 = y2 − 1,
obtenemos los siguientes puntos que definen a ∆:{(
31
)
,
(
−12
)
,
(
00
)
,
(
06
)}
.
Ahora construimos los generadores del cono caracterıstico K, asociado a P :
B1 =
311
, B2 =
−121
, B3 =
001
, B4 =
061
, B5 =
120
y B6 =
210
.
Con estos vectores, podemos construir el sistema homogeneo dual BjTy:
3y1+y2 +y3≥0
−y1 +2y2+y3≥0
y3≥0
6y2+y3≥0
y1 +2y2 ≥0
2y1+y2 ≥0.
1No es necesario darse cuenta que este punto debe ser eliminado. En caso de no eliminarlo,los resultados finales son los mismos y la restriccion polar asociada a este punto resulta serredundante.
11
Ordenando, nos queda:
3y1 +y2 +y3≥0
−y1 +2y2 +y3≥0
6y2 +y3≥0
y1 +2y2 ≥0
2y1 +y2 ≥0
(y1)
(y2)
y3≥0.
La matriz A asociada a este sistema es:
3 1 1−1 2 10 6 11 2 02 1 00 0 1
.
Teniendo en cuenta que las variables 1 y 2 son libres, construimos el primertableau:
(1) (2) (3) (4) (5)
1 −1 0 0 00 0 1 −1 0
A6y 0 0 0 0 1→ A1y 3 −3 1 −1 1
Segundo Tableau:
(1) (2) (3) (4)
1 −1 1 −1−3 3 0 0
A6y 0 0 0 3
A1y 0 0 3 0→ A2y −7 7 −1 4
Tercer Tableau:(1) (2) (3)
−1 6 −33 3 −12
A6y 0 0 21
A1y 0 21 0
A2y 7 0 0
12 CAPITULO 1. METODO DE DOBLE DESCRIPCION
que simplificado nos queda:
(1) (2) (3)
−1 2 −13 1 −4
A6y 0 0 7
A1y 0 7 0
A2y 7 0 0→ A3y 18 6 −17
Cuarto Tableau:
(1) (2) (3) (4)
−1 2 −35 283 1 −21 −7
A6y 0 0 126 42
A1y 0 7 0 119
A2y 7 0 119 0
A3y 18 6 0 0
que simplificado nos queda:
(1) (2) (3) (4)
−1 2 −5 43 1 −3 −1
A6y 0 0 18 6
A1y 0 7 0 17
A2y 7 0 17 0
A3y 18 6 0 0→ A4y 5 4 −11 2
Quinto Tableau:
(1) (2) (3) (4) (5)
−1 2 4 −36 343 1 −1 18 −17
A6y 0 0 6 90 102
A1y 0 7 17 0 187
A2y 7 0 0 162 34
A3y 18 6 0 198 0
A4y 5 4 2 0 0
13
que simplificado nos queda:
(1) (2) (3) (4) (5)
−1 2 4 −2 23 1 −1 1 −1
A6y 0 0 6 5 6
A1y 0 7 17 0 11
A2y 7 0 0 9 2
A3y 18 6 0 11 0
A4y 5 4 2 0 0→ A5y 1 5 7 −3 3
Sexto Tableau:
(1) (2) (3) (4) (5) (6)
−1 2 4 2 −5 03 1 −1 −1 10 0
A6y 0 0 6 6 5 11
A1y 0 7 17 11 0 11
A2y 7 0 0 2 30 11
A3y 18 6 0 0 65 11
A4y 5 4 2 0 15 0
A5y 1 5 7 3 0 0
que simplificado nos queda:
(1) (2) (3) (4) (5) (6)
−1 2 4 2 −1 03 1 −1 −1 2 0
A6y 0 0 6 6 1 1
A1y 0 7 17 11 0 1
A2y 7 0 0 2 6 1
A3y 18 6 0 0 13 1
A4y 5 4 2 0 3 0
A5y 1 5 7 3 0 0
Luego de obtenidos los generadores del Dual, podemos utilizarlos como coe-ficientes del Primal:
−x1 +3x2 ≥0
2x1+x2 ≥0
4x1−x2 +6x3≥0
2x1−x2 +6x3≥0
−x1 +2x2+x3 ≥0
x3 ≥0.
14 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Igualando x3 a 1, obtenemos el sistema:
−x1 +3x2 ≥ 0
2x1+x2 ≥ 0
4x1−x2 ≥−6
2x1−x2 ≥−6
−x1 +2x2 ≥−1.
Finalmente, debemos realizar la traslacion inversa, lo que nos entrega elsistema:
−x1 +3x2 ≥ 1
2x1+x2 ≥ 5
4x1−x2 ≥ 1
2x1−x2 ≥−3
−x1 +2x2 ≥−1.
Alternativamente, podrıamos haber obtenido los generadores mediante elMetodo de Eliminacion Completa de Jordan.
Primero debemos formar la matrizIA
:
(1) (2) (3)
1 0 00 1 00 0 1
A1y 3 1 1
A2y −1 2 1
A3y 0 6 1
A4y 1 2 0
A5y 2 1 0
A6y 0 0 1
Ahora intercambiamos filas (restricciones), de modo que la parte de abajo del
15
tableau quede lo mas diagonalizada posible:
(1) (2) (3)
1 0 00 1 00 0 1
A4y 1 2 0
A3y 0 6 1
A6y 0 0 1
A1y 3 1 1
A2y −1 2 1
A5y 2 1 0
y mediante operaciones elementales columna, diagonalizamos la matriz de abajo:
(1) (2) (3)
1 −2 00 1 00 0 1
A4y 1 0 0
A3y 0 6 1
A6y 0 0 1
A1y 3 −5 1
A2y −1 4 1
A5y 2 −3 0
→
(1) (2) (3)
1 −2 20 1 −10 0 6
A4y 1 0 0
A3y 0 6 0
A6y 0 0 6
A1y 3 −5 11
A2y −1 4 2
A5y 2 −3 3
Ası, obtenemos el siguiente tableau simplificado, que ya ha considerado las res-tricciones 6, 4 y 3:
(1) (2) (3)
1 −2 2
0 1 −1
A6y 0 0 6
A4y 1 0 0
A3y 0 6 0→ A1y 3 −5 11
Segundo Tableau:
(1) (2) (3) (4)
1 2 −1 −12
0 −1 3 6
A6y 0 6 0 30
A4y 1 0 5 0
A3y 0 0 18 66
A1y 3 11 0 0
16 CAPITULO 1. METODO DE DOBLE DESCRIPCION
que simplificado nos queda:
(1) (2) (3) (4)
1 2 −1 −2
0 −1 3 1
A6y 0 6 0 5
A4y 1 0 5 0
A3y 0 0 18 11
A1y 3 11 0 0→ A2y −1 2 7 9
Tercer Tableau:
(1) (2) (3) (4) (5)
2 −1 −2 4 6
−1 3 1 −1 3
A6y 6 0 5 6 0
A4y 0 5 0 2 12
A3y 0 18 11 0 18
A1y 11 0 0 17 21
A2y 2 7 9 0 0
que simplificado nos queda:
(1) (2) (3) (4) (5)
2 −1 −2 4 2
−1 3 1 −1 1
A6y 6 0 5 6 0
A4y 0 5 0 2 4
A3y 0 18 11 0 6
A1y 11 0 0 17 7
A2y 2 7 9 0 0→ A5y 3 1 −3 7 5
17
Cuarto Tableau:
(1) (2) (3) (4) (5) (6)
2 −1 4 2 0 −5
−1 3 −1 1 0 10
A6y 6 0 6 0 11 5
A4y 0 5 2 4 0 15
A3y 0 18 0 6 11 65
A1y 11 0 17 7 11 0
A2y 2 7 0 0 11 30
A5y 3 1 7 5 0 0
que simplificado nos queda:
(1) (2) (3) (4) (5) (6)
2 −1 4 2 0 −1
−1 3 −1 1 0 2
A6y 6 0 6 0 1 1
A4y 0 5 2 4 0 3
A3y 0 18 0 6 1 13
A1y 11 0 17 7 1 0
A2y 2 7 0 0 1 6
A5y 3 1 7 5 0 0
Este ultimo tableau nos entrega los mismos generadores, pero en distintoorden.
18 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Ejercicio 1.3 (†)
Considere el poliedro convexo cerrado P definido por el sistema finito de de-sigualdades lineales amplias en R
2:
−3x1+x2 ≤−2
−x1 +x2 ≤ 2
−x1 +2x2≤ 8
−x2 ≤−2
x1 ≥ 0
x2 ≥ 0
Antes que nada, observe que P es claramente no vacıo (¿Por que?)
(i) (3 ptos.) Mediante el Metodo de Doble Descripcion (M.D.D.), determineuna representacion equivalente de P , de la forma P = ∆ + C, donde ∆ esel poliedro convexo cerrado acotado de R
2, definido como el conjunto detodos los baricentros de los puntos extremos de P ; y C, el cono asintoticoengendrado por las direcciones asintoticas extremas de P .
Para ello, encuentre primeramente, mediante el M.D.D., un conjunto esen-cial de generadores del cono de soluciones del sistema homogeneizado co-rrespondiente. Luego, explicite el conjunto de puntos extremos de P y,eventualmente, el conjunto de direcciones extremas de P , de modo deexpresar toda solucion del sistema original bajo la forma parametrica:
x =
r∑
j=1
λjPj +
s∑
l=1
µlCl,
con:
r∑
j=1
λj = 1;
λj ≥ 0; j = 1, . . . , r;
µl ≥ 0; l = 1, . . . , s;
donde{
P j}r
j=1y{
Cl}s
l=1definen el conjunto de puntos extremos y de
direcciones extremas de P , respectivamente.
19
En seguida, considere el siguiente problema de minimizacion lineal:
P)xMin
2∑
i=1
yi + η
r∑
j=1
λjPji +
s∑
l=1
µlCli + yi = xi; i = 1, 2
r∑
j=1
λj + η = 1
λj ≥ 0; j = 1, . . . , r
µl ≥ 0; l = 1, . . . , s
yi ≥ 0; i = 1, 2
η ≥ 0
(ii) (1 ptos.) Aplicando los resultados de Existencia de Soluciones Optimasen Programacion Lineal vistos en el curso, muestre que:
Cualquiera sea el punto x ∈ R2+ (es decir x ∈ R
2, x ≥ 0), el problema P)x
admite siempre solucion optima.
(iii) (1 ptos.) Si x define un punto cualquiera de R2+ (i.e. x ≥ 0 ), muestre
que: x pertenece al poliedro (i.e. x ∈ P ) si y solo si el valor optimo delproblema P)x es nulo (i.e. v
(
P)x
)
= 0)
Mas aun, muestre que si x esta en P , la solucion optima de P)x proveeuna representacion parametrica de x.
(iv) (1 ptos.) Dado x = (4, 3)T , que claramente pertenece a P (¿Por que?), de-termine una representacion parametrica de x, como combinacion convexade puntos y direcciones extremas de P .
Nota: En (iv), para resolver el problema lineal de minimizacion resultante, puedeaplicar el Metodo Simplex bajo forma Revisada o de Tableau.
20 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Solucion
(i) Se tiene el siguiente sistema de desigualdades:
−3x1+x2 ≤− 2
−x1 +x2 ≤ 2
−x1 +2x2≤ 8
−x2 ≤− 2
x1 ≥ 0
x2 ≥ 0.
El sistema homogeneizado asociado es:
3x1−x2 −2x3 ≥ 0
x1 −x2 +2x3 ≥ 0
x1 −2x2+8x3 ≥ 0
+x2 −2x3 ≥ 0
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0,
cuya matriz A asociada es:
3 −1 −21 −1 21 −2 80 1 −21 0 00 1 00 0 1
.
El primer cuadrante, definido por las restricciones de no-negatividad de lasvariables, nos permiten formar el Tableau inicial:
(1) (2) (3)
x1 1 0 0x2 0 1 0x2 0 0 1
→ A1x 3 −1 −2
Segundo Tableau:(1) (2) (3)
x1 1 1 2x2 0 3 0x3 0 0 3
A1x 3 0 0→ A2x 1 −2 8
21
Tercer Tableau2:(1) (2) (3) (4)
x1 1 2 3 6x2 0 0 3 12x3 0 3 0 3
A1x 3 0 6 0A2x 1 8 0 0
→ A3x 1 26 −3 6
Cuarto Tableau:(1) (2) (3) (4) (5)
x1 1 2 6 6 12x2 0 0 12 3 18x3 0 3 3 0 3
A1x 3 0 0 15 12A2x 1 8 0 3 0A3x 1 26 6 0 0
→ A4x 0 −6 6 3 12
Quinto Tableau:
(1) (2) (3) (4) (5)
x1 1 6 6 12 8 (∗)
x2 0 12 3 18 12 (∗)
x3 0 3 0 3 6A1x 3 0 15 12 0A2x 1 0 3 0 8A3x 1 6 0 0 32A4x 0 6 3 12 0
donde las ecuaciones (∗) son redundantes
Ası, el conjunto de generadores del cono homogeneo determinado por elsistema de inecuaciones homogeneas es:
100
,
612
3
,
630
,
1218
3
,
812
6
.
Los puntos extremos del poliedro ∆ son:
P 1 =1
3
(
612
)
=
(
24
)
, P 2 =1
3
(
1218
)
=
(
46
)
, P 3 =1
6
(
812
)
=
(
4/32
)
,
2Notese que, a partir de esta iteracion, podrıamos simplificar las columnas para obtenernumeros enteros mas pequenos.
22 CAPITULO 1. METODO DE DOBLE DESCRIPCION
y las direcciones asintoticas del cono C:
C1 =
(
10
)
y C2 =
(
21
)
La forma parametrica de representar x serıa:
x = λ1
(
24
)
+ λ2
(
46
)
+ λ3
(
4/32
)
+ µ1
(
10
)
+ µ2
(
21
)
λ1 + λ2 + λ3 = 1
λ1, λ2, λ3 ≥ 0
µ1, µ2 ≥ 0.
(ii) Si consideramos:
λj = 0; j = 1, . . . , r
µl = 0; l = 1, . . . , s
de las restricciones de igualdad de P)x, tenemos que:
yi = xi; i = 1, 2
η = 1
para cualquier valor de xi. Luego P)x 6= φ
Por otro lado, tenemos:
yi ≥ 0; i = 1, 2
η ≥ 0
}
⇒
2∑
i=1
yi + η ≥ 0 = cte.
Ası, cT x ≥ cte. y, por el Teorema de Existencia de la Programacion Lineal,P)x admite solucion optima.
(iii) Por demostrar:
x ∈ P ⇔ v(
P)x
)
= 0
Condicion necesaria
Tenemos:
x ∈ P ⇒ x =r∑
j=1
λjPj +
s∑
l=1
µlCl ⇒
{
yi = 0; i = 1, 2
η = 0
}
⇒ v(
P)x
)
= 0.
23
Condicion suficiente
Tenemos:
v(
P)x
)
= 0 ⇒
2∑
i=1
yi + η = 0
yi ≥ 0; i = 1, 2
η ≥ 0
⇒
{
yi = 0; i = 1, 2
η = 0
}
⇒
x =
r∑
j=1
λjPj +
s∑
l=1
µlCl
r∑
j=1
λj = 1;
λj ≥ 0; j = 1, . . . , r;
µl ≥ 0; l = 1, . . . , s;
⇒ x ∈ P
(iv) Se podıa resolver el problema mediante Simplex, pero dada la simplicidaddel poliedro, lo mas conveniente es graficar:
x1
x2
P 1 =(
24
)
P 2 =(
46
)
P 3 =(
4/32
)
C1 =(
10
)
C2 =(
21
)
x =(
43
)
x′ =(
23
)
se puede notar que las restricciones de no-negatividad de las variables son re-dundantes.
Primero determinamos el punto x′ =(
23
)
, que resulta de la recta que pasa a
24 CAPITULO 1. METODO DE DOBLE DESCRIPCION
traves de P 2 y P 3, evaluada en x2 = 3. Luego, teniendo en cuenta que λ1 = 0,determinamos los valores de λ2 y λ3 como:
x′ =
(
23
)
= λ2
(
46
)
+ λ3
(
4/32
)
,
de donde resulta que λ2 = 1/4 y λ3 = 3/4.
Finalmente, teniendo en cuenta que µ2 = 0, calculamos µ1 como:
x = x′ + µ1
(
10
)
,
de donde resulta que µ1 = 2.
En resumen:
λ1 = 0, λ2 = 1/4, λ3 = 3/4, µ1 = 2 y µ2 = 0.
25
Ejercicio 1.4 (†)
Considere el problema de minimizacion:
P)Min 2x1−x2 +x3
2x1+x2 −2x3≤8
4x1−x2 +2x3≥2
2x1+3x2+x3 ≥4
x1, x2, x3 ≥0
(i) Determine, Mediante el Metodo de Doble Descripcion, el conjunto de pun-tos y direcciones extremas del poliedro definido por las restricciones de P)
(ii) A partir de i) y aplicando los Teoremas de Existencia de la ProgramacionLineal, determine si P) tiene o no solucion optima. Luego, si fuese el caso,determine una solucion optima de P).
Solucion
(i) El poliedro P esta definido por las siguientes desigualdades:
2x1+ x2−2x3 ≤ 8
4x1− x2+2x3 ≥ 2
2x1+3x2+ x3 ≥ 4
x1 ≥ 0
x2 ≥ 0
x3 ≥0.
Primero se debe homogeneizar el sistema:
−2x1− x2+2x3+8x4 ≥ 0
4x1− x2+2x3−2x4 ≥ 0
2x1+3x2+ x3−4x4 ≥ 0
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥0,
26 CAPITULO 1. METODO DE DOBLE DESCRIPCION
cuya matriz A asociada es:
−2 −1 2 84 −1 2 −22 3 1 −41 0 0 00 1 0 00 0 1 00 0 0 1
El primer cuadrante, definido por las restricciones de no-negatividad de lasvariables, nos permiten formar el Tableau inicial:
(1) (2) (3) (4)
x1 1 0 0 0x2 0 1 0 0x3 0 0 1 0x4 0 0 0 1
→ A1x −2 −1 2 8
Segundo Tableau:
(1) (2) (3) (4) (5) (6)
x1 0 0 1 4 0 0x2 0 0 0 0 2 8x3 1 0 1 0 1 0x4 0 1 0 1 0 1
A1x 2 8 0 0 0 0→ A2x 2 −2 6 14 0 −10
Tercer Tableau:3
(1) (2) (3) (4) (5) (6) (7)
x1 0 1 4 0 0 4 20x2 0 0 0 2 0 0 56x3 1 1 0 1 1 0 0x4 0 0 1 0 1 8 12
A1x 2 0 0 0 10 56 0A2x 2 6 14 0 0 0 0
→ A3x 1 3 4 7 −3 −24 160
3Notese que, por simplicidad en los calculos, a partir de este punto podrıamos haber sim-plificado el Tableau
27
Cuarto Tableau:
(1) (2) (3) (4) (5) (6) (7) (8) (9)
x1 0 1 4 0 20 0 0 28 140x2 0 0 0 2 56 0 6 0 168x3 1 1 0 1 0 4 10 0 0x4 0 0 1 0 12 1 7 14 196
A1x 2 0 0 0 0 16 70 56 1120A2x 2 6 14 0 0 6 0 84 0A3x 1 3 4 7 160 0 0 0 0
donde no hay ecuaciones redundantes.
Ası, el conjunto de generadores del cono homogeneo determinado por elsistema de inecuaciones homogeneas es:
0010
,
1010
,
400
1
,
0210
,
20560
12
,
004
1
,
0610
7
,
2800
14
,
1401680
196
.
Los puntos extremos del poliedro ∆ son:
P 1 =1
1
400
=
400
, P 2 =1
12
20560
=
5/314/3
0
,
P 3 =1
1
004
=
004
, P 4 =1
7
0610
=
06/710/7
,
P 5 =1
14
2800
=
200
y P 6 =1
196
1401680
=
5/76/70
;
y las direcciones asintoticas del cono C:
C1 =
001
, C2 =
101
y C3 =
021
.
(ii) Dado que poseemos las direcciones asintoticas, demostraremos existenciahaciendo uso de ellas:
Poliedro no vacıo
Efectivamente, cualquier punto determinado en la parte (ii) pertenece a P .Por ejemplo (4, 0, 0).
28 CAPITULO 1. METODO DE DOBLE DESCRIPCION
cT Cj , j = 1, . . . , s
En este caso, para cT = (2,−1, 1), se tiene:
cT C1 = 1 ≥ 0
cT C2 = 3 ≥ 0
cT C3 = −16≥ 0
Ası, por el Teorema de Existencia de la Programacion Lineal, P) no admitesolucion optima.
29
Ejercicio 1.5
Encuentre los generadores del cono homogeneo dado por el sistema de ecuacioneslineales homogeneas en R
3:
x1 + x3 ≥ 0
x1+ x2+ 2x3 ≥ 0
2x1+ x2+ 3x3 ≥ 0
x2+ x3 ≥ 0
(x1)
(x2)
(x3)
Solucion
La matriz A asociada al sistema es:
1 0 11 1 22 1 30 1 1
Como todas las variables son libres, el tableau inicial es:
(1) (2) (3) (4) (5) (6)
1 −1 0 0 0 00 0 1 −1 0 00 0 0 0 1 −1
→ A1x 1 −1 0 0 1 −1
Segundo Tableau:
(1) (2) (3) (4) (5)
0 0 1 −1 11 −1 0 0 00 0 −1 1 0
A1x 0 0 0 0 1→ A2x 1 −1 −1 1 1
30 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Tercer Tableau:(1) (2) (3) (4)
1 −1 0 11 −1 1 −1
−1 1 0 0A1x 0 0 0 1A2x 0 0 1 0
→ A3x 0 0 1 1
Todas las nuevas entradas son positivas. Luego, la restriccion A3x ≥ 0 es redun-dante y la podemos eliminar de entrada.
Cuarto Tableau:(1) (2) (3) (4)
1 −1 0 11 −1 1 −1
−1 1 0 0A1x 0 0 0 1A2x 0 0 1 0
→ A4x 0 0 1 −1
En este caso, todas las nuevas entradas de los generadores singulares con igualesa cero. Luego, el siguiente Tableau tendra los mismos generadores singulares.Los nuevos generadores no-singulares se obtienen con el M.D.D. tradicional4.
Tableau Final5:(1) (2) (3) (4)
1 −1 0 11 −1 1 0
−1 1 0 0A1x 0 0 0 1A2x 0 0 1 1A4x 0 0 1 0
Ası, los generadores del cono son:
11−1
,
−1−11
,
010
,
100
.
donde los dos primeros son los generadores singulares (simetricos) y los dosultimos, los no-singulares.
4En este caso hay 2 generadores singulares. Por ende, la dimension del vertice del conoactual es d = 1 y los vectores a combinar deben tener (n−d)−2 = 0 ceros en comun (CondicionNecesaria a Priori). Equivalentemente, los nuevos vectores generados deben tener al menos(n − d) − 1 = 1 ceros en el Tableau (Condicion Necesaria a Posteriori). Las CondicionesNecesarias y Suficientes (tanto a Priori como a Posteriori) no cambian.
5Notar que, a partir de la parte singular de las filas de este Tableau, se puede determinarque la restriccion A2x tambien es redundante.
31
Alternativamente, podrıamos haber obtenido los generadores mediante elMetodo de Eliminacion Completa de Jordan.
Primero debemos formar la matrizIA
:
(1) (2) (3)
1 0 0
0 1 0
0 0 1
A1x 1 0 1
A2x 1 1 2
A3x 2 1 3
A4x 0 1 1
y mediante operaciones elementales sobre las columnas, se diagonaliza primera-mente una sub-matriz de rango maximo de la parte inferior del Tableau inicial,realizando eventualmente permutaciones de filas y/o columnas, en busca de unpivote de diagonalizacion 6= 0 (Metodo de Eliminacion Completa de Jordan):
(1) (2) (3)
1 0 0
0 1 0
0 0 1
A1x 1 0 1
A2x 1 1 2
A3x 2 1 3
A4x 0 1 1
→
(1) (2) (3)
1 0 −1
0 1 0
0 0 1
A1x 1 0 0
A2x 1 1 1
A3x 2 1 1
A4x 0 1 1
→
(1) (2) (3)
1 0 −1
−1 1 −1
0 0 1
A1x 1 0 0
A2x 0 1 0
A3x 1 1 0
A4x −1 1 0
Una vez finalizado el procedimiento de diagonalizacion, se cambia los signosde todas las columnas que eventualmente tuvieran elementos negativos (pivotesnegativos) en la diagonal correspondiente (en el caso de este ejericio, ninguno).
En el caso particular en que el sistema de desigualdades es de rango completo,es decir, si rango(A) = n, donde n es la dimension del espacio, la base de R
n
resultante de este procedimiento, provee igualmente un conjunto esencial degeneradores del cono poliedrico puntiagudo definido por las n restricciones dedesigualdad linealmente independientes asociadas a la matriz diagonal invertibleresultante. Este conjunto define el equivalente a la base canonica del ortante no-negativo, en el caso particular en que esta ultima matriz esta definida de entrada,por las restricciones de signo sobre las variables del sistema (caso tradicional conrestricciones de signo sobre todas las variables).
En el caso general, si rango(A) = r < n (como el caso de este ejercicio, donder = 2), se puede obtener la misma situacion anterior, completando el conjuntode las r desigualdades linealmente independientes que entrega el proceso de
32 CAPITULO 1. METODO DE DOBLE DESCRIPCION
diagonalizacion anterior (en este caso las desigualdades A1x ≥ 0 y A2x ≥ 0),con el conjunto de desigualdades LT x ≥ 0 y −LT x ≥ 0 (o, equivalentemente, deigualdades LT x = 0), donde las columnas de L definen la base del sub-espaciovertice del cono poliedrico de las soluciones del sistema original. De hecho, esfacil ver que el sistema resultante es de rango n, de tal modo que una vezincorporadas las (n− r) restricciones adicionales, dispondremos entonces de unconjunto esencial de generadores del cono poliedrico puntiagudo C, resultantede la interseccion del cono poliedrico original C, con el subespacio ortogonal alvertice del cono poliedrico de las soluciones del sistema original.
En este caso, quedan incorporadas las restricciones A1x ≥ 0 y A2x ≥ 0; y:
L =
−1−11
Para generar el tableau inicial de los generadores del cono puntiagudo C,
se debe agregar la restriccion L1Tx ≥ 0 (En realidad se debe agregar todas las
restricciones LiT x ≥ 0, donde Li son las columnas de la matriz L. En nuestrocaso es solo una columna):
(1) (2) (3)
1 0 −1−1 1 −1
0 0 1A1x 1 0 0A2x 0 1 0
→ L1Tx 0 −1 3
Tableau inicial6:
(1) (2) (3)
1 −1 −1−1 −1 2
0 1 1A1x 1 0 0A2x 0 0 3
L1Tx 0 3 0
Ahora se debe agregar la restriccion −L1Tx ≥ 0 y las restricciones que
quedaron fuera en el Metodo de Jordan (en este caso, las restricciones A3x ≥ 0
6Notese que al incorporar la restriccion L1Tx ≥ 0 se forma una matriz diagonal (salvo un
intercambio de columnas) con elementos positivos en la parte de la matriz que corresponde altableau.
33
y A4x ≥ 0).
(1) (2) (3)
1 −1 −1−1 −1 2
0 1 1A1x 1 0 0A2x 0 0 3
L1Tx 0 3 0
→ −L1Tx 0 −3 0
Segundo Tableau:
(1) (2)
1 −1−1 2
0 1A1x 1 0A2x 0 3
L1Tx 0 0
−L1Tx 0 0
→ A3x 1 3
Todas las nuevas entradas son positivas. Luego, la restriccion A3x ≥ 0 es redun-dante y la podemos eliminar de entrada.
Tercer Tableau
(1) (2)
1 −1−1 2
0 1A1x 1 0A2x 0 3
L1Tx 0 0
−L1Tx 0 0
→ A4x −1 3
Cuarto Tableau7
(1) (2)
−1 22 −11 1
A1x 0 3A2x 3 3
L1Tx 0 0
−L1Tx 0 0
A4x 3 0
7Notar que, a partir de las filas de este Tableau, se puede determinar que la restriccionA2x tambien es redundante
34 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Ası, los generadores del cono puntiagudo C son:
−121
,
2−11
.
Finalmente, el conjunto de soluciones del sistema original estara dado porla suma vectorial de este cono puntiagudo y del sub-espacio vertice original,ker(A), cuya base esta dada por las columnas de la matriz L. En otras palabrasC = C + [L], donde los generadores de C son los generadores de C mas lascolumnas de L y de −L:
−1−11
,
11−1
,
−121
,
2−11
.
Observacion 1: Para pasar al segundo Tableau se ha incorporado secuen-
cialmente las restricciones L1Tx ≥ 0 y −L1T
x ≥ 0 (que son equivalentes a
L1Tx = 0). Esto lo podrıamos haber hecho en un solo paso:
(1) (2) (3)
1 0 −1−1 1 −1
0 0 1A1x 1 0 0A2x 0 1 0
→ L1Tx 0 −1 3
(1) (2)
1 −1−1 2
0 1A1x 1 0A2x 0 3
L1Tx 0 0
donde la ultima fila tiene la restriccion L1Tx = 0.
Lo que se ha hecho es:
eliminar los generadores con nueva entrada distinta de cero
combinar los generadores con nueva entrada con distinto signo
35
Observacion 2: En este caso las direcciones no-singulares entregadas por elM.D.D:
010
,
100
.
son distintas a las entregadas por el Metodo de Jordan:
−121
,
2−11
.
Sin embargo, las direcciones generan el mismo cono. De hecho, cada una de lasdirecciones entregadas por el M.D.D. es igual a la combinacion lineal positivade una de las direcciones entregadas por el Metodo de Jordan y uno de losgeneradores del ker(A) (columnas de L). Concretamente:
1
3
−121
+1
3
11−1
=
010
1
3
2−11
+1
3
11−1
=
100
36 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Ejercicio 1.6
Encuentre los generadores del cono homogeneo dado por el sistema de ecuacioneslineales homogeneas en R
3:
2x1 −x2 ≥ 0
−x1 +2x2 ≥ 0
(x1)
(x2)
(x3)
Solucion
El cono esta dado por la figura:
0
0.5
11.5
2
0
0.5
1
1.5
2
-1
-0.5
0
0.5
1
0.5
11.5
2
-1
-0.5
0
0.5
1
x1
x2
x3
Claramente este no es un cono puntiagudo.
37
La matriz A asociada al sistema es:[
2 −1 0−1 2 0
]
Como todas las variables son libres, el tableau inicial es:
(1) (2) (3) (4) (5) (6)
1 −1 0 0 0 00 0 1 −1 0 00 0 0 0 1 −1
→ A1x 2 −2 −1 1 0 0
Segundo Tableau:
(1) (2) (3) (4) (5)
0 0 1 −1 10 0 2 −2 01 −1 0 0 0
A1x 0 0 0 0 2→ A2x 0 0 3 −3 −1
Tercer Tableau:(1) (2) (3) (4)
0 0 1 40 0 2 21 −1 0 0
A1x 0 0 0 6A2x 0 0 3 0
Ası, los generadores del cono son:
001
,
00−1
,
120
,
210
.
Alternativamente, podrıamos haber obtenido los generadores mediante elMetodo de Eliminacion Completa de Jordan.
Primero debemos formar la matrizIA
:
(1) (2) (3)
1 0 0
0 1 0
0 0 1
A1x 2 −1 0
A2x −1 2 0
38 CAPITULO 1. METODO DE DOBLE DESCRIPCION
y mediante operaciones elementales columna, diagonalizamos la matriz de abajo:
(1) (2) (3)
1 1 0
0 2 0
0 0 1
A1x 2 0 0
A2x −1 3 0
→
(1) (2) (3)
4 1 0
2 2 0
0 0 1
A1x 6 0 0
A2x 0 3 0
→
(1) (2) (3)
2 1 0
1 2 0
0 0 1
A1x 3 0 0
A2x 0 3 0
Ası, no quedan restricciones sin incorporar y:
L =
001
Para generar el tableau inicial de los generadores del cono puntiagudo C,
se debe agregar la restriccion L1Tx ≥ 0 (En realidad se debe agregar todas las
restricciones LiT x ≥ 0, donde Li son las columnas de la matriz L. En nuestrocaso es solo una columna):
(1) (2) (3)
2 1 01 2 00 0 1
A1x 3 0 0A2x 0 3 0
→ L1Tx 0 0 1
39
Tableau inicial89:(1) (2) (3)
2 1 01 2 00 0 1
A1x 3 0 0A2x 0 3 0
L1Tx 0 0 1
Ahora se debe agregar la restriccion −L1Tx ≥ 0 y las restricciones que
quedaron fuera en el Metodo de Jordan (en este caso ninguna).
(1) (2) (3)
2 1 01 2 00 0 1
A1x 3 0 0A2x 0 3 0
L1Tx 0 0 1
→ −L1Tx 0 0 −1
Segundo Tableau (y final):
(1) (2)
2 11 20 0
A1x 3 0A2x 0 3
L1Tx 0 0
−L1Tx 0 0
Ası, los generadores del cono C son:
120
,
210
.
Finalmente, como C = C + [L], se tiene que los generadores de C son losgeneradores de C mas las columnas de L y de −L:
120
,
210
,
001
,
00−1
.
8Cabe notar que podrıamos haber haber “resumido” el tableau, “juntando” la tercera fila
de los generadores con la fila de la restriccion L1Tx ≥ 0. Sin embargo, no se ha hecho por
razones pedagogicas.9Notese que al incorporar la restriccion L1T
x ≥ 0 se forma una matriz diagonal conelementos positivos en la parte de la matriz que corresponde al tableau.
40 CAPITULO 1. METODO DE DOBLE DESCRIPCION
Nota: Para pasar al segundo Tableau se ha incorporado secuencialmente las
restricciones L1Tx ≥ 0 y −L1T
x ≥ 0 (que son equivalentes a L1Tx = 0). Esto
lo podrıamos haber hecho en un solo paso:
(1) (2) (3)
2 1 01 2 00 0 1
A1x 3 0 0A2x 0 3 0
→ L1Tx 0 0 1
(1) (2)
2 11 20 0
A1x 3 0A2x 0 3
L1Tx 0 0
donde la ultima fila tiene la restriccion L1Tx = 0.
Lo que se ha hecho es:
eliminar los generadores con nueva entrada distinta de cero
combinar los generadores con nueva entrada con distinto signo (en estecaso no hay generadores para combinar)
Capıtulo 2
Metodo Simplex Revisado
con Inversa de Base
Explıcita
Ejercicio 2.1 (Ejercicio de Clases)
Resolver el siguiente problema de Programacion Lineal
P) Min − 3x1 − x2 − 3x3
2x1 + x2 + x3 ≤ 2
x1 + 2x2 + 3x3 ≤ 5
2x1 + 2x2 + x3 ≤ 6
x1, x2, x3 ≥ 0,
mediante el Metodo Simplex Revisado con Inversa de Base Explıcita
Solucion
Primero se debe agregar variables de holgura, de modo de que el problema quedeen formato estandar:
P) Min−3x1 − x2 − 3x3
2x1 + x2 + x3 + x4 = 2
x1 + 2x2 + 3x3 + x5 = 5
2x1 + 2x2 + x3 + x6 = 6
x1, x2, x3, x4, x5, x6 ≥ 0.
41
42 CAPITULO 2. METODO SIMPLEX REVISADO
Ası, podemos obtener la matriz A y los vectores b y cT :
A =
2 1 1 1 0 01 2 3 0 1 02 2 1 0 0 1
b =
256
cT =[
−3 −1 −3 0 0 0]
.
Es inmediato que las ultimas columnas de la matriz A forman la identidad:
A =[
D B]
=
2 1 1 1 0 01 2 3 0 1 02 2 1 0 0 1
De este modo, se tiene:
B = {4, 5, 6} D = {1, 2, 3} B =
1 0 00 1 00 0 1
D =
2 1 11 2 32 2 1
Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 00 1 00 0 1
256
=
256
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 0]
1 0 00 1 00 0 1
=[
0 0 0]
Costos reducidos
rTD = cT
D−πT D =[
−3 −1 −3]
−[
0 0 0]
2 1 11 2 32 2 1
=[
−3 −1 −3]
6≥ 0 6≥ 0 6≥ 0
q = 2
1
Luego, x2 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y2 = B−1A2 =
1 0 00 1 00 0 1
122
=
1
22
1no se ha utilizado el costo reducido mas negativo
43
Variable saliente
Min
2
1,5
2,6
2
= 2
Ası, p = 1 y el pivote
Luego, x4 sale de la base
Nueva Base:
Matriz de pivote
P1 =
[η1]
112−12−1
0 01 00 1
=
1 0 0−2 1 0−2 0 1
Ası
B−1+ = P1B
−1 =
1 0 0−2 1 0−2 0 1
1 0 00 1 00 0 1
=
1 0 0−2 1 0−2 0 1
y los datos para la nueva iteracion son:
B = {2, 5, 6} D = {1, 3, 4} B−1 =
1 0 0−2 1 0−2 0 1
D =
2 1 11 3 02 1 0
Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 0−2 1 0−2 0 1
256
=
212
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
−1 0 0]
1 0 0−2 1 0−2 0 1
=[
−1 0 0]
Costos reducidos
rTD = cT
D − πT D =[
−3 −3 0]
−[
−1 0 0]
2 1 11 3 02 1 0
=[
−1 −2 1]
6≥ 0 6≥ 0 ≥ 0
q = 3
44 CAPITULO 2. METODO SIMPLEX REVISADO
Luego, x3 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y3 = B−1A3 =
1 0 0−2 1 0−2 0 1
131
=
1
1
−1
Variable saliente
Min
2
1,
1
1, ·
= 1
Ası, p = 2 y el pivote
Luego, x5 sale de la base
Nueva Base:
Matriz de pivote
P2 =
[η2]
100
1−111−1−1
001
=
1 −1 00 1 00 1 1
Ası
B−1+ = P2B
−1 =
1 −1 00 1 00 1 1
1 0 0−2 1 0−2 0 1
=
3 −1 0−2 1 0−4 1 1
y los datos para la nueva iteracion son:
B = {2, 3, 6} D = {1, 4, 5} B−1 =
3 −1 0−2 1 0−4 1 1
D =
2 1 01 0 12 0 0
Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
3 −1 0−2 1 0−4 1 1
256
=
113
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
−1 −3 0]
3 −1 0−2 1 0−4 1 1
=[
3 −2 0]
45
Costos reducidos
rTD = cT
D − πT D =[
−3 0 0]
−[
3 −2 0]
2 1 01 0 12 0 0
=[
−7 −3 2]
6≥ 0 6≥ 0 ≥ 0
q = 1
Luego, x1 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y1 = B−1A1 =
3 −1 0−2 1 0−4 1 1
212
=
5
−3−5
Variable saliente
Min
1
5, ·, ·
=1
5
Ası, p = 1 y el pivote
Luego, x2 sale de la base
Nueva Base:
Matriz de pivote
P1 =
[η1]
15−3−5−5−5
0 01 00 1
=
15 0 035 1 01 0 1
Ası
B−1+ = P1B
−1 =
15 0 035 1 01 0 1
3 −1 0−2 1 0−4 1 1
=
3/5 −1/5 0−1/5 2/5 0−1 0 1
y los datos para la nueva iteracion son:
B = {1, 3, 6} D = {2, 4, 5} B−1 =
3/5 −1/5 0−1/5 2/5 0−1 0 1
D =
1 1 02 0 12 0 0
Cuarta iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
3/5 −1/5 0−1/5 2/5 0−1 0 1
256
=
15854
≥
000
46 CAPITULO 2. METODO SIMPLEX REVISADO
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
−3 −3 0]
3/5 −1/5 0−1/5 2/5 0−1 0 1
=[
−65
−35 0
]
Costos reducidos
rTD = cT
D−πT D =[
−1 0 0]
−[
−65
−35 0
]
1 1 02 0 12 0 0
=[
7/5 6/5 3/5]
≥ 0 ≥ 0 ≥ 0
FIN
Finalmente:
x1
x3
x6
= y0 =
1/58/54
y
x2
x4
x5
=
000
47
Ejercicio 2.2 (†)
Considere el modelo lineal:
P) Min x1 + x2 − 4x3
x1 + x2 + 2x3 ≤ 9
x1 + x2 − x3 ≤ 2
−x1 + x2 + x3 ≤ 4
x1, x2, x3 ≥ 0,
(i) (2 Ptos.) Muestre, antes de resolver, que P) admite solucion optima. Apli-que el Teorema de Existencia de la Programacion Lineal
(ii) (4 Ptos.) Resuelva P) mediante el Simplex Revisado con Inversa de Baseexplıcita. Detalle los distintos pasos realizados en cada iteracion, explici-tando las inversas de base y las matrices de pivote utilizadas para el calculode estas. Ademas, calcule en cada iteracion el costo reducido mas negativo,e ingrese a la base la variable asociada a este ultimo costo, mientras noobtenga una solucion optima, obviamente.
Solucion
(i) Claramente x1 = x2 = x3 = 0 es solucion de P). Luego, el dominio es novacıo (P) 6= φ)
Para satisfacer la segunda parte de la hipotesis del teorema , necesitamosque:
cT x = x1 + x2 − 4x3 ≥ K
multiplicando la primera restriccion por −1, tenemos:
−x1 − x2 − 2x3 ≥ −9x1 ≥ 0x2 ≥ 0
⇒−2x3 ≥ −9 ⇒−4x3 ≥ −18
y con las restricciones de no-negatividad para el resto de las restricciones:
−4x3 ≥ −18x1 ≥ 0x2 ≥ 0
⇒x1 + x2 − 4x3 ≥ −18
Luego, se cumple la segunda hipotesis del Teorema de Existencia de la Progra-macion Lineal.
48 CAPITULO 2. METODO SIMPLEX REVISADO
(ii)Primero se debe agregar variables de holgura, de modo de que el problemaquede en formato estandar:
P) Min x1 + x2 − 4x3
x1 + x2 + 2x3 + x4 = 9
x1 + x2 − x3 + x5 = 2
− x1 + x2 + x3 + x6 = 4
x1, x2, x3, x4, x5, x6 ≥ 0.
Ası, podemos obtener la matriz A y los vectores b y cT :
A =
1 1 2 1 0 01 1 −1 0 1 0−1 1 1 0 0 1
b =
924
cT =[
1 1 −4 0 0 0]
.
Es inmediato que las ultimas columnas de la matriz A forman la identidad:
A =[
D B]
=
1 1 2 1 0 01 1 −1 0 1 0−1 1 1 0 0 1
De este modo, se tiene:
B = {4, 5, 6} D = {1, 2, 3} B =
1 0 00 1 00 0 1
D =
1 1 21 1 −1−1 1 1
Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 00 1 00 0 1
924
=
924
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 0]
1 0 00 1 00 0 1
=[
0 0 0]
Costos reducidos
rTD = cT
D −πT D =[
1 1 −4]
−[
0 0 0]
1 1 21 1 −1−1 1 1
=[
1 1 −4]
≥ 0 ≥ 0 6≥ 0
q = 3
49
Luego, x3 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y3 = B−1A3 =
1 0 00 1 00 0 1
2−11
=
2−1
1
Variable saliente
Min
9
2, ·,
4
1
= 4
Ası, p = 3 y el pivote
Luego, x6 sale de la base
Nueva Base:
Matriz de pivote
P3 =
[η3]
1 00 10 0
2−1−1−111
=
1 0 −20 1 10 0 1
Ası
B−1+ = P3B
−1 =
1 0 −20 1 10 0 1
1 0 00 1 00 0 1
=
1 0 −20 1 10 0 1
y los datos para la nueva iteracion son:
B = {4, 5, 3} D = {1, 2, 6} B−1 =
1 0 −20 1 10 0 1
D =
1 1 01 1 0−1 1 1
Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 −20 1 10 0 1
924
=
164
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 −4]
1 0 −20 1 10 0 1
=[
0 0 −4]
50 CAPITULO 2. METODO SIMPLEX REVISADO
Costos reducidos
rTD = cT
D − πT D =[
1 1 0]
−[
0 0 −4]
1 1 01 1 0−1 1 1
=[
−3 5 4]
6≥ 0 ≥ 0 ≥ 0
q = 1
Luego, x1 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y1 = B−1A1 =
1 0 −20 1 10 0 1
11−1
=
3
0−1
Variable saliente
Min
1
3, ·, ·
=1
3
Ası, p = 1 y el pivote
Luego, x4 sale de la base
Nueva Base:
Matriz de pivote
P1 =
[η1]
130−3−1−3
0 01 00 1
=
1/3 0 00 1 0
1/3 0 1
Ası
B−1+ = P1B
−1 =
1/3 0 00 1 0
1/3 0 1
1 0 −20 1 10 0 1
=
1/3 0 −2/30 1 1
1/3 0 1/3
y los datos para la nueva iteracion son:
B = {1, 5, 3} D = {2, 4, 6} B−1 =
1/3 0 −2/30 1 1
1/3 0 1/3
D =
1 1 01 0 01 0 1
Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux
51
y0 = B−1b =
1/3 0 −2/30 1 1
1/3 0 1/3
924
=
1/36
13/3
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
1 0 −4]
1/3 0 −2/30 1 1
1/3 0 1/3
=[
−1 0 −2]
Costos reducidos
rTD = cT
D − πT D =[
1 0 0]
−[
−1 0 −2]
1 1 01 0 01 0 1
= [ 4 1 2 ]
≥ 0 ≥ 0 ≥ 0
F IN
Ası:
x1
x5
x3
= y0 =
1/36
13/3
y
x2
x4
x6
=
000
Luego, la solucion del problema original queda:
x =
x1
x2
x3
=
1/30
13/3
y el valor optimo del problema es:
v(P) = 1 · 1/3 + 1 · 0 + −4 · 13/3 = −17
52 CAPITULO 2. METODO SIMPLEX REVISADO
Ejercicio 2.3 (†)
Sea P un poliedro convexo cerrado definido como:
P = {x ∈ Rn|Ax ≤ b, x ≥ 0}
(i) (1 Ptos.) En base a los resultado fundamentales del curso, muestre queP es acotado y no vacıo si y solo si el siguiente problema lineal admitesolucion optima:
P) Maximizarn∑
i=1
xi
Ax ≤ b
x ≥ 0.
(ii) (3 ptos.) En base a i), determine si el siguiente poliedro es acotado y novacıo:
P = {(x1, x2)| − x1 + x2 ≥ 1; x2 ≤ 3; x1, x2 ≥ 0} .
(iii) (2 ptos.) Considere el problema lineal:
P) Min x1 −2x2
−x1 +x2 ≥1
x2 ≤3
x1, x2 ≥0
Muestre, en base a lo anterior, que P) admite solucion optima y resuelvaP) con el Simplex Revisado con Inversa Explıcita, a partir de ii).
Solucion
(i) Debemos demostrar tanto la condicion necesaria como la suficiente:
•Condicion Necesaria
Por demostrar que:
P acotado y no vacıo ⇒ P) admite solucion optima.
Consideremos el problema equivalente de minimizacion:
P) Min −
n∑
i=1
xi
Ax ≤ b
x ≥ 0.
53
Como P es acotado, tenemos:
ai ≤ xi ≤ bi; i = 1, . . . , n ⇒ −xi ≥ −bi ⇒ −
n∑
i=1
xi ≥ −
n∑
i=1
bi := cte.
Ası −∑n
i=1 xi ≥ cte. Por otro lado, de la hipotesis, P es no vacıo. Luego, por elTeorema de Existencia de la Programacion Lineal, P) admite solucion optima2.
•Condicion Suficiente
Por demostrar que:
P) admite solucion optima ⇒ P acotado y no vacıo.
Si P) admite solucion optima, por el Teorema de Existencia de la Progra-
macion Lineal, P es no vacıo. Luego, basta con demostrar que P es acotado.
Por el mismo teorema tenemos:
−
n∑
i=1
xi ≥ cte ⇒
n∑
i=1
xi ≤ −cte. (2.1)
Por otro lado:
xi ≥ 0 ⇒ −xi ≤ 0 ⇒ −
n∑
i=1i6=j
xi ≤ 0. (2.2)
Sumando (2.1) y (2.2), tenemos:
xj ≤ −cte.; ∀j ∈ {1, . . . , n}.
Como las variables son no-negativas, tenemos:
0 ≤ xj ≤ −cte.; ∀j ∈ {1, . . . , n}.
Luego P es acotado.
(ii) Debemos demostrar si el siguiente problema admite solucion optima:
P) Max x1 +x2
−x1 +x2≥1
x2≤3
x1, x2≥0.
2Por motivos pedagogicos, se ha utilizado el Teorema de Existencia de la Programacion
Lineal. Sin embargo, la demostracion mediante el Teorema de Bolzano-Weierstrass es directa.
54 CAPITULO 2. METODO SIMPLEX REVISADO
Consideremos el problema equivalente:
P) Min −x1 −x2
−x1 +x2≥1
x2≤3
x1, x2≥0.
Tenemos que (x1, x2) = (0, 1) ∈ P , luego P 6= φ. Por otro lado, de la segundarestriccion:
x2 ≤ 3 ⇒ −x2 ≥ −3. (2.3)
Sumando (2.3) a la primera restriccion, obtenemos:
−x1 ≥ −2. (2.4)
Sumando (2.3) y (2.4), obtenemos:
−x1 − x2 ≥ −5 → cT x ≥ cte.
Ası, P) admite solucion optima (y P) tambien). Con esto, junto con el re-sultado obtenido en (i), se tiene que P es acotado.
(iii) Como la funcion objetivo es lineal (y por ende continua), el dominio esta de-finido por restricciones lineales de desigualdad no-estricta (y por ende el dominiode restriccion es cerrado). Ademas, de lo obtenido en (ii), se tiene que el dominioes acotado y no vacıo, por el Teorema de Existencia de Bolzano Weierstrass, setiene que P) admite solucion optima.
Para resolver el problema, primero se debe agregar variables de holgura y/oexceso, de modo de que el problema quede en formato estandar:
P) Min x1 −2x2
−x1 +x2 −x3 =1
x2 +x4=3
x1, x2, x3, x4≥0.
Podemos obtener la matriz A y los vectores b y cT :
A =
[
−1 1 −1 00 1 0 1
]
b =
(
13
)
cT =[
1 −2 0 0]
.
Tomemos el vertice (0, 3)3. Entonces (x1, x2, x3, x4) = (0, 3, 2, 0). Ası:
B = {2, 3} D = {1, 4} B =
[
1 −11 0
]
D =
[
−1 00 1
]
3Este problema necesita Fase I, pero dada su simplicidad, graficamente, podemos determi-nar que su solucion optima es (0, 3)
55
Debemos invertir la matriz de base:
B =
[
1 −11 0
]
⇒ B−1 =
[
0 1−1 1
]
Calculamos el vector de multiplicadores π:
πT = cTBB−1 =
[
−2 0]
[
0 1−1 1
]
=[
0 −2]
Costos reducidos:
rTD = cT
D − πT D =[
1 0]
−[
0 −2]
[
−1 00 1
]
= [ 1 2 ]
≥ 0 ≥ 0
FIN
Luego, la solucion encontrada es optima.
56 CAPITULO 2. METODO SIMPLEX REVISADO
Capıtulo 3
Fase I del Metodo Simplex
Ejercicio 3.1 (†)
Considere el siguiente problema lineal de minimizacion:
P) Min − x1 − x2
−3x1 − 2x2 ≥−20
2x1 + 3x2 ≤ 20
x1 + 2x2 ≥ 2
x1, x2 ≥ 0
(i) (2 Ptos.) Antes de resolver, muestre que el conjunto de soluciones optimasde P) define un poliedro convexo cerrado acotado y no vacıo. De ello,concluya que P) es estable, en el sentido que pequenas variaciones en loscostos se traducen en pequenas variaciones en el costo optimo.
(ii) (3 Ptos.) Resuelva P) mediante el Simplex Revisado con 2 fases, con In-versa de Base Explıcita. Explicite los distintos pasos.
(iii) (1 Pto.) ¿Dentro de que rango podrıan variar simultaneamente los costosc1 y c2 de las variables originales sin que cambie la solucion optima? Delresultado obtenido, ¿Podrıa inferir algo respecto de la estabilidad de P)?
Solucion
(i) Debemos demostrar que el conjunto de soluciones optimas de P), en adelanteX, es un poliedro convexo, cerrado, acotado y no vacıo. Para demostrar que Xes convexo y cerrado utilizaremos la solucion optima de P), en adelante x. Luegodebemos demostrar primero que x existe.
57
58 CAPITULO 3. FASE I DEL METODO SIMPLEX
Existencia de solucion optima x
Claramente (x1, x2) = (0, 1) es solucion de P). Luego, el dominio es no vacıo(P) 6= φ)
Por otro lado, de las restricciones:
−3x1 − 2x2 ≥ −20x1 ≥ 0x2 ≥ 0
⇒
{
0 ≤ x1 ≤ 20/30 ≤ x2 ≤ 10
Luego el dominio es acotado.
Ademas, las restricciones estan definidas por restricciones lineales de de-sigualdad. Luego el dominio es cerrado. Finalmente, la funcion objetivo es lineal,luego continua. Ası, por el Teorema de Bolzano Weierstrass, P) admite solucionoptima.
•X no vacıo
Claramente, como ∃x y x ∈ X , X es no vacıo
•X convexo cerrado
En general, se tiene que:
X = P ∩ {x|cT x ≤ cT x}
donde tanto P como {x|cT x ≤ cT x} son convexos y cerrados, luego X es convexocerrado
•X acotado
De la desigualdad anterior se deduce que:
X ⊆ P
Luego, como P es acotado, X tambien lo es1.
Finalmente, como X es acotado y no vacıo, el problema es estable
(ii) Primero se debe agregar variables de holgura, de modo de que el problemaquede en formato estandar:
P) Min − x1 − x2
3x1 + 2x2 + x3 = 20
2x1 + 3x2 + x4 = 20
x1 + 2x2 − x5 = 2
x1, x2, x3, x4, x5 ≥ 0.
1Nota: en caso que P no sea acotado, se necesitara demostrar que P∩{x|cT x ≤ cT x} sı es
acotado.
59
Claramente, se necesita agregar una variable artificial en la ultima res-triccion. Luego nos queda el siguiente problema para la Fase I:
Fase I
P)I Min x6
3x1 + 2x2 + x3 = 20
2x1 + 3x2 + x4 = 20
x1 + 2x2 − x5 + x6 = 2
x1, x2, x3, x4, x5, x6 ≥ 0.
Podemos obtener la matriz A y los vectores b y cT :
A =
3 2 1 0 0 02 3 0 1 0 01 2 0 0 −1 1
b =
20202
cT =[
0 0 0 0 0 1]
.
Es inmediato que las columnas 3, 4 y 6 de la matriz A forman la identidad.Luego, reordenando las columnas de A, se tiene:
A =[
D B]
=
3 2 0 1 0 02 3 0 0 1 01 2 −1 0 0 1
De este modo, se tiene:
B = {3, 4, 6} D = {1, 2, 5} B =
1 0 00 1 00 0 1
D =
3 2 02 3 01 2 −1
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 00 1 00 0 1
20202
=
20202
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 1]
1 0 00 1 00 0 1
=[
0 0 1]
60 CAPITULO 3. FASE I DEL METODO SIMPLEX
Costos reducidos
rTD = cT
D − πT D =[
0 0 0]
−[
0 0 1]
3 2 02 3 01 2 −1
=[
−1 −2 1]
6≥ 0 6≥ 0 ≥ 0
q = 2
Luego, x2 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y2 = B−1A2 =
1 0 00 1 00 0 1
232
=
23
2
Variable saliente
Min
20
2,20
3,
2
2
= 1
Ası, p = 3 y el pivote
Luego, x6 sale de la base, y termina la Fase I
Nueva Base:
Matriz de pivote
P3 =
[η3]
1 00 10 0
2−23−212
=
1 0 −10 1 −3/20 0 1/2
Ası:
B−1+ = P3B
−1 =
1 0 −10 1 −3/20 0 1/2
1 0 00 1 00 0 1
=
1 0 −10 1 −3/20 0 1/2
y los datos para la Fase II son:
B = {3, 4, 2} B−1 =
1 0 −10 1 −3/20 0 1/2
61
Fase II
Tenıamos el problema original en formato estandar:
P) Min − x1 − x2
3x1 + 2x2 + x3 = 20
2x1 + 3x2 + x4 = 20
x1 + 2x2 − x5 = 2
x1, x2, x3, x4, x5 ≥ 0.
La matriz A y el vector cT para la Fase II son:
A =
3 2 1 0 02 3 0 1 01 2 0 0 −1
cT =[
−1 −1 0 0 0]
.
De la Fase II tenıamos que B = {3, 4, 2}, entonces D = {1, 5} y:
D =
3 02 01 −1
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 −10 1 −3/20 0 1/2
20202
=
18171
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 −1]
1 0 −10 1 −3/20 0 1/2
=[
0 0 −1/2]
Costos reducidos
rTD = cT
D − πT D =[
−1 0]
−[
0 0 −1/2]
3 02 01 −1
=[
−1/2 −1/2]
6≥ 0 6≥ 0
q = 1
62 CAPITULO 3. FASE I DEL METODO SIMPLEX
Luego, x1 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y1 = B−1A1 =
1 0 −10 1 −3/20 0 1/2
321
=
21/2
1/2
Variable saliente
Min
{
18
2,
17
1/2,
1
1/2
}
= 2
Ası, p = 3 y el pivote
Luego, x2 sale de la base
Nueva Base:
Matriz de pivote
P3 =
[η3]
1 00 10 0
2−1/21/2−1/2
11/2
=
1 0 −40 1 −10 0 2
Ası
B−1+ = P3B
−1 =
1 0 −40 1 −10 0 2
1 0 −10 1 −3/20 0 1/2
=
1 0 −30 1 −20 0 1
y los datos para la nueva iteracion son:
B = {3, 4, 1} D = {2, 5} B−1 =
1 0 −30 1 −20 0 1
D =
2 03 02 −1
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 0 −30 1 −20 0 1
20202
=
14162
≥
000
63
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 −1]
1 0 −30 1 −20 0 1
=[
0 0 −1]
Costos reducidos
rTD = cT
D − πT D =[
−1 0]
−[
0 0 −1]
2 03 02 −1
=[
1 −1]
≥ 0 6≥ 0
q = 5
Luego, x5 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y5 = B−1A5 =
1 0 −30 1 −20 0 1
00−1
=
3
2−1
Variable saliente
Min
14
3,16
2, ·
=14
3
Ası, p = 1 y el pivote
Luego, x3 sale de la base
Nueva Base:
Matriz de pivote
P1 =
[η1]
132−3−1−3
0 01 00 1
=
1/3 0 0−2/3 1 01/3 0 1
Ası
B−1+ = P1B
−1 =
1/3 0 0−2/3 1 01/3 0 1
1 0 −30 1 −20 0 1
=
1/3 0 −1−2/3 1 01/3 0 0
y los datos para la nueva iteracion son:
B = {5, 4, 1} D = {2, 3} B−1 =
1/3 0 −1−2/3 1 01/3 0 0
D =
2 13 02 0
64 CAPITULO 3. FASE I DEL METODO SIMPLEX
•Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1/3 0 −1−2/3 1 01/3 0 0
20202
=
14/320/320/3
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 0 −1]
1/3 0 −1−2/3 1 01/3 0 0
=[
−1/3 0 0]
Costos reducidos
rTD = cT
D − πT D =[
−1 0]
−[
−1/3 0 0]
2 13 02 0
=[
−1/3 1/3]
6≥ 0 ≥ 0
q = 2
Luego, x2 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y2 = B−1A2 =
1/3 0 −1−2/3 1 01/3 0 0
232
=
−4/3
5/3
2/3
Variable saliente
Min
{
·,20/3
5/3
,20/3
2/3
}
= 4
Ası, p = 2 y el pivote
Luego, x4 sale de la base
Nueva Base:
Matriz de pivote
P2 =
[η2]
100
−4/3−5/3
15/32/3−5/3
001
=
1 4/5 00 3/5 00 −2/5 1
65
Ası
B−1+ = P2B
−1 =
1 4/5 00 3/5 00 −2/5 1
1/3 0 −1−2/3 1 01/3 0 0
=
−1/5 4/5 −1−2/5 3/5 03/5 −2/5 0
y los datos para la nueva iteracion son2:
B = {5, 2, 1} D = {4, 3} B−1 =
−1/5 4/5 −1−2/5 3/5 03/5 −2/5 0
D =
0 11 00 0
•Cuarta iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
−1/5 4/5 −1−2/5 3/5 03/5 −2/5 0
20202
=
1044
≥
000
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
0 −1 −1]
−1/5 4/5 −1−2/5 3/5 03/5 −2/5 0
=[
−1/5 −1/5 0]
Costos reducidos
rTD = cT
D − πT D =[
0 0]
−[
−1/5 −1/5 0]
0 11 00 0
=[
1/5 1/5]
≥ 0 ≥ 0
FIN
Ası:
x5
x2
x1
= y0 =
1044
y
(
x4
x3
)
=
(
00
)
Luego, la solucion del problema original queda:
x =
(
x1
x2
)
=
(
44
)
2Notar que el orden de los elementos de D debe ser consistente con el orden de las columnasde D.
66 CAPITULO 3. FASE I DEL METODO SIMPLEX
y el valor optimo del problema es:
v(P) = −1 · 4 + −1 · 4 = −8
(iii) Esta parte del problema se puede resolver tanto en forma algebraica comoen forma grafica:
Algebraicamente, necesitamos saber cuanto pueden variar los costos, demodo que los costos reducidos continuen siendo no-negativos. Para esto po-demos agregar una variacion ε a ambos costos de modo que:
c′1 = −1 + ε y c′2 = −1 + ε
La variacion ε debe ser pequena, de modo que c′1 y c′2 continuen siendo estric-tamente negativos.
Se debe calcular el vector de multiplicadores nuevamente:
πT = cTBB−1 =
[
0 c′2 c′1]
−1/5 4/5 −1−2/5 3/5 03/5 −2/5 0
=
[
−2/5c′2 + 3/5c′1 3/5c′2 − 2/5c′1 0]
Costos reducidos
rTD = cT
D − πT D =[
0 0]
−[
−2/5c′2 + 3/5c′1 3/5c′2 − 2/5c′1 0]
0 11 00 0
=
[
−3/5c′2 + 2/5c′1 2/5c′2 − 3/5c′1
]
≥ 0 ≥ 0
(∗) (∗∗)
De (∗) y (∗∗) tenemos:3
−3/5c′2 + 2/5c′1 ≥ 0 ⇒ c′1/c′2 ≥ 2/3
2/5c′2 − 3/5c′1 ≥ 0 ⇒ c′1/c′2 ≤ 3/2
luego2
3≤
c′1c′2
≤3
2
3Recordar que anteriormente establecimos que c′1
< 0 y c′2
< 0
67
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
x2
x1
−c = (1, 1); m =c′1c′2
= 1
m = 3/2
m = 2/3
x = (4, 4)TcT x = v(P) = 8
Se concluye que la solucion de P) es estable, puesto que ante pequenasvariaciones en los costos, el problema sigue teniendo la misma solucion y, porende, no hay grandes variaciones en el valor tomado por la funcion objetivo.
68 CAPITULO 3. FASE I DEL METODO SIMPLEX
Ejercicio 3.2 (†)
Considere el problema lineal:
P) Min −x1 −2x2+x3
−x1 +x2 +x3 ≥ 4
2x1 −x3 ≥ 3
x2 +x3 ≤ 6
x1, x2, x3 ≥ 0
(i) (1 Pto.) Muestre, antes de resolver, que P) admite solucion optima (almenos una). Aplique el Teorema de Existencia de la Programacion Lineal.
(ii) (1 Pto.) Agregando variables de holgura y/o exceso, reformule P) bajo laforma estandar equivalente.
(iii) (3 Pto.) Resolviendo un problema de Fase I para este ultimo problema,mediante el Simplex Revisado con inversa de base Explıcita, determineuna solucion basica factible para P).
(iv) (1 Pto.) ¿La solucion basica factible ası encontrada, es optima o no parael problema original P)? Justifique su respuesta en base al Criterio deTermino del Simplex.
Solucion
(i) Se tiene que (x1, x2, x3) = (2, 6, 0) ∈ P . Luego:
P 6= φ (3.1)
De la tercera restriccion y las de no-negatividad, podemos calcular cotassuperiores para las variables 2 y 3. Concretamente:
x2 + x3 ≤ 6
x3 ≥ 0
}
⇒ x2 ≤ 6
Esto, junto con la restriccion 1 nos entrega lo deseado:
x2 ≤ 6
−x1 + x2 + x3 ≥ 4
}
⇒ −x1 − 2x2 + x3 ≥ −14
Ası:cT x ≥ cte. (3.2)
Luego, de (3.1) y (3.2), P) admite solucion optima.
69
(ii) Formato estandar:
P) Min −x1 −2x2+x3
−x1 +x2 +x3 −x4 = 4
2x1 −x3 −x5 = 3
x2 +x3 +x6= 6
x1, x2, x3, x4, x5 x6≥ 0
(iii) Claramente, se necesita agregar una variable artificial en las dos primerasrestricciones. Luego nos queda el siguiente problema para la Fase I :
Fase I
P) Min x7 +x8
−x1 +x2 +x3 −x4 +x7 = 4
2x1 −x3 −x5 +x8= 3
x2 +x3 +x6 = 6
x1, x2, x3, x4, x5 x6, x7, x8≥ 0
Podemos obtener la matriz A y los vectores b y cT :
A =
−1 1 1 −1 0 0 1 02 0 −1 0 −1 0 0 10 1 1 0 0 1 0 0
b =
436
cT =[
0 0 0 0 0 0 1 1]
.
Es inmediato que las columnas 7, 8 y 6 de la matriz A forman la identidad.Luego, reordenando las columnas de A, se tiene:
A =[
D B]
=
−1 1 1 −1 0 1 0 02 0 −1 0 −1 0 1 00 1 1 0 0 0 0 1
De este modo, se tiene:
B = {7, 8, 6}, D = {1, 2, 3, 4, 5},
B =
1 0 00 1 00 0 1
, D =
−1 1 1 −1 02 0 −1 0 −10 1 1 0 0
70 CAPITULO 3. FASE I DEL METODO SIMPLEX
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
1 0 00 1 00 0 1
436
=
436
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
1 1 0]
1 0 00 1 00 0 1
=[
1 1 0]
Costos reducidos:
rTD = cT
D − πT D =[
0 0 0 0 0]
−[
1 1 0]
−1 1 1 −1 02 0 −1 0 −10 1 1 0 0
=
[
−1 −1 0 1 1]
6≥ 0 6≥ 0 ≥ 0 ≥ 0 ≥ 0
q = 1
Luego, x1 entra a la base.4
Tercer paso: Calculo de la columna entrante en el Tableaux
y1 = B−1A1 =
1 0 00 1 00 0 1
−120
=
−1
2
0
Variable saliente:
Min
·,3
2, ·
= 3/2
Ası, p = 2 y el pivote
Luego, x8 sale de la base.
Nueva Base:
Matriz de pivote.
P2 =
[η2]
100
−1−2120−2
001
=
1 1/2 00 1/2 00 0 1
4Tambien podrıa haber sido x2.
71
Ası:
B−1+ = P2B
−1 =
1 1/2 00 1/2 00 0 1
1 0 00 1 00 0 1
=
1 1/2 00 1/2 00 0 1
y los datos para la nueva iteracion son:
B = {7, 1, 6}, D = {2, 3, 4, 5, 8},
B−1 =
1 1/2 00 1/2 00 0 1
, D =
1 1 −1 0 00 −1 0 −1 11 1 0 0 0
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
1 1/2 00 1/2 00 0 1
436
=
11/23/26
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
1 0 0]
1 1/2 00 1/2 00 0 1
=[
1 1/2 0]
Costos reducidos.
rTD = cT
D − πT D =[
0 0 0 0 1]
−[
1 1/2 0]
1 1 −1 0 00 −1 0 −1 11 1 0 0 0
=
[
−1 −1/2 1 1/2 1/2]
6≥ 0 6≥ 0 ≥ 0 ≥ 0 ≥ 0
q = 2
Luego, x2 entra a la base
Tercer paso: Calculo de la columna entrante en el Tableaux
y2 = B−1A2 =
1 1/2 00 1/2 00 0 1
101
=
1
01
Variable saliente:
Min
{
11/2
1, ·,
6
1
}
= 11/2
72 CAPITULO 3. FASE I DEL METODO SIMPLEX
Ası, p = 1 y el pivote
Luego, x7 sale de la base y termina la Fase I
Nueva Base:
Matriz de pivote.
P1 =
[η1]
110−11−1
0 01 00 1
=
1 0 00 1 0−1 0 1
Ası:
B−1+ = P1B
−1 =
1 0 00 1 0−1 0 1
1 1/2 00 1/2 00 0 1
=
1 1/2 00 1/2 0−1 −1/2 1
y los datos para la Fase II (Fase que en este apartado, no se pide realizar), son:
B = {2, 1, 6}, B−1 =
1 1/2 00 1/2 0−1 −1/2 1
Para saber los nuevos valores de las variables de base actuales, necesitamoscalcular el lado derecho:
y0 = B−1b =
1 1/2 00 1/2 0−1 −1/2 1
436
=
11/23/21/2
Ası, la solucion optima para la Fase I es:
xB =
x2
x1
x6
= y0 =
11/23/21/2
y xD =
x3
x4
x5
x7
x8
=
00000
y la solucion factible del problema original es:
x =
x1
x2
x3
=
3/211/2
0
(iii) Debemos comenzar la Fase II :
73
Fase II
Tenıamos el problema original en formato estandar:
P) Min −x1 −2x2+x3
−x1 +x2 +x3 −x4 = 4
2x1 −x3 −x5 = 3
x2 +x3 +x6= 6
x1, x2, x3, x4, x5 x6≥ 0
La matriz A y el vector cT para la Fase II son:
A =
−1 1 1 −1 0 02 0 −1 0 −1 00 1 1 0 0 1
cT =[
−1 −2 1 0 0 0]
.
De la Fase I tenıamos que B = {2, 1, 6}, entonces D = {3, 4, 5} y:
D =
1 −1 0−1 0 −11 0 0
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux (ya se habıa calculado).
y0 = B−1b =
1 1/2 00 1/2 0−1 −1/2 1
436
=
11/23/21/2
>
000
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
−2 −1 0]
1 1/2 00 1/2 0−1 −1/2 1
=[
−2 −3/2 0]
Costos reducidos.
rTD = cT
D − πT D =
[
1 0 0]
−[
−2 −3/2 0]
1 −1 0−1 0 −11 0 0
=[
3/2 −2 −3/2]
≥ 0 6≥ 0 6≥ 0
74 CAPITULO 3. FASE I DEL METODO SIMPLEX
Como la base factible es no-degenerada, por la Condicion Necesaria de Op-
timalidad del Simplex, la solucion basica entregada por la Fase I no es optimapara P).
Capıtulo 4
Metodo Simplex con
Inversa de Base Explıcita y
Descomposicion LU
Ejercicio 4.1 (†)
Considere el siguiente problema de maximizacion:
P) Max 3x1+4x2+x3 +x4
8x1+3x2+4x3+x4 ≤ 7
2x1+6x2+x3 +5x4≤ 3
x1 +4x2+5x3+2x4≤ 8
x1, x2, x3, x4 ≥ 0
(i) (1 punto) Antes de resolver, muestre que P) admite solucion optima.
(ii) (4 puntos) Resuelva, mediante Simplex Revisado con Factorizacion(
L, U)
o mas bien(
L−1, U)
, el problema de minimizacion equivalente, llevando la
matriz L−1 factorizada bajo forma de producto de matrices elementales,de pivote y/o permutacion. Mas aun, aplique este metodo con permutacioneventual de filas, con el fin de conseguir un “mejor pivote”(mayor, en valorabsoluto).
(iii) (1 punto) Explicite la solucion optima encontrada y el valor optimo de P).
75
76 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
Solucion
(i) Se tiene que (x1, x2, x3, x4) = (0, 0, 0, 0) ∈ P . Luego:
P 6= φ (4.1)
De la primera restriccion y las de no-negatividad, podemos calcular cotassuperiores para todas las variables. Concretamente:
8x1 + 3x2 + 4x3 + x4 ≤ 7
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥ 0
⇒
x1 ≤ 7/8
x2 ≤ 7/3
x3 ≤ 7/4
x4 ≤ 7
Luego, el dominio de restriccion es acotado. Todo esto, junto con la continuidadde la funcion objetivo y la cerradura del dominio de restriccion, cumplen con lashipotesis del “Teorema de Existencia de Bolzano-Weierstrass”. Ası, P) admitesolucion optima.
(ii) Primero expresamos el problema en formato estandar:
P) Min −3x1−4x2−x3 −x4
8x1+3x2+4x3+x4 +x5 = 7
2x1+6x2+x3 +5x4 +x6 = 3
x1 +4x2+5x3+2x4 +x7= 8
x1, x2, x3, x4, x5, x6, x7≥ 0
Podemos obtener la matriz A y los vectores b y cT :
A =
8 3 4 1 1 0 02 6 1 5 0 1 01 4 5 2 0 0 1
b =
738
cT =[
−3 −4 −1 −1 0 0 0]
.
Es inmediato que las columnas 5, 6 y 7 de la matriz A forman la identidad. Ası,se tiene:
A =[
D B]
=
8 3 4 1 1 0 02 6 1 5 0 1 01 4 5 2 0 0 1
De este modo, se tiene:
B = {5, 6, 7}, D = {1, 2, 3, 4},
B = L = U = I, D =
8 3 4 12 6 1 51 4 5 2
77
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = I
738
=
738
Uyo = z0 ⇒ Iy0 =
738
⇒ y0 =
738
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT I =
[
0 0 0]
⇒ wT =[
0 0 0]
πT = wT L−1 =[
0 0 0]
I =[
0 0 0]
Costos reducidos:
rTD = cT
D − πT D =[
−3 −4 −1 −1]
−[
0 0 0]
8 3 4 12 6 1 51 4 5 2
=
[
−3 −4 −1 −1]
6≥ 0 6≥ 0 6≥ 0 6≥ 0
q = 2
Luego, x2 entra a la base.1
Tercer paso: Calculo de la columna entrante en el Tableaux.
z2 = L−1A2 = I
364
=
364
Uy2 = z2 ⇒ Iy2 =
364
⇒ y2 =
364
Variable saliente:
Min
{
7
3,3
6,8
4
}
= 1/2
Ası, p = 2.
Luego, x6 sale de la base.
1Podrıa haber sido cualquiera con costo reducido negativo, en este caso todas.
78 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
Nueva Base:
H =
[z2]
1 0 30 0 60 1 4
π23H =
1 0 30 1 40 0 6
= U+
{
L+}−1
= π23L−1 = π23I = π23
y los datos para la nueva iteracion son:
B = {5, 7, 2}, D = {1, 3, 4, 6}, D =
8 4 1 02 1 5 11 5 2 0
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = π23
738
=
783
Uyo = z0 ⇒
1 0 30 1 40 0 6
y0 =
783
⇒ y0 =
11/26
1/2
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT
1 0 30 1 40 0 6
=[
0 0 −4]
⇒ wT =[
0 0 −2/3]
πT = wT L−1 =[
0 0 −2/3]
π23 =[
0 −2/3 0]
Costos reducidos:
rTD = cT
D − πT D =[
−3 −1 −1 0]
−[
0 −2/3 0]
8 4 1 02 1 5 11 5 2 0
=
[
−5/3 −1/3 7/3 2/3]
6≥ 0 6≥ 0 ≥ 0 ≥ 0
q = 1
79
Luego, x1 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux.
z1 = L−1A1 = π23
821
=
812
Uy1 = z1 ⇒
1 0 30 1 40 0 6
y1 =
812
⇒ y1 =
7−1/31/3
Variable saliente:
Min
{
11/2
7, ·,
1/2
1/3
}
= 11/14
Ası, p = 1.
Luego, x5 sale de la base.
Nueva Base:
H =
[z1]
0 3 81 4 10 6 2
π12H =
1 4 10 3 80 6 2
como |H32| > |H22|, se debe hacer una permutacion de filas, con el fin de tenerun ”mejor pivote”:
π23π12H =
1 4 10 6 20 3 8
Considerando:
M1 =
1 0 00 1 00 −3/6 1
=
1 0 00 1 00 −1/2 1
Se tiene
M1π23π12H =
1 4 10 6 20 0 7
= U+
{
L+}−1
= M1π23π12L−1 = M1π23π12π23 = M1π23π12π23
y los datos para la nueva iteracion son:
B = {7, 2, 1}, D = {3, 4, 5, 6}, D =
4 1 1 01 5 0 15 2 0 0
80 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
•Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = M1π23π12π23
738
=
83
11/2
Uyo = z0 ⇒
1 4 10 6 20 0 7
y0 =
83
11/2
⇒ y0 =
263/425/2111/14
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT
1 4 10 6 20 0 7
=[
0 −4 −3]
⇒ wT =[
0 −2/3 −5/21]
πT = wT L−1 =[
0 −2/3 −5/21]
M1π23π12π23 =[
−5/21 −23/42 0]
Costos reducidos:
rTD = cT
D −πT D =[
−1 −1 0 0]
−[
−5/21 −23/42 0]
4 1 1 01 5 0 15 2 0 0
=
[
1/2 83/42 10/42 23/42]
≥ 0 ≥ 0 ≥ 0 ≥ 0
FIN
La solucion optima del problema estandarizado es:
xB = y0 ⇔
x7
x2
x1
=
263/425/2111/14
y xD = ~0 ⇔
x3
x4
x5
x6
=
0000
Por consiguiente, la solucion optima del problema original es:
x =
x1
x2
x3
x4
=
11/145/21
00
y el valor optimo del problema es:
v(P)) = cT x = 3 · 11/14 + 4 · 5/21 + 1 · 0 + 1 · 0 = 139/42
81
Ejercicio 4.2 (†)
Considere el problema lineal de minimizacion:
P) Min −x1 −2x2−3x3−4x4
x1 +2x2+x3 +x4 = 3
x1 −x2 +2x3+x4 = 4
x1 +x2 −x3 −x4 =−1
x1, x2, x3, x4 ≥ 0
(i) (4 ptos.) Aplique la Fase I del Metodo Simplex Revisado, con inversa debase implıcita bajo factorizacion
(
L−1, U)
, con el fin de determinar si elproblema P) es o no factible.
(ii) (1 pto.) Teniendo en cuenta i), estudie si P) admite o no solucion optima.
(iii) (1 pto.) Si fuera el caso, encuentre una solucion optima de P) medianteel Metodo Simplex Revisado con Inversa de Base Explıcita. Justifiqueclaramente su respuesta.
Nota: De mas esta decir que si B es regular, entonces B = LU si y solo siB−1 = U−1L−1
Solucion
(i) El problema ya esta en formato estandar, pero es conveniente expresar ellado derecho positivo:
P) Min −x1 −2x2−3x3−4x4
x1 +2x2+x3 +x4 = 3
x1 −x2 +2x3+x4 = 4
−x1 −x2 +x3 +x4 = 1
x1, x2, x3, x4 ≥ 0
Claramente, no podemos formar la identidad con estas restricciones. Luego,deberemos agregar variables artificiales a todas las restricciones. Ası, nos quedael siguiente problema para la Fase I :
P) Min x5 +x6 +x7
x1 +2x2+x3 +x4 +x5 = 3
x1 −x2 +2x3+x4 +x6 = 4
−x1 −x2 +x3 +x4 +x7= 1
x1, x2, x3, x4, x5, x6, x7≥ 0
82 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
Podemos obtener la matriz A y los vectores b y cT :
A =
1 2 1 1 1 0 01 −1 2 1 0 1 0−1 −1 1 1 0 0 1
b =
341
cT =[
0 0 0 0 1 1 1]
.
Es inmediato que las columnas 5, 6 y 7 de la matriz A forman la identidad (Dehecho, se ha construido para que sea ası). Ası, se tiene:
A =[
D B]
=
1 2 1 1 1 0 01 −1 2 1 0 1 0−1 −1 1 1 0 0 1
De este modo, se tiene:
B = {5, 6, 7}, D = {1, 2, 3, 4},
B = L = U = I, D =
1 2 1 11 −1 2 1−1 −1 1 1
Fase I
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = I
341
=
341
Uyo = z0 ⇒ Iy0 =
341
⇒ y0 =
341
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT I =
[
1 1 1]
⇒ wT =[
1 1 1]
πT = wT L−1 =[
1 1 1]
I =[
1 1 1]
Costos reducidos:
rTD = cT
D − πT D =[
0 0 0 0]
−[
1 1 1]
1 2 1 11 −1 2 1−1 −1 1 1
=
[
−1 0 −4 −3]
6≥ 0 ≥ 0 6≥ 0 6≥ 0
q = 3
83
Luego, x3 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux.
z3 = L−1A3 = I
121
=
121
Uy3 = z3 ⇒ Iy3 =
121
⇒ y3 =
121
Variable saliente:
Min
{
3
1,4
2,1
1
}
= 1
Ası, p = 3.
Luego, x7 sale de la base.
Nueva Base:
H =
[z3]
1 0 10 1 20 0 1
= U+
{
L+}−1
= L−1
y los datos para la nueva iteracion son:
B = {5, 6, 3}, D = {1, 2, 4, 7}, D =
1 2 1 01 −1 1 0−1 −1 1 1
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = I
341
=
341
Uyo = z0 ⇒
1 0 10 1 20 0 1
y0 =
341
⇒ y0 =
221
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT
1 0 10 1 20 0 1
=[
1 1 0]
⇒ wT =[
1 1 −3]
84 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
πT = wT L−1 =[
1 1 −3]
I =[
1 1 −3]
Costos reducidos:
rTD = cT
D − πT D =[
0 0 0 1]
−[
1 1 −3]
1 2 1 01 −1 1 0−1 −1 1 1
=
[
−5 −4 1 4]
6≥ 0 6≥ 0 ≥ 0 ≥ 0
q = 1
Luego, x1 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux.
z1 = L−1A1 = I
11−1
=
11−1
Uy1 = z1 ⇒
1 0 10 1 20 0 1
y1 =
11−1
⇒ y1 =
23−1
Variable saliente:
Min
{
2
2,2
3, ·
}
= 2/3
Ası, p = 2.
Luego, x6 sale de la base.
Nueva Base:
H =
[z1]
1 1 10 2 10 1 −1
Considerando:
M1 =
1 0 00 1 00 −1/2 1
Se tiene
M1H =
1 1 10 2 10 0 −3/2
= U+
{
L+}−1
= M1L−1 = M1I = M1
85
y los datos para la nueva iteracion son:
B = {5, 3, 1}, D = {2, 4, 6, 7}, D =
2 1 0 0−1 1 1 0−1 1 0 1
•Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = M1
341
=
34−1
Uyo = z0 ⇒
1 1 10 2 10 0 −3/2
y0 =
34−1
⇒ y0 =
2/35/32/3
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT
1 1 10 2 10 0 −3/2
=[
1 0 0]
⇒ wT =[
1 −1/2 1/3]
πT = wT L−1 =[
1 −1/2 1/3]
M1 =[
1 −2/3 1/3]
Costos reducidos:
rTD = cT
D − πT D =[
0 0 1 1]
−[
1 −2/3 1/3]
2 1 0 0−1 1 1 0−1 1 0 1
=
[
−7/3 −2/3 5/3 2/3]
6≥ 0 6≥ 0 ≥ 0 ≥ 0
q = 2
Luego, x2 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux.
z2 = L−1A2 = M1
2−1−1
=
2−1−1/2
Uy2 = z2 ⇒
1 1 10 2 10 0 −3/2
y2 =
2−1
−1/2
⇒ y2 =
7/3−2/31/3
86 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
Variable saliente:
Min
{
2/3
7/3, ·,
2/3
1/3
}
= 2/7
Ası, p = 1.
Luego, x5 sale de la base, y termina la Fase I 2.
Nueva Base:
H =
[z2]
1 1 22 1 −10 −3/2 −1/2
como |H21| > |H11|, se debe hacer una permutacion de filas, con el fin de tenerun ”mejor pivote”:
π12H =
2 1 −11 1 20 −3/2 −1/2
Considerando:
M2 =
1 0 0−1/2 1 0
0 0 1
Se tiene
M2π12H =
2 1 −10 1/2 5/20 −3/2 −1/2
nuevamente, como |H32| > |H22|, se debe hacer una permutacion de filas, conel fin de tener un ”mejor pivote”:
π23M2π12H =
2 1 −10 −3/2 −1/20 1/2 5/2
Considerando:
M3 =
1 0 00 1 0
0 − 1/2−3/2 1
=
1 0 00 1 00 1/3 1
Se tiene
M3π23M2π12H =
2 1 −10 −3/2 −1/20 0 7/3
= U+
{
L+}−1
= M3π23M2π12L−1 = M3π23M2π12M1
2Notese que como salieron las variables artificiales de la base, el valor optimo de la Fase I
es cero y ya podemos decir que el problema admite solucion optima. El resto de los calculossolo se hacen para conocer la base y la solucion optima.
87
La nueva base para para la Fase II (de la cual se necesita hacer el primer pasode la primera iteracion, de modo de calcular los nuevos valores de las variablesbasicas) es B = {3, 1, 2}
Calculo del lado derecho del Tableaux3.
z0 = L−1b = M3π23M2π12M1
341
=
4−12/3
Uyo = z0 ⇒
2 1 −10 −3/2 −1/20 0 7/3
y0 =
4−12/3
⇒ y0 =
13/74/72/7
≥
000
La solucion optima del problema de Fase I es:
xB = y0 ⇔
x3
x1
x2
=
13/74/72/7
y xD = ~0 ⇔
x4
x5
x6
x7
=
0000
Por consiguiente, la solucion basica factible del problema original es:
x =
x1
x2
x3
x4
=
4/72/713/7
0
Como x ∈ P), se tiene que el problema es factible.
3Notese que para conocer esta solucion hemos utilizado la nueva base (en realidad, su fac-torizacion (L−1, U)). Sin embargo, podrıamos obtener el lado derecho del tableau de formaanaloga a como se hace en la especializacion del Simplex para restricciones de cotas. Concre-tamente:
x+
2= l2 + ∆ = 0 + 2/7 = 2/7
(x+
B) = y0 − ∆y5 =
0
@
2/35/32/3
1
A − 2/7
0
@
7/3−2/31/3
1
A =
0
@
013/74/7
1
A
xB+ =
0
@
13/74/72/7
1
A
Esta vez, se debe ser consistente con el nuevo orden en que se lleva la base. Ahora la variableque entra a la base, no lo hace en la posicion de la variable que sale de la base, sino que entraen la ultima posicion, lo mismo ocurre con el nuevo lado derecho.Calcular el nuevo lado derecho de esta forma nos permite continuar con el ejercicio sin necesitarla nueva factorizacion (L−1, U).
88 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
(ii) Del apartado i), se tiene que:
P 6= φ (4.2)
De la primera restriccion y las de no-negatividad, podemos calcular cotassuperiores para todas las variables. Concretamente:
x1 + 2x2 + x3 + x4 = 3
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥ 0
⇒
x1 ≤ 3
x2 ≤ 3/2
x3 ≤ 3
x4 ≤ 3
Luego, el dominio de restriccion es acotado. Todo esto, junto con la continuidadde la funcion objetivo y la cerradura del dominio de restriccion, cumplen con lashipotesis del “Teorema de Existencia de Bolzano-Weierstrass”. Ası, P) admitesolucion optima.
(iii) Nuestro problema original en formato estandar es:
P) Min −x1 −2x2−3x3−4x4
x1 +2x2+x3 +x4 = 3
x1 −x2 +2x3+x4 = 4
−x1 −x2 +x3 +x4 = 1
x1, x2, x3, x4 ≥ 0
del cual podemos obtener la matriz A y los vectores b y cT :
A =
1 2 1 11 −1 2 1−1 −1 1 1
b =
341
cT =[
−1 −2 −3 −4]
.
Del apartado i) tenıamos:
B = {3, 1, 2}, L−1 = M3π23M2π12M1 y U =
2 1 −10 −3/2 −1/20 0 7/3
Siguiendo la indicacion del enunciado, tenemos que B−1 = U−1L−1. Calcu-lando U−1 de la forma que se estime conveniente, tenemos:
U−1 =
1/2 1/3 2/70 −2/3 −1/70 0 3/7
89
Ası4:
B−1 = U−1L−1 =
2/7 1/7 3/7−1/7 3/7 −5/73/7 −2/7 1/7
Como B = {3, 1, 2}:
D = {4} y D =
111
Se tiene todos los datos para continuar con la Fase II del Metodo Simplexcon Inversa de Base Explıtita.
Fase II
Primer paso: Calculo del lado derecho del Tableaux.
Ya lo obtuvimos en el apartado i)
y0 =
13/74/72/7
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
−3 −1 −2]
2/7 1/7 3/7−1/7 3/7 −5/73/7 −2/7 1/7
=[
−11/7 −2/7 −6/7]
Costos reducidos:
rTD = cT
D − πT D =[
−4]
−[
−11/7 −2/7 −6/7]
111
=[
−9/7]
6≥ 0
q = 4
4Notese que, como B = {3, 1, 2}, entonces:
B =
2
4
1 1 22 1 −11 −1 −1
3
5
Invirtiendo esta matriz debemos llegar al mismo resultado. Esto refuerza la idea que no ne-cesitamos la nueva matriz de base en la ultima iteracion de la Fase I para continuar con elejercicio.
90 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
Luego, x4 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
y4 = B−1A4 =
2/7 1/7 3/7−1/7 3/7 −5/73/7 −2/7 1/7
111
=
6/7−3/7
2/7
Variable saliente
Min
{
13/7
6/7, ·,
2/7
2/7
}
= 1
Ası, p = 3 y el pivote
Luego, x2 sale de la base
Nueva Base:
Matriz de pivote
P3 =
[η3]
1 00 10 0
6/7−2/7−3/7−2/7
12/7
=
1 0 −30 1 3/20 0 7/2
Ası
B−1+ = P3B
−1 =
1 0 −30 1 3/20 0 7/2
2/7 1/7 3/7−1/7 3/7 −5/73/7 −2/7 1/7
=
−1 1 01/2 0 −1/23/2 −1 1/2
y los datos para la nueva iteracion son:
B = {3, 1, 4} D = {2} B−1 =
−1 1 01/2 0 −1/23/2 −1 1/2
D =
2−1−1
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux
y0 = B−1b =
−1 1 01/2 0 −1/23/2 −1 1/2
341
=
111
≥
000
91
Segundo paso: Calculo del vector de multiplicadores π
πT = cTBB−1 =
[
−3 −1 −4]
−1 1 01/2 0 −1/23/2 −1 1/2
=[
−7/2 1 −3/2]
Costos reducidos:
rTD = cT
D − πT D =[
−2]
−[
−7/2 1 −3/2]
2−1−1
=[
9/2]
≥ 0
F IN
Ası, la solucion optima del problema es:
xB = y0 ⇔
x3
x1
x4
=
111
y xD = ~0 ⇔(
x2
)
=(
0)
y el valor optimo del problema es:
v(P)) = cT x = −1 · 1 − 2 · 0 − 3 · 1 − 4 · 1 = −8
A continuacion, se muestra como continua la Fase II del metodo con Inversade Base Implıcita en forma de producto (Notese que esto no era lo que se pedıaen el enunciado). Fase II
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
Ya lo obtuvimos en el apartado i)
y0 =
13/74/72/7
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT
2 1 −10 −3/2 −1/20 0 7/3
=[
−3 −1 −2]
⇒
wT =[
−3/2 −1/3 −11/7]
92 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
πT = wT L−1 =[
−3/2 −1/3 −11/7]
M3π23M2π12M1 =[
−11/7 −2/7 −6/7]
Costos reducidos:
rTD = cT
D − πT D =[
−4]
−[
−11/7 −2/7 −6/7]
111
=[
−9/7]
6≥ 0
q = 4
Luego, x4 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux.
z4 = L−1A4 = M3π23M2π12M1
111
=
11/22/3
Uy4 = z4 ⇒
2 1 −10 −3/2 −1/20 0 7/3
y4 =
11/22/3
⇒ y4 =
6/7−3/72/7
Variable saliente:
Min
{
13/7
6/7, ·,
2/7
2/7
}
= 1
Ası, p = 3.
Luego, x2 sale de la base.
Nueva Base:
H =
[z4]
2 1 10 −3/2 1/20 0 2/3
= U+
{
L+}−1
= L−1 = M3π23M2π12M1
y los datos para la nueva iteracion son:
B = {3, 1, 4}, D = {2}, D =
2−1−1
93
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux.
z0 = L−1b = M3π23M2π12M1
341
=
4−12/3
Uyo = z0 ⇒
2 1 10 −3/2 1/20 0 2/3
y0 =
4−12/3
⇒ y0 =
111
≥
000
Segundo paso: Calculo del vector de multiplicadores π.
wT U = CTB ⇒ wT
2 1 10 −3/2 1/20 0 2/3
=[
−3 −1 −4]
⇒
wT =[
−3/2 −1/3 −7/2]
πT = wT L−1 =[
−3/2 −1/3 −7/2]
M3π23M2π12M1 =[
−7/2 1 −3/2]
Costos reducidos:
rTD = cT
D − πT D =[
−2]
−[
−7/2 1 −3/2]
2−1−1
=[
9/2]
≥ 0
F IN
Ası, la solucion optima del problema es:
xB = y0 ⇔
x3
x1
x4
=
111
y xD = ~0 ⇔(
x2
)
=(
0)
y el valor optimo del problema es:
v(P)) = cT x = −1 · 1 − 2 · 0 − 3 · 1 − 4 · 1 = −8
94 CAPITULO 4. SIMPLEX CON INVERSA DE BASE EXPLICITA
Capıtulo 5
Especializacion del Metodo
Simplex Problemas con
Restricciones de Cotas
Ejercicio 5.1 (Ejemplo)
Dado el problema lineal:
P) Min x1 +2x2
x1 −x2 ≥2
x1 +x2 ≤− 1
0 ≤x1 ≤ 3
−3 ≤x2 ≤ 0
Resolver mediante el Metodo Simplex con Cotas
Solucion
En el siguiente grafico se puede distinguir el dominio de restriccion y el dominiodado por las restricciones de cotas:
95
96 CAPITULO 5. SIMPLEX CON COTAS
1 2 3
−1
−2
−3
x2
x1
Antes de resolver, debemos tener el problema en formato estandar con cotas:
P) Min x1 +2x2
x1 −x2 −x3 =2
x1 +x2 +x4= − 1
0 ≤x1 ≤ 3
−3 ≤x2 ≤ 0
0 ≤x3
0 ≤x4
Cuando se comienza con un problema con restricciones de desigualdad (comoeste caso), cada variable de holgura y/o exceso provee un candidato a la base,puesto que provee una columna de la matriz identidad. Si multiplicaramos laprimera restriccion por −1 podrıamos tener la identidad como Matriz de Base,teniendo a x3 y x4 como variables de base. Sin embargo, esta base puede no serfactible (tal que las variables de base cumplan con sus cotas):
P) Min x1 +2x2
−x1 +x2 +x3 = − 2
x1 +x2 +x4= − 1
0 ≤x1 ≤ 3
−3 ≤x2 ≤ 0
0 ≤x3
0 ≤x4
97
Si quisieramos hacer Fase I, debemos elegir en que cota quedara cada variable(en el caso de las variables de holgura y/o exceso, en su unica cota 0). Una vezhecho esto, debemos determinar cuales restricciones son violadas, de modo deagregar variables artificiales a cada una de estas. Sin embargo, la cantidad devariables artificiales que se necesita (eventualmente ninguna, lo que implicarıano hacer Fase I ) depende de que cotas elijamos para las variables fuera de base.
Para este problema (tomando en cuenta que las variables de holgura y/oexceso solo pueden quedar en su cota 0, pues estan fuera de la base), temenoscuatro casos:
•Caso I
Variables fuera de base D = {u1,
u2}:
x1 = 3
x2 = 0
}
⇒
{
x3 = 1
x4 = −4⇒ infactible
Se necesitarıa una variable artificial en la segunda restriccion.
•Caso II
Variables fuera de base D = {l1,
u2}:
x1 = 0
x2 = 0
}
⇒
{
x3 = −2
x4 = −1⇒ infactible
Se necesitarıa dos variables artificiales, una para cada restriccion.
•Caso III
Variables fuera de base D = {u1,
l2}:
x1 = 3
x2 = −3
}
⇒
{
x3 = 4
x4 = −1⇒ infactible
Se necesitarıa una variable artificial en la segunda restriccion.
•Caso IV
Variables fuera de base D = {l1,
l2}:
x1 = 0
x2 = −3
}
⇒
{
x3 = 1
x4 = 2⇒ factible
98 CAPITULO 5. SIMPLEX CON COTAS
No se necesita Fase I. Los datos iniciales son:
B = {3, 4}, D = {l1,
l2}, B =
[
1 00 1
]
y D =
[
−1 11 1
]
Cabe notar que cada uno de estos casos define un punto del espacio dadopor el problema original. En este caso, tal como se puede ver en el grafico, elpunto (x1, x2) = (0,−3), dado por el Caso IV, es el unico punto factible en eldominio del problema original.
99
Ejercicio 5.2 (†)
Considere el problema lineal:
P) Min x1 +2x2 +3x3 −x4
2x1−x2 +x3 −2x4≤ 6
−x1 +2x2 −x3 +x4 ≤ 8
2x1+x2 −x3 +6x4≥ 2
0 ≤ x1 ≤ 3
1 ≤ x2 ≤ 4
0 ≤ x3 ≤ 10
2 ≤ x4 ≤ 5
(i) (0.5 Pto.) Muestre, antes de resolver, que P) admite solucion optima.
(ii) (0.5 Pto.) Reformule el problema P) en formato estandar con cotas.
(iii) (4 Pto.) Resuelva el modelo resultante mediante el Simplex Revisadopara Restricciones de Cotas, definiendo una base factible inicial dondex1, x2, x3, x4 esten en sus cotas l1, u2, u3, l4, respectivamente.
(iv) (1 Pto.) ¿Que ventajas tiene la aplicacion del Simplex Revisado para Res-tricciones de Cotas, sobre el Simplex Revisado Clasico aplicado directa-mente al problema con solo restricciones de signo equivalente? Fundamentesu respuesta de manera breve y precisa.
Solucion
(i) Se tiene que (x1, x2, x3, x4) = (0, 4, 10, 2) ∈ P (De hecho, nos dicen que estabase es factible). Luego:
P 6= φ (5.1)
Sea el poliedro P , definido por las restricciones:
0 ≤x1 ≤ 3
1 ≤x2 ≤ 4
0 ≤x3 ≤10
2 ≤x4 ≤ 5
Claramente P es acotado. Como P ⊆ P , resulta que P tambien es acotado.
100 CAPITULO 5. SIMPLEX CON COTAS
Todo esto, junto con la continuidad de la funcion objetivo y la cerraduradel dominio de restriccion, cumple las hipotesis del “Teorema de Existencia deBolzano-Weierstrass”. Ası, P) admite solucion optima.
(ii) Formato estandar con cotas:
P) Min x1 +2x2 +3x3 −x4
2x1−x2 +x3 −2x4+x5 = 6
−x1 +2x2 −x3 +x4 +x6 = 8
2x1+x2 −x3 +6x4 −x7= 2
0 ≤ x1 ≤ 3
1 ≤ x2 ≤ 4
0 ≤ x3 ≤ 10
2 ≤ x4 ≤ 5
0 ≤ x5
0 ≤ x6
0 ≤ x7
Para obtener la identidad en las columnas de A relacionadas con las variablesx5, x6 y x7; debemos multiplicar la ultima restriccion por -1:
P) Min x1 +2x2 +3x3 −x4
2x1−x2 +x3 −2x4+x5 = 6
−x1 +2x2 −x3 +x4 +x6 = 8
−2x1−x2 +x3 −6x4 +x7=−2
0 ≤ x1 ≤ 3
1 ≤ x2 ≤ 4
0 ≤ x3 ≤ 10
2 ≤ x4 ≤ 5
0 ≤ x5
0 ≤ x6
0 ≤ x7
101
(iii) Podemos obtener la matriz A y los vectores b y cT :
A =
2 −1 1 −2 1 0 0−1 2 −1 1 0 1 0−2 −1 1 −6 0 0 1
b =
68−2
cT =[
1 2 3 −1 0 0 0]
.
Ası las columnas 5, 6 y 7 de la matriz A forman la identidad (Ademas, delenunciado, el resto de las variables estan en sus cotas, luego son candidatas aestar fuera de la base):
A =[
D B]
=
2 −1 1 −2 1 0 0−1 2 −1 1 0 1 0−2 −1 1 −6 0 0 1
De este modo, se tiene:
B = {5, 6, 7}, D = {l1,
u2,
u3,
l4},
B =
1 0 00 1 00 0 1
, D =
2 −1 1 −2−1 2 −1 1−2 −1 1 −6
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux1.
y0 = B−1b − B−1Dxd =
1 0 00 1 00 0 1
68−2
−
1 0 00 1 00 0 1
2 −1 1 −2−1 2 −1 1−2 −1 1 −6
04102
=
484
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
0 0 0]
1 0 00 1 00 0 1
=[
0 0 0]
1Notese que el calculo de y0 mediante la formula y0 = B−1b−B−1Dxd solo es “necesario.en
la primera iteracion.
102 CAPITULO 5. SIMPLEX CON COTAS
Costos reducidos:
rTD = cT
D − πT D =[
1 2 3 −1]
−[
0 0 0]
2 −1 1 −2−1 2 −1 1−2 −1 1 −6
=
[
1 2 3 −1]
l u u l≥ 0 6≤ 0 6≤ 0 6≥ 0
q = 3
Luego, x3 entra a la base bajando.
Tercer paso: Calculo de la columna entrante en el Tableaux
y3 = B−1A3 =
1 0 00 1 00 0 1
1−11
=
1
−1
1
Variable saliente:
γ1 = Min
{
·,8 − 0
1, ·
}
= 8
γ2 = Min {·, ·, ·} = ·
γ3 = 10 − 0 = 10
⇒ ∆ = Min {8, ·, 10} = 8
Ası, p = 2 y el pivote
Luego, x6 sale de la base en su cota inferior.
Nueva Base:
Matriz de pivote.
P2 =
[η2]
100
111−111
001
=
1 1 00 −1 00 1 1
Ası:
B−1+ = P2B
−1 =
1 1 00 −1 00 1 1
1 0 00 1 00 0 1
=
1 1 00 −1 00 1 1
y los datos para la nueva iteracion son:
B = {5, 3, 7}, D = {l1,
u2,
l4,
l6},
B−1 =
1 1 00 −1 00 1 1
y D =
2 −1 −2 0−1 2 1 1−2 −1 −6 0
103
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux.
x+3 = u3 − ∆ = 10 − 8 = 2
(
x+B
)
= y0 + ∆y3 =
484
+ 8
1−11
=
12
012
xB+ =
12
212
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
0 3 0]
1 1 00 −1 00 1 1
=[
0 −3 0]
Costos reducidos:
rTD = cT
D − πT D =[
1 2 −1 0]
−[
0 −3 0]
2 −1 −2 0−1 2 1 1−2 −1 −6 0
=
[
−2 8 2 3]
l u l l6≥ 0 6≤ 0 ≥ 0 ≥ 0
q = 2
Luego, x2 entra a la base bajando.
Tercer paso: Calculo de la columna entrante en el Tableaux
y2 = B−1A2 =
1 1 00 −1 00 1 1
−12−1
=
1
−2
1
Variable saliente:
γ1 = Min
{
·,2 − 0
2, ·
}
= 1
γ2 = Min {·, ·, ·} = ·
γ3 = 4 − 1 = 3
⇒ ∆ = Min {1, ·, 3} = 1
Ası, p = 2 y el pivote
104 CAPITULO 5. SIMPLEX CON COTAS
Luego, x3 sale de la base en su cota inferior.
Nueva Base:
Matriz de pivote.
P2 =
[η2]
100
121−212
001
=
1 1/2 00 −1/2 00 1/2 1
Ası:
B−1+ = P2B
−1 =
1 1/2 00 −1/2 00 1/2 1
1 1 00 −1 00 1 1
=
1 1/2 00 1/2 00 1/2 1
y los datos para la nueva iteracion son:
B = {5, 2, 7}, D = {l1,
l4,
l6,
l3},
B−1 =
1 1/2 00 1/2 00 1/2 1
y D =
2 −2 0 1−1 1 1 −1−2 −6 0 1
•Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
x+2 = u2 − ∆ = 4 − 1 = 3
(
x+B
)
= y0 + ∆y2 =
12212
+ 1
1−21
=
13
013
xB+ =
13
313
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
0 2 0]
1 1/2 00 1/2 00 1/2 1
=[
0 1 0]
105
Costos reducidos:
rTD = cT
D − πT D =[
1 −1 0 3]
−[
0 1 0]
2 −2 0 1−1 1 1 −1−2 −6 0 1
=
[
2 −2 −1 4]
l l l l≥ 0 6≥ 0 6≥ 0 ≥ 0
q = 4
Luego, x4 entra a la base subiendo.
Tercer paso: Calculo de la columna entrante en el Tableaux
y4 = B−1A4 =
1 1/2 00 1/2 00 1/2 1
−21−6
=
−3/2
1/2
−11/2
Variable saliente:
γ1 = Min
·,3 − 1
1/2
, ·
= 4
γ2 = Min {·, ·, ·} = ·
γ3 = 5 − 2 = 3
⇒ ∆ = Min {4, ·, 3} = 3
Luego, x4 cambia de cota inferior a cota superior y no hay cambio de base.Los datos para la nueva iteracion son:
B = {5, 2, 7}, D = {l1,
u4,
l6,
l3},
B−1 =
1 1/2 00 1/2 00 1/2 1
y D =
2 −2 0 1−1 1 1 −1−2 −6 0 1
•Cuarta iteracion
Primer paso: Calculo del lado derecho del Tableaux.
(
x+B
)
= xB+ = y0 − ∆y4 =
13313
− 3
−3/21/2
−11/2
=
35/23/259/2
106 CAPITULO 5. SIMPLEX CON COTAS
Segundo paso
Como no cambia la base, no cambian los valores de πT , ni los costos reduci-dos.
rTD =
[
2 −2 −1 4]
l u l l≥ 0 ≤ 0 6≥ 0 ≥ 0
q = 6
Luego, x6 entra a la base subiendo.
Tercer paso: Calculo de la columna entrante en el Tableaux
y6 = B−1A6 =
1 1/2 00 1/2 00 1/2 1
010
=
1/2
1/2
1/2
Variable saliente:
γ1 = Min
35/2− 0
1/2,3/2 − 1
1/2
,59/2 − 0
1/2
= 1
γ2 = Min {·, ·, ·} = ·
γ3 = ·
⇒ ∆ = Min {1, ·, ·} = 1
Ası, p = 2 y el pivote
Luego, x2 sale de la base en su cota inferior.
Nueva Base:
Matriz de pivote.
P2 =
[η2]
100
1/2−1/2
11/21/2−1/2
001
=
1 −1 00 2 00 −1 1
Ası:
B−1+ = P2B
−1 =
1 −1 00 2 00 −1 1
1 1/2 00 1/2 00 1/2 1
=
1 0 00 1 00 0 1
107
y los datos para la nueva iteracion son:
B = {5, 6, 7}, D = {l1,
u4,
l3,
l2},
B−1 =
1 0 00 1 00 0 1
y D =
2 −2 1 −1−1 1 −1 2−2 −6 1 −1
•Quinta iteracion
Primer paso: Calculo del lado derecho del Tableaux.
x+6 = l6 + ∆ = 0 + 1 = 1
(
x+B
)
= y0 − ∆y6 =
35/23/259/2
− 1
1/21/21/2
=
17
129
xB+ =
17
129
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
0 0 0]
1 0 00 1 00 0 1
=[
0 0 0]
Costos reducidos:
rTD = cT
D − πT D =[
1 −1 3 2]
−[
0 0 0]
2 −2 1 −1−1 1 −1 2−2 −6 1 −1
=
[
1 −1 3 2]
l u l l≥ 0 ≤ 0 ≥ 0 ≥ 0
FIN
Los valores optimos del problema estandarizado son:
x5
x6
x7
= y0 =
17129
y
x1
x4
x3
x2
=
0501
108 CAPITULO 5. SIMPLEX CON COTAS
Luego, la solucion del problema original queda:
x =
x1
x2
x3
x4
=
0105
y el valor optimo del problema es:
v(P) = 1 · 0 + 2 · 1 + 3 · 0 − 1 · 5 = −3
(iv) El Simplex con Cotas, al considerar las restricciones de cotas como tales,disminuye la cantidad de variables de holgura y/o exceso y el tamano de labase, con la consecuente disminucion en el tamano del problema y la cantidadde operaciones que se necesita para resolverlo.
109
Ejercicio 5.3 (†)
Considere el problema lineal:
P) Min −2x1 −x2+3x3
3x1 +x2−x3 ≤12
x2−2x3≤8
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 6
−4 ≤ x3 ≤ 0
(i) (1 Pto.) Antes de resolver, muestre que el problema admite al menos unasolucion optima.
(ii) (5 Ptos.)Resuelva el problema anterior mediante el Metodo Simplex Re-visado con Inversa Explıcita para Variables con Cotas.
Para ello, reformule primeramente el problema en formato estandar equi-valente para variables con restricciones de cotas. En seguida, considerelas variables originales fuera de base, con los siguientes valores iniciales:x1 = 3, x2 = 6, x3 = 0, para luego construir una base factible inicialutilizando el Metodo de la Fase I, con la menor cantidad de variablesartificiales.
Solucion
(i) Se tiene que (x1, x2, x3) = (0, 0, 0) ∈ P . Luego:
P 6= φ (5.2)
Sea el poliedro P , definido por las restricciones:
0 ≤x1 ≤3
0 ≤x2 ≤6
−4 ≤x3 ≤0
Claramente P es acotado. Como P ⊆ P , resulta que P tambien es acotado.
Todo esto, junto con la continuidad de la funcion objetivo y la cerraduradel dominio de restriccion, cumple las hipotesis del “Teorema de Existencia deBolzano-Weierstrass”. Ası, P) admite solucion optima.
110 CAPITULO 5. SIMPLEX CON COTAS
(ii) Formato estandar:
P) Min −2x1 −x2+3x3
3x1 +x2−x3 +x4 =12
x2−2x3 +x5=8
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 6
−4 ≤ x3 ≤ 0
0 ≤ x4
0 ≤ x5
El problema queda mejor presentado si hacemos el cambio de variables x3 =−x3
2:
˜P) Min −2x1 −x2−3x3
3x1 +x2+x3 +x4 =12
x2+2x3 +x5=8
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 6
0 ≤ x3 ≤ 4
0 ≤ x4
0 ≤ x5
La solucion basica inicial x no es factible para el problema original P) (oequivalentemente, al menos una variable de holgura, tendrıa que ser menor que
cero en ˜P). Luego, se necesita hacer emplear dos fases.
Fase I
En este caso, x no cumple la primera restriccion (o equivalentemente, lax4 debe ser estrictamente menor que cero). Luego, necesitamos una variableartificial esta ultima:
2Este cambio de variables es opcional. Si no se hace, se llega a los mismos resultados
111
˜P) Min x6
3x1 +x2+x3 +x4 −x6=12
x2+2x3 +x5 =8
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 6
0 ≤ x3 ≤ 4
0 ≤ x4
0 ≤ x5
0 ≤ x6
Para formar la identidad, necesitamos multiplicar la primera restriccion por−1:
˜P) Min x6
−3x1 −x2−x3 −x4 +x6=−12
x2+2x3 +x5 = 8
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 6
0 ≤ x3 ≤ 4
0 ≤ x4
0 ≤ x5
0 ≤ x6
Nuestra base inicial es B = {6, 5} (de modo que las columnas de A, relacio-nadas con estas variables, formen la identidad).
Podemos obtener la matriz A y los vectores b y cT :
A =
[
−3 −1 −1 −1 0 10 1 2 0 1 0
]
b =
(
−128
)
cT =[
0 0 0 0 0 1]
.
Como las columnas 6 y 5 de la matriz A forman la identidad, reordenando lascolumnas de A, se tiene:
A =[
D B]
=
[
−3 −1 −1 −1 1 00 1 2 0 0 1
]
112 CAPITULO 5. SIMPLEX CON COTAS
De este modo, se tiene:
B = {6, 5}, D = {u1,
u2,
l3,
l4},
B =
[
1 00 1
]
, D =
[
−3 −1 −1 −10 1 2 0
]
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux3.
y0 = B−1b − B−1Dxd =
[
1 00 1
](
−128
)
−
[
1 00 1
] [
−3 −1 −1 −10 1 2 0
]
3600
=
(
32
)
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
1 0]
[
1 00 1
]
=[
1 0]
Costos reducidos:
rTD = cT
D − πT D =[
0 0 0 0]
−[
1 0]
[
−3 −1 −1 −10 1 2 0
]
=
[ 3 1 1 1 ]
u u l l6≤ 0 6≤ 0 ≥ 0 ≥ 0
q = 1
Luego, x1 entra a la base bajando.4
Tercer paso: Calculo de la columna entrante en el Tableaux
y1 = B−1A1 =
[
1 00 1
] [
−30
]
=
−3
0
3Notese que el calculo de y0 mediante la formula y0 = B−1b−B−1Dxd solo es “necesario.en
la primera iteracion.4Tambien podrıa haber sido x2.
113
Variable saliente:
γ1 = Min
{
3 − 0
3, ·
}
= 1
γ2 = Min {·, ·} = ·
γ3 = 3 − 0 = 3
⇒ ∆ = Min {1, ·, 3} = 1
Ası, p = 1 y el pivote
Luego, x6 sale de la base en su cota inferior y termina la Fase I.
Nueva Base:
Matriz de pivote.
P1 =
(
[η1][
1−303
]
00
)
=
[
−1/3 00 1
]
Ası:
B−1+ = P1B
−1 =
[
−1/3 00 1
] [
1 00 1
]
=
[
−1/3 00 1
]
y los datos para la Fase II son:
B = {1, 5}, D = {u2,
l3,
l4} y B−1 =
[
−1/3 00 1
]
Fase II
El problema ˜P) en formato estandar5:
˜P) Min −2x1 −x2−3x3
−3x1 −x2−x3 −x4 =−12
x2+2x3 +x5= 8
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 6
0 ≤ x3 ≤ 4
0 ≤ x4
0 ≤ x5
La matriz A y el vector cT para la Fase II son:
A =
[
−3 −1 −1 −1 00 1 2 0 1
]
cT =[
−2 −1 −3 0 0]
.
5Recordar que hemos multiplicado la primera restriccion por −1
114 CAPITULO 5. SIMPLEX CON COTAS
De la Fase I tenıamos que B = {1, 5} y D = {u2,
l3,
l4}. Entonces:
D =
[
−1 −1 −11 2 0
]
•Primera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
x+1 = u1 − ∆ = 3 − 1 = 2
(
x+B
)
= y0 + ∆y1 =
(
32
)
+ 1
(
−30
)
=
(
02
)
xB+ =
(
22
)
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
−2 0]
[
−1/3 00 1
]
=[
2/3 0]
Costos reducidos:
rTD = cT
D − πT D =[
−1 −3 0]
−[
2/3 0]
[
−1 −1 −11 2 0
]
=
[
−1/3 −7/3 2/3]
u l l≤ 0 6≥ 0 ≥ 0
q = 3
Luego, x3 entra a la base subiendo.
Tercer paso: Calculo de la columna entrante en el Tableaux
y3 = B−1A3 =
[
−1/3 00 1
] [
−12
]
=
(
1/3
2
)
Variable saliente:
γ1 = Min
{
2 − 0
1/3,2 − 0
2
}
= 1
γ2 = Min {·, ·} = ·
γ3 = 4 − 0 = 4
⇒ ∆ = Min {1, ·, 4} = 1
115
Ası, p = 2 y el pivote
Luego, x5 sale de la base en su cota inferior.
Nueva Base:
Matriz de pivote.
P2 =
(
[η2]
10
[
1/3−212
]
)
=
[
1 −1/60 1/2
]
Ası:
B−1+ = P2B
−1 =
[
1 −1/60 1/2
] [
−1/3 00 1
]
=
[
−1/3 −1/60 1/2
]
y los datos para la nueva iteracion son:
B = {1, 3}, D = {u2,
l4,
l5}, B−1 =
[
−1/3 −1/60 1/2
]
y D =
[
−1 −1 01 0 1
]
•Segunda iteracion
Primer paso: Calculo del lado derecho del Tableaux.
x+3 = l3 + ∆ = 0 + 1 = 1
(
x+B
)
= y0 − ∆y3 =
(
22
)
− 1
(
1/32
)
=
(
5/3
0
)
xB+ =
(
5/3
1
)
Segundo paso: Calculo del vector de multiplicadores π.
πT = cTBB−1 =
[
−2 −3]
[
−1/3 −1/60 1/2
]
=[
2/3 −7/6]
Costos reducidos:
rTD = cT
D − πT D =[
−1 0 0]
−[
2/3 −7/6]
[
−1 −1 01 0 1
]
=
[
5/6 2/3 7/6]
u l l6≤ 0 ≥ 0 ≥ 0
q = 2
116 CAPITULO 5. SIMPLEX CON COTAS
Luego, x2 entra a la base bajando.
Tercer paso: Calculo de la columna entrante en el Tableaux
y2 = B−1A2 =
[
−1/3 −1/60 1/2
] [
−11
]
=
(
1/61/2
)
Variable saliente:
γ1 = Min {·, ·} = ·
γ2 = Min
{
3 − 5/3
1/6,4 − 1
1/2
}
= 6
γ3 = 6 − 0 = 6
⇒ ∆ = Min {·, 6, 6} = 6
Ası, no hay cambio de base, y x2 cambia de cota superior a inferior6 y losdatos para la nueva iteracion son:
B = {1, 3}, D = {l2,
l4,
l5}, B−1 =
[
−1/3 −1/60 1/2
]
y D =
[
−1 −1 01 0 1
]
•Tercera iteracion
Primer paso: Calculo del lado derecho del Tableaux.
(
x+B
)
= xB+ = y0 + ∆y2 =
(
5/31
)
+ 6
(
1/61/2
)
=
(
8/34
)
Segundo paso.
Como la base no cambia, no cambia el vector de multiplicadores π, ni loscostos reducidos.
rTD =
[
5/6 2/3 7/6]
l l l≥ 0 ≥ 0 ≥ 0
F IN
Los valores optimos del problema estandarizado son:
(
x1
x3
)
= y0 =
(
8/34
)
y
x2
x4
x5
=
000
6Tambien podrıa haber salido x3 en su cota superior, los resultados finales deben ser losmismos
117
Luego, la solucion del problema original (reemplazando x3 por −x3) queda:
x =
x1
x2
x3
=
8/30−4
y el valor optimo del problema es:
v(P) = −2 · 8/3 + −1 · 0 + 3 · −4 = −52/3
118 CAPITULO 5. SIMPLEX CON COTAS
Capıtulo 6
Problema de Transporte
Ejercicio 6.1 (†)
Una empresa naviera requiere una flota de barcos para el transporte diario decarga entre seis ciudades. Hay cuatro rutas especıficas que deben ser cubiertasdiariamente. Estas rutas, con sus respectivas demandas por barcos disponiblesdiariamente al inicio de ellas, estan definidas en la siguiente tabla:
Ruta Origen Destino Barcos requeridos diariamente1 Dharan Nueva York 32 Marsella Estambul 23 Napoles Bombay 14 Nueva York Marsella 1
Toda la carga es del mismo tipo, de modo que se requiere un solo tipo debarco. Los tiempos de viaje, medidos en dıas de navegacion, entre las distintasciudades, estan dados en la siguiente tabla:
Napoles Marsella Estambul Nueva York Dharan BombayNapoles 0 1 2 14 7 7Marsella 1 0 3 13 8 8Estambul 2 3 0 15 5 5
Nueva York 14 13 15 0 17 20Dharan 7 8 5 17 0 3Bombay 7 8 5 20 3 0
Por otro lado, tanto la carga de un barco en un puerto de origen cualquiera,como la descarga de un barco en un puerto de destino cualquiera, toma exacta-mente un dıa.
Teniendo en cuenta que cada barco que completa una cualquiera de estasrutas, debe ser reasignado para ir a cubrir posteriormente otra ruta, que pu-
119
120 CAPITULO 6. PROBLEMA DE TRANSPORTE
diere ser, eventualmente, la misma que acaba de cubrir, se pide establecer unmodelo lineal para determinar la mınima cantidad de barcos que la empresadebe comprar para satisfacer diariamente todos los requerimientos anteriores.
Para ello, designe por xij la cantidad diaria de barcos que, luego de com-pletar la ruta i, deben ir a cubrir la ruta j. Suponga, por simplicidad, que xij
esta definida como variable real, es decir, con valores en R.
En seguida, imponga que todos los barcos que diariamente dejan una ciertaruta, deben ser reasignados para ir a cubrir una cualquiera de las otras rutas,incluida la ruta que acaban de cubrir. Esta cantidad de barcos define la ofertadiaria de barcos asociada a esta ruta. Igualmente, imponga que en cada unade las rutas se satisfaga los requerimientos diarios de barcos, ya sea mediantebarcos provenientes de cubrir otras rutas y/o ellas mismas. Esta ultima cantidadde barcos, define la demanda asociada a esa ruta.
Finalmente, como se trata de minimizar el tamano de la flota, el costo cij
(∀i, j = 1, . . . , 4) denotara el mınimo numero de barcos comprometidos diaria-mente entre el puerto de origen de la ruta i y el puerto de origen de la ruta j,para garantizar un flujo de un barco diario a traves de barcos que, saliendo dela ruta i, sean reasignados a la ruta j. Ası, por ejemplo, c23 = 7, es decir, serequiere de siete barcos entre los puertos de Marsella y Napoles para garantizarla reasignacion diaria de un barco desde la ruta 2, hacia la ruta 3. Este costocorresponde al numero total de dıas que requiere un barco para estar en condi-ciones de servir la ruta 3, luego de iniciar su servicio en la ruta 2, incluyendolos tiempos de carga y descarga en la misma ruta 2.
(i) (3 ptos.) Formule el problema como un Modelo Clasico de Transporte(balanceado), con solo cuatro nodos de oferta y cuatro nodos de demanda
(ii) (1 pto.) Muestre que este modelo admite al menos una solucion optimacon valores enteros.
(iii) (2 ptos.) Resuelva el modelo resultante mediante el Algoritmo Simplexcon Inversa Implıcita especializado al Problema de Transporte.
121
Solucion
(i) Formulacion del problema:
P) Min4∑
i=1
4∑
j=1
Cijxij
4∑
j=1
xij ≤ Oi ∀i = 1, . . . , 4
4∑
i=1
xij ≥ Dj ∀j = 1, . . . , 4
xij ≥ 0 ∀i, j = 1, . . . , 4
donde xij es la cantidad diaria de barcos que, luego de completar la ruta i,deben ir a cubrir la ruta j.
Los parametros del modelo son:
Cij =
36 32 33 1910 8 7 2012 17 16 2923 15 16 28
, O = D =
3211
.
Como∑4
i=1 Oi =∑4
j=1 Dj = 7, el problema esta balanceado.
(ii) Como P) es una Problema de Hitchcock balanceado, P) admite solucionoptima 1. Por las mismas razones, el Metodo Simplex aplicado a este tipo deproblemas provee una solucion optima entera en un numero finito de iteraciones.
(ii) Utilizando la Regla Nor-oeste, se obtiene la siguiente solucion factible inicialdegenerada:
3 02 0
1 01
1Tambien se puede demostrar por los teoremas de existencia de la programacion lineal yno-lineal
122 CAPITULO 6. PROBLEMA DE TRANSPORTE
•Primera iteracion
Calculo de π.
u36 32 44
8 7 2016 29 29
28 28v −8 −12 −13 0
Costos reducidos.
· · 2 −25−2 · · 0−9 0 · ·3 −1 1 ·
Variable saliente.
3 0 − ∆ +∆2 + ∆ 0 − ∆
1 + ∆ 0 − ∆1
Nueva Solucion Basica
3 02 0
1 01
•Segunda iteracion
Calculo de π.
u36 19 19
8 7 2016 29 29
28 28v 17 −12 −13 0
Costos reducidos.
· 25 27 ·−27 · · 0−34 0 · ·−22 −1 1 ·
Variable saliente.
3 − ∆ 0 + ∆2 0
+∆ 1 0 − ∆1
123
Nueva Solucion Basica
3 02 0
0 11
•Tercera iteracion
Calculo de π.
u36 19 19
8 7 −1412 16 −5
28 28v 17 22 21 0
Costos reducidos.
· −9 −7 ·7 · · 34· 0 · 34
−22 −35 −33 ·
Variable saliente.
3 − ∆ 0 + ∆2 − ∆ 0 + ∆
0 + ∆ 1 − ∆+∆ 1 − ∆
Nueva Solucion Basica
2 11 1
1 01
•Cuarta iteracion
Calculo de π.
u36 19 19
8 7 −1412 16 −5
15 −7v 17 22 21 0
124 CAPITULO 6. PROBLEMA DE TRANSPORTE
Costos reducidos.
· −9 −7 ·7 · · 34· 0 · 34
13 · 2 35
Variable saliente.
2 − ∆ +∆ 11 − ∆ 1 + ∆
1 + ∆ 0 − ∆1
Nueva Solucion Basica
2 0 11 1
11
•Quinta iteracion
Calculo de π.
u36 32 19 19
8 7 −512 −5
15 2v 17 13 12 0
Costos reducidos.
· · 2 ·−2 · · 25· 9 9 344 · 2 26
Variable saliente.
2 − ∆ 0 + ∆ 1+∆ 1 − ∆ 11
1
Nueva Solucion Basica
1 1 11 11
1
125
•Sexta iteracion
Calculo de π.
u36 32 19 1910 7 −712 −5
15 2v 17 13 14 0
Costos reducidos.
· · 0 ·· 2 · 27· 9 7 344 · 0 26
Fin, la solucion encontrada es optima.
126 CAPITULO 6. PROBLEMA DE TRANSPORTE
Ejercicio 6.2 (†)
Un banquetero debe disponer de manteles limpios para realizar sendos banquetesen los cuatro siguientes dıas, con demandas de 100, 130, 150 y 140 unidades,respectivamente. Para ello, dispone de un stock inicial de 200 manteles limpios,de la posibilidad de comprar manteles en todo momento y sin lımite de cantidad,a un precio de $12 la unidad, y de la posibilidad de enviar a lavar manteles enservicio rapido, de un banquete para el siguiente a $ 6 la unidad, o en serviciolento, de un banquete para el subsiguiente, a $4 la unidad.
(i) Formule el problema de aprovisionamiento de manteles limpios a mınimocosto total, como un problema clasico de transporte de Hitchcock, debi-damente balanceado. Para ello, utilice la descripcion grafica del problemaa traves de la red de transporte correspondiente.
(ii) Resuelva el Modelo Balanceado resultante, utilizando la especializaciondel Metodo Simplex, con la regla Nor-Oeste para la construccion de unasolucion basica factible inicial.
(iii) Aplicando el criterio de optimalidad del Simplex, estudie hasta que nivelpuede aumentar el costo del lavado en servicio lento, sin que cambie elcosto optimo del problema obtenido en ii).
Solucion
(i) Formulacion del problema:
CbC = 520
O3bO3
= 150
O2bO2
= 130
O1bO1
= 100
SbS = 200
D4bD4
= −140
D3bD3
= −150
D2bD2
= −130
D1bD1
= −100
0 b0 = −580
127
donde la matriz de costos es:
D1 D2 D3 D4 0
S 0 0 0 0 01 ∞ 6 4 4 02 ∞ ∞ 6 4 03 ∞ ∞ ∞ 6 0C 12 12 12 12 0
Notar que la demanda del nodo de balanceo (nodo 0) es tal que∑
i bi = 0.
(ii) Utilizando la Regla Nor-oeste, se obtiene la siguiente solucion factible inicial:
100 10030 70
80 5090 60
520
•Primera iteracion
Calculo de π.
u0 0 −10
6 4 −46 4 −2
6 0 00 0
v 10 10 8 6 0
Costos reducidos.
· · 2 4 10∞ · · 2 4∞ ∞ · · 2∞ ∞ ∞ · ·2 2 4 6 ·
Fin, la solucion encontrada es optima.
(ii) Supongamos que el costo del servicio de lavado rapido aumenta en ǫ, ǫ > 0.Nuestra nueva matriz de costos es:
D1 D2 D3 D4 0
S 0 0 0 0 01 ∞ 6 4 + ǫ 4 + ǫ 02 ∞ ∞ 6 4 + ǫ 03 ∞ ∞ ∞ 6 0C 12 12 12 12 0
128 CAPITULO 6. PROBLEMA DE TRANSPORTE
El nuevo π.
u0 0 −10 + 2ǫ
6 4 + ǫ −4 + 2ǫ6 4 + ǫ −2 + ǫ
6 0 00 0
v 10 − 2ǫ 10 − 2ǫ 8 − ǫ 6 0
y los nuevos costos reducidos.
· · 2 − ǫ 4 − 2ǫ 10 − 2ǫ∞ · · 2 − ǫ 4 − 2ǫ∞ ∞ · · 2 − ǫ∞ ∞ ∞ · ·
2 + 2ǫ 2 + 2ǫ 4 + ǫ 6 ·
Para que la solucion optima no cambie, los costos reducidos deben perma-necer positivos (tomando en cuenta que la solucion es no-degenerada). Comoǫ > 0, esto es equivalente a:
2 − ǫ ≥ 0
4 − 2ǫ ≥ 0
10 − 2ǫ ≥ 0
⇒ ǫ ≤ 2
Luego, el costo del lavado en servicio lento puede aumentar hasta 6.
129
Ejercicio 6.3
Considere una empresa que fabrica un solo producto. Esta empresa posee mfabricas para producir el producto y n centros de distribucion, los cuales pue-den recibir productos desde cualquiera de las m fabricas. Todos los productosfabricados son destinados a algun centro de distribucion. Los costos unitariosde transporte entre los puertos i y j son denotados por cij (i = 1, . . . , m yj = 1, . . . , n). Cada fabrica produce un total de ai productos (i = 1, . . . , m)y cada centro de distribucion entrega bj productos (j = 1, . . . , n). Supongaademas que existe un exceso de oferta y que, en estas circunstancias, algunosde los centros de distribucion (por simplicidad y sin perdida de generalidad, losr primeros centros de distribucion, con r ≤ n), estan dispuestos a recibir endemasıa toda la cantidad sobrante que les pudiere ser asignada. Se desea cono-cer la cantidad de producto que debe ser enviada desde cada fabrica hacia cadacentro de distribucion, de modo de minimizar los costos totales de transporte.
(i) Establezca si este problema puede ser modelado como un “Modelo deTransporte de Hitchcock”. En caso afirmativo, explicite graficamente elmodelo resultante. En caso contrario, establezca un modelo lineal quepermita resolver el problema planteado.
(ii) En cualquier caso, balancee el modelo resultante y establezca bajo que con-diciones, este admite solucion optima.
(iii) Resuelva el modelo para la siguiente instancia:
m = 2, n = 3, r = 2, [ai] =
(
57
)
, [bj ] =
326
[Cij ] =
[
6 7 94 3 5
]
.
130 CAPITULO 6. PROBLEMA DE TRANSPORTE
Solucion
(i) Si denotamos por ∆ al exceso de oferta:
∆ =
m∑
i=1
ai −
n∑
j=1
bj
Podemos formular el problema como:
Omam
...
O2a2
O1a1
0(r − 1)∆
Dn bn
...
Dr+1 br+1
Dr br + ∆
...
D1 b1 + ∆
Notar que el nodo adicional solo tiene arcos hacia los r primeros nodos.
131
La matriz de costos tiene la forma:
D1 ... Dr Dr+1 ... Dn
0 0 . . . 0 ∞ . . . ∞O1 C1,1 . . . C1,r C1,r+1 . . . C1,n
O2 C2,1 . . . C2,r C2,r+1 . . . C2,n
... . . . . . . . . . . . . . . . . . .Om Cm,1 . . . Cm,r Cm,r+1 . . . Cm,n
(ii) Como no existen arcos entre todos los nodos, no basta con decir que la redesta balanceada para demostrar existencia. Para esto, utilizaremos el Teorema
de Existencia de la Programacion No-Lineal.
Cada flujo es no-negativo, luego:
0 ≤ xij ≤n∑
j=1
xij = ai, i = 1, . . . , m; j = 1, . . . , n.
Ası, el dominio del problema esta acotado.
Por otro lado tenemos una solucion factible (y ademas basica), que consisteen generar una solucion factible (basica) con la Regla Nor-Oeste para los todoslos nodos de origen, exceptuando el nodo artificial cero, y para todos los nodos dedestino, pero dejando solamente uno con la demanda adicional ∆ (Esta ultimaes una red clasica de Hitchcock, balanceada y con arcos entre todos los nodos,por lo que la generacion de la solucion factible (basica) esta garantizada). Luegose asigna las (r − 1)∆ unidades de oferta restantes provenientes del nodo cero,a los r− 1 nodos de demanda que no quedaron con demanda adicional en la redbalanceada anterior2.
Ası, se cumplen las hipotesis del Teorema de Existencia de la Programacion
No-Lineal, y el problema admite solucion optima siempre.
(iii) Para la instancia particular se tiene los siguientes datos sobre la red deHitchcock modificada:
m = 3, n = 3, [ai] =
157
, [bj ] =
436
[Cij ] =
0 0 ∞6 7 94 3 5
.
A continuacion se resuelve el problema mediante la especializacion del Sim-plex para el modelo de Hitchcock.
Utilizando la Regla Nor-oeste, se obtiene la siguiente solucion factible inicial:
13 2
1 6
2Este proceso es solo para demostrar factibilidad. En la practica, para encontrar una so-lucion basica factible inicial, basta con aplicar la Regla Nor-Oeste directamente sobre la redbalanceada.
132 CAPITULO 6. PROBLEMA DE TRANSPORTE
•Primera iteracion
Calculo de π.
u0 36 7 9
3 5 5v −3 −2 0
Costos reducidos.
· −1 ∞· · 02 · ·
Variable saliente.
1 − ∆ +∆3 + ∆ 2 − ∆
1 6
Nueva Solucion Basica
14 1
1 6
•Segunda iteracion
Calculo de π.
u0 2
6 7 93 5 5
v −3 −2 0
Costos reducidos.
1 · ∞· · 02 · ·
Fin, la solucion encontrada es optima.
133
Alternativamente, la red se puede plantear agregando r nodos de demanda:
Omam
...
O2a2
O1a1
0(r − 1)∆
Dn bn
...
Dr+1 br+1
Dr br
...
D1 b1
Dr∆
...
D1∆
cuyos costos desde los nodos de oferta originales replican los costos desde estos
134 CAPITULO 6. PROBLEMA DE TRANSPORTE
mismos arcos, hacia los r primeros nodos originales. Los costos desde el arcocero siguen siendo nulos:
D1 ... Dr D1 ... Dr Dr+1 ... Dn
0 0 . . . 0 ∞ . . . ∞ ∞ . . . ∞O1 C1,1 . . . C1,r C1,1 . . . C1,r C1,r+1 . . . C1,n
O2 C2,1 . . . C2,r C2,1 . . . C2,r C2,r+1 . . . C2,n
... . . . . . . . . . . . . . . . . . . . . . . . . . . .Om Cm,1 . . . Cm,r Cm,1 . . . Cm,r Cm,r+1 . . . Cm,n
Esta formulacion, si bien es mas compleja, puede ser util en caso de que losr primeros nodos acepten productos en demasıa, pero a un costo distinto al querecibirıan los bj primeros productos. En este caso Ci, 6= Ci,j , donde j = 1 . . . , r(subındice de los nodos de demanda originales Dj) y = 1 . . . , r (subındice de
los nodos de demanda adicionales D).
Capıtulo 7
Especializacion del Simplex
a Problemas de Redes
Ejercicio 7.1 Redes sin cotas
Considere el siguiente problema de flujo en redes de costo mınimo con restric-ciones de cotas sobre los flujos balanceado.
1b1 = 1
2
b2 = 0
3b3 = 2
4b4 = −3
1
-1
1
5 3
-2
(i) Aplicando el Metodo Simplex para Flujo en Redes, estudie si este pro-blema admite o no solucion optima. Para ello, muestre primeramente queel problema admite flujos factibles (al menos uno), resolviendo la Fase Ide Simplex para este problema.
(ii) Si fuera el caso, encuentre una solucion optima del problema original, apli-cando el mismo algoritmo Simplex para Flujo en Redes de Costo Mınimode este problema, partiendo del arbol basico factible eventualmente en-contrado en (i).
135
136 CAPITULO 7. SIMPLEX DE REDES
Solucion
(i) Se tiene el siguiente problema de Fase I:
2
1
3
4
0 0
1
2
3
1
1
1
1
0
0
0
0
0
0
Primera iteracion
2
1
3
4
0 0
1
2
3
1
1
1
1
0
0
0
0
0
3
0
2
1
01π = −
22π = −
12π = −
32π = −
40π =
+∆
−∆
−∆
0
r12 =−2 + 0 − (−2) = 0 ≥ 0
r14 = −2 + 0 − (0) =−2 6≥ 0
Luego x14 entra a la base. ∆ = 1 ⇒ x10 sale de la base
137
Segunda iteracion
2
1
3
4
0 0
1
2
3
1
1
1
0
0
0
0
0
2
0
2
01π = −
22π = −
10π =
32π = −
40π =
+∆
−∆
1
−∆
0
r12 =0 + 0 − (−2) = 2 ≥ 0
r14 =−2 + 0 − (0) =−2 6≥ 0
Luego x24 entra a la base. ∆ = 0 ⇒ x02 sale de la base
Tercera iteracion
2
1
3
4
0 0
1
2
3
1
1
0
0
0
0
0
2
2
01π = −
20π =
10π =
32π = −
40π =
+∆
−∆
1
0
+∆
−∆
0
r12 = 0 + 0 − (0) = 0 ≥ 0
r14 =−2 + 0 − (0) =−2 6≥ 0
138 CAPITULO 7. SIMPLEX DE REDES
Luego x31 entra a la base. ∆ = 2 ⇒ x30 (o x04) sale de la base. Como quedasolo un arco artificial en la base, se termina la Fase I.
Ası, se tiene la siguiente solucion (basica degenerada) factible:
2
1
3
4
0
1
2
33
0
2
Faltarıa demostrar que cT x ≥ cte. Note que no podemos demostrar direc-tamente con las restricciones de no-negatividad de los flujos. Por otro lado nopodemos decir que los flujos estan acotados, puesto que tenemos circuitos en lared. Tenemos las siguientes restricciones de balance de los nodos:
x12+x14 −x31 = 1 (7.1)
−x12 +x24 −x32 = 0 (7.2)
x31+x32−x43= 2 (7.3)
−x14−x24 +x43=−3 (7.4)
Si restamos 2 veces la restriccion 7.1 a “menos” la restriccion 7.2 tenemos:
−x12 − 2x14 − x24 + 2x31 + x32 = −2
que implica:
−x12 − 2x14 − x24 + 2x31 + x32 ≥ −2 (7.5)
Por otro lado, de las restricciones de no-negatividad tenemos:
2x12 ≥ 0
3x31 ≥ 0
3x43 ≥ 0
(7.6)
y sumando 7.5 y 7.6 se llega a:
x12 − 2x14 − x24 + 5x31 + x32 + 3x43 ≥ −2 ⇒ cT x ≥ cte
139
(ii) Ahora resolvemos la Fase II:
Primera iteracion
2
1
3
4
0
1
2
3
1
5
-1
-2
1
21π =
12π =
33π = −
40π =
+∆
3
0
−∆
2
3
+∆
−∆
r12 = 2 − 1 + 1 = 2 ≥ 0
r32 =−3 + 1 − 1 =−3 6≥ 0
Luego x32 entra a la base. ∆ = 2 ⇒ x31 sale de la base.
Segunda iteracion
2
1
3
4
0
1
2
3
1
5
-1
-2
1
21π =
12π =
30π =
40π =
1
2
3
2
r12 =2 − 1 + 1 =2 ≥ 0
r31 =0 + 5 − 2 =3 ≥ 0
r43 =0 + 3 − 0 =3 ≥ 0
Fin, la solucion encontrada es optima.
140 CAPITULO 7. SIMPLEX DE REDES
Esta es la solucion final:
2
1
3
4
0
1
2
3
1
1
2
2
141
Ejercicio 7.2 (†) Redes sin cotas y Fase I economica
Resuelva, mediante la especializacion del Metodo Simplex, el siguiente problemadesbalanceado de Flujo en redes de Costo Mınimo:
3b3 = 2
4b4 = −3
1
b1 = 3
2
b2 = −1
1
4-23
3
i jCij
Nota: Como∑4
i=1 bi 6= 0, reformule primeramente el problema como unoequivalente balanceado, para luego aplicar el Metodo de las Dos Fases, con Fase IEconomica, al problema resultante.
Solucion
Se tiene:
4∑
i=1
bi = 3 + (−1) + 2 + (−3) = 1 > 0 ⇒ Hay exceso de oferta
Luego, se tiene que balancear la red agregando un nodo de demanda ficticiab5 = −1, como sigue:
31
1 2
3 4
5
1
-2
3
0
0
3
4
32
1
Nota: Se deja de tarea el Metodo de Flujo en Redes con Dos Fases Clasico,donde en la Fase I se agrega un nodo 0 a la red balanceada.
142 CAPITULO 7. SIMPLEX DE REDES
Alternativamente aplicaremos aquı una Fase I Economica, utilizando el “nodo
de Balanceo” 5 como “nodo cero” de la Fase I, . Ası, se tiene el siguienteproblema de Fase I:
31
1 2
3 4
5
0
0
0
0
0
0
0
32
1
1
1
Esto nos permite definir el siguiente arbol factible inicial
31
1 2
3 4
5
0
0
0
0
0
0
0
32
1
1
1
1
3
3
2
Este arbol esta compuesto por cuatro arcos basicos:
(i) Los dos arcos de balanceo (1, 5) y (3, 5) con costos nulos
(ii) Los arcos artificiales (5, 2) y (5, 4), con costos artificiales iguales a 1.
De hecho, todos los arcos originales del problema estan con costo nulo en laFase 1 Economica. No obstante, los arcos de balanceo seguiran teniendo costonulo en la Fase II, obviamente.
143
Fase I
Primera iteracion
31
1 2
3 4
5
0
0
0
0
0
0
0
32
1
1
1
1
3
3
250π =
−∆
10π =
21π =
30π =
41π =
+∆
−∆
r12 =0 + 0 − 1 = − 1 6≥ 0
Luego x12 entra a la base. ∆ = 1 ⇒ x52 sale de la base
Segunda iteracion
31
1 2
3 4
5
0
0
0
0
0
0
0
32
1
1
1
3
2
250π =
10π =
20π =
30π =
41π =
+∆
−∆
+∆
−∆
r24 =0 + 0 − 1 = − 1 6≥ 0
Luego x24 entra a la base. ∆ = 2 ⇒ x15 sale de la base
144 CAPITULO 7. SIMPLEX DE REDES
Tercera iteracion
31
1 2
3 4
5
0
0
0
0
0
0
0
32
1
1
3
1
2
250π =
11π =
21π =
30π =
41π =
−∆
+∆
−∆
r34 =0 + 0 − 1 = − 1 6≥ 0
Luego x34 entra a la base. ∆ = 1 ⇒ x54 sale de la base. Como (5, 4) era elultimo arco artificial en la base, el nuevo arbol basico resulta factible para elproblema original (balanceado), es decir, define un arbol basico factible inicialpara la Fase II, como sigue:
31
1 2
3 4
5
0
0
0
0
0
0
0
32
1
3
1
2
1
Nota: Vale la pena observar que, en el caso de la Fase I Economica, a diferenciade la Fase I (a secas), la red extendida tiene igual numero de nodos que lared original (ya balanceada). Por esta razon, en el caso “Economica”, la Fase Itermina en cuanto todos los arcos artificiales han dejado la base.
145
Fase II
Primera iteracion
31
1 2
3 4
5
1
-2
3
0
0
3
4
32
1
3
1
2
150π =
12π = −
21π = −
30π =
43π =−∆
+∆ +∆
r13 = −1 + 3 − 0 = 1 ≥ 0
r32 =0 + (−2) − (−1) =−1 6≥ 0
Luego x32 entra a la base. ∆ = 1 ⇒ x34 sale de la base
Segunda iteracion
31
1 2
3 4
5
1
-2
3
0
0
3
4
32
1
3
1 3
150π =
13π = −
22π = −
30π =
42π =
−∆
+∆
+∆
−∆
r15 =−3 + 0 − 0 = − 3 6≥ 0
Luego x15 entra a la base. ∆ = 1 ⇒ x35 sale de la base
146 CAPITULO 7. SIMPLEX DE REDES
Tercera iteracion
31
1 2
3 4
5
1
-2
3
0
0
3
4
32
1
2
23
1
50π =
13π = −
22π = −
30π =
42π =
r13 =0 + 3 − 3 =0 ≥ 0
r34 =3 + 3 − 5 =1 ≥ 0
r13 =3 + 0 − 0 =3 ≥ 0
Luego el arbol basico encontrado es optimo.
147
Ejercicio 7.3 (†) Redes con cotas
Considere el siguiente problema de flujo en redes de costo mınimo con restric-ciones de cotas sobre los flujos balanceado.
1b1 = 1
2
b2 = 0
3b3 = 2
4b4 = −3
(0,5,1)
(0,2,-1
)
(0,2
,1)
(0,5,
5)(0,5,3)
(1,3,-2)
(i) (3 Puntos) Aplicando el Metodo Simplex para Flujo en Redes, estudie sieste problema admite o no solucion optima. Para ello, muestre primera-mente que el problema admite flujos factibles (al menos uno), resolviendopara ello un problema de Fase I, donde el arbol basico factible inicialconsidere todos los flujos sobre los arcos originales de la red, en su cotasuperior.
(ii) (3 Puntos) Si fuera el caso, encuentre una solucion optima del problemaoriginal, aplicando el mismo algoritmo Simplex para Flujo en Redes deCosto Mınimo de este problema, partiendo del arbol basico factible even-tualmente encontrado en (i).
148 CAPITULO 7. SIMPLEX DE REDES
Solucion
(i) Se tiene el siguiente problema de Fase I:
2
1
3
4
0 0
1
2
3
(0,-,1)
(0,5,0)
0
(0,-,1)
(0,-,1)
(0,2,0)
(1,3,0)
(0,5,0)
(0,2,0)
(0,-,1)
Primera iteracion
2
1
3
4
0 0
1
2
3
3
5
0
2
0 1π = −
2 2π = −
1 0π =
3 2π = −
4 0π =
−∆5
u
2
u
2
u
5
u5u
3
u
−∆
−∆
r12 =0 + 0 + 2 =2u
6≤ 0
Luego x12 entra a la base bajando. ∆ = 2 ⇒ x01 sale de la base en cota l.
149
Segunda iteracion
2
1
3
4
0 0
1
2
3
3
3
0
0 1π = −
2 2π = −
1 2π = −
3 2π = −
4 0π =
−∆
3
2
u
2
u
5u
5u
3
u
−∆−∆
r14 =−2 + 0 + 0 =−2u≤ 0
r24 =−2 + 0 + 0 =−2u≤ 0
r31 =−2 + 0 + 2 = 0u≤ 0
r32 =−2 + 0 + 2 = 0u≤ 0
r43 = 0 + 0 + 2 = 2u
6≤ 0
Luego x43 entra a la base bajando. ∆ = 0 ⇒ x03 sale de la base en cota l.
Tercera iteracion
2
1
3
4
0 0
1
2
3
3
3
0 1π = −
2 2π = −
1 2π = −
3 0π =
4 0π =
−∆
3
2
u
2
u
5
u
5
3
u
−∆
−∆
−∆
−∆
150 CAPITULO 7. SIMPLEX DE REDES
r14 =−2 + 0 + 0 =−2u≤ 0
r24 =−2 + 0 + 0 =−2u≤ 0
r31 = 0 + 0 + 2 = 2u
6≤ 0
Luego x31 entra a la base bajando. ∆ = 3 ⇒ x20 (o x04) sale de la base. Comoqueda solo un arco artificial en la base, se termina la Fase I.
Ası, se tiene la siguiente solucion (basica degenerada) factible:
2
1
3
4
0
1
2
3
0
2
u
2
u
2 2
3
u
Faltarıa demostrar que cT x ≥ cte (para utilizar el Teorema General de Existen-cia). Sin embargo, como todos los flujos por los arcos estan acotados, es masfacil utilizar el hecho de que el posliedro de soluciones factibles es acotado y que,por el Teorema de Bolzano-Weierstrass, el problema admite solucion optima.
(ii) Ahora resolvemos la Fase II:
Primera iteracion
2
1
3
4
0
1
2
3
2 9π =
18π =
33π =
40π =
0
2
u
2
u
2 2
3
u
−∆
−∆−∆
r14 =8 − 2 + 0 =6u
6≤ 0
151
Luego x14 entra a la base bajando. ∆ = 0 ⇒ x14 cambia de estado a cota l.
Segunda iteracion
2
1
3
4
0
1
2
3
29π =
18π =
33π =
40π =
0
2
u
2
u
0 0
1
l
−∆
−∆
−∆
−∆
r14 =8 − 2 + 0 =6l≥ 0
r24 =9 − 1 + 0 =8u
6≤ 0
Luego x24 entra a la base bajando. ∆ = 0 ⇒ x12 sale de la base en cota l.
Tercera iteracion
2
1
3
4
0
1
2
3
21π =
18π =
3 3π =
4 0π =
0
2
u
2
0 0
1
l
−∆
−∆
−∆
l
r12 =8 + 1 − 1 =8l≥ 0
r14 =8 − 2 + 0 =6l≥ 0
r32 =3 + 1 − 1 =3u
6≤ 0
152 CAPITULO 7. SIMPLEX DE REDES
Luego x32 entra a la base bajando. ∆ = 0 ⇒ x43 sale de la base en cota l.
Cuarta iteracion
2
1
3
4
0
1
2
3
21π =
15π =
30π =
40π =
0
2
20 0
1
l
l
l
r12 =5 + 1 − 1 =5l≥ 0
r14 =5 − 2 + 0 =3l≥ 0
r43 =0 + 3 − 0 =3l≥ 0
Fin, la solucion encontrada es optima.
Esta es la solucion final:
2
1
3
4
0
1
2
3
2
2
1
Capıtulo 8
Flujo Maximo en Redes y
Metodo de Ford-Fulkerson
Ejercicio 8.1 (†)
Para la siguiente red de vuelos inter-ciudades, con restricciones de capacidad:
O
A
B
C
D
E
T2
4 1
5
2 7
4
4
31
5
7
se pide determinar el flujo maximo de pasajeros que puede ser transportadodesde el nodo O, hasta el nodo T , a traves de esta red. Sobre cada arco de lared se indica la capacidad del vuelo que une las dos ciudades o nodos corres-pondientes:
(i) (1 Pto.) Formule el problema de flujo maximo definido por esta red, bajoel formato clasico de programacion lineal para problemas de flujo en redesde costo mınimo. Explicite la funcion de costo y las distintas restriccionessobre los flujos.
(ii) (1 Pto.) Teniendo en cuenta (i), muestre, antes de resolver, que el problemade flujo maximo admite al menos una solucion optima.
153
154 CAPITULO 8. FLUJO MAXIMAL EN REDES
(iii) (4 Ptos.) Aplique el Algoritmo de Ford-Fulkerson a la determinacion delflujo maximo, con exploracion completa de los distintos nodos, siguiendola regla FIFO. Explicitar el cuello de botella.
Nota: Alternativamente, en (iii) puede aplicar el Simplex Revisado con In-versa de Base Explıcita para Flujo en Redes de Costo Mınimo, sobre la redasociada al problema definido en (i).
(i) El problema de Flujo Maximo se puede formular equivalentemente comoun problema de redes mediante un arco de retorno. Graficamente:
A
O
C
B
E
DT
(0,2,0)
(0,∞,-1)
(0,5,0)
(0,7,0)
(0,2,0)
(0,1,0)(0,4,0) (0
,1,0)
(0,4,0)
(0,3,0)
(0,4,0)(0,5,0)
(0,7,0)
Explıcitamente, si xij representa el flujo desde el nodo i hacia el nodo j, setiene la siguiente funcion objetivo a minimizar:
−xTO,
las siguientes restricciones de balance de flujos:
xTO = xOA + xOB + xOC
xOA = xAB + xAD
xOB + xAB + xCB = xBD + xBE
xOC = xCB + xCE
xAD + xBD + xED = xDT
xBE + xCE = xED + xET
xDT + xET = xTO,
155
las restricciones de cotas sobre los arcos capacitados:
0 ≤ xOA ≤ 2
0 ≤ xOB ≤ 5
0 ≤ xOC ≤ 4
0 ≤ xAD ≤ 7
0 ≤ xBD ≤ 4
0 ≤ xCB ≤ 1
0 ≤ xCE ≤ 4
0 ≤ xBE ≤ 3
0 ≤ xED ≤ 1
0 ≤ xDT ≤ 5
0 ≤ xET ≤ 7
y la restriccion de no-negatividad del flujo sobre el arco de retorno:
xTO ≥ 0
(ii) Este problema admite una solucion factible, luego P 6= φ. Por otro lado:
xDT + xET = xTO
xDT ≤ 5
xET ≤ 7
⇒ xTO ≤ 12.
Ası, todos los flujos estan acotados, luego P es acotado y por el Teorema de
Bolzano-Weierstrass el problema admite solucion optima.
(iii) A continuacion se muestra las iteraciones del Metodo de Ford-Fulkerson
1◦ iteracion
A
O
C
B
E
DT0
0
00
0
0
0
0
0 0
0
0
M E
O O
A A
B B
C C
D
E
atajo T
(O,2)
(O,4)
(O,5) (A,2)
(D,2)
(B,3)
(-,∞)
2
5
4 1
4
3
4
2
5
7
7
2∆ =
0
→
+∆
+∆+∆
156 CAPITULO 8. FLUJO MAXIMAL EN REDES
2◦ iteracion
A
O
C
B
E
DT2
2
00
0
0
0
2
0 0
0
0
M E
O O
B B
C C
D
E
A*
atajo T
(D,2)*
(O,4)
(O,5) (B,4)
(D,3)
(B,3)
(-,∞)
2
5
4 1
4
3
4
2
5
7
7
3∆ =
2
→
+∆ +∆+∆
3◦ iteracion
A
O
C
B
E
DT5
2
00
30
3
2
0 0
0
0
M E
O O
B B
C C
D D
E
A*
atajo T
(D,1)*
(O,4)
(O,2) (B,1)
(E,2)
(B,2)
(-,∞)
2
5
4 1
4
3
4
2
5
7
7
2∆ =
5
→
+∆
+∆
+∆
4◦ iteracion
A
O
C
B
E
DT5
2
20
3
0
5
2
0 0
0
2
M E
O O
C C
B B
E
D
atajo T
(O,4)
(C,1) (B,1)
(E,4)
(C,4)
(-,∞)
2
5
4 1
4
3
4
2
5
7
7
4∆ =
7
→
+∆
+∆
+∆
157
5◦ iteracion
A
O
C
B
E
DT5
2
60
3
0
5
2
4 0
4
2
M E
O O
(-,∞)
2
5
4 1
4
3
4
2
5
7
7
11
Corte mínimo de
flujo máximo
El flujo maximo por la red es 11.
158 CAPITULO 8. FLUJO MAXIMAL EN REDES
Capıtulo 9
Metodo de Descomposicion
de Dantzig-Wolfe
Ejercicio 9.1 (†)
Considere el siguiente problema de minimizacion del costo total de produccionde una fabrica, con dos talleres que comparten un unico recurso escaso:
P) Min −x1 −3x2+x3 −x4
x1 +x2 +x3 +x4 ≤8
x1 +x2 ≤6
x3 +2x4≤10
−x3 +x4 ≤4
x1, x2, x3, x4 ≥0
(i) (1 ptos.) Muestre que este problema admite al menos una polıtica optimade produccion.
(ii) (4 ptos.) Resuelva este modelo mediante el Metodo de Descomposicion deDantzig-Wolfe, con Inversa de Base Explıcita, de modo de obtener la des-centralizacion, por talleres, de la polıtica optima de produccion, a travesde la valorizacion optima de los recursos escasos. Para ello, resuelva losproblemas satelites con ayuda grafica, u otra equivalente, para la determi-nacion del menor costo reducido en cada una de estas iteraciones maestrasgeneradas. Explicite las distintas iteraciones.
(iii) (1 ptos.) ¿Que ventaja fundamental tiene la aplicacion de este metodo dedescomposicion, respecto de la aplicacion directa del Metodo Simplex almodelo P)?
159
160 CAPITULO 9. METODO DE DANTZIG-WOLFE
Solucion
(i) Claramente (x1, x2, x3, x4) = (0, 0, 0, 0) ∈ P es solucion de P). Luego, eldominio es no vacıo (P) 6= φ)
Por otro lado, de las restricciones:
x1 + x2 + x3 + x4 ≤ 8x1 ≥ 0x2 ≥ 0x3 ≥ 0x4 ≥ 0
⇒
0 ≤ x1 ≤ 80 ≤ x2 ≤ 80 ≤ x3 ≤ 80 ≤ x4 ≤ 8
Luego el dominio es acotado.
Ademas, las restricciones estan definidas por restricciones lineales de de-sigualdad. Luego el dominio es cerrado. Finalmente, la funcion objetivo es lineal,luego continua. Ası, por el Teorema de Bolzano Weierstrass, P) admite solucionoptima.
(ii) Formato estandar:
P) Min −x1 −3x2+x3 −x4
x1 +x2 +x3 +x4 +s=8
x1 +x2 ≤6
x3 +2x4 ≤10
−x3 +x4 ≤4
x1, x2, x3, x4 ≥0
donde la primera restriccion es de coordinacion (m0 = 1) y tenemos 2 satelites(N = 2), los cuales estan formados por las restricciones
x1 +x2≤6
x1, x2≥0
para el primer satelite y
x3 +2x4≤10
−x3 +x4 ≤4
x3, x4 ≥0
para el segundo.
Los datos para comenzar el Metodo de Dantzig-Wolfe con esta configuracionson
A01 =[
1 1]
y cT1 =
[
−1 −3]
161
para el primer satelite y
A02 =[
1 1]
y cT2 =
[
1 −1]
para el segundo. El nuevo lado derecho queda:
b =
811
A continuacion, se muestra los graficos de ambos satelites.
162 CAPITULO 9. METODO DE DANTZIG-WOLFE
•Grafico Satelite 1
0 1 2 3 4 5 60
1
2
3
4
5
6
x2
x1
(
00
) (
60
)
(
06
)
•Grafico Satelite 2
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
x4
x3
(
00
)
(
04
)
(
100
)
(
23143
)
Como el punto ~0 pertenece a P), no se necesita dos fases y los datos paracomenzar el metodo son:
P 11 =
(
00
)
, P 12 =
(
00
)
, B = {s, λ11, λ21} y B−1 = I.
•Primera iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b = I
811
=
811
Segundo paso.
Costos de las variables basicas en el maestro, PTB
Ps = cs = 0
P11 = cT1 P 1
1 =[
−1 −3]
(
00
)
= 0
P21 = cT2 P 1
2 =[
1 −1]
(
00
)
= 0
⇒ PTB =
[
0 0 0]
163
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
0 0 0]
I =[
0 0 0]
de donde:πT =
[
πT0 αT
]
=[
0 0 0]
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 −3]
−[
0] [
1 1]
)
(
x1
x2
)
− 0
x ∈ S1
⇒
P) Min −x1 −3x2
x1 +x2 ≤6
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
06
)
, v(S1) = −18 6≥ 0
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
1 −1]
−[
0] [
1 1]
)
(
x3
x4
)
− 0
x ∈ S2
⇒
P) Min x3 −x4
x3 +2x4≤10
−x3 +x4 ≤4
x3, x4 ≥0
Graficamente, tenemos1:
x2 =
(
04
)
, v(S2) = −4 6≥ 0
1Alternativamente, podrıamos haber tomado la solucion x2 =
„
2
314
3
«
. Los resultados finales
son los mismos, pero este camino tomarıa una iteracion mas.
164 CAPITULO 9. METODO DE DANTZIG-WOLFE
Entonces:
P 21 =
(
06
)
y λ12 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
y(1,2) = B−1M (1,2) = B−1
A01P21
10
= I
[
1 1]
(
06
)
10
=
6
1
0
Variable saliente:
Min
{
8
6,1
1, ·
}
= 1
Ası, p = 2 y λ11 sale de la base.
Nueva Base:
Matriz de pivote.
P2 =
[η2]
100
6−1110−1
001
=
1 −6 00 1 00 0 1
Ası:
B−1+ = P2B
−1 =
1 −6 00 1 00 0 1
I =
1 −6 00 1 00 0 1
y los datos para la nueva iteracion son:
B = {s, λ12, λ21} y B−1 =
1 −6 00 1 00 0 1
•Segunda iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
1 −6 00 1 00 0 1
811
=
211
165
Segundo paso.
Costos de las variables basicas en el maestro, PTB
P12 = cT1 P 2
1 =[
−1 −3]
(
06
)
= −18 ⇒ PTB =
[
0 −18 0]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
0 −18 0]
1 −6 00 1 00 0 1
=[
0 −18 0]
de donde:πT =
[
πT0 αT
]
=[
0 −18 0]
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 −3]
−[
0] [
1 1]
)
(
x1
x2
)
− (−18)
x ∈ S1
⇒
P) Min −x1 −3x2+18
x1 +x2 ≤6
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
06
)
, v(S1) = 0 ≥ 0
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
1 −1]
−[
0] [
1 1]
)
(
x3
x4
)
− 0
x ∈ S2
⇒
P) Min x3 −x4
x3 +2x4≤10
−x3 +x4 ≤4
x3, x4 ≥0
166 CAPITULO 9. METODO DE DANTZIG-WOLFE
Graficamente, tenemos2:
x2 =
(
04
)
, v(S2) = −4 6≥ 0
Entonces:
P 22 =
(
04
)
y λ22 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
y(2,2) = B−1M (2,2) = B−1
A02P22
01
=
1 −6 00 1 00 0 1
[
1 1]
(
04
)
01
=
4
01
Variable saliente:
Min
{
2
4, ·,
1
1
}
=1
2
Ası, p = 1 y s sale de la base.
Nueva Base:
Matriz de pivote.
P1 =
[η1]
140−41−4
0 01 00 1
=
1/4 0 00 1 0
−1/4 0 1
Ası:
B−1+ = P1B
−1 =
1/4 0 00 1 0
−1/4 0 1
1 −6 00 1 00 0 1
=
1/4 −3/2 00 1 0
−1/4 3/2 1
y los datos para la nueva iteracion son:
B = {λ22, λ12, λ21} y B−1 =
1/4 −3/2 00 1 0
−1/4 3/2 1
2Notese que este problema satelite no cambia con respecto a la iteracion anterior. Ası,
todavıa podrıamos tomar la solucion x2 =
„
2
314
3
«
.
167
•Tercera iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
1/4 −3/2 00 1 0
−1/4 3/2 1
811
=
1/21
1/2
Segundo paso.
Costos de las variables basicas en el maestro, PTB
P22 = cT2 P 2
2 =[
1 −1]
(
04
)
= −4 ⇒ PTB =
[
−4 −18 0]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
−4 −18 0]
1/4 −3/2 00 1 0
−1/4 3/2 1
=[
−1 −12 0]
de donde:
πT =[
πT0 αT
]
=[
−1 −12 0]
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 −3]
−[
−1] [
1 1]
)
(
x1
x2
)
− (−12)
x ∈ S1
⇒
P) Min −2x2+12
x1 +x2 ≤6
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
06
)
, v(S1) = 0 ≥ 0
168 CAPITULO 9. METODO DE DANTZIG-WOLFE
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
1 −1]
−[
−1] [
1 1]
)
(
x3
x4
)
− 0
x ∈ S2
⇒
P) Min 2x3
x3 +2x4≤10
−x3 +x4 ≤4
x3, x4 ≥0
Graficamente, tenemos3:
x2 =
(
04
)
, v(S2) = 0 ≥ 0
Faltarıa los costos reducidos de la holgura (recordar que esta esta fuera de labase):
rTs = −(−1)(1) = 1 ≥ 0
Fin, la solucion encontrada es optima. Concretamente:
(
x1
x2
)
= λ12P21 = 1
[
06
]
=
[
06
]
(
x3
x4
)
= λ21P12 + λ22P
22 =
1
2
[
00
]
+1
2
[
04
]
=
[
02
]
(iii) El Metodo de Dantzig-Wolfe permite aprovechar los problemas estructu-rados, descomponiendo el problema en varios problemas de menor dimension yfacil resolucion, llevando una Matriz de Base del problema maestro de menordimension tambien. En el caso particular de este problema, el metodo lleva unaMatriz de Base de dimension 3 × 3 en vez de 4 × 4 y los problemas satelites sepueden resolver facilmente de forma grafica. En particular, el primer satelite esun Problema de la Mochila (Knapsack Problem).
3De hecho, cualquier solucion de la forma x =
„
0y
«
con 0 ≤ y ≤ 4, es optima para S2).
169
Ejercicio 9.2 (†)
Considere el problema lineal:
P) Min −x1
x1 +2x2≤4
x1 +x2 ≥1
x1, x2 ≥0
(i) (1 punto) Muestre que P) admite solucion optima.
(ii) (1 punto) Reformule P) bajo el formato equivalente de Dantzig-Wolfe,de tal modo de explotar la estructura de mochila subyacente, a nivel delproblema satelite. En este caso, observe que el poliedro satelite correspon-diente, es claramente acotado.
(iii) (4 puntos) Aplique finalmente el Metodo de Dantzig-Wolfe, con Dos Fases,a la resolucion del modelo equivalente resultante en (ii)
Solucion
(i) Tenemos que (x1, x2) = (1, 1) ∈ P es solucion de P). Luego, el dominio esno vacıo (P) 6= φ)
Por otro lado, de las restricciones:
x1 + 2x2 ≤ 4x1 ≥ 0x2 ≥ 0
⇒
{
0 ≤ x1 ≤ 40 ≤ x2 ≤ 2
Luego el dominio es acotado.
Ademas, las restricciones estan definidas por restricciones lineales de de-sigualdad. Luego el dominio es cerrado. Finalmente, la funcion objetivo es lineal,luego continua. Ası, por el Teorema de Bolzano Weierstrass, P) admite solucionoptima.
(ii) Formato de Dantzig-Wolfe:
P) Min −x1
x1 +x2 −x3=1
x1 +2x2 ≤4
x1, x2, x3≥0
donde la primera restriccion es de coordinacion (m0 = 1) y tenemos un satelite
170 CAPITULO 9. METODO DE DANTZIG-WOLFE
(N = 1), el cual esta formado por las restricciones:
x1 +2x2≤4
x1, x2 ≥0
A continuacion, se muestra el grafico del satelite, el cual resulta ser un Pro-blema de la Mochila.
•Grafico Satelite
0 1 2 3 40
1
2
x2
x1
(
00
) (
40
)
(
02
)
(iii) Como el punto ~0 no pertenece a P), se necesita hacer dos fases. La res-triccion violada es la de coordinacion, sobre la cual agregamos una variableartificial. El problema en formato Dantzig-Wolfe para la Fase I es:
Fase I
P) Min x4
x1 +x2 −x3+x4= 1
x1 +2x2 ≤ 4
x1, x2, x3 ≥ 0
Los datos para comenzar la Fase I del Metodo de Dantzig-Wolfe con esta con-figuracion (satelite como Problema de la Mochila) son:
A01 =[
1 1]
, cT1 =
[
0 0]
y b =
(
11
)
y la solucion factible inicial para el problema de la Fase I es:
P 11 =
(
00
)
, B = {x4, λ11} y B−1 = I
•Primera iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b = I
(
11
)
=
(
11
)
171
Segundo paso.
Costos de las variables basicas en el maestro, PTB
Px4 = 1
P11 = cT1 P 1
1 =[
0 0]
(
00
)
= 0
⇒ PTB =
[
1 0]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
1 0]
I =[
1 0]
de donde:πT =
[
πT0 αT
]
=[
1 0]
Problema Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
0 0]
−[
1] [
1 1]
)
(
x1
x2
)
− 0
x ∈ S1
⇒
P) Min −x1 −x2
x1 +2x2≤4
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
40
)
, v(S1) = −4 6≥ 0
Entonces:
P 21 =
(
40
)
y λ12 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
y(1,2) = B−1M (1,2) = B−1
[
A01P21
1
]
= I
[
1 1]
(
40
)
1
=
(
4
1
)
Variable saliente:
Min
{
1
4,1
1
}
=1
4
172 CAPITULO 9. METODO DE DANTZIG-WOLFE
Ası, p = 1, x4 sale de la base y termina la Fase I.
Nueva Base:
Matriz de pivote.
P1 =
(
[η1][
141−4
]
01
)
=
[
1/4 0−1/4 1
]
Ası:
B−1+ = P1B
−1 =
[
1/4 0−1/4 1
]
I =
[
1/4 0−1/4 1
]
y los datos para la Fase II son:
B = {λ12, λ11} y B−1 =
[
1/4 0−1/4 1
]
Fase II
Tenıamos el problema en formato de Dantzig-Wolfe:
P) Min −x1
x1 +x2 −x3=1
x1 +2x2 ≤4
x1, x2, x3≥0
Lo unico que cambia en la Fase II es el vector de costos:
cT1 =
[
−1 0]
•Primera iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
[
1/4 0−1/4 1
](
11
)
=
(
1/43/4
)
Segundo paso.
Costos de las variables basicas en el maestro, PTB
4:
P12 = cT1 P 2
1 =[
−1 0]
(
40
)
= −4
P11 = cT1 P 1
1 =[
−1 0]
(
00
)
= 0
⇒ PTB =
[
−4 0]
4Notar que, P11 no cambia de valor con respecto a la ultima iteracion de la Fase I simple-mente porque P11 = ~0. Esto es mera coincidencia y en general, al pasar a la Fase II, se debecalcular nuevamente el valor de pT
B.
173
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
−4 0]
[
1/4 0−1/4 1
]
=[
−1 0]
de donde:πT =
[
πT0 αT
]
=[
−1 0]
Problema Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 0]
−[
−1] [
1 1]
)
(
x1
x2
)
− 0
x ∈ S1
⇒
P) Min x2
x1 +2x2≤4
x1, x2 ≥0
Graficamente, tenemos5:
x1 =
(
40
)
, v(S1) = 0 ≥ 0
Faltarıa el costo reducido de la variable de exceso6 (recordar que esta ultimaesta fuera de la base):
rTx3
= −(−1) · (−1) = −1 6≥ 0
Entonces x3 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
yx3 = B−1Mx3 = B−1
[
−10
]
=
[
1/4 0−1/4 1
] [
−10
]
=
( −14
14
)
Variable saliente:
Min
{
·,3/4
1/4
}
= 3
5De hecho, cualquier solucion de la forma x =
„
y0
«
con 0 ≤ y ≤ 4, es optima para S1).
6Notese que, como x3 es variable de exceso, su costo reducido es igual al valor de π0.
174 CAPITULO 9. METODO DE DANTZIG-WOLFE
Ası, p = 2 y λ11 sale de la base.
Nueva Base:
Matriz de pivote.
P2 =
(
[η2]
10
[
−1/4−1/4
11/4
])
=
[
1 10 4
]
Ası:
B−1+ = P2B
−1 =
[
1 10 4
] [
1/4 0−1/4 1
]
=
[
0 1−1 4
]
y los datos para la nueva iteracion son:
B = {λ12, x3} y B−1 =
[
0 1−1 4
]
•Segunda iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
[
0 1−1 4
](
11
)
=
(
13
)
Segundo paso.
Costos de las variables basicas en el maestro, PTB :
Ps = 0 ⇒ PTB =
[
−4 0]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
−4 0]
[
0 1−1 4
]
=[
0 −4]
de donde:
πT =[
πT0 αT
]
=[
0 −4]
175
Problema Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 0]
−[
0] [
1 1]
)
(
x1
x2
)
− (−4)
x ∈ S1
⇒
P) Min −x1 +4
x1 +2x2≤4
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
40
)
, v(S1) = 0 ≥ 0
Fin, la solucion encontrada es optima. Concretamente:
(
x1
x2
)
= λ12P21 = 1
[
40
]
=
[
40
]
Nota: A diferencia de lo que sucede generalmente, la restriccion de coordi-nacion no es activa en el optimo. Si esto ocurriera en un problema con mas deun satelite, implicarıa que la restriccion se podrıa haber eliminado y el problemaserıa separable.
176 CAPITULO 9. METODO DE DANTZIG-WOLFE
Ejercicio 9.3 (†)
Considere el problema lineal de minimizacion :
P) Min −x1 −2x2+3x3+x4
x1 +2x2+2x3+x4≥ 40
x1 +x2 ≤ 2
−x1 +2x2 ≤ 2
x3 +x4 ≥ 6
x1, x2, x3, x4 ≥ 0
(i) (1 Pto.) Muestre, antes de resolver, que el problema admite solucionoptima.
(ii) (4 Ptos.) Calcule una solucion optima mediante el Metodo de Descompo-sicion de Dantzig y Wolfe, llevando la matriz Inversa de Base del ProblemaMaestro, en forma explıcita.
(iii) (1 Pto.) Explicite la solucion optima del problema original encontrada.
Solucion
(i) Se tiene que (x1, x2, x3, x4) = (0, 0, 0, 40) ∈ P . Luego:
P 6= φ (9.1)
De la segunda restriccion y las de no-negatividad, podemos calcular cotassuperiores para las variables 1 y 2. Concretamente:
x1 + x2 ≤ 2x1 ≥ 0x2 ≥ 0
⇒
{
x1 ≤ 2x2 ≤ 2
}
⇒
{
−x1 ≥ −2
−2x2 ≥ −4
Esto, junto con las restricciones de no-negatividad de las variables 3 y 4, nosentrega lo deseado:
−x1 ≥ −2
−2x2 ≥ −4
x3 ≥ 0
x4 ≥ 0
⇒ −x1 − 2x2 + x3 + x4 ≥ −6
Ası:cT x ≥ cte. (9.2)
177
Luego, (9.1) y (9.2) cumplen con las hipotesis del Teorema de Existencia de la
Programacion Lineal y, por lo tanto, P) admite solucion optima.
(ii) Formato de Dantzig-Wolfe:
P) Min −x1 −2x2+3x3+x4
x1 +2x2+2x3+x4 −x5= 40
x1 +x2 ≤ 2
−x1 +2x2 ≤ 2
x3 +x4 ≥ 6
x1, x2, x3, x4, x5 ≥ 0
donde la primera restriccion es de coordinacion (m0 = 1) y tenemos 2 satelites(N = 2), los cuales estan formados por las restricciones
x1 +x2 ≤ 2
−x1 +2x2≤ 2
x1, x2 ≥ 0
para el primer satelite y
x3+x4 ≥ 6
x3, x4 ≥ 0
para el segundo. Este ultimo satelite resulta ser no-acotado.
A continuacion, se muestra los graficos de ambos satelites.
•Grafico Satelite 1
0 1 20
1
2
x2
x1
(
00
)
(
01
)
(
20
)
(
2343
)
178 CAPITULO 9. METODO DE DANTZIG-WOLFE
•Grafico Satelite 2
0 1 2 3 4 5 6 70
1
2
3
4
5
6
7
x4
x3
(
00
) (
60
)
(
06
)
Como el punto ~0 no pertenece a P), se necesita hacer dos fases. Se viola larestriccion de coordinacion y el segundo satelite. Ası, necesitaremos dos variablesartificiales.
Los datos para comenzar la Fase I del Metodo de Dantzig-Wolfe con estaconfiguracion son:
A01 =[
1 2]
y cT1 =
[
0 0]
para el primer satelite y
A02 =[
2 1]
y cT2 =
[
0 0]
para el segundo. El nuevo lado derecho queda:
b =
4011
y la solucion factible inicial para el problema de la Fase I es:
P 11 =
(
00
)
, B = {η1, λ11, η2} y B−1 = I
donde η1 y η2 son las variables artificiales de la restriccion de coordinacion y elsegundo satelite, respectivamente.
•Primera iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b = I
4011
=
4011
179
Segundo paso.
Costos de las variables basicas en el maestro, PTB
Pη1 = 1
Pλ11 = cT1 P 1
1 =[
0 0]
(
00
)
= 0
Pη2 = 1
⇒ PTB =
[
1 0 1]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
1 0 1]
I =[
1 0 1]
de donde:πT =
[
πT0 αT
]
=[
1 0 1]
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
0 0]
−[
1] [
1 2]
)
(
x1
x2
)
− 0
x ∈ S1
⇒
P) Min −x1 −2x2
x1 +x2 ≤2
−x1 +2x2≤2
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
2343
)
, v(S1) = −10
36≥ 0
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
0 0]
−[
1] [
2 1]
)
(
x3
x4
)
− 1
x ∈ S2
⇒
P) Min −2x3−x4−1
x3 +x4≥6
x3, x4≥0
180 CAPITULO 9. METODO DE DANTZIG-WOLFE
Graficamente, tenemos que el problema no tiene solucion optima. Para ladireccion asintotica7:
d2 =
(
01
)
, v(S2) = −∞ 6≥ 0
Entonces:
C12 =
(
01
)
y µ21 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
yµ21 = B−1Mµ21 = B−1
A02C12
00
= I
[
2 1]
(
01
)
00
=
1
00
Variable saliente:
Min
{
40
1, ·, ·
}
= 40
Ası, p = 1 y η1 sale de la base.
Nueva Base:
Matriz de pivote.
P1 =
[η1]
110−10−1
0 01 00 1
=
1 0 00 1 00 0 1
Ası:
B−1+ = P1B
−1 =
1 0 00 1 00 0 1
I =
1 0 00 1 00 0 1
y los datos para la nueva iteracion son:
B = {µ21, λ11, η2} y B−1 =
1 0 00 1 00 0 1
7Alternativamente, podrıamos haber tomado la otra direccion asintotica d2 =
„
10
«
. Los
resultados finales son los mismos.
181
•Segunda iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
1 0 00 1 00 0 1
4011
=
4011
Segundo paso.
Costos de las variables basicas en el maestro, PTB
Pµ21 = cT2 C1
2 =[
0 0]
(
01
)
= 0 ⇒ PTB =
[
0 0 1]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
0 0 1]
1 0 00 1 00 0 1
=[
0 0 1]
de donde:
πT =[
πT0 αT
]
=[
0 0 1]
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
0 0]
−[
0] [
1 2]
)
(
x1
x2
)
− 0
x ∈ S1
⇒
P) Min 0
x1 +x2 ≤2
−x1 +2x2≤2
x1, x2 ≥0
Claramente, tenemos:
v(S1) = 0 ≥ 0
182 CAPITULO 9. METODO DE DANTZIG-WOLFE
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
0 0]
−[
0] [
2 1]
)
(
x3
x4
)
− 1
x ∈ S2
⇒
P) Min −1
x3 +x4≥6
x3, x4≥0
Claramente, tenemos:
v(S1) = −1 6≥ 0
Entonces8:
P 12 =
(
06
)
y λ21 entra a la base.
Tercer paso: Calculo de la columna entrante en el Tableaux
yλ21 = B−1Mλ21 = B−1
A02P12
01
=
1 0 00 1 00 0 1
[
2 1]
(
06
)
01
=
60
1
Variable saliente:
Min
{
40
6, ·,
1
1
}
= 1
Ası, p = 3, η2 sale de la base y termina la Fase I.
Nueva Base:
Matriz de pivote.
P3 =
[η3]
1 00 10 0
6−10−111
=
1 0 −60 1 00 0 1
8Se podrıa tomar cualquier punto del dominio de este satelite, el punto escogido es arbi-trario.
183
Ası:
B−1+ = P3B
−1 =
1 0 −60 1 00 0 1
1 0 00 1 00 0 1
=
1 0 −60 1 00 0 1
y los datos para la Fase II son:
B = {µ21, λ11, λ21} y B−1 =
1 0 −60 1 00 0 1
Fase II
Lo unico que cambia en la Fase II son los vectores de costos:
cT1 =
[
−1 −2]
y cT2 =
[
3 1]
•Primera iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
1 0 −60 1 00 0 1
4011
=
3411
Segundo paso.
Costos de las variables basicas en el maestro, PTB :
Pµ21 = cT2 C1
2 =[
3 1]
(
01
)
= 1
Pλ11 = cT1 P 1
1 =[
−1 −2]
(
00
)
= 0
Pλ21 = cT2 P 1
2 =[
3 1]
(
06
)
= 6
⇒ PTB =
[
1 0 6]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
1 0 6]
1 0 −60 1 00 0 1
=[
1 0 0]
de donde:
πT =[
πT0 αT
]
=[
1 0 0]
184 CAPITULO 9. METODO DE DANTZIG-WOLFE
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 −2]
−[
1] [
1 2]
)
(
x1
x2
)
− 0
x ∈ S1
⇒
P) Min −2x1−4x2
x1 +x2 ≤2
−x1 +2x2≤2
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
2343
)
, v(S1) = −10
36≥ 0
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
3 1]
−[
1] [
2 1]
)
(
x3
x4
)
− 0
x ∈ S2
⇒
P) Min x3
x3 +x4≥6
x3, x4≥0
Claramente, tenemos:
v(S1) = 0 ≥ 0
Entonces:
P 21 =
(
2/34/3
)
y λ12 entra a la base.
185
Tercer paso: Calculo de la columna entrante en el Tableaux
yλ12 = B−1Mλ12 = B−1
A01P21
10
=
1 0 −60 1 00 0 1
[
1 2]
(
2/34/3
)
10
=
10/3
1
0
Variable saliente:
Min
{
34
10/3,1
1, ·
}
= 1
Ası, p = 2 y λ11 sale de la base.
Nueva Base:
Matriz de pivote.
P2 =
[η2]
100
10/3−1110−1
001
=
1 −10/3 00 1 00 0 1
Ası:
B−1+ = P2B
−1 =
1 −10/3 00 1 00 0 1
1 0 −60 1 00 0 1
=
1 −10/3 −60 1 00 0 1
y los datos para la nueva iteracion son:
B = {µ21, λ12, λ21} y B−1 =
1 −10/3 −60 1 00 0 1
•Segunda iteracion maestra
Primer paso: Calculo del lado derecho del Tableaux.
y0 = B−1b =
1 −10/3 −60 1 00 0 1
4011
=
92/311
186 CAPITULO 9. METODO DE DANTZIG-WOLFE
Segundo paso.
Costos de las variables basicas en el maestro, PTB :
Pλ12 = cT1 P 2
1 =[
−1 −2]
(
2/34/3
)
= −10/3 ⇒ PTB =
[
1 −10/3 6]
Calculo del vector de multiplicadores π.
πT = PTB B−1 =
[
1 −10/3 6]
1 −10/3 −60 1 00 0 1
=[
1 −20/3 0]
de donde:πT =
[
πT0 αT
]
=[
1 −20/3 0]
Problemas Satelite
Primer Satelite
S1) Min (cT1 − πT
0 A01)~x1 − α1
x ∈ S1
⇒
S1) Min ([
−1 −2]
−[
1] [
1 2]
)
(
x1
x2
)
− (−20/3)
x ∈ S1
⇒
P) Min −2x1−4x2+20
3x1 +x2 ≤2
−x1 +2x2≤2
x1, x2 ≥0
Graficamente, tenemos:
x1 =
(
2343
)
, v(S1) = 0 ≥ 0
Segundo Satelite
S2) Min (cT2 − πT
0 A02)~x2 − α2
x ∈ S2
⇒
S2) Min ([
3 1]
−[
1] [
2 1]
)
(
x3
x4
)
− 0
x ∈ S2
⇒
P) Min x3
x3 +x4≥6
x3, x4≥0
187
Claramente, tenemos:v(S1) = 0 ≥ 0
Faltarıa el costo reducido de la variable de exceso (recordar que esta ultimaesta fuera de la base):
rTs = −(1) · (−1) = 1 ≥ 0
Fin, la solucion encontrada es optima.
(iii) Tenemos:(
x1
x2
)
= λ12P21 = 1
[
2/34/3
]
=
[
2/34/3
]
(
x3
x4
)
= µ21C12 + λ21P
12 =
92
3
[
01
]
+ 1
[
06
]
=
[
0110/3
]
Ası, la solucion del problema original queda:
x =
x1
x2
x3
x4
=
2/34/30
110/3
y el valor optimo del problema es:
v(P) = −1 ·2
3+ −2 ·
4
3+ 3 · 0 + 1 ·
110
3=
100
3
188 CAPITULO 9. METODO DE DANTZIG-WOLFE
Capıtulo 10
Dualidad en Programacion
Lineal
Ejercicio 10.1 (†)
Considere el siguiente problema lineal de minimizacion:
P) Min 2x1+15x2+5x3+6x4
x1 +6x2 +3x3+x4 ≥2
−2x1+5x2 −x3 +3x4≤− 3
x1, x2, x3, x4 ≥0
(i) (2 Ptos.) Establezca el problema dual D), de P).
(ii) (0.5 Pto.) Antes de resolver, muestre que tanto P) como su dual D) ad-miten solucion optima. Para ello, aplique el Teorema de Dualidad Debil,conjuntamente con el Teorema General de Existencia de la ProgramacionLineal. En particular, establezca un Intervalo de Confianza para los valoresoptimos de P) y D).
(iii) (0.5 Pto.) Teniendo en cuenta ii), muestre que los valores optimos deP) y D) coinciden. Fundamente su respuesta en base a los resultadosfundamentales del curso.
(iv) (1 Pto.) Resuelva, con ayuda grafica, el problema dual D) y compruebeque el valor optimo de P) esta dentro del intervalo determinado en ii).
(v) (2 Ptos.) Conocida la solucion optima del Problema Dual D), obtenga lasolucion optima del primal a traves de las condiciones de optimalidad de
189
190 CAPITULO 10. DUALIDAD EN PROGRAMACION LINEAL
Karush-Kuhn-Tucker para le problema P). Para tal efecto, recuerde quetoda solucion optima del Dual provee, salvo un eventual cambio de signo,un vector de multiplicadores optimos para P).
Solucion
(i) Antes de establecer le problema dual, multiplicaremos la primera restriccionpor -1, de modo de tener un formato mas comodo para expresar las condicionesde Karush-Kuhn-Tucker (K.K.T.):
P) Min 2x1+15x2+5x3+6x4
−x1 −6x2 −3x3−x4 ≤− 2
−2x1+5x2 −x3 +3x4≤− 3
x1, x2, x3, x4 ≥0
Ahora establecemos el Dual Equivalente D):
D) Max −2u1−3u2
−u1 −2u2≤2
−6u1+5u2≤15
−3u1−u2 ≤5
−u1 +3u2≤6
u1, u2 ≤0
Cabe notar que las variables u representan el inverso aditivo de las variablesduales del problema P). Es decir, µ = −u, donde µ representa las variablesduales de P).
(ii) El Teorema de Dualidad Debil nos indica que, si tenemos una solucionfactible x del Problema Primal P) y una solucion factible µ del Problema DualD), entonces:
−µT b ≤ cT x,
y en terminos del Dual Equivalente (con variables u en vez de µ):
uT b ≤ cT x. (10.1)
Como estos x y u pueden ser los valores optimos x y u, tenemos:
uT b ≤ cT x.
Logicamente uT b ≤ uT b = v(D) y v(P) = cT x ≤ cT x, de lo que se tiene:
uT b ≤ v(D) ≤ v(P) ≤ cT x.
191
Por otro lado, tenemos que:
x =
2000
∈ P) y u =
(
00
)
∈ D)
Reemplazando en la expresion anterior obtenemos:
0 ≤ v(D) ≤ v(P) ≤ 4
De donde se obtiene los intervalos de confianza:
0 ≤ v(P) ≤ 4
0 ≤ v(D) ≤ 4
Para demostrar que ambos tienen solucion optima, utilizamos la expresion(10.1) y el Teorema de Existencia de la Programacion Lineal :
x ∈ P) ⇒ P 6= φ
u ∈ D) ⇒ 0 ≤ cT x
}
⇒ P) admite solucion optima.
Analogamente para D):
x ∈ P) ⇒ uT b ≤ 4
u ∈ D) ⇒ D 6= φ
}
⇒ D) admite solucion optima.
Logicamente, si el Problema Dual admite solucion optima, el Problema DualEquivalente tambien.
(iii) El Teorema de Dualidad Fuerte nos indica que si un problema tiene solucionoptima, su Dual tambien y ambos valores optimos coinciden. Del apartado (ii)tenemos que P) y D) admiten soluciones optimas, luego, sus valores optimoscoinciden.
(iv) Para el problema D), graficamente:
192 CAPITULO 10. DUALIDAD EN PROGRAMACION LINEAL
−1−2−3−4−5−6
1
2
3
−1
−2
−3
−4
−5
u2
u1
−u1 − 2u2 − 2 = 0
−6u1 + 5u2 − 15 = 0
−3u1 − u2 − 5 = 0
−u1 + 3u2 − 6 = 0
u =
(
−8/5−1/5
)
c = (−2,−3)
Ası, obtenemos:
u =
(
−8/5−1/5
)
⇒ v(D) = 19/5 = v(P),
que pertenece al intervalo [0, 4].
(v) Del apartado (iv) tenemos:
u =
(
−8/5−1/5
)
⇒ µ =
(
8/51/5
)
Expresando el Primal de esta forma:
P) Min 2x1+15x2+5x3+6x4
−x1 −6x2 −3x3−x4 +2≤ 0
−2x1+5x2 −x3 +3x4+3≤ 0
x1, x2, x3, x4 ≥0
193
Podemos formar la siguiente funcion lagrangeana:
L(x, µ) = 2x1 + 15x2 + 5x3 + 6x4
+ µ1(−x1 − 6x2 − 3x3 − x4 + 2)
+ µ2(−2x1 + 5x2 − x3 + 3x4 + 3)
De las condiciones ∂L∂xi
≥ 0 tenemos las siguientes condiciones (claramenteredundantes):
∂L
∂x1≥ 0 ⇒ 2 − µ1 − 2µ2 ≥ 0 ⇒ 0 ≥ 0
∂L
∂x2≥ 0 ⇒ 15 − 6µ1 + 5µ2 ≥ 0 ⇒ 32/5 ≥ 0
∂L
∂x3≥ 0 ⇒ 5 − 3µ1 − µ2 ≥ 0 ⇒ 0 ≥ 0
∂L
∂x4≥ 0 ⇒ 6 − µ1 + 3µ2 ≥ 0 ⇒ 5 ≥ 0
De las condiciones xi∂L∂xi
= 0 tenemos:
x1∂L
∂x1= 0 ⇒ x1(2 − µ1 − 2µ2) = 0 ⇒ x1 · 0 = 0
x2∂L
∂x2= 0 ⇒ x2(15 − 6µ1 + 5µ2) = 0 ⇒ x2 · 32/5 = 0 ⇒ x2 = 0
x3∂L
∂x3= 0 ⇒ x3(5 − 3µ1 − µ2) = 0 ⇒ x3 · 0 = 0
x4∂L
∂x4= 0 ⇒ x4(6 − µ1 + 3µ2) = 0 ⇒ x4 · 5 = 0 ⇒ x4 = 0
De las condiciones µj · gj(x) = 0 tenemos:
µ1 · g1(x) = 0 ⇒ µ1(−x1 − 6x2 − 3x3 − x4 + 2) = 0
µj · g2(x) = 0 ⇒ µ2(−2x1 + 5x2 − x3 + 3x4 + 3) = 0
como µ1, µ2 6= 0 y x2, x4 = 0, tenemos el siguiente sistema:
−x1 − 3x3 + 2 = 0
−2x1 − x3 + 3 = 0
de lo que se obtiene que x1 = 7/5 y x3 = 1/5.
Finalmente:
x =
7/50
1/50
⇒ v(P) = 19/5 = v(D).
194 CAPITULO 10. DUALIDAD EN PROGRAMACION LINEAL
Capıtulo 11
Programacion Entera y
Metodo de Branch&Bound
Ejercicio 11.1 (†)
Considere el siguiente problema lineal de minimizacion en variables enteras:
P) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1, x2, ≥0 (enteras)
(i) (1 Pto.) Muestre que este problema P) admite, al menos, una solucionoptima.
(ii) (3 Ptos.) Aplique el Metodo de Branch & Bound a la determinacion deuna solucion optima de P). Para ello, considere (x1, x2) = (0, 0) como lamejor solucion entera factible inicial y explore los distintos nodos del arbolde Branch & Bound, nivel por nivel, resolviendo los problemas relajadoscorrespondientes de manera grafica, pero exacta. Dibuje el arbol de Branch& Bound resultante, indicando sobre este toda la informacion relevante,incluidos los valores sucesivos del incumbente.
(iii) (3 Pto.) Teniendo en cuenta el arbol final en ii), analice si es unica o no,la solucion optima de P). Si fuera el caso, determine todas las solucionesoptimas de P).
195
196 CAPITULO 11. PROGRAMACION ENTERA
Solucion
(i) Se tiene que el poliedro P dado por las restricciones
0 ≤ x1 ≤ 8
0 ≤ x2 ≤ 4
es acotado. Como D ⊆ P , donde D es el dominio de restriccion del problemaP), resulta que D es acotado.
Por otro lado, el punto (x1, x2) = (0, 0) pertenece a D, luego D es no vacıo.
Como D es acotado y no vacıo, tiene un numero finito de soluciones enterasfactibles. Ademas, como la funcion objetivo es continua, P) admite solucionoptima.
(ii) El incumbente inicial esta dado por el valor de la funcion objetivo, evaluadasobre la solucion entera factible inicial, entregada en el enunciado. Concreta-mente:
x0 =
(
00
)
⇒ cT x0 = 0 ⇒ f = 0 (incumbente inicial)
Problema 0
Debemos resolver el problema relajado, que resulta ser un Problema de laMochila con cotas.
P0) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
28/54
)
−kc = (1, 2)
Condiciones
197
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −136 < f = 0, R:Si
Luego debemos ramificar el nodo P0:
P0
P01 P02
x1 ≤ 5 x1 ≥ 6
Problema 01
El problema P01) es:
P01) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≤5
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
54
)
−kc = (1, 2)
Condiciones
¿es infactible? R: No
198 CAPITULO 11. PROGRAMACION ENTERA
¿es solucion entera? R: Si
¿su valor optimo es mejor que el incumbente? cT x = −130 < f = 0, R:Si
Luego, el nuevo incumbente es f = −130 y el nodo P01 se deja de ramificar.
Problema 02
El problema P02) es:
P02) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
615/4
)
−kc = (1, 2)
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −135 < f = −130,R: Si
Luego debemos ramificar el nodo P02:
199
P02
P021 P022
x2 ≤ 3 x2 ≥ 4
Problema 021
El problema P021) es:
P021) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x2 ≤3
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
36/53
)
−kc = (1, 2)
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −132 < f = −130,R: Si
Luego, el nodo P021 se debe ramificar.
200 CAPITULO 11. PROGRAMACION ENTERA
Problema 022
El problema P022) es:
P022) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x2 ≥4
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
−kc = (1, 2)
Condiciones
¿es infactible? R: Si
Luego, el nodo P022 se deja de ramificar.
Ramificamos el nodo P021:
P021
P0211 P0212
x1 ≤ 7 x1 ≥ 8
201
Problema 0211
El problema P0211) es:
P0211) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x2 ≤3
x1 ≤7
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
73
)
−kc = (1, 2)
Condiciones
¿es infactible? R: No
¿es solucion entera? R: Si
¿su valor optimo es mejor que el incumbente? cT x = −130 6< f = −130,R: No
Luego, el nodo P0211 se deja de ramificar.
202 CAPITULO 11. PROGRAMACION ENTERA
Problema 0212
El problema P0212) es:
P0212) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x2 ≤3
x1 ≥8
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
85/2
)
−kc = (1, 2)
Condiciones
¿es infactible? R: No
¿es solucion entera? R:No
¿su valor optimo es mejor que el incumbente? cT x = −130 6< f = −130,R: No
Luego, el nodo P0212 se deja de ramificar (poda).
Como no quedan mas nodos que ramificar, la solucion encontrada es optima:
x =
(
54
)
, v(P) = f = −130
El arbol de Branch & Bound queda:
203
P0f = 0
v(P0) = −136
P01f = 0
v(P01) = −130P02
f = −130
v(P02) = −135
P021f = −130
v(P021) = −132P022
f = −130
v(P022) = ∞
P0211f = −130
v(P0211) = −130P0212
f = −130
v(P0212) = −130
x1 ≤ 5 x1 ≥ 6
x2 ≤ 3 x2 ≥ 4
x1 ≤ 7 x1 ≥ 8
(iii) Del arbol anterior, se puede notar que, hasta el momento, hay dos solucio-nes enteras que evaluadas en la funcion objetivo, tienen el mismo valor que elincumbente optimo:
x =
(
54
)
, x =
(
73
)
Para determinar si existe alguna otra, debemos ramificar el arbol a cabalidad,cambiando la condicion ¿su valor optimo es mejor que el incumbente?, por lacondicion ¿su valor optimo es mejor o igual que el incumbente? Si revisamos lascondiciones sobre los nodos que no se ramificaron, podemos notar que el nodoP0212 se podrıa haber continuado ramificando. Concretamente:
Condiciones
¿es infactible? R: No
¿es solucion entera? R: Si
¿su valor optimo es mejor o igual que el incumbente? cT x = −130 ≤ f =−130, R: Si
Luego, el nodo P0211 se debe ramificar.
204 CAPITULO 11. PROGRAMACION ENTERA
Problema 02121
El problema P02121) es:
P02121) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x2 ≤3
x1 ≥8
x2 ≤2
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
x =
(
82
)
−kc = (1, 2)
Condiciones
¿es infactible? R: No
¿es solucion entera? R:Si
¿su valor optimo es mejor o igual que el incumbente? cT x = −120 6≤ f =−130, R: No
Luego, el nodo P02121 se deja de ramificar.
205
Problema 02122
El problema P02122) es:
P02122) Min −10x1−20x2
5x1 +8x2 ≤60
x1 ≤8
x2 ≤4
x1 ≥6
x2 ≤3
x1 ≥8
x2 ≥3
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 10 11 120
1
2
3
4
5
6
7
x2
x1
−kc = (1, 2)
Condiciones
¿es infactible? R: Si
Luego, el nodo P02122 se deja de ramificar.
Claramente, la ramificacion no nos ha entregado otra solucion entera optima,luego, las unicas soluciones optimas de P) son:
x =
(
54
)
, x =
(
73
)
206 CAPITULO 11. PROGRAMACION ENTERA
Ejercicio 11.2 (†)
Considere el siguiente problema lineal de minimizacion en variables enteras:
P) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1, x2, ≥0 (enteras)
(i) (1 Pto.) Muestre que este problema P) admite, al menos, una solucionoptima.
(ii) (3 Ptos.) Aplique el Metodo de Branch & Bound a la determinacion deuna solucion optima de P). Para ello, considere (x1, x2) = (0, 0) como lamejor solucion entera factible inicial y explore los distintos nodos del arbolde Branch & Bound, nivel por nivel, resolviendo los problemas relajadoscorrespondientes de manera grafica, pero exacta. Dibuje el arbol de Branch& Bound resultante, indicando sobre este toda la informacion relevante,incluidos los valores sucesivos del incumbente.
(iii) (3 Pto.) Teniendo en cuenta el arbol final en ii), analice si es unica o no,la solucion optima de P). Si fuera el caso, determine todas las solucionesoptimas de P).
Solucion
(i) De la primera restriccion y las de no-negatividad, se tiene el siguiente poliedroP :
0 ≤ x1 ≤ 56/9
0 ≤ x2 ≤ 56/7
que es claramente acotado.
Como D ⊆ P , donde D es el dominio de restriccion del problema P), resultaque D es acotado.
Por otro lado, el punto (x1, x2) = (0, 0) pertenece a D, luego D es no vacıo.
Como D es acotado y no vacıo, tiene un numero finito de soluciones enterasfactibles. Luego, P) admite solucion optima.
(ii) El incumbente inicial esta dado por el valor de la funcion objetivo, evaluadasobre la solucion entera factible inicial, entregada en el enunciado. Concreta-mente:
x0 =
(
00
)
⇒ cT x0 = 0 ⇒ f = 0 (incumbente inicial)
207
Problema 0
Debemos resolver el problema relajado:
P0) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
x =
(
4, 8091, 816
)
−kc = (1, 94 )
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −355, 87 < f = 0,R: Si
Luego debemos ramificar el nodo P0:
P0
P01 P02
x1 ≤ 4 x1 ≥ 5
208 CAPITULO 11. PROGRAMACION ENTERA
Problema 01
El problema P01) es:
P01) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1 ≤4
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
x =
(
42, 1
)
−kc = (1, 94 )
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −349 < f = 0, R:Si
Luego debemos ramificar el nodo P01:
209
P01
P011 P012
x1 ≤ 2 x1 ≥ 3
Problema 02
El problema P02) es:
P02) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1 ≥5
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
x =
(
51, 571
)
−kc = (1, 94 )
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −341, 42 < f = 0,R: Si
210 CAPITULO 11. PROGRAMACION ENTERA
Luego debemos ramificar el nodo P02:
P02
P021 P022
x2 ≤ 1 x2 ≥ 2
Problema 011
El problema P011) es:
P011) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1 ≤4
x2 ≤2
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
x =
(
42
)
−kc = (1, 94 )
Condiciones
¿es infactible? R: No
211
¿es solucion entera? R: Si
¿su valor optimo es mejor que el incumbente? cT x = −340 < f = 0, R:Si
Luego, el nuevo incumbente es f = −340 y el nodo P011 se deja de ramificar.
Problema 012
El problema P012) es:
P012) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1 ≤4
x2 ≥3
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
x =
(
1, 4283
)
−kc = (1, 94 )
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −327, 142 6< f =−340, R: No
212 CAPITULO 11. PROGRAMACION ENTERA
Luego, el nodo P012 se deja de ramificar (poda).
Problema 021
El problema P021) es:
P021) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1 ≥5
x2 ≤1
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
x =
(
5, 4441
)
−kc = (1, 94 )
Condiciones
¿es infactible? R: No
¿es solucion entera? R: No
¿su valor optimo es mejor que el incumbente? cT x = −307, 777 < f = 0,R: No
Luego, el nodo P021 se deja de ramificar (poda).
213
Problema 022
El problema P022) es:
P022) Min −40x1−90x2
9x1 +7x2 ≤56
7x1 +20x2≤70
x1 ≥5
x2 ≥2
x1, x2, ≥0
Graficamente:
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
x2
x1
−kc = (1, 94 )
Condiciones
¿es infactible? R: Si
Luego, el nodo P022 se deja de ramificar.
Como no quedan mas nodos que ramificar, la solucion encontrada es optima:
x =
(
42
)
, v(P) = f = −130
El arbol de Branch & Bound queda:
214 CAPITULO 11. PROGRAMACION ENTERA
P0
f = 0
v(P0) = −355, 87
P01 f = 0
v(P01) = −349
P02f = 0
v(P02) = −341, 42
P011f = 0
v(P021) = −340 P012f = −340
v(P022) = −327, 14 P021f = −340
v(P021) = −307, 77 P022f = −340
v(P022) = ∞
x1 ≤ 4 x1 ≥ 5
x2 ≤ 2 x2 ≥ 3 x2 ≤ 1 x2 ≥ 2
(iii) Del arbol anterior, se puede notar que, hasta el momento, hay solamenteuna solucion entera que, evaluada en la funcion objetivo, tiene el mismo valorque el incumbente optimo:
x =
(
42
)
Para determinar si existe alguna otra, debemos ramificar el arbol a cabalidad,cambiando la condicion ¿su valor optimo es mejor que el incumbente?, por lacondicion ¿su valor optimo es mejor o igual que el incumbente? Si revisamos lascondiciones sobre los nodos que no se ramificaron, podemos notar que ningunnodo se podrıa haber continuado ramificando. Luego, la solucion optima esunica.