Esercizio 2

0 passi visti su 6

Consegna

Dato il seguente problema di PL continuo

min⁡ z(x)=x1s.a. x1≤2(1)x1−x2≥0(2)x1+x2≥1(3)x1, x2≥0\begin{aligned} \min\ & z(x) = x_1 \\ \text{s.a.}\ & x_1 \le 2 && (1) \\ & x_1 - x_2 \ge 0 && (2) \\ & x_1 + x_2 \ge 1 && (3) \\ & x_1,\ x_2 \ge 0 \end{aligned}
  1. disegnarne la regione ammissibile PP;
  2. per ogni soluzione di base individuata indicare quali vincoli essa attiva;
  3. se esiste, indicare una soluzione ottima;
  4. verificare tramite Metodo del Simplesso 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

Una slack per il ≤\le e un surplus per ciascun ≥\ge:

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

(1) è la verticale x1=2x_1 = 2, con il semipiano a sinistra. (2) è la retta x2=x1x_2 = x_1: passa per l'origine, quindi si prova con (1,0)(1, 0), che la rispetta, e il semipiano è sotto. (3) passa per (1,0)(1, 0) e (0,1)(0, 1); l'origine dà 0≥10 \ge 1, falso, quindi il semipiano è sopra. PP è il quadrilatero ABCD.

2Vertici e vincoli attiviapri

La traccia chiede tutte le soluzioni di base: sono le intersezioni di due rette, e quelle dentro PP sono i vertici.

PuntoCoordinateVincoli attiviAmmissibile
A(12,12)(\frac{1}{2}, \frac{1}{2})(2), (3)sì
B(1,0)(1, 0)(3), x2≥0x_2 \ge 0sì
C(2,0)(2, 0)(1), x2≥0x_2 \ge 0sì
D(2,2)(2, 2)(1), (2)sì
(0,0)(0, 0)(2), x1≥0x_1 \ge 0, x2≥0x_2 \ge 0no, viola (3)
(0,1)(0, 1)(3), x1≥0x_1 \ge 0no, viola (2)
(2,−1)(2, -1)(1), (3)no, viola x2≥0x_2 \ge 0

In (0,0)(0, 0) passano tre rette: è una sola soluzione di base, degenere.

3Soluzione ottimaapri

Con c=(1,0)c = (1, 0) la retta x1=zx_1 = z va spinta verso sinistra e lascia PP in A: x∗=(12,12)x^* = (\frac{1}{2}, \frac{1}{2}) e z∗=12z^* = \frac{1}{2}. In B, C e D x1x_1 vale 1, 2 e 2.

4Verifica col simplessoapri

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

x1x2s1s2s3riga 0−z=−120001212s1320011212x112100−12−12x21201012−12\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_1 & x_2 & s_1 & s_2 & s_3 \\ \hline \text{riga 0} & -z = -\frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ \hline s_1 & \frac{3}{2} & 0 & 0 & 1 & \frac{1}{2} & \frac{1}{2} \\ x_1 & \frac{1}{2} & 1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2} \\ x_2 & \frac{1}{2} & 0 & 1 & 0 & \frac{1}{2} & -\frac{1}{2} \end{array}

I costi ridotti fuori base valgono 12>0\frac{1}{2} > 0: A è l'unico ottimo.

5Varianteapri

Con max⁡x1\max x_1 la retta va spinta verso destra fino a x1=2x_1 = 2, che contiene il lato CD: gli ottimi sono (2,x2)(2, x_2) con 0≤x2≤20 \le x_2 \le 2, e z∗=2z^* = 2.

Nel tableau di A la riga 0 cambia segno e s2s_2, s3s_3 hanno costo ridotto −12-\frac{1}{2}. Con Bland entra s2s_2 ed esce x2x_2 (si va in B), poi entra s3s_3 ed esce s1s_1 (si va in C):

x1x2s1s2s3riga 0z=200100s310−1101x1210100s2201110\def\arraystretch{1.6} \begin{array}{c|c|ccccc} & & x_1 & x_2 & s_1 & s_2 & s_3 \\ \hline \text{riga 0} & z = 2 & 0 & 0 & 1 & 0 & 0 \\ \hline s_3 & 1 & 0 & -1 & 1 & 0 & 1 \\ x_1 & 2 & 1 & 0 & 1 & 0 & 0 \\ s_2 & 2 & 0 & 1 & 1 & 1 & 0 \end{array}

In C i costi ridotti sono ≥0\ge 0 e quello di x2x_2 è 0, con un elemento positivo nella sua colonna: facendo entrare x2x_2 esce s2s_2 e si arriva in D con lo stesso z=2z = 2. Gli ottimi sono il lato CD.