Algoritmo smplex

Enoptimizacin matemtica, el trminoalgoritmo Smplexhabitualmente se refiere a un conjunto de mtodos muy usados para resolver problemas deprogramacin lineal, en los cuales se busca el mximo de unafuncin linealsobre un conjunto de variables que satisfaga un conjunto deinecuaciones lineales. Elalgoritmo Smplex primalfue desarrollado por el matemtico norteamericanoGeorge Dantzigen1947, y procede examinando vrtices adyacentes delpoliedrode soluciones. Un algoritmo Smplex es unalgoritmo de pivote.

Un mtodo llamado de manera similar, pero no relacionado al anterior, es elmtodo Nelder-Mead(1965) o mtodo de descenso (o ascenso) smplex; unmtodo numricoque busca un mnimo (o mximo) local de una funcin cualquiera examinando en cada paso los vrtices de unsimplex.

El algoritmo del mtodo Smplex fue elegido como uno de los 10 algoritmos ms importantes del s.XX (SIAM News, Volume 33, Number 4).

Formulacin Matemtica del problema

Considerar un problema de programacin lineal,

maximizar

sujeto a

El algoritmo Smplex requiere que el problema de programacin lineal est en la forma aumentada de la programacin lineal. El problema puede ser escrito como sigue, en forma de matriz:

Maximizaren:

dondexson las variables desde laforma estndar,xsson las variables de holgura introducidas en el proceso de aumentacin,ccontiene los coeficientes de optimizacin, describe el sistema de ecuaciones contradas, yZes la variable a ser maximizada.

El sistema es tpicamenteno determinado, desde que el nmero de variables excede el nmero de ecuaciones. La diferencia entre el nmero de variables y el nmero de ecuaciones nos da losgrados de libertadasociados con el problema. Cualquier solucin, ptima o no, incluir un nmero de variables de valor arbitrario. El algoritmo Smplex usa cero como valor arbitrario, y el nmero de variables con valor cero es igual a los grados de libertad.

Valores diferentes de cero son llamadosvariables bsicas, y valores de cero son llamadasvariables no bsicasen el algoritmo smplex.

Esta forma simplifica encontrar lasolucin factible bsicainicial, dado que todas las variables de laforma estndarpueden ser elegidas para ser no bsicas (cero), mientras que todas las nuevas variables introducidas en laforma aumentada, son bsicas (diferentes de cero), dado que su valor puede ser calculado trivialmente (para ellas, dado que la matriz problema aumentada en diagonal es su lado derecho)

En cada una de las desigualdades que se plantean en el modelo matemtico de programacin lineal, se plantean desigualdades de , , o =; estas desigualdades se convierten en igualdades completando con variables de holgura si se trata de menor o igual que, o menor que; en el caso de que sea mayor o igual que o mayor que, se completa con variables de excedente, estas con signo negativo ya que como su nombre lo indica, es una cantidad que esta de excedente y hay que quitar para convertirla en igualdad; en caso se maneje el =, se manejan las variables artificiales.

Conceptos bsicos

Forma estndar

Es la igualacin de las restricciones del modelo planteado, as como el aumento de variables de holgura, o bien la resta de variables de exceso.

Forma cannica

En el mtodo Smplex es de bastante utilidad la forma cannica, especialmente para explorar la relacin de dualidad.

Un problema de Programacin Lineal se encuentra en la forma cannica si se cumplen las siguientes condiciones:

Para el caso de la forma cannica de maximizacin:

- La funcin objetivo debe ser de maximizacin.

- Las restricciones son del tipo .

- Las variables de decisin son mayores o iguales a cero.

Para el caso de la forma cannica de la dieta:

- La funcin objetivo es minimizada.

- Las restricciones son de tipo .

- Las variables de decisin son mayores o iguales a cero.

Modelo Ampliado (forma estndar)

Cuando se introduce en cada restriccin una variable artificial que no contenga una variable de holgura.

Problema.- Una Carpintera elabora dos tipos de bates para baseball, uno de peso ligero usado en los juegos de ligas de menores y otro de peso mediano que se vende a los equipos de las ligas mayores.

El bate de menores requiere 1 minuto de torneado en tanto que el bate de mayores requiere 2 minutos de torneado, puesto que se le debe dar la forma y el peso especial. Por tanto, el bate de menores requiere 3 minutos de mquina lijadora y el otro requiere 2 minutos. El laqueado es hecho a mano y entonces solo puede producirse 400 medianos a la semana.

Cada semana se dispone 1000 minutos de torno y 1800 minutos de mquina lijadora. Hay tanta demanda que garantiza las utilidades de S/o 3.00 por cada bate ligero y de S/o4.00 por el otro. Determine el programa de produccin ptima que le d la mxima utilidad a la Carpintera.

Identificacin de variables

X1= N de bates ligeros producidos por semana

X2=N de bates medianos producidos por semana

Z= utilidad por semana

Formulacin Matemtica del Problema (forma cannica)

Max z= 3x1 + 4x2

Sujeto a

X1 + 2x2 1000 (tiempo disponible torno)

3x1 + 2x2 1800 (tiempo disponible lijadora)

X2 400

X1 0, x2 0

Forma estndar del Problema

Max z= 3x1 + 4x2 + 0x3 + 0x4 + 0x5

Sujeto a

X1 + 2x2 + x3 = 1000

3x1 + 2x2 + x4 = 1800

X2 + x5 = 400

xj 0, j=1,2,3,4,5

Variables de entrada

Estas suelen encontrarse en un criterio que se conoce como Condicin de optimalidad, en un modelo, ya sea de maximizacin o minimizacin, y se refiere a la variable no bsica en el rengln z con el coeficiente ms negativo, si se trata de una maximizacin, o el coeficiente ms positivo, si se trata de una minimizacin, la cual, en el la tabla de solucin anterior, a excepcin de la primer tabla, esta variable era una variable bsica.

'Variables de salida

Esta variable es un punto extremo que se encuentra en un criterio conocido como Condicin de factibilidad, en un modelo, ya sea de optimizacin o minimizacin, y se refiere a la variable bsica asociada con la mnima razn no negativa con el coeficiente ms negativo, si se trata de una maximizacin, o el coeficiente ms positivo, si se trata de una minimizacin, la cual, en el la tabla de solucin siguiente, pasar a ser variable no bsica.

Variables bsicas

Variables no bsicas

Variable de entrada

Variable de salida

A

X3, X4, X5, X6

X1, X2

X1

X6

B

X3, X4, X5, X1

X6, X2

X2

X3

C

X2, X4, X5, X1

X6, X3

X6

X4

D

X2, X6, X5, X1

X4, X3

X3

X1

E

X2, X6, X5, X3

X4, X1

X4

X2

Variable degenerada

Una variable degenerada es una variable bsica que vale 0. Grficamente esto puede ocurrir cuando ms de dos rectas se intersequen en el mismo punto.

Base

Conjunto de variables bsicas. En el ejemplo anterior, la base es {X3, X4, X5, X6}

Variable no restringida

Variable artificial

Se usa una variable artificial cuando las restricciones son=yy sucede cuando el origen no se encuentra dentro de la regin factible, tratando de llevar el modelo a otradimensinen la cual el origen si exista en la regin.

Es aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no-negativas.

Funcin objetivo:

Define la efectividad del modelo como funcin de las variables de decisin.

Solucin ptima

Ejemplo grfico de la solucin ptima

Siempre est asociada a un punto extremo de la regin factible y satisface todas las restricciones si se evala en ellas as como es el punto que en el caso de maximizacin hace que el valor de z sea el mximo (ms grande) y el caso de minimizacin sea el mnimo (ms pequeo).

Solucin ptima mltiple

Existen problemas lineales que no tienen una solucin ptima nica, sino que al contrario, tienen un nmero infinito de soluciones.Para detectar una solucin mltiple en la tabla ptima, se deber tener al menos una variable con su Zj-Cj=0 no bsica.

Algoritmo del mtodo Simplex

Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de la regin factible que normalmente es el origen, en cada iteracin se mueve a otro punto extremo adyacente hasta llegar a la solucin ptima.

Los pasos del Mtodo Simplex son los siguientes:

1. Utilizando la forma estndar, determinar una solucin bsica factible inicial igualando a las n-m variables igual a cero (el origen).

2. Seleccionar la variable de entrada de las variables no bsicas que al incrementar su valor pueda mejorar el valor en la funcin objetivo. Cuando no exista esta situacin, la solucin actual es la ptima; si no, ir al siguiente paso.

3. Seleccionar la variable de salida de las variables bsicas actuales.

4. Determinar la nueva solucin al hacer la variable de entrada bsica y la variable de salida no bsica, ir al paso 2 (actualizar).

Ejemplo 1.- Utilizando el algoritmo Simplex resolver el problema:

Max z= 3x1 + 4x2 + 0x3 + 0x4 + 0x5

Sujeto a

X1 + 2x2 + x3 = 1000

3x1 + 2x2 + x4 = 1800

X2 + x5 = 400

Xj 0, j=1,2,3,4,5

x1 x2 x3 x4 x5 bqx3 1 2 1 0 0 1000500 x4 3 2 0 1 0 1800900 x5 0 1 0 0 1 400400C-Z: 3 4 0 0 0 ingresa x2 sale x5x3 1 0 1 0 -2 200200x4 3 0 0 1 -2 1000333.333x2 0 1 0 0 1 400InfC-Z: 3 0 0 0 -4 ingresa x1 sale x4x1 1 0 1 0 -2 200-100x4 0 0 -3 1 4 400100x2 0 1 0 0 1 400400C-Z: 0 0 -3 0 2ingresa x5 sale x4.- U3 = 2200x1 1.0 0 -0.5 0.5 0 400.0x5 0 0 -0.75 0.25 1. 100.0x2 0 1.0 0.75 -0.25 0 300.0C-Z: 0 0 -1.5000 -0.5000 0Solucin ptima: X= [400 300], debe fabricar 400 bates ligeros y 300 bates medianos obteniendo una utilidad mxima de U = 2400

Ejemplo 2

Considerando el problema de programacin lineal:

Minimiza la siguiente funcin

Sujeta a

Se aaden las variables de holgurasyt, que se representan en la tabla cannica

donde las columnas 5 y 6 representan las variables bsicassyty la correspondiente solucin bsica posible es

Las columnas 2, 3 y 4 pueden ser seleccionadas como columnas pivotes, para este ejemplo se seleccion la columna 4. Los valores dexresultantes de la eleccin de las filas 2 y 3 como filas pivotes son 10/1=10 y 15/3=5 respectivamente. De estos el mnimo es 5, por lo que la fila 3 sera la fila pivote. Operando los pivotes se produce

Ahora columnas 4 y 5 representan las variables bsicaszysy la solucin ptima correspondiente es

Para el paso siguiente, no hay entradas positivas en la fila objetivo y de hecho

por lo que el valor mnimo deZes20.

Ejemplo 3.- Resolver mediante el mtodo simplex el siguiente problema:

Maximizar

Z = f(x,y) = 3x + 2y

sujeto a:

2x + y 18

2x + 3y 42

3x + y 24

x 0 , y 0

Se consideran las siguientes fases:

1. Realizar un cambio de variables y normalizar el signo de los trminos independientes.

Se realiza un cambio en la nomenclatura de las variables. Establecindose la correspondencia siguiente:

x pasa a ser X1

y pasa a ser X2

Como los trminos independientes de todas las restricciones son positivos no es necesario hacer nada. En caso contrario habra que multiplicar por "-1" en ambos lados de la inecuacin (teniendo en cuenta que esta operacin tambin afecta al tipo de restriccin).

Normalizar las restricciones.

Se convierten las inecuaciones en ecuaciones agregandovariables de holgura,excesoyartificialessegn la tabla siguiente:

Tipo de desigualdad

Tipo de variable que aparece

- exceso + artificial

=

+ artificial

+ holgura

En este caso se introduce una variable de holgura (X3, X4y X5) en cada una de las restricciones del tipo , para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2X1+ X2+ X3= 18

2X1+ 3X2+ X4= 42

3X1+ X2+ X5= 24

Igualar la funcin objetivo a cero.

Z - 3X1- X2- 0X3- 0X4- 0X5= 0

Escribir la tabla inicial del mtodo Simplex.

La tabla inicial del mtodo Simplex est compuesta por todos los coeficientes de las variables de decisin del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las columnas, siendo P0el trmino independiente y el resto de variables Picoinciden con Xi), y las restricciones (en las filas). La columna Cbcontiene los coeficientes de las variables que se encuentran en la base.

La primera fila est formada por los coeficientes de la funcin objetivo, mientras que la ltima fila contiene el valor la funcin objetivo y loscostes reducidosZj- Cj.

La ltima fila se calcula como sigue: Zj= (CbiPj) para i = 1..m, donde si j = 0, P0= biy C0= 0, y en caso contrario Pj= aij. Aunque al tratarse de la primera tabla del mtodo Simplex y ser todos los Cbnulos se puede simplificar el clculo, y por esta vez disponer Zj= -Cj.

Tabla I . Iteracin n 1

3

2

0

0

0

Base

Cb

P0

P1

P2

P3

P4

P5

P3

0

18

2

1

1

0

0

P4

0

42

2

3

0

1

0

P5

0

24

3

1

0

0

1

Z

0

-3

-2

0

0

0

Condicin de parada.

Si el objetivo es la maximizacin, cuando en la ltima fila (fila indicadora) no existe ningn valor negativo entre los costes reducidos (columnas P1en adelante) se alcanza la condicin de parada.

En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z (columna P0) es la solucin ptima del problema.

Otro caso posible es que en la columna de la variable entrante a la base todos los valores son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solucin siempre resultar mejorable. Ante esta situacin no es necesario continuar iterando indefinidamente y tambin se puede dar por finalizado el algoritmo.

De no ser as, se ejecutan los siguientes pasos de forma iterativa.

Eleccin de la variable entrante en la base.

Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sera la variable X1(P1) de coeficiente -3.

Si existiesen dos o ms coeficientes iguales que cumplan la condicin anterior (caso de empate), entonces se optar por aquella variable que sea bsica.

La columna de la variable que entra en la base se llamacolumna pivote(en colorverde).

Variable saliente de la base.

Una vez obtenida la variable que entra en la base, se procede a determina cual ser la variable que sale de la misma. La decisin se toma en base a un sencillo clculo: dividir cada trmino independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado haya resultado mnimo.

Si hubiera algn elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos los elementos de la columna pivote fueran de sta condicin se habra cumplido la condicin de parada y el problema tendra una solucin no acotada (verteora del mtodo Simplex).

En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

El trmino de la columna pivote que en la divisin anterior dio lugar al menor cociente positivo indica la fila de la variable de holgura que sale de la base. En este caso resulta ser X5(P5), de coeficiente 3. Esta fila se llamafila pivote(en colorverde).

Si al calcular los cocientes, dos o ms resultados cumplen la condicin para elegir el elemento saliente de la base (caso de empate), se escoge aquella que no sea variable bsica (siempre que sea es posible).

La interseccin de lafila pivoteycolumna pivotemarca elelementopivote, en este caso el 3.

Actualizar la tabla.

Los nuevos coeficientes de la tabla se calculan de la siguiente manera:

En la fila del elemento pivote cada nuevo elemento se calcula como:

Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote

En el resto de las filas cada elemento se calcula:

Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote)

Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos de la columna pivote se anulan (anlogo al mtodo de Gauss-Jordan).

Se muestran a continuacin los clculos para la fila P4:

Anterior fila P4

42

2

3

0

1

0

-

-

-

-

-

-

Anterior Elemento Fila en Columna Pivote

2

2

2

2

2

2

x

x

x

x

x

x

Nueva fila pivote

8

1

1/3

0

0

1/3

=

=

=

=

=

=

Nueva fila P4

26

0

7/3

0

1

-2/3

La tabla correspondiente a esta segunda iteracin es:

Tabla II . Iteracin n 2

3

2

0

0

0

Base

Cb

P0

P1

P2

P3

P4

P5

P3

0

2

0

1/3

1

0

-2/3

P4

0

26

0

7/3

0

1

-2/3

P1

3

8

1

1/3

0

0

1/3

Z

24

0

-1

0

0

1

Al comprobar la condicin de parada se observa que no se cumple ya que entre los elementos de la ltima fila hay uno negativo, -1. Se contina iterando nuevamente los pasos 6 y 7.

6.1. La variable que entra en la base es X2(P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.

6.2. Para calcular la variable que sale, se dividen los trminos de la columna P0entre los trminos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor cociente positivo es 6, la variable que sale de la base es X3(P3).

6.3. El elemento pivote es 1/3.

7. Actualizando nuevamente los valores de la tabla se obtiene:

Tabla III . Iteracin n 3

3

2

0

0

0

Base

Cb

P0

P1

P2

P3

P4

P5

P2

2

6

0

1

3

0

-2

P4

0

12

0

0

-7

1

4

P1

3

6

1

0

-1

0

1

Z

30

0

0

3

0

-1

Una nueva comprobacin de la condicin de parada revela que entre los elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solucin ptima y hay que seguir iterando (pasos 6 y 7):

6.1. La variable que entra en la base es X5(P5), por ser la variable que corresponde al coeficiente -1.

6.2. Se escoge la variable que sale calculando el cociente entre los trminos de la columna de trminos independientes y los trminos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]. En esta ocacin es X4(P4).

6.3. El elemento pivote es 4.

7. Despus de actualizar todas las filas, se obtiene la tabla siguiente:

Tabla IV . Iteracin n 4

3

2

0

0

0

Base

Cb

P0

P1

P2

P3

P4

P5

P2

2

12

0

1

-1/2

1/2

0

P5

0

3

0

0

-7/4

1/4

1

P1

3

3

1

0

3/4

-1/4

0

Z

33

0

0

5/4

1/4

0

Fin del algoritmo.

Se observa que en la ltima fila todos los coeficientes son positivos cumplindose, por tanto la condicin de parada.

La solucin ptima viene dada por el valor de Z en la columna de los trminos independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el punto donde se alcanza, observando las filas correspondientes a las variables de decisin que han entrado en la base: X1= 3 y X2= 12.

Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.