Сызықтық бағдарламалау есептеріндегі симплекс әдісі

1.

14.Сызықтық бағдарлама есептерін шығару үшін Зуховицкийдің симплекс әдісін
қолдануды сипаттаңыз.
Сызықтық бағдарламалау есептеріндегі симплекс әдісі
Симплекс әдісі каноникада жазылған есепте қолданылады
форма
AX = A0 жүйесінің теңдеулерінің ешқайсысы болмайды деп есептейміз
осы жүйенің қалған теңдеулерінің салдары. Әйтпесе, мұндай
теңдеуді жай алып тастауға болады.
Gx AX = A0 шарттарын қанағаттандыратын X векторларының жиыны болсын,
X≥0. Қарастырылып отырған проблеманың шешімі тек қана болуы мүмкін
жағдай Gx ≠ 0. Бұл n≥m талабына әкеледі. Сонымен қатар, n = m Gx жағдайда
бір X * векторынан тұрады
жалғыз шешімді ұсынады
жүйелер AX = A0. Бұл жағдайда ең көп Z (X) табу мәселесі шешіледі
тривиальды: ең көп Z (X) = CX *
, X Gx.
Одан әрі n> m деп қабылдаймыз. Сонымен қатар, біз түрлендіреміз
AX = A0 жүйесі, оның оң жақтары теріс емес болатындай, яғни. Біз істейміз
A0≥0 деп есептейміз.Жүйе туралы
AX = A0, A0≥0, (7)
осындай түрлендірулер нәтижесінде алынған, олар рұқсат етілген дейді
жол-жол.
Симплекс әдісін қолдануға рұқсат етілген жүйеге қолданудың алғашқы қадамы
сызықтар, бұл кез келген m айнымалыға қатысты ажыратымдылығы.
Бұл жағдайда жаңа жүйенің де болып шығуын қамтамасыз ету қажет
жолдан-жолға жарамды. Барлық мүмкін жағдайларды санау арқылы (олардың барлығы
болады)
29
Cn

2.

м
) жүйені (7) түрлендіруден кейін Джордан-Гаусс әдісімен, әрқашан
сіз мұндай рұқсатты ала аласыз немесе оның мүмкін еместігін анықтай аласыз.
Осы әдісті еске түсіріңіз:
(7) -ді xk-ге қатысты шешу үшін x-ті l-шіден өрнектейміз
осы жүйенің теңдеулерін және алынған өрнекті бәрінде ұсынады
жүйенің басқа теңдеулері (7). Бұл процесс xk ерекше жағдай деп аталады.
Содан кейін, дәл осылай, бізде xk жоқ түрлендіру жүзеге асырылады
саны (n - 1) -ге тең қалған теңдеулер - біз оларды алып тастаймыз
кейбір басқа координаттар, мысалы, xk
*
және т.б.
Мұндай алып тастаулардан кейін рұқсат етілген жүйе алынады
таңдалған m айнымалыларға қатысты, олар негізгі деп аталады.
Осындай жүйені рұқсат етілген деп атайық. Қалған n-m айнымалылар
тегін деп аталады.
Негізгі айнымалыларды ерікті түрде таңдағаннан кейін пайда болады
жүргізілген түрлендірулер жүйенің қолайсыз болып шығуы мүмкін
сызықтар. Бұған жол бермеу үшін x-ті осындай l-шіден білдіру керек
жүйенің (7) теңдеулері, олар үшін келесі қатынастар орындалады:
оk = = aik үшін ≥0.
Жүйені негізгі айнымалыларға қатысты шешкеннен кейін
оның таңдалған негізге сәйкес шешімі табылды.
Жолдар бойынша рұқсат етілген негізгі шешім, рұқсат етілген канондық
AX = A0, X ,0 жүйесінің X векторы деп аталады, оның координаталары,
негізгі айнымалыларға сәйкес келетін аналогтық координаталарға тең
векторы A0, ал координаталары еркін айнымалыларға сәйкес келеді
нөл.

3.

отыз
Анықтамалық шешімді тапқаннан кейін ол үшін бағаланады
оңтайлылық. Ол үшін k шамалары есептеледі, бағалау деп аталады
қолдау шарты негізінде Ak шарттарының векторын кеңейту:
k=
немесе векторлық белгіде
мұндағы - Cb = (с1, ..., сm) - бұл мақсат функциясының коэффициенттерінің векторы
негізгі айнымалылар;
Xk = (x1k, ..., xmk) - бұл Ақ векторының кеңею коэффициенттерінің векторы
анықтамалық шешімнің негізі:
ck - хк кезіндегі мақсат функциясының коэффициенті.
Сызықтық бағдарламалаудың максималды мәселесін шешуге қолдау көрсету
(минимум) оңтайлы болады, егер шарттардың кез келген векторы үшін оның бағасы
қолдау шешімі негізінде кеңейту теріс емес (позитивті емес),
анау.
есепте максимум k 0 k = 1, 2,…, n;
есепте минимум k 0 k = 1, 2,…, n.
Егер бұл шарттар орындалмаса, онда жаңа негіз таңдалады. Үшін
бұл негізгі координаталардың бірі еркін координаттарға, ал бірі
ақысыз - негізге.
Оған жылдам жуықтау үшін максималды мәселеде
негізгі координаттарда оңтайландырылатын функцияны аудару керек
{- ok k} өнімі қабылданатын бос координаталар туралы
жоғары мән.
31
Оған ең жақын жуықтау үшін минималды есепте
негізгі координаттарда оңтайландырылатын функцияны аудару керек
{- ok k} өнімі қабылданатын бос координаталар туралы

4.

ең кіші мән.
Осы процесті алгоритмдеуді бірге жүргізу ұсынылады
жоғарыда қарастырылған кестелерге ұқсас кестелер құрастыру арқылы
коэффициенттер. Еске салайық, әдісті қолдана отырып, жоғарыда түсіндірілген
Джордан-Гаусс, осы кестелерді жүйені шешуге қолдана отырып (7)
таңдалған негізгі айнымалыларға қатысты. Егер осыдан кейін
шешімділігі, нәтижесінде жүйе жолдан-жолға рұқсат етіледі, содан кейін
симплекс әдісін қолдануға кірісуге болады. Егер оң жағы
алынған кейбір теңдеулер теріс сандар болып шығады,
онда осы теңдеулерді (-1) көбейту арқылы негізгі айнымалыны ауыстыру керек,
осы теңдеулердің әрқайсысына екі жаңа базистің айырмасы бойынша ену
айнымалылар, олардың әрқайсысы тек теріс емес қабылдай алады
құндылықтар. Осыдан кейін болса да, саны көп жаңа жүйе
айнымалылар, бірақ олардың арасында осындай базисті таңдау бірден мүмкін болады
рұқсат етілген жүйе болатын айнымалылар
жолдан-жолға жарамды. Оған симплекс әдісін қолдануға болады.