Accueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > Le Simplex

Le Simplex

vendredi 24 juillet 2009, par frederic

Méthode graphique

Le problème :

Entreprise fabrique des voitures de type A et B. Il y a trois ateliers :
– Atelier 1 fabrique les moteurs.
– Atelier 2 fabrique les carrosseries.
– Atelier 3 effectue les assemblages.

Les capacités de travail des trois ateliers sont :
– 450 heures par mois pour l’atelier 1.
– 350 heures par mois pour l’atelier 2.
– 200 heures par mois pour l’atelier 3.

Bénéfices unitaires dégagés par l’entreprise sont: :
– 4000 francs pour les voitures de type A.
– 8000 francs pour les voitures de type B.

Le tableau ci-après indique les temps unitaires de chaque opération pour chaque type de voitures
Utilisation des ressources pour fabriquer les voitures

	Voiture type A	Voiture type B
Atelier Moteur	1	3
Atelier Carrosserie	2	1
Atelier assemblages	1	1

Question : Optimiser la production de façon à obtenir le bénéfice le
plus élevé possible

Mise en équation

Soit :
– x1 production mensuelle de voitures de type A.
– x2 production mensuelle de voitures de type B.

Programme linéaire décrivant le problème :
– les contraintes de disponibilité d’heures de travail de chaque atelier (contraintes explicites)
– la fonction économique z que l’on veut maximiser.

Exemple de l’atelier 1

il faut 1h par voiture A et 3h par voiture B : 1*x1+3*x2
maximum 450h
ce qui donne :

$1 \cdot x_{1} +3 \cdot x_{2} \le 450$
$x_{1}+3x_{2} \le 450$
$2x_{1} + x_{2} \le 350$
$x_{1} + x_{2} \le 200$
$x_{1} \Rightarrow 0, x_{2} \Rightarrow 0$

Pour maximiser le bénéfice

$Max(z)=4000x_{1}+8000x_{2}$

Principe
problème peut être étudié dans R2 :
2 variables x1, x2
Point M du plan : production qcq réalisable ou non.
Réalisable si : intérieur au polygone des contraintes

$x_{1}+3x_{2} \le 450$
$2x_{1} + x_{2} \le 350$
$x_{1} + x_{2} \le 200$
$x_{1} \Rightarrow 0, x_{2} \Rightarrow 0$

sur ce graph :
– x1 en abscisse
– x2 en ordonnée

On trace les équations :
2x1+x2<350, cette équation est modifié en remplaçant le signe < par =. Il suffira de prendre toutes les valeurs en dessous de la droite

Pour tracer on met x1=0 et on calcul x2 et inversement. Cela nous donne 2 points qui suffit pour tracer une droite.
On raie les points au dessus de cette droite car ils ne satisfont pas ma première contrainte. Pour rayer les points, on hachure
on fait pareil pour les trois inéquations, donc pour les trois contraintes
maintenant, ce qui reste en non hachuré, ce sont tous les points solutions
cet ensemble de points représente une figure géométrique qui est un polyedre ici 0, A, B, C, D
Tous les points dans la zone blanche (y compris sur les traits) sont solutions
Calcul du bénef max :
– le bénéfice vaut z = 4000 x1 + 8000 x2 on divise par 4000 pour simplifier.
– le bénéfice vaut z (z’) = x1 + 2 x2

Cette droite passe par 0, en effet si je produit 0 voiture A et 0 voiture B, le bénéfice sera de 0,
on fixe 2 variables x1=0, x2=0 => calcul de z qui est égale à 0.
Pour tracer cette droite, il nous faut un autre point avec z toujours=0.
Exemple : x1=200
0=200+2x2, => x2=-100
Ensuite, on cherche une droite parallèle a cette droite initiale qui soit la plus haute possible. Il suffit de monter pour être parallèle à cette droite et cela tant que vous restez dans le polyedre et le dernier point est le point B(75 ;125) qui est la meilleur solution.
On produira 75 voiture A et 125 voiture B, le bénéfice est de

Méthode des tableaux

Étape 1

On reprend les équations de départ :

$x_{1}+3x_{2} \le 450$
$2x_{1} + x_{2} \le 350$
$x_{1} + x_{2} \le 200$
$Max(z)=4000x_{1}+8000x_{2}$
$x_{1} \Rightarrow 0, x_{2} \Rightarrow 0$

Étape 2

Pour ne pas avoir d’inéquation on pose :
– $x_{1}+3x_{2}+x_{3}=450$ avec $x_{3}$ >0 c’est identique à $x_{1}+3x_{2} \le 450$
– x3 représente ici le temps disponible pour l’atelier moteur

Ce qui nous donne pour toutes les équations :

$x_{1}+3x_{2} +x_{3}= 450$
$2x_{1} + x_{2} +x_{4}=350$
$x_{1} + x_{2} +x_{5}= 200$
$Max(z)=x_{1}+2x_{2}$

Sous la forme matriciel

$\left[ \begin{array}{rrrrr} 1 & 3 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{array} \right] \cdot \left[ \begin{array}{r} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array} \right] = \left[ \begin{array}{r} 450 \\ 350 \\ 200 \end{array} \right]$

$Max (z)= \left[ \begin{array}{rrrrrr} 1 & 2 & 1 & 0 & 0 & 0 \end{array} \right] \cdot \left[ \begin{array}{r} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array} \right]$

Étape 2

Au départ on initialise avec un bénéfice de 0 donc z=0
Déroulement de l’algorithme
On regarde la plus grande valeur dans la ligne delta j (∆j) donc tout en bas. Ici c’est 2.
La colonne 2 vas entrer en base.

Chercher la ligne du pivot
Pour cela, on divise chaque Bi par la valeur de la ligne pivot, ici la colonne 2 (qu’on vient de choisir)

${450} \over {3}$ ,
${350} \over {1}$ ,
${200} \over {1}$

On retient le plus petit ici 150, la ligne 1.

Le pivot est la colonne 2 ligne 1.
Pour la suite on écrit i=2 à gauche, là ou on avait i=3.

La colonne 2 sort, donc elle passe en ligne à la place de la ligne que l’on traite.
Pour la ligne du pivot, on divise la ligne par la valeur du pivot :
Nouvelle valeur= ancienne valeur / Valeur du pivot

La ligne du pivot : 1,3,1,0,0,0,450
Le pivot 3 (colonne 2)
Ce qui donne 1/3 ;1 ;1/3 ;0 ;0 ;150

L1 (origine)	1	3	1	0	0	450
L1 (calcul)	1/3	3/3	1/3	0/3	0/3	450/3
L1 (résultat)	1/3	1	1/3	0	0	150

Pour les lignes suivantes :
nouvelle valeur = ancienne valeur moins 1/3 de la ligne 1
nouvelle valeur = ancienne valeur - α * par l’ancienne valeur de la ligne pivot
Le coefficient alpha se calcule sur la colonne du pivot :
α = ancienne ligne / ancienne ligne du pivot

La deuxième ligne :
α = 1/3

L2 (origine)	2	1	0	1	0	350
L2 (calcul)	2 -1/3*1	1 -1/3*3	0 - 1/3*1	1 -1/3*0	0 -1/3*0	350-1/3*450
L2 (résultat)	5/3	0	-1/3	1	0	200

La troisième ligne
α = 1/3

L3 (origine)	1	1	0	0	1	200
L3 (calcul)	1 –1* (1/3)	1 – 1*1	0 – 1*(1/3)	0 – 1/3*0	1 – 1/3*0	200 – 1/3*450
L3 (résultat)	2/3	0	-1/3	0	1	50

Les deltat (r)
α = 2/3

rj (origine)	1	2	0	0	0	0
rj (calcul)	1 – 2/3*1	2 – 2/3*0	0 – (2/3)*1	0 – 2/3*0	0 – 2/3*1	0 – 2/3*450
rj (résultat)	1/3	0	-2/3	0	0	300

ce qui nous donne :

	j=1	j=2	j=3	j=4	j=5	Bi
i=2	1/3	1	1/3	0	0	150
i=4	5/3	0	-1/3	1	0	200
i=5	2/3	0	-1/3	0	1	50

$\Delta$ j	1/3	0	-2/3	0	0	-300
						z=-300

On recommence l’algorithme

La plus grande valeur dans les delta est la colonne 1 de valeur 1/3.

On recalcule les $\Delta$

${150} \over {{1} \over {3}}$ ,
${200} \over {{5} \over {3}}$ ,
${200} \over {{2} \over {3}}$

Le plus petit 75

Notre pivot est la ligne 3 colonne 1 : (2/3).
Pour la suite on écrit i=1 à gauche, là ou on avait i=5

La ligne Pivot (Ligne 3)

On divise la ligne 3 par le pivot soit 2/3 :
Ligne de pivot : 2/3 ;0 ;-1/3 ;0 ;1 ;50
Le pivot 2/3
ce qui donne : 1 ; 0 ; -0.5 ; 0 ; 1.5 ; 75

L3 (origine)	2/3	0	-1/3	0	1	50
L3 (calcul)	(2/3)/(2/3)	0/(2/3)	(-1/3)/(2/3)	0/(2/3)	1/(2/3)	50/(2/3)
L3 (résultat)	1	0	-1/2	0	3/2	75

Calcul de la ligne 1
α = (1/3)/(2/3)=1/2

L1 (origine)	1/3	1	1/3	0	0	150
L1 (calcul)	1/3-(1/2)*(2/3)	1-(1/2)*0	1/3-(1/2)*0	0-(1/2)*0	0-(1/2)*0	150-(1/2)*50
L1 (résultat)	0	1	1/2	0	-1/2	125

Calcul de la ligne 2
α = (5/3)/(2/3)=5/2

L1 (origine)	5/3	0	-1/3	1	0	200
L1 (calcul)	5/3-(5/3)*(2/3)	0-(5/2)*0	-1/3-(5/2)*(1/3)	1-(5/2)*0	0-(5/2)*1	200-(5/2)*50
L1 (résultat)	0	0	1/2	1	-5/2	75

Les $\Delta$
α = (1/3)/(2/3)=(1/2)

$\Delta$ j (origine)	1/3	0	-2/3	0	0	-300
$\Delta$ j (calcul)	1/3-(1/3)*(2/3)	0-(1/2)*0	-2/3-(1/2)*(-1/3)	0-(1/2)*1	0-(1/2)*1	-300-(1/2)*50
$\Delta$ j (résultat)	0	0	-1/2	0	-1/2	-325

Tous les deltas sont négatifs ou nuls, donc l’algorithme s’arrête.

x1=75, x2=125,x3=0, x4=75, x5=0, z=325
Les ateliers 1 et 2 sont utilisés au maximum, l’atelier 3 dispose d’une réserve de 75

On peut finir en reprenant les équations de départ et surtout le bénéfice max :

$x_{1}+3x_{2} \le 450$ (atelier 1)
$2x_{1} + x_{2} \le 350$ (atelier 2)
$x_{1} + x_{2} \le 200$ (atelier 3)
$Max(z)=4000x_{1}+8000x_{2}$
$x_{1} \ge 0, x_{2} \ge 0$

$x_{1}=75` x_{2}=125$
$75+3 \cdot 125 = 450$ (atelier 1, au max)
$2 \cdot 75 + 125 = 275$ (atelier 2, pas au max)
(atelier 3, au max)
$1300000 = 4000 \cdot 75 + 8000 \cdot 125$