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 d’un 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. 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 La654321*414131654321*222654321*1212*0654321*00xxxxxxxxxxxxxxxxxxxxxxxxxxxxxExercice 2

Problèmes d’affectation

On a n tâches affectée à n personnes. On veut affecter une et une seule tâche à chaque personne ;

• • • Le rendement de l’affectation de la tâche i à la personne j est donnée par la

matrice Cij ;

• On veut maximiser le rendement ; • • Formulation étendue : si le nombre de tâches est inférieur au nombres de

Formulation ?

personnes

N.Elloumi

Exercice 2

Formulation de l’affectation

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 l’affectation é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

Soit la ville suivante, composée des arrondissements suivants :

On doit construire un certain nombre d’hôpitaux, qui devront de urgences médicales s’occuper l’arrondissement où il est construit et de tous ses voisins immédiats. On cherche à minimiser le nombre d’hô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

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