FSTM

Recherche
Oprationnelle
Introduction la mthode du simplexe

Karam ALLALI

FI GE 2009-2010

K. Allali

RO

FI GE 2009-2010

RO

Mthode de rsolution algbrique : lalgorithme du simplexe

- Pour des modles linaires continus dont les variables sont non
ngatives et dont les contraintes technologiques sont crites sous
forme dquations (i.e. avec un = au lieu dune ingalit du type
< ou > )
- Remarque : dans le cours, on ne montre pas comment appliquer cette
mthode la main . Il sagit plutt de savoir utiliser les rsultats
dans le cadre dune analyse de sensibilit.
Forme gnrale dun programme linaire (PL)

n variables
m contraintes

Max (Min) z = c1x1 + c2x2 + + cnxn

Sous les contraintes :
a11x1 + a12x2 + + a1nxn

b1
=

a21x1 + a22x2 + + a2nxn

b2
=

.
.
.
am1x1 + am2x2 + + amnxn

bm
=

x1 , x2 , , xn > 0
Pour pouvoir utiliser cette mthode lorsque les contraintes comportent des
ingalits, il faut introduire de nouvelles variables non ngatives. Ces
nouvelles variables permettront de transformer le modle linaire en un
modle quivalent o toutes les contraintes technologiques sont de type
= .

K. Allali

FI GE 2009-2010

RO

Transformation dun modle (PL) en un modle (PL=)

Variable dcart :

Pour transformer une contrainte du type < en

une contrainte du type = .
Quantit quil faut ajouter au cot gauche de la
contrainte pour atteindre lgalit.

Variable dexcdent : Pour transformer une contrainte du type > en

une contrainte du type = .
Quantit quil faut soustraire au cot gauche de la
contrainte pour atteindre lgalit.
Exemples :
Contrainte1 :

a11x1 + a12x2

<

b1

Introduction dune nouvelle variable non ngative e1 :

Contrainte 1 : a11x1+ a12x2 + e1 = b1
e1 = b1 (a11x1+a12x2)
(variable dcart)

Contrainte2 :

a21x1 + a22x2

>

b2

Introduction dune nouvelle variable non ngative e2 :

Contrainte 2 : a21x1 + a22x2 e2 = b2
e2 = a21x1 + a22x2 - b2
(variable dexcdent)

K. Allali

FI GE 2009-2010

RO

Programme linaire standard (PLS)

(Toutes les contraintes technologiques sont du type <)
1. Transformation du modle (PLS) en modle (PLS=) en ajoutant une
variable dcart dans chaque contrainte technologique.
2. Obtenir une solution de base admissible initiale.
La plus simple : poser x1 = x2 = .=xn = 0 (correspond au sommet 0)
Ainsi :
(x1 ; x2 ; ; xn ; e1 ; e2 ; . ; em) = (0 ; 0 ; ; 0 ; b1 ; b2 ; ; bm)
Cette solution ne sera pas probablement pas optimale. On le vrifie
en examinant la contribution marginale de chaque variable hors base
la fonction objectif Z (cots marginaux : cJ - zJ).
- Pour un problme de maximisation, la solution de base est
optimale si tous les cots marginaux sont < 0.
- Pour un problme de minimisation, la solution de base est
optimale si tous les cots marginaux sont > 0.

3. Modifier la solution initiale de faon se rapprocher de loptimum

(augmenter ou diminuer Z selon quon veut maximiser ou minimiser).
Lalgorithme du simplexe est un procd par itrations. Chaque
itration correspond au passage dun sommet un autre sommet qui
lui est adjacent.

K. Allali

FI GE 2009-2010

RO

Exemple Fonderie Rivire-bleue

Variables de dcision :

Objectif :

x1 = quantit de tuyauterie traite (en tonnes)

x2 = quantit de gueuse traite (en tonnes)

Maximiser le profit
Max z = 1000x1 + 1200x2

Sous les contraintes :

(1) 10x1 + 5x2

<

200

(barbage)

(2) 2x1 + 3x2

<

60

(peinture)

(3) x1

<

34

(demande tuyauterie)

(4) x2

<

14

(demande gueuses)

x1 , x2 > 0

(non ngativit)

Notez quil sagit bien dun programme linaire standard car toutes les contraintes
technologiques sont du type < .

Rsolution graphique :
fonderie bleue
(1)
45

(3)

35

x2

25
(2)

15

(4)

-4

16

26

36

-5

x1

K. Allali

FI GE 2009-2010

RO

Rsolution algbrique :

(selon mthode du simplexe)

1. Transformation du modle (PLS) en (PLS=)

Max z = 1000x1 + 1200x2
Sous les contraintes :
(1) 10x1 + 5x2 + e1
(2) 2x1 + 3x2
(3)

+ e2

x1

+ e3

(4)

x2

+ e4

200

60

34

14

x1 , x2 , e1 , e2 , e3 , e4 > 0
(Interprtation concrte des variables dcart dans le contexte.)
2. Dterminer une solution de base admissible initiale et construire le
tableau initial:
Poser x1 = 0 et x2 = 0 e1 = 200 ; e2 = 60 ; e3 = 34 ; e4 = 14
Tableau initial du simplexe :
Tableau no. 0

(correspond au sommet (0,0))

1000

BASE
Coeff Variable

e1
e2
e3
e4

0
0
0
0
zJ

1200

0
valeur

x1

x2

e1

e2

e3

e4

10
2
1
0

5
3
0
1

1
0
0
0

0
1
0
0

0
0
1
0

0
0
0
1

0
0

Cot marginal

cJ - zJ

K. Allali

200
60
34
14

1000

1200

FI GE 2009-2010

RO

3. Dterminer sil sagit dune solution optimale :

La solution de base admissible initiale nest pas optimale car z = 0.
On peut aussi constater quil existe des cots marginaux cJ zJ
positifs.
Par exemple :
- si on augmente x1
variables fixes, cela
de 1000 units.
- si on augmente x2
variables fixes, cela
de 1200 units.

dune unit et quon laisse les autres

se traduira par une augmentation de z
dune unit et quon laisse les autres
se traduira par une augmentation de z

Nous nentrons pas dans les dtails de calcul de la mthode du

simplexe dans le cours. Selon cette mthode, une nouvelle variable
doit remplacer une des anciennes variables de la base, chaque
itration. Le tableau du simplexe sera recalcul chaque tape. Le
processus continuera jusqu lobtention dune solution optimale. Tel
que mentionn, chaque itration correspond au passage dun sommet
de la rgion admissible un autre sommet qui lui est adjacent.
Les logiciels spcialiss en programmation linaire sont programms
pour effectuer tous les calculs intermdiaires. La solution sera donne
dans le tableau final du simplexe.

K. Allali

FI GE 2009-2010

RO

Voici, titre indicatif, la squence des tableaux correspondant chaque

itration pour lexemple Fonderie Rivire-Bleue:

Seuls le tableau initial et le tableau final seront tudis dans le cadre du

cours.

K. Allali

FI GE 2009-2010

RO

Reprenons le tableau final : correspond au sommet C : (15 ; 10)

1000 1200
0
0
0
0
BASE
Valeur
Coeff Variable
x1
x2
e1
e2
e3
e4
0
1000
0
1200

e4
x1
e3
x2

0
1
0
0

0
0
0
1

0,10
0,15
-0,15
-0,10

-0,5
-0,25
0,25
0,5

0
0
1
0

1
0
0
0

zJ

1000

1200

30

350

cJ - zJ

-30

-350

4
15
19
10

27000

Solution : (15 ; 10 ; 0 ; 0 ; 19 ; 4)
z = 27000
Les cots marginaux des variables hors base e1 et e2 sont ngatifs. Toute
augmentation de ces variables rsulterait en une diminution de Z. La solution est
donc optimale.
Plan optimal de production:
Profit correspondant :
Contraintes :
(1) e1 = 0
(2) e2 = 0
(3) e3 = 19
(4) e4 = 4

K. Allali

15 tonnes de tuyauterie
10 tonnes de gueuses
27000$

Latelier dbarbage est utilis pleine capacit.

Latelier de peinture est utilis pleine capacit.
Il manque 19 tonnes de tuyauterie pour satisfaire la
demande maximale.
Il manque 4 tonnes de gueuses pour satisfaire la
demande maximale.

10

FI GE 2009-2010

RO

Analyse post-optimale : Quadvient-il de la solution optimale si on

modifie la valeur des coefficients de la fonction objectif ou des contraintes?
Revenons lexemple Fonderie Rivire-Bleue et essayons de voir
graphiquement ce qui se passe lorsquon modifie les coefficients.
Max z = 1000x1 + 1200x2
sc. (1) 10x1 + 5x2
<

200

(barbage)

(2) 2x1 + 3x2

<

60

(peinture)

(3) x1

<

34

(demande tuyauterie)

(4) x2

<

14

(demande gueuses)

x1 , x2 > 0

(non ngativit)

fonderie bleue
(1)
45

(3)

35

x2

25
(2)

15

(4)

-4

16

26

36

-5

x1

K. Allali

11

FI GE 2009-2010

RO

Mthode algbrique :
Modification du coefficient c1 : c1 = 1000+
BASE

1200

0
valeur

Coeff

Var

x1

x2

e1

e2

e3

e4

e4

0,10

-0,5

x1

0,15

-0,25

15

e3

-0,15

0,25

19

1200

x2

-0,10

0,5

10

zJ

1000

1200

30

350

cJ - zJ

-30

-350

27000

zJ
cJ - zJ

K. Allali

12

FI GE 2009-2010

RO

Modification du coefficient c2 : c2 = 1200+

BASE

1000

0
valeur

Coeff

Var

x1

x2

e1

e2

e3

e4

e4

0,10

-0,5

1000

x1

0,15

-0,25

15

e3

-0,15

0,25

19

x2

-0,10

0,5

10

zJ

1000

1200

30

350

cJ - zJ

-30

-350

27000

zJ
cJ - zJ

K. Allali

13

FI GE 2009-2010

RO

Modification du coefficient b1 : b1 = 200 +

Contrainte de forme < et e1 hors base.
BASE

1000 1200
x1
x2

0
e1

0
e2

0
e3

0
e4

valeur

0,10

-0,5

0,15

-0,25

15

e3

-0,15

0,25

19

x2

-0,10

0,5

10

30

350

-30

-350

Coeff

Var

e4

1000

x1

0
1200
zJ

cJ - zJ

K. Allali

1000 1200
0

27000

14

FI GE 2009-2010

RO

Modification du coefficient b4 : b4 = 14 +
Contrainte < et e4 dans la base.
BASE
Var
Coeff

1000
x1

1200
x2

0
e1

0
e2

0
e3

0
e4

valeur

e4

0,10

-0,5

1000

x1

0,15

-0,25

15

e3

-0,15

0,25

19

1200

x2

-0,10

0,5

10

zJ

1000

1200

30

350

cJ - zJ

-30

-350

K. Allali

27000

15

FI GE 2009-2010

CAS GNRAL :

RO

Effet dune modification dun coefficient sur le

tableau final du simplexe.

1. Modification dun coefficient cj dans la fonction objectif z.

a) Modification du cj dune variable originale hors base :
- Dans la ligne suprieure du tableau final, remplacer le
coefficient cj par cj = cj + .
- La modification apporte au tableau naffectera quune seule
autre entre, celle du cot marginal de xj. Calculer ce cot
marginal cj zj.
- Sil sagit dun problme de maximisation, la solution admissible
de base restera optimale si cj zj < 0.
- Sil sagit dun problme de minimisation, la solution admissible
de base restera optimale si cj zj > 0.

(remarque : si le cot marginal dune variable hors base

est nul, il existe une infinit de solutions)
b) Modification du cj dune variable originale de base :
- Dans la ligne suprieure du tableau final et dans la colonne des
coefficients des variables de base du tableau final, remplacer le
coefficient cj par cj = cj + .
- La modification apporte au tableau affectera tous les cots
marginaux des variables hors base. Calculer les nouveaux zj et
les nouveaux cots marginaux cj zj.
- Sil sagit dun problme de maximisation, la solution admissible
de base restera optimale si cj zj < 0.
- Sil sagit dun problme de minimisation, la solution admissible
de base restera optimale si cj zj > 0.

K. Allali

16

FI GE 2009-2010

RO

2. Modification du coefficient bi dune contrainte

a) Contrainte de signe < : bi = bi +
Variable ei hors base :
Dans le tableau final, ajouter une colonne associe droite
de la colonne Valeur . Les entres de cette colonne sont
identiques celles de ei.
Les modifications apportes naffectent pas les cots
marginaux. Toutefois, les valeurs de certaines variables de
bases pourraient changer.
Dduire les quations dajustement partir des lignes du
tableau modifi et recalculer la valeur des variables de base
tout en sassurant de la non ngativit de ces variables (bi doit
rester dans un certain intervalle de variation. En dehors de cet
intervalle, il faudrait utiliser un nouveau tableau optimal).
Variable ei dans la base :
Mme principe sauf quil ny aura quune seule quation
dajustement.
Si bi demeure dans son intervalle de variation, la base optimale
et sa solution restent inchanges.
b) Contrainte de signe > : attention : bi = bi -
On a recours au signe - de faon ce que les entres de la
colonne associe dans le tableau final demeurent identiques aux
entres de la colonne ei.
Pour le reste : mmes indications que les cas prcdents.

K. Allali

17

FI GE 2009-2010

RO

Exercices
S1)

Ecrivez le problme PL suivant sous forme standard avec des M.d.D. non
ngatifs:

Max z = 2x1 + 3 x2 + 5 x3
x1 + x 2 x 3 5

6x1 + 7 x 2 9 x 3 4
s. c. x1 + x 2 + 4 x 3 = 10

x1 , x 2 0

x3 sans restriction

(1)
( 2)
(3)

Formulez son dual.

S2)

Considrons lensemble de contraintes suivant:

x1 + 7 x2 + 3x3 + 7 x4 46
3 x1 - x2 + x3 + 2 x4 8
2 x1 + 3 x2 - x3 + x4 10
Rsolvez par la mthode du simplexe le problme obtenu lorsque la fonction
objectif est donne par:
a)
b)
c)
d)
e)

S3)

max z
max z
max z
min z
min z

=
=
=
=
=

2x1
- 2x1
3x1
5x1
3x1

+ x2
+ 6x2
- x2
- 4x2
+ 6x2

- 3x3
+ 3x3
+ 3x3
+ 6x3
- 2x3

+ 5x4
- 2x4
+ 4x4
+ 8x4
+4x4

Rsolvez le problme suivant par la mthode du simplexe

max z = 5x1 + 4x2 + 3x3
s.c.

K. Allali

2 x1 + 3 x2 + x3 5
4 x1 + x2 + 2 x3 11
3 x1 + 4 x2 + 2 x3 8
x1, x2, x3 0

18

FI GE 2009-2010

S4)

RO

Rsolvez le problme suivant par simple inspection, puis par la mthode du

simplexe
max z = 5 x1 - 6 x2 + 3 x3 - 5 x4 + 12 x5
s.c.

x1 + 3x 2 + 5x 3 + 6x 4 + 3x5 90

xj 0

S5)

Rsolvez le problme suivant par la mthode du simplexe :

On doit organiser un pont arien 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 dun
avion du type A cote 800.000 F; la location dun avion du type B cote 200.000
F.

S6)

Les dictionnaires ci-dessous ont t obtenus aprs excution de quelques

itrations de la mthode du simplexe sur diffrents problmes. Quelles
conclusions pouvez-vous tirer sur base de linformation contenue dans ces
dictionnaires?
Les conclusions possibles sont par exemple:
. la solution courante est optimale, et vaut ...;
. le problme est non born parce que ...;
. le problme est non ralisable parce que ...;
. la solution courante nest pas optimale; dans ce cas, calculez la solution
optimale.

a)

min z
z x1
5x5
= 12

3x1 + x 2
+ 5x 4
=3

s. c.
x1
+ x 3 + x 4 4 x5
=6
4x
x5 + x 6 = 4
1

x1 , x 2 , x 3 , x 4 , x5 , x 6 0

K. Allali

19

FI GE 2009-2010

b)

RO

max z
z + x1

3x1 + x 2

s. c.
x1
+ x3
4x
1

x1 , x 2 , x 3 , x 4 ,

c)

x 4 2 x5

= 20

5x 4

=3

+ 2 x 4 x5

=6

2 x5 + x 6 = 4
x5 , x 6

max z
z
5x 2
+ 3x5 = 12

2 x2 + x3
2 x5 = 4

s.c. x1
x2
3x5 = 2

x2
+ x 4 x5 = 3

x1 , x 2 , x 3 , x 4 , x5 0

K. Allali

20

FI GE 2009-2010

RO

Dualit & Sensibilit

DS1) Suite de lexercice S6a).
Quel est le cot rduit de chacune des variables du problme?

DS2) Suite de lexercice S3).

a) Si le coefficient de la variable x2 dans la fonction objectif augmentait de 2
units, quel serait leffet produit sur la solution optimale et la valeur optimale du
problme? Et si cette augmentation tait de 4 units?
b) Quel est le cot rduit de chacune des variables du problme?
c) Quel est le prix dual de chacune des contraintes dingalit du problme?

DS3) Considrons le programme linaire suivant, exprim sous forme standard:

min z = 2x1 + x2

3x1 + x 2 x 3
=3
4 x + 3x
x4
=6
1
2
s.c.
+ x5 = 3
x1 + 2 x 2
x1 , x 2 , x 3 , x 4 , x5 0

a) Calculer le dictionnaire associ la base B dfinie par les variables de base

x1, x2, x5 .
3 / 5 1 / 5 0

B = 4 / 5 3 / 5 0

1 1
1
1

b) La solution de base associe B est-elle ralisable et optimale?

DS4) Soit le problme (P):

max z = 2x1 + 4x2 + 4x3 - 3x4

K. Allali

21

FI GE 2009-2010

RO

x1 + x 2 + x 3

s. c. x1 + 4 x 2
+ x4
x ,x , x , x
1 2 3 4 0

=4
=8

La base optimale de (P) est

1 1
B=

4 0
et son inverse

0 1 / 4
B1 =

1 1 / 4

a)

Formulez le problme dual de (P).

b)
Sur base des informations fournies (et donc, sans utiliser la mthode du
simplexe ni la mthode graphique), calculez la solution optimale de (P) et celle de
son dual. Expliquez la mthode que vous utilisez.
c)

Si la fonction objectif de (P) est remplace par

max z = 3x1 + 4x2 + 4x3 - 3x4 ,
la base B donne ci-dessus reste-t-elle optimale? Justifiez votre rponse.

DS5) Soit le problme suivant (P):

max z = 100x1 + 50x2 + 25 x3
5x1 + x 2

x1 + 2 x 2
s. c. x1 + x 2

x + x2
1
x, s 0

x3

x3

x3

+ 5x 3

+ s1

= 25
+

s2
+ s3
+ s4

(1)

= 25

( 2)

= 10

(3)

= 50

( 4)

La base optimale de (P) est

K. Allali

22

FI GE 2009-2010

5
1
B=
1

RO

1
2
1
1

0
1
0
0

0
0

1 1
avec B1 =
4 1

0 1
0 5
4 9
0 4

0
0

a) Ecrivez le dual de (P)

b) Quelle est la solution optimale du programme (P) et celle de son dual?
c) Dans quel intervalle peut varier le membre de droite de la contrainte (2) sans
affecter loptimalit de B ?

DS6) Soit le problme de programmation linaire

max z = 60x1 + 30x2 + 20x3

8 x1 + 6 x 2 +
x3
4 x
+ 2 x 2 + 1,5x 3
1
s. c.
2 x1 + 1,5x 2 + 0,5x 3
x1 , x 2 , x 3 0

48
20
8

(1)
(2 )
(3)

La rsolution de ce problme par la mthode du simplexe permet de calculer la

base optimale
8 1 1

B = 4 1,5 0

2 0,5 0

0 0,5 1,5

et son inverse B1 = 0 2
4

8
1 2

a) Calculez la solution optimale et la valeur optimale du problme.

b) Calculez et interprtez le prix dual de la contrainte (2).

DS7) Soit le problme de programmation linaire

max z = 30 x1 + 20x2

K. Allali

23

FI GE 2009-2010

5x1 + 4 x 2
x
1
s. c.
x2

x1 , x 2 , 0

RO

400
60
75

(1)
(2 )
(3)

a) Rsolvez le problme graphiquement.

b) Sur base de a), dterminez la base optimale B.
c) Pourrait-on dduire les prix duaux sur base de cette information?
DS8) Soit le problme de programmation linaire (P):
min z = 500x1 + 500x2 + 500x3 + 300x4 + 425x5

x1 + x 2
+ x4

2x2 + 4x3 + x4
s. c.
x1 , x 2 , x 3 , x 4 , x 5 0

150
+ 3x5 80

A loptimum de (P), on a x1 = x2 = x3 = x5 = 0
a) Trouvez la solution optimale et la matrice de base optimale pour (P).
b) A partir de la matrice de base, calculez la valeur optimale des variables
duales.
c) Ecrivez le problme dual de (P).

DS9) Soit le problme de programmation linaire

max z = 4x1 + 5x2 + 6x3
3x1 + 4 x 2 + 5x 3

s. c. x1 , x 2 , x 3 0

11

a) Formulez le dual et rsolvez-le (par inspection)

b) Utilisez a) et le thorme de dualit forte pour rsoudre le primal.

DS10) Soit le problme de programmation linaire:

K. Allali

24

FI GE 2009-2010

RO

min z = 2x1 + 3x2

2 x1 + 3x 2 30

x1 + 2 x 2 10
s. c. x1 x 2 0
x, x , 0
2
1

K. Allali

25

FI GE 2009-2010

RO

Son dual scrit

max w = 30y1 + 10y2
2 y1 +
y2 + y 3 2

3y1 + 2 y2 y3 3
s. c. y1
0
y , y 0
3
2

Dterminez si les solutions suivantes sont ralisables et optimales:

a)
b)
c)

( x1 = 10, x2 = 10/3; y1 = 0, y2 = 1, y3 = 1)
(x1 = 20, x2 = 10; y1 = 1, y2 = 4, y3 = 0)
(x1 = 10/3, x2 = 10/3; y1 = 0, y2 = 5/3, y3 = 1/3)

DS11) Considrons le programme linaire suivant

max z = 5x1 + 2x2 + 3x3

x1 + 5x 2 + 2 x 3 = 30
x
5x 2 6x 3 40
1
s. c.
x1 , x 2 , x 3 0

La solution optimale est donne par le dictionnaire final

max z
+
z

x1 +

s.c.

x, s

23 x2

+ 7 x3

= 150

5 x2

+ 2 x3

= 30

10 x2

8 x3

+ s2

= 10

a) Ecrivez le problme dual associ.

b) Dterminez la matrice de base optimale B. Dduisez-en la solution optimale
du dual.
c) Dans quel intervalle peut varier c1 (idem c2, c3) sans affecter loptimalit de la
solution?

K. Allali

26

FI GE 2009-2010

RO

d) Dans quel intervalle peut varier b1 (idem b2) sans affecter loptimalit de la
base B?
e) Dterminez les prix duaux.

DS12) Considrons le problme de lexercice DS11.

a) Supposons que le M. de D. des contraintes devienne (30 + , 40 - ), o est
un paramtre non ngatif. Dterminez les valeurs de pour lesquelles la
base B reste optimale.
b) Pour chacune des fonctions objectif suivantes, trouvez la nouvelle solution
optimale en utilisant la procdure danalyse de sensibilit.
i) max z = 12x1 + 5x2 + 2x3
ii) min z = 2x2 - 5x3
DS13) Voici la formulation dun petit problme de transport impliquant 3 entrepts et 2
clients:
min z = 3x11 + 2x12 + 4x21 + x22 + 2x31 + 3x32

x 11 + x 12 60
x + x 50
22
21
x 31 + x 32 50
s. c
x 11 + x 21 + x 31 = 90
x 12 + x 22 + x 32 = 60

x 11 , x 121 , x 21 , x 22 , x 31 , x 32 0
(remarquez que le problme est non quilibr).
Ce problme a t mis sous forme standard en introduisant des variables dcart
s1 , s2 et s3 dans les trois premires contraintes, puis rsolu par un logiciel
utilisant la mthode du simplexe. Voici quelques informations sur la solution
optimale:

les variables en base loptimum sont x11, x12, x22, x31 et s1;
le cot rduit de x21 et celui de x32 sont gaux 2;
les prix duaux des contraintes sont donns par (y1, y2, y3, y4, y5) = (0, -1, -1,
3, 2).

a) Mettez le problme sous forme standard (comme suggr ci-dessus) et

formulez son problme dual.
b) Utilisez linformation donne plus haut pour calculer la solution optimale du
problme et le cot de transport correspondant.

K. Allali

27

FI GE 2009-2010

RO

c) Si le cot unitaire de transport entre lentrept 2 et le client 1 diminuait de 1

unit (passant ainsi de 4 3), quelle serait lincidence de ce changement sur
la solution optimale et la valeur optimale calcules prcdemment?
d) Le gestionnaire du troisime entrept saperoit quil a commis une erreur en
valuant ses stocks: il possde en fait 55 units en stock. En supposant que
la base optimale ne soit pas affecte, quel sera leffet de cette correction sur
le cot de transport optimal?

K. Allali

28

FI GE 2009-2010

RO

Solutions des exercices

S2)
S3)
S4)
S5)
S6)

d) Solution optimale: (z*, x*, s*)=(-40/3, 0, 10/3, 0, 0, 68/3, 34/3, 0).

Solution optimale: (z*, x*, s*)=(13, 2, 0, 1, 0, 1, 0).
Solution optimale: (z*, x*, s*)=(450, 90, 0, 0, 0, 0, 0).
Solution optimale: (z*, x*, s*)=(4600, 7/2, 9, 0, 22, 17/2, 0).
a) Il existe une infinit de solutions optimales; b) Dictionnaire non
optimal; c) Dictionnaire non optimal.

DS1) Cot rduit de x1=1, de x5=5; les autres sont nuls.

DS2) a) i)Pas de changement; ii) x2 peut entrer en base. Nouvelle solution optimale:

(z*, x*, s*)=(14, 0, 1, 2, 0, 6, 0); b) Cot rduit de x2=3; c) Prix duaux=1, 0, 1 resp.
DS3) b) Oui.
DS4) b) x*=(0, 2, 2, 0), y*=(4, 0); c) Oui.
DS5) b) (x*, s*)=(15/4, 25/4, 0, 0, 35/4, 0, 40), y*=(25/2, 0, 75/2, 0); c) [65/4, +[.
DS6) a) (z*, x*)=(280, 2, 0, 8, 24, 0, 0); b) y2*=10.
DS7) b) xB=(x1, x2, s3); c) y*=(5, 5, 0).
DS8) a) x4*=150, s1*=0, s2*=0; b) y*=(300,0).
DS9) a) y*=4/3; b) x1*=11/3.
DS10) a) Ralisables; b) Pas ralisables; c) Ralisables et optimales.
DS11) b) y*=(5, 0); c) c1[3/2, +[, c2]-, 25], c3]-,10]; d) b1[0, 40], b2[30, +[.
DS12) a) [0,5]; b) i) La solution optimale est inchange; ii) Faire entrer x3 en base.
DS13) b) z*=290, xB*=(40, 10, 50, 50, 10); c) Pas de changement; d) Valeur optimale:
285.

K. Allali

29