Optimisation : études de cas

A. MENNI
2023 – 2024

Cours 1 : Algorithme du simplexe (rappels)

Les itérations de l’algorithme du simplexe sont en général présentées sous forme de tableaux ayant la

forme suivante :

variables de base valeurs courantes xH1 xH2 ... xHn x B1 x B2 ... xBm

x B1 b̄1 a11 a12 ... a1n 1 0 ... 0

x B2 b̄2 a21 a22 ... a2n 0 1 ... 0

.. .. .. .. .. .. .. .. ..
. . . . . . . . .

xBm b̄m am1 am2 ... amn 0 0 ... 1

−f − val. de f c̄1 c̄2 ... c̄n 0 0 ... 0

Tableau 1 – Tableau simplexe

ou la forme suivante :

variables de base valeurs courantes xH1 xH2 ... xHn

x B1 b̄1 a11 a12 ... a1n

x B2 b̄2 a21 a22 ... a2n

.. .. .. .. ..
. . . . .

xBm b̄m am1 am2 ... amn

−f − val. de f c̄1 c̄2 ... c̄n

Tableau 2 – Forme simplifiée d’un tableau simplexe

Les xBi (i = 1, . . . , m) sont les variables de base et les b¯i sont respectivement leurs valeurs qui changent

d’une itération à l’autre de l’algorithme.

Les xHj (j = 1, . . . , n) sont les variables hors–base ; elles sont toutes nulles.

Les c̄j (j = 1, . . . , n) sont les coefficients–objectifs courants ; ils sont aussi appelés « côuts réduits ».

1
 Le principe de l’algorithme du simplexe se résume par les étapes suivantes :

Etape0 : Initialisation

sélectionner les variables d’ecarts comme variables de base et les variables de décision comme variables

hors-base.

Etape1 : Test d’optimalité

si tous les coefficients-objectifs sont négatifs ou nuls alors STOP, la solution courante est optimale. Sinon

Aller à l’étape 2.

Etape2 : Choix de la variable entrante en base (choix de la colonne pivot)

choisir comme variable entrante la variable hors-base dont le coefficient–objectif est le plus élevé parmi

les coefficients positifs ; si plusieures variables sont candidates pour entrer en base, on choisit parmi celles-ci

celle de plus petit indice.

soit r le numéro de la colonne pivot. Aller à l’étape 3.

Etape3 : Choix de la variable sortante de la base (choix de la ligne pivot)

— Si air ≤ 0 pour tout i = 1, . . . , m, alors STOP ; le problème est non–borné.

— Sinon, on choisit comme variable sortante celle qui correspond à la ligne « s » tel que :

bs bi
= min { } ; ∀air > 0,
asr 1≤i≤m air

si plusieures variables sont candidates pour sortir de la base, on choisit parmi celles-ci celle de plus petit

indice.

L’élément asr est appelé « pivot ».

Etape4 : Calcul de la nouvelle solution de base (pivotage ou passage au tableau suivant)

— Diviser les éléments de la ligne pivot par le pivot (i.e., diviser l’équation s par asr ).

— Transformer les lignes du tableau en appliquant la règle suivante :

akr
Lk := Lk − × Ls
asr

où Lk désigne la k ème ligne du tableau.

— retour à Etape1.

2
Exemple illustratif

Regardons un exemple tiré de l’ouvrage de F.S. Hillier et G.S. Lieberman, sous le titre : Introduction

to Operations Research (Springer,1995).Il s’agit d’une entreprise qui fabrique des chassis et qui envisage

la fabrication de deux nouveaux modèles au moyen des capacités résiduelles de ses trois ateliers. Les marges

bénéficiaires unitaires, le temps de fabrication ainsi que les capacités disponibles sont résumés dans le tableau

suivant :

Modèle1 Modèle2 capacité disponible

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

Atelier1 1 0 4

Atelier2 0 2 12

Atelier3 3 2 18

Marges ($) 3 5

La question qui se pose ici est la suivante : combien faut-il produire de chassis de chaque type, par semaine,

afin de maximiser le profit net ? Appliquer l’algorithme du simplexe pour résoudre le problème de fabrication

des deux nouveaux modèles de chassis.

Un autre exemple (méthode des deux phases)

Résoudre le PL suivant :





 max f = x1 − x2 + x3









2x1 −x2 +2x3 ≤ 4


(P )
−2x1 +3x2 −x3 ≥5






−x2 +2x3 ≥1




 x1


 x1 , x2 , x3 ≥ 0
