Scribd
Importer
13 vues4 pages

Programmation Linéaire : Exemples et Solutions

Le document présente des exemples de programmation linéaire, illustrant la maximisation et la minimisation de fonctions avec des contraintes. Les solutions sont détaillées à travers des tableaux montrant les variables, les coefficients et les valeurs optimales. Les résultats finaux des exemples montrent les valeurs optimales pour les variables et les valeurs de la fonction objectif.

Transféré par

melinaguergueb94
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd
13 vues4 pages

Programmation Linéaire : Exemples et Solutions

Le document présente des exemples de programmation linéaire, illustrant la maximisation et la minimisation de fonctions avec des contraintes. Les solutions sont détaillées à travers des tableaux montrant les variables, les coefficients et les valeurs optimales. Les résultats finaux des exemples montrent les valeurs optimales pour les variables et les valeurs de la fonction objectif.

Transféré par

melinaguergueb94
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd

UNIVERSITE Mohamed Khider de Biskra

Département D’Informatique
Module : Programmation linéaire

Solution TD 05
Exemple (01) :

1) Max Z(X)= x1 +5x2 Max Z(X)= x1 + 5x2 -M A1-M A2


x1 + 3x2 ≤ 10 P’ x1 + 3x2 + e1 = 10
P
2x1- 3x2 ≥ 5 2x1 -3x2 - e2 +A1=5
x1 + x2 = 4 x1 +x2 +A2 =4
où xi ≥ 0 pour i =1; 2 où xi ,ei, Ai≥ 0 pour i =1; 2

Cj’=Cj+∑ aij A (M )
i

x1 x2 e1 e2 A1 A2 B min

e1 1 3 1 0 0 0 10 10

A1 2 -3 0 -1 1 0 5 5/2

A2 1 1 0 0 0 1 4 4

Cj 1 5 0 0 0 0 0

Cj’ 1+3M 5-2M 0 -M M M 9M

Max

x1 x2 e1 e2 . A2 B

e1 0 9/2 1 1/2 0 15/2 5/3

x1 1 -3/2 0 -1/2 0 5/2 --

A2 0 5/2 0 1/2 1 3/2 3/5

Cj 0 13/2 0 1/2 0 -5/2

Cj’ 0 13/2+5/2M 0 ½+½M M -5/2+3/2M


Max
x1 x2 e1 e2 . . B

e1 0 0 1 -2/5 24/5

x1 1 0 0 -1/5 17/5

x2 0 1 0 1/5 3/5

Cj 0 0 0 -4/5 -32/5

Cj’ 0 0 0 -4/5 32/5

Les Cj’ sont indépendante de M, on dit que une solution réalisable est obtenue
( condition nécessaire)

x1 x2 e1 e2 B

e1 0 0 1 -2/5 24/5

x1 1 0 0 -1/5 17/5

x2 0 1 0 1/5 3/5

Cj 0 0 0 -4/5 -32/5

Toute les Cj ≤0, donc le critère d’arrêt est satisfait

La solution est : X1 = 17/5, X2= 3/5, Z = 32/5

Exemple (02) :

Min Z(Y) = 14 y1 + 10y2 + 3y3 Min Z(Y) = 14 y1 + 10y2 + 3y3+MA1 +MA2


y1 + 2y2 + y3 ≥ 2 y1 + 2y2 + y3-e1+A1 = 2
2 y1 - y2 - y3 ≥ 1 2 y1 - y2 - y3 -e2+A2 = 1
Où yi ≥ 0 pour i =1;3. Où yi ≥ 0 pour i =1;3. A1, A2≥0 ; e1,e2 ≥0
n

Cj’=Cj-∑ aij A (+ M )
i

y1 y2 y3 e1 e2 A1 A2 B
Min
A1 1 2 1 -1 0 1 0 2
2
A2 2 -1 -1 0 -1 0 1 1 1/2

Cj 14 10 3 0 0 0 0 0

Cj’ 14-3M 10-M 3 M M -M -M -3M

Min

y1 y2 y3 e1 e2 A1 B Min

A1 0 5/2 3/2 -1 1/2 1 3/2 3/5

y1 1 -1/2 -1/2 0 -1/2 0 1/2 --

Cj 0 17 10 0 7 0 -7

Cj’ 0 17-5/2M 10-3/2M M 7-1/2M -M -7-3/2M

Min

y1 y2 y3 e1 e2 B

y2 0 1 3/5 -2/5 1/5 3/5

y1 1 0 -1/5 -1/5 -2/5 4/5

Cj 0 0 -1/5 34/5 18/5 -86/5

Cj’ 0 0 -1/5 34/5 18/5 -86/5

Les Cj’ sont indépendante de M, on dit que une solution réalisable est obtenue
( condition nécessaire)
Min
y1 y2 y3 e1 e2 B

y2 0 1 3/5 -2/5 1/5 3/5 1

y1 1 0 -1/5 -1/5 -2/5 4/5 --

Cj 0 0 -1/5 34/5 18/5 -86/5

Min

y1 y2 y3 e1 e2 B

y3 0 5/3 1 -2/3 1/3 1

y1 1 1/3 0 -1/3 -1/3 1

Cj 0 1/3 0 20/3 11/3 -17

Toute les Cj ≥ 0 (problème de minimisation), donc le critère d’arrêt est


satisfait.

La solution est : y1 = 1, y2= 0, y3=1 Z(Y) = 17.

Vous aimerez peut-être aussi