Scribd
Importer
69 vues1 page

TD5 - Dualité

Ce document contient des exercices sur la dualité de programmes linéaires. Il présente plusieurs problèmes d'optimisation linéaire et demande de formuler leur problème dual respectif. Il demande également d'appliquer le théorème des écarts complémentaires pour vérifier l'optimalité de solutions proposées.

Transféré par

Hamza Boujemel
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
69 vues1 page

TD5 - Dualité

Ce document contient des exercices sur la dualité de programmes linéaires. Il présente plusieurs problèmes d'optimisation linéaire et demande de formuler leur problème dual respectif. Il demande également d'appliquer le théorème des écarts complémentaires pour vérifier l'optimalité de solutions proposées.

Transféré par

Hamza Boujemel
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

Université Mohamed VI Polytechnique Année Universitaire 2023-2024

Master TIUF Niveau : M1


Module : Recherche opérationnelle, Semestre 1
Optimisation et Analyse multicritères.

TD N°5 : La dualité

Exercice 1 :
Formuler le problème dual de chacun des programmes linéaires suivants :

max z = 2x1 + 4x2 + 3x3 max z = 3x1 + x2 − 2x3


3x1 + 4x2 + 2x3 ≤ 60 x1 + 2x2≥ 10
(P1) 2x1 + x2 + 2x3 ≤ 40 (P2) 3x1 − x2 + x3 = 7
x1 + 3x2 + 2x3 ≤ 80 x1 + 3x3 ≤ 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 x2 ≥ 0, x3 ≥ 0

max z = 10x1 + 14x2 max z = 400x1 + 350x2 + 450x3


x1 + x2 ≥ 12 2x1 − 3x2 + 2x3 ≤ 120
(P3) x1≥ 8 (P4) 4x1 + 3x2= 160
x2 ≤ 6 3x1 − 2x2 + 4x3 ≥ 100
𝑥1 ≥ 0, x2 ≥ 0 𝑥1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Exercice 2
Appliquer le théorème des écarts complémentaires pour vérifier l’optimalité de la solution
proposée.
max z = 7x1 + 6x2 + 5x3 − 2x4 + 3x5
x1 + 3x2 + 5x3 − 2x4 + 2x5 ≤ 4
4x1 + 2x2 − 2x3 + x4 + x5 ≤ 3
2x1 + 4x2 + 4x3 − 2x4 + 5x5 ≤ 5
3x1 + x2 + 2x3 − x4 − 2x5 ≤ 1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
Solution proposée : (x1, x2, x3, x4, x5) = (0, 4/3, 2/3, 5/3, 0)

Exercice 3
Appliquer le théorème des écarts complémentaires pour vérifier l’optimalité de la solution
proposée.

max z = 4x1 + 5x2 + x3 + 3x4 − 5x5 + 8x6


x1 − 4x3 + 3x4 + x5 + x6 ≤ 1
5x1 + 3x2 + x3 − 5x5 + 3x6 ≤ 4
4x1 + 5x2 − 3x3 + 3x4 − 4x5 + x6 ≤ 4
−x2 + 2x4 + x5 − 5x6 ≤ 5
− 2x1 + x2 + x3 + x4 + 2x5 + 2x6 ≤ 7
2x1 − 3x2 + 2x3 − x4 + 4x5 + 5x6 ≤ 5
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0

Solution proposée : (x1, x2, x3, x4, x5, x6) = (0, 0, 5/2, 7/2, 0, 1/2)

Vous aimerez peut-être aussi