Fundamentos de Programación Lineal
Fundamentos de Programación Lineal
J. Yáñez; J. Tejada
Febrero 2013
2
Índice general
3
4
6. Dualidad 123
6.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2. Pares de problemas duales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2.1. Formulación canónica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2.2. Formulación estándar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.2.3. Formulación mixta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2.4. Formulación general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.3. Teorema fundamental de dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.4. Teorema de las holguras complementarias . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.5. Degeneración y multiplicidad de soluciones óptimas (*) . . . . . . . . . . . . . . . . . . . . 135
6.6. Interpretación económica. Análisis de la degeneración (*) . . . . . . . . . . . . . . . . . . 141
6.7. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Se introduce el problema de programación lineal a partir de varios ejemplos. La formulación básica del
primer ejemplo dará lugar al modelo estándar: el objetivo es minimizar una función lineal en las variables,
éstas no pueden tomar valores negativos y están restringidas por un conjunto de ecuaciones lineales.
Aunque el modelo estándar pueda parecer muy restrictivo, se puede adaptar a múltiples problemas en
los que las restricciones se expresen como inecuaciones lineales, o bien el objetivo sea el de maximizar
o se permita que las variables puedan tomar valores negativos. Se comprueba ası́ la gran flexibilidad
del problema de programación lineal siendo realmente la linealidad la única limitación. Se introduce la
formulación algebraica y matricial, ası́ como la notación que se desarrollará en capı́tulos posteriores y
los distintos conceptos de solución. Por último, se clasifican las distintas opciones que puede plantear la
solución de un problema de programación lineal.
1.1. Ejemplos
A continuación se presentan algunos ejemplos de problemas de programación lineal.
Se exige a la mezcla que tenga unas caracterı́sticas concretas, que se traducen en un porcentaje del
0,40 % de contenido de azufre y una densidad igual a 0,91. Se desea que el precio de la mezcla sea mı́nimo.
Los elementos fundamentales de este problema, y que caracterizan cualquier problema de programa-
ción matemática, son los siguientes:
Variable de decisión
7
8 1.1. Ejemplos
Debe identificar la mezcla y puede ser el porcentaje o la proporción de cada uno de los crudos en la
mezcla. En lo que sigue se supondrá la proporción. Es importante distinguir si la mezcla se define
por volumen o por peso.
Se introduce, por consiguiente, el vector (x1 , x2 , x3 , x4 ) ∈ IR4 que representa en cada componente la
proporción, en peso, con que intervendrán en la mezcla los crudos procedentes de Kuwait, Arabia,
Noruega y Venezuela respectivamente.
Conjunto de restricciones
Aparte de la restricción natural de que cualquier proporción no debe ser negativa
xj ≥ 0 ∀j = 1, 2, 3, 4
x1 + x2 + x3 + x4 = 1
• La densidad de la mezcla debe ser 0,91. Es importante señalar aquı́ que al ser la variable de
decisión relativa al peso, la densidad de la mezcla es su peso (x1 + x2 + x3 + x4 = 1) dividido
por su volumen, siendo el volumen de la mezcla la suma de los volúmenes de cada crudo:
x1 x2 x3 x4
+ + +
0,91 0,95 0,89 0,92
En consecuencia, si la densidad de la mezcla debe ser igual a 0,91, la restricción asociada es:
1
x1 x2 x3 x4
= 0,91
0,91 + 0,95 + 0,89 + 0,92
x1 x2 x3 x4 1
+ + + =
0,91 0,95 0,89 0,92 0,91
Función objetivo
Cada mezcla válida —verificando las restricciones anteriores— tiene asociado un coste, de forma
que la función objetivo a minimizar es el precio de cada tonelada de mezcla:
La solución de este problema de programación lineal —obtenida por procedimientos que se introdu-
cirán posteriormente— determina la variable de decisión
que permite identificar la mezcla óptima verificando las restricciones anteriores, que se obtiene mezclando
los crudos procedentes de Noruega y Venezuela en las proporciones aproximadas de 1/3 y 2/3 respecti-
vamente y añadiendo una proporción mı́nima del crudo de Arabia; el precio de esta mezcla es de 213,87
euros por tonelada.
J. Yáñez; J. Tejada 9
A continuación se introducen otros dos ejemplos del problema de programación lineal que dan lu-
gar a modelos no estándar. Estos modelos permitirán una interpretación económica del problema de
programación lineal.
Tipos de residuo 1 2 3 4 5
Proporción A 0 0.1 0.1 0.6 0
Proporción B 0.1 0.2 0.1 0.1 0.3
Proporción C 0.2 0 0.1 0.3 0.1
Coste 18 12 24 30 6
Siguiendo un esquema análogo al del problema anterior, caben destacar los siguientes elementos del
problema:
Variable de decisión
La variable (x1 , x2 , x3 , x4 , x5 ) ∈ IR5 identificará la cantidad, medida en toneladas, de residuos
recogidos semanalmente de cada tipo.
Conjunto de restricciones
En este problema, las restricciones deben asegurar la producción de cada uno de los tres productos.
Considerando que demanda debe ser satisfecha, cada una de las restricciones debe ser especificada
con una desigualdad del tipo mayor o igual ; el posible exceso de producción se verá penalizado en
la función objetivo, que tenderá a ajustar aquélla a la demanda.
Evidentemente, las cantidades de residuo recogido deben ser no negativas
xj ≥ 0 ∀j = 1, 2, 3, 4, 5
Hay tres restricciones relativas a A, B y C, que determinan que las toneladas de cada producto que
se pueden obtener del transporte de (x1 , x2 , x3 , x4 , x5 ) toneladas de residuo de cada tipo satisfacen
la demanda:
A
0,1x2 + 0,1x3 + 0,6x4 ≥ 100
B
0,1x1 + 0,2x2 + 0,1x3 + 0,1x4 + 0,3x5 ≥ 80
C
0,2x1 + 0,1x3 + 0,3x4 + 0,1x5 ≥ 60
10 1.1. Ejemplos
Función objetivo
Hay que penalizar el coste de transporte, por lo que la función objetivo a minimizar es
que representa el coste, en euros, del transporte semanal de los residuos desde el lugar de procedencia
hasta la planta de reciclado.
La solución de este problema de programación lineal permite calcular la variable de decisión óptima
que determina el transporte de 166,67 toneladas de residuos del tipo 4 y 211,11 toneladas del tipo 5. El
coste mı́nimo de la operación es 6266,67 euros.
Tipos de Abono A B C D E
[Link]ı́micos / [Link] 0.3 0.7 0.9 1.5 2
Energı́a / [Link] 0.9 1.2 1.3 2 2.5
Se desea saber qué cantidad de abono de cada tipo hay que producir para maximizar el beneficio,
teniendo en cuenta las restricciones materiales y energéticas.
Variable de decisión
El vector (x1 , x2 , x3 , x4 , x5 ) ∈ IR5 identificará la cantidad de toneladas de abono producido de cada
tipo.
Conjunto de restricciones
Las cantidades producidas de cada abono deben ser no negativas:
xj ≥ 0 ∀j = 1, 2, 3, 4, 5
Además, hay dos restricciones relativas al lı́mite de los dos recursos necesarios para la producción
de los abono:
Productos Quı́micos:
Energı́a:
0,9x1 + 1,2x2 + 1,3x3 + 2x4 + 2,5x5 ≤ 20000
Función objetivo
Hay que maximizar el beneficio por la producción de cada tipo de abono:
La solución
(x∗1 , x∗2 , x∗3 , x∗4 , x∗5 ) = (14285,720, 0, 0, 0, 2857,143)
de este problema de programación lineal determina la producción óptima de abonos, que consiste en
producir 14285,720 toneladas de abono del tipo A y 2857,143 toneladas del tipo E. El beneficio obtenido
es de 257142, 91 euros.
M in c1 x1 + . . . + cn xn
Con la notación anterior, cualquier ejemplo del problema de programación lineal se caracteriza por
los parámetros (n, m, A, b, c).
1. El valor de cada variable xj representa el nivel de la actividad j-ésima, con j ∈ {1, . . . , n}.
3. Cada componente bi del vector de términos independientes representa la cantidad del recurso i-ésimo
disponible para el proceso de producción.
4. Cada elemento aij de la matriz A representa la cantidad del recurso i-ésimo consumido en la
producción unitaria de la actividad j-ésima.
La interpretación económica del problema de programación lineal justifica los nombres de vector de
oferta o vector de demanda para el vector b, ası́ como matriz tecnológica para la matriz A, al identificar
ésta las relaciones entre los niveles de actividad y los recursos utilizados en su producción.
ó (
2x1 + 3x2 − 4x3 ≤ 5
−2x1 − 3x2 + 4x3 ≤ −5
14 1.4. Equivalencia entre los distintos modelos
Análogamente, una inecuación se puede transformar en una ecuación añadiendo una variable adicional,
que se denomina variable de holgura. Ası́, por ejemplo, la inecuación
2x1 + 3x2 ≤ 6
es equivalente a
2x1 + 3x2 + xh = 6
es equivalente a
x1 − x2 − xh = 5
exigiendo también xh ≥ 0.
En cualquier caso, dependiendo de que la variable de holgura xh sea positiva o nula, la desigualdad
asociada se verifica estrictamente o en el lı́mite, respectivamente. Obsérvese, además, que el número de
variables del problema ha aumentado en uno, puesto que la variable de holgura se incorpora en el modelo
igual que las otras variables con un coeficiente nulo en la función objetivo.
Las variables de holgura son muy importantes en programación lineal, no sólo desde un punto de vista
técnico al convertir inecuaciones en ecuaciones, sino también por su significado, puesto que recogen la
”holgura”de una restricción en forma de desigualdad, sea ésta del tipo ≤ ó ≥. Además, la introducción de
las variables de holgura puede simplificar sustancialmente la formulación del correspondiente problema.
En muchos problemas es natural exigir que las variables que intervienen en el mismo sean no negativas,
es el caso del ejemplo de la sección 1.1.1, en el que la variable identifica proporción con que interviene
cada crudo en la mezcla. Cuando no sea éste el caso bastará sustituir la correspondiente variable por la
diferencia de dos variables no negativas.
Es importante destacar esta propiedad, puesto que el algoritmo del simplex, que se verá más adelante
y que resuelve el problema de programación lineal, exige que las variables sean no negativas.
El proceso de transformación de una variable no restringida en signo como diferencia de dos variables
no negativas es el siguiente: Si xj es la variable no restringida, se puede expresar como
xj = x+ −
j − xj x+ −
j , xj ≥ 0
· · · + cj x+ −
j − cj xj + · · ·
· · · + aij x+ −
j − aij xj + · · · ∀i ∈ {1, . . . , m}
J. Yáñez; J. Tejada 15
Conviene observar que una solución x puede tener alguna componente negativa.
Se asocia ası́ al conjunto de decisiones válidas del problema el conjunto de soluciones factibles de P ,
que se denota por
S = {x ∈ IRn / Ax = b; x ≥ 0}
Definición 1.3 Una solución óptima es una solución factible que minimiza la función objetivo.
El objetivo, pues, de un problema de programación lineal es determinar una solución óptima. Para
un problema P , esta solución óptima puede no ser única, puede no existir o incluso puede que no exista
ninguna solución factible. Todas estas situaciones se describen a continuación a partir de ejemplos.
M in x1 + x2
sujeto a 2x1 + 3x2 = 6
xj ≥ 0 ∀j = 1, 2
En la figura 1.1 se representan en IR2 el conjunto de soluciones factibles S como el segmento que une
los puntos (0, 2) y (3, 0); la solución óptima x1 = (0, 2); un representante de la familia de curvas de nivel
16 1.5. Solución del problema. Clasificación
x2
x1
2 ✠
3 x1
—en este caso rectas— con igual valor en la función objetivo; y, por último, la dirección de descenso de
estas curvas de nivel.
La solución x1 se puede obtener gráficamente sin más que buscar la curva de nivel de menor valor
que interseca con el conjunto factible.
M in x1 + 3x2
M in 2x1 + 3x2
sujeto a 2x1 + 3x2 = 6
xj ≥ 0 ∀j = 1, 2
En el caso en que el óptimo se alcance en dos o más puntos, se alcanza también en el segmento que
los une. Se dice entonces que el problema tiene solución óptima no única.
En el ejemplo 1.2, el óptimo se alcanza en todo el segmento que une x1 y x2 .
En cualquiera de los casos anteriores, se dice que el problema de programación lineal tiene solución
óptima.
El ejemplo 1.1 puede ser resuelto gráficamente al ser n = 2. Obviamente, para valores de n > 3 tal
representación no es posible. Al considerar modelos no estándar, con recintos definidos por inecuaciones
de cualquier signo, el parámetro n al que hace referencia el modelo estándar equivalente incorpora el
número de variables de holgura.
J. Yáñez; J. Tejada 17
x2 x2
1 1
proyección
✲
1
1 x1 x1
xh 1
La representación gráfica en estos casos es posible siempre que el número de variables —excluidas
las de holgura— sea inferior o igual a tres. La representación en IR2 o IR3 hay que considerarla como la
proyección del conjunto S ⊂ IRn al considerar sólo las dos o tres primeras coordenadas de cada solución
factible.
Los siguientes ejemplos ilustran esta situación:
M in −x1 − x2
sujeto a x1 + x2 ≤ 1
xj ≥ 0 ∀j = 1, 2
Al considerar la variable de holgura xh , el conjunto S ⊂ IR3 asociado a las variables x1 , x2 y xh es el
hiperplano que pasa por los puntos (1, 0, 0), (0, 1, 0) y (0, 0, 1).
Al considerar el conjunto de soluciones factibles del modelo original, sin considerar la variable de
holgura, se define un recinto en IR2 . Este conjunto es la proyección del conjunto S ⊂ IR3 sobre las dos
primeras coordenadas. En la figura 1.2 se representan ambos conjuntos.
M in −x1 − x2
sujeto a −x1 + x2 ≤ 2
3x1 + 5x2 ≤ 15
3x1 + x2 ≤ 9
xj ≥ 0 ∀j = 1, 2
La figura 1.3 representa en IR2 al conjunto S como el polı́gono acotado por los vértices O, A, B, C y
D. Este conjunto de IR2 es la proyección del espacio de IR5 definido por las variables x1 , x2 y las variables
de holgura xh1 , xh2 y xh3 sobre las dos primeras coordenadas.
x2
✯
B ☛
❫
A C
✙
S
O D
x1
x2
-3
x1
-2
M in x1 + x2
sujeto a −2x1 − 3x2 = 6
xj ≥ 0 ∀j = 1, 2
La figura 1.4 representa el conjunto S = ∅ al ser la intersección del conjunto de soluciones −2x1 −
3x2 = 6 con el primer cuadrante x1 , x2 ≥ 0 el conjunto vacı́o.
x2
S
✒
x1
M in −x1 − x2
sujeto a −2x1 + 3x2 = 6
xj ≥ 0 ∀j = 1, 2
donde se observa que el conjunto S —la intersección de la recta −2x1 + 3x2 = 6 y el primer cuadrante—
es no vacı́o.
En la figura 1.5 se observa que, en la medida en que se avanza por la semirrecta asociada a S
incrementando x1 y x2 la función objetivo se hace menor que cualquier cota prefijada.
En estos casos se dice que el problema de programación lineal tiene solución no acotada.
Cuando es el caso de solución no acotada, el conjunto de soluciones factibles S es no acotado. La
implicación inversa, sin embargo, no es cierta; puede darse el caso de existencia de solución óptima
estando el conjunto S no acotado. Esta situación se ilustra con el siguiente ejemplo.
Ejemplo 1.7 El siguiente problema de programación lineal tiene solución óptima y, sin embargo, el
recinto S de soluciones factibles no está acotado.
M in 3x1 − x2
sujeto a −x1 + x2 ≤ 2
x1 − 2x2 ≤ 2
xj ≥ 0 ∀j = 1, 2
En la figura 1.6 se observa que el óptimo es único y se alcanza en x̄t = (0, 2) aun cuando el conjunto
S es no acotado.
20 1.6. Ejercicios propuestos
x2 ❘
x1
a)
M in 2x1 − 3x2 + x3
sujeto a x1 + 2x2 − x3 ≥ 7
2x1 + x3 ≤ 8
xj ≥ 0 ∀j = 1, 2, 3
b)
M ax x1 + 2x2 − 3x3
sujeto a x1 + x2 + x3 ≥ 10
3x1 − 2x2 + x3 ≤ 5
+ x2 − 2x3 = 5
x1 ≥ 0
xj cualquiera ∀j = 2, 3
c)
M in | x1 − x2 + x3 |
sujeto a 10x1 + 15x2 − 5x3 ≥ 35
200x1 + 150x3 ≤ 500
xj ≥ 0 ∀j = 1, 2
|x3 | ≤ 3
d)
M in {M ax{2x1 − x2 ; x1 + x2 }}
sujeto a 2x1 + 3x2 ≤ 6
xj ≥ 0 ∀j = 1, 2
J. Yáñez; J. Tejada 21
e)
M ax {M in{2x1 − x2 ; x1 + 2x2 ; 3x1 + x2 }}
sujeto a x1 + x2 ≥ 100
xj ≥ 0 ∀j = 1, 2
f ) Dado el recinto
R = {(x1 , x2 ) ∈ IR2 / 2x1 + 3x2 ≤ 6; x1 , x2 ≥ 0}
{(xi , yi ) / i = 1, . . . , n}
x 0 3 7
y 3 5 8
a)
M ax x1 + x2
sujeto a −x1 + 2x2 ≤ 2
x1 + 2x2 ≤ 6
3x1 + x2 ≤ 12
x2 ≥ 0
b)
M in −3x1 − 3x2
sujeto a x1 + x2 ≤ 6
5x1 + 2x2 ≤ 10
xj ≥ 0 j = 1, 2
22 1.6. Ejercicios propuestos
c)
M in 12x1 − 3x2
sujeto a −4x1 + x2 ≥ 4
6x1 + x2 ≥ 6
xj ≥ 0 j = 1, 2
d)
M in −3x1 + x2
sujeto a x1 + x2 ≥ 0
2x1 + x2 ≤ 2
x2 ≥ 0
e)
M in x1 − 3x2
sujeto a −x1 + x2 ≤ 3
x2 ≥ 2
xj ≥ 0 j = 1, 2
f)
M in x1 − 2x2
sujeto a −2x1 + x2 ≤ 2
2x1 + x2 ≥ 4
4x1 + x2 ≤ 4
xj ≥ 0 j = 1, 2
3. Identificar la variable de decisión, las restricciones asociadas y la función objetivo de los siguientes
problemas. Plantear los correspondientes modelos de programación lineal.
Si se dispone del software apropiado, utilizarlo para resolver los problemas e interpretar los resul-
tados obtenidos.
a) Una refinerı́a de petróleo va a producir un nuevo tipo de gasolina mezclando las gasolinas
que resultan de procesar diferentes tipos de crudo. Los crudos de origen son cuatro y tienen
distinta composición. Para simplificar el problema se supone que cada tipo de gasolina tiene
un porcentaje distinto de los aditivos A, B y C. La tabla siguiente indica estos porcentajes y
el precio unitario para los cuatro tipos de gasolina:
ADITIVOS PRECIO
A B C
1 80 10 10 .43
TIPOS 2 30 30 40 .31
GASOLINA 3 70 10 20 .47
4 40 50 10 .37
Las exigencias del mercado imponen que la gasolina que se va a producir debe tener al menos
el 60 % del aditivo A y no más del 30 % del aditivo C.
Determinar la mezcla que producirá la gasolina con estas especificaciones y cuyo precio sea
mı́nimo.
b) Una empresa produce tres tipos de productos: A, B y C. El proceso de producción de todos
ellos implica tres etapas E1 , E2 , E3 y E4 . La tabla adjunta identifica el tiempo, en minutos,
que necesita cada uno de los productos en cada etapa.
J. Yáñez; J. Tejada 23
PRODUCTO
ETAPA A B C
E1 12 18 21
E2 7 8 10
E3 25 30 40
E4 7 8 12
Para cada una de las etapas del proceso de producción dispone de (70, 50, 200, 50) horas se-
manales.
La siguiente tabla especifica para cada producto los costes de manufactura y materias primas,
ası́ como el precio de venta.
PRODUCTO
A B C
Coste de manufactura 15.00 18.00 19.50
Coste de m.p. 21.00 21.00 25.00
Precio de venta 65.00 73.00 80.00
COMPOSICIÓN
CRUDO I II III
A .60 .20 .20 200
B .40 .10 .35 190
C .50 .20 .20 210
D .60 .15 .30 205
El coste de cada uno de los piensos A, B y C es, respectivamente, de 0.10, 0.28, y 0.75 euros
por kilo. Se necesitan 100 kilos de alimento diariamente y la mezcla obtenida debe verificar las
siguientes restricciones:
24 1.6. Ejercicios propuestos
ACCIÓN
AÑOS A B C
5 145 80 50
10 65 40 95
15 0 200 215
Debido a compromisos financieros adquiridos previamente, el inversor necesita recuperar en
los perı́odos de tiempo de 5, 10 y 15 años las cantidades de 70000, 60000 y 30000 euros
respectivamente.
Determinar la polı́tica óptima de inversiones:
1) Sin considerar la devaluación del dinero a lo largo del tiempo.
2) Considerando que un euro actual equivale a (0,80, 0,60, 0,35) euros en los siguientes (5, 10, 15)
años respectivamente.
f ) Una empresa fabrica dos productos diferentes P1 y P2 a partir de dos materias primas M1
y M2 que posee en la cantidad de 5000 y 7000 unidades, respectivamente. Para fabricar una
unidad de P1 hacen falta 2 u. de M1 y 6 u. de M2 , mientras que, para fabricar una unidad
de P2 , hacen falta 5 y 3 unidades, respectivamente. Una unidad de producto P1 se vende a 12
euros y una unidad de P2 se vende a 14 euros.
El coste de fabricación de una unidad de P2 es de 3 euros y es de 4 euros para P1 .
g) Una empresa construye planchas de aglomerado a partir de maderas tropicales. Hay dos tipos
de aglomerado, A y B, cuya demanda es de 100 y 50 Tm. respectivamente. El aglomerado se
fabrica a partir de tres tipos de madera 1, 2 y 3 según unas proporciones que varı́an con el
tipo de aglomerado. Cada uno de los tipos de madera se puede conseguir a un precio diferente
dependiendo del paı́s donde se compren, Indonesia, Congo o Brasil.
Los datos anteriores se reflejan en la siguiente tabla:
i ) Un petrolero debe transportar 5000 Tm. de crudo en sus seis compartimentos estancos, cada
uno de los cuales permite almacenar 1500 Tm.
El coste de transportar el crudo depende, por cuestiones de mantenimiento y seguridad, del
compartimento donde se lleva, siendo las constantes de proporcionalidad asociadas a los seis
compartimentos las siguientes: (1,3, 1,3, 1,8,1,8, 1,4, 1,4).
Por otra parte, la carga debe estar repartida equilibradamente de forma que la diferencia entre
los compartimentos de babor (1,3 y 5) y los de estribor (2,4 y 6) no debe superar el 10 % de
la carga total. Análogamente, la diferencia entre la carga de los compartimentos de proa (1 y
2) y los de popa (5 y 6) no debe superar el 20 % de la carga total.
j ) Una empresa produce 5 pesticidas (A, B, C, D, E) a partir de 4 componentes básicos, identifi-
cados por (I, II, III, IV ), que intervienen según una proporción (pA,I , pA,II , . . . , pE,IV ).
Las autoridades regionales impiden que se utilicen en la fabricación de pesticidas más de
(cI , cII , cIII , cIV ) Kgr. diarios de las respectivas componentes.
El beneficio obtenido por cada Kgr. de pesticida producido diariamente es (bA , bB , bC , bD , bE ).
Las autoridades locales, conscientes del problema ecológico subyacente, deciden premiar con
una cantidad (aI , aII , aIII , aIV ) por cada Kgr. de cada uno de estos componentes que cada
dı́a no se utilice de los lı́mites impuestos por las autoridades centrales.
k ) Un fabricante de coches prevé que la demanda de un determinado modelo durante los próximos
10 meses es, en miles de unidades, 1, 2, 7, 6, 5, 3, 4, 5, 6, 2. Teniendo en cuenta ciertas
limitaciones en la producción, ha determinado que puede producir durante esos meses las
siguientes cantidades de coches, también en miles de unidades, 4, 5, 6, 7, 8, 7, 4, 6, 4, 3.
El fabricante dispone de un almacén con una capacidad de 5000 unidades. Actualmente tiene
2000 coches de este modelo.
Mensualmente, los costes fijos de producción son de 3000 euros y el coste de producción por
unidad es de 90 para los 5 primeros meses, y de 100 para los 5 últimos. El coste unitario por
coche y mes de almacenamiento es de 9 euros.
El problema del fabricante es planificar la producción mensual con el mı́nimo coste, atendiendo
toda la demanda prevista.
Observación: El coste fijo de producción se impone si durante un mes se produce
algo y es independiente de la cantidad producida. Para incluir este coste se necesita
la incorporación de una variable binaria.
l ) Un vendedor conoce cuál es la demanda de un determinado producto en los próximos cuatro
meses. Tiene que adquirir dicho producto a un almacén y el precio de compra por el que lo
adquiere, ası́ como el precio de venta, varı́an con el mes, según se indica en la tabla adjunta:
Para simplificar el problema, se supone que las adquisiciones y ventas se realizan al principio
de cada mes y que no se puede almacenar más de 500 unidades por falta de espacio.
Si al final del cuarto mes debe haber 100 unidades del producto en el almacén, plantear el
problema de optimización que resulta si la demanda debe ser satisfecha al menor coste posible
en los dos casos siguientes:
m) Una empresa fabrica un determinado producto en dos fábricas (F1 , F2 ) y dispone de dos
almacenes (A1 , A2 ). El coste unitario de transporte entre las fábricas y los almacenes es el
indicado en la tabla adjunta:
A1 A2
F1 3 5
F2 6 4
La demanda del producto durante los próximos cuatro meses en cada uno de los almacenes es
la indicada en la siguiente tabla:
1 2 3 4
A1 1000 1200 1400 1200
A2 1200 800 1000 1200
Cada una de las fábricas tiene una capacidad de producción mensual igual a 1000, pudiendo
aumentar a 1500 con un coste incrementado en un 25 % para la cantidad adicional. El coste
de producción varı́a con el mes y con la fábrica, según indica la siguiente tabla:
1 2 3 4
F1 30 32 32 32
F2 32 32 36 36
Cada almacén puede guardar para el mes siguiente hasta una cantidad igual a 1000, siendo 1
el coste unitario de almacenamiento.
Se trata de satisfacer la demanda de los almacenes durante los cuatro meses con el menor coste
posible.
ñ) Un almacén suministra a tres tiendas, (A,B,C), situadas en el centro de una gran ciudad. Se
supone que las calles están trazadas ortogonalmente de forma que la distancia entre dos puntos
cuyas coordenadas son x e y es
determinar la localización ideal del almacén de forma que se minimice la suma de las distancias
a las tiendas.
28 1.6. Ejercicios propuestos
Capı́tulo 2
En este capı́tulo se analiza el problema de programación lineal desde un punto de vista geométrico.
En el capı́tulo anterior se observaba cómo en un mismo problema, variando los coeficientes de la función
objetivo, se obtenı́an distintas soluciones; sin embargo, en el caso en que exista solución óptima, siempre
hay una solución óptima en un ”vértice”del conjunto S de soluciones factibles. La idea de ”vértice”se
corresponde con el concepto de punto extremo de un conjunto convexo.
Se definen los conceptos de conjunto convexo y de punto extremo. Se caracterizan los puntos extremos
del conjunto convexo S. Se demuestra asimismo que siempre que exista alguna solución factible, existirá al
menos un punto extremo. La solución factible asociada a un punto extremo de S se denominará solución
básica.
Para el caso en que S no esté acotado, se introducen los conceptos de dirección y dirección extrema
en un conjunto convexo, ası́ como la correspondiente caracterización de las direcciones extremas de S.
Termina el capı́tulo con el teorema de representación del conjunto S y sus implicaciones en el problema
de programación lineal. Todos los resultados conducentes a la demostración de este teorema, incluida la
propia demostración, se detallan en una sección independiente.
M in ct x
Ax =b
x ≥0
S = {x ∈ IRn / Ax = b, x ≥ 0}
se basa en considerar la matriz A ∈ Mm×n de restricciones como un conjunto de n vectores del espacio
vectorial IRm :
A = {a1 , a2 , . . . , an }
29
30 2.1. El conjunto de soluciones factibles (S). Solución básica factible
donde
a1j
a2j
aj =
..
∀j ∈ {1, . . . , n}
.
amj
Observación 2.1 Se supondrá que no hay redundancia en el sistema de ecuaciones asociado a la matriz
A, es decir
rg(A) = m
En el capı́tulo 4 se analizará el caso general, que debe incluir la posible redundancia del sistema de
ecuaciones.
Por ser rg(A) = m, existe una submatriz cuadrada B ∈ Mm×m no singular, es decir, |B| 6= 0. A
dicha submatriz cuadrada se la denomina base por identificar un conjunto de m vectores linealmente
independientes del espacio vectorial IRm .
En consecuencia, cualquier vector de IRm , y en particular, cualquier vector columna de A, aj con
j ∈ {1, . . . , n}, puede ser obtenido como combinación lineal de los vectores columna de una base B.
Tiene sentido, pues, el denotar como B ⊂ A la selección de una base B formada por m columnas de
la matriz A ∈ Mm×n . Se determina ası́ una partición de la matriz A según:
Ejemplo 2.1 Sea A la matriz de restricciones de un problema de programación lineal con n = 5 variables
y m = 3 restricciones :
2 3 1 −1 0
A= 0 0 0 −2 −2
3 3 0 −2 −2
Se puede comprobar que rg(A) = 3, de forma que si se elige como base
2 0 1
B = (a1 , a5 , a3 ) = 0 −2 0
3 −2 0
xt = (xtB , xtN )
siendo
xtB = (x1 , x5 , x3 ) xtN = (x2 , x4 )
Por comodidad de notación, se supondrá que las columnas de B son las m primeras
Esta hipótesis no supone ninguna restricción real, puesto que siempre se pueden reordenar las columnas
de la matriz A de forma apropiada.
A partir de la partición de las columnas de la matriz A = (B, N ), tiene sentido definir un tipo
particular de soluciones para el problema de Programación lineal.
M in ct x
Ax =b
x ≥0
se dice que x ∈ IRn es una solución básica cuando existe una base B ⊂ A, tal que las variables secundarias
son nulas, es decir:
! !
xB B −1 b
x= =
xN 0
Conviene observar que en esta definición no se ha exigido que las componentes básicas sean mayores
o iguales que cero, por lo que una solución básica no es necesariamente una solución factible. Hay que
exigirlo adicionalmente y tiene sentido, pues, la siguiente definición.
Definición 2.2 Dado un problema de programación lineal en su forma estándar, fijada una base B ⊂ A,
la solución básica asociada es una solución básica factible si verifica, además, que B −1 b ≥ 0.
La combinación lineal no negativa cuyos coeficientes suman 1 se denomina combinación lineal convexa.
Por inducción se demuestra que la combinación lineal convexa de k puntos de un convexo C pertenece
al conjunto, es decir, dados {x1 , . . . , xk } ⊂ C, para cualquier (λ1 , . . . , λk ) tal que λj ≥ 0 ∀j ∈ {1, . . . , k}
Pk
y j=1 λj = 1, se verifica:
32 2.2. Puntos extremos de S
k
X
λj x j ∈ C
j=1
Demostración:
Dados x1 , x2 ∈ S y dado un λ ∈ (0, 1) se define el vector x = λx1 + (1 − λ)x2 .
Para demostrar que x ∈ S es suficiente comprobar que x ≥ 0, lo que se concluye al serlo x1 y x2 y,
por otra parte, hay que comprobar que Ax = b :
Por definición de convexidad, dados dos puntos de un convexo, cualquier punto situado en el segmento
que los une, debe pertenecer al conjunto. Dicho de otra forma, el punto que resulta de la combinación
es ”soportado”por sus extremos. ¿Existen puntos que no son ”soportados”por ningún otro punto? En
un cuadrado en IR2 , por ejemplo, cualquiera de sus vértices no se puede poner como combinación lineal
convexa de puntos diferentes del cuadrado.
Con esta idea se introduce el concepto de punto extremo.
Definición 2.4 Dado un conjunto convexo C ⊂ IRn , se dice que x ∈ C es un punto extremo de C si
verifica lo siguiente:
A continuación se caracterizan los puntos extremos del conjunto de soluciones factibles del problema
de programación lineal, que coinciden con las soluciones básicas factibles.
x̄ es punto extremo de S ⇐⇒
! !
−1 x̄B B −1 b
∃B ⊂ A tal que |B| =
6 0, B b ≥ 0 y de forma que x̄ = =
x̄N 0
Demostración :
! !
−1 x̄B B −1 b
⇐ Sea A = (B, N ), donde |B| 6= 0 y B b ≥ 0 y x̄ = =
x̄N 0
Según se comentó anteriormente, las componentes básicas son las m primeras.
Supongamos que x̄ = λx̄1 + (1 − λ)x̄2 x̄1 , x̄2 ∈ S, siendo 0 < λ < 1. Descomponiendo x̄1 y x̄2 en
las componentes básicas y secundarias, se tiene:
! ! ! !
x̄B B −1 b x̄1B x̄2B
x̄ = = =λ + (1 − λ)
x̄N 0 x̄1N x̄2N
J. Yáñez; J. Tejada 33
! !
1 x̄1B x̄2B
Ax̄ = (B, N ) = Bx̄1B + N0 = b 2
Ax̄ = (B, N ) = Bx̄2B + N 0 = b
0 0
Se ha demostrado ası́ que x̄ = x̄1 = x̄2 y que, por tanto, x̄ es un punto extremo.
⇒ Sea x̄ un punto extremo de S. Sin pérdida de generalidad, se puede suponer que las coordenadas
positivas son las k primeras, de forma que
1 1 1 2
x̄ = x̄ + x̄
2 2
serı́a una combinación lineal convexa no trivial, lo que es imposible por ser x̄ un punto extremo.
Se ha llegado a una contradicción y queda demostrado ası́ que el conjunto {aj , j = 1, . . . , k} es
linealmente independiente.
!
x̄B
Ax = (B, N ) =b
0
! !
x̄B B −1 b
x̄ = =
x̄N 0
Demostración :
Al ser S no vacı́o, sea x̄ ∈ S una solución factible. Siempre se pueden reordenar las coordenadas de
forma que las k primeras, siendo 0 ≤ k ≤ n, sean positivas: x̄t = (x̄1 , . . . , x̄k , 0, . . . , 0).
Sea p = rg(a1 , . . . , ak ) el rango de los vectores columna de A asociados a estas componentes positivas.
Hay dos opciones:
p < k En este caso, {a1 , . . . , ak } es linealmente dependiente y existe una combinación lineal no nula
(α1 , . . . , αk ) 6= (0, . . . , 0) tal que
Xk
α j aj = 0
j=1
Sea r ∈ {1, . . . , k} un ı́ndice tal que αr > 0. La existencia de este ı́ndice r está garantizada al ser
el vector α 6= 0 y, en el caso en que αj ≤ 0 ∀j, serı́a suficiente con multiplicar por −1 todos estos
J. Yáñez; J. Tejada 35
k
1 X
ar = − α j aj
αr j=1
j6=r
se tiene
n
X k
X k
X k
1 X
b= aj x̄j = aj x̄j = aj x̄j − αj aj x̄r
j=1 j=1 j=1
αr j=1
j6=r j6=r
k
X αj
b= aj (x̄j − x̄r )
j=1
αr
j6=r
se deduce que x̄′ es una solución con al menos una componente nula más que x̄, puesto que x̄′r = 0.
Para garantizar que x̄′ sea solución factible hay que elegir el subı́ndice r adecuadamente; para ello,
basta observar las dos posibilidades respecto los αj :
• αj > 0
αj x̄j x̄r
(x̄j − x̄r ) ≥ 0 ⇐⇒ − ≥0
αr αj αr
x̄r x̄j
≡ M in{ /αj > 0}
αr αj
• αj ≤ 0
αj
x̄′j = (x̄j − x̄r ) ≥ x̄j ≥ 0
αr
Ası́ pues, la solución x̄′ es factible y tiene menos componentes positivas que x̄.
La demostración continúa considerando x̄ = x̄′ y volviendo al principio. Como en cada uno de los
ciclos ası́ formados disminuye, al menos en uno, el número de coordenadas positivas, el proceso
necesariamente terminará en algún momento en el caso p = k y se obtendrı́a la correspondiente
solución factible que es un punto extremo de S.
•
36 2.2. Puntos extremos de S
Ejemplo 2.2 Determinar los puntos extremos del conjunto de soluciones factibles asociadas al PPL cuya
matriz A de coeficientes y vector b de términos independientes son:
! !
1 −3 −4 5
A= b=
0 2 1 7
! ! ! ! ! !
5 31/2 5 33 5 33/5
B1−1 = ≥0 B2−1 = ≥0 B3−1 = 6≥ 0
7 7/2 7 7 7 −31/5
Sólo los dos primeros vectores tienen todas las componentes mayores o iguales que 0 y son, por tanto,
soluciones básicas factibles; geométricamente, corresponden a los dos puntos extremos del conjunto de
soluciones factibles:
31/2 33
x1 = 7/2 ; x2 = 0
0 7
Se puede observar cómo el conjunto de soluciones factibles es un segmento en IR3 , que es la intersección
de los dos planos:
x1 − 3x2 − 4x3 = 5
2x2 + x3 = 7
definidos por cada una de las restricciones. Los extremos de dicho segmento son los citados puntos extre-
mos y cualquier solución factible se puede expresar como combinación lineal convexa de ambos.
Dicho de otra forma, si al analizar todas las soluciones básicas, ninguna de ellas es factible, el problema
de programación lineal no tiene solución factible.
Hay que observar cómo a partir de los puntos extremos del conjunto S se pueden generar por combi-
naciones lineales convexas otras soluciones factibles para el problema P .
J. Yáñez; J. Tejada 37
x3
x̄
x2
x1
Ejemplo 2.3
M in x1 −x2 −x3
x1 −x2 +x3 = 1
−2x1 −x2 +x3 = 1
xj ≥ 0 ∀i = 1, 2, 3
Al analizar el conjunto de soluciones factibles de este ejemplo, cuya matriz A de coeficientes y vector
b de términos independientes son:
! !
1 −1 1 1
A= b=
−2 −1 1 1
Definición 2.5 Dado un conjunto convexo C ⊂ IRn , C 6= ∅, un vector d ∈ IRn , d 6= 0 es una dirección
de C si se verifica la siguiente propiedad:
∀x ∈ C, ∀µ ≥ 0 x + µd ∈ C
Dos direcciones de C, d1 y d2 , son equivalentes, y se denota por d1 ≃ d2 cuando sean los vectores
proporcionales con una constante positiva, es decir, d1 = αd2 , con α > 0.
38 2.3. Direcciones extremas de S
En el ejemplo 2.3 existe una dirección, dt = (0, 1, 1), que coincide con la dirección de la semirrecta
definida por el conjunto S.
d es dirección de S ⇐⇒ d ≥ 0 , d 6= 0 y Ad = 0
Demostración:
⇒ Al ser d ∈ IRn una dirección de S, debe verificarse que d ≥ 0, ya que, en caso contrario, si
existiera una componente dj < 0, considerando un µ suficientemente grande, la componente j-
ésima xj + µdj < 0 para cualquier x ∈ S y el vector x + µd 6≥ 0, contradiciendo ası́ la definición de
dirección.
Por otra parte, si el vector x + µd ∈ S ∀µ ≥ 0, debe verificarse que A(x + µd) = b ∀µ ≥ 0 y, al ser
x ∈ S, Ax = b, necesariamente debe verificarse Ad = 0.
x + µd ≥ 0
Para analizar el caso de múltiples direcciones se introduce el siguiente ejemplo, que resulta de mo-
dificar el ejemplo 1.7, cuyo recinto de soluciones factibles está representado en la figura 1.6, al incluir
explı́citamente las variables de holgura.
Ejemplo 2.4
M in 3x1 − x2
sujeto a −x1 + x2 + xh1 = 2
x1 − 2x2 + xh2 = 2
xj , xhi ≥ 0 ∀i, j = 1, 2
! ! 3
−1 1 1 0 2 −1
n=4 m=2 A= b=
c=
1 −2 0 1 2
0
0
Se puede comprobar que los vectores
1 2
1 1
d1 =
0 d2 =
1
1 0
son direcciones de S, ya que son no nulos, no negativos y verifican Ad = 0.
Cualquier combinación lineal positiva de estas direcciones es otra dirección, por ejemplo, la dirección
3
2
d3 =
1 =d +d
1 2
1
De la misma forma que se introducı́a el concepto de punto extremo de un conjunto convexo para
identificar aquellos puntos del conjunto que no se podı́an expresar como combinaciones lineales convexas
de otros puntos, se introduce el concepto de dirección extrema como aquella dirección que no puede ser
representada como combinación lineal positiva de direcciones distintas. Conviene observar que no se exige
en el caso de direcciones extremas que los coeficientes de la combinación lineal sumen 1, exigiendo sólo
que sean no negativos.
Definición 2.6 Dado un conjunto convexo C ⊂ IRn , una dirección d ∈ IRn se dice que es una dirección
extrema de C si al expresarse como:
d = µ1 d 1 + µ2 d2
siendo µ1 , µ2 > 0 y d1 , d2 direcciones de C, se concluye necesariamente que las tres direcciones son
equivalentes:
d ≃ d1 ≃ d2
A continuación, se caracterizan las direcciones extremas del conjunto S de soluciones factibles del
problema de programación lineal.
m componentes asociadas a la base, que —por comodidad de notación— se han situado al principio,
pero que en realidad hay que situar en las posiciones asociadas a las componentes de la base y en
el orden correspondiente.
n − m componentes complementarias de la base, situadas al final del vector y que son todas nulas
excepto un 1 en la posición j-ésima asociada al vector aj y que, por esta razón, se ha identificado
como el vector ej .
40 2.3. Direcciones extremas de S
Demostración :
! ! ! !
dB −B −1 aj d1B d2B
d= = = µ1 + µ2
dN ej d1N d2N
Al ser d1N , d2N ≥ 0 y µ1 , µ2 > 0, se deduce que todas las componentes secundarias, excepto la
j-ésima, son nulas, es decir:
d1t 1
N = (0, . . . , dj , . . . , 0) ∈ IR
n−m
d2t 2
N = (0, . . . , dj , . . . , 0) ∈ IR
n−m
Al ser B una base y ser 0 ≤ d 6= 0, se concluye que d1j > 0, puesto que en caso contrario existirı́a
una combinación lineal no nula de los vectores columna de B igual al vector 0. Se concluye ası́ que
d1B = −d1j B −1 aj
d2B = −d2j B −1 aj
⇒ Sea d una dirección extrema de S. Al ser dirección, d 6= 0 y, por consiguiente, sus k + 1 coordenadas
positivas, siendo 0 ≤ k ≤ (n − 1), se pueden reordenar de forma que k de ellas sean las primeras y
la (k + 1)-ésima se coloca en la posición j, j > m de forma que:
k
X
λ l al = 0
l=1
λt = (λ1 , . . . , λk , 0, . . . , 0)
d1 = d + αλ ≥ 0
d2 = d − αλ ≥ 0
que, además, son no nulos por ser dj > 0 y λj = 0. Por otra parte, al verificar
Ad1 = Ad + αAλ = 0 + 0 = 0
Ad2 = Ad − αAλ = 0 + 0 = 0
!
dB
0 = Ad = (B, N ) = BdB + aj dj
dN
!
0 0 −B −1 aj
d = dj d d =
ej
concluyendo ası́ que la dirección extrema d se puede descomponer según las condiciones del teorema.
•
42 2.3. Direcciones extremas de S
Se puede comprobar que en el ejemplo 2.3 existe una dirección extrema caracterizada por la base
B = (a1 , a2 ) y por el vector a3 según las condiciones del teorema anterior. En efecto:
! ! ! !
1 −1 1/3 −1/3 1 0
B= B −1 = B −1 = ≤0
−2 −1 −2/3 −1/3 1 −1
y se construye una dirección extrema:
0
d1 = 1
1
Considerando las componentes de este vector cambiadas de signo como las coordenadas correspon-
dientes a a1 y a2 respectivamente, y anulando las componentes no básicas excepto la correspondiente
a ah2 , que es igual a uno, se construye la siguiente dirección extrema
1
1
d1 =
0
1
!
−1 1
A partir de B2 = (a1 , ah1 ) =
1 0
Eligiendo a2 , se verifica que
! ! !
0 1 1 −2
B2−1 a2 = = ≤0
1 1 −2 −1
Una dirección proporcional a d2 , por tanto, equivalente, se podrı́a haber obtenido considerando la base
B1 y el vector ah1 . Otra equivalente se puede determinar con base (a2 , ah1 ) y el vector a1 .
Realmente, cada dirección extrema d está asociada a la combinación lineal de los vectores de la base y
un vector no básico; los coeficientes de esta combinación lineal son las componentes del vector d, puesto
que se verifica Ad = 0.
J. Yáñez; J. Tejada 43
que es el número de subconjuntos con m + 1 vectores columna de la matriz A que, siendo linealmente
dependientes al ser un espacio vectorial de dimensión m, los coeficientes de la correspondiente combinación
lineal son todos no negativos.
Observación 2.2 La demostración del teorema de representación, junto con los resultados previos ne-
cesarios, se detallan en la sección 2.5.
En el ejemplo 2.2, hay dos puntos extremos y no hay direcciones, por lo que el conjunto de soluciones
factibles se puede expresar según:
31/2 33
S = x = λ 7/2 + (1 − λ) 0 / 0 ≤ λ ≤ 1
0 7
En el ejemplo 2.3, que sólo tiene un punto extremo y una dirección extrema, el conjunto de soluciones
factibles se puede expresar según:
0
0
S = x = 0 + µ 1 / µ ≥ 0
1 1
En el ejemplo 2.4, hay tres puntos extremos, asociados a las bases (ah1 , ah2 ), (a1 , ah1 ) y (a2 , ah2 ), y dos
direcciones extremas, d1 y d2 , por lo que el conjunto de soluciones factibles se puede expresar según:
44 2.4. Teorema de representación de S
x2 −−−→
(1, 1)❃
(0,2)
−−−→
✶
(2, 1)
(0,0) (2,0) x1
0 2 0 1 2
0 0 2 1 1
S = x = λ1 + λ2
+ λ3
+ µ1
+ µ2
2 4 0 0 1
2 0 6 1 0
siendo todos los coeficientes λ1 , λ2 , λ3 , µ1 , µ2 mayores o iguales a cero y sumando los lambdas uno.
Proyectando los tres puntos extremos y las dos direcciones extremas sobre las dos primeras coordenadas
se tienen los tres vértices y las dos lı́neas que delimitan la región factible S del ejemplo 2.4; ver la figura 2.2.
Demostración:
El mı́nimo se alcanzarı́a asignando a µj el valor 0, en el caso de que existan direcciones extremas, y
λs = 1 , λi = 0 ∀i 6= s
siendo
I ∗ ≡ s ∈ {1, . . . , k} / ct xs = M in{ct xi /1 ≤ i ≤ k}
J ∗ ≡ r ∈ {1, . . . , l} / ct dr = 0
M in ct x
Ax =b
x ≥0
basándose en la proposición 2.2 y en los corolarios 2.2 y 2.3, del teorema 2.3, se propone el siguiente
algoritmo que determina, si es el caso, una solución óptima:
A continuación se aplica el algoritmo basado en el teorema de representación al ejemplo 2.4, que tiene
tres puntos extremos (k = 3) y dos direcciones extremas (l = 2):
0 2 0 1 2
0 0 2 1 1
x =
1
x =
2
x =
3
d =
1
d =
2
2 4 0 0 1
2 0 6 1 0
Variando el vector de costes se plantean distintos problemas de programación lineal:
46 2.4. Teorema de representación de S
1. ct = (2, −3, 0, 0)
1 2
1 1
t 1
c d = (2, −3, 0, 0) = −1 < 0 t 2
c d = (2, −3, 0, 0) =1≥0
0 1
1 0
2. ct = (4, −3, 0, 0)
1 2
1 1
ct d1 = (4, −3, 0, 0)
0 =1≥0 ct d2 = (4, −3, 0, 0)
1 =5≥0
1 0
Existe solución óptima que se determina en el punto extremo que alcance el mı́nimo de la función
objetivo:
0 2 0
0 0 2
ct x1 = (4, −3, 0, 0)
2 =0 ct x2 = (4, −3, 0, 0)
4 =8 ct x3 = (4, −3, 0, 0)
0 = −6
2 0 6
El mı́nimo es único I ∗ = {3}. Al ser J ∗ = ∅, la solución óptima del problema es el conjunto formado
por un único punto:
0
2
S =
∗
0
6
3. ct = (0, 1, 0, 0)
1 2
1 1
ct d1 = (0, 1, 0, 0)
0 =1≥0 ct d2 = (0, 1, 0, 0)
1 =1≥0
1 0
Existe solución óptima que se determina en el punto extremo que alcance el mı́nimo de la función
objetivo:
0 2 0
0 0 2
ct x1 = (0, 1, 0, 0)
2 =0 ct x2 = (0, 1, 0, 0)
4 =0 ct x3 = (0, 1, 0, 0)
0 =2
2 0 6
J. Yáñez; J. Tejada 47
El mı́nimo no es único, siendo I ∗ = {1, 2}. Al ser J ∗ = ∅, la solución óptima del problema es el
conjunto:
0 2
2 − 2λ
0
0
0
S = λ + (1 − λ)
∗
=
4 − 2λ
; λ ∈ [0, 1]
2 4
2 0 2λ
4. ct = (1, −1, 0, 0)
1 2
1 1
t 1
c d = (1, −1, 0, 0) =0≥0 t 2
c d = (1, −1, 0, 0) =1≥0
0 1
1 0
Hay que observar que existe una dirección extrema d1 verificando ct d1 = 0, por lo que J ∗ = {1}.
0 2 0
0 0 2
t 1
c x = (1, −1, 0, 0) =0 t 2
c x = (1, −1, 0, 0) =2 t 3
c x = (1, −1, 0, 0) = −2
2 4 0
2 0 6
0 1
µ1
2
1
2 + µ1
S =
∗
+ µ1
; µ1 ≥ 0 = ; µ1 ≥ 0
0 0
0
6 1 6 + µ1
Aunque teóricamente el problema de programación lineal está resuelto con este algoritmo, en la
práctica supone la determinación de todas las posibles bases B ⊂ A y la posterior comprobación de cuántas
de ellas proporcionan soluciones básicas. Considerando que el número de bases crece exponencialmente
con el numero de variables y ecuaciones, el algoritmo puede ser muy ineficiente computacionalmente. Por
ejemplo, si n = 50 y m = 15, el número de bases a comprobar es igual a
!
50
= 2250829575120
15
es decir, hay que invertir más de 2 billones de matrices con 15 filas y columnas.
En el siguiente capı́tulo se detalla un algoritmo, el algoritmo del simplex, que de una forma muy
eficiente resuelve el problema de programación lineal.
48 2.5. Demostración del teorema de representación (*)
Lema 2.1 Dado un espacio normado de dimensión n, en particular IRn , con la norma euclı́dea
q
k a k= a21 + . . . + a2n
2 2 2 2
k a + b k + k a − b k = 2k a k + 2k b k
2 2 2
k a + b k = k a k + k b k + 2at b
2 2 2
k a − b k = k a k + k b k − 2at b
Teorema 2.4 Sea S un conjunto convexo cerrado de IRn y sea y 6∈ S, entonces existe un único punto
x ∈ S que hace mı́nima la distancia de S a y.
Además, este punto x se puede caracterizar por la siguiente desigualdad (x − x)t (x − y) ≥ 0 ∀x ∈ S
existe una sucesión {xk } ⊂ S de modo que k y −xk k→ γ. Se demostrará que la sucesión {xk } ası́ definida
converge al punto x ∈ S.
Algunos aspectos de esta demostración se ilustran en la figura 2.3.
Primero se demuestra que la sucesión {xk } es convergente. Para ello es suficiente —al ser IRn espacio
de Banach— ver que es sucesión de Cauchy:
Por el lema 2.1, y llamando a = xk − y, b = xm − y:
k xk − xm k2 = 2 k xk − y k2 +2 k xm − y k2 − k xk + xm − 2y k2 =
xm + xk
= 2 k xk − y k2 +2 k xm − y k2 −4 k − y k2 ≤
2
J. Yáñez; J. Tejada 49
y
x̄ x̄
γ ✮ y
x̄ − y
S xk S
☛x − x̄
x
≤ 2 k xk − y k2 +2 k xm − y k2 −4γ 2
k xk − xm k→ 0
es decir, la sucesión {xk } es de Cauchy y converge a un único punto. Sea x dicho lı́mite; al ser S cerrado,
x ∈ S.
La última parte del teorema permite caracterizar este punto lı́mite:
⇐) Considerando que
x − y = (x − x) + (x − y)
se concluye que
k x − y k2 =k x − y k2 + k x − x k2 +2(x − x)t (x − y) ≥k x − y k2 ∀x ∈ S
k y − x k2 ≤k y − x k2 ∀x ∈ S
Sea x ∈ S, entonces, para cualquier λ ∈ [0, 1], y considerando que S es convexo y que x ∈ S, el
vector
x + λ(x − x) ∈ S
Dividiendo los dos miembros de la desigualdad por λ, para que sea cierta la desigualdad anterior,
es necesario que se verifique
(x − x)t (x − y) ≥ 0 ∀x ∈ S
Si fuera negativa esta expresión, bastarı́a considerar un λ > 0 suficientemente pequeño para con-
tradecir la desigualdad previa.
Definición 2.8 Dados dos conjuntos no vacı́os S1 , S2 ⊂ IRn , un hiperplano H(p, α) separa ambos con-
juntos si se verifica que S1 ⊂ H(p, α)+ y S2 ⊂ H(p, α)−
Teorema 2.5 Dado S ∈ IRn no vacı́o, convexo y cerrado y dado un punto y 6∈ S, existe un hiperplano
que los separa.
Demostración:
Al verificarse las hipótesis del teorema 2.4, existe un único punto x̄ que minimiza la distancia entre y
y S verificándose, además, que x ∈ S, y que (x − x)t (y − x) ≤ 0 ∀x ∈ S
Esta última desigualdad es equivalente a
(y − x̄)t x ≤ (y − x̄)t x̄ ∀x ∈ S
Introduciendo el vector
p ≡ y − x̄ 6= 0
y el escalar
α ≡ (y − x̄)t x̄
0 <k p k2 = pt (y − x̄)
J. Yáñez; J. Tejada 51
pt x = α
p = y − x̄
✸ y
x̄
pt x ≥ α
S ✯
✰
pt x ≤ α
pt y > α ≥ pt x ∀x ∈ S
pt s > α ≥ pt x ∀x ∈ Λ
1. pt dj ≤ 0 ∀j = 1, . . . , l, ya que si existiera un ı́ndice j0 tal que pt dj0 > 0, tomando µj0 > 0,
suficientemente grande, se obtendrı́a un punto x1 + µj0 dj0 ∈ Λ verificando
lo cual contradirı́a
pt x ≤ α ∀x ∈ Λ
2. pt xi ≤ α ∀i = 1, . . . , k
Sólo hay que considerar λi = 1 y λh = 0 ∀h 6= i y µj = 0 ∀j = 1, . . . , l.
pt x = máx {pt xi }
1≤i≤k
Al ser x un punto extremo, ∃B ⊂ A tal que, suponiendo que en B están las primeras m columnas,
!
B −1 b
x= B −1 b ≥ 0
0
!
sB
Por ser s ∈ S, se deduce que As = b y s ≥ 0. Sea s = de forma que As = BsB + N sN = b,
sN
y, por consiguiente, sB = B −1 b − B −1 N sN
Por ser pt s > pt x se verifica:
−ptB B −1 aj + pj ≤ 0
Ax̄′ = B B −1 b − λB −1 aj + λaj = b
Al sustituir en B la columna ar (puesto que x̄′r = 0) por aj se tiene una nueva base
El que B ′ sea base se garantiza al ser yrj 6= 0. Por consiguiente, x̄′ es también un punto extremo de
S por el teorema de representación.
Sólo queda, por último, llegar a una contradicción al haber supuesto que S 6⊂ Λ. La contradicción se
verifica al comprobar que este nuevo punto extremo x al ser multiplicado escalarmente por p alcanza un
valor mayor que el correspondiente a x, que era, por definición el máximo posible:
!
t t t B −1 b − λyj
p x = (pB , pN ) = ptB B −1 b − λptB yj + λpj = pt x + λ(pj − ptB B −1 aj ) > pt x
λej
•
54 2.6. Ejercicios propuestos
determinar si los siguientes conjuntos son linealmente independientes, cubren todo el espacio IR3 ,
y si forman una base:
{a1 , a3 , a4 }
{a2 , a3 , a5 }
{a2 , a3 }
{a2 , a3 , a4 , a5 }
2. Determinar cuáles de los siguientes conjuntos de IR2 son convexos. En caso afirmativo, identificar
gráficamente los conjuntos de puntos y direcciones extremos:
y el punto (0, 1), que no pertenece a ninguno de ellos, determinar, si es posible, la distancia entre
el punto y cada conjunto. Determinar, también si es posible, un hiperplano separador entre punto
y conjunto en el punto donde se minimiza la distancia anterior.
Dado el vector
2
4
3
0
x=
0
0
1
se pide:
Dado el vector
1
3
d=
1
1
se pide:
8. Sea la solución (1, 1) del recinto de IR2 determinado por las siguientes inecuaciones:
−x1 + 2x2 ≤ 4
3x1 + x2 ≤ 9
3x1 + 2x2 ≤ 12
x1 ≥ 0
x2 ≥ 0
¿Se puede deducir que no puede ser la solución óptima de ningún problema de programación lineal
definido en este recinto con cualquier vector de costes no nulo c 6= 0?. Deducir el caso general.
56 2.6. Ejercicios propuestos
9. Sea el problema
M in ct x
x ∈ A ⊂ IRn abierto
6 0 , B −1 b ≥ 0
B ⊂ A , |B| =
57
58 3.1. Sistema explı́cito
Esta base determina una partición de la matriz A = (B, N ). La clave de los cambios de base asociados
al algoritmo del sı́mplex es la transformación del sistema de ecuaciones Ax = b, en el sistema explı́cito
que resulta al despejar las componentes básicas xB en función de las componentes secundarias xN .
Para distinguir las componentes del vector xB ∈ IRm de las componentes del vector xN ∈ IRn−m se
introducen los conjuntos de subı́ndices:
I = {s ∈ {1, . . . , n} / as ∈ B} J = {j ∈ {1, . . . , n} / aj ∈ N }
BxB + N xN = b
xB + B −1 N xN = B −1 b
X
N xN = aj x j
j∈J
se introducen
yj ≡ B −1 aj ∀j ∈ J
y
x̄B ≡ B −1 b
Al despejar las componentes básicas en función del término independiente y las componentes secun-
darias, se define el sistema explı́cito —con notación vectorial— asociada a la base B:
X
xB = x̄B − yj xj
j∈J
que desglosando cada una de las m componentes, se definen las ecuaciones del sistema explı́cito:
P
xs = x̄s − j∈J ysj xj ∀s ∈ I (3.1)
aj = Byj ∀j ∈ J
por lo que el vector yj representa las coordenadas del vector aj respecto a la base B de IRm .
El sistema explı́cito permite obtener todas las soluciones del problema de programación lineal sin más
que asignar arbitrariamente los valores de las variables secundarias xN . Para que sean factibles hay que
asegurar que todas las componentes sean no negativas. Concretamente, si B −1 b ≥ 0, que es la hipótesis
de partida, se obtiene la solución básica factible asociada a la base B anulando todas las componentes
de la variable secundaria:
! !
x̄B B −1 b
x̄ = =
0 0
J. Yáñez; J. Tejada 59
Los cambios de base y, por tanto, de punto extremo del conjunto S, se conseguirán variando una de
las variables secundarias hasta anular una de las variables básicas. Con el fin de obtener el valor de la
función objetivo de las soluciones ası́ obtenidas, es preciso desarrollar las siguientes fórmulas:
z = ct x = ctB xB + ctN xN
Multiplicando la expresión vectorial del sistema explı́cito por la izquierda por cB queda
X
ctB xB = ctB x̄B − ctB yj xj
j∈J
Introduciendo
zj ≡ ctB yj ∀j ∈ J
z̄ ≡ ctB x̄B
que representa el valor de la función objetivo asociado a la solución básica, se obtiene la ecuación de coste
del sistema explı́cito:
P
z = z̄ − j∈J (zj − cj )xj (3.2)
Las fórmulas 3.1 y 3.2 permiten plantear el problema de programación lineal en forma explı́cita
dependiendo de las variables secundarias asociadas a una base
P
M in z̄ − (zj − cj )xj
Pj∈J
sujeto a x̄s − j∈J ysj xj ≥ 0 ∀s ∈ I
xj ≥ 0 ∀j ∈ J
que también se puede plantear como
P
M ax (zj − cj )xj
Pj∈J
sujeto a j∈J ysj xj ≤ x̄s ∀s ∈ I
xj ≥ 0 ∀j ∈ J
A continuación se detalla el sistema explı́cito en un problema de programación lineal definido a partir
del conjunto de soluciones factibles introducido en el ejemplo 2.1 del capı́tulo 2.
Ejemplo 3.1
Sea la base
2 0 1
B1 = (a1 , a2 , a3 ) = 0 −2 0
3 −2 0
su inversa es
0 −1/3 1/3
B1−1 = 0 −1/2 0
1 2/3 −2/3
0 −1/3 1/3 3 1
x̄B1 = 0 −1/2 0 −2 = 1 ≥ 0
1 2/3 −2/3 1 1
0 −1/3 1/3 3 1 0 −1/3 1/3 −1 0
y4 = 0 −1/2 0 0 = 0 y5 = 0 −1/2 0 −2 = 1
1 2/3 −2/3 3 1 1 2/3 −2/3 −2 −1
x1 = 1 −x4
x2 =1 −x5
x3 = 1 −x4 +x5
1
z̄ = ctB1 x̄B1 = 1 2 3 1 =6 z4 − c4 = ctB1 y4 − c4 = 0 z5 − c5 = ctB1 y5 − c5 = −6
1
z = 6 − (−6)x5
La solución básica factible se obtiene al anular las componentes secundarias x4 y x5 para obtener
z
z = z̄ − (zj − cj )xj
z̄
xj
Teorema 3.1 Una solución básica factible asociada a una base B que verifique
zj − c j ≤ 0 ∀j ∈ J
es óptima.
Demostración:
A partir de la ecuación 3.2 es evidente que cualquier valor xj > 0 para cualquier j ∈ J conseguirı́a
una función objetivo z mayor o igual que z̄ y, en consecuencia, el óptimo se alcanza anulando todas las
variables secundarias.
La figura 3.1 representa en el eje de abscisas una variable secundaria xj y en la ordenada el valor de
la función objetivo z = z̄ − (zj − cj )xj que se obtiene al asignar valores a la citada variable secundaria.
Al ser la pendiente de esta recta no negativa, no interesa asignar un valor positivo a xj .
Con el siguiente teorema se identifican condiciones suficientes para que el problema de programación
lineal tenga solución no acotada.
Teorema 3.2 Si existe una solución básica factible asociada a una base B verificando:
∃k ∈ J / zk − ck > 0 , yk ≤ 0
Demostración:
A partir de la ecuación 3.1, anulando todas las variables secundarias excepto la k-ésima, es decir,
xj = 0 ∀j ∈ J − {k}
se obtiene
62 3.2. Teoremas del sı́mplex
xs = x̄s − ysk xk ∀s ∈ I
ysk ≤ 0 ∀s ∈ I
y, por consiguiente,
xs ≥ x̄s ≥ 0 ∀s ∈ I ∀xk ≥ 0
Por tanto, cualquier asignación arbitraria a la variable secundaria xk de un valor no negativo propor-
ciona una solución factible:
xs = x̄s − ysk xk ≥ 0
∀s ∈ I
xj = 0 ∀j ∈ J − {k}
xk ≥ 0
Vectorialmente,
! !
x̄B −yk
x= + xk · ∀xk ≥ 0
0 ek
El valor de la función objetivo
z = z̄ − (zk − ck )xk
La figura 3.2 representa en el eje de abscisas la variable secundaria que no se anula xk y en la ordenada
los valores de las variables básicas en función de ella:
xs = x̄s − ysk xk ∀s ∈ I
Con trazo grueso se representa la función objetivo en función de la variable secundaria xk . Esta
relación es lineal y, además, decreciente al ser zk − ck > 0.
La solución básica asociada a B se obtiene anulando xk (el resto de variables secundarias son nulas).
Asignando a xk un valor estrictamente positivo x0k se obtiene una solución del sistema Ax = b intersecando
en el gráfico de la figura anterior la recta xk = x0k con todas estas rectas. Si los valores ası́ obtenidos son
todos mayores o iguales que 0, la solución es, además, factible.
Cada una de las rectas xs = x̄s − ysk xk para todo s ∈ I tiene la ordenada en el origen x̄s ≥ 0, y
al ser ysk ≤ 0, es no decreciente respecto de xk de forma que ∀xk ≥ 0 se obtienen soluciones factibles
y el recinto S no está acotado. Además, la recta asociada a la función objetivo z = z̄ − (zk − ck )xk es
decreciente y al aumentar el valor de xk se hace arbitrariamente pequeña. Se concluye ası́ que el problema
de programación lineal tiene solución no acotada.
Sea el problema de programación lineal del ejemplo 2.3 del capı́tulo 2. Al considerar la base
!
1 1
B = (a1 , a3 ) =
−2 1
J. Yáñez; J. Tejada 63
xs
xs = x̄s − ysk xk
x0k xk
El tercer y último teorema permite determinar una nueva solución básica factible —asociada a una
base B ′ — que proporciona un valor de la función objetivo menor o igual que el asociado a B. La diferencia
entre ambas bases es de un único vector que entra en sustitución de otro:
B ′ = B ∪ {ak } − {al }
Teorema 3.3 Dada una solución básica factible asociada a la base B verificando
∃k ∈ J / zk − ck > 0 , yk 6≤ 0
entonces existe una base B ′ cuya solución básica es factible y, además, alcanza un valor en la función
objetivo menor o igual que la solución básica factible asociada a la base B.
Demostración: Al ser zk − ck > 0, se puede obtener una función objetivo menor al aumentar xk en la
ecuación de coste del sistema explı́cito y anular el resto de componentes de la variable secundaria:
64 3.2. Teoremas del sı́mplex
xs
x̄l
z = z̄ − (zk − ck )xk
xl = x̄l − ylk xk
x̄l
x0k ylk xk
Además, cuanto mayor sea el valor de xk , mayor será el decrecimiento de la función objetivo. A
continuación se identificará el máximo valor que puede tomar xk .
De forma análoga a la demostración del teorema anterior, anulando todas las variables secundarias
excepto la k-ésima se obtiene:
xs = x̄s − ysk xk ∀s ∈ I
La figura 3.3 representa en el eje de abscisas la variable secundaria que no se anula xk y en la ordenada
los valores de las componentes básicas en función de ella. Las rectas asociadas al sistema explı́cito son
decrecientes si ysk > 0.
Con trazo grueso se representa la función objetivo en función de la variable secundaria xk ; esta recta
es decreciente al ser zk − ck > 0.
Al ser yk 6≤ 0 se concluye que al menos existe una componente ysk > 0 y, por tanto, existe alguna
recta decreciente en el gráfico de la figura 3.3 que cortará para algún valor de xk al eje de abscisas.
Para garantizar que la solución obtenida sea factible, hay que asegurar que xk no supere ninguno de
los puntos de corte anteriores. Tiene sentido, pues, determinar el mı́nimo de esos puntos de corte, que es
el cociente siguiente: ( )
x̄l x̄s
≡ M in / ysk > 0
ylk ysk
Al asignar a la variable xk el valor de este cociente
x̄l
x̄′k = ≥0
ylk
se obtiene el máximo valor de xk que identifica una nueva solución factible:
′ ′
x̄s = x̄s − ysk x̄k ≥ 0
∀s ∈ I
x̄′j = 0 ∀j ∈ J − {k}
′
x̄k
J. Yáñez; J. Tejada 65
Vectorialmente,
! !
′ x̄B −yk
x̄ = + x̄′k ·
0 ek
Hay que observar que en esta nueva solución, x̄′l = 0.
La nueva función objetivo es:
La desigualdad es estricta si x̄′k > 0 mientras que si x̄′k = 0, entonces x̄ = x̄′ , siendo ambas soluciones
básicas factibles idénticas aunque están asociadas a bases diferentes.
Al identificar las componentes del vector yk los coeficientes de la dependencia lineal de ak respecto
de la base B y ser ylk 6= 0, se puede definir la base
B ′ = B ∪ {ak } − {al }
que es la base asociada a la nueva solución x̄′ definida anteriormente; en efecto, al tomar la variable xk
que entra el valor
x̄l
x̄′k =
ylk
el sistema explı́cito garantiza que x̄′ es una solución del problema y el valor x′k = x̄′k asegura que es,
además, factible. Por otra parte, al anular las componentes secundarias de la nueva base B ′ , x′ es una
solución básica.
Para ilustrar este teorema, se considera en el problema del ejemplo 3.1 la siguiente base:
1 3 −1
B2 = (a3 , a4 , a5 ) = 0 0 −2
0 3 −2
su inversa es
1 1/2 −1
B2−1 = 0 −1/3 1/3
0 −1/2 0
y proporciona una solución básica factible, ya que
1 1/2 −1 3 1
x̄B2 = 0 −1/3 1/3 −2 = 1 ≥ 0
0 −1/2 0 1 1
Los conjuntos de ı́ndices son I = {3, 4, 5} y J = {1, 2}.
Los vectores y1 e y2 son
−1 1
y1 = 1 y2 = 0
0 1
66 3.3. Criterio de entrada del algoritmo del sı́mplex
Además,
z1 − c 1 = 0 z2 − c 2 = 6 > 0
Por lo que se puede cambiar de base al verificarse las condiciones del teorema 3.3:
y2 6≤ 0 z2 − c 2 > 0
x3 = 1 −x2 =0
x4 =1
x5 = 1 −x2 =0
que, junto con el valor de x2 = 1 identifica la solución básica factible
asociada a
B3 = (a2 , a4 , a5 , )
Esta solución básica factible tiene más de n − m = 2 ceros. Esta propiedad se justifica al no ser
único el mı́nimo de los cocientes que determina el vector que sale. Este tipo de soluciones se denominan
degeneradas y se analizan posteriormente.
(zk − ck )x̄′k
lo que implicarı́a determinar el valor de x̄′j para todos los j ∈ J con zj − cj > 0.
Sin embargo, considerando que los cálculos adicionales que supone la determinación de cada x̄′j como
el mı́nimo de los cocientes yx̄sjs , no garantizan que se llegue a la solución óptima con un número menor de
iteraciones, se adopta la siguiente regla como Criterio de Entrada:
En el caso en que este máximo sea múltiple, se elige cualquiera de los ı́ndices que alcancen dicho
máximo arbitrariamente.
El criterio de entrada no es crı́tico en el sentido de que si no se aplica, el algoritmo llega a la solución
óptima sin más que asegurar que sea positivo el zk − ck elegido.
J. Yáñez; J. Tejada 67
Si este mı́nimo es múltiple, eligiendo indistintamente cualquiera de los ı́ndices asociados, las variables
no elegidas con igual cociente se anularán en la nueva solución básica factible aún manteniéndose dentro
de la nueva base. La solución básica ası́ obtenida tiene más de n − m ceros; a este tipo de solución se la
denomina como solución degenerada.
En efecto, si el mı́nimo se alcanza en dos subı́ndices, l y l′ , la nueva solución obtenida al asignar en el
sistema explı́cito
siendo
x̄l x̄l′
x̄′k = =
ylk yl ′ k
Se anula no sólo xl sino también xl′ , ya que
Si se hubiera elegido como vector de entrada al′ en lugar de al , la nueva solución obtenida serı́a la
misma pero las bases asociadas serı́an distintas.
La existencia de una solución degenerada no modifica el criterio de salida. Concretamente, cualquier
as , con s ∈ I, que verifique x̄s = 0 e ysk > 0, es un candidato a salir de la base; independientemente del
pivote ysk elegido en estas condiciones, la nueva solución coincidirá con la inicial, aunque asociada a una
base diferente.
Una solución degenerada puede dejar de serlo en un cambio de base en el que entra ak con x̄′k > 0
si para una componente nula x̄s = 0 se verifica que ysk < 0; en efecto, el valor de la nueva componente
s-ésima serı́a:
x̄′s = 0 − ysk x̄′k > 0
El criterio de salida, a diferencia del criterio de entrada, sı́ es crı́tico; si no se aplica, la variable básica
que alcanza el mı́nimo de los cocientes —y que, por tanto, deberı́a salir— tomará en la nueva base un
valor negativo.
1.- Inicialización:
A = (B, N ) tal que B −1 b ≥ 0
I = {s ∈ {1, . . . , n} / as ∈ B} ; J = {j ∈ {1, . . . , n} / aj ∈ N }
2.- Proceso:
do
x̄B = B −1 b; z̄ = ctB x̄B
yj = B −1 aj , zj = ctB yj ∀j ∈ J
J + ≡ {j ∈ J / zj − cj > 0}
if (J + = ∅) then
SOLUCIÓN ÓPTIMA:
! !
∗ x̄∗B B −1 b
x̄ = =
x̄∗N 0
∗
z̄ = z̄
FIN
else ! ( J + 6= ∅)
if ( ∃k ∈ J + / yk ≤ 0) then
SOLUCIÓN NO ACOTADA
FIN
else ! (∀k ∈ J + yk 6≤ 0)
Criterio Entrada: Determinar k ∈ J tal que
zk − ck = máxj∈J + {zj − cj }
Criterio Salida:nDeterminar l ∈o I tal que
x̄l x̄s
ylk = M in ysk / ysk > 0
B = B ∪ {ak } − {al }
I = I ∪ {k} − {l}
J = J ∪ {l} − {k}
endif
endif
enddo
Observación 3.2 Si el problema de programación lineal se plantea como un problema de máximo, hay
dos opciones, que son excluyentes:
zk − ck = mı́n {zj − cj }
j∈J −
Observación 3.3 En el esquema del algoritmo del sı́mplex esbozado anteriormente, la búsqueda de un
ı́ndice k ∈ J + tal que yk ≤ 0 en el caso J + 6= ∅ implica la determinación de todos los yj ∀j ∈ J + .
Esta búsqueda puede resultar muy ineficiente para problemas de gran tamaño. Una alternativa válida
consiste en determinar primero
zk − ck = máx
+
{zj − cj }
j∈J
y se trata de relacionar los vectores yj′ , que determinan la dependencia de aj respecto de la base B ′ en
función de los vectores yj , asociados a la base B.
Particularizando la ecuación 3.1 para s = l:
X
xl = x̄l − ylj xj (3.4)
j∈J
o, en forma equivalente:
X
xl = x̄l − ylj xj − ylk xk (3.5)
j∈J−{k}
El elemento ylk > 0 que identifica al vector que entra en la base ak y al que sale al , se le denomina
pivote. Sobre este elemento gira el cambio de base en cada iteración del Algoritmo del sı́mplex.
Dividiendo la ecuación 3.5 por el pivote ylk y despejando la variable xk en función del resto, se obtiene
x̄l X ylj 1
xk = − xj − xl (3.6)
ylk j∈J−{k}
ylk ylk
ylj
si j ∈ J − {k}
ylk
′
ykj = (3.7)
1
si j=l
ylk
Para el resto de las filas de I ′ , es decir s ∈ I − {l}, sustituyendo el valor de xk de la ecuación 3.5 en
la ecuación 3.1:
ysk X ylj ysk
xs = x̄s − x̄l − (ysj − ysk )xj + xl s ∈ I − {l} (3.8)
ylk j∈J−{k}
ylk ylk
De la misma forma que se han obtenido expresiones para las y ′ , se obtienen las expresiones para los
nuevos valores de la solución básica factible asociada a B ′ :
x̄l
si s = k
y
′ lk
x̄s = (3.10)
x̄l
′
x̄s − y ysk si s ∈ I − {k}
lk
X
z ′ = z̄ ′ − (zj′ − c′j )xj
j∈J ′
x̄l X ylj 1
z = z̄ − (zk − ck ) − [(zj − cj ) − (zk − ck )]xj + (zk − ck )xl (3.12)
ylk j∈J−{k}
ylk ylk
X
z = z̄ ′ − (zj′ − cj )xj (3.13)
j∈J ′
se obtiene
x̄l
z̄ ′ = z̄ − (zk − ck )
ylk
(3.14)
ylj
zj′ − cj = (zj − cj ) − (zk − ck ) j ∈ J − {k} ∪ {l}
ylk
La inclusión del caso j = l se justifica al ser zl − cl = 0 y ser yll = 1.
J. Yáñez; J. Tejada 71
yj = B −1 aj ∀j ∈ J x̄B = B −1 b
as = Bes ∀s ∈ I aj = Byj ∀j ∈ J
siendo es ∈ IRm el vector con todas las componentes nulas excepto un 1 en la coordenada s-ésima.
Añadiendo a la tabla anterior una nueva fila que especifica los coeficientes de la función objetivo para
cada uno de los elementos de la base y una nueva fila que evalúa los zj − cj y z̄ se tiene
1. Todas las cantidades que interesan en el algoritmo del sı́mplex están dispuestas ordenadamente en
la tabla:
· · · zj − cj · · · z̄
.. ..
. yj . x̄B
3. El cambio de variable —lo más complejo del algoritmo— se facilita al observar que todo gira
alrededor del pivote ylk , que identifica el elemento que entra en la nueva base ak y el que sale al .
de un sistema de ecuaciones, serán válidas las operaciones que mantengan las mismas soluciones de
éste.
5. Para convertir en 1 el elemento ylk hay que dividir la fila l-ésima por ylk
6. Para convertir en 0 el resto de elementos ysk para todo s 6= l, hay que multiplicar la fila l-ésima por
′
−ysk para que al sumar esta fila a la fila s, el nuevo elemento ysk se anule.
7. Con la primera fila, que identifica los costes reducidos cambiados de signo, zj − cj , se opera del
mismo modo; es decir, hay que multiplicar la fila l-ésima por −(zk − ck ) para sumarla a la primera
fila anulando (zk′ − ck ).
8. Se ha conseguido ası́ una tabla del sı́mplex con un vector unitario en la posición k-ésima que
sustituye al que habı́a en la posición l-ésima.
Observación 3.4 Las operaciones matriciales descritas anteriormente son válidas en tanto en cuanto
mantienen el sistema de ecuaciones válido. Hay que observar, sin embargo, que hay que realizar las
operaciones según se han descrito para garantizar que los nuevos valores de la solución sean mayores o
iguales que 0.
Concretamente, si se multiplica la fila l-ésima por ysk y el resultado se resta a la fila s-ésima, se anula
′
el término ysk pero se obtiene un x̄′s ≤ 0. Esta observación es válida para la fila primera de los costes
reducidos.
Comparando estas transformaciones válidas en el sistema de ecuaciones asociado a la tabla del sı́mplex
se observa que coinciden con las fórmulas del cambio de base.
1 1 2 0
x̄B = 5/4 ≥ 0 y4 = 0 6≤ 0 y5 = −2 6≤ 0 y6 = 0 ≤ 0
1/4 1 3 −1
J. Yáñez; J. Tejada 73
6 5 −2 2 −1 1
x1 x2 x3 x4 x5 x6
0 0 0 2 −3 1 47/4
6 x1 1 0 0 1 2 0 1
5 x2 0 1 0 0 −2 0 5/4
−2 x3 0 0 1 1 3 −1 1/4
Se comprueba entonces que J + = {4, 6} y existe un k ∈ J + , concretamente k = 6, tal que y6 ≤ 0; por
lo que el problema en cuestión tiene SOLUCIÓN NO ACOTADA y termina el algoritmo del sı́mplex.
1 3 −3 −2
x̄B = 3 ≥ 0 y1 = −4 ≤
6 0 y2 = 5 ≤6 0 y3 = 7 ≤6 0
2 −3 4 5
1 2 −1 1 2 3
x1 x2 x3 x4 x5 x6
−15 17 28 0 0 0 13
1 x4 3 −3 −2 1 0 0 1
2 x5 −4 5 7 0 1 0 3
3 x6 −3 4 5 0 0 1 2
Se comprueba entonces que J + = {2, 3} tal que yj 6≤ 0 ∀j ∈ J + ; por lo que el problema en cuestión
admite un cambio de base que se determina a continuación:
74 3.6. Fórmulas del cambio de base
Criterio de entrada:
Entra a3 al ser z3 − c3 = M ax{zj − cj / j ∈ J + }
Criterio de salida:
Al ser
y43 −2
y3 = y53 = 7
y63 5
se evalúa el mı́nimo de los cocientes x̄s /ys3 con los ys3 > 0, por lo que se verifica
x̄l x̄5 x̄6 3 2 2
= min ; = min ; =
yl3 y53 y63 7 5 5
por lo que sale el vector a6 de la base y el elemento y63 = 5 es el pivote sobre el que gira el cambio de
base y la modificación de la tabla del sı́mplex, que para la nueva base B ′ = (a4 , a5 , a3 ) es la siguiente:
1 2 −1 1 2 3
x1 x2 x3 x4 x5 x6
9/5 −27/5 0 0 0 −28/5 9/5
1 x4 9/5 −7/5 0 1 0 2/5 9/5
2 x5 1/5 −3/5 0 0 1 −7/5 1/5
−1 x3 −3/5 4/5 1 0 0 1/5 2/5
Observación 3.5 Conviene observar que en esta tabla, z1 − c1 = 9/5 cuando en la tabla anterior era
menor o igual que 0. Este dato revela que los zj − cj pueden aumentar en cualquier iteración; el algoritmo
del sı́mplex sólo garantiza que z̄ no aumentará en un cambio de base.
Para esta tabla, J + = {1} y se verifica que y1 6≤ 0 por lo que entra en la nueva base el vector a1 .
En el criterio de salida se comprueba que el mı́nimo se alcanza en 2 cocientes, ya que
9/5 1/5
= =1
9/5 1/5
por lo que se puede elegir como vector de entrada cualquiera de los dos. A continuación se analizan las
tablas que resultan al elegir cada uno de los pivotes:
1 2 −1 1 2 3
x1 x2 x3 x4 x5 x6
0 −5 0 −1 0 −6 0
1 x1 1 −7/9 0 5/9 0 2/9 1
2 x5 0 −4/9 0 −1/9 1 −13/9 0
−1 x3 0 1/3 1 3/9 0 3/9 1
J. Yáñez; J. Tejada 75
Esta tabla es la óptima al verificar J + = ∅. La solución obtenida es degenerada por haber obtenido
un empate en el mı́nimo de los cocientes del criterio de salida. La solución óptima es
z̄ = 0
1 2 −1 1 2 3
x1 x2 x3 x4 x5 x6
0 0 0 0 −9 7 0
1 x4 0 4 0 1 −9 13 0
1 x1 1 −3 0 0 5 −7 1
−1 x3 0 −1 1 0 3 −4 1
1 2 −1 1 2 3
x1 x2 x3 x4 x5 x6
0 −28/13 0 −7/13 −54/13 0 0
3 x6 0 4/13 0 1/13 −9/13 1 0
1 x1 1 −11/13 0 7/13 2/13 0 1
−1 x3 0 3/13 1 4/13 3/13 0 1
La solución óptima es la misma que la obtenida anteriormente, pero con la base B IV = (a6 , a1 , a3 ):
z̄ = 0
Observación 3.6 En el ejemplo anterior se ha obtenido una solución básica óptima, que es única, pero
está asociada a tres bases distintas: B ′′ , B ′′′ y B IV .
La base B ′′′ ilustra la situación de una base asociada a una solución básica óptima que no verifica la
condición de optimalidad del teorema 3.1 del capı́tulo 3:
zj − cj ≤ 0 ∀j ∈ J
Lo que demuestra que dicha condición suficiente de optimalidad no es una condición necesaria.
76 3.7. Análisis geométrico de los teoremas del sı́mplex
Esta situación se puede presentar cuando la solución básica óptima es degenerada. Se denominará en-
tonces base óptima a cualquier base asociada a una solución básica óptima que cumpla la citada condición
de optimalidad. Se puede demostrar que toda solución básica óptima tiene asociada al menos una base
óptima.
para cualquier ı́ndice k ∈ J asociado a una variable secundaria, se introduce el vector γ k ∈ IRn definido
según:
−yjk
si j ∈ I
k
γj = 0 si j ∈ J − {k}
1 si j = k
Hay que observar que los vectores γ k tienen n componentes, formando las m correspondientes a la
base el vector yk cambiado de signo y siendo las n − m restantes todas nulas excepto un 1 en la posición
k-ésima:
− yk m
0
γk = ..
.
1 n−m
..
.
0
El análisis que sigue depende del signo de las m componentes del vector yk :
J. Yáñez; J. Tejada 77
xk ≥ 0
❘
✸
′
x̄ + xk′ γ k (yk′ ≤ 0)
xk ′ ≥ 0
❥
x̄
❄x̄ + xk γ k (yk 6≤ 0)
yk 6≤ 0
El segmento que parte de x̄ definido por:
x̄ + xk γ k / xk ∈ [0, x̄k ]
siendo ( )
x̄l x̄s
x̄k = ≡ mı́n / ysk > 0
ylk ysk
es una arista que une las soluciones básicas adyacentes x̄ y x̄′ , asociadas respectivamente a B y
B ∪ {ak } − {al }, y siendo
x̄′ ≡ x̄ + x̄k γ k
yk ≤ 0
En este caso no existe el lı́mite x̄k definido anteriormente y la semirrecta
x̄ + xk γ k / xk ≥ 0
tiene n − m − 1 componentes nulas y el vector γ k define una dirección extrema del conjunto S.
En efecto, el vector γ k es una dirección, ya que por la definición de yk = B −1 ak y al ser yk ≤ 0, se
verifica que γ k ≥ 0 y
Aγ k = B(−yk ) + ak = −ak + ak = 0
En conclusión, desde cualquier punto extremo de S ⊂ IRn salen n − m aristas que terminan en
otro punto extremo o, por el contrario, identifican una dirección extrema del conjunto S. La figura 3.4
representa esta situación con n − m = 2 y el espacio IRn proyectado en IR2 .
Para analizar si mejora la función objetivo al moverse por estas aristas incidentes en el punto extremo,
hay que considerar que, por definición de zk , se verifica:
ct γ j = −ctB yj + cj = −(zj − cj ) ∀j ∈ J
zj − cj ≤ 0 para todo j ∈ J
Moviéndose por cualquiera de las n−m aristas, empeora la función objetivo y, por tanto, la solución
básica actual es la óptima (teorema 3.1).
Determinar —si es posible— una base B que proporcione una solución básica factible iden-
tificando los conjuntos de ı́ndices I y J asociados a las componentes básicas y secundarias
respectivamente; ¿qué se puede concluir en caso contrario?
Desarrollar para B el sistema explı́cito determinando yj , zj − cj , x̄B y z̄.
Comprobar que con el vector yj , con j ∈ J, se genera el vector aj a partir de B.
Analizar si la solución básica factible es la óptima; en caso contrario, realizar los correspon-
dientes cambios de base hasta obtenerla o concluir que el problema tiene solución no acotada.
2. Para cada uno de los siguientes problemas de programación lineal y con la base B que se indica, se
pide:
2 −3 −1 A B 5
x1 x2 x3 x4 x5 x6
0 0 0 −9
−3 x2 0 1 0 2 −5 3 4
2 x1 1 0 0 −3 0 2 1
−1 x3 0 0 1 4 −1 −1 C
80 3.8. Ejercicios propuestos
Se pide:
Determinar los valores de A, B y C de forma que la tabla anterior identifique las siguientes
situaciones:
• Solución óptima.
• Solución no acotada.
Asignar los valores A = −20, B = 20 y C = 8 y llegar a la solución óptima.
Determinar, de forma independiente en cada uno de los casos, el rango de valores de los parámetros
α, β y γ que identifican en la tabla asociada a la base B = {a1 , a2 , a3 }:
a) Solución óptima.
b) Solución no acotada.
5. Resolver los problemas de programación de los ejercicios 1 y 2 por medio de la tabla del sı́mplex a
partir de la base B obtenida para cada uno de ellos.
a partir de la base B formada por las variables de holgura de las dos formas posibles (convirtiendo
el problema de máximo a uno de mı́nimo y modificando el criterio de entrada del algoritmo del
sı́mplex) y comparar los resultados obtenidos.
7. Dado el recinto definido en el problema 8 del capı́tulo 2, ¿Hay alguna solución básica degenerada?
Deducir las condiciones geométricas que deben verificarse para que un punto extremo sea una
solución degenerada.
Capı́tulo 4
El algoritmo del simplex parte de una solución básica factible asociada a una base B ⊂ A. Salvo
casos particulares, la determinación de esta base inicial no es una tarea trivial desde el punto de vista
computacional, ya que implicarı́a la inversión de ! matrices de dimensión m × m y el número de estas
n
inversiones puede alcanzar el valor lı́mite cuando el problema de programación lineal no admita
m
soluciones factibles.
El método de las dos fases y el de las penalizaciones son dos procedimientos eficientes para determinar
una solución básica factible inicial.
Ambos procedimientos detectan el caso de no existencia de solución factible sin necesidad de enumerar
todas las bases. Además, en el caso en que haya redundancia del sistema, es decir, cuando rg(A) < m,
identifican la fila redundante y la combinación lineal de filas asociada, permitiendo su eliminación y la
solución del problema.
M in x1 −3x2 −x3
x1 +4x2 +3x3 +xh1 = 12
x1 +2x2 −x3 +xh2 =4
xj ≥0 ∀j = 1, 2, 3
xhi ≥0 ∀i = 1, 2
81
82 4.1. Solución básica inicial. Variables artificiales
En este ejemplo se observa que, al elegir como base B = {ah1 , ah2 } = I, se verifica que B −1 = I y, por
consiguiente, las magnitudes relevantes se obtienen fácilmente
x̄B = b z̄ = 0 yj = aj ∀j ∈ I ∪ J zj − cj = −cj ∀j ∈ I ∪ J
1 −3 −1 0 0
x1 x2 x3 xh1 xh2
−1 3 1 0 0 0
0 xh1 1 4 3 1 0 12
0 xh2 1 2 −1 0 1 4
En general, sin embargo, la determinación de esta base inicial B no es una tarea trivial.
En lo que sigue, y para que la existencia de una submatriz identidad I ⊂ A proporcione una solución
básica factible inicial, se exigirá que el vector de términos independientes sea no negativo, es decir,
b≥0
Esta hipótesis no supone pérdida de generalidad ya que en caso contrario, si existiera un bi < 0 para
algún i ∈ {1, . . . , m}, se multiplicarı́a la restricción correspondiente por −1, invirtiendo el sentido de la
desigualdad si fuera una inecuación.
S = {x ∈ IRn / Ax = b ; x ≥ 0}
a
( ! )
x
Sa = ∈ IRn+m / Ax + Ixa = b x, xa ≥ 0
xa
donde
xa1
.
xa = .
. ≥0
xam
es el vector de variables artificiales de dimensión m.
Es fácil verificar que
x∈S ⇐⇒ (x, 0) ∈ S a
J. Yáñez; J. Tejada 83
En el caso en que haya alguna inecuación ≤ con el término independiente no negativo, no serı́a
necesario introducir una variable artificial para dicha inecuación, puesto que el vector unitario de la co-
rrespondiente variable de holgura podrı́a incluirse en la base inicial junto con las otras variables artificiales
del resto de restricciones. No obstante, y sin pérdida de generalidad, se considera que se parte del modelo
estándar de programación lineal y se añaden tantas variables artificiales como restricciones.
La base inicial formada por los vectores columna unitarios asociados a las variables artificiales
B = {aa1 , . . . , aam } = I
es la matriz identidad y proporciona como solución básica factible —para el problema ampliado— el
vector
(0, b) ∈ S a
El objetivo es intentar anular las variables artificiales para obtener una solución básica factible para
el problema original. Dos procedimientos generales son: el método de las dos fases y el método de las
penalizaciones.
1. Fase 1
Se introducen las variables artificiales según se ha detallado anteriormente y se fuerza su salida
mediante el algoritmo del simplex a partir de la base inicial formada por los vectores asociados a
las variables artificiales resolviendo el siguiente problema:
84 4.2. Método de las dos fases
M in 1t xa
P1 Ax +Ixa =b
x, xa ≥0
I ∗ = Io∗ ∪ Ia∗
donde
son los conjuntos de ı́ndices asociados a B ∗ entre las variables originales y las variables artificiales
respectivamente:
a) Ia∗ = ∅
Necesariamente, todas las variables artificiales se anulan, por lo que se eliminan de la tabla
del simplex óptima. La primera fase ha terminado. IR A LA FASE 2.
b) Ia∗ 6= ∅
Hay dos opciones:
∃i ∈ Ia∗ tal que x̄ai > 0
En este caso, no existe solución factible para el problema P . Ver proposición 4.1.
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
x̄ai = 0 ∀i ∈ Ia∗
En este caso, para cada fila i ∈ Ia∗ se distinguen dos casos:
• ∃j ∈ Jo∗ / yia j 6= 0
Sale de la base B ∗ el vector aai pivotando en el elemento yia j 6= 0 obteniendo la misma
solución con una base distinta que no la incluye.
Para pivotar, al ser solución degenerada, no es preciso que yia j > 0, pudiendo ser
negativo.
Se actualiza la base B ∗ = B ∗ ∪ {aj } − {aai }.
J. Yáñez; J. Tejada 85
• yia j = 0 ∀j ∈ Jo∗
En este caso, la fila ia -ésima puede ser suprimida al ser redundante. Ver proposición
4.2.
En ambos casos, después de pivotar o suprimir filas redundantes hasta eliminar todas las
variables artificiales en la base con valor 0, IR A LA FASE 2.
2. Fase 2
Se resuelve el problema P partiendo de la tabla del simplex óptima de la Fase 1 y con la base inicial
B ∗ . Al haber modificado los coeficientes de la función objetivo, hay que volver a calcular la fila de
los zj − cj y z̄.
Las dos posibles salidas para el problema P son ahora SOLUCIÓN NO ACOTADA y SOLUCIÓN
ÓPTIMA.
Aplicando el método de las dos fases al ejemplo 4.2, se obtiene la siguiente secuencia de tablas del
simplex:
Fase 1:
0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
2 0 6 3 1 1 0 0 0 8
1 xa1 1 0 1 1 −1 2 1 0 0 2
1 xa2 −1 1 2 0 1 −1 0 1 0 1
1 xa3 2 −1 3 2 1 0 0 0 1 5
0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
5 −3 0 3 −2 4 0 −3 0 5
1 xa1 3/2 −1/2 0 1 −3/2 5/2 1 −1/2 0 3/2
0 x3 −1/2 1/2 1 0 1/2 −1/2 0 1/2 0 1/2
1 xa3 7/2 −5/2 0 2 −1/2 3/2 0 −3/2 1 7/2
0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 −4/3 0 −1/3 3 −13/3 −10/3 −4/3 0 0
0 x1 1 −1/3 0 2/3 −1 5/3 2/3 −1/3 0 1
0 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
1 xa3 0 −4/3 0 −1/3 3 −13/3 −7/3 −1/3 1 0
0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 0 0 0 0 0 −1 −1 −1 0
0 x1 1 −7/9 0 5/9 0 2/9 −1/9 −4/9 1/3 1
0 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
0 x5 0 −4/9 0 −1/9 1 −13/9 −7/9 −1/9 1/3 0
Y se termina ası́ la fase 1, con
86 4.2. Método de las dos fases
B ∗ = {a1 , a3 , a5 }
Fase 2:
Después de eliminar las columnas asociadas a las variables artificiales, hay que volver a calcular la
primera fila siguiendo los siguientes pasos:
1. Sustituir los coeficientes de la función objetivo, que eran 0 en la Fase 1, por el vector c. En la
columna correspondiente, se especifica el vector cB .
1 2 −1 −2 2 3
x1 x2 x3 x4 x5 x6
0 −4 0 2 0 −6 0
1 x1 1 −7/9 0 5/9 0 2/9 1
−1 x3 0 1/3 1 1/3 0 1/3 1
2 x5 0 −4/9 0 −1/9 1 −13/9 0
Pivotando en y14 = 5/9 se obtiene la siguiente tabla:
1 2 −1 −2 2 3
x1 x2 x3 x4 x5 x6
−18/5 −6/5 0 0 0 −34/5 −18/5
−2 x4 9/5 −7/5 0 1 0 2/5 9/5
−1 x3 −3/5 4/5 1 0 0 1/5 2/5
2 x5 1/5 −3/5 0 0 1 −7/5 1/5
que proporciona la solución óptima:
Observación 4.1 Dada una base B que proporciona una solución básica factible, la tabla del simplex
se construye multiplicando el sistema Ax = b por su inversa B −1 y completando la primera fila de los
zj − cj y z̄.
Recı́procamente, dada una tabla del simplex, la base B se construye a partir de los vectores aj asociados
a los vectores unitarios es de la tabla en el orden canónico s = 1, 2, . . . , m.
Además, si la tabla inicial del simplex incorporaba una submatriz identidad bien porque I ⊂ A o bien
porque se hubieran añadido variables artificiales, se puede recuperar de forma instantánea la inversa de
la base B −1 sin más que reproducir los yj de la tabla asociados a los vectores unitarios de la submatriz
identidad que originó la base inicial.
J. Yáñez; J. Tejada 87
Para comprobar este resultado, y suponiendo que se han añadido las m variables artificiales, es su-
ficiente con observar que las últimas m columnas de la tabla del simplex son el producto del sistema de
ecuaciones ampliado por B −1 . Concretamente, la tabla del simplex con variables artificiales es
xt xat
zj − c j zia − cai z̄
B −1 A B −1 I x̄B
Con el fin de identificar en cada iteración del simplex la inversa de la base asociada, se pueden mantener
las columnas de las variables artificiales en la Fase 2. Estos vectores nunca entrarán en ninguna base en
la Fase 2.
El método de las dos fases no sólo proporciona una base inicial, sino que permite detectar la si-
tuación de no existencia de solución factible y la redundancia algebraica del sistema de ecuaciones que
definen el recinto de soluciones factibles. Ambas cuestiones se estudiarán en las secciones 4.2.1 y 4.2.2
respectivamente.
Integrando el método de las dos fases para determinar una solución básica inicial, se propone el
siguiente esquema del algoritmo del simplex:
88 4.2. Método de las dos fases
Io = ∅ , Ia = {1, . . . , m} ; I = Io ∪ Ia
Jo = {1, . . . , n} , Ja = ∅ ; J = Jo ∪ Ja
Pm Pm
zj − cj = i=1 aij ∀j ∈ Jo , zs − cs = 0 ∀s ∈ Ia , z̄ = i=1 bi
yj = aj ∀j ∈ Jo ys = es ∀s ∈ Ia x̄ = b
fase=1
do
J + ≡ {j ∈ J / zj − cj > 0}
if (J + = ∅) then
if (fase = 1) then
if (Ia = ∅) then
Eliminar Variables artificiales de la tabla
zj − cj = ctB yj − cj ∀j ∈ Jo zs − cs = 0 ∀s ∈ Io z̄ = ctB x̄
fase = 2
else
Ia+ ≡ {i ∈ Ia / x̄ai > 0}
if (Ia+ 6= ∅) then
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
else
do while (i ∈ Ia / x̄ai = 0)
Joi ≡ {j ∈ Jo / yia j 6= 0}
if (Joi = ∅) then
Eliminar la ecuación ia -ésima y la variable xai de la Tabla.
else
Sea j ∈ Joi .
Ia = Ia − {i} ; Ja = Ja ∪ {i} Jo = Jo − {j} ; Io = Io ∪ {j}
Pivotar la Tabla en yia j
endif
enddo
endif
endif
else ! Fase 2
SOLUCIÓN ÓPTIMA: x̄∗s = x̄s ∀s ∈ Io , x̄∗j = 0 ∀j ∈ Jo , z̄ ∗ = z̄. FIN.
endif
else ! ( J + 6= ∅)
if ( ∃k ∈ J + / yk ≤ 0) then
SOLUCIÓN NO ACOTADA. FIN.
else ! (∀k ∈ J + yk 6≤ 0)
Criterio Entrada: Determinar k ∈ J tal que zk − ck =n máxj∈J {zj −
+
o cj }
x̄l x̄s
Criterio Salida: Determinar l ∈ I tal que ylk = M in ysk / ysk > 0
I = I ∪ {k} − {l} J = J ∪ {l} − {k}. Actualizar Io , Ia , Jo , Ja .
Pivotar la Tabla en ylk
endif
endif
enddo
J. Yáñez; J. Tejada 89
Para ilustrar el caso i ∈ Ia∗ tal que existe un j ∈ Jo∗ verificando yia j 6= 0 se propone el siguiente
ejemplo.
0 0 1 1
x1 x2 xa1 xa2
3 2 0 0 3
1 xa1 1 1 1 0 1
1 xa2 2 1 0 1 2
0 0 1 1
x1 x2 xa1 xa2
0 −1 −3 0 0
0 x1 1 1 1 0 1
1 xa2 0 -1 −2 1 0
Esta tabla identifica las condiciones anteriores, es decir, aa2 ∈ B ∗ , x̄a2 = 0 y existe un elemento
y22a = −1 6= 0. Al elegir como pivote dicho elemento, se obtiene siguiente tabla, que también es óptima
para la Fase 1, pero con la ventaja de no tener variables artificiales en la base:
0 0 1 1
x1 x2 xa1 xa2
0 0 −1 −1 0
0 x1 1 0 −1 1 1
0 x2 0 1 2 −1 0
Al sustituir los coeficientes de la función objetivo de la Fase 1 por los originales, se obtiene, en este
ejemplo, la tabla óptima de la Fase 2:
3 2 − −
x1 x2 xa1 xa2
0 0 − − 3
3 x1 1 0 −1 1 1
2 x2 0 1 2 −1 0
Las columnas de las variables artificiales identifican la inversa de la base óptima, ver observación 4.1.
Demostración
Sea (x∗ , xa∗ ) la solución óptima de P 1 . Al verificar las hipótesis de la proposición, el valor de la
función objetivo de esta solución en el problema P 1 serı́a positivo.
Si existiera solución factible de P , sea por ejemplo x0 , la solución (x0 , 0) serı́a una solución del
problema P 1 , y serı́a mejor que (x∗ , xa∗ ) puesto que el valor de la función objetivo serı́a nulo. Por
consiguiente, no puede existir solución factible para P .
Con el siguiente ejemplo se ilustra la detección de no existencia de solución factible con el método de
las dos fases.
M in 2x1 +2x2 −x3 +3x4
x1 +2x2 −x3 +2x4 =3
P x1 −x2 +2x3 −3x4 =4
−x1 −5x2 +4x3 −7x4 =2
xj ≥ 0 ∀j = 1, 2, 3, 4
Fase 1:
M in xa1 +xa2 +xa3
x1 +2x2 −x3 +2x4 +xa1 =3
x1 −x2 +2x3 −3x4 +xa2 =4
P1
−x1 −5x2 +4x3 −7x4 +xa3 =2
xj ≥ 0 ∀j = 1, 2, 3, 4
xai ≥ 0 ∀i = 1, 2, 3
0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
1 −4 5 −8 0 0 0 9
1 xa1 1 2 −1 2 1 0 0 3
1 xa2 1 −1 2 −3 0 1 0 4
1 xa3 −1 −5 4 −7 0 0 1 2
0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
9/4 9/4 0 3/4 0 0 −5/4 13/2
1 xa1 3/4 3/4 0 1/4 1 0 1/4 7/2
1 xa2 3/2 3/2 0 1/2 0 1 −1/2 3
0 x3 −1/4 −5/4 1 −7/4 0 0 1/4 1/2
0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
0 0 0 0 0 −3/2 −1/2 2
1 xa1 0 0 0 0 1 −1/2 1/2 2
0 x1 1 1 0 1/3 0 2/3 −1/3 2
0 x3 0 −1 1 −5/3 0 1/6 1/6 1
En esta tabla óptima, se observa que B ∗ = {aa1 , a1 , a3 }, de forma que
En este ejemplo, 1 ∈ Ia∗ 6= ∅ y se verifica que x̄a1 = 2 > 0, por lo que no existe solución factible para
el problema planteado.
Proposición 4.2 Si en la solución óptima de P 1 existe una variable artificial en la base x̄ak = 0 para
algún k ∈ Ia∗ verificando, además, que ykj = 0 ∀j ∈ Jo∗ , entonces el sistema de ecuaciones Ax = b es
redundante y la ecuación correspondiente a esta variable se puede suprimir.
Demostración
Sea ai , con i ∈ {1, . . . , m}, el vector cuyos elementos son los de la fila i-ésima de la matriz A de
restricciones del problema P , es decir,
(a1 )t ai1
.. .
A=
.
ai = .
. ∀i ∈ {1, . . . , m}
m t
(a ) ain
El sistema de ecuaciones Ax = b es redundante si, y sólo si, existe una combinación lineal no trivial
entre las filas de la matriz A:
m
X
λi ai = 0 ∈ IRn
i=1
siendo
λ 6= 0, λ ∈ IRm
m
X
λ i bi = 0
i=1
El vector λ que identifica la combinación lineal de las ecuaciones se determina a partir del ı́ndice
k ∈ Ia∗ y de la inversa de la base óptima B ∗ del problema P 1 de la fase 1:
λt = etk (B ∗ )−1
1. λ 6= 0
Ya que el vector λ coincide con la fila de una matriz que se puede invertir.
Pm
2. i=1 λi ai = 0 ∈ IRn
En efecto,
m
X
λi ai = λt A = etk (B ∗ )−1 A = etk (. . . , ei , . . . , yj , . . .)
i=1
donde ei son vectores unitarios para todo i ∈ Io∗ , y los vectores yj = (B ∗ )−1 aj para j ∈ Jo∗ .
Al ser i 6= k para cualquier i ∈ Io∗ , se verifica que
etk ei = 0 ∀i ∈ Io∗
Por la hipótesis de la proposición, para el ı́ndice k ∈ Ia∗ verificando ykj = 0 ∀j ∈ Jo∗ , se tiene que
etk yj = 0 ∀j ∈ Jo∗
Pm
3. i=1 λ i bi = 0
Por definición del vector λ, se verifica
m
X
λi bi = λt b = etk (B ∗ )−1 b = etk x̄B ∗ = x̄ak = 0
i=1
En la demostración de esta proposición se identifica la combinación lineal de las ecuaciones del sistema
Ax = b a partir de la fila k-ésima de la inversa de la base óptima para la Fase 1, siendo xak la variable
artificial que pertenece a dicha base con valor 0.
Una demostración alternativa se basa en considerar los vectores yj∗ como los coeficientes de la depen-
dencia lineal del vector aj respecto de la base B ∗ . Entonces, bajo las condiciones de la proposición 4.2, se
∗
tiene que si ykj = 0 para todo j ∈ Jo∗ , ninguno de los vectores aj depende linealmente del vector asociado
a xak y, por consiguiente, el rango de la matriz A no serı́a m, sino m − 1.
Fase 1:
M in xa1 +xa2 +xa3
x1 +2x2 −x3 +2x4 +xa1 =1
x1 −x2 +2x3 −3x4 +xa2 =4
P1
−x1 −5x2 +4x3 −7x4 +xa3 =2
xj ≥ 0 ∀j = 1, 2, 3, 4
xai ≥ 0 ∀i = 1, 2, 3
Pivotando, según el algoritmo del simplex, sucesivamente en y1a 1 , y2a 3 e y3a 1a , se obtiene la tabla
óptima
0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
0 0 0 0 0 −1/2 −1/2 0
0 x1 1 1 0 1/3 0 2/3 1/3 2
0 x3 0 −1 1 −5/3 0 1/6 1/6 1
1 xa1 0 0 0 0 1 −1/2 1/2 0
B ∗ = {a1 , a3 , aa1 }
que, como se puede comprobar, define la combinación lineal del sistema de ecuaciones.
Observación 4.2 Observando la tabla del simplex anterior se puede aportar una demostración más
intuitiva de la redundancia del sistema de ecuaciones sin más que observar que son nulos todos los
coeficientes de las variables normales, las originales más las de holgura, y que, por tanto, la ecuación
lineal asociada a la tercera fila identifica una combinación de variables artificiales que es igual a cero
(1xa1 − 1/2xa2 + 1/2xa3 = 0).
Si se sustituyen en esta ecuación los valores de las variables artificiales por el resto de las ecuaciones
donde se introdujeron, se obtiene de forma natural una combinación lineal no trivial de las ecuaciones
que se anula.
94 4.3. Método de las penalizaciones
Una vez tachadas la tercera fila de la tabla, la asociada a xa1 , y las columnas asociadas a las variables
artificiales, se pasa a la siguiente fase.
Fase 2:
Volviendo a calcular la primera fila a partir de los coeficientes de la función objetivo del problema
original, se obtiene la tabla del simplex:
2 1 −1 3
x1 x2 x3 x4
0 2 0 −2/3 3
2 x1 1 1 0 1/3 2
−1 x3 0 −1 1 −5/3 1
Pivotando en el elemento y12 = 1 se obtiene la tabla óptima del simplex
2 1 −1 3
x1 x2 x3 x4
−2 0 0 −4/3 −1
1 x2 1 1 0 1/3 2
−1 x3 1 0 1 −4/3 3
que corresponde a la solución óptima
t
M in c x + Mt x a
PM Ax + Ixa = b
x, xa ≥ 0
Al igual que con el método de las dos fases, la base inicial B está formada por los vectores unitarios
asociados a las variables artificiales, por lo que la tabla del simplex inicial se obtiene fácilmente.
Es fácil demostrar que si (x∗ , xa∗ ) es la solución óptima de P M , x∗ será la solución óptima de P si,
y sólo si, xa∗ = 0. Esta situación se ilustra con el siguiente ejemplo.
M in x1 +2x2 −x3 −2x4 +2x5 +3x6 +M xa1 +M xa2 +M xa3
x1 +x3 +x4 −x5 +2x6 +xa1 =2
−x1 +x2 +2x3 +x5 −x6 +xa2 =1
PM
2x1 −x2 +3x3 +2x4 +x5 +xa3 =5
xj ≥ 0 ∀j = 1, . . . , 6
xai ≥ 0 ∀i = 1, . . . , 3
La tabla del simplex inicial asociada a la base B = {aa1 , aa2 , aa3 } es la siguiente
1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
2M − 1 −2 6M + 1 3M + 2 M −2 M −3 0 0 0 8M
M xa1 1 0 1 1 −1 2 1 0 0 2
M xa2 −1 1 2 0 1 −1 0 1 0 1
M xa3 2 −1 3 2 1 0 0 0 1 5
Para aplicar el criterio de entrada, todos los zj − cj con coeficiente mayor que 0 multiplicando a la
constante M son positivos, el mayor será el de mayor coeficiente y, en caso de empate, se compara el
término constante. En este caso,
x̄l 2 1 5 1
= M in{ ; ; }=
yl3 1 2 3 2
sale de la base aa2 .
La nueva tabla al pivotar en y32a = 2 es
1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
5M... −3M... 0 3M... −2M... 4M... 0 −3M... 0 5M − 1/2
M xa1 3/2 −1/2 0 1 −3/2 5/2 1 −1/2 0 3/2
−1 x3 −1/2 1/2 1 0 1/2 −1/2 0 1/2 0 1/2
M xa3 7/2 −5/2 0 2 −1/2 3/2 0 −3/2 1 7/2
96 4.3. Método de las penalizaciones
1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 −4/3M... 0 −1/3M... 3M... −12/3M... −10/3M... −4/3M... 0 0
1 x1 1 −1/3 0 2/3 −1 5/3 2/3 −1/3 0 1
−1 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
M xa3 0 −4/3 0 −1/3 3 −13/3 −7/3 −1/3 1 0
1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 −4 0 +2 0 −6 −M... −M... −M... 0
1 x1 1 −7/9 0 5/9 0 2/9 −1/9 −4/9 1/3 1
−1 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
2 x5 0 −4/9 0 −1/9 1 −13/9 −7/9 −1/9 1/3 0
1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
−18/5 −6/5 0 0 0 −34/5 −M... −M... −M... −18/5
−2 x4 9/5 −7/5 0 1 0 2/5 −1/5 −4/5 3/5 9/5
−1 x3 −3/5 4/5 1 0 0 1/5 2/5 3/5 −1/5 2/5
2 x5 1/5 −3/5 0 0 1 −7/5 −4/5 −1/5 2/5 1/5
La solución óptima es
De forma análoga al método de las dos fases, el método de las penalizaciones identifica la no existencia
de soluciones factibles cuando a la base óptima del problema P M pertenezca un vector columna asociado
a una variable artificial y ésta tome un valor positivo.
El caso de redundancia en el sistema de ecuaciones Ax = b también se puede detectar. Aplicando el
método de las penalizaciones al ejemplo 4.5 se obtiene la siguiente secuencia de tablas del simplex:
2 1 −1 3 M M M
x1 x2 x3 x4 xa1 xa2 xa3
M − 2 −4M − 2 5M + 1 −8M − 3 0 0 0 7M
M xa1 1 2 −1 2 1 0 0 1
M xa2 1 −1 2 −3 0 1 0 4
M xa3 −1 −5 4 −7 0 0 1 2
J. Yáñez; J. Tejada 97
2 1 −1 3 M M M
x1 x2 x3 x4 xa1 xa2 xa3
9M/4.. 9M/4.. 0 3M/4.. 0 0 −5M/4.. 9M/2..
M xa1 3/4 3/4 0 1/4 1 0 1/4 3/2
M xa2 3/2 3/2 0 1/2 0 1 −1/2 3
−1 x3 −1/4 −5/4 1 −7/4 0 0 1/4 1/2
2 1 −1 3 M M M
x1 x2 x3 x4 xa1 xa2 xa3
−1 0 0 −19/12 −3M.. 0 −2M.. −1
1 x2 1 1 0 1/3 4/3 0 1/3 2
M xa2 0 0 0 0 −2 1 −1 0
−1 x3 1 0 1 −3/4 5/3 0 2/3 3
En esta tabla, que es la óptima, se elimina la segunda fila por ser redundante y se obtiene directamente
la solución óptima
El caso en el que se detecte no acotación en P M requiere de un análisis más detallado; más concreta-
mente, supongamos que tenemos una solución básica factible x̄∗ de P M para la que se verifica:
zk − ck = máx{zj − cj } > 0 , yk ≤ 0
j
x̄a∗ = 0.
En este caso, P es no acotado. En efecto, si P M es no acotado es que existe una dirección de S a
dt = (do t , da t ) ≥ (0t , 0t )
verificando
Ado + Ida = 0
ct d o + Mt d a < 0
da = 0 , ct do < 0
6 5 −2 2 −1 1 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
−3 0 1 0 −6 0 −M.. −M.. −M..
5 x2 0 1 0 0 −2 0 5/4 −1/2 −3/4 5/4
2 x4 1 0 0 1 2 0 −1 1 1 1
1 x6 1 0 −1 0 −1 1 3/4 −1/2 −1/4 3/4
que identifica un problema con solución no acotada al existir un k = 3 ∈ J tal que z3 − c3 = 1 > 0
y verificar que y3 ≤ 0.
La dirección asociada en el recinto S a ⊂ IR9 es
dt = (0, 0, 1, 0, 0, 1, 0, 0, 0)
X
ysj ≤ 0 , ∀j ∈ J ∗
s∈Ia∗
En efecto, ∀j ∈ J ∗ se verifica
X X
zj − c j = cs ysj + M ysj − cj
s∈Io∗ s∈Ia∗
zk − ck = máx∗ {zj − cj } yk ≤ 0
j∈J
se deduce que
X
ysk = 0
s∈Ia∗
En caso contrario, si existiera un ysk < 0 para algún s ∈ Ia∗ , no podrı́a ser zk − ck > 0, al ser M > 0
arbitrariamente grande.
P
Tampoco puede existir ningún j ∈ J ∗ tal que s∈Ia∗ ysj > 0; en caso contrario, al multiplicar por
la constante M se obtendrı́a un zj − cj superior a zk − ck , que ha sido elegido por ser el máximo.
En segundo lugar, a partir de las ecuaciones del sistema explı́cito asociadas a las variables artificiales
J. Yáñez; J. Tejada 99
X
xs = x̄∗s − ysj xj , s ∈ Ia∗
j∈J ∗
se obtiene al sumarlas:
X X X X
xs = x̄∗s − xj ( ysj )
s∈Ia∗ s∈Ia∗ j∈J ∗ s∈Ia∗
Si P tuviera solución factible, deberı́an existir unos valores para los parámetros xj , con j ∈ J ∗ , que
anulasen todas las componentes de la variable artificial y, en consecuencia, la suma anterior, o lo
que es lo mismo,
X X X
x̄∗s = xj ( ysj )
s∈Ia∗ j∈J ∗ s∈Ia∗
Pero el lado izquierdo es positivo, ya que tenemos una variable artificial en la base que es distinta
de cero, mientras que el lado derecho serı́a menor o igual que cero, según acabamos de ver. Esta
contradicción prueba que P es no factible.
El método de las penalizaciones, al igual que el método de las dos fases, no sólo proporciona una
base inicial, sino que permite detectar la situación de no existencia de solución factible y la redundancia
algebraica del sistema de ecuaciones que definen el recinto de soluciones factibles.
Integrando el método de las penalizaciones para determinar una solución básica inicial, se propone el
siguiente esquema del algoritmo del simplex:
100 4.3. Método de las penalizaciones
Io = ∅ , Ia = {1, . . . , m} ; I = Io ∪ Ia
Jo = {1, . . . , n} , Ja = ∅ ; J = Jo ∪ Ja
Pm Pm
zj − cj = M · i=1 aij − cj ∀j ∈ Jo , zs − cs = 0 ∀s ∈ Ia , z̄ = M · i=1 bi
yj = aj ∀j ∈ Jo ys = es ∀s ∈ Ia x̄ = b
do
zk − ck = máxj∈J {zj − cj }
if (zk − ck ≤ 0) then
if (Ia 6= ∅) then
Ia+ ≡ {i ∈ Ia / x̄ai > 0}
if (Ia+ 6= ∅) then
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
else
do while (i ∈ Ia / x̄ai = 0)
Joi ≡ {j ∈ Jo / yia j 6= 0}
if (Joi = ∅) then
Eliminar la ecuación ia -ésima y la variable xai de la Tabla.
else
Sea j ∈ Joi .
Ia = Ia − {i} ; Ja = Ja ∪ {i} Jo = Jo − {j} ; Io = Io ∪ {j}
Pivotar la Tabla en yia j
endif
enddo
endif
endif
SOLUCIÓN ÓPTIMA: x̄∗s = x̄s ∀s ∈ Io , x̄∗j = 0 ∀j ∈ Jo , z̄ ∗ = z̄. FIN.
else
if ( yk ≤ 0) then
if (∃i ∈ Ia tal que x̄ai > 0) then
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
else
SOLUCIÓN NO ACOTADA. FIN.
endif
else
Criterio Entrada: Entra ak n o
x̄l x̄s
Criterio Salida: Determinar l ∈ I tal que ylk = M in ysk / ysk > 0
I = I ∪ {k} − {l} J = J ∪ {l} − {k}. Actualizar Io , Ia , Jo , Ja .
Pivotar la Tabla en ylk
endif
endif
enddo
M ax{ct x − Mt xa }
o su equivalente
M in{−ct x + Mt xa }
102 4.4. Ejercicios propuestos
a)
M in x1 −2x2 +2x3 +3x4 +x5
sujeto a 2x1 +x3 −3x4 −x5 = 10
−x1 +2x2 −2x3 +x4 +3x5 = 15
+x2 +x3 −2x5 =5
xj ≥ 0 ∀j = 1, .., 5
b)
M in x1 +x2 +x3 −3x4 −2x5
sujeto a +x2 −2x3 +x4 =3
2x1 −x2 +x4 −3x5 =3
xj ≥ 0 ∀j = 1, .., 5
c)
M in 15x1 −20x2 +10x3 +30x4 +25x5
sujeto a x1 −2x2 +3x4 +x5 = 100
x2 +2x3 −x4 +2x5 = 150
−x1 +x3 +x4 −2x5 = 200
xj ≥ 0 ∀j = 1, .., 5
d)
M in 2x1 +x2 +3x4 −2x5 −x6
sujeto a x1 −2x3 +2x4 +x5 −x6 = 10
−2x1 +2x2 +x3 −x4 +3x5 −2x6 = 15
x2 −x3 +2x4 −3x5 +x6 = 20
xj ≥ 0 ∀j = 1, .., 6
e)
M in x1 +x2 +x3 +x4 +x5 +x6
sujeto a x1 +x2 +x3 −2x4 +x5 −x6 =5
−2x1 +x3 −x4 −x5 −2x6 =6
x1 +x2 +x3 +2x4 −3x5 +x6 =7
xj ≥ 0 ∀j = 1, .., 6
f)
M in 3x1 +2x2 +x3 +x5 −2x6
sujeto a x1 −2x3 +x4 −x5 +3x6 = 10
−x1 +2x2 +x3 +x4 +2x5 −x6 = 15
−2x1 −2x2 +3x3 +3x5 −4x6 =5
xj ≥ 0 ∀j = 1, .., 6
J. Yáñez; J. Tejada 103
2. ¿Se puede utilizar el algoritmo del simplex para resolver un sistema de inecuaciones lineales? En
caso afirmativo, dar una solución del siguiente sistema:
2x1 +x2 ≥4
x2 ≤0
x1 −x2 ≤1
S = {x ∈ IR2 / x1 + x2 = 5; −2x1 + x2 = 6; x1 , x2 ≥ 0}
5. Utilizando el método de las penalizaciones para encontrar una solución básica factible inicial, ¿es
posible que P M tenga solución no acotada mientras que el problema original sea acotado?
104 4.4. Ejercicios propuestos
Capı́tulo 5
Una vez determinada la solución óptima con el algoritmo del simplex, hay que analizar la multiplicidad
de soluciones óptimas; se indica un procedimiento que permite determinar el conjunto de soluciones
óptimas S ∗ a partir de la tabla óptima del simplex.
En el capı́tulo 3 se introdujo el concepto de solución degenerada para aquellas soluciones básicas
factibles con alguna componente básica nula. La existencia de varias soluciones degeneradas adyacentes
puede provocar un ciclo en el algoritmo del simplex y que éste, en consecuencia, no converja. Se introducen
dos procedimientos que garantizan la convergencia del simplex: la variante lexicográfica, que modifica el
criterio de salida del algoritmo del simplex, y el método de Bland.
Por otra parte, el análisis de la redundancia algebraica a partir de las variables artificiales no cubre
el caso de redundancia geométrica, que se presenta cuando el semiespacio definido por una inecuación
está incluido en la intersección de uno o más semiespacios definidos por otras inecuaciones.
Después de resolver un problema de programación lineal se pueden plantear algunas cuestiones intere-
santes, por ejemplo, ¿para qué valores del vector c se mantiene la base óptima?. Ésta y otras cuestiones
se analizan en el apartado de post-optimización. Por otra parte, ante la incertidumbre de la información,
se puede plantear un problema de programación lineal donde el vector c depende de un parámetro; serı́a
un problema de parametrización.
zj − cj ≤ 0 ∀j ∈ J
J 0 ≡ {j ∈ J / zj − cj = 0}
105
106 5.1. Unicidad de la solución óptima
En caso contrario, cuando J 0 6= ∅, para cada k ∈ J 0 , hay dos posibilidades exhaustivas y excluyentes:
yk ≤ 0
En este caso, ver sección 3.7, el vector yk determina una dirección extrema
!
k −yk
γ =
ek
verificando, al ser k ∈ J 0 ,
ct γ k = −ctB yk + ck = −(zk − ck ) = 0
x = x̄ + xk γ k ∀xk ≥ 0
yk 6≤ 0
En este caso, por el teorema 3.3, existe otra solución básica adyacente asociada al asignar a la
variable xk el valor
( )
x̄s
x̄′k = M in / ysk > 0 >0
ysk
x̄k = x̄ + x̄′k γ k
Observación 5.1 Para que haya multiplicidad de soluciones óptimas asociadas a un k ∈ J 0 veri-
ficando yk 6≤ 0 hay que exigir que x̄′k > 0; en caso contrario, si x̄′k = 0, el pivote ylk cambiarı́a la
base pero no la solución al ser ésta degenerada.
Dada una tabla óptima del simplex, y con el fin de identificar las direcciones extremas que parten de
la solución básica y las soluciones básicas adyacentes, se introducen los conjuntos
J10 ≡ k ∈ J 0 / yk 6≤ 0, x̄′k > 0
J20 ≡ k ∈ J 0 / yk ≤ 0
X X X
x = λ0 x̄ + λj x̄j + µj γ j / λj ≥ 0 ∀j ∈ J10 ∪ {0} ; λ0 + λj = 1 ; µj ≥ 0 ∀j ∈ J20
j∈J10 j∈J20 j∈J10
J. Yáñez; J. Tejada 107
1 2 3 5 −5 3 −8 1
x1 x2 x3 x4 x5 x6 x7 x8
0 0 0 −1 0 0 0 0 9
1 x1 1 0 0 2 1 −2 0 −1 0
2 x2 0 1 0 1 0 1 −1 1 3
3 x3 0 0 1 0 −2 1 −2 0 1
Para analizar la multiplicidad de soluciones óptimas, se observa que
J 0 = {5, 6, 7, 8} =
6 ∅
y5 6≤ 0 y6 6≤ 0 y7 ≤ 0 y8 6≤ 0
Al determinar el pivote asociado a a5 se observa que es y15 = 1, pero x̄′5 = 0, por lo que no hay que
incluir el ı́ndice 5 en el conjunto J10 . Se puede comprobar que x̄′6 = 1 y x̄′8 = 3, por lo que se tienen
determinados los subconjuntos de J 0 :
A partir de la solución básica x̄ se obtienen las soluciones básicas óptimas x̄6 y x̄8 , pivotando respec-
tivamente en y36 e y28 . Los puntos extremos óptimos obtenidos son:
0 2 3
3 2 0
1 0 1
0 0 0
x̄ =
0 x̄ =
6
0 x̄ =
8
0
0 1 0
0 0 0
0 0 3
que junto con la dirección extrema
0
1
2
0
γ =
7
0
0
1
0
108 5.1. Unicidad de la solución óptima
λ0 x̄ + λ6 x̄6 + λ8 x̄8 + µ7 γ 7 / λj , µj ≥ 0 ; λ0 + λ6 + λ8 = 1
Sin embargo, a partir de la tabla óptima obtenida al pivotar en el elemento y36 , se obtiene la tabla:
1 2 3 5 −5 3 −8 1
x1 x2 x3 x4 x5 x6 x7 x8
0 0 0 −1 0 0 0 0 9
1 x1 1 0 2 2 −3 0 −4 −1 2
2 x2 0 1 −1 1 2 0 1 1 2
3 x6 0 0 1 0 −2 1 −2 0 1
y pivotando de nuevo en el elemento y25 = 2, se obtiene otra solución básica óptima
5
0
0
0
x̄65 =
1
3
0
0
que no está incluida en el conjunto anterior, puesto que la coordenada 5 es positiva.
Se observa con este ejemplo que la determinación del conjunto de soluciones óptimas puede ser com-
plicada desde el punto de vista computacional, ya que hay que determinar todas las tablas óptimas para
identificar todos los puntos extremos y las direcciones extremas del conjunto S de soluciones factibles del
problema de programación lineal.
xs = x̄s ∀s ∈ I − {r}
x+
j = x̄r + x−
j
xj = 0 ∀j ∈ J − {j − }
x−
j ≥0
z = z̄ − 0x−
j = z̄
La conclusión es que para cualquier valor de x−
j ≥ 0, la función objetivo es la misma, ya que la única
−
variable que depende de xj es:
x+ −
j = x̄r + xj
por lo que se concluye que la variable no restringida en signo xj toma siempre el mismo valor, ya que
xj = x+ −
j − xj = x̄r ∀x−
j ≥0
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 0 0 3/4 −20 1/2 −6 0
0 x1 1 0 0 1/4 −8 −1 9 0
0 x2 0 1 0 1/2 −12 −1/2 3 0
0 x3 0 0 1 0 0 1 0 1
La secuencia de tablas del simplex pivotando en los elementos marcados es la siguiente:
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
−3 0 0 0 4 7/2 −33 0
−3/4 x4 4 0 0 1 −32 −4 36 0
0 x2 −2 1 0 0 4 3/2 −15 0
0 x3 0 0 1 0 0 1 0 1
110 5.2. Convergencia del algoritmo del simplex
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
−1 −1 0 0 0 2 −18 0
−3/4 x4 −12 8 0 1 0 8 −84 0
20 x5 −1/2 1/4 0 0 1 3/8 −15/4 0
0 x3 0 0 1 0 0 1 0 1
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
2 −3 0 −1/4 0 0 3 0
−1/2 x6 −3/2 1 0 1/8 0 1 −21/2 0
20 x5 1/16 −1/8 0 −3/64 1 0 3/16 0
0 x3 3/2 −1 1 −1/8 0 0 21/2 1
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
1 −1 0 1/2 −16 0 0 0
−1/2 x6 2 −6 0 −5/2 56 1 0 0
6 x7 1/3 −2/3 0 −1/4 16/3 0 1 0
0 x3 −2 6 1 5/2 −56 0 0 1
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 2 0 7/4 −44 −1/2 0 0
0 x1 1 −3 0 −5/4 28 1/2 0 0
6 x7 0 1/3 0 1/6 −4 −1/6 1 0
0 x3 0 0 1 0 0 1 0 1
Y al pivotar en el elemento y72 = 1/3 se obtiene la tabla inicial, por lo que se ha formado un ciclo y
el algoritmo no convergerı́a nunca.
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 0 0 3/4 −20 1/2 −6 0
0 x1 1 0 0 1/4 −8 −1 9 0
0 x2 0 1 0 1/2 −12 −1/2 3 0
0 x3 0 0 1 0 0 1 0 1
Para evitar estas situaciones —aunque sólo se han encontrado en casos forzados teóricamente— se ha
diseñado la variante lexicográfica del algoritmo del simplex, que precisa el criterio de salida cuando hay
un empate evitando ciclos como el descrito anteriormente.
Sea ( ( ))
x̄r x̄s
I0 = r∈I / = mı́n / ysk > 0
yrk s∈I ysk
hay dos opciones:
este proceso se itera hasta que algún Ij contenga un único ı́ndice, que identifica el vector que sale de la
base:
( ( ))
yrj yij
Ij = r ∈ Ij−1 / = mı́n
yrk i∈Ij−1 yik
Este proceso termina necesariamente, puesto que en caso contrario habrı́a tantas filas proporcionales
como elementos alcanzasen el último mı́nimo y habrı́a redundancia de dichas ecuaciones.
I0 = {1, 2}
I1 = {2}
por lo que el pivote de la primera tabla serı́a y24 = 1/2 y se obtendrı́a la tabla:
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 −3/2 0 0 −2 5/4 −21/2 0
0 x1 1 −1/2 0 0 −2 −3/4 15/2 0
−3/4 x4 0 2 0 1 −24 −1 6 0
0 x3 0 0 1 0 0 1 0 1
Y se obtiene la tabla óptima:
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 −3/2 −5/4 0 −2 0 −21/2 −5/4
0 x1 1 −1/2 3/4 0 −2 0 15/2 3/4
−3/4 x4 0 2 1 1 −24 0 6 1
−1/2 x6 0 0 1 0 0 1 0 1
Para demostrar que la variante lexicográfica evita los ciclos de bases en los sucesivos cambios del
algoritmo del simplex, hay que introducir la ordenación lexicográfica de determinados vectores definidos
a partir de la tabla del simplex.
Definición 5.1 Un vector x ∈ IRn es lexicográficamente positivo, y se denota por x ≻ 0 si, y sólo si,
x 6= 0 y la primera componente no nula es positiva.
112 5.2. Convergencia del algoritmo del simplex
El siguiente lema justifica el resultado principal, que garantizará que la variante lexicográfica no genera
ningún ciclo.
Lema 5.1 Aplicando el criterio de salida lexicográfico, siempre se puede conseguir que para cualquier
base B
Demostración:
El resultado es cierto si la solución básica factible es no degenerada, ya que x̄s > 0 ∀s ∈ I.
En otro caso, si se ordenan las variables para que las primeras sean las de holgura o artificiales que
proporcionan una solución básica factible inicial, el resultado es cierto para la tabla inicial y sólo habrá que
demostrar que el criterio de salida mantiene la propiedad:
Sea ylk > 0 el pivote.
La fila l-ésima es:
x̄l ′ yl1 yln
x̄′l = ,y = ′
, . . . , yln =
ylk l1 ylk ylk
y el resto de filas s 6= l son:
x̄l ′ yl1 yln
x̄′s = x̄s − ysk , ys1 = ys1 − ysk ′
, . . . , ysn = ysn − ysk
ylk ylk ylk
A continuación se demuestra que
1. s = l
(x̄′l , yl1
′ ′
, . . . , yln )
igual al vector
2. s 6= l
a) s 6∈ I0
1) ysk ≤ 0
ysk
(x̄′s , ys1
′ ′
, . . . , ysn ) = (x̄s , ys1 , . . . , ysn ) − (x̄l , yl1 , . . . , yln ) ≻ 0
ylk
J. Yáñez; J. Tejada 113
2) ysk > 0
x̄l x̄s
Al verificarse s 6∈ I0 y ser ysk > 0, se verifica < y, por consiguiente,
ylk ysk
x̄l
x̄s − ysk > 0
ylk
y la fila
(x̄′s , ys1
′ ′
, . . . , ysn )≻0
es lexicográficamente positiva.
b) s ∈ I0
x̄l
En este caso, ysk > 0 y x̄s − ysk = 0 de forma que el vector
ylk
(x̄′s , ys1
′ ′
, . . . , ysn ′
) = (0, ys1 ′
, . . . , ysn )
Para ver si este vector es lexicográficamente positivo se distinguen las siguientes posibilidades,
que son análogas a las analizadas en el caso s 6∈ I0 :
s 6∈ I1
En este caso, se verifica
ys1 yl1
>
ysk ylk
y el valor
′ yl1
ys1 = ys1 − ysk > 0
ylk
′ ′
Por tanto, el vector (0, ys1 , . . . , ysn )≻0
s ∈ I1
En este caso, se reitera el análisis anterior distinguiendo si s 6∈ I2 o s ∈ I2 ,...
El proceso necesariamente termina en algún Ij ; puesto que, en caso contrario, si
s ∈ I0 ∩ I1 ∩ . . . ∩ In
Observación 5.3 Con una ordenación adecuada de las columnas de la matriz A, concretamente, si-
tuando al principio las m columnas de la matriz identidad inicial, se determinarı́a en estas columnas la
inversa de la base B −1 en cada tabla del simplex y se limitarı́a a m el número máximo de conjuntos Ii
para resolver los empates posibles en la determinación de la variable que sale de la base.
Con la siguiente proposición se demuestra que no puede haber ciclos en el algoritmo del simplex si se
aplica la variante lexicográfica en el criterio de salida del algoritmo del simplex.
Proposición 5.1 Aplicando el criterio lexicográfico de salida, siempre se obtienen bases distintas en el
algoritmo del simplex.
114 5.2. Convergencia del algoritmo del simplex
Demostración:
En cada cambio de base a partir del pivote ylk > 0 se verifica
zk − c k
(z̄, z1 , . . . , zn ) − (z̄ ′ , z1′ , . . . , zn′ ) = (x̄l , yl1 , . . . , yln ) ≻ 0
ylk
Otra forma de evitar los ciclos en las sucesivas bases al aplicar el algoritmo del simplex se debe a
Bland y consiste en ordenar las variables y alterar el criterio de entrada del algoritmo del simplex:
Entra ak tal que
k = mı́n {j}
j∈J +
Para decidir la variable que sale de la base se emplea el criterio de salida usual y, en caso de empate,
se selecciona la variable de menor ı́ndice.
Aplicando el método de Bland al ejemplo 5.2, se obtienen las cuatro primeras tablas idénticas, en la
tabla asociada a la base B = {a6 , a5 , a3 }, sin embargo, el criterio de entrada de Bland determina como
vector de entrada a1 y el vector que sale a5 , de forma que el pivote es y51 = 1/16. Esta tabla y siguientes
son:
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
2 −3 0 −1/4 0 0 3 0
−1/2 x6 −3/2 1 0 1/8 0 1 −21/2 0
20 x5 1/16 −1/8 0 −3/64 1 0 3/16 0
0 x3 3/2 −1 1 −1/8 0 0 21/2 1
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 2 0 5/4 −32 0 −3 0
−1/2 x6 0 −2 0 −1 24 1 −6 0
0 x1 1 −2 0 −3/4 16 0 3 0
0 x3 0 2 1 1 −24 0 6 1
J. Yáñez; J. Tejada 115
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 0 −1/2 3/4 −20 0 −6 −1/2
−1/2 x6 0 0 1 0 0 1 0 1
0 x1 1 0 1 1/4 −8 0 9 1
0 x2 0 1 1/2 1/2 −12 0 3 1/2
0 0 0 −3/4 20 −1/2 6
x1 x2 x3 x4 x5 x6 x7
0 −3/2 −5/4 0 −2 0 −21/2 −5/4
−1/2 x6 0 0 1 0 0 1 0 1
0 x1 1 −1/2 3/4 0 −2 0 15/2 3/4
−3/4 x4 0 2 1 1 −24 0 6 1
que coincide con la solución obtenida con la variante lexicográfica.
Ejemplo 5.3 Sea el recinto de soluciones factibles —el análisis es independiente de la función objetivo—
definido por las inecuaciones:
2x1 + 3x2 ≤ 6
3x1 + 2x2 ≤ 6
x1 + x2 ≤ 4
xj ≥ 0 ∀j = 1, 2
que se puede interpretar de la siguiente forma: Para cualquier valor no negativo de las variables de holgura
xh1 y xh2 siempre se obtiene un valor positivo de la variable de holgura xh3 . Dicho de otro modo, cualquier
solución factible que verifique la primera y segunda inecuación, necesariamente verifica la tercera; ésta
es, pues, redundante.
La interpretación geométrica de este ejemplo es inmediata con la figura 5.1
✢
✙
xh3
☛
xh1
xh2
Proposición 5.2 Una condición suficiente para que la inecuación s-ésima (s ∈ {1, . . . , m}) sea redun-
dante geométricamente es la existencia de una base B que proporciona una solución básica factible que
incluya al vector ahs y que verifique lo siguiente:
J h ≡ i ∈ {1, . . . , m} / ahi 6∈ B, ysh ih ≤ 0 6= ∅
Las ecuaciones que provocan la redundancia geométrica de la inecuación s-ésima son las asociadas a
las variables de holgura del conjunto J h .
resuelto y conocida la base óptima B y la tabla del simplex asociada a esta base.
Introduciendo la variable de holgura xh2 y la artificial xa1 , se llega a la tabla óptima del simplex
1 −2 1 0 −
x1 x2 x3 xh2 xa1
−2 0 0 −1 − −1
1 x3 1 0 1 1/5 2/5 1
−2 x2 1 1 0 3/5 1/5 1
en la que se ha incluido la columna de la variable artificial para recuperar automáticamente la inversa de
la base óptima B:
! !
3 −1 −1 2/5 1/5
B = (a3 , a2 ) = B =
−1 2 1/5 3/5
zj′ − c′j ≤ 0 ∀j ∈ J
La base B sigue siendo óptima y la solución básica asociada es la óptima.
∃k ∈ J / zk − ck > 0
La base B no es la óptima del nuevo problema, pero al ser la solución básica factible, se aplica el
algoritmo del simplex hasta llegar al óptimo o detectar la solución no acotada.
3 −1 −1 0 −
x1 x2 x3 xh2 xa1
−5 0 0 −4/5 − −2
−1 x3 1 0 1 1/5 2/5 1
−1 x2 1 1 0 3/5 1/5 1
118 5.4. Análisis de sensibilidad de la solución óptima. Post-optimización
que es también óptima, por lo que se mantiene la solución óptima de P para el problema P ′ ası́ mo-
dificado.
2. ct = (−1, 2, 1)
La tabla obtenida al modificar los coeficientes de la función objetivo en la tabla óptima de P es:
−1 2 1 0 −
x1 x2 x3 xh2 xa1
4 0 0 7/5 − 3
1 x3 1 0 1 1/5 2/5 1
2 x2 1 1 0 3/5 1/5 1
que no es la óptima. Aplicando el algoritmo del simplex, después de dos iteraciones, se obtiene la
tabla óptima de P ′ :
−1 2 1 0 −
x1 x2 x3 xh2 xa1
0 −5/2 −5/2 0 − −1
−1 x1 1 −1/2 3/2 0 3/10 1
0 xh2 0 5/2 −5/2 1 1/2 0
Con las ideas anteriores se realiza automáticamente un análisis de sensibilidad de la solución óptima
respecto del vector c: La solución asociada a la base B seguirá siendo óptima siempre que se verifique
zj − cj ≤ 0 para todo j ∈ J.
A partir de este conjunto de desigualdades se identifican las condiciones que debe verificar el vector
c, fijando algunas o todas las componentes, para que la base siga siendo óptima.
La solución óptima asociada a la base B = (a3 , a2 ) del problema P del ejemplo 5.4 se mantiene si se
verifica la siguiente condición:
z1 − c 1 ≤ 0
c3 + c2 ≤ c1
zn+1 − cn+1 ≤ 0.
En este caso, el vector an+1 debe entrar en la base y es preciso un cambio de base siguiendo el
algoritmo del simplex.
En cualquier caso, la tabla del simplex ampliada proporciona una solución factible —la asociada a
B— y el algoritmo del simplex tratará que sea, además, óptima.
Introduciendo la variable x4 en el problema P del ejemplo 5.4 siendo c4 = −2 y at4 = (1, 1), se obtiene:
! ! !
2/5 1/5 1 3/5
y4 = B −1 a4 = =
1/5 3/5 1 4/5
y
!
3/5
z4 − c 4 = 1 −2 − (−2) = −1 + 2 = 1 > 0
4/5
Por tanto, hay que introducir el vector a4 en la base aplicando el algoritmo del simplex para obtener
la tabla óptima:
1 −2 1 −2 0 −
x1 x2 x3 x4 xh2 xa1
−5/4 −5/4 0 0 −7/4 − −9/4
1 x3 1/4 −3/4 1 0 −1/4 1/4 1/4
−2 x4 5/4 5/4 0 1 3/4 1/4 5/4
donde
cλ = c0 + λγ λ ≥ 0; c0 , γ ∈ IRn
2x1 +x2 ≥4
x2 ≤0
x1 −x2 ≤1
7. Identificar el conjunto de soluciones óptimas del problema cuya tabla del simplex óptima es la
siguiente:
5 2 −3 −1 1 0 −1 −3
x1 x2 x3 x4 x5 x6 x7 x8
0 0 0 0 0 0 0 0 1
5 x1 1 0 0 0 −1 2 0 −1 0
2 x2 0 1 0 1 0 −2 −2 1 2
−3 x3 0 0 1 1 −2 2 −1 0 1
M in −2x1 + x2
sujeto a 2x1 + 3x2 ≤ 6
5x1 + 2x2 ≤ 10
x1 + x2 ≤ 5
xj ≥ 0 j = 1, 2
122 5.5. Ejercicios propuestos
M in x1 − 3x2 − x3
x1 + 4x2 + 3x3 = 12
x1 + 2x2 − x3 = 4
xj ≥ 0 j = 1, 2, 3
resolver los siguientes problemas de postoptimización:
10. Analizar el problema de eliminar una restricción en un problema de programación lineal ya resuelto.
Dualidad
Dado un problema de programación lineal P , se define otro problema de programación lineal D, que
se denomina dual de P . Las relaciones que existen entre ambos problemas duales se ilustran a partir de
un ejemplo; posteriormente, se formaliza la relación del par de problemas (P, D) cuando P está planteado
en forma canónica.
Se introduce a continuación el par de problemas duales cuando el problema P está planteado en forma
estándar. Se detallan, además, las reglas que permitirán construir el problema dual de cualquier problema
de programación lineal, independientemente de su formulación.
Los teoremas de dualidad y el teorema de las holguras complementarias relacionan las soluciones
óptimas de los pares de problemas duales planteados, sin pérdida de generalidad, en forma canónica.
Se estudian a continuación las relaciones matemáticas entre las soluciones óptimas de los pares de
problemas duales planteados, sin pérdida de generalidad, en forma canónica: son los teoremas de dualidad
y teorema de las holguras complementarias.
Dado el par de problemas duales (P, D), se estudia la influencia que tiene en los teoremas de dua-
lidad vistos anteriormente el hecho de que la solución óptima de uno de los problemas sea degenerada.
Concretamente, se demuestra en este caso que el problema dual tiene múltiples soluciones óptimas.
Dado un problema Pc en forma canónica, su dual Dc admite una interpretación económica al identificar
las variables duales los precios de los recursos asociados a las restricciones de Pc . Se formaliza esta
interpretación económica y se incluye, además, el análisis en el caso en que la solución óptima del problema
Pc sea degenerada.
6.1. Introducción
A partir del problema de satisfacción de la demanda con mı́nimo coste introducido en la sección 1.1.2
del capı́tulo 1, se introducirá el par de problemas duales canónicos.
Ejemplo 6.1 El problema consistı́a en determinar las Tm. de basura que habı́a que transportar desde
cada uno de los cinco orı́genes disponibles 1, 2, 3, 4 y 5 para su reciclaje y obtener, a partir de ella, tres
productos A, B y C, con demanda semanal conocida.
El problema de programación lineal que se plantea considera como variable de decisión el vector
(x1 , . . . , x5 ), siendo xj la cantidad de basura recogida del origen j ∈ {1, . . . , 5}; identifica tres restric-
ciones para garantizar que la demanda de los productos A, B y C sea satisfecha; y, por último, el coste
es el asociado al transporte de la basura desde los orı́genes al centro de reciclado.
Se identifica ası́ el modelo canónico de programación lineal:
123
124 6.1. Introducción
M in 3x1 +2x2 +4x3 +5x4 +x5
0,1x2 +0,1x3 +0,6x4 ≥ 100
P 0,1x1 +0,2x2 +0,1x3 +0,1x4 +0,3x5 ≥ 80
0,2x1 +0,1x3 +0,3x4 +0,1x5 ≥ 60
xj ≥ 0 ∀j = 1, . . . , 5
La solución de este problema consiste en transportar 166,67 Tm. de basura del tipo 4 y 211,11 Tm.
del tipo 5. El coste mı́nimo es de 1044,444 euros.
Con los mismos datos, se plantea el gerente de esta empresa el siguiente problema:
¿Cuál es la máxima cantidad que está dispuesto a pagar por la compra de los tres productos, A, B y C,
como alternativa económicamente rentable al reciclado de la basura? Si identifica el precio máximo que
hace rentable la adquisición de los tres productos, encontrando unos precios inferiores, no serı́a rentable
el reciclado de basuras.
Se introduce como variable de decisión el vector (uA , uB , uC ) que identifica el precio a pagar por cada
Tm. de producto respectivamente. La cantidad de dinero a pagar será
Para que sea rentable, el precio que paga por los productos obtenidos de una tonelada de basura de cada
origen no puede superar el coste de transportar esa tonelada al centro de reciclado. En caso contrario,
serı́a más rentable seguir con el reciclado.
Para la basura procedente del origen 1, por ejemplo, esta restricción serı́a:
0,1uB + 0,2uC ≤ 3
Obviamente, el precio a pagar por cada Tm. de producto no puede ser negativa, es decir:
uA , uB , uC ≥ 0
Otra propiedad que se puede asegurar es que el precio total a pagar en D debe ser menor o igual que
el coste total asociado al transporte en P .
La solución óptima y el valor asociado de la función objetivo para el problema D, son:
Por tanto, ambos problemas están ı́ntimamente relacionados y tiene interés formalizar dicha relación
en general.
2. A cada restricción ≥ del problema primal se asocia una variable no negativa del problema dual,
denominada variable dual.
3. A cada variable no negativa del problema primal se asocia una restricción ≤ del dual.
5. El vector de coeficientes de la función objetivo del problema dual es el vector de términos indepen-
dientes del primal.
Los problemas P y D definidos en el ejemplo 6.1 identifican un par de problemas duales en forma
canónica.
Las reglas que permiten definir Dc a partir de Pc permiten definir Pc a partir de Dc . Se observa ası́ que
la definición del problema dual es involutiva, pudiendo afirmar que cada uno de los problemas del par
(Pc , Dc ) es el dual del otro: Dc = D(Pc ) y Pc = D(Dc ).
En efecto, transformando el problema Dc a la forma canónica se tiene el par de problemas duales:
126 6.2. Pares de problemas duales
−M in
−bt u −M ax
−ct w
Dc′ −At u ≥ −c D(Dc′ ) (−A)w ≤ −b
u ≥0 w ≥0
Definición 6.2 Dado el problema de programación lineal en forma estándar Ps , se define el par de
problemas duales (Ps , Ds ) cuando tienen la siguiente estructura:
ct x (
M in M ax bt u
Ps Ax =b Ds
At u ≤c
x ≥0
El problema dual de Ps′ tiene tantas variables como inecuaciones, sean vi1 y vi2 las variables duales
asociadas a las primeras y últimas m inecuaciones respectivamente. Se tiene entonces el par de problemas
duales en forma canónica:
ct x
M in
t 1 t 2
Ax ≥ b M ax b v + (−b) v
Ps′ Ds′ At v1 − At v2 ≤ c
−Ax ≥ −b
v1 , v2 ≥ 0
x ≥0
u = v1 − v2
que al ser diferencia de vectores con componentes no negativas no está restringido en signo.
Por consiguiente, el problema dual de Ds′ es equivalente a Ds
(
M ax bt u
Ds
At u ≤ c
Se observa ası́ que al sustituir en la forma estándar las inecuaciones por ecuaciones, las variables
duales no están restringidas en signo.
J. Yáñez; J. Tejada 127
1. Las variables duales asociadas a inecuaciones del tipo ≤ en el problema primal de minimización son
variables no positivas.
2. Las inecuaciones del problema de maximización dual asociadas a variables no positivas del problema
primal son del tipo ≥.
En el siguiente ejemplo se mezclan desigualdades de los dos signos y se observa cómo los duales de
los problemas equivalentes a P son equivalentes entre sı́, lo que valida cualquier transformación de un
problema a cualquiera de las formulaciones ya introducidas para determinar el problema dual D = D(P ).
Ejemplo 6.2
M in 2x1 + 3x2
x1 − x2 ≥1
P 2x1 + x2 ≤3
x1 + x2 =1
x1 ≥0
M in 2x1 +3x+
2 −3x−
2
M ax u1 +3u2 +u3
x1 −x+
2 +x−
2 −xh1 =1
u1 +2u2 +u3 ≤2
2x1 +x+
2 −x−
2 +xh2 =3 −u1 +u2 +u3 ≤3
P1 D1
x1 +x+
2 −x−
2 =1
u1 −u2 −u3 ≤ −3
xj ≥ 0 ∀j
−u1 ≤0
xhi ≥ 0 ∀i u2 ≤0
128 6.2. Pares de problemas duales
P1 D1
P P2 D2 D
P3 D3
M ax −2x1 −3x2
−x1 +x2 ≤ −1 M in w1 +3w2 +w3 −w4
2x1 +x2 ≤3 −w1 +2w2 +w3 −w4 ≥2
P3 D3
x1 +x2 ≤1
w1 +w2 +w3 −w4 = −3
−x1 −x2 ≤ −1 wi ≥ 0 ∀i
x1 ≥0
La equivalencia de los problemas D1 , D2 y D3 se formaliza por las relaciones de sus variables duales:
u 1 = v 1 = w1
−u2 = v2 = w2
u 3 = v 3 = w4 − w3
La figura 6.1 ilustra las distintas formulaciones del problema P y sus duales correspondientes.
En este ejemplo se observa que los duales de dos problemas equivalentes, son también equivalentes.
Sin embargo, ¿cuál es la formulación del problema D, dual de P , y equivalente a D1 , D2 y D3 ?
A continuación se resumen en una tabla las reglas que permiten definir el problema dual D = D(P )
de cualquier problema de programación lineal P . Con estas reglas se identifica el (único) problema dual
de cualquier problema de programación lineal, independientemente de la formulación utilizada.
J. Yáñez; J. Tejada 129
Aplicando las reglas de esta tabla al problema P del ejemplo 6.2, se determina el problema dual
D = D(P ):
M ax u1 +3u2 +u3
u1 +2u2 +u3 ≤2
D= −u1 +u2 +u3 =3
u1 ≥0
u2 ≤0
Se puede observar que este problema es equivalente a D1 , D2 y D3 .
En el ejemplo 6.1, a partir del planteamiento del problema D que hace el gerente, está claro que
cualquier asignación válida de precios a los productos A, B y C debe asegurar una cantidad total a pagar
menor o igual que el coste de transportar basura para reciclar y verificando, además, las restricciones de
demanda de los tres productos.
Es decir, el valor de cualquier solución factible del problema D debe ser menor o igual que el valor de
cualquier solución factible del problema P .
Esta propiedad, recogida en la siguiente proposición, es conocida también como el Teorema débil de
dualidad.
Proposición 6.1 Dadas x̄ y ū, soluciones factibles de Pc y Dc respectivamente, siempre se verifica que
ct x̄ ≥ bt ū
Demostración
Al ser ū solución factible de Dc se verifica que ct x̄ ≥ ūt Ax̄ y al ser x̄ solución factible de Pc el último
término es, a su vez, mayor o igual que ūt b.
130 6.3. Teorema fundamental de dualidad
Corolario 6.1 Si los dos problemas duales tienen solución factible, entonces existe solución óptima para
ambos.
Demostración
Por la proposición 6.1, cada una de las funciones objetivo de las soluciones factibles acota la función
objetivo del problema dual. Ası́, de las tres posibles salidas de un problema de programación lineal, se
descartan dos de ellas: no existencia de solución factible y solución no acotada. Por consiguiente, los dos
problemas duales, tienen solución óptima.
ct x̄ = bt ū
Demostración
En caso contrario, si existiera una solución factible x∗ de Pc mejor que x̄ verificarı́a
ct x∗ < ct x̄ = bt ū
En el ejemplo 6.1, se verifica que el valor de las funciones objetivo de P y D coinciden en las soluciones
óptimas.
Demostración
En primer lugar, y con el fin de obtener la solución óptima de Pc , se introducen las correspondientes
variables de holgura xh para resolver el problema equivalente Ps en forma estándar.
Sea x̄ la solución óptima de Ps y sea B la base óptima. Por el teorema 3.1, se verifica
zj − c j ≤ 0 ∀j ∈ J
ctB B −1 aj ≤ cj ∀j ∈ J
ūt ≡ ctB B −1
ūt aj ≤ cj ∀j ∈ J
además,
ūt A ≤ ct
Si, además, se utiliza la optimalidad de la base B para las columnas asociadas a las variables de
holgura xh , se obtiene:
donde ei es el vector unitario y chi = 0 es el coste de la variable de holgura xhi . Se ha demostrado ası́ que
ū ≥ 0
que es solución factible del problema dual y alcanza el mismo valor, 1044,445, para la función objetivo.
zj − c j ≥ 0 ∀j ∈ J
por lo que se obtiene que ctB B −1 es una solución del problema dual.
En el ejemplo anterior, se puede obtener la solución óptima de Pc a partir de la tabla óptima del
problema Dc al añadir las variables de holgura uh :
Observación 6.1 De la proposición 6.2 se deduce automáticamente que la solución óptima del problema
dual en el caso estándar (Ds ) es ūt = ctB B −1 , siendo B la base óptima del problema Ps .
La única diferencia entre Pc y Ps es que éste no tiene variables de holgura con las que se asegura la
no negatividad de la variable dual ū.
Considerando ası́ la doble implicación en la proposición 6.2 se concluye el siguiente corolario, que en
algunos textos destacan como teorema fuerte de dualidad:
Corolario 6.3 Un problema de programación lineal Pc tiene solución óptima si y sólo si su dual Dc tiene
solución óptima.
La condición suficiente de optimalidad de un par de soluciones factibles duales (x̄, ū), demostrada en
el corolario 6.2, es, además, una condición necesaria, según se demuestra en el siguiente
ct x̄ = bt ū
Demostración
Sea x̄ una solución óptima de Pc y sea B una base óptima, por la proposición 6.2 se construye la
solución óptima del dual ūtx = ctB B −1 , por lo que verifica
Al ser ū solución óptima de Dc , debe alcanzar el mismo valor de la función objetivo, es decir
bt ū = bt ūx
La siguiente proposición analiza el caso en que el problema Pc tiene solución óptima no acotada.
Proposición 6.3 Si el problema Pc tiene solución no acotada, entonces el problema dual Dc no tiene
solución factible.
Demostración
El problema dual Dc no puede tener ninguna solución factible; en caso contrario, sea ū una solución
factible de Dc con valor de la función objetivo z̄ = bt ū.
Al ser Pc un problema con solución no acotada, se puede encontrar una solución factible, sea x̄z , tal
que
ct x̄z < z̄ = bt ū
lo que contradice la proposición 6.1.
Ejemplo 6.3
M in −x1
M ax 3u1 + 4u2
x1 − x2 ≥ 3 u1 − u2 ≤ −1
P D
−x1 + x2 ≥ 4
−u1 + u2 ≤ 0
xj ≥ 0 j = 1, 2 ui ≥ 0 i = 1, 2
Con los resultados previos, se pueden enunciar el siguiente teorema, denominado teorema fundamental
de dualidad. Este teorema es válido no sólo para la formulación canónica, sino para cualquier formulación
del par de problemas duales.
Teorema 6.1 Dados dos problemas duales P y D, una y sólo una de las siguientes afirmaciones es
cierta:
Teorema 6.2 Dados dos problemas duales Pc y Dc en forma canónica, dos soluciones factibles x̄ y ū
son óptimas si y sólo si verifican (
ūt (Ax̄ − b) = 0
(ct − ūt A)x̄ = 0
134 6.4. Teorema de las holguras complementarias
Demostración
Al ser x̄ y ū dos soluciones factibles de Pc y Dc respectivamente, se verifica
α := ūt (Ax̄ − b) ≥ 0
α + β = ct x̄ − ūt b
A partir de este teorema, tiene sentido asociar a cada variable de Pc (Dc ) la variable de holgura
asociada en el problema dual Dc (Pc ) a la restricción dual:
xj de Pc ←→ uhj de Dc ∀j ∈ {1, . . . , n}
xhi de Pc ←→ ui de Dc ∀i ∈ {1, . . . , m}
La interpretación del teorema 6.2 es clara: si una variable de Pc (Dc ) es positiva, la del problema dual
Dc (Pc ) asociada, en el sentido anterior, es nula:
Si la variable de Pc es x̄j > 0, con j ∈ {1, . . . , n}, entonces la inecuación j-ésima del problema Dc
verifica la igualdad y se dice que la restricción es activa.
Si la variable de Pc es x̄hi > 0, con i ∈ {1, . . . , m}, es decir, la restricción i-ésima es inactiva, entonces
la variable i-ésima del problema Dc es nula.
(x1 , uh1 ); (x2 , uh2 ); (x3 , uh3 ); (x4 , uh4 ); (x5 , uh5 )
Se verifica el teorema de las holguras complementarias al haber un cero en cada uno de los pares
anteriores.
La proposición 6.2 permite obtener la solución óptima del dual a partir de la solución óptima del
primal. Para determinar la base óptima del dual BD a partir de la base óptima del primal B, se sigue la
siguiente regla:
J. Yáñez; J. Tejada 135
Si el vector unitario −ei de dimensión n, asociado a la variable de holgura xhi , con i ∈ {1, . . . , m},
pertenece a B, entonces el vector fila ai de A, asociado a la variable i-ésima de Dc , no pertenece a
BD .
El valor óptimo de la variable dual es ūi = 0
Si el vector unitario −ei de dimensión n, asociado a la variable de holgura xhi , con i ∈ {1, . . . , m},
no pertenece a B, entonces el vector fila ai de A, asociado a la variable i-ésima de Dc , pertenece a
BD .
El valor óptimo de la variable dual es ūi = −zih
El teorema 6.2 no excluye el caso en que los dos valores de las variables emparejadas del par de
problemas duales sean nulos. Esta situación está relacionada con la degeneración y multiplicidad de
soluciones duales, que se estudia a continuación.
Proposición 6.4 Si el problema P tiene múltiples soluciones óptimas, entonces el dual D tiene solución
óptima degenerada.
Demostración
Sea B una base óptima de P para la que existe k ∈ J tal que zk − ck = 0. Se consideran entonces las
dos posibilidades de multiplicidad de soluciones óptimas:
yk 6≤ 0
En este caso, existe una nueva solución básica:
( ) !
x̄l x̄s −yk
x̄′k = = M in / ysk > 0 >0 k
γ =
ylk ysk ek
B ′−1 = Jlk B −1
siendo
1 ··· −y1k /ylk ··· 0
. .. ..
.
. . .
Jlk =
0 ··· 1/ylk ··· 0
. .. ..
.. . .
0 ··· −ymk /ylk ··· 1
Dividiendo esta expresión por ylk 6= 0, el elemento pivote del cambio de base desde B a B ′ , se
obtiene:
y1k 1 ymk
cl = − c1 − · · · + ck − · · · − cm
ylk ylk ylk
Observando la matriz Jlk y que todas las componentes de los vectores cB y cB ′ coinciden excepto
cl , que es sustituida por ck , se concluye la relación:
yk ≤ 0
En este caso, el vector γ k determina la dirección extrema de forma que cualquier solución factible
a lo largo de esta dirección:
x = x̄ + xk γ k ∀xk ≥ 0
es óptima.
La solución dual óptima ut = ctB B −1 es degenerada en la componente asociada a uhk , ya que por el
teorema 6.2, el producto x̄k ·ūhk = 0 y la variable xk > 0 puede tomar valores arbitrarios manteniendo
la optimalidad.
Los dos casos anteriores se ilustran con los ejemplos 6.4 y 6.5:
La tabla óptima asociada a la base B = (ah2 , a1 ) del problema P , en la que se incluyen las variables
artificiales originales para evaluar directamente la inversa B −1 , es
0 0 −7 −2 0 2
0 4 −5 −2 1 2 −1 1
1 1 −2 −1 0 1 0 1
0 0 −7 −2 0 2
0 1 −5/4 −1/2 1/4 1/2 −1/4 1/4
1 0 −3/4 −1/2 −1/4 1/2 1/4 3/4
Las soluciones duales asociadas a las dos bases óptimas anteriores son
!
2 −1
t t −1
ū = cB B = 0 2 = 2 0
1 0
y !
1/2 −1/4
t
ū′ = ctB ′ B ′−1 = 2 2 = 2 0
1/2 1/4
138 6.5. Degeneración y multiplicidad de soluciones óptimas (*)
0 1 1 0 0 2
1 2 1 0 0 2
0 −4 −1 1 0 0
0 5 2 0 1 7
0 0 3/4 1/4 0 2
1 0 1/2 1/2 0 2
0 1 1/4 −1/4 0 0
0 0 3/4 5/4 1 7
Las bases óptimas del dual están asociadas a las variables (u1 , uh2 , uh3 ) y (u1 , u2 , uh3 ) respectivamente
y ambas son soluciones degeneradas.
0 −1 0 −1 0 1
0 4 −5 −2 1 2 −1 1
1 1 −2 −1 0 1 0 1
En sentido inverso, es decir, para conseguir la multiplicidad de soluciones óptimas del problema D a
partir de la degeneración de la solución óptima de P , procediendo de forma análoga a la proposición 6.4,
se distinguen dos casos:
Proposición 6.5 Si el problema P tiene una solución óptima degenerada en la coordenada l-ésima y
verifica:
Demostración
Al ser B una base óptima, el vector ūt = ctB B −1 es una solución óptima de D.
Pivotando en el elemento ylk determinado por la condición 2, se obtiene otra base
B ′ = B ∪ {ak } − {al }
que, al partir de una solución degenerada obtiene otra solución básica idéntica a la anterior pero con
distinta base.
t
Al ser zk − ck < 0, la solución dual obtenida según ū′ = ctB ′ B ′−1 es distinta a la anterior y óptima
para D.
0 −1 −5 −1 0 1
0 4 −5 −2 1 2 −1 0
1 1 −2 −1 0 1 0 1
Se puede observar que verifica las hipótesis de la proposición 6.5. Eligiendo el pivote y2h ,1h = −2 se
obtiene la tabla óptima
0 −1 −5/2 0 −1/2 1
0 −2 5/2 1 −1/2 −1 1/2 0
1 −1 1/2 0 −1/2 0 1/2 1
Las soluciones duales asociadas a las dos bases óptimas anteriores son
!
2 −1
t t −1
ū = cB B = 0 1 = 1 0
1 0
y !
−1 1/2
t
ū′ = ctB ′ B ′−1 = 0 1 = 0 1/2
0 1/2
140 6.5. Degeneración y multiplicidad de soluciones óptimas (*)
A continuación se utilizarán las filas de la inversa de la base, por lo que se introduce la siguiente
notación:
Sea βi , con i ∈ {1, . . . , m}, el vector (columna) cuyos elementos son los de la fila i-ésima de la matriz
B −1 , es decir:
β1t
.
B −1 = .
.
t
βm
Proposición 6.6 Si el problema P tiene una solución óptima degenerada en la coordenada l-ésima y
verifica:
1. ylj ≥ 0 ∀j ∈ J
2. βl ≤ 0
Demostración
A partir de la solución del dual ūt = ctB B −1 y de βl , siendo x̄l = 0 la componente que identifica la
solución degenerada, se define
ūλ = ū − λβl
s ∈ I − {l}
ūtλ as = ūt as − λβlt as = ūt as − λ · 0 ≤ cs ∀λ ≥ 0
s=l
ūtλ al = ūt al − λβlt al = ūt al − λ · 1 ≤ cl ∀λ ≥ 0
j∈J
ūtλ aj = ūt aj − λβlt aj = ūt aj − λ · ylj ≤ cs ∀λ ≥ 0
Para ver que ūλ es solución factible, se aplica la condición de optimalidad zj −cj ≤ 0 para las variables
de holgura y se demuestra ası́ que ū ≥ 0.
Para demostrar que ūλ ≥ 0, considerando la hipótesis adicional de ser el vector βl ≤ 0, se verifica
ūλ ≥ 0 ∀λ ≥ 0
y existe, por tanto, una dirección en el recinto de soluciones factibles del problema dual que identifica un
conjunto de soluciones óptimas.
Por último, se demuestra la optimalidad de ūλ para todo λ ∈ [0, ∞):
0 −4 0 −1 1
0 1 1 1 −1 0
1 −2 0 −1 1 1
Al verificar las condiciones de la proposición 6.6, no se puede pivotar en ningún elemento de la fila
h
1 -ésima sin perder la optimalidad de la tabla.
La tabla óptima del problema dual es la siguiente
0 0 1 0 1
−1 1 1 0 1
−1 0 2 1 4
que corresponde a la solución óptima múltiple con una base óptima única.
Aplicando la demostración de la proposición 6.6 se construye la familia de soluciones óptimas de D:
ūλ = ū − λβl
siendo
!
−1 −1
B= {ah1 , a1 } =
0 1
!
−1 −1
B −1 =
0 1
! !
−1 0
β 1h = ≤
−1 0
!
−1 −1
ūt = 0 1 = 0 1
0 1
de forma que
ūtλ = (0 + λ, 1 + λ) ≥ (0, 0) ∀λ ≥ 0
Ejemplo 6.8 Sea el siguiente problema de producción de dos bienes 1 y 2, cuyo beneficio unitario es 5
y 9 respectivamente. En la producción de estos bienes se consumen dos tipos de recursos, de los que hay
disponibles 15 y 20 unidades respectivamente. El modelo de programación lineal es el siguiente:
M ax 5x1 + 9x2
2x1 + 3x2 ≤ 15
4x1 + 3x2 ≤ 20
xj ≥ 0 j = 1, 2
Una vez resuelto el problema de maximización P , se plantea la siguiente cuestión: ¿Cuánto disminuirı́a
la función objetivo si disminuye en una unidad cada uno de los recursos asociados a las restricciones?
En el ejemplo 6.8, el beneficio máximo alcanzado es de 45 unidades monetarias para 15 y 20 unidades
de los recursos 1 y 2 respectivamente.
Considerando 14 unidades disponibles del recurso 1, se consigue una función objetivo máxima de
42. La disminución de la función objetivo es, pues, de 3 unidades monetarias.
Considerando 19 unidades disponibles del recurso 2, se consigue una función objetivo máxima de
45. No se ha disminuido, por consiguiente, la función objetivo.
Definición 6.3 El precio dual de venta, precio de venta en la sombra o precio de venta imputado de un
recurso es el precio mı́nimo unitario al que interesa vender dicho recurso para que compense la disminu-
ción del beneficio óptimo de P que implica la menor disponibilidad del citado recurso.
El precio dual de venta se denota por el vector pv ∈ IRm
Considerando 16 unidades disponibles del recurso 1, se consigue una función objetivo máxima de
48. El incremento es, pues, de 3 unidades monetarias.
Considerando 21 unidades disponibles del recurso 2, se consigue una función objetivo máxima de
45. No se ha incrementado, por consiguiente, la función objetivo.
Ası́ pues, compensa económicamente incrementar el recurso 1 siempre que el precio pagado por adquirir
cada unidad del mismo sea inferior a 3 unidades monetarias. Por otra parte, no compensa económicamente
la adquisición de unidades adicionales del recurso 2 a ningún precio (positivo).
Tiene sentido, pues, introducir la siguiente definición.
J. Yáñez; J. Tejada 143
Definición 6.4 El precio dual de compra, precio de compra en la sombra o precio de compra imputado
de un recurso es el precio máximo unitario al que interesa comprar dicho recurso para que compense el
incremento del beneficio óptimo de P que implica la mayor cantidad de recurso disponible.
El precio dual de compra se denota por el vector pc ∈ IRm
El nombre de precio dual se justifica por la relación que existe con las variables del problema dual.
Sea la ecuación de coste del sistema explı́cito asociado a la base óptima del problema P :
X X
z = z̄ − (zj − cj )xj = ctB B −1 b − (zj − cj )xj
j∈J j∈J
Considerando que ūt = ctB B −1 es la solución óptima del dual asociada a B, base óptima de P , se
tiene la expresión equivalente:
m
X X
z= ūi bi − (zj − cj )xj
i=1 j∈J
∂z
= ūi
∂bi
En consecuencia, la disminución (aumento) de una unidad del recurso i-ésimo se traduce en una
disminución (aumento) de ūi unidades monetarias del beneficio total.
En el ejemplo 6.8, el precio de venta en la sombra de los recursos 1 y 2 coincide con la variable
dual óptima ū del problema D. En efecto, a partir de la tabla óptima del simplex, asociada a la base
B = (a2 , ah2 ), se deduce
!
1/3 0
ūt = ctB B −1 = 9 0 = 3 0
−1 1
y se verifica !
v 3
p = ū =
0
La dependencia del beneficio óptimo z̄ respecto de b1 y b2 , manteniendo el otro recurso fijo, se repre-
senta en la figura 6.2.
La igualdad de los precios duales de venta y compra se verifica cuando existe una única solución
óptima del dual, lo que se garantiza si la solución óptima del problema P es no degenerada. En esta
situación existe la derivada parcial del beneficio óptimo z̄ respecto de bi para cualquier i ∈ {1, . . . , m}.
Es el caso del ejemplo 6.8.
144 6.6. Interpretación económica. Análisis de la degeneración (*)
El caso general, sin embargo, es más complejo y requiere un análisis más detallado. Para ilustrar esta
situación, relacionada con la solución óptima degenerada, se introduce otro ejemplo de programación
lineal de máximo con restricciones del tipo ≤:
Ejemplo 6.9
M ax 5x1 + 6x2
2x1 + 3x2 ≤ 15
4x1 + 3x2 ≤ 20
6x1 + 9x2 ≤ 45
xj ≥ 0 j = 1, 2
alcanzando la función objetivo el valor 32,5.
A partir de la tabla óptima del simplex, asociada a la base B = {a2 , a1 , ah3 }:
se puede comprobar cómo al disminuir en una unidad el recurso 3, la función objetivo disminuye hasta
32 mientras que el valor de ū3 = 0.
Esta discrepancia se explica por la existencia de una solución óptima degenerada del problema P , lo
que provoca —si el problema está bien planteado y no es redundante— la multiplicidad de soluciones
óptimas del problema dual D.
De los dos posibles casos de multiplicidad de soluciones óptimas de D en función de la existencia de
una componente l ∈ I tal que x̄l = 0, sólo interesa el analizado en la proposición 6.5, cuando y 6≥ 0, ya
que en este caso, al pivotar en los distintos ylj < 0 se obtendrı́an distintas bases óptimas B, B ′ , . . ., que,
al ser x̄l = 0, están asociadas a la misma solución óptima de P , pero proporcionan diferentes soluciones
básicas del problema D: ctB B −1 , ctB ′ B ′−1 , . . .
Esta es la situación que se presenta en el problema P del ejemplo 6.9. A partir de la tabla óptima
anterior, y pivotando en el elemento y3h ,1h = −3, se obtiene otra tabla óptima, asociada a la nueva base
B ′ = {a2 , a1 , ah1 }:
Obsérvese que el precio en la sombra del recurso 3 coincide con el valor ū′3 = 1/2.
el precio de venta en la sombra de cada uno de los m recursos asociados a las restricciones se determina
según
pvi = máx {ūki } i ∈ {1, . . . , m}
1≤k≤K
donde {ū1 , ū2 , . . . , ūK } es el conjunto de soluciones óptimas básicas del problema D.
Demostración
Fijado i ∈ {1, . . . , m}, se supone sin pérdida de generalidad que
pvi ≤ ū1i
Considerando todas las representaciones de la ecuación de coste de los K sistemas explı́citos:
X m
X X
z = z̄ − (zj − cj )xj = ūki bi − (zj − cj )xj ∀k ∈ {1, . . . , K}
j∈J i=1 j∈J
Si pvi > ū1i , entonces pvi > ūki ∀k y, por consiguiente, se podrı́a obtener un precio menor que hiciera
rentable la venta de unidades del recurso i-ésimo, lo que irı́a en contra de la definición de pvi .
pvi ≥ ū1i
En caso contrario, es decir, si pvi < ū1i , en la representación
m
X X
z= ū1i bi − (zj − cj )xj
i=1 j∈J
se observa que decrece más rápidamente la función objetivo que el beneficio directo por la venta
del recurso i-ésimo, por lo que no compensa el citado precio.
Análogamente, con el precio de compra dual, se tiene la siguiente proposición, que se demuestra de
forma análoga.
146 6.6. Interpretación económica. Análisis de la degeneración (*)
el precio de compra en la sombra de cada uno de los m recursos asociados a las restricciones se determina
según
pci = mı́n {ūki } i ∈ {1, . . . , m}
1≤k≤K
donde {ū1 , ū2 , . . . , ūK } es el conjunto de soluciones óptimas básicas del problema D.
En el ejemplo 6.9
mı́n{3/2, 0} 0
pc = mı́n{1/2, 1/2} = 1/2
mı́n{0, 1/2} 0
La dependencia del beneficio óptimo z̄ respecto de b1 , b2 y b3 manteniendo los otros recursos fijos, se
representa en la figura 6.3.
Se puede concluir que el precio en la sombra de un recurso está asociado a un intervalo cuyo lı́mite
inferior es el precio de compra dual del citado recurso y el lı́mite superior es el precio de venta dual del
citado recurso. Se introduce la siguiente definición
Definición 6.5 El margen dual del recurso i-ésimo es el intervalo definido por los precios de compra y
de venta duales del citado recurso:
Como consecuencia de las proposiciones 6.7 y 6.8, el margen dual está bien definido.
El margen dual especifica el rango de precios a los que no interesa comprar o vender unidades del
recurso en cuestión. Interesa comprar unidades adicionales del recurso i-ésimo siempre que el precio de
compra sea inferior a pci . Interesa vender unidades del recurso i-ésimo siempre que el precio de venta del
mismo sea superior a pvi .
Cuando la solución óptima de P es degenerada, entonces el margen dual es el vector de intervalos
md = (pc , pv )
Definición 6.6 El recurso i-ésimo admite el precio dual, precio en la sombra o precio imputado, y se
denota por pi , cuando coinciden los valores del precio de compra y venta duales del citado recurso:
p = pc = pv = ū
a)
M ax −2x1 + x2
sujeto a −x1 + 2x2 ≤4
−7x1 + 2x2 ≤ 15
x1 + x2 ≤3
x2 ≥0
b)
M in 3x1 + x2
sujeto a −x1 + 2x2 ≤4
7x1 + 2x2 ≥ 15
x1 , x2 ≥0
c)
M ax x1 + x2
sujeto a −2x1 + x2 ≤1
x2 ≤2
x1 + x2 ≤3
x1 , x2 ≥0
d)
M ax 3x1 + 2x2
sujeto a 2x1 − 3x2 ≤6
−4x1 + 5x2 ≤ 15
x1 , x2 ≥0
e)
M in 3x1 + 4x2
sujeto a 2x1 + 3x2 ≤6
−3x1 + 5x2 ≥ 15
x1 , x2 ≥0
f)
M in 3x1 + 4x2
sujeto a 2x1 + 3x2 ≤6
−3x1 + 5x2 ≥ 15
x1 , x2 ≥0
J. Yáñez; J. Tejada 149
Justificar mediante el teorema de las holguras complementarias que el vector (4, 0, 0) es la solución
óptima sabiendo que (0, 2) es una solución del problema dual.
3. Demostrar que si el problema mı́n{ct x/Ax = b, x ≥ 0} tiene solución óptima finita, entonces el
problema mı́n{ct x/Ax = b′ , x ≥ 0} no puede tener solución no acotada, cualquiera que sea b′ .
4. Dado el problema mı́n{ct x/Ax = b, l ≤ x ≤ u}, siendo todas las componentes de l y u finitas, se
pide:
a) Determinar el dual.
b) Demostrar que siempre existe solución factible del dual.
c) Si el problema original tiene solución factible, ¿qué se puede deducir respecto del dual?
¿Qué ocurre en la solución del dual si la k-ésima restricción del primal se multiplica por un
escalar λ 6= 0.?
¿Qué ocurre en la solución del dual si se suman dos restricciones del primal para sustituir a
una de ellas?
¿Qué ocurre en las soluciones del primal y del dual si se suman dos columnas del primal para
sustituir a una de ellas?
Ax ≥ 0 ct x < 0
w t A = ct w≥0
7. Comprobar que la segunda condición de las proposiciones 6.5 y 6.6 es necesaria a partir del par de
problemas duales:
M ax u1 +u2
M in x1 +2x2 −2x3
u1 +2u2 ≤1
x1 +x2 −2x3 ≥1
P D u1 −2u2 ≤2
2x1 −2x2 +x3 ≥1
−2u1 +u2 ≤ −2
xj ≥ 0 ∀j
ui ≥ 0 ∀i
8. Dos jugadores se enfrentan en un juego en el que uno de ellos, jugador A, tiene tres opciones (1,2,3)
y el otro, jugador B, tiene dos (1,2). La matriz adjunta, con dos filas y tres columnas, representa el
pago que realiza A a B cuando A elige la columna y B la fila:
1 2 3
1 2 -2 -1
2 -2 3 1
150 6.7. Ejercicios propuestos
Cada uno de los jugadores elige su opción sin conocer la elección del otro. Se permiten opciones
aleatorizadas para cada uno de los jugadores. Este tipo de situación identifica un juego de suma
nula.
Desde el punto de vista del jugador A, sean (x1 , x2 , x3 ) la distribución de probabilidad asignada a
cada una de sus tres opciones. Obviamente, x1 + x2 + x3 = 1.
Además, si el jugador B elige la opción 1, el pago medio que realiza A será 2x1 − 2x2 − x3 , mientras
que si elige la opción 2, el pago medio será −2x1 + 3x2 + x3 .
Se pide:
a) Identificar y resolver el modelo de programación lineal que garantiza el menor pago posible
que realizará el jugador A para cualquiera de las decisiones del jugador B.
b) Plantear el dual de este problema y resolverlo
c) Comprobar que el dual plantea el problema desde el punto de vista del jugador B.
d ) Interpretar el teorema de las holguras complementarias.
J. Yáñez; J. Tejada 151
z̄ z̄
.
45 45
15 b1 20 b2
z̄ z̄ pv2 = pc2 z̄
pc1 pc3
pv3
pv1
15 b1 20 b2 45 b3
Algoritmo dual
En determinadas situaciones, el algoritmo del simplex no es el procedimiento más eficiente para resolver
un problema de programación lineal; es el caso de la programación entera, que se verá en la siguiente
parte. En estos problemas se dispone de soluciones básicas no factibles pero verificando la condición de
optimalidad al tener los costes reducidos no negativos. Se introduce ası́ el concepto de solución dual-
factible.
Se proponen a continuación los teoremas que soportan teóricamente el algoritmo dual y los correspon-
dientes cambios de base. El algoritmo dual se basa en las propiedades de los pares de problemas duales.
Se proporciona el esquema del algoritmo dual y se detalla un procedimiento de inicialización.
Una aplicación inmediata del algoritmo dual se ofrece al analizar la sensibilidad de la solución óptima
respecto del vector de términos independientes b. Se analizan, además, los problemas de post-optimización
que se plantean al modificar este vector o al añadir nuevas restricciones al problema de programación
lineal. Por otra parte, ante la incertidumbre de la información, se puede plantear un problema de pro-
gramación lineal donde el vector b depende de un parámetro; serı́a un problema de parametrización que
también es resuelto con el algoritmo dual.
Combinando las propiedades del algoritmo del simplex y el algoritmo dual, se propone el algoritmo
primal-dual, que tiene aplicaciones en algoritmos de optimización en redes dirigidas.
M in 2x1 +3x2 +x3
2x1 +x2 −x3 ≥2
P
x1 +x2 +x3 ≥1
xj ≥ 0 j = 1, 2, 3
Multiplicando las dos inecuaciones por −1 se obtiene directamente la tabla del simplex asociada a la
base B = (ah1 , ah2 ):
153
154 7.1. Introducción. Solución dual-factible
2 3 1 0 0
x1 x2 x3 xh1 xh2
−2 −3 −1 0 0
0 xh1 −2 −1 1 1 0 −2
0 xh2 −1 −1 −1 0 1 −1
La solución básica verifica la condición zj − cj ≤ 0 para todo j ∈ J aunque no es factible al tener
alguna componente negativa.
Interesa distinguir este tipo de solución básica, por lo que se introduce la siguiente definición.
Definición 7.1 Dado el problema de programación lineal P , una solución dual-factible es una solución
básica asociada a una base B:
! !
xB B −1 b
x̄ = =
xN 0
verificando
zj − c j ≤ 0 ∀j ∈ J
Observación 7.1 El nombre se justifica porque una solución dual-factible permite construir, ver propo-
sición 6.2, una solución factible del problema dual D = D(P ):
ūt = ctB B −1
Conviene destacar que la solución dual-factible es siempre del problema P —el problema a resolver—
y no de su dual D.
ūt = ctB B −1
es la solución óptima del problema D
A partir de esta notación, conviene recordar que el algoritmo del simplex, partiendo de una solución
básica factible (primal-factible), cambia a otra solución básica factible y el proceso termina cuando,
además, la solución básica es dual-factible.
El algoritmo dual, en cambio, parte de una solución dual-factible y en cada iteración cambia de base
manteniendo esta propiedad hasta conseguir una solución dual-factible que sea, además, primal-factible.
Representando la evolución de las tablas del simplex asociadas a ambos algoritmos, se tiene la siguiente
situación:
≤ 0t
→ → ··· →
≥0 ≥0 ≥0
≤ 0t ≤ 0t ≤ 0t
→ → ··· →
≥0
Algoritmo dual
La idea anterior de que una solución dual-factible que sea factible es óptima, se recoge en el siguiente
teorema, cuya demostración es trivial.
El caso contrario, es decir, cuando la solución dual-factible no sea factible, se recoge en los dos teoremas
siguientes.
I − = {s ∈ I / x̄s < 0} 6= ∅
Demostración
Recordando que βi , con i ∈ {1, . . . , m}, es el vector (columna) cuyos elementos identifican la fila
i-ésima de la matriz B −1 , se verifica que:
ū′ = ū − θβl
bt ū′ = bt ū − θx̄l
156 7.2. Fundamentos teóricos del algoritmo dual
Hay que analizar en qué condiciones el vector ū′ es solución de D. Para ello hay que exigir que
1. j ∈ J:
2. s ∈ I − {l}:
3. s = l:
Las dos últimas desigualdades son ciertas al considerar que cualquier solución básica verifica
zs = c s ∀s ∈ I
El único problema puede surgir en el primer grupo de desigualdades. Hay que considerar entonces que
al ser la solución básica asociada a B dual factible, se verifica
ūt aj = zj ≤ cj ∀j ∈ J
Por tanto, ū′ es solución del problema dual D para cualquier valor de θ y, por consiguiente, el problema
D tiene solución no acotada.
Por la proposición 6.3, el problema P no tiene solución factible.
I − 6= ∅
B ′ = B ∪ {ak } − {al }
t
que proporciona una nueva solución dual-factible x̄′ tal que la solución ū′ = ctB ′ B ′−1 del problema D es
mejor o igual que la anterior al verificar bt ū′ ≥ bt ū.
J. Yáñez; J. Tejada 157
Demostración
Con la notación introducida en el teorema 7.2, y considerando la solución dual
ū′ = ū − θβl
Sea l ∈ I − elegido arbitrariamente; al existir, por hipótesis, un j l ∈ J tal que ylj l < 0, con el fin de
conseguir que ū′ sea solución de D, y a diferencia del teorema 7.2, el parámetro θ no puede superar un
determinado valor lı́mite θ0 , que se determina por:
( )
zk − c k zj − c j
θ0 = = mı́n
ylk j / ylj <0 ylj
Si θ = θ0 se anula el coste reducido del vector ak en la nueva solución ū′ . Realmente, la solución ū′
del problema D está asociada a la base B ′ = B ∪ {ak } − {al }:
Por medio de la forma producto de la inversa, que se verá en la sección 8.1.1, se obtiene:
−y1k /ylk
..
.
B ′−1 = Jlk B −1 Jlk = (e1 , . . . , vlk , . . . , em ) vlk =
1/ylk
.
..
−ymk /ylk
se obtiene
β1t
.
.
.
X
ctB ′ B ′−1 = ctB ′ Jlk B −1 = cB ′ (e1 , . . . , vlk , . . . , em )
t
β t = ct (
l B ′ es βst + vlk βlt )
. s6=l
..
t
βm
El término del paréntesis es la suma de m matrices cuadradas de dimensión m × m; concretamente:
0 0 ... 0 0t
. . ..
. . .
. . . ..
es βst =
1 (β1,s , . . . , βm,s ) = β1,s . . . βm,s = βs
t
. . ..
.. .. . ...
0 0 ... 0 0t
−y1k −y1k −y1k
β1,l . . . βm,l
ylk ylk ylk
.. .. ..
. . .
1 β1,l βm,l
vlk βlt = (β1,l , . . . , βm,l ) = ...
ylk ylk ylk
. . ..
.. .. .
−ymk −ymk −ymk
β1,l . . . βm,l
ylk ylk ylk
158 7.2. Fundamentos teóricos del algoritmo dual
X X −ysk ck X X −ysk ck
cs βst + cs βlt + βlt = cs βst − cl βlt + cs βlt + βlt =
s6=l s6=k
ylk ylk s∈I s6=k
ylk ylk
P
X −ysk ck cs ysk − ck
s∈I
= ctB B −1 + cs βlt + βlt = ctB B −1 − βlt =
s∈I
ylk ylk ylk
ctB yk − ck zk − c k t
= ctB B −1 − βlt = ctB B −1 − βlt = ū′
ylk ylk
del que se conoce una base B = {a1 , a2 , ah3 } que proporciona una solución dual-factible.
La tabla del simplex asociada a esta base es:
−3 2 0 −1/5 2/5 0
B= 1 1 0 B −1 = 1/5 3/5 0
−1 1 −1 2/5 1/5 −1
M ax 6u1 −4u2 +u3
−3u1 +u2 −u3 ≤7
2u1 +u2 +u3 ≤1
D
u1 ≤0
−u2 ≤0
−u3 ≤0
4. Se comprueba que ∃j ∈ J / ylj < 0, concretamente y1h 1 = −1/5 < 0 e y2h 1 = −2/5 < 0.
5. Se evalúa ( ) ( )
zj − c j −6/5 −17/5
mı́n = mı́n ; =6
j/ylj <0 ylj −1/5 −2/5
6. Cualquier valor de θ ∈ [0, 6] consigue una solución del problema dual D mejor que la anterior. Con
el fin de maximizar esta mejora, se elige θ = 6, de forma que la nueva solución de D es:
y esta nueva solución es mejor que la anterior, puesto que la función objetivo ha aumentado al
pasar de −104/5 a −4.
7. Esta nueva solución es la asociada a la base B ′ = {ah1 , a2 , ah3 } al cambiar a1 por ah1 :
1 2 0 1 −2 0
B′ = 0 1 0 B ′−1 = 0 1 0
0 1 −1 0 1 −1
de forma que
1 −2 0
ū′ = ctB ′ B ′−1 = (0, 1, 0) 0 1 0 = (0, 1, 0)
0 1 −1
base B, ahora se hace negativo. Esta asignación al parámetro θ es equivalente a pivotar en ylk de forma
que la nueva base será
B ′ = B ∪ {ak } − {al }
En efecto, sea la tabla del simplex asociada a B, donde por comodidad de notación se ha supuesto
que B = (a1 , . . . , am ):
Al asignar ( )
zk − c k zj − c j zk − c k
θ= = mı́n =
ylk j/ylj <0 ylj ylk
se anula el valor
ū′t ak − ck = zk′ − ck
Esta operación se ha conseguido multiplicando la fila l-ésima por θ y restando el vector ası́ obtenido
a la primera fila de la tabla.
Si zj′ − cj son los nuevos valores de la primera fila (asociados a la solución del dual ū′ ), se tiene:
1. j ∈ J − {k}:
zj′ − cj = ū′t aj − cj = ūt aj − cj − θylj = zj − cj − θylj ≤ 0
Esta última desigualdad es cierta para los valores ylj ≥ 0 y se fuerza para los valores ylj < 0 al
elegir el valor de θ.
2. j = k:
zk′ − ck = ū′t ak − ck = ūt ak − ck − θylk = zk − ck − (zk − ck ) = 0
3. s ∈ I − {l}:
zs′ − cs = ū′t as − cs = ūt as − cs − θyls = zs − cs − 0 = 0
4. s = l:
zl′ − cl = ū′t al − cl = ūt al − cl − θyll = zl − cl − θ < 0
La elección del elemento ylk < 0 como pivote sólo garantiza que la nueva solución tendrá un valor
asignado a la variable que entra positivo. En efecto,
x̄l
xk = x̄′k = >0
ylk
J. Yáñez; J. Tejada 161
Lo que no se garantiza es que el resto de las componentes de la nueva solución básica sean positivas,
es más, alguna positiva puede convertirse en negativa. Lo que es más importante y caracterı́stico del
algoritmo dual es que en cada cambio de base se mantiene la dual-factibilidad de la solución asociada a
la base, es decir, zj − cj ≤ 0 ∀j ∈ J.
Volviendo al ejemplo 7.2, si se elige como componente negativa x̄1 = −14/5, el valor θ = 6 obtenido
identifica como ı́ndice k = 1h . La nueva base es, por consiguiente,
Hay que observar que en esta tabla hay una variable, xh3 , que antes era positiva y ahora es negativa.
La elección del pivote ylk debe garantizar que la nueva solución básica sea dual-factible, por lo que el
criterio de entrada es crı́tico. Sin embargo, en todo el proceso se ha fijado previamente el vector al como
vector que sale de la base; el único requisito para elegir el ı́ndice l ∈ I es que la variable x̄l < 0 por lo
que el criterio de salida que se suele elegir
no es crı́tico.
Este proceso de mejora es finito, puesto que si existe solución óptima de D, existe solución óptima de
P por el teorema de dualidad y la función objetivo está acotada. Otro caso serı́a cuando D tiene solución
no acotada, pero esta situación se detecta fácilmente, ya que ylj ≥ 0 ∀j ∈ J y se concluye el proceso al
no tener solución factible el problema P .
Al igual que el algoritmo del simplex requerı́a del conocimiento de una solución básica factible, el
algoritmo dual parte de una solución dual-factible. Posteriormente se estudiará bajo qué condiciones se
conoce una solución dual-factible.
Aplicando el algoritmo dual al ejemplo 7.1, hay que pivotar en el elemento y1h 1 = −2 para obtener la
tabla óptima:
2 3 1 0 0
x1 x2 x3 xh1 xh2
0 −2 −2 −1 0
2 x1 1 1/2 −1/2 −1/2 0 1
0 xh2 0 −1/2 −3/2 −1/2 1 0
El algoritmo dual se puede desarrollar también con la tabla del simplex. A diferencia de éste, el criterio
de entrada y salida determinan un elemento pivote que es negativo. Una vez elegido el pivote, el resto de
operaciones son las mismas que para el algoritmo del simplex.
Observación 7.2 En el caso en que el problema de programación lineal sea de maximización, el criterio
de salida no varı́a y el de entrada habrı́a que sustituirlo por
Entra ak tal que ( )
zk − c k −(zj − cj )
= mı́n
ylk j∈J,ylj <0 ylj
Una alternativa para considerar conjuntamente los dos casos serı́a incluir como criterio de entrada
Entra ak tal que ( )
zk − c k −|zj − cj |
= mı́n
ylk j∈J,ylj <0 ylj
J. Yáñez; J. Tejada 163
x2
S
✾
■
x1
Aplicando el algoritmo dual al ejemplo 7.2 y considerando como solución dual-factible inicial la aso-
ciada a la base B = (a1 , a2 , ah3 ), se pivota —según se ha detallado anteriormente— en el elemento
y11h = −1/5 para obtener la tabla asociada a la base B ′ = (ah1 , a2 , ah3 ).
Pivotando en esta última tabla en el elemento y3h 2h = −1 se obtiene la tabla óptima:
siendo M una constante positiva arbitrariamente grande. Se define ası́ un nuevo problema P (M )
al añadir una restricción que debe ser redundante para la solución óptima —si existe— al ser el
parámetro M arbitrariamente grande.
164 7.4. Inicialización del algoritmo dual
X
xj + xhm+1 = M
j∈J
zk − ck = máx{zj − cj }
j∈J
4. Pivotar en el elemento ym+1h k para sacar de la base el vector unitario asociado a la variable de
holgura xhm+1 .
Se consigue ası́ una solución dual-factible, ya que todos los coeficientes ym+1h j = 1 ∀j ∈ J.
Solución óptima.
En este caso hay que distinguir dos posibilidades:
1 1 0 0
x1 x2 x3 x4
0 0 1 1 −3
1 x1 1 0 2 −1 −1
1 x2 0 1 −1 2 −2
Introduciendo la restricción
x3 + x4 ≤ M ⇐⇒ x3 + x4 + xh3 = M
1 1 0 0 0
x1 x2 x3 x4 xh3
0 0 1 1 0 −3
1 x1 1 0 2 −1 0 −1
1 x2 0 1 −1 2 0 −2
0 xh3 0 0 1 1 1 M
1 1 0 0 0
x1 x2 x3 x4 xh3
0 0 0 0 −1 −M − 3
1 x1 1 0 0 -3 −2 −2M − 1
1 x2 0 1 0 3 1 M −2
0 x3 0 0 1 1 1 M
que es una solución dual-factible. Iterando con el algoritmo dual se pivota en el elemento y14 :
1 1 0 0 0
x1 x2 x3 x4 xh3
0 0 0 0 −1 −M − 3
0 x4 −1/3 0 0 1 2/3 2M/3 + 1/3
1 x2 1 1 0 0 -1 −M − 3
0 x3 1/3 0 1 0 1/3 M/3 − 1/3
1 1 0 0 0
x1 x2 x3 x4 xh3
0 0 0 0 0 0
0 x4 1/3 2/3 0 1 0 −5/3
0 xh3 −1 −1 0 0 1 M +3
0 x3 −2/3 1/3 1 0 0 −4/3
y se concluye que no existe solución factible para el problema original al existir un x̄4 = −5/3 < 0 y
verificar y14 = 1/3 ≥ 0; y24 = 2/3 ≥ 0.
166 7.5. Análisis de sensibilidad de la solución óptima. Post-optimización
Para ilustrar las distintas modificaciones, se parte del ejemplo 5.4 ya resuelto y cuya tabla del simplex
óptima es:
1 −2 1 0 −
x1 x2 x3 xh2 xa1
−2 0 0 −1 − −1
1 x3 1 0 1 1/5 2/5 1
−2 x2 1 1 0 3/5 1/5 1
B −1 b′ ≥ 0
En este caso, la base B sigue siendo óptima para P ′ y la solución óptima es x̄′B = B −1 b′ , x̄′N = 0.
B −1 b′ 6≥ 0
La solución básica asociada a B es dual-factible y no primal-factible, por lo que hay que aplicar el
algoritmo dual para llegar al óptimo o comprobar que no existe solución factible para P ′ .
La tabla del simplex asociada al nuevo problema P ′ se construye a partir de la tabla óptima del
problema P sin más que sustituir el vector x̄B por el nuevo vector x̄′B = B −1 b′ . En este caso, la tabla
del simplex ası́ obtenida proporciona una solución dual-factible —la asociada a B— y el algoritmo dual
tratará que sea, además, primal-factible y conseguir ası́ la solución óptima.
1. bt = (1, 1)
La tabla obtenida al modificar la tabla óptima de P sustituyendo x̄B por el nuevo valor
J. Yáñez; J. Tejada 167
! ! !
−1 2/5 1/5 1 3/5
B b= =
1/5 3/5 1 4/5
es:
−1 2 1 0 −
x1 x2 x3 xh2 xa1
−2 0 0 −1 − −1
1 x3 1 0 1 1/5 2/5 3/5
−2 x2 1 1 0 3/5 1/5 4/5
que es también óptima, por lo que se mantiene la base óptima de P para el problema P ′ aunque la
solución ha variado.
2. bt = (1, −1)
La tabla obtenida al modificar la tabla óptima de P sustituyendo x̄B por el nuevo valor
! ! !
2/5 1/5 1 1/5
B −1 b = =
1/5 3/5 −1 −2/5
es:
−1 2 1 0 −
x1 x2 x3 xh2 xa1
−2 0 0 −1 − 1
1 x3 1 0 1 1/5 2/5 1/5
−2 x2 1 1 0 3/5 1/5 −2/5
que proporciona una solución dual-factible, por lo que se aplica el algoritmo dual y se obtiene que
no existe solución factible para el problema P ′ .
El análisis de sensibilidad de la solución óptima respecto del vector b se realiza de forma automática
a partir de los desarrollos anteriores: La base B asociada a la solución óptima seguirá siendo óptima
siempre que se verifique B −1 b ≥ 0.
A partir de este conjunto de desigualdades se identifican las condiciones que debe verificar el vector
b, fijando algunas o todas las componentes, para que la base siga siendo óptima.
La base óptima B = (a3 , a2 ) del problema P del ejemplo 5.4 se mantiene si se verifica:
! ! !
2/5 1/5 b1 0
≥
1/5 3/5 b2 0
o, lo que es lo mismo:
2b1 + b2 ≥ 0 b1 + 3b2 ≥ 0
Por ejemplo, con los valores actuales b1 = 2 y b2 = 1, las dos inecuaciones se verifican. Si se fija
b1 = 3, entonces la base actual se mantiene siempre que b2 ≥ −1.
168 7.5. Análisis de sensibilidad de la solución óptima. Post-optimización
Este tipo de modificación se justifica, además de por las razones vistas al principio del apartado, por la
conveniencia de resolver problemas más sencillos —con menos restricciones— y posteriormente añadirlas.
Cuando un problema de programación lineal se transforma eliminando algunas restricciones, se dice que
es un problema relajado.
Se distinguirá el caso de introducción de inecuaciones del caso en que se introducen ecuaciones.
Cuando se introduce una inecuación, el valor de la variable de holgura asociada indicará si la solución
óptima de P verifica dicha inecuación cuando dicha variable sea no negativa. En este caso, la solución
óptima de P es la solución óptima de P ′ . En caso contrario, hay que añadir una nueva fila —la inecuación
nueva— y una nueva columna —su variable de holgura— en la tabla óptima del simplex del problema P .
La nueva fila no se debe introducir directamente en la tabla del simplex. Con el fin de mantener
la submatriz identidad de tamaño (m + 1) × (m + 1) que identifica la base, cada restricción donde se
encuentra el 1 del vector unitario ei , con i ∈ {1, . . . , m}, se multiplica por el correspondiente término
−am+1,i y se suma a la nueva restricción. De esta forma se consigue anular todos los coeficientes de la
nueva restricción asociados a columnas que están en la base. El vector unitario em+1 se consigue en la
columna asociada a la nueva variable de holgura.
La primera fila no varı́a al ser la nueva variable básica una de holgura y tener coste nulo. La tabla
del simplex ampliada en una fila y columna mantiene la dual-factibilidad de la base B ampliada con la
variable de holgura ahm+1 , por lo que el algoritmo dual se puede aplicar directamente en este caso.
El análisis anterior es independiente de que la inecuación sea del tipo ≤ o ≥. En cualquier caso hay
que conseguir un vector unitario en la columna m + 1-ésima.
Introduciendo la inecuación
en el problema P del ejemplo 5.4, se obtiene la siguiente representación del sistema de ecuaciones al
incluir la variable de holgura xh3 asociada a la nueva restricción:
1 −2 1 0 0 −
x1 x2 x3 xh2 xh3 xa1
1 x3 1 0 1 1/5 0 2/5 1
−2 x2 1 1 0 3/5 0 1/5 1
2 3 4 0 1 0 9
Esta representación del sistema de ecuaciones no es una tabla del simplex al no identificar la base por
una submatriz identidad. Para construir la tabla del simplex asociada al ampliar la base óptima de P con
la variable de holgura xh3 , hay que conseguir una submatriz identidad, por lo que se multiplica la primera
fila por −4 y la segunda por −3 para sumarlas a la tercera fila y se obtiene ası́ la siguiente tabla:
J. Yáñez; J. Tejada 169
1 −2 1 0 0 −
x1 x2 x3 xh2 xh3 xa1
−2 0 0 −1 0 − −1
1 x3 1 0 1 1/5 0 2/5 1
−2 x2 1 1 0 3/5 0 1/5 1
0 xh3 −5 0 0 −13/5 1 −11/5 2
Se obtiene ası́ una solución dual-factible y, además, factible. Se ha alcanzado ası́ la solución óptima.
Hay que observar que la inecuación añadida era verificada por la solución óptima de P , por lo que la
variable de holgura asociada ha tomado un valor no negativo.
3x1 + x2 + x3 ≥ 4
−3x1 − x2 − x3 + xh3 = −4
1 −2 1 0 0 −
x1 x2 x3 xh2 xh3 xa1
1 x3 1 0 1 1/5 0 2/5 1
−2 x2 1 1 0 3/5 0 1/5 1
−3 −1 −1 0 1 0 −4
Multiplicando la primera y segunda filas por 1 para sumarlas a la tercera, se obtiene la tabla del
simplex:
1 −2 1 0 0 −
x1 x2 x3 xh2 xh3 xa1
−2 0 0 −1 0 − −1
1 x3 1 0 1 1/5 0 2/5 1
−2 x2 1 1 0 3/5 0 1/5 1
0 xh3 -1 0 0 4/5 1 3/5 −2
que proporciona una solución dual-factible pero no factible, ya que xh3 = −2 < 0. Al aplicar el algoritmo
dual, se obtiene la tabla siguiente:
1 −2 1 0 0 −
x1 x2 x3 xh2 xh3 xa1
0 0 0 −13/5 −2 − 3
1 x3 0 0 1 1 1 1 −1
−2 x2 0 1 0 7/5 1 4/5 −1
1 x1 1 0 0 −4/5 −1 −3/5 2
Cuando se introduce una ecuación, como no lleva asociada una variable de holgura, no se puede repetir
el análisis introducido previamente. Sin embargo, considerando que una ecuación es la intersección de
dos inecuaciones de sentido inverso y se verifica sólo si las dos variables de holgura asociadas a ambas
se anulan, se puede aprovechar el algoritmo dual para sacar de la base aquélla de las dos variables de
holgura que tome un valor negativo. Si las dos variables fueran nulas, querrı́a decir que la solución óptima
de P verifica la nueva ecuación y, por consiguiente, serı́a también la solución óptima de P ′ .
Sea
la ecuación que se añade. La forma de proceder en este caso es la siguiente: como no se sabe cuál de las
dos inecuaciones es la que no se verifica, se introduce la variable artificial xam+1 :
y se hacen las transformaciones detalladas anteriormente para conseguir que la tabla ampliada tenga
m + 1 vectores unitarios.
Una vez conseguido esto, se elige el signo de la variable xam+1 de forma que el valor x̄am+1 < 0 y forzar
ası́ su salida de la base por el algoritmo dual. La elección del signo es equivalente a la elección de la
inecuación que no se verifica.
Es preciso observar que xam+1 es una variable artificial y cuando salga de la base por el algoritmo dual
debe eliminarse la columna asociada y continuar con el algoritmo dual hasta conseguir la solución óptima
de P ′ o bien detectar la no existencia de solución factible para P ′ .
Introduciendo la ecuación
2x1 + x2 + 3x3 = 2
en el problema P del ejemplo 5.4, se obtiene la siguiente representación del sistema de ecuaciones al
incluir la variable artificial xa3 con coste cero:
1 −2 1 0 0 −
x1 x2 x3 xh2 xa3 xa1
1 x3 1 0 1 1/5 0 2/5 1
−2 x2 1 1 0 3/5 0 1/5 1
2 1 3 0 ±1 0 2
El signo ± que acompaña a la variable artificial se ha introducido para luego elegir el signo que
proporcione un valor negativo. Se conseguirá ası́ forzar la salida de la variable (artificial) de la base para
excluirla posteriormente de los cálculos y recuperando ası́ la ecuación original. El coste nulo se introduce
para garantizar la dual factibilidad de la nueva solución básica obtenida al transformar esta representación
del sistema de ecuaciones en una tabla del simplex:
J. Yáñez; J. Tejada 171
1 −2 1 0 0 −
x1 x2 x3 xh2 xa3 xa1
−2 0 0 −1 0 − −1
1 x3 1 0 1 1/5 0 2/5 1
−2 x2 1 1 0 3/5 0 1/5 1
0 xa3 −2 0 0 -6/5 ±1 −7/5 −2
En este caso, se elige el signo + para que xa3 = −2 < 0 y se aplica el algoritmo dual para obtener la
tabla óptima:
1 −2 1 0 − −
x1 x2 x3 xh2 xa3 xa1
−1/3 0 0 0 − − 2/3
1 x3 2/3 0 1 0 − − 2/3
−2 x2 0 1 0 0 − − 0
0 xh2 5/3 0 0 1 − − 5/3
De forma análoga al problema de parametrización del vector de costes, se parte del valor inicial µ = 0,
se resuelve el problema y se determina para qué valores del parámetro se mantiene la optimalidad de la
solución.
El problema paramétrico ya está resuelto para valores del parámetro inferiores a dicho valor crı́tico.
Para valores superiores del parámetro, la optimalidad de la solución no se asegura. La dual-factibilidad
está siempre asegurada, por lo que hay que aplicar el algoritmo dual.
172 7.6. Ejercicios propuestos
M in 3x + 4y + 5z
s.a. x + 2y + 3z ≥ 5
2x + 2y + 3z ≥ 6
x, y, z ≥ 0
M ax 2x1 − 3x2
s.a. x1 + x2 ≤ 3
3x1 + x2 ≤ 6
x1 , x2 ≥ 0
Se pide:
3. Dado el problema:
M in ct x
Ax =b
x ≥0
x1 x2 x3 x4 x5 x6
0 0 0 B −3 −2
1 0 0 −3 −1 D C
0 1 0 −7 −1 2 5
0 0 1 A 0 3 4
Se pide:
Determinar los valores de A, B, C y D de forma que la tabla anterior identifique las siguientes
situaciones:
• Solución óptima.
• Solución no acotada.
• Solución dual-factible y no factible.
• Solución dual-factible y no factible y asegurando, además, que no existe solución factible
para el problema.
Asignar los valores A = 4, B = −2, C = −1 y D = −3 y llegar a la solución óptima.
M in x1 − 3x2 − x3
x1 + 4x2 + 3x3 = 12
P
x1 + 2x2 − x3 = 4
xj ≥ 0 j = 1, 2, 3
resolver los siguientes problemas de postoptimización:
x1 + x2 + x3 = 4
Implementación y mejoras
computacionales
B ′ = {a1 , . . . , ak , . . . , am }
Pm
Considerando que ak = s=1 ysk as o, en forma matricial, ak = Byk , para que B ′ sea una base, es
condición necesaria y suficiente que ylk 6= 0 de tal forma que
1 X 1
al = − ysk as + ak
ylk s6=l
ylk
175
176 8.1. Forma revisada del algoritmo del simplex
La inversa de B ′ se obtiene fácilmente a partir de la inversa de B sin más que ampliar lo deducido
anteriormente:
Para ilustrar la determinación de la inversa de una base como producto de la matriz Jlk por la inversa
de la base anterior, considérese el ejemplo 4.2, al que se le ha aplicado el método de las dos fases en la
sección 4.2:
Para la base B = {a1 , a3 , aa3 } se tiene la inversa
2/3 −1/3 0
B −1 = 1/3 1/3 0
−7/3 −1/3 1
Al pivotar en el elemento y3a 5 = 3, se define la matriz
1 0 1/3
J 3a 5 = 0 1 0
0 0 1/3
De forma que la inversa de la nueva base B ′ = {a1 , a3 , a5 } es
1 0 1/3 2/3 −1/3 0 −1/9 −4/9 1/3
B ′−1 = J3a 5 B −1 = 0 1 0 1/3 1/3 0 = 1/3 1/3 0
0 0 1/3 −7/3 −1/3 1 −7/9 −1/9 1/3
A continuación se demuestra que la actualización de las tablas del simplex en cada cambio de base se
puede realizar a través de un producto matricial.
" # " # !
b= 1 −ct b= 1 −ctB b= 0
A B b
0 A 0 B b
Considerando la fórmula de la inversa de matrices por cajas:
" # " #
b = M R b −1 = (M − RN −1 L)−1 −(M − RN −1 L)−1 RN −1
H H
L N −N −1 L(M − RN −1 L)−1 N −1 + N −1 L(M − RN −1 L)−1 RN −1
se concluye que
" #
b −1 1 ctB B −1
B =
0 B −1
y la tabla del simplex se puede reproducir como un producto de matrices:
" #
−1 1 (z1 − c1 ) ... (zn − cn ) z̄
B̂ (Â, b̂) =
0 y1 ... yn x̄B
De esta forma, conociendo B̂ −1 se puede recuperar cualquier cantidad de interés por medio de un
producto matricial.
El método revisado aprovecha esta propiedad para realizar sólo aquellos cálculos que sean necesarios
evitando el resto. Por ejemplo, los vectores yj sólo serán evaluados para el vector ak que vaya a entrar
en la base. En problemas de gran tamaño esto supone un ahorro computacional considerable.
1 −M −M −M 1 M M M
0
b= 0
B
1 0 0 d
B −1 =
1 0 0
0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1
Evaluando la primera fila y las columnas de la solución y la del vector que maximiza zj − cj , se
obtiene:
2M − 1 −2 6M + 1 3M + 2 M −2 M −3 0 0 0 8M
1 2
2 1
3 5
178 8.1. Forma revisada del algoritmo del simplex
Observación 8.1 Se muestran los resultados necesarios con el formato de la tabla del simplex para
resaltar las diferencias computacionales con ésta. Sólo se han calculado los números que aparecen.
Realmente, los cálculos a realizar para cada base son los siguientes:
b
de A.
Si yk ≤ 0, entonces se tiene solución no acotada y se termina. En caso contrario, hay que
pivotar y actualizar la inversa de la base por la forma producto de la inversa.
2. B ′ = {aa1 , a3 , aa3 }
Se calcula la matriz
1 −1/2 0
J2a 3 = 0 1/2 0
0 −3/2 1
1 −1/2 0 1 0 0 1 −1/2 0
B ′−1 = J2a 3 B −1 = 0 1/2 0 0 1 0 = 0 1/2 0
0 −3/2 1 0 0 1 0 −3/2 1
3. B ′′ = {a1 , a3 , aa3 }
Se procede de forma análoga hasta llegar a la base óptima
4. B ∗ = {a4 , a3 , a5 }
La inversa ampliada es
1 −8/5 3/5 −1/5
0 −1/5 −4/5 3/5
Bd
∗ −1 =
0
2/5 3/5 −1/5
0 −4/5 −1/5 2/5
Al evaluar la primera fila de la tabla del simplex, al ser todos los elementos menores o iguales que
cero, sólo hay que calcular la última columna, que identifica la solución óptima.
a)
M in 2x1 −3x2 −x3 +2x4
Sujeto a x1 +x2 ≤5
2x3 −3x4 ≤4
xj ≥0 ∀j = 1, . . . , 4
b)
M in −2x1 −3x2 −2x3 −4x4
Sujeto a x1 +x2 +x3 +x4 ≤1
−x1 +x2 ≤2
2x1 +3x2 ≤1
3x3 +4x4 ≤1
xj ≥ 0 ∀j = 1, . . . , 4
c)
M in 2x1 +3x2 +x3 +2x4
Sujeto a x1 +x2 +x3 +x4 ≥1
−x1 +x2 ≥1
2x1 +3x2 ≥1
3x3 +4x4 ≥1
xj ≥0 ∀j = 1, . . . , 4
5. Sea el problema de transporte definido con dos orı́genes y tres destinos, siendo los vectores de oferta
y demanda o y d y con la matriz de costes C detallados a continuación:
! 50 !
100 1 2 1
o= d = 150 C=
300 3 1 2
200
Se pide:
6. Una empresa que fabrica marcos para ventanas de aluminio recibe el encargo de un promotor de
viviendas que consiste en 10 barras de 2 metros, 15 de 3 y 8 de 4. El problema consiste en determinar
el menor número de barras, que tienen un tamaño fijo de 7 metros, que necesita para satisfacer la
demanda.
Este problema se conoce en la literatura como cutting stock problem y es un buen ejemplo de
aplicación del método de generación de columnas desarrollado en este capı́tulo. A continuación se
dan las ideas básicas para resolver el problema en general.
Sea L el tamaño de la barra y m el número de tamaños distintos solicitados. Los vectores (d1 , d2 , . . . , dm )
y (b1 , b2 , . . . , bm ) identifican respectivamente los tamaños y cantidades solicitadas. En el problema
planteado, L = 7, m = 3, (d1 , d2 , d3 ) = (2, 3, 4) y (b1 , b2 , b3 ) = (10, 15, 8).
El problema se puede plantear como la búsqueda de n patrones de corte de las barras. El patrón
j-ésimo, siendo j ∈ {1, . . . , n} viene identificado por el vector aj ∈ IRm de forma que ai,j es el
número de cortes de dimensión di , para todo i ∈ {1, . . . , m} y que debe verificar
m
X
ai,j di ≤ L ∀j ∈ {1, . . . , n}
i=1
se resuelve el problema anterior relajado continuamente y con estos m patrones en lugar de los n.
A partir de la solución óptima anterior, se busca si existe otro patrón que la mejore. Dicho patrón aj
P
deberá verificar la restricción i ai,j di ≤ L y se buscará el mejor candidato a la tabla del simplex
obtenida con la solución inicial, es decir, debe
máx zj − cj
j