capitolo2.tex

\chapter{31/03/2014}

I problemi saranno posti in maniera leggermente diversa, cioè quella fornita sul pdf reperibile sul sito del docente al seguente link (se il testo è effettivamente disponibile, s'intende): \url{http://www.or.deis.unibo.it/staff_pages/martello/testi_esercizi_ottimizzazione.pdf}.
Inoltre, anche se durante l'esercitazione non è stata trovata la soluzione dei problemi duali, dato che il metodo per individuarli è stato spiegato dal prof. nella lezione subito successiva, ho ritenuto opportuno e interessante cercarle io stesso e inserirle in questo eserciziario. A maggior ragione, le soluzioni dei duali \textbf{potrebbero essere errate}, per cui chiedo ad ognuno di provare a rivederle e comunicarmi gli eventuali errori trovati.
Inoltre, ho deciso - in maniera del tutto personale e arbitraria - di preporre la rappresentazione grafica alla risoluzione con tableau negli esercizi di ottimizzazione. L'unico motivo è che mi piace avere un'idea un po' più concreta di quello che sta succedendo sul piano geometrico.

\section{Esercizio 4}
Un'azienda chimica produce due tipi di composto, A e B, che danno lo stesso profitto, utilizzando una sostanza base della quale sono disponibili 8 quintali. Ogni tonnellata di composto (indipendentemente dal tipo) contiene un quintale di sostanza base. Il numero di tonnellate di composto A prodotto deve superare di almeno una unità il numero di tonnellate di composto B prodotto. Per problemi di stoccaggio non si possono produrre più di 6 tonnellate di composto A. Si associ la variabile $x_1$ al composto A e la variabile $x_2$ al composto B.
\begin{enumerate}
\item Definire il modello LP che determina la funzione di massimo profitto.
\item Porre il modello in forma standard e risolverlo con il metodo delle due fasi e la regola di Bland, introducendo il minimo numero di variabili artificiali. Dire esplicitamente qual è la soluzione trovata.
\item Disegnare con cura la regione ammissibile.
\item Costruire il duale del modello definito al punto 2 e ricavarne le soluzioni ottime.
\item Imporre il vincolo di interezza sulle variabili (supporre che non si possano produrre frazioni di tonnellate) e risolvere il problema con il metodo branch-and-bound. [\textit{Questo punto non sarà analizzato perché in data di stesura del documento (04/04/2014) l'argomento non è ancora stato trattato dal prof}]
\end{enumerate}

\subsection{Modellizzazione}

Si indichi con:
\begin{itemize}
\item $x_1$ il numero di tonnellate di composto A;
\item $x_2$ il numero di tonnellate di composto B.
\end{itemize}
Lo scopo del nostro problema è di massimizzare i profitti ottenuti dalla produzione. Anche se non siamo a conoscenza degli esatti profitti dati da ogni prodotto, sappiamo che entrambi i composti portano allo stesso profitto. Possiamo quindi esprimere così la funzione di profitto:
$$
\max z = x_1 + x_2
$$

Modelliamo ora i vincoli espressi dal problema.
Il modello matematico può essere quindi così riassunto (sono state apportate semplificazione algebriche):
\begin{align*}
\max z	&= x_1+x_2 \\
\st\;\;	& x_1+x_2 \leq 8\\
		& x_1 \geq x_2 + 1\\
		& x_1 \leq 6 \\
	  	& x_1,x_2 \geq 0
\end{align*}

\subsection{Problema in forma grafica}

In figura \vref{fig:graph4} è rappresentato graficamente il problema presentato. In giallo è rappresentato il politopo $P$ e sono stati chiamati $\alpha,\beta,\gamma,\delta$ i suoi quattro vertici, i quali sappiamo corrispondere ognuno ad una BFS.
Il gradiente della funzione obiettivo vale
\begin{equation*}
\nabla(z)=\left(\frac{\partial z}{\partial x},\frac{\partial z}{\partial y}\right) = \left(1,1\right) \\
\end{equation*}
Il politopo $P$ è, ovviamente, limitato nella direzione del gradiente (si fa notare che finora $P$ è sempre limitato in ogni direzione, quindi qualsiasi direzione avesse il gradiente non ci sarebbero problemi).

\begin{figure}[htbp]
\centering
\begin{tikzpicture}
\begin{axis}
[axis lines=middle, axis equal, enlargelimits, xlabel=$x_1$, ylabel=$x_2$,
 every axis x label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=west,
 },
 every axis y label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=south,
 },]
    \path[name path=AX]
        (axis cs:\pgfkeysvalueof{/pgfplots/xmin},0)--
        (axis cs:\pgfkeysvalueof{/pgfplots/xmax},0);
    \path[name path=AY]
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymin})--
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymax});
    \path[name path=UP]
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmin},\pgfkeysvalueof{/pgfplots/ymax})--
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmax},\pgfkeysvalueof{/pgfplots/ymax});
\addplot
[domain=0:8, samples=10, thick, blue, name path=xy8]
{-x+8} node [pos=0.2,pin={75:{\color{blue}$x_1+x_2=8$}}, inner sep=0pt] {};
\addplot
[domain=0:8, samples=10, thick, red, name path=xy1]
{x-1} node [pos=0.8, pin={-85:{\color{red}$x_1=x_2+1$}}, inner sep=0pt] {};
\addplot
[domain=0:8, samples = 10, thick, purple, name path=x6]
(6,x) node [pos=0.3, anchor=north, pin={0:{\color{purple}$x_1=6$}}, inner sep= 0pt] {};
\addplot[thick, fill=yellow, fill opacity=0.5] fill between [of=xy1 and AX, soft clip={domain=1:6}];
\addplot[white] fill between [of=xy8 and UP];
%\addplot[pattern=north east lines, pattern color=red!10] fill between [reverse=true, of=AX and UP, soft clip={domain=0:5}];
\addplot[white] fill between [of=x6 and AX];
\addplot[pattern=north east lines, pattern color=blue!10] fill between [of=xy8 and AX];
\addplot[pattern=north west lines, pattern color=red!10] fill between [of=xy1 and AX];
%\addplot[pattern=north east lines, pattern color=blue!10] fill between [of=AX and 2x2y9, soft clip={domain=0:5}];
\addplot[pattern=horizontal lines, pattern color=purple!10] fill between [of=AY and x6];
\ints{AX}{xy1}{$\alpha$}{alp};
\ints{xy1}{xy8}{$\beta$}{bet};
\intw{xy8}{x6}{$\gamma$}{gam};
\intnw{x6}{AX}{$\delta$}{del};
\node at (axis cs:4.5,1.5) {$P$};
\addplot[-latex, thick] coordinates
           {(0,0) (1/1.414,1/1.414)} node [pos=.3, anchor=south, label={45:{\small $\nabla z$}}] {};
\end{axis}
\end{tikzpicture}
\caption{Rappresentazione cartesiana del problema di programmazione lineare}
\label{fig:graph4}
\end{figure}

Possiamo osservare che anche solo dal grafico è facilmente intuibile dove si troverà la soluzione ottima. Il gradiente $\nabla z$ è \textbf{perpendicolare} allo spigolo $\OL{\beta \gamma}$, da ciò potremmo dedurre che non esiste una soluzione ottima, ma che ve ne sono infinite e tutte posizionate su questo spigolo. Riprenderemo questa considerazione in seguito, dopo aver risolto il problema con il metodo del simplesso.

\subsection{Forma standard}
Ricordiamo che un problema di \textbf{programmazione lineare in forma standard} è nella forma (matriciale):
\begin{align*}
\min c'x& \\
Ax& = b \\
x& \geq 0
\end{align*}
Trasformiamo la funzione obiettivo $z$ in $\varphi$ tale che:
\begin{equation*}
\varphi=-z=-x_1-x_2
\end{equation*}
Quindi introduciamo una \textbf{variabile slack} per ogni disequazione con simbolo $\leq$ e una \textbf{variabile surplus} per ogni disequazione con simbolo $\geq$. Otterremo infine:
\begin{alignat*}{7}
&\min \varphi = \quad && -x_1 \quad\; && -x_2 \quad\;\; && \qquad\qquad && \qquad\qquad && \qquad\qquad && \\
&\;\st  &&+x_1			&&+x_2	 		&&+\pmb{x_3}	&&		 		&&					&&=8\\
&	 	&&+x_1			&&-x_2			&&				&& -\pmb{x_4}	&&					&&=1\\
&	 	&&+x_1			&&				&&				&&				&&+\pmb{x_5}		&&=6\\
&		&&\quad\; x_1,	&&\quad\; x_2,	&&\quad\; x_3,	&&\quad\; x_4,	&&\quad\; x_5		&&\geq 0
\end{alignat*}

\subsection{Risoluzione tramite tableau}

\begin{table}[htbp]
\centering
\begin{tabular}{rcccccc}
			&$-\varphi$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ \\
$\OL{c_j}$ 	& \Sc{0} 	& -1 	& -1 	& 0 	& 0 	& 0 \\
\cline{2-7}
$R_1$ 		& \Sc{8} 	& 1 	& 1 	& 1 	& 0 	& 0 \\
$R_2$		& \Sc{1} 	& 1 	& -1	& 0 	& -1 	& 0 \\
$R_3$		& \Sc{6} 	& 1 	& 0 	& 0 	& 0 	& 1 \\
\end{tabular}
\caption{Tableau iniziale.}
\label{tab:tab41}
\end{table}

In tabella \vref{tab:tab41} il tableau ricavato dal nostro problema. A differenza dei precedenti esercizi, la fortuna non è dalla nostra parte e non abbiamo nessuna sottomatrice identità a disposizione da utilizzare come base ammissibile.
Si potrebbe \textit{erroneamente} pensare che per ottenere una BFS sia sufficiente operare $R_2\leftarrow -1\cdot R_2$. Ma si fa subito notare che così facendo otterremo come base:
\begin{align*}
\mathcal{B}&=\{A_3,A_4,A_5\}\\
x&=(0,0,8,1,6)
\end{align*}
Questa \textbf{non è una BFS} in quanto ricade \textit{all'esterno} del politopo $P$. Per ottenere una BFS di partenza, quindi, ricorriamo alla \textbf{fase 1 del metodo del simplesso}.

\subsubsection{Fase 1 - aggiunta di variabili artificiali}

Per ottenere una BFS aggiungiamo un numero $n'\leq m$ di variabili artificiali tali da riuscire ad ottenere una BFS nel nuovo problema con $m$ vincoli e $n+n'$ variabili. Ipoteticamente, potremmo aggiungere sempre $n'=m$ variabili artificiali tali da formare già loro una sottomatrice identità nel tableau, ma tale metodo risulterebbe molto sconveniente nel caso in cui i vincoli e le variabili fossero centinaia o migliaia. Inoltre, ma non meno importante, la traccia dell'esercizio richiede esplicitamente di \textbf{introdurre il minore numero di variabili artificiali}.

Per ridurre al minimo le variabili artificiali $x_i^a,\quad i=1,\cdots,n'$ è sufficiente aggiungerne una per ogni colonna della matrice identità mancante nel tableau originale. Nel nostro caso manca solo la seconda colonna e sarà quella che introdurremo con l'\textit{unica} variabile artificiale $x^a$, trasformando il secondo vincolo in:
$$
x_1 - x_2 - x_4 + x^a = 1
$$
Il nostro scopo, dopo l'introduzione di $x^a$, sarà quello di \textbf{eliminarla} dalla base. Per far ciò bisogna fare in modo che questa valga zero e quindi introduciamo, a tale scopo, una nuova funzione obiettivo da minimizzare $\psi$ tale che:
$$
\psi = \sum_{i=1}^{n'}x_i^a = x^a
$$
Scriviamo il nuovo tableau in tabella \vref{tab:tab42} e applichiamo il simplesso per ottimizzare la nostra funzione $\psi$.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{8} 	& 1		& 1 	& 1 	& 0 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{1} 	& 1		& -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{6} 	& 1 	& 0 	& 0 	& 0 	& \Sc{1}& 0 \\
\end{tabular}
\caption{Nuovo tableau con la variabile artificiale $x^a$.}
\label{tab:tab42}
\end{table}
Abbiamo una sottomatrice identità formata dalla base:
$$
\mathcal{B}=\{A_3,A_6,A_5\}
$$
Per avere a avere a disposizione i valori delle coordinate della BFS del nuovo problema, è necessario che:
$$
y_{ij}=0 \quad \forall i,j:A_j\in\mathcal{B},i\neq j
$$
Condizione vera per ogni valore tranne $y_{06}$ che provvediamo ad annullare tramite l'operazione elementare di riga:
$$
R_0\leftarrow R_0 - R_2
$$
Nel nuovo tableau in figura \vref{tab:tab43} faremo pivoting sull'unica colonna con $\OL{c_j}<0$, cioè su $A_1$.
Per scegliere su quale elemento fare \textbf{pivoting}, dobbiamo ottenere il valore di $y_{\ell 1}$ tale che:
$$
\vartheta_{\max}=\min_{i:y_{i1}>0}\frac{y_{i0}}{y_{i1}}=\frac{y_{i0}}{y_{\ell 1}}
$$
Perciò, operando con gli elementi nel tableau:
$$
\vartheta_{\max}=\min\left(\frac{8}{1},\frac{1}{1},\frac{6}{1}\right)=\frac{1}{1}=\frac{y_{20}}{\pmb{y_{21}}}
$$
Faremo pivoting sull'elemento $y_{21}$ (cerchiato in tabella). Il nostro scopo è ora far comparire uno 0 nella colonna dell'elemento pivot in tutte le righe tranne quella in cui si trova l'elemento pivot e far comparire un 1 in quest'ultima.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-1} 	& -1 	& 1 	& 0 	& 1 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{8} 	& 1		& 1 	& 1 	& 0 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{1} 	& \C{1} & -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{6} 	& 1 	& 0 	& 0 	& 0 	& \Sc{1}& 0 \\
\end{tabular}
\caption{Pivoting su $y_{21}$. $A_1$ entra in base e $A_6$ esce.}
\label{tab:tab43}
\end{table}
Poiché $y_{21}=1$ non c'è nulla da fare su $R_2$. Applichiamo le operazioni elementari di riga al nostro tableau come segue:
\begin{align*}
R_0&\leftarrow R_0 + R_2; \\
R_1&\leftarrow R_1 - R_2; \\
R_3&\leftarrow R_3 - R_2.
\end{align*}
Il nostro nuovo tableau diventa quindi quello in tabella \vref{tab:tab44}.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{7} 	& 0		& 2 	& 1 	& 1 	& \Sc{0}& -1 \\
$R_2$ & $x_1$ 		& \Sc{1} 	& 1		& -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{5} 	& 0 	& 1 	& 0 	& 1 	& \Sc{1}& -1 \\
\end{tabular}
\caption{Secondo tableau. Vertice $\alpha(1,0)$}
\label{tab:tab44}
\end{table}
Siamo giunti alla soluzione ottima, essendo $\OL{c_j}>0 \quad\forall j$. Inoltre la variabile artificiale $x^a$ non è più in base. La nuova base e la nuova soluzione sono:
\begin{align*}
\mathcal{B}&=\{A_3,A_1,A_5\} \\
x&=(1,0,7,0,5,0)
\end{align*}
Siamo nel vertice $\alpha(1,0)$ e quindi in una BFS da cui possiamo partire per la \textbf{fase 2} del metodo del simplesso.
\subsubsection{Fase 2 - Simplesso}
Per questa fase useremo come tableau di partenza quello in tabella \vref{tab:tab44} sostituendo la funzione obiettivo fittizia $\psi$ utilizzata in precedenza con la nostra vera funzione obiettivo $\varphi$. Manterremo la variabile artificiale (che si fa notare non cambia in alcun modo il nostro problema in quanto non faremo mai entrare in base) perché, come vedremo poi, il suo costo relativo finale sarà utile ai fini della soluzione del problema duale.
Il tableau così ottenuto è quello in tabella \vref{tab:tab45}
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& -1 	& -1 	& 0 	& 0 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{7} 	& 0		& 2 	& 1 	& 1 	& \Sc{0}& -1 \\
$R_2$ & $x_1$ 		& \Sc{1} 	& 1		& -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{5} 	& 0 	& 1 	& 0 	& 1 	& \Sc{1}& -1 \\
\end{tabular}
\caption{Secondo tableau. Vertice $\alpha(1,0)$ e funzione obiettivo $\varphi$.}
\label{tab:tab45}
\end{table}
Per applicare il simplesso, dobbiamo fare in modo che:
$$
y_{ij}=0 \quad\forall i,j:j\in\mathcal{B}, i\neq j
$$
L'elemento $y_{01}$ è l'unico a non essere nullo. Ovviamo al problema con l'operazione di riga:
$$
R_0\leftarrow R_0 + R_1
$$
Otteniamo quindi il tableau in tabella \vref{tab:tab46}.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{1} 	& 0 	& -2 	& 0 	& -1 	& \Sc{0}& 1\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{7} 	& 0		& 2 	& 1 	& 1 	& \Sc{0}& -1 \\
$R_2$ & $x_1$ 		& \Sc{1} 	& 1		& -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{5} 	& 0 	& 1 	& 0 	& 1 	& \Sc{1}& -1 \\
\end{tabular}
\caption{Secondo tableau. Vertice $\alpha(1,0)$}
\label{tab:tab46}
\end{table}
Per fare pivoting sceglieremo la colonna $A_2$ in base alla regola di Bland (avremmo scelto la stessa colonna anche con la regola di Dantzig). Cerchiamo quindi l'elemento pivot $y_{\ell 2}$.
\begin{align*}
\vartheta_{\max}&=\min_{i:y_{i2}>0}\frac{y_{i0}}{y_{i2}}=\frac{y_{i0}}{y_{\ell 2}} \\
\vartheta_{\max}&=\min\left(\frac{7}{2},\frac{5}{1}\right)=\frac{7}{2}=\frac{y_{10}}{\pmb{y_{12}}}
\end{align*}
Faremo pivoting sull'elemento $y_{12}$ (cerchiato in tabella \vref{tab:tab47}).
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{1} 	& 0 	& -2 	& 0 	& -1 	& \Sc{0}& 1\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{7} 	& 0		& \C{2}	& 1 	& 1 	& \Sc{0}& -1 \\
$R_2$ & $x_1$ 		& \Sc{1} 	& 1		& -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{5} 	& 0 	& 1 	& 0 	& 1 	& \Sc{1}& -1 \\
\end{tabular}
\caption{Terzo tableau. Vertice $\alpha(1,0)$}
\label{tab:tab47}
\end{table}
Le operazioni elementari di riga, \textbf{in ordine}, sono:
\begin{align*}
R_0&\leftarrow R_0 + R_1 \\
R_1&\leftarrow \frac{R_1}{2} \\
R_2&\leftarrow R_2 + R_1 \\
R_3&\leftarrow R_3 - R_1
\end{align*}
Otterremo il tableau in tabella \vref{tab:tab48}.
\begin{table}[htbp]
\centering
{
	\newcommand{\sm}{$\frac{7}{2}$}
	\newcommand{\nm}{$\frac{9}{2}$}
	\newcommand{\um}{$\frac{1}{2}$}
	\newcommand{\tm}{$\frac{3}{2}$}
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{8} 	& 0 	& 0 	& 1 	& 0 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_2$ 		& \Sc{\sm}	& 0		& 1		& \um 	& \um 	& \Sc{0}& -\um \\
$R_2$ & $x_1$ 		& \Sc{\nm} 	& 1		& 0		& \um	& -\um 	& \Sc{0}& \um \\
$R_3$ & $x_5$ 		& \Sc{\tm}	& 0 	& 0 	& -\um 	& \um 	& \Sc{1}& -\um \\
\end{tabular}
}
\caption{Quarto tableau. Vertice $\beta(\frac{9}{2},\frac{7}{2})$. $A_2$ entra in base al posto di $A_3$, che esce.}
\label{tab:tab48}
\end{table}

Siamo giunti alla soluzione ottima, essendo $\OL{c_j}>0 \quad\forall j$. La nuova base e la nuova soluzione sono:
\begin{align*}
\mathcal{B}&=\{A_2,A_1,A_5\} \\
x&=\left(\frac{9}{2},\frac{7}{2},0,0,\frac{3}{2}\right)
\end{align*}
Siamo nel vertice $\beta(\frac{9}{2},\frac{7}{2})$ ed appartiene, come previsto durante l'analisi geometrica, allo spigolo $\OL{\beta\gamma}$. Il valore della soluzione ottima è $\varphi=-8$, proviamo ora a calcolare il valore della soluzione con il vertice $\gamma(6,2)$:
$$
\varphi(6,2)=-6-2=-8
$$
Anche il vertice $\gamma$ è una soluzione ottima del nostro problema. Da ciò possiamo desumere che l'intero spigolo $\OL{\beta\gamma}$ è composto da infinite soluzioni ottime. D'altronde, spostandoci lungo $\OL{\beta\gamma}$ avanzeremo in direzione perpendicolare al gradiente della funzione obiettivo e il valore della soluzione non può cambiare.
Si fa notare infine che la nostra funzione obiettivo iniziale è:
$$
z=-\varphi=8
$$

\subsection{Soluzione del problema primale}
La soluzione ottima consiste nel produrre $4.5$T di composto A e $3.5$T di composto B ottenendo un profitto pari a 8 volte quello di $1$T di composto A (o di composto B, equivalentemente).

\subsection{Costruzione del problema duale}
Riportiamo, per comodità, il problema primale espresso in forma standard.
\begin{alignat*}{7}
&\min \varphi = \quad && -x_1 \quad\; && -x_2 \quad\;\; && \qquad\qquad && \qquad\qquad && \qquad\qquad && \\
&\;\st  &&+x_1			&&+x_2	 		&&+\pmb{x_3}	&&		 		&&					&&=8\\
&	 	&&+x_1			&&-x_2			&&				&& -\pmb{x_4}	&&					&&=1\\
&	 	&&+x_1			&&				&&				&&				&&+\pmb{x_5}		&&=6\\
&		&&\quad\; x_1,	&&\quad\; x_2,	&&\quad\; x_3,	&&\quad\; x_4,	&&\quad\; x_5		&&\geq 0
\end{alignat*}
Ricordiamo che le regole base per la creazione del problema duale (considereremo solo quelle in grassetto nel caso di problemi primali in forma standard):
\begin{itemize}
\item \textbf{Ad ogni vincolo corrisponde una variabile duale};
\item \textbf{Ad ogni vincolo di uguaglianza, la rispettiva variabile duale è una variabile libera};
\item Ad ogni vincolo di non minoranza corrisponde una variabile duale non negativa;
\item \textbf{Ad ogni variabile non negativa nel primale corrisponde un vincolo con relazione di non maggioranza nel duale};
\item Ad ogni variabile libera nel primale corrisponde un vincolo di uguaglianza nel duale.
\end{itemize}
In dettaglio, ridefiniamo in questo modo il generico problema primale in forma standard:
\begin{align*}
\min c'x& \\
Ax& = b \\
x& \geq 0
\end{align*}
Sia $\pi$ il vettore delle variabili duali, il problema duale è il seguente:
\begin{align*}
\max \pi'b& \\
\pi'A& \leq c' \\
\pi'&\gtreqless 0
\end{align*}
Ove, i vettori $x,\pi,b,c$ e la matrice $A$ sono:
\begin{align*}
x'&=
\begin{bmatrix}
x_1 & x_2 & x_3 & x_4 & x_5
\end{bmatrix} \\
\pi'&=
\begin{bmatrix}
\pi_1 & \pi_2 & \pi_3
\end{bmatrix} \\
b'&=
\begin{bmatrix}
8 & 1 & 6
\end{bmatrix} \\
c'&=
\begin{bmatrix}
-1 & -1 & 0 & 0 & 0
\end{bmatrix} \\
A&=
\begin{bmatrix}
1  & 1  & 1  & 0  & 0 \\
1  & -1 & 0  & -1 & 0 \\
1  & 0  & 0  & 0  & 1 \\
\end{bmatrix}
\end{align*}
Da ciò, il corrispondente problema duale con la sua funzione obiettivo $\xi$:
\begin{alignat*}{7}
&\max \xi = \quad && +8\pi_1 \quad\; && +\pi_2 \quad\;\; && +6\pi_3 \quad\;\; && \\
&\;\st  &&+\pi_1		&&+\pi_2 		&&+\pi_3		&& \leq -1\\
&	 	&&+\pi_1		&&-\pi_2 		&&				&& \leq -1\\
&	 	&&+\pi_1		&&				&&				&& \leq 0 \\
&	 	&&				&&-\pi_2		&&				&& \leq 0 \\
&	 	&&				&&				&&+\pi_3		&& \leq 0 \\
&		&&\quad\;\pi_1,	&&\quad\;\pi_2,	&&\quad\;\pi_3,	&& \gtreqless 0
\end{alignat*}
Per trovare la soluzione del problema duale non è necessario trasformarlo in forma standard e applicare il metodo del simplesso. Il tableau del problema primale sul quale abbiamo applicato il metodo del simplesso contiene tutte le informazioni per avere la soluzione del problema duale.
\subsubsection{Richiami (sempre molto blandi) di teoria}
Per ottenere dal tableau del problema primale la soluzione del problema duale, è sufficiente ricordare che il problema duale è ottenuto a partire dal \textbf{criterio di ottimalità}.
Per questo motivo, il costo relativo nel tableau finale - corrispondente alla soluzione ottima - è così esprimibile:
$$
\OL{c_j}=c_j-z_j=c_j-\pi'A_j \quad \forall j
$$
Se consideriamo le colonne $A_j$ corrispondenti alla base iniziale $\mathcal{B}_0$ di partenza del primo tableau - ricordando che è una matrice identità - possiamo ottenere:
$$
\OL{c_j}=c_j-\pi_j \quad \forall j:A_j\in\mathcal{B}_0
$$
Applicando un semplice passaggio algebrico:
$$
\pi_j=c_j-\OL{c_j}
$$
Ove $c_j$ è il costo iniziale nel primo tableau e $\OL{c_j}$ il costo relativo nel tableau finale.
Nel caso in cui abbiamo fatto uso di variabili artificiali e della fase 1 del metodo del simplesso, allora per tale variabile - il cui costo è $c_j=0$ - vale:
$$
\pi_j=-\OL{c_j}
$$
\textit{È importante ricordare che bisogna utilizzare il primo tableau con le variabili artificiali ma con il vettore dei costi originario in cui le variabili artificiali hanno costo nullo.}
\subsection{Soluzione del problema duale}
Riportiamo nuovamente i tableau iniziale e finale rispettivamente nelle tabella \vref{tab:tab49} e \vref{tab:tab410}.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& -1 	& -1 	& 0 	& 0 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{8} 	& 1		& 1 	& 1 	& 0 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{1} 	& 1		& -1	& 0 	& -1 	& \Sc{0}& 1 \\
$R_3$ & $x_5$ 		& \Sc{6} 	& 1 	& 0 	& 0 	& 0 	& \Sc{1}& 0 \\
\end{tabular}
\caption{Tableau iniziale.}
\label{tab:tab49}
\end{table}
\begin{table}[htbp]
\centering
{
	\newcommand{\sm}{$\frac{7}{2}$}
	\newcommand{\nm}{$\frac{9}{2}$}
	\newcommand{\um}{$\frac{1}{2}$}
	\newcommand{\tm}{$\frac{3}{2}$}
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{8} 	& 0 	& 0 	& 1 	& 0 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_2$ 		& \Sc{\sm}	& 0		& 1		& \um 	& \um 	& \Sc{0}& -\um \\
$R_2$ & $x_1$ 		& \Sc{\nm} 	& 1		& 0		& \um	& -\um 	& \Sc{0}& \um \\
$R_3$ & $x_5$ 		& \Sc{-\tm}	& 0 	& 0 	& -\um 	& \um 	& \Sc{1}& -\um \\
\end{tabular}
}
\caption{Tableau finale.}
\label{tab:tab410}
\end{table}
La base iniziale è $\mathcal{B}_1={A_3,A_6,A_5}$. Applicando delle semplici sottrazioni, ricaviamo la soluzione del problema duale:
\begin{align*}
\pi_1&=c_3-\OL{c_3}=-1 \\
\pi_2&=c_6-\OL{c_6}=0 \\
\pi_3&=c_5-\OL{c_5}=0
\end{align*}
Perciò, la soluzione del problema duale è il vettore:
$$
\pi'=
\begin{bmatrix}
-1 & 0 & 0
\end{bmatrix}
$$
Per verificare la correttezza dei calcoli, applichiamo la soluzione alla funzione obiettivo del problema duale:
$$
\xi(-1,0,0)=8(-1)+0+6(0)=-8
$$
Il risultato è, come atteso, lo stesso del problema primale.

\subsection{Vincolo di interezza}\label{sec:es4ILP}

\textit{Sezione in fase di allestimento...ci rivediamo appena il prof. spiegherà i metodi per la ILP}.

\section{Esercizio 5}

Sia dato il seguente modello matematico di un problema di LP:
\begin{align*}
\min z	&= 2x_1+x_2 \\
\st\;\;	& x_1+x_2 \leq 2\\
		& 2x_1+3x_2\geq 6\\
	  	& x_1,x_2 \geq 0
\end{align*}
\begin{itemize}
\item Si rappresenti accuratamente il problema in forma grafica;
\item Si ricavi la forma standard;
\item Si risolva il problema tramite il metodo del simplesso a due fasi utilizzando il minor numero di variabili artificiali.
\end{itemize}

\subsection{Problema in forma grafica}

In figura \vref{fig:graph5} è rappresentato graficamente il problema presentato. Il vertice $\alpha$ è l'unico punto di intersezione tra le aree del problema.
Il gradiente della funzione obiettivo vale
\begin{equation*}
\nabla(z)=\left(\frac{\partial z}{\partial x},\frac{\partial z}{\partial y}\right) = \left(2,1\right) \\
\end{equation*}
Poiché questa volta il problema è rappresentato sotto forma di minimo, saremo interessati alla limitazione del politopo nella direzione \textbf{opposta} al gradiente. A tal fine utilizziamo una funzione obiettivo ausiliaria $\varphi$ tale che:
\begin{equation*}
\varphi = -z \Rightarrow \nabla\varphi = -\nabla z = (-2,-1)
\end{equation*}
In realtà, della direzione ci importa poco, dato che esiste un solo punto di intersezione.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}
\begin{axis}
[axis lines=middle, axis equal, enlargelimits, xlabel=$x_1$, ylabel=$x_2$,
 every axis x label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=west,
 },
 every axis y label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=south,
 },xtick={1,2,3}]
    \path[name path=AX]
        (axis cs:\pgfkeysvalueof{/pgfplots/xmin},0)--
        (axis cs:\pgfkeysvalueof{/pgfplots/xmax},0);
    \path[name path=AY]
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymin})--
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymax});
    \path[name path=UP]
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmin},\pgfkeysvalueof{/pgfplots/ymax})--
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmax},\pgfkeysvalueof{/pgfplots/ymax});

%\foreach \q in {1,...,6} {
%	\ifthenelse{\q < 2}{\newcommand{\x}{2}}{\newcommand{\x}{\q}}
%	\addplot [domain=(\x/2)-1:(\q/2), samples=10, ultra thin, purple] {-2*x+\q};
%	}

\addplot
[domain=0:2.01, samples=10, thick, blue, name path=xy2]
{-x+2} node [pos=0.2,pin={75:{\color{blue}$x_1+x_2=2$}}, inner sep=0pt] {};

\addplot
[domain=0:3.01, samples=10, thick, red, name path=2x3y6]
{-(2/3)*x+2} node [pos=0.5, pin={75:{\color{red}$2x_1+3x_2=6$}}, inner sep=0pt] {};
%\addplot[thick, fill=yellow, fill opacity=0.5] fill between [of=2x3y6 and AX];
%\addplot[white] fill between [of=xy2 and AX];
%\addplot[pattern=north east lines, pattern color=red!10] fill between [reverse=true, of=AX and UP, soft clip={domain=0:5}];
%\addplot[pattern=north east lines, pattern color=blue!10] fill between [of=xy2 and UP];
%\addplot[pattern=vertical lines, pattern color=red!10] fill between [of=2x3y6 and AX];
\intne{AY}{xy2}{$\alpha$}{alp};
%\intne{AX}{2x3y6}{$\beta$}{bet};
%\intne{xy2}{AX}{$\gamma$}{gam};
%\node at (axis cs:1.8,0.5) {$P$};
\addplot[-latex, thick] coordinates
           {(2/2.236,1/2.236) (0,0)} node [pos=.3, anchor=south, label={45:{\small $\nabla\varphi$}}] {};
\end{axis}
\end{tikzpicture}
\caption{Rappresentazione cartesiana del problema di programmazione lineare}
\label{fig:graph5}
\end{figure}

\subsection{Forma standard}

Aggiungendo una variabile slack e una variabile surplus, il problema in forma standard si presenta così:
\begin{alignat*}{6}
&\min z = \quad && +2x_1 \quad\; && +x_2 \quad\;\; && \qquad\qquad && \qquad\qquad && \\
&\;\st  &&+x_1			&&+x_2	 		&&+\pmb{x_3}	&&		 		&&=2\\
&	 	&&+2x_1			&&+3x_2			&&				&& -\pmb{x_4}	&&=6\\
&		&&\quad\; x_1,	&&\quad\; x_2,	&&\quad\; x_3,	&&\quad\; x_4,	&&\geq 0
\end{alignat*}

\subsection{Risoluzione tramite tableau}

\begin{table}[htbp]
\centering
\begin{tabular}{rccccc}
			&$-z$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
$\OL{c_j}$ 	& \Sc{0} 	& 2 	& 1 	& 0 	& 0 \\
\cline{2-6}
$R_1$ 		& \Sc{2} 	& 1 	& 1 	& 1 	& 0\\
$R_2$		& \Sc{6} 	& 2 	& 3		& 0 	& -1 \\
\end{tabular}
\caption{Tableau iniziale.}
\label{tab:tab51}
\end{table}

In tabella \vref{tab:tab51} il tableau ricavato dal nostro problema. Non abbiamo nessuna sottomatrice identità a disposizione da utilizzare come base ammissibile quindi ricorriamo alla \textbf{fase 1 del metodo del simplesso} per ottenere una BFS di partenza.

\subsubsection{Fase 1 - aggiunta di variabili artificiali}

Manca solo la seconda colonna della matrice identità con cui formare la BFS di partenza e la che introdurremo con l'\textit{unica} variabile artificiale $x^a$, trasformando il secondo vincolo in:
$$
2x_1 + 3x_2 - x_4 + x^a = 6
$$
Il nostro scopo, dopo l'introduzione di $x^a$, sarà quello di \textbf{eliminarla} dalla base. Per far ciò bisogna fare in modo che questa valga zero e quindi introduciamo, a tale scopo, una nuova funzione obiettivo da minimizzare $\psi$ tale che:
$$
\psi = \sum_{i=1}^{n'}x_i^a = x^a
$$
Scriviamo il nuovo tableau in tabella \vref{tab:tab52} e applichiamo il simplesso per ottimizzare la nostra funzione $\psi$.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-8}
$R_1$ & $x_3$ 		& \Sc{2} 	& 1		& 1 	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{6} 	& 2		& 3		& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Nuovo tableau con la variabile artificiale $x^a$.}
\label{tab:tab52}
\end{table}
Abbiamo una sottomatrice identità formata dalla base:
$$
\mathcal{B}=\{A_3,A_5\}
$$
Per avere a avere a disposizione i valori delle coordinate della BFS del nuovo problema, è necessario che:
$$
y_{ij}=0 \quad \forall i,j:A_j\in\mathcal{B},i\neq j
$$
Condizione vera per ogni valore tranne $y_{05}$ che provvediamo ad annullare tramite l'operazione elementare di riga:
$$
R_0\leftarrow R_0 - R_2
$$
Nel nuovo tableau in figura \vref{tab:tab53} dobbiamo scegliere su quale colonna fare pivoting. Dato che la traccia non ci specifica nulla sulla regola da utilizzare \footnote{Oppure non ricordo se era stato specificato dal tutor all'inizio dell'esercizio durante la lezione [NdA]} applicheremo la regola di Dantzig e sceglieremo la colonna con il $\OL{c_j}$ più negativo, cioè $A_2$.
Per scegliere su quale elemento fare \textbf{pivoting}, dobbiamo ottenere il valore di $y_{\ell 2}$ tale che:
$$
\vartheta_{\max}=\min_{i:y_{i2}>0}\frac{y_{i0}}{y_{i2}}=\frac{y_{i0}}{y_{\ell 2}}
$$
Perciò, operando con gli elementi nel tableau:
$$
\vartheta_{\max}=\min\left(\frac{2}{1},\frac{6}{3}\right)
$$
Abbiamo un pareggio. Applichiamo ora la regola di Bland per risolvere il pareggio, scegliendo tra gli elementi su cui fare pivot quello con l'indice di riga minore:
$$
\vartheta_{\max}=\frac{2}{1}=\frac{y_{10}}{\pmb{y_{12}}}
$$
Faremo pivoting sull'elemento $y_{12}$ (cerchiato in tabella). Il nostro scopo è ora far comparire uno 0 nella colonna dell'elemento pivot in tutte le righe tranne quella in cui si trova l'elemento pivot e far comparire un 1 in quest'ultima.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-6} 	& -2 	& -3 	& 0 	& \Sc{1}& 0\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{2} 	& \C{1}	& 1 	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{6} 	& 2		& 3		& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Pivoting su $y_{12}$. $A_2$ entra in base e $A_3$ esce.}
\label{tab:tab53}
\end{table}
Poiché $y_{12}=1$ non c'è nulla da fare su $R_1$. Applichiamo le operazioni elementari di riga al nostro tableau come segue:
\begin{align*}
R_0&\leftarrow R_0 + 3R_1; \\
R_2&\leftarrow R_2 - 3R_1.
\end{align*}
Il nostro nuovo tableau diventa quindi quello in tabella \vref{tab:tab54}.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 1 	& 0 	& 3 	& \Sc{1}& 0\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{2} 	& 1		& 1 	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{0} 	& -1	& 0		&\C{-3}	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Secondo tableau. $x^a$ ancora in base.}
\label{tab:tab54}
\end{table}
Siamo giunti alla soluzione ottima, ma non è ancora sufficiente. Possiamo osservare, infatti, che $x_3$ è subentrata in base al posto di $x_2$ e che quindi $x^a$ è ancora in base e noi non lo vogliamo. Se il problema fosse risolvibile dovrebbe esserlo \textit{a prescindere} dalla variabile artificiale, cioè dovremmo essere in grado di trovare una soluzione a questo tableau con $x^a$ fuori base.
Non tutto è ancora perduto. Osserviamo che la base in cui ci troviamo ora è \textbf{degenere}, e possiamo fare entrare al posto di $x^a$ una qualsiasi altra variabile senza creare problemi. Qualsiasi operazione elementare di riga, in tal caso, non apporterebbe modifiche al valore di $-\psi$ e rimarremmo comunque in basi ottime.
Possiamo fare pivot su qualsiasi elemento di $R_2$ purché non sia nullo (e purché non sia la stessa variabile artificiale, ovviamente). Questa volta sceglieremo $y_{23}$, consapevoli che sarebbero andati bene anche $y_{21}$ e $y_{24}$.
Applichiamo le operazioni elementari di riga, \textbf{nell'ordine}, per completare l'operazione di pivoting:
\begin{align*}
R_0&\leftarrow R_0 + R_2 \\
R_2&\leftarrow \frac{1}{3}R_2 \\
R_1&\leftarrow R_1 + R_2
\end{align*}
Otteniamo il tableau in tabella \vref{tab:tab55}. È ancora un tableau ottimo (non poteva essere diversamente) e questa volta nessuna fastidiosa variabile artificiale è in base.
\begin{table}[htbp]
\centering
{
	\newcommand{\ut}{$\frac{1}{3}$}
	\newcommand{\dt}{$\frac{2}{3}$}
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{2} 	& \dt	& 1 	& 0 	&\Sc{-\ut}& \ut \\
$R_2$ & $x^3$ 		& \Sc{0} 	& -\ut	& 0		& 1 	&\Sc{-\ut}& 0 \\
\end{tabular}
}
\caption{Terzo tableau. $A_3$ entra in base al posto di $A_5$. Vertice $\alpha(0,2)$}
\label{tab:tab55}
\end{table}
La nuova base e la nuova soluzione sono:
\begin{align*}
\mathcal{B}&=\{A_2,A_3\} \\
x&=(0,2,0,0,0)
\end{align*}
Siamo nel vertice $\alpha(0,2)$ e quindi in una BFS da cui possiamo partire per la \textbf{fase 2} del metodo del simplesso.
\subsubsection{Fase 2 - Simplesso}
Per questa fase useremo come tableau di partenza quello in tabella \vref{tab:tab55} sostituendo la funzione obiettivo fittizia $\psi$ utilizzata in precedenza con la nostra vera funzione obiettivo $z$. Manterremo la variabile artificiale (che si fa notare non cambia in alcun modo il nostro problema in quanto non faremo mai entrare in base) perché, come vedremo poi, il suo costo relativo finale sarà utile ai fini della soluzione del problema duale.
Il tableau così ottenuto è quello in tabella \vref{tab:tab56}
\begin{table}[htbp]
\centering
{
	\newcommand{\ut}{$\frac{1}{3}$}
	\newcommand{\dt}{$\frac{2}{3}$}
\begin{tabular}{rrcccccc}
 	  & 			&$-z$		& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 2 	& 1 	& 0 	& \Sc{0}& 0\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{2} 	& \dt	& 1 	& 0 	&\Sc{-\ut}& \ut \\
$R_2$ & $x^3$ 		& \Sc{0} 	& -\ut	& 0		& 1 	&\Sc{-\ut}& 0 \\
\end{tabular}
}
\caption{Quarto tableau. Vertice $\alpha(0,2)$}
\label{tab:tab56}
\end{table}
Per applicare il simplesso, dobbiamo fare in modo che:
$$
y_{ij}=0 \quad\forall i,j:j\in\mathcal{B}, i\neq j
$$
L'elemento $y_{02}$ è l'unico a non essere nullo. Ovviamo al problema con l'operazione di riga:
$$
R_0\leftarrow R_0 - R_1
$$
Otteniamo quindi il tableau in tabella \vref{tab:tab57}.
\begin{table}[htbp]
\centering
{
	\newcommand{\ut}{$\frac{1}{3}$}
	\newcommand{\dt}{$\frac{2}{3}$}
	\newcommand{\qt}{$\frac{4}{3}$}
\begin{tabular}{rrcccccc}
 	  & 			&$-z$		& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-2} 	& \qt 	& 0 	& 0 	&\Sc{\ut} & -\ut\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{2} 	& \dt	& 1 	& 0 	&\Sc{-\ut}& \ut \\
$R_2$ & $x^3$ 		& \Sc{0} 	& -\ut	& 0		& 1 	&\Sc{-\ut}& 0 \\
\end{tabular}
}
\caption{Quarto tableau. Vertice $\alpha(0,2)$}
\label{tab:tab57}
\end{table}
Il nostro lavoro si conclude qui in quanto $\OL{c_j}>0\quad\forall j>0$ e il vertice $\alpha$ è già quello della soluzione ottima, come d'altronde previsto durante la soluzione per via grafica (si tratta dell'\textit{unico} punto della regione ammissibile). La base e la soluzione sono quelle già espresse in precedenza:
\begin{align*}
\mathcal{B}&=\{A_2,A_3\} \\
x&=(0,2,0,0,0)
\end{align*}

\subsection{Soluzione del problema}
La soluzione del problema è:
$$
z(\alpha)=z(0,2)=2
$$

\subsection{Extra - Costruzione del problema duale}
Anche se nessuno ce l'ha chiesto, proviamo a costruire e risolvere il problema duale a quello dato.
Riportiamo ora il problema primale e, per motivi di sintesi, poniamo anche una notazione più breve che ci permetterà di costruire il problema duale:
$$
{
	\renewcommand*\arraystretch{.7}
\begin{array}{r| @{}c@{} |c| @{}c@{} |c| @{}c@{}|c| @{}c@{} |c| c|}
\cline{2-2}\cline{4-4}\cline{6-6}\cline{8-8}\cline{10-10}
	 &\qquad\qquad& &\qquad\qquad& &\qquad\qquad& &\qquad\qquad& & \\
\min		& 2x_1 	&+& x_2 	& &   		& &   		& & \CG{\max}\\
	 		&\CG{=}	& &\CG{=}	& &\CG{=}	& &\CG{=}	& & 	\\
\CG{\pi_1}	& x_1	&+& x_2 	&+& x_3 	& &			&=& 2 	\\
	 		&\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{+}	& & 	\\
\CG{\pi_2}	& 2x_1 	&+&3x_2 	& &			&-& x_4		&=& 6	\\
	 		&  		& &  		& &	  		& &   		& & 	\\
\cline{2-2}\cline{4-4}\cline{6-6}\cline{8-8}\cline{10-10}
	 		&  		& &  		& &	  		& &   		& & 	\\
	 		& x_1	&,& x_2 	&,& x_3 	&,& x_4 	&\geq& 0\\
	 		&  		& &  		& &	  		& &   		& & 	\\
\cline{2-2}\cline{4-4}\cline{6-6}\cline{8-8}\cline{10-10}
\end{array}
}
$$
Ricordando che \textit{ad ogni variabile non negativa corrisponde un vincolo duale di non maggioranza}, il problema duale, perciò, è il seguente:
\begin{alignat*}{6}
&\max \xi = \quad && +2\pi_1 \quad\; && +6\pi_2 \quad\;\; && \\
&\;\st  &&+\pi_1		&&+2\pi_2 		&& \leq 2 \\
&	 	&&+\pi_1		&&+3\pi_2 		&& \leq 1\\
&	 	&&+\pi_1		&&				&& \leq 0 \\
&	 	&&				&&-\pi_2		&& \leq 0 \\
&		&&\quad\;\pi_1,	&&\quad\;\pi_2,	&& \gtreqless 0
\end{alignat*}

\subsection{Extra - Soluzione del problema duale}
Riportiamo i tableau iniziale e finale con i quali abbiamo applicato l'algoritmo del simplesso.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 2 	& 1 	& 0 	& \Sc{0}& 0\\
\cline{3-8}
$R_1$ & $x_3$ 		& \Sc{2} 	& 1		& 1 	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{6} 	& 2		& 3		& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Tableau iniziale con la \textit{funzione obiettivo originaria}.}
\label{tab:tab58}
\end{table}
\begin{table}[htbp]
\centering
{
	\newcommand{\ut}{$\frac{1}{3}$}
	\newcommand{\dt}{$\frac{2}{3}$}
	\newcommand{\qt}{$\frac{4}{3}$}
\begin{tabular}{rrcccccc}
 	  & 			&$-z$		& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-2} 	& \qt 	& 0 	& 0 	&\Sc{\ut} & -\ut\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{2} 	& \dt	& 1 	& 0 	&\Sc{-\ut}& \ut \\
$R_2$ & $x^3$ 		& \Sc{0} 	& -\ut	& 0		& 1 	&\Sc{-\ut}& 0 \\
\end{tabular}
}
\caption{Tableau finale.}
\label{tab:tab59}
\end{table}
La base iniziale è $\mathcal{B}_1={A_3,A_5}$. Applicando delle semplici sottrazioni, ricaviamo la soluzione del problema duale:
\begin{align*}
\pi_1&=c_3-\OL{c_3}=0 \\
\pi_3&=c_5-\OL{c_5}=\frac{1}{3}
\end{align*}
Perciò, la soluzione del problema duale è il vettore:
$$
\pi'=
\begin{bmatrix}
0 & \frac{1}{3}
\end{bmatrix}
$$
Per verificare la correttezza dei calcoli, applichiamo la soluzione alla funzione obiettivo del problema duale:
$$
\xi(0,\frac{1}{3})=2(0)+0+6(\frac{1}{3})=2
$$
Il risultato è, come atteso, lo stesso del problema primale.

\section{Esercizio 6}

Sia dato il seguente modello matematico di un problema di LP:
\begin{align*}
\min z	&= -x_1-x_2 \\
\st\;\;	& x_2 \leq 1\\
		& -x_1+x_2\geq 2\\
	  	& x_1,x_2 \geq 0
\end{align*}
\begin{itemize}
\item Si rappresenti accuratamente il problema in forma grafica;
\item Si ricavi la forma standard;
\item Si risolva il problema tramite il metodo del simplesso a due fasi utilizzando il minor numero di variabili artificiali.
\end{itemize}

\subsection{Problema in forma grafica}

In figura \vref{fig:graph6} è rappresentato graficamente il problema presentato. Il gradiente della funzione obiettivo vale:
\begin{equation*}
\nabla(z)=\left(\frac{\partial z}{\partial x},\frac{\partial z}{\partial y}\right) = \left( -1,-1 \right) \\
\end{equation*}
Poiché questa volta il problema è rappresentato sotto forma di minimo, saremo interessati alla limitazione del politopo nella direzione \textbf{opposta} al gradiente. A tal fine utilizziamo una funzione obiettivo ausiliaria $\varphi$ tale che:
\begin{equation*}
\varphi = -z \Rightarrow \nabla\varphi = -\nabla z = (-2,-1)
\end{equation*}
In giallo è rappresentata l'area tra i due vincoli lineari di disuguaglianza. Notiamo che quest'area si estende nel secondo e nel terzo quadrante, perciò non rispetta i vincoli di non minoranza delle singole variabili. Ci aspettiamo una soluzione impossibile dal simplesso.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}
\begin{axis}
[axis lines=middle, axis equal, enlargelimits, xlabel=$x_1$, ylabel=$x_2$,
 every axis x label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=west,
 },
 every axis y label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=south,
 },%xtick={1,2,3}
 ]
    \path[name path=AX]
        (axis cs:\pgfkeysvalueof{/pgfplots/xmin},0)--
        (axis cs:\pgfkeysvalueof{/pgfplots/xmax},0);
    \path[name path=AY]
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymin})--
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymax});
    \path[name path=UP]
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmin},\pgfkeysvalueof{/pgfplots/ymax})--
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmax},\pgfkeysvalueof{/pgfplots/ymax});

\addplot
[domain=-3.01:3.01, samples=10, thick, blue, name path=yx2]
{x+2} node [pos=0.6,pin={135:{\color{blue}$-x_1+x_2=2$}}, inner sep=0pt] {};
\addplot
[domain=-3.01:3.01, samples=10, thick, red, name path=y1]
{1} node [pos=0.5, pin={75:{\color{red}$x_2=1$}}, inner sep=0pt] {};
\addplot[thick, fill=yellow, fill opacity=0.5] fill between [of=yx2 and y1, soft clip={domain=-3:-1}];
%\addplot[white] fill between [of=xy2 and AX];
%\addplot[pattern=north east lines, pattern color=red!10] fill between [reverse=true, of=AX and UP, soft clip={domain=0:5}];
\addplot[pattern=north west lines, pattern color=blue!10] fill between [of=yx2 and UP];
\addplot[pattern=vertical lines, pattern color=red!10] fill between [of=y1 and AX];
\intne{y1}{yx2}{$\alpha$}{alp};
%\node at (axis cs:1.8,0.5) {$P$};
\addplot[-latex, thick] coordinates
           {(0,0) (1/1.414,1/1.414)} node [pos=.3, anchor=south, label={45:{\small $\nabla\varphi$}}] {};
\end{axis}
\end{tikzpicture}
\caption{Rappresentazione cartesiana del problema di programmazione lineare}
\label{fig:graph6}
\end{figure}

\subsection{Forma standard}

Aggiungendo una variabile slack e una variabile surplus, il problema in forma standard si presenta così:
\begin{alignat*}{6}
&\min z = \quad && -x_1 \quad\; && -x_2 \quad\;\; && \qquad\qquad && \qquad\qquad && \\
&\;\st  &&				&&+x_2	 		&&+\pmb{x_3}	&&		 		&&=1\\
&	 	&&-x_1			&&+x_2			&&				&& -\pmb{x_4}	&&=2\\
&		&&\quad\; x_1,	&&\quad\; x_2,	&&\quad\; x_3,	&&\quad\; x_4,	&&\geq 0
\end{alignat*}

\subsection{Risoluzione tramite tableau}

\begin{table}[htbp]
\centering
\begin{tabular}{rccccc}
			&$-z$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
$\OL{c_j}$ 	& \Sc{0} 	& -1 	& -1 	& 0 	& 0 \\
\cline{2-6}
$R_1$ 		& \Sc{1} 	& 0 	& 1 	& 1 	& 0\\
$R_2$		& \Sc{2} 	& -1 	& 1		& 0 	& -1 \\
\end{tabular}
\caption{Tableau iniziale.}
\label{tab:tab61}
\end{table}

In tabella \vref{tab:tab61} il tableau ricavato dal nostro problema. Non abbiamo nessuna sottomatrice identità a disposizione da utilizzare come base ammissibile quindi ricorriamo alla \textbf{fase 1 del metodo del simplesso} per ottenere una BFS di partenza.

\subsubsection{Fase 1 - aggiunta di variabili artificiali}

Manca solo la seconda colonna della matrice identità con cui formare la BFS di partenza e la introdurremo con l'\textit{unica} variabile artificiale $x^a$, trasformando il secondo vincolo in:
$$
-x_1 + x_2 - x_4 + x^a = 2
$$
Il nostro scopo, dopo l'introduzione di $x^a$, sarà quello di \textbf{eliminarla} dalla base. Per far ciò bisogna fare in modo che questa valga zero e quindi introduciamo, a tale scopo, una nuova funzione obiettivo da minimizzare $\psi$ tale che:
$$
\psi = \sum_{i=1}^{n'}x_i^a = x^a
$$
Scriviamo il nuovo tableau in tabella \vref{tab:tab62} e applichiamo il simplesso per ottimizzare la nostra funzione $\psi$.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-8}
$R_1$ & $x_3$ 		& \Sc{1} 	& 0		& 1 	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{2} 	& -1	& 1		& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Nuovo tableau con la variabile artificiale $x^a$.}
\label{tab:tab62}
\end{table}
Abbiamo una sottomatrice identità formata dalla base:
$$
\mathcal{B}=\{A_3,A_5\}
$$
Per avere a avere a disposizione i valori delle coordinate della BFS del nuovo problema, è necessario che:
$$
y_{ij}=0 \quad \forall i,j:A_j\in\mathcal{B},i\neq j
$$
Condizione vera per ogni valore tranne $y_{05}$ che provvediamo ad annullare tramite l'operazione elementare di riga:
$$
R_0\leftarrow R_0 - R_2
$$
Nel nuovo tableau in figura \vref{tab:tab63} dobbiamo scegliere su quale colonna fare pivoting. L'unica colonna con $\OL{c_j}<0$ è $A_2$ e cercheremo qui l'elemento pivot.
Per scegliere su quale elemento fare \textbf{pivoting}, dobbiamo ottenere il valore di $y_{\ell 2}$ tale che:
$$
\vartheta_{\max}=\min_{i:y_{i2}>0}\frac{y_{i0}}{y_{i2}}=\frac{y_{i0}}{y_{\ell 2}}
$$
Perciò, operando con gli elementi nel tableau:
$$
\vartheta_{\max}=\min\left(\frac{1}{1},\frac{2}{1}\right)=\frac{1}{1}=\frac{y_{10}}{\pmb{y_{12}}}
$$
Faremo pivoting sull'elemento $y_{12}$ (cerchiato in tabella). Il nostro scopo è ora far comparire uno 0 nella colonna dell'elemento pivot in tutte le righe tranne quella in cui si trova l'elemento pivot e far comparire un 1 in quest'ultima.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-2} 	& 1 	& -1 	& 0 	& \Sc{1}& 0\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{1} 	& 0		& \C{1}	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{2} 	& -1	& 1		& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Pivoting su $y_{12}$. $A_2$ entra in base e $A_3$ esce.}
\label{tab:tab63}
\end{table}
Poiché $y_{12}=1$ non c'è nulla da fare su $R_1$. Applichiamo le operazioni elementari di riga al nostro tableau come segue:
\begin{align*}
R_0&\leftarrow R_0 + R_1; \\
R_2&\leftarrow R_2 - R_1.
\end{align*}
Il nostro nuovo tableau diventa quindi quello in tabella \vref{tab:tab64}.
\begin{table}[htbp]
\centering
\begin{tabular}{rrcccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-1} 	& 1 	& 0 	& 1 	& \Sc{1}& 0\\
\cline{3-8}
$R_1$ & $x_2$ 		& \Sc{1} 	& 0		& 1 	& 1 	& \Sc{0}& 0 \\
$R_2$ & $x^a$ 		& \Sc{1} 	& -1	& 0		& -1	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Secondo tableau. $x^a$ ancora in base e $\psi\neq 0$.}
\label{tab:tab64}
\end{table}
Siamo nella soluzione ottima ma:
\begin{itemize}
\item la variabile artificiale $x^a$ è ancora fuori base;
\item la soluzione ottima non è nulla.
\end{itemize}
Non vale la pena sprecare energie per far uscire dalla base la variabile artificiale. Qualunque operazione facessimo, il valore della soluzione ottima non potrebbe migliorare e quindi non potrebbe annullarsi. Ciò significa che non esistono soluzioni ammissibili al nostro problema.
\subsection{Soluzione del problema}
Il problema non ha soluzione in quanto nella fase 1 del metodo del simplesso non siamo riusciti a trovare una BFS che non coinvolga variabili artificiali.
\section{Esercizio 7}
Un'azienda produce panchine per giardini di due tipi utilizzando plastica riciclata e ricevendo un contributo statale di 40\euro per ogni panchina di tipo 1 e 30\euro per ogni panchina di tipo 2. La vendita di ogni panchina di tipo 1 causa una perdita di 10\euro, mentre quella di ogni panchina di tipo 2 da un ricavo di 30\euro. I macchinari utilizzati hanno un limite produttivo di 300 panchine per ciascun tipo. L'azienda vuole ricevere almeno 12000\euro di contributi statali. Si esprimano i livelli di produzione in centinaia di panchine ed i quantitativi monetari in migliaia di euro.
\begin{enumerate}
\item Definire il modello LP che massimizza l'introito complessivo dato dalla sola vendita delle panchine.
\item Risolvere con il metodo delle due fasi (leggere prima il punto 5), introducendo il minor numero possibile di variabili artificiali. In caso di parità, fare uscire dalla base una variabile artificiale.
\item Dare esplicitamente la soluzione trovata.
\item Disegnare con cura la regione ammissibile e indicarvi le soluzioni corrispondenti a ciascun tableau.
\item Definire il duale della forma standard del modello del punto 1 e ricavarne la soluzione dai tableau prodotti.
\item Imporre l'ulteriore vincolo che debba essere prodotto un numero intero di centinaia di panchine. Risolvere con il metodo di Gomory. [\textit{Questo punto non sarà analizzato perché in data di stesura del documento (04/04/2014) l'argomento non è ancora stato trattato dal prof}]
\end{enumerate}

\subsection{Modellizzazione}

Si indichi con:
\begin{itemize}
\item $x_1$ il numero di centinaia di panchine di tipo 1;
\item $x_2$ il numero di centinaia di panchine di tipo 2.
\end{itemize}
Lo scopo del nostro problema è di massimizzare i profitti ottenuti \textbf{dalla sola vendita} delle panchine, quindi esclusi i contributi statali. Ricordiamo che le variabili indicano \textit{centinaia} di panchine e che l'introito sarà calcolato in \textit{migliaia} di euro. Facendo le opportune moltiplicazioni, la funzione di profitto sarà:
$$
\max z = -x_1 + 3x_2
$$
Modelliamo ora i vincoli espressi dal problema.
Il modello matematico può essere quindi così riassunto (sono state apportate semplificazione algebriche):
\begin{align*}
\max z	&= -x_1+3x_2 \\
\st\;\;	& x_1 \leq 3\\
		& x_1 \leq 3\\
		& 4x_1 + 3x_2 \geq 12 \\
	  	& x_1,x_2 \geq 0
\end{align*}

\subsection{Problema in forma grafica}

In figura \vref{fig:graph7} è rappresentato graficamente il problema presentato. Il gradiente della funzione obiettivo vale:
\begin{equation*}
\nabla(z)=\left(\frac{\partial z}{\partial x},\frac{\partial z}{\partial y}\right) = \left( -1,2 \right) \\
\end{equation*}
Il problema è in forma di massimo e rappresenteremo $\nabla(z)$ sul grafico, ricordando che nella forma standard è nella stessa direzione dell'opposto del gradiente della funzione obiettivo trasformata in funzione di minimo.
In giallo è rappresentato il politopo $P$. Essendo un politopo, cioè limitato in ogni direzione, sarà limitato in particolare nella direzione del gradiente, qualunque essa sia.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}
\begin{axis}
[axis lines=middle, axis equal, enlargelimits, xlabel=$x_1$, ylabel=$x_2$,
 every axis x label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=west,
 },
 every axis y label/.style={
    at={(ticklabel* cs:1.01)},
    anchor=south,
 },%xtick={1,2,3}
 ]
    \path[name path=AX]
        (axis cs:\pgfkeysvalueof{/pgfplots/xmin},0)--
        (axis cs:\pgfkeysvalueof{/pgfplots/xmax},0);
    \path[name path=AY]
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymin})--
        (axis cs:0,\pgfkeysvalueof{/pgfplots/ymax});
    \path[name path=UP]
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmin},\pgfkeysvalueof{/pgfplots/ymax})--
    	(axis cs:\pgfkeysvalueof{/pgfplots/xmax},\pgfkeysvalueof{/pgfplots/ymax});

\addplot
[domain=0:4, samples=10, thick, blue, name path=x3]
(3,x) node [pos=0.4,pin={75:{\color{blue}$x_1=3$}}, inner sep=0pt] {};
\addplot
[domain=0:4, samples=10, thick, red, name path=y3]
{3} node [pos=0.3, pin={75:{\color{red}$x_2=3$}}, inner sep=0pt] {};
\addplot
[domain=0:3, samples=10, thick, green, name path=4x3y12]
{-(4/3)*x + 4} node [pos=0.5, pin={75:{\color{green}$4x_1+3x_2=12$}}, inner sep=0pt] {};
\addplot[thick, fill=yellow, fill opacity=0.5] fill between [of=4x3y12 and UP, soft clip={domain=0:3}];
\addplot[white] fill between [of=y3 and UP];
%\addplot[pattern=north east lines, pattern color=red!10] fill between [reverse=true, of=AX and UP, soft clip={domain=0:5}];
\addplot[pattern=north east lines, pattern color=green!10] fill between [of=4x3y12 and UP];
\addplot[pattern=vertical lines, pattern color=red!10] fill between [of=y3 and AX];
\addplot[pattern=horizontal lines, pattern color=blue!10] fill between [of=x3 and AY];
\intne{x3}{AX}{$\alpha$}{alp};
\intse{y3}{4x3y12}{$\beta$}{bet};
\intne{y3}{x3}{$\gamma$}{gam};
\node at (axis cs:2.5,2) {$P$};
\addplot[-latex, thick] coordinates
           {(0,0) (-1/3.16,3/3.16)} node [pos=.3, anchor=north, label={135:{\small $\nabla z$}}] {};
\end{axis}
\end{tikzpicture}
\caption{Rappresentazione cartesiana del problema di programmazione lineare}
\label{fig:graph7}
\end{figure}

\subsection{Forma standard}

Rendiamo la funzione di massimo $z$ in una funzione di minimo $\varphi$:
$$
\varphi=-z=\min x_1-3x_2
$$
Introduciamo due variabili slack e una variabile surplus:
\begin{alignat*}{7}
&\min \varphi = \quad && x_1 \quad\; && -3x_2 \quad\;\; && \qquad\qquad && \qquad\qquad && \qquad\qquad && \\
&\;\st  &&+x_1			&&		 		&&+\pmb{x_3}	&&		 		&&					&&=3\\
&	 	&&				&&+x_2			&&				&& +\pmb{x_4}	&&					&&=3\\
&	 	&&+4x_1			&&+3x_2			&&				&&				&&-\pmb{x_5}		&&=12\\
&		&&\quad\; x_1,	&&\quad\; x_2,	&&\quad\; x_3,	&&\quad\; x_4,	&&\quad\; x_5		&&\geq 0
\end{alignat*}

\subsection{Risoluzione tramite tableau}

\begin{table}[htbp]
\centering
\begin{tabular}{rcccccc}
			&$-\varphi$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ \\
$\OL{c_j}$ 	& \Sc{0} 	& 1 	& -3 	& 0 	& 0 	& 0 \\
\cline{2-7}
$R_1$ 		& \Sc{3} 	& 1 	& 0 	& 1 	& 0 	& 0 \\
$R_2$		& \Sc{3} 	& 0 	& 1		& 0 	& 1 	& 0 \\
$R_3$		& \Sc{12} 	& 4 	& 3 	& 0 	& 0 	& -1 \\
\end{tabular}
\caption{Tableau iniziale.}
\label{tab:tab71}
\end{table}
Non abbiamo nessuna sottomatrice identità a disposizione da utilizzare come base ammissibile.
Per ottenere una BFS di partenza, quindi, ricorriamo alla \textbf{fase 1 del metodo del simplesso}.

\subsubsection{Fase 1 - aggiunta di variabili artificiali}

Per ridurre al minimo le variabili artificiali $x_i^a,\quad i=1,\cdots,n'$ è sufficiente aggiungerne una per ogni colonna della matrice identità mancante nel tableau originale. Nel nostro caso manca solo la terza colonna e sarà quella che introdurremo con l'\textit{unica} variabile artificiale $x^a$, trasformando il terzo vincolo in:
$$
4x_1 + 3x_2 - x_5 + x^a = 12
$$
Il nostro scopo, dopo l'introduzione di $x^a$, sarà quello di \textbf{eliminarla} dalla base. Per far ciò bisogna fare in modo che questa valga zero e quindi introduciamo, a tale scopo, una nuova funzione obiettivo da minimizzare $\psi$ tale che:
$$
\psi = \sum_{i=1}^{n'}x_i^a = x^a
$$
Scriviamo il nuovo tableau in tabella \vref{tab:tab72} e applichiamo il simplesso per ottimizzare la nostra funzione $\psi$.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{3} 	& 1		& 0 	& 1 	& 0 	& \Sc{0}& 0 \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x^a$ 		& \Sc{12} 	& 4 	& 3 	& 0 	& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Nuovo tableau con la variabile artificiale $x^a$.}
\label{tab:tab72}
\end{table}
Abbiamo una sottomatrice identità formata dalla base:
$$
\mathcal{B}=\{A_3,A_4,A_6\}
$$
Per avere a avere a disposizione i valori delle coordinate della BFS del nuovo problema, è necessario che:
$$
y_{ij}=0 \quad \forall i,j:A_j\in\mathcal{B},i\neq j
$$
Condizione vera per ogni valore tranne $y_{06}$ che provvediamo ad annullare tramite l'operazione elementare di riga:
$$
R_0\leftarrow R_0 - R_3
$$
Nel nuovo tableau in figura \vref{tab:tab73} faremo pivoting sulla colonna $A_1$, che sarebbe la nostra scelta sia con la regola di Dantzig che con la regola di Bland. Per scegliere su quale elemento fare \textbf{pivoting}, dobbiamo ottenere il valore di $y_{\ell 1}$ tale che:
$$
\vartheta_{\max}=\min_{i:y_{i1}>0}\frac{y_{i0}}{y_{i1}}=\frac{y_{i0}}{y_{\ell 1}}
$$
Perciò, operando con gli elementi nel tableau:
$$
\vartheta_{\max}=\min\left(\frac{3}{1},\frac{12}{4}\right)=\frac{12}{4}=\frac{y_{30}}{\pmb{y_{31}}}
$$
Faremo pivoting sull'elemento $y_{31}$ (cerchiato in tabella). In realtà avevamo un caso di \textbf{parità}, ma seguendo la regola nella traccia abbiamo fatto pivoting sull'elemento che avrebbe fatto uscire dalla base la variabile artificiale. Il nostro scopo è ora far comparire uno 0 nella colonna dell'elemento pivot in tutte le righe tranne quella in cui si trova l'elemento pivot e far comparire un 1 in quest'ultima.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-12} 	& -4 	& -3 	& 0 	& 0 	& \Sc{1}& 0\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{3} 	& 1		& 0 	& 1 	& 0 	& \Sc{0}& 0 \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x^a$ 		& \Sc{12} 	&\C{4} 	& 3 	& 0 	& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Pivoting su $y_{31}$. $A_1$ entra in base e $A_6$ esce.}
\label{tab:tab73}
\end{table}
Applichiamo le operazioni elementari di riga (nell'ordine) al nostro tableau come segue:
\begin{align*}
R_0&\leftarrow R_0+R_3; \\
R_3&\leftarrow \frac{R_3}{4}; \\
R_1&\leftarrow R_1 - R_3.
\end{align*}
Il nostro nuovo tableau diventa quindi quello in tabella \vref{tab:tab74}.
\begin{table}[htbp]
\centering
{
	\newcommand{\uq}{$\frac{1}{4}$}
	\newcommand{\tq}{$\frac{3}{4}$}
	\newcommand{\muq}{$-\frac{1}{4}$}
	\newcommand{\mtq}{$-\frac{3}{4}$}

\begin{tabular}{rrccccccc}
 	  & 			&$-\psi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 0 	& 0 	& 0 	& 0 	& \Sc{0}& 1\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{0} 	& 0		& \mtq 	& 1 	& 0 	& \Sc{\uq}& \muq \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x_1$ 		& \Sc{3} 	& 1 	& \tq 	& 0 	& 0 	& \Sc{\muq}& \uq \\
\end{tabular}
}
\caption{Secondo tableau. Vertice $\alpha(3,0)$}
\label{tab:tab74}
\end{table}
Siamo giunti alla soluzione ottima, essendo $\OL{c_j}>0 \quad\forall j$. Inoltre la variabile artificiale $x^a$ non è più in base. La nuova base e la nuova soluzione sono:
\begin{align*}
\mathcal{B}&=\{A_3,A_4,A_1\} \\
x&=(3,0,0,3,0,0)
\end{align*}
Siamo nel vertice $\alpha(3,0)$ e quindi in una BFS da cui possiamo partire per la \textbf{fase 2} del metodo del simplesso.
\subsubsection{Fase 2 - Simplesso}
Per questa fase useremo come tableau di partenza quello in tabella \vref{tab:tab74} sostituendo la funzione obiettivo fittizia $\psi$ utilizzata in precedenza con la nostra vera funzione obiettivo $\varphi$. Manterremo la variabile artificiale (che si fa notare non cambia in alcun modo il nostro problema in quanto non faremo mai entrare in base) perché, come vedremo poi, il suo costo relativo finale sarà utile ai fini della soluzione del problema duale.
Il tableau così ottenuto è quello in tabella \vref{tab:tab75}
\begin{table}[htbp]
\centering
{
	\newcommand{\uq}{$\frac{1}{4}$}
	\newcommand{\tq}{$\frac{3}{4}$}
	\newcommand{\muq}{$-\frac{1}{4}$}
	\newcommand{\mtq}{$-\frac{3}{4}$}

\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 1 	& -3 	& 0 	& 0 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{0} 	& 0		& \mtq 	& 1 	& 0 	& \Sc{\uq}& \muq \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x_1$ 		& \Sc{3} 	& 1 	& \tq 	& 0 	& 0 	& \Sc{\muq}& \uq \\
\end{tabular}
}
\caption{Secondo tableau. Vertice $\alpha(3,0)$ e funzione obiettivo $\varphi$.}
\label{tab:tab75}
\end{table}
Per applicare il simplesso, dobbiamo fare in modo che:
$$
y_{ij}=0 \quad\forall i,j:j\in\mathcal{B}, i\neq j
$$
L'elemento $y_{01}$ è l'unico a non essere nullo. Ovviamo al problema con l'operazione di riga:
$$
R_0\leftarrow R_0 - R_3
$$
Otteniamo quindi il tableau in tabella \vref{tab:tab76}.
\begin{table}[htbp]
\centering
{
	\newcommand{\uq}{$\frac{1}{4}$}
	\newcommand{\tq}{$\frac{3}{4}$}
	\newcommand{\muq}{$-\frac{1}{4}$}
	\newcommand{\mtq}{$-\frac{3}{4}$}
	\newcommand{\mqq}{$-\frac{15}{4}$}

\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-3} 	& 0 	& \mqq 	& 0 	& 0 	& \Sc{\uq}& \muq\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{0} 	& 0		& \mtq 	& 1 	& 0 	& \Sc{\uq}& \muq \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x_1$ 		& \Sc{3} 	& 1 	& \tq 	& 0 	& 0 	& \Sc{\muq}& \uq \\
\end{tabular}
}
\caption{Secondo tableau. Vertice $\alpha(3,0)$.}
\label{tab:tab76}
\end{table}
Per fare pivoting sceglieremo la colonna $A_2$, l'unica con un costo relativo negativo. Cerchiamo quindi l'elemento pivot $y_{\ell 2}$.
\begin{align*}
\vartheta_{\max}&=\min_{i:y_{i2}>0}\frac{y_{i0}}{y_{i2}}=\frac{y_{i0}}{y_{\ell 2}} \\
\vartheta_{\max}&=\min\left(\frac{3}{1},\frac{3}{\frac{3}{4}}\right)=\frac{3}{1}=\frac{y_{20}}{\pmb{y_{22}}}
\end{align*}
Faremo pivoting sull'elemento $y_{22}$ (cerchiato in tabella \vref{tab:tab77}).
\begin{table}[htbp]
\centering
{
	\newcommand{\uq}{$\frac{1}{4}$}
	\newcommand{\tq}{$\frac{3}{4}$}
	\newcommand{\muq}{$-\frac{1}{4}$}
	\newcommand{\mtq}{$-\frac{3}{4}$}
	\newcommand{\mqq}{$-\frac{15}{4}$}

\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{-3} 	& 0 	& \mqq 	& 0 	& 0 	& \Sc{\uq}& \muq\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{0} 	& 0		& \mtq 	& 1 	& 0 	& \Sc{\uq}& \muq \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& \C{1}	& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x_1$ 		& \Sc{3} 	& 1 	& \tq 	& 0 	& 0 	& \Sc{\muq}& \uq \\
\end{tabular}
}
\caption{Terzo tableau. Vertice $\alpha(3,0)$}
\label{tab:tab77}
\end{table}
$y_{22}=1$, quindi le operazioni elementari di riga sono:
\begin{align*}
R_0&\leftarrow R_0 + \frac{15}{4}R_2 \\
R_1&\leftarrow R_1 + \frac{3}{4}R_2 \\
R_3&\leftarrow R_3 - \frac{3}{4}R_2
\end{align*}
Otterremo il tableau in tabella \vref{tab:tab78}.
\begin{table}[htbp]
\centering
{
	\newcommand{\uq}{$\frac{1}{4}$}
	\newcommand{\tq}{$\frac{3}{4}$}
	\newcommand{\qq}{$\frac{15}{4}$}
	\newcommand{\nq}{$\frac{9}{4}$}
	\newcommand{\muq}{$-\frac{1}{4}$}
	\newcommand{\mtq}{$-\frac{3}{4}$}
	\newcommand{\mqq}{$-\frac{15}{4}$}
	\newcommand{\ttq}{$\frac{33}{4}$}

\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{\ttq}	& 0 	& 0 	& 0 	& \qq	& \Sc{\uq}& \muq\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{\nq} 	& 0		& 0 	& 1 	& \tq 	& \Sc{\uq}& \muq \\
$R_2$ & $x_2$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x_1$ 		& \Sc{\tq} 	& 1 	& 0 	& 0 	& \mtq 	& \Sc{\muq}& \uq \\
\end{tabular}
}
\caption{Quarto tableau. Vertice $\beta(\frac{3}{4},3)$}
\label{tab:tab78}
\end{table}
Siamo giunti alla soluzione ottima, essendo $\OL{c_j}>0 \quad\forall j$. La nuova base e la nuova soluzione sono:
\begin{align*}
\mathcal{B}&=\{A_3,A_2,A_1\} \\
x&=(\frac{3}{4},3,\frac{9}{4},0,0,0)
\end{align*}
Siamo nel vertice $\beta\left(\frac{3}{4},3\right)$
Si fa notare infine che la nostra funzione obiettivo iniziale è:
$$
z=-\varphi=\frac{33}{4}
$$

\subsection{Soluzione del problema primale}
La soluzione ottima consiste nel produrre $75$ panchine di tipo 1 e $300$ panchine di tipo 2 per un introito di $8\,250$\euro .

\subsection{Costruzione del problema duale}
Riportiamo ora il problema primale e, per motivi di sintesi, poniamo anche una notazione più breve che ci permetterà di costruire il problema duale:
$$
{
	\renewcommand*\arraystretch{.7}
\begin{array}{r| @{}c@{} |c| @{}c@{} |c| @{}c@{}|c| @{}c@{}|c| @{}c@{} |c| c|}
\cline{2-2}\cline{4-4}\cline{6-6}\cline{8-8}\cline{10-10}\cline{12-12}
	 &\qquad\qquad& &\qquad\qquad& &\qquad\qquad& &\qquad\qquad& & \qquad\qquad& & \\
\min		& x_1 	&-& 3x_2 	& &   		& &   		& &			& & \CG{\max}\\
	 		&\CG{=}	& &\CG{=}	& &\CG{=}	& &\CG{=}	& &\CG{=} 	& &   \\
\CG{\pi_1}	& x_1	& &		 	&+& x_3 	& &			& & 		&=& 3 \\
	 		&\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{+} 	& &   \\
\CG{\pi_2}	& 	 	& & x_2 	& &			&+& x_4		& &  		&=& 3 \\
	 		&\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{+} 	& &   \\
\CG{\pi_3}	& 4x_1 	&+&3x_2 	& &			& &			&-& x_5		&=& 12\\
	 		&\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{+}	& &\CG{-} 	& & \\
\cline{2-2}\cline{4-4}\cline{6-6}\cline{8-8}\cline{10-10}\cline{12-12}
	 		&  		& &  		& &	  		& &   		& & 	& & \\
	 		& x_1	&,& x_2 	&,& x_3 	&,& x_4 	&,& x_5 &\geq& 0\\
	 		&  		& &  		& &	  		& &   		& & 	& & \\
\cline{2-2}\cline{4-4}\cline{6-6}\cline{8-8}\cline{10-10}\cline{12-12}
\end{array}
}
$$
Ricordando che \textit{ad ogni variabile non negativa corrisponde un vincolo duale di non maggioranza}, il problema duale, perciò, è il seguente:
\begin{alignat*}{8}
&\max \xi = \quad && +3\pi_1 \quad\; && +3\pi_2 \quad\; && +12\pi_3 \quad\;\; && \\
&\;\st  &&+\pi_1		&&		 		&&+4\pi_3	&& \leq 1 \\
&	 	&&				&&+\pi_2 		&&+3\pi_3	&& \leq -3\\
&	 	&&+\pi_1		&&				&&			&& \leq 0 \\
&	 	&&				&&+\pi_2		&& 			&& \leq 0 \\
&	 	&&				&&				&&+\pi_3	&& \leq 0 \\
&		&&\quad\;\pi_1,	&&\quad\;\pi_2,	&&\quad\;\pi_3,	&& \gtreqless 0
\end{alignat*}

\subsection{Soluzione del problema duale}
Riportiamo nuovamente i tableau iniziale e finale rispettivamente nelle tabella \vref{tab:tab49} e \vref{tab:tab410}.
\begin{table}[htbp]
\centering
\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{0} 	& 1 	& -3 	& 0 	& 0 	& \Sc{0}& 0\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{3} 	& 1		& 0 	& 1 	& 0 	& \Sc{0}& 0 \\
$R_2$ & $x_4$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x^a$ 		& \Sc{12} 	& 4 	& 3 	& 0 	& 0 	&\Sc{-1}& 1 \\
\end{tabular}
\caption{Nuovo tableau con la variabile artificiale $x^a$.}
\label{tab:tab79}
\end{table}
\begin{table}[htbp]
\centering
{
	\newcommand{\uq}{$\frac{1}{4}$}
	\newcommand{\tq}{$\frac{3}{4}$}
	\newcommand{\qq}{$\frac{15}{4}$}
	\newcommand{\nq}{$\frac{9}{4}$}
	\newcommand{\muq}{$-\frac{1}{4}$}
	\newcommand{\mtq}{$-\frac{3}{4}$}
	\newcommand{\mqq}{$-\frac{15}{4}$}
	\newcommand{\ttq}{$\frac{33}{4}$}

\begin{tabular}{rrccccccc}
 	  & 			&$-\varphi$	& $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$	& $x^a$\\
$R_0$ & $\OL{c_j}$ 	& \Sc{\ttq}	& 0 	& 0 	& 0 	& \qq	& \Sc{\uq}& \muq\\
\cline{3-9}
$R_1$ & $x_3$ 		& \Sc{\nq} 	& 0		& 0 	& 1 	& \tq 	& \Sc{\uq}& \muq \\
$R_2$ & $x_2$ 		& \Sc{3} 	& 0		& 1		& 0 	& 1 	& \Sc{0}& 0 \\
$R_3$ & $x_1$ 		& \Sc{\tq} 	& 1 	& 0 	& 0 	& \mtq 	& \Sc{\muq}& \uq \\
\end{tabular}
}
\caption{Quarto tableau. Vertice $\beta(\frac{3}{4},3)$}
\label{tab:tab710}
\end{table}
La base iniziale è $\mathcal{B}_1={A_3,A_4,A_6}$. Applicando delle semplici sottrazioni, ricaviamo la soluzione del problema duale:
\begin{align*}
\pi_1&=c_3-\OL{c_3}=0 \\
\pi_2&=c_6-\OL{c_4}=-\frac{15}{4} \\
\pi_3&=c_5-\OL{c_6}=\frac{1}{4}
\end{align*}
Perciò, la soluzione del problema duale è il vettore:
$$
\pi'=
\begin{bmatrix}
0 & -\frac{15}{4} & 0
\end{bmatrix}
$$
Per verificare la correttezza dei calcoli, applichiamo la soluzione alla funzione obiettivo del problema duale:
$$
\xi\left(0,-\frac{15}{4},0\right)=3(0)+3\left(-\frac{15}{4}\right)+12\left(\frac{1}{4}\right)=-\frac{45}{4}+\frac{12}{4}=-\frac{33}{4}
$$
Il risultato è, come atteso, lo stesso del problema primale.

\subsection{Vincolo di interezza}\label{sec:es7ILP}

\textit{Sezione in fase di allestimento...ci rivediamo appena il prof. spiegherà i metodi per la ILP}.