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

...