Teoría de la dualidad y análisis de Sensibilidad

En los problemas primal en la forma de maximización, los problemas dual están en la forma de minimización.

Parámetros

Los coeficientes de la función objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual.

Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la función objetivo del problema dual.

Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual.

La teoría de la dualidad se basa de manera directa en la idea fundamental

Propiedad de dualidad debil

Si x es una solución factible para el problema primal y y es una solución factible para el problema dual, entonces cx ≤ yb.

Propiedad de dualidad fuerte

Si x* es una solución óptima para el problema primal y y* es una solución óptima para el problema dual, entonces cx*=y*b

Estas dos propiedades implican que cx < yb para soluciones factibles si una o ambas son no
óptimas para sus problemas respectivos, mientras que la igualdad se cumple cuando ambas son óptimas.

Propiedad de Soluciones Complementarias

En cada iteración, el método símplex identifica de manera simultánea una solución FEV, x, para el problema primal y una solución complementaria, y, para el problema dual (que se encuentra en el renglón 0, como los coeficientes de las variables de holgura), donde
cx = yb.

Si x no es óptima para el problema primal, entonces y no es factible para el problema
dua

Propiedad de soluciones complementarias óptimas

Al final de cada iteración, el método símplex identifica de manera simultánea una solución óptima x* para el problema primal y una solución óptima complementaria y* para el problema dual (que se encuentra en el renglón 0 como los coeficientes de las variables de holgura), donde cx* = y*b

Character name

Characteristics

Characteristics

Propiedad de Simetría

En el caso de cualquier problema primal y su problema dual,
las relaciones entre ellos deben ser simétricas debido a que el dual de este problema dual
es este problema primal.

En consecuencia, todas las propiedades anteriores se cumplen sin que importe a cuál de los dos problemas se le llame problema primal.

Si un problema tiene soluciones factibles y una función objetivo acotada (y, por ende,
una solución óptima), entonces ocurre lo mismo con el otro problema, de manera que se aplican tanto la propiedad de dualidad débil como la fuerte.

Si uno de los problemas tiene soluciones factibles y una función objetivo no acotada, (es decir, no tiene solución óptima), entonces el otro problema no tiene soluciones
factibles.

Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o bien la función objetivo es no acotada.

Puede resolverse el problema dual directamente con el método símplex, a fin de identificar una solución óptima para el problema primal.

La evaluación de una solución propuesta para el problema primal.

Su uso en la interpretación económica del problema dual y la visión que se obtiene para el análisis del problema primal.

Es importante llevar a cabo un análisis de sensibilidad, para investigar el efecto que tendría sobre la solución óptima que proporciona el método símplex el hecho de que los parámetros tomen otros valores posibles

Un objetivo fundamental del análisis de sensibilidad es identificar los parámetros
sensibles

Para problemas pequeños, la verificación del efecto de una variedad de cambios en los valores de los parámetros es directa con sólo aplicar de nuevo el método símplex para ver si cambia la solución óptima.

Sin embargo, en problemas más grandes como los que se encuentran en la práctica, el análisis
de sensibilidad requeriría de un esfuerzo computacional exorbitante si fuera necesario volver a aplicar el método símplex desde el principio para investigar cada cambio en el valor de un parámetro

Para cualquier problema primal y su
problema dual, todas las relaciones entre ellos deben ser simétricas.

Una consecuencia de la propiedad de simetría es que todas las afirmaciones que se hicieron antes sobre las relaciones del problema dual con el problema primal también se cumplen en sentido inverso.

Otra consecuencia es que no importa a cuál de los problemas se le dé el nombre de primal y a cuál el de dual. En la práctica, se puede encontrar un problema de programación lineal que se ajuste a nuestra forma estándar y al que se le dé el nombre de problema dual

Método común-extraño raro

Señala que la forma de una restricción funcional o de la restricción sobre una variable del problema dual debe ser común, extraña o rara, lo que depende de que la forma del elemento correspondiente en el problema sea común, extraña o rara.

Como el problema dual es un problema de programación lineal, también tiene soluciones en los vértices.

Aún más, al emplear la forma de igualdades del problema, estas soluciones se pueden expresar como soluciones básicas

Soluciones básicas complementarias

Una idea clave aquí es que la solución del dual que se lee en el renglón 0 también debe ser una solución básica. Esto se debe a que cada una de las m variables básicas del problema primal necesitan tener coeficiente igual a cero en el renglón 0

Propiedad de las soluciones básicas complementarias:
Cada solución básica del problema primal tiene una solución básica complementaria para el problema dual, donde los valores respectivos de la función objetivo (Z y W ) son iguales

Propiedad de holgura complementaria:
La razón por la que se usa el nombre de holgura complementaria para esta última propiedad
es que enuncia (en parte) que para cada par de variables asociadas, si una de ellas tiene holgura en su restricción de no negatividad (una variable básica > 0), entonces la otra no debe tener holgura (variable no básica =0)

En terminología económica, un recurso de este tipo es un “bien gratuito”; el precio de los bienes que tienen una sobredisponibilidad debe ser igual a cero por la ley de la oferta y la demanda. Este hecho justifica la interpretación de la función objetivo para el problema dual como la minimización del valor de los recursos consumidos, en lugar de los asignados

Los valores de yi (o los valores de yi* en la solución óptima) no son otra cosa que los precios sombra.

La interpretación del problema dual proporciona también una interpretación económica de lo que
hace el método símplex en el problema dual.

La meta del símplex es encontrar la manera de usar los recursos disponibles en la forma más redituable. Para alcanzarla, debe llegar a una solución BF que satisfaga todos los requisitos sobre el uso provechoso de los recursos (las restricciones del problema dual).

Estos requisitos comprenden la condición de optimalidad del algoritmo. Para cualquier solución BF dada, los requisitos (restricciones duales) asociados con las variables básicas se satisfacen de manera automática (con la igualdad).

Sin embargo, los asociados con las variables no básicas pueden o no ser satisfecho.

Suponga que los cambios que se hacen en el modelo original ocurren en los coefi cientes de una variable que era no básica en la solución óptima original. ¿Cuál es el efecto de estos cambios sobre esta solución? ¿Todavía es factible? ¿Todavía es óptima?

Como la variable en cuestión es no básica (su valor es cero), el cambio en sus coefi cientes no puede afectar la factibilidad de la solución, por lo cual, la pregunta que queda abierta en este caso es si todavía es óptima.

Las variables de decisión del modelo suelen representar los niveles de las distintas actividades en consideración. En algunas situaciones, se seleccionan algunas de ellas
de entre un grupo grande de actividades posibles en el que las restantes no fueron elegidas debido a que parecían ser menos atractivas.

La inclusión de otra actividad equivale a introducir en el modelo una nueva variable, con los coeficientes apropiados en las restricciones funcionales y en la función objetivo. El único cambio que resulta en el problema dual es la introducción de una nueva restricción