Esercizio 8

0 passi visti su 6

Consegna

Dato il seguente problema di PL

min⁡ x1s.a. x1≥1(1)x1+2x2≥2(2)x1, x2≥0\begin{aligned} \min\ & x_1 \\ \text{s.a.}\ & x_1 \ge 1 && (1) \\ & x_1 + 2x_2 \ge 2 && (2) \\ & x_1,\ 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

Due vincoli ≥\ge, due surplus:

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

(1) è la verticale x1=1x_1 = 1, con il semipiano a destra. (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 destra e verso l'alto.

2Vertici e vincoli attiviapri
VerticeCoordinateVincoli attivi
A(1,12)(1, \frac{1}{2})(1), (2)
B(2,0)(2, 0)(2), x2≥0x_2 \ge 0

(1,0)(1, 0), fra (1) e x2≥0x_2 \ge 0, viola (2); (0,1)(0, 1), fra (2) e x1≥0x_1 \ge 0, viola (1).

3Soluzione ottimaapri

Con c=(1,0)c = (1, 0) la retta x1=zx_1 = z va spinta verso sinistra e si ferma su x1=1x_1 = 1, che contiene la semiretta di PP che sale da A. Gli ottimi sono infiniti, (1,x2)(1, x_2) con x2≥12x_2 \ge \frac{1}{2}, e z∗=1z^* = 1.

4Verifica col simplessoapri

In A sono attivi (1) e (2): s1s_1 e s2s_2 fuori base, x1x_1 e x2x_2 in base.

x1x2s1s2riga 0−z=−10010x1110−10x2120112−12\def\arraystretch{1.6} \begin{array}{c|c|cccc} & & x_1 & x_2 & s_1 & s_2 \\ \hline \text{riga 0} & -z = -1 & 0 & 0 & 1 & 0 \\ \hline x_1 & 1 & 1 & 0 & -1 & 0 \\ x_2 & \frac{1}{2} & 0 & 1 & \frac{1}{2} & -\frac{1}{2} \end{array}

I costi ridotti sono ≥0\ge 0: A è ottimo. Quello di s2s_2 è 0 e la sua colonna, (0,−12)(0, -\frac{1}{2}), non ha elementi positivi: con s2=ts_2 = t si resta ottimi in (1,12+t2)(1, \frac{1}{2} + \frac{t}{2}), la semiretta del disegno.

5Varianteapri

Con max⁡x1\max x_1 la retta va spinta verso destra e non lascia mai PP: il problema è illimitato.

Nel tableau di A la riga 0 cambia segno e s1s_1 ha costo ridotto −1-1. Entra s1s_1 ed esce x2x_2, e si arriva in B:

x1x2s1s2riga 0z=2020−1x12120−1s11021−1\def\arraystretch{1.6} \begin{array}{c|c|cccc} & & x_1 & x_2 & s_1 & s_2 \\ \hline \text{riga 0} & z = 2 & 0 & 2 & 0 & -1 \\ \hline x_1 & 2 & 1 & 2 & 0 & -1 \\ s_1 & 1 & 0 & 2 & 1 & -1 \end{array}

s2s_2 ha costo ridotto −1-1 e la sua colonna non ha elementi positivi: illimitato.