Optimisation convexe - Programmation linéaire

Méthodologie

La programmation linéaire, également appelée optimisation linéaire, est une technique utilisée pour résoudre des problèmes mathématiques dans lesquels les relations sont de nature linéaire. la nature fondamentale de la programmation linéaire est de maximiser ou de minimiser unobjective function avec sujet à certains constraints. La fonction objectif est une fonction linéaire obtenue à partir du modèle mathématique du problème. Les contraintes sont les conditions qui sont imposées au modèle et sont également linéaires.

À partir de la question donnée, trouvez la fonction objectif.
trouvez les contraintes.
Dessinez les contraintes sur un graphique.
trouver la région réalisable, qui est formée par l'intersection de toutes les contraintes.
trouver les sommets de la région réalisable.
trouver la valeur de la fonction objectif à ces sommets.
Le sommet qui maximise ou minimise la fonction objectif (selon la question) est la réponse.

Exemples

Step 1 - Maximisez 5 $ x + 3y $ sous réserve de

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

$ x \ geq 0 \: et \: y \ geq 0 $

Solution -

La première étape consiste à trouver la région réalisable sur un graphique.

Clairement à partir du graphique, les sommets de la région des possibles sont

$ \ gauche (0, 0 \ droite) \ gauche (0, 2 \ droite) \ gauche (1, 0 \ droite) \ gauche (\ frac {1} {2}, \ frac {3} {2} \ droite ) $

Soit $ f \ left (x, y \ right) = 5x + 3y $

En mettant ces valeurs dans la fonction objectif, nous obtenons -

$ f \ gauche (0, 0 \ droite) $ = 0

$ f \ gauche (0, 2 \ droite) $ = 6

$ f \ gauche (1, 0 \ droite) $ = 5

$ f \ gauche (\ frac {1} {2}, \ frac {3} {2} \ droite) $ = 7

Par conséquent, la fonction maximise à $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $

Step 2- Une entreprise horlogère produit une montre numérique et une montre mécanique. Les projections à long terme indiquent une demande prévue d'au moins 100 montres numériques et 80 montres mécaniques par jour. En raison des limites de la capacité de production, pas plus de 200 montres numériques et 170 montres mécaniques peuvent être fabriquées quotidiennement. Pour satisfaire un contrat d'expédition, au moins 200 montres au total sont expédiées chaque jour.

Si chaque montre numérique vendue entraîne une perte de $ \ $ 2 $, mais que chaque montre mécanique produit un profit $ \ $ 5 $, combien de chaque type devrait-il être fait quotidiennement pour maximiser les profits nets?

Solution -

Soit $ x $ le nombre de montres numériques produites

$ y $ le nombre de montres mécaniques produites

Selon la question, au moins 100 montres numériques doivent être fabriquées quotidiennement et au maximum 200 montres numériques peuvent être fabriquées.

$ \ Rightarrow 100 \ leq \: x \ leq 200 $

De même, au moins 80 montres mécaniques doivent être fabriquées quotidiennement et au maximum 170 montres mécaniques peuvent être fabriquées.

$ \ Rightarrow 80 \ leq \: y \ leq 170 $

Puisqu'au moins 200 montres doivent être produites chaque jour.

$ \ Flèche droite x + y \ leq 200 $

Étant donné que chaque montre numérique vendue entraîne une perte $ \ $ 2 $, mais chaque montre mécanique produit un profit $ \ $ 5 $,

Le profit total peut être calculé comme suit

$ Profit = -2x + 5 ans $

Et nous devons maximiser le profit, Par conséquent, la question peut être formulée comme -

Maximiser -2x $ + 5y $ sous réserve de

100 $ \: \ leq x \: \ leq 200 $

80 $ \: \ leq y \: \ leq 170 $

$ x + y \: \ leq 200 $

En traçant les équations ci-dessus dans un graphique, nous obtenons,

Les sommets de la région des possibles sont

$ \ gauche (100, 170 \ droite) \ gauche (200, 170 \ droite) \ gauche (200, 180 \ droite) \ gauche (120, 80 \ droite) et \ gauche (100, 100 \ droite) $

La valeur maximale de la fonction objectif est obtenue à $ \ left (100, 170 \ right) $ Ainsi, pour maximiser les profits nets, 100 unités de montres numériques et 170 unités de montres mécaniques devraient être produites.