Бүтін санды бағдарламалау есептері. Гомори әдісі. Кесіп тастау әдісі



Дата17.12.2020
өлшемі21.25 Kb.

Бүтін санды бағдарламалау есептері. Гомори әдісі. Кесіп тастау әдісі.

Оңтайластыру модельдерін шешу нәтижесінде мәндері ізде-лініп отырған айнымалылар міндетті түрде бүтінсандар болуға тиіс болса, онда мұндай модельдерді бүтін санды программалау мо-дельдері деп атаған. Бүтін сандық шешім тек сызықтық програм-малау есебіне келтірілген кейбір есептерге ғана тән талап емес, шешімнің бүтін санды болуы кейде сызықты емес программалау есептерінде де кездеседі. Сондықтан, егер шектеулер және мақсат функциясы сызықты байланыста болса, онда мұндай есепті сызық-тық программалаудың бүтін санды есебі деп атайды; егер кемінде бір байланыс сызықты емес болса, онда мұндай есепті сызықты емес программалаудың бүтін санды есебі деп атайды.

Халық шаруашылығы есептерінің көбісінде бүтін санды бел-гісіздер кездеседі. Сөзсіз, мұндай сандар физикалық түрде бөлін-бейді, себебі, екі жарым жаңа кәсіпорнын ұйымдастыруға, бір жарым автокөлік сатыпалуға, қырық жарым мал бордақылауға, он жарым жұмыскерді жұмысқа қабылдауға және т.б. болмайды. Сөйтіп, сызықтық программалау есептеріне ұқсас көптеген халық шаруашылық есептеріне бүтін санды шешім қажет. Мысалға, мал табынының тиімді айналымы, ауылшаруашылық техникаларын әр түрлі жұмыстарға бекіту, өндіріс орындарының өндіретін бұйым-дарының тиімді санын анықтау және т.б.с.с.

Бүтін санды программалау есебінің пайда болуын Данциг-тың, Фулкерсонның және Джонсонның “Кесіп тастау” әдісінің идеясымен байланыстырады. Бірақ бүтін санды программалау есебінің бүгінгі дамуы, кесіп тастау идеясын іс жүзіне асыру үшін жасалған Гомори ұсынған бірінші алгоритм пайда болуынан кейін басталды. Бұл әдіс кейіннен Гоморидің атымен, Гомори әдісі деп аталынды. Сонымен, бүтін санды модельдерді шешу әдістерін күрделенген оңтайластыру әдістерінің қатарына жатқызуға болады.

Бүтін санды модельдерді шешу әдістерінің ерекшеліктеріне тоқталайық.

Бүтін санды модельдер сыныбына, айнымалылары теріс емес тек бүтін мәндер қабылдайтын, мақсат функция өзінің аргумент-терімен сызықты байланыста болатын және шектеулерінің сол жағы сызықты теңсіздік немесе теңдік түрінде берілген, бір крите-риялды оңтайластыру есептері жатады. Сонымен қатар айнымалы-лар шамаларына, келесі тақырыптарда қарастырылатын бульдік айнымалыларға қойылатын шектеулер сияқты, қосымша шектеулер қойылмайды Бүтін санды сызықты программалау есебінің жалпы математикалық қойылуын қарастырсақ, осы сынып есептері туралы нақтылы анықтама түсінікті бола бастайды. Демек, жоғарыда кел-тірген анықтама негізінде бүтінсанды сызықты программалау есебінің математикалық моделін мына түрде өрнектеуге болады:





 (2.1)



xj ≥ 0, j = 1,...n, xj – бүтін сандар, j = 1,..k.

Келтірілген (2.1) жүйенің байланыстарына қарасақ, оның сызықты программалау және оған ұқсас есептерден ешқандайда айырмашылығы жоқ екенін байқаймыз. Дегенмен де, жалғызғана айырмашылық бар. Ол есептің шешімін күрделіндіретін және оған үлкен әсер ететін, мына: xj – бүтін сандар, j = 1,..k шарты. Бүтін сандар саны k төменгі екі нұсқаның біреуін қанағаттандыруға тиіс.

Егер k = n, мұндағы айнымалылардың жалпы саны, онда барлық айнымалылар мәні тек бүтін сан болуға тиіс; мұндай жағдайда есеп толық бүтін санды деп аталады. Егер k < n, яғни тек дейінгі айнымалылар бүтін санды, ал қалғандары өздерінің шеткі шекаралықтарына дейін кез келген мән қабылдай алатын болса, онда мұндай есептерді жарым-жартылай бүтін санды деп атайды. Осы жерде, толық бүтін санды есептерді шешу үшін барлық бүтін санды айнымалылар жоғары жағынан міндетті түрде шектеулі болу керектігін атап өтейік.

Есеп-1


Көлемі 20 мың ө.б. (өлшем бірлігі) А және көлемі 38 мың ө.б. Б шикі заттарынан екі түрлі бұйымдар жасалмақшы. Нарықта бірінші бұйымның бір данасын 7 мың теңгеге, ал екінші бұйымның бір данасын 3 мың теңгеге өткізуге болады. Әрбір бұйымның бір данасына, сәйкесінше: А шикі заттынан – (5 және 2) мың ө.б., Б шикі заттынан – (8 және 4) мың ө.б. мөлшерде жұмсалынуға тиісті. Жасалған бұйымдарды нарыққа өткізу арқылы максимальды табыс алу үшін, өндіріс орынына оларды қанша данадан өндірген тиімді.

Достарыңызбен бөлісу:


©netrefs.ru 2019
әкімшілігінің қараңыз

    Басты бет