Recherche Opérationnelle 2 ème Année Gestion industrielle Année universitaire : 2009 - 2010 Responsable du cours : Rim Larbi [email protected]

Recherche Opérationnelle

2ème Année Gestion industrielle

Année universitaire : 2009 - 2010

Responsable du cours : Rim [email protected]

Plan du cours

Introduction à la recherche opérationnelle

Partie 1 : Programmation Linéaire Chapitre 1 : Introduction à la programmation

linéaire Chapitre 2 : Résolution d’un programme linéaire :

méthode de simplexe Chapitre 3 : Dualité et analyse de sensibilité dans

la programmation linéaire

Plan du cours

Partie 2 : Graphes Chapitre 1 : Notions fondamentales sur les

graphes Chapitre 2 : Problème du plus court chemin Chapitre 3 : Problème de planification de projets

Introduction à la Recherche Opérationnelle

Introduction à la RO Origines de la RO

- Période : 2ème guerre, - Responsable : armée britannique - Problèmes posés : implantation optimale de radars de

surveillance , le management des bombardements anti sous-marins opérations de miniers…

RO = Application des mathématiques et des méthodes scientifiques aux opérations militaires

RO = Approche scientifique à la prise des décisions, qui cherche à

déterminer comment concevoir et faire fonctionner un système d’une façon optimale

Introduction à la RO Techniques de la RO

La programmation mathématique programmation linéaire programmation quadratique programmation en nombres entiers programmation dynamique

Analyses de réseaux et graphes Théories des files d’attentes Simulation Analyse statistique

Champs d’application de la RO- Industries- Gouvernement- Agences- Hôpitaux- Institutions d’éducation…

Introduction à la RO Méthodologie de la RO

(1) Identification du problème

(2) Collecte des données

(3) Modélisation (Formulation

mathématique)(4) Vérification du modèle

(5) Recherche des solutions

(6) Présentation des solutions

(7) Implémentation et recommandations

Partie 1

Programmation Linéaire

Chapitre 1

Introduction à la programmation linéaire

Chapitre 1 Introduction à la PL

La programmation linéaire = méthode permettant d’optimiser, c'est-à-dire rendre le plus grand ou le plus petit possible, une fonction linéaire, cela sous certaines contraintes définies par des inégalités.

Les exemples habituels d’optimisation sont la recherche d’un bénéfice maximal ou d’un coût minimal.

Remarque : C’est grâce à cette méthode que les problèmes de ravitaillement étaient résolus pendant la seconde guerre mondiale.

Chapitre 1 Introduction à la PL Exemple Une compagnie est spécialisée dans la production de deux types de

produits : des climatiseurs et des ventilateurs. Les deux produits nécessitent un certain nombre d’heures de main d’œuvre. Le tableau suivant donne les informations nécessaires sur les deux produits, c’est-à-dire les nombres d’heures machine et d’heures main d’œuvre nécessaires à la fabrication d’une unité de chacun de ces produits, ainsi que le profit généré par la production d’une unité de ce produit. Le tableau nous donne aussi le nombre total d’heures machines et d’heures main d’œuvre disponibles.

Heures machine

Main d’œuvre Profit

Climatiseur 2 h/unité 3 h/unité 25 DT/unité

Ventilateur 2 h/unité 1 h/unité 15 DT/unité

Total disponible 240 h 140 h


I. Formulation du programme linéaire

a) Variables de décision : doivent complètement décrire les décisions à prendre.

La compagnie veut décider du nombre de climatiseurs et du nombre de ventilateurs à produire pour maximiser le profit. Ceci nous amène à choisir les deux variables de décision suivantes :

x1 = nombre de climatiseurs

x2 = nombre de ventilateurs


b) Fonction objectif : dans n’importe quel programme linéaire, le responsable de décision veut maximiser (en général, le revenu ou profit) ou minimiser (en général le coût) une fonction des variables de décisions. Cette fonction est appelée “ fonction objectif ”.

L’objectif de l’entreprise est de déterminer le programme de production qui maximisera son profit (Z=profit). La fonction objectif s’écrit alors:

Max Z = 25x1 + 15x2


c) Contraintes du modèle : La limitation des ressources contraint l’entreprise de la manière suivante :

1) Contraintes heure machine 2x1 + 2x2 ≤ 240

2) Contrainte main d’œuvre 3x1 + x2 ≤ 140

3) Contraintes de non-négativité (exprimant que les niveaux d’activité ne peuvent être négatifs) x1 ≥ 0, x2 ≥ 0

Modèle complet : x1 = nbre de climatiseurs, x2 = nbre de ventilateurs

Max Z = 25 x1 + 15 x2

s.c. 2x1 + 2x2 ≤ 240

3x1 + x2 ≤ 140

x1 ≥ 0, x2 ≥ 0

s.c = sous contraintes


Domaine réalisable et solutions optimales : Ce sont deux concepts fondamentaux associés avec un PL. Pour les définir, on va utiliser le terme point (x1,x2), qui désigne une spécification de la valeur de chaque variable de décision.

Le domaine réalisable (DR) est l’ensemble de tous les points satisfaisant toutes les contraintes du PL. Dans notre exemple, le point (20,40) (Z= 280) appartient au DR. Ce point est dit réalisable.

Pour un problème de maximisation (min), une solution optimale est un point du DR qui donne la valeur la plus large (faible) de la fonction objective.

(20, 40) ≠ solution optimale car (10, 110) est réalisable et donne Z = 1900meilleur profit que Z= 280


II. Résolution graphique Méthode de résolution d’un PL ne comportant que 2 variables

de décision

Etapes à suivre• Représenter les lignes des contraintes et l’ensemble du

domaine réalisable• Localiser la solution optimale• Calculer la solution optimale


1ère étape : domaine réalisable(PL) Max Z = 25 x1 + 15 x2

s.c. 2x1 + 2x2 ≤ 240

3x1 + x2 ≤ 140

x1 ≥ 0, x2 ≥ 0Domaine réalisable


2ème étape : Recherche de la solution optimale(PL) Max Z = 25 x1 + 15 x2

La fonction objectif Z = 25x1 + 15x2 représente pour Z fixé (25x1 + 15x2 = cte) l’équation des courbes de niveau (des droites de pente -5/3) qu’on appelle aussi ligne d’isoprofit ou isocoût.

Maximiser Z revient à déplacer la ligne d’isoprofit dans la direction qui augmente la valeur de Z (pour un pb de maximisation). La dernière ligne qui touche le DR définit la plus large valeur de toutes les solutions réalisables, et contient la solution optimale


2ème étape : Recherche de la solution optimale (suite)

Solution optimale

{B} = D ∩ D’

D

D’


3ème étape : Calcul de la solution optimale

Solution optimale{B} = D ∩ D’ d’équations respectives:

2x1 + 2x2 = 240

3x1 + x2 = 140

Donc x1=10, x2=110 et Z*=1900

D

D’

Chapitre 1 Introduction à la PLIII.Notions de convexité et points extrêmes

Définition : Un ensemble E non vide est dit convexe si et seulement si pour tout élément x et y de E et pour tout λ Є [0,1], λ x + (1- λ ) y Є E.

Pour toute paire de points P1 et P2, l’ensemble des points qui forment le segment [P1P2] appartient au demi-plan.

Caractéristique d’un PL: le DR d’un PL est ou bien vide ou convexe.

Convexes Non convexes


Définition: E, un ensemble convexe, un point P dans E est appelé point extrême si chaque segment de droite entièrement contenu dans S et contenant le point P, a P comme extrémité.

Mathématiquement :

Soit x Є E, x est un point extrême ↔ S’il Ǝ y Є E, z Є E et 0<λ<1 tels que x= λy + (1- λ)z alors x=y=z

x n’est pas un point extrême

x

a,b Points extrêmes

a

b

y

y Point extrême

Chapitre 1 Introduction à la PLThéorème: Pour un PL donné, si un optimum existe, au moins un point extrême est optimal.

Corollaire: Si PL admet un optimum unique, alors cet optimum doit être un point extrême.

IV.Cas particuliers de PL

PL non borné Max Z = x1 + 2x2

s.c. 7x1+2x2 ≥ 28

x1 + 6x2 ≥ 12

x1 ≥ 0, x2 ≥ 0


x1+6x2 = 127x1+2x2 = 28

2

14

12

Si la fonction objectif est min z = x1 + 2x2 (18/5, 7/5) est optimal.

Lignes d’isoprofit

Chapitre 1 Introduction à la PLPL a une infinité de solutions optimales

Max Z = x1 + 3x2

s.c. 2x1+6x2 ≤ 30 (1)

x1 ≤ 10 (2)

x2 ≤ 4 (3)

x1 ≥ 0, x2 ≥ 0

Tous les points appartenant à [AB] sont optimaux

Chapitre 1 Introduction à la PLPL non réalisable

Max Z = 3x1 + 2x2

s.c. x1+2x2 ≤ 2 (1)

2x1 + 4x2 ≥ 8 (2)

x1 ≥ 0, x2 ≥ 0

DR vide PL non réalisable

Chapitre 2

Résolution d’un programme linéaire : méthode de simplexe

Chapitre 2 Méthode de simplexe

I. Introduction

Dans le chapitre précédent, on a vu comment résoudre graphiquement un PL à deux variables. Or la majorité des problèmes réels ont plusieurs variables. D’où la nécessité d’avoir une méthode algébrique pour résoudre des PLs ayant plus que 2 variables.

La méthode de Simplexe est l’une des méthodes les plus anciennes (Dantzig, 1947), et la plus utilisée jusqu’à nos jours, pour résoudre même des problèmes de grandes tailles avec quelques milliers de variables et quelques milliers de contraintes.


II.Mise en forme standard

Un PL peut avoir des contraintes d’égalité (=) et des contraintes d’inégalité ( ≥ et ≤ ).

Avant l’application de Simplexe, le PL doit être converti en un PL équivalent où :- toutes les contraintes sont des égalités, - toutes les variables sont non négatives (≥ 0), - le second membre est non négatif (AX ≤ b, b≥0).

Un tel PL est dit sous la forme standard.


Exemple : Usine de ceintures

Une usine fabrique de 2 sortes de ceintures : luxe et standardChaque type demande 1m2 de cuir• Une ceinture standard demande 1h de travail• Une ceinture de luxe demande 2h

Chaque semaine, on dispose de 40m2 de cuir et de 60h de travail.• Chaque ceinture standard rapport 3 Euros• Chaque ceinture de luxe 4 Euros.

Objectif : Maximiser le profit.

Chapitre 2 Méthode de simplexe x1 = nombre de ceintures de luxe produites par semaine x2 = nombre de ceintures standard produites par semaine

Maximiser z = 4x1 + 3x2, avec

x1 + x2 40 contrainte sur le cuir (1)

2x1 + x2 60 contrainte sur le travail (2)

x1, x2 0 contrainte de signe (3)

Chapitre 2 Méthode de simplexe Pour convertir la ième contrainte en une contrainte d’égalité, on définit la variable d’écart, si (slack variables) qui représente la quantité de ressource non utilisée dans cette contrainte.

s1 = 40 - x1 - x2 x1 + x2 + s1 = 40

On doit ajouter s1 ≥ 0 pour que (x1 , x2) satisfasse x1 + x2 40.

Pour une contrainte ≥, on définit ei (excess variable), variable d’excédent, qui est aussi ≥ 0.

On obtient alors:max z = 4x1 + 3x2s.c. x1 + x2 + s1 = 40

2x1 + x2 – e1 = 60x1, x2, s1, e1 0

Chapitre 2 Méthode de simplexe Remarque : L'impact de ces variables d'écart sur la fonction objectif est nul. Ceci explique le fait que leur existence soit tout simplement liée à une mise en forme du programme linéaire initial.

En général, la mise en forme d’un PL donne :

),...2,1(,0

...

...

.....nxnc...2x2c1x1cmaxZ

2211

22222121

11212111

nix

bxaxaxa

bxaxaxa

bxaxaxacs

i

mnmnmm

nn

nn

…


On définit A = (ai j), ; ;

On suppose que n m

(PL) : Max ct xs.c. Ax = b x ≥ 0

Rq : pour avoir la forme standard, les équations doivent, si nécessaire, être multipliées par (-1) pour avoir b 0

nx

x

x

x

2

1

mb

b

b

b

2

1

nc

c

c

c

2

1


III. Analyse algébrique de la méthode de simplexe

1. Variables de base• On appelle Base une sous matrice régulière de A. Il faut que la matrice A(m,n) soit de rang m (pas de contrainte (ou équation) redondante càd inutile).

• Une solution de base est obtenue en posant n − m variables égales à 0, et en résolvant pour les m variables restantes, qui sont les variables de base (VB).

• Les n−m variables à 0 sont les variables hors base (VHB).

• Des choix différents de VHB donnent lieu à des différentes solutions de base.


Représentation

xtB xt

H

ctb ct

H

B

base

H

hors base

m colonnes n − m colonnes


Représentation matricielle xB

A = [B | H] , x = , ct = [ctB| ct

H]

xH

• Ce qui donne

Z = ct x = ctB xB + ct

H xH

Ax = b B xB + H xH = b

Une solution de base est telle que

xH = 0

BxB = b

xB = B−1b


Exemple Soit le système suivant :

x1 + x2 = 3

−x2 + x3 = −1

Si on pose VHB = {x3}, alors VB = {x1, x2}. On résout

x1 + x2 = 3

−x2 = −1

Ce qui donne x1 = 2 et x2 = 1.

Certains choix de variables peuvent ne pas générer de solution de base.


2. Solutions de base réalisables

Une solution de base est dite réalisable (SBR) si :

xB = B−1b ≥ 0

Si le vecteur xB contient des termes nuls, on dira que cette solution est une solution de base dégénérée (peut être associée à plus qu’une base).


Exemple de SBR Soit le problème : min − x1 − 2x2

s.c. x1 + 2x2 ≤ 4

2x1 + x2 ≤ 5

x1 , x2 ≥ 0

Sous forme standard, on a: min − x1 − 2x2

s.c x1 + 2x2 + x3 = 4

2x1 + x2 + x4 = 5

x1 , x2 , x3 , x4 ≥ 0

4 variables (n=4) et 2 contraintes (m=2)


(PL) : min − x1 − 2x2 s.c x1 + 2x2 + x3 = 4

2x1 + x2 + x4 = 5 x1 , x2 , x3 , x4 ≥ 0

On peut essayer de constituer une base en utilisant l’ensemble B = {1, 3},

B = [A1A3] = 1 1 H = [A2A4] = 2 0 2 0 1 1

xB = x1 , xH = x2x3 x4

L’inverse de B existe, donc B correspond à une base B−1 = 0 1/2

1 −1/2

1 2 1 0

2 1 0 1A =

Chapitre 2 Méthode de simplexe La solution de base correspondante est donc :

xB = B−1b = 0 1/2 4 = 5/2 = x1 > 0

1 −1/2 5 3/2 x3

Cette solution est bien une SBR.

Chapitre 2 Méthode de simplexe3. Conditions d’optimalité d’une SBR

Soit x une SBR associée à la base B. On a alors

Soit x une solution réalisable quelconque de P.

On a z(x)= c x et z(x) = cx = cB B-1 b.

Calculons z(x) - z(x)

On a b=Ax ; Par conséquent :

z(x) - z(x) = c x-cx = cx - cB B-1 b = cx - cB B-1 Ax = (c – cB B-1 A)x

Appelons (x) = (c - cB B-1 A), alors z(x) - z(x) = (x). x

B1

H

xB b

xx0


Théorème : Soit x une SBR de P. (x) 0 x est optimal.

Démonstration

Rq: Pour simplifier la notation, nous allons utiliser la notation au lieu de (x)

Soit x une solution réalisable de P. z(x) peut s’écrire : z(x) = cB B-1 b + . x = z(x) + . x

0 z(x) z(x), puisque x 0.

Ceci est vrai x solution réalisable; d'où x est optimal.

Rq : c’est une condition suffisante. Elle devient aussi nécessaire si la SBR est non dégénérée.


4. Théorèmes fondamentaux

Théorème : La région réalisable pour tout problème de programmation linéaire est un ensemble convexe. Si un PL possède une solution optimale, alors un point extrême de la région réalisable doit être optimal.

Théorème : Pour tout LP, il existe un point extrême unique de la région réalisable qui correspond à chaque solution de base réalisable. Egalement, il existe au moins une SBR qui correspond à chaque point extrême de la région réalisable.


Illustration des théorèmesOn reprend l’exemple des ceintures de cuir, c-à-d maximiser z, avec :

z = 4x1 + 3x2

x1 + x2 + s1 = 40

2x1 + x2 + s2 = 60

x1, x2, s1, s2 ≥ 0


On a l’équivalence entre SBR et points extrêmes suivants :

Base Hors-base SBR Point extrêmex1, x2 s1, s2 s1 = s2 = 0, x1 = x2 = 20 Ex1, s1 x2, s2 x2 = s2 = 0, x1 = 30, s1 = 10 Cx1, s2 x2, s1 x2 = s1 = 0, x1 = 40, s2 = −20 Non réalisable, s2 < 0x2, s1 x1, s2 x1 = s2 = 0, s1 = −20, x2 = 60 Non réalisable, s1 < 0x2, s2 x1, s1 x1 = s1 = 0, x2 = 40, s2 = 20 Bs1, s2 x1, x2 x1 = x2 = 0, s1 = 40, s2 = 60 F


5. Nombre de solutions possibles Le nombre de bases candidates est égal à

Cmn = n!/((n−m)!m! )

Le nombre de SBR est donc ≤ Cm

n c-à-d fini, mais peut être très large.

Puisque le nombre de telles bases peut être très large, il est pratiquement impossible de trouver la solution optimale à partir d’une formule compacte.

il nous faut donc utiliser un algorithme systématique (procédure itérative) de recherche.


Définition d’un algorithme Un algorithme est un ensemble de règles employées pour obtenir des

résultats à partir de données spécifiques, dans lequel chaque étape est bien définie et peut être traduite sous forme d’un programme

informatique.

Simplexe Le simplexe est un algorithme ou méthode de recherche qui garantit de

trouver un optimum d’un PL (s’il existe) en un nombre fini d’itérations.


IV. Méthode de simplexe1. Principe

L’algorithme du simplexe pour une maximisation suit les étapes suivantes :

1.Trouver une SBR pour le PL, appelée la SBR initiale.

2. Déterminer si la SBR courante est optimale (Δ ≤ 0). Sinon, trouver une autre SBR qui possède une valeur z plus élevée.

3. Retourner au point (2) avec la nouvelle SBR comme SBR courante.

La question est donc : comment se déplacer.


2. Tableau canonique

(PL) : Max z = ct x comme on a :s.c. Ax = b

x ≥ 0

xB

A = [B | H] , x = , ct = [ctB| ct

H]

xH

Le PL peut ainsi s’écrire comme suit :

B xB + 0 (-z) + H xH = b

cB xB + (- z) + c xH = 0

Chapitre 2 Méthode de simplexe Sous forme matricielle on aura :

Sous forme d’un tableau, le PL peut être présenté comme suit :

B

B HH

xB 0 H b

zc 1 c 0

x

0cH1cB

bH0B

xH-zxB

2ème membre1er membre

Chapitre 2 Méthode de simplexe Le tableau canonique relatif à la base B est obtenu en transformant

la matrice sous les variables xB et –z en une matrice identité d’ordre m+1.

Pour ce faire, on multiplie à gauche chaque colonne du tableau par la matrice :

0cH1cB

bH0B

xH-zxB

2ème membre

1er membre

1

0

1

0

1

111

Bc

B

c

B

BB

Chapitre 2 Méthode de simplexe Le tableau canonique relatif à B est donc le suivant :

où B-1b 0.

On rappelle que : Δ = c - cB B-1 A et peut être aussi partitionnée en ΔB et ΔH selon la SBR x

On aura alors : = (B H) = (cB – cB B-1B cH – cB B-1H)

= (0 cH – cB B-1H)

xB -z xH

I 0 B-1H B-1b

0 1 cH – cB B-1H – cB B

-1b


Soient ,

Notons par : et

m

B

x

x

x

x2

1

n

m

m

H

x

x

x

x

2

1

jm

j

j

jm

j

j

a

a

a

B

a

a

a

,

,2

,1

1

,

,2

,1

jm

j

j

jm

j

j

b

b

b

B

b

b

b

,

,2

,1

1

,

,2

,1

Chapitre 2 Méthode de simplexe Notre tableau canonique devient ainsi :

Variables de base

x1 …xm -z xm+1 … xn Valeurs des var de base

x1

.

.xm

1 … 0 0 a1,m+1 …

a1,n

0 … 1 0 am,m+1 …

am,n

b1

.

.bm

-z 0 … 0 1 m+1 …

n

– cB B-1b

Chapitre 2 Méthode de simplexe3. Itérations de Simplexe Définition : Pour tout problème de PL, deux SBR sont adjacentes si leur

ensembles de variables de base ont m − 1 variables de base en commun.

La question quelle est la variable entrante, et celle sortante?

Construction du tableau initial

Etape 1

Solution optimale FinOui

Non

Déplacement (pivotage) vers une SBR adjacente

Etape 2

Chapitre 2 Méthode de simplexe Remarque : Si la SBR est non dégénérée, le déplacement implique

un point extrême adjacent ;

Si la SBR est dégénérée, la base change mais on reste au même point extrême (une nouvelle variable nulle).

Pour se déplacer d’une SBR à une autre adjacente, une variable hors base (variable entrante xe) va prendre la place de l’une des variables de base (xs). Ainsi,


Variables de base x1 …xs …xm -z xm+1 … xe … xn Valeurs des var de base

x1

.xs

.xm

1 … 0 … 0 0 a1,m+1 … a1,e …a1,n

0 … 1 … 0 0 as,m+1 … as,e…as,n

0 … 0… 1 0 am,m+1 am,e … am,n

b1

.bs

.bm

-z 0 … 0 … 0 1 m+1 … e … n -cBB-1b = -z

Questions : 1. Quelle est la variable entrante?2. Quelle est la variable sortante?


3.1. Choix de la variable entrante

Dans une SBR toutes les variables hors base sont nulles (xe =0). Pour faire entrer xe, on augmente sa valeur, par exemple de 0 (xe = xe + ) tout en maintenant à zéro toutes les autres variables hors base.

1er critère de Dantzig : nous indique le choix de la variable entrante. Ce dernier est basé sur la contribution éventuelle de xe à la fonction objectif.

Puisque z(x) = z(x) + . x z(x)/ xj= j = taux de variation de z par rapport xj.

Par conséquent on choisit la variable, xe, ayant le taux d’augmentation maximal de z(x) (PL de max), c-à-d le j maximal :

xe est telle que e = max{ j , où j= m+1, …, n ; j > 0}


2ème critère de Dantzig : nous indique la valeur de la variable entrante ().

Pb de maximisation : on désire donc augmenter xe le maximum possible, tout en satisfaisant les contraintes. On sait que le PL sous la forme canonique est équivalent au problème de départ. Donc, les valeurs des variables de base doivent changer tout en satisfaisant les contraintes suivantes :

xi + ai,m+1 xm+1 + …+ ai,e xe…+ai,n xn = bi i = 1, …, m

Comme xe = xi =bi - ai,e

La valeur de doit être choisie telle que : xi = bi - ai,e 0, i = 1, …, m

Chapitre 2 Méthode de simplexe Pour tout i tel que ai,e 0, on a bienbi - ai,e 0 et ceci 0

(car bi 0 : puisqu’on part d’une SBR).

Pour i tel queai,e > 0, on doit choisir telle que bi/ai,e

La valeur maximale de qui satisfait ces contraintes est max = min {bi/ai,e : i = 1, …, m et ai,e > 0} 2ème critère de DANTZIG (critère du ratio minimal)

On en déduit la variable sortante :

xs telle quebs/as,e = min {bi/ai,e : i = 1, …, m et ai,e > 0}

En effet, pour la ligne s : xs = bs - as,e = bs - as,e (bs/as,e) = 0


On appelle :as,e : élément pivot

Ligne s : ligne pivot

Colonne e : colonne pivot

Maintenant on a donc une nouvelle base B’ = {1, …, e, …, m} avec xs étant une nouvelle variable hors base.

Il faudra ainsi représenter le PL sous la forme canonique associée à B’. La colonne de xe doit être transformée afin de conserver la matrice

d’identité:

s

0

1

0

a

a

a

e,m

e,s

e,1

Ligne


Pour ce faire, on applique les opérations élémentaires suivantes (selon Gauss-Jordan) :

Op1 : Division de la ligne pivot par l’élément pivot as,e asj’ = as,j/as,e j, ase’ = 1

Var. de base

x1 … xs … xm -z xm+1 …xe … xn Val. des var de base

x1.xs

.xm

1 … 0 … 0 0 a1,m+1 …a1,e …a1,n

0…1/as,e … 0 0 as,m+1’ …1 …as,n’

0 … 0 … 1 0 am,m+1’ …am,e …

am,n

b1

bs/as,e

.bm

-z 0 … 0 … 0 1 m+1 … e …

n

- z


Op2 : i s, soustraction d’un multiple approprié de la ligne pivot pour annuler le coefficient de la ligne i , colonne e.

aij’ = aij – aie as,j/as,e j = 1 , …, n+1 (n+ dernière ligne du tableau) aie’ = 0

j’ = j - e as,j/as,e j = 1, …, n+1 (n var plus -z )

0

0

1

0

Var. de base

x1 … xs … xm -z xm+1 …xe … xn Val. des var de base

x1.xs

.xm

1 … 0 … 0 0 a1,m+1 …a1,e …a1,n

0…1/as,e … 0 0 as,m+1’ …1 …as,n’

0 … 0 … 1 0 am,m+1’ …am,e …

am,n

b1

bs/as,e

.bm

-z 0 … 0 … 0 1 m+1 … e …

n

- z

Chapitre 2 Méthode de simplexe Le nouveau tableau est donc le suivant:

Variables de base

x1 … xs … xm -z xm+1 …xe … xn

Valeurs des var de base

x1.xs

.xm

1 … -a1,e (1/as,e) … 0 0 a1,m+1’…0 …a1,n’

0 … 1/as,e … 0 0 as,m+1’ …1 …as,n’

0 … -am,e (1/as,e)…1 0 am,m+1’ …0 …am,n

b1–a1,e

(bs/as,e) .

bs/as,e

.bm’

-z 0 … - e (1/as,e) 0 1 m+1 ’ … 0 … n’

- z - e (bs/as,e)

Chapitre 2 Méthode de simplexe ExempleSoit le PL suivant :

max z = 3x1 + 2x2s.c. x1 + x2 + s1 = 80

2 x1 + x2 + s2 = 100 m=3, n=5 ; rang(A)=3

x1 + s3 = 40x1, x2, s1, s2, s3 0

Une SBR apparaît d'une façon évidente : s1 = 80; s2 = 100; s3 = 40

VB = {s1, s2, s3}; alors VHB = {x1, x2} ,

c-à-d x1 = x2 = 0 z = 0


Suite exemple à faire

Chapitre 2 Méthode de simplexe Cas particuliers PL non borné : Des solutions ont été trouvées mais la valeur de z peut

toujours être améliorée. Dans le cadre de Simplexe, ce cas est représenté par le fait que dans chacune de ces colonnes j, aij 0 pour tout i (pas de variables sortantes) d’où il est impossible de faire entrer dans la base des variables telles que > 0. Les j > 0 montrent bien qu'il est possible d'augmenter z, mais le fait que tous les aij 0 montre qu'il n'existe pas de

SBR susceptible d'augmenter z. PL a une infinité de solutions

Exemple:

max z = 3x1 + 2x2

s.c. 3x1 + 2x2 120

x1 + 1x2 50

x1, x2 0


#1 x1 X2 s1 s2 bi

s1 3 2 1 0 120

s2 1 1 0 1 50

cj 3 2 0 0 0

#2 x1 X2 s1 s2 bi

x1 1 2/3 1/3 0 40

s2 0 1/3 -1/3 1 10

j 0 0 -1 0 -120


C'est un tableau optimal, mais on remarque la présence d'une variable hors base à j = 0. Cela veut dire que si on la fait entrer dans la base,

on va obtenir une autre SB optimale sans que la valeur de z ne change le segment formé par ces deux SB optimales contient

toutes les solutions optimales du problème.

Un autre tableau optimal :

#3 x1 X2 s1 s2 bi

x1 1 0 1 -2 20

x2 0 1 -1 3 30

j 0 0 -1 0 -120


4. Résumé de l’algorithme de simplexe

1. Mettre le PL sous la forme standard.2. Trouver une solution initiale de base (SBR initiale).3. Ecrire le PL sous la forme canonique relative à la SBR initiale.4. Itérations :

4.1. Si le critère d'arrêt est satisfait (Δ ≤ 0), donner le résultat final (solution optimale) ; sinon aller à l'étape 4-2.4.2. Déterminer la variable entrante (ou la colonne pivot) selon le 1er critère de DANTZIG 4.3. Déterminer la variable sortante (ou la ligne pivot) selon le 2ème critère de DANTZIG4.4. Calculer le nouveau tableau en effectuant une opération de pivot. Retour à 4-1.

Chapitre 2 Méthode de simplexeIV. Méthode de simplexe à deux phasesOn a déjà indiqué que la méthode de Simplexe part d’un PL sous la forme canonique. Cela suppose qu’on peut facilement identifier une SBR initiale. Parfois, ceci n’est pas évident, par exemple

(P) Max z = 4x1 + 3x2

s.c. 2x1 –x2 15

x1 + x2 = 10

2x1 – x2 20

x1, x2 0

En mettant ce PL sous la forme standard, on obtient

Max z = 4x1 + 3x2

s.c. 2x1 –x2 –e1 = 15

x1 + x2 = 10

2x1 – x2 + s3= 20

x1, x2, e1, s3 0

Chapitre 2 Méthode de simplexeIl est difficile de trouver intuitivement/rapidement une SBR. Alors, qu’est-ce qu’on fait ? On introduit encore des variables dites artificielles à chaque contrainte ‘‘et à chaque contrainte ‘=’, on obtient alors (P’) :

Max z = 4x1 + 3x2s.c. 2x1 –x2 –e1 + s1= 15x1 + x2 +s2= 102x1 – x2 + s3 = 20x1, x2, e1, s3, s1,s2 0

Une SBR de P’ est donnée par VB = {s1,s2, s3}. Cependant, les variables artificielles non seulement ont un effet nul dans la fonction objectif mais aussi doivent être nulles dans une SBR de P. Alors, lorsqu’une variable artificielle est non nulle, ceci indique que la solution est non réalisable dans P. On doit essayer d’annuler les variables artificielles dans P’. Ceci est réalisé en appliquant l’algorithme de Simplexe au problème suivant :


Min zI = si var artificielle si = s1 +s2s.c. 2x1 –x2 –e1 + s1= 15

(PI) x1 + x2 +s2= 102x1 – x2 + s3= 20x1, x2, e1, s3, s1, s2 0

Phase I : Résoudre PI par la méthode de Simplexe

Résultats possibles de la phase I :Cas 1 : zI 0 au moins une si 0 P non réalisable (DR vide)Cas 2 : zI = 0 et aucune variable artificielle n’est une VB. Dans ce cas, on omet toutes les colonnes du tableau optimal de la phase I, qui correspondent aux variables artificielles. On combine la fonction objectif de P avec les autres lignes de ce tableau. On met à jour la dernière ligne de telle manière à avoir j = 0 pour les VB. On obtient ainsi un tableau canonique initial de P. On continue alors la résolution avec la méthode de Simplexe (Phase II).

Chapitre 2 Méthode de simplexeCas 3 : zI= 0 et au moins une si est une VB du tableau optimal de la phase I Le problème original P a au moins une contrainte redondante Eliminer les contraintes redondantes ; réintroduire z(x) et commencer la phase II.

Rq : dans le cas 3, on trouve une ou plusieurs lignes où tous les coefficients sont nuls sauf ceux des variables artificielles telles lignes sont redondantes et peuvent être éliminées.

Exemple

La Ligne 2 peut être éliminée.

x1 x2 x3 x4 x5 s2

x3 3 -1 1 1 0 0 6

s2 0 0 0 0 0 1 0

x5 2 1 0 2 1 0 5

Chapitre 2 Méthode de simplexe Application à P :

Max zI = - s1 - s2

s.c. 2x1 –x2 –e1 + s1= 15

(PI) x1 + x2 + s2= 10

2x1 – x2 + s3= 20

x1, x2, e1, s3, s1, s2 0

# 1 x1 x2 e1 s3 s1 s2

s1 2 -1 -1 0 1 0 15

s2 1 1 0 0 0 1 10

s3 2 -1 0 1 0 0 20

0 0 0 0 -1 -1 0

Chapitre 2 Méthode de simplexeVariables de base (s1 et s2) ayant des coûts marginaux non nuls mise à jour du tableau : L4 L4 + L1 + L2

# 1 x1 x2 e1 s3 s1 s2

s1 2 -1 -1 0 1 0 15

s2 1 1 0 0 0 1 10

S3 2 -1 0 1 0 0 20

3 0 -1 0 0 0 25

# 2 x1 x2 e1 s3 s1 s2

X1 1 -1/2 -1/2 0 1 /2 0 15/2

s2 0 3/2 1/2 0 -1/2 1 5/2

S3 0 0 1 1 -1 0 5

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


Tableau optimal de la phase I (cas 2) : VB = {x1, x2, s3}

Rq: On peut éliminer du tableau la colonne d'une variable artificielle dès que celle-ci sort de la base.

# 3 x1 x2 e1 s3 s1 s2

X1 1 0 -1/3 0 1/3 1/3 25/3

X2 0 1 1/3 0 -1/3 2/3 5/3

S3 0 0 1 1 -1 0 5

0 0 0 0 -1 -1 0

Chapitre 2 Méthode de simplexePhase II :

# 4 x1 x2 e1 s3

x1 1 0 -1/3 0 25/3

x2 0 1 1/3 0 5/3

s3 0 0 1 1 5

4 3 0 0

L4 – 4L1 –3 L2 0 0 1/3 0 -115/3

# 5 x1 x2 e1 s3

x1 1 0 0 1/3 10

x2 0 1 0 -1/3 0

e1 0 0 1 1 5

0 0 0 -1/3 -40

Chapitre 2 Méthode de simplexeV. Méthode de Big M (phases I et II confondues) Si le PL est tel que des variables artificielles doivent être introduites pour obtenir un tableau canonique, on peut aussi le résoudre avec la méthode de Big-M

Principe : introduire les variables artificielles dans la fonction objectif, avec des coefficients arbitrairement larges (M >>0, pour un problème de minimisation), puis résoudre le problème résultant à l’aide de Simplexe (en une seule phase).

En général,

Max zM = cx - i Msi

(PM) s.c. Ax + s = b

x 0, s 0

Chapitre 2 Méthode de simplexeExemple :

Max zM= 4x1 + 3x2-M s1 -Ms2

s.c. 2x1 –x2 –e1 + s1= 15

(PI) x1 + x2 +s2= 10

2x1 – x2 + s3= 20

x1, x2, e1, s3, s1, s2 0

# 1 x1 x2 e1 s3 s1 s2

s1 2 -1 -1 0 1 0 15

s2 1 1 0 0 0 1 10

s3 2 -1 0 1 0 0 20

4 3 0 0 -M -M 0

Mise à jour

4+3M 3 -M 0 0 0 25M

Chapitre 2 Méthode de simplexe# 2 X1 x2 e1 s3 s1 s2

x1 1 -1/2 -1/2 0 1/2 0 15/2

s2 0 3/2 1/2 0 -1/2 1 5/2

s3 0 0 1 1 -1 0 5

0 5+3/2M

2+1/2M 0 -2-3/2M

0 -30+5/2M

# 3 X1 x2 e1 s3 s1 s2

x1 1 0 -1/3 0 1/3 1/3 25/3

x2 0 1 1/3 0 -1/3 2/3 5/3

s3 0 0 1 1 -1 0 5

0 0 1/3 0 -1/3-M 0 -115/3


# 4 X1 x2 e1 s3 s1 s2

x1 1 0 0 1/3 0 0 10

x2 0 1 0 -1/3 0 2/3 0

e1 0 0 1 1 -1 0 5

0 0 0 -1/3 -M 0 -40


Résultats possibles de Big-M : Cas 1 : Simplexe donne une solution optimale (x*, s*) avec s* =

0. Alors x* est optimal pour le problème de départ (P).

Cas 2 : Simplexe donne une solution optimale (x*, s*) avec s* 0. Le critère d’optimalité étant satisfait M suffisamment large, (P) est donc non-réalisable.

Cas 3 : (PM) est non borné M suffisamment large. Le critère d’optimalité étant satisfait M suffisamment large, (P) est non borné s’il est réalisable, sinon il est non-réalisable. On doit alors vérifier s’il est réalisable: Ceci en continuant l’algorithme après remplacement de la fonction objectif (dans le dernier tableau) par Z’M = - i Msi (en annulant les constantes dans l’expression (j + M j*) de la dernière ligne). Si la solution optimale obtenue est telle que s = 0, alors (P) est réalisable donc non-borné, sinon (P) est non-réalisable.


Exemple

Max zM = x1 + x2 - M s1 - Ms2

(PM) s.c. x1 + x2 –e1 + s1= 1

x1 - x2 – e2 +s2= 0

x1, x2, e1, e2,s1, s2 0

# 1 x1 x2 e1 e2 s1 s2

s1 1 1 -1 0 1 0 1

s2 1 -1 0 -1 0 1 0

1 1 0 0 -M -M 0

Mise à jour

1+2M 1 -M -M 0 0 M


# 2 x1 x2 e1 e2 s1 s2

s1 0 2 -1 1 1 -1 1

x1 1 -1 0 -1 0 1 0

0 2+2M -M 1+M 0 -1-2M M

# 3 x1 x2 e1 e2 s1 s2

X2 0 1 - ½ ½ ½ -½ ½

X1 1 0 - ½ -½ ½ ½ ½

0 0 1 0 -1-M -M -1

(PM) non borné car Δe1 > 0 et tous les aij < 0 (pas de var sortante)


# 4 x1 x2 e1 e2 s1 s2

x2 0 1 - ½ ½ ½ -½ ½

x1 1 0 - ½ -½ ½ ½ ½

0 0 0 0 -M -M 0

Si P est réalisable alors il est non borné sinon il est non réalisable

Pour vérifier s’il est réalisable ou pas on modifie la ligne des Δj par la fonction objectif Z’M = - i Msi et on vérifie si tous lessi = 0, alors (P) est réalisable

Z’M = 0 s1* = s2* = 0 (P) réalisable (P) non borné.


Il est pratiquement impossible de conclure si la méthode de Big-M résout les PL avec moins de calcul que l'approche à deux phases. L'expérience pratique semble indiquer que les deux approches ont approximativement le même effort de calcul.

Pour résumer :La résolution d'un PL à l'aide de l'algorithme de simplexe nécessite

une SBR initiale. C'est un problème qui peut être résolu de trois manières différentes :

1. Introduction de variables artificielles et l'application de Simplexe à deux phases (phase I trouve une SBR)

2. Introduction de variables artificielles et l'application de la méthode de Big-M (basée sur l'algorithme de Simplexe)

3. Trouver intuitivement une SBR, écrire le PL sous la forme canonique, puis passer directement à la phase II (l’approche la moins pratique).

Chapitre 3

Dualité et analyse de sensibilité dans la

programmation linéaire

Chapitre 3 Dualité et analyse de sensibilité

I. Introduction Il est possible à partir d’un PL (P) de former un autre programme linéaire qu’on appelle programme dual (D) associé à (P). Dans ce contexte, on appelle (P) problème primal.

(P) : max cx (D) : min w = yb

s.c. Ax ≤ b s.c. yA c

x 0 y 0

La notion de dualité est très importante pour le mathématicien, car dans le cas où le primal a beaucoup de contraintes, le dual peut être plus facile à résoudre que le primal. Pour l'économiste et le gestionnaire, la dualité est très importante. On verra dans la suite son interprétation économique.


II. Interprétation économique de la dualité• bi : quantité totale de la ressource i ;• aij : quantité de la ressource i consommée pour fabriquer une unité du produit j• cj : coût unitaire du produit j

yi représente la valeur unitaire de la ressource i. Elle est souvent appelée coût fictif ou prix ombre. C’est le montant maximum que l’on sera prêt à payer pour une unité supplémentaire de le ressource i ou encore le prix minimum auquel on serait prêt à vendre une unité de la ressource i.


1. Le dual d'un problème de maximisationConsidérons l'exemple suivant : une usine fabrique des bureaux, des tables et des chaises.

La fabrication de chaque type de produit nécessite de la matière première (bois) et deux types d’activités : menuiserie et finition. La quantité requise de chaque ressource est donnée comme suit :

ProduitRessource

Bureau Table Chaise Quantité de ressource disponible

Bois (plaque) 8 6 1 48

Menuiserie (heure) 2 1.5 0.5 8

Finition (heure) 4 2 1.5 20

Prix de revient (D) 60 30 20


On désire maximiser le revenu.

Variables de décision :x1 = nombre de bureaux fabriquésx2 = nombre de tables fabriquéesx3 = nombre de chaises fabriquées (P) max z = 60 x1 + 30 x2 + 20 x3 s.c. 8 x1 + 6 x2 + x3 48 (ressource bois)

2 x1 + 1.5 x2 + 0.5 x3 8 (ressource menuiserie) 4 x1 + 2 x2 + 1.5 x3 20 (ressource finition)

x1, x2, x3 0


Supposons qu'un entrepreneur veut acheter toutes les ressources de l’usine (bois, heure menuiserie, heure finition) . Il veut certainement que le prix total de ces ressources soit minimal. On définit alors :

y1 = prix d'une plaque de bois

y2 = prix d'une heure de menuiserie

y3 = prix d'une heure de finition

L'entrepreneur doit payer : w(y) = 48y1 + 8 y2 + 20 y3 et désire minimiser w, mais il doit payer suffisamment pour convaincre l’usine de vendre ses ressources.


Par exemple, il doit payer au moins 60D pour une combinaison de : 8 plaques de bois + 2 heures de menuiserie + 4 heures de finition car l’usine peut utiliser ces ressources pour fabriquer un bureau et le vendre pour 60D.

L'entrepreneur doit payer au moins 60D, sinon l’usine ne verra aucune raison de lui vendre ses ressources 8y1 + 2 y2 + 4 y3 60

De même on a : 6y1 + 1.5 y2 + 2 y3 30

y1 + 0.5 y2 + 1.5 y3 20

avec y1, y2, y3 0 coûts fictifs ou prix ombre (resource shadow price)


Le problème dual est ainsi le suivant :

(D) min w = 48y1 + 8 y2 + 20 y3s.c. 8y1 + 2 y2 + 4 y3 60

6y1 + 1.5 y2 + 2 y3 30y1 + 0.5 y2 + 1.5 y3 20y1, y2, y3 0


2. Le dual d'un problème de minimisationConsidérons l’exemple suivant : Une famille désire préparer un menu équilibré à coût minimal. Ce menu doit être constitué de 6 aliments (notés 1, 2, 3, 4, 5 et 6) et doit contenir au moins 9 unités de vitamine A et 19 unités de vitamine C.

Les proportions en vitamine A et C de chaque aliment ainsi que les quantités minimales requises de chaque vitamine et les coûts des différents aliments sont présentés dans le tableau suivant :

Proportions vitamine /Kg d'aliment1 2 3 4 5 6

Qté min requises /jour

Vitamine AVitamine C

1 0 2 2 1 20 1 3 1 3 2

919

Coût de l'aliment

35 3060 50 27 22


On définit : xj quantité en kg de l'aliment j, j = 1, ..., 6.

(P) : min z = 35x1 + 30 x2 + 60 x3 + 50 x4 + 27 x5 + 22 x6 s.c. x1 + 2 x3 + 2 x4 + x5 + 2 x6 9 (Vitamine A) x2 + 3 x3 + x4 + 3 x5 + 2 x6 19 (Vitamine C)

xj 0 j = 1, ..., 6

Un fabriquant compte lancer un projet dans le domaine alimentaire. Il propose de fabriquer des comprimés de chaque vitamine et de les vendre à la famille. Pour que cette affaire se réalise et prospère, le fabricant doit persuader la famille d'obtenir les quantités requises des vitamines en utilisant les comprimés au lieu des aliments. La famille, étant consciente de l'aspect monétaire, n'utilisera les comprimés que si leurs prix sont compétitifs par rapport aux prix des aliments. Ceci impose plusieurs contraintes sur les prix des comprimés que le fabriquant doit fixer.


Soient y1 : prix de la vitamines A

y2 : prix de la vitamine C

Prenons par exemple l'aliment 5 : Un kg de ce dernier contient 1 unité de A et 3 unités de C. Du point de vue du fabricant, le kg de l'aliment 5 vaut

y1 + 3 y2. Or un kg de l’aliment 5 coûte 27.

Il faut donc que y1 + 3 y2 27, sinon la famille réalisera que les prix du fabriquant ne sont pas compétitifs (elle aura intérêt à acheter l’aliment 5).

De l'autre côté, puisque le fabricant veut gagner dans cette affaire, y1 et y2 doivent être 0. De plus, si la famille décide d'utiliser les comprimés,

elle en achètera juste le nécessaire (9 et 19 unités), sinon, ça coûtera cher étant donné que y1 et y2 0.


Le revenu du fabricant sera alors w(y) = 9 y1 + 19 y2, et par conséquent, les prix que le fabricant va fixer sont obtenus en trouvant

la solution optimale du problème suivant :

max w(y) = 9 y1 + 19 y2s.c. y1 35

y2 302 y1 + 3 y2 602 y1 + y2 50 y1 + 3 y2 272 y1 + 2 y2 22y1, y2 0


3. Détermination du dual d’un programme linéaire3.1 Le dual d'un PL sous la forme normale

Un PL est dit sous la forme normale si c'est un problème de : max avec des contraintes ; x 0 (max x ; s.c. Ax b : infini)

ou min avec des contraintes ; x 0 (min x ; s.c. Ax b : infini)

Soit P un PL sous la forme normale : Le dual D associé à P est :max z = cx min w = ybs.c. Ax b s.c. yA ≥ c

x 0 y ≥ 0


3.2 Le dual d'un PL à contraintes mixtesSi le primal P est sous forme générale, on peut construire son dual D de deux manières possibles :

1/ Mettre P sous la forme normale. Supposons qu'on part d'un problème de maximisation. On peut :- multiplier chaque contrainte par (-1)- remplacer aix = bi par { aix bi et -aix -bi }

- remplacer chaque xj < > 0 par xj+ - xj- avec xj+ 0 et xj- 0

2/ Appliquer les règles suivantes :


Primal (Dual) Dual (Primal)

Fonction à maximiser Fonction à minimiser

ième contrainte ième variable 0

ième contrainte ième variable 0

ième contrainte = ième variable <> 0

jème variable 0 jème contrainte

jème variable 0 jème contrainte

jème variable <> 0 jème contrainte =


3.3. Exemples

max z = 2x1 + x2 min w = 2y1 + 3 y2 + y3

s.c. x1 + x2 = 2 s.c. y1 + 2 y2 + y3 2

2 x1 - x2 3 y1 - y2 - y3 = 1

x1 - x2 1 y1<> 0, y2 0, y3 0

x1 0, x2 <>0

min z = 5x1 - 6 x2 + 7 x3 + x4 max w = -7y1 + 14 y2 – 3y3

s.c. x1 + 2 x2 - x3 - x4 = -7 s.c. y1 + 6y2 – 2y3 5

6 x1 - 3x2 + x3 + 7 x4 14 2y1 – 3y2 – 17 y3 -6

-2 x1 -17 x2 + 4 x3 + 2 x4 -3 -y1 + y2 + 4y3 = 7

x1 0 , x2 0; x3<>0, x4<>0 -y1 + 7y2 + 2y3 = 1

y1<>0, y2 0, y3 0


III. Analyse de sensibilité en programmation linéaireSouvent, les coefficients de la fonction objectif cj, le second membre bi ou les coefficients technologiques aij subissent des changements (fluctuations des prix, disponibilités des ressources, ...). Alors on est intéressé par la stabilité de l'optimum par rapport à ces paramètres, afin de savoir dans quels intervalles la solution optimale, la base optimale ou la valeur optimale de la fonction objectif ne changent pas.Dans ce qui suit, nous allons nous intéresser uniquement aux variations des coefficients de la fonction objectif.

1.Variations des coefficients de la fonction objectifC’est l’étude de l'effet des variations de l'un des cj tout en maintenant les mêmes valeurs pour toutes les autres données du problème.

ck ck + λ = ck(λ)


La complexité de cette étude varie selon que la variable xk appartient ou non à la base optimale. On commence par le cas le plus simple : celui

où xk est hors base.

1.1 Cas de xk variable hors base

Quel sera l’effet d’un changement de ck sur la solution optimale du problème ?

Soit B la base optimale. Pour quelles valeurs de λ cette base reste-elle optimale ?

On remarque que dans le tableau optimal, modifié par le nouveau coefficient ck+ λ:

1. B-1b ne change pas 2nd membre est le même

2. Le seul changement possible sera au niveau des coûts marginaux, notamment Δk


B restera optimale si Δk () 0 Δk () = ck + – (cBB-1) Ak 0

- ck + (cBB-1) Ak = -Δk (0)

Déf : -j d’une variable hors base est le maximum dont on peut augmenter cj avant que la base actuelle ne soit plus optimale.

Dans le cas où > -Δk (0), B n’est plus optimale. On peut trouver la nouvelle solution optimale en remplaçant k(0) par Δk() dans le tableau

optimal. Puisque Δk() > 0, xk va entrer à la base. Alors, on continue

l’algorithme de Simplexe.

Chapitre 3 Dualité et analyse de sensibilitéExemple :Reprenons l'exemple de MEUBLE.

max z = 60 x1 + 30 x2 + 20 x3(P) s.c. 8 x1 + 6 x2 + x3 48 (ressource bois)

2 x1 + 1.5 x2 + 0.5 x3 8 (ressource menuiserie)

4 x1 + 2 x2 + 1.5 x3 20 (ressource finition)x1, x2, x3 0

Le tableau optimal est le suivant : x1 X2 x3 s1 s2 s3

s1 0 -2 0 1 -8 2 24

x1 1 1.25 0 0 1.5 -0.5 2

x3 0 -2 1 0 -4 2 8

j 0 -5 0 0 -10 -10 -280

Chapitre 3 Dualité et analyse de sensibilitéx1 bureaux ; x2 tables ; x3 chaises

B = {s1, x1, x3} ; x2 variable hors base

Considérons : c2 c2 +λ Δ2 = λ - 5 B restera optimale si λ 5

Si λ 5 (ou c2() 35): le prix d’une table diminue ( < 0) ou augmente d’au plus 5 D, la base actuelle reste optimale. De plus, les valeurs des variables ainsi que celle de la valeur de la fonction objectif restent les mêmes (x1 = 2, x3 = 8, x2 = 0, z* = 280).

Si λ > 5 (ou c2() > 35): B n’est plus optimale. Par exemple, = 10. Dans ce cas, on peut trouver la nouvelle solution optimale en remplaçant 2 = -5 par 2 (10)= 10 -5 = 5 Nouveau tableau :


x1 x2 x3 s1 s2 s3

s1 0 -2 0 1 -8 2 24

x1 1 1.25 0 0 1.5 -0.5 2

x3 0 -2 1 0 -4 2 8

j 0 5 0 0 -10 -10 -280 x2 entre et x1 sort.

x1 x2 x3 s1 s2 s3

s1 1.6 0 0 1 -5.6 1.2 27.2

x2 0.8 1 0 0 1.2 -0.4 1.6

x3 1.6 0 1 0 -1.6 1.2 11.2

j -4 0 0 0 -16 -8 -288


1.2 Cas de xk variable de baseDans ce cas, cBB-1 change Plus qu’un coefficient dans la dernière ligne peuvent changer.

Question : dans quel intervalle peut varier tout en maintenant la même base ?

Cet intervalle est donné par le système d’inégalités suivant :

j () 0 pour toute variable hors base xj. (*)

1.Si vérifie (*), alors B reste optimale ; Dans ce cas B-1b ne change pas même valeurs des variables. Mais la valeur optimale de z change :

z*() = cB()B-1b = cB()xB* = cBxB + xk = z*(0) + xk


2. Sinon : l’une des variables hors base, xj, aura un coût marginal j() > 0, et B n’est plus optimale. Dans ce cas, xj entre et une variable de base sort (pas nécessairement xk) ; et on continue la résolution.

Exemple :

c1 c1 + λ

cB ()= (0 60+ 20) ;

cB ()B-1 = (0 10+1.5 10-0.5) = y*() =

s1 ()= 1() = 3() = 0

240

5.05.10

281

5.140

5.020

181

B 1-Β

))(y),(y),(y( *3

*2

*1


Pour les variables hors base :

2() = c2 - y*() A2 = 30 - (0 10+1.5 10-0.5) = -5 – 1.25

s2() = - = -10 – 1.5

s3()= - = -10 + 0.5

B reste optimale ssi

2() 0 -5 – 1.25 0 -4

s2() 0 -10 – 1.5 0 -20/3

s3() 0 -10 + 0.5 0 20

)(y*2

)(y*3

2

5.1

6


B reste optimale ssi -4 20 (ou 56 c1() 80)

Dans ce cas, la nouvelle z*() = 280 + 2

Si c1() < 56 : x1 sort de la base : le prix d’un bureau devient trop bas il n’est plus optimal d’en produire. Dans ce cas, 2 > 0 x2 entre à la place de x1.

Si c1() > 80 : le prix d’un bureau est assez élevé on veut en produire plus.

Dans ce cas, x1 doit rester dans la base. En effet, s2() > 0, alors s2 entre et x3 sort (on ne produit plus de chaises, mais que des bureaux).

Documents

Recherche Opérationnelle 2 ème Année Gestion industrielle Année universitaire : 2009 - 2010 Responsable du cours : Rim Larbi [email protected]