UNIVERSITE DU LITTORAL

Maıtrise AES

Recherche operationnelle

Daniel DE WOLF

Dunkerque, Septembre 2003

Table des matieres

I La programmation lineaire et en nombres entiers 7

1 La programmation lineaire. 9

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Plan du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Un simple exemple . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Resolution graphique . . . . . . . . . . . . . . . . . . . . . . . 13

1.5 Formulation generale . . . . . . . . . . . . . . . . . . . . . . . 17

1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 Algorithme du Simplexe. 21

2.1 Principe de l’algorithme . . . . . . . . . . . . . . . . . . . . . . 21

2.2 Formes canoniques d’un programme lineaire. . . . . . . . . . . . 22

2.3 Notion de solution de base . . . . . . . . . . . . . . . . . . . . . 24

2.4 Initialisation de l’algorithme . . . . . . . . . . . . . . . . . . . . 26

2.5 Une iteration Simplexe . . . . . . . . . . . . . . . . . . . . . . . 27

2.5.1 Choix de la direction . . . . . . . . . . . . . . . . . . . . 27

2.5.2 Choix de la variable sortante . . . . . . . . . . . . . . . . 27

2.5.3 Calcul du nouveau sommet . . . . . . . . . . . . . . . . 28

2.5.4 Test d’optimalite . . . . . . . . . . . . . . . . . . . . . . 30

2.5.5 Chemin suivi par l’algorithme du Simplexe . . . . . . . . 31

2.6 Algorithme du Simplexe . . . . . . . . . . . . . . . . . . . . . . 32

3 L’algorithme du Simplexe en Tableaux 33

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3

4 Table des matieres

3.2 Notion de tableau Simplexe . . . . . . . . . . . . . . . . . . . . 34

3.3 Tableaux Simplexe et pivotage . . . . . . . . . . . . . . . . . . . 35

3.4 Algorithme du Simplexe en tableaux . . . . . . . . . . . . . . . . 40

3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4 Questions sur l’algorithme du Simplexe. 43

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Initialisation de l’algorithme . . . . . . . . . . . . . . . . . . . . 43

4.3 Determination de la variable entrante . . . . . . . . . . . . . . . 50

4.4 Determination de la variable sortante . . . . . . . . . . . . . . . 50

4.5 Arret apres un nombre fini d’iterations . . . . . . . . . . . . . . . 53

4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5 Analyse postoptimale. 57

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2 Variation par rapport au second membre . . . . . . . . . . . . . . 58

5.3 Variation des coefficients objectifs . . . . . . . . . . . . . . . . . 62

5.4 Cout reduit des variables hors base . . . . . . . . . . . . . . . . . 64

5.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6 La programmation en nombres entiers. 69

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.2 Formulation des problemes mixtes . . . . . . . . . . . . . . . . . 70

6.2.1 Problemes avec couts fixes . . . . . . . . . . . . . . . . . 70

6.2.2 Problemes avec contrainte logique . . . . . . . . . . . . . 71

6.2.3 Melange avec nombre limite d’ingredients . . . . . . . . 72

6.2.4 Choix parmi un nombre discret de valeurs . . . . . . . . . 73

6.3 Methode de branch and bound . . . . . . . . . . . . . . . . . . . 74

6.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Table des matieres 5

II Les modeles sur reseau, dynamiques et non lineaires. 81

7 Les modeles sur reseau 83

7.1 Le probleme de transport simple . . . . . . . . . . . . . . . . . . 84

7.1.1 Representation au moyen d’un graphe . . . . . . . . . . . 84

7.1.2 Formulation du probleme . . . . . . . . . . . . . . . . . 85

7.2 Planification de la production . . . . . . . . . . . . . . . . . . . 87

7.3 Probleme d’affectation optimale . . . . . . . . . . . . . . . . . . 89

7.4 Le probleme de transport general . . . . . . . . . . . . . . . . . 90

7.4.1 Probleme du plus court chemin . . . . . . . . . . . . . . 91

7.4.2 Probleme du flot maximum . . . . . . . . . . . . . . . . 92

7.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

8 Resolution du probleme de transport simple 95

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

8.2 Notion de cout reduit . . . . . . . . . . . . . . . . . . . . . . . . 95

8.3 Le probleme de transport simple . . . . . . . . . . . . . . . . . . 99

8.4 Resolution du probleme de transport simple . . . . . . . . . . . . 100

8.4.1 Resolution par le Simplexe . . . . . . . . . . . . . . . . 100

8.4.2 Resolution par la methode du stepping stone . . . . . . . 102

8.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

9 Resolution du probleme de transport general 107

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

9.2 Notion de reseau residuel . . . . . . . . . . . . . . . . . . . . . 107

9.3 Resolution du probleme de flot a cout minimum . . . . . . . . . . 108

9.3.1 Algorithme de plus courts chemins successifs . . . . . . . 109

9.4 Application au probleme d’affectation . . . . . . . . . . . . . . . 112

9.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

10 La programmation dynamique. 119

10.1 Le probleme du voyageur . . . . . . . . . . . . . . . . . . . . . 119

6 Table des matieres

10.2 Resolution des problemes dynamiques . . . . . . . . . . . . . . . 123

10.3 Un probleme d’affectation de ressources rares . . . . . . . . . . . 124

10.4 Application a la planification de la production. . . . . . . . . . . 126

10.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

11 Les modeles non lineaires 131

11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

11.2 Difficulte de resolution des problemes non lineaires . . . . . . . . 132

11.3 Difference avec la programmation lineaire . . . . . . . . . . . . . 133

11.4 Les problemes convexes . . . . . . . . . . . . . . . . . . . . . . 136

11.5 Conditions de Kuhn et Tucker . . . . . . . . . . . . . . . . . . . 138

11.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

12 Resolution des problemes non lineaires 143

12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

12.2 Programmation separable . . . . . . . . . . . . . . . . . . . . . 144

12.2.1 Resolution par la notion d’epigraphe . . . . . . . . . . . 146

12.2.2 Resolution par la notion d’enveloppe convexe . . . . . . . 147

12.3 La methode de Franck-Wolfe . . . . . . . . . . . . . . . . . . . 149

12.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

Partie I

La programmation lineaire et en nombresentiers

7

Chapitre 1

La programmation lineaire.

1.1 Introduction

L’objectif de ce cours est double. Il s’agit, d’une part, de donner une introductiona la formulation en modeles d’optimisation. Il s’agit, d’autre part, de presenterles techniques de resolution de ces problemes.

On parle de probleme d’optimisation lorsqu’il faut maximiser une fonctionsous contraintes. Par exemple, maximiser le benefice d’une entreprise sous lescontraintes de satisfaire la demande et de respecter la capacite de production.

Le cours est divise en deux parties correspondant a des types differents demodeles d’optimisation.

Dans la premiere partie du cours, nous nous concentrerons sur les problemeslineaires et les problemes en nombres entiers.

Nous commencerons par le cas des problemes lineaires, c’est-a-dire les proble-mes ou la fonction objectif et les contraintes sont purement lineaires. Lorsqu’il n’ya que deux variables de decision, un probleme lineaire peut etre resolu de manierepurement graphique. C’est ce que nous verrons dans ce chapitre. Lorsqu’il y a unplus grand nombre de variables, un algorithme mis en œuvre sous la forme d’unprogramme informatique s’avere necessaire. Il s’agit de l’algorithme du Simplexeque nous verrons au chapitre 2. Au chapitre 5, nous examinerons une question tresimportante : a savoir la sensibilite de la solution a des modifications de donnees.On parle d’analyse post-optimale.

Lorsque les variables doivent prendre des valeurs entieres, on parle de proble-mes en nombres entiers. On devrait a proprement parler de problemes lineaires ennombres entiers car on impose, en plus, aux contraintes et a la fonction objectifd’etre lineaires. Nous verrons au chapitre 6 une technique de resolution de cesproblemes : il s’agit de la methode de branch and bound.

Dans la seconde partie du cours, nous nous concentrerons sur les problemes

9

10 Chapitre 1. La programmation lineaire.

dynamiques et les problemes non lineaires.

Le chapitre 10 est consacre a la formulation et a la resolution des problemesdynamiques, c’est-a-dire ceux ou une decision strategique doit etre prise a chaqueetape. Une application typique est la planification de production ou a chaqueperiode de l’horizon de planification, on doit decider du niveau de production.

Lorsque les contraintes et/ou la fonction objectif sont non lineaires, on parlede problemes non lineaires. Nous verrons au chapitre 11 quelques methodes deresolution de ces problemes.

Il est a remarquer que toutes ces methodes de resolution etant mises en œuvredans des logiciels commerciaux, il ne viendrait plus a l’idee de les programmersoi-meme. Par exemple, le solveur d’Excel dispose d’une implementation de cesalgorithmes.

1.2 Plan du cours

Partie I : les problemes lineaires et en nombres entiers.

• La programmation lineaire.

• L’algorithme du Simplexe.

• Questions sur l’algorithme du Simplexe.

• L’analyse post-optimale.

• Les modeles en nombres entiers.

• Resolution des modeles en nombres entiers.

Partie II : les modeles sur reseau, dynamiques et non lineaires.

• Les modeles sur reseau.

• La programmation dynamique.

• Application a la planification de production.

• Les modeles non lineaires.

• Resolution des modeles non lineaires.

1.3 Un simple exemple

Nous prenons un exemple tire de Hillier et Lieberman [10]. Il s’agit d’une ent-reprise de fabrication de chassis qui envisage la production de deux nouveaux

Section 1.3. Un simple exemple 11

modeles au moyen des capacites residuelles de ses trois ateliers. Il s’agit respec-tivement d’un chassis en aluminium et d’un chassis en bois. Le premier produitnecessite le passage dans le premier atelier pour fabriquer le cadre en aluminium etdans le troisieme atelier ou le verre est monte sur le chassis. Tandis que le secondproduit necessite le passage dans le deuxieme atelier pour fabriquer le cadre enbois et dans le troisieme atelier ou le verre est monte sur le chassis. Les margesunitaires, les temps de fabrication de chacun des produits dans chacun des ateliersainsi que les capacites hebdomadaires residuelles de ces ateliers sont donnes autableau 1.1.

Produit 1 Produit 2 Capacite disponible

(heures/produit) (heures/produit) (heures/semaine)

Atelier 1 1 0 4

Atelier 2 0 2 12

Atelier 3 3 2 18

Marge 3$ 5$

Tableau 1.1: Marges, temps d’usinage et capacites.

La question qui se pose est la suivante : “Combien faut-il produire de chassisde chaque type par semaine pour maximiser le profit net ?”

La formulation d’un probleme d’optimisation comporte toujours les trois etapessuivantes :

1. choix des variables du modele;

2. formulation de l’objectif;

3. formulation des contraintes.

La premiere etape consiste a choisir les variables du probleme.

Definition 1.1 On appelle variable toute quantite utile a la resolution du problemedont le modele doit determiner la valeur.

Cette definition permet de differencier les variables des parametres, qui sont desdonnees qui peuvent varier, par exemple d’une periode a l’autre ou d’un scenarioa l’autre. Ici les quantites que le modele doit determiner sont les productions de

12 Chapitre 1. La programmation lineaire.

chassis par semaine. Notons donc :

x1 = nombre de chassis de type 1 produits par semaine,

x2 = nombre de chassis de type 2 produits par semaine.

La deuxieme etape consiste a formuler mathematiquement l’objectif.

Definition 1.2 On appelle fonction objectif d’un probleme d’optimisation le cri-tere de choix entre les diverses solutions possibles.

Ici l’entreprise desire maximiser son profit net. La marge etant de 3 pour le premiertype de chassis et de 5 pour le second, l’objectif s’exprime comme suit :

max z = 3x1 + 5x2

La troisieme etape est la formulation les contraintes du probleme.

Definition 1.3 On appelle contraintes du probleme toutes les relations limitantle choix des valeurs possibles des variables.

Ces relations peuvent etre de simples bornes sur les variables. Par exemple, lesquantite produites ne peuvent etre negatives. Mathematiquement :

x1, x2 ≥ 0.

Elles peuvent etre plus complexes comme les contrainte de capacite de produc-tion. Le temps pour assembler 1 chassis de type 1 dans l’atelier 1 est de 1 heureou il reste 4 heures disponibles. D’ou la contrainte de capacite de l’atelier 1 :

x1 ≤ 4

Semblablement, on peut construire les contraintes de capacites des deux autresateliers :

2x2 ≤ 12

3x1 + 2x2 ≤ 18

Il est alors tres utile de reprendre sous une forme condensee la formulationcomplete du probleme. Ici, on obtient la formulation suivante :

max z = 3 x1 + 5 x2

s.c.q.

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

x1 ≥ 0

x2 ≥ 0

(1.1)

Section 1.4. Resolution graphique 13

1.4 Resolution graphique

Comme annonce dans l’introduction, dans le cas de deux variables de decision,un probleme lineaire peut etre resolu de maniere purement graphique en suivant leprocessus en trois etapes qui suit.

La premiere etape de la resolution consiste a representer graphiquement laregion realisable.

Definition 1.4 On appelle region realisable, l’ensemble des valeurs de variablesde decision qui satisfont toutes les contraintes.

Dans le cas de l’exemple, c’est l’ensemble des points (x1, x2) satisfaisant lesinegalites de (1.1).

Graphiquement une inegalite telle que 3x1 + 2x2 ≤ 18 correspond a un demi-plan limite par la droite obtenue en prenant l’inequation a l’egalite (3x1+2x2 = 18).Lorsque l’on fait l’intersection des cinq demi-plans correspondant aux cinq inega-lites :

x1 ≤ 4 (1)

2x2 ≤ 12 (2)

3x1 + 2x2 ≤ 18 (3)

x1 ≥ 0 (4)

x2 ≥ 0 (5)

on obtient le polygone hachure a la figure 1.1. En economie, cet ensemble realisableest encore appele l’ensemble de production.

Generalisation. La notion de polyedre de Rn.

Plus generalement, si on a n variables, on ne parle plus de polygone, mais biende polyedre. En effet, la region de R

n correspondant aux solutions d’une inegalitelineaire du type suivant :

ak1x1 + ak2x2 + . . . + aknxn ≤ bk

est un demi-espace ferme situe d’un cote de l’hyperplan de Rn d’equation :

ak1x1 + ak2x2 + . . . + aknxn = bk.

Definition 1.5 On appelle polyedre de Rn l’ensemble des x ∈ R

n verifiant unsysteme d’inequations lineaires :

ak1x1 + ak2x2 + . . . + aknxn ≤ bk, k = 1, . . .p

14 Chapitre 1. La programmation lineaire.

10

8

6

4

2

0 2 4 6 8 x1

x2

(1)(2)

(3)

(4)

(5)

Figure 1.1: Ensemble de production.

A titre d’illustration, le polyedre de R3 defini par les inegalites suivantes :

x1 + x2 + x3 ≤ 1

x1, x2, x3 ≥ 0

est represente a la figure 1.2 par le prisme OABC ou O note l’origine des axes.

x1

x3

x2

A

C

BO

Figure 1.2: Hyperfaces d’un polyedre dans R3.

On voit ici clairement que le systeme est sous-determine. On va devoir choisirentre ces differents plans de production. Pour ce faire, et c’est la deuxieme etapede la resolution, on va representer graphiquement des lignes d’isovaleur de lafonction objectif :

z = 3x1 + 5x2.

Section 1.4. Resolution graphique 15

En effet, on remarquera que l’expression de la fonction objectif fait intervenir troisvariables et ne peut donc etre representee que dans l’espace. Pour se ramener dansle plan, on va considerer des valeurs successives de l’objectif :

z = k.

Ce qui correspond graphiquement a des droites paralleles

3x1 + 5x2 = k.

Les points d’une de ces droites sont donc le lieu de tous les points donnant la memevaleur du profit (d’ou le nom de droite d’isovaleur de la fonction objectif). Ceciest fait a la figure 1.3 ou l’on a represente z = 10, 20 et 36.

10

8

6

4

2

0 2 6 8 x1

x2

z = 36

z = 20z = 10

(2,6)

(4 ,3)

Figure 1.3: Droites d’isoprofit.

Enfin, et c’est la troisieme etape de la resolution, l’optimum sera determinegraphiquement comme le plan de production situe sur la droite d’isoprofit la pluselevee, c’est-a-dire celle qui donne le profit le plus eleve. On voit a la figure 1.3qu’il s’agit du point

x∗ = (2, 6).

Justifions ce choix. Comme on maximise le profit on a interet a prendre la droited’isovaleur la plus elevee possible. Bien sur, il faut que le plan de production soitencore realisable : autrement dit, il faut se restreindre a la region realisable. On aalors la tres important remarque suivante :

Observation 1 :Pour maximiser l’objectif, il faut prendre la droite d’isovaleur de l’objectif quitouche encore la region realisable et qui donne la plus grande valeur a l’objectif.

16 Chapitre 1. La programmation lineaire.

Sur base de cet exemple, on tire une deuxieme observation :

Observation 2 :On constate que la solution optimale est a un sommet de la region realisable.

On peut alors se demander si la solution optimale sera toujours a un sommet dela region realisable. En fait, lorsque la ligne d’iso-marge est parallele a un cote dupolygone, on a que tout le cote du polygone est optimal. Par exemple, si l’objectifavait ete z = 3x1 + 2x2, tout le segment entre (2,6) et (4,3) aurait ete optimum.

Observation 3 :Meme si tout un cote du polygone est optimal, on peut toujours choisir une solutionoptimale correspondant a un sommet.

En conclusion, on peut voir qu’il suffit d’evaluer la valeur de l’objectif enchacun des sommets pour determiner l’optimum d’un probleme lineaire.

Mais on peut aller plus loin encore pour limiter le nombre de sommets aexaminer en se basant sur la quatrieme observation suivante.

Observation 4 :Le long d’un cote du polygone, la valeur de l’objectif peut etre soit constante, soitstrictement croissante, soit strictement decroissante.

On peut donc suggerer l’algorithme suivant :

Algorithme 1.1 Principe de l’algorithme du Simplexe.

i) Choisir comme point de depart un sommet x∗ de la region realisable.

ii) Determiner les cotes passant par ce sommet x∗. Trouver un cote le longduquel z croıt. S’il n’y en n’a pas, STOP : le x∗ courant est optimal.

iii) Determiner le sommet y∗ a l’autre bout du cote et poser x∗ = y∗. Retour enii).

Nous allons voir au chapitre suivante comment generaliser cet algorithme au casde R

n : on obtient alors l’algorithme du Simplexe. Mais avant cela, generalisonsla notion de cote et de sommet et voyons la formulation generale d’un problemelineaire.

Generalisation. Notion de faces d’un polyedre.On peut egalement generaliser les notions de cotes et de sommet d’un polygone.Il s’agit, en fait, de cas particuliers de la notion de face d’un polyedre.

Definition 1.6 On appelle face d’un polyedre l’ensemble des points appartenantau polyedre et qui verifient un certain nombre de contraintes a l’egalite :

ak1x1 + ak2x2 + . . . + aknxn = bk, k ∈ I ⊆ {1, . . .p}

Section 1.5. Formulation generale 17

Suivant la dimension de l’ensemble obtenu, on a des noms particuliers.

Definition 1.7 Dans l’espace Rn, on appelle hyperface, une face de dimension

n − 1, arete, une face de dimension 1 et sommet, une face de dimension 0.

Reprenons l’exemple du polyedre OABC ci-dessus. Le triangle ABC est l’en-semble des points du polyedre verifiant une contrainte a l’egalite (x1+x2+x3 = 1).Il s’agit donc d’une face. Elle est de dimension 2 et donc il s’agit donc d’une hyper-face. La droite AB est l’ensemble des points du polyedre verifiant 2 contraintes al’egalite (x1 + x2 + x3 = 1 et x3 = 0). Elle est de dimension 1 : il s’agit doncd’une arete. Le point C est l’intersection de 3 (n = 3) hyperplans delimitants, ilest de dimension 0 : c’est donc un sommet.

1.5 Formulation generale

Nous allons generaliser l’exemple introductif. Considerons qu’il y a n produitspossibles (ici n = 2) necessitant l’utilisation eventuelle de m ressources limitees(ici m = 3 ateliers de capacite limitee). Notons cj , l’accroissement du profit parunite de produit j et bi, la quantite de ressource i disponible. Notons par aij laquantite de ressource i consommee pour produire une unite de produit j. Lesdonnees numeriques du probleme sont resumees au tableau 1.2.

Ressource Produit Capacite

1 2 . . . n disponible

1 a11 a12 . . . a1n b1

2 a21 a22 . . . a2n b2

...

m am1 am2 . . . amn bm

marge c1 c2 . . . cn

Tableau 1.2: Donnees numeriques du probleme.

Un programme lineaire peut donc se formuler en general de la maniere sui-vante. On veut determiner le point qui maximise un critere, fonction lineairedes variables de decision, tout en respectant des contraintes, elles aussi fonctions

18 Chapitre 1. La programmation lineaire.

lineaires des variables de decision. On peut ecrire :

max z = c1x1 + c2x2 · · · + cnxn,

s.c.q.

a11x1 + a12x2 · · · + a1nxn ≤ b1,

a21x1 + a22x2 · · · + a2nxn ≤ b2,...

......

...

am1x1 + am2x2 · · · + amnxn ≤ bm,

x1 ≥ 0,

x2 ≥ 0,. . .

xn ≥ 0.

On a donc un probleme a n variables et a m + n contraintes d’inegalite, les ndernieres etant celles de non negativite des variables.

Matriciellement, le probleme peut s’ecrire comme

max z = cTx,

s.c.q.

Ax ≤ b,

x ≥ .

(1.2)

avec A matrice (m × n) b vecteur (m × 1)c vecteur (n × 1) x vecteur (n × 1).

Definition 1.8 Tout point x verifiant les contraintes de (1.2) est dit une solutionrealisable pour le probleme lineaire.

Notons par S la region realisable :

S = {x ∈ Rn|Ax ≤ b, x ≥ 0} .

Parmi ces solutions realisables, celles qui maximisent l’objectif sont appeleessolutions optimales.

Definition 1.9 Tout point x∗ ∈ S et tel que

∀x ∈ S, cTx∗ ≥ cTx,

est dit une solution optimale pour le probleme lineaire (1.2).

Section 1.6. Exercices 19

1.6 Exercices

1.1. Recyclage du papier. Une societe de tri de dechets et recyclage de pa-pier peut se fournir en dechets aupres de deux villes. Son role consiste aseparer les listes d’ordinateur et les journaux. La repartition entre menageset societes est differente d’une ville a l’autre expliquant un pourcentagedifferent de listes d’ordinateur et de journaux dans les dechets. Ces pour-centages ainsi que la quantite maximum de dechets que peuvent fournir paran ces deux villes sont reprises au tableau suivant :

Ville Listes (%) Journaux (%) Offre (tonnes par an)

Ville 1 5 20 10.000

Ville 2 15 30 20.000

La societe offre aux villes un prix de 35 EURO par tonne de dechet. Elledoit decider du montant optimal de dechets a acheter a chaque ville pourminimiser son cout d’achat. Pour couvrir ses frais fixes, la societe doit aumoins collecter 1.500 tonnes de listing d’ordinateur par an. Au dela de 6.000tonnes de journaux mis sur le marche par an, le prix que la societe recoitpour la vente de journaux chute et donc la compagnie ne desire pas vendreplus que cette quantite. Combien la societe doit-elle acheter de dechets paran a chacune des villes ?

(a) Formuler mathematiquement le probleme (choix des variables, expres-sion des contraintes et de l’objectif);

(b) Determiner graphiquement le plan d’achat optimal et en deduire le coutd’achat minimum.

1.2. Planification de production sur cout variable. Une entreprise fabriquedeux produits P1 et P2. Chaque produit doit passer les deux ateliers d’usinageet de finition. Le mois dernier, 500 unites de P1 ont ete produites grace a750 heures d’usinage et 250 heures de finition. De meme, 700 unites deP2 ont ete produites, necessitant 700 heures d’usinage et 350 heures definition. L’entreprise dispose egalement d’une section administration. Unepartie du cout de production est independante du nombre d’heures passees ala production (les frais fixes), une partie est directement proportionnelle aunombre d’heures passees a la production (les frais variables). Le mois passe,

20 Chapitre 1. La programmation lineaire.

on a observe la repartition suivantes entre frais fixes et frais variables :

Section frais fixes frais variables

Administration 50.000 0

Usinage 60.000 11.600

Finition 40.000 6.000

Il y a un cout de conditionnement de 8 euros l’unite pour P1 et de 6 eurospour P2. Les prix de vente sont de 55 euros et 43 euros respectivement.

(a) Calculer les marges sur couts variables (difference entre prix de venteet cout variable de production) par unite de chacun des deux produits.Indication : calculer d’abord le prix de l’heure dans chacun des atelierset le temps necessaire dans chacun des ateliers par produit.

(b) Les capacites de production sont de 1.200 heures par mois pour l’usi-nage et de 500 heures pour la finition. Formuler le programme lineairecorrespondant a la maximisation de la marge sur couts variables.

(c) Determiner graphiquement la solution optimale.

Chapitre 2

Algorithme du Simplexe.

2.1 Principe de l’algorithme

L’algorithme du Simplexe permet la determination d’une solution optimale d’unprogramme lineaire lorsqu’une telle solution existe. Dans le cas contraire, l’al-gorithme, lors du passage par une phase preliminaire appelee phase I, determinel’absence de solution realisable. Nous verrons la phase I au chapitre 4.

Rappelons la formulation de l’exemple introductif :

max z = 3 x1 + 5 x2

s.c.q.

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

x1 ≥ 0

x2 ≥ 0

(2.1)

dont la representation graphique est donnee a la figure 2.1.

Le principe de l’algorithme du Simplexe est de determiner une solution opti-male en allant de sommet en sommet adjacent. Partant du point (0,0), l’algorithmeva determiner une arete le long de laquelle l’objectif s’accroıt : par exemple, l’areteen direction de (0,6). Ensuite, on va aller jusqu’au bout de cette arete : c’est-a-direau sommet (0,6). Et le processus continue de maniere iterative. On determine unearete le long de laquelle l’objectif s’accroıt : l’arete en direction de (2,6). On vajusqu’au bout de l’arete et, la, on constate que tout mouvement, en arriere vers (0,6)ou en avant vers (4,3), conduit a diminuer l’objectif. On est donc a l’optimum.

Nous allons maintenant voir comment effectuer ces memes operations en uti-lisant uniquement l’algebre. C’est l’objet de l’algorithme du Simplexe.

21

22 Chapitre 2. Algorithme du Simplexe.

10

8

4

2

2 8

3x1 + 2x2 = 18

x1 = 4

x1 = 0

2x2 = 12

x2 = 0

(0,9)

(0,6)(2,6)

(4,3)

(4,0)(0 ,0)

(6 ,0)

(4 ,6)

Figure 2.1: Un exemple de programme lineaire

2.2 Formes canoniques d’un programme lineaire.

La forme canonique d’un programme lineaire dans l’espace des variables originalesavait ete vue au chapitre 1. Elle correspond a la forme matricielle suivante :

max z = cTx,

s.c.q.

Ax ≤ b,

x ≥ .

avec A matrice (m × n) b vecteur (m × 1)c vecteur (n × 1) x vecteur (n × 1).

Il s’agit d’un probleme avec n variables et m + n contraintes d’inegalite.Cependant, parmi ces dernieres , il y am contraintes qui peuvent etre des contraintesd’inegalite generales et n qui ne sont que des contraintes de positivite des variables.

Observons qu’il est toujours possible de transformer une contrainte d’inegalitegenerale en une contrainte d’egalite par ajout d’une variable a laquelle on imposed’etre non negative. Considerons, par exemple, la contrainte

3x1 + 2x2 ≤ 18.

Imposer que le membre de gauche soit inferieur ou egal au membre de droite,revient a dire qu’il faudrait ajouter une quantite non negative au membre de gauchepour qu’il y ait egalite :

3x1 + 2x2 + x3 = 18,

avec la condition que la variable x3 soit non negative

x3 ≥ 0.

Section 2.2. Formes canoniques d’un programme lineaire. 23

Cette quantite represente un deficit ou un ecart. Comme cet ecart peut varier, onl’appelle variable d’ecart.

Definition 2.1 La variable d’ecart est la quantite qui, ajoutee au membre degauche d’une contrainte, permet de transformer la contrainte en egalite.

Bien que dans la forme canonique on ne considere que des contraintes d’ine-galites generales du type inferieur ou egal, on peut aussi envisager de transformerdes contraintes generales du type superieur ou egal en egalite. Lorsqu’on impose

2x1 + x2 ≥ 4,

on impose que le membre de gauche depasse le membre de droite. Il y a doncaussi un ecart qui s’avere cette fois etre un surplus. Pour revenir a l’egalite, il fautretrancher une quantite non negative du membre de gauche.

2x1 + x2 − x3 = 4,

avec x3 ≥ 0.

Appliquons ceci au probleme (2.1). On obtient le probleme sous forme standardavec egalites suivant :

max z = 3x1 + 5x2

s.c.q.

x1 +x3 = 4

2x2 +x4 = 12

3x1 +2x2 +x5 = 18

x1, x2, x3, x4, x5 ≥ 0

(2.2)

Remarquons qu’il y a equivalence totale entre les deux formes. En effet,d’une part, toute solution realisable du probleme (2.1) peut etre augmentee en unesolution realisable pour le probleme (2.2). Toute solution realisable du probleme(2.2) peut etre tronquee en une solution realisable pour le probleme (2.1). Comme,d’autre part, les fonctions objectifs sont identiques, on a bien equivalence entre lesdeux problemes.

Illustrons cette correspondance entre solutions : a la solution (3,2) du probleme(2.1) correspond la solution augmentee (3,2,1,8,5) du probleme (2.2). Dans l’autresens, il suffit de tronquer la solution dans R

5 en ne retenant que ses deux premierescomposantes.

24 Chapitre 2. Algorithme du Simplexe.

2.3 Notion de solution de base

On remarquera que les egalites du probleme (2.2) forment un systeme de m =3egalites en n + m = 2 + 3 = 5 inconnues. Donc la valeur de n = 2 variables peutetre fixee arbitrairement. Par exemple, dans le systeme d’egalites :

x1 +x3 = 4

2x2 +x4 = 12

3x1 +2x2 +x5 = 18

(2.3)

les deux variables x1 et x2 peuvent etre fixees a zero. On dit qu’elles sont miseshors base.

Definition 2.2 On appelle variables hors base (v.h.b.) les n variables de Rn+m

fixees a zero. Les m variables restantes sont appelees variables de base (v.b.).

Dans l’exemple, les variables de base sont donc x3, x4 et x5 dont on peut lirela valeur dans (2.3) :

x3 = 4

x4 = 12

x5 = 18

Definition 2.3 On appelle solution de base une solution ou en ayant choisi nvariables hors base, on obtient une solution unique en resolvant les m contraintesd’egalites obtenues en ajoutant les variables d’ecart.

Definition 2.4 On appelle solution de base realisable une solution de base qui,en plus, verifie les contraintes de positivite.

Dans l’exemple, la solution de base suivante :

x1 = 0, x2 = 0 variables hors base

x3 = 4, x4 = 12, x5 = 18 variables de base

est realisable car toutes les variables de base sont positives.

Le lien entre l’algebre et la geometrie est alors donne par la propriete suivante.

Propriete 2.1 La notion geometrique de sommet du polygone correspond a lanotion algebrique de solution de base realisable.

Section 2.3. Notion de solution de base 25

On peut verifier cette propriete sur l’exemple. A la figure 2.1, les sommets(0,0), (0,6), (2,6), (4,3), (4,0) correspondent a des solutions de base realisablestandis que les points (0,9), (4,6) et (6,0) correspondent a des solutions de base nonrealisables. Cette correspondance est etablie au tableau 2.1.

v.h.b. (x1, x2) (x3, x4, x5) sommet ?

x1, x2 (0, 0) (4, 12, 18) oui

x1, x4 (0, 6) (4, 0, 6) oui

x1, x5 (0, 9) (4,−6, 0) non

x4, x5 (2, 6) (2, 0, 0) oui

x3, x4 (4, 6) (0, 0,−6) non

x3, x5 (4, 3) (0, 6, 0) oui

x2, x3 (4, 0) (0, 6, 6) oui

x2, x5 (6, 0) (−2, 12, 0) non

Tableau 2.1: Correspondance entre solution de base realisable et sommet.

Nous avons deja annonce que l’algorithme du Simplexe consiste a aller desommet en sommet adjacent. Interprete algebriquement, cela revient a considererun passage d’une solution de base realisable a une autre solution de base realisable.La notion d’adjacence doit etre etendue aux solutions de base.

Definition 2.5 On appelle solutions de base adjacentes deux solutions de basedont les variables de base sont les memes sauf une qui est de base dans la premierebase et hors base dans la seconde.

Dans l’exemple, les deux solutions de base suivantes sont adjacentes :

x1 = 0, x1 = 0,

x2 = 0, x2 = 6,

x3 = 4, x3 = 4,

x4 = 12, x4 = 0,

x5 = 18, x5 = 6

car elles ne different que par une seule variable hors base. Par contre les solutionssuivantes :

x1 = 0, x1 = 2,

x2 = 0, x2 = 6

26 Chapitre 2. Algorithme du Simplexe.

ne sont pas adjacentes puisqu’elle different par plus d’une variable hors base. Onpeut le verifier a la figure 2.1.

Propriete 2.2 La notion geometrique de sommets adjacents correspond a la no-tion algebrique de solutions de base realisables adjacentes.

2.4 Initialisation de l’algorithme

La question qui se pose est : “Comment choisir le point de depart ?”

Si le probleme est mis sous forme d’inegalites avec bi ≥ 0, i = 1, . . .n, il suffitde prendre l’origine comme point de depart. Dans l’exemple, cela donne :

(x1, x2) = (0, 0)

En termes algebriques, toutes les variables originales sont mises hors base. Auto-matiquement , dans le systeme d’egalites :

x1 +x3 = 4

2x2 +x4 = 12

3x1 +2x2 +x5 = 18

,

on lit la valeur des variables de base :

x3 = 4

x4 = 12

x5 = 18

D’ou la solution de base realisable de depart :

(0, 0, 4, 12, 18).

Remarquons que si un membre de droite avait ete negatif ou si une contrainte avaitete sous forme d’egalite, on n’aurait pas pu demarrer ainsi. Ces embuches peuventetre levees en passant par une phase preliminaire appelee phase I de l’algorithmedu Simplexe (voir chapitre 4).

Que vaut la fonction objectif pour cette premiere solution de base ?

z = 3x1 + 5x2 = 3 · 0 + 5 · 0 = 0,

c’est-a-dire une marge beneficiaire nulle, ce qui n’est pas etonnant vu que celacorrespond a une production nulle des deux produits.

Section 2.5. Une iteration Simplexe 27

2.5 Une iteration Simplexe

Pour rappel, le principe de l’algorithme du Simplexe consiste a se deplacer desommet en sommet adjacent de facon a ameliorer la fonction objectif. On va doncse deplacer a partir de notre solution de base de depart vers une solution de baserealisable en suivant une arete le long de laquelle l’objectif s’accroıt.

2.5.1 Choix de la direction

La question qui se pose est alors : comment choisir la direction ? Remarquezqu’algebriquement, cette question se formule de maniere equivalente par : quellevariable hors base va entrer en base ?

Le critere de selection de la variable entrante est de prendre la variable horsbase qui fournit le plus fort taux d’augmentation de la fonction objectif :

z = 3x1 + 5x2.

Pour une augmentation unitaire de x1, z augmente de 3. Pour une augmentationunitaire de x2, z augmente de 5.

Le critere de selection de la variable entrante est donc le suivant : on choisitla variable avec le coefficient objectif le plus eleve.

Remarquez que pour pouvoir appliquer ce critere simple (choisir la variablede coefficient objectif le plus eleve), la fonction objectif z doit etre exprimee enfonction des seules variables hors base.

2.5.2 Choix de la variable sortante

La question qui se pose est : quand s’arreter le long de la direction ?

Geometriquement, on se dirige sur l’axe x2 et on s’arete en (6,0), a la premierecontrainte rencontree. Algebriquement, on constate qu’en ce point la variabled’ecart x4 s’annule et aller au dela conduirait a la rendre negative. On va donc pous-ser x2 le plus loin possible, tant que les variables de base restent non negatives.

Le critere de selection de la variable sortante est donc le suivant : prendrecomme variable sortante la premiere variable de base a s’annuler.

En maintenant x1 hors base dans (2.3), on obtient la variation des variables debase en fonction de x2 :

x3 = 4 ≥ 0

28 Chapitre 2. Algorithme du Simplexe.

x4 = 12 − 2x2 ≥ 0

x5 = 18 − 2x2 ≥ 0

ou encore :

x2 ≤ 12

2= 6

x2 ≤ 18

2= 9

On en conclut que la variable sortante est x4, c’est-a-dire la premiere quis’annule (pour x2 = 6).

De maniere generale, on calcul le minimum du rapport du coefficient du membrede droite sur le coefficient de la variable entrante dans la meme ligne lorsquecelui-ci est positif. La variable sortante est celle dont on lit la valeur dans laligne ou ce minimum se produit.

2.5.3 Calcul du nouveau sommet

La question qui se pose est : comment calculer la nouvelle solution de base ?

On va y repondre en utilisant la resolution de systemes. Plus precisement, onva calculer la nouvelle solution de base en explicitant le systeme (2.3) en fonctiondes nouvelles variables de base.

Ceci peut etre fait au moyen de deux types d’operations qui ne modifient pasl’ensemble des solutions d’un systeme d’equations :

1. Multiplier une egalite par une constante non nulle;

2. Additionner un multiple d’une equation a une autre equation.

Appliquons ceci a l’exemple. Ajoutons au systeme de depart (2.3) en premiereligne la definition de la fonction objectif :

z −3x1 −5x2 = 0 (0)

x1 +x3 = 4 (1)

2x2 +x4 = 12 (2)

3x1 +2x2 +x5 = 18 (3)

Donc x2 remplace x4 comme variable de base. On veut donc expliciter x2 dansla contrainte (2) en lieu et place de x4. Pour ce faire, il faut :

Section 2.5. Une iteration Simplexe 29

1. Amener un 1 comme coefficient de x2 dans (2). Autrement dit, la nouvellecontrainte notee (2’) est l’ancienne (2) multipliee par 1/2 :

(2′) = (2) × 1

2

2. Eliminer x2 des autres equations. Ceci en retranchant a la contrainte (3) lacontrainte (2) et en ajoutant a l’objectif (0) cinq fois la nouvelle contrainte(2’) :

(3′) = (3) − (2)

(0′) = (0) + 5 × (2′)

Le nouveau systeme est donc le suivant :

z −3x1 +52x4 = 30 (0′)

x1 +x3 = 4 (1)

x2 +12x4 = 6 (2′)

3x1 −x4 +x5 = 6 (3′)

ou l’on peut lire directement (en se souvenant que x1 et x4 sont hors basedonc nulles) :

z = 30

x3 = 4

x2 = 6

x5 = 6

On en deduit la valeur de la nouvelle solution de base :

(x1, x2, x3, x4, x5) = (0, 6, 4, 0, 6)

qui donne la nouvelle valeur de l’objectif :

z = 30.

Remarquez que les operations d’elimination de x2 des lignes autres que ladeuxieme se font obligatoirement en retranchant a chacune de ces lignes un mul-tiple de la deuxieme ligne. Toute autre operation detruirait les colonnes de lamatrice identite dans le systeme resultant comme on peut le constater en essayant,par exemple, de faire :

(3′) = −1 × (3) + (2).

30 Chapitre 2. Algorithme du Simplexe.

2.5.4 Test d’optimalite

La question qui se pose maintenant est la suivante : comment determiner le faitd’etre optimum.

Un sommet est optimal si tous les sommets adjacents donnent des valeursinferieures ou egales a la fonction objectif. Comment peut-on voir s’il existeencore un sommet adjacent profitable ?

Pour repondre a cette question, nous allons utiliser la ligne de definition del’objectif. L’equation (0’) se recrit :

z = 30 + 3x1 −5

2x4.

Comme x1 a un coefficient positif, il est interessant de faire entrer x1 en base.

Le critere d’arret sera donc le suivant : la solution de base courante est opti-male si tous les coefficients objectif sont negatifs ou nuls lorsque z est exprimeeen fonction des seules variables hors base.

Effectuons donc la seconde iteration de l’algorithme du Simplexe. Au vu de

z = 30 + 3x1 −5

2x4.

on selectionne donc pour la variable entrante x1. En effet, c’est la variable avecle plus grand coefficient objectif, et d’ailleurs la seule possible.

Pour determiner la variable sortante, etudions la variation des variables debase en fonction d’une augmentation de x1 :

x3 = 4 − x1

x2 = 6

x5 = 6 − 3x1

La variable sortante est x5, c’est elle qui est la premiere a s’annuler (pour x1 = 2).

Pour calculer le nouveau sommet, on exprime le systeme en fonction des nou-velles variables de base (x1 prend la place de x5) :

z +32x4 +x5 = 36

x3 +13x4 −1

3x5 = 2

x2 +12x4 = 6

x1 −13x4 +1

3x5 = 2

Section 2.5. Une iteration Simplexe 31

Donnant la nouvelle solution de base realisable :

(2, 6, 2, 0, 0)

Appliquons a nouveau le test d’optimalite. La ligne objectif s’ecrit :

z = 36 − 3

2x4 − x5.

Comme tous les coefficients objectifs sont negatifs, la solution courante

x∗1 = 2

x∗2 = 6

est optimale. Elle donne sa valeur maximale a l’objectif qui est de :

z∗ = 36.

Nous verrons au chapitre suivant voir une autre facon de presenter les memescalculs. Il s’agit de la presentation du Simplexe en tableaux.

2.5.5 Chemin suivi par l’algorithme du Simplexe

On peut suivre a la figure 2.1 le chemin emprunte par l’algorithme du Simplexe.Partant du sommet (0,0), la premiere iteration consiste a aller au sommet (0,6).La second iteration consiste a rejoindre le sommet (2,6). La troisieme iterationconsiste a constater que l’on est a l’optimum.

Nous verrons au chapitre 4 les differents problemes qui peuvent se produire lorsde l’execution de l’algorithme du Simplexe. Ces problemes peuvent se produiredurant les trois etapes de l’algorithme :

1. Initialisations. Pourra-t-on toujours trouver une solution de base de departrealisable ?

2. Iterations. Pourra-t-on, a chaque iteration, trouver une variable entrante ?Pourra-t-on, a chaque iteration, trouver une variable sortante ?

3. Terminaison. L’algorithme va-t-il converger en un nombre fini d’etapes ?

Mais avant cela donnons un resume de l’algorithme du Simplexe.

32 Chapitre 2. Algorithme du Simplexe.

2.6 Algorithme du Simplexe

Terminons en donnant une description schematique de l’algorithme du Simplexe.

Algorithme 2.1 Algorithme du Simplexe.

Pas 0. Initialisations.

• Ajouter les variables d’ecart.

• Selectionner les variables originales comme variables hors base.

Pas 1. Choix de la variable entrante.

• Choisir comme variable entrante la v.h.b. donc le coefficient objectifest le plus eleve lorsque z est exprimee en fonction des seules v.h.b.

• Si tous sont negatifs ou nuls, alors stop. Le tableau courant decrit unesolution optimale.

• Sinon, soit e l’indice de cette variable entrante.

Pas 2. Choix de la variable sortante.

• La variable sortante est la premiere a s’annuler : c’est celle pour laquellele minimum est atteint dans :

bs

ase

= mini|aie>0

bi

aie

Soit s l’indice de la ligne correspondante.

Pas 3. Determiner la nouvelle solution de base :

• Diviser toutes les coefficients de la ligne s par ase.

• Eliminer xe des autres lignes par soustraction d’un multiple de la lignes.

• Retour au Pas 1.

Chapitre 3

L’algorithme du Simplexe en Tableaux

3.1 Introduction

Nous avons vu au chapitre precedent une presentation algebrique de l’algorithmedu Simplexe. Pour rappel, il s’agit, partant d’une solution de base (correspondanta un sommet de la region realisable), a chaque iteration de

1. choisir comme variable entrante, celle de coefficient le plus eleve dans laligne objectif (ce qui correspond a choisir la direction assurant plus grandtaux d’accroissement a la fonction objectif);

2. choisir comme variable sortante, la premiere variable de base a s’annuler(ce qui correspond a la rencontre de la premiere contrainte dans la directionchoisie);

3. faire le pivotage : la variable entrante prend la colonne de la variable sortantedans le systeme d’equation, en ce compris dans l’expression de la fonctionobjectif.

Nous allons maintenant voir une autre facon de presenter les memes calculs. Ils’agit de la presentation du Simplexe en tableaux.

Nous verrons au chapitre suivant les embuches que l’on peut rencontrer achacune des etapes de l’algorithme.

On effectue generalement les calculs sur le tableau des coefficients qui portele nom de tableau Simplexe. Mais il faut bien garder a l’esprit que ce tableau etles operations que l’on va y effectuer ne sont qu’une traduction des operations surle systeme d’equations algebriques correspondantes.

33

34 Chapitre 3. L’algorithme du Simplexe en Tableaux

3.2 Notion de tableau Simplexe

Definition 3.1 Un tableau Simplexe est constitue des coefficients des equationsalgebriques sans le nom des variables. On aura donc :

1. les coefficients de la fonction objectif;

2. les coefficients des variables dans le membre de gauche des contraintes;

3. les coefficients du membre de droite.

ou l’on separe les coefficients de objectif des contraintes d’une barre horizontaleet les coefficients du membre de gauche des contraintes des coefficients du membrede droite par une barre verticale.

Reprenons l’exemple du chapitre 1. Sa formulation est reprise ci-dessous :

max z = 3 x1 + 5 x2

s.c.q.

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

x1 ≥ 0

x2 ≥ 0

Le systeme de depart :

z −3x1 −5x2 = 0

x1 +x3 = 4

2x2 +x4 = 12

3x1 +2x2 +x5 = 18

se met sous la forme du tableau suivant :

z x1 x2 x3 x4 x5

1 −3 −5 0 0 0 0

0 1 0 1 0 0 4

0 0 2 0 1 0 12

0 3 2 0 0 1 18

Section 3.3. Tableaux Simplexe et pivotage 35

ou l’on a ajoute au dessus du tableau le nom des variables pour voir a quelle variablecorrespond chaque colonne du tableau.

Plusieurs caracteristiques d’un tableau sont a remarquer.

• Tout d’abord les valeurs du membre de droite donnent les valeurs courantesdes variables de base.

• Ensuite la premiere ligne donne l’oppose des coefficients objectif.

• Enfin, le dernier coefficient premiere ligne donne la valeur courante del’objectif.

• On identifie des variables de base a une colonne de coefficient de la matriceidentite et a un coefficient objectif nul.

On en deduit la solution courante :

(x1, x2, x3, x4, x5) = (0, 0, 4, 12, 18)

3.3 Tableaux Simplexe et pivotage

A la premiere iteration, on selection comme variable entrante la variable x2 decoefficient le plus negatif dans la ligne objectif. On indique ceci dans le tableauen encadrant la colonne de la variable entrant que l’on appelle la colonne pivot :

z x1 x2 x3 x4 x5

1 −3 −5 0 0 0 0

0 1 0 1 0 0 4

0 0 2 0 1 0 12

0 3 2 0 0 1 18

On selectionne la variable sortante comme etant la variable de base qui s’annule lapremiere. Comme nous l’avons vu au chapitre precedent, cela revient a calculer leminimum du rapport du coefficient du membre de droite de chaque contrainte surle coefficient correspondant de la colonne pivot lorsque ce dernier est strictementpositif :

min{−,

12

2,18

2

}= 6.

Dans le cas ou le coefficient dans la colonne entrante est negatif ou nul, la lignen’entre pas en compte dans le calcul du minimum. Illustrons ceci sur un exemple.

36 Chapitre 3. L’algorithme du Simplexe en Tableaux

Supposons que le coefficient de x2 dans la premiere contrainte soit -1 a la place de0. L’equation correspondante se recrit de maniere equivalente comme suit :

x1 = 4 + x2

Quelle que soit la valeur de x2 > 0, la variable de base x1 reste positive.

La variable sortante est alors la variable de base dont la valeur se lit dans laligne ou le minimum se produit : ici, il s’agit de la deuxieme ligne et donc de lavariable x4. Il suffit, dans le cas present, de chercher la colonne identite dont lecoefficient 1 est dans la deuxieme ligne. Elle correspond bien a la variable x4.

On encadre alors la ligne ou le minimum se produit. Cette ligne recoit le nomde ligne pivot :

z x1 x2 x3 x4 x5

1 −3 −5 0 0 0 0

0 1 0 1 0 0 4

0 0 2 0 1 0 12

0 3 2 0 0 1 18

Definition 3.2 On appelle element pivot le coefficient situe a l’intersection de lacolonne pivot et de la ligne pivot.

C’est donc le centre de la croix ainsi formee par la ligne et la colonne pivot.

Le pas suivant de l’iteration Simplexe consiste a determiner le nouveau som-met : ceci en exprimant x2 dans la deuxieme equation en lieu et place de x4.Remarquez que cela revient a amener la colonne de x4 en lieu et place de celle dex2. Ceci peut etre fait par deux types d’operations :

1. Amener un coefficient 1 a la place du pivot en divisant la ligne pivot par lepivot :

z x1 x2 x3 x4 x5

1 −3 −5 0 0 0 0

0 1 0 1 0 0 4

0 0 1 0 1/2 0 6

0 3 2 0 0 1 18

Section 3.3. Tableaux Simplexe et pivotage 37

2. Eliminer x2 des autres equations en retranchant chaque fois un multiple dela nouvelle ligne pivot :

z x1 x2 x3 x4 x5

1 −3 0 0 5/2 0 30

0 1 0 1 0 0 4

0 0 1 0 1/2 0 6

0 3 0 0 −1 1 6

Rappelons que l’on doit utiliser, dans cette seconde operation, un multiple de laligne pivot a l’exclusion de toute autre ligne sinon on detruirait la matrice identite.

La nouvelle solution de base et la nouvelle valeur de l’objectif sont respective-ment :

(x1, x2, x3, x4, x5) = (0, 6, 4, 0, 6)

z = 30.

Effectuons maintenant la deuxieme iteration de l’algorithme du Simplexe. Lepremier pas de la deuxieme iteration consiste a determiner la variable entrante. Ils’agit de x1, la variable de coefficient le plus negatif dans la ligne objectif. D’oula selection de la colonne pivot suivante :

z x1 x2 x3 x4 x5

1 −3 0 0 5/2 0 30

0 1 0 1 0 0 4

0 0 1 0 1/2 0 6

0 3 0 0 −1 1 6

Le second pas de l’iteration consiste a determiner la variable sortante. Oncalcul le minimum du rapport des coefficients du membre de droite sur le coefficientcorrespondant de la colonne entrante lorsque celui-ci est strictement positif :

min{

4

1,−,

6

3

}= 2.

Le minimum se produit dans la derniere ligne ou l’on lit la valeur de x5 qui sort

38 Chapitre 3. L’algorithme du Simplexe en Tableaux

donc de base. On encadre la ligne pivot :

z x1 x2 x3 x4 x5

1 −3 0 0 5/2 0 30

0 1 0 1 0 0 4

0 0 1 0 1/2 0 6

0 3 0 0 −1 1 6

Le dernier pas de l’iteration Simplexe consiste a determiner la nouvelle so-lution de base au moyen des deux types d’operations elementaires sur le tableauSimplexe :

1. Amener un 1 en position pivot;

z x1 x2 x3 x4 x5

1 −3 0 0 5/2 0 30

0 1 0 1 0 0 4

0 0 1 0 1/2 0 6

0 1 0 0 −1/3 1/3 2

2. Eliminer x1 des autres contraintes.

Le resultat de ces deux types d’operations est le suivant :

z x1 x2 x3 x4 x5

1 0 0 0 3/2 1 36

0 0 0 1 1/3 −1/3 2

0 0 1 0 1/2 0 6

0 1 0 0 −1/3 1/3 2

La nouvelle solution de base et la nouvelle valeur de l’objectif valent :

(x1, x2, x3, x4, x5) = (2, 6, 2, 0, 0)

z = 36.

Section 3.3. Tableaux Simplexe et pivotage 39

Si maintenant, on effectue par la troisieme iteration, on constate que lors dupremier pas de celle-ci, c’est-a-dire lors de la selection de la variable entrante, iln’y a aucun candidat. On arrete l’algorithme : la solution courante est optimale :

x∗1 = 2

x∗2 = 6

z∗ = 36.

Le chemin suivi par l’algorithme du Simplexe est illustre a la figure 3.1.Initialement, on part de l’origine des axes, soit le point P0 = (0, 0). Au cours de

9

4

2 4 6

3x1 + 2x2 = 18

x1 = 4

x1

2x2 = 12

x2P0 = (0,0)

P1 = (0,6)P2 = (2,6)

Figure 3.1: Chemin suivi par l’algorithme du Simplexe.

la premiere iteration, on suit l’axe des x2 en direction du point P1 = (0, 6). A ladeuxieme iteration, on se dirige horizontalement vers le somme P2 = (2, 6). Latroisieme iteration constate l’optimalite du point P2.

Nous verrons au chapitre suivant les embuches que l’on peut rencontrer dansl’execution de l’algorithme du Simplexe. En effet, nous avons ici suppose que l’onpouvait toujours trouver une solution de base de depart realisable et qu’a chaqueiteration, il y avait toujours une variable sortant de la base. Nous verrons au chapitresuivant comment on peut demarrer l’algorithme si toutes les contraintes initialesne se presentent pas sous forme de contraintes d’inegalites du type “inferieur ouegal a” avec un membre de droite positif. Nous examinerons egalement ce qu’ilconvient de faire si on ne trouve aucune variable candidate a sortir de la base.

Mais avant cela, resumons l’algorithme du Simplexe en tableaux.

40 Chapitre 3. L’algorithme du Simplexe en Tableaux

3.4 Algorithme du Simplexe en tableaux

Algorithme 3.1 Algorithme du Simplexe.

Pas 0. Initialisation : Pour demarrer l’algorithme,

1. Ajouter les variables d’ecart aux contraintes d’inegalite.

2. Mettre les variables originales hors base et les variables d’ecart enbase.

xj = 0, ∀j = 1, . . .n

Il en resulte le tableau de depart suivant :

z x1 x2 . . . xn xn+1 xn+2 . . . xn+m

1 −c1 −c2 −cn 0 0 0 0

0 a11 a12 a1n 1 0 0 b1

0 a21 a22 a2n 0 1 0 b2

.... . .

0 an1 an2 amn 0 0 1 b1

Pas 1. Choix de la variable entrante : selectionner comme variable entrante lavariable hors base avec le coefficient dans la ligne objectif le plus negatif,en se restreignant aux variables a coefficient negatif.

Soit xe telle que − ce ≤ −cj, ∀j| − cj < 0

Si une telle variable n’existe pas, stop : on a trouve la solution optimale.

Sinon, on entoure la colonne correspondante qui est appelee colonne ent-rante. Il en resulte le tableau suivant :

z x1 x2 xe xn xn+1 xn+2 . . . xn+m

1 −c1 −c2 −ce −cn 0 0 0 0

0 a11 a12 a1e a1n 1 0 0 b1

0 a21 a22 a2e a2n 0 1 0 b2

.... . .

0 an1 an2 ane amn 0 0 1 b1

Section 3.4. Algorithme du Simplexe en tableaux 41

Pas 2. Choix de la variable sortante : selectionner comme variable sortante lapremiere variable de base a s’annuler. Pour cela, on calcule le minimum durapport du coefficient du membre de droite sur le coefficient de la variableentrante dans la meme ligne lorsque celui-ci est positif. Soit l la ligne ou leminimum se produit :

bl

ale

= min{ bi

aie

|aie > 0}

La variable sortante est celle dont on lit la valeur dans la ligne ou le minimumse produit. Soit xs la variable de base dont on lit la valeur en ligne l. Onentoure la ligne ou le minimum se produit. Il en resulte le tableau suivant :

z x1 x2 xe xn xn+1 xn+2 . . . xn+m

1 −c1 −c2 −ce −cn 0 0 0 0

0 a11 a12 a1e a1n 1 0 0 b1

0 a21 a22 a2e a2n 0 1 0 b2

0 al1 al2 ale aln 0 0 1 0 bl

0 an1 an2 ane amn 0 0 1 b1

Pas 3. Pivotage : La variable entrante xe prend la place de la variable sortantexs dans la base. Il faut

1. Exprimer la fonction objectif en fonction des nouvelles variables horsbase.

2. Expliciter le systeme d’equations des contraintes en fonctions des nou-velles variables de base.

Pour cela, pratiquement on doit

1. Amener un coefficient 1 au croisement de la colonne pivot et de la ligneligne pivot en divisant celle-ci par le coefficient ale.

2. Amener des zeros dans le reste de la colonne pivote en ajoutant auxautres lignes un multiple de la ligne ou l’on a amene le 1.

Pas 4. Iterer : retour au Pas 1.

42 Chapitre 3. L’algorithme du Simplexe en Tableaux

3.5 Exercices

3.1. Algorithme du Simplexe. Resoudre en appliquant la methode du Simplexe :

max z = 3x1 + 2x2 + 4x3

s.c.q. x1 + x2 + 2x3 ≤ 4

2x1 + 3x3 ≤ 5

2x1 + x2 + 3x3 ≤ 7

x1, x2, x3 ≥ 0

3.2. Planification de production. Une compagnie fabrique deux produits dansses deux ateliers. Les marges unitaires sont respectivement de 2 pour lepremier produit et de 1 pour le second. Le temps passe dans chacun desateliers pour fabriquer un produit de chaque type est donne au tableau ci-dessous.

Temps dans pour le produit 1 pour le produit 2

l’atelier 1 1 heure 0 heure

l’atelier 2 1 heure 1 heure

Les capacites residuelles sont de 4,5 heures par jour et de 6 heures par jourrespectivement dans le premier et le second atelier. Les productions nonentieres sont permises.

(a) Formuler mathematiquement le probleme.

(b) Determiner la solution optimale au moyen de l’algorithme du Simplexe.Preciser, pour chaque tableau, la solution de base courante et justifierle choix des variables entrante et sortante.

(c) Illustrer sur un graphique le chemin suivi par l’algorithme du Simplexe.

Chapitre 4

Questions sur l’algorithme du Simplexe.

4.1 Introduction

L’exemple considere au chapitre 2 pour illustrer le fonctionnement de l’algorithmedu Simplexe ne montrait pas les embuches qui peuvent surgir a chaque etape del’algorithme du Simplexe :

(i) Initialisation : comment construire une solution de base realisable ?

(ii) Chaque iteration : pourra-t-on, a chaque iteration, trouver une variableentrante et une variable sortante ?

(iii) Terminaison : va-t-on arriver a une conclusion (solution optimale ou ab-sence de solution) en un nombre fini d’iterations ? Qu’est-ce qui nousgarantit que l’on ne va pas iterer a l’infini ?

Le premier point sera resolu en considerant un probleme auxiliaire : le problemedit de phase I. Ce probleme sera lui-meme resolu par l’application de l’algorithmedu Simplexe. En ce qui concerne les iterations, nous verrons que l’absence devariable entrante traduit le fait que l’on est a l’optimum tandis que l’absence devariable sortante traduit le fait que le probleme est non borne. Enfin, concernant letroisieme point, nous verrons que si la fonction objectif croıt strictement a chaqueiteration, la convergence est garantie.

4.2 Initialisation de l’algorithme

Les quelques exemples de problemes examines jusqu’a present n’ont pas pose deprobleme d’initialisation car nous partions d’un probleme ou toutes les compo-santes du membre de droite etaient non negatives. Supposons donc qu’il existeau moins un des coefficients du membre de droite strictement negatif.

43

44 Chapitre 4. Questions sur l’algorithme du Simplexe.

Le probleme est double. D’une part, il n’est pas evident que le problemeconsidere ait une solution realisable. D’autre part, meme dans le cas ou unesolution realisable existe, il n’est pas clair de savoir a quelle base elle se rapporte.On va repondre a ces deux questions par la resolution d’un probleme auxiliaire :le probleme de phase I. Nous allons illustrer ceci sur le probleme suivant :

max z = x1 − x2 + x3

s.c.q.

2x1 −x2 +2x3 ≤ 4,

−2x1 +3x2 −x3 ≥ 5,

x1 −x2 +2x3 ≥ 1,

x1, x2, x3 ≥ 0.

On peut se ramener a la forme avec egalites en multipliant les deux dernieresinequations par (-1) et en ajoutant les variables d’ecart. On obtient la formulationsous forme d’egalites suivante :

max z = x1 − x2 + x3

s.c.q.

2x1 −x2 +2x3 +x4 = 4,

2x1 −3x2 +x3 +x5 = −5,

−x1 +x2 −2x3 +x6 = −1,

x1, x2, x3, x4, x5, x6 ≥ 0.

Pour rendre le membre de droite non negatif, on va lui ajouter une quantitepositive x0, ou ce qui revient au meme, retrancher x0 au membre de gauche. Onobtient le systeme suivant :

2x1 −x2 +2x3 +x4 −x0 = 4,

2x1 −3x2 +x3 +x5 −x0 = −5,

−x1 +x2 −2x3 +x6 −x0 = −1.

On voit qu’en donnant a x0 la valeur 5 et en la faisant passer dans le membrede droite, on rend non negatives toutes les composantes du membre de droite. Ilfaudra cependant eliminer cette variable artificielle si on veut determiner une basede depart realisable pour le probleme original. Puisqu’on veut se debarrasser de x0,on va chercher a minimiser cette variable, ou, ce qui revient au meme, a maximiser

Section 4.2. Initialisation de l’algorithme 45

son oppose. Notons par le symbole w, la fonction objectif de sorte que l’on peutajouter la ligne objectif suivante correspondant a une maximisation :

max w = −x0

On obtient ainsi le probleme dit de phase I de l’algorithme du Simplexe.

Notons que l’on se trouve, avec ce probleme de phase I, toujours confronteau probleme de la construction d’une base de depart realisable. Une operation depivotage non standard nous permet cependant de nous en tirer dans le cas present.On forme une base de depart non realisable en prenant comme precedemment lesvariables d’ecart en base. On fait alors rentrer la variable artificielle x0 dans labase en l’echangeant avec la variable de base la plus negative. Cette operationcorrespond precisement a donner a la variable artificielle une valeur suffisante pourqu’elle rende toutes les composantes du membre de droite non negatives.

On peut alors resoudre le probleme auxiliaire par la methode du Simplexe.Les tableaux successifs seront les suivants :Tableau de depart :

w x0 x1 x2 x3 x4 x5 x6

1 1 0 0 0 0 0 0

0 −1 2 −1 2 1 0 0 4

0 −1 2 −3 1 0 1 0 −5

0 −1 −1 1 −2 0 0 1 −1

Premiere iteration speciale :

w x0 x1 x2 x3 x4 x5 x6

1 0 2 −3 1 0 1 0 −5

0 0 0 2 1 1 −1 0 9

0 1 −2 3 −1 0 −1 0 5

0 0 −3 4 −3 0 −1 1 4

46 Chapitre 4. Questions sur l’algorithme du Simplexe.

Deuxieme iteration : x2 entre, x6 sort :

w x0 x1 x2 x3 x4 x5 x6

1 0 −1/4 0 −5/4 0 1/4 3/4 −2

0 0 3/2 0 5/2 1 −1/2 −1/2 7

0 1 1/4 0 5/4 0 −1/4 −3/4 2

0 0 −3/4 1 −3/4 0 −1/4 1/4 1

Troisieme iteration : x3 entre, x0 sort :

w x0 x1 x2 x3 x4 x5 x6

1 1 0 0 0 0 0 0 0

0 −2 1 0 0 1 0 1 3

0 4/5 1/5 0 1 0 −1/5 −3/5 8/5

0 3/5 −3/5 1 0 0 −2/5 −1/5 11/5

Nous avons obtenu la solution optimale du probleme auxiliaire. La valeurcorrespondante de la fonction objectif est w = 0. Ce qui revient a dire que l’on areussi a annuler la variable artificielle. On a donc une solution de base realisablepour le probleme original.

On remarquera que le probleme de phase I est toujours realisable (par const-ruction), et qu’il est toujours borne. En effet, son objectif est de minimiser lavariable artificielle qui est astreinte a etre non negative. Zero est, dans ce cas, uneborne inferieure sur la valeur de la fonction objectif (a minimiser).

Le probleme de phase I a donc toujours une solution optimale. Deux cas sontpossibles quant a la valeur optimale de sa fonction objectif. Soit elle est nulle eton a une solution de base realisable du probleme original, soit elle est non nulleet le probleme original n’est pas realisable.

Lorsqu’on a obtenu une solution de base realisable pour le probleme original,on passe a la phase II :

• en supprimant la variable artificielle x0;

• en reprenant comme fonction objectif la fonction objectif du problemeoriginal;

• en exprimant cette fonction objectif en fonction des seules variables horsbase.

Section 4.2. Initialisation de l’algorithme 47

Appliquons ceci a l’exemple. Pour rappel, la fonction objectif originale etait ici :

z = x1 − x2 + x3

Les deux premieres operations donne le tableau de phase II suivant :

z x1 x2 x3 x4 x5 x6

1 −1 1 −1 0 0 0 0

0 1 0 0 1 0 1 3

0 1/5 0 1 0 −1/5 −3/5 8/5

0 −3/5 1 0 0 −2/5 −1/5 11/5

La troisieme operation peut etre effectuee en ajoutant a la ligne objectif la deuxiemecontrainte et en retranchant la troisieme. On obtient le tableau suivant de departde la phase II :

z x1 x2 x3 x4 x5 x6

1 −1/5 0 0 0 1/5 −2/5 −3/5

0 1 0 0 1 0 1 3

0 1/5 0 1 0 −1/5 −3/5 8/5

0 −3/5 1 0 0 −2/5 −1/5 11/5

On peut alors proceder a la phase II car on dispose cette fois d’une base de departrealisable, x1 = x5 = x6 = 0, hors base, et x2 = 11

5, x3 = 8

5, x4 = 3 en base avec

la valeur correspondante de la fonction objectif z = −35. A la premiere iteration

de la phase II, x6 entre et x4 sort. On obtient le tableau suivant :

z x1 x2 x3 x4 x5 x6

1 1/5 0 0 2/5 1/5 0 3/5

0 1 0 0 1 0 1 3

0 4/5 0 1 3/5 −1/5 0 17/5

0 −2/5 1 0 1/5 −2/5 0 14/5

La solution optimale vaut donc :

z∗ = 3/5

x∗1 = 0

x∗2 = 14/5

x∗3 = 17/5

48 Chapitre 4. Questions sur l’algorithme du Simplexe.

Exemple 2 : probleme non realisable. Soit le probleme :

max z = 3x1 + x2

s.c.q.

−x1 +x2 ≥ 1,

x1 +x2 ≥ 3,

2x1 +x2 ≤ 2,

x1, x2 ≥ 0.

Mettons le d’abord sous forme canonique avec inegalites du type ≤ :

max z = 3x1 + x2

s.c.q.

x1 −x2 ≤ −1,

−x1 −x2 ≤ −3,

2x1 +x2 ≤ 2,

x1, x2 ≥ 0.

Puis sous forme canonique avec variables d’ecart :

max z = 3x1 + x2

s.c.q.

x1 −x2 +x3 = −1,

−x1 −x2 +x4 = −3,

2x1 +x2 +x5 = 2,

x1, x2, x3, x4, x5 ≥ 0.

Formons le tableau de depart de la phase I :

w x0 x1 x2 x3 x4 x5

1 1 0 0 0 0 0 0

0 −1 1 −1 1 0 0 −1

0 −1 −1 −1 0 1 0 −3

0 −1 2 1 0 0 1 2

On effectue un premier pivotage non standard. La variable x0 remplace dans labase la variable la plus negative, soit x4. La suite des tableaux est la suivante :

w x0 x1 x2 x3 x4 x5

1 0 −1 −1 0 1 0 −3

0 0 2 0 1 −1 0 2

0 1 1 1 0 −1 0 3

0 0 3 2 0 −1 1 5

Section 4.2. Initialisation de l’algorithme 49

A la premiere iteration, la variable x1 entre et x3 sort de la base :

w x0 x1 x2 x3 x4 x5

1 0 0 −1 1/2 1/2 0 −2

0 0 1 0 1/2 −1/2 0 1

0 1 0 1 −1/2 1/2 0 2

0 0 0 2 −3/2 1/2 1 2

A la deuxieme iteration, la variable x2 entre et x5 sort de la base :

w x0 x1 x2 x3 x4 x5

1 0 0 0 −1/4 3/4 1/2 −1

0 0 1 0 1/2 −1/2 0 1

0 1 0 0 1/4 −3/4 −1/2 1

0 0 0 1 −3/4 1/4 1/2 1

A la troisieme iteration, la variable x3 entre et x1 sort de la base :

w x0 x1 x2 x3 x4 x5

1 0 1/2 0 0 1/2 1/2 −1/2

0 0 2 0 1 −1 0 2

0 1 −1/2 0 0 −1/2 −1/2 1/2

0 0 −3/2 1 0 −1/2 1/2 5/2

La phase I se termine sans que w = 0 (x0 est encore dans la base et vaut 1/2). Leprobleme original n’est donc pas realisable. En effet, les contraintes du problemesont incompatibles. Ce verdict est confirme par un examen de la figure 4.1.

-1 1 3

1

2

3

x1

x2

Figure 4.1: Probleme irrealisable.

50 Chapitre 4. Questions sur l’algorithme du Simplexe.

4.3 Determination de la variable entrante

La variable entrante doit etre une variable hors base avec un coefficient c′j negatifdans la ligne objectif du tableau courant. Si une telle variable n’existe pas, alors letableau courant decrit une solution optimale. En effet, la ligne objectif du tableaucourant peut s’ecrire

z +∑j∈N

c′jxj = z∗,

ou N note l’ensemble des indices des variables hors base. Ceci qui peut encores’ecrire comme suit :

z = z∗ −∑j∈N

c′jxj.

La solution courante ou xj = 0 pour tout j ∈ N donne la valeur z∗ a la fonctionobjectif. Si c′j ≥ 0 pour tout j ∈ N , alors toute solution realisable ou xj ≥ 0 pourtout j ∈ N donne a la fonction objectif une valeur qui est au plus z∗. La solutioncourante est par consequent optimale.

4.4 Determination de la variable sortante

La variable qui quitte la base est la premiere a bloquer l’augmentation de lavariable entrante. Cette regle est ambigue car elle peut donner lieu a plusieurscandidats ou a aucun candidat. Ce dernier cas est illustre a la deuxieme iterationdans le probleme suivant :

max z = 2x1 + x2

s.c.q.

x1 −2x2 +x3 = 2,

−2x1 +x2 +x4 = 2,

x1, x2, x3, x4 ≥ 0.

Le tableau de depart est :

z x1 x2 x3 x4

1 −2 −1 0 0 0

0 1 −2 1 0 2

0 −2 1 0 1 2

Premiere iteration :Au depart, x1 = x2 = 0 sont hors base et x3 = 2, x4 = 2 sont en base. On fait

Section 4.4. Determination de la variable sortante 51

entrer x1 dans la base. Il n’y a que la variable de base x3 qui limite la croissancede x1. La variable x3 sort de la base lorsque x1 vaut 2.

z x1 x2 x3 x4

1 0 −5 2 0 4

0 1 −2 1 0 2

0 0 −3 2 1 6

Deuxieme iteration :La variable x2 est seule candidate a l’entree en base. Comme tous les coefficientsde la colonne x2 sont non positifs, aucune des variables de base n’est bloquante.La variable x2 peut croıtre au dela de toute limite. On en conclut que le problemeest non borne. On peut le verifier graphiquement. Le systeme de depart est lesuivant ;

max z = 2x1 + x2

s.c.q.

x1 −2x2 ≤ 2,

−2x1 +x2 ≤ 2,

x1, x2 ≥ 0.

On peut voir a la figure 4.2 qu’a partir du sommet (2,0), la region connaıt unedirection ou x2 n’est plus bornee.

-1

2

-1

2 x1

x2

Figure 4.2: Solution non bornee.

On peut arriver a la meme conclusion en general: s’il n’y a pas de candidatpour quitter la base, on peut faire croıtre la variable entrante et donc aussi lafonction objectif autant qu’on le veut. Dans ce cas, le probleme est non borne.

52 Chapitre 4. Questions sur l’algorithme du Simplexe.

D’autre part, s’il y a plusieurs candidats pour quitter la base, alors n’importelequel de ces candidats peut servir. La presence de plusieurs candidats pour quitterla base a une consequence importante : la degenerescence.

Illustrons ceci par l’exemple suivant :

z x1 x2 x3 x4 x5 x6

1 −2 1 −8 0 0 0 0

0 0 0 2 1 0 0 1

0 2 −4 6 0 1 0 3

0 −1 +3 4 0 0 1 2

Ayant choisi x3 pour entrer en base, on trouve que chacune des trois variables debase, x4, x5 et x6 bloque l’accroissement de x3 a 1

2. Chacune de ces variables est

donc candidate a sortir de base. On peut choisir x4. On obtient le tableau suivant :

z x1 x2 x3 x4 x5 x6

1 −2 1 0 4 0 0 4

0 0 0 1 1/2 0 0 1/2

0 2 −4 0 −3 1 0 0

0 −1 +3 0 −2 0 1 0

ou l’on constate que les variables de base x5 et x6 ont une valeur nulle ! Dessolutions de base avec une ou plusieurs variables de base nulles sont appelees dessolutions degenerees.

La degenerescence peut avoir la consequence suivante. Continuons l’exemple.A l’iteration suivante, x1 entre en base et x5 bloque son entree a une valeur egalea zero ! Donc la valeur de x1 et, par voie de consequence, des autres variables etde l’objectif restent inchangees au cours de ce pivotage.

Des iterations Simplexe qui changent juste la base sans changer la valeur dela solution de base sont appelees iterations degenerees. Il est a remarquer que lesiterations degenerees sont tres souvent presentes dans la resolution de problemespratiques mais, en general, ne constituent que des “accidents passagers” dans lesens qu’apres quelques iterations degenerees la fonction objectif se remet a croıtrestrictement. Ceci amene directement a considerer le point suivant.

Section 4.5. Arret apres un nombre fini d’iterations 53

4.5 Arret apres un nombre fini d’iterations

Si, a chaque iteration, la fonction objectif augmente strictement, alors on doit at-teindre une solution optimale ou detecter que le probleme est non borne apres unnombre fini d’iterations. En effet, a chaque iteration, la solution de base corres-pond a un sommet du polyedre des contraintes. La fonction objectif augmentantstrictement a chaque iteration, on ne peut pas repasser par une solution de basedeja rencontree. Le nombre de solutions de base realisables, ou ce qui revient aumeme le nombre de points extremes du polyedre des contraintes, est majore parCn

m+n, un nombre fini. Il faut en effet choisir n variables hors base parmi les n+mvariables possibles (celles de depart plus les variables d’ecart). Il n’est alors paspossible d’iterer indefiniment.

Tout ce raisonnement repose sur l’hypothese que la fonction objectif aug-mente strictement a chaque iteration. Comme le montre l’exemple suivant, sicette hypothese n’est pas satisfaite, on peut cycler, c’est-a-dire repeter a l’infini lameme suite d’iterations.

z x1 x2 x3 x4 x5 x6 x7

1 −10 57 9 24 0 0 0 0

0 0, 5 −5, 5 −2, 5 9 1 0 0 0

0 0, 5 −1, 5 −0, 5 1 0 1 0 0

0 1 0 0 0 0 0 1 1

Supposons que l’on adopte les regles suivantes en presence de candidats multiplespour les criteres d’entree et de sortie :

(i) La variable entrante est toujours la variable hors base de coefficient le plusnegatif dans la fonction objectif. En cas d’ex aequo, on prend la variable deplus petit indice.

(ii) En cas de plusieurs variables de base candidates a la sortie de la base, onprend la variable de plus petit indice.

On remarquera la presence de composantes nulles dans le membre de droite.

54 Chapitre 4. Questions sur l’algorithme du Simplexe.

Premiere iteration :

z x1 x2 x3 x4 x5 x6 x7

1 0 −53 −41 204 20 0 0 0

0 1 −11 −5 18 2 0 0 0

0 0 4 2 −8 −1 1 0 0

0 0 11 5 −18 −2 0 1 1

Deuxieme iteration :

z x1 x2 x3 x4 x5 x6 x7

1 0 0 −14, 5 98 6, 75 13, 25 0 0

0 1 0 0, 5 −4 −0, 75 2, 75 0 0

0 0 1 0, 5 −2 −0, 25 0, 25 0 0

0 0 0 −0, 5 4 0, 75 2, 75 1 1

Troisieme iteration :

z x1 x2 x3 x4 x5 x6 x7

1 29 0 0 −18 15 93 0 0

0 2 0 1 −8 −1, 5 5, 5 0 0

0 −1 1 0 2 0, 5 −2, 5 0 0

0 1 0 0 0 0 0 1 1

Quatrieme iteration :

z x1 x2 x3 x4 x5 x6 x7

1 20 9 0 0 −10, 5 70, 5 0 0

0 −2 4 1 0 0, 5 −4, 5 0 0

0 −0, 5 0, 5 0 1 0, 25 −1, 25 0 0

0 1 0 0 0 0 0 1 1

Cinquieme iteration :

z x1 x2 x3 x4 x5 x6 x7

1 −22 93 21 0 0 −24 0 0

0 −4 8 2 0 1 −9 0 0

0 0, 5 −1, 5 −0, 5 1 0 1 0 0

0 1 0 0 0 0 0 1 1

Section 4.5. Arret apres un nombre fini d’iterations 55

Sixieme iteration :

z x1 x2 x3 x4 x5 x6 x7

1 −10 57 9 24 0 0 0 0

0 0, 5 −5, 5 −2, 5 9 1 0 0 0

0 0, 5 −1, 5 −0, 5 1 0 1 0 0

0 1 0 0 0 0 0 1 1

On retrouve le tableau initial. L’algorithme du Simplexe va donc repeter inlassa-blement la meme suite de six iterations sans jamais atteindre la solution optimalequi existe cependant avec z = 1. On dit que l’algorithme cycle.

Notons que le phenomene de cyclage est necessairement associe a la presencede solutions de base ou certaines variables de base sont nulles. Une base degenereepeut donner lieu a une ou plusieurs iterations consecutives au cours desquelles ni lafonction objectif, ni aucune des variables ne change de valeur. La seule chose quichange est la liste des variables qui sont en base ou hors base. Geometriquement onse trouve en un point extreme du polyedre des contraintes ou plus de n hyperplanss’intersectent. Il y a donc differentes facon de definir ce point extreme commeintersection de n hyperplans. On passe d’une de ces definitions a une autre.

Il existe des regles qui permettent d’empecher le cyclage. Par exemple, laregle de Bland. Cette regle consiste a systematiquement choisir comme variableentrante la premiere de coefficient negatif dans la ligne objectif et comme lavariable sortante, la premiere qui veut sortir. Insistons sur la difference par rapporta la regle que nous avons utilise. Nous avions chaque fois choisi la candidate deplus petit indice parmi toutes les variables de coefficient objectif le plus negatif.Ici, on decide de prendre la premiere variable de coefficient negatif rencontreedonc pas forcement celle de coefficient minimum. On verifiera, sur l’exempleci-dessus, qu’en adoptant la regle de Bland, on evite que l’algorithme ne boucle.En effet, a la cinquieme iteration, on choisit x1 plutot que x6 pour entrer en baseet on sort du phenomene de cyclage.

Le lecteur interesse se referera a Chvatal [4, pp 34-37] pour l’expose de deuxautres methodes qui evitent le probleme du cyclage : la methode de perturbationet la methode lexicographique.

Terminons en remarquant que le cyclage est un phenomene assez rare dansla pratique de sorte que beaucoup de logiciels mettant en œuvre la methode duSimplexe ignorent totalement ce probleme.

56 Chapitre 4. Questions sur l’algorithme du Simplexe.

4.6 Exercices

4.1. Probleme realisable. Resoudre en appliquant le Simplexe en deux phases :

max z = 3x1 + x2

s.c.q.

x1 −x2 ≤ −1

−x1 −x2 ≤ −3

2x1 +x2 ≤ 4

x1, x2 ≥ 0.

4.2. Probleme non realisable. Resoudre par le Simplexe en deux phases :

max z = 3x1 + x2

s.c.q.

x1 −x2 ≤ −1

−x1 −x2 ≤ −3

2x1 +x2 ≤ 2

x1, x2 ≥ 0.

4.3. Probleme non borne. Resoudre en appliquant le Simplexe en deux phases :

max z = 3x1 + x2

s.c.q.

x1 −x2 ≤ −1

−x1 −x2 ≤ −3

2x1 −x2 ≤ 2

x1, x2 ≥ 0.

Chapitre 5

Analyse postoptimale.

5.1 Introduction

Dans ce chapitre, nous voir comment va varier la valeur optimale de l’objectifd’un programme lineaire lorsque l’on modifie certains coefficients du probleme(coefficients objectif ou du membre de droite). En effet, generalement la solutionnumerique d’un probleme lineaire est moins significative que de savoir commentl’objectif va bouger si l’on modifie certaines donnees du probleme. C’est l’objetde ce que l’on appelle l’analyse postoptimale.

Pour voir l’effet de tels changements de donnees, une solution naıve consiste aappliquer le Simplexe au nouveau probleme et bien sur on peut en deduire l’effetsur l’objectif. Mais nous allons voir dans ce chapitre que, si la base optimalene change pas, on peut predire sans aucun nouveau calcul l’effet de variationdes donnees sur la fonction objectif en exploitant simplement le tableau Simplexeoptimal du probleme original.

Nous allons d’abord envisager le cas de la variation des coefficients dumembre de droite des contraintes. Nous allons voir que la variation de la va-leur optimale de l’objectif d’un programme lineaire en fonction des coefficients dumembre de droite est donnee par la valeur des “prix caches” que l’on peut lire dansla ligne objectif du tableau Simplexe final. Nous verrons comment determiner ledomaine de validite de ces prix caches.

Nous verrons ensuite, le cas de la variation des coefficients de la fonctionobjectif. Ici, nous verrons que le taux de variation de l’objectif est donne par lavaleur des variables a l’optimum. Ici aussi, il y a un un domaine de validite pources valeurs optimales des variables : elles restent valables tant que la base optimalene change pas.

Enfin, nous terminerons en donnant l’interpretation d’une autre informationque l’on peut tirer du tableau Simplexe, a savoir la valeur des couts reduits des

57

58 Chapitre 5. Analyse postoptimale.

variables hors base.

5.2 Variation par rapport au second membre

La question qui se pose est ici la suivante : “Si on augmente la capacite disponibled’une ressource, quel est l’impact sur la valeur optimale de la fonction objectif ?”

Pour des variations de membre de droite suffisamment faibles pour que la memebase reste optimale, on peut repondre a cette question en exploitant le tableauSimplexe optimal de la maniere suivante :

Le “prix cache” (note y∗i ) mesure l’augmentation de la fonction objectif si

l’on accroıt d’une unite la capacite disponible (bi). Dans le tableau Simplexeoptimal, le prix cache y∗

i est le coefficient de la variable d’ecart de la contraintedans la ligne objectif.

Nous allons illustrer ceci sur sur l’exemple introductif du chapitre 2 dontl’enonce est rappele ci-dessous.

max z = 3 x1 + 5 x2

s.c.q.

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

x1 ≥ 0

x2 ≥ 0

Considerons le tableau final qui a ete determine au chapitre 3 :

z x1 x2 x3 x4 x5

1 0 0 0 3/2 1 36

0 0 0 1 1/3 −1/3 2

0 0 1 0 1/2 0 6

0 1 0 0 −1/3 1/3 2

Comme x3, x4 et x5 sont les variables d’ecart des contraintes de capacite des troisateliers, on en deduit les valeurs des prix caches suivants :

y∗1 = 0

y∗2 = 3/2

y∗3 = 1

Section 5.2. Variation par rapport au second membre 59

qui correspondent aux prix caches des ressources utilisees dans les ateliers 1, 2 et3 dont les capacites disponibles sont :

b1 = 4,

b2 = 12,

b3 = 18.

Ce resultat peut etre demontre mathematiquement. Mais, plutot que d’en don-ner une demonstration formelle, nous allons l’illustrer graphiquement. Conside-rons tout d’abord une augmentation de capacite du premier atelier de b1 = 4 ab′1 = 5. On peut voir a la figure 5.1 que le nouveau point optimal reste le meme

98

4

2 3x1 + 2x2 = 18

x1 = 4 2x2 = 12

0,

x1 = 5

2x2 = 13(5/3,13/2)

z = 3x1 + 5x2

2 8

x2

x1

6

640

Figure 5.1: Analyse postoptimale

x′∗ = x∗ = (2, 6).

En consequence de quoi, la valeur optimale de l’objectif ne change pas :

z′∗ = z∗ = 36

D’ou une variation nulle de l’objectif, ce qui etait bien predit par la valeur nulledu prix cache y∗

1 :∆z = z′∗ − z∗ = 0 = y∗

1.

Une augmentation de capacite du deuxieme atelier de b2 = 12 a b′2 = 13 donne undeplacement du point optimal (voir figure 5.1) vers le nouveau point :

x′∗ = (5/3, 13/2).

60 Chapitre 5. Analyse postoptimale.

En consequence de quoi, la nouvelle valeur de l’objectif est donnee par :

z′∗ = 37, 5

D’ou un accroissement de l’objectif egal a la valeur du deuxieme prix cache :

∆z = z′∗ − z∗ = 37, 5 − 36 =3

2= y∗

2.

Enfin, considerons une augmentation de capacite du troisieme atelier de b3 = 18a b′3 = 19. Comme on peut le voir a la figure 5.2, cela donne un deplacement dupoint optimal vers :

x′∗ = (7/3, 6).

En consequence de quoi, la nouvelle valeur de l’objectif vaut :

z′∗ = 37

D’ou une augmentation d’objectif egale a la valeur du troisieme prix cache :

∆z = z′∗ − z∗ = 37 − 36 = 1 = y∗3.

10

8

4

2

2 8

3x1 + 2x2 = 18

x1 = 4

x2

2x2 = 12

x1

3x + x = 191 2 2

(7/3, 6)

z = 3x1 + 5x2

6

640

Figure 5.2: Variation de capacite de l’atelier 3

Le resultat peut aussi etre interprete dans l’autre sens : y∗3 est la perte de profit

si on diminue d’une unite la capacite du troisieme atelier.

Remarquons, et ceci est l’objet de l’analyse de sensibilite qu’il y a une limitede validite de chaque prix cache. En effet, dans le cas de la premiere ressource, si

Section 5.2. Variation par rapport au second membre 61

l’effet d’une augmentation de b1 sera nul sur la valeur optimum de l’objectif quelque soit b1 ≥ 4, il n’en va pas de meme d’une diminution. En effet, en dessousde b1 = 2, la solution optimale va changer. On a donc determine le domaine devalidite de y∗

1 = 0. Il s’agit de l’intervalle :

b1 ∈ [2, +∞].

Pour le deuxieme atelier, au dela de b2 = 18, la solution optimale reste en (0,9).La base optimale et y∗

2 changent :

y∗2 = 0.

De meme, une diminution en deca de b2 = 6 va changer la base optimale. On endeduit le domaine de validite de y∗

2 = 3/2. Il s’agit de l’intervalle :

b2 ∈ [6, 18].

Pour le troisieme atelier, au dela de b3 = 24, la solution optimale reste en (4,6).La base optimale et y∗

3 changent :

y∗3 = 0.

De meme, une diminution en deca de b3 = 12 va changer la base optimale. On endeduit le domaine de validite de y∗

3 = 1. Il s’agit de l’intervalle :

b3 ∈ [12, 24].

Ces informations sont donnees dans le rapport de sensibilite du solveur d’Excel.Ces informations sont fournies sous la forme d’une augmentation admissible etd’une diminution admissible. Elle sont reprises ci-dessous :

Contrainte augmentation diminution membre

admissible admissible de droite

Atelier 1 +∞ 2 4

Atelier 2 6 6 12

Atelier 3 6 6 18

Remarquons finalement que l’on a toujours une valeur nulle du prix cachepour une contrainte non liante. Une contrainte non liante est une contrainte oula variable d’ecart est non nulle. Par exemple, la premiere contrainte

x1 ≤ 4

a un “prix cache” nul. Ceci a une interpretation economique. La ressource n’estpas entierement utilisee : il ne sert donc a rien d’augmenter son stock disponible.

62 Chapitre 5. Analyse postoptimale.

5.3 Variation des coefficients objectifs

La question qui se pose ici est la suivante :“Si on augmente le prix de vente unitaireou si l’on diminue le cout unitaire de production, quel est l’impact sur la valeur del’objectif ?”

A nouveau, on peut predire cette variation de l’objectif pour autant que labase optimale ne change pas. En effet, tant que la base optimale ne change pas,la solution optimale x∗ = (x∗

1, x∗2, . . .x

∗n) reste la meme. Seul le profit optimal

change. Le nouveau profit vaut donc :

z∗ =n∑

j=1

(cj + ∆cj)x∗j

On en conclut que pour une variation unitaire du coefficient cj , l’augmentation dez∗ est exactement la valeur optimale de la variable x∗

j .

La “valeur de la jeme variable a l’optimum” (notee x∗j ) mesure l’augmenta-

tion de la fonction objectif si l’on accroıt d’une unite la marge unitaire cj .

Dans le cas de l’exemple, les augmentations de profit pour une augmentationunitaire de la marge des produits valent respectivement :

x∗1 = 2 et x∗

2 = 6.

Considerons maintenant la question l’analyse de sensibilite. Nous allons anouveau l’illustrer sur le meme exemple. Initialement :

z = 3x1 + 5x2

On veut determiner l’intervalle de variation maximum de c1 autour de 3 tel que labase optimale ne change pas.

A la figure 5.3, on constate que le coefficient c1 peut descendre jusqu’a ce quel’objectif z = c1x1 + 5x2 soit parallele au segment

2x2 = 12,

c’est-a-dire lorsque c1 = 0. Le coefficient c1 peut augmenter jusqu’a ce que l’ob-jectif z = c1x1 + 5x2 soit parallele au segment

3x1 + 2x2 = 18.

Ceci se produit lorsqu’il y a egalite des pentes :

−c1

5=

−3

2,

Section 5.3. Variation des coefficients objectifs 63

10

8

6

4

2

0 2 6 8 x1

x2

(2,6)

z = 3x1 +5x2 = 36

z = 4x1 +5x2 = 38

10 124

Figure 5.3: Analyse de sensibilite de c1

c’est-a-dire lorsque c1 = 15/2.

La reponse a la question de l’analyse de sensibilite est donc la suivante. Tantque

c1 ∈ [0, 15/2],

on a la meme base optimale et donc la meme solution optimale.

Effectuons l’analyse de sensibilite pour le second coefficient objectif. Celui-cipeut decroıtre jusqu’a ce que l’objectif z = 3x1 + c2x2 soit parallele au segment

3x1 + 2x2 = 18.

Ceci se produit lorsqu’il y a egalite des pentes :

−3

c2

=−3

2,

c’est-a-dire lorsque c2 = 2. Dans l’autre sens, c2 peut augmenter jusqu’a ce quel’objectif z = 3x1 + c2x2 soit parallele au segment

2x2 = 12.

Ceci ne se produit jamais. On en conclut que tant que :

c2 ∈ [2, +∞[,

on a la meme base optimale et donc la meme solution optimale.

Ces intervalles de sensibilite sont egalement donnes dans le rapport de sensi-bilite du solveur d’Excel.

64 Chapitre 5. Analyse postoptimale.

5.4 Cout reduit des variables hors base

Pour terminer ce chapitre consacre a l’analyse postoptimale, nous allons definir unenotion importante qui peut egalement etre deduite du tableau Simplexe optimal, ils’agit du cout reduit d’une variable hors base.

Le “cout reduit” de la variable hors base xj , note dj , mesure l’augmentationde la fonction objectif si l’on accroıt d’une unite la valeur de la variable horsbase xj . Dans le tableau Simplexe optimal, le cout reduit dj est l’oppose ducoefficient de la variable dans la ligne objectif.

Nous illustrerons cette notion sur l’ exemple de planification de la productionde chassis auquel on adjoint un troisieme chassis mixte aluminium bois, pour lequella marge unitaire est de 4 et les temps unitaires de fabrication dans les trois atelierssont respectivement de 1, 2 et 3 heures. La formulation de ce probleme est repriseci-dessous :

z −3x1 −5x2 −4x3 = 0

x1 +x3 +x4 = 4

2x2 +2x3 +x5 = 12

3x1 +2x2 +3x3 +x6 = 18

Elle se met sous la forme du tableau Simplexe initial suivant :

z x1 x2 x3 x4 x5 x6

1 −3 −5 −4 0 0 0 0

0 1 0 1 1 0 0 4

0 0 2 2 0 1 0 12

0 3 2 3 0 0 1 18

La solution optimale de ce probleme lineaire peut etre determinee par l’algorithmedu Simplexe. Le tableau Simplexe optimal final est le suivant :

z x1 x2 x3 x4 x5 x6

1 0 0 2 0 3/2 1 36

0 0 0 2/3 1 1/3 −1/3 2

0 0 1 1 0 1/2 0 6

0 1 0 1/3 0 −1/3 1/3 2

Section 5.4. Cout reduit des variables hors base 65

On en deduit la solution optimale suivante :

(x1, x2, x3, x4, x5, x6) = (2, 6, 0, 2, 0, 0)

Tandis que la valeur optimale de l’objectif est donnee par :

z∗ = 36

On constate que seuls sont rentables les productions des chassis 1 et 2. En effet,le chassis 3, bien qu’ayant une marge unitaire superieure au chassis 1, consommeplus de ressources et permet, pour la meme capacite disponible des trois ateliersde faire moins de chassis 3 que de chassis 1. On peut alors se poser la questionsuivante : de combien faut-il augmenter la marge du chassis 3 pour le rendreattractif ?

On peut repondre a cette question en exploitant le tableau Simplexe optimalde la maniere suivante : les coefficients dans la ligne objectif du tableau Simplexefinal (l’oppose des couts reduits) fournissent l’augmentation de prix necessaire. Eneffet, les couts reduits des variables hors base s’interpretent, en general, commel’augmentation de la fonction objectif lorsque l’on augmente d’une unite la va-riable. Ici, a l’optimum, ce cout reduit, note d3, est negatif, traduisant le fait quesi la production de ce chassis etait positive, elle diminuerait le profit d’autant.

d3 = −2.

Pour qu’il devienne interessant de le produire, il faut donc augmenter sa marged’au moins cette quantite. Ici, le cout reduit s’interprete comme l’oppose de l’aug-mentation minimale de prix pour que la production devienne interessante.

Remarquez que tous les optimiseurs fournissent en plus de la solution optimaled’un probleme lineaire, cette information : les couts reduits des variables hors basesont, en effet, au signe pres, les coefficients des variables hors base dans la ligneobjectif du tableau Simplexe optimal.

En conclusions, nous avons vu dans ce chapitre comment interpreter tous lescoefficients dans la ligne objectif du tableau Simplexe optimal final :

• Les couts reduits sont, au signe pres, les coefficients des variables horsbase dans la ligne objectif du tableau Simplexe optimal. Ils s’interpretent,en general, comme l’augmentation de la fonction objectif lorsque l’onaugmente d’une unite la variable hors base.

• Les prix caches sont les coefficients des variables d’ecart des contraintesdans la ligne objectif du tableau Simplexe optimal. Ils s’interpretent commel’augmentation du profit pour une augmentation unitaire d’un des co-efficients du membre de droite.

Le rapport de sensibilite d’Excel donne ces deux informations.

66 Chapitre 5. Analyse postoptimale.

5.5 Exercices

5.1. Sensibilite aux coefficients objectif. Soit le probleme lineaire suivant :

Minimiser 0x1 + x2

s.c.q. 3x1 + 4x2 ≥ 9, (1)

5x1 + 2x2 ≤ 8, (2)

3x1 − x2 ≤ 0, (3)

x1, x2 ≥ 0.

(a) Determiner graphiquement la solution optimale.

(b) Determiner l’intervalle maximum de variation de c1 autour de zero quipreserve la solution optimale.

5.2. Sensibilite du membre de droite. Pour le probleme lineaire formule al’exercice 2 du chapitre 1,

(a) Resoudre par l’algorithme du Simplexe.

(b) Determiner la valeur des prix caches a l’optimum.

(c) Si l’unite de capacite supplementaire cout le meme prix pour les deuxateliers, a-t-on interet a augmenter la capacite du premier ou du secondatelier ?

(d) Jusqu’a quel niveau est-il interessant d’augmenter cette capacite ?

5.3. Fabrication de tourbe. Une firme quebequoise de production de tourbemet sur le marche 3 qualites de tourbe : la qualite 3 utilisee comme litiere;la qualite 2 qui sert d’engrais aux entreprises marechaires et la qualite 1destinee a l’empotage des plantes d’interieur. La tourbe de qualite 3 secommercialise en ballots de 25 kg, celle de qualite 2 en sacs plastiques de 20kg et celle de qualite 1 en sachets de 5 kg. La tourbe s’extrait au printempssous forme humide et est sechee au soleil durant l’ete pour etre livree al’automne. Un kg de tourbe humide extraite donne 100 grammes de produitsec commercialisable. La machinerie qui extrait la tourbe humide permetd’extraire 4 500 000 kg de tourbe humide chaque printemps.

La tourbe sechee est defibree a l’automne, au moyen de defibreuses quimettent 5 minutes pour preparer un ballot de Qualite 3, 8 minutes pour unsac de qualite 2 et 3 minutes pour un sachet de qualite 1. On dispose de 2000 heures de defibrage pendant la periode consideree. L’entrepot permetde stocker 20 000 metres cubes de tourbe seche emballee, un emballage de

Section 5.5. Exercices 67

qualite 3 requiert 1 metre cube, un sac de qualite 2 requiert 0,75 metre cubeet un sachet de qualite 1 requiert 0,20 metre cube.

Le service marketing impose la fabrication maximale de 15 000 ballots dequalite 3 dont un grossiste retient chaque annee 10 000 ballots. Le memegrossiste requiert 3 000 sacs de qualite 2. Les profits que retire la societede la vente de ces produits s’elevent a 9 dollars le ballot de qualite 3, a 12dollars le sac de qualite 2 et a 2 dollars le sachet de qualite 1.

(a) Formuler le probleme lineaire correspondant (choix des variables, ex-pression de l’objectif et des contraintes).

(b) Voici le tableau Simplexe final :

z x3 x2 x1 x4 x5 x6 x7 x8 x9

1 0 0 2, 2 0, 12 0 1, 20 0 0 0 198 0000 0 1 0, 5 −0, 05 0 0, 25 0 0 0 7 5000 0 0 0, 025 −0, 0425 1 0, 0125 0 0 0 2 3750 0 0 0, 5 −0, 05 0 0, 25 0 0 1 4 5000 0 0 0, 2 −0, 08 0 0, 20 1 0 0 3 0000 0 0 −0, 2 0, 08 0 −0, 20 0 1 0 2 0000 1 0 −0, 2 0, 08 0 −0, 20 0 0 0 12 000

Donnez la solution optimale, determinez les variables en base et horsbase.

(c) Dites ce qui se passerait pour l’objectif si on produisait un sachet dequalite 1. En deduire quel devrait etre le profit minimal que la societedevrait tirer de la mise sur le marche d’un sachet de qualite 1 pour quecette production devienne rentable.

(d) Le solveur d’Excel vous fournit les intervalles de sensibilite suivantpour les coefficients cj de l’objectif et bi du membre de droite :

coefficient valeur presente valeur minimum valeur maximumc3 9 7, 50 15c2 12 7, 60 14, 4c1 2 −∞ 4, 20

b1 450 000 425 000 487 500b2 20 000 17 625 +∞b3 120 000 105 000 130 000b4 15 000 12 000 ∞b5 10 000 −∞ 12 000b6 3 000 −∞ 7500

68 Chapitre 5. Analyse postoptimale.

Combien la societe serait prete a depenser au maximum pour porter de4 500 000 a 4 750 000 kg la capacite printaniere d’extraction ?

(e) Si le profit unitaire associe a un emballage de qualite 3 passait de 9 a11 dollars, le plan de production optimal resterait-il le meme ? Si oui,le profit optimal serait-il augmente ou diminue ? de combien ?

Chapitre 6

La programmation en nombres entiers.

6.1 Introduction

L’algorithme du Simplexe fournit une methode de resolution generale pour tousles problemes lineaires quelle que soit leur forme. Au contraire, en programma-tion en nombres entiers, on ne dispose pas d’un algorithme general qui permettede resoudre efficacement tous les problemes en nombres entiers. Cependant, ilexiste une classe generale de methodes connue sous le nom de branch and bound(separation et borne) qui permet de resoudre bon nombre de problemes en nombresentiers. On appelle problemes mixtes (MIP en anglais pour Mixed Integer Program-ming) les problemes comportant un certain nombre de variables lineaires (donccontinues) et un certain nombre de variables en nombres entiers (donc discretes).

Nous allons ici decrire cette methode qui commence par la resolution duprobleme lineaire obtenu en relaxant les conditions d’integralite des variables.C’est pourquoi on appelle ce programme la relaxation lineaire du probleme.

Les problemes de flots (programmation sur les graphes) sont eux a mi-cheminentre les problemes lineaires et les problemes mixtes. En effet, si les donnees duprobleme de flot a cout minimum (la formulation la plus generale d’un problemede flot) sont toutes entieres (demandes aux sommets entieres, capacites des arcsentieres et coefficients de cout entiers), la solution du probleme lineaire fournit au-tomatiquement une solution entiere. Autrement dit, ici la solution de la relaxationlineaire fournit la solution optimale du probleme mixte. Pour ces problemes, oupour ceux qui peuvent s’y ramener, on en conclut que l’on dispose d’un algorithmeperformant de calcul : l’algorithme du Simplexe.

Malheureusement, un grand nombre de problemes en nombres entiers ne peu-vent se mettre sous la forme de problemes de flot. Il convient donc pour cesproblemes d’avoir une methode tenant compte explicitement du caractere discretdes variables.

69

70 Chapitre 6. La programmation en nombres entiers.

6.2 Formulation des problemes mixtes

Nous allons voir quelques problemes classiques necessitant le recours a la pro-grammation mixte entiere.

6.2.1 Problemes avec couts fixes

Exemple 6.1 Problemes avec cout fixe de mise en route de la production. Onveut representer un cout de production qui est nul en l’absence de production etqui, dans le cas contraire, vaut la somme d’un cout fixe de production, note K, etd’un cout proportionnel, le taux marginal etant m.

On veut donc pouvoir exprimer la fonction suivante :

Si x = 0, c(x) = 0;Si x > 0, c(x) = K + mx.

(6.1)

ou x denote le niveau de production.

Cette fonction est representee a la figure 6.1.

K

c(x)

x

m

Figure 6.1: Representation d’un cout fixe

La representation mathematique de ce cout fixe necessite :

1. l’ajout d’une variable indicatrice d’une production positive :

y =

{1 si x > 00 si x = 0

2. la modification de la fonction objectif en :

c(x, y) = Ky + mx

qui devient donc purement lineaire;

Section 6.2. Formulation des problemes mixtes 71

3. l’ajout des contraintes suivantes :

x ≤ My, et y ∈ {0, 1} (6.2)

avec M une borne superieure sur la quantite produite (x).

Remarquons que si x > 0, par les relations (6.2), on a que y = 1 et on tientcompte du cout fixe de mise en route de production. Par contre, lorsque x = 0, (6.2)permet les choix y = 0 ou y = 1. Cependant, comme on minimise, l’optimiseurva automatiquement choisir y = 0, la solution qui evite le cout fixe !

Il y a de nombreuses applications de cette modelisation des couts fixes par laprogrammation mixte entiere. Un exemple de mise en application de ces coutsfixes est fournit par l’exemple de localisation d’entrepots ou il y a un cout fixed’ouverture de ces entrepots.

6.2.2 Problemes avec contrainte logique

Parfois des problemes de gestion comportent une condition logique. Un exempletypique est celui des problemes de gestion de projets avec contrainte disjonctive.Dans ces problemes, on doit determiner l’enchaınement des taches d’un projet demaniere a le realiser dans le meilleur delai, il se peut que deux taches doivent etreeffectuees par la meme equipe d’ouvriers, soit mettent en œuvre la meme machine.Les deux taches ne peuvent donc avoir lieu simultanement, sans que l’on puissedire laquelle doit etre effectuee en premier lieu. Mathematiquement, on peut ecrirececi par la condition suivante :

soit

{ti + di ≤ tj si i est realisee avant jtj + dj ≤ ti si j est realisee avant i

(6.3)

ou ti est la variable indiquant le temps de debut au plus tot de la tache i et di, saduree, est donnee.

Cette disjonction peut etre resolue par la programmation mixte binaire. Eneffet, definissons la variable binaire yij , dont la valeur est 1 si la tache i est realiseeavant la tache j et 0 si la tache j est realisee avant la tache i.

On remplace alors la condition de disjonction (6.3) par les contraintes suivantes :

ti + di ≤ tj + M(1 − yij)tj + dj ≤ ti + Myij

yij ∈ {0, 1}(6.4)

ou M note une borne superieure sur la date de fin des travaux.

Demontrons l’equivalence. Deux cas sont possibles pour la variable binaire :

72 Chapitre 6. La programmation en nombres entiers.

1. Cas ou yij = 1. Dans ce cas, le systeme (6.4) devient :{ti + di ≤ tjtj + dj ≤ ti + M

La premiere contrainte exprime donc que la tache i doit etre finie avant que necommence la tache j. La seconde contrainte est automatiquement satisfaite.

2. Cas yij = 0. Dans ce cas, le systeme (6.4) devient :{ti + di ≤ tj + Mtj + dj ≤ ti

La premiere contrainte est automatiquement satisfaite. La seconde contrainteexprime que la tache j doit etre finie avant que ne commence la tache i.

6.2.3 Melange avec nombre limite d’ingredients

Il s’agit egalement d’un probleme generique conduisant a une formulation mixteentiere, les variables binaires indiquant la presence ou non d’un ingredient dans lemelange.

C’est le cas, par exemple, d’un probleme de melange d’huiles ou cinq huilessont disponibles mais ou des contraintes techniques impliquent que seulement troishuiles differentes peuvent etre presentes dans le melange. Un autre exemple, estcelui du chargement de hauts fourneaux ou le nombre de charbons disponiblesest souvent nettement superieur au nombre de charbons qui peuvent etre chargessimultanement dans le haut fourneau. Ce nombre etant limite par le nombre deportes de chargement du haut fourneau.

Ce probleme peut etre resolu par la programmation mixte zero/un. Si xi

note la quantite d’ingredient i dans le melange, definissons la variable binaire yi

indiquant la presence de l’ingredient i dans le melange. Autrement dit :

yi = 1 si xi > 0;

yi = 0 si xi = 0.

On introduit alors les contraintes suivantes :

xi ≤ Miyi et yi ∈ {0, 1} (6.5)

ou Mi est une borne superieure sur xi.

La condition du nombre maximum d’ingredients dans le melange s’exprimealors simplement par :

n∑i=1

yi ≤ k, (6.6)

Section 6.2. Formulation des problemes mixtes 73

avec k, le nombre maximum d’ingredients dans le melange.

Demontrons l’equivalence. Deux cas sont possibles pour la variable xi :

1. Soit xi > 0. Alors, par les contraintes (6.5), la variable yi doit valoir 1 etexprime bien que l’ingredient i est dans le melange.

2. Soit xi = 0. Alors, par les contraintes (6.5), la variable yi peut valoir 0 ou1. La contrainte (6.6), exprimera donc bien que au plus k ingredients serontpris dans le melange.

Remarquez que si on veut que yi soit une parfaite indicatrice de xi > 0, il fautajouter la contrainte suivante :

miyi ≤ xi

avec mi, la teneur minimum d’un ingredient dans le melange. Cette nouvellecontrainte forcera yi a zero lorsque xi est nul.

6.2.4 Choix parmi un nombre discret de valeurs

Dans beaucoup de problemes industriels, lors du dimensionnement d’un appareil-lage, on doit choisir sa capacite parmi les valeurs commerciales existant sur lemarche. Par exemple, lors du dimensionnement d’une canalisation de transportd’eau, on doit choisir parmi les valeurs suivantes pour le diametre :

12 cm, 17 cm, 24 cm ou 47 cm.

On peut a nouveau modeliser ce choix par l’utilisation de variables binaires. Eneffet, definissons la variable x comme etant le diametre choisi et definissons yi uneindicatrice du fait que le diametre numero i a ete choisi. On peut alors ecrire larelation suivante pour le choix du diametre :

x = 12y1 + 17y2 + 24y3 + 47y4

avec la contrainte qu’un seul diametre doit etre choisi :

y1 + y2 + y3 + y4 = 1 (6.7)

et bien sur en imposant le caractere binaire de chaque indicatrice :

yi ∈ {0, 1}, ∀i = 1, 2. . .4

La contrainte (6.7) fera en effet qu’une seule indicatrice vaudra un tandis que toutesles autres seront a zero.

74 Chapitre 6. La programmation en nombres entiers.

6.3 Methode de branch and bound

La methode de “branch and bound” ou encore appelee methode de separation etevaluation que nous allons maintenant decrire est destinee a resoudre les problemesen nombres entiers du type suivant :

z∗ = max cTx

s.c.q.

{Ax ≤ b,

x ≥ 0 et entiers.

Cette methode peut egalement etre appliquee aux problemes avec variables binaires(zero-un). Elle peut egalement etre appliquee aux problemes mixtes (MIP), c’est-a-dire aux problemes comportant un certain nombre de variables entieres et uncertain nombre de variables continues.

Nous illustrons la methode sur l’exemple suivant tire de Norbert et al [15] :

z∗ = max z = 10x1 + 50x2

s.c.q.

−x1 + 2x2 ≤ 5,

x1 + 2x2 ≤ 14,

x1 ≤ 8,

x1 , x2 ≥ 0 et entiers

(6.8)

La region realisable est representee a la figure 6.2.

x1

x2

0 1 2 3 4 5 6 7 8

5

4

3

2

1

0

P0

P1 P2

P3

P5

Figure 6.2: Representation de la region realisable.

Remarquons qu’une facon de resoudre le probleme serait de construire une

Section 6.3. Methode de branch and bound 75

borne superieure sur z∗ et une borne inferieure sur z∗ et ensuite de raffiner cesbornes jusqu’a les egaliser.

Question 1 : comment construire une borne inferieure sur z∗ ?

La reponse a cette question est a la fois simple et difficile. En effet, pour trouverune borne inferieure, il suffit de donner une solution realisable pour (6.8). Commel’objectif est de maximiser, l’optimum du probleme ne pourra qu’etre superieur ala valeur de z en ce point. Cependant trouver en general une solution realisablepour un probleme en nombres entiers n’est pas une mince affaire.

Question 2 : comment construire une borne superieure sur z∗ ?

Une facon de repondre a cette question est de resoudre le probleme lineaireque l’on obtient a partir de (6.8) en laissant tomber les contraintes d’integralite desvariables. Comme on maximise sur un ensemble realisable plus large, l’optimumainsi obtenu ne pourra qu’etre superieur a l’optimum du probleme en nombresentiers. C’est aussi le premier pas de la methode de branch and bound que nousallons maintenant decrire sur l’exemple.

Pas 0. Resoudre la relaxation lineaire.

Pour cet exemple, on obtient comme solution de la relaxation lineaire le point noteP0 a la figure 6.2 :

x1 = 4, 5

x2 = 4, 75

z0 = 282, 5.

Cette solution est inacceptable car elle viole les contraintes d’integralite des va-riables. Cependant, elle fournit une premiere borne superieure sur z∗ :

z∗ ≤ 282, 5.

Pas 1. Brancher sur une variable non entiere.

La seconde idee de la methode de branch and bound est (comme le nom l’indique)d’operer une separation : la region realisable va etre separee en deux sous-regionsdont aucune ne peut contenir la solution optimale non entiere P0. Cette separationnecessite le choix d’une variable de separation. Le choix de cette variable estheuristique. Differents choix sont possibles et de ce choix peut dependre l’efficacitede la methode de resolution. Une facon simple de choisir cette variable est deprendre la variable la plus distante d’un entier. Une alternative, parfois utilisee,est de prendre la variable la plus proche d’un entier.

Dans notre exemple, il s’agit de la variable x1. On va effectuer un branchementsur cette variable. Comme x1 ne peut prendre que des valeurs entieres, il n’y a

76 Chapitre 6. La programmation en nombres entiers.

aucune perte de generalite d’imposer que

soit x1 ≤ 4 soit x1 ≥ 5

Cependant imposer cette condition va eliminer la solution courante P0 de la relaxa-tion lineaire. En general si la variable choisie xk a la valeur fractionnaire N + ε,on imposera :

soit xk ≤ N soit xk ≥ N + 1

En imposant separement l’une et l’autre conditions, on obtient deux sous-modeles, un modele fils et un modele fille. Ce que l’on represente par une dia-gramme du type de celui de la figure 6.3. Chaque nœud de cette figure correspond

z0 = 282, 5

x1 = 4,50x ,2 = 4 75

x1 4 x1 5

z1 = 265

x1 = 4x2 = 4, 5

z2 = 275

x1 = 5x2 = 4, 5

x2 4 x2 5

z3 = 260

x1 = 6x2 = 4

z4 = ∞Probleme

non realisable

x2 4 x2 5

z5 = 240

x1 = 4x2 = 4

z6 = ∞Probleme

non realisable

Figure 6.3: Arbre de branch and bound.

a un probleme lineaire. Le nœud 0 au modele original. Le nœud 1 est le modeleoriginal avec en plus la restriction x1 ≤ 4, tandis que le nœud 2 correspond aumodele original avec en plus la restriction x1 ≥ 5. On a ici numerote les nœudsdans l’ordre ou ils ont ete generes.

On peut maintenant resoudre les relaxations lineaires correspondant aux pro-blemes fils et fille. Dans notre exemple, on obtient les deux solutions suivantes :

Noeud 1 : x1 = 4, x2 = 4, 5, z1 = 265.

Noeud 2 : x1 = 5, x2 = 4, 5 z2 = 275.

Remarquez que les valeurs atteintes par la fonction objectif sont moins eleveesque dans la relaxation lineaire precedente. Ceci n’est pas etonnant : on a, en

Section 6.3. Methode de branch and bound 77

effet, ajoute des contraintes et donc restreint l’espace des solutions realisables.Comme les deux sous-regions forment une representation contenant l’ensembledes solution entieres, on peut en conclure que la borne superieure sur z∗ est :

z∗ ≤ max(z1, z2) = 275.

Pas 2. Diviser a nouveau un nœud fils ou fille en deux.

Ici, aucune des deux solutions n’est acceptable car toutes les deux comportent desparties fractionnaires. On va donc continuer en choisissant un des deux nœudspour le diviser a nouveau. Le choix du nœud a diviser est a nouveau heuristiqueet peut a nouveau avoir une grande influence sur le temps total mis pour resoudrele probleme.

Pour l’illustration de la methode, nous adoptons la regle de choix heuristiquesuivante : choisir le probleme dont la relaxation lineaire fournit la meilleure (c’est-a-dire la plus grande en cas de maximisation) valeur de la fonction objectif.

Pour cet exemple, on choisit donc le nœud 2 et on repete le Pas 1.

Pas 1. Choisir une variable pour brancher.

Ici seule la variable x2 est non entiere. On la choisit donc pour operer le branche-ment suivant :

soit x2 ≤ 4 soit x2 ≥ 5

On ajoute separement chacune de ces contraintes aux contraintes du probleme 2et on genere ainsi les nœuds 3 et 4. Ceci est illustre a la figure 6.3. On resoutgraphiquement les relaxations lineaires (voir figure 6.2) et on obtient les solutionssuivantes :

Noeud 3 : x1 = 6, x2 = 4, z3 = 260.

Noeud 4 : non realisable

Noter que, au nœud 3, on a obtenu une solution entiere dont la valeur correspon-dante de la fonction objectif est 260. On a une premiere borne inferieure sur lavaleur optimale de la fonction objectif et on a donc que :

260 ≤ z∗ ≤ 275

Si la fourchette n’est pas trop grande, on peut se satisfaire de cette solution nonoptimale plutot que de continuer de longs calculs. Il est clair egalement qu’il n’ya aucune raison de continuer a diviser le nœud 3 pour lequel la solution optimaledu probleme en nombres entiers a ete obtenue. On dit que le nœud est coupe.

Remarquons aussi que le nœud 4 a conduit a un probleme non realisable. Cen’est pas etonnant vu que l’on rajoute de plus en plus de contraintes. A nouveau,

78 Chapitre 6. La programmation en nombres entiers.

dans ce cas, il ne sert a rien de continuer a diviser ce nœud. Continuons la divisiondes autres nœuds.

Pas 2. Diviser a nouveau un nœud fils ou fille en deux.

On choisit le nœud 1 qui est le seul a encore diviser. Remarquez que c’est parceque la valeur de z1 = 265 est superieure a la borne inferieure 260 que l’on doitcontinuer. On a en effet un espoir de trouver ici une solution entiere meilleure que260. Dans le cas contraire, on aurait egalement coupe cette branche et la methodeetait terminee.

Pas 1. Brancher sur une variable non entiere.

On branche ici sur x2 en creant les nœuds 5 et 6 par la separation suivante :

soit x2 ≤ 4 soit x2 ≥ 5

On resout les relaxations lineaires correspondantes. On obtient :

Noeud 5 : x1 = 4; x2 = 4, z5 = 240

Noeud 6 : impossible

La methode est terminee puisqu’il n’existe plus de nœud a diviser. On deter-mine la solution optimale comme etant la meilleure solution entiere trouvee. Ils’agit du point P3 suivant :

x∗1 = 6

x∗2 = 4

auquel correspond une valeur optimale de l’objectif de z∗ = 260. On a ainsi, pournotre exemple, trouve et aussi prouve que la solution du nœud 3 etait la solutionoptimale du probleme en nombres entiers.

En conclusions, il y a trois raisons de couper une branche dans l’arbre :

1. lorsque la relaxation lineaire obtenue est non realisable,

2. lorsque la relaxation lineaire obtenue fournit une solution entiere,

3. lorsque la valeur de la borne superieure est inferieure a la valeur de la meil-leure solution entiere obtenue.

Enfin terminons par la remarque generale suivante. Si la region realisable dela relaxation lineaire n’est pas bornee, il n’y a pas de garantie de convergence de lamethode de branch and bound. Pour eviter ce probleme, certaines implementationsdemandent une borne inferieure et superieure sur chaque variable. On est ainsigaranti d’un nombre fini de branches dans l’arbre.

Section 6.4. Exercices 79

6.4 Exercices

6.1. Melange de maximum 4 charbons. Pour produire du coke, on melange descharbons dans un haut fourneau ou ensuite, une reaction a haute temperatureproduit le coke. On suppose qu’il y a 8 charbons disponibles. Ces charbonssont entres par des bandes porteuses qui sont au nombre de 4, permettantd’avoir au maximum 4 charbons differents dans le melange. De plus, si uncharbon est present dans le melange, il doit l’etre a hauteur de minimum5%. De plus, on exige que la teneur du melange en Silicium soit d’au plus1,8 % Le tableau 6.1 reprend les prix et teneur en Si des charbons. On

Charbon Prix Teneur Si Charbon Prix Teneur Si

Charbon 1 12 2,0 % Charbon 5 13 1,0 %

Charbon 2 14 2,5 % Charbon 6 9 5,0 %

Charbon 3 17 1,0 % Charbon 7 15 2,0 %

Charbon 4 10 5,0 % Charbon 8 11 1,5 %

Tableau 6.1: Teneurs en Si et prix des differents charbons.

veut determiner le melange repondant aux specifications qui soit de coutminimum.

6.2. Localisation optimale d’emetteurs de television. Etant donne une regioncomportant quatre villes (Lille, Dunkerque, Valencienne et Basieux), onveut savoir ou implanter, parmi divers emplacements disponibles (au nombrede 5), un ensemble d’emetteurs de television susceptibles de desservir cesdifferentes villes au moindre cout. La derniere colonne represente le coutde construction de chaque emetteur.

Ville Lille Dunkerque Valencienne Basieux Cout

Emetteur 1 1 1 25

Emetteur 2 1 1 30

Emetteur 3 1 1 15

Emetteur 4 1 1 35

Emetteur 5 1 1 1 90

Tableau 6.2: Accessibilite des villes a partir des emetteurs.

On demande d’ecrire le programme correspondant a la determination dunombre d’emetteurs a construire afin que chaque ville soit desservie par aumoins un emetteur et ceci a cout d’investissement total minimum.

80 Chapitre 6. La programmation en nombres entiers.

6.3. Probleme d’affectation de lignes aeriennes. Une petite compagnie aerien-ne dispose de six avions de 150 places. Elle desire affecter sa flotte d’avionsaux deux lignes interieures ouvertes a la concurrence (les lignes OM et OT).Le nombre de passagers desirant effectuer chaque jour un parcours sur laligne OM par cette nouvelle compagnie est 500, et de 200 sur la ligne OT. Lecout marginal (frais variables tels que le carburant, les taxes d’atterrissage,etc. . . ) d’un voyage sur la ligne OM est de 4 et de 3 sur la ligne OT. Ondesire minimiser le cout d’exploitation en satisfaisant la demande.

(a) Formuler mathematiquement le probleme de la meilleure affectationde la flotte de cette compagnie.

(b) Resoudre par la methode de Branch and bound en resolvant chaquefois la relaxation lineaire de maniere purement graphique !

Partie II

Les modeles sur reseau, dynamiques et nonlineaires.

81

Chapitre 7

Les modeles sur reseau

Dans ce chapitre, nous allons introduire differents modeles qui utilisent un graphedans leur formulation, soit pour representer un reseau (comme dans les problemesde transport), soit que le graphe soit une facon commode de representer le probleme(comme dans les problemes d’ordonnancement de projets).

Les origines des modeles sur reseaux sont nombreuses et debordent largementle cadre des seuls problemes de transport. On peut citer :

• Les problemes de distribution : il s’agit de determiner a partir de quellieu de production servir les differents points de consommation de maniere aminimiser les couts de transport : il existe plusieurs algorithmes de resolutionpour ce probleme (voir chapitre 9).

• Les problemes d’affectation optimale : il s’agit d’affecter des personnes ades postes de travail de maniere a maximiser l’efficacite generale : il s’agitd’un probleme en nombres entiers (on affecte entierement une personne aun poste ou pas du tout) qui peut etre resolu sans recourir a la methode de“Branch and Bound” (voir chapitre 6).

• Les problemes de planification des taches : il s’agit ici de determiner l’en-chaınement des taches d’un projet de maniere a terminer au plus vite entenant compte des relations d’anteriorite de certaines taches par rapport ad’autres. Il existe deux methodes de resolution : la methode potentiel et lamethode PERT (voir cours de licence).

• Les problemes de plus court chemin : il s’agit ici de trouver le chemin le pluscourt ou le moins couteux entre deux points donnes d’un reseau. Il existeun algorithme specialise : l’algorithme de Dijkstra (voir cours de licence).

Les modeles sur reseau sont le plus souvent des modeles lineaires qui peuventdonc etre resolus par l’algorithme du Simplexe mais pour lesquels il existe souventun algorithme specialise plus efficace que le Simplexe.

83

84 Chapitre 7. Les modeles sur reseau

7.1 Le probleme de transport simple

Le probleme de transport simple se rencontre lorsque l’on a un bien homogene(gaz, eau, electricite,. . . ) a transporter entre m lieux de production de capacitede production Ki connue et n lieux de consommation de demande dj connue demaniere a minimiser le cout total de transport sur le reseau. On connaıt cij ,le cout de fourniture d’une unite du producteur i au client j pour chaque couple(producteur, client).

La question qui se pose est la suivante : “Comment satisfaire la demande desconsommateurs a cout total de transport minimum tout en respectant les contraintesde capacite des producteurs ?”

Illustrons ceci sur un exemple tire de Williams [17]. Supposons qu’il y ait 3producteurs (m = 3) dont les capacites annuelles sont donnees au tableau 7.1.

Fournisseur 1 2 3

Capacite 135 56 93

Tableau 7.1: Capacite annuelle des fournisseurs

Il y a quatre 4 points de consommations (n = 4). Les demandes annuelles deces clients sont reprises au tableau 7.2.

Client 1 2 3 4

Demande 62 83 39 91

Tableau 7.2: Demandes annuelles des clients

Les couts de transport entre producteurs et clients sont repris au tableau 7.3.Les couts manquants indiquent que le fournisseur ne peut satisfaire le client.

Cout unitaire Client 1 Client 2 Client 3 Client 4

Fournisseur 1 132 - 97 103

Fournisseur 2 85 91 - -

Fournisseur 3 106 89 100 98

Tableau 7.3: Couts unitaires de fourniture

7.1.1 Representation au moyen d’un graphe

Nous allons voir comment le probleme de transport simple peut etre representepar un graphe. Rappelons la definition de graphe.

Section 7.1. Le probleme de transport simple 85

Definition 7.1 Un graphe est defini comme la paire G = (N, A) ou N representeun ensemble de nœuds et A un ensemble de couples (i, j), appeles arcs, avec i ∈ Net j ∈ N .

Ici, les nœuds representent les lieux de production ou de consommation alors queles arcs representent les liens physiques existant entre lieux de production et lieuxde consommation.

Le graphe associe au probleme de transport simple peut etre represente commea la figure 7.1. Il s’agit en fait d’un cas particulier de graphe : il s’agit d’ungraphe bipartite. On peut, en effet, isoler deux groupes de nœuds : les nœuds deproduction, d’une part, et les nœuds de consommation, d’autre part, et il n’existede liens (d’arcs) qu’entre les nœuds du premier ensemble et les nœuds du secondensemble. Autrement dit, on ne peut aller d’un lieu de production vers un clientque directement (sans passer par des points intermediaires).

3

2

1 1

2

s1 135

s2 56

s3 93

D2 = 83

D3 = 39

D4 = 91

D1 = 62

3

4

Figure 7.1: Exemple de probleme de transport simple

7.1.2 Formulation du probleme

Nous allons formuler le probleme de maniere classique (choix des variables,expression de la fonction objectif et des contraintes ).

1. Choix des variables : notons

xij la quantite transportee annuellement du producteur i au client j;

si la quantite prelevee annuellement chez le producteur i.

86 Chapitre 7. Les modeles sur reseau

2. Expression de la fonction objectif : l’objectif est simplement la minimisationde la somme des couts de transport entre producteurs et clients :

min z =∑

(i,j)∈A

cijxij

3. Formulation des contraintes : on a deux types de contraintes (cfr figure 7.1) :

(a) Contraintes de satisfaction de la demande : la somme des quantitesfournies par tous les producteurs a un client donne j doit etre egale asa demande : ∑

i|(i,j)∈A

xij = Dj, j = 1, . . .n

(b) Contraintes de capacite des producteurs : la somme des quantitesfournies par un producteur i a tous ses clients doit etre inferieure ouegale a sa capacite de production :

∑j|(i,j)∈A

xij = si ≤ Ki

Une condition necessaire de realisabilite du probleme est que la somme descapacites de production des producteurs soit suffisante pour couvrir la somme desdemande des clients :

m∑i=1

Ki ≥n∑

j=1

Dj

Il ne faut evidemment pas ajouter cette relation comme contrainte au modele.Mais il convient de verifier si cette condition est satisfaite avant de se lancer dansla resolution du modele. Si par exemple, la condition etait violee d’une certainequantite, il faudrait recourir, pour cette quantite a la sous-traitance.

Remarquez egalement que cette condition n’est pas suffisante dans le cas outous les producteurs ne peuvent servir tous les clients. Il existe au moins troismaniere d’interdire les chemins impossibles :

1. On peut imposer explicitement : xij = 0 pour tout (i, j) impossible.

2. On peut penaliser l’utilisation de tels chemins par un coefficient objectif cij

tres eleve.

3. On peut aussi restreindre les sommations aussi bien dans l’objectif que dansles contraintes aux seuls chemins (i, j) existants. C’est la solution retenuedans notre formulation.

Section 7.2. Planification de la production 87

7.2 Planification de la production

Le probleme de transport permet de modeliser des problemes qui a priori n’ontrien avoir avec la distribution, ainsi le probleme de planification de la productionsuivant tire de Williams [17].

Le probleme de planification de la production s’enonce ainsi. On produit unbien unique pour lequel la demande est connue pour les prochains mois. On connaıtaussi la capacite de production pour les prochains mois. La production en heuressupplementaires est egalement possible moyennant un surcout. Le tableau 7.4reprend les capacites (en heures normales et en heures supplementaires) ainsi quela demande pour les 4 premiers mois de l’annee.

Mois Janvier Fevrier Mars Avril

capacite (heures normales) 100 150 140 160

capacite (heures supplementaires) 50 75 70 80

Demande 80 200 300 200

Tableau 7.4: Capacites et demandes

Le cout de production est de 1 par unite produite en heures normales, alorsqu’il est de 1,5 par unite produite en heures supplementaires. Le cout de stockageest de 0,3 par mois et par unite stockee.

Nous allons maintenant formuler ce probleme en probleme de transport :

1. Choix des variables :Designons par xij la quantite produite en heures normales a la periode i poursatisfaire une demande de periode j avec i = 1, 2, . . .4 et j = i, i + 1, . . .4.De maniere semblable, yij designe la quantite produite en heures supple-mentaires a la periode i pour satisfaire une demande de periode j aveci = 1, 2, . . .4 et j = i, i + 1, . . .4.

Remarquez que l’on aurait egalement pu utiliser une seule variable a troisindices xijk ou k indiquerait le mode de production (k = 1 pour les heuresnormales et k = 2 pour les heures supplementaires).

2. Expression de l’objectif :Au cout de production (en heures normales ou en heures supplementaires),il faut ajouter autant de fois le cout de stockage qu’il n’y a de mois separantla production de la demande. Le tableau 7.5 reprend le calcul du cout totalde production et stockage.

Il n’y a evidemment pas de cout de production pour une production poste-rieure a la periode de demande.

88 Chapitre 7. Les modeles sur reseau

Demande

Production Janvier Fevrier Mars Avril

Janvier h.norm. 1 1,3 1,6 1,9

h.supp. 1,5 1,8 2,1 2,4

Fevrier h.norm. - 1 1,3 1,6

h.supp. - 1,5 1,8 2,1

Mars h.norm. - - 1 1,3

h.supp. - - 1,5 1,8

Avril h.norm. - - - 1

h.supp. - - - 1,5

Tableau 7.5: Couts de production et de stockage

3. Expression des contraintes :Outre les contraintes de positivite (xij, yij ≥ 0, i = 1, . . .4, j = 1, . . .4),il existe deux types de contraintes :

• Les contraintes de satisfaction de la demande s’ecrivent ici comme :

x11 + y11 = 80,

x12 + y12 + x22 + y22 = 200,

x13 + y13 + x23 + y23 + x33 + y33 = 300,

x14 + y14 + x24 + y24 + x34 + y34 + x44 + y44 = 200.

• Les contraintes de capacite s’ecrivent ici comme :

x11 + x12 + x13 + x14 ≤ 100,

y11 + y12 + y13 + y14 ≤ 50,

x22 + x23 + x24 ≤ 150,

y22 + y23 + y24 ≤ 75,

x33 + x34 ≤ 140,

y33 + y34 ≤ 70,

x44 ≤ 160,

y44 ≤ 80.

Remarquez que si l’on raisonne en termes de probleme de transport, les quan-tites xij sont des quantites transportees de la production au mois i vers une demandeau mois j et la somme des couts de production et de stockage joue ici le role decout de transport.

Section 7.3. Probleme d’affectation optimale 89

7.3 Probleme d’affectation optimale

Le probleme s’enonce de la maniere suivante. On a n personnes a affecter a npostes. On connaıt tij , le temps moyen mis par la personne i pour effectuer letravail au poste j. La question qui se pose est la suivante : “Comment affecter lespersonnes aux differents postes pour minimiser le temps total de realisation destaches ?”

Le probleme se formule de la maniere suivante.

1. Choix des variables :On note xij = 1 si personne i affectee au poste j, xij = 0, dans le cas contraire.

2. Formulation de l’objectif :L’objectif est de minimiser l’inefficacite totale de l’affectation :

min z =n∑

i=1

n∑j=1

tijxij

3. Formulation des contraintes : Il y a deux types de contraintes :

• chaque poste j doit etre pourvu :n∑

i=1

xij = 1, j = 1, . . .n

Cette contrainte exprime qu’exactement une personne est affectee achaque poste.

• chaque personne i est employee :n∑

j=1

xij = 1, i = 1, . . .n

Cette contrainte exprime qu’exactement un poste est affecte a chaquepersonne.

• et bien sur, il faut ajouter les contraintes d’integrite des variables :

xij ∈ {0, 1}

Le probleme d’embauche se rencontre lorsqu’il y a plus de personnes que depostes a pourvoir. Autrement dit, on a m personnes pour n postes avec m ≥ n.La seconde contrainte devient une inegalite.

Le probleme de transport simple peut etre generalise en permettant des nœudsintermediaires qui ne soient pas des nœuds source (nœud d’offre) ou des nœudspuits (nœuds de demande). On obtient ainsi le probleme de transport general.

90 Chapitre 7. Les modeles sur reseau

7.4 Le probleme de transport general

Le probleme de flot a cout minimum est illustre par l’exemple tire de Williams[17] repris a la figure 7.2. On a deux lieux de productions (deux sources) auxnœuds 0 et 1 et trois lieux de consommation (trois puits) aux nœuds 5, 6 et 7. Lescouts unitaires de transport sont indiques au dessus des arcs. On veut determiner

-10

+15

5

4

2

4

6

1

5

6

3

2

-9

-6

4

0

1

2

3

4

5

6

7

+10

Figure 7.2: Probleme de flot a cout minimum

comment satisfaire la demande des differents puits par des flux circulant a traversle reseau depuis les sources a cout total minimum.

On peut formuler le probleme de transport general comme suit :

1. Choix des variables :On appelle xij la quantite transportee entre le nœud i et le nœud j.

2. Expression de l’objectif :L’objectif correspond simplement a la minimisation des couts de transport :

min z =∑

(i,j)∈A

cijxij.

ou cij note le cout de transport unitaire sur l’arc (i, j).

3. Contraintes du probleme :Les contraintes expriment la conservation du flux aux nœuds. La somme desflux entrant dans un nœud est egale a la somme des flux sortant du nœud :

10 = x02

15 = x13

x02 + x42 = x23 + x24 + x25

x23 + x13 = x34 + x37

Section 7.4. Le probleme de transport general 91

x24 + x34 = x42 + x45 + x46

x25 + x45 = 9

x46 + x76 = 10

x37 = x76 + 6

En mettant toutes les variables a gauche et toutes les constantes a droite, on obtientle systeme suivant d’egalites :

x02 = 10

x13 = 15

−x02 +x23+x24+x25 −x42 = 0

−x13−x23 +x34+x37 = 0

−x24 −x34 +x42+x45+x46 = 0

−x25 −x45 = −9

−x46−x76 = −10

−x37 x76 = −6

En isolant les coefficients de ces contraintes, on obtient ce que l’on appellela matrice d’incidence nœuds/arcs qui a comme particularite que chaque co-lonne ne comporte qu’un coefficient +1 et un coefficient -1. Chaque colonnecorrespond a un arc, et il y a un +1 dans la ligne correspondant au nœud d’ou estissu l’arc et il y a un -1 dans la ligne correspondant au nœud destination de l’arc :

02 13 23 24 25 34 37 42 45 46 76

0 1

1 1

2 −1 1 1 1 −1

3 −1 −1 1 1

4 −1 −1 1 1 1

5 −1 −1

6 −1 −1

7 −1 1

Nous allons maintenant voir un certain nombre de cas particuliers de ce probleme.

7.4.1 Probleme du plus court chemin

Le probleme du plus court chemin est celui qui se pose lorsque l’on veut allerd’un point a un autre sur un reseau routier par la route la plus courte. A la figure 7.3,

92 Chapitre 7. Les modeles sur reseau

1

1

1

2 11

3

4

1

2

2

1

1

2

0

1 2

4

5

6

7

8

3

3

Figure 7.3: Probleme du plus court chemin

on a represente les distances entre les divers points. On se demande quel est leplus court chemin entre le nœud 0 et le nœud 8. Remarquez que ce probleme etrereformule en un probleme de flot a cout minimum. Au nœud origine, le nœud 0,il suffit de mettre une source de capacite unitaire et au nœud destination, le nœud8, un puits de demande unitaire. On utilise alors un algorithme specialise pourdeterminer le flot a cout minimum qui satisfait cette demande unitaire. Il existecependant un algorithme specialise pour resoudre ce probleme : l’algorithme deDijkstra (voir cours de licence).

7.4.2 Probleme du flot maximum

Le probleme du flot maximum est celui que l’on rencontre lorsque l’on veut, pourun reseau de transport, determiner le flot maximum de voitures qu’il peut supporteravant d’arriver a saturation. Etant donne des capacites des arcs (voir les chiffres

12

20

6

2

3

7

6

5

8

9 4

0

1

2

3

4

5

6

7

E

S

Figure 7.4: Probleme du flot maximum

indiques au dessus des arcs a la figure 7.4), on veut maximiser le flot entre lessources et les puits. Si l’on rejoint toutes les sources a une source unique et tousles puits a un puits unique, et que l’on trace l’arc de retour entre le puits unique etla source unique, cela revient a maximiser le flux dans l’arc retour.

Section 7.5. Exercices 93

7.5 Exercices

7.1. Planification de la production de moteurs d’avions. Une entreprise defabrication de moteurs d’avions travaille uniquement sur commandes. Letableau 7.6 fournit en le nombre de moteurs a fournir en fin de chaque moispour les quatre prochains mois. En fonction des operations de maintenance,la capacite de production varie de mois en mois. Le cout unitaire de produc-tion varie egalement de mois en mois (voir tableau 7.6). Au vu des donnees,il est clair qu’il faudra recourir au stockage. On se demande comment orga-niser la production du moteur pour minimiser les couts de production et destockage. Formuler le probleme comme un probleme sur reseau.

Mois Commandes Capacite Cout de production Cout de stockageJanvier 10 25 1,08 0,015Fevrier 15 35 1,11 0,015Mars 25 30 1,10 0,015Avril 20 10 1,13 0,015

Tableau 7.6: Production de moteurs d’avions.

7.2. Amelioration d’un reseau routier. On prevoit une augmentation du traficentre les villes A et F. On veut determiner quel est le flot maximum devehicules entre A et F que peut supporter le reseau. Les capacites des arcs,exprimees en milliers de voitures par heure, sont reprises au tableau 7.7.

Arc Origine Destination Capacite1 A B 32 A C 73 C B 24 C D 25 B D 46 C E 47 E D 28 D F 69 E F 5

Tableau 7.7: Capacites des arcs d’un reseau routier.

(a) Representer le probleme sur un graphique de reseau.

(b) Formuler mathematiquement le probleme.

94 Chapitre 7. Les modeles sur reseau

7.3. Tournees de vehicules. Considerons le probleme d’organisation des tour-nees de vehicules pour la collecte des dechets. La collectivite locale disposede 12 vehicules pour collecter dans 4 villes. Ces vehicules sont attribues achaque ville : 4 a la ville 1, 3 a la ville 2, 1 a la ville 3 et 4 a la ville 4. Les

Vers ville 1 ville 2 ville 3 ville 4 incinerateurDe la ville 1 0 10 ∞ ∞ 45

De la ville 2 10 0 5 ∞ ∞De la ville 3 ∞ 5 0 5 20

De la ville 4 ∞ ∞ 5 0 ∞De l’incinerateur 45 ∞ 20 ∞ 0

Tableau 7.8: Temps de parcours

temps de trajets entre ces villes et l’incinerateur sont donnes au tableau 7.8.On veut minimiser le temps total pour aller a l’incinerateur.

(a) Representer le probleme sur un graphique de reseau.

(b) Formuler mathematiquement le probleme.

7.4. Mutation des officiers. L’armee a une politique de mutation reguliere deses officiers. Tous les trois ans, ces officiers sont mutes a un autre poste pourassurer la polyvalence du commandement et eviter que trop de fraternite nes’installe entre les officiers et la troupe. L’armee, pour etablir son plan demutation, tient compte du desagrement d’etre mute loin de sa base d’origine.Et il est clair que, par exemple dans le cas d’un officier marie dont la femmetravaille dans le civil, le desagrement sera d’autant plus grand que la nouvelleaffectation sera eloignee. Pour les 5 officiers a muter cette annee, on aetabli le cout de les affecter a chacun des 4 autres postes occupes par lescollegues. On desire determiner l’affectation des officiers qui minimise

Cout pour d’etre mute au postel’officier a b c d e

A - 12 15 11 17B 6 - 14 12 16C 8 17 - 21 17D 7 16 9 - 12E 7 13 8 12 -

le desagrement total (c’est-a-dire la somme des desagrements individuels).Formuler mathematiquement le probleme.

Chapitre 8

Resolution du probleme de transportsimple

8.1 Introduction

Dans ce chapitre, nous allons presenter un algorithme de resolution du probleme detransport simple introduit au chapitre 7. Pour rappel, il s’agit du probleme obtenulorsque que le reseau ne comporte que deux types de nœuds, d’une part les nœudsd’offre et, d’autre part les nœuds de demande et que les arcs vont uniquement desnœuds d’offre aux nœuds de demande. L’algorithme de resolution faisant appel ala notion de couts reduits, nous introduirons d’abord cette notion.

8.2 Notion de cout reduit

Dans plusieurs algorithmes de resolution de problemes sur reseau, on utilise lanotion de cout reduit d’un arc.

Definition 8.1 Supposons qu’a chaque nœud i ∈ N , on associe un nombre π(i),que nous appellerons le potentiel du nœud. On definit le cout reduit de l’arc (i, j)comme

cπij = cij − π(i) + π(j) (8.1)

Prenons un exemple d’utilisation de la notion de cout reduit. Il s’agit duprobleme du calcul de la plus courte distance entre deux points dans un graphe(voir cours de licence). L’algorithme de Dijkstra calcule la fonction di qui donnela distance du plus court chemin entre le point d’entree sur le reseau et le point i.Considerons un arc quelconque du reseau comme illustre a la figure 8.1. Ainsi di

note la distance du plus court chemin depuis l’entree sur le reseau jusqu’au point iet dj note la distance du plus court chemin jusqu’au point j tandis que cij indique

95

96 Chapitre 8. Resolution du probleme de transport simple

di

icij

j

dj

Figure 8.1: Notion de cout reduit d’un arc (i, j)

la longueur de l’arc (i, j). A l’optimum, la condition suivante doit etre verifiee :

dj ≤ di + cij (8.2)

Justifions ceci. En effet, soit le plus court chemin menant de l’entree du reseau aunœud j passe par l’arc (i, j) et on a donc que

dj = di + cij

Soit le plus court chemin passe par un autre arc et passer par i est plus long :

dj < di + cij

Dans les deux cas, on a bien que (8.2) est satisfaite. Ce qui peut se recrire :

cij + di − dj ≥ 0, ∀(i, j) ∈ A

En posant πi = −di, il est equivalent de dire que

cπij = cij − πi + πj ≥ 0, ∀(i, j) ∈ A

Autrement dit que les couts reduits sont tous positifs ou nuls.

Illustrons ceci sur l’exemple de la figure 8.2.

41

d1 = 0

d2 = 2

d3 = 2

d4 = 3

c12 = 2

c13 = 2

c23 = 1

c24 = 3

c34 = 1

2

3

Figure 8.2: Application de la notion de cout reduit.

Pour determiner di la plus courte distance du nœud origine 1 au nœud i, onutilise l’algorithme de Dijkstra. Pour rappel, celui-ci stocke deux informationsen chaque nœud :

Section 8.2. Notion de cout reduit 97

1. le label courant du nœud, note di, qui indique la distance entre le nœudorigine et le nœud i par le plus court chemin trouve jusqu’a present;

2. le predecesseur courant du nœud, note pi, dans le plus court chemin trouvejusqu’a present entre le nœud origine et i.

L’algorithme de Dijkstra utilise et met a jour deux ensembles :

1. L’ensemble T des nœuds dont on a determine exactement le plus courtchemin entre le nœud origine et ces nœuds. C’est l’ensemble des nœudsdeja traites et qui ne necessitent donc plus de traitement ulterieur.

2. L’ensemble S = N \ T des nœuds qui sont encore a traiter. On dit qu’ilsont un un label provisoire qui pourra encore eventuellement etre ameliore.

Rappelons le principe de l’algorithme. Soit o l’indice du nœud origine.

Algorithme 8.1 Algorithme de Dijkstra.

1. Initialisations. Mettre lo = 0; T = {o}; S = N \ T .Pour tout nœud j ∈ S qui peut etre atteint a partir de o par un arc (o, j), onmet comme label provisoire de j le temps de parcours de l’arc (o, j) :Pour tout j ∈ S, si j tel que (o, j) ∈ A alors dj ← coj , sinon dj ← ∞;

2. Iteration k. On selectionne l’element q ∈ S de label provisoire dq minimum :

q ∈ S|dq = minj∈S

dj

Ce nœud q est deplace de l’ensemble S vers l’ensemble T :

T = T ∪ {q} et S = S \ {q}

On remet alors a jour les labels provisoires des elements de S. Pour toutnœud j ∈ S qui peut etre atteint a partir de q par un arc (q, j), on examine sile chemin menant a j en passant par q ne serait pas plus court que l’ancienchemin menant a j. Dans ce cas, dj et pj sont remis a jour comme suit :

Si dq + cqj < dj, alors dj = dq + cqj

et pj = q

3. Terminaison. L’algorithme s’arrete des que l’on a determine le labeldefinitif du sommet de destination d, c’est-a-dire des que d ∈ T :Repeter ii) jusqu’a ce que le sommet de destination d ∈ T .La distance du plus court chemin de o a d est tout simplement ld.

98 Chapitre 8. Resolution du probleme de transport simple

Voyons maintenant l’application de cet algorithme a notre exemple :

Initialisations : on marque definitivement le nœud 1 qui permet d’atteindre lesnœuds 2 et 3 :

i 1 2 3 4

di 0 2 2 +∞pi − 1 1 −

Iteration 1 : on marque definitivement le nœud 2 de label provisoire minimum.Ce nœud permet d’atteindre le nœud 4 :

i 1 2 3 4

di 0 2 2 5

pi − 1 1 2

Iteration 2 : on marque definitivement le nœud 3 de label provisoire minimum.Ce nœud permet d’atteindre le nœud 4 plus rapidement que par le nœud 2 :

i 1 2 3 4

di 0 2 2 3

pi − 1 1 3

Iteration 3 : on marque definitivement le nœud 4 et l’algorithme est termine.

On a determine les plus courtes distances de 1 a tous les nœuds. En posantπi = −di, on peut en deduire

π1 = 0, π2 = −2, π3 = −2, π4 = −3.

On en deduit le calcul des couts reduits (cπij = cij − πi + πj) :

cπ12 = 2 + 0 − 2 = 0

cπ13 = 2 + 0 − 2 = 0

cπ23 = 1 + 2 − 2 = 1

cπ24 = 3 + 2 − 3 = 2

cπ34 = 1 + 2 − 3 = 0

qui s’interprete comme le surcout d’utiliser cet arc par rapport au plus court chemin.

Section 8.3. Le probleme de transport simple 99

8.3 Le probleme de transport simple

Rappelons la formulation du probleme du transport simple pour lequel il existeseulement deux types de nœuds : les nœuds d’entree (ou encore nœuds d’offredont l’ensemble est note Ns) et les nœuds de sortie (ou encore nœuds de demandedont l’ensemble est note Nd). Il n’y a donc pas de nœuds d’interconnexion. C’estla premiere hypothese simplificatrice. On suppose egalement, c’est la secondehypothese, que les arcs liant les nœuds d’entree aux nœuds de sortie ont unecapacite infinie. On peut donc representer le probleme par un graphe bipartitecomme illustre a la figure 8.3.

m

2

1

n

1

2

sd

E S

Figure 8.3: Probleme de transport simple.

On choisit comme variable xij pour designer la quantite transportee de i a j.L’objectif est donc la minimisation des couts de transport entre les nœuds d’entreeet les nœuds de sortie. Seuls ces arcs ont un cout associe dij . L’objectif se formuledonc comme

z = min∑

(i,j)∈A

cijxij

ou A est l’ensemble des arcs de transport (correspondant au reseau ”ouvert” obtenusans considerer le nœud d’entree et le nœud de sortie).

Il est evident que si transporter du flot coute, on va, a la solution optimale, toutjuste satisfaire la demande en chaque nœud de demande. Autrement dit, on auraque : ∑

i|(i,j)∈A

xij = dj ∀j ∈ Nd

Supposons que l’offre totale soit egale a la demande globale, autrement dit que∑i∈Ns

si =∑

j∈Nd

dj

100 Chapitre 8. Resolution du probleme de transport simple

On peut, en effet, se ramener a ce cas en ajoutant un nœud de demande supplemen-taire auquel on attribue l’excedent d’offre sur la demande (

∑i∈Ns

si −∑

j∈Nddj)

et que l’on raccorde a chaque nœud d’offre par un arc de capacite infinie et de coutde transport nul.

Dans ce cas, chaque arc d’entree doit egalement etre utilise a pleine capaciteet nous aurons semblablement que∑

j|(i,j)∈A

xij = si ∀i ∈ Ns

On voit donc qu’avec les hypotheses faites dans le cas du reseau de transportsimple, les flux circulant sur les arcs entrant et sortant sont connus a priori. Lesseules inconnues du probleme sont les flux fij dans les arcs de transport. On adonc la formulation mathematique suivante pour le probleme du transport simple.

z = min∑

(i,j)∈A

cijxij

s.c.q.

∑j|(i,j)∈A

xij = si ∀i ∈ Ns

∑i|(i,j)∈A

xij = dj ∀j ∈ Nd

xij ≥ 0 ∀(i, j) ∈ A

(8.3)

8.4 Resolution du probleme de transport simple

Nous allons illustrer la resolution du probleme de transport simple sur l’exemplesuivant tire de Baglin et al [2]. Trois usines situees a Lyon, Strasbourg et Lillepeuvent approvisionner quatre depots situes a Saint-Brieuc, Poitiers, Melun etToulouse. Le tableau 8.1 fournit (en F par tonne) les tarifs des transporteursroutiers de chaque usine vers chaque depot.

Le tableau donne egalement la capacite de production (exprimee en milliers detonnes) et la demande des depots (dans la meme unite).

On cherche l’affectation usines-depots permettant d’aboutir a un cout de trans-port minimum.

8.4.1 Resolution par le Simplexe

Appelons cij le cout unitaire de transport de l’usine i vers le depot j, CAPi, lacapacite de l’usine i et DEMj , la demande du depot j. Comme vu plus haut, en

Section 8.4. Resolution du probleme de transport simple 101

Cout de Destination Capacite

fourniture St-Brieuc Poitiers Melun Toulouse de

venant de l’usine

Lyon 264 130 139 160 9

Strasbourg 279 244 146 307 17

Lille 200 166 66 278 9

Demande 10 14 7 4

Tableau 8.1: Resolution du probleme de transport simple

appelant xij la quantite transportee de l’usine i au depot j, le probleme se formulecomme suit :

z = min3∑

i=1

4∑j=1

cijxij

s.c.q.

4∑j=1

xij = CAPi ∀i = 1, . . .3

3∑i=1

xij = DEMj ∀j = 1, . . .4

xij ≥ 0 ∀(i, j)

(8.4)

Remarquez que le probleme est parfaitement equilibre car :

3∑i=1

CAPi =4∑

j=1

DEMj

Ce probleme lineaire peut etre resolu par l’algorithme du Simplexe (voir chapitre3) qui donne la solution optimale suivante :

• Lyon envoie 5.000 T a Poitiers et 4.000 a Toulouse;

• Strasbourg envoie 8.000 T a St-Brieuc et 9.000 a Poitiers;

• Lille envoie 2.000 T a St-Brieuc et 7.000 a Meulun.

Le cout global de transport de cette solution est de 6.580 kF.

102 Chapitre 8. Resolution du probleme de transport simple

8.4.2 Resolution par la methode du stepping stone

Le principe de cette methode consiste a partir d’une solution realisable que l’onameliore pas a pas. D’ou le nom de la methode. Pour la determination d’unesolution de depart, au moins deux methodes heuristiques peuvent etre utilisees :

• la methode du coin Nord-Ouest;

• la methode de Houthakker.

La methode du coin Nord-Ouest :

La methode du coin Nord-Ouest consiste a attribuer le plus grand nombre possiblea la case situee le plus a l’Ouest (1er critere) et le plus au Nord (2eme critere)possible tout en respectant les contraintes de capacite de production et de demande.

Dans notre exemple, on partira donc d’une solution consistant a livrer 9.000T de Lyon a St-Brieuc. Toute la capacite de Lyon etant utilisee, on sature lademande de St-Brieuc par 1.000 T venant de Strasbourg. On passe a la deuxiemecolonne que l’on rempli a partir du Nord. Lyon etant saturee, on envoie 14.000T de Strasbourg vers Poitiers dont la demande est ainsi saturee. On passe a latroisieme colonne. On utilise les 2.000 T restantes de Strasbourg completees de5.000 T venant de Lille pour saturer la demande de Melun. Enfin, la demande deToulouse est satisfaite a partir des 4.000 T restant disponibles a Lille. On obtiendrala solution du tableau 8.2 pour un cout total de transport s’elevant a 7 805 kF.

Fourniture Destination Capacite

venant St-Brieuc Poitiers Melun Toulouse de

de l’usine

Lyon 9 9

Strasbourg 1 14 2 17

Lille 5 4 9

Demande 10 14 7 4

Tableau 8.2: Heuristique du Coin Nord-Ouest

Heuristique de Houthakker :

La methode de Houthakker propose de commencer par saturer les liaisons (i, j)presentant le cout de transport unitaire cij le plus faible. Melun est livree par l’usine

Section 8.4. Resolution du probleme de transport simple 103

de Lille (66 F la tonne). Ensuite Lyon approvisionnera Poitiers, a concurrence de9.000 T. Le cout minimum suivant est 139 de Lyon a Melun mais la capacite deLyon est saturee. Ensuite, le cout minimum de 146 est de Strasbourg a Meulun.Mais la demande de Meulun est saturee. Puis le cout minimum est de 160 de Lyona Toulouse mais a nouveau Lyon est saturee. Ensuite, on envoie 2.000 T de Lille aPoitiers au cout unitaire de 166, la capacite de Lille etant ainsi saturee. Ensuite lecout minimum de 200 est de Lille a St-Brieuc mais la capacite de Lille est saturee.Ensuite, on envoie 3.000 T de Strasbourg vers Poitiers au cout unitaire de 244,ce qui sature la demande de Poitiers. Les deux couts unitaires minimum suivant(264 et 278) correspondent a des capacite et demande saturees. On envoie ensuite10.000 T de Strasbourg a St-Brieuc. On sature ainsi la demande de St-Brieuc. Etfinalement, on envoie les 4.000 T restantes de Strasbourg a Toulouse. On obtiendrale tableau 8.3 pour un cout de 6.714 kF.

Fourniture Destination Capacitevenant St-Brieuc Poitiers Melun Toulouse de

de l’usineLyon 9 9

Strasbourg 10 3 4 17Lille 2 7 9

Demande 10 14 7 4

Tableau 8.3: Heuristique du Houthakker

On voit que l’on est deja beaucoup plus proche de la solution optimale (de coutegal a 6.580 kF). Remarquez que si deux cases sont de cout minimum, on choisiracelle ou l’on peut attribuer le plus grand nombre : ceci aura pour effet de mettrecomme coefficient du cout minimum la plus grande valeur d’une variable.

Amelioration de la solution de base :

Pour chaque case presentant une valeur nulle, on calcule le cout marginal engendrepar le deplacement d’une unite des cases affectees voisines vers celle-ci.

Par exemple, si on veut affecter une unite de Lyon a St-Brieuc, le respectdes contraintes nous oblige a enlever une unite de la case Strasbourg-St-Brieuc, aenlever une unite de la case Lyon-Poitiers et a ajouter une unite a la case Strasbourg-Poitiers. Ce qui represente un cout de

+264 − 130 − 279 + 244 = +99.

Le solde etant positif, l’operation n’est pas interessante.

104 Chapitre 8. Resolution du probleme de transport simple

Poitiers MelunLyon -1 (x 130) +1 (x 139)Lille +1 (x 166) -1 (x 66)

Tableau 8.4: Calcul du deuxieme cout marginal

L’ajout d’une unite de Lyon a Meulun est illustree au tableau 8.4. Ce quirepresente un cout de

−130 + 139 + 166 − 66 = +109.

Le solde etant positif, l’operation n’est pas interessante.

L’ajout d’une unite de Lyon a Toulouse est illustree au tableau 8.5. Ce qui

Poitiers ToulouseLyon -1 (x 130) +1 (x 160)

Strasbourg +1 (x 244) -1 (x 307)

Tableau 8.5: Calcul du troisieme cout marginal

represente un cout de

−130 + 160 + 244 − 306 = −33.

Le solde etant negatif, cette modification ameliore la solution precedente. On peutdeplacer 4.000 T et gagner 4 × 33 = 132 kF.

Le meme raisonnement applique a la case Lille-St-Brieuc permet encore dedeplacer 2.000 tonnes de la case Lille-Poitiers a la case Strasbourg-Poitiers etaussi 2.000 T de Strasbourg-St-Brieuc a Lille-St-Brieuc, pour obtenir la solutionoptimale determinee par le Simplexe.

Toute modification se traduirait alors par une augmentation du cout global.Notez que l’algorithme de stepping stone choisit a chaque etape comme variablecelle de cout marginal le plus negatif.

Calcul des couts marginaux

Une methode permet de reduire fortement le temps de calcul des couts reduits.En effet, on peut montrer (cela resulte du principe de dualite de la programmationlineaire) qu’il existe des variables auxiliaires ui et vj telles que pour chaque casede base (c’est-a-dire chaque case utilisee dans la solution de depart), on ait :

ui + vj = cij

Section 8.4. Resolution du probleme de transport simple 105

Pour la solution du tableau 8.3, on a donc que :

u1 + v2 = 130

u2 + v1 = 279

u2 + v2 = 244

u2 + v4 = 307

u3 + v2 = 166

u3 + v3 = 66

Il s’agit d’un systeme de 6 equations a 7 inconnues. On peut donc arbitrairementfixer a zero la valeur d’une variable (par exemple u1). On en deduit immediatementla valeur de toutes les autres variables :

u1 = 0

v2 = 130

u2 = 114

u3 = 36

v1 = 165

v4 = 193

v3 = 30

On peut alors calculer les couts marginaux par la formule suivante (c’est la formulede calcul des couts reduits de l’algorithme du Simplexe) :

dij = cij − (ui + vj)

Ceci est fait au tableau 8.6.

v1 = 165 v2 = 130 v3 = 30 v4 = 193u1 = 0 264 - 0 130 - 0 139 -0 160 - 0

-165 =99 -130 = 0 -30 = 109 -193 = -33u2 = 114 279 -114 244 -114 146 -114 307 -114

-165 = 0 -130 = 0 - 30 = 2 -193 = 0u3 = 36 200 -36 166 -36 66 -36 278 -36

-165 = -1 -130 = 0 - 30 = 0 -193 = 49

Tableau 8.6: Calcul des couts marginaux

On retrouve bien les valeurs +99, +109 et -33 deja calculees plus haut.

106 Chapitre 8. Resolution du probleme de transport simple

8.5 Exercices

8.1. Plan de transport. Une entreprise, specialisee dans la production de sau-cisses, dispose de 4 laboratoires ou elle elabore son produit et de 5 centresde distribution d’ou elle ravitaille sa clientele. Le tableau 8.7 indique lesdistances entre les laboratoires et les centres de distribution. Le transport a

dij CD1 CD2 CD3 CD4 CD5 OffreL1 100 300 250 450 250 26L2 50 200 250 450 250 24L3 250 100 50 350 300 27L4 300 150 200 250 450 23

Demande 18 20 22 19 21

Tableau 8.7: Couts unitaires de transport

ete negocie au tarif kilometrique de 2 $ la tonne. La disponibilite (en tonnede chair) des differents laboratoires est egalement donnee au tableau 8.7. Lademande des centres de distribution est donnee en derniere ligne du tableau.L’entreprise cherche le plan d’acheminement a cout minimal des laboratoiresaux centres de distribution. Calculer une solution par l’heuristique du coinNord-Ouest et par celle d’Houthakker.

8.2. Probleme de transport. On dispose de deux usines de production dontles debouches sont situes sur trois marches distants geographiquement. Onconnaıt la capacite de production de chacune des usines ainsi que la demandede chacun des marches. On dispose egalement (voir tableau 8.8 pour lesdonnees precises) des distances, exprimees en milliers de miles, entre lessites de production et les marches.

Usines Marches Offre

New York Chicago Topeka

Seattle 2.5 1.7 1.8 350

San Diego 2.5 1.8 1.4 550

Demande 325 300 275

Tableau 8.8: Les donnees numeriques du probleme de transport.

Les frais de transport sont de 90 $ par millier de miles. On se demandecombien d’unites du produit acheminer a chaque marche a partir de chaqueusine de maniere a minimiser les couts de transport.

Chapitre 9

Resolution du probleme de transportgeneral

9.1 Introduction

Nous allons voir ici comment resoudre le probleme de transport general introduitau chapitre 7. Il s’agit de determiner le flot a cout minimum dans un reseau detransport general. L’algorithme faisant appel a la notion de cout reduit introduiteau chapitre 8. Elle fait egalement appel a notion de reseau residuel. Aussi, nouscommencerons par introduire cette notion a la section 9.2.

Nous presenterons ensuite l’algorithme de plus courts chemins successifs.Le principe de cet algorithme est le suivant : on determine un plus court cheminentre un nœud d’entree et un nœud de sortie non satures en utilisant le reseauresiduel (celui ou il reste de la capacite de transport). On determine alors le fluxmaximum qui peut etre transmis le long de ce chemin. On augmente le flot et onitere jusqu’a saturer tous les points de demande.

D’autres algorithmes existent pour resoudre ce probleme. On en trouvera unedescription dans Ahuja et al[1].

Nous verrons ensuite a la section 9.4 l’application de cet algorithme a laresolution du probleme d’affectation.

9.2 Notion de reseau residuel

Dans plusieurs algorithmes, on cherche a augmenter le flot par rapport a la situationactuelle du flot. Il est alors interessant d’identifier non pas le reseau actuel maisle reseau residuel, c’est-a-dire celui qui permet de faire passer un supplement deflux.

Considerons un arc (i, j)dont le flux doit etre compris entre une borne inferieure

107

108 Chapitre 9. Resolution du probleme de transport general

0 et une borne superieure egale a la capacite de l’arc cij (voir figure 9.1). Si lavaleur actuelle du flux sur cet arc est fij , il est facile de voir que l’on peut faireencore passer en flux dans l’arc (i, j) un supplement de flux egal a la capaciteresiduelle rij qui se calcule comme suit :

rij = cij − fij

Mais on peut egalement faire passer du flux dans l’autre sens en ajoutant un arc dej a i de capacite residuelle :

rji = fij

En effet, on peut ramener le flux a sa borne inferieure zero, ou ce qui est equivalent,faire circuler un flux au maximum de fij dans un arc de j a i.

di

icij

j

dj di

i j

dj

rij = cij fij

rji = fij

Figure 9.1: Notion de reseau residuel

On construit le reseau residuel en remplacant systematiquement un arc (i, j)qui n’est pas a sa borne superieure par un arc dans le meme sens avec commecapacite residuelle la difference entre la capacite de l’arc et le flot actuel. Dememe, si le flux sur cet arc n’est pas a sa borne inferieure, on ajoute un arc en sensoppose dont la capacite residuelle est egale a la valeur actuelle du flux.

Definition 9.1 Le reseau residuel, note G(f) consiste en les seuls arcs ayant unecapacite residuelle rij positive

Remarquez que ce faisant, on peut etre amener a remplacer un arc du reseau initialG, soit par un arc de meme sens (cas du flux nul), soit par deux arcs (cas du fluxstrictement entre ses bornes inferieure et superieure) soit par un arc dans le sensoppose (cas du flux a sa borne superieure). Remarquez egalement que la notionde reseau residuel est dependante du flot actuel, ce que traduit la notation G(f).

9.3 Resolution du probleme de flot a cout minimum

Plusieurs algorithmes existent pour resoudre ce probleme. Le lecteur interesse entrouvera quelques uns dans l’ouvrage de AHUJA et al [1]. Un de ceux-ci, que nousallons presenter ci-dessous est l’algorithme de plus courts chemins successifs.

Section 9.3. Resolution du probleme de flot a cout minimum 109

9.3.1 Algorithme de plus courts chemins successifs

Le principe de l’algorithme est le suivant. A chaque etape, on dispose d’unesolution f qui satisfait les conditions de non negativite et de capacites des arcs maispas necessairement les conditions de conservation de la matiere aux nœuds.

Definition 9.2 Un pseudoflotf satisfait les contraintes de capacites et de positivitedes flux. On definit l’exces au nœud i, soit e(i) comme suit

e(i) = s(i) +∑

k|(k,i)∈A

fki − d(i) −∑

j|((i,j)∈A

fij

ou s(i) note l’injection dans le reseau au nœud i, d(i), la demande satisfaite aunœud i et fij , le flux dans l’arc (i, j). Donc e(i) est la partie de l’offre au nœud iqui n’est pas encore portee plus loin.

Le principe de l’algorithme est a chaque etape de selectionner un nœud savec un exces d’offre et un nœud t avec une demande non satisfaite et d’envoyerdu flot de s a t le long d’un plus court chemin du reseau residuel (voir section 9.2pour la notion de reseau residuel).

On va illustrer l’algorithme sur l’exemple de la figure 9.2 ou la notation desarcs est la suivante :

(cπij, rij)

ou cπij denote le cout reduit de l’arc qui, pour rappel, se calcule comme suit :

cπij = cij − πi + πj

et rij note la capacite residuelle. Initialement, tous les flots sont mis a zero ainsique tous les potentiels aux nœuds :

fij = 0 ∀(i, j) ∈ A

πi = 0 ∀i ∈ N

Ainsi, on peut calculer facilement les exces de demande aux nœuds :

e(i) = s(i) − d(i)

Ce qui donne ici e(1) = 4, e(2) = 0, e(3) = 0 et e(4) = 0. On definit les deuxensembles E des nœuds avec exces d’offre et D avec exces de demande :

E = {i|e(i) > 0}D = {i|e(i) < 0}

Au depart, on a donc (voir figure 9.2) : E = {1} et D = {4}.

110 Chapitre 9. Resolution du probleme de transport general

41s1 = 4

d4 = 4

(2,4)

2

3

(3,3)

(1,5)(2,2)

(1,2)

(cπij, rij)=

e(1) = 4

π(1) = 0

e(2) = 0

π(2) = 0

e(3) = 0

π(3) = 0

e(4) = -4

π(4) = 0

Figure 9.2: Algorithme de plus courts chemins successifs.

Algorithme 9.1 Algorithme de plus courts chemins successifs. Tant que E = ∅,on selectionne k ∈ E et l ∈ D. On determine les plus courtes distances d(j) dunœud source k vers tous les nœuds du reseau residuel G(f) sur base des coutsreduits cπ

ij . Soit P le plus court chemin du nœud k au nœud l. On met a jour :

π(i) = π(i) − d(i), ∀i ∈ N ;

et on calcule le flux maximum que l’on peut faire passer le long du chemin par

δ = min{e(k),−e(l), rij∀(i, j) ∈ P}

On augmente le flot le long de P de δ. On met a jour le reseau residuel G(f), lesensembles E, D et les couts reduits.

Appliquons ceci a l’exemple. A l’iteration 1, on selectionne k = 1 et l = 4.Ensuite, on determine, par l’algorithme de Dijkstra, les plus courtes distances dunœud 1 au nœud i, soit d(i), en se basant sur les couts reduits. On obtient :

d = (0, 2, 2, 3)

et le plus court chemin P = 1− 3− 4. On met a jour les potentiels aux nœuds parla formule π = π − d. On obtient ainsi

π(1) = 0, π(2) = −2, π(3) = −2, π(4) = −3.

On calcule le flot maximum que l’on peut faire passer le long du chemin :

δ = min{4, 4, 2, 5} = 2

Section 9.3. Resolution du probleme de flot a cout minimum 111

On peut donc augmenter de 2 unites le flux le long des arcs du chemin

f13 = 2 et f34 = 2

On remet a jour le reseau residuel G(f) (voir figure 9.3) ainsi que les ensembles

41s1 = 4

d4 = 4

(0,4)

2

3

(2,3)

(0,3)(0,2)

(1,2)

(cπij, rij)=

e(1) = 2

π(1) = 0

e(2) = 0

π(2) = -2

e(3) = 0

π(3) = -2

e(4) = -2

π(4) = -3

(0,2)

Figure 9.3: Situation au debut de l’iteration 2.

E et D : E = {1} et D = {4}. On remet a jour les couts reduits :

cπ12 = 2 − 0 + (−2) = 0

cπ13 = 2 − 0 + (−2) = 0

cπ23 = 1 − (−2) + (−2) = 1

cπ24 = 3 − (−2) + (−3) = 2

cπ34 = 1 − (−2) + (−3) = 0

A la seconde iteration, on selectionne k = 1 et l = 4. Les plus courtesdistances au nœud k source basees sur les couts reduits et sur le reseau residuelsont

d = (0, 0, 1, 1)

tandis que le plus court chemin est P = 1−2−3−4. On met a jour les potentielsaux nœuds par la formule π = π − d :

π(1) = 0, π(2) = −2, π(3) = −3, π(4) = −4.

On calcule le maximum de flux que l’on peut faire passer le long du chemin

δ = min{2, 2, 4, 2, 3} = 2

112 Chapitre 9. Resolution du probleme de transport general

On peut donc augmenter de 2 unites le flux le long des arcs du chemin

f12 = 0 + 2 = 2

f13 = 2 + 0 = 2

f23 = 0 + 2 = 2

f24 = 0 + 0 = 0

f34 = 2 + 2 = 4

On remet a jour les ensembles E et D. On peut verifier que :

e(1) = e(2) = e(3) = e(4) = 0.

Comme E est vide, on a la solution optimale.

9.4 Application au probleme d’affectation

Illustrons ceci sur l’exemple suivant. On veut affecter 4 personnes a 4 postes detravail. Leurs competences sont telles que la premiere personne ne peut travaillerque sur les postes de travail 1 ou 2, la seconde sur les postes 2 ou 3, la troisiemesur les postes 1, 3 ou 4 et la quatrieme, sur les postes 3 ou 4. De plus la premierepersonne a une efficacite double si on la met au premier poste de travail plutotqu’au second. Ainsi de suite pour les autres. On determine ainsi l’efficacite dechaque personne a chaque poste ou elle est susceptible d’etre affectee.

On peut representer le probleme par un reseau de transport bipartite ou lessommets origine designent les personnes et les sommets destination, les postes.On trace des arcs entres les personnes et les postes uniquement dans le cas oul’affectation de la personne au poste est possible. Ceci est fait pour notre exemplea la figure 9.4.

3

2

1

3

1

2

4 4

Figure 9.4: Probleme d’affectation.

Section 9.4. Application au probleme d’affectation 113

Nous le completons le graphique en mettant les temps pour effectuer chacunedes taches par chacun des candidats ainsi qu’en faisant apparaıtre une entree uniqueet un puits unique. On obtient la figure 9.5.

3

2

1

7

5

6

4

0 9

0

0

0

0

5

10

8

12

0

0

0

015

11

3

1520 8

4 4

0

0

0

0

3

3

8

12

11

0

Figure 9.5: Probleme d’affectation : iteration 1

Initialement, on met a zero tous les flux ainsi que les fonctions potentielles :

π(i) = 0 ∀i et fij = 0 ∀(i, j)

On calcule l’exces aux nœuds ainsi que les ensembles E et D :

e(0) = 4 e(9) = −4 E = {0} D = {9}

Iteration 1 :On selectionne k = 0 et l =9 et on calcule les plus courtes distances a k :

(0, 0, 0, 0, 0, 3, 8, 12, 11, 3)

Le plus court chemin est P = (0, 3, 5, 9). On met a jour les π :

(0, 0, 0, 0, 0,−3,−8,−12,−11,−3)

On determine la maximum de flux qui peut passer sur le chemin

δ = min{4, 4, 1, 1, 1} = 1

On augmente d’une unite le flux le long de P :

f03 = f35 = f59 = 1.

114 Chapitre 9. Resolution du probleme de transport general

On met a jour les couts reduits :

c01 = 0 − 0 + 0 = 0 c37 = 15 − 0 + (−12) = 3c02 = 0 − 0 + 0 = 0 c38 = 11 − 0 + (−11) = 0c03 = 0 − 0 + 0 = 0 c47 = 15 − 0 + (−12) = 3c04 = 0 − 0 + 0 = 0 c48 = 20 − 0 + (−11) = 9c15 = 5 − 0 + (−3) = 2 c59 = 0 − (−3) + (−3) = 0c16 = 10 − 0 + (−8) = 2 c69 = 0 − (−8) + (−3) = 5c26 = 8 − 0 + (−8) = 0 c79 = 0 + 12 − 3 = 9c27 = 12 − 0 + (−12) = 0 c89 = 0 + 11 − 3 = 8c35 = 3 − 0 + (−3) = 0

On remet a jour le reseau residuel. Ceci est fait a la figure 9.6.

3

2

1

7

5

6

4

0 9

0

0

0

0

2

2

0

0

0

5

9

83

0

0

39 8

4 4

0

0

2

0

2

5

0

0

2

0

Figure 9.6: Probleme d’affectation : iteration 2

Iteration 2 :On selectionne k = 0 et l = 9 et on calcule les plus courtes distances a k :

(0, 0, 0, 2, 0, 2, 0, 0, 2, 5)

Le plus court chemin est P = (0, 2, 6, 9). On met a jour les π :

(0, 0, 0,−2, 0,−5,−8,−12,−13,−8)

On determine la maximum de flux qui peut passer sur le chemin

δ = min{3, 3, 1, 1, 1} = 1

On augmente d’une unite le flux le long de P : f02 = f26 = f69 = 1.

Section 9.4. Application au probleme d’affectation 115

On met a jour les couts reduits :

c01 = 0 − 0 + 0 = 0 c37 = 15 − (−2) + (−12) = 5c02 = 0 − 0 + 0 = 0 c38 = 11 − (−2) + (−13) = 0c03 = 0 − 0 + (−2) = −2 c47 = 15 − 0 + (−12) = 3c04 = 0 − 0 + 0 = 0 c48 = 20 − 0 + (−13) = 7c15 = 5 − 0 + (−5) = 0 c59 = 0 − (−5) + (−8) = −3c16 = 10 − 0 + (−8) = 2 c69 = 0 − (−8) + (−8) = 0c26 = 8 − 0 + (−8) = 0 c79 = 0 − (−12) − 8 = 4c27 = 12 − 0 + (−12) = 0 c89 = 0 − (−13) − 8 = 5c35 = 3 − (−2) + (−5) = 0

On remet a jour le reseau residuel. Ceci est fait a la figure 9.7.

3

2

1

7

5

6

4

0 9

0

0

2

0

0

2

0

0

3

0

4

5

5

0

0

37 8

4 4

0

2

0

0

0

5

2

2

0

0

Figure 9.7: Probleme d’affectation : iteration 3

Iteration 3 :On selectionne k = 0 et l =9 et on calcule les plus courtes distances a k :

(0, 0, 2, 0, 0, 0, 2, 2, 0, 5)

Le plus court chemin est P = (0, 1, 5, 3, 8, 9). On met a jour les π :

(0, 0,−2,−2, 0,−5,−10,−14,−13,−13)

On determine la maximum de flux qui peut passer sur le chemin

δ = min{2, 2, 1, 1, 1, 1, 1} = 1

On augmente d’une unite le flux le long de P :

f01 = f15 = f38 = f89 = 1

f35 = 0

116 Chapitre 9. Resolution du probleme de transport general

On met a jour les couts reduits :

c01 = 0 − 0 + 0 = 0 c37 = 15 − (−2) + (−14) = 3c02 = 0 − 0 + (−2) = −2 c38 = 11 − (−2) + (−13) = 0c03 = 0 − 0 + (−2) = −2 c47 = 15 − 0 + (−14) = 1c04 = 0 − 0 + 0 = 0 c48 = 20 − 0 + (−13) = 7c15 = 5 − 0 + (−5) = 0 c59 = 0 − (−5) + (−13) = −8c16 = 10 − 0 + (−10) = 0 c69 = 0 − (−10) + (−13) = −3c26 = 8 + 2 + (−10) = 0 c79 = 0 − (−14) − 13 = 1c27 = 12 + 2 + (−14) = 0 c89 = 0 − (−13) − 13 = 0c35 = 3 − (−2) + (−5) = 0

On remet a jour le reseau residuel. Ceci est fait a la figure 9.8.

3

2

1

7

5

6

4

0 9

0

2

2

0

0

0

0

0

8

3

1

03

0

0

17 8

4 4

0

2

0

0

2

2

2

1

2

0

Figure 9.8: Probleme d’affectation : iteration 4

Iteration 4 :On selectionne k = 0 et l =9 et on calcule les plus courtes distances a k :

(0, 2, 2, 2, 0, 2, 2, 1, 2, 2)

Le plus court chemin est P = (0, 4, 7, 9). On determine la maximum de flux quipeut passer sur le chemin δ = min{1, 1, 1, 1, 1, 1} = 1. On augmente d’une unitele flux le long de P :

f04 = f47 = f79 = 1

Comme E est vide, on a trouve la solution optimale qui consiste donc a affecterla premiere personne au premier poste, la deuxieme au deuxieme, la troisieme auquatrieme et la quatrieme au troisieme poste :

x∗11 = 1

x∗22 = 1

x∗34 = 1

x∗43 = 1

Section 9.5. Exercices 117

9.5 Exercices

9.1. Le probleme de la pharmacie centrale. La pharmacie centrale du Malidoit repondre a une demande d’un medicament rare dont elle detient certainsstocks d’ages divers. Les delais de commande et de livraison sont tels quela pharmacie centrale devra compter sur ses propres stocks pour les cinqprochains mois. Le tableau 9.1 fournit l’etat actuel des stocks.

Lot A B C D E F G H I J K LAge (mois) 2 1 4 3 2 4 5 2 1 4 5 3

Tableau 9.1: Stocks de medicaments

Le laboratoire qui fabrique ce medicament a etabli que son efficacite va de-croissant avec le nombre de mois ecoules depuis sa production (voir tableau9.2).

Age (mois) 0 1 2 3 4 5 6 7 8 9Efficacite (%) 100 99 97 94 88 83 81 78 76 75

Tableau 9.2: Efficacite des medicaments

La pharmacie prevoit avoir besoin de 12 lots au cours des 5 prochains mois,selon la distribution indiquee au tableau 9.3. La pharmacie, qui cherche

Mois 1 2 3 4 5Besoins 3 2 4 1 2

Tableau 9.3: Besoins de medicaments

a maximiser l’efficacite totale des lots, s’interroge sur la sequence selonlaquelle elle devra ecouler ses lots.

(a) Determinez une affectation qui corresponde a la regle du premier entre= premier sorti et calculer son efficacite globale.

(b) Determinez une affectation qui corresponde a la regle du dernier entre= premier sorti et calculer son efficacite globale.

(c) Formuler le probleme de la determination de l’affectation d’efficaciteglobale maximum comme un probleme affectation (ne pas le resoudre).

9.2. Entreprise de construction. Une entreprise de construction doit affecter 4ouvriers a 4 taches. Le tableau 9.4 indique l’efficacite de la personne si elle

118 Chapitre 9. Resolution du probleme de transport general

est affectee a la tache. Une barre indique que la personne n’est pas qualifieepour la tache. Utilisez l’algorithme de plus courts chemins successifs pouridentifier une affectation qui maximise l’efficacite generale.

Tache 1 Tache 2 Tache 3 Tache 4Ouvrier 1 45 - - 30Ouvrier 2 50 55 15 -Ouvrier 3 - 60 25 75Ouvrier 4 45 - - 35

Tableau 9.4: Entreprise de construction

Chapitre 10

La programmation dynamique.

La programmation dynamique a pour but de traiter les modeles ou une sequenceoptimale de decisions doit etre prise. Elle est largement utilisee en planification dela production pour determiner les lancements de production en cas de couts fixesde lancement de production.

L’idee generale des procedures de resolution en programmation dynamiqueest la suivante. On part d’un sous probleme, celui de derniere etape, dont laresolution est triviale. Ensuite, et en procedant a rebours, on etend progressivementle probleme en incluant les etapes precedentes et en calculant la politique optimalea chaque etape en se basant sur la politique optimale de l’etape suivante.

10.1 Le probleme du voyageur

Un exemple purement fictif, tire de Hillier et Lieberman [10], va nous permettred’introduire la terminologie employee en programmation dynamique. Il s’agit duprobleme du voyageur devant traverser l’ouest americain il y a plus d’un siecle.Son point de depart et sa destination sont connus. Il effectue son voyage en quatreetapes. A chaque etape, il a le choix de se diriger vers plusieurs etats. A lafigure 10.1, on a represente chaque etat par un cercle. Son etat de depart est l’etat1 et son etat d’arrivee est l’etat 10.

Le voyageur souscrit a chaque etape une police d’assurance dont le cout refletele degre d’insecurite du voyage. Ceux-ci sont indiques au dessus des arcs a lafigure 10.1. Il va donc determiner son itineraire de maniere a choisir la route laplus sure en minimisant la somme des polices d’assurance pour le passage d’etaten etat.

Notez d’abord que l’approche tres simple qui consiste a choisir a chaque etapela police la moins chere ne conduit pas a une solution globalement la moins chere.En effet, en suivant cette strategie, on choisirait le chemin 1 → 2 → 6 → 9 → 10

119

120 Chapitre 10. La programmation dynamique.

1

2

3

4

5

6

7

8

9

10

1

2

4

3

7

64

4

4

3

2

5

1

4

6

3

3 3

3

4

Figure 10.1: Probleme du voyageur

avec un cout total d’assurance de 13. Cependant en sacrifiant un peu a la premiereetape, on peut gagner aux etapes ulterieures. En effet, par exemple la route 1 →4 → 6 → 9 → 10 permet un cout total de 11.

Une autre methode serait d’evaluer toutes les routes possibles. Cependant surce petit exemple, elles sont deja au nombre de 3×3×2 = 18 et lorsque le nombred’etapes et/ou le nombre d’etats croıt, cela devient vite un travail prohibitif.

C’est ici qu’intervient la programmation dynamique qui permet de calculerla solution optimale sans faire de l’enumeration explicite. La programmation dyna-mique commence avec une petite portion du probleme original, trouve la solutionoptimale pour cette portion du probleme. Ensuite on elargit progressivement leprobleme, en determinant la nouvelle solution optimale a partir de la precedente.Pour le probleme du voyageur, on considere le probleme de fin de voyage, lorsqu’iln’y a plus qu’une etape a faire. Pour ce probleme la solution optimale est evidente :le voyageur doit aller directement a sa destination, l’etat 10. A l’iteration suivante,on elargit d’une unite le nombre d’etapes a effectuer. On peut ensuite deduire lastrategie optimale pour la troisieme etape en fonction de la strategie optimale pourla derniere etape.

En programmation dynamique, deux types de variables sont associees a chaqueetape. La variable st indique l’etat du systeme au debut de l’etape t. Cettevariable doit contenir toute l’information resultant des choix effectues aux etapesprecedentes. La variable xt indique la decision strategique prise a l’etape t. Ainsi,dans notre exemple, notons st l’etat de depart de l’etape t tandis que xt note ladestination de l’etape t.

On note par ft(st, xt) le cout total de la meilleure strategie pour les etapesrestantes, si l’on se trouve au debut de l’etape t dans l’etat du systeme st et que

Section 10.1. Le probleme du voyageur 121

l’on prend xt comme decision strategique a l’etape t. Notons par x∗t la valeur de

xt qui minimise ft(st, xt) et f ∗t (st) la valeur minimum correspondante. On a donc

que :f ∗

t (st) = minxt

ft(st, xt) = ft(st, x∗t )

Ainsi, dans notre exemple, ft(st, xt) note le cout total de la meilleure strategiepour les etapes restantes si le voyageur est dans l’etat st a l’etape t et selectionnecomme etat suivant l’etat xt.

La programmation dynamique va determiner successivement f ∗4 (s4), f ∗

3 (s3),f ∗

2 (s2), f ∗1 (s1) pour chaque etat possible st a l’etape t et utiliser par exemple f ∗

2 (s2)pour calculer f ∗

1 (s1).

Nous allons maintenant appliquer ceci a l’exemple du voyageur. Pour t = 4,c’est-a-dire lorsque le voyageur n’a plus qu’une etape a effectuer pour rejoindre sadestination, sa route est entierement determinee par son etat courant s4 (ici s4 = 8ou 9) et sa destination finale x4 = 10. Le tableau 10.1 reprend les couts minimauxde la derniere etape ainsi que la decision optimale en fonction de l’etat de depart.

s4 x∗4 f ∗

4 (s4)

8 10 3

9 10 4

Tableau 10.1: Couts minimaux de la derniere etape

Lorsque le voyageur a encore deux etapes a effectuer (t = 3), la solutionrequiere un peu plus de calculs. Si, par exemple, le voyageur est dans l’etat 5, ilpeut aller a l’etape 3 vers l’etat 8 ou 9 a un cout respectif de c5,8 = 1 ou c5,9 = 4. S’ilchoisit l’etat 8, le cout additionnel qu’il va encourir pour rejoindre sa destinationa partir de l’etat 8 est donne dans la table 10.1, il s’agit de f ∗

4 (8) = 3, de sorteque son cout total est de 1 + 3 = 4. Semblablement, s’il choisit l’etat 9, il devraadditionner 4 + 4 = 8. Et donc l’etat qu’il va choisir comme destination est l’etat8, donc x∗

3 = 8, qui donne un cout minimum pour le chemin qui reste a parcourirde f ∗

3 (5) = 4. On procede de meme pour les autres etats possibles a l’etape 3,c’est-a-dire les etats s3 = 6 et s3 = 7 et on obtient les valeurs donnees dans latable 10.2.

La solution pour le probleme ou il reste trois etapes (t = 2) est obtenue demaniere similaire. Elle est illustree a la table 10.3. Les etats destination sont cettefois au nombre de trois : il s’agit de x2 = 5, x2 = 6 ou x2 = 7 tandis que les etatsde depart possibles sont s2 = 2, s2 = 3 ou s2 = 4. Pour les etats de depart 2 ou 4,la destination optimale peut etre au choix 5 ou 6 puisque le cout total est le meme.

122 Chapitre 10. La programmation dynamique.

s3 x3 = 8 x3 = 9 x∗3 f ∗

3 (s3)

5 1 + 3 = 4 4 + 4 = 8 8 4

6 6 + 3 = 9 3 + 4 = 7 9 7

7 3 + 3 = 6 3 + 4 = 7 8 6

Tableau 10.2: Couts minimaux de la troisieme etape

s2 x2 = 5 x2 = 6 x2 = 7 x∗2 f ∗

2 (s2)

2 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 5 ou 6 11

3 3 + 4 = 7 2 + 7 = 9 4 + 6 = 10 5 7

4 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 5 ou 6 8

Tableau 10.3: Cout minimaux de la deuxieme etape

Enfin, pour terminer, le probleme de premiere etape (t = 1), le cout minimumde la police optimale est a nouveau donne en fonction de l’etat destination del’etape comme la somme du cout de premiere etape plus le cout minimum desetapes ulterieures. On obtient les resultats de la table 10.4.

s1 x1 = 2 x1 = 3 x1 = 4 x∗1 f ∗

1 (s1)

1 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 3 ou 4 11

Tableau 10.4: Cout minimaux de la premiere etape

On peut maintenant identifier une politique optimale. Pour t = 1, le voyageurdoit donc se diriger initialement vers l’etat 3 ou 4. Supposons qu’il choisissex∗

1 = 3. Pour t = 2, la strategie optimale pour s2 = 3 est x∗2 = 5 (voir tableau

10.3), ce qui dans l’etape t = 3 conduit a l’etat s3 = 5. La strategie optimale pours3 = 5 consiste a choisir x∗

3 = 8 (voir tableau 10.2). On se retrouve en s4 = 8 eton choisit x∗

4 = 10 a l’etape 4 (voir tableau 10.1). Une des routes optimales estdonc 1 → 3 → 5 → 8 → 10 donnant un cout total minimum de f ∗

1 (1) = 11. Onpeut resumer la solution dans le tableau suivant :

t 1 2 3 4

st 1 3 5 8

x∗t 3 5 8 10

Section 10.2. Resolution des problemes dynamiques 123

10.2 Resolution des problemes dynamiques

Nous allons ici resumer la notation utilisee en programmation dynamique ainsique la methode de resolution.

Rappelons qu’un probleme dynamique est divise en etapes indicees par t. Achaque etape, l’etat initial est caracterise par st et on prend une decision strategiquenotee xt.

Les problemes dynamiques peuvent etre representes comme a la figure 10.2.A l’etape t, on est dans l’etat st. En decidant la politique xt, on amene le systemea l’etape t + 1 a etre dans l’etat st+1.

Etat : st+1st

Etape

t

Etape

t + 1

Decision strategique

xt

f(st, xt) f∗t (st+1)

Figure 10.2: Resolution des problemes dynamiques

Du point de vue de l’objectif, la politique optimale a deja ete calculee en t+1,et donne une valeur optimale pour les etapes ulterieures de f ∗

t+1(st+1). La decisionxt donne une certaine contribution a l’objectif qui vient s’ajouter a la precedentepour donner ft(st, xt) au debut de l’etape t.

ft(st, xt) = cst,xt + f ∗t+1(xt)

Par exemple, dans le cas du voyageur, la contribution de l’etape cst,xt est le coutde l’assurance pour aller de st a xt. En optimisant par rapport a xt, on obtient

f ∗t (st) = min

xt{ft(st, xt)}

On note par x∗t la politique optimale pour l’etape courante de sorte que l’on a que :

f ∗t (st) = ft(st, x

∗t )

On procede de meme pour tous les etats possibles st de l’etape t et l’ondetermine ainsi tous les valeurs optimales f ∗

t (st). La procedure peut alors etrecontinuee a rebours.

124 Chapitre 10. La programmation dynamique.

10.3 Un probleme d’affectation de ressources rares

Nous illustrons le fait que le champs d’application de la methode de resolutionest tres large sur un deuxieme exemple egalement tire de Hillier et Lieberman[10] : il s’agit du probleme de l’organisation mondiale de la sante. On supposeque l’OMS dispose de 5 equipes medicales a affecter a 3 pays pour mener abien une campagne de vaccination. L’OMS doit determiner combien d’equipesenvoyer dans chacun des trois pays de maniere a maximiser l’efficacite generalede l’affectation. La mesure de l’efficacite est donnee en terme d’annees-hommede vie supplementaire. Ces donnees sont reprises au tableau 10.5. On suppose quechaque pays doit beneficier d’au moins une equipe.

Nombre d’equipes Pays 1 Pays 2 Pays 31 45 20 502 70 45 703 90 75 80

Tableau 10.5: Milliers d’annees-homme supplementaires

Bien qu’il n’y ait pas de succession temporelle, on peut imaginer que les troisetapes d’un processus dynamique consistent en l’affectation successive aux troispays puisque lorsqu’une equipe est affectee a un pays, elle n’est plus disponiblepour les autres pays. On a donc identifie les etapes.

Comment identifier les etats ? Autrement dit, quelle est l’information ne-cessaire a une etape pour pouvoir determiner la politique optimale ? Il s’agitsimplement du nombre d’equipes medicales qui restent disponibles. Notons st lenombre d’equipes encore disponibles au debut de l’etape t.

Notons pt(xt) la mesure de l’efficacite de l’allocation de xt equipes medicalesau pays t. Si, comme precedemment, on note par ft(st, xt) la contribution al’objectif des etapes ulterieures a t et de l’etape t si l’on est dans l’etat st et quel’on prend la decision xt, on peut ecrire :

ft(st, xt) = pt(xt) + f ∗t+1(st+1)

avec pt(xt) le benefice pour le pays t de recevoir xt equipes et st+1 le nombred’equipes encore disponibles au debut de l’etape t + 1. Celui-ci est lie a st par larelation de recurrence suivante :

st+1 = st − xt.

La relation de recurrence liant f ∗n et f ∗

n+1 s’ecrit quant a elle comme suit :

f ∗t (st) = max

xtft(st, xt) = max

xt

{pt(xt) + f ∗

t+1(st − xt)}

.

Section 10.3. Un probleme d’affectation de ressources rares 125

A l’etape t = 3, les etats possibles vont de 1 (il faut au moins une equipe pourle pays 3) jusqu’a 3 (on a au moins affecte une equipe au pays 1 et une equipeau pays 2). A la derniere etape, on a interet a affecter toutes les equipes encoredisponibles (voir tableau 10.6).

s3 x∗3 f ∗

3 (s3)

1 1 50

2 2 70

3 3 80

Tableau 10.6: Calculs de l’etape 3

A l’etape 2, les etats possibles vont de 2 (il faut au moins une equipe pour lepays 2 et une equipe pour le pays 3) a 4 (on a au moins attribue une equipe au pays1). A la deuxieme etape, au gain de l’etape, il faut ajouter le gain resultant pourl’etape 3 avec s3 = s2 − x2. Le detail des calculs est donne au tableau 10.7.

s2 x2 = 1 x2 = 2 x2 = 3 x∗2 f ∗

2 (s2)

2 20 + 50 = 70 − − 1 70

3 20 + 70 = 90 45 + 50 = 95 − 2 95

4 20 + 80 = 100 45 + 70 = 115 = 75 + 50 = 125 3 125

Tableau 10.7: Calculs de l’etape 2

De meme a l’etape 1, au gain de l’etape, il faut ajouter ceux des etapes suivantesavec s2 = s1 − x1. Le detail des calculs est donne au tableau 10.8.

s1 x1 = 1 x1 = 2 x1 = 3 x∗1 f ∗

1 (s1)

5 45 + 125 = 170 70 + 95 = 165 90 + 70 = 160 1 170

Tableau 10.8: Calculs de l’etape 1

La solution optimale est donc x∗1 = 1 qui donne s2 = 5 − 1 = 4 pour la

deuxieme etape ou encore x∗2 = 3, ce qui donne s3 = 4 − 3 = 1 pour l’etape 3

de sorte que x∗3 = 1, ce qui donne un gain de 170 000 hommes-annees. On peut

resumer la solution dans le tableau suivant :

t 1 2 3

st 5 4 1

x∗t 1 3 1

126 Chapitre 10. La programmation dynamique.

10.4 Application a la planification de la production.

Nous allons maintenant voir comment la programmation dynamique permet deresoudre des problemes de planification de la production en presence de couts deproduction non convexes. Illustrons ceci sur un exemple.

La demande previsionnelle de fin de mois d’un composant est donnee au ta-bleau 10.9. La fabrication de ce composant necessite un certain nombre de reglagesindependants du nombre d’unites fabriquees. Le cout fixe de lancement de la pro-duction est de 150. Le cout direct depend de la main d’œuvre disponible. Le coutest de 200 en heures normales, de 250 en heures supplementaires. Le tableau 10.9donne la production maximale en heures normales et heures supplementaires. On

Periode t 1 2 3 4 5

Capacite de production a 200 2 2 3 3 3

Capacite de production a 250 3 3 3 3 3

Demande previsionnelle 2 1 4 2 4

Tableau 10.9: Demande previsionnelle et capacite de production

une capacite de stockage limitee a 2 unites. Le cout de stockage est de 10 parunite stockee par mois. Le delai de fabrication est negligeable. On s’interdit touterupture de stock. Autrement dit, il faut satisfaire la demande de fin de mois.

Nous allons tout d’abord formuler le probleme en un probleme de pro-grammation dynamique. Pour cela, definissons la variable d’etat de la periodet suivante :

st = stock au debut de la periode t.

Definissons aussi la variable de decision de la periode t suivante :

xt = production a la periode t.

On definit la fonctionft(st, xt)

comme etant le cout de la meilleure planification pour les periodes restantes si onest dans l’etat st au debut de la periode t et que l’on decide de produire xt a laperiode t. Ce cout est la somme du cout de production de l’etape t, d’un cout depossession du stock pendant le mois t ainsi que du cout des etapes ulterieures :

ft(st, xt) = cpt(xt) + csst + f ∗t+1(st + xt − dt)

Section 10.4. Application a la planification de la production. 127

ou dt note la demande previsionnelle qui est donnee au tableau 10.9. La fonctioncpt(xt) denote le cout de production a l’etape t. Ce dernier est la somme d’un coutfixe de lancement de 150, a payer pour autant qu’il y ait production, et d’un coutdirect de main d’œuvre qui est de 200 par unite produite en heures normales, de250 par unite produite en heures supplementaires. Remarquez qu’en presence decout de lancement le cout de production n’est pas convexe. Ceci peut etre verifiea la figure 10.3 qui illustre la fonction de cout pour t = 5 :

cp5(x5) =

0 si x5 = 0;

150 + 200x5 si x5 = 1, 2 ou 3;

150 + 600 + 250(x5 − 3) si x5 = 4, 5 ou 6.

cp5(x5)

x51 2 3 4 5 6

1500

1250

1000

750

550

350

350

200

250

Figure 10.3: Cout non convexe.

La capacite de stockage est limitee a 2 unites. Ce qui limitera a trois les etatsdu monde possibles a chaque etape.

Nous allons maintenant resoudre le probleme par la programmation dyna-mique. A l’etape 5, on a d5 = 4. Ce qui explique qu’il faut au moins produire4 unites si s5 = 0 mais pas plus de 6 sinon le stock final sera superieur a deux

128 Chapitre 10. La programmation dynamique.

unites. De plus la capacite de production est limitee a six unites. On obtient lescouts suivants des differentes strategies :

s5 x5 = 2 x5 = 3 x5 = 4 x5 = 5 x5 = 6 x∗5 f ∗

5 (s5)

0 − − 1.000 1.250 1.500 4 1.000

1 − 760 1.010 1.260 − 3 760

2 570 770 1.020 − − 2 570

Par exemple le cout de 1.000 si s5 = 0 et x5 = 4 resulte du seul cout de productionqui se calcule comme suit :

150 + 3 × 200 + 250 = 1000.

Le cout de 760 si s5 = 1 et x5 = 3 resulte de la somme du cout de stockage d’uneunite pendant un mois et du cout de production des trois unites :

1 × 10 + 150 + 3 × 200 = 760.

A l’etape 4, on a d4 = 2. On ajoute au cout de production de l’etape, le coutdes etapes ulterieures. Ainsi, dans le cas ou s4 = 0 et x4 = 2, le cout corresponda l’application de la formule :

f4(s4, x4) = cp4(x4) + f ∗5 (s4 + x4 − d4)

= (150 + 400) + 1.000

= 1.550

On obtient le tableau de couts suivant :

s4 x4 = 0 x4 = 1 x4 = 2 x4 = 3 x4 = 4 x∗4 f ∗

4 (s4)

0 − − 1.550 1.510 1.570 3 1.510

1 − 1.360 1.320 1.330 − 2 1.320

2 1.020 1.130 1.140 − − 0 1.020

A l’etape 3, on a d3 = 4. On determine semblablement le tableau de coutssuivant :

s3 x3 = 2 x3 = 3 x3 = 4 x3 = 5 x3 = 6 x∗3 f ∗

3 (s3)

0 − − 2.510 2.570 2.520 4 2.510

1 − 2.270 2.330 2.280 − 3 2.270

2 2.080 2.090 2.040 − − 4 2.040

Section 10.4. Application a la planification de la production. 129

A l’etape 2, on a d2 = 1. On a une capacite de production a 200 limitee a deuxunites. On obtient le tableau de couts suivant :

s2 x2 = 0 x2 = 1 x2 = 2 x2 = 3 x∗2 f ∗

2 (s2)

0 − 2.860 2.820 2.840 2 2.820

1 2.520 2.630 2.600 − 0 2.520

2 2.290 2.410 − − 0 2.290

A l’etape 1, la demande est de 2 et on a le tableau de couts suivant :

s1 x1 = 2 x1 = 3 x1 = 4 x∗1 f ∗

1 (s1)

0 3.370 3.320 3.340 3 3.320

On peut ensuite determiner la politique optimale en partant de s1 = 0. Enpremiere etape, la strategie optimale est de produire 3. La demande etant de 2, onse retrouve avec un stock initial s2 = 1. La strategie optimale pour la deuxiemeperiode est dans ce cas de ne produire rien du tout. On se retrouve avec un stockinitial s3 = 0. La strategie optimale est de produire x3 = 4, c’est-a-dire la demandede la periode. On se retrouve avec un stock initial s4 = 0. La strategie optimaleest dans ce cas de produire x4 = 3, soit une unite de plus que la demande. On seretrouve avec un stock initial s5 = 1 et on produit x5 = 3.

La planification optimale est donc la suivante :

t 1 2 3 4 5

st 0 1 0 0 1

x∗t 3 0 4 3 3

dt 2 1 4 2 4

Remarquez qu’en periode 2, on a prefere ne pas produire la seule unite de-mandee car une unite en premiere etape meme en heures supplementaires et avecun cout de stockage revient mois cher (260) qu’une seule unite en heure normalea la periode 2 (350). Remarquez aussi qu’en periode 4, on produit une unite deplus que la demande pour eviter de produire a 250 en periode 5 la quatrieme unitedemandee cette periode. Il y a, en effet, une unite disponible a 200 (+ 10 de coutde stockage) au mois precedent.

130 Chapitre 10. La programmation dynamique.

10.5 Exercices

10.1. Ventes de livres. Un editeur de livres educatifs doit decider du nombre devendeurs qu’il envoie dans chacune des regions du pays pour maximiser lenombre de ventes. Le tableau qui suit donne l’augmentation du nombre deventes dans chaque region en fonction du nombre de vendeurs envoyes.

Nombre de vendeurs Region 1 Region 2 Region 31 4 3 52 6 6 73 9 8 124 11 10 12

Il y a 6 vendeurs mais il est decide d’en envoyer au mois un dans chaqueregion. Formuler et resoudre par la programmation dynamique.

10.2. Plan de production hebdomadaire optimal. Une societe de constructionautomobile doit planifier la production du moteur M200. Au debut de ladouzieme semaine, les commandes a honorer pour les periodes 13 a 16, sontles suivantes :

Periode 13 14 15 16Besoins totaux 4 5 2 3

La fabrication du moteur M 200 demande une semaine et le cout de lancementdans l’atelier moteurs est estime a 500 F. Le cout variable unitaire est de 300F pour les trois premieres unites produites au cours d’une semaine et de400 F pour les unites suivantes. La capacite de stockage est limitee a deuxmoteurs et le cout unitaire hebdomadaire de stockage est de 50 F.

(a) Formuler le probleme de planification comme un probleme dynamique.

(b) Sachant qu’au debut de semaine 13, il ne reste aucun M200 en stock,determiner le plan de production optimal du moteur M200 pour lessemaines 12 a 15.

(c) Donner le plan optimal de production et de stockage.

Chapitre 11

Les modeles non lineaires

11.1 Introduction

On parle de modele d’optimisation non lineaire lorsque l’on doit maximiser ouminimiser une fonction sous contraintes et que la fonction objectif, ou au moinsune contrainte est non lineaire. Dans cette partie du cours, nous allons donc nousattacher a la resolution du probleme suivant :

max f(x)

s.c.q.

gi(x) ≤ 0, i = 1, . . .m

hk(x) = 0, k = 1, . . .p

ou f(x), gi(x), k = 1, . . .m, et hk(x), i = 1, . . .p sont des fonctions continumentdifferenciables definies sur R

n a valeurs dans R. Il s’agit donc de la generalisationau cas non lineaire du probleme classique de la programmation lineaire :

max cx

s.c.q.

{Ax ≤ b

x ≥ 0

Comme exemple de fonction objectif non lineaire, on peut citer le cas d’unrendement croissant d’echelle, c’est-a-dire une contribution unitaire au profits’accroissant avec la quantite produite. Par exemple, si la marge unitaire est de laforme m1(x1) = 550 + 2x1, cela donnera un terme non lineaire dans l’objectif :

max z = m1(x1)x1 = 550x1 + 2x21.

Comme exemple de contrainte non lineaire, on peut citer la relation entre le flot degaz entre les nœuds i et j, note fij , et les pressions en ces points, pi et pj :

f 2ij = C2

ij

(p2

i − p2j

)

131

132 Chapitre 11. Les modeles non lineaires

11.2 Difficulte de resolution des problemes non lineaires

Si certains problemes particuliers d’optimisation non lineaire peuvent se ramener ala resolution d’une suite de problemes lineaires (comme les problemes separablesque nous traiteront a la section 12.2), en general, il faudra prendre en compteexplicitement le caractere non lineaire des problemes pour les resoudre.

Beaucoup d’algorithmes de programmation non lineaire exploitent directementles conditions d’optimalite, c’est-a-dire les conditions verifiees a la solution opti-male du probleme. Nous allons donc d’abord nous attacher a etablir ces conditions.Ces conditions sont les extensions a R

n des conditions bien connues d’annulationde la derivee premiere pour une fonction d’une variable dans R.

Avant de passer a l’enonce de ces conditions, soulignons quelques differencesfondamentales avec la programmation lineaire. En programmation lineaire, lasolution optimale est toujours obtenue sur la frontiere du domaine realisable et,meme si toute une arete du polygone peut etre optimale, on peut toujours choisirun sommet sur celle-ci. Autrement dit, la solution optimale est toujours en unsommet de la region realisable (cfr figure 11.1).

x1

x2

P∗

cTx

Figure 11.1: Probleme lineaire.

Des que l’objectif ou les contraintes deviennent non lineaires, cette proprieten’est plus verifiee en general. Pire encore, on peut avoir un optimum localdifferent de l’optimum global. Ce probleme ne se produit cependant pas pourles problemes convexes. Nous verrons a la section 11.4 la notion de problemesconvexes. Nous verrons ensuite a la section 11.5 les tres importantes conditionsnecessaires d’optimalite : les conditions de Kuhn et Tucker. Nous verrons auchapitre suivant les algorithmes de resolution.

Section 11.3. Difference avec la programmation lineaire 133

11.3 Difference avec la programmation lineaire

Les modeles non lineaires sont beaucoup plus difficiles a resoudre en general queles modeles lineaires. Nous allons souligner par quelques exemples les differencesavec la programmation lineaire.

Tout d’abord, contrairement a la programmation lineaire ou la solution optimaleest toujours situee en un sommet de la region realisable, on peut avoir une solutionoptimale non extreme. Ceci est illustre par l’exemple suivant :

max z = 3 x1 + 5 x2

s.c.q.

x1 ≤ 4

9x21 + 5x2

2 ≤ 216

x1 , x2 ≥ 0

Pour pouvoir en donner une representation graphique, remarquons que

x21

(4, 9)2+

x22

(6, 5)2≤ 1

est l’equation d’une surface bordee par une ellipse centree en l’origine. On peutvoir a la figure 11.2 que la seule solution optimale n’est pas situe en un pointextreme de la region realisable.

4

2

2 4

3x1 + 5x2 = 36

x1 = 4

x1

x2

(2,6)6

Figure 11.2: Solution non extreme

Mais la solution ne doit meme pas etre situee sur la frontiere de la region. Ainsi,on peut avoir une solution optimale interieure. Ceci est illustre par l’exemple

134 Chapitre 11. Les modeles non lineaires

suivant :min z = (x1 − 3)2 + (x2 − 3)2

s.c.q.

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

x1 , x2 ≥ 0

dont la representation graphique est donnee a la figure 11.3 ou l’on peut voir que lasolution optimale est strictement interieure. En effet, les courbes d’isovaleurs dela fonction objectif forment des cercles concentriques et on a interet a se situer aucentre de ces cercles, c’est-a-dire au point (3,3), strictement interieur a la region.

8

6

4

2

0 2 4 6 x1

x2

(3,3)z = 0

z = 1

z = 4z = 9

z = 16

Figure 11.3: Solution interieure

Mais la principale difficulte de la programmation non lineaire est que l’on peutavoir des optimaux locaux qui ne sont pas globaux. Illustrons ceci sur l’exemplesuivant :

max z = 3x1 + 5x2

s.c.q.

x1 ≤ 4

8x1 − x21 + 14x2 − x2

2 ≤ 49

x1 , x2 ≥ 0

Pour pouvoir tracer sa representation graphique, remarquons que

(x1 − 4)2 + (x2 − 7)2 ≥ 16

Section 11.3. Difference avec la programmation lineaire 135

correspond au plan moins un cercle de rayon 4 centre en (4,7). La representationgraphique est donnee a la figure 11.4 ou l’on peut voir que (4,3) minimum localnon global !

4

2

2 4 x1

x2

6

(0,7)

(4,3)

z = 3x1 + 5x2 = 35

z = 3x1 + 5x2 = 27

Figure 11.4: Minimum local

C’est la une des plus grandes difficultes des problemes non convexes : onpeut avoir des optimaux locaux qui ne sont pas globaux. Remarquez que leprobleme peut egalement se produire si la fonction objectif que l’on minimise estnon convexe. Prenons l’exemple illustre a la figure 11.5 de la minimisation de lafonction concave y = −x2 sur l’intervalle [−1, 2]. Au point x = −1, on a unminimum qui n’est pas global.

2

-4

x

y

-1

-1

Figure 11.5: Minimum local non global

La determination de tous les optimaux locaux est un probleme tres delicat engeneral. En effet, lorsqu’un optimum local est atteint, dans quelle direction faut-ilcontinuer la recherche ? Cependant, il existe une classe de problemes pour lesquelsce probleme ne se produit pas dans le sens que tous les optimums locaux sontdes optimum globaux. Il s’agit des problemes convexes (voir section suivante).Remarquez que les logiciels commerciaux fournissent toujours un minimum local.

136 Chapitre 11. Les modeles non lineaires

11.4 Les problemes convexes

Definition 11.1 L’ensemble S ⊂ Rn est convexe, si et seulement si quels que

soient les deux points P et Q pris dans l’ensemble S, tout le segment [P, Q] estcontenu dans l’ensemble S.

Ce cas est illustre a la figure 11.6. Ces ensembles n’ont pas de partie rentrante a

P

Q P

Q

Figure 11.6: Ensembles convexes.

la difference des ensembles non convexes illustres a la figure 11.7.

PQ

P

Q

Figure 11.7: Ensembles non convexes.

Definition 11.2 Une fonction f est convexe si l’ensemble des points situe au dessusde son graphe, encore appele epigraphe :

S = {(x, y) ∈ Rn × R|y ≥ f(x)} .

est un ensemble convexe.

Ceci est illustre a la figure 11.8 pour l’exemple de la fonction x2 ou l’on voit quel’epigraphe est bien un ensemble convexe. La definition de fonction convexe seramene donc a celle d’ensemble convexe. Remarquez egalement que la definition

Section 11.4. Les problemes convexes 137

x

y

f(x)

Figure 11.8: Exemple de fonction convexe

classique pour les fonctions de R dans R, a savoir que la corde est toujours situeeau dessus du graphe se deduit directement du fait que l’epigraphe constitue unensemble convexe.

Definition 11.3 Une fonction f est concave si la fonction −f est convexe.

Un exemple de fonction concave est illustree a la figure 11.9.

x

y

f(x)

Figure 11.9: Exemple de fonction concave

Maintenant que nous avons defini les notions d’ensemble convexe et de fonctionconvexe, nous pouvons definir la notion de probleme convexe :

Definition 11.4 Un programme mathematique est dit convexe s’il s’agit de laminimisation d’une fonction convexe sur une region realisable convexe, soit dela maximisation d’une fonction concave sur une region realisable convexe.

Comme exemple de problemes convexes, on peut donc citer les problemesavec deseconomie d’echelle puisqu’il s’agit de la maximisation d’une fonctionconcave. Et comme exemple de problemes non convexes, on peut citer lesproblemes avec economie d’echelle puisqu’il s’agit de problemes de maximisationd’une fonction convexe.

138 Chapitre 11. Les modeles non lineaires

11.5 Conditions de Kuhn et Tucker

Nous considerons le probleme de minimisation sous contraintes suivant :

min f(x)

s.c.q.

{hi(x) = 0, i = 1, 2, . . .mgk(x) ≤ 0, k = 1, 2, . . .p

(11.1)

ou f(x), hi(x), i = 1, 2, . . .m et gk(x), k = 1, 2, . . .p sont des fonctions de Rn

dans R.

Une notion importante en programmation non lineaire est celle de contraintesactives :

Definition 11.5 Une inegalite gk(x) ≤ 0 est active en x si gk(x) = 0.

Il decoule immediatement de cette definition que hi(x) = 0 sont actives pour touti. Par exemple, a la figure 11.10, seule g2 est active en x∗. Le concept de con-

g1(x) = 0

g2(x) = 0

g3(x) = 0

x∗

regionrealisable

Figure 11.10: Concept de contraintes actives

trainte active est important car, tout comme en programmation lineaire, seules lescontraintes actives a l’optimum importent pour le probleme. On pourrait resoudrele probleme sans les autres et obtenir la meme solution : ce sont uniquement lescontraintes actives qui determinent la solution optimale.

Pour ecrire les conditions d’optimalite, on a besoin qu’une condition de regu-larite soit satisfaite.

Section 11.5. Conditions de Kuhn et Tucker 139

Definition 11.6 Definition de point regulier des contraintes. Soit x∗ satisfaisantles contraintes :

h(x∗) = 0, g(x∗) ≤ 0 (11.2)

Alors x∗ est dit regulier pour les contraintes (11.2) si les gradients des contraintesactives sont lineairement independants.

Cette definition necessite quelques rappels mathematiques concernant la notionde gradient et la notion d’independance de vecteurs.

Definition 11.7 Notion de gradient. Soit f une fonction a valeurs reelles definiesur R

n continument differenciable en x. C’est-a-dire une fonction continue dontles derivees partielles premieres sont egalement continues. On definit le gradientcomme etant le vecteur ligne constitue des derivees partielles :

∇f(x) =

[∂f(x)

∂x1

,∂f(x)

∂x2

, . . .∂f(x)

∂xn

].

La derivee partielle par rapport a la variable xj , notee∂f(x)

∂xj

, est obtenue en

derivant f en considerant que les autres variables que xj sont des constantes.

Illustrons cette notion par un exemple. Considerons la fonction suivante :

f(x1, x2) = 2x21 + 2x1x2 + x2

2 − 10x1 − 10x2

Les derivees partielles par rapport a chacune des variables se calculent en consi-derant les autres variables comme des constantes :

∂f/∂x1 = 4x1 + 2x2 − 10

∂f/∂x2 = 2x1 + 2x2 − 10

De sorte que le gradient peut s’ecrire ici comme suit :

∇f(x) = [4x1 + 2x2 − 10, 2x1 + 2x2 − 10]

Definition 11.8 Notion d’independance de vecteurs. On dit que m vecteurs sontlineairement independants si aucun ne peut etre exprime comme une combinaisonlineaire des autres.

Ainsi, les vecteurs (1,0) et (0,1) de R2 sont lineairement independants car il

est impossible d’ecrire l’un comme un multiple de l’autre. Par contre les vecteurs

140 Chapitre 11. Les modeles non lineaires

(2,3), (1,0) et (0,1) ne sont pas lineairement independants car on peut ecrire (2,3)comme une combinaison lineaire des deux autres. En effet :

(2, 3) = 2 × (1, 0) + 3 × (0, 1).

On peut alors ecrire les tres importantes conditions necessaires suivantes :

Theoreme 11.1 Conditions necessaires de Kuhn-Tucker. Soit x∗ un minimumlocal pour le probleme

min f(x)

s.c.q.

{h(x) = 0,g(x) ≤ 0

(11.3)

et supposons x∗ regulier pour les contraintes. Alors il existe des multiplicateursλ ∈ Rm et µ ∈ Rp tels que

∇f(x∗) +m∑

i=1

λi∇hi(x∗) +

p∑k=1

µk∇gk(x∗) = 0 (11.4)

µkgk(x∗) = 0, ∀k = 1, . . .p (11.5)

µk ≥ 0, ∀k = 1, . . .p

Les conditions (11.5) sont les conditions de complementarite disant que siune contrainte n’est pas active, son multiplicateur µk doit etre nul. Pour biencomprendre la signification pratique des conditions (11.4), nous allons les recrireau moyen de la fonction de Lagrange. La fonction de Lagrange est obtenueen multipliant le membre de gauche de chaque contrainte d’egalite (hi(x) = 0)par un multiplicateur λi, le membre de gauche de chaque contrainte d’inegalite(gk(x) ≤ 0) par son multiplicateur µk et en additionnant le tout a la fonctionobjectif :

L(x, λ, µ) = f(x) +m∑

i=1

λihi(x) +p∑

k=1

µkgk(x)

Remarquez que ce faisant, on passe d’un probleme d’optimisation sous contraintesa un probleme d’optimisation sans contrainte. Les conditions d’optimalite pourune fonction definie sur R

n sont simplement l’annulation de son gradient. Onremarque que precisement les conditions de Kuhn et Tucker (11.4) ne sont riend’autre que l’annulation du gradient par rapport a x du gradient du Lagrangien :

∇xL(x∗, λ∗, µ∗) = 0.

Illustrons ceci sur l’exemple suivant :

min 2x21 + 2x1x2 + x2

2 − 10x1 − 10x2

s.c.q.

{x2

1 + x22 ≤ 5

3x1 + x2 ≤ 6

Section 11.5. Conditions de Kuhn et Tucker 141

Le lagrangien s’ecrit de la maniere suivante :

L(x, λ, µ) = 2x21 + 2x1x2 + x2

2 − 10x1 − 10x2

+µ1(x21 + x2

2 − 5)

+µ2(3x1 + x2 − 6)

Les conditions de Kuhn et Tucker s’ecrivent ici simplement :

∂L/∂x1 = 4x1 + 2x2 − 10 + 2µ1x1 + 3µ2 = 0

∂L/∂x2 = 2x1 + 2x2 − 10 + 2µ1x2 + µ2 = 0

µ1g1 = µ1(x21 + x2

2 − 5) = 0

µ2g2 = µ2(3x1 + x2 − 6) = 0

µ1 ≥ 0

µ2 ≥ 0

Parfois, la resolution de ces conditions permet de determiner le point optimum.Ainsi, supposons la premiere contrainte active, et la seconde inactive (µ2 = 0).Les conditions se reduisent a :

4x1 + 2x2 − 10 + 2µ1x1 = 0

2x1 + 2x2 − 10 + 2µ1x2 = 0

x21 + x2

2 = 5

dont la solution est donnee par :

x∗1 = 1,

x∗2 = 2,

µ1 = 1,

µ2 = 0.

Comme, de plus, µ1 ≥ 0, cette solution satisfait les conditions necessaires de Kuhnet Tucker.

Enfin, on peut montrer la proposition suivante.

Proposition 11.1 Si le probleme est un probleme convexe, les conditions neces-saires sont aussi suffisantes pour montrer que l’on est a l’optimum.

Nous presenterons au chapitre suivant les algorithmes de resolution.

142 Chapitre 11. Les modeles non lineaires

11.6 Exercices

11.1. Conditions de Kuhn et Tucker. On considere la maximisation de la fonction14x − x2 + 6y − y2 + 7 sous les contraintes x + y ≤ 2 et x + 2y ≤ 3.

(a) Ecrire les conditions necessaires d’optimalite de Kuhn et Tucker.

(b) Determiner graphiquement la solution optimale.

(c) Verifiez que cette solution satisfait les conditions de Kuhn et Tucker.

11.2. Minimisation des risques. Un epargnant dispose de 100 francs a investiren bourse. Son portefeuille d’actions peut comporter trois titres dont onveut determiner les parts optimales x, y et z. Les rendements rX , rY et rZ

de ces trois titres sont des variables aleatoires. On suppose connues leursmoyennes respectives : 30%, 20% et 8 %. Le risque V (x, y, z) est mesure apartir de la matrice de variance-covariance des rendements des trois titres :

V (x, y, z) = (x, y, z)

3 1 −0.5

1 2 −0.4−0.5 −0.4 1

x

yz

On veut minimiser le risque V (x, y, z) tout en s’imposant un rendementespere du portefeuille au moins egal a 12 %.

(a) Ecrire le programme quadratique correspondant.

(b) Ecrire les conditions de Kuhn et Tucker pour ce probleme et verifier sila solution (x; y; z) = (20, 091; 16, 712; 32, 877) les satisfait.

Chapitre 12

Resolution des problemes non lineaires

12.1 Introduction

Au chapitre 11, nous avons introduit la notion de modele non lineaire. En general,il s’agit de resoudre le probleme suivant :

max f(x)

s.c.q.

gi(x) ≤ 0, i = 1, . . .m

hk(x) = 0, k = 1, . . .p

ou au moins une des fonctions est non lineaire. Nous avons egalement vu lesconditions de Kuhn et Tucker qui sont necessairement verifiees a l’optimumd’un tel probleme.

Nous allons maintenant voir deux cas particuliers de problemes non lineairesqui peuvent etre resolus par recours iteratifs a la programmation lineaire. Il s’agitrespectivement :

• Des problemes separables qui ne comportent que des fonctions non line-aires d’une seule variable. Comme nous allons le voir a la section 12.2, cesproblemes peuvent etre resolus en considerant une suite d’approximationlineaires par morceaux des fonctions non lineaires d’une seule variable.

• Des problemes a contraintes lineaires. Comme nous allons le voir a lasection 12.3, ces problemes peuvent etre resolus par la methode de Franck-Wolfe qui considerent une suite d’approximations lineaires de la fonctionobjectif non lineaire.

143

144 Chapitre 12. Resolution des problemes non lineaires

12.2 Programmation separable

Il existe une classe particuliere de problemes qui ne necessitent pas le recours a deslogiciels d’optimisation non lineaire, car ils peuvent se resoudre par utilisationsrepetees de l’algorithme du Simplexe. Ce sont les programmes separables.

Definition 12.1 Une fonction est separable si elle peut etre exprimee comme lasomme de fonctions d’une seule variable :

f(x) =n∑

j=1

fj(xj)

Par exemple, la fonction suivante est separable :

x21 + 2x2 + ex3

,

puisque somme de fonctions d’une seule variable alors que la fonction suivante :

x1x2 +1

1 + x1

+ x3

est non separable a cause du terme x1x2.

Un exemple pratique, deja cite au chapitre 11, d’application de la programma-tion separable est la relation entre le flot de gaz entre les nœuds i et j, note fij , etles pressions en ces points, pi et pj :

f 2ij = C2

ij

(p2

i − p2j

)ou Cij est un parametre constant dependant de la longueur et du diametre dugazoduc.

Les modeles separables peuvent etre resolus par une suite d’approximationslineaires par morceaux. Plus precisement, on effectuera de la maniere suivant.

Algorithme 12.1 Algorithme de resolution des problemes separables.

1. Chaque fonction non lineaire d’une seule variable est remplacee par uneapproximation lineaire par morceaux.

2. Le probleme approxime est alors resolu par une version specialisee del’algorithme du Simplexe traitant les problemes lineaires par morceaux.

3. Enfin, si la solution ainsi obtenue s’ecarte trop des relations non lineairesoriginales, on raffine la discretisation autour de la solution optimale duprobleme approxime et on itere.

Section 12.2. Programmation separable 145

Voyons ceci sur un exemple. Supposons que l’on ait a resoudre le problemeconvexe suivant :

min x21 − 4x1 − 2x2

scq

x1 + x2 ≤ 42x1 + x2 ≤ 5

−x1 + 4x2 ≥ 2x1, x2 ≥ 0

(12.1)

Il s’agit bien d’un probleme convexe car on minimise x21 qui est une fonction

convexe. La premiere chose a faire est de se donner une borne inferieure et uneborne superieure a la valeur que pourra prendre la variable non lineaire. Supposonsici que 0 ≤ x1 ≤ 2, 5. On choisit alors un ensemble de valeurs de x1 ou la fonctionest evaluee. Ici, ce sont les points 0, 1, 2 et 2,5. On calcule la valeur de la fonctionen ces points. Ceci est fait ci-dessous :

Point O x1 = 0 y = x21 = 0

Point A x1 = 1 y = x21 = 1

Point B x1 = 2 y = x21 = 4

Point C x1 = 2, 5 y = x21 = 6, 25

On obtient les points O, A, B et C a la figure 12.1.

x

y = x2

O

B

C

1

2

3

4

5

6

1 2

A

(1)

(2)

(3)

Figure 12.1: Approximation par une fonction lineaire par morceaux

On construit alors une approximation lineaire par morceaux de la fonction enreliant par des segments de droite les points d’evaluation de la fonction. On obtient

146 Chapitre 12. Resolution des problemes non lineaires

la courbe lineaire par morceaux indiquee par OABC a la figure 12.1.

Nous allons maintenant voir comment resoudre le probleme lineaire par mor-ceaux. En effet, l’algorithme du Simplexe ne peut traiter directement ce genre deprobleme. Il existe au moins deux methodes pour resoudre le probleme lineairepar morceaux au moyen de l’algorithme du Simplexe, a savoir

• le recours a la notion d’epigraphe;

• le recours a la notion d’enveloppe convexe des sommets.

12.2.1 Resolution par la notion d’epigraphe

Lorsque le probleme est convexe, on peut remplacer la fonction lineaire par mor-ceaux liant x1 et y par son epigraphe comme fait a la figure 12.1. On peut verifierque l’epigraphe correspond aux trois inegalites suivantes :

y ≥ x1 (1)y ≥ 3x1 − 2 (2)y ≥ 4, 5x1 − 5 (3)

Ce qui peut encore s’ecrire comme suit :

x1 − y ≤ 0

3x1 − y ≤ 2

4, 5x1 − y ≤ 5

Il suffit alors de minimiser y. En effet, en minimisant y avec la contrainte que(x1, y) appartienne a l’epigraphe, on se retrouvera donc bien sur la limite inferieurede l’epigraphe, donc sur la la courbe lineaire par morceaux indiquee par OABC ala figure 12.1. Le probleme original est donc remplace par le suivant :

min y − 4x1 − 2x2

scq

x1 +x2 ≤ 42x1 +x2 ≤ 5−x1 +4x2 ≥ 2

x1 −y ≤ 03x1 −y ≤ 2

4, 5x1 −y ≤ 5x1, x2 ≥ 0

Section 12.2. Programmation separable 147

12.2.2 Resolution par la notion d’enveloppe convexe

Une seconde solution est d’imposer que (x1, y) appartiennent a l’ensemble convexedes points extremes du polygone OABC comme illustre a la figure 12.2. Pour cela,

x

y = x2

O

B

C

1

2

3

4

5

6

1 2

A

Figure 12.2: Approximation par une fonction lineaire par morceaux

on a ecrire que (x1, y) est une combinaison convexe des sommets du polygone.Une combinaison convexe est une combinaison lineaire dont tous les coefficientssont positifs et dont la somme est egale a un.

On note par λi le poids attribue a chacun des points de cassure O, A, B et C dela fonction approximee. On traduit alors le fait d’appartenir a l’enveloppe convexede ces quatre sommets par les relations suivantes liant x1 et y :

x1 = 0λ1 +1λ2 +2λ3 +2, 5λ4

y = 0λ1 +1λ2 +4λ3 +6, 25λ4

1 = λ1 +λ2 +λ3 +λ4

(12.2)

Si on veut se restreindre a etre sur la courbe lineaire par morceaux, il faut imposerla restriction supplementaire que :

au plus deux λi adjacents sont non nuls. (12.3)

Les relations (12.2) traduisent le fait que le point (x1, y) est combinaison convexedes points extremes O, A, B et C alors que la condition supplementaire (12.3)

148 Chapitre 12. Resolution des problemes non lineaires

impose en plus que l’on se trouve sur un des segments OA, AB ou BC puisquel’on est une combinaison convexes des deux points extremes adjacents.

Voyons maintenant comment resoudre le probleme approxime. Remarqueza nouveau que la fonction illustree par la la courbe lineaire par morceaux OABCde la figure 12.2 est une fonction non lineaire. Elle ne peut donc directement etretraitee par l’algorithme du Simplexe.

Ainsi le programme convexe (12.1) est approxime par :

min y − 4x1 − 2x2

scq

x1 +x2 ≤ 42x1 +x2 ≤ 5−x1 +4x2 ≥ 2−x1 +λ2 + 2λ3 + 2, 5λ4 = 0

−y +λ2 + 4λ3 + 6, 25λ4 = 0λ1 + λ2 + λ3 + λ4 = 1

y, x1, x2, λ1, λ2, λ3, λ4 ≥ 0

Remarquons que la condition (12.3) sera automatiquement verifiee pour unprogramme convexe. En effet, supposons que la repartition des poids ne verifiepas la condition, par exemple :

λ1 = 0, 5 λ2 = 0, 25 λ3 = 0, 25

qui correspond au point :

x = 0, 75 et y = 1, 25

Comme on minimise y, on peut faire mieux en prenant :

x = 0, 75 et y = 0, 75,

c’est-a-dire precisement en se trouvant sur la limite inferieure de l’ensembleconvexe OABC. On en conclut que pour les problemes separables convexes,on s’est ramene a la resolution d’un probleme lineaire pur !

Pour les problemes separables non convexes, il faudra imposer explicitementla condition (12.3). Par exemple, si l’on veut minimiser la fonction y = x3 quiest convexe pour les x > 0 et concave pour les x < 0, Il faudra avoir recours aune extension de l’algorithme du Simplexe qui impose explicitement qu’au plusdeux λi consecutifs sont non nuls (voir De Wolf et Smeers [5]). On obtiendra ainsil’optimum global pour des problemes convexes et un optimum local pour desproblemes non convexes.

Quelle que soit la methode utilisee pour resoudre le probleme approxime, onintroduit une erreur par rapport la vraie fonction. Ainsi pour x1 = 1, 5, la fonctionvraie x2

1 vaut 2, 25 alors que son approximation lineaire par morceaux fournitcomme valeur 2, 5. D’ou la necessite de raffiner la discretisation et d’iterer.

Section 12.3. La methode de Franck-Wolfe 149

12.3 La methode de Franck-Wolfe

Nous allons voir un type particulier d’algorithme qui permet de resoudre lesproblemes d’optimisation non lineaires convexes. Il est du type sequence d’ap-proximations lineaires. Il s’agit de l’algorithme de Franck-Wolfe.

Son principe est particulierement simple dans le cas de problemes avec con-traintes lineaires. En effet, cette procedure combine des approximations lineairesde l’objectif pour trouver la direction de recherche avec une recherche unidimen-sionnelle pour trouver le pas suivant cette direction.

Etant donnee la solution initiale realisable x0, la fonction objectif du problemesuivant

max f(x)

scq

{Ax ≤ b

x ≥ 0(12.4)

est approxime par son developpement de Taylor d’ordre 1 :

f(x) ≈ f(x0) +n∑

j=1

∂f(x0)

∂xj

(xj − x0j)

Si on substitue dans (12.4), a f(x) son approximation donnee, a une constantepres, par g(x) definie ci-dessous :

g(x) =n∑

j=1

cjxj

avec

cj =∂f(x0)

∂xj

,

on obtient un probleme lineaire soluble par l’algorithme du Simplexe. Notons x1LP

sa solution optimale de ce premier probleme lineaire.

Notez que l’objectif non lineaire est de moins en moins bien approxime par sonapproximation lineaire lorsque x s’ecarte de x0 mais que l’objectif doit s’accroıtre,du moins au debut, le long du segment de x0 a x1

LP . Aussi va-t-on choisir le pointqui maximise f(x) le long de ce segment en resolvant le probleme unidimensionnelsuivant :

max0≤α≤1

h(α) = f(x0 + α(x1LP − x0))

On verifie que α = 0 correspond a rester en x0 et α = 1 correspond a aller en x1LP .

Notons α∗, l’optimum. Le point suivant :

x1 = x0 + α∗(x1LP − x0)

150 Chapitre 12. Resolution des problemes non lineaires

deviendra le point initial pour l’iteration suivante.

Appliquons ceci sur l’exemple suivant :

max f(x) = 5x1 − x21 + 8x2 − 2x2

2

scq

{3x1 + 2x2 ≤ 6

x1, x2 ≥ 0

Calculons le gradient :

∂f

∂x1

= 5 − 2x1

∂f

∂x2

= 8 − 4x2

Il est clair que x = (0, 0) fournit une solution realisable initiale :

x0 = (0, 0)

Donc les coefficients du gradient sont

c1 = 5

c2 = 8

On peut resoudre graphiquement le probleme lineaire suivant :

max z = 5x1 + 8x2

scq

{3x1 + 2x2 ≤ 6

x1, x2 ≥ 0

A la figure 12.3, on obtient P1, la solution du premier probleme lineaire :

x1LP = (0, 3)

Le segment entre x0 et x1LP a comme coordonnees :

x(α) = x0 + α(x1LP − x0) = (0, 0) + α[(0, 3) − (0, 0)]

= (0, 3α)

On va donc maximiser la fonction

h(α) = f(x(α)) = 24α − 18α2

sous les contraintes que 0 ≤ α ≤ 1. La maximisation sans contrainte conduit aannuler la derivee premiere :

24 − 36α = 0

Section 12.3. La methode de Franck-Wolfe 151

x1

x2

1 2

3

2

1

P1

P2

P0

Figure 12.3: Methode de Franck Wolfe

soit α = 2/3. On obtient donc le point en fin d’iteration 1 :

x1 = (0, 0) + 2/3[(0, 3) − (0, 0)] = (0, 2)

Procedons a la deuxieme iteration :

c1 = 5 − 2 × 0 = 5

c2 = 8 − 4 × 2 = 0

On peut resoudre graphiquement le probleme lineaire suivant :

max z = 5x1

s.c.q.

{3x1 + 2x2 ≤ 6

x1, x2 ≥ 0

A la figure 12.3, on obtient P2, la solution du deuxieme probleme lineaire :

x2LP = (2, 0)

Le segment entre x1 et x2LP a comme coordonnees :

x1 + α(x2LP − x1) = (0, 2) + α[(2, 0) − (0, 2)]

= (2α, 2 − 2α)

de sorte que l’on maximise

max h(α) = 8 + 10α − 12α2

152 Chapitre 12. Resolution des problemes non lineaires

sous les contraintes que 0 ≤ α ≤ 1. La maximisation sans contrainte conduit aannuler la derivee premiere :

10 − 24α = 0

soit α = 5/12. On obtient donc le point en fin d’iteration 2 :

x2 = (0, 2) + 5/12[(2, 0) − (0, 2)] = (5/6, 7/6)

On peut resumer l’algorithme de Franck-Wolfe comme suit.

Algorithme 12.2 Algorithme de Franck-Wolfe.

1. Initialisation. Soit x0 une solution initiale realisable. Posons k = 1.

2. Iteration k. Pour j = 1, 2, ...n, evaluer

cj =∂f(xk−1)

∂xj

3. Calcul de la direction. Trouver, par application de l’algorithme du Sim-plexe, xk

LP la solution optimale du probleme lineaire suivant :

max g(x) =n∑

j=1

cjxj

scq

{Ax ≤ bx ≥ 0

4. Calcul du pas. Trouvez αk la solution optimale de

max f[xk−1 + α(xk

LP − xk−1)]

scq 0 ≤ α ≤ 1

et mettrexk = xk−1 + αk(x

kLP − xk−1)

5. Critere d’arret. Si xk−1 et xk sont suffisamment proches, stop. Sinon retouren 2.

Reste a resoudre en general, le probleme de la maximisation de la fonctiond’une variable h(α). Si on peut evaluer une fonction f(x) d’une seule variableainsi que sa derivee premiere f ′(x) en tout point, on peut se baser sur la procedurede recherche unidimensionnelle illustree a la figure 12.4

Soit [x, x] l’intervalle de recherche. Chaque iteration consiste en les pointssuivants :

Section 12.3. La methode de Franck-Wolfe 153

xx′ xx

f(x)

xx ′ xx

f(x)

Figure 12.4: Recherche unidimensionnelle.

1. Calculerx′ =

x + x

2

et evaluer f ′(x′), la derivee de f en x′.

2. Si f ′(x′) ≥ 0, mettre x = x′.

3. Si f ′(x′) < 0, mettre x = x′. Retour en 1.

Illustrons ceci sur un exemple. Soit la fonction d’une seule variable suivante :

f(x) = 12x − 3x4 − 2x6

Calculonsf ′(x) = 12 − 12x3 − 12x5 = 12(1 − x3 − x5)

Les 4 premieres iterations sont illustrees au tableau 12.1.

k f ′ x x x′ f(x′)

0 0, 00 2, 000 1, 0000 7, 0000

1 −12, 00 0, 00 1, 000 0, 5000 5, 7812

2 10, 12 0, 50 1, 000 0, 7500 7, 6948

3 4, 09 0, 75 1, 000 0, 8750 7, 8439

4 −2, 19 0, 75 0, 875 0, 8125 7, 8672

Tableau 12.1: Quelques iterations de la recherche unidimensionnelle.

154 Chapitre 12. Resolution des problemes non lineaires

12.4 Exercices

12.1. Programmation separable. Resoudre le probleme non lineaire separablesuivant en appliquant la technique d’approximations lineaires par morceaux :

Min x21 − 4x1 − 2x2

Scq

x1 + x2 ≤ 42x1 + x2 ≤ 5

−x1 + 4x2 ≥ 2x1, x2 ≥ 0

12.2. Methode de Franck-Wolfe. Faire la troisieme iteration de la methode deFranck-Wolfe pour l’exemple traite a la section 12.3.

12.3. Recherche unidimensionnelle. Faire trois iterations de plus pour l’exemplede recherche unidimensionnelle traite a la section 12.3 et en deduire parextrapolation la solution optimale du probleme non lineaire.

Bibliographie

[1] Ravindra AHUJA, Thomas MAGNANTI et James ORLIN, Network Flows,Prentice Hall, Englewood Cliffs, 1993.

[2] BAGLIN Gerard, Olivier BRUEL, Alain GARREAU, Michel GREIF etChristian VAN DELFT, Management Industriel et Logistique, Economica,Paris, 1996.

[3] BROOKE Anthony, David KENDRICK et Alexander MEERAUS, GAMSUser’s guide Release 2.25, The Scientific Press, San Francisco, 1992.

[4] CHVATAL Vasek, Linear Programming, Freeman and Company, 1983.

[5] DE WOLF Daniel, Olivier JANSSENS dE BISTHOVEN et Yves SMEERS,The Simplex algorithm extended to piecewise linearly constrained problems,CORE DISCUSSION Paper 9119, Universite Catholique de Louvain, 1991.

[6] EXCEL, Guide de l’utilisateur, Microsoft, 1992.

[7] GIARD Vincent, Gestion de la production et des flux, Economica, Paris,2003.

[8] Christelle GUERET, Christian PRINS, Marc SEVAUX, Programmationlineaire, Eyrolles, Paris, 2000.

[9] GUERRIEN Bernard, Initiation aux mathematiques, Economica, 1991.

[10] F.S. HILLIER et G.S. LIEBERMAN, Introduction to Operations Research,6eme edition, Mac Graw-Hill International Editions, Singapour, 1995.

[11] F.S. HILLIER, M.S. HILLIER et G.S. LIEBERMAN, Introduction to Mana-gement Sciences, 1ere edition, Mac Graw-Hill International Editions, Boston,2000.

[12] LACAZE Dominique, Optimisation appliquee a la gestion et a l’economie,Economica, 1990.

155

156 Bibliographie

[13] D. G. LUENBERGER, Linear and NonlinearProgramming, Addison-Wesley,1984.

[14] NEMHAUSER, G.L. et L.A. WOLSEY, Integer and Combinatorial Optimi-zation, Wiley, New York, 1988.

[15] Y. NORBERT, R. OUELLET et R. PARENT, La recherche operationnelle,Gaetan Morin Editeur, Montreal-Paris, 1995.

[16] SIMMONARD Michel, La programmation lineaire, Dunod 1972.

[17] M.P. WILLIAMS, Model building in Mathematical Programming, John Wi-ley, 1990.

[18] M.P. WILLIAMS, Model solving in Mathematical Programming, John Wiley,1992.

[19] XPRESS-MP, User Guide and Reference Manual, Release 10, Dash Asso-ciate, 1997.