Esercizio 7

0 passi visti su 5

Consegna

Dato il seguente problema di PL continuo

min⁡ 4x1+3x2s.a. −x1−x2≤1(1)−x1+x2≤1(2)x1≥0\begin{aligned} \min\ & 4x_1 + 3x_2 \\ \text{s.a.}\ & -x_1 - x_2 \le 1 && (1) \\ & -x_1 + x_2 \le 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 una soluzione ottima;
  4. verificare tramite Metodo del Simplesso la risposta al punto 3.
Apri nel grafico Apri nel simplesso
0Forma standardapri

x2x_2 è libera: x2=x2+−x2−x_2 = x_2^+ - x_2^-. Due vincoli ≤\le con termine noto positivo, due slack.

min⁡ 4x1+3x2+−3x2−s.a. −x1−x2++x2−+s1=1−x1+x2+−x2−+s2=1x1, x2+, x2−, s1, s2≥0\begin{aligned} \min\ & 4x_1 + 3x_2^+ - 3x_2^- \\ \text{s.a.}\ & -x_1 - 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) equivale a x1+x2≥−1x_1 + x_2 \ge -1: passa per (−1,0)(-1, 0) e (0,−1)(0, -1) e l'origine lo rispetta, quindi il semipiano è sopra. (2) equivale a x2≤x1+1x_2 \le x_1 + 1: passa per (−1,0)(-1, 0) e (0,1)(0, 1), e l'origine sta sotto. Con x1≥0x_1 \ge 0, PP è il cuneo fra le due rette che si apre verso destra.

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

Le rette (1) e (2) si incontrano in (−1,0)(-1, 0), che viola x1≥0x_1 \ge 0.

3Soluzione ottimaapri

Con c=(4,3)c = (4, 3) la retta 4x1+3x2=z4x_1 + 3x_2 = z va spinta verso −c-c, in basso a sinistra. In A vale z=−3z = -3, in B z=3z = 3; spostandosi verso destra lungo i due lati zz cresce. Ottimo unico x∗=(0,−1)x^* = (0, -1), con z∗=−3z^* = -3.

4Verifica col simplessoapri

In A sono attivi (1) e x1≥0x_1 \ge 0: fuori base s1s_1 e x1x_1, e x2+=0x_2^+ = 0 per la coppia. In base x2−=1x_2^- = 1 e s2=2s_2 = 2.

x1x2+x2−s1s2riga 0−z=310030x2−1−1−1110s22−20011\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 & 1 & 0 & 0 & 3 & 0 \\ \hline x_2^- & 1 & -1 & -1 & 1 & 1 & 0 \\ s_2 & 2 & -2 & 0 & 0 & 1 & 1 \end{array}

I costi ridotti di x1x_1 e s1s_1 sono positivi e lo zero di x2+x_2^+ è quello della coppia: A è l'unico ottimo.