Мәселені шешу теріс симплекс айырмашылықтары жойылғанға дейін бір тірек жоспарынан екіншісіне ауысудан тұрады. Бұл ауысу Джордан-Гаусс түрлендірулері арқылы жүзеге асырылады. Бұл ретте симплекс-айырмашылықтар жолы басқа жолдар сияқты ережелер бойынша қайта есептеледі.
Мүмкіндік-шешуші элементті таңдау әдісі.
Рұқсат етілген баған ретінде теріс симплекс айырмашылығы бар баған таңдалады(бұл L сызықтық формасының өсу шарты).
Егер (-) белгісі бар бірнеше симплекс айырмашылықтары болса, онда модуль бойынша ең үлкен мәні бар ∆ ( - ) баған таңдалады.
Рұқсат етілген жол ретінде bi/aik қатынасы таңдалған баған үшін ең аз мәнге ие болады (бұл жоспардың анықтамалығын сақтау шарты).
Бұл жағдайда тек оң жақтары ескеріледі aik .
Теріс симплекс айырмашылықтары бар барлық бағандарда оң aik элементтерінің болмауы L сызықтық формасының шектеусіздігін көрсетеді.
Тапсырманы симплексті әдіспен шешудің мысалы. Функцияны барынша арттыру L = x1 + 7x2 +2x3 + x4 – x5max
шектеу кезінде 6x1 + 3x2 +x3 + x4 + x5 = 20
4x1 + 3x2 +x4 = 12
3x1 - 2x2 + x5 = 6
xi ≥ 0 , i=1÷5
Шешім. Кестеге жазайық
A1
A2
A3
A4
A5
B
6
3
1
1
1
20
4
3
0
1
0
12
3
-2
0
0
1
6
Рұқсат етуші элемент ретінде a24=1 алыңыз, өйткені
min{12/1 и 20/1}=12.
Джордан-Гаусс әдісімен барлық элементтерді түрлендіре отырып, біз келесі кестені аламыз:
Рұқсат етуші элемент ретінде a35=1алыңыз. біз кесте аламыз:
Анықтамалық шешім:
X = (0,0,2,12,6)
A1
A2
A3
A4
A5
B
2
0
1
0
1
8
4
3
0
1
0
12
3
-2
0
0
1
6
A1
A2
A3
A4
A5
B
-1
2
1
0
1
2
4
3
0
1
0
12
3
-2
0
0
1
6
Алынған анықтамалық шешім үшін бірінші симплекс кестесін құрайық:
Баз.
Сбаз
B
1
A1
7
A2
2
A3
1
A4
-1
A5
A3
2
2
-1
2
1
0
0
A4
1
12
4
3
0
1
0
A5
-1
6
3
-2
0
0
1
L=
10
-2
2
0
0
0
Соңғы жолда теріс сан бар алынған тірек жоспары оңтайлы емес.
(-)бағандағы симплекс жолындағы сан A1. Бұл x1 айнымалысын негізге енгізу керек дегенді білдіреді.
Ал негізден қандай айнымалы алу керек?
min{12/4;6/3}=2 табамыз айнымалыны шығару x5 . Р.Э. a31=3
Аламыз L = 6x1 - x2 +2x3 - М x5max
4x1 + x2 +x3 + x5 = 8
2x1 - x2 +x3 + x4 = 6
xi ≥ 0 , i=1÷5
Симплекс кестесін құру
Жоспар оңтайлы емес, өйткені симплекс жолында ( - ) элементтер бар. Модуль бойынша ең үлкені ретінде A1 рұқсат бағанын таңдаңыз
теріс симплекс айырмашылығы. Біз қатынасты табамыз bi / ai1 : 8/4 < 6/2
Рұқсат жолы бірінші, ал рұқсат элементі а11 =4. Бұл
бұл жаңа жоспарда х5 негізден шығады, ал x1 негізге енеді дегенді білдіреді.
Симплекс түрлендірулер жаңа тірек жоспарын береді:
Баз
Сбаз
B
6
A1
-1
A2
2
A3
0
A4
-M
A5
A5
-M
8
4
1
1
0
1
A4
0
6
2
-1
1
1
0
-M
-4M-6
-M+1
-M-2
0
0
Сызықтық пішін өсті (L=12), Бірақ алынған жоспар әлі оңтайлы емес. Теріс симплекс айырмашылығы бар. Жаңа рұқсат элементін таңдаңыз a23 =1/2. Жасанды X5 айнымалысы негізден шықты5 бағанын қарастырудан алып тастауға болады. Симплекс түрлендірулер жаңа тірек жоспарын береді:
Симплекс-жол-оң. Алынған жоспар оңтайлы.
X = (1;0;4;0) , L = 14 нәтиже болып табылады.