Les flots INFORMATIQUE 3 - larbiguezouli.com

INFORMATIQUE 3

http://www.larbiguezouli.com

Classes Préparatoires en Sciences et TechnologiesClasses Préparatoires en Sciences et TechnologiesClasses Préparatoires en Sciences et TechnologiesClasses Préparatoires en Sciences et Technologies

Présenté par Dr Larbi GUEZOULI22

INFORMATIQUE 3

• Introduction à la théorie des graphes [9 Cours + 9 TD]

1. Le concept de graphes2. Algorithmes de base en théorie des graphes

• Le plus court chemin• Les flots

3. Les notions de base des arbres

• Introduction à la programmation linéaire [6 Cours + 6 TD]

1. Le concept de programmation linéaire (variables, contraintes et fonction ‘objectif’)

2. Résolution graphique des problèmes de programmation linéaire à deux variables

3. Résolution des problèmes linéaires par la méthode du simplexe4. Dualité: définitions et notions de base

Mode d’évaluation : InterrogationDevoir surveilléTravaux pratiquesExamen final

33

INTRODUCTION À LA THÉORIE

DES GRAPHES

1. Le concept de graphesDans la vie quotidienne, pour expliquer un problème on

utilise un graphe, par exemple: tracer un itinéraire,arbre généalogique, organigramme d’une institution, …

Ce qui veut dire que nous sommes tous familiarisésavec la notion de graphe.

On peut dire qu’un graphe constitue donc uneméthode de pensée qui permet de modéliser unproblème.

44


DES GRAPHES

1. Le concept de graphes (suite)Exemple: Leonhard Euler à posé un problème de

promenade dans sa ville Königsberg (aujourd'hui nomméKaliningrad) en Russie.

Leonhard Euler

(1707-1783)

55


DES GRAPHES

1. Le concept de graphes (suite)Il cherche à savoir s’il peut se promener dans les rues

de Königsberg en passant une et une seule fois parchaque pont, et de revenir à son point de départ.

Il a démontrer qu’il ne peut pas faire une tellepromenade en caractérisant des graphes (que l’onappelle actuellement graphes eulériens).

66


DES GRAPHES

1. Le concept de graphes (suite)Nous allons voir quelques définitions avant de

continuer dans ce cours.

1.1.Définitions d’un grapheUn graphe G est défini par deux ensembles: S={s0, s1,

…, sn} ensemble de sommets et A={a1, a2, …, am} ensembled’arêtes.

77


DES GRAPHES

1.1.Définitions d’un graphe (suite)Ou: un graphe est un ensemble fini de points appelés

sommets, nœuds ou cellules. Ces derniers sontconnectés par des liens appelés arêtes (ou arcs).

88


DES GRAPHES

1.2. Composantes d'un grapheL’ordre d’un graphe est le nombre de sommets du

graphe.

Une boucle est une arête reliant un sommet à lui-même.

Un sommet isolé s’il n’y a aucune arête qui le relie àd’autres sommets.

Deux sommets adjacents s’ils sont reliés par unearête.

Un arc est une arête orientée.

99


DES GRAPHES

1.2. Composantes d'un graphe (suite)Le degré d'un sommet est le nombre d'arêtes ayant

une extrémité en ce sommet. Par exemple, les nœuds dugraphe suivant sont tous de degré 3.

1010


DES GRAPHES

1.2. Composantes d'un graphe (suite)

Un sommet isolé est un sommet de degré zéro (sansarête connectée).

Un sommet pendant est un sommet de degré 1 (reliéà une seule arête).

isolé

pendant

1111


DES GRAPHES

1.3. Quelques types de graphes1.3.1. Graphe simple

C’est un graphe sans boucles et entre deux sommets ily a au plus une arête.

1.3.2. Multigraphe

Un multigraphe est un graphe pour lequel il peutexister plusieurs arêtes entre deux sommets ou desboucles . 1

32

4

1

32

4

Graphe simple Multigraphe 1212


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.3. Connexité

Un graphe connexe non orienté est un graphe où àpartir d’un sommet on peu rejoindre tous les autressommets.

Pour un graphe orienté, on parle de connexité si enignore l'orientation des arêtes, le graphe devient connexe.

En distingue 2 types de connexités: fortement connexeet faiblement connexe (sections: 1.3.5 et 1.3.6)

Un graphe non connexe se décompose en plusieurscomposantes connexes.

1313


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.3. Connexité (suite)

Exp. G = (S, A) est un graphe non connexe avecS={1,2,3,4,5,6} et A={(1,3), (1,4), (3,4), (2,5), (2,6)}.

Il contient 2 composantes connexes:

S1={1,3,4}; A1={(1,3), (1,4), (3,4)}.

S2={2,5,6}; A2={(2,5), (2,6)}.

Graphe non connexe

1

3

2

45

6

1414


DES GRAPHES

1.3. Quelques types de graphes (suite)

Un isthme est une arête dont la suppression augmentele nombre de composantes connexes.

1

3

2

45

6

isthmes

1

3

2

45

6

1515


DES GRAPHES

1.3. Quelques types de graphes (suite)Un point d'articulation est un sommet tel que sasuppression augmente le nombre de composantesconnexes du graphe initial.

1

3

2

45

6

Point d’articulation

1616


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.4. Graphe complet

Un graphe complet avec n sommets (noté Kn) est ungraphe possédant n sommets pour lequel chaque sommetest relié à tous les autres.

Exp. G = (S, A) est un graphe complet (noté aussi K3)avec S={1,2,3} et A={(1,2), (1,3), (2,3)}.

Graphe complet

1

3

2

1717


DES GRAPHES

1.3. Quelques types de graphes (suite)Avant de voir les autres types nous devons définir

quelques concepts.

Une chaîne est une séquence ordonnée d'arêtes telleque chaque arête ait une extrémité en commun avecl'arête suivante.

Une chaîne élémentaire ne passe pasdeux fois par le même sommet.

Une chaîne simple n'utilise pas deuxfois la même arête.

1818


DES GRAPHES

1.3. Quelques types de graphes (suite)Un chemin est une chaîne telle que l'extrémité

terminale d'un arc coïncide avec l'extrémité initiale del'arc suivant.

Le premier sommet du chemin est appelé nœud initialdu chemin, et le dernier est appelé nœud terminal.

Chemin (1,2,5)

1 2

3 4

5

Nœud initial

Nœud terminal

1919


DES GRAPHES

1.3. Quelques types de graphes (suite)Un cycle est une chaîne simple dont les sommets des

extrémités coïncident.

Un circuit est un chemin dont le nœud initial est lenœud terminal. On peut dire qu’une boucle est un circuitde longueur 1.

Circuit (1,2,5,4,3,1)

1 2

3 4

5

Nœud initial

et terminal

Cycle (1,2,5,4,3,1)

1 2

3 4

5

Nœud initial

et terminal

2020


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.5. Graphe fortement connexe

Un graphe orienté est fortement connexe s'il existeun chemin entre chaque deux sommets dans les deuxsens.

Exp. G = (S, A) est un graphe fortement connexe avecS={1,2,3,4,5} et A={(1,2), (2,4), (4,3), (3,1), (2,5), (5,4)}.

Graphe fortement connexe

1 2

3 4

5

2121


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.6. Graphe faiblement connexe

Un graphe orienté est faiblement connexe s'il y aune chaîne entre n'importe quelle paire de sommets sansconsidérer l'orientation des arcs.

Exp. G = (S, A) est un graphe faiblement connexe avecS={1,2,3,4,5} et A={(1,2), (2,4), (4,3), (3,1), (2,5), (5,4)}.

Graphe faiblement connexe

1 2

3 4

5

2222


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.7. Graphe biparti

Un graphe est biparti si l’ensemble des sommetspeut être réparti en deux sous-ensembles disjoints U etV tels que chaque arête relie un sommet de U à unsommet de V.

Graphe biparti

2 13

5 64

U

V

2323


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.7. Graphe biparti (suite)

Un graphe biparti est complet si tous les ‘n’ sommetsde U sont connectés à tous les ‘m’ sommets de V, et onnote Kn,m.

Graphe biparti complet K3,3

2 13

5 64

U

V

2424


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.8. Graphe d’intervalles

Un graphe d’intervalles est un graphe dont lessommets représentent des intervalles réels I1, …, In etdeux sommets i et j seront reliés par une arête s’il y aune intersection entre leurs intervalles: Ii ∩ Ij ≠ ∅.

Graphe d’intervalles

2

13

5

6

4

7

I1 I5 I6

I3 I7

I2 I4

2525


DES GRAPHES

1.3. Quelques types de graphes (suite)Exp. Soit quatre intervalles qui forment le graphe

suivant sous forme d’un carré sans diagonale.

On remarque que l’intervalle I1 ne peut pas êtredessiné sans coupure.

Ça représente le théorème combinatoire dumathématicien hongrois György Hajós proposé en 1961.

2 1

3 4I1 I1

I2I4

I3

2626


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.9. Graphe eulérien

Une chaîne eulérienne est une chaîne qui passe uneseule fois par toutes les arêtes du graphe. Si la chaîneest fermée on l’appel cycle eulérien.

Chaîne eulérienne (1,2,3,1,4,5,2,4,3)

Pas de cycle eulérien

1 2

3 4

5

2727


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.9. Graphe eulérien (suite)

Un graphe eulérien est un graphe qui contient aumoins un cycle eulérien.

Cycle eulérien (1,2,5,4,3,6,2,3,5,6,1)

Graphe eulérien

2 3

6 5

41

2828


DES GRAPHES


Pour déterminer un cycle eulérien, on utilisel’algorithme suivant:

Algorithme de cycle eulérien d’un graphe G:

1. Construire un cycle C0 le pluslong possible: (1,2,3,4,1)

2. Supprimer les arêtes du cycle C0;

1 2

4 3

6

5

2929


DES GRAPHES

1.3. Quelques types de graphes (suite)Algorithme de cycle eurélien (suite)

3. En commençant d’un sommet du cycle C0 qui a undegré non nul, on construit un autre cycle C1;(2,5,6,2)

4. Supprimer les arêtes du cycle C1;

5. Et on boucle sur les étapes 3 & 4 jusqu’à ce qu’il nereste plus d’arrêtes

6. On insère dans C0 tous les cycles construits à la placedes sommets de début de ces cycles.

Suite de l’exemple: (1,2,5,6,2,3,4,1)3030


DES GRAPHES


Un graphe semi-eulérien est un graphe qui contientdes chaînes eulériennes et pas de cycles eulériens.

Chaine eulérienne (2,1,4,5,2,3,4)

Pas de cycle eulérien

Graphe semi-eulérien

2

3 5

4

1

3131


DES GRAPHES


Théorème 1: Un multigraphe connexe contient uncycle eulérien si et seulement si chacun de ses sommetsest de degré pair.

Exp.

En appliquant l’algorithme de cycle eurélien en trouve:

a,b,c,d,g,k,h,g,f,d,b,e,f,i,h,j,i,e,a

b

c

e

f

d

a

h

g

kj

i

3232


DES GRAPHES


Théorème 2: Un multigraphe connexe contient unechaîne eulérienne et non un cycle eulérien si etseulement s'il a exactement deux sommets de degréimpair.

Exp. Chemin eurélien: 4,2,3,4,5,2,1,3,5

Pas de cycle eurélien. 2

3

541

3333


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.10. Graphe hamiltonien

Une chaîne hamiltonienne est une chaîne qui passeune seule fois par tous les sommets du graphe. Si lachaîne est fermée on l’appel cycle hamiltonien.

Chaîne hamiltonienne (1,2,5,4,3)

Pas de cycle hamiltonien

1 2

3 4

5

William Rowan Hamilton

(1805 – 1865) 3434


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.10. Graphe hamiltonien (suite)

Un Graphe hamiltonien est un graphe qui contient uncycle hamiltonien.

Cycle hamiltonien (1,2,5,4,3,1)

Graphe hamiltonien

1 2

3 4

5


Un graphe semi-hamiltonien est un graphe quicontient des chaînes hamiltoniennes et pas de cycleshamiltoniens.

Chaine hamiltonienne (1,2,3,4,5)

Pas de cycle hamiltonien

Graphe semi-hamiltonien

2 4

53

1

3535


DES GRAPHES

3636


DES GRAPHES


Théorème de Dirac: Soit G(S,A) un graphe simple etnon orienté avec n ≥ 3 sommets. Si pour chaque sommetx de G, degré(x) ≥ (au moins égale) n/2, alors il esthamiltonien.

∀� ∈ �, deg � ≥ �2 ⇒ � �� ℎ��a b a b

0 0 1Cas non intéressants

0 1 1

1 0 0 C’est le cas interdit selon Dirac

1 1 1 C’est le cas visé par Dirac

3737


DES GRAPHES


Exp.

∀� ∈ �, deg � ≥ 2.5 ⇒ � �� ℎ��Pas de cycle hamiltonien

L’implication est vrai (00)

1

2

3 4

5

∀� ∈ �, deg � ≥ 2.5 ⇒ � �� ℎ��Cycle hamiltonien (1,2,5,4,3,1)

Graphe hamiltonien


12

34

5

3838


DES GRAPHES


Exp. (suite)

∀� ∈ �, deg � ≥ 2.5 ⇒ � �� ℎ��Cycle hamiltonien (1,2,5,4,3,1)

Graphe hamiltonien


12

34

5

3939


DES GRAPHES


Théorème d’Ore: Soit G(S,A) un graphe simple et nonorienté avec n ≥ 3 sommets. Si pour toute paire desommets (a, b) non adjacents (a, b) ∉∉∉∉ A, on adeg(a)+deg(b) ≥≥≥≥ n alors G est hamiltonien.

∀ �, � ∈ �� , � ∉ �,deg � + deg (�) ≥ � ⇒ � �� ℎ��4040


DES GRAPHES


Exp.

∀ �, � ∈ ��,�, � ∉ �, deg � + deg � ≥ 5 ! ⇒ � �� ℎ��Cycle hamiltonien (1,2,5,4,3,1)

Graphe hamiltonien


12

34

5

∃ �, � ∈ ��,�, � ∉ �,deg � + deg � < 6 ! ⇒ � �� ℎ��Cycle hamiltonien (1,2,3,4,5,6,1)


1 2

5 4

36

4141


DES GRAPHES


Exp. (suite)

∃ �, � ∈ ��,�, � ∉ �,deg � + deg � < 6 ! ⇒ � �� ℎ��Chaîne hamiltonienne (1,2,3,4,5,6)


1 2

5 4

36

4242


DES GRAPHES


Quelques propriétés de graphe hamiltonien

• Un graphe avec un de ses sommets est de degré 1 nepeut pas être hamiltonien;

• Les arêtes liées à un sommet de degré 2 dans ungraphe hamiltonien doivent appartenir au cyclehamiltonien;

• Les graphes complets Kn sont hamiltoniens.

4343


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.11. Graphe planaire

Un graphe est planaire s'il peut être dessiné sur unplan sans que les arêtes ne se croisent.

Exp: K1,K2,K3,K4 sont planaires, mais K5 n’est pasplanaire.

4444


DES GRAPHES

1.3. Quelques types de graphes (suite)1.3.11. Graphe planaire (suite)

Dans un graphe planaire, une face F est une régiondélimitée par un ensemble d’arrêtes et que aucunearrête ne traverse cette région.

Le degré de F deg(F) est le nombre d’arrêtes sur lesfrontières de F.

1 2

3 4

A

B

C

D

Deg(A) = 3

Deg(B) = 3

Deg(C) = 3

Deg(D) = 3

4545


DES GRAPHES


Théorème 1: Soit G un graphe planaire et a lenombre d'arêtes de G, alors:

% deg & = 2 · �)∈)*+,-1 2

3 4

A

B

C

D

Deg(A) + Deg(B) + Deg(C) + Deg(D) = 12 = 2*a 4646


DES GRAPHES


Théorème 2: Le graphe biparti complet K3,3 n'estpas planaire.

Graphe biparti complet K3,3

Non planaire

2 13

5 64

4747


DES GRAPHES


Théorème 3: Le graphe complet K5 n'est pasplanaire.

Graphe complet K5

Non planaire

2

13

54

4848


DES GRAPHES


Théorème d’Euler: Soit G un graphe planaire connexeet soit s le nombre de sommets, a le nombre d'arêtes etf le nombre de faces. � − � + / = 2

Exp. s = 6, a = 10, f = 6

6 – 10 + 6 = 2

4949


DES GRAPHES


Critère de graphes planaires: Soit G un graphesimple planaire connexe avec s ≥ 3.

Et soit ‘s’ nombre de sommets, ‘a’ nombre d'arêtes de G:� ≤ 3 · � − 6Pourquoi?

Nous avons ∑ deg & ≥ 3 · /)∈)*+,- puisque dans ungraphe simple, chaque face est limitée par au-moins 3arrêtes. Et nous avons ∑ deg & = 2 · �)∈)*+,-

Donc 2 · � ≥ 3 · / ⇒ − 3 · / ≥ −2 · �5050


DES GRAPHES


Donc 2 · � ≥ 3 · / ⇒ − 3 · / ≥ −2 · �et nous avons � − � + / = 2⇒ / = 2 + � − �⇒ − 3 · (2 + � − �) ≥ −2 · �⇒ − 6 − 3 · � + 3 · � ≥ −2 · �⇒ 3 · � − 6 ≥ �

5151


DES GRAPHES

1.4. Représentations non graphiques d’un grapheOn peut représenter un graphe par une matrice

d’adjacences ou des listes d’adjacences.

1.4.1. Matrice d’adjacences

On peut représenter un graphe par une matriceM � × � de n lignes et n colonnes.

Les lignes et les colonnes représentent les sommetsdu graphe.

L’élément M(i,j) = k représente le nombre d’arrêtesentre les sommets i et j (sommets adjacents).

5252


DES GRAPHES

Caractéristiques de la matrice d’adjacences

• Matrice carrée;

• Un 1 sur la diagonale indique une boucle;

• Elle est symétrique dans le cas d’un graphe non-orienté;

Exp.

2

13

5

4

5 =0 1 1 0 11 0 1 0 11 1 0 0 10 0 0 0 11 1 1 1 0

5353


DES GRAPHES

1.4.2. Listes d’adjacences

On peut représenter un graphe par des listes oùchaque sommet possède sa liste de sommets auxquels ilest adjacent.

Exp.

2

13

5

4

1: 2,3,5

2: 1,3,5

3: 1,2,5

4: 5

5: 1,2,3,4

5454


DES GRAPHES

2. Algorithmes de base en théorie des graphes

2.1. Le plus court chemin (Algorithme de Djikstra)

L'objectif du problème du plus court chemin est decalculer un chemin entre deux sommets d'un graphe quiminimise une certaine valeur.

Nous allons considérer un graphe orienté avec desarcs pondérés par des poids.

Il existe plusieurs algorithmes, nous allons voirl’algorithme de Djikstra.

5555


DES GRAPHES

2.1. Le plus court chemin (Algorithme de Djikstra)

Soit un graphe orienté et pondéré. On cherche àtrouver le chemin qui mène du sommet ‘s’ au sommet ‘t’avec un poids minimum.

Chemin: s635tPoids: 14+18+2+16=50

5656


DES GRAPHES

2.1. Le plus court chemin (Algorithme de Djikstra)(suite)

Les poids des arcs sont des entiers positifs quipeuvent être: des distances, des tarifs, …

Le sommet ‘s’ est appelé la source.

La distance de ‘s’ à ‘t’ est la somme des poids des arcsdu chemin minimal entre ‘s’ et ‘t’.

Le but est de trouver la distance entre ‘s’ et tous lessommets du graphe.

5757


DES GRAPHES

2.1. Le plus court chemin (Algorithme de Djikstra)(suite)

Les chemins minimaux forment un arbre.

On représente cette arbre par deux tables:

dist[i]: contient la distance entre ‘s’ et ‘i’;

pred[i]: contient le sommet qui précède ‘i’.

5858


DES GRAPHES

Algorithme de Dijkstra pour former l’arbre deschemins minimaux

Soit l’ensemble S contenant les sommets dont ladistance à partir de ‘s’ est connue.

• Initialiser S par {s}

• Initialiser dist[s] à 0, et dist[ti] à ∞ pour tous lesautres sommets

• Répéter jusqu’à ce que S contient tous les sommetsconnectés à ‘s’:– Trouver l’arc ‘a’ entre ‘t1’ et ‘t2’ tel que ‘t1’∈S et ‘t2’∉S et tel

que (dist[t1] + poids(a)) est minimale

– Ajouter ‘t2’ à S; dist[t2]=dist[t1] + poids(a); pred[t2]=t1;

5959


DES GRAPHES

Pour trouver l’arc ‘a’ entre ‘t1’ et ‘t2’ tel que ‘t1’∈S et ‘t2’∉S et telque (dist[t1] + poids(a)) est minimale

6060


DES GRAPHES

2.1. Le plus court chemin (Algorithme de Dijkstra)

Exp.

Soit le graphe pondéré suivant. Appliquer l’algorithmede Dijkstra pour former l’arbre des chemins minimaux.

s2

3

4

5

6

7 8

924

19

15

14 18

26

1116

6

44

20

521

6161


DES GRAPHES

2.1. Le plus court chemin (Algorithme de Dijkstra)

Exp. (suite)

L’arbre des chemins minimaux:

s 2 3 4 5 6 7 8

Dist 0 9 32 45 34 14 15 50

Pred s 6 5 3 s s 5

s

2

6

7

3 5

4

8

6262


DES GRAPHES

2.2. Problème de flot maximum

On défini un graphe orienté et pondéré G(S, A) pourreprésenter un réseaux informatiques, un réseauxroutiers, …

Exp. 1:

Graphe ou réseau à capacité.

s

1

3

2 t

4

3

1

2

4

21

4

2

6363


DES GRAPHES

2.2. Problème de flot maximum (suite)

Chaque arc représente un chemin unidirectionnel,pondéré par le nombre maximal de véhicules quipeuvent passer par heure sur ce chemin. Le problèmeest de trouver le nombre maximal de véhicules quipeuvent voyager du point de départ ‘s’ au point d’arrivée(un puits) ‘t’ en une heure.

6464


DES GRAPHES


Ce graphe G(S, A) peut aussi représenter un réseauxélectrique. Et on cherche à trouver le courant maximalqui peut passer d’un point ‘s’ vers un puits ‘t’.

6565


DES GRAPHES


Dans ce graphe G(S, A), à chaque arc ‘a’ on associe unevaleur positive appelée ‘capacité’ C(a).

Le degré de sortie/d’entrée d’un sommet ‘x’ notéoutdeg(x)/indeg(x) représente la somme des capacitésdes arcs qui sortent du/entrent au sommet ‘x’.

Exp. Dans le graphe de l’exemple précédent:

outdeg(s) = 8 et indeg(1) = 10.

6666


DES GRAPHES


Dans un réseau (Graphe orienté et pondéré G(S, A)),un flot est une fonction ϕϕϕϕ qui associe à chaque arc ‘a’une valeur réelle non négative ϕ(a) appelée flot dans ‘a’,tel que:

• Pour chaque arc ‘a’ : ϕ(a) ≤ C(a)

• Pour chaque sommet ‘x’ ∉ {s, t}, on définit ‘x_out’l’ensemble des arcs sortant du sommet ‘x’, et ‘x_in’l’ensemble des arcs entrant à ‘x’ :

% 8(�)9∈9_;<= = % 8(�)9∈9_>?

6767


DES GRAPHES


Quelques caractéristiques:

• Un arc ‘a’ est dit saturé si: ϕ(a) = C(a).

• Soit ‘s_out’ l’ensemble des arcs sortant de ‘s’, et ‘t_in’l’ensemble des arcs entrant à ‘t’ :

% 8(�)9∈-_;<= = % 8(�)9∈=_>?

6868


DES GRAPHES


Quelques caractéristiques: (suite)

• La somme précédente est appelée ‘Valeur du flot’

% 8(�)9∈-_;<= = % 8 �9∈=_>? = @��AB CA /��Exp. 2: On définit le flotsuivant sur le graphe del’exemple précédent:

s

1

3

2 t

3/4

2/3

1/1

2/2

4/4

0/21/1

0/4

2/2

6969


DES GRAPHES


Quelques caractéristiques: (suite)

• On voit bien que le flot de l’exemple 2 est un flotmaximal pour le graphe de l’exemple 1 (sa valeur duflot = 6).

• On peut trouver plusieurs flots maximaux dans unréseau mais qui ont la même valeur.

Il existe deux méthodes pour trouver le flot maximal:(Coupe minimale – Chaîne augmentante)

7070


DES GRAPHES

2.2.1. Méthode de la coupe minimale

L’étude du flot maximal est attaché au concept decoupe (cut).

Une coupe est un ensemble d’arcs ‘AC’ tel que tous leschemins de ‘s’ à ‘t’ contiennent un arc de ‘AC’.

Autrement dit, une coupe est un ensemble dedéconnexion de ‘s’ et ‘t’.

La capacité d’une coupe est la somme des capacitésde ses arcs.

Nous sommes intéressés par la coupe qui a la capacitéminimale, et on l’appel ‘coupe minimale’

7171


DES GRAPHES

Exp. 3: Une coupe minimale est: {s-3, 2-3, 1-3, 1-t}

La capacité de cette coupe = 6.

Remarque: La coupe ne contient pas l’arc 3-1.

s

1

3

2 t

4

3

1

2

4

21

4

2

7272


DES GRAPHES

Remarques:

La valeur d’un flot maximal ne peut pas dépasser lacapacité d’une coupe minimale.

Théorème (max-flow min-cat):

Dans tout réseau, la valeur du flot maximum est égaleà la capacité de toute coupe minimale.

7373


DES GRAPHES

2.2.2. Méthode de la chaîne augmentante

Pour trouver le flot maximum, nous devons définir lanotion de chaîne augmentante.

Une chaîne augmentante µ dans un graphe orienté àcapacités est une chaîne reliant ‘s’ à ‘t’ tel que:

• Pour tout arc ‘a’ de µ orienté de ‘s’ vers ‘t’, ϕ(a) < C(a),on note a ∈ µ+;

• Pour tout arc ‘a’ de µ orienté de ‘t’ vers ‘s’, ϕ(a) > 0, onnote a ∈ µ-;

7474


DES GRAPHES

Exp:

Le flot = 19

La chaîne augmentante (s-3-2-t) permet d’augmenterla valeur du flot par la valeur de:D = �� min*∈HI J � − 8 � ; min*∈HL 8 � = 4

1 2

3 4

ts

15/16

4/13

4/4

7/10

4/9

11/14

7/7

15/20

4/4

12/12

7575


DES GRAPHES

Exp: (suite)

Le flot = 23

Il n’y a plus de chaînes augmentante à cause des arcssaturés.

1 2

3 4

ts

15/16

8/13

4/4

7/10

0/9

11/14

7/7

19/20

4/4

12/12

7676


DES GRAPHES

L’algorithme pour trouver une chaîne augmentante:

• Marquer la source ‘s’ avec ‘+’;

• Pour tout arc (u,v) ∈ A, faire:– Si ‘u’ est marqué, ‘v’ n’est par marqué et ϕ(u,v) < C(u,v) alors

marquer ‘v’ avec ‘+u’;

– Si ‘v’ est marqué, ‘u’ n’est par marqué et ϕ(u,v) > 0 alorsmarquer ‘u’ avec ‘-v’;

• Répéter la boucle jusqu’à ce qu’on ne peut plusmarquer des nœuds.

7777


DES GRAPHES

Si ‘t’ est marqué alors il y a une chaîne augmentante.

Pour trouver la chaîne, il faut suivre le marquage enremontant depuis ‘t’.

Exp. Soit le graphe orienté à capacités suivant.

Appliquer l’algorithmepour trouver une chaîne augmentante.

s-3-5-2-4-ts

1

3

2 t

2/2 1/2

1/4

21/3

2/5

4

6

5

0/1

0/1

2/22/2

1/2

0/1

1/1+

+s

+3-5

+2

+4

7878


DES GRAPHES

Pour trouver le flot maximal, on suit les étapessuivantes (Algorithme de Ford-Fulkerson):

Soit G(S,A) un graphe orienté à capacités (pondéré):

1. On commence par un flot à valeur zéro sur tous lesarcs;

2. Tant qu’il existe une chaîne augmentante µ dans Gfaire:• D ≔ �� min*∈HI J � − 8 � ; min*∈HL 8 �• ∀� ∈ OP, 8 � ≔ 8 � + D• ∀� ∈ OQ, 8 � ≔ 8 � − D

3. Calculer la valeur du flot du réseau.

7979


DES GRAPHES

Exp.

Trouver le flot maximal.

s

1

3

2 t

0/2 0/2

0/4

20/3

0/5

4

6

5

0/1

0/1

0/20/2

0/2

0/1

0/1

s

1

3

2 t

2/2 2/2

1/4

21/3

2/5

4

6

5

0/1

0/1

2/22/2

1/2

1/1

1/1

8080


DES GRAPHES

3. Les notions de base des arbres

Un arbre est un graphe connexe et sans cycle.

Une forêt est un graphe non connexe et sans cycle.

Une feuille est un sommet pendant (degré = 1)

8181


DES GRAPHES

Exp.

2

1

5

3 4 2

1

5

3 4

5

ArbreForet

Feuilles

Feuilles

8282


DES GRAPHES

3.1. Caractéristiques

Les affirmations suivantes sont équivalentes pour ungraphe G(S,A) à ‘n’ sommets:

• G est un arbre;

• G est sans cycle et connexe;

• G est sans cycle et comporte (n− 1) arêtes;

• G est connexe et comporte (n− 1) arêtes;

• Chaque paire de sommets distincts (u, v) est reliéepar une seule chaîne simple (et le graphe est sansboucle).

8383


DES GRAPHES

3.2. Codage de Prüfer

Pour représenter un arbre d’une manière compacte, lemathématicien allemand Ernst Paul Heinz Prüfer proposeun algorithme de codage et de décodage.

Soit G(S,A) un arbre, avec S = {1, 2 , 3 , … , n}

Algorithme de codage

Entrée: Un arbre G(S,A)

Sortie: Une suite C de n-2 sommets de S.

8484


DES GRAPHES

3.2. Codage de Prüfer (suite)

Algorithme de codage (suite)Répéter tant qu’il ne reste plus que 2 sommets dansl’arbre G

• Trouver la feuille ‘f’ de l’arbre ayant le numérominimum;

• Ajouter à la suite C le seul sommet ‘a’ adjacent à ‘f’dans l’arbre G;

• Supprimer de l’arbre G le sommet ‘f’.

8585


DES GRAPHES

Algorithme de codage (suite)

Exp:

1

2

6

3 4

5

2

6

3 4

5 6

3 4

5

6

3

5 6

3

C={} C={2} C={2, 3}

C={2, 3, 3} C={2, 3, 3, 3}

Il reste 2 sommets :

fin du codage

8686


DES GRAPHES

3.2. Codage de Prüfer (suite)

Algorithme de décodage

Entrée: Une suite C de n-2 sommets de S.

Sortie: Un arbre G(S,A)

Définir l’ensemble I = {1, 2 , … , n}

• Répéter tant qu’il reste des éléments dans C et plusde 2 éléments dans I:

– Trouver le plus petit élément ‘i’ de I tel que: i ∉ C;

– Ajouter une arête à G qui relie le sommet ‘i’ aupremier sommet ‘a’ de la suite C;

– Supprimer ‘i’ de I et ‘a’ de C.

8787


DES GRAPHES

Algorithme de décodage (suite)

• Les deux éléments qui restent dans I à la fin del’algorithme constituent les extrémités de ladernière arête à ajouter à G.

Exp.

1

2

6

3 4

5

C = {2, 3, 3, 3}

I = {1, 2, 3, 4, 5, 6}

1

2

6

3 4

5

C = {3, 3, 3}

I = {2, 3, 4, 5, 6} 8888


DES GRAPHES


Exp. (suite)

1

2

6

3 4

5

C = {3, 3}

I = {3, 4, 5, 6}

1

2

6

3 4

5

C = {3}

I = {3, 5, 6}

1

2

6

3 4

5

C = {}

I = {3, 6}

8989


DES GRAPHES


Exp. (suite)

1

2

6

3 4

5

C = {}

I = {}

9090


DES GRAPHES

3.3. Arbre couvrant

Un arbre couvrant ou arbre maximal d’un grapheG(S,A), est un graphe partiel de G contenant le maximumd’arêtes de ‘A’ et qui forme un arbre.

Exp:

1

2

6

3 4

5

1

2

6

3 4

5

Graphe G(S,A) Arbre couvrant de G

9191


DES GRAPHES

3.3. Arbre couvrant (suite)

Si le graphe G(S,A) est pondéré, on cherche à trouverun arbre maximal Ar(S,A1) de poids total minimum. Cetarbre est appelé arbre couvrant de poids minimum.

Monsieur Kruskal proposa un algorithme en 1956 pourtrouver un arbre couvrant de poids minimum à partird’un graphe.

9292


DES GRAPHES

3.3. Arbre couvrant (suite)

Algorithme de Kruskal:

Entrée: Graphe pondéré G(S,A) avec C(a) est la capacitéde l’arête ‘a’ et |S|=n et |A|=m.

Sortie: Arbre (ou forêt) couvrant de poids minimumAr(S,A1)

• Trier et numéroter les arêtes de G dans l’ordrecroissant de leur poids: C(a1) ≤ C(a2) ≤ … C(am);

• Poser A1 = ∅, k = 0;

• Tant que k < m et |A1| < n-1 faire

– Si ak+1 ne forme pas de cycle avec A1, alors A1=A1∪{ak+1};

– K = k + 1;

9393


DES GRAPHES

Algorithme de Kruskal: (suite)

Exp.

1

2

4

3

6

5

1

3

1

3

5

5

24

21

2

4

3

6

5

1

1

1

2

4

3

6

5

1

1

22

1

2

4

3

6

5

1

1

24

2

9494

INTRODUCTION À LA

PROGRAMMATION LINÉAIRE

1. Le concept de programmation linéaire1.1. Introduction

Un problème de programmation linéaire est unproblème d’optimisation.

c-à-d minimiser ou maximiser d'une fonction‘objectif’ linéaire en respectant des conditionslinéaires.

Pour résoudre de tels problèmes, on utilise deuxtypes de méthodes: graphique – simplexe.

9595

INTRODUCTION À LA


1. Le concept de programmation linéaire (suite)Pour modéliser un problème linéaire, on doit définir:

• Les variables à optimiser;

• Les contraintes sur ces variables;

• L’objectif visé.

9696

INTRODUCTION À LA


1.2. Forme standard

Un problème de programmation linéaire peut êtreécrit sous la forme standard (forme canonique):

Maximiser cTx;

Objectif Ax = b;

Tel que: x ≥ 0, c ∈ ℜn, b ∈ ℜm, A ∈ ℜmxn

tel que x est le vecteur de variables à optimiser.

Les données sont les vecteurs c, b et la matrice A.

9797

INTRODUCTION À LA


1.2. Forme standard (suite)Si on rencontre un problème de minimisation

(minimiser cTx), on peut l’écrire sous la forme standard(maximiser -cTx).

Si la fonction objectif été Ax ≥ b on peut l’écrireAx - y = b tel que y ≥ 0. etc.

Le vecteur y est appelée variables d’écart.

9898

INTRODUCTION À LA


1.2. Forme standard (suite)Exp. Une personne veut nourrir son petit chien avec

deux produits: des croquettes et du lait. Le chien doitavoir au moins 60 unités de fer, et 70 unités deprotéines. Sachant qu’une unité de croquettes contient30 unités de fer et 5 unités de protéines et coûte 200DA, et une unité de lait contient 17 unités de fer et 9unités de protéines et coûte 100 DA.

Modéliser ce problème pour chercher le repas lemoins cher et suffisant pour ce chien.

9999

INTRODUCTION À LA


1.2. Forme standard (suite)Exp. (suite)

Soit x1 et x2 les variables qui représentent,respectivement, le nombre d’unités de croquettes, et delait à consommer.

On peut écrire les quantités suffisantes en fer etprotéines comme suit:

Besoin en fer: 30 x1 + 17 x2 ≥ 60;

Besoin en protéines: 5 x1 + 9 x2 ≥ 70;

avec x1, x2 ≥ 0.

100100

INTRODUCTION À LA



Le coût du repas est: 200 x1 + 100 x2 ;

On peut écrire le problème sous la forme standard:

Maximiser -(200 x1 + 100 x2);

Objectif: 30 x1 + 17 x2 ≥ 60;

5 x1 + 9 x2 ≥ 70;

Tel que x1, x2 ≥ 0.

101101

INTRODUCTION À LA



On peut écrire la fonction objectif:

Maximiser -(200 x1 + 100 x2);

Objectif: 30 x1 + 17 x2 - y1 = 60;

5 x1 + 9 x2 - y2 = 70;

Tel que x1, x2, y1, y2 ≥ 0.

avec y1 représente l’excédant des unités en fer.

et y2 représente l’excédant des unités en protéines.

102102

INTRODUCTION À LA


1.3. Ensembles convexes (≠≠≠≠ concave)Un ensemble est convexe s'il contient tout segment

passant par deux de ses points.

Autrement dit, un sous-ensemble C d'un espacevectoriel E est dit convexe si et seulement si:

∀v1, v2 ∈ C, ∀ λ ∈ [0,1], λ.v1+(1- λ).v2 ∈ C.

v1

v2

v1

v2

Ensemble convexeEnsemble non convexe

103103

INTRODUCTION À LA


1.3. Ensembles convexes (≠≠≠≠ concave)Tous les points qui sont entre DR et D� peuvent être

écrits par la formule: S · DR + 1 − S · D�

v1

v2v

λ.v1

(1-λ).v2

v=λ.v1+(1-λ).v2

104104

INTRODUCTION À LA


1.3. Ensembles convexes (suite)Pour connaitre un point extrême ‘v’ (un coin) dans un

ensemble convexe C, il faut vérifier qu’il n’existent pasdeux points DR et D� de C tel que D = S · DR + 1 − S · D�

c-à-d le point ‘v’ ∉ [v1,v2] de C.

Points extrêmes

Ensemble convexe

105105

INTRODUCTION À LA


1.3. Ensembles convexes (suite)Dans le cas de la programmation linéaire, un ensemble

convexe est un ensemble de points situés à l’intérieurd’un polygone convexe qui est limité par les contraintesde la fonction objectif.

Exp.

Soit l’ensemble suivant:

C = {(x, y) ∈ ℜ2: |x| ≤ 5, |y| ≤ 10}

Est-ce que C est convexe?

106106

INTRODUCTION À LA


Exp. (suite)

Soit A(x1, y1) et B(x2,y2) ∈ C.

Soit V(X, Y) appartient au segment [A,B], donc

X = λ.|x1| + (1 - λ).|x2| et Y = λ.|y1| + (1 - λ).|y2|

tel que λ ∈ [0,1]

Nous avons |x1| ≤ 5, |y1| ≤ 10 et |x2| ≤ 5, |y2| ≤ 10

λ.|x1| ≤ λ.5 et (1 - λ).|x2| ≤ (1 - λ).5

λ.|x1| + (1 - λ).|x2| ≤ λ.5 + (1 - λ).5

λ.|x1| + (1 - λ).|x2| ≤ λ.5 + 5 - λ.5

λ.|x1| + (1 - λ).|x2| ≤ 5 X ≤ 5

107107

INTRODUCTION À LA


Exp. (suite)

de la même manière on trouve que:

λ.|y1| + (1 - λ).|y2| ≤ 10 Y ≤ 10

donc: V(X,Y) ∈ C ce qui implique que C est convexe.

10

5-5

-10 108108

INTRODUCTION À LA


2. Résolution graphique des problèmes de programmation linéaire à deux variablesUn problème de programmation linéaire est un

problème d’optimisation d’une fonction appelée objectif,tout en respectant certaines contraintes.

Pour résoudre un tel problème, on peut utiliser laméthode graphique. Pour cela, on doit suivre les étapes:

• Tracer le polygone convexe limité par les contraintes;

• Chercher les points qui optimisent (maximisent ouminimisent) la fonction objectif.

Ces points se situent aux coins du polygone.

109109

INTRODUCTION À LA


2. Résolution graphique des problèmes de PL à deux variables (suite)Exp. Soit le problème de programmation linéaire

suivant:

Maximiser 21 T . U1U2 ;

Objectif1 21 11 0 . U1U2 ≤ 643 ;

Tel que U1U2 ≥ 00110110

INTRODUCTION À LA


2. Résolution graphique des problèmes de PL à deux variables (suite)Exp. (suite)

On peut l’écrire comme suit:

Maximiser 2.X1 + X2;

Objectif X1 + 2.X2 ≤ 6;

X1 + X2 ≤ 4;

X1 ≤ 3;

Tel que X1, X2 ≥ 0.

111111

INTRODUCTION À LA


2. Résolution graphique des problèmes de PL à deux variables (suite)Exp. (suite)

L’ensemble des points

à l’intérieur du polygone

convexe sont appelés

solutions réalisables.

112112

INTRODUCTION À LA


3. Résolution des problèmes linéaires par la méthode du simplexeLa méthode graphique est facile lorsqu'il y a deux

variables, elle devient difficile pour trois variables etimpossible au delà.

Une méthode du simplexe a été développée parDantzig afin de résoudre ce type de problèmes deprogrammation linéaire.

113113

INTRODUCTION À LA


Dantzig propose quelques nominations dans la formestandard (forme canonique):

Maximiser cTx;

Objectif Ax+y = b;

Tel que: x,y ≥ 0, c ∈ ℜn, b ∈ ℜm, A ∈ ℜmxn

Variables de base

Variables hors base

114114

INTRODUCTION À LA


Dans la forme standard d’un programme linéaire, lesvariables d’écarts sont appelées variables de base (y),et les autres sont appelées variables hors base (x).

Une solution de base (contient les variables horsbase et les variables de base) est la solution où lesvariables hors base sont nulles.

Une solution faisable (réalisable, admissible) estune solution qui satisfait la fonction objectif.

Une solution faisable de base est la solution où lesvariables hors base (x) sont nulles et qui satisfait lafonction objectif.

115115

INTRODUCTION À LA


Pour la méthode du simplexe, on converti la formestandard du problème sous forme d’un tableau:

Variables de baseVariables hors base

Coefficients

des variables

de base

Coefficients de coût réduit

Cb b x1 x2 y1 y2 y3

c1 c2 0 0 0

0 y1 b1 a11 a12 1 0 0

0 y2 b2 a21 a22 0 1 0

0 y3 b3 a31 a32 0 0 1

ΣCbi*bi r1 r2 r3 r4 r5

116116

INTRODUCTION À LA


3. Résolution des problèmes linéaires par la méthode du simplexe (suite)

Une solution faisable de base est dite optimale si lescoefficients des variables de base (y) sont tous nonnuls.

Théorème: Une solution faisable de base est optimale siet seulement si les coefficients de coût réduit (ri)correspondants sont nuls.

Le but de la méthode du simplexe est de se déplacerd’une solution faisable de base à une autre jusqu’à cequ’on trouve la solution faisable de base optimale.

117117

INTRODUCTION À LA


Algorithme du simplexe:

1. Construire le tableau initial de la solution faisable debase de la forme standard du problème linéaire;

Cb b x1 x2 y1 y2 y3

c1 c2 0 0 0

0 y1 b1 a11 a12 1 0 0

0 y2 b2 a21 a22 0 1 0

0 y3 b3 a31 a32 0 0 1

ΣCbi*bi r1 r2 r3 r4 r5


Coefficients

des variables

de base

Coefficients de coût réduit

118118

INTRODUCTION À LA


Algorithme: (suite)

2. Calculer les coefficients de coût réduit rj

tel que:

BV = WV − % JX> · �>VY

>ZRm: est le nombre de variables de base.

119119

INTRODUCTION À LA


Algorithme: (suite)

3. Si rj ≤ 0 pour tous les j, alors la solution faisable debase est optimale; sinon aller à 4;

4. Sélectionnez la colonne ‘q’ tel que rq = max (rj) :remarquez que (rq > 0);

5. Si tous les coefficients de la colonne ‘q’ sont ≤ 0,alors le problème est sans limite; sinon aller à 6;

120120

INTRODUCTION À LA


Algorithme: (suite)

6. Sélectionner la ligne ‘p’ qui a�� [\*\] : �>_ > 0 ;

7. Modifier la variable de base de la ligne ‘p’ par lavariable de la colonne ‘q’;

8. Mettre à jour le tableau pour normaliser leséléments pivots (p,q) à 1, et le reste de la colonne dechaque pivot à 0 en utilisant des opérations sur leslignes;

9. Aller à 2.

121121

INTRODUCTION À LA


3. Résolution des problèmes linéaires par la méthode du simplexe (suite)

Exp. Soit le problème linéaire suivant:

Maximiser 4.x1 + 5.x2

Objectif 2.x1 + x2 ≤ 9

x1 ≤ 4

x2 ≤ 3

Tel que x1 ≥ 0, x2 ≥ 0

Appliquer l’algorithme du simplexe pour résoudre ceproblème.

122122

INTRODUCTION À LA


Exp. (suite)

La forme standard du problème:

Maximiser 45 T . U1U2 ;

Objectif2 1 1 0 01 0 0 1 00 1 0 0 1 .

U1U2a1a2a3= 943 ;

Tel que U1 U2 a1 a2 a3 ≥ 0 0 0 0 0

123123

INTRODUCTION À LA


Exp. (suite)

BR = WR − % JX> · �>Rc

>ZR = 4 − 0 ∗ 2 + 0 ∗ 1 + 0 ∗ 0 = 4

Cb b X1 X2 Y1 Y2 Y3

4 5 0 0 0

0 Y1 9 2 1 1 0 0

0 Y2 4 1 0 0 1 0

0 Y3 3 0 1 0 0 1

0 4 5 0 0 0


Coefficients

des variables

de base

124124

INTRODUCTION À LA


Exp. (suite)

q = 2ème colonne : là où rj est maximum

p = 3ème ligne

�� X>�>_ : �>_ > 0 = �� 91 , ? , 31Donc, pivot (3,2)

125125

INTRODUCTION À LA


Exp. (suite)

Pour normaliser le pivot à 1 on applique:

Ligne1 = Ligne1 - Ligne3

BR = WR − % JX> · �>Rc

>ZR = 4 − 0 ∗ 2 + 0 ∗ 1 + 5 ∗ 0 = 4q = 1ère colonne : là où rj est maximum

p = 1ère ligne

�� X>�>_ : �>_ > 0 = �� 62 , 41 , ?Donc, pivot (1,1)

126126

INTRODUCTION À LA


Exp. (suite)

Cb b X1 X2 Y1 Y2 Y3

4 5 0 0 0

0 Y19

6

2

2

1

0

1

1

0

0

0

-1

0 Y2 4 1 0 0 1 0

5 X2 3 0 1 0 0 1

0

15

4

4

5

0

0

0

0

0

0

-5

127127

INTRODUCTION À LA


Exp. (suite)

Pour normaliser le pivot à 1 on applique:

Ligne1 = Ligne1 / 2

Ligne2 = Ligne2 – Ligne1

BR = WR − % JX> · �>Rc

>ZR = 4 − 4 ∗ 1 + 0 ∗ 0 + 5 ∗ 0 = 0

128128

INTRODUCTION À LA


Exp. (suite)

Cb b X1 X2 Y1 Y2 Y3

4 5 0 0 0

0

4X1

9

6

3

2

2

1

1

0

0

1

1

1/2

0

0

0

0

-1

-1/2

0 Y24

1

1

0

0

0

0

-1/2

1

1

0

1/2

5 X2 3 0 1 0 0 1

0

15

27

4

4

0

5

0

0

0

0

-2

0

0

0

0

-5

-3

129129

INTRODUCTION À LA


Exp. (suite)

On trouve que tous les rj ≤ 0, donc on atteint la solutionfaisable optimale, qui est: (X1, X2, Y1, Y2, Y3) = (3, 3, 0,1, 0)

130130

INTRODUCTION À LA


Exp. (suite)

Graphiquement:

-1

-0,5

0

0,5

1

1,5

2

2,5

3

3,5

4

-1 0 1 2 3 4 5 6

x2=3 2.x1+x2=9 x2=0 x1=4 x1=0

131131

INTRODUCTION À LA


4. Dualité: Définitions et notions de baseLa méthode du dual simplexe est utilisée en

particulier lorsqu'il n'y a pas de solution faisable debase initiale au problème de la programmation linéaire.

Exp.

Minimiser 160.x1 + 120.x2 + 280.x3

Objectif 2.x1 + x2 + 4.x3 ≥ 1

2.x1 + 2.x2 + 2.x3 ≥ 3/2

Tel que x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

132132

INTRODUCTION À LA


4. Dualité: Définitions et notions de base (suite)Exp. (suite)

Maximiser -160.x1 - 120.x2 - 280.x3

Objectif 2.x1 + x2 + 4.x3 – Y1 = 1

2.x1 + 2.x2 + 2.x3 – Y2 = 3/2

Tel que x1 ≥ 0, x2 ≥ 0, y1 ≥ 0, y2 ≥ 0

La solution faisable initiale est (0, 0, 0, -1, -3/2)

alors que: X1 ≥ 0, X2 ≥ 0, Y1 ≥ 0, Y2 ≥ 0

133133

INTRODUCTION À LA


4. Dualité: Définitions et notions de base (suite)Exp. (suite)

Dans ce cas, on peut appliquer l’algorithme dualsimplexe.

Pour cela, nous allons changer la forme du problème.

134134

INTRODUCTION À LA


4. Dualité: Définitions et notions de base (suite)

Problème dual

Soit le problème primal:

Minimiser cTx;

Objectif Ax ≥ b;

Tel que: x ≥ 0, c ∈ ℜn, b ∈ ℜm, A ∈ ℜmxn

Son problème dual aura la forme:

Maximiser pTb;

Objectif pTA ≤ cT;

Tel que: p ≥ 0, c ∈ ℜn, p ∈ ℜm, b ∈ ℜm, A ∈ ℜmxn

135135

INTRODUCTION À LA


Problème dual (suite)Exp. Définissons le problème dual du problème précédent:

Problème primal

Minimiser 160120280T . U1U2U3 ;

Objectif: 2 1 42 2 2 . U1U2U3 ≥ 132 ;�� oA�: U1U2U3 ≥ 000 .

136136

INTRODUCTION À LA


Exp. (suite)

Problème dual

Maximiser r1r2 T . 132 ;Objectif: r1r2 T . 2 1 42 2 2 ≤ 160120280

T ;�� oA�: r1r2 ≥ 00

137137

INTRODUCTION À LA


Exp. (suite)

Maximiser P1 + 3/2.P2

Objectif 2.P1 + 2.P2 ≤ 160

P1 + 2.P2 ≤ 120

4.P1 + 2.P2 ≤ 280

Tel que P1 ≥ 0, P2 ≥ 0

On fait entrer les variables de base comme suit:

Maximiser P1 + 3/2.P2

Objectif 2.P1 + 2.P2 + Y1 = 160

P1 + 2.P2 + Y2 = 120

4.P1 + 2.P2 + Y3 = 280

Tel que P1 ≥ 0, P2 ≥ 0, Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0138

Cb c P1 P2 Y1 Y2 Y3

1 3/2 0 0 0

0

1

Y1

P1

160

40

20

2

1

0

2

0

0

1

1

-1/2

0

-1

0

0

0

1/2

0

3/2

Y2

P2

120

60

120

80

40

1

½

1

0

0

2

1

2

2

1

0

0

0

-1

-1/2

1

½

1

0

0

0

0

0

0

0

0

0

Y3

Y2

280

160160/3-40/3-20

4

3

1

0

0

2

0

0

0

0

0

0

0

-1

-3/2

0

-1

-1/3

2/3

1

1

1

1/3

1/3

1/2

0

-90

-160

-140

1

¼

0

1

3/2

0

-3/2

-3/2

0

0

-5/2

-2

0

-3/4

1

0

0

0

0

-1/2

Documents

Les flots INFORMATIQUE 3 - larbiguezouli.com