REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LARECHERCHE SCIENTIFIQUE

ECOLE NATIONALE POLYTECHNIQUE

Théorie des Graphes

Support de cours du module Informatique 3

Chapitre 4: La programmation linéaire

Partie 01: La modélisation d’un programme linéaire et la résolution

graphique

2ème année cycle préparatoire

Par: Dr. Nour El-Houda BENALIA

Année 2020/2021
Dr. N.BENALIA Informatique 3 Théorie des graphes

Préambule

Dans le contexte de la programmation linéaire, le terme programmation désigne l'organisation

des calculs et non la réalisation d'un programme informatique. Du point de vue des
applications, l'optimisation linéaire est d'une grande portée. Elle s'applique à des problèmes
très variés qui sont issus de l'économie, de l'ingénierie, de la physique ou encore des modèles
probabilistes. Dans ce cadre, on peut citer par exemple, les problèmes de type gestion de
stock, gestion de production, transport de marchandise, affectation du personnel, systèmes
industriels, réseaux de communication, etc. Pour les modèles de programmation linéaire, on
est souvent amené à maximiser un gain ou minimiser un coût. Ceci explique d'ailleurs
pourquoi la fonction à maximiser s'appelle fonction d'objectif ou économique

Objectifs

L’objectif de cette partie est de voir comment on peut résoudre des problèmes où on veut
maximiser ou minimiser cette fonction dépendant de plusieurs variables qui sont soumises à
plusieurs contraintes. Le nom du domaine qui traite ce genre de problème est la recherche
opérationnelle.

La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme
l'ensemble des méthodes et techniques rationnelles orientées vers la recherche de la meilleure
façon d'opérer des choix en vue d'aboutir au meilleur résultat possible. Quant à l’
optimisation, c’est la recherche du maximum (ou du minimum) d’une fonction ainsi que des
valeurs des variables qui maximisent (ou minimisent) la fonction.

1
Dr. N.BENALIA Informatique 3 Théorie des graphes

CHAPITRE 1

Formulation d’un programme linéaire (PL)

I. Introduction
L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des
problèmes de décision que soit économique, militaire ou autres ont fait de la programmation
linéaire un des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers
travaux (1947) sont celle de George B. Dantzig et ses associés du département des forces de
l’air des Etats Unis d’Amérique.

Les problèmes de programmations linéaires sont généralement liés à des problèmes

d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un
profit ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un
ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces
décisions sont en général le résultat d’un problème mathématique.

II. Les conditions de formulation d’un PL

La programmation linéaire comme étant un modèle admet des hypothèses (des conditions)
que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces
hypothèses sont:

1. Les variables de décision du problème sont positives

2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces
variables, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé
de deux de ces variables. La fonction qui représente le critère de sélection est dite fonction
objectif (ou fonction économique).

3. Les restrictions relatives aux variables de décision (exemple: limitations des ressources)
peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment
l’ensemble des contraintes.

4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue
avec certitude

III. Les étapes de formulation d’un PL:

Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme
linéaire:

1. Identifier les variables du problème à valeur non connues (variable de décision) et les
représenter sous forme symbolique (exp. x1, y1 ).

2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système
d’équations linéaires.

2
Dr. N.BENALIA Informatique 3 Théorie des graphes

3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en

fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à
minimiser.

IV. Présentation Théorique

Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire
dite fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En
langage mathématique, on décrira de tels modèles de la manière suivante :

Soient N variables de décision x1, x2,…, xn, l’hypothèse que les variables de décision sont
positives implique que ≥ 0, ≥ 0, … ,x ≥ 0.

La fonction objectif est une forme linéaire en fonction des variables de décision de type

z=c +c + ⋯ +c

où les coefficients c1,…,cN doivent avoir une valeur bien déterminée (avec certitude) et
peuvent être positifs, négatifs ou nuls. Par exemple le coefficient ci peut représenter un profit
unitaire lié à la production d’une unité supplémentaire du bien xi, ainsi la valeur de z est le
profit total lié à la production des différents biens en quantités égales à ,x , … ,x .

Supposons que ces variables de décision doivent vérifier un système d’équations linéaires
définis par M inégalités

11 +a12 + ⋯ +a ≥
21 +a22 + ⋯ +a ≥
⋮
+a + ⋯ +aMN ≥

où les coefficients a1M,…, aMN et b1,…, bM doivent avoir une valeur bien déterminée (avec
certitude) et peuvent être positifs, négatifs ou nuls. Le paramètre bj représente la quantité de
matière première disponible dont le bien xi utilise une quantité égale à aij xi .

En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :

Max +c + ⋯ +c
. 11 +a12 + ⋯ +a ≥
21 +a22 + ⋯ +a ≥
⋮
+a + ⋯ +aMN ≥
≥ 0, ≥ 0, … ,x ≥ 0

V. Exemples de formulations
Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de
divers domaines sont représentés ou approximés par des modèles de PL. L’utilisation de ces
techniques de modélisation s’est renforcée encore après avoir construit des algorithmes et des
logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision
que de contraintes.

3
Dr. N.BENALIA Informatique 3 Théorie des graphes

La tâche de formulation demande généralement une certaine expertise et connaissance du

problème pour pouvoir relever facilement les différentes composantes du problème et ainsi
donner un programme qui modélise au mieux la situation réelle. Dans ce qui suit, on
présentera quelques exemples de formulation en programme linéaire liés à différents
problèmes de décision:

Exemple 1: Problème d’agriculture

Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et celles
de piments. Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau. Un hectare de
tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un bénéfice net de 100
dinars. Un hectare de piments demande 4 heures de main d’œuvre, 2 m3 d’eau et donne un
bénéfice net de 200 dinars.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui permet pas de
cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources?
Formulation du problème en un PL:
Etape 1: Identification des variables de décision. Les deux activités que l’agriculteur doit
déterminer sont les surfaces à allouer pour la culture de tomates et de piments:

 x1: la surface allouée à la culture des tomates

 x2: la surface allouée à la culture des piments

On vérifie bien que les variables de décision x1 et x2 sont positives: ≥ 0, ≥ 0.

Etape 2: Identification des contraintes. Dans ce problème les contraintes représentent la

disponibilité des facteurs de production:

 Terrain: l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte liée à la

limitation de la surface de terrain est +x ≤ 150

 Eau: la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare de
piments demande 2m3 mais l’agriculteur ne dispose que de 440m3. La contrainte qui
exprime les limitations des ressources en eau est 4 + 2 ≤ 440.

 Main d’œuvre: Les 480 heures de main d’œuvre seront départager (pas nécessairement en
totalité) ente la culture des tomates et celles des piments. Sachant qu’un hectare de
tomates demande une heure de main d’œuvre et un hectare de piments demande 4 heures
de main d’œuvre alors la contrainte représentant les limitations des ressources humaines
est + 4 ≤ 480

 Les limitations du bureau du périmètre irrigué: Ces limitations exigent que l’agriculteur ne
cultive pas plus de 90 hectares de tomates. La contrainte qui représente cette restriction
est ≤ 90.
Etape 3: Identification de la fonction objectif. La fonction objectif consiste à maximiser le
profit apporté par la culture de tomates et de piments. Les contributions respectives 100 et

4
Dr. N.BENALIA Informatique 3 Théorie des graphes

200, des deux variables de décision x1 et x2 sont proportionnelles à leur valeur. La fonction
objectif est donc z=100 + 200 .
Le programme linéaire qui modélise le problème d’agriculture est:
Max 100 + 200
. . +x ≤ 150
4 + 2 ≤ 440
+4 ≤ 480
≤ 90
≥ 0, ≥0

Exemple 2: Problème de médecine

Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir les sujets
atteints d’un rhume. Ces pilules sont fabriquées selon deux formats:

 Petite taille: elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1 grain de codéine.

 Grande taille: elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6 grains de

codéine.
Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate et 24
grains de codéine. Déterminer le nombre de pilules minimales à prescrire au sujet pour qu’il
soit guérit.
Formulation du problème en un PL:
Le problème de médecine présente certaines ressemblances avec le problème de l’agriculture,
dans les deux cas c’est un problème d’allocation de ressources.
Etape 01: Les variables de décision qui représentent des valeurs inconnues par le décideur qui
est dans ce cas le spécialiste en médecine sont:

 x1: le nombre de pilules de petite taille à prescrire.

 x2: le nombre de pilules de grande taille à prescrire.

On vérifie bien que les variables de décision x1 et x2 sont positives: ≥ 0, ≥ 0.

Etape 02: Les contraintes imposées par le problème sur les valeurs possibles de x1 et x2 sont:

 La prescription doit contenir des pilules avec au moins 12 grains d’aspirine. Sachant
qu’une petite pilule contient 2 grains d’aspirine et qu’une grande pilule contient un seul
grain d’aspirine, on obtient la contrainte suivante : 2 +x ≥ 12.

 De la même façon que pour l’aspirine, la prescription du spécialiste en médecine doit

contenir au moins 74 grains de bicarbonate. Ainsi la contrainte suivante doit être
satisfaite: 5 + 8 ≥ 74.

 Finalement la contrainte imposée par le fait que la prescription doit contenir au moins
24 grains de codéine est + 6 ≥ 24.

5
Dr. N.BENALIA Informatique 3 Théorie des graphes

Etape 3: Identification de la fonction objectif. On remarque qu’il y a plusieurs couples de

solutions , qui peuvent satisfaire les contraintes spécifiées à l’étape 2. La prescription
doit contenir le minimum possible de pilules. Donc le critère de sélection de la quantité de
pilules à prescrire est celle qui minimise le nombre total des pilules z=x +x .
Le programme linéaire qui modélise ce problème médical est donc le suivant:
Min +x
. . 2 +x ≥ 12
5 + 8 ≥ 74
+ 6 ≥ 24
≥ 0, ≥ 0
VI. Différentes formes d’un PL

1. La forme canonique
Un programme linéaire (PL) est dit sous forme canonique pure s’il s’écrit:

2. La forme standard
Un programme linéaire (PL) est dit sous forme standard s’il s’´ecrit:

3. La forme mixte
Même fonction objectif que les deux précédentes formes sauf que certaines contraintes sont
des « = » d’autres sont des inégalités «<= »

4. Passage forme standard/canonique

Tout programme linéaire PL peut se mettre sous la forme standard ou canonique.

En effet, il suffit de faire les transformations suivantes:

T1) Min Z= - Max (-Z)

T2) Lorsque une contrainte est sous forme d’une inégalité. Deux cas se présentent:

6
Dr. N.BENALIA Informatique 3 Théorie des graphes

ai1 x1 + …..+ ain xn ≤ bi . On introduit une variable d’écart ei et on obtient:

ai1 x1 + …..+ ain xn + ei = bi

ai1 x1 + …..+ ain xn ≥ bi . On introduit une variable d’écart ei et on obtient:

ai1 x1 + …..+ ain xn - ei = bi

T3) Lorsqu’une contrainte est sous forme d’une égalité:

ai1 x1 + …..+ ain xn = bi

On la transforme en deux inégalités

ai1 x1 + …..+ ain xn ≤ bi

et

ai1 x1 + …..+ ain xn ≥ bi <=> -ai1 x1 + …..- ain xn ≤ -bi

T4) Si un bi est négatif

ai1 x1 + …..+ ain xn = bi avec bi < 0

- ai1 x1 …..- ain xn = - bi et - bi > 0

T5) Si une variable xj est quelconque

On pose xj= x1j – x2j avec x1j ≥ 0 et x2j ≥ 0

Exemple

Soit le PL suivant

Min Z = 2 x1 + x2 – x3 + x4

3 x1 – x2 ≥ 5

x1 + 3 x4 ≤ 8

2 x1 – x3 ≥ 1

Ecrire la forme standard et la forme canonique de ce PL

Forme standard:

Min Z <=> Max (-Z) . On introduit les variables d’écart e1, e2 et e3 aux trois contraintes
respectives et on obtient

Max Z’ = - 2 x1 - x2 + x3 - x4

3 x1 – x2 - e1 = 5

7
Dr. N.BENALIA Informatique 3 Théorie des graphes

x1 +3 x4+ e2 = 8

2 x1 – x3 -e3 = 1

8
Dr. N.BENALIA Informatique 3 Théorie des graphes

CHAPITRE 2

Résolution de Programmes Linéaires:

La méthode graphique
I. Introduction
Après avoir illustré par des exemples, comment un problème pratique peut être modélisé par
un programme linéaire, l’étape qui va suivre sera certainement celle de la résolution de ce
problème mathématique.

Deux façons de résoudre un problème de programmation linéaire:

Méthode graphique

La méthode graphique est l’une des premières méthodes utilisées à ce sujet. Pour résoudre un
problème de programmation linéaire simple ayant seulement deux variables de décisions.
Cela permet de visualiser le principe général de la programmation linéaire. Cette méthode est
beaucoup trop longue et difficile, voire impossible, à visualiser s’il y a plus de deux variables.

Méthode du simplexe

Méthode algorithmique plus rapide pour résoudre les problèmes comportant un grand nombre
de variables. Elle est généralement programmée et calculée à l’ordinateur.

Ceci indique que dans ce chapitre on examinera seulement les programmes linéaires à deux
variables de décision.

II. Système d’axes

Une des conditions de la réussite de notre représentation graphique est le choix d'un système
d’axes. Un mauvais choix peut rendre notre représentation non claire et imprécise.

A cause des contraintes de non-négativité des variables de décision, nous nous intéressons
seulement au cadran positif (voir figure ci-dessus).
Cette région s’appelle la région des solutions possibles du problème.
Prenons l’exemple 2 relatif au problème de médecine. Le programme linéaire est le suivant:

9
Dr. N.BENALIA Informatique 3 Théorie des graphes

Min +x
. . 2 +x ≥ 12
5 + 8 ≥ 74
+ 6 ≥ 24
≥ 0, ≥ 0

Un bon choix se base sur une lecture des différents paramètres du programme linéaire. Dans
notre cas, on ne peut qualifier de bon, le choix de 20 comme unité dans les deux axes.

III. Représentation graphique des contraintes

Parmi les solutions possibles d’un problème, il y a ceux qui vont satisfaire toutes les
contraintes du programme, appelés solutions réalisables, et ceux qui vont satisfaire une partie
ou aucune de ces contraintes, appelés solutions non réalisables.

Une représentation graphique des inégalités (des contraintes) va nous permettre de déterminer
l’ensemble des solutions réalisables.

Revenons à l’exemple 2 du problème de médecine.

Une des contraintes de ce problème est celle relative au grain d’aspirine:

2 +x ≥ 12.

L’ensemble des solutions qui vérifient cette inégalité est le même que celui qui vérifie
2 +x = 12 et 2 +x > 12.

x2

12

6
3

x1
6 12 24

L’ensemble des solutions qui correspond à l’équation est l’ensemble des points de la droite l
définie par = −2 + 12. Cette droite admet une valeur de la pente égale à –2 et intercepte
l’axe des ordonnées en 12 (voir figure ci-dessus).

L’inégalité 2 +x > 12 correspond à un demi-plan limité par la droite = −2 + 12. Or

cette droite divise le plan en deux demi-plans ouverts donc quel est le demi-plan à choisir?

x2

12 1

6
3

x1
6 12 24

10
Dr. N.BENALIA Informatique 3 Théorie des graphes

Pour ce faire, il suffit de prendre un point de l’un des demi-plans (c’est à dire n’appartenant
pas à la droite = −2 + 12) et voir s’il vérifie l’inégalité 2 +x > 12. Par exemple le
point de coordonnées (0,0) ne vérifie pas l’inégalité 2 +x > 12 donc le demi-plan Π1 au-
dessus de la droite est celui recherché (voir figure ci-dessus).

L’espace hachuré représente le demi-plan fermé des solutions qui vérifient la contrainte
2 +x > 12.

Si on fait de même pour les deux autres contraintes du problème (voir figures
ci-dessous), on obtient les deux autres demi-plans Π2 et Π3 relatifs aux solutions vérifiant
respectivement les contraintes 5 + 8 ≥ 74 et + 6 ≥ 24.

2 3
9.25

6
4
3

x1 x1
6 14,8 24 6 12 24

Une solution possible du problème est dite réalisable si et seulement si elle vérifie toutes les
contraintes, c’est à dire si elle appartient aux trois demi-plans relatifs à chaque contrainte du
programme linéaire, en d’autre terme à
Π1 ∩ Π2 Π3 (voir figure).

Définition: Un ensemble E non vide est dit convexe si et seulement si pour tout élément x et y
de E et pour tout
 Un objet géométrique est dit convexe lorsque, chaque fois qu'on y prend deux
pointsA et B, le segment [A, B] qui les joint y est entièrement contenu. Ainsi
un cube plein, un disque ou une boule sont convexes, mais un objet creux ou bosselé
ne l'est pas.
On peut vérifier facilement que chacun des demi-plans Π1, Π2 , Π3 est convexe en vérifiant
que pour toute paire de points P1 et P2, l’ensemble des points qui forment le segment [P1P2]
appartient au demi-plan.

Théorème: L’intersection d’ensembles convexes (non vide) est convexe.

11
Dr. N.BENALIA Informatique 3 Théorie des graphes

Propositions: L’ensemble des solutions réalisables (non vide) est convexe.

IV. Représentation de la fonction objectif

Soit z la valeur de la fonction objectif du problème de médecinez=x +x .

Pour z=0, la fonction objectif est représentée de la manière suivante:

Pour z=6, c’est à dire que le nombre de pilules à prescrire est égale à 6 pilules. La fonction
objectif est représentée comme suit:

Chaque point du segment qui relie les points (6,0) à (0,6) représente des solutions qui
engendrent une prescription avec 6 pilules des deux tailles.
On peut tracer une infinité de droites qui représentent les différentes valeurs de la fonction
objectif, toutes ces droites ont le même coefficient directeur (-1). Par suite elles sont parallèles
entre elles. De plus on peut diminuer la valeur de z indéfiniment dans le sens indiqué dans la
figure ci-dessous.

Le problème est de connaître qu’elle est la droite qui correspond à la valeur minimal de la
fonction objectif?

12
Dr. N.BENALIA Informatique 3 Théorie des graphes

V. Recherche de la solution optimale

a. Résolution graphique
Si nous retraçons l’ensemble des droites parallèles relatives à différentes valeurs de la
fonction objectif sur la figure qui représente l’ensemble des solutions réalisables, on peut
localiser la solution optimale. Elle correspond à la solution réalisable qui intercepte la droite à
la plus petite valeur de z.

Dans notre exemple, la solution optimale est l’intersection des deux contraintes 2 +x ≥ 12
et 5 + 8 ≥ 74. Une évaluation des coordonnées de ce point revient à résoudre le système
linéaire suivant:

Elle correspond d’après le graphique au point (2,8). Donc la prescription optimale est de 2
pilules de petite taille et 8 pilules de grande taille. Le nombre de pilules (la valeur de la
fonction objectif) est égale à 10.

b. Résolution par énumération:

On remarque que la solution optimale du problème de médecine est un point extrême qui se
trouve sur le bord de l’ensemble des solutions. Une telle solution est dite solution réalisable
de base.

On peut admettre le résultat suivant: « Si un programme linéaire admet une solution optimale
alors il existe une solution réalisable de base pour laquelle la fonction objectif atteint la valeur
optimale»

Une méthode de résolution du programme linéaire consiste donc à déterminer les solutions
réalisables de base (les points d’intersection des droites qui forment les contraintes) et à
calculer pour chaque point la valeur de la fonction objectif. La solution du programme linéaire
est la solution à qui on associe la valeur optimale de la fonction objectif.

Dans le problème de

13
Dr. N.BENALIA Informatique 3 Théorie des graphes

médecine, l’ensemble des solutions réalisables de base présente 4 points extrêmes A(0,12),
B(2,8), C(23/11,126/11) et D(24,0). La valeur de la fonction objectif associée respectivement
à A, B, C et D est 12, 10, 149/11 et 24. On vérifie bien que B est la solution optimale du
problème avec une valeur optimale égale à 10.

VI. Exemples
Dans cette section on donne quelques exemples de résolution graphique de problèmes
linéaires relatifs au différents cas possibles :

Problème de maximisation

Max 100 + 200 x (

2)
. . +x ≤ 150 1 (
4)
2

A
4 + 2 ≤ 440 2 B
+ 4 ≤ 480 3 1
10
C
≤ 90 4 (
3)
≥ 0, ≥ 0 Z
=0 3
0
D (
1)

E x
4
0
1

la solution optimale est B(40,110)

Problème avec solution non bornée

Max -2 + 3 x
. . ≤5 1
2

2 −3 ≤6 2 (
2)
≥ 0, ≥ 0

5 x
Z
=0
1

(
1)

On peut augmenter la valeur de la fonction objectif dans la direction des flèches indéfiniment
donc la solution est non bornée

14
Dr. N.BENALIA Informatique 3 Théorie des graphes

Problème impossible

Min 3 +2 x
. . +2 ≤2 1
2

2 +4 ≥8 2
≥ 0, ≥ 0

x
(
2)
1

(
1)

L’espace des solutions réalisables est vide, il est l’intersection des deux zones grises de la
figure ci-dessus

15
Dr. N.BENALIA Informatique 3 Théorie des graphes

VII. Analyse de sensibilité

Une analyse de sensibilité se résume à la recherche des intervalles de variations possibles des
paramètres du programme linéaire sans que la solution optimale ne soit modifiée.

Question: De combien peut-on faire varier la quantité de codéine dans le problème de

médecine sans changer la solution optimale.

Réponse:

x
2

1
2
B

x
6 1
2
1

Z
=10

On peut changer la valeur du second membre de la troisième contrainte jusqu'à ce que la

droite de coefficient directeur –1/6 touche le point optimal (2,8). C’est à dire qu’on peut varier
le second membre de la troisième contrainte de 24 jusqu'à 50 sans changer la solution
optimale.

Question: De combien peut-on faire varier le profit engendré par la culture d’un hectare de
tomates, dans le problème de l'agriculture, sans changer la solution optimale ?

Réponse:

x (
2)
(
4)
2

A
B
1
10
C
(
3)
Z
=0 3
0
D (
1)

E x
4
0
1

Soit  la variation du profit engendré par la culture d’un hectare de tomate. La fonction
objectif est égale à 100+λ + 200

La solution demeure optimale si la pente de la fonction objectif reste toujours comprise entre
la pente de la contrainte (1) et (3). Ceci est équivalent à dire que :

200 1
−1 ≤ − ≤− ⇔ − 50 ≤ ≤ 100
100+λ 4

16
Dr. N.BENALIA Informatique 3 Théorie des graphes

On peut vérifier aussi que si:

. λ< − 50 alors la solution optimale est A

. λ= − 50 alors le problème est à solutions multiples: [AB]

.−50 < λ<100 alors la solution optimale est B

. λ=100 alors le problème est à solutions multiples: [BC]

.100 < λ<300 alors la solution optimale est C

. λ=300 alors le problème est à solutions multiples: [CD]

. λ>300 alors la solution optimale est D

17