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

საკითხავია, როგორ უნდა გადანაწილდეს K სახსრები საწარმოებს შორის ისე, რომ მთლიანობაში მათ მაქსიმალური შემოსავალი გამოიმუშაონ?

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

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

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

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

და პირობითი ოპტიმალური მოგება

S-ის მნიშვნელობების მთელი დიაპაზონის გათვალისწინებით (მათი საკმაოდ მჭიდროდ განვსაზღვრავთ), ჩვენ ვიცით S-ის თითოეული მნიშვნელობისთვის. ბოლო ნაბიჯი ოპტიმიზებულია.

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

და თქვენ უნდა იპოვოთ ის, სადაც ეს მოგება იქნება მაქსიმალური:

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

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

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

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

მას შემდეგ რაც ამ თანხებს პირველ საწარმოში ჩავდებთ, დაგვრჩება. S-ის ამ მნიშვნელობის რეკომენდაციის „კითხვისას“ მეორე საწარმოს გამოვყოფთ სახსრების ოპტიმალურ რაოდენობას: და ასე ბოლომდე.

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

ცხრილი 13.1

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

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

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

ცხრილი 13.2

თითოეული წყვილის პირველი სვეტი იძლევა პირობითი ოპტიმალური კონტროლის მნიშვნელობას, მეორე - პირობით ოპტიმალურ მომატებას. ცხრილი ივსება მარცხნიდან მარჯვნივ, ზემოდან ქვემოდან. გადაწყვეტილება მეხუთე – ბოლო – საფეხურზე იძულებულია: ყველა თანხა გამოიყოფა; ყველა სხვა ეტაპზე, გამოსავალი უნდა იყოს ოპტიმიზირებული. მე-5, მე-4, მე-3, მე-2 და 1 საფეხურების თანმიმდევრული ოპტიმიზაციის შედეგად მივიღებთ ყველა რეკომენდაციის სრულ ჩამონათვალს ოპტიმალური კონტროლისთვის და უპირობო ოპტიმალური მომატების W მთელი ოპერაციისთვის - ამ შემთხვევაში ის უდრის 5.6-ს. . 13.2 ცხრილის ბოლო ორ სვეტში ივსება მხოლოდ ერთი სტრიქონი, ვინაიდან ჩვენ ზუსტად ვიცით სისტემის მდგომარეობა პირველი ნაბიჯის დაწყებამდე: . ოპტიმალური კონტროლი ყველა საფეხურზე ხაზგასმულია ჩარჩოთი. ამრიგად, მივიღეთ საბოლოო დასკვნა: პირველ საწარმოს ათიდან ორი ერთეული უნდა მივცეთ, მეორეს ხუთი ერთეული, მესამეს ორი, მეოთხეს არცერთი და მეხუთეს ერთი ერთეული. ამ განაწილებით შემოსავალი იქნება მაქსიმალური და 5,6-ის ტოლი.

გაკვეთილის გეგმა

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

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

გაკვეთილის მიზნები

დინამიური პროგრამირების პრობლემების გადაჭრის უნარ-ჩვევების გამომუშავება.

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

მოსწავლეებში დისციპლინისა და მონდომების დანერგვა.

საგაკვეთილო აღჭურვილობალექციის შენიშვნები, V.P. Agaltsov "მათემატიკური მეთოდები პროგრამირებაში".

გაკვეთილის პროგრესი:

ორგანიზაციული წერტილი:

დაუსწრებელთა შემოწმება, ჟურნალის შევსება.

საცნობარო ცოდნის განახლება: პასუხები უსაფრთხოების კითხვებზე

რა ამოცანებს ეწოდება მრავალსაფეხურიანი?

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

რა არის ოპტიმალური კონტროლი u*?

რა არის ალგორითმი ორი წრის თანმიმდევრული მიახლოების მეთოდისთვის?

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

ახალი მასალის სწავლა:

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

• ყველაზე გრძელი საერთო ქვემიმდევრობის პრობლემა: ორი მიმდევრობის გათვალისწინებით, თქვენ უნდა იპოვოთ ყველაზე გრძელი საერთო ქვემიმდევრობა.

• ყველაზე გრძელი მზარდი ქვემიმდევრობის პოვნის პრობლემა: მიმდევრობის გათვალისწინებით, თქვენ უნდა იპოვოთ ყველაზე გრძელი მზარდი ქვემიმდევრობა.

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

• ფიბონაჩის რიცხვების გამოთვლის პრობლემა

• მატრიცის გამრავლების რიგის პრობლემა: მოცემული მატრიცები, ..., საჭიროა მათი გამრავლებისთვის სკალარული ოპერაციების რაოდენობის მინიმიზაცია.

• ტრაექტორიის შერჩევის პრობლემა

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

• შრომის უტილიზაციის პრობლემა

• ინვენტარის მართვის პრობლემა

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

• ფლოიდ-ვარშალის ალგორითმი: იპოვნეთ უმოკლესი მანძილი შეწონილი მიმართული გრაფიკის ყველა წვეროს შორის.

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

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

მაგალითი: რესურსების ოპტიმალური განაწილება

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

u

მოგება განხორციელებიდან

f4(u)

f3(u)

f2(u)

f1(u)

55

39

120

115

10 0

120

135

134

14 0

145

158

147

გამოსავალი:

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

ეტაპი 1.

ჩვენ ვანაწილებთ კაპიტალს ოთხ პროექტს შორის და ვიანგარიშებთ მიღებულ მოგებას ლ (მე ), მე = 8,16,24,32,40.

1 ნაბიჯი: თანხები ჩადებულია მეოთხე პროექტში.

L(8)= 55

L(16)=58

L(24)=90

L(32)=100

L(40)=140

ნაბიჯი 2: სახსრები ჩადებულია მეოთხე და მესამე პროექტებში.

u

მოგება განხორციელებიდან

1 ნაბიჯი

f3(u)

55

39

10 0

120

14 0

145

ნაბიჯი 3: სახსრები იდება მეოთხე, მესამე (ნაბიჯი 2) და მეორე პროექტებში.

u

მოგება განხორციელებიდან

ნაბიჯი 2

f 2(u)

94

108

120

135

135

175

158

175

134

214

147

ეტაპი 2:

მეოთხე საფეხურზე ვირჩევთ მიღებული მოგების მნიშვნელობების მაქსიმუმს L (40) = 214.

და საპირისპირო თანმიმდევრობით დავბრუნდებით ცხრილიდან ცხრილამდე (4 ნაბიჯიდან 1-მდე) ვირჩევთ შემოსავლის ისეთ მნიშვნელობებს, რომლებზეც მიიღება მნიშვნელობა 214.

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

1 პროექტი - 0 მილიონი რუბლი.

2 პროექტი - 24 მილიონი რუბლი.

მესამე პროექტი - 8 მილიონი რუბლი.

4 პროექტი - 8 მილიონი რუბლი.

ახალი მასალის კონსოლიდაცია:

5. გაკვეთილის შეჯამება: დასკვნები, შეფასებები, საშინაო დავალება:

(2) პუნქტი 5.1

Ср12: თეორიული მასალის შინაარსის ფორმირება და ათვისება

მასწავლებლის ხელმოწერა

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

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

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

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

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

მიღებულ ნოტაციაში ბელმანის ოპტიმალური პრინციპი შეიძლება ჩაიწეროს მათემატიკური ფორმით შემდეგნაირად

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

DP მეთოდის გამოთვლითი პროცედურა იყოფა ორ ეტაპად: პირობითი და უპირობო ოპტიმიზაცია.

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

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

3.1. რესურსების ოპტიმალური განაწილების პრობლემა

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

დავალება უნდა ჩაითვალოს მრავალსაფეხურიან.

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

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

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

უპირობო ოპტიმიზაციის ეტაპზე განისაზღვრება საწარმოებს შორის რესურსების განაწილების ოპტიმალური გეგმა.

მაგალითი 3.1.

პროდუქციის წარმოების მოცულობის გასაზრდელად, რომლებზეც დიდი მოთხოვნაა, თანხები 50 მილიონი რუბლის ოდენობით გამოიყო საწარმოო ასოციაციის ოთხ საწარმოს. თითოეული საწარმო შეიძლება გამოიყოს: 0, 10, 20, 30, 40 ან 50 მილიონი რუბლი. ამავდროულად, ყოველწლიურად იზრდება პროდუქციის წარმოება თითოეული საწარმოს მიერ
ინვესტიციის მიხედვით ცნობილია და ნაჩვენებია ცხრილში. 3.1.

ცხრილი 3.1

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

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

1. ძირითადი ცნებები

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

1.2. ოპტიმალური პრინციპი. ბელმანის განტოლება

2. რესურსების ოპტიმალური განაწილება

2.1 პრობლემის განცხადება

2.2 რესურსების განაწილების ორგანზომილებიანი მოდელი

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

2.4 რესურსების ოპტიმალური განაწილების პრობლემების შემდგომი ეფექტების გათვალისწინება

დასკვნა

გამოყენებული წყაროების სია

დანართი 1. პროგრამული ჩამონათვალი მოცემული პარამეტრებით რესურსების ოპტიმალური განაწილების პრობლემის გადასაჭრელად. პროგრამის შედეგები

შესავალი

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

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

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

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

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

1. ძირითადი ცნებები

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

მოდით მივცეთ დინამიური პროგრამირების მოდელის ზოგადი აღწერა.

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

საბოლოო მდგომარეობამდე. დავუშვათ, რომ სისტემის მართვის პროცესი შეიძლება დაიყოს ნნაბიჯები. მოდით , ,…, იყოს სისტემის მდგომარეობები პირველი, მეორე,..., ნ- ნაბიჯი. ეს სქემატურად არის ნაჩვენები ნახ. 1.

სურათი 1

სახელმწიფო

სისტემების შემდეგ ქთნაბიჯი ( კ = 1,2 …,ნ) ხასიათდება პარამეტრებით, ,…, რომლებიც ე.წ ფაზის კოორდინატები.მდგომარეობა შეიძლება წარმოდგენილი იყოს წერტილით s-განზომილებიან სივრცეში ე.წ ფაზის სივრცე.სისტემის თანმიმდევრული ტრანსფორმაცია (ეტაპობრივად) მიიღწევა გარკვეული აქტივობების დახმარებით, ,…, რომელიც წარმოადგენს სისტემის მართვას. სად არის კონტროლი კ-ე ნაბიჯი, სისტემის გადატანა მდგომარეობიდან სახელმწიფოში (ნახ. 1). მენეჯმენტი ჩართულია კმე-4 ნაბიჯი არის გარკვეული საკონტროლო ცვლადების მნიშვნელობების შერჩევა.

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

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

ტოლობები (1.1) ეწოდება მდგომარეობების განტოლებები.ფუნქციები

ჩვენ ვვარაუდობთ, რომ მოცემულია.

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

და არჩეული კონტროლიდან უ : . (1.2)

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

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

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

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

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

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

ნაბიჯ-ნაბიჯ ოპტიმიზაციის პრობლემა შეიძლება ჩამოყალიბდეს შემდეგნაირად: განსაზღვრეთ შესაძლებელი კონტროლის ნაკრები

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

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

გამოქვეყნებულია http://www.allbest.ru/

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

სამი A, B და C საწარმოს საწარმოო სიმძლავრის გასაფართოებლად გამოიყოფა დამატებითი ელექტროენერგიის ერთეულის გარკვეული რაოდენობა x 0 = 8 ერთეულის ოდენობით. ელექტროენერგიის გამოშვება შესაძლებელია 1, 2, 3, 4, 5, 6, 7 და 8 ერთეულის სახით. მე-ე საწარმოს განვითარებაში x i ერთეული ელექტროენერგიის ინვესტიციით, შეგიძლიათ მიიღოთ შემოსავალი საწარმოში i ერთეულებიდან. არსებობს სხვადასხვა ვარიანტი x i (k) დამატებითი ელექტროენერგიის გამოყოფისთვის. შემოსავალი მოაქვთ i (k), k=1,n. საწარმოების განვითარების შესაძლო ვარიანტები მოცემულია ცხრილში 1. ყველა საწარმოს მთლიანი შემოსავალი მაქსიმალური უნდა იყოს, ანუ y=? y i (k)>მაქს

მაგიდა 1. საწარმოს განვითარების ვარიანტები

ვარიანტი k	საწარმო ა	საწარმო ბ	საწარმო გ

მათემატიკური დადგმა ამოცანები:

y=? ზე მე (ლ)> მაქს

?X მე (k)?x 0

გამოსავალი:

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

g C (S 2) = max k f c , x C (k)?S 2, k=1,2,3,4

მაგიდა 2. პირობითად ოპტიმალური გადაწყვეტილებები (ნაბიჯი 3)

სახელმწიფო		კონტროლი

სახსრების ინვესტირების ოთხი შესაძლებლობა არსებობს - ოთხი ნაბიჯის კონტროლი x C (1) = 0 ერთეული, x C (2) = 1 ერთეული, x C (3) = 2 ერთეული, x C (4) = 3 ერთეული. და S 2 სისტემის ცხრა თეორიულად შესაძლო მდგომარეობა, რომელიც წინ უძღვის C საწარმოსათვის სახსრების გამოყოფას - ინვესტიციების მოცულობები, რომლებიც არ არის განაწილებული მე-3 ეტაპზე: 0,1,2,3,4,5,6,7,8.

დავუშვათ, რომ სისტემა იყო S 2 =2 მდგომარეობაში, მაშინ, საფეხურის კონტროლისთვის x C (2) = 1, C (2) შემოსავალი იქნება 3 ერთეულის. (ცხრილი 3) და საფეხურის კონტროლი x C (3) = 2 იქნება ოპტიმალური ამ მდგომარეობისთვის, რაც იძლევა პირობით მაქსიმალურ მომატებას g c (S 2) = 5. თუ სისტემა იყო S 2 =3 მდგომარეობაში, მაშინ დასაშვებია ყველა საფეხურის კონტროლი: x C (1) = 0 ერთეული, x C (2) = 1 ერთეული, x C (3) = 2 ერთეული, x C (4) = 3 ერთეული და ოპტიმალური კონტროლი იქნება x C (4) = 3, რაც უზრუნველყოფს პირობით მაქსიმალურ მომატებას g c (S 2) = 6.

ცხრილი 3 პროგრამირების დინამიური ინვესტიციების განაწილება

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

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

g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4

ამრიგად, მდგომარეობისთვის S 1 =3 საფეხურის კონტროლით x A (2) = 1 ვიღებთ:

g A (S 1) = max k f A +g c ]

Max k 4+g c =4+5=9, სადაც ვხვდებით ცხრილი 1-დან და g c ცხრილიდან 3. ყველა მდგომარეობა ივსება ანალოგიურად.

მაგიდა 4. პირობითად ოპტიმალური გადაწყვეტილებები (ნაბიჯი 2)

სახელმწიფო	f A +g გ	კონტროლი

აქ წარმოიქმნება სიტუაციები, რომლებშიც ოპტიმალური გადაწყვეტა არ იქნება ერთადერთი. ამრიგად, S 1 = 3, საფეხურის კონტროლი x A (2) = 1 და x A (3) = 2 იქნება პირობითად ოპტიმალური, რაც იგივეს იძლევა. მომატება g A (S 1)=9

მაგიდა 5. უპირობოდ ოპტიმალური გადაწყვეტილებები (ნაბიჯი 1)

პირველ ეტაპზე (ცხრილი 5) - ინვესტიციების განაწილება B საწარმოსთვის - არსებობს სისტემის მხოლოდ ერთი წინა მდგომარეობა, რომელიც შეესაბამება საწყის მდგომარეობას S 0 =8. უპირობოდ ოპტიმალური მომატება განისაზღვრება გამონათქვამით:

y * = g B (S 0) = max k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5

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

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

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

ნახაზი 1. საწარმოებს შორის ინვესტიციების ოპტიმალური განაწილების სქემა

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

გამოქვეყნებულია Allbest.ru-ზე

...

მსგავსი დოკუმენტები

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

კურსის სამუშაო, დამატებულია 25/04/2015


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

კურსის სამუშაო, დამატებულია 12/30/2010


დინამიური პროგრამირების მეთოდი და მისი ძირითადი ეტაპები. აღჭურვილობის შეცვლის ოპტიმალური სტრატეგია. საწარმოების მშენებლობისა და ექსპლუატაციის ხარჯების მინიმიზაცია. რესურსების ოპტიმალური განაწილება შპს STROYKROVLYA-ში და ინვესტიციები PKT Khimvolokno-ში.

კურსის სამუშაო, დამატებულია 01/08/2015


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

ნაშრომი, დამატებულია 08/07/2013


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

კურსის სამუშაო, დამატებულია 01/14/2011


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

ტესტი, დამატებულია 10/15/2010


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

კურსის სამუშაო, დამატებულია 16/12/2013


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

პრეზენტაცია, დამატებულია 12/02/2014


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

ნაშრომი, დამატებულია 02/11/2017


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