optimisation linéaire en nombres entiers

Un atelier doit décider combien de bureaux et d’étagères fabriquer avec un nombre limité d’heures de découpe et d’assemblage. Produire 2,6 bureaux n’aurait aucun sens : les quantités doivent être entières.

L’optimisation linéaire en nombres entiers cherche, parmi toutes les combinaisons réalisables, celle qui maximise un gain ou minimise un coût. Les ressources consommées et le gain de chaque objet sont décrits par des relations linéaires.

Un problème d’optimisation linéaire en nombres entiers comporte une fonction objectif linéaire, des contraintes linéaires et des variables dont les valeurs doivent être entières. Si le vecteur des décisions est noté $xx$, le vecteur des gains ou coûts $cc$, la matrice des coefficients $AA$ et les ressources disponibles $bb$, une forme courante est :

L’ensemble des contraintes détermine les solutions admissibles ; l’intégralité écarte toutes celles qui ont une coordonnée fractionnaire. Certaines variables peuvent aussi être binaires, donc limitées à 0 ou 1, ou seules certaines variables peuvent être entières : on parle alors d’optimisation linéaire mixte en nombres entiers. Retirer l’exigence d’intégralité donne la relaxation linéaire, plus simple à résoudre mais susceptible de fournir une solution inutilisable. La classe contient des problèmes NP-difficiles. Des méthodes exactes comme la séparation et évaluation, ou branch and bound, divisent l’ensemble des possibilités en sous-problèmes et utilisent des bornes pour en éliminer. Les plans sécants ajoutent plutôt des inégalités valides qui retirent des solutions fractionnaires sans exclure les solutions entières admissibles.

Un atelier fabrique des bureaux et des étagères. Un bureau rapporte 40 €, demande 2 heures de découpe et 1 heure d’assemblage. Une étagère rapporte 50 €, demande 1 heure de découpe et 2 heures d’assemblage. L’atelier dispose de 8 heures pour chaque activité. Le nombre de bureaux est noté $xx$ et celui d’étagères $yy$.

1. Le modèle maximise $40x+50y40x+50y$, avec $2x+y\le 82x+y\; \backslash le\; 8$, $x+2y\le 8x+2y\; \backslash le\; 8$, et des nombres entiers $x,y\ge 0x,y\; \backslash ge\; 0$.
2. Sans l’intégralité, les deux contraintes sont saturées pour $x=y=\frac{8}{3}x=y=\backslash frac\{8\}\{3\}$. Le gain serait exactement 240 €, mais cette production fractionnaire est impossible.
3. Parmi les points entiers voisins admissibles, (2, 3) rapporte $2\times 40+3\times 50=2302\; \backslash times\; 40+3\; \backslash times\; 50=230$ euros, contre 220 € pour (3, 2).
4. Le choix optimal est donc 2 bureaux et 3 étagères, pour 230 €. Le contrôle donne 7 heures de découpe et exactement 8 heures d’assemblage. L’énumération des autres points entiers admissibles confirme qu’aucun ne dépasse 230 €.

Dans un atelier, les décisions portent sur des objets indivisibles : machines à lancer, séries à produire ou équipes à affecter. Un modèle entier est préférable à une relaxation linéaire dès qu’arrondir une quantité peut violer une capacité ou dégrader le gain.

Pour une sélection de projets, une variable binaire vaut 1 si le projet est retenu et 0 sinon. Cette écriture convient lorsque la décision est tout ou rien ; une variable entière générale convient plutôt quand plusieurs unités identiques peuvent être choisies.

Avant de résoudre, on vérifie que chaque contrainte traduit bien une ressource ou une règle et que toutes les unités concordent. Une solution approchée peut suffire si un écart contrôlé est acceptable ; une méthode exacte reste nécessaire lorsqu’il faut prouver qu’aucune solution admissible n’est meilleure.

Optimisation linéaire continue. Ses variables peuvent prendre toutes les valeurs réelles autorisées. Dans l’exemple de l’atelier, elle accepte 8/3 bureaux et 8/3 étagères, tandis que le modèle entier les refuse.

Optimisation non linéaire. La différence porte sur la forme de l’objectif ou des contraintes, et non sur le caractère entier des variables. Un produit de deux variables rend le modèle non linéaire, même si ces variables sont entières.

Arrondi d’une solution continue. Arrondir n’est pas une méthode générale de résolution. Passer de 8/3 à 3 pour les deux productions demanderait 9 heures de chaque activité et créerait une solution interdite.

Modèle irréalisable. Des contraintes contradictoires peuvent ne laisser aucune solution entière. Le symptôme n’est pas un gain faible, mais l’absence de tout point admissible ; il faut alors contrôler les données ou assouplir explicitement une règle.

Modèle non borné. Si le gain peut croître sans limite tout en respectant les contraintes, aucun optimum fini n’existe. Il faut rechercher une capacité ou une borne oubliée, plutôt que demander au solveur une meilleure solution.

Écart d’intégralité. La relaxation donne une borne, pas nécessairement une décision réalisable. Dans l’atelier, elle annonce 240 €, alors que l’optimum entier vaut 230 € : l’écart absolu est 10 € et l’écart relatif à la borne est d’environ 4,17 %.

Temps de calcul. L’existence d’un modèle linéaire entier ne garantit pas une résolution rapide : la classe comprend des problèmes NP-difficiles. On resserre les bornes, ajoute des plans sécants ou accepte un écart d’optimalité annoncé lorsque la preuve exacte devient trop coûteuse.

Optimisation linéaire — Situer la relaxation continue qui fournit les bornes utilisées par les méthodes entières.

Algorithme — Revenir à la notion de procédure finie avant d’étudier la séparation et évaluation.

Polyèdre — Lire la géométrie de la région délimitée par des contraintes linéaires.