Exercices 7 et 8 du TD
Exercise 1
1. R solution par le simplexe :
x2
M v1
(cid:0)
(cid:0)
M v2)
(P )0
t1 + v2 = 6
(cid:0)
(cid:0)
max (z1 =
sous
2x1
(cid:0)
contraintes
3x1 + x2 + v1 = 3
4x1 + 3x2
x1 + 2x2 + t2 = 3
x1; x2
0
M >>> 0
(cid:0)
(cid:21)
8
>>>><
>>>>:
(a)
(t3; v1; v2) est une base r alisable du probl me (P )0, mais la fonction
objectif nest pas crite en fonction des variables Hors base L4 =
2+3M +
L0 +M L1 +M L2 =
(cid:0)
)
4M =
M;L45=0;L46=
2+7M;L43=
M + M = 0 et L47=
L41 = 0+3M +6M = 9M;L42=
1+M +3M =
M + M = 0:
1+4M;L44=
(cid:0)
(cid:0)
(cid:0)
(cid:0)
(cid:0)
max
B
v1
v2
t3
cB
(cid:0)
(cid:0)
0
b
M 3
M 6
3
9M
2
(cid:0)
x1
3
4
1
1
(cid:0)
x2
1
3
2
0
t1
0
1
(cid:0)
0
0
t2
0
0
1
M 0
M
(cid:0)
v1
1
0
0
0
M
(cid:0)
v2
0
1
0
0
L0
L1
L2
L3
L4
bi
ai1
=ai1 > 0
=
(cid:0)
(b) 2+7M > 0, x1 entre (la colonne 1 est la colonne pivot), min
" (cid:0)
(cid:0)
2 + 7M
1 + 4M
donc v1 sort de la base et la ligne 1 est la ligne pivot ( le Pivot
n
b1
a11
est a11)
o
3 L1
L1 := 1
L2 := L2
L3 := L3
4L1
L1
(cid:0)
(cid:0)
2 + 7M )L1
(
(cid:0)
max
B
x1
v2
t2
max
B
x1
v2
t2
L4 := L4
(cid:0)
2
(cid:0)
x1
b
cB
1
2
1
(cid:0)
M 6
4
(cid:0)
3
1
0
2 + 2M 0
(cid:0)
(cid:0)
(cid:0)
(cid:0)
4
1
4
1
1
(cid:0)
x2
1=3
3
(cid:0)
2
(cid:0)
5
3 M
2
(cid:0)
x1
cB
b
1
1
2
(cid:0)
M 2
0
(cid:0)
2
0
0
2 + 2M 0
1
(cid:0)
x2
1=3
5=3
5=3
5
3 M
1
0
t1
0
0
t2
0
0
1
0
(cid:0)
(cid:0)
0
0
0
M
(cid:0)
v1
1=3
0
(cid:0)
0
(cid:0)
- 1
3 (
4=3
1=3
(cid:0)
2 + 7M )
M
(cid:0)
v2
0
1
0
0
(cid:0)
0
(cid:0)
M
(cid:0)
1
(cid:0)
0
4=3
1=3
1
3 (cid:0)
0
t1
0
1
3 " (cid:0)
(cid:0)
0
t2
0
0
1
M 0
1
(cid:0)
0
M
(cid:0)
v2
0
1
0
0
(c) 5
1
3 > 0, x2 entre (la colonne 2 est la colonne pivot), min
(cid:0)
3; 6=5; 6=5
3 M
min
f
est la ligne pivot ( le Pivot est a22)
= 6=5 = b2
a22
donc v2 sort de la base et la ligne 2
n
g
bi
ai2
=ai2 > 0
=
o
0
Publicité
t2
0
0
1
0
(cid:0)
(cid:3)
(cid:0)
0
3
5 = 0
0
2 + 2M
(cid:0)
max
B
x1
x2
t2
cB
2
(cid:0)
1
(cid:0)
0
L2 := 3
5 L2
1=3L2
L2
L1 := L1
(cid:0)
L3 := L3
(cid:0)
( 5
3 M
L4 := L4
(cid:0)
1
3 ) = 12=5
(cid:0)
0
0
1
3 )L2
6
5 ( 5
3 M
(cid:0)
2M + 1
3
(cid:0)
0
2=5
5 = 6
3
5
b
1
2
0
12=5
(cid:0)
(cid:3)
0
2
(cid:0)
x1
1
0
0
0
(cid:0)
max
B
x1
x2
t2
cB
2
(cid:0)
1
(cid:0)
0
b
3=5
6
5
0
12=5
2
(cid:0)
x1
1
0
0
0
1
(cid:0)
x2
1=3
5=3
5=3
0
1
(cid:0)
x2
0
1
0
0
1=3
3
5 = 1
5=3
(cid:0)
(cid:3)
(cid:0)
0
t1
0
1=3 (
(cid:0)
3
5 =
(cid:0)
3=5)
3
5
(cid:0)
1
(cid:0)
(cid:3)
0 + 1
2M + 1
3
(cid:0)
0
t1
1=5
3
5
(cid:0)
1
2M + 1
3
(cid:0)
0
t2
0
0
1
0
(d) Puisque le coe cient r duit de la hors base sont positifs : c3 < 0,
: t1 = 0; x1 = 3=5; x2 = 6
5
alors la solution de base B =
et t2 = 0;est optimale, de co t
x1; x2; t2
f
12
5 :
:
(cid:0)
g
2. Repr sentation des solutions admissibles :8
>><
>>:
x1 = 3
5 ; x2 = 6
, Solution is:
(a)
5
3x1 + x2 = 3
4x1 + 3x2
6
(cid:21)
x1 + 2x2
3
(cid:20)
x1; x2
0
(cid:21)
(cid:26)
(cid:26)
3x1 + x2 = 3
4x1 + 3x2 = 6
3x1 + x2 = 3
x1 + 2x2 = 3
4x1 + 3x2 = 6
x1 + 2x2 = 3
, Solution is:
(cid:2)
x1 = 3
5 ; x2 = 6
5
(cid:3)
(cid:2)
, Solution is:
x1 = 3
(cid:3)
5 ; x2 = 6
5
(cid:26)
points des bases A01=(0,0) A02=(0,3) A03=(0; 2) A04=(0, 3
2 )
(cid:3)
(cid:2)
points qui repr sentent des bases A12=(1,0) A13=( 3
2 ,0) A14=(3,0)
2
points qui repr sentent des bases A23=(0,0) A24=(1,4)
5 ; 6
5
points qui repr sentent des bases A34=
z(
) =
(cid:0)
3
3
2
(cid:0)
(cid:3)
3
5 (cid:0)
6
5 =
12
5
(cid:0)
5 ; 6
5
(cid:0)
3
5 ; 6
5
3
5 ; 6
(cid:1)
5
(cid:0)
(cid:1)
(cid:1)
(cid:0)
(cid:1)
Figure 1: R solution graphique
point qui repr sente la base r alisable optimale A34=
z(
) =
3
2
(cid:0)
(cid:3)
3
5 (cid:0)
6
5 =
12
5
(cid:0)
5 ; 6
5
3
5 ; 6
5
(cid:0)
(cid:1)
(cid:1)
(cid:0)
(b) Cheminement initialisation (le premier tableau du simplexe ) solution
de base r alisable A01 = (0; 0) : le deuxi me point est A12 = (1; 0)
ensuite A23 = A24 = A34 =
(optimale).
3
5 ; 6
5
Exercise 2 On consid re le programme lin aire suivant:
(cid:0)
(cid:1)
min (z1 = 6x1 + 5x2)
sous
(cid:0)
x1 + x2
contraintes
8
2x1 + 3x2
x2
3
(cid:20)
(cid:20)
6
(cid:0)
x1
Publicité
(cid:0)
x1; x2
(cid:20)
0
(cid:21)
(P )
8
>><
>>:
x1 + x2
(cid:20)
8
2x1 + 3x2
x2
3
6
(cid:20)
1. Repr sentation des solutions admissibles :8
>><
>>:
5 ; x2 = 22
(cid:0)
x1
(cid:0)
x1; x2
, Solution is:
x1 + x2 = 8
2x1 + 3x2 = 6
x1 = 18
5
(cid:26)
(cid:0)
(cid:20)
0
(cid:21)
,
(cid:3)
(cid:2)
3
012345012345x1 + x2 = 8
x2 = 2
x1
(cid:0)
2x1 + 3x2 = 6
x2 = 3
(cid:0)
x1
(cid:0)
(cid:26)
(cid:26)
, Solution is: ,
, Solution is: ,
points qui repr sentent des bases A01 = (0; 0) A02 = (0; 8) A03 = (0; 2) A04 = (0;
2)
(cid:0)
r alisable
r alisable
points bases A12 = (8; 0) A13 = (
3; 0) A14 = (2; 0)
(cid:0)
r alisable
points des bases A23 =
18
5 ; 22
5
r alisable
(cid:0)
A24 = (5; 3)
r alisable
(cid:1)
points des bases A34=(15; 12)
Figure 2: R solution graphique
La solution optimale est A24 = (5; 3) de co t z (5; 3) = 6
5 + 5
(cid:3)
(cid:3)
3 = 45:
2. R solution par le simplexe :
2(cid:21)) x1 + (5 + (cid:21)) x2
max z1 = (6
sous
(cid:0)
contraintes
x1 + x2 + t1 = 8
(cid:0)
2x1 + 3x2 + t2 = 6
x2 + t3 = 2
(cid:0)
x1
(cid:0)
x1; x2
t1
(cid:21)
0
(cid:21)
0; t2
0
(cid:21)
(P )
8
>>>><
>>>>:
4
0246802468(a)
gi=1;2;3 est une base r alisable donc on peut crire le tableau du
ti
f
simplexe associ cette base :
max
B
t1
t2
t3
cB
0
0
0
b
8
6
2
2(cid:21))
(cid:0)
(6
x1
1
2
(cid:0)
1
(6
(cid:0)
2(cid:21))
(5 + (cid:21))
x2
1
3
1
(cid:0)
(5 + (cid:21))
0
t1
1
0
0
0
0
t2
0
1
0
0
0
t3
0
0
1
0
L1
L2
L3
L4
5 + (cid:21)
1=3
, donc t2 sort de la base
()
(cid:20)
(cid:20)
= b2
a22
(cid:21) alors, x2 entre dans la base
3 L2
L2 := 1
L1 := L1
L2
L3 := L3 + L2
(cid:0)
L4 := L4
(5 + (cid:21))L1
(cid:0)
2(cid:21)) + 2=3 (5 + (cid:21)) =: 28
(b) Si 6
min
2(cid:21)
(cid:0)
1 ; 6
8
3
(a)
(cid:8)
(cid:9)
L4
(cid:0)
max
B
t1
x2
t3
(5 + (cid:21))L1
(6
(cid:0)
cB
0
0
0
2 = 6
b
8
2
2 + 2 = 4
(cid:0)
(cid:0)
2(cid:21))
(6
x1
1 + 2=3 = 5=3
2=3 = 1=3
2=3
(cid:0)
1
(cid:0)
28
3 (cid:0)
4
3 (cid:21)
"
4
3 (cid:21)
"
3 (cid:0)
(5 + (cid:21))
x2
1
1
(cid:0)
1 = 0
1 + 1 = 0
(cid:0)
0
(cid:0)
(5 + (cid:21))
0
t1
1
0
0 + 0 = 0
0
(5 + (cid:21)) = 0
0
(cid:0)
0
t2
0
(cid:0)
1=3
0 + 1=3 = 1=3
1=3 =
(cid:0)
1=3
(5+(cid:21))
3
(cid:0)
0
0
0
t3
0
0
1
0
(5 + (cid:21))
1=3
0
0 = 0
(cid:3)
(cid:0)
(cid:0)
L1
L2
L3
L4
i. Si
4(cid:21)
28
(cid:0)
5 + (cid:21)
0
(cid:20)
0
(cid:20)
(cid:26)
(cid:26)
alors x1 = 0 et x2 = 2 est optimale
Publicité
4(cid:21)
28
(cid:0)
5 + (cid:21)
0
(cid:20)
0 ()
(cid:20)
(cid:21)
7
(cid:20)
ii. Sinon 7
b1
a11
(cid:21)
(cid:21)
= t1 sort de la base :
(cid:21)
1
3 alors x1 entre dans la base, min
6
5 (cid:3)
(cid:8)
3 = 18=5; 12
=
(cid:9)
5 L1
L1 := 3
L2 := L2 + 2=3L1
1=3L2
L3 := L3
4
3 (cid:21)
(cid:0)
28
3 (cid:0)
L4 := L4
(cid:0)
(cid:0)
2(cid:21))
max
B
t1
x2
t3
cB
0
0
0
b
18=5
22=5
14=5
(cid:0)
(6
x1
1
0
0
0
5
(cid:1)
(5 + (cid:21))
x2
0
1
0
0
L1
0
t1
3=5
2=5
1=5
3
5
(cid:0)
(cid:0)
28
3 (cid:0)
(cid:0)
4
3 (cid:21)
(cid:1)
0
t2
1=5
(cid:0)
1=5
2=5
1
5 (cid:0)
3
5 (cid:21),
0
t3
0
0
1
0
L1
L2
L3
L4
3
5
4
3 (cid:21)
28
3 (cid:0)
3
5 (cid:21)
Si
(cid:0)
(cid:20)
0
(cid:1)
(cid:20)
x2 = 22=5 est une solution optimale.
1
5 (cid:0)
(cid:0)
()
(cid:26)
(cid:20)
1=3
0
(cid:21)
(cid:20)
7 alors x1 = 0 et
(b) Si (cid:21) < 1
3
1 ; 2
min
1
8
(5 + (cid:21)
6 + 2(cid:21)) alors, x1 entre dans la base
(cid:20)
= b2
a22
, t3 sort de la base :
(cid:8)
max
B
t1
t2
t3
(cid:0)
(cid:9)
cB
0
0
0
b
8
6
2
2(cid:21))
(cid:0)
(6
x1
1
2
(cid:0)
1
(6
(cid:0)
(5 + (cid:21))
x2
1
3
1
(cid:0)
(5 + (cid:21))
0
t1
1
0
0
0
0
t2
0
1
0
0
0
t3
0
0
1
0
L1
L2
L3
L4
2(cid:21))
"
L2 := 1
L1 := L1
L2
L3 := L3 + L2
3 L2
(cid:0)
L4 := L4
(5 + (cid:21))L1
(cid:0)
2(cid:21))
max
B
t1
t2
x1
cB
0
0
(6
2(cid:21))
(cid:0)
b
6
10
2
(cid:0)
(6
x1
0
0
1
0
(5 + (cid:21))
x2
2
1
1
(cid:0)
(11
(cid:21))
"
(cid:0)
0
t1
1
0
0
0
0
t2
0
1
0
0
0
t3
1
(cid:0)
2
1
6 + 2(cid:21)
(cid:0)
L1
L2
L3
L4
(cid:21)
11
(cid:0)
6 + 2(cid:21)
0
0 ()
(cid:20)
(cid:20)
(cid:26)
(cid:0)
i. Condition darr t si :
impossible . Donc
on peut am liorer la solution en appliquant le simplexe, on
cherche le coe cient r duit le plus grand.
(cid:21))
6 + 2(cid:21)
1
3 ; alors, x2 entre dans la base min
17
3 vrai sous la condition
2 ; 10
, t1
1
= b1
a12
()
(11
Publicité
(cid:20)
(cid:20)
(cid:0)
(cid:21)
6
ii. Si
(cid:21)
sort de la base :
(cid:0)
(cid:20)
(cid:8)
(cid:9)
2 L1
L1 := 1
L1
L2 := L2
L3 := L3 + L2
(cid:0)
L4 := L4
(11
(cid:0)
(cid:0)
(cid:21))L1
2(cid:21))
(cid:0)
(6
x1
0
0
1
0
(5 + (cid:21))
x2
1
0
0
0
0
t1
1=2
1=2
(cid:0)
1=2
(11
(cid:0)
(cid:21))=2
(cid:0)
0
t2
0
1
0
0
max
B
x2
t2
x1
cB
0
0
(6
conclusion
2(cid:21))
(cid:0)
b
3
7
5
6
1=2
0
t3
(cid:0)
5=2
1=2
3
2 (cid:21)
(cid:0)
L1
L2
L3
L4
1
2
(cid:21)
Solution optimale
(cid:0)1
A34 = (5; 3)
1
3
A24 =
18
5 ; 22
5
7
A03 = (0; 2)
1
3. Le programme lin aire admet une in&nit de solutions optimale si et seule-
ment si pour une solution de base optimale il ya un coe cient r duit de
la hors base nul. Soit on voit directement dapr s le tableau pr cedent
que lensemble des solution est in&ni sinon il faut reprendre les derniers
tableaux dans chaque cas.
(cid:0)
(cid:1)
(cid:21)
Solution optimale
z(x1; x2)
(cid:0)1
A34 = (5; 3)
5 (6
(cid:0)
2(cid:21)) + 3 (5 + (cid:21)) = 45
1
3
7(cid:21)
45
7(cid:21) = 218
5 (cid:0)
(cid:0)
14
5 (cid:21)
(cid:0)
A24 =
18
5 (6
5 ; 22
18
5
5 (5 + (cid:21)) = 218
2(cid:21)) + 22
(cid:1)
(cid:0)
(cid:0)
5 (cid:0)
14
5 (cid:21)
218
5 (cid:0)
14
5 (cid:21) = 2 (5 + (cid:21))
1
A03 = (0; 2)
2 (5 + (cid:21))
7
Remarque il est plus facile dutiliser la premi re remarque. Je vais pr sen-
ter la deuxi me methode car nous navons pas tudi ce cas en cours.
(a) Pour (cid:21) = 1
3 , A34 = (5; 3) apr s transformation on montre que
A24 = (5; 3) est une solution optimale ( d velopper les calculs)
2=3)
0
t3
(cid:0)
max
B
x2
t2
(cid:0)
x1
cB
0
0
6
2=3
(cid:0)
b
3
7
5
(6
x1
0
0
1
0
(5 + 1=3)
x2
1
0
0
0
0
t1
1=2
1=2
(cid:0)
1=2
16=3
(cid:0)
0
t2
0
1
0
0
1=2
(cid:0)
5=2
1=2
0
"
REMARQUE : la variable hors
base t3 a un coe cient r duit nul donc t3 le co t de la fonction
objectif:
max
B
x2
t3
x1
cB
0
0
b
22=5
14=5
18=5
16
3
x1
0
0
1
0
16
3
x2
1
0
0
0
0
t1
2=5
1=5
(cid:0)
3=5
0
t2
1=5
2=5
1=5
0
t3
0
0
0
0
L1
L2
L3
L4
18
(cid:0)
0
A24 =
une autre solution de base optimale donc le segment
( toute combinaison convexe de ceux deux points) est une
(cid:1)
solution optimale pour (cid:21) = 1
3 :
5 ; 22
16=3
(cid:0)
(cid:0)
5
(b) Conclusion le m me raisonnement pour (cid:21) = 7
(cid:21)
Solution optimale
(cid:0)1
A34 = (5; 3)
1
3
A24 =
18
5 ; 22
5
7
(cid:0)
(cid:1)
L1
L2
L3
L4
7
A03 = (0; 2)
1