´N P ROGRAMACI O L INEAL Noviembre 2012

Universidad Polit´ ecnica de Madrid Alvaro Garc´ıa S´ anchez Miguel Ortega Mier

´Indice general

´Indice general 1.

2.

2

´ A LA PROGRAMACION ´ LINEAL. TEOREMA INTRODUCCION DAMENTAL 1.1. Introducci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1. Caracterizaci´ on de soluciones . . . . . . . . . . . . 1.2. Teorema Fundamental . . . . . . . . . . . . . . . . . . . . . 1.2.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2. Demostraci´ on . . . . . . . . . . . . . . . . . . . . . . 1.3. Implicaciones del Teorema Fundamental . . . . . . . . . . 1.4. Ejempo de aplicaci´ on . . . . . . . . . . . . . . . . . . . . . .

FUN. . . . . . .

. . . . . . .

. . . . . . .

3 3 4 4 4 5 6 7

. . . . . . . .

. . . . . . . .

. . . . . . . .

11 11 13 14 14 15 15 18 20

MATRIZ COMPLETA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23 23 24 24

FUNDAMENTOS DEL M´ ETODO DEL SIMPLEX 2.1. Introducci´ on . . . . . . . . . . . . . . . . 2.2. Regla de entrada . . . . . . . . . . . . . . 2.3. Regla de salida . . . . . . . . . . . . . . . 2.4. Criterio de optimalidad . . . . . . . . . . 2.5. Ejemplo . . . . . . . . . . . . . . . . . . . 2.5.1. Primera iteraci´ on . . . . . . . . . 2.5.2. Segunda iteraci´ on . . . . . . . . 2.5.3. Tercera iteraci´ on . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

3.

M´ ETODO DEL SIMPLEX.VARIANTE DE LA 3.1. Introducci´ on . . . . . . . . . . . . . . 3.2. Variante de la matriz completa . . . 3.3. Ejemplo . . . . . . . . . . . . . . . . .

4.

M´ ETODOS DE LA M GRANDE Y DE LAS DOS FASES 4.1. Introducci´ on . . . . . . . . . . . . . . . . . . . . 4.2. M´ etodo de la M grande . . . . . . . . . . . . . . 4.3. M´ etodo de las 2 fases . . . . . . . . . . . . . . . 4.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . 4.4.1. M´ etodo de la M grande . . . . . . . . . 4.4.2. M´ etodo de las dos fases . . . . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

25 25 26 28 30 30 31

´Indice general

5.

6.

7.

8.

9.

´ T´ ´ INTERPRETACION ECNICO-ECONOMICA 5.1. Introducci´ on . . . . . . . . . . . . . . . 5.1.1. Ejemplo de aplicaci´ on . . . . . 5.2. Tasas de sustituci´ on . . . . . . . . . . 5.2.1. Discusi´ on te´ orica . . . . . . . . 5.2.2. Ejemplo de aplicaci´ on . . . . . 5.3. Multiplicadores del simplex . . . . . . 5.3.1. Discusi´ on te´ orica . . . . . . . . 5.3.2. Ejemplo de aplicaci´ on . . . . . 5.4. Criterios del simplex . . . . . . . . . . 5.4.1. Discusi´ on te´ orica . . . . . . . . 5.4.2. Ejemplo de aplicaci´ on . . . . . ´ GRA ´ FICA INTERPRETACION 6.1. Introducci´ on . . . . . . . . . . . 6.2. Conceptos generales . . . . . . 6.3. M´ etodo del Simplex . . . . . . . 6.4. M´ etodo de las dos fases y de la 6.5. M´ etodo de Lemke . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . M grande . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . . . . .

33 33 34 36 36 36 37 37 39 39 39 41

. . . . .

44 44 44 52 55 56

M´ ETODO DEL LEMKE 7.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2. Cu´ ando es interesante el m´ etodo de Lemke . . . . . . . . . . . 7.2.1. Problemas de m´ınimos con c ≥ 0 . . . . . . . . . . . . . 7.2.2. Al introducir un cambio en b, una vez obtenida la soluci´ on ´ optima . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.3. Al a˜ nadir una restricci´ on adicional a un programa, una vez obtenida la soluci´ on ´ optima . . . . . . . . . . . . . 7.3. Reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1. Criterio de factibilidad . . . . . . . . . . . . . . . . . . . 7.3.2. Regla de supresi´ on . . . . . . . . . . . . . . . . . . . . . 7.3.3. Regla de introducci´ on . . . . . . . . . . . . . . . . . . . . 7.4. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57 57 58 58

CASOS ESPECIALES 8.1. Introducci´ on . . . . . . . . . . . . . ´ 8.2. Optimo m´ ultiple . . . . . . . . . . . 8.3. Soluci´ on degenerada . . . . . . . . 8.4. Problema no factible . . . . . . . . 8.5. Regi´ on de factibilidad no acotada

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

64 64 64 66 67 69

´ POSTOPTIMIZACION 9.1. Introduction . . . 9.2. Cambio en b . . . 9.3. Cambio en c . . . . 9.4. Nueva actividad . 9.5. Nueva restricci´ on

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

73 73 73 74 75 75

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

60 61 61 61 61 62 62

3

´Indice general

9.6.

Cambio en aij . . . . . . . . . . . . . . . . 9.6.1. Cambio en aij con xj no b´ asica 9.6.2. Cambio en aij con xj b´ asica . . Ejemplo . . . . . . . . . . . . . . . . . . . . 9.7.1. Cambio de b . . . . . . . . . . . . 9.7.2. Cambio de c . . . . . . . . . . . . . 9.7.3. Nueva actividad . . . . . . . . . . 9.7.4. Nueva restricci´ on . . . . . . . . . 9.7.5. An´ alisis de sensibilidad de b . . 9.7.6. An´ alisis de sensibilidad de c . . La aparente paradoja de b . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

76 76 77 77 78 78 79 80 81 82 84

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

85 85 85 85 85 89 89 89 91

´ 11. TRANSPORTE Y ASIGNACION 11.1. Presentaci´ on del problema de transporte . . . . . 11.1.1. Introducci´ on . . . . . . . . . . . . . . . . . 11.1.2. Formulaci´ on . . . . . . . . . . . . . . . . . . 11.1.3. Presentaci´ on matricial . . . . . . . . . . . 11.1.4. Representaci´ on del problema . . . . . . . 11.1.5. Propiedades . . . . . . . . . . . . . . . . . . 11.2. M´ etodos de resoluci´ on . . . . . . . . . . . . . . . . 11.2.1. Obtenci´ on del soluci´ on inicial de partida 11.2.2. Regla de entrada. Stepping-stone . . . . . 11.2.3. Regla de entrada. MODI . . . . . . . . . . . 11.2.4. Regla de salida . . . . . . . . . . . . . . . . 11.2.5. Criterio de optimalidad . . . . . . . . . . . 11.3. Problemas desequilibrados . . . . . . . . . . . . . 11.3.1. Oferta superior a demanda . . . . . . . . 11.3.2. Demanda superior a oferta . . . . . . . . 11.4. Soluciones degeneradas . . . . . . . . . . . . . . . 11.5. Transporte y dualidad . . . . . . . . . . . . . . . . 11.6. Para pensar . . . . . . . . . . . . . . . . . . . . . . . 11.7. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . 11.8. El problema de asignaci´ on . . . . . . . . . . . . . . 11.8.1. Introducci´ on . . . . . . . . . . . . . . . . . 11.8.2. Representaci´ on . . . . . . . . . . . . . . . . 11.8.3. Propiedades . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

96 96 96 96 97 98 98 99 100 100 100 101 101 101 101 101 101 102 103 103 104 104 104 105

9.7.

9.8.

´ PARAM´ 10. PROGRAMACION ETRICA 10.1. Introducci´ on . . . . . . . . . 10.2. Programaci´ on con c(λ) . . . 10.2.1. M´ etodo general . . . 10.2.2. Ejemplo c(λ) . . . . 10.3. Programaci´ on con b(λ) . . . 10.3.1. M´ etodo general . . . 10.3.2. Ejemplo c(λ) . . . . 10.4. Ejemplo c(λ) y b(λ) . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4

´Indice general

11.8.4. M´ etodo H´ ungaro . . . . . . . . . . . . . . . . . . . . . . .

106

´ ENTERA. FUNDAMENTOS 12. PROGRAMACION 12.1. Divide y vencer´ as . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2. Enumeraci´ on impl´ıcita . . . . . . . . . . . . . . . . . . . . . . . . 12.3. Branch and Bound: un ejemplo . . . . . . . . . . . . . . . . . . .

107 107 107 109

´ ENTERA. BRANCH AND BOUND 13. PROGRAMACION 13.1. Introducci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.2. Optimalidad y relajaci´ on . . . . . . . . . . . . . . . . . . . . . . .

112 112 113

14. DUALIDAD 14.1. Introducci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.2. Teor´ıa sobre dualidad . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.1. El problema dual . . . . . . . . . . . . . . . . . . . . . . . 14.2.2. El dual del dual es el primal . . . . . . . . . . . . . . . . 14.2.3. Relaciones entre el problema primal y el problema dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.4. La funci´ on objetivo . . . . . . . . . . . . . . . . . . . . . 14.2.5. Teorema fundamental de la dualidad . . . . . . . . . . 14.2.6. Teorema de las holguras complementarias . . . . . . . 14.3. Interpretaci´ on econ´ omica de las variables duales en el ´ optimo 14.4. Algoritmo del simplex dual . . . . . . . . . . . . . . . . . . . . .

116 116 119 119 119 120 122 123 124 126 128

5

Cap´ıtulo 1 ´ A LA PROGRAMACION ´ INTRODUCCION LINEAL. TEOREMA FUNDAMENTAL

1.1.

Introducci´ on

Un problema de Programaci´ on Lineal tiene la siguiente forma. maz z =cx

(funci´ on objetivo)

s.a: Ax = b x≥0

Forma general de un problema

(restricciones funcionales)

(1.1)

(restricciones de no negatividad)

Matriz de coeficientes t´ ecnicos: A • matriz m × n • m filas - restricciones • n columnas - variables Vector de disponibilidad de recursos: b • matriz m × 1 • tantos elementos como restricciones Vector de contribuciones unitarias al beneficio: c • matriz 1 × n • tantos elementos como variables Soluci´ on del problema x • matriz n × 1 Podr´ıa haber tres casos para la relaci´ on entre y m y n: 1. m > n, t´ıpicamente, soluci´ on no factible. Sistema incompatible. O el modelo est´ a mal (por ejemplo, si se trata de un modelo de un sistema que existe y que est´ a en funcionamiento). O no existe soluci´ on factible. ´nica. Sistema compatible deter2. m = n, t´ıpicamente, soluci´ on factible u ´nica soluci´ minado. Existe una u on, con lo que no hay un problema de decisi´ on.

Dimensiones de A, b, c y x

Relaci´ on entre myn

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION

3. n > m, t´ıpicamente, infinitas soluciones factibles. Sistema compatible indeterminado. Infinitas soluciones, el problema consiste en obtener la mejor.

1.1.1.

Caracterizaci´ on de soluciones

Un conjunto de valores x es una soluci´ on del problema si cumple el sistema de ecuaciones Ax = b

Soluci´ on

Un conjunto de valores x es una soluci´ on factible del problema si cumple el sistema de ecuaciones Ax = b (es soluci´ on) y cumple que x ≥ 0, es decir todos los valores son no negativos.

Soluci´ on factible

Una soluci´ on x es linealmente independiente si las columnas de la matriz A correspondientes a las variables con valor no nulo son linealmente independientes.

Soluci´ on linealmente independiente

Una soluci´ on x es linealmente dependiente si las columnas de la matriz A correspondientes a las variables con valor no nulo son linealmente dependientes.

Soluci´ on linealmente dependiente

Dado que en un problema de programaci´ on lineal n > m, si el rango de la matriz A es m:

Caracter´ısiticas de las soluciones linealmente independientes

el n´ umero m´ aximo de componentes no nulas de una soluci´ on linealmente independiente es, m y el n´ umero m´ınimo de componentes no nulas de una soluci´ on linealmente dependiente t´ıpicamente es m + 1 1

1.2.

Teorema Fundamental

1.2.1.

Enunciado

Dado un problema de programaci´ on lineal: Si existe una soluci´ on factible, existe una soluci´ on linealmente independiente factible y ´nica, esta es una soluci´ si la soluci´ on ´ optima es u on linealmente independiente; si la soluci´ on ´ optima es m´ ultiple, al menos existe una soluci´ on linealmente independiente ´ optima. 1 Esto es as´ ı siempre cuando el rango de todas las matrices de m columnas de A es m. Si existiera una submatriz dentro de A con menos de m columnas linealmente dependientes, podr´ıa existir una soluci´ on linealmente dependiente con menos de m componentes.

Enunciado

7

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION

1.2.2.

Demostraci´ on

Si se demuestra que dada una soluci´ on linealmente dependiente x 0 de un problema de programaci´ on lineal, basta con que el problema est´ e acotado para que exista una soluci´ on linealmente independiente x tal que cx ≥ cx 0 , queda demostrado el teorema, ya que: 1. se demostrar´ıa que existe una soluci´ on linealmente independiente y 2. si para cualquier dependiente, siempre es posible encontrar otra lineal´nica ´ mente independiente no peor, de haber una u optima es linealmente independiente y, si hay varias, al menos una es linealmente independiente. En este segundo caso, si se conoce que alguna de las soluciones ´ optimas es linealmente independiente, quedar´ıa demostrado. Si no, alguna de las soluciones ´ optimas ser´ıa linealmente dependiente, por aplicaci´ on del enunciado, ser´ıa posible encontrar otra linealmente independiente no peor, y como la soluci´ on linealmente dependiente es ´ optima existir´ıa al menos una soluci´ on linealmente independiente tambi´ en ´ optima. En el primer enunciado del Teorema Fundamente, se entiende impl´ıcitamente, que el problema considerado est´ a actado. En efecto, si el problema no est´ a acotado, entonces no existe una soluci´ on ´ optima. Al contrario, si el problema s´ı est´ a acotado, existe al menos una soluci´ on ´ optima. Se trata de una demostraci´ on constructiva, partiendo de la soluci´ on x 0 . Como 0 x es una soluci´ on linealmente dependiente se puede encontrar un vector y, con las siguientes propiedades:

Propiedades de x0

Ay = 0 y yi = 0 si xi = 0 cy ≥ 0 (si no es as´ı, basta con cambiar de signo a y). A partir de x 0 se puede construir una nueva soluci´ on x 1 : x 1 = x 0 + ty

(con t ≥ 0)

Una nueva soluci´ on x 1 (1.2)

Efectivamente, es soluci´ on: Ax 1 = A(x 0 + ty) = Ax 0 + tAy = b + t0 = b

(1.3)

z1 = cx 1 = c(x 0 + ty) = cx 0 + tcy = z0 + tcy

(1.4)

Dado que cy ≥ 0, siempre se cupmle z1 ≥ z0 .

x 1 no es peor que x 0

8

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION

Los valores de las variables de la nueva soluci´ on son:

xi1 = xi0 + tyi

Una componente nula m´ as (1.5)

Se puede dar un valor a t de manera que ninguna variable tenga valor negativo y que tenga una componente nula m´ as que x 0 . t = min{i/yi ≤0}

xi0 yi

x 1 no es peor que x 0

(1.6)

Examinando de forma exhaustiva los casos que se pueden dar, la discusi´ on completa es la siguiente.

Discusi´ on completa

Si cy = 0 siempre se puede encontrar t ∈ (−∞, ∞) tal que x 1 tenga una componente nula m´ as que x 0 . En este caso: 1 • x es factible • cx 1 = cx 0 • x 1 tiene una componente nula m´ as Si cy > 0 x1

on no peor • Si ∃yi < 0, con t = min{i/yi ≤0} yii se obtiene una soluci´ con una componente nula m´ as. • Si yi > 0 el problema no est´ a acotado, el valor de la funci´ on objetivo pude ser tan grande como se desee. En t´ erminos de Ingenier´ıa de Organizaci´ on, los problemas no acotados no tienen sentido.

Problemas no acotados

Al llegar a una linealmente independiente, ya no se puede iterar, porque no existe y que cumpla 1.2.2. Por supuesto, por otro lado, se habr´ıa encontrado la soluci´ on linealmente independiente deseada.

Iterando

1.3.

Implicaciones del Teorema Fundamental

De acuerdo con lo que se sigue del teorema fundamental, siempre existe una soluci´ on ´ optima dentro del conjunto de todas las soluciones linealmente independientes.

D´ onde buscar

Una forma de resolver un problema de Programaci´ on Lineal es la siguiente:

Enumeraci´ on expl´ıcita

1. Resolver todos los sistemas de ecuaciones correspondientes a todas las soluciones linealmente independientes. 2. Descartar las no factibles 3. Escoger la que tenga mayor valor de la funci´ on ojetivo

9

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION

Eficaz, pero poco eficiente.

El problema 

Con m restricciones y n variables, existen

n m

 =

n! m!(n−m)!

Tiempos de resoluci´ on en a˜ nos supondiendo que cada sistema se resuelve en 10−6 segundos. Nº variables Nº restricciones Nº sol. B´ asicas Tiempo res. (a˜ nos)

1.4.

10 4 210

100 40 1.37462E+28 4.3589E+14

1000 400 4.9653E+290 1.5745E+277

Ejempo de aplicaci´ on maz z =4x1 + 4x2 + 6x3 + 8x4 2x1 + 3x2 + 3x3 + 6x4 + x5 = 400 1x1 + 2x2 + 6x3 + 3x4 + x6 = 200

(1.7)

5x1 + 5x2 + 5x3 + 5x4 + x7 = 10000

Soluci´ on inicial: x 0 = (0, 4, 14, 36, 130, 0, 9370)T , z0 = 388. Se trata de una soluci´ on porque se cumple Ax = b. Efectivamente, se puede comprobar que: ⎞ ⎛ 0 ⎟ ⎜ ⎜ 4 ⎟ ⎟ ⎛ ⎞ ⎛ ⎞⎜ ⎟ 400 2 3 3 6 1 0 0 ⎜ ⎜ 14 ⎟ ⎜ ⎟ ⎟ ⎜ ⎜ ⎟ (1.8) Ax 0 = ⎝ 1 2 6 3 0 1 0 ⎠ ⎜ 36 ⎟ = ⎝ 200 ⎠ ⎟ ⎜ ⎟ 1000 5 5 5 5 0 0 1 ⎜ ⎜ 130 ⎟ ⎟ ⎜ ⎝ 0 ⎠ 9370 Como las columnas correspondientes a componentes no negativas de x son linealmente dependientes, se pueden encontrar varlores de y2 , y3 , y4 , y5 y y7 no todos ellos nulos que cumplan: ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 3 3 6 1 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ y2 ⎝ 2 ⎠ + y3 ⎝ 6 ⎠ + y4 ⎝ 3 ⎠ + y5 ⎝ 0 ⎠ + y7 ⎝ 0 ⎠ = 5 5 5 0 1 (1.9) ⎛ ⎞ 0 ⎜ ⎟ =⎝ 0 ⎠ 0 O lo que es equivalente:

Ejemplo num´ erico

10

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION ⎞ ⎛ ⎞ ⎞ ⎞ ⎞ ⎞ ⎞ ⎛ ⎛ ⎛ ⎛ ⎛ 0 3 3 6 1 0 2 ⎟ ⎜ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 0 ⎝ 1 ⎠ + y2 ⎝ 2 ⎠ + y3 ⎝ 6 ⎠ + y4 ⎝ 3 ⎠ + y5 ⎝ 0 ⎠ + 0 ⎝ 1 ⎠ + y7 ⎝ 0 ⎠ = 0 5 5 5 0 1 5 ⎛ ⎞ 0 ⎜ ⎟ =⎝ 0 ⎠ 0 ⎛

(1.10) Es decir, es posible encontrar y que cumple Ay = 0, con yi = 0 si xi = 0 Un posible vector y es y = (0, 0,1, −0,567, 1,067, −5, 0, −3)T , con el que es posible construir una nueva soluci´ on x 1 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 1 0 x = x + ty = ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

0 4 14 36 130 0 9370

⎞

⎛

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎟+t⎜ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠

0 0,1 −0,567 1,067 −5 0 −3

Primera iteraci´ on

⎞

La nueva soluci´ on

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

(1.11)

Se puede comprobar que AX 1 = b. En efecto:

x 1 es soluci´ on ⎛

⎛

2 ⎜ Ax = A(x + ty) = ⎝ 1 5 1

0

⎛ ⎛

2 ⎜ +t ⎝ 1 5

3 2 5

3 6 5

6 3 5

1 0 0

0 1 0

⎜ ⎜ ⎞⎜ 0 ⎜ ⎜ ⎟⎜ 0 ⎠⎜ ⎜ 1 ⎜ ⎜ ⎜ ⎝

0 0,1 −0,567 1,067 −5 0 −3

⎞

3 2 5

3 6 5

6 3 5

1 0 0

0 1 0

⎜ ⎜ ⎞⎜ 0 ⎜ ⎜ ⎟⎜ 0 ⎠⎜ ⎜ 1 ⎜ ⎜ ⎜ ⎝

0 4 14 36 130 0 9370

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

⎟ ⎟ ⎟ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎟ 400 0 400 ⎟ ⎟ ⎜ ⎟ ⎜ ⎟ ⎟ ⎜ ⎟ = ⎝ 200 ⎠ + ⎝ 0 ⎠ = ⎝ 200 ⎠ ⎟ ⎟ 1000 0 1000 ⎟ ⎟ ⎠ (1.12)

Se puede comprobar que cy ≥ 0

x 1 no peor que x0

11

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION ⎞ 0 ⎟ ⎜ ⎟ ⎜ 0,1 ⎟ ⎜ ⎜ −0,567 ⎟ ⎟ ⎜  ⎟ ⎜ 0 ⎜ 1,067 ⎟ = 5,534 ⎟ ⎜ ⎟ ⎜ −5 ⎟ ⎜ ⎟ ⎜ 0 ⎠ ⎝ −3 ⎛

cy =

4

4

6

8

0

0

(1.13)

x 1 no peor que De no ser as´ı, bastar´ıa con cambiar el signo a y y todo lo anterior ser´ıa cierto. 1 Dado que cy > 0, el valor de la funci´ on de objetivo de x es mayor que la de x0 0 x en una cantidad igual a cy

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 ⎠ −3 9370 388 + 24,56 × 5,534 (1.14) Dado que s´ olo 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 9730 respectivamente 0 cada una de esas componentes de x 1 son 0,57 , 130 5 y 3 . En 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.15) 0,57 5 3 La nueva soluci´ on es: ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 1 x =⎜ ⎜ ⎜ ⎜ ⎜ ⎝

0 4 14 36 130 0 9370)

⎞ ⎛ ⎛ 0 0 ⎟ ⎜ ⎜ ⎟ ⎟ ⎜ 6,47 ⎜ ⎟ 0,1 ⎟ ⎜ ⎜ ⎟ ⎜ −0,567 ⎟ ⎜ ⎟ 0 ⎟ ⎜ ⎜ ⎟ ⎟ ⎜ ⎜ ⎟ ⎟ + 24,56 ⎜ 1,067 ⎟ = ⎜ 62,35 ⎟ ⎜ ⎜ ⎟ ⎟ ⎜ 6,55 ⎜ ⎟ −5 ⎟ ⎜ ⎜ ⎟ ⎟ ⎜ ⎜ ⎟ 0 0 ⎠ ⎝ ⎝ ⎠ 9655,93 −3 ⎞

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

(1.16)

12

´ A LA PROGRAMACION ´ LINEAL. TEOREMA FUNDAMENTAL Cap´ıtulo 1. INTRODUCCION

z1 = 524,68 y = (0, −4,2, 0, 2,8, −4,2, 0, 7)T t = min{ 6,47 4,2 ,

6,54 4,2

= 1,54

x 2 = (0, 0, 0, 66,66, 0,07, 0, 9666,71)T z2 = 533,38

Segunda iteraci´ on

13

Cap´ıtulo 2 FUNDAMENTOS DEL M´ ETODO DEL SIMPLEX

2.1.

Introducci´ on

Dado un problema de Programaci´ on Lineal

Soluci´ on b´ asica

maz z =cx s.a: Ax = b

(2.1)

x≥0 donde A es una matriz m × n, con n > m y rang(A) = m: Se define: Base B como un conjunto de m columnas de A linealmente independientes. Soluci´ on b´ asica correspondiente a la base B, valores de x resultantes de resolver el sistema de ecuaciones Ax = b anulando todas las variables correspondientes a columnas diferentes de las de B. Una soluci´ on b´ asica: • es linealmente independiente y • como m´ aximo, tiene m componentes no nulas, tantas como restricciones. En lo que sigue identificaremos: soluci´ on b´ asica con soluci´ on linealmente independiente. 1 soluci´ on no b´ asica con soluci´ on linealmente dependiente. Adem´ as: una soluci´ on b´ asica tiene como m´ aximo m componentes no nulas y 1 En

efecto. Por la propia definici´ on, una soluci´ on b´ asica es linealmente independiente. Por otro lado, cualquier soluci´ on linealmente independiente con m componentes no nulas es b´ asica. Y cualquier soluci´ on linealmente independiente con menos de p < m componenetes nulas tambi´ en es b´ asica por la siguiente raz´ on. Si tomamos la matriz con las p columnas de las variables no nulas, siempre podemos a˜ nadir 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´ on b´ asica con p varuables b´ asicas no nulas y m − p variables b´ asicas nulas, lo que se conoce como soluci´ on degenerada.

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

15

una soluci´ on no b´ asica tiene, t´ıpicamente, al menos m + 1 componentes no nulas2 . Dada una soluci´ on b´ asica, con base B, hay dos tipos de variables: Variable b´ asica: cada una de las variables correspondientes a las columnas de B, que son pontencialmenete no nulas. Variable no b´ asica: cada una de las variables correspondientes a las columnas de A no incluidas en B, que son siempre nulas. Podemos expresar las restricciones Ax = b como: BuB + A(−B) x (−B) = b

Nivel de realizaci´ on (2.2)

Donde uB es el nivel de realizaci´ on de las actividades b´ asicas (valor de las variables b´ asicas). x (−B) representa las variables no b´ asicas, que son nulas por definici´ on. A(−B) es el conjunto de columnas de las actividades no b´ asicas. c B es un vector fila con los elmentos de c correspondientes a las variables b´ asicas z = cx = c B uB + c (−B) x (−B)

Vector c B

(2.3)

Donde c (−B) es el vector fila de las contribuciones unitarias al beneficio de las variables no b´ asicas. Precios sombra πB

El vector de multiplicadores del simplex o precios sombra: π B = c B B −1

(2.4) Criterio del Simplex, V B

El vector de criterios del Simplex: V B = c − c B B −1 A

(2.5)

V B es un vector fila de n × 1. El criterio del simplex de la variable xk es VkB = ck − c B B −1 Ak , y es un escalar. Tasas de sustituci´ on, p B

El vector de tasas de sustituci´ on de las variables b´ asicas: p B = B −1 A

(2.6)

2 Podr´ ıa ocurrir que m columnas de A sean linealmente dependientes, de forma que el sistema de ecuaciones corrrespondiente fuera compatible indeterminado. Podr´ıan existir soluciones no b´ asicas con m componentes no nulas

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

16

p es una matriz m × n. Las tasas de sustituci´ on de las variables b´ asicas con respecto a la variable xk es p B = B −1 Ak , que es un vector columna m × 1.

Figura 2.1: L´ ogica del m´ etodo del Simplex

1. 2. 3. 4.

2.2.

Una soluci´ on b´ asica factible de partida; Un criterio de optimalidad; Una regla de entrada; y Una regla de salida.

Lo que necesitamos

Regla de entrada

Dada una soluci´ on b´ asica B, si la variable xk es no b´ asica, interesa introducirla en la base si se cumple: VkB = ck − c B B −1 Ak > 0

(2.7)

Dada una base B, se cumple Ax = b o, lo que es lo mismo, dado que todas las variables no b´ asicas son nulas: BuB = b. Si introducimos la variable xk con nivel de realizaci´ on t, la expresi´ on se convierte en: BuB (t) + tAk = b

(2.8)

Es decir, como xk = t ≠ 0, los valores originales de las variables b´ asicas (uB ) cambian en funci´ on del valor de la variable xk = t, y por esto la notaci´ on uB (t). Despejando: uB (t) = B −1 b − tB −1 Ak = uB − tpkB

Enunciado

(2.9)

Si entra xk cambia el valor de las variables b´ asicas

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

El valor de z al introducir la nueva variable es: z = cx(t) = c B uB (t) + tck = c B (B −1 b − tB −1 Ak ) + tck = c B B −1 b + t(ck − c B B −1 Ak ) = z + tVkB

(2.10)

Por lo tanto, si VkB es positivo, la nueva funci´ on objetivo es mayor. En concreto, V B representa el incremento unitario de la funci´ on objetivo al introducir xk .

VkB = ΔzΔxk =1

2.3.

17

Si entra xk cambia el valor de z

Intepretaci´ on de VB

(2.11)

Regla de salida

Si a partir de una soluci´ on b´ asica de base B entra la variable xk en la base, la variable que debe salir de la base es aquella variable es la i-´ esima, y que cumple: ⎧ ⎫ ⎨ uB ⎬ uBi j = min pB >0 (2.12) ⎩ pB ⎭ jk pB ik

Enunciado

jk

uB (t) = uB − tpkB ⇒ uBk (t) = uB − t

uBk B pjk

(2.13)

B pjk representa cu´ anto disminuye el valor de la j-´ esima variable b´ asica cuando se introduce la variable no b´ asica k con valor igual a 1.

Interpretaci´ on de p B

Si pjB k > 0, la j-´ esima variable b´ asica disminuye al introducir xk Si pjB k < 0, la j-´ esima variable b´ asica aumenta al introducir xk Si pjB k = 0, la j-´ esima variable b´ asica no se modifica al introducir xk

2.4.

Criterio de optimalidad

Una soluci´ on es ´ optima si V B ≤ 0, es decir, VjB ≤ 0 ∀j En efecto, si VjB ≤ 0∀j, la introducci´ on de una variable no b´ asica en la base dar´ıa lugar a un incremento negativo de la funci´ on objetivo. Con lo que no hay posiblidad de mejora; la soluci´ on es ´ optima.

Enunciado

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

18

Otra forma de justificarlo es la siguiente. Dada una soluci´ on b´ asica con base B:

V B ≤ 0 ⇒ c − c B B −1 A ≤ 0

(2.14)

Dada cualquier soluci´ on x, se pueden multiplicar por la derecha los t´ erminos de la expresi´ on anterior y operar:

cx − c B B −1 Ax = z − c B B −1 b = z − c B uB = z − zB ≤ 0 ⇒ zB ≥ z

2.5.

(2.15)

Ejemplo El problema

max. z =1x1 + 2x2 + 3x3 1x1 + 2x2 + 1x3 + x4 = 16 3x1 − 2x2 + 2x3 + x5 = 26

(2.16)

1x1 + 0x2 + 2x3 + x6 = 24 xi ≥ 0, i = 1 · · · 6

2.5.1.

Primera iteraci´ on

No hacer nada. Variables b´ asicas: variables de holgura.

Soluci´ on inicial

Las columnas de las variables b´ asicas.

La base ⎛

1 ⎜ B1 = (A5 A6 A7 ) = ⎝ 0 0

0 1 0

⎞ 0 ⎟ 0 ⎠ 1

(2.17)

En este caso, la inversa de la base es la identidad tambi´ en, pero solo en este caso. ⎛

B1−1

1 ⎜ =⎝ 0 0

0 1 0

⎞ 0 ⎟ 0 ⎠ 1

(2.18)

La inversa de la base

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

En este caso, el nivel de realizaci´ on coincide con b, pero solo en este caso. ⎛

uB1

1 ⎜ = B1−1 b = ⎝ 0 0

⎞⎛ ⎞ ⎛ ⎞ 0 16 16 ⎟⎜ ⎟ ⎜ ⎟ 0 ⎠ ⎝ 26 ⎠ = ⎝ 26 ⎠ 1 24 24

0 1 0

zB1 = cx 1 = c B1 uB1 =

0

0



0

La funci´ on objetivo

⎛

⎞ 16 ⎜ ⎟ ⎝ 26 ⎠ = 0 24

(2.20)

En este caso, las tasas de sustituci´ on coinciden con la matriz de coeficientes t´ ecnicos, pero solo en este caso. ⎛

p B1

1 ⎜ −1 = B1 A = ⎝ 0 0

0 1 0

⎞⎛ 0 1 ⎟⎜ 0 ⎠⎝ 3 1 1 ⎛

2 −2 0

1 ⎜ ⎝ 3 1

1 2 2

2 −2 0

1 0 0 1 2 2

0 1 0 1 0 0

⎞ 0 ⎟ 0 ⎠= 1 ⎞ 0 0 ⎟ 1 0 ⎠ 0 1

0

0

0



−

0

0

=



1 2 −2 0 1

2 1 2 2 2

c B1

(2.22)

El criterio del Simplex es igual a c, pero s´ olo en este caso.

V B1 = c − c B1 B −1 A = ⎛ ⎞⎛ 1  1 0 0 ⎜ ⎟⎜ 0 ⎝ 0 1 0 ⎠⎝ 3 0 0 1 1

Las tasas de sustituci´ on

(2.21)

Las componentes de c B1 son las componentes de c de las variables b´ asicas.

c B1 =

El nivel de realizaci´ on de las variables b´ asicas

(2.19)

La funci´ on objetivo se puede calcular de la siguiente manera:

19

3 1 0 0 3

0 0 1 0 0

El criterio del Simplex 0

0 ⎞



0 ⎟ 0 ⎠= 1  0 0

(2.23)

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

20

Aquella de las no b´ asicas con criterio del Simplex positivo y, de entre ellas, la mayor. En este caso, la variable de entrada es x3 .

Variable de entrada

Las tasas de sustituci´ on de la variable x3 con respecto a las variables b´ asicas B son p3 1

Variable de salida

⎛

B

p3 1

1 ⎜ = B −1 A3 = ⎝ 0 0

0 1 0

⎞⎛ ⎞ ⎛ ⎞ 0 1 1 ⎟⎜ ⎟ ⎜ ⎟ 0 ⎠⎝ 2 ⎠ = ⎝ 2 ⎠ 1 2 2

(2.24)

Las variables candidatas a salir de la base son aquellas que tienen tasa de asicas. Aquella sutituci´ on postiva con respecto a x3 , que son las tres variables b´ que sale es aquella correspondiente al menor cociente de t de la variable de entrada: t = min

16 26 24 , , 1 2 2

uBi B

p3i1

, que ser´ a el valor

= 12

(2.25)

Los valores de las variables b´ asicas de la primera base cambian al introducir x3 ⎛

B

uB1 (t) = uB1 − tp3 1

⎞ ⎛ ⎞ 16 1 ⎜ ⎟ ⎜ ⎟ = ⎝ 26 ⎠ − t ⎝ 2 ⎠ 24 2

Nuevos valores de las variables b´ asicas

(2.26)

Como sabemos que t = 12 ⎛

⎞ ⎛ ⎞ ⎛ ⎞ 16 1 4 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ uB1 (12) = ⎝ 26 ⎠ − 12 ⎝ 2 ⎠ = ⎝ 2 ⎠ 24 2 0

(2.27)

on de las tres variaEs decir, al introducir x3 en la base, los niveles de realizaci´ bles b´ asicas disminuyen y la primera que se anula es x6 cuando x3 = 12 A partir de la primera base, que no es ´ optima:

Resumen B

interesa introducir x3 , cuyo criterio del simplex es V3 1 = 3 y y que entre con valor x3 = 12 para que salga de la base x6 B y que la funci´ on objetivo se incremente en tV3 1 = 12 × 3 = 36

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

2.5.2.

21

Segunda iteraci´ on

Hacer solo 12 unidades de producto P3 y nada del resto. Variables b´ asicas: x4 , x5 y x3 .

Soluci´ on inicial

Las columnas de las variables b´ asicas.

La base

⎛

1 ⎜ B2 = ⎝ 0 0

⎞ 1 ⎟ 2 ⎠ 2

0 1 0

(2.28)

En este caso, la inversa de la base ya no es la identidad. ⎛

1 ⎜ =⎜ ⎝ 0 0

B2−1

La inversa de la base

⎞ − 12 ⎟ −1 ⎟ ⎠

0 1 0

(2.29)

1 2

En este caso, el nivel de realizaci´ on no coincide con b. ⎛

uB2

z

B2

1 ⎜ 0 = B2−1 b = ⎜ ⎝ 0

2

B2

B2

= cx = c u

⎞⎛ ⎞ ⎛ ⎞ − 12 16 4 ⎟⎜ ⎟ ⎜ ⎟ −1 ⎟ ⎠ ⎝ 26 ⎠ = ⎝ 2 ⎠ 1 24 12 2

0 1 0

=

0

0

3



⎞ 4 ⎜ ⎟ ⎝ 2 ⎠ = 36 12

(2.30)

⎛

(2.31)

El nivel de realizaci´ on de las variables b´ asicas

La funci´ on objetivo

B

En efecto, como esper´ abamos z2 = z1 + x3 V3 1 = 0 + 36 = 36 En este caso, las tasas de sustituci´ on no coinciden con la matriz de coeficientes t´ ecnicos. ⎛

p B2

1 ⎜ 0 = B2−1 A = ⎜ ⎝ 0

0 1 0

⎞⎛ − 12 1 ⎟⎜ −1 ⎟ ⎠⎝ 3 1 1 2 ⎛

1

⎜ 2 ⎜ 2 ⎝ 1 2

2 −2 0

1 2 2

1 0 0

2 −2 0

0 0 1

1 0 0

⎞ 0 ⎟ 0 ⎠= 1 ⎞ 0 − 12 ⎟ 1 −1 ⎟ ⎠ 1 0 2

0 1 0

(2.32)

Las tasas de sustituci´ on

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

Las componentes de c B2 son las componentes de c de las variables b´ asicas.

c B2 =

0

0

3



−

0

0

El criterio del Simplex

V B2 = c − c B2 B2−1 A = ⎞⎛ ⎛ 1 ⎜ 1 0 −2 ⎟ 1 ⎟⎜ 3 ⎜ ⎝ 0 1 −1 ⎠ ⎝ 3 1 1 0 0 2 ⎛ −

0

0

3

c B2

(2.33)

El criterio del Simplex es el siguiente.

22

⎜ ⎜ ⎝ =



1 2 −2 0

2 1 2 2

3 1 0 0

0

0

0 1 0

0 ⎞



0 ⎟ 0 ⎠= 1

 1 2 3 0 0 0 ⎞ 1 2 0 1 0 − 21 2 ⎟ 2 −2 0 0 1 −1 ⎟ ⎠ 1 1 0 1 0 0 2 2  − 21 2 0 0 0 − 32

(2.34)

Aquella de las no b´ asicas con criterio del Simplex positivo y, de entre ellas, la mayor. En este caso, la variable de entrada es x2 .

Variable de entrada

Las tasas de sustituci´ on de la variable x2 con respecto a las variables b´ asicas B son p2 2

Variable de salida

⎛

B

p2 2

1 ⎜ 0 = B2−1 A2 = ⎜ ⎝ 0

0 1 0

⎞⎛ ⎞ ⎛ ⎞ − 12 2 2 ⎟⎜ ⎟ ⎜ ⎟ −1 ⎟ ⎠ ⎝ −2 ⎠ = ⎝ −2 ⎠ 1 0 0 2

(2.35)

Las variables candidatas a salir de la base son aquellas que tienen tasa de sutituci´ on postiva con respecto a x2 , que son la variables b´ asica x4 . Aquela que sale es aquella correspondiente al menor cociente de t de la variable de entrada:

t=

4 =2 2

uBi B

p2i2

, que ser´ a el valor

(2.36)

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

Los valores de las variables b´ asicas de la primera base cambian al introducir x3

Nuevos valores de las variables b´ asicas

⎛

uB2 (t) = uB2 −

B tp2 2

⎞ ⎛ ⎞ 4 2 ⎜ ⎟ ⎜ ⎟ = ⎝ 2 ⎠ − t ⎝ −2 ⎠ 12 0

23

(2.37)

Como sabemos que t = 2 ⎛

⎞ ⎛ ⎞ ⎛ ⎞ 4 2 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ uB2 (2) = ⎝ 2 ⎠ − 2 ⎝ −2 ⎠ = ⎝ 6 ⎠ 12 0 12

(2.38)

on solo x4 disminuEs decir, al introducir x2 en la base, los niveles de realizaci´ ye y, en particular, se hace cero cuando x2 = 2 A partir de la segunda base, que no es ´ optima:

Resumen B

interesa introducir x2 , cuyo criterio del simplex es V2 2 = 2 y y que entre con valor x3 = 2 para que salga de la base x4 B y que la funci´ on objetivo se incremente en tV2 2 = 2 × 2 = 4

2.5.3.

Tercera iteraci´ on

Hacer solo 12 unidades de producto P3 y cuatro de P2 . Variables b´ asicas: x2 , x5 y x3 .

Soluci´ on inicial

Las columnas de las variables b´ asicas.

La base

⎛

2 ⎜ B3 = ⎝ −2 0

0 1 0

⎞ 1 ⎟ 2 ⎠ 2

(2.39)

En este caso, la inversa de la base ya no es la identidad. ⎛ B3−1

1

⎜ 2 =⎜ ⎝ 1 0

0 1 0

⎞ − 14 ⎟ − 32 ⎟ ⎠ 1 2

La inversa de la base

(2.40)

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

En este caso, el nivel de realizaci´ on no coincide con b. ⎛

1 2

⎜ uB3 = B3−1 b = ⎜ ⎝ 1 0

⎞⎛ ⎞ ⎛ ⎞ − 14 16 2 ⎟ ⎜ ⎟ ⎜ ⎟ − 32 ⎟ ⎠ ⎝ 26 ⎠ = ⎝ 6 ⎠ 1 24 12 2

0 1 0

zB3 = cx 3 = c B3 uB3 =

2

0

3



⎞ 2 ⎜ ⎟ ⎝ 6 ⎠ = 40 12

24

El nivel de realizaci´ on de las variables b´ asicas (2.41)

⎛

(2.42)

La funci´ on objetivo

B

En efecto, como esper´ abamos z3 = z2 + x2 V2 2 = 36 + 2 × 2 = 40 En este caso, las tasas de sustituci´ on son las siguientes. ⎛ p B3

1

⎜ 2 = B3−1 A = ⎜ ⎝ 1 0

0 1 0

⎞⎛ − 14 1 ⎟⎜ − 32 ⎟ ⎝ ⎠ 3 1 1 2 ⎛ ⎜ ⎜ ⎝

1 4 5 2 1 2

2 −2 0

1 2 2

1 0 0

1 0 0

0 0 1

1 2

1 0

Las tasas de sustituci´ on ⎞ 0 ⎟ 0 ⎠= 1 ⎞ 0 − 14 ⎟ 1 − 32 ⎟ ⎠ 1 0 2

0 1 0

(2.43)

Las componentes de c B3 son las componentes de c de las variables b´ asicas.

c B3 =

2

0

3



(2.44)

El criterio del Simplex es el siguiente.

−

0

0

 V B3 = c − c B3 B −1 A = 1 2 3 0 0 0 ⎞⎛ ⎛ ⎞ 1 1 2 1 1 0 0 ⎜ 2 0 −4 ⎟ 1 ⎟ 3 ⎟⎜ 3 ⎜ ⎝ 1 1 − 2 ⎠ ⎝ 3 −2 2 0 1 0 ⎠ = 1 1 0 2 0 0 1 0 0 2

 = −1 0 0 −1 0 −1

c B3

El criterio del Simplex

(2.45)

´TODO DEL SIMPLEX Cap´ıtulo 2. FUNDAMENTOS DEL ME

La soluci´ on de la base B3 es ´ optima, ya que V B3 ≤ 0

25

La soluci´ on es ´ptima o

Cap´ıtulo 3 M´ ETODO DEL SIMPLEX.VARIANTE DE LA MATRIZ COMPLETA

3.1.

Introducci´ on

(B|A)

oper andopor f ilas

→

I|B −1



(3.2)

Operar por filas una matriz es id´ entico a premultipilcar por una matriz En 3.3, la matriz A se puede obtener a patir de la matriz A de la siguiente manera. F 1 = 2 × F 1 F 2 = F 2 + F 1 = F 2 + 2 × F 1 F 3 = F 3 ⎛ ⎞ 1 −1 3 ⎜ ⎟ 1 0 ⎠ A=⎝ 2 0 4 1

⎛

2 ⎜

A =⎝ 4 0

Es posible encontrar una matriz M, tal que ⎛ 2 0 ⎜ M =⎝ 2 1 0 0

−2 −1 4

⎞ 6 ⎟ 6 ⎠ 1

MA = B ⎞ 0 ⎟ 0 ⎠ 1

(3.3)

(3.4)

En 3.2, la matriz por la que estamos multiplicando tanto B como A es B − 1 Podemos ampliar el conjunto de matrices con el que operamos por filas

 oper andopor f ilas → uB |p B |I|B −1 | (3.5) (b|A|B|I) Finalmente:

(3.6)



0 b

c A

cB B

0 I



 -

−z uB

VB pB

0 I

−π B B −1



´TODO DEL SIMPLEX.VARIANTE DE LA MATRIZ COMPLETA Cap´ıtulo 3. ME

3.2.

27

Variante de la matriz completa

Figura 3.1: L´ ogica del m´ etodo del Simplex

3.3.

Ejemplo

El siguiente problema es el mismo que el del ejemplo disponible en 2.5, resuelto mediante el m´ etodo del simplex, en su variante de la matriz completa. maz z =1x1 + 2x2 + 3x3

El problema

1x1 + 2x2 + 1x3 + x4 = 16 3x1 − 2x2 + 2x3 + x5 = 26 1x1 + 0x2 + 2x3 + x6 = 24 xi ≥ 0, i = 1 · · · 6 0 16 26 24

x1 1 1 3 1

x2 2 1 -2 0

x3 3 1 2 2

x4 0 1 0 0

x5 0 0 1 0

x6 0 0 0 1

F0 F1 F2 F3

x4 x5 x6

0 16 26 24

1 1 3 1

2 1 -2 0

3 1 2 2

0 1 0 0

0 0 1 0

0 0 0 1

F0

F1

F2

F3

= F0 = F1 = F2 = F3

− 21

x4 x5 x3

-36 4 2 12

2 2 -2 0

0 0 0 1

0 1 0 0

0 0 1 0

− 32 − 12 -1

F0

F1

F2

F3

= F0 − 3F3

= F1 − F3

= F2 − 2F3

= F3 /2

-1

0 1 0 0

0 0 0 1

-1

x2 x5 x3

-40 2 6 12

0 0 1 0

-1 − 14 − 32

F0

F1

F2

F3

= F0

− 2F1

= F1

/2 = F2

+ 2F1

= F3

1 2

2 1 2

1 4 5 2 1 2

1 2

1 0

1 2

1 2

(3.7)

Cap´ıtulo 4 M´ ETODOS DE LA M GRANDE Y DE LAS DOS FASES

4.1.

Introducci´ on

Para aplicar el m´ etodo del Simplex es necesario disponer de una soluci´ on b´ asica factible de partida del sistema Ax = b a partir de la cual iterar.

Por qu´ e estos m´ etodos

Cuando todas las restricciones son ≤ con t´ ermino independiente no negativo, es decir, de la forma:

Soluci´ on inicial sencilla



aij xj ≤ bi

bi ≥ 0

(4.1)

j

todas se pueden expresar como: 

aij xj + hi = bi

bi ≥ 0

(4.2)

j

En este caso existe una soluci´ on de partida b´ asica factible inicial trivial, con las variables de holgura como variables b´ asicas. Para esta soluci´ on: La base es igual a la matriz identidad, B = I. uB = b, es decir el valor de cada variables b´ asicas, correspondiente a una variable de holgura es igual al valor de la disponibilidad del recurso correspondiente. z = 0. V B = c. pB = A cB = 0 πB = 0

Soluci´ on inicial trivial

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

Si existe alguna restricci´ on de tipo ≥, se puede convertir en una igualdad a˜ nadiendo una variable de holgura con coeficiente −1:  

aij xj ≥ bi

bi ≥ 0

aij xj − hi = bi

bi ≥ 0

j

29

Restricciones ≥

(4.3)

j

Si existe alguna restricci´ on de tipo =, no es necesario introducir ninguna variable de holgura: 

aij xj = bi

j

Restricciones =

(4.4)

Si existen restricciones de tipo ≥ o =, al convertirlas en restricciones en t´ erminos de igualdad, no es tan sencillo obtener una soluci´ on de partida trivial.

4.2.

M´ etodo de la M grande

Dado un problema de Programaci´ on Lineal P : 

Problema original, P y problema auxiliar P

aij xj ≤ bi

j



ai j xj ≥ bi

j



(4.5) ai

j xj = bi

j

xj ≥ 0 Es posible convertirlo en un problema en donde las restricciones respondan a la forma de Ax = b:   j

max. z = cx aij xj + hi = bi

j

ai j xj − hi = bi



ai

j xj = bi

j

xj , hi , hi ≥ 0

(4.6)

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

30

Se puede definir un problema P de la forma: max. z = cx − M

 i

  j

ai − M



ai

i

aij xj + hi = bi

j

ai j xj − hi + ai = bi



(4.7)

ai

j xj + ai

= bi

j

xj , hi , hi , ai , ai

≥ 0 Donde M es un n´ umero ’suficientemente grande’ y las variables ai y ai

se denominan variables artificiales. Cualquier soluci´ on factible de P es soluci´ on factible de P .

Una soluci´ on factible de P lo es tambi´ en de P si todas las variables artificiales son simult´ aneamente cero. Si no existe ninguna soluci´ on factible de P con todas las variables artificiales simult´ aneamente nulas, no existe soluci´ on factible de P . Si para cualquier soluci´ on ´ optima de P , siempre una variable artificial toma un valor no nulo, P no tiene soluci´ on factible. Siempre es posible encontrar una soluci´ on b´ asica factible de partida de P

1. Dado P construir P

2. Resolver P : a) Si al resolver P mediante el m´ etodo del simplex se obtiene una soluci´ on b´ asica factible de P en la que todas la variables artificiales son nulas, esa es una soluci´ o b´ asica de partida del problema P , que puede servir de soluci´ on de partida para aplicar el m´ etodo del Simplex en la resoluci´ on de P . b) Si para cualquier soluci´ on ´ optima de P , siempre al menos una variable artificial toma un valor no nulo, P no tiene soluci´ on factible. P y P solo se diferencian en que P tiene un conjunto de actividades adicionales (las ficticias), lo cual es traduce en tantas componentes de c adicionales como variables artificiales (con valor nulo) y tantas columnas en A adicionales como variables artificiales (columnas de la matriz identidad). Salvo por esas columnas c, A, b y x son id´ enticos para los dos problemas

propiedades de P

M´ etodo de resoluci´ on

Relaci´ on entre P y P

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

31

Cuando se obtiene una soluci´ on b´ asica de P en la que las variables artificiales no est´ an en la base:



B = B , c B = c B , uB = uB , por lo que:

VB = VB

pB = pB

uB = uB

zB = zB Es decir, la tabla obtenida en la resoluci´ on de P es completamente id´ entica a la correspondiente a P , salvo por las columnas correspondientes a las variables artificiales. Las columnas auxiliares de las variables correspondientes a las variables artificiales permiten disponer, en todo momento, de parte de las columnas de la inversa de la base.

4.3.

Las columnas de las variables artificiales

M´ etodo de las 2 fases

El m´ etodo de las dos fases se apoya, igualmente, en un problema auxiliar P , igual que el de la M salvo en la funci´ on objetivo. Esta funci´ on es la suma de las

variables artificiales con coeficiente −1. Es decir, P tiene la forma: max. z = −   j

 i

ai −



ai

i

aij xj + hi = bi

j

ai j xj − hi + ai = bi



(4.8)

ai

j xj + ai

= bi

j

xj , hi , hi , ai , ai

≥ 0 Las propiedades del problema P son las siguientes: Cualquier soluci´ on factible de P es soluci´ on factible de P .

Una soluci´ on factible de P lo es tambi´ en de P si todas las variables artificiales son simult´ aneamente cero. Si no existe ninguna soluci´ on factible de P con todas las variables artificiales simult´ aneamente nulas, no existe soluci´ on factible de P . Si para cualquier soluci´ on ´ optima de P , siempre una variable artificial toma un valor no nulo, P no tiene soluci´ on factible. Siempre es posible encontrar una soluci´ on b´ asica factible de partida de P

propiedades de P

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

1. Dado P construir P

2. Resolver P : a) Si al resolver P mediante el m´ etodo del simplex se obtiene una soluci´ on b´ asica factible de P en la que todas la variables artificiales son nulas, esa es una soluci´ on b´ asica de partida del problema P , que puede servir de soluci´ on de partida para aplicar el m´ etodo del Simplex en la resoluci´ on de P . b) Si para cualquier soluci´ on ´ optima de P , siempre al menos una variable artificial toma un valor no nulo, P no tiene soluci´ on factible. Los problemas P y P se diferencian en lo siguiente: 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: el vector de disponibilidad de los recursos b = b y la matriz de coeficientes t´ ecnicos de las variables no artificiales Ai = A i si xi no es una variable artificial. Dada una soluci´ on b´ asica factible de P en la ninguna variables b´ asica es artificial las bases de dicha soluci´ on es com´ un para P y P

32

M´ etodo de resoluci´ on

Diferencias entre P y P

Analog´ıas entre P y P

Relaci´ on entre bases

Cuando se obtiene una soluci´ on b´ asica de P en la que las variables artificiales no est´ an en la base, los siguientes elementos son coincidentes: B = B

B −1 = B −1

uB = u B (ya que B −1 b = B −1 b )

p B = p B Pero los siguientes elementos son diferentes

c B ≠c’B

zB ≠ z B B

B

V ≠V Es decir, de la tabla obtenida en la resoluci´ on de P de pueden reutilizar todas B las filas menos la que contienen −z y V , que hay que recalcular. Las columnas auxiliares de las variables correspondientes a las variables artificiales permiten disponer, en todo momento, de parte de las columnas de la inversa de la base.

Las columnas de las variables artificiales

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

4.4.

4.4.1.

33

Ejemplos

M´ etodo de la M grande max. z = x1 + 2x2 + 3x3

Problema P

x1 + x2 + x3 ≤ 16 3x1 + 2x2 + 2x3 = 26

(4.9)

x1 + x3 ≥ 10 x1 , x2 , x3 ≥ 0 max. z = x1 + 2x2 + 3x3

Problema P reformulado

x1 + x2 + x3 + h1 = 16 3x1 + 2x2 + 2x3 = 26

(4.10)

x1 + x3 − h3 = 10 x1 , x2 , x3 , h1 , h3 ≥ 0 max. z = x1 + 2x2 + 3x3 − Ma2 − Ma3

Problema P’

x1 + x2 + x3 + h1 = 16 3x1 + 2x2 + 2x3 + a2 = 26 x1 + x3 − h3 + a3 = 10 x1 , x2 , x3 , h1 , h3 , a2 , a3 ≥ 0

(4.11)

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

34

0 16 26 10

x1 1 1 3 1

x2 2 1 2 0

x3 3 1 2 1

h3 0 0 0 -1

h1 0 1 0 0

a2 -M 0 1 0

a3 -M 0 0 1

F0 F1 F2 F3

h1 a2 a3

36M 16 26 10

1+4M 1 3 1

2+2M 1 2 0

3+3M 1 2 1

-M 0 0 -1

0 1 0 0

0 0 1 0

0 0 0 1

F 0

F 1

F 2

F 3

0

7+M 3 1 3 2 3 1 3

0

F 0

= F 0 − (1 + 4M)F 2

0 0 -1

1 0 0

−1−4M 3 −1 3 1 3 −1 3

0

0 1 0

4−2M 3 1 3 2 3 −2 3

-M

h1 x1 a3

4M−26 3 22 3 26 3 4 3

0 0 1

F 1

= F 1 − F 2

F 2

= F 2 /3 F 3

= F 3 − F 2

h1 x1 x3

-18 6 6 4

0 0 1 0

6 1 2 -2

0 0 0 1

7 1 2 -3

0 1 0 0

2-M 0 1 -1

-7-M -1 -2 3

= F 0 + MF 2 + MF 3 = F1 = F2 = F3

F 0

F 1

F 2

F 3





= F 0

− 7+M 3 F3



= F 1 − 1/3F 3 = F 2

− 2/3F 3

= 3F 3

La soluci´ on anterior es una soluci´ on b´ asica factible de P y tambi´ en una soluci´ on b´ asica factible de P (ya que las actividades artificiales son simult´ aneamente nulas).

h1 x1 x3

-18 6 6 4

h1 h3 x3

-39 3 3 13

4.4.2.

x1 0 0 1 0

x2 6 1 2 -2

x3 0 0 0 1

h3 7 1 2 -3

h1 0 1 0 0

a2 2 0 1 -1

a3 -7 -1 -2 3

− 27 − 21

-1 0 1 1

0 0 0 1

0 0 1 0

0 1 0 0

− 32 − 12

-0 -0 -1 0

1 2 3 2

1 2 1 2

M´ etodo de las dos fases max. z = x1 + 2x2 + 3x3

Problema P

x1 + x2 + x3 ≤ 16 3x1 + 2x2 + 2x3 = 26 x1 + x3 ≥ 10 x1 , x2 , x3 ≥ 0

(4.12)

´TODOS DE LA M GRANDE Y DE LAS DOS FASES Cap´ıtulo 4. ME

max. z = x1 + 2x2 + 3x3

35

Problema P reformulado

x1 + x2 + x3 + h1 = 16 3x1 + 2x2 + 2x3 = 26

(4.13)

x1 + x3 − h3 = 10 x1 , x2 , x3 , h1 , h3 ≥ 0 max. z = −a2 − a3

Problema P’

x1 + x2 + x3 + h1 = 16 3x1 + 2x2 + 2x3 + a2 = 26

(4.14)

x1 + x3 − h3 + a3 = 10 x1 , x2 , x3 , h1 , h3 , a2 , a3 ≥ 0

fase 1 fase 2

0 0 16 26 10

x1 0 1 1 3 1

x2 0 2 1 2 0

x3 0 3 1 2 1

h3 0 0 0 0 -1

h1 0 0 1 0 0

a2 -1 0 0 1 0

a3 -1 0 0 0 1

F 01 F 02 F1 F2 F3

fase 1 fase 2 h1 a2 a3

36 0 16 26 10

4 1 1 3 1

2 2 1 2 0

3 3 1 2 1

-1 0 0 0 -1

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

F 0 1 = F 01 + F 2 + F 3

F 0 2 = F 02 F 1 = F 1 F 2 = F 2 F 3 = F 3

fase 1 fase 2

0 0

− 23

1 3 7 3 1 3 2 3 1 3

0 0

− 43 − 13

0 0



F 0

1 = F 01 − 4F 2



F 02 = F 01 − F 2

0 1 0

4 3 1 3 2 3 − 23

-1 0

h1 x1 a3

4 3 − 26 3 22 3 26 3 4 3

0 0 -1

1 0 0

− 13 1 3 − 13

0 0 1

F 1

= F 1 − F 2

F 2

= F 2 /3 F 3

= F 3 − F 2

fase 1 fase 2 h1 x1 x3

0 -18 6 6 4

0 0 0 1 0

0 6 1 2 -2

0 0 0 0 1

0 7 1 2 -3

0 0 1 0 0

-1 2 0 1 -1

-1 -7 -1 -2 3

F 0

1 F 0

2 F 1

F 2

F 3

1

= F 0

1 − 3F3 7

= F 01 − 3 F 3

= F 1

− 1/3F 3

= F 2

− 2/3F 3

= 3F 3

Cap´ıtulo 5 ´ T´ ´ INTERPRETACION ECNICO-ECONOMICA

5.1.

Introducci´ on

Dado un problema de Programaci´ on Lineal, {P : max. z = cx, s.a Ax = b, x ≥ 0}, existen varios elementos caracter´ısticos del problema y que no dependen de la soluci´ on:

Elementos caracter´ısticos de un problema

c b A Para un problema y una base B (que caracteriza a la soluci´ on b´ asica correspondiente), existen varios elementos caracter´ısticos de esa soluci´ on para ese problema

Elementos caracter´ısticos de una soluci´ on

uB cB pB πB Este cap´ıtulo se ocupa de la interpretaci´ on de estos elementos que dependen de la base. Por ejemplo, m´ as adelante, se habla sobre el valor de los recursos en un problema y para una soluci´ on (una base). Pues bien, el valor de los recursos depende de dicha soluci´ on. Por ejemplo, el valor que tiene para un centro de c´ alculo depende de la forma en la que operar de dicho centro. Un servidor adicional no tiene ning´ un valor si en dicho centro de c´ alculo existen servidores desocupados. Esto no significa que el servidor adicional no tenga valor, no tiene valor para dicha forma de operar del centro de c´ alculo.

Un ejemplo

En otro contexto, el valor que tiene un vaso de agua cuando alguien lleva varios d´ıas sin suministro en el desierto es muy diferente del valor que tiene ese vaso 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´ on. Aqu´ı diremos que los recursos tienen diferente valor seg´ un la soluci´ on, es decir, seg´ un la base elegida.

Un ejemplo m´ as dom´ estico

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

37

´ptima, T´ıpicamente, la interpretaci´ on econ´ omica se realiza para la soluci´ on o porque es la soluci´ on m´ as interesante pero se podr´ıa realizar el mismo an´ alsis para cada cualquier soluci´ on del problema considerado.

5.1.1.

Ejemplo de aplicaci´ on

Para ilustrar la interpretaci´ on, en lo que sigue del cap´ıtulo emplearemos el siguiente ejemplo. Una empresa monta dos tipos de pal´ es. Los pal´ es de tipo 1 contienen un producto P1 y los pal´ es de tipo 2 contienen, a su vez, dos productos P2 .

Presentaci´ on del problema

Con la venta de cada pal´ e de tipo 1, la empresa tiene un beneficio neto de 2 unidades monetarias (u.m.) Igualmente, la empresa tiene un beneficio neto de 1 u.m. con cada pal´ e de tipo 2.

El beneficio

Los pal´ es deben ser preparados en dos talleres, T1 y T2 , de los que se dispone de un total de 30 y 16 horas semanales, respectivamente, para realizar las operaciones correspondientes a cada uno de ellos. Cada pal´ e 1 requiere 3 horas de preparaci´ on en T1 y 4 horas de preparaci´ on en T2 . Cada pal´ e 2 requiere 1 hora de preparaci´ on en T1 y 3 horas de preparaci´ on en T2 .

Los talleres

Adem´ as, existe un compromiso comercial de entregar al menos 4 productos semanales, donde estos cuatro productos pueden ser cualquier combinaci´ on de productos P1 y P2 .

Compromiso comercial

´ltimo, existe un colectivo al respecto del cual la empresa tiene un comproPor u miso consistente en emplear un n´ umero m´ınimo de horas de dicho colectivo. Con cada pal´ e de tipo 1 se emplea una hora de este colectivo y con cada pal´ e2 se ocupan 3 horas del mismo. La empresa debe ocupar al menos 5 horas de mano de obra del colectivo citado. Si xi representa el n´ umero de unidades de pal´ es de tipo Pi , i = 1, 2, se puede construir el siguiente modelo de Programaci´ on Lineal para obtener la producci´ on que reporte un mayor beneficio. max z = 2x1 + x2

Formulaci´ on

sujeto a: 3x1 + 1x2 ≤ 30 4x1 + 3x2 ≤ 16 x1 + 2x2 ≥ 4 x1 + 3x2 ≥ 5

(5.1)

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

38

Este problema se puede reformular introduciendo variables de holgura, h1 , h2 , h3 y h4 que representan, respectivamente: h1 : el n´ umero de horas del taller T1 que no se llegan a utilizar. h2 : el n´ umero de horas del taller T2 que no se llegan a utilizar h3 : el n´ umero de productos entregados a los clientes por encima de la cantidad m´ınima pactada. h4 : el n´ umero de horas en la que el colectivo citado trabaja por encima del m´ınimo pactado con la admisnistraci´ on. max z = 2x1 + x2

Formulaci´ on equivalente

sujeto a: 3x1 + x2 + h1 = 30

(5.2)

4x1 + 3x2 + h2 = 16 x1 + 2x2 − h3 = 4 x1 + 3x2 − h4 = 5 La soluci´ on ´ optima de este problema queda descrita en la siguiente tabla

h1 h3 x1 x2

-70/9 167/9 5/9 11/3 4/9

x1 0 0 0 1 0

x2 0 0 0 0 1

h1 0 1 0 0 0

h2 -5/9 -8/9 1/9 1/3 -1/9

h3 0 0 1 0 0

La soluci´ on ´ptima o

h4 -2/9 -5/9 -5/9 1/3 -4/9

El plan ´ optimo consiste en lo siguiente.

Interpretaci´ on

Se montan, por t´ ermino medio, 11 pal´ es de tipo 1 cada tres semanas (x1 = 11/3) y se montan, por t´ ermino medio un 4 pal´ es de tipo 2 cada nueve semanas (x2 = 4/9) con lo que se obtiene un beneficio semanal de 7.78 u.m. h1 = 167/9, es decir, el taller T1 no est´ a ocupado todo el tiempo. De las 30 horas, est´ a ocioso un total de 18.56 horas. h2 = 0, es decir, el taller T2 est´ a ocupado las 16 horas en las que est´ a disponible cada semana. h3 = 5/9, es decir, se producen 0.56 pal´ es m´ as del m´ınimo comprometido. Es decir, se entregan 4.56 por t´ ermino medio cada semana. h4 = 0, es decir, el nivel de ocupaci´ on del colectivo al que se refiere el compromiso est´ a ocupado un n´ umero de horas igual al m´ınimo.

Uso de los recursos

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

39

La soluci´ on ´ optima se alcanza cuando las variables b´ asicas son h1 , h3 x1 y x2 . Es decir la base, B es la siguiente: ⎞ ⎛ 1 0 3 1 ⎟ ⎜   ⎜ 0 0 4 3 ⎟ ⎟ (5.3) B = Ah1 Ah3 Ax1 Ax2 = ⎜ ⎜ 0 −1 1 2 ⎟ ⎠ ⎝ 0 0 1 3

Caracterizaci´ on

5.2.

Tasas de sustituci´ on

5.2.1.

Discusi´ on te´ orica

Las tasas de sustituci´ on se definen como p B = B −1 A

Definici´ on

B relaciona la variable b´ asica que ocupa la posici´ on i-´ esima y la El elemento pij B variable j-´ esima del problema. En particular, pij representa en qu´ e medida disminuye el nivel de realizaci´ on de la actividad b´ asica i-´ esima cuando se realiza la actividad j-´ esima con valor unitario. De otra manera: B pij = −ΔuBi |xj =1 (5.4)

5.2.2.

Ejemplo de aplicaci´ on

En el ejemplo de aplicaci´ on, para la soluci´ on ´ optima, p B es la siguiente matriz: ⎛ ⎜ ⎜ pB = ⎜ ⎜ ⎝

0 0 1 0

0 0 0 1

1 0 0 0

−8/9 1/9 1/3 −1/9

0 1 0 0

−5/9 −5/9 1/3 −4/9

⎞ ⎟ ⎟ ⎟ ⎟ ⎠

(5.5)

Por ejemplo, las tasas de sutituci´ on de la variable h2 con respecto a las variables b´ asicas se discuten a continuaci´ on. Antes, conviene notar que h2 es una variable no b´ asica. Hacer que h2 = 1 significa que el taller T2 , que en la soluci´ on ´ optima est´ a ocupado al completo, tuviera una hora desocupada. En este caso, los valores de las variables b´ asicas se modificar´ıan de la siguiente manera. B p14 = −8/9 • Cuando h2 = 1, Δh1 = 8/9. • Es decir, al desocupar una hora de taller T2 , de dejan de utilizar 8/9 de hora m´ as con respecto a la cantidad que no se estaba utilizando de T1 . B p24 = 1/9

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

40

• Cuando h2 = 1, Δh3 = −1/9 • Es decir, al desocupar una hora de taller T2 , el n´ umero de productos que se entregan por encima del compromisio comercial disminuye en 1/9. B p34 = 1/3 • Cuando h2 = 1, Δx1 = −1/3 • Es decir, al desocupar una hora de taller T2 , se produce 1/3 de pal´ es de tipo 1 menos. B p44 = −1/9 • Cuando h2 = 1, Δx2 = 1/9 • Es decir, al desocupar una hora de taller T2 , se produce 1/9 de pal´ es de tipo 2 m´ as.

5.3.

5.3.1.

Multiplicadores del simplex

Discusi´ on te´ orica

El vector de multiplicadores del simplex (o precios sombra), π B se define como: π B = c B B −1

(5.6)

El vector de multiplicadores del simplex representa, para una soluci´ on determinada (es decir, para una base B determinada), el valor de los recursos. De otra manera: πiB representa el valor que tiene una unidad adicional de recurso Ri (es decir, un incremento unitario de b1 ). En efecto, como se cumple que: z = c B uB = c B B −1 b = π B b

(5.7)

Si Δbi = 1, es decir, si se incrementa la disponibilidad del recurso Ri en una unidad: ⎞⎞ ⎛ ⎛ 0 ⎜ 0 ⎟⎟ ⎜ ⎟⎟ ⎜ ⎜ ⎟⎟ ⎜ ⎜ ⎟⎟ ⎜ ⎜ ... ⎟⎟ ⎜ b + z = c B uB = c B B −1 b = π B ⎜ ⎜ 1 ⎟⎟ = ⎜ ⎟⎟ ⎜ ⎜ ⎟⎟ ⎜ ⎜ ⎝ ... ⎠⎠ ⎝ 0 (5.8) ⎞ ⎛ 0 ⎜ 0 ⎟ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ B B B B ⎜ ... ⎟ =π b+π ⎜ ⎟ = z + πi ⇒ Δz = πi ⎜ 1 ⎟ ⎟ ⎜ ⎝ ... ⎠ 0

Definici´ on

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

La relaci´ on que existe entre los multiplicadores del simplex y los valores de los criterios del simplex es la siguiente. El criterio del simplex de una variable de holgura, hi , correspondiente a una restricci´ on de tipo ≤ es: VhBi = chi − c B B −1 Ahi = chi − π B Ahi = ⎞ ⎛ 0 ⎜ 0 ⎟ ⎟ ⎜ ⎟ ⎜

(5.9) ⎟ ⎜ ... B B B B B ⎜ ⎟ = 0 − π1 , π2 , ..., πi , ..., πm ⎜ 1 ⎟ = −πi ⎟ ⎜ ⎟ ⎜ ⎝ ... ⎠ 0 El criterio del simplex de una variable de holgura, hi , correspondiente a una restricci´ on de tipo ≥ es: VhBi = chi − c B B −1 Ahi = chi − π B Ahi = ⎞ ⎛ 0 ⎜ 0 ⎟ ⎟ ⎜ ⎟

⎜ (5.10) ⎟ ⎜ ... B B ⎜ ⎟ = 0 − π1B , π2B , ..., πiB , ..., πm ⎜ −1 ⎟ = πi ⎟ ⎜ ⎟ ⎜ ⎝ ... ⎠ 0 En el caso de la soluci´ on ´ optima, V B ≤ 0 y, en particular, VhBi ≤ 0 En el caso de los recursos correspondientes a las restricciones de tipo ≤: • Si hi no es una variable b´ asica, la restricci´ on se cumple en t´ erminos de igualdad: hi = 0 ⇒ πiB = −VhBi ≥ 0. En este caso, un aumento de unitario positivo de b1 (relajar la restricci´ on) reporta un incremento del beneficio postivo Δz = π B y un incremento unitario negativo de b1 (hacer m´ as restrictiva la restricci´ on) reporta un incremento del beneficio negativo Δz = −π B . • Si hi es una variable b´ asica (salvo en casos especiales) la restricci´ on no se cumple en t´ erminos de igualdad: hi ≥ 0 ⇒ πiB = −VhBi = 0 En este caso, el incremento unitario positivo o negativo de la disponibilidad del recurso Ri no afecta a la funci´ on objetivo (Δz = 0) En el caso de los recursos correspondientes a las restricciones de tipo ≥: • Si hi no es una variable b´ asica, la restricci´ on se cumple en t´ erminos de igualdad: hi = 0 ⇒ πiB = VhBi ≤ 0. En este caso, un aumento de unitario negativo de b1 (hacer menos restrictiva la restricci´ on) reporta un incremento del beneficio postivo Δz = π B y un incremento unitario positivo de b1 (hacer m´ as restrictiva la restricci´ on) reporta un incremento del beneficio negativo Δz = −π B . • Si hi es una variable b´ asica (salvo en casos especiales) la restricci´ on no se cumple en t´ erminos de igualdad: hi ≥ 0 ⇒ πiB = −VhBi = 0

41

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

42

En este caso, el incremento unitario positivo o negativo de la disponibilidad del recurso Ri no afecta a la funci´ on objetivo (Δz = 0)

5.3.2.

Ejemplo de aplicaci´ on

El vector de multiplicadores del simplex (precios sombra) correspondiente a esta soluci´ on es: 

  5 2 π B = π1B , π2B , π3B , π4B = 0, , 0, − 9 9

(5.11)

Restricci´ on 1. El recurso R1 no se est´ a utilizando completamente. Como sobran horas de taller T1 , no estamos dispuestos a pagar nada por disponer de una hora adicional del mismo y ceder´ıamos una hora del mismo si nos dieran cualquier cantidad (positiva) por esa hora. Restricci´ on 2. El taller T2 se est´ a utilizando completamente. Estamos dispuestos a pagar un m´ aximo de 5/9 unidades monetarias por disponer de una hora adicional del mismo y ceder´ıamos una hora del mismo si nos dieran cualquier cantidad mayor que 5/9. Restricci´ on 3. Estamos cumpliendo el compromiso comercial por encima del m´ınimo pactado. No estamos dispuestos a pagar nada por tener que cumplir un compromiso menos exigente (y pasar de b3 = 4 a b3 = 3). Con cualquier cantidad que rec´ıbi´ eramos estar´ıamos dispuestos hacer m´ as exigente el compromiso comercial. Restricci´ on 4. Estamos cumpliendo el compromiso de la ocupaci´ on de la mano de obra de un colectivo con el menor valor posible. Estamos dispuestos a pagar 29 por tener que cumplir un compromiso menos exigente (y pasar de b4 = 5 a b4 = 4). Tambi´ en estamos dispuestos a recibir una 2 cantidad de dinero mayor 9 que para hacer m´ as exigente el compromiso comercial (y pasar de b4 = 5 a b4 = 6).

5.4.

5.4.1.

Criterios del simplex

Discusi´ on te´ orica

El criterio del Simplex se define como V B = c − c B B −1 A

Definici´ on (5.12)

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

43

En particular, el criterio del simplex de la variable xk es: VkB = ck − c B B −1 Ak

(5.13)

El criterio del Simplex, ya se vio en el cap´ıtulo 2, representa el incremento de la funci´ on objetivo cuando Δxk = 1. Es decir: VkB = Δz|xk =1

Primera aproximaci´ on

(5.14)

El primer t´ ermino ck representa el beneficio unitario que reporta la actividad xk . Existen dos formas de interpretar VkB :

ck

VkB = ck − c B pkB VkB = ck − π B Ak En ambos casos, se obtiene con la diferencia entre ck (beneficio unitario) y un t´ emino que puede interpretarse de dos maneras. El t´ ermino −c B pkB es el producto de: c B : que es el beneficio unitario correspondiente a las variables b´ asicas y −p B : el incremento de los valores de dichas variables b´ asicas. De forma que c B pkB representa lo que se deja de ganar por la cantidad en la que se modifican las variables b´ asicas. As´ı que VkB es el resultado de: aumentar el valor de la funci´ on objetivo por el beneficio derivado de hacer una unidad de la actividad k (xk = 1), es decir, por ingresar ck y disminuir la funci´ on objetivo por la modificaci´ on del ingreso debido a la modificaci´ on del valor de las variables b´ asicas −c B pkB . Por lo tanto, se puede concluir lo siguiente. Si V B > 0, el aumento de la funci´ on objetivo debido a la realizaci´ on de la nueva actividad supera a la reducci´ on de la funci´ on objetivo debida a la disminuci´ on de beneficios debida a la modificaci´ on del nivel de realizaci´ on de las variables b´ asicas. La realizaci´ on de la actividad k mejora netamente el valor de la funci´ on objetivo. Si V B < 0, el aumento de la funci´ on objetivo debido a la realizaci´ on de la nueva actividad no compensa la reducci´ on de la funci´ on objetivo debida a a la disminuci´ on de beneficios debida a la modificaci´ on del nivel de realizaci´ on de las variables b´ asicas. La realizaci´ on de la actividad k empeora netamente el valor de la funci´ on objetivo.

VkB = ck − c B pkB

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

44

Si V B = 0, la realizaci´ on de la actividad k no modifica el valor de la funci´ on objetivo. El t´ ermino π B Ak es el producto de:

VkB = ck − π B Ak

π B : que es valor de cada uno de los recursos y Ak : que es el consumo de cada uno de esos recursos en los que se incurre al realizar la actividad k, xk = 1. De forma que π B Ak es el valor de los recursos correspondientes a la realizaci´ on de una unidad de la actividad k. Es decir, hacer una unidad de la actividad k, significa consumir recursos que est´ an dedicados a otra actividades. El valor de esos recursos empleados en esas actividades es π B Ak , con lo que si se emplean en la actividad k y no en las correspondientes a las variables b´ asicas, la funci´ on objetivo se reducir´ıa en ese valor. As´ı que VkB es el resultado de: aumentar el la funci´ on objetivo por el beneficio ck , dervidado de hacer una unidad de la actividad k (xk = 1) y disminuir la funci´ on objetivo por el hecho de que se detraen recursos que antes estaban dedicados a realizar las actividades b´ asicas y cuyo valor es π B Ak . Por lo tanto, se puede concluir lo siguiente. Si V B > 0, el aumento de la funci´ on objetivo debido a la realizaci´ on de la nueva actividad supera a la reducci´ on del beneficio debida la detracci´ on de recursos que ya no se destinan a las actividades b´ asicas y que se destinan a realizar la actividad k. La realizaci´ on de la actividad k mejora netamente el valor de la funci´ on objetivo. Si V B < 0, el aumento de la funci´ on objetivo debido a la realizaci´ on de la nueva actividad no compensa la reducci´ ondel beneficio debida la detracci´ on de recursos que ya no se destinan a las actividades b´ asicas y que se destinan a realizar la actividad k. La realizaci´ on de la actividad k empeora netamente el valor de la funci´ on objetivo. Si V B = 0, la realizaci´ on de la actividad k no modifica el valor de la funci´ on objetivo.

5.4.2.

Ejemplo de aplicaci´ on

Como se ha dicho al principio del cap´ıtulo, la interpretaci´ on de los elementos que se han comentado es v´ alido y, en particular, en cualquier soluci´ on. A titulo de ilustraci´ on, a continuaci´ on se discute la interpretaci´ on del criterio del simplex de una variable para una soluci´ on diferente de la ´ optima. La discusi´ on, insistimos, podr´ıa realizarse igualmente para la soluci´ on ´ optima.

Presentaci´ on

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

h1 h2 h4 x2

x1 3/2 5/2 5/2 1/2 1/2

-2 28 10 1 2

x2 0 0 0 0 1

h1 0 1 0 0 0

h2 0 1 0 0 0

h3 1/2 1/2 3/2 -3/2 -1/2

h4 0 0 0 1 0

45

Otra soluci´ on

El criterio del simplex de la variable x1 se puede entender como la difencia entre el beneficio unitario por realizar la actividad correspondiente y c B p1B = π B A1 .

V1B

Con cualquiera de las dos posibles interpretaciones, c1 = 2, representa el beneficio unitario por realizar una unidad de la actividad 1, es decir por montar y vender un pal´ e de tipo 1.

c1

c B = (0, 0, 0, 1)   5 5 1 1 T , , , pB = 2 2 2 2

(5.15)

c B p1B

Al hacer una unidad de x1 : h1 disminuye en 52 unidades, cada una de las cuales ficio de ch2 = 0, con lo que dejamos de ganar 52 × 0. h2 disminuye en 52 unidades, cada una de las cuales ficio de ch2 = 0, con lo que dejamos de ganar 52 × 0. h4 disminuye en 12 unidades, cada una de las cuales ficio de ch2 = 0, con lo que dejamos de ganar 12 × 0. x2 disminuye en 12 unidades, cada una de las cuales ficio de ch2 = 1, con lo que dejamos de ganar 12 × 1. Es decir, dejamos de ganar

reportaba un benereportaba un benereportaba un benereportaba un bene-

1 2

Netamente:

V1B = c1 − c B p1B

El beneficio aumenta, por un lado en 2 y disminuye, por otro, en 12 , por lo que, globalmente, si hacemos un pal´ e de tipo 1, aumentamos el beneficio en V1B = 2 − 12 = 32 Se puede interpretar el valor de V2B en t´ erminos de π B

π B A1

´ TE ´ ´CNICO-ECONOMICA Cap´ıtulo 5. INTERPRETACION

π B = (0, 0, −1, 0) T  1 A1 = 3, 4, − , 0 2

46

(5.16)

Al hacer una unidad de x1 : Se consumen 3 unidades del recurso 1, es decir, se emplean 3 horas de taller T1 , cuyo valor es π1 = 0 (sobran horas). Se consumen 4 unidades del recurso 2, es decir, se emplean 4 horas de taller T2 , cuyo valor es π2 = 0 (sobran horas). Se “consume” 1 unidad del recurso 3. En este caso, esto significa contribuir con 1 unidad adicional al cumplimiento del compromiso comercial. Cada unidad en la que el cumplimiento comercial se hace m´ as restricitivo, esto deteriora la funci´ on objetivo en − 12 (esta soluci´ on se cumple exactamente al l´ımite (h3 = 0)). Fabricar un pale de tipo 1 provoca superar el compromiso comercial y eso deteriora la funci´ on objetivo en − 12 El razonamiento es an´ alogo para la cuarta restriccion, pero en este caso, ya se est´ a π4 = 0. Es decir, dejamos de ganar

1 2

Netamente: El beneficio aumenta, por un lado en 2 y disminuye, por otro, en 12 , por lo que, globalmente, si hacemos un pal´ e de tipo 1, aumentamos el beneficio en V1B = 12

V1B = c1 − π B A1

Cap´ıtulo 6 ´ GRA ´ FICA INTERPRETACION

6.1.

Introducci´ on

En este cap´ıtulo se presenta la interpretaci´ on gr´ afica en el plano de muchos de los conceptos presentados hasta ahora. Este cap´ıtulo no pretende ser un tratado exhaustivo de la geometr´ıa de los problemas de Programaci´ on Lineal.

Dos dimensiones

El objetivo es ilustrar dichos conceptos pero no ofrecer herramientas para el tratamiento de problemas de Programaci´ on Lineal.

Objetivo

Existe una forma de abordar lo que aqu´ı se presenta de forma muy somera ´til para el tratamiento y la resoconocida como teor´ıa de poliedros, s´ı resulta u luci´ on de problemas de Programaci´ on Lineal, pero que queda fuera del alcance de este texto.

Teor´ıa de poliedros

6.2.

Conceptos generales

Dado un problema de Programaci´ on lineal en el plano maz z =cx s.a: Ax = b

(6.1)

x≥0 x ∈ R+ 2×1 A ∈ Rm×2 c ∈ R1×2 b ∈ Rm×1 donde m es el n´ umero de restricciones

Dimensiones

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

En el ejemplo que sigue m = 2

48

Ejemplo max z = x1 + 2x2 sujeto a:

−2x1 + x2 ≤ 2

Restricci´ on R1

x1 + x2 ≤ 6

Restricci´ on R2

2x1 + x2 ≤ 10

Restricci´ on R3

(6.2)

x1 , x2 ≥ 0 En la figura 6.1, aparecen representadas las tres restricciones. Cada restricci´ on 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´ on y el otro semiplano a soluciones con factibles con respecto a la misma restricci´ on. El problema del ejemplo anterior se puede formular en t´ erminos de igualdad a˜ nadiendo las variables de holgura necesarias. max z = x1 + 2x2 sujeto a: −2x1 + x2 + h1 = 2 x1 + x2 + h2 = 6

(6.3)

2x1 + x2 + h3 = 10 x1 , x2 h1 h2 h3 ≥ 0 on Ri : Dado un punto cualquiera en el plano, P (x1 , x2 ) y una restricci´ Si este punto est´ a situado en el semimplano de soluciones factibles con respecto a Ri , entonces el P cumple la restricci´ on Ri y hi ≥ 0. En particular, puede estar sobre la propia recta, en cuyo caso, se cumple la restricci´ on con hi = 0 Si este punto est´ a situado en el semimplano de soluciones no factibles con respecto a Ri , entonces el P no cumple la restricci´ on Ri y hi < 0. Por ejemplo: El punto (4, 2) • Est´ a a la derecha de la recta R1 , el su semiplano factible, con lo que h1 > 0 • Est´ a sobre la recta R2 , con lo que h2 = 0 • Est´ a sobre la recta R3 , con lo que h3 = 0 El punto (1, 6) • Est´ a a la izquierda de la recta R1 , el su semiplano no factible, con lo que h1 < 0

Restricciones

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

49

• Est´ a a la derecha de la recta R2 , el su semiplano no factible, con lo que h2 < 0 • Est´ a a la izquierda de la recta R3 , el su semiplano factible, con lo que h3 > 0

Figura 6.1: Restricciones de un problema de Programaci´ on Lineal Las restricciones funcionales junto con las restricciones de no negatividad definen la regi´ on de factiblidad (sombreada en la figura 6.2). Cualquier punto perteneciente a la regi´ on de soluciones factibles cumple con todas las restricciones, incluidas las de no negatividad. La regi´ on de soluciones factibles siempre es un pol´ıgono y es una regi´ on convexa; es decir, para cualesquiera dos puntos de la soluci´ on de regiones factibles, todos los puntos pertenecientes al segmento que uno aquellos dos puntos tambi´ en est´ a dentro de la regi´ on de soluciones factibles.

Regi´ on de soluciones factibles

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

50

Figura 6.2: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal

La funci´ on objetivo de un problema de Programaci´ on lineal en el plano tiene la forma de z = c1 x1 + c2 x2 . Para cada valor de z tenemos una recta en particular, donde todos los puntos de dicha recta proporcionan el mismo valor de la funci´ on objetivo.

Funci´ on objetivo

La funci´ on objetivo se puede entender como un haz de rectas paralelas c1 x1 + c2 x2 = k.

Haz de rectas

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

51

Figura 6.3: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal

En el ejemplo del problema, la recta x1 + 2x2 = 14 es el conjunto de todas las soluciones que proporcionan un valor de la funci´ on objetivo de 14. Ninguno de los puntos de dicha recta est´ an en la regi´ on de soluciones factibles, por lo que no existe ninguna soluci´ on factible que proporcione un valor de z = 14. Lo mismo ocurre con z = 12.

Funci´ on objetivo

Sin embargo, la recta x1 + 2x2 = 6 s´ı tiene un segmento dentro de la regi´ on de factiblidad. Existe un conjunto de soluciones factibles que reportan un valor de z = 6, correspondiente a todos los puntos del segmento en el que la recta anterior intersecta con la regi´ on de soluciones factibles. Un problema en el plano tiene n variables (x1 , x2 y todas las variables de holgura correspondiente a restriciones leq o geq) y una soluci´ on b´ asica tiene m variables b´ asicas. En particular, en el caso de que todas las retricciones tengan variables de holgura, una soluci´ on b´ asica tiene: m variables b´ asicas y 2 variables no b´ asicas.

Soluciones b´ asicas

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

52

Figura 6.4: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal

Es decir en una soluci´ on b´ asica, como m´ınimo, debe haber dos variables nulas: x1 y x2 (la soluci´ on es el origen de coordenadas); x1 o x2 y una variable de holgura (la soluci´ o es la intersecci´ on la restricci´ on correspondiente con uno de los ejes); dos variables de holgura (la soluci´ on es la itersecci´ on de dos restricciones). Es decir, las soluciones b´ asicas de un problema de programaci´ on lineal son: el eje de coordenadas, cada una de las intersecciones de una restricci´ on 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 m+2 = gura, el problema tiene un n´ umero de soluciones b´ asicas igual m 2m2 + 2m − 4

N´ umero de soluciones b´ asicas

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

En el ejemplo, existen tres restricciones (m = 3), por lo que el n´ umero de 5 = 10, que aparecen indicadas en 6.4 soluciones b´ asicas es 2

Figura 6.5: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal De las soluciones b´ asicas anteriores, algunas son factibles (en azul) y otras son no factibles (en rojo). Y de las factibles, aquella que tiene una funci´ on objetivo mayor es la soluci´ on ´ optima del problema.

53

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

54

Figura 6.6: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal La interpretaci´ on gr´ afica del Teorema Fundamental es la siguiente. Dada cualquier soluci´ on no b´ asica (un punto interior del p´ ol´ıgono de soluciones factibles), es posible desplazarse hacia una soluci´ on en una restricci´ on (con una componente con un cero m´ as que la de partida) y, desde ella, a una soluci´ on b´ asica (con dos componentes nulas adicionales), siendo esta soluci´ on no peor que la de partida. En la figura 6.7 se muestra una soluci´ on no b´ asica x NB . Desde ella es posible desplazarse por m´ ultiples caminos hasta llegar a una soluci´ on b´ asica no pero NB que x . x NB , no est´ a sobre ninguna restricci´ on, ni sobre ning´ un eje, con lo que tiene cinco componentes no nulas (es decir, todas). Siguiendo el camino verde, nos desplazamos primero a una soluci´ on no b´ asica sobre el eje x1 (con una componente 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´ on b´ asica y mejor que la de partida. Igualmente, siguiendo el camino naranja, nos desplazamos primero a una soluci´ on no b´ asica sobre la restricci´ on R1 (con una componente nula adicional: h1 ). Y, desde ella es posible llegar a x 7 , en la que hay dos componentes nulas: h1 y h2 y tres no nulas: es una soluci´ on b´ asica y mejor que la de partida.

Teorema fundamental

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

55

Figura 6.7: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal

6.3.

M´ etodo del Simplex

El m´ etodo del Simplex, al cual se dedicaron los cap´ıtulos 2 y 3, opera transitando de soluci´ on b´ asica factible en soluci´ on b´ asica factible hasta llegar a una que es ´ optima. En la figura 6.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 soluci´ on ´ optima. Como se ha comentado antes, las soluci´ on b´ asicas son los v´ ertices del pol´ıgono de la regi´ on de factiblidad.

L´ ogica general

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

56

Figura 6.8: L´ ogica general del m´ etodo del Simplex

El criterio del simplex de la variable b´ asica xi , ViB representa el incremento unitario de la funci´ on objetivo si x1 . En la figura 6.9, considerando la soluci´ on 1 b´ asica x , las variables no b´ asicas de esa soluci´ on son x1 y x2 . Si partiendo de x 1 , hacemos que x1 = 1, ser´ıa equivalente a desplazarse por el eje de abscisas, hasta llegar al punto (1, 0). La funci´ on objetivo de este punto es z = 1. Igualemente, si partiendo de x 1 ahora hacemos que x2 = 1, ser´ıa equivalente a desplazarse por el eje de abscisas, hasta llegar al punto (0, 1). La funci´ on objetivo de este punto es z = 2. Es decir, V1B = 1 y V2B = 2. En efecto, tanto la introducci´ on de x1 como la de x2 en la base, a partir de x 1 , dan lugar a un incremento de la funci´ on objetivo, por lo que, seg´ un la regla de entrada, ambas son potenciales candidatas para obtener una nueva soluci´ on b´ asica factible, mejor que x 1

Regla de introducci´ on V B

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

57

Figura 6.9: Regi´ on de soluciones factibles de un problema de Programaci´ on Lineal El cada iteraci´ on del m´ etodo del simplex, se introduce una variable nueva en la base con un valor que hace que una de las que era b´ asica, se haga cero. Por ejemplo, si a partir de x 1 , decidimos que la variable x2 deje de ser cero, podemos acceder a tres nuevas soluciones b´ asicas: si x1 = 2, las variables b´ asicas son: x2 , h2 y h3 (soluci´ on b´ asica x 5 ) si x1 = 6, las variables b´ asicas son: x2 , h1 y h3 (soluci´ on b´ asica x 9 ) si x1 = 10, las variables b´ asicas son: x2 , h1 y h2 (soluci´ on b´ asica x 10 ) Lo anterior es lo esperado. Para el ejemplo anterior, en cada soluci´ on b´ asica existen tres variables b´ asicas y dos no b´ asicas, con lo que desde cada soluci´ on b´ asica, una vez decidida la variable de entrada, podemos acceder a otras tres soluciones b´ asicas suprimiendo de la base alguna de las tres las variables b´ asicas. En el ejemplo anterior, las tres soluciones a las que se puede acceder desde x1 son b´ asicas, pero solo una es factible. La regla de supresi´ on del m´ etodo del simplex garantiza que al introducir 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´ on b´ asica factible.

Regla de supresi´ on p B

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

Sabemos que una soluci´ on b´ asica es ´ optima si V B ≤ 0, es decir, si introduciendo cualquier variable no b´ asica la funci´ on objetivo disminuye. En el ejemplo, podemos apreciar en la figura 6.10 que la soluci´ on x 7 es ´ optima.

58

Criterio de optimalidad

Figura 6.10: Criterio de optimalidad

on de cada En efecto, las variables no b´ asicas de x 7 son h1 y h2 . La introducci´ una de ellas supone seguir desplazarse por las restricciones R2 y R1 , respectivamente, tal y como aparece en la imagen seg´ un las fechas rojas. Los valores de z para esas soluciones son peores que la de x 7 .

6.4.

M´ etodo de las dos fases y de la M grande

Pendiente

Problema auxiliar

Pendiente

Regiones de factibilidad de P y de P

Iteraciones del

Pendiente

problema P

Pendiente

Iteraciones del problema P

´ GRAFICA ´ Cap´ıtulo 6. INTERPRETACION

6.5.

59

M´ etodo de Lemke

Pendiente

L´ ogica general

Pendiente

Regla de supresi´ on V B

Pendiente

Regla de introducci´ on p B

Pendiente

Criterio de factiblidad

Cap´ıtulo 7 M´ ETODO DEL LEMKE

7.1.

Introduction

En el cap´ıtulo 2 se present´ o el m´ etodo del Simplex para resolver problemas de Programaci´ on Lineal. Este m´ etodo consist´ıa en, a partir de una soluci´ on b´ asica factible de partida, de forma iterativa, transitar por diferentes soluci´ on b´ asicas factibles hasta alcanzar una que tambi´ en fuera ´ optima.

Introducci´ on

L´ ogica del m´ etodo del Simplex

Figura 7.1: L´ ogica del m´ etodo del Simplex En este cap´ıtulo se va a presentar el m´ etodo de Lemke, o dual del Simplex, que tambi´ en permite resolver problemas de Programaci´ on Lineal. En este m´ etodo consist´ıa en, a partir de una soluci´ on b´ asica que cumple el criterio de optimalidad (V B ≤ 0) de partida, de forma iterativa, se transita por diferentes soluci´ on b´ asicas que tambi´ en cumplen el criterio de optimalidad hasta alcanzar una que tambi´ en es factible. Al respecto de las diferencias y las analog´ıas entre los dos m´ etodos: El ambos m´ etodos siempre se transita de soluci´ on b´ asica en soluci´ on b´ asica. Las soluciones por las que transita el m´ etodo del Simplex siempre son factibles. Las soluciones por las que transita el m´ etodo del Lemke siempre cumplen el criterio de optimalidad.

L´ ogica del m´ etodo de Lemke

´TODO DEL LEMKE Cap´ıtulo 7. ME

61

En el m´ etodo del Simplex, con las diferentes iteraciones, se mejora el criterio de optimalidad hasta alcanzar una soluci´ on ´ optima (que tambi´ en es factible). En el m´ etodo del Simplex, con las diferentes iteraciones, se mejora el criterio de factiblidad hasta alcanzar una soluci´ on factible (que tambi´ en es ´ optima).

Figura 7.2: L´ ogica del m´ etodo de Lemke Para aplicar el m´ etodo de Lemke, de acuerdo con la l´ ogica anterior, es necesario: 1. 2. 3. 4.

una soluci´ on b´ asica que cumpla el criterio de optimalidad de partida, un criterio de factiblidad, una regla de supresi´ on y una regla de introducci´ on.

7.2.

Cu´ ando es interesante el m´ etodo de Lemke

El m´ etodo de Lemke es potencialmente interesante cuando existe una soluci´ on b´ asica que cumple el criterio de optimalidad, pero que no es factible. A continuaci´ on se discuten tres casos habituales.

7.2.1.

Problemas de m´ınimos con c ≥ 0

Los problemas que cumplen con las siguientes caracter´ısticas: La funci´ on objetivo es de la forma min. z = cx con c ≥ 0. Todas las restricciones son de tipo ≤ o ≥.

Qu´ e necesitamos

´TODO DEL LEMKE Cap´ıtulo 7. ME

Por ejemplo, un problema como el siguiente.

62

Ejemplo

min. z =1x1 + 2x2 + 3x3 1x1 + 2x2 + 1x3 ≥ 10 4x1 + 2x2 + 3x3 ≥ 20

(7.1)

1x1 + x2 + x3 ≤ 40 xi ≥ 0 En efecto: Si un problema es del tipo min. z = cx con c ≥ 0, se puede transfomar en uno equivalente del tipo max. (−z) = −cx con c ≤ 0. Al a˜ nadir las variables de holgura a todas y cada una de las restricciones (ninguna es originalmente de tipo =), existe una soluci´ on b´ asica en la que hi = bi .

 0 0 ... 0 Para dicha soluci´ on c B = y, por lo tanto: V B = c −

 c B B −1 A = c − 0 0 ... 0 B −1 A = c ≤ 0 Es decir, la soluci´ on en la que las variables b´ asicas son las variables de holgura es una soluci´ on que cumple el criterio de optimalidad y es b´ asica, con lo cual es una soluci´ on a partir de la cual se puede aplicar el m´ etodo del ejemplo. El problema de 7.1 se puede formular como:

Ejemplo

max. z = − 1x1 − 2x2 − 3x3 − 1x1 − 2x2 − 1x3 + h1 = −10 − 4x1 − 2x2 − 3x3 + h2 = −20

(7.2)

1x1 + x2 + x3 + h3 = 40 xi , hi ≥ 0 Si las variables b´ asicas son h1 , h2 y h3 :

 cB = 0 0 0 .



 V B = c − c B B −1 A = −1 −2 −3 0 0 0 − 0 0 0 B −1 A =

 −1 −2 −3 0 0 0 . Es decir, V B ≤ 0. Por lo tanto, esta soluci´ on es b´ asica, cumple el criterio de optimalidad y no es factible: es una soluci´ on de partida v´ alidad para aplicar el m´ etodo de Lemke.

´TODO DEL LEMKE Cap´ıtulo 7. ME

La tabla inicial a partir de la cual se podr´ıa comenzar a iterar, tal y como se describe m´ as adelante ser´ıa la siguiente. x1 -1 -1 -4 1

0 -10 -20 40

7.2.2.

x2 -2 -2 -2 1

x3 -3 -1 -3 1

h1 0 1 0 0

h2 0 0 1 0

h3 0 0 0 1

63

La tabla inicial

La tabla inicial

Al introducir un cambio en b, una vez obtenida la soluci´ on ´ptima o

Dado un problema P del que se ha obtenido la soluci´ on ´ optima, si cambia el vector de disponibilidad de recursos b, se modificar´ıan: uB = B −1 b zB = c B uB

Y no se modfiicar´ıa: VB pB Si el cambio de b hace que alg´ un uBi sea negativo, la soluci´ on que era ´ optima y factible deja de ser factible y sigue siendo cumpliendo V B ≤ 0, por lo que es una soluci´ on a partir de la cual se puede aplicar el m´ etodo de Lemke. Para el problema de ejemplo del cap´ıtulo 3, en el ep´ıgrafe 3.3 maz z =1x1 + 2x2 + 3x3

Ejemplo

1x1 + 2x2 + 1x3 + x4 = 16 3x1 − 2x2 + 2x3 + x5 = 26 1x1 + 0x2 + 2x3 + x6 = 24 xi ≤ 0, i = 1 · · · 6 Se conoce la soluci´ on ´ optima

x2 x5 x3

-40 2 6 12

x1 -1 1 4 5 2 1 2

x2 0 1 0 0

x3 0 0 0 1

x4 -1 1 2

1 0

x5 0 0 1 0

x6 -1 − 14 − 32 1 2

(7.3)

´TODO DEL LEMKE Cap´ıtulo 7. ME

Si el nuevo vector fuera b = siguiente.

⎛

10

1 2

⎜ uB = B −1 b = ⎜ ⎝ 1 0 El nuevo valor de z ser´ıa c B uB =

26

24

T

, el nuevo valor de uB ser´ıa el

0 1 0

⎞⎛ ⎞ ⎛ ⎞ − 14 10 −1 ⎟ ⎜ ⎟ ⎜ ⎟ − 32 ⎟ ⎠ ⎝ 26 ⎠ = ⎝ 0 ⎠ 1 24 12 2

2

0

3



−1

0

12

T

(7.4)

= 34

La nueva tabla cuando las variables b´ asicas son x2 , x5 y x3 es la siguiente:

x2 x5 x3

-34 -1 0 12

x1 -1 1 4 5 2 1 2

x2 0 1 0 0

x3 0 0 0 1

x4 -1 1 2

1 0

x5 0 0 1 0

x6 -1 − 14 − 32 1 2

A partir de esa tabla se podr´ıa iterar aplicando el m´ etodo de Lemke, tal y como se comenta m´ as adelante en el cap´ıtulo.

7.2.3.

Al a˜ nadir una restricci´ on adicional a un programa, una vez obtenida la soluci´ on ´ optima

Pendiente

7.3.

7.3.1.

Reglas

Criterio de factibilidad

Una solucion b´ asica (base B) es factible si uB ≥ 0

7.3.2.

Regla de supresi´ on

Dada una soluci´ on b´ asica no factible interesa eliminar de la base cualquier variable con valor negativo. En particular, eliminaremos la variable i-´ esima que cumple.

64

´TODO DEL LEMKE Cap´ıtulo 7. ME     uBi = maxuB 0 ik

VkB

(7.6)

B pik

Si, en general, entra la variable j-´ esima del problema, los nuevos criterios del Simplex son: VkB

=

VkB −

pik B B Vj pij

(7.7)

Para garantizar que con la nueva base, se sigue cumpliendo el criterio de optimalidad se debe cumplir 7.6.

VkB

7.4.

=

VkB −

B pik B pij

VjB ≤ 0 ⇒ VkB ≤

B pik B pij

VjB ⇒

VkB B pik

≥

VjB B pij

B dado que pik ≤0

(7.8)

Ejemplo min. z =300x1 + 400x2 + 100x3 + 50x4

El problema

4x1 + 5x2 + 2x3 + x4 ≥ 800 2x1 + 4x2 + x3 ≥ 600

(7.9)

1x1 + x2 + 4x4 ≤ 2000 xi ≥ 0 Problema equivalente max. (−z) = − 300x1 − 400x2 − 100x3 − 50x4 − 4x1 − 5x2 − 2x3 − x4 ≤ −800 − 2x1 − 4x2 − x3 ≤ −600 1x1 + x2 + 4x4 ≤ 2000 xi , hi ≥ 0

(7.10)

´TODO DEL LEMKE Cap´ıtulo 7. ME

Problema equivalente max. (−z) = − 300x1 − 400x2 − 100x3 − 50x4 − 4x1 − 5x2 − 2x3 − x4 + h1 = −800 − 2x1 − 4x2 − x3 + h2 = −600

(7.11)

1x1 + x2 + 4x4 + h3 = 2000 xi , hi ≥ 0

h1 h2 h3 x3 h2 h3 x3 x2 h3

0 -800 -600 2000 40000 400 -200 2000 60000

x1 -300 -4 -2 1 -100 2 0 1 -100

x2 -400 -5 -4 1 -150

1 0

x3 -100 -2 -1 0 0 1 0 0 0

200 3 400 3 5600 3

2 0 1

0 1 0

1 0 0

5 2 − 32

x4 -50 -1 0 4 0

0 -50

h1 0 1 0 0 -50 − 12 − 12 0 0

h2 0 0 1 0 0 0 1 0 -100

h3 0 0 0 1 0 0 0 1 0

4 3 − 13 13 3

− 43 − 13 − 13

5 3 − 23 2 3

0 0 1

1 2 1 2

F0 F1 F2 F3 F0 = F0 + 100F1

F1 = −F1 /2 F2 = F2 + F1

F3 = F3 F0

= F0 + 150F2

F1

= F1 − 5/2F2

F2

= −2/3F2

F3

= F3 − F2

66

Cap´ıtulo 8 CASOS ESPECIALES

8.1.

Introducci´ on

Pendiente

8.2.

´ Optimo m´ ultiple

´ptima Dado un problema de programaci´ on lineal, P , se conoce una soluci´ on o b´ asica y factible, x B , asociada a una base B. Si una variable no b´ asica, xk , es tal que VkB = 0, existe la posiblidad de introducir dicha variable en la base1 y:

Caracterizaci´ on anal´ıtica

se obtiene una soluci´ on b´ asica, x B diferente de la anterior (con otra base B y con el mismo valor de la funci´ on objetivo.

asicas y ´ optiLas dos soluciones b´ asicas anteriores x B y x B son soluciones b´ mas del problema P

Adem´ as, todas las soluciones del tipo x = λx B + (1 − λ)x B con λ ∈ (0, 1) son soluciones no b´ asicas y ´ optimas del problema.

Soluciones no ´ptimas b´ asicas o

En general, pueden existir r soluciones b´ asicas factibles (x B1 , x B2 ...x Br ) y ´ optir r mas y todas las soluciones de la forma s=1 λs x Bs , con s=1 λs = 1

Generalizaci´ on

En el plano, existen soluciones ´ optimas m´ ultiples cuando la funci´ on objetivo es paralela a la restricci´ on que contiene dos soluciones b´ asicas factibles y ´ optimas.

Interpretaci´ on gr´ afica

Cap´ıtulo 8. CASOS ESPECIALES

68

Figura 8.1: Soluciones ´ optimas m´ ultiples

max. z = 3x1 + 4x2

Ejemplo

3x1 + 4x2 ≤ 12 x2 ≤ 2

(8.1)

x1 − x2 ≤ 1 x1 , x2 ≥ 0

1 Esto es as´ ı siempre. Si existen variables b´ asicas con tasas de sustituci´ on positiva con respecto

a la que abandone la base. Si todas las tasas de sustituci´ on son negativas a xk , una de ellas ser´ se trata de un caso que se describe en la secci´ on 8.5

Soluciones ´ptima b´ o asicas

Cap´ıtulo 8. CASOS ESPECIALES

x1 x2 h3

-12 4/3 2 7/6

x1 0 1 0 0

x2 0 0 1 0

h1 -1 1/3 0 -1/3

h2 0 -4/3 1 7/3

h3 0 0 0 1

x1 x2 h2

-12 16/7 9/7 5/7

0 1 0 0

0 0 1 0

-1 1/7 1/7 -1/7

0 0 0 1

0 4/7 -3/7 3/7

Existen dos soluciones ´ optimas que son b´ asicas:

Soluciones ´ptimas o

T

x = (4/3, 2, 0, 0, 0, 7/6) x 2 = (16/7, 9/7, 0, 5/7, 0)T 1

69

Y todas las siguientes que son no b´ asicas: x NB = λ (4/3, 2, 0, 0, 0, 7/6)T + T (1 − λ) (16/7, 9/7, 0, 5/7, 0) , con λ ∈ (0, 1) Para todas ellas, z = 12

8.3.

Soluci´ on degenerada

Se dice que una soluci´ on b´ asica es degenerada si alguna de las variables b´ asicas toma valor 0, es decir, alg´ un uBi = 0 max. z = x1 + 4x2 2x1 + 3x2 ≤ 6

(8.2)

x1 + 2x2 ≤ 4

Caracterizaci´ on anal´ıtica Ejemplo Interpretaci´ on gr´ afica

x1 , x2 ≥ 0

x2 h2

-8 2 0

x1 -5/3 2/3 -1/3

x2 0 1 0

h1 -4/3 1/3 -2/3

h2 0 0 1

x2 h1

-8 2 0

-1 1/2 1/2

0 1 0

0 0 1

-2 1/2 -3/2

x2 x1

-8 2 0

0 0 1

0 1 0

2 -1 2

-5 2 -3

Soluci´ on del problema

Cap´ıtulo 8. CASOS ESPECIALES

70

Figura 8.2: Soluci´ on degenerada

Las tres soluciones b´ asicas son la misma, todas corresponden a x = T on. (0, 2, 0, 0) . Se trata de tres bases que conducen a la misma soluci´

8.4.

Problema no factible

Cuando se aplica el m´ etodo del Simplex para resolver el problema auxiliar correspondiente al m´ etodo de las dos fases o de la M grande, el problema original no tiene soluci´ on factible si para todas las soluciones ´ optimas del problema auxiliar existe al menos una variable artificial diferente de 0.

Caracterizaci´ on anal´ıtica. Simplex

Cuando se aplica el m´ etodo de Lemke, se puede concluir que el problema no tiene soluci´ on factible si para se llega a una soluci´ on en la que para todas las variables b´ asicas negativas, todas las tasas de sustituciones de las variables no b´ asicas con respecto a dichas variables b´ asicas son positivas.

Caracterizaci´ on anal´ıtica. Lemke

Cap´ıtulo 8. CASOS ESPECIALES

71

Figura 8.3: Problema sin soluci´ on factible

min. z = 2x1 + 3x2 = max. (−z) = −2x1 − 3x2 x1 + 2x2 ≤ 1 x1 + x2 ≥ 3

Ejemplo (8.3)

x1 , x2 ≥ 0 Esta ser´ıa la tabla a la que se llegar´ıa aplicando el m´ etodo de las dos fases.

x1 a2

2 1 2

x1 0 1 0

x2 -1 2 -1

h2 -1 0 -1

h1 -1 1 -1

Al aplicar Lemke se iterar´ıa de la siguiente manera

a2 0 0 1

Aplicando las dos fases

Aplicando Lemke

Cap´ıtulo 8. CASOS ESPECIALES

8.5.

h1 h2

0 1 -3

x1 -2 1 -1

x2 -3 2 -1

h1 0 1 0

h2 0 0 1

0 h1 x1

0 -2 3

-1 0 1

0 1 1

-2 1 0

1 -1

72

Regi´ on de factibilidad no acotada

B ´ptima existe una variable, xk , no b´ Si en la soluci´ on o asica, y pik ≤ 0 para todas las variables b´ asicas (i = 1...m), entonces si al aumentar el valor de xk aumenta el valor de todas las variables b´ asicas, con lo que la regi´ on de soluciones factibles no est´ a acotada.

Caracterizaci´ on anal´ıtica

Si el VkB ≤ 0, a pesar de que es posible introducir esta variable, con el consiguiente incremento de todas las variables b´ asicas, la introducci´ on de xk no ´nica. resulta interesante, con lo que la soluci´ on ´ optima es u

´ptima Soluci´ on o ´ nica u

max. z = −x1 + x2

Ejemplo

−x1 + 2x2 ≤ 6

(8.4)

−2x1 + 2x2 ≤ 0 x1 , x2 ≥ 0

x1 x2

-2/3 2/3 4/3

x1 0 1 0

x2 0 0 1

h1 -1/3 1/3 2/3

h2 -1/3 -2/3 -1/3

Soluci´ on del problema

Si el VkB = 0, es posible introducir esta variable, con el consiguiente incremento de todas las variables b´ asicas, la introducci´ on de xk no altera el valor de la funci´ on objetivo con lo que existen soluciones ´ optimas m´ ultiples. max. z = −2x1 + 4x2 −x1 + 2x2 ≤ 6 −2x1 + 2x2 ≤ 0 x1 , x2 ≥ 0

Soluciones ´ptimas o m´ ultiples Ejemplo

(8.5)

Cap´ıtulo 8. CASOS ESPECIALES

73

´nica Figura 8.4: Regi´ on de factibilidad no actodada con soluci´ on ´ optima y u

x1 x2

-4 2/3 4/3

x1 0 1 0

x2 0 0 1

h1 -2 1/3 2/3

h2 0 -2/3 -1/3

Si el VkB ≥ 0, es posible introducir esta variable, con el consiguiente incremento de todas las variables b´ asicas y el incremento de z, con lo que el problema no est´ a acotado y no se puede hablar de soluci´ on ´ optima.

Soluci´ on del problema

z no acotada

Cap´ıtulo 8. CASOS ESPECIALES

Figura 8.5: Regi´ on de factibilidad no actodada con soluci´ on ´ optimas m´ ultiples

Figura 8.6: Regi´ on de factibilidad no actodada con funci´ on objetivo no actodada

74

Cap´ıtulo 8. CASOS ESPECIALES

max. z = 3x1 + x2

75

Ejemplo

−x1 + 2x2 ≤ 6

(8.6)

−2x1 + 2x2 ≤ 0 x1 , x2 ≥ 0

x1 x2

-21/3 2/3 4/3

x1 0 1 0

x2 0 0 1

h1 -8/3 1/3 2/3

h2 10/3 -2/3 -1/3

Soluci´ on del problema

Cap´ıtulo 9 ´ POSTOPTIMIZACION

9.1.

Introduction

Dado un problema de PL: max z = cx Ax = b

(9.1)

x≥0 Una vez otenida la soluci´ on ´ optima x ∗ , podr´ıan producirse cambios en el problema, que pueden hacer que la x ∗ deje de ser la soluci´ on ´ optima. En particular, puede cambiar: 1. b 2. c 3. Aparici´ on de una nueva actividad (una nueva columna en A y una nueva componente en c) 4. Aparici´ on de una nueva restricci´ on (una nueva fila en A y una nueva componente en b) 5. Cambio en aij

9.2.

Cambio en b

Si el vector de disponibilidad de recursos cambia, b , cambia: 1. u B = B −1 b

2. z = c B u B No cambia 1. 2. 3. 4.

B B −1 p B = B −1 A V B = c − c B B −1 A. En particular, al tratarse de la soluci´ on ´ optima V B ≤ 0

´ Cap´ıtulo 9. POSTOPTIMIZACION

La soluci´ on puede dejar de ser factible, si alg´ un u i < 0. En an´ alisis consiste en

B recalcular u : on sigue siendo factible y, como V B ≤ 0, las varia1. Si u B i ≥ 0 ∀i la soluci´ bles b´ asicas son las mismas, con un nuevo nivel de realizaci´ on u B y un

nuevo valor de la funci´ on objetivo z 2. Si ∃u B < 0 la soluci´ o n deja de ser factible pero cumple el criterio de opi timalidad, V B ≤ 0. Se debe aplicar el m´ etodo de Lemke hasta obtener una soluci´ on que adem´ as de cumplir el crierio de optimalidad sea factible, la nueva soluci´ on ´ optima, que tendr´ a un conjunto de variables b´ asicas de las de la soluci´ on original.

9.3.

Cambio en c

Si el vector de contribuciones unitarias al beneficio, c , cambia: 1. z = c B uB 2. V B = c − c B B −1 A No cambia: 1. 2. 3. 4.

B B −1 p B = B −1 A uB = B −1 b. En particular, como la soluci´ on era factible uB ≥ 0

La soluci´ on puede dejar de ser ´ optima, si alg´ un Vi B > 0. En an´ alisis consiste en recalcular V B : ´ptima y, como uB ≥ 0, las variaon sigue siendo o 1. Si Vj B ≤ 0 ∀j la soluci´ bles b´ asicas son las mismas, con el mismo nivel de realizaci´ on uB y un

nuevo valor de la funci´ on objetivo z 2. Si ∃Vj B > 0 la soluci´ on deja de ser ´ optima pero sigue siendo factible, uB ≥ 0: se debe aplicar el m´ etodo de Simplex hasta obtener una soluci´ on que adem´ as de ser factible cumpla el crierio de optimalidad, la nueva soluci´ on ´ optima, que tendr´ a un conjunto de variables b´ asicas de las de la soluci´ on original. Si solo cambia una componente de c, se pueden dar dos situaciones: 1. Cambia ck y xk no es variable b´ asica. Solo cambia VkB , con lo que esta actividad, que no era b´ asica, al cambiar VkB pordr´ıa ocurrir que VkB ≥ 0, en cuyo caso la soluci´ on original no ser´ıa ´ optima. 2. Cambia ck y xk es variable b´ asica, con lo que cambiar´ıa todo V B .

77

´ Cap´ıtulo 9. POSTOPTIMIZACION

9.4.

Nueva actividad

Una actividad k queda caracterizada por: on unitaria al beneficio de dicha actividad y 1. ck la contribuci´ 2. Ak el consumo que hace dicha actividad de cada uno de los recursos. Con la aparici´ on de una nueva actividad, la soluci´ on ´ optima del problema puede ser la misma o puede ser otra mejor. Es decir, si interesa realizar dicha actividad, ser´ a porque la soluci´ on a la que se llegar´ a ser´ a mejor. Si no interesa realizar dicha actividad, la mejor soluci´ on ser´ a la obtenida para el problema antes de introducir dicha actividad. En efecto, con la introducci´ on de una nueva actividad, se debe calcular el criterio del simples VkB la variable correspondiente xk . ´ptima y no interesa realizar dicha Si VkB ≤ 0 la soluci´ on sigue siendo o actividad. Si VkB > 0, la soluci´ on deja de ser ´ optima porque la introducci´ on de la nueva actividad representa una oportunidad de mejora. Se debe aplicar el m´ etodo del Simplex hasta alcanzar la soluci´ on ´ optima

9.5.

Nueva restricci´ on

Una restricci´ on l queda caracterizada por: on unitaria al beneficio de dicha actividad y 1. bl la contribuci´ 2. alj el consumo que hacen todas las actividades del nuevo recurso y 3. el signo de la desigualdad En el caso de una restriccion de igualdad o de desigualdad se convierte en una de igualdad con la variable de holgura correspondiente 

alj xj ≤ bl

j

 j



alj xj + hl = bl

j

alj xj ≥ bl



alj xj − hl = bl

(9.2)

j

En el caso de una restricci´ on de tipo igual, es equivalente a dos: una de con ≤ y otra con lgeq:

78

´ Cap´ıtulo 9. POSTOPTIMIZACION

 j

⎧  ⎨ a x  j lj j alj xj = bl equivalente a alj xj l ⎩ j alj xj

(9.3)

j

Con la aparici´ on de una nueva restricci´ on, la soluci´ on ´ optima del problema puede ser la misma o puede ser otra peor. Es decir: ´ptima original cumple la nueva restricci´ si la soluci´ on o on, la soluci´ on ´ptima seguir´ o a siendo factible y tambi´ en ´ optima, es decir, la soluci´ on ´ optima no cambiar´ a; si la soluci´ on ´ optima obtenida no cumple con la nueva restricci´ on, la soluci´ on seguir´ a dejar´ a de ser factible y habr´ a que obtener una nueva soluci´ on factible y ´ optima, peor que la original. Cuando aparece una nueva restricci´ on, la forma de obtener la nueva soluci´ on factible sin resolver el problema desde el principio consiste en: 1. Introducir en la tabla de la soluci´ on ´ optima final la nueva restricci´ on tal y como habr´ıa aparecido en la primera tabla y 2. operar con las filas para conseguir ceros en la matriz p B donde deber´ıa haberlos (esto se explica en el ejemplo final, 9.7.4).

9.6.

Cambio en aij

Se pueden dar dos situaciones, que la variable xj sea b´ asica o que no.

9.6.1.

Cambio en aij con xj no b´ asica

Si cambia aij y xj es una variable no b´ asica, cambia: 1. Vj B = cj − c B B −1 Aj 2. pj B = B −1 Aj

No cambia: 1. 2. 3. 4. 5. 6.

B B −1 z = c B uB VkB , k ≠ j (no cambia el criterio del simplex del resto de variables b´ asicas) pk B = B −1 A k k ≠ j u B = B −1 b

79

´ Cap´ıtulo 9. POSTOPTIMIZACION

Solo cambia VjB , con lo que: si VjB > 0 interesa realizar dicha actividad , en cuyo caso habr´ıa que aplicar el m´ etodo del Simplex y xj entrar´ıa en la base en la primera iteraci´ on. Se deber´ıa iterar hasta alcanzar la nueva soluci´ on ´ optima; si VjB ≤ 0 no interesa introducir la variable xj en la base y la soluci´ on ´ optima no var´ıa.

9.6.2.

Cambio en aij con xj b´ asica

Si cambia aij y xj es una variable b´ asica, cambia: 1. 2. 3. 4. 5. 6.

B

B −1 u B = B −1 b z = c B u B V B = c − c B B −1 A

p B = B −1 A

Se pueden dar cuatro situaciones, ligadas a la p´ erdida o no de las condiciones de soluci´ on factible y de soluci´ on ´ optima. La tabla siguiente resume los casos que se pueden dar: V’B ≤ 0 Soluci´ on ´ optima Lemke

u’B ≥ 0 ∃uB ≤ 0

9.7.

∃V B ≥ 0 Simplex -

Ejemplo max z = x1 + 2x2 + 3x3 sujeto a: x1 + x2 + x3 ≤ 16

(9.4)

3x1 + 2x2 + 2x3 = 26 x1 + x3 ≥ 10

Tabla correspondiente a la soluci´ on ´ optima.

h1 h3 x3

-39 3 3 13

x1 -7/2 -1/2 1/2 3/2

x2 -1 0 1 1

x3 0 0 0 1

h3 0 0 1 0

h1 0 1 0 0

a2 -3/2 -1/2 1/2 1/2

a3 0 0 -1 0

80

´ Cap´ıtulo 9. POSTOPTIMIZACION

9.7.1.

Cambio de b

Supongamos que b =

B

cas, u

14

22

T

11

. El nuevo valor de las variables b´ asi-

ser´ıa: ⎛

u B

⎞ ⎞ ⎛ ⎞⎛ 3 14 0 ⎟ ⎟ ⎜ ⎟⎜ −1 ⎠ ⎝ 22 ⎠ = ⎝ 0 ⎠ 11 11 0

−1/2 1/2 1/2

1 ⎜ = B −1 b = ⎝ 0 0

(9.5)

La soluci´ on sigue siendo factible y ´ optima. Supongamos que b =

B

cas, u

12

26

T

11

. El nuevo valor de las variables b´ asi-

ser´ıa: ⎛

u B

⎞⎛ ⎞ ⎛ ⎞ 0 12 −1 ⎟⎜ ⎟ ⎜ ⎟ −1 ⎠ ⎝ 26 ⎠ = ⎝ 2 ⎠ 0 11 13

−1/2 1/2 1/2

1 ⎜ = B −1 b = ⎝ 0 0

La soluci´ on ya no es factible y es necesario aplicar Lemke.

9.7.2.

h1 h3 x3

-39 -1 2 13

x1 -7/2 -1/2 1/2 3/2

x1 h3 x3

-32 2 1 10

0 1 0 0

x2 -1 0 1 1

x3 0 0 0 1

h3 0 0 1 0

h1 0 1 0 0

a2 -3/2 -1/2 1/2 1/2

a3 0 0 -1 0

-1 0 1 1

0 0 0 1

0 0 1 0

-7 -2 1 3

2 1 0 -1

0 0 -1 0

Cambio de c

Supongamos que c =

2

2

4

0

0



El nuevo valor del vector de criterios del Simplex, V B ser´ıa:

(9.6)

81

´ Cap´ıtulo 9. POSTOPTIMIZACION

2

2

4

0

0



−

0

0

4



⎛

−1/2 ⎜ ⎝ 1/2 3/2

0 1 1

0 0 1

0 1 0

82

V ‘B = c − c B B −1 A =

⎞

1

⎟ 0 ⎠ = −4 0

−2

0

0

0



(9.7) La soluci´ on sigue siendo factible y ´ optima. Supongamos que c =

6

1

3

0

0



El nuevo valor del vector de criterios del Simplex, V B ser´ıa:

6

1

3

0

0



−

0

0

3



⎛

−1/2 ⎜ ⎝ 1/2 3/2

0 1 1

0 0 1

0 1 0

V ‘B = c − c B B −1 A =

⎞

1

⎟ 0 ⎠ = 3/2 0

−2

0

(9.8) La soluci´ on ya no es ´ optima y es necesario aplicar el m´ etodo del Simplex.

9.7.3.

h1 h3 x3

-39 3 3 13

x1 3/2 -1/2 1/2 3/2

x2 -2 0 1 1

x3 0 0 0 1

h3 0 0 1 0

h1 0 1 0 0

a2 -3/2 -1/2 1/2 1/2

a3 0 0 -1 0

h1 x1 x3

-48 6 6 4

0 0 1 0

-5 1 2 -2

0 0 0 1

-3 1 2 -3

0 1 0 0

-3 0 1 -1

3 -1 -2 3

Nueva actividad

Existe la posiblidad de realizar una nueva actividad, x4 y se sabe que: c4 = 5

A4 = 1

1

1

T

0

0



´ Cap´ıtulo 9. POSTOPTIMIZACION

El criterio del simplex de la nueva actividad es: V4B = c4 − c B B −1 A4 = c4 − π B A4 ⎛ ⎞

 1 ⎜ ⎟ 5 − 0 3/2 0 ⎝ 1 ⎠ = 7/2 1

(9.9)

La soluci´ on ya no es ´ optima y es necesario aplicar el m´ etodo del Simplex. Para reutilizar la tabla, es necesario calcular p4B

⎛

1 ⎜ ⎝ 0 0

9.7.4.

−1/2 1/2 1/2

p4B = B −1 A4 ⎞ ⎛ 0 1 1/2 ⎟⎜ ⎟ ⎜ −1 ⎠ ⎝ 1 ⎠ = ⎝ −1/2 0 1 1/2 ⎞⎛

= ⎞ (9.10)

⎟ ⎠

h1 h3 x3

-39 3 3 13

x1 3/2 -1/2 1/2 3/2

x2 -2 0 1 1

x3 0 0 0 1

x4 7/2 1/2 -1/2 1/2

h3 0 0 1 0

h1 0 1 0 0

a2 -3/2 -1/2 1/2 1/2

a3 0 0 -1 0

x4 h3 x3

-60 6 6 10

0 -1 0 2

-1 0 1 1

0 0 0 1

0 1 0 0

0 0 1 0

-7 2 1 -1

2 -1 0 1

0 0 -1 0

Nueva restricci´ on

Supongamos que aparece la siguiente nueva restricci´ on x1 + x3 ≤ 15

(9.11)

on sigue siendo factible y ´ optima. Como x2 + x3 = 0 + 13 ≤ 15, la soluci´ Supongamos que aparece la siguiente nueva restricci´ on x2 + x3 ≤ 10

(9.12)

83

´ Cap´ıtulo 9. POSTOPTIMIZACION

84

Como x2 + x3 = 0 + 13  10, la soluci´ on ´ optima ya no cumple esta nueva restricci´ on, con lo que ya no es soluci´ on factible del nuevo problema. La restricci´ on se puede formular como: x2 + x3 − h4 = 10

h4

-39 3 3 13 10 -3

x1 -7/2 -1/2 1/2 3/2 0 -3/2

x2 -1 0 1 1 1 0

x3 0 0 0 1 1 0

h3 0 0 1 0 0 0

h1 0 1 0 0 0 0

h4 0 0 0 0 1 1

a2 -3/2 -1/2 1/2 1/2 1/2 -1/2

a3 0 0 -1 0 0 0

h1 h3 x3 x1

-32 4 2 10 2

0 0 0 0 1

-1 0 1 1 0

0 0 0 1 0

0 0 1 0 0

0 1 0 0 0

7/3 -1/3 1/3 1 -2/3

2 1 0 -1 1/3

0 0 -1 0 0

h1 h3 x3

9.7.5. Si b =

(9.13)

An´ alisis de sensibilidad de b

b1

26

10

T

, el nuevo valor de las variables b´ asicas, u B ser´ıa: ⎛

1 ⎜ uB = B −1 b = ⎝ 0 0 ⎛

−1/2 1/2 1/2

⎞ ⎞⎛ 0 b1 ⎟ ⎟⎜ −1 ⎠ ⎝ 26 ⎠ = 10 0 ⎞

b1 − 13 ⎟ ⎜ 3 ⎠ ≥ 0 ⇒ b1 ≥ 13 ⎝ 13

Si b =

16

b2

10

T

⎞⎛ ⎞ 1 −1/2 0 16 ⎜ ⎟⎜ ⎟ 1/2 −1 ⎠ ⎝ b2 ⎠ = uB = B −1 b = ⎝ 0 0 1/2 0 10 ⎞ ⎛ 16 − b2 /2 ⎟ ⎜ ⎝ b2 /2 − 10 ⎠ ≥ 0 ⇒ 20 ≤ b2 ≤ 32 b2 /2 (9.15)

(9.14)

, el nuevo valor de las variables b´ asicas, u B ser´ıa: ⎛

An´ alisis b1

An´ alisis b2

´ Cap´ıtulo 9. POSTOPTIMIZACION

Si b =

16

26

b3

T

, el nuevo valor de las variables b´ asicas, u B ser´ıa: ⎛

1 ⎜ uB = B −1 b = ⎝ 0 0 ⎛

−1/2 1/2 1/2

85

An´ alisis b3

⎞⎛ ⎞ 0 16 ⎟⎜ ⎟ −1 ⎠ ⎝ 26 ⎠ = 0 b3 ⎞

3 ⎟ ⎜ ⎝ 13 − b3 ⎠ ≥ 0 ⇒ b3 ≤ 13 13

(9.16)

Resumen 13 ≤ b1 < ∞ 20 ≤ b2 ≤ 32

(9.17)

−∞ < b3 ≤ 13

9.7.6.

An´ alisis de sensibilidad de c

Variable x1 . Variable no b´ asica

V1B = c1 − π B a2 = c1 −

0

An´ alisis c1

3/2

0



⎞ 1 ⎟ ⎜ ⎝ 3 ⎠ = c1 − 9/2 ≤ 0 ⇒ c1 ≤ 9/2 1 ⎛

(9.18) Variable x2 . Variable no b´ asica

V2B = c2 − π B a3 = c2 −

0

An´ alisis c2

3/2

0



⎛

⎞ 1 ⎜ ⎟ ⎝ 2 ⎠ = c2 − 3 ≤ 0 ⇒ c2 ≤ 3 0

(9.19)

Variable x3 . Variable b´ asica

An´ alisis c3

V B = c − c B B −1 A = ⎞ 

 −1/2 0 0 0 1 ⎜ ⎟ 0 − 0 0 c3 ⎝ 1/2 1 0 1 0 ⎠= 3/2 1 1 0 0 

1 − 3/2c2 2 − c3 0 0 0 ≤ 0 ⇒ c3 ≥ 2 ⎛

1

2

c3

0

(9.20)

´ Cap´ıtulo 9. POSTOPTIMIZACION

Resumen −∞ < c1 ≤ 4,5 −∞ < c2 ≤ 3 2 ≤ c3 < ∞

(9.21)

86

´ Cap´ıtulo 9. POSTOPTIMIZACION

9.8.

La aparente paradoja de b

Dado el problema max z = x1 + 3x2 x1 + 2x2 ≤ 20

(9.22)

2x1 + x2 ≥ 20 x1, x2 ≥ 0 La tabla del simplex correspondiente a la soluci´ on ´ optima es:

x2 x1

-80/3 20/3 20/3

x1 0 0 1

x2 0 1 0

h1 -5/3 2/3 -1/3

h2 -1/3 1/3 -2/3

Si realizamos en an´ alisis de sensibilidad con respecto a b1 , el resultado es el siguiente:      b1 2b1 − 20 2/3 −1/3 1 uB = B −1 b = = ≥ 0 ⇒ 10 ≤ b1 ≤ 40 −1/3 2/3 −b2 + 40 20 3 (9.23) on Es decir, si la disponibilidad el recurso R1 (b1 ) es superior a 40, la soluci´ no es factible. ¿C´ omo puede ser que si aumentamos la disponibilidad de un recurso de una restricci´ on de tipo ≤ la soluci´ on se haga no factible?

87

Cap´ıtulo 10 ´ PARAM´ PROGRAMACION ETRICA

10.1.

Introducci´ on

10.2.

Programaci´ on con c(λ)

10.2.1.

M´ etodo general

Procedimiento general: Tras la resoluci´ on para un valor de λ0 1. C´ alculo de uB (λ0 ) 2. C´ alculo del λ1 y λ2 , tal que uB ≤ 0 si λ1 ≤ λ ≤ λ2 3. Para λ1 (´ıdem para λ2 ) a) si λ1 es −∞ (si λ2 es ∞), no hay valores menores (mayores) de λ que analizar. b) en caso contrario: obtener la degenerada para λ = λ1 : 1) Si es posible aplicar el m´ etodo del Lemke, iterar para obtener otra base de la misma soluci´ on degenerada y volver al punto 1. 2) Si no es posible aplicar el m´ etodo del Lemke, es que no hay soluci´ on factible fuera del valor de λ extremo estudiado.

10.2.2.

Ejemplo c(λ) max z = 5x1 + 6x2 + 8x3 s.a. 2x1 + 3x2 + 4x3 ≤ 25 3x1 + 2x2 + 1x3 = 20 x1 , x2 , x3 ≥ 0

(10.1)

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

-111/2 7/2 11/2

x3 x1

x1 0 0 1

x2 -1/2 1/2 1/2

x3 0 1 0

h1 -19/10 3/10 -1/10

89

a -2/5 -1/5 2/5

Sea c1 = λ, si λ = 5, T0 es la tabla correspondiente a la soluci´ on ´ optima. A continuaci´ on vamos a realizar el an´ alisis para c(λ) = 0≤λ≤∞

λ

6

8



, , con

Si λ modifica su valor, se modificar´ a el vector de criterios del Simplex V B (λ). B Siempre y cuando V (λ) ≤ 0 las actividades b´ asicas ser´ an x1 y x3 , con los niveles de realizaci´ on de la tabla T0 . El criterio del Simplex V B (λ) es:

B

B

V (λ) = c − c B

−1

B

A=c−c p =

λ

6

8

0



−

8

λ





0 1

1/2 1/2

1 0

0

4−λ 2

3/10 −1/10

(10.2) Las variables b´ asicas son x1 y x3 siempre y cuando V B (λ). Es decir:

4−λ≤0 ⇒ 4 ≤ λ ≤ 24 λ − 24 ≤ 0

(10.3)

Si 4 ≤ λ ≤ 24, la tabla corresondiente a la soluci´ on ´ optima es T0 (λ): T0 (λ) x3 x1

−28 − 11λ 2 7/2 11/2

x1 0 0 1

x2 4−λ 2 1/2 1/2

x3 0 1 0

h1 λ−24 10 3/10 -1/10

´ptimo m´ Si λ = 4, la tabla se convierte en T1 , correspondiente a un o ultiple. Introduciendo x2 y sacando x3 se obtiene una nueva soluci´ on a la que le corresponde la tabla T2

0



λ−24 10

= 

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

T1 x3 x1 T2 x2 x1

-50 7/2 11/2 -50 7 2

x1 0 0 1 x1 0 0 1

x2 0 1/2 1/2 x2 0 1 0

x3 0 1 0 x3 0 2 -1

90

h1 -2 3/10 -1/10 h1 -2 3/5 -2/5

Si λ modifica su valor, se modificar´ a el vector de criterios del Simplex V B (λ). Siempre y cuando V B (λ) ≤ 0 las actividades b´ asicas ser´ an x1 y x2 , con los niveles de realizaci´ on de la tabla T2 . El criterio del Simplex V B (λ) es:

V B (λ) = c − c B B −1 A = c − c B p =

λ

6

8

0



−

6

λ





0 1

1 0

2 −1

3/5 −2/5

0

0

λ−4 (10.4)

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´ asicas con x1 y x2 . Existe aqu´ı una aparente contradicci´ on 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´ asica porque deteriora notablemente la funci´ on 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´ on final. La explicaci´ on es la siguiente. Si las variables b´ asicas con x1 y x2 (aun cuando c1 = λ 24 En resumen: Variables b´ asicas: x1 = 2 y x2 = 7 si λ ≤ 4 con z = 42 + 2λ Variables b´ asicas: x1 = 11/2 y x3 = 7/2 si 4 ≤ λ ≤ 24 con z = 28 + 11λ/2 Variables b´ asicas: x1 = 20/3 y h1 = 35/3 si 24 ≥ λ con z = 20λ/3

1 0

 = 0)



´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

10.3.

Programaci´ on con b(λ)

10.3.1.

M´ etodo general

Procedimiento general: 1. 2. 3. 4.

Resoluci´ on para un valor de λ0 C´ alculo de V B (λ0 ) C´ alculo del λ1 y λ2 , tal que V B ≤ 0 si λ1 ≤ λ ≤ λ2 Para λ1 (´ıdem para λ2 ) a) si λ1 es −∞ (si λ2 es ∞), no hay valores menores (mayores) de λ que analizar. b) en caso contrario: obtener la soluci´ on ´ optima m´ ultiple para λ = λ1 : 1) Si es posible aplicar el m´ etodo del Simplex, obtener una soluci´ on ´ optima b´ asica alternativa y volver al punto 1. 2) Si no es posible aplicar el m´ etodo del Simplex, es que no hay soluci´ on factible fuera del valor de λ extremo estudiado.

10.3.2.

Ejemplo c(λ) max z = 3x1 + 4x2 + 2x3 + 3x4 s.a. 30x1 + 10x2 + 10x3 + 15x4 ≤ 120

(10.6)

50x1 + 50x2 + 30x3 + 30x4 ≤ 150 x1 , x2 , x3 , x3 ≥ 0 x1 -2 5 5/3

T0 h1 x4 b(λ) =

120 − λ

-15 45 5 150 + λ 

B

u (λ) = B

−1

b(λ) =

1 0

x2 -1 -15 5/3

x3 -1 -5 1

x4 0 0 1

h1 0 1 0

h2 -1/10 -1/2 1/30

T

−1/2 1/30



120 − λ 150 + λ



 =

45 − 3λ/2 5 + λ/30

 (10.7)

92

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

La siguiente tabla es v´ alida si uB ≥ 0. Es decir, si −150 ≤ λ ≤ 30 T0 (λ) h1 x4

x1 -2 5 5/3

-15 45-3λ/2 5-λ/30

x2 -1 -15 5/3

x3 -1 -5 1

x4 0 0 1

h1 0 1 0

h2 -1/10 -1/2 -1/30

Si λ = 30 T0 (λ = 30) h1 x4

-18 0 6

x1 -2 5 5/3

x2 -1 -15 5/3

x3 -1 -5 1

x4 0 0 1

h1 0 1 0

h2 -1/10 -1/2 -1/30

T1 (λ = 30) x2 x4

-18 0 6

-7/3 -1/3 20/9

0 1 0

-2/3 1/3 4/9

0 0 1

-1/60 -2/30 1/9

-1/60 1/30 -2/90

 B

u (λ) = B

−1

b(λ) =

−1/60 1/9

1/30 −2/90





120 − λ 150 + λ

 =

(−30 + λ)/10 (900 − 12λ)/90



(10.8) La siguiente tabla es v´ alida si uB ≥ 0. Es decir, si 30 ≤ λ ≤ 75 T1 (λ) -18 (-30+λ)/10 (900-12λ)/90

x2 x4

x1 -7/3 -1/3 20/9

x2 0 1 0

x3 -2/3 1/3 4/9

x4 0 0 1

h1 -1/60 -2/30 1/9

h2 -1/60 1/30 -2/90

Si λ = 75 T1 (λ = 75) x2 x4

-18 9/2 0

x1 -7/3 -1/3 20/9

x2 0 1 0

x3 -2/3 1/3 4/9

x4 0 0 1

h1 -1/60 -2/30 1/9

h2 -1/60 1/30 -2/90

T2 (λ = 75) x2 h2

-18 9/2 0

-9 3 -100

0 1 0

-2 1 20

-3 3/2 -45

-2/5 1/10 -5

0 0 1

93

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

 B

u (λ) = B

−1

b(λ) =

−1/10 −5

0 1



120 − λ 150 + λ



 =

(−120 + λ)/10 6λ − 450



(10.9) La siguiente tabla es v´ alida si uB ≥ 0. Es decir, si 75 ≤ λ ≤ 120 T2 (λ) x2 h2

-18 (-120+λ)/10 6λ − 450

-9 3 -100

0 1 0

-2 1 20

-3 3/2 -45

-2/5 1/10 -5

0 0 1

Para λ > 120 no existe soluci´ on factible del problema. En resumen: No existe soluci´ on factible para λ < −150 Variables b´ asicas: h1 = 45 − 3λ 2 y x4 = 5 + Variables b´ asicas: x2 =

λ 30 si −150 ≤ λ ≤ 900−12λ si 30 ≤ λ ≤ 75 90

30

−30+λ y x4 = 10 −120+λ y h2 = 10

Variables b´ asicas: x2 = 6λ − 450 si 75 ≤ λ ≤ 120 No existe soluci´ on factible para λ > 120

10.4.

Ejemplo c(λ) y b(λ) max z = 2x1 + 4x2 + x3 s.a. 2x1 + 5x2 + 1x3 ≤ 40

(10.10)

x1 + 4x2 + 2x3 ≤ 24 x1 , x2 , x3 ≥ 0 b(λ) = c(λ) =



40 2

24 − 3λ 4+λ

1

T

y

0

0



, co λ ≥ 0

Soluci´ on ´ optima para λ = 0

x1 x3

-40 56/3 8/3

x1 0 1 0

x2 -1 2 1

x3 0 0 1

h1 -1 2/3 -1/3

h2 0 -1/3 2/3

94

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

2

4+λ

1

0

0

 uB (λ) = B −1 b(λ) =



−

2/3 −1/3

2

V B (λ) = c − c B B −1 A = c − c B p B =    1 2 0 2/3 −1/3 1 = 0 1 1 −1/3 2/3

 0 λ − 1 0 −1 0

−1/3 2/3



40 24 − 3λ

 =

1 3



56 + 3λ 8 − 6λ

(10.11)

 (10.12)

VB ≤ 0 ⇒ λ ≤ 1

(10.13)

4 3

(10.14)

uB ≥ 0 ⇒ λ ≤

La condici´ on m´ as restricitiva es λ ≤ 1, ya que cuando esto ocurre, el problema tiene dos soluciones b´ asicas ´ optimas factibles. Con λ > 1, las soluciones en las que x1 y x3 son variables b´ asicas son no factibles. A continuaci´ on figuran tres tablas, correspondientes, respectivamente a la soluci´ on b´ asica con x1 y x3 en funci´ on de λ, la tabla para λ = 1 y la soluci´ on b´ asica ´ optima alternativa para ese valor de λ.

2

4+λ

x1 x3

(56 + 3λ)/3 (8 − 6λ)/3

x1 0 1 0

x1 x3

-40 59/3 2/3

0 1 0

0 2 1

0 0 1

-1 2/3 -1/3

0 -1/3 2/3

x1 x2

-40 55/3 2/3

0 1 0

0 0 1

0 -2 1

-1 4/3 -1/3

0 -5/3 2/3

1

0

x2 λ−1 2 1

x3 0 0 1

h1 -1 2/3 -1/3

h2 0 -1/3 2/3

V B (λ) = c − c B B −1 A = c − c B p B =   

 1 0 −2 4/3 −5/3 0 − 2 4+λ = 0 1 1 −1/3 2/3

 0 0 1 − λ (λ − 4)/3 (2 − 2λ)/3) (10.15)

95

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

 B

u (λ) = B

−1

b(λ) =

4/3 −1/3

−5/3 2/3



40 24 − 3λ



1 = 3



40 + 15λ 8 − 6λ



(10.16)

VB ≤ 0 ⇒ 1 ≤ λ ≤ 4

(10.17)

4 3

(10.18)

uB ≥ 0 ⇒ −3/8λ ≤

Por lo tanto, para que las variables b´ asicas x1 y x2 conduzcan a una soluci´ on ´ptima y factible 1 ≤ λ ≤ 43 . El extremo inferior de este intervalo coincide, nao turalmente, con el extremo superior del intervalo obtenido para las soluciones b´ asicas con x1 y x3 . 4

4

Con λ = 3 se obtiene una soluci´ on degenerada. Con λ > 3 se obtiene una soluci´ on b´ asica no factible, por lo que deja de ser la soluci´ on ´ optima y factible del problema. A continuaci´ on figuran las siguientes tres tablas: la correspondiente a x1 y x2 como variables b´ asicas, en funci´ on de λ, la anterior con λ = 43 y la soluci´ on obtenida al aplicar Lemke a patir de la anterior.

x1 x2

(40 + 15λ)/3 (8 − 6λ)/3

x1 0 1 0

x1 x2

40 0

0 1 0

0 0 1

-1/3 -2 1

-8/9 4/3 -1/3

-2/9 -5/3 2/3

40 0

0 1 0

-8/3 4 -3

-3 2 -3

0 0 1

-2 1 -2

x1 h1

2

4+λ

1

0

x2 0 0 1

x3 1−λ -2 1

h1 (λ − 4)/3 4/3 -1/3

h2 (2-2λ)/3 -5/3 2/3

V B (λ) = c − c B B −1 A = c − c B p B =   

 1 4 2 0 1 0 − 2 0 = 0 −3 −3 1 −2

 0 −4 + λ −3 0 −2

(10.19)

96

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

 B

u (λ) = B

−1

b(λ) =

0 1

1 −2



40 24 − 3λ



 =

24 − 3λ −8 + 6λ

VB ≤ 0 ⇒ λ ≤ 4

uB ≥ 0 ⇒

 (10.20)

(10.21)

4 ≤λ≤8 3

(10.22)

on Por lo tanto, para que las variables b´ asicas x1 y h2 conduzcan a una soluci´ 4 ´ optima y factible 3 ≤ λ ≤ 4. El extremo inferior de este intervalo coincide, naturalmente, con el extremo superior del intervalo obtenido para las soluciones b´ asicas con x1 y x2 . Con λ = 4 se obtiene una soluci´ on degenerada. Con λ > 4 se obtiene una soluci´ on b´ asica no ´ optima, por lo que deja de ser la soluci´ on ´ optima y factible del problema. A continuaci´ on figuran las siguientes tres tablas: la correspondiente a x1 y h1 como variables b´ asicas, en funci´ on de λ, la anterior con λ = 4 y la soluci´ on obtenida al aplicar el m´ etodo del Simplex a patir de la anterior.

24 − 3λ 8 + 6λ

x1 0 1 0

x2 −4 + λ 4 -3

x3 -3 2 -3

h1 0 0 1

h2 -2 1 -2

x1 h1

12 16

0 1 0

0 4 -3

-3 2 -3

0 0 1

-2 1 -2

x2 h1

3 25

0 1/4 3/4

0 1 0

-3 1/2 -3/2

0 0 1

-2 1/4 -5/4

x1 h1

2

4+λ

1

0

0



−

4+λ

V B (λ) = c − c B B −1 A = c − c B p B =    1/4 1 1/2 0 1/4 0 = 3/4 0 −3/2 1 −5/4

 1 − λ4 0 −1 − λ2 0 −1 − λ4 (10.23)

97

´ PARAME ´TRICA Cap´ıtulo 10. PROGRAMACION

 B

u (λ) = B

−1

b(λ) =

0 1

1/4 −5/4



40 24 − 3λ



1 = 4



24 − 3λ 40 + 15λ

 (10.24)

V B ≤ 0∀λ ≥ 4

(10.25)

uB ≥ 0 ⇒ λ ≤ 8

(10.26)

Por lo tanto, para que las variables b´ asicas x2 y h1 conduzcan a una soluci´ on ´ptima y factible 4 ≤ λ ≤ 8. El extremo inferior de este intervalo coincide, nao turalmente, con el extremo superior del intervalo obtenido para las soluciones b´ asicas con x1 y x2 . Con λ = 8 se obtiene una soluci´ on degenerada. Con λ > 8 se obtiene una soluci´ on b´ asica no ´ optima, por lo que deja de ser la soluci´ on ´ optima y factible del problema. A continuaci´ on figuran las siguientes dos tablas: la correspondiente a x2 y h1 como variables b´ asicas, en funci´ on de λ, la anterior con λ = 8. Se observa que para la variable x2 no existen tasas de sustituci´ on negativas, con lo que si λ > 4 no existe soluci´ on factible, porque no es posible que x2 salga de la base.

x2 h1

(24 − 3λ)/4 (40 + 15λ/4

x1 1 − λ4 1/4 3/4

x2 h1

0 40

-1 1/4 3/4

x2 0 1 0

x3 −1 − λ2 1/2 -3/2

h1 0 0 1

h2 −1 − λ4 1/4 -5/4

0 1 0

-5 1/2 -3/2

0 0 1

-3 1/4 -5/4

En resumen: Variables b´ asicas: x1 = (56 + 3λ)/3 y x3 = (8 − 6λ)/3 si 0 ≤ λ ≤ 1 Variables b´ asicas: x1 = (45 + 15λ)/3 y x2 = (8 − 6λ)/3 si 1 ≤ λ ≤ 4/3 Variables b´ asicas: x1 = 24 − 3λ y h1 = −8 + 6λ si 4/3 ≤ λ ≤ 4 Variables b´ asicas: x1 = (24 − 3λ)/4 y h2 = (40 + 15λ)/4 si 4 ≤ λ ≤ 8 No existe soluci´ on factible para λ > 8

98

Cap´ıtulo 11 ´ TRANSPORTE Y ASIGNACION

11.1.

11.1.1.

Presentaci´ on del problema de transporte

Introducci´ on

Se trata de un caso particular de PL

11.1.2.

Formulaci´ on

Dados un conjunto de or´ıgenes (O), cada uno de los cuales tiene asociada una capacidad Oi (unidades de producto) un conjunto de destinos (D), cada uno de los cuales tiene una demanda asociada Dj (unidades de producto) y el coste Cij asociado a transportar una unidad de producto del origen i ∈ O al destino j ∈ D el problema consiste en determinar las cantidades transportadas desde el origen i ∈ O al destino j ∈ D con el m´ınimo coste, xij . max z =



Cij xij

ij

s.a.



xij ≤ Oi ∀i ∈ O

j∈D



xij ≥ Dj ∀j ∈ D

i∈O

xij ≥ 0 ∀j ∈ D, ∀i ∈ O Problemas equilibrados:

 i∈D

Oi =

 j∈D

Dj

(11.1)

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

100

Formulaci´ on equivalente, si el problema est´ a equilibrado  Cij xij max z = ij

s.a.



xij = Oi ∀i ∈ O

(11.2)

j∈D



xij = Dj ∀j ∈ D

i∈

xij ≥ 0 ∀j ∈ D, ∀i ∈ O

11.1.3.

Presentaci´ on matricial

La formulaci´ on extendida de 11.2 max z = s.a. x11

+x12

...

+x1J +x21

x22

+x2J

...

+x21

x11 x12

x22 ...

... +x1J

+x2J

... ... ... ... ... ... ...

+xI1 +xI1

+xI2

...

+xIJ +xIJ

+xI2 ... +xIJ

= = = = = = =

O1 O2 OI D1 D2 DJ

xij ≥ 0 ∀j ∈ D, ∀i ∈ O (11.3) De acuerdo con max z = cx s.a.

(11.4)

Ax = b x≥0 Las matrices son: ⎛ ⎜ ⎜ ⎜ ⎜ A=⎜ ⎜ ⎜ ⎜ ⎝

1 0 0 ... 0 I

0 1 0 ... 0 I

0 0 1 ... 0 I

... ... ... ... ... ...

0 0 0 ... 1 I

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

(11.5)

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.

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION ⎛ ⎜ ⎜ ⎜ ⎜ b=⎜ ⎜ ⎜ ⎜ ⎝

c=

11.1.4.

C11

...

CI1

⎞

O1 ... OI D1 ... DJ ...

101

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

Cij

(11.6)

c1J

...CIJ



(11.7)

Representaci´ on del problema

Representaci´ on tabular espec´ıfica, diferente, por ejemplo, de la matriz completa del m´ etodo del simplex

destino 1 c11 x11

c11 ... ci1 xi1

cij ... cI1 xI1

cI1

origen 1

origen i

origen J

...

destino j

...

c1j ...

x1j

...

...

...

...

...

xij

...

x1jJ

cij

...

...

xIj

...

cIj

x1J

1. Si el problema es equilibrado, existe al menos una soluci´ on factible: xij = OD  i j j∈D Dj

Oj

cIJ

Las propiedades..

=

cij

...

Propiedades

OD  i j i∈O Oi

O1

...

donde cij es el coste reducido asociado al a variable xij , que se presentar´ a m´ as adelante.

11.1.5.

c1J

ciJ

cIj ...

x1J

c1j

cij ...

destino J cIJ

En efecto, cumple las restricciones:

cIj

OJ

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

max z =



Cij xij

ij

 

xij

i∈O

s.a.

Oi Dj j∈D Dj  = Oi  = Oi ∀i ∈ O D j∈D j j∈D Dj j∈D   Oi Dj Oi  = = Dj i∈O = Dj ∀j ∈ D O i i∈O i∈O Oi i∈O

xij =

j∈D





(11.8)

2. La base de cualquier soluci´ on, B es una matriz unimodular y los elementos de B −1 son 0, 1 o -1. 3. El n´ umero de restricciones linealmente independientes es car d(O) + car d(D) − 1 11.1.5.1. Propiedades de las soluciones b´ asicas El n´ umero de variables b´ asicas es igual al n´ umero de restricciones linealmente independientes es car d(O) + car d(D) − 1 ´nico ciclo (pasarela) Existe al menos uno: Dada una soluci´ on existe un u cualquier actividad no b´ asica se puede obtener como combinaci´ on linea de las b´ asicas Existe solo uno: solo hay una forma de combinar linealmente actividades b´ asicas Las celdas de una soluci´ on b´ asica no permiten formar ciclos: no se pueden combinar linealmente Las tasas de sustituci´ on son 1, −1 o 0

11.2.

M´ etodos de resoluci´ on

Si el problema se formula como PE, el car´ acter unimodular de la base garantiza que el la soluci´ on de la relajaci´ on lineal siempre es entera. Adem´ as de cualquier m´ etodo general de PL, dos atlernativas: 1. Stepping-stone 2. MODI Procedimiento: 1. Soluci´ on inicial de partida. Para esto existen diferentes m´ etodos 2. Criterio de optimalidad. En este paso es donde se diferencian los m´ etodos de Stepping-stone y MODI 3. Regla de entrada 4. Regla de salida

102

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

11.2.1.

Obtenci´ on del soluci´ on inicial de partida

M´ etodos Rinc´ on NO M´ınimo coste Voguel Otros Diferente esfuerzo y diferente calidad de la soluci´ on de partida

11.2.2.

Regla de entrada. Stepping-stone

11.2.3.

Regla de entrada. MODI

Las restricciones convenientemente modificadas se pueden exprear como: 

Oi −

xij = 0 ∀i ∈ O

j∈D

Dj −



(11.9)

xij = 0 ∀j ∈ D

i∈

Se definen ui y vi A su vez, a la funci´ on objetivo se le pueden sumar los t´ erminos nulos, que son los primeros miembros de las dos expresiones anteriors y, posteriormente, se puede operar: ⎛ ⎞ ⎛ ⎞       z= Cij xij = Cij xij − ui ⎝Oi − xij ⎠ − vj ⎝Dj − xij ⎠ = ij

ij

i

j

=



j

Oi Dj +

ij



i

xij (cij − ui − vj )

ij

(11.10) Por lo tanto, la funci´ on ojetivo se puede expresar como la suma de dos t´ ermiB a las vanos, uno constante y otro que depende de xij . Si se denota con xij

−B riables b´ asicas y xij a las no basicas, el t´ ermino variable se puede reformular como:    B −B xij (cij − ui − vj ) = xij (cij − ui − vj ) + xij (cij − ui − vj ) (11.11) ij

ij

ij

Se pueden elegir los valores de ui y vi de tal manera que cij − ui − vj = 0 si la variable xij es b´ asica. De esta manera, la expresi´ on 11.11 es estrictamente −B nula. El primer t´ ermino lo es por que cij − ui − vj = 0 y el segundo porque xij al tratarse de variables b´ asicas.

103

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

Por lo tanto, si una variable no b´ asica entra a formar parte de la soluci´ on, el

incremento de la funci´ on objetivo es, precisamente, el valor de cij = cij − ui − vj . Es decir Δz|Δx −B =1 = cij − ui − vj ij

11.2.4.

Regla de salida

11.2.5.

Criterio de optimalidad

(11.12)

Sean como sean calculados, el coste reducido cij representa la reducci´ on unitaria de la funci´ on objetiva al introducir con valor 1 la variable no b´ asica xij ,

por lo que la soluci´ on es ´ optima si cij ≥ 0, ∀j ∈ D, ∀i ∈ O

11.3.

11.3.1.

Problemas desequilibrados

Oferta superior a demanda

Es necesario introducir un destino ficticio d∗ . El problema se redefine sobre un conjunto D∗ = D ∪ {d∗ }. La variable xid∗ representa la capacidad no utilizada del origen i ∈ O. En la representaci´ on tabular, de incorpora una fila m´ as. Los costes de las nuevas variables son...

11.3.2.

Demanda superior a oferta

Es necesario introducir un destino ficticio o∗ . El problema se redefine sobre un conjunto O∗ = O ∪ {o∗ }. La variable xo∗ j representa la demanda no atendida del destino j ∈ D. En la representaci´ on tabular, de incorpora una columna m´ as. Los costes de las nuevas variables son...

11.4.

Soluciones degeneradas

104

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

11.5.

Transporte y dualidad

El dual del problema de transporte es max z =



= Oi ui +



i

Dj vj

j

s.a. (11.13)

ui + vj ≤ cij ∀i ∈ O, ∀j ∈ D ui libre de signo ∀i ∈ O vj libre de signo ∀j ∈ D Justificaci´ on. El problema 11.13 es equivalente a max z =



− = Oi (u+ i − ui ) +



i

Dj (vi+ − vi− )

j

s.a. +

−

+

−

(u − u ) + (v − v ) ≤ cij ∀i ∈ O, ∀j ∈ D

(11.14)

− u+ i , ui libre de signo ∀i ∈ O

vi+ , vi− libre de signo ∀j ∈ D El dual de este problema es min z =



Cij xij

ij

s.a.



xij ≤ Oi ∀i ∈ O

j∈D



xij ≥ Oi ∀i ∈ O

(11.15)

j∈D



xij ≤ Dj ∀j ∈ D

i∈



xij ≥ Dj ∀j ∈ D

i∈

xij ≥ 0 ∀j ∈ D, ∀i ∈ O Que es equivalente a 11.2 Por otro lado, V B de un problema P y de es ese mismo problema, formulado en t´ erminos de m´ aximo son iguales, pero cambiados de signo. Del teorema de las holguras complementarias: B h ij = −Vij

max

B = Vij

cij − ui − vj =

min B Vij min

(11.16)

105

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

11.6.

Para pensar

11.7.

Ejemplo

106

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

11.8.

11.8.1.

El problema de asignaci´ on

Introducci´ on

Se trata de un caso particular del problema de transporte, en el que: m = car d(O) = car d(D) = n Oi = 1 ∀i ∈ O y Dj = 1 ∀j ∈ D Es decir, el n´ umero de or´ıgenes y de destinos es el mismo y la capacidad de los primeros y la demanda de los segundos es igual a 1. Ejemplos... El problema se puede formular como: max z =



Cij xij

ij

s.a.



xij ≤ 1 ∀i ∈ O

(11.17)

j∈D



xij ≥ 1 ∀j ∈ D

i∈O

xij ≥ 0 ∀j ∈ D, ∀i ∈ O De las m + n restricciones, en este caso existen I = J linealmente independientes, con lo que una soluci´ on b´ asica contendr´ a m = n variables b´ asicas.

11.8.2.

Representaci´ on

Dada la estructura particular de este problema, se puede represetnar con una tabla cuadrada con tantas filas y columnas como el n´ umero de origenes o de destinos.

O1 O2 ··· Oi ··· OI

···

D1 C11 C21

D2 C12 C22

Ci1

Ci2

Dj C1j C2j C Cij

CI1

CI2

CIj

···

Donde Cij es el coste de asignar el origen i al destino j Por ejemplo,...

DJ C1J C2J CiJ CIJ

107

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

O1 O2 O3 O4

D1 4 5 1 10

D2 2 2 8 1

D3 3 6 9 6

D4 1 3 2 4

D2 ×

D3

D4

108

Una posible asignaci´ on podr´ıa ser D1 O1 O2 O3 O4

11.8.3.

× × ×

Propiedades

En una soluci´ on del problema, para cada fila i, solo un valor xij = 1 En una soluci´ on 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 columna, el problema resultante alcanza la soluci´ on ´ optima para la misma asignaci´ on 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´ on objetivo es:      

Cij xij = Cij xi,j + (Ci ∗ j + k)xi,j = Ci,j xij + Ci ∗ j xij + kxij = z = i,j

i≠i∗ ,j

i≠i∗ ,j

j



i=i∗ ,j

Ci,j xij + k (11.18)

Se puede justificar, igualmente para una columna. En particular, k puede ser el opuesto del menor valor de la fila o la l´ınea corerspondiente. En un problema en el que todos los costes son no negativos y hay un conjunto de ceros, de tal manera que se puede encontrar un conjunto de dichos ceros, de manera que hay un 0 y solo uno cada cada fila y un 0 y solo un en cada columna, la soluci´ on consiste en asignar los orignes y destinos correspondientes a dichos ceros, con un coste total igual a 0. D1 2 0 2 3

D2 0 2 5 1

D3 1 1 7 0

D4 3 1 0 3

i=i∗ ,j

i=i∗ ,j

i≠i,j

O1 O2 O3 O4



xij = z + k

´ Cap´ıtulo 11. TRANSPORTE Y ASIGNACION

11.8.4.

M´ etodo H´ ungaro

1. Restar a cada fila el menor coste de dicha fila 2. Restar a cada columna el menor coste de dicha columna 3. Si existe un conjunto de costes iguales a cero que permiten realizar una asignaci´ on con coste global igual a cero, se ha obtenido la soluci´ o´ optima, si no, hay que continuar. 4. Tachar todos los ceros con el m´ınimo n´ umero posible de l´ıneas (siempre habr´ a que utilizar menos que el n´ umero de orignes o destinos, porque si no, existir´ıa una asignaci´ on con coste cero). 5. Identificar k igual al coste m´ınimo de todos los costes no tachados y obtener un problema equivalente: Restar k a los elementos sin tachar, sumar k Sumar k a los elementos tachados Dejar igual los elementos tachados una sola vez

O1 O2 O3 O4

D1 1 2 3 1

D2 4 1 2 2

D3 3 6 6 3

D4 1 7 6 7

O1 O2 O3 O4

D1 0 1 1 0

D2 3 0 0 1

D3 2 5 4 2

D4 0 6 4 6

-1

-1

-1

O1 O2 O3 O4

D1 0 1 1 0

D2 3 0 0 1

D3 0 3 2 0

D4 0 6 4 6

O1 O2 O3 O4

D1 0 0 0 0

D2 4 0 0 2

D3 0 2 1 0

D4 0 5 3 6

109

Cap´ıtulo 12 ´ ENTERA. FUNDAMENTOS PROGRAMACION

12.1.

Divide y vencer´ as

Considera el problema z = max{cx : x ∈ S} ¿Ser´ a posible dividir este problema en un conjunto de problemas de menor tama˜ no y m´ as f´ aciles de resolver, resolverlos y luego juntar toda la informaci´ on para hallar la soluci´ on del porblema original? Se dice que S = S1 ∪ · · · ∪ Sk es una descomposici´ on de S en un conjunto m´ as peque˜ no de problemas y que si zk = max{cx : x ∈ Sk } para k = 1 . . . K, entonces z = maxk zk . Una forma t´ıpica de representar el enfoque “divide y vencer´ as” es mediante los ´ arboles de enumeraci´ on. Por ejemplo si S ⊆ {0, 1}3 , se puede construir el ´ arbol que se presenta en la figura [?]. En este caso se divide el conjunto S en dos: S0 = {x ∈ S : x1 = 0} y S1 = {x ∈ S : x1 = 1}. Despu´ es estos dos subconjuntos se dividen en dos cada uno: S00 = {x ∈ S0 : x2 = 0} = {x ∈ S : x1 = x2 = 0}, S01 = {x ∈ S0 : x2 = 1} y as´ı sucesivamente. Si nos fijamos, cualquier hoja final del ´ arbol Si1,i2,i3 es no vac´ıa si y s´ olo si s = (i1, i2, i3) est´ a en S. Es decir, las hojas finales (nodos) del ´ arbol corresponden precisamente a los puntos del conjunto B 3 que habr´ıamos examinado mediante la enumeraci´ on completa.

12.2.

Enumeraci´ on impl´ıcita

Como ya hemos visto anteriormente, la enumeraci´ on completa (o expl´ıcita) es imposible de hacer para muchos problemas cuando el n´ umero de variables enteras crece. Luego a parte de dividir indefinidamente el problema tenemos que hacer algo m´ as. ¿C´ omo podemos usar de forma inteligente algunas cotas de los valores de {zk }? Vamos a ello. Si S = S1 ∪· · ·∪Sk es una descomposici´ on de S en un conjunto m´ as peque˜ no de k k problemas, z = max{cx : x ∈ Sk } para k = 1 . . . K, z es una cota superior de zk y zk es una cota inferior de zk ; entonces z = maxk zk es una cota superior de z y z = maxk zk es una cota inferior de z.

´ ENTERA. FUNDAMENTOS Cap´ıtulo 12. PROGRAMACION

111

Vamos a ver ahora tres casos hipot´ eticos para ver c´ omo podemos utilizar con sentido la informaci´ on relativa a las cotas de un problema. ¿Qu´ e se puede decir sobre la soluci´ on ´ optima con la infomaci´ on relativa a las cotas y qu´ e conjuntos (suproblemas) neceistan seguir examin´ andose para encontrar la soluci´ on ´ optima? . En la figura 12.1 se pude ver una descomposici´ on del conjunto S en dos subconjuntos S1 y S2 y las cotas superiores e inferiores de los distintos problemas.

Ejemplo 1

Figura 12.1: Poda por acotamiento Podemos ver que z = maxk zk = max{20, 25} = 25 y que z = maxk zk = max{20, 15} = 20. Adem´ as las cotas inferiores y superiores de z1 con iguales y no hace falta seguir examinando el conjunto S1 . Entonces la rama corresponiente al conjunto S1 del ´ arbol puede ser podada por optimalidad. . En la figura 12.2 vemos de nuevo la descomposici´ on del conjunto S en dos subconjuntos S1 y S2 y las cotas superiores e inferiores de los distintos problemas.

Ejemplo 2

Figura 12.2: No poda posible Podemos ver que z = maxk zk = max{20, 26} = 26 y que z = maxk zk = max{18, 21} = 21. A parte, la funci´ on objetivo del problema tiene un valor como poco de 21 y la cota superior z1 = 20, luego la soluci´ on ´ optima no puede estar en el subconjunto S1 . En este caso la rama correspondiente a S1 se poda por acotamiento. . En la figura 12.3 est´ a descompuesto de nuevo el conjunto S en dos subconjuntos S1 y S2 con diferenctes cotas superiores e inferiores. Podemos ver que z = maxk zk = max{24, 37} = 37 y que z = maxk zk = max{13, −} = 13. En este caso no podemos decir nada y hay que seguir explorando los subconjuntos S1 y S2 . Basados en estos tres ejemplos se pueden enumerar las tres razones que permiten podar alguna rama del ´ arbol y con ello enumerar de forma impl´ıcita un gran n´ umero de soluciones: 1. Poda por optimalidad: zt = {max cx : x ∈ St } se ha resuelto. 2. Poda por acotamiento: zt ≤ z. 3. Poda por infactibilidad: St = ∅ Si nos preguntamos c´ omo se pueden obtener las cotas, la respuesta es la misma que lo que vimos en el cap´ıtulo anterior. Las cotas inferiores se calculan al obtener soluciones factibles y las cotas superiores mediante relajaciones.

Ejemplo 3

´ ENTERA. FUNDAMENTOS Cap´ıtulo 12. PROGRAMACION

Figura 12.3: Poda por optimalidad

Construir un algoritmo de enumeraci´ on impl´ıcita basado en los visto anteriormente es ya una tarea sencilla, aunque quedan a´ un muchas preguntas por resolver para poder tener bien definido el algoritmo. Algunas de estas pregunta puede ser: ¿Qu´ e relajaci´ on vamos a utilizar para hallar las cotas superiores?¿C´ omo elegir entre una sencilla cota d´ ebil f´ acil de obtener y una cota fuerte cuyos c´ alculos llevan m´ as tiempo? ¿C´ omo generamos los distintos subconjuntos del problema principal S = S1 ∪ · · · ∪ SK ?¿Cada conjunto se tiene que dividir en dos o m´ as subconjuntos?¿Tenemos que tener una regla a priori para subdividir los problemas o es mejor que esas divisiones dependan de c´ omo evoluciona el problema? ¿En qu´ e orden vamos a examinar los problemas? Normalmente tendremos un conjunto de nodos activos (ramas sin podar). ¿Tenemos que estudiar el primer nodo al que hayamos llegado (FIFO), el que tenga mejor cota superior u otro criterio? Estas y otras cuestiones se discuten en el siguiente apartado.

12.3.

Branch and Bound: un ejemplo

La forma m´ as com´ un de resolver problemas con n´ umeros enteros es usando la enumeraci´ on impl´ıcita o branch & bound, en donde las relajaciones lineales se utilizan para calcular las cotas superiores. Por ejemplo, dado este problema: max z = 4x1 − x2 s.a.

(12.1)

7x1 − 2x2 ≤ 14 2 x2 ≤ 32x1 − 2x2 ≤ 3x ∈ Z+

Acotamiento. Para obtener una primera cota superior, a˜ nadimos las holguras correspondientes (h1 , h2 y h3 ) y resolvemos la relajaci´ on lineal de este problema (quitando las restricciones de integrabilidad). La tabla ´ optima a la que se llega es: RL

z x1 x2 h3

50/7 20/7 3 23/7

x1 0 1 0 0

x2 0 0 1 0

h1 -4/7 1/7 0 -2/7

h2 -1/7 2/7 1 10/7

h3 0 0 0 1

112

´ ENTERA. FUNDAMENTOS Cap´ıtulo 12. PROGRAMACION

De aqu´ı obtenemos una cota superior z =

59 7 ,

y una soluci´ on que no es entera

on factible? Pues aparente( 20 7 , 3). ¿Hay alguna forma de encontrar una soluci´ mente, no. Luego no tenemos ninguna cota inferior a´ un, z = −∞. Ramificaci´ on. Como z ≤ z tenemos que dividir o ramificar. ¿C´ omo podemos dividir la regi´ on factible? Una idea muy sencilla es elegir una variable que est´ e en la base y que debiera de ser entera pero no lo es, y dividir el problema en dos subproblemas en funci´ on del valor del valor que tiene la variable. Veamos, si xj = x j ∉ Z 1 , se puede  dividir el problema en:

S1 = S ∩ {x : xj ≤ x j } ! S2 = S ∩ {x : xj ≥ x j } Est´ a claro que S = S1 ∪ S2 y que S1 ∩ S2 = ∅. Otra raz´ on por la que se eligen estos subproblemas es que la soluci´ on de la relajaci´ on lineal no es factible en las relajaciones lineales de S1 ni S2 . Esto es muy importante pues evita degeneraciones de la soluci´ on (o m´ ultiples soluciones); con lo cual max{z1 , z2 } ≤ z y la cota superior tendr´ a siempre menor valor. 1 Siguiendo esta idea, como x 1 = 20 an S1 = S ∩ {x : 7 ∉ Z , los subproblemas ser´ xj ≤ 2} y S2 = S ∩ {x : xj ≥ 3}. Se puede ver en la figura ??. A los dos subproblemas (nodos del ´ arbol) que deben ser examinados se les llama nodos activos. Elecci´ on de un nodo. La lista de nodos activos que deben ser examinados contiene a S1 y S2 . Arbitrariamente elegimos S1 . Reoptimizaci´ on. ¿C´ omo podemos resolver las relajaciones lineales de los nuevos subproblemas sin necesidad de partir de cero? Como simplemente hemos a˜ nadido una restricci´ on que sabemos que no se cumple, al a˜ nadir la la fila correspondiente a la tabla del simplex expresada en la base actual tendremos una soluci´ on no factible. Utilizando el m´ etodo de Lemke en varios pivotes (tablas) podemos llegar a la nueva soluci´ on ´ optima. Al resolver la relajaci´ on lineal de S1 a˜ nadimos la restricci´ on x1 ≤ 2 o x1 + h4 = 2, h4 ≥ 0. Y tendr´ıamos la siguiente tabla que ser´ a igual que la anterior pero con una fila m´ as en la parte inferior:

z1RL x1 x2 h3 h4

50/7 20/7 3 23/7 -6/7

x1 0 1 0 0 0

x2 0 0 1 0 0

h1 -4/7 1/7 0 -2/7 -1/7

h2 -1/7 2/7 1 10/7 -2/7

h3 0 0 0 1 0

h4 0 0 0 0 1

Despu´ es de pasar por dos soluciones intermedias se llega la la siguiente soluci´ on ´ optima

113

´ ENTERA. FUNDAMENTOS Cap´ıtulo 12. PROGRAMACION

z1RL x1 x2 h1 h2

15/2 20/7 3 23/7 -6/7

x1 0 1 0 0 0

1 1 1 con z1RL = 15 2 y (x 1 , x 2 ) = (2, 2 ). Ramificaci´ on.

x2 0 0 1 0 0

h1 0 0 0 1 0

h2 0 0 0 0 1

h3 -1/2 0 -1/2 -1 1/2

h4 -3 1 1 -5 6

114

Cap´ıtulo 13 ´ ENTERA. BRANCH AND PROGRAMACION BOUND

13.1.

Introducci´ on

Existe una gran varedad de problemas que se pueden formular y resolver utilizando variables enteras, por ejemplo: programaci´ on de horarios de trenes o de tripulaciones en una compa˜ n´ıa a´ erea, problemas de programaci´ on de la producci´ on, de c´ alculo de rutas, etc. En ocasiones, las variables enteras aparecen por la propia naturaleza de la decisi´ on. En otras ocasiones, se debe Supongamos que tenemos un problema de programaci´ on lineal: max{cx cx : Ax ≤ b, x ≥ 0 } donde A es una matriz m por n, c es un vector fila de dimensi´ on n, b es un vector columna de dimensi´ on m y x es un vector columna de dimensi´ on n. A este problema le a˜ nadimos la restricci´ on de que ciertas variables tienen que ser enteras. Si s´ olo alguna (no todas) las variables tienen que ser enteras, entonces tenemos un problema de programaci´ on lineal entera mixto (Mixed Integer Problem, MIP). Si todas las variables tienen que ser enteras, entonces tenemos un problema de programaci´ on lineal puro (Integer Programming, IP). Y, si todas la variables est´ an restringidas a los valores 0 − 1, entonces tenemos un problema de programaci´ on entera binaria (Binary Integer Problem, BIP). Dado que los problemas enteros se parecen bastante a los lineales, no sorprende que tanto la teor´ıa como la pr´ actica de la programaci´ on lineal es fundamental para comprender y resolver problemas enteros. Una de las primeras ideas que nos viene a la mente es la del redondeo: resolver el problema como si fuera lineal y luego redondear el valor de las variables. ˜ ADIR No tiene sentido en muchos problemas: “3.5 aviones” son 3 o 4, ... AN Ejemplo: (apuntes Miguel)

´ ENTERA. BRANCH AND BOUND Cap´ıtulo 13. PROGRAMACION

116

Figura 13.1: Cotas de un problema entero

13.2.

Optimalidad y relajaci´ on

Dado un problema entero de la forma: z = max{c(x) : x ∈ X ⊆ Z n } ´ptima? O dicho de otra forma, ¿c´ omo se puede probar que una soluci´ on x ∗ es o ser´ıa muy interesante encontrar algunas condiciones que nos garanticen la optimalidad y as´ı dejar de buscar la soluci´ on ´ optima en un problema entero. Para ello es importante darse cuenta de que se necesita encontrar una cota inferior (lower bound) z ≤ z y una cota superior (upper bound) z ≥ z tal que z = z = z. Pr´ acticamente esto significa que cualquier algoritmo que encuentre una secuencia decreciente z 1 ≥ z 2 ≥ · · · ≥ zs ≥ z de cotas superiores, y una secuencia creciente z 1 ≤ z 2 ≤ · · · ≤ zt ≥ z de cotas inferiores ser´ıa muy interesante y se podr´ıa parar cuando zs − zt ≤  donde  es un valor positivo elegido. Luego lo que nos interesa es encontrar formas de obtener cotas superiores e inferiores. Todas las soluciones factibles x ∗ ∈ X son una cota inferior z = c(x ∗ ) ≤ z∗ . ´ ´nica forma de encontrar cotas inferiores: encontrando soluciones Esta es la u factibles. Para algunos problemas PLE encontrar una soluci´ on factible es sencillo y lo complicado es encontrar buenas cotas inferiores (cercanas al ´ optimo); esto ocurre por ejemplo en el problema del TSP (cualquier ciclo que contenga todas las ciudades es una soluci´ on factible que ofrece una cota inferior). Pero para otros problemas, encontrar una soluci´ on factible es tan complicado como resolver el problema entero. Para algunos problemas no es dif´ıcil utilizar algoritmos greedy (algoritmo ´ avidos) que permiten encontrar soluciones factibles “buenas” (cotas inferiores).

Cotas primales/inferiores

´ ENTERA. BRANCH AND BOUND Cap´ıtulo 13. PROGRAMACION

117

La idea centra de estos heur´ısticos es, a partir de no tneer una soluci´ on, ir construy´ endola paso a paso (dando valor una a una a cada variable) y en cada paso tomar la decisi´ on que suponga una mayor mejora de la funci´ on objetivo. La tarea de encontrar cotas superiores muy distinta de la anterior. Una de las formas de hallar las cotas superiores es mediante “relajaciones”. La idea que hay detr´ as de las relajaciones es reemplazar un problema entero “dif´ıcil” de maximizar (como normalmente formulamos los problemas) por otro problema m´ as sencillo cuya funci´ on objetivo es mayor o igual que la z del problema original. Para que el problema relajado cumpla esta propiedad hay dos posibilidades:

Cotas duales/superiores

hacer mayor el conjunto de soluciones factibles de forma que el problema se resuelve sobre un conjunto mayor, o reemplazar la funci´ on objetivo (max) por una funci´ on que tiene el mismo o mayor valor que la original siempre. Se dice que el problema (RP) {zR = max{f (x) : x ∈ T ⊆ R n } es una relajaci´ on del problema (IP) {z = max{c(x) : x ∈ X ⊆ R n } si: x ⊆ T, y f (x) ≥ c(x)para todo x ∈ X Si RP es una relajaci´ on de IP, entonces zR ≥ z. La cuesti´ on entonces est´ a en c´ omo encontrar relajaciones interesantes. Una de las m´ as naturales y m´ as utilizadas es la relajaci´ on lineal. n Dado un problema entero max{c(x) : x ∈ P ⊆ Z n } siendo P = x ∈ R+ : Ax ≤ b}, la relajaci´ on lineal es el problema lineal zLP = mboxmax{cx : x ∈ P }. Como P ∩Z n ⊆ P y la funci´ on objetivo no cambia, es claramente una relajaci´ on. Por ejemplo, si consideramos el problema entero:

max z = 4x1 − x2 s.a. 7x1 − 2x2 ≤ 14 x2 ≤ 3

(13.1)

2x1 − 2x2 ≤ 3 2 x ∈ Z+

El punto (2, 1) es una soluci´ on factible luego tenemos una cota inferior z ≥ 7. Para obtener una cota superior podemos recurrir a la relajaci´ on lineal. La 20 59 ∗ LP soluci´ on ´ optima es x = ( 7 , 3) con funci´ on objetivo z = 7 . Como el valor de la funci´ on objetivo del problema entero tiene que ser entero (en este caso), podemos redondear y obtener z ≤ 8. Las relajaciones no s´ olo permiten obtener cotas superiores, sino que tambi´ en sirven paara probar la optimalidad. Si la relajaci´ on (RP) es no factible, el problema original entero (IP)tambi´ en. Si al resolver la relajaci´ on lineal (RP) resulta

Relajaciones lineales

´ ENTERA. BRANCH AND BOUND Cap´ıtulo 13. PROGRAMACION

118

que cumple las condiciones de integralidad del problema entero (IP) resulta que tambi´ en es su soluci´ on ´ optima. Por ejemplo, la relajaci´ on lineal del problema entero max z = 7x1 + 4x2 + 5x3 + 2x4 s.a. 3x1 + 3x2 + 4x3 + 2x4 ≤ 6

(13.2)

x ∈ {0, 1} tiene como soluci´ on ´ optima x ∗ = (1, 1, 0, 0). Como x ∗ es entera, es tambi´ en soluci´ on ´ optima del problema entero. Existen m´ as tipos de relajaciones que perimten hallar cotas superiores. Entre ellas, por ejemplo, las relajaciones combinatorias que son espec´ıficas para determinados problemas (TSP, Knapsack, etc.); y las relajaciones lagrangianas, mucho m´ as generales y que se basan en relajar restricciones (quitarlas) pero su cumplimiento afecta a la funci´ on objetivo con un coste.

Otras relajaciones lineales

Cap´ıtulo 14 DUALIDAD

14.1.

Introducci´ on

Existen dos problemas de optimizaci´ on lineal asociados que cada uno de ellos proporciona informaci´ on sobre el otro, de tal manera que la soluci´ on ´ optima de uno de los problemas nos permite conocer la soluci´ on del problema asociado. A los dos problemas asociados se les denomina problemas duales y su relaci´ on se va a tratar en este cap´ıtulo. La dualidad es una parte clave en la programaci´ on lineal que muchas veces pasa como desapercibida pero que es lo que permite que tenga sentido toda la teor´ıa correspondiente. ¿Por qu´ e estudiar la dualidad? Hay varias razones:

¿Por qu´ e?

Por una lado aporta elementos clave que van a ayudar a comprender la programaci´ on lineal ´til para resolver problemas de programaci´ Es una herramienta u on lineal; cuando hay mucha diferencia entre filas y columnas (hay distinto coste computacional) puede ser interesante resolver el dual en lugar del problema primal El problema dual ayuda a conocer la factibilidad o no acotaci´ on del problema primal Fundamental para el desarrollo de t´ ecnicas m´ as avanzadas (descomposici´ on de Benders, etc.) La dualidad ofrece otra forma de ver el significado de los precios sombra La dualidad ofrece otra visi´ on del m´ etodo de Lemke (o dual del simplex) Para introducir el tema vamos a ver un ejemplo sencillo en el se puede observar de forma r´ apida las relaciones entre un problema y un dual (aunque a´ un no se haya descrito como construir el problema dual de uno dado). Una empresa internacional produce y vende estos dos tipos de supercomputadores: el modelo 1 y el modelo 2. En la elaboraci´ on de ambos tipos de equipos hay que destacar dos procesos, el de ensamblado final y el de empaquetado (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´ as se sabe que los tiempos requeridos para realizar dichas

Ejemplo de problema dual

Cap´ıtulo 14. DUALIDAD

operaciones para cada uno de los tipos de supercomputadores son los que se muestran en la tabla siguiente:

Proceso Montaje Embalaje

Horas requeridas Modelo 1 Modelo 2 6 4 2 4

Horas disponibles 2000 1000

El beneficio neto obtenido tras la venta de un supercomputador 1 es de 400 u.m. y tras la venta de una unidad tipo 2 es de 600 u.m. Con esta informaci´ on se plantea y resuelve inicialmente un problema que permita determinar el n´ umero de unidades de cada tipo de ordenador con objeto de maximizar el beneficio total. Se definen las variables x1 y x2 como el n´ umero de ordenadores elaborados de tipo 1 y 2 respectivamente, con estas variables el problema queda: max z = 400x1 + 600x2 s.a: 6x1 + 4x2 ≤ 2000

(14.1)

2x1 + 4x2 ≤ 1000 x1 ≥ 0, x2 ≥ 0 ´ptima de dicho problema es elaborar 250 unidades del tipo 1 y y La soluci´ on o 125 unidades del modelo 2 con un beneficio de 175000 u.m. En la figura 14.1 se puede ver las soluciones por las que se pasa hasta x ∗ = (250, 125). La tabla correspondiene a la soluci´ on ´ optima es la siguiente:

x1 x2

-175000 250 125

0 1 0

0 0 1

-25 1/4 -1/8

-125 -1/4 3/8

Ahora podemos cambiar el enfoque sobre el problema planteado, nuestro prop´ osito va a ser determinar los precios a los cuales esta empresa deber´ıa 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. Sean y1 e y2 , la renta percibida por hora de los procesos P1 y P2 respectivamente (precios de los recursos). La renta total obtenida ser´ıa pues, 2000y1 + 1000y2 . Se desea como objetivo encontrar el m´ınimo valor de 2000y1 + 1000y2 de modo que la empresa pueda, de una manera inteligente, analizar algunas propuestas de alquiler o compra de todos los recursos como un paquete total. Se consideran las condiciones siguientes, los precios pagados por el alquiler ser´ıan no negativos, es decir y1 ≥ 0, y2 ≥ 0. Adem´ as los precios y1 e y2 deben ser competitivos con las alternativas disponibles, es decir, el beneficio que la empresa debe obtener por los recursos necesarios para elaborar un

120

Cap´ıtulo 14. DUALIDAD

x2

5 4 3 2 x ∗ (250, 125) 1 0 0

1

2

3

4

5

x1

Figura 14.1: Soluci´ on gr´ afica del problema inicial

supercomputador al menos deben ser iguales a los que obtendr´ıa al utilizar dichos recursos en la elaboraci´ on del computador, es decir, para el modelo 1 tendremos 6y1 + 2y2 ≥ 400 y para el modelo 2 queda 4y1 + 4y2 ≥ 600. Con esto se garantiza la obtenci´ on de precios con los que al menos iguala el beneficio obtenido al producir el mismo los equipos. El problema planteado queda: min z = 2000y1 + 1000y2 s.a: 6y1 + 2y2 ≤ 400

(14.2)

2y1 + 4x2 ≤ 600 y1 ≥ 0, y2 ≥ 0 La resoluci´ on de este problema proporciona un valor de 25 para cada unidad del primer recurso (montaje) y un valor de 125 para cada unidad del segundo (embalaje), con un beneficio de 175000, igual al obtenido en el planteamiento del primer problema. Este nuevo problema es problema dual del problema planteado originalmente. En la siguiente tabla se puede ver la tabla correspondiente a la soluci´ on ´ optima de est segundo subproblema:

x1 x2

175000 25 125

0 1 0

0 0 1

-250 -1/4 1/4

-125 1/8 -3/8

121

Cap´ıtulo 14. DUALIDAD

14.2.

14.2.1.

Teor´ıa sobre dualidad

El problema dual

Dado el problema de programaci´ on lineal: Max z = cx Ax ≤ b

(14.3)

x≥0 se le asocia otro problema: Min s = yb yAT ≥ c

(14.4)

y ≥0 Al problema (14.3) se le denomina primal y a (14.4) se le denomina dual.

14.2.2.

El dual del dual es el primal

En efecto, dado el problema primal Max z = cx Ax ≤ b

(14.5)

x≥0 tiene como problema dual asociado: Min s = yb yAT ≥ c

(14.6)

y ≥0 El problema dual puede expresarse como: max (−s) = −bT y T − Ay T ≤ −c T

(14.7)

y ≥0 El problema (14.7) considerado como un problema primal, tiene como problema dual asociado el siguiente problema de programaci´ on lineal: min u = t(−c T ) t(−AT ) ≥ −bT t≥0

(14.8)

122

Cap´ıtulo 14. DUALIDAD

El problema dual (14.8) puede expresarse como: max (−u) = ct T At T ≥ b

(14.9)

T

t ≥0 Al comparar el problema (14.5) y el problema (14.9) se observa que: el vector c es el mismo en los dos problemas, la matriz A es la misma en los dos problemas, el vector b es el mismo en los dos problemas, por lo cual, los vectores x y t T y los valores de z y u son iguales, es decir se comprueba que en efecto el problema dual asociado a un problema dual coincide con el problema primal inicial.

14.2.3.

Relaciones entre el problema primal y el problema dual

teorema De la propia definici´ on de problema primal y problema dual asociado se deducen unas primeras relaciones entre ambos problemas: una variable del problema primal genera una restricci´ on en el problema dual; una restricci´ on del problema primal genera una variable en el problema dual, una restricci´ on de desigualdad en el problema primal genera una variable no negativa en el problema dual. Existen otras relaciones no evidentes entre ambos problemas: una restricci´ on de igualdad en el problema primal genera una variable libre de signo en el problema dual; una variable libre de signo en el problema primal genera una restricci´ on de igualdad en el problema dual. En efecto, la restricci´ on del problema primal a31 x1 + a32 x2 + a33 x3 + a34 x4 = b3 que es equivalente a : a31 x1 + a32 x2 + a33 x3 + a34 x4 ≤ b3 a31 x1 + a32 x2 + a33 x3 + a34 x4 ≥ b3 La segunda restricci´ on se puede expresarse como: −a31 x1 − a32 x2 − a33 x3 − a34 x4 = −b3 La inecuaci´ on primera, corresponde a una restricci´ on en el problema primal y genera en el problema dual un variable que se denominar´ a y3+ y, por lo tanto, se obtiene en dicho problema:

123

Cap´ıtulo 14. DUALIDAD

un t´ ermino en la funci´ on objetivo: b3 y3+ una columna en el sistema de restricciones t´ ecnicas: • +a31 y3+ • +a32 y3+ • +a33 y3+ • +a34 y3+ La otra inecuaci´ on, vista de una forma u otra, genera a su vez en e problema dual la variable y3− y, por lo tanto: un t´ ermino en la funci´ on objetivo: b3 y3− una columna en el sistema de restricciones t´ ecnicas: • −a31 y3− • −a32 y3− • −a33 y3− • −a34 y3− Por lo que, la resricci´ on a nivel de igualdad del problema primal genera en el problema dual: dos t´ erminos en la funci´ on objetivo: b3 (y3+ + y3− ) dos columnaa en el sistema de restricciones t´ ecnicas: • +a31 y3+ + a31 y3− • +a32 y3+ + a32 y3− • +a33 y3+ + a33 y3− • +a34 y3+ + a34 y3− Efectuando un cambio de variable:

y3 = y3+ y3− y3 ser´ a libre se signo siempre que y3+ y y3− sean no negativas y, adem´ as, no puedan estar ambas en la soluci´ on del problema. En dicho caso: 1. si y3+ ≥ 0 y y3− = 0 y 3 = y3+ ≥ 0 2. si y3− ≥ 0 y y3+ = 0 y 3 = y3− ≥ 0 Las dos condiciones anteriores se cumplen ya que: se parte de un problema primal con restricciones t´ ecnicas de desigualdad, lo que genera en el problema dual variables no negativas, es decir y3+ ≥ 0 y y3− ≥ 0. el criterio del simplex de la variable y+3 respecto a cualquier soluci´ on b´ asica es V B y3+ = b3 cBB−1 (a31 , a32 , a33 , a34 )T el criterio del simplex de la variable y-3 respecto a cualquier soluci´ on b´ asica es V B y3− = −b3 cBB−1 (−a31 , −a32 , −a33 , −a34 )T

124

Cap´ıtulo 14. DUALIDAD

es decir V B y3+ = V B y3− lo que implica que: si V B y3+ > 0 ⇒ V B y3− < 0 y que si V B y3+ < 0 ⇒ V B y3− > 0 por lo cual, si interesa introducir en la soluci´ on y3+ no interesa introducir − + on s´ı interesa introducir y3− . y3 , y si no interesa introducir y3 en la soluci´ Cuando una de las variables pertenece a la soluci´ on, por ejemplo y3∗ , el criterio 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´ on 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´ on deje de ser factible. Con lo que se comprueba que una restricci´ on de igualdad en el problema primal genera en el problema dual una variable libre de signo. En el ep´ıgrafe anterior se comprobaba que el problema dual de un problema dual es el problema primal, por lo cual ya se puede afirmar que una variable libre de signo en el problema primal genera una restricci´ on de igualdad en el problema dual.

14.2.4.

La funci´ on objetivo

El valor de la funci´ on objetivo para cualquier soluci´ on factible del problema primal es una cota inferior del valor de la funci´ on objetivo para cualquier soluci´ on factible del problema dual. Es decir: z0 ≤ s 0 En efecto, se parte de las dos soluciones factibles de los dos problemas asociados primal y dual x 0 e y 0 para las cuales el valor de cada funci´ on objetivo es z0 = cx 0 s 0 = y 0 b on del problema primal se cumple que Ax 0 ≤ b al adem´ as, al ser x 0 soluci´ premultiplicar por y 0 la expresi´ on anterior, como y 0 se factible, se cumple que: y 0 Ax 0 ≤ y 0 b on del problema dual se cumple que y 0 AT ≥ c Por otra parte, al ser y 0 soluci´ 0 al postmultiplicar por x la expresi´ on anterior, como x 0 es factible, se cumple que: y 0 Ax 0 ≥ cx 0 De ambas expresiones se obtiene que: cx 0 ≤ y 0 Ax 0 ≤ y 0 b es decir: z0 = cx 0 ≤ y 0 b = s 0 luego: z0 ≤ s 0

125

Cap´ıtulo 14. DUALIDAD

s 0 dual z0 ≤ s 0

z0 primal Corolario 1. El valor de la funci´ on objetivo del problema primal de m´ aximo para cualquier soluci´ on factible es una cota inferior del m´ınimo valor de la funci´ on objetivo del dual, y reciprocamente, el valor de la funci´ on objetivo del problema dual de m´ınimo para cualquier soluci´ on factible dual es una cota superior del m´ aximo valor de la funci´ on objetivo del primal. Corolario 2. Si el problema primal es factible y su soluci´ on es no acotada, (z → ∞), entonces el problema dual no tiene soluci´ on. An´ alogamente, si el problema dual es factible pero con soluci´ on no acotada, (s → −∞), entonces el problema primal no tiene soluci´ on factible.

14.2.5.

Teorema fundamental de la dualidad

´ptima, x ∗ , de un problema primal a la que le Dada una soluci´ on b´ asica factible o corresponde una base B y un vector de multiplicadores del simplex π B = cB B −1 , ´ptima del problema dual es y ∗ = π B . la soluci´ on b´ asica factible o En efecto: 1. y* es la soluci´ on del problema dual. Como x* es soluci´ on ´ optima del problema primal se cumple: VxB = c − cB B −1 A ≤ 0 identificando los t´ erminos correspondientes a las variables iniciales del problema primal, c y A, y los t´ erminos correspondientes a las variables de holgura del problema primal, ch e I, la expresi´ on anterior se transforma en: VxB = [(c, ch ) − cB B −1 (A, I)] ≤ 0 por lo que: c − cB B −1 A ≤ 0 ch − cB B −1 I ≤ 0 En la expresi´ on primera al sustituir cB B −1 = y ∗ se obtiene c − ∗ y A ≤ 0 es decir y ∗ A ≥ c luego y ∗ = π B cumple las restricciones t´ ecnicas del problema dual. Al sustituir y ∗ por su valor en la segunda expresi´ on y ch por su valor se obtiene 0y ∗ I ≤ 0 es decir y ∗≥ 0 luego el vector y ∗ es una soluci´ on factible del problema dual.

126

Cap´ıtulo 14. DUALIDAD

´ptima del problema dual. 2. y ∗ = π B es soluci´ on o En el ep´ıgrafe anterior se comprobaba que el valor de la funci´ on objetivo para una soluci´ on factible del problema primal es siempre una cota inferior del valor de la funci´ on objetivo para una soluci´ on factible del problema dual, es decir z0 ≤ s 0 Por otra parte, z∗ es el valor de la funci´ on objetivo correspondiente a la soluci´ on 0 ∗ ∗ ´ optima del problema primal, se cumple que z ≤ z = cx s ∗ es el valor de la funci´ on objetivo correspondiente a la soluci´ on ´ optima del problema dual, luego y ∗ b = s∗ ≤ s 0 Adem´ as, z∗ = cx ∗ = cB B −1 b = π B b = y ∗ b = s ∗ Por lo cual podemos afirmar que z no puede tener un valor mayor y s no puede tener un valor menor y ambos coinciden. Corolario 3. Si el problema primal tiene soluci´ on ´ optima finita entonces el problema dual tambi´ en, y rec´ıprocamente, si el problema dual tiene soluci´ on ´ optima finita entonces el primal tambi´ en. Corolario 4. Si el problema primal es no factible entonces su dual o no tiene soluci´ on o tiene soluci´ on no acotada, y rec´ıprocamente, si el dual es no factible entonces el primal o es no factible o tiene soluci´ on no acotada. Dado un problema primal y su dual s´ olo una de las siguientes afirmaciones es cierta: ´ptima (finita)  el dual tiene soluci´ El primal tiene soluci´ on o on ´ optima (finita). Si el primal es no factible ⇒ el dual es no factible o tiene soluci´ on no acotada. Si el dual es no factible ⇒ el primal es no factible o tiene soluci´ on no acotada. Si el primal tiene soluci´ on no acotada ⇒ el dual es no factible. Si el dual tiene soluci´ on no acotada ⇒ el primal es no factible.

14.2.6.

Teorema de las holguras complementarias

El teorema fundamental de la dualidad permite, cuando se conoce la soluci´ on ´ optima de uno de los problemas asociados, conocer cual es el valor de las variables iniciales de su problema dual que son componentes de la soluci´ on ´ optima de dicho problema. El teorema de las holguras complementarias permite conocer el valor del resto de las componentes de la soluci´ on del problema dual. La demostraci´ on del teorema de las holguras complementarias se realizar´ a para las soluciones ´ optimas de los problemas duales asociados aunque se cumple para todas las soluciones intermedias. Se parte del conocimiento de las dos soluciones ´ optimas de los problemas duales correspondientes, x ∗ e y ∗ .

127

Cap´ıtulo 14. DUALIDAD

El teorema fundamental de la dualidad dice que: cx ∗ = y ∗ b a la expresi´ on anterior le restamos a ambos miembros y ∗ Ax ∗ , cx ∗ y ∗ Ax ∗ = y ∗ by ∗ Ax ∗ o lo que es lo mismo: (cy ∗ A)x ∗ = y ∗ (bAx ∗ ) En la igualdad anterior el primer miembro es un n´ umero negativo y el segundo miembro es un n´ umero positivo, por lo cual, s´ olo es posible cuando ambos t´ erminos son iguales a cero. En efecto: 1. (c ∗ − y ∗ A) · x ∗ = 0 - como x ∗ es la soluci´ on ´ optima del problema primal x ∗ ≥ 0 ∗ - como y es la soluci´ on ´ optima del problema dual y ∗ A ≥ c ⇒ cy ∗ A ≤ 0 y el producto de un n´ umero positivo por un n´ umero negativo es un n´ umero negativo. 2. y ∗ · (bAx ∗ ) - como y ∗ es la soluci´ on ´ optima del problema primal y ∗ ≥ 0 ∗ - como x es la soluci´ on ´ optima del problema dual Ax ∗ ≤ b ⇒ bAx ∗ ≥ 0 y el producto de un n´ umero positivo por un n´ umero positivo es un n´ umero positivo. Por lo cual: 1. (cy ∗ A) · x ∗ = 0 2. y ∗ · (bAx ∗ ) = 0 Veamos ambas expresiones. (1) (cy ∗ A) · x ∗ = 0 . Para analizar esta expresi´ on vectorial se identifica uno de sus t´ erminos: (cj y ∗ Aj )xj∗ = 0 Si cj y ∗ Aj < 0, la restricci´ on del dual no se cumple como igualdad y, por lo tanto, la holgura , yhj , de la restricci´ on forma parte de la soluci´ on ´ optima; es necesario que xj∗ = 0, lo que genera que dicha restricci´ on no forma parte de la soluci´ on ´ optima del primal. Adem´ as , cj y ∗ Aj ≤ 0

128

Cap´ıtulo 14. DUALIDAD

transformado en igualdad, cj y ∗ Aj + yhj = 0 luego yhj = −(cj y ∗ Aj ) = −(cj − π B Aj ) = −VxB∗ j

que es mayor que cero ya que el criterio del simplex de una variable no b´ asica en la soluci´ on ´ optima del problema es negativo. Si xj∗ > 0, es decir xj pertenece a la soluci´ on ´ optima del problema primal, entonces cj y ∗ Aj = 0, es decir la restricci´ on 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´ on ´ optima del problema, ya que: cj y ∗ Aj ≤ 0 ⇒ cj y ∗ Aj + yhj = 0 y como: cj y ∗ Aj = 0 ⇒ yhj = 0 Adem´ as, como yhj = −VxB∗ se comprueba que yhj = 0 ya que el criterio j

del simplex de una variable b´ asica, xj∗ , es cero. (2) y ∗ · (bAx ∗ ) = 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. Como conclusi´ on, la aplicaci´ on del teorema de las holguras complementarias a dos problemas duales asociados permite saber que: ´ptima, si una variable inicial de un problema pertenece a la soluci´ on o la restricci´ on que genera dicha variable en el problema dual se cumple como igualdad, es decir la variable de holgura de dicha restricci´ on no pertenece a la soluci´ on ´ optima, si una restricci´ on de un problema de optimizaci´ on lineal se cumple como desigualdad, es decir, la variable de holgura correspondiente pertenece a la soluci´ on ´ optima, la variable que genera dicha restricci´ on es el problema dual no forma parte de la soluci´ on ´ optima de dicho problema dual, finalmente, el valor del criterio del simplex cambiado de signo de una variable inicial del problema primal es el valor de la variable de holgura de la restricci´ on que genera dicha variable en el problema dual.

14.3.

Interpretaci´ on econ´ omica de las variables duales en el ´ optimo

Por el teorema fundamental de la dualidad los valores ´ optimos de las funciones objetivo de un problema primal [P] y su dual [D] son iguales, si x es una

129

Cap´ıtulo 14. DUALIDAD

soluci´ on b´ asica factible y ´ optima no degenerada de [P] e y (calculada como y = π B = cB B −1 ) podemos escribir: z(x) = c1 x 1 + c2 x 2 + · · · + cn x n = y 1 b1 + y 2 + · · · + y m bm = s(y) Vamos a supoer ahora que se modifica un recurso, por ejemplo b1 , en una cantidad “peque˜ na” Δb1 , de manera que la soluci´ on ´ optima del problema primal siga siendo factible, y en consecuencia ´ optima (c − cB B −1 A no var´ıa). Es decir, de manera tal que ⎞ ⎛ Δb1 ⎟ ⎜ ⎜ 0 ⎟ ⎟ ⎜ −1 ⎟) ≥ 0 ⎜ B (b + ⎜ ... ⎟ ⎠ ⎝ 0 Consideremos ahora los problemas [P1] y [D1], donde [P1] es el problema primal en el que se ha cambiado b por b + (Δb1 , 0, . . . , 0)T y [D1] es su ˜ tiene la mismas variables b´ dual. La soluci´ on ´ optima de [P1], x, asicas que x (por la elecci´ on de Δb1 ) y el valor que toma la parte b´ asica de dicha solu˜ B = B −1 [b + (Δb1, 0, · · · , 0)T ], por otro lado la soluci´ ci´ on es u on de [D1] es B ˜ no han cambiado entonces B sigue ˜ = π = c B B −1 , las variables b´ asicas de x y ˜ = y, teniendo en cuenta estos hechos tenemos siendo la misma que antes y y que:

˜ = c1 x ˜1 (b1 + Δb1 ) + y ˜2 + · · · + y ˜m bm = ˜ 1 + c2 x ˜2 + · · · + cn x ˜n = y z(x) = (y 1 b1 + y 2 + · · · + y m bm ) + yΔb1 = S(y) + yΔb1 = Z((x)) + yΔb1 ´ptimo de la variable dual y 1 De esta expresi´ on se desprende que el valor o asociada a la primera restricci´ on del problema primal representa la cantidad en la que se modifica el valor de la funci´ on objetivo de [P] por cada unidad adicional de recurso 1 (siempre que la modicaci´ on mantenga la base ´ optima). Esto puede hacerse en general para cualquier recurso bi del problema primal. Teniendo en cuenta esto, si nos situamos, por ejemplo, en un problema primal de m´ aximo con restricciones de tipo ≤, lo resolvemos y calculamos la soluci´ on del problema dual, entonces los valores ´ optimos de las variables duales (que son ≥ 0) representan la variaci´ on unitaria de la funci´ on objetivo del primal por cada unidad adicional del recurso correspondiente que pudieramos conseguir. Esto nos permite tambi´ en interpretar dichos valores como la mayor cantidad que estar´ıamos dispuestos a pagar por una unidad adicional de recurso.

130

Cap´ıtulo 14. DUALIDAD

14.4.

Algoritmo del simplex dual

Vamos a pensar en este apartado en un algoritmo “an´ alogo” al del simplex, pero pensando en el problema dual en lugar de en el primal. Dado un primal (de m´ aximos) diremos que una base del problema primal (no necesariamente factible) si y s´ olo si c − c B B −1 A ≤ 0 Se puede apreciar que dicha definici´ on es equivalente a decir que una base es factible dual si c B B −1 constituye una soluci´ on 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´ on que define las restricciones funcionales del problema dual. Alternativamente, la definici´ on de base factible dual s´ olo implica que la correspondiente base primal verifica las condiciones de optimalidad. Si diera la casualidad que adem´ as fuera factible entonces dicha soluci´ on ser´ıa una soluci´ on ´ optima. El algoritmo simplex dual trabaja con soluciones b´ asicas factibles duales que por medio de operaciones apropiadas finalizar´ an (si es posible) en una soluci´ on que adem´ as ser´ıa factible primal. Mientras el simplex trabaja con soluciones 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´ a” la factibilidad hasta alcanzarla (realmente lo que se ir´ a mejorando ser´ıa las soluciones del dual y = c B B −1 ). El algoritmo del simplex dual va a utilizar herramientas an´ alogas a las utilizadas en el simplex. Los pasos son los siguientes: 1. Construcci´ on de una soluci´ on b´ asica primal que sea b´ asica factible dual (´ optimo del primal). 2. Si una soluci´ on es factible primal entonces dicha soluci´ on ser´ıa ´ optima. 3. En caso de que la soluci´ on no sea factible primal, entonces habr´ıa que construir una soluci´ on b´ asica primal que sea b´ asica factible dual y que sea adyacente a la anterior, para lo cual deberemos determinar que variable sale de la base actual, que variable entra en la nueva base y deberemos realizar la operaci´ on de cambio de base. Ese algoritmo lo hemos estudiado como M´ etodo de Lemke (desarrollado por por C. E. Lemke en 1954).

El dual de un problema grande Corolarios del Tma fundamental Ejercicios

131