In questo capitolo studieremo alcuni risultati teorici sulla Programmazione Lin-eare, culminanti nel teorema fondamentale della stessa PL. Tali risultati por-ranno le fondamenta per l’algoritmo di risoluzione per i problemi di PL che verr`a presentato nel capitolo successivo, l’algoritmo del simplesso. Verranno qui introdotti anche alcuni concetti importanti (come quelli di base e soluzione di base) che verranno poi utilizzati nella definizione dell’algoritmo.
3.1 I problemi di PL in forma canonica
Come gi`a visto, la forma generica dei problemi di PL `e la seguente max (o min) Pnj=1cjxj Pn j=1aijxj ≤ bi i∈ I1 Pn j=1aijxj ≥ bi i∈ I2 Pn j=1aijxj = bi i∈ I3 x1, . . . , xn ∈ R
Qui per`o cominceremo a concentrare l’attenzione su un tipo particolare di prob-lemi di PL, rappresentato dai probprob-lemi di PL in forma canonica, in cui l’obiet-tivo `e sempre da massimizzare, i vincoli sono tutti di≤ e le variabili sono tutte vincolate ad assumere valori non negativi, cio`e
max Pnj=1cjxj
Pn
j=1aijxj ≤ bi i = 1, . . . , m xj≥ 0 j = 1, . . . , n
Come vedremo si tratta solo di una restrizione apparente rispetto ai problemi di PL in forma generica. Possiamo anche scrivere il problema di PL in forma canonica in forma pi`u compatta introducendo dei vettori. Indichiamo con:
• c ∈ Rnil vettore di dimensione n con componenti cj, j = 1, . . . , n, ovvero: c = (c1 c2 · · · cn);
• x ∈ Rn il vettore di variabili di dimensione n con componenti xj, j = 1, . . . , n, ovvero:
x = (x1 x2 · · · xn);
• ai ∈ Rn, i = 1, . . . , m, gli m vettori di dimensione n con componenti aij, j = 1, . . . , n, ovvero:
ai= (ai1 ai2 · · · ain).
Recuperando alcune nozioni di algebra lineare, ricordiamo che dati due vettori della stessa dimensione n, indicati con p = (p1 · · · pn) e q = (q1 · · · qn), il prodotto scalare tra questi vettori `e definito come somma dei prodotti delle singole componenti, ovvero:
pq =
n
X
j=1
pjqj.
Un’importante propriet`a del prodotto scalare `e la seguente. Siano p, q1, q2∈ Rn
e α, β∈ R. Allora:
p(αq1+ βq2) = α(pq1) + β(pq2)
Possiamo anche generalizzare questa propriet`a. Infatti, dati i vettori p, q1, q2, . . . , qt∈ Rn e gli scalari α1, α2, . . . , αt∈ R, si ha che
p[α1q1+ α2q2+· · · + αtqt] = p " t X i=1 αiqi # = t X i=1 αi(pqi).
Si ricordano infine le definizioni di prodotto di matrice per vettore e di vettore per matrice. Data una matrice A di ordine m× n (m righe e n colonne)
a11 . . . a1n .. . ... ... am1 . . . amn ed un vettore p di dimensione n p = (p1 · · · pn)
Il prodotto matrice-vettore `e un vettore di dimensione m la cui componente i `e il prodotto scalare tra la i-esima riga di A e il vettore p:
n
X
j=1
Data una matrice A di ordine m× n (m righe e n colonne) a11 . . . a1n .. . ... ... am1 . . . amn ed un vettore q di dimensione m q = (q1 · · · qm)
Il prodotto vettore-matrice `e un vettore di dimensione n la cui componente j `e il prodotto scalare tra la j-esima colonna di A e il vettore q:
m
X
i=1
aijqi
Tenuto conto di tutto questo possiamo riscrivere il problema di PL in forma canonica nella seguente forma:
max cx
aix≤ bi i = 1, . . . , m x≥ 0
Possiamo ulteriormente compattare la rappresentazione con l’introduzione della matrice A ∈ Rm×n che ha tante righe quanti sono i vincoli del problema (m) e la cui i-esima riga `e il vettore ai e del vettore b = (b1 · · · bm) ∈ Rm di dimensione m con componenti bi, i = 1, . . . , m. Con l’introduzione di questi possiamo riscrivere il problema di PL in forma canonica nel seguente modo:
max cx Ax≤ b
x≥ 0
Come gi`a anticipato, se apparentemente i problemi di PL in forma canonica rap-presentano un sottinsieme dei problemi di PL, `e in realt`a possibile dimostrare che ogni problema di PL ha un problema di PL in forma canonica a esso equivalente, come dimostra la seguente osservazione.
Osservazione 4 Dato un problema di PL, esiste un problema di PL in forma canonica a esso equivalente.
Dimostrazione Si pu`o notare che
1. ogni problema di minimo pu`o essere trasformato in un problema di mas-simo sfruttando la seguente relazione
2. ogni vincolo di ≥ pu`o essere trasformato in un vincolo di ≤ nel modo seguente
aTi x≥ bi ⇒ −aix≤ −bi
3. ogni vincolo di = pu`o essere trasformato in due vincoli di ≤ nel modo seguente
aix = bi ⇒ aix≤ bi, −aix≤ −bi
4. se abbiamo una variabile xj ≤ 0 possiamo sostituirla nei vincoli e nell’o-biettivo con la variabile
x′j=−xj ≥ 0
5. se abbiamo una variabile xjlibera in segno, possiamo sostituirla nei vincoli e nell’obiettivo con una differenza di variabili non negative
xj = x′j− x′′j x′j, x′′j ≥ 0
Come esercizio, si trasformi il seguente problema di PL in un problema di PL in forma canonica min x1+ x2+ x3 x1+ 2x2− x3≤ 3 x1+ 4x2+ 5x3= 5 x1− 2x2+ x3≥ 3 x1≥ 0 x2≤ 0 x3 libera in segno
Il risultato appena citato ci consente di concentrare la nostra attenzione sui soli problemi di PL in forma canonica.
3.2 La regione ammissibile Sa
La regione ammissibile di un problema di PL in forma canonica `e definita nel modo seguente:
Sa ={x ∈ Rn : aix≤ bi, i = 1, . . . , m, x≥ 0}. Dobbiamo ora introdurre alcune definizioni.
Definizione 1 Un insieme C si dice convesso se
∀ x1, x2∈ C ∀ λ ∈ [0, 1] : λx1+ (1− λ)x2∈ C,
ovvero se dati due punti qualsiasi in C, il segmento che li congiunge `e anch’esso completamente contenuto in C.
Definizione 2 Un insieme C si dice limitato se esiste un R > 0 tale che ∀ x ∈ C : kxk ≤ R,
dovekxk indica la norma euclidea di x. In altre parole l’insieme C `e contenuto in una sfera di raggio finito R.
Definizione 3 Un insieme C si dice chiuso se contiene la sua frontiera. Definizione 4 Si definisce semispazio in Rn l’insieme di punti che soddisfa una disequazione lineare in Rn:
n
X
j=1
wjxj≤ v
(in forma vettoriale: wx ≤ v). Si definisce iperpiano in Rn l’insieme di punti che soddisfa un’equazione lineare in Rn:
n
X
j=1
wjxj= v
(in forma vettoriale: wx = v).
Definizione 5 Si definisce poliedro l’intersezione di un numero finito di semis-pazi e/o iperpiani. Se il poliedro `e limitato esso viene chiamato politopo. Questo ci dice che la regione ammissibile Sadi un problema di PL `e un poliedro. Si noti che ogni iperpiano e ogni semispazio sono insiemi chiusi. Poich´e un inter-sezione di un numero finito di insiemi chiusi `e un insieme chiuso, ogni poliedro `e un insieme chiuso. In problemi con 2 sole variabili `e possibile rappresentare grafi-camente le regioni ammissibili Sa. Nel seguente esempio, la rappresentazione grafica ci consentir`a di visualizzare le diverse forme possibili di Sa.
Esempio 11 Rappresentare graficamente le regioni ammissibili Saper i seguen-ti tre problemi e constatare che sono altrettanseguen-ti esempi di regione ammissibile vuota, di politopo e di poliedro illimitato.
max x1+ x2 x1≤ −1 x1+ x2≤ 1 x1, x2≥ 0 max x1+ x2 x1+ x2≤ 1 x1, x2≥ 0 max x1+ x2 x1− x2≤ 0 x1, x2≥ 0
La seguente osservazione ci mostra anche che la regione ammissibile Sa di un problema in forma canonica `e un insieme convesso (il risultato `e facilmente estendibile a ogni poliedro).
Osservazione 5 La regione ammissibile Sa di un problema di PL in forma canonica `e un insieme convesso.
Dimostrazione Siano dati due generici punti x1, x2∈ Sa. Si avr`a: aix1≤ bi i = 1, . . . , m x1≥ 0,
e
aix2≤ bi i = 1, . . . , m x2≥ 0. Quindi, per ogni λ∈ (0, 1) e per ogni i ∈ {1, . . . , m} avremo:
ai[λx1+ (1− λ)x2] = λaix1+ (1− λ)aix2≤ λbi+ (1− λ)bi= bi, e λ |{z} >0 x1 |{z} ≥0 + (1− λ) | {z } >0 x2 |{z} ≥0 ≥ 0, da cui λx1+ (1− λ)x2∈ Sa. Ci`o equivale a dire che Sa `e un insieme convesso.
Vediamo ora di introdurre la definizione di alcuni particolari punti di Sa, i vertici di Sa.
Definizione 6 Si definisce vertice di Sa un punto x∈ Sa tale che non esistono due punti distinti x1, x2∈ Sa, x16= x2, tali che
x = 1 2x1+
1 2x2.
In problemi con 2 variabili i vertici sono facilmente identificabili, coincidendo con la usuale definizione di vertice di una figura piana.
Esempio 12 Si verifichi che, dato il problema max x1+ x2
x1+ x2≤ 1 −2x1− 2x2≤ −2
x1, x2≥ 0
il punto (1/2, 1/2) non `e un vertice di Sa mentre lo `e il punto (1, 0) Un primo importante teorema per la PL `e il seguente.
Teorema 1 Dato un problema di PL in forma canonica, se Sa 6= ∅, allora Sa
contiene almeno un vertice.
Si pu`o inoltre dimostrare la seguente osservazione.
Osservazione 6 Sa ha sempre un numero finito di vertici.
Nel caso Sa sia un poliedro illimitato possiamo anche introdurre le definizioni di raggio e raggio estremo.
Definizione 7 Si definisce raggio di Sa un vettore r6= 0 tale che ∀ x0∈ Sa ∀ λ ≥ 0 : x0+ λr∈ Sa,
cio`e la semiretta con origine in x0 e direzione r `e completamente contenuta in Sa per qualsiasi punto x0 ∈ Sa. Un raggio r di Sa si definisce raggio estremo di Sa se non esistono altri due raggi r1 e r2 di Sa con direzioni distinte, ovvero
r16= µr2 ∀ µ ∈ R, tali che r = 1 2r1+ 1 2r2.
Ovviamente i politopi non hanno alcun raggio. Infatti l’esistenza di un raggio implica che Sa contenga almeno una semiretta, che `e un insieme illimitato, mentre i politopi sono, per definizione, insiemi limitati. Anche in questo caso in problemi con 2 sole variabili `e facile riconoscere i raggi estremi, che coincidono con le semirette che delimitano la figura piana.
Esempio 13 Si verifichi che dato il problema max x1+ x2
x1− x2≤ 0 x1, x2≥ 0 i vettori
(1/2, 1) (0, 1) (1, 1)
sono tutti raggi di Sa ma solo gli ultimi due sono raggi estremi.
Come per i vertici, anche per i raggi estremi si pu`o dimostrare che il loro numero `e sempre finito.
Osservazione 7 Sa ha sempre un numero finito di raggi estremi.
Siamo ora pronti per enunciare un importante teorema che mostra che la re-gione ammissibile Sadi un problema di PL in forma canonica `e completamente caratterizzata dai suoi vertici e raggi estremi , il teorema di rapprsentazione per Sa.
Teorema 2 Sia dato un problema di PL in forma canonica con Sa6= ∅. Siano v1, . . . , vk i vertici di Sa e, nel caso in cui Sa sia un poliedro illimitato, siano r1, . . . , rh i raggi estremi di Sa. Allora
x∈ Sa se e solo se ∃ λ1, . . . , λk≥ 0, k X i=1 λi = 1, ∃ µ1, . . . , µh≥ 0 tali che x = k X i=1 λivi+ h X j=1 µjrj.
Il teorema ci dice che tutti e soli i punti di Sa sono ottenibili come somma di una combinazione convessa (combinazione lineare con coefficienti non negativi e la cui somma `e pari a 1) dei vertici di Sa e di una combinazione lineare con coefficienti non negativi dei raggi estremi di Sa.
3.3 L’insieme delle soluzioni ottime Sott
Fino a questo momento ci siamo limitati a considerare la regione ammissibile Sa di un problema di PL. Ricordiamo per`o che il nostro scopo `e determinare una soluzione ottima del problema di PL. Quindi dobbiamo trovare almeno un punto all’interno dell’insieme:
Sott={x∗∈ Sa: cx∗≥ cx ∀ x ∈ Sa},
detto insieme delle soluzioni ottime del problema. Notiamo immediatamente che Sott ⊆ Sa, il che banalmente implica che se Sa =∅, allora anche Sott=∅. Inoltre, si dimostra la seguente osservazione.
Osservazione 8 Se Sott `e un insieme finito e non vuoto, Sottcontiene un solo punto.
Dimostrazione Ragioniamo per assurdo. Supponiamo che Sottsia un insieme finito e contenga pi`u di un punto. Siano x1, x2 ∈ Sott, x1 6= x2, due punti distinti di Sott. Si dovr`a avere cx1= cx2. Per la convessit`a di Sa si ha che tutti i punti:
λx1+ (1− λ)x2 λ∈ (0, 1),
(i punti lungo il segmento che congiunge x1 e x2), appartengono a Sa. Inoltre, la linerit`a della funzione obiettivo implica:
c[λx1+ (1− λ)x2] = λcx1+ (1− λ)cx2= λcx1+ (1− λ)cx1= cx1 ∀ λ ∈ (0, 1). Ma allora tutto il segmento che congiunge x1 e x2 `e contenuto in Sott. Es-sendo tale insieme costituito da un numero infinito di punti, questo contraddice
l’ipotesi di finitezza dell’insieme Sott.
Prima di addentrarci nell’analisi di Sottintroduciamo un metodo di tipo grafico che ci consentir`a di determinare Sottnel caso di problemi con due sole variabili. Nonostante la limitata applicabilit`a di questo metodo di risoluzione (i problemi reali hanno tipicamente molto pi`u di due sole variabili), esso ci consentir`a di visualizzare facilmente le diverse possibili forme dell’insieme Sott.
3.3.1 Metodo di risoluzione grafica
Per descrivere la risoluzione grafica consideriamo il seguente esempio: max x1+ 2x2
x1+ x2≤ 1 x1, x2≥ 0
Per prima cosa disegniamo la regione ammissibile Sa. Poi prendiamo la funzione obiettivo e poniamola uguale a 0, cio`e consideriamo cx = 0 nel caso generale e x1+ 2x2 = 0 nell’esempio. Questa `e una retta che passa per l’origine che contiene tutti i punti in R2 con valore della funzione obiettivo pari a 0. Ora voglio individuare qual `e la direzione di crescita del fascio di rette
cx = k, k∈ R
parallele alla retta cx = 0 passante per l’origine. Nell’esempio avremo x1+ 2x2= k, k∈ R
fascio di rette parallele a x1+ 2x2 = 0. Possiamo individuare la direzione di crescita per esempio tracciando la retta cx = 1 (quindi x1+ 2x2= 1 nel nostro esempio) e la direzione di crescita sar`a quella che va dalla retta cx = 0 verso la retta cx = 1. In Figura 3.1 la direzione di crescita per il nostro esempio `e indicata con una freccia sulla retta x1+ 2x2= 0. A questo punto sono possibili due casi:
Caso 1 Muovendomi dalla retta cx = 0 verso la direzione di crescita ho almeno una retta del fascio con intersezione non vuota con Sa. In tal caso abbiamo due sottocasi possibili.
Caso 1.1 Esiste un valore k tale che la retta cx = k ha intersezione non vuota con Sa mentre tutte le retta cx = k per k > k hanno intersezione vuota con Sa. In tal caso k `e il valore ottimo del problema e l’intersezione della retta cx = k con Sa costituisce l’insieme Sott. Caso 1.2 Esiste un K ≥ 0 tale che per ogni k ≥ K la retta cx = k ha
intersezione non vuota con Sa. In tal caso ci troviamo nella situazione in cui Sott=∅ in quanto il problema ha obiettivo illimitato.
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ HH HH HH HH HH HH HH HH HH HHH Sa x1+2x2=0 O A B (0,1) (1,0) Figura 3.1:
Caso 2 Muovendomi dalla retta cx = 0 verso la direzione di crescita non ho alcuna retta del fascio con intersezione non vuota con Sa. In tal caso mi muovo nella direzione di decrescita e mi arresto con la prima retta cx = k (k < 0) che ha intersezione non vuota con Sa (quindi per ogni k > k si ha che la retta cx = k ha intersezione vuota con Sa). Il valore k `e il valore ottimo del problema e l’intersezione della retta cx = k con Sarappresenta l’insieme Sott.
Nel nostro esempio si pu`o vedere che ci si trova nel Sottocaso 1.1 con k = 2 e Sott ristretto al solo punto B di coordinate (0, 1).
3.3.2 Le diverse forme possibili di Sott
Siamo ora pronti a individuare tutte le forme possibili di Sottal variare di Sa. Caso 1 Sa =∅. In tal caso, essendo Sottun sottinsieme di Sa, pu`o solo essere
Sott=∅.
Caso 2 Sa6= ∅ e politopo. Un politopo `e un insieme chiuso e limitato, mentre la funzione obiettivo `e lineare e quindi certamente continua. Di conseguenza, il Teorema di Weierstrass garantisce l’esistenza di almeno una soluzione ottima, ovvero Sott6= ∅. Sono possibili due sottocasi.
Caso 2.1 Sott`e costituito da un solo punto.
Caso 2.2 Sott`e costituito da un insieme infinito e limitato di punti. Si noti che l’Osservazione 8 esclude la possibilit`a di un numero finito e maggiore di 1 di punti in Sott, mentre la limitatezza di Sott`e garantita dal fatto che `e un sottinsieme di Sa che a sua volta `e un politopo e quindi `e limitato.
Caso 3 Sa 6= ∅ e poliedro illimitato. Sono possibili quattro sottocasi.
Caso 3.1 Sott = ∅ in quanto l’obiettivo `e illimitato, ovvero esiste una sequenza infinita di punti{xk} di Sa lungo cui la funzione obiettivo cresce a +∞. Formalmente:
∃ {xk} : xk ∈ Sa ∀ k e cxk → +∞ k → +∞. Caso 3.2 Sott`e costituito da un solo punto.
Caso 3.3 Sott`e costituito da un insieme infinito e limitato di punti. Caso 3.4 Sott`e costituito da un insieme infinito e illimitato di punti. Come esercizio si applichi ora la risoluzione grafica ai seguenti esempi riconoscen-do in essi molti dei casi possibili per Sott precedentemente elencati.
max x1+ x2 x1+ x2≤ 1 x1, x2≥ 0 max x1+ x2 −x1+ x2≤ 0 x1− x2≤ 1 x2≥ 1 x1, x2≥ 0 max −x1 −x1+ x2≤ 0 x1− x2≤ 1 x2≥ 1 x1, x2≥ 0 max −x2 −x1+ x2≤ 0 x1− x2≤ 1 x2≥ 1 x1, x2≥ 0
max x1− x2
−x1+ x2≤ 0 x1− x2≤ 1
x2≥ 1 x1, x2≥ 0
3.4 Il Teorema Fondamentale della PL
La risoluzione grafica dei precedenti esempi mostra anche che, quando Sott6= ∅, tale insieme contiene sempre almeno un vertice. Non `e un caso. Vale infatti un teorema molto importante noto come Teorema Fondamentale della Program-mazione Lineare. Prima di dimostrare questo abbiamo bisogno di dimostrare un lemma.
Lemma 1 Dato un problema di PL in forma canonica, se Sott6= ∅, allora per ogni raggio estremo r di Sa si ha:
cr≤ 0.
Dimostrazione La dimostrazione `e per assurdo. Supponiamo infatti che esista un raggio estremo r tale che
cr > 0 (3.1) Notiamo che Sott6= ∅ implica Sa6= ∅. Sia allora x0∈ Sa. Poich`e r `e un raggio, in base alla Definizione 7 di raggio avremo che
∀ λ ≥ 0 : x0+ λr∈ Sa.
Calcoliamo ora il valore della funzione obiettivo nei punti x0+ λr: c(x0+ λr) = cx0+ λcr
Ma, in base a (3.1) possiamo concludere che
c(x0+ λr)→ +∞ λ→ +∞,
cio`e Sott=∅ in quanto l’obiettivo `e illimitato sulla regione ammissibile, il che contraddice Sott6= ∅.
Si noti che la dimostrazione del lemma ci dice anche che qualora esista un raggio estremo r di Satale che cr > 0, allora il problema ha obiettivo illimitato. Si pu`o dimostrare anche il viceversa, cio`e se il problema ha obiettivo illimitato, allora esiste sicuramente un raggio estremo r di Sa tale che cr > 0. Siamo ora pronti a dimostrare il Teorema Fondamentale della PL.
Teorema 3 Dato un problema di PL in forma canonica, se Sott 6= ∅, allora Sott contiene almeno un vertice di Sa.
Dimostrazione Indichiamo con v1, . . . , vk i vertici di Sa e, nel caso in cui Sa
sia un poliedro illimitato, indichiamo con r1, . . . , rh i raggi estremi di Sa. Se Sott6= ∅, sia x∗∈ Sott.
Utilizzeremo una dimostrazione per assurdo. Per assurdo supponiamo che v1, . . . , vk 6∈ Sott
cio`e supponiamo che nessun vertice di Sa appartenga a Sott. In particolare avremo
cvi< cx∗ i = 1, . . . , k (3.2) In base al Teorema 2, poich´e x∗ ∈ Sa avremo che
∃ λ∗1, . . . , λ∗k≥ 0, k X i=1 λ∗i = 1, ∃ µ∗1, . . . , µ∗h≥ 0 (3.3) tali che x∗= k X i=1 λ∗ivi+ h X j=1 µ∗jrj. Quindi avremo cx∗= c k X i=1 λ∗ivi+ h X j=1 µ∗jrj e per la linearit`a della funzione obiettivo
cx∗= k X i=1 λ∗i(cvi) + h X j=1 µ∗j(crj).
Nel Lemma 1 abbiamo dimostrato che:
crj ≤ 0 j = 1, . . . , h. (3.4) Ora, in base a (3.3) e (3.4) avremo
cx∗ = k X i=1 λ∗i(cvi) + h X j=1 µ∗j |{z} ≥0 (crj) | {z } ≤0 . da cui cx∗≤ k X i=1 λ∗i(cvi). Ma ora possiamo sfruttare (3.2):
cx∗≤ k X i=1 λ∗i(cvi) | {z } <cx∗ < k X i=1 λ∗i(cx∗).
(si noti che lo strettamente minore vale perch´e almeno uno dei λ∗i `e strettamente positivo in quanto, in base a (3.3), la loro somma deve essere pari a 1). Poich´e cx∗ non dipende dall’indice i della sommatoria, lo possiamo portare fuori dalla stessa e quindi cx∗< (cx∗) k X i=1 λ∗i.
Ma ora in base a (3.3) abbiamo chePki=1λ∗
i = 1, da cui cx∗< cx∗
il che `e assurdo.
Questo risultato `e alla base della procedura di risoluzione che descriveremo, l’algoritmo del simplesso. Infatti, tale algoritmo ricerca la soluzione ottima cer-cando di spostarsi ad ogni iterazione in modo intelligente da un vertice all’altro di Sa. Per modo intelligente si intende che l’algoritmo tenta di spostarsi ad una data iterazione da un vertice a uno con valore della funzione obiettivo maggiore.
3.5 Preparazione al metodo del simplesso
Sappiamo che il nostro scopo `e trovare almeno un punto in Sottoppure stabilire che Sott = ∅ in quanto anche Sa = ∅ oppure perch´e l’obiettivo del problema di PL `e illimitato. Dobbiamo allora individuare un metodo che ci consenta di raggiungere il nostro scopo. Abbiamo gi`a incontrato un tale metodo, quello di risoluzione grafica, la cui applicabilit`a `e per`o ristretta ai soli problemi con due variabili. Quello che vogliamo ora `e un metodo che possa essere applicato con un numero qualsiasi di variabili. Questo metodo sar`a il metodo del simplesso. Prima per`o di arrivare a descriverlo avremo bisogno di alcuni passaggi intermedi. Per prima cosa ci spostiamo dalla forma canonica a un’altra forma particolare dei problemi di PL.
3.5.1 I problemi di PL in forma standard
I problemi di PL in forma standard hanno la seguente formulazione: max cx
aix = bi i = 1, . . . , m x≥ 0
o, equivalentemente, in forma matriciale: max cx
Ax = b x≥ 0
dove A `e la matrice la cui i-esima riga `e il vettore aie b `e il vettore la cui i-esima componente `e bi. Rispetto alla forma canonica cambia solamente il fatto che i vincoli non sono pi`u di≤ ma sono di uguaglianza. Vale la seguente osservazione. Osservazione 9 Ogni problema di PL in forma canonica pu`o essere trasfor-mato in uno equivalente in forma standard.
Dimostrazione Sia dato il problema di PL in forma canonica max cx
aix≤ bi i = 1, . . . , m x≥ 0
Con l’aggiunta di una nuova variabile yi per ogni vincolo aix ≤ bi, possiamo esprimere tale vincolo attraverso la seguente coppia di vincoli:
aix + yi= bi, yi≥ 0.
Quindi, il problema di PL in forma canonica `e equivalente al seguente: max cx
aix + yi= bi i = 1, . . . , m x≥ 0
yi≥ 0 i = 1, . . . , m
che `e in forma standard (vincoli di uguaglianza e variabili non negative). Avendo gi`a dimostrato in precedenza che ogni problema di PL pu`o essere ricon-dotto ad uno equivalente in forma canonica, l’osservazione sopra ci dice anche che ogni problema di PL pu`o essere ricondotto ad uno equivalente in forma standard.
Riguardo la matrice A ∈ Rm×n con i-esima riga ai, nel seguito faremo sem-pre la seguente ipotesi: la matrice A ha rango pari a m, il numero delle sue righe, dove ricordiamo che il rango di una matrice coincide con il massimo nu-mero di righe (o, equivalentemente, di colonne) linearmente indipendenti della matrice. Si noti che deve necessariamente essere m≤ n (per n < m il rango di A potrebbe essere al pi`u n e non potrebbe essere pari a m). Si pu`o dimostrare che anche questa sul rango non `e una condizione restrittiva e che ci si pu`o sempre ricondurre a essa, eliminando eventuali vincoli ridondanti (si veda la Sezione 4.2).
3.5.2 Basi e soluzioni di base
Definizione 8 Si definisce base di un problema di PL in forma standard un sottinsieme:
B ={xi1, . . . , xim}
di m delle n variabili del problema di PL con la propriet`a che la matrice AB ∈ Rm×m ottenuta considerando le sole colonne di A relative alle variabili xik, k = 1, . . . , m, sia invertibile. Le variabili dell’insieme B verranno dette variabili in base, quelle al di fuori di B verranno raggruppate nell’insieme:
N ={xim+1, . . . , xin} e verranno dette variabili fuori base.
Esempio 14 Sia dato il seguente problema di PL in forma standard: max 3x1+ 4x2+ 2x3+ 2x4+ x5
x1+ 2x2+ 2x3+ x4− x5= 2 x1+ 2x2+ x3+ 4x4− 2x5= 2
x1, x2, x3, x4, x5≥ 0
In questo caso si hanno due vincoli e quindi m = 2. Se prendiamo B1={x1, x2} vediamo che B1 non `e una base. Si ha infatti:
AB1 =
1 2 1 2
che non `e invertibile. Invece, B2={x1, x3} `e una base in quanto: AB2 =
1 2 1 1
`e invertibile. Allo stesso modo si verifichi che B3 ={x3, x4} e B4 = {x4, x5} sono basi.
Introduciamo ora il concetto di soluzione di base. Data una base B, indichiamo con xB ∈ Rm il vettore delle variabili in base, con xN ∈ Rn−m il vettore delle variabili fuori base, cB ∈ Rm il vettore dei costi relativi alle variabili in base, con cN ∈ Rn−mil vettore dei costi relativi alle variabili fuori base e, infine, con AN ∈ Rm×(n−m)la matrice ottenuta da A considerando le sole colonne relative alle variabili fuori base. Possiamo ora riscrivere il problema di PL in forma standard nella seguente forma equivalente:
max cBxB+ cNxN
ABxB+ ANxN = b xB, xN ≥ 0 e quindi anche in questo modo:
max cBxB+ cNxN
ABxB = b− ANxN
Moltiplichiamo ora i vincoli per A−1B . Si ottiene: max cBxB+ cNxN
xB = A−1B b− A−1B ANxN
xB, xN ≥ 0
In pratica questo coincide con la risoluzione di un sistema con m incognite e m