AppuntidiRicercaOperativa2006/2007PrefazioneLaRicercaOperativa `euncampoincontinuaevoluzione,ilcuiimpattosullerealt` aaziendaliedorganizzative`eincostantecrescita. Linsegnamen-todi questadisciplina, edinparticolare delle suebasi metodologiche edalgoritmiche, `equindi indispensabilenei corsi chemiranoaformaremoltegure conelevatecapacit` atecnologicheemanageriali,adesempiomanonsolamenteneicorsidiLaureainInformatica,Ingegneriaematerieani.Questedispensesonostatesviluppatedal Gruppodi RicercaOperati-vadel Dipartimentodi InformaticadellUniversit` adi Pisaperil supportoadiversi corsi allinternodellaFacolt`adi ScienzeMatematiche, FisicheeNaturalidellastessaUniversit` a,qualiiCorsidiLaureainInformaticaeinInformaticaApplicataei Corsi di LaureaSpecialisticainInformaticaeinTecnologieInformatiche. Inoltre, ledispensesonoadottateancheinCorsidiLaureadialtreUniversit` aitaliane.Questedispensesonoil fruttodi unlavorocollettivo, svoltonel corsodi molti anni dadiversepersone, informeeruoli diversi. Inparticolare,hannocollaboratoallastesuradiquestodocumentoGiorgioGallo, StefanoPallottino, MariaGraziaScutell` a, AntonioFrangioni eGiancarloBigi. Unaiutoparticolareallastesuraealmiglioramentodelledispense `estatodatodaPaolaCappaneraeMariaPaolaScaparra. Moltealtrepersone, tracuimoltistudentideicorsidiRicercaOperativaallinternodeicorsidiLaureaediLaureaSpecialisticadellaClassediInformaticadellUniversit` adiPisa,hannocontributoaquestedispensesegnalandoerrori esuggerendomiglio-ramenti. Atutti lorovail ringraziamentodegli estensori. Ogni erroreedimprecisionerimastanel testo`eesclusivamenteresponsabilit`adegli autori;segnalazioniatalpropositosonocaldamentebenvenute.Lutilizzodi questomaterialeincorsi di studiodiversi daquelli tenutidagliestensorideldocumento`epermessoedincoraggiato, acondizionechesia opportunamente citatala fonte,che non venga tratto protto dal fornireilmaterialeaglistudenti,echetaleutilizzovengasegnalatoagliautori. Lamodalit` adidistribuzioneconsigliata`equelladifareriferimentoallapaginaWebdeiCorsidiRicercaOperativapressoilDipartimentodiInformaticahttp://www.di.unipi.it/optimize/Courses/courses.htmlincui si trovalaversioneaggiornatadel testo, insiemeadaltromaterialechepu` orisultareutileperglistudenti.Indice1 Problemi eModelli 11.1 Problemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Modelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.1 ProgrammazioneLineare . . . . . . . . . . . . . . . . 91.2.2 Variabililogiche . . . . . . . . . . . . . . . . . . . . . 141.2.3 Relazionibinarie . . . . . . . . . . . . . . . . . . . . . 191.2.4 Vincolidiassegnamentoesemiassegnamento . . . . . 221.2.5 Selezionedisottoinsiemi . . . . . . . . . . . . . . . . . 281.2.6 Variabiliavaloridiscreti. . . . . . . . . . . . . . . . . 311.2.7 Minimaquantit`apositivapressata . . . . . . . . . . . 351.2.8 Funzioneconcaricosso. . . . . . . . . . . . . . . . . 361.2.9 Vincolidisoglia . . . . . . . . . . . . . . . . . . . . . 371.2.10 Comerappresentareilvaloreassoluto . . . . . . . . . 391.2.11 Funzionilineariatratti . . . . . . . . . . . . . . . . . 411.2.12 Vincolidisgiuntivi . . . . . . . . . . . . . . . . . . . . 451.2.13 Unesempiodiformulazioneealcuniesercizi . . . . . . 472 Graeretidiusso 552.1 Flussisureti . . . . . . . . . . . . . . . . . . . . . . . . . . . 552.1.1 Alcunimodellidiusso . . . . . . . . . . . . . . . . . 582.1.2 Trasformazioniequivalenti . . . . . . . . . . . . . . . . 602.2 Visitadiungrafo. . . . . . . . . . . . . . . . . . . . . . . . . 632.2.1 Implementazionidellaproceduradivisita . . . . . . . 642.2.2 Usidellaproceduradivisita. . . . . . . . . . . . . . . 662.3 Camminidicostominimo . . . . . . . . . . . . . . . . . . . . 692.3.1 Ilproblema . . . . . . . . . . . . . . . . . . . . . . . . 702.3.2 Alberi,etichetteecondizionidiottimo. . . . . . . . . 722.3.3 LalgoritmoSPT . . . . . . . . . . . . . . . . . . . . . 742.3.4 Algoritmiacodadipriorit`a . . . . . . . . . . . . . . . 782.3.5 Algoritmiaselezionesulista . . . . . . . . . . . . . . 822.3.6 Camminiminimisugraaciclici . . . . . . . . . . . . 852.3.7 Camminiminimiconradicimultiple . . . . . . . . . . 862.4 Alberodicoperturadicostominimo . . . . . . . . . . . . . . 87iiiiv INDICE2.4.1 AlgoritmodiKruskal . . . . . . . . . . . . . . . . . . . 892.4.2 AlgoritmodiPrim . . . . . . . . . . . . . . . . . . . . 912.4.3 Alberodicoperturabottleneck . . . . . . . . . . . . . 932.5 Ilproblemadiussomassimo . . . . . . . . . . . . . . . . . . 952.5.1 Tagli,camminiaumentantiecondizionidiottimo. . . 962.5.2 Algoritmopercamminiaumentanti. . . . . . . . . . . 992.5.3 Algoritmobasatosupreussi . . . . . . . . . . . . . . 1032.5.4 Flussomassimoconpi` usorgenti/pozzi . . . . . . . . . 1082.6 Ilproblemadiussodicostominimo. . . . . . . . . . . . . . 1092.6.1 Cammini,cicliaumentantiecondizionidiottimo . . . 1102.6.2 Algoritmobasatosucamminiminimisuccessivi . . . . 1132.6.3 Algoritmobasatosucancellazionedicicli . . . . . . . 1172.6.4 Basidicicli . . . . . . . . . . . . . . . . . . . . . . . . 1192.7 Problemidiaccoppiamento . . . . . . . . . . . . . . . . . . . 1212.7.1 Accoppiamentodimassimacardinalit`a. . . . . . . . . 1222.7.2 Assegnamentodicostominimo . . . . . . . . . . . . . 1252.7.3 Accoppiamentodimassimacardinalit`abottleneck . . 1283 ProgrammazioneLineare 1333.1 ProblemidiProgrammazioneLineare . . . . . . . . . . . . . . 1333.1.1 GeometriadellaProgrammazioneLineare . . . . . . . 1383.2 TeoriaMatematicadellaDualit`a . . . . . . . . . . . . . . . . 1493.2.1 Coppiediproblemiduali . . . . . . . . . . . . . . . . 1493.2.2 Ilteoremadeboledelladualit` a . . . . . . . . . . . . . 1543.2.3 Ilteoremafortedelladualit` aesueconseguenze . . . . 1553.2.4 Ilteoremadegliscarticomplementari . . . . . . . . . 1593.2.5 Soluzionicomplementariebasi . . . . . . . . . . . . . 1653.3 AlgoritmidelSimplesso . . . . . . . . . . . . . . . . . . . . . 1703.3.1 LalgoritmodelSimplessoPrimale . . . . . . . . . . . 1703.3.2 LalgoritmodelSimplessoDuale . . . . . . . . . . . . 1853.3.3 Analisipost-ottimale. . . . . . . . . . . . . . . . . . . 1934 OttimizzazioneCombinatoria 2014.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2014.2 ProgrammazioneLineareIntera(Mista) . . . . . . . . . . . . 2034.2.1 Ilrilassamentocontinuo . . . . . . . . . . . . . . . . . 2044.2.2 FormulazionidiPLequivalentiperlaPLI . . . . . . . 2064.2.3 Diseguaglianzevalide . . . . . . . . . . . . . . . . . . . 2084.3 Dimostrazionidiottimalit` a . . . . . . . . . . . . . . . . . . . 2105 Algoritmi euristici 2135.1 Algoritmigreedy . . . . . . . . . . . . . . . . . . . . . . . . . 2145.1.1 Esempidialgoritmigreedy . . . . . . . . . . . . . . . 2155.1.2 Algoritmigreedycongaranziasulleprestazioni . . . . 224INDICE v5.1.3 Matroidi. . . . . . . . . . . . . . . . . . . . . . . . . . 2365.2 Algoritmidiricercalocale . . . . . . . . . . . . . . . . . . . . 2425.2.1 Esempidialgoritmidiricercalocale . . . . . . . . . . 2445.2.2 Intornidigrandedimensione . . . . . . . . . . . . . . 2555.2.3 Metaeuristiche . . . . . . . . . . . . . . . . . . . . . . 2586 Tecnichedirilassamento 2736.1 Rilassamentocontinuo . . . . . . . . . . . . . . . . . . . . . . 2756.1.1 Ecaciadelrilassamentocontinuo . . . . . . . . . . . 2766.1.2 Informazionegeneratadalrilassamentocontinuo . . . 2806.2 Eliminazionedivincoli . . . . . . . . . . . . . . . . . . . . . . 2846.2.1 Esempidirilassamentipereliminazionedivincoli . . . 2856.3 RilassamentoLagrangiano . . . . . . . . . . . . . . . . . . . . 2916.3.1 TeoriadelrilassamentoLagrangiano . . . . . . . . . . 2946.3.2 AlgoritmiperilrilassamentoLagrangiano . . . . . . . 3006.3.3 InformazionegeneratadalrilassamentoLagrangiano . 3086.4 Rilassamentosurrogato . . . . . . . . . . . . . . . . . . . . . 3117 Algoritmienumerativi 3157.1 Algoritmidienumerazioneimplicita . . . . . . . . . . . . . . 3167.1.1 Unoschemagenerale. . . . . . . . . . . . . . . . . . . 3167.1.2 Implementareunalgoritmoenumerativo . . . . . . . . 3257.1.3 Esempidialgoritmienumerativi . . . . . . . . . . . . 3387.2 Programmazionedinamica. . . . . . . . . . . . . . . . . . . . 3487.3 Tecnichepoliedrali . . . . . . . . . . . . . . . . . . . . . . . . 348AAlgoritmiecomplessit`a 349A.1 Modellicomputazionali . . . . . . . . . . . . . . . . . . . . . 349A.2 Misuredicomplessit`a . . . . . . . . . . . . . . . . . . . . . . 350A.3 Problemitrattabilieproblemiintrattabili . . . . . . . . . . . 351A.3.1 LeclassiPeNP. . . . . . . . . . . . . . . . . . . . . 351A.3.2 ProblemiNP-completieproblemiNP-ardui . . . . . 352A.3.3 Complessit`aedapprossimazione . . . . . . . . . . . . 353BGraeReti 355B.1 Igra: notazioneenomenclatura . . . . . . . . . . . . . . . . 355B.1.1 Gra,nodi,archi . . . . . . . . . . . . . . . . . . . . . 355B.1.2 Cammini,cicli . . . . . . . . . . . . . . . . . . . . . . 357B.1.3 Taglieconnettivit`a . . . . . . . . . . . . . . . . . . . 358B.1.4 Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . 359B.2 Rappresentazionedigraedalberi . . . . . . . . . . . . . . . 361B.2.1 Matricidiincidenzaelistediadiacenza . . . . . . . . 362B.2.2 Rappresentazionedialberi: lafunzionepredecessore . 364B.2.3 Visitediunalbero . . . . . . . . . . . . . . . . . . . . 364vi INDICEB.2.4 Livellodeinodidiunalbero . . . . . . . . . . . . . . . 365Capitolo1ProblemieModelliLa RicercaOperativaha comeoggettolo studio e la messa a punto di meto-dologie per la soluzione di problemi decisionali. I problemi arontati nellam-bito della Ricerca Operativa sono tipicamentequelli in cui bisogna prenderedecisioni sulluso di risorse disponibili in quantit`a limitata in modo da rispet-tare un insieme assegnatodi vincoli,massimizzando il benecio ottenibiledallusodellerisorsestesse.Unprocesso decisionale pu` o, inmodoschematico, essere decompostonelleseguentifasi:1) individuazionedelproblema;2) analisidellarealt` aeraccoltadeidati;3) costruzionedelmodello;4) determinazionediunaopi` usoluzioni;5) analisideirisultatiottenuti.Questi punti nonvannovisti comestrettamentesequenziali; inunproces-sodecisionale reale`e infatti frequente il casoche unadelle fasi richiedamodichedei risultati ottenuti inunafaseprecedente. Adesempio, nellacostruzionedelmodellopu` oemergerelesigenzadinuovidatiinaggiuntaaquelliraccoltinellafaseprecedente. Lastessaraccoltadeidatipresupponeunideasultipodi modellochesar` acostruito. Nellosvolgimentodel corsoconcentreremolattenzionesui punti (3)e(4), chepi` usi prestanoadunarigorosatrattazionematematica, edai quali sonodirettegranpartedellemetodologiemesseapuntonellambitodellaRicercaOperativa.Ilmodello`eunadescrizione,ingeneralepermezzodistrumentiditipologico-matematico, dellaporzionedi realt` adi interesseai ni del processodecisionale. Ricordiamoquitreclassi principalidimodelli: giochi, modellidisimulazione,modellianalitici.12 CAPITOLO1. PROBLEMIEMODELLI Neigiochi,la dicolt` adi modellare inmodo matematicoilcomporta-mento degli individui o dei gruppi di individui presenti nella realt` a sot-to esame viene superata introducendo direttamente luomo nel modelloattraversoigiocatori,aciascunodeiqualivieneadatounpressatoruolo. Nei modelli di simulazione si cercadi descriverenel modopi` uaccu-ratopossibileilcomportamentodel sistemachesi vuolestudiarepermezzodirelazionimatematiche; quindisistudiasucalcolatorelasuarisposta a sollecitazioniche vengonorealizzate,in genere per mezzodigeneratoridi numeri pseudo casuali,in modo che siano il pi` u possibilesimiliaquellereali. Nei modellianalitici invece tutto il sistema sotto esame `e descritto permezzo di relazioni matematiche(o logiche) tra variabili che rappresen-tanoglielementidel sistema;quindi si cercanovaloriper talivariabiliche soddisno i vincoli e che massimizzino o minimizzino una funzioneobiettivoopportunamentedenita.AllaSimulazione`ededicatoun corsospecialistico. Inquesto corso,comeinaltri corsi dellareadi RicercaOperativa, restringeremolanostraatten-zioneaimodellianalitici: inparticolare,imodellichestudieremoinquestocorsorientranoinquellapartedellaRicercaOperativachevasottoilnomediProgrammazioneMatematica.Nellanalizzarelarealt` aper mezzodi modellinonvamaidimenticatoloscarto esistente tra la realt` a stessa ed il modello: la soluzione di un problema`e in realt` a sempre la soluzione della rappresentazione che abbiamo costruitodel problema reale.`E sempre necessario prestare grande attenzione alla fon-datezzadel modello costruito: il modello sar` a sempre una descrizione moltolimitata della realt` a, ma dovr`a rappresentare con ragionevole accuratezza gliaspetticheinteressanoai ni dellasoluzionedel problema decisionalechesistaarontando.1.1 ProblemiDiamo adesso una serie di denizioni riguardanti i problemi di ottimizzazio-ne. Nel seguitoper problemaintenderemo una domanda espressa interminigenerali, la cui risposta dipende da un certo numero di parametri e variabili.Unproblemavieneusualmentedenitopermezzodi: unadescrizionedeisuoiparametri,ingeneralelasciatiindeterminati; unadescrizionedellepropriet`achedevonocaratterizzarelarispostaosoluzionedesiderata.1.1. PROBLEMI 3Unistanza di undatoproblema(P)`equellaparticolaredomandachesiottienespecicandovaloripertuttiiparametridi(P).Moltospesso unproblema vienedenito fornendo linsiemeFdellepos-sibilirisposteosoluzioni. Ditaleinsieme,dettoinsiemeammissibile,vienein generale data la struttura mediante i parametri da cui essa dipende; i suoielementivengonodettisoluzioni ammissibili. FrequentementeFvienespe-cicatoindicandouninsiemedisupporto F

talecheF F

,edulterioricondizioni(vincoli)cheglielementidiFdevonosoddisfare. Inquestocaso,siparlaspessodeglielementidiF

\ Fcomedisoluzioninonammissibili.Inunproblemadiottimizzazione, sullinsiemeammissibileFvienede-nitaunafunzioneobiettivoc : F Rchefornisceil costooil benecioassociatoadogni soluzione; lasoluzionedel problema`eunelementodi Fcherendeminima, oppuremassima, lafunzione obiettivo. Un generico problemadi minimopu` o essere scritto come(P) min { c(x) : x F}. (1.1)Sostituendominconmaxin(1.1)si ottieneunproblemadi massimo.Chiamiamoz(P) =min { c(x) : x F}il valoreottimodel problema. UnasoluzioneammissibilexFtalechec(x)=z(P)`edettasoluzioneottimaper(P). Unproblemadiottimizza-zionepu` oessereindierentementecodicatocomeproblemadi massimoodiminimo: infatti,`eimmediatovericarecheilproblema(P

) max { c(x) : x F},`eequivalente a(P), ossiaz(P)=z(P

); inoltre, i dueproblemi hannolostessoinsiemedisoluzioniottime.Esempio1.1: UnproblemadiequipartizioneIl problemadi equipartizionecorrispondeallaseguentedomanda: datouninsiemedi nnumerinaturali,N= {a1, a2, . . . , an},qual`eilsottoinsiemeSdiNtalecheladierenzainmodulotralasommadei numeri inSequelladei numeri inN\ S`elapi` upiccolapossibile?Unaformulazionematematicadelproblema`eminc(S) =XiSai Xi / Sai: S N. (1.2)In questo caso, F`e linsieme di tutti i sottoinsiemi di N; infatti, lunica condizione (vincolo)cheunarisposta(soluzione) devesoddisfare`edi essereunsottoinsiemedegli nnumeridati. Perquestoproblema, i parametri sonoil numeronegli nnumeri a1, a2, . . . , an;scegliendo adesempio n=4 e N={7, 3, 4, 6} si ottiene unaparticolare istanza delproblema, incuituttii parametri sonospecicati. Invece,S`elavariabiledelproblema:S= {3, 7} `eunasoluzioneottimaperlistanzaconsiderata,convaloreottimopariazero.Datounproblemadiottimizzazione(P),sonopossibiliquattrocasi:4 CAPITOLO1. PROBLEMIEMODELLI Il problema`evuoto, ossiaF=; inquestocasosi assumepercon-venzionez(P) = +(perunproblemadimassimo). Lesistenzadi problemi vuoti potrebbeatuttaprimaparereparadossale, maingenerale, comevedremo, non`efacilestabilireseuninsiemeFspeci-catoattraversounalistadi condizioni (vincoli)contengaoppurenoelementi. Il problema`e inferiormente illimitato (superiormente illimitato perunproblemadimassimo), ossiacomunquesceltounnumerorealeMesisteunasoluzioneammissibilexFtalechec(x)M(M); inquestocasoilvaloreottimo`ez(P) = (+). Il problemahavalore ottimo nito 0, lasoluzione xsi dice-ottima seR x. Unalgoritmoeu-ristico pu` oessere considerato buono se produce soluzioni conbassoerrorerelativoper tutte leistanzedi (P): unalgoritmoAsi dicequindi-approssimatose produce una soluzione -ottima per ogni istanza. Algorit-mi -approssimati con piccolo possono essere valide alternative interessantiaglialgoritmiesatti;perulterioriinformazionisiconsultilAppendiceA.Si noti che, ingenerale, z(p)non`enoto, percui calcolarelerrore(as-solutoorelativo)diunasoluzione x`enonbanale. Unmetodoperstimarez(p)`equellodi costruireunaqualcheapprossimazionedel problemadato,adesempiotenendoincontosolamentedi alcunedellecondizioni (vincoli)chelesoluzioni ammissibili devonosoddisfare. Inparticolare, si deniscerilassamentodi(1.1)qualsiasiproblema( P) min { c(x) : x F} (1.3)tale che F F e c(x) c(x) per ogni xF. Inaltre parole, ( P) `eunrilassamentodi (P)sehapi` usoluzionidi (P)e/oselasuafunzioneobiettivo`e unapprossimazioneinferiore dellafunzioneobiettivoc di (P)sullinsiemeF.`Eimmediatovericarecheil valoreottimodi ( P)fornisceunavalutazioneinferioredel valoreottimodi(P), ossiaz( P)z(P). Nelcasodi problemi di massimo, lasecondacondizione diventa c(x) c(x)perogni xF, edil rilassamentofornisceunavalutazione superiore delvaloreottimo.`Espessopossibiledenirei rilassamenti inmodochesiano1.2. MODELLI 7risolubili con algoritmi di complessit`a inferiore rispetto a quelli necessari perilproblemaoriginale;sivedailCapitolo6.Pu`oaccaderecherisolvereilrilassamentopermettadirisolverediretta-menteilproblemaoriginale; questocapitaselasoluzioneottimaxdi( P)soddisfalecondizioni xFe c(x) =c(x), ossia`eammissibileper ilproblemaoriginaleelafunzioneobiettivo chainxlostessovaloredellafunzione obiettivoreale c. In questo caso,infatti, `e immediato vericare chex`eanchesoluzioneottimaper(P),inquanto c(x) = z( P) z(P) c(x) = c(x).Quandoci`ononaccade, lavalutazioneinferiorez(P)elasoluzionexdelrilassamentopossonocomunqueessere sfruttateper risolvere il problema(P). Infatti,combinandoopportunamenteeuristicheerilassamenti`epossi-bilerealizzarealgoritmiesatti,anchesedicomplessit`aesponenzialealcasopessimo,permoltiproblemidiottimizzazione; sivedailCapitolo7.1.2 ModelliLa costruzione di un modello analitico di un sistema reale `e una delle attivit`api` ucreativeecertamentepi` uutilinellostudio disistemiorganizzativiege-stionali, nella progettazione industriale, nella descrizione di sistemi altamen-tecomplessi quali quelli informatici edinmoltealtrediscipline. Pertanto,gli strumenti per lacostruzionedi modelli rappresentanounacomponen-teessenzialenel curriculumdellinformatico, enonsoltantoinquellodellospecialistadiRicercaOperativa.Inquantoattivit`acreativa, lacostruzionedi modelli nonpu` oadarsisolamenteallusodi tecnichestandard; nonesistonocio`emetodologiefor-mali ingradodicostruireautomaticamenteunmodelloanalitico, ancheseesistonotecnichee strumenti softwarein gradodi facilitareedautomatizza-realcunefasidelprocessodimodellazione. Lacostruzionediunmodello`ecomunquelasciatafondamentalmenteallafantasia, allacreativit`aedalle-sperienza del singolo,il quale pu` o certamente fare riferimento ai modelli chehaincontratoprecedentementecercandodiadattarli ovepossibile, mapu` oanchetrovarsinellanecessit`adicrearnediinteramentenuovi.Nellacostruzionedimodelli(ingenerale,edinparticolarediottimizza-zione)`esemprepresentelanecessit`adi bilanciareaccuratamentedueesi-genzecontrastanti: daunaparteil modellodeveesseresignicativo, ossiarappresentareinmanierasucientementeaccuratalarealt` a, madallaltradeve essere eettivo, ossiadeve permettere di ottenere risultati intempicompatibili conquelli del processodecisionale. Tali tempi possonoesserenellapraticamoltovariabili, asecondacheilprocessodecisionaleriguardi,adesempio, investimenti strategici conunorizzontedi molti anni, oppuredecisioni on-linedaattualizzareintempidellordinedei secondi(opersino8 CAPITOLO1. PROBLEMIEMODELLIinferiori); inoltre, lerisorsedicalcolodisponibilipossonovariaredasuper-computers noaprocessori embeddedconrisorsemoltolimitate. Co-munque, anche nel caso di disporre di tempi moltolunghi e di ampie risorsedi calcolonon`epossibiledareperscontatochesi siaingradodi determi-naresoluzioni perqualsiasi modello; ci`o`eparticolarmenteveronelcasodiproblemi di ottimizzazione,la grande maggioranza dei quali sono NP-ardui.In generale, una data situazione reale pu` o essere modellata in molti modidiversi, asecondadiquali aspetti dellarealt` avengonoinseriti nel modelloedi quali assunzioni (spessosemplicate)si fannosullerelazioni cheli le-gano. Tali sceltepossonoinuenzareinmodospessodrasticoladicolt` adel problemadi ottimizzazionechesi ottiene; comevedremoinmolteplicioccasioni, accadesoventechemodicheapparentementeminoriadunpro-blema di ottimizzazionelo rendano signicativamente pi` u facile o dicile darisolvere. Anche una voltaspecicate le propriet`a che il modello deve avere,ladecisionesullaformadel modellopu` oesserenonbanale: esistonomoltimodidiversiperspecicarelostessoinsiemedientimatematici, maalcunisonopi` uutilidialtrialnedisviluppareapproccialgoritmici.In queste note viene eettuatauna scelta precisa sulla forma dei modelliutilizzati: essi sono tutti problemi di ProgrammazioneLineareIntera(PLI).Lagiusticazionedi talesceltarisiedesostanzialmentenel fattoche, comevedremo, taleclassedi problemi possiedeunanotevoleespressivit`acheconsente di modellare moltissimi problemi di interesse pratico; daltra parte,leassunzioni restrittivesullaformadel problemapermettonodi utilizzaretecnichealgoritmichepi` usemplici, espessopi` uecienti, rispettoadaltreformedimodello.`Eper` oopportuno rilevarechequestascelta`earbitraria,efondamental-mentedettatadal fattochequeste notesi intendono per un corso di base diRicercaOperativa. Esistonoaltreformediproblemidiottimizzazionefa-cili oltre a quelli qu` presentati che consentono luso di relazioni nonlineari;daltra parte, esistono molte situazioni pratiche in cui non `e possibile (o non`econveniente)evitarediutilizzarerelazioni nonlinearinelmodello. Sipu` oper` oaermarechelaPLI fornisceunottimocompromessotrasemplicit`aepotenza espressiva; inoltre, la maggioranza dei concetti algoritmici utilizzatiper risolvere problemi pi` u generali `e presente,almeno in forma semplicata,agliinternodegliapproccialgoritmiciperlaPLI.Inquestoparagrafoforniamounabreveintroduzioneallamodellazionedi problemi di ottimizzazionesottoformadi PLI, presentandouninsiemedimodellielementarichecostituisconoiblocchidibaseperlacostruzio-nedimodellicomplessi. Nelfarlodescriveremoanchealcuninotiproblemidi ottimizzazione, checi aiuterannoadillustrarelusodellediversetecni-chedimodellazioneechesiincontranofrequentementenelleapplicazioni,odirettamente opi` u spessocome sottoproblemi di problemi pi` u complessi.1.2. MODELLI 91.2.1 ProgrammazioneLineareUnproblemadi ProgrammazioneLineare(PL) `eunproblemadi ottimizza-zionecaratterizzatodalleseguentipropriet`a:1. unnumeronitondivariabili,chepossonoassumerevalorireali;2. unafunzioneobiettivolineare, cio`edeltipof(x)=cxdovec Rn`eilvettoredeicosti(ssato)edx Rn`eilvettoredellevariabili;3. linsieme ammissibile `e denito da un insieme nito di m vincoli linearideltipoax = b,e/oax b,e/oax b,dovea Rneb R.Unproblemadi PLpu` osempreessereespresso, adesempio, permezzodiunaformulazionedeltipomax{ cx : Ax b }doveA `eunamatricerealemneb Rm.Nel seguitouseremoleseguenti convenzioni: seaebsonovettori dellestessedimensioni, abdenotail loroprodottoscalare; seA`eunamatricem nebunvettoredi dimensionen[m], Ab[bA] denotail prodottodiAperb[bperA] intesocomevettorecolonna[riga]. Perevitarelusodelsegnoditrasposta,considereremounvettorecomeunarigaounacolonna,asecondadelcontesto.Iproblemi di PLformanounadellepi` uimportanti classi di modelli diottimizzazione, poichepermettonodimodellareconsucienteaccuratezzamolte situazioni reali e possonoessere risolti ecientemente ingenerale,come mostrato nel Capitolo 3). Introduciamo ora alcuni esempi di problemidiPL.1.2.1.1 PianicazionedellaproduzioneLasociet`aPintel devepianicarelaproduzionedellasuafabbricadi mi-croprocessori. LaPintelpossiededuediverselineediprodotti: iprocessoriPintium, pi` upotenti edestinati al mercatoserver, edi Coloron, menopotentiedestinatialmercatoconsumer. Limpianto`eingradodirealiz-zare 3000 wafer alla settimana: su ogni wafer trovano posto o 500 Coloronoppure 300Pintium. Laresadi unwaferdipende anchessadaltipodi pro-cessore: i Coloron, di minori dimensioni, hannounaresamediadel 60%,mentrei Pintium, pi` ugrandi equindi maggiormente sottoposti adifetti,solamente del 50%. I processori Pintium si vendono a 500$ al pezzo,mentreiColoronsivendonoa200$alpezzo. LadivisionecommercialedellaPintelhaanchestabilitochelamassimaquantit`adiprocessorichepossonoesseremessi sul mercato ogni settimana senza causare un calo dei prezzi `e di 400000unit` a per i Pintium e di 700000unit` a per i Coloron. Si vuole determinare le10 CAPITOLO1. PROBLEMIEMODELLIquantit`a di ciascun tipo di processore da produrre settimanalmente in mododamassimizzareilricavototale.Formuliamo,matematicamenteilproblema. Aquestoscopointroducia-mo le variabili xPed xC, che indicano il numero di processori rispettivamentedi Pintium e Coloron da produrre. Su queste variabili possiamo innanzituttoporreleseguentilimitazionisuperioriedinferiorisulvaloredellevariabili0 xP 4000000 xC 700000checorrispondonoal fattochenon`epossibileprodurrequantit`anegativedi processori, edalle limitazioni impostedalladivisione commerciale perimpedireuncalodeiprezzi.Restanodaconsiderarelelimitazionilegatealprocessoproduttivo. Peresprimerle, indichiamoconwPewCil numerodi waferutilizzati perpro-durrerispettivamenteiPintiumeiColoron;ilseguentevincololegaquesteduevariabiliallaproduzionesettimanalewP+wC 3000.Conoscendo il numero di pezzi per wafer e la resa produttiva si ottengonoquesterelazioni cheleganoil numerodi pezzi processori funzionanti conilnumerodiwaferprodotti:xP= wP 300 0.5 = wP 150 ,xC= wC 500 0.6 = wC 300 .(1.4)EliminandoleduevariabiliwPewCdalvincolosullaproduzionesetti-manalesiottieneilvincolo2xP+xC 900000 .Quindi,linsiemeammissibileFperilproblema `eilseguente:F= { (xP, xC) : 0 xP 400000 , 0 xC 700000 , 2xP+xC 900000 }Adesempio, (xP, xC)=(0, 0)`eovviamenteunasoluzioneammissibileperilproblema. Unovvioinsiemedisupportoperilmodello`eF

= R2,elasoluzione(xP, xC) = (400000, 700000)non`eammissibileperil problemainquantoviolail vincolosullacapacit` adiproduzionedeiwafers.Il ricavo ottenuto dalla vendita della produzione settimanale `e dato dallaseguentefunzione(lineare)nellevariabilidecisionalidelproblema:c(xP, xC) = 500xP+ 200xC.1.2. MODELLI 11Di conseguenza, unmodelloanaliticoperil problemadellaPintel `eil se-guente:max 500xP+ 200xCxP 400000xC 7000002xP+ xC 900000xP, xC 0Unavoltadeterminatalasoluzione(xP, xC),ossiainterminidiproces-sori, `epossibilericavarelasoluzione(wP, wC), ossiaintermini di wafers,semplicementeutilizzandolerelazioni(1.4).Esercizio1.1Forniretrediversesoluzioni ammissibili evalutarei ricavichesiottengono.Linsieme ammissibile del problema della Pintel `e mostrato in Figura 1.1(entrambi gli assi sonostati scalati di unfattore100000percomodit` adirappresentazione).[4,1][4,0]xP[0,0]xC 7[0,7]xP 42xP + xC 9[1,7]xC 0xP 0xCFigura1.1: InsiemeammissibileperilproblemadellaPintelLinsieme ammissibile `e il poliedroconvessotratteggiato,delimitatodal-lerettecorrispondenti ai vincoli del problema.`Epossibilevericareche,perlalinearit` adellafunzioneobiettivo, unasoluzioneottimadelproblema(seesiste)si trovasempreinunverticedel poliedro, inquestocasoquellocorrispondentealpunto(4, 1).Unaspettocherestaancoradadiscutere`eil dominioammissibileperlavariabili wPewC. Tali variabili rappresentanolaproduzionedi unit` adiscrete di bene (i singoli wafers), e quindi sarebbe ragionevole imporre12 CAPITOLO1. PROBLEMIEMODELLIlulteriore vincolo che, nella soluzione attesa del problema, esse possanoassumeresoltantovalori interi. Sinoti cheimporrelinterezzadi wPewCnon`eequivalenteadimporre linterezzadixPe xC;lasoluzioneottimadelproblema`e(xP, xC) =(400000, 100000), quindi intera, matalesoluzionecorrisponde,interminidiwafers,a(wP, wC) = (2666.6, 333.3).Daltro canto, i dati del problema sono tali per cui si pu` o ragionevolmen-teipotizzarecheunadierenzadi unwafernoncambi sostanzialmentelaqualit`adellasoluzioneinpratica: lestimedelladivisionecommercialehan-nopresumibilmenteunrilevantemarginediincertezza, edancheil vincolosul numerodiwafers `eprobabilmentesoggettoarilevantiincertezze(guastidi macchinari oscioperi, eventi imprevedibili, ecc.) percui laproduzionedi wafers inogni specicasettimanapotrebbeessereleggermente diversadaquellaipotizzata. Inquestecircostanze,sipu` opensareche,adesempio,lasoluzioneammissibileintera(wP, wC) =(2666, 334) siacomunqueunabuonadecisione inpratica; per questo, `eragionevole ammettere valorifrazionariperlevariabiliwPedwC.1.2.1.2 IlproblemadellaFonderiaUna fonderia deve produrre 1000 pezzi del peso ciascuno di un chilogrammo.Il ferro con cui tali pezzi sono fatti dovr`a contenere manganese e silicio nelleseguentiquantit`a:0.45% manganese3.25% silicio 5.5%Sonodisponibilitretipidimaterialeferrosoconleseguenticaratteristiche:Materialeferroso A B CSilicio(%) 4.00 1.00 0.60Manganese(%) 0.45 0.50 0.40Costo(Euro/kg.) 0.025 0.030 0.018Inoltre si pu` o aggiungeredirettamentemanganeseal costodi 10Euro al kg.Il problemachesi vuolemodellare`equellodi determinareil pianodiproduzionecheminimizzail costodel materiale utilizzato. Si vuolecio`eindividuarelequantit`adimaterialeperciascunodeitretipiA,B,oCedimanganese puro da acquistare per produrre i 1000 pezzi richiesti, spendendoilmenopossibile.Proviamoacostruireunmodelloanaliticoper il problema. Aquestoscopointroduciamolevariabilix1, x2, x3, x4,aventiilseguentesignicato:x1( 0) : laquantit`ainkgdimaterialeferrosoAdautilizzare;x2( 0) : laquantit`ainkgdimaterialeferrosoBdautilizzare;x3( 0) : laquantit`ainkgdimaterialeferrosoCdautilizzare;x4( 0) : laquantit`ainkgdimanganesedautilizzare.1.2. MODELLI 13Abbiamo imposto chele quantit`adi prodottoacquistatesiano dei valorinonnegativi (vincoli di nonnegativit`a). Esistonopoi altri vincoli chedo-vranno essererispettatiechedescriviamodi seguito. Il numero totaledi kgprodottideveessere1000:x1 +x2 +x3 +x4= 1000 .Laquantit`adisilicio,inkg,presentenelprodottorisultante`edatada0.04x1 + 0.01x2 + 0.006x3.Lapercentualedisilicionelprodottonitosar` aquindidatada1000.04x1 + 0.01x2 + 0.006x31000.Tale numero deve essere compreso tra 3.25 e 5.5. Possiamo quindi esprimerelacondizionesullapercentualedisiliciomedianteiduevincolilineari4x1 +x2 + 0.6x3 3250 ,4x1 +x2 + 0.6x3 5500 .Analogamente,perlacondizionesullapercentualedimanganesesiottiene0.45x1 + 0.5x2 + 0.4x3 + 100x4 450 .Inneilcostodelprodottorisultante`e0.025x1 + 0.030x2 + 0.018x3 + 10x4.Ilproblemadelladeterminazionediunpianodi produzionecheminimizzailcostopu` oquindiessereformulatocomesegue:min 0.025x1+ 0.030x2+ 0.018x3+ 10x44x1+ x2+ 0.6x3 32504x1+ x2+ 0.6x3 55000.45x1+ 0.5x2+ 0.4x3+ 100x4 450x1+ x2+ x3+ x4= 1000x1, x2, x3, x4 0Le variabili x1, x2, x3 e x4 corrispondono alle scelte operative che il problemareale richiededi compiere,e ciascunvincolo del modellocorrisponde adunacondizione imposta dal problema reale. Determinare i valori delle variabili inmodo che i vincoli siano soddisfatti e la funzione obiettivo assuma il minimovalorefornisceilmigliorpianodiproduzione.14 CAPITOLO1. PROBLEMIEMODELLI1.2.2 Variabili logicheNegli esempi precedenti abbiamoincontratovariabili cherappresentanoillivellodi attivit`aproduttive, comeil numerodi processori daprodurrein1.2.1.1oppureilnumerodipezzidaprodurrenellafonderiain1.2.1.2. Va-riabili di questotipovengonoanchedettevariabili quantitative; ci`ochelecaratterizza`eil fattodi rappresentarequantit`adi beni, di oggetti dapro-durre, comprareoutilizzare, oppurevalori assunti dagrandezzesicheoeconomiche.Inaltri casi levariabili rappresentanodellesceltedi tipologico(vero,falso);siparlaalloradi variabililogiche. Peresprimere questotiposisceltasiutilizzanousualmentevariabilibooleane,obinarie,chepossonoassumereunosolodeiduevalorinumerici0o1,attribuendoalvalore0ilsignicatodifalsoeda1quellodivero.`E importante sottolineare come luso di variabili binarie, o pi` u in genera-le di variabili vincolatead assumere solamenteun insieme discreto di valori,se da unlatoaumentalespressivit`adei modellidi ottimizzazione,dallaltronepu` orenderemoltodicilelasoluzione. SidenisconoproblemidiPro-grammazioneLineareIntera(PLI ),oMista,iproblemiincuiivincolielafunzioneobiettivosonolineari, comenel casodellaPL, maincui tuttelevariabili, ounlorosottoinsieme, possonoassumeresolamentevalori interi.MentrelaPL`eunproblemafacile, laPLI `eingenerale unproblemadicile(sivedalAppendiceA).Vediamoadessoalcuniesempidimodellicheusanovariabililogiche.1.2.2.1 IlproblemadellozainoSiadato uninsieme E={1, 2, . . . , n} di elementi, aciascuno dei qualisiaassegnatounpesoaieduncostoci, i =1, . . . , n, interi epositivi: ilproblemadellozaino(KP, daKnapsackProblem)consisteneldeterminareunsottoinsiemedi elementi cheabbiacostototalemassimoedil cui pesototalenonsuperiunpressatointerob. Il nomederivadalfattochevieneusualmentedescrittocomeilproblemadisceglierequalioggetti diundatoinsieme mettere inunozainoinmododanonsuperareundatopeso(ocapacit` a)edamassimizzareil valorecomplessivodegli oggetti selezionati.Si assumechesia00ciascunnodoabbiaesattamenteduearchi incidenti;qualsiasivincolo,ovepresente,vaindicatoesplicitamente.I vincoli (1.7) non garantiscono che gli archi (i, j) le cui variabili associatexijassumono il valore1 formino un cicloHamiltoniano;infatti esse garanti-sconosolounacoperturapercicli delgrafo, comeillustratonellesempioingura1.2incui gli archi selezionati formanounacoperturadi tutti i nodidelgrafomediantedueciclidisgiunti,unodi3archielaltrodi4.1 2 345 6 7Figura1.2: unacoperturapercicli(archiingrassetto)Per imporrechegli archi selezionati forminoununicociclo(Hamilto-niano)possiamoutilizzareivincolidiconnessionesuitagli(1.5),introdottiper (MST).Laggiuntadeivincolidi connessioneaivincolidi copertura percicli (1.7)imponechelacoperturapercicli formi ungrafoconnesso: ci`o`epossibilesolosesi haununicociclonellacopertura, che`equindiunciclo1.2. MODELLI 19Hamiltoniano. Laformulazionecompletadi(TSP)diventaquindi(TSP)min

(i,j)Acijxij

iS,j / Sxij 1 S N

(i,j)Axij= 2 i Nxij {0, 1} (i, j) ACome per (MST), esistonodelle formulazioni per (TSP) conunnumeropolinomialedivincoli;peressesirinviaallabibliograasuggerita.Esercizio1.4Assegnaredei pesi agli archi del grafoingura1.2suppo-nendochegli archi mancanti abbianopesoinnito. CostruirequattrocicliHamiltonianievalutarnelalorolunghezza.Esercizio1.5Costruire unistanza con un grafo completo con 4 nodi eformulareil (TSP)pertaleistanza.Sipu`onotarechelaformulazionedi(TSP)coincideconquelladi(MST)acuisonostatiaggiunti i vincoli (1.7). Pertanto, linsieme ammissibile di (MST) contiene quello di (TSP);siccomelafunzioneobiettivo`eidentica,(MST)`eunrilassamentodi(TSP).1.2.3 RelazionibinarieSpesso, le relazioni tra i valori di variabili booleane sono assimilabili alle bennoterelazionilogichetravariabiliproposizionali,ossiavariabilichepossonoassumereivaloriveroofalso. Ineetti, sipossonocostruirevincoli linearitravariabili binarie equivalenti alle classiche relazioni logiche del calcoloproposizionale. Nel seguito, datounletterale(proposizioneelementare)adelcalcoloproposizionaleindicheremoconx(a)lacorrispondentevariabilebooleana,associandoilvalore1dix(a)alvaloreverodiaedilvalore0dix(a)alvalorefalsodia.Analizziamoadessolepi` ucomunirelazionitravariabiliproposizionali.Negazione. Data la variabile proposizionale a, la variabile complementareb = a viene rappresentata facilmente dalla variabilecomplementarex(b) =1 x(a), conx(b) {0, 1}. Sesihannoduevariabiliproposizionaliaebesivuoleimporrecheunasiailcomplementodellaltra,`esucienteimporrealle corrispondenti variabili booleane di rispettare il vincolo x(a) +x(b) = 1.Implicazione. Larelazione logicaab (aimplicab) `e esprimibilemedianteladisuguaglianzax(b) x(a); infatti,x(b)`eforzataadassumereilvalore1sex(a) = 1.20 CAPITOLO1. PROBLEMIEMODELLIUnione (Or). Date due variabili proposizionali a e b, la variabile c = ab,cheassumeilvaloreveroquandoalmenounadelledue variabili `evera,pu` oessereespressamedianteleseguentirelazioni:x(c) x(a), x(c) x(b), x(c) x(a) +x(b), x(c) {0, 1}.Infatti, ledueprimediseguaglianzeimpongonoallavariabilebooleanax(c)di assumere il valore1 seuna delle due altre variabiliha il valore1. Laterzaimponeilvalorex(c) = 0sex(a) = x(b) = 0.Unioneesclusiva(Oresclusivo). Dateduevariabiliproposizionaliaeb,la variabilec = a b,cheassume ilvaloreveroquando una soladelle duevariabili`evera,pu` oessereespressamedianteleseguentirelazioni:x(c) x(a) x(b), x(c) x(b) x(a),x(c) x(a) +x(b), x(c) 2 x(a) x(b), x(c) {0, 1}.Infatti, ledueprimediseguaglianzeimpongonoallavariabilebooleanax(c)di assumereil valore1quandounasoladelleduealtrevariabili hailvalore1. Laterzaimponeilvalorex(c)= 0sex(a)= x(b)= 0elaquartaimponex(c) = 0sex(a) = x(b) = 1.Intersezione (And). Date due variabili binarie a e b, la variabile c = ab,cheassumeilvaloreverosoloquandoentrambeleduevariabili sianovere,pu` oessereespressamedianteleseguentirelazioni:x(c) x(a), x(c) x(b), x(c) x(a) +x(b) 1, x(c) {0, 1}.Infatti, leprimeduediseguaglianzeimpongonoallavariabilebooleanax(c)diassumereilvalore0quandoalmenounadelleduealtrevariabilihailvalore0. Laterzaimponeilvalorex(c) = 1sex(a) = x(b) = 1.Ingenerale,`epossibileformularemoltiproblemidelcalcoloproposizio-nale sottoforma di problemi di ottimizzazione. Questo tipo di formulazionepermette di utilizzare tecniche di ottimizzazione in alternativa o in appoggioallenormalitecnicheinferenzialiusatenelcalcolologico.1.2.3.1 Soddisfattibilit`aIl problemadellaSoddisfattibilit` aProposizionale (SAT, daSATisability)richiededi determinareseunadataformuladel calcoloproposizionaleinFormaNormaleCongiuntivaA = C1 C2 . . . Cm`esoddisfattibile,doveC1, C2, . . . , CmsonoclausoledeltipoCi= P1 P2 . . . Pr1.2. MODELLI 21econPjsiindicaoilletteralePjolasuanegazionePj,j= 1, . . . , n. Sivuolecio`edeterminareseesisteunassegnamentodivalorediverit` averoofalsoalleproposizioni elementari P1, P2, . . . , PncherendaveralaformulaA. Siccomequalsiasi formuladel calcoloproposizionalepu` oessereportatainFNC,questoproblemaharilevantiapplicazionipratiche,adesempioperilprogettoelavericadicircuitidigitaliVLSI.Introduciamo n variabili binarie xjassociate ai letterali Pj, j= 1, . . . , n,edeniamoaij=1 seilletteralePjapparedirettonellaclausolaCi,1 seilletteralePjapparenegatonellaclausolaCi,0 seilletteralePjnonapparenellaclausolaCi.Datounqualunquevettorex {0, 1}n,chepossiamointerpretarecomeunassegnamentodivaloridiverit` aagli nletterali P1, . . . , Pn,`efacileveri-carechelaclausolaCi`esoddisfattadallassegnamentodi valori di verit` acorrispondenteadxseesoloserisulta

jaijxj 1 n(i) ,dove n(i) `e il numero di letterali che appaiono negati in Ci. Di conseguenza,unaformulazionePLI di(SAT)`eMax

ja1jxj

jaijxj 1 n(i) i = 2, . . . , mxj {0, 1} j= 1, . . . , nInfatti,qualsiasisoluzioneammissibilexperilproblemacorrisponde adunassegnamentodi valori di verit` aalleproposizioni elementari cherendevere tutte le clausole C2, C3, . . . Cm. Se la soluzione ottima xdel problemasoddisfaanchelaclausolaC1,cio`eserisulta

j a1jxj 1 n(1),alloraxcorrisponde ad un assegnamentodi valori di verit` aalleproposizioni elemen-tari che soddisfa A, e quindi A `e soddisfattibile;altrimenti,non pu` o esisterenessunassegnamentodi valori di verit` aallevariabili chesoddisfacontem-poraneamenteC1etuttelealtreclausole, equindiAnon`esoddisfattibile.Unavariantedi (SAT)`eil problemadi ottimizzazione nel qualesi cercalassegnamentodi valoridiverit` aailetteralichemassimizzailnumerodelleclausoleCisoddisfatte(Max-SAT).Esercizio1.6Sidiaunaformulazioneanaliticadi(Max-SAT).Esisteunarilevanteinterfacciatraproblemilegatialcalcolologicoeproblemidiottimiz-zazione: ineetti, (SAT)`estatoil primoproblemache`estatodimostratoessereNP-completo(si vedalAppendiceA). Ci`opermettedi utilizzaretecnichedi ottimizzazioneper lasoluzionedi problemi relativial calcolologicoe,viceversa,tecniche di inferenza per22 CAPITOLO1. PROBLEMIEMODELLIrisolvereproblemi di ottimizzazione. Esistonopersinoalcuni interessanti risultati teoricichemostranocomelededuzioni logiche nel calcoloproposizionale possonoessere vistecomecombinazioni lineari dei vincoli nellacorrispondenteformulazionedi PLI, equindicomele tecniche inferenzialisianoun casoparticolaredi alcune tecniche per larisoluzionediproblemidiPLI,dimostrandocomelarelazionetraottimizzazioneecalcolologicosiaprofonda.1.2.4 VincolidiassegnamentoesemiassegnamentoDescriviamo adesso due tipi di vincoli su variabili binarie che sono utiliz-zatimoltodifrequenteinmodellidiPLI.SiaN= {1, 2, . . . , n}uninsiemedi noggetti eV ={v1, v2, . . . , vm}uninsiemedi melementi, cheposso-norappresentarealtri tipi dioggetti, persone, sottoinsiemi, ecc. asecondadel contesto. Introduciamolavariabilelogicaxijcol seguentesignicato:xij=1indicache alloggetto i `e stato assegnato lelemento vj, mentrexij= 0indicachelelementovjnon `estatoassegnatoadi.Ivincoli di semiassegnamentoimpongonocheaciascunoggettosiaas-segnatounoedunsoloelemento:m

j=1xij= 1, i = 1, . . . , n.Si noti ancoraunavolta come lipotesi che le variabili sianobinarie,ossiachexij{0, 1}, i =1, . . . , n, j =1, . . . , m, siacriticaper garantirelacorrettezzadiquestivincoli: rilassandoilvincolodiintegralit` a, esisteadesempio,lasoluzionefrazionariaxij= 1/m, i = 1, . . . , n, j= 1, . . . , m,cheovviamentenonhanessunapossibileinterpretazioneintermini del si-gnicatochesivuoldareallevariabili.Capitaspessocheuncertooggettoi possaessereassegnatosolamenteadundatoinsiemeB(i)di elementi ammissibiliperi; inquestocaso, `esuciente denire le variabili xijsolamente per le coppie (i, j)con j B(i),emodicareivincolidisemiassegnamentoin

jB(i)xij= 1, i = 1, . . . , n .Quandoi dueinsiemi NeV hannolastessacardinalit`a, cio`em=n,`e possibilechenel modellovengarichiestocheanche aciascunelementosiaassegnatounoeunsolooggetto; intal casosi utilizzerannoi vincoli diassegnamenton

j=1xij= 1, i = 1, . . . , n ,n

i=1xij= 1, j= 1, . . . , n .(1.9)1.2. MODELLI 23Ivincolidiassegnamentopossonoessereutilizzatipercreareunordina-mentotraoggetti. Si suppongache, allinternodi unproblema, si debbadecidere conquale ordine eettuaren lavori1, 2, . . . , n. In tal caso,i vincoli(1.9)impongonounordinamentodei lavori seassociamoadogni variabilexij,i, j= 1, . . . , n,ilseguentesignicato:xij=

1, seillavoroi `eeettuatocomej-esimo,0, altrimenti.In altritermini,una soluzioneammissibileper ivincolidi assegnamentoassegnaadognilavoroiunaposizioneallinternodellordinamento.Presentiamo adesso tre modelli incui vengono utilizzati i vincoli disemiassegnamento.1.2.4.1 AssegnamentodicostominimoLagenziamatrimonialeCuoriSolitarideveorganizzareilgranballodineanno. Lagenziahanclienti maschi enclienti femmine, edhaprenotatontavoli dadueposti al famosoristorante Cupido. Dai proli psicologi-ci raccolti dai clienti, lagenzia`eingradodi calcolare, per ogni maschioi, linsiemeF(i)dellefemmineconlequali potrebbeessereinteressatoadintrecciareunarelazione, echepotrebberoessereinteressateadintrecciareuna relazione con lui; un analogo insieme M(j) pu` o essere ottenuto per ognifemminaj. Dai proli dei clienti, lagenzia`eancheingradodi calcolare,perogni coppia(i, j) compatibile, il costocijdellacenadaorire, chedeveconsisteredipiattigraditiadentrambiicommensali. Lagenziavuolequindi deciderecomeformarelecoppieperilgranballoinmododaevitarecoppieincompatibilieminimizzareilcostocomplessivodellecene.Unaformulazione del problemadellagenzia Cuori Solitari fausodeivincolidiassegnamentoincuiCindicalinsiemedellecoppiecompatibili:min

(i,j)Ccijxij

jF(i)xij= 1 i = 1, . . . , n

iM(j)xij= 1 j= 1, . . . , nxij {0, 1} (i, j) CQuesto problema,notocomeilproblemadellassegnamentodi costomi-nimo, `e polinomiale ed ha molte applicazioni in pratica;algoritmiper la suasoluzionesonodescrittinellaSezione2.7.DatoungrafononorientatoG, il problemadi determinareunacoperturaperciclidicostominimodelgrafo(si vedail 1.2.2.3)pu`oessereformulatocomeunproblemadiassegnamentodicostominimo: siagli oggetti ichegliindicijcorrispondonoainodidel24 CAPITOLO1. PROBLEMIEMODELLIgrafo, elecoppie(i, j) compatibilicorrispondonoagli archi del grafo, conil relativocosto. Diconseguenza, ilproblemadellassegnamentodicostominimo`eunrilassamentodi(TSP).Si noti quindi come lo stesso problema possa avere molti rilassamenti diversi: ad esem-pio,siailproblemadellassegnamentodicostominimoche il(MST)sonorilassamentidel(TSP). Diversi rilassamenti possonocatturarepartidiversedellastrutturacombinato-riadiunproblema: adesempio,(MST)incorporailvincolodiconnessionemanonquellodellaformazionedi cicli, mentreil problemadellassegnamentoincorporail vincolodellaformazionediciclimanonquellodiconnessione.Inne, si noti che sia il problema dellassegnamentoche (MST) sono problemi facili,mentre (TSP),chepu`o essereconsideratolintersezionediquesti due problemi, `edi-cile. In generale, solo in casi molto particolari lintersezione di due strutture combinatoriecorrispondentiaproblemifaciligeneraunproblemaasuavoltafacile.1.2.4.2 Ordinamentodi lavori sumacchine: minimizzazionedelnumerodellemacchineQuestoproblemaapparefrequentementeindiversi ambiti, adesempioinquellomanifatturiero, nellagestionedi sistemi informatici enellagestionedi progetti. Sianodati nlavori emmacchine uguali, sucui fareseguireilavori. Il lavoro i-esimo, i = 1, . . . , n, pu` o essere svolto su ciascuna macchinaerichiedeuntempodi esecuzione diindipendentedallamacchinasucuivieneeseguito. Illavoroi-esimovieneconsegnatoaltempotiedeveessereimmediatamenteeseguito; essendodilasuadurata, lesecuzioneterminer`aaltempo ti +di. Il numero m di macchine `eapriori illimitato(ovviamente,`esucientechesiam = n;sefossem > n, alcunedellemacchinesarebberocomunqueinutilizzate). Lobiettivo`eutilizzareilminimonumeropossibiledi macchine per eseguire tutti i lavori, assegnando alla stessa macchina lavoriicuitempidiesecuzionenonsisovrappongano.Si noti cheuna soluzioneammissibilecorrisponde aduna partizionedel-linsieme N={1, 2, . . . , n}inmsottoinsiemi N(1), N(2), . . . , N(m), chepossono anche essere vuoti, in cui il generico sottoinsieme N(j), j= 1, . . . , m,rappresentailavoriassegnatiallaj-esimamacchina.Perdescrivereilproblema,introduciamo mnvariabilibinarie xij,inten-dendochexij=1seil lavoroivieneeseguitosullamacchinaj, exij=0altrimenti. LavariabilexijrappresentalappartenenzaomenodiiaN(j).Perrappresentaremediantelevariabili xijlinsiemedellesoluzioniammis-sibili, dobbiamoimporrecheogni lavorosiaassegnatoadunaedunasolamacchina,il chepu` o essere espresso mediante i vincoli di semiassegnamentom

j=1xij= 1, i = 1, . . . , n . (1.10)Dobbiamoinoltregarantirecheseduelavori i ehsonoassegnati allastessa macchina j, allora i loro tempi di elaborazione, cio`e gli intervalli[ti, ti + di] e[th, th + dh], sianodisgiunti ; inaltri termini si deveavereche1.2. MODELLI 25oti + dith(il lavoroiterminaprimadelliniziodel lavoroh), oppureilviceversa,th +dh ti. Perogni lavoro,i = 1, . . . , n1,deniamo linsiemeS(i)deilavorih,conh > i,chesonoincompatibili conesso:S(i) = {h {i + 1, . . . , n} : [ti, ti +di] [th, th +dh] = }, i = 1, . . . , n 1.Si notichegliinsiemidiincompatibilit` aS(i), i = 1, . . . , n 1,sonodeidatidiinputdelproblema. Mediantetaliinsiemipossiamoscrivereiseguentivincolidicompatibilit` a:xij+xhj 1 i = 1, . . . , n 1, h S(i), j= 1, . . . , m .Ivincoli di compatibilit`aimpedisconochelevariabili relativeaduelavoriincompatibili assumano entrambe valore 1. Il numero dei vincoli di incompa-tibilit` a dipende dai conitti tra gli intervalli di tempo, e quindi dalla sommadelle cardinalit`a degli insiemi di incompatibilit`a moltiplicatoil numero m dimacchine;talenumero `ecertamentenonsuperioreamn(n 1)/2.Esercizio1.7Dimostrarelasserzioneprecedente.Performularelafunzioneobiettivosideveesprimereilnumerodimac-chineutilizzate;inquestocaso`econvenienteintrodurre,perognimacchinaj, unulteriore variabile logica yj {0, 1} che assume il valore 1 se essa vieneutilizzatae0altrimenti. Intalmodolafunzioneobiettivo,daminimizzare,`em

j=1yj.Si deve quindi esprimere il legame tra le macchine utilizzate (cio`e le variabiliyj)eilavoriassegnatiadesse(cio`elevariabilixij);inaltriterminisideveimporrecheseallamacchinaj`estatoassegnatoalmenounlavoro, alloradeveessereyj= 1. Ci` o `eesprimibileinduemodidistinti:yj xij, i = 1, . . . , n, j= 1, . . . , m; (1.11)oppurenyjn

i=1xij, j= 1, . . . , m. (1.12)Il primo insieme di mn vincoli (1.11)forza yj= 1 se almeno una delle varia-bili xijha valore1;taleinsiemedi vincoli `ecorrispondente alleimplicazionilogicheseil lavoroivieneeseguitosullamacchinaj, alloralamacchinaj`eutilizzata(cf. 1.2.3). Il secondoinsieme, disoli mvincoli, (1.12)metteinrelazione yjconil numero

ni=1xijdi lavori assegnati aj. Seesso`epositivo,sicuramentenonsuperioreadn,ilvincoloimponeyj= 1. Sinotiancoraunavoltacomelevariabili booleaneabbianounadoppianatura,logicaenumerica.26 CAPITOLO1. PROBLEMIEMODELLILa formulazione analitica del problema (MCMS, da Minimal CardinalityMachineScheduling)cheutilizzaivincoli(1.11)`e:(MCMS)minm

j=1yjm

j=1xij= 1 i = 1, . . . , nxij+xhj 1 i = 1, . . . , n 1, h S(i), j= 1, . . . , myj xiji = 1, . . . , n, j= 1, . . . , mxij {0, 1} i = 1, . . . , n, j= 1, . . . , myj {0, 1} j= 1, . . . , mSi noti che, seallamacchinaj nonsonostati assegnati lavori, yjpu` oassumereentrambi i valori 0e1; siccomesi minimizzalasommadelleyj,enessunvincoloimponecheyjsia1, allottimotalevariabileassumer`ailcorrettovalore0. Questovaleancheperilmodellocheusaivincoli(1.12).Si ricordi sempre che i vincoli di integralit` asulle variabili devono sempreessere esplicitamente indicati, altrimenti le variabili potrebberoassumerevalori noninteri.`Eimmediatovericarechenel rilassamentocontinuo, incui le variabili xijpossonoassumere qualsiasi valore nellintervallo [0, 1],vienepersaunapartesostanzialedellastrutturadelproblemaoriginario.Esercizio1.8Dimostrare che la rimozione dei vincoli yj{0, 1}, j =1, . . . , mnonpu` oessereapplicatasesi usanoi vincoli (1.12)al postodeivincoli(1.11).Esercizio1.9Costruireunistanzadelproblema(MCMS)con7lavori,de-nendo le durate e i tempi di inizio di essi; formulare quindi listanza, fornireduesoluzioniammissibilievalutareil numerodimacchineoccorrenti.1.2.4.3 AssegnamentodifrequenzeUngestoredi telefoniacellularedisponedi nstazioni radiobaseingradodi copriretuttalacitt`a. Perpoterattivarelarete, per` o, deveassegnareaciascuna antennauna frequenza di trasmissione inmodo tale chele antenneadiacenti cheservonocellesovrappostenonproducanointerferenza.`EdisponibileuninsiemeF={f1, . . . , fm}, di frequenze, incui ogni fi`eunvalorenumerico(espressoinMhzoGhz),elarelazionediadiacenzatraleantenne `e rappresentata da un grafo (non orientato) G = (N, A) in cui i nodirappresentano leantenneedesistelarco(i, j) A se esolose ledue anten-neiejsonoadiacenti, ossiaservonocellechepresentanosovrapposizioni,equindiassegnandolastessafrequenzaaiedajsicreerebbeinterferenza.Datocheacquisireildirittodiusodiognifrequenzahauncosto,ilgestorevuoledeterminareunassegnamentodifrequenzealleantennechenonpro-ducainterferenzaecheutilizziilminimonumerodifrequenze: sinotichea1.2. MODELLI 27due nodi non adiacenti nel grafo pu` o in linea di principio essere assegnata lastessa frequenza. In altre parole, si vuole colorareil grafo G con i colorifiinmodotalechei nodi adiacenti abbianocolori diversi echeil numerodicoloriutilizzatisiaminimo.Per descrivereil problema, introduciamo nm variabilibinarie xif,inten-dendochexif= 1selafrequenzafvieneassegnataallantennai. Siccomead ogni antenna deve essere assegnata una ed una sola frequenza, dobbiamoimporreivincolidisemiassegnamento

fFxif= 1 i = 1, . . . , n .Dobbiamoinoltregarantirechelassegnamentodi frequenzenoncausiinterferenza, ossiacheai nodi adiacenti sianoassegnatefrequenzediverse.Questopu` oesserefattoattraversoivincolilogicixif+xjf 1 (i, j) A , f F.Performularelafunzioneobiettivosi deveesprimereil numerodi fre-quenze utilizzate;in questocaso `econvenienteintrodurre, per ognifrequen-zaf, unulteriorevariabilelogicayfcheassumeil valore1seessavieneutilizzata,0altrimenti. Lafunzioneobiettivo,daminimizzare,`e

fFyf.Si deve quindi esprimere il legame trale frequenze utilizzate (cio`e levariabiliyf)eleantenneacuisonoassegnate(cio`elevariabilixif);questopu` oesserefattoadesempiomedianteivincoliyf xifi = 1, . . . , n, f F,che garantiscono che la variabile yfha valore 1 se almeno unantenna utilizzalafrequenza f. La formulazione analitica del problema(GC, daGraphColoring)`e:(GC)min

fFyf

fFxif= 1 i = 1, . . . , nxif+xjf 1 (i, j) A, f Fyf xifi = 1, . . . , n, f Fxif {0, 1} i = 1, . . . , n, f Fyf {0, 1} f FIl problema(GC)`equindi unmoltosimilecasoal problema(MCMS)seinterpretiamolefrequenzecomemacchine, leantennecomelavori egliinsiemi di incompatibilit`a tra lavori (antenne) come la relazione di adiacenzasulgrafoG.28 CAPITOLO1. PROBLEMIEMODELLIEsercizio1.10Siformulilageneralizzasionedel problema(GC)incuiadogni antennai devonoessereassegnateesattamentenifrequenzediverseeanche frequenzevicinefannointerferenza, nel sensocheseaduenodiadiacenti iejvengonoassegnateduefrequenzehek,alloraoccorrecheheksianodistantiossiache|fhfk| > perunasogliassata.1.2.5 SelezionedisottoinsiemiAbbiamo gi`a visto, nel problema di ordinamento di lavori su macchine1.2.4.2comeformalizzare lapartizionedi uninsiemeinpi` usottoinsiemi.Riprendiamooraquestoproblemageneralizzandolo.SiaEuninsiemenitodielementi (adesempioE= {1, 2, . . . , n}),eFunafamigliadimsuoisottoinsiemi:F= {F1, F2, . . . , Fm},conFj E, j= 1, . . . , m. AdognisottoinsiemeFj`eassociatouncostocj,j=1, . . . , m; ilproblemachevogliamoconsiderare`equellodideterminareunasottofamigliaS Fdicostominimochesoddisparticolarivincoli.Introduciamo per questo m variabili binarie x1, x2, . . . , xm, col signicatochexj= 1seFj S,exj= 0altrimenti, perj= 1, . . . , m. IlcostodiS`ealloradenitoda:m

j=1cjxj.Considereremo tre tipi di vincoli,detti rispettivamentedi copertura, di par-tizione e di riempimento, che danno origine a tre diversi problemi di selezionedisottoinsiemi.ProblemadicoperturaSupponiamoche si vogliache ogni elementodi Esiaselezionatoalmenounavolta, cio`echeappaiainalmenounodegliinsiemidiS: ci`opu` oessereespressoattraversoilvincolo

j: iFjxj 1 i E, (1.13)chegarantiscecheperognii EesistaalmenounindicejpercuiFjSei Fj. Ilproblemadicopertura `ealloracos`denito:(PC) minm

j=1cjxj:

j: iFjxj 1 i E , x {0, 1}m1.2. MODELLI 29Si noti che`epossibilerappresentarelafamigliaF medianteunamatriceA = [aij]icuielementisonocos`deniti:aij=

1 sei Fj,0 altrimenti.Cos`facendo,ilvincolodicoperturadivienem

j=1aijxj 1 i E .Esempio1.2:Il direttoredi uncanale televisivoper leinformazioni locali deveorganizzare il lavorodellesquadredi giornalisti eoperatori percoprirendiversi servizi fuori sede. Il capo-redattorehapredispostompossibili attivit`acheunasingolasquadrapu`osvolgere, doveunaattivit`a`elinsiemedei servizi chepossonoesseresvolti ecomportaundeterminatocostodiretribuzionedellasquadra, comprensivodeicosti perlatrasfertaeeventualioredi straordinario. Il direttoredevedeciderequali delleattivit`afar svolgereinmododapagareilmenopossibileconlagaranziacheciascunodeiservizisiacopertodaalmenounasquadra.ProblemadipartizioneSupponiamoche si voglia che ogni elementodi Esiaselezionato esatta-mente unavolta, cio`e che appaiainunoedunosolodegli insiemi di S.Formalizziamoquestarichiestaattraversoilvincolodipartizione

j: iFjxj= 1 i E, (1.14)chegarantisce, cheperogni iE, esistaunsoloindicejpercui iFjeFj S. Ilproblemadipartizionesiottienefacilmentesostituendoivincoli(1.14)aquellidicopertura(1.13):(PP) minm

j=1cjxj:

j: iFjxj= 1 i E , x {0, 1}mEsempio1.3:Il direttoredi uncantierenel Mugelloperlanuovalineadi altavelocit`adeveappaltarendiversi lavori. Lucioappalti hapredispostomdiversi possibili incarichi di appalto,ciascunodei quali `eformatodaunsottoinsiemedei lavori che, perragioni di ecienzaesecutiva, `e bene siano eseguiti dalla stessa ditta. Per ciascun incarico di appalto `e denitoanche il costo. Il problema `e di decidere quali appalti assegnare anche tutti i lavori sianosvolti e il costo degli appalti sia minimo. Questo problema pu`o essere facilmente formulatocomeproblemadipartizione.30 CAPITOLO1. PROBLEMIEMODELLIProblemadiriempimentoSupponiamochesivogliacheognielementodiEsiaselezionatononpi` udiunavolta, cio`echeappaiainal pi` uunodegli insiemi diS. Formalizziamoquestarichiestaattraversoilvincolodiriempimento

j: iFjxj 1 i E,chegarantiscecheperogni i Enonpossaesisterepi` udiunindicejpercuii FjeFj S. Ilproblemadiriempimento`ealloracos`denito:(PR) minm

j=1cjxj:

j: iFjxj 1 i E , x {0, 1}mSi noti che, se tutti i costi sono non negativi, questo problema ha banalmentesoluzioneottimanulla; per questo, losi trovapi` uspessoformulatocomeproblemadimassimizzazione.Esempio1.4: UnitedcolorsofowersIl famoso allestitore di vetrine Ulivetto Laziali `e stato chiamato a predisporre la vetrina delpi` u importante oraio di Pescia. Con gli n ori, di forma e colore diversi, che il oraio gli hafornito,Ulivetto produce mdiversibozzettidi composizioneorealee per ciascunodiessifornisce anche un punteggio di bellezza compositiva. Decide quindi di allestire in vetrinauninsieme di composizioni oreali che massimizzi il punteggio globale (denitocomesommadeipunteggidellesingolecomposizioni realizzate). Ilproblema`echiaramenteunproblema di riempimento inquanto non si possonorealizzaredue composizionicontenentilostessoore.Esercizio1.11SiadatalafamigliaF={{1, 3, 5}, {2, 3}, {1, 4}, {3, 4, 5},{2}, {5}, {1, 5}}formatada7sottoinsiemi diE= {1, 2, 3, 4, 5}. Formulareiproblemidicopertura, partizioneeriempimentosapendocheil vettoredeicosti `e c =[3, 5, 1, 9, 2, 4, 1]. Determinare unasoluzione ammissibile, seesiste,perciascunproblema.Esercizio1.12Si formulinoanaliticamente i problemi di copertura, par-tizioneeriempimentogeneralizzati incui ogni oggettoi devefarpartedi,rispettivamente,almeno,esattamenteedal pi` ubisottoinsiemi.Esercizio1.13Si formulino analiticamente le ulteriori generalizzazioni deiproblemi di copertura, partizioneeriempimentogeneralizzati dellesercizioprecedente incui di ogni sottoinsieme Fjsi possano prendere pi` u copie,eventualmentelimitateadunnumeromassimodiuj.1.2. MODELLI 311.2.6 VariabiliavaloridiscretiCome abbiamo visto in molti esempi precedenti, le variabili booleane hanno,neimodelli,unadoppianatura: daunapartevengonointerpretatecomevariabili binarie, equindi il lorovalorevieneassociatoavalori di verit` a,dallaltrasononormali variabili numericheil cui dominio`elimitatoaduninsieme di valoridiscreti,per cui si pu` o operare su di esseconle usuali ope-razioni aritmetiche. In questa e nelle successive sezioni mostreremo ulterioriesempiincuiquestadoppianaturavienesfruttata.Una variabile che pu` o assumere solo alcuni, specici, valori `e detta varia-bile avaloridiscreti. Si pensi, ad esempio, a una variabile x che rappresentalavelocit`adi trasmissionefraduenodi collegati damodemedauncavotelefonico: inquestocasoessapu` oassumeresolounodei valori corrispon-denti allevelocit`adei modemincommercio. Per esprimerelacondizionex{v1, v2, . . . , vn}possiamointrodurrenvariabili booleaney1, y2, . . . , yn,incui,perognii,yi= 1sex = vi,eyi= 0altrimenti. Ivincolin

i=1yi= 1yi {0, 1} i = 1, . . . , ngarantisconochelax,espressacomex =n

i=1viyi,assumaunosolodeglinpossibilivalori. Vediamoadessounesempiodiusodiquestevariabili.1.2.6.1 ProgettodiretiSi voglionocollegarele reti fognarie di alcuni centriresidenziali e industrialiadunimpiantodi depurazioneesmaltimento. Ogni centroproduceunaquantit`anotadi riuti (liquidi), ed`enecessariodimensionareopportuna-mentelimpiantodi collegamentoal depuratoreinmododaconsentirneiltrasporto. Si possono scegliere condotte di diversa portata e il costo di messainoperadiunacondottasar` aunafunzionedellasuaportata.Si consideri ad esempio il grafo G = (N, A) di gura 1.3(a) dove i nodi da1 a 4 rappresentano i centri edil nodo 5 rappresenta il depuratore. Accantoadogni nodo`e indicatalaquantit`adi liquidodadepurareper unit` aditempoprodottadal centroadessocorrispondente. Ogni arco(i, j) Arappresentaunpossibilecollegamento; fradiessiandrannosceltiquellicheverrannoeettivamentecostruiti, eperciascunodei collegamenti costruitisidovr`adeterminarelaportata. Osserviamocheicollegamenti hannounadirezionepressatadipercorrenza.32 CAPITOLO1. PROBLEMIEMODELLI(a) (b)115310.54210.5121.5115310.5421Depuratore DepuratoreFigura1.3: ProgettodiunaretefognariaUnasoluzioneammissibile`edatadauninsiemedicollegamenti chega-rantiscanoil uiredei liquidi datutti i centri noal depuratore. Ingura1.3(b)`erappresentataunapossibilesoluzione.Forniamounadescrizioneanaliticadel problemamediantedellevaria-bili quantitativexij, unaperogni arco(i, j) del grafo, cherappresentanolaquantit`adiriutiliquidiinviati daiaj, nellunit`aditempo,lungotalecondotta. Essesonochiaramentevincolateadesserenonnegative; ilvalorexij= 0indicachesi`edecisodinonutilizzarelarco(i, j). Dobbiamoades-sointrodurredei vincoli chegarantiscanochei riuti prodotti daciascuncentrogiungano al depuratore. I riuti, per giungere al depuratore, dovran-nopassareperqualcunadellecondottecheviarrivanodirettamente,dovr`aesserex15 +x25 +x35= 3.5 .Vincoli analoghi possono essere scritti per i nodi corrispondenti agli altricentri;inquestocaso,per` o,`enecessariotenereincontoanchedelussoinuscita dal nodo. In altri termini, per ogni centro occorre garantireche tuttoil ussochevi giunge, siaquelloivi prodottochequellocheloattraversaproveniendodaaltri centri, siainviato, attraversoqualcunadellecondottecheesconodalnodo, o direttamentealdepuratore ocomunque adun diver-socentro, dal qualepoi sar` aulteriormenteinstradatonoaraggiungereildepuratore. Adesempioperilnodo3sihax23 +x43 + 1 = x35,mentreperilnodo1sihax21 + 1 = x15.Perinodichehannosolamentearchiuscenti,2e4,ivincolisaranno1 = x21 +x25 +x23, 0.5 = x43.Il costodi posa della condottacorrispondente allarco(i, j)dipende fon-damentalmentedallaportatadellacondottaedallalunghezzadeltrattoda1.2. MODELLI 33compiere. Sesupponiamochesianodisponibili condottedi qualsiasi por-tata, possiamopensarediinstallare, suogniarco, unacondottadiportataesattamentepari aquellarichiestadal ussodei riuti, inquantononsiavrebbenessunvantaggioafarealtrimenti. Sesupponiamoinoltrecheilcostodellacondottadipendalinearmentesiadallalunghezzadel trattodacompierechedallaportata,abbiamocheilcostodiinstallareunacondottasucienteadinviarelaquantit`adiriutixijdalcentroialcentrojattra-versolacondottacheliuniscedirettamente`ecijxij,dovecij= lij,lij`elalunghezzadel trattodai aj e`eil costoperunit` adi lunghezzadi unacondottadi capacit` aunitaria. Inquestocasoil problemadel progettodiretipu` oessereformulatocome2min c15x15+c21x21+c23x23+c25x25+c35x35+c43x43x15+x21= 1x21x23x25= 1+x23x35+x43= 1x43= 0.5x15+x25+x35= 3.5x15, x21, x23, x25, x35, x43 0Ingenerale,per` o,acausadelleeconomiediscalailcostodiposadiunacondottasar` auna funzione concavadeltipodi quellaindicataingura 1.4.Inascissasihailvalorexdellasezionedellacondottaeinordinatasihailcostof(x)dellaposainoperadellacondotta;adogni(i, j) A `eassociatauna funzione fij(x) che fornisce il costo globale dellacquisto e posa in operadellacondottaconportataxlungotuttoiltrattodaiaj. Sesupponiamochesianodisponibilicondottediqualsiasiportata,ilproblemadiventamin f15(x15) +f21(x21) +f23(x23) +f25(x25) +f35(x35) +f43(x43)x15+x21= 1x21x23x25= 1+x23x35+x43= 1x43= 0.5x15+x25+x35= 3.5x15, x21, x23, x25, x35, x43 0Si notichequestoproblemahaunafunzioneobiettivononlineare. Nellarealt` a,per` o,lecondottesonosolitamentedisponibilisoltantoinunnumeronitodi portatediverse; nel nostroesempio, supponiamochelecondottesonodisponibiliintresoledimensioni,conportaterispettivamente0.7,1.4e 3. In questo caso non possiamo pi` u supporre che la portata della condotta2Si noti che, portando nel latosinistro di ogni equazione tutte le variabilie nel latode-stro le costanti,si ottiene che tutte le variabili corrispondenti adarchi entranti inun nodoappaiono nel vincolo corrispondente con segno negativo, mentre tutte quelle corrispondentiadarchiuscentidallostessonodoappaiononelvincoloconsegnopositivo.34 CAPITOLO1. PROBLEMIEMODELLIxf(x)Figura1.4: Funzionecostoinstallatasiaugualeallaquantit`adiriutieettivamenteinviati: potrebbeinfattiesserenecessarioinstallarecondottedi portatamaggiore. Perquestointroduciamo un altro insieme di variabili quantitative yij, una per ogni arco(i, j)delgrafo,cherappresentanolaportatadellacondottainstallatatrailnodo i ed il nodo j (0 se non viene installata nessuna condotta). Ovviamente,occorreinserireivincolixij yij, (i, j) A,che garantiscono che la quantit`a di usso inviata lungo ogni condotta non siasuperioreallaportatadellacondottaeettivamenteinstallata. Unmodelloanaliticodelnostroproblemadiprogettodiretidiventamin f15(y15) +f21(y21) +f23(y23) +f25(y25) +f35(y35) +f43(y43)x15+x21= 1x21x23x25= 1+x23x35+x43= 1x43= 0.5x15+x25+x35= 3.50 xij yij(i, j) Ayij {0, 0.7, 1.4, 3} (i, j) APossiamoadessotrasformarequestoproblemainmododasostituirelevariabili quantitative yij, vincolate ad assumere un insieme discreto di valori,convariabilibinarie. Peresprimereilvincoloyij {0, 0.7, 1.4, 3},introduciamo,perogniarco(i, j), trenuovevariabilibooleaney1ij,y2ijey3ijesostituiamoilvincoloconyij= 0.7y1ij+ 1.4y2ij+ 3y3ij(1.15)y1ij+y2ij+y3ij 1 (1.16)y1ij, y2ij, y3ij {0, 1}1.2. MODELLI 35Utilizzandoivincoli(1.15)possiamopoisostituireyijovunquecon0.7y1ij+ 1.4y2ij+ 3y3ij,eliminando cos` tutte le variabili yijed i vincoli (1.15) dal problema. Questoci consente anche di ottenere nuovamente unafunzioneobiettivolineare:infattisihachefij(0.7y1ij+ 1.4y2ij+ 3y3ij) = fij(0.7)y1ij+fij(1.4)y2ij+fij(3)y3ije quindi il problema del progetto di reti pu` o essere modellato come unproblemadiProgrammazioneLineareIntera.Sinotiche,difatto, inquestocasononsiamointeressatialvaloredellefunzioni fijintutti i punti, maai lorovalori nei punti di ascissa0.7, 1.4e3. Ineetti,`epossibileformulareilproblemaeliminandocompletamentelevariabili relativeallecondotte, econsiderandocomecostoper il ussoxijchepassaperlarco(i, j)ilcostodellapi` upiccolasezioneincommerciosucienteatrasportarequellaquantit`adi usso. Di conseguenza, il costodel usso ha la forma, detta agradini,della funzione mostratain gura 1.5.xf(x)0.7 1.4 3.0Figura1.5: UnafunzionecostoagradiniNel seguitoverr` amostratocomerappresentarequestotipodi funzionimediantefunzionilinearievariabilibinarie.1.2.7 Minimaquantit`apositivapressataSpessonellapianicazionedellaproduzione(otrasporto)dibeni, si haundoppiolivellodidecisione: il primosullaproduzioneomenodel bene, eilsecondo livellosulla quantit`a di beni da produrre allinternodi un intervallo[l, u], conl >0. Inpraticasi hache lavariabile x, che rappresentalaproduzione, pu` o assumere valori solamente nellinsieme {0, [l, u]},cio`e x = 0rappresentaladecisionedi nonproduzione, mentrex[l, u] indicalaproduzioneincasodidecisionepositiva.Permodellarei valori chexpu` oassumere, introduciamounavariabilelogicaycheassumeilvalore0sesidecidedinonprodurre,eilvalore1sesi `edecisodiprodurre. Possiamoallorascrivere:36 CAPITOLO1. PROBLEMIEMODELLIly x uy, y {0, 1}, x R;infatti, sey=0, lavariabilex`eforzataadassumereil valore0, mentresey= 1,essapu` oassumereunqualsiasivalorerealenellintervallo[l, u].1.2.8 FunzioneconcaricossoSi consideri la seguente funzione concarico sso che si vuole minimizzare:f(x) =

0 sex = 0,b +cx se0 < x u,(1.17)dove `eb > 0eu `eunopportunorealepositivo(sivedaanchelagura1.6).cubxf( x )Figura1.6: unafunzioneconcaricossoLafunzionecostof(x)comparespessonei problemi di produzione: senon si produce (x = 0) non vi `e costo (f(x) = 0); se si decide di produrre (conillimitedellacapacit` aproduttiva u) allorasi ha un costodi investimentob,ssoedindipendentedallaproduzione,euncostodiproduzionec>0perunit` adiprodotto.Per rappresentareanaliticamente unatalefunzioneconcava nellinter-vallo[0, u],analogamenteaquantofattonelcasoprecedente,introduciamolavariabiledecisionaleycol seguentesignicato: y=0implicax=0ey= 1implicax 0. Lecondizionicheleganolavariabilexallaysono:0 x yu , y {0, 1} , x R.Si noti che il limite superiore u`e essenziale nellaformulazione. Neicasi pratici `esemprepossibileintrodureunvalorenitochesiaunlimitesuperioreaivalorichelavariabilexpu` oassumere.Possiamoorasostituirelafunzionef(x)conunanuovafunzione:1.2. MODELLI 37g(x, y) = by +cx;infatti, quandoy =0si hag(0, 0) =f(0) =0, mentre quandoy =1si hag(x, 1) =b + cx. Osserviamochei vincoli introdotti nonescludonolapossibilit`achesiacontemporaneamentey=1ex=0, inquestocasoavremmog(0, 1) =f(0). Quindi lag(x, y) nonriescearappresentareinmodounivocof(x);tuttavia, poicheilnostroobiettivo`eminimizzaref(x)equindig(x, y),lasoluzione(x, y) = (0, 1)vieneesclusaessendog(0, 1) = b > g(0, 0) = 0 = f(0).Naturalmente, la formulazione proposta non sarebbe adeguata se lobiet-tivofosselamassimizzazionedellafunzionef(x).Esercizio1.14Disegnare e descrivere analiticamente la funzione f(0) = 0,ef(x) = 180 + 2xper0 < x 250.1.2.9 VincolidisogliaNegli esempi precedenti, abbiamovistocomevariabili binarieequantita-tivepossanoessereutilizzatenegli stessi vincoli. Si trattavacomunquedivariabili decisionali, ossiacherappresentanodecisioni eettivedel proble-ma,siapureditipodiverso. Ingenerale, tuttelevariabilidiunmodellosonovariabili decisionali; pu` oinalcuni casi farcomodo, per` o, distingueretralevariabili strutturali delmodello,quellecheriettonoledecisionifon-damentali daassumere, elevariabili ausiliarie, quellechesonointrodottenel modello col solo scopo di permettere la formulazione di qualche specicacondizione. Adesempio,possonoessereconsiderateausiliarielevariabiliyjnelproblema(MCMS)(si vedailParagrafo1.2.4.2), inquantoledecisionifondamentali (quali lavori assegnareaquali macchine, e, di conseguenza,quali macchine vengono utilizzate)sono gi`a rappresentate dalle variabili xij;levariabiliyjservonosolamenteadesprimerelafunzioneobiettivo.Inmoltiproblemisihabisognodirappresentaredeivalorisogliame-diante variabili e vincoli lineari. Pi` u formalmente, siano x1, x2, . . . , xn,variabili reali; si voglionodenireduevariabili l educhesianounaap-prossimazione rispettivamente per difettoe per eccessodi ciascunadellevariabili:l min{xi: i = 1, . . . , n};u max{xi: i = 1, . . . , n}.Talicondizionisonofacilmenteottenutemediante:l xi, u xi, i = 1, . . . , n;38 CAPITOLO1. PROBLEMIEMODELLIinfatti,lsar` a nonsuperiore edu sar` anoninferioreaciascunadellenvaria-bili. Sesi massimizzal osesi minimizzau, allottimoessesarannougualirispettivamente al massimo e al minimo dei valori assumibili dalle n variabili.Vediamooraunapplicazionedei vincoli di sogliarelativamente adunaltroproblemadiordinamentodilavorisumacchine.1.2.9.1 Ordinamentodi lavori sumacchine: minimizzazionedeltempodicompletamentoQuesto problema `e una variante di (MCMS) (si veda 1.2.4.2)in cui il tempodi iniziodi ciascunlavoronon`e ssato, e pu` oessere decisosenzaalcunvincolo.`Einvecessatoilnumerodimacchinedautilizzare, esichiededicompletaretuttiilavorinelminortempopossibile.SeN(j)`elinsiemedei lavori assegnati allamacchinaj, j=1, . . . , m,allorailtempodilavoroD(j)dellamacchina`eD(j) =

iN(j)di.Il tempodicompletamentoT,da minimizzare, `eilmassimo deitempi dilavorodellemacchineT= max{D(j) : j= 1, . . . , m} ,ossiailtemponecessarioallamacchinapi` ucaricaperterminare.Utilizziamo le stesse variabili xijutilizzate in (MCMS); useremo i vincolidi semi-assegnamento(1.10), assiemeai vincoli di integralit` a, perimporrecheciascunlavorosiaeseguitodaunaedunasolamacchina.Per formulare lafunzione obiettivo, daminimizzare, dobbiamoespri-mereil massimotramquantit`a. Per questoutilizziamolatecnicaappe-naintrodottaedintroduciamounanuovavariabilet cherappresentaunaapprossimazionepereccessodeltempodicompletamento:n

i=1dixij t, j= 1, . . . , m.La formulazione risultante del problema (MMMS, da Minimal MakespanMachineScheduling)`e:(MMMS)min tm

j=1xij= 1 i = 1, . . . , nn

i=1dixij t j= 1, . . . , mxij {0, 1} i = 1, . . . , n, j= 1, . . . , m1.2. MODELLI 39Comeabbiamogi`anotato, quandoil problema`erisoltoallottimolavariabileausiliariatfornisceiltempodicompletamentoenonunasuaap-prossimazione;infatti,seperassurdo siavesset > D(j), j= 1, . . . , m,siot-terrebbe un valore inferiore della funzione obiettivo ponendo t = max{D(j) :j= 1, . . . , m}.Esercizio1.15Costruire unistanza del problema (MMMS) con 3 macchinee7lavori,denendoleduratediessi;formularequindilistanza,forniretresoluzioniammissibilievalutarneil tempodicompletamento.Esercizio1.16Unadittadicostruzioniediliziehadecisodisubappaltarendiverseopereadndiversiartigiani. Adogniartigianoi = 1, . . . , nchiededifornireil costopreventivocijcherichiedepereettuareloperaj, perognij=1, . . . , n. Si vuoleassegnareunoperaaciascunartigianoinmodochetutteleoperesianoeettuateeilcostomassimodeisubappaltiassegnatisiaminimizzato. Formulareil problema.Esercizio1.17Siprovioraamassimizzareil costominimodeisubappaltiassegnati.Esercizio1.18Si formuliilproblemain cui sivuole che ladierenzatrailmassimoeilminimocostodeisubappaltiassegnatisiapi` upiccolapossibile.Esercizio1.19Siano a1, . . . , annumeri reali positivi. Partizionaretali nu-meriindueinsiemiIeJinmodotalechelesommedeivaloriassegnatiaciascunsottoinsiemeabbianolaminimadierenzainvaloreassoluto.1.2.10 ComerappresentareilvaloreassolutoPu`ocapitaredidovertrattareunvincolodeltipo:|g(x)| b , (1.18)doveg(x)`eunafunzionedellinsiemedi variabili xeb`eunnumerorealepositivo. Seg(x) 0allorailvincolodivieneg(x) b,mentreseg(x)< 0ilvincolodivieneg(x) b. Pertanto,perrappresentareilvincolo(1.18)`esucienteconsiderareiseguentiduevincoli:g(x) b; g(x) b .Vediamooracometrattareunafunzione obiettivoespressa medianteunvaloreassoluto. Si suppongadi dovermassimizzare|f(x)|, conxX.`Esucienterisolvereiduediversiproblemimax{f(x) : x X},max{f(x) : x X},40 CAPITOLO1. PROBLEMIEMODELLIe prendere come soluzione quella che fornisce il valore pi` u alto della funzioneobiettivo.Se f(x) `e una funzione lineare nella singola variabile x, cio`e f(x) = b+cx,allorabastasostituireallaf(x)lafunzionelineareatrattig(x) =

b cx, x b/c,b +cx, x > b/c;chepu` oesseretrattataconletecnichecheverrannospiegatenelparagrafo1.2.11.Esercizio1.20Formulareil problemamin{|3 4x| : |x| 2}.1.2.10.1 MinimadistanzaDatouninsiemeXRn, si vuoledeterminareil pi` upiccoloelementodi X, ossialelemento di Xche minimizzaunaqualche norma. Questoproblemahanumeroseapplicazioni, adesempioinstatisticaedingegneria.La sua versionedecisionaleconsistenel determinarese linsiemeXcontieneunelementodi normaminoreougualeak, cio`eselasfera(nellanormaprescelta) avente centronellorigineeraggiokhaintersezione nonvuotaconX; uncasoparticolaremoltorilevante`equelloincui k=0, cio`e sivuoledeterminareseXcontienelorigine.Lenormepi` ucomunementeusatesonoL1(x) =n

i=1|xi| ,L2(x) =

n

i=1x2i,L(x) = max{|xi| : i = 1, . . . , n} .NelcasoincuiXsiaunpoliedroconvesso,ossiaX= {x : Ax b} ,ilproblemadiminimadistanzacorrispondentealleL1oL`eunproblemadi PL. Infatti, il problema di minima distanza pu` o essere scritto nei due casicome(PMD1)minn

i=1vivi xi vii = 1, . . . , nAx b(PMD)min vv xi v i = 1, . . . , nAx b1.2. MODELLI 411.2.11 Funzionilineari atrattiConsideriamolaseguentefunzionef(x):f(x) =

b1 +c1x sex [a1, a2],b2 +c2x sex (a2, a3].doveassumiamob2 +c2a2 b1 +c1a2. (1.19)La funzione f(x) `e denita nellintervallo[a1, a3] ed `e la composizionediduefunzionilinearideniteneiduesottointervalli[a1, a2]e(a2, a3](sivedaunesempioingura1.7). Ilcasoprecedentedellafunzioneconcaricossopu` o essere visto comeun casoparticolare,in cui il primo intervallosi riduceadununicopunto.f(x)c2c1x a1a3a2b1+c1a1b1+c1a2b2+c2a2b2+c2a3Figura1.7: UnafunzionelineareaduetrattiIntroduciamoduevariabilibooleaney1ey2conilseguentesignicato:y1=

1, sex [a1, a2],0, altrimenti,y2=

1, sex (a2, a3],0, altrimenti.Dovendo x appartenere a uno ed uno solo dei due sottointervalli,occorreaggiungereilvincoloy1 +y2= 1aivincoliy1, y2 {0, 1};alternativamente,sipotrebbe sostituire1 y1ay2(leduevariabilisonocomplementari).Si noti che se x [a1, a2] possiamo porre x = a1+z1,dove z1(= xa1)non`ealtrochelaporzionedi valoredi xchesuperaa1, pertantoil suovalore`elimitatodalledisuguaglianze0z1a2 a1. Analogamente, sex (a2, a3],poniamo x = a2 +z2, dovez2ha un signicatoanalogoa quello42 CAPITOLO1. PROBLEMIEMODELLIdi z1, con 0 < z2 a3a2. Considerato il signicato delle variabili booleaney1ey2,possiamoscrivere:x = a1y1 +z1 +a2y2 +z2,purchesianorispettatiiseguentivincoli:0 z1 (a2a1)y10 z2 (a3a2)y2y1 +y2= 1y1, y2 {0, 1}(1.20)Ivincoli(1.20)impongonochesolounadelleduevariabiliz1ez2possaaverevalorenonnullo. Sinotichelacondizionez2 0permettedidenireil valorex=a2anchenel casoincui y2=1; torneremosuquestocasoinseguito.Sostituiamoallafunzionef(x)laseguentefunzione:g(z1, z2, y1, y2) = b1y1 +c1(a1y1 +z1) +b2y2 +c2(a2y2 +z2)= (b1 +c1a1)y1 +c1z1 + (b2 +c2a2)y2 +c2z2.conlevariabili soggetteai vincoli (1.20). Abbiamoespressounafunzionenonlinearef(x) comeunafunzionelineareg(z1, z2, y1, y2) denitasuunopportunoinsieme.Discutiamooralambiguit` adellafunzioneg(z1, z2, y1, y2)nel puntoa2:x = a2pu` o essereespresso siaponendo z1= a2a1, y1= 1, z2= y2= 0cheponendoz1=y1=z2=0, y2=1; chiaramentesoloil primodei duecasi`eaccettabile. Analogamenteaquantoosservatoperlafunzioneconcaricosso nel paragrafo precedente, se si vuole minimizzare f(x), per lassunzione(1.19)sihag(0, 0, 0, 1)= b2 +c2a2 b1 +c1a2= g(a2a1, 0, 1, 0),equindi, x=a2fosselasoluzioneottima, lasoluzionez1=a2 a1, y1=1, z2= y2= 0risulterebbecomunqueottima,nonostantelambiguit` a.Si noti che, sef(x)fossecontinuain[a1, a3], cio`esefosseb2 + c2a2=b1 + c1a2, alloranonsarebbescorrettoconsiderareil valorea2inentrambii casi (cio`eil secondointervallosarebbe[a2, a3]); nonessendovi ambiguit` asul valore di f(x) in a2, inquesto casola funzione g(z1, z2, y1, y2) pu` o essereanchemassimizzata.La trasformazione presentata pu` o essere generalizzataal caso di funzionilineariatrattidenitesupi` udidueintervalli:f(x) =b1 +c1x, sex [a1, a2],b2 +c2x, sex (a2, a3],...bn +cnx, sex (an, an+1],1.2. MODELLI 43concondizionianaloghea(1.19)neipuntididiscontinuit` a.Lafunzioneinsostituzionedif(x) `eg(z1, . . . , zn, y1, . . . , yn) =n

i=1(bi +ciai)yi +n

i=1cizi,conlevariabilisoggetteaivincoli:0 zi (ai+1ai)yi, i = 1, . . . , n,n

i=1yi= 1yi {0, 1}, i = 1, . . . , n.Ilvaloredellavariabilex `edatoda:x =n

i=1aiyi +n

i=1zi.Esercizio1.21Siadatalaseguentefunzione:f(x) =1 + 2x, sex [0, 2],8 x, sex (2, 5],3, sex (5, 6],2 +x/2, sex (6, 10].Disegnaref(x)efornirelaformulazioneanaliticadel corrispondentepro-blemadiminimizzazionedif.Lanecessit`adi utilizzarevariabili binarieper rappresentarelefunzio-ni lineari atratti degli esempi precedenti derivadallalorononconvessit` a;laformulazionetrasferiscelanonconvessit` adel problemadallafunzio-neobiettivoallinsiemeammissibilepermezzodellevariabili avalori inte-ri. Questonon`enecessarioqualoralafunzionesiaconvessa, comequellamostrataingura1.8. Anche ci`oaccada, devonoesserevericate duecondizioni: f deveesserecontinua, ossiabi+1+ ci+1ai+1=bi+ ciai+1per i =1, . . . , n 1; laderivatadi f (nei tratti lineari)deveesserenondecrescente, ossiaci+1 ciperi = 1, . . . , n 1.Inquestocaso, laminimizzazionedi f(x)pu` oessereequivalentementeespressamediantelaminimizzazionedig(z1, . . . , zn) = b1 +n

i=1cizi44 CAPITOLO1. PROBLEMIEMODELLIf(x)c3c2c1x a1a3a2a4b1+c1a1b2+c2a2b3+c3a3Figura1.8: Unafunzionelineareatrattieconvessasoggettaaivincoli0 zi ai+1ai, i = 1, . . . , n;ilvaloredellavariabilex `edatodax = a1 +n

i=1zi.Infatti,seallottimolavariabileoriginariaxdeveavereilvalore x,talevalore dovr`a essere costruito aumentando il valore di alcune delle variabilizi nche la loro somma non dia xa1. Ma siccome la derivata della funzione `enon decrescente, `e chiaramenteconvenientefar crescere prima il valore dellavariabilizidiindicepi` ubasso;inaltritermini,inunasoluzioneottimadelproblemasiavr`acertamentechezi= ai+1ai, i < h,zh= x ah,zi= 0, i > h,dove h `e il pi` u piccolo indice tale che x ah. Si noti che questa propriet`a nonvale nel caso in cui fnon sia convessa,o nel caso in cui venga massimizzata;una formulazionesenza variabili binarie, analogaa questa, `e possibile per lamassimizzazionema non per la minimizzazionedi funzioni lineari a tratticoncave,ossialacuiderivatasianoncrescente.1.2. MODELLI 451.2.12 VincolidisgiuntiviCome abbiamovisto, nei modelli di Programmazione Lineare (Intera) sihannounnumeronitodivincolilinearideltipoAix bi, i = 1, . . . , m (1.21)cheindividuanounpoliedroconvesso. Adesempio,linsiemedivincolix1+ x2 2x1 3x2 1x1 0x2 0denisceilpoliedrodiverticiA,D,G,CinFigura1.9.ACBEDF x1x2GFigura1.9: RappresentazionedipoliedrinonconvessiSupponiamo ora che la regione ammissibile che si vuole rappresentare siatutta quella grigia: si tratta di una regione non convessa, che pu` o essere rap-presentatacomelunione(invecedellintersezione)didueregioni(poliedri),quella denita dal primo vincolo e da quelli di non negativit`a (il triangolo divertici A, B e C) e quella denita dal secondo e dal terzo vincolo e, di nuovo,dai vincolidi non negativit`a(ilrettangoloA, D, E e F).Anche qui, comeincasi precedenti, si presentaunasceltafraduealternative: lasoluzionechecerchiamoappartieneoal primopoliedro, oppure al secondo. Si parlainquestocasodi vincoli disgiuntivi perchevogliamochelasoluzionesoddis(almeno)unofradueinsiemidivincoli. Perrappresentarevincolidiquestotipo `enaturaleintrodurre duevariabilibinariey1edy2,conlaconvenzionechey1= 0signicachexappartienealprimoinsiemeey2= 0signicache46 CAPITOLO1. PROBLEMIEMODELLIxappartieneal secondoinsieme. Possiamoquindi rappresentarelinsiemeammissibilepermezzodelsistemadivincolix1+x2M1y1 2x1M2y2 3x2M2y2 1x1 0x2 0y1+y2 1y1, y2 {0, 1}purcheM1edM2sianonumeri sucientementegrandi. Inparticolare,sirichiedecheM1rendaridondanteilprimovincoloquando y1= 1,ossiacheilvincolox1 +x2 2 +M1sia soddisfatto da tutti i punti che soddisfano tutti gli altri vincoli (un vincolo`eridondantequandolasuaeliminazionenoncambialinsiemeammissibiledel problema). Analogamente, M2 deve essere scelto in modo tale da rendereridondanti il secondoedil terzovincoloquandoy2=1. Si pu` ofacilmentevericareche,inquestocasospecico, `esucienteporreM1= 2eM2= 1.Si noti cheil vincoloy1 + y21assicuracheal pi` uunadellevariabiliabbia valore 1, ossia che almeno uno dei due insiemi di vincoli sia soddisfatto.Pi` uingenerale, consideriamo il caso incui si abbiamo gli mvinco-li (1.21), e che S1, S2, . . . , Spsiano p sottoinsiemi, non necessariamentedisgiunti,dellinsieme{1, 2, . . . , m}. DeniamogliinsiemiXh= {x : Aix bi, i Sh}, h = 1, . . . , p ;cio`e, Xh`elinsiemedituttiipuntichesoddisfanoivincoliicuiindicisonoinSh.ConsideriamooralinsiemeX= X1 X2 . . . Xp. SetuttigliinsiemiXhsonolimitatipossiamorappresentare Xintroducendo p variabilibinarieegeneralizzandolideavistainprecedenzaperilcasop = 2: X`elinsiemedituttiivettorixchesoddisfanoivincoliAix M1y1 bi, i S1Aix M2y2 bi, i S2............Aix Mpyp bi, i Spy1+y2 +yp p 1y1, y2, , yp {0, 1}.Per ogni h = 1, . . . , p, Mh `e una costante tale che tutti i vincoli Aix bi+Mhperi ShsonoridondantipertuttigliinsiemiSk,k= h;unatalecostanteesistecertamenteperchetuttigliinsiemiXksonolimitati.1.2. MODELLI 47Esercizio1.22Sipropongaunaprocedurachepermettadideterminareunvalore opportuno per ciascunacostante Mh(suggerimento: si risolvaunnumeroopportunodiproblemidi PL).Unavarianteinteressante`eil casoincui si vuolechealmenokdegliinsiemidivincolisianosoddisfatti(cio`exappartengaallintersezionedial-menokdegliinsiemiXi, i = 1, . . . , p). Inquestocaso `esucientesostituireal vincolo y1+y2+ +yp p1 il nuovo vincolo y1+y2+ +yp pk.Esercizio1.23Lacasadi produzione di cibi inconservaStellainten-deimmetteresul mercatounanuovalineadi preparati perinsalatedi riso,chiamatiGhiottoRiso,chepossonocontenere,oltreadaltriprodottivege-tali,anche funghetti rosa(nel seguitofr), cipollineovali(co),peperoncinipiccanti(pp)ecrautiindiani(ci);diciascunodiessisidevedeciderelapresenzaequantit` a.La divisione marketing della Stella ha denito 6 diversi standardqualita-tivitalicheil raggiungimentodiciascunodiessifar` aaumentarelevenditedel prodotto. Essisonoespressicome:2xfr+4xco+xpp+3xci 150,xfr+2xco+5xpp+2xci 95,3xfr+xco+2xpp+xci 80,5xfr+3xco+3xpp+4xci 200,xfr+5xco+2xpp+xci 70,4xfr+xco+xpp+4xci 100,dovelevariabilixrappresentanolequantit` aingrammideiquattroprodottichesiintendemetterenel GhiottoRiso. Inoltre,dalleultimeindaginisvoltesullapprezzamentopressolaclienteladeiprodotti delleditteconcorrenti, si`e riusciti a prevedere che, se si riescono a soddisfarealmeno 3 dei 6 standarddiqualit` a,linteraproduzionesar` aassorbitadal mercato.Il costoal grammodei quattroprodotti inquestione`ecfr=12, cco=6, cpp=15, cci=5. Inne, per ciascunodi essi, lamassimaquantit` aingrammichesipu` oimmetterenel GhiottoRiso`e15grammi.Si vuole ottenere la composizione ottimale di GhiottoRiso,cio`e quella cherispetti le indicazioni date e che abbia il minimo costo;formulare il problemaedeterminareunasoluzioneammissibile.1.2.13 UnesempiodiformulazioneealcunieserciziConcludiamoquestaparte dedicataalle tecniche di modellazione conunesempionel qualesi utilizzanoalcunedelletecnicheprecedentementeillu-strate; lusodelletecniche potr` apoi essereautonomamentesperimentatosvolgendogliesercizipropostiallanedelparagrafo.48 CAPITOLO1. PROBLEMIEMODELLI1.2.13.1 DislocazioneottimadiimpiantiLa societ`a informatica MilanNet ha deciso di aprire nel territorio pisano sinoa n possibili uci di assistenza ai suoi m clienti. Per ogni sito i = 1, . . . , n siconosceilcostodidi installazioneeilnumero massimouidiclientichepu` oassisterequalorasiaattivato;inoltre,perognisitoi = 1, . . . , nsiconosceilcostocijdigestireilclientej= 1, . . . , mpressotalecentro.Si vuoledecidereinquali dellenlocalit`aapriregli uci di assistenzae, perciascunodiessilinsiemedeiclienti assegnati, inmodotalecheogniclientesiaassegnatoadunoedunsolouciodi assistenzaecheil costocomplessivo(diinstallazioneegestione)siaminimo.Performularetaleproblemaoccorreintrodurredueinsiemi di variabilibinarie: levariabiliyi,i = 1, . . . , n,perrappresentarelasceltarelativaagliucidaaprire,elevariabilixij,i =1, . . . , n, j=1, . . . , m,perassegnareiclientiagliuci.Lafunzioneobiettivo,daminimizzare,cheincludesiaicostidigestionechequellidiinstallazione`en

i=1m

j=1cijxij+n

i=1diyi.I vincoli di semiassegnamentogarantisconoche ogni clientesia assegnatoadunoedunsoloucio:n

i=1xij= 1, j= 1, . . . , m .Dobbiamopoi aggiungere siai vincoli sul numeromassimodi clienti peruciom

j=1xij ui, i = 1, . . . , n , (1.22)siaquelli chegarantisconochei clienti sianoassegnati aduci di cui siastatadecisalacostruzione:xij yi, j= 1, . . . , m, i = 1, . . . , n . (1.23)Questi ultimi esprimonolimplicazionexij>0yj=1. Perevitarediusaremnvincoli, si pu` oimporrechelasommadellexij, cio`eil numerodiclientiassegnatialsitoi sia nullaquando yi= 0 e possa assumere un valorenonsuperioreauiquandoyi= 1, i = 1, . . . , n:m

j=1xij uiyii = 1, . . . , n .1.2. MODELLI 49Osserviamocheil vincolorelativoallucioi, i =1, . . . , n, implicasiailcorrispondente vincolo (1.22) che i corrispondenti vincoli (1.23). Il problemapu` oquindiessereformulatocomeminn

i=1m

j=1cijxij+n

i=1diyin

i=1xij= 1 j= 1, . . . , m i = 1, . . . , nm

j=1xijuiyi 0 i = 1, . . . , nyi {0, 1} i = 1, . . . , nxij {0, 1} j= 1, . . . , m i = 1, . . . , nEsercizio1.24Formulareunproblemadi installazioneottimadi al pi` u4impianti con11clienti,dandoancheicosti diinstallazioneedigestioneelecapacit` adegliimpianti.1.2.13.2 EsercizidimodellazioneEsercizio1.25LaFintus producetretipi di patatinesurgelate,denominatiA, BeC.Lacompagniaacquistapatatediduetipidiversi,denominatiP1eP2. Idiversitipidiprodottousanopartidiversedellapatataoriginaria,percui1Kgdi patateacquistatodeterminalaproduzionedi unacertaquantit` adi tutti etrei prodotti. I rendimenti dei duetipi di patatasonodiversi,comeindicatonellaseguentetabella:patata/tipo A B CP1.2 .2 .3P2.3 .1 .3IlprottodellaFintus `edi.03EuroalKgperlepatateP1edi.025EuroalKgperlepatateP1: laFintusintendeprodurrenonpi` udi 6.000Kgdi A,4.000KgdiBe8.000kgdi C,massimizzandoil protto. FormularecomePLil problemadiottimizzazionecorrispondente.Esercizio1.26LaziendaCaramelli produceunoliospecialepercosmeti-ci, ottenutodallaranazioneemiscelazionedi oli. Gli oli si dividonoinduecategorie, oli vegetali edoli nonvegetali. Sonodisponibili duediversioli vegetali, cheindichiamoconV1eV2, etrediversi oli nonvegetali cheindichiamoconN1,N2eN3. Icosti(Euro/tonnellata)eladensitdegliolisonoiseguenti:V1V2N1N2N3Costo 110 120 130 110 115Densit` a 8.8 6.1 2.0 4.2 5.050 CAPITOLO1. PROBLEMIEMODELLIGli olivegetali equellinonvegetali richiedonodierentilineediprodu-zioneperlaranazione. Inogni mesenon`epossibileranarepi` udi 200tonnellatedi oliovegetalee250tonnellatedi oliononvegetale. Nonvi `eperditadipesonel processodiranamento, edil costoditaleprocessopu` oessere ignorato. Vi `e invece una restrizionetecnologicasulla densit` a del pro-dottonale: nellunit` adimisuraopportuna,questadeveesserecompresatra3 e 6. Si assume che la densit` a degli oli si misceli nel prodottonale in modolineare. Il prodottonalesar` avendutoa150Euro/tonnellata. FormularecomePLil problemadiprodurreil benemassimizzandoil protto.Esercizio1.27Unindustriadolciariaproduce3diversitipididolci: A,B,C. Si devestabilireil pianodi produzionegiornalierodellindustria, aventeunacapacit produttivamassimadi 10000dolci al giorno, inmodochelaproduzionedi A non eccedail 50% della produzioneglobale giornaliera,e chelaproduzionedi Csiaugualeal pi al 25%dellaproduzionedi B. Sapendoche il guadagnogarantitodallaproduzione di undolce di tipoA, BeC`erispettivamentedi0.2Euro, 0.1Euroe0.4Euro, sivuoleindividuareunpiano di produzioneche massimizzi il guadagno. Si formuli il problema comePLI.Esercizio1.28Unimpresa ha a disposizione tre proced