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

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

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

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

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

მოგზაური ვაჭრის პრობლემის გადაჭრის ეს ეტაპები უფრო დეტალურად არის აღწერილი ქვემოთ.

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

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

ასე რომ, მოგზაური გამყიდველის პრობლემის გადაჭრის მეთოდი:

1. მატრიცის აგება საწყისი მონაცემებით

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

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

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

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

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

3. სიმების შემცირება

ჩვენ ვასრულებთ მწკრივის შემცირებას - ვაკლებთ მწკრივის თითოეულ ელემენტს შესაბამისი ღირებულებანაპოვნი მინიმუმი (di).

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

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

5. სვეტის შემცირება

მატრიცის თითოეულ ელემენტს ვაკლებთ შესაბამის dj-ს.

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

6. ნულოვანი უჯრედის ქულების გაანგარიშება

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

და ასე შემდეგ ყველა ნულოვანი უჯრედისთვის:

7. მატრიცის შემცირება

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

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

8. თუ სრული გზა ჯერ არ არის ნაპოვნი, გადადით მე-2 წერტილზე, თუ ნაპოვნია, გადადით მე-9 წერტილზე

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

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

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

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

ჩვენს მაგალითში მარშრუტი ასეთია: 4 → 2 → 3 → 1 → 4 .

ბილიკის მთლიანი სიგრძე: L=30.

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

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

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

გალიაუტდინოვი რ.რ.

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

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

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

დაე, დავალება იყოს:

სად დ- სასრული ნაკრები.

ალგორითმი არის განმეორებადი და ყოველი გამეორებისას ის მუშაობს კომპლექტის გარკვეულ ქვეჯგუფთან დ. მოდით ვუწოდოთ ამ ქვეჯგუფს მიმდინარედა აღვნიშნავთ როგორც დ (ქ), სად ქ- გამეორების ინდექსი. პირველი გამეორების დაწყებამდე, როგორც მიმდინარე ნაკრებიშერჩეულია მთელი ნაკრები დ (დ (1) =დ), და მისთვის ზედა შეფასების მნიშვნელობა ობიექტური ფუნქციამაქს f(x)≤ ξ( დ(1)). ალგორითმის სტანდარტული გამეორება შედგება შემდეგი ნაბიჯებისგან:

1°. თუ შეგიძლიათ დაწერეთ გეგმა x (ქ) ∊დ (ქ), რისთვისაც f(x (ქ) ) ≤ξ( დ (ქ)), ეს x (ქ) =X*- პრობლემის გადაწყვეტა (4.29).

2°. თუ ასეთი გეგმა არ არის ნაპოვნი, მაშინ განსაზღვრების დომენი დ (ქ) გარკვეულწილად იყოფა ქვეჯგუფებად დ 1 (ქ) , დ 2 (ქ) , ..., Dlq (ქ) აკმაყოფილებს პირობებს:

თითოეული ქვეჯგუფისთვის, ზედა საზღვრები (ზედა საზღვრები) გვხვდება ობიექტური ξ ფუნქციისთვის დ 1 (ქ) , ξ დ 2 (ქ) , ..., ξ დ ლ 1 (ქ) რომელიც აზუსტებს ადრე მიღებულ შეფასებას ξ დ (ქ), ანუ ξ დ ი (ქ) ≤ ξ დ (ქ) , მე∊1:ლ ქ. ორიდან ერთი შესაძლებელია:

2.1. თუ არის ასეთი გეგმა X (ქ), რა

მაშინ ეს გეგმა ოპტიმალურია.

2.2. თუ ასეთი გეგმა ვერ მოიძებნა, მაშინ არჩეულია ერთ-ერთი ნაკრები დ ი (ქ) , მე∊1:ლ ქ(როგორც წესი, ყველაზე მაღალი ქულებით

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

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

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

4.3.2. CPLP-ის ამოხსნა განშტოებისა და შეკრული მეთოდის გამოყენებით.განვიხილოთ განშტოება-და-შეკრული მეთოდის ალგორითმის გამოყენება CLLP (4.2)-(4.3) ამოსახსნელად. როგორც უკვე აღვნიშნეთ, მეშვეობით დ (ქ) აღნიშნავს პრობლემის შესასრულებელი გეგმების სიმრავლის ქვეჯგუფს. პირველი გამეორების დაწყებამდე ( ქ= 1) მთელი ნაკრები აღებულია როგორც მიმდინარე ნაკრები დ (დ (1) = დ), რის შემდეგაც გადაწყდება სტანდარტული დავალება ხაზოვანი პროგრამირება (დ (1) , ვ). ადვილი მისახვედრია, რომ ის უწყვეტი ანალოგია

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

1) არჩეულია გეგმის ზოგიერთი არამთლიანი კომპონენტი კ (ქ) . ვინაიდან ოპტიმალურ გეგმაში ის უნდა იყოს მთელი რიცხვი, შესაძლებელია შეზღუდვების დაწესება x k ≤ [კ (ქ) ] და x k ≥ [კ (ქ) ]+1. ამრიგად, დ (ქ) იყოფა ქვეჯგუფებად

ნაკრების ასეთი დანაყოფის გრაფიკული ინტერპრეტაცია დ (ქ) მოცემულია ბრინჯი. 4.4.

2) ხაზოვანი პროგრამირების ამოცანები მოგვარებულია

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

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

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

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

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

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

და მის საფუძველზე მიღებული პრობლემის შეზღუდვების სისტემა ( 1 (ქ) , ვ) როგორ

სად x n+1 ≥ 0 - მოჩვენებითი ცვლადი, რომელიც შეესაბამება ნულოვანი კოეფიციენტს ობიექტურ ფუნქციაში, დამატებული უტოლობის მკაცრ თანასწორობაში გადასაყვანად.

ცხადია 1≤ კ≤მვინაიდან ოპტიმალური გეგმის არაძირითადი კომპონენტები ( მ+1≤j≤n) ტოლია ნულის, ანუ აშკარად მთელი რიცხვებია. შემდეგ, საფუძვლის ფორმის შესახებ გაკეთებული ვარაუდების გათვალისწინებით, შეგვიძლია დავწეროთ:

როგორც ჩანს (4.39), ქ კმე-6 სვეტს აქვს მხოლოდ ორი არანულოვანი ელემენტი: in კ-ე და ( მ+1) ხაზები. თუ გამოვაკლებთ ( მ+1)-th განტოლება კ-ე, მაშინ, იმის გათვალისწინებით, რომ [ά კ] – ά კ =-{ά კ), ვიღებთ ექვივალენტურ სისტემას:

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

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

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

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

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

Ø Ø პრობლემები განუყოფელობასთან.

Ø ექსტრემალური კომბინატორული პრობლემები.

Ø Ø პრობლემები წყვეტილ ობიექტურ ფუნქციებთან.

Ø Ø სწორი ჭრა.

Ø Ø გომორის მეთოდი.

Ø Ø ფილიალის და შეკრული მეთოდები.

სატესტო კითხვები

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

4.2. ჩამოაყალიბეთ ზურგჩანთის პრობლემა.

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

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

4.5. რა პრინციპი გამოიყენება გომორის მეთოდით სწორი წყვეტის ასაგებად?

4.6. ჩამოთვალეთ გომორის მეთოდის „დიდი“ გამეორების ძირითადი ნაბიჯები.

4.7. რა როლს ასრულებს ორმაგი სიმპლექსის მეთოდის ალგორითმი მთელი რიცხვის ამოცანის გადაჭრაში?

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

4.8. ჩამოთვალეთ ფუნდამენტური იდეები ფილიალისა და შეკრული მეთოდების უკან.

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

ტოტები და საზღვრები?

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

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

ჭრის შეზღუდვა?

შესავალი

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

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

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

განშტოების საზღვრის ხაზოვანი პროგრამირება

ტოტი და შეკრული მეთოდი

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

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

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

აღმავალი ან დაღმავალი ინდექსები;

ცვლადი წარმოადგენს მნიშვნელოვანი გადაწყვეტილებამიღებულია ამ ამოცანის ფარგლებში;

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

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

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

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

შეზღუდვების ქვეშ

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

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

მოდით აღვნიშნოთ ეს წრფივი პრობლემა ZLP პროგრამირება-0.

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

განშტოებისა და შეკრული მეთოდის შემდეგი ნაბიჯი არის განშტოება ერთ-ერთი მთელი ცვლადის გასწვრივ, რომელსაც აქვს წილადი მნიშვნელობა, მაგ. ამისათვის ჩვენ დავამატებთ ორ ახალ შეზღუდვას ZLP-0 პრობლემას და ეს შეზღუდვები ხსნის ინტერვალს = რომელშიც არ არის მთელი რიცხვები. ამრიგად, განშტოების პროცესში იქმნება ორი ახალი დავალება ZLP-1 და ZLP-2.

სურათი 1.1 ZLP-0 პრობლემის გადაწყვეტა

2. მოვაგვაროთ პრობლემა ZLP-1 გრაფიკულად.

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

სურათი 1.2 ZLP-1 პრობლემის გადაწყვეტა

3. გადავჭრათ ZLP-2 პრობლემა გრაფიკულად.

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

სურათი 1.3 ZLP-2 პრობლემის გადაწყვეტა

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

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

ამ თავის 1 ნაწილი ადგენს ზოგადი იდეაგანშტოება და შეკრული მეთოდი; § 2 -ში - Land and Doig ალგორითმი მთელი რიცხვითი წრფივი პროგრამირების ამოცანისთვის, § 3 - ლიტლის და სხვა ავტორების მეთოდი მოგზაური გამყიდველის პრობლემისთვის.

§ 1. ტოტისა და შეკრული მეთოდის იდეა

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

მინიმიზაცია

იმის გათვალისწინებით, რომ

აქ G არის გარკვეული სასრული ნაკრები.

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

I. ქვედა ზღვრის გამოთვლა (შეფასება).

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

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

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

კომპლექტები, რომლებიც ჯერ არ არის გაყოფილი

ხელახლა დანიშნა

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

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

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

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

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

V. ოპტიმალურობის ნიშანი. დაე

და გეგმა X ეკუთვნის ზოგიერთ ქვეჯგუფს, თუ გარდა ამისა,

მაშინ X არის პრობლემის ოპტიმალური გეგმა (1.1) - (1.2).

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

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

VI. სავარაუდო ამოხსნის სიზუსტის შეფასება. დაე

თუ X არის თავდაპირველი პრობლემის გარკვეული გეგმა (ე.ი.), მაშინ

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

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

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

0 ნაბიჯი. ჩვენ ვიანგარიშებთ შეფასებას. თუ შესაძლებელია ისეთი გეგმის მოძებნა X რომ

მაშინ X არის ოპტიმალური გეგმა.

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

და გადადით საფეხურზე.

1 ნაბიჯი. გამოთვალეთ შეფასებები თუ შესაძლებელია ისეთი გეგმის მოძებნა, რომ ზოგიერთისთვის და

მაშინ X არის ოპტიმალური გეგმა.

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

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

ზოგადი აღწერა

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

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

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

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

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

განაცხადი

მეთოდი გამოიყენება ზოგიერთი NP-სრული პრობლემის გადასაჭრელად, როგორიცაა:

აგრეთვე იხილეთ

შენიშვნები

ფონდი ვიკიმედია.

2010 წელი.

განშტოება და შეკრული მეთოდინახეთ, რა არის „ტოტი და შეკრული მეთოდი“ სხვა ლექსიკონებში: - - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. ელექტროტექნიკის და ენერგეტიკის ინგლისურ-რუსული ლექსიკონი, მოსკოვი] ელექტროტექნიკის თემები, ძირითადი ცნებები EN ფილიალი და შეკრული მეთოდი ...

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

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

ოპტიმალური მარშრუტი მოგზაური გამყიდველისთვის გერმანიის 15 უდიდესი ქალაქის გავლით. მითითებული მარშრუტი არის უმოკლესი ყველა შესაძლო 43,589,145,600 მოგზაურობის გამყიდველის პრობლემა (TSP) (მოგზაური გამყიდველი ... ვიკიპედია ამ ტერმინს სხვა მნიშვნელობა აქვს, იხილეთ Overkill.სრული ძებნა (ან მეთოდი"უხეში ძალა “, ინგლისურიუხეში ძალა ) გადაწყვეტის მეთოდიმათემატიკური ამოცანები

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

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

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

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

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

წიგნები

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