Мустакил иш

Беллман тенгламасини ечиш
Масалани динамик программалаш усули билан ечишнинг учинчи (ва охирги) босқичи Беллман тенгламасининг ечимини излашдан ва у бўйича (1) масаланинг ечимини қуришдан иборатдир. (6) тенгламада деб оламиз:
(8)
Бу ифоданинг ўнг томонидан берилган функция ва (7) дан топилган функция бор. Шунинг учун (8) формула маълум бир ўзгарувчилиги функцияни максималлаштириш билан функцияни ҳисоблаш имконини беради. Сўнгра (6) да деб олиб, ҳар бир ҳолда бир ўзгарувчилиги функцияни максималлаштириш амални бажариб, кетма-кет функцияларн оламиз.

1. 
   га асосан сон (1) бошланғич масала учун максимал фойдадан иборатдир. Хомашёнинг технологик жараёнлар бўйича оптимал тақсимотини топиш учун (5) ифодага мурожаат қиламиз. Унда деб олб, (5) нинг аниқланиши бўйича агар барча c та жараён учун хомашё миқдори с га тенг бўлса, охирги жараёнга (бу ҳолда n- жараёнга) ажратилган хомашёнинг оптимал миқдорга тенг бўлган сонни оламиз. Шундай қилиб, бошланғич масала оптимал режасининг компонентаси топилади:
   

Агар n- жараён учун миқдор ажратилса, у ҳолда қолган n-1 та жараён учун миқдордаги хомашё қолади. (5) да деб оламиз ва ни топамиз. Равшанки, (1) масаланинг оптималнинг охиргидан олдинги компонентаси га тенгдир. Ечиш жараёнини давом эттириб, (1) бошланғич масала ечимининг компонентларини топамиз.
Натижани таҳлил қиламиз. Усулнинг афзалликлари: 1) бошланғич n та ўзгарувчи бўйича максималлаштириш масаласи (1) битта ўзгарувчи бўйича n-1 та максималлашитириш масаласи (6) га келтирилди ҳамда натижа-глобал оптимал режадан иборат бўлди; 2) ечиш жараёнида масала элементларининг аналтик хоссаларидан фойдаланилмайди; берилган функциялар жадвал, график, алгоритмик ва ҳ.к кўринишда берилиши эди; 3) ларни ҳисоблаш натижалари бўйича c ва n нинг қийматларини вариациялаб, (1) масаланинг ечимини осон қуриш мумкин; бу (1) масала ечимининг кўрсатилган параметрларнинг ўзгаришига сезгирлигини таҳлил имконини беради.
Усулнинг асосий камчилг Беллман томонидан «ўлчовнинг қарғши» деб аталган бўлиб, у шундай иборатки, (6) Беллман тенгламасини ечишда функцияларни эсда сақлашга тўғри келади. Берилган битта хомашёни тақсимлаш масаласида улар бир ўзгарувчили функциялардан иборат. Умумий ҳолда эса аргументларнинг сони хомашёнинг хиллари сонига тенг бўлади. ЭХМ да кўп ўзгарувчили функциялар (n>2) жадвалларини тузиш оператив хотира имкониятининг чегараланганлигидан принципиал қийинчиликларга олиб келади, шунинг учун бу усулнинг муҳокама қилинаётган шу камчилиги кўп ўлчовли (с-вектор) масалаларни ечишда динамик программалашнинг юқорида баён қилинган классик тарҳини амалга ошириш имконини бермайди. «Ўлчов қарғиши» ни бартараф этишнинг турли усуллари тавсия қилинган.