Exercice 1.2.1.
R(cid:19)esoudre par le simplexe
Max x1 + 2x2
sous 8
><
>:
(cid:0)3x1 + 2x2 (cid:20) 2
(cid:0)x1 + 2x2 (cid:20) 4
x1 + x2 (cid:20) 5
xi (cid:21) 0 i = 1; 2
1) Forme standard
Min z = (cid:0)(x1 + 2x2)
(cid:0)3x1 + 2x2 + x3
sous 8
><
(cid:0)x1 + 2x2
x1 + x2
+ x4
= 2
= 4
+ x5 = 5
>:
xi (cid:21) 0 i = 1; : : : ; 5
1
2) Tableau du simplexe (forme canonique !)
x1 x2 x3 x4 x5
0
0
-1 -2
0
1
2
-3
0
0
2
-1
1
0
1
1
0
0
1
0
b
z
-1 0
0 2
0 4
0 5
3) Si SBR, alors phase II (sinon phase I)
Ici, (cid:19)evident
x1 = x2 = 0
x3 = 2 (cid:21) 0
x4 = 4 (cid:21) 0
x5 = 5 (cid:21) 0
8
>>><
>>>:
4) sol pas optimale car 9 cj (cid:20) 0
5) Changement de base :
c2 + n(cid:19)egatif que c1 ! x2 rentre dans la base.
? Variable xs sortant de la base
t = arg minif bi
2; 4
gjai2(cid:21)0 = minf2
ai2
) t = 1
2; 5
1g = 2
2
xs tq B(cid:0)1as = et = 0
B
@
! s = 3
1
C
A
2
1
0
0
6) Tableau canonique de la nouvelle base
l0
2 = l2=2
l0
1 = l1 + l2
l0
3 = l3 (cid:0) l2
l0
4 = l4 (cid:0) l2=2
x1 x2 x3 x4 x5
0
1
-4
1
-3
0
2
2
0
-1
2
5
-1
1
2
2
0
0
1
0
0
1
0
0
b
z
-1 2
0 1
0 2
0 4
7) seul c1 < 0 ! x1 entre en base
minf2
2; 4
5=2g = 2
2 ! x4 sort de la base
l00
3 = l0
l00
1 = l0
l00
2 = l0
l00
4 = l0
3=2
1 + 2l0
3
2 + 3l0
3=4
4 (cid:0) 5l0
3=4
3
x1 x2 x3 x4 x5
0
-1
0
-1
0
0
4
-1
0
1
2
3
1
0
4
2
3
4
1
2
-5
4
0
1
0
0
b
z
-1 6
5
0
2
0 1
3
0
2
8) seul c3 < 0 ! x3 entre en base
minf
3=2
3=4g ! x5 sort de la base
4 = 4l00
l000
1 = l00
l000
2 = l00
l000
3 = l00
l000
4=3
1 + 4l00
2 + l00
4=3
3 + 2l00
4=3
4=3
x1 x2 x3 x4 x5
4
0
0
Publicité
3
1
0
0
3
2
0
1
3
4
1
0
3
1
3
1
3
-1
3
-5
3
0
1
0
0
b
z
-1 8
0 3
0 2
0 2
(cid:15) sol : x1 = 2; x2 = 3; x3 = 2; x4 = x5 = 0
(cid:15) co^ut = -8
(cid:15) sol optimale car tous les cj (cid:21) 0
4
Exercice 1.2.2.
x1 x2 x3 x4
0
0
0
0
0
1
1
0
0
1
0
0
6
5
4
7
b
z
-1 31
7
0
0
5
0 12
Optimum, x1 = 5; x2 = 0; x3 = 7; x4 = 12,
co^ut=-31
x1 x2 x3 x4 x5
0
0
0
0
0
1
1
0
0
0
1
0
-1
-2
0
-1
4
6
6
2
b
z
-1 0
0 8
0 1
0 1
Optimum non born(cid:19)e (! (cid:0)1)
x1 x2 x3
0
0
-4
0
1
1
1
0
2
b
z
-1 -2
0 -1
2
0
Impossible !
5
Exercice 1.2.5.
Max x1
x1 (cid:0) x2 (cid:20) 1
2x1 (cid:0) x2 (cid:20) 2
x1 + x2 (cid:20) 7
x1 (cid:21) 0
x2 (cid:21) 0
sous
8
>>>>>><
>>>>>>:
R(cid:19)esoudre par le simplexe. Comparer avec les
solutions obtenues graphiquement.
1) Forme standard
Min z = (cid:0)x1
x1 (cid:0) x2 +x3
2x1 (cid:0) x2
x1 + x2
xi (cid:21) 0
i = 1; : : : ; 5
+x4
= 1
= 2
+x5 = 7
sous 8
>>><
>>>:
6
2) Tableau du simplexe
x1 x2 x3 x4 x5
0
0
-1
0
1
1
0
0
2
1
0
1
0
-1
-1
1
0
0
1
0
b
z
-1 0
0 1
0 2
0 7
SBR (VHB : x1 = x2 = 0 ; VB : x3 = 1; x4 =
2; x5 = 7)
3) Phase II
x1 entre dans la base
minf1
2; 7
1; 2
Choix : x3 sort
1g = 1 ! x3 ou x4 sort de la base.
l1 ! l1 + l2
l3 ! l3 (cid:0) 2l2
l4 ! l4 (cid:0) l2
x1 x2 x3 x4 x5
0
1
0
0
1
1
0
-2
0
1
-1
0
-1
-1
1
2
0
0
1
0
z
b
-1 1
0 1
0 0
0 6
Publicité
7
x2 entre dans la base
minf0
1; 6
2g = 0 ! x4 sort de la base.
l1 ! l1 + l3
l2 ! l2 + l3
l4 ! l4 (cid:0) 2l3
x1 x2 x3 x4 x5
0
-1
0
0
-1
1
0
-2
0
1
3
0
1
1
1
-2
0
0
1
0
z
b
-1 1
0 1
0 0
0 6
x3 entre dans la base, x5 en sort.
l1 ! l1 + l4=3
l2 ! l2 + l4=3
l3 ! l3 + 2l4=3
l4 ! l4=3
x1 x2 x3
0
0
0
0
0
1
0
1
0
1
0
0
z
b
x4
x5
1/3 1/3 -1 3
1/3 1/3 0 3
-1/3 2/3 0 4
-2/3 1/3 0 2
8
Optimum :
x1 = 3 ; x2 = 4 ; x3 = 2 ; x4 = x5 = 0 ; z = (cid:0)3
Remarque : si on avait fait sortir x4 au d(cid:19)ebut
l1 ! l1 + l3=2
l2 ! l2 (cid:0) l3=2
l3 ! l3=2
l4 ! l4 (cid:0) l3=2
x1
0
0
1
0
x2
-1/2
-1/2
-1/2
3/2
x3
0
1
0
0
x4
1/2
-1/2
1/2
-1/2
x5
0
0
0
1
b
z
-1 1
0
0
1
0
6
0
l1 ! l1 + l4=3
l2 ! l2 + l4=3
l3 ! l3 + l4=3
l4 ! 2=3l4
x1
0
0
1
0
x2
0
0
0
1
x3
0
1
0
0
z
x4
1/3
-2/3 1/3
1/3
1/3
-1/3 2/3
b
x5
1/3 -1 3
2
3
4
0
0
0
Solution optimale identique mais avec une (cid:19)etape de
moins.
9
Exercice 1.2.3.
R(cid:19)esoudre par la m(cid:19)ethode du simplexe
Min x1 (cid:0) x2 + x3
(cid:21) 4
x1 + 3x2
x1 + x2 (cid:0) x3 (cid:20) 10
xi (cid:21) 0
i = 1; : : : ; 3
sous 8
><
1) Forme standard
>:
Min x1 (cid:0) x2 + x3
sous 8
><
x1 + 3x2
x1 + x2 (cid:0) x3
xi (cid:21) 0
i = 1; : : : ; 5
(cid:0)x4
= 4
+x5 = 10
>:
2) Pas de base r(cid:19)ealisable initiale ! Phase I
Variable arti(cid:12)cielle : a6
Min a6
(
yi)
sous
x1 + 3x2
x1 + x2 (cid:0) x3
(
X
(cid:0)x4
+x5
+a6 = 4
= 10
xi (cid:21) 0
i = 1; : : : ; 5;
a6 (cid:21) 0
10
) SBR : xT =(0 0 0 0 10 4)
Fonction objectif sous forme canonique :
z = a6 = 4 (cid:0) x1 (cid:0) 3x2 + x4
! (cid:0)x1 (cid:0) 3x2 + x4 (cid:0) z = (cid:0)4
x1 x2 x3 x4 x5 a6
0
-1 -3
1
3
1
0
1
1
0
0
-1
1
-1
0
0
0
1
Publicité
b
z
-1 -4
4
0
0 10
x2 rentre ; minf4
1 g ) a6 sort
3; 10
l1 ! l1 + l2
l2 ! l2=3
l3 ! l3 (cid:0) l2=3
x1
0
1/3
2/3
x2 x3
0
0
0
1
-1
0
x4
0
-1/3
1/3
x5
0
0
1
z
b
a6
1
-1
0
4/3
0
1/3
-1/3 0 26/3
a6 = 0 ! n’est plus n(cid:19)ecessaire
on a la SBRO du probl(cid:18)eme min a6, a6 (cid:21) 0
11
) on a une SBR du probl(cid:18)eme de d(cid:19)epart :
xT =(0 4/3 0 0 26/3)
Base : x2; x5
3) Phase II
Exprimer la fct objectif en fct des VHB
z = x1 + x3 +
x1 (cid:0) x4 (cid:0) 4
3
=
4x1
3
+ x3 (cid:0)
x4
3
(cid:0)
4
3
x1
4/3
1/3
2/3
x2 x3
1
0
0
1
-1
0
x4
-1/3
-1/3
1/3
x5
0
0
1
b
z
4/3
-1
0
4/3
0 26/3
x1 x2 x3 x4 x5
1
0
2
1
-1
1
3
-3
2
0
0
1
0
1
0
b
z
-1 10
0 10
0 26
Optimum : xT =(0 10 0 26 0) ; z=-10
12
Exercice 1.2.4.
R(cid:19)esoudre par la m(cid:19)ethode du simplexe
Min x2 (cid:0) 2x1
sous
2 (cid:20) x1 (cid:20) 8
x2 (cid:20) x1 (cid:20) x2 + 2
(
Comparer avec les solutions obtenues graphi-
quement
1) Forme standard
Min x2 (cid:0) 2x1
x1 (cid:0) x3 = 2
x1 + x4 = 8
x1 (cid:0) x2 (cid:0) x5 = 0
x1 (cid:0) x2 + x6 = 2
xi (cid:21) 0
i = 1; : : : ; 6
sous
8
>>>>>><
>>>>>>:
Il manque une VB
13
2) Phase I
sous
Min x7
x1 (cid:0) x3 + x7 = 2
x1 + x4 = 8
(cid:0)x1 + x2 + x5 = 0
x1 (cid:0) x2 + x6 = 2
xi (cid:21) 0
i = 1; : : : ; 7
8
>>>>>><
>>>>>>:
z = x7 = 2 (cid:0) x1 + x3 ! x3 (cid:0) x1 (cid:0) z = (cid:0)2
x1 x2 x3 x4 x5 x6 x7
0
0
-1
1
0
1
0
1
1
0
0
-1
0
0
1
0
0
0
1
-1
1
-1
0
0
0
0
0
0
0
1
0
0
0
1
0
z
b
-1 -2
2
0
8
0
0
0
2
0
1; 2
x1 rentre ; minf2
pour terminer phase I)
1; 8
1g ! x6 ou x7 sort (x7
14
x1 x2 x3 x4 x5 x6 x7
1
0
0
1
Publicité
0
1
-1
1
0
1
0
0
-1
0
0
0
-1
1
-1
1
0
0
0
1
-1
0
0
0
0
1
0
0
0
1
0
b
z
-1 0
0 2
0 6
0 2
0 0
z = 0 = x7 OK ; SBR : xT =(2 0 0 6 2 0)
VB : x1; x4; x5; x6 ; VHB : x2; x3
3) Phase II
z = x2 (cid:0)2x1 = x2 (cid:0)2(x3 +2) ) x2 (cid:0)2x3 (cid:0)z = 4
x1 x2 x3 x4 x5 x6
0
0
0
1
0
0
0
0
1
0
-2
-1
1
-1
1
1
0
0
1
-1
0
0
0
1
0
0
0
1
0
0
x6 sort, x3 rentre
l1 ! l1 + 2l5
l2 ! l2 + l5
l3 ! l3 (cid:0) l5
l4 ! l4 + l5
b
z
-1 4
0 2
0 6
0 2
0 0
15
x1 x2 x3 x4 x5 x6
2
0
1
1
-1
0
1
0
1
0
-1
-1
1
0
-1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
x4 sort, x2 rentre
l1 ! l1 + l3
l2 ! l2 + l3
l5 ! l5 + l3
x1 x2 x3 x4 x5 x6
1
0
0
1
-1
0
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
b
z
-1 4
0 2
0 6
0 2
0 0
b
z
-1 10
8
0
6
0
2
0
6
0
Optimum : xT =(8 6 6 0 2 0) ; z=-10
16
4) Remarque :
Substitution : x0
1 = x1 (cid:0) 2
) Min x2 (cid:0) 2(x0
1 + 2) ! Min x2 (cid:0) 2x0
1
0 (cid:20) x0
1 (cid:20) 6
x2 (cid:0) 2 (cid:20) x0
x0
1; x2 (cid:21) 0
1 (cid:20) x2
sous 8
><
>:
x0
1 + x3 = 6
x0
1 (cid:0) x2 + x4 = 0
(cid:0)x0
xi (cid:21) 0
1 + x2 + x5 = 2
i = 1; : : : ; 6
) 8
>>><
>>>:
) simplexe canonique !
5) R(cid:19)esolution graphique
17