Método simplex1

MÉTODO SIMPLEX ESTÁNDAR

José Alberto Lorda Abadías

El método Simplex fue creado en 1947 por el matemático-físico George-Dantzing (1914-2005, Oregón) en el departamento de defensa de los Estados Unidos durante la segunda guerra mundial. Por el desarrollo del método Simplex y otras contribuciones Dantzing es considerado como el “padre” de la programación lineal.

El método utiliza un algoritmo iterativo cuyo objetivo es alcanzar la solución óptima de un problema. Se utiliza, sobre todo para resolver problemas de programación lineal de gran tamaño. El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método Simplex.

Método Simplex estándar. 1 Introducción


Dada una función Z de n variables no negativas (X1,X2,…Xn) sometida a m restricciones con la forma de inecuaciones del tipo ≤ con la parte derecha no negativa, encontrar el valor óptimo (máximo o mínimo).

El método Simplex estándar no aborda el problema en el caso de que las restricciones sean ecuaciones o inecuaciones del tipo ≥, en ese caso se utilizan versiones modificadas como el método de las dos fases.

Problema que resuelve

El valor óptimo debe encontrarse entre todos los puntos que satisfacen las m restricciones, a este conjunto de puntos se le denomina espacio factible.


El punto óptimo se encuentra entre los vértices del espacio factible.

Solución del problema


Ejemplo: Función: Z= 20X+Y

Restricciones:i) 20Y+3X≤60ii) Y+4X≥20iii) 3Y+X≤15

Área factible

Vértices del espacio factible

Para problemas grandes es necesario un procedimiento que permita identificar y evaluar dichos vértices METODO SIMPLEX

Método Simplex estándar. 1 Forma estándar del problema

Problema de optimización

Los vértices del espacio factible son intersecciones entre ecuaciones

Transformar inecuaciones en ecuaciones

¿Cómo convertir inecuaciones en ecuaciones?

Siguiente diapositiva

En cada restricción i se introduce una variable de

holgura hi no negativa sumando a la izquierda

Si la parte de la derecha es negativa se multiplica toda

la ecuación por -1

Método Simplex. 1 Forma estándar del problema

Forma estándar del problema

Problema

……………………………………………………..

……………………………………………………..

Conversión de las inecuaciones en ecuaciones

Método Simplex. 1 Forma estándar del problema

Convertir las inecuaciones en ecuaciones: Se introducen la variables de holgura:

i) Para convertir una inecuación del tipo ≤ a una ecuación se introduce una variable de holgura sumando:

Ejemplo: a11X1+a12X2≤b1a11X2+a12X2+h1=b1

Transformar cada ecuación para que su parte de la derecha sea no negativa.

ii) Si inicialmente la parte de la derecha es negativa se multiplica toda la ecuaciones por -1

Ejemplo: a11X2+a12X2-h1=-b1-a11X2-a12X2+h1=b1

Ejemplo

……………………………………………………..

Método Simplex. 1 Análisis de la forma estándar del problema

La solución de un sistema de ecuaciones lineales requiere que existan el mismo número de ecuaciones que de variables

Las soluciones del problema (vértices del espacio factible), vienen dadas por:

m variables no nulas (variables de base)

n variables nulas (variables fuera de base)

m ecuaciones con n+m incógnitas

Método Simplex estándar.

El método Simplex recorre los vértices del espacio factible de modo eficiente en busca del vértice que optimiza la función.

1. Analiza un vértice del espacio factible inicial: Generalmente por simplicidad analiza el origen.

2. Determina si es el vértice óptimo: -Si es que Sí: El problema ya está resuelto.-Si es que no: Determina el camino que parte del vértice, por donde más crece la función en el caso de que estemos buscando un máximo, determina el camino por donde más decrece la función en el caso de buscar un mínimo. Lo realiza en dos pasos: Determinando variable de entrada (3a) y determinando variable de salida (3b).

4. Determina cual es el nuevo vértice del espacio factible al que se llega por el camino elegido (que surge con el cambio de base).

5. Se vuelve a realizar el paso 2.i) Si existe solución óptima, el método Simplex garantiza que se alcanza en un número finito de iteraciones.ii) La solución óptima se alcanza independientemente del punto de partida

Método Simplex estándar.Problema resuelto

Se propone un problema para explicar el proceso:Dada la siguiente función:

Z(X, Y) = 3.X + 2.Y donde X≥0 e Y≥0

Sometida las siguientes restricciones:

i) 2.X + Y ≤ 18

ii) 2.X+3.Y ≤ 42

iii) 3.X + Y ≤ 24

Encontrar su máximo


Paso previo: Transformar el problema a la forma estándar

Z(X, Y) = 3.X + 2.Y

i) 2.X + Y ≤ 18

ii) 2.X+3.Y ≤ 42

iii) 3.X + Y ≤ 24

Z(X, Y) - 3.X + 2.Y = 0

i) 2.X + Y+ h = 18

ii) 2.X+3.Y +s= 42

iii) 3.X + Y +d= 24

Problema

Forma estándar del problema

Se introducen las variables de holgura h s y d:

Z(X, Y) - 3.X - 2.Y = 0

i) 2.X + Y+ h = 18

ii) 2.X+3.Y +s= 42

iii) 3.X + Y +d= 24

3 ecuaciones (con la parte derecha no negativa) con 5 incógnitas (X, Y, h, s, d) no negativas

Método Simplex estándar. Problema resuelto

Los vértices del espacio factible vendrán dados por:

3 variables de base: variables no nulas2 variables fuera de base: variables nulas

Análisis del problema en su forma estándar.

i) 2.X + Y+ h = 18

ii) 2.X+3.Y +s= 42

iii) 3.X + Y +d= 24

1. Vértice inicial: El origen.X=0, Y=0 : Por lo tanto X e Y son las variables fuera de base

i) h = 18

ii) s= 42

iii) d= 24

h s y d son las variables de base.

Z(X,Y) = 3.(X=0) + 2.(Y=0)+ 0.(h=18)+0.(s=42)+ 0.(d=24) = 0


Base x y h s d V.Sh 2 1 1 0 0 18s 2 3 0 1 0 42d 3 1 0 0 1 24Z -3 -2 0 0 0 0

Método Simplex estándar. Problema resuelto1. Representación del origen en una tabla Simplex

i) 2.X + Y+ h = 18

ii) 2.X+3.Y +s= 42

iii) 3.X + Y +d= 24

Z - 3.X - 2.Y = 0

En la primera columna aparecen las tres variables de base (en azul) y la función Z (en rosa). En la ultima columna (en amarillo) los valores de las variables de base y de la función Z. El resto de columnas (en verde) aparecen todas las variables del problema

La tabla Simplex está constituida por filas correspondientes a cada restricción y la última fila donde aparece la función Z- Cx.X-Cy.Y-Ch.h-Cs.s.Cd.d=0

Z(X,Y) = 3.(X=0) + 2.(Y=0)+ 0.(h=18)+0.(s=42)+ 0.(d=24) = 0


2. Cómo saber si el vértice que estamos evaluando es el que optimiza la función:

En el caso del origen:

¿Existe un vértice distinto del origen, en el cual, el valor de la función Z pueda alcanzar un valor mayor?O dicho de otro modo…¿Existe un variable fuera de base, tal que al entrar a formar parte de la base en sustitución de otra, pueda aumentar el valor de la función Z?

Cualquiera con coeficiente Ci positivo (en la tabla simplex cualquiera con –Ci negativo)

Variables fuera de base

Variables de base


2. Cómo saber si el vértice que estamos evaluando es el que optimiza la función:i) Si el objetivo es encontrar el máximo:El vértice que estamos evaluando no será un máximo si existen variables fuera de base con coeficientes Ci positivos (en la fila de la función Z en la tabla simplex, -Ci negativos).

ii) Si el objetivo es encontrar el mínimo:El vértice que estamos evaluando no será el mínimo si en existen variables fuera de base con coeficientes Ci negativos (en la fila de la función Z en la tabla simplex, -Ci positivos).



En nuestro caso, en la fila de la función Z las variables X e Y tienen coeficientes –Ci negativos, luego el origen no es el máximo de la función.

2. Cómo saber si el vértice que estamos evaluando es el que optimiza la función:


3. Determinar el camino por donde más crece ( o decrece) la función:

Si nuestro objetivo es determinar el máximo: Determinar el camino que parte del vértice actual por donde más crece la función Z.

Si nuestro objetivo es determinar el mínimo: Determinar el camino que parte del vértice actual por donde más disminuye la función Z.¿Cómo hacerlo?

3.a Determinando la variable fuera de base que va a entrar en la base.

3.b Determinando la variable de base que debe salir de ella

3.a Variable que va a entrar en la base:i) Si el objetivo es calcular el máximo: La variable que entra en la base es aquella con coeficiente Ci más positivo ( en la tabla Simplex con coeficiente –Ci más negativo) ya que es la que más va a hacer crece la función.

ii) Si el objetivo es calcular el mínimo: La variable que entra en la base es aquella con coeficiente Ci más negativo ( en la tabla Simplex con coeficiente –Ci más positivo) ya que es la que más va a hacer disminuir la función.



Z(X,Y) = 3.(X=0) + 2.(Y=0)+ 0.(h=18)+0.(s=42)+ 0.(d=24) = 0


3.a Variable de entrada en el caso del origen:

Variables fuera de base

Variables de base


La variable fuera de base que al entrar en ella va a hacer crecer en mayor cantidad la función Z es la X ya que -3 es el coeficiente -Ci más negativo de la fila de la función Z en la tabla Simplex.


3.b Variable que va a salir de la base:i) Si el objetivo es calcular el máximo: La variable que sale de la base es la que más restringe el crecimiento de la función al entrar la nueva variable de base.

ii) Si el objetivo es calcular el mínimo: La variable que sale de la base es la que más restringe la disminución de la función al entrar la nueva variable de base

¿Cómo saber cual es la variable de base que más restringe el crecimiento o decrecimiento de la función?A través de los cocientes de radio



3.b Variable que va a salir de la base:El cociente de radio entre una variable de base y la variable de entrada se define como el cociente entre el valor que toma la variable de base y el coeficiente de la variable de entrada en la fila de la variable de basei) Tan sólo tiene significado físico aquellos cocientes de radio positivoii) Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir con el método Simplex

iii)Un cociente de radio pequeño significa que la variable de base restringe mucho el

crecimiento que produce la variable de entrada.

Como variable de salida se elige aquella para la cual se obtiene el cociente

de radio positivo más pequeño.



En nuestro caso la variable de entrada era la X, por lo tanto los cocientes de radio son:

h: 18/2=9S: 42/2=21d: 24/3=8

Por lo tanto la variable que sale de la base es la d.

3.b Variable que va a salir de la base:


4. Calcular el nuevo vértice que surge al cambiar de base:

o lo que es lo mismo, calcular la nueva tabla

Simplex:

Una vez determinada la variable de entrada y la variable salida:

En nuestro caso:Columna pivote : XFila Pivote: dTérmino pivote: 3

Definiciones:

Columna pivote: Columna correspondiente a la variable de entrada

Fila pivote: Fila correspondiente a la variable de salida

Término pivote: Término correspondiente a la intersección entre columna y fila pivote


En primer lugar se calculan los nuevos coeficientes de la fila pivote:

4.calcular la nueva tabla Simplex:


Nuevos coeficientes de la fila pivote: 3/3=1 , 1/3, 0/3=0, 0/3=0, 1/3, 24/3=8

En nuestro caso:

Cada nuevo coeficiente de la fila pivote es igual al antiguo dividido para el término pivote.


4.calcular la nueva tabla Simplex:

En segundo lugar se calculan el resto de filas:

El nuevo coeficiente ij es el coeficiente antiguo ij menos el producto entre el coeficiente de la fila i en la columna pivote por el nuevo coeficiente de la columna j en la fila pivote.

Base x y h s d V.Sh 2 1 1 0 0 18s 2 3 0 1 0 42X 1 1/3 0 0 1/3 8Z -3 -2 0 0 0 0

fila h: 2-(2x1)=0, 1-(2x1/3)=1/3, 1-(2x0)=1, 0-(2x0)=0, 0-(2x1/3)=-2/3 18-(2x8)=3fila s: 2-(2x1)=0, 3-(2x1/3)=7/3, 0-(2x0)=0, 1-(2x0)=1, 0-(2x1/3)=-2/3 42-(2x8)=26fila Z: -3-(-3x1)=0, -2-(-3x1/3)=-1, 0-(-3x0)=0, 0-(-3x0)=0, 0-(-3x1/3)=1 0-(-3x8)=24


La nueva tabla Simplex es:

Base x y h s d V.Sh 0 1/3 1 0 -2/3 2s 0 7/3 0 1 -2/3 26X 1 1/3 0 0 1/3 8Z 0 -1 0 0 1 24

El nuevo vértice es: (X=1, Y=0), donde la función Z adquiere el valor Z=24

Observamos que existen en la fila de la función variables fuera de base con coeficientes -Ci negativos, de modo que este vértice no es el que optimiza la función.

Dado que no se ha encontrado el vértice que optimiza la función, se vuelve a repetir el proceso: Iteración 2

Base x y h s d V.Sh 0 1/3 1 0 -2/3 2s 0 7/3 0 1 -2/3 26X 1 1/3 0 0 1/3 8Z 0 -1 0 0 1 24


Iteración II:

Variable de entrada: YCocientes de radio: h/Y=2//1/3)=6, s/Y=26/(7/3)=78/7, X/Y=8/(1/3)=24Variable de salida: hColumna Pivote: Y, Fila pivote: h Coeficiente Pivote: 1/3

Nuevos coeficientes de la fila pivote:0/(1/3)=0, (1/3)/(1/3)=1, 1/(1/3)=3, 0/(1/3)=0, (-2/3)/(1/3)=-2, 2/(1/3)=6

Nuevos coeficientes de la fila s:0-(7/3x0)=0, 7/3-(7/3x1)=0, 0-(7/3x3)=-7, 1-(7/3x0)=1, -2/3+(7/3x2)=4, 26-(7/3x6)=12

Nuevos coeficientes de la fila X: 1-(1/3x0)1; 1/3-(1/3x1)=0; 0-(1/3x3)=-1; 0-(1/3x0)=0; 1/3+(1/3x2)=1; 8-(1/3x6)=6

Nuevos coeficientes de la fila Z: 0+(1x0)=0; -1+(1x1)=0; 0+(1x3)=3; 0+(1x0)=0; 1-(1x2)=-1; 24+(1x6)=30

Método Simplex estándar. Problema resueltoIteración II:

Base x y h s d V.SY 0 1 3 0 -2 6s 0 0 -7 1 4 12X 1 1/3 0 0 1/3 8Z 0 0 3 0 -1 30


Tabla Simplex 3:

Vértice (X=6,Y=6), Z=30. No es el óptimo ya que existen coeficientes en la fila Z negativos.


Iteración 3

Base x y h s d V.SY 0 1 3 0 -2 6s 0 0 -7 1 4 12X 1 1/3 0 0 1/3 8Z 0 0 3 0 -1 30

Variable de entrada: dCocientes de radio: Y/d=6/(-2) (no tiene significado físico), s/d=12/4=3, X/d=6/1=6Variable de salida: sColumna Pivote: d, Fila pivote: s Coeficiente Pivote: 4


Iteración 3

Nuevos coeficientes de la fila pivote:0/4=0; 0/4=0; -7/4; 1/4; 4/4=1; 12/4=3

Nuevos coeficientes de la fila Y:0+(2x0)=0; 1+(2x0)=1; 3-(2x7/4)=-1/2; 0+(2x1/4)=1/2; -2+(2x1)=0; 6+(2x3)=12

Nuevos coeficientes de la fila X:1-(1x0)=1; 0-(1x0)=0; -1+(1x7/4)=3/4; 0-(1x1/4)=-1/4; 1-(1x1)=0; 6-(1x6)=0

Nuevos coeficientes de la fila Z:0+(1x0)=0; 0+(1x0)=0; 3-(1x7/4)=5/4; 0+(1x1/4)=1/4; -1+(1x1)=0; 30+(1x3)=33


Base x y h s d V.SY 0 1 -1/2 1/2 0 12d 0 0 -7/4 1/4 1 3X 1 0 3/4 -1/4 0 3Z 0 0 5/4 1/4 0 33

Tabla Simplex 4

Observamos que en la fila de la función no existen coeficientes –Ci negativos luego el vértice (X=3, Y=12) la función alcanza su valor máximo, Z=33

x y h s dV.S.

h 2 1 1 0 0 18s 2 3 0 1 0 42d 3 1 0 0 1 24Z -3 -2 0 0 0 0

Tabla Simplex I

x y h s dV.S.

h 0 1/3 1 0-

2/3 2

s 0 7/3 0 1-

2/3 26x 1 1/3 0 0 1/3 28Z 0 -1 0 0 1 24

Tabla Simplex II

x y h s dV.S.

y 0 1 3 0 -2 6

s 0 0 -7 1 4 12

x 1 0 -1 0 1 6

Z 0 0 3 0 -1 30

x y h s d V.S.

y 0 1-

1/2 1/2 0 12

d 0 0-

7/4 1/4 1 3

x 1 0 3/4-

1/4 0 3Z 0 0 5/4 1/4 0 33

Tabla Simplex III Tabla Simplex IV

0 1 2 3 4 5 6 7 8 90

2

4

6

8

10

12

14

X

Y

31

3

2

1

2

Z(0,0)=0

Z(8,0)=24

Z(6,6)=30

Z(3,12)=33


Interpretación de los pasos


Bibliografía

Libros:

Métodos cuantitativos. Eduardo Vicens Salort y Angel Ortiz Bas.

Métodos y modelos de investigación de operaciones. Juan Prawda Witenberg .

Web:

www.programaciónlineal.net

www.investigación_operaciones.com

http://www.xn--programacinlineal-pyb.net/

FIN

Documents

Método simplex1