Program Ac I On Lineal
Program Ac I On Lineal
Índice general
1. INTRODUCCIÓN 1
1.1. Un problema de asignación de recursos . . . . . . . . . . . . 2
1.1.1. Modelación del problema . . . . . . . . . . . . . . . . 2
1.2. El problema del transporte . . . . . . . . . . . . . . . . . . . 4
1.3. Un problema de dieta . . . . . . . . . . . . . . . . . . . . . . 6
3. MÉTODO GRÁFICO 19
3.1. Región acotada . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2. Región no acotada . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3. Óptimo no acotado . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4. Otros casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4. CONJUNTOS CONVEXOS 27
4.1. Convexos, envolventes, combinaciones . . . . . . . . . . . . . 27
iii
iv ÍNDICE GENERAL
6. DOS TEOREMAS 47
6.1. Representación . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.2. Optimalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7. EL MÉTODO SIMPLEX 57
7.1. Condiciones de optimalidad . . . . . . . . . . . . . . . . . . . 57
7.2. Deducción matricial del método simplex . . . . . . . . . . . . 62
iv
ÍNDICE GENERAL v
v
vi ÍNDICE GENERAL
vi
PRÓLOGO
viii
NOTACIÓN
R1×1 = R.
AT = transpuesta de la matriz A.
Rn = { (x1 , x2 , . . . , xn ) : xj ∈ R ∀j}.
n = número de variables.
m = número de restricciones.
min z := minimizar z.
max z := maximizar z.
x ≥ y ⇔ xi ≥ yi ⇔ xi ≥ yi para todo i.
x ≥ 0 ⇔ xi ≥ 0 ⇔ xi ≥ 0 para todo i.
x ≥ 0 y x ≯ 0 ⇔ x ≥ 0, ∃xi = 0.
min z = cT x
min z = cT x
sujeto a
Ax = b ⇐⇒
Ax = b
x ≥ 0.
x ≥ 0.
x
NOTACIÓN xi
xi
Capı́tulo 1
INTRODUCCIÓN
1
2 CAPÍTULO 1. INTRODUCCIÓN
Sean:
2
1.1. UN PROBLEMA DE ASIGNACIÓN DE RECURSOS 3
Es claro que las variables no pueden tomar todos los valores posibles, en este
ejemplo hay que tener en cuenta la disponibilidad mensual de las máquinas.
La máquina M1 es usada una hora por cada unidad del producto P1 y
una hora por cada unidad del producto P2 . Su disponibilidad es de 400
horas al mes. Esto se puede expresar mediante la siguiente desigualdad
x1 + x2 ≤ 400.
x1 + 2x2 ≤ 580.
x1 ≤ 300.
x1 ≥ 0
x2 ≥ 0,
o también
xi ≥ 0, i = 1, 2,
o simplemente
x ≥ 0.
La no negatividad de las variables es una restricción común a casi todos los
problemas de optimización lineal.
En este problema se puede pensar que las variables x1 , x2 deben tomar
valores enteros (no tiene sentido producir 249.2 unidades del producto P1 ).
Sin embargo, puesto que se trata de números relativamente grandes y los
métodos usuales de optimización lineal suponen que las variables pueden
tomar valores no enteros, se puede hacer la aproximación de un número no
3
4 CAPÍTULO 1. INTRODUCCIÓN
4
1.2. EL PROBLEMA DEL TRANSPORTE 5
Restricciones de no negatividad:
En resumen:
x11 + x21 = 70
x12 + x22 = 80
x13 + x23 = 90
xij ≥ 0 para todo i, j.
5
6 CAPÍTULO 1. INTRODUCCIÓN
% % % % Calorı́as
Proteı́nas Grasas Glúcidos Agua por kilo
Carne 10 10 0 80 1300
Papas 2 0 20 78 880
Habichuelas 1 0 5 94 240
Leche 5 3 5 87 670
Guayaba 1 0 15 84 640
Sean:
x1 = cantidad (kilos) de carne que hay que comprar para el almuerzo de las
seis personas.
6
1.3. UN PROBLEMA DE DIETA 7
Función objetivo:
Cantidad de calorı́as:
Porcentaje de proteı́nas:
Porcentaje de grasas:
Porcentaje de glúcidos:
Condiciones de no negatividad:
xi ≥ 0, i = 1, 2, . . . , 5.
En resumen:
7
8 CAPÍTULO 1. INTRODUCCIÓN
EJERCICIOS
1.1. Una cooperativa agrı́cola debe planificar las siembras en n fincas. Para
la finca i , i = 1, ..., n, se conoce:
Si : superficie (ha) de la finca.
Ai : volumen (m3 ) de agua disponible por dı́a.
Es posible sembrar m clases de cultivos. Para el cultivo j , j = 1, ..., m,
se conocen los siguientes datos:
Hj : superficie máxima total (ha) que se puede sembrar.
Cj : consumo diario de agua (m3 ) por hectárea.
Tj : número de toneladas cosechadas en cada hectárea.
Pj : precio de venta ($) de cada tonelada.
Ij : cantidad inicial ($) que se debe invertir en cada hectárea.
8
1.3. UN PROBLEMA DE DIETA 9
9
10 CAPÍTULO 1. INTRODUCCIÓN
Periodo Cantidad
2 a.m. a 6 a.m 34
6 a.m. a 10 a.m 48
10 a.m. a 2 p.m 37
2 p.m. a 6 p.m 35
6 p.m. a 10 p.m 32
10 p.m. a 2 a.m 30
De todas maneras don Ramón vende los huevos a $100. Las cajas de
huevos miden 30 cm. × 35 cm. × 40 cm. En su bodega, de noche, hay
espacio para guardar 2000 cajas. Durante el dı́a hay mucho más espa-
cio pues no están las dos busetas que su cuñado deja por las noches en
la bodega. Para garantizar que los huevos que él vende sean frescos,
don Ramón tomó la determinación de no dejar huevos en la bodega
entre el viernes en la tarde y el lunes en la mañana. Inicialmente don
10
1.3. UN PROBLEMA DE DIETA 11
Ramón pagaba un vigilante para las noches y los fines de semana, pero
un vecino, que trabaja en una compañı́a de seguros, lo convenció para
asegurar su mercancı́a y ası́ no tener que pagar vigilante. Don Ramón
debe pagar $10 por cada caja (de 180 huevos) y por noche, esto quiere
decir, por ejemplo, que no paga nada por las noches de viernes, sábado
y domingo. Para maximizar la ganancia, pidió consejo a su hijo Ra-
moncito, quien estudia en la universidad, y precisamente está tomando
un curso de OL. Como esta materia es nueva para él, pidió ayuda a
su profesor, quien no le resolvió el problema, pero le sugirió plantearlo
fácilmente con las siguientes variables: x1 : número de cajas de huevos
que compra el lunes; x2 : número de cajas que compra el martes; ...
x5 : número de cajas que compra el viernes; y1 : número de cajas que
quedan en la bodega el lunes en la noche; y2 : número de cajas que
quedan en la bodega el martes en la noche; ... y4 : número de cajas
que quedan en la bodega el jueves en la noche. Plantee el anterior
problema de OL.
11
12 CAPÍTULO 1. INTRODUCCIÓN
12
Capı́tulo 2
DIFERENTES FORMAS
DE PROBLEMAS DE
OPTIMIZACIÓN LINEAL
13
14 CAPÍTULO 2. DIFERENTES FORMAS DE PROBLEMAS
14
2.3. FORMA CANÓNICA 15
min z = cT x
Ai x ≥ bi , para todo i
x ≥ 0,
min z = cT x
Ax ≥ b
x ≥ 0.
min z = cT x
Ai x = bi , para todo i
x ≥ 0,
min z = cT x
Ax = b
x ≥ 0.
15
16 CAPÍTULO 2. DIFERENTES FORMAS DE PROBLEMAS
1. Una desigualdad
Si la desigualdad es de la forma
16
2.5. EQUIVALENCIA ENTRE LAS DIFERENTES FORMAS 17
17
18 CAPÍTULO 2. DIFERENTES FORMAS DE PROBLEMAS
EJERCICIOS
18
Capı́tulo 3
MÉTODO GRÁFICO
El método gráfico sirve para resolver, con una precisión aceptable, una
gran parte de los problemas de optimización lineal de dos variables. Tiene
dos etapas importantes, la primera es la determinación de la región ad-
misible o realizable o factible (el conjunto de puntos que cumplen todas las
restricciones) y la segunda es la búsqueda del punto óptimo (o de los puntos
óptimos) en la región admisible.
La determinación de la región admisible es muy sencilla, pues se trata de
obtener la intersección de semiplanos (desigualdades) y de rectas (igualda-
des). Como generalmente las variables son no negativas, el estudio se hace
únicamente en el primer cuadrante. El conjunto admisible estará entonces
limitado por semirrectas (en este caso el conjunto admisible no es acotado)
o por segmentos de recta. Los valores de las coordenadas de los vértices
se pueden determinar gráficamente o de manera más precisa, analı́ticamen-
te, calculando la solución de las dos ecuaciones (rectas) que determinan el
vértice (un vértice corresponde a la noción, que se verá posteriormente, de
punto extremo de un convexo).
Una vez hallada la región admisible se procede a buscar el óptimo. Se
necesita entonces saber como varı́a la función objetivo y, sobre todo, en
qué dirección mejora. Una manera sencilla consiste en dar dos valores arbi-
trarios diferentes a z y dibujar las rectas (paralelas) correspondientes. Esto
permite saber en qué sentido mejora el valor de z. Para cualquier otro valor
de z, la recta correspondiente será paralela. Únicamente queda por encon-
trar una de estas rectas paralelas, con el mejor valor posible de z y que pase
al menos por un punto de la región admisible.
19
20 CAPÍTULO 3. MÉTODO GRÁFICO
Ejemplo 3.1.
max z = x1 + 1.4x2
x1 + x2 ≤ 400
x1 + 2x2 ≤ 580
x1 ≤ 300
x ≥ 0.
.....
.....
.....
.....
.....
.....
400 .....
.....
.....
.....
..... x1 + x2 = 400
.....
..... ...
..... ...
..... ...
.....
....... ..... ...
.......
........
........
.......
.....
.....
.....
.....
...
...
...
x1 = 300
.
(0,290) .............
.................. ..
.....
......
...
...
...................... . . ..
..... ...
.......................... .. ..
...... ...
.............................. .. ..
..... ...
.................................. ...... .. .. ...
...................................... ...... . . . (220,180) ...
200 ................................................
............................................
.. .
.
..
...
...
...
..................................................... ... ..
....... .............................................. ......... .... . ..
.
................................................ .......... . .
.
....... ..................................................
.................................................... .... ..............
.
.
...........
x1 + 2x2 = 580
. ........................................................... .......
....... ............
.
. .......
.................................................. ....... .......
(300,100)
.................................................. .. .......
.................................................. ... ..... . .
.
.......
.......
.......
....... .......
.....
...
400 .....
....
....... . z = 100
.......
.......
z=0
Figura 3.1
( 0, 0),
( 300, 0),
( 300, 100),
( 220, 180),
( 0, 290).
Al dar a z los valores 0 y 100, dos valores arbitrarios, se obtienen las rectas
0 = x1 + 1.4x2 ,
100 = x1 + 1.4x2 .
20
3.2. REGIÓN NO ACOTADA 21
x∗ = (220, 180),
z ∗ = 472. 3
( 0, 0), z = 0,
( 300, 0), z = 300,
( 300, 100), z = 440,
( 220, 180), z = 472,
( 0, 290), z = 406.
Ejemplo 3.3.
21
22 CAPÍTULO 3. MÉTODO GRÁFICO
...
... . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. .
...
.......................................
...
...
.......................................
...
...
...
. . . . . . . . . . . . . . . . . . . .
...
6 .......................................
...
...
...
......................................
...
...
...
......................................
...
...
...
. .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. .
...
...
...
...
...
...................................
...
...
...
4 ...................................
...
...
...
. .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . ..
...
...
...
...
z =....30
................ . . . . . . . . . . . . . . . . ...
................. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . ..
...
...
...
...
................. . . . . . . . . . . . . . ...
...
. . . ....................... . . . . . . . . . . . . . . . . . . . . .
...
...
...
..
. .. . .. . .. . .. . ........................................ .. . .. . .. . .. . .. . ..
....... ...
....... ...
.......
2 .......
.......
.......
...
...
..
. .. . .. . .. . .. . .. . .. . .. . .. . .. .........................................
....... ...
....... ...
....... ...
....... .
.......
....... ....
(2,1) . . . . . . . . . . . . . . . . . . . . . . . . .
........ ..
..........
........... .....
... .........
. . . . . . . . . . . . . . . . . . . . . ..
. . . . . . . ....
.
... .........
...
.......
.......
.......
z=.......0......... ...
...
.......
.......
................
... .......
4 6 ...
...
.......
.......
................ ... .......
.......
... .......
................ x1 + 2x2 = 4 ... .......
... ......
............. ...
.
Figura 3.2
3x1 + 10x2 = 0,
3x1 + 10x2 = 30.
Los vértices de la figura son: (2, 1), (4, 0), (0, 6). Sin embargo, la región
admisible no está totalmente determinada por estos tres vértices. Además,
es claro que el conjunto factible no es acotado, pero el valor óptimo de z se
obtiene en el punto x∗ = (4, 0) con z ∗ = 12. 3
22
3.3. ÓPTIMO NO ACOTADO 23
Ejemplo 3.4.
max z = 10x1 + 8x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
En este ejemplo la región admisible es la misma. La función z mejora en
la dirección noreste y no hay lı́mite para encontrar una recta z mejor que
las anteriores y que pase por un punto admisible. En este caso hablamos de
un óptimo no acotado o no finito. Lo ideal es que x1 , x2 tomen valores
muy grandes. 3
Ejemplo 3.5.
min z = 8x1 + 16x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
En este caso los puntos que están en el segmento que une (2, 1) con (4, 0),
para los cuales z = 32, son puntos óptimos. Un punto del segmento óptimo
es un punto de la forma
Ejemplo 3.6.
min z = 7x1
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
En este caso los puntos de la semirrecta que parte del punto (0, 6) y sigue en
la dirección del eje x2 , son puntos óptimos con un valor óptimo de z ∗ = 0.
23
24 CAPÍTULO 3. MÉTODO GRÁFICO
x∗ = (0, 6) + µ(0, 1) , µ ≥ 0.
Ejemplo 3.7.
min z = 7x1 + 9x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x1 + x2 ≤ 1
x ≥ 0.
Al hacer la intersección de los conjuntos determinados por cada restricción
se obtiene el conjunto vacı́o. Esto se ve con facilidad ya que se trata sim-
plemente del conjunto admisible de los anteriores ejemplos, intersectado con
el semiplano x1 + x2 ≤ 1. Es decir, no hay puntos que cumplan todas las
restricciones, o más simplemente, el problema no tiene solución. 3
EJERCICIOS
Resolver por el método gráfico los ejercicios 3.1 a 3.10. Averiguar si hay
puntos factibles. Si hay puntos factibles averiguar si hay puntos óptimos. Si
hay puntos óptimos, encontrarlos todos.
24
3.4. OTROS CASOS 25
25
26 CAPÍTULO 3. MÉTODO GRÁFICO
26
Capı́tulo 4
CONJUNTOS CONVEXOS
Figura 4.1
Definición 4.1. Sea C un subconjunto de V . Se dice que C es convexo si
dados x, y en C, λ un escalar en el intervalo [0, 1], entonces z = (1 − λ)x + λy
también está en C. Gráficamente, un conjunto C es convexo si dados dos
27
28 CAPÍTULO 4. CONJUNTOS CONVEXOS
puntos x, y en C, cualquier punto del segmento de recta que los une, también
está en C.
3
Ejemplo 4.2. {(x1 , x2 ) : x2 = x21 } no es convexo ya que (0, 1) = 12 (1, 1)
+ 12 (−1, 1) no está en el conjunto. 3
Definición 4.2. Dados c ∈ Rn , c 6= 0, α ∈ R, se llama hiperplano al
siguiente conjunto:
H = Hc,α = {x ∈ Rn : cT x = α}
H + = {x ∈ Rn : cT x ≥ α},
H − = {x ∈ Rn : cT x ≤ α}.
28
4.1. CONVEXOS, ENVOLVENTES, COMBINACIONES 29
{x ∈ Rn : Ax = b},
{x ∈ Rn : Ax ≥ b},
{x ∈ Rn : Ax = b, x ≥ 0}.
Ejemplo 4.3. Dados (1, 0), (0, 0), (0, 1), son ejemplos de combinaciones
convexas:
1 1 1 1 1
( , ) = (1, 0) + (0, 0) + (0, 1),
2 4 2 4 4
(0, 1) = 0(1, 0) + 0(0, 0) + 1(0, 1). 3
29
30 CAPÍTULO 4. CONJUNTOS CONVEXOS
................. .................
................ .......... ................ ..........
....... . . . . . . ...... ....... . . . . . . ......
............................. .............................
... . . . . . . . . . . ..... ... . . . . . . . . . . .....
............................................. .............................................
.. . . . . . . . . . . . . ... .. . . . . . . . . . . . . ...
.. . . . . . . . . . . . . . ... .. . . . . . . . . . . . . . ...
.................................. ..................................
................................................... ...................................................
.... . . . . . . . . . . . . .... .... . . . . . . . . . . . . ....
................................ ................................
................................ ................................
........ . . . . . . . ........ ........ . . . . . . . ........
.............. . . ............ .............. . . ............
................. .................
A co(A)
. .
...... ......
.......... ..........
... . ... ... . ....
................
. ...............
.
. . . . ... . . . . ..
.... . . . ... .... . . . ...
................. ..................
.................. ..................
.....................
. .....................
.
. . . . . . . . ... . . . . . . . . ..
.... . . . . . . . ... .... . . . . . . . ...
......................... ..........................
........... .... ............ ..........................
....................... ........................
. .............................
.
..... ......... ........ . .... ..............................
......... ..
............ ......... ... . . . . . . . . . . . . ...
......... ... .........................................................................................
B co(B)
· .
...........
..... . ......
..... . . ......
...
..............................
.. . . . . . . ...
..... . . . . . . . ......
.... . . . . . . . . ......
...............................
..... . . . . . . . . . . . .....
· · ........................................
................................
.............................
... . . . . . . . . . . ....
...........................
... ......................
.... . . . . . . . . ...
.....................
... . . . . . . ....
· · ....................................
D co(D)
Figura 4.2
La anterior definición es descriptiva, pero no constructiva. El convexo ge-
nerado por A se puede caracterizar “constructivamenteçomo la intersección
de todos los convexos que contienen a A.
\
co(A) = C.
C convexo
A⊆C
Esta intersección está bien definida ya que por lo menos existe un conjunto
convexo que contiene a A: el espacio completo Rn .
También se puede demostrar que co(A) es exactamente cc(A), el conjunto
de todas las combinaciones convexas de elementos de A, es decir, el conjunto
de todas las combinaciones convexas de subconjuntos finitos de A.
30
4.2. PUNTOS Y DIRECCIONES EXTREMOS 31
Ejemplo 4.4. co({(1, 0), (0, 1), (0, 0)}) = {(x1 , x2 ) : x1 + x2 ≤ 1, x ≥ 0}.
co({(x1 , x2 ) : x1 x2 = 0, x21 + x22 ≤ 1, x ≥ 0}) =
{(x1 , x2 ) : x1 + x2 ≤ 1, x ≥ 0}.
co({(x1 , x2 ) : x2 = x21 }) = {(x1 , x2 ) : x2 ≥ x21 }. 3
x = (1 − λ)u + λv )
u, v ∈ C =⇒ u = v = x.
λ ∈]0, 1[
punto
.............................. ....... punto
....... . . . . ..........
..................... ......
................................ extremo
.......
.... ....
extremo
..
.. . . . . . . . . . . . .. ..............
. ..
............................... ..............
................................ ............ ...
................................... ... . . . . ....
.................................... ............................
.................................
... ........................ ......... punto no
.
.
......................
........................
. puntos no
..... . . . . . . . . .. . .....
....... . . . . . . . . .......
..................... ......... extremo
.............................
... . . . . . .... . . ....
.....................................
.
.. . . . . . . . . . . ...
extremos
.. . . . . . . . . . . . ....
............................ ...
..........................................................................................
Figura 4.3
Ejemplo 4.5. Dado el conjunto convexo
31
32 CAPÍTULO 4. CONJUNTOS CONVEXOS
d = µ1 d1 + µ2 d2 )
d1 , d2 direcciones de C =⇒ d, d1 , d2 son equivalentes .
µ1 , µ2 > 0
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
Los puntos extremos de este conjunto son: (2, 1), (4, 0), (0, 6).
Para el mismo conjunto, (1, 4), (0, 0.001), (345, 0), (2, 8) son direcciones,
y no lo son (0, 0), (−0.01, 100), (−3, −4).
Son direcciones extremas (0, 0.001), (10, 0), o sus direcciones equivalen-
tes. 3
Definición 4.9. Se llama un politopo (convexo) a cualquier conjunto que
se pueda expresar como la intersección de un número finito de semiespacios
(o de semiespacios e hiperplanos). Cuando el politopo (convexo) es acotado
se llama poliedro.
Ejemplo 4.9. El conjunto admisible del ejemplo 3.1 es un politopo y tam-
bién es poliedro. 3
32
4.2. PUNTOS Y DIRECCIONES EXTREMOS 33
EJERCICIOS
4.7. Sea C = {(x1 , x2 ) : |x1 | ≤ x2 }. Halle los puntos extremos, las direc-
ciones y las direcciones extremas de C.
4.9. Sea C = {(x1 , x2 ) : x21 ≤ x2 }. Halle los puntos extremos, las direccio-
nes y las direcciones extremas de C.
33
34 CAPÍTULO 4. CONJUNTOS CONVEXOS
4.11. Sea C = {(x1 , x2 ) : |x1 | + |x2 | ≤ 1}. Halle los puntos extremos, las
direcciones y las direcciones extremas de C.
4.12. Sea C = {(x1 , x2 ) : |x1 + x2 | ≤ 1}. Halle los puntos extremos, las
direcciones y las direcciones extremas de C.
4.15. Sea A ⊆ Rn . Muestre que cc(A) = co(A). Puede usar las siguientes
etapas: mostrar que A ⊆ cc(A); mostrar que cc(A) es convexo; mos-
trar que co(A) ⊆ cc(A); mostrar por inducción, sobre el número de
elementos de una combinación convexa, que cc(A) ⊆ co(A).
34
Capı́tulo 5
CONVEXOS EN
OPTIMIZACIÓN LINEAL
min z = cT x
Ax = b
x ≥ 0,
o lo que es lo mismo:
min z = cT x
x∈F,
donde
F = {x : Ax = b, x ≥ 0} ,
35
36 CAPÍTULO 5. CONVEXOS EN OPTIMIZACIÓN LINEAL
x1 + x2 + x3 = 1
x1 + 2x2 + 3x3 = 4
3x1 + 4x2 + 5x3 = 6
x ≥ 0.
x1 + x2 + x3 = 1
x1 + 2x2 + 3x3 = 4
x ≥ 0.
En cambio
x1 + x2 + x3 = 1
x1 + 2x2 + 3x3 = 4
3x1 + 4x2 + 5x3 = 5
x ≥ 0.
es un sistema inconsistente, no tiene solución. 3
36
5.1. PUNTOS EXTREMOS 37
A = [B L] .
Entonces
Ax = b
x ≥ 0,
es equivalente a
BxB + LxL = b
xB ≥ 0, xL ≥ 0 .
xL = 0
xB solución única de BxB = b, es decir, xB = B −1 b ,
Si además,
xB ≥ 0 ,
37
38 CAPÍTULO 5. CONVEXOS EN OPTIMIZACIÓN LINEAL
Si
xB > 0 ,
la solución se llama básica factible no degenerada.
Si
xB ≥ 0 , pero xB ≯ 0 ,
es decir, si se trata de una solución básica factible, pero alguna coordena-
da básica es nula, la solución se llama básica factible degenerada. Una
solución básica factible no degenerada tiene exactamente m componentes
positivas, una solución básica factible degenerada tiene menos de m compo-
nentes positivas.
Ejemplo 5.2.
min z = − x1 − 1.4x2
x1 + x2 + x3 = 400
x1 + 2x2 + x4 = 580
x1 + x5 = 300
x ≥ 0.
1 1 1 0 0
A= 1 2 0 1 0 .
1 0 0 0 1
Sea
1 0 0
B = [A2 A4 A5 ] = 2 1 0 invertible.
0 0 1
Entonces
1 1
L = [A1 A3 ] = 1 0 ,
1 0
1 0 0 x2 400
BxB = 2 1 0 x4 = 580 .
0 0 1 x5 300
38
5.1. PUNTOS EXTREMOS 39
Luego
400
xB = −220 ,
300
además
· ¸ · ¸
x1 0
xL = = .
x3 0
Se dice entonces que
x = (xB , xL ) = (0, 400, 0, −220, 300)
es una solución básica; pero como no se cumple que xB ≥ 0, entonces no es
realizable.
Sea
1 0 0
B = [A3 A4 A5 ] = 0 1 0 invertible.
0 0 1
Entonces
1 0 0 x3 400
BxB = 0 1 0 x4 = 580 .
0 0 1 x5 300
400
xB = 580 ,
300
39
40 CAPÍTULO 5. CONVEXOS EN OPTIMIZACIÓN LINEAL
Sea
1 2 0
B = [A1 A2 A4 ] = 2 1 −1 invertible.
1 1 0
1 2 x1 6
0
BxB =
2 1 −1 x2 = 6 ,
x4 4
1 1 0
2
xB = 2 .
0
Entonces
x = (2, 2, 0, 0, 0)
40
5.1. PUNTOS EXTREMOS 41
Si
· ¸
1 2
B = [A1 A2 ] = ,
5 2
la solución básica correspondiente es x = (2, 1, 0, 0), que es realizable, luego
es un punto extremo de F .
41
42 CAPÍTULO 5. CONVEXOS EN OPTIMIZACIÓN LINEAL
5.2. Direcciones
Estos datos son los mismos del ejemplo 5.2 , entonces F 6= ∅. Para resolver
Ad = 0, hay que convertir la matriz [A 0] en una matriz equivalente,
escalonada reducida.
1 0 0 0 1 0
0 1 0 1/2 −1/2 0 .
0 0 1 −1/2 −1/2 0
42
5.2. DIRECCIONES 43
Estos datos son los mismos del ejemplo 5.4 , entonces F 6= ∅. Al resolver
Ad = 0 (intercambiando las columnas 1 , 2 con las columnas 3 , 4 ) se
obtiene la solución general:
43
44 CAPÍTULO 5. CONVEXOS EN OPTIMIZACIÓN LINEAL
D1 = {d : Ad = 0, d ≥ 0, d1 + d2 + . . . + dn = 1} .
d ≥ 0.
44
5.2. DIRECCIONES 45
Estas son:
(−2/11, 5/11, 8/11, 0 ) ,
( 2/9, −1/9, 0, 8/9 ) ,
( 1/7, 0, 1/7, 5/7 ) ,
( 0, 1/5, 2/5, 2/5 ) .
Las dos últimas soluciones básicas son realizables y, por lo tanto, son (salvo
equivalencia) las direcciones extremas de F . 3
Ejemplo 5.10. Utilizando el corolario 5.2 para la misma matriz A y el
mismo vector columna b del ejemplo anterior se tiene:
EJERCICIOS
45
46 CAPÍTULO 5. CONVEXOS EN OPTIMIZACIÓN LINEAL
5.3. Minimizar z = 4x1 +5x2 con las restricciones x1 +x2 ≥ 12, 4x1 +3x2 ≥
18, x ≥ 0.
5.4. Minimizar z = 4x1 +5x2 con las restricciones x1 +x2 ≥ 12, 4x1 −3x2 ≤
18, x ≥ 0.
5.5. Minimizar z = 4x1 +5x2 con las restricciones x1 +x2 ≥ 12, 4x1 −3x2 =
18, x ≥ 0.
5.6. Minimizar z = 4x1 + 5x2 con las restricciones 4x1 − 3x2 ≤ −2, −4x1 +
3x2 ≤ 3, x ≥ 0.
5.7. Minimizar z = 4x1 + 5x2 con las restricciones 4x1 − 3x2 ≤ −2, −4x1 +
3x2 ≤ 1, x ≥ 0.
46
Capı́tulo 6
DOS TEOREMAS
6.1. Representación
F = {x = λ1 x1 + λ2 x2 + . . . + λk xk + µ1 d1 + µ2 d2 + . . . + µs ds :
λi ≥ 0∀i λ1 + λ2 + . . . + λk = 1, µj ≥ 0∀j},
47
48 CAPÍTULO 6. DOS TEOREMAS
Ejemplo 6.1.
· ¸ · ¸
1 2 −1 0 4
A= , b= .
5 2 0 −1 12
Los puntos extremos de F son: (2, 1, 0, 0), (4, 0, 0, 8), (0, 6, 8, 0) y sus direc-
ciones extremas (salvo equivalencia) son: (0, 1, 2, 2), (1, 0, 1, 5).
También
x1 + 2x2 ≥ 3
2x1 + x2 ≥ 3
x ≥ 0.
Sus puntos extremos son (1, 1), (3, 0), (0, 3) y sus direcciones extremas (salvo
equivalencia) son (1, 0), (0, 1).
6.2. Optimalidad
48
6.2. OPTIMALIDAD 49
min z = cT x
en F = {x : Ax = b, x ≥ 0},
min z = cT x
Xk s
X k
X
x∈ λi xi + µj dj : dλi ≥ 0, λi = 1, µj ≥ 0 .
i=1 j=1 i=1
cT xu = min {cT xi },
1≤i≤k
c x = max {cT xi }.
T v
1≤i≤k
Entonces, como λi ≥ 0
k
X k
X k
X
i u u
T
λi c x ≥ T
λi c x = c x T
λi = cT xu .
i=1 i=1 i=1
De manera análoga
k
X
λi cT xi ≤ cT xv ,
i=1
y ası́
s
X s
X
v j u
T
c x + T
µj c d ≥ z ≥ c x + T
µj cT dj , µj ≥ 0.
j=1 j=1
49
50 CAPÍTULO 6. DOS TEOREMAS
a)
cT x1 = 8,
cT x2 = 12,
cT x3 = 12,
cT d1 = 2,
cT d2 = 3.
z ∗ = 8, x∗ = x1 = (2, 1, 0, 0).
50
6.2. OPTIMALIDAD 51
b)
cT x1 = 6,
cT x2 = 12,
cT x3 = 0,
cT d1 = 0,
cT d2 = 3.
c)
cT x1 = −5,
cT x2 = −8,
cT x3 = −6,
cT d1 = −1,
cT d2 = −2.
d)
cT x1 = 16,
cT x2 = 16,
cT x3 = 48,
cT d1 = 8,
cT d2 = 4.
z ∗ = 16, x∗ = λ1 x1 + λ2 x2 , λ1 , λ2 ≥ 0, λ1 + λ2 = 1.
51
52 CAPÍTULO 6. DOS TEOREMAS
Ejemplo 6.4.
1 1 1 0 0 400
A = 1 2 0 1 0 , b = 580 .
1 0 0 0 1 300
a)
cT x1 = 0,
T 2
c x = −300,
cT x3 = −440,
cT x4 = −472,
cT x5 = −406,
b)
cT x1 = 0,
T 2
c x = −600,
cT x3 = −800,
cT x4 = −800,
cT x5 = −580,
52
6.2. OPTIMALIDAD 53
z ∗ = −800, x∗ = λ1 x3 + λ2 x4
= λ1 (300, 100, 0, 80, 0) + λ2 (220, 180, 0, 0, 80),
λ1 , λ2 ≥ 0, λ1 + λ2 = 1.
F 6= ∅ ⇐⇒ P =
6 ∅,
F 6= ∅ =⇒ F = cc(P) + cnn(D).
F ∗ 6= ∅ ⇐⇒ F 6= ∅, D− = ∅,
F 6= ∅, D− = ∅ =⇒ F ∗ = cc(P ∗ ) + cnn(Do ).
53
54 CAPÍTULO 6. DOS TEOREMAS
hallar P
si P = ∅ ent F = ∅
sino
hallar D, D− , Do
si D− 6= ∅ ent z ∗ = −∞
sino
si Do = ∅
F ∗ es acotado
si |P ∗ | = 1 ent F ∗ = P ∗
sino |F ∗ | = ∞, F ∗ = cc(P ∗ )
sino
|F ∗ | = ∞, F ∗ no es acotado
F ∗ = cc(P ∗ ) + cnn(Do )
fin-si
fin-si
fin-si
EJERCICIOS
54
6.2. OPTIMALIDAD 55
6.4. Minimizar z = 4x1 +3x2 con las restricciones x1 +x2 ≥ 12, 5x1 −2x2 ≤
4, x ≥ 0.
6.5. Minimizar z = 5x1 +5x2 con las restricciones x1 +x2 ≥ 12, 5x1 −2x2 ≤
4, x ≥ 0.
6.6. Minimizar z = x1 −2x2 con las restricciones x1 +x2 ≥ 12, 5x1 −2x2 ≤ 4,
x ≥ 0.
6.10. Minimizar z = 4x1 + 5x2 con las restricciones 4x1 − 3x2 ≤ −2, −4x1 +
3x2 ≤ 1, x ≥ 0.
55
56 CAPÍTULO 6. DOS TEOREMAS
56
Capı́tulo 7
EL MÉTODO SIMPLEX
57
58 CAPÍTULO 7. EL MÉTODO SIMPLEX
xB = B −1 b ≥ 0,
xL = 0,
El problema
min z = cT x
Ax = b
x ≥ 0,
se puede escribir
entonces
xB = B −1 b − B −1 LxL ,
y ası́ se tiene el problema únicamente en función de las variables libres xL :
58
7.1. CONDICIONES DE OPTIMALIDAD 59
Si se define
T
c̃L = cL − LT B −1 cB ,
entonces
z = cTB B −1 b + c̃TL xL .
El vector c̃L tiene exactamente p = n − m componentes, es decir, una por
cada variable libre; estos coeficientes se llaman usualmente costos reduci-
dos o relativos de las variables libres. También se les acostumbra a denotar
por cj − zj .
Es posible definir de manera análoga los costos reducidos para las varia-
bles básicas:
T
c̃B = cB − B T B −1 cB = 0.
Esta propiedad es una caracterı́stica muy importante: los costos reduci-
dos de las variables básicas son nulos.
Utilizando únicamente las variables libres y sus costos reducidos, el pro-
blema de optimización lineal queda ahora ası́:
Supongamos, por el momento, que las variables básicas son las m primeras
y que las p siguientes son las variables libres. Esta suposición no es restric-
tiva, pues simplemente se puede considerar como un reordenamiento de las
variables.
z es igual a una constante (cTB B −1 b), más una expresión lineal de las
variables libres.
59
60 CAPÍTULO 7. EL MÉTODO SIMPLEX
Proposición 7.1. Para una solución básica realizable, si los costos reduci-
dos de las variables libres son no negativos, entonces esta solución es óptima.
Una solución básica realizable no degenerada es óptima si y solamente si los
costos reducidos de las variables libres son no negativos
T
c̃L = cL − LT B −1 cB ≥ 0.
Ejemplo 7.1.
min z = − x1 − 1.4x2
x1 + x2 + x3 = 400
x1 + 2x2 + x4 = 580
x1 + x5 = 300
x ≥ 0.
Sea
B = [A3 A4 A5 ].
La solución básica correspondiente es x = (0, 0, 400, 580, 300).
−1 T
· ¸ · ¸ · ¸ 1 0 0 0
c̃1 −1.0 1 1 1 0 1 0 0 ,
c̃L = = −
c̃2 −1.4 1 2 0
0 0 1 0
· ¸ · ¸
c̃1 −1.0
c̃L = = .
c̃2 −1.4
60
7.1. CONDICIONES DE OPTIMALIDAD 61
entonces
2 −1 0 220
B −1 = −1 1 0 , B −1 b =
180 .
−2 1 1
80
El punto extremo correspondiente es x = (220, 180, 0, 0, 80) ,
T
· ¸ · ¸ · ¸ 2 −1 0 −1
c̃3 0 1 0 0
c̃L = = − −1 1 0 −1.4
c̃4 0 0 1 0
−2 1 1 0
· ¸ · ¸
c̃3 0.6
c̃L = = .
c̃4 0.4
Luego este punto extremo es óptimo y el valor óptimo de z es: z ∗ = −472,
valor que se puede obtener de dos formas:
220
£ ¤ 180
z = c x = −1 −1.4 0 0 0 0
T
= −472,
0
80
£ ¤ 220
z = cTB B −1 b = −1 −1.4 0 180 = −472. 3
80
Ejemplo 7.2. Considere el problema
min z = − x1 − x2
x1 + 2x2 + x3 = 3
2x1 + x2 + x4 = 3
4x1 + 5x2 + x5 = 9
x ≥ 0.
y el punto
x = (1, 1, 0, 0, 0).
Esta solución básica factible degenerada se puede obtener con
£ ¤
B = A1 A2 A4 .
Entonces al calcular los costos reducidos de las variables libres x3 y x5 se
obtiene £ ¤
c̃TL = −1/3 1/3 .
61
62 CAPÍTULO 7. EL MÉTODO SIMPLEX
b ≥ 0,
se puede formar Im (matriz identidad de orden m) con m columnas
de A.
Sean:
A1 = A,
b1 = b.
En esta primera iteración es muy fácil obtener la solución básica realizable
(ejemplo 7.3.1), pues basta tomar:
B 1 = Im
L1 conformada por las columnas restantes,
y la solución básica realizable es:
x1B = b1 ,
x1L = 0,
x1 = (x1B , x1L ).
62
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 63
Para pasar a la siguiente solución básica realizable x2 , que, además, debe ser
mejor (su valor de z debe ser menor), únicamente se cambiará una columna
de B 1 : una columna de B 1 dejará de ser básica y pasará a ser libre y
también una columna de L1 dejará de ser libre para convertirse en básica.
De manera análoga, una variable básica se volverá libre, y una variable libre
se convertirá en básica.
A1 x = b1 donde B 1 = Im ,
b1 ≥ 0,
A2 x = b2 donde también B 2 = Im ,
b2 ≥ 0.
Este proceso se repite hasta llegar al óptimo o hasta saber que el óptimo no
es acotado.
63
64 CAPÍTULO 7. EL MÉTODO SIMPLEX
c̃L = cL − LT cB ≥ 0.
z = cTB b
Sean: β la m-upla formada por los ı́ndices de las columnas (y de las variables)
básicas en el orden adecuado (para formar la matriz identidad), λ el vector
de p = n − m componentes, formado por los ı́ndices de las columnas libres.
β = (β1 , β2 , . . . , βm ),
λ = (λ1 , λ2 , . . . , λp ),
El cálculo de los costos reducidos de las variables libres (cL −LT cB ) se puede
explicitar ası́:
(LT )1
(LT )2
c̃L = cL − .. cB
.
(LT )p
(LT )1 cB
(LT )2 cB
c̃L = cL − ..
.
(LT )p cB
(Aλ1 )T cB
(Aλ2 )T cB
c̃L = cL − ..
.
(Aλp )T cB .
64
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 65
o también
La igualdad anterior es válida también para las variables básicas, pero para
estas variables no es necesario calcular el costo reducido ya que es nulo.
Efectuando el producto matricial se tiene:
Si c̃kj ≥ 0 para todas las variables libres, entonces xk sı́ es una solución
óptima.
En el caso ii) la(s) variable(s) libre(s) tal(es) que c̃j = 0 puede(n) tomar
valores positivos sin que esto haga aumentar el valor de z, es decir, el valor
óptimo z ∗ permanece óptimo al variar xj de cero a un valor positivo. Esto
quiere decir, si no se trata de una solución realizable básica degenerada,
que hay varios puntos extremos óptimos, más aún, hay un número infini-
to de puntos óptimos (cualquier combinación convexa de puntos extremos
óptimos).
En el caso i), si el punto no es degenerado, cualquier modificación de una
variable libre xj , por pequeña que sea, hace aumentar (empeorar) el valor
de z; o sea, el punto xk es el único óptimo.
Hay varios criterios para escoger una variable, entre las libres, con coefi-
ciente c̃j < 0, para que deje de ser nula y tome un valor positivo, volviéndose
también variable básica. Uno de estos criterios, tal vez el más usado, es esco-
ger la variable con costo reducido más pequeño, es decir, la de costo reducido
“más negativo”. Ası́ se escoge la variable libre que hace disminuir más la
función objetivo z por cada unidad que aumente esta variable libre.
65
66 CAPÍTULO 7. EL MÉTODO SIMPLEX
xB = B −1 b − B −1 LxL = b − LxL
xλ1
xB = b − [L1 . . . Lp ] ...
xλp
p
X
=b− Li xλi
i=1
Xp
xB = b − Aλi xλi .
i=1
xB = b − xe Ae ,
xβi = bi − xe aie , i = 1, . . . , m.
66
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 67
sencilla, basta aumentar xe hasta cuando la primera variable básica con aie
positivo se anule.
bi
xβi = 0 si xe = ·
aie
El nuevo valor de xe será el máximo valor que pueda tomar, o sea, el mayor
valor sin que ninguna variable básica sea negativa, o sea,
½ ¾
bσ bi
x0e = = min : aie > 0, i = 1, ..., m .
aσe aie
En la iteración k
β k = (β1 , β2 , . . . , βσ , . . . , βm ),
β k+1 = (β1 , β2 , . . . , e, . . . , βm ).
67
68 CAPÍTULO 7. EL MÉTODO SIMPLEX
Ak+1 x = bk+1 ,
donde
Ak+1 = (Qk )−1 Ak , bk+1 = (Qk )−1 bk .
Entonces h i
Ak+1
β1 Ak+1
β2 . . . Ae
k+1 . . . Ak+1
βm = Im ,
que es exactamente lo deseado.
−1
Fácilmente se comprueba que Qk tiene la siguiente forma (ver ejemplo
7.3.7):
1 0 ... −ak1e /akσe ... 0
0 1 ... −ak2e /akσe ... 0
.. .. .. .. . . ..
. . . . . .
k −1
(Q ) = 0 0
... 1/akσe ... 0
.. .. .. .. . . ..
. . . . . .
0 0 . . . −akme /akσe ... 1
68
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 69
akie akσj
ak+1
ij = akij − , i = 1, ..., m , i 6= σ, j = 1, ..., n,
akσe
ak bk
bk+1
i = bki − iek σ , i = 1, ..., m, i 6= σ,
aσe
aσjk
ak+1
σj = k , j = 1, ..., n,
aσe
bk
bk+1
σ = kσ ·
aσe
Se puede comprobar que las fórmulas anteriores pueden ser vistas simple-
mente como el resultado de efectuar operaciones elementales sobre las filas
de Ak , bk utilizando la fila σ, para obtener el valor uno en la posición (σ, e)
y el valor cero en las otras posiciones (i, e) de la columna e (ejemplo 7.3.8).
Con el nuevo sistema Ak+1 x = bk+1 se efectúa el mismo proceso y ası́ su-
cesivamente (ejemplo 7.3.9).
En el método simplex, casi siempre se pasa de un punto xk a un punto
mejor xk+1 . En el peor de los casos xk y xk+1 son igualmente buenos. Más
precisamente, si xk no es degenerado, entonces cT xk+1 < cT xk . En general,
cT xk+1 ≤ cT xk .
Puesto que el número de puntos extremos (soluciones básicas realiza-
bles) es finito y (en ausencia de soluciones básicas realizables degeneradas)
siempre se pasa de un punto extremo a uno estrictamente mejor, entonces
el método simplex es un proceso iterativo finito. Más aún, las estadı́sticas
muestran [Dan63] que, para n bastante mayor que m, el número promedio
de iteraciones varı́a aproximadamente entre m y 3m, valores mucho meno-
res que Cm n = n!/(m!(n − m)!) (número de combinaciones de m elementos
69
70 CAPÍTULO 7. EL MÉTODO SIMPLEX
Ejemplo 7.3.
max z = x1 + 1.4x2
x1 + x2 ≤ 400
x1 + 2x2 ≤ 580
x1 ≤ 300
x ≥ 0.
Introduciendo variables de holgura
min z = − x1 − 1.4x2
x1 + x2 + x3= 400
x1 + 2x2 + x4
= 580
x1 + x5 = 300
x ≥ 0.
1 1 1 0 0 400
A = 1 2 0 1 0 , b = 580 .
1 0 0 0 1 300
Ejemplo 7.3.1 : Es claro que se cumplen las condiciones del método sim-
plex: b ≥ 0 y las columnas tercera, cuarta y quinta de A forman la matriz
identidad.
Ejemplo 7.3.2 :
1 1 0 · ¸
−1.0
L = 1 2 , cB = 0 , cL =
1 1 1
.
−1.4
1 0 0
70
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 71
Ejemplo 7.3.3 :
· ¸ · ¸ 0
T −1.0 1 1 1 0
c̃1L = c1L − L1 c1B = −
−1.4 1 2 0
0
· ¸
−1.0
c̃1L = ,
−1.4
luego x1 no es óptimo.
xe = x2 .
Ejemplo 7.3.5 : Para escoger la variable que sale de la base hay que efectuar
los cocientes:
b11 400
1 = = 400,
a12 1
b12 580
1 = = 290,
a22 2
b13
1 : no se calcula ya que a132 ≤ 0.
a32
xβσ = xβ2 ,
xs = x4 .
Ejemplo 7.3.7 :
1 1 0 1 −1/2 0
Q1 = 0 2 0 , (Q1 )−1 = 0 1/2 0 .
0 0 1 0 0 1
71
72 CAPÍTULO 7. EL MÉTODO SIMPLEX
por la matriz (Q1 )−1 , es decir, A2 = (Q1 )−1 A1 , b2 = (Q1 )−1 b1 , o bien, por
medio de operaciones elementales sobre las filas de A1 , b1 para obtener un
uno en la posición (2,2) y ceros en el resto de la segunda columna.
1/2 0 1 −1/2 0 110
A2 = 1/2 1 0 1/2 0 , b2 = 290 .
1 0 0 0 1 300
Ejemplo 7.3.9 :
x2B = (x3 , x2 , x5 ) = (110, 290, 300),
x2 = (0, 290, 110, 0, 300),
z = −406.
El valor de z 2 se puede obtener de tres maneras:
£ ¤£ ¤T
i) z 2 = cT x2 = −1 −1.4 0 0 0 0 290 110 0 300 ,
£ ¤ £ ¤T
ii) z 2 = cTB 2 b2 = 0 −1.4 0 110 290 300 ,
b1σ
iii) z 2 = z 1 + c̃1e = z 1 + c̃1e x1e = 0 + (−1.4)(290).
a1σe
· ¸ · ¸ 0
−1 1/2 1/2 1 −1.4
c̃2L = −
0 −1/2 1/2 0
0
· ¸
−3/10
c̃2L = ,
7/10
luego x2 no es óptimo.
xe = x1 ,
b21 110
2 = = 220,
a11 1/2
b22 290
= = 580,
a221 1/2
b23 300
2 = = 300,
a31 1
xβσ = xβ1 ,
xs = x3 .
72
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 73
· ¸ · ¸ −1.0
0 2 −1 −2 −1.4 ,
c̃3L = −
0 −1 1 1
0
· ¸
3/5
c̃3L = ,
2/5
z ∗ = 472. 3
EJERCICIOS
73
74 CAPÍTULO 7. EL MÉTODO SIMPLEX
7.3. Minimizar z = 4x1 +3x2 con las restricciones x1 +x2 ≥ 12, 5x1 −2x2 ≤
4, x ≥ 0.
a) x = (0, 12).
b) x = (4, 8).
c) x = (5, 10).
d) x = (2, 10).
74
7.2. DEDUCCIÓN MATRICIAL DEL MÉTODO SIMPLEX 75
7.8. Minimizar z = 4x1 +3x2 con las restricciones x1 +x2 ≥ 12, 5x1 −2x2 ≤
4, x ≥ 0.
75
76 CAPÍTULO 7. EL MÉTODO SIMPLEX
76
Capı́tulo 8
Los datos y valores del método simplex se pueden organizar en una tabla,
de tal manera que se facilite la solución manual de un problema pequeño de
programación lineal.
x1 x2 x3
..............................................................................................................................................................................
xn
.... ...
....
c1 ...
...
...
c2 c3 ....
...
cn
.
..........................................................................................................................................................................................................................................
.
.. .. .... ...
... ... b1
xβ1 cβ ...
...
a11 a12 a13
1 ....
.. ...
.....
a1n b1
...
...
....
... ... ... ... a1e
... ... ... ...
... ... .... ....
xβ2 cβ ...
...
...
a21 a22 a23
2 ...
...
.
.
...
...
...
a2n b2 ...
...
... X
... .... ...
...
...
...
... ...
... ... ..... .....
... ... ... ...
... ... ... ...
... ... .... ....
... ... ... ...
... ... ...
...
...
...
... ... ... ...
... ... ... ...
... ...
... ... ..... .....
... ... ... ...
... ... ... ...
xβm cβ ...
... am1 am2 am3
m ...
...
.
. amn bm ....
.
.....
....
...
bm
...
...............................................................................................................................................................................................................................................
ame
...
.. ...
... ...
....
c̃1 c̃2 ...
...
...
X c̃n ...
...
z
..............................................................................................................................................................................
77
78 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
Una vez calculados los costos reducidos c̃j , se puede saber si la tabla es
óptima o no. Recordemos que se tiene el óptimo si los costos reducidos c̃j
son no negativos, para todas las variables libres.
Si la tabla no es óptima se escoge la variable que entra a la base (aquella
cuyo coeficiente c̃j sea el menor). Para visualizar mejor, se resalta la columna
78
8.1. UNA PRIMERA TABLA PARA EL SIMPLEX 79
... ........... ....... ....... ....... ......... ....... ....... ....... ....... ....... ....... ....... ....... ......... ....... ....... ....
... ... ... . ... ...
... ... . . .... ....
... ... ... .... ... ...
... ... .. ... ...
... ... .
. ... ...
............................................................................................................................................................................................................................................................
... ...
... ....
... ...
... ...
.... ..
.............................................................................................................................................................................
Los valores del extremo derecho de la tabla bi /aie , son simplemente los
cocientes de los términos independientes bi y los elementos de la columna
resaltada (la columna que entra), cuando éstos son positivos. Cuando los
coeficientes aie son menores o iguales a cero el cociente no se efectúa (y se
puede indicar por un signo x ). La escogencia de la variable básica que sale
xβσ se hace buscando el mı́nimo de los cocientes. De nuevo para visualizar
mejor, se resalta la fila correspondiente.
Si ninguno de los cocientes bi /aie se efectúa, el valor de z no es acotado
(inferiormente).
Para empezar la iteración siguiente únicamente queda por calcular la
nueva tabla, con base en las fórmulas, pero teniendo en cuenta algunas
simplificaciones:
Para el cálculo de la fila σ únicamente hay que dividir todos sus ele-
mentos por el elemento aσe , llamado pivote.
akie akσj
ak+1
ij = akij − ,
akσe
79
80 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
Ejemplo 8.1.
min z = −x1 − 1.4x2
x1 + x2 ≤ 400
x1 + 2x2 ≤ 580
x1 ≤ 300
x ≥ 0.
.....................................................................................................................................................................................
.. ...
... ...
... ...
−1 −1.4
...
... 0 0 ...
... 0
... ...
.
.
................................................................................................................................................................................................................................................................
.
.. .. .
... ... ..... .....
... ...
x3 ...
... 0 1 ...
... 1 1 0
...
0 ...
.... 400
...
...
....
... ... ... ...
... ... ... ...
... ... ...
...
...
...
... ... ... ...
... ...
x4 ...
... 0 1 ...
... 2 0 1 0 .....
... 580 .....
...
... ... ... ...
... ... .... ....
... ... ... ...
... ... ...
...
...
...
... ...
x5 0 ...
... 1 ...
... 0 0 0 1 ...
... 300 ...
...
... ... ..... ....
..................................................................................................................................................................................................................................................................
.. ...
... ....
... ...
... ...
...
... ...
...
.........................................................................................................................................................................................
80
8.1. UNA PRIMERA TABLA PARA EL SIMPLEX 81
....................................................................................................................................................................................
.... ...
... ...
... ...
−1 −1.4...
... 0 0 ...
...
...
0
... .
..............................................................................................................................................................................................................................................................
.
.
.... .. ... ..
... ... ... ...
x3 ...
...
... 0 1
...
...
... 1 1 0 0
....
...
... 400
....
...
...
... ... ...
...
...
...
... ... ... ...
... ...
... ... ..... .....
... ...
x4 ...
... 0 1 ...
... 2 0 1 0
...
...
.... 580
...
...
....
... ... ... ...
... ... ... ...
... ... ...
...
...
...
... ... ... ...
... ...
x5 0 ...
... 1 ...
... 0 0 0 1 .....
... 300 .....
...
... ... ... ..
...................................................................................................................................................................................................................................................................
... ...
... ...
... ...
−1 −1.4 ...
...
...
0 0 0 ...
...
....
0
.......................................................................................................................................................................................
xe = x2 .
.......................................................................................................................................................................................
... ...
... ...
−1 −1.4
...
...
...
0 0 ...
...
...
0
... ...
........................................................................................................................................................................................................................................................................................
... ... ...
.. ... ...
... ... .. ... ...
x3 ...
... 0 1 ...
... 1 .
.... 1 .
.
.
. 0 ...
0 .
.
.... 400 ...
....
... ... ...
... ... . .... ...
... ... ... ..
. ... ...
... ... .. ... ...
... ... .
. ... ...
.
.... ..... .....
x4 ...
...
...
0 1 ...
...
...
2 ... 0
.
..
. 1 0 ...
... 580 ...
...
. . ..
... ... . ....
... ... ... .... ... ...
... ... .. .... ...
... ... . ... ...
...
x5 0 ...
...
...
1 ...
...
...
0 ....
...
0 ....
0 1 .....
.
.....
300 .....
...
...
.... .... ........ ....... ....... .... ..
..............................................................................................................................................................................................................................................................
... ...
... ...
...
...
−1 −1.4 ...
...
0 0 0 ...
.....
0
... ..
....................................................................................................................................................................................
81
82 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
......................................................................................................................................................................................
.. ..
... ...
... ....
−1 −1.4
...
... 0 0 ...
... 0
... ...
....................................................................................................................................................................................................................................................................................
.
.
.. .. . ..
.... .... ...
.
.
.
. ..... ....
x3 ..
...
... 0 1
..
...
... 1
..
.... 1
.
... 0 0
...
...
.... 400
...
...
.... 400
... ... . .
.. ...
... ... .
. .
. ...
.... . ... ...
... ... . .... ...
... ... .
... ... .. .. ... ...
x4 ...
... 0 1 ...
... 2 ..
.. 0
.
.... 1 0 ..
.
... 580 .....
... 290
... ... .. ..... ...
... ... .. .
. ....
... ... ... .
. .... ...
... ... . ..
. ...
... ... .... ... ...
x5 0 ...
... 1 ...
... 0
...
..
0 . 0 1 ....
... 300 ...
... X
... ... .... ... ..... ....
......................................................................................................................................................................................................................................................................................
... ...
... ....
... ...
−1 −1.4 ...
...
...
0 0 0 ...
...
...
0
.......................................................................................................................................................................................
xβσ = xβ2 ,
xs = x4 .
......................................................................................................................................................................................
... ...
... ...
... ....
−1 −1.4...
...
0 0 ...
...
0
... ..
.......................................................................................................................................................................................................................................................................................
... ... .. ... ...
... ... ... .. .... ....
x3 ...
...
...
0 1 ...
...
...
1 .
.
...
1 .
.
.. 0 0 ...
.
.
.....
400 ...
...
....
400
... ... .. ... ..
... ....... ....... ....... .......... ....... ....... .. ....... ....... ....... ....... ....... ....... ....... ....... .......... ....... ....... .........
... .... . ... ....
... .... ... .
. .
... ..
.. ..........
x4 ...
...
...
0 1 .......
...
.....
2 .
... 0 ..
..
1 0 ...
...
... 580 ......
.. 290
... ..... . ... .....
... .......... ....... ....... ......... ....... ......... ....... ....... ....... ....... ....... ....... ....... ....... .......... ....... ....... ....
... ... .. . ... ...
... ... .. ... ...
x5 0 ...
...
...
1 ...
...
...
0
...
..
0
..
.
. 0 1
...
...
... 300
...
...
... X
... ... .... .. ..... ....
...................................................................................................................................................................................................................................................................................
... ...
... ....
... ...
−1 −1.4 ...
... 0 0 0 ...
...
...
0
...
.....................................................................................................................................................................................
Ahora hay que construir la nueva tabla. En ella se colocan los valores
82
8.1. UNA PRIMERA TABLA PARA EL SIMPLEX 83
.......................................................................................................................................................................................
... ...
... ...
−1 −1.4
...
...
...
0 0 ...
...
... 0
... ...
..................................................................................................................................................................................................................................................................
... ... ... ...
... ... ... ...
x3 ...
...
...
0 ...
...
...
0 1
...
0
....
...
...
....
...
... ... ...
...
...
...
... ... ... ...
... ... ... ...
... ...
..... .....
x2 −1.4 ...
...
...
...
...
...
1 0 0 ...
...
...
...
... ... .... ....
... ... ... ...
... ... ...
...
...
...
... ... ... ...
x5 0 ...
...
...
...
...
...
0 0 1 ...
.....
...
.....
... ... ... ..
................................................................................................................................................................................................................................................................
... ...
... ...
... ...
...
... 0 0 0 ...
...
...
...
.....................................................................................................................................................................................
.....................................................................................................................................................................................
... ...
... ....
...
−1 −1.4
...
...
0 0 ...
...
... 0
.... ...
.................................................................................................................................................................................................................................................................
... ... ... ...
... ... ... ...
x3 ...
...
...
0 0.5 ...
...
...
0 1 −0.5 0
...
....
... 110
...
....
...
... ... ...
...
...
...
... ... ... ...
... ... ... ...
... ...
..... .....
x2 −1.4 0.5 ...
...
...
...
...
...
1 0 0.5 0 ...
... 290 ...
...
... ... .... ....
... ... ... ...
... ... ...
...
...
...
... ... ... ...
x5 0
...
...
... 1
...
...
... 0 0 0 1 ...
..... 300 ...
.....
... ... ... ..
................................................................................................................................................................................................................................................................
... ...
... ...
... ...
...
... 0 0 0 −406 ....
...
... ...
......................................................................................................................................................................................
83
84 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
xe = x1 ,
xβσ = xβ1 ,
xs = x3 .
.....................................................................................................................................................................................
.... ...
... ....
−1 −1.4
...
...
...
0 0 ....
...
...
0
.. .
.................................................................................................................................................................................................................................................................
.
.... .... ... ...
... ... ..... .....
x1 ...
... −1 1 ...
... 0 2 −1 0
...
... 220 ...
...
... ... .... ....
... ... ... ...
... ... ... ...
... ... ...
...
...
...
... ...
x2 −1.4 ...
... 0 ...
... 1 −1 1 0
...
..... 180
...
.....
... ... ... ...
... ... ... ...
... ... .... ....
... ... ... ...
... ... ... ...
x5 0 ...
...
...
0 ...
...
...
0 −2 1 1
...
...
... 80
...
...
...
.... .... ..... ...
..............................................................................................................................................................................................................................................................
... ...
... ....
...
0 ...
...
0 0.6 0.4 0 −472 ...
...
...
... ...
....................................................................................................................................................................................
84
8.1. UNA PRIMERA TABLA PARA EL SIMPLEX 85
...........................................................................................................................................................................................................................
... ...
... ...
...
...
...
0 0 0 0 1 ...
...
...
1
... ...
.............................................................................................................................................................................................................................................................................................................................
... ..... ... ...
... ...... .... ... ...
x5 ...
... 1 1 ...
...... 2 .. −1 0 1 ...
.... 0 ...
.... 4 4
... .... .. ... ...
... .... . .
. ..
... ...... ....... ....... ......... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ............ ....... ....... .........
... ...... ... ...
... .... .... ... ......
x6 ...
1
... 5 .....
...... 2 .
0 −1 0 ....
1 ...
......
.. 12 2.4
... .... ... .. .......
.... ............. ....... ........ ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ............ ....... .............
................................................................................................................................................................................................................................................................................................
... ...
... ...
...
...
−6 ...
...
−4 1 1 0 0 ...
.....
16
... ..
........................................................................................................................................................................................................................
x = (0, 0, 0, 0, 4, 12),
xe = x1 ,
xβσ = xβ2 ,
xs = x6 .
.........................................................................................................................................................................................................................
... ...
... ...
... ....
...
...
0 0 0 0 1 1 ...
...
... ...
...........................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.... .... ..
.
..
. ... ...
... ..... .... ...
........
x5 ...
...
...
1 0....
......
...
1.6
...
.. −1 ...
.
.
0.2 1 −0.2 1.6
...
...
.
. .
.
...
..
1
... ...... ... .... .... .......
... .......... ....... ....... ........ ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ........... ....... ....... ....
... ... .. ... ... ...
... ... .. . ... ...
... ...
x1 ...
...0
... 1
...
...
... 0.4 .... 0
.
.... −0.2 0 0.2 .....
...2.4 .....
... 6
... ... ... ... ... ..
.....................................................................................................................................................................................................................................................................................................................
... ...
... ...
... ...
0 ...
... −1.6 1 −0.2 0 1.2 1.6 ...
...
... ....
..........................................................................................................................................................................................................................
85
86 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
.........................................................................................................................................................................................................................
... ...
... ...
... ....
0
...
...
0 0 0 1 1 ...
...
... ...
..................................................................................................................................................................................................................................................................................................
.
.
.... .. ... ..
... ... .... ....
x2 ...
...
... 0 0
...
...
... 1 −5/8 1/8 5/8 −1/8 ...
...
.... 1
...
...
....
... ... ... ...
... ... ... ...
... ... ...
...
...
...
... ... ... ...
... ...
x1 0
...
... 1 ...
... 0 1/4 −1/4 −1/4 1/4 .....
... 2 .....
...
... ... ... ..
.......................................................................................................................................................................................................................................................................................................
... ...
... ...
... ...
0 ...
...
...
0 0 0 1 1 ...
...0
....
..........................................................................................................................................................................................................................
x∗ = (2, 1, 0, 0, 0, 0).
Esta solución básica realizable es óptima puesto que todos los costos redu-
cidos de variables libres son no negativos. Como, además, algunos de éstos
son nulos y la solución no es degenerada, entonces se puede afirmar que hay
un número infinito de soluciones óptimas para este problema. 3
La tabla del método simplex se puede ver de otra manera, muy semejan-
te, pero con la diferencia de que hay menos fórmulas para pasar de una tabla
a la siguiente. Las pequeñas diferencias se basan en los siguientes hechos:
Se puede demostrar que los costos reducidos de la tabla k + 1 se pueden
calcular directamente a partir de los costos reducidos de la tabla k, mediante
la siguiente fórmula:
c̃ke akσj
c̃k+1
j = c̃k
j − .
akσe
Como se veı́a en el capı́tulo 7 , el nuevo valor de z se puede calcular direc-
tamente mediante la siguiente fórmula:
c̃ke bkσ
z k+1 = z k + ,
akσe
o también:
c̃ke bkσ
−z k+1 = −z k − .
akσe
Si se supone que los costos reducidos forman la fila m + 1, que el valor de −z
es el elemento en la posición (m + 1, n + 1) y que los términos independientes
86
8.2. UNA TABLA MÁS COMPACTA PARA EL SIMPLEX 87
akie akσ,n+1
ak+1 k
i,n+1 = ai,n+1 − , i = 1, . . . , m,
akσe
akm+1,e akσj
ak+1
m+1,j = akm+1,j − , j = 1, . . . , n,
akσe
akm+1,e akσ,n+1
ak+1
m+1,n+1
k
= am+1,n+1 − .
akσe
Esto quiere decir que las fórmulas del capı́tulo 7 son válidas también para
i = m + 1 y para j = n + 1.
akie akσj
ak+1
ij = akij − , i = 1, ..., m + 1, i 6= σ, j = 1, ..., n + 1,
akσe
akσj
ak+1
σj = , j = 1, ..., n + 1.
akσe
87
88 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
Para pasar de Â0 a Â1 basta con efectuar operaciones elementales sobre las
filas de Â0 de tal manera que en la fila m+1 se obtenga el valor cero para las
variables básicas, es decir, se obtiene ası́, al mismo tiempo, en la fila m + 1
los costos reducidos c̃j y el valor de −z.
Una convención muy utilizada es resaltar el elemento pivote aσe , ence-
rrándolo entre un cı́rculo o un cuadrado, mostrando con esto al mismo tiem-
po la columna de la variable que entra y la fila de la variable básica que
sale.
Ejemplo 8.3. Consideremos los mismos datos del ejemplo 8.2:
min z = x5 + x6
x1 + 2x2 − x3 + x5 = 4
5x1 + 2x2 − x4 + x6 = 12
x ≥ 0.
1 2 −1 0 1 0 4
Â0 = 5 2 0 −1 0 1 12
0 0 0 0 1 1 0
La columnas que forman la matriz identidad 2×2 son la quinta y la sexta, en-
tonces hay que buscar, mediante operaciones elementales entre filas, el valor
cero en las posiciones (3,5) y (3,6). Esto se obtiene fácilmente sustrayendo
de la tercera fila una vez la primera fila y una vez la segunda fila.
x5 1 2 −1 0 1 0 4
Â1 : x6 5 2 0 −1 0 1 12
−z −6 −4 1 1 0 0 −16
x = (0, 0, 0, 0, 4, 12),
z = 16.
xe = x1 ,
xβσ = xβ2 ,
xs = x6 .
Un ejemplo del cálculo de los costos reducidos en la segunda tabla es:
a131 a124
a234 = a134 − ,
a121
(−6)(−1)
a234 =1− = −0.2.
5
88
8.2. UNA TABLA MÁS COMPACTA PARA EL SIMPLEX 89
x5 0 1.6 −1 0.2 1 −0.2 1.6
Â2 : x1 1 0.4 0 −0.2 0 0.2 2.4
−z 0 −1.6 1 −0.2 0 1.2 −1.6
xe = x2 ,
xβσ = xβ1 ,
xs = x5 .
x2 0 1 −5/8 1/8 5/8 −1/8 1
Â3 : x1 1 0 1/4 −1/4 −1/4 1/4 2
−z 0 0 0 0 1 1 0
x∗ = (2, 1, 0, 0, 0, 0),
z ∗ = 0. 3
Ejemplo 8.4. Consideremos los mismos datos del ejemplo 8.1 , la matriz
inicial Â0 es:
1 1 1 0 0 400
1 2 0 1 0 580
Â0 =
1 0 0 0 1 300
−1.0 −1.4 0 0 0 0
89
90 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
xe = x2 ,
xβσ = xβ2 ,
xs = x4 .
x3 1/2 0 1 −1/2 0 110
x2 1/2 1 0 1/2 0 290
Â2 :
x5 1 0 0 0 1 300
−z −3/10 0 0 7/10 0 406
xe = x1 ,
xβσ = xβ1 ,
xs = x3 .
x1 1 0 2 −1 0 220
x2
0 1 −1 1 0 180
Â3 :
x5 0 0 −2 1 1 80
−z 0 0 3/5 2/5 0 472
EJERCICIOS
90
8.2. UNA TABLA MÁS COMPACTA PARA EL SIMPLEX 91
91
92 CAPÍTULO 8. TABLAS DEL MÉTODO SIMPLEX
92
Capı́tulo 9
93
94 CAPÍTULO 9. MÉTODO DE LAS DOS FASES
tenido ası́ una solución factible básica con variables básicas no artificiales.
Esto permite utilizar el método simplex con la función objetivo original,
suprimiendo las columnas correspondientes a todas las variables artificiales
(libres y nulas). Esta es la segunda fase.
Si en la primera fase (minimización de la función objetivo artificial) se
desea disminuir el número de cálculos, se puede, en cada iteración, eliminar
la columna correspondiente a la variable que sale (variable básica que se
vuelve libre, nula ) si ésta es artificial.
De todas maneras hay que evitar en la primera fase y en la segunda fase,
que las variables artificiales libres vuelvan a ser básicas.
Ejemplo 9.1.
min z = 3x1 + 10x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
Introduciendo variables de holgura se tiene:
Primera fase:
min za = x5 + x6
x1 + 2x2 − x3 + x5 = 4
5x1 + 2x2 − x4 + x6 = 12
x ≥ 0.
94
9.1. PROBLEMA ARTIFICIAL 95
siguiente:
x2 0 1 −5/8 1/8 1
Â3 : x1 1 0 1/4 −1/4 2
−za 0 0 0 0 0
x = (2, 1, 0, 0),
za = 0.
Como todas las variables artificiales son nulas, entonces el problema sı́ tiene
soluciones factibles; además, se tiene ahora la matriz identidad con variables
no artificiales.
Segunda Fase:
z = 16,
xe = x4 ,
xβσ = xβ1 ,
xs = x2 .
x4 0 8 −5 1 8
x1 1 2 −1 0 4
−z 0 4 3 0 −12
x∗ = (4, 0, 0, 8),
z ∗ = 12.
95
96 CAPÍTULO 9. MÉTODO DE LAS DOS FASES
Puesto que los costos reducidos son positivos, entonces el punto extremo
obtenido es la única solución óptima. 3
Ejemplo 9.2.
min z = 3x1 + 4x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
A la tercera fila hay que restarle tres veces la segunda y cuatro veces la
primera fila para obtener los costos reducidos.
x2 0 1 −5/8 1/8 1
x1 1 0 1/4 −1/4 2
−z 0 0 7/4 1/4 −10
x∗ = (2, 1, 0, 0),
z ∗ = 10.
Ejemplo 9.3.
min z = 3x1 + 4x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x1 + x2 ≤ 1
x ≥ 0.
96
9.2. CONJUNTO NO FACTIBLE 97
Primera fase
min za = x6 + x7
x1 + 2x2 − x3 + x6 = 4
5x1 + 2x2 − x4 + x7 = 12
x1 + x2 + x5 = 1
x ≥ 0.
x6 1 2 −1 0 0 1 0 4
x7
5 2 0 −1 0 0 1 12
Â0 :
x5 1 1 0 0 1 0 0 1
0 0 0 0 0 1 1 0
Para obtener los costos reducidos en la cuarta fila es necesario restarle una
vez la primera fila y una vez la segunda fila.
x6 1 2 −1 0 0 1 0 4
x7 5 2 0 −1 0 0 1 12
Â1 :
x5 1 1 0 0 1 0 0 1
−za −6 −4 1 1 0 0 0 −16
xa = (0, 0, 0, 0, 1, 4, 12),
za = 16,
xe = x1 ,
xβσ = xβ3 ,
xs = x5 .
x6 0 1 −1 0 −1 1 0 3
x7 0 −3 0 −1 −5 0 1 7
Â2 :
x1 1 1 0 0 1 0 0 1
−za 0 2 1 1 6 0 0 −10
97
98 CAPÍTULO 9. MÉTODO DE LAS DOS FASES
min z = cT x
Ai x S bi , i = 1, ..., m,
x≥0
98
9.2. CONJUNTO NO FACTIBLE 99
EJERCICIOS
9.5. Minimizar z = 10x1 + 11x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x ≥ 0.
9.6. Minimizar z = 10x1 + 25x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x ≥ 0.
9.7. Minimizar z = 10x1 + 25x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x1 + x2 ≤ 4, x ≥ 0.
99
100 CAPÍTULO 9. MÉTODO DE LAS DOS FASES
100
Capı́tulo 10
101
102 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
Ejemplo 10.1.
min z = −10x1 − 8x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
Introduciendo variables de holgura se tiene:
min z = −10x1 − 8x2
x1 + 2x2 − x3 = 4
5x1 + 2x2 − x4 = 12
x ≥ 0.
Como no se tiene la matriz identidad es necesario introducir dos variables
artificiales, x5 y x6 . La primera fase para este problema es exactamente la
misma del ejemplo 9.1 y ası́ en el óptimo de la primera fase se tiene:
x2 0 1 −5/8 1/8 1
Â3 : x1 1 0 1/4 −1/4 2 .
−za 0 0 0 0 0
Colocando los costos originales
x2 0 1 −5/8 1/8 1
Âk : x1 1 0 1/4 −1/4 2 .
−10 −8 0 0 0
Calculando los costos reducidos
x2 0 1 −5/8 1/8 1
Âk : x1 1 0 1/4 −1/4 2 ,
−z 0 0 −5/2 −3/2 28
x = (2, 1, 0, 0),
z = −28,
xe = x3 ,
xβσ = xβ2 ,
xs = x1 .
x2 5/2 1 0 −1/2 6
Âk : x3 4 0 1 −1 8 ,
−z 10 0 0 −4 48
102
10.2. CONJUNTO DE PUNTOS ÓPTIMOS INFINITO Y ACOTADO 103
x = (0, 6, 8, 0),
z = −48,
xe = x4
d4 = 1,
dj = 0 en los demás casos,
d = (0, 1/2, 1, 1),
T
c d = c̃e = c̃4 = −4.
z = −48 + µ(−4), µ ≥ 0. 3
103
104 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
Ejemplo 10.2.
min z = 8x1 + 16x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
Estas restricciones son exactamente las mismas del ejemplo anterior. Enton-
ces es necesario introducir dos variables de holgura, dos variables artificiales,
efectuar la primera fase y colocar los costos originales.
x2 0 1 −5/8 1/8 1
Âk : x1 1 0 1/4 −1/4 2 .
8 16 0 0 0
x∗ = (2, 1, 0, 0),
z ∗ = 32.
xe = x4 ,
xβσ = xβ1 ,
xs = x2 .
x4 0 8 −5 1 8
Âk : x1 1 2 −1 0 4 ,
−z 0 0 8 0 −32
104
10.3. CONJUNTO DE PUNTOS ÓPTIMOS NO ACOTADO 105
105
106 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
x = (2, 1, 0, 0),
z = 14,
xe = x3 ,
xβσ = xβ2 ,
xs = x1 .
x2 5/2 1 0 −1/2 6
Âk : x3 4 0 1 −1 8 ,
−z 7 0 0 0 0
x∗ = (0, 6, 8, 0),
z ∗ = 0,
xe = x4 .
d4 = 1,
dj = 0 en los demás casos,
d = (0, 1/2, 1, 1),
T
c d = c̃e = c̃4 = 0.
z ∗ = 0 + µ(0), µ ≥ 0,
z ∗ = 0. 3
106
10.4. VARIABLES ARTIFICIALES BÁSICAS NULAS 107
107
108 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
Ejemplo 10.4.
min z = 4x1 + 2x2 + 5x3
x1 + x2 + x3 = 3
x1 + 2x2 + 3x3 = 6
4x1 + 5x2 + 6x3 = 15
x ≥ 0.
En este caso todas las variables artificiales son nulas, luego hay puntos fac-
tibles. Pero hay una variable artificial nula en la base: x6 . Si se escoge la
opción de ir directamente a la segunda fase, entonces se coloca la fila de
costos originales:
x1 x2 x3 x6
x1
1 0.5 0 0 1.5
 k
: x3
0 0.5 1 0 1.5
.
x6 0 0 0 1 0
4 2 5 0 0
108
10.4. VARIABLES ARTIFICIALES BÁSICAS NULAS 109
x∗ = (0, 3, 0),
z ∗ = 6.
Si en este mismo ejemplo se busca quitar las variables artificiales nulas de
la base, antes de pasar a la segunda fase, hay que sacar a x6 de la base.
Veamos que pasa con la fila correspondiente, es decir, la tercera fila de la
última tabla de la primera fase. Esta fila indica simplemente que x6 = 0,
luego se puede suprimir sin ninguna pérdida de información.
En este caso, desde el principio habı́a una restricción redundante. Se
puede ver, por ejemplo, que la tercera restricción es simplemente la suma de
tres veces la primera y una vez la segunda. Sin embargo, en general, es dis-
pendioso, difı́cil o casi imposible averiguar si hay restricciones redundantes.
Más aún, cuando se plantea un problema es preferible escribir restricciones,
que de pronto podrı́an ser redundantes, que pecar por ausencia de restric-
ciones.
El problema queda entonces con dos restricciones. Al colocar los costos
de la función objetivo real se tiene:
x1 1 1/2 0 1.5
x3 0 1/2 1 1.5 .
4 2 5 0
109
110 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
x = (1.5, 0, 1.5),
z = 13.5,
xe = x2 ,
xβσ = xβ1 ,
xs = x1 .
x2 2 1 0 3
Âk = x3 −1 0 1 0 ,
−z 5 0 0 −6
x∗ = (0, 3, 0),
z ∗ = 6. 3
Ejemplo 10.5.
110
10.4. VARIABLES ARTIFICIALES BÁSICAS NULAS 111
siguiente:
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x13
x1 1 1 1/2 1/2 0 0 1/2 5/4 0 0 0 3
x10 0 0 0 0 0 0 −1/3 −2/3 0 1 0 0
x6
0 1 0 1 0 1 1/3 2/3 0 0 0 3
x5
0 −1 1/2 −1/2 1 0 −1/2 −5/4 0 0 0 0
x13 0 0 0 0 0 0 −1/3 1/3 −1 0 1 0
−za 0 0 0 0 0 0 2/3 1/3 1 0 0 0
Como el valor de za es cero, entonces sı́ hay puntos factibles, sin embargo,
hay variables artificiales básicas nulas. El objetivo es sacar las variables
artificiales de la base antes de pasar a la segunda fase, bien sea suprimiendo
la fila correspondiente, bien sea pivoteando para que una variable no artificial
entre a la base.
La segunda fila, la de la variable básica x10 , no se puede suprimir puesto
que hay valores no nulos (−1/3 y −2/3) fuera del valor uno en la columna
de x10 . En este caso hay que escoger una variable entre x7 y x8 para que
entre a la base. Se observa que en este caso (entrar x7 o x8 ), el pivote resulta
negativo.
Si el criterio es buscar mayor precisión numérica, debe entrar la variable
de coeficiente dominante (mayor en valor absoluto), es decir, la variable x8 .
Si se desea entrar la variable de menor costo hay empate, pues en este
ejemplo ambas son variables de holgura y tienen costo nulo.
Al pivotear sobre el coeficiente −2/3, para que entre la variable x8 y
salga la variable artificial x10 , se obtiene la siguiente tabla
x1 x2 x3 x4 x5 x6 x7 x8 x9 x13
x1
1 1 1/2 1/2 0 0 −1/8 0 0 0 3
x8 0 0 0 0 0 0 1/2 1 0 0 0
x6 0 1 0 1 0 1 0 0 0 0 3
x5 0 −1 1/2 −1/2 1 0 1/8 0 0 0 0
x13 0 0 0 0 0 0 −1/2 0 −1 1 0
111
112 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
x = (3, 0, 0, 0, 0, 3, 0, 0, 0),
z = 15,
xe = x3 ,
xβσ = xβ4 ,
xs = x5 .
x1 1 2 0 1 −1 0 −1/4 0 0 3
x8
0 0 0 0 0 0 1/2 1 0 0
k x6
0 1 0 1 0 1 0 0 0 3
 :
x3
0 −2 1 −1 2 0 1/4 0 0 0
x9 0 0 0 0 0 0 1/2 0 1 0
−z 0 −2 0 0 4 0 3/4 0 0 −15
112
10.4. VARIABLES ARTIFICIALES BÁSICAS NULAS 113
x = (3, 0, 0, 0, 0, 3, 0, 0, 0),
z = 15.
xe = x2 ,
xβσ = xβ1 ,
xs = x1 .
x2 1/2 1 0 1/2 −1/2 0 −1/8 0 0 3/2
x8 0 0 0 0 0 0 1/2 1 0 0
x6
−1/2 0 0 1/2 1/2 1 0 0 0 3/2
,
x3 1 0 1 1 1 0 1/8 0 0 3
x9 0 0 0 0 0 0 1/2 0 1 0
−z 1 0 0 1 3 0 1/2 0 0 −12
EJERCICIOS
10.1. Maximizar z = 4x1 + 5x2 con las restricciones 4x1 + 3x2 ≥ 20, x1 +
2x2 ≥ 10, x ≥ 0.
10.2. Minimizar z = 15x1 + 30x2 con las restricciones 4x1 + 3x2 ≥ 20,
x1 + 2x2 ≥ 10, x ≥ 0.
113
114 CAPÍTULO 10. CASOS ESPECIALES DEL MÉTODO SIMPLEX
10.3. Minimizar z = 10x1 − 10x2 con las restricciones 4x1 + 3x2 ≥ 20,
x1 + 2x2 ≥ 10, −x1 + x2 ≤ 7, x ≥ 0.
10.4. Minimizar z = 2x1 +8x2 con las restricciones 4x1 +3x2 = 20, x1 +2x2 ≥
10, 3x1 + x2 ≥ 10, x ≥ 0.
10.5. Minimizar z = 2x1 + 8x2 + x3 con las restricciones 4x1 + 3x2 + x3 = 20,
x1 + 2x2 + x3 = 10, 3x1 + x2 = 10, x ≥ 0.
114
Capı́tulo 11
MÉTODO DE
PENALIZACIÓN
c̃j = ρj + αj M,
115
116 CAPÍTULO 11. MÉTODO DE PENALIZACIÓN
116
11.2. ESCOGENCIA DE LA VARIABLE QUE ENTRA 117
x1 + 2x2 − x3 + x5 = 4
5x1 + 2x2 − x4 + x6 = 12
x ≥ 0.
117
118 CAPÍTULO 11. MÉTODO DE PENALIZACIÓN
o también
Para obtener costos reducidos se necesita obtener el valor cero para las
variables básicas en las filas de ρj y de αj , es decir, la tercera y cuarta filas;
para esto basta con restar de la cuarta fila una vez la primera fila y una vez
la segunda fila.
x1 x2 x3 x4 x5 x6
x5 1 2 −1 0 1 0 4
Â1 : x6 5 2 0 −1 0 1 12 ,
ρj 3 10 0 0 0 0 0
αj −6 −4 1 1 0 0 −16
x = (0, 0, 0, 0, 4, 12),
zp = 16M.
xe = x1 ,
xβσ = xβ2 ,
xs = x6 .
118
11.2. ESCOGENCIA DE LA VARIABLE QUE ENTRA 119
x1 x2 x3 x4 x5
x5 0 1.6 −1 0.2 1 1.6
2
 : x1 1 0.4 0 −0.2 0 2.4 ,
ρj 0 8.8 0 0.6 0 −7.2
αj 0 −1.6 1 −0.2 0 −1.6
x = (2.4, 0, 0, 0, 1.6),
zp = 7.2 + 1.6M.
xe = x4 ,
xβσ = xβ1 ,
xs = x5 .
x4 0 8 −5 1 8
x1
1 2 −1 0 4
,
Â3 :
ρj 0 4 3 0 −12
αj 0 0 0 0 0
x∗ = (4, 0, 0, 8),
z ∗ = 12.
119
120 CAPÍTULO 11. MÉTODO DE PENALIZACIÓN
x = (0, 0, 0, 0, 4, 12),
zp = 16M.
Es claro que hasta acá no hay ninguna diferencia con el método anterior.
120
11.2. ESCOGENCIA DE LA VARIABLE QUE ENTRA 121
xe = x1 ,
xβσ = xβ2 ,
xs = x6 .
x1 x2 x3 x4 x5
x5 0 1.6 −1 0.2 1 1.6
Â2 : x1 1 0.4 0 −0.2 0 2.4 ,
ρj 0 8.8 0 0.6 0 −7.2
αj 0 −1.6 1 −0.2 0 −1.6
x = (2.4, 0, 0, 0, 1.6),
zp = 7.2 + 1.6M.
xe = x2 ,
xβσ = xβ1 ,
xs = x5 .
x2 0 1 −5/8 1/8 1
x1 1 0 1/4 −1/4 2
Â3 : ,
ρj 0 0 5.5 −0.5 −16
αj 0 0 0 0 0
x = (2, 1, 0, 0),
z = 16.
xe = x4 ,
xβσ = xβ1 ,
xs = x2 .
x4 0 8 −5 1 8
Â4 : x1 1 2 −1 0 4 ,
ρj 0 4 3 0 −12
121
122 CAPÍTULO 11. MÉTODO DE PENALIZACIÓN
x∗ = (4, 0, 0, 8),
z ∗ = 12. 3
Ejemplo 11.3.
min z = 3x1 + 4x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x1 + x2 ≤ 1
x ≥ 0.
Introduciendo variables de holgura x3 , x4 y x5 y las artificiales x6 y x7 , se
tiene:
x1 + 2x2 − x3 + x6 = 4
5x1 + 2x2 − x4 + x7 = 12
x1 + x2 − x4 + x5 = 1
x ≥ 0.
La función objetivo de penalización será:
zp = 3x1 + 4x2 + M x6 + M x7 .
122
11.3. CONJUNTO NO FACTIBLE 123
x = (0, 0, 0, 0, 1, 4, 12),
zp = 16M,
xe = x1 ,
xβσ = xβ3 ,
xs = x5 .
x1 x2 x3 x4 x5 x6 x7
x6
0 1 −1 0 −1 1 0 3
x7 0 −3 0 −1 −5 0 1 7
Â2 : ,
x1 1 1 0 0 1 0 0 1
ρj 0 1 0 0 −3 0 0 −3
αj 0 2 1 1 6 0 0 −10
x = (1, 0, 0, 0, 0, 3, 7),
zp∗ = 3 + 10M.
Todos los coeficientes αj de las variables libres son positivos, entonces los
costos reducidos son positivos, luego ya se alcanzó el óptimo. Como hay
variables artificiales no nulas, x6 y x7 , entonces se puede afirmar que el
problema no tiene puntos realizables, es decir, no tiene solución. 3
EJERCICIOS
123
124 CAPÍTULO 11. MÉTODO DE PENALIZACIÓN
11.5. Minimizar z = 10x1 + 11x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x ≥ 0.
11.6. Minimizar z = 10x1 + 25x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x ≥ 0.
11.7. Minimizar z = 10x1 + 25x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x1 + x2 ≤ 4, x ≥ 0.
11.8. Maximizar z = 4x1 + 5x2 con las restricciones 4x1 + 3x2 ≥ 20, x1 +
2x2 ≥ 10, x ≥ 0.
11.9. Minimizar z = 15x1 + 30x2 con las restricciones 4x1 + 3x2 ≥ 20,
x1 + 2x2 ≥ 10, x ≥ 0.
11.10. Minimizar z = 10x1 − 10x2 con las restricciones 4x1 + 3x2 ≥ 20,
x1 + 2x2 ≥ 10, −x1 + x2 ≤ 7, x ≥ 0.
11.11. Minimizar z = 2x1 +8x2 con las restricciones 4x1 +3x2 = 20, x1 +2x2 ≥
10, 3x1 + x2 ≥ 10, x ≥ 0.
11.12. Minimizar z = 2x1 + 8x2 + x3 con las restricciones 4x1 + 3x2 + x3 = 20,
x1 + 2x2 + x3 = 10, 3x1 + x2 = 10, x ≥ 0.
124
Capı́tulo 12
MÉTODO SIMPLEX
REVISADO
12.1. Generalidades
Sea Tb0 la matriz que permite pasar de Â0 a Â1 , es decir, la que permite
125
126 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
Ejemplo 12.2. Para el mismo ejemplo 8.3 , la matriz Tb1 representa el paso
de Â1 a Â2 .
1 −1/5 0
Tb1 = 0 1/5 0 ,
0 6/5 1
0 1.6 −1 0.2 1 −0.2 1.6
Â2 = Tb1 Â1 = 1 0.4 0 −0.2 0 0.2 2.4 . 3
0 −1.6 1 −0.2 0 1.2 −1.6
126
12.1. GENERALIDADES 127
donde
Sbk = Tbk−1 Tbk−2 . . . Tb2 Tb1 Tb0 .
Por construcción Sbk es cuadrada, de orden m+1, invertible (por ser producto
de matrices invertibles) y representa todas las operaciones elementales que
se efectúan sobre Â0 , para obtener Âk . En particular
Sb0 = Im+1 ,
Sb1 = Tb0 ,
Sbk+1 = Tbk Sbk .
Al comparar la última igualdad con la igualdad Âk+1 = Tbk Âk , se deduce que
para pasar de Sbk a Sbk+1 hay que efectuar exactamente las mismas
operaciones elementales requeridas para pasar de Âk a Âk+1 , o sea,
para pasar de Sbk a Sbk+1 hay que utilizar fórmulas sencillas iguales a las de
método simplex.
127
128 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
Ejemplo 12.3. Considérese la tabla Â2 del ejemplo 8.3 . Allı́ las variable
básicas son x5 y x1 , entonces:
· ¸
2 1 1
B = ,
0 5
· ¸
2 −1 1 −0.2
B = ,
0 0.2
£ ¤
cTB 2 = 1 0 ,
−1 £ ¤
−cTB 2 B 2 = −1 0.2 ,
1 −0.2 0
Sb2 = 0 0.2 0 .
−1 0.2 1
128
12.1. GENERALIDADES 129
−1
Es posible corregir o volver a calcular de manera más precisa B k al
cabo de cierto número de iteraciones.
129
130 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
min z = cT x
Ax = b
x ≥ 0,
2. b ≥ 0,
130
12.2. ALGORITMO DEL MSR 131
La única diferencia entre la tabla Â0 y la tabla Â1 está en la última fila: la
tabla Â0 tiene los costos cj y la tabla Â1 tiene los costos reducidos c̃j . Esto
hace que la única diferencia entre R b0 y Rb1 esté en la última fila. Entonces
para obtener R b1 son necesarios los siguientes cálculos:
−1
−cTB 1 B 1 = −cTB 1 Im = −cTB 1 ,
−z 1 = −cTB 1 b1 = −cTB 1 b0 .
cTLk = Sbm+1,
k
Lb0,k .
Ası́ el valor de un costo reducido está dado por:
h i h i · A0 ¸
c̃j = −cB k
T
Bk
−1
1
Â0j = −cB k T
Bk
−1
1 j
cj
−1
= cj − cTB k B k A0j .
131
132 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
c̃Lk ≥ 0,
La columna de la variable que entra Âke está compuesta por Ake y por c̃ke
en la posición m + 1. El vector columna de m componentes Ake se obtiene
−1
multiplicando la matriz B k , que ocupa las primeras m filas y las primeras
m columnas de R bk , por la columna de A0 correspondiente a la variable que
entra.
· k ¸ " −1
#
Ae B k A0e
Âe =
k
= .
c̃ke c̃ke
xs = xβσ ,
bkσ bki
= min { : akie > 0},
akσe 1≤i≤m akie
bki
σ = argmin{ : akie > 0}.
1≤i≤m akie
bk :
En términos de elementos de R
k
ri,m+2 k
σ = argmin{ k
: ri,m+3 > 0}.
1≤i≤m ri,m+3
132
12.2. ALGORITMO DEL MSR 133
min z = − x1 − 1.4x2
x1 + x2 + x3 = 400
x1 + 2x2 + x4 = 580
x1 + x5 = 300
x ≥ 0.
133
134 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
b0 a R
En este ejemplo sencillo no hubo ninguna modificación al pasar de R b1 :
x3 1 0 0 0 400 ?
b1 = x4 0 1 0 0 580 ? ,
R
x5 0 0 1 0 300 ?
−z 0 0 0 1 0 ?
Esto indica que la solución factible actual no es óptima y que la variable que
entra es xe = x2 .
Entonces
1
2
Â1e =
,
0
−1.4
134
12.2. ALGORITMO DEL MSR 135
x3 1 0 0 0 400 1
2
b1 = x4
R
0 1 0 0 580 .
x5 0 0 1 0 300 0
−z 0 0 0 1 0 −1.4
En esta iteración no se puede afirmar que el óptimo sea no acotado, entonces
el proceso continua con la escogencia de la variable que sale de la base,
efectuando los cocientes
400 580
= 400, = 290.
1 2
La variable que sale es entonces
xβσ = xβ2 ,
xs = x4 .
135
136 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
Entonces
0.5
0.5
Â1e =
,
1
−0.3
x3 1 −0.5 0 0 110 0.5
0.5
b 2 = x2
R
0 0.5 0 0 290 .
x5 0 0 1 0 300 1
−z 0 0.7 0 1 406 −0.3
En esta iteración tampoco se puede afirmar que el óptimo sea no acotado,
entonces el proceso continua con la escogencia de la variable que sale de la
base, efectuando los cocientes
110 290 300
= 220, = 580, = 300.
0.5 0.5 1
La variable que sale es entonces
xβσ = xβ1 ,
xs = x3 .
136
12.2. ALGORITMO DEL MSR 137
£ ¤ 2 −1 0 £ ¤
−cTB B −1 = −1 −1.4 0 −1 1 0 = 0.6 0.4 0 .X
−2 1 1
La tabla del MSR presentada aquı́, puede diferir de las tablas presentadas
en algunos libros. Las diferencias pueden ser dos: con respecto a la columna
m + 1 y a la fila m + 1. Como la columna m + 1 siempre tiene la forma: 0 0
. . . 1, entonces puede ser suprimida. La fila m + 1 algunas veces es colocada
como primera fila.
137
138 CAPÍTULO 12. MÉTODO SIMPLEX REVISADO
EJERCICIOS
12.2. Minimizar z = 4x1 +3x2 con las restricciones x1 +x2 ≥ 12, 5x1 −2x2 ≤
4, x ≥ 0.
138
Capı́tulo 13
139
140 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
140
13.1. DE LA PRIMERA A LA SEGUNDA FASE 141
Entonces
1
Â1e = 5 ,
−6
x5 1 0 0 4 1
b1 = x6 0
R 1 0 12 5 .
−za −1 −1 1 −16 −6
4 12
= 4, = 2.4.
1 5
xβσ = xβ2 ,
xs = x6 .
141
142 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
Entonces
1.6
Â2e = 0.4 ,
−1.6
x5 1 −0.2 0 1.6 1.6
b2 = x1 0
R 0.2 0 2.4 0.4 .
−za −1 0.2 1 −1.6 −1.6
En esta iteración no se puede afirmar que el óptimo sea no acotado, entonces
el proceso continua con la escogencia de la variable que sale de la base,
efectuando los cocientes
1.6 2.4
= 1, = 6.
1.6 0.4
La variable que sale es entonces
xβσ = xβ1 ,
xs = x5 .
142
13.1. DE LA PRIMERA A LA SEGUNDA FASE 143
x = (2, 1, 0, 0, 0, 0),
za = 0.
Como todas las variables artificiales son nulas se puede afirmar que ya se
obtuvo el óptimo de la primera fase con una solución factible. De todas
maneras esto se puede comprobar mediante el cálculo de los costos reducidos
de las variables libres no artificiales.
£ ¤ −1 0
c̃TL3 = Sb33 L
b 0,3 = 0 0 1 0 −1
0 0
£ ¤
= 0 0 .
bk es:
Entonces la nueva matriz R
x2 0.625 −0.125 0 1 ?
b3 = x1 −0.250
R 0.250 0 2 ? ,
−z −5.5 0.5 1 −16 ?
x = (2, 1, 0, 0),
z = 16.
143
144 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
Esto indica que la solución factible actual no es óptima y que la variable que
entra es:
xe = x4 .
Ahora se requiere calcular la columna Ae :
· ¸· ¸ · ¸
3 −1 0 0.625 −0.125 0 0.125
Ae = B
3
Ae = = .
−0.250 0.250 −1 −0.250
Entonces
0.125
Â3e = −0.250 ,
−0.5
x2 0.625 −0.125 0 1 0.125
b3 = x1 −0.250
R 0.250 0 2 −0.250 .
−z −5.5 0.5 1 −16 −0.5
En esta iteración no se puede afirmar que el óptimo sea no acotado, entonces
el proceso continúa con la escogencia de la variable que sale de la base; en
este caso únicamente puede salir x2 .
xβσ = xβ1 ,
xs = x2 .
144
13.2. CONJUNTO NO FACTIBLE 145
min za = x6 + x7
x1 + 2x2 − x3 + x6 = 4
5x1 + 2x2 − x4 + x7 = 12
x1 + x2 + x5 = 1
x ≥ 0.
145
146 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
1 2 −1 0 0 1 0 4
5 2 0 −1 0 0 1 12
Â0 =
1
.
1 0 0 1 0 0 1
0 0 0 0 0 1 1 0
Las variables básicas en la primera iteración son: x6 , x7 , x5 . La obtención
b0 es inmediata:
de la matriz R
x6 1 0 0 0 4 ?
Rb0 = x7 0 1 0 0 12 ? .
x5 0 0 1 0 1 ?
0 0 0 1 0 ?
146
13.2. CONJUNTO NO FACTIBLE 147
Entonces
1
5
Â1e =
1 ,
−6
x6 1 0 0 0 4 1
x 0 1 0 0 12 5
b1 = 7
R .
x5 0 0 1 0 1 1
−za −1 −1 0 1 −16 −6
4 12 1
=4 , = 2.4, = 1.
1 5 1
xβσ = xβ3 ,
xs = x5 .
x = (1, 0, 0, 0, 0, 3, 7),
za = 10.
147
148 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
148
13.3. CONJUNTO ÓPTIMO NO ACOTADO 149
x = (2, 1, 0, 0),
z = −28.
Esto indica que la solución factible actual no es óptima y que la variable que
entra es:
xe = x3 .
Ahora se requiere calcular la columna Ae :
· ¸· ¸ · ¸
3 −1 0 0.625 −0.125 −1 −0.625
Ae = B
3
Ae = = .
−0.250 0.250 0 0.250
Entonces
−0.625
Â3e = 0.250 ,
−2.5
x2 0.625 −0.125 0 1 −0.625
bk = x1 −0.250
R 0.250 0 2 0.25 .
−z 2.5 1.5 1 28 −2.5
149
150 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
xβσ = xβ2 ,
xs = x1 .
x = (0, 6, 8, 0),
z = −48.
Esto indica que la solución factible actual no es óptima y que la variable que
entra es:
xe = x4 .
Ahora se requiere calcular la columna Ae :
· ¸· ¸ · ¸
−1 0 0.5 0 −0.5
A4e = B 4 A0e = = .
−1 1 −1 −1
Entonces
−0.5
Â4e = −1 ,
−4
x2 0 0.5 0 6 −0.5
b4 = x3 −1
R 1 0 8 −1 .
−z 0 4 1 48 −4
150
13.3. CONJUNTO ÓPTIMO NO ACOTADO 151
Aquı́ es claro que no se puede escoger una variable que salga de la base,
es decir, el óptimo no es acotado. De igual manera, como en el método
simplex, se puede construir una dirección a lo largo de la cual la función
objetivo disminuye.
d = (0, 0.5, 1, 1).
Entonces los puntos de la forma
son factibles. Para ellos la función objetivo vale −48 + µ(−4), es decir,
decrece indefinidamente. 3
EJERCICIOS
13.5. Minimizar z = 10x1 + 11x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x ≥ 0.
13.6. Minimizar z = 10x1 + 25x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x ≥ 0.
13.7. Minimizar z = 10x1 + 25x2 con las restricciones 2x1 + 3x2 ≥ 12,
2x1 + x2 ≥ 8, x1 + x2 ≤ 4, x ≥ 0.
151
152 CAPÍTULO 13. EL MÉTODO DE LAS DOS FASES Y EL MSR
152
Capı́tulo 14
DUALIDAD
min z = cT x
Ai x ≥ bi , i ∈ M1 ⊆ M
Ai x = bi , i ∈ M r M1
xj ≥ 0, j ∈ N1 ⊆ N
xj ∈ R, j ∈ N r N1 .
max w = bT y
ATj y ≤ cj , j ∈ N1 ⊆ N
ATj y = cj , j ∈ N r N1
yi ≥ 0, i ∈ M1 ⊆ M
yi ∈ R, i ∈ M r M1 .
153
154 CAPÍTULO 14. DUALIDAD
PRIMAL DUAL
problema de minimización problema de maximización
desigualdades ≥ desigualdades ≤
m = número de restricciones m = número de variables
n = número de variables n = número de restricciones
A = matriz de coeficientes AT = matriz de coeficientes
de las restricciones de las restricciones
una desigualdad ≥ una variable no negativa
una igualdad una variable no restringida
una variable no negativa una desigualdad ≤
una variable no restringida una igualdad
cj = coeficiente de la función cj = término independiente
objetivo
bi = término independiente bi = coeficiente de la función
objetivo
154
14.1. EL PROBLEMA DUAL 155
Su dual es entonces:
min z = cT x
Ai x ≥ bi , i ∈ M1 ⊆ M
Ai x = bi , i ∈ M r M1
x ≥ 0.
Su dual es:
max w = bT y
AT y ≤ c
yi ≥ 0, i ∈ M1 ⊆ M
yi ∈ R, i ∈ M r M1 . 3
min z = cT x
Ax = b
x ≥ 0.
155
156 CAPÍTULO 14. DUALIDAD
Su dual es:
max w = bT y
AT y ≤ c
y ∈ Rm . 3
min z = cT x
Ax ≥ b
x ≥ 0.
Su dual es:
max w = bT y
AT y ≤ c
y ≥ 0. 3
14.2. Propiedades
min z = cT x
Ai x ≥ bi , i ∈ M1 ⊆ M
Ai x = bi , i ∈ M r M1
xj ≥ 0, j ∈ N1 ⊆ N
xj ∈ R, j ∈ N r N1 .
156
14.2. PROPIEDADES 157
Su dual es:
max w = bT y
ATj y ≤ cj , j ∈ N1 ⊆ N
ATj y = cj , j ∈ N r N1
yi ≥ 0, i ∈ M1 ⊆ M
yi ∈ R, i ∈ M r M1 .
Para hallar el dual de PD, por ahora, hay que colocarlo en la forma de
minimización con desigualdades ≥ :
min w0 = −bT y
−ATj y ≥ −cj , j ∈ N1 ⊆ N
−ATj y = −cj , j ∈ N r N1
yi ≥ 0, i ∈ M1 ⊆ M
yi ∈ R, i ∈ M r M1 .
max ζ = −cT ξ
−AT Ti ξ ≤ −bi , i ∈ M1 ⊆ M
−AT Ti ξ = −bi , i ∈ M r M1
ξj ≥ 0, j ∈ N1 ⊆ N
ξj ∈ R, j ∈ N r N1 .
min ζ = cT ξ
Ai ξ ≥ bi , i ∈ M1 ⊆ M
Ai ξ = bi , i ∈ M r M1
ξj ≥ 0, j ∈ N1 ⊆ N
ξj ∈ R, j ∈ N r N1 .
157
158 CAPÍTULO 14. DUALIDAD
158
14.2. PROPIEDADES 159
En particular
(Ax̄)i ≥ bi ,
ȳi ≥ 0.
Luego
Entonces
m
X m
X
ȳi (Ax̄)i ≥ ȳi bi ,
i=1 i=1
es decir,
ȳ T Ax̄ ≥ ȳ T b,
o sea,
x̄T AT ȳ ≥ bT ȳ.
Partiendo de
x̄ ≥ 0,
T
A ȳ ≤ c,
se llega a
Ejemplo 14.6.
min z = 3x1 + 4x2
x1 + 2x2 ≥ 4
5x1 + 2x2 ≥ 12
x ≥ 0.
Su dual es
max w = 4y1 + 12y2
y1 + 5y2 ≤ 3
2y1 + 2y2 ≤ 4
y ≥ 0.
159
160 CAPÍTULO 14. DUALIDAD
Sean: x̄ = (4, 3), ȳ = (1, 0). Se puede verificar que x̄ es una solución factible
de PP, es decir, cumple las dos restricciones y, además, sus componentes
son no negativas. Por otro lado, ȳ es una solución factible de PD. Además,
z = cT x̄ = 24, w = bT ȳ = 4. Esto concuerda con el teorema. 3
Ejemplo 14.7. Consideremos los mismos PP y PD del ejemplo anterior.
Sean: x̄ = (4, 3), ȳ = (10, 0). El punto x̄ es una solución factible de PP;
z = cT x̄ = 24; w = bT ȳ = 40. Luego ȳ no puede ser una solución factible de
PD, pues si lo fuera contradirı́a el teorema. 3
160
14.2. PROPIEDADES 161
min z = cT x
Ax − Ih = b
x, h ≥ 0.
min z = c0 x0
T
A0 x0 = b
x0 ≥ 0,
· ¸ · T ¸
c A T
− B −1 c0B ≥ 0
0 −I
T
Sea y = B −1 c0B . Entonces al expresar la última desigualdad por bloques se
tiene:
c − AT y ≥ 0,
0 − −Iy ≥ 0.
161
162 CAPÍTULO 14. DUALIDAD
0 3
Por otro lado, si se emplea el MSR, se obtiene y óptimo directamente de la
última tabla (los 3 primeros elementos de la fila 4):
x1 0 0 1 0 4
x3
−1 0 5 0 8 . 3
x4 0 −1 1 0 1/2
−z 0 0 −3 1 −12
Corolario 14.1. Dos puntos x, y, factibles para el PP y el PD respectiva-
mente, son óptimos si y sólo si cT x = bT y.
162
14.2. PROPIEDADES 163
Ejemplo 14.11.
min z = −x1 − x2
x1 − x2 ≥ 1
−x1 + x2 ≥ 1
x ≥ 0.
Su dual es
max w = y1 + y2
y1 − y2 ≤ −1
−y1 + y2 ≤ −1
y ≥ 0.
(Ai x∗ − bi )yi∗ = 0, i = 1, . . . , m,
(ATj y ∗ − cj )x∗j = 0, j = 1, . . . , n.
163
164 CAPÍTULO 14. DUALIDAD
Ax∗ ≥ b AT y ∗ ≤ c
x∗ ≥ 0 y∗ ≥ 0
cT x∗ = bT y ∗ .
Entonces
Ax∗ − b ≥ 0, x∗ ≥ 0, c − AT y ∗ ≥ 0, y ∗ ≥ 0.
Sean
α = y ∗ T (Ax∗ − b) ≥ 0, β = x∗ T (c − AT y ∗ ) ≥ 0.
α + β = y ∗ T Ax − y ∗ T b + x∗ T c − x∗ T AT y ∗ = 0,
luego
α = 0, β = 0.
m
X m
X
∗T ∗
0 = α = y (Ax − b) = yi∗ (Ax∗ − b)i = yi∗ (Ai x∗ − bi ).
i=1 i=1
max z = x1 + 1.4x2
x1 + x2 ≤ 400
x1 + 2x2 ≤ 580
x1 ≤ 300
x ≥ 0.
Su dual es:
min w = 400y1 + 580y2 + 300y3
y1 + y2 + y3 ≥ 1
y1 + 2y2 ≥ 1.4
y ≥ 0.
La solución de PP es x∗ = (220, 180).
164
14.2. PROPIEDADES 165
Como x∗1 , x∗2 son positivas, entonces la holgura es nula en el óptimo del dual,
para la primera y para la segunda restricción (se tiene la igualdad y no la
desigualdad). Además, en el óptimo del primal, la holgura de la tercera
restricción no es nula: A3 x∗ − b3 = 220 − 300 = −80 ; esto implica que la
tercera variable en el óptimo del dual debe ser nula. En resumen:
y1∗ + y2∗ + y3∗ = 1
y1∗ + 2y2∗ = 1.4
y3∗ = 0
Resolviendo este sistema se tiene:
y1∗ = 0.6,
y2∗ = 0.4,
y3∗ = 0.
También se hubiera podido utilizar la igualdad 400y1∗ +580y2∗ +300y3∗ = z ∗ =
472, obtenida a partir de la proposición 14.4 (o de la proposición 14.6). 3
165
166 CAPÍTULO 14. DUALIDAD
Ejemplo 14.13.
min z = 5x1 + 4x2
x1 + x2 ≥ 5
3x1 + 2x2 ≥ 11
x1 + 2x2 ≥ 8
x ≥ 0.
Su dual es:
max w = 5y1 + 11y2 + 8y3
y1 + 3y2 + y3 ≤ 5
y1 + 2y2 + 2y3 ≤ 4
y ≥ 0.
166
14.2. PROPIEDADES 167
Entonces
eb∗ = 0 = x∗ ,
1 2+1
eb∗ = 0 = x∗ ,
2 2+2
eb = 1 = x∗ ,
∗
3 2+3
eb∗ = 1 = x∗ ,
3+1 1
eb∗ = 4 = x∗ .
3+2 2
y1∗ = 2 = c̃∗2+1 ,
y2∗ = 1 = c̃∗2+2 ,
y3∗ = 0 = c̃∗2+3 ,
∗
y3+1 = 0 = c̃∗1
∗
y3+2 = 0 = c̃∗2 .
Además
z ∗ = 21. 3
EJERCICIOS
167
168 CAPÍTULO 14. DUALIDAD
14.8. Minimizar z = 16x1 + 15x2 con las restricciones x1 + 2x2 ≥ 16, 2x1 +
x2 ≥ 14, 3x1 + x2 ≥ 17, x ≥ 0.
14.9. Minimizar z = 7x1 +8x2 con las restricciones x1 +4x2 ≥ 1, 2x1 +5x2 ≥
2, 3x1 + x2 ≤ −3, 3x1 + 6x2 ≥ 2, x ≥ 0.
168
Capı́tulo 15
15.1. Generalidades
min z = cT x
Ax = b
x ≥ 0.
169
170 CAPÍTULO 15. MÉTODO SIMPLEX DUAL
El MSD acaba, bien sea porque se sabe que el problema no tiene solu-
ciones factibles, o, bien porque se obtuvo una solución factible (y óptima).
Veamos ahora con más detalle algunos pasos del MSD.
Una solución básica es factible si todos los términos independientes son
no negativos:
bi ≥ 0 ∀i.
La escogencia de la variable básica que sale se hace mediante la búsqueda
del bi más negativo, es decir, el más pequeño.
xs = xβσ ,
bσ = min{bi },
i
σ = argmin{bi }.
1≤i≤m
170
15.1. GENERALIDADES 171
de tal manera, que al ser tomado como pivote vuelva positivo el término
independiente bσ y, además, conserve no negativos los costos reducidos.
c̃e c̃j
= max { : aσj < 0, xj es variable libre},
aσe aσj
c̃j
e = argmax { : aσj < 0, xj es variable libre},
1≤j≤n aσj
c̃j
e = argmin { : aσj < 0, xj es variable libre}.
1≤j≤n −aσj
Precisamente este coeficiente aσe se usa como pivote. Las fórmulas para el
pivoteo son exactamente las mismas del método simplex.
akσj
ak+1
σj = , j = 1, ..., n + 1,
akσe
akie akσj
ak+1
ij = akij − , i = 1, ..., m + 1, i 6= σ, j = 1, ..., n + 1
akσe
Ejemplo 15.1. Resolver por el método simplex dual el siguiente problema:
Ahora hay que calcular los costos reducidos. En este caso los costos son
iguales a los costos reducidos ya que su valor es nulo para las variables
171
172 CAPÍTULO 15. MÉTODO SIMPLEX DUAL
básicas. Cómo en esta tabla no hay ningún costo reducido negativo, entonces
sı́ se puede utilizar el MSD.
Cómo hay términos independientes negativos, entonces la solución básica
actual no es factible. Al buscar el término independiente más pequeño se
observa que éste es −12. Entonces:
xβσ = xβ2 ,
xs = x4 .
xe = x1 .
Ahora hay que modificar la tabla usando como pivote a21 = −5.
x3 0 −1.6 1 −0.2 −1.6
Â2 = x1 1 0.4 0 −0.2 2.4 .
−z 0 2.8 0 0.6 −7.2
xβσ = xβ1 ,
xs = x3 ,
2.8 0.6
= −1.75, = −3,
−1.6 −0.2
xe = x2 .
Ahora hay que modificar la tabla usando como pivote a12 = −1.6.
x2 0 1 −0.625 0.125 1
Â3 = x1 1 0 0.25 −0.25 2 .
−z 0 0 1.75 0.25 −10
172
15.2. CONJUNTO NO FACTIBLE 173
173
174 CAPÍTULO 15. MÉTODO SIMPLEX DUAL
xβσ = xβ2 ,
xs = x4 .
2 1
= −0.4, = −0.5,
−5 −2
xe = x1 .
Ahora hay que modificar la tabla usando como pivote a21 = −5.
x3 0 −1.6 1 −0.2 0 −1.6
x1
1 0.4 0 −0.2 0 2.4
.
Â2 =
x5 0 0.6 0 0.2 1 −1.4
−z 0 0.2 0 0.4 0 −4.8
xβσ = xβ1 ,
xs = x3 ,
xe = x2 .
Ahora hay que modificar la tabla usando como pivote a12 = −1.6.
x2 0 1 −0.625 0.125 0 1
x1
1 0 0.25 −0.25 0 2
.
Â3 =
x5 0 0 0.375 0.125 1 −2
−z 0 0 0.125 0.375 0 −5
xβσ = xβ3 ,
xs = x5 .
174
15.2. CONJUNTO NO FACTIBLE 175
EJERCICIOS
15.1. Minimizar z = 7x1 −8x2 con las restricciones x1 +4x2 ≥ 1, 2x1 +5x2 ≥
2, 3x1 + x2 ≤ −3, 3x1 + 6x2 ≥ 2, x ≥ 0.
15.4. Minimizar z = 16x1 + 15x2 con las restricciones x1 + 2x2 ≥ 16, 2x1 +
x2 ≥ 14, 3x1 + x2 ≥ 17, x ≥ 0.
15.5. Minimizar z = 7x1 +8x2 con las restricciones x1 +4x2 ≥ 1, 2x1 +5x2 ≥
2, 3x1 + x2 ≤ −3, 3x1 + 6x2 ≥ 2, x ≥ 0.
175
176 CAPÍTULO 15. MÉTODO SIMPLEX DUAL
176
Capı́tulo 16
EL PROBLEMA DEL
TRANSPORTE
16.1. Planteamiento
m X
X n
min z = cij xij
i=1 j=1
n
X
xij ≤ fi , i = 1, ..., m
j=1
Xm
xij = dj , j = 1, ..., n
i=1
xij ≥ 0, para todo i, j,
donde
177
178 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
bajo la condición
m
X n
X
fi = dj .
i=1 j=1
178
16.1. PLANTEAMIENTO 179
D1 D2 D3 D4
F1 5 9 4 1
F2 3 5 0 8
F3 4 2 6 7
Utilizando el orden x11 , x12 , x13 , x14 , x21 , x22 , ..., la matriz de restricciones
de este problema (con una columna adicional para los términos independien-
tes) es:
1 1 1 1 0 0 0 0 0 0 0 0 10
0 0 0 0 1 1 1 1 0 0 0 0 20
0 0 0 0 0 0 0 0 1 1 1 1 30
1 0 0 0 1 0 0 0 1 0 0 0 13
0 1 0 0 0 1 0 0 0 1 0 0 14
0 0 1 0 0 0 1 0 0 0 1 0 15
0 0 0 1 0 0 0 1 0 0 0 1 18
Las caracterı́sticas especiales son las siguientes:
Hay m × n = 3 × 4 = 12 variables.
Hay m + n = 3 + 4 = 7 restricciones.
179
180 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 0 0 12 8 20
4 2 6 7
F3 13 14 3 0 30
13 14 15 18
180
16.1. PLANTEAMIENTO 181
no nulas.
D1 D2 D3 D4
5 9 4 1
F1 0 0 1 9 10
3 5 0 8
F2 0 0 11 9 20
4 2 6 7
F3 13 14 3 0 30
13 14 15 18
D1 D2 D3 D4
5 9 4 1
F1 0 0 2 9 10
3 5 0 8
F2 0 0 11 9 20
4 2 6 7
F3 13 14 3 0 30
13 14 15 18
181
182 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 −1 11 10
3 5 0 8
F2 0 0 13 7 20
4 2 6 7
F3 13 14 3 0 30
13 14 15 18
Ejemplo 16.3. Consideremos los mismos datos del ejemplo 16.1 , salvo que
las demandas son: 10, 10, 10, 30 .
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 0 10 10 0 20
4 2 6 7
F3 0 0 0 30 30
10 10 10 30
182
16.2. ALGORITMO DEL TRANSPORTE 183
Más adelante se verá como tratar el caso de las soluciones básicas de-
generadas, por el momento se supondrá que no se presentan soluciones
básicas degeneradas.
El algoritmo del transporte es uno solo, sin embargo, hallar la solución
básica inicial y calcular los costos reducidos se puede hacer de varias formas.
Inicialmente veremos métodos muy sencillos, aunque no necesariamente los
más eficientes. Estos métodos son: el de la esquina noroccidental para
obtener una solución básica inicial, y el método ”stepping-stone”(método
paso a paso o método del circuito), para calcular los costos reducidos.
Este método permite hallar una solución factible básica. Como su nom-
bre lo indica, escoge siempre la casilla disponible que esté más arriba y más
a la izquierda. El esquema del algoritmo es el siguiente:
183
184 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
En este contexto del problema del transporte, lı́nea significa fila o colum-
na. Actualizar la oferta quiere decir: restar de la oferta disponible el valor
asignado a la última casilla noroccidental. De manera análoga se actualiza
la demanda disponible. Cuando se asigna la mayor cantidad posible a la
casilla noroccidental, se satura una lı́nea, es decir, una fila o una columna.
En algunos casos, cuando hay degeneramiento, en una casilla anterior a la
última, se saturan al tiempo la fila y la columna. Este caso se estudiará en
el capı́tulo siguiente.
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 18
184
16.3. MÉTODO DE LA ESQUINA NOROCCIDENTAL 185
fila, la cual queda sin oferta disponible. La primera columna queda con una
demanda disponible de 3 unidades.
D1 D2 D3 D4
5 9 4 1
10 0 0 0
F1
0
3 5 0 8
F2 20
4 2 6 7
F3 30
3 14 15 18
Ahora la casilla noroccidental es la casilla (2, 1). La máxima cantidad que se
puede asignar es 3. Esto hace que se sature la primera columna. La primera
columna queda sin demanda disponible y la segunda fila tendrá una oferta
disponible de 17 unidades.
D1 D2 D3 D4
5 9 4 1
10 0 0 0
F1
0
3 5 0 8
3
F2 17
4 2 6 7
F3 0 30
0 14 15 18
En este momento la casilla noroccidental es la casilla (2, 2). La máxima
cantidad que se puede asignar es 14. Esto hace que se sature la segunda
185
186 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
columna.
D1 D2 D3 D4
5 9 4 1
10 0 0 0
F1
0
3 5 0 8
3 14
F2 3
4 2 6 7
F3 0 0 30
0 0 15 18
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0
0
3 5 0 8
F2 3 14 3 0
0
4 2 6 7
F3 0 0 30
0 0 12 18
186
16.3. MÉTODO DE LA ESQUINA NOROCCIDENTAL 187
columna.
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0
0
3 5 0 8
F2 3 14 3 0
0
4 2 6 7
F3 0 0 12 18
0 0 0 18
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 0
3 5 0 8
F2 3 14 3 0 0
4 2 6 7
F3 0 0 12 18 0
0 0 0 0
187
188 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
Este método sirve para calcular los costos reducidos de las variables
libres. Si xij es una variable libre, entonces su costo reducido c̃ij indica la
modificación que tendrá la función objetivo por cada unidad que aumente
esta variable libre. Como en el método simplex, en cada iteración, una y
solamente una variable libre entra a la base, y también, exactamente una
variable básica sale de la base.
Si la variable libre xij con valor nulo, se incrementara en una unidad,
entonces serı́a necesario reequilibrar la tabla, aumentando y disminuyendo el
valor de algunas variables, para que se siga teniendo una solución realizable.
Estas modificaciones únicamente son posibles en las variables básicas, ya
que una sola variable libre puede aumentar para volverse básica y, además,
las variables libres no pueden disminuir pues se volverı́an negativas.
Entonces dada la variable libre xij , que aumentarı́a en una unidad, es
necesario buscar casillas correspondientes a variables básicas, en algunas de
ellas se necesita aumentar una unidad, en otras se necesita disminuir una
unidad, de tal manera que:
Las modificaciones se pueden simbolizar por un signo más (+) para los
aumentos, y un signo menos (−) para las disminuciones.
Se puede demostrar que en una solución factible básica no degenerada,
para cada variable libre xij , hay exactamente un camino o circuito, formado
por la casilla de xij y las casillas de algunas variables básicas, de tal manera
que este circuito rebalancea la tabla.
188
16.4. MÉTODO DEL CIRCUITO (STEPPING-STONE) 189
Una vez conseguido este circuito, el costo reducido c̃ij se calcula natu-
ralmente como la suma de los costos de las casillas del circuito, donde se
tiene en cuenta el signo de cada casilla. Es decir se suman los costos de las
casillas con signo más (+), y se restan los costos de las casillas con signo
menos (−).
Ejemplo 16.5. Tomemos los mismos datos del ejemplo 16.1 y la solución
básica inicial obtenida en el ejemplo 16.4 .
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 3 14 3 0 20
4 2 6 7
F3 0 0 12 18 30
13 14 15 18
Cálculo del costo reducido c̃12 : Si la variable libre x12 aumenta, y como la
única variable básica en la primera fila es x11 , necesariamente x11 debe dis-
minuir. Como x11 está en la primera columna, entonces otra variable básica
de la primera columna debe aumentar. Para este ejemplo necesariamente
x21 debe aumentar. Ahora, considerando la segunda fila, como x21 aumenta,
otra variable básica debe disminuir. La única posibilidad corresponde a x22 .
189
190 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
Ası́ ya se ha completado el circuito con las casillas (1,2), (1,1), (2,1), (2,2).
D1 D2 D3 D4
5− 9+ 4 1
F1 10 0 0 0 10
3+ 5− 0 8
F2 3 14 3 0 20
4 2 6 7
F3 0 0 12 18 30
13 14 15 18
c̃12 = 9 − 5 + 3 − 5 = 2.
Cálculo del costo reducido c̃13 : Si la variable libre x13 aumenta, debe dis-
minuir x11 , entonces debe aumentar x21 . Aquı́ hay dos posibilidades: puede
disminuir x22 o puede disminuir x23 . Si disminuye x22 debe aumentar otra
variable básica en la misma segunda columna, pero no hay más variables
básicas. Luego es necesario desechar esta posibilidad. Si disminuye x23 ya
se completa el circuito (1,3), (1,1), (2,1), (2,3).
c̃13 = 4 − 5 + 3 − 0 = 2.
190
16.4. MÉTODO DEL CIRCUITO (STEPPING-STONE) 191
D1 D2 D3 D4
5− 9 4 1+
F1 10 0 0 0 10
3+ 5 0− 8
F2 3 14 3 0 20
4 2 6+ 7−
F3 0 0 12 18 30
13 14 15 18
c̃14 = 1 − 5 + 3 − 0 + 6 − 7 = −2
De manera semejante:
las casillas “de aumento”son las de posición impar y las casillas “de
disminución”son las de posición par.
191
192 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
Son exactamente las mismas del método simplex: si todos los costos
reducidos de las variables libres de una solución factible básica son
no negativos, entonces ésta es óptima.
192
16.5. OPTIMALIDAD Y MODIFICACIÓN DE LA TABLA 193
Ejemplo 16.6. Consideremos los mismos datos del ejemplo 16.1, la solución
básica inicial obtenida en el ejemplo 16.4 y los costos reducidos calculados
en el ejemplo 16.5.
Hay una sola variable libre con costo reducido mı́nimo: x32 . Ésta es la
variable que entra. Si hubiera empate habrı́a que resolverlo de cualquier
forma, por ejemplo, tomando como variable que entra la primera encontrada
entre las empatadas.
El circuito de esta variable es: (3,2), (3,3), (2,3), (2,2). En las casillas
de disminución (las de posición par), el menor valor xij es 12 y está en la
casilla (3, 3). Entonces la variable x33 sale de la base. La variable libre
y las variables de su circuito son modificadas en 12 unidades. Las demás
casillas no alteran su valor. El valor de la función objetivo debe modificarse
(disminuir) en −9 × 12 = −108 unidades.
Para obtener la nueva tabla, basta aumentar 12 unidades en las casillas
(3, 2), (2, 3) y disminuir 12 unidades en las casillas (3, 3), (2, 2).
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 3 2 15 0 20
4 2 6 7
F3 0 12 0 18 30
13 14 15 18
193
194 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 8 0 0 2 10
3 5 0 8
F2 5 0 15 0 20
4 2 6 7
F3 0 14 0 16 30
13 14 15 18
z = 197,
c̃12 = 13, c̃13 = 2, c̃22 = 11, c̃24 = 9, c̃31 = −7, c̃33 = −2.
194
16.5. OPTIMALIDAD Y MODIFICACIÓN DE LA TABLA 195
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 5 0 15 0 20
4 2 6 7
F3 8 14 0 8 30
13 14 15 18
z = 141,
c̃11 = 7, c̃12 = 13, c̃13 = 9, c̃22 = 4, c̃24 = 2, c̃33 = 5.
195
196 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
4 5 0 8
F2 3 14 3 0 20
3 2 6 7
F3 0 0 12 18 30
13 14 15 18
z = 330.
Después de iteraciones semejantes a las del ejemplo anterior, se llega a la
tabla óptima.
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
4 5 0 8
F2 5 0 15 0 20
3 2 6 7
F3 8 14 0 8 30
13 14 15 18
z = 138,
c̃11 = 8, c̃12 = 13, c̃13 = 11, c̃22 = 2, c̃24 = 0, c̃33 = 7.
196
16.5. OPTIMALIDAD Y MODIFICACIÓN DE LA TABLA 197
Aquı́ hay una diferencia importante. En el óptimo hay una variable libre
con costo reducido nulo: x24 (podrı́a haber más de una). Como la solución
factible básica no es degenerada se puede afirmar que hay muchas soluciones.
Para obtener otra solución factible básica, de manera semejante al método
simplex, se entra a la base la variable libre con costo reducido nulo, y se
construye otra tabla.
Variable que entra : x24 ,
circuito de x24 : (2,4), (2,1), (3,1), (3,4) ,
valor máximo para x24 : 5,
variable que sale : x21 .
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
4 5 0 8
F2 0 0 15 5 20
3 2 6 7
F3 13 14 0 3 30
13 14 15 18
z = 138
c̃11 = 8, c̃12 = 13, c̃13 = 11, c̃21 = 0, c̃22 = 2, c̃33 = 7.
Como era de esperarse, no hay costos reducidos negativos y la tabla es
óptima.
Aquı́ de nuevo, hay una variable libre con costo reducido nulo: x21 . Para
obtener otra solución factible básica, se entra a la base x21 y se construye
otra tabla.
variable que entra : x21 ,
circuito de x21 : (2,1), (2,4), (3,4), (3,1) ,
valor máximo para x21 : 5,
variable que sale : x24 .
197
198 CAPÍTULO 16. EL PROBLEMA DEL TRANSPORTE
Cuando en el óptimo hay varias variables libres con costo reducido nulo,
no es sencillo encontrar todas las soluciones básicas realizables óptimas. En
la práctica, bastarı́a con encontrar dos soluciones básicas realizables óptimas,
escogiendo una de las variables libres con costo reducido nulo para entrarla
a la base construyendo una nueva tabla.
EJERCICIOS
198
Capı́tulo 17
Este método sirve para calcular los costos reducidos sin tener que calcular
el circuito de cada variable. Como su nombre lo indica utiliza las variables
de su problema dual. En realidad se utilizan las variables del dual de un
problema equivalente. El problema planteado inicialmente es el mismo:
m X
X n
min z = cij xij
i=1 j=1
n
X
xij = fi , i = 1, ..., m
j=1
Xm
xij = dj , j = 1, ..., n
i=1
xij ≥ 0, para todo i, j,
bajo la condición
m
X n
X
fi = dj .
i=1 j=1
199
200 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
ui + vj = cij .
200
17.1. MÉTODO DE LAS VARIABLES DUALES 201
c̃ij = cij − ui − vj .
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 3 14 3 0 20
4 2 6 7
F3 0 0 12 18 30
13 14 15 18
201
202 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
z = 327.
u1 + v1 = 5,
u2 + v1 = 3,
u2 + v2 = 5,
u2 + v3 = 0,
u3 + v3 = 6,
u3 + v4 = 7.
v1 = 3, v2 = 5, v3 = 0,
luego
u1 = 2, u3 = 6, v4 = 1.
En resumen
u1 = 2, v1 = 3,
u2 = 0, v2 = 5,
u3 = 6, v3 = 0,
v4 = 1.
c̃12 = 9 − 2 − 5 = 2,
c̃13 = 4 − 2 − 0 = 2,
c̃14 = 1 − 2 − 1 = −2,
c̃24 = 8 − 0 − 1 = 7,
c̃31 = 4 − 6 − 3 = −5,
c̃32 = 2 − 6 − 5 = −9.
Se escoge como variable que entra a la base a x32 , hay que obtener su circuito
y proseguir el método del transporte.
A manera de simple comprobación, se puede escoger otra variable y
otro valor, por ejemplo, v3 = −3. Al resolver el sistema se tienen valores
202
17.2. MÉTODO DEL COSTO MÍNIMO POR FILAS 203
diferentes:
u1 = 5, v1 = 0,
u2 = 3, v2 = 2,
u3 = 9, v3 = −3,
v4 = −2.
Sin embargo, como era de esperarse, los valores de los costos reducidos son
exactamente los mismos.
c̃12 = 9 − 5 − 2 = 2,
c̃13 = 4 − 5 − −3 = 2,
c̃14 = 1 − 5 − −2 = −2,
c̃24 = 8 − 3 − −2 = 7,
c̃31 = 4 − 9 − 0 = −5,
c̃32 = 2 − 9 − 2 = −9. 3
203
204 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 18
204
17.2. MÉTODO DEL COSTO MÍNIMO POR FILAS 205
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 8
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
15
F2 5
4 2 6 7
F3 0 30
13 14 8
205
206 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 0 30
8 14 8
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 14 0 16
8 8
206
17.2. MÉTODO DEL COSTO MÍNIMO POR FILAS 207
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 8 14 0 8
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 5 0 15 0 20
4 2 6 7
F3 8 14 0 8 30
13 14 15 18
207
208 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
Este método sirve para hallar una solución factible básica inicial. Es
muy semejante al método del costo mı́nimo por filas. La única diferencia
consiste en que siempre se busca la casilla disponible de costo mı́nimo en la
primera columna no saturada.
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 18
208
17.3. MÉTODO DEL COSTO MÍNIMO POR COLUMNAS 209
D1 D2 D3 D4
5 9 4 1
0
F1
10
3 5 0 8
13
F2 7
4 2 6 7
F3 0 30
14 15 18
D1 D2 D3 D4
5 9 4 1
0 0
F1
10
3 5 0 8
13 0
F2 7
4 2 6 7
F3 0 14 16
15 18
209
210 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0
10
3 5 0 8
F2 13 0 7 0
4 2 6 7
F3 0 14 16
8 18
D1 D2 D3 D4
5 9 4 1
F1 0 0 8
2
3 5 0 8
F2 13 0 7 0
4 2 6 7
F3 0 14 0 16
18
210
17.3. MÉTODO DEL COSTO MÍNIMO POR COLUMNAS 211
D1 D2 D3 D4
5 9 4 1
F1 0 0 8 2
3 5 0 8
F2 13 0 7 0
4 2 6 7
F3 0 14 0 16
16
D1 D2 D3 D4
5 9 4 1
F1 0 0 8 2 10
3 5 0 8
F2 13 0 7 0 20
4 2 6 7
F3 0 14 0 16 30
13 14 15 18
211
212 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
Este método sirve para hallar una solución factible básica inicial y es
semejante a los dos métodos anteriores. La diferencia consiste en que acá se
busca la casilla disponible de costo mı́nimo en toda la matriz. Su algoritmo
es el siguiente:
212
17.4. MÉTODO DEL COSTO MÍNIMO DE LA MATRIZ 213
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 18
D1 D2 D3 D4
5 9 4 1
0
F1
10
3 5 0 8
15
F2 5
4 2 6 7
F3 0 30
13 14 18
213
214 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
15
F2 5
4 2 6 7
F3 0 30
13 14 8
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
0 15
F2 5
4 2 6 7
F3 14 0 16
13 8
214
17.4. MÉTODO DEL COSTO MÍNIMO DE LA MATRIZ 215
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 14 0 16
8 8
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 8 14 0 8
215
216 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 5 0 15 0 20
4 2 6 7
F3 8 14 0 8 30
13 14 15 18
Este método también sirve para hallar una solución factible básica inicial.
Su algoritmo es el siguiente:
216
17.5. MÉTODO DE VOGEL 217
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 18
217
218 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1
10 3
3 5 0 8
F2 20 3
4 2 6 7
F3 30 2
13 14 15 18
1 3 4 6
218
17.5. MÉTODO DE VOGEL 219
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
F2 20 3
4 2 6 7
F3 30 2
13 14 15 8
1 3 6 1
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
15
F2 5 2
4 2 6 7
F3 0 30 2
13 14 8
1 3 1
219
220 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
0 15
F2 5 5
4 2 6 7
F3 14 0 16 3
13 8
1 1
220
17.5. MÉTODO DE VOGEL 221
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 14 0 16 3
8 8
∞ ∞
221
222 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7
F3 8 14 0 8 ∞
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 5 0 15 0 20
4 2 6 7
F3 8 14 0 8 30
13 14 15 18
222
17.6. MÉTODO DE RUSSEL 223
Este método también sirve para hallar una solución factible básica inicial.
Su algoritmo es el siguiente:
223
224 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 20
4 2 6 7
F3 30
13 14 15 18
D1 D2 D3 D4
5 −9 9 −9 4 −11 1 −16
F1
10 9
3 −10 5 −12 0 −14 8 −8
F2 20 8
4 −8 2 −14 6 −7 7 −8
F3 30 7
13 14 15 18
5 9 6 8
224
17.6. MÉTODO DE RUSSEL 225
El mı́nimo de los valores c0ij es −16 y está en la casilla (1,4). Allı́ se puede
asignar 10 y se satura la primera fila.
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 −9 5 −8 0 −14 8 −8
F2 20 8
4 −7 2 −10 6 −7 7 −8
F3 30 7
13 14 15 8
4 5 6 8
El mı́nimo de los valores c0ij es −14 y está en la casilla (2,3). Allı́ se puede
asignar 15 y se satura la tercera columna.
225
226 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 −9 5 −8 0 8 −8
15
F2 5 8
4 −7 2 −10 6 7 −8
F3 0 30 7
13 14 8
4 5 8
El mı́nimo de los valores c0ij es −10 y está en la casilla (3,2). Allı́ se puede
asignar 14 y se satura la segunda columna.
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 −9 5 0 8 −8
0 15
F2 5 8
4 −7 2 6 7 −8
F3 14 0 16 7
13 8
4 8
226
17.6. MÉTODO DE RUSSEL 227
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 −7 2 6 7 −7
F3 14 0 16 7
8 8
4 7
227
228 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 5 0 15 0
4 2 6 7 −7
F3 8 14 0 8 7
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 5 0 15 0 20
4 2 6 7
F3 8 14 0 8 30
13 14 15 18
228
17.7. SOLUCIONES BÁSICAS DEGENERADAS 229
229
230 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 0 10 0 0 10
4 2 6 7
F3 0 0 10 10 20
10 10 10 10
Dos de las variables nulas deben considerarse como básicas, sin embargo, la
siguiente escogencia no es adecuada.
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 0 10 ² 0 10
4 2 6 7
F3 0 ² 10 10 20
10 10 10 10
230
17.7. SOLUCIONES BÁSICAS DEGENERADAS 231
Las variables básicas son aquellas cuyo valor es positivo o las nulas
indicadas por el sı́mbolo ².
x + ² = x, si x > 0,
x − ² = x, si x > 0,
² + ² = ²,
² − ² = 0.
Ejemplo 17.8. Hallar una solución básica factible por el método de Vogel:
231
232 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1
10
3 5 0 8
F2 10
4 2 6 7
F3 20
10 10 10 10
D1 D2 D3 D4
5 9 4 1
F1
10 3
3 5 0 8
F2 10 3
4 2 6 7
F3 20 2
10 10 10 10
1 3 4 6
232
17.7. SOLUCIONES BÁSICAS DEGENERADAS 233
D1 D2 D3 D4
5 9 4 1
0 0 0 10
F1
3 5 0 8
F2 10 3
4 2 6 7
F3 20 2
10 10 10 0
1 3 6 1
233
234 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 0 0 10 0
4 2 6 7
F3 20 2
10 10 0 0
∞ ∞ ∞ ∞
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 0 0 10 0
4 2 6 7
F3 10 10 4
10 0 0
∞ ∞ ∞
234
17.7. SOLUCIONES BÁSICAS DEGENERADAS 235
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 0 0 10 0
4 2 6 7
F3 10 10 0 1
0 0
∞ ∞
235
236 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10
3 5 0 8
F2 0 0 10 0
4 2 6 7
F3 10 10 ² 0 ∞
No queda sino una casilla disponible, la (3,4). Allı́ se puede asignar 0 (de-
notado por ²) y se saturan al tiempo la tercera fila y la cuarta columna.
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 0 0 10 0 10
4 2 6 7
F3 10 10 ² ² 20
10 10 10 10
236
17.7. SOLUCIONES BÁSICAS DEGENERADAS 237
u1 + v4 = 1,
u2 + v3 = 0,
u3 + v1 = 4,
u3 + v2 = 2,
u3 + v3 = 6,
u3 + v4 = 7.
u1 = −6, v1 = 4,
u2 = −6, v2 = 2,
u3 = 0, v3 = 6,
v4 = 7.
c̃11 = 5 − −6 − 4 = 7,
c̃12 = 9 − −6 − 2 = 13,
c̃13 = 4 − −6 − 6 = 4,
c̃21 = 3 − −6 − 4 = 5,
c̃22 = 5 − −6 − 2 = 9,
c̃24 = 8 − −6 − 7 = 7.
237
238 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 1
F1 10 0 0 0 10
3 5 0 8
F2 10 10 0 0 20
4 2 6 7
F3 0 10 10 10 30
20 20 10 10
z = 280.
238
17.7. SOLUCIONES BÁSICAS DEGENERADAS 239
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 20 ² 0 0 20
4 2 6 7
F3 0 20 10 ² 30
20 20 10 10
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 10 10
3 5 0 8
F2 10 0 10 0 20
4 2 6 7
F3 10 20 0 ² 30
20 20 10 10
z = 120. 3
239
240 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
240
17.8. OFERTA TOTAL DIFERENTE DE DEMANDA TOTAL 241
D1 D2 D3
5 9 4
F1
10
3 5 4
F2 20
4 2 6
F3 30
11 12 13
D1 D2 D3 D4
5 9 4 0
F1
10
3 5 4 0
F2 20
4 2 6 0
F3 30
11 12 13 24
241
242 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
D1 D2 D3 D4
5 9 4 0
F1 0 0 4 6 10
3 5 4 0
F2 11 0 9 0 20
4 2 6 0
F3 0 12 0 18 30
11 12 13 24
z = 109. 3
D1 D2 D3 D4
5 9 4 1
F1 11
3 5 0 8
F2 22
11 12 13 24
242
17.8. OFERTA TOTAL DIFERENTE DE DEMANDA TOTAL 243
D1 D2 D3 D4
5 9 4 1
F1
11
3 5 0 8
F2 22
99 99 99 99
F3 27
11 12 13 24
D1 D2 D3 D4
5 9 4 1
F1 0 0 0 11 11
3 5 0 8
F2 9 0 13 0 22
99 99 99 99
F3 2 12 0 13 27
11 12 13 24
z = 2711.
En realidad el costo mı́nimo de transporte de esta seudosolución es z = 38,
a lo cual habrı́a que agregar el verdadero costo, correspondiente al incumpli-
243
244 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
EJERCICIOS
17.2. Ofertas 10, 11, 12, 13, 14; demandas 9, 9, 9, 9, 24; matriz de costos
unitarios:
6 8 9 6 5
7 10 7 7 6
10 8 8 7 6
.
9 9 7 5 2
10 9 4 3 1
17.3. Ofertas 10, 50, 20, 40, 30; demandas 27, 35, 31, 28, 29; matriz de
costos unitarios:
6 8 9 5 1
5 10 6 2 9
8 8 4 8 6 .
9 2 6 5 2
1 6 4 3 1
17.4. Ofertas 40, 30, 30; demandas 10, 20, 30, 40; matriz de costos unitarios:
11 9 8 7
10 5 6 1 .
4 3 1 0
244
17.8. OFERTA TOTAL DIFERENTE DE DEMANDA TOTAL 245
17.6. Ofertas 20, 15, 10, 15; demandas 18, 19, 23; matriz de costos unitarios:
11 10 4
9 5 3
8 6 1 .
7 1 0
17.7. Ofertas 10, 16, 20; demandas 10, 15, 15; matriz de costos unitarios:
11 10 4
9 5 3 .
8 6 1
17.8. Ofertas 10, 16, 10; demandas 10, 15, 15; matriz de costos unitarios:
11 10 4
9 5 3 .
8 6 1
245
246 CAPÍTULO 17. OTROS MÉTODOS PARA EL TRANSPORTE
246
Capı́tulo 18
ANÁLISIS DE
SENSIBILIDAD
247
248 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
sea óptima.
max x1 + 1.4x2 + 1.5x3
x1 + x2 + 2x3 ≤ 400
x1 + 2x2 + x3 ≤ 580
x1 + 2x3 ≤ 300
x ≥ 0.
Introduciendo variables de holgura y convirtiendo el problema en uno de
minimización se obtiene:
min z = −x1 − 1.4x2 − 1.5x3
x1 + x2 + 2x3 + x4 = 400
x1 + 2x2 + x3 + x5 = 580
x1 + 2x3 + x6 = 300
x ≥ 0.
248
18.1. MODIFICACIONES EN LOS COSTOS 249
y pasa a ser
249
250 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
y pasa a ser
y pasa a ser
donde ckL son los costos iniciales correspondientes a las variables libres en la
iteración k; L0,k es la matriz formada por las columnas de la matriz inicial
250
18.1. MODIFICACIONES EN LOS COSTOS 251
c0LT = c0 L − c0 B Lk
T T
e
c̃0j = c0j − c0 B Akj ,
T
xj es variable libre .
¡ ¢
c̃j = cj − cTB B −1 A0j , xj variable libre ,
£ ¤ 0,k
= −c0 TB B −1 1 L b
¡ ¢
c̃0j = c0 j − c0 B B −1 A0j , xj variable libre .
T
251
252 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
252
18.1. MODIFICACIONES EN LOS COSTOS 253
253
254 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
luego
α ≥ cj − c̃j
α ∈ [cj − c̃j , ∞[.
254
18.1. MODIFICACIONES EN LOS COSTOS 255
Entonces
α ∈ [αmin , αmax ],
donde
−∞
si( akij ≥ 0 para toda variable libre ) xj ,
αmin = c̃j
cβi − min : akij < 0, xj es variable libre ,
−akij
∞
si( akij ≤ 0 para toda variable libre ) xj ,
αmax = c̃j
cβi + min : akij > 0, xj es variable libre .
akij
255
256 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
c̃0L T = c0L − c0 B Lk
T T
£ ¤ £ ¤ −1 −1 1
= −1.5 0 0 − −1.4 0 α −1 −2 1
3 2 −1
£ ¤
= −3α − 2.9 −2α − 1.4 α + 1.4 ≥ 0,
entonces
−2.9
α≤
3
−1.4
α≤
2
α ≥ −1.4
α ∈ [−1.4, −0.9667],
−z 0 = −c0B bk
T
£ ¤ 180
=− −1.4 0 α 80
220
= 252 − 220α
0
z = 220α − 252.
c0 = c + θc̄.
256
18.1. MODIFICACIONES EN LOS COSTOS 257
c̃0L T = c0L − c0 B Lk ,
T T
entonces
donde
c̄˜j = c̄j − c̄TB Akj .
−∞ ½ si c̄˜L ¾
≤0
θmin = c̃j
− min : c̄˜j > 0, xj es variable libre ,
c̄˜j
∞ ½ si c̄˜L ≥¾0
θmax = c̃j
min : c̄˜j < 0, xj es variable libre .
−c̄˜j
Obviamente, el intervalo de variación de θ siempre contiene el valor cero. Al
reemplazar el vector c, por su modificación c̄, se obtiene
−z 0 = −c̄0B T bk
= −cTB bk − θc̄TB bk
z 0 = z k + θc̄TB bk .
257
258 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
De nuevo hay dos formas para abordar el problema: partir de las fórmu-
las generales para c̃0L , o utilizar directamente las fórmulas para θmin y θmax .
c̃0L T = c0L − c0 B Lk
T T
£ ¤ £ ¤ −1 −1 1
= −1.5 − θ 0 0 − −1.4 + θ 0 −1 − 2θ −1 −2 1
3 2 −1
£ ¤
= 0.1 + 6θ 0.6 + 5θ 0.4 − 3θ ≥ 0.
Entonces
θ ∈ [−0.1/6, 0.4/3].
Por otro lado
c̄˜TL = c̄TL − c̄TB Lk
£ ¤ £ ¤ −1 −1 1
= −1 0 0 − 1 0 −2 −1 −2 1
3 2 −1
£ ¤
= 6 5 −3 .
Entonces
½ ¾
0.1 0.6 0.1
θmin = − min , =− ,
6 5 6
½ ¾
0.4 0.4
θmax = min = ,
−−3 3
£ ¤ 180
z 0 = −472 + θ 1 0 −2 80
220
= −472 − 260θ.
Como el coeficiente de θ, en la expresión de z, es negativo, entonces el mejor
valor que puede tomar θ sin que cambie el punto óptimo es θmax = 0.4/3.
3
258
18.2. MODIFICACIONES EN LOS TÉRMINOS INDEPENDIENTES 259
259
260 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
£ ¤ 190
z0 = −1.4 0 −1 60 = −486.
220
Luego las variables básicas en el óptimo siguen siendo las mismas y su valor
cambia un poco; el nuevo punto óptimo es entonces
Ejemplo 18.10. Considerar los datos del ejemplo 18.1, modificando las
disponibilidades de las máquinas por 430, 600, 250.
−1 1 0 430 170
0
bk = −2 1 1 600 = −10 ,
2 −1 0 250 260
£ ¤ 170
z0 = −1.4 0 −1 −10 = −498.
260
Luego las variables básicas en el óptimo no son las mismas. Para hallar la
solución óptima es necesario utilizar el simplex dual:
x2 0 1 −1 −1 1 0 170
x6
0 0 −1 −2 1 1 −10
x1 1 0 3 2 −1 0 260
−z 0 0 0.1 0.6 0.4 0 498
xβσ = xβ2 ,
xs = x6 ,
xe = x3 .
x2 0 1 0 1 0 −1 180
x3
0 0 1 2 −1 −1 10
x1 1 0 0 −4 2 3 230
−z 0 0 0 0.4 0.5 0.1 497
260
18.2. MODIFICACIONES EN LOS TÉRMINOS INDEPENDIENTES 261
0 0
bk = B −1 b0 = bk − b0j (B −1 )j + α(B −1 )j ≥ 0.
Sea S = [sij ] = B −1 .
0
bki = bki − b0j sij + αsij ≥ 0, i = 1, ..., m,
−∞ si Sj ≤ 0,
½ ¾
αmin = 0 bki
bj − 1≤i≤m
min : sij > 0 .
sij
∞ si Sj ≥ 0,
½ ¾
αmax = 0 bki
bj + 1≤i≤m
min : sij < 0 .
−sij
261
262 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
Ejemplo 18.11. Considerar los datos del ejemplo 18.1, modificando las
disponibilidades de las máquinas, por α, 580, 300. Averiguar en qué intervalo
puede variar α sin que cambie el grupo de variables básicas.
180 −1 −1
0
bk = 80 − 400 −2 + α −2 ≥ 0,
220 2 2
αmin = 290,
αmax = 440,
£ ¤ −1
z ∗ 0 = −472 + (α − 400) −1.4 0 −1 −2
2
= −232 − 0.6α.
El valor −0.6 indica que, por cada unidad que aumente el primer término
independiente, el valor de z se incrementa en −0.6 unidades. Puesto que se
está tratando de minimizar z, lo más conveniente es que se incremente lo
más que se pueda la disponibilidad de la primera máquina. El valor de este
precio sombra es válido dentro del intervalo de factibilidad de la restricción.
Si para aumentar la disponibilidad de la primera máquina, la compañı́a
puede alquilar horas adicionales a un precio de $ 0.8 , no valdrı́a la pena
hacerlo. En cambio, si se consiguen horas adicionales de la máquina 1 a un
precio de $ 0.5, sı́ valdrı́a la pena hacerlo. 3
262
18.2. MODIFICACIONES EN LOS TÉRMINOS INDEPENDIENTES 263
Ejemplo 18.12. Considerar los datos del ejemplo 18.1, modificando las
disponibilidades de las máquinas, por 580, 400, α. Averiguar en qué intervalo
puede variar α sin que cambie el grupo de variables básicas.
180 0 0
0
bk = 80 − 300 1 + α 1 ≥ 0,
220 0 0
αmin = 220,
αmax = ∞.
263
264 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
−∞ si b̄k ≤ 0,
½ ¾
θmin = bki k
− min : b̄i > 0 .
i b̄ki
∞ si b̄k ≥ 0,
½ ¾
θmax = bki k
min : b̄i < 0 .
i −b̄ki
0
z 0 = cTB bk
= z k + θcTB b̄k .
180 1.5
k0
b = 80 + θ 2.5
220 −2.5
θmin = −32,
θmax = 88.
264
18.3. MODIFICACIONES EN UNA COLUMNA LIBRE DE A 265
entonces
0
c̃0j = cj − cTB B −1 A0 j .
265
266 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
266
18.3. MODIFICACIONES EN UNA COLUMNA LIBRE DE A 267
xe = x3 ,
xβσ = xβ3 ,
xs = x1 .
x2 0.25 1 0 −0.5 0.75 0 235
x6
0.5 0 0 −1 0.5 1 190
x3 0.5 0 1 1 −0.5 0 110
−z 0.1 0 0 0.8 0.3 0 494
0
c̃0j = cj − cTB B −1 A0 j
a1j
..
.
ai−1,j
= cj − cTB S
α
ai+1,j
..
.
amj
267
268 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
a1j 0
.. ..
. .
ai−1,j 0
c̃j = cj − cB S
0 T
aij − cB S(α − aij )
T
1
ai+1,j 0
.. ..
. .
amj 0
= c̃j + (aij − α)cTB Si ≥ 0.
Entonces α puede variar en el intervalo [0.75, ∞[, sin que el punto óptimo
cambie.
En éste, como en otros casos, se puede hacer un análisis de más alcance
sobre la variación de α. Para valores de α menores que 0.75, entrarı́a a la
base la variable x3 y se puede prever qué pasarı́a. La columna modificada
serı́a
2 α−2
B −1 α = α − 2 .
2 −α + 4
El único elemento positivo es el tercero, luego saldrı́a la tercera variable
básica, es decir, x1 . El valor de z en la nueva tabla estarı́a dado por:
−0.3 + 0.4α
−z 0 = 472 − 220,
−α + 4
o sea,
−0.3 + 0.4α
z 0 = −472 + 220.
−α + 4
268
18.4. UNA RESTRICCIÓN ADICIONAL 269
Luego
θ ∈] − ∞, 0.5]. 3
269
270 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
xj = bkj j = 1, ..., m
xj = 0 j = m + 1, ..., n.
270
18.4. UNA RESTRICCIÓN ADICIONAL 271
fila multiplicada por −am+1,1 , ..., hasta la fila q multiplicada por −am+1,q .
Entonces
q
X
0
bkm+1 = b0m+1 − am+1,j bkj ≥ 0
j=1
Xq
= b0m+1 − am+1,j xkj ≥ 0.
j=1
Luego
q
X
am+1,j xkj ≤ b0m+1 ,
j=1
x1 + x2 + x3 ≤ 490,
y multiplicando por −1
271
272 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
se obtiene una igualdad que se puede agregar a la tabla para que x7 sea
variable básica:
x2 0 1 −1 −1 1 0 0 180
x6
0 0 −1 −2 1 1 0 80
x1
1 0 3 2 −1 0 0 220
x7 −1 −0.5 −3 0 0 0 1 −400
−z 0 0 0.1 0.6 0.4 0 0 472
A partir de esta tabla se utiliza el método simplex dual y en dos tablas más
se obtiene el óptimo:
272
18.5. UNA COLUMNA ADICIONAL 273
Esta igualdad se puede agregar a la tabla para que x7 sea variable básica.
Además, se cambia la fila de costos reducidos por los costos artificiales.
0 1 −1 −1 1 0 0 180
x2
0 0 −1 −2 1 1 0 80
x6
1
0 3 2 −1 0 0 220
x1
−2 −2 −3
0 0 0 1 −780
x7
0 0 0 0 0 0 1 0
0 1 −1 −1 1 0 0 180
x2
0 0 −1 −2 1 1 0 80
x6
1 0 3 2 −1 0 0 220
x1
0 0 1 2 0 0 1 20
x7
0 0 0 0 0 0 1 0
También es necesario calcular los costos reducidos
x2 0 1 −1 −1 1 0 0 180
x6 0 0 −1 −2 1 1 0 80
x1 1 0 3 2 −1 0 0 220
x7 0 0 1 2 0 0 1 20
−za 0 0 −1 −2 0 0 0 −20
Tener una columna adicional significa que hay una nueva variable, por
ejemplo xn+1 y, por lo tanto, se conocen los valores a01,n+1 , a02,n+1 ,..., a0m,n+1 ,
y también el costo cn+1 . La variable xn+1 entra a la tabla como variable
libre con valor nulo. Obviamente, es necesario calcular su costo reducido
para saber si la tabla sigue siendo óptima. Para este cálculo, de nuevo, se
necesita conocer B −1 .
273
274 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
Akn+1 = B −1 A0n+1 ,
c̃n+1 = cn+1 − cTB Akn+1 .
Ak7 = B −1 A07
−1 1 0 0.5
= −2 1 1 0.5
2 −1 0 1
0
= 0.5 .
0.5
274
18.5. UNA COLUMNA ADICIONAL 275
Ak7 = B −1 A07
0
Ak7 = 0.5 ,
0.5
£ ¤ 0
c̃7 = −0.7 − −1.4 0 −1 0.5
0.5
= −0.2.
EJERCICIOS
275
276 CAPÍTULO 18. ANÁLISIS DE SENSIBILIDAD
276
Bibliografı́a
[BJS99] Bazaraa M.S., Jarvis J. J., Sherali H.D., Programación lineal y flujo
en redes, 2 ed., Limusa - Noriega, México, 1999.
[Las70] Lasdon Leon S., Optimization Theory for Large Sytems, MacMillan,
New York, 1970.
[NaS96] Nash Stephen G., Sofer Ariela, Linear and Nonlinear Programming,
McGraw-Hill, New York, 1996.
277
278 BIBLIOGRAFÍA
278
Índice alfabético
acotado, 47 admisible, 47
aditividad, 1 convexo, 27, 35
admisible, véase factible factible, 36
algoritmo del transporte, 183 convexo
análisis de sensibilidad, 247 conjunto, 27
artificial generado, 30
función objetivo, 93 costo reducido
nula, variable, 107 libre nulo, 105, 106
asignación de recursos, 2 costos
modificación, 249
base, 36 reducidos, 59, 60, 200, 237
casco convexo, 30
casos especiales del simplex, 101 Dantzig
circuito, 188, 198, 231 método de descomposición, 47
caracterı́sticas, 191 método simplex, 57
columna demanda total, 240
adicional, 273 desigualdad, 29
básica, 36, 103 determinista, 1
libre, 36 diferentes formas de problemas, 13
que entra, 79 dirección, 32, 42, 101, 106
combinación equivalente, 32
convexa, 29, 47, 50 extrema, 32, 42, 44, 48, 105
estricta, 29 dual
lineal no negativa, 47 del dual, 156
condiciones problema, 153, 156, 158, 200
de optimalidad, 57, 64, 192 dualidad, 153
conjunto débil
óptimo teorema, 158
acotado e infinito, 103 fuerte
infinito y acotado, 103 teorema, 161
no acotado, 105, 113 teorema fundamental de, 163
279
280 ÍNDICE ALFABÉTICO
280
ÍNDICE ALFABÉTICO 281
281
282 ÍNDICE ALFABÉTICO
entra, 170
holgura, 200, 263
independiente, 36
libre, 36, 63, 65, 117, 132, 188
nula, 229
que entra, 80, 88, 107
que sale, 94, 117
sale, 170
variedad lineal, 28
Wolfe
método de descomposición, 47
282