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.