Esercizio 5

0 passi visti su 6

Consegna

Dato il seguente problema di PL

min⁡ x1s.a. x1≤1(1)x1+2x2≥2(2)x2≥0\begin{aligned} \min\ & x_1 \\ \text{s.a.}\ & x_1 \le 1 && (1) \\ & x_1 + 2x_2 \ge 2 && (2) \\ & x_2 \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 Tabellare la risposta al punto 3.

Cosa sarebbe accaduto se la funzione obiettivo fosse stata max⁡x1\max x_1?

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

Manca x1≥0x_1 \ge 0, quindi x1=x1+−x1−x_1 = x_1^+ - x_1^-. Le colonne vanno nell'ordine x2,x1+,x1−x_2, x_1^+, x_1^- e poi slack e surplus.

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

(1) è la verticale x1=1x_1 = 1, con il semipiano a sinistra. (2) passa per (2,0)(2, 0) e (0,1)(0, 1); l'origine dà 0≥20 \ge 2, falso, quindi il semipiano è sopra. Con x2≥0x_2 \ge 0, PP è illimitata verso sinistra e verso l'alto.

2Vertici e vincoli attiviapri

C'è un solo vertice, A =(1,12)= (1, \frac{1}{2}), dove sono attivi (1) e (2). (1,0)(1, 0), fra (1) e x2≥0x_2 \ge 0, viola (2); (2,0)(2, 0), fra (2) e x2≥0x_2 \ge 0, viola (1).

3Soluzione ottimaapri

Con c=(1,0)c = (1, 0) la retta x1=zx_1 = z va spinta verso sinistra e non lascia mai PP: i punti (−t,1+t2)(-t, 1 + \frac{t}{2}) con t≥0t \ge 0 stanno in PP e danno z=−tz = -t. Il problema è illimitato e non c'è soluzione ottima.

4Verifica col simplessoapri

Non c'è un ottimo da verificare: si parte dalla base del vertice A e si guarda dove va il simplesso. In A sono attivi (1) e (2), quindi s1s_1 e s2s_2 sono fuori base; x1=1x_1 = 1 dà x1+=1x_1^+ = 1 in base.

x2x1+x1−s1s2riga 0−z=−1000−10x1+101−110x212100−12−12\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_2 & x_1^+ & x_1^- & s_1 & s_2 \\ \hline \text{riga 0} & -z = -1 & 0 & 0 & 0 & -1 & 0 \\ \hline x_1^+ & 1 & 0 & 1 & -1 & 1 & 0 \\ x_2 & \frac{1}{2} & 1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2} \end{array}

Entra s1s_1 ed esce x1+x_1^+, e si arriva in (0,1)(0, 1):

x2x1+x1−s1s2riga 0−z=001−100s1101−110x21112−120−12\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_2 & x_1^+ & x_1^- & s_1 & s_2 \\ \hline \text{riga 0} & -z = 0 & 0 & 1 & -1 & 0 & 0 \\ \hline s_1 & 1 & 0 & 1 & -1 & 1 & 0 \\ x_2 & 1 & 1 & \frac{1}{2} & -\frac{1}{2} & 0 & -\frac{1}{2} \end{array}

x1−x_1^- ha costo ridotto −1-1 e la sua colonna non ha elementi positivi: il problema è illimitato, come sul disegno.

5Varianteapri

Con max⁡x1\max x_1 la retta va spinta verso destra e si ferma su x1=1x_1 = 1: è ottima tutta la semiretta (1,x2)(1, x_2) con x2≥12x_2 \ge \frac{1}{2}, e z∗=1z^* = 1.

Nel tableau di A la riga 0 cambia segno:

x2x1+x1−s1s2riga 0z=100010x1+101−110x212100−12−12\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_2 & x_1^+ & x_1^- & s_1 & s_2 \\ \hline \text{riga 0} & z = 1 & 0 & 0 & 0 & 1 & 0 \\ \hline x_1^+ & 1 & 0 & 1 & -1 & 1 & 0 \\ x_2 & \frac{1}{2} & 1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2} \end{array}

I costi ridotti sono ≥0\ge 0, quindi A è ottimo. Quello di s2s_2 è 0 con la colonna senza elementi positivi: crescendo s2s_2 si percorre la semiretta di ottimi.