\documentclass[10pt]{article}
\usepackage[italian]{babel}
%\usepackage{latexsym}
%\usepackage{algorithm}
\usepackage{epsfig}
\usepackage{fancybox}


\textwidth 15.5cm
\textheight 21.5cm
\topmargin 0cm
\evensidemargin 0in
\oddsidemargin 0in


\def\bbbr{{\rm I\!R}}
\def\bbbm{{\rm I\!M}}
\def\bbbn{{\rm I\!N}}

\def\sm{\setminus}
\newcommand {\ol}[1]{\overline{#1}}

\newtheorem{Teo}{Theorem}[section]
\newtheorem{Dom}{Domanda}%[section]
\newtheorem{Ese}{Esercizio}%[section]
\newtheorem{Att}{Attenzione!!! \ }%[section]
\newtheorem{Not}{Nota}%[section]
\newtheorem{Con}[Teo]{Conjecture}
\newtheorem{Que}{Question}
\newtheorem{Cor}[Teo]{Corollary}
\newtheorem{Property}[Teo]{Property}
\newtheorem{Pro}[Teo]{Proposition}
\newtheorem{Cla}[Teo]{Claim}
\newtheorem{Lem}[Teo]{Lemma}
\newtheorem{Obs}[Teo]{Observation}

\pagestyle{empty}
 
\begin{document}

\begin{center}
   {\LARGE \bf Il tableau\footnote{``tableau'' si pronuncia come fosse scritto tabl\`o}: un sussidio alla gestione dei conteggi}
\end{center}

{\bf La lettura di questo documento \`e strettamente
consigliata agli studenti che intendano affrontare la
provetta di Programmazione Lineare}.
Svolgeremo qu\`\i\ di seguito alcuni
esercizi di preparazione alla provetta.
Ci atterremo a procedimenti standard di soluzione.
Proporremo inoltre l'uso del tableau.
Il tableau si \`e imposto come scrittura compatta di
un dizionario nella didattica della 
Programmazione Lineare.
Spesso i vari elementi,
teorici ed algoritmici,
che compongono la PL
vengono introdotti come metodi
di manipolazione del tableau che conducano
ai risultati desiderati.
Se avrete altre occasioni di incontro con la PL 
vi dovrete probabilmente confrontare
con il tableau.
Conviene pertanto impadronirsi ora di questo approccio
con relativo linguaggio e tecnicalit\`a.
{\em 
E comunque la conoscenza del tableau
come descritto in questo documento \`e intesa
come parte integrante del programma del corso.
Per quanto riguarda la provetta l'uso del tableau
non \`e n\`e obbligatorio n\`e incoraggiato.}
Tuttavia esso \`e consigliato
dacch\`e
il presentare i passaggi in forma compatta
aumenta chiarezza e leggibilit\`a.
In pratica il tableau offre lo strumento,
di fatto standard,
per incrementare la qualit\`a del documento prodotto
nello svolgimento di problemi di PL.\\


\medskip

Buona Lettura.


\bigskip

{\large \bf Il tableau ed il metodo del simplesso}\\

Al seguente problema di PL associo il corrispondente tableau:

\[
   \begin{array}{l}
        \max \mbox{\ }6x_1 + 7x_2\\
        \left\{
        \begin{array}{l}
        \begin{array}{rrr}
            2x_1 \;+& 3x_2 \;\leq &   12 \\
            2x_1 \;+&  x_2 \;\leq &    8 \\
        \end{array} \\
        x_1, x_2  \geq 0    
        \end{array}
        \right.
   \end{array}
\hfill
\hspace{1cm}
{\Huge \Longrightarrow}
\hfill
\hspace{2cm}
   \begin{array}{rrrr}
         & x_1  & x_2  \\
      x_3 &  2 &  3 &  12 \\
      x_4 &  2 &  1 &   8 \\
       z  & -6 & -7 &   0 \\
   \end{array}
\]

Dove $x_3$ ed $x_4$ indicano le variabili di slack.
Osserviamo che i coefficienti della funzione obiettivo
(o costi) vengono riportati nel tableau col segno rovesciato
e che alla funzione obiettivo corrisponde 
(nella prassi diffusa)
l'ultima riga.

A dire il vero il tableau non corrisponde propriamente
ad un problema di PL ma ad un particolare dizionario
di un problema di PL ossia ad un problema di PL
visto dalla particolare prospettiva di una sua soluzione di base
(ammissibile o meno).
Il caso di cui sopra era fortuito:
essendo il problema in forma standard era possibile
scriverne direttamente un primo tableau.

\begin{Dom}
   A quale soluzione di base si riferisce
   il tableau dato sopra?
\end{Dom}
{\em Risposta: \/}
tutte le variabili di decisione fuori base
($x_1 = x_2 = 0$) mentre $x_3=12$ ed $x_4=8$.\\

In corrispondenza di una qualsiasi soluzione,
la funzione obiettivo assume un determinato valore,
che viene riportato a destra nell'ultima riga del tableau.\\

In generale, il seguente dizionario \`e 
pi\`u compattamente descritto in forma di tableau:


\[ {\small
   \begin{array}{lcrrrrrr}
      x_{n+1} &=& b_1 & -a_{1,1}x_1 & \ldots & -a_{1,i}x_i & \ldots & -a_{1,n} x_n \\
      \ldots  &\ldots& \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+j} &=& b_j & -a_{j,1}x_1 & \ldots & -a_{j,i}x_i & \ldots & -a_{j,n} x_n \\
      \ldots  &\ldots& \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+m} &=& b_m & -a_{m,1}x_1 & \ldots & -a_{m,i}x_i & \ldots & -a_{m,n} x_n \\
         z    &=& v & +c_1 x_1 & \ldots & +c_i x_i & \ldots &  +c_n x_n \\
   \end{array}
\hspace{0.2cm}
{\Huge \Longleftrightarrow}
\hspace{0.2cm}
   \begin{array}{rrrrrrr}
         & x_1 \; & \ldots  & x_i \; & \ldots  \; & x_n\\
      x_{n+1} & a_{1,1} & \ldots & a_{1,i} & \ldots & a_{1,n} &  b_1 \\
      \ldots  & \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+j} & a_{j,1} & \ldots & a_{j,i} & \ldots & a_{j,n} &  b_j \\
      \ldots  & \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+m} & a_{m,1} & \ldots & a_{m,i} & \ldots & a_{m,n} &  b_m \\
         z    & -c_1 & \ldots & -c_i & \ldots & -c_n &  v \\
   \end{array}
  }
\]



Ecco un secondo esempio:

\[
   \begin{array}{c}
   \mbox{\sc Problema di PL}\\ 
   \begin{array}{l}
        \min \mbox{\ }2x_1 + 7x_2 -2x_3\\
        \left\{
        \begin{array}{l}
        \begin{array}{rrrr}
             x_1 \;+&  2x_2 \;+&  x_3 \;\leq &   1 \\
           -4x_1 \;+& -2x_2 \;+& 3x_3 \;\leq &   2 \\
        \end{array} \\
        x_1, x_2, x_3  \geq 0    
        \end{array}
        \right.
   \end{array}
   \end{array}
\]
\[
   \begin{array}{c}
   \mbox{\sc Dizionario Iniziale}\\ \\
   \begin{array}{lcrrrr}
      x_{4} &=& 1 & -x_1 & -2x_2 & -x_3 \\
      x_{5} &=& 2 & +4x_1 & +2x_2 & -3x_3 \\
         z    &=& 0 & +2x_1 & +7x_2 & -2x_3 \\
   \end{array}
   \end{array}
\hfill
\hspace{1cm}
{\Huge \Longleftrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{c}
   \mbox{\sc Tableau}\\ 
   \begin{array}{rrrrr}
         & x_1  & x_2 & x_3  \\
      x_4 &  1 &  2 &  1   &  1 \\
      x_5 & -4 & -2 & \fbox{3} &  2 \\
       z  & -2 & -7 &  2   &  0 \\
   \end{array}
   \end{array}
\]

\begin{Dom}
   Secondo te,
   perch\'e il \fbox{3} nel tableau sopra \`e stato incorniciato?
\end{Dom}
{\em Risposta: \/}
Il \fbox{3} \`e l'elemento di {\em pivot}.\\


\begin{Dom}
   Come sceglieresti l'elemento di pivot direttamente dal tableau?
\end{Dom}
{\em Possibile Risposta: \/}
Come colonna di pivot si sceglie
una qualsiasi colonna $\bar{\jmath}$
avente l'ultimo elemento $-c_{\bar{\jmath}}$
maggiormente positivo ($+2$ nella terza colonna)
dacch\`e stiamo minimizzando.\\

La scelta della riga di pivot si effettua
considerando tutti gli $a_{i,\bar{\jmath}}$ positivi.
Tra questi, quello che minimizza il rapporto $b_i/a_{i,\bar{\jmath}}$,
\`e l'elemento di pivot.\\ 

\begin{Ese}
   La regola ora introdotta per la scelta dell'elemento
   di pivot non dovrebbe esserti del tutto nuova.
   Sapresti proporre ora una seconda regola per
   la scelta dell'elemento di pivot nel tableau?
\end{Ese}

Eseguiamo ora il passo di pivot nel dizionario
e scopriamo cos\`\i\ come debba venir
aggiornato il tableau.

\[
   \begin{array}{c}
   \mbox{\sc Dizionario Iniziale}\\ \\
   \begin{array}{lcrrrr}
      x_{4} &=& 1 & -x_1 & -2x_2 & -x_3 \\
      x_{5} &=& 2 & +4x_1 & +2x_2 & -3x_3 \\
         z    &=& 0 & +2x_1 & +7x_2 & -2x_3 \\
   \end{array}\\ \\
       \hspace{1cm} {\Huge \downarrow} {\Large \mbox{ \ $(pivot)$}}
   \end{array}
\hfill
\hspace{1cm}
{\Huge \Longleftrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{c}
   \mbox{\sc Tableau Iniziale}\\ 
   \begin{array}{rrrrr}
         & x_1  & x_2 & x_3  \\
      x_4 &  1 &  2 &  1   &  1 \\
      x_5 & -4 & -2 & \fbox{3} &  2 \\
       z  & -2 & -7 &  2   &  0 \\
   \end{array}\\ \\
       \hspace{1cm} {\Huge \downarrow} {\Large \mbox{ \ $(pivot)$}}
   \end{array}
\]

\[
   \begin{array}{c}
   \mbox{\sc Nuovo Dizionario}\\ \\
   \begin{array}{lcrrrr}
      x_{4} &=& \frac{1}{3} & -\frac{7}{3}x_1 & -\frac{8}{3}x_2 & +\frac{1}{3}x_3 \\
      x_{3} &=& \frac{2}{3} & +\frac{4}{3}x_1 & +\frac{2}{3}x_2 & -\frac{1}{3}x_5 \\
         z    &=& -\frac{4}{3} & -\frac{2}{3}x_1 & +\frac{17}{3}x_2 & +\frac{2}{3}x_5 \\
   \end{array}
   \end{array}
\hfill
\hspace{1cm}
{\Huge \Longleftrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{c}
   \mbox{\sc Nuovo Tableau}\\ 
   \begin{array}{rrrrr}
         & x_1  & x_2 & x_5  \\
      x_4 &  \fbox{$\frac{7}{3}$} &  \frac{8}{3} & -\frac{1}{3}   &  \frac{1}{3} \\
      x_3 & -\frac{4}{3} &  -\frac{2}{3}  &  \frac{1}{3}  &  \frac{2}{3} \\
       z  &  \frac{2}{3} &  -\frac{17}{3} & -\frac{2}{3}  & -\frac{4}{3} \\
   \end{array}
   \end{array}
\]

Nel tableau, siano $\bar{\imath}$ e $\bar{\jmath}$
la riga e la colonna di pivot.
Sia $p= a_{\bar{\imath},\bar{\jmath}}$ il valore dell'elemento di pivot.
Ecco la regola generale per
eseguire il pivot direttamente sul tableau:

\[
   \begin{array}{rrrrrrr}
         & x_1 \; & \ldots  & x_{\bar{\jmath}} \; & \ldots  \; & x_n\\
      x_{n+1} & a_{1,1} & \ldots & a_{1,\bar{\jmath}} & \ldots & a_{1,n} &  b_1 \\
      \ldots  & \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+\bar{\imath}} & a_{\bar{\imath},1} & \ldots & a_{\bar{\imath},\bar{\jmath}} & \ldots & a_{\bar{\imath},n} &  b_j \\
      \ldots  & \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+m} & a_{m,1} & \ldots & a_{m,\bar{\jmath}} & \ldots & a_{m,n} &  b_m \\
         z    & -c_1 & \ldots & -c_{\bar{\jmath}} & \ldots & -c_n &  v \\
   \end{array}
\hspace{0.2cm}
{\Huge \Longleftrightarrow}
\hspace{0.2cm}
   \begin{array}{rrrrrrr}
         & x_1 \; & \ldots  & x_{n+\bar{\imath}} \; & \ldots  \; & x_n\\
      x_{n+1} & \ldots & \ldots & -\frac{a_{1,\bar{\jmath}}}{p} & \ldots & \ldots &  \ldots \\
      \ldots  & \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{\bar{\jmath}} & \frac{a_{\bar{\imath},1}}{p} & \ldots & \frac{1}{p} & \ldots & \frac{a_{\bar{\imath},n}}{p} &  \frac{b_j}{p} \\
      \ldots  & \ldots  & \ldots & \ldots  & \ldots & \ldots  & \ldots \\
      x_{n+m} & \ldots & \ldots & -\frac{a_{m,\bar{\jmath}}}{p} & \ldots & \ldots & \ldots \\
         z    & \ldots & \ldots & +\frac{c_{\bar{\jmath}}}{p} & \ldots & \ldots &  \ldots \\
   \end{array}
\]
Gli elementi non specificati del secondo tableau
si modificano come segue:
$a_{i,j}$ diviene $a_{i,j}-\frac{a_{\bar{\imath},j}a_{i,\bar{\jmath}}}{p}$ e 
similmente $c_j$ diviene $c_j-\frac{a_{\bar{\imath},j}c_{\bar{\jmath}}}{p}$.
Inoltre $b_i$ diviene $b_i-\frac{a_{i,\bar{\jmath}}b_{\bar{\imath}}}{p}$
e $v$ diviene $v-\frac{-c_{\bar{\jmath}}b_{\bar{\imath}}}{p}$.\\ 


Abbiamo cio\`e il seguente meccanismo di pivot.
\begin{itemize}
   \item Le variabili associate alla riga ed alla colonna di pivot
         si scambiano tra di loro.
   \item Gli elementi contenuti nella riga di pivot
         vengono divisi per $p:= a_{\bar{\imath},\bar{\jmath}}$.
   \item Gli elementi contenuti nella colonna di pivot
         vengono divisi per $p$
         ed invertiti in segno.
   \item L'elemento di pivot diviene $\frac{1}{p}$.
   \item Ogni elemento del tableau che non appartenga
         n\`e alla riga n\`e alla colonna di pivot 
         viene modificato come segue:
         $a_{i,j}$ diviene $a_{i,j}-\frac{a_{\bar{\imath},j}a_{i,\bar{\jmath}}}{p}$ e $c_j$ diviene $c_j-\frac{a_{\bar{\imath},j}c_{\bar{\jmath}}}{p}$.
Inoltre $b_i$ diviene $b_i-\frac{a_{i,\bar{\jmath}}b_{\bar{\imath}}}{p}$
e $v$ diviene $v-\frac{-c_{\bar{\jmath}}b_{\bar{\imath}}}{p}$.
\end{itemize}

L'operazione di pivot \`e forse meglio illustrata in Figura~\ref{pivot}.
\begin{figure}[htb]   % h=here; t=top; b=bottom;
\begin{center}
  \leavevmode
  \psfig{figure=pivot.eps, height=8.6 true cm}

  \caption{L'operazione di PIVOT.}
  \label{pivot}
\end{center}
\end{figure}

Ma ritorniamo al nostro problema di PL
ed eseguiamo il prossimo passo di pivot.

\[
   \begin{array}{rrrrr}
         & x_1  & x_2 & x_5  \\
      x_4 &  \fbox{$\frac{7}{3}$} &  \frac{8}{3} & -\frac{1}{3}   &  \frac{1}{3} \\
      x_3 & -\frac{4}{3} &  -\frac{2}{3}  &  \frac{1}{3}  &  \frac{2}{3} \\
       z  &  \frac{2}{3} &  -\frac{17}{3} & -\frac{2}{3}  & -\frac{4}{3} \\
   \end{array}
\hfill
\hspace{1cm}
{\longrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{rrrrr}
         & x_4  & x_2 & x_5  \\
      x_1 &  \frac{3}{7} &  \frac{8}{7}  & -\frac{1}{7}  &  \frac{1}{7} \\
      x_3 &  \frac{4}{7} &  \frac{6}{7}  &  \frac{1}{7}  &  \frac{6}{7} \\
       z  & -\frac{2}{7} & -\frac{45}{7} & -\frac{4}{7}  & -\frac{10}{7} \\
   \end{array}
\]

Gli elementi dell'ultima riga
sono ora tutti negativi.
Possiamo pertanto concludere che il valore ottimo del nostro
problema era $-\frac{10}{7}$.
(Perch\`e?)
La soluzione primale ottima \`e $x_2=x_4=x_5 = 0$
con $x_1=\frac{1}{7}$ e $x_3=\frac{6}{7}$.
La soluzione duale ottima \`e $y_1 = y_3 = 0$
con $y_2=-\frac{45}{7}$, $y_4=-\frac{2}{7}$ e $y_5=-\frac{4}{7}$
ed \`e anch'essa espressa nel tableau.\\

Di fatto \`e persino possibile ricavare
il tableau del problema duale
dal tableau del problema primale.

\[
   \begin{array}{c}
   \mbox{\sc Tableau Primale}\\ 
   \begin{array}{rrrrr}
         & x_4  & x_2 & x_5  \\
      x_1 &  \frac{3}{7} &  \frac{8}{7}  & -\frac{1}{7}  &  \frac{1}{7} \\
      x_3 &  \frac{4}{7} &  \frac{6}{7}  &  \frac{1}{7}  &  \frac{2}{7} \\
       z  & -\frac{2}{7} & -\frac{45}{7} & -\frac{4}{7}  & -\frac{10}{7} \\
   \end{array}
   \end{array}
\hfill
\hspace{1cm}
{\Huge \Longleftrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{c}
   \mbox{\sc Tableau Duale}\\ 
   \begin{array}{rrrr}
         & y_1  & y_3  \\
      y_4 &  -\frac{3}{7} & -\frac{4}{7}  & -\frac{2}{7} \\
      y_2 &  -\frac{8}{7} & -\frac{6}{7}  & -\frac{45}{7}\\
      y_5 &   \frac{1}{7} & -\frac{1}{7}  & -\frac{4}{7} \\
       z  &  -\frac{1}{7} & -\frac{2}{7}  & -\frac{10}{7} \\
   \end{array}
   \end{array}
\]

Dove la variabile duale $y_4$ corrisponde alla variabile
di slack $x_4$ e cio\`e \`e il moltiplicatore del primo vincolo.
La variabile duale $y_1$ corrisponde alla variabile
primale $x_1$ che \`e il moltiplicatore del primo vincolo duale,
ossia $y_1$ \`e la variabile di surplus nel primo vincolo duale. 

\begin{Dom}
   Quale \'e la regola per passare dal tableau del primale
   al tableau del duale?
\end{Dom}

\begin{Ese}
   Verificare che l'ultimo tableau proposto
   \`e il tableau per il problema duale all'ottimo.
\end{Ese}

\begin{Dom}
   Nell'ultimo tableau il prodotto 
   $x_i\cdot y_i$ \`e nullo
   per ogni $i$. Sai darne una ragione semplice? 
   Questa propriet\`a vale solo per l'ultimo tableau?
\end{Dom}

\begin{Att}
   Si noti come la regola per passare dal tableau del primale
   al tableau del duale non sia indempotente ossia differisca
   dalla regola per passare dal tableau del duale a quello
   del primale.
   Ci\`o \`e in contrasto con il fatto che il duale del duale di un
   problema di PL \`e di nuovo il problema originale.
   Tale contrasto \`e tuttavia solo apparente: 
     nel passare da un problema di PL al suo duale
    dovevo distinguere le diseguaglianze $\leq$ da quelle $\geq$.\\ 
   La convenzione standard per il tableau rompe
   questa simmetria primale/duale con una scelta arbitraria di segni.
   Il vantaggio \`e quello di una semplice regola di pivot
   unica per il primale ed il duale.
\end{Att}

Qualora si debba massimizzare la funzione obiettivo
allora seguiamo la stessa procedura,
solo che ora miriamo ad ottenere valori non negativi nell'ultima riga.
Ad esempio:
\[
   \begin{array}{l}
        \max \mbox{\ }2x_1 + 7x_2 -2x_3\\
        \left\{
        \begin{array}{l}
        \begin{array}{rrrr}
             x_1 \;+&  2x_2 \;+&  x_3 \;\leq &   1 \\
           -4x_1 \;+& -2x_2 \;+& 3x_3 \;\leq &   2 \\
        \end{array} \\
        x_1, x_2, x_3  \geq 0    
        \end{array}
        \right.
   \end{array}
\]

\[
   \begin{array}{rrrrr}
         & x_1  & x_2 & x_3  \\
      x_4 & 1  & \fbox{$2$} &  1  & 1  \\
      x_5 & -4 &  -2  &  3  & 2 \\
       z  & -2 &  -7  &  2  & 0 \\
   \end{array}
\hfill
\hspace{1cm}
{\longrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{rrrrr}
         & x_1  & x_4 & x_3  \\
      x_2 &  \frac{1}{2} &  \frac{1}{2}  & \frac{1}{2}  &  \frac{1}{2} \\
      x_5 &  -3 &  1  &  4  &  3 \\
       z  & \frac{3}{2} & \frac{7}{2} & \frac{11}{2}  & \frac{7}{2} \\
   \end{array}
\]

Il valore ottimo della funzione obiettivo \`e ora $\frac{7}{2}$.
La soluzione primale ottima \`e $x_1=x_3 = 0$
con $x_2=\frac{1}{2}$.
La soluzione duale ottima \`e 
$y_2 = 0$
con $y_1 = \frac{3}{2}$.\\

\setlength{\fboxsep}{25pt}
\shadowbox{
  \begin{minipage}{12.7cm}
    \begin{center}
      \vspace{-1.8mm}
      LA PROVA DI CONTROLLO
    \end{center}

    Anche la PL ha la sua prova del nove.
    Si assegni ad ogni variabile il valore
    del coefficiente di quella variabile nella
    funzione obiettivo originaria.
    Ad esempio l'ultimo tableau diviene:

\[
   \begin{array}{rrrrrr}
       &  & (2)  & (0) & (-2) \\
       &  & \downarrow \;& \downarrow \;& \downarrow \;\\
       &  & x_1  & x_4 & x_3  \\
    (7) \rightarrow & x_2 &  \frac{1}{2} &  \frac{1}{2}  & \frac{1}{2}  &  \frac{1}{2} \\
    (0) \rightarrow &   x_5 &  -3 &  1  &  4  &  3 \\
      & z  & \frac{3}{2} & \frac{7}{2} & \frac{11}{2}  & \frac{7}{2} \\
   \end{array}
\]

  Per ogni colonna vale quanto segue:
  il valore del coefficiente associato alla colonna
  pi\`u il valore dell'ultimo elemento della colonna
  eguaglia la somma degli altri elementi della colonna ciascuno
  moltiplicato per il coefficiente della riga cui appartiene.\\

  \noindent
  {\em Colonna 1:} $\frac{1}{2}(7) -3(0) = (2) + \frac{3}{2}$.\\
  {\em Colonna 2:} $\frac{1}{2}(7) +1(0) = (0) + \frac{7}{2}$.\\
  {\em Colonna 3:} $\frac{1}{2}(7) +4(0) = (-2) + \frac{11}{2}$.\\
  {\em Colonna 4:} $\frac{1}{2}(7) +3(0) = \frac{7}{2}$.\\

  Queste relazioni valgono per ogni tableau,
  non necessariamente ottimale.

  \end{minipage}
}
\setlength{\fboxsep}{3pt}


\vspace{1cm}

\bigskip

{\large \bf Il tableau ed il metodo del simplesso duale}\\


Consideriamo un problema in forma standard
e si assuma per fissare le idee che esso sia
un problema di massimizzazione.
Si assuma inoltre che tutti i coefficienti della funzione obiettivo
siano non-positivi.
Pertanto nel primo tableau i coefficienti nell'ultima riga
sono di gi\`a non-negativi, come li vorremmo nell'ultimo tableau.
Un tale tableau \`e detto {\em duale ammissibile}.
Se poi tutti i coefficienti nell'ultima colonna sono
non-negativi allora la soluzione di base corrente
\`e ammissibile ed il problema \`e gi\`a risolto.
Altrimenti si applica il metodo del simplesso
duale.
Una caratteristica interessante del metodo del
simplesso duale sul tableau \`e che l'operazione di
pivot si esplica esattamente come la regola di pivot
per il simplesso primale.
L'unica differenza operativa tra i due metodi
st\`a nella scelta dell'elemento di pivot
che nel caso del simplesso duale segue
la stessa filosofia gi\`a richiamata
per il simplesso primale.

\begin{Dom}
   Come sceglieresti l'elemento di pivot direttamente dal tableau?
\end{Dom}
{\em Possibile Risposta: \/}
Come riga di pivot si sceglie
una qualsiasi riga $\bar{\jmath}$
avente l'ultimo elemento $b_{\bar{\imath}}$
negativo (magari quello maggiormente negativo)
dacch\`e si mira ad ottenere anche l'ammissibilit\`a primale
(e quidi l'ottimalit\`a).\\

La scelta della colonna di pivot si effettua
considerando tutti gli $a_{\bar{\imath},j}$ negativi.
Tra questi, quello che minimizza il rapporto 
$|c_j/a_{\bar{\imath},j}|$,
\`e l'elemento di pivot.\\ 

\begin{Ese}
   Sapresti proporre ora una seconda regola per
   la scelta dell'elemento di pivot nel tableau?
\end{Ese}



Ecco un esempio:

\[
   \begin{array}{l}
        \max \mbox{\ }-x_1 - 2x_2 \\
        \left\{
        \begin{array}{l}
        \begin{array}{rrrr}
             -x_1 \;+&  4x_2 \;\leq &  -2 \\
            -2x_1 \;+&  2x_2 \;\leq &  -7 \\
             -x_1 \;-&  3x_2 \;\leq &   2 \\
        \end{array} \\
        x_1, x_2  \geq 0    
        \end{array}
        \right.
   \end{array}
\hfill
\hspace{0.4cm}
   \begin{array}{rrrrr}
         & x_1  & x_2  \\
      x_3 & -1 &  4  & -2 \\
      x_4 & \fbox{$-2$}  & 2  & -7  \\
      x_5 & -1 &  -3  & 2 \\
       z  & 1 &  2  & 0 \\
   \end{array}
\hfill
\hspace{0.2cm}
{\longrightarrow}
\hfill
\hspace{0.2cm}
   \begin{array}{rrrrr}
         & x_1  & x_2  \\
      x_3 & -\frac{1}{2} &  3  & \frac{3}{2} \\
      x_4 & -\frac{1}{2} & -1  & \frac{7}{2} \\
      x_5 & -\frac{1}{2} & -4  & \frac{11}{2} \\
       z  & \frac{1}{2} & 3  & \frac{7}{2} \\
   \end{array}
\]

\begin{Not}
   Il metodo del simplesso duale corrisponde
   a risolvere il problema duale attraverso
   il metodo del simplesso.\\
   Il simplesso duale conviene quando
   l'origine non \`e primale ammissibile 
   ma duale ammissibile oppure quando nel problema di PL
   primale il numero di vincoli supera il numero di incognite.
\end{Not}

\bigskip

{\large \bf Come gestire i vincoli sulle singole variabili}\\

Se invece di avere $x_j \geq 0$ si ha $x_j \geq l_j$
con $l_j\neq 0$ allora ci si avvale della sostituzione:
$x'_j = x_j - l_j$.
Se poi una variabile \`e limitata verso il basso
invece che verso l'alto, 
ossia $x_j \leq u_j$,
ma $x_j \geq 0$ non \`e richiesto,
allora si sostituisce 
$x'_j = u_j - x_j$.\\ 

Qualora invece una variabile non-negativa
sia limitata verso il basso,
tale condizione pu\`o essere considerata
come uno dei vincoli del problema.
Tuttavia, qualora tutte le variabili siano limitate
(ed in molti casi un limite ovvio \`e facilmente prodotto),
allora la situazione pu\`o essere girata a nostro vantaggio
considerando sia la variabile $x_j$ che
la variabile $x'_j = u_j - x_j$
e decidendo di adottare per la scrittura
del primo tableau quella delle due che
conduce ad un tableau duale ammissibile.
Si procede quindi con il metodo del simplesso duale.
Dobbiamo ovviamente garantire $0\leq x_j,x'_j \leq u_j$.
Attraverso le varie fasi del simplesso duale
l'ammissibilit\`a duale resta garantita,
e se una delle variabili primali utilizzate per esprimere
il tableau ($x_j$ o $x'_j$) \`e negativa allora 
un passo di pivot viene eseguito con l'effetto
di avvicinarsi all'ammissibilit\`a anche primale.
Tuttavia pu\`o accadere che una variabile attualmente
presente nel tableau ecceda il suo limite verso il basso.
Quando ci\`o succede si rimpiazza la rispettiva riga del tableau:\\

\noindent
$
\begin{array}{llrrrrl}
 &x'_j \mbox{ (o $x_j$) \hspace{0.3cm} } &
        a_{j,1} & a_{j,2} & \ldots & a_{j,n} & \; b_j\\ 
\mbox{con la riga: \hspace{3cm}}\\
 &x_j \mbox{ (o $x'_j$) \hspace{0.3cm} } &
        -a_{j,1} & -a_{j,2} & \ldots & -a_{j,n} & \; u_j - b_j\\ 
\end{array}
$

e proseguendo.  Ad esempio:

\[
   \begin{array}{l}
        \max \mbox{\ }3x_1 + 4x_2 \\
        \left\{
        \begin{array}{l}
        \begin{array}{rrrr}
             x_1 \;+&  6x_2 \;\leq &   3 \\
        \end{array} \\
        0 \leq x_1, x_2  \leq 5    
        \end{array}
        \right.
   \end{array}
\]

Introdotte le variabili
$x'_1 = 5 - x_1$ ed $x'_2 = 5 - x_2$
si sceglie di utilizzare nel tableau
proprio $x'_1$ ed $x'_2$ dacch\`e
i coefficienti della funzione obiettivo erano
entrambi positivi (e quindi?).

\[
   \begin{array}{l}
        \max \mbox{\ } 35 - 3x'_1 - 4x'_2 \\
        \left\{
        \begin{array}{l}
        \begin{array}{rrrr}
             -x'_1 \;-&  6'x_2 \;\leq & -32 \\
        \end{array} \\
        0 \leq x'_1, x'_2  \leq 5    
        \end{array}
        \right.
   \end{array}
\]

La sequenza dei tableau \`e quindi:

\[
   \begin{array}{rrrr}
         & x'_1  & x'_2 \\
      x_3 & -1  & \fbox{$-6$} &  -32  \\
       z  &  3 &  4  &  35 \\
   \end{array}
\hfill
\hspace{1cm}
{\longrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{rrrr}
         & x'_1  & x_3 \\
      x'_2 & \frac{1}{6} & -\frac{1}{6} & \frac{16}{3}  \\
       z   & \frac{7}{3} &  \frac{2}{3} & \frac{41}{3}  \\
   \end{array}
\]

Ora $\frac{16}{3} > 5$ e pertanto la prima riga del
tableau viene sostituita introducendo $x_2$:

\[
   \begin{array}{rrrr}
         & x'_1  & x_3 \\
      x_2  & \fbox{$-\frac{1}{6}$} &  \frac{1}{6} & -\frac{16}{3}  \\
       z   &  \frac{7}{3} &  \frac{2}{3} &  \frac{41}{3}  \\
   \end{array}
\hfill
\hspace{1cm}
{\longrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{rrrr}
         & x_2  & x_3 \\
      x'_1 & -6 & -1 & 2  \\
       z   & 14 &  3 & 9  \\
   \end{array}
\]

Soluzione ottima: $x_1 = 3$ ed $x_2 = 0$
con funzione obiettivo $9$.



\bigskip

{\large \bf Analisi di Sensitivit\`a}\\

Supponiamo di massimizzare una funzione obiettivo
che rappresenti un profitto o qualche altra forma
di beneficio.
I vincoli descriveranno limitazioni
in materie prime o disponibilit\`a.
Allora i valori delle variabili duali
esprimeranno il massimo ``prezzo''
che saremmo disposti a pagare per incrementare
di un'unit\`a la disponibilit\`a cui la variabile
duale si riferisce.
(Da qui il nome di ``prezzo ombra'' o ``valore marginale'').
Ricordiamo che tuttavia il significato di un prezzo
ombra \`e strettamente locale e che in generale
non sar\`a conveniente continuare a pagare sulla
base del prezzo ombra per un incremento comunque grande
di disponibilit\`a.
Ci chiediamo ora fino a dove il prezzo ombra
\'e significativo
ossia quale sia il massimo incremento 
di una certa facilit\`a
che ha senso promuovere pagando il prezzo ombra.
La risposta pu\`o essere prodotta agevolmente
con riferimento al tableau duale.\\

Si consideri ad esempio di voler massimizzare il seguente profitto:

\[
   \begin{array}{l}
        \max \mbox{\ }2x_1 + 6x_2 +3x_3\\
        \left\{
        \begin{array}{l}
        \begin{array}{rrrr}
             x_1 \;+&  2x_2 \;+& 2x_3 \;\leq &   5 \\
            2x_1 \;+&   x_2 \;+& 3x_3 \;\leq &   6 \\
        \end{array} \\
        x_1, x_2, x_3  \geq 0    
        \end{array}
        \right.
   \end{array}
\]

dove $x_1, x_2$ ed $x_3$
esprimono dei livelli non-negativi di attivit\`a,
mentre i coefficienti di destra nei vincoli
impongono limiti su determinate disponibilit\`a.
Il tableau associato alla soluzione di base ottimale \'e il seguente.

\[
   \begin{array}{rrrrr}
         & x_1  & x_2 & x_3  \\
      x_4 &  1 &  \fbox{$2$}  &  2 &  5 \\
      x_5 &  2 &  1  &  3 &  6 \\
       z  & -2 & -6  & -3 &  0 \\
   \end{array}
\hfill
\hspace{1cm}
{\longrightarrow}
\hfill
\hspace{1.2cm}
   \begin{array}{rrrrr}
         & x_1  & x_4 & x_3  \\
      x_2 & \frac{1}{2} &  \frac{1}{2} &  1  & \frac{5}{2} \\
      x_5 & \frac{3}{2} & -\frac{1}{2} &  2  & \frac{7}{2} \\
       z  &          1  &           3  &  3  & 15 \\
   \end{array}
\]

Pertanto saremmo disposti a pagare (non certo pi\`u di ) $1$
per incrementare di un'unit\`a la disponibilit\`a
nel primo vincolo.
Ma {\em quanto} siamo disposti a comperare?
Si consideri il duale dell'ultimo tableau:

\[
   \begin{array}{rrrr}
         & y_2  & y_5  \\
      y_1 &  -\frac{1}{2} & -\frac{3}{2} &  1 \\
      y_4 &  -\frac{1}{2} &  \frac{1}{2} &  3 \\
      y_3 &  -1 &  -2 &  3 \\
       z  &  -\frac{5}{2} & -\frac{7}{2} & 15 \\
   \end{array}
\]

Assumiamo di incrementare di $D$ 
la disponibilit\`a nel primo vincolo.
Il vantaggio nel considerare il duale \'e
che l'unica riga ad essere influenzata da questa
modifica nel problema \`e l'ultima.
La nuova riga pu\`o essere prodotta 
attraverso opportune sostituzioni o 
avvalendosi della PROVA DI CONTROLLO (prova del nove) della PL.\\


\[
   \begin{array}{rrrrr}
       &  & (0)  & (6) \\
       &  & \downarrow \;& \downarrow \;\\
       &  & y_2  & y_5  \\
    (0) \rightarrow & y_1 &  -\frac{1}{2} & -\frac{3}{2} &  1 \\
    (5) \rightarrow & y_4 &  -\frac{1}{2} &  \frac{1}{2} &  3 \\
    (0) \rightarrow & y_3 &  -1 &  -2 &  3 \\
       & z  &  -\frac{5}{2} & -\frac{7}{2} & 15 \\
   \end{array}
\]

  Ricordiamo che per ogni colonna vale quanto segue:
  il valore dell'ultimo elemento della colonna
  si ottiene sommando gli altri elementi della colonna ciascuno
  moltiplicato per il coefficiente della riga cui appartiene
  e sottraendo infine il valore del coefficiente associato alla colonna.\\

  \noindent
  {\em Colonna 1:} $-\frac{1}{2}(0)-\frac{1}{2}(5+D)-1(0)-(0)=-\frac{5+D}{2}$\\
  {\em Colonna 2:} $-\frac{3}{2}(0)+\frac{1}{2}(5+D)-2(0)-(6)= \frac{-7+D}{2}$\\
  {\em Colonna 3:} $1(0)+3(5+D)+3(0) = 15+3D$\\

Pertanto la riga prodotta \`e:
\[
   \begin{array}{lll}
      -\frac{5+D}{2} & \frac{-7+D}{2} & 15+3D \\
   \end{array}
\]

Pertanto il tableau resta ottimo fintanto ch\`e
$D$ non supera $7$.
Concludendo $7$ \`e il massimo incremento di diponibilit\`a
nel primo vincolo che siamo disposti ad acquistare
pagando $1$ per ogni unit\`a di incremento.
Per determinare il prezzo 
che siamo disposti a pagare per incrementi superiori
(il nuovo prezzo ombra)
dobbiamo eseguire un nuovo pivot.



\end{document}










