განათლების ფედერალური სააგენტო

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

პერმის სახელმწიფო ტექნიკური უნივერსიტეტი

ლისვენსკის ფილიალი

ეკონომიკის დეპარტამენტი

კურსის მუშაობა

დისციპლინის მიხედვით" სისტემის ანალიზიდა ოპერაციების კვლევა"

თემაზე: „მარტივი მეთოდი პრეზენტაციის სახით“

დაასრულა VIVT-06-1 ჯგუფის სტუდენტმა:

სტარცევა ნ.ს.

შემოწმებულია მასწავლებლის მიერ:

მუხამეტიანოვი ი.ტ.

ლისვა 2010 წ

შესავალი. 3

მათემატიკური პროგრამირება. 5

გრაფიკული მეთოდი. 6

ტაბულური სიმპლექსის მეთოდი. 6

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

მოდიფიცირებული სიმპლექსის მეთოდი. 7

Dual simplex - მეთოდი. 7

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

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

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

თეორემა 1: 13

თეორემა 2: 14

თეორემა 3: 15

თეორემა 4: 15

თეორემა 5: 15

ახალზე გადასვლა საცნობარო გეგმა. 15

ორმაგი დავალება. 17

თეორემა 1 (პირველი ორმაგობის თეორემა) 18

თეორემა 2 (მეორე ორმაგობის თეორემა) 18

დასკვნა. 20

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

7x 1 +5x 2 →მაქს

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 ორიგინალური საცნობარო გეგმა

x 6 =18-3x 1 F(x 1, x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

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

x 1 =წთ(19/2;13/2;∞;18/3)=6

ეს ნიშნავს, რომ როდესაც x 1 =6, x 6 =0, ანუ x 1 შედის ძირითად რიცხვში, ხოლო x 6 შედის თავისუფალითა რიცხვში.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2; x 6) =42-7/3 x 6 +5 x 2

მოცემული საცნობარო გეგმით (6;0;7;1;15;0) x 2 გადაიტანეთ თავისუფალიდან ძირითად ცვლადებზე:

x 2 =წთ(∞;7/3;1/11;15/3)=1

გამოხატეთ x2-დან x4-მდე

x 2 =1+2/3 x 6 - x 4

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

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 დადებითია, ამიტომ შეიძლება გაიზარდოს

x 6 =წთ(18;∞;3;6)=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

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

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

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

αX=(αx 1 , x 2 ,…, αx n)

X+Y=(x 1 +y 1, x 2 +y 2,… x n +y n)

წრფივი კოორდინატები X 1 ,X 2 ,…X n ეწოდება წერტილი P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

ნაკრები P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 i= 1,…k n åR i =1, 1≤ i ≤k წერტილების ამოზნექილი წრფივი კომბინაცია x 1 ,x 2,…x n. თუ k=2, მაშინ ამ სიმრავლეს სეგმენტი ეწოდება. X 1,X 2 – სეგმენტის ბოლოები. დახურული ნაკრების კუთხის წერტილი არის წერტილი, რომელიც არ არის სიმრავლის წერტილების არატრივიალური წრფივი კომბინაცია (კუთხის წერტილი).

არატრივიალურობა ნიშნავს, რომ მინიმუმ ერთი λ განსხვავდება 0-დან ან 1-დან.

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

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

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

ახალ საცნობარო გეგმაზე გადასვლა

F 1 =F (x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 შეიძლება დადასტურდეს, სადაც υ k არის ზემოთ განხილული მინიმუმი, რომელიც განისაზღვრება საფუძველში k-ე ცვლადის შეყვანით და Δ k =åс j x j (1) -С k, სადაც n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) არის k-ე ცვლადის შეფასება , ასე რომ, თუ მაქსიმალური პრობლემა მოგვარებულია, მაშინ მნიშვნელობა ΔF 2 უნდა იყოს დადებითი, Δk უნდა იყოს უარყოფითი. მინიმალური ამოცანების ამოხსნისას ΔF 2 უარყოფითია, Δ k დადებითია. ეს მნიშვნელობები გამოითვლება და თუ ΔF 2-ს შორის ყველა მნიშვნელობა არ არის დადებითი, მაშინ პრობლემების მინიმუმზე გადაჭრისას პირიქით ხდება. თუ მაქსიმუმის ამოხსნისას ΔF 2-ს შორის არის რამდენიმე დადებითი, მაშინ საფუძველში შემოვიყვანთ ვექტორს, რომლითაც ეს მნიშვნელობა აღწევს მაქსიმუმს, ხოლო თუ პრობლემა მოგვარებულია მინიმუმზე და ΔF 2-ს შორის არის რამდენიმე უარყოფითი. პირობა, შემდეგ ვექტორი ერთად ყველაზე დაბალი ღირებულებაΔF 2, ანუ უდიდესით აბსოლუტური მნიშვნელობა. როდესაც ეს პირობები დაკმაყოფილებულია, გარანტირებულია ფუნქციის მნიშვნელობის ყველაზე დიდი შესაძლო ცვლილება.

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

თუ რომელიმე Δ k-სთვის x k ≤ 0 ცვლადის კოეფიციენტები ეწინააღმდეგება ოპტიმალურობის პირობას, მაშინ შეზღუდვების სისტემა შეზღუდული არ არის, ე.ი. ოპტიმალური გეგმაარ არსებობს.

ორმაგი პრობლემა

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

ორმაგი პრობლემაა:

პირდაპირი ამოცანის შეზღუდვების რაოდენობის შესაბამისი 1. m ცვლადები;

2. n შეზღუდვა, რომელიც შეესაბამება პირდაპირი პრობლემის ცვლადების რაოდენობას.

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

· თითოეული შეზღუდვა b i PD შეესაბამება ცვლადს y i PD;

· თითოეული ცვლადი x j PD შეესაბამება შეზღუდვას C j PD;

· PD შეზღუდვებში x j-ის კოეფიციენტები ხდება შესაბამისი PD შეზღუდვის მარცხენა მხარის კოეფიციენტები;

· კოეფიციენტები C j x j-სთვის PD-ის სამიზნე ფუნქციაში ხდება მუდმივი PD შეზღუდვის მარჯვენა მხარეს;

· შეზღუდვის მუდმივები b i PD ხდება სამიზნე ფუნქციის PD კოეფიციენტები.

განვიხილოთ შემდეგი ორი პრობლემა:

F = С 1 x 1 +С 2 x 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 x 1 +b 2 x 2 +... +b n x n →წთ

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

. . . . . . . . . . . . . . . . . . . . . . .

a 1 n y n + a 2 m y n + ... + a nm y n ≤C n

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

1. მათემატიკური მეთოდების საფუძვლები და მათი გამოყენება;

2. ამოცანების ამოხსნა სიმპლექსის მეთოდით.

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

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

(2.23)

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

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

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

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

მოდით განვსაზღვროთ იდენტურობის მატრიცა შემდეგი გზით:

(2.24)

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

(2.25)

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

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

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

ამ მეთოდმა მიიღო რამდენიმე სხვადასხვა ფორმები(მოდიფიკაციები) და შეიქმნა 1947 წელს გ.დანციგის მიერ.

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

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

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

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

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

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

• 1. პირველი ციკლის დასაწყისში ჩვენ ვიცით შებრუნებული მატრიცა ( პირადობის მატრიცა), ძირითადი ამოხსნა x b = b.
• 2. ყოველი არაძირითადი ცვლადი, ჩვენ ვქმნით დამახასიათებელ განსხვავებას j განტოლების გამოყენებით:

j = c j -- = c j -- P j , (2)

სად არის ორმაგი ცვლადები, რომლებიც შეიძლება მოიძებნოს შემდეგნაირად:

სადაც c x არის ძირითადი ცვლადების ობიექტური ფუნქციის კოეფიციენტების ვექტორი.

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

• 4. თუ s 0, პროცედურა ჩერდება. არსებული ძირითადი გადაწყვეტა ოპტიმალურია.
• 5. თუ s 0, გამოთვალეთ გარდაქმნილი სვეტი:

= (, ...,) . (2.4)

თუ ყველა არის 0, პროცედურა ჩერდება: ოპტიმალური შეუზღუდავია.

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

8. ჩვენ ვაშენებთ გაფართოებულ მატრიცას:

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

9. ძირითადი ამოხსნის გარდაქმნა:

x b i x b i -- * , i r, (2.7)

და გადავიდეთ მე-2 ეტაპზე.

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

ამისათვის საჭიროა:

• 1. შეინახეთ დავალების ორიგინალური ჩანაწერი მეთოდის მთელი მუშაობის განმავლობაში, ეს არის ფასი, რომელიც უნდა გადაიხადოთ უფრო დიდი შესრულებისთვის;
• 2. გამოიყენე ეგრეთ წოდებული simplex - მულტიპლიკატორები p - კოეფიციენტები პრობლემის თავდაპირველი ჩანაწერიდან მის დღევანდელ კანონიკურ საფუძველზე გადასვლისთვის;
• 3. გამოიყენეთ შებრუნებული საფუძველი BO№ - m x m ზომის მატრიცა, რომელიც საშუალებას გაძლევთ გამოთვალოთ წამყვანი სვეტი aґs ყოველ საფეხურზე და განაახლოთ simplex - ფაქტორები p.

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

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

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

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

Კარგი ნამუშევარიასაიტზე">

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

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

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

რეზიუმე, დამატებულია 06/15/2010


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

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


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

ტესტი, დამატებულია 08/15/2012


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

ტესტი, დამატებულია 02/18/2014


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

ტესტი, დამატებულია 05/11/2014


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

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


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

ტესტი, დამატებულია 06/01/2014

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

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

მაქსიმუმი Z = c x,
მიხედვით
A x ≤ b და x ≥ 0,
სადაც c არის მწკრივის ვექტორი
x, b და 0 სვეტის ვექტორები

A - მატრიცა
გაძლიერებული ფორმისთვის, სვეტის ვექტორი
მოჩვენებითი ცვლადები:
შეზღუდვები:
I = (m × m იდენტურობის მატრიცა)
0 = (ნულოვანი ვექტორის n + m ელემენტები)

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

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

და საბაზისო მატრიცა
შესაბამისი სვეტების გამოკლებით მიღებული შედეგი
არასაბაზისო ცვლადების კოეფიციენტები დან.
(გარდა ამისა, xB ელემენტები და B სვეტები განსხვავებულები არიან
კარგი). მარტივი მეთოდი შემოაქვს მხოლოდ ძირითად
ცვლადები ისეთი, რომ B არის არადეგენერატი, ასე რომ
ინვერსიული მატრიცა B-1 ყოველთვის იარსებებს.
B x B = b ამოსახსნელად ორივე მხარე მრავლდება B-1-ზე:
B-1 B x B = B-1 ბ.

cB არის ვექტორი, რომლის ელემენტებია კოეფიციენტები
ობიექტური ფუნქციები (მათ შორის ნულები მოტყუებისთვის
ცვლადები) შესაბამისი xB ელემენტებისთვის.
ამ ძირითადი ამოხსნის ობიექტური ფუნქციაა:

მაგალითი:
- გამეორება 0
ისე
ისე

10.

- გამეორება 1
ისე
ისე

11.

- გამეორება 2
ისე
ისე

12. მატრიცული ფორმა განტოლებათა მიმდინარე სიმრავლისთვის

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

13.

14.

ამ მატრიცას ექნება იგივე ელემენტები, რაც იდენტობის მატრიცას
მატრიცა, გარდა იმისა, რომ თითოეული პროდუქტი
გარკვეული ალგებრული ოპერაციისთვის დასჭირდება
ამ ოპერაციის შესასრულებლად საჭირო სივრცე,
მატრიცის გამრავლების გამოყენებით. სერიალის მერეც
ალგებრული მოქმედებები რამდენიმე გამეორებაზე,
ჩვენ მაინც შეგვიძლია დავასკვნათ, რომ ეს მატრიცა
უნდა იყოს მთელი სერიისთვის, იმის გამოყენებით, რაც ვიცით
მარჯვენა მხარე ახალი სისტემაგანტოლებები. ნებისმიერის შემდეგ
გამეორებები, xB = B-1b და Z = cB B-1b, ამიტომ მარჯვენა მხარეები
განტოლებათა ახალმა სისტემამ მიიღო ფორმა

15.

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

16.

მაგალითი: მატრიცული ფორმა, რომელიც მიღებულია გამეორების შემდეგ 2
მინის ქარხნის პრობლემისთვის B-1 და cB გამოყენებით:

17.

xB = B-1 b და Z = cB B-1 b რაოდენობების გამოყენებით:

18.

გაანგარიშებისთვის უნდა მიიღოთ მხოლოდ B-1
სიმპლექსის ცხრილის ყველა ნომერი ორიგინალიდან
დავალების პარამეტრები (A, b, cB). რომელიმე ამ ნომრიდან
შეიძლება ინდივიდუალურად მიიღოთ როგორც
როგორც წესი, მხოლოდ ვექტორული გამრავლება ხდება
(ერთი მწკრივი თითო სვეტში) სრულის ნაცვლად
მატრიცის გამრავლება. საჭირო ნომრები
სიმპლექსის მეთოდის გამეორებების შესრულება შეიძლება იყოს
მიიღეთ საჭიროებისამებრ დახარჯვის გარეშე
არასაჭირო გამოთვლები ყველა ნომრის მისაღებად.

19. მოდიფიცირებული სიმპლექსის მეთოდის მოკლე მიმოხილვა

1. ინიციალიზაცია: როგორც ორიგინალური სიმპლექსის მეთოდი.
2. გამეორება: ნაბიჯი 1 განსაზღვრეთ შეყვანილი ძირითადი (ძირითადი)
ცვლადები: როგორც ორიგინალური სიმპლექსის მეთოდში.
ნაბიჯი 2 განსაზღვრეთ გამავალი საბაზისო ცვლადები: როგორც ორიგინალში
სიმპლექსის მეთოდი, გამონაკლისია მხოლოდ იმათთვის, რაც აუცილებელია
ამ რიცხვებიდან [დანერგილი ძირითადი ცვლადების კოეფიციენტები
თითოეული განტოლება განტოლების გარდა. (0) და შემდეგ, თითოეული მკაცრად
დადებითი კოეფიციენტი მარჯვენა ნაწილიეს განტოლება].
ნაბიჯი 3 ახალი OD ამოხსნის განსაზღვრა: მიიღეთ B-1 და დააყენეთ xB=B-1b.
3. ოპტიმალურობის ანალიზი: როგორც ორიგინალური სიმპლექსის მეთოდში, ამისთვის
გარდა ამ ანალიზისთვის საჭირო მხოლოდ რიცხვების დათვლისა,
ანუ არასაბაზისო (არაძირითადი) ცვლადების კოეფიციენტები ში
განტოლება (0).
გამეორების მე-3 საფეხურზე B-1 შეიძლება მიღებულ იქნას ყოველ ჯერზე გამოყენებით
სტანდარტული კომპიუტერული პროგრამაშებრუნებისთვის (ინვერსიისთვის)
მატრიცები. ვინაიდან B (შემდეგ B-1) ოდნავ იცვლება ერთი გამეორებიდან
სხვა, უფრო ეფექტურია ახალი B-1-ის (აღნიშნული B-1 ახალი) მიღება
B-1 წინა გამეორებაში (B-1 ძველი). (OA ორიგინალური ხსნარისთვის).