Сызықтық бағдарламалаудың жалпы есебі және математикалық бағдарламалау есептерініңмодельдерін құру
Сызықтық бағдарламалау есебін графикалық әдіспен шешу
жүктеу/скачать 147,42 Kb.
|
1 Сызықтық бағдарламалау
| 1.2 Сызықтық бағдарламалау есебін графикалық әдіспен шешу
Сызықтық бағдарламалауесебін (СБЕ) ең қарапайым және көрнектішешу әдісі графикалық әдіс болып табылады. Ол сызықтық бағдарламалауесебінің геомтериялық интерпритациясына негізделген және екі белгісізі бар СБЕ шешу кезінде қолданылады: Есептің шешімін жазықтықта қараймыз. Функционалды шектеулер жүйесінің әрбір теңсіздігі аi1 x1+ai2 x2 = bi , i=1,m шеқаралы түзумен жарты жазықтықты анықтайды. Теріс еместіктің шарттары х1=0, х2=0 шекаралық түзулермен сәйкес жарты жазықтықтарды анықтайды. Егер жүйе үйлеспелі болса, онда жарты жазықтықтар қиылыстырып дөңес жиыны болып табылатын жалпы бөлікті туындайды және өзімен нүктелердің жиынтығын ұсынады; бұл нүктелердің әр координаттары осы жүйенің шешімі болып табылады. Осы нүктелердің жиынтығын шешімдердің көпбұрышы деп атайды. Ол көпбұрышпен шектелген және шектелмеген нүкте, кесінді, сәуле бола алады. Геометриялы СБЕ өзімен сызықтық мақсатты функцияның максималды (минималды) мәндер координаттары жеткізілетін шешімдер көпбұрышының сондай бір бұрыштық нүктесін табуы болып ұсынылады, сонымен бірге рұқсат етілетін шешімдер ретінде шешімдер көпбұрышының барлық нүктелері болып табылады. Сызықтық теңдеуі бір сызықта жататын нүктелер жиынын бейнелейді. Сызықтық теңсіздік жазықтықтағыәлдебіроблыстықұрайды. СБЕ шектеулер жүйесінің әр теңсіздігінің шешімі шекаралық түзуі бар және оның бір жағында орналасқан жарты жазықтық болып табылады. Жүйенің сәйкес теңсіздігімен анықталатын әр жарты жазықтықтардың қиылысы мүмкін болатын шешімдер облысы (МШО) немесе анықталу облысы деп аталады. Мүмкін болатын шешімдер облысы теріс еместік шартын (хj≥0, j = )қанағаттандыратынын есте сақтау қажет. Анықталу облысына тиісті кез-келген нүктенің координаты есептің мүмкін шешімі болып табылады. СБЕ графикалық әдісі бойынша мақсатты функцияның экстремалды мәнін табу үшін вектор-градиентті қолданады, оның координаттары мақсатты функцияның дербес туындылары болып табылады: Бұл вектор мақсатты функцияның ең жылдам өзгерісінің бағытын көрсетеді. Вектор-градиентке перпендикуляр с1х] + с2х2 = f(x0) түзуі мақсатты функция деңгейінің түзуі болып табылады. Деңгей түзуінің кез-келген нүктесінде мақсатты функция бірдей мәнді қабылдайды. Мақсатты функцияны тұрақты а шамасына теңестірейік. а мәнін өзгерте отырып, әрқайсысы мақсатты функция деңгейінің түзуі болатынпараллель түзулердің жиынын аламыз. Мақсатты функция деңгей түзуінің маңызды қасиеті мынада, түзуді бір жаққа параллель жылжытқан кезде деңгей тек өседі, ал кері жаққы жылжытқанда – тек кемиді. СБЕ шешімінің графикалық әдісі төрт кезеңнен тұрады: СБЕ мүмкін болатын шешімдер облысы (МШО) құрылады. Басы х0 (0; 0) нүктесінен басталатын мақсатты функцияның (МФ) вектор-градиенті құрылады: = (c1, с2). с]х[ + с2х2 = а(а – тұрақты шама) деңгей түзуі - вектор-градиентіне перпендикуляр түзу f(х1, х2) мақсатты функцияның барынша максималдану жағдайында,МШО аумағынан шыққанша, вектор-градиент бағытында жылжиды. f(х1, х2) минимизациясы жағдайында деңгей түзуі вектор-градиентке қарсы бағытта жылжиды. Бұл жылжыту кезінде МШО шеткі нүктесі (немесе нүктелері) f(х1, х2) максимум (минимум) нүктесі болып табылады. Егер деңгей түзуіне тиістітүзу өзінің қозғалысы кезінде МШО шықпайтын болса, онда f(х1, х2) функциясының минимумы (максимумы) жоқ. Егер мақсатты функция деңгейінің түзуі МФ оңтайлы шешімі табылатын есептің функционалды шектеуіне параллель болса, онда МФ оңтайлы шешімі екі оңтайлы бұрыштық нүктелердің арасында жатқан сол шектеудің кез-келген нүктесінде табылады, және тиісінше сол нүктелердің кез-келгені СБЕ оңтайлы шешімі болып табылады. Максимум (минимум) нүктелерінің координаттары анықталады. Бұл үшін қиылысында максимум (минимум) нүктесін беретін түзулердің теңдеулер жүйесін шешу жеткілікті. Алынған нүктедегі f(х1, х2) мәні мақсатты функцияның максималды (минималды) мәні болып табылады. СБЕ графикалық әдісінің мүмкін болатын жағдайлары 1.3 кестесінде келтірілген. Кесте 1.3
жүктеу/скачать 147,42 Kb. Достарыңызбен бөлісу:
|