Mathematical Engineering - Fondamenti di Ricerca Operativa

Modelli

Divided by topic

Fondamenti di Ricerca OperativaEsercizi propostiModelli AA. 2019/2020 Fondamenti di Ricerca Operativapagina 1 Esercizio 1- Smistamento vetture Un’azienda produttrice di automobili deve pianificare lo smistamentodelle vetture in un paese straniero. Le vetture raggiungono il paese via mare e le navi possono attraccare in 3 diversi porti, P1, P 2e P 3. Per ciascun porto si deve pagare una tassa per ciascuna automo bile del carico: nel portoP 1la tassa ammonta a 150 euro per vettura, nel porto P 2a 250 euro per vettura, mentre nel portoP 3la tassa `e di 200 euro a vettura. Inoltre `e prevista una tassa pe r l’utilizzo di ciascun porto, pari rispettivamente a 1500, 1500 e 2000 euro. Le automobili devono essere inviate ai 4 centri di smistamento presenti nel paese,S 1, S 2, S 3e S 4. L’invio di un’automobile dal porto P 1 costa 0.2 euro/Km, l’invio di un’automobile dal portoP 2costa 0.1 euro/Km, mentre dal porto P3costa 1 euro/Km. Le distanze, in chilometri, tra porti e centri di s mistamento sono riportate nella tabella. S1 S2 S3 S4 P1 250 150 100 200 P 2 400 300 300 600 P3 40 15 30 10 La richiesta del centro di smistamentoS 1`e di almeno 170 vetture, quella del centro S 2`e di 130 vetture, quella del centroS 3`e di 100 vetture mentre la domanda di S 4`e di 200 vetture. Per motivi strategici, il centroS 3deve essere fornito da un solo porto. Inoltre se il porto P 2 serve il centro di smistamentoS 2deve servire anche S 4. Sapendo che il porto P 1gestisce al pi`u 350 automobili, il portoP 2gestisce al pi`u 200 vetture mentre il terzo porto gestisce al pi `u 300 vetture, scrivere il modello in programmazione lineare che pianifichi la distribuzione delle vetture minimizzando i costi. Esercizio 2- Compagnia aerea Una compagnia aerea deve organizzare la gestione dei propri voli che atterrano in un dato aeroporto, rappresentati dall’insiemeA. Nell’aeroporto sono disponibili un certo numero di hangar (insiemeH), ciascuno dei quali pu`o contenere un solo aereo. Ogni aereo deve essere assegnato ad un hangar. Per le operazioni da effettuare su ogni aereo sono necessari un certo numero di operatori. Gli operatori sono di tre tipi: operatori comuni, operatori specializzati e operatori addetti al trasporto. Gli operatori sono dipendenti dell’aeroporto e sono raggruppati in tre tipi di squadre fisse: le squadre del primo tipo comprendono 1 operatore comune, 1 operatore specializzato e 1 operatore addetto al trasporto, le squadre delsecondo tipo comprendono 3 operatori comuni e 1 operatore specializzato mentre le squadre del terzo tipo comprendono 3 operatori comuni, 2 operatori specializzati e 1 operatore addetto al trasporto. Per ogni hangar j`e noto il numero di operatori dei tre tipi richiesti, rispettivamentec j, s je t j. Per garantire il numero necessario di operatori, la compagnia aerea deve “noleggiare” un certo numero di squadre: il costo di una squadra del primo tipo `eg 1, il costo di una squadra del secondo tipo `e g2, mentre il costo di una squadra del terzo tipo `e g 3. Per motivi contrattuali, se la compagnia richiede 3 o pi`u squadre di tipo 2 deve richiederne almeno 2 di tipo 3.Formulare il modello in programmazione lineare con l’obiettivo di minimizzare la spesa totale per le squadre di operatori. ModelliProf. Giuliana Carello Fondamenti di Ricerca Operativapagina 2 Esercizio 3- Azienda alimentare Un’azienda alimentare produce due prodotti,p 1e p 2. Per ciascun prodotto j= 1,2 sono noti il prezzo di venditar je la domanda minima da soddisfare d j. I due prodotti hanno bisogno di un certo insieme, indicato daI, di materie prime. Per ogni materia primai∈ I`e nota la disponibilit`ac i(espressa in unit`a di materia prima), e il costo unitario g i. Per produrre un’unit`a di prodottop 1sono necessari q 1iunit`a della materia prima ieo 1ore di manodopera. Il prodotto p2pu`o essere ottenuto sia a partire dalle materie prime, sia lavorando ulteriormente il prodotto p1. Nel primo caso sono necessarie q 2iunit`a di materia prima ieo 2ore di manodopera, nel secondo caso non sono necessarie materie prime, mabunit`a di prodottop 1e o 3ore di manodopera. Inoltre se si attiva il secondo processo produttivo`e necessario pagare un costo fisso di attivazionek. L’azienda ha a disposizione al massimoOore di manodopera. Scrivere il modello in programmazione lineare del problema di pianificare la produzione con l’obiettivo di massimizzare il profitto (differenza tra guadagno e spesa). Esercizio 4- Tour Operator Un tour operator deve organizzare il trasporto diTgruppi di turisti. I gruppi di turisti devono viaggiare uniti, poich´e hanno acquistato viaggi di gruppo. Ogni gruppoi∈ {1, .., T}comprende pipersone. Il tour operator pu`o scegliere quali aerei noleggiare t ra un insieme dimaeromobili. Noleggiare l’aereojha un costoc j, con j= 1, . . . , m. Per ogni aereoj`e nota la capienzaB j. Oltre a scegliere quali aerei noleggiare e ad assegnare i gruppi di turisti agli aerei noleggiati, il tour operator deve decidere da quale aeroporto far partire ogni aereo effettivamente usato, avendo a disposizione un insiemeAdi possibili aeroporti. Per ogni aeroportok∈ A`e noto il numero massimo di voliG kche il tour operator pu`o far partire dall’aeroporto. Per ogni aer eo je per ogni aeroportok`e dato il costol jkdi far partire jdak. Per motivi di praticit`a il tour operator non vuole usare aeroporti vicini. Sono dati perci`oRsottoinsiemi di aeroporti vicini: per ogni sottoinsiemeS r, con r= 1, . . . , R, il tour operator vuole usare al pi`u un aeroporto. Scrivere il modello in programmazione lineare del problema di assegnare i gruppi di turisti agli aerei e gli aerei noleggiati agli aeroporti, rispettando i limiti di capacit`a degli aeromobili e degli scali, con l’obiettivo di minimizzare i costi totali. Esercizio 5- Scuola di ballo Il direttore di una scuola di ballo da sala deve organizzare le classi per un corso estivo di perfezionamento. La scuola ha ricevuto delle domande di iscrizione (insiemeP), di cui un certo numero (sottoinsiemeM) proviene da uomini e un certo numero (sottoinsiemeF) da donne, conM∪F=P. Per poter garantire una buona qualit`a dell’insegnamento ogni classe deve contenere al pi`unpersone e ogni classe deve avere lo stesso numero di donne e di uomini. Visto il numero limitato di aule a disposizione, al massimo si possono averedclassi. Dal momento che si tratta di un corso di perfezionamento, il direttore vuole che ogni classe abbia un certo livello di partenza. Ad ogni iscrittoi∈P`e stato assegnato un coefficienteb iche ne indica la preparazione: ogni classe deve avere un livello medio almeno pari aq. A causa dei limiti di spazio non sar`a possibile accettare tutte le domande. Alcune persone si sono iscritte in coppia: l’insieme delle coppie gi`a formate `e descritto da un insiemeC: ogni elemento diC`e una coppia (i, j) dovei∈Mej∈F. Il direttore ha deciso di non separare una coppia gi`a affiatata: se un elemento di una coppia viene accettato nel corso deve essere accettato anche l’altro e i due ModelliProf. Giuliana Carello Fondamenti di Ricerca Operativapagina 3 devono stare nella stessa classe. Il direttore vuole soddisfare quante pi`u richieste di iscrizione `e possibile. Formulare il modello del problema in Programmazione Lineare. Esercizio 6- Raffineria Una raffineria comprendeNaltiforni, che possono eseguire due tipi di lavorazioni a partire da un’unica materia prima. Un altofornoi= 1, . . . , Npu`o lavorare al massimom iquintali di materia prima. Entrambe le lavorazioni producono un insieme diPprodotti, ma in quantit`a diverse. La quantit`a di prodottoj= 1, . . . , Pottenuto a partire da un quintale di materia prima `e pari aq 1jse si esegue la prima lavorazione, e pari a q 2jse si esegue la seconda lavorazione. Il mercato richiede una quantit`ar jdi prodotto j. Il costo di lavorazione di un quintale di materia nell’altofornoi`e pari ac ieuro se si esegue la lavorazione 1, e pari a g ise si esegue la lavorazione 2. L’attivazione della seconda lavorazione prevede un costof iper ogni altoforno i. Passare da una lavorazione all’altra richiede un certo tempo di setup, che si vuole evitare. Si deve perci`o evitare che un altoforno passi da una lavorazione all’altra. Per motivi di sicurezza non `e possibile che tutti gli altiforni eseguano la lavorazione 2. Si richiede inoltre che almeno un altoforno lavori pi`u diqquintali di materia prima. Formulare il modello di programmazione lineare intera con l’obiettivo di minimizzare il costo totale della produzione. Esercizio 7- Cioccolateria Una cioccolateria produceCtipi di cioccolatini diversi (fondenti, al latte, all’arancia, ecc.). Per San Valentino ha deciso di preparare delle confezioni regalo. Vuole offrire confezioni regalo diverse per costo e contenuto ai suoi clienti: ha selezionatoSpossibili confezioni regalo. Per ogni tipo di confezionej= 1, . . . , Se per ogni tipo di cioccolatinoi= 1, . . . , C,r ij`e il numero di cioccolatini di tipoiche devono essere messi nella confezione di tipoj. I cioccolatini non inseriti in confezioni sono venduti sciolti. Per ogni tipo di cioccolatinoi`e noto il costo di produzione del cioccolatino,g i, il numero massimo di cioccolatini che si possono produrre, m ie il prezzo di vendita del cioccolatino venduto sfuso,p i. Il prezzo totale di vendita di una confezione di tipo j`ed j. Per preparare la confeziona `e necessaria la scatola: le scatole ve ngono acquistate da un grossista di imballaggi. Una scatola necessaria per una confezione di tipojcostab j. Se vengono acquistate pi`u diqscatole, il grossista scontaBeuro. Scrivere il modello in programmazione lineare intera del problema di decidere la produzione con l’obiettivo dimassimizzare il profitto, ovvero la differenza tra ricavi e costi, sapendo che la cioccolateria vuole che almeno il 20% dei cioccolatini prodotti sia del tipo 1, poich´e sono i pi`u richiesti. Esercizio 8- Allenatore L’allenatore di una squadra di splugo deve decidere la formazione della squadra per le prossime due partite. Ogni formazione deve contenereDdifensori eAattaccanti. L’allenatore ha a disposizioneGgiocatori. Per ciascun giocatorei∈Gun parametror idice se i`e un attaccante o difensore: sei`e un attaccanter i= 1, altrimenti r i= 0. Per ogni giocatore i`e noto il suo valorev i. Si vuole che il valore complessivo di ciascuna delle due formazioni sia almenoB, e che almenoqgiocatori non giochino entrambe le partite. L’allenatore vuole massimizzare il valore della squadra di minor valore. ModelliProf. Giuliana Carello Fondamenti di Ricerca Operativapagina 4 Esercizio 9- Protezione civile Il responsabile della protezione civile di un’area inondata deve organizzare i rifornimenti di beni di prima necessit`a. I beni, descritti da un insiemeB, devono essere acquistati e stivati nei magazzini della protezione civile (insiemeM) e da essi distribuiti ai luoghi in cui gli sfollati sono stati raccolti (insiemeA). Ogni benei∈Bha un costo unitario di acquistoc i. Un’unit`a di beneioccupa un volumev inel magazzino in cui viene stivata. Ogni magazzino j∈Mha una capacit`a massimab j. L’uso di un magazzino jcomporta una spesaf j, dovuta alla manutenzione del magazzino stesso, che non dipende dalla quantit`a dei beni stivati in esso: il costof jviene affrontato solo se il magazzino viene usato. Il trasporto di un’unit`a di bene, qualunque esso sia, dal magazzinoj∈Malla tendopolik∈Aha un costog jk. Per ogni tendopoli k`e nota la richiesta di beneiche viene indicata condi k . Scrivere il modello in programmazione lineare del problema di decidere di quanto approvvigionare i magazzini e comesoddisfare i bisogni delle tendopoli con l’obiettivo di minimizzare il costo totale. Esercizio 10- Analisi del sangue In un’area urbana sono presenti 4 centri per le analisi del sangueda cui si servono i 5 ospedali presenti nella citt`a. Nella tabella sono riportati i tempi di percorrenza tra ospedali e centri per le analisi, espressi in minuti. C1 C2 C3 C4 O1 10 15 30 45 O2 5 20 15 20 O 3 7 32 10 13 O4 30 28 5 5 O5 6 6 15 25 Ogni ospedale ha un certo numero di analisi giornaliere da eseguire eogni laboratorio di analisi riesce a eseguire al massimo un certo un numero di analisi: il numero di analisi richieste da ciascun ospedale e il numero massimo di analisi che ogni centro pu`osvolgere sono riportati nelle tabelle: ospedale O1 O2 O3 O4 O5 numero analisi 150 100 175 300 145 centro analisi C1 C2 C3 C4 numero analisi 250 275 200 245 Per mantenere una certa equit`a tra i centri di analisi, si vuole che il numero di analisi prodotte dal centroC 1non superi l’80% del numero di analisi prodotte nei centri C 2e C 3, che il centro C2non superi il 60% della analisi eseguite in C 1e C 3e che i centri C 3e C 4non eseguano, da soli, pi`u del 50% delle analisi totali. Si vuole inoltre che l’ospedaleO 2si serva da un solo centro di analisi. Per risparmiare sul costo di trasporto si vuole minimizzare la sommadelle distanze pesate: scrivere un modello in programmazione lineare del problema. ModelliProf. Giuliana Carello