DAI SISTEMI DI DISEQUAZIONI LINEARI … …. ALLA ... · La soluzione di sistemi di disequazioni...

1

UniversitUniversitàà del Salentodel SalentoDipartimento di MatematicaDipartimento di Matematica

DAI SISTEMI DI DISEQUAZIONI LINEARI DAI SISTEMI DI DISEQUAZIONI LINEARI ……

……. ALLA PROGRAMMAZIONE LINEARE. ALLA PROGRAMMAZIONE LINEARE

Chefi Chefi TrikiTriki

La Ricerca OperativaLa Ricerca Operativa

Fornisce strumenti matematici di supporto alle attività decisionali

Per gestire e coordinare attività con risorse limitate

Al fine di massimizzare un profitto o minimizzareun costo (obiettivo)

2

Un poUn po’’ di di storiastoria……. .

1935 1935 --U.K. U.K. --Progetto Progetto difesadifesa antiaereaantiaereaBawdseyBawdsey Research Station radarResearch Station radar

localizzazione degli aerei nemicilocalizzazione degli aerei nemici

intercettazioneintercettazione

rientro a terra degli aerei inglesi rientro a terra degli aerei inglesi

1938 1938 –– Relazione del soprintendente RoweRelazione del soprintendente RoweCompare per la prima volta lCompare per la prima volta l’’espressione espressione OperationalOperational

ResearchResearch (ricerca operativa)(ricerca operativa)

ottimizzare la distribuzione ottimizzare la distribuzione delle apparecchiature radar delle apparecchiature radar sul territoriosul territorio

Un poUn po’’ di di storiastoria……. .

1939 1939 -- P. M. S. P. M. S. BlackettBlackettcostituzione di un gruppo di ricerca di scienziati e costituzione di un gruppo di ricerca di scienziati e militari lotta contro i sommergibili tedeschimilitari lotta contro i sommergibili tedeschi

1943 USA gruppi di Ricerca Operativa per:1943 USA gruppi di Ricerca Operativa per:guerra antisommergibile guerra antisommergibile dimensionamento dei convogli navalidimensionamento dei convogli navaliscelta dei bersagli nelle incursioni aereescelta dei bersagli nelle incursioni aereeavvistamento ed intercettazione degli aerei nemiciavvistamento ed intercettazione degli aerei nemici

19451945----2010 Problemi di tipo civile2010 Problemi di tipo civileLocalizzazione dei depositi industrialiLocalizzazione dei depositi industrialiProblemi di produzione, di trasposto Problemi di produzione, di trasposto ……..

1961 in Italia viene fondata l1961 in Italia viene fondata l’’AIROAIRO

3

Individuazione del problema

Le fasi di uno studio di ricerca operativaLe fasi di uno studio di ricerca operativa

Raccolta e analisi dei dati

Costruzione del modello

Ricerca della soluzione

Interpretazione dei risultati

Problema di decisioneProblema di decisione

UnUn’’ azienda automobilistica produce due modelli di azienda automobilistica produce due modelli di auto, uno a auto, uno a benzina Bbenzina B che vende al prezzo di 10 mila euro che vende al prezzo di 10 mila euro

e uno e uno diesel Ddiesel D che vende a 12 mila euro. Ogni che vende a 12 mila euro. Ogni autovettura autovettura èè realizzata da due robot R1 e R2. realizzata da due robot R1 e R2.

I tempi di lavorazione dei robot in ore per realizzare le I tempi di lavorazione dei robot in ore per realizzare le auto sono:auto sono:

B DB DR1 2 3R1 2 3R2 2 1R2 2 1

La disponibilitLa disponibilitàà al giorno di R1 al giorno di R1 èè di 24 ore, mentre quella di 24 ore, mentre quella di R2 di R2 èè di 10 ore.di 10 ore.

4

Problema di decisioneProblema di decisione

LL’’azienda ha effettuato unazienda ha effettuato un’’indagine di mercato indagine di mercato con i seguenti esiti:con i seguenti esiti:

•• la domanda giornaliera di B la domanda giornaliera di B èè al pial piùù il doppioil doppio di quella di quella della macchina Ddella macchina D

•• la la domanda minimadomanda minima giornaliera di auto giornaliera di auto èè di 4. di 4.

ProblemaProblema: determinare le quantit: determinare le quantitàà dei due modelli di dei due modelli di auto che devono essere prodotte giornalmente in modo auto che devono essere prodotte giornalmente in modo

da da rendere massimo il guadagnorendere massimo il guadagno. .

Supponiamo che tutte le auto prodotte siano vendute.Supponiamo che tutte le auto prodotte siano vendute.

Formulazione del modello matematicoFormulazione del modello matematico

Definizione delle variabili

Definizione della Funzione obiettivo

Definizione dei vincoli

FormulazioneMatematica

5

Definizione delle variabiliDefinizione delle variabili

Si introducono due variabili che rappresentano leSi introducono due variabili che rappresentano lequantitquantitàà prodotte (e vendute) ogni giorno per i due prodotte (e vendute) ogni giorno per i due modelli di automodelli di auto

Variabili x: Variabili x: Numero di auto a benzina Numero di auto a benzina y: y: Numero di auto dieselNumero di auto diesel

•• Cosa devo decidere?Cosa devo decidere?

Definizione della funzione obiettivoDefinizione della funzione obiettivo

•• Cosa voglio massimizzare?Cosa voglio massimizzare?

Il guadagno giornaliero dipende Il guadagno giornaliero dipende ((èè funzione)funzione) dalla dalla decisione di quante auto D e B voglio produrredecisione di quante auto D e B voglio produrre

La funzione obiettivoLa funzione obiettivo

F(x,y)=10 x+12 y F(x,y)=10 x+12 y

èè una funzione lineare !una funzione lineare !

6

Definizione dei vincoliDefinizione dei vincoli

•• Quali sono le restrizioni sulle variabili?Quali sono le restrizioni sulle variabili?

Vincoli sul tempo di utilizzo dei robot:

Vincoli conseguenti l’indagine di mercato:

Non si può produrre un numero negativo di auto:

2 x +3 y 2 x +3 y ≤≤ 24242 x + y 2 x + y ≤≤ 1010

2 y 2 y ≥≥ xxx + y x + y ≥≥ 44

x x ≥≥ 0, y 0, y ≥≥ 00

Formulazione del problemaFormulazione del problema

Max F(x,y)=10 x+12 yMax F(x,y)=10 x+12 y

soggetto a:soggetto a:

2 x +3 y 2 x +3 y ≤≤ 24242 x + y 2 x + y ≤≤ 10 10

2 y 2 y ≥≥ xxx + y x + y ≥≥ 44

x x ≥≥ 00y y ≥≥ 00

7

Problema di programmazione lineare Problema di programmazione lineare

I problemi che hanno per modello matematico sistemi di disequazioni (o equazioni) lineari

vincoliabbinati ad una funzione lineare da massimizzare o minimizzare

funzione obiettivoprendono il nome di problemi di

Programmazione Lineare (PL)

Ma Ma adessoadesso……..

Qual Qual èè la soluzione?la soluzione?

Quante auto a benzina e diesel si devono Quante auto a benzina e diesel si devono produrre?produrre?

Qual Qual èè il guadagno massimo?il guadagno massimo?

Che si faceva con i sistemi di disequazioni?Che si faceva con i sistemi di disequazioni?

Problema di programmazione lineare Problema di programmazione lineare

8

Metodo grafico Metodo grafico

Un problema di PL in due Un problema di PL in due variabili può essere risolto variabili può essere risolto attraverso semplici attraverso semplici considerazioni di tipo considerazioni di tipo geometrico, a partire geometrico, a partire dalldall’’individuazione su di individuazione su di un piano cartesiano del un piano cartesiano del poligono ammissibile poligono ammissibile

Regione AmmissibileRegione Ammissibile

determinata dai vincoli.determinata dai vincoli.

x

y

Ogni retta f(x,y)= Ogni retta f(x,y)= axax + + byby + c = 0 divide il piano + c = 0 divide il piano cartesiano in due semipiani rappresentati dalle cartesiano in due semipiani rappresentati dalle disequazioni: disequazioni: axax + + byby + c + c << 00

axax + + byby + c + c > > 00

Individuare il semipiano: f(x, y) = ax + by + c > 0Individuare il semipiano: f(x, y) = ax + by + c > 0Si sceglie P(xSi sceglie P(x’’, y, y’’) non appartenente alla retta) non appartenente alla retta

•• Se f(xSe f(x’’, y, y’’) > 0 ) > 0 il semipiano che contiene ilil semipiano che contiene ilpunto P punto P èè quello cercato;quello cercato;

•• Se f(xSe f(x’’, y, y’’) < 0 ) < 0 il semipiano che non contieneil semipiano che non contieneil punto P il punto P èè quello cercato.quello cercato.


9


Ogni vincolo del mio problema rappresenta un Ogni vincolo del mio problema rappresenta un semipiano o una retta semipiano o una retta …… e siccome tutti i vincoli e siccome tutti i vincoli devono essere rispettati la soluzione apparterrdevono essere rispettati la soluzione apparterrààalla parte di piano che alla parte di piano che èè intersezioneintersezione di tutti di tutti i semipiani!!!i semipiani!!!

Per trovare la Regione Ammissibile del nostro problema allora … cerchiamo dove si intersecano i semipiani … ma questo non voleva dire risolvere un

sistema di disequazioni ???

Regione ammissibileRegione ammissibile

Max F(x,y)=10 x+12 yMax F(x,y)=10 x+12 y

soggetto a:soggetto a:

2 x +3 y 2 x +3 y ≤≤ 24242 x + y 2 x + y ≤≤ 10 10

2 y 2 y ≥≥ xxx + y x + y ≥≥ 44

x x ≥≥ 00y y ≥≥ 00

10

Vincoli: x Vincoli: x ≥≥ 0, y 0, y ≥≥ 00

x

y


x

y

Vincolo: 2 x +3 y Vincolo: 2 x +3 y ≤≤ 2424

12

8


11

x

y

Vincolo: 2x + y Vincolo: 2x + y ≤≤ 1010

12

8

5

10


x

y

Vincolo: 2y Vincolo: 2y ≥≥ x x

12

8

5

10


12

x

y

Vincolo: x + y Vincolo: x + y ≥≥ 4 4


Dai sistemi lineari alla regione ammissibileDai sistemi lineari alla regione ammissibile

La regione ammissibile èuna figura convessa

Che vuol dire convessa?

13


La soluzione di sistemi di disequazioni lineari La soluzione di sistemi di disequazioni lineari in due incognite coincide con la parte di piano in due incognite coincide con la parte di piano comune ai semipiani individuati dalle singole comune ai semipiani individuati dalle singole disequazioni. disequazioni.

Questa regione può essere Questa regione può essere limitatalimitata o o illimitataillimitata. .

Se le disequazioni del sistema non hanno Se le disequazioni del sistema non hanno soluzioni comuni (i semipiani non si soluzioni comuni (i semipiani non si intersecano) il sistema intersecano) il sistema èè detto detto impossibileimpossibile..


x

x1

2

3

2

-3

-2

14


La regione ammissibile è

un poliedro!!!

Esempi di RetiEsempi di Reti

Risolvere un problema di PL significa determinare Risolvere un problema di PL significa determinare se il problema se il problema èè: :

InammissibileInammissibile(il sistema di disequazioni (il sistema di disequazioni èè impossibile)impossibile)

Illimitato inferiormente o superiormente Illimitato inferiormente o superiormente

Ammette una soluzione ottima Ammette una soluzione ottima che massimizza o minimizza la funzione obiettivo.che massimizza o minimizza la funzione obiettivo.

15

Teorema fondamentaleTeorema fondamentale

Se il problema di PL ammette minimo o massimo, Se il problema di PL ammette minimo o massimo, allora la funzione obiettivoallora la funzione obiettivo

F(x, y) = ax+by+c F(x, y) = ax+by+c assume il suo valore massimo o minimo solo su un assume il suo valore massimo o minimo solo su un

VERTICEVERTICEo su tutti i punti di un o su tutti i punti di un

LATOLATOdella frontiera della regione ammissibile.della frontiera della regione ammissibile.

..

Ma allora….come si trova una soluzione per il problema delle auto???

Metodo enumerativoMetodo enumerativo

Determinata la regione ammissibile:Determinata la regione ammissibile:Calcola le coordinate dei vertici del poligono;Calcola le coordinate dei vertici del poligono;Calcola il valore della funzione obiettivo su ogniCalcola il valore della funzione obiettivo su ogniverticeverticeLa soluzione La soluzione èè data dalle coordinate del verticedata dalle coordinate del verticeche rende massima o minima la funzione obiettivoche rende massima o minima la funzione obiettivo

16

Metodo enumerativoMetodo enumerativo

x

y

A(0,8)

E(0,4)

B(3/2,7)

C(4,2)

D(8/3,4/3)

F(0,8)=10*0+12*8=96F(3/2,7)=10*3/2+12*7=99

F(4,2)=10*4+12*2=64

F(8/3,4/3)=10*8/3+12*4/3=42,7

F(0,4)=10*0+12*4=48

Il metodo del Il metodo del SimplessoSimplesso

Il metodo del simplesso Il metodo del simplesso èè un algoritmo che un algoritmo che permette, attraverso un numero finito di permette, attraverso un numero finito di iterazioni, di passare, se il problema ammette iterazioni, di passare, se il problema ammette soluzione, da un qualsiasi vertice del poliedro al soluzione, da un qualsiasi vertice del poliedro al vertice ottimo. vertice ottimo. L'algoritmo del L'algoritmo del SimplessoSimplesso, ideato dall'americano , ideato dall'americano George George DantzigDantzig nel 1947, nel 1947, èè un metodo numerico un metodo numerico per risolvere problemi di per risolvere problemi di PLPL

17

E per i piE per i piùù pigri: il pigri: il LingoLingo

LINGO è un pacchetto software che consente di formulare e risolvere problemi di ottimizzazione (Programmazione Lineare e non) anche a grandi dimensioni, e di analizzarne le rispettive soluzioni.

Altro esempio: Gestione del PersonaleAltro esempio: Gestione del Personale

Il responsabile della gestione del personale di un’azienda manifatturiera ha il compito di organizzare i turni di lavoro ad una catena di montaggio a ciclo continuo.

18

Gestione del PersonaleGestione del Personale

Sono previste sei fasce orarie per ognuna delle quali è richiesto un numero minimo di unità lavorative, come riassunto dalla seguente tabella:


A seguito di accordi sindacali sono stati individuati sei turni di lavoro ciascuno dei quali di 8 ore lavorative:

19


Si vuole determinare il numero di unitàlavorative da assegnare ad ogni turno in modo tale da impiegare la minor forza lavoro complessiva.

SoluzioneSoluzione: : Si indichi con:Si indichi con:

xixi = numero di unit= numero di unitàà di personale da di personale da assegnare al turno iassegnare al turno i--esimo (i = 1, , 6).esimo (i = 1, , 6).


E' evidente che la fascia oraria E' evidente che la fascia oraria compresa tra le 00.00 e le 04.00 sarcompresa tra le 00.00 e le 04.00 sarààcoperta dalle unitcoperta dalle unitàà lavorative del primo lavorative del primo e del secondo turno. Dovendo garantire e del secondo turno. Dovendo garantire una disponibilituna disponibilitàà di personale di almeno di personale di almeno 6 unit6 unitàà, si impone il vincolo: x1 + x2 6. , si impone il vincolo: x1 + x2 6.

20


E' evidente che la fascia oraria E' evidente che la fascia oraria compresa tra le 00.00 e le 04.00 sarcompresa tra le 00.00 e le 04.00 sarààcoperta dalle unitcoperta dalle unitàà lavorative del primo lavorative del primo e del secondo turno. Dovendo garantire e del secondo turno. Dovendo garantire una disponibilituna disponibilitàà di personale di almeno di personale di almeno 6 unit6 unitàà, si impone il vincolo: x1 + x2 6. , si impone il vincolo: x1 + x2 6.


Analogamente, per le altre fasce orarie:Analogamente, per le altre fasce orarie:

x2 + x3 x2 + x3 99x3 + x4 x3 + x4 1414x4 + x5 x4 + x5 99x5 + x6 x5 + x6 1111x6 + x1 x6 + x1 8 8

Obiettivo: minimizzare il numero di unitObiettivo: minimizzare il numero di unitàà z z impiegate: z = x1 + x2 + x3 + x4 + x5 + x6. impiegate: z = x1 + x2 + x3 + x4 + x5 + x6.

21


Modello Matematico:Modello Matematico:


La soluzione ottimale prevede:La soluzione ottimale prevede:

per un numero complessivo di unitper un numero complessivo di unitàà lavorative lavorative utilizzate pari a: utilizzate pari a: z*z* = 31.= 31.Nota:Nota: soltanto per la fascia oraria compresa soltanto per la fascia oraria compresa tra le 12.00 e le 16.00 saranno utilizzate tra le 12.00 e le 16.00 saranno utilizzate unitunitàà di personale in un numero superiore di personale in un numero superiore rispetto al minimo richiesto.rispetto al minimo richiesto.

22

Modello dello zainoModello dello zaino

Decisione:

Quali materie preparare:

•• avendo a disposizione un totale di 27 giorni

•• volendo massimizzare il profitto?

Materia Giorni prep. ProfittoItaliano 10 20,00Latino 12 22,50Greco 15 25,00Inglese 9 15,00Fisica 7 12,50Scienze 6 12,50Storia 6 12,00Geografia 6 12,00Disegno 4 7,50


Strategia (algoritmo) massimo profitto:Strategia (algoritmo) massimo profitto:•• scelgo le materie piscelgo le materie piùù remunerative remunerative

(rispettando il vincolo di 27 giorni)(rispettando il vincolo di 27 giorni)

tempotempo: 27 giorni : 27 giorni profittoprofitto: : 47,5047,50


23


tempotempo: 22 giorni : 22 giorni profittoprofitto:: 44, 0044, 00

Strategie minimo tempo:Strategie minimo tempo:•• scelgo le materie che richiedono meno scelgo le materie che richiedono meno tempo di preparazionetempo di preparazione



tempotempo: 26 giorni : 26 giorni profittoprofitto:: 5252

Altre Strategie?Altre Strategie?


24


tempotempo: 27 giorni: 27 giorni profittoprofitto: : 52, 5052, 50

Risolvo un problema di PL con 9 variabili allRisolvo un problema di PL con 9 variabili all’’ottimoottimo


Compiti: Problema di TrasportoCompiti: Problema di Trasporto

UnUn’’azienda possiede due centri di azienda possiede due centri di distribuzione e tre punti vendita dislocati sul distribuzione e tre punti vendita dislocati sul territorio. Di un prodotto sono disponibili al territorio. Di un prodotto sono disponibili al pipiùù 250 unit250 unitàà presso il primo centro di presso il primo centro di distribuzione e al pidistribuzione e al piùù 400 presso il secondo.400 presso il secondo.Alla direzione centrale risulta una richiesta Alla direzione centrale risulta una richiesta di rifornimento dai tre punti vendita pari ad di rifornimento dai tre punti vendita pari ad almeno 120, 270, 130 unitalmeno 120, 270, 130 unitàà rispettivamente. rispettivamente. Presso tali centri ciascuna unitPresso tali centri ciascuna unitàà di prodotto di prodotto viene venduta a Euro 14, 17 e 16.viene venduta a Euro 14, 17 e 16.

25


I costi unitari di trasporto, legati alla I costi unitari di trasporto, legati alla distanza tra i centri di distribuzione e i distanza tra i centri di distribuzione e i punti vendita, sono cospunti vendita, sono cosìì riassumibili:riassumibili:

ObiettivoObiettivo: massimizzare il profitto : massimizzare il profitto ipotizzando che sia possibile vendere tutto il ipotizzando che sia possibile vendere tutto il quantitativo di prodotto disponibile presso i quantitativo di prodotto disponibile presso i punti vendita. punti vendita.


Suggerimento:Suggerimento:

Indicare con:Indicare con:

xijxij = quantitativo di prodotto inviato = quantitativo di prodotto inviato dal centro di distribuzione i (i = 1, 2) dal centro di distribuzione i (i = 1, 2) al punto di vendita j (j = 1, 2, 3).al punto di vendita j (j = 1, 2, 3).

DAI SISTEMI DI DISEQUAZIONI LINEARI … …. ALLA ... · La soluzione di sistemi di disequazioni...

Documents

Transcript of DAI SISTEMI DI DISEQUAZIONI LINEARI … …. ALLA ... · La soluzione di sistemi di disequazioni...