Aplicar los métodos simplex dual de solución de problemas de programación lineal y el programa TORA



Oscar Alejandro Ortiz Martinez
INGENIERO INDUSTRIAL ADMINISTRADOR
Tema: 1.3, 1.4 (Realiza un resumen del tema)
Aplicar los métodos simplex dual de solución de problemas de programación lineal y el programa TORA.













INDICE

Introducción………..………………………………………….…………………..2
Desarrollo………………………………………………………………………….3-6
Conclusión…………………………………………………….……………………..7Referencias bibliográficas…………………………………………………….7
Soluciones de Problemas de PL por computadora TORA…….8
Referencias bibliográficas…………………………………………………….19



INTRODUCCIÓN
El método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la basede su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
Se aplica a problemas que tienen factibilidad dual inicial, es decir, que son óptimos pero infactibles simples. La factibilidad dual se reconoce expresando las restricciones en la forma canónica (£). La función objetivo puede ser de maximizacióno minimización.
El método simplex dual resulta ser una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.
Una aplicación típica del método simplex dual es en la resolución de problemas con unafunción objetiva de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.


DESARROLLO
El método dual simplex se aplica a problemas que tienen factibilidad dual inicial, es decir, que son óptimos pero infactibles simples. La factibilidad dual se reconoce expresando las restricciones en la forma canónica (£). La función objetivopuede ser de maximización o minimización. Condiciones:
Factibilidad
La variable de salida es la variable básica que tiene el valor más negativo, en caso de empate procedemos de forma arbitraria, y si todas las variables básicas son no negativas, el proceso finaliza y la solución factible óptima se encuentra.
Optimalidad
Paso 1: La variable de entrada es seleccionada de las variables nobásicas, se hacen cocientes cuyos denominadores serán necesariamente negativos y se toman dela ecuación pivote. Los numeradores serán los números correspondientes en la función objetivo.
Enseguida, en las ecuaciones que tengan variables de exceso (resultantes de restricciones de tipo >), se debe multiplicar por (-1) en ambos lados , para hacer positivo el coeficiente de la variable de exceso, y formarasí un vector unitario que nos permita tomar esta variable de exceso como una
Variable básica inicial. sin necesidad de agregar una variable artificial en esa restricción.
Al hacer lo anterior se logra que debajo de las variables básicas aparezca una matriz identidad, que es la que el simplex siempre toma como base inicial. Obtendremos que los términos del lado derecho de las ecuacionesmultiplicadas por (-1) quedan con signo negativo, lo cual hace que la solución inicial sea infactible.Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión de variables artificiales en el momento de transformar un modelo a formato estándar.El algoritmo para resolver un modelo de maximización es el siguiente:Paso 1: Hallar una solución básica inicial infactible e...