Exemples :M thode de simplexe
Exercise 1. On consid re le programme lin aire suivant:
(P1) :
1. R solution graphique:
8
>><
>>:
max (z1 = x1 + 3x2)
contraintes
sous
14
(cid:0)
x1 + x2
(cid:20)
2x1 + 3x2
x2
12
(cid:20)
12
(cid:0)
2x1
(cid:0)
x1; x2
(cid:20)
0
(cid:21)
Figure 1: R solution graphique
2. R solution par le simplexe :
(a) Recherche dune premi re solution de base r alisable : Il est vident pour cet ex-
emple que : x1 = x2 = 0; t1 = 14; t2 = 12 et t3 = 12 est une solution de base
r alisable. La fonction objectif est crit en fonction des variables Hors base
x1; x2: On peut donc construire le premier tableau de simplexe :
ax
B
t1
t3
t2
cB b
0
0
0
1
3
x1 x2
1
3
-1
3
"
14 1
12 -2
12 2
1
0
0
t1
1
0
0
0
0
t2
0
1
0
0
0
t3
0
0
1
0
(b) puisque les coe cients r duits de la hors base sont positifs : ci > 0, alors la
: x2 = x1 = 0; t1 = 14; t2 = 12; et t3 = 12 nest
solution de base B =
pas optimale. On fait entrer la variable x2 dans la base et on fait sortir
t1; t2; t3
g
f
min
bi
ai2
(cid:26)
min
=ai2 > 0
14
1
;
12
3
(cid:26)
(cid:27)
(cid:27)
=
=
bs
ais
b2
ai2
1
la variable la ligne s sort de la base
la variable la ligne 2 sort de la base : t2
051015051015xy
max
B
t1
x2
t3
3
1
x2
x1
5/3
0
-2/3 1
0
4/3
0
cB b
10
0
4
3
16
0
-12 3
"
0
t1
1
0
0
0
0
0
t2
t3
-1/3 0
0
1/3
1
1/3
0
-1
(c) puisqu il existe un coe cient r duit de la hors base qui est positif
( c1 > 0
: t2 = x1 = 0; t1 = 10; x2 = 4; et
), alors la solution de base B =
t3 = 16 nest pas optimale.
f
t1; x2; t3
g
max
B
x1
x2
t3
3
1
x1 x2
cB b
0
1
6
1
1
0
8
3
0
8
0
0
0
-30 0
0
0
0
t2
t3
Publicité
t1
-1/5 0
3/5
0
1/5
2/5
-4/5 3/5
1
-9/5 -2/5 0
(d) Les coe cients r duits de la hors base sont non positifs : cj < 0, alors la solution
de base B =
x1; x2; t3
f
g
: t2 = t1 = 0; x1 = 6; x2 = 8; et t3 = 8 est optimale.
3. Dual de (P1) :
(D1) :
4. R solution du dual (D1)
8
<
:
min (z01 = 14y1 + 12y2 + 12y3)
sous
(cid:0)
contraintes
y1
(cid:0)
x1 + 3y2
y1; y2
2y2 + 2y3
y3
(cid:0)
0
1
(cid:21)
3
(cid:21)
(cid:21)
Lorsque le primal admet une solution optimale &nie, il est facile de d duire le dernier tableau
de simplexe de (D1) partir du dernier tableau du simplexe du primal:
1.
(a) La ligne de la j i me variable de d cision xj en base donne ( un signe pr s) la
colonne de la j i me variable d cart du dual uj hors-base.
(b) La ligne de la j i me variable d cart tj donne ( un signe pr s) la colonne de la j
i me variable de d cision du dual yj hors-base.
(c) la colonne de la j i me variable de d cision xj hors-base donne ( un signe pr s) la
ligne de la j i me variable d cart du dual uj en base
(d) La colonne de la j i me variable d cart tj donne ( un signe pr s) la ligne de la j
i me variable de d cision du dual yj:
(e) Le co t r duit donne z (P ) ( un signe pr s) la colonne b du dual.
(f) La colonne b du primal donne ( un signe pr s) la derni re ligne du dual z (D)
min
B(D) b(D)
y1
y2
9/5
2/5
0
y2
0
1
0
y1
1
0
0
2
u2
y3
4/5
-3/5 1/5
-8
u1
-3/5 -2/5
1/5
-8
-6
Exercise 2. On consid re le programme lin aire suivant:
(P2)
(cid:0)
min (z1 =
x1 + x2)
sous
contraintes
(cid:0)
2x1
x2
(cid:0)
x1
x2
(cid:0)
x1 + x2
x1; x2
2
(cid:21) (cid:0)
2
(cid:20)
5
(cid:20)
0
8
>><
(cid:21)
1. R solution graphique:
>>:
Figure 2: R solution graphique
2. R solution par le simplexe: On rappelle que min(z) =
max(
z)
(cid:0)
(cid:0)
min
B
t1
t2
t3
z
(cid:0)
min
B
t1
x1
t3
-z
cB
0
0
0
cB
0
1
0
1
-1
b x1 x2
1
2 -2
-1
2 1
1
5 1
0 1
-1
"
-1
1
x1 x2
b
-1
0
6
-1
1
2
2
3
0
0
-2 0
"
0
t1
1
0
0
0
0
t1
1
0
0
0
0
0
t3
t2
0
0
0
1
Publicité
1
0
0
0
0
0
t3
t2
0
2
0
1
-1 1
-1 0
1
de co t
2. On remarque dans le dernier tableau
(cid:0)
que le coe cient de la variable hors base x2 est nul, donc on peut obtenir une autre solution
de base optimale. Pour obtenir la nouvelle solution il su t de faire entrer la variable x2 :
Solution optimale: SB = 0
B
B
B
B
@
x1 = 2
x2 = 0
t1 = 6
t2 = 0
t3 = 3
C
C
C
C
A
3
012345012345
min
B
t1
x1
x2
cB b
0
-1
1
15/2 0
1
7/2
0
3/2
0
-2
-1
1
x1 x2
0
0
1
0
0
t1
1
0
0
0
0
0
t3
t2
1/2
3/2
1/2
1/2
-1/2 1/2
-1
0
Remarque : Une autre solution optimale de base : SB0 = 0
B
B
B
B
@
tous les points r alisables par combinaison lin aire convexe de ces deux points sont optimaux.
1
. Par cons quence,
x1 = 7=2
x2 = 3=2
t1 = 15=2
t2 = 0
t3 = 0
C
C
C
C
A
Exercise 3. On consid re le programme lin aire suivant:
(P3)
max (z1 = 5x1 + 7x2)
sous
contraintes
6
(cid:0)
x1 + x2
x1
4
(cid:21)
x2
3
(cid:20)
x1; x2
(cid:21)
0
8
>><
(cid:21)
Obtention dune solution de Base r alisable de d part par la m thode M : on introduit des
variables arti&cielles en nombre su sant le nouveau probl me r soudre est (qui nest pas
forcement quivalent (P3) ) :
>>:
max (z1 = 5x1 + 7x2
contraintes
sous
M v1
(cid:0)
(cid:0)
M v2)
t1 + v1 = 6
t2 + v2 = 4
(cid:0)
(cid:0)
(cid:0)
x1 + x2
x1
x2 + t3 = 3
x1; x2
0
M >>> 0
(cid:21)
(P3)0
1. R solution graphique:
8
>>>><
>>>>:
2. R solution par le simplexe :
(a) (t3; v1; v2) est une base r alisable du probl me (P3)0 , mais la fonction objectif nest
pas crite en fonction des variables Hors base
0
t1
-1
0
0
0
7
t3
x2
0
1
0
0
1
1
7+M -M -M 0
0
t2
0
-1
0
M
(cid:0)
v1
1
0
0
0
M
(cid:0)
v2
0
Publicité
1
0
0
max
B
v1
v2
t3
5
x1
1
1
0
b
cB
-M 6
-M 4
3
0
0+10M 5+2M
"
4
(b)
(c)
(d)
Figure 3: R solution graphique
max
B
(cid:0)
x1
t3
v1
7
5
x1 x2
cB
b
1
0
-M 2
0
1
4
5
3
1
0
0
-20+2M 0 M+7
"
0
0
0
t3
t2
t1
0
1
-1
0
-1
0
0
1
0
-M M+5 0
M
(cid:0)
v1
1
0
0
0
M
(cid:0)
v2
max
B
x2
x1
t3
max
B
x2
x1
t1
5
7
x1 x2
cB b
1
0
2
7
0
1
4
5
0
1
0
0
0
-34 0
5
7
x1 x2
cB b
1
0
3
7
0
1
4
5
0
1
0
0
0
-41 0
0
t1
-1
0
1
7
"
0
t1
0
0
1
0
0
0
t3
t2
1
0
-1 0
-1 1
-2 0
0
0
t3
t2
1
0
-1 0
-1 1
-7
5
M
(cid:0)
v1
M
(cid:0)
v2
M
(cid:0)
v1
M
(cid:0)
v2
Puisque le coe cients r duits de la hors base sont positifs : c4 > 0 , alors la solution de
nest pas optimale on peut am liorer le co t en introduisant t2. mais
base B =
ai4 < 0 donc la solution est in&nie.
x1; x2; t1
f
g
Exercise 4. On consid re le programme lin aire suivant:
5
024681002468
(P4)
(cid:0)
min (z1 =
x1 + x2)
Publicité
sous
contraintes
(cid:0)
2x1
x2
(cid:0)
2x2
x1
(cid:0)
x1 + x2
x1; x2
2
(cid:21) (cid:0)
8
(cid:20) (cid:0)
5
(cid:20)
0
(cid:21)
x1 + x2 + M v)
(cid:0)
contraintes
(cid:0)
2x1 + x2 + t1 = 2
x1 + 2x2
t2 + v = 8
8
>><
>>:
min (z1 =
sous
(P4)0
(cid:0)
(cid:21)
8
>>>><
>>>>:
(cid:0)
(cid:0)
x1 + x2 + t1 = 5
x1; x2
0
M >>> 0
1
x2
1
2
1
cB b
0
2
M 8
5
0
8M 1-M 2M-1
"
-1
x1
-2
-1
1
min
B
t1
v
t3
0
t1
1
0
0
0
0 M
0
v
t3
t2
0
0
0
1
0
-1
0
0
1
0
-M 0
max
B
x2
v
(cid:0)
t3
-1
x1
-2
3
3
cB b
1
2
M 4
3
0
4M+2 3M-1
"
1
-1
x1 x2
cB b
1
0
1
4
0
0
M 1
0
1
1
-1
0
M 0
max
B
x2
v
x1
0
t2
0
-1
0
0 M
0
1
v
t3
t1
x2
0
0
1
1
1
0
-2
0
0
-1
1
0
-2M+1 -M 0
0
0
M
0
0
0
v
t3
t2
t1
0
2/3
0
1/3
1
-1
-1
-1
-1/3 0
11/3 0
-M -M -M 0
Puisque dans la solution optimale de ce probl me, la variable arti&cielle nest pas dans la
hors base (v = 1), le probl me initial na pas de solution r alisable.
6