Fundamentos de Programación Lineal: Dualidad, Sensibilidad y Modelos de Transporte

Teoría de la Dualidad

Asociado a todo problema de programación lineal, existe otro problema lineal llamado dual.

Teorema de la Dualidad

Las siguientes son las únicas relaciones posibles entre los problemas primal y dual:

1. 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.
2. 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.
3. Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o bien la función objetivo es no acotada.

Principios de Dualidad

• Propiedad de dualidad débil: Si x es una solución factible para el problema primal e 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.

Propiedad de Soluciones Complementarias

En cada iteración, el método símplex identifica de manera simultánea una solución FEV (Factible en un Vértice), 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 dual.

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. Los valores de y_i* son los precios sombra para el problema primal.

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.

Holgura Complementaria

La holgura complementaria para esta última propiedad 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).

Estudio de Sensibilidad en la Dualidad

Para la dualidad, el estudio de sensibilidad consiste, en esencia, en la investigación del efecto que tiene sobre la solución óptima el hecho de hacer cambios en los valores de los parámetros del modelo a_ij, b_i y c_j. Sin embargo, al cambiar los valores de los parámetros en el problema primal, se cambian también los valores correspondientes en el problema dual.

El estudio de sensibilidad sirve 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. En general, habrá algunos parámetros a los que se les pueda asignar cualquier valor razonable sin que afecten la optimalidad de esta solución. Sin embargo, también habrá parámetros con valores probables que lleven a una nueva solución óptima.

Esta situación es seria, en particular si la solución original adquiere valores muy inferiores en la función objetivo, o tal vez no factibles. Por tanto, un objetivo fundamental es identificar los parámetros sensibles (es decir, los parámetros cuyos valores no pueden cambiar sin que cambie la solución óptima).

Intervalos Permisibles

Para coeficientes de la función objetivo que no están clasificados como sensibles, también puede resultar de gran utilidad determinar el intervalo de valores del parámetro para el que la solución óptima no cambia. Este intervalo de valores se conoce como intervalo permisible para ese coeficiente.

En algunos casos, el cambio del valor de un parámetro en la columna del lado derecho dentro de una restricción funcional puede afectar la factibilidad de la solución BF (Básica Factible) óptima. Para manejar tales parámetros, es útil determinar el intervalo de valores para el que la solución BF óptima (con los valores ajustados de las variables básicas) seguirá siendo factible. Este intervalo recibe el nombre de intervalo permisible por el lado derecho involucrado. Este rango de valores es también el rango dentro del cual el precio sombra actual de la restricción correspondiente permanece válido.

Conceptos Adicionales de Optimización

• Valor más favorable: Significa el valor más grande si la función objetivo debe maximizarse, o el valor más pequeño si la función objetivo debe minimizarse.
• Solución Factible en un Vértice (FEV): Es una solución que se encuentra en una esquina de la región factible.

Relación entre las Soluciones Óptimas y las Soluciones FEV

El problema debe poseer soluciones FEV y al menos una solución óptima. Además, la mejor solución FEV debe ser una solución óptima. Entonces, si un problema tiene exactamente una solución óptima, ésta debe ser una solución FEV. Si el problema tiene múltiples soluciones óptimas, al menos dos deben ser soluciones FEV.

Supuestos de la Programación Lineal

Supuesto de Proporcionalidad

La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de la actividad x_j, como lo representa el término c_jx_j en la función objetivo. De manera similar, la contribución de cada actividad al lado izquierdo de cada restricción funcional es proporcional al nivel de la actividad x_j, como lo representa en la restricción el término a_ijx_j. En consecuencia, este supuesto elimina cualquier exponente diferente de 1 para las variables en cualquier término de las funciones.

Supuesto de Aditividad

Cada función de un modelo de programación lineal (ya sea la función objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades respectivas.

Supuesto de Divisibilidad

En un modelo de programación lineal, las variables de decisión pueden tomar cualquier valor, incluso valores no enteros, que satisfagan las restricciones funcionales y de no negatividad. En consecuencia, estas variables no están restringidas a solo valores enteros. Se supone que las actividades se pueden realizar a niveles fraccionales.

Supuesto de Certidumbre

Se supone que los valores asignados a cada parámetro de un modelo de programación lineal son constantes conocidas.

Modelos de Transporte

Propiedad de Soluciones Enteras

En los casos de problemas de transporte en los que s_i y d_j toman un valor entero, todas las variables básicas (asignaciones), de toda solución básica factible (inclusive la óptima), asumen también valores enteros.

Propiedad de Soluciones Factibles

Un problema de transporte tiene soluciones factibles si y solo si la sumatoria de las ofertas es igual a la sumatoria de las demandas (∑ s_i = ∑ d_j).

Supuesto de Costo

El costo de distribuir unidades de un origen a un destino dados es directamente proporcional al número de unidades distribuidas. Por tanto, este costo es igual al costo unitario de distribución multiplicado por el número de unidades distribuidas. El costo unitario del origen i al destino j se denota por c_ij.

Tipos de Programación por Metas

Las tres formas de la función de logro más antiguas y todavía más utilizadas en la práctica son las siguientes:

1. Programación por metas ponderadas.
2. Programación por metas lexicográficas.
3. Programación por metas MINMAX.