Scribd
Importer
37 vues2 pages

Fiche 2. TD - Optimisation Convexe: PL Z X X X X X X, X X X, X, X, X - B, B

Le document présente des exercices d'optimisation convexe liés à des programmes linéaires, incluant des résolutions graphiques et par la méthode du simplexe. Chaque exercice aborde des aspects spécifiques comme la forme standard, la réalisabilité des bases, et l'utilisation de la méthode Big M. Les exercices sont conçus pour aider les étudiants à comprendre et appliquer les concepts d'optimisation en mathématiques appliquées.

Transféré par

Abdellah Kahlaoui
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
37 vues2 pages

Fiche 2. TD - Optimisation Convexe: PL Z X X X X X X, X X X, X, X, X - B, B

Le document présente des exercices d'optimisation convexe liés à des programmes linéaires, incluant des résolutions graphiques et par la méthode du simplexe. Chaque exercice aborde des aspects spécifiques comme la forme standard, la réalisabilité des bases, et l'utilisation de la méthode Big M. Les exercices sont conçus pour aider les étudiants à comprendre et appliquer les concepts d'optimisation en mathématiques appliquées.

Transféré par

Abdellah Kahlaoui
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 Premier Année Universitaire 2021/2022

Faculté des Sciences et Techniques - Settat

Master 1 : Mathématiques et Applications

Fiche 2. TD - Optimisation convexe

Exercice 1 Soit le programme linéaire (P L) :

min z = −x1 − x2 − x3



x1 − 2x2 + 2x3 = 5,


(P L) 

 2x1 + 3x2 − x3 = 4,
x1 , x2 , x3 ≥ 0.

1. Montrer que B = {1, 3} est une base.


2. Montrer que B est réalisable.
3. Résoudre (PL).

Exercice 2 Soit le programme linéaire (PL) :

min z = −5x1 − x2 − 6x3 − 2x4





4x1 + 4x2 + 4x3 + x4 ≤ 24,


(P L)


 8x1 + 6x2 + 4x3 + 3x4 ≤ 36,
x1 , x2 , x3 , x4 ≥ 0.

1. Donner la forme standard de (PL).


2. Mettre (PL) sous forme canonique par rapport à la base {3, 4}.
3. Résoudre (PL).

Exercice 3 Résoudre graphiquement le programme (P ), puis à l’aide des tableaux du sim-


plexe :
min −2x1 − x2



 x + x ≤ 4,

1 2
(P )


 x 1 − x 2 ≤ 1,
x1 , x2 ≥ 0.

Exercice 4 (Big M) On considère le programme linéaire suivant :

min c> x



(P L) Ax = b,
x ≥ 0.

Au programme (PL) on associe le programme linéaire (PL’)


m

min c> x + M
 X



 yi
0 i=1
(P L )


 Ax + y = b,
x ≥ 0, y ≥ 0,

où M ∈ R∗+ . Si le programme (PL’) est résolu par la méthode du simplexe, montrer que :
1) Si une solution optimale est trouvée avec y = 0 alors les composantes en x corres-
pondent à une solution réalisable de (PL).
2) Si pour tout M > 0, une solution optimale est trouvée avec y 6= 0, alors le programme
(PL) est incompatible.
3) On suppose que le programme (PL) a un optimum fini z ∗ . Soit z ∗ (M ) l’optimum de
(PL’) pour M fixé.
a) Montrer que z ∗ (M ) ≤ z ∗ .
b) Montrer que si M1 ≤ M2 alors z ∗ (M1 ) ≤ z ∗ (M2 ).
c) Montrer qu’il existe M0 tel que z ∗ (M ) = z ∗ , pour tout M ≥ M0 .

Exercice 5 On considère le programme linéaire (P) suivant :




 min z = x1 + x2 ,
x1 − 2x2 ≤ 2,





x2 ≤ 4,


(P )


 x1 + x2 ≥ 4,
x1 − x2 ≥ 0,





x1 , x2 ≥ 0.

1. a) Résoudre graphiquement le programme (P).


b) Résoudre (P) à l’aide de la méthode des tableaux.

Exercice 6 Considérons le programme linéaire suivant :

(P ) min{c> x | Ax ≥ b, x ≥ 0},

où A est une matrice m × n, c ∈ Rn et b ∈ Rm avec b ≥ 0.


1. Mettre le problème (P ) sous forme standard.
2. Soit bk = max{bi | 1 ≤ i ≤ m} et considérons le problème sous forme standard
obtenu en 1. En ajoutant la k ieme contrainte de ce problème à l’opposé de chacune
des autres contraintes, montrer que le nouveau problème obtenu ne necessite que
l’addition d’une seule variable artificielle pour obtenir la matrice identité comme base
initiale réalisable.
3. Utiliser cette technique pour résoudre le programme linéaire suivant :




min z = x1 + 2x2 + x3
x1 + 2x2 + x3 ≥ 4,




(P ) 2x1 + x2 + x3 ≥ 5,
2x1 + 3x2 + 2x3 ≥ 6,





x1 , x2 , x3 ≥ 0.

Vous aimerez peut-être aussi