INSTITUTO TECNOLOGICO DE
TLALNEPANTLA
UNIDAD ORIENTE
RUEDA OSORIO ANDRÉS
NUMERO DE CONTROL:21253666
GRUPO: OV4
METODO SIMPLEX
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 (el
mayor o menor valor posible, según el caso, para el que se satisfacen todas las
restricciones).
Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento
consiste en buscar otro punto que mejore el valor anterior. Como se verá en el
método Gráfico, dichos puntos son los vértices del polígono (o poliedro o polícoro,
si el número de variables es mayor de 2) que constituye la región determinada por
las restricciones a las que se encuentra sujeto el problema (llamada región
factible). 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á que
estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el
algoritmo del Simplex. En caso de que después de este 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 el
método de las Dos Fases.
La forma estándar del modelo de problema consta de una función objetivo sujeta a
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. El objetivo consistirá en maximizar o minimizar el valor de la función
objetivo (por ejemplo, incrementar ganancias o reducir pérdidas,
respectivamente).
2. Todas las restricciones deben ser ecuaciones de igualdad (identidades
matemáticas).
3. Todas las variables (xi) deben tener valor positivo o nulo (condición de no
negatividad).
4. 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.
Tipo de optimización.
Como se ha comentado, el objetivo del método consistirá en optimizar el valor de
la función objetivo. 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 en cuanto al criterio de condición de parada para finalizar las
iteraciones y a las condiciones de entrada y salida de la base. Así:
• 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 la fila 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 de entrada 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.
No obstante, es posible normalizar el objetivo del problema con el fin de aplicar
siempre los mismos criterios en lo referente a la condición de parada del algoritmo
y a las condiciones de entrada y salida de las variables de la base. De esta forma,
si el objetivo es minimizar la solución, se puede cambiar el problema a otro
equivalente de maximización simplemente multiplicando la función objetivo por "-
1". Es decir, el problema de minimizar Z es equivalente al problema de maximizar
(-1)·Z. Una vez obtenida la solución será necesario multiplicarla también por (-1).
Ventajas: No hay que preocuparse por nuevos criterios de parada, condición de
entrada y salida de la base ya que se mantienen.
Inconvenientes: En el caso de que la función tenga todos los coeficientes de sus
variables básicas positivos, y además las restricciones sean del tipo de
desigualdad "≤", al hacer el cambio dichos coeficientes quedan negativos
cumpliéndose la condición de parada en la primera iteración (en la fila del valor de
la función objetivo todos los valores son positivos o cero). Obteniéndose en este
caso por defecto un valor óptimo para la función igual a 0.
Solución: Realmente no existe este problema dado que para que la solución sea
superior a 0 es necesario que alguna restricción tenga impuesta la condición "≥" (y
se trataría de un modelo para el método de las Dos Fases). En el caso planteado,
la solución real debe ser cero.
Cambio de signo de los términos independientes
También se ha dicho que los términos independientes (bi) de cada ecuación
deben ser no negativos para poder emplear el método Simplex. A tal fin, si alguna
de las restricciones presenta un término independiente menor que 0 habrá que
multiplicar por "-1" ambos lados de la inecuación (teniendo en cuenta que esta
operación también afecta al tipo de restricción).
Ventajas: Con esta simple modificación de signos en las restricciones
correspondientes se posibilita la aplicación del método Simplex al problema
modelado.
Inconvenientes: Puede resultar que en las restricciones donde tengamos que
modificar los signos de las constantes, los tipos de desigualdad fueran "≤"
(quedando tras la operación del tipo "≥") siendo necesario desarrollar el método de
las Dos Fases. Este inconveniente no es controlable, aunque podría ocurrir el caso
contrario y resultar beneficioso si los términos independientes negativos se
presentan en todas aquellas restricciones con desigualdad de tipo "≥". Si existe
alguna restricción del tipo "=" no supondría ninguna ventaja ni desventaja puesto
que siempre sería de necesaria aplicación el método de las Dos Fases.
Desarrollando el método Simplex
Una vez estandarizado el modelo puede ocurrir que sea necesario aplicar el
método Simplex o el método de las Dos Fases. Véase en la figura la forma de
actuación para llegar a la solución del problema modelado.
El método simplex es un procedimiento sistemático y eficiente para encontrar y
probar soluciones de problemas de programación lineal localizadas en los vértices
de optimidad. El método termina una vez que se haya encontrado la solución
óptima.