Дискреттік программалау модельдері

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

Дискретті программалау есептеріне бір мысал қ арастырайық.

Мысал. Формасы параллелипипед болып келетін бактың сиымдылығ ы максимальды болатындай, табанының ені (a) жә не ұ зындығ ы (b), сонымен қ атар биіктігінің (h) ұ зындық тарын табу керек.

Бак жасауғ а, ені: a = 4, 25; 5, 5 жә не 6, 75 м, материалдарды қ олдану ұ сынылды. Материалдардың бағ асы: С = kS =100 мың тең ге, мұ ндағ ы k – 1 м² материалдың бағ асы k =10 мың тең ге, S – бак жасауғ а кеткен материал, м².

Есептің математикалық моделін қ ұ рамыз. Бактың кө лемі:

V = abh, м³.

Бак жасауғ а керекті материалдың ауданы:

S = 2 (ab) + 2 (a +b) h = 2 (ab + (a + b) h), осыдан аламыз

С = kS = 2 k (ab + (a + b) h).

Осындай ә рекеттерден кейін есептің оң тайластыру моделін қ ұ рамыз:

V = abh → max

Берілген материалдардан жасалғ ан максимальды сиымды бактың қ ұ ны берілген бағ адан (С_бер) кө п болмауғ а тиіс:

2 k (ab + (a + b) h) ≤ С_бер,

a, b, h ≥ 0 жә не a 4.25; 5.5; 6.75.

Есептің шарты бойынша бактың бағ асы С_бер =100 жә не k = =10 мың тең ге екенін ескерсек, онда бірінші тең сіздікті былай жазуғ а болады:

2∙ 10 (ab + (a + b) h) ≤ 100 немесе ab + (a + b) ≤ 5 (a)

Осыдан кейін бульдік айнымалылар арқ ылы математикалық модель мына тү рде жазылады:

a = 4, 25δ ₁ + 5, 5 δ ₂ + 6, 75 δ ₃ немесе

a - 4, 25δ ₁ - 5, 5 δ ₂ - 6, 75 δ ₃ = 0 (б)

δ ₁ + δ ₂ + δ ₃ =1 (в)

0 ≤ δ _j ≤ 1, j = 1, 2, 3.

δ _j – бү тін, j = 1, 2, 3.

Сонымен сызық ты емес оң тайластыру моделі қ ұ рылды. Есепті MS Excel–де шығ арамыз. Жұ мыс бетіне барлық деректерді жазып, кестелік модель тұ рғ ызамыз. Ол ү шін B2: G2 аралық та мә ндері ізделініп отырғ ан (бульдіктермен қ оса) айнымалылардың белгілері, E4: G4; E5: G5 жә не E6: G6 аралық тарда бульдік айнымалылардың тө менгі жә не жоғ ары мә ндері, сонымен қ оса олардың бү тін сандар болу шарттары жазылды (2.14–сурет).

2.14-сурет

Жоғ арыда сызық ты емес программалау есебінің математи-калық моделі қ ұ рылғ аны аталды. MS Excel кө мегімен сызық ты емес программалау есебін шығ ару тә сілінде сызық ты програм-малау есебіне қ арағ анда мынадай ө згешеліктер бар:

– барлық ізделінетін айнымалыларғ а бастапқ ы мә ндер тағ айындалынады;

– Поиск решения –ның Параметры –де Линейная мо-дель –ді іске қ осудың қ ажеті жоқ.

Бірінші талапты қ амтамасыздандыру мақ сатында B3: G3 аралық қ а 1 жазамыз (2.14-сурет).

H9 ұ яғ а мақ сат функция формуласы: =B3*C3*D3, сонымен қ атар H10, H11 жә не H12 ұ яларында, сә йкесінше (а), (б) жә не (в) шектеулер формулаларының сол жағ ы: =B3*C3+(B3+C3);

=СУММПРОИЗВ (E11: G11; $E$3: $G$3) +B3 жә не

=СУММПРОИЗВ(E12: G12; $E$3: $G$3) жазылады.

Поиск решения қ ұ ралында мақ сат функция ұ ясының адресін жә не бағ ытын, айнымалылар ұ яларының аралығ ын жә не шектеулерді енгізгеннен кейінгі сұ хбаттасу терезесінің бейнесі 2.15-суреттегідей болады.

2.15-сурет

2.16-сурет

Сызық ты емес программалау есебін шығ ару тә сілінің екінші талабы бойынша Парамер -дің сұ хбаттасу терезесі 2.16-сурет-тегідей қ алыпта қ алады.

Выпонить батырмасын басқ аннан кейін есептің шешімін аламыз (2.17-сурет).

2.17-сурет

Алынғ ан шешімнен параллелипипед формалы бактың а қ абырғ асы тең 4, 25 м (a = 4, 25 м), ал қ алғ ан қ абырғ аларының ұ зындық тары бірдей жә не тең: b=h= 0, 55 м. Анық талғ ан қ абыр-ғ аларының оң тайлы ұ зындық тарында бактың сиымдылығ ы максимальды жә не тең: V= 1, 2966 м³.

Бактың а қ абырғ асының ұ зындығ ы (4, 25, 5, 5 жә не 6, 75 м) берілген жә не математикалық модельде олар туралы қ осымша шектеулер қ арастырылғ андық тан, табылғ ан бактың сиымдылығ ы, есепті қ осымша шектеусіз шығ арғ ан сиымдық тан азаяды.

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

Дискретті программалау есептерін шығ ару барысында тек нә тиже бойынша есеп (Отчет по результатам) алынады. Онда ешқ андай да жаң а деректер болмайды, сондық тан оны талдау қ ажетсіз. Нұ сқ алық талдау қ алай жү ргізілетініне тоқ талсақ, олда сызық ты емес программалау есептерінде қ олданылғ ан тә сілдер арқ ылы жү ргізілетінін байқ аймыз. Дискреттік программалау есеп-терін шығ арғ анда параметрлік талдау біраз қ ызық ты. Мысалғ а, 2.18-суретте қ арастырылып отырғ ан есептің ізделіп отырғ ан пара-метрлері (бактың қ абырғ аларының ұ зындығ ы) ү здіксіз (есепті бульдік айнымалыларысыз шешу) жә не ү здікті (яғ ни дискретті программалау есебі қ ұ рылып, бірнеше мә ндердің ішінен бір мә нді, бульдік айнымалылары арқ ылы таң дау) болғ ан жағ дайда нә тиже-лерді салыстырыу ү шін сценария кестесі келтірілген.

2.18-сурет

Ескерту: параметрлік талдауда жасалынғ ан жұ мыстар жоғ арғ ы бө лімде жан-жақ ты баяндалуына байланысты, 2.18-суреттегі қ орытынды сценарияны қ алыптастыру жолына терең тоқ талмаймыз.

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

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