Informatica

MÉTODO SIMPLEX
El algoritmo símplex fue descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica para dar soluciones numéricas a problema de programación lineal. Un problema en su forma estándar se puede representar como:
X, Xs ≥ 0.
Donde X son las variables de decisión de la forma estándar, Xs son las variables de holgura o de exceso, c contiene loscoeficientes de la función objetivo y Z es la variable a ser maximizada o minimizada.
El sistema es no determinado, debido a que el número de variables excede el número de ecuaciones. La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados con el problema.
Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. Esta formapermite encontrar la solución factible básica inicial haciendo Xsi = bj.
El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior.La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largode la cual f aumenta.
Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común elmétodo de las Dos Fases.

PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX
Esta es la forma estándar del modelo:
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
Para ello se deben cumplir las siguientes condiciones:
1. El objetivo es de la forma demaximización o de minimización.
2. Todas las restricciones son de igualdad.
3. Todas las variables son no negativas.
4. Las constantes a la derecha de las restricciones son no negativas.
5.
Cambio del tipo de optimización.
Si en nuestro modelo, deseamos minimizar, podemos dejarlo tal y como está, pero deberemos tener en cuenta nuevos criterios para la condición de parada (deberemos parar derealizar iteraciones cuando en la fila del valor de la función objetivo sean todos menores o iguales a 0), así como para la condición de salida de la fila. Con objeto de no cambiar criterios, se puede convertir el objetivo de minimizar la función F por el de maximizar F• (-1).
Ventajas: No deberemos preocuparnos por los criterios de parada, o condición de salida de filas, ya que se mantienen.Inconvenientes: En el caso de que la función tenga todas sus variables básicas positivas, y además las restricciones sean de desigualdad "≤", al hacer el cambio se quedan negativas y en la fila del valor de la función objetivo se quedan positivos, por lo que se cumple la condición de parada, y por defecto el valor óptimo que se obtendría es 0.
Solución: En la realidad no existen este tipo de problemas,ya que para que la solución quedara por encima de 0, alguna restricción debería tener la condición "≥", y entonces entraríamos en un modelo para el método de las Dos Fases.

Conversión de signo de los términos independientes (las constantes a la derecha de las restricciones)
Deberemos preparar nuestro modelo de forma que los términos independientes de las restricciones sean mayores o...