coursROGC2014_2015

1 Hanen Bouchriha

Fascicule du cours

Recherche Oprationnelle

Hanen Bouchriha

Cours de recherche oprationnelle

Introduction la programmation linaire

2 Hanen Bouchriha

Chapitre 1


1. Introduction

La programmation mathmatique est une technique de la Recherche Oprationnelle (RO). Il

est ainsi bon de prciser dabord, mme en peu de mots, ce quon entend par la RO. Il sagit dune discipline carrefour o se rencontrent aujourdhui lconomie, les mathmatiques et linformatique. Elle reprsente une dmarche scientifique permettant de prendre rationnellement les bonnes dcisions engager dans une situation donne. Ce qui revient

construire un modle de la ralit, de dterminer la dcision permettant doptimiser (minimiser ou maximiser) une certaine fonction conomique , en prsence de

contraintes multiples.

La programmation mathmatique est la technique de la (RO) base sur des modles

mathmatiques. Elle met en jeu : (1) une fonction objectif, (2) des variables de dcision

dterminer et (3) des contraintes respecter. La programmation linaire constitue la branche

de la programmation mathmatique pour laquelle toutes les fonctions du modle (fonction

objectif et contraintes) sont linaires.

2. Exemple de Formulation de Programme Linaire (PL)

Lentreprise VITRE SAR SA. Fabrique des vitres de haute qualit pour portes et fentres. Lentreprise souhaite lancer deux nouveaux produits : - Le produit 1 requiert des ressources dans latelier 1 et 3 - Le produit 2 requiert des ressources dans latelier 2 et 3.

Dans latelier 1, il sagit de construire des cadres en aluminium pour portes. Dans latelier 2, il sagit de construire des cadres en bois pour fentres. Lassemblage des vitres sur les cadres se fait dans latelier 3 (voir figure 1).



3 Hanen Bouchriha

Figure 1. Ateliers de la compagnie VITRE SAR SA.

Les deux types de produits sont fabriqus en lots de 20 units. .

Les responsables de cette entreprise se posent aujourdhui la question suivante : Quel serait le mix de produits 1 et 2 le plus profitable raliser dans latelier 3 ?

Afin de rpondre cette question, il faut disposer des donnes suivantes :

Le nombre dheures de production disponibles par semaine dans chaque atelier ; ce temps a t dtermin en tenant compte du temps dj allou aux autres produits.

Le nombre dheures de production ncessaires pour fabriquer un lot de produit donn dans chaque atelier.

Le profit ralis par la compagnie pour chaque lot de produit vendu.

Le tableau suivant rapporte lensemble des donnes cites ci-dessus.

Atelier Temps de production

(heures/lot)

Temps de production disponible

(heures/semaine)

1 2

1 1 0 4

2 0 2 12

3 3 2 18

Profit (TND/lot) 3000 5000

Compte tenu de ces donnes, lentreprise cherche dterminer le nombre de lots raliser par semaine pour les deux produits 1 et 2 dans lobjectif de maximiser le profit total, en respectant les restrictions imposes par les capacits limites des machines des 3 ateliers.

Cadre aluminium

pour porte

Cadre en bois

pour fentre

Assemblage

Vitre & cadre

Atelier 1 Atelier 2 Atelier 3

Ressource

partage

Cadre aluminium

pour porte

Cadre en bois

pour fentre

Assemblage

Vitre & cadre

Atelier 1 Atelier 2 Atelier 3

Ressource

partage



4 Hanen Bouchriha

Formulation mathmatique

- Variables de dcision : elles doivent dcrire les dcisions prendre.

Lentreprise doit dterminer le nombre de lots de produits 1 et de produits 2 produire par semaine. On dfinit alors :

x1 : le nombre de lots de produits 1 produire par semaine,

x2 : le nombre de lots de produits 2 produire par semaine.

- Fonction objectif : elle traduit lobjectif de lentreprise. Dune faon gnrale un responsable veut maximiser le revenu (ou le profit) ou minimiser le cot. Lobjectif est exprim sous forme dune fonction des variables de dcision, appele fonction objectif.

Profit hebdomadaire = Revenu hebdomadaire (Service commercial) Cot hebdomadaire (Service technique)

= 3000 x1 + 5000 x2 (en TND)

= 3 x1 + 5 x2 (en MTND)

Remarque : Dans les PL, on retrouve les proprits dadditivit et de proportionnalit mais pas celles concernant lconomie dchelle.

- Contraintes : si lentreprise est libre de choisir nimporte quelles valeurs pour x1 et x2, elle peut avoir un profit trs large en produisant de trs grandes quantits de produits 1

et de produits 2. Malheureusement, ces valeurs sont limites causes des restrictions

imposes par lenvironnement de lentreprise dune part et par les ressources capacit finie, dautre part. Ces restrictions sont exprimes par le biais des contraintes.

Contraintes de ressources Chaque semaine la capacit de production de latelier 1 est limite 4 heures

1 x1 + 0 x2 4 Chaque semaine la capacit de production de latelier 2 est limite 12 heures

0 x1 + 2 x2 12 Chaque semaine la capacit de production de latelier 3 est limite 18 heures

3 x1 + 2 x2 18

Contraintes de signe Pour terminer la formulation dun PL, on doit prciser lensemble des valeurs auquel appartiennent les variables de dcision.

Est-ce que les variables x1 et x2 peuvent prendre nimporte quelles valeurs relles, ou seulement des valeurs non ngatives ou encore des valeurs entires ou binaires ?

Dans cet exemple, le nombre de lots ne peut pas tre ngatif.

x1 0, x2 0

Remarque : Ici, nous supposons quon accepte les lots non entiers. Autrement, x1 et x2 doivent tre entiers et il sagit dun programme linaire en nombres entiers.

En combinant la fonction objectif et les contraintes, on obtient le programme linaire

suivant :



5 Hanen Bouchriha

Max Z=3 x1 + 5 x2 (1.1)

Sous les contraintes (s.c.) :

x1 4 (2.1)

2 x2 12 (3.1)

3 x1 + 2 x2 18 (4.1)

x1 0, x2 0 (5.1)

3. Dfinitions

Un PL est un problme mathmatique qui scrit sous la forme :

Max Ct x

S.c. Ax b

x0

O Max signifie maximiser, C IRn, b IRm et A est une matrice (m,n). La fonction maximiser (C

t x) est appele fonction objectif ou fonction conomique. Les

ingalits dfinies par le systme linaire (Ax b) sont les contraintes du problme et les composantes du vecteur x sont les variables de dcision.

La programmation linaire permet de modliser de nombreux problmes rels en exprimant

leur fonction objectif et leurs contraintes sous forme de fonctions linaires des variables de

dcision. Cependant, la programmation linaire impose un certain nombre de restrictions

rduisant ainsi son champ dapplication. Ces restrictions sont : - la proportionnalit : les termes mesurant les cots et les quantits de ressources

utilises doivent tre proportionnels au niveau de chaque activit.

- ladditivit : les cots et les ressources engages par lutilisation conjointe de deux activits doivent tre gaux aux termes correspondants ces deux activits utilises

sparment.

- le problme est dterministe : tous les coefficients du modle doivent tre des constantes connues et non des variables sujettes des variations.

Un vecteur x est une solution ralisable sil vrifie toutes les contraintes du problme (i.e. Ax

b et x 0). Lensemble de tous les vecteurs, solution ralisable, est appel domaine ralisable, not (DR).

Une solution ralisable du problme de lexemple 1 est reprsent par le point (3, 2) : il suffit de vrifier que les contraintes sont satisfaites ; par contre le point (3, 6) nest pas une solution ralisable du moment quil viole la contrainte (4.1). Une solution ralisable x* est optimale si la valeur de C

tx* est la meilleure des valeurs de C

tx

pour tout x, solution ralisable.

4. Rsolution graphique dun programme linaire

La rsolution graphique peut tre utilise pour des programmes linaires ayant au plus deux

variables de dcision. Dans le plan dfini par les deux variables de dcision, on trace les

diffrentes droites reprsentant les contraintes du problme. Suivant le sens des ingalits, on

dtermine le domaine ralisable par lintersection des diffrents demi-plans ralisables. On



6 Hanen Bouchriha

trace ensuite la ligne isoprofit (isocot) reprsentant la fonction objectif. Pour lexemple 1, la ligne profit est : 3 x1 + 5 x2 =cte. Cest une droite de pente (-5, 3).

Pour trouver une solution optimale, on dplace la ligne isoprofit dans la direction qui

augmente la valeur de la fonction objectif (pour une maximisation). La ligne la plus haute

coupant le domaine ralisable contient la ou les solutions optimales. Dans lexemple 1, la solution optimale est (2, 6) avec un profit hebdomadaire de 36 MTND.

Dans la figure 1, on a reprsent le graphique utilis pour rsoudre le problme de lexemple 1.

Figure 1. Rsolution graphique du problme de lexemple 1

5. Notions gomtriques relatives aux programmes linaires

Les techniques de la programmation linaire font appel aux proprits gomtriques des PL.

5.1. Notion de convexit

Un ensemble de points S dans le plan de dimension n est dit convexe si le segment joignant

nimporte quelle paire de points de S est entirement contenu dans S. Autrement,

Un ensemble SIRn est dit convexe si et seulement si :

x S, y S, [0,1], ( x1 + (1-) x2) S Dans la figure 3, quelques formes gomtriques sont donnes. Quels sont les ensembles

convexes ?



7 Hanen Bouchriha

Figure 3. Quelques formes gomtriques

(1), (2), (4) et (6) sont les ensembles convexes.

5.2. Polydre

Un ensemble H I Rn est un demi espace sil existe un vecteur a I Rn et a0 IR /

H={x IRn / atx a0}

On dit que H est le demi espace dfini par atx a0

Un ensemble PIRn est un polydre sil est dfini par lintersection dun nombre fini de demi-

espaces. Il est donc de la forme P ={x IRn / Ax b} o A est une matrice (m,n)

et b IRm.

Un polydre PIRn est dit born sil existe B IR+ et tel que P{x IRn / xj B j=1..n}. Dans la figure 3, les ensembles (2), (4) et (6) sont des polydres.

Lemme 1

Un polydre est un ensemble convexe.

5.3. Points extrmes

Soit un polydre PIRn.

MP est un point extrme si chaque segment de droite entirement contenu dans P et contenant M a M comme extrmit.

Autrement,

Soit P un ensemble convexe, xP est un point extrme si et seulement si : sil existe xP,

xP et [0,1] / x= x + (1-) x alors x= x= x. En dautres termes, un point extrme ne peut pas tre exprim comme combinaison convexe dautres lments de P. Dans la figure 4, on a reprsent un polydre ; les points A, B, C, D et E sont les points

extrme de ce polydre, F par contre nest pas un point extrme.



8 Hanen Bouchriha

Figure 4. Exemple de point extrme

Par dfinition, le domaine ralisable dun PL, sil nest pas vide, cest un polydre. Thorme 1

Lensemble des solutions ralisables dun PL, sil nest pas vide, il est convexe (un polydre). Thorme 2

Pour un PL donn, si un optimum existe, au moins un point extrme est optimal.

Corollaire 1

Si P est un polydre non vide alors loptimum est soit atteint en un point extrme, soit il est non born sur P.

Ces rsultats montrent que quand on cherche rsoudre un PL, il suffit de restreindre la

recherche de la solution optimale lensemble fini et discret des points extrmes du polydre dfini par les contraintes du problme. Dans le chapitre suivant, on va explorer la mthode du

simplexe qui repose sur cette ide.


Rsolution de programmes linaires laide de la mthode simplexe

9 Hanen Bouchriha

Chapitre 2 : Rsolution de programmes linaires par la mthode

du simplexe

1. Introduction

Jusque l, on a vu que cest la mthode gomtrique qui est utilise pour la rsolution des programmes linaires. Cette mthode est limite au cas de deux variables de dcision. Or,

pour les problmes rels, on se ramne toujours plus que deux variables. Pour un problme

de taille quelconque, cest la mthode du simplexe qui est utilise. Cette mthode a t dveloppe par George Dantzig en 1947. Elle est efficace et performante pour les problmes

de grande taille (notamment en terme de temps de rsolution).

2. Concepts lis la solution recherche

Concept 1 : La mthode du simplexe se concentre uniquement sur la recherche de points

extrmes du Domaine des solutions ralisables (D)

a. Cela suppose que D est born b. Pour tout problme ayant au moins une solution optimale, trouver la solution

qui correspond au meilleur point extrme.

Concept 2 : La mthode Simplexe est un algorithme itratif qui ncessite lapplication dun certain nombre dtapes :

Concept 3 : Quand cest possible, choisir lorigine comme solution initiale de la mthode du simplexe.

Examiner si lorigine (toutes les variables de dcision sont nulles) vrifie toutes les contraintes

Concept 4 : tant donne une solution qui correspond un point extrme, cest plus rapide (en terme de temps de calcul informatique), de rassembler les informations sur les points

extrmes adjacents.

A chaque fois quon veut amliorer une solution, la mthode simplexe considre les points extrmes adjacents

Initialisation

STOPTest

doptimalit ?

Rechercher un autre point extrme

permettant damliorer la solution obtenue jusque l

Oui

Non

Lequel?

Quelle mthode

dnumration?

Comment vrifier si

la solution courante

est Optimale?



10 Hanen Bouchriha

Dfinition :

Pour un PL n variables, 2 points extrmes ralisables sont adjacents sils partagent les frontires donnes par (m-1) contraintes. Ainsi, deux solutions adjacentes sont

relies par un segment (ou un bord) du Domaine Ralisable.

Exemple : on considre lexemple du chapitre prcdent

Point extrme ralisable Point extrme ralisable adjacent

(0,0) (0,6) et (4,0)

(0,6) (0,0) et (2,6)

(4,3) (2,6) et (4,0)

Concept 5 : une fois une solution (qui correspond un point extrme) est identifie, la

mthode du simplexe examine chaque bord du domaine qui mane de ce point. Chacun des

bords correspond un point extrme adjacent. La mthode identifie le taux damlioration de Z qui correspond au balayage de chacun des bords. Parmi les bords qui correspondent un

taux damlioration positif, la mthode choisit celui qui correspond au taux le plus lev. Cest le point extrme correspondant qui sera considr et constituera la nouvelle solution du problme qui subira le test doptimalit

Concept 6 : Le test doptimalit consiste vrifier si lun des bords correspond un taux damlioration positif de Z

0,

18 2 3

12 2

4

53

21

21

2

1

21

xx

xx

x

xsc

xx Z Max



11 Hanen Bouchriha

Retour lexemple :

Etape 0 : (0,0) est Point extrme (Z = 0)

Etape 1 : En parcourant laxe x1 ceci devra amliorer Z dun taux de 3 units ; alors quen balayant laxe x2 ceci entraine une amlioration de 5 units

Parcourir x2 nouveau point extrme (0,6) et nouvelle valeur de Z = 30 Etape 2 : Le seul bord qui doit engendrer un taux damlioration de Z positif correspond x1

Nouveau point extrme (2,6) qui correspond un Z = 36 Etape 3 : en parcourant les deux bords, Z dcroit (2,6) est point extrme optimal ARRET

3. Dfinition de la forme standard Etant donne la forme standard suivante dun programme linaire :

Max Ctx

Sc Ax = b

x 0

O c n, x n , b m, A une matrice relle (m,n) Avec :

- b 0

- m n / rg (A) = m (cest--dire pas de contraintes redondantes)

Dans tout le cours, nous adoptons cette forme standard pour tout programme linaire

considr.

Il est toujours possible de transformer nimporte quel PL en un PL quivalent exprim sous la forme standard :

- un problme de minimisation est transform en un problme quivalent de maximisation : Min (C

t x) = Max ( Ct x).

(2,6)

(4,3)

x1

x2

X1=4

X2=6

3X1+2X2 = 18

(4,0)

(0,6)

(0,0)



12 Hanen Bouchriha

- une ingalit de la forme aijxi bj peut tre transforme en une galit en introduisant une variable supplmentaire non ngative si, appele variable dcart ou slack variable.

La contrainte quivalente scrit alors aijxi + sj =bj.

- Dans la mesure du possible, et si on a des contraintes de type le sens dune ingalit peut tre invers en multipliant des deux cts par (-1) condition que le

second membre reste positif.

- une variable de dcision xi non contrainte en signe (xi ) peut tre exprime comme la diffrence de deux variables positives xi

+ et xi

- ; xi = xi

+ xi-.

4. Solution de Base - Soit B une matrice carre rgulire dordre m extraite de la matrice A

B est forme de colonnes linairement indpendantes Ou encore B est / det(B) = 1

B est dite matrice de base - Notons N La matrice forme par les n m colonnes de A et nappartenant pas B

N est dite matrice hors base - Tout vecteur x n peut tre partitionn en xB et xN

Matrice A

- On appelle Solution tout point x qui satisfait

Ax = b (pas ncessairement x 0)

BxB + NxN = b

- Une solution satisfaisant x 0 est dite Solution Ralisable. - La solution dfinie par xN= 0 et xB = B

-1b est dite Solution de Base associe la Base B

- Soit x une solution de base. Si de plus, on a xB 0 alors x est une Solution de Base Ralisable (SBR). Ainsi, on appelle :

xB : Variables de Base (VB) xN : Variables Hors Base (VHB)

Proprit

Pour une Solution de Base Ralisable Le nombre de variables de base = Nombre de contraintes Nombre de variables Hors Base = Nombre total de variables Nombre de

contraintes

Revenons lexemple aprs lavoir crit sous sa forme standard et dfinissons des SBRs et des Solutions Ralisables

(0,6,4,0,6) et (0,0,4,12,18) sont deux SBR (1,0,3,12,15) est une SR mais pas une SBR parce quelle admet plus de 3

variables non nulles.

N

m

m n-m

n

xB

xN

m

n-m



13 Hanen Bouchriha

Thorme

Soit x D une solution ralisable dun PL

x est un point extrme x est une SBR A chaque point extrme on associe une solution de Base Ralisable et

inversement.

Une SBR correspond un point extrme augment des variables dcart. Dfinition

Deux SBR sont adjacentes ssi elles correspondent deux points extrmes adjacents.

Deux SBR sont adjacentes si Tout sauf une de ses variables Hors Base sont identiques ce qui implique que Tout sauf une de ses variables de Base sont

identiques. Toutefois ces dernires peuvent avoir des valeurs numriques

diffrentes

SBR SBR adjacente

xi : une variable Hors Base xi : une variable de Base

xj : une variable de Base xj : une variable Hors Base

Exemple : 2 SBR adjacentes :

(0,0,4,12,18) (0,6,4,0,6)

5. Tableau canonique

Soit B une Base ralisable extraite de la matrice A

La Fonction Objectif scrit alors : Z = CBxB + CNxN Do : CBxB + CNxN - Z = 0 Les contraintes scrivent : BxB + NxN = b

Le programme linaire (PL) scrit alors partir de la forme standard sous forme dun tableau comme suit :

1er

Membre 2nd

Membre

xB -Z xN

B 0 N b

CB 1 CN 0

Le tableau canonique relatif la base B est obtenu en transformant la matrice sous les

variables xB et Z en une matrice identit dordre (m+1) Il sagit de multiplier gauche de chaque colonne du tableau par

1

0

1

01

11

1

BC

B

C

BT

BB



14 Hanen Bouchriha

Le tableau canonique relatif la Base B est :

1er

Membre 2nd

Membre

xB -Z xN

Im 0 B-1

N B-1

b

0 1 -CBB-1

N + CN -CBB-1

b

La forme canonique est intressante car elle permet de lire directement la solution de base

relative la base B

xB = B-1

b

xN = 0

Z = CBB-1

b 0

La forme canonique satisfait les 3 conditions suivantes :

La matrice extraite de A par la considration des m colonnes de Base est une matrice Identit Im

Les coefficients des variables de Base dans la fonction objectif sont nuls Le second membre correspondant aux contraintes est non ngatif.

6. Mthode du simplexe

Lide de la mthode simplexe est de partir dun point extrme initial et de gnrer une suite de points extrmes adjacents tout en assurant une amlioration de la fonction objectif.

Recherche dune solution de Base Ralisable Initiale (Point extrme) On revient notre exemple. La formulation standard est :

0x,x,x,,

18 x 2 3

12 x 2

4 x

053

54321

521

42

31

21

xx

xx

x

xsc

ZxxMax

Do le tableau :

x1 x2 x3 x4 x5 2nd

Membre

1 0 1 0 0 4

0 2 0 1 0 12

3 2 0 0 1 18

3 5 0 0 0 0

Il sagit dun tableau canonique relatif la solution de base ralisable initiale (0,0,4,12,18)

Disposant dune SBR, il faut vrifier sil sagit dune solution Optimale (test doptimalit) Soit x* une Solution de Base Ralisable associe la base B Z(x*) = CBB

-1b (1)

Soit x une Solution Ralisable. Do, on peut crire : x = xB + xN



15 Hanen Bouchriha

Z(x) = CBxB + CNxN (2)

De plus BxB +NxN=b. En multipliant par (CBB-1

) gauche, on obtient :

CBB-1

BxB + CBB-1

NxN= CBB-1

b = Z(x*) (daprs 1) Do Z(x) - Z(x*) = (CB- CBB

-1B)xB +(CN- CBB

-1N)xN = (C- CBB

-1A)x = x

Thorme

Soit x* une SBR relative la base B.

Si = C CBB-1A 0 alors x* est optimale

reprsente la dernire ligne du tableau (cf. forme canonique) x = (CB- CBB

-1B)xB +(CN- CBB

-1N)xN

Il suffit de vrifier le signe des coefficients de xN dans la dernire ligne du tableau

Corollaire

Soit x une SBR associe la base B. Sil existe une variable Hors Base xe/ e 0 (cela reprsente le taux damlioration de la fonction objectif si la variable xe devient une variable de Base) alors

Soit loptimum du PL est non born Soit il existe une SBR y associe une base B/ cy cx ; x et y deux solutions de

bases ralisables adjacentes. En fait, on se dplace dune base une autre adjacente :

Si la SBR est non dgnre, le dplacement implique un point extrme adjacent ;

Si la SBR est dgnre la base change mais on reste au mme point extrme (une nouvelle variable nulle).

Sans perdre de gnralit, on va supposer que

m

2

1

B

x

x

x

x

et

n

2m

1m

H

x

x

x

x

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 1 am,m+1 am,n

b1 .

.

bm

-z 0 0 0 m+1 n cB B-1

b

= 0 : Coefficient de xB dans la

dernire ligne du tableau

Coefficient de xN dans la

dernire ligne du tableau



16 Hanen Bouchriha

O

j,m

j,2

j,1

1

j,m

j,2

j,1

a

a

a

B

a

a

a

Pour se dplacer dune SBR une autre, une variable hors base va prendre la place de lune des variables de base. 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

cB B-1

b = z

Questions : quelle est la variable entrante ?

Pour dterminer une nouvelle SBR on choisit de considrer la solution de base ralisable adjacente correspondant la base B et contenant xj / j = Max {k, k = m+1n } (k tant un indice relatif une variable Hors Base)

1er critre de DANTZIG

xj est appele variable entrante (quon note xe) xj prendra la place dune autre variable de base dans la base B. Cette variable est dite

variable sortante (xs)

Pour faire entrer xe, on augmente sa valeur de en gardant les autres variables hors bases nulles. Deux questions se posent :

Question 1 : De quelle valeur augmente-t-on la variable entrante xe ? Question 2 : Quelle sera la nouvelle variable sortante xs ?

Rponse 1 :

2me

critre de DANTZIG ou critre du ratio minimal

Avec :

: coefficient du second membre du tableau canonique relatif la base B

: coefficient de la variable xe dans la ie ligne du tableau canonique relatif la base B

Rponse 2 :

xs /

0/min ...1 ieie

i

mi aa

b

ib

iea

0/min ...1 ieie

i

mise

sa

a

b

a

b



17 Hanen Bouchriha

Preuve

On dsire augmenter xe le maximum possible, tout en satisfaisant les contraintes. Pour chaque

contrainte i, on a :

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

xe = xi = bi - ai,e

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

Si ai,e 0 alors bi/ai,e

la valeur maximale de qui satisfait toutes les contraintes est

= min {bi/ai,e : i = 1, , m et ai,e > 0}

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

En effet, pour la ligne s, on a : xs = bs - as,e (bs/as,e) = 0. Do xs devient la variable sortante.

Dfinition

- as,e est appel lment pivot - Ligne s : ligne pivot - Colonne e : colonne pivot

Dterminer la nouvelle SBR relative la base B= (x1, x2,,xe,,xm) Il faudra retrouver la forme canonique associe B. Il sagit de transformer la colonne relative xe comme suit :

s

a

a

a

em

es

e

Ligne

0

1

0

,

,

,1

Pour cela, il faut appliquer les oprations lmentaires (Gauss-Jordan) :

- Opration 1 : Diviser la ligne Pivot par llment pivot se asj as,j/as,e j

En particulier, ase = 1 - Opration 2 Pour toute ligne diffrente de la ligne Pivot, soustraire cette ligne un multiple approprie de

la ligne pivot pour annuler le coefficient de la ligne i correspondant la colonne pivot

aij aij - aie as,j/as,e j

En particulier, aie = 0

Aussi, pour la ligne qui correspond la fonction objectif, on a : j j - e as,j/as,e j



18 Hanen Bouchriha

7. Exemple dapplication

On propose ici de reprendre lexemple du chapitre 1 et de le rsoudre par la mthode du simplexe.

Max Z=3 x1 + 5 x2

Sous les contraintes :

x1 4

2 x2 12

3 x1 + 2 x2 18

x1 0, x2 0

Tout dabord, on crit la forme standard associe ce PL : Max Z=3 x1 + 5 x2

Sous les contraintes (s.c.) :

x1 + s1 = 4

2 x2 + s2 = 12

3 x1 + 2 x2 + s3 = 18

x1, x2, s1, s2 , s3 0

On retrouve une forme canonique, on dresse alors le premier tableau de simplexe

correspondant

# 1 x1 x2 s1 s2 s3 bi

s1 1 0 1 0 0 4

s2 0 2 0 1 0 12 s3 3 2 0 0 1 18

-z 3 5 0 0 0 0

# 2 x1 x2 s1 s2 s3 bi

s1 1 0 1 0 0 4

x2 0 1 0 1/2 0 6

s3 3 0 0 -1 1 6

-z 3 0 0 -5/2 0 -30

# 3 x1 x2 s1 s2 s3 bi

s1 0 0 1 1/3 -1/3 2

x2 0 1 0 1/2 0 6

x1 1 0 0 -1/3 1/3 2

-z 0 0 0 -3/2 -1 -36

Tableau optimal

La solution optimale est : x*1=2, x

*2=6, s

*1=2, s

*2=s

*3=0 et z*=36



19 Hanen Bouchriha

8. Algorithme simplexe (rsum)

- Mettre le PL sous la forme standard - Trouver une SBR ralisable - crire le PL sous la forme canonique relative la SBR considre - Faire les itrations suivantes

Tester loptimalit : si le critre darrt est satisfait, donner le rsultat final, sinon aller ltape suivante.

Dterminer la variable entrante (colonne pivot) selon le premier critre de DANTZIG.

Dterminer la variable sortante (ligne pivot) selon le deuxime critre de DANTZIG

Calculer le nouveau tableau canonique en effectuant les oprations ncessaires.

9. Mthode simplexe pour un problme de minimisation

Nous pouvons procder de deux manires :

Minimiser (Z) Maximiser (-Z) et appliquer la dmarche vue pour un problme de maximisation

Minimiser Z directement. Dans ce cas : Le critre doptimalit devient

Si j 0 j = 1,n alors la SBR actuelle est optimale

Si il existe k / k 0 et aik 0 i, le problme est non born. Le critre de choix de la variable entrante est celle qui correspond au

cot rduit le plus ngatif.

10. Mthode du simplexe deux phases La mthode simplexe part dun PL sous la forme canonique. Cela suppose quon peut facilement identifier une SBR initiale. Parfois ce nest pas vident de trouver une SBR initiale. Dans ce cas, on applique la mthode du simplexe deux phases

Soit le (PL) :

Max Z = 4x1 + 3x2 s.c. 2x1 - x2 15 x1 + x2 = 10

2x1 - x2 20 x1, x2 0

La forme standard est :

Max z = 4x1 + 3x2 s.c. 2x1 x2 e1 = 15 x1 + x2 = 10

2x1 x2 + s3= 20

x1, x2, e1, s3 0



20 Hanen Bouchriha

A vue dil, cest difficile de trouver une SBR. Alors, quest-ce quon fait ?

On introduit des variables dites artificielles chaque contrainte et chaque contrainte =, on obtient alors (PL): Max z = 4x1 + 3x2 s.c. 2x1 x2 e1 +s1 = 15

x1 + x2 +s2 = 10 2x1 x2 + s3= 20

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

Une SBR de (PL) est donne par les variables de base (s1,s2, s3). Or, les variables artificielles doivent tre nulles dans une SBR de PL (si une variable artificielle est non nulle,

ceci indique que la solution est non ralisable pour PL)

On doit donc essayer dannuler les variables artificielles dans (PL) Pour cela, nous allons appliquer la mthode simplexe pour le (PL)1 constitu des mmes

contraintes que le problme initiale et dont lobjectif sera de minimiser la somme des variables artificielles. Cela reprsente la phase I de la mthode simplexe deux phases.

(PL)1 :

Min Z1 =s1 +s2

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

x1 + x2 +s2 = 10 2x1 x2 + s3 = 20

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

Rsultats possibles de la phase I :

Cas 1 : z1 0 au moins unesi 0 PL non ralisable

Cas 2 : z1 = 0 et aucune variable artificielle nest une VB. Dans ce cas: on limine toutes les colonnes du tableau optimal de la phase I, qui correspondent aux

variables artificielles.

On introduit la fonction objectif de (PL) avec les autres lignes de ce tableau. On met jour la dernire ligne de telle manire avoir j = 0 pour les VB. do le tableau canonique initial de (PL). On continue alors la rsolution avec la mthode de Simplexe (Phase II).

Cas 3 : z1= 0 et au moins une si est une VB du tableau optimal de la phase I. Dans ce cas, le problme original (PL) a au moins une contrainte redondante

Eliminer les contraintes redondantes ; Rintroduire de la fonction objectif initiale

commencer la phase II. Dans le cas 3, on trouve une ou plusieurs lignes o tous les coefficients sont nuls sauf ceux

des variables artificielles ces lignes sont redondantes et peuvent tre limines.

Exemple



21 Hanen Bouchriha

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

La ligne 2 peut tre limine.

Nous revenons lexemple plus haut et nous appliquons la mthode du simplexe deux phases.

Phase I :

# 1 x1 x2 e1 s3 s1 s2 bi

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

3 0 -1 0 0 0 25

# 2 x1 x2 e1 s3 s1 s2 bi

x1 1 -1/2 -1/2 0 1/2 0 25/2

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

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

# 3 x1 x2 e1 s3 s1 s2 bi

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 1 0 0 -1 -1 0

Tableau optimal de la phase I

La solution optimale de la phase I est : z = 0 et aucune variable artificielle nest une variable de base. On omet alors les colonnes correspondant aux variables artificielles, on met la

fonction objectif de PL la dernire ligne et on procde sa mise jour pour obtenir un

premier tableau canonique de PL. Puis, on entame la phase II de la rsolution.



22 Hanen Bouchriha

Phase II :

# 4 x1 x2 e1 s3 bi

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 0

0 0 1/3 0 -115/3

# 5 x1 x2 e1 s3 bi

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

Tableau optimal de la phase II

La solution optimale est : z*=40 avec x

*1=10, x

*2=0, e

*1=5 et s

*3=0.

11. Cas particulier

11.1 PL non born

Des solutions ralisables peuvent tre trouves et la valeur de z peut toujours tre amliore.

Dans le cadre du simplexe, ce cas est reprsent par le fait qu'il est impossible de faire entrer

dans la base des variables telles que j > 0. Ceci est d au fait que dans chacune de ces

colonnes j, aij 0 pour tout i. Gomtriquement, cela correspond un rayon extrmal (une demi-droite) sur lequel z(x) peut augmenter infiniment.

Soit xe la variable vrifiant le 1er critre de DANTZIG :

xe = xi = bi aie i= 1, , m

Si pour tout i, aie 0, on pourra augmenter la valeur de xe infiniment tout en respectant

xi =bi aie 0.

bi pente = -aie



23 Hanen Bouchriha

Le rayon extrmal est donn par :

- Le point de coordonnes

- La direction

Exemple:

max z = x1 + 2x2

s.c. 7x1 + 2x2 28

x1 + 6x2 12

x1, x2 0

11.2 PL ayant une infinit de solution

Dans le tableau canonique optimal, lune des variables hors base correspond un j =0. Si on fait entrer xj dans la base, on obtient une autre SBR sans que la valeur de la fonction objectif

change. Le segment form par ces deux SBRs optimales contient toutes les solutions

optimales du problme.

Exemple

Max Z = 3x1 + 2x2 s.c. 3x1 + 2x2 120

x1 + x2 50

x1, x2 0

mb

b

1

em

e

a

a

,

,1


Dualit

24 Hanen Bouchriha

Chapitre 3 : Dualit

1. Introduction

Soit (P) le programme linaire suivant :

Max Cx

Sc Ax = b

x 0 A chaque programme P (dit problme primal) on associe un programme D (dit problme

dual) o chaque variable du dual est associe une contrainte du problme primale.

La dualit est une relation trs importante car :

- Elle permet de caractriser loptimum. - Proposer des algorithmes de rsolution rapide. - Permet davoir une interprtation conomique importante.

2. Interprtation conomique de la dualit

2.1 Le dual dun problme de Maximisation

Une compagnie de meuble produit des :

- bureaux - tables - chaises

Elle utilise des ressources :

- Matire premire (exprime en plaque de bois) - Activit de menuiserie (exprime en heure) - Activit de finition (exprime en heure)

Le tableau suivant prsente les donnes du problme

Lobjectif est de dterminer les quantits produire de faon maximiser le profit.

Les variables de dcision sont dfinies comme suit :

x1 : nombre de bureau

x2 : nombre de table

x3 : nombre de chaise

Le programme linaire (P) qui correspond ce problme est :

Ressources

Produit

Quantit disponible bureau table chaise

Bois (plaque) 8 6 1 48

Menuiserie (h) 2 1,5 0,5 8

Finition (h) 4 2 1,5 20

Prix de revient (D/unit) 60 30 20


Dualit

25 Hanen Bouchriha

Max 60x1 + 30x2 + 20x3 SC 8x1 + 6x2 + x3 48 Bois 2x1 + 1.5x2 + 0.5x3 8 Menuiserie 4x1 + 2x2 + 1.5x3 20 Finition x1, x2, x3 0

On suppose quun entrepreneur peut acheter la compagnie de meuble et ses ressources. Pour cet entrepreneur :

- Lobjectif : le prix total de ces ressources est minimal mais - Les contraintes il doit payer suffisamment pour convaincre meuble de lui vendre ses

ressources (au moins couvrir le prix de revient de chaque produit.

Le problme linaire qui correspond ce nouveau problme est comme suit :

- Variables de dcision y1 : prix dune plaque de bois. y2 : prix dune heure de menuiserie. y3 : prix dune heure de finition.

- Fonction Objectif : Lentrepreneur paye w(y) = 48y1 + 8y2 + 20y3 Minimiser w(y).

- Contraintes : Meubles peut utiliser 8 units de bois pour fabriquer un bureau et le vendre 60D pour

convaincre la compagnie de vendre, lentrepreneur doit payer cette combinaison un prix dau moins 60D. Do :

8y1 + 2y2 + 4y3 60

De mme, on a :

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

De plus, on a les contraintes de signe :

y1, y2, y3 0

y1, y2, y3 sont dits Cots fictifs ou prix dombre

Min w = 48y1 + 8y2 + 20y3

8y1 + 2y2 + 4y3 60 6y1 + 15y2 + 2y3 30 y1 + 0.5y2 + 1.5y3 20 y1, y2, y3 0

(D) est le programme linaire associ (P).

(D)


Dualit

26 Hanen Bouchriha

2.2 Le dual dun problme de minimisation (Problme de rgime alimentaire)

Une famille peut prparer un menu quilibr cot minimal. Le menu est constitu de 6

aliments et doit contenir au moins 9 units de vitamine A et 19 units de vitamines B.

La composition des diffrents aliments en vitamine est reprsente par le tableau suivant :

Nombre d'units de vitamine /Kg

d'aliment

1 2 3 4 5 6

Nombre minimum d'units requises

/jour

Vitamine A

Vitamine C

1 0 2 2 1 2

0 1 3 1 3 2

9

19

Cot de

l'aliment

(x10M/kg)

35 30 60 50 27 22

On dsigne par xi = nombre de kg daliments i prpar

Le programme linaire correspondant ce problme est :

Min 35x1 + 30x2 + 60x3 + 50x4 + 27x5 + 22x6 (* 10 M)

Sv x1 + 2x3 + 2x4 + x5 + 2x6 9 x2 + 3x3 + x4 + 3x5 + 2x6 19

xi 0, i = 1 .6

Un fabriquant compte lancer un projet. Il propose de fabriquer des comprims de chaque

vitamines et les vendre la famille. Le fabriquant doit convaincre la famille dobtenir les quantits requises des vitamines en utilisant ses comprims au lieu des aliments tout assurant

un prix comptitif des vitamines par rapport aux aliments que cette famille utilisait.

Nous dfinissons ainsi le programme linaire suivant associ ce nouveau problme :

- Variables de dcision : y1 : prix dune unit de vitamine A y2 : prix dune unit de vitamine B

- Fonction objectif : Le fabriquant dsire maximiser son profit. Do la fonction objectif :

Max w(y) = 9y1 + 19y2

- Contraintes : Si on prend laliment 5 ; il contient 1 unit du vitamine A et 3 du vitamine B. Pour convaincre la famille dacheter il faut que le prix quelle paye pour les comprims correspondant cet aliment soit infrieur ou gale 27 (prix de prparation de laliment). Do :

y1 + 3y2 27 De mme pour les autres aliments.


Dualit

27 Hanen Bouchriha

Le problme Dual associ est donc :

Max w(y) = 9y1 + 19y2 Sc y1 35

y2 30 2y1 + 3y2 60 2y1 + y2 50 y1 + 3y2 27 2y1 + 2y2 22 y1, y2 0

2.3 Constatations sur les formes du Primal et du Dual :

A partir des exemples ci-dessous, nous pouvons conclure quil y a des relations entre le problme primal (P) et le problme dual (D) correspondant dfinies comme suit :

- La matrice des coefficients des contraintes de D est la transpose de P et vice-versa.

- Les composants du second membre de D sont les coefficients de la fonction objective de P et vice-versa.

- Les coefficients de la fonction objectif de D sont les coefficients de second membre de P et vice-versa

- Chaque colonne (ou variable) de P rsulte en une contrainte dans D et vice-versa.

- Chaque contrainte de P correspond une variable dans D et vice-versa.

- Si P est un problme de maximisation avec contraintes alors D est un problme de minimisation avec contraintes et vice-versa.

- Si on considre le second exemple, la famille ne va acheter les comprims que sils contiennent la quantit ncessaire de vitamine et que le prix quelle paye et au plus au mme prix que le prix de prparation des aliments normaux. Do la relation : Max W(y) Min Z(x) (Faible dualit)


Dualit

28 Hanen Bouchriha

3. Rgles de dtermination du dual partir dun programme linaire :

3.1 Dual partir dune forme normale :

Nous dfinisson deux formes normales pour un programme linaire :

- maximisation avec contraintes 0, x 0 - minimisation avec contraintes 0, x 0

Soit (P) :

.

Alors le dual (D) associ est

3.2 Dtermination du dual partir dun LP contraintes mixtes

Si le primal (P) est sous forme gnrale, on peut construire son dual (D) de deux faons

diffrentes :

a- Mettre P sous la forme normale Exemple : Pour un problme de maximisation

- Multiplier chaque contrainte par (-1) - Remplacer aix = bi par aix bi et - aix - bi

- Remplacer chaque xj rel (xj0) par ( jj xx )

b- Appliquer les rgles suivantes :

Primal Dual

Fonction maximiser Fonction minimiser

ime contrainte 0 ime contrainte 0 ime contrainte = 0

ime variable 0 ime variable 0 ime variable 0

jme variable 0 jme variable 0 jme variable 0

jme contrainte 0 jme contrainte 0 ime contrainte = 0

nm R ,;R b

n)(m matrice uneA Avec

0, x

bAx Sc

Cx

xC

Max

ligne un vecteur:R y

Avec

0,y

CyA Sc

yb w

m

Min


Dualit

29 Hanen Bouchriha

Exemple 1 :

(D) Min W = 2y1 + 3y2 + y3

Sc y1 + 2y2 + y3 2 y1 - y2 - y3 = 1

y1 0, y2 0, y3 0

Exemple 2 :

(D) Max w = 7y1 + 14y2 3y3 Sc y1 + 6y2 2y3 5 2y1 3y2 - 17y3 -6 -y1 + y2 + 4y3 = 7

-y1 + 7y2 + 2y3 = 1

y1 0, y2 0 y3 0

4. Dualit et condition doptimalit :

Soit :

(P) Max Cx (D) Min w = yb Sc Ax = b Sc yA C x 0 y = 0

4.1 Lemme fondamental (faible dualit) :

Soit K1 et K2 Domaine ralisable de P et D respectivement

xK1, yK2 Yb Cx

0 ; 0

1

3 2

2 Sc

2Max

21

21

21

21

21

xx

xx

xx

xx

xxZ

0 ; 0 ; 0 ; 0

324172-

14736

72 Sc

765Min

4321

4321

4321

4321

4321

xxxx

xxxx

xxxx

xxxx

xxxxZ

(P)

(P)


Dualit

30 Hanen Bouchriha

Dmonstration

yK2 yA c

x K1 x 0

yAx cx do yb cx

Implications:

w* Z(x) x K1

w(y) Z* y K2

En particulier, on aura : w* z*

Faible dualit Si on connat une solution ralisable quelconque de lun des problmes (P ou D), la faible dualit peut tre utilise pour obtenir une borne (inf ou sup) sur la valeur de la

fonction objectif de lautre

4.2 Thorme de la forte dualit :

Soit x*K1, loptimum de P

des solutions x*K1 et y*K2 / Cx*=y*b

Et on peut dmontrer dans ce cas que y* nest que loptimum de D

Dmonstration :

? x

* est loptimum de P

= C CB B-1 A 0 => CB B

-1 A C

et Z* = CB B

-1 b = Cx

*

On pose y* = CB B

-1

On vrifie :

y*

A = CB B-1 A C do y* est bien une solution ralisable de D

y*

b = CB B-1

b = Cx*

Maintenant dmentions que y* est loptimum de D

y*

est solution ralisable pour D

=> w* y* b

Daprs la faible dualit w* z* = Cx* = y*b Do w* y* b et w* y*b

w* = y* b do y* est la solution optimale de D

?

Il existe x* K1, y* K2 avec Cx* = y* b (y* est loptimum de D)

Soit x K1, daprs la faible dualit :


Dualit

31 Hanen Bouchriha

Cx y* b

Comme y* b = Cx* donc Cx Cx* x K Ainsi x* est loptimum de P

Rsultat important :

Si x* est la solution optimale pour P alors CBB-1

est la solution optimale de D o B est la base

associ x*

5. Comment dterminer la solution du dual partir du primal?

5.1 partir des cots marginaux :

Cas dun problme de maximisation avec contraintes mixtes

On a = C CB B-1

A

j = Cj CB B-1

Aj

On considre B la base optimale du primal alors CB B-1

est la solution optimale du dual.

On cherche dterminer [(CB B-1

)1, (CB B-1

)2, (CB B-1

)n ]. En effet, chaque contrainte du P

est associ une variable de D.

Pour tout i : 1n

- Si la contrainte i est de type 0 on doit avoir Si dans le primal avec

Si = CSi - (CB B-1

)ASi = - (CB B-1

)

0

...

1

...

0

= - (CB B-1

)i

En effet, CSi = 0 car Si est une variable dcart donc son cfficient est nul dans le vecteur C (Fonction objectif).

- Si la contrainte i est de type 0 on doit avoir ei dans le primal

ei = 0 (CB B-1

)

0

...

1

...

0

(CB B-1

)i = ei

Contrainte i

Contrainte i


Dualit

32 Hanen Bouchriha

- pour toute contrainte de type = il faut utiliser la forte dualit Cx* = y*b

5.2 A partir du tableau canonique :

Comment dterminer (B-1

) partir du tableau canonique ?

Cas dun problme de maximisation avec contraintes 0

Tableau initiale : B0 est forme par les variables dcarts => une matrice identit qui correspond aux variables de base (Forme canonique)

Tableau optimale : La base B est obtenue en effectuant des transformations linaires sur le

tableau initial. Il sagit de multiplier par B-1 gauche pour la partie relative aux contraintes (ainsi on a Im qui correspond au variables de base).

XB XN * B-1 XB Xn

B N b I B-1N

CB CN 0

Si on a la forme standard, on aura N = I(n-m) (les variables dcarts correspondent aux variables de base dans le tableau initiale). Do B-1 est la matrice du tableau actuel qui correspond aux variables de base dans le tableau initial.

Exemple :

B1 = (S1, S2, S3) = I3

B1-1

= I3

#2 X1 X2 X3 S1 S2 S3

S1 0 0 -1 1 -4 0 16

X1 1 0.75 0.25 0 0.5 0 4

S3 0 -1 0.5 0 -2 1 4 j 0 -15 5 0 -30 0 -240

140

020

081

2B

120

02/10

0411

2B

#1 X1 X2 X3 S1 S2 S3

S1 8 6 1 1 0 0 48

S2 2 1.5 0.5 0 1 0 8 S3 4 2 1.5 0 0 1 20

j 60 30 20 0 0 0 0


Dualit

33 Hanen Bouchriha

La base B2 est forme par (S1, x1, S3)

#3 X1 X2 X3 S1 S2 S3

S1 0 -1 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

Cest le tableau optimal

B3 est la base forme par S1, x1, x3

2/340

2/120

181

3B

240

2/12/30

2811

3B

13B intervient dans le calcul de y*

CB3 = [0, 60, 20]

CB B-1

= [0 60 20]

240

2/12/30

281

= [0 (3/2 * 60 4 * 20) (-1/2 * 60 + (2 * 20))]

= [0 10 10 ]

y1 = 0

y2 = 10

y3 = 10

On vrifie avec le calcul des

S1 = 0 = -y1 S2 = -10 = -y2 S3 = -10 = -y3


Dualit

34 Hanen Bouchriha

5.3 Thorme de complmentarit :

(P) Max Cx (D) Min yb

Sc ax b Sc ya c x 0 y 0 x1, x2 .xn y1, y2,yn n contraintes n contraintes

Sn, S2.Sn (variables dcarts) e1, e2,.en (variables dcarts)

x D (P)

y D (D)

x et y sont optimaux de (P) et (D) respectivement Si yi = 0 i 1.m ej xj = 0 j 1.n

Preuve :

Si aij xj < bi (Si > 0) => ressources partiellement utilise => yi 0 Si xj > 0 => il ne faut pas offrir des prix assez leve sinon cela va coter cher lentreprise => le juste ncessaire yi aij = cj (ej = 0)

Application de ce thorme celle dusine de meubles

Rsolution du primal => S1 > 0 => y1 = 0

x1 = 2 > 0 => e1 = 0

X3 = 8 > 0 => e3 = 0

Do la solution du dual :

(1) 8y1 + 2y2 + 4y3 - e1 = 60

(2) 6y1 + 1.5y2 + 2y3 - e2 = 30

(3) y1 + 0.5y2 + 1.5y3 - e3 = 20

(1) => y2 + 2y3 = 30

(3) => y2 + 3y3 = 40

y3 = 10 y2 = 10

(2) => e2 = 5


35 Hanen Bouchriha


Thorie de graphe : Dfinitions et Concepts de base

36 Hanen Bouchriha

Chapitre 5 : Dfinition et concepts de base

1. Introduction

La thorie des graphes est un domaine des mathmatiques, qui constitue lun des instruments les plus courants et les plus efficaces pour rsoudre des problmes discrets poss en

Recherche Oprationnelle (RO). Un graphe permet de reprsenter simplement diffrents

problmes ayant une criture formelle complique. De manire gnrale, cet outil de

modlisation est utilis pour reprsenter simplement la structure, les connexions, les

cheminements possibles dans un systme complexe en exprimant les relations entre ses

composantes (par exemple, un rseau de communication, un rseau routier ou ferroviaire, une

structure en chimie, diagramme de succession de tches n gestion de projet ).

2. Dfinitions et concepts de base

Graphe :

Un graphe ou rseau est un ensemble de points ou sommets relis par des lignes appeles arcs

G = (X, U) avec

X : ensemble discret, fini de sommets ou nuds U : ensemble darcs constitu par des paires de sommets (i, j) de X

Si N = |X| est le nombre de sommets alors G est dordre N

Arc et graphe orient :

Un arc u = (i,j) est dit orient si i est son extrmit initiale et j son extrmit terminale.

- u est incident extrieurement au sommet i et incident intrieurement j. - i est un prcdent ou prdcesseur de j et j est un suivant ou successeur de i.

Lensemble des successeurs de i est not (i) ; lensemble des prdcesseurs de i est not

-1(i).

Un graphe est dit orienter si tous ses arcs sont orients

Un arc est non orient si le flux correspondant est bidirectionnel. On parle darrte est non plus darc.

3. Graphe partiel et sous graphe :

Graphe partiel

Un graphe Gp=(X, Up) est un graphe partiel du graphe si UpU

Exemple : G graphe reprsentant les routes de France, celui qui reprsente les routes

nationales de France est un graphe partiel



37 Hanen Bouchriha

Sous graphe

G=(X, U) est un graphe, S X. Un sous graphe Engendr par S est constitu de sommets contenus dans S et darcs (ou arrtes) dont les extrmits sont dans S

Exemple :

G graphe reprsentant les routes de France, celui qui reprsente les routes de la Bretagne est

un sous graphe.

4. Chane cycle chemin - circuit :

Chane cycle :

Une chane entre deux nuds est une squence dartes telle que chaque arte de la squence ait une extrmit commune avec larte suivante

Un cycle est une chane dont les extrmits concident

Chemin circuit :

Un chemin est une chane dont les arcs sont orients dans le mme sens

Un circuit est un chemin dont les extrmits concident.

Exemple :

- Le graphe reprsent par les arcs (C, A), (C, E) et (E, D) reprsente une chane reliant A et D

- Le graphe reprsent par les arcs (A, B), (B, C), (C, E) et (E, D) reprsente un chemin reliant A et D

- (C, B), (B, D), (E, D) et (C, E) constituent un cycle - (A, B), (B, C) et (C, A) constituent un circuit

A

B

C

D

E



38 Hanen Bouchriha

5. Matrices associes un graphe :

Matrice dincidence sommets arcs

Soit G = (X,U), N = Nombre de sommets, M tant le nombre darcs

La matrice dincidence sommets arcs : A=(aij) (i=1..N et j=1..M) est dfinie par : - Chaque colonne correspond un arc de G - Chaque ligne correspond un sommet de G.

- A est coefficients entiers 0 ou 1 ou 1 / Si u= (i,j) U, la colonne u a tous ses termes nuls sauf aiu = +1 et aju = -1

Matrice dincidence sommets arrte

Soit G = (X,U), N = Nombre de sommets, M tant le nombre darrte

La matrice dincidence sommets arrte : A=(aij) (i=1..N et j=1..M) est dfinie par : - chaque colonne correspond une arrte de G - chaque ligne correspond un sommet de G.

- A est coefficients entiers 0 ou +1 / si u=(i,j) U, la colonne u a tous ses termes nuls sauf aiu = +1 et aju = +1

Matrice dadjacence sommets-sommets

Soit G = (X, U), N = Nombre de sommets

La matrice dadjacence sommets-sommets est une matrice carre A= (aij) (i=1..N et j=1..N) dfinie par :

- chaque colonne correspond un sommet de G. - chaque ligne correspond un sommet de G. - A est coefficients entiers 0 ou +1 / sil existe un arc u= (i, j) entre les sommets i et j

alors aij = +1 sinon aij = 0



39 Hanen Bouchriha

Exemple :

La matrice dincidence sommet arc est donne par :

10110

11000

01101

00011

La matrice dincidence sommet arrte est donne par :

10110

11000

01101

00011

La matrice dadjacence sommet sommet est donne par :

0100

0000

1100

1001

A B

C D

u2 u3

u4

u5


Problme du plus court chemin

40 Hanen Bouchriha

Chapitre 6 : Problme du pus court chemin

1. Introduction

Soit G=(X,U) ; on associe chaque arc u= (i,j)U un nombre rel quon note l(u) ou lij appel longueur de larc u. On dit alors que le graphe G est valu par les longueurs l(u).

Les longueurs des arcs peuvent correspondre :

des distances physiques, des cots de transport, des dpenses de construction, temps ncessaire une ralisation,

La longueur dun chemin joignant le sommet i au sommet j est donne par : l ()

Le problme de plus court chemin entre deux sommets i et j consiste dterminer un chemin

de i j, (i, j), de longueur minimale.

La longueur dun chemin comprenant un circuit de longueur strictement ngative est non borne (il suffit demprunter ce circuit une infinit de fois). Ce type de circuit est appel circuit absorbant

Labsence dun circuit absorbant constitue une condition ncessaire lexistence dun chemin de longueur minimale

2. Exemples de modlisation par PCC

2.1 Stratgie de remplacement dquipements :

Une mine a une dure totale dexploitation de T annes. Elle utilise un quipement quelle a acquis la date i=0 (quipement neuf).

Au dbut de chaque anne i, deux possibilits soffrent la mine : - garder lquipement en service pendant [i, i+1] - revendre cet quipement un prix de rcupration de v(x) avec x est son ge et acheter

un quipement neuf au prix p (i)

Le cot dune anne de fonctionnement r(x) dpend de lge. Lquipement doit tre vendu la date T.

Dterminer la politique de remplacement de lquipement cot minimal.



41 Hanen Bouchriha

Le problme peut tre reprsent par un graphe comme suit :

- Un sommet est associ chaque date (T+1 sommets). - Un arc qui relie deux sommets i et j reprsente la dcision dacheter un quipement la date

i et le vendre j (j>i).

- La longueur dun arc = (cot dachat + cot de fonctionnement prix de vente)

lij = p(i) v(j-i)+

ij

x

xr

1

)(

- La politique de remplacement de lquipement cot minimal est reprsent par le plus court chemin de 0 T.

2.2 Optimisation des achats

Le service dachat doit assurer lapprovisionnement pendant T priodes pour raliser un programme de production. Le prix dachat p(t) dpend de la priode dapprovisionnement t.

Afin de tirer profit de la variation des prix, lentreprise peut : - Acheter la matire en t et constituer des stocks. Le cot unitaire de stockage est h (t) en

la priode t.

- Reporter sa demande moyennant une pnalit de retard. p est la pnalit de reporter une unit de la demande pendant une priode.

Dterminer le plan dapprovisionnement cot minimal.

0 1 2 T



42 Hanen Bouchriha

Le problme peut tre reprsent par un graphe comme suit :

- X = S {t, t =1,.., T} (T+1 sommets) - Un arc (S,t) correspond la dcision dacheter en la priode t. lst = p(t) - Tout sommet t (t =1,.., T-1) est reli t+1. Larc (t,t+1) correspond la dcision de

stocker pendant la priode t et a une longueur de h(t)

- Tout sommet t (t =2,.., T) est reli t-1. Larc (t, t-1) correspond la dcision de reporter la demande de la priode t la priode t-1 et a une longueur de p.

- La Politique optimale dapprovisionnement correspond la recherche du plus court chemin entre S et tous les sommets du graphe

3. Algorithmes de rsolution :

3.1 Principe doptimalit de Bellman :

Thorme :

Soit un chemin entre i et j de longueur optimale. Toute partie 1 de reliant un sommet h

un sommet l est alors de longueur optimale.

Ce thorme permet de conclure que le chemin optimal est compos de sous chemins

optimaux.

Dmenstration :

Pour dmontrer ce thorme on peut raisonner par labsurde : tant un chemin entre i et j de longueur minimale. On suppose quil existe une partie 1 de joignant h l qui nest pas de longueur minimale. Il existe alors un chemin 2 de h l tel

que l(1)l(2). Le graphe identique sauf pour la partie 1 qui est remplace par 2, est alors de longueur infrieure celle de ; ce qui contredit lhypothse de dpart.

1 2 3 T

S

p(1) p(2) p(3)

p(4)

h(1))) (1)

h(2)

p p p



43 Hanen Bouchriha

Illustration :

Soit (5) : La longueur du plus court chemin entre 1 et 5

(5) = min {(2) + l25 ; (3) + l35 ; (4) + l45}

3.2 Classification des algorithmes de recherche de PCC

Les algorithmes de rsolution du problme de recherche du plus court chemin seront

diffrents suivant.

les proprits du graphe :

- graphe valu par des longueurs positives.

- graphe valu par des longueurs de signes quelconques.

- graphe sans circuit.

le problme considr :

- recherche du plus court chemin dun sommet un autre. - recherche du plus court chemin dun sommet tous les autres. - recherche du plus court chemin entre tous les couples de sommets.

3.3 Cas dun graphe valu par des longueurs positives : Algorithme de Dijkstra-Moore (1959):

Cet algorithme permet la recherche du plus court chemin partant dun sommet (not 1) tous les autres sommets du graphe.

Les sommets sont partitionns en deux sous-ensembles

- P : ensemble de sommets ayant une tiquette permanente

- T = X-P : ensemble de sommets ayant une tiquette temporaire

chaque itration un sommet est transfr de T vers P. Lalgorithme converge en n-1 itrations (n tant lordre du graphe G=(X,U))

On dsigne par (x) : la longueur du plus court chemin entre le sommet 1 et le sommet x. Le calcul des plus courtes distances se fait de proche en proche par ajustements successifs.

1

2 3

4 5



44 Hanen Bouchriha

Algorithme de Dijkstra-Moore (1959):

Etape 1 : Initialisation

(1)=0 P={1}

T={2, , N}

i T, (i)= l1i si (1,i) U

= sinon

Etape 2 :

Slectionner j T tel que (j)= )(min iTi

Faire : T=T\{j}

P=P{j}

Si T = alors fin sinon aller ltape 3.

Etape 3 :

i T tel que (j,i)U faire : (i) min ((i), (j)+ lji) (Principe doptimalit de Bellman)

Aller ltape 2.

Exemple

Une entreprise doit distribuer la marchandise ses clients situs aux nuds 2 6. La distance parcourir dun point un autre et le sens de circulation sont indiqus dans la figure ci-contre.

Dterminer les plus courts chemins entre 1 et 2 et entre 1 et 6 ?

1

2

3

5

6

4

70

10

40 50

20

3050

40

10

20



45 Hanen Bouchriha

Etape 1 :

(1)=0, (2)=70, (3)=10, (4)= (5)= (6)= P= {1}, T= {2, 3, 4, 5, 6}

Etape 2 :

j=3

P= {1, 3}, T= {2, 4, 5, 6}

Etape 3 :

(2)=min {70, 10+50} = 60

(5)=min {, 10+20} = 30

(6)=min {, 10+40} = 50 Etape 2 :

j=5

P= {1, 3,5}, T= {2, 4, 6}

Etape 3 :

(2)=min {60, 30+20}= 50

(4)=min {, 30+50} = 80

(6)=min {50, 30+30} = 50 Etape 2 :

j=6

P= {1, 3,5,6}, T={2, 4}

Etape 2 :

j=2

P= {1, 3,5,6,2}, T={4}

Etape 3 :

(4)=min {30+50,50+40} = 80 Etape 2 :

j=4

P= {1, 3, 5, 6, 2,4}, T=

Fin de lalgorithme

On peut reprsenter le calcul sous forme de tableau comme suit :

Itration 1 2 3 4 5 6

1 - 70 10 2 - 60/3 - 30/3 50/3

3 - 50/5 - 80/5 - 50/3

4 - 50/5 - 80/5 - -

5 - - - 80/5 - -

Le plus court chemin de 1 2 est 1, 3, 5, 2 de longueur 50.

Le plus court chemin de 1 6 est 1, 3, 6 de longueur 50.



46 Hanen Bouchriha

3.4 Cas dun graphe valu par des longueurs de signes quelconques

Cet algorithme sapplique pour un graphe ayant des cots quelconques. Il permet la recherche du plus court chemin entre un sommet et tous les autres.

Il y a convergence en absence de circuit absorbant.

Il sagit de dterminer le plus court chemin de proche en proche en calculant chaque itration le plus court chemin un sommet donn i en utilisant les plus courts chemins tous

les prdcesseurs de i (Processus itratif)

Dans lalgorithme, m reprsente lindice de litration et m (i) est le plus court chemin entre le sommet 1 et le sommet i calcul litration m.

Algorithme de BELLMAN

Soit G = (X,U) un graphe dordre N


- m=1

- 1(1)=0

- j # 1 1 (j) = l1j si (1,j) U

= + sinon

Etape 2 :

Tant que {m N-1} et { j / m (j) < m-1 (j) } Faire Dbut

m+1 (j) = min (m (j) , jk#

min { m (k) + lkj } )

m=m+1

Fin

Remarque : Lalgorithme converge en N-1 itrations.

Si m=N et il existe j / m (j) < m-1 (j) il existe un circuit de longueur ngative (circuit absorbant)

Exemple :

Un agent commercial se trouvant la ville S dcide de participer une foire la ville T. Pour

cela, il doit emprunter le rseau routier donn par la figure ci-contre. Lagent commercial a estim le cot de son transport ainsi que les bnfices rapportes par la vente de produits aux

diffrentes villes intermdiaires. Sur le graphe, les dpenses ont t reprsentes par des

longueurs positives ; les bnfices raliss ont t reprsents par des longueurs ngatives.



47 Hanen Bouchriha

Trouver le chemin emprunt par lagent permettant de minimiser ses cots nets

Application :

Itration O A B C D E T

1 0/O 2/O -5/O 4/O + + +

2 0/O 2/O -6/A 4/O -1/B -2/B +

3 0/O 2/O -6/A 4/O -3/E -3/B 4/D

4 0/O 2/O -6/A 4/O -4/E -3/B 2/D

5 0/O 2/O -6/A 4/O -4/E -3/B 1/D

Le chemin le plus court est O A B E D T de cot = 1

3.5 Cas dun graphe sans circuit :

Dans un graphe sans circuit, il existe au moins un sommet ne possdant aucun prcdent,

sinon G possderait un circuit. Ce sommet est appel racine du graphe. Soit 1 ce sommet

Dans un graphe sans circuit, il existe au moins un sommet ne possdant aucun successeur,

sinon G possderait un circuit.

Dans le cas dun graphe sans circuit, il y a un algorithme plus simple de recherche du plus court chemin du sommet 1 tous les autres

S

A

C

D

E

T

4

2

7

-1

4

7

5

B

-8

1

-5

4

3



48 Hanen Bouchriha

Algorithme de dtermination du rang dun sommet :

Dfinition :

On dfinit le rang dun sommet i dun graphe G sans circuit par : - rg(1) = 0, - rg (i) = le nombre darcs dans un chemin allant de 1 i, de cardinalit maximum.

Algorithme de dtermination des rangs dans un graphe sans circuit :

Etape 1 :

Initialisation : S=X, k=0

Etape 2 :

Sk ={ensemble des sommets sans prcdent dans S}

Pour tout i Sk, rg(i) = k Etape 3 :

S=X-Sk

Si S= fin Sinon

Dbut

Eliminer du graphe tous les arcs ayant pour origine un sommet de Sk

k=k+1,

Retour ltape 2

Algorithme de dtermination du plus court chemin dans un graphe sans circuit :


On pose (1)=0, k=1 et S=X-{iX / rg(i)=0}

Etape 2 :

Sk={ iX / rg(i)=k}

Pour tout i Sk faire

Etape 3 :

Faire S=S- Sk

Si S= fin Sinon faire k=k+1, retour ltape 2

))(()( min),(

ji

Uij

lji



49 Hanen Bouchriha

Exemple

Le plus court chemin de 1 6 ?

rg(1) =0, rg(3)=1, rg(2)=rg(5)=2, rg(4)=3, rg(6)=4.

(1)=0, (3)=4, (2)=min (4+2, 3) =3, (5)=min (4+7)=11, (4)=min (3+1, 11+5)=4,

(6)=min (4+10, 11+2)=13.

Le plus court chemin de 1 6 est : 1, 3, 5 et 6.

1

2 1

2

3

4

5

6

4

3

7

2

10

5


Problme de planification de projet

50 Hanen Bouchriha

Chapitre 7 : Problme de planification de projet

1. Dfinition du problme :

La ralisation dun projet consiste dans lexcution de tches en utilisant des ressources (humaines, matrielles, temps, ). Ces tches sont relies entre elles par des contraintes de prcdence. Lobjectif de ce cours est de dterminer lordonnancement des tches de date dachvement minimale.

A une tche i (i = 1n) nous associons une dure totale dexcution (pi).

On dfinit un arc (i,j) U si la tche i prcde la tche j c'est--dire i doit tre achev avant le dbut de la tche.

Ainsi, il sagit de : - identifier les tches prioritaires - donner pour chaque tche lintervalle de temps durant lequel lexcution doit

avoir lieu pour raliser le projet au plus tt.

2. Le graphe potentiel des tches :

A partir des donnes du projet, on construit le graphe tel que :

- chaque tche i (i = 1n) on associe un sommet du graphe. - on dfinit un arc (i,j) si la tche i prcde la tche j. - la longueur de larc (i,j) reprsente le dure dexcution de la tche i lij = pi - on dfinit deux tches fictives : - i = 0 reprsente la tche de dbut du projet - i = n+1 reprsente la tche de fin du projet avec po = pn+1 = 0

Remarque 1 :

- 0 ne possde pas de prdcesseur - (n+1) ne possde pas de successeur Il sagit dun graphe sans circuit



51 Hanen Bouchriha

3. Mthode du chemin critique

Un chemin entre 0 et (n+1) reprsente une squence ralisable de tches. La date minimale

dachvement est donc gale la dure du plus long chemin entre les sommets 0 et n+1. Ce chemin est dit chemin critique. Les sommets de ce chemin sont les tches critiques du projet.

Les dures de ces tches dterminent la dure minimale de ralisation du projet. Si lune des tches critiques fait un retard, tout le projet sera retard.

3.1 Dtermination de la date minimale dachvement dun projet :

Nous appliquons lalgorithme de recherche du plus long chemin dans un graphe sans circuit (PCC : Max Min)


t0 = 0

tj = p0 si (0,j) U

Etape 1 : Prendre les sommets par rang croissant

Faire ti ij

Max

{tj + pj}

ti reprsente la longueur du plus long chemin entre 0 et i et reprsente aussi la date de dbut au

plus tt de la tche i, en particulier tn+1 est la date minimale dachvement du projet.

3.2 Dtermination des dates de dbut au plus tard :


Tn+1 = tn+1

Etape 1 : Prendre les sommets par rang dcroissant

Faire Ti ji

Min

Tj - pi

Ti reprsente la date de dbut au plus tt de la tche i.

3.3 Marge totale et Marge libre :

- Marge totale de la tche i = Date de dbut au plus tard (i) date de dbut au plus tt (i) mi = Ti - ti

Ainsi, tout retard dune tche i > marge totale de i augmentera autant la date minimale dachvement du projet.

Les tches critiques ont des marges totales nulles. En effet, les tches appartenant au plus long

chemin sont dites tches critiques. Ces tches doivent tre excutes dans les dlais prvus

(marge totale nulle) faute de quoi tout le projet sera retard.



52 Hanen Bouchriha

- Marge libre de la tche i :

Mli = ij

Min

{date au plus tt de j }- pi date au plutt de i

Tout retard suprieur mli retardera autant la date de dbut au plutt de lune des tches suivantes ;

3.4 Exemple :

Tche Dure

Tche

antrieure

1 7 -

2 4 1

3 8 1

4 2 2.3

5 1 2.3

6 2 5

7 1 4.6

- Graphe potentiel tche :

- Dtermination des rangs :

R0 = {1}

R1 = {2,3}

R2 = {4,5}

R3 = {6}

R4 = {7}

R5 = {8}

- Date dachvement au plus tt du projet et calcul des dates de dbut au plus tt :

t1 = 0

t2 = 0 + 7 = 7

t3 = 0 + 7 = 7

t4 = Max {7 + 4, 7 + 8} = 15

t5 = 15

t6 = 16

t7 = Max {15 + 2, 16 + 2} = 18

t8 = 19 : Date minimale dachvement du projet

0 1 2 4 7

3 5 6

80 7

7

4

4

8

8

2

1

2

100 11 22 44 77

33 55 66

880 7

7

4

4

8

8

2

1

2

1



53 Hanen Bouchriha

- Date de dbut au plus tard :

T8 = 19

T7 = 18

T6 = 16

T5 = 15

T4 = 16

T3 = Min {16 8 ; 15 8} = 7 T2 = Min {16 4 ; 15 4} = 11 T1 = Min{7 7 ; 11 7} = 0

- Marge totale :

m1 = 0

m2 = 4

m3 = 0

m4 = 1

m5 = 0

m6 = 0

m7 = 0

m8 = 0

- Chemin critique :

1 2 5 6 7 ( travers lalgorithme de calcul du plus long chemin ou le calcul de mi).

4. Mthode PERT (program evaluation and review technique) :

Cadre dapplication : la dure dxcution dune tche i, pi, est une variable alatoire de

moyenne i et de variance i2

Objectif : dterminer la probabilit de terminer le projet dans un dlai (deadline) sinon des

pnalits peuvent tre encourues.

Donne du problme :

A chaque tche i on associe :

- oi : Dlai optimiste de ralisation de lactivit si toutes les conditions de bon fonctionnement sont runies.

- mi : Dlai le plus probable de ralisation de lactivit. - pi : Dlai le plus pessimiste de ralisation de lactivit si toutes les conditions

dfavorables sont runies.

Rsolution :

a- calcul de i et i pour chaque activit :

La dure de ralisation dune activit est une variable alatoire qui peut tre approche par une loi Bta de paramtres (oi, mi, pi).



54 Hanen Bouchriha

Figure 1 : Loi de distribution de la probabilit li au dlai dachvement dune activit

Etant donne cette approximation, on peut calculer la moyenne de la dure de ralisation

dune activit donne (i) et sa variance (i2) respectivement /

22

6

6

4

op

pmo

i

i

b- Dtermination du chemin critique moyen : Cela correspond au chemin critique (le chemin le plus long) en considrant la dure moyenne

de ralisation de chaque tche

c- Dtermination de la dure moyenne de ralisation du projet (p) et sa variance (p2)/ p = somme des moyennes des dures de ralisation des activits appartenant au chemin

critique moyen.

2p = somme des variances des dures de ralisation des activits appartenant au chemin critique moyen (on suppose ici que les activits du chemin critique moyen sont

statistiquement indpendants).

d- Calcul de la probabilit de terminer le projet dans les dlais :

En supposant un nombre de tches assez important et daprs le thorme de la limite centrale, le dlai de ralisation du projet (dure totale dp) suit la loi normale de moyenne p et

variances 2p

Retour lexemple :

En considrant que les tches ont des dures alatoires dont les moyennes sont celles

considres dans lexemple prcdant, quel est la probabilit de terminer le projet dans un dlai de 21 jours

Tche 1 2 3 4 5 6 7

i 7 4 8 2 1 2 1

i 1.78 1.78 2.78 0.4 0.44 0.5 1



55 Hanen Bouchriha

On trouve p = 19 et 2

p = 12,34. Ainsi dpN(19 ; 3,51)

Prob(dp12) = prob( )51,3

1921

51,3

19(

dp= F(0,56) = 0,71

Avec F est la fonction de rpartition de la loi normale centre rduite.

56 Hanen Bouchriha

Documents

coursROGC2014_2015