Mathematics">
PLE2
PLE2
PLE2
linea I
Introducción 111
,
lNTRODUCCION .
OBJETIVOS
• Conocer diversas variantes del algoritmo del simplcx. que pueden utili-
zarsc en la práctica en un computador.
CONTENIDOS
2.2 Dualidad
2.2. 1 Defin iciones
2.2. l . I Formas equivalentes
2.2.2 El teorema de la dualidad
2.2.3 Los teoremas de las holg uras complementarias
2.2.4 liI teorema del Lagrangiano
2.2.5 El algoritmo primal del simplex y la dualidad
2.2.6 íntcrprcu c í óo económica de la dualidad
2.2.7 El algoritmo dual del sim plcx
2.2.7. I Fundamentos del algoritmo dual del sim plex
2.2.7.2 Fonna del algoritmo dual del simplcx
2.2.7.3 El método de la restricción en ítícieí
Minim izar ex
sujeto a
Ax b
x > O
Suponemos que A es una matriz m x n, m < n y rango de A = m. Esto quiere
decir que el sistema de ecuaciones no es redundante y que tiene infini tas so-
luciones. Aunque, como es lógico, en los problemas reales esto no tiene por
qué verificarse, veremos que en la práctica no es necesario el cálculo del ran go
de A de forma que esta hipótesis sólo se utili za en Jos desarrollos teóricos.
Supongamos que A = (al .a2, ,u,, ) donde los aj son vectores columna de
m componen tes. Sea B = (aj., ah ' .ai ..) una base de A, es decir una matriz
de rango m extraída de las columnas de A. Los índices que marcan las co-
lumnas de R son los que tien en orig inalmente en A. independientemente de su
ubicación en la matriz B.
d' = (c,)
(~)
x" = (x,) s EI s ~ J
x= xN = (X}) j CC J eN = (c}) j EJ
=
Si en el sistema 2. 1 hacemos :!' = Oresulta BXJ h. Puesto que B tiene inversa
podemos despej ar el vector de variab les JI y obtener
x B = S -lb
(2 .2)
y = (y¡) = (y,¡) s E / , l E }
x" = (x,) sEl
Veamos en primer lugar qué signifi cado tienen los vectores anteriores. Por no-
taci ón, tenemos que B - 1aj = y j por 10 cual
aj = By } = L,YSj Qs
s (/
(2.3)
(2.5)
"'
LJ cSo"'.Y
y +"'LJ cJ·XJ z (2.6)
sE/ jU
Vamos a ex presar la ecuación anterior en func ión de las vari ables fuera de la
base. Para e llo multip licamos el sistema 2.3 por Ji
o eq uivalentemente
z-¿'xI' (2.8)
Mi nimizar Z= X l + X2
sujeto a
x, + 2r, < 4
x, < 1
x, > O
x, > O
La forma estándar es:
Elijamos la base B :-- ( a¡' Q2) , es decir, vamos a despejar las variables .1" 1,.1"2· Si 10
hacemos directamente en el sistema de ecuaciones queda:
es decir
x,
x, =
Las ecuaciones anteriores form an el sistema explícito de restricciones y también pue-
den escribirse como:
- 2
1
Aquf , los vectores Yj y ~ son:
B ... 1- N = b
La expresión anterior nos da el valor de z en func ión de las variables qu e están fuera
de la base. Vemos que los coeficientes de las variables y el termino independiente de la
expresión anterior son, en efec to, los valores que se obti enen al utilizar las notaciones
introducidas antcrionnente. Tenemos que z ¡" ;:- tfly] = (l ,I )(YIJ) , po r lo que z) =-=
n¡
(', 1)(b) = 1, z, - ( 1, ' )( ,2) = - 1 Y por lanto e, -
z, = O - , = - \, z, = e, -
0 - (- 1) = 1. También c Bx8 = ( 1, I )(~) ;:- 3 En resumen LjEA cj - Z])Xj :.= Z - í es
exac tamente la expresi ón que habíamos obtenido - x ) + X4 = z - 3.
El algoritmo del simplcx 119
Demostración
Consideremos el sistema 2.2. Tenemos el programa de base asociado a una
hase B, ~ = ¡B. J!V = Oque proporciona a la función objetivo un valor z Z. =
Supongamos que existe un índice k e J, tal que ZIf - CA; > Oe Yk < O. Asignemos
a la variable Xi un valor cualquiera positivo, digamos a , y a las demás variables
fuera de la base un valor nulo. Entonces el sistema queda JI +YkXII: = ¡/J. Dc
aquí x!1 = jB YkXII: > O, puesto quc jk > Oe YII: < O. Es decir, el conjunto dc
valores: Xi. = Xh xii = xB - YkXk y ~ = Oexcepto para x.. es un programa para
cualquier valor .Q no negativo. Ahora bien, en el programa anterior la función
del objetivo vale Z = Z - (zt - e.t)Xk. Como (ZI; - e¡:) > Oresulta que cuando
Xl -t oo. también z --+ - oo. por lo cual no existe programa mínimo finito.
Minimiza r Z = - X ¡ - 3X2
suj eto a
X, 2.<, < 4
- x, + x, < 3
x" x, > O
En la forma estándar es
N~ ( 1
- 1 B 'N=(-J
- 1
\20 UNIDAD DIDÁ CT ICA 2 Algoritmos de programación lineal
segunda ec uación:
X3 - lO + x ¡ - 2x4
xz 3 + X¡ - X4
X3 10 t- X I
Xz - 3 -jx¡
z - 9 - 4x¡
--Xl = mm
, Xs
- {-
Ylk .f Y\'k
Demost ra ción
A l ig ual q ue en el teorema anterior, consideremos de nuevo el sistema que
se obtiene al anular en el sistema explícito todas las variab les fuera de la base
excepto la variable Xk Y escribamos tos nuevos valores de las variables, que
denotaremos ~, para un valor positivo cualquiera dc -Xk
-, -
X = x» - Y-fk Xk s E l.
s
Por hipótesis, ex iste algún s E J tal que ~k > O. Por lo tanto para algún s
tenemos que ~ será menor que xs ' Ahora bien, como las variables no pueden
ser negativa." ~ será un programa en tanto en cu anto que ~. X s - Y skXk > O. =
Por tanto Xk no puede aumentarse indefinidamente sino que
xk ~ mm
, {x, _.
s Y.d
El algoritmo del simplex 121
y,¡ > O}
=
ya que así, efectivamente X't O. Los restantes ~ . s E / - {e} tendrán un valor
no negativo. Además los vectores H = (( aS)Sf l - {l) ak) forman una base ya
que al = ¿ j O Y sl Qs y el escalar YlA: que multiplica a la columna tl(. que es la
que hemos intercambiado con la lt. es no nulo y estas dos condiciones son
necesarias y sufi cientes para que el nuevo conjunto de vectores considerado
siga siendo una base. Obtenemos entonces un nuevo programa en el cual to-
das las variables asociadas a vectores que no pertenezcan a son nulas. El n
nuevo programa es un programa de base asociada a 11. Adem ás, en este nuevo
programa la función objetivo vale
~
Z = -z - (Zi )- - x,
-Ck X,t =Z - (Z¡ -q) - <z
y"
en donde la última desigualdad es consecuenc ia de que (2k - q ) > Oy f:¡ ~ O.
La desigualdad será estricta siempre y cuando a i= O en cuyo caso será es- z
trictamente menor que z .
B - B ' _- [- 1/ 3
2/3
1/3]
1/ 3
122 UNIDA D DID ÁCTICA 2 Algoritmos de programación lineal
Fi~tJ ra 2.1
Las expresi ón anterior nos indica que hacer crecer la variable x 4 desde su actua l valor
nu lo hasta un valor positivo es favorable para la m inimización, ya que por elida unidad
que au mente Xol la función objetivo disminuye en ~ unidades. Por tanto, es buena
decisión introducir .\"4 en la base, lo cual implica que hay que recalcular [as demás
variables de la base. La otra variable no básica x ) se sigue dejando en su ac tual valor
nu lo . Entonces el sis tema de ecuaciones queda:
4 I
x, - - - - X4
3 3
\0 1
- - - -X4
" 3 3
Observemos que 110 es posible aumcntar xa sin límite, ya que llegarla un momento en
que Xl y X2 seria n negati vas. 1.0 más que puede aumentar la variable X4 sin que las
variab les XI YX2 sean negativas se ca lcula fácilmente. 11a de ser:
4 1
Xl = - - - X4> O
3 3 -
10 I
-3 - 3- x, >
-
O
Entonces es claro q ue
4
x4 < ~ =4
ro
X2 < ~ ~ 10
3
El algoritmo del simplex 123
por lo cual X4 < Mínimo {4,lO} =-= 4. Si tomamos X4 - 4 resu lta que XI = O Y x 2 -
I 4 -- 6'J - 2 . Oh tenemos un nuevo programa
10 - J'
"]
Xl -= 0, X2 = 2, X3 = 0, X4 =4
que verifica todas las restricciones y además proporciona a la función objetivo un va lor
igua l a
2 4 1 2 1 2 4 2
z = - - t- - x l - - X4 """ - - + 0- -· 4 = -- - - =- - 2 <
3 3 33333 - 3
Demostración
Necesidad:
Es consecuencia inmediata de los teoremas anteriores. En efecto, si para
algún j E: J ocurriese que z} - ej > O, o bien no habr ía solución finita, teore-
ma 2.1, o bien seria posible mejorar la solución. teorema 2.i- .
Suficiencia:
Supongamos q ue Zj - ej < O para todo j e: J . Veamos que el programa es
óptimo. La ecuación ¿ (el' -Zl'}xJ = z - z es váli da para toda solución del
j E!
sistema de ecuacio nes Xs + L J-rj Xj = X.H s E t , Las variables en la función ob-
jE!
jetivo son ahora Xj y z ya que los demás términos son conocidos una vez fijada
la basc B. Ahora bien, como Zj - Cj < O si tratamos de calcular el mínimo de
z sujeto a que Xj > O que es un condición obligada paro ser un programa, ob-
servamos que el mínimo se alcanza paraxj = O.j E J . es decir, en el programa
actual. Si todos los Zj - Cj son estrictamente positivos el mínimo es único. pero
si existe algún Zj - ej = O es posible que ex istan otros mínimos.
Xj >O
2Aqui hay que d~'lC8~~r la ~bilidad de ciclaje que puede darse cuando hay degeneración.
Analizaremos esta suuacron mas adelan te
124 UN IDA D DID ÁCTI CA 2 Algoritmos de programación lineal
Demostració n
Trivial.
Demostración
Trivial.
siendo -
Xl
Yik
.
= "llll
{-
Xs
Y sk
Paso 3: Calcular:
J ¡ ={j EJ I ( Zj-Cj» O}
I z, - ct 1
= Máx {I Zj - Cj 1, j e J I } Crucrío de entrada
Xt • {i,
- =M m - ; Ysk >O, Criterio de salida
Y ik Ysk
Alrededor del pivote gira el proceso de act ualización de las iteraciones. Para
obtener la nueva expresión del sistema son necesarias dos tipos de operaciones:
una para actualizar la ecuación de las variables entrante- saliente, o ecuación
del pivote, y olea para actualizar cl resto de las ecuaciones, incluida la ecuación
correspondi ente a la función objetivo. Observemos que la ecuación del pivote
inicialmente tiene índice f y después dcl cambio de hase tiene índ ice k.
Consideremos el sistema en la forma explicita e; + ¿ j f"JYsjXj = i s , s E J.
e
La ecuación de índice de este sistema es:
Xt +YlkXk + L Y tjXj = X l
jf'J -- {k}
XI
Xs +Ysk
(
'- "¿. Ylj
- Xj + -Xf ) + "L _
YsjXj = Xs s U - {E}
Yik JO {k} Ylk Yek jE.I-{k }
El algoritmo del simple, 127
y..
x ,J - - Xt + ~
~ (YJk -Yl¡
-Y.fk) Xj = xs
- - Y.'-
- X[ s f= / - {l} (2.13 )
ya j~J {.t} n« Y lk
En definitiva, de las ecuaciones 2.12 y 2.13 deducimos que los nuevos coefi-
cientes del sistema, es decir, los nuevos elementos de la matri z Y son:
Y i}
Y.¡ - -Y., con s c J -{l} = ¡' -{k} (2 .14)
Ytt
_ Yi )
(2.15)
Ytt
Estas fórmul as son válidas para todo j E {1, 2, . . . ,N} como se puede compro-
bar fácilmente. En particular, vamos a escribir las que corresponden al índice
j = l . Paras E r-
{k } las ecuaciones son
, yu Y sk
Ysl =Y.,t -
Y ik
Y,d:= - -
Y t4
ya que Yst = O e vu = I paras 1= f. porque Xi está en la base actual y por
consiguiente el corres po ndiente vector tiene todos sus elementos iguales a cero
salvo el que ocupa cllugar f. que es l . Por la misma razón, en la nueva ecuación
de indice k los coeficientes son:
J ru 1
Yu = YJI - - YJA: = -
Ytk Ya
Los segundos miembros de las ecuaciones 2. 12 y 2.13 proporcionan las
fórmulas de transformaci ón de los X;... (s E JI)
-,
X, x,, -
Xl
- Ysk s E f' -{k} (2. 16)
y"
Xl
X\. (2.17)
y"
Al igual que antes las formulas anteriores siguen siendo válidas para s =l ya
que
-4 _ Xl
xl =xl - -r-yn =O
Ytt
lo cual es lógico porque Xl sale de la base.
Recordemos ahora que la funci ón del obj etivo venía dada en forma expl icita
por L JEJ ( CJ - Zj ) = z- z. Sustituyamos aqul el valor dc .q que se obtuvo antes
al despejar la variable.
Al reordenar queda
y,.
(i¡--e¡) - (z¡- e¡) --!.(z¡ - e¡) j = I •. . .• n; j er (2.18)
YIk
, ~ Xi
i - z - - (Z¡ -Ck ) (2. 19)
YIk
En la ecuación 2. 18 se ha puesto qu e la expresión es válida para todo j E J .
En efecto as i cs. Para j f =
Z; - e, = (z/_ e,) _ Ytt (Z¡ _ e¡ ) = _ Z¡ - ek•
YIk ylk
=
ya que Zt - el O e vu = 1 Y esta es la expresión que tiene en la f6nn ula 2.18.
Una observación detallada de las fórmulas 2.14 - 2.19 revela que tienen
todas una estructura común que permiten resumirlas en dos reglas que son
válidas para todas las ecuaciones y todas las variables, inciuida la variable z
del objetivo.
FÓRMULAS DE Proposición 2.1 Las fórmulas de ca mbio de base paro realizar la ope-
CAMBI O DE BASE ración de pivollij e son:
YI¡
- Y sj - - Ys! s E / -{t) +{O); j EN +{Oj (2.20)
YIk
YI¡
j EN +{Oj (2.2 1)
YIk
CI C, .. .. .. C, · .... . Cj • • • • • • Cn
XI X, ·.... . X.• •• • • •• Xj • • • • •• Xn
cas, es decir, los valores del programa básico correspondiente o lado derecho
de las restricciones. En ocasiones se añade una columna adicional en la que
se ponen los cocientes entre la columna de valores de las variables básicas y
los correspondientes elementos de la columna de la variable entrante, supuesto
que éstos últimos son positivos; estos cocientes son necesarios para el criterio
de salida del simplex. Esta disposición admite diversas variantes. En ocasiones
sólo se escriben los coeficientes originales de la función obj etivo en la tabla
inicial. También la fi la correspondiente a la [unción objetivo puede colocarse
en último lugar. Incluso, en lugar de los coefic ientes Zj - Cj pueden colocarse
sus opuestos Cj - - Zj . Asimismo, la columna dc los valores dc las variables de
la base puede ponerse a la derecha de la tabla.
EJEMPLO 2.4 Vamos a encontrar la so lución óptima del siguiente prob lema de pro~
gramaeión lineal medi ante el algo ritmo del simplex.
Tabla inicial
O O O - 107 - 1 -2
x, x, X3 x, Xj x,
z (J O O O 107 1 2
O x, 7/3 1 O O t4/ 3 1/3 - 1/ 3
O x, 5 O 1 O 16 1/ 2 -2
O X3 O O O 1 3 O O
La info rmacióu recog ida en la labia nos d ice cuáles son las variables básicas, x l . X2
y ."3, los va lores del progmmu b ásico, Xl = 7/ 3• .t 2 = 5, Xl =
0, .1'4 = O, .'fs = O Y
}¡:, = O Y el valor de a en d icho programa básico z = o . Co menzam os la ejec uc ión
del algo ritmo de acuerdo con el esquema del apartado 2. 1.3. 1. El cálculo de la ma triz
=
y 0 - 1N es elemental puesto que la ma triz 8 es la identidad y po r consiguiente
r = N, es decir, para escribir la matriz Y en la tabla simplemente tenemos que po ncr
los m is mos número s que fi guran en el sistema origina l. Calculamos ahora los z j - e j .
Para ello es (u il poner el vector eH en la primera co lumna de la tabla. Asl, Z j se calcula
fácilmente a l multiplicar cscalar mcntc este vector por las columnus y J para cada j E J .
En este caso J = 4,5 ,6 y entonces
z, = e H y, ~ (0,0, 0) t 4136/ 3 ) = 0
(
El algoritmo del simplcx 131
1/ 3 )
z, =t! y, = (0, 0, 0) I /~ = O
(
- 1/3 )
H
Zo - c Yo = (0, 0,0) -~ - O
(
Entonces:
-113) <
a dichos valores positivos. Vemos que la columna yg =
( ~2 Ono tiene valores
Xl + 3x, - O
Tabl a inicial
O O O - 28 - 1 - 2
x, X2 x, x, x, Xo
z O O O O 28 1 2
O x, 7/3 1 O O 14/ 3 113 1/3
O X2 5 O 1 O 16 112 - 2
O x, O O O 1
0 O O
gxaminamos los coeficientes Z j - Cj para las variables fuera de la base. Los val ores
son Z4 - C4 = 28 , zs - es = I Y Z6 - Có -= 2. Entonces J I = {4.5, 6} Y las variablcs xa,
Xs Y.1:6 son candidatas 3 entrar en la base. Seleccionamos la variable entrante mediante
el criterio de entrad a del simp lex. Para ello hay que calcular
de salida. Ello exige ca lcular los coc ien tes entre los elementos de la columna en que
fi guran los valo res de las variables que están en la base y los elementos de la co lumna
de la variable entrante. restring iendo el cá lculo a los elementos de esta última columna
que son es trictamente positivos. L, variable sa liente será aquella para la que se obt enga
el cociente mínimo. Tenemos
Iteraci ón 1
x, x, x, x, x, Xó
z O O O 28/3 O 1 2
O x, 713 1 O - 14/ 9 O I!J @
O x, 5 O 1 -16/3 O 1/ 2 - 2
-28 x, O 6 O 1/3 1 O O
Z - 14 - 6 O O O -1 O
-2 X6 7 3 O - 14 / 3 O I I
O x, 19 6 1 - 44/ 3 O 5/2 O
-28 x, O O O 1/3 1 O ()
Al examinar ahora la fila de los Z j - ej encon tramos que todo s son menores o ig uales
que cero. Entonces hemos llegado a la situación denominada Paso 4. 1. El programa
actual es u n programa óptimo . Los valores de las variables y la función obj etivo son:
•
L. a ijxj = b, i = l , .. . , p
j ~ m - pl l
•
Xi _p + L. u ijXj h¡ i =p +l , . . .•m
j =m -pi 1
con b¡ > O
Las variables XI ,Xl • . • • ,Xm _ p son las variab les de ho lgura. A fin de obtener una
matriz un idad de dimensión m se añaden p vectores unidad a1 sistema. cadn
uno de ellos asoc iado a una variab le xl , ~ .... . x:.
que se llamaran var;~l b/cs
artificiales. El sistema queda:
•
xf +
j
L
m- p i 1
a ijxj - h, i = l , .. . ,p
•
Xi _ p +
j
L
m -p + 1
a ¡jXj - h, i =p +l, .. .•m
co n h, > O
Sea A' la matri z original del sistema en forma can ónica, o sea antes de intro-
ducir las variables de holgura
El algoritmo del simplex 135
O O I Mxm
X',x > O
La matriz AO contiene, eviden temente, una submatriz de rango m. por lo que ya
se cumple la hipótesis sobre la matriz del sistema que se utilizó en los apartados
anteriores al hacer el desarrollo teórico de l algoritmo del simplcx. Además, la
solución evidente
.t: = bl • . . . X; = bp • •t"J = bp + 1• •• • xm - p = bm
constituye un programa inicial de base. El prob lema original queda transfor-
mado en un nuevo problema denominarlo problema aum entado.
PROBLEMA Definición 2.3. Se denomina problema aumentado al siguiente problem a:
AUMENTADO
Minimizar z = ex
sujeto a
.1",., > O
Hemos conseguido form ular un problema que verifica todas las hipótesis que
hab íamos exigido en el método de l simplex. Resta por ver cómo están relacio-
nadas las soluciones de este problema con las soluciones del problema original.
La relación es simp le y se expresa a continuación.
Dem ostración
Consecuencia inmediata de las definiciones.
Se trata entonces de idear al gún procedimiento que nos cOIu h IZC.¡ a un pro·
grama del problema numcumdo en el cual todas las variables artifi ciales lomen
el va lor cero. En ese momento tend remos un programa del probl ema original y
pod emos abandonar las variables artificiales. Estudiaremos dos métodos para
conseguir esto: el método de las penalidades y el método de las dos fases.
p •
Minimizar z= M L X! + L CjXj
i=1 j=1
Hay que hacer notar que en el caso de q ue el problema origi nal fuese un
problema de maximlsaci ón, entonces habría que introducir las variables artifi-
ciales en la función objetivo multiplicadas por un coeficiente - M. donde M es
un número po sitivo arbitrariamente grande, siempre mayor quc cualquier otro
número con el cual se le compare en el transcurso de los cálculos del algoritmo
dcl simplcx. Por esta razón, el método se llama también m étodo de la gran M.
Los resultados sig uientes son evidentes:
El algoritmo del simplex 137
d) Todo programa del prob lema aumentado que no contenga variables arti-
ficiales estrictamen te posi tivas es un programa del problema original.
EJEM PLO 2.6 Cons ide remos el siguiente p roblema de programación lineal:
A primera vista no se encuentra una base por 10 cual se crea artificialmente introdu-
ciendo las variablesxj • .xi y xj. El problema penalizado es:
J
JXI -txz c2x, +4X4 -1 lXj +x. ü~ - 2
XI. X2. X). X4 . xs. 4. XI' xj, xl > O
Tabla ¡nici!!1
1 2 O I 5 M M M
z
,,
"
11M - 1
.Q
11M- 2
.Q X<
4M -1
"
2M - 1
',. ..: ..: 4
M ..:..;
'M
,• -, 'M
I I 1
3M .. 5 O
1
O
O
O
O
-1 /3 - 1 1/2
M
M 4 2
0 -1 z ,1
1/2
O O
O
1
O
O
1
Ilcraci6n 1
,
'1
" " X<
"
I
O -, -,
, e"
M 1
M ..; , /3 - 7/ 3
" O
- 213 1 - 213
1 21) - 1/ 3 2/,
'13
.jI ]
1/ '
I / t, "
'1
"' O O
"' -
El algoritmo del simplcx 139
lteraci6n 2
X, x, X. x1 x'1
M
2
'Í
,"
O
XI
O
O
O
O 3
Xl
-3M- ~1 -9M-1'
X4
-9
1
J
O
,
J
O
O
¡
-M + 7
O
-3M "
-2
-!f
2
1
x,
XI
5
,
7
O
I
1
O
-7
,s
-5
-,1 ¡, -2
1
l
O
O
3
1
-2
,
1
La única variabl e artifi cial que permanece en la base tiene valor nulo. Adem ás
todos los coeficientes de los términos en M de la primera fila son negativos o nulos.
Así pues hemos termi nado la primera etapa. El programa
X2 = 5;
Iteración 3
Si se desea. a part ir de ahora se pueden eliminar las tres ultimas colum nas ya que
no SOI1 necesarias. Al seg uir aplicando el algoritmo vemos que Z6 - C6 = ~ > O e
Fase 1
A" C~ ) - b
.\ .(1 , .r > O
Se verifica que:
La primera fase consiste pues en reso lver el problema auxiliar hasta que se
llegue a u na de las situaciones siguientes:
El algo ritmo del simplex 141
Fase 2
Minimizar
suj eto a
3x, +Xl - 3
XI t- X2 +x; ~ -12
X2 + X3 .¡.tj ~ 4
.t1, ~ ,xj > O
El algoritmo del simplex 143
- - --
PR IMERA FASE:
Las tablas del simpl ex de las iteraciones de la primera fase son:
labia inicial
O O O O O 1 1 I
x, x, X, X4 X, xf x'i x'j
í 19 2 - 1 2 3 O O O O
I .r¡ 3 3 O I O - 1 I O O
I
I
4
x'j
12
4
I
O
- 1
I
O
I
0O O
I
O
O
I
O
O
1
Iteración I
X, x, X, X4 x, .r¡ 4 .r¡
í 7 3 I 2 O O O - 1 O
xf 3
X4 4
0
- 1/ 3 - 1/ 3
O 1
O
O
1
- 1
O
I
O
O
113
O
O
x'j 4 O 1 I O I O O 1
Iteraci ón 2
x, x, X, X4 X, .r¡ 4 x'j
í 4 O I I O I - 1 - 1 O
x, I I O 1/ 3 O - 1/ 3 1/3 O O
X4 13 /3 O - 1/3 1/9 1 - 1/ 9 1/9 113 O
x'í 4 O I 1 O
CD O O 1
Iteración 3
x, x, x, .... x, xf x'i x'j
í O O O O O O - 1 - 1 -1
x, 7/ 3 1 1/ 3 2/3 O O 1/3 O 1/3
X4 43 /9 O - 2/ 9 2/9 I O 1/9 113 1/9
x, 4 O I 1 O 1 O O 1
Puesto que S = Ohemos llegado al final de la primera fase. Como no hay ninguna
variable artificia l en la base estamos en el caso a). Disponemos de un programa básico
del problema original.
S EGUNDA FAS/i:
Como ya no necesitamos las columnas correspondientes a las variables artificiales
las excluimosde los cálculos. Tenemos que calcular los coeficientes Z j - ej correspon-
dientes a la función objetivo original. Esta función es z = 3x I + 2.r2 + x} ·1 x,. + 5x:¡
y se trata de un problema de maximizaci ón, Podemos considerar la función - z _
- 3 x l - a 2 - X ) - .(4 - SX5 y plantear un problema de minimización. La tabla es:
144 UNIDAD DIDÁ CTICA 2 Algoritmos de programación lineal
Iteración 4
-3 -2 -1 -1 · ·5
X, x, x) x, x,
e
x,
- 2'1.(1/ 9
7/3
O - 34/ 9 - 56 / 9 O O
-3 1 1/3 2/3 O O
- 1 x, 4319 O - 219 2/ 9 I O
·5 x, 4 O 1 1 O 1
-
Puesto que todos los coeficientes Z j son menores o iguales que cero, la solu-
- ej
ción actual es la solución óptima. Los valores de la variables son x I = 7 /3, X2 =- O.
XJ = O, x. -= 43 /9, X5 =-- 4 que proporcionan un valor - z =- ~286 /9 o 10 que es lo
mismo z = 286 /9 que es el máx imo buscado.
DEGENER AC iÓN Definición 2.6. Se dice que un programa básico es degenerado cuando los
valores dc una o más variables básicas son cero.
Demostración
Trivial.
C uando hay degeneración la función del obj etivo puede tornar el mismo
valor en dos iterac iones sucesivas. En particular, supongamos que en una itera-
=
ción dada a.t es el vector que entra en la base y sea -»* > O y Xl O. Entonces
El algoritmo del simple. 145
sujeto a
x, + fX4 - 8.rs - .16 1 9X7 = O
+ 2.14 - la s - ~X6 + 3.17 = o
XJ --/ .16 = 1
X, • .12, x) • .14. Xs. x(" .17 >o
Aplicamos el algoritmo del simplex de la forma habitual. Obtenemos la secuencia de
iter aciones siguiente:
Tabla inicial
O O O - 3/ 4 20 - 1/ 2 6
X, x, X, x, x, X6 x,
z O O O O 3/4 - 20 1/ 2 -6
O
O
x,
x,
O
O O
J O
1
O
O
8 1/2
-8
- 12
- 1
- 1/ 2
?
3
O X, 1 O O 1 O O 1 O
Iteración I
X, x, X, x, x, X, x,
z () -3 O O O 4 7/2 - 33
- 3/ 4 X4 () 4 O O 1 - 32 - 4 36
O x, O -2 1 O O
0O 3/2 -1 5
O X, 1 () O 1 O 1 O
Iteración 2
X, X, xJ x, x, X, x,
z O - 1 () () () () 2 - IX
- 3/ 4
20
X4
Xs
()
O
- 12
- 1/2
X
1/ 4
()
O
1
O
O
1
0 - X4
3/ X - 15/ 4
O X) 1 O () 1 O () 1 O
146 UN IDA D DIDÁCTICA 2 Algoritmos de programación lincal
Iteración 3
XI x, X, X, x, X6 x,
z O 2 - 3 O - 1/ 4 O O 3
- 1/ 2 x, O - 3/2 I O 1/ 8 O 1 - 21/2
20 x, O 1/ 16 - 1/ 8 O - 3/ 64 1 O
0 1~
O x, 1 3/2 - 1 - 1 - 1/ 8 O O 21/2
Iteración 4
XI X, X, x, x, X6 x,
z O 1 - 1 O 1/2 - 16 O O
- 1/2 X6 O 0) - 6 O 5/2 56 1 O
6 X, O 1/ 3 - 2/ 3 O - 1/ 4 16/ 3 O 1
O x, 1 -2 6 1 5/2 - 56 O O
Iteración 5
XI X, x, X4 X, X, X,
z O O 2 O 7/ 4 - 44 - 1/ 2 O
XI O 1 - 3 O -5/4 28 1/ 2 O
X, O O @ O 1/6 - 4 - 1/ 6 I
X, 1 O O 1 O O I O
Iteración 6
XI X, Xl x, x, X6 x,
Z O O O O 3/ 4 - 20 1/2 - 6
XI O 1 O O 1/4 - 8 - 1 9
x, O O 1 O 1/ 2 - 12 - 1/ 2 3
Xl I O O 1 O O 1 O
Minimizar z = ex
suj eto a:
A. = b
. >0
siendo A una matriz m X n de rango m. Como el método del simplcx siempre
comienza por la matriz unidad como matriz bás ica, supongamos por simplifi-
car las notaciones que esta matriz inicial B =
1m. está formada por los m pri-
meras co lumnas de A. Para prevenir el ciclaje se aplica el método del simplcx
utilizando un criterio de salida modifi cado.
Dada una solución básica factible con base B supongamos que la variable
no básica seleccionada para entrar (..'11 la base por el criterio de entrada es la
variable XA;, es decir;
a) Calc ular:
Mínimo {y"X.l' I Ysk > O, sE l}
• Si este mínimo es único y se obtiene para s = l entonces hacer salir
de la base la variable Xi.
• En caso contrario, sea:
/1 ={ r E/ [ X'
Y,k =
M' { X'
In YSt I y,. > 0, so}}
b) Calcular ahora
'
M In {i',1
-
Y,k
, s E !) }
• Si ~stc mínimo es único y se alcanza para s = l , entonces hacer
salir de la base la variable Xi.
14M UNIDAD DIDÁCTICA 2 Algoritmos de programación lineal
Ij = {r E: Ij _ t I Yr j-l
Y rk
= Mío { Ysj¡ .
Ysk
s(; IjI}}
El hecho de que B' sea de rango máximo implica que no puede tener dos
fi las proporcionales y por lo tanto los empates han de romperse a lo ma s
tardar después de hacer las operaciones anteriores (m + 1) veces. Por
tanto, este procedimiento proporciona un mínimo del criterio de salida
único.
Tabla inicia l
O () () - 3/ 4 20 - 1/ 2 6
XI X, Xl x, x, X6 X7
O X, O O I O @ - 12 - 1/ 2 3
O Xl 1 O O I () O 1 O
Iteració n I
O O () - 3/ 4 20 - 1/ 2 6
XI X, Xl x, x, X6 X7
Z () () - 3/ 2 O O -2 5/ 4 - 2 1/ 2
O .\:1 () 1 - 1/ 2 O O -2 - 3/ 4 15/2
3/4 x, O () 2 () 1 - 24 - 1 6
O Xl 1 O O 1 O O C0 O
El algoritmo del simplex 149
Iteración 2
x, x, X, X, X, X, X,
z - 5/ 4 O - 3 /2 - 5/ 4 O - 2 O - 2 1/ 2
.l , 3/4 I - 1/2 3/4 O -2 O 15 /2
X, 1 O 2 1 1 - ·24 O 6
X, 1 O O I O O I O
EJEMPLO 2.10
• Los vectores (0,2, - 1,3), (2, 1,- 3, 1), (O,O, 1, - 1) son lexicográficamente po-
sitivos.
• Los vectores (- 1,1,2,3), (O,O,O, O), (0,0, - 2, 1) no son lexicográficamente po-
sitivos.
Demostración
a) En la iteración de partida se tiene B = l , J!l = b > O. Por tanto en la ite-
ración original ~ada ~cclor de la matriz ti' ,B- I) = (b,J) >- O, es decir,
es un vector lexJcografi camcnlc positivo.
150 UNmAD DIDÁ CTI CA 2 Algoritmos dc programación lineal
XI Xj x~ XIII+! x. x.
z z ZI - el 'j ej ... z'" - c", Zt -Cl • •• z" -e"
Xj , Xj, Yil l • •• • •• • •• YJ... Yjl! • •• Y j¡n
• •
• • •• • • ••
x, x, Y>1 Y'j y,. • •• y,.
••
••• • ••
Xl Xl YlI Ylj
e YIA
• ••
Xj ... Xj", Yi",l Yjm] Yj.m ••• J'j . l • •• Yi. n
XI Xj • •• X. x•
t z- Xl (ZA;
y"
_q ) (ZI -ej) - ~; (Z.l; - Ci ) ... o (Zn-Clf )-~~ (Z~ - C,t )
XJo .. . ... .. . •
• o
•
• ... ...
•
X, .f~ !.L Y.•(
- y"
f!I.
Y .' ) - YIIY.1k
•
• ·.. ... ... •
•
Xl k
y"
.. . ! t.¡
y"
1
...
Xi'" ·.. o
• Supongamos s rt 11·
• Consideremos el caso en que Ys1 < O. La fila s después del pivotaj c
viene dada por:
_ ,Ysl • . . . ,Y.fm) - Y'k
(Xs (_
- - Xt,Yt ]. · · · ,y (",
)
Ylk
Ahora bien, los vectores:
• Supongamos s E J¡.
En este caso se tiene que Y.tk > O, X,s - Xl ;:' = O ya que es uno de los
índices en que se alcanza el mlnimo. De nuevo consideremos dos casos.
• s (/ h.
i'U < h!. por lo que Y,sl _ .w.YJk
Entonces YtI > O y de nuevo el vector
y.k Ytl
es lexicográficamente positivo.
• s (;. 12 ,
Aquí consideramos de nuevo dos casos, s E 1J 6 sr¡. 1).
Siguiendo de cste modo, al cabo de a 10 sumo ni + 1 p ' ISOS. se llega
a la conclusi ón de que el vector es lexicográficame nte positivo. Po r
tanto (xH' ,B' 1) >-- Opor fi las que es lo que teníamos que probar.
Demostrac ión
Es claro que el vector
Demostración
Por contradicci ón, supongamos que se tiene una sucesión de bases:
(C.BjB~J i b• cEJBe')
J - ( C;Rj+l
- ]+ B Ci 1 b' c8j+ 1 B·~
} -I1 I ) r~ O con J' = l , 2 , ... , t - l
Demost ración
Trivial, pues sólo hay un número finito de bases.
Dualidad 153
2.2 Dualidad
2.2.1 Definiciones
Consideremos el problem a de programación lineal definido en el aparta-
do 1.2.
=
Introducimos las sigu ientes notaciones: ,Al' { I, 2, .. . , n] , .JI = { 1, 2, . .. ,m},
.Aí = {l,2, ... ,q }, ,.h", = {q+ l,q + 2,.. . ,n} = JV - .Aí, Al, = {p + l ,p +
2, ... ,m} = A -Afl • Consideremos también un vector de m variables J =
(UI , uz. · · " um ) y una variable w. La definición siguiente introduce la noción
de par de problemas duales de programación lincal.
154 UNIDAD DIDÁCTICA 2 Algoritmos de programaci óo lineal
L QijXj > b;
jC%
Xj cualquiera j E .%, L
¡(JI
{lil ft ; = ej
Minimizar Z =X ] + X2+ X ]
sujeto
x, 3x, + 4x, - 5
X, x, < 3
2.<, Xl >
- 4
X, > O
X, > O
X, cualquiera
Maximizar w = >--, b. u¡
Minimizar z = L. CjXj ,cd
j~ .A '
lltlj < ej j E .AI"
tu x > !Ji i E ./I)
11, > O ¡ E .-If ,
a ix = b¡ i E ''//1
'-"lJ:Jh¡uicr.J i E ./f,
"i
X¡ > O j E.A '
FORMA CANÓ N ICA Definición 2.10. La forma canónica de la dualidad se obtiene a punir de
DE LA DUALID AD la fonna general suponiendo que ..1/1 y .A" I son vacíos, o sea:
M inimizar z = ex Maximizar w = ub
le Ax > b tt; uA < e
X > O u > O
FORM A ESTÁNDAR Defi nición 2.11. La forma estándar de la dualidad se obtiene de la forma
DE LA DUALIDAD general suponiendo que Al¡ y JY' I son vec íos.
Min;m;7.ar z = ex Maximi7.ar w = u b
le Ax - b tt, uA < e
X > O u cualquiera
Las formas mixta, canónica y estándar son tan generales como la forma
general, por lo que cualquiera de ellas puede tornarse como definición de par
de problemas duales. En efecto, es cl aro que a partir de la forma general puede
deducirse cualquiera de las otras tres sin más que hace r las co nsideraciones
oportunas. Para ver la equivalencia, sólo hay que demostrar que si la dualidad
se define med iante una de las formas mixta, canónica o estándar. es posible
deducir la expresión / / del problema dual de un problema dado bajo la fonna
general /. Esta demo straci ón se basa en las tres cons ideraciones siguientes :
PRIM AL
Variables XI ~ OX2 > 0 x:•. .. •X ¡, . • . ,Xn > O Relación Constantes
"
EJEM PLO 2.12 Consideremos de nuevo el ejemplo 2. 11. Veamos cómo son su for-
ma canónica y su forma estándar.
• Fo rme Canónica
• Primal.
Sustituimos la variable X 3 que tiene signo cualquiera po r la d ifcrcncia de
d~IS vari?blcs no negativas, X 3 :-:: xt -
xl' Además, cambia rnos la rcstric-
ción de Ig ua ldad por dos restricciones de desigualdad . Resulta:
• Dual.
Las restricciones son :
- 4u t + 4u l + "J < - 1
+ I/j". 112. "J > O
"1 •
- 3 Ul
", +
'"
+ 2,,)
<
<
1
1
4", '" "J < 1
- 4u I r "J < - 1
cua lquiera
"' > O
'" "J > O
• Fonna es tándar
• Primal.
Consideramos de lluevo la sustitución de la variable .oC ) por x j - xi" .
Además, a (as restricciones de dcsiguntdad le añadimos sendas variables
de holgura, xf y x~. con el signo correspondiente.j unte con las condicio-
nes de que d ichas variables sean no negativas. Las restricciones loman 1:1
forma
• Dual.
Las restricciones del dual son
u] ·1 u' , <
- 3u¡ u'a + 2U3 <
4u ] U3 <
- 4U1 + U3 < -1
u'a < O
U3 > O
Maximizar w ;- 5u I - 3U2 + 4u ]
sujetoa
u] u, < I
- 3u l + u, + 2U3 < 1
4u] u, I
u, > O
U3 > O
u] cualquiera
Minimizar z = ex Maximizar w = ub
sujeto a sujeto a
I Ax > b If
uA < e
x > O u > O
160 UNIDAD DIDÁCTICA 2 Algodono, de programaci ón lineal
a ¡x > b¡ y u, >
- 0
Demostración
Puesto que x y u son programas, utilizando 1 y 11 se puede escribir
cx >uAx >ub
Demost ración
Observemos en primer lugar que la condición ex < ü b ya impl ica ex =u b
sin más que tener en cuenta la proposición 2.5. Supongamos que k no fuese
x
óptimo. Entonces ex istiría un programa tal que
e~ < ex < ub
lo cual está en contradicción co n la proposición 2.5. Un argumento análogo,
puede aplicarse a u. Si este programa no fuese óptimo existiría-u tal que
ub >u!J =ex
contradiciendo de nuevo la proposición 2.5.
Dual Primal
;~I'-u-
,- dominio de w ~M~áx
"""-"
, dominio de z ---+~
-e-e Min z o válor
fi nito finito
Flgura 2.2: Posici ón relativa de Io.~ valores de la función objetivo en un par de problemas
duales.
Kx > O
X > O
tiene una solución x que verifica Ki +'j > O.
Demostrac ión
Utili...taremos el corolario 1.7. Con las notacion es del citado corolario pon-
gamos AT = K , e = e, = (O•. . . , 1, .. . ,0), donde el 1 ocupa el lugar i, Entonces
A = K T = - J:. Si designamos por klla fil a ¡-si ma de K siempre va a existir
una solución i tal que k¡X' + ~ > Ocorno vamos a probar a continuación.
Si el sistema I ti ene so lución entonces cxistc j' > O tal que
es decir
~>O y ,> O
x~
o sea
Kx' > O
k I -X 1 > 1 >0
Ahora bien. lo anterior es cieno para todas la filas de K sin más que tomar como
e el vector e¡ = (0•. . .• 1•.. . •0). i = I . .. •n. Entonces el vector x = I.7:1 x! es
una solución del sistema 1/ tal que
> O
Axo -tob + uT; (2.26)
- uoA + tO C+ x6 > O (2.27)
uob -cxo + to > O (2.2S)
Demost ració n
El sistema puede escribirse:
O A -b uT II
_AT O cT x >0 siendo .r >0
hT -e O I 1
Si tenemos en cuenta que la matriz del sistema es antisim étrica podemos apli-
car la propo sición 2.6 para obtener el resultado.
Demostración
Consideremos la solución (Xo ,uo,to) cuya existencia se ha establecido en la
proposición 2.7. Se pueden dar dos casos mutuamente excluyentes yexhausti-
vos.
Dualidad 163
a) lO> O
1 1 ( = Xo
En este caso, os va ores j - ,U ud 1)
= -r-, ·
constnuycn taro bié
len una
lO lo
solución del sistema homogéneo de inecuaciones 2.23, 2.24, 2.25. Es
decir se verifica que Ax > b, x > O. uA < e, u ? 0, 'úb > d . Por tanto
x, ü, forman una par de programas duales. Además, al aplicar el corola-
no 2.4 resulta que x,ii so n óptimos, mientras que de la proposición 2.5
=
obtenemos que ci iib. Hemos demostrado entonces que se verifica la
afinnaci6n a) del enunciado.
b) lo =O
Supongamos que existe un par de programas :i, u. Entonces se cumple
queAj > h, x > 0, uA < e, Ü > O. Dado que (.lO,uo ,O) es una soJuci6n del
sistema homogéneo de inecuaciones 2.23. 2.24, 2.25 se verifica A ~ > O,
XO ;:::: O, lIoA < O, Uo > Oy Uo b > exo. De de las desigualdades anteriores
se SIgue que
lo cual es una co ntrad icción con que l() b > CX(l. Así pues, no puede
ex istir u na pareja de prog ramas duales en el easo en q ue 6 = O llegando
as! a la parle b} 2. es decir, al menos uno de los problemas no tiene
soluciones factibles.
Supongamos ahora que uno de los problemas tiene programa, por ejem-
p lo el primal. Sca x un programa del primal. Se tien e por definición
Ax > b, x:::: O. Sea A :::: O un escalar arbitrariamente grande. Dado que
Xo .>- Opor ser solución del sistema 2.23 resu lta A~ > Ocon lo que
(2.30)
Demost ración
Es consecuencia inmediata del corolario 2.5.
T EOREM A DE Teorema 2.7 Dado un par de problem,1s duales, una condición nece-
D UA LIDA D PARA saria y suficiente para que un prognuna x (pu) de uno de los problemas
LA sea óptimo, es que exista un programa u (o·x) del otro problema tal que
PROGR AM ACi ÓN
LINEAL cx =ub
EIprograma u {ox} es esím ísmo un programa óptimo y la relación anterior
se cumple evidentemente para todo par de programas óptimos.
Demostración
Este teorema resulta inmediatamente del corolario 2.5, condición suficien-
te, y del hecho de que la existencia de un programa óptimo para uno de los
dos problemas, quiere decir, que nos encontramos en el apartado a) del coro-
lario 2.5, condición necesari a.
EJ EMPLO 2.13 La labia 2.3 reflej a las posibles situaciones que pueden darse en un
par de problemas duales de acuerdo con el teorema de la dualidad. _
EJEM PLO 2.14 En la tab la 2.4 se muestran ejemplos concretos de los cualro casos
que pueden presentar un par de problemas duales.
Dualidad 165
El primal JiJprimal
tiene so luc iones no tiene soluciones
f act ibles. factibles.
(1 ) El dlml Mln z e- Máx w Máx w - } +00
tiene soluciones
fact ibles.
b) El dual Min z - > _ 00 caso que puede pre-
no tiene so luciones sentarse
factibles
'rabia 2.3: Situaciones posibles de dos problemas duales, de acuerdo con el rcorema de fa
dualidad.
TEOREMA DÉB IL Teorema 2.8 Dado un par de problemas duales una condición necesa-
DE LAS HOLGURAS ria y suficiente paro que los progrnmasx y u sean óptimos es que verifiquen
COM PLEMENTA- las rc1aciones:
RIAS
u(Ax -b) - O
(e - uA )x O
Demostra ción
Dado que X, u son programas se cu mple que Ax > b, x > O, uA < e, u > O.
De aq uí Ax - b > O. e - uA < O. Como consecuencia a = u (Ax - d ) > O,
{J = (e - üA) x> (). Luego
ex + IJ = ü Ax - ub + cx- uAx = cx - uh
Las relaciones del teo rema 2.8 se interpretan de manera sencilla. La igual-
dad u (Ax - b,) = Oes lo mi smo que r..i -I u¡((XiX- b¡) = O. Puesto que U j > Oy
a¡x - b¡ > O, I = 1" . "m resulta que U¡( (XiX - b¡) > O, pero como la suma ha de
166 UNIDAD DIDÁCTICA 2 Algoritmos dc programación lineal
PR IMAL DUAL
XI >
- O /11 < I
1'/~ /MA l ,
POS/HI.E x\ - 5 /1 1 cualquiera
[)UA l. I'OSIIlI.E XI - z (Min) 5 /11- w (Max)
Mio z = Máx w =5
XI = 5 UI = 1
XI > o
X2 > O "I < -1
PRiMA L POSIRLE : XI - X2 > 5 - 112 < - 1
D UAL lMPOSIRLE - x I - X2 - z (M in) 5u J - w (Max)
z - , -~
XI > o /1 1 < I
PRIMAL IMPOSIBl.E : XI -5 - 5u¡ IV (Máx)
DUAL POSIHW XI = z (M in) w -, +~
ser cero tiene que ocurrir que 11¡( U;X - b¡) = O, i = 1, . . . , 111. Esta relación, que
se veri fic a para cualq uier par de problemas duales óptimos, ex presa el hecho
de q ue si uno de Jos términos del producto es estrictamente posit ivo, el o tro ha
de ser forzos ame nte nulo, es decir:
Si u, > O entonces a¡x = b¡ }
i = l , . .. ,m
Si ex¡x > b¡ entonces U¡ = O
Podemo s observar que las co nd iciones anteriores no excl uye n el caso en {] UC
los dos térm inos del producto sean nulos simul táneamente pam un par (o in-
cl uso var ios) de programas duales óptimos. Sin embargo, el teorema siguiente
aseg ura que esta situac ión no puede da rse para todos los pares de programas
óptimos d uales.
TEOREM A FUERT E Teorema 2.9 Dado un par de problemas duales que sean ambos facti-
DE LAS H OLGURAS bles existe al menos un par de programas óptimos ); y u que verifican las
CO MP LEMENTA· relaciones:
RIAS
(Ax- h)+ z1 > O
(c - uA) + x' > O
Dualidad 167
Demostración
Pu esto que ambos problemas son factibles, estamos en el caso a) del COTO-
lario 2.5, es decir fo > O y los valores:
._ Xo _ Xo
x= - u =.-
lo lo
constituyen un par de programas duales óptimos. Entonces si utilizamos las
Xo
relaciones 2.26 y 2.27 de la proposición 2.4 se cumple que A - b + J/o > O
fo fo
y - -Uo A+c+ --G, > O. A partir d c estas eondlIClones se ob uenc mmcdilatamente
o o o o
lo ro
el resultado deseado.
> O
a ¡.i - b¡+u¡ i = l •. . . ,m
- uaj + cj + Xj > O j = l , . . . •m
Las desigualdades anteriores se cumplen al menos para un par de programas
duales óp timos y expresan que si uno de los términos de la suma es nulo en-
tonces el otro ha de ser estrictamente positivo, es decir, cxisten x ,u tales que
Coro lar io 2.6 Dados dos problemas duales que tengan cada uno m + n
restricciones llamadas respectivamente duales unas de las otras según la
correspondencia biunívoca
- b., <->
a ,o: > , >- O
U· i ::::::: l , .. . ,m
x, >
- O <--> UUj :'S: e, j = 1, . .. . n
una condición ncccseriu y sulicic.·ntc para que una restriee íón de uno de
los probkmas sea ilJ3etiv.1 para al menos un progf¡jlJ r.1 óptimo es que su
J"(.·stricción dual sea ecíive para todo pmgmrua ciptitllo del problema dlWI.
168 UNIDAD DIDÁCTICA 2 Algoritmos de programación lineal
Dem ostración
Necesidad:
Supongamos qu e la restricción; del problema primal es inactiva en el pro-
grama X, es decir a¡x > b.. Entonces por el teorema débil de las holguras com-
plementarias se deduce que U¡ = O para cualquier programa óptimo dual, es
decir, la restricción Uj > Oes activa para cualquier programa óptimo dual.
Suficiencia:
Supongamos que la restricción Uj > O es activa para cualquier programa
óptimo dual, es decir, se verifica siempre en igualdad en el óptimo. Entonces
por el teorema fuerte de las holguras complementarias ha de existir un pro-
grama óptimo primal x tal que ~x - b¡ > 0, es decir, la restricción i primal es
inactiva. n
Del corolario 2.6 se deduce que si una restricción es inactiva, la restric-
ción dual correspondiente es automáticamente activa para cualquier programa
óptimo. En otras palabras, si consideramos las 2m + 2n restricciones primales
y duales podemos afirmar que habrá como mínimo m + n restricciones acti-
vas ya que si no habría mas inactivas que activas, en contradicción con lo que
asegura el corolario. Esto vale para cualquier par de programas duales ópti-
mos. Además, el teorema fuerte de las holguras complementarias asegura que
habrá una parej a de programas óptimos para los que habrá también como máxi-
mo m + n restricciones activas y, por lo tanto, exactamente m + n restricciones
activas.
EJ EM PLO 2.15 Sea el par de problemas du ales
15 33 O O O
XI X, xl /, x',
z 53 O O -5 O -23
15 x, 4/3 I O -1/3 O 213
33 X2 1 O 1 O O -1
O x', 3 O O -2 I 3
6 6 1 O O
u, u, u, u'1 ,
u'
w 53 O 3 O 413 I
6 u, 5 1 2 O 1/3 O
1 u, 23 O -3 1 -2/3 1
(ct - ua¡)XI = O . ~= O
Mini mizar z - ex
Sujeto a Cl¡X - b¡ i = 1•.. . ,m
n m
Je(x,u) = uó + (e -uA )x = ¿ CjXj + ¿ lI¡(b¡- a,x)
j= 1 j= l
PUNT O DE SILL A Definición 2. 15. lil par de vectores x > 0, u > 0. constituye un punto de
silla del Lagrangiano Y (x, u) si para todo par de vectores x > O,u > O se
ricnc
Je(x, u) < Je (x, ú) < Je (x,u)
es decir 2'(x,u) alcanza su m/nimo con respecto a la variable x enx y un
máximo con respecto a la vmable u en u.
TEO REMA Del Teorema 2.JO Dado un par de problemas duales de ProhTTamac;Ón lineal,
LAGRA NGIA NO una condición necesaria y suficiente para que Jos vectores x > 0, u > O
formen un par de programas duales óptimos es que (x, u) forme un punto
de silla del Lagrangiano 2'(X,II). El valor 2'(:<,11) es el valor común de
las dos funciones obj etivo de Jos problemas.
Dem ostración
Necesidad.
Sean X, Ü programas duales óptimos. Por e l teorema débil de las holguras
=
co mpleme ntarias, teo rema 2.8, tenemos, ,,(Ax - b) O Y (e - 7IA}x = O. Esto
es 10 mismo que ñb = ¡¡Ai y eX = üAx. Asimismo, - uA.t + 11 h = O. Por lo
tanto
ex = uAx = íib = ex - uAx + u b = 2'(x,u)
Así pues, ~(x. u) es igual al valor de ambas funciones obj etivo. Además,
(x. u) es un punto de silla. En efecto, si x > O
.2'(x,u) - cx+ u b - II Ax
ub +(c - uA)x
> ub [ ya que e - nA > 0, por ser u un programa ]
y x > 0 por hipótesis.
- 2 ' (x,u)
Por otra parte, si u > O
- 2'(x,i1)
Suficiencia.
Sea .2'(X, II) un punto de silla del Lagrangiano. Entonces .2'(X,u) < 2'(x,u),
es decir,
cx+ u b - u Ax < cx+ u h - uAx
Al simplificar la expresión anterior y reordenar los términos se obtiene la
desigualdad (e - uA)(x - x) > O. Para j = 1, .. . ,n tomamos sucesivamente
x = x+ ej siendo tj = (O... . , 1, .. " O) donde el 1 ocupa el lugar j . Se cumple
O « e - uA )(x + ej - x ) = (c -uA)ej =Cj- U l/j
"2
MaxiLll izar w = 4//1 ¡.. J lI ~
7
V értice óptimo
, ,
•
7 /11
El problema du al es
Maximizar w -4uI + 3U2
sujeto a
"1 ~ < 2", 2
", < 2", 3
2111 + 3", < 5
'" + '" < 2
3 11 1 + 2", < 3
II I,U2 > O
Este es un problema con dos variables que podemos resolver gráficamente como se
muestra en la fi gura 2.3. Su solución es Ul = ~ . U2 -=- J.
w = 5. Por el teorema débil
de las hotgurus complementarias tenemos X2 = O, X ) = O, X4 =- O. Asimismo ha de ser
XI f- 3xs = 4 yal + X5 =- 3 porlo quc J¡ ....., 1 Y X2 = l . Consccucntemcntc z = 5.
Minimizar z = ex
Ax > b
x > O
Notemos que los costes de las variables de holgura son cero. Observemos 13m.
bién que la matri z de coe fic ientes de las restricciones contiene por cada YJ.-
riable de holgura un vector columna unidad - lj que es el que da lugar a la
restricción de no negatividad de la variable dual co rrespondiente. ya que como
sabemos en el dual de la fo rma estándar las variables son no restringidas.
174 UNIDAD DIDÁ CTICA 2 Algoritmos de programación lineal
Proposición 2.8 Sea x una solución básica óptima del problema primal
en la forma estándar anterior con base asociada 8 . Entonces
-
U=c.8B- 1
Demostración
Como Zj -Cj < O resulta uaj - cj < O, o sea ua¡ < cjoj = l , .. . •n + m. Las
desigualdades anteriores para j = 1, .. " n se pueden escribir en forma matricial
corno uA < e, por lo que diB lA < c. Si considerarnos ahora las desigualdades
anteriores para j = n + 1, .. . •n + m y tenemos en cuenta que para i l •. .. , m =
es QIl + i = e¡ y Cn J I = Oobtenemos la desigualdad
O > uan+ i - Cn t¡ = u ( - e¡) - O = - u e¡ =- U¡
El dual es
Maximizar W :..- 2UI + 5 U2
", > O
", > O
", ",
<
< 3
4
Las tablas del método del simplcx para el pri mal son
4 3 6 O O
X, X, Xl X'4 x!
Z 23 O O I -4 -3
4
3
x,
X,
2
5
1
O
O
1
0I -1
O
O
-1
XI X, X, xl xl
Z 21 -1 O O -3 -3
6 Xl 2 1 O 1 -1 O
3 X, 3 -\ 1 O 1 -1
u - c 8 n 1 = (6,3 )( \
- 1 ~ ) = (3, 3) ~ (;'1,. ')
", = -Zm ~ - ( - 3) c- 3
", - - Z H " ~ - ( - 3) ~. 3
Comprobemos que los valores anteriores coinciden exactamente con los que se obtie-
nen al aplicar el método del simplcx al problema dual. La s tablas son
176 UNIDAD DIDÁ CTICA 2 Algoritmos de programación lineal
2 5 O O O
~
1
1 - 1)
b' fIiJ - - (0,5, 2) ( 1 ~ = (0, 3,2) =x
- 1
es decir, hemos obtenido los valores del programa óptimo primal.
m
- --
Z eft-R
x- -_ e RB- 1b -- -b
u -- w' -- ~ -
~ U¡ bi
;=1
Supongamos que los valores del lado derecho de la restricciones Q no son fi-
jos sino que puede admitirse que varían en un determinado rango. Entonces,
podemos entender que el valor óptimo de la función objetivo -: es una fun-
ci6n que depende de los valores 4. i = 1, ... ,m. Es decir, para cada vector
11 = (bl •. . . ,h", ) se puede considerar el correspondiente problema de progra-
mación lineal en el cual el lado derecho de las restricciones es prec isamente el
vector b. Si resolvemos este problema entonces podemos designar a la solución
optima con i (b), a la solución ópti ma d ual asociada u(b ) y al valor que toma la
función objetivo en dicha so lución óptima -,,(b) = cx (b ) = ¿r=1u,(b) b¡. Po-
demos preguntamos ahora cómo varía el valor óptimo de la función objetivo
en función de cómo varia b. Encontramos la respuesta calculando las derivadas
parciales de z(b) con respecto a b. A la vista dc la expresión anterior vemos
que -9t¡ = Uj. De aquí se sigue la interpretación económica de las variables
duales.
PRECIOS SO MBRA Definición 2.16. El valor óptimo U¡ de la i- sima variable dual represen-
ta la .razón de cambio del valor óptimo del primal z contra incrementos
unitarios del í - eimo lado derecho del primal 4. es decir. = U¡ . En la 5t
lcnnino/ogia cconómica los valores'u¡ suelen denominarse precios so mbra
(shadow priees).
Dado que Uj > Oes claro que la razón de cambio de es no negativa con lo
á
•
Minimi...ar Z '"'" L CjXj
j=1
sujeto a
•
L
j=1
CliJXj > b¡ i = l , . .. ,m
que. como se puede apreciar. es el probl ema dual del anterior. El teorema dc la dua-
lidad asegura que hay un conj unto de n iveles de las actividades. Xjo j = 1 ... ,n. y
un conjunto de p recios. u" j = 1, .. . , m. que es tán cn equilibrio. es dec ir, el costo de
producción mínimo es igua l al beneficio de la ganancia máxi ma.
EJEMPLO 2.19 Este eje mp lo es una revisión del problema de la dicta que se vio en
el apartado 1.2.2.2. Supongamos que u na persona está afectada de ciertas carencias ali-
menti cias. El nutricion ista que le atiende le recomienda someterse a una determinada
d icta. Supongamos, por simpl icidad, que las cantidades mínimas dc calorias y vita-
minas que debe tomar cada día para una alimentac ión adec uada son respectivamente
2 .800 unidades y 200 unidades. El terapeuta le facilita un cuadro con los contenid os
en calorías y vitaminas de cada uno de los alimentos usuales. Estos datos fi guran en
la tabla 2.5 . La tabla también incluye el coste promedio, en euros p or kg., de cada uno
de los alimentos en el mercado. Ev identemente el objetivo del paciente es elaborar
Tabla 2.5: Com posición en nutrientes de algunos alimentos y precio unitario de estos.
Dualidad 179
una dieta que satisfaga tudas sus necesidades energéticas y le salga lo mas barata po-
siblc. Para resolver el problem a puede utilizar se un modelo de programación lineal.
Llamemos
Cam ino de su casa se detien e en la farmacia del barrio y comenta su caso con el
farmacéutico. A éste se le ocurre un p lan . Para ahorrar a s u vecino la molestia de ir
al mercado todos los días y tomarse el trabajo de pesar las cantidades necesarias de
alimentos le proponed siguiente trato . El farmacéutico fabricará dos tipos de píldoras:
unas de aporte calórico y otras de aporte vitamínico y le suministrará la cantidad
suficiente de cada tipo para poder satisfacer sus necesidades de calorías y vitaminas.
Además, el farmacéu tico se las venderá a un precio que será competitivo con el p recio
de los alimentos de form a que co n un mi smo aporte energético que un alimento dado le
saldrán a 10 sumo tan caras como éste. El paciente acepta y el farmac éutico sc dispone
entonces a fabricar las pastillas. Supo ngamos por sen cillez, que una pastilla de tipo
calórico aporta 100 unidades de calorías y una de tipo vitaminico aporta 100 •.midadcs
de vitaminas. Entonces ha de fabrica r 28 pastillas de tipo eufórico y 2 past illas dc tipo
vita mín ico. A la hora de decidir los precios de las pastillas, que llamaremos " I para
la de: tipo ca lórico y " 2 para la de tipo vitamínico. el farmac éutico hace el siguiente
razonamiento: los precios ha n de ser competitivos con los de los alimen tos. o sea,
que a igualdad de aporte de nutrientes no deben sobrepasar los precios de mercado
de cada UIlO de los alimentos. Por ejemplo. para obtener un aporte energét ico similar
al de la carn e ha de tomar l O pastillas de tipo calórico y 0.47 de tipo vitam ínico .
Pues bien. el prec io de esta combinación no debe ser superio r al prec io de la carne, es
decir, 1011 1 '-' 0.47111 < 4 . Razonando d e manera análoga para el resto de los a limentos
tenemos las siguientes restricciones en los prec ios:
-o
" , "1
-+
o
t
o
~
-8
o
'"
S
11 -+
· t
w
ce
o ..
o
~
S
1
,.11
8
6
3
//1 O.3X
¡h _ 0.43
\1 ' _ 11 .511
Vérti ce óptimo
• •
•
0.371f
'"
1.35 2
- 1
Fi~ura 2.4: El problema del farmac éutico dual del problema de la dicta.
Por otra parte, el farmac éutico desea sacar el mayor provecho posibl e de la venta de las
píl doras. El beneficio obtenido será evidentemente w = 28u 1 l· 2U2. Asl pues, puede
Dual idad 181
SOLUCiÓ N BÁSICA Definición 2.17. Sea B una base del problema primal y sea que iI la
DUAL FACT IBLE solución básica del primal esocíede a B. Se dice que J!l es una solución
básica dual factible si cfl B I es un programa del programa dual.
Proposición 2.9 Sea B una base del problema primal y sea J!1 la solu-
ción básica del primal asociada a H. S upongamos que 11 es dual factiblc.
Si ¡B es también primal factib le, o sca si verifica todas las restricciones del
primal, entonces xB es una solución óptima.
182 UN ][)A D DIDÁ CTI CA 2 Algoritmos de programación lineal
Demostración
Sea B una base y xl' la so lución básica asociada a B. Por scrtJ dual factib le
se cumple que c!n- 1 es un program a dual, es decir, J1B - 1a j = Zj < c j> j =
l , o•. ,n. De aquizj -cj < O, j = J • • • • • n que es L
a condición que se utiliza en
el algoritmo del simplcx para identificar la situación de óptimo en un problema
de minim ización. Si además tenemos quc r" verifica todas las restricciones del
primal, es inmediato que xB es un pro grama básico 6ptimo.
Primal Du al
Minimizar z = ex Maxi mizar w = uh
sujeto a sujeto a
Ax > b uA = c
x >O u cualquiera
Demostració n
1. Es consecuencia inmediata del teorema de la dualidad. puesto que como
jR es dual fa ctible se cumple el criterio de óptimo del simplcx; ento nces
si x.R es primal factible es tambi én óptimo.
2. Denotemos con Ar
la fila s de la matriz S -l . Definamos i1 = ü - 0Pt.
donde e es un número real. Puesto que:¡R = B - 1 b se verifica
rt b = ub - IJfJ,b = ub - IJx,
Por lo tanto, puesto que X, < O. si O > 0, se llega a que JI b > ísb, para
e
todo > O. Por otra parte para j E (J UJ ) = N l:s Tlaj = Ütlj - O/3(d]. S i
=
tenernos en cuenta que B (CI)-).Iu. 1J - 1 = (Ps ).r€1 resulta que el produc-
lo de una fi ja n-l. como /31. por una columna de B como llT da igual a
cero salvo que tengan el mismo índice en cuyo caso vale uno. Si ade más
utilizamos las notaciones habituales obtenemos
Cons ideremos ah ora los dos casos que pued en darse: a) X J > Opara todo
j E J Yb) y,} < Opara algún j E J
a) Y l] > O, j E J .
En este caso para 6 ~ O está claro que rI es un
programa del dual ya que:
6< Mín
j¡'." <o
{Zj-ej
Yl}
J EJ}
184 UNIDAD DIDÁCTICA 2 Algoritmos de programación lineal
Si se toma exactamente
Seu ahora X'B = (B' r I b la nueva solución básica del primal. S1X H > O
entonces esta solución es un programa óptimo básico del primal. Si, por
el contrario, existe s c: 1 tal que ~ < Oentonces se puede repetir el procc-
so anterior y encontrar un nuevo programa u' mejor que u. Dejaremos
e
aparte el caso en que = o que correspondería a la situación de degene-
ración dual y que no vamos a desarrollar aquí porque es completamente
similar al caso del algoritmo primal del simplex. Entonces en cada ite-
u
ración se tiene que b = u b - (h s con lo cual se obtiene una mejora
estricta de la función objetivo dual w.
-
z } · - c} · < O j El
en donde J designa el conjunto de índices de las columnas de A asociadas
a los vectores fuera de la base. Denotamos 1 = N - J . Y
Zj = ¿'Yj = ¿'B-' aj .
b) Comprobar el vector ~ = B - 1 b.
= Min { • Y l¡ < O,
La forma estándar es
Minimizar z = 2x 1 t- 3X2 + 4X3
sujeto a
x, + a, + x] X4 - 3
a, x, + X3 - X, 4
XI, X2. X3 , X4 . X5 > o
Si multipli camos las dos ecuaciones por -cl , tenernos automáticamente una base H
correspondiente a las columnas X4 y X5. Como además los coeficientes de la función
objetivo son todos positivos, esta base proporc iona un programa de base dual factible
pero no primal factib le. Con este programa comenzamos las iteraciones del algoritmo
dual del simplex. La tabla inicial es la siguiente
Tab la inicial
2 3 4 O O
X, x, X3 X4 X,
z O ·2 ·3 -4 O O
O X4 ·3 .] ·2 .] ] O
O x, -4 0) ] ·3 () I
Vemos, en p rimer lugar, que no todos los valores de las variables son positivos, es
decir, no tenemos un program a primal factible. Asimismo observamos que ninguna
de las dos fi las de res tricciones tiene todos los coeficientes estrictamente positivos.
Entonces debernos iterar. Tenernos 1 1 = {4,5 }. Buscamos en primer lugar la variable
saliente
Mln{x, } ~ Min{x4,x, } ~ Mlo{- 3,-4} ~ - 4 ~ x, .
4~s<o
:leJ¡
Por tanto sale X5. Veamos ahora cuál es la variable entrante. El criterio de entrada es
Mín
j [YI,<O {
Zj C; } =
Y lj
M in {-2 -4} {4}
-
- 2
, -
- 3
= M ín 1, -
3
= I = Y SI
Iteración 1
x, X, X3 X4 X,
z 4 O -4 ·1 O ·1
X4
x,
·1
2
()
I
e · 1/2
1/2
3/2
l
O
·1/2
· 1/2
La única variable negativa es x4. por tanto 11 - {4}. Vemos que no toda la fila es
positiva, p or lo que hay que iterar para que salga dc la base la variable X4 . La variable
entrante es
MIO
.{ -4 -I } .{S}~ S
. 5/ 2 ' - 1/ 2 = MIO 5,2 5
Por 10 tanto entra X3. La nueva tabla es
Dualidad 187
Iteración 2
X, X2 X3 X, X,
z 28/5 O O -9/5 -8/5 - 1/5
x, 2/5 O I - 1/5 -2/5 1/5
x, 11 /5 1 O 7/5 - 1/5 -2/5
Puesto que i B > Oel programa actual es el programa óptimo. Los valores óptimos de
las variables duales son Ul = ~. U2 ~ ~ .
Z + ¿ (Zj - Cj )Xj = z
j E.!
¿ Xj <M
j El
188 UN IDAD DIDÁCTICA 2 Algoritmos de programación lineal
Xo + ¿ xj = M
jfC'J
Dado que estamos suponiendo que no todos los Zj - e j son negativos o nulos
y Zl - q es el máximo de ellos podemos afirmar que 2'« - Ck > O. Efectuemos
ahora un cambio de base tomando como pivote el coeficiente I de la variable
Xl en la ecuación Xo + L j EJ Xj =
M . Esencialmente, lo que hacemos es sustituir
en todas las ecuaciones, menos en la última, el valor de -'l despejado de última
ecuación. Xl = M Xo - ¿ j E,) X j' con lo que la función objetivo queda
jl l
Xv + X I + X2 +X) M
J: = 8 - 4M, x~ = - 3 - M, ~ = - 4-¡- 2M , XI = M
es una solución básica dual factible ya que todos los [a j - Cj) fuera de la hase son no
negativos o nulos, si bien no es primal factible. Podemos ahora aplicar el algoritmo
dual del simp lcx. La tabla inicial es
Tabla inicial
O -2 -/ -/ O o O
Xo X\ X, Xl x1 0, .0,
z -2M -2 O -\ -1 O O O
O xl 8 - 4M 0) O 2 -/ 1 O O
O xh - 3- M -1 O - 10 O o \ O
o )1 - 4 / 2M -2 o -\ 7 O O /
-2 x\ M \ \ \ \ o O o
Las iteracione s son
Iteración 1
\ \
z -4 O O -2
I
-1
- 1 -, O O
Xo M -·2 1 O 4 O O
0, -5 O O @ , -,
-,• \
13
\
\
1 o
0, O O O O O \
x\ 2 O 1 ~, ,1
3 O O
~
Iteración 2
_ 64 23 19 4
z O O O O
- '? - '? - ~'
Xo
X, M-Hn /
O
O O
O 1 ~'
- jj
-V - TI
';! O
O
x'3 O O O O 'f O \
x\ , 9
O \ O n
... ;
14 ,I
O
Puesto que la solución actual es dual factible y también es primal factible tenc..m es
una solución óptima del p roblema aumentado. Como xu está en la base del programa
Dualidad 191
mínimo, entonces la solución óptima encontrada, sin Xo. es asim ismo so lución óptima
del problema original, es decir,
_ 64
z= - -
21
es la solución óptima del problema original.
La convergencia del algoritmo dual se fundamenta en que en cada iteración
se obtiene una base distinta. Como sabemos, en presencia de degeneración
esto no tiene porque ser necesariament e cierto y al igual que en el caso primal
puede presentarse ciclajc. El tratamiento de este problema es similar al del caso
primal y conduce a la forma lexicográfica del algoritmo dual. No entraremos
aquí en una exposición detallada del m ismo.
192 UNIDAD DmÁ CTl CA 2 Algori tmos de programación lineal
El examen del desarrollo de los cálculos del algoritmo ordinario del sim-
plex nos permite observar algunas circunstancias relevantes desde el punto de
vista práctico. En primer lugar, podemos apreciar que todos los números que
constituyen la tabla del simplcx en cada iteración se puede calcular directa-
mente a partir de los datos inici ales. la matriz A y los vectores b y c. tan pronto
como sc haya calculado la matriz B 1, inversa de la base B correspondiente a la
iteración dada. Por otra parte. para efectuar las iteraciones en realidad tan sólo
cs necesario vo lver a calcular una parte dc los números que figuran en la tabla
del simplex, puesto que muchos de ellos, como las columnas de las variables
de la base, son automáticamente conocido s una vez que se tiene identificada la
base B.
El método del simplex revisado se basa precisamente en las consideraciones
anteriores. Esencialmente. realiza exactamente Ios mismos pasos que el m ótc-
do del simplex pero utiliza en la práctica una tabla mas pequeña. En realidad,
desde el punto de vi sta teórico la forma revisada del simplex no aña de nada
digno de mención. En cambio, contemplado desde el punto de vista práctico
las ventajas son indudables, ya que util iza una ca ntidad menor de memoria
de almacenam iento en el ordenador, por lo cual pueden tratarse problemas de
mayores dimensiones. También ocurre normalmente que el número de opera -
ciones aritméticas que efectúa la forma revisada es menor que el número de
operaciones que necesita el dcsarollo de la forma normal, por lo cual el pro-
ccdimiento ser á, en princip io, más rápido. Así pues, podernos sintetizar las
ventaj as del método del simplex revisado diciendo que añade mayores facili-
dades para cl tratamicntc de problemas de grandes dimensiones y que obtiene
la solución de una manera más rápida.
2.3.1.1 Just ificación de la forma revisada del mét odo del simplex
-8
U
n i
Puesto que se COnl'lCC 111 = c!IJ 1 Y la matriz ti = (8 N) = (a J aj ) podernos
calcular fuera de la tab la los Zj - Cj ya que Zj =
di JI - IUj = ¡¡BUj. Si resu lta
que z¡ - Cj < O pam lodo I, el prog rama actua l es el óptimo. Supongamos por
el contra rio que existe un k tal que ~ - e... > O. Usando JI - 1 se puede calcu lar
i
Y.t = 8 - 1lIk · Si YA: < Oentonces el problema no tiene so luci ón fin ita. Si ) l O
se puede insertar este vector co lumna a la derecha de la tabla para obtener
z ,¡I'
Zk - C.t
Yj,ic
Yj~ .t
x" n- I
Y j",k
B-1
z ¡¡B
xl' n- I
-l
X
-= mm
. {-Xs
- ,
Y/k Ylt> O Ysk
Pivotar sobre Yik para actualizar la tab la. Eliminar la co lumna Xk y volver
al paso e).
Se introducen las variables de holgura X7 ,XH, X9. La base inicial es B = (X7,X8, X9) = J,
8 - 1 = /, uB = ¿¡ H- J = (0, 0,0) 1 = (0, 0, 0), X7 = 6, X8 - 4, X9 - 4, siendo
nulas las restantes variables.
Iteración 1
z O O O O 4
X7 fi I O O 1
X, 4 O 1 O O
X, 4 O O O 0_ - Pivote. Sale X9
ZI - q = 1
Z2 - ('2 - 2
z) - e J = - 1
Z.¡ - q - 1
Zj - e j = 4 - ; Entra Añadir
Z6 - C (, - -2
Formas especiales del método del simplex 195
Iteración 2
x,
-8 O O -2 , 2,
o
7.
x, 4 1 O - I\ - Sale X7
x, 4 O 1 O -1
x, 2 O O ~ O
z l -Q
Z2 - C'2
=
- 2
1
- ~ Entra
I
Añ adir
ZJ - CJ - -3
%.4 - C4 - - 1
Z(¡ - C6 - -4
z~ - "9 = -2
u = (0,0, - 2);
Iteración 3
z - 16 -2 O -1 z\ - c¡ = - \
x, 4 1 O - zj - el - -4
x, 8 1 1 -, ;::4 - C'4 = -2
x, 2 O O ~ 4 - ( '6 - -5
%7 - C7 - -2
u= (- 2,0,-1 ) %9 - ( ,' 1} - O
Puesto que todos los Zj - Cj son menores o iguales que cero, la base es la óptima.
,-
OPERACIÓN
METODD PI VOl1<JE Z¡ - c¡ rorxt,
Simplcx M ultiplicaciones (m i- I)( n- m+ 1) m(n - m) + n+1
ó divisiones
Tabla 2.6: Número de operaciones en cada iteración de la forma ordinaria y la forma revisada
del método del sim plcx.
MATRIZ Definición 2.19. Una matriz elemental es una matriz cuadrada que dificre
ELEMENTAL de la identidad cn una sola columna (o una sola fJla).
=
Sea una iteración dada en la cual la matriz básica es B ( ajl . aj2 •. . . ,ajm) =
(a'~)SEJ Y su inversa E - l. En la iteración siguiente la columna no básica a;
reemplaza a la a l y obtenemos una matri z d . Veamos tul procedi miento a l-
Formas especiales del m étodo del simplex t 97
O O O
'" o ...
_Yj]!
E - '"
•
• •
•
•
•
• 1 • •
• •
• •
y"
•
• • • •
• • • • •
y •
o O ••• O _ !a' .
y"
O 1
o sea que para calcular la inversa de B hay que multiplicar B - 1 por una matriz
elemental E . Esta matriz elemental E viene especificada almacenando la co-
lumn a no unitaria g y su posición k. Utiliza ndo esto recursivamente se obtiene
la inversa en cualquier iteración. En efecto, supongamos que la base 8. dc la
primera iteración es la matriz unidad l . Entonces
• Postmultiplicación
Sea e un vector. Entonces si multiplicamos este vector por E resulta
columna
k
j
l •• • 1:, ... O
• •
•
• 1 g2 •
•
•
O O gM I
- (el , e2. · . .• CIt _ 1, eg , Ck+ J• • • •• c", )
• Prcmultiplicación
Sea a un vector. Si multiplicamos la matriz E por este vector resulta
l 1: , O a, a, g,
• •
• •
1:2 • •
•
•
Ea - •
•
•
•
•
•
•
•
a, O + a, 1:,
• •• •
• • •
• • • •
O .. . I:M .. . l aM am I:M
8 +ur g
siendo él e l propio vector a excepto que la r - sima componente es un
cero.
A partir de las expresiones anteriores podemos calc ular fácilmente los datos
necesarios para hacer las iteraciones de la forrna revisada.
1-
g -
(_n,¡ _1 _y¡.¡)
Ylk , . .. .Ylk •. . . • Yu.
Minimizar Z -= - XI - 2x2 + Xl
sujeto a
x, + x, ~ x, < 4
- x, + 2.<, 2.<, < 6
2.<, + x, < 5
.er, X2 . Xl > O
•
200 UN IDA D DIDACTI CA 2 Algoritmo, de programación lineal
Introducimos las variables de holgura X oi, xs. X6. La base inicial está formada por los
vectores columna correspondientes a las variables de holgura, es decir,
O - (a,a ,a. ) _1 0 -1 = I
Iteración 1
z = c'i
R
~ (0.0.0) ( i ) ~ O
iI' - c'0 ' - (O. O. O) / ~ (0.0. 0)
Calculamos ahora Zj - ej . j E J.
%1 - Cl (0,0,0) ( - i)
= (0,0,0) ( ~) - (- 2) - 2
z) - (;] (0,0,0) ( -~ ) . I ~ l
Por el criterio de entrada z ~ - Ck = Máx{ I,2, 1} = 2 =. %2 - ca, por lo que entra en la
base la variable X2 . La variable saliente viene dctcnninada por
X
.I X, X' }
Mio {YU' YS1 ' Y62 -
{4 6S} X,
Mio 1'2'1 = 3 =- YS2
y" 1
-- --
2
YS2
1 1
g- - -
Ys2 2
yoz
-- YS2
1
- -2
y El se representa por [ ; ] .
Formas especiales del método d el simplex 201
Iteración 2
Procedcmos a la actualización de los datos de la tabla . Utilizamos para cllo las
fórmulas de premultiplicación, para el cálcu lo dc x", y dc pustmutiplicación, para el
cálculo de ü.
F,l" ~ ~
El [ ] = [ ~ ] +6 [ ~ ¡~n -[i] ;~ = [ ]
z Z- j2(Z2 - C2) = 0 - 3 - 2 =- 6
u - c"E , - (O, - 2,O) E¡ = (0,- 1,0)
El criterio dc salida es
2/3, ]
[ 10/3
x" =
2
3 ] + 1 [ 21/
E2XB = [ O
2
- 18- 4
/3'3 ]
22
- 5/3
-
1/3
-
[;:]
z - - 6- 2-- = = - -
3 3 3
U c"E,Et ~ (- I, -2,O)E,E, ~ ( ;,-2,O)Et ~ (- ~ , - ~ ,o)
z) - C] - UUJ -CJ ~ (-;,- ~,o) ( -D 5
1- --
3
zs - es = Uu,e, = H,-:,o) (n - o ~ -:
202 UNIDAD DIDÁCTICA 2 Algoritmos de programacióo Iincal
Minimizar z = ex
sujeto a:
Ax - b
f < x < ti
en donde f. y u son los vectore s con los valores de la cotas inferiores y superio-
res respectivamente
f, /11
f2 /12
( = 11 =
•
•
f" ti'/
VARIAB LES Dcñnjcí ón 2.20. Sea A una matriz m x n de rungo m. Sea el sistema de
BÁS ICAS Y NO restricciones
BÁSICAS EN El Ax - b
MÉTODO DEL l < x < u
S IMP l EX PARA
El vector x es una solución básica del sistema si A se puede descomponer
VARIA BLES
de la forma en A = (8 N I N2) donde B es una submatriz m x m de rango m
ACOTADAS
y se verifica:
x"
_
X -
_N,
..
x'"
donde
Xl <
+ -'".2 5
-x, + 2'"2 <
O < .\"1 <
4
4
85
- 1 < X2 s 4
Xl = 4
(0,2)
(4,1 )
10.-1 1 (4,-1 )
x, + x, < 5
- XI + 2<, < 4
O < x, < 4
- 1 < x, < 4
Introducimos las variab les de holgura
x, + x, -+ x, - 5
-X, + 2<, + X4 - 4
O < x, < 4
- 1 < x, < 4
O < x, < ~
O < x, < ~
Observemos que al tener en cuenta las cotas de las variables originales en realidad
los valores superiores de XJ y X4 son, respectivamente, 6 y 10. Para hallar un solución
básica de este sistema se elige una base de las dos primeras restricciones, se resuelve
respec to de las variables no básicas y después se asigna a las variables no bási cas
los valores de las cotas inferiores o superiores. Por ejemplo, tomamos B - (aZ,a4 ) =
- 6 l-3x¡ + 2.:C)
Ahora asignamos las variab les no básicas a sus cotas inferiores y superiores. Por ejem-
plo, si XI = OYX 3 = Oentonces e¡ = 5 YX 4 = - 6 que es 110 factible. También si X I = 4
YX 3 = Oentonceso = I Y-"-t = 6 Y la solución básica (4, 1, O, 6) es factible. De forma
similar pueden obtenerse el resto de las soluciones básica s factibl es:
cuya representación corresponde a los puntos extremos de la región factibl e, figura 2.5.
)ot.
podernos sustituir los valores anteriores en las ecuaciones 2.31 y 2.32 Y ten-
dremos:
con los términos del lado derecho de las ecuaciones que son B: 1 b. Tratare-
mas ahora de investigar si es posible mejorar el valor de la función objeti-
vo modificando los valores de alguna de las variables no básicas. Observe-
mos que (¿VI - ¿ n- IN!) y (c!'2 - eBB- 1N2) son, respectivamente, los valo-
res (ej - Z j) de las variables no básicas en sus cotas inferiores y superiores, es
decir, podemos poner:
siendo
Si el m áximo anterior es negativo o cero entonces resulta que Z;' - Cj < 0, pa-
ra j E R¡ Y también Zj - Cj > O para j E R2. Así pues, no se puede lograr un
mayor decrecimiento de la función objetivo y la solución que tenemos es por
consiguiente una solución óptima. Alternativamente, si dicho máximo es po-
sitivo entonces llamemos k al índice en que se alcanza el máximo . Si k E= Rt
entonces aumentaremos x"
desde su valor actual en la cota inferior fk • mien-
tras que si k C R2 entonces disminuiremos Xk desde su valor actual en la cota
superior Uk . Analizaremos los dos casos anteriores de forma separada.
Puesto que (Zk- Ck ) es positivo porque k E U[. resulta que cuanto mayor sea
I':1 k mayor será la disminución de z, Pero ~ no puede aumentarse indefinida-
mente sin tener en cuenta las restricciones. El aumento de puede bloquearse "*
Formas especiales del método del simplcx 207
u-:
- 'l---_X-'" = m m
• { u, - ~~
- Yik .flv,.,¡ <o - Y.\'k
u i - Xl
Y.! - - Yilt
SI Yk i O
(2.34)
~ SI Yk > O
3) La variable Xt alcanza su cota superior l4..
Evidentemente esto ocurre cuando ~ llega a va ler Uk - fk,
En resumen, el valor máximo que puede aumentar una variable no básica .l:
vendrá dado por el más pequeño de los tres valores anteriores, o sea :
8k = Min {Yi>y'! .Uk - fk}
=
Si 1111. +00, entonces el aumento de Xk no está bloqueado y por tanto el pro-
blema no tiene solución óptima finita ya que puede incrementarse indefi nida-
mente la variable Xk disminuyendo indefinidamente la función objetivo , Alter-
nativamente, si I1k < 0<.>, entonces se obtiene una nueva solución básica factib le
dando a Xk el valor Xk + 1111. y modificando las variables básicas de acuerdo con
la ecuación que la expresa en función dc n .
208 UNIDAD OlDÁCTlCA 2 Algoritmo, de programaci ón lineal
z = z- (Zk - q )" k
x" - ?' - Yk"k
2. Si I'1 k está dado por i1 Ó 12. entonces la variable Xk entra en la base y la
variable Xf sale de la base, donde t. viene dctcnninada por 2.33 si ¡'j¡. = Yl
=
o 2.34 si !'1k )'l. La tabla del simplex se actualiza pivotando sobre »'*
como es usual, exceptuando la primera columna. Notemos que}rk puede
ser positivo o negativo, pero esto no afecta al pivotaje, ya que la primera
columna no se pivota. La primera columna se actualiza de acuerdo con
las ecuaciones
Z z - (Z, -q)"k
x" ?' - Yk"k
Xk f k +'"
Alternativamente la primera columna se puede actualizar directamente
con el resto de la tabla. Para ello hay que reajustar previamente dicha co-
lumna mediante mediante la aplicación de las tres operaciones siguientes
que se pueden ejecutar en cualquier orden:
siendo:
si y.;¡~ O
71 =
si y. > 0
Ui - - Xi
--'---'
Ylk
•
= m III
sty.. >0
{ us - ~ ; s E
Ys.
.¡}
)'> =
si Yk <O
Si /)J. = oo. ento nces la solución óptima es no finita. Si ÓIc < 00 ,
se obtiene
una nueva solución básica factible co n q = Uk - 6 •. La nueva tabla se obtiene
pivotando sobre Yi k.
¿ X" +y,""
z = z+ (z, - q) ""
2.3.2.2 Inicialización del método del simplex para varia bles acota-
das
Cuando no se dispone de una solución básica factible adecuada sc puede
iniciar el método usando variables artificiales. Esto se efectúa siguiendo los
pasos siguientes :
3) Representar el sistema
Paso principa l
zk - q = Máx { jMáx
ERI
Z ' -C '
J J'
Máx
J Elll
Cj - Zj }
S ik E R¡ ir a Z.
Si k E R2 ir a 3.
2) Incrementar Xk en el valor fj,k dado por fj, k = Min{ ')'l , ~ , Uk - f.k } '
Si fj, k = oc , entonces FINALI ZAR: no exi ste so luci ón óptima finita.
En caso contrario actualizar la tabla y repetir el paso 1).
Formas especiales del método del eimplex 21 1
EJEMPLO 2.25
Minimizar z = - 2x ¡ - 4 x 2 - XJ
sujeto a
2.1;1 + X, + Xl < 10
Xl + X, Xl < 4
O < Xl < 4
O < X, < 6
1 < Xl < 4
Introducimos las variables de holgura
n - . {x.-t.
M In -
~
- Y sk
}
> O = Mio - - {9-0I ' S-O}
1
= 5 o:- s. -«
.'"-....::0
Y S2
_. 00 ya tille Y2 >O
1'l
Y2 - 1.2 - 6 -0 = 6
,
212 UNIDAD OID ACTl CA 2 Algoritmos de programación lineal
De aqul 6/{ = Mín {5, 00, 6} -= 5 y, por tanto, sale la variable x 5, Entonces se pivota
conY52, salvo la primera columna que se actualiza de la manera siguiente
x, - 9 -1 , 5 ~4
X, 5 -5 =0
x, 5
z - 1 4 ,5 ~ - 21
La nueva tabla es
e e e
x, X2 Xl X, x,
z - 21 -2 o 5 o -4
x, 4 1 o 2 1 1
x, 5 1 1 - 1 o 1
y,
De aquí, Mln{2, 1,3} - 1, por lo que sale la variablc r r y se pivota sobre Y2) . Ahora
se cambia la primera columna
X4 4 - 2· 1 = 2
X2 5 -( - 1)· 1 ~ 6
X3 x) f/j,/{ =11 1 =2
Z - - 2 1- 5, 1 ~ - 26
e u e
XI X, X, x, x,
Z - 26 ] 5 O O - 1
X4 2 3 2 O 1 l
x, 2 - 1 - 1 1 O - 1
Uj - t I - 4-0~ 4
'" - Ming.2.4} ~ ~
por lo que sale la variable X4 . Se pivota sobre Y 41 y los nuevos valores de las variables
son
2
-26- 3 · -= - 28
3
u e e
x, x, Xl X4 X,
Z - 28 O 3 O - 1 O
2 2 1 1
x, - I - O - -
3 3 3 3
8 1 1 2
X3
3
O --
3
I -
3
-- 3
214 UNIlJAD DIDÁ CTICA 2 Algoritmos de programación lineal
Máx {O, - 3} = O
Puesto que el máximo del criterio de entrada es menor o igual que cero obtenemos
que la solución actual es la soluc ión óptima :
_ 2
XI = 3' i , = 0, z = - 28
[ SU BS IST EMA R I
fo'igu ra 2.6: Estructura de la matriz de restricciones de un problema de programación lineal
susceptible de ser resuelto mediante el algoritmo de descom posición.
Minimizar z = ex
sujeto a
Ax b
x E: X
¿ (AXj )Aj b
j =- I
I
¿ Aj I
j = 1
Aj > O
Utiliza remos para ello el método del simplcx revisado. Supongamos que
disponemos de una so lución básica del problema máster A = (l B.ÁN) Y co-
nocemos la matriz inversa de la base n-l. Ésta es una matriz (m+ 1) x (m+ 1)
ya que en el problema tenemos las m restricciones debidas a la matriz A y la
restricción adicional que exige que las variab les A, sume n uno. Denotamos
por u = ( u J." " um) las variables duales asociadas a las m primeras restric-
ciones y por ex a la variable dual asociada a la última restricción. Ponemos
además c= (CXI,CX2•. ..,CXI ) = (CXj) , j = 1. 2, . . . •1 que es el vector de coe-
ficiente s en la función objetivo del problema máster. Podemos entonces es-
cribir (!I B - 1 = (u, a), siendo en el subvcctor de costes correspond ientes a
las variables básicas. El lado derecho del problema es (~) y denotaremos
b = B-1 (~) . Con estas notaciones, la tabl a de la forma revisada del algorit-
mo del simplcx es
C"/; (u,a)
b 8-1
Procedemos ahora de la manen! que indica la forma revisada del algoritmo del
simplcx. Para saber si la solución actual es óptima calculamos
~
- Máximo { (l/,a)
I $J< t
(A?) - CX] }
Máximo {l/Ax] + a - cx]} (2.35)
I $.J<;.t
Corno para las variables básicas se tiene que .<; - ~ = O, el máximo anterior
tiene que ser mayor o igual que cero. Ahora bien, si el máximo anterior es igual
a cero resulta que para cualquier índice j se tiene que :; - Cj < O, incluidas to-
das las variables no básicas; de ello podernos deducir que la solución actual es
la solución óptima; en otras palabras. el criterio de óptimo del problema máster
es que el máximo calculado en 2.35 sea cero, es decir; "l - CA: = O. Al ternati-
vamente, si Zk - CA: > Odeberá incrementarse la variable .Al . La detenn inaci6n
del índice k para el cual se alcanza el máximo no se puede calcular de manera
sencilla mediante la ecuación 2.35 puesto que el número de puntos extremos
es muy grande y además no se conocen explícitamente. Necesitamos utilizar
entonces un método alternativo. Como X es un conjunto poliédrico acotado,
sabemos que el máximo de una función lineal en X ha de alcanzarse en un
punto extremo:
As í pues, dada una solución básica factible (ltP,A. k) con variables duales (u,a)
para determ inar la variable en trante hay que resolver el llamado subproblema
lineal del algoritmo de d escomposición.
SUBPROBLEMA Definición 2.22. Se Jlama subproblema lineal del algoritmo de descom-
LINEAL Del posición al siguiente problema
ALGORITMO DE
DESCOMPOSICiÓN Maximizar (uA - c )x + a
sujeto a
x EX
Paso inicial
• Determinar una solución básica factible inicial del problema master aso-
ciada a la base B y formar la tabla maestra
,.B b (u,a)
b 8- 1
Pa so principal
Sea Xk una solución básica fact ible óptima con valor objetivo ~ - Ck.
218 UNIDAD DIDÁCTICA 2 Algoritmos de programaci ón lineal
b, , . b,
-Ylt = Mínimo
1:5.\':5m+ I { Ysk'
O bservaciones
Para una restricción del problema máster de tipo menor o igual con va-
riable de holgura XS¡ se tendrá
=
6. El algoritmo se detien e cua ndo Max (Zj - Cj ) O. Puesto que el número
de variab les 1. 10 )..2, . . • ,,\¡ puede ser mu y g rande, aplicar el algoritmo
hasta que se ve rifique dicha cond ición puede preci sar un elevado número
de iteraciones. Por ello, en la práctica se pued e proceder del modo que
se ind ica a continuación.
A) Buscar una cota inferi or para la función del objetivo en una solu-
ción factible y, consecuentemente, en la solución óptima.
B) Co mo cl algoritmo ge ne ra puntos fac tibles mejorados, el procedi-
miento pued e detenerse cuando la diferencia entre el valor actual
de la fu nción objetivo y la cota sea menor que una tolerancia aecp-
tablc.
Para encontrar una cota inferior para la func ión del objetivo se puc-
dc proceder del modo siguiente. Sea el problema:
Maximizar (uA--c)x + a
sujeto a x EX
Sea (Zk - CA:) el valor óptimo. Sea x cualquier solución factible del
problema original, es decir, Ax =
b, x E: X . Dado que (z.t: - ék) es
el máximo se tiene
De aquí resulta
B =( ~ lA;' )
siendo 11a matriz identidad asociada a las variables de holgura qu e
denotaremos en esta ocasión con i. Obviamente B es un base cuya
inversa es de la forma
Tabla inicial
z cx, O ex,
xl' h - Ax l 1 - Ax ¡
A, l O l
A-e o
I
I
o
x, X, .\'4
3 .r ¡ = 2 3
(o.¡¡
X2
,>
2 •o .,,
(2. ~)
-I¡ '1-
"Y.
y
\1
<,-.., ~s
o-
1I 1I
o 2 3 Xl o 1 2 3 .\')
En la fi gura 2.7 se representan los conjuntos X l y Xl que serv irán para reso lver
gráficamen te los subprob lemas. Como punto de partida se puede tomar el punto x l =-
(0,0, 0, 0) que verifica evidentemente las dos primeras restricciones.
o
o o
Ax'
e I o
o
En dicho punto la función objetivo toma el valor
()
O
(- 2, - 1, - 1, 1) ()
= ()
()
/J - G!~) B- =
J
G! ~)
(u, a) é"B- J = (O. O. O)B- ' = (0,0,0)
b B-
J
(7) ~ (~ ! Dm m =
Así pues, la primera tabla del problema m ástcr, donde Ll) significa "Lado Derech o de
las restricciones", es la siguiente:
Tab la inicial
LO Inversa
z O O O O
xl 2 I O O
>1 3 O I O
A, 1 O O 1
Itcmci6n 1
l . Subproblema
Puesto que u ~ (0,0), ex = O, c = ( 2, - 1, -1 ,1 ) resulta que
Entonces el subproblema es
- _ 17 17
é"b - (z, ~ C2) = 0 -- ~ --
2 2
El mejor valor de la función obj etivo que tenemos hasta el momento es z -= O,
que co rresponde al punto inicial. La diferencia entre este valor y la cota inferior
es apreciable por lo que debemos seguir con las iteraciones.
Formas especiales del método del simplex 223
2
_
Z2- ez=-
2
17
Ax' -- [11 01 (', (2)] 3 /3
2
7i2
= [ ']
()
LO Inversa
z () O O O I 1712 I
.<t 2 1 O O 0712
<t 3 O I ()
)., 1 O () 1 1
. { 2 3 1} 2
Mm S' r l = 5
LD Inversa
z - 17/ 5 - 17/ 10 O O
)., 2 /5 1/ 5 O O
0, X/ 5 - 7/ 10 I O
)., 3 /5 - 1/ 5 () I
que da a la func ión objetivo un valorz = - l/.También tenemos que ("I. U2. a ) =
(-!.l. O,O)
,
224 UN IDAD DIDACTl CA 2 Algoritmos de programación lineal
Iteración 2
1. Subproblema
Como U l =- :~ < Oentonces x7 no es candidata a entrar en la base. Tenemos
(uA- c) = (-:~'O) (: o
1 O 2
1 0) _( _'2 - 1 _ 1 t ) =
."
(2. 1 _2. - 1)
10" 10'
2. Problema mésrcr
o
_ 5
ZJ- C]- -
2 Ax' ~ [ : ~ ~ ~] 5~2 = [5~2]
O
Calculamos el vector
y , -B I .-!x']
[1 = [1
- 7//510
- t/ 5
LD Inversa
--
z - 17/5 - 17/ 10 O OI I 512 I
)., 215 1/ 5 O O O
s, R/5 -7/ lO t O 5/2
-
A, 3/5 - t/5 O t CD
'-' -
El criterio de salida detcnnina que sale de la base la variable A). Después de
pivotar sobre el I se obtiene la tabla siguiente.
Formas especiales del método del simplcx 225
-
LD Inversa
z 49/10 - 6/ 5 O - 5/2
A2 215 1/ 5 O O
52 1/10 - 1/ 5 I - 5/ 2
A, 315 - 1/5 O I
Como a = - i el subproblema es
. . {4
Maximizar 1
- X I+ X2- - X l - X4- -
5
55 2
Si rec urrimos de nuevo a la fi gura 2.7 vemos q ue la soluc ión óptima es x 4 _-
(2. ~ ,0, 0) en la cual la funci ón objetivo loma el valor Z4 - 24 = ~ > O. Entonces
se introduce ~ en la base.La cola infe rior tille tenemos para la función objetivo
del problema genera l es
- _ 49 3 55
c"b - (z. -c. ) ~ - - - - =- - = - 5 5
105 10 ·
El mejor valor conoc ido de z hasta ahora es - 4 .9. Si esta precisión fuese suñ-
cientc se podría parar aq uí la aplicación del algoritmo.
2. Probkma m éstcr
2
_ 3
Z4 - C4 = - > O
5 Ax' = [ : ~ ~ ~] 3~2 = [772]
O
Calcu lamos el vector:
= [;~;]
3/5
y añadimos esta columna a la tabla.
226 UNIDA D DIDÁ CTI CA 2 Algoritmos de programacióo lineal
LO Inversa
z - 49/ 10 - 6/ 5 O - 5/ 2 3/5
A, 215 1/ 5 O O 215
.<1
Al
1/10
3/5
1/ 5
- 1/ 5
1
O
- 5/ 2
1
(0 3/5
LD Inversa
z - 5 - 1 - 1 O
A, 1/3 1/ 3 2/ 3 5/3
A., 1/6 - 1/ 3 5/ 3 - 25/ 6
Al 112 O - 1 7/ 2
XI = 1, X2 - 2, Xl - 1, X4 = O, z"- -5
es la solución óptima.
Formas especiales del método del simplcx 227
1 2 J 4 Iteración
o I
- -.,
El
>
o Valor obj etivo pr imal
o
.-"o- " J
, ·0· 0
-
4
. ~
2 ·~
••
- -1. \1
-,
-. 5
- o
--
".
00
O"
-' ''>.
>
-7
s
- 5.9
- 5.5
Cota inferior
-9
FI~urK 2.8: Representación de la evo lución de los valores de la función objeti vo a lo largo de
1a.'I iteraciones .
Por ejemplo, en la iteración 3 se sabe que la so lución actual vale - 4.9 y que no
ex isten soluciones fact ibles que den a la func ión objetivo un valor inferior a - 5.5. El
punto óptimo ( 1,2, 1,O) corresponde a los puntos ( 1, 2) ~ X t Y ( 1, 0) E Xl tal como se
puede aprec iar en la fig ura 2.7. Obsérvese que no son puntos extremos de X , YX2 nin-
guno de los dos, lo cuall ógicamente no tiene pur qué ocurrir. En cambio sí tienen que
ser puntos extremos si añadimos las restricc iones maest ras como se ve en la figura 2.9.
X2 X4
•• o 2 3
XI
X,
2
I " o .~ . 1
o o
o 2 3 XI o '0 '- (1, 0) 2
En efecto , la primera restricc ión del prob lema es x I -t X3 < 2 . Si añadimos la con-
dición X3 = 1 se obtiene la inecuación x I + l < 2, o sea X I < l . La segunda ecuación
es Xt + X 2 + 2x4 ~ 3. Si añadimos la condic ión X 4 '- O res ulta XI + X 2 + "5 3, o St.'3
X I + X2 < 3. Entonces si al conjunto XI le añadimos estas dos restricc iones adicionales
°
oblcnc mos una región factible en la cual el punto (1.2) sí es un punto ex tremo. Ami to-
,
228 UNIDAD DmACnCA 2 Algoritmos dc programación lineal
I l
Minimizar a e L (CXj) Aj + L (c dj )/li
J= I j=l
sujeto a
I l
L (AXj )Aj + L (A dj) /lj b
j=1 j - l
I
L Aj 1
j -: I
Aj :> O j ~ 1, ,1
/l} :> O j ~ l, ,l
Si utilizamos el método del simplex revisado para resolver este problema, en
una iteración cualquiera tendremos la tabla
C"b (u, a )
b B I
en donde
-
e _ (CX I •• .. ,cx¡, cdl , ' . . , edi )
(u,a) C" B- 1
b B-
1
G)
Formas especiales del método del simplcx 229
- - - -- - - - - - - - - - - - - - -
Scgún el criterio de optimalidad la solución actual será óptima si se verifica
que Zj - S
< O para tod as las variables. En particular, se han de cump lir las
condici ones sig uientes :
• Para Aj no básica
(2.36)
Supongamos en pri mer lugar que el problema anterior tiene un óptimo no aco-
tad o. Esto sólo es posible si existe una di recci ón extrema 4: para la cual se
cumple que (uA - c)d" > O, puesto que como Jq > O pued e hacerse arbitraria-
mente grande entonces x = JIK(h es fa ctible para valores arbitrariamen te g ran-
des con lo cual la funci ón objetivo (/fA- e ) (Jlkd/i. ) + ex - ) ee. Así p UCS, en este
C"1SO no se cumple la cond ic ión de óptimo 2.37 para e l co rrespondiente ~ - eh
=
es deci r, Z/i. - C/i. (l/A - C)dk > O, con lo cual t1k será clig iblc para entrar en la
hase. Se ge nera entonces 1a co lumna [ AO
d. ] ' se actua l·Iza prcmu 1np
·1 rcanco
· ·'
[
Z! -
y.
ek
] , co ntinuando con la aplicac ión dd m étodo del simplex revisado .
y, por tanto, la condición Zj - ej < O se cumple para todas las variables 'A¿
fuera de la base. Si por el contrario zt - Ck > 0, entonces hay que introdu cir
.
en la base la variables A¡¡ . Para ello se genera la columna Yk = B - ,(AX,)
1
Minimizar Z = - X l - 2 X2 - x]
suj eto a
x, + x, + x, < 12
-x, + x, < 2
-x, + !x, < 8
x, < 3
x,, x" x, > O
Cons ideramos que la restricción relativa al sistema global es la pri mera, de fonna que
A es la matriz. A = ( 1, 1, 1) mientras que b = 12. Las otras res tricciones forman el
co nj unto X. Este conjunto, se descompone en los dos subconjunt os
Tabla inicial
LD Inversa
z O O O
x" 12 1 O
Al I O 1
Iteración 1
l. Subproblema
Puesto que uA - e = O· ( 1, 1, 1) - (- 1, - 2, - 1) - ( 1,2, 1) el subproblema es
Maximizar z - XI + 2x2 +X ] + O
sujeto a
+ x, < 2
+ !x, < 8
x, < 3
xr , X 2, X 3 > O
Formas especiales dcl método del simplcx 231
x,
7 -;
x,
6
5
4
J
-1
o
o J--~
Xl
o 2 3 4 5 (, l'
Figura 2.10: Representación gráfica del ejemplo 2.27.
Para resolverlo lo separarnos en dos partes: una en la que sólo interv ienen las
variables X I y X2 Y otra en la que sólo interviene la vari able Xl. La soluc ión ópti-
ma del problema cn r j es obviarncnrc x j = 3. La solución óptima del probl ema
en X I Xl se puede encontrar gráfi camente con facilidad, pero vamos a hacerlo
usando el algoritmo normal del simplcx. Introduci mos pa ra ello las corrcspon-
dientes variab les de holgura.xa en la primera rest ricc ión y x s en la segunda. Ln
labia inicial del simplcx ordinario es:
x, X, x. x,
z O - 1 - 2 O O
x. 2 - 1 1 1 o
x, 8 - 1 2 o 1
x, x, X4 x,
z 4 -3 O 2 O
x, 2 - 1 1 1 O
x, 4 1 O - 2 1
x, x, X4 X,
z 16 O O -4 3
x, 6 O 1 - 1 1
x, 4 1 O -2 1
,
232 UNIDAD DIDA CTI CA 2 Algoritmos de programación lineal
Entonces, si X4 -+ 00, significa que (X I, X2) - ) 00 sin sal irse del conjunto. Juego
(2, 1) es una dirección de X. A esta dirección en el espacio (x hxz ).le corres-
ponde evidentemente la dirección (2, 1, 0) en el espacio (x I,X2,X3) . Asl pues,
la so lución del subproblema ha dado como salida una dirección d 1 - (2, 1,0) Y
un coe ficiente
ZI - CI = 4 A d i = ( 1, 1, 1) m = 3
y, ~ B- 'C~I) = (~ nG) ~ G)
Añadimos esta columna a la tabla
LO Inversa
z O O O I 1 4
x"
Al
12
I
1
O
O
I
0O
Según el criterio de salida abandona la base la variable x" , Al pivotar sobre 3
se obtiene la nueva tabla
Z 16 4 /3 O
111 4 1/3 O
Al l O l
Iteración 2
l . Subproblema
Tenemos u -- - j y a = O. Como 11 < 0, la variable x" no es candidata a entrar
en la base. Tenemos
4 1 2 l
uA - c = - - (1 1 I} - (- I - 2 - 1) = (- - - - - )
3" ,. 3'3 ' 3
Formas especiales del método del simp1cx 233
- 1/ 3 2/3 O O
X, X, x, x,
z 8/3 O O O 1/3
2/3 x, 6 O 1 - 1 1
- 1/ 3 XI 4 1 O - 2 I
Esta es la solució n óptima (no única). La función objetivo del subprob lema es
LD Inversa
z - 16 - 4/ 3 O
/11 4 1/ 3 O
~I I O 1
LJ) Inversa
z -56 /3 - 4/ 3 -8/3
/11 2/3 1/ 3 - 10/ 3
~, 1 O 1
Ob servemos que la cola inferior del problema que conocemos hasta el momen-
to, - ~:'. coincide con el valo r que hemos obtenido pa ra la función objetivo.
Por ello. podemos ya asegurar que la solución ac tual es la so lución óptima.
Comprobaremos este al rea lizar la iteración siguiente.
234 UNIDAD DID ÁCTI CA 2 Algoritmos de programación lineal
Iremci6n 3
1. Subprob lema
Como u = - ~ < O,:r!' no es candidata a entrar en la base. Tenemos ahora
uA - c = - 4( 1 11 ) _ ( _ 1 - 2 - 1)=
3 " .,
(_ ~3'32 '-3~)
. . I
Maximizar - 3 X )
sujeto a sujeto a
- Xl + X2 < 2 X3 <3
- Xl + 2x 2 < 8 x) >O
XI,X2 :::: O
Evidentemente la solución óptima de cada uno de los subpro blemas sigue sien-
do la misma que en la iteración anterior, es decir, x I = 4, X 2 = 6, x ) = O. Sin
embargo, la función objetivo vale ahora z ) - 2] = ~ + O- ~ = O Por tanto la
solución actual es la solución óptima. La solución del problema general viene
dada por
16
3
20
'r
O
l . Posloplimi7.ación
Los análisis incluidos en este grupo se refi eren a aquellas situaciones en
que se efectúa una modificación discreta de los datos, matriz A. vector
del lado derecho b, vector de coeficientes de la función objetivo c. Se
pueden distinguir varios tipos de modificación:
2. Análisis de sensibilidad
En este grupo se trata de determinar un intervalo en el cual un dato puede
fl uctuar sin que la solución obtenida dej e de ser óptima. De esta forma
se puede dar respuesta a cuestiones como: si se modifica ligeramente
un dato ¿cambia m ucho la soluci ón" , ¿viene sensiblemente afectada la
sol ución óptima si se p roducen pequeñas imprec isiones en los datos? u
otras similares. Los análisis de sensibilidad mas importantes son los que
se hacen sobre el vector del lado derecho de las restricciones b y sobre
los coeficientes de la funci ón de coste c.
3. Análisis paramétrico
En este análisis se considera que los datos pueden variar de manera con-
tin ua en un determ inado rango de val ores y se trata de ver cómo influye
dicha variación en la sol ución óptima. El caso más general en el cual
uno o varios datos son una función cualquiera de uno o varios paráme-
tros es mu y complejo. Normalmente só lo es posible rea lizar un análisis
más senci llo en el que los datos son función lineal de un sólo parámetro.
En part icular, estudiaremos el caso en que los vectores e y b son función
lineal de un paráme tro.
Así pues las modificac iones que se hagan en los datos a fectarán a la facti-
bilidad de la solución, a su optimalidad, o bien a ambas características .
Análisis d e la solución óp t ima 237
2.4.1 Postoptimización
El estudio d e la postoptimi zaci ón se desarrollará sobre la base de un ejem-
plo sencillo que nos dará pie para ir introduciendo las oportuna s considcracio-
ncs sob re el a ná lisis d e la so luci ón ó pt im a . Presentamos a co ntinua ción di cho
ejemplo y su sol ución ó pt ima obtenida mediante el a lgo ritmo p rimal del sim-
plcx .
EJEMPLO 2.28 Una compañia fabrica dos productos /'. y / ',.. Para ello nece sita
dos tipos de materia prima A y B. La tabla 2.7 mu estra las necesidades de materia
prima para 1,1 fabricación de cada tonelada de producto y las can tidades dispo nibles
diariamente de cada una de ellas.
Resolvemos este problema por el método del sim plcx . Para ello lo ponemos baj o la
forma estándar como problema de minimiza ci ón introduciendo las variables de hol gu-
ra X), .44, X 5 Y.46 Ycambiando los coeficientes de la función objetivo por sus opuestos.
I
x, + X6 -. 2
Xl, X2, x). x 4. x5. X6 > O
238 UN IDA D DID ÁCTI CA 2 Algoritmos de programaci ón lineal
El problema dual es
Tabla inicial
-3 - 2 O O O O
X, x, X, X, X, X,
Z O 3 2 O O O O
O Xl 6 l 2 1 O O O
, -,
11 X, 8 I 2 , 1 11 1 O O
O X, 1 '-'
- 1 1 O O 1 O
O X, 2 O 1 O O O 1
Iteración I
XI X, X, X, X, X,
z - 12 O 112 11 - 3/ 2 O O
11
- 3
X, 2 O @ 1 - 1/2 O O
X, 4 1 112 O 1/ 2 11 O
O X, 5 O 3/2 O 1/ 2 1 O
O X, 2 11 1 O O O 1
Iteración 2
X, X, X, x, X, X,
z - 38/ 3 11 O - 113 - 4/ 3 O O
-2 x, 4/ 3 O I 2/3 - 1/ 3 O O
- 3 x, 10/ 3 1 11 - 1/ 3 213 11 11
O x, 3 11 11 - 1 1 1 11
O x, 2/3 O O - 2/3 1/3 O 1
\8
máximo de z = mil euros. Además la tabla óptima nos informa de que la primera
restricción se c umple en igualdad debido a que x } = O(o bien el valor dual lit = í). es
í
decir, I . ~ t- 2 · = Jf = 6, 10 eU:11 qu iere decir que se usa lodo el material dispo nible
de la materia pri ma A. Asimismo. la segunda restricción se cumple en igualdad. ya
í
q ue ."4= O (u bien U2 = ~ ). es decir, 2· lf + I • = 'Jf = 8, es decir. se utiliz..1 toda
la mater ia 11 dispon ible. Las restricciones de demanda no se verifi can en igualdad, ya
que las variables de holgura correspondientes son positiY'J.s, .xs = 3, X6 = j. Esto sig-
nifica que las restricciones de demanda no influyen cn la solución óptima y el máximo
beneficio que puede obtenerse viene limitado por la disponibil idad de materia prima y
no porque el mercado no acepte mas producción. Observemos que la base óptima es
2 1 o O
1 2 O O
1 - 1 1 O
1 O O 1
y que su Inversa es
2 1
- O O
1 ~
O O
3 3
- 1 1 1 O
2 1
O 1
3 3
según puede leerse di rectamente en la tabla.
Veamos ahora cómo puede usarse toda la in formació n proporcionada por
la tabla óptima del algoritmo del simplex para efectuar un análisis de postop-
" .,
tmuzacrón.
2.4.1.1 Modifica ción del vector del lado derecho de las restriccio-
nes
Veamos cómo afecta a la soluc ión óptima una perturbación de los elementos
del vector del lado derecho de las restricciones. Sea b + oh el nuevo valor del
-r
segundo miembro y R la nueva solución básica asociada a hase B, es decir, a
la base óptima antes de la perturbación de b. Tendremos:
-r
Puesto que B > O esta so lución básica sigue siendo un programa por lo que sigue
siendo óptimo ya que la función objetivo no se ha modificado. El plan de producción
óptimo es ahora fabricar Xl = 3 toneladas de P I y X2 = 2 toneladas de ~, lo cual pro-
porciona un beneficio de i = 3 ·3 ·t 2 ·2 - 13 mi l euros. Observemos que la di ferencia
entre el nuevo valor de la función objetivo y el antiguo vale 13 - ~ = = til . por Jo í
que U l se puede entender como el precio 'J usto" que hay que pagar por aumentar en
una unidad la disponibilidad de materia A, es decir, pasar de 6 a 7 unidades. Rccncon-
tramos dc nu evo la interpretaci ón económica de las variables duale s como "precios
sombra" (ver página 177).
b) Supongamos que la disponibilidad diaria de materia prima es de 7 toneladas
para A y 4 toncladas para /J . ¿Cómo afecta esto a la solución óptima?
En este caso el vector del lado derecho es (7,4, 1,2) /, La solución básica asociada es
2 1
- --
3 3
O O
10
-
3
x, I 2 7 I
x, - -3 - O O 4 -3
x, - 1
3
1 I O 1 -2
x, 2 1
2
4
--3 -
3
O 1 - -3
Como X s y X6 son negativas esta solución no es un programa. Para rcoptimizar utiliza -
mos el algoritmo dual del simp lcx sobre la tabl a óptima modificada :
-3 -2 O O O O
Xl X, X3 X, x, x,
z - 23/ 3 O O - 1/3 - 4/3 O O
- 2 x, 10/3 O 1 2/3 - 1/ 3 O O
- 3 x, 1/3 I O - 1/ 3 2/3 O O
O
O
x,
x,
-2
- 4 /3
O
O
O
O
G
- 2/ 3 1/3
1
O
1 O
1
Como xs = - 2 = mln {x} = min{ --2, - 4 /3) sale de la base la variable x s. El único
i~ <O
término de la fila de Xs que es negativo es YS) . Por tanto este elemento es el pivote y
entra en la basc la variable X) .
Análisis de la so lución óptima 241
X, x, Xl x, x, x,
z -7 O O O - 5/ 3 -1 /3 O
x, 2 O O O 1/3 2/ 3 O
x, 1 1 O O 1/ 3 - 1/3 O
Xl 2 O O 1 - 1 - 1 O
x, O O O O - 1/3 - 2/3 1
Tenemos una solución primal factible y dual factible por lo cual es una solución ópti-
ma. El nuevo programa de producción es XI =- 1 tonelada y X2 = 2 toneladas lo cual
proporciona un benefic io de 7 mi l euros.
EJEMPLO 2.30 Cons ideremos de nuevo el ejemplo 2.28. Supongamos que se intro-
ducen los cambios que se indican a continuación.
2 1 1) ' 2 4 2
r,, -c, = ( 1•-400)
,. - - - - 1
( 3' 3' • 3 - - - 0= - - +
3 3 - - -
3
Como zJ -CJ > O la solución actual deja de ser óptima. Entonces hay que seguir
optim izando a partir de la última tabla previa a la modificación de la primera fila.
-4 - 1 O O O O
x, x, x, x, x, x,
z - 44 /3 11 O 2/3 - 7/3 O O
- 1 x, 4 /3 11 I @ - 1/ 3 O O
- 4
11
.x," 10/3
3
1
O
O
11
- 1/3
- 1
2/3
1
O
1
O
O
11 Xl. 2/ 3 O 11 - 2/3 1/3 O 1
x, x, x, x, x, x,
z - 16 O - 1 O -2 O O
x, 2 O 312 1 - 1/ 2 O O
x, 4 1 1/2 11 1/ 2 O O
x, 5 O 3/2 11 1/2 1 O
x, 2 O 1 11 O O 1
Supongamos que se añade una variable al prob lema. En es te caso está cla ro
qu e el programa óptimo de base actua l sigue siendo un programa de hase del
nuevo problem a, con valor nulo para la nueva varia ble, pero puede no ser ya
óptim o. La adición de una variab le .x;¡ -t I quie re decir que se añade a la matriz
A una nueva columna an t-l Y al vector e una n ueva componente Cñ¡.¡ . Las
consec uencias de añadir esta nueva variable se deducen fácilmente si se conoce
la m atriz inversa H- 1 • En efecto,
• Si diB- lan+ 1- C" t l > 0, entonces se mej ora el valor de la fun ción ob-
jetivo introduciendo la variable ~ +t en la base. Para ello se aplica el
algoritmo del simp lex a la última tabla completada previamente con un a
nueva columna correspondiente a la variable añadida.
a) Supollg<llJlOS 'IU<" 1<1 cmprcse esl.; pensando en labriC<lr un nuevo producto 1')
¡
que IIcc<.'silll wncllldas de c.ld;l una de las lI !<llen aS"rimlls A y ¡¡ por rondad;1
producid'l y 'lile le tmcc la emll" I.' renci.1 .1 Jos otros dos productos de modo que
la diferencia curre tu cmltid¡Jd dcm;lIId.1da de 1'2 y 1.1s dc J'. y Ij j Ull w.'i no es
superior iI 1111;1 Ilttidad. 1.<J eompiltiíll picnsa ohrctler de /1) ltll beneficio deí
mil cer os por roncl.1d.1. ¿l lllbcl que f.,bric.1r el " nxluc1o J}J ();Ira obtener más
bcndido?
el coeficiente Z7 - "1,
z, - C7 - c!B- l a 7 - c7
2 1
3
- - -3 O O -
3
1 2 4
-- - O O 3
= ( - 3,-2, 0,0) 3 3 -4 -( D
- 1 1 1 O - 1
2 1
- -3 -
3
O 1 O
1
-
4
1
-
- (- 3, - 2, 0, 0) 4
- 1
- (- ~)
1
-
4
5 3 1
- --4 + -2 - -4
Por tanto como Z7 - C7 > o. al introducirx i en la base se obtendrá un valor mejor para
la función objetivo. Si realizamos la correspondiente iteración obtenemos las tablas
siguientes:
- 3 -2 O O O O - 3/ 2
x, X, X, X4 X, X, X,
z 38/3 O O - 1/3 - 4/ 3 O O 1/ 4
- 2
- 3 X,
X, 4/ 3 O 1 2/3 - 1/3 O O (3
10/3 1 O - 1/ 3 2/ 3 O O 1/4
O X, 3 O O - 1 1 1 O - 1
O X, 2/3 O O - 2/ 3 1/ 3 O 1 - 1/ 4
X, X, X, X, X, X, X,
z - 14 O - 1 - 1 - 1 O O O
X, 1M 3 O 4 8/ 3 - 4/ 3 O O 1
X, 2 1 - 1 - 1 1 O O O
x~ 25/3 O 4 5/3 - 1/ 3 1 O O
X, 2 O 1 O O O 1 O
EJEMPLO 2.32 Consideremos una vez más el ejemplo 2.28 y la situación siguiente.
el coeficiente Z2 - cz
I
I - -2 O O
1 4
O - O O 3
Z2 - e 2 - (0, - 4,0,0) 2 - (- 1)
1 1
O - 1 O 1
2
O O O 1
5
2
3
(0, - 4,0,0) 2 - (- 1)
5
2
1
- 6 + 1~- 5< O
La modi fi cación introducida supo ne que hay que añadir al problema una nueva restric-
ción. Xl < 4. La solución óptima actua l XI = \0 , X2 = ~ cumple la nueva restricción
ya que XI = ~ < 4. Por tanto la solución actual sigue siendo ó ptima. L.' hase puede
co mpletarse con una variable de holgura XI! = 4 - Jf
= j.
x, x, x, X4 x, x, x,
z -38/ 3 O O - 1/ 3 - 4/ 3 O O O
Xl 4/3 () 1 2/3 - 1/ 3 () () ()
x, 10/3 1 O - 1/3 2/3 () O ()
x, 3 O O - 1 1 1 O O
x, 2/3 O O - 2/ 3 1/ 3 O 1 O
x, - 1/3 O O 1/3
G O O 1
,
248 UNIDAD DIDACTICA 2 Algoritmos de programación lineal
X, X, X3 x, x, X6 X8
z - 12 O O - ] O O O - 2
x, 3/2 O 1 1/ 2 O O O - 1/ 2
x, 3 1 O O O O O 1
x, 512 O O - 1/ 2 O 1 O 3/2
X6 112 O O - 1/ 2 O O 1 112
x, 1/2 O O - 1/ 2 1 O () - 3/ 2
dados por xB + ()B - t e¡ , es decir, xH + OSI donde hemos denotado ~ = s:' ej.
e
Si hacemos variar a partir dc cero para valores positivos o negativos se dctcr-
mina un valor negativo el o positivo 9.-.. para el cual una componente del vector
xB + OSI pasa a ser negativa. El campo de variación del elemento del segundo
miembro es entonces [h¡ + e/ ,b; + es] . Para estos valores extremos del campo
de variación del elemento del segundo miembro, cl valor de la función obje-
tivo es cf1 (x" + OB- 1e l ) = Z + ecHB -1 e¡ y si representamos I¡ = c!B --1e¡ a la
i-ésima componente del vector fila ¿ S -I resulta que el campo de variación
de la función objetivo es [z + B¡1;,z + Osi;].
En el caso de que en la base óptima la variable de índice i corresponda a una
variable de holgura o a una variable artificial, el análisis se simplifica haciendo
innecesario el cálculo anterior. En erecto,
Análisis de la solución óptima 249
"<> -
2 -J/.
'x
"",')'"
. '""" :--':" o/1','
' <l' '-',
() "-'----;,---.~_.r- \-,-----,----"'''''',__
o 2 3 5 .r 1
Iteración 1
- 5 -6 O O
Xl X, X, X,
Z O 5 6 O O
O
O
X,
x,
18
7
3
2
0 O
l
O
O
1
Iteración 2
Xl X, X, X,
z - 27 1/ 2 O - 3/2 O
-6 x, 9/2 3/ 4 1 1/ 4 O
() x, 5/2 5/4 O - 1/ 4 1
Iteración 3
X, x, x, x,
z - 28 O O - 7/ 5 O
-6 x, 3 O 1 215 -3/5
-5 Xl 2 1 O - 1/ 5 415
La última tabla muestra la solución óptima. En ella podemos ver que la hase óptima
cs !J = (a2,tll) = (43
2)I. y suinvcrsa xv -e ( 2/5
- 1/ 5 -43/
155) . Nos planteamos
ahora las cuestiones siguientes:
a) ¿Para qué rango de valores de b 1 la matriz B sigue siendo la base óptima?
b) ¿Para qué rango de valores de b2 la matri/' B sigue siendo la base óptima?
Ha de ser x H + OS-l e ] ~ Opor lo que
2
3 f- - 8
(O)< (3)
O
( 215 - 3/ 5) ( 1)
2 + 8 - 1/ 5 415 O =
5
2 - -8
I
5
de 10 que se deduce que - li < 6 < 10. Por tanto 18 ·- '5 b1 < 18 -l- 10, o equiva- 'i
lentemente 'lf< b1 < 28. Por otra parte también tiene que ser xB -t- 9S- l e2 > O, por
lo que
3
3- - 8
(O
) < (3)+ (-2/1/55
() - 2 8
- 3/ 5)
415
(O
)1 __ 5
4
2 -j -8
5
Análisis de la solución óptima 251
/1 '= c 8 H_ ] el :::" (
- 6, - 5 )(2/5
- 1/5
por lo que
e::
en donde es un subvcctor de ep cuyas componentes se corresponden con las
columnas de 8 . Para O = O es Zj - ej < O. Haciendo varia r O a partir de cero
para valores positivos () negativos se determina un valor negativo 1I o positivo
252 UN If)A [) DIDÁ CTICA 2 Algoritmos dc programacióo lineal
6 -
o
o I 2 3
"'igur~ 2.12
a) Modificación de el
4
Oprimo
I
<'( 12. 6)
o
o I 2 J
FI2u ra 2,13
Análogamente
El programa actual seguirá siendo óptimo en tanto en cuanto los Z j - ej sigan siendo
no nega tivos. es decir ~ - ~ < () y z~ - '-~. < O 10 cual ex ige que se ve rifiquen las de-
sigualdadcs - ~ - ~ o < O y - ~ - ~ o < O. Luego ha de ser O > - 7 = 9, Y también
O< ~ = Os. Por tanto el programa será óptimo para C I tal que - 12 < CI < - ~. la fi-
gura 2.13 representa geom étricamente las condiciones extremas, es decir representa la
función z = - 12x I - &2 . Análogamente si representamos z = - ~XI - 6X2 obtenemos
la figura 2.14.
b) Modificación de e 2
En este caso
, 7 ( 2/5 )
I, -C' = -5 + 0 ( 1, 0) - 1/ 5 =- 7S' 2
SO ~ O
i
dc lo que se deduce que 9 > - j = 9, Y 9 < = 9s. Así pues el rango de variación de
C2 es - 2~ < C2 <; - ~ . En los valores extremos la función objetivo es z "'- - 5x I - 2j1 X2
quc es paralela a la restricción 3x¡ t- 4X2 '-- : 18 y z '=- - 5 t" 1 - ~X2 que es paralela a la
restricción 2x 1 + X2 = 7.
254 UNIDAD DI DÁ C TI C A 2 Algoritmos de programación lineal
6-
•
_ _ Oprimo
4
, Óp¡il11U
,
3
Figur a 2.14
La repuesta a esta pregunta es inmed iata. Si ~ > O entonces -:f es 1111 pro-
grama para todo valor de B > O. Por ot ra parte, si ~ < Opa ra nl mcn os un s E 1,
=
ex iste un valor crítico O 9¡ a partir del cua l -XI deja de ser un progrmna,
puesto que al menos una componente se h '1CC negat iva. Este valo r critico es
e
Cuando supera el umbml B tenemos que reoptimizar el problema. Esto
nos conduce a la siguiente pregunta del análisis de sensibilidad.
2) ¿Qué hay que hacer cuando O pasa el valor critico & para reopumiar
el problema o bien demostror que el problema ya no es factible ?
Cuando B sobrepasa el valor O¡, una o varias variables pasan a ser negativas .
Como se sigue verificando el criterio de óptimo, se puede aplicar el algoritmo
dual del simplex.
256 UN IDA D OID ÁCTI CA 2 Algoritmos de programación lineal
Primer caso
- - ~- O
x, XIs = X01' - ~I Xue > s El - {f}
XI x le = O
en donde hemos denotado XíH (B,)-I (bo +( 10). Ahora bien, recor-
=
demos que XII = O, es decir, el valor de la variab le básica .~ es cero, y
ésta es la fi la que sale, o sea es la fi la del pivote. Al recordar las fórm ulas
Análisis de la so luci ón óptima 257
~: - S E I - {R}
-,
x, -
Xü.~ -
.;,- + 0" ~\. - O,Y,'
T XÜl - ~l
, sEl - {R}
<;,e Yu.
z, o,k
~"
Puesto que la parte de Xo qu e no depende de 9' es positiva, ya que es XI ,~ ,
y puesto que 9 < O, Y ik < O se deduce lo sigu iente
Segundo caso
Tenemos
Tabla inicial
- 3 -2 -S O O O
X, X, Xl X, X, X.
Z O 3 2 S O O O
O x, 40 1 2 ¡ 1 O O
O x, 60 3 O 0) O 1 O
O x. 30 1 4 O O O 1
Iteración I
Xl x, x, x, x, x,
z - ISO - 9/ 2 2 O O - S/ 2 O
O x, 10 - 1/ 2 0) O 1 - 1/2 O
-S Xl 30 3/2 O 1 O 112 O
O x. 30 1 4 O O O 1
Itcración 2
x, x, X, X, X, X,
z - 160 -4 O O -1 - 2 O
x, S - 1/4 1 O 1/2 - 1/ 4 O
Xl 30 3/2 O 1 O 112 O
x. 10 2 O O - 2 ¡ 1
En la última tabla se encuentra la solución óptima para (} = 0, xgo --: (X2 .X) ,X6Y :..
(5,30.1OY que co rresponde a la matriz básica Ro ~ (a2.a),a6) euya inversa es la
matriz
Puesto que ~ i. Oexiste un valor crítico a partir del cual .fo deja de ser óptimo. Ese
valor se determina por la relación
81 = M ío
5
{ - - 1' - - 3
lO } _ 10 _
- 3-- ~
'06
o sea que la base Bo es óptima en el intervalo (} E [O, ~I . El valordcl programa óptimo
para cada (3 de este intervalo es
-3 -2 -5 O O O
XI X, X, X, X, X,
z - 170 -S O O O - S/ 2 - 1/ 2
-2 X, S/3 1/4 1 O O O 1/ 4
-5 X, 100/3 3/2 O 1 O 112 O
O X, O - 1 O O 1 1/2 - 1/2
H 1= [~ I ~2 1~4 ]
1 - 1/ 2 - 1/ 2
Calculamos ahora el rango de valores de B para los cuales esta base es óptima. Calcu-
lamos pri mero H I (j de la forma siguiente:
El p rograma actual es
IS 7
- - -O
1 ~~2] + 0[ -;/4 ] =
2 4
_ [ 30 -1 0
-s 3/2 3
-s t- - O
2
IS
z ~ - 2 ( "2 7)
- 4 0 - 5 (30 H ) + 0 - 5 1 20 (3 ) = - 165 - 230
Observemos que para B = .1]0 tcnemosz - - 165 - ; JP
=- - 170. I.a base actual pcrma-
ncccrá óptima mientras siga siendo un programa, es decir; mientras B 1 6 > O. Como
8 - 16 = (- 7/ 4, 1,3/2)' 1:. O existe un valor límite para 8 a partir del cua l dejamos
de tencr un programa. Dicho limite resulta de exigir que Jt -
~ 8 > O y de esta de -
sigualdad obtenemos qu e 8 < ~o = 9l . El valor anterior se puede obtener también del
cociente
15
Mlnirno { _
.rl{'< O
X:5"'5 }_Mínimo - -2
7
_ _30 _ a
- 7 - v,
4
Es decir, para ..!j!- < O< ~o la base (az, a) ,a4) es la óptima y el programa básico es
O x, x, x, z
O -< O -<~
3 O S- O 30+ 0 - 160 - 30
10 O 30
-3 -< <- O ~_ 70 30+0
3
- 16S - - 0
- 7 2 4 2
O 30
>- no hay solución factible
7
•
262 UN ([)A D DlD ACTl C A 2 Al gorilmos de programacióo lineal
e
Supongamos, para fijar ideas, que se hace creecr a partir de cero (el easo en
e
que se hace decrecer es análogo). De forma similar al apartado 2.4.3.1 nos
planteamos a continuació n una serie de cuestiones que constituyen el anális is
de sens ibi lidad .
a) Si y'l y - Y < O, entonces la base B será óptima para todo valor e > 0.
b) Si ~j - Yj > o para al menos un j E J, entonces existe un valor crítico ~
a partir del cual Zj - Cj es positivo.
el = ~
z2-c'!k = mínimo
¡;, - )1 j ll'r 1¡»0
Análisis de la solución óptima 263
e
2) ¿Qué hay que hacer cuando $obrcpasa el valor critico Q para rcop-
rimizar el probJcm~ o bien demostrar que no existe progrdma mínimo
finito?
Primer caso
a) Si Yd: <; O para todo s pertenec iente a l, no existe programa mínimo finito
para 11 > 91•
j EJ - {k }
=
de la forma a al + (J I , ( (J I ~ o.) Por tan to, después del cambio de base
tendremos una expresión similar a la obtenida inicialmente para (J = liJ.
eJi'v¡ - ej
Asimismo, ten iendo en c uenta las fórmu las generales de cambio de base
se tiene también:
i, - e, = _ O' ~k - Yk
Yik
En resumen, efectuando el cambio de base, tenernos la'! siguientes ex-
prcstoncs
torna valores positivos por pequeños que sean. Cuando ocurre esto no existe
un intervalo no nulo de variación de O en el cual la base 1/ sea óptima (el caso
el =o es d e este tipo). En esta situación hay qu e efectuar un nuevo cambio de
base aplicando el a lgoritmo primal para (f =
e. De esta manera puede ocurrir
que sea necesaria real izar varios cambios de hase para un valo r fij o B de e, y
s up uesto que no hay c ic laj c , después de un nú mero fin ito d e pivotajes acaba
por alcanzarse o bien una hase óptima o b ien la segurida d de que no existe
programa óptimo fi nito para los va lores 8 > e.
e
Observemos fi nalmente que cua ndo varia se pasa de manera discreta de
una base a otra, pero tanto el vector e y por tanto la fu nción objetivo varían de
forma conti nua. La discusión anter ior puede resumirse de la forma sig uiente.
Sean X4. Xs Yx 6 las variables de hol gura correspondie ntes. respectivame nte. a la pri-
mera, segunda y tercera restricción. Resolvemos el problema para 9 = O mediante el
algoritmo del simplcx. La tabl a óptima es:
,
266 UNIDA D DIDA CT ICA 2 Algoritmos dc programación lineal
X, x, Xl x. x, x,
z - 160 -4 O O - 1 -2 O
x, 5 - 1/ 4 1 O 1/2 - 1/ 4 O
Xl 30 3/2 O I O 1/2 O
x, 10 2 O O -2 1 1
Co nsideramos ahora la fonna param étrica del vector de costes. De acuerdo con las
notaciones de este apartado c O- (-3, - 2, - 5,0, 0,0) Y y = (6, 2, - 5, 0.0,0), de fonna
quc
e= c' + 9r = (-3, - 2, - 5,0,0,0) + 9 (6,2, -5,0,0,0)
La form a paramétrica de los elementos 2 j ej es Zj - ej = z'} - cJ + (] (~j - "ti )'
Aquí 8. = (a" a" a, ), Por tanto c" = ( - 2,-5,0), r' ~ (2, - 5,0) Y como cense-
cucncra:
Observemos que los cálculos anteriores proporcionan los elementos de la primera fila
cuando se uti liza el vector de costes paramctrizado. En efecto, la manera habitual de
realizar dichos cálculos en el algoritmo del simplex es:
~ ~10 ! - ~ O
(-2+ 29, 5 - 59,0) l O1 O lo 1- (3- 69), -(2- 29),-(5+ 59) ,0,0,0)1
200 -2 11
91= 1 - - - 1 :- M mun
" o { - T1}
T
Análisis de la solución óptima 267
Así pues, el programa actual es óptimo para todo 6 tal que O < 6 < l . El va lor de la
func ión del objetivo en este intervalo es:
x, x, x, x, Xl x,
z - 300 - 18 O O O -5 O
x, 10 . 1/2 2 O I - 1/ 2 O
Xl 30 3/2 O 1 O 1/ 2 O
x. 30 I 4 O O O 1
La primera fil a de la tab la anterior es la fil a de los t érminos Z~I , es decir la fila co-
rrespondiente al va lor de O = 6 . = I Y a la base (U4, U3 , il6) ' Como hemos visto en
el desarrollo teórico estos coefic ientes S<1Il igua les a los z } ya qu e el z.. - C4 = O pa-
ra O = Ot - Vamos a detenemos en comprobar este hecho. La nueva mat riz básica es
Ir = (tl4, Cl },,,,,) Y su inversa es
Entonces
Z2" - C2 =2 -2·! =O
id - C5 = _ 5_ 5 1
2 2
---s
La tabla siguiente resume los cálculos anteriores
Xl
=) - ej - 4 - 140 O O - 1+ O - 2- 30 O
Para (J - I - IK O O O - 5 O
9 27 5 5
~- Cj ---- O 2 -20 () () --- - O O
2 2 2 2
Para B = 1 - 18 O O O - 5 O
i¡ - el
9 - -27 ( 1+0')
- - ~- 1 8 -- 0
27 ,
2 2 2
2 -2(1 +0 ') = -29'
O
O
5 - -S ( 1+9 ')
-- ~- 5 - - 0
5 ,
2 2 2
O
X,
- 18 - 7j. O' - l B' O O - 5-~ 8 ' O (conO ' > l)
z
o 5 30 - 160 - 1400
O O 30 - 150 - 1500
Problemas de autoevaluaci ón 271
• •
Problemas de autoevaluación ".
_,;. Il
Problema 2.4
Problema 2.3 Cons idere mos el si guiente problema de programación
Una empresa fabr ica 4 produc tos A. n, e y D. Para el lo linea l pa ram ótnco:
empica dos recursos: ma teria prima M . que le suministra
un determ inado proveedor, y tiempo . En la tahla s iguiente Problema P(k¡,k2 )
se muestran las can tidades dc materia pr ima y de tiempo Máx z = 5 X l 1- 3x 2 + 2x)
necesarias para fabrica r una unida d de cada uno de lus pro-
tlUclos, así como el be ne fi cio q ue se obtiene de la ve nta de sujeto a
una unidad de cada uno de ell os. XI + 2.q + X3 .5 kl
Solución del problema 2.1 d) La solución sigue siendo óptima pero el valor de la
El dual es variable de holgura se reduce a 825.
sujeto a