Solución utilizando el Programa QSB.- I

Este programa usa el Método Simplex con la variación BIG M o Método de la M Grande, que determina primero si hay solución posible, al calcular y obtener las variables artificiales con valor final cero. Si obtiene valores cero para esas variables, continúa a partir de allí buscando la solución óptima, que ya ha determinado que existe. Se ilustran las tablas para que compare el formato de salida de datos. 

METODO de la M GRANDE

Solución con el Método Simplex Regular

Esta solución no puede ser mejorada. Cada unidad de Producto Dos que se elabore en una nueva solución desmejora o disminuye los beneficios en 2 unidades. Cada unidad en que se incremente la cantidad de materia prima que quede disponible disminuirá los beneficios totales en 6 unidades. 

Las variables artificiales una vez que salen de la base no entran más. En cada tabla la solución del modelo se lee en la forma siguiente: Cada variable que se encuentra en la BASE se iguala al valor que se lee en el vector bi. Las variables que no están en la base (las nobásicas) tienen valor cero.

Práctica. Solución de Modelos con el Método Simplex.

El siguiente modelo, de dos variables, se usa como ejemplo para ilustrar el proceso de solución con el Método Simplex.

La solución matemática que se lee en los diferentes formatos de salida de datos presentados, es la siguiente:

La solución del modelo se ilustra a continuación, en las próximas cuatro páginas: 

1) Utilizando el método simplex y resolviendo manualmente, con indicación de los cálculos realizados. Todas las iteraciones necesarias para obtener la solución óptima se muestran en Tablas Simplex 

2) Utilizando el programa de computadora QSB que utiliza la variación del método simplex llamado M Grande (Big M) 

3) El modelo también se soluciona en computadora con el método Gráfico del programa QSB. Esto permite mostrar los puntos extremos de solución por los que se mueve el algoritmo Simplex y compararlos en cada iteración, o solución de punto extremo, hasta llegar al punto extremo óptimo. 

4) A fin de ilustrar los resultados, en otro formato de salida de datos, también se soluciona el modelo usando el programa LINDO en computadora.

SECCION C. Solución de Modelos Lineales con el Método SIMPLEX y el Método de Puntos Interiores. - IV

30. El Método de Karmakar también es un algoritmo iterativo, como el Simplex, pero parte de una solución de prueba, obtenida DENTRO de la región de soluciones posibles. En cada iteración se mueve dentro de la región solución a una mejor solución de prueba y así continúa hasta obtener la mejor solución en un punto extremo. La principal diferencia con el Algoritmo Simplex es que trabaja con puntos interiores de la región solución y por eso se le llama también ALGORITMO DE PUNTOS INTERIORES. 

 31. La empresa Delta Airlines con 7000 pilotos que deben manejar 400 aviones y movilizarlos a 166 ciudades en el mundo, ha preferido las ventajas de este algoritmo para usar eficientemente los recursos escasos. 

32. Programas de computadora para la solución de modelos lineales son distribuidos comercialmente. Por lo tanto, la principal atención debe darse a la definición del problema y a la determinación y elaboración del modelo a usar. Todo ello con el fin de poder aplicar la técnica e interpretar resultados para tomar decisiones.

SECCION C. Solución de Modelos Lineales con el Método SIMPLEX y el Método de Puntos Interiores. - III

20. Para determinar cuál variable básica debe salir de una solución, para pasar a ser variable nobásica, se utiliza como criterio el seleccionar a la variable básica que se hace cero al introducir 26 la nueva variable básica. La medida utilizada para aplicar este criterio es el llamado Ratio Mínimo de la variable. Además de indicar la variable que se hace cero, el Ratio Mínimo informa cuál será el valor de la variable entrante en la nueva solución. 

21. Para calcular una nueva solución posible efectúa operaciones matemáticas que transforman el sistema actual de ecuaciones, en un sistema de ecuaciones equivalente. Este es un proceso iterativo. En cada iteración intercambia una variable básica por una no-básica. Los Coeficientes Relativos y los Ratios Mínimos tiene fórmulas matemáticas para calcularlos. 

22. En cada iteración intercambia una variable básica por una no-básica. En cada solución los Coeficientes Relativos informan si se ha llegado o no al óptimo. Coeficientes Relativos y los Ratios Mínimos tiene fórmulas matemáticas para calcularlos. 

23. En las Tablas Simplex se reconoce que hay una solución óptima ÚNICA cuando los coeficientes relativos de variables no-básica tienen valor > que cero en minimización y < que cero en maximización. Esto indicaría que ninguna de esas variables IGUALARÍA el valor óptimo encontrado y por lo tanto, es única. 24. Se reconoce que hay una solución óptima ALTERNA cuando por lo menos uno de los coeficientes relativos de variables no-básica tiene valor igual a cero Esto indicaría que esa variables IGUALARIA el valor óptimo encontrado y por lo tanto, es alterna. 

25. Se reconoce que hay una solución óptima con valor INFINITO cuando por lo menos uno de los coeficientes relativos de variables no-básica tiene un valor que indique que la solución actual puede ser mejorada. Pero al calcular el Ratio Mínimo, éste indica que esa variable puede crecer indefinidamente y por lo tanto también el valor del objetivo. 

26. Se reconoce que hay una solución óptima IMPOSIBLE cuando todos los coeficientes relativos indican que la solución es óptima pero, por lo menos, una variable artificial permanece en la solución con valor mayor que cero. 

27. Se reconoce que hay una solución óptima DEGENERADA cuando por el número de variable básicas con valor mayor que cero es menor que el número de restricciones en el modelo. 28. El Método Simplex estudiado es el Regular, existen variaciones como el Simplex Revisado y numerosos refinamientos que se le han hecho en aplicaciones para computadora. 

29. En 1984, el matemático Narendra Karmakar creó un nuevo algoritmo para solucionar modelos lineales. Este algoritmo permite manejar cantidades enormes de variables y restricciones. AT&T desarrolló su implementación en computadora en 1988 y ha presentado versiones posteriores. IBM agregó variantes al algoritmo en 1990. Mientras tanto, se han elaborado miles de trabajos dirigidos a desarrollar variantes mejoradas del algoritmo.

SECCION C. Solución de Modelos Lineales con el Método SIMPLEX y el Método de Puntos Interiores. - II

11. Una variable artificial debe tener incorporado un coeficiente muy alto en la Función Objetivo, con signo negativo en maximización y con signo positivo en minimización. Con esto se logra que el procedimiento Simplex las elimine de la solución en las primeras iteraciones. Estas variables deben valer cero en la solución óptima del modelo.

12. Una Tabla Simplex es un resumen detallado de toda la información del modelo para trabajar más fácilmente con él. 

13. En las Tablas Simplex, el espacio Cx se utiliza para copiar los coeficientes de todas las variables en la Función Objetivo. En fila porque ellos conforman un vector fila. Debajo de cada coeficiente se escribe el símbolo correspondiente a la variable de ese coeficiente. En el espacio CB, se copian los coeficientes de las variables correspondientes a las variables que son básicas en cada restricción. En el espacio BASE se copian las variables que son básicas en cada restricción. Tanto los coeficientes como las variables están colocadas en el correspondiente nivel de la restricción en la que se usan como básicas. Debajo del símbolo de cada variable se escriben los vectores de esas variables en el modelo. Ellos conforman la matriz de coeficientes. En el espacio bi se copian los lados derechos de las restricciones conformando un vector columna, cada solución posible del modelo se leerá en este espacio. 

14. El Modelo Lineal en su forma estándar general puede ser escrito en notación matriz- vectores, como:

Donde A es una matriz (mxn); x es un vector columna (nx1); b es vector columna (mx1) y c es un vector fila (1x n). El número de variables es n y el número de restricciones es m. 

15. El Método Simplex funciona, en forma general, de la siguiente forma: Calcula una solución posible inicial y determina sí esa solución es óptima. Si no lo es, se mueve a un punto extremo adyacente, en el conjunto convexo de soluciones posibles, y calcula la nueva solución en ese punto. De nuevo determina si esa solución es o no óptima; si no lo es, repite el proceso anterior. Así continúa sucesivamente hasta encontrar un punto extremo cuyo valor objetivo no pueda ser mejorado y allí concluye, determinando así que ha encontrado la solución óptima. 

16. Para calcular la solución posible inicial le otorga valor cero a las variables que no son básicas y resuelve para las otras variables básicas. Cada solución posible satisface todas las restricciones. 

17. Para determinar si la solución inicial es óptima, calcula los llamados coeficientes relativos de las variables. Estos valores informan en cuanto variaría el objetivo por cada unidad en que se incremente el valor de la variable a la que se refiere ese coeficiente relativo. 

18. Si la solución no es óptima, al moverse a otro punto extremo adyacente en el conjunto convexo, el Método Simplex efectúa un intercambio de una variable básica por una no-básica. 

19. Para determinar cual variable no-básica debe entrar a formar parte de una nueva solución, como variable básica, se utiliza como criterio el seleccionar la variable que mejore en mayor cantidad el objetivo. La medida utilizada para aplicar este criterio son los llamados Coeficientes Relativos de las variables.

SECCION C. Solución de Modelos Lineales con el Método SIMPLEX y el Método de Puntos Interiores. - I

Esbozo de conceptos y aspectos relevantes de la teoría de la solución de Modelos de Programación Lineal 

1. El Método Simplex es un procedimiento de cálculo algebráico, iterativo, para resolver Modelos Lineales de cualquier tamaño. 

2. El algoritmo Simplex requiere que el Modelo Lineal, para ser solucionado, cumpla las condiciones de Forma Estándar y Sistema Canónico. 

3. La Forma Estándar incluye: a) una Función Objetivo a optimizar, b) lado derecho de las restricciones con valor positivo, c) variables de decisión no negativas y d) las restricciones deben ser expresadas como igualdades. 

4. Para transformar las restricciones en igualdades se deben incorporar las llamadas variables de holgura. 

5. Una variable de holgura tiene coeficiente cero en la Función Objetivo. Se suman en restricciones del Tipo £ y se restan en restricciones del Tipo ³. En términos matemáticos, expresan la diferencia entre el lado izquierdo y el lado derecho de las restricciones. Al igual que las variables de decisión deben ser mayores o iguales a cero. 

6. En términos del modelo representan la cantidad de recurso no utilizado con relación a un máximo disponible, o utilizado por encima de un mínimo disponible. Esto es así cuando la restricción es de un recurso disponible. 

7. Cuando la restricción es de una condición o requerimiento, representan la cantidad de esa condición o requerimiento que se obtiene por encima de un mínimo o que se deja de tener con relación a un máximo. 

8. El Sistema Canónico en un Modelo Lineal significa que debe existir una variable básica en cada restricción. Esto permite obtener una primera solución posible que satisface todas las restricciones. 

9. Una variable básica tiene coeficiente 1 positivo en una restricción y no existe en las demás. 

10. Las variables de decisión (estructurales) del modelo y las variables de holgura pueden ser variables básicas. Cuando ninguna de ellas cumple con la condición de ser básica, se incorpora una variable como artificio matemático, para cumplir con el sistema canónico y a esa variable se le llama variable artificial.