Metodo Dual m369

METODO DUAL Introducción Dado un problema de programación lineal, se llama problema primitivo y hay otro problema de programación lineal estrechamente relacionado con él, llamado problema dual. Se dice que estos dos temas son mutuamente dobles. Bajo ciertos supuestos, el problema original y el problema dual producirán el mismo valor óptimo de la función objetivo, por lo que el problema original puede resolverse indirectamente resolviendo el problema dual. Además, nos permite utilizar el método doble simplex para resolver problemas que la forma estándar no puede resolver. Además, puede facilitar otros cálculos, como el cálculo de variables artificiales.

Dualidad La dualidad se puede definir mediante la siguiente oración: "Para cada problema de maximización de programación lineal, habrá otro problema de minimización asociado, por otro lado, para cada problema de minimización, también habrá otro problema de maximización asociado. problema." El primer problema se denomina problema principal y el problema relacionado correspondiente se denomina problema doble. En esta sección, veremos cómo hacer preguntas dobles si hay algún problema importante.

La dualidad es importante por las siguientes razones • El problema dual puede ahorrar un número considerable de cálculos, en particular cuando el problema primario tiene muchas restricciones y pocas

variables, lo que implica un número elevado de cálculos para su resolución por el método simplex. • La dualidad tiene una relación importante con el análisis de sensibilidad que se verá más adelante en este mismo capítulo. Esto es muy útil para analizar cómo puede cambiar la función objetivo ante variaciones en las diferentes condiciones del problema de programación lineal. • El problema dual proporciona información importante sobre la manera óptima de aplicar recursos que son escasos con el fin de obtener beneficios económicos.

Importancia de la dualidad en programación lineal Considerando la dificultad del problema cuando el número de restricciones excede el número de variables, es razonable resolver el problema dual de los colores primarios. Además de los grandes problemas de aplicación en el análisis económico. Otra ventaja que aporta es que, asumiendo que las restricciones y el número de variables entre el problema dual y el problema original son opuestos, el problema con dos restricciones se puede resolver gráficamente, independientemente del número de variables.

El problema dual El planteamiento del problema dual para un problema primario cualquiera puede hacerse basado en los siguientes puntos: 1. Se invierte el sentido de la función objetivo. Si el problema primario es de maximización, el problema dual será de minimización y viceversa. 2. Se invierte el sentido de las desigualdades de las restricciones. Esto es, si las restricciones del problema primario son del tipo menor o igual que

(<=), en el problema dual las restricciones serán del tipo mayor o igual que (>=) y viceversa. 3. Los coeficientes de la función objetivo del problema primario pasan a ser las constantes de las restricciones del problema dual. Esto implica que el problema dual tendrá tantas restricciones como variables tenga el primario. 4. Las constantes de las restricciones del problema primario pasan a ser los coeficientes de la función objetivo del problema dual. Esto significa que el problema dual tendrá tantas variables como restricciones tenga el primario. 5. Los coeficientes de las restricciones del problema primario se colocan de tal forma que los renglones del primario pasarán a ser las columnas del problema dual y con este cambio las columnas del primario serán los renglones del dual. 6. Las variables del problema primario se denominarán X, mientras que las del problema dual serán Y, debiendo ser no negativas. Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma canónica de la siguiente forma: Maximizar Sujeto a:

Relaciones entre problemas primales y duales 1. El número de variables planteadas por el problema dual está determinado por el número restringido planteado por el problema original. 2. El número limitado de preguntas duales planteadas está determinado por el número de variables planteadas en la pregunta original. 3. El coeficiente de la función objetivo en el problema dual corresponde al término independiente de la restricción (RHS), y el término de la restricción está en el otro lado de la variable. 4. El término independiente (RHS) de la restricción en el problema dual corresponde al coeficiente de la función objetivo en el problema original. 5. Determine la matriz de coeficientes técnicos para cada variable en cada restricción correspondiente a la transposición de la matriz de coeficientes técnicos del problema original. El sentido de las igualdades y desigualdades se comporta según la tabla de Tucker, presentada a continuación.

Ejercicio de aplicación Sea el siguiente modelo:

Expresar el modelo en formato estándar

Multiplicar por (-1) en ambos lados de las ecuaciones, para formar los vectores unitarios, requeridos para contar con una base inicial unitaria.

Tomando las variables básicas iniciales hacemos lo siguiente:

Paso 2 Sale E2 = (XB)2 o sea s = 2

Paso 3 Calculando los cocientes para todo (Sj)2 < 0 obtenemos:

Es decir que X3 es la variable de entrada (entonces e = 3) y el elemento pivote es el (Se)s = (S3)2 = -9

Efectuando el pivoteo obtenemos la tabla siguiente: Tabla 1 (maximizar)

Repitiendo el algoritmo desde el paso 1, obtenemos: Sale E1 = (XB)1 y entra X2 por lo cual obtenemos la siguiente tabla Tabla 2

Como se observa, ahora estamos en el óptimo. En definitiva: X2* = 11/7 X3* = 13/7 Z* = – 61/7

Conclusión A través de esta investigación, puedo entender que cada problema de programación lineal tiene un problema de programación lineal doble. Existen algunas relaciones útiles entre el problema original (principal) y su problema dual, que pueden mejorar la capacidad de analizar el problema original. Por ejemplo, la explicación económica del problema dual proporciona precios sombra, que pueden medir el valor marginal de los recursos en el problema original, y una explicación del método simplex. Dado que el método simplex se puede aplicar directamente a cualquiera de los dos problemas para obtener la solución de los dos problemas al mismo tiempo, si se trata directamente el problema dual, se puede ahorrar una gran cantidad de trabajo computacional.

Bibliografías López, B. S. (2019, 28 octubre). Dualidad en programación lineal. Ingenieria Industrial

Online.

https://www.ingenieriaindustrialonline.com/investigacion-de-

operaciones/dualidad-en-programacion-lineal/ El problema dual y el método dual simplex. (2012, 21 junio). Optimus. https://inveoperaciones.wordpress.com/el-problema-dual-y-el-metodo-dualsimplex/ Landeta, J. M. I. & TRILLAS, EDITORIAL. (2014). Investigacion De Operaciones (2.a ed.). Trillas.