Course: Mixed Integer Programming (Solving)

1. Exemple introductif

Ces chapitres proviennent du cours 1A d'Olivier Briant et sont très didactiques pour revoir l'algorithme du branch and bound.

Vous avez un budget de 4200 euros pour acheter des ordinateurs pour l’entreprise pour qui vous travaillez. Sur le marché, seuls deux types vous intéressent. Configurer chaque ordinateur prend du temps et vous limite. Vous cherchez à optimiser l’utilité globale.

Modélisation en programme linéaire en nombres entiers (IP) :

Hypothèses:

Linéarité: la fonction objectif et les contraintes sont linéaires

Domaines des variablesles variables ne peuvent pas prendre n’importe quelle valeur réelle, seules les valeurs entières sont considérées 

Representation graphique:

Remarque importante: contrairement à la programmation linéaire (en variables continues), la solution optimale peut se situer à l’intérieur du polyèdre