Esercizio 4

0 passi visti su 5

Consegna

Dato il seguente problema di PL

max⁡ x1−x2s.a. x1+x2≥−1(1)x1≤1(2)x1≥0\begin{aligned} \max\ & x_1 - x_2 \\ \text{s.a.}\ & x_1 + x_2 \ge -1 && (1) \\ & x_1 \le 1 && (2) \\ & x_1 \ge 0 \end{aligned}
  1. disegnarne la regione ammissibile PP;
  2. per ogni vertice di PP indicare quali vincoli esso attiva;
  3. se esiste, indicare una soluzione ottima;
  4. verificare tramite Metodo del Simplesso la risposta al punto 3.
Apri nel grafico Apri nel simplesso
0Forma standardapri

max⁡x1−x2\max x_1 - x_2 diventa min⁡ −x1+x2\min\ -x_1 + x_2, e x2x_2 è libera: x2=x2+−x2−x_2 = x_2^+ - x_2^-. Il vincolo (1), moltiplicato per −1-1, diventa un ≤\le con termine noto positivo.

min⁡ −x1+x2+−x2−s.a. −x1−x2++x2−+s1=1x1+s2=1x1, x2+, x2−, s1, s2≥0\begin{aligned} \min\ & -x_1 + x_2^+ - x_2^- \\ \text{s.a.}\ & -x_1 - x_2^+ + x_2^- + s_1 = 1 \\ & x_1 + s_2 = 1 \\ & x_1,\ x_2^+,\ x_2^-,\ s_1,\ s_2 \ge 0 \end{aligned}

Sono due vincoli ≤\le con termine noto ≥0\ge 0, quindi si può partire dalla base delle slack.

1Disegno di Papri

(1) passa per (0,−1)(0, -1) e (−1,0)(-1, 0); l'origine dà 0≥−10 \ge -1, vero, quindi il semipiano contiene OO. (2) è la verticale x1=1x_1 = 1, con il semipiano a sinistra. PP è la striscia 0≤x1≤10 \le x_1 \le 1 sopra la retta (1), illimitata verso l'alto.

2Vertici e vincoli attiviapri
VerticeCoordinateVincoli attivizz
A(0,−1)(0, -1)(1), x1≥0x_1 \ge 01
B(1,−2)(1, -2)(1), (2)3
3Soluzione ottimaapri

Con c=(1,−1)c = (1, -1) la retta x1−x2=zx_1 - x_2 = z va spinta verso cc, in basso a destra, e lascia PP in B. Salendo nella striscia zz diminuisce, quindi il massimo esiste anche se PP è illimitata: x∗=(1,−2)x^* = (1, -2) e z∗=3z^* = 3.

4Verifica col simplessoapri

Dalla base delle slack, cioè dall'origine:

x1x2+x2−s1s2riga 0z=0−11−100s11−1−1110s2110001\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_1 & x_2^+ & x_2^- & s_1 & s_2 \\ \hline \text{riga 0} & z = 0 & -1 & 1 & -1 & 0 & 0 \\ \hline s_1 & 1 & -1 & -1 & 1 & 1 & 0 \\ s_2 & 1 & 1 & 0 & 0 & 0 & 1 \end{array}

Con Bland entra x1x_1 ed esce s2s_2, poi entra x2−x_2^- ed esce s1s_1. Si arriva in B:

x1x2+x2−s1s2riga 0z=300012x2−20−1111x1110001\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_1 & x_2^+ & x_2^- & s_1 & s_2 \\ \hline \text{riga 0} & z = 3 & 0 & 0 & 0 & 1 & 2 \\ \hline x_2^- & 2 & 0 & -1 & 1 & 1 & 1 \\ x_1 & 1 & 1 & 0 & 0 & 0 & 1 \end{array}

Per un max l'angolo in alto a sinistra dà direttamente z∗=3z^* = 3. I costi ridotti di s1s_1 e s2s_2 sono positivi e lo zero di x2+x_2^+ è quello della coppia: B è l'unico ottimo. I punti (0,0)(0, 0) e (1,0)(1, 0) visitati prima non sono vertici del disegno: succede per via della variabile libera.