PROGRAMMATION
LINEAIRE

Maximiser (ou minimiser) une valeur qui dépend de plusieurs variables étant donné des contraintes sur ces variables

Quelques exemples:

• stocks+entrepôts : il faut avoir assez de chaque produit pour pouvoir satisfaire aux demandes prévisibles; les entrepôts ont une capacité finie; on veut minimiser le coût.
• produits+matières de base : chaque produit nécessite certaines quantités des plusieurs matières de base; on ne peut pas en utiliser plus que l'on a; on veut maximiser le profit.

• réseaux : le flux dans chaque arête ne peut pas être supérieur à sa capacité; ce qui arrive à un noeud doit en partir; on veut minimiser le coût d'un ensemble de flux qui effectue les transferts souhaités.
• Trouver les stratégies mixtes qui donnent un équilibre dans un jeu (les supports étant donnés)

Définition générale

Un ensemble de variables: x₁, x₂, ...  x_n

Une fonction objective linéaire à maximiser (ou minimiser):

z =  n ∑ j=1  cjxj

Un ensemble de contraintes linéaires: il suffit de considérer des contraintes avec la partie droite une constante: ∑A_i,jx_j   ≤   b_i

(Chaque i donne une contrainte; par convention 1  ≤  i  ≤  m)
on écrit aussi maximiser cx avec Ax  ≤  b
chaque contrainte correspond à une ligne de la matrice A

• Chaque variable est astreinte à être
  supérieure ou égale à 0

• Une restriction qui ne change rien quant à la difficulté du problème
• Mais souvent utile

• solution réalisable; un ensemble de valeurs des variables vérifiant toutes les contraintes
• problème faisable; un problème qui possède au moins une solution réalisable
• problèmes sans borne finie sur la fonction objective: c'est-à-dire le maximum de la fonction objective (sur les solutions réalisables) n'existe pas.
• problème possédant plusieurs solutions optimales; (plusieurs ensembles de valeurs des variables donnant la même valeur optimale de la fonction objective).

parmi les solutions sont: (10,20), (100,200), (1000,2000)... avec valeurs de z: 10, 100, 1000 et ainsi de suite.

parmi les solutions sont: (10,0), (8,2) avec valeur de z: 30.

S'il existe 2 solutions optimales, il en existe un nombre infini:
par exemple (9,1), (9.5,0.5)

(En effet, on voit que la somme des deux dernières contraintes divisée par 2 est -x₁-x₂  ≤  -22.5 en contradiction avec la première.

• Les valeurs des n variables sont interprétées comme coordonnées d'un point en n dimensions
• Chaque contrainte définit un hyperplan dans cet espace tel que chaque solution réalisable doit être à la même coté (ou sur) l'hyperplan
• polytope (+intérieur) de solutions réalisables (peut-être de dimension inférieure à n);
• convexité: La ligne droite reliant deux solutions réalisables consiste en d'autres solutions réalisables
• si le polytope est fini, la fonction objective est bornée

Solutions de base

Une solution donnée par la solution de n des équations correspondant aux contraintes
(c'est-à-dire les équations obtenues en remplacant ≤ par =)
(à noter que si les n équations ne sont pas indépendantes la solution n'existe pas et elles ne donnent pas de solution de base)

ou Un sommet du polytope

théorème : si la fonction objective est bornée, elle prend sa valeur optimale à une solution de base

Donc un algorithme possible

• calculer chaque solution de base;
• vérifier qu'elle est réalisable;
• si oui calculer la fonction objective;
• prendre le maximum des valeurs calculées.

Mais  ca serait très très lent ...

Limitations

Il existe des types de contraintes réelles qu'on ne peut pas exprimer (directement) par des contraintes linéaires.

• impossible de contraindre les variables à des valeurs entières;
  la ``programmation linéaire en nombres entiers'' a ses propres méthodes
• contraintes non-linéaires: impossible! (p.ex x₁ ≥ 5 ou x₂ ≥ 10, x₁*x₂ ≤ 20 ...)

• Un prix qui change selon la quantité achetée?
  

  • Réduction au delà d'un seuil donné (rabais pour grosse commande): impossible à traiter...
  • Hausse au delà d'un seuil donné (doit changer à un autre fournisseur): traiter avec une variable pour la quantité achetée à chaque prix?
• contraintes avec < ou > (donc interdisant l'égalité): cas peu probable pour les problèmes réels.

Les problèmes qui ne sont pas en forme standard canonique (variables négatives, contraintes ≥ ou =) sont facilement réformulés.