Programmation linéaire

Composition d’aliments pour le bétail

On désire déterminer la composition, à coût minimal, d’un aliment pour bétail qui est obtenu en
mélangeant au plus 3 produits bruts : orge, arachide, sésame. L’aliment ainsi conditionné devra
comporter au moins 22% de protéines et 3,6% de graisses. On a indiqué ci-dessous les pourcentages
de protéines et de graisses contenus respectivement dans l’orge, l’arachide et le sésame, ainsi que le
coût par tonne de chacun des produits bruts.

Produit brut 1. Orge 2. Arachides 3. Sésame Pourcentage

1-On notera xi i=1,2,3, la fraction de tonne de produit brut i contenu dans 1 tonne d’aliment. La
somme de ces variables doit donc faire 1. Formuler le problème.

2-Eliminer la variable x1 , puis résoudre le problème graphiquement.

Problème de production

Une usine fabrique 2 produits liquides P1 et P2.

Chaque litre de ces produits demande des heures de fabrication sur les machines A,B,…,F. comme
indiqué sur le tableau suivant. Chaque machine n’est disponible qu’un certain nombre d’heures dans
la semaine.

A B C D E F
P1 0 1,5 4 5 3 3
P2 3 2 3 2 4 0
Disponibilité 30 30 60 50 60 60

Chaque litre de produit P1 rapporte 1600 euros et chaque litre de produit P2 3200 euros. On veut
trouver la production par semaine qui maximise le gain total.

1-Ecrire le programme linéaire correspondant avec x1 et x2 la quantité en litre produite de P1 et de

Résolution d’un programme linéaire par la méthode des tableaux du simplexe

Soit le programme linéaire :

1
 max 𝑧 = 2𝑥1 + 𝑥2

𝑥1 − 𝑥2 ≤ 3
Sous les contraintes x1 0 , x2 0 et { 𝑥1 + 2𝑥2 ≤ 6
−𝑥1 + 2𝑥2 ≤ 2

1-Rajouter les variables d’écart (positives ou nulles). Puis résoudre le problème par l’algorithme du
simplexe et la méthode des tableaux.

2-Pour vérifier le résultat de la question précédente, résoudre le problème (à 2 variables x1, x2)
graphiquement.

Crème glacée

Un fabricant désire produire 100kg d’une préparation pour crème glacée. Cette préparation doit
contenir 21,5kg de matières grasses, 21kg de sucre, 1,2kg d’œuf et 56,3 kg d’eau. Les ingrédients
dont il dispose figurent en tête des colonnes du tableau ci-dessous, les constituants figurent en ligne.
Ce tableau donne les pourcentages en poids de chaque constituant dans chaque ingrédient ainsi que
le coût par kg de chaque ingrédient.
crème jaune d'oeuf frais lait entier en poudre jaune d'oeuf surgelé et sucré sirop de sucrede canne eau

matières grasses 40 50 12 30
sucre 14 70
oeuf 40 40
eau 60 10 88 16 30 100
coût 3 4 1 2 0,80 0

Le fabricant désire déterminer la composition du mélange d’ingrédients de coût minimal et

1- Modéliser le problème par un programme linéaire comportant 6 variables x1,…,x6 représentant les
quantités d’ingrédients (crème, jaune d’œuf frais,…,eau) utilisées et 4 contraintes d’égalité.
2- Jusqu’à présent le fabricant produisait le mélange suivant :
crème = 50kg., Jaune d’œufs frais = 3kg., sirop de sucre de canne = 30kg., eau = 17kg.
Cette solution est-elle une solution de base ? Pour cela chercher la matrice B associée. On admettra
 0,4 0,5 0 0
 
 0 0 0,7 0
que la matrice suivante est inversible B=  .
0 0,4 0 0
 
 0,6 0,1 0,3 1 

a-A l’aide des 4 contraintes du problème, exprimer x1, x2, x5, x6 en fonction de x3, x4.
On note z la fonction objectif représentant le coût du mélange. Exprimer alors z en fonction de x3, x4.
En déduire le tableau simplexe relativement à cette base. Le mélange est-il optimal ?
b-Même question en utilisant la méthode matricielle et l’inverse de B donné ci-dessous.

2
  1 / 0,4 0  0,5 / 0,16 0
 
 0 0 1 / 0,4 0
B-1= 
0 1 / 0,7 0 0
 
  0,6 / 0,4  0,3 / 0,7 0,26 / 0,16 1 

3- Soit le tableau simplexe suivant :
base x1 x2 x3 x4 x5 x6
x1 1 0 0,3  0,5 0 0  50
x2 0 1 0 1 0 0  3
x5 0 0 0 0,2 1 0  30
x6 0 0 0,7 0,3 0 1  17
0 0 0,1  0,66 0 0   186  z

Déterminer la composition du mélange optimal en appliquant l’algorithme du simplexe à partir de ce

4-Par suite de fluctuations économiques les prix de la crème et du jaune d’œuf frais passent
respectivement de 4 à 7. Le mélange déterminé à la question 3 est-il toujours de coût minimal ?

Méthode des 2 phases

Soit le programme linéaire (P) suivant :

max 𝑧 = 𝑥1 + 𝑥2

𝑥1 + 𝑥2 ≥ 1
Sous les contraintes x1 0 , x2 0 et { 𝑥1 ≤ 1
𝑥2 ≤ 1

1-Ecrire le problème sous forme standard en rajoutant 3 variables d’écart (jamais négatives). Faire
attention au signe de la première.

2-La solution 𝑥1 = 𝑥2 = 0 autrement dit 𝑥1 , 𝑥2 hors-base est-elle une solution de base réalisable ?

3-Résoudre (P) en utilisant la méthode des 2 phases.