Бүтінсандық программалау.
Сұрақтар:
1. Бүтін санды программалаудың есебінің экономикалық және геометриялық интерпритациясы
2. Тиімділік әдістерінің анықтамасы, бүтінсанды программалаудың тапсырмалары
Бүтін санды программалаудың есебінің экономикалық және геометриялық интерпритациясы
Тек бүрін санды мән қабылдайтын айнымалылар, бүрін санды программалау есебі деп аталады. Бүрін санды программалау есебінің математикалық моделі, мақсаттық функция сол сияқты шектелген жүйенің функциясы сызықтық, сызықтық емес және аралас бола алады. Мақсаттық функция және шектелген жүйе есебі, сызықтық болып табылуымен шектелеміз.
Мысал. 19/3м3 ауданды кәсіпорын цехнде қосалқы құрылғы қою үшін берілд. Екі түрлі құрылғыны сатып алу үшін кәсіпорын 10мың руб. жұмсай алады. Құрылғының I ші түрінің бір комплекті 1000 руб. Тұрады, ал II түрі 3000 руб. тұрады. Құрылғының I-ші түрінің бір комплекті бірінші ауысым екі бірлікке, ал II түрдің бір комплекі өнімнің шығаруын төрт бірлікке өсіреді. Құрылғының I-ші түрінің орнату үшін 2м2 аудан қажет, ал II-ші түрдің орнату үшін 1м2 аудан қажет екенің біле тұра, қосалқы құрылғының қайсысы өнімнің максималды өсуіне мүмкіндік туғызатының анықтау.
Шешуі. Есептің математикалық моделін құрастырамыз. Кәсіпорын х1 комплект I-ші түрлі және х2 II-ші түрлі құрылғыны алды деп санайық. Онда х1 және х2 айнымалылары келесі теңсіздікті қанағаттандыру керек:
(1)
Егер кәсіпорын көрсетілген мөлшерде құрылғыны алса, онда өнім шығарылымы мынаны құрайды
F=2x1+4x2 (2)
х1 мен х2 өзінің экономикалық кұрамы бойынша тек бүтін және теріс емес мән қабылдай алады, яғни.
(3)
х1 х2 бүтін. (4)
Осылайша келесі математикалық есепке көшеміз: (1),(2) және (4)
шарттары орындалғанда сызықтық (2) функцияның максималды мәнін тап. Белгісіздер бүтін сандар ғана бола алатындықтан (1)-(4) есептер программалаудың бүтін сандар болып табылады. Белгісіздер саны екеу болғандықтан геометриялық интерпритацияны қолданып берілген есептің жауабын табуға болады. Ол үшін ең алдымен көпбұрыш есебінің шешімін қарастырып өту керек, (1)(3) ның шартын орындағанда (2) сызықтық функцияның максимум мәнін анықтаудан тұратын. Құрылған ОАЕВС көпбұрышының кординаттары (1)-ші сызықтық теңсіздік жүйесін және (3)- шы теріс емес айнымалылардың шартын қанағаттандырады. Ал (4)-нің шартын яғни бүтін санды айнымалылардың шартын 6.1. суретте көрсетілгн 12 нүктенің кординаттары ғана қанағаттандырады. Бастапқы есептің шешімін анықтайтын кординатаны табу үшін, ОАВС көпбұрышын OKEMNF қөпбұрышына ауыстырайық, бүтін санды нүктелерінің кординатталары қолайлы болғанда, әрбір төбесінің кординаталары бүтін сан болып табылады.
Сурет 6.1
Егер (2)-ші функцияның және OKEMNF қөпбұрышының максимум нүктесін тапсақ, онда осы нүктенің кординатасы тірек жоспары есбін анықтайды.
Бұл үшін OKEMNF қөпбұрышынан өтетін векторын және 2х1+4х2=12 түзуін қарастырайық (12 саны кездейсоқалынды). Құрылған түзу берілген қөпбұрышпен соңғы нүктеден өткенше дейін векторына қарай созамыз. Осы нүктенің кординатасы тірек жоспарын анықтайды, ал мақсаттық функцияның мәні оның максимумы болып табылады.
Мақсаттық функция мәнін Fmax =14 максимум болатын Е(1;3) нүктесі ізделінеді. Е нүктесінің кординатасы (1)-(4) есебінің тірек жоспарын анықтайды. Осы жоспарға сәйкес кәсіп орын I-ші түрдің бір комплектін және II-ші түрдің үш комплектін алуы керек. Бұл кәсіпорынға өндірістегі шектеулі ауданы мен ақша мүмкіндіктерінен, өндірісті максимум 14 бірлікке арттырады.
2. Тиімділік әдістерінің анықтамасы, бүтінсанды программалаудың тапсырмалары
Мақсатты функция сияқты шектелген жүйеде функциялар сызықтық болғандықтан, бүтінсанды программалаудың тапсырмаларын қарастырамыз. Осыған орай, айнымалылары тек қана бүтін сан бола алатын, сызықтық программалаудың негізгі тапсырмаларын құрастырамыз. Бұл тапсырманы толық түрінде былай жазуға б олады: функцияның максимумын табу керек
(5)
шарттары
, (6)
(7)
xj – бүтін . (8)
Егер (5)-(8) есептердің шығарылуын симплекс әдісімен табатын болсақ, онда ол бүтінсанды болып табылуы мүмкін немесе болмауы да мүмкін. Сызықтық программалаудың негізгі есебіне, есептің шешуі әрқашан бүтінсан болатын жүк тасымалы туралы есеп, мысал бола алады. Толық жағдайда (5)-(8) есептің тиімді жоспарын анықтау үшін арнайы әдістерді қолдану керек. Қазіргі уақытта мұндай әдістердің бірнешеуі кездеседі, яғни, жоғарыда көрсетілгендей симплекс әдісінің негізінде жатқан олар, көбіне белгілі Гомори әдісі деген атпен белгілі.
Достарыңызбен бөлісу: |
