PLNE
PLNE
Programmation Lin aire en Nombres Entiers
Applications et Exercices
N.Elloumi
Exercice 0
N.Elloumi
21:est optimalesoution la entiers dessont x les -2294:est optimalesolution la r els dessont x les -1:si queMontrer 2121====xxxx 쳣+- +-+=013108122S.C(P)212121ixxxxxxxZMax
Exercice 1
Probl me du sac dos
Un randonneur dispose dun sac `a dos de volume B.
Il peut emporter n objets chacun de volume ai et
de valeur ci. Le randonneur doit choisir les objets
qui maximiseront la valeur totale emport e.
Advertisement
On suppose que les objets sont indic s dans le sens des ci/ai d croissants.
Exemple :
N.Elloumi
{} Σ= == niiniiiniiixBxaxcZMax0111,0S.C(P){} Σ++++++++++= 606543216543211,05343S.C2741815(P)iixxxxxxxxxxxxxZMax
N.Elloumi
()()0,0,0,1,1,022Z0 :Ssolutions de pas1 :S:en partag est , valuation meilleure la a qui Ssommet Le0,0,31,1,0,121Z0 :S0,0,0,0,1,3123Z1 :S sur brancheOn optimalesolution la de sup rieure borne une donne 24Z0,0,0,0,21,124 Z:S continues esen variabl PLdu optimalesolution La65432141413165432122265432112120654321*00======= = = ======= = ======= == =======xxxxxxxxxxxxxxxxxxxxxxxxxxxxxExercice 2
Probl mes daffectation
On a n t ches affect e n personnes.
On veut affecter une et une seule t che chaque personne ;
"
"
" Le rendement de laffectation de la t che i la personne j est donn e par la
matrice Cij ;
" On veut maximiser le rendement ;
Advertisement
"
" Formulation tendue : si le nombre de t ches est inf rieur au nombres de
Formulation ?
personnes
N.Elloumi
Exercice 2
Formulation de laffectation
N.Elloumi
=sinon0j personne la affect e i t chela si1 variablesesintroduit On ijijxx()()fois une affect eest t chechaque1j affect eest t cheseule une1sContrainte Maximiser 1111== ====njijniijninjijijxxxC
Exercice 2
Formulation de laffectation tendu
N.Elloumi
m t chesde Nombren personne de Nombre> ======== minjijijnjijmiijxCmixnjx1111 Maximiser ...11:1est i t chela affect es personnes des Somme...11:1est j personnes la affect es t chesdes Somme
Exercice 3: probl me de recouvrement
Advertisement
Soit la ville suivante, compos e des arrondissements suivants :
On doit construire un certain nombre dh pitaux, qui devront
de
urgences m dicales
soccuper
larrondissement o il est construit et de tous ses voisins
imm diats. On cherche minimiser le nombre dh pitaux.
provenant
des
N.Elloumi
0. reste le1 optimaleSolution 983====xxx
Exercice 3: probl me de recouvrement
N.Elloumi
=sinon0iment arrondissel' dans h pitalun auray il si1 variablesesintroduit On iixx1111111111sContrainte Minimiser 111091110985109876587648765439865327643165432153214321111 ++ ++++ +++++ +++ +++++ +++++ ++++ +++++ +++ +++ =xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxii
Advertisement
Exercice 4
N.Elloumi
Σ+--=INxxxxxZMini59121011102121S.C(P)Dos- -Sac Prob 쳣+--=059121011102121ixxxxxZMinS.C)(Pcontinue RelaxationR() 0;9.559 :P de optimaleSolution 21R==-=xxZ()P? de optimalesolution une elleest 0;6 arrondie P de optimalesolution la:21R1==xxQ() 4;1 :P de optimalesolution la que coupes de m thode uned' aidel' montrer :212==xxQ
Exercice 5
N.Elloumi
Σ+ +--=++ZxIRxxxxxxxZMin2121212115863253S.C(P){} Σ++++=10734151816321321,S.C(P)ixxxxxxxZMax() B)&B Bound and-Branch de M thode Σ+ ++=+INxxxxxxxZMaxi4559658212121S.C(P)
Exercice 6
N.Elloumi
Σ- ++=+INxxxxxxxZMaxi041543212121S.C(P) coupes de M thode Σ ++=+INxxxxxxZMaxi22010512121S.C(P) Σ+ ++=+INxxxxxxxZMaxi11239225212121S.C(P)
Exercice 7
N.Elloumi
() Σ- ۣ +- ++=INxxxxxxxxxxZMaxi155120802682111212121&..S.C(P)B&B de M thode