Unidad 3

UNIDAD 3: METODO SIMPLEX

3.1  SOLUCION GRAFICA

3.2  SOLUCION TABULAR

3.3  VARIABLES DE HOLGURA Y ARTIFICIAL

EL METODO SIMPLEX: Transición del método grafico al método Simplex

Como ya vimos el método gráfico indica que la solución óptima, de un programa lineal, siempre está asociada a un punto esquina del espacio de soluciones factibles. Este resultado es la clave del Método Simplex algebraico, y en general para resolver cualquier modelo de programación lineal.

La transición de la solución del punto esquina geométrico, hasta el método simplex, implica un procedimiento de computo que determina en forma algebraica los puntos esquinas. Esto se logra convirtiendo primero a todas las restricciones del modelo, de desigualdades a ecuaciones (el modelo en forma estándar), para luego manipular esas ecuaciones en forma sistemática.

Una propiedad general del método Simplex es que resuelve la programación lineal en iteraciones. Cada iteración desplaza la solución a un nuevo punto esquina,  que tiene potencial de mejorar el valor de la función objetivo. El proceso termina cuando ya no se pueden tener mejoras. El método simplex implica cálculos voluminosos y tediosos, lo que hace que la computadora sea una herramienta esencial para resolver los problemas de programación lineal. Por consiguiente las reglas computacionales del método simplex se adaptan para facilitar el cálculo.

Transición de la solución gráfica a la solución algebraica.

Las ideas contenidas en la solución gráfica, de un modelo de programación lineal, son la base para desarrollar el método algebraico simplex. El siguiente esquema muestra el paralelismo entre los dos métodos.

Método Gráfico

1.       .   Se gráfica todas las restricciones, incluyendo las de no negatividad.
2.          El espacio de soluciones consiste en una infinidad de puntos factibles.
3.          Identifica puntos factibles de esquina del espacio de soluciones.
4.          Los candidatos a la solución óptima corresponden a una cantidad finita de puntos de esquina.
5.      Se usa la función objetivo para determinar el punto esquina óptimo entre todos los candidatos.

     Método Algebraico

1.       Se representa el espacio de soluciones con m ecuación y  n variables, y restringe a todas las variables a valores no negativos; m≤n. (forma estándar del modelo)
2.             El sistema tiene infinidad de soluciones factibles.
3.       .      Determina las soluciones básicas factibles de las ecuaciones.
4.        Los candidatos a solución óptima corresponden a una cantidad finita de soluciones básicas factibles.
5.        Se usa la función objetivo para determinar la solución básica factible óptima, entre todas las candidatas. 

En el método gráfico, el espacio de soluciones se delimita con los ¨semis-espacios¨  que representan las restricciones y en el método simplex, el espacio de soluciones se representa con m ecuaciones lineales simultaneas y n variables no negativas.

En la representación algebraica, la cantidad m de ecuaciones  siempre es menor, o igual a la cantidad de variables n.

Si m = n y las ecuaciones son consistentes, el sistema solo tiene una solución (Solución Única); pero si m<n (esto representa la mayor parte de los programas lineales), entonces el sistema de ecuaciones producirá una infinidad de soluciones.

El Método Simplex: Calculo del Algoritmo Simplex.

Como ya dijimos, el método simplex usa un procedimiento inteligente de búsqueda, diseñado para llegar al punto esquina óptimo en forma eficiente. El algoritmo simplex aumenta el valor de las variables una por una, hasta llegar al punto óptimo.  El método Simplex proporciona una regla definida, para determinar que variable aumentar, esto para facilitar el desarrollo de un programa de computo.

En forma específica como se está maximizando, la variable no básica que tenga el coeficiente positivo más grande, en la función objetivo, es la que se selecciona para aumentar primero.

Téngase en cuenta que solo se trata de una regla fácil que, de acuerdo con la experiencia, generalmente conduce a la menor cantidad de iteraciones. En la terminología del método Simplex X₁ y S₁ en el punto A se llama variable de entrada y de salida respectivamente.

Detalles de cálculo del algoritmo Simplex.

Los detalles de cálculo de una iteración Simplex, que incluye las reglas para determinar las variables de entrada y de salida, así como para determinar los cálculos cuando se llega a la solución óptima, los veremos utilizando el modelo de Comex, ya conocido.

Resumen del Método Simplex:

 Hasta ahora nos hemos ocupado en maximización. El problema de minimización, la condición de Optimalidad requiere seleccionar la variable de entrada, como la variable no básica, con el coeficiente objetivo, más positivo en la ecuación objetivo (renglón Z), la regla es aptamente opuesta al caso de maximización. En cuanto a la condición de factibilidad para seleccionar la variable de salida la regla no cambia.

Condición de Optimalidad.

La variable  de entrada en un problema de maximización (o minimización), es la variable no básica con el coeficiente más negativo (positivo), en el renglón Z los vínculos se rompen arbitrariamente. El óptimo se alcanza en la iteración en la cual los coeficientes, en el renglón Z son no negativos (o no positivos).

Condición de Factibilidad:

Tanto en problema de maximización y minimización la variable de salida, es la variable básica, asociada con la razón mínima no negativa con el denominador estrictamente positivo. Los vínculos se rompen arbitrariamente  (dos razones mínimas iguales).

Los pasos del Método Simplex son:

1.      Determine la solución factible básica inicial.

2.      Seleccione una variable de entrada, utilizando la condición de Optimalidad. Deténgase si no hay variable de entrada. La última condición es óptima. De otro modo prosiga con el paso 3.

3.      Seleccione una variable de salida utilizando una condición de factibilidad.

4.      Aplique los pasos de Gauss – Jordan, para determinar la solución básica  y vaya al paso 2

METODO M: Solución Artificial de Inicio.

Como puede observarse el Método Simplex lo hemos utilizado en un modelo de programación lineal donde todas las restricciones son de la forma ≤, con el lado derecho no negativo. Esto ofrece una cómoda solución básica factible de inicio con todas las holguras. Los modelos donde hay restricciones del tipo ≥ o = no ofrece esta solución básica de inicio. A estos modelos se les llama programas lineales de mal comportamiento.

El procedimiento para iniciar la resolución de estos programas lineales (con restricciones ≥ e =) permite que variables artificiales desempeñen el trabajo de holguras, en la primera iteración, para después en alguna iteración posterior, desecharla de forma legítima. Para ello se puede hacer uso de dos métodos muy relacionados entre sí, el método M y el método de dos fases.

El Método M o Método de Penalización:

Comienza con la programación lineal en forma de ecuación (forma estándar).

Una ecuación i, que no tenga una holgura positiva, se aumenta con una variable artificial R_i, para formar una solución de inicio parecida  a la solución básica con todas las holguras. Sin embargo como las variables artificiales son ajenas al modelo de programación lineal, se usa un mecanismo de retroalimentación en el que el proceso de optimización trata de forma automática de hacer que esas variables tengan nivel cero.

Esto significa que al final, la solución será como si las variables artificiales nunca hubiesen existido. El resultado deseado, se obtiene penalizando las variables artificiales en la función objetivo.

Acerca del método M se puede hacer dos observaciones:

• El uso de la penalización M podrá no forzar la variable artificial hasta el nivel cero en la iteración Simplex  final, si el problema de programación lineal no tiene una solución factible (es decir, si las restricciones no son consistentes). En este caso, la iteración simplex final incluirá cuando menos una variable artificial a un nivel positivo

  

•     La aplicación de la técnica M implica, teóricamente, que M  → ∞. Sin embargo, al usar la computadora M debe ser finito pero suficientemente grande. ¿Qué tan grande es ¨suficientemente grande¨? Es una pregunta abierta.

En forma específica, M debe ser lo bastante grande como para funcionar como penalización. Al mismo tiempo no debe ser tan grande como para perjudicar  la exactitud de los cálculos simplex, al manipular una mezcla de números muy grandes o muy pequeños. 

1.