Scribd
Importer
265 vues1 page

Dualité en optimisation linéaire : TD 4

Ce document présente quatre exercices sur l'optimisation linéaire et la programmation linéaire. Les exercices portent sur la construction de problèmes duaux, la résolution graphique de problèmes, et l'analyse de problèmes de mixage de ressources.

Transféré par

Ibidhi Sana
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
265 vues1 page

Dualité en optimisation linéaire : TD 4

Ce document présente quatre exercices sur l'optimisation linéaire et la programmation linéaire. Les exercices portent sur la construction de problèmes duaux, la résolution graphique de problèmes, et l'analyse de problèmes de mixage de ressources.

Transféré par

Ibidhi Sana
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Dualité

Exercice 3

Recherche opérationnelle et optimisation – TD n°4 ENIT Soit le PL suivant :

H. Bouchriha Temimi et C. Sadfi
Max z = -2 x1 - x2 + x3
(P) s.c. x1 + x2 + x3 ≤ 3
Exercice 1 x2 + x3 ≥ 2
x1 + x3 = 1
Démontrer graphiquement que ce problème n’admet pas de solution. x1, x2, x3 ≥ 0
Construire le problème dual. Démontrer graphiquement que le problème dual
1. Quel est le dual de P ?
a une fonction objectif non bornée.
2. Trouver la solution du dual.


Max z = x1 + 2 x2
(P) s.c. - x1 + x2 ≤ -2 Exercice 4
4x1 + x2 ≤ 4
x1, x2 ≥ 0 On considère le programme linéaire suivant représentant un problème de mixage de
trois ressources b1, b2 et b3, d’une compagnie, pour produire 6 produits finis.


Exercice 2

Soit le PL suivant : min z = 15x1 + 7x2 + 3x3 + 39x4 + 51x5 + 35x6
Max z = 3 x1 + 2 x2 s.c. 5x1 + 2 x2 + x3 + 10x4 + 13x5 + 11x6 = 41 (b1)
(P) s.c. x1 + x2 ≤ 80 x1 + x2 + 3x4 + 3x5 + 3x6 = 12 (b2)
4x1 + 2x2 + x3 + 9x4 + 11x5 + 10x6 = 38 (b3)
2x1 + x2 ≤ 100
x1, x2, x3, x4, x5, x6 ≥ 0
x1 ≤ 40

x1, x2 ≥ 0


1. Dresser le tableau canonique associé à la base {x1, x2, x3}.

1. Trouver le dual de P. 2. Est-ce que cette base est optimale ? Sinon trouver le tableau optimal.
2. Utiliser le tableau optimal de P pour trouver la solution optimale du dual. 3. Donner la solution optimale du dual de ce problème (sans résoudre le dual)
4. La compagnie a le choix de diminuer la quantité de l’une des ressources bi par
rapport à sa valeur actuelle. Est-ce que c’est avantageux de le faire ? Si oui,
x1 x2 s1 s2 s3 lesquelles des ressources est-elle la plus prioritaire d’être diminuée ? Toutes
s3 0 0 1 -1 1 20 les réponses doivent être justifiées.
x2 0 1 2 -1 0 60
x1 1 0 -1 1 0 20
∆j 0 0 -1 -1 0 -180


3. Vérifier le théorème de dualité dans ce cas.

Vous aimerez peut-être aussi