Esercizio 3

Nel foglio l'esercizio 6 è identico a questo.

0 passi visti su 6

Consegna

Dato il seguente problema di PL

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

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

Due vincoli ≥\ge, due surplus:

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

(1) è la retta x2=x1x_2 = x_1; passa per l'origine, quindi si prova con (1,0)(1, 0), che la rispetta: il semipiano è sotto. (2) è l'orizzontale x2=1x_2 = 1, con il semipiano sopra. PP è l'angolo fra le due rette con la punta in (1,1)(1, 1), illimitato verso destra.

2Vertici e vincoli attiviapri

C'è un solo vertice, A =(1,1)= (1, 1), dove sono attivi (1) e (2). Le altre soluzioni di base non stanno in PP: (0,1)(0, 1), fra (2) e x1≥0x_1 \ge 0, viola (1); (0,0)(0, 0) viola (2).

3Soluzione ottimaapri

Con c=(1,0)c = (1, 0) la retta x1=zx_1 = z va spinta verso sinistra e lascia PP in A. Del resto in PP vale x1≥x2≥1x_1 \ge x_2 \ge 1. Ottimo unico x∗=(1,1)x^* = (1, 1), con 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=−10011x1110−1−1x21010−1\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 & 1 \\ \hline x_1 & 1 & 1 & 0 & -1 & -1 \\ x_2 & 1 & 0 & 1 & 0 & -1 \end{array}

I costi ridotti di s1s_1 e s2s_2 valgono 1: A è l'unico ottimo.

5Varianteapri

Qui cambia la funzione obiettivo, non solo il verso. Con c=(1,−1)c = (1, -1) la retta x1−x2=zx_1 - x_2 = z va spinta verso cc, in basso a destra. Lungo (1+t,1)(1 + t, 1) vale z=tz = t, che cresce senza limite: il problema è illimitato.

Nel tableau di A scritto per min⁡ −x1+x2\min\ -x_1 + x_2:

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

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