Programa lineal dual

Concepto de optimización matemática

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

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

El teorema de 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 primal 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 de límite se cumple para los valores óptimos de los PL duales y primales.

El teorema de 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 dualidad fuerte es uno de los casos en los que la brecha de dualidad (la brecha entre el óptimo del primal y el óptimo del 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. Por lo tanto, creamos una combinación lineal de las restricciones, con coeficientes positivos, de modo que los coeficientes de x en las restricciones sean al menos c ^T . Esta combinación lineal nos da un límite superior para el objetivo. Las variables y del PL dual son los coeficientes de esta combinación lineal. El PL dual intenta encontrar coeficientes que minimicen el límite superior resultante. Esto da el siguiente PL: ^{[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 dualidad tiene una interpretación económica. ^{[2] [3]} Si interpretamos el LP primal como un problema clásico de " asignación de recursos ", su LP 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 ( cantidad de bien que se fabrica ), sea la lista de precios de mercado (una unidad de bien se puede vender por ). Las restricciones que tiene son (no puede producir bienes negativos) y restricciones de materia prima. Sea la materia prima de la que dispone 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.

Ahora, consideremos 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 por ). Para que se acepte la oferta, debería ser el caso de que , ya 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 ser , 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 PL 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 dualidad establece que la brecha de dualidad entre los dos problemas de PL es al menos cero. En términos económicos, significa que si a la primera fábrica se le ofrece comprar todo su stock de materia prima, a un precio por artículo de y , de modo que A ^T y ≥ c , y ≥ 0, entonces debería aceptar la oferta. Obtendrá al menos tantos ingresos como los que podría obtener produciendo bienes terminados.

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

Para entender por qué, pensemos en lo siguiente: si los precios de las materias primas son tales que, para algunos , la fábrica compraría más materias primas para producir más del bien , puesto que los precios son "demasiado bajos". Por el contrario, si los precios de las materias primas satisfacen , pero no minimizan , la fábrica ganaría más dinero vendiendo su materia prima que produciendo bienes, puesto que los precios son "demasiado altos". A un precio de equilibrio , la fábrica no puede aumentar sus beneficios comprando o vendiendo materias primas. ${\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 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. Por lo tanto, 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. Por lo tanto, " " se convierte en y " " se convierte en y " " se convierte en . ${\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. Por lo tanto, 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. Por lo tanto, 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. Por lo tanto, 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 primordial.

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 valores primarios y duales.

Los teoremas de dualidad

A continuación, supongamos que el LP primal 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 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 PL del primal "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 no tiene límites (desde arriba), entonces el dual no tiene solución factible, y si el dual no tiene límites (desde abajo), entonces el primal no tiene solución factible.

Fuerte dualidad

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

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

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

Una prueba utiliza el algoritmo simplex y se basa en la prueba de que, con la regla pivote adecuada, proporciona una solución correcta. La prueba establece que, una vez que el algoritmo simplex termina con una solución para el LP primario, es posible leer de la tabla final una solución para el LP dual. Por lo tanto, al ejecutar el algoritmo simplex, obtenemos soluciones tanto para el LP primario 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 dualidad débil implica que encontrar una única solución factible es tan difícil como encontrar una solución factible óptima . Supongamos que tenemos un oráculo que, dado un PL, encuentra una solución factible arbitraria (si existe alguna). Dado el PL "Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0", podemos construir otro PL combinando este PL con su dual. El PL 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 PL combinado tiene una solución factible ( x , y ), entonces por dualidad débil, c ^T x = b ^T y . Por lo tanto, x debe ser una solución máxima del PL primario e y debe ser una solución mínima del PL dual. Si el PL combinado no tiene una solución factible, entonces el PL primario tampoco tiene una solución factible.

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

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

Ejemplos

Pequeño ejemplo

Consideremos el LP primal, 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 como resultado 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 PL 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 límite inferior real es 4/6 y el mínimo es 7 ⋅ 4/6 = 14/3.

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

Utilizamos este ejemplo para ilustrar la prueba del teorema de dualidad débil. Supongamos que, en el PL primario, queremos obtener un límite superior para el objetivo . Podemos usar la restricción multiplicada por algún coeficiente, digamos . Para cualquier obtenemos: . Ahora, si y , entonces , por lo que . Por lo tanto, el objetivo del PL dual es un límite superior para el 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 agricultor

Solución gráfica para el 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 (su ubicación sobre las líneas de tierra y pesticida implica que los ingresos están limitados por la tierra y el pesticida, no por el fertilizante)

Consideremos un agricultor que puede cultivar trigo y cebada con una provisión fija 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 de matriz 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 una junta de planificación fija los precios unitarios de y para cada uno de estos medios de producción (insumos). La tarea de la junta de planificación es minimizar el costo total de adquisición de las cantidades fijas de insumos y, al mismo tiempo, proporcionar al agricultor un precio unitario mínimo para cada uno de sus cultivos (productos), S ₁ para el trigo y S ₂ para la cebada. Esto corresponde al siguiente PL:

En forma de matriz 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 primario se ocupa de las 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 se deben producir para maximizar los ingresos totales? El problema dual se ocupa de los valores económicos. Con garantías mínimas para todos los precios unitarios de los productos y suponiendo que se conoce la cantidad disponible de todos los insumos, ¿qué esquema de precios unitarios de los insumos se debe establecer para minimizar el gasto total?

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

Los coeficientes que delimitan 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 delimitan las desigualdades en el espacio dual, precios unitarios de salida en este ejemplo.

Tanto el problema primal como el dual utilizan la misma matriz. En el espacio primal, esta matriz expresa el consumo de cantidades físicas de insumos necesarias para producir cantidades fijas 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 fijos.

Como cada desigualdad puede ser reemplazada 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 PL también puede ser ilimitado o inviable. La teoría de la dualidad nos dice que:

• Si lo primordial no tiene límites, entonces lo dual es inviable;
• Si lo dual no tiene límites, entonces lo primordial es inviable.

Sin embargo, es posible que tanto el dual como el primordial sean inviables. He aquí un ejemplo:

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

Existe una estrecha relación entre los problemas de programación lineal, las ecuaciones propias y el modelo de equilibrio general de von Neumann. La solución de 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 varios 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 con valores matriciales: ^[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 el nivel de utilidad de los distintos 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 que analizamos 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 corte mínimo de flujo máximo 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 gráficos pueden demostrarse utilizando el teorema de dualidad fuerte, en particular, el teorema de König . ^[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. Consideremos el siguiente programa lineal:

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

Como se trata de un problema de minimización, nos gustaría obtener un programa dual que sea una cota inferior del primal. En otras palabras, nos gustaría que la suma de todos los miembros del lado derecho de las restricciones fuera la máxima bajo la condición de que para cada variable primal 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 _n  +  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 formato estándar y, por lo tanto, no es un factor limitante.

Véase 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 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, consultado 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: Dover Publications. 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, Sr.  0859549
5. von Neumann, J. (1945). "Un modelo de equilibrio económico general". The Review of Economic Studies . 13 : 1–9.:
6. Kemeny, JG; Morgenstern, O.; Thompson, GL (1956). "Una generalización del modelo de von Neumann de una economía en expansión". Econometrica . 24 : 115–135.
7. Li, Wu (2019). Equilibrio general y dinámica estructural: perspectivas de la nueva economía estructural (en chino). Pekín: Economic Science Press. pp. 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 el programa lineal dual en R.
9. AA Ahmadi (2016). "Conferencia 6: programación lineal y emparejamiento" (PDF) . Universidad de Princeton .