ჩამოტვირთვები 

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

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

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

საწარმოთა რაოდენობა 2 3 4 5 6 7 8 9 10
მწკრივების რაოდენობა (ეფექტური ბუდეების ვარიანტების რაოდენობა) 2 3 4 5 6 7 8 9 10

მაგალითი No1. განსაზღვრეთ სამი საწარმოს წარმოების გაფართოების ოპტიმალური გეგმა, თუ მათი წლიური მოგება ცნობილია ინვესტიციების არარსებობის შემთხვევაში და 1, 2, 3 ან 4 მილიონის ინვესტიციით.

f1f2f3x i
40 30 35 0
90 110 95 1
395 385 270 2
440 470 630 3
620 740 700 4

ეტაპი I. პირობითი ოპტიმიზაცია.
1 ნაბიჯი. k = 3.

e 2u 3e 3 = e 2 - u 3f 3 (u 3)F* 3 (e 3)u 3 (e 3)
1 0 1 35
1 0 95 95 1
2 0 2 35
1 1 95
2 0 270 270 2
3 0 3 35
1 2 95
2 1 270
3 0 630 630 3
4 0 4 35
1 3 95
2 2 270
3 1 630
4 0 700 700 4

მე-2 ნაბიჯი. k = 2.

e 1u 2e 2 = e 1 - u 2f 2 (u 2)F* 2 (e 1)F 1 (u 2,e 1)F* 2 (e 2)u 2 (e 2)
1 0 1 30 95 125 125 0
1 0 110 0 110
2 0 2 30 270 300
1 1 110 95 205
2 0 385 0 385 385 2
3 0 3 30 630 660 660 0
1 2 110 270 380
2 1 385 95 480
3 0 470 0 470
4 0 4 30 700 730
1 3 110 630 740 740 1
2 2 385 270 655
3 1 470 95 565
4 0 740 0 740

მე-3 ნაბიჯი. k = 1.

e 0u 1e 1 = e 0 - u 1f 1 (u 1)F* 1 (e 0)F 0 (u 1,e 0)F* 1 (e 1)u 1 (e 1)
1 0 1 40 125 165 165 0
1 0 90 0 90
2 0 2 40 385 425 425 0
1 1 90 125 215
2 0 395 0 395
3 0 3 40 660 700 700 0
1 2 90 385 475
2 1 395 125 520
3 0 440 0 440
4 0 4 40 740 780 780 0
1 3 90 660 750
2 2 395 385 780
3 1 440 125 565
4 0 620 0 620

შენიშვნა: სვეტები 1 (ინვესტირებული სახსრები), 2 (პროექტი) და 3 (ფონდის ნაშთი) იგივეა სამივე ცხრილისთვის, ამიტომ ისინი შეიძლება იყოს საერთო. მე-4 სვეტი ივსება შემოსავლის ფუნქციების საწყისი მონაცემების საფუძველზე, მე-5 სვეტის მნიშვნელობები აღებულია წინა ცხრილის მე-7 სვეტიდან, მე-6 სვეტი ივსება მე-4 და მე-5 სვეტების მნიშვნელობების ჯამით. (მე-3 ნაბიჯის ცხრილში არ არის მე-5 და მე-6 სვეტები).
მე-7 სვეტი იწერს წინა სვეტის მაქსიმალურ მნიშვნელობას ფიქსირებული საწყისი მდგომარეობისთვის, ხოლო მე-8 სვეტში ჩაიწერება კონტროლი მე-2 სვეტიდან, რომელიც აღწევს მაქსიმუმ 7-ს.
II ეტაპი. უპირობო ოპტიმიზაცია.
მე-3 ნაბიჯის ცხრილიდან გვაქვს F* 1 (e 0 = 4 მილიონი რუბლი) = 780 ათასი რუბლი, ანუ მაქსიმალური მოგება ინვესტიციიდან e 0 = 4 მილიონი რუბლი. უდრის 780 ათას რუბლს.
იმავე ცხრილიდან ვხვდებით, რომ პირველ საწარმოს უნდა გამოეყოთ u* 1 (e 0 = 4 მილიონი რუბლი) = 0 მილიონი რუბლი.
ამ შემთხვევაში, სახსრების ბალანსი იქნება: e 1 = e 0 - u 1, e 1 = 4 - 0 = 4 მილიონი რუბლი.
მე-2 ნაბიჯის ცხრილიდან გვაქვს F* 2 (e 1 = 4 მილიონი რუბლი) = 740 ათასი რუბლი, ე.ი. მაქსიმალური მოგება e 1 = 4 მილიონი რუბლი. უდრის 740 ათას რუბლს.
იმავე ცხრილიდან ვხვდებით, რომ მეორე საწარმოს უნდა გამოეყოთ u* 2 (e 1 = 4 მილიონი რუბლი) = 1 მილიონი რუბლი.
ამ შემთხვევაში, სახსრების ბალანსი იქნება: e 2 = e 1 - u 2, e 2 = 4 - 1 = 3 მილიონი რუბლი.
ბოლო საწარმო იღებს 3 მილიონ რუბლს. ასე რომ, ინვესტიცია 4 მილიონი რუბლი. უნდა გადანაწილდეს შემდეგნაირად: პირველ საწარმოს არ უნდა გამოეყოს არაფერი, მეორე საწარმოს უნდა გამოყოს 1 მილიონი რუბლი, მესამე საწარმოს გამოყოს 3 მილიონი რუბლი, რაც უზრუნველყოფს მაქსიმალურ მოგებას 780 ათასი რუბლი.

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

ლაბორატორიული სამუშაო

კომპიუტერული მეცნიერება, კიბერნეტიკა და პროგრამირება

X სახსრები გამოყოფილია, რომელ კომპანიას მოაქვს მოგება წლის ბოლოს. ფუნქციები მოცემულია ცხრილში: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 დაადგინეთ რა თანხა სჭირდება თითოეულ საწარმოს გამოყოფას რომ მთლიანი მოგება უდრის თითოეული საწარმოდან მიღებული მოგების ჯამს იყო ყველაზე დიდი. რომელ საწარმოზეა გამოყოფილი თანხების ოდენობა. მეთე საფეხურზე განტოლებები აკმაყოფილებს პირობას: ან რომელ საწარმოს არ გამოვყოფთ არაფერს: ან მეტის...

ლაბორატორიული სამუშაო 4_2. რესურსების განაწილების პრობლემის გადაჭრა დინამიური პროგრამირების მეთოდით.

სამუშაოს მიზანი შეისწავლეთ მაგიდის პროცესორის შესაძლებლობები MS Excel დინამიური პროგრამირების მეთოდის გამოყენებით შეზღუდული რესურსების გამოყოფის პრობლემის გადაჭრა.

მოკლე თეორიული ინფორმაცია

დინამიური პროგრამირების (DP) მოდელის აგება და DP მეთოდის გამოყენება პრობლემის გადასაჭრელად შემდეგნაირად ხდება:

  1. მენეჯმენტის პროცესის ეტაპებად დაყოფის მეთოდის არჩევა;
  2. განსაზღვრეთ მდგომარეობის პარამეტრები და საკონტროლო ცვლადები X k ყოველ ნაბიჯზე;
  3. ჩამოწერეთ მდგომარეობის განტოლებები;
  4. ობიექტური ფუნქციების დანერგვაკ საფეხური და მთლიანი მიზნობრივი ფუნქცია;
  5. გათვალისწინება პირობითი მაქსიმუმები (მინიმუმები) და პირობითი ოპტიმალური კონტროლი kth ნაბიჯი: .
  6. ჩაწერეთ ძირითადი DP გამოთვლითი წრედისთვისბელმანის განტოლებებიამისთვის და წესის მიხედვით:
  1. ბელმანის განტოლებები წყდება თანმიმდევრობით (პირობითი ოპტიმიზაცია) და ფუნქციების ორი თანმიმდევრობით და მიღებულია.
  2. პირობითი ოპტიმიზაციის განხორციელების შემდეგ მიიღება კონკრეტული მდგომარეობის ოპტიმალური გადაწყვეტა:

ა) და

ბ) ჯაჭვის გასწვრივ ოპტიმალური კონტროლი (ხსნარი).

დინამიური პროგრამირების პრობლემის განცხადება ზოგადი ფორმით.

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

f 1 (X)

f2 (X)

f 3 (X)

f 4 (X)

დაადგინეთ რამდენი ფული უნდა გამოიყოს თითოეულ საწარმოს, რათა მთლიანი მოგება (თითოეული საწარმოდან მიღებული მოგების ჯამის ტოლი) იყოს უდიდესი.

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

ამოხსნის დიაგრამა DP მეთოდის გამოყენებით პრობლემას აქვს შემდეგი ფორმა: სახსრების განაწილების გადაწყვეტის პროცესი შეიძლება ჩაითვალოს 4-საფეხურიან პროცესად, საფეხურის ნომერი ემთხვევა საწარმოს ნომერს; ცვლადების განტოლებების არჩევანი 1, 2, 3, 4 ნაბიჯები შესაბამისად; - განაწილების პროცესის საბოლოო მდგომარეობა ნულის ტოლია, რადგან ყველა თანხები უნდა ჩაიდოს წარმოებაში,=0 .

მდგომარეობის განტოლებები და განაწილების სქემა შეიძლება წარმოდგენილი იყოს როგორც:

Აქ - სტატუსის პარამეტრის შემდეგ დარჩენილი თანხების ოდენობაკ -ე ნაბიჯი, ე.ი. თანხები, რომლებიც რჩება დარჩენილთა შორის გასანაწილებლად (4-ლ ) საწარმოები.

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

ბელმანის განტოლებებს აქვს ფორმა:

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

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

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

S k-1

k =3

k =2

k =1

f 3 (X 3 )+

f 2 (X 2 )+

f 1 (X 1 )+

0+4=4

3+0=3

0+4=4

6+0=6

0+6=6

8+0=8

0+6=6

3+4=7

4+0=4

0+7=7

6+4=10

9+0=9

0+10=10

8+6=14

10+0=10

0+8=8

3+6=9

4+4=8

7+0=7

0+9=9

6+7=13

9+4=13

11+0=11

0+13=13

8+10=18

10+6=16

11+0=11

0+13=13

3+8=11

4+6=10

7+4=11

11+0=11

0+13=13

6+9=15

9+7=16

11+4=15

13+0=13

0+16=16

8+13=21

10+10=20

11+6=17

12+0=12

0+16=16

3+13=16

4+8=12

7+6=13

11+4=15

18+0=18

0+18=18

6+13=19

9+9=18

11+7=18

13+4=17

15+0=15

0+19=19

8+16=24

10+13=23

11+10=21

12+6=18

18+0=18

2 ნაბიჯი კ =2. ყველა შესაძლო მნიშვნელობებისთვის, მნიშვნელობები და არის 8 და 9 სვეტებში, შესაბამისად; მე-7 სვეტის პირველი ტერმინები აღებულია მდგომარეობიდან, მეორე ტერმინები აღებულია მე-5 სვეტიდან, როდესაც.

1 ნაბიჯი . პირობითი ოპტიმიზაცია ხორციელდება ცხრილში: k =1 ამისთვის.

თუ, მაშინ=5; ოთხი საწარმოდან მიღებული მოგება, იმ პირობით, რომ = 5 სახსრები დანარჩენ სამ საწარმოს შორის ოპტიმალურად გადანაწილდება, უდრის.

თუ, მაშინ=4; მთლიანი მოგება, იმ პირობით, რომ = 4 სახსრები დანარჩენ სამ საწარმოს შორის ოპტიმალურად გადანაწილდება, უდრის.

ანალოგიურად, როდის და;

როდის და;

როდის და;

მიღებული მნიშვნელობების შედარებისას ვიღებთ ზე.

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

უპასუხე. მაქსიმალური ჯამური მოგებაა 24 აშშ დოლარი. იმ პირობით, რომ 1 საწარმოს გამოყოფილია 1 აშშ დოლარი; მე-2 საწარმოს გამოეყო 2 აშშ დოლარი; მე-3 საწარმო - 1 ​​აშშ დოლარი; მე-4 საწარმო - 1 ​​აშშ დოლარი

დავალების შესრულება ქ MS Excel

  1. საწყისი მონაცემების ცხრილში შეყვანა ნაჩვენებია ნახ. 1-ში.

ნახ.1. წყაროს მონაცემების შეყვანა სამუშაო ფურცლის უჯრედებში MS Excel

2. ცხრილის უჯრების შევსების თანმიმდევრობა:

1). უჯრედში E 15 შეიყვანეთ ფორმულა INDEX($B$3:$F$8,MATCH($C15,$B$3:$B$8),G$12+1) და დააკოპირეთ ფორმულა უჯრედების დიაპაზონში E 15-დან E 35-მდე.

2). უჯრედში F 15 შეიყვანეთ ფორმულა

INDEX($B$3:$F$8,MATCH($D15,$B$3:$B$8),5) და დააკოპირეთ ფორმულა უჯრედების დიაპაზონში F 15-დან F 35-მდე.

3). უჯრედში G 15 შეიყვანეთ ფორმულა E 15+ F 15 და დააკოპირეთ ფორმულა დიაპაზონში: G 15 - G 35.

4). ჩვენ ვპოულობთ მაქსიმალურ მნიშვნელობას თითოეული მდგომარეობისთვის 0-დან 5-მდე, ამ მიზნით უჯრედში H 15 შეიყვანეთ ფორმულა MAX(G15); ფორმულის უჯრედში შეყვანის შემდეგ H 16 საჭიროა დიაპაზონის შეცვლა G 16-დან G 16-მდე: გ 17 და ა.შ. მთელ სვეტში უჯრედამდე H 30 (ნახ. 2a).

3. იპოვეთ საკონტროლო მნიშვნელობა, რომელიც შეესაბამება ფუნქციის მაქსიმალურ მნიშვნელობას, ამ მიზნით უჯრედშიმე 15 შევიყვანოთ ფორმულა INDEX($ C 15: G 15; MATCH (H 15; G 15;0);1), დააკოპირეთ ფორმულა უჯრედშიმე 16 და გაზარდეთ დიაპაზონი, რის შედეგადაც უჯრედიმე 16 ვიღებთ: INDEX($ C 16: G 17; MATCH (H 16; G 16: G 17;0);1). შემდეგი, დააკოპირეთ ფორმულა უჯრედებშიმე 18, მე 21, მე 25, მე 30 , თანდათან იზრდება დიაპაზონი (ნახ. 2ბ)

ნახ.2ა. სამუშაო ფურცლის ტიპი ფორმულებით, k =3.

ნახ.2ბ (სამუშაო ფურცლის მარჯვენა მხარე ფორმულებით, k =3

შედეგად ვიღებთ:

ბრინჯი. 3 . პირველი ნაბიჯის შედეგი ( k =3).

4. აირჩიეთ დიაპაზონი E 15: I 35, შეასრულეთ ბრძანებადააკოპირეთ ჯ 15 და შეასრულეთ ბრძანებაჩასმა .

5. შევცვალოთ ფუნქციის ფორმულა. უჯრედებისკენ K 15, K 16, K 18, K 21, K 25, K 30 ჩვენ შევიყვანთ, შესაბამისად, უჯრედებში მდებარე წინა ნაბიჯის მაქსიმალურ მნიშვნელობებს H 15, H 16, H 18, H 21, H 25, H 30. დანარჩენ უჯრედებში ჩვენ ვათავსებთ მნიშვნელობებს იმავე სვეტში და შეესაბამება წინა მნიშვნელობებსს კ . :

საკანში K 17 დააკოპირეთ K15 უჯრედის მნიშვნელობები;

უჯრედებში K19 და K20 მნიშვნელობები K16 და K17;

K22:K24 მნიშვნელობებში K18:K20;

K26:K29 მნიშვნელობებში K21:K24;

K31:K35 მნიშვნელობებში K25:K29;

შედეგად ვიღებთ:

ნახ.4. მეორე ნაბიჯის შედეგი ( k =2).

6. აირჩიეთ უჯრედების დიაპაზონი J15: N 35, შეასრულეთ ბრძანებაკოპირება , მოათავსეთ კურსორი უჯრედშიო 15, შეასრულეთ ბრძანებაჩასმა . შედეგად, ჩვენ ვიღებთ დასრულებულ ცხრილს ხსნარით k =1 (ნახ.5)

7. ავხსნათ მიღებული შედეგები: ატ. გაანგარიშებით ვიღებთ და მე-12 სვეტის ცხრილიდან ვპოულობთ. შემდეგ ჩვენ განვსაზღვრავთ და მე-6 სვეტიდან. საბოლოოდ და. ამრიგად, ოპტიმალური მნიშვნელობა და ფუნქციის მნიშვნელობა არის 24 cu, რაც შეესაბამება ხელით მიღებულ მონაცემებს.

სურ.6. მესამე ნაბიჯის შედეგი ( k =1).

საკონტროლო ვარჯიშები. Პარამეტრები.

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

f 1 (X)

f2 (X)

f 3 (X)

f 4 (X)

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

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

f 1 (X)

f2 (X)

f 3 (X)

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


ისევე როგორც სხვა ნამუშევრები, რომლებიც შეიძლება დაგაინტერესოთ
58796. გეოგრაფიული ხედვა 977.5 კბაიტი
გაკვეთილის ბოლოს თქვენ უნდა შეგეძლოთ ტექსტში ახალი სიტყვებისა და სიტყვების კომბინაციების ამოცნობა და გაგება, ბუნებრივი სირთულის მიუხედავად წაიკითხოთ და გაიგოთ არსი და დეტალები.
58797. საინფორმაციო და საინფორმაციო პროცესები. გამოთვლითი სისტემა 128 კბ
Zagalny დამახასიათებელი იმ. უსაფრთხოების წესები PEOM ანგარიშზე. Კომპიუტერული მეცნიერება. ინფორმაციის ცნებები. ინფორმაცია და ხმაური. საინფორმაციო პროცესები. ინფორმაცია და შეტყობინება.
58798. Ოპერატიული სისტემა 126 კბ
Სამუშაო მაგიდა. Windows-ის ძირითადი ობიექტები. ობიექტის ხედვა. ოპერაციები, უფლებამოსილებები და ძირითადი ბრძანებები ობიექტებთან მუშაობისთვის. ობიექტის კონტექსტური მენიუ. ეტიკეტები მათი მიზნებისთვისაა.
58799. რობოტიკის საფუძვლები დისკებით 144.5 კბ
ზაგალნი დახასიათება იმ. დისკის ფორმატირება. დისკების დიაგნოსტიკა და დეფრაგმენტაცია. განახლებულია ინფორმაცია დისკზე. ფლოპი დისკებიდან ინფორმაციის ჩაწერისა და წაკითხვის წესები.
58800. Ტექსტის რედაქტორი 190 კბ
ტექსტის დამუშავების სისტემები და მათი ძირითადი ფუნქციები. შთაგონება ტექსტური რედაქტორისთვის. რედაქტორის ინტერფეისი. ინფორმაციის რიგი. ეკრანის რეჟიმები, vikoristannya vikon.
58801. გრაფიკული რედაქტორი 708 კბ
ზაგალნი მათთვის დამახასიათებელია. მანქანის გრაფიკა. გრაფიკული ეკრანი. გრაფიკული ინფორმაციის დამუშავების სისტემა. ჩანართები არის გრაფიკული პრიმიტივების ნახატები რედაქტორთან მუშაობისას. გრაფიკული ფაილების ტიპები.
58802. ელექტრონული მაგიდები 280.5 კბ
ნავჭალნა. აღწერეთ ახალი თემა და მონიშნეთ მისი როლი კომპიუტერული მეცნიერების კურსში. შეიყვანეთ ელექტრონული ცხრილის კონცეფცია. გაეცანით სტუდენტებს ET დამუშავების პროგრამებს, ET-ში ინფორმაციის შეყვანისა და რედაქტირების წესებს და ET-ის ფორმატირების მეთოდებს.
58803. მონაცემთა ბაზის მართვის სისტემები (DBMS) 156.5 კბ
ბასი ხარკი. ფაქტობრივი დოკუმენტური მონაცემთა ბაზა. მონაცემთა ბაზის ირაქიული, მერეჟევური, რელაციური მოდელი. მონაცემთა ბაზის ძირითადი ელემენტები: ველი, ჩანაწერი, ფაილი. DBMS.

დინამიური პროგრამირება (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. განვიხილავთ სისტემას, რომლის მდგომარეობა თითოეულ საფეხურზე განისაზღვრება ვექტორით. მისი მდგომარეობის შემდგომი ცვლილება დამოკიდებულია მხოლოდ ამ მდგომარეობაზე და არ არის დამოკიდებული იმაზე, თუ როგორ მივიდა სისტემა მასზე. ასეთ პროცესებს უწოდებენ პროცესებს შემდგომი ეფექტის გარეშე.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

დავიწყოთ ბოლო ეტაპიდან. მოდით იყოს სისტემის შესაძლო მდგომარეობები მე-4 ეტაპის დასაწყისში. Ჩვენ ვიპოვეთ:

ბოლო ორი ეტაპისთვის ვიღებთ:

ანალოგიურად:

…………………….

…………………….

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

პრობლემის გადაჭრის მაგალითი

Ამოცანა

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

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

გამოყოფილი სახსრები, მილიონი ფულადი ერთეული კომპანია №1 №2 №3 №4 საწარმოებში წარმოების პროდუქციის ზრდა, მილიონი ფულადი ერთეული. 20 10 12 11 16 40 31 24 36 37 60 42 36 45 46 80 62 52 60 63 100 76 74 77 80

პრობლემის გადაწყვეტა

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

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

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

გამოყოფილი თანხები 0 0 0 0 0 20 10 12 11 16 40 31 24 36 37 60 42 36 45 46 80 62 52 60 63 100 76 74 77 80

Ნაბიჯი 1

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

ნაბიჯი 2

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

ნაბიჯი 3

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

ნაბიჯი 4

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

0 0 0 0 0 20 10 12 12 16 40 31 31 36 37 60 42 43 48 52 80 62 62 67 73 100 76 76 79 85

უპასუხე

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

0 20 40 40

ამ შემთხვევაში წარმოების მთლიანი ზრდა მაქსიმალურ მნიშვნელობას 85-ს მიაღწევს.

საშუალოტესტის გადაჭრის ღირებულებაა 700 - 1200 რუბლი (მაგრამ არანაკლებ 300 რუბლი მთელი შეკვეთისთვის). ფასზე დიდ გავლენას ახდენს გადაწყვეტილების გადაუდებლობა (დღიდან რამდენიმე საათამდე). ონლაინ დახმარების ღირებულება გამოცდა/ტესტისთვის არის 1000 რუბლიდან. ბილეთის გადასაჭრელად.

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

დაკავშირებული პრობლემების მაგალითები

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

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

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

- 1.03 MB

მოდით მივცეთ ოპტიმალური პრინციპის მათემატიკური ფორმულირება. სიმარტივისთვის, ჩვენ ვივარაუდებთ, რომ სისტემის საწყისი x 0 და საბოლოო x T მდგომარეობები მოცემულია. z 1-ით (x 0 , u 1) ავღნიშნოთ მიზნის ფუნქციის მნიშვნელობა პირველ ეტაპზე სისტემის საწყისი მდგომარეობით x 0 და კონტროლით u 1, z 2-ით (x 1 , u 2) შესაბამისი. მიზნის ფუნქციის მნიშვნელობა მხოლოდ მეორე ეტაპზე, .., მეშვეობით
z i (x i -1 ,u i) - i-ე საფეხურზე, ..., z N-ის გავლით (x N -1 , u N) - N-ე საფეხურზე. აშკარაა რომ

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

ამ პრობლემის გადასაჭრელად, ჩვენ ჩავძირავთ მას მსგავსთა ოჯახში. მოდით შემოვიტანოთ რამდენიმე აღნიშვნა. მოდით იყოს, შესაბამისად, ტერიტორიები

მსგავსი პრობლემების განმარტებები ბოლო ეტაპზე, ბოლო ორი და ა.შ.;
– საწყისი პრობლემის განსაზღვრის დომენი. ავღნიშნოთ F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0) შესაბამისად, პირობითად ოპტიმალური მიზნის ფუნქციის მნიშვნელობები ბოლო ეტაპზე, ორი ბოლო და ა.შ., ბოლოს k და ა.შ., ყველა N საფეხურზე.

დავიწყოთ ბოლო ეტაპიდან. მოდით x N-1 იყოს სისტემის შესაძლო მდგომარეობები N-ე საფეხურის დასაწყისში. Ჩვენ ვიპოვეთ:

F 1 (x N -1) = z N (x N -1, u N). (2)

ბოლო ორი ეტაპისთვის ვიღებთ

F 2 (x N -2) = (Z N -1 (x N -2, u N -1) + F 1 (x N -1)). (3)

ანალოგიურად:

F 3 (x N -3) = (Z N -2 (x N -3, u N -2) + F 2 (x N -2)). (4)

………………………………………………….

F k (x N -k) = (z N-k +1 (x N -k, u N-k +1) + F k- 1 (x N-k +1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0, u 1) + F N -1 (x 1)). (6)

გამოხატულება (6) არის ოპტიმალური პრინციპის მათემატიკური წარმოდგენა. გამოთქმა (5) არის მიზნობრივი ფუნქციის პირობითად ოპტიმალური მნიშვნელობის ჩაწერის ზოგადი ფორმა k დარჩენილი საფეხურებისთვის. გამონათქვამებს (2) – (6) ეწოდება ბელმანის ფუნქციური განტოლებები. მათი განმეორებადი (განმეორებადი) ბუნება აშკარად ჩანს, ანუ N საფეხურზე ოპტიმალური კონტროლის მოსაძებნად საჭიროა იცოდეთ პირობითად ოპტიმალური კონტროლი წინა N – 1 საფეხურზე და ა.შ. ამიტომ ფუნქციონალურ განტოლებებს ხშირად უწოდებენ განმეორებადს (განმეორებადს). ბელმანის ურთიერთობები.

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

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

  • განვიხილავთ სისტემას, რომლის მდგომარეობა თითოეულ საფეხურზე განისაზღვრება x t ვექტორით. მისი მდგომარეობის შემდგომი ცვლილება დამოკიდებულია მხოლოდ მოცემულ xt მდგომარეობაზე და არ არის დამოკიდებული იმაზე, თუ როგორ მივიდა სისტემა ამ მდგომარეობამდე. ასეთ პროცესებს უწოდებენ პროცესებს შემდგომი ეფექტის გარეშე.
  • ყოველ საფეხურზე არჩეულია ერთი გამოსავალი u t, რომლის გავლენით სისტემა გადადის წინა x t -1 მდგომარეობიდან ახალ x t მდგომარეობაში. ეს ახალი მდგომარეობა არის x t -1 ინტერვალის დასაწყისში არსებული მდგომარეობის ფუნქცია და ინტერვალის დასაწყისში მიღებული გადაწყვეტილება u t, ანუ x t = x t (x t -1 ,u t).
  • ყოველ საფეხურზე მოქმედება დაკავშირებულია გარკვეულ მოგებასთან (შემოსავალთან, მოგებასთან) ან ზარალთან (დანახარჯებთან), რაც დამოკიდებულია საფეხურის (სტადიის) დასაწყისში არსებულ მდგომარეობასა და მიღებულ გადაწყვეტილებაზე.
  • შეზღუდვები შეიძლება დაწესდეს სახელმწიფო და საკონტროლო ვექტორებზე, რომელთა ერთობლიობა წარმოადგენს შესაძლებელი გადაწყვეტილებების რეგიონს.
  • საჭიროა მოიძებნოს ასეთი დასაშვები კონტროლი u t თითოეული საფეხურისთვის, რათა მივიღოთ მიზნის ფუნქციის უკიდურესი მნიშვნელობა ყველა T საფეხურისთვის.

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

დინამიური პროგრამირების პრობლემის გეომეტრიული ინტერპრეტაცია შემდეგია. მოდით n იყოს მდგომარეობის სივრცის განზომილება. დროის თითოეულ მომენტში, სისტემის კოორდინატებს აქვთ ძალიან სპეციფიკური მნიშვნელობა. t დროის ცვლილებით, სახელმწიფო ვექტორის კოორდინატთა მნიშვნელობები შეიძლება შეიცვალოს. სისტემის გადასვლას ერთი მდგომარეობიდან მეორეში დავარქვათ მისი მოძრაობის ტრაექტორია მდგომარეობათა სივრცეში. ასეთი გადასვლა ხორციელდება სახელმწიფო კოორდინატებზე ზემოქმედებით. სივრცეს, რომელშიც სისტემის მდგომარეობები ემსახურება როგორც კოორდინატებს, ეწოდება ფაზური სივრცე. დინამიური პროგრამირების პრობლემის ინტერპრეტაცია შეიძლება განსაკუთრებით მკაფიოდ, თუ სახელმწიფო სივრცე ორგანზომილებიანია. ამ შემთხვევაში შესაძლო მდგომარეობების ფართობი გამოსახული იქნება გარკვეული ფიგურით, სისტემის საწყისი და საბოლოო მდგომარეობები - x 0 წერტილებით (ნახ. 1). კონტროლი არის გავლენა, რომელიც გადასცემს სისტემას საწყისი მდგომარეობიდან საბოლოო მდგომარეობამდე. მრავალი ეკონომიკური პრობლემისთვის, საწყისი ან საბოლოო მდგომარეობა ცნობილი არ არის, მაგრამ ცნობილია X 0 ან X T რეგიონი, რომელსაც ეს პუნქტები ეკუთვნის.

სურათი 1

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

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

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

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

1. ცენტრალური სატუმბი და ფილტრაციის სადგური;

2. აღმოსავლეთის სატუმბი და ფილტრაციის სადგური;

3. წყლის სატუმბი სადგური;

4. ცენტრალური აერაციის სადგური;

5. აღმოსავლეთის აერაციის სადგური;

6. ქვეყნის აერაციის სადგური.

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

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

ობიექტის სერიული ნომერი

ობიექტების განვითარებისთვის გამოყოფილი რესურსების მოცულობა (ათასი UAH)

ობიექტების პროდუქტიულობა განვითარების შედეგად (ათას მ3)
    1. პროგრამის ბლოკ-სქემა

სურათი 1. ძირითადი პროგრამა

QtObj - ობიექტების რაოდენობა


QtRes - რესურსების რაოდენობა

effMatrix - ობიექტის შესრულების მატრიცა,


distVector – გამოყოფილი რესურსების ვექტორი


ნაბიჯი 1: პირობითი ოპტიმიზაცია

ნაბიჯი 2. უპირობო ოპტიმიზაცია


I = QtObj-1.0 ქმნის ვექტორულ შედეგს

სურათი 2. მონაცემთა შეყვანა

distVector – მანძილის ვექტორი, effMatrix = შესრულების მატრიცა

თუ მატრიცის ყველა ელემენტია შეყვანილი



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

უარყოფითი

სურათი 3. პირობითი ოპტიმიზაცია,

ჩვენ ვქმნით გამომავალ მატრიცას (მიზნის ფუნქციის მაქსიმუმი)


outMatrix - მაქსიმალური სამიზნე მატრიცა

QtObj - ობიექტების რაოდენობა

QtRes - რესურსების რაოდენობა

მატრიცა – შესრულების მატრიცა

distVect - მანძილის ვექტორი (რესურსების ვექტორი)

არა დიახ თუ პირველი საწარმო

მაქსიმუმის პოვნა


დიახ maxItem = temp; outMatrix[i][j] = maxItem

    1. პროგრამის ალგორითმის სტრუქტურა
  1. მონაცემთა შეყვანა – კლასი DataDlg.

ცვლადი კლასის წევრები.

//ვექტორი რესურსების რაოდენობის შესანახად

std:: ვექტორი distVector;

//ობიექტის შესრულების მატრიცა

int** effMatrix;

//სტრიქონის რიცხვად გადაქცევის ფუნქცია

int StringToInt(CString);

//ფუნქცია შეყვანილი მონაცემების სისწორის შესამოწმებლად

BOOL FillMatrix();

//რესურსების გაწმენდის ფუნქცია ფანჯრის დახურვის შემდეგ

ვირტუალური BOOL DestroyWindow();

//დიალოგის ინიციალიზაციის ფუნქცია

ვირტუალური BOOL OnInitDialog();

  1. შედეგების გამოთვლა - პროგრამის კურსის ძირითადი კლასიWorkDlg

ცვლადი კლასის წევრები

intValue; //შესრულების ღირებულება

int MaxIndex;// მაქსიმალური ინდექსი რესურსის ვექტორში

int Facility;//საწარმო

int Recource;//გამოყოფილი რესურსი

ელემენტი ** outMatrix; //მაქსიმალური სამიზნე მატრიცა

std:: ვექტორი რესვექტორი; //შედეგების ვექტორი

void BuildOutMatrix(int**,std::vector );//ფუნქცია მიზნის მატრიცის გენერირებისთვის (პირობითი ოპტიმიზაცია)

afx_msg void OnBnClickedButton1( // დამმუშავებელი ღილაკზე „გამოთვლა“ დაწკაპუნებით, რომელიც იწყებს გამოთვლის პროცესს.

ვირტუალური BOOL DestroyWindow();//პროგრამის რესურსების გასუფთავება

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

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

2.4 პროგრამის შედეგები

საწყისი მონაცემების შეყვანა

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

სწორი მონაცემების შეყვანა

შედეგის ჩვენება

  1. მონაცემთა შეყვანა

პროგრამის შედეგი

საწყისი მონაცემების შეყვანა

ობიექტის პროდუქტიულობაში შესვლა

განაცხადი.

პროგრამის ჩამონათვალი

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// ყველა ველი შევსებულია?

BOOL DataDlg::FillMatrix()

bool flag = true;

for (int i = 0; i< Cells.GetSize(); i ++){

for (int j = 0 ; j< Cells.GetAt(i)->Edits.GetSize(); j++)(

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

თუ (ტემპ->m_hWnd != NULL)(

temp->GetWindowText(str);

if (str.IsEmpty())(

MessageBox(L"თქვენ უნდა შეავსოთ ყველა ველი", L"შეცდომა", MB_ICONERROR | MB_OK);

სამუშაოს აღწერა

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

შინაარსი

შესავალი ………………………………………………………………… 2
დინამიური პროგრამირება
ძირითადი ცნებები…………………4
დინამიური პროგრამირების პრინციპები. ბელმანის ფუნქციური განტოლებები…………………….5
დინამიური პროგრამირების პრობლემების თავისებურებები……………….10
რესურსების განაწილების პრობლემა………………………12
პრობლემის ზოგადი განცხადება …………………………….13
პროგრამის ბლოკ-სქემა
პროგრამის ალგორითმის სტრუქტურა
პროგრამის შედეგი
დასკვნა
ბიბლიოგრაფია



გაქვთ შეკითხვები?

შეატყობინეთ შეცდომას

ტექსტი, რომელიც გაეგზავნება ჩვენს რედაქტორებს:

გაგზავნა