Dimostrare ottimalità soluzione

[zardo1992]

Sia dato il seguente problema di programmazione lineare:

$ min (2x_1 + 4x_2 + 2x_3 - x_4) $
$ 3x_1 + x_2 \ge 2 $
$x_2 + 2x_3 = 4 $
$x_3 + 4x_4 \le 5 $

$x_i \ge 0, i = 1,2,3,4 $

Dimostrare che $ (\{2}/{3}, 0, 2, \{3}/{4}) $ è soluzione ottima, senza applicare l'algoritmo del simplesso.

Ho pensato di passare al duale, così da poter applicare le condizioni di complementarietà e dimostrare che la soluzione del primale è ottima applicando la dualità forte.

Il punto è che il duale è molto più complesso del primale, perché ho una variabile negativa e una libera, che portano ulteriori variabili, e non è possibile risolverlo graficamente quindi devo comunque passare per il simplesso!

Qualche aiuto?

Grazie

[zardo1992]

Ho risolto. Ho applicato le condizioni di complementarietà al duale, e tramite queste ho trovato il valore delle 3 incognite duali. Sostituendo le soluzioni nel primale e le soluzioni appena trovate nel duale, il valore della funzione obiettivo del primale è lo stesso del valore della funzione obiettivo del duale, così posso concludere tramite la dualità forte che la soluzione data è ottima.