Optimisation linéaire

Optimisation linéaire

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 : {quote} Hédi Nabli, ''Recherche Opérationnelle : Algorithme du Simplexe et ses Applications'', Centre de Publication Universitaire , Tunisie (2006) {quote} 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

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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

Les coefficients et bi sont des réels fixés et les xj 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

I-1 Généralités

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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

I-3 Domaine réalisable

I-4 Présentation des méthodes

I-2 Exemple

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 x1 et x2 les quantités vendues du produit (A) et (B), le gain total vaut

Z(x1,x2) = 4x1 +5x2

D'autre part, la disponibilité en matières premières revient à exiger des quantités, utilisées pour la fabrication de x1 et x2, qui soient inférieures aux quantités disponibles. Ces contraintes s'expriment par les inégalités suivantes :

Bien entendu, les variables x1 et x2 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 :

I-1 Généralités

I-3 Domaine réalisable

I-4 Présentation des méthodes

I-3 Domaine réalisable

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 et il est défini par

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

tout point réalisable (x1,x2) vérifie

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.
I-1 Généralités

I-2 Exemple

I-4 Présentation des méthodes

I-4 Présentation des méthodes

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

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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.
I-1 Généralités

I-2 Exemple

I-3 Domaine réalisable

II Méthode graphique

Optimisation linéaire  ---> II Méthode graphique
I Programmation linéaire picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 . Noter que tout hyperplan d'équation Z(x) = r, , est parallèle à .
  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 qui fait augmenter ( resp. diminuer) r.
  4. Déterminer la droite la plus éloignée (dans le sens de la flèche) de et qui coupe le domaine réalisable . Tout point de est une solution optimale. Si une telle droite 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

II-1 Exemple 1

I Programmation linéaire picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

Reprenons l'exemple

Représentation graphique pour l'exemple 1

Le domaine réalisable est schématisé en gris sur la Figure. Toute droite d'équation Z(x1, x2) = r, où r est un réel fixé, est parallèle à la droite : Z(x1, x2) = 0. On constate aussi que tout déplacement parallèle de 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 la plus éloignée (dans le sens de la flèche) de et qui coupe le domaine réalisable. Du point de vue graphique, il s'agit de la droite passant par le point (3, 2) et parallèle à . 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

II-3 Exemple 3

II-4 Remarque

II-5 Exercice

II-2 Exemple 2

I Programmation linéaire picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

On considère le (PL) suivant :

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 dans le sens de la flèche (voir dessin ci-après) fait augmenter r. Donc tout point de la demi-droite est optimal et la valeur maximale de Z vaut Z(A) = Z(3,2) = 12 (voir dessin ci-après).

II-1 Exemple 1

II-3 Exemple 3

II-4 Remarque

II-5 Exercice

II-3 Exemple 3

I Programmation linéaire picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

On considère maintenant le (PL) suivant :

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 d'équation Z(x1, x2) = r, avec , coupe le domaine réalisable. Donc, et par conséquent, le problème n'admet aucune solution optimale (voir dessin ci-dessous).

II-1 Exemple 1

II-2 Exemple 2

II-4 Remarque

II-5 Exercice

II-4 Remarque

I Programmation linéaire picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

Tous les exemples traités ci-dessus possèdent deux variables structurelles x1 et x2. 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 (x1, x2, x3) vérifiant une contrainte
se représente par un demi-espace qui est délimité par le plan d'équation
II-1 Exemple 1

II-2 Exemple 2

II-3 Exemple 3

II-5 Exercice

II-5 Exercice

I Programmation linéaire picto

III Méthode des sommets picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

Exercice

A venir

II-1 Exemple 1

II-2 Exemple 2

II-3 Exemple 3

II-4 Remarque

III Méthode des sommets

Optimisation linéaire  ---> III Méthode des sommets
I Programmation linéaire picto

II Méthode graphique picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

La méthode des sommets est 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 .

{df} Pour toute contrainte d'inégalité ( resp. contrainte de positivité ) d'un (PL) donné, l'hyperplan associé ( resp. xi = 0) s'appelle hyperplan frontière . {df}

III-1 Résultat préliminaire

III-2 Mise en oeuvre

III-3 Champ d'application

III-1 Résultat préliminaire

Optimisation linéaire  ---> III Méthode des sommets  ---> III-1 Résultat préliminaire
I Programmation linéaire picto

II Méthode graphique picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 une application linéaire et un polyèdre de . 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

III-2 Mise en oeuvre

III-3 Champ d'application

III-2 Mise en oeuvre

I Programmation linéaire picto

II Méthode graphique picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 )

La valeur de la fonction d'objectif Z en chacun de ces sommets est

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

III-1 Résultat préliminaire

III-3 Champ d'application

III-3 Champ d'application

I Programmation linéaire picto

II Méthode graphique picto

IV Méthode du simplexe picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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é : ). 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 (n-p) 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 à . 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 (pn) est en général très important. A titre indicatif, on a ! 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

III-1 Résultat préliminaire

III-2 Mise en oeuvre

IV Méthode du simplexe

Optimisation linéaire  ---> IV Méthode du simplexe
I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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

IV-1 Forme canonique

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

On convient de dire qu'un vecteur u est inférieur à un vecteur v , et on écrit , si pour tout i, on a . Ici, le terme ui désigne la i-ième composante du vecteur u. Nous mettons en garde sur le fait que

la négation de n'est pas u > v.

En effet, l'inégalité u > v traduit la propriété ui > vi pour toute composante i. Par contre, la négation de , que l'on convient de noter , exprime que l'inégalité ui > vi ait lieu pour au moins une composante i.

{df} 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. {df}

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 :

où , A, matrice (m, p) et sont fixés.

Le vecteur x a p composantes réelles xi et désigne l'opérateur transposé. Les inégalités

(i.e. ) 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.

IV-2 Forme standard

IV-3 Relation entre la frome canonique et standard

IV-4 Notion de base réalisable picto

IV-5 Algorithme du simplexe picto

IV-2 Forme standard

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 xi sans restriction de signe par la différence de deux variables positives : avec et .
  • Si une variable xi est négative, effectuer le changement de variable xi' = -xi.

Soit la forme canonique (FC) suivante :

max Z =
sous les contraintes
geq
geq
geq
geq
x1 geq 0, x2 geq 0

Les données de la forme standard de cette (FC) sont :

M = [ ], b = [] =

Exemple

Mettre sous forme standard le (PL) suivant :

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 x3 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 x4, elle devient

x1 - x3 - x4 = -1
Quant à la troisième contrainte, on lui ajoute une variable positive x5 pour devenir
x2 + x3 + x5 = 4
Concernant la variable x3 qui est sans restriction de signe, elle est remplacée par x3-x3-, avec et . En conclusion, la forme standard associée à ce (PL) s'écrit

Les variables du (PL) initial s'appellent variables de décision , celles de la forme standard associée s'appellent variables structurelles .
IV-1 Forme canonique

IV-3 Relation entre la frome canonique et standard

IV-4 Notion de base réalisable picto

IV-5 Algorithme du simplexe picto

IV-3 Relation entre la frome canonique et standard

Optimisation linéaire  ---> IV Méthode du simplexe  ---> IV-3 Relation entre la frome canonique et standard
I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 est une solution optimale de la forme standard associée. De plus, on a

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 (v1, v2, v3, v4, v5, v6) 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 (v1, v2, v3 - v4) est une solution optimale du (PL) initial.

Exercice

Forme standard : à venir

IV-1 Forme canonique

IV-2 Forme standard

IV-4 Notion de base réalisable picto

IV-5 Algorithme du simplexe picto

IV-4 Notion de base réalisable

Optimisation linéaire  ---> IV Méthode du simplexe  ---> IV-4 Notion de base réalisable
I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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 :

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

IV-1 Forme canonique

IV-2 Forme standard

IV-3 Relation entre la frome canonique et standard

IV-5 Algorithme du simplexe picto

IV-4-1 Système de base

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

Notons par Mi la colonne de M. Le vecteur colonne My s'écrit alors

yi est composante de y. On appelle système de variables de base tout ensemble de m variables distinctes yi, , prises parmi , telles que le déterminant des vecteurs Mi, 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 Mi, , s'appelle base et les variables yi, , 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 :

où et .

Les variables yi, , peuvent aussi être classées selon B et N :

Désormais, l'ensemble J des indices de base sera noté par JB et son complémentaire par JN. En respectant cette partition, le système My=b vérifie :

Par suite, l'ensemble des solutions dans du système linéaire My = b est égal à
Parmi les solutions de ce système, nous distinguons les solutions dites de base pour lesquelles yN = 0N (on écrit 0N à la place de pour dire que les variables hors base sont nulles). Une telle solution existe et elle vaut
Cette solution de base est réalisable ( i.e. elle vérifie les contraintes My = b et ) si et seulement si
Dans ce cas, on dit que la base B est réalisable .

Noter que toute solution de base réalisable admet (n - m) 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

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

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

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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
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
avec . Ces solutions de base réalisable sont bien évidemment en nombre fini.

IV-4-1 Système de base

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

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

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

Une solution de base réalisable est dite dégénérée , si en plus des (n - m) composantes nulles relatives à 0N, il existe une composante du vecteur qui est nulle. Elle est non dégénérée dans le cas où toutes les composantes de 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 relatif à une base dégénérée B admet au moins une coordonnée , , qui est nulle. En considérant que , on obtient

car Dans la matrice B, nous allons remplacer le vecteur colonne par un autre vecteur pour de sorte que la matrice B' ainsi obtenue soit inversible. Il est clair que u est solution du système linéaire B'x = b, étant donné que
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 .
IV-4-1 Système de base

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

IV-5 Algorithme du simplexe

Optimisation linéaire  ---> IV Méthode du simplexe  ---> IV-5 Algorithme du simplexe
I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

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

IV-1 Forme canonique

IV-2 Forme standard

IV-3 Relation entre la frome canonique et standard

IV-4 Notion de base réalisable picto

IV-5-1 Condition d'optimalité

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

La fonction d'objectif Z(y) = c y est entièrement définie par la donnée du vecteur . A chaque base , on note et . D'une façon équivalente, le vecteur cB (resp. cN) s'obtient à partir de c en prenant les coordonnée ci relatives aux variables de base (resp. hors base) associée à la matrice B (resp. N). Le classement du vecteur c selon JB et JN donne . Naturellement, on dit qu'une base B est optimale si la solution associée 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
(resp. ). Alors, on a :
  • (i) est optimale.
  • (ii) Si de plus la base B est non dégénérée (i.e. ), alors

La condition d'optimalité 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 wN. A partir de la solution réalisable , 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 , où es désigne le s-ième vecteur de la base canonique de . Si le point ainsi obtenu est réalisable, on obtient :

Pour un problème de type maximisation, cette dernière égalité s'écrit . Donc, l'élément ws représente la quantité s'ajoutant à la valeur économique Z lorsqu'on incrémente d'une unité la coordonnée hors base de , pour autant que le nouveau point obtenu soit réalisable. Semblablement, lorsqu'il s'agit d'un problème de minimisation, ws correspond à la valeur retranchée de la valeur économique. C'est la raison pour laquelle wN 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

IV-5-3 Algorithme

IV-5-4 Règle de pivotage

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

Optimisation linéaire  ---> IV Méthode du simplexe  ---> IV-5 Algorithme du simplexe  ---> IV-5-2 Amélioration de la fonction d'objectif
I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

On se donne une base réalisable . Le vecteur Bi désigne la colonne de B qui est à fortiori une colonne de M. On note aussi Nj la colonne d'indice j de la matrice N. D'ailleurs, Nj n'est autre Nejej est le j-ième vecteur de la base canonique de .

Théorème

On suppose que la base réalisable B vérifie . Il existe donc une composante ws du vecteur wN qui est strictement positive. Considérons le vecteur colonne de la matrice . Alors de deux choses l'une
  • (i) ou bien , et dans ce cas l'optimum est infini,
  • (ii) ou bien . Dans ce cas, on calcule le réel

et on détermine un indice pour lequel ce minimum lambda est atteint (i.e. ). Alors, la matrice B', obtenue à partir de en remplaçant le vecteur colonne Br par Ns, est une base réalisable. La solution de base associée à B' vérifie

De plus, on a , selon que (FS) soit de tupe maximisation ou minilisation. Ici, le point représente la solution de base réalisable associée à B : .

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 possède, en cas de non dégénérescence, une valeur économique strictement meilleure que celle de .

IV-5-1 Condition d'optimalité

IV-5-3 Algorithme

IV-5-4 Règle de pivotage

IV-5-3 Algorithme

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index


/* On suppose que l'on dispose d'une base réalisable B */



while do
       choisir s telle que ws = wN es>0
      
      if then
             optimum infini /* */
             exit
      else
             calculer
             déterminer r pour lequel lambda est atteint
      end if
      
       /* Br est remplacée par Ns */
       /* Ns est remplacée par Br */
      
       Calculer wN
end while
Optimum atteint en et il vaut Z
/* Fin de l'algorithme */
IV-5-1 Condition d'optimalité

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

IV-5-4 Règle de pivotage

IV-5-4 Règle de pivotage

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

V Algorithme du simplexe standard picto

VI Dualité en programmation linéaire picto

Index

Dans la pratique, le choix de ws est souvent multiple, il se peut que plusieurs composantes wN soient strictement positives. Etant donnée que la nouvelle solution vérifie :

il serait commode de choisir la plus grande composante ws de wN 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 soit le plus élevé parmi les éléments strictement positifs. Le critère qui fixe le choix de ws et de l'indice r s'appelle règle de pivotage . La règle qui prend systématique la plus grande valeur positive de wN s'appelle règle du meilleur coût marginal , c'est cette règle que l'on adopte dans ce cours.

IV-5-1 Condition d'optimalité

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

IV-5-3 Algorithme

V Algorithme du simplexe standard

Optimisation linéaire  ---> V Algorithme du simplexe standard
I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

VI Dualité en programmation linéaire picto

Index

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

V-1 Tableau simplexe

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

VI Dualité en programmation linéaire picto

Index

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 associée à la base réalisable B. Puisque yN = 0N, on ne retient que le vecteur .
  • Le vecteur pour tester l'optimalité.
  • La matrice afin de calculer wN et le coefficient lambda.
  • La valeur de la fonction Z au point qui est égale à
    Z(y) = cB yB
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 :

 

vdots
Z

Les coordonnées correspondent aux variables de base, et les coordonnées correspondent aux variables hors base. Le terme Z désigne la valeur de la fonction d'objectif Z au point réalisable . D'après l'indexation des variables de base, on a :

V-2 Application picto

V-3 Sommets et solutions de base

V-4 Formules itératives picto

V-5 Algorithme du simplexe standard

V-2 Application

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

VI Dualité en programmation linéaire picto

Index

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-1 Tableau simplexe

V-3 Sommets et solutions de base

V-4 Formules itératives picto

V-5 Algorithme du simplexe standard

V-2-1 Exemple 1

I Programmation linéaire picto

II Méthode graphique picto

III Méthode des sommets picto

IV Méthode du simplexe picto

VI Dualité en programmation linéaire picto

Index