Metodo 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 los coeficientes 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 forma permite encontrar la solución factible básica inicial haciendo Xsi = bj

 

El método Simplex es un algoritmo interativo que permite mejorar la solución con cada paso sucesivo. El algoritmo termina cuando no se puede seguir

mejorando más la solución. Se parte de una solución básica inicial para la función objetivo en un vértice cualquiera, el método consiste en buscar

sucesivamente otro vértice que mejore la anterior solución. La búsqueda se hace siempre a través de los lados del polígono de soluciones factibles o de las aristas de la región solución, si el número de variables es mayor. Cómo el número de vértices y de lados o 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 Z, no toma su valor máximo en el vértice A, entonces hay una arista o lado que parte de A, a lo largo de la cual Z aumenta.

 

FORMA ESTANDAR DEL MODELO:

1.- Todas las restricciones son ecuaciones con los lados derechos no negativos, en el caso del primal. Las restricciones del tipo ≤ o ≥ se convierten en ecuaciones sumando una variable de holgura (caso ≤) o restando una variable de exceso (caso ≥) en el lado izquierdo de la restricción.

 

2.- Todas las variables son no negativas, si una variable es irrestricta se usa la sustitución Yi = Y ́i – Y ́ ́i. Una variable negativa se hace no negativa  multiplicando por -1 a la variable en la función objetivo y las restricciones.

 

3.- La función objetivo es de maximización o minimización.

 

 

SOLUCIÓN BÁSICA:

Una solución básica es aquella que es factible o se encuentra en uno de los vértices de la región solución. Con m ecuaciones y n variables una

solución básica se determina haciendo n-m variables iguales a cero. En general existen n!/ [m!(n-m)!] soluciones básicas posibles.

 

VARIABLES NO BÁSICAS:

Son las n -m variables que hemos hecho igual a cero.

 

VARIABLES BÁSICAS:

Son m variables restantes diferentes de cero. La solución básica será factible si todos los valores de las variables básicas son no negativos. Si alguna de las variables es negativa entonces la solución será infactible.

 

CONDICIONES PARA QUE UNA VARIABLE SEA BÁSICA O NO BÁSICA:

 

CONDICIÓN DE OPTIMIDAD:

La variable que entra o pasa a ser básica es aquella no básica con el coeficiente más negativo si el problema es de maximización, o más positivo si es

de minimización. Si todos los coeficientes de las variables no básicas en Z son no negativos, la solución es óptima en maximización y si son no positivos entonces la solución es óptima en minimización. Otro método utiliza para evaluación la fila (Cj – Zj) y elige para entrar la variable que de el mayor  mejoramiento por unidad a la función objetivo.

 

CONDICIÓN DE FACTIBILIDAD:

La variable que sale es la variable básica, con la menor razón(denominador positivo) en la dirección de la variable que entra.

Tanto en la condición de optimidad como de factibilidad, los empates se rompen de forma arbitraria.

OPERACIONES NECESARIAS

La fila de la variable que sale es la ecuación pivote.

●Nueva ecuación pivote: = ecuación pivote / elemento pivote

 

●Las demás ecuaciones incluyendo Z: (ecuación anterior) – [coeficiente de la columna de la variable que entra]x(nueva ecuación pivote)

 

Si todas las restricciones no son del tipo ≤, es decir hay restricciones de = y ≥, entonces no es posible obtener una solución básica inicial con las variables de holgura, en este caso se utilizan otras variables llamadas variables artificiales (Rm) que se agregan a las restricciones que son del tipo ≥o de = con coeficiente

1, en la función objetivo se penalizan agregándolas con coeficiente muy alto si es minimización o muy bajo si es maximización (una M o -M). Las iteraciones se hacen igual que el simplex normal y las condiciones de optimidad y factibilidad son las mismas. Si en la solución óptima hay variables artificiales, se dice que el modelo es infactible.

 

Otra técnica se denomina de Dos Fases:

 

Fase I:

Minimizar las variables artificiales sujetas a las restricciones originales. Si el valor mínimo es cero el problema tiene solución y se pasa a la fase II. Si el

valor mínimo es positivo el modelo es infactible.

 

Fase II:

Se utiliza la solución básica óptima de la fase I como solución inicial para el problema original.

 

CASO ESPECIALES DEL MÉTODO SIMPLEX:

 

SOLUCIÓN DEGENERADA:

Si se presenta un empate en la variable que sale de forma repetida, una variable básica tomará valor cero, esto hace que la solución sea degenerada. Lo anterior es debido a la existencia de a lo menos una restricción redundante.