Problema 8 · Matematiques Iii UPF 2014

Problema 8 (15 punts). Programació lineal i dualitat

Es considera el següent problema de programació lineal:

$\begin{aligned}

\max \quad & z = 2x_1 + 3x_2 + x_3 \\

\text{subjecte a} \quad & x_1 + 2x_2 + x_3 \le 5 \\

& -2x_1 + 3x_3 \ge x_2 - 7 \\

& x_1, x_2, x_3 \ge 0

\end{aligned}$

a)

Formuleu i resoleu el problema dual associat.

$u_1^* =$

$u_2^* =$

$D^* =$

b)

A partir de la solució del dual, determineu la solució òptima del problema primal aplicant el teorema d'holgura complementària.

$x_1^* =$

$x_2^* =$

$x_3^* =$

c)

Quin és el valor màxim de la funció objectiu primal? Quins són els preus ombra? Utilitzant aquests preus, estimeu el nou valor màxim si les restriccions passen a ser:

$\begin{cases}

x_1 + 2x_2 + x_3 \le 4.8 \\

-2x_1 + 3x_3 \ge x_2 - 7.1 \\

x_1, x_2, x_3 \ge 0

\end{cases}$

Valor màxim primal $z^* =$

Preus ombra: $y_1 =$

$y_2 =$

Nou valor màxim estimat $z_{\text{nou}}^* \approx$