Il metodo del simplesso è una procedura molto usata per risolvereproblemi di programmazione lineare. Esso consente di trovare un'allo-cazione ottimale delle risorse spostandosi da un vertice all'altro lungogli spigoli di un politopo, solido tridimensionale le cui facce sonopoligoni. Ciascun punto della porzione di spazio in cui è costruito ilpolitopo corrisponde a un particolare programma di allocazione dimanodopera, capitale o altre risorse e a ciascun programma corrispon-de un beneficio (o costo) netto. Scopo della programmazione lineare èdi individuare il programma che presenti il massimo di benefici e ilminimo di costi. Il politopo definisce una zona «ammissibile»: tutti iprogrammi di allocazione delle risorse rappresentati da punti contenuti

nel politopo o appartenenti alla sua superficie sono ammissibili, mentrequelli rappresentati da punti esterni al politopo non lo sono a causadella scarsità di risorse. Quando il rapporto fra risorse e costi o beneficiè lineare, i valori di massimo e di minimo devono giacere in corrispon-denza di uno dei vertici del politopo. L'algoritmo del simplesso passa inrassegna in modo selettivo i vertici, tracciando un percorso (ABC... V)lungo gli spigoli del politopo. A ciascun passo del percorso la misura deibenefici o dei costi continua a migliorare fino a raggiungere nel puntoM il massimo o il minimo. Vi sono spesso numerosi percorsi che vannodal vertice di partenza A a M. Il politopo non deve necessariamenteessere tridimensionale: anzi comunemente ha migliaia di dimensioni.

Programmazione linearee allocazione di risorse

aggiuntivi e risolvere nuovamente il pro-blema onde esaminarne gli effetti. Essopuò, per esempio, dire tempestivamenteall'imprenditore quanto costa fornire unservizio che non dà profitto ma che puòassicurargli la buona disposizione delcliente.

Il metodo del simplesso si è dimostratoestremamente efficiente nella soluzionedi problemi complessi di programmazio-

ne lineare con migliaia di vincoli, anche sela sua rapidità ha sempre rappresentatoper i teorici un enigma, mancando unaspiegazione definitiva del motivo di que-ste ottime prestazioni. Di fatto, vi sonoproblemi costruiti dai matematici per iquali il metodo del simplesso è di unalentezza inaccettabile. Ma per ragioni chenon sono del tutto chiare, tali probleminon sembrano presentarsi nella pratica.

Alcuni matematici sovietici hanno re-centemente messo a punto un nuovo algo-ritmo per la programmazione lineare cheevita, in un certo senso, alcune difficoltàteoriche attribuite al metodo del imples-so. A dimostrazione del significato eco-nomico della programmazione lineareoggi, la notizia di questo risultato è appar-sa sulle prime pagine dei giornali in tuttailmondo. Sfortunatamente, il nuovo algo-

Strutture astratte simili a cristalli pluridimensionali possono aiutarcia risolvere problemi di programmazione e di amministrazione. Un nuovoalgoritmo pone un limite superiore alla complessità di questi problemi

C

onsideriamo la situazione di unapiccola fabbrica di birra i cuiprodotti, e cioè la birra e lo «ale»

(bevanda molto diffusa negli Stati Unitisimile alla birra ma più alcoolica), venga-no costantemente richiesti dal mercatoma la cui fabbricazione sia limitata daalcune materie prime scarseggianti. Sup-poniamo che queste ultime siano il mais, illuppolo e il malto d'orzo. La ricetta per unbarile di ale richiede un dosaggio degliingredienti differente da quello per unbarile di birra. Lo ale, ad esempio, vuolepiù malto per barile che non la birra. Inol-tre il fabbricante ricava dalla vendita del-lo ale un profitto di 13 dollari a barile,contro 23 dollari a barile di birra. Sogget-to a tali condizioni, come può il fabbrican-te massimizzare i propri profitti?

Si potrebbe pensare che il programmaproduttivo migliore sia di impiegare tuttele risorse nella fabbricazione del prodottoche garantisce maggiori profitti, e cioè labirra. Questa scelta tuttavia può non esse-re la più saggia, dal momento che la produ-zione di questo tipo di birra può consuma-re alcune delle risorse disponibili con unarapidità maggiore dello ale. Se ci vogliono5 libbre (1 libbra = 0,453 chilogrammi) dimais per fare un barile (1 barile = 119,22litri) di ale e 15 libbre per fare un barile dibirra, è possibile produrre il triplo di aleche di birra. Inoltre, producendo solo bir-ra, il fabbricante scoprirà di consumaretutto il mais prima di aver esaurito le scortedi luppolo e di malto. Un uso più vantag-gioso delle risorse e quindi un profittomaggiore si possono invece ottenere dallaproduzione mista di ale e di birra. Madefinire un simile programma produttivodi ottimo non è un problema banale. Eesattamente questo il tipo di problemi lacui formulazione esplicita, analisi e solu-zione, sono affidate alle tecniche dellaprogrammazione lineare. Quest'ultima èuna branca della matematica che rientranel più ampio campo d'indagine della co-siddetta ricerca operativa, in cui i più di-

di Robert G. Bland

sparati metodi di modellistica matematicae di analisi quantitativa vengono applicatialla gestione di grandi imprese e organi-smi. La programmazione lineare fu messaa punto nell'immediato secondo dopo-guerra in risposta a problemi logistici che sierano presentati durante e subito dopo laguerra. Una delle prime pubblicazioni sul-l'impiego della programmazione lineareconteneva la discussione di un modello delpeso totale aerotrasportato a Berlino nel1948.

Per quanto l'elaboratore sia uno stru-mento indispensabile per risolvere pro-blemi di programmazione lineare, il ter-mine «programmazione» è inteso nel sen-so di stesura di piani e non di formulazionedi programmi per elaboratore. L'aggetti-vo «lineare» si riferisce invece a una pro-prietà matematica di certi problemi che nesemplifica l'analisi. Nel problema dellafabbrica di birra si suppone, per esempio,che il quantitativo di una qualsiasi risorsanecessaria a produrre ale o birra sia pro-porzionale alla quantità di bevanda pro-dotta. Raddoppiando cioè la quantità dibirra, si raddoppia la quantità di ciascuningrediente necessario alla sua produzio-ne, e si raddoppia anche il profitto imputa-bile alla sua vendita. Se si traccia il dia-gramma cartesiano del consumo di mais infunzione della quantità di birra prodottacon il medesimo, si ottiene una retta. Perapplicare le tecniche della programma-zione lineare si deve altresì supporre che iprodotti e le risorse siano quantità divisibi-li, almeno in via approssimativa. Così sipotrà produrre mezzo ettolitro di birra conun valore che sarà la metà di quello di unettolitro intero.

Un tipico ambito dei problemi di pro-grammazione lineare è la ripartizione

di risorse scarse su un certo numero diprodotti o attività, alle condizioni di pro-porzionalità e divisibilità ora descritte. Talirisorse possono essere materie prime, pro-dotti semilavorati, manodopera, capitali

investiti o tempi di lavoro su macchine digrandi dimensioni e molto costose. Un'al-locazione di ottimo sarà quella che massi-mizza una certa misura di benefici o utilità,come il profitto, o ne minimizza una di costi.Nella nostra epoca di produttività decre-scente e di risorse in diminuzione sarà cer-tamente utile esaminare una tecnica capacedi allocare le risorse con la massima effi-cienza possibile.

Le proprietà dei problemi di program-mazione lineare discendono da alcuniprincipi elementari di algebra e di geome-tria. La soluzione efficiente di tali pro-blemi dipende da algoritmi, o procedurecompletamente specificate passo per pas-so, in grado di sfruttare nel modo piùintelligente questi principi algebrici egeometrici. Questi algoritmi sono altresìdi semplice concezione, per quanto com-plicati possano apparire i dettagli delleloro operazioni. E dall'efficacia e dallaversatilità di un singolo algoritmo, il co-siddetto «metodo del simplesso», che di-scende in gran parte il rilievo economicodella programmazione lineare.

Il metodo del simplesso è stato introdot-to nel 1947 da George B. Dantzig, ora allaStanford University. Il suo valore essen-ziale consiste nella rapidità, nella ricchez-za delle applicazioni e nella possibilità dirispondere a importanti quesiti circa lasuscettibilità delle soluzioni a variazionidei dati in entrata. Per esempio: in chemisura deve essere modificato il pro-gramma produttivo del fabbricante di bir-ra se si sono modificate le disponibilità diluppolo e la resa economica della birra?Quanto dovrà essere disposto a pagare perulteriori scorte di risorse che scarseggia-no? Quanto dovrà farsi pagare da un altroimprenditore che voglia comprare da luidelle risorse? Il criterio del simplesso puòaiutare a decidere se sia meglio acquistareo vendere una macchina, farsi prestaredenaro o concedere prestiti e pagare deglistraordinari o farne a meno. Con il suoaiuto è inoltre possibile imporre vincoli

92 93

EDIFICIO B

'‘.1..s19 Sé)0.o cp '' 09 P .., 00°

O .' O'P' .<3 0C' P

sx.P cj \ O,,* ..s0 9F-

00' \ >0 kt,o.•09. P O(e? <2;.\ -- ‘4̀ 0° 0\ > <1'90 0 p.

."- 0 C' \i'. O 0- \,'.. 0 c,

6 1 2

7 6 5

6 2 4

6 + 6 + 4 = 16

6 1 2

7 6 5

6 2 4

1 + 7 + 4 = 12 2 + 7 .+ 2 = 11

EDIFICIO A

EDIFICIO B

EDIFICIO C

EDIFICIO A

EDIFICIO B

EDIFICIO C

6 1 2

7 6 5

6 2 4

6 + 5 + 2 = 13

1 + 5 + 6 = 12

2 + 6 + 6 = 14

L'applicazione di attribuzione cerca di minimizzare il costo dell'adat-tamento di edifici disponibili per il ripristino a funzioni che debbonoessere svolte ciascuna in un solo edificio. Con tre edifici e tre funzionioccorre considerare 3 2 ovvero nove costi per altrettanti interventi dirinnovamento. I costi (valutati in miliardi di lire) sono riportati in unamatrice numerica; un'attribuzione ammissibile sceglie un numero per

ciascuna riga e ciascuna colonna della matrice. Vi sono 3 x 2 x I ov-vero sei alternative possibili. Più in generale, per attribuzioni di dimen-sione n-per-n il numero delle attribuzioni è n fattoriale (scritto n.' ), paria n moltiplicato per tutti gli interi positivi minori di n. A causa dellarapidità con cui cresce n! è praticamente impossibile determinare ilcosto minimo mediante enumerazione di tutte le possibili attribuzioni.

11~111•91•••1111•111••111MMEM•IN••

MENEM!~

EDIFICIO A

LABORATORIO

6 7 6

BIBLIOTECA

6 2

CAMPI DA TENNIS

2 5 4

6 1 2

7 6 5

6 2 4

6 1 2

7 6 5

6 2 4

6 6 12 4 14 11 3 9 4 10

8 12 17 8 16 16 6 13 7 13

11 13 18 9 15 16 8 14 8 14

8 10 15 10 16 13 7 9 7 11

13 15 16 11 19 19 10 16 12 18

9 12 17 8 16 15 7 13 7 11

8 8 13 8 13 12 6 8 4 11

6 8 11 3 14 10 2 8 3 9

5 5 12 2 12 7 2 9 6 12

15 14 17 13 17 18 7 18 10 16

1 0 2 0 3 2 1 2 1 2

0 3 4 1 2 4 1 3 1 2

2 3 4 1 0 3 2 3 1 2

1 2 3 4 3 2 3 0 2 1

2 3 0 1 2 4 2 3 3 4

1 3 4 1 2 3 2 3 1 0

2 1 2 3 1 2 3 0 0 2

2 3 2 0 4 2 1 2 1 2

2 1 4 0 3 0 2 4 5 6

5 3 2 4 1 4 0 6 2 3

ritmo, che va sotto il nome di «metododell'ellissoide», ha finora poche speranzedi superare nella pratica il metodo delsimplesso. Il fatto è che, al presente, vi èuna curiosa divergenza fra misure pratichee teoriche di esecuzione dei calcoli.

Anche quando si utilizza un algoritmoefficiente, i costi di messa a punto per lasoluzione di un problema molto ampio diprogrammazione lineare possono essereconsiderevoli. L'esplicitazione di un in-sieme reale di circostanze in termini diprogrammazione lineare - come pure laraccolta e l'organizzazione dei dati che ledescrivono - non è impresa da poco. Inol-tre la soluzione del problema è possibilesolo utilizzando un elaboratore veloce.

Tuttavia i benefici economici della pro-grammazione lineare sono spesso decisi-vi. Verso la metà degli anni cinquanta,allorché furono messi a punto dei metodidi programmazione lineare per coordina-re la miscelatura delle benzine, la ExxonCorporation cominciò a realizzare ri-sparmi dal 2 al 3 per cento sul costo delleoperazioni di miscelatura. L'applicazionesi estese presto nell'industria petrolchi-mica al controllo delle ulteriori operazio-ni di raffinazione, compresi il crackingcatalitico, la distillazione e la polimeriz-zazione. Press'a poco nello stesso periodoaltre industrie, e in particolare quella car-taria, quella della distribuzione degli ali-menti, l'agricoltura, le acciaierie e l'indu-stria metallurgica, incominciarono adadottare la programmazione lineare.Secondo una stima di Charles Boudryedella Linear Programming Inc., di SilverSpring, Maryland, i profitti di una cartierasono aumentati di 15 milioni di dollarigrazie all'applicazione della programma-zione lineare per determinare l'assorti-mento dei prodotti.

Oggi vengono offerti da una decina disocietà «pacchetti» di programmi perelaboratore basati sull'algoritmo del sim-plesso e circa 1000 clienti ne fanno uso sulicenza dei loro estensori. Ciascun clientepaga consistenti diritti mensili, sicché èprobabile che egli faccia uso del suddettometodo in modo regolare. Un numeromolto maggiore di organismi ha inveceaccesso ai «pacchetti» attraverso dei con-sulenti. Inoltre, sono stati messi a puntodei programmi specializzati per risolvereproblemi di flussi nelle reti, i quali posso-no fornire un servizio ancor più ampiodegli algoritmi generici di programma-zione lineare.

La vasta applicabilità della program-mazione lineare è riconoscibile anche inun singolo organismo. La Exxon, peresempio, applica correntemente la pro-grammazione lineare alla determinazionedei tempi nelle operazioni di trivellazio-ne, all'allocazione del grezzo alle diverseraffinerie, alla distribuzione dei prodotti ealla pianificazione delle strategie di mer-cato. David Smith, del Communicationand Computer Sciences Department del-la Exxon, riferisce che alla programma-zione lineare e alle sue estensioni è riser-vato il 5-10 per cento del carico totale dielaborazione della società. Negli ultimi20 anni tale quota ha tenuto il passo con le

applicazioni generali di elaborazione del-l'informazione in rapido sviluppo.

Sebbene il metodo del simplesso sia uno strumento molto potente, esso si basa

su idee elementari. Per meglio intendernealcune è utile esaminare un problema diallocazione dalla struttura particolare, lacosiddetta «applicazione di attribuzio-ne». Consideriamo il caso di una commis-sione per la progettazione di un'universi-tà, con tre edifici disponibili per il rinno-

cg

LU

LU

O

O

SI SOTTRAE 2

SI SOTTRAE 5

SI SOTTRAE 6

SI SOTTRAE 4

SI SOTTRAE 8

SI SOTTRAE 5

SI SOTTRAE 3

SI SOTTRAE 1

SI SOTTRAE 0

SI SOTTRAE 7

vamento strutturale e tre funzioni diversea cui essi debbono venire adibiti. Imma-giniamo che le funzioni siano quelle dilaboratorio, biblioteca e campi da tenniscoperti, per cui ogni edificio non può as-solvere più di una funzione. Le tavoledella pagina a fronte indicano il costo dirinnovamento delle nove possibili combi-nazioni funzione-edificio. In che modo lacommissione può minimizzare i costi dirinnovamento strutturale?

Il problema si può risolvere scegliendo

Convincere uno scettico che un'attribuzione è ottimale (illustrazione in alto, caselle in colore)non comporta la stima dei costi di tutte le attribuzioni ammissibili. In questo caso la matrice deicosti è 10 x 10, con conseguenti 10! ovvero 3 628 800 attribuzioni possibili. Sottraendo undeterminato numero da ciascuna entrata di una riga o di una colonna, lo si sottrae anche dal costototale di ogni possibile attribuzione, con il risultato di lasciare invariati i costi relativi. La ragione èche ciascuna attribuzione sceglie esattamente un numero dalla riga (o colonna) trasformata dellamatrice. L'insieme di numeri da sottrarre può essere scelto in modo che la matrice di partenza sitrasformi in una matrice senza entrate negative e con almeno un'entrata a costo nullo in ciascunariga o colonna (in basso). Dal momento che nessuna attribuzione può avere un costo totale minoredi zero, l'attribuzione ottimale per la matrice trasformata deve presentare un costo totale nullo.L'immediata conseguenza è che anche le corrispondenti entrate nella matrice di partenza sonoottimali. Per generare l'insieme di numeri da sottrarre sono stati escogitati algoritmi efficienti.

94

95

A O

B O

MAIS

SA + 158 n 480

A

LUPPOLO

4A + 48 160

La zona ammissibile nel problema del fabbricante di birra è formata dall'intersezione di cinquesemipiani. A ogni punto (A, B) del piano corrisponde un programma produttivo che richiede laproduzione di A barili di ale e B barili di birra. I primi tre semipiani rappresentano graficamentetutti i programmi produttivi realizzabili con gli ingredienti a disposizione. Ad esempio, il quanti-tativo di mais richiesto è SA + 15B (peso in libbre del mais necessario a produrre I barile di alemoltiplicato per A più il peso del mais necessario a produrre 1 barile di birra moltiplicato per B).Tale quantità non deve superare le 480 libbre di mais effettivamente disponibili per il fabbri-cante. Quindi, ogni punto del semipiano dominato dalla retta 5A + 15B = 480 rappresenta unpiano produttivo ammissibile che non richiede più di 480 libbre di mais. In modo analogo sipossono costruire i semipiani relativi al luppolo e al malto. Gli altri due semipiani esprimonoil fatto che sono ammissibili solo quei programmi che hanno una produzione non negativa.

V VALE

fatgerlì«MIRI14•••1"111

larea111<11•••111

niZatfiralIMEM

MENU

«figall/P«Mal@

TACISImriloW/

V VBIRRA

MAIS

LUPPOLO

MALTO D'ORZO480 LIBBRE

160 ONCE

1190 LIBBRE

5 LIBBRE DI MAIS

15 LIBBRE DI MAIS

4 ONCE DI LUPPOLO

4 ONCE DI LUPPOLO

35 LIBBRE DI MALTO

20 LIBBRE DI MALTO

VPROFITTO

PROFITTO13 DOLLARI

23 DOLLARI

COMBINAZIONEDI PRODOTTI

DI MASSIMO PROFITTO

Il dilemma del fabbricante di birra rappresenta un esempio di applicazione della programmazionelineare a problemi di ottimizzazione dello smistamento di risorse su diversi canali produttivi. Laproduzione di birra normale e di «ale» (una sorta di birra a più alta gradazione alcoolica assai diffusanegli Stati Uniti) è limitata dalla scarsità dei tre ingredienti essenziali: mais, luppolo e malto. I livel-li di produzione ammissibili sono determinati non solo dal quantitativo totale di ciascun ingredientedisponibile, ma anche dalle proporzioni richieste dai due prodotti. La funzione obiettivo, e cioè laquantità da ottimizzare, è il profitto del fabbricante di birra. Nella programmazione lineare sisuppone che tutte le risorse, i prodotti e i benefici siano quantità divisibili: il fabbricante può usa-re mezza libbra di mais, vendere un quarto di barile di ale e realizzare profitti proporzionali.

tre caselle nella tavola 3 x 3, e precisa-mente una per riga e una per colonna inmodo che a ciascun edificio venga asse-gnata una funzione e che tutte le funzionisiano coperte. La soluzione ottimale èquella che minimizza la somma dei costinelle caselle prescelte. La sua individua-zione non è difficile, dal momento che lealternative possibili sono poche. Una vol-ta infatti che sia stata segnata una dellecaselle della prima riga, nella seconda nerestano libere solo due. Nella terza, poi, lascelta è forzata, dal momento che rimaneuna sola casella nella colonna non ancorasegnata. Vi sono perciò 3 x 2 x I , ovverosei modi possibili di operare l'attribuzio-ne. È facile enumerare tutte e sei le possi-bilità, valutare il costo totale di ciascuna eprescegliere l'attribuzione economica-mente più vantaggiosa.

Questo approccio enumerativo, se ri-solve il problema di una matrice 3 x 3,diventa invece impraticabile per problemidi dimensioni maggiori. Nel caso di 4 edi-fici e 4 diverse funzioni, il numero dellepossibili attribuzioni è4 x3 x 2 x 1, cioè24. Nell'enunciazione generalizzata delproblema vi sono n edifici e n funzioni,mentre il numero delle attribuzioni è nfattoriale (scritto n!), e cioè n moltipli-cato per tutti gli interi da 1 a n-1. Così,per n = 10 vi saranno 10!, ovvero piùdi 3,6 milioni di attribuzioni differenti.

La rapida crescita di n! dissipa qualsiasientusiasmo per il metodo enumerativo.Immaginiamo di dover risolvere median-te enumerazione un'applicazione di attri-buzione 35 x 35 e di avere un elaboratorecapace di scegliere fra le attribuzioni pos-sibili, valutare il costo di ciascuna e con-frontarla con l'attribuzione con il costopiù basso fino a quel momento, il tutto alritmo di un miliardo di attribuzioni al se-condo (un elaboratore in grado di funzio-nare a tale velocità sarebbe molto più ra-pido di quelli attualmente disponibili).Anche se il compito di enumerare le 35!attribuzioni fosse suddiviso su un miliar-do di elaboratori di questo tipo, dopo unmiliardo di anni potrebbe essere comple-tata solo una frazione insignificante deicalcoli necessari.

L'applicazione di attribuzione 35 x 35non è particolarmente grande. Se si trattadi assegnare del personale a diverse man-sioni per minimizzare il costo totale del-l'addestramento professionale, n può fa-cilmente essere uguale a 35. Ma vi sonomolte applicazioni di attribuzione in cui nè uguale a 1000 e più. Problemi di questotipo richiedono un procedimento più«astuto» della semplice enumerazione.

T l peso dell'enumerazione verrebbegrandemente ridotto se si potesse evi-

tare di passare in rassegna le attribuzioniche comportano costi maggiori di quellegià controllate. Ciò sarebbe possibile se vifossero una regola di arresto o un criteriodi ottimalità capaci di individuare rapi-damente e di primo acchito le attribuzionidi ottimo. Un algoritmo che incorporasseun criterio del genere offrirebbe significa-tivi benefici collaterali. I benefici si pos-sono riassumere in quello che Jack Ed-

monds, della Università di Waterloo, nel-l'Ontario, chiama «il principio del super-visore assoluto» e che si potrebbe anchechiamare dello «scetticismo del capo».

Immaginate, dopo noiose enumerazio-ni, di aver risolto l'applicazione di attri-buzione 10 x 10, indicata nell'illustrazio-ne in alto della pagina 95, passando inrassegna tutte le 3 628 800 possibili at-tribuzioni. L'attribuzione di ottimo è,secondo voi, quella segnata in colorenella figura. Presentate soddisfatti la so-luzione al vostro capo, il quale vi guardabene negli occhi, tira una boccata dalsigaro e vi domanda a bruciapelo: «Ma èproprio sicuro che non ci sia una soluzio-ne più conveniente?». Avete un bel de-glutire, visto che l'unico modo di mostra-re i meriti della vostra soluzione sembraproprio essere quello di ripetere al capo loscrutinio di tutte le 3 628 800 possibilità.

Una regola di arresto è capace di offrireuna concisa dimostrazione di ottimalità.Immaginate di presentarvi dal vostrocapo non solo con un'attribuzione di ot-timo, ma anche con un insieme di numerida sottrarre alle entrate di ciascuna riga ecolonna. Spiegare il modo in cui questinumeri sono ottenuti richiederebbe unadiscussione particolareggiata dell'appli-cazione di attribuzione; basterà specifica-re che l'insieme dei numeri può essereindividuato mediante un algoritmo effi-ciente su un elaboratore. La loro utilità,una volta individuati, appare subito evi-dente. Si osservi che sottrarre lo stessonumero da ciascuna entrata di una riga ocolonna date equivale a sottrarlo dal co-sto totale di ogni possibile attribuzione; ilmotivo è che in ciascuna delle attribuzionipossibili si deve scegliere una, e una sola,entrata di ogni riga e colonna. Se, adesempio, si sottrae 5 a tutte le entratedella sesta riga, tutte le attribuzioni possi-bili conteranno esattamente un'entrata di5 punti minore della relativa attribuzionefatta con l'insieme iniziale dei costi. I costirelativi di tutte le attribuzioni possibilirimarranno pertanto immutati. Tale sot-trazione può essere ripetuta purché siasempre applicata uniformemente a cia-scuna entrata di una data riga o colonna.

Tramite sottrazione iterata è possibiletrasformare la matrice iniziale dei costi nel-la matrice illustrata nella figura in basso apagina 97. Questo insieme di costi possie-de un'interessante proprietà. Potete cioèsegnalare al vostro capo che i costi corri-spondenti alle caselle scelte dalla vostraattribuzione sono tutti nulli e che nessunaentrata della matrice è negativa. Poiché lasomma dei costi segnalati dalla vostra at-tribuzione è nulla e non vi sono costi ne-gativi. non esistono possibili attribuzionia costi inferiori. In breve, avete dimostra-to al vostro capo, con poche migliaia dicalcoli anziché con decine di milioni, chenessuna attribuzione può essere menocostosa di quella da voi prescelta.

Per quanto non abbia dimostrato il

modo di risolvere un'applicazione diattribuzione o di trovare le costanti diriga o di colonna da sottrarre, il proble-ma dell'attribuzione illustra la necessità

di evitare l'enumerazione e la possibilitàdi farlo mediante una regola di arrestocapace di riconoscere una soluzione diottimo. Si tratta di caratteristiche struttu-rali degli algoritmi che si possono appli-care anche ai problemi di programma-zione lineare in generale.

Consideriamo di nuovo il caso del fab-bricante di birra i cui due prodotti, lo ale ela birra normale, sono fatti con diverseproporzioni di mais, luppolo e malto.Supponiamo che vi sia disponibilità im-mediata di 480 libbre di mais, 160 once dilievito e 1190 libbre di malto e che laproduzione sia limitata dalla scarsità diquei materiali. Altre risorse consumatenel processo produttivo, come l'acqua, illievito, la manodopera e l'energia, si sup-pone esistano in abbondanza: sebbenepossano con i loro costi condizionare leintenzioni del fabbricante a produrre aleo birra, non limitano comunque diretta-mente la capacità produttiva. Supponia-mo che la fabbricazione di ciascun barile

di ale richieda 5 libbre di mais, 4 oncedi luppolo e 35 libbre di malto. Suppo-niamo ancora che tutto lo ale e tutta labirra che si riesce a produrre possano es-sere venduti ai prezzi correnti, con unprofitto di 13 dollari per barile di ale e 23dollari per barile di birra.

La scarsità di mais, luppolo e maltolimita i livelli produttivi ammissibili. Così,per esempio, sebbene vi siano abbastanzaluppolo e malto per fabbricare più di 32barili di birra, la produzione di quest'ul-tima esaurirebbe la disponibilità di maisnon consentendo un'ulteriore produzionedi birra e impedendo del tutto quella diale. Un altro programma produttivoammissibile non prevede birra, ma solo34 barili di ale, esaurendo in tal modotutte le 1190 libbre di malto. La primaalternativa sembra da preferirsi alla se-conda. Il profitto realizzato dal primoprogramma è di 32 x 23, ovvero 736dollari contro i soli 34 x 13, ovvero 442dollari, del secondo programma.

96 97

PROBLEMINOTI DITIPO NP

-----'PROBLEMINOTI DI TIPO

NP-COMPLETO

PROBLEMINOTI DITIPO P

• C

Alla teoria della complessità computazionale è recentemente riuscito di far rientrare la program-mazione lineare nell'insieme P delle classi di problemi limitati da un polinomio. Questa attribu-zione, rappresentata dal punto A, è stata resa possibile dalla dimostrazione, proposta dal matema-tico L. G. Hatan, che un nuovo algoritmo per la programmazione lineare - il cosiddetto metododell'ellissoide - è limitato da un polinomio. La funzione polinomio di un numero n è una sommafinita di potenze di n, moltiplicate ciascuna per una costante. Si dice che una classe di problemi èlimitata da un polinomio se il numero di operazioni aritmetiche elementari necessarie a risolverequalsiasi problema della classe è limitato da una funzione polinomio di misura s esprimente ladimensione del problema. Prima del risultato di Haéan non si sapeva se per la programmazionelineare esistesse un algoritmo del genere (sebbene non vi fossero prove che non esistesse). Sisapeva che la programmazione lineare rientrava nell'insieme più ampio NP delle funzioni polino-miali non deterministiche (punto B), dove NP è l'insieme di classi di problemi per cui è agevolecontrollare l'ammissibilità di una soluzione proposta. Un secondo sottoinsieme diNP è il cosiddet-to insieme dei problemi NP-completi; se si dimostrasse che tutte le classi NP-complete diproblemi sono limitate da polinomi, si avrebbe che tutte le classi di NP sono contenute in P. Inun certo senso, i problemi NP- completi sono i più difficili fra quelli contenuti in NP (punto C).

A

Il valore della funzione obiettivo per ogni punto P della zona ammissibile può essere rappresenta-to graficamente dalla distanza Z (P) al di sopra o al di sotto di?. misurata sull'asse : (le distanzelungo l'asse: sono state tracciate a una scala differente da quella per !e distanze sul piano dellazona ammissibile). Si può pensare alla distanza Z (P) come a un punto dello spazio tridimensiona-le. Se la funzione è lineare, il grafico dei valori assunti dalla funzione lungo una retta compresanella zona ammissibile è anch'esso una retta (grafico in alto). Per ogni punto interno a tale zona,esiste una retta passante per? che interseca il contorno della zona in due punti, per esempio R eS(grafico in basso). Se il segmento di retta nello spazio che unisce Z(R) e Z (S ) non è parallelo alpiano della zona ammissibile, la funzione obiettivo deve assumere il valore massimo lungo ilsegmento a uno dei suoi estremi, per esempio Z (S), che corrisponde al punto S sullo spigolo dellazona ammissibile. Il grafico della funzione obiettivo lungo uno spigolo è una retta e assumeanch'esso il valore massimo a uno degli estremi, diciamo Z (D), che corrisponde a un vertice dellazona ammissibile. Vi è sempre un punto sullo spigolo che domina un punto interno dato, e c'èsempre un vertice che domina un punto lungo uno spigolo. Per trovare il valore massimo Z (M)della funzione obiettivo è necessario esaminare solo i vertici. Se la zona ammissibile è bidimen-sionale, la funzione obiettivo forma un piano la cui altezza massima è raggiunta in un vertice.

Esistono altri programmi produttivi mi-gliori di questi due. Così, 6 barili di ale e 30barili di birra sfruttano tutte le 480 libbre dimais, 154 delle 160 libbre di luppolo e 810delle 1190 libbre di malto, garantendo unprofitto di (6 x 13) + (30 x 23), ovvero 768dollari. Con altri programmi si ottengonoprofitti anche maggiori. In tal caso, l'enu-merazione di tutte le possibilità non è sol-tanto impraticabile, come nel caso dell'ap-plicazione di attribuzione; è addiritturaimpossibile. Vi è un numero infinito diprogrammi produttivi che risolvono il pro-blema del fabbricante di birra e ciascuno diessi va sotto il nome di soluzione ammissibi-le. Vi è fortunatamente solo un insiemelimitato di soluzioni ammissibili su cui vai lapena di soffermare l'attenzione, l'insiemedelle cosiddette «soluzioni estremali».

'importanza delle soluzioni estremali risulta evidente se si rappresenta gra-ficamente l'insieme di tutte le soluzioniammissibili come un insieme di punti delpiano, insieme che costituisce appunto lacosiddetta zona ammissibile. Indichiamocon A il numero di barili di ale fabbrica-ti secondo tutte le possibili strategie pro-duttive e con B il numero di barili dibirra. A e B sono note nella programma-zione lineare come variabili decisionali epossono essere associate alle coordinatedel piano. Tutti i punti del piano si posso-no indicare con una coppikdi coordinate(A, B), corrispondenti altresì a un partico-lare insieme di livelli produttivi.

Essendo impossibili dei livelli produttivicon valori negativi, si può immediatamenteconfinare la zona ammissibile al quadrantesuperiore destro del piano, dove A e B sonoentrambi non negativi. In che modo la scar-sità di malto influisce sulla produzione? Dalmomento che occorrono 35 libbre di maltoper ogni barile di ale e 20 libbre per ognibarile di birra, il quantitativo totale di maltonecessario a fabbricare A barili di ale e Bbarili di birra è 36A x 20B. Se vengonousate tutte le 1190 libbre di malto,35A X 20B = 1190. L'insieme dei punti (A,B) che soddisfano questa equazione formauna retta. Tutti i punti (A, B) che corri-spondono ai programmi produttivi che ri-chiedono più di 1190 libbre di malto giac-ciono da una parte della retta e quelli che nerichiedono di meno, dall'altra. Solo que-st'ultimo insieme e i punti situati effettiva-mente sulla retta sono ammissibili a causadelle scorte limitate di malto.

Analogamente, la scarsità di luppolo li-mita la zona ammissibile a un versante dellaretta 4A +4B = 160, mentre la scarsità dimais limita tale zona a un versante dellaretta 5A + 15B =480.1 punti che soddisfa-no tutte queste condizioni formano la zonaammissibile (si veda la illustrazione nellapagina precedente). Si osservi che la zonaammissibile è convessa: tutti i segmenti diretta che uniscono due dei suoi punti (com-presi i punti del perimetro) sono interamen-te contenuti nella zona stessa.

Dal momento che il profitto del fabbri-cante di birra è di 13 dollari per ognibarile di ale e di 23 dollari per ogni bariledi birra, il suo problema è quello di mas-simizzare il profitto totale: 13A +24B. A

tale scopo egli deve trovare un punto (A,B) della zona ammissibile convessa in cui13A + 23B presenti un valore di massimo.Nella programmazione lineare una talemisura dei benefici da massimizzare (o,qualche volta, dei costi da minimizzare)viene chiamata «funzione obiettivo».

La funzione obiettivo può essere incor-porata nel grafico della zona ammissibileaggiungendo una terza dimensione. Perciascun punto (A, B) che rappresenta unprogramma produttivo, il profitto atteso èdato dall'altezza della funzione 13A +238al di sopra del piano in quel punto. Ilcompito che aspetta il fabbricante è ov-viamente quello di individuare un puntodella zona ammissibile in cui la funzioneobiettivo raggiunga la sua massima altez-za sul piano. Se si dovesse calcolare talefunzione per tutti i punti, il compito nonsarebbe eseguibile; tuttavia le due pro-prietà distintive del problema, e cioè laconvessità della zona ammissibile e la li-nearità della funzione obiettivo, contri-buiscono a facilitare la ricerca.

Poiché la zona e convessa, ogni punto alsuo interno può fdr parte di un segmento diretta i cui estremi giacciono sul contornodella zona (di fatto, per un punto dato sipossono tracciare infiniti segmenti di retta;non importa quale viene scelto). Nello spa-zio che sovrasta ciascuno di questi segmentidi retta è possibile costruire un grafico dellafunzione obiettivo che dà il profitto di cia-scun punto del segmento. Poiché la funzio-ne obiettivo è lineare, il grafico sarà unaretta (si veda l'illustrazione nella pagina afronte). Il grafico della retta può essereparallelo al piano, nel qual caso tutte lestrategie produttive situate sul segmentoavranno lo stesso profitto. Se il grafico dellafunzione obiettivo che sovrasta il segmentonon è parallelo al piano, deve assumere unvalore massimo a uno degli estremi situatisul contorno della zona ammissibile. Diconseguenza, il massimo della funzioneobiettivo che sovrasta un tale segmentodeve essere raggiunto sempre in uno deipunti di intersezione del segmento con ilcontorno. Dal momento che la medesimaanalisi si può applicare a qualsiasi segmentodi retta della zona ammissibile, ne segue cheil massimo globale della funzione obiettivosi trova invariabilmente in un punto delcontorno della zona. Il fabbricante potràallora, nella sua ricerca del massimo profit-to, ignorare tutto l'interno della zona am-missibile e considerare solo quelle strategieproduttive che corrispondono ai punti delcontorno.

Con un analogo ragionamento è possibi-le fare un passo avanti nell'analisi. Se lazona ammissibile è un poligono, ciascunpunto del contorno giace su un segmento diretta i cui estremi sono due vertici del poli-gono. Un grafico della funzione obiettivoper tale segmento si può costruire nellostesso modo che per un segmento che inter-seca la zona. Anche qui il massimo si devetrovare a uno degli estremi (o ad ambedue,se la funzione obiettivo è costante e quindiparallela al piano). In tal modo un valore dimassimo della funzione obiettivo relativaall'intera zona ammissibile può essere indi-viduato fra i vertici. Il fabbricante deve solo

controllare, al massimo, il valore dellafunzione su tutti i vertici della zona am-missibile e scegliere quello che garantisceil profitto più alto. Può essere certo allorache nessun'altra strategia produttiva po-trebbe assicurare migliori profitti. Nell'e-sempio considerato qui vi sono cinquevertici. Quello nel punto (12,28), cherappresenta la produzione di 12 barili diale e di 28 barili di birra, garantisce unprofitto di (12 x 13) + (28 x 23), ovvero800 dollari. È questo il massimo profittoconseguibile dal fabbricante.

'inclusione di un ulteriore vincolo (per esempio una scarsità di lievito) nonaltererebbe in modo significativo l'inter-pretazione geometrica del problema delfabbricante di birra. Il poligono potrebbeavere semplicemente sei vertici anzichécinque. D'altra parte l'introduzione di unterzo prodotto modificherebbe il modellopiù in profondità, rendendolo tridimensio-nale. Le disuguaglianze in tre variabili cor-rispondono a semispazi definiti da pianinello spazio bidimensionale. La zona am-missibile non sarebbe più un poligono, maavrebbe l'aspetto di una gemma tagliata, unpolitopo tridimensionale le cui facce sonopoligoni. Al crescere del numero n dellevariabili di decisione, l'interpretazionegeometrica conserva la sua validità mentrediventa di più ardua visualizzazione il poli-topo n-dimensionale definito dalle interse-zioni di iperpiani (n- I )-dimensionali. I ver-tici conservano tuttavia la loro funzionespecifica e le loro posizioni si determinanomediante metodi algebrici che si sostitui-scono all'intuizione geometrica.

Sembrerebbe che, limitando la valuta-

zione della funzione obiettivo ai verticidella zona ammissibile, la soluzione diproblemi di programmazione linearemediante enumerazione debba diventarepiù accessibile. Resta tuttavia il fatto che,come nell'applicazione di attribuzione, ilnumero delle possibilità da enumerarecresce in maniera esplosiva. Un problemacon 35 variabili decisionali e 35 vincolisarebbe del tutto impossibile.

Il metodo del simplesso di Dantzigesamina, sì, i vertici, ma in modo seletti-vo. Nell'esempio del fabbricante di birrail metodo parte dal vertice situato nell'o-rigine (0,0): dal momento che qui la pro-duzione è nulla, anche il profitto è nullo.Seguendo verso l'esterno l'uno o l'altrodegli spigoli incidenti, si arriva a punti convalori di funzione obiettivo sempre mag-giori. Il metodo del simplesso sceglie unodi questi spigoli, ad esempio l'asse B, e losegue fino all'altra estremità, il vertice(0,32); qui il programma produttivo ri-chiede la fabbricazione di 32 barili di bir-ra e niente ale, per un profitto di 736dollari. A partire da questo vertice unospigolo incidente conduce a valori ancorasuperiori della funzione obiettivo. L'algo-ritmo del simplesso prosegue perciò finoal vertice (12,28) all'altra estremità dellospigolo, dove il profitto di 12 barili di aie edi 28 barili di birra è di 800 dollari. In(12,28) tutti gli spigoli incidenti condu-cono a posizioni sfavorevoli; l'algoritmopertanto si arresta con la dichiarazioneche il vertice (12,28) è ottimale.

In generale il metodo del simplesso sisposta lungo gli spigoli di un politopo daun vertice all'altro adiacente, continuan-do a innalzare il valore della funzione

98

99

(12,38, 27,88)

LUPPOLO(25,67, 14,58)'

Il metodo dell'ellissoide. come quello del simplesso, può essere interpretato geometricamente.Nel caso del problema del fabbricante di birra, esso parte da un grande cerchio E, di centro X edimensioni definite dai dati del problema, contenente la zona ammissibile. Si costruisce poi unasuccessione di ellissi minori contenenti ciascuna la soluzione ottimale. Dal momento che il centrodel cerchio è ammissibile, occorre che ciascuna delle ellissi via via costruite contenga tutti i puntidel cerchio la cui funzione obiettivo è almeno altrettanto grande che in X. La più piccola delleellissi che soddisfano questa condizione èF. Il centro di F, nel punto l', non è ammissibile. Quindi,l'algoritmo esige che la successiva ellisse G, centrata su Z, contenga tutti i punti diF che giaccionosul versante ammissibile del vincolo 4,4 + 411 = 160, già violato dal punto Y. Il procedimentocontinua tagliando l'ellisse in esame con un contorno della funzione obiettivo se il centrodell'ellisse è ammissibile; se non lo è. l'ellisse successiva circoscrive la parte di quella preceden-te che soddisfa un vincolo violato dal suo centro. Le aree delle ellissi si contraggono con una ra-pidità sufficiente ad assicurare la convergenza dei rispettivi centri su una soluzione ottimale.

La proprietà della convessità nella programmazione lineare stabilisce che per due punti qualsiasidella zona ammissibile un segmento di retta che li congiunga deve giacere dentro tale zona. La zo-na ammissibile sulla sinistra è convessa; quella a destra è un insieme di punti discreti. La convessi-tà assicura che ogni massimo locale di una funzione obiettivo lineare sia un massimo globale.

A A A

obiettivo. Il procedimento può partire daqualsiasi vertice e si ferma quando non visono più vertici adiacenti con valori dellafunzione obiettivo maggiori di quelli finoa quel momento raggiunti. Questa regoladi arresto è valida solo perché la zonaammissibile è convessa: la convessità ga-rantisce infatti che un vertice di massimolocale sia anche un vertice di massimo

globale. Per controllare se vi sia la possibi-lità di miglioramenti basta guardare solole immediate vicinanze di ciascun punto.

Come si fa a dire se uno spigolo cheparte da un vertice dato migliorerà il valo-re della funzione obiettivo? La chiaveconsiste nel concetto di «valore margina-le» attribuito a ciascuna risorsa in ognivertice del politopo ammissibile. Per mol-

ti problemi di programmazione linearepluridimensionali il metodo algebricocomunemente usato per scegliere un per-corso da vertice a vertice può essere com-preso solo se si comprende il significatodei valori marginali.

Nel vertice di massimo del problemadel fabbricante di birra vi sono 210 libbredi malto in eccesso, che rimangono inuti-lizzate nel programma produttivo rappre-sentato dal vertice suddetto. L'aggiunta ola sottrazione di mezzo chilo di malto dal-la disponibilità iniziale di 1190 libbre nonmodificherebbe il profitto conseguibile.Ma l'aggiunta di un'oncia di luppolo ren-derebbe possibile un aumento di 2 dollarinel profitto totale. Questo aumento èappunto il valore marginale del luppolonel vertice di massimo. Lo si può interpre-tare come il risultato di una «spinta» im-pressa alla retta del vincolo, che lo fa al-lontanare dall'origine per riflettere l'ulte-riore disponibilità di un'oncia di luppolo(si veda l'illustrazione nella pagina a fron-te). Analogamente, il valore marginaledel mais in questo vertice è di I dollaro.

T prezzi marginali hanno un'interpreta--L zione economica naturale. Se il fabbri-cante di birra potesse acquistare un'altraoncia di luppolo, il suo profitto aumente-rebbe di 2 dollari e, se il luppolo fossedisponibile a un prezzo inferiore ai 2 dol-lari per oncia, varrebbe la pena acquistar-ne. D'altra parte, se per tale quantità sipagassero più di 2 dollari, sarebbe piùconveniente per il fabbricante distogliereil luppolo dalla produzione e venderlo.Ciò non significa che l'acquisto o la vendi-ta del luppolo debba sempre continuare alprezzo di 2 dollari per oncia, ma per au-menti di circa 19 once o cali fino a 32 onceil prezzo di 2 dollari rimane nell'esempioil punto di pareggio economico.

I valori marginali sono qualche voltachiamati anche «prezzi ombra» o «prezzicontabili». Essi indicano di quanto cia-scuna risorsa scarsa contribuisce alla con-venienza economica di ciascun articolo inproduzione. Per esempio, 1 barile di alerichiede 5 libbre di mais con un prezzocontabile di 1 dollaro per libbra, 4 once diluppolo con un prezzo contabile di 2 dol-lari per oncia e 35 libbre di malto con unprezzo contabile nullo. Il prezzo contabiletotale dello ale è pari al profitto di 13dollari per barile.

Immaginiamo che venga proposta laproduzione di un nuovo articolo, la birraleggera. La fabbricazione di I barile dibirra leggera richiede 2 libbre di mais, 5once di luppolo e 24 libbre di malto.Quanto profitto per ettolitro si deve rica-vare dalla birra leggera in modo da giusti-ficare il dirottamento di risorse dalla pro-duzione di birra normale e di ale? Alladomanda rispondono i prezzi contabilidelle rispettive risorse. Il prezzo contabiletotale degli ingredienti della birra leggeraè (2 x 1 ) + (5 x 2) + (24 x 0), pari a 12dollari. Questa cifra misura il profitto chesi perderebbe distogliendo risorse dallafabbricazione della birra normale e delloale per produrre I barile di birra leggera.In tal modo, la produzione di birra legge-

ra sarebbe conveniente se garantisse unprofitto di almeno 12 dollari per barile.

La funzione dei prezzi marginali nel giu-dicare dell'opportunità di introdurre unnuovo prodotto può contribuire a spiegarein che modo il metodo del simplesso indivi-dui il percorso sui vertici del politopo capa-ce di aumentare il valore della funzioneobiettivo. Supponiamo che il vertice at-tualmente in esame sia quello in (0,32) nelproblema della fabbrica di birra. Innanzi-tutto si può determinare il prezzo marginaledi ciascuna risorsa nel caso di tale pro-gramma produttivo. Dal momento che inquesto punto il malto e il luppolo sono ineccesso, i loro valori marginali sono nulli. Ilmais, invece, scarseggia e di conseguenza ilsuo valore marginale è positivo. Poiché nelpunto (0,32) viene prodotta soltanto la bir-ra normale, il valore marginale degli ingre-dienti di 1 barile di birra deve essere ugualeal profitto legato alla birra, e cioè 23 dollari.Dal momento che solo il mais ha valoremarginale diverso da zero e che per 1 bariledi birra sono necessarie 15 libbre di mais, ilvalore marginale del mais è 23 dollari divisoper 15 libbre ovvero circa 1,53 dollari perlibbra.

Qual è il valore marginale degli ingre-dienti dello ale misurato nel vertice (0,32)?Se tale valore è inferiore al profitto ricava-bile dalla vendita di I barile di ale, il dirot-tamento di alcune risorse dalla produzionedi birra e quella di ale provocherà un au-mento nel profitto complessivo del fabbri-cante. Per fare I barile di ale occorrono 5libbre di mais. Di conseguenza, il valoremarginale degli ingredienti di 1 barile di aleè (23/15) x 5, ovvero circa 7,67 dollari perbarile. Come nell'esempio della birra leg-gera, il valore marginale rappresenta laperdita di profitto risultante dal dirotta-mento delle risorse dalla fabbricazione dibirra normale a quella di ale. Dal momentoche tale valore è minore di 13 dollari (pro-fitto atteso dalla vendita di ciascun barile diale), converrebbe fabbricare più ale diquanto non indichi il programma produtti-vo nel punto (0,32). Di fatto, mantenendocostante il consumo totale di mais e disto-gliendo il mais dalla birra allo ale, il fabbri-cante può aumentare il suo profitto per ognibarile di ale di 13 — 7,67 dollari, cioè 5,33

Aumenti marginali nella disponibilità di risor-se scarse alterano in modo prevedibile il po-tenziale profitto di un ipotetico fabbricante dibirra. Se si disponesse di un' altra libbra dimais, il profitto massimo crescerebbe di I dol-laro: tale modificazione della funzione obiet-tivo si riflette nello spostamento del verticemassimale della zona ammissibile dal punto incolore al circoletto in colore (grafico in alto).Se si disponesse di un'altra oncia di luppolo, ilProfitto massimale aumenterebbe di 2 dollari(grafico al centro). Una variazione nella di-sponibilità di malto non altererebbe invece ilprofitto conseguibile: il malto è già una risorsasovrabbondante (grafico in basso). Le varia-zioni del profitto associate alle variazioni didisponibilità di ciascuna risorsa son note con ilnome di «prezzi ombra» o «prezzi contabili».La loro funzione è di dirigere l'algoritmo daun vertice all'altro. Le variazioni marginalisono state esagerate per maggiore chiarezza.

100

101

FLUSSO RICHIESTOVERSO L'ESTERNO

1

FLUSSO RICHIESTOVERSO L INTERNO

A 8 C

6 1 2

7 6 5

6 2 4

X

Microsoft Ba,sic

argONOMIA CON 1.1r1IL CALCOLATORE LJUTASCABILE

I problemi a flusso di rete sono una classe particolare di problemi noticome problemi di programmazione a numeri interi, ai quali si possonoapplicare le tecniche della programmazione lineare. In un problema diprogrammazione a numeri interi le variabili di decisione non sonodivisibili, ma possono assumere solo valori interi. In generale, questiproblemi si trovano nell'insieme degli NP- completi e sono perciò con-siderati difficili. Il costo di ciascun tratto della rete (diagramma in altoa sinistra) è dato da una matrice numerica. Si osservi che la matrice èidentica a una possibile matrice per un problema di attribuzione 3 x 3.

Le soluzioni dei problemi di attribuzione devono tuttavia essere espres-se in valori interi e non pare che i vincoli sul flusso di rete sianosufficienti a garantire tale risultato. Sono molti i flussi frazionari cherispondono ai vincoli (diagramma in alto a destra). Ciononostante, lesoluzioni estremali di problemi a flusso di rete trovate con metodi diprogrammazione lineare sono sempre espresse in valori non fraziona-ri, purché siano interi i valori dei flussi in arrivo e in partenza su ciascunnodo. Il problema dell'attribuzione può essere interpretato comeun caso speciale del problema a flusso di rete (diagramma in basso).

dollari. Essendo tenuto costante il quanti-tativo di mais, una maggiore produzione diale corrisponde a uno spostamento lungo lospigolo della zona ammissibile che rappre-senta il vincolo sulle scorte di mais. È esat-tamente questo il modo in cui il metodo delsimplesso riconosce la possibilità di miglio-rare la funzione obiettivo lungo uno spigo-lo. Qui lo spigolo collega il vertice (0,32) alvertice (12,28) del poligono.

Acche in problemi di programmazionelineare piuttosto modesti la zona

ammissibile può presentare un numeroenorme di vertici e vi è sempre la possibi-lità che il metodo del simplesso richiedaun numero enorme di iterazioni, cioè dimosse da vertice a vertice, per risolvere ilproblema. Di solito, tuttavia, la ricercaselettiva considera solo una frazione insi-gnificante del numero totale di vertici. Co-loro che risolvono regolarmente problemicon 2000±3000 vincoli sulle risorse a10 000 +15000 variabili decisionali consta-tano che l'operazione richiede solitamenteda pochi minuti a poche ore di funziona-mento di un potente elaboratore. Vor-remmo sapere qualcosa di più preciso sul-l'efficienza del metodo del simplesso.

Un sistema per convincere uno scetticodell'efficienza di un algoritmo è quello didare una certa garanzia sotto forma di unafunzione G e di un enunciato che affermi

che per un problema di dimensione d iltempo di esecuzione dell'algoritmo nonsupererà G(d). La dimensione d del pro-blema è una misura della quantità di infor-mazione (espressa sovente in termini dinumero delle cifre binarie) necessaria aspecificare i dati in entrata. È questa lacosiddetta «analisi dell'eventualità peggio-re», dove il valore della garanzia è definitodal problema di dimensione d più comples-so e difficile che l'algoritmo può esserechiamato a risolvere. Il tempo di esecuzionedell'algoritmo per la soluzione di un pro-blema di dimensione d dipende dalle carat-teristiche del particolare elaboratore im-piegato. Per rendere indipendente dal tipodi macchina usato la misura G(d), la fun-zione è solitamente espressa non in ore ominuti bensì in termini del massimo nume-ro di operazioni aritmetiche elementari(addizione, moltiplicazione e confronto)che devono essere eseguite dall'algoritmo.

Se G(d) è opportunamente piccola per ivalori di d che ci si aspetta di incontrare, sisarà inclini a riconoscere l'efficienza del-l'algoritmo proposto. Così, per esempio,Harold W. Kuhn della Princeton Univer-sity ha messo a punto un algoritmo perl'applicazione di attribuzione che richiedeal massimo cn 3 operazioni elementari perrisolvere un problema n per n, dove c èuna costante piccola. Quando n è pari a 2,3, 4 o 5, l'algoritmo può effettivamente

COSTO TOTALE

= (1/2 x 6) + (1/2 x 1) + (O x 2)

+ (1/2 x 7) + ( 1/3 x 6) + ( 1 /6 x 5)

+ (O x 6) + ( 1 /6 x 2) + (5/6 x 4)

= 131/2

CCOSTO TOTALE

= (O x 6) + (O x l) + (1 x2)

+ (1 x 7) + (O x 6) + (O x 5)

+ (O x 6) + (1 x 2) + (O x 4)

= 11

richiedere più tempo dell'enumerazione(per quanto con un elaboratore nessunodei due metodi richiederebbe più di unbatter di ciglio). Una volta che n cresca divalore, n! (che misura la dimensione del-l'enumerazione) supera molto rapida-mente cn 3 . In realtà n! cresce in manieratalmente esplosiva che nessun elaborato-re attualmente esistente sarebbe in gradodi portare a termine i calcoli. D'altra par-te, n 3 cresce con minore rapidità al cresce-re di n. Per n = 35 l'algoritmo di Kuhnpuò ancora risolvere il problema in unbatter d'occhio. Inoltre, al crescere di n da35 a 36, il peso dei calcoli per l'algoritmodi Kuhn cresce di un fattore di circa (36/35) 3 , ovvero approssimativamente 1,09.Il lavoro richiesto invece dall'enumera-zione crescerebbe di un fattore 36.

C oloro che operano nel settore deglielaboratori sono particolarmente

interessati agli algoritmi che vanno sottoil nome di «algoritmi limitati da un poli-nomio», nei quali cioè la funzione G è unafunzione polinomiale di d. Una funzionepolinomiale di d è una somma di più ter-mini, in ciascuno dei quali d è elevato auna potenza costante e moltiplicato perun coefficiente costante. Se d è sufficien-temente grande, qualsiasi algoritmo la cuigaranzia dell'eventualità peggiore crescacome d! o come una funzione esponenzia-

le di d, ad esempio 2 1, procederà conmaggiore lentezza di uno limitato da unpolinomio. Di conseguenza, coloro chelavorano con gli elaboratori consideranola proprietà di essere limitato da un poli-nomio un criterio teorico per valutarel'efficienza di un algoritmo.

Dal momento che il metodo del simples-so funziona molto bene nella pratica, si ètentati di pensare che si tratti di un algorit-mo limitato da un polinomio. Di fatto, si ètrovato nella pratica che una buona regolaempirica approssimativa è che il numerodelle iterazioni mediante criterio del sim-plesso cresce in funzione lineare del nume-ro dei vincoli. Negli impieghi abituali, tut-tavia, il metodo del simplesso non è limitatoda polinomi. Victor La Rue Klee, Jr., dellaUniversità di Washington, e George J. Min-ty, Jr., della Indiana University, hanno co-struito una famiglia infinita di problemi diprogrammazione lineare in cui il metododel simplesso è sostanzialmente inadeguatoal pari dell'enumerazione.

Che un algoritmo così valido nella praticapossa essere considerato tutt'altro che effi-ciente in teoria può apparire strano. Inrealtà non bisogna dimenticare che il crite-rio teorico esamina i risultati dell'eventuali-tà peggiore. Nella pratica non sembra che,almeno fino a oggi, si presentino esempicome quelli costruiti da Klee e Minty cheprovocano un cattivo funzionamento delmetodo del simplesso. Per spiegare la di-vergenza fra l'esperienza pratica con ilmetodo del simplesso e la sua prestazionenell'eventualità peggiore, i ricercatori han-no tentato di dimostrare che in un certosenso probabilistico gli esempi cattivi sonodavvero «patologici». Tuttavia, nonostan-te gli interessanti risultati in questa direzio-ne riferiti recentemente da Dantzig, la di-mostrazione si scontra con difficoltà consi-derevoli.

Vi è una certa flessibilità nel modo in cui ilmetodo del simplesso sceglie a ogni itera-zione fra più vertici adiacenti, quando ognivertice sembrerebbe migliorare il valoredella funzione obiettivo. La costruzione diKlee-Minty mostra che una strategia moltodiffusa conduce a risultati non polinomiali.Altri ricercatori hanno a tutt'oggi costruitoesempi analoghi per altre strategie. Non sisa tuttavia se esista una realizzazione delmetodo del simplesso che sia limitata da unpolinomio. Fino a poco„tempo fa non sisapeva ancora se esistesse un algoritmolimitato da un polinomio per la program-mazione lineare; era un problema irrisoltodi grande interesse teorico. Infine L. G.Ha'éan dell'Accademia delle scienze del-l'URSS ha mostrato che un algoritmo mes-so a punto da tre altri matematici sovietici,N. Z. 8or, D. B. Judin e A. S. Nemirovskij,poteva essere realizzato in tempo polino-miale.

Dal momento che il lavoro di or, Judine Nem irovskij non pone condizioni di linea-rità, il nuovo algoritmo differisce notevol-mente dal metodo del simplesso. Si trattadel cosiddetto metodo dell'ellissoide. Ilpunto di partenza è dato da un grandeellissoide centrato nell'origine. Più in gene-rale, l'ellissoide di partenza è una sfera conun raggio abbastanza grande da contenere

sicuramente la soluzione di ottimo. L'algo-ritmo passa a costruire progressivamenteellissoidi sempre più piccoli, ciascuno deiquali è tale da contenere la soluzione diottimo. Il volume degli ellissoidi che via viasi succedono si contrae abbastanza in frettada garantire la convergenza dei rispettivicentri sulla soluzione di ottimo. Non è ne-cessario, per usare l'algoritmo, disegnaregli ellissoidi; semplici formule ricorsive ba-stano a descriverli. Se si considera il lavoronecessario a costruire ciascun ellissoide apartire da quello che l'ha preceduto, il limi-te al numero complessivo delle operazioni èdell'ordine di (m +n)n 61, dove m è il numerodei vincoli, n quello delle variabili decisio-nali e I il logaritmo in base 2 del coefficientepiù grande che figura nei dati del problema.

Tale espressione è un limite polinomia-le, ma, come qualsiasi altro limite di que-sto tipo, può crescere ancora di molto pervalori grandi di m, n e 1. È possibile che ilmetodo dell'ellissoide, come quello delsimplesso, dia migliori risultati nella pra-tica di quanto non lasci pensare il suolimite peggiore? I risultati preliminarinon sono incoraggianti. Le prove di calco-lo hanno finora mostrato una convergen-za estremamente lenta per il metodo del-l'ellissoide. Vi sono inoltre delle famiglieassai semplici di problemi che possono farfunzionare il metodo sui tempi lunghiprevisti dal limite. Ciò contrasta con laforma complessa dei problemi costruitiper sconfiggere il metodo del simplesso.

Un'altra difficoltà rilevante del metododell'ellissoide riguarda le condizioni dimemoria. I problemi di programmazionelineare molto grandi tendono nella prati-ca a presentare una struttura diradata: laproporzione di coefficienti diversi da zeronei dati è di solito piuttosto piccola. Èpossibile utilizzare il metodo del simples-so in modo da conservare questa strutturarada mentre i dati vengono elaborati nelcorso dello svolgimento dell'algoritmo. Sitratta di una proprietà decisiva, dal mo-mento che basta immagazzinare nell'ela-borazione i soli coefficienti non nulli. In-vece, non sembra possibile sfruttare nelmetodo dell'ellissoide questa proprietà.

Sebbene deboli appaiano fino a questomomento le prospettive di un impiegopratico del metodo dell'ellissoide, biso-gna ancora vedere quali saranno i suoisviluppi. Nel breve tempo trascorso dopola nota di Haèan molto lavoro è statofatto, con alcuni miglioramenti sostanzia-li. Tuttavia le difficoltà qui sottolineateappaiono davvero molto temibili.

T a programmazione lineare è uno stru-1 mento pratico di grande interesseteorico. Per il matematico rappresentauna teoria delle disequazioni lineari, ecioè un elegante contrappunto alla teoriaclassica delle equazioni lineari. Per leamministrazioni pubbliche e private co-stituisce un valido aiuto nella gestione alivello decisionale e per la programma-zione a lungo raggio. Probabilmente laconseguenza più importante dell'exploitteorico di Haéan sarà l'aumento di inte-resse per gli aspetti pratici e per quelliteorici della programmazione lineare.

franco muzzioeditore

annuncia l'uscitanelle migliori librerie

delle seguentinovità

"il piacere del computer"

"manuali scientifici"

"le scienze dell'artificiale"

via bonporti 36, 35100 padova, tel. 049/661147

A

6 1 2

7 6 5

6 2 4

102 103