Programmation linéaire 101

Programmation linéaire

En Recherche Opérationnelle (RO) telle que la programmation linéaire, modéliser un problème consiste à identifier:

• les variables intrinsèques (inconnues)
• les différentes contraintes auxquelles sont soumises ces variables
• l’objectif visé (optimisation) appelé fonction Objectif.

Dans un problème de programmation linéaire (PL) les contraintes et l’objectif sont des fonctions linéaires des variables. On parle aussi de programme linéaire. Ils se notent de la façon suivante (forme canonique pure):

Maximize	cT x
Subject to	Ax  ≤  b
	x ≥ 0

où x est le vecteur de variables (x₁, …, x_n), c et b sont des vecteurs de coefficients, A une matrice de coefficient de taille m*n, et ^T la transposée (vecteur colonne au lieu de vecteur ligne par exemple). Les inégalités Ax ≤ b et x ≥ 0 (positivité des variables) sont des contraintes. Le domaine de définition formé est un polytope convexe. Le programme linéaire est dit sous forme standard s’il s’agit de contraintes égalités.

Positivité des variables. Si dans le contexte,  nous avons une borne inférieure non nulle x ≥ k, il suffit de poser y = x-k et y ≥ 0. S’il n’y a pas de borne inférieure, on peut toujours poser x = y-z avec y ≥ 0 et z ≥ 0.

Tout problème standard peut être écrit de façon canonique et réciproquement. La contrainte égalité se décompose en deux contraintes inégalités. Une contrainte inégalité s’écrit sous forme d’égalité en rajoutant une variable d’écart.

Une solution x’ est dite réalisable si elle satisfait toutes les contraintes.

Pour résumer, la programmation linéaire est composé de quatre éléments :

1. des variables de décision;
2. une fonction objectif;
3. des contraintes de ressources;
4. des contraintes de « type ».

Pour formuler un problème à partir d’un cahier des charges, il faut suivre les quatre points précédents dans l’ordre.

Exemple. Soit une usine qui produit deux types de clavier rapportant 50£ et 70£ l’unité. Pour fabriquer une unité de type 1, il faut 40 min de main-d’œuvre et 20 min d’usinage. Pour fabriquer une unité de type 2, il faut 30 min de main d’œuvre et 30 min d’usinage. La main-d’œuvre travaille 6h par jour tandis que la machine est disponible 8h par jour. Combien d’unité de chaque type doit-on produire pour maximiser les bénéfices ?

Programme linéaire. Ce problème se modélise selon le PL suivant :

maximum 50x + 70y
S.C 40x +30y ≤ 360
20x + 30y ≤ 480
x,y≥ 0

Solutions possibles

Seuls quatre cas peuvent se présenter :

1. Si le domaine de définition est nul, le problème n’est pas réalisable;
2. sinon : l’optimum n’existe pas, le problème est non borné;
3. ou : le problème possède une solution optimale unique coïncidant avec un point extrême (un sommet) du domaine de définition;
4. ou : le problème possède une infinité de solutions formant une face ou une arête du domaine de définition.