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)

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: l₁ < = l₂, l₁ = l₂, l₁ > = l₂ (chaque l_i étant une combinaison linéaire des variables comme z) il suffit de considérer des contraintes du premier type avec l₂ 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

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)

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 ...

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.