Exercice trois et quatre du TD
Exercise 1 On consid re le programme lin aire suivant:
(P2)
x1 + x2)
(cid:0)
min (z1 =
contraintes
sous
(cid:0)
x2
2x1
(cid:0)
x1
x2
(cid:0)
x1 + x2
x1; x2
(cid:21) (cid:0)
2
5
(cid:20)
(cid:20)
0
2
(cid:21)
8
>><
>>:
1. Repr sentation des solutions admissible :
Figure 1: R solution graphique
points qui repr sentent des bases r alisables E=(0,0) A=(2,0) B=( 7
2 ; 3
2 ) C=(1,4) D=(2,0)
2.
3.
points qui repr sentent des bases r alisables E=(0,0) A=(2,0) B=( 7
Z
-2
-2
0
2 ; 3
2 )
c=(1,4) D=(2,0)
3
2
4. On remarque que les deux sommets A et B sont optimaux:
Z(A) = Z((2; 0)) =
Z(B) = Z((
7
2
;
3
2
1
Publicité
2
(cid:0)
)) =
2
(cid:0)
012345012345donc les points r alisables qui sen d duisent par combinaison lin aire con-
2 situ s entre A et B
vexe c- -d tous les point de la droite :
le segment
x1 + x2 =
(cid:0)
(cid:0)
Exercise 2
(P L)
8
<
:
1.
max (z = 5x1 + x2 + 6x3 + 24x4)
sous
(cid:0)
contraintes
4x1 + 4x2 + 4x3 + x4
4x1 + 4x2 + 4x3 + x4
xj
0
24
36
(cid:20)
(cid:20)
(cid:21)
max (z = 5x1 + x2 + 6x3 + 24x4)
sous
contraintes
(P L)
8
<
4x1 + 4x2 + 4x3 + x4 + x5 = 24
4x1 + 4x2 + 4x3 + 3x4 + x6 = 36
xj
0
(cid:0)
(cid:21)
4
6
4
4
1
3
1
0
0
1
:
Publicité
A =
b =
4
8
(cid:18)
24
36
c =
5
1
6
24
0
0
x1
(cid:0)
0
1
(cid:19)
(cid:1)
x =
C
C
C
C
C
C
A
On appelle base toute sous-matrice carr e r guliaire extraite de A Soit B
une base, A = (B; N ) de m me on partitionne x =t (xB; xN ) :
B
B
B
B
B
B
@
x6
(P L)
max (z = cx)
sous
contraintes
(cid:0)
Ax = b
x
0
(cid:26)
(cid:21)
(P L)
()
z
max
sous
1b =
Publicité
cBB(cid:0)
(cid:0)
contraintes
N xN
(cid:0)
(cid:0)
BxB = b
x
0
(cid:0)
(cid:26)
(cid:21)
cN
(cid:0)
(cid:0)
cBB(cid:0)
1N
xN
(cid:1)
(cid:1)
On note cN = cN
(cid:0)
2. B
, inverse de B:
cBB(cid:0)
1N appel s coe cients r duits de
B =
(cid:18)
4
4
1
3
(cid:19)
1
3
8
8 (cid:0)
1
1
2 (cid:19)
2
(cid:0)
B(cid:0)
1 =
(cid:18)
2
(a) B est r alisable ssi B(cid:0)
1b
0: la solution associ e B = (A3; A4) :
xN = 0 (x1 = x2 = x5 = 0) donc x3 = 9
2 ; x4 = 6:
(cid:21)
(b) B est optimale ssi les coe cients r duits sont tous n gatifs pour un
probl me de maximisation.
Publicité
cN = cN
cBB(cid:0)
1N
0
(cid:20)
(cid:0)
6
(cid:0)
(cid:1)
(cid:0)
39
4 (cid:0)
45
4
1
3
8
8 (cid:0)
1
1
2 (cid:19) (cid:18)
2
(cid:0)
4
8
4
6
1
0
0
1
(cid:19)
(cid:18)
(cid:1)
24
(cid:1)
cBB(cid:0)
1N =
5
1
0
0
cN
(cid:0)
46
(cid:0)
55
2
(cid:0)
=
(cid:0)
(cid:0)
3