Presentación

Ponentes:

JEIMY SALON
JASAY GUTIERREZ
ILLARYIS OLIVERO
HENNESSY SUAREZ
ELIZABETH ABUCHAIBE
WILFREDO CASTAÑEDA

CIENCIAS ECONOMICAS Y ADMINISTRATIVAS

ADMINISTRACIÓN DE EMPRESA

VI SEMESTRE 

UNIVERSIDAD DE LA GUAJIRA
EXTENSION MAICAO

Preliminar

TEORÍA DE LA DUALIDAD

Durante el desarrollo inicial de la programación lineal se descubrió el concepto de dualidad , esto reveló que asociado a todo problema de programación lineal existe otro problema lineal llamado dual. Por esto cada vez que se plantea y resuelve un problema existe otro problema connatural planteado, y que puede ser resuelto, el cual tiene unas importantes relaciones y propiedades respecto al problema primal que pueden ser de gran beneficio para la toma de decisiones. Los problemas primales y duales se encuentran ligados por una serie de relaciones, saber la existencia de estas puede ser considerado de gran utilidad para la resolución de problemas que parecen no factibles, o que no pueden ser resueltos mediante un método en particular.

IMPORTANCIA DE LA DUALIDAD EN PROGRAMACIÓN LINEAL

La resolución de los problemas duales tiene gran aplicación en el análisis económico del problema.

Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

Maximización en el Método Dual Simplex

UTILIDAD DEL 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 dualidad en la formulación de problemas de  programación lineal no debe tomada únicamente como un ejercicio matemático, sino que se debe apreciar ambas versiones del problema ya que estas entran a explicar dos condiciones económicas distintas para un mismo problema.

VENTAJAS DEL MÉTODO DUAL SIMPLEX

Permite resolver problemas de programación lineal de forma más rápida y sencilla. 

     Es otra vía para resolver un problema de programación lineal.

     Facilita profundizar en el contenido económico del problema original (primal).

     Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener que resolver completamente el problema.

Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables. 

El método de solución para los problemas de maximización es el denominado Método Dual-Simplex y se aplica por medio de reglas de equivalencia Min. (z) = Max. (- z).  En la maximización mediante el método Dual Simplex, se requiere que la función objetivo del dual se exprese en forma de maximización, max(z).

Método Dual-Simplex  empieza con una solución óptima o mejor que óptima, pero no factible y se mueve hacia el óptimo mediante iteraciones que mejoran su factibilidad conservando su optimalidad.

PASOS PARA LA TRANSFORMACIÓN DEL PROBLEMA DUAL A PARTIR DEL PROBLEMA PRIMAL

1.  Cuando las restricciones no cumplen con el criterio ≤ es necesario aplicar el formato canónico.

2.  Se pasa al dual cuando cumple con el criterio que estén todos ≤ Primero minimizamos y la solución de las restricciones pasan a ser los coeficientes de la función objetivo.

3. Las nuevas restricciones se construyen de las columnas verticales de las mismas, pasando hacer mayor igual y la solución son los coeficientes de la anterior función objetivo.

4.  Después se convierte al formato estándar.

Generalidades del problema dual

RELACIONES ENTRE PROBLEMAS PRIMALES Y DUALES  

• El número de variables que presenta el problema dual es igual al número de restricciones que presenta el problema primal.

• El número de restricciones que presenta el problema dual es igual al número de variables que presenta el problema primal.

• El dual del dual, tiene como resultado el problema primal. 

• Una restricción expresada como una igualdad en el problema primal, genera una variable no restringida (sin restricción de signo) en el problema dual. 

• Una variable no restringida (sin restricción de signo) del problema primal, genera una restricción de igualdad en problema dual.  

Los 2 poseen propiedades muy relacionadas, de tal manera que la solución óptima a un problema proporciona información completa sobre la solución óptima para el otro.

Categoría de 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.

Categoría de Optimalidad

La variable de entrada es seleccionada de las variables no básicas, se hacen cocientes cuyos denominadores serán necesariamente negativos y se toman de la ecuación pivote. Los numeradores serán los números correspondientes en la función objetivo.

TABLA DE TUCKER

Los problemas  duales simétricos  son los que se obtienen de un problema primal en forma canónica y ‘normalizada’, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades menores o igual para los problemas de maximización.  

 

Ejemplos y Ejercicios

SUMARIO

De acuerdo a la anterior información cabe resaltar que cuando se tiene un caso de maximización en el método Dual-Simplex, todo el procedimiento es exactamente igual que si fuera de minimización, excepto que al definir la variable de entrada se hacen cocientes cuyos denominadores serán necesariamente negativos tomados de la ecuación base y los numeradores serán los números correspondientes en la función objetivo.Se toman los valores absolutos de los cocientes (prescindiendo de los signos) y se elige, para determinar la variable de entrada, el cociente más próximo a cero.