III.2.5.4. RECHERCHE DE SOLUTION D'UN PROGRAMME
LINEAIRE
Un programme linéaire peut - être résolu
en utilisant l'une de quatre méthodes ci - dessous :
- La méthode graphique ;
- L'algorithme de dénombrement ;
- La méthode algébrique ;
- La méthode d'algorithme du simplexe.
III.2.5.4.1. La Méthode de graphique
Dans cette méthode, seules les variables
d'activité ou variables réelles (appelées encore variables
principales) sont utilisées. On se borne simplement à :
- Représenter graphiquement les droites limites ;
- Délimiter le domaine d'acceptabilité enfin ;
- Remplacer successivement les coordonnées de chaque
sommet du polygone dans la fonction économique afin d'obtenir la
combinaison optimale cherchée (minimum ou maximum).
En général, pour chercher le minimum, on optera
le point le plus voisin de l'origine et pour le maximum, on choisira le point
le plus éloigné.
III.2.5.4.2. L'Algorithme de
Dénombrement
Cette méthode consiste à dénombrer toutes
les solutions de base, à déterminer celles qui sont
réalisables ou admissibles et à calculer la valeur de la fonction
économique en chacune de ces bases.
La solution de base fournissant la plus petite ou la plus
grande valeur à la fonction économique selon qu'il s'agisse d'un
problème à minimum ou à maximiser sera la solution
optimale de programme.
84
III.2.5.4.3. La Méthode
Algébrique
Au moment où la forme canonique est plus pratique dans
le cas de résolution graphique d'un programme linéaire, la forme
standard est la mieux appropriée dans la méthode
algébrique et l'algorithme du simplexe.
Rappelons qu'on passe à la forme standard en
introduisant des variables d'écarts et/ou des variables artificielles.
Les variables d'écarts Interviennent dans certaines
inégalités tournées dans le sens « inférieur
ou égal à ». les variables artificielles n'interviennent qua
dans les contraintes égalités et inégalités
tournées dans le sens « supérieur ou égal ».
III.2.5.3.1. Principe Généraux de la
Méthode (Problème à Maximum)
Cette méthode consiste à :
- Dresser la forme canonique du problème posé
;
- Passer de la forme canonique à la forme standard ;
- Trouver une première solution de base admissible en
utilisant d'abord les variables réelles comme variables hors base
(variables nulles). A ce stade, la fonction économique est nulle ;
- Faire subir un test d'optimalité à cette
solution de base pour déterminer s'il s'agit ou non de la solution
optimale. S'il s'agit de la solution optimale, le problème est
terminé. Sinon, il passer à l'étape suivante ;
- Passer à la première itération afin de
trouver une solution de base meilleure, c'est - à - dire,
améliorer la fonction économique ; pour parvenir, on
sélectionne une variable entrante et une variable sortante. Est variable
entrante, toute celle qui, dans la fonction économique, présente
le coefficient positif le plus élevé. Et la variable sortante est
celle qui correspond au plus petit rapport positif des rapports des seconds
membres des contraintes aux coefficients de la variable entrante (l'infini et
les membres négatifs étant exclus) ;
85
- On arrête les différentes itérations
dès que la fonction économique en contient que des coefficients
négatifs ou nuls.
Par ailleurs, il sied de signaler que le processus est le
même pour minimiser une fonction linéaire. Mais la
différence se constate dans le sens où le problème
à minimiser consiste à faire rentrer dans la base la variable,
hors base dont le coefficient est le plus négatif dans la fonction
économique. Le minimum sera atteint lorsque tous les coefficients de
cette fonction seront positifs.
III.2.5.4.4. Algorithme du Simplexe
Le nom de cet algorithme est dû au fait que l'une des
premières applications en a été faite à un
problème dans lequel l'ensemble des programmes était
représenté par un simplexe. Cette méthode repose sur le
théorème fondamental suivant :
- Si un programme linéaire admet une solution possible
finie alors il admet au moins une solution de base ;
- Si ce programme linéaire admet une solution optimale,
il admet au moins une solution optimale (ce qui signifie qu'une solution de
base au moins est solution optimale).
III.2.5.4.4.1. PRINCIPES D'ALGORITHME DU
SIMPLEXE
Les principes de l'algorithme du simplexe sont identiques
à ceux de la méthode algébrique, à savoir :
- Formuler le problème sous forme canonique ;
- Passer de la forme canonique à la forme standard en
introduisant des variables d'écarts et/ou des variables artificielles
selon les cas ;
- Trouver une première solution de base qui soit
admissible en utilisant d'abord les variables réelles comme des
variables hors base, les autres variables non nulle (variables de base)
constituant alors solution dans cette première opération ;
86
- Faire le test d'optimalité, c'est - à - dire,
s'assurer si cette première solution de base constitue la solution
optimale de programme. Dans la négativité, on trouve une autre
solution de base en échangeant le rôle d'une variable de base (que
l'on tire dans la base) et d'une variable hors base (que l'on introduit dans la
base) de manière à améliorer la valeur prise par la
fonction économique.
III.2.5.4.4.2. CRITERE D'ENTREE
Est variable entrante toute celle dont le coefficient Dj est le
plus grand positif (pour un problème à
maximiser) ou le plus négatif (pour un problème
à minimiser).
III.2.5.4.4.3. CRITERE DE SORTIE
Est variable sortante celle qui correspond au petit rapport
positif des seconds membres aux coefficients de la variable entrante (l'infini
et les membres négatifs étant exclus).
L'optimum est atteint lorsqu'on ne peut plus améliorer
la fonction économique, c'est - à - dire lorsque la fonction
économique qui ne contient plus que des coefficients Dj négatifs
ou nuls (pour un problème à maximiser) ou des coefficients Dj
positifs (pour un problème à minimiser).
III.2.5.4.4.4. TECHNIQUES DE RESOLUTION
1). Classons dans un tableau à m lignes et (n+m+1)
colonnes les coefficients du système d'équations linéaires
;
2). Repérons chaque colonne à l'aide de la
variable qui lui correspond, la dernière colonne à droite
étant celle relative au terme constant V0i = bi ;
3). Ajoutons deux colonnes à gauche, l'une
repérée « i » comprendra les indices relatifs aux
variables situées dans la base ; les indices des variables hors base
seront repérées par l'indice « j » dans l'autre
colonne, repérée Ci, seront inscrits les profits marginaux des
variables dans la base à cette étape ;
87
4). Sur une ligne située en dessous du tableau,
portons les coefficients Cn de la fonction économique, puis une seconde
ligne les variables Xi = bi de la solution. On a alors la valeur de Z à
cette étape ;
5). Calculer ensuite les profits marginaux Dj permettant de
déterminer la variable Xe à faire entrer dans la base
et les rapports Voi/aie ; aie étant les coefficients situés sur
la ligne « i » et dans la colonne « Xe » ces valeurs
permettent de choisir la variable Xs sortante de la base ;
Toutefois, il est important de rappeler que dans toute
stratégie commerciale, le pivot demeure toujours le (s) produit (s) qui
est (sont) fabriqué (s) à partir d'une ou plusieurs
matières premières traitées de façon à lui
conférer des caractéristiques de qualité correspondant
à une norme fixée préalablement. D'où, toute
disposition utile doit être prise en vue d'obtenir la qualité et
la quantité du produit voulu.
Sans doute, il convient de dire que pour produire de l'eau
potable, il nous importe de comprendre les mécanismes que la
REGIDESO/Kindu utilise afin d'atteindre cet objectif. Ainsi, pour obtenir l'eau
potable, la REGIDESO/Kindu combine quatre types des matières
premières (eau brute du fleuve Congo, le sulfate d'aluminium, le chlore
et le chaud) moyennant quatre étapes indispensables notamment :
- Le captage d'eau brute du fleuve Congo ;
- La décantation ;
- La filtration et enfin ;
- Les neutralisations.
1. CAPTAGE
C'est une opération qui consiste à aspirer l'eau
brute du fleuve Congo.
Elle
se réalise grâce à deux motopompes,
immergée dans deux puisards de six mètres de
profondeur chacun, placés au bord du fleuve et ayant
chacune un débit de 200 m3/h.
88
Une cabine de commande avec deux maitres assurent le
fonctionnement de ces deux motopompes travaillant alternativement.
2. LA DECANTATION OU LA SEPARATION
Une conduite qui amène l'eau dans le décanteur
où elle est soumise à la décantation et reçoit les
premiers produits chimiques qui est le sulfate d'aluminium et reçoit
également une partie de lait de chaux. L'eau coagulée entre deux
décanteurs en passant par les chaines dont chacun a une capacité
ou un volume de 150 m3. L'eau décantée gravite
à la bâche tampon de 24m3 qui est une
récupération d'eau de surface.
3.
La FILTRATION
Dans cette étape, on récupère l'eau de la
bâche en passant par les pompes de transfert qui transfèrent les
eaux de la bâche tampon pour les envoyer aux filtres. Ces pompes sont au
nombre de quatre avec un débit de 40m3
4. LA NEUTRALITE
L'eau filtrée doit être purifiée en
injectant la chlore pour désinfecter, pour que cette eau soit potable,
puis elle passe par les réservoirs de stockage d'eau traitée. Ces
réservoirs ont une capacité de 100 m3 chacun.
A la lumière de ce qui précède, il
convient d'affirmer que la REGIDESO/Kindu produit hebdomadairement deux types
de bien ; l'eau potable (X1) et le service de raccordement (X2). La production
d'eau potable nécessite 24 heures pour le captage, 33 heures pour la
décantation, 31 heures pour la filtration et 12 heures pour la
neutralisation est le service de raccordement exige 32 heures pour creuser, 22
heures pour déposer les tuyaux, 28 heures pour le raccordement et 20
heures pour l'installation des compteurs. L'entreprise ne peut disposer chaque
semaine que de 96 heures pour le captage et le creusage, 120 heures pour la
décantation et le dépôt des tuyaux, 123 heures pour la
filtration et le raccordement et en fin 168 heures pour la neutralisation et
l'installation des compteurs. Si la marge bénéficiaire est de
224250 CDF par 1000m3 d'eau potable produite et de 200.000FC par
nouvel abonné, cherchons à trouver une combinaison des produits
qui maximise le profit hebdomadaire de la REGIDESO/Kindu.
89
PROGRAMME DE PRODUCTION
|
|
|
FORME CANONIQUE
|
|
FORME STANDARD
|
Max P = 224250 X1 + 200.000X2
|
Max P = 224250 X1 + 200.000X2
|
+0X3+0X4+0X5+0X6
|
S/C 24X1 + 32 X2 S 96
|
24X1
|
+ 32X2 +
|
X3
|
=
|
96
|
33X1 + 22X2 S 120
|
33X1
|
+ 22X2
|
+ X4
|
=
|
120
|
31X1 + 28X2 S 132
|
31X1
|
+ 28 X2
|
+ X5
|
=
|
132
|
12X1 + 20 X2 S 168
|
12X1
|
+ 20X2
|
+ X6 = 168
|
Xj = 0 ; (j = 1,2)
|
Xj = 0 ; (j = (1,2,
|
3,4, 5, 6)
|
|
|
SOURCE : Nos ajustements à partir des
informations reçues à la section production
Pour trouver une combinaison des produits qui maximise le
profit (P), nous allons faire recours à une méthode
citées, dans les lignes précédentes. C'est ainsi que, pour
le cas présent, nous faisons recours à la méthode
d'algorithme de dénombrement. Connaissant le nombre des variables dans
la base (m=2) et le nombre total des variations (n= 6), cherchons maintenant
à trouver une combinaison de six éléments pris deux
à deux entre eux ; on aura :
Tableau °6. Tableau Combinatoire de la Production
d'eau potable en milliers de m3 et des Abonnés
N°
|
Solution de Base
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
A ou NA
|
?
|
1
|
A
|
0
|
0
|
96
|
120
|
132
|
168
|
A
|
0
|
2
|
B
|
0
|
3
|
0
|
54
|
48
|
108
|
A
|
60000
|
3
|
-
|
0
|
5,45
|
-78,4
|
0
|
-20,6
|
59
|
NA
|
-
|
4
|
-
|
0
|
4,71
|
-54,72
|
16,38
|
0
|
73,8
|
NA
|
-
|
5
|
-
|
0
|
8,4
|
-172,8
|
-64,8
|
-103,2
|
0
|
NA
|
-
|
6
|
-
|
4
|
0
|
0
|
-12
|
8
|
120
|
NA
|
-
|
7
|
C
|
3,64
|
0
|
8,64
|
0
|
19,16
|
124,32
|
A
|
816270
|
8
|
-
|
4,26
|
0
|
-6,24
|
-20,58
|
0
|
116,88
|
NA
|
-
|
9
|
-
|
14
|
0
|
-240
|
-342
|
-302
|
0
|
NA
|
-
|
90
10
|
D
|
3,27
|
0,54
|
0
|
0
|
15,51
|
117,96
|
NA
|
-
|
11
|
-
|
4,8
|
-0,6
|
0
|
-25,2
|
0
|
122,4
|
NA
|
-
|
12
|
-
|
-36
|
30
|
0
|
648
|
408
|
0
|
NA
|
-
|
13
|
-
|
1,88
|
2,63
|
-33,28
|
0
|
0
|
92,84
|
NA
|
-
|
14
|
-
|
-3,27
|
10, 34
|
-156,4
|
0
|
-56,15
|
0
|
NA
|
-
|
15
|
-
|
-7,27
|
12,77
|
-138,16
|
78,97
|
0
|
0
|
NA
|
-
|
Source : nos ajustements à partir des
données de la section production/Régideso-Kindu Après
analyse du tableau ci - haut, sur base de 15 solutions possibles ou 15
combinaisons de X1 et X2, nous constatons que la solution D
permet à la REGIDESO/Kindu de produire 3270m3 ou 327000
litres d'eau potable et d'ajouter ou de récolter au moins un
abonné par semaine afin de maximiser son profit hebdomadaire d'un
montant de 841297,5 CDF
91
|