Programa lineal dual

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 problema de programación lineal primal se convierte en una restricción en el problema de programación lineal dual;
Cada restricción en el problema de programación lineal primal se convierte en una variable en el problema de programación lineal dual;
La dirección del objetivo se invierte: el máximo en lo primal se convierte en el mínimo en lo dual y viceversa.

El teorema de dualidad débil establece que el valor objetivo del problema de programación lineal dual en cualquier solución factible siempre constituye una cota para el valor objetivo del problema de programación lineal primal en cualquier solución factible (cota superior o inferior, según se trate de un problema de maximización o minimización). De hecho, esta propiedad de cota se cumple para los valores óptimos de los problemas de programación lineal dual y primal.

El teorema de dualidad fuerte establece que, además, si el problema primal tiene una solución óptima, entonces el problema 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 diferencia entre el óptimo del problema primal y el óptimo del problema dual) es cero.

Formato del LP doble

Supongamos que tenemos el programa lineal:

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

Queremos construir una cota superior para la solución. Para ello, 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 proporciona una cota superior para la función objetivo. Las variables y del problema de programación lineal dual son los coeficientes de esta combinación lineal. El problema de programación lineal dual intenta encontrar coeficientes que minimicen la cota superior resultante. Esto da como resultado el siguiente problema de programación lineal: ^{[ 1 ]}^{: 81–83}

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

Este LP se considera la versión 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. $1,\ldots ,n$ , que produce utilizando materias primas $1,\ldots ,m$ Para producir una unidad de bien $i$ La fábrica necesita $A_{ji}\geq 0$ unidades de materia prima $j$ . Dejar $x$ ser el programa de producción de la fábrica (producir $x_{i}$ unidades de bien $i$ ), dejar $c\geq 0$ sean los precios de mercado (una unidad de bien) $i$ puede venderse por $c_{i}$ ), y deja $b\geq 0$ sean las cantidades de materia prima que la fábrica tiene disponibles (tiene $b_{j}$ unidades de materia prima $j$ ). Las restricciones son que $x\geq 0$ (no puede producir bienes negativos), y que la fábrica solo puede producir tantos bienes como lo permitan sus cantidades de materias primas, es decir, $Ax\leq b$ La fábrica desea maximizar sus ingresos totales. $c^{\top }x$ .

Por lo tanto, la maximización de ingresos con restricciones es el problema de programación lineal primal:

Maximizar $c^{\top }x$ sujeto a $Ax\leq b,x\geq 0$

Ahora consideremos otra fábrica que desea comprar todo el stock de materia prima. $b$ de la fábrica anterior. Ofrece un vector de precios de $y$ (una unidad de materia prima $i$ para $y_{i}$ ). Para que la oferta sea aceptada, debe darse el caso de que $A^{T}y\geq c$ , ya que de lo contrario la primera fábrica podría ganar más dinero produciendo un determinado producto que vendiendo la materia prima utilizada para producir los bienes. También debería ser $y\geq 0$ , ya que la primera fábrica no vendería sus materiales a un precio negativo. La segunda fábrica desea minimizar la cantidad $b^{\top }y$ que paga todo el stock de materias primas de la primera fábrica. Entonces, el problema de optimización de la segunda fábrica es el problema de programación lineal dual:

Minimizar $b^{\top }y$ sujeto a $A^{\top }y\geq c,y\geq 0$

El teorema de dualidad establece que la brecha de dualidad entre los dos problemas de programación lineal es no negativa. En otras palabras, una solución óptima para este problema de programación lineal dual es al menos tan grande como una solución óptima para el problema de programación lineal primal, lo que significa que una oferta óptima $b^{\top }y$ Los ingresos de la segunda fábrica siempre serán al menos iguales a los ingresos óptimos de la primera fábrica. $c^{\top }x$ . 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 tal manera que $A^{\top }y\geq c,y\geq 0$ Entonces debería aceptar la oferta. Obtendrá al menos los mismos ingresos que obtendría produciendo bienes terminados.

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

Para entender por qué, considere si los precios de las materias primas $y\geq 0$ son tales que $(A^{T}y)_{i}<c_{i}$ para algunos $i$ Entonces la fábrica compraría más materia prima para producir más de buena calidad. $i$ , ya que los precios son "demasiado bajos". Por el contrario, si los precios de la materia prima satisfacen $A^{T}y\geq c,y\geq 0$ pero no minimiza $b^{T}y$ , 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 $y^{*}$ La fábrica no puede aumentar sus ganancias mediante la compra o venta de materia prima.

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

Construcción del LP doble

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

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

El LP doble se construye de la siguiente manera.

Cada restricción primal se convierte en una variable dual. Por lo tanto, hay m variables: $y_{1},\ldots ,y_{m}$ .
La restricción de signo de cada variable dual es "opuesta" al signo de su restricción primal. Por lo tanto, $\geq b_{j}$ " se convierte en $y_{j}\leq 0$ y " $\leq b_{j}$ " se convierte en $y_{j}\geq 0$ y " $=b_{j}$ " se convierte en $y_{j}\in \mathbb {R}$ .
La función objetivo dual es ${\text{minimizar }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$
Cada variable primal 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 primal en su restricción primal. Así, cada restricción i es: $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ , donde el símbolo antes del $c_{i}$ es similar a la restricción de signo en la variable i en el LP primal. Por lo tanto, $x_{i}\leq 0$ se convierte en " $\leq c_{i}$ " y $x_{i}\geq 0$ se convierte en " $\geq c_{i}$ " y $x_{i}\in \mathbb {R}$ se convierte en " $=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 concisa utilizando matrices y vectores. La siguiente tabla muestra la relación entre los distintos tipos de primales y duales.

Los teoremas de dualidad

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

Dualidad débil

El teorema de dualidad débil establece que, para cada solución factible x del problema primal y cada solución factible y del problema dual: c ^Tx ≤ b ^Ty . En otras palabras, el valor objetivo en cada solución factible del problema dual es una cota superior del valor objetivo del problema primal, y el valor objetivo en cada solución factible del problema primal es una cota inferior del valor objetivo del problema dual. A continuación se presenta una demostración para el problema de programación lineal primal "Maximizar c ^Tx sujeto a A x ≤ b , x ≥ 0":

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

La dualidad débil implica:

máx _x c ^Tx ≤ min _y b ^Ty

En particular, si el problema primal no está acotado (superiormente), entonces el problema dual no tiene solución factible, y si el problema dual no está acotado (inferiormente), entonces el problema 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 ajustados, es decir:

máx _x c ^Tx = min _y b ^Ty

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

Una demostración utiliza el algoritmo simplex y se basa en la prueba de que, con la regla de pivote adecuada, proporciona una solución correcta. La demostración establece que, una vez que el algoritmo simplex finaliza con una solución para el problema de programación lineal primal, es posible leer del tableau final una solución para el problema de programación lineal dual. Por lo tanto, al ejecutar el algoritmo simplex, obtenemos soluciones para ambos problemas, el primal y el dual, simultáneamente. ^{[ 1 ]}^{: 87–89}

Otra demostración 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 problema de programación lineal (PL), encuentra una solución factible arbitraria (si existe). Dado el PL "Maximizar c ^Tx sujeto a A x ≤ b , x ≥ 0", podemos construir otro PL combinando este PL con su dual. El PL combinado tiene tanto x como y como variables:

Maximizar 1

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

Si el problema de programación lineal combinado tiene una solución factible ( x , y ), entonces , por dualidad débil, cTx = bTy . Por lo tanto, ^xdebe ser una solución máxima del problema de programación lineal primal e y debe ser una solución mínima del problema de programación lineal dual. Si el problema de programación lineal ^combinado no tiene solución factible, entonces el problema de programación lineal primal tampoco la tiene.

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

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

Ejemplos

Pequeño ejemplo

Consideremos el problema de programación lineal primal, con dos variables y una restricción:

{\begin{aligned}{\text{maximizar }}&3x_{1}+4x_{2}\\{\text{sujeto a }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}

Aplicando la receta anterior se obtiene el siguiente problema de programación lineal dual, con una variable y dos restricciones:

{\begin{aligned}{\text{minimizar }}&7y_{1}\\{\text{sujeto a }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}

Es fácil ver que el máximo del problema de programación lineal primal se alcanza cuando x ₁ se minimiza hasta su límite inferior (0) y x ₂ se maximiza hasta 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.

Usamos este ejemplo para ilustrar la demostración del teorema de dualidad débil. Supongamos que, en el problema de programación lineal primal, queremos obtener una cota superior para la función objetivo. $3x_{1}+4x_{2}$ Podemos usar la restricción multiplicada por algún coeficiente, por ejemplo $y_{1}$ . Para cualquier $y_{1}$ obtenemos: $y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}$ Ahora bien, si $y_{1}\cdot 5x_{1}\geq 3x_{1}$ y $y_{1}\cdot 6x_{2}\geq 4x_{2}$ , entonces $y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}$ , entonces $7y_{1}\geq 3x_{1}+4x_{2}$ Por lo tanto, el objetivo del problema de programación lineal dual es una cota superior del objetivo del problema de programación lineal primal.

Ejemplo de agricultor

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

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

En forma matricial, esto se convierte en:

Maximizar:

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

sujeto a:

{\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 un comité de planificación fija los precios unitarios de cada uno de estos medios de producción (insumos). La función del comité es minimizar el costo total de adquisición de las cantidades establecidas de insumos, al tiempo que garantiza al agricultor un precio unitario mínimo para cada uno de sus cultivos (productos), S₁ _para_eltrigo y S₂ para la cebada. Esto corresponde al siguiente problema de programación lineal:

En forma matricial, esto se convierte en:

Minimizar:

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

sujeto a:

{\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 primal trata sobre 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 trata sobre valores económicos. Con garantías mínimas sobre los precios unitarios de todos los productos, y suponiendo que se conoce la cantidad disponible de todos los insumos, ¿qué esquema de precios unitarios de insumos se debe establecer para minimizar el gasto total?

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

Los coeficientes que delimitan las desigualdades en el espacio primal se utilizan para calcular la función objetivo en el espacio dual, que en este ejemplo son las cantidades de entrada. Los coeficientes utilizados para calcular la función objetivo en el espacio primal delimitan las desigualdades en el espacio dual, que en este ejemplo son los precios unitarios de salida.

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 los valores económicos asociados a los productos a partir de precios unitarios de insumos preestablecidos.

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

Programa inviable

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

Si lo primal no tiene límites, entonces lo dual es inviable;
Si el dual no tiene límites, entonces el primal es infactible.

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

Considerar 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 de autovalores y el modelo de equilibrio general de von Neumann. La solución a un problema de programación lineal puede considerarse como un autovector generalizado.

Las ecuaciones de autovalores de una matriz cuadrada son las siguientes:

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

dónde $\mathbf {p} ^{T}$ y $\mathbf {z}$ son los autovectores izquierdo y derecho de la matriz cuadrada $\mathbf {A}$ , respectivamente, y $\rho$ es el valor propio.

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

${\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 $\mathbf {p}$ y $\mathbf {z}$ son los precios de equilibrio de varios bienes y los niveles de actividad de equilibrio de varios agentes económicos, respectivamente.

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

${\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 $\mathbf {u}$ son los niveles de utilidad de varios consumidores. Un caso especial del modelo anterior es

${\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 $\mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}$ , $\mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}$ , $\mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}$ , $\mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}$ , entonces el modelo de equilibrio estructural se puede escribir como

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

${\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 ya hemos comentado. En este ejemplo, tenemos: $\mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}$ , $\mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}$ y $\mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}$ .

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

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

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

Sustituimos los resultados de cálculo anteriores en el modelo de equilibrio estructural, obteniendo ${\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 problema de programación lineal primal, y la minimización del corte es el problema de programación lineal dual. Véase Teorema de flujo máximo y corte mínimo#Formulación de programa lineal .

Otros teoremas relacionados con grafos 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

En ocasiones, puede resultar más intuitivo obtener el programa dual sin consultar 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:

Dado que se trata de un problema de minimización, nos gustaría obtener un programa dual que sea una cota inferior del programa primal. En otras palabras, nos gustaría que la suma de todos los términos del lado derecho de las restricciones fuera 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,1y ₁ + a _1,2y ₂ + ... + a _1,;;n;;y _n + f ₁s ₁ . Esta suma debe ser como máximo c ₁ . Como resultado, obtenemos:

Cabe señalar que en nuestros cálculos asumimos que el programa está en forma estándar. Sin embargo, cualquier programa lineal puede transformarse a forma estándar, por lo que esto no constituye un factor limitante.

Véase también

Referencias

1 2 3 4 5 6 7 Gartner, 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.
↑ Sakarovitch, Michel (1983), Complementos sobre la dualidad: Interpretación económica de las variables duales , Springer Texts in Electrical Engineering, Nueva York, NY: Springer New York, pp. 142–155 , doi : 10.1007/978-1-4757-4106-3_9 , ISBN 978-0-387-90829-8, consultado el 23 de diciembre de 2022
↑ 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-5OCLC 16577541
↑ Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
↑ von Neumann, J. (1945). "Un modelo de equilibrio económico general". The Review of Economic Studies . 13 : 1–9 .:
↑ 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.
↑ 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.
↑ "Modelo de equilibrio general y programa lineal dual" . CRAN - Proyecto R. Consultado el 26 de junio de 2023. Documentación detallada sobre el modelo de equilibrio general y el programa lineal dual en R.
↑ AA Ahmadi (2016). "Lección 6: programación lineal y emparejamiento" (PDF) . Universidad de Princeton .

[gm06-1] 1 2 3 4 5 6 7 Gartner, 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 las variables duales , Springer Texts in Electrical Engineering, Nueva York, NY: Springer New York, pp. 142–155 , doi : 10.1007/978-1-4757-4106-3_9 , 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-5OCLC 16577541

[lp-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, MR 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" . CRAN - Proyecto 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). "Lección 6: programación lineal y emparejamiento" (PDF) . Universidad de Princeton .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]