Praogrammation des charrois automobiles pour la distribution de la boisson dans la ville de Bukavu: Cas de la Bralima/Bukavu(2005-2006)

3.2. Introduction à la théorie de graphe

3.2.1. Définition de graphe

Soit x un ensemble de sommets fini et dénombrable

X = (x₁, x₂, x₃, ...x₄), soit m, une application multivoque et ex une appliation de x dans lui-même noté x de x, dans ce cas, le couple (x, m) défini un graphe noté G. (MVIBUDULU KALUYIT Jacques, cours de la recherche opérationnelle).

Ex. : Soit l'ensemble de sommets de x = (x₁, x₂, x₃, x₄, x₅, x₆) l'application multivoque correspondant à chaque sommet et peut se présenter comme suit :

X m (x)

X₁ x₂, x₃

X₂ x₄

X₃ x₂, x₄

X₄ x₅, x₆

X₅ x₆

X₆

Représentation d'un graphe

Le graphe est représenté par un ensemble de points reliés entre eux par des flèches. La flèche relie un sommet X_i X_j appartenant à un sommet X_i X_j si X_j m (X_i). Partant de notre exemple, on peut avoir la représentation de graphe ci-après :

X₂

X₁

X₃ X₄

X₅ X₆

3.2.2. Sommet suivant et sommet précédent

Un sommet X_j est dit « suivant » de X_i s'il y a une flèche de X_i vers X_j m (X_i). Dans ce cas, X_i est dit « précédent » de X_j. L'ensemble de suivants de x est symbolisé par S (x). L'ensemble de précédents de x est symbolisé par P (x).

Ainsi pour notre exemple on aura le tableau de suivant.

Tableau de suivant (Dictionnaire de suivant)

S S (x)

X₁ -

X₂ x₁, x₃

X₃ x₁

X₄ x₂, x₃

X₅ x₄

X₆ x₄, x₅

Le tableau de précédent est ainsi appelé dictionnaire de précédent. Il s'obtient du dictionnaire de suivant. Pour cela, la procédure est la suivante :

On note sur la ligne x_i les numéros des lignes dans lesquelles x_i apparaît comme suivant. Ainsi, si on applique cette procédure on aura le tableau de précédent ci-après :

P P (x)

X₁ -

x₂ x₁, x₃

x₃ x₁

x₄ x₂, x₃

x₅ x₄

x₆ x₅, x₄

3.2.3. Les points de vente de la BRALIMA

A partir de cette théorie nous pouvons l'applliquer à la réalité rencontrée à la Bralima/Bukavu. Ainsi donc, par son circuit de distribution, la ville de Bukavu a 2 axes, dont le 1^er axe appelé VILLE 1 et le 2^e axe VILLE 2. Et chacun d'axes a ses points de ventes bien identifiés.

I) Les principaux points de vente de l'axe 1 peuvent se présenter comme suit :

X₁ : Bralima (point de départ)

x₂ : Place de l'indépendance (ces points de vente a comme dépôts relais :

TEM'S 1)

X₃ : Av. P.E LUMUMBA/Labotte (FAIDA, NABINTU 4, JEANNE)

X₄ : Athénée d'Ibanda (KITAMBALA 2, MAMAN JENIFER)

X₅ : AV. P.E LUMUMBA (La source 2, NOTRE VRAI SIEGE)

X₆ : NYAWERA Marché (super Copin, NABINTU 2, Alexis BAGUMA 2,

BITIJULA)

X₇ : Cercle Hippique (Maman MUDERHWA)

X₈ : Camp Saïo (Maman MUDERWHA)

X₉ : Nganda Belvédère (KONDA, BIGIRIMANA, KITAMBALA 1)

X₁₀ : AV. Cimetière (MUSHAMALIRWA, NABINTU 3)

X₁₁ : DGI (MUKULU, BIREM, CIGOHO)

X₁₂ : Rond point ISP (CIKIZA, BOUTIQUE RAFIKI, MAMAN DEPS,

MUGENGE)

X₁₃ : Rond point Major Vangu (WASSO AKILI, BUHENDWA, MUHANANO,

CHOKOLA)

X₁₄ : Panzi (MUSAFIRI, Jean MADO).

Pour l'axe 2 les principaux points des ventes sont :

X₁ : Bralima (Point de départ)

x₂ : Beach MUHANZI (MATATA, TEM'S 2)

x₃ : AV. KIBOMBO (Trois canards, DA LETHY)

x₄ : Av. Industriel (Maman Tantine)

x₅ : Nyamugo deux poteaux (TAIFA)

x₆ : Nyamugo Marché (Alain, KONDA 1, AYAYS)

x₇ : Essence KIBONGE (JOMBA MONGANE, CARITAS)

x₈ : BUHOLO V (INTERNET, M'BISIMWA, KIZO'S)

x₉ : Pas à pas (Maman Anny, BAHUGUKE, MUSHAGA, CIRUZA 1)

x₁₀ : BUHOLO IV (NGOMO)

x₁₁ : CHIMPUDA (Flavien, urelie)

x₁₂ : Avenue KADURU (MAMAN MUOMERWA)

x₁₃ : Avenue KASALI (Place du Dialogue)

x₁₄ : Nyamugo Stade (N'SHANGALUME RUNINGA)

x₁₅ : CIRIRI (MAKERA, MBASWA, CLAIRE)

x₁₆ : CAMP TV (BABA TANTINE, ROMAIN)

x₁₇ : Marché Nkafu (SIKUZANI, MAFUALA, VERONIQUE)

x₁₈ : AV. Route de Goma (M'NYAMUKONDE) « BAGIRA »

x₁₉ : QUARTIER A (WENGA, MAMA SILLY)

x₂₀ : AUX 7 FONTAINES/Place communale Bagira (NABINTU 1)

x₂₁ : Quartier B (NOTRE SOURCE 1)

D'une manière générale, nous pouvons représenter ces deux axes en utilisation la méthode de graphe évoquée précédemment.

I. L'AXE 1 (VILLE 1)

a) Le graphe de l'axe 1

P P (x)

X₁ -

X₂ X₂, X₃, X₄

X₃ X₃, X₄, X₅

X₄ X₄, X₅, X₆

X₅ X₅, X₆, X₇

X₆ X₆, X₇, X₈

X₇ X₇, X₈, X₉

X₈ X₈, X₉, X₁₀

X₉ X₉, X₁₀, X₁₁

X₁₀ X₁₀, X₁₁, X₁₂

X₁₁ X₁₁, X₁₂, X₁₃

X₁₂ X₁₂, X1₃, X₁₄

X₁₃ X₃, X₁₄

X₁₄ X₄

b) Construction graphe ordonné

La procédure de détermination de niveau :

1. On commence toujours par la détermination de niveau zéro (NO), on le détermine comme suit : les sommets de NO correspondent aux sommets n'ayant pas de précèdent

NO = {x₁}

2. Niveau 1 (N₁)

Les sommets de N₁ s'obtiennent à partir des sommets de niveau zéro.

Pour cela, on barre sur toutes les lignes partout où se trouve les sommets de NO. Si la ligne est complètement barrée, les sommets correspondant sont de N_1.

N₁= {x₂, x3, x4}

3. Niveau 2 (N₂)

Les sommets de N₂ s'obtiennent de niveau un, pour cela, on barre sur trouves lignes partout où se trouve les sommets de NO. Si la ligne est complètement barrée, les sommets correspondant sont de N₁

N₂= {x₅, x₆}

4. niveau 3 (N₃)

Le processus continue comme précédemment en portant du niveau 2.

N₃= {x₆, x₇}

5. Niveau 4 (N₄)

N₄={x₇, x₈}

6. Niveau 5 (N₅)

N₅= {x₈,x₉}

7. Niveau 6 (N₆)

N₆={x₉,x₁₀}

8. Niveau 7 (N₇)

N₇={x₁₀,x₁₁}

9. Niveau 8 (N₈)

N₈={x₁₁,x₁₂}

10. Niveau 9 (N₉)

N₉={x₁₂,x₁₃}

5. Niveau 10 (N₁₀)

N₁₀={x₁₃,x₁₄}

6. Niveau 11 (N₁₁)

N₁₁={x₁₄}

c) Construction de graphe ordonné pour l'axe1 (N° 1)

7h30' N 6h°° 4h30' 3h°° 1h30é de la journée

8h°° de la journée

X₂ x₅ x₉ x₁₃

400m

X₁ x₃ x₇ x₁₁

X₈

X₁₄

X₄ x₆ x₁₀ x₁₂

SOURCE : nos constructions

Comme nous l'avons évoqué précédemment, l'approche de la programmation dynamique s'effectue par la décomposition en sous-problème, du problème concerné et l'analyse commence par traiter d'abord les sous problèmes qui sont situés chronologiquement les derniers en terminant par les sous problèmes situé ou encore selon les principes LIFO (last in first out) « première sortie, dernière entrée »

Ainsi, lorsqu'un problème est divisé en sous-problème :1, 2,3 les inputs des 3è sous-problèmes sont considérés comme étant les out put du 2è problème. Et des inputs du deuxième sous-problème sont les outputs du 1è sous-problème.

d) Résolution de problème

· Procédure

Imaginons un poste de vente quelconque Pi où le vendeur veut minimiser les coùts (c) pendant une allée de m heures vers la déstination J.

Ainsi, ces coûts C est fonction du point de départ (Poste Pi) et du nombre de jour de W requises (n) pour effectuer le travail au point J. on peut alors dire :

C (i, r) au coût minimal de kilomètres à parcourir par les charrois automobile de la Bralima au moment où il ne reste que n heures pour atteindre la destination.

Ces coûts peuvent être exprimés mathématiquement par une option fonctionnelle. Ainsi, l'équation fonctionnelle à maximiser ou à minimiser au niveau de chaque sous-problème sera :

C (i,n) = max [C_ij + C(j, n-1)].

Pour le problème de minimisation, l'équation sera alors:

C(i, n) = min [C_ij + C(j, n-1]

C_ij = les kilomètres à parcourir en allant du poste X_i vers le poste X_j.

C_j, n-1 = les kilomètres à parcourir pendant l e reste de temps du travail soit n-1 heures vers X_j.

· Analyse

Soit le 1^er sous-problème, en effet, le vendeur de la Bralima se trouvant à une 1h30' du point d'arrivée.

PANZI (X₁₄), il sera alors à l'un des points de vente ci-après

(Points de départ) : X₁₂, X₁₁, X₁₃.

L'équation fonctionnelle de minimisation sera appliquée à chacun de ces points de vente : C(14, 1), C(11, 1), C(13, 1).

C(13, 1) = min (C_nj + C(j, 1-1) tel que j = 14

= min (C(nj) + C(j, 0) tel que j = 14

= min [(C_nj + C(14,0)]

N.B : c(14, 0) = 0

C'est-à-dire que C (13, 1) = 500+0 = 500m 5 km

· Point de vente X₁₁

C₁₁, ₁ = min (C_11j + C_j, 1-1) tel que j = 14

= min (C_11j = Cj, 0 tel que j = 14

= 915 + 0 = 915m 9,15km

· Point de vente X₁₂

C₁₂, ₁ = min (C_12j + C_j, 1-1) tel que j = 14

= min (C_{12, 1} + C₁₄, ₀)

= min (800 + 0)

= 800m 8km

9. Deuxième sous-problème

A ce niveau les vendeurs de la Bralima sera à 3h°° de vente (journée) pendant la journée. Le vendeur peut atteindre les points de vente suivant : X₉, X₈, X₁₀.

· Point de vente X₉

C (₉, ₂) = min (C_9, 2 + C_j, 2-1) tel que j = 13, 12

= min (C_{9, 2} = C_j, ₁) tel que j = 13, 12

= min (600 + 500, 200 + 800)

= min (1100, 1000)

= 1000m 10km.

· Point de vente X₈

· C (₈, ₂) = min (C_8, 2 + C_j, 1) tel que j = 11, 12

= min (790 + 914, 600 + 800)

= min (1705, 1400)

= 1400m 14km.

· Point de vente X₁₀

C (₁₀, ₂) = min (C_{10, 2} + C_j, 1) tel que j = 13, 14

= min (940 + 500, 1560 + 0)

= min (1440, 1560)

= 1440m 14,4km.

10. Troisième sous-problème

Le vendeur de la Bralima est à 4h30' de la distribution et peut se trouver à l'un des points de ventes X₅, X_7, X₆ et doit passer par l'un des postes suivants : X_8, X_9, X₁₀ avant d'arriver à la destination. A partir du poste X₅ = C(5,3), C(7, 3), C(6, 3).

C (₅, ₂) = min (C_{5, 3} + C_j, 3-1) tel que j = 9, 8

= min (C_{5, 3} + C_j, 2) tel que j = 9, 8

= min (280 + 1000, 730 + 1400)

= min (1280, 2130)

= 1280m 12,8km.

· Point de vente X₇

C(7,3) = min [C(_7,3) + C(_j,2)] tel que j =11, 10

= min (214 + 915, 375 + 1440)

= min (1229, 1815)

= 1229m 12,29km

· Point de vente X₆

C(6,3) = min [C(_6,3) + C(_j,2)] tel que j =9, 10

= min (170 + 1000, 413 + 1440)

= min (1170, 1815)

= 1170m 11,70km

11. Quatrième sous-problème

Le vendeur de la Bralima est à 6h°° de la journée vers la destination finale. Aussi à 6h°° vers Panzi, le vendeur peut arriver à l'un des ces 3 points de ventes : X₅, x₆, x₇. a partir de ces points de vente

X₂ = C(_2,4), C(_3,4), C(_4,4)

· Point de vente X₂

C(_2,4)) = min [C(_2,4) + C(_j,3)] tel que j = 5,6

= min (320 + 1280, 435 + 1170)

= min (1600, 1605)

= 1600m 16km

· Point de vente X₃

C(_3,4)) = min [C(_3,4) + C(_j,3)] tel que j = 7,6

= min (7000 + 1229, 310 + 1170)

= min (1929, 1480)

= 1480m 14,8km

· Point de vente X₄

C(_4,4)) = min [C(_4,4) + C(_j,3)] tel que j = 7,8

= min (320 + 1280, 435 + 1170)

= min (1441, 2070)

= 1441m 14,41km

12. Cinquième sous-problème

Le vendeur est à 7h30 ou à 8h°° avant d'atteindre le point final. Le vendeur peut arriver à l'un de ces 3 points de vente : x₁, x₂, x₃.

De la Bralima X₁

C(_1,5) = min [C(_1,5) + C(_j,4)] tel que j = 2,3,4

= min (400 + 600, 615 + 1480, 775 + 1441)

= min (2000, 2095, 2216)

= 2000m 20km

Au courant de la journée le vendeur de la Bralima pourra effectuer 20km. Après avoir évalué les distances à parcourir, on peut alors indiquer le tableau de l'itinéraire relatif à ces différents points de vente :

- C(14,0) = 0 - C(7,3) = 12,9km

- C(13,1) = 5km - C(6,3) = 11,7km

- C(12,1) = 8km - C(2,4) = 16km

- C(11,1) = 10km - C(3,4) = 14,8km

- C(9,2) = 14km - C(4,4) = 14,41km

- C(10,2) = 14,4 - C(1,5) = 20km

- C(5,3) = 12,8

Le tableau de l'itinéraire peut se présenter comme suit:

C(₁₃,₁) = 5km

C(₁₂,₁) = 8km

C(₁₁,₁) = 9,15km

C(₁₄,₀) = 0

On place à gauche les distances à parcourir ci-dessous, d'autres distances au niveau du 5^e sous problème.

C₁₃,₁ = 5km

C₁₂,₁ = 8km

C₁₁,₁ = 9,15km

C₁₄,₀ = 0

C₉,₂ = 10km

C₈,₂ = 14km

C₁₀,₂ = 14,4km

C₁₀,₂ = 14,4km

C₈,₂ = 14km

Au niveau du 4^e sous-problème, on placera les 3 points de vente au coût optimale à gauche de 3 points de ventes situés à droite.

C₉,₁ = 10km

C₈,₂ = 14km

C₁₀,₂ = 14,4km

C₁₄,₀ = 0

C₅,₃ = 12,8km

C₆,₃ = 11,7km

C₁₃,₁ = 5km

C₁₂,₁ = 8km

C₁₁,₁ = 9,15km

C₇,₃ = 12,8km

Au 4^e sous-problème, on place toujours les distances minimales à parcourir par le vendeur de la Bralima à gauche de ces 3 points de vente situés à droite.

C₆,₂ = 11,7km

C₁₄,₀ = 0

C₂,₄ = 16km

C₄,₄ = 14,41km

C₁₃,₁ = 5km

C₁₂,₁ = 8km

C₁₁,₁ = 9,15km

C₃,₄ = 14,8km

C₉,₂ = 10km

C₈,₂ = 14km

C₁₀,₂ = 14,4km

C₇,₃ = 12,29km

C₅,₃ = 12,8km

Quant au 5^e sous-problème, on aura un seul poste (le point de départ) la flèche sera de la case C (^1,4) vers la case C (_4,4) car il a obtenu son niveau minimum de j = 4.

C₆,₃ = 11,7km

C₁₄,₀ = 0

C₂,₄ = 16km

C₄,₄ = 14,41km

C₁₃,₁ = 5km

C₁₂,₁ = 8km

C₁₁,₁ = 9,15km

C₃,₄ = 14,8km

C₉,₂ = 10km

C₈,₂ = 14km

C₁₀,₂ = 14,4km

C₇,₃ = 12,29km

C₅,₃ = 12,8km

C₄,₁=20km

Le chemin qui désigne le point de vente au coût minimal se fait ressortir facilement.

C(₄,₁) C(₄,₄) C(₇,₃) C(₉,₂) C(₁₃,₁) C(₄,₀)

Ou X₁ X₄ X₇ X₉ X₁₃ X₁₄

Pour l'axe qui est la VILLE 1, le vendeur peut adopter le programme de vente minimum en commençant par la Bralima successivement aux points de ventes de l'athénée, cercle hippique, Belvédère, Rond point Major Vangu jusqu'à Panzi.

Ainsi, il aura évité le risque de gaspillage inutile enfin pour la bonne marche de l'entreprise.

II. L'axe 2 (VILLE 2)

a) Le graphe de l'axe 2 b) Construction de graphe ordonné

1) sommet 0 (N₀)

N₀ = {y₁}

2) sommet 1 (N₁)

N₁ = {y_2, y₃, y₄}

3) sommet 2 (N₂)

N₂ = {y_5, y₆}

4) sommet 3 (N₃)

N₃ = {y_6, y₇}

5) sommet 4 (N₄)

N₄ = {y_7, y₈}

6) sommet 4 (N₄)

N₄ = {y_7, y₈}

7) sommet 6 (N₆)

N₆ = {y_9, y₁₀}

8) sommet 7 (N₇)

N₇ = {y_10, y₁₁}

9) sommet 8 (N₈)

N₈ = {y_11, y₁₂}

10) sommet 9 (N₉)

N₉ = {y_11, y₁₂}

11) sommet 10 (N₁₀)

N₁₀ = {y_13, y₁₄}

12) sommet 11 (N₁₁)

N₁₁ = {y_14, y₁₅}

13) sommet 12 (N₁₂)

N₁₂ = {y_15, y₁₆}

14) sommet 13 (N₁₃)

N₁₃ = {y_16, y₁₇}

15) sommet 14 (N₁₄)

N₁₄ = {y_17, y₁₈}

16) sommet 15 (N₁₅)

N₁₅ = {y_18, y₁₉}

17) sommet 16 (N₁₆)

N₁₆ = {y_19, y₂₀}

18) sommet 17 (N₁₇)

N₁₇ = {y_20, y₂₁}

19) sommet 18 (N₁₈)

N₁₈ = {y₂₁}

P P(y) Procédure

Y₁

Y₂ Y₂, Y₃, Y₄

Y₃ Y₃, Y₄, Y₅

Y₄ Y₄, Y₅, Y₆

Y₅ Y₅, Y₆, Y₇

Y₆ Y₆, Y₇, Y₈

Y₇ Y₇, Y₈, Y₉

Y₈ Y₈, Y₉, Y₁₀

Y₉ Y₉, Y₁₀, Y₁₁

Y₁₀ Y₁₀, Y₁₁, Y₁₂

Y₁₁ Y₁₁, Y₁₂, Y₁₃

Y₁₂ Y₁₂, Y₁₃, Y₁₄

Y₁₃ Y₁₃, Y₁₄, Y₁₅

Y₁₄ Y₁₄, Y₁₅, Y₁₆

Y₁₅ Y₁₅, Y₁₆, Y₁₇

Y₁₆ Y₁₆, Y₁₇, Y₁₈

Y₁₇ Y₁₇, Y₁₈, Y₁₉

Y₁₈ Y₁₈, Y₁₉, Y₂₀

Y₁₉ Y₁₉, Y₂₀, Y₂₁

Y₂₀ Y₂₀, Y₂₁

Y₂₁ Y₂₁

Le graphe ordonné peut se schématiser comme suit :

Y₂ Y₅ Y₉ Y₁₃ Y₁₆ Y₁₉

Y₁ Y₃ Y₇ Y₁₁ Y₁₅ Y₁₇ Y₂₀

Y₄ Y₈ Y₁₄

Y₆ Y₁₀ Y₁₂ Y₁₈ Y₂₁ source : nos constructions

c) Résolution de problème

- Analyse

Soit le 14er sous-problème, le vendeur se trouve à 1h30' à la zone de Bagira et au Quartier B. de quartier B et de la zone de Bagira, il sera alors à l'un des points de vente ci-après : y₁₉, y₁₇, y₁₈. L'équation fonctionnelle de minimisation sera appliquée à chacun de ces points de vente : C₁₉,₁ , C₁₇,₁ , C₁₇,₁.

C(_19,1) = min [C(_nj + C(_{j, 1-1})] tel que j = 20,

= min [(C_nj + C(_{j, 0})] tel que j = 20

= min (60 + 0)

= 60m 0,6km

· Point de vente Y₁₇

C_17,1 = min (C_17,1 + C_{j, 0}) tel que j = 20, 21

= min (600 + 0, 620 + 0)

= min (600, 620)

= 600m 6km

· Point de vente Y₁₈

C_18,1 = min (C_18,1 + C_{j, 0}) tel que j = 21

= min (150+0)

= 150m 1,5km

2. Deuxième sous-problème

A ce niveau le vendeur de la Bralima sera à 3h°° de vente pendant la journée. Le vendeur peut attendre l'un des points suivants : y₁₆, y₁₇, y₁₄.

· Point de vente Y₁₆

C_16,2 = min (C_16,2 + C_{j, 2-1}) tel que j = 19, 20

= min (3500+600, 3508+0)

= min (3560,3508)

= 3508m 35,08km

· Point de vente Y₁₅

C_15,2 = min (C_15,2 + C_j,1) tel que j = 19, 18

= min (3900+60, 3890+150)

= min (39600, 4040)

= 3960m 39,6km

· Point de vente Y₁₄

C_14,2 = min (C_14,2 + C_j,1) tel que j = 17, 18

= min (800+600, 1300+150)

= min (1400, 1450)

= 1400m 14km

3. Troisième sous-problème

Le vendeur étant à 4h30', il peut atteindre l'un de ces points de vente : y₁₃, y₁₁, y₁₂.

· Point de vente Y₁₃

C_13,3 = min (C_13,3 + C_{j, 3-1}) tel que j = 16, 17

= min (C_13,3 + C_j,2) tel que j = 16, 17

= min (2200+3508, 1350+600)

= min (5708, 1950)

= 1950m 19,50km

· Point de vente Y₁₁

C_11,3 = min (C_13,2 + C_j,2) tel que j = 15, 14

= min (310 + 3960, 770+1400)

= min (4270, 2170)

= 2170m 21,7km

· Point de vente Y₁₂

C_12,3 = min (C_12,2 + C_j,2) tel que j = 16, 15

= min (1000+3508, 990+3960)

= min (4508, 4950)

= 4508m 45,08km

4. Quartier sous-problème

Il se trouve maintenant à 6h, il peut atteindre l'un de ces points de vente : y₉, y₈, y₁₀.

· Point de vente Y₉

C_9,4 = min (C_9,4 + C_{j, 4-1}) tel que j = 13, 12

= min (C_9,4 + C_j,3) tel que j = 13, 12

= min (400+1950, 300+4508)

= min (2350, 4808)

= 2350m 23,50km

· Point de vente Y₈

C_8,4 = min (C_8,4 + C_j,3) tel que j = 11, 12

= min (500+2170, 350+4508)

= min (2670, 4858)

= 2670m 26,7km

· Point de vente Y₁₀

C_10,4 = min (C_10,4 + C_j,3) tel que j = 13, 14

= min (350+1950, 275+1400)

= min (2300, 1675)

= 1675m 16,75km

5. Cinquième sous-problème

Il se trouve alors à 7h30', il pourra atteindre l'un de ces points suivants : y₅, y₇, y₆.

· Point de vente Y₅

C_5,5 = min (C_5,5 + C_{j, 5-1}) tel que j = 9, 8

= min (415+2350, 900+26700)

= min (2765, 3570)

= 2765m 27,65km

· Point de vente Y₇

C_7,5 = min (C_7,5 + C_j,4) tel que j = 11, 10

= min (2220+2170, 1440+1675)

= min (4390, 3115)

= 3115m 31,15km

· Point de vente Y₆

C_6,5 = min (C_6,5 + C_j,4) tel que j = 9, 10

= min (450+2350, 1512+1675)

= min (2800, 3187)

= 2800m 28km

13. Sixième sous-problème

A 9h°°, ilpourra atteindre l'un de ces points suivants : y₂, y₃, y₄.

· Point de vente Y₂

C_2,6 = min (C_2,6 + C_{j, 6-1}) tel que j = 5, 7

= min (200+275, 400+2800)

= min (2969, 3200)

= 2969m 29,69km

· Point de vente Y₃

C_3,6 = min (C_3,6 + C_j,5) tel que j = 7, 6

= min (365+3115, 200+2800)

= min (3480, 3000)

= 3000m 30km

· Point de vente Y₄

C_4,6 = min (C_4,6 + C_j,5) tel que j = 7, 8

= min (380+3115, 995+2670)

= min (3495, 3665)

= 3495m 34,95km

14. Septième sous-problème

A 10h°° et 30', il a un seul point, qui est le point de départ Y₁ (La Bralima), il peut atteindre l'un de ces points suivants :

y₂, y₃, y₄.

De la Bralima Y₁ :

C(_1,7) = min (C_1,7 + C_{j, 7-1}) tel que j = 2, 3, 4

= min (C_1,7 + C_j,6) tel que j = 2, 3, 4

= min (300+2969, 500+3000, 550+3495)

= min (3269, 3500, 4045)

= 3269m 32,69km

Au cours de cette allé, le vendeur de la Bralima pourra parcourir une distance minimum de 32, 69km. Le tableau de l'itinéraire relatif à ces différentes points de vente peut se présenter comme suit :

C₁₉, ₁= 0,6km C₁₁, ₃= 21,70km C₇, ₅= 31,15km

C₁₇, ₁= 6km C₁₂, ₃= 45,08km C₆, ₅= 28km

C₁₈, ₁= 1,5km C₉, ₄= 23,5km C₂, ₆= 29,69km

C₁₆, ₂= 35,08km C₈, ₄= 26,7km C₃, ₆= 30km

C₁₅, ₂= 39,6km C₁₀, ₄= 16,75km C₄, ₆= 34,95km

C₁₄, ₂= 14km C₅, ₅= 27,65km C₁= 32,69km

C₁₃, ₃= 19,50km

Le tableau de l'itinéraire est le suivant:

C₁₉, ₁= 0,6km

C₁₇, ₁= 6km

C₁₈, ₁= 1,5km

C₂₀, ₀= 0

C₂₁, ₀= 0

On place à gauche les distances à parcourir ci-dessous, d'autres distances au niveau du 6^e sous-problème.

C₂₀, ₀= 0

C₁₉, ₁= 0,6km

C₁₆, ₂= 35,08km

C₁₇, ₁= 6km

C₁₅, ₂= 39,6km

C₂₁, ₀= 0

C₁₈, ₁= 1,5km

C₁₄, ₂= 14km

Au niveau du 5^e sous-problème, on placera les 3 points de vente au coût optimale à gauche de 3 points de ventes situés à droite.

C₁₃, ₃= 19,50km

C₁₁, ₃= 21,70km

C₁₂, ₃= 45,08km

C₁₆, ₂= 35,08km

C₁₅, ₂= 39,6km

C₁₄, ₂= 14km

C₁₉, ₁= 0,6km

C₁₇, ₁= 6km

C₁₈, ₁= 1,5km

C₂₀, ₀= 0

C₂₁, ₀= 0

C₁₃, ₃= 19,50km

C₁₃, ₃= 19,50km

C₁₃, ₃= 19,50km

C₁₃, ₃= 19,50km

Le processus continue de la manière suivante :

C₉, ₄= 23,5km

C₈, ₄= 26,7km

C₁₀, ₄= 16,75km

C₁₃, ₃= 19,50km

C₁₁, ₃= 21,70km

C₁₂, ₃= 45,08km

C₁₆, ₂= 35,08km

C₁₅, ₂= 39,6km

C₁₄, ₂= 14km

C₁₉, ₁= 0,6km

C₁₇, ₁= 6km

C₁₈, ₁= 1,5km

C₂₁, ₀= 0

C₂₀, ₀= 0

Au niveau du 4^e sous-problème, on place toujours les 3 points de vente au coût optimal à gauche de 3 points de vente situés à droite.

C₅, ₅= 27,65km

C₇, ₅= 31,15km

C₆, ₅= 28km

C₉, ₄= 23,5km

C₈, ₄= 26,7km

C₁₀, ₄= 16,75km

C₁₃, ₃= 19,50km

C₁₁, ₃= 21,70km

C₁₂, ₃= 45,08km

C₁₆, ₂= 35,08km

C₁₅, ₂= 39,6km

C₁₄, ₂= 14km

C₁₇, ₁= 6km

C₁₉, ₁= 0,6km

C₁₈, ₁= 1,5km

C₂₀, ₀= 0

C₂₁, ₀= 0

On continue le processus :

C₂, ₆= 29,69km

C₃, ₆= 30km

C₄, ₆= 34,95km

C₅, ₅= 27,65km

C₇, ₅= 31,15km

C₆, ₅= 28km

C₉, ₄= 23,5km

C₈, ₄= 26,7km

C₁₀, ₄= 16,75km

C₁₂, ₃= 45,08km

C₁₁, ₃= 21,70km

C₁₃, ₃= 19,50km

C₁₆, ₂= 35,08km

C₁₅, ₂= 39,6km

C₁₄, ₂= 14km

C₁₈, ₁= 1,5km

C₁₇, ₁= 6km

C₁₉, ₁= 0,6km

C₂₀, ₀= 0

C₂₁, ₀= 0

On pourra compléter le coût minimal précédent :

C₂₁, ₀= 0

C₁₈, ₁= 1,5km

C₁₄, ₂= 14km

C₁₂, ₃= 45,08km

C₁₀, ₄= 16,75km

C₁₇, = 32,69km

C₄, ₆= 34,95km

C₆, ₅= 28km

C₁₇, ₁= 6km

C₁₅, ₂= 39,6km

C₁₁, ₃= 21,70km

C₈, ₄= 26,7km

C₇, ₅= 31,15km

C₃, ₆= 30km

C₁₉, ₁= 0,6km

C₁₆, ₂= 35,08km

C₂, ₆= 29,69km

C₅, ₅= 27,65km

C₉, ₄= 23,5km

C₁₃, ₃= 19,50km

C₂₁, ₀= 0

La route qui désigne les points de vente au coût minimal se fait ressortir facilement :

C_1,7 C_2,6 C_5,5 C_9,4 C_13,3 C₁₆,₂ C_19,2 C₂₀

Y₁ Y₂ Y₅ Y₉ Y₁₃ Y₁₆ Y₁₉ Y₂₀

Le programme de vente minimum à ce niveau commence à partir de point de départ en commençant par le Beach Muhanzi, Nyamugo deux poteaux, pas à pas, avenue Kasali, camp TV, quartier A et puis à la commune de Bagira.

A partir de cette analyse, nous pouvons conclure en disant que le manager de les Bralima n'ayant pas introduit les notions de programmation en subdivisant le circuit de distribution, cela nous a amené aux résultats biaisés. Par exemple, du au camp TV au quartier A à Bagira il n'y a aucune route qui relie ce tronçon, et puis si la route existait on n'aurait pas minimisé les coûts liés à cette affectation, car quitter Camp TV jusqu'à Bagira au Q/A il y a une longue distance. Cela va nous amener à aider la Bralima à faire une subdivision ordonnée de son circuit de distribution en tenant compte des notions de programmation dynamique.

Pour faciliter la distribution à la Bralima, il a été préférable de faire une étude approfondie sur la politique optimale capable de minimiser les coûts. C'est le point qui fera la troisième partie de notre chapitre.