Pregunta 7 · Matematiques Iii UPF 2013

Pregunta 7 (15 punts). Problema de programació lineal primal-dual i folgança complementària

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

$$\text{Maximitzar } Z = 4x + 3y + 13z$$

subjecte a:

$$\begin{cases} x + 2z \le 1 \\ y + z \le 1 \\ x, y, z \ge 0 \end{cases}$$

a)

Planteja i resol gràficament el problema dual associat. Explica detalladament el procediment seguit per trobar la solució òptima. [7 punts]

$u^* =$

$v^* =$

b)

A partir de la solució del dual, indica el valor màxim de la funció objectiu $Z$ del primal. Quin seria el valor òptim aproximat de la solució si les restriccions del primal canviessin a $x + 2z \le 1.2$ i $y + z \le 0.9$? [3 punts]

c)

Emprant les condicions de folgança complementària i la solució del dual, troba el punt solució $(x^*, y^*, z^*)$ del problema primal. [5 punts]

$x^* =$

$y^* =$

$z^* =$