Динамикалық бағдарламалау түсініктері

1. Динамикалық  бағдарламалау түсініктері

Сызықтық және бейсызықтық бағдарламалау есептерінде экономика-лық үдеріс  статикалық, яғни уақыттан тәуелсіз деп қарастырылатындықтан, тиімді шешімі жоспарлаудың бір ғана кезеңіне анықталатын. Бұндай есептер бір кезеңдік немесе бір қадамдық делінеді.

Динамикалық бағдарламалау есептерінде экономикалық үдеріс уақыттан тәуелді, бірнеше уақыт кезеңінен тұратындықтан әрбір кезеңдерінің тиімді шешімдері анықталады, осы негізде бүкіл үдерістің тиімді ұласуы қалыптасады. Осы себепті динамикалық бағдарламалау есептері көп кезеңді немесе көп қадамды деп аталады.

Экономикалық үдеріс басқарылымды делінеді, егер оның дамуына әсер ету мүмкін болса. Әрбір кезеңде үдеріс барысына әсер ететін шешімдер жиынтығы басқару деп аталады.

Көп кезеңді үдерісті жоспарлағанда, тұтас үдерістің талаптарынан шығатындай етіп, жеке кезеңдегі шешімдер қабылданады.

жүйесінің   уақытындағы қызметі жоспарлансын, мұндағы   – кәсіпорындары, – әрбір кезең (шаруашылық жылы). Т периодының басталуында бөлінген негізгі қаржы , жүйенің бастапқы жағдайы , соңғы жағдайы . Т периодының ақырында кәсіпорындар жүйесінің қосынды кірісі  максималды болатындай етіп, негізгі қаржы   кәсіпорындарына әрбір кезеңге қалай бөлінеді?

-шы жыл басында -ші кәсіпорынға   бөлінетін қаржы  десек, басқару  анықталады, яғни  кәсіпорнына ,  кәсіпорнына , … ,   кәсіпорнына   үлестері  бөлініп,     басқару векторы анықталады.

Бөлінген қаржылар жиынтығы k  қадамдарында n-өлшемді кеңістіктің келесі векторлар жүйесімен анықталады

Сонымен  k жылдарындағы қосынды кіріс басқарулар жиынтығынан тәуелді, яғни

Онда есеп былай қойылады: әрбір кезеңдегі басқаруды, кәсіпорындар жүйесінің қосынды кірісі максималды болатындай етіп таңдау қажет.

Математикалық моделі

2.Динамикалық  бағдарламалаудың жалпы есебі

Басқарылатын физикалық жүйе   бастапқы  жағдайынан уақыт өте келе ақырғы  жағдайына келтіріледі. Жағдайлардың өзгеріс үдерісімен сандық белгі    байланысты. Үдерісті осы сандық  белгі тиімді (оптималды) мәнін қабылдайтындай етіп ұйымдастыру қажет.

Мүмкін болатын басқарулар жиынын   деп белгілейміз. Онда есеп былай қойылады:  жүйесін бастапқы жағдайынан, ақырғы  жағдайына белгі  тиімді  мәнін қабылдайтындай етіп келтіретін,  басқаруын анықтау керек.

Математикалық түрде 3.Тиімді басқаруды кезеңдерімен құру қағидасы функционалдық теңдеулер әдісі

3.1 Динамикалық  бағдарламалау  көп қадамды үдерісті кезеңдермен жоспарлайтындықтан, үдерістің  тұтас дамуын ескере отырып, әрбір қадамын келешекті ескере отырып тиімді етеді.

Әрбір үдерістің соңғы k-ші қадамы бар, онда шешімді қабылдау келешектен  тәуелсіз.  Осы  себепті  бұл  қадамда  ең  үлкен  әсер  басқару қабылданады. Бұл қадамды жоспарлап алып, оның алдынғы (k-1)-қадам тіркеледі, ал оған өз кезегінде (k-2)-қадам тіркеледі т.с.с. Ақырында бастапқы  жағдайына келеді. Динамикалық бағдарламалау осылайша ақырынан  бастапқы жағдайға оралатындай болып түзіледі.

k-ші қадамды жоспарлау үшін жүйенің (k-1)-ші қадамындағы жағдайын білу керек. Егер жүйенің (k-1)-ші қадамындағы жағдайы белгісіз болса, үдерістің сипатында, осы қадамдағы жағдайына мүмкін болатындай әр түрлі болжамдар жасалады. Соңғы  k-ші қадамда әрбір болжамға тиісті тиімді басқару анықталады. Мұндай тиімді басқару  шартты тиімді делінеді.

k қадамды үдеріс жоспарланады. Жүйенің (k-1)-ші қадамдағы мүмкін болатын жағдайларды    делік. Соңғы қадамда олардың әрқайсысына шартты тиімді басқаруларын

табамыз. Осылайша k-ші қадамы жоспарланады. Шындығында, соңғы қадам алдында жүйе қандай жағдайда болмасын, алдын ала белгілі  соңғы қадамда  қандай басқару қабылданатыны. Дәл осылайша (k-1)-ші қадамда да шартты тиімді қадам басқаруы k-ші қадамдағы шартты тиімді  қортындыда жүйенің бастапқы   жағдайына келеміз.

Басқа қадамдарға қарағанда жүйенің бірінші қадамда мүмкін болатын жағдайлар қарастырылмайды, себебі бастапқы жағдай  біреу ғана, екінші қадамдағы  шартты тиімді  басқарулар ескеріле отырып , тиімді басқару  бірден анықталады. -ден  -ға дейін өтіп, тұтас үдерістің ізделініп отырған тиімді басқаруы алынады.

3.2 Р.Беллманның [1] көрсетуіндей, көп кезеңді үдерістің тиімді шешімін табу функционалдық теңдеудің шешімін табуға келтіріледі.

Шамасы  х қаржы екі түрлі кәсіпорнын дамытуға жұмсалады делік. Егер бірінші кәсіпорнына у, екіншісіне х-у қаржы бөлінсе, онда кіріс тиісінше g(y)  және h(x-y)-ті құрасын. Жалпы кіріс J максималды болатындай етіп қаржыны бөлу қажет. Қойылған есеп мақсат  функциясының максималды мәнін табуға келтіріледі.

Егер g  және h  функциялары        мәндерінде үздіксіз болса,  мақсат функциясының максималды мәні барлық уақытта бар екендігі белгілі.

Сонымен max бір кезеңді үдерістегі мүмкін болатын максималды кірісті анықтайды. Кірістің бірлік өлшемі қаржының бірлік өлшемінен өзгеше болуы да мүмкін.  Мысалы  х теңге болса,  g(y)  адам-сағат мөлшері, машина қолданғанда үнемделген нәтижесі болуы да мүмкін.

Екі кезеңді үдерісті қарастырайық. Бастапқы қаржы у  кіріс g(y)-ті  алуға жұмсалған шығыннан соң   шамасына дейін кемиді , сол сияқты (х-у)-те һ(х-у) кірісінен соң b(x-y)-ке дейін кемиді  делік. Онда бір кезеңді үдерістен соң қалған қаржы  үшін бөлісті қайта жалғастырамыз , ,        .

Бұл бөліс нәтижесіндегі кіріс , онда толық кіріс

Демек, максималды толық кіріс осы функцияның және айнымалылары бойынша алынатын максимумынан турады

N кезеңнен тұратын үдерісте операция N  рет қайталанады, толық кіріс функциясы былай анықталады

мұндағы бірінші, екінші, … , (N-1)-ші кезеңдерде әрі қарай бөлініске түсетін шамалар келесі қатынастармен анықталады

Есепті кезеңдерге бөліп, тиімділік қағидасымен N  кезеңді үдерісте шешеміз. N кезеңді үдерістегі толық кірістің максималды мәні тек N-нен және бастапқы х шамасынан тәуелді болатындықтан деп аламыз.

Екі кезеңдік үдерісте алғашқыдан қалған  шамасын тиімді етіп бөлу қажет. Демек  тиімді таңдалғандағы кіріс , ал екі кезеңді үдеріс үшін толық кіріс  және  функцияларын байланыстыратын рекурентті қатынасымен өрнектеледі.

Осылайша тұжырымдай отырып, N кезеңді үдеріс үшін негізгі функцио-налдық  теңдеуді аламыз

Мұнда әрбір кезең есептеулерінде  мен бірге -те анықталады.

Сонымен динамикалық бағдарламалау есебін функционалдық теңдеулер әдісімен шешкенде N өлшемді есепті N тізбектен тұратын бір өлшемді есептерге келтіреміз.

Динамикалық бағдарламалауда үдеріс соңғы жағдайдан бастапқы жағдайына қарай өрбитіндіктен, бұған тән дискретті үдерісті өрнектейтін функционалдық теңдеу

f-үдеріс мақсаты (кіріс, пайда т.б);  N-кезеңдер саны; х-айнымалы, жүйенің N-ші қадамдағы сипаттаушысы; — белгінің нәтижелік мәні, тиімділік қағидасымен алынған; — басқарушы айнымалы, нәтижелік белгінің мәні тәуелді болатын; — белгінің шамасы; N-ші кезеңде алынған, 0 мен х аралығында; — нәтижелік белгінің тиімді мәні  жағдайынан бастап қалған N-1 кезеңдерден өткеннен соңғы.

себебі  шамасын   N-ші кезеңде таңдауға байланысты бастапқы х шамасы -ге дейін кеміген.

Қорытынды. Шешімдері бірінен соң бірі қабылданатын көп кезеңді үдерісте, кезеңнен-кезеңге және жағдайдан-жағдайға ауысып отыру функционалдық теңдеулермен өрнектеледі, Р.Беллманның [1] тиімділік қағидасына негізделеді.

ӘДЕБИЕТТЕР

Беллман Р. Динамическое программирование. –М.: ИЛ, 1960.

Вентцель Е.С. Исследование операций. –М.: Советское радио, 1972.

Кузнецов Ю.Н., Кузибов В.И., Волощенко А.Б. Математическое программирование. –М.: Высшая школа, 1976.

Робертс С. Динамическое программирование в процессах химической технологии и методы управления. –М.: Мир, 1965.

Хедли Дж. Нелинейное и динамическое программирование. –М.: Мир, 1967.