METODO SIMPLEX

UNIVERSIDAD DE LAS FUERZAS ARMADAS
ESPE-L
INVESTIGACION OPERATIVA
NOMBRE: Irma Elizabeth Chango.
CURSO: 4to “A “
FECHA: 8 de Diciembre del 2015.

METODO SIMPLEX
Según (Becerra, 2002), en su libro titulado Investigación de Operaciones, Programación lineal aplicada a Economía, Administración e Ingeniería.
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la funciónobjetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).
Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) ysus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar 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, siendo el más común elmétodo de las Dos Fases.

El modelo debe cumplir las siguientes condiciones:
El objetivo consistirá en maximizar o minimizar el valor de la función objetivo (por ejemplo, incrementar ganancias o reducir pérdidas, respectivamente).
Todas las restricciones deben ser ecuaciones de igualdad (identidades matemáticas).
Todas las variables (xi) deben tener valor positivo o nulo (condición de nonegatividad).
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.

Normalización de las restricciones

Otra de las condiciones del modelo estándar del problema es que todas las restricciones sean ecuaciones de igualdad (también llamadas restricciones de igualdad), por lo que hay queconvertir las restricciones de desigualdad o inecuaciones en dichas identidades matemáticas.
La condición de no negatividad de las variables (x1,..., xn ≥ 0) es la única excepción y se mantiene tal cual.
Restricción de tipo "≤"
Para normalizar una restricción con una desigualdad del tipo "≤", hay que añadir una nueva variable, llamada variable de holgura xs (con la condición de no negatividad: xs ≥0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y sumando en la ecuación correspondiente (que ahora sí será una identidad matemática o ecuación de igualdad).
a11·x1 + a12·x2 ≤ b1 a11·x1 + a12·x2 + 1·xs = b1
Restricción de tipo "≥"
En caso de una desigualdad del tipo "≥", también hay que añadir una nueva variable llamada variable de exceso xs (con la condición de nonegatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y restando en la ecuación correspondiente.
Surge ahora un problema con la condición de no negatividad con esta nueva variable del problema. Las inecuaciones que contengan una desigualdad de tipo "≥" quedarían:
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs = b1
Al realizar la primera iteración con el métodoSimplex, las variables básicas no estarán en la base y tomarán valor cero. En este caso la nueva variable xs, tras hacer cero a x1 y x2, tomará el valor -b1 y no cumpliría la condición de no negatividad. Es necesario añadir otra nueva variable xr, llamada variable artificial, que también aparecerá con coeficiente cero en la función objetivo y sumando en la restricción correspondiente. Quedandoentonces de la siguiente manera:
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs + 1·xr = b1

Restricción de tipo "="
Al contrario de lo que cabría pensar, para las restricciones de tipo "=" (aunque ya son identidades) también es necesario agregar variables artificiales xr. Como en el caso anterior, su coeficiente será cero en la función objetivo y aparecerá sumando en la restricción correspondiente....