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

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

გამოქვეყნებულია http://www.allbest.ru/

1 . მეთოდის აღწერატოტები და საზღვრები

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

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

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

1 . 1 განშტოების წესები

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

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

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

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

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

განშტოება ხორციელდება იმ შემთხვევაში, თუ ოპტიმალურ გადაწყვეტაში პრობლემის თავდაპირველ ფორმულირებაში მინიმუმ ერთი მთელი ცვლადის მნიშვნელობა არ არის მთელი. ამ ცვლადებს შორის არჩეულია ერთი, მაგალითად j - i. ავღნიშნოთ მისი მნიშვნელობა ნაპოვნი ოპტიმალური ამონახსნით x 0 [j]. ისინი ამბობენ, რომ განშტოება ხორციელდება x[j] ცვლადით. რეგიონი D i "დაყოფილია ორ ქვერეგიონად D i1" და D i2" შემდეგნაირად:

სადაც ] არის x 0 [j] მნიშვნელობის მთელი რიცხვი

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

გამოქვეყნებულია http://www.allbest.ru/

ბრინჯი. 2. განშტოების გეომეტრიული ინტერპრეტაცია

ჩანს, რომ ამ შემთხვევაში ახლად შემოღებული შეზღუდვების სიბრტყეებს შორის ნაწილი ამოღებულია D i დომენიდან. ვინაიდან ცვლადი x[j] საწყისი ამოცანის დასაშვები ამონახსნების დომენის პირობების მიხედვით არის მთელი რიცხვი. , მაშინ თავდაპირველი პრობლემის დასაშვები გადაწყვეტილებებიდან D i (D i D i ") ასეთი გამონაკლისის გარდა, არანაირი გადაწყვეტილება არ არის გამორიცხული.

1 . 2 ობიექტური ფუნქციის ქვედა და ზედა შეფასებების ფორმირება

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

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

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

ობიექტური ფუნქციის f(x) ქვედა შეფასება D i (ან D i ") სიმრავლეზე იქნება რაოდენობა:

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

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

ქვედა საზღვრების გამოთვლის ერთ-ერთი უნივერსალური გზაა შემდეგი პრობლემის გადაჭრა:

ამ გზით განსაზღვრული O i არის f(x)-ის დაბალი შეფასება D i (ან D i "-ზე, რადგან D i D i ".

თუ (4) ამოცანის ამოხსნისას დადგინდა, რომ, მაშინ განზოგადებისთვის ვივარაუდებთ, რომ.

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

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

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

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

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

ალგორითმის ძირითადი წესები შეიძლება ჩამოყალიბდეს შემდეგნაირად:

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

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

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

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

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

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

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

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

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

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

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

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

ამ წყვილი პრობლემის გადაჭრისას არსებობს ოთხი შესაძლო შემთხვევა:

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

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

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

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

ამრიგად, პრობლემის გადაჭრისას ვიღებთ შემდეგ დიაგრამას:

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

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

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

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

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

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

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

პირველ პრობლემას აქვს ოპტიმალური გეგმა

მეორე გადაუჭრელია.

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

პრობლემა 1.1

პრობლემა 1.2

პრობლემა 1.2 გადაუჭრელია, ხოლო პრობლემა No1.1 აქვს ოპტიმალური გეგმა, რომელზეც წერია ობიექტური ფუნქციის მნიშვნელობა.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

მოგზაური გამყიდველის ყველა რაუნდის G ნაკრები ასოცირდება რიცხვთან j(G) და M 1 მატრიცასთან.

მეორე ნაბიჯი. მოდით ავირჩიოთ უმძიმესი ნული მატრიცაში M 1; დადგეს გალიაში; ჩვენ ვაფიქსირებთ გრაფის კიდეს და ვყოფთ G სიმრავლეს ორ ნაწილად: ნაწილი, რომელიც შედგება ტრავერსებისგან, რომლებიც გადის კიდეზე, და ნაწილი, რომელიც შედგება ტრავერსიებისგან, რომლებიც არ გადიან ზღვარზე.

შემდეგი მატრიცა M 1,1 დავაკავშიროთ სიმრავლესთან: M 1 მატრიცაში უჯრედში რიცხვს ვცვლით Ґ-ით. შემდეგ მიღებულ მატრიცაში ჩვენ გადავკვეთთ რიგის ნომერი i და სვეტის ნომერი j, ხოლო დარჩენილი სტრიქონები და სვეტები თავდაპირველი ნომრებით ვინახავთ. და ბოლოს, მოდით შევამციროთ ეს ბოლო მატრიცა და გავიხსენოთ შემცირების მუდმივების ჯამი. შედეგად შემცირებული მატრიცა იქნება მატრიცა M 1,1; ჩვენ ვამატებთ შემცირების მუდმივთა ჯამს, რომელიც ახლახან გვახსოვდა j(G)-ს და შედეგი, რომელიც შემდგომ აღინიშნება j(-ით), შედარებულია სიმრავლესთან.

ახლა ჩვენ ასევე ვუკავშირებთ გარკვეულ მატრიცას M 1,2 სიმრავლეს. ამისათვის მატრიცა M 1-ში ვცვლით უჯრედის რიცხვს Ґ-ით და წარმოგიდგენთ მიღებულ მატრიცას. გავიხსენოთ შემცირების მუდმივების ჯამი და ავღნიშნოთ მიღებული მატრიცა M 1,2-ით. მოდით დავუმატოთ შემცირების მუდმივთა დამახსოვრებული ჯამი j(G) რიცხვს და მიღებული რიცხვი, რომელიც შემდგომ აღინიშნება j(-ით), შედარებულია სიმრავლესთან.

ახლა ავირჩიოთ სიმრავლეს შორის ის, რომელზედაც j ფუნქცია მინიმალურია (ანუ სიმრავლე, რომელიც შეესაბამება j() და j() რიცხვებს შორის მცირეს).

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

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

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

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

ამის შემდეგ ჩანაწერი უმჯობესდება საბოლოო პასუხის მიღებამდე.

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

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

2.3 ამოცანის მათემატიკური მოდელი

პრობლემის გადასაჭრელად მარშრუტის თითოეულ წერტილს მივანიჭებთ კონკრეტულ ნომერს: მე-12 კორპუსი - 1, თეთრი სახლი - 2, KRK "პრემიერი" - 3, ადმინისტრაცია - 4 და მე-5 კორპუსი - 5. შესაბამისად, საერთო რაოდენობა ქულები. შემდეგი, ჩვენ შემოგთავაზებთ ალტერნატიულ ცვლადებს, რომლებიც იღებენ მნიშვნელობას 0, თუ i-ე წერტილიდან j-th-ზე გადასვლა არ შედის მარშრუტში და 1 სხვაგვარად. თითოეულ წერტილში მისვლის და თითოეული წერტილიდან გასვლის პირობები გამოიხატება მხოლოდ ერთხელ ტოლობებით (8) და (9).

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

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

ჩვენს შემთხვევაში, ეს პირობები დაიწერება შემდეგი ფორმით:

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

1) D კომპლექტის ანალიზი.

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

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

ავირჩიოთ საწყისი გეგმა: . მაშინ ზედა ზღვარი არის:

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

2) D 12 ქვეჯგუფის ანალიზი.

3) D 13 ქვეჯგუფის ანალიზი.

4) D 14 ქვეჯგუფის ანალიზი.

5) D 15 ქვეჯგუფის ანალიზი.

6) არაპერსპექტიული ქვეჯგუფების სკრინინგი.

D 13 და D 15 ქვეჯგუფები არაპერსპექტიულია. იმიტომ რომ , მაგრამ შემდეგ განვიხილავთ D 14 ქვეჯგუფს.

7) D 142 ქვეჯგუფის ანალიზი.

8) D 143 ქვეჯგუფის ანალიზი.

9) D 145 ქვეჯგუფის ანალიზი.

10) არაპერსპექტიული ქვეჯგუფების სკრინინგი

D 143 ქვეჯგუფი არაპერსპექტიულია. იმიტომ რომ , მაგრამ შემდეგ განვიხილავთ D 145 ქვეჯგუფს.

11) D 1452 ქვეჯგუფის ანალიზი.

ფილიალის საზღვრის სამიზნე ალგორითმი

12) D 1453 ქვეჯგუფის ანალიზი.

ოპტიმალური გადაწყვეტა:.

ამრიგად, სტუდენტის მარშრუტი: მე-12 კორპუსი - ადმინისტრაცია - მე-5 კორპუსი - თეთრი სახლი - KRK Premier - მე-12 კორპუსი.

გამოქვეყნებულია http://www.allbest.ru/

მეორადი სიალიტერატურა

1. აბრამოვი ლ.ა., კაპუსტინი ვ.ფ. მათემატიკური პროგრამირება. - ლ.: ლენინგრადის სახელმწიფო უნივერსიტეტის გამომცემლობა, 1981. -328გვ.

2. ალექსეევი ო.გ. დისკრეტული ოპტიმიზაციის მეთოდების ინტეგრირებული გამოყენება. - მ.: ნაუკა, 1987. -294გვ.

3. Korbut A.A., Finkelgein Yu.Yu. დისკრეტული პროგრამირება. მ.: მეცნიერება. 1969. -240 წ

4. კუზნეცოვი იუ.ნ. და სხვა მათემატიკური პროგრამირება: სახელმძღვანელო. - მე-2 გამოცემა, შესწორებული და დამატებული. - მ.: უმაღლესი სკოლა, 1980. -300გვ.

5. Papadimitriou H., Steiglitz K. კომბინატორიული ოპტიმიზაცია. ალგორითმები და სირთულე. - M.: Mir, 1985. -213გვ.

გამოქვეყნებულია Allbest.ru-ზე

...

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

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

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


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

კურსის სამუშაო, დამატებულია 10/01/2009


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

კურსის სამუშაო, დამატებულია 03/05/2012


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

ნაშრომი, დამატებულია 02/07/2013


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

კურსის სამუშაო, დამატებულია 20/07/2012


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

კურსის სამუშაო, დამატებულია 08/08/2013


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

კურსის სამუშაო, დამატებულია 21/05/2015


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

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


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

კურსის სამუშაო, დამატებულია 01/18/2011


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

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

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

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

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

დაე, სახელმწიფო მოიძიონ ბ*,რომელშიც R(b *)მინიმალური. მოდით ვივარაუდოთ, რომ ზოგიერთი მიმდინარე გამოსავალი ცნობილია ბ xამჟამინდელი ჩანაწერით R(b x). მაშინ ცხადია, რომ ნებისმიერი სახელმწიფო ბ ი, რომელშიც საუკეთესო მიღწევადი ღირებულებაა R(b i) ³ R(b x), შეიძლება წაიშალოს (საძიებო ხის შესაბამისი ნაწილი მონიშნულია, როგორც ნაჩვენებია ნახატზე 3.9-ზე დაჩრდილული უბნით).

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

ჩვენ გვჯერა ij ³ 0-ითდა ერთად ii = ¥და ეს არ არის აუცილებელი ij-ით = ჯისთან. ჩვენ დავაშიფრავთ პრობლემას ხარჯების მატრიცით C = [с ij ], რომელიც ნაჩვენებია ნახ. 3.10, ბ.

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

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

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

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

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

მატრიციდან ნახ. 3.11, b ადვილია იმის დადგენა, რომ მინიმალური შესაძლო მნიშვნელობა *თან ერთად(რომელსაც ჩვენ აღვნიშნავთ) გამოითვლება შემდეგნაირად

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

მოდით ვივარაუდოთ, რომ რკალი ეკუთვნის C*;ალტერნატიული ვარაუდი ნიშნავს იმას, რომ. თუ რკალი არის , მაშინ ვივარაუდებთ რკალს 4.3 = ¥-ით და ასევე ამოვიღებთ მას ნახ. 2.11, b მწკრივი 3 და სვეტი 4, რომელიც საბოლოოდ იძლევა ნახ. 2.12, ა. მოცემული მატრიცა ნაჩვენებია ნახ. 2.12, ბ.

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

ამავდროულად, ციკლის სიგრძეა 5+2+3+2=12, შესაბამისად, ვასკვნით, რომ რკალი არ შედის ოპტიმალურ ციკლში. ჩვენ გვჯერა 3.4 = ¥-ით. ახლა ვივარაუდოთ, რომ რკალი. მსგავსი გამოთვლების განხორციელების შემდეგ, ჩვენ დავადგინეთ, რომ მინიმალური ჯამური ღირებულება ციკლისთვის, რომელიც შეიცავს რკალს, არის 13 ერთეული. შესაბამისად, ეს ვარაუდიც უარყოფილია, რადგან ეს არ აუმჯობესებს მიმდინარე რეკორდს. ჩვენ გვჯერა 1.4 = ¥-ით. შედეგად, მატრიცის მე-4 სვეტში ნახ. 3.10, b დარჩება მხოლოდ ერთი მოქმედი ელემენტი 2.4 = 2-ით. ჩვენ გვჯერა. ეს დაშვება საშუალებას გვაძლევს წავშალოთ რიგი 2 და სვეტი 4. შედეგად, ვიღებთ შემცირებულ მატრიცას, რომელიც ნაჩვენებია ნახ. 3.13, რისთვისაც C*უდრის 12-ს. დავუშვათ, რომ რკალი მაშინ ავტომატურად გამოდის, რომ რკალი არის . მოდით ამოვიღოთ რიგი 4 და სვეტი 3: ვიღებთ შემცირებულ მატრიცას, რომელიც ნაჩვენებია ნახ. 3.14, საიდანაც ავტომატურად გამომდინარეობს, რომ რკალი . ამრიგად, საწყისი დაშვებიდან გამომდინარე, რომ რკალი, ჩვენ ვადგენთ შემდეგ ოპტიმალურ ციკლს, რომელიც არ შეიცავს რკალს: ჯამური ხარჯებით ტოლია 2 + 3 + 2 + 5 = 12.

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

ან
, ან

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ზე
.

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

მთელი რიცხვის ოპტიმალური ამონახსნის საპოვნელად ვყოფთ ცვლადის ცვალებადობის ინტერვალს x 1 ორ ზონად, კერძოდ x 1  და x 1 = 10 და გაყავით მოცემული დავალება ორ ახალ დავალებად.

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

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

ზე
.

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