PROGRAMMATION LINEAIRE

(sujet des 5 prochaines semaines)

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_{1}, x_{2}, ... x_{n} Une fonction objective linéaire à maximiser (ou minimiser):

z = ∑_{j=1}^{n} c_{j}x_{j}

Un ensemble de contraintes linéaires: il suffit de considérer des contraintes avec la partie droite une constante: ∑ A_{i,j}x_{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

– p. 3/13

Forme canonique

• 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

Quelques définitions et cas spéciaux

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

– p. 5/13

Exemple de solution sans borne

−4x_{1} + 1x_{2} ≤ − 10

1x_{1} − 2x_{2} ≤ − 30

maximiser z = 5x_{1} − 2x_{2} parmi les solutions sont: (10, 20), (100, 200), (1000, 2000)... avec valeurs de z: 10, 100, 1000 et ainsi de suite.

Exemple de plusieurs solutions optimales

1x_{1} + 1x_{2} ≤ 10

2x_{1} + 3x_{2} ≤ 24

1x_{1} + 5x_{2} ≤ 18

maximiser z = 3x_{1} + 3x_{2} 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)

– p. 7/13

Exemple sans aucune solution réalisable

1x_{1} + 1x_{2} ≤ 20

−1x_{1} − 3x_{2} ≤ − 50

−1x_{1} + 1x_{2} ≤ 5

(En effet, on voit que la somme des deux dernières contraintes divisée par 2 est −x_{1} − x_{2} ≤ − 22.5 en contradiction avec la première.

Interprétation géométrique

• 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

– p. 9/13

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 sur ce qu’on peut exprimer en PL (forme standard et canonique):

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_{1} ≥ 5 ou x_{2} ≥ 10, x_{1} ∗ x_{2} ≤ 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.

– p. 13/13