Scribd
Importer
138 vues3 pages

Fiche 4

Ce document contient plusieurs exercices de programmation linéaire. Les exercices portent sur la formulation de programmes primale et duale, la représentation graphique des contraintes, et la résolution de programmes linéaires avec la méthode du simplexe sous forme algébrique ou tableau.

Transféré par

Hamza Ghoudrani
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
138 vues3 pages

Fiche 4

Ce document contient plusieurs exercices de programmation linéaire. Les exercices portent sur la formulation de programmes primale et duale, la représentation graphique des contraintes, et la résolution de programmes linéaires avec la méthode du simplexe sous forme algébrique ou tableau.

Transféré par

Hamza Ghoudrani
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é Hassan II de Casablanca

Faculté des Sciences et Techniques de Mohammedia


Département de Mathématiques
Recherche opérationnelle
TD4
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Exercice 1 :
Soit le programme primal suivant


 max z = 4x1 + 6x2
4x1 + 2x2 ≤ 8

(P)

 4x1 − 3x2 ≥ 24
x1 ≥ 0, x2 ≥ 0

1/ Vérier que le primal n'a pas de solution admissible (réalisable).


2/ Formuler le programme dual.
3/ Vérier que la solution u1 = 3, u2 = −1 est une solution réalisable au dual.
4/ A quel cas correspond ce couple de programme (primal-dual) ?
Exercice 2 :
Soit le programme primal suivant


 max z = 2x1 + 2x2
−x1 + x2 = 1

(P)

 −1/4x1 − 3x2 = 0
x1 ≥ 0, x2 ≥ 0

1/ Formuler le programme dual.


2/ Tracer les contraintes de chaque programme.
3/ Existe-t-il des solutions réalisables
a) pour le primal ?
b) pour le dual ?
4/ Quelle propriété existe ici entre le primal et le dual ?

1
Exercice 3 :
Résoudre le PL suivant avec la méthode de Simplexe (algébrique)


 max z = −x1 + x2
 −2x1 + x2 ≤ 1


(P) x1 + 3x2 ≤ 10
x1 ≤4




x1 ≥ 0, x2 ≥ 0

Exercice 4 :
Résoudre le PL suivant avec la méthode de Simplexe (tableau)


 max z = x1 + 3x2
 x1 + x2 ≤ 14


(P) −2x1 + 3x2 ≤ 12
2x1 − x2 ≤ 12




x1 ≥ 0, x2 ≥ 0

Exercice 5 :
Soit le programme linéaire suivant


 min −x1 − 3x2 − 5x3 − x4 − 4x5
x1 + x2 − x3 + x4 =1



(P) 2x1 + 4x2 + 2x4 + x5 = 7
x1 + 5x2 + x4 + 4x5 = 12




x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0

On considère la base K = {2, 3, 5}


1/ Donner le tableau du simplexe correspondant à cette base
2/ La solution de base obtenue est-elle optimale ? Sinon déterminer la solution optimale.

2
Exercice 6
Soit le programme linéaire suivant :


 max z = 5x1 + 4x2
6x1 + 4x2 ≤ 24




x1 + 2x2 ≤ 6

(P)

 x2 ≤ 2
−x1 + x2 ≤ 1




x1 , x2 ≥ 0

1/ Résoudre le programme linéaire (P).


2/ Dénir le dual (D) associé à (P).
3/ Déduire la solution de (D).

Exercice 7 :
Utiliser la méthode de Simplexe (tableau) à deux phases pour trouver la solution optimale
du PL suivant : 

 min 2x1 + 3x2
 2x1 + x2 ≤ 16


(P) x1 + 3x2 ≥ 20
x1 + x2 = 10




x1 ≥ 0, x2 ≥ 0

Vous aimerez peut-être aussi