EL MÉTODO SIMPLEX

...

a1X1 + a2X2 + .......... + anXn = bi

Es equivalente a:

a1X1 + a2X2 + .......... + anXn ≤ bi

a1X1 + a2X2 + .......... + anXn≥ bi

-

Una restricción con signo ≤ puede ser cambiada a ecuación (tipo =) si se suma del lado izquierdo una variable no negativa llamada variable de holgura.

a1X1 + a2X2 + .......... + anXn ≤ bi

Es equivalente a:

a1X1 + a2X2 + .......... + anXn+Xh= bi

-

Una restricción con signo ≥puede ser cambiada a ecuación (tipo =) si se resta del lado izquierdo una variable no negativa llamada variable superflua.

a1X1 + a2x2 + .......... + anXn≥ bi

Es equivalente a:

a1X1 + a2X2 + .......... + anXn- Xs= bi

3.

Sobre las condiciones de no-negatividad

-

Una variable no restringida en signo (positivo, negativo ó cero) es equivalente a la diferencia entre dos variables no negativas.

Si X1es no restringida en signo

Es equivalente a:

X1= X2-X3para toda X2 ≥ 0 y X3 ≥ 0

-

Una variable del tipo ≤, es decir X1≤0es equivalente a multiplicarla por –1 para convertir la desigualdad a≥y establecer una relación igualando la variablenegativa a otra variableno-negativa, dónde la nueva variable será mayor o igual a cero.

Si X1 ≤ 0

Es equivalente a:

-X1 ≥0dónde -X1=X2para toda X2 ≥ 0 Al sustituir esta variable, en el modelo original, se deberá hacer con signo contrario para que esta relación sea válida.

Algoritmo del método Simplex

El método simplex es un procedimiento iterativo, iterar significa repetir; descrito someramente, consiste en obtener primero una solución básica factible no-óptima del problema dado y a partir de esta determinar una sucesión de nuevas soluciones básicas factibles no-óptimas, de tal manera que se van mejorando progresivamente los valores de la función objetivo, hasta obtener la solución final que debe ser, si la solución existe, básica factible y óptima. Esto es análogo al método gráfico explicado anteriormente, en donde la solución de los modelos de dos variables se obtiene desplazando una línea recta a través del conjunto de soluciones factibles en la dirección en que se mejora el valor de la función objetivo a optimizarse.

El método simplex emplea una forma tabular para simplificar su procedimiento, la forma se obtiene a partir del modelo matemático expresado en forma estándar e igualando a cero la función objetivo.

Forma estándar del modelo de PL

Maximizar o Minimizar Z - C1X1 - C2X2 +………-CnXn -0xn+1 -0Xn+2 ............-0Xn+m=0S.A.

a11X1 + a12X2 +……… a1nXn +…..+ Xn+1 = b1

a21X1 + a22X2 +……… a2nXn +….+ Xn+2 = b2 …………………………………………………………

a m 1X1 + a m 2X2 +……… a m nXn +…..+ Xn+ m =b m

…………………………………………………………

X1 ≥ 0; X2 ≥ 0;………………… Xn ≥ 0; Xn+m ≥ 0

Tabla Inicial Simplex

[pic 2]

2.2.1 LOS CRITERIOS DE OPTIMALIDAD Y FACTIBILIDAD

Criterio de optimalidad

Una solución básica factible de un modelo de programación lineal es óptima cuando todos los coeficientes en la ecuación "0" (renglón de la función objetivo) son positivos (≥0) para el caso de maximizar, o negativos (≤0) para el caso de minimizar. Si esto ocurre hemos llegado a una solución óptima de lo contrario debemos continuar con el procedimiento iterativo simplex para obtener la siguiente solución básica factible la cual involucra el cambio de una variable no básica por una variables básica (parte1) y viceversa (parte 2) y entonces aplicar el procedimiento para determinar una nueva solución (parte 3)

Parte 1. Para determinar la variable no básica entrante seleccionamos aquella variable cuyo coeficiente, en la ecuación cero (renglón de la función objetivo) sea el más negativo para el caso de maximizar, o el más positivo para el caso de minimizar, una vez que identificamos la variable con el coeficiente más positivo o más negativo según sea el caso, el paso siguiente es enmarcar toda esa columna a la cual llamaremos "Columna Pivotal".

Criterio de factibilidad

Parte 2.Para determinar lavariable básica saliente.Seguir los pasos siguientes:

a)

Seleccionamos de la columna enmarcada (en la parte 1) los coeficientes positivos.

b)

Dividimos cada elemento del vector bi (b1, b2,.........bm) entre su correspondiente elemento positivo, identificado en el inciso a).

c)

De los resultados obtenidos en el inciso b), identificamos la ecuación (fila) que tiene el mínimo cociente, la cual nos indicará la variable básica que saldrá de la base (las variables básicas (VB) se identifican y localizan en la columna número uno de la tabla simplex).

d)

Seleccionando la variable básica saliente, procedemos a marcar la fila, identificada en el inciso c) a la cual llamaremos "Fila Pivotal". Al número que se encuentra en la intersección de la columna y fila enmarcada le llamaremos elemento pivote.

Parte 3.Una nueva solución básica factible es determinada mediante la aplicación del algoritmo del método simplex,