Cours du module Recherche Opérationnelle

Pr. Omar ANANE

Cours du module

Recherche Opérationnelle Cycle ingénieur

Filières : Génie Télécommunications et Réseaux

& Génie Electrique

Université Mohammed Premier

ENSAO

Programme du module

Partie1: Programmation linéaire

• Introduction

• Théorème fondamental de la programmation linéaire

• Algorithme du simplexe

• Pratique de la méthode du simplexe

• Dualité en programmation linéaire

Partie2: Théorie des graphes et applications

• Eléments de théorie des graphes

• Problème de recherche des chemins optimaux

• Problème d’ordonnancement

• Problème de transport

• Problème d’affectation

• Phénomènes d’attente

• Gestion scientifique des stocks

Cours Recherche opérationnelle - GTR & GE - Omar ANANE

1- Introduction


a) Un exemple

Position du problème: Une entreprise fabrique deux produits P1 et P1 dans trois ateliers A1, A2 et

A3. La production d’une unité de P1 (resp. P2) nécessite une 1 minute de travail dans l’atelier A1, 1 mn

dans A2 et 4 mn dans A3. (resp. 2 mn dans A1, 1 mn dans A2 et 30s dans A3), La vente d’une unité de

P1 (resp. P2) rapporte un bénéfice de 4 Dh (resp. 3 Dh). Les durées de fonctionnement des ateliers A1,

A2 et A3 ne peuvent pas excéder respectivement 10h , 6h et 17h par jour. Quelles sont les quantités

optimales des produits P1 et P2 que l’entreprise doit produire par jour ?

Formulation du problème: Désignons par 𝑥1 et 𝑥2 respectivement les quantités des produits P1 et

P2 à produire par jour. Les durées de fonctionnement nécessaires à ces productions sont :

• Pour l’atelier A1 : 𝑥1 +2𝑥2 ,

• Pour l’atelier A2 : 𝑥1 +𝑥2

• Pour l’atelier A3 : 4𝑥1 +0,5𝑥2

Les contraintes de production sont : (I)

𝑥1 +2𝑥2 ≤ 600𝑥1 + 𝑥2 ≤ 360

4𝑥1 +0,5𝑥2 ≤ 1020𝑥1 ≥ 0 𝑒𝑡 𝑥2 ≥ 0

Posons x=(𝑥1 ;𝑥2) et désignons par K l’ensemble des point x de ℝ2 vérifiant les inégalités (I)

Le bénéfice à la ventes des quantités produites par jour est : c(x) = 4𝑥1 +3𝑥2

Le problème se formule donc de la façon suivante :

𝑃 : 𝑇𝑟𝑜𝑢𝑣𝑒𝑟 𝑥 ∈ 𝐾 𝑡𝑒𝑙 𝑞𝑢𝑒:

𝑐 𝑥 = max {𝑐 𝑥 , 𝑥 ∈ 𝐾}

240

120

300

Résolution graphique du problème:

K

1- Introduction


240

120

C’ 255

4𝑥1 +0,5𝑥2 = 1020

b) Remarques:

• La fonctionnelle à maximiser et les contraintes sont linéaires ( de ce fait, le problème (P) est

dit programme linéaire);

• L’ensembles des contraintes K est un polyèdre (intersection de demis-espaces);

• La droite (hyperplan) c(x) = α (α constante) est orthogonale au vecteur c’= (4;3). Le bénéfice

α augmente lorsqu’on déplace cette droite dans le sens du vecteur c’;

• La droite optimale (qui correspond à un bénéfice maximale) est celle qui passe par le point

(240,120) qui est un sommet du polyèdre K;

• Lorsque le nombre de variables est réduit à 2, la résolution graphique est possible,

• Une solution du problème (P) est un sommet du polyèdre K. Cette constatation est en fait

générale : c’est le théorème fondamental de la programmation linéaire;

• Pour un problème donné, si on arrive à énumérer l’ensembles des sommets du polyèdre de ses

contraintes, ont peut trouver un sommet optimal. Cette méthode n’est pas envisageable dans

les problèmes rencontrés dans la pratique qui comprennent plusieurs dizaines de variables et

de contraintes;

• Pour résoudre un programme linéaire, l’algorithme du simplexe permet, en partant d’un

sommet initial, construire par un procédé itératif, une suite de sommets qui améliorent

progressivement la fonction objectif, pour aboutir après un nombre fini d’itérations à une

solution du problème.

1- Introduction


c) Taille des PL:

• On considère que des PL comportant m=1000 contraintes et n= 3 000 variables sont de dimension

courante (pour l’algorithme du simplexe). On parle de gros problèmes à partir de m = 5 000 contraintes

et n = 10 000 variables.

• De très gros PL ont été résolus opérationnellement : un PL avec m = 30 000 et n = 300 000 pour la

gestion intégrée de la firme américaine NABISCO, et à la NASA n = 35 000 et m = 512 000. Pour une

compagnie aérienne, un problème avec n = 5 500 000 variables (mais seulement m=850 contraintes) a

aussi été résolu. Avec des PL dont les données ont des structures particulières, on a pu même dépasser

les 10 000 000 de variables !

• Pour n variables et m contraintes explicites, il y a 𝑚+𝑛 !

𝑚!𝑛! sommets possibles. Cette valeur croissant très

vite avec m et n, l’énumération est impraticable pour des problèmes de taille industrielle. Ainsi pour un

petit PL comportant m = 20 contraintes et n = 30 variables il y a 4,7129x1013 sommets possibles :

même en calculant un million de sommets par seconde il faudrait un an et demi pour résoudre par

ordinateur ce tout petit problème

d) Rentabilité:

• L’emploi de la PL permet d’optimiser des systèmes et de réaliser des économies de pouvant dépasser

10% sur le coût de fonctionnement du système.

• L’optimisation de l’achat de pneumatiques pour équiper des véhicules chez un grand constructeur avait

permis une économie de 0,5% sur un coût mensuel de 12 millions d’euros soit 600 000 €/mois …

• Il n’est pas rare qu’une optimisation à l’aide de la P.L. permette des gains annuels représentant 200 à

300 fois le coût de l’étude. Les « retours sur investissement » se comptent plus souvent en semaines ou

en mois, qu’en années…

1- Introduction


2- Théorème fondamental de la programmation linéaire


a) Définitions et notations

• Les éléments de ℝn sont notés x=

𝑥1⋮𝑥𝑛

(vecteur colone), le produit scalaire euclidien est noté ( | )

• Les éléments du dual ℝn* de ℝn (ensemble des formes linéaires sur ℝn) sont notés 𝑎=(𝑎1, … , 𝑎𝑛)

(vecteur ligne), le produit de dualité est noté < ,> ( 𝑎(x) ≝< 𝑎 , 𝑥 > 𝑎𝑣𝑒𝑐 𝑎 ∈ ℝn* et x ∈ ℝn )

• La transposé d’un vecteur colonne x=

𝑥1⋮𝑥𝑛

est le vecteur ligne x’=(𝑥1, … , 𝑥𝑛) et la transposé d’un

vecteur ligne 𝑎=(𝑎1, … , 𝑎𝑛) est le vecteur colonne 𝑎′=

𝑎1⋮𝑎𝑛

. On a ∶ < 𝑎 , 𝑥 >=(a’| x)

• L’ensemble des matrices réelles à m lignes et n colonnes est noté Mm,n

• Soit 𝑎 ∈ ℝn* et b ∈ ℝ, l’hyperplan H={ x ∈ ℝn : < 𝑎 , 𝑥 > = 𝑏} est noté H={a= 𝑏}, il est

orthogonal au vecteur 𝑎’ et partage l’espace ℝn en deux demi-espaces fermés :

H+ = { x ∈ ℝn : < 𝑎 , 𝑥 > ≥ 𝑏}≝ {a ≥ 𝑏} et H- = { x ∈ ℝn : < 𝑎 , 𝑥 > ≤ 𝑏}≝ {a ≤ 𝑏}

• Un polyèdre K de ℝn est une intersection d’un nombre fini de demis espaces fermés :

𝐾 = {𝑎𝑖 ≤ 𝑏𝑖1≤𝑖≤𝑚

} ≝ { x ∈ ℝn : < 𝑎𝑖 , 𝑥 > ≤ 𝑏𝑖 , i=1, … ,m}

Où les 𝑎𝑖 sont des formes linéaires non nulles et 𝑏𝑖 des scalaires.



• Une face d’un polyèdre K est une partie frontalière F de K de la forme :

FJ = { x ∈ K : < 𝑎𝑖 , 𝑥 > = 𝑏𝑖 , i ∈ 𝐽}

Où J est un sous ensemble de { 1, …, m}

Il résulte de cette définition qu’une face d’un polyèdre est un polyèdre et qu’une face d’une face d’un

polyèdre est une face de ce polyèdre

• Un sommet de K est une face réduite à un singleton (un point)

• Une arrête de K est une face réduite à une portion de droite

• Un polyèdre est dit saillant s’il contient au moins un sommet



• Un programme linéaire (PL) est un problème qui s’exprime sous la forme générale :

𝑃 : 𝑇𝑟𝑜𝑢𝑣𝑒𝑟 𝑥 𝑡𝑒𝑙 𝑞𝑢𝑒:

< 𝑐 , 𝑥 >= m𝑖𝑛 < 𝑐 , 𝑥 >< 𝑎𝑖 , 𝑥 >≤ 𝑏𝑖 , 𝑖 = 1,… ,𝑚

Où 𝑐 , 𝑎𝑖 ∈ ℝn* et 𝑏𝑖 ∈ ℝ

• La forme linéaire est dite fonction objectif ou fonction coût

• Les inégalités < 𝑎𝑖 , 𝑥 > ≤ 𝑏𝑖 , i=1, … ,m s’appelles contraintes du problème (P)

• Le polyèdre K = { < 𝑎𝑖 , 𝑥 >≤ 𝑏𝑖 , i=1, … ,m} s’appelle ensemble des contrainte de (P)

• Les éléments x ∈ K s’appellent solutions admissibles de (P) et une solution 𝑥 de (P) s’appelle

solution optimale de (P)

• Soit A=(𝑎𝑖)1≤𝑖≤𝑚 la matrice de Mm,n formée des vecteurs lignes 𝑎𝑖 et soit b =

𝑏1⋮𝑏𝑚

, le polyèdre

des contrainte K s’écrit K={ x ∈ ℝn : 𝐴𝑥 ≤ 𝑏 } et le problème (P) s’écrit sous la forme générale :

𝑃 : 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 , 𝑥 >

𝐴𝑥 ≤ 𝑏

Remarque : Le problème de minimisation (P) est équivalent au problème de maximisation :

𝑃′ : 𝑚𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 < −𝑐 , 𝑥 >

𝐴𝑥 ≤ 𝑏

b) Théorème fondamental de la programmation linéaire

Théorème 1.2 :

(1) Si une forme linéaire atteint son minimum sur un polyèdre saillant de ℝn, alors le minimum est atteint

en un sommet de ce polyèdre.

(2) Si une forme linéaire est minorée sur un polyèdre de ℝn, alors elle atteint son minimum sur ce

polyèdre.

Démonstration:

(1) Soient c ϵ ℝn* et K={x ϵ ℝn : <ai . x> ≤ bi , i=1…m} un polyèdre, où ai ϵ ℝn* et bi ϵ ℝ, i=1…m.

Soient J⊂{1,…,m} et FJ={x ϵ K : <ai . x> = bi , i ϵ J} une face de K (F∅ = K) et montrons que si c n’est pas

constante sur FJ et atteins son minimum en un point x1 de FJ , alors il existe i ∉ J tel que x1 ϵFJ⋃{i} .

Supposons, par l’absurde, que <ai .x1> < bi , ∀ i ∉ J.

Soit x2 ϵ FJ tel que <c . x2 > > <c . x1 >. Posons v = x2 - x1 et

𝑡 = min

𝑏𝑖 −< 𝑎𝑖 . 𝑥1 >

< −𝑎𝑖 . 𝑣 > , 𝑖 ∉𝐽 𝑒𝑡 < 𝑎𝑖 . 𝑣 > < 0 𝑠𝑖 { 𝑖 ∉𝐽 𝑒𝑡 < 𝑎𝑖 . 𝑣 > < 0} ≠ ∅

𝑡 = 17 𝑠𝑖𝑛𝑜𝑛

On a par construction t > 0, x1 – tv ϵ FJ et <c . x1 – tv > =<c . x1 > - t<c . v > < <c . x1 >. Ceci contredit le

fait que le minimum est atteint au point x1.



Posons J0 =∅ , FJ0 = K et d = min{<c . x> , x ϵ FJ0

} . Soit 𝑥 ϵ FJ0 tel que <c . 𝑥 > =d.

D’après ce qui précède, si c n’est pas constante sur FJ0 , il existe i1 ∉ J0 tel que 𝑥 ϵ FJ0⋃{i1}

On pose J1 =J0 ⋃ {i1}. Si c n’est pas constante sur FJ1 , il existe i2 ∉ J1 tel que 𝑥 ϵ FJ1⋃{i2}

En procédant ainsi, on construit une suite K= FJ0 ⊃ FJ1

⊃ … ⊃FJk avec J0 ⊊J1 ⊊… ⊊Jk avec c constante sur

FJk (car le nombre de faces d’un polyèdre est fini). On a alors,

- ou bien FJk est un singleton, dans ce cas FJk

={ 𝑥 } est un sommet de K,

- ou bien admet FJk n’est pas un singleton, dans ce cas FJk

admet un sommet {𝑥 ′} (qui est également

un sommet de K) et on a <c . 𝑥 ′ > = <c . 𝑥 > =d.

L’assertion (2) est admise.



a) Forme standard d’un programme linéaire

La forme standard d’un PL est :

𝑃1 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0

La forme symétrique d’un PL est :

𝑃2 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >𝐴𝑥 ≤ 𝑏 𝑒𝑡 𝑥 ≥ 0

où c ϵ ℝn* , A ϵ Mm,n( ℝ) et b ϵ ℝn .

Proposition 1.3: Les formes générale, standard et symétrique d’un PL sont équivalentes.

Démonstration : On considère un PL écrit sous forme générale :

𝑃𝑔 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >

𝐴𝑥 ≤ 𝑏

avec c ϵ ℝn* , A ϵ Mm,n(ℝ) et b ϵ ℝn

Tout réel a s’écrit a= a’- a’’ avec a’ ≥0 et a’’ ≥0 (on peut prendre a’ =max (a, 0) et a’’ =max (-a,0))

Donc un point x ϵ ℝn s’écrit x= x’ – x’’ avec x’ ≥0 et x’’ ≥0 . Posons X=(x’ ; x’’) , on a ϵ ℝ2n et X ≥0 .

On a Ax= A(x’-x’’)=Ax’-Ax’’ . Posons 𝐴 =[A, -A] , on a 𝐴 ϵ Mm,2n(ℝ) et 𝐴 X=Ax.

On a <c.x> = <c. x’-x’’>=<c. x’> - <c. x’’> . Posons 𝑐 = (c, -c) , on a 𝑐 ϵ ℝ2n* et <𝑐 . X> =<c.x>

3- Algorithme du simplexe


Le PL général (Pg) est donc équivalant au PL symétrique :

𝑃𝑠𝑦𝑚 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 <𝑐 . X>𝐴 X ≤ 𝑏 𝑒𝑡 𝑋 ≥ 0

On considère maintenant un PL écrit sous forme symétrique:

𝑃2 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >𝐴𝑥 ≤ 𝑏 𝑒𝑡 𝑥 ≥ 0

avec c ϵ ℝn*, A ϵ Mm,n(ℝ) et b ϵ ℝn

Pour tout x ϵ ℝn , posons x’ = b -Ax, X=(x ; x’ ) ϵ ℝn+m , 𝐴 = [A , Im] ϵ Mm,n+m(ℝ), 𝑐 =(c,0m)où 0m est le vecteur ligne nul de ℝn* . On a pour tout x ϵ ℝn <𝑐 ,X> = <c.x> et :

𝐴𝑥 ≤ 𝑏 𝑒𝑡 𝑥 ≥ 0 ⇔ 𝐴 X = b et X ≥ 0.

Donc, le PL symétrique 𝑃2 est équivalant au PL standard:

𝑃𝑠𝑡𝑑 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 <𝑐 . X>𝐴 X = 𝑏 𝑒𝑡 𝑋 ≥ 0

On considère maintenant un PL écrit sous forme standard:

𝑃1 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0

avec c ϵ ℝn*, A ϵ Mm,n(ℝ) et b ϵ ℝn



Posons 𝐴 = [A , -A, -In] ϵ M2m+n,n(ℝ) , 𝑏 =(b;-b;0n)où 0n est le vecteur colonne nul de ℝn . On a pour tout x ϵ ℝn :

𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0 ⇔ 𝐴 x ≤ 𝑏 .

Donc, le PL symétrique 𝑃1 est équivalant au PL général:

𝑃𝑔 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 <𝑐 . x>

𝐴 x ≤ 𝑏

b) Caractérisation des sommets

On considère un PL en forme standard :

𝑃 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0

où c ϵ ℝn* , A ϵ Mm,n( ℝ) et b ϵ ℝm .

On peut toujours supposer, sans perte de généralité, que b ≥ 0, rang(A)=m et m<n .

Pour tout i ϵ {1,…,n}, Ai désigne le i ème vecteur colonne de A.

Posons K={x ϵ ℝn: 𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0} et pour tout x ϵ K, Ix= { i ϵ {1,…,n} : xi ≠0 } et Sx={Ai, i ϵ Ix }.

Remarque : On peut supposer que 0 ∉ K, sinon on a b=0 et par suite 0 est une solution de (P) si elle existe.

Proposition 2.3: Un point x de K est un sommet de K si et seulement si la famille Sx est libre.

Démonstration : voir TD



Soit x un sommet de K.

Il résulte de la proposition précédente que ⧣(Ix) ≤ m.

Si ⧣(Ix) = m, alors Sx est une base de ℝm . Dans ce cas x est dit sommet non dégénéré, Ix est noté βx et Sx est noté Bx

Si ⧣(Ix) < m, x est dit sommet dégénéré. On peut compléter Sx en une base de ℝm par des vecteurs colonnes de la matrice A. càd il existe Jx ⊂{1,…,n}\Ix tel que la famille Bx = { Ai, i ϵ βx}, avec βx= Ix⋃ Jx , est une base de ℝm .

Dans les deux cas βx ( resp. Bx) est dit ensemble de base (resp. base) associé à x.

Pour tout j ϵ {1,…,n} le vecteur Aj s’exprime d’une façon unique dans la base Bx sous la forme :

𝐴𝑗 = 𝛾𝑖𝑗𝐴𝑖

𝑖∈𝛽𝑥

On note 𝑧𝑗 = 𝑐𝑗 − 𝛾𝑖𝑗𝑐𝑖𝑖∈𝛽𝑥

. Les 𝑧𝑗 sont dits coûts marginaux.

Notons que si j ϵ βx , alors 𝛾𝑖𝑗 = 𝛿𝑖,𝑗 (symbole de Kronecker) et 𝑧𝑗= 0.

Le calcul des coefficients 𝛾𝑖𝑗 nécessite d’inverser la matrice Mx =( Ai )i ϵ βx

.



c) Algorithme du simplexe

Théorème 1.3 : Soit x un sommet de K, Bx et βx une base et un ensemble de base associé à x. et soit :

Pour tout j ∉ βx , soit 𝑧𝑗 = 𝑐𝑗 − 𝛾𝑖𝑗𝑐𝑖𝑖∈𝛽𝑥

où les 𝛾𝑖𝑗 sont donnés par : 𝐴𝑗 = 𝛾𝑖

𝑗𝐴𝑖𝑖∈𝛽𝑥

Une des trois alternatives suivantes a lieu:

(1) Si 𝑧𝑗 ≥ 0 ∀j ∉ βx , alors x est une solution de (P);

(2) Si J≝{ j ∉ βx , tel que 𝑧𝑗 < 0}≠ ∅ et si ∃𝑘ϵ J : 𝛾𝑖𝑘 ≤ 0 ∀i ϵ βx , alors (P) n’admet pas de solution ;

(3) Si ∀j ϵ J , ∃i ϵ βx : 𝛾𝑖𝑗 >0 , soit 𝑗+ ϵ J, on pose :

𝜃+ = min𝑥𝑖

𝛾𝑖𝑗+

, i ϵ βx et 𝛾𝑖𝑗+ > 0 . Soit 𝑗− ϵ βx tel que 𝛾𝑗−

𝑗+ > 0 et 𝜃+ = 𝑥𝑗−

𝛾𝑗− 𝑗+

et on considère le point 𝑥+ défini par :

𝑥+𝑖 = 𝑥𝑖 − 𝜃+𝛾𝑖𝑗+ 𝑠𝑖 i ϵ βx

𝑥+𝑗+ = 𝜃+

𝑥+𝑖 = 0 𝑠𝑖 i ∉ βx ⋃{𝑗+ }

𝑥+ est un sommet de K et β𝑥+

= ( βx \ { 𝑗− } )⋃{𝑗+ } est un ensemble de base associé à x.

De plus 𝜃+ >0 ⇔ 𝑥+ ≠ x et dans ce cas on a : <c . 𝑥+> < <c . x >.



Démonstration :

Soit x’ ϵ K , on a 𝐴𝑥′ = 𝑥′𝑗𝐴𝑗 =𝑛

𝑗=1 𝑥′𝑗 𝛾𝑖𝑗𝐴𝑖𝑖∈𝛽𝑥

= ( 𝑥′𝑗𝛾𝑖𝑗)𝑛

𝑗=1𝑖∈𝛽𝑥𝑛𝑗=1 𝐴𝑖

Or 𝐴𝑥 = 𝑥𝑖𝐴𝑖 = 𝐴𝑥′ = 𝑏 𝑒𝑡 𝑖∈𝛽𝑥

Bx est une base, donc 𝑥𝑖 = 𝑥′𝑗𝛾𝑖

𝑗 𝑛𝑗=1 ∀i ϵ βx

Par suite <c . x' > - <c . x> = 𝑥′𝑗𝑐𝑗 − 𝑛𝑗=1 𝑐𝑖𝑥𝑖𝑖∈𝛽𝑥

= 𝑥′𝑗𝑐𝑗 − 𝑐𝑖( 𝑥′𝑗𝛾𝑖𝑗 𝑛

𝑗=1 )𝑖∈𝛽𝑥𝑛𝑗=1

= 𝑥′𝑗𝑐𝑗 − 𝑛𝑗=1 𝑥′𝑗

𝑛𝑗=1 ( 𝛾𝑖

𝑗𝑐𝑖) =𝑖∈𝛽𝑥 𝑥′𝑗𝑛𝑗=1 𝑧𝑗 = 𝑥′𝑗𝑧𝑗j ∉ βx

(1) On a ∀ x’ ϵ K <c . x' > − <c . x> = 𝑥′𝑗𝑛𝑗=1 𝑧𝑗 ≥ 0 . Donc x est une solution de (P).

(2) Soit 𝑘ϵ J : 𝛾𝑖𝑘 ≤ 0 ∀i ϵ βx . Soit 𝜃 >0, on considère le point 𝑥𝜃 défini par :

𝑥𝜃𝑖 = 𝑥𝑖 − 𝜃 𝛾𝑖𝑘 𝑠𝑖 i ϵ βx

𝑥𝜃𝑘 = 𝜃

𝑥𝜃𝑖 = 0 𝑠𝑖 i ∉ βx ⋃{𝑘}

On a 𝑥𝜃 ≥ 0 𝑒𝑡 𝐴𝑥𝜃 = 𝑥𝜃𝑖𝐴

𝑖 =𝑛𝑖=1 𝑥𝑖𝐴

𝑖 − 𝜃 𝛾𝑖𝑘𝐴𝑖 + 𝜃𝐴𝑘 𝑖∈𝛽𝑥

= 𝐴𝑥 − 𝜃𝐴𝑘 + 𝜃𝐴𝑘 = 𝑏𝑖∈𝛽𝑥

Donc 𝑥𝜃ϵ K ∀𝜃 >0. On a , d’après ce qui précède :

< c . 𝑥𝜃> = <c . x> + 𝑥𝜃𝑖𝑛𝑖=1 𝑧𝑖 = <c . x> + 𝑥𝜃𝑖 𝑖∈𝛽𝑥

𝑧𝑖 +𝜃𝑧𝑘 = <c . x> +𝜃𝑧𝑘

Or 𝑧𝑘 <0, donc lim𝜃→+∞

< c . 𝑥𝜃> = −∞ . D’où (P) n’admet pas de solution.



(3) Montrer que 𝑥+ est un sommet de K revient à montrer que B𝑥+

est libre car I𝑥+⊂ β

𝑥+

Par l’absurde, supposons qu’il existe des réels αi , i ϵ β𝑥+

tels que α𝑖𝐴𝑖

i ϵ β𝑥+

= 0.

On a α𝑗+ ≠ 0, car sinon on aura α𝑖𝐴𝑖

i ϵ βx \ { 𝑗− } = 0 par suite αi =0 ∀i ϵ βx \ { 𝑗− }, on aura donc

αi =0 ∀i ϵ β𝑥+

.

𝐴𝑗+ = −

α𝑖

α𝑗+

i ϵ βx \ { 𝑗− }

𝐴𝑖 = 𝛾𝑖𝑗+ 𝐴𝑖

𝑖∈𝛽𝑥

= 𝛾𝑖𝑗+ 𝐴𝑖

i ϵ βx \ { 𝑗− }

+ 𝛾𝑗− 𝑗+ 𝐴𝑗

−

Donc 𝛾𝑗− 𝑗+ = 0, d’où la contradiction.

Il est claire que 𝜃+ >0 ⇔ 𝑥+ ≠ x et dans ce cas on a :

<c . 𝑥+> - <c . x > = 𝑥+𝑗𝑧𝑗j ∉ βx = 𝜃+𝑧𝑗+ < 0.



d) Initialisation de l’algorithme du simplexe

On considère un PL :

𝑃 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >

𝑥ϵ 𝐾

où K = 𝑥 ϵ ℝn ∶ 𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0 , c ϵ ℝn* , A ϵ Mm,n( ℝ) et b ϵ ℝm .

On associe à (P) le PL suivant :

𝑃0 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐0 .

𝑥

𝑣>

𝑥

𝑣ϵ 𝐾0

où 𝐾0 =𝑥𝑣 ϵ ℝn x ℝm: 𝐴0 𝑥

𝑣= 𝑏 𝑒𝑡 𝑥

𝑣≥ 0 , 𝐴0 𝑥

𝑣= 𝐴𝑥 + 𝑣, < 𝑐0 . 𝑥

𝑣> = 𝑣𝑖

𝑚𝑖=1 .

Théorème 2.3 :

(1) P0 admet une solution optimale;

(2) 0b

est un sommet de 𝐾0;

(3) Soit 𝑥 𝑣

un sommet optimal de P0 , on a:

– Si 𝑣 ≠ 0, alors (P) n’admet pas de solutions admissibles (K= ∅);

– Si 𝑣 =0, alors 𝑥 est un sommet de K .



Démonstration :

(1) On a < 𝑐0 . 𝑥𝑣> = 𝑣𝑖

𝑚𝑖=1 ≥ 0 ∀ 𝑥

𝑣 ϵ 𝐾0 . Donc 𝑐0 est minorée sur 𝐾0. Par suite, d’après le

théorème fondamental de la PL, P0 admet une solution optimale.

(2) On a 𝐴0 0𝑏= 𝑏 𝑒𝑡 0

𝑏≥ 0, donc

0𝑏

est une solution admissible de P0 . De plus on a :

𝑆 0𝑏 est inclus dans la base canonique de ℝm , donc 𝑆 0

𝑏 est libre par suite

0𝑏

est un sommet de 𝐾0,

(3) - Si 𝑣 ≠ 0 et K ≠ ∅ , soit x ϵ K, on a 𝑥0

ϵ 𝐾0 et < 𝑐0 . 𝑥0> 0 < < 𝑐0 . 𝑥

𝑣 > , ce qui est absurde.

- Si 𝑣 = 0, on a 𝐴0 𝑥 0

=A𝑥 =b et 𝑥 ≥ 0, par suite 𝑥 ϵ K. De plus, on a :

𝐼 𝑥 0

= 𝐼𝑥 ≝ { i ϵ {1,…,n} : xi ≠0 }, par suite 𝑆 𝑥 0

= Sx≝{Ai, i ϵ 𝐼𝑥 } est une famille libre de ℝm.

Donc, d’après la proposition 2.3, 𝑥 est un sommet de K.



a) Forme canonique

On considère un PL :

𝑃 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 > +𝑑

𝑥ϵ 𝐾

où K = 𝑥 ϵ ℝn ∶ 𝐴𝑥 = 𝑏 𝑒𝑡 𝑥 ≥ 0 , c ϵ ℝn* , A ϵ Mm,n( ℝ) et b ϵ ℝm , d ϵ ℝ .

Le programme (P) est dit canonique si que b ≥ 0, rang(A)=m, m<n et :

• Bc ⊂ {Ai, i =1,…,n} où Bc ={ei , i =1,…,m} est la base canonique de ℝm ;

• ci =0 pour tout i ϵ {1 , …, n} tel que Ai ϵ Bc .

Les indices j tels que Aj ϵ Bc s’appellent indices canoniques.

On définit une application col :{1,…,m} {1,…,n} par j=col(i) si Aj = ei

Remarque : Si (P) est canonique, alors le point x défini par : xj = bi si j est canonique j = col(i) et xj =0 sinon, est un sommet de K associé à la base Bc. De plus, on a:

• 𝛾𝑖𝑗 = 𝑎𝑘

𝑗 avec i =col(k) ;

• 𝑧𝑗 = 𝑐𝑗 ;

• <c.x> = 0.

4- Pratique de la méthode du simplexe


On associe à (P) le tableau suivant qui représente toutes ses données :



𝑎11 … 𝑎1

𝑛 𝑏1

⋮ ⋮ ⋮ ⋮

𝑎𝑚1 … 𝑎𝑚

𝑛 𝑏𝑚

𝑐1 … 𝑐𝑛 d

(T)

b) Opération pivotage

Soit 𝑎𝑟𝑠 un terme de la matrice A tel que 𝑎𝑟

𝑠 ≠ 0. On effectue sur (T) les opérations suivantes :

• on divise la ligne Tr par 𝑎𝑟𝑠 : 𝑎′𝑟

𝑠=

𝑎𝑟𝑗

𝑎𝑟𝑠 , j=1…n et 𝑏′𝑟 =

𝑏𝑟

𝑎𝑟𝑠 ;

• pour i≠r et i≠m+1, à la ligne Ti on retranche 𝑎𝑖𝑠

𝑎𝑟𝑠Tr : 𝑎′𝑖

𝑗=𝑎𝑖

𝑗 −𝑎𝑖𝑠

𝑎𝑟𝑠 𝑎𝑟

𝑗 , j=1…n et 𝑏′𝑖 = 𝑏𝑖 −𝑎𝑖𝑠

𝑎𝑟𝑠 𝑏𝑟 ;

• au vecteur ligne c on retranche 𝑐𝑠


: 𝑐′𝑗=𝑐𝑗 −𝑐𝑠


𝑗 , j = 1…n ;

• à la constante d on ajoute 𝑐𝑠

𝑎𝑟𝑠 𝑏𝑟

: d’=d+

𝑐𝑠

𝑎𝑟𝑠 𝑏𝑟

.

Remarque : Les transformations effectuées ne modifient pas le problème (P). En effet, on passe du

système Ax=b à un système équivalent A’x=b’ et la fonction objectif ne change pas : <c.x>+d=<c’.x>+d’.

Si T est canonique et b’≥0, alors le nouveau tableau T’ est canonique.



b) Exemple

On considère le programme linéaire :

(𝑃)

𝑚𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 (𝑥1 + 3𝑥2)−𝑥1 + 𝑥2 ≤ 4 𝑥1+ 3𝑥2 ≤ 24 𝑥1 ≤ 64𝑥1 + 3𝑥2 ≥ 12𝑥1 ≥ 0, 𝑥2 ≥ 0

(1) Standardisation : Le problème (P) s’écrit sous la forme standard :

(𝑃)

𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 (−𝑥1 − 3𝑥2) −𝑥1 + 𝑥2 + 𝑥4 = 4

𝑥1+ 3𝑥2 +𝑥5 = 24 𝑥1 +𝑥6 = 6 4𝑥1 + 3𝑥2 − 𝑥3 = 12

𝑥𝑖 ≥ 0, 𝑖 = 1,… , 6



(2) Initialisation (phase 1) : Puisque la matrice A comprend 3 vecteurs canoniques, il a suffit de rajouter

une seule variable (𝑥7) pour initialiser le problème. On associe à (P) le problème initial (P0) :

(𝑃0)

𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 (𝑥7) −𝑥1 + 𝑥2 + 𝑥4 = 4

𝑥1+ 3𝑥2 + 𝑥5 = 24 𝑥1 +𝑥6 = 6 4𝑥1 + 3𝑥2 − 𝑥3 + 𝑥7 = 12

𝑥𝑖 ≥ 0, 𝑖 = 1, … , 6

(3) Formation du tableau initial : On associe à (P0) le tableau suivant :

T0 1 2 3 4 5 6 7 b

1 -1 1 0 1 0 0 0 4

2 1 3 0 0 1 0 0 24

3 1 0 0 0 0 1 0 6

4 4 3 -1 0 0 0 1 12

c -1 -3 0 0 0 0 0 0

c0 0 0 0 0 0 0 1 0



(4) Canonisation : Les indices 4,5 et 6 sont canoniques mais l’indice j=7 n’est pas canonique ( c70 ≠ 0) .

Pour le rendre canonique, on retranche a4 à c0 et on ajoute b4 à d. On obtient le tableau suivant :

(5) Traitement du tableau (T0,1)

• Sommet : x0,1 = (0; 0; 0; 4; 24; 6; 12) , base associée βx0,1= (4, 5, 6, 7) ;

• Test d’optimalité : x0,1 n’est pas optimal, car c10 < 0;

• Premier critère de Dantzig : l’indice entrant j+ = 1;

• Deuxième critère de Dantzig : l’indice sortant j- = 7;

• Opération pivotage (4,1).

T0,1 1 2 3 4 5 6 7 b

1 -1 1 0 1 0 0 0 4

2 1 3 0 0 1 0 0 24

3 1 0 0 0 0 1 0 6

4 4 3 -1 0 0 0 1 12

c -1 -3 0 0 0 0 0 0

c0 -4 -3 1 0 0 0 0 12

βx

4

5

6

7

𝑥𝑖 𝛾𝑖𝑗

-

24

6

3



(6) Traitement du tableau (T0,2)

• Sommet : x0,2 = (3; 0; 0; 7; 21; 3; 0) , base associée βx0,2 = (1,4, 5, 6) ;

• Test d’optimalité : x0,2 est optimal (fin de la phase1 );

• (P) admet des solutions admissibles (car d=0 ).

T0,2 1 2 3 4 5 6 7 b

1 0 7/4 -1/4 1 0 0 -1/4 7

2 0 9/4 1/4 0 1 0 1/4 21

3 0 -3/4 1/4 0 0 1 1/4 3

4 1 3/4 -1/4 0 0 0 -1/4 3

c 0 -9/4 -1/4 0 0 0 -1/4 -3

c0 0 0 0 0 0 0 1 0

βx

4

5

6

1



Phase 2:

(7) Traitement du tableau (T1) : (T1 =T0,2 auquel on supprime la ligne c0 et la colonne de la variable 7 )

• Sommet : x1 = (3; 0; 0; 7; 21; 3) , base associée βx1 = (1,4, 5, 6) ;

• Test d’optimalité : x1 n’est pas optimal, car c2 < 0 ;




T1 1 2 3 4 5 6 b

1 0 7/4 -1/4 1 0 0 7

2 0 9/4 1/4 0 1 0 21

3 0 -3/4 1/4 0 0 1 3

4 1 3/4 -1/4 0 0 0 3

c 0 -9/4 -1/4 0 0 0 -3

βx

4

5

6

1


4

28/3

-

4



(8) Traitement du tableau (T2)






T2 1 2 3 4 5 6 b

1 -7/3 0 1/3 1 0 0 0

2 -3 0 1 0 1 0 12

3 4/3 0 1249

900

0 0 1 6

4 3 1 -1/3 0 0 0 4

c 0 0 -1 0 0 0 -12

βx

4

5

6

2


0

12

5400

1249

-









T3 1 2 3 4 5 6 b

1 -7 0 1 3 0 0 0

2 4 0 0 -3 1 0 12

3 1 0 0 -1249

300

0 1 6

4 -1 1 0 1 0 0 4

c -4 0 0 3 0 0 -12

βx

3

5

6

2


-

3

6

-





• Test d’optimalité : x4 est optimal ;

• Coût optimal = -24 .

T4 1 2 3 4 5 6 b

1 0 0 1 -9/4 5/4 0 21

2 1 0 0 -3/4 ¼ 0 3

3 0 0 0 3/4 -1/4 1 3

4 0 1 0 1/4 1/4 0 7

c 0 0 0 0 1 0 -24

βx

3

1

6

2

5- Dualité en programmation linéaire


Définition : Etant donné un PL sous forme symétrique :

𝑃 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑐 . 𝑥 >𝐴𝑥 ≤ 𝑏 𝑒𝑡 𝑥 ≥ 0

où c ϵ ℝn*, A ϵ Mm,n( ℝ) et b ϵ ℝm .

On appelle dual de (P) le PL défini par :

𝐷 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 < 𝑏′ . 𝑦 >

−𝐴′𝑦 ≤ 𝑐′𝑒𝑡 𝑦 ≥ 0

où A’ , b’ et c’ sont respectivement les transposés de A, b et c .

Il est claire que (D) est également sous forme symétrique et que le dual (D) est (P).

Théorème 1.5 : Soient 𝑥 ∈ 𝐾 = 𝑥 ∈ ℝn: 𝐴𝑥 ≤ 𝑏 𝑒𝑡 𝑥 ≥ 0 𝑒𝑡 𝑦 ∈ 𝐾′ = 𝑦 ∈ ℝm: − 𝐴′𝑦 ≤ 𝑐′ 𝑒𝑡 𝑦 ≥ 0

(1) Les propositions suivantes sont équivalentes :

i. 𝑥 et 𝑦 sont des solutions de (P) et (D)respectivement;

ii. (𝑥 . c’+A’𝑦 )=0 et (𝑦 . b-A𝑥 ) =0 (conditions de complémentarité);

iii. <c. 𝑥 >+<b’. 𝑦 > =0.

(2) Les propositions suivantes sont équivalentes :

i. (P) admet une solution;

ii. (D) admet une solution;

iii. K et K’ ne sont non vides.



Exemple: Un entrepreneur transforme 3 produits P1 , P2 et P3 dans deux ateliers A1 et A2 .

La fabrication d’une unité de P1 (resp. P2 , P3 ) demande 1 heure de travail dans l’atelier A1 et 1 heure

dans l’atelier A2 (resp. 4h, 1h sur A1 et 1h , 5h sur A2) et rapporte un bénéfice de 1 UM (resp. 2 UM , 2

UM).

Les unités A1 et A2 ne peuvent pas fonctionner plus de 15 heures et 6 heures par jour respectivement.

Le problème de l’entrepreneur est de déterminer les quantités des produits P1 , P2 et P3 à transformer de

sorte à maximiser le bénéfice.

Un intermédiaire propose à l’entrepreneur de lui louer ses unités pour réaliser la transformation à sa place.

Pour que l’ entrepreneur accepte l’offre, le prix de location doit se faire sur la base de l’horaire limite de

fonctionnement des deux unités et les prix unitaires de location doivent être plus intéressants que les

bénéfices réalisés sur chaque unité des produits transformés.

Le problème de l’intermédiaire est de déterminer les prix unitaires de location des unités A1 et A2 de sorte

à minimiser le coût de location.

A1 A2 Bénéfice unitaire

P1 1 h 1 h 1 UM

P2 4 h 1 h 2 UM

P3 1 h 5 h 2 UM

Durée maximale 15 h 6 h



Formulation des problèmes:

Soient x1 , x2 et x3 respectivement les quantités des produits P1, P2 et P3 à fabriquer par jour.

Le problème de l’entrepreneur est 𝑃

𝑚𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 (𝑥1 + 2𝑥2 + 2𝑥3)𝑥1 + 4𝑥2+𝑥3 ≤ 15𝑥1 + 𝑥2+4𝑥3 ≤ 6𝑥1, 𝑥2 , 𝑥3 ≥ 0

Soient y1 et y2 respectivement les prix de location de l’heure des ateliers A1 et A2.

Le problème de l’intermédiaire est 𝐷

𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟(15𝑦1 + 6𝑦2)𝑦1 + 𝑦2≥ 14𝑦1 + 𝑦2≥ 2𝑦1 + 4𝑦2≥ 2𝑦1, 𝑦2 ≥ 0

Résolution des problèmes:

On remarque que le problème de l’intermédiaire est dual du problème de l’entrepreneur.

Le problème (D) à deux variable, sa résolution graphique montre que 𝑦 = (1/3 ; 2/3) est une solution optimale (D) et le coût de location est de 9 UM par jour. Cette solution sature les deux premières contraintes. D’après le théorème de dualité (P) admet une solution optimale.Les conditions de complémentarité s’écrivent :

𝑥1 + 4𝑥2+𝑥3 = 15 𝑥1 + 𝑥2+4𝑥3 = 6 𝑥3 = 0

La solution optimale de (P) est donc 𝑥 = (3; 3; 0) et le bénéfice réalisé par jour est de 9 UM

Documents

Cours du module Recherche Opérationnelle