Necesito ayuda con un problema de programación lineal

Question

El problema LP se presenta a continuación:

max $3x_1+2x_2$ s.t.

$x_1+x_2\leq3$

$2x_1+x_2-x_3\leq1$

$x_1+2x_2-2x_3\leq1$.

Las restricciones de no negatividad se aplican a cada una de las tres variables.

Enunciado de la pregunta: Formula el problema para cualquier valor fijo de $x_3 \in [0,\infty)$. El valor máximo de $3x_1+2x_2$ es una función de $x_3$. Encuentra la función y máximiza.

Mi intento:

El dual es:

min $3u_1+u_2+u_3$

s.t. $u_1+2u_2+u_3\geq3$

$u_1+u_2+2u_3\geq2$

$-u_2-2u_3\geq0$

A partir de la tercera restricción de desigualdad del dual, es claro que $u_2=u_3=0$. Luego, a partir de las dos primeras restricciones, obtenemos $u_1\geq3 \Rightarrow u_1>0$, por lo tanto, se cumple con la primera restricción del primal con una igualdad. Usando la igualdad y las dos restricciones de desigualdad del problema primal, obtengo $x_2\geq 5-x_3$ y $x_2 \leq 2x_3-2$.

Además, la función criterio del primal es $9-x_2$ (después de eliminar $x_1$ usando la restricción de igualdad. Claramente, 9 es el valor máximo (también confirmado por el valor óptimo del dual).

Después de esto, puedo escribir $11-2x_3\leq 9-x_2\leq 4-x_3\leq 9$. Pero más allá de esto, estoy atascado. ¿Cómo puedo proceder?

Answer 1

No creo que tomar el dual del problema ayudaría. Atacaría este problema directamente discutiendo casos.

Tu objetivo aumenta mientras que todas tus restricciones se vuelven más estrictas a medida que $x_1$ o $x_2$ aumenta. Por lo tanto, es seguro concluir que tantas restricciones están vinculadas. Sin embargo, puedes tener como máximo 2 restricciones vinculantes (si hay más, son redundantes), porque solo tienes 2 variables primarias. Más restricciones (excepto las redundantes) ligadas te darán un sistema lineal sobredeterminado y no conducirán a ninguna solución.

Teniendo esto en mente, discutimos casos sobre cuáles dos restricciones están vinculantes. Etiqueta $$x_1 + x_2\leq 3\tag{1}$$ $$2x_1 + x_2\leq 1+x_3\tag{2}$$ $$x_1 + 2x_2\leq 1+2x_3\tag(3)$$ Entonces hay 3 casos, ya sea que (1)(2) estén vinculadas, (1)(3) estén vinculadas, o (2)(3) estén vinculadas. Nota que si (3) está vinculada, (2) también debe estarlo. La razón es que en (2), $x_1$ es más costoso (precio relativo $2/1$) que en (3) (precio relativo $1/2$), mientras que el presupuesto total es más ajustado ($1+x_3 < 1+2x_3$). Así que podemos descartar el caso de vinculación (1)(3) [por supuesto, puedes discutir este caso y encontrarás que está dominado por otro caso].

Ahora, Caso 1: supongamos que (1)(2) están vinculadas. Luego estás resolviendo un sistema de ecuaciones $$x_1 +x_2 = 3$$ $$2x_1 + x_2 = 1+ x_3$$ que tiene la solución $$x_1 = x_3-2, x_2 = 5-x_3$$ que da como resultado el valor objetivo $$3(x_3-2) + 2(5-x_3) = 4 + x_3$$ Necesitamos verificar que (3) se cumpla. Sustituyendo $x_1$ y $x_2$, obtenemos $$ x_3-2 + 2(5-x_3) \leq 1+2x_3 $$ lo cual implica que $x_3 \geq \frac{7}{3}$. Además, la restricción primaria en $x_2$ requiere que $x_3 \leq 5$. Es decir, esta solución existe cuando $5 \geq x_3\geq \frac{7}{3}$.

Caso 2: supongamos que (2)(3) están vinculadas. Luego estás resolviendo un sistema de ecuaciones $$2x_1 + x_2= 1+x_3$$ $$x_1 + 2x_2 = 1+2x_3$$ Esto te da $x_1 + x_2 = 2/3 + x_3$. Para satisfacer (1), necesitamos requerir $x_3 \leq 7/3$. De hecho, el rango de la solución es complementario al Caso 1. La solución es $$x_1 = 1/3, x_2 = 1/3 + x_3$$ lo cual te da un valor de $$2x_3 + \frac{5}{3}$$ En particular, cuando $x_3 = 7/3$, las soluciones de Caso 1 y Caso 2 coinciden.

En resumen, la solución al programación lineal es $$(x_1, x_2) = \begin{cases}(1/3, 1/3 + x_3), \text{ cuando } 0 \leq x_3 < 7/3\\(x_3-2, 5-x_3), \text{ cuando } 5 \geq x_3 \geq 7/3\\ (3, 0), \text{ cuando }x_3 \geq 5 \end{cases}$$

Alternativamente, también puedes dibujar un gráfico en un plano $x_2-x_1$ porque tienes un problema 2D.