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

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

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

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

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

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

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

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

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

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

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

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

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

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

პირველი მწკრივიდან და მეორე სვეტიდან შეგიძლიათ გამოაკლოთ თითო-თითო, რაც ქვედა ზღვარს 2-ით გაზრდის და 9-ის ტოლია.

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

ერთი შეიძლება გამოკლდეს მის პირველ სტრიქონს და პირველ სვეტს, რის შედეგადაც მიიღება მატრიცა

ქვედა ქულა აქ იზრდება 2-ით და ასევე ხდება 9-ის ტოლი.

ციკლის ოპტიმალური სიგრძის ქვედა ზღვარი უცვლელი რჩება.

რკალი (2.5) უნდა აიკრძალოს, რადგან იწვევს არაჰამილტონის ციკლის გამოჩენას და მატრიცა იღებს ფორმას.

ჰამილტონის ციკლის ხანგრძლივობის ქვედა ზღვარი 9-ის ტოლია.

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

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

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

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

შესავალი ..................................................... .......................................................... ..... 3

1. ..…………….4

2. ფილიალი და შეკრული მეთოდი………………………………………..6

2.1 განშტოებისა და კიდეების მეთოდის ალგორითმიგ……………………………………………….10

დასკვნა………………………………………………………….14

ლიტერატურა ………………………………………………………………………….15

შესავალი

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

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

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

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

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

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

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

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

2. ზოგადი LP პრობლემებისგან განსხვავებით, ახალი შეზღუდვების დამატება, განსაკუთრებით მთელი რიცხვების ცვლადებთან დაკავშირებული, ჩვეულებრივ ამცირებს CPU პრობლემების გადაჭრის დროს.

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

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

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

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

2. ფილიალი და შეკრული მეთოდი

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

f(X) -> max,

Х€D,

სადაც D არის სასრული სიმრავლე.

პირველი, ჩვენ ვპოულობთ f(X) ფუნქციის £(D) (საზღვარი) შეფასებას, X е D: f(X) ≤ £(D) V X е D-სთვის. თუ ამოცანის X°-ის ზოგიერთი გეგმისთვის ტოლობაა. f(X0) = £(D ), შემდეგ X° = X* არის პრობლემის გადაწყვეტა. თუ მითითებული პირობა არ არის დაკმაყოფილებული, მაშინ შესაძლებელია D სიმრავლის დაყოფა (განშტოება) განცალკევებული ქვესიმრავლეების სასრულ რაოდენობად D1i: ỤD1i. = D, ∩D1i = Ө, და შეფასების გაანგარიშება £(D1i) (საზღვრები), 1≤i≤m (სურათი 2.1)

სურათი 2. 1

თუ რომელიმე გეგმისთვის X1i е Di1, 1 ≤ / ≤ m პირობა f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m დაკმაყოფილებულია, მაშინ Xk1=X* არის ოპტიმალური გეგმა (გამოსავალი). პრობლემა (7.9) -(7.10).

თუ ასეთი გეგმა არ არსებობს, მაშინ არჩეულია Dkl ქვესიმრავლე უმაღლესი შეფასებით £(D1i) და იყოფა სასრული რაოდენობის დისჯუნტულ ქვესიმრავლეებად D2kj: UD2kj=D1k, ∩D2kj=Ө. თითოეული ქვეჯგუფისთვის ნაპოვნია შეფასება £(D2kj), 1≤j≤n (სურათი 2.2)

სურათი 2.2

თუ ამ შემთხვევაში არსებობს გეგმა X2j е D2kJ, 1 ≤j ≤n, ისეთი, რომ f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n, მაშინ X2r= X* არის გამოსავალი პრობლემა. თუ ასეთი გეგმა არ არსებობს, მაშინ განშტოების პროცედურა ტარდება D2kj სიმრავლისთვის ყველაზე მაღალი შეფასებით £(D2kj) , 1≤j≤n. განშტოების მეთოდი განისაზღვრება სპეციფიკით კონკრეტული დავალება.

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

მაგალითი.

5 მ3 მოცულობის კონტეინერი მოთავსებულია 12 ტონა ტევადობის საკონტეინერო გემზე. ტვირთის ერთეულის მასა mj (ტონებში), ტვირთის ერთეულის მოცულობა Vj (მ3-ში), ღირებულება Cj (ჩვეულებრივ ფულად ერთეულებში) მოცემულია ცხრილში 2.1.

ცხრილი 2.1

ტვირთის ტიპი			C j

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

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

Z(X) = 10x1+12x2→max,

3x1+x2≤12,

x1+2x2≤5

x1≥0

x2≥0

x1, x2 არის მთელი რიცხვები

სადაც x1, x2 არის პირველი და მეორე დატვირთვის ერთეულების რაოდენობა, შესაბამისად.

ჩვენ აღვნიშნავთ ამ პრობლემის გეგმების ერთობლიობას D-ით - ეს არის OABC პოლიედრონის მთელი რიცხვების სიმრავლე (სურათი 2.3).

სურათი 2.3

პირველ რიგში, ჩვენ ვხსნით პრობლემას მთელი რიცხვის პირობის გარეშე და ვიღებთ D სიმრავლის შეფასებას - Z(X) ფუნქციის მნიშვნელობა X° = (19/5, 3/5) ოპტიმალურ გეგმაზე.

წერტილი X არ არის პრობლემის ოპტიმალური გეგმა. მაშასადამე, განშტოებისა და შეკრული მეთოდის შესაბამისად, საჭიროა D სიმრავლის დაყოფა განცალკევებულ ქვეჯგუფებად. ავირჩიოთ პირველი არამთლიანი ცვლადი x1=19/5=34/5 და გავყოთ D სიმრავლე ორ განცალკევებულ ქვეჯგუფად D11 და D22. ხაზები x1=3 (L3) და x4= (L3) არის დანაყოფის ხაზები.

სურათი 2.4

L\

მოდით ვიპოვოთ შეფასებები £(D11) და £(D12), რისთვისაც ჩვენ ვხსნით ხაზოვანი პროგრამირების ამოცანებს.

Z(X)=10x1+12x2→max,

3x1+x2≤12

x1+2x2≤5

x1≤3

x1≥0, x2 – მთელი რიცხვები

Z(X)=10x1+12x2→max,

3x1+ x2≤12

x1+2x2≤5

x1≥4

x1≥0, x2 – მთელი რიცხვები

მაგალითად, გრაფიკული მეთოდის გამოყენებით:

X11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); £(D12)=40.

განშტოების შედეგი ნაჩვენებია სურათზე 2.5

სურათი 2.5

გეგმა X01 აკმაყოფილებს პრობლემის პირობებს და ამისთვის დაკმაყოფილებულია შემდეგი პირობა: Z(X11)= £(D11)=42 > £(/)/) = 42 > £(D12) = 40. ამიტომ გეგმა X °1= (3, 1) არის პრობლემის გადაწყვეტა (7.11)-(7.13), ანუ თქვენ უნდა აიღოთ პირველი დატვირთვის სამი ერთეული და მეორე დატვირთვის ერთი ერთეული.

2.1 ფილიალისა და შეკრული ალგორითმი

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

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

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

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

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

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

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

თუ ვივარაუდებთ, რომ ნაპოვნი ოპტიმალური გეგმა X0 არ აკმაყოფილებს მთელი რიცხვების ცვლადების პირობას, ამით ვივარაუდებთ, რომ მის კომპონენტებს შორის არის წილადი რიცხვები. მოდით, მაგალითად, ცვლადმა მიიღოს წილადი მნიშვნელობა X0-ის მიხედვით. მაშინ ოპტიმალურ მთელ გეგმაში მისი მნიშვნელობა იქნება შესაბამისად მაინცან ნაკლები ან ტოლი უახლოეს პატარა მთელ რიცხვზე, ან მეტი ან ტოლი უახლოეს უფრო დიდ რიცხვზე font-size:14.0pt">font-size:14.0pt">მოდით, ვიპოვოთ გამოსავალი წრფივი პროგრამირების ამოცანების (5) და ( 6). ცხადია, აქ შესაძლებელია შემდეგი ოთხი შემთხვევიდან ერთი:

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

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

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

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

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

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

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

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

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

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

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

3. იპოვნეთ ამოცანები (5) და (6), რომლებიც მიღებულია (1)-(3) ამოცანებიდან დამატებითი შეზღუდვების დამატების შედეგად.

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

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

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

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

როგორც განშტოების და შეკრული მეთოდის მაგალითი, განიხილეთ ფუნქცია z=4x1+x2+1®max შეზღუდვებში:

font-size:14.0pt">მოდით X0 = (0; 0), z0 = 1 - "ოპტიმალური" გადაწყვეტა. დავასრულოთ 1 ეტაპი ზოგადი ალგორითმიდა იპოვნეთ მარტივი მეთოდის გამოყენებით და შემდეგ ორმაგი სიმპლექსის მეთოდი(იხ. დანართი 1) X1, შეზღუდვებზე დაყრდნობით ასე რომ, X1 = (3; 0.5; 0; 1; 0; 2.5), z1 = 13.5. ვინაიდან z1 არის წილადი, გეგმა X0 რჩება „ოპტიმალური“,

ჩვენი გეგმის მე-2 პუნქტის მიხედვით, ჩვენ შევქმნით შეზღუდვების 2 ახალ სისტემას:

https://pandia.ru/text/79/453/images/image012_25.gif" alt="აღწერა: http://*****/images/paper/93/79/4327993.png" width="108" height="98"> . !}

განვახორციელოთ ალგორითმის მე-3 პუნქტი. დასაწყისისთვის, მოდით გადავჭრათ პრობლემა გამოყენებით მაგიდის პროცესორი Microsoft Excel (დანართი 2) და მივიღებთ X2 = (2; 1) z2= 10. ვინაიდან z2 ≥ z0, გეგმა X0 ხდება „ოპტიმალური“.

მოვაგვაროთ პრობლემა. ბოლო განტოლებიდან აშკარაა, რომ x2 = 0. აქედან გამომდინარეობს, რომ x1 = 3 (მაქსიმალური შესაძლო). შემდეგ X3 = (3; 0), z3 = 13 და, შესაბამისად, ეს გეგმა ოპტიმალურია (ახლა ბრჭყალების გარეშე).

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

დასკვნა

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

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

ლიტერატურა

1. ა შრაივერი. წრფივი და მთელი რიცხვითი პროგრამირების თეორია: 2 ტომად.; თარგმანი ინგლისურიდან. 1991 წ 360-იანი წლები.

2. თ.ჰუ. მთელი რიცხვების პროგრამირება და ნაკადები ქსელებში.; თარგმანი ინგლისურიდან. 1974 წ

3. , . უმაღლესი მათემატიკა: მათემატიკური პროგრამირება. The Apprentice - მე-2 გამოცემა. 2001 წ 351 წ.

4. . მათემატიკური პროგრამირება: სახელმძღვანელო- მე-5 გამოცემა, სტერეოტიპი-M: FISMAT, 2001 - 264 გვ.

5. , .: ეკონომიკურ-მათემატიკური მეთოდები და გამოყენებითი მოდელები: სახელმძღვანელო. სახელმძღვანელო უნივერსიტეტებისთვის/UNITI, 1999 - 391 გვ.

6. , ; რედაქტირებულია პროფ. . : ოპერაციების კვლევა ეკონომიკაში; სახელმძღვანელო სახელმძღვანელო უნივერსიტეტებისთვის.

დანართი 2

ამოცანის ამოხსნა z = 4x1 + x2 +1 ® max შეზღუდვების მიხედვით:

მაგიდის პროცესორის გამოყენებით Microsoft Excel.

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

იპოვეთ -უცნობების ვექტორი, D- სასრული

ბევრი მისაღები ღირებულებებიამ ვექტორის F(x) არის მოცემული ობიექტური ფუნქცია.

მეთოდის იდეაა D დაყოფა Di disjoint ქვეჯგუფებად (ამ პროცედურას ეწოდება განშტოება) და გამოვთვალოთ ობიექტური ფუნქციის ზედა და ქვედა საზღვრები თითოეულ ქვეჯგუფზე. ქვედა ზღვარს აღვნიშნავთ H-ით, ხოლო ზედა ზღვარს E-ით. შესაბამისად, Hi Eo, მაშინ ეს ქვესიმრავლე არ შეიცავს ოპტიმალურ წერტილს და შეიძლება გამოირიცხოს შემდგომი განხილვისგან. თუ ზედა ზღვარი არის Ei H, შეცვალეთ H min Hi-ით. თუ E=H, მაშინ პრობლემა მოგვარებულია, წინააღმდეგ შემთხვევაში აუცილებელია განშტოების პროცედურის გაგრძელება და ზედა და ქვედა საზღვრების გამოთვლა. ამ შემთხვევაში, ყველა ან მხოლოდ ზოგიერთი ქვესიმრავლე შეიძლება დაიყოს შემდეგ ეტაპზე, სანამ არ მიიღწევა ზედა და ქვედა საზღვრების თანასწორობა და არა ცალკეულ ქვეჯგუფზე, არამედ მოქმედი ტერიტორიაზოგადად.

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

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

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

ბრინჯი. 5.1.

ახლა Di-ს ქვესიმრავლეები არის ტრაექტორიების სიმრავლეები, რომელთაგან თითოეული გადის შესაბამის i-ე წერტილში.

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

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

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

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

განშტოებისა და შეკრული მეთოდი პირველად შემოგვთავაზეს 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 არის ოპტიმალური გეგმა.

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

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

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

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

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

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

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

მაგალითი.

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

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

.

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

,

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

ელემენტების შეჯამებით და ვიღებთ შემცირების მუდმივას:

.

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

.

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

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

– ქვეჯგუფი, რომელიც შეიცავს რკალს;

– ქვეჯგუფი, რომელიც არ შეიცავს რკალს

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