Graphes et Recherche Operationnelle ESIAL 2A

pefav

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

34 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

Graphes et Recherche Operationnelle – ESIAL 2A Chapitre 7 : Programmation lineaire en nombres entiers J.-F. Scheid 2011–2012 1

procedures de separation et d'evaluation

pixi ≤

solution optimal

probleme de sac

production en nb entiers

quantite entiere de produit

Informations

Publié par	pefav
Nombre de lectures	87
Langue	Français

Extrait

Graphes et Recherche Operationnelle { ESIAL 2A
Chapitre 7 : Programmation lineaire en nombres entiers
J.-F. Scheid
2011{2012
1Plan du chapitre
I. Introduction et exemples
II. Solutions optimales a valeurs entieres
III. Procedures de Separation et d’Evaluation ("Branch and Bound")
1 Programmation lineaire en variables binaires
2 lineaire en nombres entiers (PLNE)
2I. Introduction et exemples
PL en nombres entiers deja rencontres : pb d’a ectation, pb de ot
maximal, pb de production en nb entiers
Le caractere entier de la solution resulte directement de la structure
du programme et plus precisement des proprietes de la matrice A des
contraintes (Ax b).
Pour certains problemes ou on cherche une solution optimale entiere
(par ex. quantite entiere de produit ...), il faut inclure la contrainte de
nombres entiers dans le programme, sans quoi la solution optimale
n’est pas entiere (pb de sac a dos, pb de remplissage)
3