D.C. програмчлал ба түүний тоглоомын онолын хэрэглээ
Салбар : Байгалийн шинжлэх ухаан
Улсын дугаар : 2621
Хамгаалсан он : 2011
Түлхүүр үг : Нэшийн тэнцвэр, глобал шийд, гүдгэр максимум, глобал нийлэлт, холимог стратеги
Аннотаци
Оптимизацийн онолын гүдгэр бус ангийн бодлого болох D.C. ангийн бодлого нь нэлээн хүнд ангиллын бодлого байдаг. Гүдгэр бус оптимизацийн ангийн бодлого нь гүдгэр ангийн бодлогоо бодвол локал шийд нь глобал шийд байх нөхцөл, шийд нь глобал шийд байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлүүд нь сайтар судлагдаагүй байдгаараа илүү хүндрэлтэй юм. Шийдийн глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь уг бодлогын тооцон бодох арга, алгоритмын үндэс нь болж өгдөг. Глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөлийг анх Фолк 1973 онд, Гальперин 1987 онд тус тус хийсэн байдаг. Гэвч эдгээр нөхцлүүд нь тооцон бодох үүднээс хэрэглэхэд нэлээн бэрхшээлтэй, тооцон бодох хүндрэлийг бууруулах боломжгүй байв. 1987 онд А.С.Стрекаловский гүдгэр функцийг максимумчлах бодлогын ангид анх удаа глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг томъёолж баталсан. Уг нөхцлийг А.С.Стрекаловский, Р.Энхбат нар судалж тооцон бодох аргад буулган хэрэглэсэн. Хожим Ж.Б.Ирриарт-Уррути нар D.C. ангийн хувьд глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг томъёолсон боловч энэхүү нөхцөл нь тооцон бодохын хувьд хэрэглэхэд түвэгтэй байдаг. Ер нь А.С.Стрекаловскийн глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг одоогийн байдлаар өөрөө болон Идэр, Барсболд зэрэг эрдэмтэд нийтдээ 10 гаруй ангийн хувьд өргөтгөн эсвэл түүнтэй төстэй байдлаар ашиглан хэрэглээд байна. Иймд энэхүү глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг D.C. бодлогын хувьд мөн томъёолж хэрэглэх чиглэлийн судалгаа нь шинэлэг бөгөөд онолын бүрэн үндэслэлтэй юм.
Нөгөө талаас эдийн засгийн болон техник, технологийн олон төрлийн бодлогууд нь гүдгэр бус оптимизацийн бодлого хэлбэрээр тавигдах нь нэн элбэг. Ялангуяа миний авч үзэж буй олигодоль зах зээл дээрх цөөн тооны тоглогчтой тэг биш нийлбэртэй тоглоомын үед түүний Нэшийн тэнцвэрийг олох их чухал байдаг. Гэтэл одоог хүртэл Нэшийн тэнцвэрийг олох үр дүнтэй түгээмэл арга боловсруулагдаагүй байна. D.C. бодлогыг А.С.Стрекаловскийн глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийн үр дүнд тулгуурласан арга, алгоритмыг ашиглан бодох бүрэн боломжтой. Ингэхдээ уг бодлогын ангид тохирсон байхаар алгоритмыг зохиож, зүгшрүүлэх нь их чухал.
Диссертацийн хүрээнд дээр дурдсан үндэслэлүүд дээр тулгуурлан D.C. ангийн бодлогын глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг томъёолон түүн дээр тулгуурласан алгоритмыг боловсруулж, уг алгоритмынхаа онолын нийлэлтийг батлан, тоон туршилтаар шалгаж баталгаажуулах зэрэг асуудлыг дэвшүүлж шийдвэрлэсэн.
Энэхүү ажлын хүрээнд гүдгэр бус оптимизацийн бодлогын D.C. ангийн хувьд онол, арга зүй, хэрэглээний асуудлыг судалсан.
Судалгааны онолын хэсэгт гүдгэр бус оптимизацийн ангиудын хувьд глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлүүдийг судалсан. 1987 онд А.С.Стрекаловскийн анх томъёолсон глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг нийтдээ 10 гаруй ангийн хувьд өргөтгөн эсвэл түүнтэй төстэй байдлаар ашиглан хэрэглээд байна. Ж.Б.Ирриарт, Уррути, Р.Хорст, Хоанг Туй зэрэг дэлхийд тэргүүлдэг эрдэмтэд энэ чиглэлээр судалгаа хийж байгаа нь энэхүү глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг ашиглан глобал шийд олох чиглэл нь их ирээдүйтэйг харуулж байгаа юм. Энэхүү чиглэлийн анхны үр дүнгүүдийг Р.Энхбат, Ц.идэр, А.С.Стрекаловский нар гарган авсан байдаг. Р.Энхбат нь глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийн хувьд хувьд зааг функцийн тухай ойлголтыг анх оруулж, түүнийг аппроксимачлах замаар бодлогыг бодох аргачлалыг боловсруулсан. Хамгийн сүүлд 2009 онд Б.Барсболд монотон фунзцийн ангийн хувьд глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг томъёолж, алгоритм боловсруулан нийлэлтийг нь баталсан байдаг.
Тоглоомын онолын бодлогын тэг биш нийлбэртэй хожлын матрицтай тоглоомын Нэшийн тэнцвэрийн цэгийг /шийдийг/ олох нь нэлээн хүндрэлтэй. Ийм төрлийн бодлогын глобал шийдийг олох боловсронгуй арга одоог хүртэл олдоогүй л байна. Ер нь бол оптимизацийн ихэнх ангийн бодлогыг D.Cангийн бодлого руу шилжүүлж болдог. Харин D.C. ангийн бодлого нь ерөнхийдөө NP хүндрэлтэй бодлогын ангид багддаг бөгөөд нэгэнт NP хүндрэлтэй шийдэх учраас түүнийг бодох бэлэн жор байхгүй. Энэ ангиллын бодлогыг бодох огтлолын арга нь глобал нийлэлт байхгүй учир дутагдалтай байдаг бол салаа мөчрийн арга нь глобал нийлэлттэй боловч маш их хэмжээний санах ой, цаг хугацаа шаарддаг нь тооцон бодохын хувьд хүндрэлтэй байдаг. Иймд бидний авч үзэж буй D.C. ангийн бодлогын хувьд шалгахад хялбар глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг ашиглан бодох арга боловсруулах нь илүү үр дүнтэй юм.
Энэхүү судалгааны ажлаар дараах үндсэн үр дүнд хүрэх зорилт тавьсан. Үүнд:
1. D.C. бодлогын ангийн хүрээнд уг бодлогыг гүдгэр максимумчлалын бодлогын анги руу шилжүүлэх, түүний үндсэн дээр глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг шинээр бичих
2. Шинэ үүссэн бодлогыг анхны бодлоготой эквивалент гэж харуулах
3. Шинэ бодлогын хувьд глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөлд тулгуурласан тооцон бодох арга боловсруулж турших, алгоритм байгуулах
4. Энэхүү алгоритмын нийлэлтийг баталж харуулах
5. Эдийн засгийн судалгааны нэг хэсэг болох тоглоомын онолын бодлогыг өөрсдийн аргаар бодох, турших, баталгаажуулах
Дээрх зорилтуудад хүрэх арга зам харьцангуй тодорхой байсан. Энэ чиглэлээр судлаачдын хийсэн ажлуудыг судалсан. Профессор Р.Энхбатын боловсруулсан аргыг эрс гүдгэр нөхцлийг сулруулж өмнөх хийгдсэн ажлуудыг өргөтгөсөн. Мөн арга алгортимыг авч үзэж буй бодлогын ангид тохируулан өөрчилж хэрэглэсэн. Тоглоомын онол болон тооны онолын бодлогуудад аргаа туршсан. Квадратлаг тохиолдолд D.C. бодлогуудыг алгоритмаараа туршиж шалгасан.
Энэхүү ажлын хүрээд хийгдсэн судалгааны шинэлэг талыг дараах үр дүнгүүдээр тодорхойлж болно. Үүнд:
1. D.C. бодлогын ангийн хүрээнд уг бодлогыг гүдгэр максимумчлалын бодлого ангируу шилжүүлэх, түүний үндсэн дээр глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг тохируулан бичсэн. Шинээр үүссэн бодлогыг анхны бодлоготой эквивалент гэж харуулсан.
2. Шинэ бодлогын хувьд глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл дээр тулгуурласан тооцон бодох арга боловсруулж туршсан. Алгоритм байгуулсан.
3. Энэхүү алгоритмын нйилэлтийг баталж харуулсан.
4. Тоглоомын онолын бодлогыг бодож тоон туршилтаар баталгаажуулсан.
o Онолын ач холбогдол
D.C. бодлогынг гүдгэр максимумчлалын бодлого руу шилжүүлж болохыг харуулсан. Уг бодлогыг бодохдоо зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг огтлолын эсвэл салаа мөчрийн арга дээр биш глобал оновтой байх зайлшгүй бөгөөд хүрэлцээтэй нөхцлийг ашиглан бодох арга боловсруулсан. Энэхүү аргыг тооцон бодох аргад буулган хэрэглэхэд тохиромжтой.
o Практикийн ач холбогдол
Тоглоомын онолын бодлогыг бий болгосон алгоритмаараа бодсон. Мөн квадратлаг тохиолдолд D.C. бодлогыг бодох аргаа хэрхэн хэрэглэх талаар сайтар судалж энэ тохиолдолд бодох алгоритм боловсруулсан.
Судалгааны үр дүнг нийтдээ 8 хуралд илтгэж илтгэлээ хурлын хураангуйнуудад нь хэвлүүлж байсан. Үүнээс 1 хурал нь дотоодын, 7 хурал нь олон улсын хурал байсан. Мөн судалгааны үр дүнг ШУТИС-ийн КТМС-ийн Үйлдлийн шинжилгээний профессорын багийн эрдэм шинжилгээний хурал, МУИС-ийн МКС-ийн Математик Загварчлал, Хэрэглээний Математик, ЭЗС-ийн Эдийн Засгийн Мэдээлэл-Загварчлалын тэнхмүүдийн хамтарсан семинарт илтгэж хэлэлцүүлсэн. Мөн диссертацийн ажлаа МУИС-ийн МКС-ийн “Математикийн Их Семинар”-т илтгэж хэлэлцүүлсэн.
Зохиогч
Боловсролын доктор(PhD)
Бүтээлийн тоо : 2
Ишлэгдсэн тоо : 0
