-
7/24/2019 TD N4-1
1/13
Universit Mohamed V 20-01-2016-ENSIAS-
Devoir N 4
Exercice 1:Rsoudre avec la mthode analti!ue du sim"le#e
Ma# $x1 % &x2 %6x3
Su'et (&x1 % x2 % &x3 ) &02x1 % 2x2 % &x3 )
$0
x1 *x2, x3 + 0,Note trans.ormer en un "ro/lme Min da/ord
Exercice 2 :Soit le "ro/lme de "ro3rammation linaire
min 4 5x1 4 x2 4 7x& 4 6x$ 4 5x8 4 x6 4Su'et ( x1 % x& %
x8 9 $
% x2 % x$ %x6 9 2x1 % x$ 9 2
x2 % x8 9 1xj + 0* j 91* 2* :* 6
; une certaine itration de lal3orithme du sim"le#e* linverse de
la /ase est
a Si oui* "our!uoi? Sinon "oursuivrelal3orithme du sim"le#e
c Si les termes de droite du "ro/lme ori3inal sont modi.is avec
le vecteur
b=[1*1*1*1]T
,i?e?*
b b +b * la solution o"timale demeure-t-elle
-
7/24/2019 TD N4-1
2/13
ralisa/le "our le nouveau "ro/lme> @uelle est la modi.ication
de la valeur o"timale de la.onction conomi!ue
Exercice 3 :
1? Soit le "ro/lme de "ro3rammation linaire avec une seule
contrainte n
mincjxjj =1
n
ajx j b
Su'et ( j=1
x j 0*
j =1* 2*???* n?
Su""osons !ue b 0 et aj 0*j 9 1* 2* :* n? Su""osons 3alement
!uil e#iste aumoins un indicej tel !ue cj B 0?
-
7/24/2019 TD N4-1
3/13
,Su33estion considrerxk comme varia/le de /ase du "ro/lme?
Exercice 4:Donsidrons le "ro/lme de "ro3rammation linaire
minn
z =cjxjj =1
n
Su'et( aijx j =bij=1
i =1*2*???* m
oC les varia/lesxj ne sont "as restreintes ( tre non n3atives?
Four crire le"ro/lme sous une .orme standard en "ro3rammation
linaire* rem"laGons
Alors le "ro/lme devient
x j =x1j x2j
j =1*2*???* n?
min
Su'et (
n
z=cj ,x1j x2j j=1n
aij ,x1j x2j =
bij=1
i =1*2*???* m
x1j 0*x2j 0 j =1*2*???* n?
-
7/24/2019 TD N4-1
4/13
-
7/24/2019 TD N4-1
5/13
nous modi.ions le terme de droite de la "remire contrainte
b2 =15
dune
!uantit b2 =16
sans chan3er le terme de droite de la deu#ime contrainte
,i?e?*
b1 =0 * la solution de /ase o"timale "our le "our le "ro/lme
ori3inal est-elleralisa/le "our le "ro/lme modi.i > Si oui*
dterminer une solution o"timale"our le nouveau "ro/lme de mme !ue
la valeur o"timale de ce dernier? Si non*dites "our!uoi elle nest
"as ralisa/le?
3
-
7/24/2019 TD N4-1
6/13
Exercice 8:
1? Rsoudre avec la variante du sim"le#e "our "ro/lme avec
varia/les /ornes
min z 9 2x1 %x2 % &x&4 2x$ % 10x8Su'et (
x1 % x&4 x$ % 2x8 9 8x2 % 2x& % 2x$ % x8 9 6
0)x1 )7* 0)x2 )10* 0)x& )1* 0)x$ )8* 0)x8 )&
Exercice 9:
1? Donsidrer le "ro/lme de "ro3rammation linaire suivantmin
Sujet
Mn
Haijx j )M
j 91
n
Hx j 91j 91
x j + 0
i 91*2*???*m
j 91*2*???*n?
a
-
7/24/2019 TD N4-1
7/13
2? Su""oser !uun "ro/lme de "ro3rammation linaire sous .orme
standard et sondual soient ralisa/les?
-
7/24/2019 TD N4-1
8/13
alorsx est une solution o"timale du "ro/lme?
2? Donsidrer le "ro/lme de "ro3rammation linaire suivant
min 2x1
% &x2
% $x
&
Su'et ( x1
% 2x2
% x&
+ &
2x1 R x2 % &x& + $
x1
+ 0*x2
+ 0*x&
+0
Introduire les varia/les dcart et rsoudre ce "ro/lme avec
lal3orithme dual dusim"le#e en utilisant la solution de /ase
initiale oC les varia/les dcart sont lesvaria/les de /ase?
crire le dual de ce "ro/lme?
-
7/24/2019 TD N4-1
9/13
min z 9 &x1 R&x 2 $x&Su'et ( 6x1 % 2x2 % 8x& )
28
&x1 % &x2 % 8x& ) 20
x1 *x2 *x& + 0?
Utiliser la thorie de la dualit "our dterminer si la solution
"our le "ro/lmeori3inal demeure o"timale "our ce nouveau
"ro/lme?
e
-
7/24/2019 TD N4-1
10/13
VT x1 x2 x& x$ z
