Ottimizzazione convessa - Programmazione lineare
Metodologia
La programmazione lineare, chiamata anche ottimizzazione lineare, è una tecnica utilizzata per risolvere problemi matematici in cui le relazioni sono di natura lineare. la natura di base della programmazione lineare è massimizzare o minimizzare un fileobjective function con soggetto ad alcuni constraints. La funzione obiettivo è una funzione lineare che si ottiene dal modello matematico del problema. I vincoli sono le condizioni che vengono imposte al modello e sono anche lineari.
- Dalla domanda data, trova la funzione obiettivo.
- trova i vincoli.
- Disegna i vincoli su un grafico.
- trova la regione ammissibile, che è formata dall'intersezione di tutti i vincoli.
- trova i vertici della regione ammissibile.
- trova il valore della funzione obiettivo in questi vertici.
- Il vertice che massimizza o minimizza la funzione obiettivo (secondo la domanda) è la risposta.
Esempi
Step 1 - Massimizza $ 5x + 3y $ soggetto a
$ x + y \ leq 2 $,
$ 3x + y \ leq 3 $,
$ x \ geq 0 \: e \: y \ geq 0 $
Solution -
Il primo passo è trovare la regione ammissibile su un grafico.
Chiaramente dal grafo, i vertici della regione ammissibile sono
$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $
Sia $ f \ sinistra (x, y \ destra) = 5x + 3y $
Mettendo questi valori nella funzione obiettivo, otteniamo:
$ f \ sinistra (0, 0 \ destra) $ = 0
$ f \ sinistra (0, 2 \ destra) $ = 6
$ f \ sinistra (1, 0 \ destra) $ = 5
$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7
Pertanto, la funzione massimizza a $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $
Step 2- Una società di orologi produce un orologio digitale e uno meccanico. Le proiezioni a lungo termine indicano una domanda prevista di almeno 100 orologi digitali e 80 orologi meccanici ogni giorno. A causa delle limitazioni alla capacità di produzione, è possibile realizzare giornalmente non più di 200 orologi digitali e 170 meccanici. Per soddisfare un contratto di spedizione, ogni giorno viene spedito un totale di almeno 200 orologi.
Se ogni orologio digitale venduto si traduce in una perdita di $ \ $ 2 $, ma ogni orologio meccanico produce un profitto di $ \ $ 5 $, quanti di ciascun tipo dovrebbero essere effettuati giornalmente per massimizzare i profitti netti?
Solution -
Sia $ x $ il numero di orologi digitali prodotti
$ y $ essere il numero di orologi meccanici prodotti
Secondo la domanda, ogni giorno devono essere realizzati almeno 100 orologi digitali e possono essere realizzati al massimo 200 orologi digitali.
$ \ Rightarrow 100 \ leq \: x \ leq 200 $
Allo stesso modo, ogni giorno devono essere realizzati almeno 80 orologi meccanici e possono essere realizzati al massimo 170 orologi meccanici.
$ \ Rightarrow 80 \ leq \: y \ leq 170 $
Poiché ogni giorno devono essere prodotti almeno 200 orologi.
$ \ Freccia destra x + y \ leq 200 $
Poiché ogni orologio digitale venduto comporta una perdita di $ \ $ 2 $, ma ogni orologio meccanico produce un profitto di $ \ $ 5 $,
Il profitto totale può essere calcolato come
$ Profitto = -2x + 5y $
E dobbiamo massimizzare il profitto, Pertanto, la domanda può essere formulata come:
Massimizza $ -2x + 5y $ soggetto a
$ 100 \: \ leq x \: \ leq 200 $
$ 80 \: \ leq y \: \ leq 170 $
$ x + y \: \ leq 200 $
Tracciando le equazioni di cui sopra in un grafico, otteniamo,
I vertici della regione ammissibile sono
$ \ sinistra (100, 170 \ destra) \ sinistra (200, 170 \ destra) \ sinistra (200, 180 \ destra) \ sinistra (120, 80 \ destra) e \ sinistra (100, 100 \ destra) $
Il valore massimo della funzione obiettivo si ottiene a $ \ left (100, 170 \ right) $ Pertanto, per massimizzare i profitti netti, è necessario produrre 100 unità di orologi digitali e 170 unità di orologi meccanici.