სიმპლექსის მეთოდი არის ამოხსნის მარტივი მაგალითი. მაგალითი - ცხრილის სიმპლექსის მეთოდი

საქონლის სამი ჯგუფის გასაყიდად კომერციულ საწარმოს აქვს სამი სახის შეზღუდული მატერიალური და ფულადი რესურსი b 1 = 240, b 2 = 200, b 3 = 160 ერთეულის ოდენობით. ამავდროულად, საქონლის 1 ჯგუფის გასაყიდად 1 ათასი რუბლი. სასაქონლო ბრუნვა, პირველი ტიპის რესურსი იხარჯება 11 = 2 ერთეულის ოდენობით, მეორე ტიპის რესურსი 21 = 4 ერთეულის ოდენობით, მესამე ტიპის რესურსი 31 = ოდენობით. 4 ერთეული. იყიდება 2 და 3 ჯგუფის საქონლის 1 ათასი რუბლი. ბრუნვა იხარჯება პირველი ტიპის რესურსის მიხედვით 12 = 3, a 13 = 6 ერთეულის ოდენობით, მეორე ტიპის რესურსი 22 = 2, 23 = 4 ერთეული, რესურსი მესამე ტიპი ოდენობით 32 = 6, 33 = 8 ერთეული. მოგება სამი ჯგუფის საქონლის გაყიდვიდან 1 ათასი რუბლით. ბრუნვა არის შესაბამისად c 1 = 4, c 2 = 5, c 3 = 4 (ათასი რუბლი). განსაზღვრეთ სავაჭრო ბრუნვის დაგეგმილი მოცულობა და სტრუქტურა ისე, რომ სავაჭრო საწარმოს მოგება იყოს მაქსიმალურად.

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

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

მოდით x 1, x 2, x 3 იყოს გაყიდული საქონლის რაოდენობა, ათასი რუბლით, შესაბამისად, 1, 2, 3 ჯგუფი. შემდეგ პრობლემის მათემატიკურ მოდელს აქვს ფორმა:

F = 4 x 1 + 5 x 2 + 4 x 3 -> მაქს

0)))(~)" title="delim(lbrace)(მატრიცა(4)(1)(2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

ჩვენ ვხსნით სიმპლექსის მეთოდს.

ჩვენ შემოგთავაზებთ დამატებით ცვლადებს x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, რათა გარდაქმნას უტოლობები ტოლებად.

საფუძვლად ავიღოთ x 4 = 240; x 5 = 200; x 6 = 160.

ჩვენ შევიყვანთ მონაცემებს სიმპლექსის მაგიდა

Simplex ცხრილი No1

ობიექტური ფუნქცია:

0 240 + 0 200 + 0 160 = 0

ჩვენ ვიანგარიშებთ შეფასებებს ფორმულის გამოყენებით:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

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

ჩვენ ვნერგავთ ცვლადს x 2 საფუძველში.

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

= 26.667

ყველაზე პატარა არაუარყოფითი: Q 3 = 26.667. ჩვენ გამოვიყვანთ ცვლადი x 6 საფუძვლიდან

გაყავით მე-3 ხაზი 6-ზე.
1 სტრიქონს გამოაკელი მე-3 სტრიქონი, გამრავლებული 3-ზე
მე-2 სტრიქონს გამოვაკლოთ მე-3 სტრიქონი, გამრავლებული 2-ზე

ჩვენ ვიანგარიშებთ:

ჩვენ ვიღებთ ახალ ცხრილს:

Simplex ცხრილი No2

ობიექტური ფუნქცია:

0 160 + 0 440/3 + 5 80/3 = 400/3

ჩვენ ვიანგარიშებთ შეფასებებს ფორმულის გამოყენებით:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

ვინაიდან არსებობს უარყოფითი შეფასება Δ 1 = - 2/3, გეგმა არ არის ოპტიმალური.

ჩვენ ვნერგავთ ცვლადს x 1 საფუძველში.

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

ყველაზე პატარა არაუარყოფითი: Q 3 = 40. ჩვენ გამოვიყვანთ ცვლადი x 2 საფუძვლიდან

გაყავით მე-3 ხაზი 2/3-ზე.
მე-2 სტრიქონს გამოვაკლოთ მე-3 სტრიქონი, გამრავლებული 8/3-ზე

ჩვენ ვიანგარიშებთ:

ჩვენ ვიღებთ ახალ ცხრილს:

Simplex ცხრილი No3

ობიექტური ფუნქცია:

0 160 + 0 40 + 4 40 = 160

ჩვენ ვიანგარიშებთ შეფასებებს ფორმულის გამოყენებით:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

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

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

უპასუხე

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

ანუ აუცილებელია პირველი ტიპის საქონლის გაყიდვა 40 ათასი რუბლის ოდენობით. მე-2 და მე-3 ტიპის პროდუქციას არ სჭირდება გაყიდვა. ამ შემთხვევაში, მაქსიმალური მოგება იქნება F max = 160 ათასი რუბლი.

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

ორმაგ პრობლემას აქვს ფორმა:

Z = 240 y 1 + 200 y 2 + 160 y 3 -> წთ

Title="delim(lbrace)(მატრიცა(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

ჩვენ შემოგთავაზებთ დამატებით ცვლადებს y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 უტოლობების ტოლებად გადაქცევისთვის.

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

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

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

გაფრთხილება

გაასუფთავო ყველა უჯრედი?

დახურეთ გასუფთავება

მონაცემთა შეყვანის ინსტრუქციები.რიცხვები შეყვანილია როგორც მთელი რიცხვები (მაგალითები: 487, 5, -7623 და ა.შ.), ათწილადები (მაგ. 67., 102.54 და ა.შ.) ან წილადები. წილადი უნდა შეიტანოს a/b სახით, სადაც a და b (b>0) არის მთელი რიცხვები ან ათობითი რიცხვები. მაგალითები 45/5, 6.6/76.4, -7/6.7 და ა.შ.

მარტივი მეთოდი

ZLP-ის ამოხსნის მაგალითები სიმპლექსის მეთოდით

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

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

მოდით ჩამოვწეროთ მიმდინარე საცნობარო გეგმა:

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

ეს საცნობარო გეგმა არ არის ოპტიმალური, რადგან ბოლო რიგს აქვს უარყოფითი ელემენტი (-3), ამიტომ საფუძველი მოიცავს ვექტორს x 1 . ვადგენთ რომელი ვექტორი გამოდის საფუძვლიდან. ამისათვის ჩვენ ვიანგარიშებთ ზე . min(44/3:11/3, 62/3:5/3)=4 შეესაბამება მე-2 ხაზს. ვექტორი გამოდის საფუძვლიდან x 4 . მოდით გავაკეთოთ გაუსის ელიმინაცია სვეტისთვის x 1, იმის გათვალისწინებით, რომ წამყვანი ელემენტი შეესაბამება 2 რიგს. მოდით გადავაყენოთ ამ სვეტის ყველა ელემენტი წამყვანი ელემენტის გარდა. ამისათვის დაამატეთ 1, 3, 4 სტრიქონები 2 სტრიქონით გამრავლებული 1/11, -5/11, 9/11 შესაბამისად. შემდეგი, ჩვენ ვყოფთ ხაზს წამყვანი ელემენტით წამყვანი ელემენტით.

სიმპლექსის ცხრილი მიიღებს შემდეგ ფორმას:

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

გამოსავალი შეიძლება დაიწეროს ასე: .

ობიექტური ფუნქციის მნიშვნელობა ამ ეტაპზე: ფ(X)=.

მაგალითი 2. იპოვეთ ფუნქციის მაქსიმუმი

გამოსავალი.

ბაზის ვექტორები x 4 , x 3 ამიტომ ყველა ელემენტი სვეტებში x 4 , xჰორიზონტალური ხაზის ქვემოთ 3 უნდა იყოს ნული.

სვეტის ყველა ელემენტის გადატვირთვა ნულამდე x 4, გარდა წამყვანი ელემენტისა. ამისათვის დაამატეთ მე-3 მწკრივი 1 მწკრივით გამრავლებული 4-ზე. სვეტის ყველა ელემენტის ნულზე გადატვირთვა x 3, გარდა წამყვანი ელემენტისა. ამისათვის დაამატეთ 3 სტრიქონი მე-2 სტრიქონით გამრავლებული 1-ზე.

მარტივი ცხრილი მიიღებს ფორმას:

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

ZLP-ის ამოხსნის მაგალითები ხელოვნური ბაზის მეთოდით

მაგალითი 1. იპოვეთ ფუნქციის მაქსიმუმი

ამოხსნა იმის გამო, რომ საბაზისო ვექტორების რაოდენობა უნდა იყოს 3, ჩვენ ვუმატებთ ხელოვნურ ცვლადს, ხოლო ობიექტურ ფუნქციას ვამატებთ −M-ზე გამრავლებულს, სადაც M არის ძალიან დიდი რიცხვი.

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

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

მოდით გადავაყენოთ სვეტის ყველა ელემენტი წამყვანი ელემენტის გარდა. ამისათვის დაამატეთ მე-5 სტრიქონი მე-3 სტრიქონით გამრავლებული -1-ზე.

მარტივი ცხრილი მიიღებს ფორმას:

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

სიმპლექსის ცხრილი მიიღებს შემდეგ ფორმას:

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

სიმპლექსის ცხრილი მიიღებს შემდეგ ფორმას:

ეს საცნობარო გეგმა არ არის ოპტიმალური, რადგან ბოლო რიგში არის უარყოფითი ელემენტები. ყველაზე დიდი უარყოფითი ელემენტია მოდულში (-13/2), ამიტომ საფუძველი მოიცავს ვექტორს x 3. ვადგენთ რომელი ვექტორი გამოდის საფუძვლიდან. ამისათვის ჩვენ ვიანგარიშებთ ზე შეესაბამება მე-3 ხაზს. ვექტორი გამოდის საფუძვლიდან x 5 . მოდით გავაკეთოთ გაუსის ელიმინაცია სვეტისთვის x 3, იმის გათვალისწინებით, რომ წამყვანი ელემენტი შეესაბამება 3 მწკრივს. მოდით გადავაყენოთ ამ სვეტის ყველა ელემენტი წამყვანი ელემენტის გარდა. ამისათვის დაამატეთ 1, 2, 4 ხაზის ხაზები მე-3 სტრიქონთან, გამრავლებული შესაბამისად 5/3, 25/9, 65/9. შემდეგი, ჩვენ ვყოფთ ხაზს წამყვანი ელემენტით წამყვანი ელემენტით.

სიმპლექსის ცხრილი მიიღებს შემდეგ ფორმას:

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

ორიგინალური პრობლემის გადაწყვეტა შეიძლება დაიწეროს შემდეგნაირად:

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

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

ბაზის ვექტორები x 4 , x 5 , x 6 ამიტომ ყველა ელემენტი სვეტებში x 4 , x 5 , x 6, ჰორიზონტალური ხაზის ქვემოთ უნდა იყოს ნული.

სვეტის ყველა ელემენტის გადატვირთვა ნულამდე x 4, გარდა წამყვანი ელემენტისა. ამისათვის დაამატეთ მე-4 სტრიქონი 1 სტრიქონით გამრავლებული -1-ზე. სვეტის ყველა ელემენტის გადატვირთვა ნულამდე x 5, გარდა წამყვანი ელემენტისა. ამისათვის დაამატეთ მე-5 სტრიქონი მე-2 სტრიქონით გამრავლებული -1-ზე. სვეტის ყველა ელემენტის გადატვირთვა ნულამდე x 6, გარდა წამყვანი ელემენტისა. ამისათვის დაამატეთ მე-5 სტრიქონი მე-3 სტრიქონით გამრავლებული -1-ზე.

მარტივი ცხრილი მიიღებს ფორმას:

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

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

სიმპლექსის მეთოდის ალგორითმი შემდეგია:

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

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

პრობლემას კანონიკურ ფორმაში მივყავართ:

ჩვენ ვადგენთ ვექტორებს:

შეავსეთ მარტივი ცხრილი:

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

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

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

არ არსებობს უარყოფითი ელემენტები ვ- ხაზი ნიშნავს ნაპოვნი ოპტიმალური გეგმა:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. ხაზოვანი პროგრამირება, M: Nauka, 1998,
• ვენტცელი ე.ს. ოპერაციების კვლევა, M: საბჭოთა რადიო, 2001 წ.
• კუზნეცოვი იუ.ნ., კუზუბოვი ვ.ი., ვოლოშენკო ა.ბ. მათემატიკური პროგრამირება, M: უმაღლესი სკოლა, 1986 წ.

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

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

ლექცია 3.მარტივი მაგიდები. სიმპლექსის მეთოდის ალგორითმი.

§ 3 SIMPLEX მეთოდი

3.1. სიმპლექსის მეთოდის ზოგადი იდეა. გეომეტრიული ინტერპრეტაცია

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

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

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

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

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

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

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

სიმპლექსის მეთოდის განსახორციელებლად - ხსნარის თანმიმდევრული გაუმჯობესება - საჭიროა დაუფლება სამი ძირითადი ელემენტი:

პრობლემის ნებისმიერი საწყისი შესაძლო ძირითადი გადაწყვეტის განსაზღვრის მეთოდი;

საუკეთესო (უფრო ზუსტად, არა უარეს) გადაწყვეტაზე გადასვლის წესი;

ნაპოვნი ამოხსნის ოპტიმალურობის შემოწმების კრიტერიუმი.

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

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

3.2. სიმპლექსის მეთოდის ალგორითმი.

განვიხილოთ ZLP-ის ამოხსნა სიმპლექსის მეთოდის გამოყენებით და წარმოვადგინოთ იგი მაქსიმიზაციის პრობლემასთან მიმართებაში.

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

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

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

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

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

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

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

ა) თუ შიგნით
– რიგში არ არის უარყოფითი ელემენტები (თავისუფალ ტერმინს არ ჩავთვლით), მაშინ გეგმა ოპტიმალურია. თუ არ არის ნულები, მაშინ არსებობს მხოლოდ ერთი ოპტიმალური გეგმა; თუ არის მინიმუმ ერთი ნული, მაშინ არის ოპტიმალური გეგმების უსასრულო რაოდენობა;

ბ) თუ გ
– მწკრივში არის მინიმუმ ერთი უარყოფითი ელემენტი, რომელიც შეესაბამება არაპოზიტიური ელემენტების სვეტს
;

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

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

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

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

1) შეხედეთ ხაზს, რომელიც შეესაბამება ზოგიერთ უარყოფით თავისუფალ ტერმინს, მაგალითად – სტრიქონი და აირჩიეთ მასში ნებისმიერი უარყოფითი ელემენტი და შესაბამისი სვეტი მიიღება გადამჭრელად (ვვარაუდობთ, რომ პრობლემის შეზღუდვები თანმიმდევრულია);

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

3) ამოირჩიეთ უმცირესი მარტივი ურთიერთობებიდან. ეს განსაზღვრავს ჩართვის სტრიქონს. დაე, მაგალითად, რ- ხაზი;

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

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

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

ობიექტური ფუნქცია:

2x 1 +5x 2 +3x 3 +8x 4 →წთ

შეზღუდვის პირობები:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

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

ვინაიდან ჩვენი პრობლემა არის მინიმიზაციის პრობლემა, ჩვენ უნდა გადავაქციოთ ის მაქსიმალურ საძიებო პრობლემად. ამისათვის ჩვენ ვცვლით ობიექტური ფუნქციის კოეფიციენტების ნიშნებს საპირისპიროზე. ჩვენ ვწერთ პირველი უტოლობის ელემენტებს უცვლელად, ვამატებთ დამატებით ცვლადს x 5 და ვცვლით ნიშანს „≤“ „="-ზე. ვინაიდან მეორე და მესამე უტოლობას აქვს „≥“ ნიშნები, აუცილებელია მათი კოეფიციენტების ნიშნები საპირისპიროდ შეიცვალოს და მათში შეიყვანოთ დამატებითი ცვლადები x 6 და x 7, შესაბამისად. შედეგად, ჩვენ ვიღებთ ექვივალენტურ პრობლემას:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

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

					თავისუფალი წევრი
ფ
X5
X6
X7

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

	X1	X2	X6	X4	თავისუფალი წევრი
ფ	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

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

	X1	X7	X6	X4	თავისუფალი წევრი
ფ	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

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

	X2	X7	X6	X4	თავისუფალი წევრი
ფ	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

ვინაიდან F სტრიქონში უარყოფითი ელემენტები არ არის, ნაპოვნია ოპტიმალური გადაწყვეტა. ვინაიდან თავდაპირველი ამოცანა იყო მინიმალურის პოვნა, ოპტიმალური გადაწყვეტა იქნება F სტრიქონის თავისუფალი ვადა, აღებული საპირისპირო ნიშნით. F=1.924
ცვლადი მნიშვნელობებით ტოლია: x 3 =0.539, x 1 =0.153. ცვლადები x 2 და x 4 არ შედის საფუძველში, ამიტომ x 2 =0 x 4 =0.