Programación Lineal
Programación Lineal
P ROGRAMACI ÓN
L INEAL
Mayo 2021
Programación Lineal
Copyright
c 2011–2020 Alvaro Garcı́a Sánchez y Miguel Ortega Mier
TEX, LATEX, and AMS-LATEX son marcas registradas de la American Mathematical Society. Lucida es una
marca registrada por Bigelow & Holmes Inc. Acrobat es marca registrada por Adobe Systems Inc.
La información de este documento está sujeta a cambio sin ningún aviso y no representa una obligación
por parte de los autores.
Los autores no garantizan la idoneidad de este documento o de los programas descritos en él para ningún
propósito en particular o su idoneidad para obtener ningún resultado en particular. En ningún caso los au-
tores serán responsables de los daños, pérdidas, costes, cargos, reclamaciones, demandas o reclamaciones
por perjuicios, honoarios o gastos de ninguna naturaleza, ya sean directos, indirectos, de carácter especial
o derivados del uso del mismo.
Además de lo anterior, los lectores deben saber que cualquier documentación contiene errores y/o omi-
siones. Los autores no tienen el compromiso bajo ninguna circunstancia de proporcionar información o
correcciones a los errores y omisiones de este documento, tanto si son conocedores de dichos errores y
omisiones como si no.
Los autores quieren agradecer el trabajo de Irene Gómez Sánchez por la colaboración para la mejora del
contenido y maquetación de este documento.
También quieren agradecer a tantos alumnos que en estos años han ido indicando a los autores erratas
detectadas; de entre todos ellos destacar el trabajo intenso de revisión de Marta Navarro Alberti, Marta
Mañá Sánchez, Cristina Conde González de Uriarte y Eduardo López González.
Para informar de erratas o conceptos que no han quedado bien explicados, por favor, escribid a mi-
guel.ortega.mier@upm.es
Índice general
4. INTERPRETACIÓN TÉCNICO-ECONÓMICA 43
4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.1. Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . 44
4.2. Tasas de sustitución . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1. Discusión teórica . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.2. Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . 47
4.3. Multiplicadores del Simplex . . . . . . . . . . . . . . . . . . . . . 47
4.3.1. Discusión teórica . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.2. Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . 49
4.3.3. Precio sombra de las restricciones de tipo “=” . . . . . 50
4.4. Criterios del Simplex . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.1. Discusión teórica . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.2. Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . 54
6. POSTOPTIMIZACIÓN 65
6.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2. Cambio en b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.3. Cambio en c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.4. Nueva actividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.5. Nueva restricción . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.6. Cambio en aij . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.6.1. Cambio en aij con xj no básica . . . . . . . . . . . . . 68
6.6.2. Cambio en aij con xj básica . . . . . . . . . . . . . . . 69
6.7. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.7.1. Cambio de b . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.7.2. Cambio de c . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.7.3. Nueva actividad . . . . . . . . . . . . . . . . . . . . . . . 72
6.7.4. Nueva restricción . . . . . . . . . . . . . . . . . . . . . . 72
Índice general v
7. ANÁLISIS DE SENSIBILIDAD 74
7.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.2. Análisis de b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3. Análisis de c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.4. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4.1. Análisis de cx2 . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4.2. Análisis de cx3 . . . . . . . . . . . . . . . . . . . . . . . . 78
7.4.3. Análisis de b2 . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.5. La aparente paradoja de b . . . . . . . . . . . . . . . . . . . . . . 79
8. CASOS ESPECIALES 81
8.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.2. Óptimo múltiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.3. Solución degenerada . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.4. Problema no factible . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.5. Región de factibilidad no acotada . . . . . . . . . . . . . . . . . 88
9. INTERPRETACIÓN GRÁFICA 91
9.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.2. Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.3. Método del Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . 98
INTRODUCCIÓN A LA PROGRAMACIÓN
LINEAL. TEOREMA FUNDAMENTAL
1.1. Introducción
n
1 c
n 1 1
m A n x m b
Un conjunto de valores x es una solución factible del problema si cumple el Solución factible
sistema de ecuaciones Ax = b (es solución) y cumple que x ≥ 0, es decir todos
los valores son no negativos.
1.2.1. Enunciado
1.2.2. Demostración
1 Esto es ası́ siempre cuando el rango de todas las matrices de m columnas de A es m. Si exis-
tiera una submatriz dentro de A con menos de m columnas linealmente dependientes, podrı́a
existir una solución linealmente dependiente con menos de m componentes.
Capı́tulo 1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL. TEOREMA FUNDAMENTAL 4
Ay = 0 y
yi = 0 si xi = 0
cy ≥ 0 (si no es ası́, basta con cambiar de signo a y).
Efectivamente, es solución:
x 1 no es peor
z1 = cx 1 = c(x 0 + ty) = cx 0 + tcy = z0 + tcy (1.5) que x 0
Se puede dar un valor a t de manera que ninguna variable tenga valor negativo x 1 no es peor
y que tenga una componente nula más que x 0 . que x 0
xi0
t = min{i/yi ≤0}
yi (1.7)
Examinando de forma exhaustiva los casos que se pueden dar, la discusión Discusión
completa es la siguiente. completa
Si cy > 0
x1
• Si ∃yi < 0, con t = min{i/yi ≤0}i
se obtiene una solución no peor
|yi |
con una componente nula más.
• Si yi > 0 ∀i el problema no está acotado, el valor de la función
objetivo pude ser tan grande como se desee.
De acuerdo con lo que se sigue del teorema fundamental, siempre existe una Dónde buscar
solución óptima dentro del conjunto de todas las soluciones linealmente inde-
pendientes.
Si el problema crece, suponiendo que cada sistema se resuelve en 10−6 segun- Ejemplo
dos, se pueden tener tiempos de resolución de años: numérico
Sol.
Solución
Nº lineal. Restricción 1 Restricción 2 z
(x1 , x2 , x3 , x4 , x5 , x6 )
indep.
Sol.
Solución
Nº lineal. Restricción 1 Restricción 2 z
(x1 , x2 , x3 , x4 , x5 , x6 )
indep.
En la tabla 1.2 se observa que existen dos soluciones cuyo valor z es mayor que
para el resto de soluciones linealmente independientes. Estas dos soluciones
son las soluciones óptimas; casualmente, en este caso hay soluciones óptimas
múltiples. Además, existe un conjunto de soluciones no factibles, cuyo valor
de z no es relevante, dado que no cumplen las restricciones de dominio.
T
La solución 6,37 7,58 13,53 3,42 4,21 es una solución porque Solución inicial:
cumple Ax = b. Efectivamente, se puede comprobar que:
⎛ ⎞
6,37
⎛ ⎞⎜ ⎟ ⎛ ⎞
−3 1 1 0 0 ⎜ 7,58 ⎟ 2
⎜ ⎟⎜ ⎟ ⎜
⎟ = ⎝ 11 ⎟
Ax 0 = ⎝ 0 1 0 1 0 ⎠⎜
⎜ 13,53 ⎟ ⎠ (1.11)
⎜ ⎟
1 −1 0 0 1 ⎝ 3,42 ⎠ 3
4,21
T
Un posible vector y es 12 4 32 −4 −8 , aunque hay infinitos posi- Primera
1 iteración
bles. Con este vector y es posible construir una nueva solución x :
⎞⎛ ⎛ ⎞ La nueva
6,37 12
⎜ ⎟ ⎜ ⎟ solución
⎜ 7,58 ⎟ ⎜ 4 ⎟
⎜ ⎟ ⎜ ⎟
x 1 = x 0 + ty = ⎜ ⎟ ⎜
⎜ 13,53 ⎟ + t ⎜ 32
⎟
⎟ (1.13)
⎜ ⎟ ⎜ ⎟
⎝ 3,42 ⎠ ⎝ −4 ⎠
4,21 −8
Capı́tulo 1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL. TEOREMA FUNDAMENTAL 9
De no ser ası́, bastarı́a con cambiar el signo a y, de forma que todo lo anterior x 1 no peor que
serı́a cierto. x0
cx 1 = c(x 0 + tcy) =
⎛ ⎞ ⎛ ⎞
6,37 12
⎜ ⎟ ⎜ ⎟
⎜ 7,58 ⎟
⎜
⎟ ⎜⎜
4 ⎟
⎟
1 2 0 0 0 ⎜ ⎟
⎜ 13,53 ⎟ + t 1 2 0 0 0 ⎜ ⎟
⎜ 32 ⎟ = (1.16)
⎜ ⎟ ⎜ ⎟
⎝ 3,42 ⎠ ⎝ −4 ⎠
4,21 −8
21,53 + t × 20
Capı́tulo 1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL. TEOREMA FUNDAMENTAL 10
Dado que sólo y4 e y5 son negativas, sólo es posible que las componentes x4
y x5 se hagan nulas con t > 0. En particular, los valores que hacen respectiva-
mente 0 cada una de esas componentes de x 1 son 3,42 4,21
4 y 8 .
En menor valor de los anteriores hace que una componente, x5 , se haga nula y
no se haga negativa ninguna de las otras dos.
3,42 4,21
t = min , = 0,52625 (1.17)
4 8
z1 = 32,07
T
x 1 = 12,69 9,69 30,37 1,32 0 Segunda
T iteración
y = 1 1 2 −1 0
Ay = 0
t = min 1,32
1 = 1,32
T
x 2 = 14 11 33 0 0
z2 = 36
z= z=
x2 32 36
,07
13
12
8
=2
x0
2
+x
7
1
−3x
6 3
5
=
2
x
−
1
x
(0,2)
2
x1 = 0
(0, 0) x2 = 0 (3, 0)
1 4 5 7 11 14 15 x1
z 2= 3 6 8 9 10 12 13
0
En el gráfico, además, hay cuatro rectas representadas: x1 +2x2 = 0, x1 +2x2 = Función objetivo
21,53, x1 + 2x2 = 32,07 y x1 + 2x2 = 36. Cada una de estas rectas (se podrı́an
representar otras), contiene al conjunto de puntos que tienen la misma función
objetivo (0 , 21,53 , 32,07 y 36, según el caso).
En este ejemplo, las soluciones linealmente independientes tienen como máxi- Soluciones
mo tres (m) componentes no nulas y, por lo tanto, al menos 3 (n − m = 6 − 3) linealmente
independientes
Capı́tulo 1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL. TEOREMA FUNDAMENTAL 12
nulas.
Una variable nula significa una de las dos siguientes cosas:
Es decir, si hay tres componentes nulas debe estar la intersección de tres res-
tricciones o ejes. Las soluciones linealmente independientes factibles son los
vértices del poliedro.
Soluciones linealmente dependientes son el resto, es decir, las que están sobre Soluciones
los lados (no en los vértices) o en el interior del poliedro. linealmente
dependientes
La interpretación gráfica del Teorema Fundamental en dos dimensiones es la Significado de
siguiente: dado un punto en el interior o en el lado del polı́gono que define la las iteraciones
región de factibilidad, siempre es posible moverse hasta un vértice que tiene
una mayor función objetivo, no necesariamente el óptimo del problema pero
sı́ al menos tan buena como la solución de partida.
⎛ ⎞
0
⎜ ⎟
⎜ 4 ⎟
⎛ ⎞⎜ ⎟ ⎛ ⎞
2 3 3 6 1 0 0 ⎜⎜ 14 ⎟
⎟ 400
0 ⎜ ⎟⎜ ⎟ ⎜ ⎟
Ax = ⎝ 1 2 6 3 0 1 0 ⎠⎜ 36 ⎟ = ⎝ 200 ⎠ (1.20)
⎜ ⎟
5 5 5 5 0 0 1 ⎜⎜ 130 ⎟
⎟ 10000
⎜ ⎟
⎝ 0 ⎠
9730
O lo que es equivalente:
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
2 3 3 6 1 0 0
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
0 ⎝ 1 ⎠ + y2 ⎝ 2 ⎠ + y3 ⎝ 6 ⎠ + y4 ⎝ 3 ⎠ + y5 ⎝ 0 ⎠ + 0 ⎝ 1 ⎠ + y7 ⎝ 0 ⎠ =
5 5 5 5 0 0 1
⎛ ⎞
0
⎜ ⎟
=⎝ 0 ⎠
0
(1.22)
⎛ ⎞ ⎛ ⎞ La nueva
0 0
⎜ ⎟ ⎜ ⎟ solución
⎜ 4 ⎟ ⎜ 0,1 ⎟
⎜ ⎟ ⎜ ⎟
⎜ 14 ⎟ ⎜ −0,567 ⎟
⎜ ⎟ ⎜ ⎟
1 0 ⎜ ⎟ ⎜ ⎟
x = x + ty = ⎜ 36 ⎟+t⎜ 1,067 ⎟ (1.23)
⎜ ⎟ ⎜ ⎟
⎜ 130 ⎟ ⎜ −5 ⎟
⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎝ 0 ⎠ ⎝ 0 ⎠
9730 −3
Capı́tulo 1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL. TEOREMA FUNDAMENTAL 14
De no ser ası́, bastarı́a con cambiar el signo a y y todo lo anterior serı́a cierto. x 1 no peor que
Dado que cy > 0, el valor de la función de objetivo de x 1 es mayor que la de x0
x 0 en una cantidad igual a tcy.
cx 1 = c(x 0 + tcy) =
⎛ ⎞ ⎛ ⎞
0 0
⎜ ⎟ ⎜ ⎟
⎜ 4 ⎟ ⎜ 0,1 ⎟
⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ −0,567 ⎟
⎜ 14 ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
4 4 6 8 0 0 0 ⎜ 36 ⎟ + t 4 4 6 8 0 0 0 ⎜ 1,067 ⎟ =
⎜ ⎟ ⎜ ⎟
⎜ 130 ⎟ ⎜ −5 ⎟
⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎝ 0 ⎠ ⎝ 0 ⎠
9730 −3
388 + 24,56 × 5,534
(1.26)
Capı́tulo 1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL. TEOREMA FUNDAMENTAL 15
Dado que sólo y3 , y5 e y7 son negativas, solo es posible que las componentes
x3 , x5 y x7 se hagan nulas con t > 0. En particular, los valores que hacen
14
respectivamente 0 cada una de esas componentes de x 1 son 0,57 , 130
5 y
9730
3 .
El menor valor de los anteriores hace que una componente, x3 , se haga nula y
no se haga negativa ninguna de las otras dos.
14 130 9730
t = min , , = 24,56 (1.27)
0,57 5 3
z1 = 523,48
z2 = 532,50
Capı́tulo 2
2.1. Definiciones
max. z =cx
s.a.:
(2.1)
Ax = b
x≥0
Además:
otro lado, cualquier solución linealmente independiente con m componentes no nulas es bási-
ca. Y cualquier solución linealmente independiente con menos de p < m componentes no nulas
también es básica por la siguiente razón. Si tomamos la matriz con las p columnas de las varia-
bles no nulas, siempre podemos añadir otras m − p columnas de variables para que formen una
base (el rango de A es m y esto siempre es posible. Haciendo eso obtendrı́amos una solución
básica con p variables básicas no nulas y m − p variables básicas nulas, lo que se conoce como
solución degenerada.
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 17
Dada una solución básica, con base B, hay dos tipos de variables:
Elegimos como base: B0 = Ah1 Ah2 Ah3 . Las tres variables básicas son las tres
variables de holgura. Dado que se deben cumplir las restricciones, el valor de
las variables de esta solución serán:
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 18
Variables básicas
h1 = 16
h2 = 26
h3 = 24
(2.4)
Variables no básicas
x1 = 0
x2 = 0
x3 = 0
Podemos convertir las cuatro filas del problema (función objetivo y tres res-
tricciones y representarlas de la siguiente manera):
Incluso lo podemos escribir en forma tabular, donde cada columna representa Representación
una variable o los términos independientes (columna de la izquierda) y ası́ no tabular
explicitar la variable de cada término.
z x1 x2 x3 h1 h2 h3
0 -1 1 2 3 0 0 0 F0
16 0 1 2 1 1 0 0 F1
26 0 3 -2 2 0 1 0 F2
24 0 1 0 2 0 0 1 F3
En la tabla 2.1 podemos leer lo siguiente, dado que las variables no básicas son Interpretación
0 y que las demás variables básicas tienen valor 0. de la tabla
En la fila F1 : 16 = h1 .
En la fila F2 : 26 = h2 .
En la fila F3 : 24 = h3 .
En la fila F0 : aparece la expresión de la función objetivo, con todas las
variables en el término de la derecha. En este caso esa fila es equivalente
a 0 = −z ⇒ z = 0, es decir, esta fila contiene la información de la función
objetivo para esta base.
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 19
En la tabla 2.1 podemos leer lo mismo que en las ecuaciones 2.5. En la tabla o Efecto de xj = t
en las ecuaciones, podemos observar lo siguiente.
Si x1 = t:
• De la fila F0 , se sigue que la función objetivo aumentarı́a en t. En
efecto, obviando los términos nulos de F0 :
0 = −z + t ⇒ z = 0 + t
16 = 1x1 + h1 ⇒ 16 = t + h1 ⇒ h1 = 16 − t
26 = 3x1 + h2 ⇒ 26 = 3t + h2 ⇒ h2 = 26 − 3t
24 = 1x1 + h3 ⇒ 24 = t + h3 ⇒ h3 = 24 − t
En resumen, hacer que una variable no básica tome un valor diferente de cero
modifica la función objetivo y modifica el valor de las variables básicas. En este
caso, la entrada en la base de cualquiera de las tres variables no básicas harı́a
que la función objetivo aumentase.
En particular, vamos a elegir la variable x3 . Dado que interesa que x3 aumen- Valor máximo
te porque ası́ aumenta la función objetivo, ¿cuál es el mayor valor que puede de x3
tomar? A la vista de las tres restricciones (2.5), se puede observar el valor
máximo que puede tomar sin que se haga negativa la variable básica corres-
pondiente.
16
16 =1t + 1h1 ⇒ t ≤ = 16
1
26
26 =2t1 + h2 ⇒ t ≤ = 13 (2.6)
2
24
24 =2t + 1h3 ⇒ t ≤ = 12
2
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 20
uB
40
30
h2
20 h3
h1
10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 x3
−10
−20
Y podemos sustituir esa expresión en el resto de filas y sustituir la tercera fila Modificación de
por la modificación de la misma: las restricciones
1 1
0 = − z + 1x1 + 2x2 + 3 12 − x1 − h3 + 0h1 + 0h2 + 0h3 Fila F0
2 2
1 1
16 =0z + 1x1 + 2x2 + 12 − x1 − h3 + 1h1 + 0h2 + 0h3 Fila F1
2 2
1 1
26 =0z + 3x1 − 2x2 + 2 12 − x1 − h3 + 0h1 + 1h2 + 0h3 Fila F2
2 2
1 1
12 =0z + x1 + 0x2 + 1x3 + 0h1 + 0h2 + h3 Fila F3
2 2
(2.8)
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 21
1 3
−36 = − z − x1 + 2x2 + 0x3 + 0h1 + 0h2 − h3 Fila F0
2 2
1 1
4 =0z + x1 + 2x2 + 0x3 + 1h1 + 0h2 − h3 Fila F1
2 2 (2.9)
2 =0z + 2x1 − 2x2 + 0x3 + 0h1 + 1h2 − 1h3 Fila F2
1 1
12 =0z + x1 + 0x2 + 1x3 + 0h1 + 0h2 + h3 Fila F3
2 2
z x1 x2 x3 h1 h2 h3
0 -1 1 2 3 0 0 0 F0
h1 16 0 1 2 1 1 0 0 F1
h2 26 0 3 -2 2 0 1 0 F2
h3 24 0 1 0 2 0 0 1 F3
-36 -1 − 12 2 0 0 0 − 23 F0
= F0 − 3F3
h1 4 0 1
2 2 0 1 0 − 21 F1
= F1 − F3
h2 2 0 2 -2 0 0 1 -1 F2
= F2 − 2F3
F3
1 1
x3 12 0 2 0 1 0 0 2 = F3 /2
Esta segunda tabla 2.2 (y este segundo conjunto de ecuaciones, 2.9) correspon- Nuevas
de a una nueva solución básica, donde la base es B1 = Ah1 Ah2 Ax3 , con lo que variables
las nuevas variables básicas y no básicas son las siguientes: básicas y no
básicas
Variables básicas
h1
h2
x3
(2.10)
Variables no básicas
x1 = 0
x2 = 0
h3 = 0
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 22
En la fila F0
: −36 = −z. Segunda
En la fila F1
: 4 = h1 . solución básica
En la fila F2
: 2 = h2 .
En la fila F3
: 12 = x3 .
En la tabla 2.2 podemos leer lo mismo que en las ecuaciones 2.9, de forma
análoga a como razonamos con la tabla 2.1.
1 1 1
si x1 = t, Δz = − 2 t, Δh1 = − 2 t, Δh2 = −2t, Δx3 = − 2 t.
si x2 = t, Δz = 2t, Δh1 = −2t, Δh2 = 2t, Δx3 = 0.
si h3 = t, Δz = − 32 t, Δh1 = 12 t, Δh2 = 1t, Δx3 = − 12 t.
De nuevo, hacer que una variable no básica tome un valor diferente de cero
modifica la función objetivo y modifica el valor de las variables no básicas. En
este caso:
4
4 =2x2 + 1h1 ⇒ 4 = 2t + 1h1 ⇒ t ≤ =2
2
2 = − 2x2 + 1h2 ⇒ 2 = 2t + 1h2 ⇒ t ≤ ∞ (2.11)
De la fila F1
de las ecuaciones de 2.9, podemos despejar x2 en función de h1 .
1 1
4 =0z + x1 + 2x2 + 0x3 + 1h1 + 0h2 − h3 ⇒
2 2
1 1 1
2 =0z + x1 + 1x2 + 0x3 + h1 + 0h2 − h3 ⇒ (2.12)
4 2 4
1 1 1
x2 =2 − x1 − h1 + h3
4 2 4
1 1 1 1 3
−36 = − z − x1 + 2 2 − x1 − h1 + h3 + 0x3 + 0h1 + 0h2 − h3 Fila F0
2 4 2 4 2
1 1 1
2 =0z + x1 + 1x2 + 0x3 + h1 + 0h2 − h3 Fila F1
4 2 4
1 1 1
2 =0z + 2x1 − 2 2 − x1 − h1 + h3 + 0x3 + 0h1 + 1h2 − 1h3 Fila F2
4 2 4
1 1 1 1 1
12 =0z + x1 + 0 2 − x1 − h1 + h3 + 1x3 + 0h1 + 0h2 + h3 Fila F3
2 4 2 4 2
(2.13)
1 1 1
2 =0z + x1 + 1x2 + 0x3 + h1 + 0h2 − h3 Fila F1
4 2 4
5 3 (2.14)
6 =0z + x1 − 0x2 + 0x3 + 1h1 + 1h2 − h3 Fila F2
2 2
1 1
12 =0z + x1 + 0x2 + 1x3 + 0h1 + 0h2 + h3 Fila F3
2 2
z x1 x2 x3 h1 h2 h3
0 -1 1 2 3 0 0 0 F0 = F0
h1 16 0 1 2 1 1 0 0 F1 = F1
h2 26 0 3 -2 2 0 1 0 F2 = F2
h3 24 0 1 0 2 0 0 1 F3 = F3
-36 -1 − 12 2 0 0 0 − 32 F0
= F0 − 3F3
h1 4 0 1
2 2 0 1 0 − 12 F1
= F1 − F3
h2 2 0 2 -2 0 0 1 -1 F2
= F2 − 2F3
x3 12 0 1
2 0 1 0 0 1
2 F3
= F3 /2
-40 -1 -1 0 0 -1 0 -1 F0
= F0
− 2F1
x2 2 0 1
4 1 0 1
2 0 − 14 F1
= F1
/2
h2 6 0 5
2 0 0 1 1 − 32 F2
= F2
+ 2F1
x3 12 0 1
2 0 1 0 0 1
2 F3
= F3
Esta tercera tabla 2.3 (y este segundo conjunto de ecuaciones, 2.14) correspon-
de a una nueva solución básica, donde la base es B2 = Ax2 Ah2 Ax3 , con lo que
las nuevas variables básicas y no básicas son las siguientes:
Variables básicas
x2
h2
x3
(2.15)
Variables no básicas
x1 = 0
h1 = 0
h3 = 0
, F2
y F3
En la fila F0
: −40 = −z.
En la fila F1
: 2 = x2 .
En la fila F2
: 6 = h2 .
En la fila F3
: 12 = x3 .
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 25
En la tabla 2.3 podemos leer lo mismo que en las ecuaciones 2.14, de forma
análoga a como razonamos en los casos anteriores.
si x1 = t, Δz = −t.
si h1 = t, Δz = −t.
si h3 = t, Δz = −t.
Se ha añadido una primera columna que incluye, para cada una de las filas co-
rrespondientes a las restricciones (1 a 3), los coeficientes en la función objetivo
de las variables básicas correspondientes.
x1 x2 x3 h1 h2 h3
0 1 2 3 0 0 0 F0
0 h1 16 1 2 1 1 0 0 F1
0 h2 26 3 -2 2 0 1 0 F2
0 h3 24 1 0 2 0 0 1 F3
-36 − 12 2 0 0 0 − 32 F0
= F0 − 3F3
0 h1 4 1
2 2 0 1 0 − 12 F1
= F1 − F3
0 h2 2 2 -2 0 0 1 -1 F2
= F2 − 2F3
3 x3 12 1
2 0 1 0 0 1
2 F3
= F3 /2
-40 -1 0 0 -1 0 -1 F0
= F0
− 2F1
2 x2 2 1
4 1 0 1
2 0 − 14 F1
= F1
/2
0 h2 6 5
2 0 0 1 1 − 32 F2
= F2
+ 2F1
3 x3 12 1
2 0 1 0 0 1
2 F3
= F3
A partir de la tabla 2.4, se puede observar que las filas 1-3 de cada tabla se Operaciones
pueden obtener mediante operaciones elementales por filas haciendo que en para las filas
las columnas de las variables básicas aparezcan las columnas de la matriz 1-3
identidad.
Igualmente, se puede observar que, para la tabla, la fila 0 de la solución básica Operaciones
(n)
n-ésima, F0 , se puede obtener realizando las siguientes operaciones: para la fila 0
(n) (n) (n) (n) (n) (n) (n)
F0 =F0 − c1 × F1 − c2 × F2 − c3 × F3
(n)
donde ci es el coeficiente en la función objetivo de la variable i-ésima varia-
ble básica.
El método del Simplex opera de forma iterativa, partiendo de una solución Planteamiento
básica factible inicial y transitando, después, de solución básica factible a so- general
lución básica factible hasta llegar a una que además es óptima.
Solución
Solución Solución básica
básica Entra variable básica factible
factible factible óptima
0 1 2 ... n-1 n
Sale variable
0 c
b A
Ejemplo
1 2
Siendo A la matriz original, A = →
3 5
haciendo la operación elemental, F 2
= F 2 + 2F 1
→
1 2
se obtiene el resultado final, .
5 9
Ası́, elegida una base B, las transformaciones del ejemplo, en realidad, se co-
rresponden con las siguientes:
−c B B −1 b c − c B B −1 A
B −1 b B −1 A
Tabla 2.6: Tabla correspondiente a una base B aplicando el método del Simplex
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 28
0 c
b A
−zB VB
uB pB
Tabla 2.7: Tabla correspondiente a una base B al aplicar el método del Simplex
0 cB cI
b B AI
−c B B −1 b 0 c I − c B B −1 A
B −1 b I B −1 (AI )
Tabla 2.8: Tabla correspondiente a una base B aplicando el método del Simplex
Una variable no básica es potencial candidata a entrar si cumple que VxBj ≥ 0. Regla de
En particular: entrada
Dada una base, se puede expresar la función objetivo de la siguiente manera: Justificación
−zB = −c B uB = −z + VxBj xj
(2.17)
j
Donde:
Dada una variable de entrada xj , la variable de salida es aquella que se anula Regla de salida
sin que el resto de variables básicas se hagan negativas. Es decir, sale la básica
variable i-ésima, que cumple lo siguiente:
B
pij >0
y
(2.18)
uBi uBk B
B ≤ B ∀k/pkj >0
pij pkj
uBi
Para ello, el valor t con el que entra la nueva variable básica xi es: t = B
pij
Esto es ası́ porque, dada una base B, cuando una variable no básica (xj ) toma Justificación
valor t, el valor de las variables básicas en función de t es:
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 30
Si una solución, x ∗ , básica (con base B) cumple que V B ≤ 0, se cumple que, Justificación
para cualquier otra solución factible del problema, x:
V B ≤ 0 ⇒ c − c B B −1 A ≤ 0 ⇒
−1 −1
B
cx − c B B
Ax ≤ 0 ⇒ cx ≤ c B Ax = c B B −1 b = c B uB = zB ⇒ (2.20)
z ≤ zB
x1 x2 x3 h1 h2 h3
0 2 1 3 0 0 0 F0
h1 60 4 2 1 1 0 0 F1
h2 20 2 6 -1 0 1 0 F2
h3 10 1 0 2 0 0 1 F3
h1 55 7/2 2 0 1 0 -1/2 F 1
= F 1 − F 3
h2 25 5/2 6 0 0 1 1/2 F 2
= F 2 + F 3
x3 5 1/2 0 1 0 0 1/2 F 3
= F 3/2
= F 0
− F 2
= F 1
− F 2
= F 2/6
x3 5 1/2 0 1 0 0 1/2 F 3
= F 3
= F 0
− 1/12F 2
= F 1
− 8/3F 2
= 12/5F 2
= F 3
− 1/2F 2
Figura 2.3: Representación gráfica del método del Simplex aplicado al proble-
ma del apartado 2.4.4
Capı́tulo 2. FUNDAMENTOS DEL MÉTODO DEL SIMPLEX 32
3.1. Introducción
Para aplicar el método del Simplex es necesario disponer de una solución Por qué estos
básica factible de partida del sistema Ax = b a partir de la cual iterar. métodos
Cuando todas las restricciones son ≤ con término independiente no negativo, Solución inicial
es decir, de la forma: sencilla
aij xj ≤ bi bi ≥ 0 (3.1)
j
aij xj + hi = bi bi ≥ 0 (3.2)
j
En este caso existe una solución de partida básica factible inicial trivial, con las Solución inicial
variables de holgura como variables básicas. Para esta solución: trivial
aij xj ≥ bi bi ≥ 0
j
(3.3)
aij xj − hi = bi bi ≥ 0
j
aij xj = bi
(3.4)
j
j
ai
j xj ≥ bi
j (3.5)
ai
j xj = bi
xj ≥ 0
max. z = cx
s.a. :
aij xj + hi = bi
j
ai
j xj − hi
= bi
(3.6)
j
ai
j xj = bi
xj , hi , hi
≥ 0
max. z
= − ai
− ai
i
i
s.a. :
aij xj + hi = bi
j
(3.7)
ai
j xj − hi
+ ai
= bi
j
ai
j xj + ai
= bi
xj , hi , hi
, ai
, ai
≥ 0
1. Dado P construir P
. Método de
2. Resolver P
: resolución
a) Si al resolver P
mediante el método del Simplex se obtiene una
solución básica factible de P
en la que todas la variables artificiales
son nulas, esa es una solución básica de partida del problema P ,
Capı́tulo 3. MÉTODOS DE LA M GRANDE Y DE LAS DOS FASES 36
Los problemas P y P
se diferencian en lo siguiente: Diferencias
entre P y P
que P
tiene un conjunto de actividades adicionales (las ficticias) y
que las contribuciones unitarias al beneficio, c y c
son diferentes.
Los problemas P y P
comparten: Analogı́as entre
P y P
B = B
.
B −1 = B
−1 .
uB = u
B , ya que B −1 b = B
−1 b
.
p B = p
B .
c B ≠ c
B
zB ≠ z
B
V B ≠ V
B
Las columnas auxiliares correspondientes a las variables artificiales permiten Las columnas
disponer, en todo momento, de parte de las columnas de la inversa de la base. de las variables
artificiales
En relación con la columna auxiliar correspondiente a la variable artificial que
proviene de una restricción =, se comprueba que el criterio del Simplex y las
tasas de sustitución tienen el mismo valor y signo contrario que los de la va-
riable de holgura asociada a esa misma restricción.
Capı́tulo 3. MÉTODOS DE LA M GRANDE Y DE LAS DOS FASES 37
max. z
= cx − M ai
− M ai
i
i
aij xj + hi = bi
j
ai
j xj − hi
+ ai
= bi
(3.8)
j
ai
j xj + ai
= bi
xj , hi , hi
, ai
, ai
≥ 0
1. Dado P construir P
. Método de
2. Resolver P
: resolución
a) Si al resolver P
mediante el método del Simplex se obtiene una
solución básica factible de P
en la que todas la variables artificiales
son nulas, esa es una solución básica de partida del problema P ,
que puede servir de solución de partida para aplicar el método del
Simplex en la resolución de P .
b) Si para cualquier solución óptima de P
, siempre al menos una va-
riable artificial toma un valor no nulo, P no tiene solución factible.
P y P
solo se diferencian en que P
tiene un conjunto de actividades adiciona- Relación entre P
les (las ficticias), lo cual se traduce en: y P
B = B
, c B = c B , uB = uB , por lo que:
VB = VB .
pB = pB .
B
u =u .
B
zB = zB .
Las columnas auxiliares correspondientes a las variables artificiales permiten Las columnas
disponer, en todo momento, de parte de las columnas de la inversa de la base. de las variables
artificiales
3.4. Ejemplos
Problema P
max. z = x1 + 2x2 + 3x3
s.a. :
x1 + x2 + x3 ≤ 16
(3.9)
3x1 + 2x2 + 2x3 = 26
x1 + x3 ≥ 10
x1 , x2 , x3 ≥ 0
Problema P
max. z = x1 + 2x2 + 3x3
reformulado
s.a. :
x1 + x2 + x3 + h1 = 16
(3.10)
3x1 + 2x2 + 2x3 = 26
x1 + x3 − h3 = 10
x1 , x2 , x3 , h1 , h3 ≥ 0
Capı́tulo 3. MÉTODOS DE LA M GRANDE Y DE LAS DOS FASES 39
Problema P’
max. z
= −a2 − a3
s.a. :
x1 + x2 + x3 + h1 = 16
(3.11)
3x1 + 2x2 + 2x3 + a2 = 26
x1 + x3 − h3 + a3 = 10
x1 , x2 , x3 , h1 , h3 , a2 , a3 ≥ 0
x1 x2 x3 h3 h1 a2 a3
fase 1 0 0 0 0 0 0 -1 -1 F 01
fase 2 0 1 2 3 0 0 0 0 F 02
16 1 1 1 0 1 0 0 F1
26 3 2 2 0 0 1 0 F2
10 1 0 1 -1 0 0 1 F3
fase 1 36 4 2 3 -1 0 0 0 F 0
1 = F 01 + F 2
+ F 3
fase 2 0 1 2 3 0 0 0 0 F 0
2 = F 02
h1 16 1 1 1 0 1 0 0 F 1
= F 1
a2 26 3 2 2 0 0 1 0 F 2
= F 2
a3 10 1 0 1 -1 0 0 1 F 3
= F 3
1 = F 01 − 4F 2
2 = F 02 − F 2
= F 1
− F 2
= F 2
/3
a3 4/3 0 -2/3 1/3 -1 0 -1/3 1 F 3
= F 3
− F 2
fase 1 0 0 0 0 0 0 -1 -1 F 0
1 = F 01 − 1/3F 3
fase 2 -18 0 6 0 7 0 2 -7 F 0
2 = F 02 − 7/3F 3
h1 6 0 1 0 1 1 0 -1 F 1
= F 1
− 1/3F 3
x1 6 1 2 0 2 0 1 -2 F 2
= F 2
− 2/3F 3
x3 4 0 -2 1 -3 0 -1 3 F 3
= 3F 3
fase 1 0 0 0 0 0 0 -1 -1 F 0
1 = F 01
fase 2 -39 -7/2 -1 0 0 0 -3/2 0 F 0
2 = F 02 − 7F 2
h1 3 -1/2 0 0 0 1 -1/2 0 F 1
= F 1
− F 2
h3 3 1/2 1 0 1 0 1/2 -1 F 2
= F 2
/2
x3 13 3/2 1 1 0 0 1/2 0 F 3
= F 3
+ 3F 2
Problema P
max. z = x1 + 2x2 + 3x3
s.a. :
x1 + x2 + x3 ≤ 16
(3.12)
3x1 + 2x2 + 2x3 = 26
x1 + x3 ≥ 10
x1 , x2 , x3 ≥ 0
Problema P
max. z = x1 + 2x2 + 3x3
reformulado
s.a. :
x1 + x2 + x3 + h1 = 16
(3.13)
3x1 + 2x2 + 2x3 = 26
x1 + x3 − h3 = 10
x1 , x2 , x3 , h1 , h3 ≥ 0
Problema P’
max. z
= x1 + 2x2 + 3x3 − Ma2 − Ma3
s.a. :
x1 + x2 + x3 + h1 = 16
(3.14)
3x1 + 2x2 + 2x3 + a2 = 26
x1 + x3 − h3 + a3 = 10
x1 , x2 , x3 , h1 , h3 , a2 , a3 ≥ 0
Capı́tulo 3. MÉTODOS DE LA M GRANDE Y DE LAS DOS FASES 41
x1 x2 x3 h3 h1 a2 a3
0 1 2 3 0 0 -M -M F0
16 1 1 1 0 1 0 0 F1
26 3 2 2 0 0 1 0 F2
10 1 0 1 -1 0 0 1 F3
h1 16 1 1 1 0 1 0 0 F 1
= F 1
a2 26 3 2 2 0 0 1 0 F 2
= F 2
a3 10 1 0 1 -1 0 0 1 F 3
= F 3
= F 0
− (1 + 4M)F 2
= F 1
− F 2
= 1
3 F2
= F 3
− F 2
= F 0
− 3 F 3
7+M
h1 6 0 1 0 1 1 0 -1 F 1
= F 1
− 1
3 F3
x1 6 1 2 0 2 0 1 -2 F 2
= F 2
− 2
3 F3
x3 4 0 -2 1 -3 0 -1 3 F 3
= 3F 3
x1 x2 x3 h3 h1 a2 a3
-18 0 6 0 7 0 2 -7
h1 6 0 1 0 1 1 0 -1
x1 6 1 2 0 2 0 1 -2
x3 4 0 -2 1 -3 0 -1 3
= F 0
− 7F 2
h1 3 -1/2 0 0 0 1 -1/2 0 F 1
= F 1
− F 2
h3 3 1/2 1 0 1 0 1/2 -1 F 2
= F 2
/2
x3 13 3/2 1 1 0 0 1/2 0 F 3
= F 3
+ 3F 2
Problema P
max. z = 2x1 + 1x2 + 3x3
s.a. :
1x1 + 2x2 + 1x3 ≤ 20
(3.15)
2x1 + 6x2 − 1x3 ≥ 100
x1 + 2x3 = 10
x1 , x2 , x3 ≥ 0
x1 x2 x3 h2 h1 a2 a3
fase 1 0 0 0 0 0 0 -1 -1 F 01
fase 2 0 2 1 3 0 0 0 0 F 02
20 1 2 1 0 1 0 0 F1
100 2 6 -1 -1 0 1 0 F2
10 1 0 2 0 0 0 1 F3
fase 1 110 3 6 1 -1 0 0 0 F 0
1 = F 01 + F 2 + F 3
fase 2 0 2 1 3 0 0 0 0 F 0
2 = F 02
h1 20 1 2 1 0 1 0 0 F 1
= F 1
a2 100 2 6 -1 -1 0 1 0 F 2
= F 2
a3 10 1 0 2 0 0 0 1 F 3
= F 3
fase 1 50 0 0 -2 -1 -3 0 0 F 0
1 = F 0
1 − 6F 1
2 = F 0
2 − F 1
= F 1/2
a2 40 -1 0 -4 -1 -3 1 0 F 2
= F 2 − 6F 1
a3 10 1 0 2 0 0 0 1 F 3
= F 3
INTERPRETACIÓN TÉCNICO-ECONÓMICA
4.1. Introducción
c
b
A
Para un problema y una base B (que caracteriza a la solución básica corres- Elementos
pondiente), existen varios elementos caracterı́sticos de esa solución para ese caracterı́sticos
problema de una solución
uB
cB
pB
πB
En otro contexto, el valor que tiene un vaso de agua cuando alguien lleva varios Un ejemplo más
dı́as sin suministro en el desierto es muy diferente del valor que tiene ese vaso doméstico
de agua en el domicilio de una ciudad con un buen suministro de agua potable
corriente. El vaso de agua es el mismo pero el valor depende de la situación.
Aquı́ diremos que los recursos tienen diferente valor según la solución, es
decir, según la base elegida.
Capı́tulo 4. INTERPRETACIÓN TÉCNICO-ECONÓMICA 44
Para ilustrar la interpretación, en lo que sigue del capı́tulo emplearemos el Presentación del
siguiente ejemplo. Una empresa monta dos tipos de palés. Los palés de tipo problema
1 contienen un producto P1 y los palés de tipo 2 contienen, a su vez, dos
productos P2 .
Con la venta de cada palé de tipo 1, la empresa tiene un beneficio neto de 2 El beneficio
unidades monetarias (u.m.). Igualmente, la empresa tiene un beneficio neto de
1 u.m. con cada palé de tipo 2.
Los palés deben ser preparados en dos talleres, T1 y T2 , de los que se dispone Los talleres
de un total de 30 y 16 horas semanales, respectivamente, para realizar las
operaciones correspondientes a cada uno de ellos. Cada palé 1 requiere 3 horas
de preparación en T1 y 4 horas de preparación en T2 . Cada palé 2 requiere 1
hora de preparación en T1 y 3 horas de preparación en T2 .
Por último, existe un colectivo al respecto del cual la empresa tiene un compro-
miso consistente en emplear un número mı́nimo de horas de dicho colectivo.
Con cada palé de tipo 1 se emplea una hora de este colectivo y con cada palé
2 se ocupan 3 horas del mismo. La empresa debe ocupar al menos 5 horas de
mano de obra del colectivo citado.
Formulación
Capı́tulo 4. INTERPRETACIÓN TÉCNICO-ECONÓMICA 45
max. z = 2x1 + x2
s.a. :
3x1 + 1x2 ≤ 30
4x1 + 3x2 ≤ 16 (4.1)
x1 + 2x2 ≥ 4
x1 + 3x2 ≥ 5
x1 , x2 ≥ 0
Formulación
max. z = 2x1 + x2
equivalente
s.a:
3x1 + x2 + h1 = 30
(4.2)
4x1 + 3x2 + h2 = 16
x1 + 2x2 − h3 = 4
x1 + 3x2 − h4 = 5
h1 = 167/9, es decir, el taller T1 no está ocupado todo el tiempo. De las Uso de los
30 horas, está ocioso un total de 18.56 horas. recursos
h2 = 0, es decir, el taller T2 está ocupado las 16 horas en las que está
disponible cada semana.
h3 = 1/9, es decir, se producen 0.11 palés más del mı́nimo comprometi-
do. En total, se entregan 4.11 por término medio cada semana.
h4 = 0, es decir, el nivel de ocupación del colectivo al que se refiere el
compromiso está ocupado un número de horas igual al mı́nimo.
B
El elemento pij relaciona la variable básica que ocupa la posición i-ésima y la
B
variable j-ésima del problema. En particular, pij representa en qué medida dis-
minuye el nivel de realización de la actividad básica i-ésima cuando se realiza
la actividad j-ésima con valor unitario. De otra manera:
B
pij = −ΔuBi |xj =1 (4.5)
Capı́tulo 4. INTERPRETACIÓN TÉCNICO-ECONÓMICA 47
⎛ ⎞
0 0 1 −8/9 0 −5/9
⎜ ⎟
⎜ 0 0 0 2/9 1 1/9 ⎟
pB = ⎜
⎜ 1
⎟
⎟ (4.6)
⎝ 0 0 1/3 0 1/3 ⎠
0 1 0 −1/9 0 −4/9
Por ejemplo, las tasas de sustitución de la variable h2 con respecto a las varia-
bles básicas se discuten a continuación.
π B = c B B −1 (4.7)
z = c B uB = c B B −1 b = π B b (4.8)
La relación que existe entre los multiplicadores del Simplex y los valores de los
criterios del Simplex es la siguiente.
5 2
π B = π1B , π2B , π3B , π4B = 0, , 0, − (4.12)
9 9
x1 x2 x3 h3 h1 a2 a3
fase 1 0 0 0 0 0 0 -1 -1 F 01
fase 2 0 1 2 3 0 0 0 0 F 02
16 1 1 1 0 1 0 0 F1
26 3 2 2 0 0 1 0 F2
10 1 0 1 -1 0 0 1 F3
...
fase 1 0 0 0 0 0 0 -1 -1 F 0
1 = F 0
1
fase 2 -39 -7/2 -1 0 0 0 -3/2 0 F 0
2 = F 0
2 − 7F 2
h1 3 -1/2 0 0 0 1 -1/2 0 F 1
= F1 − F2
h3 3 1/2 1 0 1 0 1/2 -1 F 2
= F 2
/2
x3 13 3/2 1 1 0 0 1/2 0 F 3
= F 3
+ 3F 2
V B = c − c B B −1 A (4.13)
El primer término cxk representa el beneficio unitario que reporta la actividad cxk
xk . Existen dos formas de interpretar VxBk :
x1 x2 h1 h2 h3 h4 Otra solución
-2 3/2 0 0 0 1/2 0
h1 28 5/2 0 1 0 1/2 0
h2 10 5/2 0 0 1 3/2 0
h4 1 1/2 0 0 0 -3/2 1
x2 2 1/2 1 0 0 -1/2 0
Con cualquiera de las dos posibles interpretaciones, cx1 = 2, representa el be- cx1
neficio unitario por realizar una unidad de la actividad 1, es decir, por montar
y vender un palé de tipo 1.
c B p1B
c B = (0, 0, 0, 1)
(4.16)
5 5 1 1 T
pB = , , ,
2 2 2 2
1
Es decir, dejamos de ganar 2.
1
π B = (0, 0, , 0)
2 (4.17)
Ax1 = (3, 4, 1, 1)T
1
Es decir, dejamos de ganar 2.
Netamente: VxB1 =
cx1 − π B Ax1
El beneficio aumenta, por un lado, en 2 y
disminuye, por otro, en 12 ,
5.1. Introducción
Lógica del
Soluciónmétodo del
Solución Solución básicaSimplex
básica Entra variable básica factible
factible factible óptima
0 1 2 ... n-1 n
Sale variable
En este capı́tulo se va a presentar el método de Lemke, o dual del Simplex, que Lógica del
también permite resolver problemas de Programación Lineal. En este método método de
consistı́a en, a partir de una solución básica que cumple el criterio de optimali- Lemke
dad (V B ≤ 0) de partida, de forma iterativa, se transita por diferentes solución
básicas que también cumplen el criterio de optimalidad hasta alcanzar una que
también es factible.
Las soluciones por las que transita el método del Lemke siempre cum-
plen el criterio de optimalidad.
En el método del Simplex, con las diferentes iteraciones, se mejora el
criterio de optimalidad hasta alcanzar una solución óptima (que también
es factible).
En el método del Lemke, con las diferentes iteraciones, se mejora el cri-
terio de factiblidad hasta alcanzar una solución factible (que también es
óptima).
Solución
Solución Solución básica
básica Entra variable básica óptima
óptima óptima factible
0 1 2 ... n-1 n
Sale variable
Para aplicar el método de Lemke, de acuerdo con la lógica anterior, es necesa- Qué
rio: necesitamos
En efecto:
Es decir, la solución en la que las variables básicas son las variables de holgura
es una solución que cumple el criterio de optimalidad y es básica (no factible),
con lo cual es una solución a partir de la cual se puede aplicar el método del
ejemplo.
La tabla inicial a partir de la cual se podrı́a comenzar a iterar, tal y como se La tabla inicial
describe más adelante, serı́a la siguiente:
x1 x2 x3 h1 h2 h3
0 -1 -2 -3 0 0 0
h1 -10 -1 -2 -1 1 0 0
h2 -20 -4 -2 -3 0 1 0
h3 40 1 1 1 0 0 1
uB = B −1 b
zB = c B uB
Y no se modfiicarı́a:
VB
pB
Si el cambio de b hace que algún uBi sea negativo, la solución que era óptima
y factible deja de ser factible y sigue cumpliendo V B ≤ 0, por lo que es una
solución a partir de la cual se puede aplicar el método de Lemke.
x1 x2 x3 h1 h2 h3
-40 -1 0 0 -1 0 -1
x2 2 1/4 1 0 1/2 0 -1/4
h2 6 5/2 0 0 1 1 -3/2
x3 12 1/2 0 1 0 0 1/2
Capı́tulo 5. MÉTODO DEL LEMKE 60
T
Si el nuevo vector fuera b
= 10 26 24 , el nuevo valor de uB serı́a el
siguiente.
⎛ ⎞⎛ ⎞ ⎛ ⎞
1
0 − 14 10 −1
⎜ 2 ⎟ ⎜ ⎟ ⎜ ⎟
uB = B −1 b
= ⎜
⎝ 1 1 − 32 ⎟
⎠ ⎝ 26 ⎠ = ⎝ 0 ⎠ (5.4)
1
0 0 2
24 12
T
El nuevo valor de z serı́a c B uB = 2 0 3 −1 0 12 = 34.
x1 x2 x3 h1 h2 h3
-34 -1 0 0 -1 0 -1
x2 -1 1/4 1 0 1/2 0 -1/4
h2 0 5/2 0 0 1 1 -3/2
x3 12 1/2 0 1 0 0 1/2
A partir de esa tabla se podrı́a iterar aplicando el método de Lemke, tal y como
se comenta más adelante en el capı́tulo.
x1 x2 x3 h2 h1
-8 0 2 0 -2 -2
x1 2 1 4 0 2 1
x3 0 0 -3 1 -3 -1
-9 -1/2 0 0 -3 -5/2
x2 1/2 1/4 1 0 1/2 1/4
x3 3/2 3/4 0 1 -3 /2 -1/4
Capı́tulo 5. MÉTODO DEL LEMKE 61
x1 x2 x3 h2 h1 h3
-9 -1/2 0 0 -3 -5/2 0
x2 1/2 1/4 1 0 1/2 1/4 0
x3 3/2 3/4 0 1 -3 /2 -1/4 0
1 0 1 1 0 0 1 (fila en la tabla original)
h3 -1 -1 0 0 1 0 1 (nueva fila)
x1 x2 x3 h2 h1 h3
-9 -1/2 0 0 -3 -5/2 0
x2 1/2 1/4 1 0 1/2 1/4 0
x3 3/2 3/4 0 1 -3 /2 -1/4 0
h3 -1 -1 0 0 1 0 1
5.3. Reglas
Dada una solución básica no factible interesa que salga de la base cualquier
variable con valor negativo. En particular, saldrá la variable i-ésima que cum-
ple:
Capı́tulo 5. MÉTODO DEL LEMKE 62
uBi = maxuB <0 uBk (5.6)
k
Dado que la variable i-ésima de la base es la que debe salir, la variable que
entra en su lugar es la variable j-ésima del problema que cumple lo siguiente:
VxBj VxBk
= minpB <0 B (5.7)
pij ik pik
Si, en general, entra la variable j-ésima del problema, los nuevos criterios del
Simplex son:
pik B
VxBk = VxBk − B Vxj (5.8)
pij
Para garantizar que con la nueva base se sigue cumpliendo el criterio de opti-
malidad se debe cumplir 5.7.
B
pik B
pik VxBk VxBj
B
VxBk = VxBk − B VxBj ≤ 0 ⇒ VxBk ≤ B VxBj ⇒ B ≥ B dado que pik ≤ 0 (5.9)
pij pij pik pij
5.4. Ejemplo
El problema
min. z =300x1 + 400x2 + 100x3 + 50x4
s.a. :
4x1 + 5x2 + 2x3 + x4 ≥ 800
(5.10)
2x1 + 4x2 + 1x3 ≥ 600
1x1 + 1x2 + 4x4 ≤ 2000
xi ≥ 0
Capı́tulo 5. MÉTODO DEL LEMKE 63
Problema equivalente
Problema equivalente
x1 x2 x3 x4 h1 h2 h3
0 -300 -400 -100 -50 0 0 0 F0
h1 -800 -4 -5 -2 -1 1 0 0 F1
h2 -600 -2 -4 -1 0 0 1 0 F2
h3 2000 1 1 0 4 0 0 1 F3
h3 2000 1 1 0 0 0 0 1 F3
= F3
= F0
+ 150F2
= F1
− 5/2F2
= −2/3F2
= F3
− F2
100
10 20 30 40 50 60 70 80 90 100 110 VB
VxB3
−100
−200
VxB1
−300
VxB2
−400
VB
Figura 5.3: Efecto de h1 en los criterios del Simplex de las variables no básicas
Capı́tulo 6
POSTOPTIMIZACIÓN
6.1. Introducción
max z = cx
s.a. :
(6.1)
Ax = b
x≥0
1. b
2. c
3. Aparición de una nueva actividad (una nueva columna en A y una nueva
componente en c)
4. Aparición de una nueva restricción (una nueva fila en A y una nueva
componente en b)
5. Cambio en aij
6.2. Cambio en b
1. u
B = B −1 b
2. z
= c B u
B
Capı́tulo 6. POSTOPTIMIZACIÓN 66
No cambia:
1. B
2. B −1
3. p B = B −1 A
4. V B = c − c B B −1 A. En particular, al tratarse de la solución óptima V B ≤ 0.
1. Si u
B
i ≥ 0 ∀i, la solución sigue siendo factible y, como V ≤ 0, las varia-
B
6.3. Cambio en c
1. z
= c
B uB
2. V B = c
− c
B B −1 A
No cambia:
1. B
2. B −1
3. p B = B −1 A
4. uB = B −1 b. En particular, como la solución era factible uB ≥ 0.
1. Si Vx
Bj ≤ 0 ∀j, la solución sigue siendo óptima y, como uB ≥ 0, las varia-
bles básicas son las mismas, con el mismo nivel de realización uB y un
nuevo valor de la función objetivo z
.
2. Si ∃Vx
Bj > 0, la solución deja de ser óptima pero sigue siendo factible,
uB ≥ 0. Se debe aplicar el método de Simplex hasta obtener una solución
que además de ser factible cumpla el criterio de optimalidad, la nueva so-
lución óptima, que tendrá algunas variables básicas de las de la solución
original.
Capı́tulo 6. POSTOPTIMIZACIÓN 67
1. Cambia cxk y xk no es variable básica. Solo cambia VxBk , con lo que esta
actividad, que no era básica, al cambiar VxBk podrı́a ocurrir que VxBk ≥ 0,
en cuyo caso la solución original no serı́a óptima.
2. Cambia cxk y xk es variable básica, con lo que cambiarı́a todo V B .
Con la aparición de una nueva actividad, la solución óptima del problema pue-
de ser la misma o puede ser otra mejor.
a x ≤ bl ⇒ j alj xj + hl = bl
j lj j (6.2)
j alj xj ≥ bl ⇒ j alj xj − hl = bl
j alj xj ≤ bl
alxj xj = bl equivalente a: (6.3)
j j alj xj ≥ bl
Se pueden dar dos situaciones, que la variable xj sea básica o que no.
1. Vx
Bj = cxj − c B B −1 Axj
2. pj
B = B −1 Axj
Capı́tulo 6. POSTOPTIMIZACIÓN 69
No cambia:
1. B
2. B −1
3. z = c B uB
4. VxBk , k ≠ j (no cambia el criterio del Simplex del resto de variables)
5. pk
B = B
−1 A
xk k ≠ j
6. u
B = B
−1 b
1. B
2. B
−1
3. u
B = B
−1 b
4. z
= c
B u
B
5. V
B = c − c
B B
−1 A
6. p
B = B
−1 A
V
B ≤ 0 ∃V B ≥ 0
u
B ≥ 0 Solución óptima Simplex
∃uB ≤ 0 Lemke -
6.7. Ejemplo
x1 x2 x3 h3 h1 a2 a3
-39 -7/2 -1 0 0 0 -3/2 0
h1 3 -1/2 0 0 0 1 -1/2 0
h3 3 1/2 1 0 1 0 1/2 -1
x3 13 3/2 1 1 0 0 1/2 0
6.7.1. Cambio de b
T
Supongamos que b
= 14 22 11 . El nuevo valor de las variables bási-
cas, u
B serı́a:
⎛ ⎞⎛ ⎞ ⎛ ⎞
1 −1/2 0 14 3
⎜ ⎟⎜ ⎟ ⎜ ⎟
u
B = B −1 b
= ⎝ 0 1/2 −1 ⎠ ⎝ 22 ⎠ = ⎝ 0 ⎠ (6.5)
0 1/2 0 11 11
T
Supongamos que b
= 12 26 11 . El nuevo valor de las variables bási-
cas, u
B serı́a:
⎛ ⎞⎛ ⎞ ⎛ ⎞
1 −1/2 0 12 −1
⎜ ⎟⎜ ⎟ ⎜ ⎟
u
B = B −1 b
= ⎝ 0 1/2 −1 ⎠ ⎝ 26 ⎠ = ⎝ 2 ⎠ (6.6)
0 1/2 0 11 13
x1 x2 x3 h3 h1 a2 a3
-39 -7/2 -1 0 0 0 -3/2 0
h1 -1 -1/2 0 0 0 1 -1/2 0
h3 2 1/2 1 0 1 0 1/2 -1
x3 13 3/2 1 1 0 0 1/2 0
-32 0 -1 0 0 -7 2 0
x1 2 1 0 0 0 -2 1 0
h3 1 0 1 0 1 1 0 -1
x3 10 0 1 1 0 3 -1 0
Capı́tulo 6. POSTOPTIMIZACIÓN 71
6.7.2. Cambio de c
Supongamos que c
= 2 2 4 0 0 .
V ‘B = c
− c
B B −1 A =
⎛ ⎞
−1/2 0 0 0 1
⎜ ⎟
2 2 4 0 0 − 0 0 4 ⎝ 1/2 1 0 1 0 ⎠ = −4 −2 0 0 0
3/2 1 1 0 0
(6.7)
Supongamos que c
= 6 1 3 0 0 .
V ‘B = c
− c
B B −1 A =
⎛ ⎞
−1/2 0 0 0 1
⎜ ⎟
6 1 3 0 0 − 0 0 3 ⎝ 1/2 1 0 1 0 ⎠ = 3/2 −2 0 0 0
3/2 1 1 0 0
(6.8)
x1 x2 x3 h3 h1 a2 a3
-39 3/2 -2 0 0 0 -3/2 0
h1 3 -1/2 0 0 0 1 -1/2 0
h3 3 1/2 1 0 1 0 1/2 -1
x3 13 3/2 1 1 0 0 1/2 0
-48 0 -5 0 -3 0 -3 3
h1 6 0 1 0 1 1 0 -1
x1 6 1 2 0 2 0 1 -2
x3 4 0 -2 1 -3 0 -1 3
Capı́tulo 6. POSTOPTIMIZACIÓN 72
cx4 = 5
T
Ax4 = 1 1 1
VxB4 = cx
4 − c B B −1 Ax4 = cx
4 − π B Ax4
⎛ ⎞
1 (6.9)
⎜ ⎟
5 − 0 3/2 0 ⎝ 1 ⎠ = 7/2
1
p4B = B −1 Ax4 =
⎛ ⎞⎛ ⎞ ⎛ ⎞
1 −1/2 0 1 1/2
⎜ ⎟⎜ ⎟ ⎜ ⎟ (6.10)
⎝ 0 1/2 −1 ⎠ ⎝ 1 ⎠ = ⎝ −1/2 ⎠
0 1/2 0 1 1/2
x1 x2 x3 x4 h3 h1 a2 a3
-39 -7/2 -1 0 7/2 0 0 -3/2 0
h1 3 -1/2 0 0 1/2 0 1 -1/2 0
h3 3 1/2 1 0 -1/2 1 0 1/2 -1
x3 13 3/2 1 1 1/2 0 0 1/2 0
-60 0 -1 0 0 0 -7 2 0
x4 6 -1 0 0 1 0 2 -1 0
h3 6 0 1 0 0 1 1 0 -1
x3 10 2 1 1 0 0 -1 1 0
x2 + x3 ≤ 15 (6.11)
x2 + x3 ≤ 10 (6.12)
x2 + x3 + h4 = 10 (6.13)
x1 x2 x3 h3 h1 h4 a2 a3
-39 -7/2 -1 0 0 0 0 -3/2 0
h1 3 -1/2 0 0 0 1 0 -1/2 0
h3 3 1/2 1 0 1 0 0 1/2 -1
x3 13 3/2 1 1 0 0 0 1/2 0
10 0 1 1 0 0 1 0 0 (fila en la tabla original)
h4 -3 -3/2 0 0 0 0 1 -1/2 0 (nueva fila)
ANÁLISIS DE SENSIBILIDAD
7.1. Introducción
max. z = cx
s.a. :
(7.1)
Ax = b
x≥0
−zB VB
uB pB
7.2. Análisis de b
uB = B −1 b
zB = c B uB = c B B −1 b
B −1 b ≥ 0 (7.2)
7.3. Análisis de c
V B = c − c B B −1 A
zB = c B uB , si la variable xi es básica.
c − c B B −1 A ≤ 0 (7.3)
7.4. Ejemplo
x1 x2 x3 h1 a2
-111/2 0 -1/2 0 -19/10 -2/5
x3 7/2 0 1/2 1 3/10 -1/5
x1 11/2 1 1/2 0 -1/10 2/5
El rango de valores para cx2 dentro del cual la composición del mix de produc-
ción se mantiene igual se obtiene calculando los nuevos criterios del Simplex
en función de dichos valores.
Capı́tulo 7. ANÁLISIS DE SENSIBILIDAD 77
3 3/10 −1/5 3
−1
VxB2 B
= cx2 −c B Ax2 = cx2 −π B
= cx2 − 8 5 = cx2 −13/2
2 −1/10 2/5 2
(7.5)
13 13
El mix sigue siendo el mismo si cx2 − 2 ≤ 0, es decir, si cx2 ≤ 2 .
13
En el caso de que cx2 = 2 la tabla correspondiente a la solución óptima serı́a
la siguiente:
x1 x2 x3 h1 a2
-111/2 0 0 0 -19/10 -2/5
x3 7/2 0 1/2 1 3/10 -1/5
x1 11/2 1 1/2 0 -1/10 2/5
De forma que serı́a posible aplicar el método del Simplex y que la variable x2 Nueva base
entrara en la base, para obtener una nueva solución básica con la misma fun-
ción objetivo. Igualmente, si cx2 fuera ligeramente superior a 13
2 , el criterio del
Simplex de x2 serı́a positivo y la entrada de x2 en la base darı́a lugar a una
mejora de la función objetivo. En cualquiera de los dos casos, tras iterar se ob-
tendrı́a una nueva base para la solución óptima, caracterizada por la siguiente
tabla. El valor de la función objetivo dependerı́a del valor de c2 (como se ha
dicho serı́a el mismo si cx2 = 13 13
2 y serı́a mayor si cx2 > 2 .
x1 x2 x3 h1 a2
0 0 VxB3 VhB1
x2 7 0 1 2 3/5 -2/5
x1 2 1 0 -1 -2/5 3/5
Los criterios del Simplex dependerı́an del valor de cx2 cuando la base es B =
Ax2 Ax1 . En efecto, V B serı́a:
0 1 2 3/5
B B B
V =c−c p = 5 cx2 8 0 − cx2 5 =
1 0 −1 −2/5
10−3cx2
= 0 0 13 − 2cx2 5
(7.6)
Capı́tulo 7. ANÁLISIS DE SENSIBILIDAD 78
El el caso de que cambie cx3 , como x3 es una variable básica, cambian los
criterios del Simplex de todas las variables (menos los de las básicas, que son
0). En particular:
0 1/2 1 3/10
B B −1 B
V =c−c B A=c−c p = 5 6 cx3 0 − cx3 5 =
1 1/2 0 −1/10
cx3 +5 3cx3 −5 7−cx3 5−3cx3
= 5 6 cx3 0 − 5 2 cx3 10
= 0 2 0 10
(7.7)
7 − cx3 ≤ 0 cx3 ≥ 7
⇒ ⇒ cx3 ≥ 7 (7.8)
5 − 3cx3 ≤ 0 cx3 ≥ 53
Como en el caso anterior, podrı́amos evaluar cuál serı́a la nueva base para el
caso en el que cx3 fuera igual o ligeramente inferior a 7. En el caso de que fuera
igual, el criterio del Simplex de x2 serı́a nulo, con lo cual dicha variable podrı́a
entrar en la base y se podrı́a encontrar una nueva base correspondiente a una
solución óptima pero con el mismo valor de la función objetivo. Si cx3 fuera
ligeramente inferior a 7, la entrada de x2 en la base darı́a lugar a una función
objetivo mayor. Al introducir x2 , tendrı́amos la solución correspondiente a la
siguiente tabla:
x1 x2 x3 h1 a2
0 0 -3 -14/5 1/5
x2 7 0 1 2 3/5 -2/5
x1 2 1 0 -1 -2/5 3/5
7.4.3. Análisis de b2
B −1 3/10 −1/5 25
75−2b2 b2 ≤ 75/2
u =B b= = 10
≥0⇒
−1/10 2/5 b2 −25+4b2 b2 ≥ 25/4
10
(7.10)
Dado el problema:
x1 x2 h1 h2
-80/3 0 0 -5/3 -1/3
x2 20/3 0 1 2/3 1/3
x1 20/3 1 0 -1/3 -2/3
CASOS ESPECIALES
8.1. Introducción
Además, todas las soluciones del tipo x = λx B + (1 − λ)x B con λ ∈ (0, 1) son Soluciones no
soluciones no básicas y óptimas del problema. básicas óptimas
1 Esto es ası́ siempre. Si existen variables básicas con tasas de sustitución positiva con respecto
a xk , una de ellas será la que abandone la base. Si todas las tasas de sustitución son negativas
se trata de un caso que se describe en la sección 8.5.
Capı́tulo 8. CASOS ESPECIALES 82
x2 z
1 2 3 4 5 6 7 8 x1
Ejemplo
max. z = 3x1 + 4x2
s.a. :
3x1 + 4x2 ≤ 12
(8.1)
x2 ≤ 2
x1 − x2 ≤ 1
x1 , x2 ≥ 0
x1 x2 h1 h2 h3 Soluciones
-12 0 0 -1 0 0 óptima básicas
x1 4/3 1 0 1/3 -4/3 0
x2 2 0 1 0 1 0
h3 5/3 0 0 -1/3 7/3 1
-12 0 0 -1 0 0
x1 16/7 1 0 1/7 0 4/7
x2 9/7 0 1 1/7 0 -3/7
h2 5/7 0 0 -1/7 1 3/7
Capı́tulo 8. CASOS ESPECIALES 83
z
x2
1 2 3 4 5 6 7 x1
Se dice que una solución básica es degenerada si alguna de las variables básicas Caracterización
toma valor 0, es decir, algún uBi = 0. analı́tica
Ejemplo
max. z = x1 + 4x2
s.a. :
2x1 + 3x2 ≤ 6 (8.2)
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
Capı́tulo 8. CASOS ESPECIALES 84
x1 x2 h1 h2 Solución del
-8 -5/3 0 -4/3 0 problema
x2 2 2/3 1 1/3 0
h2 0 -1/3 0 -2/3 1
-8 -1 0 0 -2
x2 2 1/2 1 0 1/2
h1 0 1/2 0 1 -3/2
-8 0 0 2 -5
x2 2 0 1 -1 2
x1 0 1 0 2 -3
Las soluciones degeneradas llevan asociados precios sombra múltiples. A con- Precios sombra
tinuación, esto se ilustra con otro ejemplo: múltiples
Ejemplo
max. z = x1 + 2x2
s.a. :
x1 + 3x2 ≤ 15
(8.3)
x1 + x2 ≤ 10
2x1 ≤ 15
x1 , x2 ≥ 0
x1 x2 h1 h2 h3 Interpretación
Solución del
-25/2 0 0 0 -2 1/2 gráfica
problema
x1 15/2 1 0 0 0 1/2
x2 5/2 0 1 0 1 -1/2
h1 0 0 0 1 -3 1
x2
9
6
z
5
4 Restricciones redundantes
3
Solución óptima básica degenerada
h1 = h2 = h3 = 0
2
1 2 3 4 5 6 7 8 9 10 11 12 x1
T
15 5
Las tres conducen a una misma solución: x = 2 2 0 0 0 . La solución
Los precios sombra de cada base son los siguientes: Los precios
sombra
1
π B1 = 0 2 2
2
π B2 = 0 16
3
1 1
π B3 = 2 2 0
Al relajar cualquiera de las tres restricciones, es decir, al hacer Δbi > 0, las Análisis de
otras dos siguen activas y la solución no cambia. Naturalmente, en consecuen- Δi > 0
cia, tampoco cambia el valor de la función objetivo.
Sin embargo, al hacer Δbi < 0, la modificación tiene lugar de forma diferente, Análisis de
porque la modificación de la restricción correspondiente hace que las tres ba- Δi < 0
ses no conduzcan a la misma solución y, además, en cada caso se modifican
de una manera diferente.
Capı́tulo 8. CASOS ESPECIALES 86
z
x2
B3
3
B2
2
B1
1 2 3 4 5 6 7 8 9 10 11 12 x1
Si se modifica b2 , de forma que Δb2 = −1, la función objetivo de cada una Ejemplo con R2
de las tres bases son las siguientes, consistente con los valores de los precios
sombra:
B
zB1 = 12, es decir, Δz = −2 = −π2 1
B
zB2 , es decir, Δz = 0 = −π2 2
1 B
zB3 , es decir, Δz = − 2 = −π2 3
Es decir:
Cuando se aplica el método del Simplex para resolver el problema auxiliar Caracterización
correspondiente al método de las dos fases (o de la M grande), el problema analı́tica.
Simplex
Capı́tulo 8. CASOS ESPECIALES 87
original no tiene solución factible si para todas las soluciones óptimas del
problema auxiliar existe al menos una variable artificial diferente de 0.
x2 z
1 2 3 4 5 6 7 8 9 x1
Ejemplo
min. z = 2x1 + 3x2 = max. (−z) = −2x1 − 3x2
s.a. :
x1 + 2x2 ≤ 1 (8.4)
x1 + x2 ≥ 3
x1 , x2 ≥ 0
Esta serı́a la tabla a la que se llegarı́a aplicando el método de las dos fases. Aplicando las
dos fases
x1 x2 h2 h1 a2
2 0 -1 -1 -1 0
x1 1 1 2 0 1 0
a2 2 0 -1 -1 -1 1
Capı́tulo 8. CASOS ESPECIALES 88
0 0 -1 0 -2
h1 -2 0 1 1 1
x1 3 1 1 0 -1
B
Si en la solución óptima existe una variable, xk , no básica, y pik ≤ 0 para todas Caracterización
las variables básicas (i = 1...m), entonces, al aumentar el valor de xk aumen- analı́tica
ta el valor de todas las variables básicas, con lo que la región de soluciones
factibles no está acotada.
Para cualquier variable no básica, xk , si VxBk < 0, a pesar de que es posible Solución óptima
que esta variable entre en la base con el consiguiente incremento de todas las única
variables básicas, la entrada de xk no aumenta el valor de la función objetivo,
con lo que la solución óptima es única.
x2
z
10
6
Solución óptima básica (única)
1 2 3 4 5 6 7 8 9 10 11 12 x1
Ejemplo
max. z = −2x1 + 3x2
s.a. :
−x1 + 2x2 ≤ 6 (8.5)
−2x1 + 2x2 ≤ 0
x1 , x2 ≥ 0
x1 x2 h1 h2 Solución del
-6 0 0 -1 -1/2 problema
x1 6 1 0 1 -1
x2 6 0 1 1 -1/2
Si VxBk = 0, aunque es posible que esta variable entre en la base con el consi- Soluciones
guiente incremento de todas las variables básicas, la entrada de xk no altera el óptimas
valor de la función objetivo, con lo que existen soluciones óptimas múltiples. múltiples
x2
10
Soluciones óptimas
9 no básicas
8
z
7
6
Solución óptima básica
1 2 3 4 5 6 7 8 9 10 11 12 13 14 x1
Ejemplo
max. z = −2x1 + 4x2
s.a. :
−x1 + 2x2 ≤ 6 (8.6)
−2x1 + 2x2 ≤ 0
x1 , x2 ≥ 0
Capı́tulo 8. CASOS ESPECIALES 90
z
x2
x1
1 2 3 4 5 6 7 8 9 10 11 12 13 14
x1 x2 h1 h2 Solución del
-12 0 0 -2 0 problema
x1 6 1 0 1 -1
x2 6 0 1 1 -1/2
Si VxBk ≥ 0, es posible que esta variable entre en la base con el consiguiente z no acotada
incremento de todas las variables básicas y de z, con lo que el problema no
está acotado y no se puede hablar de solución óptima.
Ejemplo
max. z = 3x1 + x2
s.a. :
−x1 + 2x2 ≤ 6 (8.7)
−2x1 + 2x2 ≤ 0
x1 , x2 ≥ 0
x1 x2 h1 h2 Solución del
0 3 1 0 0 problema
h1 6 -1 2 1 0
h2 0 -2 2 0 1
Capı́tulo 9
INTERPRETACIÓN GRÁFICA
9.1. Introducción
Existe una forma de abordar lo que aquı́ se presenta de forma muy somera Teorı́a de
conocida como Teorı́a de poliedros, que resulta útil para el tratamiento y la poliedros
resolución de problemas de Programación Lineal, pero que queda fuera del
alcance de este texto.
max. z = cx
s.a:
(9.1)
Ax = b
x≥0
x ∈ R+
2×1 Dimensiones
A ∈ Rm×2
c ∈ R1×2
b ∈ Rm×1
max. z = x1 + 2x2
s.a.:
−2x1 + x2 ≤ 2 Restricción R1
(9.2)
x1 + x2 ≤ 6 Restricción R2
2x1 + x2 ≤ 10 Restricción R3
x1 , x2 ≥ 0
En la figura 9.1, aparecen representadas las tres restricciones. Cada restricción Restricciones
de tipo ≤ o ≥ divide al plano en dos semiplanos, de tal manera que uno de
ellos corresponde a soluciones factibles con respecto a dicha restricción y el
otro semiplano a soluciones no factibles con respecto a la misma restricción.
max. z = x1 + 2x2
s.a.:
−2x1 + x2 + h1 = 2
(9.3)
x1 + x2 + h2 = 6
2x1 + x2 + h3 = 10
x1 , x2 , h1 , h2 , h3 ≥ 0
Por ejemplo:
El punto (4, 2)
• Está a la derecha de la recta R1 , el su semiplano factible, con lo que
h1 > 0.
• Está sobre la recta R2 , con lo que h2 = 0.
• Está sobre la recta R3 , con lo que h3 = 0.
El punto (1, 6)
Capı́tulo 9. INTERPRETACIÓN GRÁFICA 93
x2
10
−1 1 2 3 4 5 6 7 x1
Las restricciones funcionales junto con las restricciones de no negatividad de- Región de
finen la región de factibilidad (sombreada en la figura 9.2). Cualquier punto soluciones
perteneciente a la región de soluciones factibles cumple con todas las restric- factibles
ciones, incluidas las de no negatividad.
x2
10
−1 1 2 3 4 5 6 7 x1
La función objetivo se puede entender como un haz de rectas paralelas cx1 x1 + Haz de rectas
cx2 x2 = k.
En el ejemplo del problema, como se observa en la figura 9.3, la recta x1 + Función objetivo
2x2 = 14 es el conjunto de todas las soluciones que proporcionan un valor
de la función objetivo de 14. Ninguno de los puntos de dicha recta están en la
región de soluciones factibles, por lo que no existe ninguna solución factible
que proporcione un valor de z = 14. Lo mismo ocurre con z = 12.
m variables básicas y
2 variables no básicas.
Es decir, en una solución básica, como mı́nimo, debe haber dos variables nulas:
x2
10
6
x1
+2
5 x2
=1
x1 4
+2
4 x2
=1
2
3
x1
+2
x2
2 =6
−1 1 2 3 4 5 6 7 x1
x2
x 10
10
x9 x8
6
5 x7
5
2 x x6
x 2
x1 x3 x4
−1 1 2 3 4 5 6 7 x1
el eje de coordenadas,
cada una de las intersecciones de una restricción con cada uno de los
ejes y
cada una de las intersecciones de los difernetes pares de restricciones.
Por otro lado, en el caso de que todas las retricciones tengan variables de hol- Número de
gura, el problema tiene un número de soluciones básicas que se puede calcular soluciones
de dos maneras: básicas
De las soluciones básicas anteriores, algunas son factibles (en azul) y otras
son no factibles (en rojo), 9.5. Y de las factibles, aquella que tiene una función
objetivo mayor es la solución óptima del problema, 9.6.
x2
x 10
10
x9 x8
6
5 x7
5
2 x x6
x 2
x1 x3 x4
−1 1 2 3 4 5 6 7 x1
x2
10
5
Solución óptima
4
2x
1 +2
x2
3
−1 1 2 3 4 5 6 7 x1
que x NB .
x NB , no está sobre ninguna restricción, ni sobre ningún eje, con lo que tiene
cinco componentes no nulas (es decir, todas). Siguiendo el camino verde, nos
desplazamos primero a una solución no básica sobre el eje x1 (con una com-
ponente nula adicional: x2 ). Y, desde ella es posible llegar a x 3 , en la que hay
dos componentes nulas: x2 y h3 y tres no nulas: es una solución básica y mejor
que la de partida.
x2
x 10
10
x9 x8
6
5 x7
5
2 x x6
1 X NB
x2 x1 x3 x4
−1 1 2 3 4 5 6 7 x1
El método del Simplex, al cual se dedicó el capı́tulo 2, opera transitando de Lógica general
solución básica factible en solución básica factible hasta llegar a una que es
óptima. En la figura 9.8, en particular, se muestran dos posibles transiciones,
la primera entre las soluciones x 1 y x 5 y la segunda entre x 5 y x 7 , que es la
Capı́tulo 9. INTERPRETACIÓN GRÁFICA 99
solución óptima. Como se ha comentado antes, las solución básicas son los
vértices del polı́gono de la región de factibilidad.
x2
x 10
10
x9 x8
6
5 x7
4
2x
1 +2
x2
3
5
2 x x6
x 2
x1 x3 x4
−1 1 2 3 4 5 6 7 x1
Figura 9.8: Lógica general del método del Simplex en un problema de Progra-
mación Lineal
x2
x 10
10
x9 x8
6
5 x7
5
z= 2 x x6
2
z=
1 Δx2 = 1
z= 1
0
Δx1 = 1
x2 x3 x4
1
−1 x 1 2 3 4 5 6 7 x1
El cada iteración del método del Simplex, entra una variable nueva en la base Regla de salida
con un valor que hace que una de las que era básica, se haga cero. Por ejem- pB
plo, si a partir de x 1 , decidimos que la variable x2 deje de ser cero, podemos
acceder a tres nuevas soluciones básicas:
En el ejemplo anterior, las tres soluciones a las que se puede acceder desde
x1 son básicas, pero solo una es factible. La regla de salida del método del
Simplex garantiza que al entrar una nueva variable, el valor con el que esta
entra no hace ninguna de las variables negativas, por lo que siempre se accede
a una nueva solución básica factible.
x2
x 10
10
x9 x8
6
5 x7
5
2 x x6
x 2
x1 x3 x4
−1 1 2 3 4 5 6 7 x1
PROGRAMACIÓN PARAMÉTRICA
10.1. Introducción
En este capı́tulo se estudia el impacto que tienen estas variaciones, que tı́pica- Objetivo
mente dependen de un parámetro λ (aunque puede haber otros), y se estudian
la solución y la ecuación de la función objetivo para cada rango de λ en el que
las variables básicas son las mismas.
Procedimiento general:
x1 x2 x3 h1 a
-111/2 0 -1/2 0 -19/10 -2/5
x3 7/2 0 1/2 1 3/10 -1/5
x1 11/2 1 1/2 0 -1/10 2/5
A continuación vamos a realizar el análisis para c(λ) = λ 6 8 , con
0 ≤ λ ≤ ∞.
V B (λ) = c − c B B −1 A = c − c B p =
0 1/2 1 3/10
λ 6 8 0 − 8 λ = (10.2)
1 1/2 0 −1/10
0 4−λ 2 0 λ−2410
4−λ≤0
⇒ 4 ≤ λ ≤ 24 (10.3)
λ − 24 ≤ 0
T0 (λ) x1 x2 x3 h1
11λ 4−λ λ−24
−28 − 2 0 2 0 10
x3 7/2 0 1/2 1 3/10
x1 11/2 1 1/2 0 -1/10
TA = T0 (λ = 4) x1 x2 x3 h1
-50 0 0 0 -2
x3 7/2 0 1/2 1 3/10
x1 11/2 1 1/2 0 -1/10
TB = T1 (λ = 4) x1 x2 x3 h1
-50 0 0 0 -2
x2 7 0 1 2 3/5
x1 2 1 0 -1 -2/5
V B (λ) = c − c B B −1 A = c − c B p =
0 1 2 3/5
λ 6 8 0 − 6 λ = (10.4)
1 0 −1 −2/5
0 0 λ − 4 2λ−18 5
El criterio del Simplex de la tabla T2 nunca se anula para valores de λ tales que
λ ≤ 4.
Es decir, para cualquier valor de λ menor que 4, las variables básicas son x1
y x2 . Existe aquı́ una aparente contradicción por el hecho de que si c1 es muy
grande en valor absoluto y negativo, parece sensato pensar que x1 deberı́a
no ser una variable básica porque deteriora notablemente la función objetivo.
Por ejemplo, parace razonable pensar que si c1 = −1000, si z representa el
beneficio de un sistema real, estarı́amos perdiendo 1000 unidades monetarias,
con lo que parece intuitivo pensar que esta variable no deberı́a estar en la
solución final.
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 105
Es decir, el criterio del Simplex nos dice cómo se modifica la z cuando una
variable no básica entra en la base con valor 1. Dada la estructura de las res-
tricciones, hacer que cualquiera de las variables no básicas crezca hace que x1
crezca también, con lo que la solución a la que se llega es peor, ası́ que para
cualquier λ ≤ 4, las variables básicas de la solución óptima son x1 y x2 .
TC = T0 (λ = 24) x1 x2 x3 h1
−160 0 -10 0 0
x3 7/2 0 1/2 1 3/10
x1 11/2 1 1/2 0 -1/10
TD = T2 (λ = 24) x1 x2 x3 h1
−160 0 -10 0 0
h1 35/3 0 5/3 10/3 1
x1 20/3 1 2/3 1/3 0
V B (λ) = c − c B B −1 A = c − c B p =
0 5/3 10/3 1
λ 6 8 0 − 0 λ = (10.5)
1 2/3 1/3 0
0 6−2λ 3
24−λ
3 0
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 106
El criterio del Simplex no se hace positivo para ningún valor de λ tal que λ >
24.
En resumen:
T1 T0 T2
V B ≤ 0, V B ≤ 0,
B2 B
u (λ) u (λ) uB4 (λ)
λ
4 24
{x1 = 2, x2 = 7} {x1 = 11
, x3 = 7
} {x1 = 20
, h1 = 35
}
2 2 3 3
z = 42 + 2λ z = 28 + 11
λ z = 20
λ
2 3
z
300
250
20 λ
3
200 =
z
150
11 λ
+ 2
100 28
z=
50
z = 42 + 2λ
5 10 15 20 25 30 35 λ
Procedimiento general:
T0 x1 x2 x3 x4 h1 h2
-15 -2 -1 -1 0 0 -1/10
h1 45 5 -15 -5 0 1 -1/2
x4 5 5/3 5/3 1 1 0 1/30
T
b(λ) = 120 − λ 150 + λ
B −1 1 −1/2 120 − λ 45 − 3λ/2
u (λ) = B b(λ) = = (10.7)
0 1/30 150 + λ 5 + λ/30
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 108
T0 (λ) x1 x2 x3 x4 h1 h2
-15 -2 -1 -1 0 0 -1/10
h1 45 − 3λ/2 5 -15 -5 0 1 -1/2
x4 5 + λ/30 5/3 5/3 1 1 0 -1/30
Si λ = 30:
T0 (λ = 30) x1 x2 x3 x4 h1 h2
-18 -2 -1 -1 0 0 -1/10
h1 0 5 -15 -5 0 1 -1/2
x4 6 5/3 5/3 1 1 0 -1/30
T1 (λ = 30)
-18 -7/3 0 -2/3 0 -1/60 -1/60
x2 0 -1/3 1 1/3 0 -2/30 1/30
x4 6 20/9 0 4/9 1 1/9 -2/90
−1/60 1/30 120 − λ
uB (λ) = B −1 b(λ) = =
1/9 −2/90 150 + λ
(10.8)
(−30 + λ)/10
(900 − 12λ)/90
T1 (λ) x1 x2 x3 x4 h1 h2
-18 -7/3 0 -2/3 0 -1/60 -1/60
x2 (−30 + λ)/10 -1/3 1 1/3 0 -2/30 1/30
x4 (900 − 12λ)/90 20/9 0 4/9 1 1/9 -2/90
Si λ = 75:
T1 (λ = 75) x1 x2 x3 x4 h1 h2
-18 -7/3 0 -2/3 0 -1/60 -1/60
x2 9/2 -1/3 1 1/3 0 -2/30 1/30
x4 0 20/9 0 4/9 1 1/9 -2/90
T2 (λ = 75)
-18 -9 0 -2 -3 -2/5 0
x2 9/2 3 1 1 3/2 1/10 0
h2 0 -100 0 20 -45 -5 1
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 109
1/10 0 120 − λ (120 − λ)/10
uB (λ) = B −1 b(λ) = = (10.9)
−5 1 150 + λ 6λ − 450
T2 (λ) x1 x2 x3 x4 h1 h2
-18 -9 0 -2 -3 -2/5 0
x2 (120 − λ)/10 3 1 1 3/2 1/10 0
h2 6λ − 450 -100 0 20 -45 -5 1
En resumen:
T0 T1 T2
λ
-150 30 75 120
3 λ λ
{h1 = 45 − 2 λ, {x2 = −3 + 10 , {x2 = 12 − 10 ,
x4 = 5 +
λ
x4 = 10 −
2 h2 = −450 + 6λ}
30 } 15 λ}
z = 15 +
λ z = 18 z = 48 −
2
10 5λ
100z
80
60
40
20 z = 18 z=
1 λ 48
+ −
z = 15
10 2
5 λ
−20
x1 x2 x3 h1 h2
-40 0 -1 0 -1 0
x1 56/3 1 2 0 2/3 -1/3
x3 8/3 0 1 1 -1/3 2/3
V B (λ) = c − c B B −1 A = c − c B p B =
1 2 0 2/3 −1/3
2 4+λ 1 0 0 − 2 1 = (10.11)
0 1 1 −1/3 2/3
0 λ − 1 0 −1 0
B −1 2/3 −1/3 40 1 56 + 3λ
u (λ) = B b(λ) = = (10.12)
−1/3 2/3 24 − 3λ 3 8 − 6λ
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 111
VB ≤ 0 ⇒ λ ≤ 1 (10.13)
4
uB ≥ 0 ⇒ λ ≤ (10.14)
3
T0 (λ) x1 x2 x3 h1 h2
0 λ−1 0 -1 0
x1 (56 + 3λ)/3 1 2 0 2/3 -1/3
x3 (8 − 6λ)/3 0 1 1 -1/3 2/3
T0 (λ = 1)
-40 0 0 0 -1 0
x1 59/3 1 2 0 2/3 -1/3
x3 2/3 0 1 1 -1/3 2/3
T1 (λ = 1)
-40 0 0 0 -1 0
x1 55/3 1 0 -2 4/3 -5/3
x2 2/3 0 1 1 -1/3 2/3
V B (λ) = c − c B B −1 A = c − c B p B =
1 0 −2 4/3 −5/3
2 4+λ 1 0 0 − 2 4+λ =
0 1 1 −1/3 2/3
0 0 1 − λ (λ − 4)/3 (2 − 2λ)/3)
(10.15)
B −1 4/3 −5/3 40 1 40 + 15λ
u (λ) = B b(λ) = =
−1/3 2/3 24 − 3λ 3 8 − 6λ
(10.16)
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 112
VB ≤ 0 ⇒ 1 ≤ λ ≤ 4 (10.17)
4
uB ≥ 0 ⇒ −3/8λ ≤ (10.18)
3
Por lo tanto, para que las variables básicas x1 y x2 conduzcan a una solución
óptima y factible 1 ≤ λ ≤ 43 . El extremo inferior de este intervalo coincide, na-
turalmente, con el extremo superior del intervalo obtenido para las soluciones
básicas con x1 y x3 .
Con λ = 43 se obtiene una solución degenerada. Con λ > 43 se obtiene una solu-
ción básica no factible, por lo que deja de ser la solución óptima y factible del
problema. A continuación figuran las siguientes tres tablas: la correspondiente
a x1 y x2 como variables básicas, en función de λ, la anterior con λ = 43 y la
solución obtenida al aplicar Lemke a partir de la anterior.
T1 (λ) x1 x2 x3 h1 h2
0 0 1−λ (λ − 4)/3 (2 − 2λ)/3
x1 (40 + 15λ)/3 1 0 -2 4/3 -5/3
x2 (8 − 6λ)/3 0 1 1 -1/3 2/3
T1 (λ = 43 )
0 0 -1/3 -8/9 -2/9
x1 20 1 0 -2 4/3 -5/3
x2 0 0 1 1 -1/3 2/3
T2 (λ = 43 )
0 -8/3 -3 0 -2
x1 20 1 4 2 0 1
h1 0 0 -3 -3 1 -2
V B (λ) = c − c B B −1 A = c − c B p B =
1 4 2 0 1
2 4+λ 1 0 0 − 2 0 = (10.19)
0 −3 −3 1 −2
0 −4 + λ −3 0 −2
B −1 0 1 40 24 − 3λ
u (λ) = B b(λ) = = (10.20)
1 −2 24 − 3λ −8 + 6λ
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 113
VB ≤ 0 ⇒ λ ≤ 4 (10.21)
4
uB ≥ 0 ⇒ ≤λ≤8 (10.22)
3
Por lo tanto, para que las variables básicas x1 y h2 conduzcan a una solución
óptima y factible 43 ≤ λ ≤ 4. El extremo inferior de este intervalo coincide, na-
turalmente, con el extremo superior del intervalo obtenido para las soluciones
básicas con x1 y x2 .
Con λ = 4 se obtiene una solución degenerada. Con λ > 4 se obtiene una solu-
ción básica no óptima, por lo que deja de ser la solución óptima y factible del
problema. A continuación figuran las siguientes tres tablas: la correspondiente
a x1 y h1 como variables básicas, en función de λ, la anterior con λ = 4 y la
solución obtenida al aplicar el método del Simplex a patir de la anterior.
T2 (λ) x1 x2 x3 h1 h2
0 −4 + λ -3 0 -2
x1 24 − 3λ 1 4 2 0 1
h1 −8 + 6λ 0 -3 -3 1 -2
T2 (λ = 4)
0 0 -3 0 -2
x1 12 1 4 2 0 1
h1 16 0 -3 -3 1 -2
T3 (λ = 8)
0 0 -3 0 -2
x2 3 1/4 1 1/2 0 1/4
h1 25 3/4 0 -3/2 1 -5/4
V B (λ) = c − c B B −1 A = c − c B p B =
1/4 1 1/2 0 1/4
2 4+λ 1 0 0 − 4+λ 0 =
3/4 0 −3/2 1 −5/4
1 − λ4 0 −1 − λ2 0 −1 − λ4
(10.23)
Capı́tulo 10. PROGRAMACIÓN PARAMÉTRICA 114
0 1/4 40 1 24 − 3λ
uB (λ) = B −1 b(λ) = = (10.24)
1 −5/4 24 − 3λ 4 40 + 15λ
VB ≤ 0 ⇒ λ ≥ 4 (10.25)
uB ≥ 0 ⇒ λ ≤ 8 (10.26)
Por lo tanto, para que las variables básicas x2 y h1 conduzcan a una solución
óptima y factible 4 ≤ λ ≤ 8. El extremo inferior de este intervalo coincide, na-
turalmente, con el extremo superior del intervalo obtenido para las soluciones
básicas con x1 y x2 .
Con λ = 8 se obtiene una solución degenerada. Con λ > 8 se obtiene una solu-
ción básica no óptima, por lo que deja de ser la solución óptima y factible del
problema. A continuación figuran las siguientes dos tablas: la correspondiente
a x2 y h1 como variables básicas, en función de λ, la anterior con λ = 8. Se
observa que para la variable x2 no existen tasas de sustitución negativas, con
lo que si λ > 4 no existe solución factible, porque no es posible que x2 salga
de la base.
T3 (λ) x1 x2 x3 h1 h2
1 − λ4 0 −1 − λ2 0 −1 − λ4
x2 (24 − 3λ)/4 1/4 1 1/2 0 1/4
h1 (40 + 15λ/4 3/4 0 -3/2 1 -5/4
T3 (λ = 8)
-1 0 -5 0 -3
x2 0 1/4 1 1/2 0 1/4
h1 40 3/4 0 -3/2 1 -5/4
En resumen:
T0 T1 T2 T3
λ
0 1 4 4 8
3
{x1 = 56+3λ
, {x1 = 40+15λ
, {x1 = 24 − 3λ, {x1 = 6 − 3λ
3 3 4 ,
x3 = 8−6λ
} x2 = 8−6λ
} h1 = −8 + 6λ} h2 = 40+15λ
}
3 3 4
DUALIDAD
11.1. Introducción
Existen dos problemas de optimización lineal asociados cada uno de los cuales
proporciona información sobre el otro, de tal manera que la solución óptima de
uno de los problemas nos permite conocer una solución óptima del problema
asociado. A los dos problemas asociados se les denomina problemas duales y
su relación se va a tratar en este capı́tulo.
La dualidad es una parte clave en la Programación Lineal que permite que tenga ¿Por qué?
sentido toda la teorı́a correspondiente previa. ¿Por qué estudiar la dualidad?
Hay varias razones:
Una empresa internacional produce y vende estos dos tipos de supercompu- Ejemplo de
tadores: el modelo 1 y el modelo 2. En la elaboración de ambos tipos de equi- problema
pos hay que destacar dos procesos, el de ensamblado final y el de empaque- primal
tado (procesos P1 y P2). Esta empresa dispone mensualmente de 2000 horas
dedicadas al proceso de ensamblado y 1000 horas dedicadas al proceso de
empaquetado, además se sabe que los tiempos requeridos para realizar dichas
Capı́tulo 11. DUALIDAD 117
operaciones para cada uno de los tipos de supercomputadores son los que se
muestran en la tabla siguiente:
Horas requeridas
Proceso Modelo 1 Modelo 2 Horas disponibles
Montaje 6 4 2000
Embalaje 2 4 1000
La solución óptima de dicho problema es elaborar 250 unidades del tipo 1 y Solución óptima
125 unidades del modelo 2 con un beneficio de 175000 u.m. En la figura 11.1 del primal
se pueden ver las soluciones por las que se pasa hasta x ∗ = (250, 125). La
tabla correspondiente a la solución óptima es la siguiente:
Ahora podemos cambiar el enfoque sobre el problema planteado, nuestro Problema dual
propósito va a ser determinar los precios a los cuales esta empresa deberı́a asociado
valorar sus recursos (horas de trabajo de los dos procesos) de tal manera que
puedan determinar el mı́nimo valor total al cual estarı́a dispuesta a arrendar o
vender los recursos.
Capı́tulo 11. DUALIDAD 118
600
x2
z
500
400
300
200
(250, 125)
100
x1
100 200 300 400 500 600
Se consideran algunas condiciones. Por una parte, los precios pagados por el Restricciones del
alquiler serı́an no negativos, es decir, y1 ≥ 0 e y2 ≥ 0. Por otra parte, los pre- problema dual
cios y1 e y2 deben ser competitivos con las alternativas disponibles, es decir,
el beneficio que la empresa debe obtener por los recursos necesarios para ela-
borar un supercomputador al menos deben ser iguales a los que obtendrı́a al
utilizar dichos recursos en la elaboración del computador, esto es, para el mo-
delo 1 tendremos 6y1 + 2y2 ≥ 400 y para el modelo 2 queda 4y1 + 4y2 ≥ 600.
Con esto se garantiza la obtención de precios con los que al menos iguala el
beneficio obtenido al producir el mismo los equipos. El problema planteado
queda:
y2
s
500
400
300
200
(25, 125)
100
100 200 y1
La resolución de este problema proporciona un valor de 25 u.m. para cada Solución óptima
unidad del primer recurso (montaje) y un valor de 125 u.m. para cada unidad del problema
del segundo (embalaje), con un beneficio de 175000 u.m., igual al obtenido en dual
el planteamiento del primer problema. Este nuevo problema es el problema
dual del problema planteado originalmente.
max. z = cx
Ax ≤ b (11.3)
x≥0
min. s = yb min. s = bT y T
yA ≥ c (11.4) AT y T ≥ c T (11.5)
y ≥0 y ≥0
max. z = cx
Ax ≤ b (11.6)
x≥0
min. s = yb
yA ≥ c (11.7)
y ≥0
min u = t(−c T )
t(−AT ) ≥ −bT (11.9)
t≥0
Capı́tulo 11. DUALIDAD 121
max (−u) = ct T
At T ≤ b (11.10)
T
t ≥0
Con lo cual, los vectores x y t T y los valores de z y u son iguales. Se comprueba El dual del dual
que, en efecto, el problema dual asociado a un problema dual coincide con el es el primal
problema primal inicial.
De la propia definición de problema primal y problema dual asociado se dedu- Relaciones entre
cen unas primeras relaciones entre ambos problemas: ambos
problemas
una variable del problema primal genera una restricción en el problema
dual;
una restricción del problema primal genera una variable en el problema
dual;
una restricción de desigualdad en el problema primal genera una variable
no negativa en el problema dual.
es equivalente a :
y3 = y3+ − y3−
y3 será libre de signo siempre que y3+ y y3− sean no negativas y, además, no
puedan estar ambas en la solución del problema. En dicho caso:
−1
VyB+ = b3 − bB Bdual (a31 , a32 , a33 , a34 )T
3
−1
VyB− = −b3 + bB Bdual (−a31 , −a32 , −a33 , −a34 )T
3
es decir, VyB+ = V B y3− lo que implica que si VyB+ > 0 ⇒ VyB− < 0 y que si
3 3 3
VyB+ < 0 ⇒ V B y3− > 0.
3
Cuando una de las variables pertenece a la solución, por ejemplo y3∗ , el crite-
rio del Simplex de ambas variables tiene un valor de V B y3+ = 0 y V B y3− = 0
pero al analizar el vector de tasas de sustitución se comprueba que Py3+ =
(0, ..., 1, ..., 0)T y P y3− = (0, ..., −1, ..., 0)T por lo cual no es posible sustituir y3+
por y3− sin que la solución deje de ser factible.
El valor de la función objetivo para cualquier solución factible del problema pri-
mal es una cota inferior del valor de la función objetivo para cualquier solución
factible del problema dual.
Capı́tulo 11. DUALIDAD 124
Es decir: z0 ≤ s 0
En efecto, se parte de las dos soluciones factibles de los dos problemas aso-
ciados primal y dual x 0 e y 0 para las cuales el valor de cada función objetivo
es:
z0 = cx 0 s0 = y 0b
Por otra parte, al ser y 0 solución del problema dual, se cumple que y 0 AT ≥ c.
Al postmultiplicar por x 0 la expresión anterior, como x 0 es factible, se cumple
que:
y 0 Ax 0 ≥ cx 0
cx 0 ≤ y 0 Ax 0 ≤ y 0 b
es decir:
z0 = cx 0 ≤ y 0 b = s 0
luego:
z0 ≤ s 0
s 0 dual
z0 ≤ s 0
z0 primal
Figura 11.3: z0 ≤ s 0
En efecto:
VxB = c − c B B −1 A ≤ 0
por lo que:
c − c B B −1 A ≤ 0
cx h − c B B −1 I ≤ 0
Además, z∗ = cx ∗ = c B B −1 b = π B b = y ∗ b = s ∗ .
Por lo tanto, podemos afirmar que z no puede tener un valor mayor y s
no puede tener un valor menor y ambos coinciden.
En los otros tres ejemplos se pueden observar las relaciones entre ambos en
las situaciones de no acotación y no factibilidad.
x2 y2
z s
4 4
3 3
2 2
1 Solución 1
óptima Solución óptima
1 2 3 4 x1 1 2 3 4 y1
x2 y2
z 5 s
5
4
4
3
3
2
2
1
1
−1 1 2 3 4 5 y1
1 2 3 4 5 x1 −1
x2 y2
z s
5 5
4 4
3 3
2 2
1 1
1 2 3 4 5 x1 1 2 3 4 5 y1
x2 z y2 s
5 5
4 4
3 3
2 2
1 1
1 2 3 4 5 x1 1 2 3 4 5 y1
cx ∗ = y ∗ b
cx ∗ − y ∗ Ax ∗ = y ∗ b − y ∗ Ax ∗
o lo que es lo mismo:
(c − y ∗ A)x ∗ = y ∗ (b − Ax ∗ )
En efecto:
1. (c ∗ − y ∗ A)x ∗ = 0
- como x ∗ es la solución óptima del problema primal x ∗ ≥ 0
- como y ∗ es la solución óptima del problema dual
y ∗ A ≥ c ⇒ c − y ∗ A ≤ 0
Ax ∗ ≤ b ⇒ b − Ax ∗ ≥ 0
Por lo cual:
1. (c − y ∗ A)x ∗ = 0
2. y ∗ (b − Ax ∗ ) = 0
Capı́tulo 11. DUALIDAD 130
Además ,
cj − y ∗ Aj ≤ 0
transformado en igualdad,
cj − y ∗ Aj + yjh = 0
luego
yjh = −(cj − y ∗ Aj ) = −(cj − π B Aj ) = −VxB∗
j
que es mayor que cero ya que el criterio del Simplex de una variable no
básica en la solución óptima del problema es negativo.
Si xj∗ > 0, es decir xj pertenece a la solución óptima del problema primal,
entonces cj − y ∗ Aj = 0, es decir la restricción que genera la variable
xj en el problema dual se cumple como una igualdad y, por lo tanto,
la variable de holgura correspondiente no forma parte de la solución
óptima del problema, ya que:
cj − y ∗ Aj ≤ 0 ⇒ cj − y ∗ Aj + yjh = 0
y como:
cj − y ∗ Aj = 0 ⇒ yjh = 0
(2) y ∗ (b − Ax ∗ ) = 0.
Se puede obtener el mismo resultado anterior con las variables del dual y las
restricciones (por lo tanto las variables de holgura) del primal.
z(x) = cx 1 x 1 + cx 2 x 2 + · · · + cx n x n = y 1 b1 + y 2 + · · · + y m bm = s(y)
z(x̃) = cx̃1 x̃1 + cx̃2 x̃2 + · · · + cx̃n x̃n = ỹ1 (b1 + Δb1 ) + ỹ2 + · · · + ỹm bm =
Dado un primal (de máximos) diremos que una base del problema primal (no
necesariamente factible):
c − c B B −1 A ≤ 0
Se puede apreciar que dicha definición es equivalente a decir que una base
es factible dual si c B B −1 constituye una solución factible para el problema
dual. Por ejemplo, si llamamos y = c B B −1 (Teorema fundamental) tenemos
que c − c B B −1 A = c − yA ≤ 0, que es equivalente a la expresión que define las
restricciones funcionales del problema dual.
El algoritmo Simplex dual trabaja con soluciones básicas factibles duales que,
por medio de operaciones apropiadas, finalizarán (si es posible) en una solu-
ción que además serı́a factible primal. Mientras el Simplex trabaja con solu-
ciones que no cumplen el criterio de optimalidad y poco a poco se mejoraban
hasta conseguir la optimalidad, en el Simplex dual se trabaja con soluciones
primales no factibles en las que poco a poco se “mejorará” la factibilidad has-
ta alcanzarla (realmente lo que se irá mejorando serı́a las soluciones del dual
y = c B B −1 ).
1. Construcción de una solución básica primal que sea básica factible dual
(óptimo del primal).
2. Si una solución es factible primal entonces dicha solución serı́a óptima.
Capı́tulo 11. DUALIDAD 133
s.a.:
xij = Oi ∀i ∈ O (11.11)
j∈D
xij = Dj ∀j ∈ D
i∈
xij ≥ 0 ∀j ∈ D, ∀i ∈ O
s.a.:
(11.12)
ui + vj ≤ cij ∀i ∈ O, ∀j ∈ D
ui libre de signo ∀i ∈ O
vj libre de signo ∀j ∈ D
Capı́tulo 11. DUALIDAD 134
11.8. Ejercicios
En esta sección se incluyen dos ejercicios sobre dualidad, en los que princi-
palmente se obtiene el problema dual a partir del primal, se halla su solución
óptima y se analiza la información obtenida.
11.8.1. Ejercicio 1
Se pide:
1. Como y1 ≠ 0, x1h = 0.
2. Como y2 ≠ 0, x2h = 0.
3. Como y2h ≠ 0, x2 = 0.
4. Como y3h ≠ 0, x3 = 0.
Capı́tulo 11. DUALIDAD 135
11.8.2. Ejercicio 2
Se pide:
12.1. Introducción
Existe una gran variedad de problemas reales que se tienen que formular y
resolver utilizando variables enteras, por ejemplo: programación de horarios
de trenes o de tripulaciones en una compañı́a aérea, problemas de programa-
ción de la producción, de cálculo de rutas, etc. El número de aviones que una
empresa produce en un año no puede ser 20,12, al igual que el número de
vagones de un convoy del metro no puede ser 2,5 (o van 2 o van 3). De igual
forma, una planta se construye (1) o no (0). Es decir, en ocasiones las variables
enteras aparecen por la propia naturaleza de la decisión.
En otras ocasiones, las variables enteras son necesarias para poder modelar
ciertas situaciones que surgen de forma “natural”. Por ejemplo, imaginemos
tres restricciones:
R1 : 3x1 + x2 + x3 ≤ 10
R2 : 2x1 + 3x2 ≤ 8
R3 : x1 + 4x2 + x3 ≤ 12
Si queremos conseguir que sólo una de las tres se tenga que cumplir no actuan-
do las otras dos; una manera de hacerlo serı́a creando tres variables binarias
(α1 , α2 y α3 ), modificando las tres restricciones anteriores y creando una nue-
va restricción:
R1 : 3x1 + x2 + x3 ≤ 10 + M(1 − α1 )
R2 : 2x1 + 3x2 ≤ 8 + M(1 − α2 )
R3 : x1 + 4x2 + x3 ≤ 12 + M(1 − α3 )
Rnueva : α1 + α2 + α3 = 1
Capı́tulo 12. PROGRAMACIÓN ENTERA. FUNDAMENTOS 138
max.{cx : Ax ≤ b, x ≥ 0}
Si sólo alguna (no todas) de las variables tienen que ser enteras, entonces tene-
mos un problema de Programación Lineal Entera Mixto (Mixed Integer Problem,
MIP).
Si todas las variables tienen que ser enteras, entonces tenemos un problema de
Programación Lineal Puro (Integer Programming, IP). Por ejemplo, xi ∈ Z+ ∀i,
siendo Z+ el conjunto de enteros no negativos.
Dado que los problemas enteros se parecen bastante a los lineales, no sorpren-
de que tanto la teorı́a como la práctica de la Programación Lineal sea funda-
mental para comprender y resolver problemas enteros.
Primero, las soluciones obtenidas con los métodos aprendidos para resolver
problemas de Programación Lineal (Simplex, etc.) no sirven, por la necesidad
de que determinadas variables sean siempre enteras (nº de vagones, abrir o no
una planta, etc.).
Una de las primeras ideas que nos viene a la mente es la del redondeo: resolver El redondeo
el problema como si fuera lineal y luego redondear el valor de las variables.
Pero el redondeo no es aplicable. La solución entera obtenida al redondear una
solución con valores reales puede que sea:
Se puede ver fácilmente con el siguiente ejemplo sencillo (figura 12.1). Dado
este problema:
x2
z
4
1
Solución óptima PL
1 2 3 4 x1
Luego hay que buscar otros métodos distintos a los aprendidos hasta ahora.
x2 z
4 Solución óptima PL
1 2 3 4 5 x1
max. z = x1 + x2
s.a.:
10x1 − 8x2 ≤ 13 (12.2)
2x1 − 2x2 ≥ 1
x1 , x2 ∈ Z+
12.3.1. Optimalidad
z = max{c(x) : x ∈ X ⊆ Zn
+}
Capı́tulo 12. PROGRAMACIÓN ENTERA. FUNDAMENTOS 141
¿Cómo se puede probar que una solución x ∗ es óptima? O dicho de otra forma,
serı́a muy interesante encontrar algunas condiciones que nos garanticen la
optimalidad y ası́ dejar de buscar la solución óptima en un problema entero.
En la PLE no podemos utilizar el vector de criterios del Simplex como criterio
de optimalidad.
Una solución a esta pregunta es utilizando las cotas, como veremos en el si-
guiente apartado.
12.3.2. Cotas
Prácticamente esto significa que cualquier algoritmo que encuentre una se-
cuencia decreciente
z1 ≥ z2 ≥ · · · ≥ zs ≥ z
z1 ≤ z2 ≤ · · · ≤ zt ≥ z
de cotas inferiores serı́a muy interesante y ese algoritmo se podrı́a parar cuan-
do
zs − zt ≤
Cualquier solución factible x 0 ∈ X es una cota inferior z = c(x 0 ) ≤ z∗ . Esta es Cotas inferio-
la única forma de encontrar cotas inferiores: encontrando soluciones factibles. res/primales
En este caso las cotas factibles hablan del valor de la z que ya se tiene; es decir,
que como poco la función objetivo va a tener ese valor. Las cotas inferiores
hablan de realismo (lo que hay).
Capı́tulo 12. PROGRAMACIÓN ENTERA. FUNDAMENTOS 142
Z1
Z2 cotas superiores
Z3
z∗
Z1
Z2 cotas inferiores
Z3
La tarea de encontrar cotas superiores es muy distinta de la anterior. Una de las Cotas superio-
formas de hallar las cotas superiores es mediante “relajaciones”. La idea que res/duales
hay detrás de las relajaciones es reemplazar un problema entero “difı́cil” de
maximizar (como normalmente formulamos los problemas) por otro problema
más sencillo cuya función objetivo z es mayor o igual que la del problema
original.
Para que el problema relajado cumpla esta propiedad hay dos posibilidades:
X ⊆ T, y
f (x) ≥ c(x) para todo x ∈ X.
max. z = 4x1 − x2
s.a.:
7x1 − 2x2 ≤ 14
(12.3)
x2 ≤ 3
2x1 − 2x2 ≤ 3
2
x ∈ Z+
Como se puede ver en la figura 12.4 el punto (1, 1) es una solución factible,
luego tenemos una cota inferior z ≥ 3. Para obtener una cota superior pode-
∗
mos recurrir a la relajación lineal. La solución óptima es xRL = ( 20
7 , 3) con
función objetivo zLP = 59
7 . Como el valor de la función objetivo del problema
entero tiene que ser entero (en este caso), podemos redondear y obtener z ≤ 8.
La solución óptima del problema entero xP∗E , que es el punto (2, 1), tiene un
valor de 7, comprendido entre 3 y 8 (cota inferior y superior respectivamente).
Las relajaciones no sólo permiten obtener cotas superiores, sino que también Relación cotas
sirven para probar la optimalidad. Si la relajación (RL) es no factible, el proble- duales -
ma original entero (IP) también. Si al resolver la relajación lineal (RP) resulta factibilidad y
que cumple las condiciones de integralidad del problema entero (IP) resulta optimalidad del
que también es su solución óptima. problema
entero
Capı́tulo 12. PROGRAMACIÓN ENTERA. FUNDAMENTOS 144
z
x2
5
4
Solución
óptima PL
3
x1
1
Solución
óptima PLE
x
1 2 3 4 5 1
∗ ∗
tiene como solución óptima xRL = (1, 1, 0, 0). Como xRL es entera, es también
∗ ∗
solución óptima del problema entero; xRL = xP E .
Existen más tipos de relajaciones que permiten hallar cotas superiores. Entre Otras
ellas, por ejemplo, las relajaciones combinatorias que son especı́ficas para de- relajaciones
terminados problemas (TSP, Knapsack, etc.); y las relajaciones lagrangianas, lineales
que son mucho más generales y que se basan en relajar restricciones (quitar-
las), pero su cumplimiento afecta a la función objetivo con un coste.
Vista esta introducción previa, ahora viene la pregunta de qué estrategia uti-
lizar para obtener la solución óptima de un problema de PLE o, lo que es lo
mismo, cómo conseguir la mejor pasa de un bizcocho de con pasas.
Si además se utilizan los conceptos relacionados con las cotas, que he-
mos estudiado recientemente, se conseguirá que el estudio de cada sub-
problema por separado no se tenga que realizar por completo (mediante
la enumeración explı́cita de todas las soluciones).
Planos de corte. En este enfoque se intenta añadir restricciones nuevas
al problema, de forma que al añadir una de ellas la solución óptima de
la relajación lineal sea entera; solución óptima del problema entero.
La idea que hay detrás del enfoque divide y vencerás es aplicable a problemas
de diversa ı́ndole, en concreto también en problemas de Programación Lineal
Entera. Desde esa mirada más amplia se puede pensar en un problema:
z = max{cx : x ∈ S}
x1 = 0 x1 = 1
S0 (0) S1 (1)
x2 = 0 x2 = 1 x2 = 0 x2 = 1
x2 = 0 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x2 = 1
S000 (0, 0, 0) S001 (0, 0, 1) S010 (0, 1, 0) S011 (0, 1, 1) S100 (1, 0, 0) S101 (1, 0, 1) S110 (1, 1, 0) S111 (1, 1, 1)
Por una parte, la figura 13.2 representa las soluciones enteras del problema
inicial en 3D. Se observa que las sucesivas divisiones sobre el árbol de la figura
13.1 no son más que inserciones de planos sobre el espacio de soluciones.
Por ejemplo, la primera ramificación sobre x1 dividı́a el conjunto S en dos:
S0 = {x ∈ S : x1 = 0} y S1 = {x ∈ S : x1 = 1}. Eso es igual que añadir el plano
x1 = 1 sobre el espacio de soluciones.
x3
x3 = 1
x2 = 1
x1 = 1
x2
x1
(0,0,0) (1,0,0)
(0,0,1)
(1,0,1)
(0,1,0) (1,1,0)
(0,1,1)
(1,1,1)
MAX. MAX.
S P
S1 S2 P1 P2
.
Vamos a ver ahora tres casos hipotéticos para ver cómo podemos utilizar con
sentido la información relativa a las cotas de un problema. ¿Qué se puede
decir sobre la solución óptima con la infamación relativa a las cotas y qué
conjuntos (subproblemas) necesitan seguir examinándose para encontrar la
solución óptima?
Poda por optimalidad. En la figura 13.5 se puede ver una descomposición del Poda por
conjunto S en dos subconjuntos S1 y S2 y las cotas superiores e inferiores de optimalidad
los distintos problemas.
MAX. 27 MAX. 27
S S
13 13
20 25 20 25
S0 S1 S0 S1
20 15 . 20 15
27 z
z2 z
25
20 z1 ∗
z 1 z1
15
z2 z
13
z
Poda por acotamiento. En la figura 13.7 vemos de nuevo la descomposición Poda por
del conjunto S en dos subconjuntos S1 y S2 y las cotas superiores e inferiores acotamiento
de los distintos problemas.
MAX. 27 MAX. 26
S S
13 21
\
18 26 26
S1 S2 S1 S2
20 21 . 21
27 z
z1 z
26
21
z2
z1 z
20
18
z2
13
z
No poda posible. En la figura 13.9 está descompuesto de nuevo el conjunto S No poda posible
en dos subconjuntos S1 y S2 con diferentes cotas superiores e inferiores.
MAX. 40 MAX. 37
S S
13
24 37 24 37
S1 S2 S1 S2
13 . 13
40 z
37
z2 z
z1
24
13
z1 z
Basados en estos tres ejemplos se pueden enumerar las tres razones que per- Razones para
miten podar alguna rama del árbol y con ello enumerar de forma implı́cita un podar
gran número de soluciones:
Búsqueda de cotas
División en subproblemas
En esta sección se presenta un ejercicio resuelto con Branch and Bound, que
ha sido cogido del libro Integer Programming [?].
max. z = 4x1 − x2
s.a.:
7x1 − 2x2 ≤ 14
(13.1)
x2 ≤ 3
2x1 − 2x2 ≤ 3
x ∈ Z2+
Acotamiento. Para obtener una primera cota superior, añadimos las holguras
correspondientes (h1 , h2 y h3 ) y resolvemos la relajación lineal de este proble-
ma (quitando las restricciones de integrabilidad).
x1 x2 h1 h2 h3
zRL -59/7 0 0 -4/7 -1/7 0
x1 20/7 1 0 1/7 2/7 0
x2 3 0 1 0 1 0
h3 23/7 0 0 -2/7 10/7 1
59
De aquı́ obtenemos una cota superior z = 7 , y una solución que no es entera
( 20
7 , 3).
¿Hay alguna forma de encontrar una solución factible? Pues aparente-
mente, no. Luego no tenemos ninguna cota inferior aún, z = −∞.
Capı́tulo 13. PROGRAMACIÓN ENTERA. BRANCH AND BOUND 154
59
MAX. 7
x1 ≤ 2 x1 ≥ 3
S1 S2
59
MAX. 7
x1 ≤ 2 x1 ≥ 3
15
2
S1 S2
x2 ≤ 0 x2 ≥ 1
S11 S12
x1 x2 h1 h2 h3 h4
z1RL 59/7 0 0 -4/7 -1/7 0 0
x1 20/7 1 0 1/7 2/7 0 0
x2 3 0 1 0 1 0 0
h3 23/7 0 0 -2/7 10/7 1 0
h4 -6/7 0 0 -1/7 -2/7 0 1
x1 x2 h1 h2 h3 h4
z1RL 15/2 0 0 0 0 -1/2 -3
x1 2 1 0 0 0 0 1
x2 1/2 0 1 0 0 -1/2 1
h1 1 0 0 1 0 -1 -5/7
h2 5/2 0 0 0 1 1/2 6
15
con z1RL = 2 y (x 11 , x 12 ) = (2, 12 ).
x1 x2 h1 h2 h3 h5
z1RL 59/7 0 0 -4/7 -1/7 0 0
x1 20/7 1 0 1/7 2/7 0 0
x2 3 0 1 0 1 0 0
h3 23/7 0 0 -2/7 10/7 1 0
h5 -1/7 0 0 1/7 2/7 0 1
Selección de nodo. La lista de nodos activos contiene ahora a S11 y S12 . Arbi-
trariamente se elige S12 y se elimina de la lista.
Se guarda esta solución y este nodo se poda por optimalidad, ya no hace falta
seguir estudiándolo.
59
MAX. 7 7
S
7
x1 ≤ 2 x1 ≥ 3
/
15
7 2
S1 S2 No factible
x2 ≤ 0 x2 ≥ 1
\ /
6 7 7
3 , 0)
S11 (2 S12 (2,1)
x2 z
5
x1 ≤ 2 x1 ≥ 3
4
∗
xRL
3
2
∗
x2 ≥ 1 x12
1
x1∗
x2 ≤ 0 ∗ 2
1 x11 3 4 5 x1
Como resumen del ejemplo estudiado, el método de Branch and Bound, según
Dankin, implica:
Tras la presentación del algoritmo de Branch and Bound, quedan aspectos so-
bre los que pensar, que son los que se muestran en esta sección.
El árbol no se guarda como tal, sólo los nodos activos (por estudiar).
¿Qué información de cada nodo se debe guardar? Poca y repetir los cálcu-
los (volver a hallar las tablas de las soluciones óptimas de algunos nodos
aún no podados o acotado; o guardar todas estas tablas a costa de nece-
sitar más memoria del ordenador.
Hay una información mı́nima que hay que guardar de un nodo; sus cotas,
cuando se conozcan, de qué nodo son hijos, etc.
Generalización del concepto de cotas El significado de la cota superior, por cotas primales y
ejemplo, es muy distinto en función de si el problema es de máximos (fun- duales
ción objetivo de la relajación lineal) o de mı́nimos (función objetivo de una
solución factible). Por eso, para generalizar el concepto de cotas es preferible
independizar el significado del tipo de problema. De esta manera, se define:
Método para buscar cotas: la forma de acotar los nodos es utilizando las re-
lajaciones lineas. Éstas acotan por arriba (duales) siempre por ser relajación;
y por debajo (primales) cuando la solución óptima de la relajación lineal es
entera.
Al azar.
La variable aún no entera con mayor parte fraccional, casi entera.
Ramificar las variables con mayor contribución al beneficio.
MAX. 40 41.25
S 3.75, 2.25
40
x1 ≤ 3 x1 ≥ 4
39 39 40 41
S1 (3, 3) S2 (4, 1.8)
39 40
x2 ≤ 1 x2 ≥ 2
40 40.55
S21 (4.44, 1) S22 No factible
40
x1 ≤ 4 x1 ≥ 5
37 37 40 40
S211 (4, 1) S212 (5, 0)
37 40
x2
9 z
Problema S:
7
max. z = 8x1 + 5x2
6
s.a.:
5
x1 + x2 ≤ 6
4
9x1 + 5x2 ≤ 45
x1 , x2 ∈ Z+ 3
x0∗
2
1 2 3 4 5 x1
Problema S
Subproblema S1 : Subproblema S2 :
max. z = 8x1 + 5x2 max. z = 8x1 + 5x2
s.a.: s.a.:
x1 + x2 ≤ 6 x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45 9x1 + 5x2 ≤ 45
x1 ≤ 3 x1 ≥ 4
x1 , x2 ∈ Z+ x1 , x2 ∈ Z+
Capı́tulo 13. PROGRAMACIÓN ENTERA. BRANCH AND BOUND 163
x2 x2
9 z 9 z
8 8
7 7
6 6
5 5
4 4
x1∗
3 3
2 2 x2∗
1 1
1 2 3 4 5 x1 1 2 3 4 5 x1
Subproblema S1 Subproblema S2
x2 x2
9 z 9 z
8 8
7 7
6 6
5 5
4 4
3 3
2 2
∗
x21
1 1
1 2 3 4 5 x1 1 2 3 4 5 x1
x2 x2
9 z 9 z
8 8
7 7
6 6
5 5
4 4
3 3
2 2
∗
x211
1 1
1 2 3 4 5 x1 1 2 3 4 5 x1
13.8. GAP
En esta sección se introduce el concepto de gap, que indica cuán cerca puede
estar una solución entera del óptimo en función de los lejos que está de su
cota dual. Si no hay soluciones enteras no se puede calcular el gap.
La diferencia entre las cotas duales y primales nos da una idea del gap, como
se representa en la figura 13.16 en un problema de máximos.
z
Cota
dual
≈ Continua
gap
a saltos
Cota
primal
t/ iteración
zP − zD
gap = (13.3)
zP
z
Cota
dual
Cota horas
primal
t/ iteración
z
Cota
dual
Cota
horas
primal
t/ iteración
Conseguir acercar rápidamente las cotas y lograr un buen valor del gap
(figura 13.19).
Capı́tulo 13. PROGRAMACIÓN ENTERA. BRANCH AND BOUND 168
z
Cota
dual
Cota
primal
t/ iteración
zP − zD 135335 − 131277,86
gap = = = 0,03
zP 135335
Capı́tulo 14
14.1. Introducción
Las técnicas basadas en planos de corte son una alternativa a los métodos
basados en Branch and Bound.
Volviendo a la analogı́a con un bizcocho con pasas. Las pasas son las solu-
ciones enteras y el bizcocho en sı́ la zona factible de la relajación lineal. Se
pueden hacer cortes con un cuchillo de forma que nunca se eliminen las pasas
del bizcocho de tal forma que tras algún corte con el cuchillo aparece una pasa
(solución entera) en la parte exterior del bizcocho, la miga (y que serı́a óptimo).
En este capı́tulo nos vamos a centrar en un método de corte de los muchos que
hay en la literatura, más concretamente en una de las variantes del algoritmo
de Gomory. Esta variante nos sirve para resolver problemas de Programación
Lineal en los que todas las variables han de ser enteras.
Capı́tulo 14. PROGRAMACIÓN ENTERA. PLANOS DE CORTE 170
max. z = cx
s.a.:
(14.1)
Ax ≤ b
n
x ∈ Z+
max. z = cx
s.a.:
(14.2)
Ax ≤ b
x≥0
x2 z
X0∗ ∈ F0 Xe∗ ∈ F1
7
4 x0∗
S<0 xe∗ x1∗ Corte
3
S≥0
1 2 3 4 5 6 x1
Evidentemente, la solución óptima x1∗ del nuevo problema lineal P1 será tal
que cx1∗ ≥ cxe∗ puesto que xe∗ ⊆ Fe ⊆ F1 y, al mismo tiempo, cx0∗ ≥ cx1∗
puesto que x1∗ ⊆ F1 ⊆ F0 luego:
y, por lo tanto:
x1∗ es pues una solución aproximada por exceso del problema Pe igual o más
próxima que x0∗ a la solución verdadera, xe∗ , y cx1∗ representa una cota supe-
rior igual o más estricta.
Capı́tulo 14. PROGRAMACIÓN ENTERA. PLANOS DE CORTE 172
Dado un problema de PL continua, una solución del mismo y por ello tene-
mos una base B, a la cual corresponden m variables siendo n las variables no
básicas que se anulan para la solución básica correspondiente a B.
m+n
m B A’
Colocando las columnas de las variables básicas en primer lugar (lo que exi-
girá sencillamente un cambio de notación de los ı́ndices), podemos escribir las
restricciones funcionales del problema P0 en la forma
A · x = (B|A )x = b
B −1 (B|A ) · x = B −1 · b
(I|B −1 · A ) · x = B −1 · b = uB
I · x B = uB − B −1 A · x NB
xi = uBi − αik xk
k∈NB
haciendo B −1 A = [aik ]
xi = uBi
. Esta expresión también permite observar cómo varı́a el valor de una variable
básica si se hace positiva una variable no báisca (en función del valor de la tasa
de sustitución, el valor de las aik ).
Como se puede ver en ambas bases, se ha presentado, para cada base, la expre-
sión de las variables básicas en función de las no básicas. Por ejemplo para la
base B2 se tiene la expresión de h1 y x1 en función de las variables no básicas
(x2 y h2 ).
Continuando con la analogı́a del bizcocho, este algoritmo supondrı́a hacer cor-
tes con el cuchillo de forma tal que en uno de los cortes tocarı́amos con el
cuchillo (o dejarı́amos al exterior) una pasa (y esa pasa serı́a la mejor).
Una gran ventaja de este algoritmo es que, dado cualquier problema que cum-
pla unas hipótesis concretas, se puede aplicar sin más.
Por hipótesis, uBi es positiva pero no es entera puesto que xiB =uBi no es entera.
siendo:
siendo:
entero
S > −fi0 y como fi0 < 1 entonces −fi0 > −1 y S > 0
S≥0
Fe ∈ F1 siendo F1 = (S ≥ 0) ∩ F0
max. z = cx
s.a.:
Ax = b
(14.8)
−fi0 + fik xk ≥ 0
k∈NB
x≥0
max. z = cx
s.a.:
Ax = b
(14.9)
hck − fik xk = −fi0
k∈NB
x ≥ 0 , hc ≥ 0
Por otra parte, hemos visto que S tenı́a que ser entero para cualquier solución
factible de Pe , luego, si añadimos a las restricciones de 14.10 la condición de
que x ∈ Z+ n
tenemos un nuevo programa entero equivalente al Pe de partida.
Si la nueva restricción
hck − fik xk = −fi0
k∈NB
max. z = cx
s.a.:
B −1
−1
(14.10)
Ix + (B |A ) · xk = B · b k ∈ NB
x≥0
hc = −fi0 < 0
Capı́tulo 14. PROGRAMACIÓN ENTERA. PLANOS DE CORTE 177
Con todo, los planos de corte han supuesto una base teórica para estudios
posteriores en los que se combinan junto con técnicas de descomposición (por
ejemplo: Branch and Cut).
Cada vez que se añade un corte, se añade una nueva columna (la correspon-
diente a la nueva variable de holgura) y una nueva fila. Si todas las filas y
columnas se mantuvieran siempre el tamaño de la tabla podrı́a ser muy gran-
de después de muchos cortes. Por lo tanto, en la medida que se añaden nuevos
cortes hay que desechar los viejos tan pronto que sea posible. Pero ¿es posible?
¿se puede desechar algún corte? Veamos.
Pero cuando en alguna iteración hck vuelve a entrar en la base, el valor de esta
variable se hace positivo y la solución ya no está en el plano de corte hck = 0;
el corte se vuelve inactivo. A partir de este momento las tasas de sustitución
de hck son todas nulas salvo en la fila correspondiente a hck . Es decir el corte
puede eliminarse y la fila y variable correspondiente también.
x2
3
x1
1 2 3 4
x2
3
x1
1 2 3 4
Lo deseable serı́a que todos los puntos extremos del poliedro que se usa como
formulación fuesen enteros.
14.8.2. Definiciones
≤ λπ y λπ0 ≤ π
π 0,
x2
5 z
1 2 3 4 5 x1
Ejemplo: región factible
max. z = x1 + x2
x2
s.a.: 5 z
x1 + x2 ≥ 2
x2 ≤ 4
x2 ≥ 1 4
x
x1 ≥ 0
1 +
2
x1 − x2 ≤ 1 x
2 ≤
9
x1 ≤ 3 3
x1 ≤ 3
x1 + 2x2 ≤ 9
2
x1
1
x2 ≤ 4
2 ≤
+
x2
x
1 −
≥
x1 , x2 ≥ 0
2
x
1 x2 ≥ 1
x1 , x2 ∈ Z+
1 2 3 4 5 x1
Ejemplo: envolvente convexa
x2
5 z
xe∗
3
1 2 3 4 5 x1
Ejemplo: solución óptima entera
x1 x2 h1 h2
-39/5 0 0 -4/5 -3/5
x2 7/5 0 1 2/5 -1/5
x1 9/5 1 0 -1/5 3/5
x2 z
x0∗
1 2 3 x1
Tanto en la tabla como en la figura 14.5, se observa que esta solución óptima
no es solución del problema entero. Vamos a aplicar el algoritmo de Gomory
con la variable x1 (la de mayor fi0 ).
4 4 3
S=− + h1 + h2
5 5 5
Capı́tulo 14. PROGRAMACIÓN ENTERA. PLANOS DE CORTE 183
Si S = 0, entonces:
4 3 4
h1 + h2 =
5 5 5
x1 x2 h1 h2 hc1
-39/5 0 0 -4/5 -3/5 0
x2 1 0 1 0 -1/2 1/2
x1 2 1 0 0 3/4 -1/4
h1 1 0 0 1 3/4 -5/4
Se obtiene ahora una solución óptima factible y con las variables x1 y x2 ente-
ras.
x2
z
x0∗
1 xe∗
Corte
1 2 3 x1
Nota: tras añadir la nueva fila correspondiente al corte se podrı́a haber pivota-
do por 35 . En ese caso se habrı́a llegado a otra solución que es óptima también
(óptima múltiple, al ser el corte paralelo a la z, pero no entera).
5 z
4
max. z = 2x1 + 4x2
s.a.: 3 x0∗
6x1 + 2x2 ≤ 39
2
2x2 + 2x2 ≤ 15
2x2 ≤ 5 1
x1 , x2 ∈ Z+
x
1 2 3 4 5 6
−1
Al ser x0∗ continua, tenemos que introducir un corte. Definimos el primer plano
de corte como se indica a la izquierda y lo incluimos en el gráfico como se
muestra a la derecha:
Capı́tulo 14. PROGRAMACIÓN ENTERA. PLANOS DE CORTE 185
5 z
3 x0∗
1 1 2
− + h3 ≥ 0
2 2
1
x
1 2 3 4 5 6
−1
x1 x2 h1 h2 h3 hc1
-20 0 0 0 -1 -1 0
h1 4 0 0 1 -3 2 0
x1 5 1 0 0 1/2 -1/2 0
x2 5/2 0 1 0 0 1/2 0
hc1 -1/2 0 0 0 0 -1/2 1
-19 0 0 0 -1 0 -2
h1 2 0 0 1 -3 0 4
x1 11/2 1 0 0 1/2 0 -1
x2 2 0 1 0 0 0 1
h3 1 0 0 0 0 1 -2
x2 ≤ 2
Capı́tulo 14. PROGRAMACIÓN ENTERA. PLANOS DE CORTE 186
5 z
2x2 + 2x2 ≤ 15
2
2x2 ≤ 5 x1∗
x2 ≤ 2 1
x1 , x2 ∈ Z+
x
1 2 3 4 5 6
−1
La solución óptima obtenida, x1∗ , también es continua, ası́ que tenemos que
introducir un nuevo corte.
5 z
3 x0∗
2
x1∗
1
1 1
− + h2 ≥ 0
2 2 x
1 2 3 4 5 6
−1
x1 + x2 ≤ 7
x1 x2 h1 h2 h3 hc1 hc2
-19 0 0 0 -1 0 -2 0
h1 2 0 0 1 -3 0 4 0
x1 11/2 1 0 0 1/2 0 -1 0
x2 2 0 1 0 0 0 1 0
h3 1 0 0 0 0 1 -2 0
hc2 -1/2 0 0 0 -1/2 0 0 1
-18 0 0 0 0 0 -2 -2
h1 5 0 0 1 0 0 4 -6
x1 5 1 0 0 0 0 -1 1
x2 2 0 1 0 0 0 1 0
h3 1 0 0 0 0 1 -2 0
h2 1 0 0 0 1 0 0 -2
s.a.:
4
6x1 + 2x2 ≤ 39
2x2 + 2x2 ≤ 15 3 x0∗
2x2 ≤ 5 x1∗
2
x2 ≤ 2 xe∗
x1 + x2 ≤ 7 1
x1 , x2 ∈ Z+
x
1 2 3 4 5 6
−1
OPTIMIZACIÓN EN RED
15.1. Introducción
15.2. Terminologı́a
Se suele hablar de red o de grafo que está formado por nodos y arcos, o vérti-
ces y aristas o nudos y ramas. En el ejemplo de la figura 15.1 el grafo está
compuesto por el conjunto de nodos N = {1, 2, 3, 4, 5} y el conjunto de arcos
A = {(1, 2); (1, 3); (1, 4); (3, 4); (3, 5); (5, 4)}.
Capı́tulo 15. OPTIMIZACIÓN EN RED 190
1 2
3 4
1 2
3 4
2
1
3 4 3 1 4 1
2 3 4
2
En la matriz de incidencia las filas son los nodos del grafo y las columnas las
aristas. Los elementos de la matriz, bi,j , se definen como:
1 si el nodo i pertenece a la arista j
bij =
0 otro caso
Capı́tulo 15. OPTIMIZACIÓN EN RED 192
1 1
1 2 1 2
2 2
4 5 4 5
3
3 4 3 4
3
Dados los dos grafos de la figura 15.4 sus matrices de incidencia son respecti-
vamente:
⎡ ⎤ ⎡ ⎤
1 1 0 1 0 −1 −1 0 1 0
⎢ ⎥ ⎢ ⎥
⎢ 1 0 0 0 1⎥ ⎢1 0 0 0 −1⎥
⎢ ⎥ ⎢ ⎥
⎢ 0 0 1 1 0⎥ ⎢0 0 1 −1 0⎥
⎣ ⎦ ⎣ ⎦
0 1 1 0 1 y 0 1 −1 0 1
En la matriz de adyacencia las filas son los nodos del grafo y las columnas
también. Los elementos de la matriz de adyacencia, ai,j , se definen como:
1 si existe arco del nodo i alj
aij =
0 otro caso
Dados los dos grafos de la figura anterior 15.4 sus matrices de adyacencia son
respectivamente:
⎡ ⎤ ⎡ ⎤
0 1 1 1 0 1 0 1
⎢ ⎥ ⎢ ⎥
⎢1 0 0 1⎥ ⎢0 0 0 1⎥
⎢ ⎥ ⎢ ⎥
⎢1 0 0 1⎥ ⎢1 0 0 0⎥
⎣ ⎦ ⎣ ⎦
1 1 1 0 y 0 0 1 0
Capı́tulo 15. OPTIMIZACIÓN EN RED 193
Aplicaciones:
Cálculo de rutas más corta entre dos estaciones del metro (el plano del
metro es un grafo)
Cálculo de camino más corto con un navegador de un coche o con Google
Maps
Enrutamiento por el camino más corto de paquetes de datos entre servi-
dores
Hipótesis:
red conexa no dirigida
cada arco no dirigido lleva asociada una distancia no negativa.
Objetivo: encontrar las distancia (coste, tiempo, etc.) mı́nima entre el origen
(uno de los nodos) y el resto de los nodos del grafo.
Se basa en:
ir etiquetando los nodos, primero de forma temporal (calculando la me-
jor distancia hasta el momento desde el nodo inicial) y después de forma
permanente (cuando ya se conoce la mejor distancia acumulada).
que si se conoce el camino mı́nimo entre dos nodos, esta información
se puede reutilizar para calcular el camino mı́nimo desde el origen hasta
ese nodo del que conocemos ya el camino mı́nimo.
2
B E
3 1 3 3
2
A C F
4 4 5
2
3
D G
En el paso 3, la clave del algoritmo está en que seleccionado el nodo con eti-
queta temporal con distancia acumulada más pequeña como siguiente nodo
etiquetado de forma permanente esa distancia es la mı́nima para llegar desde
el nodo inicial; pues si fuera otra (viniendo desde uno de los nodos aún tempo-
rales) esa distancia será siempre mayor pues ya lo es y además hay que añadir
la distancia de los arcos necesarios.
Ahora se conocen los caminos más cortos desde A al resto de los nodos. Por
ejemplo para ir de A a E el camino más corto es pasando por ABE y la distancia
es de 5. Para ir de A a F el camino más corto es vı́a ABCF con una distancia de
6.
2 2
B E B E
3 {A,3} 1 3 3 3 [A,3] 1 3 3
2 2
A C F A C F
[-,0] 4 4 5 [-,0] 4 4 5
2 2
3 3
D G D G
{B,4} {B,4}
a) expansión desde el nodo A b) etiquetado permanente del nodo B
2 2
B E B E
2 2
A C F A C F
{A,4} {A,4}
a) expansión desde el nodo B b) etiquetado permanente del nodo C
2 2
B E {B,5}, {C,7} B E {B,5}
3 [A,3] 1 3 3 3 [A,3] 1 3 3
2 2
A C F A C F
2 2
B E {B,5} B E [B,5]
3 [A,3] 1 3 3 3 [A,3] 1 3 3
2 2
A C F A C F
Si se quiere calcular los caminos más cortos de todos los nodos a todos los
nodos, se utilizarı́a el algoritmo de Floyd-Warshall.
Capı́tulo 15. OPTIMIZACIÓN EN RED 197
2 2
B E [B,5] B E [B,5]
3 [A,3] 1 3 3 3 [A,3] 1 3 3
2 2
A C F A C F
2
B E [B,5]
3 [A,3] 1 3 3
2
A C F
[A,4] [D,7]
Aplicaciones:
redes de telecomunicaciones
redes de distribución
redes de transporte
Hipótesis:
Objetivo: encontrar la cadena de longitud mı́nima que recorre todos los nodos
sin ciclos (es decir, el árbol generador de peso mı́nimo).
Métodos:
Prim
Kurskal
Capı́tulo 15. OPTIMIZACIÓN EN RED 198
Se puede probar que la elección del nodo inicial no influye en la función objeti-
vo; sı́, en el caso de soluciones múltiples puede ser que haya dos o más árboles
generadores óptimos distintos.
2 2
B E B E
3 1 3 3 3 1 3 3
2 2
A C F A C F
4 4 5 4 4 5
2 2
3 3
D G D G
Figura 15.12: Algoritmo de Prim - It. 1 Figura 15.13: Algoritmo de Prim - It. 2
2 2
B E B E
3 1 3 3 3 1 3 3
2 2
A C F A C F
4 4 5 4 4 5
2 2
3 3
D G D G
Figura 15.14: Algoritmo de Prim - It. 3 Figura 15.15: Algoritmo de Prim - It. 4
2 2
B E B E
3 1 3 3 3 1 3 3
2 2
A C F A C F
4 4 5 4 4 5
2 2
3 3
D G D G
Figura 15.16: Algoritmo de Prim - It. 5 Figura 15.17: Algoritmo de Prim - It. 6
2
B E
3 1 3 3
2
A C F
4 4 5
2
3
D G
En este caso se busca utilizar los arcos más cortos (de menor distancia).
input : grafo no dirigido con distancias positivas en cada arco
output: árbol generador de peso mı́nimo
1 while no estén unidos todos los nodos mediante un árbol generador do
2 añadir al árbol el arco con menor distancia no añadido aún de forma
que no se generen ciclos.;
3 end
Algoritmo 4: Algoritmo de Kurskal
2
B E
3 1 3 3
2
A C F
4 4 5
2
3
D G
Aplicaciones:
Hipótesis:
Métodos:
la Programación Lineal
algoritmo de los caminos de aumento (Ford-Fulkerson)
Según esto, el objetivo del problema del flujo máximo se puede redefinir como:
determinar el flujo compatible que transporta la mayor cantidad de flujo de la
fuente al destino.
Capacidad residual de un arco. Los arcos tienen una capacidad inicial (nomi-
nal), en la medida que se mete flujo por un arco, la capacidad que le queda
disponible (residual) va disminuyendo hasta el lı́mite en el que el arco no tiene
capacidad residual. La suma de la capacidad residual y el flujo es la capacidad
nominal.
Red residual. Indica el flujo sobrante de cada arco para asignarle flujo adicio-
nal sin violar su capacidad. Es la red cuya capacidad es la capacidad residual
de cada arco.
Capı́tulo 15. OPTIMIZACIÓN EN RED 202
Capacidad de un corte. Suma de las capacidades de los arcos que unen ambas
subredes (cruzan el corte) en el sentido del O al D.
Flujo de un corte. Suma de los flujos que atraviesan el corte cada uno en su
sentido.
Teorema de máximo flujo - mı́nimo corte. Para una red conexa dirigida con
un origen y un destino, el valor del flujo máximo es igual al valor mı́nimo de
las capacidades de cualquier corte de la red inicial. En el óptimo no existen
caminos de aumento en la red residual y se obtiene un corte con capacidad de
corte cero para la red residual.
El flujo máximo del origen al destino tiene una cotas claras: la capacidad inicial
de todos los arcos de salida del origen y la capacidad inicial de los arcos que
van al nodo destino. Esto son cotas superiores (nunca se podrá llevar más
flujo), pero muchas veces lo que ocurre dentro del grafo puede hacer que no
se alcancen esas cotas, siendo el flujo máximo menor.
Tenemos el siguiente grafo compuesto por 5 nodos y unos arcos dirigidos, Ejemplo -
cada uno de ellos con una capacidad máxima de flujo que puede pasar (ver Problema de
figura 15.20). flujo máximo
resuelto con el
B algoritmo de
Ford-Fulkerson
1 2
3
1 1
A C E
2 2
Parece que como mucho sólo se pueden sacar del origen 4 unidades de flujo
(1+1+2) y como mucho puede llegar al destino 5 unidades de flujo. Lógicamen-
te como mucho llegarán 4 unidades, pero ¿estamos seguros de que si salen las
4 unidades del origen hay capacidad suficiente en el grafo para que lleguen al
destino?
B
0
1 3
0 0
0 0 2
A C E
0 1
1
2
0
2
D
B
1
0 3
1 0
0 0 1
A C E → ABE 1
0 1
1
2
0
2
D
B
1
0 3
1 0
0 0 1 → ABE 1
A C E
2 1 → ADE 2
1
0
2
0
D
B
1
0 3
1 0
→ ABE 1
1 1 1
A C E → ADE 2
2 0
0 → ACE 1
0
2
0
D
B
1
0 3
1 0
→ ABE 1
1 1 1
A C E → ADE 2
2 0
0 → ACE 1
0
Hipótesis:
Variables:
Parámetros:
cij , coste unitario de cada flujo que va por el arco que sale de i y va a j
uij , capacidad del arco de i a j
bi , flujo generador del nodo. Un nodo puede ser generador (bi > 0),
consumidor (bi < 0) o de transbordo (bi = 0)
Objetivo: Calcular los flujos entre los nodos generadores y consumidores que
supongan un coste menor.
min. z = cij xij
i,j
s.a. :
xij − xki = bi ∀i
j k
Propiedad Si bi y uij son enteros, todas las variables básicas en cada solu-
ción básica son enteras (por ser la matriz de coeficientes técnicos una matriz
unimodular).
Ciclo euleriano: ciclo que pasa por todos los nodos y atraviesa exactamente
una vez cada arista.
Camino euleriano: camino entre dos nodos que pasa por todos los vértices y
atraviesa exactamente una vez cada arista.
Teorema de Euler: Dado un grafo conexo, posee un ciclo euleriano sı́ y solo
si todos sus vértices son de grado par (número de aristas que inciden en el
vértice).
Un grafo tiene un camino euleriano sı́ y solo si es conexo y sólo tiene dos
vértices de orden impar (que serı́an en principio y fin del camino).
E E
B C B C B C
A D A D A D
Si el grafo tiene un ciclo euleriano es evidente que ese ciclo será la solución.
Si no lo tiene (algún vértice de orden impar), alguna de las aristas han de ser
recorridas más de una vez.
15.7.1.1. Ejemplo
Se quiere hallar el ciclo de longitud mı́nima que pasa por todas las aristas del
grafo de la figura 15.27:
Capı́tulo 15. OPTIMIZACIÓN EN RED 210
70
70
50
B F
50 50 60 60
50
A D H
50 70 120 70
70
C G
50
B F
50
60
A D H
C G
Figura 15.28: Ejemplo: arcos extra que se añaden para tener ciclo
Capı́tulo 15. OPTIMIZACIÓN EN RED 211
TRANSPORTE Y ASIGNACIÓN
16.1.1. Introducción
Dados:
s.a.:
xij ≤ Oi ∀i ∈ O (16.1)
j∈D
xij ≥ Dj ∀j ∈ D
i∈O
xij ≥ 0 ∀j ∈ D, ∀i ∈ O
s.a.:
xij = Oi ∀i ∈ O (16.2)
j∈D
xij = Dj ∀j ∈ D
i∈
xij ≥ 0 ∀j ∈ D, ∀i ∈ O
De acuerdo con:
max. z = cx
s.a.:
(16.4)
Ax = b
x≥0
donde 1 representa un vector fila con tantos elementos como destinos, todos
ellos con valor 1 y 0 representa un vector fila con tantos elementos como
destinos, todos ellos con valor 0.
Destinos
destino D1 ... destino Dj ... destino DJ Ofertas
c11 c1j cIJ
origen O1 x11 ... x1j ... x1J O1
donde cij es el coste reducido asociado al a variable xij , que se explicará más
adelante. El coste reducido hace las veces del vector de criterios del Simplex
(V B ) en problemas de minimizar.
16.2.2. Propiedades
s.a.:
Oi Dj j∈D Dj (16.9)
xij = = Oi = Oi ∀i ∈ O
j∈D j∈D j∈D D j j∈D Dj
Oi Dj Oi
xij = = Dj i∈O = Dj ∀j ∈ D
i∈O i∈O i∈O Oi i∈O Oi
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 217
1. Stepping-stone
2. MODI
16.4. El procedimiento
Hay distintos métodos para hallar una solución inicial de partida, como el
rincón noroeste (NO), el mı́nimo coste y Vogel, entre otros. Estas requieren
diferente esfuerzo y ofrecen distinta calidad de la solución de partida.
16.4.1.1. Rincón NO
Con este procedimiento se llega con prácticamente el mismo esfuerzo que con
el caso de la regla del rincón noroeste a una solución básica factible de me-
nor coste, a veces mucho más ventajosa. De hecho, la diferencia entre ambas
soluciones de partida es tanto mayor:
cuanto mayor sea la ventaja de elegir casillas con costes bajos, es decir
cuanto mayores sean las diferencias entre costes;
cuanto más consigamos aprovechar dicha ventaja utilizando justamente
las casillas más interesantes.
Precisamente estas consideraciones son la base del método de Vogel que per-
mite hallar fácilmente una solución básica factible de coste en general aún
menor.
16.4.1.3. Vogel
El procedimiento de Vogel para hallar una solución básica inicial factible cons-
ta pues de las siguientes etapas:
Para calcular los costes reducidos cij hay dos métodos: Stepping-stone y MODI.
16.4.2.1. Stepping-stone
Para saber si una solución básica factible es óptima, parece natural fijarnos en
cómo cambiarı́a el coste si una unidad se suministrara utilizando una casilla
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 221
Sea (i, j) esta casilla. Para no vulnerar las restricciones relativas a las ofertas Oi
y a las demandas Dj , tendremos que introducir modificaciones en el circuito
cerrado que se pone de manifiesto al entrar en juego la nueva casilla. El cambio
resultante en los costes será evidente una vez hechos los reajustes necesarios
para restablecer el cumplimiento de las restricciones.
16.4.2.2. MODI
Oi − xij = 0 ∀i ∈ O
j∈D
(16.10)
Dj − xij = 0 ∀j ∈ D
i∈
A su vez, a la función objetivo se le pueden sumar los términos nulos, que son Se definen ui y
los primeros miembros de las dos expresiones anteriores premultiplicados por vi
los valores ui y vi . Posteriormente, se puede operar:
⎛ ⎞ ⎛ ⎞
z= cij xij = cij xij − ui ⎝Oi − xij ⎠ − vj ⎝Dj − xij ⎠ =
ij ij i j j i
= ui Oi + vj Dj + xij (cij − ui − vj )
i j ij
(16.11)
Por lo tanto, la función objetivo se puede expresar como la suma de dos térmi-
B
nos, uno constante y otro que depende de xij . Si se denota con xij a las va-
−B
riables básicas y xij a las no básicas, el término variable se puede reformular
como:
B −B
xij (cij − ui − vj ) = xij (cij − ui − vj ) + xij (cij − ui − vj )
(16.12)
ij ij ij
Con ayuda de estos pasaremos a calcular los valores de cij − ui –vj para to-
das las casillas no básicas. Si todos son positivos, la solución es óptima. En
caso contrario, podremos elegir, como hemos visto, la variable que vamos a
introducir.
Una vez calculados los costes reducidos por cualquiera de los dos métodos,
establecemos la regla de entrada: de entre todas las variables con costes redu-
cidos negativos, elegimos aquella cuyo valor absoluto del coste reducido sea
mayor, es decir, el más negativo.
La variable básica que habrá que suprimir será, al igual que en el método del
Simplex, la primera que se anule al ir aumentando el valor de la nueva variable
introducida. En este caso, como ya hemos dicho, los valores que varı́an son
los de las casillas del ciclo cerrado que aparece al introducir la nueva variable,
siendo evidente en cada caso cual de ellos es el primero en anularse, y qué va-
lores resultan entonces para la nueva variable y para las restantes modificadas.
Por tanto, para conocer qué variable sale de la base, hacemos una “pasarela”
completa.
I
J
Oi = Dj
i=1 j=1
I
J
Oi > Dj
i=1 j=1
Sin embargo, si los costes de origen son lineales, el problema puede también
reducirse fácilmente a un problema equilibrado. Sean αi los costes fijos y βi
los costes marginales del origen Oi , los costes de producción totales en dicho
origen i serán:
J
CTi = αi + βi xij
j=1
I
I
J
I
J
z
= αi + βi xij + cij xij
i=1 i=1 j=1 i=1 j=1
I
luego, sumando y restando i=1 βi Oi a la función z
, y agrupando convenien-
temente los términos, queda de la siguiente forma equivalente:
I
I
I
J
I
J
z
= αi + βi Oi + βi ( xij − Oi ) + cij xij
i=1 i=1 i=1 j=1 i=1 j=1
J
Ahora bien, para cada fábrica de origen Oi , Oi − j=1 xij = xid , donde xid∗
representa la capacidad no utilizada del origen i ∈ O, que corresponderı́a
al destino ficticio. Como las dos primeras sumas son constantes, el proble-
ma queda reducido a un problema equilibrado en el cual βi es el coste del
transporte (evidentemente ficticio) desde cada fábrica hasta el destino ficticio
introducido para equilibrar los flujos.
I
J
Oi < Dj
i=1 j=1
No hay capacidad suficiente para satisfacer todas las necesidades; del mismo
modo que en el caso anterior, introducimos ahora un origen ficticio o∗ que
satisfaga el exceso de demanda. Teniendo en cuenta este origen ficticio, o∗ , el
problema se redefine sobre un conjunto O∗ = O∪{o∗ }. En este caso, la variable
xo∗ j representa la demanda no atendida del destino j ∈ D, que corresponderı́a
al origen ficticio.
Ahora bien, el coste de una necesidad insatisfecha raras veces es nulo, ya que
puede implicar la pérdida de clientes, un retraso costoso, el empleo de produc-
tos sustitutivos menos adecuados, etc. En el caso de que los costes de carencia
sean los mismos para todos los destinos, pueden repartirse arbitrariamente
entre ellos. Para ello, se busca, como siempre, el mı́nimo coste de transporte,
y se admite que el suministro desde el origen ficticio hasta cualquier destino
se hace con un coste de transporte nulo.
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 226
En este caso lo que resulta esencial es tener bien presente la distinción entre
una variable básica que aparezca con el valor particular cero, y una variable
no básica. Si, al introducir una nueva actividad en una base, y aplicar la regla
de supresión, se anulan simultáneamente varias variables, podremos designar
arbitrariamente una de ellas como no básica en la nueva solución, y considerar
que la otra o las otras siguen perteneciendo a la nueva base pero con valor cero.
Para facilitar su identificación (puesto que normalmente las variables básicas
se reconocen por tener valores positivos) podemos suponer que no son riguro-
samente nulas, sino que tienen un valor muy pequeño , que haremos figurar
en todos los pasos sucesivos en que siga siendo necesario, como si se tratara
de una cantidad realmente asignada a la casilla correspondiente.
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 227
s.a.:
(16.14)
ui + vj ≤ cij ∀i ∈ O, ∀j ∈ D
ui libre de signo ∀i ∈ O
vj libre de signo ∀j ∈ D
s.a.:
+ − + − (16.15)
(u − u ) + (v − v ) ≤ cij ∀i ∈ O, ∀j ∈ D
u+ −
i , ui libre de signo ∀i ∈ O
vi+ , vi− libre de signo ∀j ∈ D
s.a.:
xij ≤ Oi ∀i ∈ O
j∈D
xij ≥ Oi ∀i ∈ O (16.16)
j∈D
xij ≤ Dj ∀j ∈ D
i∈
xij ≥ Dj ∀j ∈ D
i∈
xij ≥ 0 ∀j ∈ D, ∀i ∈ O
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 228
Por otro lado, los criterios del Simplex, V B , de un problema P y del dual de
ese mismo problema, formulado en términos de máximo son iguales, pero
cambiados de signo.
h
ij = −Vij
B B
= Vij
max min
B
(16.17)
cij − ui − vj = Vij
min
16.8.1. Introducción
s.a.:
xij ≤ 1 ∀i ∈ O (16.18)
j∈D
xij ≥ 1 ∀j ∈ D
i∈O
xij ≥ 0 ∀j ∈ D, ∀i ∈ O
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 229
16.8.2. Representación
D1 D2 ... Dj ... DJ
O1 c11 c12 ... c1j ... c1J
O2 c21 c22 ... c2j ... c2J
... ... ... ... ... ... ...
Oi ci1 ci2 ... cij ... ciJ
... ... ... ... ... ... ...
OI cI1 cI2 ... cIj ... cIJ
D1 D2 D3 D4
O1 4 2 3 1
O2 5 2 6 3
O3 1 8 9 2
O4 10 1 6 4
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 230
D1 D2 D3 D4
O1 ×
O2 ×
O3 ×
O4 ×
16.8.3. Propiedades
En una solución del problema, para cada fila i, solo un valor xij = 1.
En una solución del problema, para cada columna j, solo un valor xij = 1.
Si se suma una constante k a todos los costes de una fila o de una co-
lumna, el problema resultante alcanza la solución óptima para la misma
asignación que el problema original. En efecto, por ejemplo, si cambian
todos los costes del origen i∗ ci
∗ j = ci∗ j +k ∀j, la nueva función objetivo
es:
z
= cij xij = cij xi,j + (ci
∗ j + k)xi,j
i,j i≠i∗ ,j j
= ci,j xij + ci
∗ j xij + kxij =
(16.19)
i≠i∗ ,j i=i∗ ,j i=i∗ ,j
ci,j xij + k xij = z + k
i≠i,j i=i∗ ,j
D1 D2 D3 D4
O1 2 0 1 3
O2 0 2 1 1
O3 2 5 7 0
O4 3 1 0 3
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 231
D1 D2 D3 D4
O1 1 4 3 1
O2 2 1 6 7
O3 3 2 6 6
O4 1 2 3 7
D1 D2 D3 D4
O1 0 3 2 0
O2 1 0 5 6
O3 1 0 4 4
O4 0 1 2 6
D1 D2 D3 D4
O1 0 3 0 0
O2 1 0 3 6
O3 1 0 2 4
O4 0 1 0 6
D1 D2 D3 D4
O1 0 4 0 0
O2 0 0 2 5
O3 0 0 1 3
O4 0 2 0 6
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 232
Una compañı́a tiene tres almacenes y en una determinada semana cuatro clien-
tes solicitan el suministro de determinadas cantidades que la compañı́a tiene
en sus almacenes. Las existencias de almacén (Oi ), las demandas (Di ) y los cos-
tes de transporte de cada uno de los almacenes (Oi ) a cada uno de los clientes
(Dj ) se muestran en la tabla:
D1 D2 D3 D4 Oi
O1 20 11 3 6 5
O2 5 9 10 2 10
O3 18 7 4 1 15
Dj 3 3 12 12
Resolución
D1 D2 D3 D4 Oi
20 11 3 6
O1 3 2 5 (=3+2)
5 9 10 2
O2 1 9 10 (=1+9)
18 7 4 1
O3 3 12 15 (=3+12)
Empecemos, por ejemplo con la variable x21 . Desde su casilla puedo trazar un
circuito cerrado que pasa por las casillas x11 , x12 , x22 y acaba de nuevo en x21
(ver siguiente tabla).
D1 D2 D3 D4 Oi
20 11 3 6
O1 3 → → 2 5
↑ (-) ↓ (+)
5 ↑ 9 ↓ 10 2
O2 ← ← 1 9 10
(+) (-)
18 7 4 1
O3 3 12 15
Dj 3 3 12 12
Podemos recoger estos resultados en la misma tabla que antes, indicando las
casillas que contienen las variables básicas en gris, y las casillas correspondien-
tes a las variables no básicas en blanco con la variación de Z que se obtendrı́a
si dicha variable tomara el valor 1.
D1 D2 D3 D4 Oi
20 11 3 6
O1 3 2 -9 -3 5
5 9 10 2
O2 -13 1 9 -6 10
18 7 4 1
O3 +6 +4 3 12 15
Dj 3 3 12 12
Nos interesará introducir la variable x21 , que es la que reduce el valor del coste
de transporte en mayor medida. Sólo se puede introducir en una unidad para
que la solución continúe siendo óptima.
D1 D2 D3 D4 Oi
20 11 3 6
O1 2 2 5
5 9 10 2
O2 1 9 10
18 7 4 1
O3 3 12 15
Dj 3 3 12 12
Capı́tulo 16. TRANSPORTE Y ASIGNACIÓN 235
Ahora tenemos que ver si esta nueva solución es óptima o no. Vamos a dibujar
el circuito cerrado de una variable básica, por ejemplo, el circuito de la variable
x14 .
D1 D2 D3 D4 Oi
20 11 3 6
O1 3 ← 2 ← 5
↓ (-) ↑ (+)
5 ↓ 9 10 2
O2 1 → → 9 10
(+) ↓ (-)
18 7 4 ↓ 1 ↑
O3 3 → → 12 15
(+) (-)
Dj 3 3 12 12
D1 D2 D3 D4 Oi
20 11 3 6
O1 3 2 5
5 9 10 2
O2 3 7 10
18 7 4 1
O3 3 12 15
Dj 3 3 12 12
Hasta ahora, para calcular si la solución era óptima o, si no lo era, hallar qué va-
riable no básica introducir a la solución, hemos usado el método de los circui-
tos cerrados. Este método se puede aplicar siempre que se quiera en cualquier
problema que presente esta estructura, pero se convierte en muy farragoso
cuando el problema tiene una dimensión considerable al complicarse mucho el
cálculo de los circuitos cerrados correspondientes. Vamos a seguir resolviendo
este problema pero el resto de los pasos los vamos a calcular con otro método
más sistemático, el método de “las ui y las vj ” o de ”los multiplicadores”.
Según se ha visto en la teorı́a, para las variables básicas se cumplen las siguien-
tes ecuaciones:
c12 = u1 + v2 = 11
c13 = u1 + v3 = 3
c21 = u2 + v1 = 5
c23 = u2 + v3 = 10
c33 = u3 + v3 = 4
c34 = u3 + v4 = 1
u1 = 0, u2 = 7, u3 = 1, v1 = −2, v2 = 11, v3 = 3, v4 = 0
D1 D2 D3 D4 Oi ui
20 11 3 6
O1 22 3 → → 2 6 5 0
↑ ↓
5 9 ↑ 10 ↓ 2
O2 3 -9 ← ← 7 -5 10 7
18 7 4 1
O3 19 -5 3 12 15 1
Dj 3 3 12 12
vj -2 11 3 0
Según esto, tenemos que introducir la variable x22, el circuito existente para
equilibrar la solución es:
D1 D2 D3 D4 Oi ui
20 11 3 6
O1 5 5
5 9 10 2
O2 3 3 4 10
18 7 4 1
O3 3 12 15
Dj 3 3 12 12
vj
u1 = 0, u2 = 7, u3 = 1, v1 = −2, v2 = 2, v3 = 3, v4 = 0
D1 D2 D3 D4 Oi ui
20 11 3 6
O1 22 9 5 6 5 0
5 9 10 2
O2 3 3 4 ← ← -5 10 7
↓ ↑
18 7 4 ↓ 1 ↑
O3 19 4 3 → → 12 15 1
Dj 3 3 12 12
vj -2 2 3 0
D1 D2 D3 D4 Oi ui
20 11 3 6
O1 17 4 5 6 5 0
5 9 10 2
O2 3 3 → 5 → 4 10 2
↑ ↓
18 7 ↑ 4 1 ↓
O3 14 -1 ← 7 ← 8 15 1
Dj 3 3 12 12
vj 3 7 3 0
D1 D2 D3 D4 Oi ui
20 11 3 6
O1 17 5 5 6 5 0
5 9 10 2
O2 3 1 5 7 10 2
18 7 4 1
O3 14 3 7 5 15 1
Dj 3 3 12 12
vj 3 6 3 0
Z = c13 x13 + c21 x21 + c24 x24 + c32 x32 + c33 x33 + c34 x34 = 98
2. Método de Vogel
D1 D2 D3 D4 Oi Máx. dif. i
20 11 3 6
O1 5 3
5 9 10 2
O2 10 3
18 7 4 1
O3 15 3
Dj 3 3 12 12
Máx. dif. j 13 2 1 1
↑
Estas operaciones junto con las nuevas diferencias entre los dos menores cos-
tes de cada fila y cada columna se recogen en la siguiente tabla.
D1 D2 D3 D4 Oi Máx. dif. i
20 11 3 6
O1 5 3
5 9 10 2
O2 3 7 7←
18 7 4 1
O3 15 3
Dj 3 3 12 12
Máx. dif. j 2 1 1
D1 D2 D3 D4 Oi Máx. dif. i
20 11 3 6
O1 5 3
5 9 10 2
O2 3 7 0
18 7 4 1
O3 15 3
Dj 0 3 12 5
Máx. dif. j 2 1 5
↑
D1 D2 D3 D4 Oi Máx. dif. i
20 11 3 6
O1 5 3←
5 9 10 2
O2 3 7 0
18 7 4 1
O3 5 10 3
Dj 0 3 12 0
Máx. dif. j 2 1
Ahora, de entre las nuevas diferencias, elegimos arbitrariamente una de las dos
mayores, por ejemplo, la fila nº1. Le asignamos la máxima cantidad posible, 5.
D1 D2 D3 D4 Oi Máx. dif. i
20 11 3 6
O1 5 0
5 9 10 2
O2 3 7 0
18 7 4 1
O3 5 10 3
Dj 0 3 7 0
Máx. dif. j 2 6
↑
D1 D2 D3 D4 Oi Máx. dif. i
20 11 3 6
O1 5 0
5 9 10 2
O2 3 7 0
18 7 4 1
O3 7 5 3 7
Dj 0 3 0 0
Máx. dif. j 7
↑
D1 D2 D3 D4
20 11 3 6
O1 5
5 9 10 2
O2 3 7
18 7 4 1
O3 3 7 5