Il tableau¹: un sussidio alla gestione dei conteggi

La lettura di questo documento è strettamente consigliata agli studenti che intendano affrontare la provetta di Programmazione Lineare. Svolgeremo quì di seguito alcuni esercizi di preparazione alla provetta. Ci atterremo a procedimenti standard di soluzione. Proporremo inoltre l'uso del tableau. Il tableau si è 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à. E comunque la conoscenza del tableau come descritto in questo documento è intesa come parte integrante del programma del corso. Per quanto riguarda la provetta l'uso del tableau non è nè obbligatorio nè incoraggiato. Tuttavia esso è consigliato dacchè il presentare i passaggi in forma compatta aumenta chiarezza e leggibilità. In pratica il tableau offre lo strumento, di fatto standard, per incrementare la qualità del documento prodotto nello svolgimento di problemi di PL.

Buona Lettura.

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\{ \beg... ...& 12 \\ x_4 & 2 & 1 & 8 \\ z & -6 & -7 & 0 \\ \end{array}$$

Dove x₃ ed x₄ 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.

Domanda 1   A quale soluzione di base si riferisce il tableau dato sopra?

Risposta: tutte le variabili di decisione fuori base ( x₁ = x₂ = 0) mentre x₃=12 ed x₄=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 è più compattamente descritto in forma di tableau:

$${\small \begin{array}{lcrrrrrr} x_{n+1} &=& b_1 & -a_{1,1}x... ... & -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}... ... x_2, x_3 \geq 0 \end{array} \right. \end{array} \end{array}$$

$$\begin{array}{c} \mbox{\sc Dizionario Iniziale}\\ \\ \begi... ...ox{3} & 2 \\ z & -2 & -7 & 2 & 0 \\ \end{array} \end{array}$$

Domanda 2   Secondo te, perché il nel tableau sopra è stato incorniciato?

Risposta: Il è l'elemento di pivot.

Domanda 3   Come sceglieresti l'elemento di pivot direttamente dal tableau?

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è 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}}$, è l'elemento di pivot.

Esercizio 1   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?

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

$$\begin{array}{c} \mbox{\sc Dizionario Iniziale}\\ \\ \begi... ...cm} {\Huge\downarrow} {\Large\mbox{ \ $(pivot)$ }} \end{array}$$

$$\begin{array}{c} \mbox{\sc Nuovo Dizionario}\\ \\ \begin{a... ...}{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 $b= 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}} ... ..._{\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è il seguente meccanismo di pivot.

• Le variabili associate alla riga ed alla colonna di pivot si scambiano tra di loro.
• Gli elementi contenuti nella riga di pivot vengono divisi per $b= a_{\bar{\imath},\bar{\jmath}}$.
• Gli elementi contenuti nella colonna di pivot vengono divisi per $b= a_{\bar{\imath},\bar{\jmath}}$ ed invertiti in segno.
• L'elemento di pivot diviene $\frac{1}{p}$.
• Ogni elemento del tableau che non appartenga nè alla riga nè 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}$.

L'operazione di pivot è forse meglio illustrata in Figura 1.

  

Figure 1: L'operazione di PIVOT.

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{$\fr... ...& -\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è?) La soluzione primale ottima è x₂=x₄=x₅ = 0con $x_1=\frac{1}{7}$ e $x_3=\frac{6}{7}$. La soluzione duale ottima è y₁ = y₃ = 0con $y_2=-\frac{45}{7}$, $y_4=-\frac{2}{7}$ e $y_5=-\frac{4}{7}$ed è anch'essa espressa nel tableau.

Di fatto è persino possibile ricavare il tableau del problema duale dal tableau del problema primale.

$$\begin{array}{c} \mbox{\sc Tableau Primale}\\ \begin{array... ...{7} & -\frac{2}{7} & -\frac{10}{7} \\ \end{array} \end{array}$$

Dove la variabile duale y₄ corrisponde alla variabile di slack x₄ e cioè è il moltiplicatore del primo vincolo. La variabile duale y₁ corrisponde alla variabile primale x₁ che è il moltiplicatore del primo vincolo duale, ossia y₁ è la variabile di surplus nel primo vincolo duale.

Domanda 4   Quale é la regola per passare dal tableau del primale al tableau del duale?

Esercizio 2   Verificare che l'ultimo tableau proposto è il tableau per il problema duale all'ottimo.

Domanda 5   Nell'ultimo tableau il prodotto $x_i\cdot y_i$ è nullo per ogni i. Sai darne una ragione?

Attenzione!!! 1   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ò è in contrasto con il fatto che il duale del duale di un problema di PL è di nuovo il problema originale. Tale contrasto è tuttavia solo apparente: nel passare da un problema di PL al suo duale dovevo distinguere le diseguaglianze $\leq$ da quelle $\geq$.

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\{... ...y} \\ 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} & \frac{7}{2} & \frac{11}{2} & \frac{7}{2} \\ \end{array}$$

Il valore ottimo della funzione obiettivo è ora $\frac{7}{2}$. La soluzione primale ottima è x₁=x₃ = 0con $x_2=\frac{1}{2}$. La soluzione duale ottima è y₂ = 0con $y_1 = \frac{3}{2}$.

LA PROVA DI CONTROLLO

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) \\ & & \downarr... ...{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ù il valore dell'ultimo elemento della colonna eguaglia la somma degli altri elementi della colonna ciascuno moltiplicato per il coefficiente della riga cui appartiene.

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

Queste relazioni valgono per ogni tableau, non necessariamente ottimale.

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à non-negativi, come li vorremmo nell'ultimo tableau. Un tale tableau è detto duale ammissibile. Se poi tutti i coefficienti nell'ultima colonna sono non-negativi allora la soluzione di base corrente è ammissibile ed il problema è già risolto. Altrimenti si applica il metodo del simplesso duale. Una caratteristica interessante del metodo del simplesso duale sul tableau è 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à nella scelta della variabile di pivot che nel caso del simplesso duale segue la stessa filosofia già richiamata per il simplesso primale.

Domanda 6   Come sceglieresti l'elemento di pivot direttamente dal tableau?

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è si mira ad ottenere anche l'ammissibilità primale (e quidi l'ottimalità).

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

Esercizio 3   Sapresti proporre ora una seconda regola per la scelta dell'elemento di pivot nel tableau?

Ecco un esempio:

$$\begin{array}{l} \max \mbox{\ }-x_1 - 2x_2 \\ \left\{ \be... ...{11}{2} \\ z & \frac{1}{2} & 3 & \frac{7}{2} \\ \end{array}$$

Nota 1   Il metodo del simplesso duale corrisponde a risolvere il problema duale attraverso il metodo del simplesso.
Il simplesso duale conviene quando l'origine non è primale ammissibile ma duale ammissibile oppure quando nel problema di PL primale il numero di vincoli supera il numero di incognite.

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 è limitata verso il basso invece che verso l'alto, ossia $x_j \leq u_j$, ma $x_j \geq 0$ non è richiesto, allora si sostituisce x'_j = u_j - x_j.

Qualora invece una variabile non-negativa sia limitata verso il basso, tale condizione può essere considerata come uno dei vincoli del problema. Tuttavia, qualora tutte le variabili siano limitate (ed in molti casi un limite ovvio è facilmente prodotto), allora la situazione può essere girata a nostro vantaggio considerando sia la variabile x_j che la variabile x'_j = u_j - x_je 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à duale resta garantita, e se una delle variabili primali utilizzate per esprimere il tableau (x_j o x'_j) è negativa allora un passo di pivot viene eseguito con l'effetto di avvicinarsi all'ammissibilità anche primale. Tuttavia può accadere che una variabile attualmente presente nel tableau ecceda il suo limite verso il basso. Quando ciò succede si rimpiazza la rispettiva riga del tableau:

$\begin{array}{llrrrrl} &x'_j \mbox{ (o $x_j$ ) \hspace{0.3cm} } & a_{j,1} & ... ...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\{ \be... ... \\ 0 \leq x_1, x_2 \geq 5 \end{array} \right. \end{array}$$

Introdotte le variabili x'₁ = 5 - x₁ ed x'₂ = 5 - x₂si sceglie di utilizzare nel tableau proprio x'₁ ed x'₂ dacchè i coefficienti della funzione obiettivo erano entrambi positivi (e quindi?).

$$\begin{array}{l} \max \mbox{\ } 35 - 3x'_1 - 4x'_2 \\ \lef... ...\ 0 \leq x'_1, x'_2 \geq 5 \end{array} \right. \end{array}$$

La sequenza dei tableau è quindi:

$$\begin{array}{rrrr} & x'_1 & x'_2 \\ x_3 & -1 & \fbox{$-6$... ... 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₂:

$$\begin{array}{rrrr} & x'_1 & x_3 \\ x_2 & \fbox{$-\frac{1}... ..._3 \\ x'_1 & -6 & -1 & 2 \\ z & 14 & 3 & 9 \\ \end{array}$$

Soluzione ottima: x₁ = 3 ed x₂ = 0con funzione obiettivo 9.

Analisi di Sensitività

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à. Allora i valori delle variabili duali esprimeranno il massimo ``prezzo'' che saremmo disposti a pagare per incrementare di un'unità la disponibilità 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 è strettamente locale e che in generale non sarà conveniente continuare a pagare sulla base del prezzo ombra per un incremento comunque grande di disponibilità. Ci chiediamo ora fino a dove il prezzo ombra é significativo ossia quale sia il massimo incremento di una certa facilità che ha senso promuovere pagando il prezzo ombra. La risposta può 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\{... ...y} \\ x_1, x_2, x_3 \geq 0 \end{array} \right. \end{array}$$

dove x₁, x₂ ed x₃esprimono dei livelli non-negativi di attività, mentre i coefficienti di destra nei vincoli impongono limiti su determinate disponibilità. Il tableau associato alla soluzione di base ottimale é il seguente.

$$\begin{array}{rrrrr} & x_1 & x_2 & x_3 \\ x_4 & 1 & \fbox{... ...}{2} & 2 & \frac{7}{2} \\ z & 1 & 3 & 3 & 15 \\ \end{array}$$

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

$$\begin{array}{rrrr} & y_2 & y_5 \\ y_1 & -\frac{1}{2} & -\... ... & 3 \\ z & -\frac{5}{2} & -\frac{7}{2} & 15 \\ \end{array}$$

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

$$\begin{array}{rrrrr} & & (0) & (6) \\ & & \downarrow \;& \... ... 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.

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

Pertanto la riga prodotta è:

$$\begin{array}{lll} -\frac{5+D}{2} & \frac{-7+D}{2} & 15+3D \\ \end{array}$$

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