UNIVERSIDAD NACIONAL “JOSÉ FAUSTINO SÁNCHEZ CARRIÓN”

FACULTAD DE INGENIERÍA QUÍMICA METALÚRGICA ESCUELA

PROFESIONAL DE INGENIERÍA QUÍMICA
PROGRAMACION DUAL

ESTUDIANTE: ALBERTO PRINCIPE , MARIELA ALANIS

ANDRADE LOPEZ, ABEL KENNEDY
BAILON HILARIO ,VIVIANA NAYELLY
COLLANTES JAIMES ,KIARA JHAMILET
CHACON CONCHUCOS ,JHOSSELYN
JARA CALDERÓN, LUCIO LORENZO

DOCENTE: MG. JORGE ANTONIO SANCHEZ GUZMAN

CICLO: VI
MATERIA: INVESTIGACIÓN OPERATIVA

HUACHO -PERÚ
2023
 INTRODUCCION

Uno de los descubrimientos más importantes durante el desarrollo inicial de la

programación lineal fue el concepto de dualidad y sus muchas e importantes
ramificaciones. Este descubrimiento revelo que asociado a todo problema de
programación lineal existe otro problema lineal llamado dual. Las relaciones entre el
dual y su original (llamado primal) son extremadamente útiles en una gran variedad de
situaciones. Por ejemplo, se verá que de hecho la solución óptima del problema dual es
la que proporciona los precios sombra descritos en las practicas al introducir el análisis
de sensibilidad. Uno de los papeles clave que juega la teoría de la dualidad es la
interpretación y realización del análisis de sensibilidad. De hecho la dualidad nos
permitirá tratar dicho análisis desde el punto de vista algebraico pudiendo así
generalizarlo y aplicarlo a cualquier problema de programación lineal,
independientemente de cual sea su tamaño, número de variables y/o restricciones. Los
orígenes de la dualidad, tal y como hoy se conoce, son, en boca del propio Dantzig ,
atribuibles al célebre matemático John Von Neumann, quien, en octubre de 1947,
conjeturó por primera vez la existencia de un problema dual asociado al modelo de
programación lineal. Dantzig había acudido a Von Neumann en busca de sugerencias e
ideas para desarrollar nuevas técnicas para resolver el modelo de programación lineal
pues, por aquel entonces los ordenadores todavía no se habían desarrollado y el
potencial del método Simplex estaba aún por descubrir.
Programación dual y construcción de modelos dual
Modelo dual: Es una programación lineal obtenida en forma directa y sistemática a
partir del modelo primal, los modelos primal y dual están relacionados de tal manera
que la solución simplex óptimo de uno de ellos produce automáticamente la solución
del otro.
La importancia de la teoría de la dualidad se puede resumir, entre otros aspectos, en lo
siguiente:
 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.

Relaciones entre el método primal y el dual

 El dual tiene la matriz D transpuesta, es decir, si suponemos que D es de orden
sx r, entonces Dt es de orden r x s. Además las variables del primal y el dual son
diferentes, ya que X será un vector de r-componentes mientras que el vector Y
tendrá s-componentes
 Los términos independientes del conjunto de las restricciones del problema
primal forman los coeficientes de la función objetivo del dual.
 Los coeficientes de la función objetivo del primal forman los términos
independientes de las restricciones del dual.
 Las restricciones del dual cambian su sentido al igual que el criterio de
optimización en términos de mínimo o máximo.
 A cada restricción del problema primal le corresponde una variable dual y
análogamente a cada restricción del dual le corresponde una variable del primal.
 Si se halla el dual del problema dual, obtendremos el problema primal.

n m
maximizar z=∑ CjXj Minimizar w=∑ biYi
j−i i= j

Sujeta a: Sujeta a
n m

∑ aijXj ≤ bi para¿ i=1 , 2… . m ¿ ∑ aijYi ≥Cj para J =1 ,2 , , , , n

j−i i=1

Y Y

Xj ≥0 , para j=1, 2 … .. n Yi ≥ 0. para i=1, 2 … .. m

En consecuencia, con el problema primal en la En consecuencia, con el problema primal
en la forma de maximización, el problema dual de maximización, el problema dual está
en la forma de minimización. Aún más, el problema dual usa exactamente los mismos
parámetros que el problema primal, pero en diferentes lugares, tal como se resume a
resume a continuación continuación.
1. Los coeficientes de la 1. Los coeficientes de la función objetivo del prob función
objetivo del problema primal son los lados lema primal son los lados derechos
de derechos las restricciones funcionales del problema dual.
2. Los lados derechos de las restricciones funcionales del problema primal son los
coeficientes de la f coeficientes de la función objetivo del problema du unción
objetivo del problema dual.
3. Los coeficientes de 3. Los coeficientes de una variable de las restricc una
variable de las restricciones funcionales del p iones funcionales del problema
primal roblema primal son los coeficientes de una restricción funcional del
problema dual.
Interpretación de las variables duales Cada variable del dual está asociada a una
restricción del programa primal, y su valor óptimo representa el incremento de la
función objetivo del primal por cada unidad que aumente el término independiente de
dicha restricción, siempre que este último aumento no suponga un cambio de base. Es,
por tanto, el precio adicional máximo que estamos dispuestos a pagar por el incremento
del recurso. Los valores de estas variables se denominan precios sombra.
Los modelos duales pueden ser simétricos o asimétricos; a continuación explicaremos
en que consiste cada uno.

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. Es decir, si el problema original es de la siguiente forma:
Dual asimétrico
Son los restantes tipos de Son los restantes tipos de combinaciones de problem combinaciones
de problema. Como por ejemplo: a. Como por ejemplo:

Obtención de la solución de solución del dual

El dual de un modelo lineal es otro modelo lineal, que puede solucionarse (después de las
oportunas transformaciones, si algunas de las variables resultantes es no negativa o no
restringida en signo) del m o no restringida en signo) del mismo modo que el pr ismo modo que
el primal. Sin embargo, en general pu imal. Sin embargo, en general puede obtenerse la solución
del dual resolviendo el primal.

Método Simplex Dual:

Este método se aplica a problemas óptimos pero in aplica a problemas óptimos pero infactibles.
En factibles. En este caso, las restricciones se expresan en forma canónica (restricciones). La
función objetivo puede estar en la forma de maximización o de minimización. Después de
agregar las variables de holgura y de poner el problema en la tabla, si algún elemento de la parte
derecha es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse
por el método dual simplex. Note que un elemento negativo en el lado derecho significa que el
problema comienza óptimo pero infactible como se requiere en el método dual simplex. En la
iteración donde la solución básica llega a ser factible esta será la solución óptima del problema.

Ventajas:

 Reducir el esfuerzo esfuerzo computacio computacional al resolver resolver

ciertos ciertos modelos modelos de programación programación lineal.
 Permite resolver probl lver problemas de emas de programaci programación li
neal de neal de forma más forma más rápida y sencilla.
  Es otra vía para resolver un resolver un problema problema de programación
lineal. programación lineal.
 Facilita profundizar en profundizar en el contenido e contenido económico
conómico del problema problema original original (primal). (primal).
 Puede ser utilizada para resolver el tilizada para resolver el caso en caso en que
se debe considerar la 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.
 Dado al número d número de restricc restricciones y variables entre variables
entre problema dual problema dual y primal es primal es inverso, se pueden
resolver gráficamente problemas que presenten dos restricciones sin importar el
número de variables.
Desventajas:
 La única desventaja única desventaja de este método, este método, es que se
requiere para requiere para empezar a empezar a iterar la condición de f la
condición de factibilida actibilidad dual.

Análisis de sensibilidad
Es una herramienta útil cuando no tenemos una certeza absoluta sobre los valores que se
han dado a los términos independientes de las restricciones o los coeficientes de la
función objetivo, en este sentido el análisis de sensibilidad consiste en estudiar cómo
evoluciona el óptimo y el valor de la función objetivo del optimo ante variaciones de
dichos términos independientes y dichos términos independientes y coeficientes.
coeficientes. Estudia los intervalos para los cuales la modificación de un valor en el
programa lineal de forma individualizada, no cambia las variables que componen la
base de nuestra solución, hallando para el rango de valores definido en el intervalo, la
evolución de la función objetivo expresado a través de los precios sombra. El objetivo
del análisis de sensibilidad es establecer un intervalo de números reales en el cual el
dato que se analiza puede estar contenido, de tal manera que la solución sigue siendo
óptimo siempre que el dato pertenezca a dicho intervalo, Investigar el cambio en la
solución óptima del problema, cuando se producen cambios en los parámetros del
modelo.
Características del análisis s del análisis de sensibilidad
El análisis de sensibilidad es una El análisis de sensibilidad es una herramien
herramienta efectiva por ta efectiva por dos razones fundamentales. Los modelos de
programación lineal son frecuencias grandes y costosas por lo tanto no es recomendable
para usarlos en un solo caso. Los elementos que se dan como datos para un problema de
programación lineal la mayoría de las veces son estimaciones; por lo tanto es necesario
investigar o tener en cuenta más de un conjunto de casos posibles.
 Conclusión

Hay que considerar que todo problema de programación lineal tiene, asociado a él, un
problema dual de programación lineal. Existen ciertas relaciones útiles entre el
problema original (primal) y su problema dual que refuerzan la habilidad para analizar
el problema original. Por ejemplo, la interpretación económica del problema dual
proporciona los precios sombra que miden el valor marginal de los recursos en el
problema primal, al igual que permite dar una interpretación del método símplex. Puesto
que el método símplex se puede aplicar directamente a cualquiera de los dos problemas
para obtener la solución de ambos al mismo tiempo, es posible ahorrar una gran
cantidad de esfuerzo computacional si se maneja directamente el problema dual.