Método simplex

1

Método Simplex estándar

José Alberto Lorda Abadías

1. Introducción

El método Simplex estándar 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 Simplex utiliza un algoritmo iterativo cuyo objetivo es alcanzar

eficientemente la solución óptima de un problema. Garantiza que si una solución óptima

existe, se encuentra en un número finito de iteraciones. 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.

2. Problema que soluciona el método Simplex estándar

El método Simplex es capaz de determinar el punto o puntos que optimizan una función

Z constituida por n variables no negativas, y sometida a m restricciones que tienen la

forma de inecuaciones de tipo ≤, con la parte de la derecha no negativa:

(1) Problema a optimizar

Función

� = �1�1 + �2�2 + ⋯ �

Restricciones:

1) 11�1 + 12�2 + ⋯ + 1� ≤ �1

2) 21�1 + 22�2 + ⋯ + 2� ≤ �2

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

�) �1�1 + �2�2 + ⋯ + �� ≤ ��

Nota: El método Simplex estándar tan solo aborda el problema de optimización cuando las

restricciones tienen la forma de una inecuación del tipo ≤. En caso de que las restricciones

tengan la forma de ecuaciones o bien inecuaciones del tipo ≥, se emplean versiones

modificadas del método Simplex tales como el método de las dos fases.

2

2.1 Análisis del problema

Al espacio formado por las Xi variables que satisfacen las m restricciones se

denomina espacio factible. Un requisito que debe cumplir el punto que optimiza la

función es que pertenezca a dicho espacio. Se puede demostrar que el punto que

optimiza una función sometida a varias restricciones es justamente uno de los vértices

del espacio factible.

Ejemplo I.

Consideramos una función de dos variables Z=2X+Y sometida a las siguientes

restricciones: i) 20Y+3X≤60, ii) Y+4X≥20, iii) 3Y+X≤15, representando gráficamente

obtenemos la figura (1)

Figura 1. Representación en el espacio X-Y de las tres restricciones, en el caso en el que se

cumple la igualdad: i) 20Y+3X=60, ii) Y+4X=20, iii) 3Y+X=15.

En este ejemplo el espacio del problema es el plano X-Y. El área factible corresponde a la

zona amarilla de la figura, allí todos los puntos contenidos satisfacen las condiciones i)

ii) y iii). Si existe un punto o puntos que optimizan la función Z y que además satisfacen

las condiciones impuestas, dicho punto o puntos son uno de los vértices O, P, Q o R.

En el ejemplo I, tan solo existen 4 vértices del área factible, de modo que encontrar el

punto óptimo no es una tarea demasiado dura. Sin embargo, en problemas grandes con

muchas variables y muchas restricciones, para encontrar el punto óptimo es necesario un

procedimiento que permita identificar y evaluar todos los vértices del área factible, y este

es el objetivo del método Simplex.

3

3. Paso previo a la aplicación del método Simplex: Obtener la forma estándar

del problema.

Como se ha indicado en el apartado 2, el punto o puntos que optimizan la función

satisfaciendo al mismo tiempo las restricciones, son uno o varios vértices del espacio

factible. Como estos vértices son en realidad intersecciones entre ecuaciones, para poder

determinar y evaluar dichos vértices el primer paso a realizar es transformar las

inecuaciones en ecuaciones. Por otro lado el método Simplex exige dos condiciones más:

que todas las variables que intervienen en el problema sean no negativas y que la parte

de la derecha de cada ecuación sea no negativa. Cuando el problema inicial adopta la

forma en la cual se satisfacen estas tres condiciones se dice que el problema ha adquirido

su forma estándar. Veamos ahora cuales son las transformaciones que se deben aplicar

para conseguir que el problemas adopte la forma estándar.

i) Para convertir una inecuación del tipo ≤ a una ecuación, se introduce una

variable de holgura hi no negativa sumando en la parte de la izquierda:

��: 11�1 + 12�2 ≤ �1 → 11�1 + 12�2 + ℎ1 = �1

ii) En el caso en que la parte de la derecha de la ecuación sea negativa, se

multiplica toda la ecuación por -1:

��: 11�1 + 12�2 + ℎ1 = −�1 → − 11�1 − 12�2 − ℎ1 = �1

Realizando estas transformaciones en cada una de las m restricciones obtenemos un

sistema de m ecuaciones lineales (cada una con la parte de la derecha no negativa) con

n+m variables no negativas.

(2) Forma estándar del problema

11�1 + 12�2 + ⋯ + 1� + ℎ1 = �1

21�1 + 22�2 + ⋯ + 2� + ℎ2 = �2

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

�1�1 + �2�2 + ⋯ + �� + ℎ� = ��

� − �1�1 − �2�2 − ⋯ − �� = 0

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

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

igual al número de ecuaciones, por lo tanto los vértices del espacio factible están

constituidos por m variables no nulas, denominadas variables de base y n variables nulas

que son las variables fuera de base.

4

4. Aplicación del método Simplex

Una vez que el problema ha adoptado su forma estándar se aplica el método Simplex.

Explicamos brevemente cómo el método Simplex busca el vértice que optimiza la

función: En primer lugar evalúa un vértice inicial, generalmente el origen (X1=0,

X2=0,…Xn=0). Después determina si este vértice es el que optimiza la función, si resulta

que sí, nuestro problema ya está resuelto, si resulta que no, el método simplex salta a

uno de los vértices vecinos, en concreto al que más hace crecer o disminuir el valor la

función (según estemos tratando de determinar el máximo o el mínimo), y vuelve a

determinar si éste es el vértice que optimiza la función, de modo que se repite este

proceso sucesivamente hasta que se alcanza la solución. En los siguientes apartados se

explican detalladamente cada uno de los pasos.

4.1 Vértice de partida.

El método Simplex comienza evaluando el vértice más sencillo de la zona factible: el

origen. El origen viene dado por:

X1=X2=…=Xn=0, como son todas ellas nulas, estas son las variables fuera de base, si nos

fijamos en (2), las variables de holgura toman los siguientes valores: h1=b1, h2=b2,…,

hm=bm. Por lo tanto para el origen las variables de base son justamente las variables de

holgura.

El valor que adquiere la función es:

Z=C1.0+C2.0+…+Cn.0+0.h1+0.h2+…+0.hm=0

4.2 Representación Simplex

El método Simplex representa el análisis de la función Z para cada vértice en las

denominadas tablas simplex. En la figura (2) está representado el análisis para el vértice

inicial (el origen). En la primera columna aparecen las variables de base (en azul) y la

función Z (en rosa), en la última columna (en amarillo) aparece el valor que toman las

variables de base y la función Z en dicho vértice. En el resto de columnas (en verde)

aparecen todas las variables del problema. La tabla está constituida por m filas, una para

cada restricción. En cada fila aparecen los coeficientes aij que acompañan a cada

variable. En la última fila aparece la función Z-C1.X1-C2.X2-…-Cn.Xn-o.h1-0.h2-…-0.hm.

Figura 2. Tabla Simplex del Vértice de partida: El origen.

Tabla Simplex inicial

Base X1 X2 … Xn h1 h2 … hm Valor de Solución

h1 a11 a12 … a1n 1 0 … 0 b1

h2 a21 a22 … a2n 0 1 … 0 b2

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

hm am1 am2 … amn 0 0 … 1 bm

Z -c1 -c2 … -cn 0 0 … 0 0

5

Nota: Los coeficientes que acompañan a las variables h1,h2,…hm son, los aij cero o uno, a

lo largo de todas las filas de las restricciones y los Ci todos cero a lo largo de la fila de la

función Z. Esto es así porque estamos evaluando justamente el origen. En general estas

casillas podrán tomar distintos valores positivos o negativos según el vértice que se esté

evaluando en cada momento.

4.3 Cómo saber si el vértice que estamos evaluando da lugar al valor óptimo.

Analizamos en primer lugar el caso del origen y suponemos que nuestro propósito es

buscar el vértice que maximiza la función Z. En el origen, la base está constituida por el

conjunto de variables h1, h2, ...,hm. El valor que toma la función Z en esta base es:

Z= 0.(h1=b1)+0.(h2=b2)+...+0.(hm=bm) + C1.(X1=0)+C2.(X2=0)+…+Cn.(Xn=0) =0

Variables de base (variables no nulas) Variables fuera de base (variables nulas)

Nos preguntamos ahora si 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 tal

que al entrar a formar parte de la base en sustitución de otra, pueda aumentar el valor de

la función Z?

Contestar a esta pregunta es fácil, la respuesta es, cualquiera con coeficiente Ci

positivo(en la tabla Simplex, cualquiera con valor –Ci negativo). Por otro lado si resulta

que no hay ninguna variable fuera de base cuyo coeficiente Ci sea positivo (en la tabla

Simplex –Ci negativo), quiere decir que no existe ninguna variable fuera de base tal que

al entrar a formar parte de ella pueda incrementar el valor de la función Z, y por lo tanto

en ese caso se habrá alcanzado la solución óptima y el problema habrá llegado a su fin. Si

esto sucediera por ejemplo en el vértice origen, diríamos que en el punto

X1=0,X2=0,…,Xn=0 se alcanza el valor máximo de la función Z, que es Z=0.

En el caso de que nuestro propósito sea minimizar la función, sucede lo contrario. El

valor de la función Z podrá ser menor siempre que exista una variable fuera de base cuyo

coeficiente Ci sea negativo (en la tabla Simplex -Ci positivo). El vértice para el cual la

función alcanza su valor mínimo es aquel en el que no existen variables fuera de base con

coeficiente Ci en la fila de la función negativo (en la tabla Simlex –Ci positivo).

4.4 Variable de entrada

El método Simplex trata de alcanzar el valor óptimo de una función por el camino

más eficiente posible, para ello cuando se verifica que el vértice actual que se está

evaluando no es el que optimiza la función, se busca el camino que parte de este por

donde más crece la función en el caso de buscar el máximo, o por donde más decrece en

el caso de buscar el mínimo. Ello se hace en dos pasos, determinando la variable de

entrada a la base y la de salida. La variable fuera de base que al entrar a formar parte de

ella va a hacer aumentar en mayor cantidad el valor de la función, es aquella con

coeficiente Ci más positivo (en la tabla Simplex con coeficiente –Ci más negativo). Y por

otro lado, la que va a hacer disminuir la función en mayor cantidad es la de coeficiente Ci

más negativo (en la tabla Simplex con coeficiente –Ci más positivo). Por lo tanto el

criterio del método Simplex para elegir la variable de entrada es:

6

Para la búsqueda de un máximo: Variable con coeficiente –Ci más negativo.

Para la búsqueda de un mínimo: Variable con coeficiente –Ci más positivo.

Ejemplo: Consideramos que tratamos de encontrar el máximo de una función Z(X1,X2)

sometida a tres restricciones. Previamente se han introducido las variables de holgura

X3, X4 y X5. Nos imaginamos que la siguiente tabla Simplex corresponde al análisis de un

determinado vértice de la zona factible.

Tabla Simplex

Base x1 x2 x3 x4 x5 solución

x3 2 1 2 1 0 30

x4 5 4 5 4 10 15

x5 7 5 1 0 0 47

Z -3 -1 0 1 2 45

En esta tabla Simplex, las variables X1 y X2 están fuera de base por lo tanto su valor es

X1=0 y X2=0, es decir se está evaluando el origen. El valor que toma la función Z en el

origen es Z=45.

Como podemos observar en la fila de la función Z aparecen coeficientes negativos, por lo

tanto el vértice que estamos analizando no es el óptimo. Esto quiere decir que existe un

vértice vecino para el cual el valor de la función Z crece. Para pasar a evaluar al vértice

vecino para el cual la función Z crece en la mayor cantidad posible debemos elegir en

primer lugar como variable de entrada X1, ya que –C1=-3 es el coeficiente más negativo de

la fila de la función.

4.5 Variable de salida

El criterio que sigue el método Simplex para determinar la variable que debe salir de

la base, es elegir aquella que más restringe el crecimiento o disminución de la función Z

cuando entra la nueva variable a la base. Esto se puede determinar de forma sencilla

mediante el cociente de radio. 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 base. Tan sólo tiene

significado físico aquellos cocientes de radio positivo. 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. Un cociente de radio pequeño significa que la variable de

base restringe mucho el crecimiento que produce la variable de entrada. Por ello como

variable de salida se elige aquella para la cual se obtiene el cociente de radio positivo más

pequeño.

7

Ejemplo: Consideramos de nuevo el caso del ejemplo anterior en el que ya habíamos

visto que la variable de entrada era X1.

Para determinar cuál es la variable que sale de la base calculamos los cocientes de radio:

X3:X1�30/2=15

X4:X1�15/5=3

X5:X1�49/7=7

Como el cociente de radio más pequeño es el de la variable X4, esta será la variable de

salida.

4.6 Cálculo de la nueva tabla Simplex

En el ejemplo anterior, se mostraba la tabla Simplex correspondiente al análisis de

un vértice del espacio factible. Se vio que en dicho vértice la función no alcanzaba su

valor óptimo, así que el siguiente paso a dar es determinar cuál es el vértice vecino en el

que la función Z crece en mayor cantidad. Para ello en primer lugar se determina la

nueva base del espacio factible, determinando cual es la variable de entrada (vimos que

era X1) y cuál la de salida (ya vimos que era X4). Una vez hecho esto se recalcula la

nueva tabla Simplex que surge al pasar de la base formada por (X3, X4, X5) a la base

formada por (X3, X1, X5). La nueva tabla Simplex nos dará el nuevo vértice y el valor que

adquiere la función Z.

Antes de calcular la nueva tabla Simplex, se definen los siguientes elementos: Se define la

columna y la fila pivote como la columna de la variable de entrada y la fila de la variable

de salida respectivamente. Y se define el término pivote como la intersección entre la

columna y la fila pivote. Una vez realizadas estas definiciones se procede a calcular la

nueva tabla Simplex.

En primer lugar se calculan los nuevos coeficientes de la fila pivote. Cada nuevo

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

Ejemplo

El término pivote es la intersección de la columna y la fila pivote, X1 y X4

respectivamente, por lo tanto el término pivote es igual a 5.

Tabla Simplex


x3 2 1 2 1 0 30

x4 5 4 5 4 10 15

x5 7 5 1 0 0 49

Z -3 -1 0 1 2 45

8

Tabla Simplex


x3 2 1 2 1 0 30

x4 5 4 5 4 10 15

x5 7 5 1 0 0 49

Z -3 -1 0 1 2 45

Los nuevos coeficientes de la fila pivote son: 5/5=1; 4/5; 5/5=1; 4/5; 10/5=2 y 15/5=3.

En la siguiente tabla aparecen los nuevos coeficientes de la fila pivote y el resto de filas

con sus coeficientes antiguos:

Tabla Simplex


x3 2 1 2 1 0 30

X1 1 4/5 1 4/5 2 3

x5 7 5 1 0 0 49

Z -3 -1 0 1 2 45

Tras calcular los nuevos coeficientes de la fila pivote se recalculamos los coeficientes en

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.

Ejemplo:

Nuevos Coeficientes de la fila X3:

2-(2.1)=0; 1-(2.(4/5))=-3/5; 2-(2.1)=0; 1-(2.(4/5))=-3/5; 0-(2.2)=-4; 30-(2.3)=24

Nuevos Coeficientes de la fila X5:

7-(7.1)=0; 5-(7.(4/5))=-3/5; 1-(7.1)=-6; 0-(7.(4/5))=-28/5; 0-(7.2)=-14; 49-(7.3)=28

Nuevos Coeficientes de la fila Z:

-3+(3.1)=0; -1+(3.(4/5))=7/5; 0+(3.1)=3; 1+(3.(4/5))=17/5; 2+(3.2)=8; 45+(3.3)=54

La nueva tabla Simplex es:

Tabla Simplex


x3 0 -3/5 0 -3/5 -4 24

X1 1 4/5 1 4/5 2 3

x5 0 -3/5 6 -28 -14 28

Z 0 7/5 3 17/5 8 54

9

Como se puede ver en la tabla anterior se ha llegado a la solución óptima ya que en la fila

de la función no existen coeficientes negativos. Por lo tanto, la función Z(X1,X2) alcanza

su valor máximo Z=54 en el vértice (X1=3, X2=0).

Ejemplo de aplicación del método Simplex estándar

Dada la función � = ��, �) = 3. � + 2. �, obtener su valor máximo cumpliendo las

siguientes condiciones: i) 2� + � ≤ 18, ##) 2� − 3� ≤ 42, ###) 3� + � ≤ 24 y

#%) � ≥ 0, � ≥ 0:

Transformamos el problema a la forma estándar: Para ello introducimos las variables de

holgura h s y d en las restricciones:

i) 2X+Y+h=18

ii) 2X+3Y+s=42

iii) 3X+Y+d=24

La forma estándar del problema consiste en un sistema de 3 ecuaciones lineales con la

parte de la derecha no negativa, con 5 variables no negativas: X, Y, h, s y d. Por lo tanto la

base del espacio factible estará constituida por 3 variables no nulas. Las otras dos

variables se encontrarán fuera de base y serán nulas.

En primer lugar analizamos el vértice más sencillo del espacio factible: El origen.

El origen viene dado por X=0 Y=0, por lo tanto X e Y son las variables fuera de base. Por

otro lado las variables de base son: h=18, s=42 y d=24.

Construimos la tabla simplex para el vértice inicial, el origen:

Tabla Simplex 1

Base X Y h s d solución

h 2 1 1 0 0 18

s 2 3 0 1 0 42

d 3 1 0 0 1 24

Z -3 -2 0 0 0 0

Vértice (X=0,Y=0), Z=0: No es el optimo ya que existen coeficientes en la fila Z negativos.

Iteración I:

Buscamos el vértice vecino donde más crece la función Z:

Variable de entrada: X

Cocientes de radio: h/X=18/2=9, s/X=42/2=21, d/X=24/3=8

10

Variable de salida: d

Columna Pivote: X, Fila pivote: d Coeficiente Pivote: 3

Nuevos coeficientes de la fila pivote:

3/3=1; 1/3; 0/3=0; 0/3=0; 1/3; 24/3=8

Nuevos coeficientes de la fila h:

2-(2x1)=0, 1-(2x1/3)=1/3, 1-(2x0)=1, 0-(2x0)=0, 0-(2x1/3)=-2/3 18-(2x8)=3

Nuevos coeficientes de la fila s:

2-(2x1)=0, 3-(2x1/3)=7/3, 0-(2x0)=0, 1-(2x0)=1, 0-(2x1/3)=-2/3 42-(2x8)=26

Nuevos coeficientes de la fila Z:

-3-(-3x1)=0, -2-(-3x1/3)=-1, 0-(-3x0)=0, 0-(-3x0)=0, 0-(-3x1/3)=1 0-(-3x8)=24

Tabla Simlex 2:

Tabla Simplex 2


h 0 1/3 1 0 -2/3 2

s 0 7/3 0 1 -2/3 26

X 1 1/3 0 0 1/3 8

Z 0 -1 0 0 1 24

Vértice (X=1,Y=0), Z=24: No es el optimo ya que existen coeficientes en la fila Z

negativos.

Iteración II:


Variable de entrada: Y

Cocientes de radio: h/Y=2//1/3)=6, s/Y=26/(7/3)=78/7, X/Y=8/(1/3)=24

Variable de salida: h

Columna Pivote: Y, Fila pivote: h Coeficiente Pivote: 1/3


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:

11

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


0+(1x0)=0; -1+(1x1)=0; 0+(1x3)=3; 0+(1x0)=0; 1-(1x2)=-1; 24+(1x6)=30

Tabla Simlex 3:

Tabla Simplex 3


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

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

negativos.

Iteración III:


Variable de entrada: d

Cocientes de radio: Y/d=6/(-2) (no tiene significado físico), s/d=12/4=3, X/d=6/1=6

Variable de salida: s

Columna Pivote: d, Fila pivote: s Coeficiente Pivote: 4


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


0+(1x0)=0; 0+(1x0)=0; 3-(1x7/4)=5/4; 0+(1x1/4)=1/4; -1+(1x1)=0; 30+(1x3)=33

12

Tabla Simlex 4:

Tabla Simplex 4


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 3

Z 0 0 5/4 1/4 0 33

En la tabla Simplex 4 no existen coeficientes negativos en la fila de la función Z por lo

tanto se ha alcanzado la solución óptima. El valor máximo de la función es Z=33 en el

vértice (X=3, Y=12).

Documents

Método simplex