Chapitre 5 Solutions des exercices de révision

Chapitre 5 – Solutions des exercices de révision

Section 5.2 Quelques exemples supplémentaires de problèmes de réseaux

1. Érébus et les châteaux de neige.

La figure ci-dessous illustre un réseau associé à ce problème. Les éléments de ce modèle graphique

sont :

Flot. Les charges de parpaings de neige expédiées des glacières aux villes constituent

clairement le flot qui circulera dans le réseau.

Sommets émetteurs. Les glacières constituent le point de départ des charges de parpaings et

on crée donc dans le réseau les deux sommets émetteurs G1 et G2.

Sommets récepteurs. Les villes constituent la destination finale des charges de parpaings et on

crée donc dans le réseau les trois sommets récepteurs A, B et C.

Sommets de transbordement. Il n'y a aucun sommet de transbordement dans le réseau, car les

charges de parpaings sont acheminées directement des glacières aux villes.

Arcs. La présence ou l'absence d'un arc entre deux sommets se déduit des définitions

précédentes et du tableau des coûts d'acheminement des charges de parpaings fourni dans

l'énoncé. Le coût et les bornes reportés sur un arc se déduisent aisément du texte.

Le problème de réseau associé à la figure ci-dessus a été résolu à l'aide du solveur d'Excel. Une

solution optimale consiste à

2 Chapitre 5 – Les problèmes de réseaux

produire, en G1 , 200 charges de parpaings, dont 75 seront acheminées à la ville A et 125, à la

ville C;

produire, en G2 , 280 charges de parpaings, dont 25, 200 et 55 respectivement seront livrées

aux villes A, B et C.

Le coût minimal d'approvisionnement des villes s'élève à 290 875 $. Noter que les besoins des

trois villes sont satisfaits selon les minimums indiqués dans l'énoncé.

2. La collecte de déchets domestiques.

Pour chacun des quatre secteurs, S1 à S4, on introduit un sommet émetteur dans le réseau; de

même, les sommets récepteurs correspondront aux trois sites d'enfouissement, D1 à D3. On

ajoute des sommets de transbordement, T1 et T2, que l'on dédouble afin de traduire dans le

réseau les données (capacité et coût de traitement) associées aux centres. Voici le réseau

résultant.

Une solution optimale, dont le coût est de 2 280 euros par jour, recommande :

d'acheminer tous les déchets des secteurs S1 et S4 au centre de transbordement T1, tous ceux

de S3 au centre T2 et de répartir moitié-moitié les 20 tonnes de S2;

de traiter 40 tonnes par jour en T1 et 42 tonnes en T2;

de transporter les 42 tonnes traitées en T2 vers le site d'enfouissement D1 et de répartir les 20

tonnes de T2 moitié-moitié entre D2 et D3.

Solutions des exercices de révision 3

3. La société Kola.

Composantes du réseau

El Hadj doit décider combien de sacs acheter et vendre chaque mois. On associe dans un premier

temps les mois aux sommets du réseau, et le flot se composera de sacs de kola. Au début de chaque

mois i, El Hadj doit décider :

du nombre de sacs à acheter, ce qui se modélise en traitant comme émetteur le sommet associé

au mois i, c’est-à-dire en créant un arc virtuel • i;

du nombre de sacs à vendre, ce qui se modélise en considérant i comme sommet récepteur,

c’est-à-dire en ajoutant un arc virtuel i • ;

du nombre de sacs à entreposer dans le but de les vendre à la fin d'un mois subséquent, ce qui

se modélise par la transmission d’un flot de sacs le long d'un arc dont le sommet initial est

associé au mois i et dont le sommet terminal est associé au mois i+1.

Schématisées, les décisions de El Hadj associées au mois i se représentent par la figure suivante.

Comme la capacité d'entreposage de l'entrepôt durant le mois i est limitée, on dédouble le

sommet i en deux sommets notés Di et Fi , «début» et «fin» du mois. La figure au haut de la page

suivante donne la partie du réseau associée au mois 4. Par l'arc F3 D4 transitent les sacs de kola

qui étaient en stock à la fin du mois 3 et qui n'ont pas été vendus; ils resteront entreposés durant

le mois 4. L'arc • D4 achemine les sacs de kola achetés au début du mois 4; le coût de

transmission d'une unité de flot par cet arc est le coût d'achat (en milliers de FCFA) d'un sac de

kola au début du mois 4. Les coûts d'entreposage durant le mois 4 sont imputés à l'arc D4 F4

qui acceptera, comme flot, la somme des sacs non vendus à la fin du mois précédent (F3 D4) et

de ceux achetés au tout début du mois (• D4); une borne supérieure de 6 500 et un coût unitaire

de 50 FCFA sont donc attribués à cet arc. Le flot sur l'arc F4 • correspond au nombre de sacs

de kola vendus à la fin du mois 4 : pour tenir compte de la demande, ce nombre doit appartenir à

l'intervalle [1 400; 2 000]. Chaque sac qui emprunte l'arc F4 • rapporte un revenu de 17 000

F CFA, ce qui dans le réseau se traduit par un coût de 17. L'arc F4 D5 est similaire à l'arc

F3 D4 . Noter que, d'après la figure, une unité de flot incidente en D4 sera forcément transmise à

F4 pour ensuite se diriger soit vers le sommet virtuel • , soit vers D5 , ce qui correspond au fait

qu'un sac de kola acheté au début du mois 4 sera forcément entreposé au moins pendant un mois

avant d'être soit vendu en fin de mois 4, soit entreposé pendant le mois 5.


Modélisation graphique et solution optimale

Voici un réseau qui modélise le problème de la société Kola.

Une solution optimale

La figure ci-dessous illustre une solution optimale du modèle, le nombre reporté sur un arc

indiquant le flot qui l’emprunte. S’il applique la stratégie recommandée par cette solution,

El Hadj répondra à la demande maximale seulement lors des mois 1, 2, 3, 5 et 8 ;

durant les autres mois, il limitera ses livraisons à 70 % de la demande, soit le minimum qu’il

s’impose pour garder sa part du marché ;

au cours des mois 2, 3, 6 et 10, il n’effectuera aucun achat, se contentant de puiser dans les

stocks en entrepôt ;

l’entrepôt sera vide à la fin du 10e mois, comme il se doit ;

le profit s’élèvera à 39 760 000 F CFA.

Noter que le prix à l’achat est au plus bas le mois 1 et que notre spéculateur se procurera 6 500 sacs,

emplissant l’entrepôt à pleine capacité. De même, le prix à la vente le mois 4 est inférieur au prix à

l’achat de tous les mois précédents et El Hadj limitera ses livraisons au minimum qu’il s’autorise.


Le tableau « Données concernant les arcs » du gabarit est reproduit ci-dessous.

Données concernant les arcs Solution optimale

No Nom S. initial S. terminal Coût un. Borne inf. Borne sup. Flot Coût

1 M1: Achats . D1 18 0 6500 6 500 117 000

2 M2: Achats . D2 24 0 6500 0 0

3 M3: Achats . D3 20 0 6500 0 0

4 M4: Achats . D4 20 0 6500 900 18 000

5 M5: Achats . D5 19 0 6500 6 500 123 500

6 M6: Achats . D6 23 0 6500 0 0

7 M7: Achats . D7 22 0 6500 4 800 105 600

8 M8: Achats . D8 23 0 6500 300 6 900

9 M9: Achats . D9 19 0 6500 5 600 106 400

10 M10:Achats . D10 20 0 6500 0 0

11 M1: Ventes F1 . -20 1400 2000 2 000 -40 000

12 M2: Ventes F2 . -20 1400 2000 2 000 -40 000

13 M3: Ventes F3 . -23 1400 2000 2 000 -46 000

14 M4: Ventes F4 . -17 1400 2000 1 400 -23 800

15 M5: Ventes F5 . -22 1400 2000 2 000 -44 000

16 M6: Ventes F6 . -22 2800 4000 2 800 -61 600

17 M7: Ventes F7 . -23 2800 4000 2 800 -64 400

18 M8: Ventes F8 . -24 2800 4000 4 000 -96 000

19 M9: Ventes F9 . -19 2800 4000 2 800 -53 200

20 M10:Ventes F10 . -18 2800 4000 2 800 -50 400

21 M1: Entrep D1 F1 0,05 0 6500 6 500 325

22 M2: Entrep D2 F2 0,05 0 6500 4 500 225

23 M3: Entrep D3 F3 0,05 0 6500 2 500 125

24 M4: Entrep D4 F4 0,05 0 6500 1 400 70

25 M5: Entrep D5 F5 0,05 0 6500 6 500 325

26 M6: Entrep D6 F6 0,05 0 6500 4 500 225

27 M7: Entrep D7 F7 0,05 0 6500 6 500 325

28 M8: Entrep D8 F8 0,05 0 6500 4 000 200

29 M9: Entrep D9 F9 0,05 0 6500 5 600 280

30 M10:Entrep D10 F10 0,05 0 6500 2 800 140

31 M1: F-D F1 D2 0 0 . 4 500 0

32 M2: F-D F2 D3 0 0 . 2 500 0

33 M3: F-D F3 D4 0 0 . 500 0

34 M4: F-D F4 D5 0 0 . 0 0

35 M5: F-D F5 D6 0 0 . 4 500 0

36 M6: F-D F6 D7 0 0 . 1 700 0

37 M7: F-D F7 D8 0 0 . 3 700 0

38 M8: F-D F8 D9 0 0 . 0 0

39 M9: F-D F9 D10 0 0 . 2 800 0


4. La Société nationale de niobium de Laputa.

(a) Le réseau complété est donné ci-dessous – les coûts négatifs des arcs virtuels à droite

réfèrent à la question (b). L’unité de flot est la tonne de métal pur; les coûts unitaires sur les arcs

sont exprimés en dollars laputiens. Ceux entre usines et marchés, qui sont associés aux arcs

V B, U B, ..., W Y, représentent les coûts de transport de 1 tonne de métal pur. Pour les

autres arcs, on doit convertir les coûts fournis dans l'énoncé : il faut 25 tonnes de minerai de la mine

M pour obtenir 1 tonne de métal pur et, par conséquent, les coûts reportés sur les arcs M,

M V et M U sont obtenus en multipliant par 25 les coûts mentionnés dans l'énoncé; de

même, il faut multiplier par 20 les coûts associés à la mine N. Enfin, les bornes des arcs virtuels

M et N tiennent compte de la conversion des minerais en équivalents de métal pur.

(b) Il suffit, par exemple, de reporter ces prix de vente sur les arcs virtuels B , L et

Y . Ces revenus sont affectés d'un signe négatif.

(c) Il suffit de dédoubler les noeuds associés aux usines et de reporter les coûts et les bornes

appropriés sur les arcs V V', U U' et W W'. Voici le réseau résultant.


5. La planification de la production chez Assemblor.

(a) Le flot sur l'arc F1 A1 représente le nombre d'unités du produit P assemblées durant la

semaine 1. Les arcs F1 F2 et A1 A2 donnent respectivement le nombre de paires de pièces X

et le nombre d'unités assemblées de P qui seront stockées à l'usine de Longueuil à la fin de la

semaine 1.

(b) Voici le réseau une fois complété.


(c) Il s'agit de dédoubler les arcs virtuels Ai • et de reporter négativement les deux prix. La

figure de gauche ci-dessous indique, à titre d'exemple, ce qu'on obtient pour le sommet A1.

(d) Il s'agit d'ajouter, pour i = 3, 4, 5, 6, un deuxième arc virtuel • Fi, sur lequel sont reportés

un coût de 40 et des bornes (0; 10). La figure de droite ci-dessus indique, à titre d'exemple, ce

qu'on obtient pour F3.

(e) Il s'agit d'ajouter, entre les sommets Ai et Fi, un deuxième arc sur lequel sont reportés un

coût de 43 et des bornes (0; 28) ou (0; 35).

Voici un réseau modifié qui tient compte des contraintes des questions (c) à (e).


Section 5.3 Quelques cas particuliers du problème de transbordement

1. Les hauts fourneaux.

(a) Pour modéliser une situation réelle comme un problème de transport, il faut déterminer ce

qui, dans cette situation, constitue les origines du problème de transport (avec leurs

disponibilités), ce qui constitue les destinations (avec leurs demandes) et, finalement, quels sont

les coûts unitaires de transport entre les origines et les destinations. Ici, trois types de matériaux

doivent être brûlés dans un ou plusieurs des quatre hauts fourneaux dont la capacité quotidienne

de traitement est limitée. Si l'on associe la capacité de traitement des hauts fourneaux à la

disponibilité des origines, les quantités des trois types de matériaux à brûler aux demandes des

destinations et les coûts de traitement aux coûts de transport, le problème des hauts fourneaux

s'écrit comme un problème de transport dont le tableau des coûts unitaires est le suivant.

Minerai Voitures Ferraille Disponibilité

Haut fourneau 1 500 325 370 270

Haut fourneau 2 450 330 360 185

Haut fourneau 3 475 345 380 205

Haut fourneau 4 510 310 350 245

Demande 450 275 180 905

(b) Le tableau suivant énumère les différents arcs du réseau utilisé et donne une solution

optimale. Le haut fourneau numéro 1 traitera 60 tonnes de minerai et 210 de voitures; le 2e et le

3e réserveront toute leur capacité au minerai; enfin, le 4

e traitera 65 tonnes de voitures et 180 de

ferraille. Le coût total pour la fonderie s’élèvera à 362 025 dollars par jour.

Données concernant les arcs Solution optimale

No Nom S. initial S. terminal Coût un. Borne inf. Borne sup. Flot Coût

1 Capacité de HF1 . HF1 0 270 270 270 0

2 Capacité de HF2 . HF2 0 185 185 185 0

3 Capacité de HF3 . HF3 0 205 205 205 0

4 Capacité de HF4 . HF4 0 245 245 245 0

5 Arc 05 HF1 M 500 0 . 60 30000

6 Arc 06 HF1 V 325 0 . 210 68250

7 Arc 07 HF1 F 370 0 . 0 0

8 Arc 08 HF2 M 450 0 . 185 83250

9 Arc 09 HF2 V 330 0 . 0 0

10 Arc 10 HF2 F 360 0 . 0 0

11 Arc 11 HF3 M 475 0 . 205 97375

12 Arc 12 HF3 V 345 0 . 0 0

13 Arc 13 HF3 F 380 0 . 0 0

14 Arc 14 HF4 M 510 0 . 0 0

15 Arc 15 HF4 V 310 0 . 65 20150

16 Arc 16 HF4 F 350 0 . 180 63000

17 Minerai M . 0 450 450 450 0

18 Voitures V . 0 275 275 275 0

19 Ferraille F . 0 180 180 180 0


2. La livraison des berlingots de lait.

(a) Il faut déterminer ici par quel camion ou fourgonnette chaque camp sera desservi. Il faut

donc essentiellement affecter des véhicules à des camps. Il s’agit d’un problème analogue à un

problème d'affectation, la différence venant du fait que les camions desserviront deux camps chacun.

Traduit dans la terminologie générique du problème d'affectation, un employé (le camion) devra être

affecté à deux tâches (les camps), au lieu d'une tâche comme c'est le cas dans le problème classique

d'affectation. La figure ci-dessous illustre le modèle graphique associé à ce problème. Les sommets

émetteurs correspondent aux véhicules et les sommets récepteurs, aux camps. Les coûts des

différents arcs dans le modèle sont donnés par les kilomètres supplémentaires qu'un véhicule doit

parcourir pour desservir un camp.

Le tableau suivant décrit une solution optimale. Le nombre total de kilomètres supplémentaires à

parcourir s'élève à 15 + 10 + 18 + 11 + 11 + 19 = 84 kilomètres au minimum.

Camp 1 2 3 4 5 6

Véhicule C2 F2 C1 C2 F1 C1

Distance parcourue (en km) 15 10 18 11 11 19

(b) Puisque chaque camion Ci dessert deux camps, on peut imaginer qu'il existe deux copies,

Ci et Ci’, de ce camion, chaque copie livrant les berlingots à un camp. Il s'agit donc d'affecter les

six «véhicules» C1 , C1’, C2, C2’, F1 et F2 aux six camps 1, 2, ..., 6. On obtient alors un problème

d'affectation dont la matrice des coûts est donnée par le tableau suivant. On retrouve évidemment

la même solution optimale.

1 2 3 4 5 6

C1 18 16 18 14 16 19

C1’ 18 16 18 14 16 19

C2 15 14 16 11 17 16

C2’ 15 14 16 11 17 16

F1 13 16 18 18 11 18

F2 16 10 19 14 19 15


3. La compagnie Abitibus.

Pour déterminer comment apparier les trajets, il faut essentiellement affecter des allers à des

retours. Considérons, à titre d'exemple, les trajets A et 2 : si A constitue l'aller et 2 le retour, le

temps d'attente est de 19,5 heures à Amos; si par contre le trajet 2 est l'aller et A le retour, on

obtient un temps d'attente de 14,5 heures à Montréal; par conséquent, si le trajet A est affecté au

trajet 2, on subira un coût de 14,5 heures et l'équipage de l'autobus résidera à Amos. Dans

certains cas, l'équipage pourra résider indifféremment dans l'une ou l'autre des deux villes, car les

temps d'attente sont identiques; par exemple, si l'on apparie les trajets A et 1, l'équipage attendra

17 heures, qu'il réside à Montréal ou à Amos.

Le problème d'Abitibus est donc équivalent à un problème d'affectation, dont la forme générique

est donnée à la figure 5.41 du manuel. Pour décrire de façon complète un problème d'affectation,

il suffit d'en donner la matrice des coûts d'affectation. Ici, ces coûts correspondent aux temps

d'attente et sont donnés dans le tableau suivant.

1 2 3 4 5

A 17 14,5 7,75 5 12

B 16 15,5 8,75 4 11

C 11,5 14 13,25 10,5 6,5

D 5 7,5 14,25 17 10

E 11 8,5 8,25 11 16

De la matrice des coûts d'affectation, on déduit, comme à la section 5.3.3, le modèle graphique

suivant :

aux lignes sont associés des sommets émetteurs, dont les bornes sont (1; 1);

aux colonnes sont associés des sommets récepteurs de bornes (1; 1);

à une entrée à l'intersection de la ligne i et de la colonne j on associe un arc de coût cij .

Le tableau suivant décrit une solution optimale. Le temps total minimal d'attente est de 31,75

heures.

Aller Retour Lieu de résidence

de l'équipage

Temps d'attente

(en heures)

3 A Amos 7,75

B 4 Montréal 4

C 5 Montréal 6,5

D ou 1 1 ou D Montréal ou Amos 5

2 E Amos 8,5


Section 5.5 Les problèmes apparentés à des problèmes de réseaux

1. La compagnie Chimex.

(a) Le modèle graphique demandé est donné à la page suivante. On notera qu'il est composé

de deux sous-réseaux indépendants, l'un pour l'engrais P1, l'autre pour P2. L'unité de flot est le

millier de tonnes; la fonction-objectif est exprimée en milliers de dollars.

(b) Le sommet E12 est un sommet de transbordement. Voici la contrainte linéaire associée,

qui indique que le flot net émergeant de ce sommet est nul :

𝑥𝐸12𝐸′12 − 𝑥𝑈12𝐸12 − 𝑥𝑈22𝐸12 = 0.

(c) Le sommet U12 est un sommet émetteur. Voici la contrainte linéaire associée, qui indique

que le flot net émergeant de ce sommet satisfait aux bornes reportées dans le modèle :

0 ≤ 𝑥𝑈12𝐸12 + 𝑥𝑈12𝐸22 ≤ 50.

(d) Non. Un modèle graphique modifié est donné à la page suivante. Les deux portions du

réseau sont reliées cette fois, car l'espace disponible dans les entrepôts est utilisé pour les deux

engrais conjointement. Mais, le modèle graphique ne peut à lui seul garantir que le flot reçu en

C11 représente bien de l'engrais P1 : en effet, les engrais P1 et P2 expédiés séparément à l'entrepôt

E1 sont, du point de vue du réseau, indiscernables à la sortie du sommet E1. Pour traduire

correctement le problème modifié, il faut ajouter au modèle linéaire associé au réseau les

contraintes d'équilibre suivantes.

𝑥𝑈11𝐸1 + 𝑥𝑈21𝐸1 = 𝑥𝐸′1𝐶11 + 𝑥𝐸′1𝐶21


𝑥𝑈11𝐸2 + 𝑥𝑈21𝐸2 = 𝑥𝐸′2𝐶11 + 𝑥𝐸′2𝐶21

𝑥𝑈12𝐸1 + 𝑥𝑈22𝐸1 = 𝑥𝐸′1𝐶12 + 𝑥𝐸′1𝐶22

𝑥𝑈12𝐸2 + 𝑥𝑈22𝐸2 = 𝑥𝐸′2𝐶12 + 𝑥𝐸′2𝐶22 .

2. Les trois conditionnements de Pastissimo.

Le réseau de la figure 5.23 constitue une représentation graphique pertinente du problème des

trois conditionnements de Pastissimo. Cependant, le modèle linéaire associé à ce réseau n'est pas

adapté au nouveau contexte et il faut le modifier de la façon suivante.

Tout d'abord, on introduit des variables yhj (h = 1, 2, 3 et j = 1, …, 6) qui représentent le

nombre de sacs du format numéro h livrés à la fin du mois j. On exigera que ces variables

soient entières.

Les termes dans la fonction-objectif reliés aux arcs Fh → ● sont remplacés par les revenus

tirés de la vente des sacs, c'est-à-dire par la somme des trois expressions suivantes :

1,08(y11 + y12) + 1,28(y13 + y14 + y15 + y16)

5,02(y21 + y22 + y23 + y24 + y25 + y26)


8,81(y31 + y32 + y33 + y34 + y35 + y36).

Le flot émergeant du sommet Fh se décompose en quatre termes qui sont exprimés dans des

unités différentes. La contrainte de conservation du flot en Fh prend donc une forme

particulière. Par exemple, celle associée à F2 s'écrit :

1000 xD2F2 + 1000 xF1F2 = 1000 xF2F3 + y12 + 4 y22 + 7 y32.

Les équations de conservation du flot aux sommets F3, F4 et F5 sont semblables; dans celle

pour F1, le second terme du membre gauche est absent et dans celle associée à F6, c'est le 1er

terme du membre droit qui manque.

Le premier des trois engagements pris par Pastissimo signifie que les variables yhj sont

bornées ainsi:

yhj ≥ 80 tout h et tout j

y1j ≤ 2000 tout j

y2j ≤ 500 tout j

y3j ≤ 500 tout j.

Le 2e engagement se traduit par l'ensemble des six contraintes suivantes :

0,1 y1j + 0,1 y2j – 0,9 y3j ≤ 0 tout j.

Le tableau ci-dessous décrit une solution optimale.

Mois 1 2 3 4 5 6 Coût (Revenu)

Achat 5 4 5 3 4 5 26 045

Production 6 5 4 4 4 3 4 145

Entrepôt – Blé 1 0 1 0 0 – 40

Magasin 0,42 0 0 0 0 – 10,50

Sacs de 1 kg 80 80 2000 2000 2000 1469 -9 733,12

Sacs de 4 kg 500 460 80 80 80 80 -6 425,60

Sacs de 7 kg 500 500 240 240 240 173 -16 677,33

Le revenu net de Pastissimo s'élève à 2 595,55 dollars :

(9 733,12 + 6 425,60 + 16 667,33) – (26 045 + 4 145 + 40 + 10,50) = 2 595,55.

Documents

Chapitre 5 Solutions des exercices de révision