Optimisation linéaire

Optimisation linéaire


Ce cours d'optimisation linéaire est destiné à des étudiants en Mathématiques apliquées ou Informatique, niveau troisième année universitaire. Il est basé essentiellement sur la référence ci-après :
: Hédi Nabli, ''Recherche Opérationnelle : Algorithme du Simplexe et ses Applications'', Centre de Publication Universitaire, Tunisie (2006)
Ce livre propose entre autres
  1. une nouvelle méthode de recherche d'une base réalisable initiale pour l'algorithme du simplexe. Cette technique ne fait pas intervenir les variables artificielles. De plus il est souvent possible d'aboutir, en une seule itération, à une base réalisable.
  2. Grâce aux tableaux formels, une nouvelle alternative, autre que l'algorithme dual-simplexe, est proposée.
  3. Pour les problèmes de transport, un algorithme récursif pour la détermination des éléments d'un tableau de transport est mis en oeuvre.

Dans ce document, les résultats mathématiques sont donnés sans démonstration. Pour plus de détails, on peut consulter la référence ci-dessus.

I Programmation linéaire

II Méthode graphique

III Méthode des sommets

IV Méthode du simplexe

V Algorithme du simplexe standard

VI Dualité en programmation linéaire


Vous trouverez ici une version pdf : docquadratic.pdf
Je remercie vivement Sophie Lemaire et Bernadette Perrin-Riou, enseignants-chercheurs à l'université de Paris-Sud, pour leur aide précieuse à réaliser ce document interactif.

I Programmation linéaire

Optimisation linéaire → I Programmation linéaire

Un programme linéaire est un problème dans lequel on est amené à maximiser (ou minimiser) une application linéaire, appelée fonction d'objectif ou fonction économique, sur un ensemble d'équations et/ou d'inéquations linéaires, dites contraintes. Autrement dit, la programmation linéaire est une branche des mathématiques qui a pour but de résoudre des problèmes d'optimisation linéaire de type
{max(oumin)[Z(x 1,,x p)= j=1 pc jx j] j=1 pa ijx j(et/ou =) b i, pouri=1,,m.
Les coefficients c j,a ij et b i sont des réels fixés et les x j sont des variables réelles. Les contraintes d'inégalités éventuelles sont toutes larges et non strictes. Il se peut qu'une contrainte d'inégalité soit de type '' geq''. En multipliant chaque inégalité de type '' geq'' par (1), on peut supposer que toutes les contraintes d'inégalité sont de type '' leq''.

I-1 Généralités

I-2 Exemple

I-3 Domaine réalisable

I-4 Présentation des méthodes

Optimisation linéaire → I Programmation linéaire

I-1 Généralités


Dans le contexte de la programmation linéaire, le terme programmation désigne l'organisation des calculs et non la réalisation d'un programme informatique. Du point de vue des applications, l'optimisation linéaire est d'une grande portée. Elle s'applique à des problèmes très variés qui sont issus de l'économie, de l'ingénierie, de la physique ou encore des modèles probabilistes. Dans ce cadre, on peut citer par exemple, les problèmes de type gestion de stock, gestion de production, transport de marchandise, affectation du personnel, systèmes industriels, réseaux de communication, etc. Pour les modèles de programmation linéaire, on est souvent amené à maximiser un gain ou minimiser un coût. Ceci explique d'ailleurs pourquoi la fonction à maximiser s'appelle fonction d'objectif ou économique.

I-2 Exemple


Exemple

Une usine fabrique deux produits (A) et (B) à l'aide des matières premières I, II et III. Le fonctionnement de l'usine est comme suit :
  • 1 unité du produit (A) nécessite 2 unités de I et 1 unité de II.
  • 1 unité du produit (B) nécessite 1 unité de I, 2 unités de II et 1 unité de III.
On suppose que l'usine dispose des matières premières I, II et III en quantités respectives 8, 7 et 3. Le profit dû à la fabrication d'une unité du produit (A) (resp. (B)) est égal à 4 (resp. 5) Dinars Tunisiens (DT). L'objectif étant de maximiser le profit tout en respectant les contraintes sur la matière première.

Formulation mathématique

Si on désigne respectivement par x 1 et x 2 les quantités vendues du produit (A) et (B), le gain total vaut
Z(x 1,x 2)=4x 1+5x 2
D'autre part, la disponibilité en matières premières revient à exiger des quantités, utilisées pour la fabrication de x 1 et x 2, qui soient inférieures aux quantités disponibles. Ces contraintes s'expriment par les inégalités suivantes :
{2x 1+x 2 8 x 1+2x 2 7 x 2 3
Bien entendu, les variables x 1 et x 2 doivent être positives. En conclusion, le problème de maximisation du profit se traduit mathématiquement par un programme linéaire qui s'écrit sous la forme :
{max[Z(x 1,x 2)= 4x 1+5x 2] 2x 1+x 2 8 x 1+2x 2 7 x 2 3 x 10,x 20

I-3 Domaine réalisable

Optimisation linéaireI Programmation linéaire → I-3 Domaine réalisable

Pour un problème d'optimisation linéaire, tout point qui vérifie l'ensemble des contraintes s'appelle point réalisable ou admissible. L'ensemble de tous les points réalisables s'appelle domaine réalisable. Il est facile de vérifier que le domaine réalisable d'un programme linéaire est convexe. On rappelle qu'un ensemble est dit convexe si à chaque fois qu'il contient deux points x et y, il contient le segment joignant x et y. Ce segment est souvent noté par [x,y] et il est défini par
[x,y]={λx+(1λ)yλ[0,1]}
Un point est dit optimal s'il est admissible et s'il réalise l'optimum de la fonction d'objectif sur le domaine réalisable. Par exemple, pour le problème
{max[Z(x 1,x 2)=x 1x 2] x 1+x 21 x 20,
tout point réalisable (x 1,x 2) vérifie
Z(x 1,x 2)=x 1x 2x 1x 1+x 21.
D'autre part, le point (1,0) est réalisable et on a Z(1,0)=1. Donc, la solution réalisable (1,0) est optimale et la valeur maximale de Z sur le domaine réalisable est Z(1,0)=1.
Optimisation linéaireI Programmation linéaire → I-3 Domaine réalisable

I-4 Présentation des méthodes

Optimisation linéaireI Programmation linéaire → I-4 Présentation des méthodes

Nous allons présenter des techniques qui permettent de résoudre les programmes linéaires que l'on convient désormais de noter (PL). Diverses méthodes ont été proposées dans la littérature :
  • La méthode graphique : l'utilisation de cette méthode est restreinte aux (PL) ayant un nombre de variables au plus égal à 3.
  • La méthode des sommets : le nombre de sommets étant prohibitif, cette méthode est très coûteuse en temps de calcul.
  • La méthode du simplexe : algorithme itératif mis au point par George Dantzig en 1951.
Optimisation linéaireI Programmation linéaire → I-4 Présentation des méthodes

II Méthode graphique

Optimisation linéaire → II Méthode graphique

Nous allons décrire la méthode graphique à travers trois exemples représentatifs, ayant chacun deux variables structurelles. Le premier admet une et une seule solution optimale. Le deuxième admet une infinité de solutions optimales. Par contre, le troisième exemple n'admet aucune solution optimale.
La résolution d'un (PL) par la méthode graphique se fait selon une démarche commune, celle-ci peut être résumée en quatre directives :
  1. Schématiser le domaine réalisable dans un repère orthonormé.
  2. Dans le même repère, représenter l'hyperplan Δ 0:Z(x)=0. Noter que tout hyperplan Δ r d'équation Z(x)=r, r, est parallèle à Δ 0.
  3. Si le (PL) considéré est de type maximisation ( resp. minimisation), indiquer, par une flèche, le sens de déplacement parallèle de Δ r qui fait augmenter ( resp. diminuer) r.
  4. Déterminer la droite Δ r max la plus éloignée (dans le sens de la flèche) de Δ 0 et qui coupe le domaine réalisable . Tout point de Δ r max est une solution optimale. Si une telle droite Δ r max n'existe pas, cela veut dire que l'optimum est infini.
Appliquons ce principe général sur l'exemple 1 défini dans le paragraphe précédent.

II-1 Exemple 1

II-2 Exemple 2

II-3 Exemple 3

II-4 Remarque

II-5 Exercice

Optimisation linéaire → II Méthode graphique

II-1 Exemple 1


Reprenons l'exemple
{max[Z(x 1,x 2) =4x 1+5x 2] 2x 1+x 2 8 x 1+2x 2 7 x 2 3 x 10 x 20
Représentation graphique pour l'exemple 1

Le domaine réalisable est schématisé en gris sur la Figure. Toute droite Δ r d'équation Z(x 1,x 2)=r, où r est un réel fixé, est parallèle à la droite Δ 0 : Z(x 1,x 2)=0. On constate aussi que tout déplacement parallèle de Δ r dans le sens de la flèche (voir dessin ci-après) fait augmenter r. Donc maximiser la fonction Z, tout en satisfaisant aux contraintes du problème, revient à chercher la droite Δ r la plus éloignée (dans le sens de la flèche) de Δ 0 et qui coupe le domaine réalisable. Du point de vue graphique, il s'agit de la droite Δ r max passant par le point (3,2) et parallèle à Δ 0. Ainsi, on peut conclure que le point (3,2) est la seule solution optimale qui donne une valeur maximale de la fonction d'objectif égale à Z(3,2)=22. Autrement dit, le meilleur profit vaut 22DT obtenu en fabriquant 3 unités du produit (A) et 2 unités du produit (B).

II-2 Exemple 2


On considère le (PL) suivant :
{max[Z(x 1,x 2) =6x 1+15x 2] 2x 1x 2 4 2x 1+5x 2 4 x 10,x 20
Représentation graphique pour l'Exemple 2

Le domaine réalisable est la partie non bornée représentée partiellement en gris sur la Figure. Tout déplacement parallèle de Δ r:Z(x 1,x 2)=r dans le sens de la flèche (voir dessin ci-après) fait augmenter r. Donc tout point de la demi-droite [A,B) est optimal et la valeur maximale de Z vaut Z(A)=Z(3,2)=12 (voir dessin ci-après).

II-3 Exemple 3


On considère maintenant le (PL) suivant :
{max[Z(x 1,x 2) =x 1+x 2] x 1+x 2 1 x 1+2x 2 4 x 10,x 20
Représentation graphique pour l'Exemple 3

Le domaine réalisable associé à ce (PL) est la partie non bornée représentée partiellement en gris dans la Figure. Dans le graphique, on observe que toute droite Δ r d'équation Z(x 1,x 2)=r, avec r0, coupe le domaine réalisable. Donc, supZ=+ et par conséquent, le problème n'admet aucune solution optimale (voir dessin ci-dessous).

II-4 Remarque

Tous les exemples traités ci-dessus possèdent deux variables structurelles x 1 et x 2. Pour des (PL) en dimension 3, le raisonnement pour la méthode graphique reste le même. La seule différence est que l'ensemble des points (x 1,x 2,x 3) vérifiant une contrainte
a 1x 1+a 2x 2+a 3x 3b
se représente par un demi-espace qui est délimité par le plan d'équation
a 1x 1+a 2x 2+a 3x 3=b.

II-5 Exercice

Exercice


A venir

III Méthode des sommets

Optimisation linéaire → III Méthode des sommets

La méthode des sommetsest simple, elle se base sur la résolution des systèmes linéaires de Cramer. Cependant, elle est dans la pratique inexploitable car le nombre de systèmes à résoudre est en général trop important.
Néanmoins, la méthode des sommets est d'une utilité incontestable : la recherche de l'optimum éventuel sur tout le domaine réalisable se ramène au calcul de l'optimum de la fonction d'objectif restreinte à un sous ensemble fini. Ce résultat sera l'un des outils clé de la méthode du simplexe.

Définition

Pour toute contrainte d'inégalité a ijx jb i ( resp. contrainte de positivité x i0) d'un (PL) donné, l'hyperplan associé a ijx jb i ( resp. x i=0) s'appelle hyperplan frontière.

III-1 Résultat préliminaire

III-2 Mise en oeuvre

III-3 Champ d'application

Optimisation linéaire → III Méthode des sommets

III-1 Résultat préliminaire

Optimisation linéaireIII Méthode des sommets → III-1 Résultat préliminaire

Considérons un (PL) à p variables réelles. Un point A du domaine réalisable est appelé sommet, s'il existe p hyperplans frontières dont l'intersection est réduite à A.

Théorème

Soit Z: p une application linéaire et un polyèdre de p. Si Z admet son optimum global en un point de , il est aussi atteint en un sommet de .

Sans nul doute, l'intérêt de ce théorème est immédiat :
L'optimum (que ce soit maximum ou minimum) d'un (PL), lorsqu'il existe, peut toujours être réalisé sur un sommet.

La méthode des sommets pour la résolution d'un (PL), consiste donc à :
  • déterminer tous les sommets du domaine réalisable,
  • puis calculer la valeur de Z en chacun de ces sommets.
Le sommet doté de la meilleure valeur de Z serait une solution optimale. Une chose reste à vérifier pour l'application de cette méthode : s'assurer tout d'abord que le (PL) considéré admet bien une solution ( i.e. l'optimum est fini). Cette condition est souvent difficile à vérifier. Néanmoins, lorsque le domaine réalisable est borné, et par suite compact, l'existence d'une solution optimale est certaine.

Exercice

Application 1 : Problème de trains

Exercice

Application 2 : Production optimale
Optimisation linéaireIII Méthode des sommets → III-1 Résultat préliminaire

III-2 Mise en oeuvre

Optimisation linéaireIII Méthode des sommets → III-2 Mise en oeuvre

Appliquons la méthode des sommets aux trois exemples précédents. Pour l'exemple , les sommets du domaine réalisable sont les points (voir Figure )
(0,0);(4,0);(1,3);(3,2) et (0,3).
La valeur de la fonction d'objectif Z en chacun de ces sommets est
Z(0,0)=0;Z(4,0)=16;Z(1,3)=19
Z(3,2)=22;Z(0,3)=15.
Il est clair que la plus grande valeur de Z en ces sommets est atteinte au point (3,2) et vaut Z(3,2)=22. Pour l'exemple , d'après le graphique, les seuls sommets sont (2,0) et (3,2). De plus, on a
Z(2,0)=12<Z(3,2)=12,
ce qui entraîne que (3,2) est une solution optimale. Concernant l'exemple , les sommets du domaine réalisable sont les points (0,0), (0,1) et (2,3). La valeur de Z en chacun de ces points vaut
Z(0,0)=0,Z(0,1)=1,Z(2,3)=5.0
Cependant, on ne peut affirmer que (2,3) est une solution optimale, puisqu'on a déjà vu que la fonction d'objectif n'est pas bornée sur son domaine réalisable.

Exercice

Méthode graphique générale
Optimisation linéaireIII Méthode des sommets → III-2 Mise en oeuvre

III-3 Champ d'application

Optimisation linéaireIII Méthode des sommets → III-3 Champ d'application

La méthode des sommets peut s'appliquer même pour des (PL) ayant un nombre de variables structurelles strictement supérieur à 3. Afin de déterminer un sommet, on choisit p hyperplans ( p étant le nombre de variables) parmi les n contraintes du domaine réalisable (y compris les contraintes de positivité : x i0). On obtient ainsi un système linéaire d'ordre p que l'on résoud. Si ce système admet une et une seule solution A, on vérifie si A satisfait les (np) contraintes restantes. Dans ce cas, A est un sommet, sinon le choix considéré de ces p équations linéaires ne permet pas d'avoir un sommet et pour ce faire, on effectue un autre choix de p hyperplans frontières parmi les n contraintes. Dans le but d'obtenir tous les sommets, il va falloir balayer tous les choix possibles dont le nombre est égal à ( p n)=n!p!(np)!. Chaque choix qui aboutit à un système de Cramer dont la solution est réalisable permet d'obtenir un sommet. Enfin, la solution du problème considéré est obtenue en prenant l'optimum de la fonction d'objectif sur tous les sommets.

Remarque

Dans la pratique, la méthode des sommets est en fait très coûteuse en temps de calcul. D'une part, la détermination d'un sommet exige la résolution d'un système linéaire de Cramer d'ordre p dont la solution doit satisfaire les contraintes restantes. D'autre part, le nombre ( p n) est en général très important. A titre indicatif, on a ( 10 25)=3.268.760! Par ailleurs, cette méthode n'est applicable que lorsqu'on est certain que le (PL) admet une solution optimale, ce qui est a priori difficile à vérifier.

Exercice


Résolution par la méthode des sommets : A venir
Optimisation linéaireIII Méthode des sommets → III-3 Champ d'application

IV Méthode du simplexe

Optimisation linéaire → IV Méthode du simplexe

Dans ce chapitre, nous allons étudier une méthode qui évite de parcourir tous les sommets. Plus précisément, le passage d'un sommet à un autre se fait en améliorant la valeur de la fonction à optimiser. De plus, elle fournit un test qui permet d'affirmer le cas échéant que le problème n'admette pas de solution. Nous verrons que les résultats concernant les problèmes de type maximisation, comparés à ceux relatifs aux problèmes de minimisation, sont très similaires.

IV-1 Forme canonique

IV-2 Forme standard

IV-3 Relation entre la frome canonique et standard

IV-4 Notion de base réalisable

IV-5 Algorithme du simplexe

Optimisation linéaire → IV Méthode du simplexe

IV-1 Forme canonique

Optimisation linéaireIV Méthode du simplexe → IV-1 Forme canonique

On convient de dire qu'un vecteur u est inférieur à un vecteur v, et on écrit uv, si pour tout i, on a u iv i. Ici, le terme u i désigne la i-ième composante du vecteur u. Nous mettons en garde sur le fait que
la négation de uv n'est pas u>v.
En effet, l'inégalité u>v traduit la propriété u i>v i pour toute composante i. Par contre, la négation de uv, que l'on convient de noter u¬v, exprime que l'inégalité u i>v i ait lieu pour au moins une composante i.

Définition

Une forme canonique ( resp. forme standard) est un (PL) où toutes les contraintes sont des inégalités ( resp. égalités) et les variables sont astreintes à être positives.

On a déjà expliqué qu'on peut supposer et sans perte de généralité, que les contraintes d'inégalité sont toutes de type '' leq''. Par conséquent, on peut affirmer que tout (PL) sous forme canonique s'écrit sous la forme suivante :
{max(oumin)[Z(x)=c *x] Axb x0 p
c p, A, matrice (m,p) et b m sont fixés.
Le vecteur x a p composantes réelles x i et désigne l'opérateur transposé. Les inégalités
x i0;i=1,,p
(i.e. x0 p) s'appellent contraintes de positivité. Désormais, on décide de noter un (PL) sous forme canonique par (FC). Remarquer que les trois exemples précédents sont tous écrits sous forme canonique.
Optimisation linéaireIV Méthode du simplexe → IV-1 Forme canonique

IV-2 Forme standard

Optimisation linéaireIV Méthode du simplexe → IV-2 Forme standard

La mise sous forme standard d'un (PL) quelconque consiste à transformer les contraintes d'inégalités (mise à part les contraintes de positivité) en égalité tout en imposant aux variables d'être positives. Pour ce faire, on procède comme suit :
  • A chaque contrainte de type '' leq'' (resp. '' geq''), ajouter (resp. retrancher) une variable tout en lui imposant d'être positive. Celle-ci s'appelle variable d'écart.
  • Remplacer chaque variable x i sans restriction de signe par la différence de deux variables positives : x i=x i +x i avec x i +0 et x i 0.
  • Si une variable x i est négative, effectuer le changement de variable x i=x i.


Soit la forme canonique (FC) suivante :
max Z=
sous les contraintes
geq
geq
geq
geq
x 1 geq 0, x 2 geq 0

Les données de la forme standard de cette (FC) sont :
M= [], b = [] c * = (,0 0 0 0)

Exemple

Mettre sous forme standard le (PL) suivant :
{max[Z(x 1,x 2,x 3) =2x 1x 2+5x 3] x 12x 2 =3 x 1x 3 1 x 2+x 3 4 x 10,x 20
On peut dire à juste titre que ce (PL) n'est pas une forme canonique car la première contrainte est une égalité et la troisième variable x 3 n'est pas astreinte à être positive. Pour la mise sous forme standard, la première contrainte, qui est déjà une égalité, reste inchangée. Pour la deuxième, on lui retranche une variable positive x 4, elle devient
x 1x 3x 4=1.
Quant à la troisième contrainte, on lui ajoute une variable positive x 5 pour devenir
x 2+x 3+x 5=4.
Concernant la variable x 3 qui est sans restriction de signe, elle est remplacée par x 3 x3, avec x 3 +0 et x 3 0. En conclusion, la forme standard associée à ce (PL) s'écrit
{max[Z(x)=2x 1x 2+5x 3 +5x 3 ] x 12x 2= 3 x 1x 3 ++x 3 x 4= 1 x 2+x 3 +x 3 +x 5= 4 x=(x 1,x 2,x 3 +,x 3 ,x 4,x 5)0 6.
Les variables du (PL) initial s'appellent variables de décision, celles de la forme standard associée s'appellent variables structurelles.
Optimisation linéaireIV Méthode du simplexe → IV-2 Forme standard

IV-3 Relation entre la frome canonique et standard

Optimisation linéaireIV Méthode du simplexe → IV-3 Relation entre la frome canonique et standard

L'écriture d'un (PL) sous forme standard est introduite tout simplement parce que l'algorithme du simplexe ne s'applique qu'aux formes standards. En d'autres termes,
pour résoudre un (PL) par le simplexe, il faut tout d'abord l'écrire sous forme standard.
Etant donné qu'on résoud le (PL) proprement dit et non la forme standard associée, la question naturelle qu'on se pose est de savoir comment retrouver une solution optimale du (PL) de départ à partir d'une solution optimale de sa forme standard. Le théorème suivant établit le lien entre une solution optimale d'un (PL) et celle de sa forme standard, et on se limite au cas où le (PL) considéré est une (FC).

Théorème

v est une solution optimale de (FC) si et seulement si (v bAv) est une solution optimale de la forme standard associée. De plus, on a
Z(v)=Z˜(v bAv)

Ce théorème se généralise bien évidemment pour tout (PL) quelque soit son type d'écriture. A titre d'illustration, pour l'Exemple qui n'est pas sous forme canonique, si (v 1,v 2,v 3,v 4,v 5,v 6) est une solution optimale de la forme standard associée, compte tenu des variables d'écarts et du changement de variable considérés, on peut dire que (v 1,v 2,v 3v 4) est une solution optimale du (PL) initial.

Exercice


Forme standard : à venir
Optimisation linéaireIV Méthode du simplexe → IV-3 Relation entre la frome canonique et standard

IV-4 Notion de base réalisable

Optimisation linéaireIV Méthode du simplexe → IV-4 Notion de base réalisable

Désormais, on note tout (PL) écrit sous forme standard par (FS). Par définition, l'écriture matricielle d'un problème (FS) possède la forme suivante :
(FS){max(oumin)[Z(y)=c *y] My=b y0 n
c n,MM m,n et b m sont fixés.
La matrice M contient toujours plus de colonnes que de lignes (i.e. n>m) vu que le nombre de variables structurelles n (variables de décision + variables d'écarts + variables dûes aux variables sans restriction de signe) dépasse le nombre de contraintes m. Sans perte de généralité, on suppose que la matrice M est de rang m. Sinon,
  1. ou bien il y a une (ou plusieurs) équation qui est combinaison linéaire des autres équations, qu'il faut alors enlever,
  2. ou bien le système est incompatible et dans ce cas le système linéaire My=b n'admet aucune solution.

IV-4-1 Système de base

IV-4-2 Optimalité et base réalisable

IV-4-3 Base dégénérée

Optimisation linéaireIV Méthode du simplexe → IV-4 Notion de base réalisable

IV-4-1 Système de base


Notons par M i la iieme colonne de M. Le vecteur colonne My s'écrit alors
My= i=1 ny iM i
y i est iieme composante de y. On appelle système de variables de base tout ensemble de m variables distinctes y i, iJ, prises parmi y 1,,y n, telles que le déterminant des vecteurs M i, iJ est différent de zéro. On rappelle que l'entier m désigne le nombre de contraintes d'égalités qui apparaissent dans (FS). La matrice carrée formée par les m colonnes M i, iJ, s'appelle base et les variables y i, iJ, s'appellent variables hors base. Autrement dit,
une base B du problème (FS) n'est autre qu'une sous matrice carrée de M d'ordre m et inversible.
Pour mieux visualiser une telle base B, on effectue des permutations de colonnes de sorte que la base B apparaisse sur les m premières colonnes de M. Ainsi, on met M sous la forme suivante :
M=[BN],
B=(M i,iJ)GL m() et N=(M i,iJ)M m,nm.
Les variables y i, i=1,,n, peuvent aussi être classées selon B et N :
y=( y N y B),y B=(y i,iJ) et y N=(y i,iJ).
Désormais, l'ensemble J des indices de base sera noté par J B et son complémentaire par J N. En respectant cette partition, le système My=b vérifie :
My=b[BN](y B )By B+Ny N=b
y B=B 1bB 1Ny N.
Par suite, l'ensemble des solutions dans n du système linéaire My=b est égal à
{y nMy=b}=(B 1bB 1Ny N y N)y N nm}.
Parmi les solutions de ce système, nous distinguons les solutions dites de base pour lesquelles y N=0 N (on écrit 0 N à la place de 0 R nm pour dire que les variables hors base sont nulles). Une telle solution existe et elle vaut
y=(B 1b 0 N)
Cette solution de base est réalisable ( i.e. elle vérifie les contraintes My=b et y0 n) si et seulement si
B 1b0 B.
Dans ce cas, on dit que la base B est réalisable.
Noter que toute solution de base réalisable admet (nm) composantes nulles relatives aux variables hors base et que les autres composantes vérifient un système de Cramer d'ordre m.

IV-4-2 Optimalité et base réalisable

Optimisation linéaireIV Méthode du simplexeIV-4 Notion de base réalisable → IV-4-2 Optimalité et base réalisable

Par analogie au Théorème , nous allons établir que lorsque (FS) admet une solution, on peut toujours chercher une solution optimale parmi les solutions de base réalisable.

Théorème

Si un problème (FS) admet un optimum global, il existe toujours une solution optimale qui est une solution de base réalisable.

Remarque

Tout sommet du domaine réalisable
𝒴={yMy=b,y0 n}
est une solution de base réalisable, la réciproque est également vraie. Les sommets de 𝒴 correspondent donc aux solutions de base réalisable. De ce fait, l'algorithme du simplexe ne s'intéresse qu'aux solutions de type
y=(B 1b 0 N)
avec B 1b0 B. Ces solutions de base réalisable sont bien évidemment en nombre fini.
Optimisation linéaireIV Méthode du simplexeIV-4 Notion de base réalisable → IV-4-2 Optimalité et base réalisable

IV-4-3 Base dégénérée


Une solution de base réalisable y=(B 1b 0 N) est dite dégénérée, si en plus des (nm) composantes nulles relatives à 0 N, il existe une composante du vecteur B 1b qui est nulle. Elle est non dégénérée dans le cas où toutes les composantes de B 1b sont non nulles et par suite strictement positives. De même, on dit qu'une base réalisable est dégénérée si la solution de base associée est dégénérée. Il est intéressant de noter qu'un point dégénéré est solution de plusieurs bases réalisables. En effet, tout vecteur colonne u=B 1b relatif à une base dégénérée B admet au moins une coordonnée u i 0, i 0J B, qui est nulle. En considérant que B=(M i,iJ B), on obtient
u=B 1bBu=b iJ Bu iM i=b
iJ B\{i 0}u iM i=b
car u i 0=0. Dans la matrice B, nous allons remplacer le vecteur colonne M i 0 par un autre vecteur M j 0 pour j 0J N de sorte que la matrice B ainsi obtenue soit inversible. Il est clair que u est solution du système linéaire Bx=b, étant donné que
iJ B{i 0}u iM i+0M j 0=b.
Cette solution est unique en raison de la régularité de la matrice B. Donc, les deux bases réalisables B et B donnent toutes les deux la même solution de base (u 0 N).

IV-5 Algorithme du simplexe

Optimisation linéaireIV Méthode du simplexe → IV-5 Algorithme du simplexe

L'algorithme du simplexe est un procédé itératif qui progresse dans un sens évolutif : il passe d'une solution de base réalisable non optimale à une autre solution ayant une meilleure valeur d'objectif. De cette façon, on évite de parcourir toutes les solutions de base réalisable dont le nombre est en général prohibitif. Pour vérifier la non optimalité d'une solution, un simple test sera effectué. De plus, grâce à l'algorithme du simplexe, on sera capable de détecter, le cas échéant, que l'optimum est infini.

IV-5-1 Condition d'optimalité

IV-5-2 Amélioration de la fonction d'objectif

IV-5-3 Algorithme

IV-5-4 Règle de pivotage

Optimisation linéaireIV Méthode du simplexe → IV-5 Algorithme du simplexe

IV-5-1 Condition d'optimalité


La fonction d'objectif Z(y)=c y est entièrement définie par la donnée du vecteur c=(c i,i=1,,n). A chaque base B=(M i,iJ B), on note c B=(c i,iJ B) et c N=(c i,iJ N). D'une façon équivalente, le vecteur c B (resp. c N) s'obtient à partir de c en prenant les coordonnée c i relatives aux variables de base (resp. hors base) associée à la matrice B (resp. N). Le classement du vecteur c selon J B et J N donne c=( c N c B). Naturellement, on dit qu'une base B est optimale si la solution associée y=( 0 N B 1b) est optimale.

Théorème

On se donne une base réalisable B du problème (FS). Si la forme standard (FS) est de type maximisation (resp. minimisation), on considère le vecteur ligne
w N *=c N *c B *B 1N
(resp. w N *=c B *B 1Nc N *). Alors, on a :
  • (i) w N *0 N *B est optimale.
  • (ii) Si de plus la base B est non dégénérée (i.e. B 1b>0 B), alors
B est optimale w N *0 N *.

La condition d'optimalité w N *0 N * peut être interprétée comme un test d'arrêt des itérations pour l'algorithme du simplexe. Il reste à décrire la technique qui permet de passer d'une solution de base réalisable non optimale à une autre solution de base réalisable ayant une meilleure valeur économique. Cette partie fera l'objet du paragraphe suivant.

Interprétation

Donner une interprétation économique du vecteur w N . A partir de la solution réalisable y (0)=( 0 N B 1b), on construit le point y obtenu en augmentant d'une unité la s-ième variable hors base. D'après l'égalité BNyN , ce point vaut y=( e s B 1bB 1Ne s), où e s désigne le s-ième vecteur de la base canonique de nm. Si le point ainsi obtenu est réalisable, on obtient :
Z(y)=Z(y (0))±w N *e s=Z(y (0))±w s, car w N *e s=w s.
Pour un problème de type maximisation, cette dernière égalité s'écrit Z(y)=Z(y (0))+w s. Donc, l'élément w s représente la quantité s'ajoutant à la valeur économique Z lorsqu'on incrémente d'une unité la sieme coordonnée hors base de y (0), pour autant que le nouveau point obtenu soit réalisable. Semblablement, lorsqu'il s'agit d'un problème de minimisation, w s correspond à la valeur retranchée de la valeur économique. C'est la raison pour laquelle w N s'appelle vecteur des coûts réduits (ou coûts fictifs ou encore coûts marginaux).

Exercice


Sommet-Base-Optimalité : A venir

IV-5-2 Amélioration de la fonction d'objectif

Optimisation linéaireIV Méthode du simplexeIV-5 Algorithme du simplexe → IV-5-2 Amélioration de la fonction d'objectif

On se donne une base réalisable B=(B 1,,B m). Le vecteur B i désigne la iieme colonne de B qui est à fortiori une colonne de M. On note aussi N j la colonne d'indice j de la matrice N. D'ailleurs, N j n'est autre Ne je j est le j-ième vecteur de la base canonique de nm.

Théorème

On suppose que la base réalisable B vérifie w N *¬0 N *. Il existe donc une composante w s du vecteur w N qui est strictement positive. Considérons le sieme vecteur colonne γ=B 1N s de la matrice B 1N. Alors de deux choses l'une
  • (i) ou bien γ0 B, et dans ce cas l'optimum est infini,
  • (ii) ou bien γ¬0 B. Dans ce cas, on calcule le réel
    λ=min{(B 1b) iγ iγ i>0},
et on détermine un indice r{1,,m} pour lequel ce minimum lambda est atteint (i.e. λ=(B 1b) rγ r). Alors, la matrice B, obtenue à partir de B=(B 1,,B m) en remplaçant le vecteur colonne B r par N s, est une base réalisable. La solution de base y (1)=( 0 N B 1b) associée à B vérifie
(B 1b) i={(B 1b) iλγ i siir λ sii=r.
De plus, on a Z(y (1))=Z(y (0))±λw s, selon que (FS) soit de tupe maximisation ou minilisation. Ici, le point y (0) représente la solution de base réalisable associée à B : y (0)=( 0 N B 1b).

Il est intéressant de remarquer que dans le cas où la base réalisable B est non dégénérée, le paramètre lambda est strictement positif. Sans aucun doute, le point construit y (1) possède, en cas de non dégénérescence, une valeur économique strictement meilleure que celle de y (0).
Optimisation linéaireIV Méthode du simplexeIV-5 Algorithme du simplexe → IV-5-2 Amélioration de la fonction d'objectif

IV-5-3 Algorithme



/* On suppose que l'on dispose d'une base réalisable B */
y B=B 1b
Z=c B *y B
w N *={c N *c B *B 1N simax c B *B 1Nc N * simin
tant que w N *¬<=0 N * faire
       choisir s telle que w s=w N e s>0
       γ=B 1N s
      si γ<=0 B alors
             optimum infini /* sup=+ ou inf= */
             exit
      sinon
             calculer λ=min{(B 1b) iγ iγ i>0}
             déterminer r pour lequel lambda est atteint

       Z{Z+λw s simax Zλw s simin
       BB /* B r est remplacée par N s */
       NN /* N s est remplacée par B r */
       (y B) i{(y B) iλγ i pourir λ pouri=r
       Calculer w N

Optimum atteint en y=( 0 N y B) et il vaut Z
/* Fin de l'algorithme */

IV-5-4 Règle de pivotage


Dans la pratique, le choix de w s est souvent multiple, il se peut que plusieurs composantes w N soient strictement positives. Etant donnée que la nouvelle solution y (1) vérifie :
Z(y (1))=Z(y (0))±λw s
il serait commode de choisir la plus grande composante w s de w N strictement positive.
Il arrive aussi que le minimum lambda soit atteint pour deux ou plusieurs coordonnées différentes. Dans ce cas de figure, on fixe comme critère de choix pour l'indice r, la première coordonnée trouvée j qui réalise le minimum lambda. Pour des raisons de stabilité numérique et par analogie avec la méthode de Gauss avec pivot partiel, un autre critère de choix est souvent considéré. Il consiste à choisir r de façon à ce que γ r soit le plus élevé parmi les éléments γ i strictement positifs. Le critère qui fixe le choix de w s et de l'indice r s'appelle règle de pivotage. La règle qui prend systématique la plus grande valeur positive de w N s'appelle règle du meilleur coût marginal, c'est cette règle que l'on adopte dans ce cours.

V Algorithme du simplexe standard

Optimisation linéaire → V Algorithme du simplexe standard

Dans ce chapitre, les données mise en oeuvre dans l'algorithme du simplexe seront représentées dans un tableau. A chaque itération correspond un tableau appelé tableau simplexe. Des formules itératives liant les éléments d'un tableau au tableau subséquent seront également établies.

V-1 Tableau simplexe

V-2 Application

V-3 Sommets et solutions de base

V-4 Formules itératives

V-5 Algorithme du simplexe standard

Optimisation linéaire → V Algorithme du simplexe standard

V-1 Tableau simplexe


Les éléments qui interviennent dans l'algorithme du simplexe peuvent être récapitulés dans ce qui suit.
  • Les variables de base et les variables hors base. La base réalisable B et la matrice N seront immédiatement identifiées à partir des variables de base et hors base.
  • La solution y=(B 1b 0 N) associée à la base réalisable B. Puisque y N=0 N, on ne retient que le vecteur y B=B 1b.
  • Le vecteur w N *=±[c N *c B *B 1N] pour tester l'optimalité.
  • La matrice B 1N afin de calculer w N et le coefficient lambda.
  • La valeur de la fonction Z au point y=(B 1b 0 N) qui est égale à
    Z(y)=c B *y B.
A chaque base réalisable B correspond une itération de l'algorithme du simplexe. Pour rendre pratique l'application manuelle de l'algorithme du simplexe, les éléments décrits ci-dessus sont regroupés dans un tableau de la manière suivante :
y i m+1y i n  
B 1N B 1b y i 1
vdots
y i m
w N * Z 

Les coordonnées y i 1,,y i m correspondent aux variables de base, et les coordonnées y i m+1,,y i n correspondent aux variables hors base. Le terme Z désigne la valeur de la fonction d'objectif Z au point réalisable (B 1b 0 N). D'après l'indexation des variables de base, on a :
Z= j=1 mc i jy i j, avec y i j=(B 1b) j.

V-2 Application


Comme application de l'algorithme du simplexe, nous allons résoudre les trois exemples du premier chapitre en utilisant les tableaux simplexe.

V-2-1 Exemple 1

V-2-2 Exemple 2

V-2-3 Exemple 3

V-2-1 Exemple 1


Reprenons l'Exemple 1 :
{max[Z(x 1,x 2) =4x 1+5x 2] 2x 1+x 2 8 x 1+2x 2 7 x 2 3 x 10,x 20
  • On écrit ce probème sous forme standard.
    En ajoutant les variables d'écart, on obtient :
    M=(2 1 1 0 0 1 2 0 1 0 0 1 0 0 1),
    c *=(4 5 0 0 0) et b=(8 7 3).
  • On cherche un système de variables de base réalisable
    Il est clair que {y 3,y 4,y 5} forme un système de variables de base réalisable. La base associée est B=I 3, elle vérifie bien
    B 1b=I 3b=b0 3.
    Pour cette base, on obtient :
    B 1N=N=(2 1 1 2 0 1),
    w N *=c N *=(4 5)
    car c B =0 B et
    ZZ(0,0,8,7,3)=0.
    Rappelons que les coordonnées de chaque solution de base réalisable (B 1b 0 N) sont classées selon B et N. Pour la base B=I 3, si on écrit les coordonnées de la solution réalisable (B 1b 0 N)=(b 0 N) dans l'ordre y i, i=1,,5, on obtient exactement le point (0,0,8,7,3).
  • Itération 1
    y 1    y 2      

    2  
      1    8    y 3
    1    2    7    y 4
    0    1    3    y 5

    4  
      5    0   

    Le vecteur ligne w N *=(45) n'est pas négatif, il contient deux composantes strictement positives. Il a été convenu de choisir la plus grande qui est 5. Pour distinguer notre choix, on décide de l'écrire en gras. Faisant référence aux notations utilisées dans le Théorème , on a :
    w s=5 et γ=B 1N s=(1 2 1).
    Donc, au cours de l'itération suivante, la variable hors base qui se situe au niveau de w s va devenir une variable de base. D'après le tableau ci-dessus, il s'agit de la variable y 2. Pour déterminer la variable qui prend place, il va falloir calculer le paramètre lambda et en déduire l'indice r. D'après le même tableau, on a :
    λ=min{81,72,31}=3
    et donc r=3.0 L'indice r correspond alors à la variable y 5. On décide de mettre en gras l'élément γ r qui a permis de réaliser le minimum
    λ=(B 1b) rγ r.
    En résumé, lorsqu'on écrit en gras une composante w s de w N , cela signifie que la variable, figurant sur la même colonne que w s du tableau simplexe, entre dans la base. Inversement, l'identification de γ r permet de décider que la variable, située sur la même ligne que γ r sort de la base. Naturellement, ces deux variables s'appellent respectivement variable entrante et variable sortante.
  • Itération 2
    A ce stade de calcul, la base réalisable B est associée aux variables {y 3,y 4,y 2}. Pour la prochaine itération, on aura besoin de B à la place de B. Afin de ne pas encombrer le texte par les notations, il est naturel de garder les mêmes symboles B, N et lambda pour toutes les itérations du simplexe. En tenant compte de l'ordre des indices J B={3,4,2} des variables de base et de J N={1,5}, on obtient
    B=(1 0 1 0 1 2 0 0 1) et N=(2 0 1 0 0 1).
    Par un simple calcul, on vérifie les égalités suivantes :
    B 1N=(2 1 1 2 0 1),B 1b=(5 1 3) et w N *=(4 5).
    Le tableau simplexe relatif à cette itération est
    y 1    y 5      
    2    1    5    y 3
    1    2    1    y 4
    0    1    3    y 2
    4    5    15   

    Noter que le vecteur B 1b peut être calculé aussi via la formule
    (B 1b) i leftarrow {(B 1b) iλγ i pourir λ pouri=r
    = (83×1 73×2 λ)
    = (5 1 3)

    De même, la valeur Z=15 qui correspond à Z(0,3,5,1,0) peut être obtenue à travers le résultat ZZ+λw s=0+3×5=15. Ces deux constatations restent valables pour les itérations qui suivent et pour n'importe quel exemple.
    Pour ce tableau, le vecteur w N admet une seule composante strictement positive qui est w s=4. Donc, la variable y 1 entre dans la base au cours de l'itération 3. En ce qui concerne le nouveau paramètre lambda, on a :
    γ=B 1N s=(2 1 0), et par suite λ=min{52,11}=1.
    Ainsi, la variable y 4 devient hors base. Il est intéressant de noter que les matrices B et N peuvent être déduites du tableau simplexe à partir des variables de base et des variables hors base. Dans toute la suite et lors de l'exécution d'une itération simplexe, seul le tableau simplexe sera donné. Bien entendu, on précisera en gras les éléments w s et γ r et on calculera le coefficient lambda, à chaque fois que cela s'avère nécessaire.
  • Itération 3
    y 4    y 5      
    2    3    3    y 3
    1    2    1    y 1
    0    1    3    y 2
    4    3    19   
    λ=min{33,31}=1.
  • Itération 4
    y 4    y 3      
    23    13    1    y 5
    13    23    3    y 1

    23  
      13    2    y 2
    2    1    22   
  • Conclusion
    On a
    w N *=(21)(00)
    donc le Théorème assure que (3,2,0,0,1) est une solution optimale pour (FS). D'après le Théorème , le point (3,2) est optimal pour notre (PL) de départ. Il réalise une valeur maximale de Z égale à 22.

V-2-2 Exemple 2


Pour l'Exemple 2, le (PL) considéré est
{max[Z(x 1,x 2) =6x 1+15x 2] 2x 1x 2 4 2x 1+5x 2 4 x 10,x 20
  • On écrit ce probème sous forme standard.
    En retranchant une variable d'écart à la première contrainte, et en ajoutant une seconde à la deuxième, on obtient :
    M=(2 1 1 0 2 5 0 1),c *=(6 15 0 0) et b=(4 4).
  • On cherche un système de variables de base réalisable
    Prenons par exemple {y 1,y 4} et montrons qu'il forme un système de variables de base réalisable. La matrice B associée à ce système vérifie :
    B=(2 0 2 1)B 1=(12 0 1 1)B 1b=(2 8).
    Les composantes de B 1b étant positives, la matrice B est une base réalisable. On calcule
    B 1N=(12 0 1 1)(1 1 5 0)=(12 12 4 1),
    et
    w N *=(15 0)(6 0)(12 12 4 1)=(12 3).
    La solution de base réalisable relative à B est (2,0,0,8), elle donne une valeur d'objectif égale à Z(2,0,0,8)=12.
  • Itération 1

    y 2    y 3      
    12    12    2    y 1

    4  
      1    8    y 4
    12    3    12   
    λ=min{84}=2.
  • Itération 2

    y 4    y 3      
    18    58    3    y 1

    14  
      14    2    y 2
    3    0    12   

    Le vecteur ligne w N *=(30) étant négatif, la solution associée (3,2,0,0) est optimale pour (FS). Compte tenu du Théorème , on peut affirmer que (3,2) est une solution optimale de ce (PL) et que la valeur maximale de Z sur le domaine réalisable est 12.
  • Remarque
    On avait montré à l'aide du graphique que ce probème admettait une infinité de solutions optimales. Ce résultat peut être retrouvé via le dernier tableau simplexe. En effet, on remarque sur ce tableau une composante w s nulle. Le vecteur γ=B 1N s est égal à γ=(5/8 1/4), qui est négatif. Donc, tout point de la forme z λ=(B 1bλγ λe s) est réalisable pour (FS) et ceci pour tout réel lambda positif. Du fait que w s=0, la valeur de Z(z λ), qui est égale à 12+λw s, reste inchangée. Par suite, le point z λ est optimal pour (FS) quelque soit le réel positif lambda.
  • Conclusion
    En ce qui concerne le (PL) associé, nous allons utiliser comme d'habitude le Théorème . Si on classe les composantes de z λ dans l'ordre y i, i=1,,4, on obtient z λ=(3+λ58,2+λ14,λ,0). Par conséquent,
    x λ=(3+λ58,2+λ14)=(3,2)+λ(58,14)
    est un point optimal pour (PL). Notons que (58,14) est un vecteur directeur de la droite (AB) (voir Figure ). D'ailleurs, la demi-droite [AB) co''{5}ncide avec l'ensemble des points (3,2)+λ(58,14) lorsque lambda décrit +.

V-2-3 Exemple 3


Pour l'Exemple 3 :
{max[Z(x 1,x 2) =x 1+x 2] x 1+x 2 1 x 1+2x 2 4 x 10,x 20
  • On écrit ce problème sous forme standard
    On a :
    M=(1 1 1 0 1 2 0 1),c *=(1 1 0 0) et b=(1 4).
  • On cherche un système de variables de base réalisable
    Il est facile de vérifier que B=I 2 est une base réalisable.
  • Itération 1

    y 1    y 2      
    1    1    1    y 3
    1    2    4    y 4
    1    1    0   

  • Conclusion
    Pour w s=1 écrit en gras, on a γ=(1 1)(0 0). Donc, d'après le Théorème , le probème vérifie :
    \sup y𝒴Z(y)=+.
    Plus précisément, pour tout réel λ0, le point réalisable y λ=(B 1bλγ λe s) possède une valeur d'objectif égale à :
    Z(y λ)=0+λw s=λ
    dont la limite en + vaut +. Le point y λ est égal à
    (λ,0,1+λ,4+λ)
    et par conséquent x λ=(λ,0) est un point réalisable du (PL) initial et ceci pour tout réel λ0. Noter que x λ décrit le demi axe [Ox 1) lorsque lambda parcourt l'ensemble des réels positifs. D'après la Figure , tous ces points sont effectivement réalisables.

V-3 Sommets et solutions de base

Optimisation linéaireV Algorithme du simplexe standard → V-3 Sommets et solutions de base

Tous les (PL) résolus jusqu'ici sont des formes canoniques puisque le domaine réalisable de chacun peut s'écrire sous la forme
={x pAxb et x0 p}
Comme conséquence immédiate du Théorème , on peut affirmer que si (v bAv) est une solution d'une base réalisable de 𝒴, alors v est un sommet de . Essayons donc de voir le lien entre les différentes solutions de base réalisable parcourues par l'algorithme du simplexe et les sommets correspondants. Pour l'Exemple , à partir des quatre itérations effectuées, on voit que les sommets de mis en jeu ont été parcourus dans l'ordre suivant :
{(0,0) Z(0,0)=0{(0,3) Z(0,3)=15{(1,3) Z(1,3)=19{(3,2) Z=22.
En se référant à la Figure , on remarque que deux sommets relatifs à deux itérations consécutives sont toujours adjacents : ils appartiennent à un même segment de droite frontière de . Cela s'explique algébriquement par le fait que les bases B et B ne différent que d'une seule colonne.
Optimisation linéaireV Algorithme du simplexe standard → V-3 Sommets et solutions de base

V-4 Formules itératives


A chaque itération de l'algorithme du simplexe, on est contraint à calculer la matrice B 1N et le vecteur ligne w N *=±[c N *c B *B 1N]. Ces calculs exigent préalablement la détermination de la matrice inverse B 1. Dans cette section, nous allons voir comment surmonter cette difficulté. Tout simplement, on évitera le calcul de B 1. Les éléments d'un tableau vont être déterminés itérativement à partir des éléments du tableau précédent.

V-4-1 Matrice du pivot

V-4-2 Vecteur des coûts réduits

V-4-1 Matrice du pivot


Posons β=B 1N la matrice réelle rectangulaire (m,p) avec p=nm. Aussi, on pose B=(B 1,,B m) et N=(N 1,,N p)B i (resp. N i) désigne la iieme colonne de B (resp. N). Supposons qu'à l'itération relative à la base B, on ait permuté le vecteur colonne B r avec N s. Au niveau du tableau, cela revient à écrire en gras l'élément (r,s) de la matrice beta, que l'on note communément β rs. Par conséquent, au cours de la prochaine itération, on aura
B=(B 1,,B r1,N s,B r+1,,B m)
comme base réalisable et
N=(N 1,,N s1,B r,N s+1,,N p).

Théorème

Les relations qui lient β=B 1N avec β=B 1N sont données par :
β is={1β rs sii=r β isβ rs siir
et
{β rj=β rjβ rs sijs β ij=β ijβ isβ rjβ rs sijs et ir.

Afin de mieux visualiser les formules établies dans le Théorème , nous allons illustrer tout d'abord les éléments du tableau simplexe dans le schéma suivant. Le réel { β rs} correspond à l'élément écrit en gras au niveau de la matrice β=B 1N.
(B 1b) r
β rs
w s Z

Ensuite, le tableau simplexe qui suit sera rempli moyennant des transformations qui peuvent être résumées en ces termes :
  • au niveau de { β rs}, on aura 1β rs.
  • Tout élément de la colonne relative à { β rs} devient β rs.
  • Tout élément de la ligne relative à { β rs} devient β rs.
  • Tout élément en dehors de la ligne et de la colonne relative à { β rs} sera transformé en β rs. Dans cette dernière expression, on tient à préciser que ( resp. ) est l'élément de la matrice β=B 1N qui appartient à la même colonne (resp. ligne) que et la même ligne (resp. colonne) que { β rs}.
Les relations données dans le Théorème sont identiques aux formules de Gauss-Jordan pour l'inversion d'une matrice. Pour cette raison, l'élément β rs s'appelle pivot, faisant allusion au pivot de Gauss. A chaque itération du simplexe, le pivot est donc l'intersection de la variable sortante avec la variable entrante. Noter également que toute ligne, en dehors de la ligne du pivot, qui possède un zéro sur la colonne du pivot reste inchangée ; idem pour les colonnes possédant un zéro sur la ligne du pivot.

V-4-2 Vecteur des coûts réduits


On garde ici le même pivot β rs. Cela veut dire que le vecteur colonne B r a été échangé par N s et vice versa. Les formules établies précédemment pour β vont conduire aux relations liant les composantes de w N * avec celles de w N . Pour cela, on pose :
w N *=(w 1w p) et w N *=(w 1w p).

Théorème

Les composantes de w N * sont données par
w j={w sβ rs sij=s w jw sβ rjβ rs sijs.

D'ores et déjà, on peut observer que les relation liant w N * à w N sont les mêmes que les relations entre une ligne β i et une ligne en dehors de la ligne du pivot β i. Le terme w s, qu'on a convenu d'écrire en gras, se situe sur la même colonne du pivot. Il est remplacé par w sβ rs. Les opérations qu'il faut appliquer sur w j, jk, en vue d'obtenir w j sont identiques à celles effectuées sur les termes de symbole dans le schéma du paragraphe précédent.

V-5 Algorithme du simplexe standard

Optimisation linéaireV Algorithme du simplexe standard → V-5 Algorithme du simplexe standard

En ce qui concerne le vecteur B 1b, il a été indiqué d'avance qu'il peut être déterminé par les relations
(B 1b) i={(B 1b) iλβ is pourir λ pouri=r.
Si on remplace lambda par sa valeur (B 1b) r/β rs, on obtient les mêmes formules qui régissent une colonne de beta en dehors de la colonne du pivot. Maintenant, l'élément en bas à droite du tableau simplexe, à savoir Z, se calcule itérativement via la relation ZZ+λw s ou ZZλw s selon que le probème étudié soit de type maximisation ou minimisation. En tenant compte de l'expression de lambda, il est facile de constater que la formule ZZλw s s'identifie à la formule relative à un élément de symbole '' ''. Afin de garder les mêmes formules, il est souhaitable de remplacer Z par Z lorsqu'il s'agit d'un probème de type maximisation. Au niveau de l'implémentation sur machine, il est commode de définir une matrice, que l'on note H, qui contient les éléments beta, B 1b, w N et Z :
{H(1:m,1:p)=β=B 1N, avec p=nm H(1:m,p+1)=B 1b H(m+1,1:p)=w N *=±[c N *c B *B 1N] H(m+1,p+1)=±Z(y (0))
La matrice H est de taille (m+1,p+1). D'une itération à une autre, elle est calculée itérativement de la même façon que l'on détermine les éléments symbolisés par '' '', '' '' et '' ''. Afin de balayer tous les paramètres du tableau simplexe, on ajoute à H deux vecteurs entiers, notés base et hbase et de taille respective m et p. Pour chaque coordonnée i, base(i) fournit l'indice de la iieme variable de base du tableau simplexe en cours. De même, hbase(j) correspond à l'indice de la jieme variable hors base. La mise en oeuvre des résultats de ce paragraphe dans l'algorithme du simplexe aboutit à une formulation plus simplifiée au niveau de l'implémentation sur machine. Ici, on suppose que l'on prend systématiquement l'élément w s>0 le plus élevé. Naturellement, le plus grand parmi les composantes strictement positives est le maximum sur toutes les composantes de w N .

Algorithme du simplexe standard



Input: base réalisable
Initialiser H, base et hbase
Calculer ws=max[H(m+1,1:p)]
tant que ws>0 faire
       déterminer l'indice s pour lequel le maximum ws est atteint
      si H(1:m,s)<=0 m alors
             optimum infini /* sup=+ ou inf= */
             exit
      sinon
             calculer λ=min{H(i,p+1)H(i,s), pour i=1,,mH(i,s)>0}
             déterminer l'indice r pour lequel lambda est atteint

       base(r)hbase(s)
       piv=H(r,s)
       H(r,s)1piv
       H(r,j)H(r,j)piv, pour j=1,,p+1 et js
       H(i,j)H(i,j)H(r,j)*H(i,s), pour ir et js
       H(i,s)H(i,s)piv, pour i=1,,m+1 et ir
       Calculer ws=max[H(m+1,1:p)]

Optimum vaut Z=±H(m+1,p+1)
Une solution optimale, que l'on note opty, est donnée par :
<br>{opty(base(1:m))=H(1:m,p+1) opty(hbase(1:p))=0.<br>

Exercice

Résolution par les tableaux simplexe
Méthode du simplexe
Optimisation linéaireV Algorithme du simplexe standard → V-5 Algorithme du simplexe standard

VI Dualité en programmation linéaire

Optimisation linéaire → VI Dualité en programmation linéaire

Dans le cadre de la programmation linéaire, on peut associer à chaque (PL) un autre (PL), de type opposé, nommé programme dual. Leurs propriétés sont étroitement liées :
Par souci d'optimiser les calculs lors de la résolution d'un (PL), il est plus avantageux, dans certaines circonstances, de résoudre le probème dual. Ensuite, la solution du (PL) initial sera déduite facilement par l'intermédiaire de la solution du dual.
Une des conséquences les plus fructueuses de la notion de dualité est l'algorithme dual-simplexe qui a été conçu, dans les années 50, par Lemke. Cet algorithme a un intérêt inéluctable en programmation linéaire.

VI-1 Primal - Dual

VI-2 Optimalité pour le primal-dual

Optimisation linéaire → VI Dualité en programmation linéaire

VI-1 Primal - Dual

VI-1-1 Cas d'une forme canonique


On considère un programme linéaire écrit sous forme canonique que l'on suppose de type maximisation :
{max[Z(x)=c *x] Axb x0 p.
Von Neumann, un Mathématicien Allemand du début du 20-ième siècle, a défini le dual de ce probème par le programme linéaire de type minimisation suivant :
{min[ψ(v)=b *v] A *vc v0 m.
Le probème initial à partir duquel on a défini le dual s'appelle primal. Pour une forme canonique, le second membre du dual est formé par les coefficients de la fonction économique du primal ; de même, les coefficients de la fonction d'objectif du dual ne sont autres que les composantes du second membre du dual ; aussi, la matrice régissant les contraintes du dual est la matrice transposée de la matrice du primal ; et enfin, les inégalités (mise à part les inégalités de positivité) du primal et du dual sont en sens inverse.

VI-1-2 Cas général


Tout programme linéaire ne s'écrit pas forcément sous forme canonique. Il peut admettre en effet des contraintes d'égalités et/ou des variables sans restriction de signe (s.r.s. en abrégé). De ce fait, la forme générale d'un primal de type maximisation s'écrit de la façon suivante :
(𝒫){max[Z(x)= j=1 pcjxj] j=1 paijx jb i, pour i=1,,l j=1 paijx j=b i, pour i=l+1,,m x j0, pour j=1,,k x j s.r.s., pour j=k+1,,p.
Après un certain nombre d'opérations algébriques, on montre que le dual de (𝒫) est :
(𝒟){min[ψ(v)= i=1 mb ivi] i=1 maijv ic j, pour j=1,,k i=1 maijv i=c j, pour j=k+1,,p v i0, pour i=1,,l v i s.r.s., pour i=l+1,,m.

VI-1-3 Tableau récapitulatif


On note que lorsque le primal est écrit sous une forme générale, son dual l'est aussi. Le tableau ci-dessous récapitule les règles de correspondance entre un primal de type maximisation et son dual.

Primal  
  Dual
- Maximisation    - Minimisation
- Coefficients d'objectif    - Second membre
- Second membre    - Coefficients d'objectif
- Matrice régissant les contraintes    - Matrice transposée
- Relation liant les contraintes
  • i-ième inégalité : leq
  • i-ième équation : =
 
  - Nature des variables
  • v i0
  • v i s.r.s.
- Nature des variables
  • x j0
  • x j s.r.s.
 
  - Relation liant les contraintes
  • j-ième inégalité : geq
  • j-ième équation : =

Remarque

On aurait pu choisir comme primal un probème de minimisation, le dual aurait été alors un programme linéaire de type maximisation. Tout simplement parce que le dual du dual est le primal (facile à prouver). Autrement dit, si on permutait dans le tableau précédent les deux mots Primal et Dual, on obtiendrait les règles de correspondance entre un primal de minimisation et son dual.

VI-2 Optimalité pour le primal-dual

Optimisation linéaireVI Dualité en programmation linéaire → VI-2 Optimalité pour le primal-dual

Théorème

Si x op et v op sont deux solutions réalisables de (𝒫) et (𝒟) respectivement, alors Z(x op)ψ(v op). Si de plus on a Z(x op)=ψ(v op), alors x op et v op sont deux solutions optimales de (𝒫) et (𝒟) respectivement.

Dans la pratique, il est souvent difficile de trouver deux points réalisables x op et v op de (𝒫) et (𝒟) tels que Z(x op)=ψ(v op). La situation la plus envisageable consiste à déterminer une solution optimale du primal via par exemple le simplexe, puis essayer d'en dégager une solution optimale du dual.

Théorème

Soit B une base réalisable de la forme standard relative au primal (𝒫). Si la base B vérifie w N *0 N *, alors v op *=c B *B 1 est une solution optimale du dual (𝒟).

Remarque

Afin de déterminer la solution optimale v op *=c B *B 1, il est inutile de calculer la matrice inverse B 1. Il suffit, en effet, de résoudre le système de Cramer v B=c B . Par ailleurs, le Théorème précédent n'exige aucune condition sur la nature du primal ( max ou min).

Optimisation linéaireVI Dualité en programmation linéaire → VI-2 Optimalité pour le primal-dual

cours d'optimisation linéaire (licence).
: linear_optimisation, simplex_method, interactive mathematics, interactive math, server side interactivity

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.