1. MODELLI DI PROGRAMMAZIONE LINEARE - Corsi di Laurea...

Ricerca Operativa

1 Esercizi di programmazione lineare

© Politecnico di Torino Pagina 1 di 30Data ultima revisione 13/12/00 Autore: Federico Dalla Croce

Politecnico di TorinoCeTeM

1. MODELLI DIPROGRAMMAZIONE

LINEARE

Ricerca Operativa




Es. 1Il problema dello zaino

Un gruppo di amici dovendo fare una gita ha deciso di mettere cibie bevande di tutti in un unico zaino da 10 Kg.

Lo zaino può essere riempito con:

F Cioccolata (confezioni da 500 g.)F Succhi di frutta (bottiglie da 1 l.)F Lattine di birra (formato da 0.33 l.)F Panini imbottiti (da 100 g. l'uno)F Acqua minerale (bottiglie da 1 l.)F Pacchi di biscotti (confezioni da 500 g.)

Ricerca Operativa




Dopo un'indagine tra i partecipanti alla gita (si poteva dare un votoda 1 a 100 a ciascuno dei prodotti), sono stati determinati iseguenti punteggi:

F Cioccolata: punti 10F Succhi di frutta: punti 30F Lattine di birra: punti 6F Panini imbottiti: punti 3F Acqua minerale: punti 20F Pacchi di biscotti: punti 8.

Ricerca Operativa




Per non scontentare nessuno si è deciso di portare almeno:F Cioccolata: 2 confezioniF Succhi di frutta: 2 bottiglieF Lattine di birra: 6 lattineF Panini imbottiti: 10 paniniF Acqua minerale: 1 bottigliaF Pacchi di biscotti: 2 confezioni

Formulare il modello di Programmazione Lineare che massimizzi ilpunteggio rispettando il vincolo di capacità dello zaino.

Ricerca Operativa




L'acciaieria PLASTIK deve evadere un ordine di 1000 tonnellate diacciaio INOX. Per questa produzione servono manganese (almenol'1%), cromo (almeno il 18%) e molibdeno (almeno il 2%).I fornitori di metalli non ferrosi vendono, per esigenze di mercato,questi prodotti in tre tipi di confezioni differenti. La primaconfezione contiene 2 Kg. di manganese, 2 Kg. di cromo e 1 Kg. dimolibdeno e costa L. 20000. La seconda confezione contiene 2 Kg.di manganese, 3 Kg. di cromo e 1 Kg. di molibdeno e costa L.30000. La terza confezione contiene 1Kg. di manganese, 2 Kg. dicromo e 5Kg. di molibdeno e costa L. 40000.

Formulare il modello di Programmazione Lineare che minimizzi ilcosto di acquisto delle confezioni.

Es. 2L'acciaieria PLASTIK

Ricerca Operativa




Es. 3La casa editrice ANALFABETA

La casa editrice ANALFABETA pubblica un quotidiano che vienedistribuito da quattro centri di smistamento S1, S2, S3 e S4 cherichiedono rispettivamente 100000, 150000, 50000 e 75000 copie.Il giornale viene stampato in tre tipografie T1, T2 e T3 cheproducono rispettivamente 125000, 180000 e 70000 copie.Sapendo che i costi per la spedizione sono di L. 10/Km pergiornale e che le distanze tra le tipografie ed i centri dismistamento sono rispettivamente di 20, 25, 15 e 5 Km. per laprima tipografia, 12, 14, 18 e 30 Km. per la seconda tipografia e 19,11, 40 e 12 Km. per la terza tipografia, la casa editrice vuolepianificare le sue spedizioni giornaliere in modo da minimizzare icosti di spedizione.Formulare il modello di Programmazione Lineare corrispon-dente.

Ricerca Operativa




Es. 4Il ranch LITTLE DIXIE

Il proprietario del ranch LITTLE DIXIE sta facendo dei test perdeterminare la mescola corretta per due classi di alimenti.Entrambi contengono in percentuali differenti quattro diversi tipidi ingredienti essenziali.L'alimento 1 ha un costo unitario di 5 dollari ed è formato per il40% dall'ingrediente 1, per il 10% dall'ingrediente 2, per il 20%dall'ingrediente 3 e per il 30% dall'ingrediente 4.L'alimento 2 ha un costo unitario di 3 dollari ed è formato per il20% dall'ingrediente 1, per il 30% dall'ingrediente 2, per il 40%dall'ingrediente 3 e per il 10% dall'ingrediente 4.Sapendo che devono essere impiegate come minimo 400 unitàdell'ingrediente 1, 200 unità dell'ingrediente 2, 300 unitàdell'ingrediente 3 e 600 unità dell'ingrediente 4, si vuoledeterminare la mescola di costo minimo.Formulare il modello di Programmazione Lineare di questoproblema.

Ricerca Operativa




Es. 5Un problema di acquisto di aerei

Una compagnia aerea sta considerando l'acquisto di nuovi aereiper passeggeri a lunga, media e corta percorrenza.Il prezzo d'acquisto sarebbe di 6,700,000 dollari per ogni aereo alunga percorrenza, di 5,000,000 dollari per ogni aereo a mediapercorrenza e di 3,500,000 per ogni aereo a percorrenza corta. LaCompagnia ha autorizzato acquisti al massimo per 150 milioni didollari. Indipendentemente da quali aerei vengano acquistati, ilviaggio aereo su tutte le distanze è considerato sufficientementerichiesto perché questi aerei siano utilizzati alla massima capacità.È stato valutato che il profitto annuale netto (al netto degliammortamenti)dovrebbe essere di 420,000 dollari per gli aerei alunga percorrenza, di 300,000$ per gli aerei a media percorrenza edi 230,000$ per gli aerei a percorrenza corta.

Ricerca Operativa




È stato previsto che vi sarà un numero sufficiente di piloti espertiper guidare 30 nuovi aerei. Se fossero acquistati solo aerei a cortapercorrenza, le squadre di manutenzione potrebbero controllare40 nuovi aerei. Tuttavia, in termini di manutenzione, ogniaeroplano a media percorrenza è equivalente a 1+1/3 aerei a cortapercorrenza e ciascun aereo a lunga percorrenza è equivalente a1+2/3 aerei a corta percorrenza.Le informazioni sopra indicate furono ottenute da un'analisipreliminare del problema. Un'analisi più dettagliata sarà condottain seguito. Comunque, usando i dati sopra indicati come primaapprossimazione, la direzione desidera sapere quanti aerei di ognitipo si dovrebbero acquistare in modo da rendere massimo ilprofitto.Formulare il modello in Programmazione Lineare di questoproblema.

Ricerca Operativa




Es. 6Un problema di produzione

Un'azienda produce tre modelli (I, II e III) di un certo prodotto.Ciascun modello richiede due tipi di materiali grezzi (A e B), di cuisono disponibili rispettivamente 4000 e 6000 unità.In particolare per produrre una unità del modello I sononecessarie 2 unità di A e 4 unità di B; per una unità del modello IIsono invece necessarie 3 unità di A e 2 unità di B; infine, per unaunità del modello III sono necessarie 5 unità di A e 7 di B.Il modello I richiede una forza lavoro doppia rispetto al modello II etripla rispetto al modello III; la forza di lavoro disponibile inazienda è in grado di produrre al massimo l'equivalente di 700unità del modello I. Il settore marketing dell'azienda ha reso notoche la domanda minima per ciascun modello è rispettivamente di200, 200 e 150 unità. Il profitto unitario di ciascun modello èrispettivamente di 30, 20 e 50 dollari.Formulare il modello di Programmazione Lineare di questoproblema che massimizzi il profitto totale.

Ricerca Operativa




Es. 7Un problema di utilizzo di manodopera

Un Motel autostradale, dovendo garantire un servizio continuato24 ore su 24, ha bisogno di un numero minimo di inservienti perogni ora del giorno secondo la seguente tabella:

Ciascun inserviente lavora 8 ore consecutive al giorno. L'obiettivoè quello di garantire la presenza richiesta utilizzando il minornumero possibile di inservienti.Formulare il modello di Programmazione Lineare di questoproblema.

Ora del giorno Numero minimodi inservienti

02 - 0606 - 1010 - 1414 - 1818 - 2222 - 02

48

107

124

Ricerca Operativa




Es. 8Un problema semplificato dischedulazione su più linee

Un certo prodotto finale è composto da tre parti che possonoessere lavorate su quattro linee differenti di produzione; ogni lineaè dotata di una limitata capacità di ore di produzione disponibili.La tabella seguente indica la produttività (in numero di pezziall'ora) di ciascuna parte su ciascuna linea e la capacità diciascuna linea.

Linea Capacità Produttività (#pezzi/ora)

parte 1 parte 2 parte 3

1234

10015080200

10152010

15105

15

55

1020

Ricerca Operativa




Si vuole determinare il numero di ore di lavorazione di ciascunaparte su ciascuna linea in modo da massimizzare il numero diunità complete del prodotto finale.Formulare il modello di Programmazione Lineare di questoproblema.

Ricerca Operativa




Es. 9Un secondo problema di produzione

Una certa società ha tre impianti con capacità eccedente. Tutti etre gli impianti sono in grado di produrre un certo prodotto e lasocietà ha deciso di sfruttare in questo modo una parte dellacapacità produttiva in eccesso. Questo prodotto può essere fattoin tre dimensioni (grande, media e piccola) che forniscono unguadagno unitario netto di 12, 10 e 9 dollari. Gli stabilimenti 1, 2 e3 hanno manodopera in eccesso e capacità per produrrerispettivamente 500, 600 e 300 unità al giorno di questo prodotto,non considerando l'ampiezza o la combinazione delle dimensioniin gioco. Comunque la disponibilità dello spazio destinato almagazzinaggio durante la produzione limita il processoproduttivo. Gli stabilimenti 1, 2 e 3 hanno 9000, 8000 e 3500 m2 dispazio disponibile per questo prodotto. Ogni unità prodotta algiorno, in dimensione grande, media o piccola, richiederispettivamente 20, 15 e 10 m2.

Ricerca Operativa




Le previsioni di vendita indicano che si possono vendere algiorno, rispettivamente, al massimo 600, 800 e 500 unità deiprodotti in grande media e piccola dimensione. Per mantenere uncarico di lavoro uniforme tra gli stabilimenti e per ottenere unacerta flessibilità, la direzione ha deciso che la produzioneassegnata in più ad ogni stabilimento deve usare la medesimapercentuale della capacità produttiva in eccesso. La direzionedesidera conoscere la quantità divisa per taglie da produrre inciascuno degli impianti in modo da rendere massimo il guadagno.Formulare il modello in Programmazione Lineare di questoproblema.

Ricerca Operativa




Es. 10Un problema di finanziamento

Un finanziere ha due piani di investimento A e B disponibiliall'inizio di ciascuno dei prossimi cinque anni.Ogni dollaro investito in A all'inizio di ogni anno dà, due anni piùtardi, un profitto di 0.4 dollari (e può essere immediatamentereinvestito).Ogni dollaro investito in B all'inizio di ogni anno dà, tre anni dopo,un profitto di 0.1 dollari. In più da un certo momento in avanti saràpossibile sfruttare anche i piani di investimento C e D. Inparticolare, ogni dollaro investito in C all'inizio del secondo annoraddoppierà dopo quattro anni. Ogni dollaro investito in D all'iniziodel quinto anno darà un profitto di 0.3 dollari l'anno successivo.Anche per i piano di investimento B, C e D vale la possibilità direinvestimento come per il piano A.

Ricerca Operativa




Il finanziere ha a disposizione 10000 dollari e vuole sapere qualepiano di investimento massimizza la somma di denaro che puòaccumulare all'inizio del sesto anno.Formulare il modello in Programmazione Lineare per questoproblema.

Ricerca Operativa




Il modello è il seguente:

Sol. 1Il problema dello zaino

+∈

≥≥≥≥≥≥

≤+++++

+++++=

ZFEDCBA

F

EDC

BA

FEDCBA

as

FEDCBAzof

,,,,,

2

1

10

6

2

2

1021

101

31

21

..

820363010max:..

A=cioccolataB=succhi di fruttaC=Lattine di birraD=Panini imbottitiE=Acqua mineraleF=Pacchi di biscotti

Ricerca Operativa




Siano x1, x2 e x3 rispettivamente, il numero di confezioni di tipo 1,2e 3. Si avrà:

Sol. 2L'acciaieria PLASTIK

+∈

≥++

≥++

≥++

++=

Zxxx

xxx

xxx

xxx

ts

xxxzof

321

321

321

321

321

,,

200005

180000232

1000022

..

400003000020000min:..

Vincolo sulla quantità minima di manganese

Vincolo sulla quantità minima di molibdeno

Vincolo sulla quantità minima di cromo

Ricerca Operativa




Sia xij il numero di giornali stampato nella tipografia i e distribuitonel centro di smistamento j. Si avrà:

Sol. 3La casa editrice ANALFABETA

jiZx

xxxx

xxxx

xxxx

xxx

xxx

xxx

xxxts

xxxxxx

xxxxxxzof

ij ,

70000

180000

125000

75000

50000

150000

100000

..

120400110190300180

14012050150250200min:..

34333231

24232221

14131211

342414

332313

322212

312111

343332312423

222114131211

∀∈

≤+++≤+++≤+++

≥++

≥++≥++

≥++

++++++

++++++=

+

Vincoli sul numero digiornali che devonoraggiungere ogni stabilimento

Vincoli sul numero digiornali che possono esserespediti da ogni tipografia

Ricerca Operativa




Sia x1 la quantità prodotta dell'alimento I e sia x2 la quantitàprodotta dell'alimento II; si avrà:

Sol. 4Il ranch LITTLE DIXIE

iRx

xx

xx

xx

xx

ts

xxzof

i ∀∈

≥+

≥+

≥+

≥+

+=

+

6001.03.0

3004.02.0

2003.01.0

4002.04.0

..

35min:..

21

21

21

21

21

Vincoli sugli ingredienti

Ricerca Operativa




Siano:AL = numero di aerei a lunga percorrenza da acquistareAM = numero di aerei a media percorrenza da acquistareAC = numero di aerei a corta percorrenza da acquistare

Sol. 5Un problema di acquisto di aereoplani

+∈

≤++

≤++

≤++

++=

ZAAA

AAA

AAA

AAA

ts

AAAzof

CML

CML

CML

CML

CML

,,

1505.357.6

4034

35

30

..

230000300000420000max:..

Vincolo sui piloti

Vincolo sulle squadre di manutenzione

Vincolo sulla spesa massima sostenibile

Ricerca Operativa




Sia xi la quantità prodotta del modello i; si avrà:

Sol. 6Un problema di produzione

iZx

xxx

xxx

x

x

x

xxx

ts

xxxzof

i ∀∈

≤++≤++

≥≥≥

≤++

++=

+

6000724

4000532

150

200

200

70031

21

..

502030max:..

321

321

3

2

1

321

321

Vincoli sulla domanda minima

Vincoli sui materiali

Vincolo sulla forza lavoro

Ricerca Operativa




Si identificano i seguenti turni:

Turno 1 = 02-10Turno 2 = 06-14Turno 3 = 10-18Turno 4 = 14-22Turno 5 = 18-02Turno 6 = 22-06

Sol. 7Un problema di utilizzo di manodopera

Ricerca Operativa




Sia xi il numero di inservienti che cominciano la propria attivitàlavorativa all'inizio del turno i; si avrà:

iZx

xx

xx

xx

xx

xx

xx

ts

xxxxxxzof

i ∀∈

≥+

≥+

≥+

≥+

≥+

≥+

+++++=

+

4

12

7

10

8

4

..

min:..

65

54

43

32

21

61

654321

Vincolo sul turno 1

Vincolo sul turno 2

Vincolo sul turno 3

Vincolo sul turno 4

Vincolo sul turno 5

Vincolo sul turno 6

Ricerca Operativa




Sia xij il numero di ore di lavorazione della parte j sulla linea diproduzione i. Si ottiene:

Sol. 8Un problema semplificato dischedulazione su più linee

{}

jiZx

xxx

xxx

xxx

xxxts

xxxxxxxx

xxxxzof

ij ,

200

80

150

100

..

201055,1551015

,10201510minmax:..

434241

333231

232221

131211

4333231342322212

41312111

∀∈

≤++

≤++≤++

≤++

++++++

+++=

+

Vincoli sulla capacità di ciascuna linea

Ricerca Operativa




La funzione obiettivo scritta in questo modo non è lineare. Perrenderla lineare, basta introdurre una nuova variabile ymodificando la funzione obiettivo nel modo seguente:

ed introducendo i seguenti vincoli:

che andranno aggiunti ai vincoli di capacità della linea e di nonnegatività e interezza delle variabili.

yz =max

yxxxx

yxxxx

yxxxx

≥+++

≥+++≥+++

43332313

42322212

41312111

201055

1551015

10201510

Ricerca Operativa




Siano:SiG = unità di prodotto di grandi dimensioni realizzato nellostabilimento i;SiM = unità di prodotto di medie dimensioni realizzato nellostabilimento i;SiP = unità di prodotto di piccole dimensioni realizzato nellostabilimento i.

Sol. 9Un secondo problema di produzione

( ) ( )( )

300

600

500

..

9

1012max:..

333

222

111

321

321321

≤++

≤++

≤++

++

++++++=

PMG

PMG

PMG

PPP

MMMGGG

SSS

SSS

SSS

ts

SSS

SSSSSSzof

Vincoli di capacità relativa alla manodopera

Ricerca Operativa




( ) ( )( ) ( )

iZSSS

SSSSSS

SSSSSS

SSS

SSS

SSS

SSS

SSS

SSS

iPiMiG

PMGPMG

PMGPMG

PPP

MMM

GGG

GMP

GMP

GMP

∀∈

=++−++

=++−++

≤++

≤++

≤++

≤++

≤++

≤++

+ ,,

063

056

500

800

600

3500201510

8000201510

9000201510

333222

222111

321

321

321

333

222

111

Limiti di dimensione degli stabilimenti

Vincoli sulle previsioni di vendita

Stessa percentuale dimanodopera in eccesso

Ricerca Operativa




SianoAi = dollari investiti nel piano A all'anno i-esimo;Bi = dollari investiti nel piano B all'anno i-esimo;Ci = dollari investiti nel piano C all'anno i-esimo;Di = dollari investiti nel piano D all'anno i-esimo.

Sol. 10Un problema di finanziamento

iRDCBA

ABABACBAD

ABACBBAA

ABCBABA

BACBA

BA

ts

DA

BACBABAzof

iiii ∀∈

≤−−−−−+++

≤−−−++++

≤−+++++

≤++++

≤+

++

+++++++=

+ ,,,

100004.01.04.01.04.0

100004.01.04.0

100004.0

10000

10000

..

100003.04.0

1.04.01.04.01.04.0max:..

322112345

21122334

1122233

11222

11

54

3322211

Vincolo sul primo anno

Vincolo sul secondo anno

Vincolo sul terzo anno

Vincolo sul quarto anno

Vincolo sul quinto anno

1. MODELLI DI PROGRAMMAZIONE LINEARE - Corsi di Laurea...

Documents

Transcript of 1. MODELLI DI PROGRAMMAZIONE LINEARE - Corsi di Laurea...