Бүтін санды модельдер

Тарихи деректер бойынша бү тін санды тең деулерді шешумен ғ алымдар ертеден айналысқ ан. Мысалғ а, Гректік математик Диофант (II–III ғ.ғ.) тең деулердің шешімінде ізделініп отырғ ан белгісіз тек бү тін мә нді болады деп қ арастырғ ан. Бү гінгі ә дебиет-терде бү тінсанды модельдердің негізін 1932 жылы Венгер матема-тигі Е. Эгервари қ алыптастырды делінеді. Ол ә рбір ұ шақ тар жолы-на белгілі бір ұ шақ тарды бекітумен жә не ә ртү рлі жұ мыстарғ а механиктерді бө лумен айналысқ ан.

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

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

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

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

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

(2.1)

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

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

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