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

Дискреттік программалау есебінің типтері

Көптеген өндірістік есебі басқарылатын ресурстардың көлемі (осы және басқа да объективті қасиеттер бойынша) тек бүтін мәндер қабылдай алатындығымен сипатталады. Берілген жағдайдың математикалық құрылымы дискретті программалау моделіне алып келеді. Дискретті программалау есебі жалпы түрде шектеулер жүйесімен анықталатын жиындағы мақсат функцияның ең үлкенін (ең кішісі) табу есебі ретінде құрылуы мүмкін.

Айнымалылардың кейбір соңғы немесе саналымды жиынға жату шарты дискреттілік шарты деп аталады. Дискретті есептердің арасында ерекше орынды канондық түрдегі сызықты программалаудың бүтін санды есебі (КСПБЕ) аалады.

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

Пайда болған мәселелер дискретті және бүтін санды есептерді шешудің арнайы әдістерін өңдеу қажеттілігін анықтап берді. Дискретті програмалау есебін жіктеуге тоқталайық. Әдебиетте дискретті оңтайландыру есептерінің келесі кластары ерекшеленеді:

бөлінбейтін есептер (ранц туралы есеп);

экстремалды комбинаторлық есептер (коммовояжер туралы есеп);

резервті бүтін функциялы есеп (белгіленген төлемді транспорттық есеп);

байланыспаған және дөңес емес аймақтардағы есептер және т.б

Гомори әдісі

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

табылған бүрін санды емес оңтайлы жоспар жаңа қосылған шекетеулереді қанағатандырмайтын;

үздіксіз есептің кез-келген бүтін санды жоспары қайта толықтырылған шектеулерді қанағаттандыратын шектеулер қосылуы мүмкін:

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

Алгоритмнің сипаттамасы. Гомори алгоритмінің жалпыланған схемасын келтіреміз. Құрылымы бойынша үлкен итерацияларға бөлінеді. Әрбір үлкен итерация келесі этаптардан тұрады:

1. «Ағымды» есепті сызықтық программалау әдісімен шешу (кіші итерация). Бірінші итерацияда «ағымды» есеп ретінде бастапқы СПӘ-нін бүтін санды баламасы кіреді.

2. 1 кезеңде алынған тиімді жоспарда бірінші бүтін емес компонентті анықтау. Егер барлық компоенттер бүтін санды болса, онда алгоритм аяқталады.

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

Екі жақты симплекс әдісі Гомори әдісі үшін негіз болып табылады, өйткені ол жаңа қосымша шектеулерді (дұрыс қима) ескеруге және ағымды псевдо жоспардан жаңа тиімді жоспарға өтуге мүмкіндік береді.

Келтірілген алгоритм соңғы екендігін дәлелдеуге болады. Бұл кейбір қадамда (итерацияда) бүтін санды тиімді жоспар табылатынын және мүмкін бүтінсанды жоспарлардың болмау факті табылғанынбілдіреді.

Гомори әдісі бойынша маңызды ескерту ретінде оны ЭЕМ-де тәжірибелік жүзеге асыру барысында дөңгелектеу қатесін ескеру керектігін қосуға болады, өйткені машиналық арифметика жағдайында бір де бір жоспар бүтін санды болмайды. Сонымен қатар, жинақталғанқателіктер алгоритмге өзгерістер енгізуі және тиімді бүтінсанды жоспардан «алып кетуі» мүмкін.