Solutions
544
On a donc la solu tion :
x
*
1 5 0 ; x
*
2 5
5
2
; x
*
3 5 0 ; x
*
4 5 0 ; x
*
5 5
19
2
; x
*
6 5 0 ; x
*
7 5
9
2
; z
* 5 10.
2) En consi dé rant le tableau ini tial des contraintes, on obtient immé dia te ment le pro -
gramme dual :
x 1
y 1
y 2
y 3
x 2
x 3
x 4
1
3
2
1
2
1
1
3
1
1
1
4
12
5
7
5
4
3
1
I µ
x 1 1
x 2 1
x 3 1
x 4 < 12 (1)
3x 1 1 2x 2 1 3x 3 1
x 4 < 5 (2)
2x 1 1 x 2 1 x 3 1 4x 4 < 7 (3)
x 1 ,
x 2 ,
x 3 ,
x 4 > 0
3max4 z 5 5x 1 + 4x 2 + 3x 3 +
x 4
II µ
y 1 1 3y 2 1 2y 3 > 5 (1)
y 1 1 2y 2 1 y 3 > 4 (2)
y 1 1 3y 2 1 y 3 > 3 (3)
y 1 1 y 2 1 4y 3 > 1 (4)
y 1 ,
y 2 ,
y 3 > 0
3min4 z r 5 12y 1 + 5y 2 + 7y 3
et l’on sait que l’on peut pas ser des solu tions du primal à celles du dual : (on a posé
y 4 5 y 1 , y 5 5 y 2 , y 6 5 y 3 , y 7 5 y 4 et x 5 5 x 1 , x 6 5 x 2 , x 7 5 x 3 ).
Variables duales
Variables primales
Solutions du dual
Solutions du primal
(�j du primal au signe près)
(��i du dual au signe près)
�y 1
x 1
x 2
x 3
�y4 �y5 �y6 �y7 y 1
x 1
x 2
x 3
x 4
x 5
x 6
x 7
y 2
y 3
�y 2 �y 3 �y 4
1
0
0
0
0
0
3
1
0
2
0
5
2
9
2
19
2
3) Il est évident que l’équa tion (1) est redon dante dans le sys tème I (primal) car (2)
implique (1) ; dans ces condi tions, on pour rait résoudre le pri mal en ne tenant compte que des
in équa tions (2) et (3). En effet : x 1 1 x 2 1 x 3 1 x 4 < 3x 1 1 2x 2 1 3x 3 1 x 4 < 5 , 12.
PRIMAL
DUAL