Transcript
Programmation Linéaire
Combien d'hectares l'exploitation doit-elle consacrer à chacune des cultures pour maximiser son bénéfice?
On peut mettre en évidence les données de l'énoncé par un tableau:
P1
P2
P3
P4
P5
Stocks
e1
1
1
0
2
0
8
e2
1
0
2
0
0
4
e3
0
2
0
0
1
9
Bénéfices
3
4
1
7
2
On utilise les variables x1, x2, x3, x4, x5 pour représenter la superficie en hectares de la culture des céréales P1, P2, P3, P4, P5, avec la condition que xi 0. Et z représente le bénéfice moyen net total.
On en déduit le système d'équations suivant (forme canonique):
9144002730500
x1 + x2 + 2x4 8
x1 + 2x3 4 avec xi 0
2x2 + x5 9
x1 + x2 + x3 + x4 + x5 16
max z = 3x1 + 4x2 + x3 + 7x4 + 2x5
On introduit les variables d'écart t1 à t4 afin de le mettre sous forme standard:
9144002730500x1 + x2 + 2x4 + t1 = 8
x1 + 2x3 + t2 = 4 avec xi , ti 0
2x2 + x5 + t3 = 9
x1 + x2 + x3 + x4 + x5 + t4 = 16
max z = 3x1 + 4x2 + x3 + 7x4 + 2x5
t1 représente la quantité d'engrais e1 restante
t2 représente la quantité d'engrais e2 restante
t3 représente la quantité d'engrais e3 restante
t4 représente le nombre d'hectare non cultivé
On utilise la méthode des tableaux afin de trouver la solution optimale
285750014033500coef
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
16
1
1
1
1
1
0
0
0
1
16
t4
914400107315004
1
1
0
2
0
1
0
0
0
8
t1
/
1
0
2
0
0
0
1
0
0
4
t2
/
0
2
0
0
1
0
0
1
0
9
t3
3
4
1
7
2
0
0
0
0
Z
400050012001500Solution de base admissible: x1 = x2 = x3 = x4 = x5 = Z = 0 t1 = 8
t2 = 4
t3 = 9
t4 = 16
Etant donné que l'on a encore des coefficients positifs apparaissant dans la fonction économique, ce n'est pas la solution optimale. On fait donc rentrer x4 en base et sortir t1 de la base…
297180016764000coef
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
12
½
½
1
0
1
-½
0
0
1
12
t4
/
½
½
0
1
0
½
0
0
0
4
x4
/
1
0
2
0
0
0
1
0
0
4
t2
914400127000009
0
2
0
0
1
0
0
1
0
9
t3
-½
½
1
0
2
-7/2
0
0
0
Z-28
Ce n'est pas encore la solution optimale, on fait rentrer x5 en base et sortir t3 de la base…
coef
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
20574003810003
½
-3/2
1
0
0
-½
0
-1
1
3
t4
/
½
½
0
1
0
½
0
0
0
4
x4
91440091440002
1
0
2
0
0
0
1
0
0
4
t2
/
0
2
0
0
1
0
0
1
0
9
x5
-½
-7/2
1
0
0
-7/2
0
-2
0
Z-46
Ce n'est pas encore la solution optimale, on fait rentrer x3 en base et sortir t2 de la base…
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
0
-3/2
0
0
0
-½
-½
-1
1
1
t4
½
½
0
1
0
½
0
0
0
4
x4
½
0
1
0
0
0
½
0
0
2
x3
0
2
0
0
1
0
0
1
0
9
x5
-1
-7/2
0
0
0
-7/2
-½
-2
0
Z-48
Aucun coefficient positif n'apparaissant plus dans la fonction économique, nous avons ici la solution optimale:
Z=48 pour t4 = 1, x4 = 4, x3 = 2, x5 = 9, avec x1 = x2 = t1 = t2 = t3 = 0
Le bénéfice sera donc d'un maximum de 48 si l'agriculteur cultive 4ha de P4 , 2ha de P3 , 9ha de P5 , et laisse un hectare non cultivé (car il aura utilisé tous ses stocks d'engrais).
Pour quelles valeurs minimales des subsides l'exploitation peut-elle promettre à la coopérative que:
Pour paramétrer suivant les primes accordées à la culture des céréales P1et P2, ajoutons dans la matrice optimale aux coefficients de x1 et x2 de la fonction économique 3 et 5 (d'après la méthode utilisée dans l'exemple de Faure: Guide de la R.O. T.2 les applications).
Ce qui donne le tableau suivant:
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
0
-3/2
0
0
0
-½
-½
-1
1
1
t4
½
½
0
1
0
½
0
0
0
4
x4
½
0
1
0
0
0
½
0
0
2
x3
0
2
0
0
1
0
0
1
0
9
x5
3 -1
5 -7/2
0
0
0
-7/2
-½
-2
0
Z-48
La solution avant paramétrage était Z=48 pour t4=1, x4=4, x3=2, x5=9, avec x1=x2=t1=t2=t3=0. Cette solution n'est optimale que si tous les coefficients de la fonction économique sont négatifs. Cherchons les cas où des coefficients sont positifs:
Soit 1 = 3 -1 > 0 > 1/3
Soit 2 = 5 -7/2> 0 > 7/10
Bilan:
1/3
7/10
1
-
+
+
2
-
-
+
L'une au moins de ces 2 céréales sera cultivées?
Etant donné que l'on recherche la valeur minimale du subside pour lequel au moins une des deux céréales sera cultivée, cela induit qu'au moins un des coefficients de la fonction économique sur x1 ou x2 doit être positif. On se place donc dans le cas où ] 1/3 , 7/10 ]
Afin de faciliter les calculs, on introduit la variable 1 (proche de zéro) telle que:
= 1/3 + 1 > 1/3 (avec 1 > 0 )
102870013652500coef
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
/
0
-3/2
0
0
0
-½
-½
-1
1
1
t4
8
½
½
0
1
0
½
0
0
0
4
x4
91440042545004
½
0
1
0
0
0
½
0
0
2
x3
/
0
2
0
0
1
0
0
1
0
9
x5
31
51 -11/6
0
0
0
-7/2
-½
-2
0
Z-48
31 est le plus grand coefficient positif de la fonction économique, donc on fait rentrer x1 dans la base et sortir x3.
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
0
-3/2
0
0
0
-½
-½
-1
1
1
t4
0
½
-1
1
0
½
-½
0
0
2
x4
1
0
2
0
0
0
1
0
0
4
x1
0
2
0
0
1
0
0
1
0
9
x5
0
51 -11/6
-61
0
0
-7/2
-½ -31
-2
0
Z-48-121
Aucun coefficient positif n'apparaissant plus dans la fonction économique (puisque 1 est proche de zéro, on a forcement 1 11/30), nous avons donc ici la solution optimale:
Z = 48+121 soit Z = 44 + 12
pour t4 = 1, x4 = 2, x1 = 4, x5 = 9, avec x3 = x2 = t1 = t2 = t3 = 0
Le bénéfice sera donc fonction du subside donné par la coopérative si l'agriculteur cultive 4ha de P1 , 2ha de P4 , 9ha de P5 , et laisse un hectare non cultivé (car il aura utilisé tous ses stocks d'engrais).
Comme on l'a vu plus haut, la culture d'au moins une des deux céréales présentera un intérêt économique si le subside est supérieur à un tiers ( >1/3).
Ces deux céréales seront cultivées?
Etant donné que l'on recherche la valeur minimale du subside pour lequel les deux céréales seront cultivées, et d'après le bilan réalisé précédemment, on se place dans le cas où > 7/10.
Afin de faciliter les calculs, on introduit la variable 2 (proche de zéro) telle que:
= 7/10 + 2 > 7/10 (avec 2 > 0 )
125730015049500coef
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
/
0
-3/2
0
0
0
-½
-½
-1
1
1
t4
8
½
½
0
1
0
½
0
0
0
4
x4
914400114935004
½
0
1
0
0
0
½
0
0
2
x3
/
0
2
0
0
1
0
0
1
0
9
x5
11/10+32
52
0
0
0
-7/2
-½
-2
0
Z-48
11/10 + 32 est le plus grand coefficient positif de la fonction économique, donc on fait rentrer x1 dans la base et sortir x3.
125730015049500coef
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
-2/3
0
-3/2
0
0
0
-½
-½
-1
1
1
t4
800100117475004
0
½
-1
1
0
½
-½
0
0
2
x4
/
1
0
2
0
0
0
1
0
0
4
x1
9/2
0
2
0
0
1
0
0
1
0
9
x5
0
52
-11/5 -62
0
0
-7/2
-8/5 -32
-2
0
Z-262/5-122
52 est le plus grand coefficient positif de la fonction économique, donc on fait rentrer x2 dans la base et sortir x4.
x1
x2
x3
x4
x5
t1
t2
t3
t4
bi
définit
0
0
-3
3
0
1
-2
-1
1
7
t4
0
1
-2
2
0
1
-1
0
0
4
x2
1
0
2
0
0
0
1
0
0
4
x1
0
0
4
-4
1
0
-2
1
0
1
x5
0
0
-11/5 +42
-102
0
-7/2-52
-8/5 +22
-2
0
Z-262/5-322
Aucun coefficient positif n'apparaissant plus dans la fonction économique (puisque 2 est proche de zéro), nous avons donc ici la solution optimale:
Z = 262/5+322 soit Z = 30 + 32
pour t4 = 7, x1 = 4, x2 = 4, x5 = 1, avec x3 = x4 = t1 = t2 = t3 = 0
Le bénéfice sera donc fonction du subside donné par la coopérative si l'agriculteur cultive 4ha de P1 , 4ha de P2 , 1ha de P5 , et laisse 7ha non cultivé (car il aura utilisé tous ses stocks d'engrais).
Comme on l'a vu plus haut, la valeur minimale du subside pour lequel les deux céréales seront cultivées, est > 7/10.
