Esercizi

Esercizio_esame_01

b) devi prendere due valori di $a,b$ e fare risolvere il problema duale

c) e d) bisogna fare il tableau del problema primale (o duale, dipende dalla domanda) (vedi che c’è scritto dal dottor Spinetti)

Esercizio 1 - esercizio_esame_04

Punto a)

Abbiamo il vettore $\overline{x}=\left[\begin{array}{c}2\\ 1\\ 1\end{array}\right]$ . Per essere un SBA (Soluzione di Base Ammissibile) deve soddisfare questi 2 requisiti :

1. ammissibilità : rispettare i vincoli
2. condizione di vertice (base) : siccome siamo in ${\mathbb{R}}^3$ (3 variabili), per essere un vertice (SBA) il punto deve trovarsi nell’intersezione di almeno 3 vincoli attivi (anche quelli di segno). Ricordiamo che un vincolo è attivo quando la disuguaglianza è soddisfatta all’uguaglianza perfetta ($\text{scarto}=0$).

Attenzione che nel caso ci sia una variabile libera $x_i\in \mathbb{R}$, la seconda regola cambia in :

• se il numero di variabili non nulle è $\le$ numero di vincoli principali (le componenti sono tutte le variabili del problema in forma standard, quindi ricordare di calcolare gli slack (scarti))

Quindi :

• vincolo 1 : $2+3(1)-2(1)=3\le 8⟹$ ammissibile ma non attivo ($\text{scarto}=5$)
• vincolo 2 : $2(2)-1+4(1)=7\ge 6⟹$ ammissibile ma non attivo
• vincoli di segno :
  • $x_1=2\in \mathbb{R}$ (OK, nessun vincolo da attivare qui)
  • $x_2=1\ge 0⟹$ ammissibile ma non attivo
  • $x_3=1\ge 0⟹$ ammissibile ma non attivo

Quindi è ammissibile però non ci sono abbastanza vincoli attivi sufficienti (non ci sono proprio) $⟹$ NO SBA.

---

Punto b)

Richiesta : Può esistere un vertice della regione ammissibile del problema con $x_1,x_2>0$ ?

Per essere un vertice, deve essere un SBA e quindi dobbiamo avere $n=3$ vincoli attivi (${\mathbb{R}}^3$, $n=3$). Allora disponiamo a equazioni e vediamo :

$$\begin{array}{rl}& \{\begin{array}{l}{x}_1+3x_2-2x_3=8\\ 2x_1-x_2+4x_3=6\\ x_1\in \mathbb{R}\to \text{non ci frega basta che }{x}_1>0\\ x_2=0\to \text{no la richiesta ci dice }{x}_2>0\\ x_3=0\end{array}⟹\{\begin{array}{l}{x}_1+3x_2-2x_3=8\\ 2x_1-x_2+4x_3=6\\ x_3=0\end{array}⟹\\ & \\ & ⟹\{\begin{array}{l}{x}_1+3x_2=8\\ 2x_1-x_2=6\\ x_3=0\end{array}⟹\{\begin{array}{l}{x}_1=8-3x_2\\ 16-6x_2-x_2=6\\ x_3=0\end{array}\\ & \\ & ⟹\{\begin{array}{l}{x}_1=8-3x_2⟹x_1=8-3\left(\frac{10}{7}\right)=\frac{26}{7}\\ -7x_2=-10⟹x_2=\frac{10}{7}\\ x_3=0\end{array}\end{array}$$

controlliamo se ammissibile per sicurezza :

• $x_1\in \mathbb{R}\to \text{OK}$
• $x_2>0\to \text{OK}$
• $x_3\ge 0\to \text{OK}$

Allora : SI ESISTE IL VERTICE ED È IL PUNTO $\overline{x}=\left[\begin{array}{c}26/7\\ 10/7\\ 0\end{array}\right]$.

Punto c)

Richiesta : può esistere una soluzione ottima del problema con $x_1,x_2>0$ ?

Ricordiamo questa regola che viene dal teorema degli scarti complementari : Se una variabile del Primale è strettamente positiva, allora il vincolo corrispondente nel Duale deve essere ATTIVO (soddisfatta uguaglianza).

La strategia allora è :

• scrivere il duale
• forzare l’uguaglianza sui vincoli associati a $x_1$ e $x_2$
• risolvere il piccolo sistema di equazioni che si crea
• controllare le soluzioni trovate, se rispettano i vincoli del segno del duale
  • se troviamo una contraddizione $⟹$ ipotesi iniziale è impossibile

Costruiamo il duale :

• abbiamo :

$$\begin{array}{r}x={\left(\begin{array}{c}{x}_1,x_2,x_3\end{array}\right)}^{T}A=\left[\begin{array}{ccc}1& 3& -2\\ 2& -1& 4\end{array}\right]c={\left(\begin{array}{c}2,1,-1\end{array}\right)}^{T}b=\left[\begin{array}{c}8\\ 6\end{array}\right]\end{array}$$

quindi :

• siccome il vincolo 1 è $\le$ : $y_1\le 0$
• siccome il vincolo 2 è $\ge$ : $y_2\ge 0$

$$\begin{array}{rl}\max & w=8y_1+6y_2\\ s.t.& y_1+2y_2=2\to \text{(colonna) }{x}_1\in \mathbb{R}\text{ mettiamo "="}\\ & 3y_1-y_2\le 1\\ & -2y_1+4y_4\le -1\\ & y_1\le 0,y_2\ge 0\end{array}$$

Ora ipotizziamo una soluzione ottima con $x_1,x_2>0$, questo vuol dire che il vincolo nel Duale deve essere ATTIVO.

• $x_1>0⟹$ imponiamo uguaglianza nel vincolo del duale corrispondente : $y_1+2y_2=2$ (già lo era)
• $x_2>0⟹$ imponiamo uguaglianza nel vincolo del duale corrispondente : $3_1-y_2=1$

Risolviamo il sistema :

$$\begin{array}{r}\{\begin{array}{l}{y}_1+2y_2=2\\ 3y_1-y_2=1\end{array}⟹\{\begin{array}{l}{y}_1=\frac{4}{7}\\ y_2=\frac{5}{7}\end{array}\end{array}$$

Ma come vediamo abbiamo contraddizione dal vincolo del segno del duale siccome :

$$\{\begin{array}{l}{y}_1=\frac{4}{7}\\ y_1\le 0\end{array}$$

Pertanto tale soluzione ottima con $x_1,x_2>0$ non può esistere.

---

Punto d)

(NO SIMPLESSO DUALE MA CON METODO DUE FASI)