Qu'est-ce que la programmation linéaire ?
Les problèmes de programmation linéairea> consistent à déterminer les allocations optimales de ressources limitées pour atteindre les objectifs. Certains problèmes classiques de programmation linéairea> se rencontrent dans la fabrication, l'alimentation et la planification des transports.
Les ressources peuvent prendre la forme d'hommes, de matières premières, d'argent, de demande, de machines, etc. L'objectif du problème de programmation linéaire peut être de maximiser le profit et l'utilité, de minimiser le coût total et les dépenses en capital, etc. Il y aura certaines restrictions sur la quantité totale de ressources disponibles et sur la quantité ou la qualité de chaque produit fabriqué.
Un problème de programmation linéaire consiste à optimiser (maximiser ou minimiser) une fonction. Il se compose de trois parties : la fonction objective, la variable de décision et les contraintes.
Les fonctions qui doivent être optimisées sont appelées fonction objectif.
Les variables dont les valeurs déterminent la solution du problème donné sont appelées variables de décision du problème.
L'ensemble des équations ou inégalités linéaires simultanées auxquelles le problème est soumis est appelé contraintes.
Dans les problèmes de programmation linéaire, le terme 'linéaire' fait référence au fait que toutes les variables impliquées dans la fonction objectif et les contraintes sont linéaires, c'est-à-dire de degré \(1\) dans les problèmes considérés. Le terme "programmation" fait référence au processus de détermination d'un plan d'action particulier.
Règles de formulation des problèmes de programmation linéaire
Les règles suivantes doivent être appliquées lors de la formulation d'un problème de programmation linéaire.
Il doit y avoir un objectif bien défini à atteindre (maximiser ou minimiser).
Il n'y a qu'un nombre fini de variables de décision.
Au moins quelques-unes des ressources doivent être en quantité limitée, ce qui donne lieu à des contraintes.
Tous les éléments doivent être quantifiables. Toutes les variables de décision ne doivent prendre que des valeurs non négatives.
La fonction objective et les contraintes doivent être des équations ou des inégalités linéaires.
Il doit y avoir d'autres possibilités de choix pour la ligne d'action.
Formulation mathématique des problèmes de programmation linéaire
Si \(x_i (i=1,2,...,n)\) sont les \(n\) variables de décision du problème et si le système donné est soumis à \(k\) contraintes, alors le modèle mathématique général peut être écrit sous la forme suivante
Optimiser \N(Z = f(x_1,x_2,...,x_n)\Nsous réserve de \N(g_i(x_1,x_2,...,x_n) \Nleq ,=,\Ngeq b_j,(i=1,2,...,k)\N)
et \N(x_1,x_2,....,x_n \geq 0\N)
Examinons les étapes de la formulation mathématique des problèmes de programmation linéaire.
Nous devons identifier les variables de décision inconnues à déterminer et leur attribuer des symboles.
Après cela, identifie l'objectif ou le but et représente-le également comme une fonction linéaire des variables de décision.
Ensuite, tu dois identifier toutes les restrictions ou contraintes du problème donné et exprimer ces restrictions ou contraintes sous forme d'équations ou d'inégalités linéaires des variables de décision.
Exprime la formulation complète du problème de programmation linéaire sous la forme d'un modèle mathématique composé de l'objectif et des contraintes.
Étapes de la formulation des problèmes de programmation linéaire
Les étapes suivantes sont utilisées pour formuler mathématiquement les problèmes de programmation linéaire.
Étape 1 : Tout d'abord, pour optimiser la fonction, identifie le nombre de variables de décision qui régissent le comportement de la fonction objective. Représentons-la par "\(n\)".
Étape 2 : Deuxièmement, tu dois identifier l'ensemble des contraintes sur les variables de décision. Tu devras les exprimer sous forme d'équations linéaires ou d'inéquations. Cela t'aidera à définir ta région dans l'espace à \(n\) dimensions dans lequel ta fonction objective doit être optimisée. Prends note de la condition de non-négativité des variables de décision, c'est-à-dire qu'elles doivent toutes être positives car le problème peut représenter un scénario du monde réel, et ces variables ne peuvent pas être négatives.
Étape 3 : Exprime maintenant la fonction objective sous la forme d'une équation linéaire ou d'inéquations dans les variables de décision.
Étape 4 : Enfin, optimise mathématiquement la fonction objective.
Exemples de formulation de problèmes de programmation linéaire
Une usine fabrique deux types de produits \N(S\N) et \N(T\N) et les vend avec un bénéfice de \N($2\N) sur le type \N(S\N) et \N($3\N) sur le type \N(T\N). Chaque produit est traité sur deux machines \(M_1\) et \(M_2\). Le type \N(S\N) nécessite \N(1) minute de temps de traitement sur \N(M_1\N) et \N(2) minutes sur \N(M_2\N). Le type \N(T\N) nécessite \N(1) minute sur \N(M_1\N) et 1 minute sur \N(M_2\N). La machine \(M_1\) n'est pas disponible plus de \(6\) heures \(40\) minutes tandis que la machine \(M_2\) est disponible pendant \(10\) heures au cours d'une journée de travail. Formule le problème sous forme de LPP afin de maximiser le profit.
Solution :
L'usine décide de produire \(x_1\) unités du produit \(S\) et \(x_2\) unités du produit \(T\) pour maximiser son profit.
Pour produire ces unités de produits de type \N(S\N) et de type \N(T\N), il faut \N(x_1+x_2\N) minutes de traitement sur \N(M_1\N) et \N(2x_1+x_2\N) minutes de traitement sur \N(M_2\N). Étant donné que la machine \N(M_1\N) est disponible pendant un maximum de \N(6\N) heures \N(40\N) minutes et que \N(M_2\N) est disponible pendant un maximum de \N(10\N) heures chaque jour ouvrable, les contraintes sont les suivantes
\N-[x_1+x_2 \Nleq 400,\N] \N-[2x_1+x_2 \Nleq 600,\N] et \N-[x_1,x_2 \Ngeq 0,\N].
Étant donné que le bénéfice du type \N(S\N) est de \N($2\N) et que le bénéfice du type \N(T\N) est de \N($3\N), le bénéfice total est de \N(2x_1+3x_2\N). L'objectif étant de maximiser le profit, la fonction objective est de maximiser \(Z=2x_1+3x_2\).
La formulation complète du LPP est \N(\text {Maximiser}\, Z=2x_1+3x_2\) sous réserve des contraintes suivantes
\N-[x_1+x_2\Nleq 400,\N]
\N- [2x_1+x_2\Nleq 600,\N]
et \N[x_1,x_2 \Ngeq 0,\N].
Examinons un autre problème.
Une entreprise produit des smartwatches et des téléphones phares. Les projections de l'entreprise indiquent une demande attendue d'au moins 200 téléphones phares et 140 smartwatches par jour. En raison de quelques limitations dans le service de production, il n'est pas possible de fabriquer plus de 300 téléphones phares et 180 smartwatches par jour.
Afin de faciliter le contrat d'expédition, un minimum de 240 millions de marchandises doit être expédié chaque jour. Si chaque téléphone vedette vendu entraîne une perte de 10 $, mais que chaque smartwatch produit un bénéfice de 20 $, combien de smartwatches et de téléphones vedettes doivent être fabriqués chaque jour pour maximiser le bénéfice net ?
Solution :
Résolvons le problème de programmation linéaire donné en suivant les étapes impliquées.
Étape 1 : Tu dois trouver les variables de décision. On t'a demandé d'optimiser le nombre de smartphones et de téléphones phares produits par l'entreprise. Ce seront tes variables de décision dans le problème donné.
Soit \(x=\)Nombre de téléphones phares produits et \(y=\)Nombre de smartphones produits.
Par conséquent, \(x\) et \(y\) sont les deux variables de décision dans le problème donné.
Étape 2 : Tu dois maintenant t'occuper des contraintes. Puisque l'entreprise ne peut pas produire un nombre négatif de téléphones phares et de smartwatches, les contraintes évidentes seraient \[x \ge 0,\N] et \[y \ge 0.\N] Dans le problème donné, la limite inférieure pour que l'entreprise vende ses smartwatches et ses téléphones phares est donnée. Tu peux les écrire comme \N [x \N 200,\N] et \N[y \N 140,\N] Les limites supérieures de cette fabrication en tenant compte des limitations du département de production sont également données. Tu peux les écrire sous la forme \N[x \le 300,\N] et \N[y \le 180,\N]. Tu as également la contrainte conjointe pour les smartwatches et les téléphones phares en raison du contrat d'expédition, sous la forme \N[x+y \le 240,\N].
Étape 3 : considère maintenant la fonction objective. Tu dois optimiser la fonction de bénéfice net. Elle est donnée par \N[P=-10x+20y.\N]
Étape 4: la dernière étape consiste à résoudre le problème.
\N- [\N- Texte {Maximiser}\N, P=-10x+20y \N]
sous réserve de \[200 \le x \le 300,\N] \[140 \le y \le 180,\N] et \ [x+y \ge 240.\N].
Voyons un autre scénario de la vie réelle.
Dave veut décider des composants de son régime alimentaire qui répondent à ses besoins quotidiens en protéines, en matières grasses et en glucides au moindre coût. Il obtient ces nutriments à partir de quatre aliments différents. Les rendements par unité de son alimentation sont donnés dans le tableau suivant.
| Type d'aliment | Rendement/unitéProtéines | Rendement/unitéGraisses | Rendement/unitéGlucides | Coût/unité$ |
| \[1\] | \[3\] | \[2\] | \[6\] | \[2\] |
| \[2\] | \[4\] | \[2\] | \[4\] | \[1\] |
| \[3\] | \[8\] | \[7\] | \[7\] | \[5\] |
| \[4\] | \[6\] | \[5\] | \[4\] | \[3\] |
| Exigence minimale | \[900\] | \[200\] | \[700\] |
Formule le modèle de programmation linéaire pour le problème.
Solution :
Soit \(x_1,x_2,x_3\) et \(x_4\) les unités de nourriture de type \(1\), \(2\), \(3\), et \(4\) utilisées respectivement.
À partir de ces unités de nourriture de types \N(1), \N(2), \N(3) et \N(4), il a besoin de
\N- [3x_1+4x_2+8x_3+6x_4\N, \Ntexte{protéines/jour},\N]
\N- [2x_1+2x_2+7x_3+5x_4\N, \N-text{Les graisses/jour et}\N-]
\[6x_1+4x_2+7x_3+4x_4\, \text{Carbohydrates/day}.\]
Comme les besoins minimaux en protéines, en lipides et en glucides sont respectivement de \(900\), \(200\) et \(700\), les contraintes sont les suivantes
\N- [3x_1+4x_2+8x_3+6x_4 \N- 900,\N] \N- [2x_1+2x_2+7x_3+5x_4 \N- 200,\N] \N- [6x_1+4x_2+7x_3+4x_4 \N- 700,\N]
et \N[x_1,x_2,x_3,x_4 \geq 0,\N].
Puisque le coût de cet aliment de type \N(1\N), \N(2\N), \N(3\N) et \N(4\N) est de \N(2\N), \N(1\N), \N(5\N) et \N(3\N) par unité, le coût total est de \N(2x_1+x_2+5x_3+3x_4\N, $\N). L'objectif étant de minimiser le coût total, la fonction objective est la suivante
\[\texte {Minimiser}\, Z=2x_1+1x_2+5x_3+3x_4.\]
La formulation complète de la LPP est
\[\texte {Minimiser}\, Z=2x_1+1x_2+5x_3+3x_4\]
sous réserve de
\N[3x_1+4x_2+8x_3+6x_4 \Ngeq 900,\N]
\N- [2x_1+2x_2+7x_3+5x_4 \N- 200,\N]
\N- [6x_1+4x_2+7x_3+4x_4 \N- 700,\N] et \N- [x_1,x_2,x_3,x_4 \N- 0,\N].
Formuler des problèmes de programmation linéaire - Principaux enseignements
- Les problèmes de programmation linéaire consistent à déterminer les allocations optimales de ressources limitées pour atteindre les objectifs.
- Les trois étapes de la formulation des problèmes de programmation linéaire consistent à trouver les variables de décision, la fonction objective et les contraintes.
- Les variables dont les valeurs déterminent la solution du problème donné sont appelées variables de décision du problème.
- Les fonctions qui doivent être optimisées sont connues sous le nom de fonction objectif. L'ensemble des équations ou des inégalités linéaires simultanées auxquelles le problème est soumis sont appelées contraintes.
- Limites : Elle ne peut traiter que des problèmes à objectif unique, toutes les fonctions impliquées ne peuvent être que linéaires et les variables de décision ne peuvent prendre que des valeurs non négatives.
Apprends avec 15 fiches de Formulation des problèmes de programmation linéaire dans l'application gratuite StudySmarter
Nous avons 14,000 fiches sur les paysages dynamiques.
Tu as déjà un compte ? Connecte-toi
Questions fréquemment posées en Formulation des problèmes de programmation linéaire
Teste tes connaissances avec des questions à choix multiples
TON SCORE
Ton score
Rejoins l'application StudySmarter et apprends efficacement avec des millions de flashcards, et plus encore.
Apprends avec 15 fiches de Formulation des problèmes de programmation linéaire dans l'application gratuite StudySmarter
Tu as déjà un compte ? Connecte-toi
À propos de StudySmarter
StudySmarter est une entreprise de technologie éducative mondialement reconnue, offrant une plateforme d'apprentissage holistique conçue pour les étudiants de tous âges et de tous niveaux éducatifs. Notre plateforme fournit un soutien à l'apprentissage pour une large gamme de sujets, y compris les STEM, les sciences sociales et les langues, et aide également les étudiants à réussir divers tests et examens dans le monde entier, tels que le GCSE, le A Level, le SAT, l'ACT, l'Abitur, et plus encore. Nous proposons une bibliothèque étendue de matériels d'apprentissage, y compris des flashcards interactives, des solutions de manuels scolaires complètes et des explications détaillées. La technologie de pointe et les outils que nous fournissons aident les étudiants à créer leurs propres matériels d'apprentissage. Le contenu de StudySmarter est non seulement vérifié par des experts, mais également régulièrement mis à jour pour garantir l'exactitude et la pertinence.
En savoir plus
