Жоғары оқу орнынан кейінгі білім бөлімі
Тақырып. Сызықты программалаудың жалпы және негізгі есептері
жүктеу/скачать 251 Kb.
|
- Бұл бет үшін навигация:
- Анықтама
- 2. Тақырып. Сызықты программалау есебінің негізгі қасиеті. Сызықты программалау есебінің геометриялық түсінігі.
- Теорема
| 1. Тақырып. Сызықты программалаудың жалпы және негізгі есептері.
Анықтама 1.1. Сызықтық программалаудың жалпы есебі деп, функцияның анықтауыш максималды (минималды) көрсеткішінен тұратын есепті айтамыз. (1) ш а р т т а р ы (2) (3) , (4) мұндағы, aij, bi, cj – нақты сандар және k m. Анықтама 1.2. Сызықтық программалаудың жалпы есебінде (1) функция (1)-(4) есептерінің мақсаттық функциясы, ал (2)-(4) берілген есептің шарттары деп аталады. Анықтама 1.3. Сызықтық программалаудың стандарт есебінде шарттары біртектес теңсіздік түрінде болады және айнымалылары теріс мән қабылдамайды. Яғни, (1) функция мен оның шарттарын (2)-(4) орындағанда, мұндағы k=m және l=n. Анықтама 1.4. Сызықтық программалаудың негізгі есебі деп, шарттардың барлығы тек теңдік түрінде берілген және бірде-бір айнымалысы теріс мән қабылдамайтын есепті айтады. Яғни, (1) функция мен оның шарттарын (3)-(4) орындағанда, мұндағы k=0 және l=n. Анықтама 1.5. сызықтық программалаудың жалпы есебінің шешуі (жоспары) деп аталады, егер ол осы есептің барлық шарттарын (3)-(4) қанағаттандыратын болса. Анықтама 1.6. Егер (1) есебіндегі жоспары үшін мақсаттық функция өзінің максималды (минималды) мәнін қабылдаса, онда ол ең тиімді жоспар деп аталады. Сызықтық программалаудың жоғарыда айтылған үш түрі бір-бірімен эквивалентті, яғни олардың бір түрінен түрлендірулер арқылы келесі түріне көшуге болады. Демек, ол үш түрлі жазылатын сызықтық программалау есептерінің қандай да бір түрінің ең тиімді жоспарын алсақ, онда басқа түрде жазылған бұл есептің ең тиімді жоспарын да анықтау дегенді білдіреді. 2. Тақырып. Сызықты программалау есебінің негізгі қасиеті. Сызықты программалау есебінің геометриялық түсінігі. Сызықты программалаудың негізгі есебін қарастырайық. Ол шарт бойынша F= функцияның максималды мәнін анықтаудан тұрады. Анықтама 1.7. Егер xj-дің оң коэфициентімен (9) теңсіздікке кіретін Pj векторының жүйесі сызықты тәуелсіз болса, онда X=(X1; X2;…;Xn) сызықты программалаудың негізгі есебінің тірек жоспары деп аталады. Pj векторлары m-мөлшерлі болғандықтан, тірек жоспары анықтамасынан оның оң элементтерінің саны m-нен көп болмау керектігі шығады. Анықтама 1.8 (8)-(10) сызықтық программалаудың негізгі себінің қасиеті дөңес жиынның қасиеттерімен тығыз байланысты. Анықтама 1.9. X1; X2;…;Xn- Еn евклидтік кеңістіктің еркін нүктелері болсын. Бұл нүктелердің дөңес сызқтық комбинациясы деп 1Х1+ 2Х2+...+ nXn суммасы аталады, мұндағ аi – еркін теріс емес сандар, олардың суммасы 1: тең. Анықтама 1.10. Егер кез-келген екі нүктесімен қоса олардың кез-келген дөңес сызықтық комбинациясында ішінде жататын жиын дөңес жиын деп аталады. Анықтама 1.11. Дөңес жиынның Х нүктесі оның төбесі деп аталады, егер ол берілген жиынның кез-келген әртүрлі екі нүктесі дөңес сызықтық комбинация түрінде бола алмаса. Теорема 1.1. Сызықтық программалаудың негізгі есебінің жоспарларының жиыны дөңес жиын болады. (егер ол бос жиын болмаса). Анықтама 1.12. Сызықтық программалаудың негізгі есебінің жоспарларының жиыны шешімдері көпбұрышы деп аталады. Теорема 1.2. Егер сызықтық программалаудың негізгі есебінің ең тиімді жоспары бар болса онда ол шешімдер көпбұрышының қандай да бір төбесінде орналасқан. Егер мақсаттық функция өзінің максималды мәнін шешімдер көпбұрышының екі төбенің дөңес сызықты комбинациясы болатын кез-келген нүктеде де өзінің максимум мәнін қабылдайды. Сызықтық программалаудың негізгі есебінің жоспарының жиыны бос жиын болмаса, онда ол дөңес көпжақты құрайды. Осы дөңес көпжақтың әрбір төбесі тірек жоспарына сәйкес келеді. Осы аталған төбелердің бірінде яғни қандай да бір тірек жоспары үшін мақсаттық функцияның мәні оның максимумына тең болады. Демек бұл төбе оң тиімді жоспарды анықтайды. Мақсаттық функция максимал мәнге ие болатын шешімдер көпбұрышының төбесін салыстрмалы түрде табу оңай, егер стандарттық түрде жазылған есептің екеуден көп емес айнымалысы бар болса немесе негізгі түрде жазылған есептің екеуден көп емес бос айнымалысы, яғни шектелген есептің жүйесінің коэфициенттерінен құралған n-r 2, мұндағы n- айнымалылар саны, r-матрица рангі, бар болса. Мынандай есепті қарастырайық: F=c1x1+c2x2 max (11) шарттары ai1x1+ai2x2 bi (i= ), (12) (13) (12) және (13) теңсіздіктің әрқайсысы геометрия тілінде жартылай жазықтықты анықтайды. Сондықтан (12), (13) теңсіздіктің жүйесінің шешуі бар болса, онда ол жоғарыда тұрған әрбір жартылай жазықтыққа тиісті болады. Жартылай жазықтықтың қиылысуы дөңес жиын болады. Бұл жиынды шешімдер көпбұрышы деп атайды. Бұл көпбұрыштың қабырғалары жататын түзудің теңдеуі (11)-(12) теңсіздіктерді теңдікке айналдыруда шығатын формуламен анықтайды. Демек, сызықтық программалаудың (12)-(13) есебінің шешуі дегеніміз шешімдер көпбұрышы бос жиын болмауы керек және мақсаттық функция осы шешімдер көпбұрышы жоғарыдан шектелуі керек. Осы шарттар орындалғанда шешімдер көпбұрышының ең болмағанда бір төбесінде мақсаттық функция өзінің максимум мәнін қабылдады. Осы ең тиімді жоспарға сәйкес төбені анықтау үшін мына сызықты c1x1+c2x2=h сызамыз және бұл сызықты = {c1; c2} векторлары бағытында параллель жылжытамыз. Нәтижесінде ол осы түзумен көпбұрыштың ең соңғы қиылысатын нүктесі ең тиімді жоспарға сәйкес нүкте болады. (12), (13) есептерінің геометриялық интерпретациясын қарастыруды анықтай отырып, оның шешімін табу кезінде 1.1-1.4 суреттердегі көрсетілген жағдайлар кездесуі мүмкін. B Fmax Fmax A c
1.1 сурет 1.2 сурет 1.1 суретте ең тиімді жоспарға сәйкес бір ғана нүкте төбесі болады. 1.2 суреттен мақсаттық функция максимал мәнді АВ кесіндісінің кез-келген бөлігінде қабылдай алатындығы көрініп тұр. 1.3 суретте есептің шешімі болмайды. Себебі мақсаттық функция шешімдер көпбұрышында жоғарыдан шектелмеген. 1.4 суретте есептің шешімі болмайды. Себебі шешімдер көпбұрышы бос жиын. 1.3 сурет 1.4 сурет Берілген шектелген жүйедегі сызықтық функцияның минималды мәнін табу оның осындай шектеудегі максимал мәнін табудан айырмашылығы c1x1+c2x2=h сызығы = {c1; c2} векторының бойымен емес, оған қарама-қарсы бағытта жылжуында. Осылайша мақсаттық функцияның максималды мәнін табуда кездесетін жоғарыда көрсетілген жағдайлар сол мақсаттық функцияның минимал мәнін тапқанда да орын алады. 3. Геометриялық интерпретация негізінде сызықты программалау есебінің шешу алгоритмі. Сонымен, сызықтық программалау есептерінің (11), (13) геометриялық мағынасына сүйеніп, графиктік әдіспен шешу мынадай қадамдардан тұрады: 1. Теңдеуі (12), (13) шарттардағы теңсіздік белгісін теңдікпен алмастырғанда шығатын түзулер сызады. 2. Есептің шартындағы әрбір теңсіздіктің шешуі болатын жартылай жазықтықтар табады. 3. Шешімдер көпбұрышын анықтайды. 4. = {c1; c2} сызады. 5. c1x1+c2x2=h түзуін сызады. Бұл түзу с векторына перпендикуляр орналасады. 6. c1x1+c2x2=h түзуін с векторы бағытында параллель жылжыта береді. Нәтижесінде мақсаттық функцияның максимум мәнін қабылдайтын нүктені табады немесе есептің шешімі болмайтындығын анықтайды. 7. Ең тиімді жоспардың координаталарын анықтап, мақсаттық функцияның сол нүктедегі мәнін есептейді. жүктеу/скачать 251 Kb. Достарыңызбен бөлісу:
|