Embed Size (px)
DESCRIPTION
Démonstration n°10. Exemple de Klee- Minty. Problème de Klee- Minty. Exemple pour n = 3. Klee- Minty : l’algorithme du simplexe suivant les règles habituelles nécessitera 2^3 – 1 opérations de pivots avant de trouver une solution optimale. Tous les points extrêmes sont visités. - PowerPoint PPT Presentation
Citation preview
Démonstration n°10
Exemple de Klee-Minty
Problème de Klee-Minty
Exemple pour n = 3
Klee-Minty : l’algorithme du simplexe suivant les règles habituelles nécessitera 2^3 – 1 opérations de pivots avant de trouver une solution optimale. Tous les points extrêmes sont visités.
Tableau initial
X1 X2 X3 X4 X5 X6 -z TD
X4 1 1 1
X5 20 1 1 100
X6 200 20 1 1 10^4
-z -100 -10 -1 1 0
Tableau #1
X1 X2 X3 X4 X5 X6 -z TD
X1 1 0 0 1 0 0 1
X5 0 1 0 -20 1 0 80
X6 0 20 1 -200 0 1 9800
-z 0 -10 -1 100 0 0 1 100
Tableau #2
X1 X2 X3 X4 X5 X6 -z TD
X1 1 0 0 1 0 0 1
X2 0 1 0 -20 1 0 80
X6 0 0 1 200 -20 1 8200
-z 0 0 -1 -100 10 0 1 900
Tableau #3
X1 X2 X3 X4 X5 X6 -z TD
X4 1 0 0 1 0 0 1
X2 10 1 0 0 1 0 100
X6 -200 0 1 0 -20 1 8000
-z 100 0 -1 0 10 0 1 1000
Tableau #4
X1 X2 X3 X4 X5 X6 -z TD
X4 1 0 0 1 0 0 1
X2 20 1 0 0 1 0 100
X3 -200 0 1 0 -20 1 8000
-z -100 0 0 0 -10 1 1 9000
Tableau #5
X1 X2 X3 X4 X5 X6 -z TD
X1 1 0 0 1 0 0 1
X2 0 1 0 -20 1 0 80
X3 0 0 1 200 -20 1 8200
-z 0 0 0 100 -10 1 1 9100
Tableau #6
X1 X2 X3 X4 X5 X6 -z TD
X1 1 0 0 1 0 0 1
X5 0 1 0 -20 1 0 80
X3 0 20 1 -200 0 1 9800
-z 0 10 0 -100 0 1 1 9900
Tableau #7
X1 X2 X3 X4 X5 X6 -z TD
X4 1 0 0 1 0 0 1
X5 20 1 0 0 1 0 100
X3 200 20 1 0 0 1 10000
-z 100 10 0 0 0 1 1 10000
Solution optimale X = (0, 0, 10^4, 1, 100, 0) de valeur optimale - 10 000.
Bases réalisables
A : matrice 3 lignes, 6 colonnes Nombre de matrices carrées = 20Nombre de bases réalisables = 8B0, B3, B5, B9, B10, B14, B16, B19
X1 X2 X3 X4 X5 X6 SS-Matrices de A
0 1 10 10000 B19
1 1 80 9800 B9
2 1 80 8200 B3
3 100 1 8000 B14
4 100 8000 1 B10
5 1 80 8200 B0
6 1 9800 80 B5
7 10000 1 100 B16
Code Matlab pour les sous-matrices carrées de A
• A= [1 0 0 1 0 0;20 1 0 0 1 0;200 20 1 0 0 1]• b=[1; 100; 10000]• B0 = [A(:,1) A(:,2) A(:,3)];• B1 = [A(:,1) A(:,2) A(:,4)];• B2 = [A(:,1) A(:,2) A(:,5)];• B3 = [A(:,1) A(:,2) A(:,6)];• B4 = [A(:,1) A(:,3) A(:,4)];• B5 = [A(:,1) A(:,3) A(:,5)];• B6 = [A(:,1) A(:,3) A(:,6)];• B7 = [A(:,1) A(:,4) A(:,5)];• B8 = [A(:,1) A(:,4) A(:,6)];• B9 = [A(:,1) A(:,5) A(:,6)];• B10 =[A(:,2) A(:,3) A(:,4)];• B11 =[A(:,2) A(:,3) A(:,5)];• B12 =[A(:,2) A(:,3) A(:,6)];• B13 =[A(:,2) A(:,4) A(:,5)];• B14 =[A(:,2) A(:,4) A(:,6)];• B15= [A(:,2) A(:,5) A(:,6)];• B16 =[A(:,3) A(:,4) A(:,5)];• B17 =[A(:,3) A(:,4) A(:,6)];• B18 =[A(:,3) A(:,5) A(:,6)];• B19 =[A(:,4) A(:,5) A(:,6)];
