Алгоритмларни лойиҳалаш

“Алгоритмларни лойиҳалаш” фани бўйича маърузалар матни.
Лекция 4
4. ЧИЗИҚЛИ ДАСТУРЛАШ МАСАЛАЛАРИНИНГ МАТЕМАТИК МОДЕЛЛАРИ. ИҚТИСОДИЙ ТАХЛИЛ. МАҚСАД ФУНКЦИЯСИ. ЭГИЗАК МАСАЛА
Ишлаб чиқариш параметрлари орасидаги мавжуд иқтисодий ва моддий боғлиқликларга мос келувчи энг муносиб ишлаб чиқариш режасини топиш масаласи чизиқли дастурлаш масаласи(ЧДМ) деб аталувчи янги масалалар синфи пайдо бўлишига олиб келди.Математик модель қуриш жараёнида мавжуд ишлаб чиқариш ресурслари, бозор нархлари, ишлаб чиқариш нормативлари асосида шартлар шакиллантирилади ва мақсад функцияси (МФ) деб аталувчи функция кўриниши танланади.Вазиятга кўра,агар масала даромад билан боғлиқ бўлса, мақсад функциясининг максимал қийматини топиш талаб қилинади,агар масала сарф- ҳаражат билан боғлиқ бўлсамақсад функциянинг минимал қийматини топиш талаб қилинади.
Кўп ҳолларда ишлаб чиқариш ресурслари, кучлари ва уларнинг имкониятларини ифодаловчи шартлар чизиқли функция кўринишида берилишидан, ҳамда мақсад функцияси ҳам чизиқли шаклда бўлишидан бу масалалар ЧДМ деб ном олган.Бу ерда дастурлаш термини(сўзи)ни режалаштириш деб тушуниш керак,яъни даромадлари максимал ва харажатлари минимал бўладиган ишлаб чиқаришнинг оптимал режасини тузиш талаб қилинади. Бундай холда анъанавий оптималлаштириш усулларини қўллаб бўлмаслигига кейинроқ ишонч хосил қиламиз. Шунингучун ЧДМларни ечиш учун мўлжалланган махсус усуллар ишлаб чиқилган бўлиб. Биз бу ерда уларнинг баъзилари билан танишиб ўтамиз.
ЧДМ ҳақида бошланғич тасаввурга эга бўлиш учун, қўйидаги ишлаб чиқариш масаласини кўрайлик. Олдиндан таъкидлаб ўтиш керакки,масалада келтирилган нормативлар шартли қийматга эга бўлиб, керак бўлганда уларни реал қийматларга ўгириш ҳеч қандай қийинчилик туғдирмайди.
Икки хил турдаги мева шарбатларини ишлаб чиқарувчи ҳусусий кичик корхона бор. Корхонада 30 кг олча, 45 кг олма,12 кг шакар бор.Биринчи турдаги 1 банка шарбат ишлаб чиқариш учун 0,1кг олча, 0,5 кг олма, 0,1кг шакар керак. Иккинчи турдаги 1 банка шарбат ишлаб чиқариш учун 0,3кг олча, 0,2 кг олма, 0,1кг шакар керак. Биринчи турдаги 1 банка шарбат нархи 1000 сўм.Иккинчи турдаги 1 банка шарбат нархи 1400 сўм. Ишлаб чиқариш оптимал режасини аниқланг, яъни корхона даромади максимал бўлиши учун ишлаб чиқарилиши керак бўладиган биринчи ва иккинчи турдаги шарбатлар сонини аниқланг.
Масалани иқтисодий қўйилиши шундай ифодаланади. У етарлича жиддий муаммо бўлиб, бу масалани тўгри ечган хусусий тадбиркор ҳам ўз корхонасининг гуллаб яшнашини таъминлаши мумкин. Замонавий бозор иқтисодиёти стратегияси шароитида муҳит тез ўзгарувчан бўлиб режалаштиришни алгоритмлаш жараёни ҳам ишлаб чиқаришнинг узлуксиз қисми бўлади.
Юқорида келтирилган иқтисодий масалани математик моделини тузишга киришамиз. Корхонада ишлаб чиқарилган биринчи ва иккинчи тур мева шарбатлар банкаларининг номаълум сонини орқали белгилаймиз. Бунда ишлаб чиқариш режаси корхонада мавжуд ишлаб чиқариш ресурсларига мос келиши керак.Бунинг учун ишлаб чиқаришга сарфланадиган ресурслар хажми мос ресурслар заҳирасидан ошмаслиги керак. Шу талаблар асосида мавжуд нормативларга мос ресурслар сарфи ва ресурслар сарфи бўйича шартларнианиқлаймиз(олча,олма ва шакар):
(4.1)
(4.2)
Бу ерда корхона даромади қуйидаги мақсад функцияси билан ифодаланади:
(4.3)
Шундай қилиб, биз юқорида келтирилган иқтисодий масалани математик моделини ҳамда мақсад функциясини хосил қилдик. Моделда масала шартида келтирилган барча маълумотлар ҳисобга олинган. Мақсад функцияси эсакорхона даромадини ифодалайди.(4.1)-(4.3) формулалар билан ифодаланган мисол ЧДМнинг оддий мисоли бўлади. Математик масала мазмуни эса ОХ₁Х₂текислик координат текислигини тўпламидаги (4.1)-(4.2) шартларни қаноатлантирувчи (4.3) мақсад функциясининг нуқталари орасидан максимал қийматини топишдадир. (4.1)-(4.2) шартларга мос келувчи нуқталар тўплами мумкин бўлган ечимлар соҳаси(МБЕС) деб аталади. МБЕСнинг ихтиёрий нуқтасининг координаталари ишлаб чиқаришнинг мумкин бўлган режасини беради. Демакмумкин бўлган режалар сони чексиз кўп бўлади. Бу тўпламдан оптимал планни ажратиш масаласи нотривиал масала бўлади.
Икки ва уч ўлчовли холда қўлланилиши мумкин бўлган ЧДМни ечиш усулларидан бири билан танишайлик. Олдиндан айтиб ўтиш керакки, биринчи тартибли ҳосила нолга тенг бўладиган стационар нуқталарни топишга асосланган экстремумни аниқлашни анъанавий усулларини бу ерда қўллаб бўлмайди. Хақиқатдан хам,бизнинг ҳолда:

Яъни стационар нуқталар мавжуд эмас.