OL – Optimisation Linéaire année 2020–2021

Cahier de TD

1 Programmation linéaire - Modélisation

Exercice 1 – Fabrication de télévisions

Une entreprise fabrique trois modèles de TV A, B et C qui lui rapportent des profits de 160, 300 et
500 Euros. Les niveaux minima de production pour une semaine sont de 100 pour A, 150 pour B et
75 pour C. Chaque douzaine de TV de type i requiert un temps Fi pour la fabrication, un temps Ai
pour l’assemblage et un temps Ei pour l’emballage.

i A B C
Fi 3 3,5 5
Ai 4 5 8
Ei 1 1,5 3

Pendant la semaine à venir, l’entreprise aura 150 heures disponibles pour la fabrication, 200 pour
l’assemblage et 60 pour l’emballage. On peut noter que l’usine étant en production constante, le plan
de production demandé peut prévoir un nombre fractionnaire de télévisions.
Q 1.1 Définir les variables définissant le plan de production.
Q 1.2 Donner la fonction objective du problème dans le but de maximiser le profit de l’entreprise
Q 1.3 Dans un plan de production encodé par vos variables, donner la quantité d’heures utilisées
pour la fabrication d’une télévision de type A. Indiquer alors la quantité totale de temps utilisé pour
la fabrication. En déduire une contrainte horaire sur le temps de fabrication.
Q 1.4 Formuler le problème sous forme d’un programme linéaire.
Q 1.5 Mettre le modèle sous forme standard.
Q 1.6 Que représentent les variables d’écart ?
Q 1.7 La solution optimale de ce problème est de produire en nombre de télévisions par semaine :
100 de type A, 263,33 de type B et 75 de type C. Que peut-on analyser sur le problème à partir de
cette solution optimale ?

Exercice 2 – Combinaison optimale

Une personne soucieuse de sa forme physique souhaite absorber chaque jour 36 grammes de Vitamine
A, 28 grammes de Vitamines C et 32 grammes de Vitamine D. Deux marques sont susceptibles de
fournir ces apports. La marque 1 coûte 3 centimes d’euros par comprimé. Chaque comprimé pèse 12
grammes : il procure 2 grammes de Vitamine A, 2 grammes de Vitamine C et 8 grammes de vitamine
D. La marque 2 coûte 4 centimes d’euros par comprimés. Chaque comprimé pèse 7 grammes et procure
3 grammes de Vitamine A, 2 grammes de Vitamine C et 2 grammes de vitamine D.
OL – Optimisation Linéaire page 2

Il s’agit de trouver la combinaison respectant les exigences d’absorption quotidiennes au moindre coût.
On peut couper un comprimé de chacune des deux marques de manière à ne prendre qu’une fraction
de chaque comprimé.
Q 2.1 Définir les variables de décision de ce problème.
Q 2.2 Formuler la fonction objectif.
Q 2.3 Ecrire les contraintes.

Exercice 3 – Fabrication de Yaourts

Un fabriquant de yaourt produit 2 types de yaourts à la fraise A et B à partir de fraise, de lait et de

sucre. Chaque yaourt doit respecter les proportions suivantes de matières premières.
A B
Fraise 2 1
Lait 1 2
Sucre 0 1
Les matières premières sont en quantité limitée : 800 kilos de fraises, 700 kilos de lait et 300 kilos de
sucre. La vente des yaourts A rapportent 4e par kilo et les yaourts B 5e.
Donner une formulation du problème sous la forme d’un programme linéaire.

Exercice 4 – Culture de blé et de pommes de terre

Un fermier dispose de 100 acres de terre, et de 1100e d’investissement pour une période de 160 jours
de main d’oeuvre. En tenant compte de l’ensemble
 des informations suivantes :
20e par acre de blé
— Coût de travail et d’ensemencement
10e par acre de pommes de terre

120e par acre de blé
— Revenus
40e par acre de pommes de terre

4 jours par acre de blé
— Temps de main d’oeuvre
1 jours par acre de pommes de terre
quelles surfaces en blé et en pommes de terre faut-il cultiver pour obtenir un revenu maximum ?

Exercice 5 – Ateliers en usine

Une usine composée de 3 ateliers A, B, C fabrique trois produits 1, 2, 3 en quantités mensuelles x1 , x2 ,

x3 à déterminer. Les ateliers A, B, C sont limités respectivement à 400, 300 et 240 heures de travail
par mois.
— Le produit 1 est traité suivant le processus :
ateliers successifs : A C B C
rendements horaires : 1/4 2 5/4 2
— Le produit 2 est traité selon le processus :
ateliers successifs : A B C
rendements horaires : 1/5 10/9 10/7
OL – Optimisation Linéaire page 3

— Le produit 3 est traité selon le processus :

ateliers successifs : B C
rendements horaires : 1 5/4
Les demandes mensuelles pour les 3 produits sont respectivement au plus égales à 50, 100, 150 (une
demande non satisfaite n’implique pas de pénalité spéciale).

Les revenus unitaires respectifs sur les 3 produits sont : 350, 250 et 400 e.
1. Montrer que ce problème se ramène à un programme mathématique linéaire (écrire les contraintes
et la fonction économique).
2. Montrer que 2 contraintes sont en fait redondantes.
3. Montrer que le programme se ramène à un problème à deux dimensions avec deux contraintes
dont une de borne.
4. Résoudre le problème graphiquement.

Exercice 6 – Productique

Soit une entreprise disposant de deux machines pour traiter trois produits P1 , P2 et P3 . Les temps de
traitement en minutes par unité de ces produits sont :

machine 1 machine 2
P1 5 6
P2 3 5
P3 2

Les productions de ces biens doivent être en nombres d’unités par heure exactement :

8 pour P1 , 9 pour P2 , et 5 pour P3 .

Les dépenses de fabrication par unité de fabrication sont :

machine 1 machine 2
P1 20 26
P2 8 16
P3 12

1. Mettre sous forme d’un programme linéaire le problème qui consiste à répartir les traitements
des produits sur les deux machines dans le but de minimiser les dépenses de production.
note : poser xij = quantité de produit Pj , j ∈ {1, 2, 3} à traiter en une heure par la machine
i ∈ {1, 2}.
2. Quelle est la valeur optimale de x23 ?
3. En déduire une forme réduite du modèle.

Exercice 7 – Résolution graphique

OL – Optimisation Linéaire page 4

Q 7.1 On considère le problème de programmation linéaire (P) suivant :



 min z = −x1 + 4x2
−3x1 + x2 ≤ 6



x1 + 2x2 ≤ 4
x ≥ −1

1



x2 ≥ −3


1. Formuler le problème (P) en un problème (P’) dans lequel toutes les variables sont positives.
2. Résoudre graphiquement le problème (P’).
3. Déduire la solution optimale de (P) à partir de (P’).

Exercice 8 – Résolution graphique (2)

Montrer graphiquement si les problèmes de programmation linéaire suivants possèdent ou non des
solutions réalisables.
a) 
 max z = x1
 + 2x2
−x1 + x2 ≤ −2


 4x 1 + x 2 ≤ 4
xi ≥ 0, ∀ i ∈ {1, 2}


b) 

 max z = x1 + 2x2
−x1 + x2 ≤ −2


 4x1 + x2 ≥ 4
xi ≥ 0, ∀ i ∈ {1, 2}


c) 

 max z = x1 + 2x2
−x1 + x2 ≥ −2


 4x1 + x2 ≤ 4
xi ≥ 0, ∀ i ∈ {1, 2}


Exercice 9 – Confitures

Un producteur de confitures veut produire une confiture Fraise-Framboise. Il peut acheter au plus
200 kg de fraises à 7e le kilo et 200 kg de framboises à 14e le kilo. Il peut avoir autant de sucre
que nécessaire à 1e le kilo. La législation sur les confitures est qu’un pot de confiture doit contenir
au moins 35% de fruits : le reste pouvant être du sucre. Pour pouvoir annoncer une confiture Fraise-
Framboise, chacun des deux fruits doit au moins être en proportion de un quart sur la quantité de
fruits. Le producteur veut produire exactement une tonne de confiture.

On utilise les variables x1 , x2 , x3 pour représenter la quantité en kilogrammes de fraise, de framboise

et de sucre respectivement.
OL – Optimisation Linéaire page 5

Q 9.1 Modéliser le problème pour minimiser le prix d’achat des ingrédients.

Q 9.2 Peut-on déterminer la solution sans résoudre un programme linéaire ?

Exercice 10 – Exploitation de mines

Une société minière américaine exploite 3 mines de Virginie Occidentale. Le minerai extrait de chaque
mine est séparé en deux qualités notées HQ (haute qualité) et BQ (basse qualité), avant d’être expédié
chez les clients. La société minière s’est engagée à livrer 54 tonnes de minerai HQ et 65 tonnes de
minerai BQ pour la fin de la semaine. L’exploitation des mines est possible 7 jours sur 7 mais on peut
travailler moins. Le coût d’exploitation de chaque mine est proportionnel au temps de travail, exprimé
en jours de travail, par un nombre réel. Les capacités de production des mines, ainsi que les coûts
d’exploitation journaliers sont donnés dans le tableau ci-dessous :

Minerais HQ Minerais BQ Coût d’exploitation

tonnes/jour tonnes/jour Milliers de dollars/jour
Mine I 4 4 20
Mine II 6 4 22
Mine III 1 6 18
On souhaite déterminer les temps de travail optimaux dans chaque mine pour la semaine à venir
de manière à ce que la société minière puisse tenir ses engagements à moindre coût. Formaliser ce
problème comme un programme linéaire que l’on mettra sous forme standard (on ne demande pas de
le résoudre), en prenant soint de préciser la définition de vos variables de décision.

Exercice 11 – Essence sans plomb

Une raffinerie veut fabriquer dans une période donnée de l’essence sans plomb avec 3 ingrédients : du
butane, du naphta lourd et du réformat catalytique. Quatre caractéristiques de l’essence résultante et
de ses composants sont importants : le coût, l’indice d’octane, la tension de vapeur et la volatilité. Ces
caractéristiques sont résumées dans le tableau ci-dessous. L’indice d’octane est une mesure du pouvoir
antidétonant du carburant dans le moteur (un faible indice donne un “cognement” caractéristique).
La tension de vapeur et la volatilité sont très liées. La tension de vapeur est une mesure du risque
d’explosion au stockage, notamment par temps chaud. La volatilité est plutôt une mesure de la facilité
de démarrage du moteur par temps froid.

Caractéristiques Butane Réformat Naphta Essence

Coût/tonne 7.3 18.2 12.5 ?
Indice d’octane 120 100 74 ≥ 94
Tension de vapeur 60 2.6 4.5 ≤ 11
Volatilité 105 3 12 ≥17

On suppose que les intéractions entre ingrédients sont linéaires : par exemple un mélange 50-50 de
butane et de réformat aura un indice d’octane 0.5*120+0.5*100=110. Cette simplification est exacte
avec l’essence sans plomb : de légères non-linéarités existent pour l’essence classique avec plomb.
On dispose de 800t de butane seulement, tandis que les autres ingrédients sont en quantité supérieure
à la capacité de production sur la période et sont donc virtuellement illimités. La raffinerie fabrique
OL – Optimisation Linéaire page 6

aussi du fuel lourd sur les mêmes installations, et la capacité totale de production est limitée à 12000t
(essence+fuel). Le processus de fabrication du fuel est fixé et n’intervient pas dans le problème d’op-
timisation qui nous intéresse. On sait seulement que ce produit rapporte 2.5 par tonne, coût des
ingrédients compris. L’essence rapporte par contre 18.4 par tonne, mais le coût des ingrédients n’est
pas compris et doit être déduit. Dernière remarque, lors des mélanges de produits, il n’y a pas de perte,
ni d’ajout : ainsi les quantités résultantes des mélanges sont bien la somme des quantités mélangées.
L’objectif est de calculer les quantités d’ingrédients et d’essence à fabriquer de façon à respecter les
contraintes et à maximiser le profit total de la raffinerie sur la période. L’originalité du problème est
qu’on ne connaı̂t pas le coût de fabrication de l’essence, car il va dépendre des proportions des divers
ingrédients.

1.1 Programmation linéaire - Algorithme du simplexe

Exercice 12 – Industrie Pharmaceutique

Une industrie pharmaceutique a le choix de produire 4 sortes de médicaments pour soigner une maladie
rénale. La fabrication de chaque médicament donne un profit mais produit également des déchets
toxiques dont les pourcentages dépendent de la quantité fabriquée. Dans le tableau suivant, a(i, j)
représente la quantité en kilogrammes de déchet i produit par la fabrication de 100 kg du médicament
j. On donne également le profit en centaine d’euros par kilogramme du médicament j.
Médicament M1 M2 M3 M4
toxique T1 20 20 10 40
T2 10 30 20 0
T3 20 40 30 10
profit 15 60 4 20
Les réglementations en vigueur limitent la production maximale des déchets toxiques T1 , T2 et T3 à
21, 6 et 14 kg respectivement par semaine. Calculer les productions par semaine de façon à respecter
les restrictions tout en maximisant le profit.

Exercice 13 – Visualisation de l’algorithme du simplexe

On considère le programme linéaire suivant :



 max z = −3x1 + 5x2
−2x1 + 3x2 ≤ 6


 x1 − 4x2 ≤ 4
xi ≥ 0, ∀ i ∈ {1, 2}


Q 13.1 Résoudre ce programme linéaire par la méthode du simplexe.

Q 13.2 Visualisez graphiquement le domaine de définition de ce programme linéaire et interprétez le
résultat de la question précédente.
OL – Optimisation Linéaire page 7

Exercice 14 – Conditions nécessaires et suffisantes

Déterminer les conditions nécessaires et suffisantes pour s et t de façon à ce que le programme linéaire
suivant :

 max z = x1 + x2
sx1 + tx2 ≤ 1
xi ≥ 0, ∀ i ∈ {1, 2}


- possède une solution optimale

- soit non-réalisable
- soit non-borné

Exercice 15 – Algorithme du simplexe

Soit le programme linéaire P suivant sous forme canonique :

max z = 1/2 x1 + 1/2 x2

3x1 + 2x2 ≤ 12
x1 + 2x2 ≤ 8
xi ≥ 0, i = 1, 2
Pour écrire la forme standard, on ajoute les deux variables d’écart non-négatives suivantes :
e1 = 12 −3x1 − 2x2
e2 = 8 −x1 − 2x2

Q 15.1 Montrer que si les variables en base sont {e1 , x1 } et que les variables hors base sont {e2 , x2 }
alors le sommet associé à cette base n’est pas réalisable.
Q 15.2 On choisit maintenant de mettre en base les variables {x1 , x2 } et hors base les variables
{e1 , e2 }. L’expression des variables en base en fonction des variables hors base donne alors :
x1 = 2 −1/2 e1 + 1/2 e2
x2 = 3 +1/4 e1 − 3/4 e2
Déterminer la solution associée à cette base. En vous servant de l’expression des variables en base
en fonction des variables hors base donnée ci-dessus, montrer qu’il s’agit de la solution optimale du
problème P et donner la valeur de l’objectif à l’optimum.
Q 15.3 On considère maintenant la généralisation du problème P notée Pα qui consiste à remplacer
la fonction objectif de P par : max zα = αx1 + (1 − α)x2 , pour une valeur α ∈ [0, 1]. Déterminer
l’intervalle de valeurs de α pour lequel la solution obtenue à la question précédente reste optimale.

1.2 Compléments sur l’algorithme du simplexe

OL – Optimisation Linéaire page 8

Exercice 16 – Méthode des deux-phases

On s’intéresse au programme linéaire suivant



 max z = 3x1 + x2
−x1 + x2 ≥ 1



(P) x1 + x2 ≥ 2
2x1 + x2 ≤ 4




xi ≥ 0, ∀ i∈ {1, 2}


Q 16.1 Montrez que la bases des variables d’écart n’est pas réalisable. Représenter ce cas en dessinant
le domaine de définitions de (P ).
Q 16.2 On ne peut donc pas démarrer la phase 2 de l’algorithme du simplexe en utilisant la base des
variables d’écart. On commence donc par la phase 1.
Ecrire le programme auxiliaire noté (P 0 ) associé à (P ) obtenu en ajoutant des variables artificielles.
Q 16.3 Résoudre le programme (P 0 ) en partant de la base des variables artificielles.
Q 16.4 A l’issue de la phase 1 où vous avez résolu le programme auxiliaire (P 0 ), quelle valeur objective
obtenez-vous ? Que peut-on en déduire ?
Q 16.5 Déduire de l’écriture finale en base optimale de (P 0 ), une base réalisable pour (P ). Est-elle
optimale pour (P ) ?
Q 16.6 Résoudre le programme (P ).

Exercice 17 – Cas particuliers de la méthode du simplexe

Résoudre les programmes linéaires suivants.



 max z = 3x1 + x2
x1 − x2 ≤ −1



(P1 ) −x1 − x2 ≤ −3
2x1 + x2 ≤ 2




xi ≥ 0, ∀ i∈ {1, 2}




 max z = 3x1 + x2
x1 − x2 ≤ −1



(P2 ) −x1 − x2 ≤ −3
2x1 − x2 ≤ 2




xi ≥ 0, ∀ i∈ {1, 2}


1.3 Dualité
OL – Optimisation Linéaire page 9

Exercice 18 – Algorithme du simplexe et dualité

Soit le problème de programmation linéaire (P) suivant :


 max z = 3x1 + x2 + 4x3
6x1 + 3x2 + 5x3 ≤ 25


 3x 1 + 4x2 + 5x3 ≤ 20
xi ≥ 0, ∀ i∈ {1, 3}


Le dictionnaire optimal est donné par :

 x1 = 53 + 13 x2 − 1 1

3 x4 + 3 x5
1 2
x3 = 3 − x2 + 5 x4 − 5 x5
1 3
z = 17 − 2x2 − 5 x4 − 5 x5


Q 18.1 Donner la solution optimale. Préciser les variables de base et les variables hors-base.
Q 18.2 Formuler le problème dual associé au problème (P).
Q 18.3 Identifier la solution optimale du problème dual dans le dictionnaire optimal.

Exercice 19 – Dualité

Soit le problème P suivant :

min z = 7x1 + 10x2 + 4x3
x1 + x2 ≥ 2
x1 + 2 x2 + x3 ≥ 3
xi ≥ 0, i = 1, 2, 3

Q 19.1 Ecrire le dual D du programme linéaire P.

Q 19.2 Résoudre graphiquement le problème D, donner sa solution optimale et la valeur de la fonction
objectif à l’optimum.
Q 19.3 En utilisant le théorème des écarts complémentaires, déduire de la question précédente la
solution optimale de P.
Q 19.4 On modifie le second membre des contraintes de P en remplaçant (2, 3) par (3, 2). Quel est le
surcoût induit par ce changement sur la valeur optimale de P ?

Exercice 20 – Théorème de la dualité

Q 20.1 Illustrer le théorème de la dualité pour les programmes linéaires suivants :

OL – Optimisation Linéaire page 10

1. 

 min z = 2x1 + 2x2
−x1 + x2 ≤ 1


 x1 − x2 ≤ 1
xi ≥ 0, ∀ i ∈ {1, 2}


2. 

 max z = 2x1 + 2x2
−x1 + x2 ≤ 1


 x1 − x2 ≤ 1
xi ≥ 0, ∀ i ∈ {1, 2}


3. 

 max z = 2x1 + 2x2
−x1 + x2 ≥ 1


 x1 − x2 ≥ 1
xi ≥ 0, ∀ i ∈ {1, 2}


Exercice 21 – Théorème des écarts complémentaires

On considère le PL (P ) suivant :


 max 18x1 − 7x2 + 12x3 + 5x4 + 8x6



 2x1 − 6x2 + 2x3 + 7x4 + 3x5 + 8x6 ≤ 1
−3x1 − x2 + 4x3 − 3x4 + x5 + 2x6 ≤ −2



(P ) 8x1 − 3x2 + 5x3 − 2x4 + 2x6 ≤ 4
4x1 + 8x3 + 7x4 − x5 + 3x6 ≤ 1




5x1 + 2x2 − 3x3 + 6x4 − 2x5 − x6 ≤ 5




xi ≥ 0, ∀ i∈ {1, 6}


Q 21.1 Utilisez le théorème des écarts complémentaires pour prouver que la solution x̃ = (2, 4, 0, 0, 7, 0)
est optimale pour (P ).
Q 21.2 Nous allons généraliser l’approche précédente. Etant donnée une solution réalisable x̃ d’un PL
sous forme canonique max, donner à partir du théorème des écarts complémentaires, les conditions
que doit remplir une solution ỹ du dual pour que les solutions x̃ et ỹ soient optimales pour le primal
et le dual.
Q 21.3 En utilisant la question précédente, justifier si x̃ est encore optimale pour le PL (P ) lorsque
le coefficient de la variable x3 passe de 12 à 18.

Exercice 22 – Encore un petit exo

On considère le programme linéaire P suivant :

max z = 8x1 + 6x2 + 10x3


2x1 + x2 + x3 ≤ 20
x1 + x2 + 5 x3 ≤ 15
OL – Optimisation Linéaire page 11

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Q 22.1 Déterminer le dual D de ce programme linéaire.

Q 22.2 Déterminer la solution optimale de D par résolution graphique et en déduire la solution
optimale de P.
Q 22.3 Mettre le problème P sous forme standard. Déterminer alors les variables de base et les
variables hors base associées à la solution trouvée en 2. Exprimer alors la fonction objectif de P en
fonction des variables hors base.
Q 22.4 On anticipe une augmentation λ > 0 du coefficient de x3 dans la fonction objectif de P (qui
devient donc 10 + λ). Déterminer à partir de quelle valeur de λ la solution obtenue à la question
précédente n’est plus optimale pour le problème P(λ).
Q 22.5 On remplace le second membre (20, 15) du problème P par (12, 24). Déterminer la solution
optimale du problème primal ainsi modifié.

1.4 Dualité - Paramétrisation

Exercice 23 – Écarts complémentaires

Soit le problème de programmation linéaire suivant :


 min z = 4x1 + 5x2 + 7x3



 x 1 + x2 + x3 = 1
+ 5x2 + 3x3 ≥ 2


 + x2 + 2x3 ≥ 1
+ 4x2 + x3 ≤ 2




xi ≥ 0, ∀ i ∈ {1, . . . 3}


En utilisant le théorème des écarts complémentaires, justifier si la solution ( 72 , 37 , 27 ) est optimale pour
ce programme et, si c’est le cas, indiquer la solution optimale du programme dual.

Exercice 24 – Gaufres ou crêpes

Une entreprise produit des pâtes prêtes à l’emploi pour réaliser des gaufres ou des crêpes. Pour réaliser
1 kg de pâtes à gaufres, elle utilise 0,4 kg de farine, 0,2 kg de lait et 0,4 kg d’œuf. Pour 1 kg de pâtes
à crêpes, elle utilise 0,3 kg de farine, 0,5 kg de lait et 0,2 kg d’œuf. De plus, l’emballage en brique
alimentaire et les frais de gestion de l’ensemble de l’entreprise lui coûte 2e par kg de pâtes.
L’entreprise a conclu depuis plusieurs années un contrat d’approvisionnement avec un fournisseur qui
lui livre chaque semaine 1,2 tonnes de farine, 1 tonne de lait et 1 tonne d’œufs au prix global de
2000e par semaine.
Elle vend 3,5e le kg de pâte à gaufres et 3,6e le kg de pâte à crêpes.
OL – Optimisation Linéaire page 12

L’entreprise souhaite remettre en cause son contrat d’approvisionnement. Or dans ce contrat, elle en
connaı̂t le coût total mais pas le coût de chaque ingrédient. Pour remettre en cause ce coût, elle désire
calculer le coût marginal, en e/kg, de chacun des ingrédients, c’est-à-dire la proportion du revenu
correspondant à l’utilisation d’1 kg d’un ingrédient sans prendre en compte le coût de l’ingrédient.
Q 24.1 On considère les variables y1 , y2 et y3 correspondant au coût marginal d’1 kg de farine, de lait
et d’œuf.
a) Donner le coût total de production en fonction de ces variables.
b) Donner le coût marginal d’1 kg de pâte à gaufres sans prendre en compte le prix des ingrédients.
c) Quelle inégalité doit vérifier ce coût d’1 kg de pâte à gaufres par rapport à son prix de vente ?
d) En déduire un programme linéaire permettant de calculer ces coûts marginaux.

Q 24.2 Donner le dual (D) du programme (P ). Interpréter-le et indiquer à quoi correspond sa solution
optimale pour l’entreprise.
Q 24.3 La solution obtenue par Glpk à partir de (P ) est la suivante :
Rows: 2
Columns: 3
Non-zeros: 6
Status: OPTIMAL
Objective: obj = 4812.5 (MINimum)

No. Row name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------
1 r.3 NL 1.5 1.5 1875
2 r.4 NL 1.6 1.6 1250

No. Column name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------
1 y1 NL 0 0 75
2 y2 B 2.125 0
3 y3 B 2.6875 0
et celle à partir de (D) :

Rows: 3
Columns: 2
Non-zeros: 6
Status: OPTIMAL
Objective: obj = 4812.5 (MAXimum)

No. Row name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------
1 r.3 B 1125 1200
2 r.4 NU 1000 1000 2.125
3 r.5 NU 1000 1000 2.6875
OL – Optimisation Linéaire page 13

No. Column name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------
1 x1 B 1875 0
2 x2 B 1250 0

En déduire les coûts marginaux des ingrédients.

Q 24.4 A quel prix l’entreprise peut-elle avantageusement renégocier les prix de la farine, du lait et
des œufs ?

Exercice 25 – Intervalles de stabilité

Une entreprise pharmaceutique, nommée Hypnos, produit un somnifère à base de morphine. La

législation étant très sévère, le gouvernement étudie des lois pour limiter la production par entre-
prise afin d’en surveiller la production. L’entreprise Hypnos voit sa production totale limitée à 800 kg.
En revanche, le gouvernement souhaite inciter la production pour l’exportation : pour cela il impose
que la production pour la vente en France ne dépasse pas la production pour l’exportation de plus de
200kg . D’autre part, le gouvernement veut néanmoins maintenir les ventes en France et exige que la
production pour l’exportation ne dépasse pas de plus de 200 kg les deux tiers de la production pour
la vente en France.
Q 25.1 En notant x1 la production de 100 kg du somnifère pour la vente en France et x2 la production
de 100kg du somnifère pour son exportation, donner les contraintes du problème que doit résoudre
Hypnos.
Q 25.2 Le profit de la vente du somnifère en France est de 6 ke par centaine de kg et de 5 ke par
centaine de kg à l’exportation. La manipulation de la morphine étant très réglementée, une taxe de
p ke par centaine de kg est imposée lors de la production. Pour la vente en France, il faut payer une
deuxième fois cette taxe lors de la vente. Pour l’exportation, une aide à l’exportation compense 2 fois
la taxe p déboursée. Donner le montant du profit total pour l’entreprise Hypnos.
Q 25.3 Pour le problème de programmation linéaire paramétré suivant :

 max z = (6 − 2p)x1 + (5 + p)x2

x1 + x2 ≤ 8



−2x1 + 3x2 ≤ 6
x1 − x2 ≤ 2




xi ≥ 0, ∀ i∈ {1, 2}


Un intervalle de stabilité pour p est un intervalle pour lequel une solution x est optimale pour tout
l’intervalle. Donner les intervalles de stabilité du paramètre p.
Q 25.4 Déduire de la question précédente, l’impact de la valeur de la taxe p sur le profit d’Hypnos.
En déduire les conséquences sur la production d’Hypnos et sur l’utilité des contraintes vis à vis des
objectifs du gouvernement.

Exercice 26 – Dualité - Paramétrisation

OL – Optimisation Linéaire page 14

Soit le problème de programmation linéaire (P ) suivant :



 max z = x1 + 3x2 − x3
2x1 + 2x2 − x3 ≤ 10



3x1 − 2x2 + x3 ≤ 10
x1 − 3x2 + 2x3 ≤ 10




xi ≥ 0, ∀ i∈ {1, 3}


Q 26.1 Déterminer une base optimale BP de (P ). Est-elle unique ?

Q 26.2 Écrire le programme linéaire dual (D) de (P ). Déterminer directement à partir de BP une
base optimale BD de (D).
Q 26.3 On considère le problème (P ) obtenu à partir de (P ) en remplaçant les trois seconds membres
de P par 10(1 + ).
a) Démontrer que, pour tout  ≥ 0, la solution associée à BP reste optimale pour (P ).
b) En déduire la valeur optimale de (P ).
c) Trouver la solution de (P ).