optimisation linéaire

Un atelier fabrique des tables et des chaises avec des ressources limitées. Chaque objet rapporte une certaine somme, mais consomme du temps et de la matière. Il faut choisir combien en produire pour obtenir le meilleur gain sans dépasser aucune ressource.

L'optimisation linéaire traduit ce choix par des variables, une quantité à maximiser ou minimiser et des contraintes. Tout est linéaire : doubler une production double sa contribution et sa consommation. En deux dimensions, les choix autorisés forment une zone polygonale ; comparer ses coins suffit souvent à trouver une meilleure solution.

Un problème d'optimisation linéaire cherche à maximiser ou minimiser une fonction objectif linéaire sous des contraintes linéaires. Le vecteur x regroupe les variables de décision, le vecteur c leurs coefficients dans l'objectif, la matrice A leurs coefficients dans les contraintes et le vecteur b les limites disponibles. Une forme standard de maximisation s'écrit : Les égalités et les variables de signe libre se ramènent à des formes équivalentes, mais ne disparaissent pas du modèle : elles doivent être déclarées explicitement.

L'ensemble des valeurs de x qui satisfont simultanément toutes les contraintes est la région admissible. C'est un ensemble convexe : en dimension deux, une région polygonale éventuellement vide ou non bornée ; en dimension trois, un polyèdre ; en dimension quelconque, un polyèdre convexe au sens général. Si un optimum fini existe et si la région admissible possède des sommets, au moins un sommet est optimal. Plusieurs sommets, voire toute une arête, peuvent toutefois donner la même valeur.

L'expression programmation linéaire, introduite par le mathématicien américain George Dantzig, est synonyme d'optimisation linéaire. Ici, « programmation » désigne l'organisation d'un plan de décision et non l'écriture d'un programme informatique. De nombreux modèles de recherche opérationnelle relèvent de ce cadre.

Un atelier choisit le nombre x de tables et le nombre y de chaises à fabriquer. Une table apporte 30 unités de gain et une chaise 20. Les capacités imposent x + y ≤ 6 et 2x + y ≤ 8, avec x ≥ 0 et y ≥ 0. L'objectif est donc de maximiser le gain z = 30x + 20y.

1. Traçons les droites frontières x + y = 6 et 2x + y = 8, puis gardons les points qui respectent les quatre inégalités.

2. Les quatre sommets de la région admissible sont (0, 0), (4, 0), (2, 4) et (0, 6). Le point (2, 4) vient de la résolution simultanée des deux égalités : leur soustraction donne x = 2, puis y = 4.

3. La représentation du polygone montre les quatre choix extrêmes et la droite d'objectif qui atteint sa meilleure valeur au sommet (2, 4).

4. Évaluons l'objectif aux sommets : La valeur maximale est 140 unités de gain, obtenue avec 2 tables et 4 chaises.

5. Contrôlons la solution : 2 + 4 = 6 et 2 × 2 + 4 = 8. Les deux capacités sont exactement saturées, et le gain vaut bien 30 × 2 + 20 × 4 = 140.

Planifier une production. On choisit les quantités de chaque produit, puis on traduit les heures, les matières ou les capacités en contraintes. Ce modèle convient lorsque les consommations et les gains sont proportionnels ; sinon, un modèle non linéaire est préférable.

Composer un mélange. Les variables représentent les quantités d'ingrédients, tandis que les contraintes imposent un coût, un volume ou une composition. Si les ingrédients doivent être pris par lots indivisibles, l'optimisation linéaire en nombres entiers remplace le modèle continu.

Répartir des ressources. On maximise un résultat ou on minimise un coût en respectant les disponibilités. Le premier contrôle consiste à vérifier que chaque relation est bien additive et que toutes les limites importantes figurent dans le modèle.

Programmation linéaire et programmation informatique. La première construit un modèle mathématique de décision ; la seconde écrit des instructions exécutées par une machine. Le calcul d'un plan de production sous contraintes relève de la première, même si un logiciel sert ensuite à le résoudre.

Optimisation linéaire et optimisation non linéaire. Dans un modèle linéaire, variables, objectif et contraintes n'interviennent qu'au premier degré et ne sont pas multipliés entre eux. Une contrainte xy ≤ 8 ou un objectif x² + y sort donc du cadre linéaire.

Optimisation linéaire continue et en nombres entiers. Le modèle continu autorise par exemple x = 2,5 ; le modèle entier impose des valeurs entières à certaines variables. Pour compter des véhicules indivisibles, une solution fractionnaire distingue immédiatement les deux cadres.

Région vide. Des contraintes incompatibles ne laissent aucun point admissible. Si un modèle exige à la fois x ≥ 5 et x ≤ 3, aucun optimum n'existe ; il faut corriger les données ou assouplir une contrainte justifiée.

Objectif non borné. Une région admissible peut s'étendre à l'infini dans une direction qui améliore sans cesse l'objectif. L'absence de maximum fini n'est pas une très grande solution : elle signale qu'une limite manque ou que le modèle permet réellement une croissance illimitée.

Optimum non unique. Si une droite d'objectif est parallèle à une arête optimale, tous les points de cette arête ont la même valeur. Deux sommets ex æquo ne suffisent donc pas à conclure qu'il n'existe que deux solutions optimales.

Sommet absent ou dégénéré. L'affirmation « l'optimum est sur un sommet » suppose notamment qu'un optimum fini existe et que la région possède des sommets. Sur une droite admissible entière avec un objectif constant, chaque point est optimal sans qu'aucun sommet n'existe ; il faut alors décrire l'ensemble des solutions.

La programmation linéaire — Approfondir la mise en équations et les méthodes de résolution d'un modèle linéaire.

La programmation linéaire en nombres entiers — Voir ce qui change lorsque certaines décisions doivent rester indivisibles.

concept de convexité — Relier les combinaisons de solutions admissibles à la géométrie convexe de la région.

polyèdre — Passer du polygone en dimension deux à l'intersection de demi-espaces en dimension supérieure.