|
Programmazione lineare
Programmazione lineare Tecnica matematica propria
della ricerca operativa, usata nella pianificazione amministrativa
ed economica per massimizzare le funzioni lineari di un gran numero
di variabili soggette a vincoli noti. Lo sviluppo di calcolatori
elettronici ad alta velocità e delle tecniche di elaborazione dati
ha prodotto molti dei progressi recenti della programmazione
lineare, che ora trova un gran numero di applicazioni in campo
industriale e militare.
La programmazione lineare è usata fondamentalmente per
individuare un set di valori, scelto in un insieme predefinito di
numeri, in grado di massimizzare o minimizzare una forma polinomiale
assegnata.
Ciò è illustrato dall'esempio seguente, che rappresenta
un particolare tipo di problema e di tecnica di soluzione. Un
produttore realizza due varietà, V1 e V2, di
un articolo, le cui parti devono essere tagliate, assemblate e
rifinite; egli sa che tutti gli articoli prodotti possono essere
venduti. La varietà V1 richiede 25 minuti per il taglio,
60 per l'assemblaggio e 68 per la rifinitura, e produce un utile di
30 mila lire. La varietà V2 richiede 75 minuti per il
taglio, 60 per l'assemblaggio e 34 per la rifinitura e rende 40 mila
lire. Ogni giorno non è possibile dedicare più di 450 minuti di
tempo al taglio, 480 minuti all'assemblaggio e 476 minuti alla
rifinitura. Quanti pezzi per ciascuna varietà dell'articolo
dovrebbero essere realizzati per massimizzare il profitto?
Indichiamo con x e y i numeri degli
articoli rispettivamente delle varietà V1 e V2
che dovrebbero essere realizzati quotidianamente per massimizzare il
profitto. Poiché x e y non possono essere numeri
negativi,
In un sistema di riferimento cartesiano, queste
disequazioni sono verificate per tutti i punti rispettivamente a
destra della retta di equazione x = 0 e al di sopra di quella
di equazione y = 0. I dati relativi a taglio, assemblaggio e
rifinitura determinano le seguenti espressioni:
Sul grafico, le disequazioni individuano aree al di sotto
di determinate rette.
Il problema è ora di determinare i valori di x e
y, se ve ne sono, che rispettino i vincoli delle espressioni
da 1 a 5, e tali da massimizzare il profitto.
Per soddisfare tutte e cinque le condizioni, occorre una
coppia di valori x e y rappresentata da un punto che
stia sul contorno o all'interno del poligono convesso OABCD della
figura 1.
Il profitto sarà massimo se si sceglie un punto di questa
regione le cui coordinate rendano massima l'espressione p =
30x + 40y; nel nostro caso, il vertice B(3,5). Il
produttore, dunque, otterrà il massimo profitto (290 mila lire) se
saranno realizzati ogni giorno tre pezzi della varietà V1
e cinque della varietà V2. Ogni altro quantitativo delle
due varietà, che rispetti le limitazioni del tempo di produzione,
comporta infatti una riduzione del profitto.
Pagina 2 |
Programmazione |
