República Bolivariana de Venezuela
Ministerio del poder popular para la educación
Instituto politécnico “Santiago Mariño”
Ingeniería en Sistemas
Dualidad
Profesora: Lilibeth Rondón Bachiller: José Rodriguez
Barcelona, 16 de mayo de 2021
Introducción
La Programación Lineal es tal vez la herramienta más famosa y utilizada de la Investigación
de Operaciones. A ella recurren los matemáticos, ingenieros de diferentes disciplinas,
economistas, administradores de empresas, estadísticos, y en general cualquier profesional
que esté involucrado en la toma de decisiones con recursos escasos. Es por ello que en los
planes curriculares de diversos programas de formación a nivel de pregrado, especialización,
maestría e incluso doctorado, la incluyen directamente como asignatura o como tema en
cursos de investigación de operaciones.
En este informe trataremos algunos temas fundamentales de la Programación Lineal y
profundizaremos directamente en la dualidad, lo cual es un concepto concebido en esta
materia.
1. Definición de Dualidad
La dualidad en programación lineal provee de resultados teóricos interesantes que justifican
su uso como herramienta alternativa y complementaria de resolución.
Hay 3 tipos de dualidad, les daré una breve definición de estos, pero mas adelante
profundizaremos en algunos de ellos:
• Teorema de dualidad débil: En general, el valor de cualquier solución factible del
problema de minimización, provee una cota superior del valor óptimo del problema de
maximización.
• Teorema de dualidad fuerte: En el óptimo el valor de la función objetivo del
problema primal será igual al valor de la función objetivo del problema dual evaluada
en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es
infactible. Alternativamente si el problema primal es infactible, entonces el dual es no
acotado.
• Teorema de holguras complementarias: Este teorema es útil ya que simplifica la
forma de obtener la solución óptima dado que como en un problema lineal la solución
óptima (en caso de existir) esta en un vértice, esto implica resolver un sistema de
ecuaciones (con restricciones de igualdad).
2. Identificación de la esencia de la teoría de dualidad.
Para determinar la esencia de algo tenemos que capturar la información que es imprescindible
para dicha actividad, es decir, los fundamentos, la base, y en general lo que defina a ciencia
cierta lo que es.
Podríamos establecer que la esencia de la Teoría de la Dualidad es:
• La teoría de la Dualidad es una propiedad Matemática. Y dicho concepto matemático
se aplica a la teoría de optimización.
• La teoría de Dualidad introduce un nuevo test de optimalidad, como tambíen nuevos
algoritmos para resolver problemas lineales.
• Uno de los aspectos mas importantes de la teoría de dualidad es la interpretación del
análisis de sensibilidad.
3. Identificación del origen del problema dual.
Cada problema de programación lineal (Primal) está estrechamente relacionado con otro
problema simétrico a él, denominado problema dual.
El dualismo es una teoría que surge como consecuencia de una profundización en el estudio
de la programación lineal porque la distribución de los recursos y la formación de los precios
son dos aspectos del mismo problema. Entonces la doble formulación de la programación
lineal no se debe considerar como un simple ejercicio matemático, sino que una y otra versión
del problema viene a explicar dos aspectos económicos distintos para una misma situación
polémica. Una propiedad fundamental de la relación entre el primal y el dual es que la
solución óptima de cualquiera de estos problemas proporciona la solución óptima para el otro.
4. Identificación entre los elementos de los problemas
primal y dual.
Al problema que se formula originalmente se lo conoce como primal, mientras que a su
contraparte estrechamente relacionada se lo conoce como dual. Las relaciones son tales que
cada uno es el dual del otro y encontrar la solución óptima de uno implica encontrar
inmediatamente la solución óptima del otro. Para introducir los conceptos más elementales de
la dualidad se retomará el problema de la
relación predador-presa cuya formulación original fue:
Aplicando los teoremas ya definidos obtenemos:
Establecimiento de las propiedades débil.
Teorema de Dualidad Débil
El Teorema de Dualidad Débil establece que si x є IRn, es una solución factible del problema
Primal P) y ∏ є IRm, una solución factible del problema Dual D), entonces:
Es decir, en el formato descrito anteriormente, el valor que reporta una solución factible del
problema dual de minimización al ser evaluada en su respectiva función objetivo, representa
una cota superior del valor óptimo del problema primal de maximización.
5. Establecimiento de las propiedades de soluciones
complementarias.
Propiedad de las soluciones complementarias: En cada iteración, el simplex determina una
solución FEV X del primal, y una solución complementaria Y del dual. En cada paso se
obtienen variables básicas para el primal, y los valores de las variables de holgura son las
soluciones del dual complementarias óptimas.
6. Desarrollo de las relaciones entre primal y dual.
Mencionaremos algunas de la relaciones mas importantes entre los problemas primal y dual a
continuación:
• Una de las relaciones más importantes ente los problemas primal y dual es la
correspondencia directa entre sus soluciones básicas.
• Como el problema dual es de programación lineal, también tiene soluciones en los vértices. Aún
más, empleando la forma de igualdades del problema, estas soluciones se pueden expresar como
soluciones básicas.
• El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de
modelamiento matemático que nos permite rescatar la información del problema original conocido
comúnmente como modelo primal.
