Que vendría a ser la ecuación

Que vendría a ser la ecuación (0).

De manera similar, para lograr un cero en el coeficiente de x3 de la ecuación (1),

multipliquemos la ecuación (A) por -1 y sumemos el resultado a la ecuación (1).

(1) Ecuación A: -2x1 + x2 – x3 -1/4X5 = - 6

Ecuación (1): x1 + x2 + x3 + x4 = 12

Nueva Ecuación: - x1 + 2x2 + x4 – 1/4x5 = 6

Finalmente, para lograr un cero en el coeficiente de x3 de la ecuación (3),

multipliquemos (A) por -1 y sumemos el resultado a (3). La nueva ecuación (3)

después de la transformación es:

-2x1 + 2x2 - 1/4x5 + x6 = 2

La solución presente después de la primera iteración es:

(x1, x2, x3, x4, x5, x6) = (0, 0, 6, 6, 0, 2); Z = 48

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

E stos resultados se presentan de una manera sencilla en forma tabular. Al igual

que se hizo con la tabla inicial, registramos solamente los coeficientes de las

variables y los colocamos inmediatamente debajo de la tabla inicial. Esta segunda

tabla proporciona una manera fácil de ver los valores actuales de las variables

básicas después de que se ha realizado la primera iteración.

La tabla inicial y la que resulta después de la primera iteración son las siguientes:

V.B x1 x2 x3 x4 x5 x6 b

Z -2 -5 -8 0 0 0 0

x4 1 1 1 1 0 0 12

x5 8 -4 4 0 1 0 24

x6 0 1 1 0 0 1 8

Tabla Inicial

Tabla Después De La Primera Iteración

V.B x1 x2 x3 x4 x5 x6 b

Z 14 -13 0 0 2 0 48

x4 -1 2 0 1 -1/4 0 6

x5 2 -1 1 0 1/4 0 6

x6 -2 2 0 0 -1/4 1 2

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

Observe que si en la segunda tabla se intercambian las columnas de x5 y x3, de

nuevo se destaca la matriz unitaria.

En este momento, es oportuno preguntarse si la solución que se ha obtenido

después de la primera iteración es la solución óptima. Para responder la pregunta,

veamos si es posible incrementar una de las variables de tal manera que la

función objetivo aumente. La función objetivo después de la primera iteración es:

Z + 14x1 – 13x2 + 2x5 = 48, o bien

Z = -14x1 + 13x2 – 2x5 + 48

Si aumentamos x2 aumentará el valor de Z, puesto que su coeficiente es positivo

(+13). Por consiguiente, todavía no hemos obtenido el valor óptimo y necesitamos

realizar otra iteración. A esta misma conclusión hubiésemos llegado si

observamos que en la tabla después de la primera iteración, todavía existe un

coeficiente (el de x2) que es negativo.

Segunda iteración

Después de la primera iteración, el sistema de ecuaciones queda:

Z = -14x1 + 13x2 -2x5 + 48

-x1 + 2x2 + x4 - 1/4x5 = 6

2x1 - x2 + x3 + 1/4x5 = 6

-2x1 +2x2 - 1/4x5 + x6 = 2

La variable básica entrante es x2, puesto que es la que tiene mayor coeficiente en

la función objetivo, o bien es la del coeficiente más negativo en la tabla después

de la primera iteración.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

P ara determinar la variable básica saliente, procedemos de manera similar a lo

que hizo en la primera iteración.

En este caso xent = x2

Restricción

1 a'12 = 2 , b'1 = 6

2 a'22 = -1 , b'2 = 6

3 a'32 = 2 , b'3 = 2

Las cotas superiores son:

6/2 = 2

+∞ ya que a'22 = -1 < 0

2/2 = 1

La menor cota superior es 1 y corresponde a la tercera restricción. Entonces la

variable básica saliente es x6, es decir, cambiamos x6 por x2. Las nuevas

variables son x4,x3 y x2.

Como x2 es ahora una variable básica, debe tener un coeficiente +1 en la

ecuación (3) y no debe aparecer en ninguna otra ecuación. Esto se logra de la

siguiente manera:

1. Se divide toda la ecuación (3) por 2, que es el coeficiente de x2 en esa

ecuación.

2. Se multiplica la ecuación resultante en el paso 1º. por 13, -2 y +1, unos a

las vez, y se suman los resultados a las ecuaciones (0), (1) y (2).

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

El resultado es:

Z + x1 +3/8x5 + 13/2x6 = 61 (0)

x1 + x4 - x6 = 4 (1)

x1 + x3 + 1/8x5 + 1/2x6 = 7 (2)

x1 + x2 - 1/8x5 + 1/2x6 = 1 (3)

Regla de parada

Como todos los coeficientes de la ecuación (0) son positivos, la solución presente

es óptima; o sea: Z = 61, x4 = 4, x3 = 7, x2 =1 y el resto de las variables son

ceros.

Al igual que en la primera iteración, los resultados se pueden presentar en forma

tabular. La tabla inicial y las que resultan después de la primera y de la segunda

iteración, son las siguientes:

V.B x1 x2 x3 x4 x5 x6 b

Z -2 -5 -8 0 0 0 0

x4 1 1 1 1 0 0 12

x5 8 -4 4 0 1 0 24

x6 0 1 1 0 0 1 8

Tabla Inicial

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

V.B x1 x2 x3 x4 x5 x6 b

Z 14 -13 0 0 2 0 48

x4 -1 2 0 1 -1/4 0 6

x5 2 -1 1 0 1/4 0 6

x6 -2 2 0 0 -1/4 1 2

Primera Iteración

V.B x1 x2 x3 x4 x5 x6 b

Z 1 0 0 0 3/8 13/2 61

x4 1 0 0 1 0 -1 4

x5 1 0 1 0 1/8 1/2 7

x6 1 1 0 0 -1/8 1/2 1

Segunda Iteración

La solución óptima es (x1, x2, x3, x4, x5, x6) = (0, 1, 7, 4, 0, 0); Z = 61

Hemos visto la aplicación del método Simplex para obtener la solución óptima de

un problema de Programación Lineal y su forma tabular asociada. En realidad, el

proceso de hace bastante mas expedito utilizando directamente la tabla, sin tener

que pasar por las ecuaciones correspondientes. La determinación de las variables

básica entrantes y salientes en cada iteración, puede hacerse directamente a

partir de cada una de las tablas.

Ejemplo 4:

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

O bservemos el siguiente ejemplo, recordando los pasos fundamentales en el

método simplex, además del uso de variables artificiales, no confundir con

adicionales.

Maximizar Z = -5x1 + 8x2 + 3x3,

sujeto a

2x1 + 5x2 - x3 ≤ 1

-3x1 - 8x2 + 2x3≤ 4

-2x1 - 12x2 + 3x3≤£ 9

1. Expresamos estas condiciones en forma matricial. Se eligen 3 (m)

columnas linealmente independientes dentro de A ___ P4, P5, P6.

P4 P5 P6

2

5 -1 1 0 0 1

-3 -8 2 0 1 0 4

-2

-

12

3 0 0 1 9

Al introducir estas tres nuevas columnas, estamos utilizando tres variables

adicionales: x4, x5 y x6.

Nuestra función objetivo tendrá la siguiente expresión:

Z = -5x1 + 8x2 + 3x3+ 0x4 + 0x5 + 0x6

Se resuelve el sistema en las variables correspondientes:

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

1 - 2x1 - 5x2 + x3 = x4

4 + 3x1 + 8x2 - 2x3 = x5

9 + 2x1 + 12x2 - 3x3 = x6

Haciendo x1= x2= x3= 0 se obtiene el vértice de salida:

(0,0,0,1,4,9)

Obtenemos, asimismo una "nueva" función objetivo:

Z =-5x1 + 8x2 + 3x3+ 0· (1 - 2x1 - 5x2 + x3)+ 0· (4 + 3x1 + 8x2 - 2x3) + 0· (9 + 2x1

+ 12x2 - 3x3)

2. De aquí obtenemos que z0= 0

3. Para ver si es posible mejorar z0, se examina la función z=f(x1, x2, x3) y de

todos los coeficientes que sean positivos, se coge el mayor. Mientras haya

coeficientes positivos se va a poder mejorar.

Se plantea como aumentar el valor de una variable, de forma que las otras

variables que aparecían en la expresión de Z sigan nulas y, al menos, una

de las que eran distintas de cero se anule.

Actuaremos sobre la variable x2, ya que es la de mayor coeficiente, 8.

Nuestro siguiente vértice debe cumplir las siguientes condiciones:

x2=k>0,

x1= x3= 0

y x4, x5, x6³ 0 y de estas tres variables, al menos, una nula.

Se resuelve el sistema en las variables señaladas, teniendo en cuenta

todas las anteriores condiciones:

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

CONTENIDO DIDÁCTICO DEL CUSO: 100404 – PROGRAMACION LINEAL

1 - 5·k = x4

4 + 8·k = x5

9 + 12·k = x6

Debemos anular x4, ya que es imposible anular x5 y x6, con valores

positivos. La mejor elección será k=1/5,

Con este valor obtenemos el nuevo vértice de salida:

(0, 1/5 ,0,0, 28/5

...