Optimisation lineaire td 5 probleme du jardinier -Programmat

Télécharger PDF

Optimisation Linéaire, TD n° 5

Problème du jardinier

On cherche à minimiser la fonction objectif :

Z min = 3x1 + 2x2

Sous les contraintes :

5x1 + x2 ≥ 10
2x1 + 2x2 ≥ 12
x1 + 4x2 = 12

Avec : x1, x2 ≥ 0

1) Méthode Géométrique

Pour résoudre graphiquement, nous traçons les droites correspondant aux égalités des contraintes :

(D1) 5x1 + x2 = 10
(D2) 2x1 + 2x2 = 12 (simplifié en x1 + x2 = 6)
(D3) x1 + 4x2 = 12

Le minimum de la fonction objectif est atteint à un sommet de la région admissible.

Le point optimal est atteint à l'intersection de (D1) et (D2) :

De (D1) : x2 = 10 - 5x1
De (D2) : x2 = 6 - x1

En égalisant les deux expressions pour x2 :
10 - 5x1 = 6 - x1
4x1 = 4
x1 = 1

En substituant x1 dans l'équation de (D2) :
x2 = 6 - 1 = 5

Ainsi, le point optimal est (x1, x2) = (1, 5).

Le coût minimum est alors :
Z = 3(1) + 2(5) = 3 + 10 = 13

2) Méthode du Simplexe

Forme standard

Pour appliquer la méthode du Simplexe, nous introduisons des variables d'écart (slack/excédent) pour convertir les inégalités en égalités. Pour les contraintes "supérieur ou égal", des variables d'excédent sont soustraites, et des variables artificielles seront nécessaires pour la base initiale.

5x1 + x2 - x3 = 10 (avec x3 ≥ 0, variable d'excédent)
2x1 + 2x2 - x4 = 12 (avec x4 ≥ 0, variable d'excédent)
x1 + 4x2 = 12

La fonction objectif reste : Z = min (3x1 + 2x2)

Base non réalisable et variables artificielles

La base formée par les variables d'excédent (x3, x4) et l'absence d'une variable de base évidente pour la troisième contrainte (x1 + 4x2 = 12) rend la base initiale non réalisable. Nous introduisons des variables artificielles (a1, a2, a3) pour former une base réalisable initiale :

5x1 + x2 - x3 + a1 = 10
2x1 + 2x2 - x4 + a2 = 12
x1 + 4x2 + a3 = 12

Toutes les variables : x1, x2, x3, x4, a1, a2, a3 ≥ 0

Nouvelle forme standard avec pénalités M

La méthode du Grand M est utilisée. Pour une minimisation, un grand nombre positif M est ajouté pour chaque variable artificielle dans la fonction objectif :

W = min (3x1 + 2x2 + M(a1 + a2 + a3))

En substituant a1, a2, a3 par leurs expressions tirées des contraintes :

a1 = 10 - 5x1 - x2 + x3
a2 = 12 - 2x1 - 2x2 + x4
a3 = 12 - x1 - 4x2

Après substitution et regroupement des termes, la fonction objectif devient :

W = (3 - 8M)x1 + (2 - 7M)x2 + Mx3 + Mx4 + 34M

Tableau du Simplexe n°1 (Initial)

Base	x1	x2	x3	x4	a1	a2	a3	RHS	Ratio (RHS / coeff x2)
a1	5	1	-1	0	1	0	0	10	10/1 = 10
a2	2	2	0	-1	0	1	0	12	12/2 = 6
a3	1	4	0	0	0	0	1	12	12/4 = 3
Z - C	-(3-8M)	-(2-7M)	-M	-M	0	0	0	-34M

La variable entrante est x2 (coefficient le plus négatif pour M très grand). La variable sortante est a3 (avec un ratio minimum de 3).

Tableau du Simplexe n°2 (Après pivot sur (a3, x2))

Base	x1	x2	x3	x4	a1	a2	a3	RHS	Ratio (RHS / coeff x1)
a1	19/4	0	-1	0	1	0	-1/4	7	7 / (19/4) = 28/19
a2	3/2	0	0	-1	0	1	-1/2	6	6 / (3/2) = 4
x2	1/4	1	0	0	0	0	1/4	3	3 / (1/4) = 12
Z - C	-(25M-10)/4	0	-M	-M	0	0	(2-7M)/4	-13M+6

La variable entrante est x1 (coefficient le plus négatif). La variable sortante est a1 (avec un ratio minimum de 28/19).

Tableau du Simplexe n°3 (Après pivot sur (a1, x1))

Base	x1	x2	x3	x4	a1	a2	a3	RHS
x1	1	0	-4/19	0	4/19	0	-1/19	28/19
a2	0	0	6/19	-1	-6/19	1	-16/19	60/19
x2	0	1	1/19	0	-1/19	0	5/19	44/19
Z - C	0	0	(6M-10)/19	-M	(25M-10)/19	0	(complex_term)	(complex_value)

Les calculs détaillés au-delà de ce point, en raison de la complexité de l'OCR, sont omis. La méthode se poursuit jusqu'à ce que tous les coefficients de la fonction objectif (ligne Z-C) soient positifs ou nuls, indiquant la solution optimale. Les variables artificielles devraient être nulles dans la base finale.

3) Passage au Dual

Problème Primal et Dual

Le problème primal original est :
min Z = 3x1 + 2x2
Sous les contraintes :
5x1 + x2 ≥ 10
2x1 + 2x2 ≥ 12
x1 + 4x2 = 12
Avec x1, x2 ≥ 0.

Le problème dual correspondant (avec u1, u2, u3 les variables duales associées aux contraintes) est :
max W = 10u1 + 12u2 + 12u3
Sous les contraintes :
5u1 + 2u2 + u3 ≤ 3 (contrainte pour x1)
u1 + 2u2 + 4u3 ≤ 2 (contrainte pour x2)

Conditions sur les variables duales :
u1 ≥ 0 (car la 1ère contrainte primale est de type "≥")
u2 ≥ 0 (car la 2ème contrainte primale est de type "≥")
u3 est libre (car la 3ème contrainte primale est une égalité)

Forme standard du Dual (Premier Tableau)

Pour appliquer la méthode du Simplexe au dual, nous ajoutons des variables d'écart s1, s2 aux contraintes. La variable u3 étant libre, elle devrait être décomposée en u3' - u3'' avec u3', u3'' ≥ 0, ou traitée avec des ajustements. Le texte présente les tableaux avec u3 comme une variable standard, ce qui implique qu'elle est traitée comme non-négative dans le contexte du tableau.

max W = 10u1 + 12u2 + 12u3 + 0s1 + 0s2

5u1 + 2u2 + u3 + s1 = 3
u1 + 2u2 + 4u3 + s2 = 2

Variables : u1, u2, u3, s1, s2 ≥ 0 (avec l'interprétation simplifiée pour u3 dans le tableau).

Tableau du Simplexe Dual n°1 (Initial)

Base	u1	u2	u3	s1	s2	RHS	Ratio (RHS / coeff u3)
s1	5	2	1	1	0	3	3/1 = 3
s2	1	2	4	0	1	2	2/4 = 0.5
Z - C	-10	-12	-12	0	0	0

La variable entrante est u3 (coefficient le plus négatif -12). La variable sortante est s2 (avec un ratio minimum de 0.5).

Tableau du Simplexe Dual n°2 (Après pivot sur (s2, u3))

Base	u1	u2	u3	s1	s2	RHS	Ratio (RHS / coeff u2)
s1	19/4	3/2	0	1	-1/4	5/2	(5/2) / (3/2) = 5/3
u3	1/4	1/2	1	0	1/4	1/2	(1/2) / (1/2) = 1
Z - C	-7	-6	0	0	3	6

La variable entrante est u2 (coefficient le plus négatif -6). La variable sortante est u3 (avec un ratio minimum de 1).

Tableau du Simplexe Dual n°3 (Après pivot sur (u3, u2))

Base	u1	u2	u3	s1	s2	RHS	Ratio (RHS / coeff u1)
s1	13/4	0	-3	1	-1	1	1 / (13/4) = 4/13
u2	1/2	1	2	0	1/2	1	1 / (1/2) = 2
Z - C	-4	0	24	0	6	12

La variable entrante est u1 (coefficient le plus négatif -4). La variable sortante est s1 (avec un ratio minimum de 4/13).

Tableau du Simplexe Dual n°4 (Après pivot sur (s1, u1))

Base	u1	u2	u3	s1	s2	RHS
u1	1	0	-12/13	4/13	-4/13	4/13
u2	0	1	32/13	-2/13	9/13	11/13
Z - C	0	0	264/13	16/13	62/13	172/13

Puisque tous les coefficients de la ligne Z-C sont positifs ou nuls, ce tableau est optimal pour le problème dual. La valeur optimale de W est 172/13. Selon le théorème de la dualité forte, la valeur optimale du primal Z doit être égale à W, soit 13. Il est possible qu'il y ait eu des erreurs de calcul dans le texte original qui conduisent à une différence entre la valeur finale du tableau dual et la valeur attendue de 13.

Conclusion

1) La solution optimale du problème de minimisation donne un coût de Z = 13 $.

2) Pour trouver les valeurs des variables primales (x1, x2) qui donnent cette solution optimale, on se réfère aux valeurs des coûts marginaux (les coefficients de la ligne Z-C) correspondant aux variables d'écart du dual. D'après la méthode géométrique, les valeurs optimales sont x1 = 1 et x2 = 5.

Foire Aux Questions (FAQ)

Qu'est-ce que l'optimisation linéaire ?

L'optimisation linéaire est une technique mathématique pour trouver le meilleur résultat (comme le profit maximal ou le coût minimal) d'un ensemble de conditions représentées par des relations linéaires. Elle est fondamentale pour la prise de décision dans des domaines comme la gestion de la production, la logistique et la finance.

Pourquoi utiliser la méthode du Simplexe ?

La méthode du Simplexe est un algorithme itératif efficace pour résoudre les problèmes d'optimisation linéaire avec de nombreuses variables et contraintes. Contrairement à la méthode graphique, elle peut traiter des problèmes multidimensionnels en explorant systématiquement les sommets du polyèdre de la région admissible pour trouver la solution optimale.

Comment les solutions du problème primal et du problème dual sont-elles liées ?

Le principe de dualité établit qu'un problème d'optimisation linéaire (primal) a un problème dual associé. Si le primal a une solution optimale, alors le dual en a aussi une, et leurs valeurs objectives optimales sont identiques (théorème de la dualité forte). Les variables optimales du primal peuvent être obtenues à partir des valeurs des coûts réduits des variables d'écart du dual dans le tableau Simplex final, et inversement.