La programmazione lineare E’ una tecnica matematica usata nella pianificazione amministrativa ed economica per trovare il massimo o il minimo di funzioni lineari soggette a “vincoli” Il ricavo (o il costo) assume la forma di funzione, che viene indicata spesso con z e viene detta “funzione obiettivo”. E s e m p i o: Un’ azienda produce quotidianamente una quantità x di divani e una quantità y di poltrone y x N° di divani prodotti N° di poltrone prodotte L’ azienda ricava € 600 per ogni divano venduto e € 400 per ogni poltrona venduta. Il ricavo assume la forma di funzione: Z = 600 X + 400 y Il ricavo assume la forma di funzione: Z = 600 X + 400 y Quanto vale il massimo ricavo per l’ azienda ? Al variare di x e di y, ovvero del numero di articoli prodotti dell’ uno e dell’ altro tipo, varia il ricavo giornaliero. La funzione z = 600 x + 400 y nello spazio viene rappresentata con un piano. Da un punto di vista matematico, questa funzione ricavo non ha limitazioni … Da un punto di vista pratico ci rendiamo conto che x ed y non possono assumere valori qualsiasi, ma devono obbedire a dei “vincoli” I vincoli (di produzione) possono essere dovuti a: Disponibilità di materiale Ore lavorative Capienza del magazzino L’ obiettivo del problema è trovare il valore di produzione che rende massimo il ricavo, tenendo conto dei vincoli. L’ obiettivo del problema è trovare il valore di produzione che rende massimo il ricavo, tenendo conto dei vincoli. Aggiungiamo dei vincoli al problema … 1° VINCOLO: Ogni divano richiede 2 ore di lavoro, mentre ogni poltrona richiede 1 ora. In azienda le ore lavorative sono 8 al giorno. 2° VINCOLO: Il salottificio può produrre giornalmente al massimo 6 oggetti I vincoli si traducono in DISEQUAZIONI ore lavorative ≤ 8 ore lavorative ≤ 8 Bisogna esprimere le ore lavorative in funzione di x e y ore lavorative ≤ 8 2x+y≤ 8 n° di oggetti prodotti ≤ 6 n° di oggetti prodotti ≤ 6 Bisogna esprimere anche questo vincolo in funzione di x e y n° di oggetti prodotti ≤ 6 x+y≤ 6 Oltre ai vincoli di produzione esistono i vincoli di segno: Le quantità prodotte x ed y non possono essere negative: x≥0 y≥0 Oltre ai vincoli di produzione esistono i vincoli di segno: Le quantità prodotte x ed y non possono essere negative: x≥0 y≥0 3° VINCOLO R I E P I L O G A N D O: Il problema consiste nel trovare il massimo della funzione lineare: R I E P I L O G A N D O: Il problema consiste nel trovare il massimo della funzione lineare: z = 600 x + 400 y R I E P I L O G A N D O: Il problema consiste nel trovare il massimo della funzione lineare: z = 600 x + 400 y Soggetta al sistema di vincoli: R I E P I L O G A N D O: Il problema consiste nel trovare il massimo della funzione lineare: z = 600 x + 400 y Soggetta al sistema di vincoli: 2x+y≤ 8 x+y≤ 6 x≥0 y≥0 GENERALIZZANDO … Si parla di PROGRAMMAZIONE LINEARE quando si e' in presenza di: GENERALIZZANDO … Si parla di PROGRAMMAZIONE LINEARE quando si e' in presenza di: a) una FUNZIONE LINEARE di 2 o più VARIABILI INDIPENDENTI che si deve MASSIMIZZARE (se si tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE (se si tratta di FUNZIONE COSTI); GENERALIZZANDO … Si parla di PROGRAMMAZIONE LINEARE quando si e' in presenza di: a) una FUNZIONE LINEARE di 2 o più VARIABILI INDIPENDENTI che si deve MASSIMIZZARE (se si tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE (se si tratta di FUNZIONE COSTI); b) un INSIEME DI VINCOLI dati da EQUAZIONI o DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI; GENERALIZZANDO … Si parla di PROGRAMMAZIONE LINEARE quando si e' in presenza di: a) una FUNZIONE LINEARE di 2 o più VARIABILI INDIPENDENTI che si deve MASSIMIZZARE (se si tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE (se si tratta di FUNZIONE COSTI); b) un INSIEME DI VINCOLI dati da EQUAZIONI o DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI; c) un INSIEME DI VINCOLI DI SEGNO, di norma POSITIVO, che esprimono la NON-NEGATIVITA' delle VARIABILI presenti, essendo esse GRANDEZZE ECONOMICHE. Risoluzione del problema Si parte con la risoluzione per via grafica del sistema di disequazioni: 2x+y≤ 8 x+y≤ 6 x≥0 y≥0 Risoluzione del problema Si parte con la risoluzione per via grafica del sistema di disequazioni: 2x+y≤ 8 x+y≤ 6 x≥0 y≥0 y≤-2x+8 y≤-x+6 x≥0 y≥0 Risoluzione del problema Si rappresentano le rette corrispondenti alle equazioni associate: y≤-2x+8 y≤-x+6 x≥0 y≥0 y=-2x+8 y=-x+6 x=0 y=0 y 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 x y 8 7 y=-2x+8 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 x y 8 7 y=-2x+8 6 5 4 3 y=-x+6 2 1 0 0 1 2 3 4 5 6 7 8 9 x y x=0 8 7 y=-2x+8 6 5 4 3 y=-x+6 2 1 0 0 1 2 3 4 5 6 7 8 9 x y x=0 8 7 y=-2x+8 6 5 4 3 y=-x+6 2 1 y=0 0 0 1 2 3 4 5 6 7 8 9 x y x≥0 8 7 y≤-2x+8 6 5 4 3 y≤-x+6 2 1 y≥0 0 0 1 2 3 4 5 6 7 8 9 x y REGIONE x≥0 8 AMMISSIBILE 7 y≤-2x+8 6 5 4 3 y≤-x+6 2 1 y≥0 0 0 1 2 3 4 5 6 7 8 9 x y Il massimo della funzione z si trova su uno dei vertici del poligono x≥0 8 7 y≤-2x+8 6 5 4 3 y≤-x+6 2 1 y≥0 0 0 1 2 3 4 5 6 7 8 9 x y In questo caso il poligono è un quadrilatero 8 7 A(0; 6) 6 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y Teorema della programmazione lineare 8 7 A(0; 6) 6 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y ZA = 600 * 0 + 400 * 6 = 2.400 8 7 A(0; 6) 6 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y ZA = 600 * 0 + 400 * 6 = 2.400 8 ZB = 600 * 2 + 400 * 4 = 2.800 7 A(0; 6) 6 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y ZA = 600 * 0 + 400 * 6 = 2.400 8 ZB = 600 * 2 + 400 * 4 = 2.800 7 A(0; 6) 6 ZC = 600 * 4 + 400 * 0 = 2.400 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y ZA = 600 * 0 + 400 * 6 = 2.400 8 ZB = 600 * 2 + 400 * 4 = 2.800 7 A(0; 6) 6 ZC = 600 * 4 + 400 * 0 = 2.400 ZO = 600 * 0 + 400 * 0 = 0 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y ZA = 600 * 0 + 400 * 6 = 2.400 8 ZB = 600 * 2 + 400 * 4 = 2.800 7 A(0; 6) 6 ZC = 600 * 4 + 400 * 0 = 2.400 ZO = 600 * 0 + 400 * 0 = 0 5 B(2; 4) 4 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x y ZA = 600 * 0 + 400 * 6 = 2.400 8 ZB = 600 * 2 + 400 * 4 = 2.800 7 A(0; 6) 6 ZC = 600 * 4 + 400 * 0 = 2.400 ZO = 600 * 0 + 400 * 0 = 0 5 B(2; 4) 4 Il massimo ricavo (€ 2.800) si ha con una produzione giornaliera di 2 divani e 4 poltrone. 3 2 1 O(0; 0) 0 0 1 2 C(4; 0) 3 4 5 6 7 8 9 x Teorema della programmazione lineare Quando l’ insieme delle soluzioni ammissibili di un problema di programmazione lineare è un poligono convesso, allora la soluzione ottimale (ossia il punto di massimo o di minimo della funzione obiettivo), esiste sempre e si trova in uno dei vertici del poligono.