Esercizio 1

0 passi visti su 6

Consegna

Dato il seguente problema di PL

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

Cosa sarebbe accaduto se la funzione obiettivo fosse stata max⁡x2\max x_2?

Apri nel grafico Apri nel simplesso Variante nel grafico
0Forma standardapri

Manca x2≥0x_2 \ge 0, quindi x2x_2 è libera e si scrive x2=x2+−x2−x_2 = x_2^+ - x_2^-. Il vincolo (1) ha termine noto negativo: moltiplicato per −1-1 diventa −x2≤1-x_2 \le 1 e prende una slack. Il (2) è un ≥\ge e prende un surplus.

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

(1) è l'orizzontale x2=−1x_2 = -1, con il semipiano sopra. (2) passa per (1,0)(1, 0) e (0,1)(0, 1); l'origine darebbe 0≥10 \ge 1, falso, quindi il semipiano è quello sopra la retta. Con x1≥0x_1 \ge 0 la regione PP è illimitata verso destra e verso l'alto.

2Vertici e vincoli attiviapri
VerticeCoordinateVincoli attivi
A(0,1)(0, 1)(2), x1≥0x_1 \ge 0
B(2,−1)(2, -1)(1), (2)

Il punto (0,−1)(0, -1), dove si incontrano (1) e x1≥0x_1 \ge 0, è una soluzione di base non ammissibile: viola (2).

3Soluzione ottimaapri

Con c=(0,1)c = (0, 1) la retta di livello x2=zx_2 = z va spinta verso −c-c, cioè in basso. Si ferma a x2=−1x_2 = -1, dove tocca tutta la semiretta di (1) che parte da B. Gli ottimi sono infiniti, (x1,−1)(x_1, -1) con x1≥2x_1 \ge 2, e z∗=−1z^* = -1.

4Verifica col simplessoapri

In B sono attivi (1) e (2), quindi s1s_1 e s2s_2 stanno fuori base. Siccome x2=−1x_2 = -1, vale x2−=1x_2^- = 1 e x2+=0x_2^+ = 0: anche x2+x_2^+ è fuori base. In base restano x2−x_2^- e x1x_1.

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

I costi ridotti sono tutti ≥0\ge 0: B è ottimo. Quello di s2s_2 vale 0 e la sua colonna, (0,−1)(0, -1), non ha elementi positivi: facendo crescere s2=ts_2 = t si resta ottimi lungo (2+t,−1)(2 + t, -1), la semiretta del disegno. Lo zero di x2+x_2^+ non conta, è la metà della coppia della variabile libera.

5Varianteapri

Con max⁡x2\max x_2 la retta di livello sale senza lasciare PP: i punti (0,t)(0, t) con t≥1t \ge 1 danno z=tz = t, quindi il problema è illimitato.

Nel tableau di B la riga 0 cambia segno e s1s_1 ha costo ridotto −1-1. Con Bland entra s1s_1 ed esce x2−x_2^-, poi entra x2+x_2^+ ed esce x1x_1, e si arriva in A:

x1x2+x2−s1s2riga 0z=11000−1s121001−1x2+111−10−1\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_1 & x_2^+ & x_2^- & s_1 & s_2 \\ \hline \text{riga 0} & z = 1 & 1 & 0 & 0 & 0 & -1 \\ \hline s_1 & 2 & 1 & 0 & 0 & 1 & -1 \\ x_2^+ & 1 & 1 & 1 & -1 & 0 & -1 \end{array}

In A il costo ridotto di s2s_2 è −1-1 e la sua colonna non ha elementi positivi: illimitato.