Programa lineal dual

Concepto de optimización matemática

El dual de un programa lineal (LP) dado es otro LP que se deriva del LP original (el primario ) de la siguiente manera esquemática:

• Cada variable en el PL primario se convierte en una restricción en el PL dual;
• Cada restricción en el PL primario se convierte en una variable en el PL dual;
• La dirección objetiva se invierte: lo máximo en lo primario se vuelve mínimo en lo dual y viceversa.

El teorema de la dualidad débil establece que el valor objetivo del PL dual en cualquier solución factible es siempre un límite del objetivo del PL primario en cualquier solución factible (límite superior o inferior, dependiendo de si se trata de un problema de maximización o minimización). De hecho, esta propiedad límite es válida para los valores óptimos de los LP duales y primarios.

El teorema de la dualidad fuerte establece que, además, si el primal tiene una solución óptima, entonces el dual también tiene una solución óptima y los dos óptimos son iguales . ^[1]

Estos teoremas pertenecen a una clase más amplia de teoremas de dualidad en optimización . El teorema de la dualidad fuerte es uno de los casos en los que la brecha de dualidad (la brecha entre el óptimo de lo primario y el óptimo de lo dual) es 0.

Forma del LP dual

Supongamos que tenemos el programa lineal:

Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0.

Nos gustaría construir un límite superior para la solución. Entonces creamos una combinación lineal de las restricciones, con coeficientes positivos, tal que los coeficientes de x en las restricciones sean al menos c ^T . Esta combinación lineal nos da un límite superior del objetivo. Las variables y del LP dual son los coeficientes de esta combinación lineal. El LP dual intenta encontrar coeficientes que minimicen el límite superior resultante. Esto da el siguiente LP: ^{[1] : 81–83}

Minimizar b ^T y sujeto a A ^T y ≥ c , y ≥ 0

Este LP se llama el dual del LP original.

Interpretación

El teorema de la dualidad tiene una interpretación económica. ^{[2] [3]} Si interpretamos el PL primario como un problema clásico de " asignación de recursos ", su PL dual puede interpretarse como un problema de "valoración de recursos".

Consideremos una fábrica que está planificando su producción de bienes. Sea su programa de producción (hacer cantidad de bien ), sea la lista de precios de mercado (una unidad de bien se puede vender por ). Las limitaciones que tiene son (no puede producir bienes negativos) y limitaciones de materia prima. Sea la materia prima que tiene disponible, y sea la matriz de costos de materiales (producir una unidad de bien requiere unidades de materia prima ). ${\displaystyle x}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle c\geq 0}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle x\geq 0}$ ${\displaystyle b}$ ${\displaystyle A\geq 0}$ ${\displaystyle i}$ ${\displaystyle A_{ji}}$ ${\displaystyle j}$

Entonces, la maximización de ingresos restringida es el LP primario:

Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0.

Consideremos ahora otra fábrica que no tiene materia prima y desea comprar todo el stock de materia prima de la fábrica anterior. Ofrece un vector de precios de (una unidad de materia prima para ). Para que la oferta sea aceptada, debería darse el caso de que , de lo contrario, la fábrica podría ganar más dinero produciendo un determinado producto que vendiendo la materia prima utilizada para producir el bien. También debería serlo , ya que la fábrica no vendería ninguna materia prima con precio negativo. Entonces, el problema de optimización de la segunda fábrica es el LP dual: ${\displaystyle y}$ ${\displaystyle i}$ ${\displaystyle y_{i}}$ ${\displaystyle A^{T}y\geq c}$ ${\displaystyle y\geq 0}$

Minimizar b ^T y sujeto a A ^T y ≥ c , y ≥ 0

El teorema de la dualidad establece que la brecha de dualidad entre los dos problemas de PL es al menos cero. Económicamente, significa que si a la primera fábrica se le ofrece una oferta para comprar todas sus existencias de materia prima, a un precio por artículo de y , tal que A ^T y ≥ c , y ≥ 0, entonces debería aceptar la oferta. Obtendrá al menos tantos ingresos como los que obtendría produciendo productos terminados.

El teorema de la dualidad fuerte establece además que la brecha de dualidad es cero. En caso de dualidad fuerte, la solución dual es, económicamente hablando, el "precio de equilibrio" (ver precio sombra ) de la materia prima que una fábrica con matriz de producción y existencias de materia prima aceptaría como materia prima, dado el precio de mercado de los productos terminados . (Tenga en cuenta que puede no ser único, por lo que es posible que el precio de equilibrio no esté completamente determinado por , y .) ${\displaystyle y^{*}}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle y^{*}}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle c}$

Para ver por qué, considere si los precios de las materias primas son tales que para algunos , entonces la fábrica compraría más materia prima para producir más bienes , ya que los precios son "demasiado bajos". Por el contrario, si los precios de las materias primas satisfacen , pero no minimizan , entonces la fábrica ganaría más dinero vendiendo su materia prima que produciendo bienes, ya que los precios son "demasiado altos". Al precio de equilibrio , la fábrica no puede aumentar sus ganancias comprando o vendiendo materia prima. ${\displaystyle y\geq 0}$ ${\displaystyle (A^{T}y)_{i}<c_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle A^{T}y\geq c,y\geq 0}$ ${\displaystyle b^{T}y}$ ${\displaystyle y^{*}}$

El teorema de la dualidad también tiene una interpretación física. ^{[1] : 86–87}

Construyendo el LP dual

En general, dado un LP primario, se puede utilizar el siguiente algoritmo para construir su LP dual. ^{[1] : 85} El LP primario se define por:

• Un conjunto de n variables: . ${\displaystyle x_{1},\ldots ,x_{n}}$
• Para cada variable , una restricción de signo : debe ser no negativa ( ), no positiva ( ), o sin restricciones ( ). ${\displaystyle x_{i}}$ ${\displaystyle x_{i}\geq 0}$ ${\displaystyle x_{i}\leq 0}$ ${\displaystyle x_{i}\in \mathbb {R} }$
• Una función objetivo: ${\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}$
• Una lista de m restricciones. Cada restricción j es: donde el símbolo antes de puede ser uno de o o . ${\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}$ ${\displaystyle b_{j}}$ ${\displaystyle \geq }$ ${\displaystyle \leq }$ ${\displaystyle =}$

El LP dual se construye de la siguiente manera.

• Cada restricción primaria se convierte en una variable dual. Entonces hay m variables: . ${\displaystyle y_{1},\ldots ,y_{m}}$
• La restricción de signo de cada variable dual es "opuesta" al signo de su restricción primaria. Entonces " " se vuelve y " " se vuelve y " " se vuelve . ${\displaystyle \geq b_{j}}$ ${\displaystyle y_{j}\leq 0}$ ${\displaystyle \leq b_{j}}$ ${\displaystyle y_{j}\geq 0}$ ${\displaystyle =b_{j}}$ ${\displaystyle y_{j}\in \mathbb {R} }$
• La función objetivo dual es ${\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}$
• Cada variable primaria se convierte en una restricción dual. Entonces hay n restricciones. El coeficiente de una variable dual en la restricción dual es el coeficiente de su variable primaria en su restricción primaria. Entonces, cada restricción i es: , donde el símbolo antes de es similar a la restricción de signo en la variable i en el LP primario. Entonces se convierte en " " y se convierte en " " y se convierte en " ". ${\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}$ ${\displaystyle c_{i}}$ ${\displaystyle x_{i}\leq 0}$ ${\displaystyle \leq c_{i}}$ ${\displaystyle x_{i}\geq 0}$ ${\displaystyle \geq c_{i}}$ ${\displaystyle x_{i}\in \mathbb {R} }$ ${\displaystyle =c_{i}}$

A partir de este algoritmo, es fácil ver que el dual del dual es el primal.

formulaciones vectoriales

Si todas las restricciones tienen el mismo signo, es posible presentar la receta anterior de forma más breve utilizando matrices y vectores. La siguiente tabla muestra la relación entre varios tipos de primarios y duales.

Los teoremas de la dualidad

A continuación, supongamos que el LP primario es "maximizar c ^T x sujeto a [restricciones]" y el LP dual es "minimizar b ^T y sujeto a [restricciones]".

Dualidad débil

El teorema de la dualidad débil dice que, para cada solución factible x del primal y cada solución factible y del dual: c ^T x ≤ b ^T y . En otras palabras, el valor objetivo en cada solución factible del dual es un límite superior del valor objetivo del primal, y el valor objetivo en cada solución factible del primal es un límite inferior del valor objetivo del dual. Aquí hay una prueba para el LP primario "Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0":

• cTx^​​
• = x ^T c [ya que esto es solo un producto escalar de los dos vectores]
• ≤ x ^T ( A ^T y ) [ya que A ^T y ≥ c por las restricciones duales, y x ≥ 0]
• = ( x ^T A ^T ) y [por asociatividad]
• = ( Ax ) ^T y [por propiedades de transposición]
• ≤ b ^T y [ya que A x ≤ b por las restricciones primarias]

La dualidad débil implica:

máx _x c ^T x ≤ mín _y b ^T y

En particular, si el primal es ilimitado (desde arriba), entonces el dual no tiene solución factible, y si el dual es ilimitado (desde abajo), entonces el primal no tiene solución factible.

Fuerte dualidad

El teorema de la dualidad fuerte dice que si uno de los dos problemas tiene una solución óptima, el otro también la tiene y que los límites dados por el teorema de la dualidad débil son estrechos, es decir:

máx _x c ^T x = mínimo _y b ^T y

El teorema de la dualidad fuerte es más difícil de demostrar; las pruebas suelen utilizar el teorema de la dualidad débil como subrutina.

Una prueba utiliza el algoritmo simplex y se basa en la prueba de que, con la regla de pivote adecuada, proporciona una solución correcta. La prueba establece que, una vez que el algoritmo simplex termina con una solución al LP primario, es posible leer en el cuadro final una solución al LP dual. Entonces, al ejecutar el algoritmo simplex, obtenemos soluciones tanto para el primal como para el dual simultáneamente. ^{[1] : 87–89}

Otra prueba utiliza el lema de Farkas . ^{[1] : 94}

Implicaciones teóricas

1. El teorema de la dualidad débil implica que encontrar una única solución factible es tan difícil como encontrar una solución óptima factible. Supongamos que tenemos un oráculo que, dado un PL, encuentra una solución factible arbitraria (si existe). Dado el LP "Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0", podemos construir otro LP combinando este LP con su dual. El LP combinado tiene x e y como variables:

Maximizar 1

sujeto a A x ≤ b , A ^T y ≥ c , c ^T x ≥ b ^T y , x ≥ 0, y ≥ 0

Si el LP combinado tiene una solución factible ( x , y ), entonces por dualidad débil, c ^T x = b ^T y . Entonces x debe ser una solución máxima del LP primario y y debe ser una solución mínima del LP dual. Si el LP combinado no tiene solución factible, entonces el LP primario tampoco tiene solución factible.

2. El teorema de la dualidad fuerte proporciona una "buena caracterización" del valor óptimo de un PL en el sentido de que nos permite demostrar fácilmente que algún valor t es el óptimo de algún PL. La prueba se desarrolla en dos pasos: ^{[4] : ​​260–261}

• Muestre una solución factible al LP primario con valor t ; esto demuestra que el óptimo es al menos t .
• Muestre una solución factible al LP dual con valor t ; esto demuestra que el óptimo es como máximo t .

Ejemplos

Pequeño ejemplo

Considere el LP primario, con dos variables y una restricción:

${\displaystyle {\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}$

La aplicación de la receta anterior da el siguiente LP dual, con una variable y dos restricciones:

${\displaystyle {\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}$

Es fácil ver que el máximo del LP primario se alcanza cuando x ₁ se minimiza a su límite inferior (0) y x ₂ se maximiza a su límite superior bajo la restricción (7/6). El máximo es 4 ⋅ 7/6 = 14/3.

De manera similar, el mínimo del LP dual se alcanza cuando y ₁ se minimiza a su límite inferior bajo las restricciones: la primera restricción da un límite inferior de 3/5 mientras que la segunda restricción da un límite inferior más estricto de 4/6, por lo que el el límite inferior real es 4/6 y el mínimo es 7 ⋅ 4/6 = 14/3.

De acuerdo con el teorema de la dualidad fuerte, el máximo del primal es igual al mínimo del dual.

Usamos este ejemplo para ilustrar la prueba del teorema de la dualidad débil. Supongamos que, en el LP primario, queremos obtener un límite superior para el objetivo . Podemos usar la restricción multiplicada por algún coeficiente, digamos . Para cualquiera obtenemos: . Ahora, si y , entonces , entonces . Por lo tanto, el objetivo del PL dual es un límite superior del objetivo del PL primario. ${\displaystyle 3x_{1}+4x_{2}}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}$ ${\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}$ ${\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}$ ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}$ ${\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}$

Ejemplo de granjero

Solución gráfica al ejemplo del agricultor: después de sombrear las regiones que violan las condiciones, el vértice de la región factible restante con la línea discontinua más alejada del origen da la combinación óptima (que se encuentre en las líneas de pesticidas y tierra implica que los pesticidas y la tierra limitan los ingresos)

Consideremos un agricultor que puede cultivar trigo y cebada con la provisión fija de algo de tierra L , fertilizante F y pesticida P. Para cultivar una unidad de trigo, se deben utilizar una unidad de tierra, unidades de fertilizante y unidades de pesticida. De manera similar, para cultivar una unidad de cebada, se deben utilizar una unidad de tierra, unidades de fertilizante y unidades de pesticida. ${\displaystyle F_{1}}$ ${\displaystyle P_{1}}$ ${\displaystyle F_{2}}$ ${\displaystyle P_{2}}$

El problema principal sería que el agricultor decidiera cuánto trigo ( ) y cebada ( ) cultivar si sus precios de venta son y por unidad. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$

En forma matricial esto se convierte en:

Maximizar: ${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

sujeto a: ${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}$

Para el problema dual, supongamos que y los precios unitarios para cada uno de estos medios de producción (insumos) los fija una junta de planificación. La tarea de la junta de planificación es minimizar el costo total de adquirir las cantidades establecidas de insumos y al mismo tiempo proporcionar al agricultor un precio mínimo unitario para cada uno de sus cultivos (productos), S ₁ para el trigo y S ₂ para la cebada. Esto corresponde al siguiente LP:

En forma matricial esto se convierte en:

Minimizar: ${\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}$

sujeto a: ${\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}$

El problema principal tiene que ver con cantidades físicas. Con todos los insumos disponibles en cantidades limitadas, y suponiendo que se conocen los precios unitarios de todos los productos, ¿qué cantidades de productos producir para maximizar el ingreso total? El doble problema tiene que ver con los valores económicos. Con garantías mínimas para todos los precios unitarios de producción, y suponiendo que se conozca la cantidad disponible de todos los insumos, ¿qué esquema de precios unitarios de insumos establecer para minimizar el gasto total?

A cada variable en el espacio primal le corresponde una desigualdad a satisfacer en el espacio dual, ambas indexadas por tipo de producto. A cada desigualdad a satisfacer en el espacio primal le corresponde una variable en el espacio dual, ambas indexadas por tipo de entrada.

Los coeficientes que limitan las desigualdades en el espacio primario se utilizan para calcular el objetivo en el espacio dual, cantidades de entrada en este ejemplo. Los coeficientes utilizados para calcular el objetivo en el espacio primario limitan las desigualdades en el espacio dual, precios unitarios de producción en este ejemplo.

Tanto el problema primario como el dual utilizan la misma matriz. En el espacio primario, esta matriz expresa el consumo de cantidades físicas de insumos necesarios para producir cantidades determinadas de productos. En el espacio dual, expresa la creación de valores económicos asociados con los productos a partir de precios unitarios de insumos establecidos.

Dado que cada desigualdad puede reemplazarse por una igualdad y una variable de holgura, esto significa que cada variable primaria corresponde a una variable de holgura dual, y cada variable dual corresponde a una variable de holgura primaria. Esta relación nos permite hablar de holgura complementaria.

Programa inviable

Un LP también puede ser ilimitado o inviable. La teoría de la dualidad nos dice que:

• Si el primario es ilimitado, entonces el dual es inviable;
• Si el dual es ilimitado, entonces el primal es inviable.

Sin embargo, es posible que tanto lo dual como lo primario sean inviables. Aquí hay un ejemplo:

Ver la solución a un problema de programación lineal como un vector propio (generalizado)

Existe una estrecha conexión entre los problemas de programación lineal, las ecuaciones propias y el modelo de equilibrio general de von Neumann. La solución a un problema de programación lineal puede considerarse como un vector propio generalizado.

Las ecuaciones propias de una matriz cuadrada son las siguientes:

${\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}}$

donde y son los vectores propios izquierdo y derecho de la matriz cuadrada , respectivamente, y es el valor propio. ${\displaystyle \mathbf {p} ^{T}}$ ${\displaystyle \mathbf {z} }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \rho }$

Las ecuaciones propias anteriores para la matriz cuadrada se pueden extender al modelo de equilibrio general de von Neumann: ^{[5] [6]}

${\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} \geq \rho \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} \mathbf {z} \leq \rho \mathbf {B} {\mathbf {z} }\\\end{matrix}}}$

donde los significados económicos de y son los precios de equilibrio de diversos bienes y los niveles de actividad de equilibrio de varios agentes económicos, respectivamente. ${\displaystyle \mathbf {p} }$ ${\displaystyle \mathbf {z} }$

El modelo de equilibrio de von Neumann se puede ampliar aún más al siguiente modelo de equilibrio estructural con y como funciones valoradas en matrices: ^[7] ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {B} }$

${\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\geq \rho \mathbf {p} ^{T}\mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\\\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\mathbf {z} \leq \rho \mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} ){\mathbf {z} }\\\end{matrix}}}$

donde el significado económico de es los niveles de utilidad de varios consumidores. Un caso especial del modelo anterior es ${\displaystyle \mathbf {u} }$

${\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)\geq \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} \leq \mathbf {B} {\mathbf {z} }\end{matrix}}}$

Esta forma del modelo de equilibrio estructural y los problemas de programación lineal a menudo se pueden convertir entre sí, es decir, las soluciones a estos dos tipos de problemas suelen ser consistentes.

Si definimos , , , , entonces el modelo de equilibrio estructural se puede escribir como ${\displaystyle \mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}}$ ${\displaystyle \mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}}$ ${\displaystyle \mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}}$ ${\displaystyle \mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}}$

Ilustremos el modelo de equilibrio estructural con el pequeño ejemplo discutido anteriormente. En este ejemplo , tenemos y . ${\displaystyle \mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}}$ ${\displaystyle \mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}}$ ${\displaystyle \mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}}$

Para resolver el modelo de equilibrio estructural, obtenemos ^[8]

${\displaystyle \mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3}$

Estos son consistentes con las soluciones a los problemas de programación lineal.

Sustituimos los resultados del cálculo anterior en el modelo de equilibrio estructural, obteniendo ${\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)=(10/3,4,14/3)\geq (3,4,14/3)=\mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} =(14/3,7)^{T}\leq (14/3,7)^{T}=\mathbf {B} {\mathbf {z} }\end{matrix}}}$

Aplicaciones

El teorema de flujo máximo y corte mínimo es un caso especial del teorema de dualidad fuerte: la maximización del flujo es el LP primario y la minimización del corte es el LP dual. Consulte Teorema de corte mínimo de flujo máximo # Formulación de programa lineal .

Otros teoremas relacionados con grafos se pueden demostrar utilizando el teorema de dualidad fuerte, en particular, el teorema de Konig . ^[9]

El teorema Minimax para juegos de suma cero se puede demostrar utilizando el teorema de dualidad fuerte. ^{[1] : sub.8.1}

Algoritmo alternativo

A veces, puede resultar más intuitivo obtener el programa dual sin mirar la matriz del programa. Considere el siguiente programa lineal:

Tenemos m  +  n condiciones y todas las variables no son negativas. Definiremos m  +  n variables duales: y _j y s _i . Obtenemos:

Dado que se trata de un problema de minimización, nos gustaría obtener un programa dual que sea un límite inferior del primal. En otras palabras, nos gustaría que la suma de todos los lados derechos de las restricciones fuera máxima bajo la condición de que para cada variable primaria la suma de sus coeficientes no exceda su coeficiente en la función lineal. Por ejemplo, x ₁ aparece en n  + 1 restricciones. Si sumamos los coeficientes de sus restricciones obtenemos a _1,1 y ₁  +  a _1,2 y ₂  + ... +  a _1,;;n;; y _norte  +  f ₁ s ₁ . Esta suma debe ser como máximo c ₁ . Como resultado, obtenemos:

Tenga en cuenta que en nuestros pasos de cálculo asumimos que el programa está en formato estándar. Sin embargo, cualquier programa lineal puede transformarse a forma estándar y por tanto no es un factor limitante.

Ver también

• Dualidad convexa
• Dualidad
• Dualidad (optimización)
• Programación semidefinida
• Relajación (aproximación)

Referencias

1. Gärtner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.Páginas 81–104.
2. Sakarovitch, Michel (1983), "Complementos sobre la dualidad: interpretación económica de variables duales", Springer Texts in Electrical Engineering , Nueva York, NY: Springer New York, págs. 142-155, ISBN 978-0-387-90829-8, recuperado el 23 de diciembre de 2022
3. Dorfman, Robert (1987). Programación lineal y análisis económico. Paul A. Samuelson, Robert M. Solow. Nueva York: Publicaciones de Dover. ISBN 0-486-65491-5. OCLC  16577541.
4. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, señor  0859549
5. von Neumann, J. (1945). "Un modelo de equilibrio económico general". La Revista de Estudios Económicos . 13 : 1–9.:
6. Kemeny, JG; Morgenstern, O.; Thompson, GL (1956). "Una generalización del modelo von Neumann de una economía en expansión". Econométrica . 24 : 115-135.
7. Li, Wu (2019). Equilibrio general y dinámica estructural: perspectivas de la nueva economía estructural (en chino). Beijing: Prensa de Ciencias Económicas. págs. 122-125. ISBN 978-7-5218-0422-5.
8. "Modelo de equilibrio general y programa lineal dual". Proyecto CRAN-R . Consultado el 26 de junio de 2023 . Documentación detallada sobre el Modelo de Equilibrio General y Programa Lineal Dual en R.
9. AA Ahmadi (2016). "Lección 6: programación lineal y coincidencia" (PDF) . Universidad de Princeton .