Кириш. Чизиқли программалаштириш (1-маъруза машғулоти)

Динамик программалаш масаласининг геометрик талқини. «Беллманнинг функционал тенгламалари»

• Геометрик нуқтаи назардан, динамик программалаш масаласини қуйидагича талқин қилиш мумкин:
• Умумий ҳолда системанинг бошланғич xo ҳолати ва охирги xk ҳолати аниқ берилмайди, ҳамда бошланғич ҳолатнинг бутун бир X0* соҳаси ва охирги ҳолатларнинг Xk* соҳаси кўрсатилади.

• Умумий ҳолда динамик программалаш масаласи қуйидагича таърифланади:
• Бирор бошқарувчи X система бошланғич xoXo* ҳолатда бўлсин. Вақт ўтиши билан системанинг ҳолати ўзгаради ва u xkXk* охирги ҳолатга ўтади, деб ҳисоблайлик. Система ҳолатларининг ўзгариши бирор миқдори y W-мезон (критерий) билан боғлик дейлик. Системанинг ўзгаrиш жараёнини шундай ташкил этиш керакки, бунда W-мезон ўзининг оптимал қийматига эришсин.

• U-мумкин бўлган бошқарувлар тўплами бўлсин, у ҳолда, масала X системани xoXo* ҳолатдан xkXk* ҳолатга ўтказишга имкон берувчи шундай u*U бошқарувни топишдан иборатки, бунда W(u) мезон ўзининг W*=W(u*) оптимал қийматига эришсин.

• Одатда системанинг xo ҳолатини сонли параметрлар билан, масалан, ажратилган фондлар миқдори, жалб қилинган инвестициялар миқдори, сарфланган ёқилғи миқдори ва ҳакозо билан ифодалаш мумкин. Бу параметрларни системанинг координаталари деб атаймиз. У ҳолда системанинг ҳолатини x нуқта билан ва унинг X0 ҳолатдан Xk ҳолатга ўтишини x нуқтанинг траекторияси билан тасвирлаш мумкин.

• Масалани ечишдан аввал
• GT, GT-1,T, …, G1,2,…,T=G
• белгилашлар киритамиз. Бу ерда GT – масаланинг охирги T босқичдаги аниқланиш соҳаси, GT-1,T – T ва T-1 босқичлардаги аниқланиш соҳа, G1,2,…,T=G – берилган масаланинг аниқланиш соҳаси.
• Мақсад функциянинг охирги босқичдаги оптимал қийматини f1(xT-1) билан белгилаймиз:

• Худди шунингдек, T-1 қадамдаги шартли оптимал қийматни f2(xT-2) билан белгилаймиз. У ҳолда

• Худди шунингдек,

• Бу функциялар оптималлик принципининг математик формадаги ёзилишидан иборат бўлиб, улар «Беллманнинг функциянал тенгламалари» ёки «динамик программалашнинг асосий функциянал тенгламалари» деб аталади. Бу тенгламалари ёрдамида динамик программалашнинг T-1 босқичдаги ечимини сўнги T босқичдаги ечим орқали топилади. Шунинг учун юқоридаги муносабатлар Беллманнинг реккурент муносабатлари деб аталади.