Scribd
Upload
42 views3 pages

Forme Canonique Forme Standard MAX (Z) X1 + 2X2 MAX (Z) X1 + 2X2

1. The document discusses several linear programming problems presented in both canonical and standard form. It provides the constraints, objective functions and optimal solutions for each problem. 2. The problems involve maximizing or minimizing linear functions subject to various constraints on variables. The document converts the problems between canonical and standard form and solves for the optimal values. 3. Several worked examples are presented with the objective function, constraints, basis matrices and optimal solutions provided for each linear program.

Uploaded by

asmaelhanbout
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
42 views3 pages

Forme Canonique Forme Standard MAX (Z) X1 + 2X2 MAX (Z) X1 + 2X2

1. The document discusses several linear programming problems presented in both canonical and standard form. It provides the constraints, objective functions and optimal solutions for each problem. 2. The problems involve maximizing or minimizing linear functions subject to various constraints on variables. The document converts the problems between canonical and standard form and solves for the optimal values. 3. Several worked examples are presented with the objective function, constraints, basis matrices and optimal solutions provided for each linear program.

Uploaded by

asmaelhanbout
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Recherche opérationnelle : Travail à rendre 2

Fait par : EL KATI REDA

1
Forme canonique Forme standard
MAX (Z) = X1 + 2X2 MAX (Z) = X1 + 2X2

SC : SC :

BASE X1 X2 X3 X4 X5 b b/ai BASE X1 X2 X3 X4 X5 b b/ai


X3 -3 2 1 0 0 2 1 X2 -1,5 1 0,5 0 0 1 -0,67
X4 -1 2 0 1 0 4 2 X4 2 0 -1 1 0 2 1
X5 1 1 0 0 1 5 5 X5 2,5 0 -0,5 0 1 4 1,6
Cj-Zj 1 2 0 0 0 0 Cj-Zj 4 0 -1 0 0 -2

BASE X1 X2 X3 X4 X5 b b/ai BASE X1 X2 X3 X4 X5 b b/ai


X2 0 1 -0,25 0,75 0 2,5 -10 X2 0 1 0 0,33 0,33 3
X1 1 0 -0,5 0,5 0 1 -2 X1 1 0 0 -0,33 0,67 2
X5 0 0 0,75 -1,25 1 1,5 2 X3 0 0 1 -1,67 1,33 2
Cj-Zj 0 0 1 -2 0 -6 Cj-Zj 0 0 0 -0,33 -1,33 -8

X1= 2 X2= 3 Z=8

2
Forme canonique Forme standard
MAX (Z) = 12 X1 + 12 X2 MAX (Z) = 12 X1 + 12 X2

SC : SC :

BASE X1 X2 X3 X4 b b/a(x1) b/a(x1) BASE X1 X2 X3 X4 b


X3 1 1 1 0 7 7 7 X1 1 1 1 0 7
X4 2 1 0 1 14 7 14 X4 0 -1 -2 1 0
Cj-Zj 12 12 0 0 0 Cj-Zj 0 0 -12 0 -84
On prend X1 variable entrante et X3 variable sortante => P=1

X1= 7 X2= 0 Z=84

3
Forme canonique Forme standard
MAX (Z) = X1 MAX (Z) = X1

SC : SC :

BASE X1 X2 X3 X4 X5 b b/ai (∑Cj)/P BASE X1 X2 X3 X4 X5 b b/ai


X3 1 -1 1 0 0 1 1 1 X1 1 -1 1 0 0 1 -1
X4 2 -1 0 1 0 2 1 1 X4 0 1 -2 1 0 0 0
X5 1 1 0 0 1 7 7 X5 0 2 -1 0 1 6 3
Cj-Zj 1 0 0 0 0 0 Cj-Zj 0 1 -1 0 0 -1
La variable sortante est X1. On prend X3 variable sortante
BASE X1 X2 X3 X4 X5 b b/ai BASE X1 X2 X3 X4 X5 b b/ai
X1 1 0 -1 1 0 1 -1 X1 1 0 0 0,33 0,33 3
X2 0 1 -2 1 0 0 0- X2 0 1 0 -0,33 0,67 4
X5 0 0 3 -2 1 6 2 X5 0 0 1 -0,67 0,33 2
Cj-Zj 0 0 1 -1 0 -1 Cj-Zj 0 0 0 -0,33 -0,33 -3

X1= 3 X2= 4 Z=3

4
Forme canonique Forme standard
Min (Z) = X1 – X2 + X3 Min (Z) = X1 – X2 + X3 + 0X4 + 0X5 + Ma1

SC : SC :

BASE X1 X2 X3 X4 X5 a1 b b/ai
CJ 1 -1 1 0 1 M
X5 1 1 3 0 -1 0 1 4 1,333333333
a1 M 1 1 -1 0 1 0 10 10
Zj 1+M 3 + M -M -1 M 1
Cj-Zj -M -4 -M 1 + M 1 1-M M-1 4 + 10M

BASE X1 X2 X3 X4 X5 a1 b b/ai
CJ 1 -1 1 0 1 M
X2 -1 0,33 1 0 - 0,33 0 0,33 1,33 ∞
a1 M 0,67 0 -1 0,33 1 - 0,33 8,67 8,666666667
Zj 0,67 M - 0,33 -1 -M 0,33 M + 0,33 M -0,33 M - 0,33
Cj-Zj 0,67 - 0,67 M 0 1 + M -0,33M - 0,33 1 - M 1,33 M + 0,33 8,67 M - 1,33

BASE X1 X2 X3 X4 X5 a1 b b/ai
CJ 1 -1 1 0 1 M
X2 -1 0,33 1 0 - 0,33 0 0,33 1,33 -4
X5 1 0,67 0 -1 0,33 1 - 0,33 8,67 26
Zj 0,33 -1 -1 0,67 1 - 0,67
Cj-Zj 0,67 0 2 - 0,67 0 M + 0,67 7,33

BASE X1 X2 X3 X4 X5 a1 b b/ai
CJ 1 -1 1 0 1 M
X2 -1 1 1 -1 0 1 0 10,00
X4 0 2 0 -3 1 3 -1 26
Zj -1 -1 1 0 -1 0
Cj-Zj 2 0 0 0 2 M -10

X1 = X3 = 0 X2= 10 Z= -10

5
Forme canonique Forme standard
Min (Z) = X2 – 2X1 Min (Z) = X2 – 2X1+ 0X3 + 0X4 + 0X5 + 0X6 +Ma1

SC :
SC :
BASE X1 X2 X3 X4 X5 X6 a1 b b/ai BASE X1 X2 X3 X4 X5 X6 a1 b b/ai
CJ -2 1 0 0 0 0 M (∑Cj)/P CJ -2 1 0 0 0 0 M
a1 M 1 0 -1 0 0 0 1 2 2 1 X1 -2 1 0 -1 0 0 0 1 2 -2
X4 0 1 0 0 1 0 0 0 8 8 X4 0 0 0 1 1 0 0 -1 6 6
X5 0 -1 1 0 0 1 0 0 0 0- X5 0 0 1 -1 0 1 0 1 2 -2
X6 0 1 -1 0 0 0 1 0 2 2 1 X6 0 0 -1 1 0 0 1 -1 0 0
Zj M 0 -M 0 0 0 M Zj -2 0 2 0 0 0 -2
Cj-Zj -2 - M 1 M 0 0 0 0 2M Cj-Zj 0 1 -2 0 0 0 M+2 -4
X1 est la variable entrante. On prend a1 la variable sortante

BASE X1 X2 X3 X4 X5 X6 a1 b b/ai BASE X1 X2 X3 X4 X5 X6 a1 b b/ai


CJ -2 1 0 0 0 0 M CJ -2 1 0 0 0 0 M
X1 -2 1 -1 0 0 0 1 0 2 -2 X1 -2 1 0 0 1 0 0 0 8
X4 0 0 1 0 1 0 -1 0 6 6 X2 1 0 1 0 1 0 -1 0 6
X5 0 0 0 0 0 1 1 0 2 ∞ X5 0 0 0 0 0 1 1 0 2
X3 0 0 -1 1 0 0 1 -1 0 0- X3 0 0 0 1 1 0 0 -1 6
Zj -2 2 0 0 0 -2 0 Zj -2 1 0 -1 0 -1 0
Cj-Zj 0 -1 0 0 0 2 M -4 Cj-Zj 0 0 0 1 0 1 M -10

X1 =8 X2= 6 Z= -10

6
Forme canonique Forme standard
MAX (Z) = 10X1 + 12X2 + 8X3 + 9X4 MAX (Z) = 10X1 + 12X2 + 8X3 + 9X4 + 0X5 + 0X6 –Ma1 – Ma2

SC : SC :

BASE X1 X2 X3 X4 X5 X6 a1 a2 b b/ai BASE X1 X2 X3 X4 X5 X6 a1 a2 b b/ai

CJ 10 12 8 9 0 0 -M -M CJ 10 12 8 9 0 0 -M -M

a1 -M 1 1 1 1 0 0 1 0 100 100 a1 -M 1 1 0 0 1 0 1 -1 70 70

a2 -M 0 0 1 1 -1 0 0 1 30 30 X4 9 0 0 1 1 -1 0 0 1 30 ∞
X6 0 0 1 0 1 0 1 0 0 50 50 X6 0 0 1 -1 0 1 1 0 -1 20 20

Zj -M -M -2M -2M M 0 -M -M Zj -M -M 9 9 -M - 9 0 -M -M + 9

Cj-Zj 10 + M 12 + M 8 + 2M 9 + 2M -M 0 0 0 -130 M Cj-Zj 10 + M 12 + M -1 0 M+9 0 0 -9 270 - 70M

BASE X1 X2 X3 X4 X5 X6 a1 a2 b b/ai BASE X1 X2 X3 X4 X5 X6 a1 a2 b b/ai

CJ 10 12 8 9 0 0 -M -M CJ 10 12 8 9 0 0 -M -M

a1 -M 1 0 1 0 0 -1 1 0 50 50 a1 -M 1 0 0 -1 1 -1 1 -1 20 20

X4 9 0 0 1 1 -1 0 0 1 30 30 X3 8 0 0 1 1 -1 0 0 1 30 ∞
X2 12 0 1 -1 0 1 1 0 -1 20 -20 X2 12 0 1 0 1 0 1 0 0 50 ∞
Zj -M 12 -M -3 9 3 12 + M -M -3 Zj -M 12 8 M + 20 -M - 8 M + 12 -M M+8

Cj-Zj 10 + M 0 11 + M 0 -3 -12 - M 0 -M + 3 510 - 50M Cj-Zj 10 + M 0 0 -M - 11 M+8 -M - 12 0 -2M - 8 840 - 20M

BASE X1 X2 X3 X4 X5 X6 a1 a2 b b/ai
CJ 10 12 8 9 0 0 -M -M
X1 10 1 0 0 -1 1 -1 1 -1 20
X3 8 0 0 1 1 -1 0 0 1 30
X2 12 0 1 0 1 0 1 0 0 50
Zj 10 12 8 10 2 2 10 -2
Cj-Zj 0 0 0 -1 -2 -2 -M - 10 -M + 2 1040

X1 = 20 X2 = 50 X3 = 30 X4 = 0 Z= 1040

You might also like