Programación Lineal Metodo Simplex.pdf

Materia: Investigacin Operativa

Profesor: Ing. Pablo E. Godino

- 1 -

MDULO 2: Mtodo SMPLEX

PROGRAMACIN LINEAL: EL MTODO SIMPLEX

2.1 Introduccin En el mdulo anterior hemos estudiado el mtodo grfico para resolver un programa

lineal con dos variables de decisin. La presentacin geomtrica fue til en la exploracin de

propiedades importantes del modelo de programacin lineal.

Dado que la mayora de los problemas del mundo real contienen ms de dos variables

de decisin, dichos problemas son resueltos mediante el mtodo o algoritmo (procedimiento

matemtico repetitivo) simplex, o alguna variable de l. Este mtodo fue creado por George

Dantzig en los ltimos aos de la dcada de los cuarenta. Desde entonces, Dantzig y otros

han continuado su desarrollo, especialmente para ciertas aplicaciones.

Visin general del mtodo simplex El mtodo simplex puede sintetizarse en la siguiente forma: es un mtodo matricial

que consiste en dos faces. La primera fase radica en encontrar una solucin inicial y la

segunda fase consiste en probar si esa solucin es ptima; si esta solucin no es ptima

buscamos otra solucin y probamos nuevamente para ver si la nueva solucin es ptima. Si

sta solucin tampoco lo es, el mtodo se repite hasta encontrar la ptima. Es un mtodo

algebraico sistemtico que examina las esquinas (tambin llamados vrtices o puntos

extremos) de un conjunto factible de programacin lineal en busca de la mencionada solucin

ptima.

2.2 Algunos conceptos bsicos Seguidamente repasaremos algunos conceptos necesarios para continuar con el

desarrollo de este mdulo.

Conjunto Convexo

Un conjunto de puntos S es un conjunto convexo, si el segmento rectilneo que une cualquier

par de puntos de S, se encuentra completamente en S.



- 2 -

Como puede apreciarse en las figuras anteriores a y b, son convexos y la figura c es

no convexa. Para cualquier conjunto convexo S, un punto P es un punto extremo si para cada

segmento rectilneo que se encuentra completamente en S y que pasa por P, P es un extremo

del segmento rectilneo.

Vectores linealmente independientes

Un conjunto de r vectores V1, V2, , Vr son linealmente independiente si:

1*V1 + 2*V2 + + r*Vr + = Implica que 1 = 2 = = r = 0; dnde las i (i = 1, 2, .., r) son nmeros reales.

Combinacin lineal convexa de vectores

Una combinacin lineal convexa de r vectores Vi, V2, Vr es otro vector V, tal que:

V = 1*V1 + 2*V2 + + r*Vr

Con la condicin de que los i 0 y i = 0 para i = 1, 2, .., r

Por ejemplo para el caso de dos dimensiones, si realizamos una combinacin lineal

convexa de dos vectores obtendremos como resultado un punto (vector) que pertenece al

segmento de recta que los une. Grficamente:

Para un problema de PL, en forma estndar, con m ecuaciones de restriccin y n

variables incluidas las de holgura o excedente, enunciamos los siguientes conceptos respecto

al conjunto de soluciones del problema:

Solucin factible o posible de un PL (SF)

Es un conjunto de valores de las variables Xj que verifican el sistema de restricciones

incluidas las de no negatividad.

Solucin Factible Bsica (SFB)

Es toda solucin factible que tiene como mximo m variables positivas; o lo que es lo mismo,

tiene n-m valores de las variables nulos. El nmero mximo de soluciones bsicas es:

C (m, n) = n! / [(n-m)!*m!]



- 3 -

Solucin Factible Bsica No Degenerada

Tiene exactamente m variables positivas, o exactamente n-m variables nulas.

Solucin Factible Bsica Degenerada

Tiene menos de m variables positivas, o ms de n-m variables nulas.

Solucin ptima

Es toda solucin que le da a la funcin Z el mximo (o mnimo) valor.

2.3 Observaciones sobre el conjunto de soluciones de un PL Veamos el siguiente problema de PL (programacin lineal)

Mx. (Z) = 70 x1 + 40 x2

S a 2 x1 + 5 x2



- 4 -

La solucin ptima es:

X1 = 200

X2 = 300

Z* = 29.000

Veamos el grfico y analicemos algunas soluciones (la lnea que esta en rojo

corresponde a la funcin objetivo). La cantidad de soluciones posibles a nuestro problema es

infinito y esta determinada por la zona sombreada de color verde. Una caracterstica del

mtodo simplex es que trabaja con soluciones o puntos extremos y la solucin ptima se

encuentra en uno de ellos, es decir, que estos puntos que se encuentran donde se cortan dos

restricciones o bien cuando una restriccin corta algunos de los ejes.

Los puntos A (donde se corta C1 con C3) y B (donde se corta C1 con eje X2) son

soluciones bsicas factibles, son soluciones bsicas porque se encuentran en un punto

extremo y son factibles porque pertenecen a la regin factible (zona sombreada de verde). El

punto D es una solucin no bsica y factible, es no bsica porque no es punto extremo y

factible por que se encuentra dentro del polgono de soluciones (regin factible). Y el punto C

(donde se corta C3 con eje X1) es una solucin bsica no factible. Es bsica porque es punto

extremo y es no factible porque se encuentra por fuera de la regin factible.

Considerando lo analizado hasta el momento, podemos hacer las siguientes

observaciones:

Para cumplir con las restricciones de no negatividad de las variables,

grficamente se trabaja siempre en el primer cuadrante

El poliedro de soluciones es un conjunto convexo..

Los puntos que resulta necesario considerar para buscar el ptimo, son

los que se encuentran sobre la frontera de la regin factible.

En particular podemos observar que si el PL tiene solucin, sta se

encontrar en, al menos, uno de los vrtices.

Se puede obtener la solucin en cada vrtice resolviendo en forma

simultnea las ecuaciones lineales que lo determinan.

Las soluciones factibles en los vrtices son soluciones factibles bsicas.

Todos los puntos del poliedro de soluciones verifican las restricciones,

es decir que el problema tiene infinitas soluciones factibles.

En todo punto situado sobre una recta no hay sobrante de insumos.

En las ecuaciones determinantes del ptimo (restricciones limitantes), no

hay sobrantes de insumos, por lo tanto, las variables de holgura son

nulas.

En las ecuaciones no determinantes del ptimo (restricciones no

limitantes) siempre hay sobrantes de insumos, o sea, las variables de

holgura son positivas.

Si el funcional verifica su mximo valor en un nico vrtice del poliedro,

significa que el problema tiene una nica solucin ptima.

Si z fuera paralela a una restriccin limitante, el problema tendra

infinitas soluciones ptimas.



- 5 -

Si el ptimo se verifica en un vrtice donde s cruzan 3 o ms rectas de

restriccin, la solucin ptima es degenerada.

2.4 Teoremas de combinaciones lineales convexas de soluciones factibles

Expresaremos una serie de teoremas relacionados con las soluciones factibles de los

problemas lineales, los que resultarn de utilidad en desarrollos posteriores.

Teorema 1

Este teorema se enuncia como: "Toda combinacin lineal convexa de soluciones

factibles, es otra solucin factible".

Para demostrarlo partimos de un PL estndar matricial:

Maximizar CX

AX = B

X

Sean X1, X2, Xr, r vectores soluciones del PL, por lo tanto se verificar:

AX, = B

AX, = B

... (1)

Xr = B

Si multiplicamos miembro a miembro las ecuaciones del sistema (1) por escalares 1;

2, , r, respectivamente, con la condicin que,

i 0 y i =1, i = 1, 2,..., r,

Tendremos:

1 A X1 = 1 B

2 A X2 = 2 B

(2)

r A X2 = r B

Sumando miembro a miembro:

r A X2 = r B

De donde,

A r X2 = B r



- 6 -

Siendo,

i =1,

El vector resultante de la combinacin convexa,

i Xi = Xk

Ser tambin una solucin factible del PL, es decir:

AXk = B

En consecuencia queda demostrado el teorema.

Corolario del teorema 1: el conjunto de todas las soluciones factibles de un PL, si no

es vaco, es un conjunto convexo. Es decir que, si no es vaco, est formado por un

nico elemento o por una infinidad".

Teorema 2

"Si existe ms de una solucin factible que le den el mismo valor a la funcin objetivo,

cualquier combinacin lineal convexa de las mismas, dar al funcional igual valor*.

La demostracin de este teorema es similar al anterior.

Partimos de un PL en forma estndar matricial:

Maximizar CX

AX = B

X

Sean Xi, X2, Xr, r vectores soluciones del PL que dan a la funcin objetivo igual valor,

por lo tanto se verificar:

CX1 = Z0

CX2 = Z0

.. (3)

CXr = Z0

Si multiplicamos miembro a miembro las ecuaciones del sistema (3) por escalares 1;

2, , r, respectivamente, con la condicin que,

i 0 y i =1, i = 1, 2,..., r,

Tendremos:

1 C X1 = 1 Z0

2 C X2 = 2 Z0

(2)



- 7 -

r C X2 = r Z0

Si ahora sumamos miembro a miembro, obtendremos:

C i Xi = i Z0

De donde,

C i Xi = Z0 i

Como,

i =1,

Tendremos que el vector resultante de la combinacin convexa

i Xi = Xk

Es tambin una solucin factible del PL que otorga a la funcin de decisin el mismo

valor Z0, es decir:

CXk = Zo

En consecuencia, de acuerdo a los teoremas 1 y 2, podemos afirmar que cualquier

combinacin convexa de soluciones factibles ptimas es tambin una solucin factible

ptima.

Por lo cual, respecto al conjunto de soluciones factibles ptimas decimos que es un

conjunto convexo, que si no es vaco, esta formado por un elemento o por una

infinidad.

Teorema 3

"Si un PL puede ser resuelto - es decir que posee ptimo existir siempre por lo

menos una solucin factible bsica que tambin sea ptima".

2.5 Mtodo simplex Este mtodo, desarrollado por George Dantzig en 1947, como se mencionara

anteriormente, permite encontrar la solucin ptima de cualquier programa lineal,

cualquiera sea l nmero de variables y ecuaciones que lo forman, e identificar

aquellos problemas que no tienen solucin, o cuya solucin ptima es no acotada.

El algoritmo parte de una solucin bsica inicial, y a travs de sucesivas iteraciones,

explora sistemticamente los vrtics del poliedro de soluciones del Programa Lineal

hasta identificar la solucin ptima.

Si bien con posterioridad, se han desarrollado mtodos que tericamente son ms

eficientes en tiempo computacional para problemas de gran tamao, Simplex ha

demostrado en la prctica, un mejor desempeo en la mayora de ios casos, razn

por la cual es an el de mayor difusin.



- 8 -

El mtodo Simpiex tiene en cuenta las siguientes propiedades de los puntos extremos

o soluciones factibles bsicas:

1.

A) Si existe exactamente una solucin ptima, entonces debe ser una

solucin de punto extremo.

B) Si existen soluciones ptimas mltiples, entonces al menos dos de ellas

deben ser soluciones factibles en puntos extremos adyacentes (slo se

consideran las soluciones factibles).

2. Existe slo un nmero finito de puntos extremos (soluciones factibles

bsicas).

3. Si una solucin en un vrtice es igual o mejor (segn el valor de la funcin

objetivo) que todas las soluciones factibles en los vrtices adyacentes a

ella, entonces es igual o mejor que todas las dems soluciones en los

vrtices, es decir, es ptima.

Recordemos que grficamente, cada vrtice se forma por la interseccin de las rectas

representativas de las restricciones y que los valores de las variables para cada punto

extremo, se encuentran resolviendo en forma simultnea las ecuaciones de restriccin

correspondientes a ese vrtice. A su vez, cada punto extremo o vrtice corresponde a

una solucin posible bsica del problema.

El mtodo Simplex, basndose en estas conclusiones generales, analiza

sistemticamente los puntos extremos de la regin factible hasta identificar el punto

ptimo. Asegurndose en cada paso que el vrtice analizado no es peor que el

anterior, esto es, que le d a la funcin objetivo un valor mejor o al menos igual que el

anterior.

Pasos del mtodo simplex

Teniendo en cuenta lo expresado en el Teorema 3, el algoritmo Simplex busca el

ptimo de un problema de PL recorriendo algunos de los vrtices del poliedro del

conjunto de soluciones factibles de manera que el valor de la funcin objetivo mejore

en cada desplazamiento.

Es decir que analiza las soluciones posibles bsicas del problema hasta encontrar la

ptima, resolviendo en cada paso un sistema de m" ecuaciones con "n" variables.

El mtodo consiste fundamentalmente en dos fases:

En la primera fase se identifica una solucin posible bsica que sirva de punto de

partida.

En la segunda fase o fase iterativa se analiza si dicha solucin es o no ptima, y si no

lo es, a partir de ella se encuentra una mejor.

El Simplex trabaja con tablas o cuadros, cada uno de ellos corresponde a un punto

extremo o vrtice del conjunto de soluciones factibles, es decir a una solucin posible

bsica. Las tablas resumen toda la informacin necesaria de cada solucin.



- 9 -

Primera Fase: identificacin de una solucin factible bsica.

Los pasos a seguir en esta etapa son:

Convertir el modelo a su forma estndar. Esto se logra sumando una variable de

holgura al lado izquierdo de las restricciones de < y restando una variable de

excedente en los primeros miembros de las restricciones de >. Estas variables

debern interpretarse de acuerdo al significado de la restriccin de que se trate, sin

embargo, en la funcin objetivo llevan un coeficiente nulo ya que no agregan nada al

objetivo.

Analizar la matriz de coeficientes del sistema de ecuaciones de restriccin y ver si en

ella existen m vectores unitarios con configuracin de matriz identidad. Las variables

cuyos coeficientes tcnicos (aj) se corresponden con la submatriz identidad, sern

las variables consideradas bsicas en la solucin inicial y sus valores en la solucin

sern los trminos independientes de las restricciones (b). El resto de las variables

sern consideradas no bsicas y, por tanto, su valor en la solucin ser cero. Si la

matriz A no contiene una submatriz identidad o existe algn componente negativo en

el vector B, no se puede determinar en esta instancia una solucin factible bsica

inicial y por lo tanto no es posible comenzar con Simplex.

Armar la tabla de partida, tomando como solucin bsica inicial la correspondiente a

los vectores unitarios identificados en la etapa anterior.

Segunda fase: mejoramiento de la solucin

1. Anlisis de la solucin: analizar si la solucin hallada se puede mejorar, para

ello analizar las diferencias Cj-Zj. Estos valores miden el incremento de la

funcin objetivo ante un aumento unitario en el valor de cada una de las

variables no bsicas. Por lo tanto:

Si una variable no bsica que tenga asociado un (Cj-Zj)>0 ingresa a la base, el

valor de Z aumentar.

Si una variable no bsica que tenga asociado un (Cj-Zj)



- 10 -

de minimizacin), ya que sta es la variable que aumenta (disminuye) ms

rpidamente el valor de la funcin objetivo. Entonces:

Si Z es de Maximizacin, ingresa la variable que verifica mayor diferencia

marginal (Cj-Zj) > 0.

Si Z es de Minimizacin, ingresa la variable que verifica menor diferencia

marginal (Cj-Zj) < 0

3. Variable de salida: para determinar la variable que sale de la base, se

selecciona aquella que tenga el menor cociente entre su valor en la solucin

actual (i) y el coeficiente ik (siendo k la variable que entra) siempre y cuando

dicho coeficiente Sea estrictamente positivo, es decir:

= min.(i / ij)

Este cociente representa el mximo valor que puede tomar la variable entrante, antes

que viole la restriccin de no negatividad.

Si todos los ij y son 0 la solucin es no acotada. Esto significa que la funcin

objetivo podra incrementar (disminuir) infinitamente su valor. Esta situacin es

prcticamente imposible en la realidad, por lo cual corresponde detener el proceso de

clculo y revisar la modelizacin del problema.

4. Actualizacin: se debe actualizar la tabla, mediante operaciones elementales

en filas.

5. Criterio de detencin: el proceso se detiene cuando:

Si Z es de Maximizacin: (Cj-Zj) 0; V j

Si Z es de Minimizacin: (Cj-Zj) 0; V j

Para alguna variable no bsica que pueda entrar a la base se verifica que todos los ij son 0



- 11 -

2.6 Caso de aplicacin Veamos un ejemplo:

Mx. (Z) = 70 x1 + 40 x2

S a 2 x1 + 5 x2



- 12 -

A cada una de estas soluciones las podemos encontrar en el grfico (puntos

grandes), donde se cortan dos restricciones o bien donde una restriccin corta a cada

eje. Veamos nuevamente el grfico para identificarlas.

Podemos analizar cada una de estas soluciones, para ello construiremos la siguiente

tabla:

Sol. X1 X2 S1 S2 S3 Z Observaciones

1 0 0 2.000 800 500 0 Solucin bsica factible no ptima

2 0 400 0 400 100 16.000 Solucin bsica factible no ptima

3 0 800 -2000 0 -300 -- Solucin bsica no factible

4 0 500 -500 300 0 -- Solucin bsica no factible

5 1.000 0 0 -1.200 -500 -- Solucin bsica no factible

6 400 0 1200 0 100 28.000 Solucin bsica factible no ptima

7 500 0 1.000 -200 0 -- Solucin bsica no factible

8 250 300 0 0 -50 -- Solucin bsica no factible



- 13 -

9 166,66 333,33 0 133,33 0 16.999,89 Solucin bsica factible no ptima

10 300 200 400 0 0 29.000 Solucin bsica factible ptima.

De las ecuaciones que habamos formado a partir de las restricciones, agregamos la

funcin objetivo, incorporamos las variables de holgura a esta ltima con coeficiente

cero para que no la altere y obtenemos lo que se llama forma estndar del problema

de programacin lineal.

Mx. (Z) = 70 X1 + 40 X2 +0S1 +0S2 +0S3

Sa 2 X1 + 5 X2 +S1 = 2.000

2 X1 + 1 X2 +S2 = 800

1 X1 + 1 X2 +S3 = 500

x1 ; x2 ; S1 ; S1 ; S1 >= 0

Apartir de la forma estndar de nuestro PL vamos a armar la tabla del simplex,

sacando toda la informacin de la misma con una disposicin conveniente para

trabajar de manera cmoda.

Cj

70 40 0 0 0

Sol. x1 x2 s1 s2 s3

2.000 2 5 1 0 0

800 2 1 0 1 0

500 1 1 0 0 1

A la altura del rengln Cj, vamos a colocar los coeficientes de la funcin objetivo para

cada una de las variables. Por columna tenemos el vector solucin (en la tabla a la

altura de sol.), que corresponde al lado derecho de las restricciones y van a

corresponder al valor de las variables que no son cero (recuerde que el mtodo

simplex trabaja con soluciones bsicas y para obtenerlas se deben hacer dos

variables iguales a cero, y las vamos a llamar variables no bsicas). A la altura de

sol por rengln tenemos identificadas las variables y por debajo tenemos cada uno de

los coeficientes de las restricciones.



- 14 -

Como hemos dicho anteriormente el mtodo simplex arranca con una solucin bsica

inicial, resultndole ms conveniente hacer las variables principales del problema

iguales a cero (X1= 0 y X2= 0), con lo cual del sistema de ecuaciones obtenemos S1

= 2.000, S2 = 800 y S3 = 500. Que corresponde al punto de origen del grfico y la

solucin 1 de la tabla con un valor de Z=0 (valor sombreado a la altura de la columna

sol y fila Zj. Vamos a pasar a completar la primera tabla del simplex que habamos

comenzado con el resto de la informacin.

Cj

70 40 0 0 0

Ck Xk Sol. x1 x2 s1 s2 s3

0 S1 2.000 2 5 1 0 0

0 S2 800 2 1 0 1 0

0 S3 500 1 1 0 0 1

Zj 0 0 0 0 0 0

Cj Zj -- 70 40 0 0 0

X

1 = 0

X2 = 0

Solucin inicial= S1 = 2.000 Z inicial= 0 solucin 1 de la tabla de soluciones

S2 = 800

S 3 = 500

Agregamos el vector Xk que corresponde al vector de las variables que no son cero en esta primera solucin bsica, de ahora en ms las vamos a llamar variables bsicas (porque estn a la base). Ck es un vector columna conformado por los coeficiente de la funcin objetivo de las variables que estn a la base. Por otro lado hemos adicionado el rengln Zj que se calcula haciendo la suma producto del vector Ck por cada uno de los vectores columnas correspondiente, por ejemplo a la altura del vector solucin tenemos: 0*2.000+0*800+0*500 = 0 y corresponde al valor de Z de esta solucin. El rengln Cj - Zj es la prueba que realiza el mtodo para saber si esta solucin es la ptima o no, si en ese rengln existe un valor positivo significa que la solucin no es la ptima (como se observa en la tabla hay mas de un valor positivo), si bien de antemano sabamos que no era el ptimo porque lo vimos a travs del mtodo grfico. Entonces encontramos una solucin, que le llamamos solucin inicial y a partir de cual simplex comienza a trabajar. El siguiente paso consiste en encontrar otra solucin, para ello vamos a sacar unas de las variables que esta a la base (variables que tienen



- 15 -

un valor positivo, esto es, S1, S2 o bien S3 y reemplazarla por X1 o X2 que corresponde a la variable que ingresa en el prximo paso). Intuitivamente si analizamos la funcin objetivo, vemos que nos conviene hacer positivo y lo ms grande posible el valor de la variable X1, ya que es la que tiene mayor coeficiente en la funcin objetivo con lo cual nos hara aumentarla ms rpidamente esta funcin y como se trata de un problema de maximizacin resulta lo ms conveniente. Si vamos a la tabla del simplex nos fijamos en el rengln Cj - Zj encontramos como valor ms positivo a 70 que est a la altura de X1 lo que nos indica que en la prxima tabla es la variable de ingreso. Para saber cual es la variable que sale de la base se realiza lo que se conoce como prueba de la razn, y consiste en hacer el cociente entre el vector solucin y el vector columna de la variable que ingresa (i / ij) y tomar el mnimo. Considerando el mnimo de i / ij nos aseguramos de que ninguna de las variables que esta a la base se vuelva negativa, ya que sera un error gravsimo por la condicin de no negatividad encontrar un i (vector solucin) negativo.

= min.(i / ij)

Cj 70 40 0 0 0

Ck X

k Sol. x

1 x

2 s

1 s

2 s

3

0 s1 2.000 2 5 1 0 0

1=2.000/2

0 s2 800 2 1 0 1 0

2=800/2

0 s3 500 1 1 0 0 1

3=500/1

Zj 0 0 0 0 0 0

Cj - Z

j -- 70 40 0 0 0

El valor ms chico es 2 que est a la altura del rengln de S2, indicando que esta es la variable que se va a de la base en el prximo paso y en su lugar entra X1. En este caso 2 representa el valor que va a tener X1 en la prxima tabla. Para obtener la prxima solucin directamente de la tabla de simplex, vamos a tener que trasladar el vector unitario que esta a la altura de la variable que se va de la base (S2) a la posicin de la columna de X1. Esta operacin no se puede realizar en un mero acto de movimiento fsico, si no que se debe realizar a travs de operaciones elementales de matrices. Recordemos estas tres operaciones: 1). Se pueden intercambiar de posicin dos filas o columnas, 2). Se puede multiplicar a los elementos de una fila por una constante distinta de cero y 3). Una fila se le puede sumar otra fila previamente multiplicado por una constante distinta de cero.



- 16 -

El elemento que est en la interseccin de la fila de la variable que sale con la columna de la variable entrante se la denomina elemento pivot y es el elemento que en el prximo paso o iteracin va a tomar el valor de 1, y es por esta fila por la que comenzamos a trabajar. Entonces para hacer 1 el elemento pivot vamos a multiplicar toda la fila por (operacin 2) y obtendremos lo siguiente:

Cj 70 40 0 0 0

Ck X

k Sol. x

1 x

2 s

1 s

2 s

3

0 s1 2.000 2 5 1 0 0

1=2.000/2

0 s2 800 2 1 0 1 0

2=800/2

0 s3 500 1 1 0 0 1

3=500/1

Zj 0 0 0 0 0 0

Cj - Z

j -- 70 40 0 0 0

70 x1 400 1 0 0

Ahora debemos hacer cero los elemento que estn por encima y por debajo del elemento pivot, para ello nos vamos a valer de la operacin 3. Tomamos la nueva fila calculada, la multiplicamos por el elemento opuesto al que queremos hacer cero y la sumamos a la primera fila de la tabla de simplex original. Entonces para nuestro ejemplo sera la primera nueva fila (la llamamos F1), que es la nueva fila que queremos calcular) resulta de tomar la fila 2 nueva calculada (la lamamos F2) la multiplicamos por el elemento opuesto que queremos hacer cero (en este caso -2) y la sumamos la primera fila de la primera tabla de simplex (que la llamamos F1) en resumen:

F1= F2*(-2) + F1 Para la tercera fila hacemos algo similar: F3= F2*(-1) + F3 Y obtenemos:



- 17 -

Cj 70 40 0 0 0

Ck X

k Sol. x

1 x

2 s

1 s

2 s

3

0 s1 2.000 2 5 1 0 0

1=2.000/2

0 s2 800 2 1 0 1 0

2=800/2

0 s3 500 1 1 0 0 1

3=500/1

Zj 0 0 0 0 0 0

Cj - Z

j -- 70 40 0 0 0

0 S1 1200 0 4 1 -1 0

70 X1 400 1 0 0

0 S3 100 0 0 -1/2 1

Recuerde que simplex trabaja cambiando de a una variable por vez, en el caso anterior sac de la base S2 e introdujo X1 a la base y obtuvo una nueva solucin. Ahora debemos probar si esta solucin es la ptima o no y para ello volvemos a calcular de nuevo Zj y Cj - Zj. Esta nueva solucin por supuesto es otra solucin bsica, es punto extremo y la podemos ubicar sobre el eje X1 en interseccin con la restriccin C2 formando punto (400,0). En el ejemplo el mtodo simplex arranco en el origen y tomo la solucin bsica adyacente inmediata sobre X1, dado que en la funcin objetivo es la que tiene mayor coeficiente. Para a prxima solucin simplex va a analizar la solucin adyacente siguiente en la misma direccin con la que arranco, esto es que si arranco en sentido horario va continuar en esta direccin sin volverse para atrs. Calculemos de Zj y Cj Zj para saber si es la solucin ptima o no, aunque sabemos de antemano que la solucin ptima no esta en este punto.



- 18 -

Cj 70 40 0 0 0

Ck X

k Sol. x

1 x

2 s

1 s

2 s

3

0 s1 2.000 2 5 1 0 0

1=2.000/2

0 s2 800 2 1 0 1 0

2=800/2

0 s3 500 1 1 0 0 1

3=500/1

Zj 0 0 0 0 0 0

Cj - Z

j -- 70 40 0 0 0

0 S1 1200 0 4 1 -1 0

1=1.200/4

70 X1 400 1 0 0

2=400/0.5

0 S3 100 0 0 -1/2 1

3=100/0.5

Zj 28.000 70 35 0 35 0

Cj - Z

j -- 0 5 0 -35 0

X

1 = 400

X2 = 0

Nueva solucin = S1 = 1.200 Z

1 = 28.000 solucin 2 de la tabla de soluciones

S2 = 0

S 3 = 100

Como se muestra en la tabla anterior ya que en el rengln Cj Zj encontramos un valor positivo, lo cual nos esta indicando que en prximo paso es la variable que entra (recordemos que si hubiera ms de un valor positivo, elegimos el ms positivo). Entonces volvemos a hacer la prueba de la razn, esto es, calcular los valores de para saber cuan es la variable que se va de la base. Haciendo memoria, el mtodo simplex trabaja de a una variable por vez, es decir que saca una variable y mete otra (en el prximo paso entra X2 y sale S3). La siguiente solucin que simplex va a analizar es la contigua adyacente en la misma direccin en la que venamos avanzando y como se muestra en el grfico es la solucin ptima.



- 19 -

Entonces vamos a sacar S3 y entra X2, ahora el elemento pivot es que es el elemento que debemos hacer 1 y para ello vamos a multiplicar toda la tercera fila por el valor 2, o sea F3= F3*(2). Para completar la tabla vamos a hacer las siguientes operaciones elementales: F1= F3*(-4) + F1 F2= F3*(-1/2) + F2 Obteniendo la siguiente:

Cj 70 40 0 0 0

Ck X

k Sol. x

1 x

2 s

1 s

2 s

3

0 s1 2.000 2 5 1 0 0

1=2.000/2

0 s2 800 2 1 0 1 0

2=800/2

0 s3 500 1 1 0 0 1

3=500/1

Zj 0 0 0 0 0 0

Cj - Z

j -- 70 40 0 0 0

0 S1 1200 0 4 1 -1 0

1=1.200/4

70 X1 400 1 0 0

2=400/0.5

0 S3 100 0 0 - 1

3=100/0.5

Zj 28.000 70 35 0 35 0

Cj - Z

j -- 0 5 0 -35 0

0 S1 400 0 0 1 3 -8

70 X1 300 1 0 0 1 -1

40 X2 200 0 1 0 -1 2

Y luego calculamos Zj y Cj Zj para determinar si la nueva solucin es ptima o no.



- 20 -

Cj 70 40 0 0 0

Ck X

k Sol. x

1 x

2 s

1 s

2 s

3

0 s1 2.000 2 5 1 0 0

1=2.000/2

0 s2 800 2 1 0 1 0

2=800/2

0 s3 500 1 1 0 0 1

3=500/1

Zj 0 0 0 0 0 0

Cj - Z

j -- 70 40 0 0 0

0 S1 1200 0 4 1 -1 0

1=1.200/4

70 X1 400 1 0 0

2=400/0.5

0 S3 100 0 0 -1/2 1

3=100/0.5

Zj 28.000 70 35 0 35 0

Cj - Z

j -- 0 5 0 -35 0

0 S1 400 0 0 1 3 -8

70 X1 300 1 0 0 1 -1

40 X2 200 0 1 0 -1 2

Zj 29.000 70 40 0 30 10

Cj - Z

j -- 0 0 0 -30 -10

Como puede verse esta es la ltima tabla del simplex dado que en el Cj Zj son todos positivos o nulos, esto significa que hemos encontrado la solucin ptima:



- 21 -

X

1 = 0

X2 = 0

Nueva solucin = S1 = 2.000 Z* = 29.000 solucin ptima

S2 = 800

S 3 = 500

2.6 Mtodo de la variable artificial Al resolver algunos problemas con el mtodo Simplex, numerosas veces sucede que no podemos identificar la solucin bsica de inicial. En general, esto ocurre cuando en el planteo tenemos restricciones de igualdad o inecuaciones del tipo . En el primer caso, no es necesario agregar variables de holgura y en el segundo las agregamos restando (variable de excedente), por lo cual no existirn en la matriz A los m vectores unitarios necesarios para formar la primera solucin bsica. Para solucionar este problema, se utiliza la tcnica de la base artificial o simplemente variables artificiales. Se trata de un artilugio matemtico por medio del cual, se agregan al problema tantas variables artificiales como vectores unitarios nos falten en la matriz A. De este modo, modificamos el problema original de manera tal que nos permita identificar la solucin de partida. Es importante destacar que estas variables no son variables del problema original. Por ello decimos que, una solucin del mismo, se obtiene una vez que se hayan eliminado de la base todas las variables artificiales. Para que el algoritmo Simplex las elimine de la base rpidamente, se deben agregar en la funcin objetivo precedidas de un coeficiente que deber ser:

En caso de maximizacin, muy grande en valor absoluto y negativo.

Si el problema es de mnimo, muy grande y positivo. Si se verifica la condicin de optimidad y en la base an queda alguna variable artificial, puede suceder alguna de las siguientes dos cosas: s Si la variable artificial qued en la base con un valor positivo, entonces el problema original es no factible. s Si la variable artificial qued en la base pero con un valor nulo, entonces la solucin encontrada s es solucin del problema original y ser degenerada ya que tendr menos de m valores positivos. Respecto de la variable artificial hay tres posibilidades:

a) Que la variable artificial no aparezca en la ltima tabla del simplex, lo que indica que el problema tiene solucin.

b) Que la variable artificial aparezca en la ltima tabla del simplex con un valor igual a cero, esto significa que el problema tiene solucin y la solucin es degenerada.

c) Y por ltimo que la variable artificial aparezca en la ltima tabla del simple, lo que indica que el problema no tiene solucin.



- 22 -

Ejemplo de aplicacin

Mx. (Z) = 8 X1 + 5 X2

S a 4 X1 + 2 X2 = 50

-3 X1 + 1 X2 = 0

X1 ; X2 >= 0

Como puede verse en este problema tenemos una restriccin de menor e igual, una

de mayor e igual y una de igualdad. Para llevarlo a la forma estndar, en el caso de la

primera restriccin simplemente agregamos una variable de holgura y se transforma

la desigualdad en igualdad (+S). Para el caso de la restriccin de mayor e igual

agregamos una variable de excedente (-S), el signo es lo que la diferencia de la de

holgura, y se transforma la desigual en igualdad. Ahora ya hemos transformado las

inecuaciones en ecuaciones y agregamos tantas variables artificiales como son

necesarias; en nuestro caso a la segunda restriccin por ser mayor e igual y a la

tercera que es una restriccin del tipo desigual. Entonces el problema de

programacin lineal en su forma estndar nos queda:

Mx. (Z) = 5 X1 + 8 X2 +0S1 +0S2 - 100A2 - 100A3

Sa 4 X1 + 2 X2 +S1 = 1.000

1 X1 - S2 + A2 = 50

-3X1 + 1 X2 +A3 = 0

X1 ; X2 ; S1 ; S2 ; A2 ; A3 >= 0

Al incorporar las variables artificiales a la funcin objetivo, como se mencionara

anteriormente, hay que darle un valor negativo muy grande en el caso de un problema

de maximizacin, mnimo 10 veces el valor del coeficiente ms alto de la funcin

objetivo. Ahora ya estamos en condiciones de armar la tabla de simplex:



- 23 -

Cj 5 8 0 0 -100 -100

Ck X

k Sol. X

1 X

2 S

1 S

2 A

2 A

3

0 S1 1.000 4 2 1 0 0 0

1=1000/2

-100 A2 50 1 0 0 -1 1 0

2=50/0

-100 A3 0 -3 1 0 0 0 1

3=0/1

Zj -5000 100 -100 0 100 -100 -100

Cj - Z

j -- -95 108 0 -100 0 0

X

1 = 0

X2 = 0

Solucin inicial= S1 = 1.000 Z inicial= -5000

A 2 = 15

A 3 = 0

Lo que diferencia este ejemplo del anterior es simplemente el armado de la primera tabla, de ahora en ms seguimos utilizando las mismas operaciones. Entonces en el prximo paso entra la variable X2 y sale A2. Como el elemento pivot ya es 1 copiamos la fila tal cual est, o sea F3= F3



- 24 -

Cj 5 8 0 0 -100 -100

Ck X

k Sol. X

1 X

2 S

1 S

2 A

2 A

3

0 S1 1.000 4 2 1 0 0 0

1=1000/2

-100 A2 50 1 0 0 -1 1 0

2=50/0

-100 A3 0 -3 1 0 0 0 1

3=0/1

Zj -5000 100 -100 0 100 -100 -100

Cj - Z

j -- -95 108 0 -100 0 0

8 X2 0 -3 1 0 0 0 1

Posteriormente debemos hacer cero los elementos que estn por encima y por debajo del elemento pivot. Recuerde que lo que estamos haciendo es trasladar el vector unitario de las variables que sale a la posicin de la variable que entra. A continuacin desarrollamos el simplex completo.



- 25 -

Cj 8 5 0 0 -100 -100

Ck X

k Sol. X1 X2 S1 S2 A2 A3

0 S1 1.000 4 2 1 0 0 0 1=1000/2

-100 A2 50 1 0 0 -1 1 0 2=50/0

5 A3 0 -3 1 0 0 0 1 3=0/1

Zj -5000 100 -100 0 100 -100 -100

Cj - Z

j -- -95 108 0 -100 0 0

0 S1 1.000 10 0 1 0 0 -2 1=1000/10

-100 A2 50 1 0 0 -1 1 0 2=50/1

8 X2 0 -3 1 0 0 0 1 3=0/-3

Zj -5000 -124 8 0 100 -100 8

Cj - Z

j -- 129 0 0 -100 0 -108

0 S1 500 0 0 1 10 -10 -2 1=500/10

5 X1 50 1 0 0 -1 1 0 2=50/-1

8 X2 150 0 1 0 -3 3 1 3=0/-3

Zj 1.450 5 8 0 -29 29 8

Cj - Z

j -- 0 0 0 29 -129 -108

0 S2 50 0 0 0,1 1 -1 -0,2

5 X1 100 1 0 0,1 0 0 -0,2

8 X2 300 0 1 0,3 0 0 0,4

Zj 2.900 5 8 2,9 0 0 3/5

Cj - Z

j -- 0 0 -2,9 0 -100 -100

Nota: ij negativo no se tiene en

cuenta para la

seleccin de



- 26 -

X1 = 100

X2 = 300

Nueva solucin = S1 = 50 Z* = 2.900 solucin ptima

S2 = 0

A2 = 0

A3 = 0

2.6 Problema de minimizacin En cuanto a los problemas de minimizacin, criterio de resolucin es prcticamente el mismo, aunque cambian algunos conceptos. Uno de ellos es la prueba que realiza el simplex, esto es el, Cj - Zj para determinar la variable que entra se toma el valor ms negativo y se ha llegado al ptimo cuando todos los valores son nulos o positivos. En cuanto a la prueba de la razn (), tanto en problemas de maximizacin como minimizacin siempre se toma el positivo o nulo de menor valor. Y se llega al ptimo cuando los valores del rengln Cj Zj son todos positivos o nulos. Vamos con un ejemplo. En lo que respecta a la incorporacin de las variables artificiales, como se indicara anteriormente, se incorporan a la funcin objetivo con un coeficiente positivo muy alto (mnimo 10 veces el coeficiente ms alto de la misma). Min. (Z) = 30 X1 + 20 X2

Sa 1 X1 + 3 X2 = 120

X1 ; X2 >= 0

Forma estndar:

Min. (Z) = 30 X1 + 20 X2 +0S1 +0S2 + 100A2

Sa 1 X1 + 3 X2 +S1 = 90

4 X1 + 2 X2 - S2 + A2 = 120

X1 ; X2 ; S1 ; S2 ; A2 ; >= 0



- 27 -

Tabla de simplex:

Cj 30 20 0 0 500

Ck X

k Sol. X1 X2 S1 S2 A2

0 S1 90 1 3 1 0 0 1=90/1

500 A2 120 4 2 0 -1 1 2=120/4

Zj 60.000 2000 1000 0 -500 500

Cj - Z

j -- -1970 -980 0 500 0

0 S1 60 0 5/2 1 1/4 -1/4

30 X1 30 1 1/2 0 -1/4 1/4

Zj 900 30 15 0 -15/2 15/2

Cj - Z

j -- 0 5 0 15/2 1015/2

X

1 = 30

X2 = 0

Nueva solucin = S1 = 60 Z* = 900 solucin ptima

S2 = 0

A2 = 0

Todo problema de minimizacin puede ser resuelto como un problema de maximizacin, multiplicando la funcin objetivo por (-1), aplicamos simplex y una vez obtenido el valor de Z ptimo se lo vuelva a multiplicar por (-1). Compruebe esto.

Min. (Z) = 30 X1 + 20 X2

Sa 1 X1 + 3 X2 = 120

X1 ; X2 >= 0

Max. (Z) = - 30 X1 - 20 X2

Sa 1 X1 + 3 X2 = 120

X1 ; X2 >= 0



- 28 -

2.7 Anexo I: Solucin Win QSB El Win QSB es un software que est disponible en forma gratuita y puede ser descargado desde distintas pginas de internet. Este software nos permite resolver problemas con varias variables y varias restricciones, ms que suficiente para resolver lo problemas desarrollados en la materia. Si el problema es de dos variables tambin lo resuelve grficamente. Ejemplo 1: Mx. (Z) = 70 x1 + 40 x2

S a 2 x1 + 5 x2



- 29 -

Completamos esta tabla con los coeficientes y parmetros de nuestro PL. Hacemos clic en el botn grfico y nos da la solucin grafica a nuestro problema: Solucin del sistema, entramos al men results y hacemos clic en solution summary. Se obtiene el valor de las variables y el valor de la funcin objetivo.



- 30 -

Tambin se puede obtener la ltima tabla del simplex (o sea la solucin ptima) aunque con una disposicin un poco diferente de las columnas, siendo fcilmente detectable si comparamos la tabla del simplex que con la que nos tira el sistema. Entramos en results y hacemos clic en final simplex tableau nos tira el siguiente resultado: Ejemplo 2: Mx. (Z) = 8 X1 + 5 X2

S a 4 X1 + 2 X2 = 50

-3 X1 + 1 X2 = 0

X1 ; X2 >= 0

Ingreso de los datos



- 31 -

Confirmamos haciendo clic en OK, y nos aparece la siguiente tabla: Haciendo clic sobre el signo es te va a cambiar y elegimos el signo segn el tipo de restriccin. Completamos esta tabla con los coeficientes y parmetros de nuestro PL. Hacemos clic en el botn grfico y nos da la solucin grafica a nuestro problema:



- 32 -

Solucin del sistema: ltima tabla del simplex: Ejemplo 3: Mx. (Z) = 30 X1 + 20 X2

S a 1 X1 + 3 X2 = 50

X1 ; X2 >= 0

Ingreso al programa:



- 33 -

Carga de datos: Hacemos clic en el botn grfico y nos da la solucin grafica a nuestro problema: Solucin:



- 34 -

Tabla final del simplex



- 35 -

2.8 Anexo II: Resolucin Automtica de problemas con Mtodo Smplex

Existen sitios web que permiten al usuario resolver problemas lineales on-line

simplemente con la nica tarea de cargar los datos apropiadamente. Si bien es un recurso

adicional a los conocimientos que se esperan del alumno para la resolucin del mtodo

Smplex, es una excelente herramienta de apoyo para corroborar y comprobar ejercicios

resueltos o para disear nuevos ejercicios y cotejar resultados.

La direccin web es la siguiente:

http://www.phpsimplex.com/

Luego recurrimos a la herramienta de resolucin virtual que se encuentra clickeando la

primer palabra que aparece en el texto introductorio: PHPsimplex.

Este paso nos lleva a la siguiente direccin:

http://www.phpsimplex.com/simplex/simplex.htm?l=es

A continuacin se muestra la resolucin completa del problema anterior con la ayuda

on-line de esta herramienta de clculo virtual.



- 36 -

Paso 1: Cargamos la cantidad de variables de decisin que tiene la funcin

objetivo y la cantidad de restricciones que tiene el problema

Paso 2: Conociendo cada uno de los valores correspondientes, armamos la

funcin objetivo y las restricciones de manera idntica a las hemos planteado

en el problema



- 37 -

Paso 3: El programa nos muestra un resumen de los datos ingresados hasta

ahora.

En esta instancia podemos ir paso a paso armando la tabla smplex o ir

directamente a la solucin final.

Paso 4:

Listo! La solucin ptima se expresa resaltada en color verde. Fcil, no?

Esto es todo. Pueden utilizar esta herramienta como apoyo para practicar con otros ejemplos para repasar el mtodo.

Programación Lineal Metodo Simplex.pdf

Documents

Transcript of Programación Lineal Metodo Simplex.pdf