Exercices à résoudre

1. [Michel Simonnard, "Programmation linéaire Technique du calcul économique". Dunod, 1972,

p. 22].

Considérons le problème suivant:

Min - 3x1 - 2x2

Sujet à - 2x1 + x2 ≤1
x1 ≤2
x1 + x2 ≤3
x1 ≥ 0, x2 ≥ 0.

i) Donner une représentation géométrique de ce problème.

ii) Résoudre ce problème par la méthode graphique.

2. [Gérald Baillargeon, "Introduction à la programmation linéaire". Les Éditions SMG,

1977, pp. 14-25].

a) Répondre aux mêmes questions que l'exercice précédent dans le cadre du problème suivant:

Max z = 100x1 + 120x2

Sujet à 3x1 + 4x2 ≤ 4200
x1 + 3x2 ≤ 2400
2x1 + 2x2 ≤ 2600
x1 ≥ 0, x2 ≥ 0.

b) La fonction objectif z devient z = 90x 1 + 120x2. En quoi, le problème énoncé en a) est

affecté?

3. [BAIL 77]

Résoudre les problèmes de programmation linéaire suivant par la méthode graphique.

Déterminer, pour chaque cas, la solution optimale, si elle existe (valeurs des variables et de la
fonction économique).
a) Maximiser z = 6x1 + 4x2
avec les contraintes
2x1 + 2,8x2 ≤ 28
x1 + x2 ≥2
3x1 - 7,8x2 ≤ 18
+ x2 ≤7
x1 ≥ 0, x2 ≥ 0.

b) Maximiser z = 5x1 + 4x2

avec les contraintes
15x1 + 20x2 ≥ 90
3x1 + x2 ≥ 18
20x1 + 4x2 ≤ 140
x1 ≥ 0, x2 ≥ 0.

c) Minimiser z = 1,5x1 + x2
sujet à 3x1 + 2x2 ≥6
2x1 - 3x2 ≤0
x1 + x2 ≤8
x2 ≤4
x1 ≥1
x1 ≥ 0, x2 ≥ 0.
Est-ce que la solution optimale est unique?

d) Maximiser z = 2x1 + 3x2

sujet à 4x1 + 2x2 ≤8
x1 ≥7
4x1 - 3x2 ≥ 24
x1 ≥ 0, x2 ≥ 0.

e) Maximiser z = 5x1 + 7x2

sujet à x1 - x2 ≥0
1,5x1 - x2 ≥3
x1 ≥6
x1 ≥ 0, x2 ≥ 0.
f) Minimiser z = 100x1 + 120x2
avec les contraintes
2,5x1 + 2x2 ≥ 15
x1 + 2,5x2 ≥ 25
x1 ≥ 12
x2 ≤ 16
x1 ≥ 0, x2 ≥ 0.

4. [Gérald Baillargeon, "Introduction à la programmation linéaire". Les Éditions SMG, 1977, p.

36]

Le département 742 d'une entreprise ne fabrique que deux types de lampes à utilisation
industrielle. La contribution au bénéfice de l'entreprise est évaluée à

15,00$ l'unité pour la lampe de type SP-100,

22,00$ l'unité pour la lampe de type SP-200.

Le temps de fabrication pour le type SP-200 est le double de temps de fabrication pour le type
SP-100 et si toutes les lampes étaient du type SP-100, le département pourrait en fabriquer 60
unités par jour. Le faible taux de production est spécialement dû à la complexité de la fabrication
des lampes. De plus, l'assemblage des lampes s'effectue en grande partie à l'aide d'opérations
manuelles. D'autre part, les filaments utilisés (un pour chaque type de lampes) pour la fabrication
de ces lampes ont un taux élevé de rejet et la quantité maximale disponible pour le type SP-100
est de 45 filaments par jour et de 25 par jour pour le type SP-200. La quantité totale des deux
types de lampes qu'on peut fabriquer ne peut excéder 50 unités par jour parce qu'ils utilisent la
même chaîne d'assemblage.

Formuler le modèle de programmation linéaire correspondant à ce problème de fabrication et

déterminer, à l'aide de la méthode graphique, le programme optimal de production à mettre en
oeuvre. Vérifier si les contraintes sont respectées.

5. [Gérald Baillargeon, "Introduction à la programmation linéaire". Les Éditions SMG, 1977,

pp. 36-37]

Un petit atelier possède une machine automatique pouvant opérer durant un maximum de 7,5
heures par jour. Avec cette machine on veut fabriquer des chevilles et des boulons et on croit que
le marché peut absorber toute la production. Toutefois, dû à un manque de matière première, la
fabrication des boulons est réduite à un maximum de 1 000 unités par jour. De plus, on considère
qu'au moins 600 unités de chaque élément doivent être fabriquées. Les données concernant le
taux de production, les coûts et les prix de vente sont indiqués dans le tableau suivant:

Éléments Taux- Coût-matériel Main d'œuvre Prix-vente

production $/unité $/heure $/unité
unités/heure

Cheville 300 0,03 3,00 0,08

Boulon 200 0,035 3,00 0,10

On veut maximiser les bénéfices.

a) Formuler ce problème sous forme d'un modèle de programmation linéaire.

b) Déterminer, par la méthode graphique, le programme optimal de production à mettre en

oeuvre. Quel est le bénéfice maximum réalisé?

c) Est-ce que la machine automatique est utilisée à pleine capacité?

d) Si le prix de vente d'un boulon est de 0,11$ au lieu de 0,10$, quelle conséquence aura ce
changement sur le programme optimal de fabrication?

e) Avec cette modification du prix de vente des boulons spécifiée en d), le responsable de
l'atelier suggère de fabriquer 1 000 boulons et autant de chevilles. Est-ce réalisable?
Expliquez.

6. [Frederick S. Hillier, Gerald J. Lieberman, "Introduction to Operations Research".

McGraw-Hill, 5ième édition, 1990, pp. 56.]

Une ferme familiale possède une étendue de 125 acres de terre. Une subvention gouvernementale
de 40,000$ a été accordée pour investir dans cette entreprise familiale. L'entreprise peut produire
jusqu'à 3500 heures - personnes de travail au cours de l'hiver (mi-septembre à mi-mai) et 4000
heures - personnes de travail au cours de l'été. Si ces heures-personnes ne sont pas toutes
utilisées, les plus jeunes membres de la famille utiliseront les heures-personnes disponibles pour
travailler sur une ferme voisine à raison de 5$ de l'heure au cours des mois d'hiver et de 6$ de
l'heure au cours de l'été.
Les revenus de l'entreprise proviennent de trois récoltes et de deux troupeaux de bétail: des
vaches laitières et des poules pour la ponte. Aucun investissement n'est nécessaire pour les
récoltes. Cependant, chaque vache laitière exige une mise de fonds initiale de 1200$ et chaque
poule coûtera 9$.

Chaque vache exigera 1.5 acres de terre, 100 heures-personnes de travail au cours de l'hiver et 50
heures-personnes de travail au cours de l'été. Chaque vache produira un revenu net annuel de
1000$ pour l'entreprise. Les poules n'exigent pas d'acres de terre, mais demandent 0.6 heure-
personne au cours de l'hiver, 0.9 heure-personne au cours de l'été et un revenu net annuel de 5$.
Le poulailler peut contenir jusqu'à un maximum de 3000 poules et la dimension de la grange
limite le troupeau à un maximum de 32 vaches.

Le nombre d'heures personnes estimées et le revenu par acre cultivé pour chaque récolte sont:

Haricot blé avoine

Heures-personnes à l'hiver 20 35 10
Heures-personnes à l'été 50 75 40
Revenu annuel net 600 900 450

La famille voudrait déterminer le nombre d'acres qui devraient être utilisés pour chaque récolte et
le nombre de vaches et de poules que l'entreprise devrait posséder afin de maximiser son profit.

Construire un modèle de programmation linéaire pour ce problème.

7. [Gérald Baillargeon, "Introduction à la programmation linéaire". Les Éditions SMG, 1977,

pp. 38-39]

L'entreprise Westeel-Rosco fabrique deux types de réservoir d'une capacité de 450 litres chacun:
réservoir d'huile et réservoir d'eau. Les deux types de réservoir doivent, dans le processus de
fabrication, passer par différents départements: préparation des gabarits, assemblage, soudure,
polissage. Le réservoir d'eau doit, en plus, passer par le département de peinture.

Le responsable de la fabrication possède les données suivantes concernant le nombre d'heures

requises par unité dans les différents départements, pour fabriquer chaque type de réservoir ainsi
que le nombre d'heures disponibles mensuellement à chaque département:
 Type de réservoir

Départements Eau Huile Disponibilité

(heures)

Préparation des 1 1,5 3 810

gabarits

Assemblage 0,5 1 2 400

Soudure 2 1,5 6 000

Polissage 0,5 1,5 3 000

Peinture 0,2 - 460

Le responsable de la comptabilité possède l'information suivante sur les coûts standards des deux
types de réservoir:

Réservoir d'eau Réservoir d'huile

Matières premières 21$ 24$

Main d'oeuvre

Préparation des gabarits 5$ 8$

Assemblage 3 6

Soudure 12 9

Polissage 2 6

Peinture 2 -

Frais généraux 25 27$

Le budget global mensuel pour les différents frais afférents à la fabrication des deux types de
réservoir est de 250 000$. L'analyse du marché révéla que l'entreprise devrait être en mesure de
prendre au moins 20% du marché des réservoirs d'eau et au moins 40% du marché des réservoirs
d'huile. Le marché global étant actuellement de 2 500 réservoirs d'eau par mois et de 1 500
réservoirs d'huile par mois.

L'entreprise a fixé à 110$, le prix de vente d'un réservoir d'eau et à 130$, celui d'un réservoir
d'huile.

a) Formuler le problème de l'entreprise sous forme d'un modèle de programmation linéaire.

b) Déterminer par la méthode graphique le programme optimal de fabrication à mettre en

oeuvre. L'entreprise veut maximiser ses revenus.

c) Est-ce que tous les départements sont utilisés à pleine capacité? Justifier.

d) Préparer un sommaire de tous les frais mensuels amenés par le programme optimal de
fabrication.

e) Est-ce que la contrainte correspondant au département d'assemblage est restrictive?

Expliquer.

8. [Gérald Baillargeon, "Introduction à la programmation linéaire". Les Éditions SMG, 1977,

pp. 39-40]

L'entreprise Electro-Air fabrique deux modèles d'aspirateur électrique: le modèle économique et

le modèle de luxe. Les deux modèles requièrent l'utilisation de trois départements pour en
assurer l'assemblage. Le modèle économique exige 2 heures de main d'œuvre au département A,
3,5 heures de main-d'œuvre au département B et enfin, 2,6 heures de main-d'œuvre au
département C pour compléter l'assemblage. D'autre part, le modèle de luxe exige 2,4 heures au
département A, 1,8 heure au département B et 4,2 heures de main-d'œuvre au département C.

Le coût des composantes utilisées dans le modèle économique est estimé à 36$ tandis qu'il en
coûte 58$ pour le modèle de luxe.

La main-d'œuvre des départements A et B est rémunérée au taux de 3,20$ l'heure et celle du

département C, 3,50$ l'heure. Les frais généraux sont de 1,30$ l'unité pour le modèle
économique et de 1,86$ l'unité pour le modèle de luxe.
Pour répondre aux besoins du marché, il est essentiel que l'entreprise fabrique au moins 40 unités
par semaine du modèle économique et au moins 25 unités par semaine du modèle de luxe.
L'entreprise est assurée de vendre toute la production hebdomadaire du modèle économique,
toutefois, le département de mise en marché suggère de fabriquer un maximum de 60 unités par
semaine du modèle de luxe.

Le nombre d'heures de main-d'œuvre disponible par jour dans chaque département est:

Département A: 48 heures

Département B: 56 heures

Département C: 80 heures

Le prix de vente du modèle économique est 79$ l'unité et celui du modèle de luxe, 125$ l'unité.
On considérera que la semaine de travail est de cinq jours.

L'entreprise désire établir un programme de production hebdomadaire qui va maximiser les

bénéfices.

a) Structurer ce problème sous forme d'un modèle de programmation linéaire.

b) Déterminer, à l'aide de la méthode graphique, le programme optimal de fabrication

hebdomadaire à mettre en oeuvre.

c) Déterminer le pourcentage d'utilisation de chaque département.

d) Présenter, pour le programme de fabrication optimal, un sommaire des différents coûts (main-
d'œuvre, composantes, frais généraux) pour chaque modèle.

e) Déterminer le chiffre d'affaires et le bénéfice maximum de l'entreprise sur une base

hebdomadaire.

9. Considérons le problème de programmation linéaire sous sa forme standard

Min c tx
sujet à Ax = b
x ≥ 0.
Supposons de plus que ce problème possède une valeur optimale finie.
i) Démontrer que l'ensemble R  m+1 est convexe:
R = {[bt, z]tm+1 : xn tel que Ax = b, x ≥ 0, ctx = z

ii) Soit D  m un ensemble convexe et soit f une fonction à valeur réelle ayant D comme
domaine. La fonction f est une fonction convexe sur D si et seulement si

 d1, d2 D, la relation suivante est satisfaite:

f ( d1 + (1 -)d2) ≤  f(d1) + (1 -) f(d2) 

Dénotons par z(b) la valeur optimale du problème

Min c tx
sujet à Ax = b
x ≥ 0.

Dénotons également B = {b m : X(b) ≠  où X(b) = {x n : Ax = b, x ≥ 0

Démontrer que B est un ensemble convexe et que z(b), perçue comme une fonction définie sur B,
est une fonction convexe sur B.

10. Transformer le problème suivant sous une forme standard:

a) [LUEN 73]

Min |x1| + |x2| + |x3|

sujet à: x1 + x2 ≤ 1
2x1 + x3 = 3

b) Min Max citx + di

i=1, 2, ..., k

sujet à Ax = b, x ≥ 0.

11. [LUEN 73]

Soit C n, un ensemble fermé et convexe tel que C  {x  n| x ≥ 0}. Soit T C l'ensemble
des points où la forme linéaire f(x) = ctx atteint son minimum. Démontrer que si T ≠ , alors il
contient au moins un point extrême de C.
12. [LUEN 73]

Utilisons le résultat de l'exercice 2.6.11, pour démontrer que si un problème de programmation

linéaire, comportant des contraintes d'inégalités et d'égalités, dont toutes les variables sont
contraintes à être non-négatives, est borné inférieurement, alors il existe un point extrême qui est
une solution optimale.

Illustrer à l'aide d'un exemple que ce résultat n'est pas nécessairement vérifié si certaines
variables du problème ne sont pas contraintes à être non-négatives.

13.

Un importateur de whisky dispose d'un marché illimité, mais se trouve restreint par la
réglementation des importations quant aux quantités mensuelles maximales autorisées, qui
s'établissent comme suit:

Sir Roses au plus 2000 bouteilles à 7$

Highland Wind au plus 2500 bouteilles à 5$
Old Frenzy au plus 1200 bouteilles à 4$.

Il effectue trois mélanges A, B et C qu'il vend aux prix respectifs de 6.80$, 5.70$ et 4.50$ la
bouteille.

Ces mélanges se définissent comme suit:

A: pas moins de 60% de Sir Roses,

pas plus de 20% de Old Frenzy

B: pas moins de 15% de Sir Roses,

pas plus de 60% de Old Frenzy

C: pas plus de 50% de Old Frenzy.

On recherche les mélanges qui rendent maximaux les bénéfices de l'importateur. On se contentera
de formuler ce problème comme un programme linéaire.

14. [NOBE 95] Les arbustes

Une agence recrute des travailleurs pour assurer la plantation d'arbustes au rythme de 18 000 par
jour. Son bassin de recrutement comprend à la fois des planteurs expérimentés et des étudiants,
qu'elle attire par la voie des journaux. L'agence exige de chaque planteur expérimenté qu'il plante
70 arbustes à l'heure et qu'il obtienne un taux de reprise de 98%. Les étudiants doivent chacun
planter 40 arbustes à l'heure et obtenir un taux de reprise de 95%. L'agence verse 8$ l'heure aux
planteurs d'expérience et 6$ l'heure aux étudiants; une journée comprend 10 heures de travail.
Pour chaque arbuste qui ne reprend pas, l'agence doit remettre 2$ au propriétaire de la plantation.

L'agence a accès à un bassin de 16 planteurs expérimentés et de 30 étudiants. Combien de ces

personnes l'agence doit-elle recruter si elle cherche à minimiser les coûts engagés pour assurer la
plantation de 18 000 arbustes par jour?

15. [NOBE 95] Les jouets

Un manufacturier a présenté au récent Toy-Fair de Hong-Kong 2 nouveaux jouets qui y ont

connu un éclatant succès. L'engouement a été tel, qu'il n'arrive pas à satisfaire à la demande et est
en train de négocier avec d'autres ateliers pour leur proposer des ententes de sous-traitance. En
attendant la conclusion de ces accords, il veut, au cours du mois qui vient, réaliser le plus de
revenus possibles avec les ressources de son usine. Le manufacturier réalise un profit de 4$ pour
chaque jouet A et de 3$ pour chaque jouet B qu'il fabrique. Chacun de ces nouveaux jouets
requiert les prestations des travailleurs de 2 ateliers: un jouet A requiert 4,5 minutes de travail en
atelier 1, et 2,25 minutes en atelier 2; pour un jouet B, ces durées passent à 3,2 minutes en atelier
1, et à 3,3 minutes en atelier 2. Le manufacturier dispose pour le mois prochain de 725 heures de
main-d'œuvre dans l'atelier 1, et de 610 heures dans l'atelier 2.

Combien de jouets de chaque sorte devra-t-il fabriquer le mois prochain pour utiliser au mieux les
ressources de ces 2 ateliers, s'il s'est déjà engagé à livrer à la fin de ce mois 10 000 jouets B?

16. [NOBE 95] Intervalle de sensibilité

Voici les contraintes d'un modèle linéaire:

x1 - x2 ≤ 6
2x1 + x2 ≤ 24
x2 ≤ 20
x1, x2 ≥ 0

(a) Tracer la région admissible.

(b) Donner les coordonnées des points extrêmes de cet ensemble.

(c) Soit le modèle linéaire consistant à maximiser

z = 14x1 + 7x2

sous les contraintes précédentes. Déterminer une solution optimale de ce modèle qui soit
située ailleurs qu'en un des points extrêmes déterminés en (b).

(d) La fonction objectif z = c1x1 + 2x2 atteint sa valeur maximale au point extrême (10,4)
quand c1 = 5. À quel intervalle doit appartenir c 1, le coefficient de x1 dans la fonction-
objectif, pour que ce point reste solution optimale du modèle linéaire?

(e) Déterminer le point extrême de la région admissible où la fonction-objectif z = 12x 1 - 3x2

atteint sa valeur minimale.

_______________________________________________