algoritmo_del_metodo_simplex

PASO A PASO METODO SIMPLEX
Se desarolla el modelo matemático (PLANTEAMIENTO DEL PROBLEMA) mediante lo aprendido en PROGRAMACION LINEAL. (MODELACIÓN MEDIANTE PROGRAMACIÓN LINEAL), se determina si se maximiza o minimiza según el caso.
Identificación de las restricciones y formulación de las ecuaciones.
Plantear la variable de no negatividad.
Igualar la función objetivo a 0 con el fin deaumentar una o más variables.
Escribir la tabla inicial del método simplex guiado por el método de matrices es descomponer cada uno de los coeficientes formando asi una matriz o tabla. Esta tabla resulta por la igualación a cero de las diferentes variables (Al estar igualadas a ceros se facilita el desarrollo de las mismas).
condición de parada.
Elección de la variable entrante y saliente de labase.
Actualizar la tabla.
Se comprueba la condición de la parada.
Fin del algoritmo.
CONCEPTOS
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 sesatisfacen 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 seencuentra 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 lafunció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, siendo el más común el método de las Dos Fases.
Preparando el modelo para adaptarlo al método Simplex
La formaestándar del modelo de problema consta de una función objetivo sujeta a determinadas restricciones:
Función objetivo: c1·x1 + c2·x2 + ... + cn·xnSujeto a: a11·x1 + a12·x2 + ... + a1n·xn = b1a21·x1 + a22·x2 + ... + a2n·xn = b2...am1·x1 + am2·x2 + ... + amn·xn = bmx1,..., xn ≥ 0
El modelo debe cumplir las siguientes condiciones:
El objetivo consistirá en maximizar o minimizar el valor de la funciónobjetivo (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 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 poderaplicar 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...