TDs de Recherche Opérationnelle Dr MBOE BOBO

Thème I : Programmation Linéaire

Par Dr MBOE BOBO

Définir les expressions suivantes : Recherche opérationnelle, programme linéaire, fonction objectif, activités,
coefficients économiques et contrainte redondante.

Pourquoi dit-on qu’il n’y a pas de définition réellement satisfaisante et exhaustive de la Recherche
Opérationnelle ?

Qu’elle est l’importance de la Recherche opérationnelle ? Donnez son impact, ses étapes pratiques ainsi que ses
domaines d’application.

Que vous rappelle ce nom en Recherche Opérationnelle : Patrick Blackett (1940) ?

Donnez sans expliquer, les préalables à la formulation d’un programme linéaire.

Enoncez les théorèmes du point extrême et de base

Donner l’avantage et rappelez les théorèmes du Dual

Une entreprise de la place souhaite produire 𝑋𝑗 (j = 1, 2, 3 …n) articles dont les prix de vente unitaires sont 𝐶𝑗 (j
= 1, 2, 3 …n). Les consommations des ressources disponibles𝑏𝑖 (i = 1, 2,…m) de chaque produit sont 𝑎𝑖𝑗 (i = 1,
2, …m ; j = 1, 2, 3 …n). TAF : 1) Résumer ce problème dans un tableau ; 2) Donner la forme canonique de ce
problème : a) sous la forme algébrique classique ; b) sous la forme matricielle ; sous la forme de notation de
sommation.

Exercice I Soit le programme linéaire suivant :

Max Z = 2x+y

𝑥−𝑦 ≤6
−3𝑥 + 𝑦 ≤ 12
𝑆/𝐶 {
𝑥 + 𝑦 ≤ 20
𝑥, 𝑦 ≥ 0

1) Résoudre ce problème en utilisant la méthode graphique ; 2) vérifier les résultats de la méthode

graphique par la méthode du simplexe ; 3) Ecrire le dual de ce programme et déduire les résultats du
dual à partir de la résolution du primal par les deux méthodes précédentes (1 et 2).

Exercice II

La fabrique RadioIn fabrique deux types de radios A et B. Chaque radio produite est le fruit des efforts conjoints
de 3 spécialistes Pierre, Paul et Jean. Pierre travaille au plus 24 heures par semaine, Paul travaille au plus 45
heures par semaine et Jean travaille au plus 30 heures par semaine. Les ressources nécessaires pour construire
chaque type de radio ainsi que leurs prix de vente sont données dans le tableau ci-dessous :

Radio A Radio B
Pierre 60 minutes 2h
Paul 2h 1h
Jean 1h 0,125 Jour
Prix de vente 15 10
On suppose que l'entreprise n'a aucun problème a vendre sa production, quelle qu'elle soit. TAF : 1) Modéliser le
problème de la recherche d'un plan de production hebdomadaire maximisant le chiffre d'affaires de RadioIn sous
forme d'un programme linéaire en Précisant clairement les variables de décision, la fonction objectif et les
contraintes. 2) Résoudre ce programme linéaire graphiquement et donner le plan de production optimal. 3)
vérifier les résultats trouvés précédemment par la méthode du simplexe. 4) en déduire la solution optimale du
dual.

1
TDs de Recherche Opérationnelle Dr MBOE BOBO
Exercice III

Une société de la place fabrique trois modèles de meubles : classique, rustique et moderne. Les standards
sanitaires de production sont résumés dans le tableau suivant :

Classique Rustique Moderne Capacités

Bois 5 2 5 900
Main d’œuvre 1 2 3 316
Centre finition 2 2 0 200
Marges sur coûts 1000 960 1200
variables
TAF :

Vous êtes le responsable de production dans cette société, on vous demande de déterminer les quantités à
produire pour optimiser ses résultats en utilisant les étapes suivantes :

1) Présenter le programme sous forme canonique

2) Sous forme standard
3) Résoudre le programme et interpréter les résultats
4) Présenter le programme dual de ce primal et en déduire la solution optimale

Exercice IV

Résoudre le modèle de programmation Linéaire suivant par la méthode graphique et vérifier les résultats trouvés
par la méthode du simplexe.
Max𝜋 = 8𝑋1 + 8𝑋2

3𝑋1 + 4𝑋2 ≤ 360

5𝑋 + 2𝑋2 ≤ 320
S/C { 1
2𝑋1 + 𝑋2 ≤ 130
𝑋1 , 𝑋2 ≥ 0

Exercice V

Pour relancer les activités de la coopérative dont il est gestionnaire, un maitre de stage soumet à ses stagiaires les
données du problème auquel il est confronté. Besoins : 60 machettes, 120 paires de chaussures et 90 dabas. Ce
matériel se vend par lots appelés lot A et lot B comme l’indique le tableau ci-après :

1 lot A 1 lot B
Nombre de machettes 1 3
Nombre de paires de chaussures 2 3
Nombre de dabas 2 1
Coûts 10 000 F 9 000 F
Le maitre de stage voudrait déterminer le nombre de lots de chaque type à acheter pour dépenser le moins
possible. Pour ce faire : 1) mettre ce problème sous forme de programme linéaire ; 2) résoudre ce
programme linéaire par la méthode du simplexe.

Exercice VI
Soit le modèle de programmation suivant

Max 𝜋 = 14𝑋1 + 12𝑋2 + 18𝑋3

2𝑋1 + 𝑋2 + 𝑋3 ≤ 2
S/C {𝑋1 + 𝑋2 + 3𝑋3 ≤ 4
𝑋1 , 𝑋2 , 𝑋3 ≥ 0

2
TDs de Recherche Opérationnelle Dr MBOE BOBO
a) Ecrire le Dual de ce programme
b) Résoudre le Dual par la méthode graphique (déterminer les valeurs optimales)
c) En déduire la solution optimale du primal

Exercice VII

Soit le primal d’un programme linéaire suivant :

𝑀𝑖𝑛𝑧 = 10𝑥1 + 6𝑥2 + 8𝑥3

S/C 𝑥1 + 𝑥2 + 2𝑥3 ≥ 2

5𝑥1 + 3𝑥2 + 2𝑥3 ≥ 1

𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Ecrire le dual de ce problème ; le résoudre par deux méthodes et en déduire la solution du primal.

Exercice VIII

Une association culturelle organise une exposition, pendant cette exposition des tasses de café au lait et des
tasses de chocolat au lait sont vendues pour apporter une aide aux orphelins. Un sponsor a permis de procurer 20
litres de lait, 2 kg de sucre et assez de café et de chocolat pour faire 100 tasses de chaque boisson. On prévoit de
servir 2 sucres par tasse en moyenne ; chaque paquet de sucre contient 120 morceaux et le poids du paquet
indiqué sur la boite est de 500 g ; il faut 1/4 de litre de lait pour une tasse de chocolat et 1/12 de litre de lait pour
une tasse de café. Le trésorier du club propose de vendre à 50 F chaque tasse de chocolat au lait et à 40 F chaque
tasse de café au lait. Déterminez le nombre de tasses de chaque sorte à servir et calculez la recette maximale
collectée par la méthode graphique.

Exercice IX

Une usine produit sur deux chaines des appareils électroniques. En raison de différences importantes dans le
procédés de fabrication, les temps nécessaire aux machines-outils « fabrication » (Fab) et « finition-réglage »
(Fir) pour traiter un appareil diffèrent sensiblement sur chaque chaine avec des prix de revient eux aussi
sensiblement différents. L’élaboration d’un appareil sur la chaine 1 nécessite 3 heures de Fab et 1 heure de Fir,
pour un prix de revient unitaire de 20 F, tandis que la deuxième chaine le produit pour 60 F avec 1 heure de Fab
et 2 heures de Fir. La machine Fab est disponible 60 heures par mois et la machine Fir 70 heures. La demande
étant de 30 appareils par mois au moins. Résoudre ce problème par les méthodes graphique et de simplexe.

Exercice X

La fabrication d’une pièce C coûte 1060 F, celle d’une pièce D 650 F. chaque pièce C et/ou D est traitée
successivement dans trois ateliers. Le nombre d’heures machine par pièce est indiqué dans le tableau suivant :

Atelier I Atelier II Atelier III

Pièce C 3h 5h 2h
Pièce D 1h 3h 3h
Pour éviter un chômage technique, l’atelier I doit obligatoirement fournir 1200 heures-machine, l’atelier II 3300
h et l’atelier III 1680 heures-machine. TAF : Combien faut-il fabriquer de pièces C et/ou de pièces D, pour
rendre minimum le coût de revient de l’ensemble de production et assurer le fonctionnement des trois ateliers
excluant tout chômage technique (utiliser la méthode graphique) ?

Exercice XII

Une entreprise fabrique 2 types de ceintures : A et B. le type A est de meilleur qualité que le type B. le bénéfice
net est de 2F pour le type A et 1,5F pour le type B. le temps de fabrication pour le type A est 2 fois le temps de

3
TDs de Recherche Opérationnelle Dr MBOE BOBO
fabrication du type B et si toutes les ceintures étaient du type B, l’entreprise pourrait en fabriquer 1000 par jour.
L’approvisionnement en cuir est suffisant pour 800 ceintures par jour (type A ou B). Enfin, 400 boucles de type
A et 700 boucles de type B sont disponibles chaque jour. Quels sont les nombres respectifs de ceintures des deux
types à fabriquer chaque jour de manière à maximiser le bénéfice total de l’entreprise (méthodes graphique et du
simplexe)?

Exercice XIII

Résoudre le programme linéaire suivant par la méthode du simplexe

Minimiser Z (x, y) = −2x + y

x − 3y ≥ −1

x−y≤1

x ≥ 0, y ≥ 0

Exercice XIV (DSEP 2016)

L’entreprise Maxi désire produire des articles de type I et/ou de type II. Elle dispose de deux ateliers A et B dont
les capacités maximales sont respectivement de 330 heures et de 420 heures. La production d’un article de type I
nécessite 2 heures de l’atelier A et 4 heures de l’atelier B alors que la production d’un article de type II exige 5
heures de l’atelier B. le marché limité ne peut absorber plus de 100 articles. Un article de type I rapporte net 200
F alors qu’un article de type II rapporte net 270 F. TAF : 1) écrire le programme linéaire qui maximise le profit
total de l’entreprise sous sa forme canonique. 2) Mettre le programme sous sa forme standard puis dresser le
premier tableau de simplex. 3) le tableau suivant correspond à une étape de la résolution :

Base x y 𝑒1 𝑒2 𝑒3 Valeurs Ratio

y 2⁄ 1 1⁄ 0 0 66
5 5
𝑒2 2 0 -1 1 0 90
𝑒3 3⁄ 0 1
- ⁄5 0 1 34
5
Ζ 92 0 -54 0 0 -17 820
a) Ce tableau est-il optimal? Pourquoi? b) déterminer la solution optimale.

Exercice XV

Suite à l’incendie d’un entrepôt, une société fait appel à vos compétences pour reconstituer un programme
linéaire retrouvé sur place, dans un état malheureusement assez délabré. Les seules informations dont vous
disposez consistent en le tableau donné ci-dessous :

1. A l’aide du tableau, déterminer le programme linéaire réalisé par l’entrepôt.

2. Recréer un contexte économique d’entrepôt utilisant les données du tableau précédent.

3. Résoudre le programme linéaire précédent.

4. Comment procède-t-on afin de minimiser la fonction objectif ?

4
TDs de Recherche Opérationnelle Dr MBOE BOBO
Exercice XVI

Une industrie agricole possède 150 hectares de terre et décide de cultiver pas plus de trois plants. Le coût des
engrais des plants A, B et C sont de 60UM, 30UM et 45UM par hectares respectivement. Une somme maximale
de 4800UM peut être dépensée pour l’achat des engrais. Les plants A, B et C nécessite 1 .5, 3 et 1.5 jours de
travail par hectares respectivement, et un maximum de 240 jours de travail sont disponibles. Cette agro-industrie
peut faire des profits de 150UM par hectare pour le plant A, 450UM par hectare pour le plant B et 300UM par
hectare pour le plant C. TAF : 1) Reporter les informations ci-dessus dans un tableau. 2) présentez le programme
linéaire correspondant sous la forme canonique.

Exercice XVII (BTS 2014)

L’entreprise Fadia fabrique deux types de chaussures : « le grand pied et le petit pied ». La fabrication est
assurée dans un atelier où il y a deux machines qui assurent la confection des chaussures. La confection d’un lot
de chaussures grand pied nécessite 2 heures tandis que la confection d’un lot petit pied nécessite 3 heures.
Chaque machine a une capacité de 120 heures par mois. L’entreprise utilise 2 types de matières premières : « la
gomme et le plastique ». La fabrication d’un lot de grand pied demande 1 Kg de gomme et 3 Kg de plastique. La
fabrication d’un lot de petit pied demande 4 Kg de gomme et 7 Kg de plastique. Le fournisseur ne peut livrer
mensuellement que 200 Kg de gomme et 420 Kg de plastique. La vente d’un lot de grand pied procure un
bénéfice de 192 F tandis que le lot de petit pied procure un bénéfice de 184 F. TAF : 1) donner la forme
canonique de ce problème ; 2) Résoudre ce problème par la méthode graphique.

Exercice XVIII (DSEP 2016)

L’entreprise Maxi désire produire des articles de type I et/ou de type II. Elle dispose de deux ateliers A et B dont
les capacités maximales sont respectivement de 330 heures et de 420 heures. La production d’un article de type I
nécessite 2 heures de l’atelier A et 4 heures de l’atelier B alors que la production d’un article de type II exige 5
heures de l’atelier B. le marché limité ne peut absorber plus de 100 articles. Un article de type I rapporte net 200
F alors qu’un article de type II rapporte net 270 F. TAF : Écrire le programme linéaire qui maximise le profit
total de l’entreprise sous sa forme canonique et le résoudre par la méthode du simplexe.

Exercice XIX (BTS 2008)

Une distillerie fabrique sur une machine M deux types de liqueurs : « Parker » et « Quick », mais ces deux types
de liqueurs ne peuvent être produits simultanément. La machine M est disponible 100 heures par semaine. 30
unités de « Parker » ou 50 unités de « Quick » peuvent être produites à l’heure. Chaque unité de « Parker » et
chaque unité de « Quick » laissent respectivement un revenu net de 1 000 F et 3000 F. les demandes sont telles
que, l’on ne doit pas produire plus de 2 000 unités de « Parker », ni plus de 4 000 unités de « Quick » par
semaine. Un raisonnement économique sur les rendements monétaires permettra de trouver facilement les
quantités X de « Parker » et Y de « Quick » à produire chaque semaine pour rendre le revenu net global
maximal. TAF : 1) Donner la fonction économique ; 2) Mettre ce programme linéaire sous forme canonique ; 3)
Résoudre le modèle précédent par deux méthodes.

Exercice XX

Une entreprise de production de café utilise trois types d’ingrédients (A, B, C), afin de produire deux types de
produits : le produit I et le produit II. Les restrictions ou contraintes suivantes doivent être respectées :

Produit I : Pas plus de 30% de A ; moins de 20% de B

Produit II : Pas moins de 50% de A ; pas plus de 30% de B

Les coûts unitaires de A, B et C sont respectivement de : 30 um, 40 um, 35um ; et les quantités disponibles de
ces ingrédients sont de 2000 kgs, 1000 kgs et 3000 kgs respectivement. On vous demande de définir clairement

5
TDs de Recherche Opérationnelle Dr MBOE BOBO
les variables de décision dans un tableau et de formuler le programme linéaire de minimisation de la fonction de
coût de cette entreprise.

Exercice XXI

On doit organiser un pont aérien pour transporter 1600 personnes et 90 tonnes de bagages. Les avions
disponibles sont de deux types: 12 du type A et 9 du type B. Le type A peut transporter, à pleine charge, 200
personnes et 6 tonnes de bagages. Le type B, 100 personnes et 6 tonnes de bagages. La location d’un avion du
type A coûté 800.000 F; la location d’un avion du type B coûte 200.000 F. TAF : Résolvez ce problème par la
méthode du simplexe.

Exercice XXII
La société Beyala fabrique et vend deux articles A et B dont les prix de vente respectifs sont 940 F et 460 F hors
taxes au tarif en vigueur. Cette fabrication nécessite des travaux dans deux ateliers : atelier I et atelier II. Les
temps en heures machine par unité de produit et par atelier ainsi que les capacités quotidiennes maximales sont
indiquées dans le tableau suivant :

Atelier I Atelier II
Article A 3h 4h
Atelier B 4h 2h
Capacités quotidiennes 1 452 h 1 176 h
Par ailleurs, en raison d’un marché limité pour l’article A, il est impossible d’envisager la fabrication et la vente
de plus de 220 articles A par jour. TAF : donner la forme canonique de ce problème et le résoudre.

Exercice XXIII

L’entreprise SAKOU fabrique deux produits dont chacun passe par les départements 1 et 2. Le tableau ci-
dessous donne les besoins en hommes par heures par unité de chaque produit dans chaque département, prix par
unité et le coût de matière première par unité. L’objectif étant de maximiser les bénéfices totaux, formuler le
modèle de programmation linéaire et le résoudre.

Produit A Produit B Capacité mensuelle de travail

Département1 3h/unité 2h/unité 120 heures
Département2 4/unité 6h/unité 260 heures
Prix de vente (U.M) 25 30
Coût de travail (U.M) 16 20
Coût de la matière 1ère (U.M) 4 4

Exercice XIV

Un fermier souhaite obtenir un fertilisant qui nécessite un minimum de 15 unités de potassium, 20 unités de
nitrates et 24 unités de phosphate. Un kg de la marque A nécessité 3 unités de potassium, 1 unité de nitrate et 3
unités de phosphate, son coût est de 120 um. Un kg de la marque B nécessite 1 unité de potassium, 5 unités de
nitrate et 2 unités de phosphate ; son coût est de 60 um. TAF : 1) Reporter les informations ci-dessus dans un
tableau puis formuler ce problème sous forme de PL associé ; 2) Résoudre ce PL par la méthode du simplexe.

Exercice XXV
Un ébéniste fabrique des bureaux sous forme standard ou luxe. Des études de marché ont montré que pour
l’année à venir, les possibilités de vente s’élèvent à 300 unités pour le modèle luxe et à 400 unités pour le
modèle standard. L’approvisionnement en bois est suffisant pour fabriquer annuellement 500 bureaux quel que
soit le type. Par ailleurs, le temps de fabrication d’un modèle luxe est le double de celui d’un bureau de modèle
standard. La capacité annuelle de fabrication est telle que, si tous les bureaux fabriqués étaient de type standard,
on pourrait en fabriquer 700 au maximum. La vente d’un bureau sous le modèle luxe conduit à une marge

6
TDs de Recherche Opérationnelle Dr MBOE BOBO
unitaire sur coût variable égale à 7 F, celle d’un bureau de type standard égale à 5 F. TAF : Rechercher par la
méthode du simplexe, le programme annuel de fabrication conduisant au profit global maximum.

Exercice XXVI

La SAND qui travaille à sa façon, produit deux bien dans son atelier T. le nombre d’heures disponibles pour une
semaine est de 200 heures de fonctionnement. Un produit A consomme 2 heures machines et un produit B
consomme 4 heures machines. Ces produits laissent respectivement une marge sur coût variable de 20 F et 30 F.
les conditions du marché imposent de ne pas produire plus de 1500 unités de A et 40 unités de B. la cadence de
production est distinctement de 60 heures machines pour le produit A et 40 heures machines pour le produit B.
TAF : Quelle est la forme canonique de ce problème linéaire ? Le résoudre par deux méthodes.