Бұтақ және шекара әдісі туралы қысқаша түсінік

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

Сонымен, сызық ты программалау есептеріне қ арағ анда бү тін санды программалау есептерін шешу алгоритмдерін компьютермен орындағ ан кезде біраз қ иындық тар кездеседі. Осы қ иындық тарды шешумен бү гінгі кү нге дейін кө птеген жас зерттеушілер айна-ласуда. Олар бү тін санды есептерді шығ аруғ а біраз ә дістерді жасап та тастады. Солардың ішінде компьютер тілінде орындауғ а ә жептә уір қ ызық ты жә не ың ғ айлы алгоритм, ол “Бұ тақ жә не шекара” ә дісінің алгоритмі. Бұ л ә дістің алгоритмін ұ сынғ ан А. Лэнд жә не А. Дайг.

Қ арастырылып отырғ ан ә дістің негізгі идеясы – іздеп отырғ ан шешімді тапқ анынша бастапқ ы кө птікті бірінен кейін бірін, бірнеше ішкі кө птікке, яғ ни бұ тақ тан бұ тақ қ а бө ліп, жаң а есептер қ ұ рылады да, олардың шешімдерін, яғ ни барлық ішкі кө птіктерде шешімдерді іздейді.

Оң тайлы бү тін санды шешімі табылғ ан кө птік бұ тақ тарғ а бө лінбейді, оғ ан ақ ырғ ы немесе ілініп тұ рғ ан бұ тақ тың ұ шының тө бесі сә йкес келеді.

Бұ л ә діспен есепті шығ ару ү рдісі, Гомори ә дісіндегі кесіп тастайтын жазық тар сияқ ты ү здіксіз сызық ты программалау есебін шығ арудан басталады.

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

Шешімі. Бұ йымдардың оң тайлы ө ндіру санын, сә йкесінше x ₁ жә не x ₂ деп белгілеп, есептің математикалық моделін қ ұ рамыз (1 -ші есеп):

Z = 7 x ₁ + 3 x ₂ ® max

5 х ₁ + 2 х ₂ £ 20,

8 х ₁ + 4 х ₂ £ 38,

x ₁³ 0, x ₂ ³ 0 жә не x ₁, x ₂ – бү тін сандар.

Ізделініп отырғ ан айнымалылардың мә ні бү тін сан болу шарттын алып тастап, кә дімгі симплекс ә дісімен оң тайлы шешімді табылды: х ₁

Шешімде х ₂

x ₂≤ 7 жә не x ₂≥ 8

Нә тижесінде, 2 -ші есеп.

Z = 7 x ₁ + 3 x ₂ ® max

5 х ₁ + 2 х ₂ £ 20

8 х ₁ + 4 х ₂ £ 38

х ₂ £ 7

x ₁³ 0 жә не х ₂³ 0.

Симплекс ә дісімен шығ ару нә тижесінде: х ₁

Ә рі қ арай х ₁

Z = 7 x ₁ + 3 x ₂ ® max

5 х ₁ + 2 х ₂ £ 20

8 х ₁ + 4 х ₂ £ 38

х ₂ ³ 8

x ₁³ 0 жә не х ₂³ 0

Симплекс ә дісімен шығ ару нә тижесінде: х ₁

Шешімде х

4-ші есеп. Z = 7 x ₁ + 3 x ₂ ® max

5 х ₁ + 2 х ₂ £ 20,

8 х ₁ + 4 х ₂ £ 38,

х ₁ £ 1 жә не х ₂ £ 7,

x ₁³ 0 жә не х ₂³ 0.

Симплекс ә дісімен шығ ару нә тижесінде: х ₁

5-ші есеп. Z = 7 x ₁ + 3 x ₂ ® max

5 х ₁ + 2 х ₂ £ 20,

8 х ₁ + 4 х ₂ £ 38,

х ₁ ≥ 2 жә не х ₂ £ 7,

x ₁³ 0 жә не х ₂³ 0.

Симплекс ә дісімен шығ ару нә тижесінде: х ₁

Сонымен, жоғ арыдағ ы есептердің шешімі бойынша 2.1-кестені тұ рғ ызайық.

2.1-кесте

Кестеден кө ріп отырмыз, 4-ші есептің шешімі, айнымалы-лардың мә ндері бойынша бү тін санды, бірақ оң тайлы емес. Ө йткені мақ сат функцияның мә нін ә лі де болса жоғ арылататындай бү тін-сандылық шешім бар. Ондай шешімді 5-ші есептен алдық жә не ол шешім оң тайлы.

Айнымалылар мә ндері бү тін санды болу шарты қ арастырыл-мағ ан, «Бұ тақ жә не шекара» ә дісінің алгоритмі бойынша, 1-ші бө лімде келтірілген тә сілмен, жоғ арыдағ ы қ арастырылғ ан ә рбір есептің сызық тық модельдерінің MS Excel кө мегімен алынғ ан шешімдерді MS Excel-де сценарияғ а жазайық. Мысалғ а, 1-ші есептің шешімі алынғ аннан кейін Сервис → Сценарии.. бұ йрығ ын іске қ осамыз. Диспетчер сценариев сұ хбаттасу терезесі ашылады. Добавить батырмасын шертеміз. Название сценария терезесіне сценария атын жазамыз: 1 -есеп (2.1-сурет).

2.1-сурет. «Бұ тақ жә не шекара» ә дісі алгоритмі бойынша бір есептің оң тайлы шешімін табу барысында шығ арылғ ан есептер

Ә рі қ арай келесі кезектегі есептің шарттары бойынша кестелік модельге тү зетулер енгізіп, Поиск решения қ ұ ралымен шешімдерді алғ аннан кейін, оларды сценарияғ а жазу ә рекеттері қ айталанады. Осылай қ ұ рылғ ан, барлық есептердің шешім нә тиже-лері, яғ ни сценария қ ұ рлымы 2.1-суретте келтірілген. Суреттен кө ріп отырмыз, сценария қ ұ рлымы толығ ымен қ олмен қ ұ рылғ ан 2.1-кес-тедегі мә ліметтерді қ айталады. Осы процедуралардан кейін алғ ашқ ы 1-есеп, айнымалылардың бү тінсан болу шарты (ол тура-лы келесі есепте тү сініктеме беріледі) бойынша, MS Excel-де Поиск решения қ ұ ралында қ арастырылғ ан «Бұ тақ жә не шекара» ә дісімен қ айта шығ арылды. Есептің шешім нә тижесі 2.2-суретте келтірілген. Онда жоғ арыда жеке-жеке шешілген ә рбір есептер «автоматты» тү рде бірге қ арастырылып, есеп бірден шешілді, яғ ни ешқ андай қ иындық сыз оң тайлы шешімді алдық.

2.2-сурет. «Бұ тақ жә не шекара» ә дісімен бірден анық талғ ан оң тайлы шешім

Сонымен берілген есепті шешу нә тижесінен “Бұ тақ жә не шекара” ә дісі бү тін санды оң тайлы шешімді қ амтамасыз ететініне жә не осы ә діс компьютерде жең іл орындалынатынына кө з жеткіздік. Ең бастысы, осы ә дісті тә жірибеде қ олдану нә тижесінде, бө лшек мә нді шешімге жай қ арапайым «дө ң гелектеу» ережесін қ олдану, бү тінсанды оң тайлы шешім алуды қ амтамасыздандыра алмайды деп қ ортынды жасалынды.

2.1.2 Бү тін санды модельдерді MS Excel кө мегімен

шешу алгоритмі

Шартты ү здіксіз сызық ты модельдерден қ ұ ралатын есептер симплекс ә дісімен, симплекс кестелерін қ ұ ру арқ ылы шешілетіні жә не осы ә дістің алгоритмі кө птеген пакеттерде компьютер тіліне ө ткізіліп, программалар қ ұ рылғ аны белгілі. Осы ә дістің, «Ә рекет-терді зерттеу» [1], «Математикалық программалау» [16], «Эконо-микалық -математикалық ә дістер» [15] жә не «Менеджментте мате-матикалық ә дістер» [12] пә ндерінде баяндалғ ан теориясынан, ә рбір қ адамда кезекті жақ сартылғ ан симплекс кесте қ ұ рылатыны жә не осы кесте бойынша нақ тылы қ арастырылатын белгілер негізінде мынадай сұ рақ тарғ а: есепте мү мкін бола алатындай шешім барма жә не алынғ ан кестедегі мә ндер есептің шешімі бола ала ма? жә не ол оң тайлы ма?, жауап алынатыны айтылғ ан. Есептің шешімі бар болса, онда аталғ ан сұ ақ тарғ а жауап беретін белгі (ереже бойынша қ арастырылатын белгілердің біреу орындалса, онда алынғ ан шешім мү мкін бола алатыны, ал егер екеуі де орындалса шешім оң тайлы делінеді) табылғ анша қ айта-қ айта жаң а сиплекс кестесі тұ рғ ызыла береді. Бү тін санды есептерді шешкенде мұ ндай белгілер қ арастырылмайды, сондық тан кезекті алынғ ан нә тиже бойынша есептің мү мкін бола алатын шешімі алынғ анына жә не шешімнің оң тайлығ ына жауап алынбайды. Міне осындай қ иындық тарғ а қ арамастан, бү тін санды модельді «Бұ тақ жә не шекара» ә дісі бойынша шешу қ арастырылғ ан MS Excel қ ұ ралы оң тайлы шешімді нақ тылы дұ рыс анық тайды.

Бү тін санды модельдерді MS Excel кө мегімен шешу бары-сында жасалынатын жұ мыстардың реті 1-ші бө лімде баяндалғ ан сызық ты модельдерді шешу технологиясымен бірдей. Сонымен қ атар есепті шығ ару барысында, айнымалылар ү здіксіз жә не бү тін санды болғ ан жағ дайда олардың нә тижелерінің дә лдігін бағ алау ү шін есептің шешімдерін салыстыруғ а болады.

Бү тін санды модельді MS Excel кө мегімен шешу технология-сының кейбір ерекшеліктерін мынадай мысал арқ ылы қ арасты-райық.

Тө рт тү рлі бұ йымдарды: A, B, C жә не D даярлауғ а ү ш тү рлі қ ор: ең бек, шикі зат жә не қ аржы қ ажет, оларды қ анша данадан шығ ару керектігін анық тайық. Бұ йымдардың бір данасына есептелінген қ орлардың шығ ындары жә не бір дана бұ йымдардан тү сетін пайда 2.2-кестеде берілген.

2.2-кесте. Есептің алғ ашқ ы деректері

Математикалық модель қ ұ рамыз, ол ү шін мынадай белгілерді қ абылдаймыз:

x _j – ө ндірілетін j – тү рлі ө німнің оң тайлы саны,

b _i – i – ші қ ордың шаруашылық та бар мө лшері,

a _ij – i – ші қ ордың j –шы ө німнің бір данасын ө ндіруге керекті мө лшері;

c _j – j – шы ө німнің бір данасынан алынатын пайда.

Осыдан есептің математикалық моделі мына тү рде жазылады:

(2.2)

x_j ≥ 0, j = 1, 2, 3, 4 x_j – бү тін сандар, j = 1,..4.

MS Excel –дің жұ мыс бетіне кестелік модельді қ ұ рамыз. Ол ү шін мынадай іс-ә рекеттер жү ргізіледі:

1. Кестелік модельге керекті комментарияларды арнайы ұ яларғ а (2.3-сурет) енгіземіз. Бұ л ұ ялардағ ы жазулар қ арастырылып отырғ ан есептің шешіміне ешқ андай да ә сер жасамайтынын тағ ы да ескерте кетейік.

2. B6: E6 аралық тағ ы ұ яларғ амақ сат функция коэффи-циенттерін енгіземіз: с₁ = 60, с₂ = 70, с₃ = 120, с₄ = 130.

3. F6 ұ яғ а мақ сат функция формуласын енгіземіз: =СУММПРОИЗВ(B4: E4; B6: E6).

4. B9: E11 аралық тағ ы ұ яларғ а шектеулердің коэффициент-терін енгіземіз.

5. H9: H11 аралық тағ ы ұ яларғ а шектеулердің оң жағ ын: b₁ = = 40, b₂ = 75, b₃ = 120 енгіземіз.

6. F9 ұ яғ а бірінші шектеудің сол жағ ының формуласын жазамыз: =СУММПРОИЗВ($B$4: $E$4; B9: E9).

7. F9 ұ ядағ ы формуланы F10 жә не F11 ұ яларғ а белгілі ә діспенкө шіреміз.

8. I 9ұ ясынашектеудің оң жақ бө лігімен сол жағ ының айырмашылығ ынбілдіретінформуланы: =I9 – F9 жазамыз.

9. I 9ұ ядағ ы формуланы, I 10жә н е I 11ұ яларғ а кө шіреміз.

Сонымен Excel-дің жұ мыс бетінде қ арастырылып отырғ ан есептің кестелік моделінің сыртқ ы пішіні 2.3-суретте кө рсетілген.

Есепті ә рі қ арай шешу ү шін Поиск решения шақ ырылады. Ол ү шін бас менюдан: Сервис Þ Поиск решения...

Сұ хбаттасу терезесінде Поиск решения пайда болғ аннан кейін тө менгідей іс-ә рекеттер орындалынады:

2.3-сурет. Бү тін санды есептің кестелік моделі

1. Установить целевую ячейку жолына мақ саттық ұ яның абсолюттік $F$6 адресін кө рсетеміз, яғ ни курсорды мақ сат функция формуласы жазылғ ан ұ яғ а орналастырамыз.

2. Равной: тобы ү шін, максимальному значению – нұ сқ асын іздеуді таң даймыз.

3. Изменяя ячейки жолынамә ндері ізделінетін айнымалы-лардың абсолюттік $B$4: $E$4 адрестерін енгіземіз.

4. Келесі кезекте шектеулерді, айнымалылардың тө менгі жә не жоғ арғ ы шектерін, теріс болмау жә не бү тін санды болу шарттарын енгіземіз. Осы мақ саттарғ а жету ү шін келесідей іс-ә рекеттер орындалынады:

· шектеулерді енгізу ү шін Поиск решения- ның алғ ашқ ы сұ хбаттасу терезесіндегі Добавить батырмасын басамыз (2.4-сурет );

· қ осымша пайда болғ ан сұ хбаттасу терезеде Ссылка на ячейку: жазуының астындағ ы терезеге $F$9: $F$11 ұ ялар аралығ ыбейнеленеді;

· шектеулердің жиналып тұ рғ ан белгілері тізімдерінің ішінен кестелік модельде кө рсетілген белгіні “< =” таң даймыз;

· Ограничение: жазуының астындағ ы терезеге $H$9: $H$11 аралық тарында тұ рғ анұ ялардағ ы шектеулердің оң жақ тары енгізіледі;

· шектеулерге қ осымша шарттарды енгізу ү шін осы қ о-сымша сұ хбаттасу терезесіндегі Добавить батырмасын іске қ осамыз (2.5-сурет).

2.4-сурет. Поиск решения –ның сұ хбаттасу терезесі (барлық

шектеулер енгізілгеннен кейінгі бейне)

5. Шектеулер қ атарына айнымалылардың мә ндері олардан кем болуы мү мкін еместігін білдіретін тө менгі шекара шектеулерін жә не бү тін сан болу шарттарын енгіземіз. Осы мақ сат ү шін келесі іс-ә рекеттер орындалынады:

· қ осымша сұ хбаттасу Добавление ограничения терезесіне айнымалыларың тө менгі шекара шектеулерін екі нұ сқ ада енгізуге болады: біріншісінде, Ссылка на ячейку жазуы астындағ ы терезеге бірден ұ ялардың адрес аралығ ын, мысалғ а, біздің жағ дайда $B$4: $E$4, немесе екінші нұ сқ ада ә рбір айнымалыны жеке-жеке B4, C4, D4, E4 енгіземіз;

· тү сіп кеткен, кө рінбей тұ рғ ан белгілер тізімінен кем емес “≥ ” белгісін таң даймыз;

· айнымалылардың тө менгі шекара шектеулерінің мә ндері тұ рғ ан бірінші нұ сқ ада Ограничение жазуы астындағ ы терезеге бірден ұ ялардың адрес аралығ ын, біздің мысалда $B$5: $E$5, немесе екіншісінде, ә рбір мә ндерді жеке-жеке B5, C5, D5, E5 енгіземіз;

· қ осымша сұ хбаттасу Добавление ограничения терезе-сіндегі Ссылка на ячейку жазуы астындағ ы терезеге айнымалылар мә ндері алынатын ұ ялар аралығ ын $B$4: $E$4 жазамыз;

· тү сіп кеткен, кө рінбей тұ рғ ан белгілер тізімінен, бү тін сан шартын білдіретін “ цел ” жазуын таң даймыз;

· шектеулердің оң жақ тарының мә ндері тұ рғ ан ұ ялардың адрестерін кө рсетуге арналғ ан Ограничение жазуы астындағ ы терезені сол қ алпында қ алдырамыз, онда Поиск решения «автоматты» тү рде «целое» деп жазады (2.5-сурет);

· соң ғ ы шектеуді енгізу ү шін ОК батырмасын басамыз.

2.5-сурет. Добавление ограничения- қ осымша сұ хбаттасу терезесі

(соң ғ ы ә рекет кезең і)

6. Поиск решения → Параметрлер арқ ылы қ осымша сұ хбаттасу терезесінен Линейная модель, Неотрицательные значения жә не Автоматическое масштабирование жазуларын белгілейміз (2.6-сурет).

2.6-сурет. Поиск решения параметрлері

7. Жоғ арыдағ ы ә рекеттерді тиянақ ты орындағ аннан кейін есепті шешуге кө шеміз. Ол ү шін Выполнить батырмасын іске қ осамыз. Оң тайластыру ү рдісі орындалғ аннан кейін сұ хбаттасу терезесі Результаты поиска решения ашылады (2.7-сурет).

2.7-сурет.

2.8-сурет. Есептің оң тайлы шешімінің нә тижелері

8. Сохранить найденное решение жазуынбелгілейміз де, ОК батырмасын шертеміз.Программа MS Excel – де есептеуді аяқ тағ аннан кейін, есептің 2.8-суретте кө рсетілген нә тижесін сандық жә не графикалық тү рде аламыз.

Есептің шешім нә тижесінде ізделініп отырғ ан айнымалы-лардың оң тайлы мә ндері анық талынды: х ₁ = 5; х ₂ = 2; х ₃ = 5; х ₄ = 4, оларғ а мақ сат функция мә не z =1560 а.б. сә йкес келеді.

Есептің шешімін талдау нә тижесінде, егер бұ йымдар мынадай қ атынаста: А→ 5 дана, В→ 2 дана, С→ 5 дана жә не D→ 4 дана ө ндірілетін болса, онда максималды пайда табу қ амтамасыз етілетіні анық талды. Сонымен қ атар, шаруашылық тағ ы ең бек жә не қ аржы қ орлары тү гелдей қ олданылатыны жә не 3 ө.б. шикізат қ оры қ олданылмай қ алатыны белгілі болды. Сө йтіп, шаруашылық та шикізат қ оры 3 ө.б. артық мө лшерде екені, оны басқ а мақ сат ү шін немесе сыртқ а сатуғ а болатындығ ы жө нінде шешім қ абылданды.

Бү тін сандық жә не ү здіксіз шешімдер нә тижелерін салысты-ру ү шін, айнымалылардың бү тін санды болу шартын алып тастап, қ арастырылып отырғ ан есеп, Поиск решения қ ұ ралымен қ айта шығ арылды. Шешім нә тижелері бойынша 2.3-кестені тұ рғ ыздық.

2.3-кесте

Ескерту: S₁, S₂ жә не S₃ белгілері, сә йкесінше ең бек, шикізат жә не қ аржы қ орларының қ олданбай қ алғ ан мө лшерлерін кө рсетеді.

Кестеден мыналар туындалды:

î ү здіксіз шешімдеө ндірілетін С(х ₃) жә не D(х ₄) бұ йымдар-дың мә ндері кө п ө згеріске ұ шырады. Біріншіден, олар бө лшек сандар, екіншіден, алынғ ан бө лшек сандарды жай қ арапайым «дө ң гелектеу» арқ ылы бү тін сандарғ а айналдырсақ: х ₃=6, 71≈ 7 жә не х ₄=2, 71≈ 3 жү йедегі шектеулер шарттары бұ зылады (42> 40, 77> 75 жә не 124> 120). Сө йтіп, бү тін сандық шешім алу ү шін жай қ арапайым «дө ң гелектеу» тә сілін қ олдануғ а мү лдем болмайды;

î ү здіксіз жә не бү тін сандық шешімдерде мақ сат функция бір-біріне ө те жақ ын. Дегенмен де, басқ а да шарттар сияқ ты бү тін сандық шарт мақ сат функция мә нін тө мендетеді (1598, 57– 1560 = =38, 57);

î ү здіксіз шешімде қ аржы қ оры 1, 71 ө.б. қ олданбай қ алатыны анық талса, ал бү тін сандық шешімде керісінше шикізат қ оры 3 ө.б. артық. Демек, есептің алғ ашқ ы мә ліметтері бірдей болғ анымен, айнымалылардың бү тін санды болу шарты оның нә тижесін айтарлық тай ө згеріске ә келетініне кө з жеткіземіз.