Соли= ва божхона органлари академияси
Download 246.63 Kb.
|
2 5240437937430073730
|
10-мавзу Симплекс усули Режа : Чизиқли дастурлаш масаласини ечиш учун симплекс усулининг алгоритми. Оптималлик мезони. Мақсад функциясининг чегараланмаганлиги аломати. Янги ечимга ўтиш қоидалари. Янги симплекс жадвалига ўтишдаги алмаштириш формулалари. Оптимал ечимнинг ягоналиги шарти. Чизиқли дастурлаш масалаларини ечиш учун ишлатиладиган энг универсал усуллардан бири симплекс усулидир. Бу усул бошланғич ечимдан чекли сондаги итерациялардан кейин оптимал ечимни ҳосил қилиш йўлини кўрсатади ва ҳар бир навбатдаги итерация олдингисига нисбатан оптимал ечимга яқинроқ ечимни беради ҳамда шу усул ёрдамида иқтисодий масалаларнинг ечими топилади ёки ечим мавжуд эмаслиги аниқланади. Симплекс усулининг ғояси қуйидагидан иборат. Берилган чизиқли дастурлаш масаласининг ихтиёрий бошланғич ечими топилади. Агар бу ечим оптималлик шартини қаноатлантирса, оптимал ечим бўлади, акс ҳолда бошланғич ечим оптимал ечимга яқинроқ бўлган бошқа ечимга алмаштирилади. Ечимларни алмаштириш жараёни оптимал ечим топилгунча ёки берилган масаланинг оптимал ечими мавжуд эмаслиги аниқлангунча такрорланади. Агар масала ечимга эга бўлмаса ёки унинг чизиқли функцияси ечимлар кўпёқлигида чегараланмаган бўлса, симплекс усули ечиш жараёнида буни аниқлаштиришга имкон беради. Симплекс усулини 1949 йилда америкалик олим Данциг кашф қилди. Данциг билан параллел равишда собиқ совет олими, академик Канторович симплекс усулининг бир тури бўлган «иккиламчи баҳолар» усулини кашф қилиб, чизиқли дастурлаш фанининг тараққиётига катта ҳисса қўшди. Симплекс усули кейинчалик турли олимлар томонидан ривожлантирилиб борилди. Данциг яратган симплекс усул ҳар бир тенгламада биттадан ажратилган номаълум (базис ўзгарувчи) қатнашиши шартига асосланган. Умумийликни бузмаган ҳолда бу номаълумлар биринчи m та , , …, ўзгарувчилардан иборат деб оламиз. У ҳолда масала қуйидаги кўринишда бўлади: номаълумларнинг (7.1) функцияга минимал (максимал) қиймат берувчи ҳамда , (7.2) , , …, шартларни қаноатлантирувчи қийматлари топилсин, бу ерда ( ). ўзгарувчиларни базис ўзгарувчилар сифатида қараймиз. Демак, озод ўзгарувчилар ларга 0 қиймат берсак, базис ўзгарувчилар озод ҳадларга тенг бўлади. Натижада бошланғич ечим ҳосил бўлади. (7.2) чеклашлар системасида базис ўзгарувчиларни озод ўзгарувчилар орқали ифодалайлик: , (7.3) ва бу ифодаларни (7.1) мақсад функциясига қўямиз. Бунда у (7.4) кўринишни олади, бу ерда ( ), . Кейинги ҳисоблашларни бажариш қулай бўлиши учун масаланинг берилганлари ҳамда бошланғич ечим аниқлангандан кейин олинган дастлабки маълумотлар симплекс жадвал деб аталувчи қуйидаги жадвалга жойлаштирилади: 7.1 – ж а д в а л
Жадвалдаги озод ҳадлар устунида бошланғич ечим ёзилади ва шу устунда ҳисоблашлар натижасида оптимал ечимни оламиз. Жадвалнинг m+1 нчи сатрида (7.4) чизиқли функциянинг озод ҳади ва коэффициентлари ёзилади. Бу ечим учун оптималлик мезонини текширамиз: агар жадвал m+1 нчи сатрининг озод ҳадлар устунидаги элементидан бошқа барча элементлари номусбат (мақсад функциясини максималлаштириш ЧДМида — номанфий) бўлса, ечим оптимал ечим бўлади ва чизиқли функциянинг минимал (максимал) қиймати га, яъни озод ҳадлар устунидаги элементга тенг. Агар m+1 нчи сатрдаги камида битта элемент мусбат (манфий) бўлса, масаланинг оптимал ечими ҳали топилмаган бўлади. Шунинг учун топилган ечимни оптимал ечимга яқинроқ бўлган ечимга алмаштириш мақсадида базисга m+1 нчи сатрнинг энг катта мусбат (энг кичик манфий) элементига мос келувчи ўзгарувчини киритиш керак. Агар бундай элементлар бир нечта бўлса, у ҳолда сифатида мақсад функциясидаги коэффициенти энг кичик (энг катта) бўлган ўзгарувчи олинади. Бироқ агар бунда m+1 нчи сатрнинг мусбат (манфий) элементларига мос келувчи устунларнинг камида биттасининг барча (m+1 нчи сатрдагиларидан ташқари) элементлари номусбат бўлса, чизиқли дастурлаш масаласининг мақсад функцияси чекли минимумга (максимумга) эга бўлмайди. Бу ҳолда ЧДМ оптимал ечимга эга эмас ва уни топиш жараёни тўхтатилади. ўзгарувчи базисга киритилганда эски базис ўзгарувчилардан бирортасини базисдан чиқариш керак. Базисдан (7.5) шартни қаноатлантирувчи ўзгарувчи чиқарилади. коэффициент ҳал қилувчи элемент деб, у турган сатр ва устун эса мос равишда ҳал қилувчи сатр ва ҳал қилувчи устун деб аталади. Ҳал қилувчи (l нчи) сатрдаги ўзгарувчи ўрнига ҳал қилувчи (k нчи) устундаги ўзгарувчи базисга киритилади. Бунинг учун симплекс жадвал қуйидаги тарзда алмаштирилади. Ҳал қилувчи (l нчи) сатрдаги янги озод ҳад ва коэффициентлар аввалгиларидан уларни ҳал қилувчи элементга бўлишдан ҳосил қилинади. Қолган сатрлар учун эса l-сатрдаги янги озод ҳад ва коэффициентлар шу сатрларнинг ҳар бирида ҳал қилувчи элементдан мос равишда юқорида ёки пастда ётган коэффициентга кўпайтирилиб, шу кўпайтмалар қаралаётган сатрдаги эски озод ҳад ва коэффициентлардан мос равишда айирилиши натижасида янги озод ҳад ва коэффициентлар ҳосил қилинади. Жумладан, ҳал қилувчи (k нчи) устундаги ҳал қилувчи элементнинг ўрнида 1, қолган коэффициентлар ўрнида эса 0 ҳосил бўлади. m+1 нчи сатрдаги янги элементлар худди шунга ўхшаш тарзда аниқланади. Янги симплекс жадвали (7.2-жадвал)да дастлабки итерацияда бажарилган амалларни такрорлаймиз. Ечимнинг оптималлик мезони текширилиб, ё оптимал ечим олинади, ё масаланинг мақсад функцияси чекли минимумга (максимумга) эга эмаслиги аниқланади, ё жараён ана шу икки натижадан бирига келгунча давом эттирилади. Агар оптимал ечимдаги m+1 нчи сатрнинг озод ҳадлар устунидаги элементидан бошқа элементларининг фақат базис ўзгарувчиларга мос келувчиларигина нолга тенг бўлса, бу оптимал ечим ягона бўлади. Агар бирорта базис бўлмаган ўзгарувчи учун m+1 нчи сатр элементи нолга тенг бўлса, умумий ҳолда оптимал ечим ягона бўлмайди. 7.2 – ж а д в а л
Download 246.63 Kb. Do'stlaringiz bilan baham: 
|