Алғашқы базистік жоспарды құру.
Симплекс әдіспен шешілетін есептің шектеулер жүйесі <= таңбасымен теңсіздіктер жүйесінде берілген, оның оң жағы bi>=0. Теңсіздіктер жүйесіне оң қосымша айнымалылар енгізу арқылы теңдеулер жүйесіне көшеміз. Осы айнымалылардың баған векторлары бірлік векторлар болып табылады және базис құрайды, сонымен бірге оларға сәйкес келетін айнымалылар базистік деп аталады:
Мұнда хn+I - базистік айнымалылар, хj- еркін айнымалылар.
Енді симплекс әдісінің орындалу ретін(алгоритмін) кестеде қарастырайық.
1)Симплекс кесте құрамыз. Кесте шектеулер жүйесі коэффициенттерінен және оң жағынан тұрады. Кестенің соңғы жолы индекстік деп аталады және мақсат функциясының қарама – қарсы таңбаларымен алынған коэффициенттерімен толтырылады.
2) Оңтайлылықты тексеру. Индекстік жолда теріс санның бар-жоғын анықтаймыз. Егер теріс сан болмаса, онда табылған негізге алынатын жоспар функцияның максимумына сәйкес оңтайлы шешімі болып табылады. Егер индекстік жолда теріс сандар болса, онда осы кестедегі айнымалылар есептің оңтайлы шешімі емес немесе алгоритмнің келесі кезеңіне көшеміз.
3)Бағыттаушы баған мен жолды анықтау. Бағыттаушы баған мен жолды табамыз. Бағыттаушы баған индекстік жолдың теріс санының барынша көп абсолюттік мөлшері бойынша, ал бағыттаушы жол – бос мүшелер векторы бағанының элементтерін бағыттаушы бағанның оң элементтеріне min(bi/air) қатынастарының барынша аз абсолюттік мөлшерімен анықталады. Бағыттаушы баған мен жол түйіскен жерде бас элемент орналасқан.
|
|
|
4)Жаңа негізге алынатын жоспар кұру. Бағыт беруші жол мен бағанға сәйкес келетін белгісіз айнымалылардың орны ауыстырылады. Мұнда базистік айнымалы еркін айнымалы болады және керісінше. і жолда және j бағанда орналасқан элементтің (Эн) жаңа мәні элементтің (Эс) ескі мәнінен j баған мен бағыттаушы жол (Э1) түйіскен жерде орналасқан Элементті і жол мен бағыттаушы баған түйіскен жерде орналасқан элементке (Э2) көбейтіп, бас элементке (Эг) бөліп алып тастағанға тең болады. Бұл тікбұрыш ережесі деп аталады:
Эн=Эс- 
5)Немесе төмендегі формулалар бойынша:
В1= (ві-(вг/аrk)аіk болса і 
r; br/аrk болса і=r) (5.12)
а'ij= (аij-/аrj/ark)аіk болса і=r; аrj/аrk болса і=r) (5.13)
Ғ'о=Ғо- (bгrаrk) 
k; 
j=А,- (аrі/аrk) k (5.14)
Барлық осы сандар жаңа симплекс кестеде жазылады.
6)Табылған жаңа базистің оңтайлылығын тексеру. Егер жоспар оңтайлы болмай, жаңа оңтайлы жоспарға көшу қажет болса, онда 4) кезеңге қайта оралады, ал оңтайлы жоспар алынған жағдайда, есептің шешімі қабылданады.
|
|
|
Дата добавления: 2015-12-18; просмотров: 1; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!