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

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 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 '' ''. En multipliant chaque inégalité de type '' '' par (-1), on peut supposer que toutes les contraintes d'inégalité sont de type '' ''.

I-1 Généralités

I-2 Exemple

I-3 Domaine réalisable

I-4 Présentation des méthodes

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.

Exemple

Formulation mathématique

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 (x₁,x₂) 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.

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.

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

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(x₁, x₂) = r, où r est un réel fixé, est parallèle à la droite : Z(x₁, x₂) = 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).

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

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

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

Exercice

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. x_i = 0) s'appelle hyperplan frontière . {df}

III-1 Résultat préliminaire

III-2 Mise en oeuvre

III-3 Champ d'application

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

Sans nul doute, l'intérêt de ce théorème est immédiat :

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

Exercice

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

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

Exercice

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

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 u_i 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é u_i > v_i pour toute composante i. Par contre, la négation de , que l'on convient de noter , exprime que l'inégalité u_i > v_i 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 '' ''. 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 x_i 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.

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 '' '' (resp. '' ''), 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 : avec et .
• 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



x₁ 0, x₂ 0

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

M = [ ], b = [] =

Exemple

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₃ 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₄, elle devient

Quant à la troisième contrainte, on lui ajoute une variable positive x₅ pour devenir Concernant la variable x₃ qui est sans restriction de signe, elle est remplacée par x₃^-x₃^-, 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 .

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

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₁, v₂, v₃, v₄, v₅, v₆) 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₁, v₂, v₃ - v₄) est une solution optimale du (PL) initial.

Exercice

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 :

où 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

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

où y_i est composante de y. On appelle système de variables de base tout ensemble de m variables distinctes y_i, , prises parmi , telles que le déterminant des vecteurs M_i, 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, , s'appelle base et les variables y_i, , 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 y_i, , peuvent aussi être classées selon B et N :

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 :

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 y_N = 0_N (on écrit 0_N à 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.

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

Remarque

Une solution de base réalisable est dite dégénérée , si en plus des (n - m) composantes nulles relatives à 0_N, 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 .

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

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 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 . Naturellement, on dit qu'une base B est optimale si la solution associée est optimale.

Théorème

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

Exercice

On se donne une base réalisable . Le vecteur B_i désigne la 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_j où e_j est le j-ième vecteur de la base canonique de .

Théorème

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

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 vérifie :

il serait commode de choisir la plus grande composante w_s de w_N strictement positive.

Il arrive aussi que le minimum 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 . 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 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.

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

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 y_N = 0_N, on ne retient que le vecteur .
• Le vecteur pour tester l'optimalité.
• La matrice afin de calculer w_N et le coefficient .
• La valeur de la fonction Z au point 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 :

	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 :

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

Reprenons l'Exemple 1 :

• On écrit ce probème sous forme standard.
  En ajoutant les variables d'écart, on obtient :

• On cherche un système de variables de base réalisable
  Il est clair que forme un système de variables de base réalisable. La base associée est B = I₃, elle vérifie bien

  Pour cette base, on obtient :

  car c_B = 0_B et

  Rappelons que les coordonnées de chaque solution de base réalisable sont classées selon B et N. Pour la base B = I₃, si on écrit les coordonnées de la solution réalisable dans l'ordre y_i, , on obtient exactement le point (0, 0, 8, 7, 3).

• Itération 1

  y1	y2
  2	1	8	y3
  1	2	7	y4
  0	1	3	y5
  4	5	0

  Le vecteur ligne 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 :

  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₂. Pour déterminer la variable qui prend place, il va falloir calculer le paramètre et en déduire l'indice r. D'après le même tableau, on a :

  et donc r = 3.0 L'indice r correspond alors à la variable y₅. On décide de mettre en gras l'élément qui a permis de réaliser le minimum

  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 permet de décider que la variable, située sur la même ligne que 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 . 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 pour toutes les itérations du simplexe. En tenant compte de l'ordre des indices des variables de base et de , on obtient

  Par un simple calcul, on vérifie les égalités suivantes :

  Le tableau simplexe relatif à cette itération est

  y1	y5
  2	-1	5	y3
  1	-2	1	y4
  0	1	3	y2
  4	-5	15

  Noter que le vecteur peut être calculé aussi via la formule

  	=
  	=

  De même, la valeur Z = 15 qui correspond à Z(0, 3, 5, 1, 0) peut être obtenue à travers le résultat 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₁ entre dans la base au cours de l'itération 3. En ce qui concerne le nouveau paramètre , on a :

  Ainsi, la variable y₄ 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 et on calculera le coefficient , à chaque fois que cela s'avère nécessaire.

• Itération 3

  y4	y5
  -2	3	3	y3
  1	-2	1	y1
  0	1	3	y2
  -4	3	19

• Itération 4

  y4	y3
  		1
  		3
  		2
  -2	-1	22

• Conclusion
  On a

  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.

Pour l'Exemple 2, le (PL) considéré est

• 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 :

• On cherche un système de variables de base réalisable
  Prenons par exemple et montrons qu'il forme un système de variables de base réalisable. La matrice B associée à ce système vérifie :

  Les composantes de étant positives, la matrice B est une base réalisable. On calcule

  et

  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

  y2	y3
  		2
  4	-1	8
  12	-3	-12

• Itération 2

  y4	y3
  		3
  		2
  -3	0	12

  Le vecteur ligne é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 est égal à , qui est négatif. Donc, tout point de la forme est réalisable pour (FS) et ceci pour tout réel positif. Du fait que w_s = 0, la valeur de , qui est égale à , reste inchangée. Par suite, le point est optimal pour (FS) quelque soit le réel positif .

• Conclusion
  En ce qui concerne le (PL) associé, nous allons utiliser comme d'habitude le Théorème . Si on classe les composantes de dans l'ordre y_i, , on obtient . Par conséquent,

  est un point optimal pour (PL). Notons que est un vecteur directeur de la droite (AB) (voir Figure ). D'ailleurs, la demi-droite [AB) co''{4}ncide avec l'ensemble des points lorsque décrit .

Pour l'Exemple 3 :

• On écrit ce problème sous forme standard
  On a :

• On cherche un système de variables de base réalisable
  Il est facile de vérifier que B = I₂ est une base réalisable.

• Itération 1

  y1	y2
  -1	1	1
  -1	2	4
  1	1	0

• Conclusion
  Pour w_s = 1 écrit en gras, on a . Donc, d'après le Théorème , le probème vérifie :

  Plus précisément, pour tout réel , le point réalisable possède une valeur d'objectif égale à :

  dont la limite en vaut . Le point est égal à

  et par conséquent est un point réalisable du (PL) initial et ceci pour tout réel . Noter que décrit le demi axe [Ox₁) lorsque parcourt l'ensemble des réels positifs. D'après la Figure , tous ces points sont effectivement réalisables.

Tous les (PL) résolus jusqu'ici sont des formes canoniques puisque le domaine réalisable de chacun peut s'écrire sous la forme

Comme conséquence immédiate du Théorème , on peut affirmer que si 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 :

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.

A chaque itération de l'algorithme du simplexe, on est contraint à calculer la matrice et le vecteur ligne . Ces calculs exigent préalablement la détermination de la matrice inverse . Dans cette section, nous allons voir comment surmonter cette difficulté. Tout simplement, on évitera le calcul de . 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

Posons la matrice réelle rectangulaire (m,p) avec p = n-m. Aussi, on pose et où B_i (resp. N_i) désigne la 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 , que l'on note communément . Par conséquent, au cours de la prochaine itération, on aura

comme base réalisable et

Théorème

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 { } correspond à l'élément écrit en gras au niveau de la matrice .

ws	Z

Ensuite, le tableau simplexe qui suit sera rempli moyennant des transformations qui peuvent être résumées en ces termes :

• au niveau de { }, on aura .
• Tout élément de la colonne relative à { } devient .
• Tout élément de la ligne relative à { } devient .
• Tout élément en dehors de la ligne et de la colonne relative à { } sera transformé en . Dans cette dernière expression, on tient à préciser que ( resp. ) est l'élément de la matrice qui appartient à la même colonne (resp. ligne) que et la même ligne (resp. colonne) que { }.

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

On garde ici le même pivot . 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 avec celles de w_N. Pour cela, on pose :

Théorème

D'ores et déjà, on peut observer que les relation liant à w_N sont les mêmes que les relations entre une ligne et une ligne en dehors de la ligne du pivot . 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 . Les opérations qu'il faut appliquer sur w_j, , 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.

En ce qui concerne le vecteur , il a été indiqué d'avance qu'il peut être déterminé par les relations

Si on remplace par sa valeur , on obtient les mêmes formules qui régissent une colonne de 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 ou selon que le probème étudié soit de type maximisation ou minimisation. En tenant compte de l'expression de , il est facile de constater que la formule 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 , , w_N et Z :

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 variable de base du tableau simplexe en cours. De même, hbase(j) correspond à l'indice de la 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.

Exercice

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

VI-1-1 Cas d'une forme canonique

VI-1-2 Cas général

VI-1-3 Tableau récapitulatif

On considère un programme linéaire écrit sous forme canonique que l'on suppose de type maximisation :

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

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 :

Après un certain nombre d'opérations algébriques, on montre que le dual de est :

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.

Remarque

Théorème

Dans la pratique, il est souvent difficile de trouver deux points réalisables et de et tels que . 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

Remarque