Les exemples qui constituent ce chapitre sont présentés non seulement pour montrer le vaste champs des applications de la programmation linéaire mais aussi et peut-être surtout pour vous inciter à  passer d'une présentation informelle ou littéraire, à  une présentation formelle. La démarche qui est proposée est décrite dans le graphique suivant.

Chacune des étapes décrites doit être travaillé avec soin. Après lecture attentive de la présentation verbale et la prise de conscience que, si jamais on est confronté à  la réalité, il y a une étape préalable encore plus ardue qui correspond à  prendre conscience du fait qu'on est face à  un problème qui peut être structuré sous la forme d'un programme et, qu'en ce qui nous concerne ce programme est linéaire, l'étape la plus difficile est bien entendu l'étape de transposition du problème verbal vers une formulation mathématique sous forme de programme linéaire. Il est conseillé de respecter le mode de raisonnement qui suit :

1. quelles sont les variables ou les inconnues impliquées dans le problème ?
2. Quelle quantité doit être maximisée ou minimisée et comment peut-on exprimer cette quantité en termes des inconnues déterminées à  la question 1 ?
3. À quelles contraintes doit-on faire face ? Comment peut-on exprimer ces contraintes à  partir des inconnues?

Une fois la mise sous forme mathématique réalisée, choisir un programme de résolution adapté n'est pas une chose simple. Chaque programme a une syntaxe distincte et souvent des transcriptions qui semblent correctes d'après les mode d'emploi ne fonctionnent pas. Il est donc nécessaire de bien connaître comment fonctionne le solver que l'on veut utiliser, quelle est la structure de la syntaxe qu'il reconnaît, quels sont les langages de programmation dans lesquels on peut écrire ces programmes, ses limites computationnelles (i.e. : quelles sont les dimensions des programmes qu'il accepte, quelles sont ses performances), les méthodes qu'il implémente ?

Évidemment, un étudiant se tournera naturellement vers un programme gratuit, mais il doit savoir que certains programmes payants peuvent être utilisés gratuitement avec une licence pour étudiants et qu'ils sont, en général plus performants (ceci pour le cas où il voudrait explorer d'autres implémentations que SageMath). Dans certains cas, doit-on utiliser un logiciel spécifique ? À la fin de cette présentation, quelques pages sont consacrées à  l'utilisation des logiciels gratuits ou payants que l'on trouve sur Internet. Elles ne peuvent être exhaustives, mais elles donnent une idée de ce que le logiciel permet d'obtenir.

Une fois toutes ces étapes réalisées, il ne rester plus qu'à  appuyer sur le bouton entrée. Enfin, "il ne reste plus" est un bien grand groupe verbal. Il est nécessaire alors de lire les résultats et de les présenter de telle sorte qu'ils puissent être compris par un lecteur potentiel qui n'y connaît strictement rien. Et là, honnêtement, si vous n'avez pas fait l'effort de passer du temps à  essayer de rédiger dans un langage compréhensible pour non-spécialiste, tous les efforts réalisés au paravent risquent d'être sans effet.

Sous cet angle, la recherche opérationnelle ou plus précisément, en ce qui nous concerne ici, la programmation linéaire en nombre réels, fractionnaires, entiers ou mixtes, est une des rares occasion de commencer à  se former à  la modélisation pratique qu'un ingénieur économique (titre qui n'existe pas en France) devrait avoir.

Un certain nombre des problèmes décrits dans cette section peuvent être résolus graphiquement avec la méthode présentée à  la section\ref{pspipl} --- page \pageref{pspipl}. On utilisera le symbole ✍🏼 pour signaler ce cas. On peut aussi utiliser l'algorithme du simplex présenté à  la section \ref{algosimplex} ---~page \pageref{algosimplex}. On utilisera le symbole 💻 pour signaler cet autre cas. Il est conseillé d'utiliser un programme pour résoudre ces problèmes. Notons que tout programme solvable par la méthode graphique (✍🏼) est solvable par ordinateur (💻). On trouvera une présentation des programmes disponibles au téléchargement ou directement en ligne au chapitre \ref{lppl} page \pageref{lppl}. Mais souvenez vous que les corrections seront toutes données avec $\texttt{SageMath}$. Dans le cas où il est nécessaire d'attendre d'avoir étudié la programmation en nombres entiers (ou la programmation mixte), on attendra d'avoir atteint le chapitre concerné (voir le chapitre~\ref{cne} page \pageref{cne}). Le symbole retenu sera (ℕ). (✍🏼 + ℕ) signifie qu'il est possible, dans un premier temps, de résoudre graphiquement le problème, mais qu'il s'agit réellement d'un programme en nombres entiers et qu'il faudra y revenir.

(✍🏼 + ℕ) Étant donné le nombre d'étudiants de première année dont il doit corriger les copies, le professeur Rechtervorderteil souhaite employer deux étudiants Kevin et Simona, pour corriger les épreuves à sa place. Kevin, qui n'est pas encore docteur, peut corriger 10 copies par heure et demande de 5 €/heure alors que Simona, qui elle est déjà docteur, peut corriger 30 copies par heure de demande 7 €/heure.

Pour des raisons administratives, il est impossible d'employer qui que ce soit moins d'une heure. Si le professeur Rechtervorderteil a au moins 215 copies à corriger par semaine, combien d'heures par semaine doit-il employer chaque étudiant afin de minimiser son coût ?

(✍🏼)Une entreprise fabrique des cadres de fenêtres. Le modèle standard nécessite 1h30 de coupe et 1h de finition. Le modèle de luxe nécessite aussi 1h de coupe mais 2h30 de finition. Étant donné le nombre de salariés dans l'entreprise et les compétences de ces derniers, l'entreprise dispose de 420h/mois pour la coupe, tandis qu'elle ne peut allouer que 280h/mois pour la finition. Le modèle standard apporte une bénéfice de 6 € par unité, tandis que le modèle de luxe apporte une bénéfice de 11 € par unité. Travaillant dans un domaine où la demande est forte, elle est certaine de vendre tout ce qu'elle fabrique. Déterminer la quantité de chaque modèle qu'elle doit fabriquer chaque mois.

(✍🏼 + ℕ) Une entreprise familiale souhaite mettre en bouteille 2 boissons artisanales différentes. Il faut 3 heures pour mettre en bouteille une caisse de la première boisson et 1/2 heure pour étiqueter les bouteilles et la boîte. En revanche, la seconde boisson, qui se vend en canettes, nécessite 3 heures pour la mise en boîte et 2 heures pour les marquer. L'entreprise réalise un bénéfice de 15 € sur la première boisson et de 20 € sur la seconde. Étant donnée la technicité des deux opérations, l'entreprise ne dispose que de 32 heures de disponible à allouer à la première opération (la mise en bouteille) et de 16 heures pour l'étiquetage. Combien doit-elle prévoir de boissons des deux types ?

(✍🏼 + ℕ) Un ébéniste dispose de 17 unités de bois et a l'intention de construire deux types de bibliothèques dans la semaine (la semaine dure 40h). Le premier modèle nécessite 4 unités de bois et 8 heures de travail, tandis que le second modèle nécessite 3 unités de bois et 6 heures. Le prix de vente du premier modèle est de 120 € et celui du second est de 90 €. Combien de bibliothèques de chaque modèle doit-il assembler afin de maximiser son chiffre d'affaires ?

(✍🏼) Une entreprise qui travaille pour une agence spatiale, doit livrer un produit final pesant exactement 70kg. Pour ce faire, elle utilise deux matières premières : la première a un coût de 4,10 € par unité et la seconde un coût de 8 € par unité. Au moins 12 unités de la seconde et pas plus de 18 unités de la première ne doivent être utilisées. Chaque unité de la première pèse 6kg et chaque unité de la seconde 10kg.

1. Donner une représentation graphique de ce problème. Est-il faisable ?
2. Toutes choses égales par ailleurs, quelle est la valeur du membre de droite de la contrainte égalitaire qui permet d'obtenir un point faisable?
3. Toutes choses égales par ailleurs, quelle est la valeur du coefficient associé à $x_2$ qui permet d'obtenir un point faisable ?
4. Résoudre graphiquement le cas où on remplace 70 par 260.
5. Quelle quantité de chaque type de matière première l'entreprise doit-elle utiliser pour chaque unité de produit fini afin de minimiser son coût de production.

(✍🏼 + ℕ) Un fabricant de raquettes de tennis fait un bénéfice de 8 € sur chaque raquette ordinaire et de 15 € sur chaque grande raquette. Pour satisfaire à  la demande des vendeurs, la production journalière de raquettes ordinaires devrait se situer entre 30 et 80 et la production journalière de grandes raquettes entre 10 et 30. Pour maintenir une bonne qualité, le nombre de raquettes produites ne devrait dépasser 80 par jour.

Combien de raquettes de chaque type faudrait-il fabriquer quotidiennement pour réaliser un bénéfice maximum ?

(✍🏼 + ℕ) Une entreprise fabrique deux produits qu'elle désire vendre aux USA. Le produit A rapporte 4 € par kilo et le produit B en rapporte 6 (par kilo). Ayant des moyens financiers limités, la société ne peut affréter qu'un seul avion. La charge utile de ce dernier ne peut dépasser 50 tonnes et a un volume de 2100 m$^3$. Le produit A a un volume de 30 m$^3$ par tonne, le produit B a un volume de 70 m$^3$ par tonne. Combien de kilos de chaque produit l'entreprise doit-elle mettre dans l'avion afin de maximiser ses gains?

(✍🏼 + ℕ) Un éditeur conserve ses livres dans deux entrepôts. Dans le premier, il conserve 150 livres et dans le second 200. Deux librairies lui commandent respectivement 120 et 180 livres. Étant données les distances entrepôts-clients, il doit charger un coût de livraison tel que :

1. pour livrer le premier libraire
1. à  partir du premier entrepôt, il paye 5.60 € ;
2. à  partir du second entrepôt, il paye 7.40 € ;
2. pour livrer le second libraire
1. à  partir du premier entrepôt, il paye 9.20 € ;
2. à  partir du second entrepôt, il paye 4.80 € ;

Comment satisfaire la commande de telle manière que le coût total du transport soit minimisé ?

(✍🏼 + ℕ) Un manager veut refaire sa salle de théâtre et réinstaller trois types de fauteuils : des fauteuils standards, des fauteuils de luxe et des fauteuils de grand luxe. Il décide que le total des deux dernières catégories de fauteuils doit être au moins égal à  la moitié du nombre des fauteuils standards.

Le nombre des fauteuils de luxe doit être au moins égal à  10% et au plus égal à  20% du nombre total de sièges. Le nombre de fauteuils de grand luxe doit être au moins égal à  la moitié du nombre des fauteuils de luxe. Enfin, le nombre total de fauteuils doit être au moins égal à  250. Les prix des trois catégories de fauteuils sont : 50 € pour les fauteuils standards, 70 € pour les fauteuils de luxe et 90 € pour les fauteuils de grand luxe. Le manager veut minimiser le coût total d'installation des fauteuils.

(✍🏼 + ℕ) Une petite entreprise qui produit des pièces usinées utilise à  la fois des travailleurs qualifiés et des apprentis. Sa main-d'œuvre ne doit pas dépasser 50 personnes de manière à  ne pas changer de catégorie. Afin de satisfaire la demande, elle doit produire au moins 6000 pièces par semaine. En moyenne, un travailleur qualifié peut assembler 500 pièces et un apprenti de 200 par semaine. Les conventions collectives indiquent que le nombre des apprentis doit être inférieur au nombre de travailleurs qualifiés mais qu'il peut être supérieur à  la moitié du nombre travailleurs de qualifiés.

Quel est le plus grand nombre de travailleurs qualifiés que peut utiliser l'entreprise ?

(✍🏼 + ℕ) Dans la même situation que le problème précédent, si un travailleur qualifié coûte 375 € par semaine et un apprentis 100 €, combien l'entreprise doit-elle employer de travailleurs qualifiés et d'apprentis pour maintenir le coût salarial au plus bas ?

(✍🏼) Un raffineur peut se procurer du pétrole brut de deux origines distinctes : le premier (du Brent) coûte 79.12€ (brl=barril.), alors que le second coûte 74.84€ brl. Après raffinage, qui coûte pour le premier 4.9 € brl et le second 11€ brl, le pétrole donne, pour simplifier, du gasoil, du kérosène, du Fioul et des résidus. De plus, le raffineur est confronté aux données suivantes :

Sachant que le producteur veut maximiser son profit journalier, montrer que l'on peut écrire ce programme à  6 variables comme un programme à  deux variables, puis le résoudre.

(✍🏼) Une pilule vitaminée doit être produite en utilisant deux ingrédients $I_1$ et $I_2$. Cette pilule doit satisfaire à  certaines conditions sur la contenance en vitamines $A$ et $B$ : elle doit contenir au moins 5 mg de vitamine $A$ et au plus 14. En ce qui concerne la vitamine $B$, elle doit contenir au moins 6 mg et au plus 13. Chaque gramme de $I_1$ contient 2.5 mg de vitamine $A$ et $1$ de vitamine $B$ alors qu'en ce qui concerne $I_2$, les quantités sont 3 mg de $A$ et 5 de $B$. L'entreprise veut fabriquer une pilule de poids minimal. Quelle quantité de $I_1$ et de $I_2$ doit-elle mélanger ?

(✍🏼 + ℕ) À l'approche des fêtes de Pâques, un artisan chocolatier décide de confectionner des œufs en chocolat. En allant inspecter ses réserves, il constate qu'il lui reste 18 kilos de cacao, 8 kilos de noisettes et 14 kilos de lait. Il a deux spécialités : l' œuf Extra et l' œuf Sublime. Un œuf Extra nécessite 1 kilo de cacao, 1 kilo de noisettes et 2 kilos de lait. Un œuf Sublime nécessite 3 kilos de cacao, 1 kilo de noisettes et 1 kilo de lait. Il fera un profit de 20 € en vendant un œuf Extra, et de 30 € en vendant un œuf Sublime. Combien d' œufs Extra et Sublime doit-il fabriquer pour faire le plus grand bénéfice possible ?

(✍🏼 + ℕ) Un fabricant de raquettes de tennis fait un bénéfice de 8 € sur chaque raquette ordinaire et de 15 € sur chaque grande raquette. Pour satisfaire à  la demande des vendeurs, la production journalière de raquettes ordinaires devrait se situer entre 30 et 80, et la production journalière de grandes raquettes entre 10 et 30. Pour maintenir une bonne qualité, le nombre de raquettes produites ne devrait dépasser 80 par jour. Combien de raquettes de chaque type faudrait-il fabriquer quotidiennement pour réaliser un bénéfice maximum ?

(✍🏼 + ℕ) Une entreprise fabrique deux produits qu'elle désire vendre aux USA. Le produit A rapporte 4 € par kilo et le produit B en rapporte 6 par kilo. Ayant des moyens financiers limités, la société ne peut affréter qu'un seul avion. Celui-ci ne peut transporter que 50 tonnes et a un volume de 2100 m$^3$. Le produit A a un volume de 30 m$^3$ par tonne, le produit B a un volume de 70 m$^3$ par tonne. Combien de kilos de chaque produit l'entreprise doit-elle mettre dans l'avion afin de maximiser ses gains ?

(✍🏼) Supposons qu'un agriculteur dispose d'une terre agricole d'une certaine superficie exprimée en $\mathrm{km}^2$. Cette surface peut être utilisée pour cultiver du blé et de l'orge mais l'agriculteur peut aussi décider de diversifier sa production et cultiver une certaine combinaison des deux. Il dispose d'une quantité limitée d'engrais et d'une certaine quantité limitée d'insecticide. Chaque kilomètre carré de blé exige une certaine quantité d'engrais et une certaine quantité d'insecticide, tandis que chaque kilomètre carré d'orge exige une autre quantité d'engrais et une autre quantité d'insecticide. La productivité des deux céréales n'est pas la même et leur prix de vente non plus. Écrire le programme auquel l'agriculteur est confronté.

(✍🏼) Les dissolvants sont largement utilisés dans les industries chimiques. Leur sélection est largement fondée sur leurs coûts. Un chimiste habitué à  utiliser un produit dissolvant $x_1$ dans ses processus de production découvre soudain qu'il peut utiliser efficacement un mélange de $x_1$ avec un autre produit $x_2$ et obtenir le même résultat que quand il utilisait le produit $x_1$ seul.

Il se trouve que $x_2$ est un produit hautement polluant qui est le résidu d'autres processus de production. Pour limiter la diffusion dans la nature de $x_2$, la politique gouvernementale offre une \underline{subvention} qui, tous frais déduits, c'est-à-dire après récupération, conditionnement et transport, revient à  1 € par tonne utilisée dans un processus de production matière. On notera que le produit $x_1$ coûte à  4 € la tonne.

La disponibilité du produit n'est garantie que si une commande est passée une journée à  l'avance sous deux contraintes :

1. la capacité de stockage de $x_1$ et $x_2$ est de 8 tonnes par jour ;
2. la disponibilité journalière de $x_1$ est le double de ce qui est nécessaire alors que $x_2$ est acheté au coup par coup ;
3. la disponibilité maximale de $x_2$ est de 5 tonnes par jour ;
4. par sécurité, la quantité disponible de $x_1$ ne peut excéder celle de $x_2$ de 4 tonnes.

1. Écrire le programme du producteur.
2. En donner une représentation graphique et trouver la solution.
3. Écrire le problème sous la forme d'un tableau simplicial et le résoudre.

(✍🏼) Une ville qui produit 100 tonnes de déchets incinérables par jour possède deux usines d'incinération $A$ et $B$. La tonne incinérée coûte 4.2 € dans l'usine $A$ et 5 € dans l'usine $B$. Les deux usines ont des capacités journalières respectives de 30 et 32 tonnes. La part des déchets qui ne seront pas incinérés doit être enterrée pour un coût de 6 € la tonne. Bien entendu, la municipalité veut minimiser les coûts en brûlant le plus possible de déchets, mais en même temps, elle doit respecter les normes environnementales en limitant la production d'hydrocarbone à  90 kg par jour et la production de particules à  230 kg par jour. Pour chaque tonne de déchets brûlée, l'usine $A$ produit 2 kg d'hydrocarbone et 10 kg de particules alors que l'usine $B$ produit 3 kg d'hydrocarbone et 6 kg de particules.

1. Écrire le programme du producteur.
2. En donner une représentation graphique et trouver la solution.
3. Écrire le problème sous la forme d'un tableau simplicial et le résoudre.

(✍🏼) Vous devez passer un test qui contient des problèmes formels d'une valeur de 5 points chacun et des problèmes informels d'une valeur de 12 points chacun. Vous pouvez finir un problème formel en 3 minutes et un problème informel en 7 minutes. Le test dure 50 minutes et il est interdit de répondre à plus de 15 problèmes. En supposant que toutes vos réponses soient correctes :

1. Écrire le programme linéaire permettant, par le choix du nombre de problèmes de chaque catégories de maximiser votre score.
2. Combien de problèmes informels et de problèmes formels vous décidez vous à résoudre ?
3. En ouvrant le livret des exercices, vous découvrez qu'il y a uniquement 10 exercices informels. Á combien d'exercices formels et informels choisissez vous de répondre ?

(✍🏼) Une entreprise fabrique deux produits en quantités $x_1$ pour le premier et $x_2$ pour le second. Ces deux produits sont obtenus par le passage dans deux processus opérés par deux départements distincts dont la main d'œuvre permet un temps opératoire disponible de 2110 heures pour le premier département et de 1900 pour le second. Bien que les conditions technologiques soient identiques dans les deux départements, les temps de production unitaires sont distincts. On a le tableau suivant (en heure par unités produites) :

La demande est telle que l'entreprise doit produire au plus 200 unités du produit $x_1$ et au moins 300 du produit $x_2$ sacahnt que leurs prix de vente est de 4 pour le produit $x_1$ et de 3 pour le produit $x_2$.

1. Construire le programme.
2. Construire le domaine de faisabilité associé à ce problème :
1. Tracer les contraintes.
2. Obtenir les sommets et les placer.
3. Rajouter l'objectif
4. Déterminer le maximum du profit par déduction.
3. Déterminer l'optimum en évaluant l'objectif sur chaque sommet en déterminant le sommet qui donne la valeur la plus élevée de l'objectif.
4. Pourquoi ne peut-on pas appliquer la méthode du simplexe canonique sur cet exemple ?
5. Déterminer l'optimum par élimination de Fourier-Motzkin. Hint : il suffit de rajouter l'objectif comme une inégalité $z\leq \ldots$ et de conserver $z$ jusqu'à la fin de la procédure d'élimination. Alors, la valeur du membre de droite donne le maximum de $z$. Il suffit alors de remonter pour obtenir $x_1$ et $x_2$.
6. Déterminer la solution par la méthode du simplex.

👈 ☝ 👉