CALCULO DE SOLUCION INICIAL

Cálculo de solución inicial

Técnicas Cuantitativas en Transporte

27 de marzo de 2020

Solución inicial

Considere el siguiente programa lineal

min x1 + x2 − x3

sujeto a

−x1 − x2 + 2x3 ≥ 3,

−2x1 + x2 + 3x3 ≤ 7,

x1, x2, x3 ≥ 0

Si obtenemos el problema en su forma básica , obtenemos

−x1 − x2 + 2x3 − x4 = 3,

−2x1 + x2 + 3x3 + x5 = 7,

x1, x2, x3, x4, x5 ≥ 0

El inconveniente introducido por la primer restricción es que no es posible obtener un bloque de la matriz

identidad, en la columna correspondiente a x4 y x5, como componentes básicas. Por lo que no se puede

empezar facilmente el método simplex. El objetivo de los siguientes métodos es obtener una solución básica

factible para éste tipo de programas lineales (que no tienen una matriz identidad). Supongamos que se tiene

el siguiente programa lineal.

min c

0

· x

sujeto a

Ax ̄ =  ̄b

con A una matriz de tamaño m × n. Tal que A no tiene un bloque de matriz identidad de tamaño m × m.

Método de las dos fases

El primer método, llamado de las dos fases, consiste en introducir otras variables, llamadas variables arti-

ficiales . Esto permite separar el problema en 2 partes, por que se introducen dos programas lineales, el

primero busca encontrar la solución básica inicial, a partir de dicha solución, se empieza las iteraciones del

método simplex en formato Tableau.

En el siguiente ejemplo, mostramos como se introducen las variables artificiales.

Ejemplo.

Supongamos que tenemos las siguientes restricciones.

x1 + 2x2 ≥ 4,

−3x1 + 4x2 ≥ 5,

2x1 + x2 ≤ 6,

x1, x2 ≥ 0

1

Introducimos las variables de holgura

x1 + 2x2 − x3 ≥ 4,

−3x1 + 4x2 + x4 ≥ 5,

2x1 + x2 ≤ 6,

x1, x2 ≥ 0

Introducimos las variables de holgura

x1 + 2x2 − x3 = 4,

−3x1 + 4x2 − x4 = 5,

2x1 + x2 + x5 ≤ 6,

x1, x2, x3, x4, x5 > 0

El problema con las dos primeras restricciones es que generan variables con signo negativo, si quisieramos

encontrar las soluciones básicas factibles con x3, x4 y x5 entonces algunas de las variables serían negativas.

Para el método de dos fases, introducimos otras variables además de las de holgura. En las mismas restric-

ciones que tienen el signo negativo agregamos tantas variables como sean necesarias para tener un bloque de

la matriz identidad.

Introducimos las variables artificiales.

x1 + 2x2 − x3 + x6 = 4,

−3x1 + 4x2 − x4 + x7 = 5,

Ahora tenemos una solución factible, x6 = 4, x7 = 5, y x5 = 6.

Buscamos un programa lineal cuya solución factible contenga a variables de holgura y básicas.

Ahora tenemos a una matriz con las variables del problema original, las variables de holgura y las artificiales,

el nuevo problema se puede escribir de la forma

Ax ̄ + Ix ̄a =  ̄b

Se busca que eventualmente todas las variables artificiales salgan de la componente básica. Por tanto se

busca minimizar a una función de costo que solo incluya a las variables artificiales. Así, el primer problema

lineal es

Fase I

min 1 · x ̄a

sujeto a

Ax ̄ +  ̄xa =  ̄b,

x,  ̄ x ̄a ≥ 0

Aqui x ̄a son las variables artificiales. Al programa lineal anterior se le llama la primer fase.

• Si x ̄a 6= 0 entonces no existe el óptimo en el problema original.

• Si por el contrario, x ̄a =  ̄0 y la componente básica xB no contiene a ninguna variable artificial, entonces,

dejando de considerar a las variables artificiales en el problema original el vector

xB, xNB

es una

solución factible. A partir de dicha solución básica factible resolvemos el problema

2

Fase II

min c · x ̄

sujeto a

Ax ̄ =  ̄b,

x ̄ ≥ 0

usando como punto de partida la solución inicial de la fase I.

Ejemplo

Resolver el siguiente problema por medio del método de las 2 fases.

min x1 − 2x2

sujeto a x1 + x2 ≥ 2

−x1 + x2 ≥ 1

x2 ≤ 3

x1, x2 ≥ 0

Su forma estándar:

min x1 − 2x2

sujeto a x1 + x2 − x3 = 2

−x1 + x2 − x4 = 1

x2 + x5 = 3

x1, x2, x3, x4, x5 ≥ 0

Ya con el programa en la forma estándar, vemos que las variables de holgura no forman a la matriz identidad,

por lo que no podemos obtener una solución básica factible. Para las primeras dos restricciones, introducimos

las variables artificiales x6 y x7.

sujeto a x1 + x2 − x3 + x6 = 2

−x1 + x2 − x4 + x7 = 1

x2 + x5 = 3

x1, x2, x3, x4, x5, x6, x7 ≥ 0

Por lo que la fase I está dada por

min x6 + x7

sujeto a x1 + x2 − x3 + x6 = 2

−x1 + x2 − x4 + x7 = 1

x2 + x5 = 3

x1, x2, x3, x4, x5, x6, x7 ≥ 0

Aplicando el método simplex en formato Tableau.

3

Vemos que hay un ciclo en el método simplex, pues los costos en x3 son 0. Pero una solución básica factible

es x1 = 1/2, x2 = 3/2, x5 = 5/2, x3 = 0 y x4 = 0.

Fase II

Partiendo del tableau sin x6 ni x7

Reemplazamos el vector de costos del problema original, z = x1 − 2x2

Aplicamos el método simplex, con el formato Tableau nuevamente.

Esto nos da la solución óptima en (0, 3, 1, 2, 0) y el valor óptimo −6.

El método de la gran M.

El uso de las variables artificiales es una forma de obtener una solución básica inicial en el método simplex. El

método de las dos fases falla en obtener una solución básica si una variable artificial es parte de la componente

básica. Otra posibilidad consiste en considerar al problema original, de tal forma que las variables artificiales

tienen un costo exorbitante, el método simplex eliminará las variables artificiales si el costo es suficientemente

grande para cada una de las variables artificiales (en el entendido que el problema es de minimización).

Suponga que  ̄b es un vector tal que todas sus coordenadas cumplen con bi ≥ 0. Escribimos de manera

simplificada  ̄b ≥ 0 y el programa lineal esta dado por

min c · x ̄

sujeto a Ax ̄ =  ̄b

x ̄ ≥ 0

En el método de la gran M en vez de dividi el problema en dos partes, consideramos el programa lineal y

lo único que va a cambiar, además de las variables artificiales en las restricciones, es la presencia de costos

“artificiales”.

min c · x ̄ +M1x ̄a

sujeto a Ax ̄ + ̄xa =  ̄b

x ̄ ≥ 0, x ̄a ≥ 0

4

Cuando M es suficientemente grande el término M se interpreta como un costo de penalización por tener a

las variables artificiales en la componente básica.\ Al igualque en el método de las dos fases, al resolver el

método simplex del problema, pueden ocurrir dos posibilidades.

• Todas las variables artificiales son nulas.

...