Симплекстік түрлендіру
жүктеу/скачать 20,36 Kb.
|
|
Симплекстік түрлендіру Мәселені шешу теріс симплекс айырмашылықтары жойылғанға дейін бір тірек жоспарынан екіншісіне ауысудан тұрады. Бұл ауысу Джордан-Гаусс түрлендірулері арқылы жүзеге асырылады. Бұл ретте симплекс-айырмашылықтар жолы басқа жолдар сияқты ережелер бойынша қайта есептеледі. Мүмкіндік-шешуші элементті таңдау әдісі. Рұқсат етілген баған ретінде теріс симплекс айырмашылығы бар баған таңдалады(бұл 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 Шешім. Кестеге жазайық
Рұқсат етуші элемент ретінде a24=1 алыңыз, өйткені min{12/1 и 20/1}=12. Джордан-Гаусс әдісімен барлық элементтерді түрлендіре отырып, біз келесі кестені аламыз: Рұқсат етуші элемент ретінде a35=1алыңыз. біз кесте аламыз: Анықтамалық шешім: X = (0,0,2,12,6)
Алынған анықтамалық шешім үшін бірінші симплекс кестесін құрайық:
Соңғы жолда теріс сан бар алынған тірек жоспары оңтайлы емес. (-)бағандағы симплекс жолындағы сан 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 негізге енеді дегенді білдіреді. Симплекс түрлендірулер жаңа тірек жоспарын береді:
Сызықтық пішін өсті (L=12), Бірақ алынған жоспар әлі оңтайлы емес. Теріс симплекс айырмашылығы бар. Жаңа рұқсат элементін таңдаңыз a23 =1/2. Жасанды X5 айнымалысы негізден шықты5 бағанын қарастырудан алып тастауға болады. Симплекс түрлендірулер жаңа тірек жоспарын береді: Симплекс-жол-оң. Алынған жоспар оңтайлы. X = (1;0;4;0) , L = 14 нәтиже болып табылады.
жүктеу/скачать 20,36 Kb. Достарыңызбен бөлісу:
|