Metodo Simplex

METODO SIMPLEX
Un poco de .. HISTORIA
Estados Unidos al unirse a la Guerra Fria en 1942, comenzó a aplicar técnicas de
Investigación de Operaciones militarmente.
Unos años más tarde, en 1947, formó un grupo de trabajo dedicado a mejorar los
procesos de planificación a gran escala: el proyecto SCOOP (Scientific Computation Of
Optimum Programs).
En dicho grupo se encontraba trabajando GeorgeBernard Dantzig, quien desarrolló
en 1947 el algoritmo del método Simplex.

TEORIA
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la
función objetivo en cada paso. El proceso concluye cuando no es posible continuar
mejorando dicho valor, es decir, se ha alcanzado la solución óptima.
Partiendo del valor de la función objetivo en un punto cualquiera, el procedimientoconsiste en buscar otro punto que mejore el valor anterior. La búsqueda se realiza
mediante desplazamientos por las aristas del polígono, desde el vértice actual hasta
uno adyacente que mejore el valor de la función objetivo. Siempre que exista región
factible, como su número de vértices y de aristas es finito, será posible encontrar la
solución.
El método Simplex se basa en la siguiente propiedad:Si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe
una arista que parte de A y a lo largo de la cual el valor de Z aumenta.
Será necesario tener en cuenta que el método Simplex únicamente trabaja con
restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y
sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá queestandarizar las restricciones para que cumplan estos requisitos antes de iniciar el
algoritmo del Simplex.
En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o
igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos
de resolución.

ADAPTAR MODELO AL MÉTODO SIMPLEX
La forma estándar del modelo de problema consta de una función objetivo sujetaa
determinadas restricciones:

Función objetivo:

c1·x1 + c2·x2 + ... + cn·xn

Sujeto a:
a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0

El modelo debe cumplir las siguientes condiciones:
1.
2.
3.
4.

El objetivo consistirá en maximizar o minimizar el valor de la función objetivo
Todas las restricciones deben serecuaciones de igualdad (identidades
matemáticas).
Todas las variables (xi) deben tener valor positivo o nulo (condición de no
negatividad).
Los términos independientes (bi) de cada ecuación deben ser no negativos.

Hay que adaptar el problema modelado a la forma estándar para poder aplicar el
algoritmo del Simplex.
OPTIMIZACIÓN
El objetivo del método consistirá en optimizar el valor de la funciónobjetivo. Sin
embargo se presentan dos opciones: obtener el valor óptimo mayor (maximizar) u
obtener el valor óptimo menor (minimizar).
Además existen diferencias en el algoritmo entre el objetivo de maximización y el de
minimización.
Objetivo de maximización
•. Condición de parada: cuando en la fila Z no aparece ningún valor negativo.
•. Condición de entrada a la base: el menor valor negativo en lafila Z (o el de mayor
valor absoluto entre los negativos) indica la variable Pj que entra a la base.
•. Condición de salida de la base: una vez obtenida la variable entrante, la variable
que sale se determina mediante el menor cociente P0/Pj de los estrictamente
positivos.

Objetivo de minimización
•

Condición de parada: cuando en la fila Z no aparece ningún valor positivo.

•

Condición deentrada a la base: el mayor valor positivo en la fila Z indica la variable
Pj que entra a la base.

•

Condición de salida de la base: una vez obtenida la variable entrante, la variable
que sale se determina mediante el menor cociente P0/Pj de los estrictamente
negativos.

CAMBIO DE SIGNO DE LOS TÉRMINOS INDEPENDIENTES
También se ha dicho que los términos independientes (bi) de cada ecuación deben...