Meto di e Mo delli della Ricerca Op erativxoomer.virgilio.it/appuntinweb/ElemRO/libtex.pdf · 2005....
116
Transcript of Meto di e Mo delli della Ricerca Op erativxoomer.virgilio.it/appuntinweb/ElemRO/libtex.pdf · 2005....
Metodi e Modelli della Ricerca OperativaA.A. 2000/2001
Fabio Schoen Dipartimento di Sistemi e Informatica
e-mail: [email protected]
web: www.dsi.unifi.it/users/schoen
PL { versione 1.0 - 6 marzo 2001
Capitolo 1
Esempi elementari di modelli
lineari per le decisioni
1.0.1 Modelli di miscelazione
Uno dei pi�u semplici modelli di ottimizzazione, descritto in qualunque testointroduttivo di Ricerca Operativa, �e il cosiddetto modello di miscelazione,presentato a volte sotto forma di modello per la formulazione di una dieta;un modello per la piani�cazione di diete di costo minimo con vincoli di ti-po nutrizionale �e stato uno dei primi modelli di ottimizzazione risolti conil metodo del simplesso. Tale modello venne risolto a mano da un gruppodi ricercatori, e richiese parecchie ore di calcolo \parallelo": �e forse inutileosservare che quel modello, basato su una proposta del premio Nobel per l'e-conomia del 1982 George Stigler, pu�o essere risolto in una frazione di secondosu un modesto Personal Computer.
Nella sua forma base, il modello di miscelazione corrisponde al problemadi decidere come comporre una miscela di costo minimi e qualit�a garantita,ottenuta da materiali vari. Uno dei campi industriali nei quali il modello dimiscelazione trova vasta applicazione �e quello della produzione di alluminioda rottami. Si immagini di poter acquistare, in quantitativi limitati, alcunirottami costituiti in massima parte da alluminio, ma miscelati anche ad al-tri elementi chimici, e di volerli miscelare in modo tale da ottenere, tramitefusione, un materiale che contenga quantitativi pre�ssati dei vari elementichimici. Naturalmente, per correggere la qualit�a dei rottami disponibili, �esempre possibile acquistare, in quantit�a teoricamente illimitate, ma ad unprezzo sensibilmente pi�u alto, elementi chimici puri. Il problema diventa
1
quindi quello di stabilire le quantit�a di rottami e di materiali puri da impie-gare in una miscela che rispetti i vincoli imposti sulla qualit�a e che risulti dicosto minimo.
Nella tabella seguente viene riportato il �le dati, preparato secondo lasintassi di AMPL, per un ipotetico problema di miscelazione di alluminioda rottami. L'obiettivo �e quello di ottenere una miscela secondo speci�chequalitative pre�ssate e note nell'ambiente della produzione di alluminio conil codice \6063".
�le: Al6063.dat# problema di miscelazione ottimale
set MATERIALI := Scarti_ALMC Scarti_KAC Rottami Al Si Mg;
set ELEMENTI := Si Mg Fe Cu Mn Zn Cr Ti Al Altri;
param qta_rich := 4.5; # tonnellate
param: rich_min rich_max :=
Si 0.2 0.6
Mg 0.45 0.9
Fe . 0.35
Cu . 0.1
Mn . 0.1
Zn . 0.1
Cr . 0.1
Ti . 0.1
Al 96.9 100.0
Altri . 0.15
;
param compos:
Scarti_ALMC Scarti_KAC Rottami Al Si Mg:=
Si 0.50 0.50 0.30 . 100 .
Mg 0.75 0.70 0.50 . . 100
Fe 0.20 0.20 0.35 . . .
Cu 0.01 0.01 0.05 . . .
Mn 0.02 0.02 0.05 . . .
Zn 0.02 0.02 0.05 . . .
Cr 0.02 0.02 0.05 . . .
Ti 0.02 0.02 0.05 . . .
Al 97.00 97.00 90.00 100 . .
Altri 0.06 0.06 0.77 . . .
;
param: dispon costo := # costo in Euro per tonnellata
Scarti_ALMC 0.50 1230
Scarti_KAC 1.20 1230
Rottami 2.20 1230
Al . 2140
Si . 1300
Mg . 2442;
2
La prima parte del �le dati contiene la de�nizione dei nomi dei materia-li disponibili e degli elementi chimici di interesse. Segue la speci�ca dellaquantit�a totale di materiale da produrre (in tonnellate) e, per ciascun ele-mento chimico, il valore della percentuale minima e massima richiesta, inbase alle speci�che di de�nizione della miscela \6063" (il valore di defaultper la richiesta minima �e pari a 0). Come si vede dal listato, viene richiestauna miscela di alluminio contenente almeno una piccola frazione di Silicio eManganese. Successivamente, nel �le dati vengono riportate le composizionichimiche dei vari materiali ed in�ne, per ciascun materiale, il quantitativomassimo disponibile ed il costo in Euro per tonnellata.
Per la formalizzazione del problema occorre individuare le variabili di de-cisione, i vincoli, l'obiettivo. Per le variabili �e naturale associare una variabilematj a ciascun materiale j; il vincolo relativo alla quantit�a totale da produrresi pu�o esprimere mediante l'equazioneX
j2MATERIALI
matj = qta rich.
Per il bilancio chimico, se si indica con composi;j la percentuale di elemen-to chimico i presente nel materiale j, la quantit�a percentuale dell'elementochimico i presente nella miscela sar�a data daX
j2MATERIALI
composi;j �matj
qta rich
e, pertanto, i vincoli che esprimono le richieste minime e massime di elementichimici presenti nella miscela assumono la forma
rich mini �X
j2MATERIALI
composi;j �matj
qta rich� rich maxi:
In�ne, per ciascun materiale j, dovr�a essere imposta la non negativit�a e, peri materiali disponibili in quantit�a limitata, un limite superiore:
0 � matj � disponj:
L'obiettivo, dato un costo unitario costoj associato a ciascun materiale, sar�a
minX
j2MATERIALI
costojmatj :
3
Riassumendo, il modello completo della miscelazione di costo minimo ha laforma seguente:
minmat
Xj2MATERIALI
costojmatj
Xj2MATERIALI
composi;j �matj
qta rich� rich maxi 8i
Xj2MATERIALI
composi;j �matj
qta rich� rich mini 8i
Xj2MATERIALI
matj = qta rich
matj � disponj 8j
matj � 0 8j:
Il modello, in linguaggio AMPL, pu�o essere implementato come riporta-to nel �le seguente, dove si pu�o notare la forte somiglianza tra il modellomatematico e la sua implementazione in AMPL.
�le: AlBlend.mod# problema di miscelazione ottimale
set MATERIALI; # materiali disponibili
set ELEMENTI; # elementi chimici
param qta_rich >=0 ; # qta' richiesta
param dispon{MATERIALI}, default Infinity;
# disponibilita' dei materiali
param compos {ELEMENTI, MATERIALI} default 0, >=0, <=100;
# composizione chimica dei materiali
param rich_min {ELEMENTI} >= 0 default 0;
# richieste minime in percentuale
param rich_max {el in ELEMENTI} <= 100, >= rich_min[el];
# richieste massime
check {mat in MATERIALI}: 0 < sum {el in ELEMENTI} compos[el,mat] <= 100;
param costo {MATERIALI};
var qta {mat in MATERIALI} >= 0, <= dispon[mat];
4
minimize costo_tot:
sum {mat in MATERIALI} costo[mat] * qta[mat];
subject to totale:
sum {mat in MATERIALI} qta[mat] = qta_rich;
subject to def_qualita {el in ELEMENTI}:
rich_min[el] <=
sum {mat in MATERIALI} (qta[mat]/qta_rich) * compos[el,mat] <=
rich_max[el];
# la qta e' assoluta ==> divisa per qta_rich fornisce qta percentuale;
Con i dati del �le sopra riportati, utilizzando un opportuno risolutore, siottiene la seguente soluzione di costo minimo:
Al 2:04176Mg 0:00438Si 0:00970
Rottami 0:74416Scarti ALMC 0:5Scarti KAC 1:2
ed il costo, in Euro, risulta pari a 7398.988. Per quanto riguarda la qualit�adella miscela ottenuta, si pu�o far riferimento alla tabella seguente:
rich min miscela rich maxAl 96:9 96:9 100Cr 0 0:0158 0:1Cu 0 0:0120 0:1Fe 0 0:1334 0:35Mg 0:45 0:45 0:9Mn 0 0:0158 0:1Si 0:2 0:4542 0:6Ti 0 0:0158 0:1Zn 0 0:0158 0:1
Altri 0 0:15 0:15
1.0.2 Il modello della dieta
Il modello della dieta pu�o essere visto come una variante del modello di mi-scelazione; il modello classico prevede la determinazione della dieta, o della
5
miscela di cibi, di costo minimo soggetta a vincoli sul contenuto nutritivo.Tali vincoli, come nel modello di miscelazione, possono prevedere soglie mi-nime (per gli elementi nutritivi vantaggiosi) e/o soglie massime (per quellinocivi). L'unica di�erenza sostanziale tra il modello elementare di miscela-zione e quello di dieta consiste nel fatto che in quest'ultimo non ha in generesenso imporre vincoli sulla quantit�a totale; un'altra di�erenza �e il fatto chenei problemi di dieta i contenuti nutritivi non sono espressi generalmente inpercentuale, ma in unit�a di misura di�erenti, quali grammi, ad esempio perle proteine, i grassi ed i carboidrati, o calorie, nel caso del valore energeti-co. Spesso le etichette sulle confezioni di cibo riportano il valore riferito a100g di prodotto, oppure il valore riferito ad una porzione tipica: in questicasi nel formulare il modello occorrer�a prestare attenzione al signi�cato dellevariabili, che deve essere scelto coerentemente ai dati nutrizionali utilizzati.Spesso, almeno per alcuni componenti nutritivi quali le vitamine, si utilizzaun'unit�a di misura detta percentuale del fabbisogno medio giornaliero: conquesto termine si usa indicare la quantit�a che mediamente un individuo adul-to dovrebbe assumere giornalmente in una dieta equilibrata. Quest'ultimaunit�a di misura �e una percentuale, da trattare in modo simile a quanto fattonel caso della miscela; per tutti gli altri casi, la di�erenza tra l'uso dei valoripercentuali nel modello della miscela ed i contenuti e�ettivi in quello delladieta si riduce semplicemente all'uso di unit�a di misura di�erenti. Il modelloelementare della dieta pu�o quindi essere presentato nel modo seguente, uti-lizzando una terminologia che sia la pi�u vicina possibile a quella utilizzataper il modello di miscelazione:
minmat
Xj2CIBI
costojqtaj
Xj2CIBI
composi;jqtaj � rich maxi 8i
Xj2CIBI
composi;jqtaj � rich mini 8i
qtaj � 0 8j:
In questo modello sono stati omessi anche i limiti superiori alla quantit�a ac-quistabile per ogni cibo, in quant si pu�o immaginare che la disponibilit�a dicibo sia sostanzialmente illimitata per una dieta singola, cio�e che le quan-tit�a di cibo acquistabili in base ai vincoli nutrizionali siano sempre reperibili
6
sul mercato. In alcuni casi �e utile per�o inserire tali vincoli non tanto perriprodurre la situazione di cibi di�cilmente reperibili sul mercato, quantopiuttosto per limitare la quantit�a di cibo di un dato tipo presente nella die-ta. Ad esempio, in una dieta piani�cata per un'intera giornata, si potrebberichiedere che per molti, o forse tutti, i cibi il numero massimo di porzionisia pari a 1 oppure a 2. A titolo di esempio si riporta un �le dati AMPLcon alcune speci�che nutrizionali (naturalmente l'esempio ha il solo scopodi illustrare la metodologia di modellizzazione e non deve essere consideratocome un esempio realistico di modello di dieta, n�e si deve considerare la dietarisultante dal modello come consigliabile).
�le: dieta-1.datset NUTR := Proteine Vitamina-A Vitamina-C VitaminaB1 VitaminaB2
Niacina Calcio Ferro Sodio ;
set GRASSI := Grassi ;
set CALORIE := Calorie ;
set CIBO := Hamburger McLean BigMac PatateFritte PolloFritto Miele
ChefSalad InsalataVerde UovoMcMuffin Wheaties Vaniglia Latte
SuccoArancia SuccoPompelmo SuccoMela;
param:
costo upp_bnd :=
Hamburger 0.59 .
McLean 1.79 .
BigMac 1.65 .
PatateFritte 0.68 .
PolloFritto 1.56 .
Miele 0.00 .
ChefSalad 2.69 .
InsalataVerde 1.96 .
UovoMcMuffin 1.36 .
Wheaties 1.09 .
Vaniglia 0.63 .
Latte 0.56 .
SuccoArancia 0.88 .
SuccoPompelmo 0.68 .
SuccoMela 0.68 .;
param:
rich_min rich_max :=
Proteine 55 .
Sodio 0 3000
Vitamina-A 100 .
Vitamina-C 100 .
VitaminaB1 100 .
VitaminaB2 100 .
Niacina 100 .
Calcio 100 .
Ferro 100 . ;
param compos (tr):
7
Calorie Proteine Grassi Sodio Vitamina-A Vitamina-C VitaminaB1 :=
Hamburger 255 12 9 490 4 4 20
McLean 320 22 10 670 10 10 25
BigMac 500 25 26 890 6 2 30
PatateFritte 220 3 12 110 0 15 10
PolloFritto 270 20 15 580 0 0 8
Miele 45 0 0 0 0 0 0
ChefSalad 170 17 9 400 100 35 20
InsalataVerde 50 4 2 70 90 35 6
UovoMcMuffin 280 18 11 710 10 0 30
Wheaties 90 2 1 220 20 20 20
Vaniglia 105 4 1 80 2 0 2
Latte 110 9 2 130 10 4 8
SuccoArancia 80 1 0 0 0 120 10
SuccoPompelmo 80 1 0 0 0 100 4
SuccoMela 90 0 0 5 0 2 2
: # continuazione tabella
VitaminaB2 Niacina Calcio Ferro :=
Hamburger 10 20 10 15
McLean 20 35 15 20
BigMac 25 35 25 20
PatateFritte 0 10 0 2
PolloFritto 8 40 0 6
Miele 0 0 0 0
ChefSalad 15 20 15 8
InsalataVerde 6 2 4 8
UovoMcMuffin 20 20 25 15
Wheaties 20 20 2 20
Vaniglia 10 2 10 0
Latte 30 0 30 0
SuccoArancia 0 0 0 0
SuccoPompelmo 2 2 0 0
SuccoMela 0 0 0 4 ;
Un modello che rappresenta il problema della dieta sopra descritto �e ilseguente:
�le: dieta-1.modset NUTR; # elementi nutritivi
set CALORIE;
set GRASSI;
# calorie e grassi sono considerati a parte per poter formare vincoli piu'
# complessi o obiettivi diversi dalla minimizzazione del costo.
set CARATT := NUTR union CALORIE union GRASSI;
# l'insieme di tutte le caratteristiche nutrizionali.
set CIBO;
param costo {CIBO} >= 0;
param low_bnd {CIBO} >= 0. default 0;
param upp_bnd {j in CIBO} >= low_bnd[j], default +Infinity;
8
# quantita' minime e massime di ciascun cibo nella dieta - default 0 e
# infinito rispettivamente
param rich_min {NUTR} >= 0, default 0;
param rich_max {NUTR} >= 0, default +Infinity;
# richieste minime e massime per i singoli elementi nutritivi
param compos {CARATT,CIBO} >= 0;
var Qta {j in CIBO} >= low_bnd[j], <= upp_bnd[j];
minimize costo_totale: sum {j in CIBO} costo[j] * Qta[j];
subject to dieta {i in NUTR}:
rich_min[i] <= sum {j in CIBO} compos[i,j] * Qta[j] <= rich_max[i];
L'esecuzione di un algoritmo risolutore per questo modello produce ilseguente risultato: la dieta minima risulta avere un costo totale di 6.12605(i costi sono espressi in Euro) e risulterebbe composta come segue:
cibo qt�aHamburger 5:299
Insalata verde 0:535Latte 1:441
Succo Pompelmo 0:381'Wheaties' 0:812
ed i contenuti nutrizionali risultano i seguenti:
Elemento nutritivo qt�aCalcio 100Ferro 100Niacina 124:047Proteine 80:708Sodio 3000
Vitamina A 100Vitamina C 100Vitamina B1 138:48Vitamina B2 116:44
Come si vede immediatamente, la dieta ottenuta dal risolutore, sebbenecorretta, non �e utilizzabile in pratica, per vari motivi. Ad esempio, appareimproponibile una dieta che presenti un numero di porzioni molto elevate {pi�u di 5 { per un singolo cibo (ricordando che il dati inseriti corrispondono
9
alla piani�cazione di una dieta per un giorno). Inoltre la variet�a di cibi �eabbastanza limitata: sono stati scelti dal risolutore solo relativamente pochicibi, rispetto al totale disponibile. In�ne, dovendo programmare una dietaper un'unica persona, occorrerebbe evitare la presenza di valori decimali nellasoluzione. Per quanto riguarda la limitazione del numero totale di porzioniassunte nel corso di un'unica giornata, nel modello �e su�ciente speci�careun dato diverso da quello di default per il parametro upp bnd; imponendoad esempio un limite inferiore pari a 2 porzioni per ogni cibo si ottiene lasoluzione seguente:
cibo qt�aHamburger 2InsalataVerde 0:265823
Latte 0:949367SuccoPompelmo 0:388987UovoMcMu�n 1:85823
Wheaties 2
con un costo pari a 7:204 - come si pu�o facilmente intuire, l'aumento di vincolicomporta un aumento di prezzo. Si nota anche come l'inserimento del vincolorelativo al numero massimo di porzioni ha portato ad una variazione non solonelle quantit�a dei cibi, ma anche nella composizione della dieta ottimale.Aggiungendo il vincolo di interezza sulle variabili, si ottiene la soluzione
cibo qt�aBigMac 1
Hamburger 2Insalata Verde 1
Latte 2Patate Fritte 1Wheaties 2
di costo 8:77. Si nota come la soluzione intera non sia un arrotondamentodella soluzione decimale { compaiono cibi nuovi ed alcuni (Latte) assumonovalori molto diversi da quelli ottenuti precedentemente.
Naturalmente il modello qui presentato �e talmente elementare da rivelarsidi poca o nessuna utilit�a pratica; tuttavia esso pu�o costituire la base per lacostruzione di un modello pi�u realistico. Ad esempio, uno dei vincoli che
10
gli esperti di nutrizione inseriscono spesso �e una limitazione sulla quantit�adi alcuni tipi di grassi, sia in assoluto, sia in rapporto ad altri grassi. Adesempio spesso si richiede in una dieta equilibrata che le calorie provenientidai grassi non superino il 30% delle calorie totali. Avendo a disposizioni idati sulla quantit�a di calorie provenienti dai grassi e quelle totali per ognicibo, il vincolo si esprime facilmente come disequazione lineare:
Xj2CIBI
CalorieDalGrassojqtaj �30
100
Xj2CIBI
Caloriejqtaj:
Molti altri requisiti nutrizionali possono essere espressi in modo simile a que-sto. Altri richiedono invece una modellazione pi�u complessa e, spesso, pos-sono essere formulati utilizzando le variabili binarie indicatrici come si vedr�anella parte dedicata ai modelli di programmazione lineare intera. Vincoli diquesto genere sono spesso posti sotto forma di vincoli logici del tipo: \Sela dieta prevede hamburger, allora devono esserci anche le patatine" oppu-re \Nella dieta devono essere presenti o gli hamburger o i BigMac, ma nonentrambi", ecc.
Anche nella sua versione elementare, per�o, il modello risulta utile, in par-ticolare in campi quali quello della preparazione dei mangimi per animali odei fertilizzanti per terreni, dove non entrano in gioco vincoli particolari sulgusto o sulla variet�a della dieta. In�ne, come si vedr�a nella parte dedicataai modelli, l'esempio qui descritto pu�o essere generalizzato su un orizzontetemporale di pi�u di una giornata: in questo caso le variabili dovranno avereun secondo indice relativo alla giornata e si potranno prevedere vincoli nutri-zionali relativi a periodi pi�u lunghi, tipicamente una settimana od un mese.In questi casi il problema si avvicina a quello della piani�cazione dei menuper una mensa.
1.0.3 Il modello dell'abbinamento
Un modello piuttosto lontano dai due precedentemente esposti �e il seguente:si consideri la situazione in cui un certo numero n di progetti (ad esempio,lo sviluppo di moduli di un progetto software) devono essere a�dati ad unugual numero n di progettisti o di sviluppatori. Ogni progettista deve svol-gere esattamente un progetto { si tratta quindi di mettere in corrispondenzabiunivoca i progetti ed i progettisti (esistono varianti del modello nelle quali
11
non tutti i progetti devono essere svolti o altre nelle quali qualche progettistapu�o svolgere pi�u di un progetto). Per addestrare il progettista i a realizzareil progetto j occorre un periodo di addestramento il cui costo �e stimato paria cij . Il problema di abbinamento consiste nel determinare l'accoppiamentoprogetto/progettista che rende minimo il costo totale di addestramento.
Per questo modello �e comodo utilizzare delle variabili decisionali di tipobinario, �ij, con la convenzione che �ij = 1 sta ad indicare che il progettistai svolge il progetto j e 0 altrimenti. Con questa convenzione il costo totaledi addestramento si esprime facilmente comeX
i;j
cij�ij:
Il vincolo che esprime la necessit�a che ogni progetto sia svolto esattamenteda un progettista, ricordando che le variabili � sono binarie, si esprime comeX
i
�ij = 1 8j
(una somma di variabili binarie vale uno se e solo se esattamente una diloro �e pari ad 1), mentre il fatto che ogni progettista svolga esattamente unprogetto si esprime simmetricamente comeX
j
�ij = 1 8j:
Si vedr�a pi�u avanti che questo modello, nonostante richieda l'interezza dellevariabili, pu�o essere risolto trascurando questo vincolo.
In tutti gli esempi presentati in questo paragrafo, si pu�o vedere comeesistano alcuni elementi comuni. Ogni modello prevede l'identi�cazione di 3componenti principali: un insieme di variabili di decisione, o incognite, unoo pi�u vincoli, espressi generalmente sotto forma di equazioni e/o disequa-zione, una funzione obiettivo da massimizzare o minimizzare. La maggiorparte dei vincoli visti nei modelli qui presentati �e costituita da equazioni edisequazioni lineari; naturalmente esistono molti modelli nei quali i vincoli siesprimono come equazioni o disequazioni non lineari. Un esempio particolaresi �e visto gi�a nei modelli presentati, quando, ad esempio nel modello delladieta, si �e richiesta l'interezza delle variabili: questo �e un vincolo complesso,non esprimibile come vincolo lineare (ma, come vedremo, esprimibile come
12
equazione non lineare), la cui presenza spesso porta ad un enorme crescitadella complessit�a di risoluzione del problema.
Naturalmente, oltre alle 3 componenti viste, ogni modello preveder�a laspeci�ca di parametri, cio�e dei coe�cienti che compaiono in tutti i vincolie nell'obiettivo. Sistemi di modellizzazione algebrica quali AMPL o anchesistemi basati su fogli elettronici quali Excel prevedono una separazione trale speci�che descrittive del modello ed i dati. Questa separazione, maggiorenei linguaggi algebrici che nei fogli elettronici, riduce la possibilit�a di errori,separando la fase di progettazione del modello, da e�ettuarsi a cura di unesperto nella formulazione di problemi di decisione, dalla fase di speci�ca deidati di un esempio particolare (quella che con pessimo neologismo viene detta\istanziazione"), operazione che pu�o essere e�ettuata da qualcuno non par-ticolarmente esperto nella formulazione di modelli. Un terzo componente,separato sia dal modello che dai dati, �e il risolutore, un algoritmo in gra-do di determinare una soluzione ad un problema di decisione rappresentatoformalmente mediante modello e dati.
13
Capitolo 2
Problemi di ottimizzazione
2.1 Introduzione e de�nizioni principali
Si consideri un generico problema di ottimizzazione:
P : Optx2Xf(x) (2.1)
dove Opt pu�o indicare indi�erentemente l'operatore min o max e X � Rn,n 2 N.
De�nizione 1 Il problema di ottimizzazione P si dice non ammissibile oinammissibile se X = ;.
De�nizione 2 Un vettore x 2 Rn si dice soluzione ammissibile per il pro-blema P se x 2 X.
De�nizione 3 La funzione f in (2.1) si dice funzione obiettivo. L'insiemeX si dice insieme ammissibile.
De�nizione 4 Un problema di ottimizzazione P di minimo si dice illimi-tato (inferiormente) se esiste almeno una successione fxkg1k=1 di soluzioniammissibili tale che
limk!1
f(xk) = �1:
Un problema di ottimizzazione P di massimo si dice illimitato (superior-mente) se esiste almeno una successione fxkg
1k=1 di soluzioni ammissibili
14
tale che
limk!1
f(xk) = +1:
De�nizione 5 Un problema di ottimizzazione P di minimo ammette ottimo�nito se e solo se
9x? 2 X : f(x?) � f(x) 8x 2 X: (2.2)
Analogamente un problema P di massimo ammette ottimo �nito se e solo se
9x? 2 X : f(x?) � f(x) 8x 2 X: (2.3)
Ogni punto x? che soddis� la (2.2) per un problema di minimo o la (2.3) peruno di massimo, si dice ottimo (globale) per il problema P .
L'insieme degli ottimi di P si indica con
arg optP:
15
Capitolo 3
Introduzione alla
programmazione lineare
3.1 Problemi di programmazione lineare - im-
portanza della linearit�a
Gran parte dei modelli che verranno studiati in questo volume rientra nellacategoria dei cosiddetti \modelli lineari". E' opportuno ricordare che unafunzione lineare de�nita in Rn pu�o sempre essere espressa nella forma
f(x1; : : : ; xn) = a1x1 + � � �+ anxn =nXi=1
aixi = aTx
dove con a si �e indicato il vettore colonna
264a1...an
375e con a1; : : : ; an si sono
indicate n costanti reali.I problemi di programmazione lineare sono caratterizzati da una funzione
obiettivo lineare e da un insieme ammissibile rappresentabile esplicitamentemediante un numero �nito di equazioni e/o disequazioni lineari. Un gene-rico problema di programmazione lineare potrebbe pertanto avere la formaseguente:
16
OptnX
j=1
cjxj (3.1)
nXj=1
aijxj = bi i = 1; : : : ;ml (3.2)
nXj=1
aijxj � bi i = ml + 1; : : : ;mh (3.3)
nXj=1
aijxj � bi i = mh + 1; : : : ;mk (3.4)
In questo problema il simbolo Opt rappresenta l'operatore min o l'opera-tore max; sono presentiml � 0 equazioni lineari e (mk�ml) � 0 disequazionilineari, alcune delle quali rappresentate in forma di �, altre di �.
Nel problema sopra rappresentato sono presenti i principali elementi deigenerici problemi di programmazione lineare e, in particolare:
1. un insieme di variabili di decisione o incognite x1;x2; : : : ; xn;
2. una funzione obiettivo o costo da minimizzare o massimizzare;
3. alcune (in certi casi anche nessuna) equazioni lineari o vincoli di egua-glianza ;
4. alcune (a volte nessuna) disequazioni lineari o vincoli di diseguaglianza;
5. alcuni vincoli di segno o di non negativit�a sulle variabili; questi vin-coli non sono altro che semplici disequazioni lineari, ma in genere sipreferisce mantenerli separati dagli altri vincoli del problema.
Si noti che nel modello appena introdotto non sono presenti vincoli didiseguaglianza stretta, cio�e caratterizzati dalla relazione > o <; n�e sonopresenti vincoli di diseguaglianza, caratterizzati dalla relazione 6=.
In un modello lineare, la funzione obiettivo, cio�e la funzione da minimiz-zare o massimizzare, �e lineare, cos�� come i vincoli sono espressi da equazionie/o disequazioni lineari. La funzione obiettivo potrebbe anche essere \a�ne",
17
cio�e avere la forma aTx+ k, con k 2 R, anche se dal punto di vista algorit-mico non vi �e alcuna di�erenza nell'ottimizzare funzioni che di�eriscono fraloro per una costante.
Il notevole peso dato ai modelli lineari si pu�o spiegare in vari modi:
1. molti concetti e propriet�a relativi ai modelli lineari si possono ritrovare,con opportune varianti, anche in alcuni modelli pi�u complessi;
2. i modelli lineari possono essere risolti molto e�cientemente;
3. moltissimi modelli applicativi sono e�ettivamente o possono ricondursia modelli lineari;
4. molti modelli non lineari possono essere approssimati e�cacementemediante opportuni modelli lineari.
Naturalmente l'ipotesi di linearit�a �e molto forte. Formulare un proble-ma mediante un modello lineare corrisponde ad assumere la validit�a delleseguenti ipotesi:
1. additivit�a: il contributo al \costo" (o al membro di sinistra di equazionio disequazioni) �e la somma dei contributi dovuti alle singole incognite;
2. proporzionalit�a marginale: il contributo (ad esempio, al costo) di cia-scuna variabile �e di tipo proporzionale: a valori doppi della variabilecorrisponde un contributo doppio. Spesso questa ipotesi non �e ragio-nevole { si pensi ad esempio al caso degli sconti per acquisti di grossequantit�a, oppure ai modelli di imposizione �scale, nei quali ad impo-nibili via via crescenti corrispondono percentuali di prelievo crescenti.Nel capitolo ?? verr�a presentata la formulazione dei modelli lineari atratti, utili per formulare problemi di questo genere;
3. divisibilit�a: le incognite possono assumere qualsiasi valore reale com-patibile con i vincoli. Cio�e, se una variabile pu�o assumere sia il valore3 che il valore 7, allora potr�a anche assumere ciascuno dei valori del-l'intervallo [3; 7] : Questa �e forse l'ipotesi che pi�u spesso non �e veri�catanelle applicazioni reali. Molto spesso alcune incognite possono assume-re solo valori interi, a volte soltanto binari. Nel capitolo ?? verrannotrattati in dettaglio i modelli di programmazione lineare intera.
18
Anche se quello appena visto �e il pi�u generale problema di programma-zione lineare che incontreremo in questo libro, �e importante de�nire unaforma \standard", alla quale sia facile ricondurre altre forme di problemi diprogrammazione lineare. Avendo a disposizione tale forma standard sar�apossibile sviluppare un algoritmo risolutivo \standard", senza dover cio�epresentare forme algoritmiche di�erenti per le diverse tipologie di problemi.
3.1.1 Forma standard di un problema di programma-
zione lineare
Useremo la convenzione di de�nire standard un problema di minimizzazioneche si presenti sotto il seguente aspetto:
min c1x1 + c2x2 + � � � + cnxna11x1 + a12x2 + � � � + a1nxn = b1a21x1 + a22x2 + � � � + a2nxn = b2
......
...am1x1 + am2x2 + � � � + amnxn = bm
x1 � 0; x2 � 0; : : : ; xn � 0
(3.5)
Il problema standard consiste quindi nella minimizzazione di una funzio-ne, detta funzione obiettivo , lineare nelle n incognite reali x1, : : : , xn; icoe�cienti c1, : : : , cn delle incognite sono chiamati coe�cienti di costo. Ivincoli sono rappresentati da un sistema di m equazioni lineari e dall'impo-sizione del vincolo di non negativit�a su tutte le incognite; l'i{esima equazioneha coe�cienti ai1, : : : , ain.
Naturalmente lo stesso problema pu�o anche essere espresso in forma pi�uconcisa come
minPn
j=1 cjxjPn
j=1 aijxj = bi; i = 1; : : : ;m
xj � 0; j = 1; : : : ; n:
In molti casi sar�a conveniente utilizzare una rappresentazione ancora pi�uconcisa. Riunendo i coe�cienti del sistema di equazioni in una matricem�n:
A =
264a11 � � � a1n...
...am1 � � � amn
375
19
i costi in un vettore n{dimensionale:
c =
264c1...cn
375
i termini noti in un vettore m{dimensionale
b =
264b1...bm
375
ed, analogamente, le incognite in un vettore n{dimensionale:
x =
264x1...xn
375
si pu�o scrivere
minxcTx (3.6)
Ax = b (3.7)
x � 0 (3.8)
Con la notazione cT si indica il trasposto del vettore c (quindi, in questocaso, un vettore riga 1 � n) e con cTx si rappresenta il prodotto interno (oprodotto scalare)
Pn
j=1 cjxj tra i vettori c ed x.
3.1.2 Trasformazione di programmi lineari in forma
standard
Spesso un problema di programmazione lineare si presenta gi�a nella formastandard precedentemente introdotta. Ad esempio, un semplice problema diassegnamento 3� 3
min3P
i=1
3Pj=1
cijxij
3Pj=1
xij = 1; i = 1; 2; 3
3Pi=1
xij = 1; j = 1; 2; 3
xij � 0; i = 1; 2; 3; j = 1; 2; 3
20
pu�o essere scritto in forma matriciale ponendo
A =
26666664
1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1
37777775;
b =�1 1 1 1 1 1
�T;
c =�c11 c12 c13 c21 c22 c23 c31 c32 c33
�T;
x =�x11 x12 x13 x21 x22 x23 x31 x32 x33
�T:
In altri casi per�o il problema originale non si presenta in forma standard| si pensi, ad esempio, al problema della dieta, nel quale i vincoli sonodisequazioni lineari che rappresentano richiesteminime o massime di elementinutritivi. Fortunatamente in molti casi �e facile ricondurre il problema informa standard. Vedremo ora alcuni casi tra i pi�u comuni.
Massimizzazione
Se il problema dato richiede la massimizzazione di un obiettivo lineare, cisi pu�o ricondurre ad un problema standard semplicemente cambiando segnoal vettore dei costi. Questo perch�e, data una qualunque funzione f ed ungenerico insieme ,
maxff(x) : x 2 g = �minf�f(x) : x 2 g
e se x? 2 �e tale che f(x?) = maxff(x) : x 2 g, allora �e anche vero chelo stesso x? �e tale che �f(x?) = minf�f(x) : x 2 g. La dimostrazione diquesta importante propriet�a �e molto elementare e viene lasciata al lettore.
Dovendo ad esempio risolvere un problema di massimizzazione linearecon vincoli lineari di eguaglianza e variabili vincolate in segno, avendo adisposizione un codice di calcolo predisposto per la minimizzazione, baster�arisolvere il problema
min �cTxAx = bx � 0
e ricordarsi, al termine, di cambiare segno al valore dell'ottimo trovato (soloal valore dell'ottimo, non all'ottimo stesso).
21
Vincoli di diseguaglianza
Se in un problema di programmazione lineare compare un vincolo del tipo
nXj=1
aijxj � bi;
ci si pu�o ricondurre alla forma standard introducendo una variabile in pi�u.L'espressione del vincolo pu�o essere scritta in modo equivalente come
bi �nX
j=1
aijxj � 0:
Ora, de�nendo una nuova variabile si come
si = bi �nX
j=1
aijxj;
il vincolo originale si riduce al vincolo di non negativit�a si � 0. In altreparole, al posto del vincolo originale scriveremo
nXj=1
aijxj + si = bi; si � 0;
coerentemente con quanto richiesto dalla forma standard.La variabile si viene detta variabile di slack o di scarto , in quanto
rappresenta lo scarto esistente fra i due membri della disequazione originale.Se nel problema compaiono diversi vincoli di diseguaglianza, si potr�a operareuna simile trasformazione per ciascuno di essi, ricordandosi di utilizzare, perciascun vincolo, una diversa variabile di slack.
Se in un problema compaiono disequazioni di tipo \�", si utilizza unprocedimento del tutto analogo; in particolare una disequazione del tipo
nXj=1
aijxj � bi
pu�o essere portata in forma standard con l'introduzione di una variabileaggiuntiva (detta di surplus o di eccedenza):
nXj=1
aijxj � si = bi; si � 0:
22
Vincoli sul segno delle variabili
A volte, anche se nelle applicazioni ci�o �e relativamente raro, un'incognita �evincolata ad assumere valori non positivi: xj � 0; ovviamente, in questocaso, sostituendo ogni occorrenza della variabile xj con il suo opposto �xj cisi riporta alla forma standard, con vincoli di non negativit�a sulle incognite.
In altri casi invece sull'incognita xj non �e richiesto alcun vincolo di segno| si pensi ad esempio al caso di un'incognita che rappresenti il livello di unconto corrente bancario: a secondo dei movimenti, l'incognita potr�a assumeresia valori negativi che positivi. Altre volte, in�ne, non �e noto a priori se sialecito o meno presupporre un segno speci�co per una variabile.
Uno dei sistemi pi�u comunemente utilizzati per trattare questo caso con-siste nel sostituire tale incognita libera con la di�erenza di due incognite nonnegative:
xj � x+j � x�j dove x+j � 0; x�j � 0:
Per qualsiasi valore di xj esisteranno in�nite coppie di valori x+j ed x�j taliche xj �e uguale a x
+j � x�j . In generale x+j e x�j non coincidono con la parte
positiva e la parte negativa di xj; questo avviene se e solo se almeno una delledue variabili x+j o x�j �e nulla { in questo caso l'altra variabile corrispondealla parte positiva (o negativa) di xj.
3.2 Equivalenza tra problemi di ottimizzazione?
L'equivalenza tra diversi problemi di programmazione lineare �e stata postu-lata nel paragrafo precedente appoggiandosi su una base intuitiva. Poich�epi�u avanti sar�a necessario veri�care l'equivalenza fra forme apparentementemolto diverse di problemi di ottimizzazione, pare utile a questo punto de�nireil concetto di equivalenza in modo pi�u rigoroso.
Sia data una coppia di famiglie di problemi di ottimizzazione
P (F ;X ) Q(G;Y)Optx2Xf(x);X 2 X ; f 2 F Opty2Y g(y); Y 2 Y; g 2 G
dove Opt pu�o indicare indi�erentemente l'operatore min o max e X � Rn,Y � Rm. Ogni problema di ottimizzazione �e caratterizzato da un insie-me ammissibile e da una funzione obiettivo. Per formalizzare il concetto
23
di equivalenza occorre stabilire una corrispondenza tra famiglie diverse diproblemi di ottimizzazione che permetta di passare dalla soluzione di unproblema di una famiglia alla risoluzione di un problema dell'altra e vicever-sa. Ogni problema pu�o essere identi�cato con la terna hf;X;Opti costituitadalla funzione obiettivo e dall'insieme ammissibile, oltre che dalla direzionedell'ottimizzazione.
De�nizione 6 Le famiglie di problemi P e Q si dicono equivalenti se esi-stono quattro trasformazioni
� : P ! Q �X : X � Rn ! Y � Rm
: Q! Q Y : Y � Rm ! X � Rn
tali che
1. un problema hf;X;Opti 2 P �e inammissibile se e solo se � hf;X;Opti 2Q �e inammissibile e, viceversa, un problema hg; Y;Opti 2 Q �e inam-missibile se e solo se hg; Y;Opti 2 P �e inammissibile
2. un problema hf;X;Opti 2 P �e illimitato se e solo se il problema� hf;X;Opti 2 Q �e illimitato e viceversa;
3. vale inoltre:
8x? 2 arg opt hf;X;Opti =) �X(x?) 2 arg opt � hf;X;Opti
e
8 y? 2 arg opt hg; Y;Opti =) Y (y?) 2 arg opt hg; Y;Opti
Possiamo ora veri�care formalmente l'equivalenza tra alcune famiglie par-ticolari di problemi di ottimizzazione.
Teorema 3.1 Il problema di ottimizzazione
minx2X
f(x)
�e equivalente al problema di ottimizzazione
�maxx2X
(�f(x))
24
Dimostrazione. Le famiglie di problemi
P := hf;X;mini
e
Q := h�f;X;maxi
con X = Rn sono equivalenti. Infatti, considerate le trasformazioni
� : � (f;X;min) =! h�f;X;maxi
: (f;X;max) =! h�f;X;mini
�X(x) = x
X(x) = x
si ha:
1. l'insieme ammissibile di un problema in una delle due famiglie �e identicoal corrispondente insieme nell'altra;
2. se un problema in P �e illimitato, esiste una successione di soluzioniammissibili fxkg � X tale che limk f(xk) = �1: utilizzando la stessasuccessione si ha che limk(�f(xk)) = +1;
3. se x? 2 argminx2X f(x) allora x? = �X(x?) 2 argmaxx2X �f(x) eviceversa.
Come ulteriore esempio di applicazione formale della nozione di equiva-lenza si consideri il caso dei problemi lineari con vincoli di diseguaglianza.
Teorema 3.2 I problemi:
P : min cTxAx � bx � 0
e
Q : min cTxAx+ y = b
x; y � 0
sono equivalenti.
25
Dimostrazione. Si considerino gli insiemi ammissibili
X = fx 2 Rn : Ax � b; x � 0g
Y =�(x; y) 2 Rn+m : Ax+ y = b; x; y � 0
e le trasformazioni
� :cTx;X;min
�!cTx+ 0Ty; Y;min
�con
�X(x) =
�x
b�Ax
�
e
:cTx+ 0Ty; Y;min
�!cTx;X;min
�con
Y (x; y) = x:
Si ha:
1. fx : Ax � b; x � 0g = ; se e solo se f(x; y) : Ax + y = b; x; y �0g = ;. Infatti se esiste x 2 fx : Ax � b; x � 0g allora de�nendoy = b � Ax si ottiene una soluzione ammissibile per Q; viceversa, se(x; y) �e una soluzione ammissibile per Q, si vede immediatamente chex �e ammissibile per P ;
2. se esiste una successione fxkg ammissibile per un problema P conlimcTxk = �1, la successione, fxk; ykg con yk = b � Axk, forniscela dimostrazione di illimitatezza per il corrispondente problema Q. Ilviceversa si dimostra del tutto analogamente;
3. attraverso le trasformazioni �X e Y si ottiene la corrispondenza cercataper gli ottimi dei due problemi. Infatti, se x? �e un ottimo per P , lacoppia
�x? b�Ax?
�rappresenta una soluzione ammissibile per Q.
Nessuna diversa soluzione ammissibile per Q pu�o avere costo inferiore aquesta: se per assurdo esistesse una soluzione ammissibile
��x �y
�con
cT �x < cTx?, la soluzione �x risulterebbe ammissibile per P e di costoinferiore a cTx?; il viceversa �e immediato.
26
Teorema 3.3 Dato un qualunque insieme P 2 Rn, i problemi
minx;y;z
z (3.9)
z = maxfx; yg�xy
�2 P
e
minx;y;z
z (3.10)
z � x
z � y�xy
�2 P
sono equivalenti.
Dimostrazione. La funzione obiettivo e la direzione dell'ottimizzazionesono le medesimenelle due famiglie di problemi. Una coppia di trasformazioniutilizzabile per la dimostrazione di equivalenza �e data da
�X(x; y; z) = (x; y; z)
Y (x; y; z) = (x; y; z0 = maxfx; yg)
1. Se l'insieme X = fx; y; z : z = maxfx; yg ; (x; y) 2 Pg �e vuoto, allo-ra deve essere vuoto anche Y = fx; y; z : z � x; z � y; (x; y) 2 Pg eviceversa; infatti se esistesse una terna (x; y; z) in X la stessa terna for-nirebbe un punto ammissibile per Y ; se esistesse una terna ammissibile
per Y , poich�e la variabile z non compare nel vincolo
�xy
�2 P , baste-
rebbe de�nire z0 = max fx; yg per ottenere una soluzione ammissibiledi X.
2. Se il problema (3.9) �e illimitato, esiste una successione fxk; yk; zkg am-missibile con zk ! �1; la medesima successione prova l'illimitatezzadel problema (3.10); viceversa, data una successione fxk; yk; zkg ammis-sibile per il problema (3.10) e con costo divergente a �1, la successione
27
fxk; yk; z0k = maxfxk; ykgg risulta ammissibile per il problema (3.9) econ costo illimitato.
3. In�ne, per quanto riguarda l'ottimalit�a, si osservi che, se (x?; y?; z?) �eottimo per (3.9), allora �e anche ottimo per il secondo problema: se infat-ti esistesse una soluzione ammissibile (�x; �y; �z) per il secondo problema,con �z < z?, si avrebbe anche �x < z? e �y < z? e, pertanto, la soluzione(�x; �y;maxf�x; �yg) sarebbe ammissibile per il primo problema e con co-sto inferiore a z?; viceversa, data una soluzione ottimale (x?; y?; z?) peril problema (3.10), sicuramente si avr�a z? = maxfx?; y?g, poich�e altri-menti, non essendo la variabile z presente nei vincoli che de�niscono P ,sarebbe possibile costruire soluzioni ammissibili con costo strettamenteminore a z?. La terna (x?; y?; z?) risulta dunque ottimale anche per(3.9).
Grazie a questo teorema �e quindi possibile trasformare problemi di mini-max in problemi equivalenti. Ad esempio, il problema non lineare
minx
max�cT1 x; c
T2 x; : : : ; c
Tk x
Ax = b
x � 0
risulta equivalente al problema di PL
minz;x
z
z � cT1 x
z � cT2 x
: : :
z � cTk x
Ax = b
x � 0:
E' anche importante notare, in questa trasformazione, che non �e neces-sario, a�nch�e due famiglie di problemi siano equivalenti, che esista una tra-sformazione dell'insieme ammissibile di un problema nell'insieme ammissibile
28
dell'altro: attraverso la trasformazione �X ad esempio non �e possibile otte-nere soluzioni ammissibili (x; y; z) del problema (3.10) con z > x; z > y. E'importante, come si vede in questo caso, che le mappe � e abbiano co-me dominio un insieme che contiene i possibili punti di ottimo del problematrasformato, non necessariamente tutti i punti ammissibili.
Nel seguito le dimostrazioni di equivalenza verranno spesso presentatesottintendendo le trasformazioni tra famiglie di problemi, ma evidenziandosolamente le trasformazioni dell'insieme ammissibile di un problema nell'al-tro e viceversa, oppure le trasformazioni tra le funzioni obiettivo dei dueproblemi. Generalmente inoltre, per non appesantire troppo la notazione,si individuer�a una famiglia di problemi con un suo generico rappresentante,evitando quindi la presentazione formale della tripla.
La veri�ca di equivalenza pu�o essere e�ettuata sfruttando la seguentecondizione su�ciente:
Teorema 3.4 Due famiglie di problemi di minimizzazione P : minx2X f(x)e Q : miny2Y g(y) sono equivalenti se esistono due funzioni
� : X ! Y e : Y ! X
tali che:1. X = ; se e solo se �(X) = ; e Y = ; se e solo se (Y ) = ;;2. inoltre
8x 2 X =) g(�(x)) � f(x)
e
8 y 2 Y =) f( (y)) � g(y)
Dimostrazione.
1. Se esiste una successione di soluzioni ammissibili fxkg � X tale chelimk f(xk) = �1, considerando la successione fykg con yk = �(xk), siosserva che
g(yk) = g(�(xk)) � f(xk)! �1
da cui segue che Q �e illimitato. Il viceversa si dimostra analogamente;
29
2. se x? �e un ottimo per P , allora y? = �(x?) �e un ottimo per Q. Infatti, seesistesse una soluzione ammissibile �y 2 Y per Q con costo g(�y) < g(y?),si avrebbe anche che
f( (�y)) � g(�y) < g(y?) = g(�(x?)) � f(x?)
da cui segue l'assurdo.
Come esempio di applicazione della condizione su�ciente appena dimo-strata si consideri il caso dei problemi con variabili non vincolate in segno.La propriet�a verr�a ora dimostrata in un caso pi�u generale di quello visto peril caso lineare.
Teorema 3.5 I problemi:
P : minx2X
f(x)
e
Q : minf(u � v)
u� v 2 X
u; v � 0
sono equivalenti.
Dimostrazione.
1. i due problemi sono o entrambi ammissibili o entrambi non ammissibili.Infatti, se 9 �x 2 X, scegliendo
�ui = maxf0; �xig i = 1; : : : ; n (3.11)
�vi = �minf0; �xig i = 1; : : : ; n (3.12)
si ottiene una soluzione��u �v
�ammissibile perQ; viceversa se
��u �v
��e ammissibile per Q, si vede immediatamente che �x = �u� �v �e ammis-sibile per P .
2. de�nendo
�(x) =
�uv
�
30
con u e v de�niti tramite le (3.11) e (3.12) e
(u; v) = u� v
si ottengono due mappe tra gli insiemi ammissibili dei due problemiche soddisfano i requisiti del teorema 3.4. Infatti
g(�(x)) = g(
�max(0; x)�min(0; x)
�) = f(max(0; x) + min(0; x)) = f(x)
e
f( (u; v)) = f(u � v) = g(u; v)
Vale la pena osservare a questo punto che spesso uno stesso problema pu�oessere trasformato in diversi problemi equivalenti fra loro. Ad esempio si pu�ovedere come �e possibile trasformare un problema con variabili libere in segnoin uno equivalente che ha solo una variabile in pi�u rispetto all'originale. Quiper semplicit�a ci si limiter�a a presentare il caso in cui tutte le variabili sianolibere in segno:
Teorema 3.6 I problemi
P : minx2X
f(x)
e
Q : minf(y � v1)
y � v1 2 X
y � 0 2 Rn
v � 0 2 R
sono equivalenti.
(con 1 si �e indicato un vettore di dimensione opportuna i cui elementisono tutti pari ad 1)
Dimostrazione. La trasformazione che permette di dimostrare l'equi-valenza �e la seguente:
� : x 2 X 7!
�yv
�
31
con
v = �minf0; minj=1;::: ;n
fxjgg
e
yj = xj + v;
mentre
(y; v) = x
con
xj = yj � v j = 1; : : : ; n:
La dimostrazione formale dell'equivalenza viene lasciata come esercizio.
32
Capitolo 4
Teoria della Programmazione
Lineare
4.1 Basi e soluzioni di base nella programma-
zione lineare
Si consideri un problema di programmazione lineare in forma standard:
min cTxAx = bx � 0
E' possibile, senza perdita di generalit�a, assumere la validit�a della seguenteipotesi:
1. Il numero m di righe della matrice A 2 Rm�n �e strettamente minoredel numero di colonne;
2. la matrice A ha rango pari al numero m di righe.
E' chiaro che in molti casi queste ipotesi non sono veri�cate. Tuttavia �epossibile ridurre l'analisi dei problemi di PL alle sole situazioni nelle quali ledue ipotesi sono valide. Da un punto di vista formale, si hanno i seguenticasi:
33
1. m > n: in questo caso nel sistema di equazioni Ax = b compaionopi�u equazioni che incognite. Segue che o il sistema �e privo di soluzioni,nel qual caso il problema di PL sar�a non ammissibile, oppure, se esistealmeno una soluzione di Ax = b, almeno un'equazione �e ridondante epu�o essere eliminata. Si pu�o ripetere l'operazione �no a che m = n;
2. m = n: il sistema di equazioni �e quadrato. Se det(A) 6= 0, esiste un'uni-ca soluzione del sistema Ax = b: se tale unica soluzione ha componentitutte non negative, essa sar�a anche ottimale; se invece almeno unacomponente �e negativa, il problema di PL �e inammissibile. Se invecedet(A) = 0, come nel caso precedente, o il sistema non ha soluzioni, op-pure almeno un'equazione pu�o essere eliminata. Ci si riconduce quindial caso m < n;
3. m < n: ancora, eliminando tutte le equazioni ridondanti, si arriva adun sistema, equivalente a quello iniziale, caratterizzato da una matricedei coe�cienti A con rango(A) = m.
Le considerazioni fatte qui sopra ci autorizzano a considerare solo proble-mi di PL che soddisfano alle due condizioni date. Tuttavia occorre ricordareche volendo giungere ad un algoritmo risolutivo, occorrer�a identi�care unmetodo che permetta di trasformare un problema in uno equivalente chesoddis� le ipotesi. Fortunatamente lo stesso metodo che verr�a utilizzato perla risoluzione dei problemi di PL, potr�a essere utilizzato anche per la veri�cadelle ipotesi, come si vedr�a pi�u avanti.
Si ipotizzi quindi che il rango di A sia m, pari al numero delle righe diA; in questo caso �e sempre possibile scegliere tra le n colonne della matriceA un sottoinsieme costituito da m colonne fra loro linearmente indipenden-ti. Ammettendo che tali colonne abbiano indici corrispondenti ad un datoinsieme B e che le restanti abbiano indici nell'insiemeN = f1; : : : ; ng nB, sipotr�a scrivere (a parte un eventuale scambio di colonne)
A = [AB AN ]
dove AB �e una matrice (m;m) con determinante non nullo che viene detta
base.
Il nome di \base" deriva dal fatto che le m colonne di AB costituisconouna base per lo spazio euclideo m{dimensionale, cio�e ogni elemento di Rm
34
pu�o essere espresso in modo univoco tramite una combinazione lineare dellecolonne di AB. Ricordando che anche il termine noto b �e un vettore m{dimensionale, si ha che il sistema di equazioni
ABx = b
ammetter�a sempre una (ed una sola) soluzione
xB = A�1B b 2 Rm:
Se si considera il vettore n�dimensionale x =
�xB0
�si vede immediata-
mente che tale vettore �e una soluzione del sistema Ax = b. Infatti
Ax = [AB AN ]
�xBxN
�= ABxB +AN0 = ABA
�1B b+ 0 = b:
Una soluzione x cos�� costruita viene chiamata
soluzione di base
corrispondente alla base AB. Le variabili xB si dicono
variabili di base.
Si noti che una soluzione di base possiede sempre almeno n�m compo-nenti uguali a zero. Potrebbe tuttavia averne anche pi�u di n � m nulle; intal caso la corrispondente soluzione di base si dice
soluzione di base degenere.
Per estensione anche la base si dir�a degenere. Una soluzione �x si dice
ammissibile
se soddisfa tutti i vincoli del problema, cio�e se
A�x = b
�x � 0:
35
4.2 Interpretazione del concetto di base
I concetti di base e di soluzione ammissibile di base si prestano a facili inter-pretazioni per alcuni dei problemi presentati nel capitolo ??. Ad esempio,una soluzione di base nei problemi della dieta od in quelli di miscelazioneottimale corrisponde ad una ricetta composta da un numero ridotto di ele-menti. La base corrisponde ad un insieme di cibi i cui contributi nutritivi,opportunamente combinati, possono soddisfare esattamente qualsiasi esigen-za. Occorre ricordare che, nel problema della dieta, spesso i vincoli sonoespressi come disequazioni lineari; per poter parlare di basi e di soluzioni dibase, occorrer�a quindi inserire delle variabili di slack e/o di surplus. Le basipotranno pertanto essere costituite anche da coe�cienti di variabili di slacko di surplus, non solo da variabili associate a cibi. Pu�o sembrare a primavista piuttosto restrittivo limitarsi a considerare le soluzioni di base, poich�e,ad esempio, in un problema di dieta ottimale in cui si debba ottenere la ri-cetta ottimale miscelando 100 cibi diversi in modo da soddisfare a 3 richieste(vincoli) sul contenuto nutritivo, le soluzioni di base saranno costituite danon pi�u di 3 cibi a livello strettamente positivo. Nel prossimo capitolo sivedr�a come ci�o non costituisca a�atto una restrizione; naturalmente se, pernecessit�a diverse, quali ad esempio quella di voler garantire una certa variet�aalla dieta, si desiderassero ricette con pi�u elementi non nulli (ad esempio,con almeno un primo, un secondo, un contorno), occorrerebbe modi�care ilproblema, inserendo vincoli opportuni; in genere tali vincoli richiedono l'usodi variabili binarie o variabili indicatrici.
4.2.1 Basi e soluzioni di base nei problemi di usso
Pi�u complessa, ma di notevole importanza sia teorica che applicativa, �e l'in-terpretazione di base nei problemi di ottimizzazione su gra� introdotti nelcapitolo ??. Sia dato un grafo G = hV;Ei con jV j = m e jEj = n, e sia A lamatrice di incidenza (nodi{archi). Si consideri un problema di usso di costominimo
min cTfAf = df � 0
(4.1)
in cui si �e supposto che la capacit�a minima di ogni arco sia 0 e quella massimasia +1; il vettore d rappresenta la di�erenza tra usso uscente da ciascun
36
nodo e usso entrante. Il generico problema con vincoli sul usso sia inferioriche superiori pu�o essere trattato con relativa semplicit�a come estensione delproblema qui considerato. Se, come si ipotizza in genere,
Pi2V di = 0,
sicuramente una delle equazioni Af = d �e ridondante e pu�o essere eliminatasenza che l'insieme ammissibile del problema vari { naturalmente, se fosseP
i2V di 6= 0, il problema non sarebbe ammissibile. Questo signi�ca ancheche, ammesso che esistano soluzioni ammissibili, non potranno certamenteesistere soluzioni di base, almeno se si intende il concetto di base in sensostretto, come de�nito in precedenza. Il rango della matrice di incidenza nonpu�o essere superiore a m� 1. Scelto comunque un nodo v, sia Anv la matricedi incidenza da cui �e stata cancellata la riga corrispondente a v e sia dnv ilvettore d modi�cato in modo analogo. Ricordando che la matrice A ha mrighe ed n colonne, vale la seguente propriet�a fondamentale:
Teorema 4.1 La matrice A di incidenza di un grafo G = hV;Ei ha rangopari a jV j � 1 se e solo se il grafo �e connesso (debolmente).
La dimostrazione di questo importante teorema si basa su altre propriet�a,altrettanto fondamentali:
Teorema 4.2 Un grafo �e connesso se e solo se possiede un albero di suppor-to.
Teorema 4.3 La matrice di incidenza di un albero H = hV; T i di supportoper G ha rango jV j � 1; inoltre essa pu�o essere scritta in forma triangolare,con elementi tutti pari a +1 o a �1 sulla diagonale.
I teoremi 4.2 e 4.3 implicano la condizione su�ciente del teorema 4.1; ilteorema seguente permette invece di dimostrarne la necessit�a.
Teorema 4.4 Gli archi corrispondenti alle colonne di una base della ma-trice di incidenza di G (privata di una riga qualsiasi) formano un albero disupporto per G.
Dimostrazione. (teorema 4.2): Dato un grafo connesso �e possibile elimi-nare un arco alla volta, mantenendo sempre la connessione; dopo un numero�nito di iterazioni si ottiene un grafo connesso nel quale �e impossibile eli-minare un arco senza perdere la connessione: questa condizione �e necessaria
37
e su�ciente perch�e il grafo risultante sia un albero. La dimostrazione del-l'implicazione in senso opposto �e banale: se un grafo contiene un albero disupporto, �e certamente connesso.
Dimostrazione. (teorema 4.3) Il rango della matrice di incidenza di unsottografo di G qualsiasi non pu�o essere superiore a jV j � 1; dimostriamoche, nel caso degli alberi di supporto, �e esattamente pari a jV j � 1. Ladimostrazione viene fatta per induzione su jV j. Il lemma vale se jV j = 2poich�e in questo caso la matrice di incidenza ha una delle due forme possibili:�
+1�1
�;
��1+1
�
ed eliminando una qualunque delle due righe si ottiene una matrice quadratadi rango jV j � 1 = 1, triangolare con elemento sulla diagonale pari a 1 o a�1.Supponendo valido il lemma per jV j = k, lo si dimostra ora per jV j = k+ 1.Per una propriet�a elementare dei gra�, in ogni albero con almeno un arcoesistono almeno due foglie; sicuramente sar�a quindi sempre possibile scegliereuna foglia, w 2 V , non coincidente con il nodo v (non �e detto che v sia unafoglia, ma anche se lo fosse se ne potrebbe sempre trovare un'altra). Siae 2 T l'unico arco dell'albero H incidente su w; eliminando dall'albero H ilnodo w e l'arco e, si ottiene un grafo ancora privo di cicli (poich�e lo �e H)e connesso (poich�e si �e eliminata una foglia), cio�e si ottiene un albero H 0.H 0 �e un albero con k nodi, quindi, per l'ipotesi di induzione, la sua matricedi incidenza, privata della riga associata a v, sar�a quadrata, invertibile escrivibile in forma triangolare (ad esempio, superiore) con tutti elementi paria �1 sulla diagonale. Sia T 0 tale matrice. Orlando T 0 in basso con la rigaassociata a w e a destra con la colonna corrispondente a e si ottiene la matriceseguente: �
T 0 u0T �1
�
dove il vettore u conterr�a un solo elemento non nullo. Essendo T 0 triangolaresuperiore, anche questa matrice sar�a triangolare e con elementi pari a �1sulla diagonale. Da qui segue che la matrice cos�� ottenuta �e invertibile e ilteorema �e dimostrato. Tale matrice corrisponde ad un riordinamento dellerighe e delle colonne della matrice di incidenza, privata di una riga, dell'albero
38
Si �e quindi dimostrato che se un grafo G �e connesso, esso possiede unalbero di supporto e, poich�e la matrice di incidenza dell'albero di supportoha rango jV j � 1, anche la matrice di incidenza ha rango jV j � 1.
Occorre ora provare che se la matrice di incidenza di G ha rango jV j �1, esso �e connesso, cio�e possiede un albero di supporto. La dimostrazioneconsiste nel mostrare che le colonne corrispondenti ad una sottomatrice dellamatrice di incidenza di rango jV j � 1 sono associate agli archi di un alberodi supporto per G.
Dimostrazione. (Teorema 4.4) Si consideri una sottomatrice di A dirango jV j � 1 e siano Ae1 ; Ae2; : : : ; AejV j�1
le sue colonne, corrispondenti adun sottografo di G. In tale sottografo non pu�o esistere alcun ciclo; infatti, sein un grafo qualsiasi esiste un ciclo orientato, diciamo
C = fv0; v1; : : : ; vk; vk+1 = v0g;
composto dagli archi (v0; v1); : : : ; (vk; v0) ricordando che la colonna della ma-trice di incidenza corrispondente ad un arco (i; j) pu�o essere scritta comeei � ej, dove ei �e l'i{esimo versore, sommando le colonne della matrice diincidenza del ciclo si otterrebbe:
(ev0 � ev1) + (ev1 � ev2) + � � �+ (evk�1� evk) + (evk � ev0) = 0
Pertanto le colonne della matrice di incidenza associate ad un ciclo sonolinearmente dipendenti (una loro combinazione lineare con coe�cienti pariad 1 fornisce il valore 0). Se il ciclo fosse non orientato, (si ricordi che unciclo non orientato �e un grafo orientato in cui modi�cando l'orientamento dialcuni archi si pu�o ottenere un ciclo orientato) basterebbe scegliere un versodi percorrenza qualsiasi e moltiplicare per +1 gli archi percorsi \in avanti"e per �1 (il che equivale a cambiarne il verso) gli archi percorsi all'indietro.Quindi anche in questo caso si otterrebbe una combinazione non banale chedimostra la dipendenza lineare.
Si �e quindi dimostrato che se un sottoinsieme delle colonne di una matricedi incidenza �e formato da vettori linearmente indipendenti, il grafo corrispon-dente �e aciclico; nel caso di un sottoinsieme di jV j�1 colonne tale grafo sar�aun albero di supporto, essendo aciclico e composto da jV j � 1 archi.
Dai teoremi appena dimostrati segue quindi che vi �e corrispondenza biu-nivoca tra alberi di supporto di un grafo connesso e matrici (jV j � 1; jV j � 1)invertibili.
39
Il teorema 4.3, assieme al teorema th:aciclicita, implica un'altra impor-tante propriet�a dei problemi di usso a costo minimo, e cio�e che se il terminenoto d nella (4.1) �e intero, allora ogni soluzione di base del problema di PLcorrispondente sar�a intera. Infatti, poich�e ogni soluzione di base si ottienerisolvendo un sistema di equazioni del tipo
ABf = d
e poich�e AB pu�o essere portata in forma triangolare superiore con elementisulla diagonale tutti pari a �1, risolvendo il sistema partendo dall'ultimaequazione si vede immediatamente che tutte le componenti di f sarannocombinazioni lineari a coe�cienti interi di d.
Esempio 4.1 Si consideri il problema di usso a costo minimo caratterizzatodal grafo in �gura 4.1 in cui la quantit�a indicata sugli archi rappresenta ilcosto associato all'arco. Si suppone che il vettore d sia de�nito da d(A) =
Figura 4.1: Problema di usso a costo minimo
������������@
@@@@@@@@@@@r r r
r r r
r r r
GH
I
DE F
AB
C
- -
- -
� �
?
?
6
6
6
6
R
�
�
R
2 6
3 4
4 3
2
3
2
2
1
3
1
5
6
1
+8; d(E) = �3; d(I) = �5 e d(v) = 0 per ogni altro nodo v. Il sottograforappresentato in �gura 4.2 �e un albero di supporto. La sottomatrice della
40
Figura 4.2: Flusso ammissibile - albero di supporto
������������
r r r
r r r
r r r
GH
I
DE F
AB
C
- -
-
?
?
6
�
�
2 6
4
2
3
2
5
6
matrice di incidenza corrispondente a tale albero �e data da
AD DG EB EC EF GE GH HI
A +1 0 0 0 0 0 0 0B 0 0 �1 0 0 0 0 0C 0 0 0 �1 0 0 0 0D �1 +1 0 0 0 0 0 0E 0 0 +1 +1 +1 �1 0 0F 0 0 0 0 �1 0 0 0G 0 �1 0 0 0 +1 +1 0H 0 0 0 0 0 0 �1 +1I 0 0 0 0 0 0 0 �1
:
Eliminando una riga da questa matrice, ad esempio la riga corrispondentead A, si ottiene una matrice quadrata. Il teorema 4.3 garantisce che questamatrice �e una base.Tale teorema a�erma che �e possibile trasformare in formatriangolare superiore tale sottomatrice. La tecnica per ottenere tale trasfor-mazione, indicata dal procedimento per induzione usato nella dimostrazione,consiste nell'iniziare ad elencare i nodi partendo da una foglia e aggiungendol'unico arco su di essa incidente. E' possibile iniziare da una qualsiasi fo-glia, purch�e non coincidente con il nodo associato alla riga che si �e eliminatadalla matrice di incidenza. Ad esempio, si pu�o iniziare con la foglia I e l'ar-co (H; I) incidente su di essa; immaginando di eliminare tale foglia e l'arcocorrispondente si otterrebbe un albero con un nodo in meno. Se si sapesse
41
portare in forma triangolare superiore la matrice di incidenza di tale albe-ro, la si potrebbe orlare con la riga associata ad I e la colonna associata ad(H; I) mantenendo la forma triangolare. A questo punto si prosegue in mo-do ricorsivo, analizzando il sottoalbero privo della foglia I. Anche in questosottoalbero esister�a almeno una foglia (non coincidente con A). Proseguendosi potrebbe ottenere la seguente sequenza di foglie: H;F;C;B;E;G;D. Siottiene quindi la matrice riordinata
AD DG GE EB EC EF GH HI
D �1 +1 0 0 0 0 0 0G 0 �1 +1 0 0 0 +1 0E 0 0 �1 +1 +1 +1 0 0B 0 0 0 �1 0 0 0 0C 0 0 0 0 �1 0 0 0F 0 0 0 0 0 �1 0 0H 0 0 0 0 0 0 �1 +1I 0 0 0 0 0 0 0 �1
Osservando che il vettore richieste, riordinato coerentemente, ha la forma
dT =�0 0 �3 0 0 0 0 �5
�si determina immediatamente la soluzione di base corrispondente:
f(HI) = 5
f(GH) = 0 + f(HI) = 5
f(EF ) = 0
f(EC) = 0
f(EB) = 0
f(GE) = 3 + f(EB) + f(EC) + f(EF ) = 3
f(DG) = f(GE) + f(GH) = 8
f(AD) = f(DG) = 8
che �e una soluzione ammissibile di base. Il costo di questa soluzione �e paria 2 � 8 + 3 � 8 + 5 � 3 + 2 � 5 + 6 � 5 = 95. Esistono altre soluzioni di baseammissibili, alcune delle quali con costo inferiore a quello della soluzionequi determinata. Non �e detto che un albero di supporto corrisponda sempread una base ammissibile. Ad esempio, sostituendo l'arco (H; I) con l'arco(I; F ), si otterrebbe un nuovo albero, ma non una soluzione ammissibile.
42
4.3 Il teorema fondamentale della program-
mazione lineare
Un aspetto fondamentale del metodo del simplesso che verr�a presentato pi�uavanti �e che, nel corso delle iterazioni, esso produce soluzioni ammissibili(cio�e soluzioni che soddisfano tutti i vincoli) di base. Il teorema seguentefornisce il necessario supporto teorico:
Teorema 4.5 Si consideri un problema di programmazione lineare in formastandard, con m vincoli, n incognite, m < n e di rango m.
1. esiste una soluzione ammissibile se e solo se esiste almeno una solu-zione ammissibile che �e anche di base;
2. esiste una soluzione ottimale se e solo se esiste almeno una soluzioneottimale che �e anche di base.
Siamo quindi autorizzati a limitarci all'esplorazione delle soluzioni di ba-se, poich�e tra di esse, se il problema ammette ottimo, si trover�a la soluzioneottimale; ci�o non vuol dire che non possano esistere soluzioni ottimali non dibase, ma almeno una delle soluzioni ottimali deve essere di base. Le eventua-li soluzioni ottimali alternative avranno, naturalmente, tutte lo stesso costo.Si osservi che questo teorema permette, in un certo senso, di passare da unproblema in cui lo spazio delle soluzioni da analizzare per trovare l'ottimo �eun \continuo", ad un insieme di candidati ottimi discreto, anzi, �nito: in-fatti le soluzioni di base nascono dall'identi�cazione di una sottomatrice AB
invertibile costituita da m colonne della matrice originale A, e pertanto ilnumero complessivo di possibili basi non potr�a superare il numero (�nito) dimodi in cui �e possibile scegliere m colonne da un insieme di n, e cio�e
�n
m
�.
Naturalmente la �nitezza del numero massimo di basi, se da un lato permettedi pensare ad una procedura �nita per la risoluzione di un generico problemadi programmazione lineare per il quale sia nota l'esistenza di una soluzioneottima, dall'altro non rappresenta un risultato molto potente. Il numero dibasi di un problema di programmazione lineare cresce, al crescere di n ed mad una velocit�a tale da rendere totalmente impraticabile la strada dell'enu-merazione esplicita di tutte le soluzioni di base. Il metodo del simplesso si�e spesso dimostrato in pratica estremamente e�ciente nel determinare unabase ottimale evitando di generare esplicitamente tutte le soluzioni di base,compiendo cio�e un'enumerazione implicita delle basi.
43
Come ulteriore osservazione si pu�o far notare che, se da un lato questapropriet�a ha fornito la giusti�cazione teorica del metodo del simplesso, dal-l'altro �e stata spesso considerata come una caratteristica irrinunciabile deglialgoritmi per la programmazione lineare: solo recentemente sono stati svilup-pati algoritmi radicalmente diversi dal metodo del simplesso che procedonogenerando via via soluzioni intermedie non di base.
Passiamo ora alla dimostrazione del teorema fondamentale, che contienein nucleo alcuni degli aspetti che caratterizzano il metodo del simplesso.
Dimostrazione.
1. La condizione su�ciente si dimostra banalmente; per quanto riguardala condizione necessaria, si consideri una soluzione ammissibile �x delsistema Ax = b. La matrice A pu�o essere vista come accostamento din vettori colonna:
A = [A1A2 � � �An]
e pertanto il sistema di equazioni Ax = b pu�o essere scritto nella forma
nXj=1
Ajxj = b;
in altri termini si pu�o esprimere il vettore b come combinazione linearedelle colonne di A mediante i coe�cienti xi. Sia p, (0 � p � n), ilnumero di componenti non nulle nel vettore �x. Si pu�o sempre supporreche le eventuali componenti non nulle occupino i primi p posti nelvettore �x: sia cio�e
�x =��x1 �x2 : : : �xp 0 : : : 0
�T:
Avendo espresso �x in questo modo, sar�a vero che
pXj=1
Aj�xj = b:
Per quel che riguarda le colonne dei coe�cienti delle componenti nonnulle di �x si possono distinguere due situazioni possibili:
(a) le colonne A1; : : : ; Ap sono linearmente indipendenti. In questocaso p �e certamente non maggiore di m, poich�e non possono esi-stere pi�u di m colonne linearmente indipendenti in una matrice
44
di rango m. Se p = m la soluzione �x �e una soluzione di base(la corrispondente sottomatrice AB =
�A1 : : : Am
�di A �e in-
vertibile); se invece p < m, per una propriet�a elementare dellematrici, sicuramente tra le colonne Ap+1; : : : ; An se ne possonoscegliere m� p che, assieme alle prime p colonne, formano un si-stema di m vettori linearmente indipendenti (cio�e una base). Sia-no Ai1; Ai2; : : : ; Aim�p tali colonne. Il vettore �x rappresenta unasoluzione di base corrispondente alla base
AB =�A1 A2 � � � Ap Ai1 Ai2 � � � Aim�p
�Infatti, la combinazione lineare
A1�x1 + � � �+Ap�xp +Ai10 + � � �+Aim�p0 = b
�e ancora valida e, dato che i coe�cienti formano una matrice in-vertibile, la soluzione �x1; : : : ; �xp; 0; : : : ; 0 sar�a l'unica soluzione (dibase) del sistema ABx = b. In questo caso, in cui sono nulle alcu-ne delle componenti della soluzione di base (oltre naturalmente aquelle fuori base), si dice che la soluzione di base e la base stessasono degeneri.
(b) le colonne A1; : : : ; Ap sono linearmente dipendenti. La tecnicadimostrativa consiste in questo caso nel generare soluzioni ammis-sibili con un numero decrescente di componenti non nulle, �noa ridursi al caso in cui i coe�cienti di tali variabili formino uninsieme di vettori linearmente indipendenti (caso a). Dalla de�ni-zione di vettori linearmente dipendenti si deduce che sicuramenteesistono p coe�cienti d1; d2; : : : ; dp non tutti nulli tali che
pXj=1
Ajdj = 0:
Ricordando che vale la relazionepX
j=1
Aj�xj = b
si ottiene immediatamente chepX
j=1
Aj(�xj + �dj) = b 8� 2 R:
45
Introducendo il vettore n�dimensionale
d =�d1 d2 : : : dp 0 0 : : : 0
�T;
si ha
A(�x+ �d) = b:
Mentre per qualsiasi valore di �, il vettore �x + �d �e soluzione delsistema Ax = b, non �e detto che in generale tale vettore sia solu-zione ammissibile. L'idea �e a questo punto di scegliere � in modotale da annullare almeno una componente di �x+ �d senza perderel'ammissibilit�a. Si �e visto che non tutte le componenti di d sononulle; si consideri ora ciascuna componente del vettore �x+ �d, con� 2 R (ci si pu�o limitare alle componenti di indice j = 1; : : : ; p,essendo tutte le altre pari a 0):
� se dj = 0 allora �xj + �dj = �xj > 0 8�;
� se dj < 0 allora �xj + �dj � 0 8� � ��xjdj;
� se dj > 0 allora �xj + �dj � 0 8� � � �xjdj.
Dovendo rispettare il vincolo sul segno di ciascuna componentedel vettore �xj + �dj, occorrer�a scegliere per � la condizione pi�urestrittiva. Siano:
�l = maxj:dj>0
���xjdj
�
�u = minj:dj<0
���xjdj
�:
Si noti che �l < 0 e che �u > 0 e che almeno uno dei due termini �l,�u �e �nito, grazie al fatto che non tutti gli elementi dj ; j = 1; : : : ; psono nulli.Supponendo che ad esempio �u sia �nito, allora il vettore
x := �x+ �ud
�e ancora soluzione, ma con al pi�u p� 1 componenti non nulle. Seinvece �u = +1, sicuramente si avr�a �1 < �l < 0; nel qual casosar�a il vettore
x := �x+ �ld
46
ad avere al pi�u p� 1 componenti non nulle. Sostituendo al postodi �x la nuova soluzione ammissibile x, si pu�o ripetere il procedi-mento, �no a giungere, in non pi�u di p iterazioni, ad una soluzionecorrispondente a colonne linearmente indipendenti (caso a), cio�ead una soluzione di base.
2. Per dimostrare la seconda parte del teorema, cio�e che se esiste una solu-zione ottimale, esiste pure una soluzione ottimale di base (il viceversa �ebanale), si procede sulla falsariga della dimostrazione della prima par-te. Si ipotizzi di avere a disposizione una soluzione �x ammissibile eottimale. Si distinguono ancora i due casi:
(a) le colonneA1; : : :Ap sono linearmente indipendenti. In questo casola soluzione considerata �e gi�a (a parte l'eventuale aggiunta di zeri)una soluzione di base, ed il teorema �e dimostrato;
(b) le colonne sono linearmente dipendenti. Procedendo come nellaprima parte della dimostrazione, si osserva che, perturbando ilvettore �x, il costo
cT �x
viene modi�cato in
cT (�x+ �d):
Da quanto gi�a illustrato, si vede immediatamente che �x + �d �eammissibile per ogni � 2 [�l; �u]. Da qui si deduce che cTd deveessere necessariamente nullo: infatti, se cTd fosse strettamentepositivo, scegliendo "l � " < 0 si avrebbe
cT (�x+ �d) = cT �x+ �cTd
< cT �x
che �e assurdo essendo �x una soluzione ottimale. Analogamente sefosse cTd < 0, scegliendo 0 < " � "u si avrebbe
cT (�x+ �d) = cT �x+ �cTd
< cT �x
47
Pertanto, essendo cTd = 0, lo spostamento ammissibile da �x a �x+�d; con � 2 [�l; �u], e�ettuato come indicato nella prima parte delladimostrazione mantiene, oltre all'ammissibilit�a, anche l'ottimalit�a.La nuova soluzione, ancora ottimale, avr�a al pi�u p�1 componentinon nulle; iterando il procedimento ci si riconduce in un numero�nito di passi, al caso a.
La dimostrazione precedente �e importante da un punto di vista metodo-logico poich�e evidenzia una delle tecniche principali su cui �e basato il pi�upopolare algoritmo per la risoluzione di problemi di PL: il metodo del sim-plesso. L'aspetto pi�u interessante �e la tecnica mediante la quale si passa dauna soluzione ammissibile ad un'altra mediante uno spostamento ammissi-bile. L'algoritmo del simplesso, come si vedr�a nei prossimi paragra�, sfruttaesattamente lo stesso procedimento, passando da una soluzione ammissibiledi base all'altra mediante spostamenti ammissibili. A questo proposito, siricorda che, considerato un insieme generico S � Rn ed un punto x 2 S, sidice che un vettore d 2 Rn rappresenta direzione ammissibile in x se esiste�� > 0 tale che
x+ �d 2 S 8 � 2 [0; ��]:
In base alla de�nizione la direzione degenere d = 0 �e sempre ammissibile: inquesto caso si ammette anche che �� = 0. Nel caso di insiemi ammissibili diproblemi di programmazione lineare in forma standard, si ha
S = fx 2 Rn : Ax = b; x � 0g
quindi le direzioni ammissibili in �x saranno caratterizzate da
A(�x+ �d) = b; �x+ �d � 0
cio�e da
Ad = 0; �x+ �d � 0:
Si vede quindi che le direzioni ammissibili sono identi�cabili con un sot-toinsieme degli elementi del nucleo (Ker) della matrice A; nella dimostra-zione del teorema fondamentale, in particolare nella seconda parte, gioca un
48
ruolo fondamentale la possibilit�a di compiere un passo non nullo sia in dire-zione d che in direzione �d. Questo equivale, nella scelta di una direzioneammissibile d, a poter compiere spostamenti ammissibili caratterizzati daun passo � sia positivo che negativo; da qui segue immediatamente che, pergarantire la non negativit�a, per ciascuna componente �xj = 0 si avr�a neces-sariamente dj = 0. Le direzioni utilizzate nella dimostrazione del teoremafondamentale sono quindi \bi{ammissibili" (cio�e ammissibili in entrambe ledirezioni). Si �e quindi anche implicitamente dimostrato che in corrispon-denza di una soluzione ammissibile non di base, esiste sempre almeno unadirezione bi{ammissibile. Nell'esempio seguente viene mostrata la tecnica diperturbazione ammissibile vista nella dimostrazione del teorema.
Esempio 4.2 Si consideri il seguente insieme dei vincoli di un problema diPL: 2
4 1 �1 1 0 2 1 2�1 0 0 1 1 2 10 0 1 1 �1 1 1
35 x =
24 311
35
x � 0:
�E immediato veri�care che il vettore �x =�1 1 1 1 1 0 0
�T�e una
soluzione ammissibile (cio�e veri�ca i vincoli sopra indicati). Tuttavia sicura-mente non �e una soluzione di base, avendo 5 elementi non nulli. Seguendo latecnica usata nella dimostrazione del teorema si individua una perturbazioneammissibile della soluzione �x.Le colonne corrispondenti agli elementi non nulli di A sono le prime 5; �efacile vedere che una combinazione lineare di tali colonne con coe�cienti adesempio pari a:
�1 0 �1 1 0
�Tfornisce il vettore nullo. Lo spostamento ammissibile avviene quindi nella
direzione d =�1 0 �1 1 0 0 0
�T. Scegliendo un passo � si ottiene il
49
nuovo punto
x(�) =
2666666664
1111100
3777777775+ �
2666666664
10�11000
3777777775=
2666666664
1 + �1
1� �1 + �100
3777777775
Per mantenere l'ammissibilit�a si dovr�a scegliere il passo � 2 [�1; 1]. Sce-gliendo ad esempio il passo �1 si ottiene la soluzione ammissibile �x =�0 1 2 0 1 0 0
�Tche �e di base, essendo le colonne numero 2, 3, 5
della matrice originale fra loro linearmente indipendenti; scegliendo invece il
passo � = 1, si ottiene la soluzione ammissibile �x =�2 1 0 2 1 0 0
�Tche non �e di base; iterando il procedimento, scegliendo ad esempio come coef-�cienti delle colonne numero 1, 2, 4, 5 i valori 2 4 1 1 si ottiene lo spo-
stamento ammissibile d =�2 4 0 1 1 0 0
�T; applicando il criterio
per la determinazione del passo massimo in entrambe le direzioni si ottieneche, essendo d non negativo, �u = +1 { come �e facile veri�care, infatti, tuttii punti
x(�) =
2666666664
2 + 2�1 + 4�0
2 + �1 + �00
3777777775
sono soluzioni ammissibili, per qualunque valore di � � 0. Per quantoriguarda invece gli spostamenti in direzione negativa, si ha
�l = maxj:dj>0
���xjdj
�= max
��2
2;�
1
4;�
2
1;�
1
1
�= �
1
4
da cui si ottiene la nuova soluzione ammissibile
�x =�
32 0 0 7
434 0 0
�50
E' facile veri�care che la sottomatrice costituita dalla prima, quarta e quintacolonna di A �e invertibile; la soluzione trovata �e dunque una soluzione di base.
Nei prossimi capitoli si vedr�a come questa tecnica di spostamento lungodirezioni ammissibili possa essere sfruttata per mettere a punto e�cientialgoritmi risolutivi per problemi di PL.
51
Capitolo 5
Il metodo del simplesso
5.1 Un esempio d'uso del metodo del simples-
so
Si consideri un problema di programmazione lineare caratterizzato solamenteda vincoli di \�" e variabili vincolate in segno; si ipotizzi anche che tutti itermini noti bi siano non negativi:
minnP
j=1
cjxj
nPj=1
aijxj � bi i = 1; : : : ;m
xj � 0 j = 1; : : : ; n:
Introducendo m variabili di slack per portare il sistema in forma standardsi arriva alla forma
minnP
j=1
cjxj
nPj=1
aijxj + si = bi i = 1; : : : ;m
xj � 0 j = 1; : : : ; nsi � 0 i = 1; : : : ;m:
(5.1)
Grazie alla presenza delle variabili di slack �e facile scrivere la soluzione
52
generale del sistema di equazioni (5.1):
si = bi �nX
j=1
aijxj i = 1; : : : ;m: (5.2)
In questo caso si vede immediatamente come il sistema che, in formastandard, contiene m equazioni ed n +m incognite, possa essere risolto as-segnando valore arbitrario a n variabili (si osservi che n = (n + m) � m,cio�e �e pari al numero delle incognite meno il rango del sistema). La rap-presentazione (5.2) viene a volte detta \dizionario", poich�e corrisponde allade�nizione di un simbolo (si) mediante altri simboli. Nella terminologia dellaprogrammazione lineare si dice anche che mediante la (5.2) le variabili di bases1; : : : ; sm sono esplicitate in funzione delle variabili non di base x1; : : : ; xn.Nel caso dell'esempio qui riportato, la matrice dei coe�cienti delle variabili dislack �e certamente una matrice invertibile, cio�e una base, essendo la matriceidentica.
Per introdurre il metodo del simplesso utilizziamo un semplice esempionumerico. Si consideri il problema
minx� 4y
x+ y � 1
x� 2y � 0
�x+ y �1
2x; y � 0
Inserendo le opportune variabili di slack ed introducendo una variabile ausi-liaria z per rappresentare la funzione obiettivo, il problema precedente pu�oessere scritto come
min z = x� 4y
s = 1 � x� y
t = �x+ 2y
u =1
2+ x� y
x; y; s; t; u � 0
Si dice che la forma precedente corrisponde alla rappresentazione del pro-blema originale in funzione della base costituita dalle variabili s; t; u; sarebbe
53
pi�u corretto dire che la base �e costituita dalla matrice dei coe�cienti di talivariabili, ma spesso si user�a indi�erentemente il termine \base" anche per in-dicare un insieme di variabili i cui coe�cienti formano una base. Le variabilix ed y sono \fuori base". Assegnando ad x ed y valori arbitrari, si ottengonotutte le soluzioni del sistema di equazioni appena scritto. Occorre ricordarsiper�o che qui stiamo trattando il caso di problemi con disequazioni { anche nelcaso standard compaiono delle disequazioni: sono i vincoli di non negativit�a{ anche se apparentemente semplici, queste disequazioni rappresentate daivincoli di segno costituiscono la vera novit�a della programmazione lineare,rispetto al classico trattamento dei sistemi di equazioni lineari.
Quando un sistema �e scritto nella forma del dizionario visto sopra, �e pos-sibile ottenere immediatamente una soluzione particolare assegnando valore0 a tutte le variabili fuori base: il vettore di valori cos�� ottenuto si dice so-luzione di base. Nel caso del sistema in esame, ponendo uguali a 0 le duevariabili fuori base x ed y si ottiene la soluzione di base
x = 0; y = 0; s = 1; t = 0; u =1
2;
il costo associato a questa soluzione di base �e z = 0.Il nucleo dell'algoritmo del simplesso �e l'operazione che ora stiamo per
descrivere, detta operazione di pivot o di cardine, mediante la quale si pas-sa dal dizionario corrispondente ad una base ad un dizionario relativo aduna base diversa, tramite semplici operazioni di trasformazione del sistemalineare. Lo scopo �e quello di ottenere cos�� facendo una soluzione di base conobiettivo inferiore.
Il ragionamento su cui si fonda l'operazione di pivot �e piuttosto elementa-re: nell'attuale soluzione di base tutte le incognite fuori base hanno valore 0:si cerca, se �e possibile, di incrementare il valore di una delle incognite fuoribase in modo tale da
1. generare un nuovo dizionario (associato ad una nuova base);
2. garantire che la soluzione di base associata al nuovo dizionario siaancora ammissibile;
3. migliorare l'obiettivo.
Consideriamo l'esempio: in corrispondenza della soluzione di base cor-rente sia x che y valgono 0. Se si provasse ad incrementare la sola variabile
54
x non si otterrebbe un miglioramento dell'obiettivo: infatti, essendo il costoz = x� 4y, mantenendo y = 0 e rendendo positivo, se possibile, x, si otter-rebbe un aumento di z, l'esatto opposto di ci�o che desidereremmo. Questonon signi�ca che nessuna soluzione con x positivo sia conveniente { signi�casoltanto che non �e conveniente incrementare x in questo momento. Al con-trario, un incremento di y, lasciando x a 0, porterebbe ad una diminuzionedel costo { una diminuzione di 4 unit�a per ogni unit�a di incremento di y. Diquanto �e possibile incrementare y, lasciando invariato x = 0? Per quantoriguarda il sistema di equazioni, non esistono vincoli ai valori assumibili day; tuttavia occorre rispettare i vincoli di non negativit�a per tutte le variabili.Esaminandoli singolarmente, si osserva che:
� x resta �ssato a 0;
� y �e scelto non negativo per costruzione;
� s resta non negativo se e solo se 1� y � 0; cio�e se y � 1;
� la non negativit�a di t �e assicurata per qualsiasi valore di y � 0;
� quella di u solo per y � 12.
Pertanto, mentre per soddisfare il sistema di equazioni avremmo potutoscegliere y liberamente, per tener conto dei vincoli sul segno siamo costretti alimitare la scelta ai valori 0 � y � 1
2. Poich�e maggiore �e il valore di y, minore
sar�a il valore dell'obiettivo, la scelta pi�u conveniente pare essere y = 12 .
Per costruzione, solo le variabili di base possono assumere valore non nul-lo; pertanto per ottenere una soluzione di base con y = 1
2 dovremo scrivereun dizionario nel quale y compaia fra le variabili di base; ma il numero divariabili nella base �e �ssato e pari ad m, pertanto una variabile che attual-mente fa parte della base dovr�a lasciare il posto ad y. Poich�e si �e sceltodi dare ad y il massimo valore possibile, compatibilmente con i vincoli sulsegno, tale scelta avr�a l'e�etto di rendere nulla una (in genere, almeno una)delle attuali variabili di base. Nel caso in esame, sar�a u ad annullarsi quandoy = 1
2 . Questa variabile �e la candidata naturale per lasciare il posto in basead y. Riscriviamo quindi il dizionario esplicitando le equazioni rispetto alleincognite s; t; y: dalla terza equazione ricaviamo y = 1
2 +x�u che, sostituita
55
nelle prime due e nell'obiettivo, porta al dizionario seguente:
z = �2� 3x+ 4u
s =1
2� 2x+ u
t = 1 + x� 2u
y =1
2+ x� u:
Si noti che in questo dizionario si sono tralasciate sia l'indicazione delladirezione dell'ottimizzazione (min) che i vincoli di non negativit�a su tutte levariabili: adottando la convenzione di associare un dizionario solo a problemidi programmazione lineare standard, sar�a sempre sottinteso che i problemisaranno di minimo e con tutte le variabili non negative.
Il dizionario appena ricavato �e, naturalmente, una rappresentazione esat-tamente equivalente alla precedente, ottenuta con operazioni standard di tra-sformazione di sistemi lineari (si tratta del metodo di eliminazione di Gauss).Tuttavia questa rappresentazione permette una lettura pi�u agevole ed indicala strada verso la soluzione ottimale. In particolare, questo dizionario �e as-sociato ad una nuova soluzione di base, facilmente leggibile ponendo ugualia zero le variabili fuori base, corrispondente ai valori
x = 0; y =1
2; s =
1
2; t = 1; u = 0
e caratterizzata da un costo z = �2 (leggibile anche direttamente dalla primaequazione, ponendo x = u = 0).
I coe�cienti delle variabili non di base nell'espressione dell'obiettivo sidicono coe�cienti di costo ridotto o anche prezzi ombra. Come gi�a vistoprecedentemente, il segno dei coe�cienti di costo ridotto �e particolarmen-te utile nella determinazione della variabile entrante in base, cio�e di quellavariabile, attualmente fuori base { e quindi a valore nullo nella soluzione dibase corrente { che conviene rendere positiva. Si vede immediatamente checoe�cienti di costo ridotto positivi corrispondono a variabili il cui ingresso inbase porterebbe tendenzialmente ad un peggioramento del costo; le variabiliche possono entrare a far parte della base con pro�tto (cio�e con diminuzionetendenziale del costo) sono quelle alle quali �e associato un coe�ciente di costoridotto negativo. Quelle con coe�ciente di costo ridotto 0 non comportanoalcuna variazione nell'obiettivo. Queste considerazioni hanno solo valore lo-cale, nel senso che una variabile con coe�ciente di costo ridotto positivo ad
56
un'iterazione, e quindi non conveniente rispetto alla base corrente, potrebberisultare conveniente in un'iterazione successiva.
Nell'esempio, il coe�ciente di costo ridotto di x �e pari a �3: ci�o signi�cache per ogni unit�a di incremento assegnato ad x il costo diminuir�a di 3 unit�a.Il coe�ciente di costo ridotto di u �e invece positivo, pari a 4: un eventualeinnalzamento del livello di u provocherebbe un aumento del costo. Si notiche la positivit�a del coe�ciente di costo ridotto della variabile appena uscitadi base non �e casuale, ma �e conseguenza del fatto che un eventuale ingressoin base di u riporterebbe il dizionario ad assumere la forma iniziale, conconseguente aumento del costo.
Ripetendo il ragionamento svolto in precedenza, analizziamo l'e�etto cheun innalzamento del livello di x potrebbe avere sui vincoli di segno: dallaprima equazione otteniamo che la condizione di non negativit�a di s �e x � 1
4;
dalla seconda non abbiamo vincoli (un incremento di x non pu�o renderenegativa t) e cos�� pure dalla terza. Quindi la scelta sar�a quella di far entrarex in base a livello 1
4, facendo uscire nel frattempo la variabile s (divenuta
pari a 0).Ricavando x dalla prima equazione e sostituendola nelle rimanenti, si
ottiene
z = �11
4+3
2s+
5
2u
x =1
4�
1
2s+
1
2u
t =5
4�
1
2s�
3
2u
y =3
4�
1
2s�
1
2u:
Questo dizionario corrisponde ad una base costituita da x; y; t e rappre-senta una soluzione di base con
x =1
4; y =
3
4; s = 0; t =
5
4; u = 0
e costo pari a �11=4. In teoria si potrebbero scrivere dizionari diversi; tutta-via si pu�o osservare che i coe�cienti di costo ridotto di entrambe le variabilinon di base sono positivi (basterebbe in realt�a che fossero non negativi).Poich�e le soluzioni ammissibili sono un sottoinsieme delle soluzioni ottenuteassegnando valore arbitrario, ma non negativo, alle due variabili fuori base
57
(t; y), dall'espressione z = �114+ 3
2s + 5
2u si deduce che nessuna soluzione
ammissibile pu�o avere obiettivo inferiore a �11=4. Pertanto la soluzione dibase corrente �e ottimale: abbiamo risolto il problema dato.
Vale la pena di sottolineare quanto appena visto:
Teorema 5.1 Se ad una soluzione ammissibile di base sono associati coe�-cienti di costo ridotto non negativi, tale soluzione �e ottimale.
5.2 Presentazione dell'algoritmo del simples-
so mediante dizionario.
Lo schema computazionale visto nel paragrafo precedente pu�o essere facil-mente generalizzato a problemi generici di programmazione lineare. Occorrericordare per�o che nell'esempio visto sono state introdotte varie ipotesi sem-pli�catrici e che nulla �e stato detto circa la teoria del metodo. Inoltre i codicidi calcolo disponibili in commercio non utilizzano la forma del \dizionario",ma usano ra�namenti del metodo e strutture dati particolari sia per evitarei problemi derivanti dagli errori di arrotondamento, sia per poter gestire inmodo e�ciente problemi di grande dimensione { si pensi che attualmente �epossibile risolvere, con macchine di normali capacit�a di calcolo, problemi conmigliaia di incognite e vincoli e che, su macchine potenti, si arriva anche aproblemi con milioni di variabili e centinaia di migliaia di vincoli.
Ricordiamo innanzitutto lo sviluppo del metodo cos�� come esempli�catonel precedente paragrafo. Si �e ipotizzato di avere un dizionario iniziale { che,nell'esempio, era costituito dalle variabili di slack, ma, in genere, pu�o essere
58
composto da m variabili qualsiasi, purch�e formino una base { nella forma:
z = �z +nX
j=m+1
cjxj
x1 = b1 +nX
j=m+1
a1jxj
x2 = b2 +
nXj=m+1
a2jxj
...
xm = bm +
nXj=m+1
amjxj
dove b1; : : : ; bm sono costanti non negative { l'ipotesi di non negativit�a �elegata alla necessit�a di avere una base iniziale ammissibile.
Si tratta quindi di un problema con n incognite, m vincoli di eguaglianza,il vincolo di non negativit�a (sottointeso per tutte le incognite), un obiettivo zda minimizzare. I coe�cienti cj nell'equazione dell'obiettivo sono i coe�cientidi costo ridotto; la base �e formata dalle incognite x1; : : : ; xm, mentre fuoribase abbiamo le incognite xm+1; : : : ; xn.
Se tutti i coe�cienti di costo ridotto sono non negativi, allora questa base�e ottimale e la soluzione ottimale del problema �e data da
x1 = b1; x2 = b2; : : : ; xm = bm; xm+1; : : : ; xn = 0
con costo pari a �z.Altrimenti certamente esister�a almeno un coe�ciente di costo ridotto
strettamente minore di 0. Sia �| l'indice di un simile coe�ciente: c�| < 0.L'incognita (fuori base) x�| �e \competitiva" rispetto a quelle attualmente inbase: un suo eventuale ingresso in base, ad un livello strettamente positi-vo, porterebbe ad un miglioramento del costo; in particolare, per ogni unit�adi x�| in base si avrebbe una variazione pari a c�| del costo. Per capire se �epossibile fare entrare in base tale variabile e, in caso a�ermativo, poter co-struire il nuovo dizionario, occorre considerare i vincoli ed analizzare l'e�ettoche l'eventuale ingresso di tale variabile in base avrebbe sul segno delle altreincognite.
59
Consideriamo una generica equazione del dizionario, evidenziando il ter-mine contenente la variabile x��:
xk = bk + ak��x�� + � � �
(non sono stati scritti esplicitamente gli altri addendi in quanto, nel corsodelle operazioni di pivot, le variabili non di base con indice diverso da ��restano �ssate a 0).
Si vede che se ak�| � 0, all'aumentare di x�| anche xk non diminuir�a,mantenendo quindi la positivit�a { si ricordi che si �e supposto che bk � 0.Se al contrario il segno del coe�ciente della variabile entrante in base fossenegativo, allora per non violare il vincolo sul segno di xk si dovrebbe scegliere
x�| � �bkak�|
(che �e una quantit�a non negativa). Analizzando la situazione di tutte leequazioni del dizionario, si dovr�a scegliere x�| in modo tale da rispettare lapi�u restrittiva di tutte le condizioni, cio�e
x�| � �bkak�|
8 k : ak�| < 0
da cui si ottiene
x�| � mink
��
bkak�|
: ak�| < 0
�:
Per quanto gi�a visto, poich�e tanto maggiore �e il valore della variabile entrantein base, tanto maggiore sar�a la diminuzione del costo, si sceglier�a
x�| = mink
��
bkak�|
: ak�| < 0
�:
Questa scelta provoca l'azzeramento di almeno una tra le variabili dibase. Sia �k l'indice di tale variabile: sar�a questa la variabile uscente di base.L'operazione di pivot pu�o essere ora e�ettuata \risolvendo" l'equazione che,nel dizionario, corrisponde alla de�nizione di x�k, rispetto a x�| e sostituendoogni occorrenza di x�| nelle altre equazioni e nell'espressione dell'obiettivo.
60
Capitolo 6
Cenni sull'interpretazione
geometrica della
programmazione lineare
In questo capitolo verranno fornite alcune de�nizioni e propriet�a elementarirelative alla geometria della PL. Le considerazioni geometriche che verrannopresentata in questo capitolo saranno di tipo elementare e saranno orientateal miglioramento della comprensione di alcuni aspetti della programmazionelineare e del funzionamento del metodo del simplesso. L'argomento, trattatoin modo rigoroso, richiederebbe una trattazione ben pi�u estesa; si �e ritenutoqui di fornire solo alcune nozioni elementari per facilitare la comprensione dialcuni aspetti della programmazione lineare, rimandando a testi specializzatiper approfondimenti e per estensioni.
Si consideri lo spazio vettoriale n�dimensionale Rn;
De�nizione 7 Un sottoinsieme S � Rn chiuso rispetto alla somma vetto-riale ed al prodotto scalare si dice sottospazio di Rn.
Ogni sottospazio S di Rn pu�o essere rappresentato come l'insieme deipunti dello spazio che soddisfano ad un sistema di equazioni lineari omogenee,cio�e
S = fx 2 Rn : Ax = 0g
dove A �e una matrice (m;n); senza perdere di generalit�a, si supporr�a chem � n.
61
De�nizione 8 La dimensione di un sottospazio S, �e il massimo numero divettori linearmente indipendenti contenuti in S.
Esempio 6.1 In R3 l'insieme
S = f(x; y; z) : x+ y + z = 0g
rappresenta un sottospazio (con m = 1; n = 3). E' facile vedere che i vettorilinearmente indipendenti
v1 =�1 �1 0
�; v21 =
�1 0 �1
�appartengono ad S; quindi la dimensione di questo sottospazio �e almeno 2.Si pu�o anche dimostrare che non �e possibile trovare tre vettori indipendentiin S.
Vale una propriet�a che rende pi�u semplice il calcolo della dimensione diun sottospazio.
Teorema 6.1 La dimensione di un sottospazio S = fx 2 Rn : Ax = 0g �epari a
n� rango(A)
Nell'esempio precedente, il rango della matrice dei coe�cienti
A =�1 1 1
��e pari ad 1 e, pertanto, la dimensione di S �e 2.
De�nizione 9 Un sottospazio a�ne �e un sottoinsieme di Rn ottenuto tra-slando un sottospazio.
Equivalentemente un sottospazio a�ne �e rappresentabile come un sot-toinsieme S di Rn che soddisfa un sistema di equazioni lineari (non necessa-riamente omogenee):
S = fx 2 Rn : Ax = bg:
La dimensione di un sottospazio a�ne �e quella del sottospazio corrispon-dente (cio�e quella del sottospazio ottenuto ponendo b = 0).
62
De�nizione 10 La dimensione di un qualunque insieme E � Rn �e la mini-ma dimensione di un sottospazio a�ne che contenga E.
Ad esempio, un insieme costituito da due punti distinti in Rn, con n � 1,ha dimensione 1, come pure ha dimensione 1 un segmento; un cerchio conraggio strettamente positivo ha dimensione 2, e cos�i via.
L'insieme ammissibile di un problema di PL
Ax = b
x � 0
�e un sottoinsieme dello spazio a�ne fx : Ax = bg e pertanto avr�a dimensionenon superiore a n� rango(A).
Sia � 2 Rn un vettore non nullo e � un numero reale.
De�nizione 11 Si de�nisce iperpiano il sottospazio a�ne di dimensionen� 1:
H =�x 2 Rn : �Tx = �
Il vettore � si dice normale ad H. Un iperpiano suddivide lo spazio in
due regioni convesse dette semispazi a�ni la cui espressione analitica �e:
H� = fx 2 Rn : �Tx � �g
H� = fx 2 Rn : �Tx � �g:
Si pu�o vedere facilmente che l'orientamento del vettore � �e verso l'internodel semispazio a�ne H�. Un sistema di disequazioni lineari
Ax � b
rappresenta quindi l'intersezione di un numero �nito di semispazi.
De�nizione 12 L'intersezione di un numero �nito di semispazi a�ni �e una�gura convessa detta poliedro.
Si ricorda che un insieme convesso �e caratterizzato dal fatto che dati duesuoi punti qualsiasi il segmento che li unisce �e tutto contenuto nell'insiemestesso. I semispazi a�ni, gli iperpiani ed i poliedri sopra de�niti sono insiemiconvessi. Poich�e come si �e visto nei capitoli precedenti, un qualunque sistemadi equazioni e disequazioni lineari pu�o essere ricondotto ad un sistema di di-sequazioni lineari, segue che l'insieme ammissibile di un qualunque problemadi PL �e un poliedro ed �e, pertanto, un insieme convesso.
63
De�nizione 13 Un poliedro limitato e non vuoto �e detto politopo.
Esempio 6.2 Si consideri l'insieme ammissibile del seguente problema diPL in R2:
�x+ y � 0
x+ y � 1
x+ 2y � 6
y � 4
x � 2
x � 0
y � 0:
Questo insieme �e un politopo che pu�o essere rappresentato gra�camente comein �gura 6.1.
-1 0 1 2 3 4 5-1
0
1
2
3
4
5
AB
C
D
O
Figura 6.1: Un esempio di politopo
Come si pu�o vedere dal gra�co alcuni vincoli possono risultare ridondan-ti: nell'esempio la regione ammissibile non cambierebbe se si eliminassero ivincoli y � 0; y � 4; x � 2.
Si consideri ora un poliedro P di dimensione d;
64
De�nizione 14 Una disequazione �Tx � � si dice valida per P se
P ��x 2 Rn : �Tx � �
:
De�nizione 15 Data una disequazione
�Tx � �
valida per P , l'iperpiano
H =�x 2 Rn : �Tx = �
si dice iperpiano di supporto per P se e solo se
P \H 6= ;:
L'insieme
P \H
si chiama faccia del poliedro.
I vincoli che de�niscono un generico poliedro sono ovviamente disegua-glianze valide. Se con aTi e bi si indicano rispettivamente i coe�cienti dell'i�esimovincolo ed il corrispondente termine noto, si ha che l'intersezione di ogniiperpiano della forma
aTi x = bi
con il poliedro P , se non vuota, costituisce una faccia; inoltre l'intersezionedi pi�u facce di P �e una faccia.
Una faccia di dimensione zero (cio�e un punto) si dice vertice mentre unafaccia di dimensione 1 si dice spigolo .
Una faccia di dimensione n� 1 �e detta faccetta oppure faccia massimale
Esempio 6.3 Con riferimento al precedente esempio 6.2, si osservi che isegmenti AB;BC;CD;DA sono spigoli (e anche facce massimali) del polie-dro i cui vertici sono A;B;C;D. In particolare lo spigolo AB pu�o esseregenerato dalla disequazione valida
x+ y � 1:
65
Infatti la retta x + y = 1 interseca il poliedro lungo lo spigolo AB. L'in-tersezione fra la faccia AB e la faccia AD corrisponde al vertice A. Talevertice �e una faccia di dimensione 0; pu�o ad esempio essere generato dalladisequazione valida
2y � 1
La retta 2y = 1 �e di supporto al poliedro, e la sua intersezione con il poliedro�e il vertice A. Il vincolo y � 4 �e naturalmente una disequazione valida, mala retta y = 4 non interseca il poliedro: non costituisce pertanto un supportoe non de�nisce una faccia.
Un punto x di un insieme convesso C si dice estremo se non �e rappresen-tabile come combinazione convessa in senso stretto di alcuna coppia di puntidistinti di C. In altri termini, x �e un estremo di C se e solo se
@ y; z 2 C; y 6= z :
x = �y + (1 � �)z;� 2 (0; 1)
Per i poliedri, che sono insiemi convessi particolari, �e possibile ottenereuna caratterizzazione pi�u precisa dei punti estremi. Dato un poliedro P =fAx � bg ed un punto �x, si indichi con I=(�x) l'insieme degli indici dei vincolidi P attivi in �x, cio�e sia
aTi �x = bi 8i 2 I=(�x)
aTi �x < bi 8i =2 I=(�x)
Sia A= la sottomatrice di A costituita dalle righe il cui indice sia in I=(�x) eanalogamente si de�nisca b=; sia quindi A=�x = b=. Vale il seguente
Teorema 6.2 Un punto �x appartenente ad un poliedro P = fx 2 Rn : Ax �bg �e un estremo per P se e solo se rango(A=) = n.
Dimostrazione. Sia �x un estremo di P e si supponga per assurdo cherango(A=) < n; allora il sistema di equazioni
A=x = 0
ammette almeno una soluzione y 6= 0. I vettori
z = �x+ �y
w = �x� �y
66
sono tali che, per qualsiasi valore di �, A=z = b= e A=w = b=. Inoltre, poich�eper i vincoli con indice i =2 I(�x) vale
aTi �x < bi
e poich�e tali vincoli sono in numero �nito, esister�a una perturbazione �su�cientemente piccola ma strettamente positiva tale che
aTi z = aTi �x+ �y � bi
aTi w = aTi �x+ �w � bi
per i =2 I(�x). Ne segue che z e w appartengono al poliedro P . Per�o vale
�x =1
2z +
1
2w
che �e assurdo, essendo �x un punto estremo.Per dimostrare il viceversa, si supponga che rango(A=) = n e che, per assur-do, �x non sia un punto estremo per P . Devono quindi esistere due punti z ew, con z 6= w, in P ed un numero reale � 2 (0; 1) tali che
�x = �z + (1� �)w:
Si consideri ora il sistema A=x = b=; sostituendo si ha che
�A=z + (1 � �)A=w = b=:
Pertanto deve essere
A=z = b=
A=w = b=
poich�e, se per una delle due soluzioni valesse il vincolo con il segno di < l'altrarisulterebbe non ammissibile. Si �e giunti all'assurdo, poich�e in questo caso ilsistema di equazioni A=x = b= avrebbe pi�u di una soluzione, contraddicendol'ipotesi rango(A=) = n.
Esistono poliedri privi di punti estremi: ogni poliedro fAx � bg con Amatrice di rango minore di n non pu�o avere punti estremi.
Esempio 6.4 Il poliedro
f(x; y) 2 R2 : x+ y � 1g
�e privo di punti estremi.
67
Teorema 6.3 In un poliedro P vertici e punti estremi coincidono.
Dimostrazione. Sia �x un vertice di P = fAx � bg; se �x non fosse unestremo, dovrebbero esistere due elementi z;w 2 P tali che
�x = �z + (1� �)w
con � 2 (0; 1). Essendo �x un vertice, deve esistere un iperpiano di supporto
H = fx : �Tx = �g
tale che
P � f�Tx � �g
e
H \ P = �x:
Poich�e z e w sono in P deve valere �T z < � e �Tw < � (la diseguaglianzadeve essere stretta poich�e �x �e l'unico punto di P che appartiene ad H). Maquesto �e assurdo perch�e, se fosse vero, si avrebbe
�T �x = ��T z + (1 � �)�Tw < �:
Viceversa, se �x �e un punto estremo, vale
A=�x = b=
con A= matrice di rango n. L'iperpiano
H = fx 2 Rn : �Tx = �g
con � = 1TA= e � = 1T b= �e di supporto per P . Infatti per ogni punto x 2 Pvale Ax � b e, conseguentemente,
1TA=x � 1Tb=:
L'iperpiano H �e quindi di supporto per P e vale �x 2 H \ P ; resta da dimo-strare che �x �e l'unico punto in H \P . Se y 2 H \ P deve valere A=y � b= e�Ty = �; queste relazioni sono equivalenti a
bi � aTi y � 0 8i 2 I(�x)Xi2I(�x)
(bi � aTi y) = 0;
68
ma la somma di quantit�a non negative pu�o essere nulla solo se ciascunaddendo �e pari a 0. Pertanto vale
A=y = b:
Questo �e assurdo, poich�e �x �e l'unica soluzione del sistema A=x = b.Per i poliedri si possono quindi usare indi�erentemente i termini di vertice
e di punto estremo. I vertici hanno anche una corrispondenza con le soluzioniammissibili di base dei problemi di PL. Vale infatti:
Teorema 6.4 Ogni soluzione ammissibile di base di un problema di PLstandard
min cTx
Ax = b
x � 0
�e un vertice del poliedro
P = fx 2 Rn : Ax = b; x � 0g:
Dimostrazione. Una soluzione di base ammissibile �e soluzione unica diun sistema
ABx = b
con A matrice (m;m). Almeno n �m componenti di una soluzione di basesono nulle e, pertanto, almeno n �m vincoli x � 0 sono attivi in corrispon-denza della soluzione di base. Si pu�o quindi determinare la soluzione di basecome unica soluzione di un sistema di n equazioni�
AB 00 I
�x =
�b0
�:
Si �e quindi dimostrato che la soluzione di base corrisponde ad un vertice diP , in base al teorema 6.2.
Il teorema appena dimostrato a�erma che ad ogni soluzione di base cor-risponde un vertice del poliedro P ; non �e detto per�o che a soluzioni associatea basi di�erenti corrispondano vertici di�erenti: pi�u soluzioni di base potreb-bero essere rappresentate come un unico vertice. Questo avviene nel caso disoluzioni di base degeneri.
69
6.1 Soluzione gra�ca di problemi di PL
I problemi di PL in R2 o in R3 possono essere rappresentati e risolti pervia gra�ca. Naturalmente la risoluzione gra�ca di tali problemi ha esclusiva-mente interesse didattico e nessuna reale utilit�a pratica. Per poter risolvereper via gra�ca un problema di PL in R2 si pu�o iniziare dalla rappresentazio-ne gra�ca dell'insieme ammissibile; successivamente si possono aggiungere algra�co alcune curve di livello della funzione obiettivo. Per i problemi di PLla funzione obiettivo ha curve di livello esprimibili come
H` = fx 2 Rn : cTx = `g:
Tali curve sono quindi iperpiani, tutti paralleli fra loro, aventi il vettore deicosti c come normale. Si ricorda che il vettore normale c �e orientato nelladirezione del semispazio cTx � `, cio�e in direzione crescente della funzio-ne obiettivo. Per risolvere gra�camente un problema di PL si pu�o quindirappresentare il vettore dei costi c e disegnare una retta che abbia c comenormale. Facendo \scivolare" tale retta parallelamente a se stessa �no adincontrare l'ultimo punto di P in direzione opposta a quella indicata da c siottiene l'ottimo del problema di PL.
Esempio 6.5 Si consideri il problema
min�x�1
2y
�x+ y � 0
x+ y � 1
x+ 2y � 6
y � 4
x � 2
x; y � 0
che ammette la seguente rappresentazione gra�ca:Nel disegno sono rappre-sentate, a titolo di esempio, le curve di livello a livello 0;�1;�2;�3. Si vedecome la curva a livello �3 sia quella di livello minimo tra quelle che interse-cano P . Si deduce quindi che il punto D �e la soluzione ottimale del problemadi PL dato.
70
-1 0 1 2 3 4 5-1
0
1
2
3
4
5
AB
C
D
Oc
Figura 6.2: Risoluzione geometrica
Esempio 6.6 Se nell'esempio precedente l'obiettivo fosse stato
min�1
2x� y
la rappresentazione geometrica sarebbe stata quella indicata in �gura: Inquesto caso la linea di livello minima interseca il poliedro P lungo uno spigolo,CD: esistono pertanto in�nite soluzioni ottimali, due delle quali, C e Dcorrispondenti a vertici e, quindi, a soluzioni di base. Le soluzioni lungo ilsegmento aperto (C;D) sono ottimali, ma non di base. Si pu�o anche veri�careche il vertice C �e in corrispondenza con un'unica soluzione di base, mentre ilvertice D corrisponde a soluziono ottimali di base associate a basi di�erenti.
Esempio 6.7 Si consideri il problema
min�x�1
2y
�x+ y � 0
x+ y � 1
x; y � 0
rappresentato nella �gura seguente: Questo problema �e illimitato inferior-mente, come si pu�o anche vedere dal fatto che le curve di livello normali al
71
-1 0 1 2 3 4 5-1
0
1
2
3
4
5
AB
C
D
O
c
Figura 6.3: Risoluzione geometrica: in�nite soluzioni ottimali
vettore dei costi c =��1 1
2
�Tintersecano la regione ammissibile a livelli
piccoli a piacere. Se nello stesso problema l'obiettivo fosse
max�x�1
2y
la soluzione ottimale sarebbe il vertice B.
72
-1 0 1 2 3 4 5-1
0
1
2
3
4
5
AB
c
Figura 6.4: Risoluzione geometrica: problema illimitato
73
Capitolo 7
Formulazione matriciale del
metodo del simplesso
Il metodo del simplesso costituisce uno dei pi�u di�usi ed e�cienti algorit-mi per la risoluzione di problemi di PL anche di notevoli dimensioni. Inquesto paragrafo verr�a analizzato l'algoritmo nella cosiddetta formulazionematriciale.
Il criterio di base dell'algoritmo consiste nell'analizzare i vertici della re-gione ammissibile (cio�e le soluzioni ammissibili di base) procedendo da unvertice ad un vertice adiacente caratterizzato da un valore della funzioneobiettivo non superiore a quello del vertice di partenza.
La struttura dell'algoritmo pu�o essere scomposta in modo naturale nelleseguenti fasi:
1. scelta di una soluzione ammissibile di base iniziale;
2. controllo di ottimalit�a della soluzione di base corrente;
3. scelta di una nuova soluzione di base.
Il primo punto, cio�e la determinazione di una soluzione ammissibile dibase con cui iniziare l'algoritmo, viene per il momento lasciato in sospeso everr�a trattato solo come ultimo punto, nel paragrafo 7.1: per determinareuna soluzione ammissibile di base con cui iniziare il metodo del simplesso, oc-correr�a eseguire il metodo del simplesso stesso su un problema ausiliario, conuna tecnica che, in altri contesti, viene detta di bootstrap. Per ora quindi si
74
supporr�a di conoscere una base AB ammissibile e la corrispondente soluzioneammissibile di base �x per il problema di PL in forma standard
min cTx
Ax = b
x � 0:
Si supporr�a, al solito, che A sia una matrice m � n di rango m, conm < n. Si ricorda che una sottomatrice AB di A di dimensioni m � mcostituisce una base ammissibile per il problema se e solo se AB �e invertibilee �xB = A�1B b � 0.
7.0.1 Ottimalit�a di una soluzione ammissibile di base
Per comodit�a di notazione, ma ovviamente senza che ci�o sia in pratica neces-sario, si supporr�a che le colonne della matrice dei coe�cientiA, le componentidel vettore dei costi c, quelle della generica soluzione x e quelle della soluzio-ne particolare �x siano state permutate in modo tale che le prime m colonnecorrispondano alla base AB, cio�e:
A =�AB AN
�x =
�xBxN
�
�x =
��xB0
�
dove AB �e una matrice m � m invertibile, AN �e una matrice m � n � m e�xB = A�1B b.
Nel punto �x la funzione obiettivo ha valore �z = cT �x, che �e esprimibileanche come
�z =�cTB cTN
� � �xB0
�= cTB�xB
A�nch�e la soluzione �x sia ottimale, non deve esistere alcuna altra solu-zione ammissibile con valore funzionale strettamente minore di cTB�xB. Ognisoluzione ammissibile deve soddisfare al sistema di equazioni
Ax = b
75
che, espresso in funzione della base corrente B, si pu�o scrivere come
ABxB +ANxN = b
cio�e
xB = A�1B b�A�1B ANxN
= �xB �A�1B ANxN
e, in corrispondenza di una generica soluzione x, la funzione obiettivo havalore
cTx = cTBxB + cTNxN (7.1)
= cTBA�1B b+ (cTN � cTBA
�1B AN)xN
= cT �x+ cTNxN : (7.2)
Gli elementi del vettore
cTN = cTN � cTBA�1B AN
sono i
coe�cienti di costo ridotto.
Si ha quindi:
z = cT �x+ cTNxN
xB = �xB �A�1B ANxN
e si vede facilmente che la rappresentazione matriciale non �e altro che ildizionario del metodo del simplesso visto in precedenza.
Poich�e ogni soluzione ammissibile deve soddisfare la condizione xN � 0,�e evidente che la soluzione di base corrente �x sar�a ottimale se nessuno deicoe�cienti di xN �e negativo. Si �e quindi dimostrato, utilizzando la formamatriciale, il criterio su�ciente di ottimalit�a gi�a presentato nel teorema 5.1.
Esempio 7.1 Si consideri il problema di PL seguente:
min�2 �1 3 1 0 0
�x�
1 1 �2 1 1 02 �1 1 1 0 1
�x =
�12
�x � 0
76
La soluzione corrispondente alla base A5;6 �e data da
�x5;6 = A�15;6b =
�1 00 1
��1 �12
�=
�12
�
ed �e caratterizzata da un costo pari a 0 e da coe�cienti di costo ridotto
cT1;2;3;4 = cT1;2;3;4� cT5;6A�15;6A1;2;3;4
=�2 �1 3 1
���0 0
� � 1 00 1
��1 �1 1 �2 12 �1 1 1
�=�2 �1 3 1
�:
Tale soluzione ammissibile di base non soddisfa la condizione su�ciente diottimalit�a, essendo il coe�ciente di costo ridotto della variabile x2 negativo.Si pu�o cercare di costruire qualche soluzione di base nella quale la variabilex2 sia di base. Ad esempio, considerando la base A1;2 si ottiene
�x1;2 =
�1 12 �1
��1 �12
�=
�10
�
alla quale sono associati i coe�cienti di costo ridotto
cT3;4;5;6 =�3 1 0 0
���2 �1
� � 1 12 �1
��1 ��2 1 1 01 1 0 1
�=�2 0 0 �1
�che ancora non soddisfa la condizione su�ciente di ottimalit�a. Questa solu-zione di base ha costo pari a 2, ed �e degenere. Provando a costruire una basecomprendente sia la variabile x2 che la variabile x6, si ottiene la soluzione dibase
�x2;6 =
�1 0
�1 1
��1 �12
�=
�13
�
alla quale sono associati i coe�cienti di costo ridotto
cT1;3;4;5 =�2 3 1 0
����1 0
� � 1 0�1 1
��1 �1 �2 1 12 1 1 0
�=�3 1 2 1
�:
77
Questa soluzione ammissibile di base soddisfa il criterio su�ciente di ot-timalit�a; si pu�o pertanto a�ermare che, nel problema in esame, una soluzioneottimale �e costituita dal vettore
�x =
26666664
010003
37777775
ed il costo ottimale �e pari a �1.
E' importante ricordare che la condizione di ottimalit�a �e su�ciente, manon necessaria.
Esempio 7.2 Si consideri un problema ottenuto dal precedente tramite unavariazione del termine noto:
min�2 �1 3 1 0 0
�x�
1 1 �2 1 1 02 �1 1 1 0 1
�x =
�01
�x � 0;
se si considera di nuovo la soluzione di base associata ad A2;6, si ottiene
�x2;6 =
�1 0
�1 1
��1 �01
�=
�01
�
e i coe�cienti di costo ridotto risultano, come nell'esempio precedente, paria
cT1;3;4;5 =�3 1 2 1
�:
Il costo della soluzione ottimale �e quindi pari a 0. Se ora si riprende inconsiderazione la prima soluzione ammissibile di base individuata nel prece-dente esempio, e cio�e quella associata alla base A5;6, si vede immediatamenteche tale soluzione di base �e ammissibile:
�x5;6 = A�15;6b =
�1 00 1
��1 �01
�=
�01
�
78
e, poich�e la formula dei coe�cienti di costo ridotto non dipende dal terminenoto b, ma solo dal vettore dei costi e dalla ripartizione della matrice deicoe�cienti in matrice di base e non, i coe�cienti di costo ridotto sarannoidentici a quelli gi�a calcolati:
cT1;2;3;4 =�2 �1 3 1
�:
Questa soluzione di base quindi non soddisfa la condizione su�ciente diottimalit�a; tuttavia, valutando il costo associato a questa soluzione di base,che �e pari a 0, ci si accorge che essa ha lo stesso costo della soluzione ottimaleed �e, pertanto, ottimale. Tra l'altro, si pu�o vedere immediatamente che inrealt�a non si tratta di una diversa soluzione ottimale, ma sempre della stessa,sebbene ottenuta tramite una diversa rappresentazione della base. Si noti chein questo caso la soluzione ottimale di base �e degenere.
La presenza in un problema di PL, di soluzioni ottimali con alcuni coe�-cienti di costo ridotto negativi non �e assolutamente rara { anzi, nei problemiincontrati nella pratica, si pu�o dire che costituisca la norma, non l'eccezione.Tuttavia, pi�u avanti si dimostreranno le seguenti fondamentali propriet�a:
Teorema 7.1 Se in un problema di PL tutte le soluzioni di base ottimalisono non degeneri, allora ogni soluzione ottimale di base avr�a coe�cienti dicosto ridotto non negativi. La condizione di non negativit�a dei coe�cienti dicosto ridotto �e, in questo caso, necessaria e su�ciente per l'ottimalit�a.
Teorema 7.2 In ogni problema di PL che ammette almeno una soluzioneottimale di base, esiste almeno una base ottimale alla quale sono associaticoe�cienti di costo ridotto tutti non negativi.
In base a queste propriet�a e, in particolare, all'ultima, si pu�o pensare di co-struire un algoritmo che utilizzi la condizione di non negativit�a dei coe�cientidi costo ridotto come regola d'arresto. Naturalmente se si potesse riconoscerel'ottimalit�a di una soluzione di base anche in presenza di coe�cienti di costoridotto negativi, la velocit�a di esecuzione dell'algoritmo sarebbe maggiore;in certi casi questo �e possibile: a volte, ad esempio, �e noto a priori il valoredell'ottimo, ma non l'ottimo stesso. In questi casi si pu�o arrestare l'algoritmoappena si incontra una soluzione ammissibile con costo pari all'ottimo. Pi�uspesso �e nota una limitazione inferiore al valore dell'ottimo: anche in questicasi ci si pu�o arrestare se si incontra una soluzione ammissibile il cui costo �epari a tale limitazione inferiore. In generale tuttavia gli algoritmi del tipo del
79
metodo del simplesso attendono di aver determinato una soluzione di basecon tutti i coe�cienti di costo ridotto non negativi (o di aver dimostrato chetale soluzione non pu�o esistere).
7.0.2 Scelta di una nuova soluzione ammissibile di base
- operazione di pivot
Se, come supporremo in questo capitolo, si dispone di una soluzione ammis-sibile di base con almeno un coe�ciente di costo ridotto negativo, occorreun metodo per modi�care, se possibile, la base corrente in una nuova cuicorrisponda una soluzione \migliore" di quella attuale. Questo criterio sicompone di due fasi: la scelta di una direzione e la successiva scelta di unospostamento lungo tale direzione. In genere si cercher�a di determinare unadirezione ammissibile, che come si �e gi�a visto in precedenza, rappresenta unadirezione lungo la quale sia possibile e�ettuare uno spostamento non nullosenza violare alcun vincolo. Sia
x =
�xB0
�
la soluzione di base corrente. L'obiettivo di questo paragrafo �e la determina-zione di una nuova soluzione ammissibile
~x =
�~xB~xN
�
che sia ancora di base e non peggiore di �x, nel senso che cT ~x � cT �x. Sinoti che la suddivisione di ~x nelle componenti ~xB ed ~xN �e fatta, in questomomento, rispetto agli indici della base B corrispondente ad �x, non agli indicidella nuova base associata ad ~x.
Come si �e visto, per mantenere l'ammissibilit�a, le componenti ~xB e ~xNdella nuova soluzione ~x devono soddisfare le relazioni:
~xB = A�1B b�A�1B AN ~xN
= xB �A�1B AN ~xN
~x � 0
cio�e �xB �A�1B AN ~xN
~xN
�� 0;
80
ovvero �xB0
�+
��A�1B AN
I
�~xN � 0:
La scelta ~xN = 0 corrisponde alla soluzione di base corrente, cio�e a ~x = x.Ricordando che, dalla de�nizione dei coe�cienti di costo ridotto, si ha
cT ~x = cT �x+ cTN ~xN ;
se la soluzione �x non �e ottimale esister�a certamente almeno una componente,ad esempio quella di indice j 2 N , del vettore dei coe�cienti di costo ridottostrettamente negativa, cj < 0. Incrementando (se possibile) la corrisponden-te componente del vettore ~xN , il valore della funzione obiettivo diminuir�a.Indicando con � l'incremento della variabile ~xj, si ha
~x = ~x(�) =
�xB0
�+
��A�1B AN
In�m
�ej�
dove In�m rappresenta una matrice identica di dimensione (n�m)� (n�m)ed ej rappresenta il versore di Rn�m le cui componenti sono tutte nulle adeccezione di quella corrispondente a xj che vale 1. Ponendo
y = �A�1B ANej 2 Rm
si ottiene
~x(�) = �x+
�yej
��:
Per costruzione, qualunque sia il valore di �, il punto ~x(�) �e soluzione delproblema di PL, cio�e soddisfa i vincoli di eguaglianza. Per essere ammissibiledeve inoltre soddisfare la condizione di non negativit�a ~x � 0. Scegliendo� � 0 le componenti di ~xN sono non negative (anzi, ne esiste soltanto una,quella di indice j, che potrebbe divenire strettamente positiva). Per quantoriguarda le componenti di ~xB, si ha invece
~xi = xi + yi� i 2 B (7.3)
Ricordando che si suppone che la soluzione di base corrente sia ammissi-bile, e che pertanto xi sia non negativo, si ha, analizzando i casi possibili:
81
� se yi � 0, per qualunque valore di � la corrispondente variabile ~xi sar�anon negativa;
� se yi < 0, incrementando � la corrispondente componente di xi di-minuisce; per imporre l'ammissibilit�a si deve pertanto richiedere chexi + yi� � 0 e cio�e che
� � �xiyi
8i : yi < 0:
L'ammissibilit�a della nuova soluzione �e quindi garantita per ogni sceltadi � tale da soddisfare
0 � � � �? = mini:yi<0
��xiyi
�: (7.4)
Poich�e maggiore �e il valore di �, maggiore sar�a il decremento nel valoredella funzione obiettivo (si veda la (7.2)), ponendo
� = �?
si ottiene il massimo decremento possibile per la funzione obiettivo lungo ladirezione �
yej
�(7.5)
7.0.3 Problemi illimitati
Esiste un caso in cui non �e possibile determinare �? e cio�e il caso in cui nonesiste nessun indice i 2 B : yi < 0. In questo caso ciascuna componente delvettore
~xi = xi + yi� i 2 B
resta non negativa per qualsiasi scelta di � � 0. Poich�e ad uno spostamento� > 0 corrisponde una variazione della funzione obiettivo pari a cj� < 0, sivede, in questo caso, che il problema risulta illimitato.
82
Esempio 7.3 Si consideri il problema
min�1 0 1 2 �1 �1
�x�
1 0 2 �1 1 �10 1 �1 1 �1 �1
�x =
�12
�x � 0:
Utilizzando come base iniziale la matrice identica A1;2, corrispondente
alla soluzione di base x1;2 =
�12
�, si ha
c3;4;5;6 =�1 2 �1 �1
���1 0
� � 2 �1 1 �1�1 1 �1 �1
�=��1 3 �2 0
�:
Si pu�o scegliere, come variabile entrante, sia x3 che x5. Si vedr�a pi�uavanti che entrambe queste scelte sono corrette. Si scelga, ad esempio, x5.Per la scelta della variabile uscente, si ha
y = �A�11;2A5 =
��11
�:
L'unica possibilit�a per la variabile uscente �e x1. Lo scambio avvienedunque tra x1 e x5; la nuova base diventa
A2;5 =
�0 11 �1
�
e la soluzione di base ad essa associata �e
x2;5 =
�0 11 �1
��1 �12
�=
�31
�:
I coe�cienti di costo ridotto associati a questa base sono
c1;3;4;6 =�1 1 2 �1
���0 �1
� � 0 11 �1
��1 �1 2 �1 �10 �1 1 �1
�=�2 3 1 �2
�
83
La variabile entrante �e quindi x6. Per determinare la variabile uscente, sicerca, al solito, il vettore direzione
y = �A�12;5A6 = �
�0 11 �1
��1 ��1�1
�=
�21
�:
Nessuna delle componenti di y �e negativa. Pertanto il problema �e illimi-tato. Per confermare questo fatto, si osservi che la soluzione di base correntecorrisponde al vettore
�x =
26666664
030010
37777775
e che, attraverso lo spostamento individuato dal vettore y appena calcolato,sono ammissibili tutte le soluzioni
x(�) =
26666664
030010
37777775+
26666664
020011
37777775� =
26666664
03 + 2�00
1 + ��
37777775;
il cui costo �e z(�) = �(1 + �)� � = �1� 2� ! �1 per � ! +1.
La (7.3) fornisce una prova costruttiva dell'illimitatezza del problema e,in alcuni casi, pu�o aiutare a indicarne il motivo; in un problema applicativo,in genere l'illimitatezza �e causata da vincoli troppo deboli o assenti. L'indi-viduazione di una direzione di spostamento illimitata in discesa pu�o aiutarenella scelta di un vincolo da aggiungere al problema in modo da ottenere unottimo �nito.
7.0.4 Determinazione della variabile uscente di base
Se il valore �? cos�� individuato �e strettamente positivo, la (7.4) individua unospostamento non nullo lungo la direzione (7.5). Indicando con i? 2 B un
84
indice in corrispondenza del quale viene raggiunto il minimo nella (7.4), cio�equell'indice (o uno di quegli indici) tale che
�? = �xi?
yi?� �
xiyi
8 i 2 B : yi < 0
cio�e
i? 2 arg mini2B:yi<0
��xiyi
�
si vede immediatamente che la variabile di base xi? assume valore nullo eche, se �? > 0, la variabile di indice j 2 N acquista un valore strettamentepositivo. Si dimostrer�a ora che la matrice ottenuta sostituendo la colonna deicoe�cientiAi? con quella dei coe�cienti di Aj �e ancora una base ammissibile.Si suole dire in questo caso che la variabile di base xi? \esce" dalla base,mentre la variabile xj \entra" nella nuova base. L'operazione consistentenello scambio tra queste due variabili, di cui una in base e l'altra fuori base,si chiama operazione di
pivot
o di \cardine"; tale operazione corrisponde, nell'interpretazione geometricadella PL, ad uno spostamento da un vertice ad un vertice adiacente lungouno spigolo del poliedro. L'operazione di pivot pu�o anche essere e�ettuataqualora si abbia �? = 0 { cosa che pu�o accadere solamente nel caso di basidegeneri { nel qual caso il passo e�ettuato �e nullo. La soluzione di base restainvariata, ma cambia la composizione della matrice di base.
Nello scambio tra il vettore dei coe�cienti di xi? (variabile uscente di ba-se) e quelli di xj (variabile entrante in base), non si perde l'invertibilit�a dellamatrice AB. Vale infatti un'importante propriet�a generale sulla sostituzionedi vettori in matrici invertibili (cio�e in basi): sia AB = fA1; A2; : : : ; Amg 2Rm�m una base di Rm e sia v 2 Rm un vettore generico. Grazie alla de�ni-zione di base, esiste un'unica combinazione lineare delle colonne di AB chegenera v:
v =mXi=1
Ai�i
dove �i sono coe�cienti opportuni, univocamente determinati. Vale la pro-priet�a seguente:
85
Teorema 7.3 La matrice AB0 = AB n Aj [ v (ottenuta scambiando v conuna colonna Aj di AB) �e ancora una base se e solo se �j 6= 0.
Dimostrazione. La condizione �j 6= 0 �e su�ciente. Infatti, si consideri-no le colonne
AB0 = fA1; A2; : : : ; Aj�1; v;Aj+1; : : : ; Amg
e se ne e�ettui una combinazione lineare con coe�cienti �1; : : : ; �m:Xi6=j
Ai�i + v�j (7.6)
Sfruttando la rappresentazione di v mediante le colonne di AB questa �eequivalente a X
i6=j
Ai�i + �jXi
Ai�i
cio�e a Xi6=j
(�i + �j�i)Ai + �j�jAj
Poich�e AB �e una base l'unica combinazione lineare delle sue colonne cheproduce il vettore nullo �e quella banale. Per annullare la combinazione (7.6)occorre avere
�j�j = 0
�i + �j�i = 0 i = 1; : : : ;m; i 6= j
ed, essendo per ipotesi �j 6= 0, dovr�a essere �j = 0. Ma, essendo �j = 0,dovranno essere nulli anche tutti i coe�cienti �i; i 2 f1; : : : ;mg ; i 6= j.Pertanto l'unica combinazione lineare che annulla le colonne di AB0 �e quellabanale tutta nulla: AB0 �e quindi una base.
La condizione �e anche necessaria. Infatti, se si avesse �j = 0, allora nellarappresentazione di v mediante AB si avrebbe
v =Xi 6=j
Ai�i
86
Quindi v sarebbe dipendente linearmente dai vettori Ai; i 6= j. Non potrebbepertanto formare, con loro, una base.
Questa propriet�a pertanto ci permette di caratterizzare tutti e soli gliscambi possibili tra un vettore in base ed uno esterno alla base stessa. Per po-ter applicare quanto visto all'operazione di scambio nel simplesso, osserviamoche la scelta del vettore uscente di base avviene tramite il criterio
i? 2 arg mini2B:yi<0
��xiyi
�(7.7)
con y = �A�1B Aj, dove j �e l'indice della variabile entrante in base.Il vettore y non �e altro che (a meno di un cambio di segno) il vettore dei
coe�cienti nella rappresentazione di Aj tramite le colonne di AB. Infatti siosservi che X
i2B
Aiyi = ABy = AB(�A�1B Aj) = �Aj:
Il vettore al posto del quale v = Aj viene inserito in base compare esplici-tamente in questa rappresentazione (in base al criterio (7.7) il coe�ciente y?i�e sicuramente non nullo, anzi, strettamente negativo). Quindi l'operazionedi pivot �e valida, nel senso che trasforma basi in basi. In particolare, data lascelta del segno di yi, in realt�a tale operazione trasforma basi ammissibili inbasi ammissibili.
L'operazione di pivot appena descritta viene eseguita in modo tale che lafunzione obiettivo non aumenti; in particolare, se �? > 0, la funzione obiettivonel nuovo vertice avr�a valore strettamente minore di cTB�xB.
Esistono due casi in cui non �e possibile ottenere un valore �? > 0 �nito:
1. yi � 0 8i 2 B: in questo caso la componente di indice j di x pu�oessere incrementata a piacere senza che alcun vincolo sia violato; ci�oimplica che il costo cTx pu�o essere diminuito a piacere incrementandoxj (si veda la (7.2)); pertanto in questo caso si dimostra, come gi�a visto,che il problema di PL �e
illimitato.
2. 9i 2 B : �xi = 0; yi < 0; in questo caso (ovviamente possibile solo inpresenza di una soluzione di base degenere), lo spostamento �? sar�a
87
necessariamente pari a zero; n�e il vettore soluzione �x n�e il valore dellafunzione obiettivo quindi varieranno. Tuttavia sar�a ancora possibilee�ettuare l'operazione di \pivot": in questo caso l'operazione avr�a comee�etto semplicemente quello di cambiare la composizione delle colonneche formano la base AB. Si dice che in questo caso la variabile xj entranella nuova base \a livello zero".
Il trattamento del caso degenere �e particolarmente importante sia dalpunto di vista dell'analisi teorica del metodo del simplesso che dal punto divista della realizzazione di algoritmi e�cienti e delle implementazioni del me-todo stesso: la presenza di soluzioni degeneri, come si �e accennato, potrebbefar ciclare l'algoritmo. Vale un'importante, elementare, propriet�a:
Teorema 7.4 Si consideri una versione deterministica del metodo del sim-plesso, implementato in modo tale che le decisioni relative alle variabili en-tranti ed uscenti di base ad ogni iterazione dipendano esclusivamente dallacomposizione della base corrente. Se tale algoritmo non termina, allora deveciclare all'in�nito.
Dimostrazione. La dimostrazione segue banalmente dal fatto che lebasi di un problema di PL sono in numero �nito; pertanto un metodo delsimplesso che non terminasse dovrebbe visitarne almeno una pi�u volte. Sel'evoluzione del metodo �e completamente determinata dalla base corrente,allora l'algoritmo ripeter�a ciclicamente all'in�nito una stessa sequenza di basi.
La richiesta che il metodo sia deterministico nasce dal fatto che se inqualche fase del metodo, come ad esempio la scelta della variabile entranteo uscente di base, si inserisse una decisione di tipo randomizzato, allorasarebbe possibile il ripetersi non ciclico di un insieme di basi. In ogni caso,deterministico o non, dato l'andamento monotono dei valori delle funzioniobiettivo nelle basi successivamente generate dal metodo, la non terminazione�e possibile esclusivamente nel caso in cui nel problema vi siano delle basidegeneri. Solo in tale caso infatti �e possibile una ripetizione di basi. Valecio�e la seguente propriet�a elementare:
Teorema 7.5 Se nessuna base incontrata nel corso dell'esecuzione del me-todo del simplesso �e degenere, allora il metodo termina in un numero �nitodi iterazioni.
88
Soluzioni di base e vertici degeneri
Si consideri il sistema di equazioni che permette di determinare la soluzionedi base, ABxB = b, equivalente a
Pi2B Aixi = b. Nel caso di una base AB
degenere, se B0 � B �e l'insieme di indici delle componenti non nulle dellasoluzione di base, si vede che il sistema si riduce a AB0xB0 = b. Esistonoin genere diversi insiemi di colonne della matrice A che, accostate ad AB0
formano una base. Si vede quindi che, nel caso degenere, una stessa soluzionedi base pu�o essere ottenuta attraverso basi di�erenti.
Dal punto di vista geometrico, nel caso non degenere una soluzione dibase si trova all'intersezione degli m iperpiani con n � m vincoli del tipoxj = 0 e, pertanto, �e l'unica soluzione di un sistema quadrato di equazionilineari: �
AB AN
0n�m;m In�m
�x =
�b0
�;
dove 0h;k ed Ihrappresentano rispettivamente una matrice nulla h� k ed unamatrice identica h� h.
Nel caso degenere invece la soluzione di base corrente si pu�o ottenerecome soluzione di un sistema non pi�u quadrato; indicando con N 0 l'insiemedelle colonne di A con l'eccezione di B0, si ha�
AB AN
0jN 0j;jB0j IjN 0j
�x =
�b0
�;
il sistema sopra scritto contiene pi�u equazioni che incognite (jm+N 0j > n).Poich�e si sa che il sistema ammette soluzione (la soluzione di base corrente),se ne deduce che almeno una di tali equazioni �e ridondante. Ci�o signi�ca,geometricamente, che il vertice corrispondente alla base si trova all'interse-zione di un numero superiore ad n di iperpiani. Risulta quindi che, per ladeterminazione del vertice in questione, almeno un vincolo �e ridondante. Siosservi che questo non signi�ca che nel problema originale esistono vincolieliminabili. Immaginando ad esempio una piramide a base pentagonale inR3, si vede che un vertice di tale piramide si trova all'intersezione di ben 5piani, mentre tutti gli altri si trovano all'intersezione di 3 piani. Il primovertice �e degenere { le sue coordinate potrebbero essere individuate in modounivoco come intersezione di 3 qualunque (purch�e indipendenti) dei pianiche de�niscono le facce della piramide. Tuttavia nessuna delle 5 facce pu�oessere eliminata senza modi�care la forma dell'insieme. Nel caso di una base
89
degenere �e possibile che un'operazione di pivot avvenga \a livello 0", cio�econ spostamento nullo e senza variazione della funzione obiettivo. In questocaso l'operazione di pivot non porta ad un nuovo vertice, ma semplicementeall'individuazione del vertice corrente mediante l'intersezione di un diversoinsieme di iperpiani di supporto, cio�e di una diversa base.
Esempio 7.4 Si consideri l'esempio 7.1 di pag. 76:
min�2 �1 3 1 0 0
�x�
1 1 �2 1 1 02 �1 1 1 0 1
�x =
�12
�x � 0
Si �e visto che la soluzione
�12
�corrispondente alla base A5;6 �e caratterizzata
da un costo pari a 0 e da coe�cienti di costo ridotto
cT1;2;3;4 =�2 �1 3 1
�
Poich�e il coe�ciente di costo ridotto corrispondente alla seconda variabilenon di base, cio�e alla variabile x2, �e negativo, �e possibile e�ettuare un'opera-zione di pivot per cercare, se possibile, di diminuire il valore della funzioneobiettivo. Per determinare qual �e la variabile uscente dalla base si opera comesegue:
y = �A�1B ANe2
= �
�1 00 1
��1 �1 1 �2 12 �1 1 1
� 26640100
3775
=
��1+1
�
�? = mini2B:yi<0
��xiyi
�= �
1
�1= 1
La variabile uscente di base �e dunque la prima di base, cio�e x5. La nuovabase sar�a quindi B = f2; 6g. La variabile entrante in base (x2) entrer�a a
90
livello �? = 1.Si vede facilmente (riferendosi all'esempio 7.1) che questa soluzione di base�e ottimale.
Esempio 7.5 Riprendendo l'esempio 7.2
min�2 �1 3 1 0 0
�x�
1 1 �2 1 1 02 �1 1 1 0 1
�x =
�01
�x � 0
si considerino la soluzione di base associata a A5;6, con �x5;6 =
�01
�ed i
coe�cienti di costo ridotto cT1;2;3;4 =�2 �1 3 1
�: E' possibile e�ettuare
un'operazione di pivot facendo entrare in base la variabile x2. Per la deter-minazione della variabile uscente, si procede in modo simile a quanto vistonell'esempio precedente:
y = �A�15;6A2
=
��1+1
�
�? = mini2B:yi<0
��xiyi
�= �
0
�1= 0
In questo caso il passo di pivot �e degenere. Tuttavia lo scambio tra lavariabile entrante in base e quella uscente, x5, viene comunque e�ettuato.La nuova base B = f2; 6g, pur corrispondendo alla stessa soluzione (x1 =x2 = x3 = x4 = x5 = 0; x6 = 1), permette di certi�carne l'ottimalit�a, avendotutti i coe�cienti di costo ridotto non negativi.
Scelta della variabile entrante in base
Nel caso in cui pi�u coe�cienti di costo ridotto siano negativi, si pone ilproblema di determinare quale sar�a l'indice del vettore entrante in base.Esistono var� metodi per compiere questa scelta. Sia | l'indice della variabileentrante in base;
91
1. uno dei metodi pi�u semplici, ma relativamente poco utilizzati, �e lascelta casuale dell'indice | nell'insieme N
Tfj : cj < 0g.
2. | = minfj 2 N : cj < 0g, che corrisponde alla scelta del primocoe�ciente di costo ridotto negativo osservato scandendo gli elementidell'insieme N .
3. | 2 argminj2Nfcjg. Questo criterio, consistente nella scelta della va-riabile cui �e associato il coe�ciente di costo ridotto minimo, �e utilizzatoin molte implementazioni. Il criterio �e anche noto con il nome di \me-todo del gradiente nello spazio delle variabili non di base", in quanto,osservando la (7.2), si vede come il gradiente della funzione obiettivorispetto alle variabili non di base sia proprio il vettore c; un incrementodella componente della soluzione cui �e associato il coe�ciente di costoridotto minimo equivale quindi alla scelta della direzione di pi�u ripidadiscesa, tra le direzioni del tipo (7.5), della funzione obiettivo rappre-sentata in funzione delle variabili con indice in N . Si noti tuttavia cheil solo fatto di \scendere" lungo la direzione pi�u ripida non �e garanziadi e�cienza, in quanto il decremento e�ettivo della funzione obiettivo�e funzione non solo della direzione, ma anche dello spostamento possi-bile lungo tale direzione. Addirittura, nel caso di soluzione degenere,lo spostamento potrebbe essere nullo. Inoltre non �e detto che un passodi discesa ripida porti necessariamente ad una terminazione pi�u rapidadell'algoritmo.
4. Uno dei metodi pi�u utilizzati nelle implementazioni attuali �e un com-promesso tra i due metodi precedenti { si sceglie cio�e la variabile en-trante tra quelle che possiedono il coe�ciente di costo minimo in unsottoinsieme costituito da un certo numero, k, degli indici diN associatia coe�cienti di costo ridotto negativo.
�E da sottolineare il fatto che nessuno dei metodi sopra illustrati si con�-gura come \ottimale"; �e possibile costruire esempi in cui ciascuno dei criterisopra esposti porta all'esplorazione di un numero eccessivo di soluzioni dibase. Il problema dell'esistenza o meno di strategie di pivoting e�cienti �eun problema tuttora aperto (si veda in proposito la discussione sull'e�cienzadel metodo del simplesso nel paragrafo 7.1.2).
In tutti questi metodi, nel caso di ulteriore incertezza nella scelta, siadotta un qualunque criterio di \tie breaking", ad esempio scegliendo ilcoe�ciente di indice minimo oppure estraendo a caso.
92
�E opportuno precisare che, nonostante i metodi suesposti richiedano costicomputazionali di�erenti, il vantaggio in termini di tempi globali di esecuzio-ne non sempre presenta signi�cative di�erenze. Se per�o il problema di PL �edotato di particolare struttura, alcune scelte diventano vantaggiose rispettoad altre: nel caso del problema del cammino minimo, ad esempio, si pu�odimostrare che, mentre il criterio 2 pu�o comportare un numero esponenzialedi passi di pivot, il criterio del gradiente richiede l'esecuzione di un numerodi passi di pivot polinomiale rispetto al numero di archi del grafo.
7.0.5 Scelta del vettore uscente dalla base
La scelta della variabile uscente di base non �e molto critica nel caso di soluzio-ni di base non degeneri; il caso in cui pu�o esistere incertezza nella scelta dellavariabile uscente di base corrisponde alla situazione in cui esistono almenodue variabili di base, �xl; �xk tali che
�? = ��xlyl
= ��xkyk:
In questo caso in genere si pu�o scegliere indi�erentemente l'una o l'altracome variabile uscente di base. Si pu�o per�o vedere che, in ogni caso, lasoluzione di base che si ottiene al termine dell'operazione di pivot, �e degenere.
Se la soluzione di base corrente �e degenere, �e possibile che l'operazione dipivot avvenga a livello 0, cio�e con �? = 0. In questo caso, e solo in questocaso, �e necessario utilizzare accorgimenti opportuni per evitare i cicli in�nitidi operazioni di pivot e, quindi, la non terminazione del metodo.
Si pu�o dimostrare che, nel caso di soluzioni di base degeneri, �e possibileun ciclo in�nito di iterazioni solo se almeno 2 variabili sono in base a livellozero e corrispondono a elementi negativi del vettore y. In questo caso occorreun criterio per decidere quale delle variabili a livello zero deve uscire di base.Il metodo pi�u semplice, anche se non molto utilizzato nella pratica, �e quellodi scegliere a caso (uniformemente): il metodo garantisce l'uscita dal ciclocon probabilit�a uno in un numero �nito di iterazioni.
Una tecnica pi�u usata �e la cosiddetta
regola di Bland,
che prescrive sia la scelta del vettore entrante che quella del vettore uscentedi base. Per il vettore entrante si sceglie il primo vettore il cui coe�ciente
93
di costo ridotto sia negativo (�e il criterio 2 visto nel precedente paragrafo);analogamente, per il vettore uscente, la scelta corrisponde al primo tra gliindici che realizzano il minimo nella (7.4). Cio�e si sceglie come variabileuscente la variabile di indice i? caratterizzata da:
i? = minfi 2 B : yi < 0; xi = 0g :
Naturalmente niente vieta di usare la regola di Bland anche nel caso dibasi non degeneri: basta in questo caso scegliere la variabile uscente con indiceminimo tra quelle che determinano il valore �?; tuttavia nella pratica si usageneralmente una regola di�erente (soprattutto per la scelta della variabileentrante) e si passa alla regola di Bland solamente quando si incontra unpivot degenere.
Questo algoritmo garantisce l'impossibilit�a di cicli in�niti e, come conse-guenza, la �nitezza dell'algoritmo del simplesso.
7.0.6 Finitezza del metodo del simplesso
Teorema 7.6 Il metodo del simplesso, equipaggiato con la regola di Bland,termina sempre in un numero �nito di iterazioni.
Dimostrazione. Per la dimostrazione �e su�ciente mostrare che, graziealla regola di Bland, il metodo del simplesso non entra in ciclo; si ipotizzi,per assurdo, che l'algoritmo non termini. Dovr�a quindi esistere una sequenzaciclica �nita di basi generata dal metodo; siano
B0; B1; : : : ; Bk�1; B0
gli insiemi di indici corrispondenti a tali basi. Sia
t = max
(i 2
k�1[r=0
Br : i =2k�1\r=0
Br
): (7.8)
In altre parole, t �e il massimo tra tutti gli indici che compaiono in almenouna, ma non in tutte le basi della sequenza. Nel corso delle operazioni dipivot che portano in successione alle basi B0; B1; : : : ; Bk�1, ad un certo puntola variabile t uscir�a di base. Si pu�o sempre immaginare, data la ciclicit�a dellasequenza, che t esca di base nel passaggio da B0 a B1. Si indichi con s lavariabile che, nel corso di questa operazione di pivot, entra in base.
94
Il dizionario corrispondente alla base B0 �e il seguente:
xB0=b0 �A�1B0
AN0xN0
z =�z + cTN0xN0
dove b0 e �z indicano rispettivamente la soluzione di base corrente ed il suovalore. In base alle ipotesi fatte t 2 B0; s 2 N0. Per come �e stato de�nito t,esister�a un altro dizionario, corrispondente ad esempio alla base Bk, in cuila variabile xt, dopo essere uscita di base, rientrer�a. Si consideri il dizionarioassociato a tale base:
xBk=bk �A�1Bk
ANkxNk
z =�z + cTNkxNk
:
Poich�e le operazioni di pivot considerate sono tutte degeneri, entrambii dizionari hanno lo stesso valore �z. Per quanto riguarda la soluzione dibase, il vettore bk non sar�a necessariamente identico a b0, ma conterr�a unapermutazione degli elementi di b0.
Associando un coe�ciente di costo ridotto nullo alle variabili di base, edindicando con c0 e ck rispettivamente i vettori dei coe�cienti di costo ridottoassociati alle basi B0 e Bk, si pu�o scrivere
z = �z +nX
j=0
c0jxj = �z +nX
j=0
ckjxj:
Si immagini ora di incrementare la variabile xs nel dizionario associato aB0, mantenendo �ssate a zero tutte le altre variabili fuori base:
xN0= es�
xB0= b0 + y�
z = �z + c0s�
dove con y si �e indicato il vettore �A�1B0As. L'obiettivo pu�o anche essere
scritto in funzione dei coe�cienti di costo ridotto associati alla base Bk:
z = �z +nX
j=0
ckjxj
= �z + cks� + ckT
B0(b0 + y�):
95
Uguagliando le due espressioni del costo si ottiene
�z + c0s� = �z + cks� + ckT
B0(b0 + y�)
da cui
c0s� = cks� + ckT
B0(b0 + y�)
ovvero, raccogliendo � a fattor comune,
(c0s � cks � ckT
B0y)� = ck
T
B0b0:
Questa relazione deve essere valida per qualunque valore di �, e, pertanto,deve risultare
c0s � cks � ckT
B0y = 0
ckT
B0b0 = 0:
A questo punto viene e�ettivamente utilizzata la regola di Bland: poich�ela variabile di indice s entra in base, certamente c0s < 0. La variabile diindice s, al pari di quella di indice t, compare in qualcuno dei dizionari delciclo, ma non in tutti. Si �e ipotizzato che t sia l'indice massimo tra quelliche corrispondono a variabili presenti in alcuni, ma non tutti, i dizionari (siveda la 7.8). Quindi s < t e sicuramente cks � 0, perch�e in caso contrario,per la regola di Bland, nel dizionario k sarebbe stata scelta la variabile xscome variabile entrante. Da queste considerazioni scende che
ckT
B0y < 0;
cio�e Xi2B0
cki yi < 0;
da cui segue che deve esistere almeno un indice r 2 B0 tale che ckryr < 0.Questo pu�o succedere solo se ckr 6= 0; ricordando che r 2 B0, si osserva
che anche la variabile xr appartiene a qualcuna, ma non a tutte, le basi delciclo ed, essendo t il massimo indice delle variabili di questo tipo, si avr�ar < t oppure r = t. Si vede facilmente che in realt�a non pu�o essere r = t.Infatti, poich�e la variabile di indice t �e la variabile entrante nel dizionario
96
associato a Bk, ckt < 0 e yt < 0 poich�e la variabile di indice t esce di base neldizionario associato a B0. Si ha quindi ckt yt > 0 e, pertanto, non pu�o esserer = t, essendo ckryr < 0.
Quindi r < t; deve essere allora ckr � 0, altrimenti, per la regola di Bland,al passo k entrerebbe in base la variabile di indice r e non quella di indice t,come si �e ipotizzato. Di conseguenza si avr�a yr < 0.
Ad ogni dizionario del ciclo, essendo ogni pivot degenere, nessuna variabilecambia valore e, pertanto, tutte le variabili che a volte sono in base e a volteno, avranno valore 0; ne segue che in particolare b0r = 0. Questo �e assurdo;infatti la scelta della variabile uscente di base, quando il dizionario �e quelloassociato a B0, avviene mediante la regola usuale (7.7):
i? 2 arg mini2B0:yi<0
��b0iyi
�
e, nel caso in esame, si avrebbe, per i = r, yr < 0 e b0r = 0; il pivot sarebbedunque degenere (e questo �e possibile), ma poich�e r < t, dalla regola di Blandsi sarebbe scelta la variabile r piuttosto che, come ipotizzato, la variabile t,da cui l'assurdo.
La dimostrazione della correttezza della regola di Bland �e piuttosto labo-riosa, ma non priva di eleganza. La regola stessa �e estremamente semplice,e�cace, anche se, a volte, non molto e�ciente; esistono altri metodi perevitare i cicli nel metodo del simplesso, ma generalmente non hanno la sem-plicit�a della regola di Bland. Una di queste regole, usata �no ad alcuni annifa, nasce dall'idea che la degenerazione pu�o essere eliminata spostando leg-germente i vincoli in modo da impedire che pi�u di n iperpiani si intersechinonello stesso punto.
Grazie alla correttezza delle regole anti-ciclaggio, come la regola di Bland,si possono dimostrare immediatamente due importantissime propriet�a deiproblemi di PL:
Teorema 7.7 Per ogni problema di PL in forma standard che ammettauna soluzione di base ottimale, esiste sempre almeno una soluzione di baseottimale alla quale sono associati coe�cienti di costo ridotto non negativi.
Dimostrazione. Se cos�� non fosse, eseguendo il metodo del simplessoa partire da una base ottimale, ad ogni passo di pivot si troverebbe semprealmeno un coe�ciente di costo ridotto negativo e l'algoritmo prima o poientrerebbe in un ciclo.
97
Teorema 7.8 Per ogni problema di PL vale una ed una sola delle seguenti:
1. il problema non �e ammissibile;
2. il problema ammette ottimo �nito;
3. il problema �e illimitato.
Dimostrazione. Se il problema �e ammissibile, �e possibile eseguire l'al-goritmo del simplesso equipaggiato con la regola di Bland. Data la �nitezzadelle basi e l'impossibilit�a di cicli, in un numero �nito di passi di pivot osi arriva ad una soluzione di base ottimale con tutti i coe�cienti di costoridotto non negativi, oppure si arriva all'individuazione di una direzione didecrescita illimitata dell'obiettivo.
7.1 Inizializzazione del metodo del simplesso
- Il metodo due fasi
Abbiamo visto �nora alcune propriet�a dei problemi di PL ammissibili e, inparticolare, dei problemi di PL per i quali sia nota una base iniziale ammis-sibile. In questo paragrafo si vedr�a come veri�care se un problema di PL �eammissibile o no ed, in caso a�ermativo, come trovare, se esiste, una solu-zione ammissibile di base. Infatti, non �e detto che un problema ammissibileammetta soluzioni ammissibili di base { il sistema di equazioni potrebbe nonessere ridotto al rango.
Tra i vari metodi esistenti per la ricerca di una soluzione ammissibile dibase, viene qui presentato il pi�u noto e di�uso, il cosiddetto metodo duefasi. Il nome deriva dal fatto che alla fase di ottimizzazione vera e propriaviene fatta precedere una prima fase il cui scopo �e unicamente determinare,se esiste, una base ammissibile iniziale. L'idea di questa prima fase nascedall'osservazione che in alcuni problemi di PL la determinazione di una baseiniziale ammissibile �e un problema banale. Si consideri infatti il problema:
min cTx
Ax � b
x � 0:
98
Se il termine noto b �e non negativo, allora aggiungendo le variabili di slacksi ottiene immediatamente una base ammissibile:
min�cT 0T
� � xs
��A I
� � xs
�= b
x; s � 0;
costituita dalla matrice identica. Quindi in un problema con variabili dislack e termine noto non negativo, le variabili di slack costituiscono unabase ammissibile. In un problema generico, che supponiamo essere in formastandard, possiamo sempre ricondurci al caso in cui il termine noto sia nonnegativo (al massimo si tratter�a di moltiplicare per �1 entrambi i membri dialcune equazioni). La prima fase del metodo due fasi consiste nella risoluzionedel seguente problema (detto \problema prima fase"):
min1Txa
Ax+ xa = b
x; xa � 0;
con b � 0.Come si vede il problema prima fase ha alcune variabili, xa dette \variabi-
li arti�ciali", che appaiono come variabili di slack. In realt�a esse sono diversedalle variabili di slack, in quanto queste ultime sono vere e proprie variabili,introdotte per scrivere in forma standard un problema di PL, mentre quellearti�ciali sono variabili che provocano una perturbazione del problema origi-nale. L'obiettivo del problema prima fase �e la minimizzazione della sommadi tali perturbazioni.
Si vede immediatamente che il problema prima fase non �e n�e inammissi-bile, n�e pu�o essere illimitato. Infatti una soluzione ammissibile (a patto checi si sia ricondotti al caso b � 0) esiste sempre, ed �e data da x = 0; xa = b.Anzi, questa �e una soluzione ammissibile di base; inoltre, poich�e il costo �euna combinazione non negativa di variabili non negative, il problema non po-tr�a essere illimitato inferiormente. Quindi, per quanto gi�a visto, il problemaprima fase ammette sempre soluzione ottimale. In base al valore dell'ottimopossiamo dedurre se il problema originale ammette soluzioni ammissibili. Sia
99
z? il valore dell'ottimo del problema prima fase e siano x? e xa?
le componentidi una soluzione ottimale. Vale il seguente
Teorema 7.9 Esiste almeno una soluzione ammissibile per il sistema Ax =b; x � 0 se e solo se z? = 0.
Dimostrazione. Se l'ottimo della prima fase �e 0 allora, essendo l'obietti-vo della prima fase pari alla somma delle variabili arti�ciali, e, poich�e questeultime sono non negative, esse dovranno essere tutte nulle. Quindi si avr�a
Ax? + 0 = b
x? � 0
e pertanto x? sar�a ammissibile per il problema originario.Se invece z? > 0, non �e possibile che esista una soluzione ammissibile per il
problema originale. Infatti, se per assurdo esistesse una soluzione ammissibile�x tale che A�x = b; �x � 0, allora ponendo �xa = 0 si otterrebbe una soluzioneammissibile per il problema prima fase il cui costo 1T �xa sarebbe 0. Ma questo�e assurdo se, come ipotizzato, l'ottimo del problema �e strettamente positivo.
Il valore ottimo del problema prima fase ci permette dunque di distingueretra problemi ammissibili e non e, nel caso di problemi ammissibili, fornisceuna soluzione particolare ammissibile. Tuttavia non �e detto che tale soluzionesia di base. Il teorema fondamentale garantisce che, nel caso di problemi neiquali il sistema di equazioni lineari sia ridotto al rango, se esiste una soluzioneammissibile ne esiste una ammissibile di base. La prima fase del metodo delsimplesso ci permette anche di determinare una soluzione di base ammissibile.Infatti si indichi con B l'insieme degli indici di una soluzione ottimale di basedel problema prima fase, nel caso in cui la prima fase sia terminata con costopari a 0. Si possono dare i seguenti casi:
1. nessuna variabile arti�ciale xa appartiene alla base B; in questo casoB �e una base ammissibile per il problema originario;
2. almeno una variabile arti�ciale compare nella base ottimale B; sicu-ramente tale variabile sar�a nulla, in quanto, essendo l'obiettivo dellaprima fase pari alla somma delle variabili arti�ciali, nessuna di questepotr�a essere diversa da zero se l'ottimo �e zero. Se �e possibile, occorre ef-fettuare un'operazione di pivot per far uscire di base tale variabile. Sia
100
xai una variabile arti�ciale in base a livello 0. Si consideri una variabilenon arti�ciale xj fuori base. Sia
A0 = A I
la matrice dei coe�cienti del problema prima fase. Si �e visto (teore-ma 7.3) che condizione necessaria e su�ciente per poter e�ettuare loscambio tra la colonna A0j di coe�cienti di xj e quella dei coe�cienti di
xai �e che l'i{esima componente del vettore d = �A0�1B A0j sia non nulla.Quindi se (e solo se) esiste una variabile fuori base xj tale che
yi = �eTi A0�1B A0j 6= 0
allora sar�a possibile scambiare le colonne dei coe�cienti di xj e di xai .Poich�e la variabile arti�ciale xai �e a livello 0, tale operazione cambiasolo la composizione della base, non la soluzione di base (si e�ettua unpasso di lunghezza 0). Pertanto in questo caso �e possibile e�ettuareun'operazione di pivot sia se yi < 0 che se yi > 0. Si osservi che, ingenerale un'operazione di pivot che faccia uscire di base una variabilecui �e associato un coe�ciente yi > 0, nel metodo del simplesso non�e ammessa, poich�e il risultato sarebbe una perdita di ammissibilit�a.Anche nel metodo del simplesso per�o, se la variabile entrante in baseha valore 0, l'operazione �e in teoria possibile, dato che un passo dilunghezza 0 non modi�ca la soluzione corrente. Tuttavia nel metododel simplesso, sebbene possibile, questa operazione non ha interessealcuno e, pertanto, non viene mai e�ettuata. Nella prima fase delmetodo due fasi invece tale operazione di pivot pu�o servire a far usciredi base la variabile arti�ciale yi. L'unico caso in cui l'operazione dipivot non �e possibile �e quello in cui per nessuna variabile xj fuori basesi ha �eTi A
0�1B A0j 6= 0. Ma questo signi�ca che �eTi A
0�1B AN = 0, dove
AN , al solito, rappresenta la matrice delle colonne dei coe�cienti dellevariabili x fuori base. Si ha anche
eTi A0�1B A0B = eTi
e quindi, essendo yi arti�ciale,
eTi A0�1B A0Bx
= 0
101
dove con A0Bxsi sono indicate le colonne della matrice di base associate
a variabili x non arti�ciali. Si �e quindi dimostrato che
eTi A0�1B A = 0
Il vettore eTi A0�1B fornisce quindi una combinazione lineare nulla non
banale delle righe di A. La matrice A quindi in questo caso non harango massimo. Poich�e il sistema Ax = b era ammissibile, signi�ca cheun'equazione, in questo caso quella di indice i, �e ridondante e pu�o essereeliminata dal dizionario �nale del problema, al termine della prima fase.
Quindi si potranno fare uscire di base, attraverso operazioni di pivot,tutte e sole le variabili arti�ciali presenti in base e associate ad equazionidel sistema Ax = b fra loro linearmente indipendenti.
Una volta terminata la prima fase del metodo due fasi, nel caso in cui sisia determinata una base ammissibile, si pu�o iniziare con il normale metododel simplesso e determinare, se esiste, una soluzione ottimale del problemaoriginario.
Esempio 7.6 Si consideri il problema di PL seguente
min�1 �1 0 1 2
�x2
4 1 �1 �1 1 2�1 �1 0 2 12 0 �1 �1 1
35 x =
24 212
35
x � 0:
Poich�e non �e evidente una base iniziale si imposta il problema prima fase:
min�1 1 1
�xa2
4 1 �1 �1 1 2�1 �1 0 2 12 0 �1 �1 1
35 x+ xa =
24 212
35
x; xa � 0:
Utilizzando il dizionario per questo problema, si ha:
z = 5 � 2x1 + 2x2 + 2x3 � 2x4 � 4x5
xa1 = 2 � x1 + x2 + x3 � x4 � 2x5
xa2 = 1 + x1 + x2 � 2x4 � x5
xa3 = 2 � 2x1 + x3 + x4 � x5
102
Facendo entrare in base la variabile x5 (regola del coe�ciente di costo ridottominimo), si ottiene
z = 1 + 2xa1 + 2x4
x5 = 1�1
2xa1 �
1
2x1 +
1
2x2 +
1
2x3 �
1
2x4
xa2 =3
2x1 +
1
2x2 �
1
2x3 �
3
2x4 +
1
2xa1
xa3 = 1�3
2x1 �
1
2x2 +
1
2x3 +
3
2x4 +
1
2xa1
In questo caso si pu�o concludere che il problema dato �e privo di soluzioniammissibili, in quanto la prima fase �e terminata con valore strettamente
positivo. Se il termine noto del problema iniziale fosse stato
24 211
35, si sarebbe
invece ottenuto il dizionario seguente:
z = 0 + 2xa1 + 2x4
x5 = 1�1
2xa1 �
1
2x1 +
1
2x2 +
1
2x3 �
1
2x4
xa2 =3
2x1 +
1
2x2 �
1
2x3 �
3
2x4 +
1
2xa1
xa3 = 0�3
2x1 �
1
2x2 +
1
2x3 +
3
2x4 +
1
2xa1
Da questo dizionario si deduce che il problema originario ammette soluzioni:ad esempio la scelta x5 = 1, con tutte le altre variabili nulle, soddisfa ilsistema dei vincoli, come �e facile vedere per sostituzione diretta. Quindi �enota una soluzione ammissibile, non per�o una soluzione ammissibile di base.Per determinare una base occorre, se possibile, far uscire di base tutte levariabili arti�ciali, e�ettuando pivot degeneri. Ad esempio, �e possibile faruscire di base la variabile arti�ciale xa2 facendo un'operazione di pivot conuna qualsiasi delle quattro variabili x presenti nell'equazione che de�niscexa2, indipendentemente dal segno del coe�ciente. Ad esempio, scambiando
103
xa2 con x2 si ottiene il dizionario:
z = 2xa1 + 2x4
x2 = 2xa2 � 3x1 + 3x4 � xa1 + x3
x5 = 1 � xa1 � 2x1 + xa2 + x4 + x3
xa3 = �xa2 + xa1;
che ancora non rappresenta una soluzione di base; volendo far uscire di basela variabile xa3, si scopre che non �e possibile, in quanto nell'equazione che de-�nisce tale variabile non compare nessuna incognita del problema originario.Ricordando che il problema iniziale non conteneva le variabili arti�ciali, sipu�o anche considerare che la terza equazione sia stata trasformata nell'equi-valente equazione ridondante 0Tx = 0, che pu�o essere eliminata dal problema.Il problema dato pu�o pertanto essere risolto partendo dal dizionario seguen-te (seconda fase), nel quale �e stata inserita l'equazione del costo, sono stateeliminate le variabili arti�ciali della prima fase ed �e stata eliminata la terzaequazione, combinazione lineare delle prime due:
z = 2 + x3
x2 = �3x1 + 3x4 + x3
x5 = 1 � 2x1 + x4 + x3:
Per coincidenza, il dizionario iniziale �e gi�a ottimale. Si conclude pertantoche la soluzione x5 = 1 �e ottima per il problema dato.
7.1.1 Problemi con in�niti ottimi
Se, al termine del metodo del simplesso, esistono dei coe�cienti di costoridotto nulli, possono esistere in�nite soluzioni ottimali; infatti incrementan-do, se possibile, la componente non di base associata ad un coe�ciente dicosto ridotto nullo, la funzione obiettivo non varier�a. Se l'incremento �? sar�astrettamente positivo e �nito, si otterr�a un nuovo vertice ottimale; �e imme-diato veri�care che, se x? ed y? sono due soluzioni ottimali per un problemadi PL, anche ogni soluzione ottenuta come loro combinazione convessa sar�aammissibile ed ottimale. In particolare, se si compie un'operazione di pivotper portare in base la variabile corrispondente al coe�ciente di costo ridottonullo, se esiste almeno una componente negativa nel corrispondente vettoredirezione y, l'operazione di pivot pu�o essere eseguita e si determina cos�� una
104
nuova base ottimale; se invece le componenti di y sono tutte positive o nul-le allora non esister�a una corrispondente soluzione di base, ma esisterannocomunque in�nite soluzioni ottimali. In altri termini, se x? �e una soluzioneottimale associata ad una base AB ed esiste un coe�ciente di costo ridotto,ad esempio cj, nullo, allora per ogni valore di 0 � � � �? dove
�? =
�minf�xi
yi: yi < 0g se 9 i 2 B : yi < 0
+1 altrimenti(7.9)
il vettore
x(�) =
�A�1B b0
�+
�yej
��
�e soluzione ottimale del problema di PL. Naturalmente se nella (7.9) risulta�? = 0, in corrispondenza di ogni coe�ciente di costo ridotto nullo, allora lasoluzione ottimale sar�a ancora unica, pur esistendo diverse basi ottimali. Unproblema di PL (in forma standard e ridotto al rango), se ammette ottimo�nito, pu�o dunque avere una e una sola soluzione ottimale (e, in questo caso,sar�a sicuramente una soluzione ottimale di base), oppure in�nite soluzioniottimali (almeno una delle quali di base). Un problema di PL con uno o in�-niti ottimi pu�o ammettere diverse basi ottimali; una stessa soluzione ottimalepu�o, nel caso degenere, corrispondere a diverse basi ottimali. Un problemadi PL pu�o avere in�nite soluzioni ottimali, tra cui anche una sola potreb-be essere di base. Si noti che, in un caso degenere, un'operazione di pivotdegenere non porta ad un cambiamento della soluzione (�? = 0); in questocaso �e possibile anche e�ettuare un'operazione di pivot corrispondente ad unelemento positivo di y senza perdere l'ammissibilit�a e l'ottimalit�a { si trattain sostanza di un passo in una direzione non ammissibile, ma di lunghezza 0e, pertanto, non si perde l'ammissibilit�a.
Per comprendere meglio la struttura dei problemi di PL e delle lorosoluzioni ottimali, �e utile tenere presente le seguenti propriet�a:
Teorema 7.10 L'insieme ammissibile di un problema di PL �e convesso.
Dimostrazione. Si ricordi che un insieme S �e convesso se e solo secomunque scelti due suoi elementi u 2 S; v 2 S, ciascuna loro combinazioneconvessa appartiene ad S, cio�e
�u+ (1� �)v 2 S 8� 2 [0; 1]:
105
Scegliendo due soluzioni u e v, ammissibili per un problema in cui S =fx 2 Rn : Ax = b; x � 0g si ha che la combinazione convessa �u+ (1� �)v �enon negativa (essendo combinazione non negativa di due vettori non negativi)e inoltre
A(�u+ (1� �)v) = �Au+ (1 � �)Av
= �b + (1� �)b = b;
pertanto �u+ (1� �)v �e soluzione ammissibile per ogni � 2 [0; 1].
Teorema 7.11 L'insieme delle soluzioni ottimali di un problema di PL cheammette ottimo �nito �e convesso.
Dimostrazione. E' su�ciente dimostrare che il costo della combinazioneconvessa di due soluzioni ottimali �e ancora ottimale. In e�etti, se u e v sonosoluzioni ottimali, di valore z, si ha
cT (�u+ (1 � �)v) = �cTu+ (1� �)cTv
= �z + (1 � �)z = z:
Il seguente teorema fornisce una rappresentazione �nita dei poliedri.
Teorema 7.12 (Minkoswski) Dato un qualsiasi poliedro S = fx 2 Rn : Ax = b; x � 0gesiste un numero �nito di elementi v1; v2; : : : ; vk 2 S ed un insieme �ni-to di vettori y1; y2; : : : ; yh 2 Rn tale che ogni elemento x di S pu�o essererappresentato come
x =kX
i=1
�ivi +hX
j=1
�jyj
con
�j � 0 8jkX
i=1
�i = 1; �i � 0 8i:
Il teorema di Minkowski permette di generare ogni poliedro attraversola somma di una combinazione convessa (cio�e e�ettuata con coe�cienti non
106
negativi a somma unitaria) di un numero �nito di suoi elementi (l'insiememinimale di tali elementi �e costituito dai vertici del poliedro) e di una com-binazione a coe�cienti non negativi di un numero �nito di vettori; in questocaso l'insieme minimale �e costituito dai cosiddetti raggi estremi del poliedro.Un raggio r in un poliedro S �e un vettore di Rn tale che, se u 2 S, allora
u+ �r 2 S 8� � 0:
I raggi sono dunque direzioni ammissibili che permettono uno sposta-mento illimitato in un verso, senza mai uscire dall'insieme ammissibile, apartire da un qualunque punto ammissibile. I raggi estremi sono raggi chenon �e possibile rappresentare come combinazione convessa non banale (cio�ea coe�cienti non 0 n�e 1) di altri due raggi.
Esempio 7.7 Si consideri il problema
min�0 0 0 1
�x�
1 0 1 10 1 �1 2
�x =
�21
�x � 0
che possiede la soluzione ottimale x =�0 3 2 0
�T, corrispondente alla
base A2;3. Per confermare che questa �e la base ottimale basta calcolare icoe�cienti di costo ridotto:
c1;4 =�0 1
���0 0
�A�12;3A1;4
=�0 1
�:
Il coe�ciente di costo ridotto della variabile x1 �e nullo; �e possibile per-tanto che esistano in�nite soluzioni ottimali. Per determinarle si cerca sepossibile di fare entrare in base la variabile x1:
y = �A�12;3A1 = �
�0 11 �1
��1 �10
�=
��1�1
�:
La variabile uscente di base viene determinata con la regola usuale:
min
���x2y2;�
�x3y3
�= min
��
3
�1;�
2
�1
�
= 2 = ��x3y3:
107
La variabile uscente di base �e quindi la x3; la nuova base diviene B =f1; 2g. La soluzione associata a questa base �e
�x1;2 =
�1 00 1
��1 �21
�=
�21
�
ed i coe�cienti di costo ridotto ad essa associati sono
cT3;4 =�0 1
���0 0
� � 1 00 1
��1 �1 1
�1 2
�=�0 1
�:
Questa veri�ca non �e in realt�a necessaria per dimostrare l'ottimalit�a dellasoluzione corrente, dato che avendo fatto entrare in base una variabile concoe�ciente di costo ridotto nullo, sicuramente non si avr�a un cambio del-la funzione obiettivo. Per�o dai coe�cienti di costo ridotto di quest'ultimasoluzione di base si vede che per trovare altre soluzioni di base ottimali sidovrebbe fare rientrare in base la variabile x3, che ne �e appena uscita. Si pu�oquindi concludere che le due soluzioni di base trovate sono le uniche soluzio-ni ottimali di base. Non esistono raggi nel poliedro delle soluzioni ottimali(altrimenti si sarebbero trovati in corrispondenza di un coe�ciente di costoridotto nullo). Quindi tutte e sole le soluzioni ottimali sono ottenibili da unacombinazione convessa delle due appena trovate:
x?(�) = �
26640320
3775 + (1� �)
2664
2100
3775 =
26642� 2�2� + 12�0
3775
con � 2 [0; 1].
Esempio 7.8 Se si considera il problema seguente, ottenuto modi�cando inparte il precedente,
min�0 0 0 1
�x�
1 0 �1 10 1 �1 2
�x =
�21
�x � 0
108
si vede facilmente che la base B = f1; 2g �e, come nell'esempio precedente,ottimale. I coe�cienti di costo ridotto associati a questa base sono anco-ra cT3;4 =
�0 1
�. Cercando di fare entrare in base la variabile x3, con
coe�ciente di costo ridotto nullo, si ottiene:
y = �A�11;2A3 =
�11
�:
Lungo la direzione individuata dal vettore y per le variabili di base �e possi-bile compiere uno spostamento illimitato senza perdere l'ammissibilit�a; lungoquesta direzione inoltre il costo non cambia e, pertanto, si �e determinato unraggio (estremo) ottimale:
x�(�) =
��x1;20
�+
�ye1
��
=
26642100
3775+
26641110
3775 �
=
26642 + �1 + ��0
3775 :
Le soluzioni x?(�) sono ottimali per ogni scelta di � � 0. Di queste in�nitesoluzioni, una sola, caratterizzata da � = 0, �e di base.
Esempio 7.9 Il problema
min�0 0 0 1
�x�
1 0 1 10 1 �1 2
�x =
�1
�1
�x � 0
�e ancora una variante dei precedenti, e possiede la soluzione ottimale �x =�0 0 1 0
�T, degenere, ancora associata alla base A2;3. La conferma �e
banale, in quanto la soluzione �e ammissibile (come �e facile controllare sosti-tuendo il vettore �x nel sistema di equazioni) e i coe�cienti di costo ridotto,essendo indipendenti dal vettore dei termini noti, sono ancora pari a
cT1;4 =�0 1
�:
109
Cercando di fare entrare in base la variabile di costo ridotto nullo x1, siottiene
y = �A�12;3A1 =
��1�1
�;
il passo di lunghezza massima possibile in questa direzione �e dato da
�? = min
��
0
�1;�
1
�1
�= 0:
Si pu�o dire, in questo caso, che le in�nite soluzioni ottimali sono degene-rate in un solo punto, la soluzione di base corrente. Si osservi che, in questocaso, la soluzione di base �e degenere: se in una soluzione ottimale di base nondegenere esiste almeno un coe�ciente di costo ridotto nullo, allora esistonosempre in�niti ottimi. Naturalmente, in questo caso, �e possibile fare entrarein base la variabile x1 al posto della variabile x2: la nuova base A1;3 �e ancoraottimale e corrisponde alla soluzione di base
�x1;3 =
�1 10 �1
��1 �1�1
�=
�01
�
che rappresenta sempre la stessa soluzione, �x3 = 1. Esistono pertanto pi�ubasi ottimali, ma una sola soluzione ottimale (si pu�o veri�care che le basiottimali in questo esempio sono 3).
Esempio 7.10 (continuazione).I tre esempi appena visti possono essere facilmente rappresentati gra�ca-
mente: infatti le prime due variabili, associate alla matrice identica, possonoessere viste come variabili di slack e i tre esempi assumono dunque le seguentiforme:
minx;y
y
x+ y � 2
�x+ 2y � 1
x; y � 0
110
0
0.5
1
1.5
2
2.5
3
0 0.5 1 1.5 2 2.5 3
miny
�x+ y � 2
�x+ 2y � 1
x; y � 0
0
0.5
1
1.5
2
2.5
3
0 0.5 1 1.5 2 2.5 3
111
miny
x+ y � 1
�x+ 2y � �1
x; y � 0
0
0.5
1
1.5
2
2.5
3
0 0.5 1 1.5 2 2.5 3
In tutti e tre gli esempi, sono ottimali tutte le soluzioni ammissibili cheappartengono all'asse delle x.
7.1.2 E�cienza del metodo del simplesso
Esiste un'importante teoria, detta teoria della complessit�a computazionale, icui scopi sono l'analisi e la classi�cazione dei problemi in classi di di�colt�adi�erente. Non ci vogliamo addentrare qui in una discussione specialisticasull'argomento. Con molta approssimazione si pu�o dire che una classe di pro-blemi �e considerata computazionalmente facile se esiste un algoritmo in gradodi risolvere qualsiasi esempio di tale classe compiendo un numero di operazio-ni elementari che �e asintoticamente limitato da un polinomio di grado �nitonella dimensione di tale esempio. La de�nizione di \dimensione" di un pro-blema non �e banale: per la programmazione lineare dimensioni naturali sono
112
m ed n, ma questo non basta a caratterizzare in modo soddisfacente la realedimensione del problema. Esistono, ad esempio, molte implementazioni delmetodo del simplesso che sfruttano la sparsit�a della matrice dei coe�cienti.E' ragionevole pensare quindi che i problemi di PL siano in genere tanto pi�udi�cili quanto meno sparsa �e la matrice dei coe�cienti. La de�nizione comu-nemente accettata di dimensione di un problema corrisponde alla lunghezzadi una codi�ca e�ciente dell'intero insieme dei coe�cienti
~A =
�A bcT 0
�del problema di PL. Ad esempio, volendo memorizzare i dati di un problemadi PL (con coe�cienti interi o razionali) in forma binaria, ed utilizzando ilminimo numero possibile di bit per ogni dato ed un separatore tra un dato el'altro, si vede che occorreranno
L = O(mn +X
i;j: ~Aij 6=0
log(j ~Aijj))
bit (il simbolo O(f(k)) indica una quantit�a tale che lim supk!1O(f(k))f(k)
�
1). Un algoritmo polinomiale per la PL dovrebbe poter risolvere qualsiasiproblema di PL in un tempo O(Lr), con r costante opportuna.
La questione se la PL fosse o meno una classe di problemi risolvibili inmodo e�ciente, al di l�a della notevole e�cienza pratica del metodo del sim-plesso, �e rimasta aperta �no agli anni '80, quando �e stato de�nitivamentedimostrato che esistono algoritmi polinomiali per la PL. Curiosamente, ilmetodo del simplesso non �e un algoritmo polinomiale. Per tutte le imple-mentazioni note del metodo si �e potuta trovare una successione di problemiparticolari, a lunghezza crescente, per il quale il metodo richiede un numeroesponenziale di passi di pivot.
Per l'implementazione basata sulla scelta della variabile entrante con coef-�ciente di costo ridotto minimo, il seguente esempio fornisce il caso peggioreper il metodo del simplesso:
maxnX
j=1
10n�jxj
2i�1Xj=1
10i�jxj + xi � 100i�1 i = 1; : : : ; n
xj � 0 j = 1; : : : n
113
Esempio 7.11 Per n = 4 il problema diventa
max�1000 100 10 1 0 0 0 0
�x2
6641 0 0 0 1 0 0 020 1 0 0 0 1 0 0200 20 1 0 0 0 1 02000 200 20 1 0 0 0 1
3775x =
2664
1100
10 0001 000 000
3775
x � 0
Si nota subito come questo sia un problema mal scalato, cio�e con coef-�cienti il cui ordine di grandezza �e molto diverso. A causa della diver-sa grandezza dei termini noti, l'insieme ammissibile non �e molto diversodall'iperrettangolo
0 � x1 � 1
0 � x2 � 100
0 � x3 � 10 000
0 � x4 � 1 000 000:
Eseguendo il metodo del simplesso a partire dalla base A5;6;7;8, corrispon-dente all'origine nello spazio delle prime 4 incognite, scegliendo la variabileentrante con coe�ciente di costo ridotto minimo, vengono visitati tutti i 24
vertici dell'iperrettangolo deformato.
L'algoritmo del simplesso ha rappresentato, e rappresenta tuttora, uncampo di ricerca estremamente ricco ed aperto. Non �e ancora stata fornita,ad esempio, una soddisfacente giusti�cazione teorica del fatto che, nonostantei risultati fortemente negativi della teoria della complessit�a, l'algoritmo delsimplesso sia in pratica, un metodo estremamente e�ciente, utilizzato perrisolvere problemi con centinaia di migliaia di variabili. Esistono studi sullacomplessit�a media del metodo, ma in genere i modelli stocastici su cui sonobasati non sono su�cientemente vicini ai problemi reali. Studi sia empiriciche teorici tendono a sostenere che il metodo del simplesso termina con unnumero di passi di pivot O(m), in genere compresi tra 3m e 4m.
Un'altra questione tuttora aperta �e la seguente: per ogni tipo di strategiadi pivoting �nora tentata, si �e potuto determinare un controesempio per ilquale il metodo richiede un numero esponenziale di pivot. Ma questo non �esu�ciente per concludere che non pu�o esistere una strategia di pivoting che
114
renda il metodo polinomiale. A tutt'oggi non �e ancora chiaro se tale strategiapossa esistere o meno.
115
