Note del corso di Ottimizzazione Discreta

(1)

Note del corso di Ottimizzazione Discreta

Laurea in Matematica Universit`a degli Studi di Padova

Marco Di Summa A.A. 2014/2015

(2)

(3)

Indice

Notazione v

1 Problemi di Programmazione Lineare 1

1.1 Concetti basilari e teorema fondamentale . . . 1

1.2 Problemi in forma standard . . . 2

2 Geometria della Programmazione Lineare 5 2.1 Insiemi convessi e poliedri . . . 5

2.2 Punti estremi, punti esposti, soluzioni di base, vertici . . . 6

2.3 Soluzioni di base per problemi in forma standard . . . 9

3 Il metodo del simplesso 13 3.1 Forma tableau e condizioni di ottimalit`a . . . 13

3.2 Iterazione del metodo del simplesso . . . 16

3.3 Esempi . . . 18

3.3.1 Un problema che ammette soluzione ottima . . . 18

3.3.2 Un problema illimitato . . . 20

3.4 Pivot . . . 21

3.5 Basi degeneri e terminazione . . . 22

3.6 Il metodo delle due fasi . . . 27

3.6.1 Esempio . . . 30

4 Teoria della Dualit`a 33 4.1 Dualit`a per problemi in forma standard . . . 33

4.1.1 Dualit`a, basi ottime e metodo del simplesso . . . 34

4.2 Dualit`a per problemi in altre forme . . . 35

4.2.1 Forma canonica . . . 35

4.2.2 Altre forme . . . 36

4.2.3 Duale del duale . . . 37

4.2.4 Dualit`a in generale . . . 38

4.3 Scarti complementari . . . 39

4.4 Interpretazione economica della dualit`a . . . 40

4.4.1 Mercato ombra . . . 40

4.4.2 Variabili duali come prezzi di equilibrio . . . 41

4.5 Inammissibilit`a e Lemma di Farkas . . . 42

4.5.1 Forma standard . . . 43

4.5.2 Altre forme . . . 44 iii

(4)

4.6 Problemi illimitati . . . 45

4.7 Metodo del Simplesso duale . . . 47

5 Grafi e complessit`a degli algoritmi 51 5.1 Grafi . . . 51

5.1.1 Grafi non orientati . . . 51

5.1.2 Grafi orientati . . . 54

5.2 Complessit`a degli algoritmi . . . 56

5.2.1 Complessit`a della Programmazione Lineare . . . 60

6 Problemi di Cammino Minimo 63 6.1 Cammini di lunghezza minima . . . 64

6.2 L’algoritmo di Bellman–Ford . . . 66

6.3 Cammini minimi e programmazione lineare . . . 70

6.4 Trovare cicli di costo negativo . . . 74

7 Il problema del Flusso Massimo 77 7.1 Algoritmo di Ford–Fulkerson . . . 78

7.1.1 Cammini aumentanti . . . 78

7.1.2 Grafo ausiliario . . . 79

7.1.3 Teorema del Flusso Massimo e Taglio Minimo . . . 80

7.1.4 L’algoritmo di Ford–Fulkerson . . . 81

7.2 Flusso massimo e programmazione lineare . . . 84

(5)

Notazione

In queste note, un vettore x ∈ Rⁿ`e considerato sempre come vettore colonna e trattato come una matrice n × 1. Dunque, dati x, y ∈ Rⁿ, il valore

x^Ty = y^Tx = x1y1+⋅ ⋅ ⋅ + x_ny_n

`e il prodotto scalare tra x e y.

Dati due vettori x, y ∈ Rⁿ, scriveremo

x ≥ y

per indicare che xj ≥yj per ogni j ∈ {1, . . . , n}; scriveremo x > y

per indicare che x_j >y_j per ogni j ∈ {1, . . . , n}; invece scriveremo x ≠ y

se esiste almeno un indice j ∈ {1, . . . , n} tale che xj ≠yj.

Denoteremo con 0 il vettore nullo, dove la dimensione di tale vettore sarà di volta in volta chiara dal contesto. Ad esempio, dato x ∈ Rⁿ, quando scriveremo x ≥ 0 sarà sottinteso che le dimensioni dei due vettori x e 0 sono compatibili e che dunque 0 è il vettore nullo di Rⁿ. Analogamente, 0 indicherà talvolta la matrice nulla di dimensioni opportune.

v

(6)

(7)

Capitolo 1

Problemi di Programmazione Lineare

In questo capitolo verranno date alcune definizioni e nozioni di base sulla Programmazione Lineare.

1.1 Concetti basilari e teorema fondamentale

Un problema di Programmazione Lineare (detto anche programma lineare) `e un problema di ottimizzazione vincolata in cui la funzione da massimizzare (o minimizzare) `e lineare e tutti i vincoli sono descritti da equazioni e/o disequazioni lineari:

max (o min) c1x1+ ⋅ ⋅ ⋅ + cnx_n (1.1) soggetto a a¹¹x1+ ⋅ ⋅ ⋅ + a¹nx_n∼b1 (1.2)

⋮ ⋮

a_m1x1+ ⋅ ⋅ ⋅ + a_mnx_n∼b_m, (1.3) dove ciascuno dei simboli “∼” sta per uno degli operatori “≥”, “≤” o “=” (si noti che non sono ammesse disequazioni strette). Nel problema (1.1)–(1.3), x¹, . . . , x_n sono le variabili (cioè le incognite), (1.1) è la funzione obiettivo e (1.2)–(1.3) sono i vincoli. Tutti i dati aij, b_i, c_j (i = 1, . . . , m, j = 1, . . . , n) sono numeri reali noti. Le variabili x1, . . . , xn possono prendere qualunque valore reale, purché esse soddisfino tutti i vincoli. Si noti che l’espressione (1.1) può essere scritta più concisamente come c^Tx. In modo del tutto analogo, un vincolo del tipo ai1x1+ ⋅ ⋅ ⋅ + ainxn∼bi (dove i ∈ {1, . . . , m}) sarà spesso indicato con la notazione a^T_ix ∼ bi.

Ogni vettore x ∈ Rⁿ che soddisfi (1.2)–(1.3) è detto soluzione ammissibile del problema. Il corrispondente valore c^Txè il valore o costo della soluzione ammissibile x. L’insieme di tutte le soluzioni ammissibili di un programma lineare è detto regione ammissibile. Un vettore

¯

x ∈ Rⁿè una soluzione ottima del programma lineare se ¯xè ammissibile e c^Tx ≥ c¯ ^Txper ogni x ammissibile (la condizione è c^Tx ≤ c¯ ^Tx se il problema è di minimizzazione). Il corrispondente valore c^Tx¯è detto valore ottimo del problema.

Enunciamo subito un importante risultato, noto come Teorema fondamentale della Pro- grammazione Lineare. La dimostrazione verr`a data nel Capitolo 3 come conseguenza della cor- rettezza di un algoritmo (il metodo del simplesso) per risolvere problemi di programmazione lineare.

1

(8)

Teorema 1.1 (Teorema fondamentale della Programmazione Lineare) Dato un programma lineare, vale una e una sola delle seguenti alternative:

(a) il problema ha almeno una soluzione ottima;

(b) il problema `e inammissibile, cio`e non ha soluzioni ammissibili;

(c) il problema è illimitato, cioè per ogni α ∈ R esiste una soluzione ammissibile x tale che c^Tx ≥ α (c^Tx ≤ αse il problema è di minimizzazione).

Menzioniamo il fatto che alcuni testi indicano come Teorema fondamentale della Program- mazione Lineare un risultato più forte del Teorema 1.1, in cui viene precisato che se si verifica il caso (a) allora c’è una soluzione ottima con particolari proprietà: questo sarà discusso nel Capitolo 2 (in particolare, nel Teorema 2.6).

1.2 Problemi in forma standard

Mostriamo ora che possiamo ridurci senza perdita di generalit`a a studiare problemi di programmazione lineare di una forma particolare, detta forma standard:

max c^Tx (1.4)

s.a Ax = b (1.5)

x ≥0, (1.6)

dove A ∈ R^m×n, c ∈ Rⁿ, b ∈ R^m sono i dati del problema e x ∈ Rⁿ`e il vettore delle variabili. Si noti che la scrittura Ax = b `e un modo compatto di indicare il sistema di m equazioni lineari a^T_ix = b_i per i = 1, . . . , m (in altre parole, ai1x1+ ⋅ ⋅ ⋅ + ainx_n=b_i per i = 1, . . . , m).

Due programmi lineari P1 e P2 sono detti equivalenti quando, per ogni α ∈ R, P1 ha una soluzione ammissibile di costo α se e solo se P² ha una soluzione ammissibile di costo α. In particolare, se P1 e P2 sono programmi lineari equivalenti, si verifica immediatamente che valgono le seguenti propriet`a:

P1 ha una soluzione ammissibile se e solo se P2 ha una soluzione ammissibile;

per ogni α ∈ R, P¹ ha una soluzione ottima di costo α se e solo se P² ha una soluzione ottima di costo α;

P1 `e illimitato se e solo se P2 `e illimitato.

Proposizione 1.2 Ogni programma lineare `e equivalente ad un programma lineare in forma standard.

Dimostrazione. Consideriamo un generico problema di programmazione lineare, che avr`a dunque la forma (1.1)–(1.3), e mostriamo come esso sia equivalente ad un problema in forma standard.

Si noti anzitutto che se (1.1)–(1.3) è un problema di minimizzazione (vogliamo cioè determinare min c^Tx), tale problema è equivalente al programma lineare in cui la (1.1) è sostituita da − max −c^Tx. Pertanto possiamo assumere senza perdita di generalità che (1.1)–(1.3) sia un problema di massimizzazione.

(9)

1.2. PROBLEMI IN FORMA STANDARD 3 Diciamo che una variabile xjè una variabile non-negativa se il sistema (1.2)–(1.3) contiene esplicitamente il vincolo xj≥0; altrimenti la variabile è detta libera. Nel passaggio alla forma standard sarà utile trattare le variabile non-negative e quelle libere in modo diverso.

Consideriamo una disuguaglianza della forma a^T_ix ≥ b_i che non sia un vincolo di non- negatività su una variabile. Tale disuguaglianza è equivalente a −a^T_ix ≤ −bi. Ne segue che possiamo assumere che ciascun vincolo del problema (eccetto quelli che impongono la non- negatività di qualche variabile) sia del tipo a^T_ix ≤ b_i o a^T_ix = b_i.

Consideriamo ora un vincolo della forma a^T_ix ≤ b_i. Aggiungiamo al problema una variabile di scarto (o di slack) s_i, e rimpiazziamo il vincolo precedente con i seguenti:

a^T_ix+ si=bi, si≥0. (1.7)

Si noti che se x soddisfa a^T_ix ≤ b_i, allora, ponendo si =b_i− a^T_ix, le condizioni (1.7) risultano verificate. Viceversa, se x ed si soddisfano (1.7), allora x soddisfa il vincolo di partenza a^T_ix ≤ b_i. Pertanto, poich´e non abbiamo modificato la funzione obiettivo, il problema cos`ı ottenuto `e equivalente a quello di partenza.

Abbiamo finora dimostrato che ogni programma lineare è equivalente ad un programma lineare di massimizzazione in cui tutti i vincoli (eccetto quelli che impongono la non-negatività di qualche variabile) sono equazioni. Per arrivare ad un problema in forma standard, dobbiamo però avere il vincolo di non-negatività su tutte le variabili. Resta dunque da capire come gestire le variabili libere.

Supponiamo che la variabile xj sia libera. Basandoci sulla semplice osservazione che ogni numero reale pu`o essere scritto come differenza di due numeri non-negativi, introduciamo due variabili non-negative (x^′_j e x^′′_j) ed imponiamo i vincoli

x_j =x^′_j− x^′′_j, x^′_j, x^′′_j ≥0.

Inoltre, sostituiamo x_j con x^′_j− x^′′_j nella funzione obiettivo e in tutti i vincoli del problema.

Otteniamo cos`ı un programma lineare in cui xj non compare e le nuove variabili introdotte sono non-negative. Il problema che ricaviamo `e equivalente a quello di partenza: data una soluzione ammissibile del nuovo problema, otteniamo una soluzione ammissibile del problema originario con lo stesso costo ponendo xj =x^′_j− x^′′_j; viceversa, data una soluzione ammissibile del problema di partenza, otteniamo una soluzione ammissibile del nuovo problema con lo stesso costo scegliendo valori non-negativi per x^′_j e x^′′_j tali che x_j =x^′_j − x^′′_j (possiamo porre, ad esempio, x^′_j =max{0, xj} e x^′′_j =max{0, −xj}).

Ci siamo dunque ridotti ad un problema in forma standard equivalente a quello iniziale.

◻ Si noti che, oltre a mostrare che un qualunque programma lineare P¹ `e equivalente ad un programma lineare P2 in forma standard, la dimostrazione della proposizione precedente ci dice come da una soluzione di P2 di costo α possiamo ricavare una soluzione di P1 di costo α.

In particolare, da una soluzione ottima di P2 possiamo ricavare una soluzione ottima di P1. Dunque il fatto di restringersi ai soli problemi in forma standard non pone alcuna limitazione alla generalit`a della trattazione.

(10)

(11)

Capitolo 2

Geometria della Programmazione Lineare

In questo capitolo verranno introdotte alcune nozioni della teoria dei poliedri che permet- teranno di cogliere gli aspetti geometrici della Programmazione Lineare e del suo algoritmo risolutivo pi`u noto, trattato nel capitolo successivo.

2.1 Insiemi convessi e poliedri

Un semispazio chiuso in Rⁿ`e un insieme della forma {x ∈ Rⁿ∶ a^Tx ≤ β}, dove a ∈ Rⁿ∖ {0} e β ∈ R. Scritto per esteso, un semispazio chiuso `e l’insieme dei punti di Rⁿ che soddisfano una disequazione del tipo a1x1+ ⋅ ⋅ ⋅ + anx_n≤β.

Un poliedro in Rⁿ è l’intersezione di un numero finito di semispazi chiusi. In altre parole, un poliedro è un insieme che può essere scritto nella forma {x ∈ Rⁿ∶ Ax ≤ b}, dove A ∈ R^m×n e b ∈ R^m. Si noti che la regione ammissibile di un qualunque problema di programmazione lineare è un poliedro (eventuali vincoli scritti sotto forma di equazioni possono essere sostituiti ciascuno con una coppia di disequazioni opposte).

Un insieme K ⊆ Rⁿ si dice convesso se, per ogni coppia di punti y, z ∈ K, il segmento di retta che congiunge y e z `e contenuto in K, cio`e se λy + (1 − λ)z ∈ K per ogni scelta di y, z ∈ K e λ ∈[0,1].

Proposizione 2.1 Valgono le seguenti propriet`a:

(i) Ogni semispazio chiuso `e convesso.

(ii) L’intersezione di insiemi convessi `e un insieme convesso.

(iii) Ogni poliedro `e convesso.

Dimostrazione. (i) Sia S il semispazio chiuso definito dalla disequazione a^Tx ≤ β e scegliamo arbitrariamente y, z ∈ S e λ ∈[0,1]. Allora

a^T(λy + (1 − λ)z) = λa^Ty+(1 − λ)a^Tz ≤ λβ+(1 − λ)β = β,

dove la disuguaglianza vale perch´e y, z ∈ S, λ ≥ 0 e 1 − λ ≥ 0. Dunque λy +(1 − λ)z ∈ S, da cui segue che S `e convesso.

5

(12)

(ii) Per semplicità di scrittura diamo la dimostrazione per il caso in cui vengono intersecati due insiemi convessi, ma l’argomento è identico per il caso di più insiemi convessi (anche se non in numero finito). Siano K1e K2due insiemi convessi e definiamo K = K1∩K2. Scegliamo arbitrariamente y, z ∈ K e λ ∈[0,1]. Allora il punto λy + (1 − λ)z appartiene sia a K¹ che a K2 (in quanto questi due insiemi sono convessi) e dunque a K. Ne segue che K è convesso.

(iii) Poich´e un poliedro `e l’intersezione di un numero finito di semispazi chiusi, il risultato

segue dalle propriet`a (i) e (ii). ◻

Chiudiamo questa sezione con una definizione. Un punto x ∈ Rⁿ è detto combinazione convessa dei punti y, z ∈ Rⁿ se x è contenuto nel segmento di retta che congiunge y e z, cioè se esiste λ ∈[0,1] tale che x = λy + (1 − λ)z. Se, inoltre, x ≠ y e x ≠ z, allora si dice che x è combinazione convessa propria di y e z; si noti che in tal caso si ha necessariamente λ ∈]0,1[.

2.2 Punti estremi, punti esposti, soluzioni di base, vertici

Dato un insieme convesso K ⊆ Rⁿ, un punto ¯x ∈ K è un punto estremo di K se ¯x non è combinazione convessa propria di due punti di K, cioè se non esistono due punti y, z ∈ K ∖{x}

e λ ∈]0,1[ tali che ¯x = λy + (1 − λ)z.

Dato un insieme convesso K ⊆ Rⁿ, un punto ¯x ∈ K è un punto esposto di K se esiste c ∈ Rⁿ tale che c^Tx < c^Tx¯ per ogni x ∈ K ∖{¯x}. In altre parole, ¯x è un punto esposto di K se esiste una funzione obiettivo lineare per cui ¯x è l’unico punto ottimale di K.

Come vedremo più sotto, ogni punto esposto di un insieme convesso K è un punto estremo di K, ma la Figura 2.1 mostra che il viceversa non è vero. Dimostreremo, tuttavia, che i concetti di punto estremo e punto esposto coincidono nel caso in cui K sia un poliedro (Figura 2.2). Prima di verificare questo fatto, introduciamo alcune ulteriori definizioni.

K

s

❅❅

■c

¯ x

s

¯ z

s

!!✒ c

¯ y

¯ s w

su¯

Figura 2.1: Un insieme convesso K e tre suoi punti estremi ¯x, ¯y, ¯z. Di questi, solo ¯xe ¯y sono anche punti esposti di K. Per ciascuno di questi due punti è rappresentato un vettore c come nella definizione di punto esposto. I punti ¯u e ¯w, invece, non sono né punti estremi né punti esposti di K.

Consideriamo un generico sistema di equazioni e/o disequazioni lineari in Rⁿ:

a^T_ix = b_i, i =1, . . . , k (2.1) a^T_ix ≤ b_i, i = k+ 1, . . . , m. (2.2)

(13)

2.2. PUNTI ESTREMI, PUNTI ESPOSTI, SOLUZIONI DI BASE, VERTICI 7

P

s

❅❅

■c

¯ x

s

¯ z

❙❙✇ c

s

!!✒ c

¯ y

sw¯

!!

✠c

Figura 2.2: Nel caso di un poliedro P , i punti estremi sono esattamente i punti esposti.

I vincoli (2.1)–(2.2) sono detti linearmente indipendenti se i vettori {aⁱ}^i=1,...,m sono linearmente indipendenti. Dati un punto ¯x ∈ Rⁿe un indice i ∈{1,... ,m}, l’i-esimo vincolo `e attivo in ¯xse a^T_ix = b¯ _i.

Un punto ¯x ∈ Rⁿ`e detto una soluzione di base del sistema di vincoli (2.1)–(2.2) se (i) a^T_ix = b¯ i per i = 1, . . . , k,

(ii) esistono n vincoli del sistema attivi in ¯xche sono linearmente indipendenti.

Si noti che non `e richiesto che una soluzione di base soddisfi anche tutti i vincoli di disuguaglianza (2.2); quando questo avviene, la soluzione di base `e detta soluzione di base ammissibile.

Teorema 2.2 Sia P ⊆ Rⁿil poliedro definito dal generico sistema (2.1)–(2.2). Dato un punto

¯

x ∈ P, le seguenti affermazioni sono equivalenti:

(i) ¯x `e un punto estremo di P ; (ii) ¯x `e un punto esposto di P ;

(iii) ¯x `e una soluzione di base ammissibile del sistema (2.1)–(2.2).

Dimostrazione. (i) ⇒ (iii) Supponiamo che ¯x sia un punto estremo di P. Poiché ¯x ∈ P, ¯x soddisfa tutti i vincoli del sistema. Allora, per dimostrare che ¯x è una soluzione di base ammissibile, basterà dimostrare che esistono n vincoli del sistema attivi in ¯xche sono linearmente indipendenti.

Scriviamo il sistema (2.1)–(2.2) nella forma matriciale Ax ∼ b, dove A ∈ R^m×n, b ∈ R^m e la notazione “∼” indica che su ciascuna riga del sistema appare il simbolo “=” oppure il simbolo

“≤”. Sia A⁼ la sottomatrice di A formata dalle righe che corrispondono ai vincoli del sistema che sono attivi in ¯x; sia A^< la sottomatrice di A formata dalle righe rimanenti. Definiamo b⁼ e b^< come i sottovettori di b corrispondenti ad A⁼ e A^< rispettivamente. Allora valgono le condizioni

A⁼x = b¯ ⁼ A^<x < b¯ ^<.

Dire che esistono n vincoli del sistema attivi in ¯xche sono linearmente indipendenti equivale a dire che rk(A⁼) = n. Supponiamo per contraddizione che rk(A⁼) < n. Allora esiste un vettore

(14)

non-nullo v ∈ Rⁿ tale che A⁼v = 0. Scelto uno scalare ε > 0 e definiti i vettori y = ¯x+ εv e z =x¯− εv, si ha

A⁼y = A⁼x¯+ εA⁼v = A⁼x¯+ 0 = b⁼, A⁼z = A⁼x¯− εA⁼v = A⁼x¯− 0 = b⁼; inoltre, se ε `e scelto sufficientemente piccolo, si ha

A^<y = A^<x¯+ εA^<v ≤ b^<, A^<z = A^<x¯− εA^<v ≤ b^<.

Dunque y e z soddisfano tutti i vincoli del sistema e sono quindi punti di P . Tuttavia, poiché ¯x = ¹₂y+¹₂z, ¯x ≠ y e ¯x ≠ z, si ha che ¯x è combinazione convessa propria di y e z, in contraddizione con il fatto che ¯xè un punto estremo di P .

(iii) ⇒ (ii) Supponiamo che ¯x sia una soluzione di base ammissibile. Definiamo A⁼, A^<, b⁼e b^< come sopra. Possiamo assumere senza perdita di generalit`a che, per un qualche intero p ≥0, le righe di A⁼ siano i vettori a^T1, . . . , a^T_p e che b⁼=(b¹, . . . , b_p)^T. Scegliamo c = a¹+ ⋅ ⋅ ⋅ + ap: dimostreremo che c^Tx < c^Tx¯ per ogni x ∈ P ∖{¯x}, da cui ¯x `e un punto esposto di P.

Per ogni x ∈ P si ha

c^Tx = a^T1x+ ⋅ ⋅ ⋅ + a^T_px ≤ b1+ ⋅ ⋅ ⋅ + bp=a^T1x¯+ ⋅ ⋅ ⋅ + a^T_px = c¯ ^Tx.¯

Dunque c^Tx ≤ c^Tx¯ per ogni x ∈ P e l’uguaglianza vale se e solo se a^T_ix = b_i per i = 1, . . . , p, cioè se e solo se A⁼x = b⁼. Poiché ¯xè una soluzione di base, la matrice A⁼ ha rango n, dunque il sistema A⁼x = b⁼ ha ¯xcome unica soluzione. Pertanto c^Tx < c^Tx¯ per ogni punto x ∈ P ∖{¯x}.

(ii) ⇒ (i) Supponiamo che ¯x sia un punto esposto di P e sia c ∈ Rⁿ tale che c^Tx < c^Tx¯ per ogni x ∈ P ∖{¯x}. Assumiamo per assurdo che ¯x non sia un punto estremo di P. Allora esistono due punti y, z ∈ P ed uno scalare λ ∈]0,1[ tali che ¯x = λy + (1 − λ)z, ¯x ≠ y e ¯x ≠ z.

Per la scelta di c, abbiamo c^Ty < c^Tx¯ e c^Tz < c^Tx. Ne segue che¯

c^Tx = c¯ ^T(λy + (1 − λ)z) = λc^Ty+(1 − λ)c^Tz < λc^Tx¯+(1 − λ)c^Tx = c¯ ^Tx,¯

dove la disuguaglianza vale perch´e λ > 0 e 1 − λ > 0. Abbiamo dunque ottenuto la contraddi-

zione c^Tx < c¯ ^Tx.¯ ◻

Si noti che per dimostrare l’implicazione(ii) ⇒ (i) non abbiamo sfruttato il fatto che P `e un poliedro. Ne segue che ogni punto esposto di un insieme convesso K `e un punto estremo di K, mentre il viceversa vale solo per poliedri. (Infatti per mostrare l’implicazione inversa siamo passati attraverso il concetto di soluzione di base ammissibile, che ha senso solo per sistemi lineari e dunque solo per poliedri.)

I punti estremi (cio`e i punti esposti) di un poliedro sono anche detti vertici. Non diamo qui la definizione di vertice per un generico insieme convesso, ma menzioniamo il fatto che nel caso di poliedri la nozione di vertice coincide con quelle di punto estremo e punto esposto.

Nel seguito vedremo che le soluzioni di base ammissibili giocano un ruolo fondamentale in programmazione lineare. Conviene sempre tenere presente l’interpretazione geometrica delle soluzioni di base ammissibili, cio`e il fatto che esse corrispondono ai punti estremi (cio`e ai punti esposti) della regione ammissibile.

(15)

2.3. SOLUZIONI DI BASE PER PROBLEMI IN FORMA STANDARD 9

2.3 Soluzioni di base per problemi in forma standard

Sia P ⊆ Rⁿ un poliedro definito da un sistema lineare in forma standard

Ax = b (2.3)

x ≥0, (2.4)

con A ∈ R^m×n e b ∈ R^m. Nel seguito assumeremo che P ≠ ∅. In particolare, il sistema Ax = b ammette una soluzione, da cui segue che rk(A) = rk(A ∣ b). Possiamo assumere senza perdita di generalità che le righe di A siano linearmente indipendenti (cioè che rk(A) = m): in caso contrario, se si avesse cioè rk(A) = m^′ < m, potremmo tenere nel sistema m^′ equazioni linearmente indipendenti e rimuovere le altre senza alterare l’insieme delle soluzioni ammissibili, riducendoci cos`ı ad avere un sistema A^′x = b^′ con m^′ righe e rk(A^′) = m^′.

Vogliamo caratterizzare le soluzioni di base del sistema (2.3)–(2.4). Da ora in avanti, denoteremo con A_j, j = 1, . . . , n, le colonne di A. Dato un sottoinsieme S ⊆ {1,... ,n}, indicheremo con AS la sottomatrice di A formata dalle colonne Aj con j ∈ S.

Data una matrice A ∈ R^m×n di rango m, un insieme B ⊆{1,... ,n} `e detto una base di A se∣B∣ = m e la matrice AB`e invertibile. Con riferimento ad un sistema in forma standard del tipo (2.3)–(2.4), B viene anche detta una base del sistema.

I risultati seguenti giustificano l’utilizzo del termine “base”.

Proposizione 2.3 Un punto ¯x ∈ Rⁿ `e una soluzione di base del sistema in forma standard (2.3)–(2.4) se e solo se A¯x = b ed esiste una base B di A tale che ¯x_j=0 per ogni j ∉ B.

Dimostrazione. Supponiamo che ¯x sia una soluzione di base del sistema (2.3)–(2.4). Allora esistono n vincoli attivi in ¯xche sono linearmente indipendenti. Si noti che gli m vincoli del sistema Ax = b sono necessariamente attivi in ¯x. Inoltre, poich´e rk(A) = m, tali vincoli sono linearmente indipendenti. Dunque esistono n−m vincoli di non-negativit`a attivi in ¯x, diciamo le disuguaglianze xj ≥0 per j ∈ N , dove N ⊆{1,... ,n} e ∣N∣ = n − m, tali che i vincoli

a^T_ix = bi, i =1, . . . , m (2.5)

x_j ≥0, j ∈ N, (2.6)

siano linearmente indipendenti. In altre parole, la matrice del sistema (2.5)–(2.6) `e invertibile.

A meno di permutare le variabili, possiamo assumere che N ={m+1,... ,n}. Definiamo inoltre B ={1,... ,m}. Allora la matrice del sistema (2.5)–(2.6) `e la seguente:

(A_B A_N

0 I ), (2.7)

dove I denota la matrice identità (n − m) × (n − m). Poiché, come detto, la matrice (2.7) è invertibile, anche ABè invertibile. Dunque B è una base di A. Inoltre, siccome i vincoli xj ≥0 per j ∈ N sono attivi in ¯x, si ha ¯x_j=0 per j ∈ N (cioè per j ∉ B), come volevasi dimostrare.

Viceversa, supponiamo che A¯x = bed esista una base B di A tale che ¯xj=0 per ogni j ∉ B.

A meno di permutare le variabili, possiamo assumere che B ={1,... ,m}. Definiamo inoltre N ={m+1,... ,n}. Poiché B è una base di A, la sottomatrice A^B è invertibile, dunque anche la matrice (2.7) è invertibile. Pertanto i vincoli (2.5)–(2.6) sono linearmente indipendenti e sono attivi in ¯x, cioè ¯x è una soluzione di base del sistema (2.3)–(2.4). ◻

(16)

Corollario 2.4 Un punto ¯x ∈ Rⁿ `e una soluzione di base del sistema in forma standard (2.3)–(2.4) se e solo se A¯x = b e i vettori {A^j}^j∈S sono linearmente indipendenti, dove S = {j ∈ {1,... ,n} ∶ ¯xj≠0}.

Dimostrazione. Se ¯x`e una soluzione di base del sistema (2.3)–(2.4), allora per la proposizione precedente esiste una base B di A tale che {A^j}^j∈S ⊆ {A^j}^j∈B; inoltre, tali vettori sono linearmente indipendenti per definizione di base.

Viceversa, se i vettori{Aj}j∈Ssono linearmente indipendenti, allora possiamo scegliere una base B di A tale che S ⊆ B. Dunque ¯x_j=0 per ogni j ∉ B. Per la proposizione precedente, ¯x

`e una soluzione di base del sistema (2.3)–(2.4). ◻

Osservazione 2.5 Data una base B del sistema in forma standard (2.3)–(2.4), esiste un unico vettore ¯x che soddisfa A¯x = b e ¯x_j=0 per j ∉ B.

Dimostrazione. A meno di permutare le variabili, possiamo assumere che B ={1,... ,m}. Sia inoltre N ={m + 1,... ,n}. Se x ∈ Rⁿ `e un vettore che soddisfa Ax = b e xj =0 per j ∉ B, allora

b = Ax = A_Bx_B+ A_Nx_N =A_Bx_B.

Poiché B è una base di A, la matrice A_B è invertibile. Pertanto l’unica scelta possibile per x_Bè data da xB=A⁻¹_Bb. Ne segue che vi è un unico vettore ¯xche soddisfa A¯x = b e ¯x_j =0 per j ∉ B, precisamente il vettore ¯xle cui componenti sono definite da ¯x_B=A⁻¹_Bbe ¯x_N =0. ◻ L’osservazione precedente permette di dare la seguente importante definizione. Data una base B del sistema in forma standard (2.3)–(2.4), la soluzione di base relativa a B è l’unico vettore ¯x che soddisfa A¯x = be ¯x_j=0 per j ∉ B, cioè il vettore definito da

¯

x_B=A⁻¹_Bb

¯ xN =0.

Se ¯x è una soluzione ammissibile del sistema (2.3)–(2.4), cioè se ¯x_B = A⁻¹_Bb ≥0, allora B è detta una base ammissibile del sistema (2.3)–(2.4).

Siamo ora in grado di dimostrare il seguente importante risultato, che viene spesso considerato parte integrante del Teorema Fondamentale della Programmazione Lineare (Teore- ma 1.1).

Teorema 2.6 Se un programma lineare in forma standard

max c^Tx (2.8)

s.a Ax = b (2.9)

x ≥0 (2.10)

ha una soluzione ottima, allora ha una soluzione ottima che `e una soluzione di base ammissibile.

Dimostrazione. Tra tutte le soluzioni ottime del problema dato (ce n’`e almeno una per ipotesi), ne scegliamo una che abbia il numero massimo di componenti nulle e la chiamiamo

¯

x. Dimostreremo che ¯x`e una soluzione di base (ovviamente ammissibile).

(17)

2.3. SOLUZIONI DI BASE PER PROBLEMI IN FORMA STANDARD 11 Supponiamo che ¯xnon sia una soluzione di base e definiamo S ={j ∶ ¯x^j>0} = {j ∶ ¯x^j ≠0}.

Per il Corollario 2.4, i vettori{A^j}^j∈Ssono linearmente dipendenti. Dunque possiamo ottenere il vettore nullo come combinazione lineare di tali vettori, dove i coefficienti della combinazione non sono tutti nulli: in altre parole, esiste v ∈ R^S tale che v ≠ 0 e ASv =0. Possiamo assumere senza perdita di generalit`a che v abbia almeno una componente positiva (in caso contrario basta rimpiazzare v con −v). Estendiamo v ad un vettore ¯v ∈ Rⁿ come segue:

¯ v_j =⎧⎪⎪

⎨⎪⎪⎩

v_j, j ∈ S 0, j ∉ S.

Si noti che A¯v =0 e ¯v ha almeno una componente positiva.

Per ogni ε ≥ 0 si ha A(¯x ± ε¯v) = A¯x ± εA¯v = b; inoltre, poich´e ¯v^j =0 per ogni j ∉ S, si ha

¯

vj =0 per ogni j tale che ¯xj =0. Allora, se ε > 0 è scelto sufficientemente piccolo, entrambi i punti ¯x+ ε¯v e ¯x− ε¯v sono soluzioni ammissibili. Inoltre, poiché ¯x è una soluzione ottima, si ha

c^Tx ≥ c¯ ^T(¯x + ε¯v) = c^Tx¯+ εc^T¯v, c^Tx ≥ c¯ ^T(¯x − ε¯v) = c^Tx¯− εc^Tv,¯ da cui segue che c^Tv =¯ 0.

Consideriamo un punto della forma ¯x− ε¯v con ε ≥ 0. Poiché c^T¯v =0, il punto ¯x− ε¯v è una soluzione ottima per ogni ε ≥ 0 per cui il punto stesso è ammissibile.

Ci chiediamo ora quali siano i valori ε ≥ 0 per cui il punto ¯x− ε¯v `e ammissibile. Questo avviene se e solo se ¯x_j− ε¯v_j ≥ 0 per ogni j = 1, . . . , n. Si noti che se j `e un indice tale che

¯

vj ≤0, allora, poiché ¯xj ≥ 0, si avrà ¯xj − ε¯vj ≥ 0 per ogni ε ≥ 0. Dunque il punto ¯x− ε¯v è ammissibile se e solo se ¯x_j− ε¯v_j ≥0 per ogni j ∈{1,... ,n} tale che ¯vj>0, cioè se e solo se

ε ≤x¯_j/¯v^j per ogni j ∈{1,... ,n} tale che ¯v^j >0. (2.11) Sia h un indice tale che ¯v_h>0 per cui il valore ¯x_h/¯v^h sia il pi`u piccolo possibile. Come assunto in precedenza, il vettore ¯v ha almeno una componente positiva, dunque h `e ben definito.

Poniamo ora ε = ¯x_h/¯vh e x^∗ = x¯− ε¯v. Poich´e ε soddisfa la condizione (2.11), il punto x^∗ `e ammissibile. Inoltre, x^∗_h =x¯_h− ε¯v_h =0, mentre, per ogni j ∉ S, si ha x^∗_j =x¯_j− ε¯v_j =0 − 0 = 0.

Dunque x^∗ `e una soluzione ottima con almeno una componente nulla in pi`u rispetto a ¯x, il

che contraddice la scelta di ¯x. ◻

Il teorema precedente chiarisce perché la programmazione lineare sia considerata parte dell’ottimizzazione discreta nonostante la regione ammissibile di un programma lineare sia una regione continua: il fatto che, quando esiste una soluzione ottima, ce ne sia una che è una soluzione di base ammissibile permette di limitare la ricerca dell’ottimo alle sole soluzioni di base ammissibili, che sono in numero finito (come segue dalla definizione di base). Dunque la programmazione lineare può essere vista come un problema di ottimizzazione discreta. Come vedremo nel capitolo successivo, questa osservazione è alla base del metodo del simplesso.

Il teorema precedente ha anche la seguente immediata conseguenza.

Corollario 2.7 Se un sistema in forma standard ha una soluzione ammissibile, allora ha una soluzione di base ammissibile.

Dimostrazione. Un sistema in forma standard ha la forma (2.9)–(2.10). Scegliendo c = 0 come vettore dei coefficienti della funzione obiettivo, ogni soluzione ammissibile del problema

(18)

(2.8)–(2.10) è una soluzione ottima. Il teorema precedente mostra che il programma lineare cos`ı ottenuto ha una soluzione ottima che è una soluzione di base ammissibile; nel nostro caso, possiamo parafrasare dicendo che il problema ha una soluzione ammissibile che è una

soluzione di base ammissibile. ◻

Chiudiamo il capitolo con un’importante precisazione. Mentre abbiamo visto che ogni sistema in forma standard che ammetta soluzione ha una soluzione di base ammissibile, questo non `e sempre vero per sistemi lineari generali. Ad esempio, il sistema di vincoli

x1+ x2+ x3≤1 x1+ x2 ≥0 x3≥0

non ha alcuna soluzione di base, in quanto non `e possibile estrarre dal sistema tre vincoli linearmente indipendenti. Tuttavia il sistema ammette soluzioni (ad esempio l’origine). Geo- metricamente, questo sistema definisce un poliedro non vuoto privo di vertici e dunque privo di soluzioni di base ammissibili.

(19)

Capitolo 3

Il metodo del simplesso

Come visto nel capitolo precedente, dato un programma lineare in forma standard che abbia una soluzione ottima, esiste una soluzione di base ottima. Dunque, in linea di principio, si potrebbe cercare una soluzione ottima enumerando tutte le soluzioni di base ammissibili del programma lineare e controllando quale tra queste d`a il miglior valore della funzione obiettivo. Questo approccio, tuttavia, richiederebbe un tempo eccessivo e sarebbe inapplicabile nella pratica, in quanto il numero di soluzioni di base di un programma lineare, nonostante sia sempre finito, pu`o essere estremamente alto anche per problemi di modeste dimensioni.

Inoltre, un tale approccio non permetterebbe di stabilire se il problema dato `e illimitato.

In questo capitolo verrà illustrato un algoritmo per la risoluzione di problemi di programmazione lineare che esplora le soluzioni di base ammissibili in modo più intelligente rispetto all’enumerazione completa: il metodo del simplesso. Tale algoritmo permette di decidere se il problema è inammissibile, illimitato, o se ammette ottimo; in quest’ultimo caso, esso fornisce una soluzione ottima di base.

3.1 Forma tableau e condizioni di ottimalit` a

Consideriamo un generico problema di programmazione lineare ed assumiamo di averlo gi`a messo in forma standard:

max c^Tx s.a Ax = b

x ≥0,

dove i dati del problema sono A ∈ R^m×n, b ∈ R^m, c ∈ Rⁿ, e il vettore delle variabili è x ∈ Rⁿ. Tramite il metodo di eliminazione di Gauss, è possibile stabilire se il sistema Ax = b ha soluzioni. Se il sistema Ax = b non ammette soluzioni, allora il programma lineare dato è chiaramente inammissibile. Possiamo dunque assumere che il sistema Ax = b abbia almeno una soluzione. Sotto questa ipotesi, lo stesso metodo di Gauss restituisce un sistema equivalente ad Ax = b in cui il numero di righe è uguale al rango della matrice A. Possiamo dunque assumere senza perdita di generalità che rk(A) = m. Come visto nel capitolo precedente, la condizione rk(A) = m ci autorizza a parlare di soluzioni di base del problema.

13

(20)

Per convenienza nella trattazione, riscriviamo il programma lineare dato nella seguente forma equivalente:

max z (3.1)

s.a z − c^Tx =0 (3.2)

Ax = b (3.3)

x ≥0. (3.4)

Sia B ⊆ {1,... ,n} una base di A e sia N la cosiddetta non-base, cio`e N = {1,... ,n} ∖ B.

Allora valgono le seguenti equivalenze:

Ax = b ⇐⇒ A^Bx_B+ ANx_N =b ⇐⇒ x^B=A⁻¹_Bb− A⁻¹_BA_Nx_N.

Riscrivendo l’equazione (3.2) nella forma z − c^T_Bx_B− c^T_Nx_N =0 e sostituendo xB con A⁻¹_Bb− A⁻¹_BANxN, otteniamo

z− c^T_BA⁻¹_Bb−(c^TN− c^T_BA⁻¹_BA_N)x^N =0.

Definiamo

A¯_N =A⁻¹_BA_N (3.5)

¯b = A⁻¹_Bb (3.6)

¯

c^T_N =c^T_N − c^T_BA⁻¹_BAN (3.7)

¯

z = c^T_BA⁻¹_Bb. (3.8)

Il vettore ¯cN `e detto il vettore dei costi ridotti di c relativo alla base B. Allora il problema (3.1)–(3.4) `e equivalente al seguente programma lineare:

max z (3.9)

s.a z − ¯c^T_NxN =z¯ (3.10)

xB+ ¯ANxN = ¯b (3.11)

x ≥0. (3.12)

Si tenga ben presente che (3.10)–(3.12) `e precisamente lo stesso sistema di vincoli definito da (3.2)–(3.4) (nel senso che i due sistemi hanno le stesse soluzioni), solamente scritto in una forma diversa, che chiamiamo forma tableau rispetto alla base B. In questa forma, la funzione obiettivo e le variabili in base sono esplicitate rispetto alle variabili fuori base.

Spesso rappresenteremo il problema (3.10)–(3.12) in forma compatta attraverso il cosid- detto tableau del problema (3.1)–(3.4) rispetto alla base B, cio`e la matrice del sistema (3.10)–

(3.11). Assumendo per semplicit`a di scrittura che B ={1,... ,m} e dunque A = (A^B∣ A^N), il tableau `e la seguente matrice:

1 0^T −¯c^T_N z¯ }^{1 riga} 0 I A¯_N ¯b }^m^righe

®₁ °_m °_n−m ®₁

(3.13)

(21)

3.1. FORMA TABLEAU E CONDIZIONI DI OTTIMALIT `A 15 La prima colonna del tableau corrisponde alla variabile z, il blocco successivo alle variabili x (prima quelle appartenenti alla base e poi le altre), l’ultima colonna ai termini noti. La prima riga corrisponde all’equazione (3.10), le righe successive ai vincoli del sistema (3.11).

In generale, le variabili in base non saranno le prime m e non compariranno in ordine nei vincoli del problema in forma tableau. Se gli elementi di B sono B[1],... ,B[m] ∈ {1,... ,n}, allora il problema in forma tableau (3.10)–(3.12) pu`o essere scritto pi`u esplicitamente cos`ı:

max z (3.14)

s.a z −∑

j∈N

¯

c_jx_j =¯z (3.15)

x_B_[i]+ ∑

j∈N

¯

a_ijx_j = ¯b_i, i =1, . . . , m (3.16) x_j ≥0, j =1, . . . , n. (3.17) Per i = 1, . . . , m, diremo che x_B_[i] `e la variabile in base nella riga i.

Si noti che dal sistema in forma tableau (3.15)–(3.17) `e immediato ricavare la soluzione di base ¯x associata a B:

¯

x_B_[i]= ¯b_i, i =1, . . . , m

¯ xN =0.

Tale soluzione può essere letta direttamente dalla colonna destra del tableau (3.13). Dunque la base B è ammissibile se e solo se ¯b ≥ 0, cioè se la colonna di destra del tableau contiene solo termini non-negativi. Il corrispondente valore della funzione obiettivo è ¯z: questo può essere verificato usando l’equazione (3.10) (si ricordi che ¯x_N =0) oppure osservando che

c^Tx = c¯ ^T_Bx¯B+ c^T_Nx¯N =c^T_BA⁻¹_Bb =z,¯

dove l’ultima uguaglianza segue dalla definizione di ¯zdata in (3.8). Dunque il tableau rispetto alla base B contiene nella posizione pi`u in alto a destra il valore della funzione obiettivo valutata nella soluzione di base associata a B.

Supponiamo che ¯c_N ≤ 0. In tal caso, per ogni soluzione ammissibile ˆx del problema (3.14)–(3.17), il valore della funzione obiettivo ˆz, calcolato tramite l’equazione (3.10), `e

ˆ

z =z¯+ ¯c^T_Nxˆ_N ≤z,¯

dove abbiamo usato il fatto che ¯cN ≤0 e ˆxN ≥0. Pertanto, se la base B `e ammissibile, ¯x `e una soluzione ottima del programma lineare dato. Abbiamo dunque dimostrato il seguente risultato.

Lemma 3.1 Dato un programma lineare in forma standard, se i costi ridotti relativi ad una base ammissibile B sono non-positivi, allora la soluzione di base relativa a B `e ottima.

Quello appena enunciato è un criterio (sufficiente) per l’ottimalità: se determiniamo una base ammissibile i cui costi ridotti sono non-positivi, allora abbiamo trovato una soluzione ottima del problema. Come vedremo più avanti, questo sarà uno dei criteri di arresto per il metodo del simplesso.

Si presti attenzione al fatto che la prima riga del tableau contiene gli opposti dei costi ridotti, dunque la condizione da verificare `e che tali valori siano non-negativi. Inoltre, si noti che la condizione ha senso solo se siamo in presenza di una base ammissibile, cio`e se anche la colonna di destra del tableau contiene solo valori non-negativi.

(22)

3.2 Iterazione del metodo del simplesso

Supponiamo ora di conoscere una base ammissibile B, ma che nel problema in forma tableau (3.14)–(3.17) (che, ricordiamo, `e una scrittura esplicita di (3.9)–(3.12)) vi siano dei costi ridotti positivi, cio`e che valga ¯c_k>0 per qualche k ∈ N . In questo paragrafo mostriamo come determinare una nuova soluzione di base ammissibile il cui valore della funzione obiettivo sia maggiore o uguale di quello della soluzione di base corrente.

Per ogni t ≥ 0, sia x(t) il vettore definito come segue:

x_k(t) = t

xj(t) = 0, j ∈ N ∖ {k}

x_B_[i](t) = ¯xB[i]− t¯aik= ¯bi− t¯aik, i =1, . . . , m.

Si noti che la soluzione di base corrente ¯x coincide con x(0). Per ogni i = 1,... ,m si ha x_B_[i](t) + ∑

j∈N

¯

aijxj(t) = ¯bⁱ− t¯a_ik+ t¯a_ik= ¯bi,

quindi x(t) soddisfa Ax(t) = b per ogni t ≥ 0. (Pi`u precisamente, x(t) `e l’unica soluzione del sistema Ax = b che soddisfa le condizioni xk =t e xj =0 per j ∈ N ∖{k}.) Utilizzando l’equazione (3.10) o (3.15), si scopre che il valore della funzione obiettivo calcolato in x(t), che indichiamo con z(t), soddisfa

z(t) = ¯z + ¯c^TNx_N(t) = ¯z+ ¯c^kt ≥z,¯ (3.18) dunque x(t) ha valore della funzione obiettivo non peggiore del valore di ¯x. Si noti anche che, essendo ¯c_k > 0, si ha z(t) > ¯z se e solo se t > 0. Inoltre, z(t) aumenta strettamente all’aumentare di t. Vogliamo determinare il valore di t per cui x(t) `e una soluzione ammissibile col massimo valore possibile della funzione obiettivo.

Osserviamo che x(t) è ammissibile se e solo se x(t) ≥ 0. Poiché x^N(t) ≥ 0 per costruzione, x(t) è ammissibile se e solo se

x_B_[i](t) = ¯bⁱ− t¯a_ik≥0 per i = 1, . . . , m.

Fissiamo un qualunque indice i ∈{1,... ,m}. Se ¯a^ik≤0, allora ¯bi− t¯a_ik≥0 per ogni t ≥ 0. Se, invece, ¯a_ik>0, allora ¯bi− t¯a_ik≥0 se e solo se t ≤ ¯bi/¯aik. Pertanto x(t) `e ammissibile se e solo se

t ≤ ¯b_i

¯

a_ik per ogni i ∈{1,... ,m} tale che ¯a^ik>0.

Ora distinguiamo due casi:

Caso 1: Esiste un indice i ∈{1,... ,m} tale che ¯a^ik>0.

Allora il massimo valore ¯ttale che x(¯t) ≥ 0 `e

¯t = min

i∈{1,...,m} ∶ ¯aik>0{¯bi

¯ a_ik} .

Questo è noto come il criterio del minimo rapporto. Chiamiamo h un indice per cui viene raggiunto il minimo, cioè h è tale che ¯a_hk >0 e ¯t = ¯b_h/¯a^hk. Definiamo x^′ =x(¯t). Allora x^′ è una soluzione ammissibile ed inoltre

x^′_B_[h]= ¯b_h− ¯t¯a_hk= ¯b_h− ¯b_h

¯ ahk

¯ a_hk=0.

(23)

3.2. ITERAZIONE DEL METODO DEL SIMPLESSO 17 Dunque, se poniamo B^′=B∖{B[h]} ∪ {k} e N^′={1,... ,n} ∖ B^′=N∖{k} ∪ {B[h]}, vale la propriet`a

x^′_j =0 per ogni j ∈ N^′. (3.19)

Dimostriamo ora che B^′è una base e che pertanto, per la proprietà (3.19), x^′è la soluzione di base relativa a B^′. Sia A^′ la matrice m × m ottenuta dalla matrice identità sostituendo l’h-esima colonna con il vettore ¯A_k. Si noti che A^′ è una matrice invertibile, poiché ha determinante uguale a ¯a_hk > 0. Si verifica inoltre che A⁻¹_BA_B^′ =A^′, dove l’insieme B^′ deve essere pensato ordinato cos`ı: B^′[i] = B[i] per i ∈ {1,... ,m} ∖ {h}, B^′[h] = k. Pertanto A_B^′ =A_BA^′ è una matrice invertibile e dunque B^′è una base.

Si dice che la variabile x_kentra in base (nella riga h) (oppure che x_k`e la variabile entrante) e che la variabile x_B_[h] esce di base (oppure che x_B_[h] `e la variabile uscente).

Possiamo ora calcolare il tableau relativo alla base B^′ e ripetere. Si noti che il tableau rispetto a B^′pu`o essere ottenuto ricavando dall’equazione x_B_[h]+∑^j∈N¯a_hjx_j= ¯b_h l’equazione

x_k= ¯b_h

¯

a_hk − ∑

j∈N ∖{k}

¯ a_hj

¯

a_hkx_j− 1

¯

a_hkx_B_[h]

e quindi sostituendo nel problema (3.14)–(3.17) x_k con il secondo membro della precedente equazione. Dopo tale operazione, sia z che tutte le variabili in base (cio`e con indice in B^′) saranno esplicitate rispetto alle variabili non in base (cio`e con indice in N^′). Quella ottenuta

`e dunque la forma tableau rispetto alla base B^′. Caso 2: a¯_ik≤0 per ogni indice i ∈{1,... ,m}.

In questo caso x(t) `e ammissibile per ogni t ≥ 0. Inoltre, grazie alla relazione (3.18) e ricordando che ¯c_k>0, otteniamo

t→+∞lim z(t) = ¯z + lim

t→+∞¯c_kt =+∞, pertanto il problema `e illimitato.

Sia r ∈ Rⁿ il vettore cos`ı definito:

r_k=1, (3.20)

r_j =0, j ∈ N∖{k} (3.21)

r_B_[i]=−¯a_ik, i =1, . . . , m. (3.22) Si noti che x(t) = ¯x + tr per ogni t ≥ 0. Allora il vettore r indica una direzione lungo la quale, muovendosi a partire da ¯x, si rimane all’interno della regione ammissibile e lungo la quale il valore della funzione obiettivo cresce indefinitamente (una tale direzione `e detta raggio).

Si osservi che questa proprietà vale qualunque sia la soluzione ammissibile di partenza, non solo per ¯x: per ogni x ammissibile e per ogni t ≥ 0, la semiretta costituita dai punti della forma x + tr con t ≥ 0 è contenuta nella regione ammissibile e lungo tale semiretta la funzione obiettivo cresce indefinitamente. Un tale vettore r può dunque essere considerato come la prova che il problema è illimitato.

Ricapitolando, la discussione precedente giustifica il seguente metodo per risolvere problemi di programmazione lineare.

(24)

Metodo del Simplesso

Input: A ∈ R^m×n, b ∈ R^m, c ∈ Rⁿ ed una base ammissibile B = {B[1],... ,B[m]} per il sistema (3.3)–(3.4).

Output: Una soluzione ottima di base ¯xper il programma lineare (3.1)–(3.4), oppure un raggio r che dimostri che il problema `e illimitato.

1. Si calcoli il tableau rispetto alla base B e la soluzione di base ¯x relativa a B.

2. Se ¯c ≤0, allora ¯x`e una soluzione ottima; STOP.

3. Altrimenti, si scelga un indice k tale che ¯c_k>0.

4. Se ¯a_ik≤0 per ogni i ∈{1,... ,m}, allora il problema `e illimitato; si definisca r come in (3.20)–(3.22); STOP.

5. Altrimenti, si scelga h ∈{1,... ,m} tale che

¯

a_hk>0 e ¯b_h

¯ ahk

=min{¯b_i

¯ aik

∶ i ∈{1,... ,m}, ¯aik>0} .

6. Si ridefinisca B[h] ∶= k e si torni al Passo 1.

3.3 Esempi

Vediamo ora due esempi di applicazione del metodo del simplesso.

3.3.1 Un problema che ammette soluzione ottima Si consideri il problema

max z = 130x1 + 100x2

1.5x¹ + x2 ≤ 27 x1 + x2 ≤ 21 0.3x1 + 0.5x2 ≤ 9

x1 , x2 ≥ 0.

(Si veda la Figura 3.1.) Possiamo scrivere il problema in forma standard aggiungendo variabili di scarto:

max z = 130x¹ + 100x²

1.5x¹ + x2 + x³ = 27

x1 + x2 + x4 = 21

0.3x1 + 0.5x2 + x5 = 9

x1 , x2 , x3 , x4 , x5 ≥ 0.

Si noti che la base{3,4,5} è ammissibile. La soluzione di base corrispondente è data da x¹=0, x2 =0, x³ =27, x⁴ =21, x⁵ =9; il relativo valore della funzione obiettivo è 0. Tale soluzione

(25)

3.3. ESEMPI 19 corrisponde al vertice(0,0) nel problema originale. Il sistema in forma tableau rispetto alla base B ={3,4,5} (con B[1] = 3, B[2] = 4 e B[3] = 5) `e il seguente:

z − 130x1 − 100x2 = 0

1.5x1 + x2 + x3 = 27

x1 + x2 + x4 = 21

0.3x1 + 0.5x2 + x5 = 9.

Ogni iterazione del metodo del simplesso pu`o essere suddivisa in tre passi: scelta della variabile entrante in base, scelta della variabile uscente dalla base, costruzione del nuovo tableau.

ITERAZIONE 1

Scelta della variabile entrante in base Si scelga una variabile xk il cui costo ridotto sia strettamente positivo.

Nell’esempio precedente, i costi ridotti di x1 e x2 sono rispettivamente 130 e 100. Scegliamo, ad esempio, di far entrare x1 in base.

Scelta della variabile uscente dalla base Se xk entra in base, si scelga come variabile uscente la variabile in base in una riga corrispondente al minimo rapporto

i ∶ ¯mina_ik>0{¯b_i

¯ a_ik} .

Nell’esempio, min{1²⁷.5,²¹₁,₀⁹_.3} = 1²⁷.5 =18, che è ottenuto nella riga del tableau in cui è in base x3. Dunque x3 è scelta come variabile uscente dalla base.

Costruzione del nuovo tableau Riportiamo il problema in forma tableau rispetto alla nuova base {1,4,5} ottenuta facendo entrare x¹ in base nella prima riga e facendo uscire x3. Per farlo, usiamo l’equazione 1.5x1+ x2+ x3 =27 per esplicitare x1 in funzione di x2 e x3 (che sono le variabili della nuova non-base) e sostiutiamo nel tableua precedente x¹ con l’espressione trovata. Otteniamo:

z − ⁴⁰₃x2 + ²⁶⁰₃ x3 = 2340

x1 + ²₃x2 + ²₃ x3 = 18

1

3x2 − ²₃ x3 + x4 = 3

0.3x2 − 0.2x3 + x5 = 3.6 La soluzione di base corrente `e(18,0,0,3,3.6)^T, con valore 2340.

ITERAZIONE 2

L’unica variabile candidata ad entrare in base `e x2, con costo ridotto ⁴⁰₃. Per scegliere la variabile uscente, applichiamo la regola del minimo rapporto: min{2¹⁸/3,₁³

/3,³₀^.6_.3} = 1³/3 =9. Il

(26)

(0,0) x1

x2

(18,0) (0,18)

(12,9) (7.5,13.5)

1.5x¹+ x²≤27 x1+ x2≤21 0.3x¹+ 0.5x2≤9

Figura 3.1: Rappresentazione della regione ammissibile del problema dato come esempio e cammino percorso dal metodo del simplesso.

minimo è ottenuto nella riga in cui è in base x⁴, pertanto x⁴ esce dalla base. Il problema in forma tableau rispetto alla nuova base{1,2,5} è:

z + 60x3 + 40x4 = 2460

x1 + 2x³ − 2x⁴ = 12

x2 − 2x3 + 3x4 = 9

− 0.4x3 − 0.9x4 + x5 = 0.9 ITERAZIONE 3

A questo punto tutte le variabili hanno costo ridotto non-positivo, dunque il valore della funzione obiettivo non pu`o essere incrementato (Lemma 3.1) ed il metodo del simplesso termina con la soluzione ottima x1=12, x2=9, x3=x4=0, x5=0.9. Il valore ottimo `e pertanto 2460.

Ricaviamo immediatamente che x1 = 12, x2 = 9 `e una soluzione ottima per il programma lineare iniziale, con valore 2460.

Si noti che il cammino percorso dal metodo del simplesso, visto nello spazio delle variabili originali x1, x2, `e costituito dai vertici (0,0), (18,0), (12,9) (si veda di nuovo la Figura 3.1).

3.3.2 Un problema illimitato

Si consideri il seguente problema in forma tableau rispetto alla base{1,2}:

z + 1.5x3 − 0.35x4 = −3

x1 + 0.5x3 − 0.25x4 = 2 x2 − 0.5x3 − 0.25x4 = 1.

Come vedremo, questo programma lineare è illimitato. Cerchiamo prima di spiegare perché il problema è illimitato ripercorrendo quanto detto nella parte teorica, per poi vedere in che modo il metodo del simplesso riconosce l’illimitatezza del problema.

La soluzione di base corrente `e(2,1,0,0)^T. L’unica variabile candidata ad entrare in base

`e x⁴, in quanto `e l’unica ad avere costo ridotto positivo. Se aumentiamo x⁴ di t ≥ 0 lasciando

(27)

3.4. PIVOT 21 invariato a 0 il valore delle altre variabili fuori base (in questo caso la sola variabile x³), per soddisfare i vincoli dobbiamo modificare il valore delle variabili in base come segue:

x1(t) = 2 + 0.25t x2(t) = 1 + 0.25t.

La funzione obiettivo aumenterà di 0.35t. Poiché x1(t) e x²(t) sono non-negative per qualunque valore t ≥ 0, possiamo aumentare x4 arbitrariamente senza uscire dalla regione ammissibile. Dunque il valore della funzione obiettivo può essere arbitrariamente grande, cioè il problema è illimitato.

Nell’esecuzione del metodo del simplesso, una volta selezionata la variabile x⁴ come unica candidata ad entrare in base, si osserva che ¯ai4 ≤ 0 per ogni indice i, dunque l’algoritmo termina concludendo che il problema `e illimitato (si veda il Passo 4 del metodo del simplesso). Il raggio r restituito dall’algoritmo, che dimostra l’illimitatezza del problema, `e r =(0.25,0.25,0,1)^T.

3.4 Pivot

Mostriamo come, durante l’esecuzione del metodo del simplesso, quando dal Passo 6 si torna al Passo 1 con una nuova base B^′=B∖{B[h]} ∪ {k}, il tableau T^′ relativo a B^′ pu`o essere facilmente calcolato a partire dal tableau T relativo alla base B utilizzando operazioni elementari sulle righe (cio`e operazioni sulle righe che lasciano inalterato l’insieme delle soluzioni del sistema lineare rappresentato dal tableau).

Assumiamo per semplicit`a di scrittura che B = {1,... ,m} e B[i] = i per i = 1,... ,m. Il tableau T relativo alla base B avr`a la forma seguente:

T =

h k

1 0 . . . 0 . . . 0 ? . . . ? −¯c_k ? . . . ? z¯

0 1 ? . . . ? ¯a1k ? . . . ? ¯b1

⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

0 1 ? . . . ? a¯_hk ? . . . ? ¯b_h

⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

0 1 ? . . . ? a¯_mk ? . . . ? ¯b_m

dove le posizioni lasciate vuote sono occupate da zeri e i punti interrogativi indicano componenti che non ci interessa precisare in questo momento. Poiché T^′ dovrà avere una colonna unitaria nella colonna k, in cui l’elemento unitario apparirà in posizione h, possiamo eseguire le seguenti operazioni elementari sulle righe di T :

riga_h(T^′) = 1

¯

a_hkriga_h(T) riga_i(T^′) = rigai(T) − ¯a_ik

¯

a_hkriga_h(T), i = 1,... ,m, i ≠ h riga0(T^′) = riga⁰(T) + ¯c_k

¯

a_hkriga_h(T),