მენეჯმენტის ამოცანების ზემოთ განხილულ მოდელებში დრო არ იყო გათვალისწინებული. ეს არის ეგრეთ წოდებული ერთსაფეხურიანი მოდელები, რომლებიც საშუალებას გაძლევთ გაანალიზოთ სტატიკური, დროიდან დამოუკიდებელი პროცესები, მაგალითად, როდესაც დროთა განმავლობაში შესწავლილი პროცესის ცვლილებები შეიძლება უგულებელყოთ. ასეთი მოდელირების შესახებ მენეჯმენტის გადაწყვეტილებას აქვს აზრი ან სისტემის სტაბილურობის პირობებში, ან მომავალში მოკლე პერიოდის განმავლობაში.

რეალურად ყველა ეკონომიკური პროცესი და ფენომენი დროთა განმავლობაში ფუნქციონირებს და ვითარდება, ანუ დინამიური ხასიათისაა. ეს მოითხოვს მენეჯერებს პრაქტიკული პრობლემების გადაჭრას, რომლებშიც აუცილებელია დროთა განმავლობაში ეკონომიკური პროცესების შესაძლო ცვლილებების გათვალისწინება, იმ პირობით, რომ პროცესი შეიძლება იყოს კონტროლირებადი, ანუ გავლენა მოახდინოს მისი განვითარების კურსზე.

დინამიური პროგრამირება არის მათემატიკური აპარატურა, რომლის დახმარებით წყდება მრავალსაფეხურიანი ოპტიმალური მართვის ამოცანები. ასეთ პროგრამირებაში, პროცესის გასაკონტროლებლად, ყველა შესაძლო გადაწყვეტილებების ერთობლიობას შორის, ეძებს ოპტიმალურს გარკვეული კრიტერიუმის გაგებით, ანუ გამოსავალი, რომელიც იძლევა ობიექტური ფუნქციის უკიდურეს (მეტ-ნაკლებად) მნიშვნელობას. - პროცესის ზოგიერთი რიცხვითი მახასიათებელი. მრავალსაფეხურიანი ეხება ან პროცესის მრავალსაფეხურიან სტრუქტურას, ან კონტროლის განაწილებას რამდენიმე თანმიმდევრულ ეტაპად, რომლებიც, როგორც წესი, შეესაბამება დროის სხვადასხვა წერტილს. ამრიგად, სიტყვა „პროგრამირება“ ნიშნავს მენეჯმენტის გადაწყვეტილებების მიღებას, ხოლო სიტყვა „დინამიური“ მიუთითებს განხილულ პროცესებსა და მეთოდებში ოპერაციების დროისა და რიგის არსებით მნიშვნელობაზე.

დინამიური პროგრამირების ამოცანები მოიცავს დაგეგმვის, ინვესტიციების განაწილების, ინვენტარის მენეჯმენტის, მიმდინარე და ძირითადი რემონტის ამოცანებს, სარეკლამო მეთოდების შერჩევას და სხვა.

ზოგიერთ დინამიურ პროგრამირების პრობლემაში მართვის პროცესი ბუნებრივად იყოფა ეტაპებად, მაგალითად, თვეში, კვარტალში, წელიწადში. სხვა სიტუაციებში, ეტაპებად დაყოფა შეიძლება იყოს პირობითი. ყველა დინამიური პროგრამირების პრობლემის თავისებურება ის არის, რომ თითოეულ ეტაპზე შესაძლებელია წინა ცვლილებების გათვალისწინება, მოვლენების მიმდინარეობის კონტროლი, ასეთი კონტროლის ხარისხის შეფასებისას. ასე რომ, დინამიური პროგრამირება საშუალებას გაძლევთ მიიღოთ მენეჯმენტის მთელი რიგი გადაწყვეტილებები და უზრუნველყოთ სისტემის ოპტიმალური განვითარება მთლიანად.

განვიხილოთ ამ პროგრამირების პრობლემის ზოგადი ფორმულირება. მოდით გამოვიკვლიოთ რამდენიმე ეკონომიკური პროცესი, რომელსაც აქვს n თანმიმდევრული ეტაპი. ყოველ მე-7 ეტაპზე პროცესი შეიძლება იყოს სხვადასხვა მდგომარეობაში, რომელთაგან თითოეული ხასიათდება პარამეტრების სასრული ნაკრებით. ამოცანის თითოეული ეტაპი დაკავშირებულია მენეჯმენტის გარკვეული გადაწყვეტილების მიღებასთან, რომელიც სისტემას ერთი მდგომარეობიდან მეორეში გადააქვს. ვარაუდობენ, რომ სისტემის si მდგომარეობა მე-7 ეტაპის ბოლოს განისაზღვრება მხოლოდ წინა მდგომარეობით si_1 და კონტროლი xi მე-7 ეტაპზე და არ არის დამოკიდებული წინა მდგომარეობებზე და კონტროლებზე. შემდეგ სისტემის მდგომარეობა si იწერება დამოკიდებულების სახით

Si = f (in, _!, Xi), i = 1, P.

მთელი მენეჯმენტის პროცესის ეფექტურობა შეიძლება წარმოდგენილი იყოს როგორც მენეჯმენტის გადაწყვეტილებების ეფექტურობის ჯამი ცალკეულ ეტაპებზე, ე.ი.

ზემოაღნიშნულ პირობებში, დინამიური პროგრამირების პრობლემა ჩამოყალიბებულია შემდეგნაირად: განისაზღვროს მენეჯმენტის გადაწყვეტილებების ასეთი დასაშვები თანმიმდევრობა X = (x1, x2, xn), რომელიც გადასცემს სისტემას საწყისი მდგომარეობიდან 50 საბოლოო მდგომარეობამდე sn და რომლის მართვის მაქსიმალური ეფექტურობა მიიღწევა.

მრავალსაფეხურიანი მენეჯმენტის პროცესის დაგეგმვისას, დინამიური პროგრამირების პრობლემებში აუცილებელია თითოეულ ეტაპზე მენეჯმენტის გადაწყვეტილების შერჩევა, მისი შედეგების გათვალისწინებით იმ ეტაპებზე, რომლებიც ჯერ კიდევ მოვა. მხოლოდ ბოლო ეტაპზეა შესაძლებელი მენეჯმენტის გადაწყვეტილების მიღება, რომელიც მაქსიმალურ ეფექტს მისცემს, რადგან შემდეგი ნაბიჯი მისთვის არ არსებობს. ამიტომ, დინამიური პროგრამირების პრობლემები მოგვარებულია ბოლომდე.

მიზნობრივი ფუნქციის მაქსიმუმი ბოლო n საფეხურზე უდრის

^ n-O = შემოწმება / n ^ n-i xn).

შესაბამისად, (n - 1) -სტადიაზე გვაქვს

r * n-1 (5n-2) = ShaX ((fn-1 (sn-2, xn-1) + r * n ^ n-1)).

ამ კანონზომიერების გათვალისწინებით, თვითნებური k-სტადიისთვის შეგვიძლია დავწეროთ განმეორებადი დამოკიდებულება

g * (მეხუთე-1) = შაჰი (L (ik-1, xk) + g * + 1)).

ეს განმეორებადი დამოკიდებულება არის ბელმანის ოპტიმალური პრინციპის მათემატიკური წარმოდგენა.

განმეორებითი დამოკიდებულებების გამოყენებით საწყის ეტაპზე პირობითად ოპტიმალური ეფექტის დადგენის შემდეგ, კონტროლის უპირობო ოპტიმიზაცია ხორციელდება "საპირისპირო" მიმართულებით, რის შედეგადაც აღმოჩენილია მენეჯმენტის გადაწყვეტილებების თანმიმდევრობა, რომელიც უზრუნველყოფს სისტემის მაქსიმალურ ეფექტურობას. .

დინამიური პროგრამირების მეთოდის ძირითადი მახასიათებლები

1. დინამიური პროგრამირების იდეა და მეთოდი უფრო შესაფერისია დისკრეტული პრობლემებისთვის, რომლებიც უმეტეს შემთხვევაში საკონტროლო პრობლემებია.

2. დინამიური პროგრამირების მეთოდის გამოყენება შესაძლებელია ობიექტური ფუნქციის დაზუსტების ნებისმიერი მეთოდით და მდგომარეობისა და კონტროლის ნებისმიერი დასაშვები ნაკრებით. კლასიკური ოპტიმიზაციის მეთოდებს და მათემატიკური პროგრამირების სხვა გამოთვლით მეთოდებს არ გააჩნია ეს უპირატესობა.

3. დინამიური პროგრამირების მეთოდის გამოთვლითი სქემები დისკრეტულ შემთხვევაში, რომელიც დაკავშირებულია ეფექტურობის და კონტროლის ინდიკატორის ოპტიმალური მნიშვნელობების დახარისხებასთან k-th საფეხურზე მდგომარეობის ცვლადის ყველა შესაძლო მნიშვნელობისთვის, მაგრამ გამოთვლების მოცულობა. მნიშვნელოვნად ნაკლებია, ვიდრე პარამეტრების პირდაპირი დახარისხება. ეს გამოწვეულია იმით, რომ პირობითი ოპტიმიზაციის ეტაპზე, წარუმატებელი ვარიანტები დაუყოვნებლივ უგულებელყოფილია და მხოლოდ ის, რაც ამ ეტაპზე პირობითად ოპტიმალურია, ინახება.

4. დინამიური პროგრამირების მეთოდი შესაძლებელს ხდის გაანალიზდეს სქ მდგომარეობების საწყისი მონაცემების ცვლილებებისადმი და მათი რიცხვი n ფაქტობრივად, აქ ყოველ საფეხურზე წყდება არა ერთი პრობლემა, არამედ მრავალი მსგავსი პრობლემა სხვადასხვა მდგომარეობებისთვის sk და განსხვავებული კ (1<к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

დასკვნები

1. არაწრფივი მოდელების გაჩენა დაკავშირებულია არაწრფივი შაბლონების გათვალისწინებისა და დემონსტრირების აუცილებლობასთან, რომლებიც გავლენას ახდენენ გადაწყვეტილების ოპტიმალურ მიღებაზე. ასეთი შაბლონები შედის პრობლემის შეზღუდვებში და ობიექტურ ფუნქციაში.

2. ფუნქციებისა და შეზღუდვების ხასიათის მიხედვით, რომლებიც აღწერს არაწრფივი პროგრამირების ამოცანებს, ისინი შეიძლება დაიყოს შემდეგნაირად: კლასიკური ოპტიმიზაციის ამოცანები; არაწრფივი ობიექტური ფუნქციის და წრფივი შეზღუდვების პრობლემები; ამოზნექილი, კვადრატული, განცალკევებული პროგრამირების პრობლემები.

3. წრფივი პროგრამირების ამოცანებისგან განსხვავებით, არ არსებობს არაწრფივი ამოცანების ამოხსნის უნივერსალური მეთოდი. თითოეულ კონკრეტულ შემთხვევაში აუცილებელია საუკეთესო მეთოდის არჩევა.

4. დინამიური პროგრამირება არის მათემატიკური აპარატურა, რომლის დახმარებით წყდება მრავალსაფეხურიანი ოპტიმალური მართვის ამოცანები. მრავალხარისხიანი გაგებულია, როგორც პროცესის მრავალსაფეხურიანი სტრუქტურა, ან კონტროლის განაწილება რამდენიმე თანმიმდევრულ ეტაპად, რომლებიც, როგორც წესი, შეესაბამება დროის სხვადასხვა წერტილს.

5. დინამიური პროგრამირების ამოცანები მოიცავს დავალებებს დაგეგმვის, ინვესტიციების განაწილების, ინვენტარის მართვის, მიმდინარე და ძირითადი რემონტის, სარეკლამო მეთოდების შერჩევას და სხვა. ყველა დინამიური პროგრამირების პრობლემის თავისებურება ის არის, რომ ყოველ ეტაპზე შესაძლებელია წინა ცვლილებების გათვალისწინება და მოვლენების მიმდინარეობის კონტროლი, ასეთი კონტროლის ხარისხის შეფასებისას.

6. დინამიური პროგრამირების ამოცანების ამოხსნა ეფუძნება ბელმანის ოპტიმალურობის პრინციპს. დინამიური პროგრამირების კონტროლის ოპტიმიზაციის პროცესში მრავალსაფეხურიანი პროცესი ორჯერ ხორციელდება. პირველად არის ბოლოდან დასაწყისამდე, რის შედეგადაც გვხვდება პირობითად ოპტიმალური კონტროლი. მეორე არის თავიდან ბოლომდე, რის შედეგადაც ხდება პროცესის ოპტიმალური კონტროლი მთლიანობაში.

დინამიური პროგრამირება.

ქსელის სტრუქტურების მოდელირებისას, ტრანსპორტში, ელექტრო, სატელეფონო, კომპიუტერულ და სხვა ტიპის ქსელებში ნაკადების არსებობასთან დაკავშირებული პრობლემების გარდა, წარმოიქმნება პრობლემების მთელი კლასი, რომელიც შეიძლება შემცირდეს უმოკლესი გზის პრობლემამდე. მაგალითად, უმოკლესი გზის პრობლემას წყვეტს ყოველ ჯერზე როუტერის პროგრამა, როცა საიტი ინტერნეტში მისი სახელით არის ნაპოვნი.

მიმართულ ქსელში უმოკლესი გზის პრობლემა არის ტიპიური დინამიური პროგრამირების პრობლემა, ამიტომ, თუმცა დინამიური პროგრამირება, ისევე როგორც ქსელის დაგეგმვა, დაკავშირებულია დროთა განმავლობაში პროცესების განვითარებასთან, რომლის მოდელირება უფრო დეტალურად განიხილება შემდეგ ნაწილში. , ამ განყოფილებაში განვიხილავთ დინამიური პროგრამირების მეთოდს უმოკლესი გზის პოვნის მაგალითზე.

დინამიური პროგრამირების კონცეფცია მჭიდრო კავშირშია მრავალსაფეხურიანი პროცესებიგადაწყვეტილების მიღება. გადაწყვეტილების მიღების მრავალსაფეხურიანი პროცესი შეიძლება განისაზღვროს, როგორც თანმიმდევრული გადაწყვეტილებების მიღების პროცესი, რომელიც მიმართულია მოცემული მიზნის მისაღწევად. გადაწყვეტილების მიღების მრავალსაფეხურიანი პროცესები მუდმივად გვხვდება მრავალფეროვან სიტუაციებში, მანქანის შეკეთებიდან მანქანის სარემონტო მაღაზიაში და კოსმოსური ხომალდის კონტროლამდე.

დინამიური პროგრამირება შეიძლება თავისუფლად განისაზღვროს, როგორც მათემატიკური პროცედურების ერთობლიობა, რომელიც გამოიყენება გადაწყვეტილების მიღების მრავალსაფეხურიანი პროცესების ანალიზში. ყოველი მრავალსაფეხურიანი გადაწყვეტილების პროცესი არის შემდეგი პრობლემის ევოლუცია: უმოკლესი გზის პოვნა მიმართულ, აციკლურ ქსელში.

დინამიური პროგრამირება შეიძლება ჩაითვალოს ერთიან თეორიად იდეებისა და ტექნიკის ერთი ნაკრების გამო, რომლებიც გამოიყენება სხვადასხვა ამოცანების მათემატიკური ანალიზისას. ეს იდეები და ტექნიკა არის დინამიური პროგრამირების არსი. ბელმანმა ერთ-ერთმა პირველმა გაიგო ოპტიმალური პრინციპის არსი და დაიწყო მისი გამოყენება მათემატიკაში, ინჟინერიაში, ოპერაციების კვლევაში და სხვა სფეროებში წარმოქმნილი ოპტიმიზაციის მრავალი პრობლემისთვის.

ამრიგად, დინამიური პროგრამირების კონცეფცია დაკავშირებულია გადაწყვეტილების მიღების მრავალსაფეხურიან პროცესთან კონკრეტული მიზნის მისაღწევად. მაგალითად, თვითმფრინავის ერთი ორბიტიდან მეორეზე გადატანა ტიპიური დინამიური პროგრამირების პრობლემაა, იმ პირობით, რომ ორბიტის კორექტირება განხორციელდება იმპულსების გამოყენებით დისკრეტულ დროს და მიზანია საწვავის დაზოგვა.

დინამიური პროგრამირების დახასიათება, როგორც მათემატიკური პროცედურების ერთობლიობა დისკრეტული სისტემის ოპტიმალური კონტროლისთვის, ზოგადად, ოპტიმალური მართვის პრობლემა შეიძლება ჩამოყალიბდეს შემდეგნაირად. დროის დისკრეტულ მომენტებში ტ= 1, 2,..., N სისტემა არის s i მდგომარეობების ერთ-ერთ სიმრავლეში, რომელსაც ახასიათებს x (t) მდგომარეობის ვექტორი. თანმიმდევრულ მდგომარეობებს შორის გადასვლა ხორციელდება საკონტროლო ვექტორის გამოყენებით u (t) კანონის შესაბამისად:

x (ტ) = გ (ტ) (x (ტ) , u (ტ)) ; ტ= 1, 2,..., ნ

კონტროლი u (t) შეირჩევა დასაშვები კონტროლის სიმრავლიდან და ქმნიან დასაშვები კონტროლის თანმიმდევრობას u (0) ,u (1) ,…,u (N) . დასაშვები კონტროლის თანმიმდევრობა მოცემული საწყისი მდგომარეობისთვის x (0) განსაზღვრავს სისტემის ტრაექტორიას x (0), x (1), x (2),…, x (N).

თითოეული ტრაექტორია შეესაბამება ოპტიმალური კრიტერიუმის F-ის საკუთარ მნიშვნელობას, ან სამიზნე კონტროლის ფუნქციას, რომელიც შედგება ინდივიდუალური წვლილისაგან კონტროლის თითოეულ ეტაპზე:

კონტროლის ოპტიმალური პრობლემაა საკონტროლო მიმდევრობების სიმრავლეს შორის ისეთის პოვნა, რომელიც მიაღწევს F-ის მინიმალურ მნიშვნელობას. ასეთ თანმიმდევრობას ეწოდება ოპტიმალური კონტროლის თანმიმდევრობა და განსაზღვრავს ოპტიმალურ ტრაექტორიას.

დინამიური პროგრამირება ეფუძნება ბელმანის ოპტიმალურობის პრინციპს, რომელიც შეიძლება ჩამოყალიბდეს შემდეგნაირად. ოპტიმალურ სტრატეგიას აქვს ის თვისება, რომ როგორიც არ უნდა იყოს საწყისი მდგომარეობა და გადაწყვეტილება საწყის მომენტში, შემდგომმა გადაწყვეტილებებმა უნდა ჩამოაყალიბონ ოპტიმალური სტრატეგია იმ მდგომარეობის მიმართ, რომელიც წარმოიქმნება საწყისი გადაწყვეტილების შემდეგ.

ოპტიმალურობის პრინციპის მნიშვნელობა უფრო ნათელი ხდება, თუ გავითვალისწინებთ, რომ ოპტიმალური ტრაექტორიისთვის, ბოლო წერტილსა და ნებისმიერ შუალედურ წერტილს შორის თითოეული მონაკვეთი ასევე ოპტიმალური ტრაექტორიაა. ოპტიმალური პრინციპი, ან სხვაგვარად დინამიური პროგრამირების მეთოდი, საშუალებას გაძლევთ იპოვოთ ოპტიმალური მრავალსაფეხურიანი სტრატეგია უფრო მარტივი ერთსაფეხურიანი ოპტიმიზაციის პრობლემების გადაჭრით.

დინამიური პროგრამირების მეთოდი კარგად არის ილუსტრირებული ორიენტირებული ქსელის უკიდურეს კვანძებს შორის უმოკლესი გზის პოვნის მაგალითით. განვიხილოთ ზოგიერთი მიმართული ქსელი 12 კვანძით, რომელიც უნდა გაიაროს საწყისი კვანძიდან (1) ბოლო კვანძამდე (12) ოთხი ნაბიჯით, გადაადგილება კვანძიდან კვანძში ყოველი ნაბიჯით.

ბრინჯი. 6.4.1. მიმართული ქსელის გავლა უმოკლესი გზის გასწვრივ.

რკალებზე მითითებული რიცხვები ( მე, ჯ) ტოლია რკალების სიგრძისა ლ იკვანძებს შორის მედა ჯ(ჩვეულებრივ ერთეულებში). სისტემის s i-ს შესაძლო მდგომარეობები ამ შემთხვევაში ასოცირდება ყოფნასთან მეე კვანძი, კონტროლი u(t) ასოცირდება გზის მიმართულების არჩევასთან ყოველ საკონტროლო საფეხურზე. საკონტროლო ოთხი საფეხური u (1),...,u (4) თანმიმდევრულად გადასცემს სისტემას საწყისი მდგომარეობიდან s 1 საბოლოო მდგომარეობიდან s 12-ში და, ამრიგად, ქმნის გარკვეულ ტრაექტორიას, რომელიც უნდა მოიძებნოს. ოპტიმალური კრიტერიუმი F ამ შემთხვევაში არის ტრაექტორიის სიგრძე ლ, რომელიც შედგება ცალკეული რკალების სიგრძისგან:

თუ უმოკლესი გზის, ანუ ოპტიმალური ტრაექტორიის ძიება იწყება არა ქსელის დასაწყისიდან, არამედ ბოლოდან და მოძრაობს დასაწყისის საპირისპირო მიმართულებით, მაშინ ამ შემთხვევაში გვაქვს „უკუღმა სვიპის“ ალგორითმი. ამ შემთხვევაში, უკან დახევის ალგორითმის განხორციელებისას მოძრაობა ხორციელდება საბოლოო მდგომარეობიდან s 12 საწყის მდგომარეობამდე s 1-მდე.

უმოკლესი გზის ძიების დასაწყისში დგება გარდამავალი ცხრილი. ცხრილის სტრიქონების რაოდენობა უდრის საკონტროლო ნაბიჯების რაოდენობას, სვეტების რაოდენობა უდრის მდგომარეობების რაოდენობას მინუს ერთი. ეს ცხრილი შეინახავს საკონტროლო ნაბიჯებს და ოპტიმალური კრიტერიუმის L t შესაბამის მნიშვნელობებს სისტემის ყველა შესაძლო მდგომარეობისთვის ყოველი ნაბიჯის შემდეგ.

ცხრილი 6.4.1

მე ტ	s 1	s 2	s 3	s 4	ს 5	S 6	s 7	s 8	ს 9	ს 10	s 11
									12	12 6
						10	11 10
			5
1

ცხრილის შევსებული უჯრები იყოფა შუაზე. კონტროლი u(t) შედის შევსებული უჯრედის ზედა ნაწილში, ანუ, ამ შემთხვევაში, იმ კვანძის ნომერი, რომელზეც ხდება გადასვლა. Lt წვლილის მნიშვნელობა L ოპტიმალური კრიტერიუმის ჯამურ მნიშვნელობაში, რომელიც მიღებული იყო ამ უჯრედის შესაბამისი კვანძიდან საბოლოო კვანძში გადასვლისას, შეყვანილია შევსებული უჯრედის ქვედა ნაწილში.

ცხრილის შევსება იწყება პირველი ხაზით, სადაც ინახება ინფორმაცია ბილიკის ბოლო საფეხურის შესახებ. ბოლო, ამ შემთხვევაში, ბილიკის მეოთხე საფეხური ცალსახად განისაზღვრება ნებისმიერი ბოლო მდგომარეობიდან გადასვლისას, რომელიც შეიძლება იყოს სამი შესაძლოდან რომელიმე: s 9, s 10, s 11. ამიტომ, ოპტიმალური კონტროლი ბოლო ეტაპზე აშკარაა. ბოლო მდგომარეობიდან გამომდინარე, ოპტიმალურობის კრიტერიუმში წვლილი არის L 4 (9) = 12, L 4 (10) = 6, ან L 4 (11) = 7. ეს წვლილი მნიშვნელობები L იწერება ბოლოში. ცხრილის პირველი რიგის უჯრედები. 6.4.1.

წინაბოლო - ამ შემთხვევაში, მესამე - საფეხურამდე, სისტემის შესაძლო მდგომარეობების ნაკრები არის (s 5, s 6, s 7, s 8). ახლა გამოვიყენოთ ბელმანის პრინციპი მესამე და მეოთხე საფეხურზე ტრაექტორიის დასადგენად. ის მდგომარეობს იმაში, რომ კონტროლის პირველი ორი საფეხურის მიუხედავად, ბოლო ორ საფეხურზე ტრაექტორიის სეგმენტი თავისთავად არის ოპტიმალური ტრაექტორია, ე.ი. იძლევა L 3-ის მინიმალურ წვლილს ოპტიმალურობის კრიტერიუმში.

თუ სისტემის მდგომარეობა ბოლო საფეხურამდე არის მდგომარეობა s 8, მაშინ ბოლო საფეხურებზე წვლილი L-ში განისაზღვრება მიმართებით.

L 3 (s 5)=წთ( }.

ვინაიდან s 5-დან შესაძლებელია გადასვლები s 9-ზე და s 11-ზე, ე.ი.

g(s 5,9) = s 9; ; L 4 (s 9) = 12,

g(s 5,11) = s 11; ; L 4 (s 11) = 7,

L 3 (s 5) = min(6+12, 4+7) = 11 და u (3) = 11.

ეს ნიშნავს, რომ თუ სისტემა s 5 მდგომარეობაშია, მაშინ ოპტიმალური კონტროლი შედგება ჯერ s 11 მდგომარეობაში, შემდეგ s 12 მდგომარეობაში. რკალის სიგრძე s 5-დან s 12-მდე აღმოჩნდება 11 ერთეულის ტოლი.

s 6, s 7, s 8 მდგომარეობებიდან გადასვლებისთვის L-ში წვლილის ანალოგიურად გამოანგარიშებით, მივიღებთ შემდეგ შენატანებს:

L 3 (s 6)=min(7+12, 6+6)=12, u (3) =10;

L 3 (s 7)=min(5+6, 3+7)=10, u (3) =11;

L 3 (s 8)=min(10+6, 12+7)=16, u (3) =10;

შედეგად მიღებული ოთხი წყვილი რიცხვი იწერება ცხრილის მეორე სტრიქონში. 6.4.1.

მეორე საკონტროლო საფეხურზე ოპტიმალური კრიტერიუმში წვლილი საწყის მდგომარეობაზეა დამოკიდებული

L 2 (s 2) = min( ) = min(11+11, 14+10) = 22, u (2) = 5;

L 2 (s 3) = min( ) = min(7+11, 9+12) = 18, u (2) = 5;

L 2 (s 4) = min( ) = min(2+16, 3+12, 6+10) = 15, u (2) = 6;

შედეგად მიღებული სამი წყვილი რიცხვი იწერება 6.4.1 ცხრილის მესამე სტრიქონში.

საწყისი მდგომარეობა s 1 ცალსახად არის განსაზღვრული, ამიტომ ცხრილის ბოლო სტრიქონში ივსება ერთადერთი უჯრა, სადაც 3 და 24 მნიშვნელობები იწერება, რადგან:

L 1 (s 1) = წთ ) = წთ(5+22, 6+18, 11+15) = 24, u (1) = 3.

ახლა ჩვენ საბოლოოდ შეგვიძლია განვსაზღვროთ ოპტიმალური მრავალსაფეხურიანი კონტროლის თანმიმდევრობა. პირველ საფეხურზე u (1) = 3, ე.ი. 1 კვანძიდან მივდივართ მე-3 კვანძში, მეორე საფეხურზე u (2) = 5, ე.ი. მივდივართ 5 კვანძში, შემდეგ კონტროლის შემდეგ u (3) = 11 - 11 კვანძში და ბოლოს კვანძში 12. საბოლოოდ ვიღებთ, რომ უმოკლეს გზას ქსელში, რომელიც ნაჩვენებია ნახ. 6.4.1, გადის s 1 →s 2 →s 5 →s 11 →s 12 მდგომარეობების თანმიმდევრობით და მისი სიგრძე 24 ჩვეულებრივი ერთეულია.

უმოკლესი გზის ძიება ასევე შეიძლება განხორციელდეს ქსელის დასაწყისიდან, წინ გადადგმული ალგორითმის დანერგვისას, რომელიც არსებითად ასრულებს იგივე დამატებისა და შედარების ოპერაციებს, მაგრამ ოდნავ განსხვავებული თანმიმდევრობით.

წინ და უკან სვლის ალგორითმები, თუმცა არსებითად განსხვავებულია, იძლევა ერთ დამატებას და ერთ შედარებას თითო რკალზე. ამრიგად, ორივე ალგორითმს აქვს იგივე შესრულება. თუმცა, არის მნიშვნელოვანი განსხვავება. წინ გადაადგილების ალგორითმი ითვალისწინებს რკალებს გამავალიიმ კვანძებიდან, უმოკლესი ბილიკები მე მერომლებიც უკვე ცნობილია.

უკან დახევის ალგორითმი ითვალისწინებს რკალებს შემომავალიიმ კვანძებისკენ, უმოკლესი გზებისკენ ლ ჯრომლისთვისაც ჯერჯერობით უცნობია. ამ უკანასკნელი გარემოებიდან გამომდინარე, უპირატესობა ხშირად ენიჭება პირდაპირი სვიპის ალგორითმს. ეს ალგორითმი შეიძლება გამოყენებულ იქნას უმოკლესი ბილიკის ნაკრების ნებისმიერ სტრუქტურაზე.

მარტივი უმოკლესი გზის პრობლემის გადაჭრა ასახავს შემდეგ დამახასიათებელ მახასიათებლებს, რომლებიც თან ახლავს ბევრად უფრო რთულ მრავალსაფეხურიან გადაწყვეტილების მიღების პროცესს:

1. ორიგინალური პრობლემა ჩაფლულია მრავალ ოპტიმიზაციის პრობლემაში; ამ შემთხვევაში, თითოეული კვანძი წყვეტს საკუთარ პრობლემას.

2. ოპტიმიზაციის ამოცანების ამონახსნების ერთობლიობა აღწერილია ფუნქციური განტოლებით, რომელიც წარმოადგენს განტოლებათა სისტემას, რომელიც აკავშირებს რამდენიმე ოპტიმიზაციის პრობლემას. ასეთ სისტემაში თითოეული განტოლება შეესაბამება ერთ კვანძს და ჩვეულებრივ შეიცავს ოპერატორებს, როგორიცაა min, max ან minimax ტოლობის ნიშნის მარჯვნივ და ცვლადებს, როგორიცაა g i და g j მის ორივე მხარეს.

3. ოპტიმიზაციის მრავალი პრობლემის გადაწყვეტა შეიძლება მოიძებნოს უკუღმა სვიპის ალგორითმის გამოყენებით, რომელიც უდრის ფუნქციონალური განტოლებების თანმიმდევრობის ამოხსნის შეკვეთილ პროცედურას.

დინამიური პროგრამირება კარგად არის შესაფერისი ქსელის სისტემების მოდელირებასთან დაკავშირებული პრობლემების გადასაჭრელად, რომლებსაც არ აქვთ სპეციალური სტრუქტურა. ამრიგად, წინ და უკან გადაადგილების ალგორითმები შესაფერისია აციკლურ ქსელებში გამოთვლების შესასრულებლად. უკან დახევის ალგორითმი შეიძლება განზოგადდეს და გამოიყენოს პრობლემების გადასაჭრელად, რომელშიც არის შემთხვევითობის ელემენტი. ეს არ შეიძლება გაკეთდეს წინ გადაადგილების ალგორითმისთვის.

ცნება "სახელმწიფო" ცენტრალურ როლს თამაშობს დინამიურ პროგრამირებაში, მდგომარეობების გაგება შემდეგნაირად. გადასვლა ხორციელდება მდგომარეობიდან მდგომარეობაზე, რომელიც შეიცავს პროცესის მთელ ისტორიას, ანუ მდგომარეობა აღწერილია ისეთი დეტალებით, რაც საშუალებას იძლევა გამოთვალოს (შეფასებას) მიმდინარე ალტერნატიული გადაწყვეტილებები.

ქსელის მოდელისთვის მდგომარეობები არის კვანძები, ხოლო გარკვეული კვანძიდან გამომავალი რკალი წარმოადგენს სხვადასხვა გადაწყვეტილებებს, რომლებიც შეიძლება მიღებულ იქნეს ამ კვანძზე (მდგომარეობაში). ამ ინტერპრეტაციით შეგვიძლია ვთქვათ, რომ გადასვლა ხდება შტატიდან შტატში და სახელმწიფოები წარმოადგენს წერტილებს, რომლებზეც მიიღება გადაწყვეტილებები. ზემოაღნიშნული განცხადება ნიშნავს, რომ კვანძიდან გამოსულ რკალებს არავითარი კავშირი არ აქვთ იმ გზასთან, რომლითაც მიაღწიეს ამა თუ იმ კვანძს, ანუ ისინი არ არიან დამოკიდებული შემომავალ რკალებზე.

სახელმწიფო ელემენტებს ხშირად უწოდებენ მდგომარეობის ცვლადები.დინამიური პროგრამირების მოდელებში მდგომარეობები ზოგჯერ ჯგუფდება ეტაპებად და ხდება გადასვლა ერთი ეტაპიდან მეორეზე. მაგალითად, უმოკლესი გზის პრობლემაში არის მდგომარეობები, მაგრამ არ არსებობს ეტაპები, რადგან შეუძლებელია მდგომარეობების დაჯგუფება ნაკრებებად ისე, რომ მოხდეს გადასვლა ერთი სიმრავლიდან მეორეზე.

ოპტიმიზაციის სხვადასხვა პრობლემებში ჩაძირვა კონცეფციის დანერგვის ტოლფასია სახელმწიფო სივრცერომელიც წარმოადგენს სახელმწიფოთა ერთობლიობას. ფუნქციურ განტოლებაში ოპტიმალური პასუხი განიხილება, როგორც საწყისი მდგომარეობის ფუნქცია, ხოლო ოპტიმალურის პრინციპი ადგენს ურთიერთობას ოპტიმალურ პასუხებს შორის სხვადასხვა საწყისი მდგომარეობისთვის.

ბევრი სშესაძლო (ან დაკვირვებად) მდგომარეობებს უწოდებენ სახელმწიფო სივრცე,და ელემენტი სსაწყისი სგანსაზღვრავს კონკრეტულს სახელმწიფო.ყველა პირობით სბევრი დაკავშირებული დ(ს) . ელემენტი დბევრისგან დ(ს) ეწოდება გადაწყვეტილება.წესს, რომლის მიხედვითაც თითოეული სახელმწიფოსთვის დგინდება შესაძლებელი გადაწყვეტა, ეწოდება სტრატეგიად.

რეალურად სტრატეგია d შეესაბამება თითოეულ შტატს სრაღაც ელემენტი d( ს) ბევრისგან დ(ს). ყველა ასეთი დ ფორმის სიმრავლე სტრატეგიის სივრცედ. ეს უკანასკნელი ნიშნავს, რომ გადაწყვეტის არჩევა რომელიმე სახელმწიფოში არ ზღუდავს არჩევანს ყველა სხვა მდგომარეობაში. არსებითად, D არის კომპლექტების დეკარტისეული პროდუქტი დ(ს) მიერ ს.

დინამიური პროგრამირების ერთ-ერთი იდეა არის ის, რომ თითოეულ სტრატეგიას d უნდა ჰქონდეს ე.წ. მოგების ფუნქცია ვდ(ს), რომლის მიღება შესაძლებელია სახელმწიფოს საფუძველზე სდა სტრატეგიის გამოყენებით დ. მოგების ფუნქციის (ან შემოსავლის) კონცეფცია განაზოგადებს L t კონტრიბუციის კონცეფციას ოპტიმალური კრიტერიუმის L მთლიან მნიშვნელობამდე, რომელიც განიხილება უმოკლესი გზის ამოცანის გადაჭრისას.

გამოთქმა „სტრატეგიის გამოყენება d“ ნიშნავს, რომ შენ შეგიძლია სხსნარი დ( ს); შემდეგ ითვლება, რომ პროცესი შევიდა სახელმწიფოში ს“, ანუ სახელმწიფო რეალიზებულია ს", რომელშიც ხსნარი d( ს") და ა.შ. მოგების ფუნქციას აქვს საკმაოდ რთული სტრუქტურა, რადგან ის დამოკიდებულია მდგომარეობებისა და გადაწყვეტილებების თანმიმდევრობაზე, ჯილდოებზე, რომლებიც დაკავშირებულია ამ მდგომარეობებთან და გადაწყვეტილებებთან, აგრეთვე ჯილდოების აგრეგაციის გზაზე.

მდგომარეობა არის პროცესის ისტორიის აღწერა დეტალური დონით, რომელიც საშუალებას იძლევა შეფასდეს მიმდინარე ალტერნატიული გადაწყვეტილებები. სახელმწიფოთა მთავარი საკუთრება ის არის, რომ სახელმწიფო არის პროცესის ისტორიის მოკლე ჩანაწერი და დეტალების ხარისხისაშუალებას გვაძლევს განვსაზღვროთ ადგილობრივი შემოსავლის ფუნქცია. სხვა სიტყვებით რომ ვთქვათ, ადგილობრივი შემოსავლის ფუნქცია შეიძლება მხოლოდ დამოკიდებული იყოს ს, დდა ვ.

მომდევნო თავში უფრო დეტალურად განიხილება მარკოვის ჯაჭვები, რომლებსაც დიდი მნიშვნელობა აქვთ წარმოებისა და ტექნიკური სისტემების დროული ევოლუციის მოდელირებისთვის. ასევე არსებობს მარკოვის გადაწყვეტილების მიღების მოდელები, რომლებშიც სახელმწიფო სგანისაზღვრება რამდენიმე წყვილი რიცხვით (n, i), გამოსავალი არის მათზე დამოკიდებული ფუნქცია კდა ადგილობრივი შემოსავლის ფუნქცია განისაზღვრება მსგავსი გამონათქვამით თ[(ნ, მე) , კ, ვ] = რ კ ი(ნ) + å ჯ პ კ იჯ(ნ)ვ(n+ 1, ჯ) (ნ ).

მარკოვის გადაწყვეტილების მიღების მოდელები განზოგადებულია სხვადასხვა მიმართულებით, კერძოდ, საქმეზე მარკოვის რეკონსტრუქციის პრობლემები. ყველაზე სასარგებლო განზოგადება მიიღება, როდესაც განიხილება არათანაბარი ან ცვლადი გადასვლის დრო. მარტივ მოდელებში, ვარაუდობენ, რომ მდგომარეობიდან მდგომარეობაზე გადასვლა და მდგომარეობაზე დაკვირვება მყისიერია, ხოლო მდგომარეობიდან მდგომარეობაზე გადასვლას შორის დროის მონაკვეთს შეიძლება ჰქონდეს ცვლადი ან შემთხვევითი სიგრძე.

როდესაც მდგომარეობა დაფიქსირდა, გამოსავალი არჩეულია და არ შეიძლება შეიცვალოს მანამ, სანამ პროცესი არ გადავა ახალ მდგომარეობაში, სადაც შეირჩევა ახალი გამოსავალი და ა.შ. ეს მოდელი არის მარკოვის ჯაჭვის თეორიისა და აღდგენის თეორიის კომბინაცია; ჩვეულებრივ უწოდებენ მარკოვის რეკონსტრუქციის პრობლემა.

ტესტის კითხვები მე-6 თავისთვის.

1. რა კომპონენტებისგან შედგება მიმართული ქსელი?

1. როგორ არის აგებული ქსელის სიმძლავრის მატრიცა?

1. როგორ იქმნება ქსელის ნაკადის მატრიცა?

1. რატომ აკლდება სიმძლავრის და დინების მატრიცები?

1. რა არის ქსელის დიაგრამა და რისთვის გამოიყენება?

1. როგორ განისაზღვრება სამუშაოს ადრეული დაწყების და ადრეული დასრულების დრო?

1. რა არის ჯამური float ზოგიერთი მოვლენისთვის ქსელის დიაგრამაზე?

1. როგორ განისაზღვრება კრიტიკული გზა?

1. რას ეწოდება გარკვეული სისტემის მდგომარეობის ვექტორი?

1. როგორია სისტემის ტრაექტორია სახელმწიფო სივრცეში?

1. რა არის ოპტიმალური კონტროლის პრობლემა?

1. როგორ არის ჩამოყალიბებული ოპტიმალური კრიტერიუმი?

1. რა არის დინამიური პროგრამირება?

1. ჩამოაყალიბეთ ბელმანის ოპტიმალური პრინციპი.

1. რა არის უმოკლესი გზის ძიებისას წინ და უკან სვლის ალგორითმების არსი?

დავალებების ვარიანტები მე-6 თავისთვის.

ქსელებისთვის თითოეულ ვარიანტში:

1) იპოვნეთ მაქსიმალური ნაკადი წყაროდან (1) ქსელის ბოლო კვანძამდე - ნიჟარამდე, იმ ვარაუდით, რომ თითოეული რკალის ფრჩხილებში მოცემული რიცხვებიდან ერთი (i, j) განსაზღვრავს რკალის სიმძლავრეს;

1) თუ ვივარაუდებთ, რომ რკალი (1)®(2), (1)®(3) და ა.შ. განსაზღვრავს ზოგიერთ სამუშაოს, რომელთა მინიმალური და მაქსიმალური ხანგრძლივობა მოცემულია შესაბამისი რკალების ქვეშ მითითებული რიცხვებით, იპოვეთ კრიტიკული გზა. საწყისი მოვლენიდან (1) ბოლომდე;

1) მოძებნეთ უმოკლესი გზა ქსელის საწყისი კვანძიდან ბოლო კვანძამდე. განვიხილოთ მანძილი i, j კვანძებს შორის, რომელიც მოცემულია ფრჩხილებში მოცემული რიცხვებიდან.

X 4

გაკვეთილზე განიხილება დინამიური პროგრამირების კონცეფცია და მისი გარეგნობის ისტორიული ასპექტი. განხილულია დინამიური პროგრამირების პრობლემები და მათი გადაწყვეტის რამდენიმე მაგალითი.

"დინამიური პროგრამირების" კონცეფცია პირველად გამოიყენა 1940-იან წლებში რიჩარდ ბელმანმა პრობლემის გადაჭრის პროცესის აღსაწერად, სადაც ერთ პრობლემაზე პასუხის მიღება შესაძლებელია მხოლოდ სხვა "წინასწარ" პრობლემის გადაჭრის შემდეგ.
ამრიგად, ამერიკელი მათემატიკოსი და მათემატიკისა და კომპიუტერული ტექნოლოგიების დარგის ერთ-ერთი წამყვანი ექსპერტი - რიჩარდ ერნსტ ბელმანი- გახდა დინამიური პროგრამირების მამა.

მოგვიანებით, კონცეფციის ფორმულირება დაიხვეწა და გაუმჯობესდა მის თანამედროვე ფორმამდე თავად ბელმანმა.

სიტყვა "პროგრამირება""დინამიური პროგრამირების" კონტექსტში, ფაქტობრივად, გულისხმობს პროგრამირების კლასიკურ გაგებას (პროგრამის ენაზე კოდის დაწერა) პრაქტიკულად არაფერი აქვს საერთო. სიტყვა "პროგრამირებას" იგივე მნიშვნელობა აქვს, რაც ფრაზაში "მათემატიკური პროგრამირება", რომელიც სინონიმია სიტყვა "ოპტიმიზაციასთან".

ამიტომაც პროგრამებიგამოყენებული იქნება, როგორც მოქმედებების ოპტიმალური თანმიმდევრობა პრობლემის გადაჭრის მოსაპოვებლად.

ზოგადად, დასაწყისისთვის, დინამიური პროგრამირების არაფორმალური განმარტებაშეიძლება ასე ჟღერდეს:

დინამიური პროგრამირებაეს არის ტექნიკა ან მეთოდი, რომელიც საშუალებას გაძლევთ გადაჭრას კომბინატორიკის, ოპტიმიზაციის და სხვა პრობლემების გარკვეული თვისება (ქვედავალებების თანაოპტიმალურობის თვისება).

ოპტიმიზაციის პრობლემებიროგორც წესი, დაკავშირებულია ამა თუ იმ ობიექტური ფუნქციის მაქსიმიზაციის ან მინიმიზაციის ამოცანასთან (მაგალითად, სისტემის არ დაშლის ალბათობის მაქსიმიზაცია, მოსალოდნელი მოგების მაქსიმიზაცია და ა.შ.).

კომბინატორიკის პრობლემები, როგორც წესი, უპასუხეთ კითხვას, რამდენი ობიექტია, რომელსაც აქვს გარკვეული თვისებები, ან რამდენი კომბინატორიული ობიექტია, რომელსაც აქვს თვისებები.

ანუ, DP არ წყვეტს ყველა პრობლემას, არამედ მხოლოდ ზოგიერთ, გარკვეულ კლასს ქვეამოცანას. მაგრამ ქვეამოცანის ეს კლასი გამოიყენება ცოდნის მრავალ სფეროში: პროგრამირება, მათემატიკა, ლინგვისტიკა, სტატისტიკა, თამაშების თეორია, ეკონომიკა, კომპიუტერული მეცნიერება და ა.შ.

დინამიური პროგრამირების გამოყენებით გადაჭრილი პრობლემები უნდა ჰქონდეს კოოპტიმალურობის თვისება, რომელიც შემდგომ გაკვეთილებზე იქნება განხილული.

ქვეპრობლემების ოპტიმალური თვისების არაფორმალური ახსნა შეიძლება აჩვენოს დიაგრამის გამოყენებით:
არის პრობლემა, რომლის მოგვარებაც გვინდა DP-ს გამოყენებით, ე.ი. იპოვნეთ რაიმე გეგმა მის გადასაჭრელად. ვთქვათ, ეს პრობლემა კომპლექსურია და მაშინვე ვერ მოვაგვარებთ. ვიღებთ პატარა ქვეპრობლემას და ჯერ ვხსნით (x1-ისთვის). შემდეგ ამ პატარა ამონახსნის გამოყენებით x1 და ამ ამოხსნის სტრუქტურის შეცვლის გარეშე ვხსნით შემდეგ პრობლემას x1 და x2. და ა.შ.

ბრინჯი. 1.1. ქვეპრობლემების ოპტიმალური თვისების არაფორმალური ახსნა

არაფორმალური განმარტება უფრო დეტალურად არის განხილული.

დინამიური პროგრამირების გამოყენებით მოგვარებული პრობლემების მაგალითები

პირველ რიგში, განიხილეთ ოპტიმიზაციის პრობლემები (დავალებები 1-5):

1. ოპტიმალური სიგრძის მარშრუტი

მაგალითი:არსებობს გარკვეული საგზაო რუკა, რომელიც წარმოდგენილია გრაფიკის სახით. ჩვენი მიზანი: წერტილიდან გასვლა ამიუთითოს ბ. ეს უნდა გაკეთდეს ისე, რომ მინიმუმამდე დაიყვანოს მანძილი ან დახარჯული საწვავი.

ობიექტური ფუნქციააქ არის მანძილი არომ ბ. იმათ. ჩვენი მიზანია მინიმუმამდე დავიყვანოთ მანძილი.

და რა არის შერჩევის ცვლადი? იმისათვის, რომ იპოვოთ უმოკლესი გზა, თქვენ უნდა მიიღოთ გადაწყვეტილებები ყოველ ჯერზე. იმათ. თითოეულ წერტილში ან თითოეულ გზაჯვარედინზე უნდა იქნას მიღებული გადაწყვეტილებები: სად გადაუხვიოთ ან პირდაპირ წავიდეთ.

მნიშვნელოვანია:ამ პრობლემისგან უკვე შეგიძლიათ იხილოთ დინამიური პროგრამირების გამოყენებით გადაჭრილი პრობლემების ზოგადი სტრუქტურა: თითოეულ პრობლემას აქვს ობიექტური ფუნქცია და არჩევანის ცვლადი.

2. მანქანის შეცვლა (დანახარჯების მინიმიზაცია)

მაგალითი:ყოველწლიურად ვიღებთ გადაწყვეტილებას, ვიტაროთ თუ არა ძველი მანქანა კიდევ ერთი წელი და გავწიოთ თუ არა ძველი მანქანის შენახვა-შენახვის ხარჯები, ან გავყიდოთ მანქანა და ვიყიდოთ ახალი (და გავითვალისწინოთ შეძენის ხარჯები).

ობიექტური ფუნქცია:ხარჯების მინიმიზაცია (ან ძველი მანქანის შენარჩუნების ან ახლის შეძენის ხარჯები).

შერჩევის ცვლადი:ყოველწლიურად მიიღეთ გადაწყვეტილება მანქანის გაყიდვის ან შენახვის შესახებ.

3. გაცვლის პორტფელი

მაგალითი:საფონდო ბირჟაზე თამაში, ნებისმიერი კომპანიის აქციების შეძენა


ობიექტური ფუნქცია:მაქსიმიზაცია საშუალოშემოსავალი, რადგან ბირჟაზე შემოსავალი მიიღება ალბათობით, ე.ი. ეს არის სტატისტიკური პროცესი, ალბათობითი.

შერჩევის ცვლადი:როგორი საინვესტიციო პორტფელი იქნება: რამდენი აქცია და რომელი კომპანია უნდა შევიძინოთ.

4. ოპტიმალური წარმოების გეგმის შედგენა (ლოგისტიკა)

მაგალითი:არის ფაბრიკა, რომელიც ავეჯს ამზადებს. ქარხანაში დასაქმებულია მუშების გარკვეული რაოდენობა, რომლებსაც შეუძლიათ გარკვეული რაოდენობის ავეჯის (სკამები, მაგიდები, კარადები და ა.შ.) დამზადება.


ობიექტური ფუნქცია: მოგების მაქსიმიზაცია.

შერჩევის ცვლადი:აირჩიე რამდენი სკამი ან მაგიდა უნდა გაკეთდეს იმისათვის, რომ საკმარისი შრომა გქონდეთ.

5. თამაშები (ალბათური ან არასავარაუდო)

მაგალითი:მონაწილეობა სხვადასხვა თამაშებში


ობიექტური ფუნქცია:გამარჯვების ალბათობის მაქსიმიზაცია ან საშუალო მოგების მაქსიმიზაცია და ა.შ.

შერჩევის ცვლადი აქ დამოკიდებულია კონკრეტულ თამაშზე.

ამოცანები 1 - 5 არის ოპტიმიზაციის ამოცანების მაგალითები.

კომბინატორიკა:

6. გრაფიკები და ხეები

მაგალითი:ამოცანაა გადაწყვიტოს რამდენი ხეა, რომელსაც აქვს ფოთლის გარკვეული რაოდენობა; ან რამდენი გრაფიკი არსებობს ამა თუ იმ ამოცანის ამოსახსნელად და ა.შ.

7. მონეტების გაცვლის პრობლემა ან ცვლის დაბრუნების გზების რაოდენობა

მაგალითი:არსებობს სხვადასხვა ნომინალის მონეტები, რა გზით შეგიძლიათ დააბრუნოთ ცვლილება.

ეს არის დინამიური პროგრამირების პრობლემების მოკლე აღწერა, რომელიც შემდგომში დეტალურად იქნება განხილული.

დინამიური პროგრამირების კონცეფცია

DP ქვეპრობლემების ოპტიმალურობის არაფორმალური ახსნა.

განვიხილოთ არაფორმალური DP იდეა.

მაშ ასე, ავიღოთ ავეჯის მწარმოებელი ქარხნის მაგალითი.

ამისთვის მოგების მაქსიმიზაციის მიზნის მისაღწევად, აუცილებელია მრავალი ქვეამოცანის გადაჭრა:

• რამდენი სკამი უნდა დამზადდეს - ცვლადი X1,
• რამდენი ცხრილი უნდა შეიქმნას - ცვლადი X2,
• რამდენი თანამშრომელი დაიქირაოს - ცვლადი X3,
• ... Xn.

ქვეპრობლემების დიდი რაოდენობით, ძნელია იმის გაგება, თუ როგორ უნდა მოგვარდეს ასეთი პრობლემა. როგორც წესი, ერთი პატარა პრობლემის გადაჭრა უფრო ადვილია, ვიდრე დიდი პრობლემის გადაჭრაშედგება პატარებისგან.

აქედან გამომდინარე, DP გთავაზობთ შემდეგს:

• ვიღებთ ერთ ქვეამოცანას X1 ცვლადით და ახლა ვივიწყებთ დარჩენილ ქვეამოცნებებს.

მაგალითად, ქარხანა აწარმოებს მხოლოდ სკამებს. დირექტორს აქვს ამოცანა სკამების გაყიდვიდან მაქსიმალური მოგების მიღება.

• მას შემდეგ რაც ვიპოვით ოპტიმალურ ამოხსნას პირველი ქვეამოცანისთვის, ვიღებთ ქვეამოცანას ორი ცვლადის X1 და X2 და ვხსნით მას. პირველი ქვეამოცანის უკვე ნაპოვნი ამოხსნის გამოყენებით.
• ჩვენ ვიღებთ გამოსავალს უფრო დიდი ქვეამოცნებისთვის, სადაც ჩნდება ცვლადები X1 და X2. შემდეგ მიღებული ამოხსნის გამოყენებით ვიღებთ X1, X2 და X3 ქვედავალებებს.
• და ასე ვაგრძელებთ მანამ, სანამ არ მივიღებთ გადაწყვეტას მთელი ზოგადი პრობლემისთვის.

DP-ის ოფიციალური იდეა

ხშირად, პრობლემის დასმისას, ერთი შეხედვით ოპტიმალური გადაწყვეტაა ვცდილობთ ყველა შესაძლო ვარიანტს. თუმცა, ასეთი ვარიანტების ძალიან დიდი რაოდენობის და, შედეგად, კომპიუტერის მეხსიერების გადატვირთვის გამო, ეს მეთოდი ყოველთვის არ არის მისაღები.

გარდა ამისა, შეიძლება წარმოიშვას შემდეგი კითხვა: იმისათვის, რომ ვიპოვოთ, მაგალითად, მინიმალური ან მაქსიმალური, რატომ არ ვპოულობთ წარმოებულს? თუ არ გამოვიყენოთ La Grange კომპლექტები, ან მათემატიკური ანალიზის სხვა მეთოდები? რატომ გჭირდებათ DP, თუ სახსრების დიდი არსენალი გაქვთ?

საქმე იმაშია რომ:

დინამიური პროგრამირება ეფუძნება მოცემული პრობლემის გადაჭრის იდეას მისი ცალკეულ ნაწილებად დაყოფით (ქვედავალებები, ეტაპები), ამ ქვეამოცნების გადაჭრა და შემდეგ ამ გადაწყვეტილებების გაერთიანება ერთ საერთო გადაწყვეტაში. ხშირად ქვეამოცანების უმეტესობა ზუსტად იგივეა.

მნიშვნელოვანია, რომ უფრო რთული ამოცანის ამოხსნისას, ისევ არ გადავჭრათ მცირე ქვეპრობლემა, არამედ გამოვიყენოთ ამ ქვეპრობლემის უკვე ამოხსნილი პასუხი.
გრაფიკზე შეიძლება ასე გამოიყურებოდეს:

მნიშვნელოვანია:ამ მიზეზით, დავალების დაყოფა ქვეამოცნებებად და ამ ქვეპრობლემების გადაჭრა მხოლოდ ერთხელ (!), რითაც მცირდება საერთო გამოთვლების რაოდენობა - უფრო ოპტიმალური მეთოდი, რომელიც თანდაყოლილია დინამიურ პროგრამირებაში

როდესაც პრობლემას ვაგვარებთ წარმოებულებით, La Grange სიმრავლეებით და ა.შ., ჩვენ ვმუშაობთ უწყვეტი ფუნქციებით. DP პრობლემების გადაჭრისას ჩვენ ვიმუშავებთ ძირითადად დისკრეტულ ფუნქციებთან, ამიტომ უადგილოა აქ საუბარი უწყვეტი ფუნქციების გამოყენებაზე.
ამ მიზეზით, ბევრ პრობლემაში, მაგრამ არა ყველა, მათემატიკური ანალიზის გამოყენება მიუღებელი იქნება.

პრობლემების გადაჭრის მარტივი მაგალითი DP-ს გამოყენებით

განვიხილოთ პრობლემის გადაჭრის ვარიანტი დინამიური პროგრამირების გამოყენებით.

მაგალითი:აუცილებელია n რიცხვის ჯამის გამოთვლა: 1 + 2 + 3 + ... + n

რა არის ამ პრობლემის სავარაუდო „სირთულე“: თქვენ უნდა აიღოთ რიცხვების დიდი რაოდენობა ერთდროულად და მიიღოთ პასუხი.

შევეცადოთ გამოვიყენოთ DP იდეები პრობლემაზე და მოვაგვაროთ იგი მარტივ ქვეამოცნებებად დაყოფით.
(DP-ში ყოველთვის საჭიროა პირველად განისაზღვროს საწყისი პირობები ან მდგომარეობა)

• დავიწყოთ პირველი ელემენტის ჯამით, ე.ი. უბრალოდ მიიღეთ პირველი ელემენტი:
  F(1) = 1
• ახლა, პირველი ელემენტის გამოსავლის გამოყენებით, ჩვენ ვხსნით
  F(2) = F(1) + 2 = 1 + 2 = 3, ე.ი. თქვენ უნდა აიღოთ პირველი ელემენტის ჯამი და დაამატოთ მას მეორე ელემენტი
• F(3) = F(2) + 3 = 6
• ჩვენ ვაგრძელებთ ანალოგიით და ვიღებთ ობიექტურ ფუნქციას:
  F(n) = F(n-1) + An

მაშ, რა გავაკეთეთ: განვსაზღვრეთ თანმიმდევრობა და განვსაზღვრეთ ქვეამოცანები, შემდეგ მოვაგვარეთ თითოეული მათგანი წინა ამოხსნის საფუძველზე.

მარტივი მაგალითი, სადაც DP ჯერ კიდევ გაუმართლებლად გამოიყენება (ხელოვნურად), ასახავს DP იდეების პრინციპს.

მოდით შევხედოთ სხვა მაგალითს.

მაგალითი:არის n საფეხურიანი კიბე, რომლის წინ არის ადამიანი, რომელიც უკან დგას 1 საფეხურს შეუძლია ასვლა შემდეგ საფეხურზე ან გადახტომა ერთ საფეხურზე. კითხვა: რამდენი გზით შეუძლია მას ბოლო საფეხურამდე მისვლა?

გამოსავალი:

მოდით განვიხილოთ უმარტივესი ვარიანტები (ქვედავალებები):

მოდით შევხედოთ i ნაბიჯების მაგალითს

როგორ მივიდეთ I საფეხურზე:

1. i-1 საფეხურიდან და ჩვენ შეგვიძლია მივიდეთ i-1 საფეხურზე i-1 გზებით
2. i-2 საფეხურიდან და ჩვენ შეგვიძლია მივსულიყავით i-2 საფეხურზე i-2 გზებით

მაგალითად, როგორ მივიდეთ მე-4 ნაბიჯი:

რომ., გზების საერთო რაოდენობამიდი I საფეხურზე:
f(a i) = f(a i-1) + f(a i-2)

მოდით განვსაზღვროთ საწყისი მნიშვნელობები, საიდანაც უნდა დაიწყოს პრობლემის გადაჭრა.
თუ დაიწყებთ 1-ით, მაშინ ფორმულა შეესაბამება ფიბონაჩის რიცხვების მიმდევრობის პოვნას.

ჩვენ ვხედავთ, რომ პრობლემა არსებითად კომბინატორულია (ანუ რამის გაკეთების გზების რაოდენობა) შემცირდა გარკვეული განმეორებადი თანმიმდევრობის გამოთვლაზე.

ამოცანა 1:განახორციელეთ მაგალითი პირველი ათი ნაბიჯისთვის (არსებითად ფიბონაჩის სერიის პირველი 10 რიცხვი), რეკურსიის გამოყენებით.

შეავსეთ კოდი:

1 2 3 4 5 6 7 8 9 10 11 12 13

var c: მთელი რიცხვი;

პროცედურა getKolSposob(i, n: მთელი რიცხვი);

წერის დაწყება (i+ n, "");
inc(c);

თუ ... მაშინ getKolSposob(...,...) დასასრული;

1. დასაწყისი c: = 1 ;

getKolSposob(0, 1);

დასასრული.
var c: მთელი რიცხვი;

განვიხილოთ პროცედურა getKolSposob(i,n: მთელი რიცხვი);.
დაე, გადაწყვეტილების მიღების მრავალსაფეხურიანი პროცესი დაიყოს ნნაბიჯები. ე 0-ით აღვნიშნოთ სისტემის საწყისი მდგომარეობა, ε 1, ε 2, … ε ნ- სისტემის მდგომარეობა პირველი, მეორე, ნ- ნაბიჯი. ზოგადად, სახელმწიფო ε კ– ვექტორი (ე კ 1, …, ე კ ს).
მენეჯმენტიმრავალსაფეხურიან პროცესში, გადაწყვეტილებების ერთობლიობა (საკონტროლო ცვლადები) ეწოდება u k = (u k 1 , ..., u k r) ყოველ ნაბიჯზე გადადგმული კდა სისტემის გადატანა სახელმწიფოდან ε კ-1 = (ე კ- 1 1 , …, ე კ -1 ს) ე კ = (ε კ 1, …, ე კ ს).
ეკონომიკურ პროცესებში მენეჯმენტი შედგება სახსრების განაწილებისა და გადანაწილებისგან თითოეულ ეტაპზე. მაგალითად, ნებისმიერი საწარმოს მიერ პროდუქციის წარმოება არის კონტროლირებადი პროცესი, ვინაიდან იგი განისაზღვრება აღჭურვილობის შემადგენლობის ცვლილებებით, ნედლეულის მიწოდების მოცულობით, დაფინანსების ოდენობით და ა.შ. დასაწყისში მიღებული გადაწყვეტილებების ნაკრები. წლის დაგეგმვის პერიოდი, საწარმოს ნედლეულით უზრუნველყოფა, ტექნიკის გამოცვლა და დაფინანსების ოდენობა და ა.შ. როგორც ჩანს, გამომავალი მაქსიმალური მოცულობის მისაღებად, უმარტივესი გზაა მაქსიმალური შესაძლო თანხების ინვესტირება და აღჭურვილობის სრული სიმძლავრით გამოყენება. მაგრამ ეს გამოიწვევს აღჭურვილობის სწრაფ ცვეთას და, შედეგად, წარმოების გამომუშავების შემცირებას. ამიტომ, პროდუქტის გამოშვება უნდა დაიგეგმოს ისე, რომ თავიდან იქნას აცილებული არასასურველი შედეგები. აუცილებელია ზომების მიღება იმის უზრუნველსაყოფად, რომ აღჭურვილობის შევსება ხდება მისი ამოწურვისას, ანუ გარკვეული პერიოდის განმავლობაში. ეს უკანასკნელი, მიუხედავად იმისა, რომ იწვევს გამოშვების საწყისი მოცულობის შემცირებას, იძლევა სამომავლოდ წარმოების გაფართოების შესაძლებლობას. ამრიგად, წარმოების ეკონომიკური პროცესი შეიძლება ჩაითვალოს რამდენიმე ეტაპისგან (საფეხურისგან), რომელთაგან თითოეული გავლენას ახდენს მის განვითარებაზე.
კონტროლირებადი პროცესის ეტაპის (საფეხურის) დასაწყისად ითვლება გადაწყვეტილების მიღების მომენტი (კაპიტალური ინვესტიციის ოდენობაზე, გარკვეული ტიპის აღჭურვილობის გამოცვლაზე და ა.შ.). ეტაპი ჩვეულებრივ გაგებულია, როგორც საქმიანი წელი.
როგორც წესი, ყოველ ნაბიჯზე კონტროლი u kმოქმედებს გარკვეული შეზღუდვები. კონტროლი, რომელიც აკმაყოფილებს ამ შეზღუდვებს, ეწოდება მისაღები.
ვივარაუდოთ, რომ შესრულების მაჩვენებელი კპროცესის მე-4 საფეხური დამოკიდებულია ამ ეტაპზე საწყის მდგომარეობაზე კ-1 და ამ ეტაპზე კონტროლიდან u k, ჩვენ ვიღებთ მთელი მრავალსაფეხურიანი პროცესის ობიექტურ ფუნქციას სახით:
.

ახლა ჩამოვაყალიბოთ დინამიური პროგრამირების პრობლემა: „დაადგინეთ დასაშვები კონტროლის ნაკრები ( u 1 , …, u n), სისტემის გადატანა საწყისი მდგომარეობიდან ε 0 საბოლოო მდგომარეობაში ε ნდა ეფექტურობის ინდიკატორის მაქსიმიზაცია ან მინიმიზაცია ფ».
კონტროლი, რომელიც აღწევს ფუნქციის მაქსიმუმს (მინიმუმს). ფდაურეკა ოპტიმალური კონტროლი u * = (u 1* ,…, u n *).
თუ საკონტროლო ცვლადები u kაიღეთ დისკრეტული მნიშვნელობები, შემდეგ გამოიძახება DP მოდელი დისკრეტული. თუ ცვლადები u kმუდმივად იცვლება, მაშინ DP მოდელი ეწოდება უწყვეტი.
დამოკიდებულია მდგომარეობის პარამეტრების რაოდენობაზე სდა საკონტროლო ცვლადების რაოდენობა რგანასხვავებენ ერთგანზომილებიანიდა მრავალგანზომილებიანი DP ამოცანები.
დავალების ნაბიჯების რაოდენობა შეიძლება იყოს საბოლოოან გაუთავებელი.

დინამიური პროგრამირების გამოყენებითი პრობლემები

1. ობიექტების მშენებლობის დაგეგმვის პრობლემა.