დიფერენციალური ქირის მეთოდის აღწერა. დამატებითი შეზღუდვები ტრანსპორტის პრობლემასთან დაკავშირებით. კვლევის ობიექტს წარმოადგენს ხაზოვანი პროგრამირების ამოცანები, ხოლო საგანი სატრანსპორტო ამოცანები
მეთოდი დიფერენციალური ანუიტეტები
პოტენციური მეთოდისგან განსხვავებით, რომლისთვისაც საცნობარო გეგმა, შემდეგ კი მუდმივად იხვეწებოდა პრობლემის გადაჭრისას დიფერენციალური ქირის მეთოდით დაუყოვნებლივ საუკეთესო გზაპროდუქციის ნაწილის განაწილება მომხმარებლებში და შემდგომ გამეორებებში თანდათანობით შეამცირებს გაუნაწილებელი მარაგების მთლიან რაოდენობას.
სატრანსპორტო პრობლემის გადაწყვეტის დასადგენად დიფერენციალური ქირის მეთოდით, გამოიყენება შემდეგი ალგორითმი:
1. თითოეულ სვეტში განსაზღვრეთ მინიმალური ტარიფი და მონიშნეთ შესაბამისი უჯრედი.
2. არჩეული უჯრედები ივსება მაქსიმალური შესაძლო რიცხვებით.
3. რადგან ვ ზოგადი შემთხვევაეს განაწილება არ აკმაყოფილებს ყველა მომხმარებელს, რათა შემცირდეს დაუკმაყოფილებელი მოთხოვნილებების რაოდენობა შემდგომი ნაბიჯებით, აუცილებელია მომწოდებლების შეფასება.
განმარტება 6. რიგები, რომლებიც შეესაბამება მომწოდებლებს, რომელთა მარაგი ამოწურულია და რომელთა გამოყოფილი მომხმარებლების მოთხოვნილებები არ არის დაკმაყოფილებული, უარყოფითია.
განმარტება 7.რიგები, რომლებიც შეესაბამება მომწოდებლებს, რომელთა მარაგები მთლიანად არ არის ამოწურული, დადებითია.
განმარტება 8.რიგები, რომლებიც შეესაბამება მომწოდებლებს, რომელთა მარაგი ამოწურულია და რომელთა გამოყოფილი მომხმარებლების მოთხოვნილებები დაკმაყოფილებულია, ფასდება ნულოვანი. უფრო მეტიც, თუ მეორე შევსებული უჯრედი, რომელიც დგას ამ მწკრივთან დაკავშირებულ სვეტში სხვა შევსებული უჯრედის მიერ, მდებარეობს დადებით რიგში, ნულოვანი ქულის მქონე ეს მწკრივი ითვლება დადებითად. წინააღმდეგ შემთხვევაში - უარყოფითი.
4. ყოველი სვეტისთვის, რომელსაც აქვს მონიშნული ტარიფი უარყოფით მწკრივში, იპოვეთ განსხვავება მონიშნულ ტარიფსა და დადებით მწკრივში უახლოეს ტარიფს შორის.
5. მიღებულ განსხვავებებს შორის განისაზღვრება მინიმალური. ამ რიცხვს შუალედური ანუიტეტი ეწოდება.
6. აშენებენ ახალი მაგიდა, ხოლო დადებით ხაზებში ტარიფები გადაიწერება ცვლილებების გარეშე, ხოლო ნეგატიურ ხაზებში ტარიფები იზრდება შუალედური ქირის ოდენობით.
7. გადადით საფეხურზე 1.
კომენტარი:ა) თუ მწკრივში ან სვეტში არის ერთზე მეტი არჩეული უჯრედი, მაშინ შეავსეთ, უპირველეს ყოვლისა, ის შერჩეული უჯრედები, რომლებიც ერთადერთია სვეტში ან მწკრივში;
ბ) თუ შესაძლებელია ყველა მარაგის განაწილება, მაშინ იღებენ ოპტიმალური გეგმასატრანსპორტო დავალება.
დამატებითი შეზღუდვებიტრანსპორტის პრობლემა
აკრძალული მარშრუტები.
თუ რაიმე მიზეზით შეუძლებელია პროდუქციის მიტანა A i წერტილიდან B j წერტილამდე, აიღეთ ტარიფი ამ მარშრუტისათვის თვითნებურად დიდი M ღირებულებით, ij = M-ით და გადაწყვიტეთ პრობლემა ჩვეულებრივი გზით.
სავალდებულო მიწოდება.
ა) თუ საჭიროა d ij პროდუქტის გარკვეული რაოდენობის ტრანსპორტირება A i წერტილიდან B j წერტილამდე, შესაბამისი უჯრა დაუყოვნებლივ ივსება d ij რიცხვით და შემდეგ პრობლემა წყდება, შევსებული უჯრედის თავისუფალი თვლით, მაგრამ ტარიფით, ij = M-ით, ტოლია Very დიდი რიცხვი, ხოლო მარაგები და საჭიროებები მცირდება დ ij ოდენობით.
ბ) თუ საჭიროა A i წერტილიდან B j წერტილამდე ტრანსპორტირება არანაკლებ გარკვეული თანხაპროდუქტები d ij , შემდეგ გაითვალისწინეთ რეზერვები და საჭიროებები უნდა იყოს ნაკლები d ij ოდენობით, ეს რაოდენობა d ij ითვლება ტრანსპორტირებულად A i B j მარშრუტით და შემდეგ გადაჭრით პრობლემა ჩვეულებრივი გზით.
გ) თუ საჭიროა A i წერტილიდან B j პუნქტამდე ტრანსპორტირება არაუმეტეს გარკვეული რაოდენობის პროდუქტის d ij, შემოღებულია დამატებითი დანიშნულება (-d ij) ტოლი საჭიროებით, B j წერტილის საჭიროებაა. გაუტოლდა d ij. დამატებით დანიშნულების ადგილზე ტრანსპორტირების ტარიფები უდრის B j პუნქტის ტარიფებს, გარდა i-ე ხაზისა, რომელშიც ტარიფი უდრის M-ის თვითნებურად დიდ რაოდენობას. ისინი წყვეტენ პრობლემას ჩვეული გზით და პასუხის დაწერისას ისინი აერთიანებენ ძირითად და დამატებით მომხმარებლებს (დაამატეთ სვეტების შინაარსი).
თუ პოტენციური მეთოდის გამოყენებით სატრანსპორტო პრობლემის ოპტიმალური გეგმის განსაზღვრისას ჯერ მოიძებნა რაიმე ძირითადი გეგმა, შემდეგ კი ის მუდმივად იხვეწებოდა, მაშინ დიფერენციალური ქირის მეთოდით სატრანსპორტო პრობლემის გადაწყვეტის პოვნისას, ტვირთის ნაწილი. პირველად ნაწილდება დანიშნულების ადგილებს შორის საუკეთესოდ (ე.წ. პირობითი ოპტიმალური განაწილება) და შემდგომ გამეორებებში თანდათან შეამცირეთ გამოუყენებელი მარაგების მთლიანი რაოდენობა. საწყისი დატვირთვის განაწილების ვარიანტი განისაზღვრება შემდეგნაირად. სატრანსპორტო დავალების მონაცემთა ცხრილის თითოეულ სვეტში არის მინიმალური ტარიფი. ნაპოვნი ნომრები ჩასმულია წრეებში და ივსება მითითებული ნომრების შემცველი უჯრები. მათში იწერება მაქსიმალური შესაძლო რიცხვები. შედეგად, მიიღება ტვირთის მარაგების გარკვეული განაწილება დანიშნულების ადგილებზე. ეს განაწილება ზოგადად არ აკმაყოფილებს თავდაპირველი ტრანსპორტის პრობლემის შეზღუდვებს. ამიტომ, შემდეგი ნაბიჯები უნდა იყოს გამოუყენებელი ტვირთის მარაგების თანდათანობით შემცირება, რათა საერთო ღირებულებამოძრაობა მინიმალური იყო. ამისათვის ჯერ განსაზღვრეთ ზედმეტი და არასაკმარისი რიგები.
არასაკმარისად ითვლება ხაზები, რომლებიც შეესაბამება მომწოდებლებს, რომელთა ინვენტარი სრულად არის გამოყოფილი და რომელთა მოთხოვნა არ არის დაკმაყოფილებული იმ მიმართულებებიდან, რომლებიც დაკავშირებულია ამ მომხმარებლების დაგეგმილ გადაზიდვებთან. ამ ხაზებს ზოგჯერ უარყოფით ხაზებსაც უწოდებენ. ხაზები, რომლებიც არ არის მთლიანად ამოწურული, ითვლება ჭარბად. ზოგჯერ მათ პოზიტიურსაც უწოდებენ.
ჭარბი და არასაკმარისი მწკრივების დადგენის შემდეგ, თითოეული სვეტისთვის აღმოჩენილია განსხვავებები წრეში მოცემულ რიცხვსა და ზედმეტ მწკრივში ჩაწერილ უახლოეს ტარიფს შორის. თუ წრეში რიცხვი დადებით ხაზშია, მაშინ განსხვავება არ არის განსაზღვრული. მიღებულ რიცხვებს შორის იპოვეთ ყველაზე პატარა. ამ რიცხვს შუალედური ანუიტეტი ეწოდება . შუალედური ანუიტეტის განსაზღვრის შემდეგ გადადიან ახალ მაგიდაზე. ეს ცხრილი მიიღება წინა ცხრილიდან, უარყოფითი რიგების შესაბამის ტარიფებზე შუალედური ქირის დამატებით. დარჩენილი ელემენტები იგივე რჩება. ამ შემთხვევაში ახალი ცხრილის ყველა უჯრედი თავისუფლად ითვლება. ახალი ცხრილის აგების შემდეგ იწყება მისი უჯრედების შევსება. ახლა შევსებული უჯრედების რაოდენობა ერთით მეტია, ვიდრე წინა ეტაპზე. ეს დამატებითი უჯრედი არის სვეტში, რომელშიც ჩაიწერა შუალედური ანუიტეტი. ყველა სხვა უჯრედი განლაგებულია თითო სვეტში და შეიცავს უმცირეს რიცხვებს მოცემული სვეტისთვის, წრეებში ჩასმული. წრეებში ჩასმულია ორი იდენტური რიცხვი სვეტში, რომელშიც შუალედური ანუიტეტი იყო ჩაწერილი წინა ცხრილში.
ვინაიდან ახალ ცხრილში შევსებული უჯრედების რაოდენობა სვეტების რაოდენობაზე მეტია, უჯრედების შევსებისას უნდა გამოიყენოთ სპეციალური წესი, რომელიც არის შემდეგი. აირჩიეთ გარკვეული სვეტი (რიგი), რომელშიც არის ერთი უჯრედი, რომელშიც მოთავსებულია წრე. ეს უჯრედი ივსება და გამორიცხულია განხილვისგან. ამ სვეტს(სტრიქონი). ამის შემდეგ აიღეთ გარკვეული მწკრივი (სვეტი), რომელშიც არის ერთი უჯრედი, რომელშიც მოთავსებულია წრე. ეს უჯრედი ივსება და გამორიცხულია განხილვისგან. ეს ხაზი(სვეტი). ასე გაგრძელდება, სასრული რაოდენობის საფეხურების შემდეგ, ივსება ყველა ის უჯრა, რომელშიც მოთავსებულია წრეები თანდართული რიცხვებით. თუ გარდა ამისა, შესაძლებელია გამგზავრების წერტილებში არსებული ყველა ტვირთის გადანაწილება დანიშნულების პუნქტებს შორის, მაშინ მიიღება სატრანსპორტო ამოცანის ოპტიმალური გეგმა. თუ ოპტიმალური გეგმა არ იქნა მიღებული, მაშინ ისინი გადადიან ახალ მაგიდაზე. ამისათვის იპოვეთ ზედმეტი და არასაკმარისი რიგები, შუალედური ქირა და ამის საფუძველზე ააწყვეთ ახალი ცხრილი. ამ შემთხვევაში, შეიძლება წარმოიშვას გარკვეული სირთულეები სტრიქონის ნიშნის განსაზღვრისას, როდესაც ის არ არის გამოყოფილი ნულის ტოლი. ამ შემთხვევაში, მწკრივი ითვლება დადებითად იმ პირობით, რომ მეორე შევსებული უჯრედი, რომელიც მდებარეობს ამ მწკრივთან დაკავშირებულ სვეტში სხვა შევსებული უჯრედის მიერ, მდებარეობს დადებით რიგში.
ზემოთ აღწერილი გამეორებების სასრული რაოდენობის შემდეგ, გაუნაწილებელი ნაშთი ხდება ნული. შედეგად მიიღება მოცემული სატრანსპორტო ამოცანის ოპტიმალური გეგმა.
სატრანსპორტო პრობლემის გადაჭრის ზემოთ აღწერილი მეთოდი უფრო მარტივია ლოგიკური წრეგამოთვლები, ვიდრე ზემოთ განხილული პოტენციური მეთოდი. ამიტომ, უმეტეს შემთხვევაში, კომპიუტერის გამოყენებით კონკრეტული სატრანსპორტო პრობლემების გადაჭრის მიზნით, გამოიყენება დიფერენციალური ქირის მეთოდი.
მაგალითი (4):
სატრანსპორტო პრობლემისთვის, რომლის საწყისი მონაცემები მოცემულია ცხრილში 11, იპოვეთ ოპტიმალური გეგმა დიფერენციალური ქირის მეთოდით.
გამოსავალი. გადავიდეთ ცხრილიდან 11 ცხრილიდან 12-ზე, დავამატოთ ერთი დამატებითი სვეტი, რათა მიუთითოთ ჭარბი და ნაკლოვანება მწკრივის მიხედვით და ერთი მწკრივი შესაბამისი განსხვავებების ჩასაწერად.
ცხრილი 10.
|
გამგზავრების წერტილები |
მიმართულებები | ||||||
|
საჭიროებებს | |||||||
ცხრილი 11.
|
გამგზავრების წერტილები |
მიმართულებები |
ნაკლი ჭარბი ( |
|||||||||
|
| |||||||||||
|
|
|
|
| ||||||||
|
საჭიროებებს | |||||||||||
|
განსხვავება | |||||||||||
მე-12 ცხრილის თითოეულ სვეტში ვპოულობთ მინიმალურ ტარიფებს და შემოხაზავთ მათ. შეავსეთ მითითებული ნომრების შემცველი უჯრები. ამისათვის ჩაწერეთ მაქსიმალური დასაშვები რიცხვი თითოეულ უჯრედში. მაგალითად, სტრიქონისა და სვეტის გადაკვეთაზე მდებარე უჯრაში ვწერთ რიცხვს 120. ამ უჯრაში უფრო დიდი რიცხვის განთავსება შეუძლებელია, რადგან ამ შემთხვევაში დანიშნულების საჭიროება გადააჭარბებს.
ზემოაღნიშნული უჯრების შევსების შედეგად მიიღება ეგრეთ წოდებული პირობითად ოპტიმალური გეგმა, რომლის მიხედვითაც სრულად დაკმაყოფილებულია მიმართულებების მოთხოვნილებები და ნაწილობრივ დანიშნულების მოთხოვნილებები. . ამავდროულად, სრულად გადანაწილდა ამოსავალი წერტილის რეზერვები, ნაწილობრივ - გამავალი წერტილის მარაგი, ხოლო ამოსავალი წერტილის მარაგი მთლიანად გაუნაწილებელი დარჩა.
პირობითად ოპტიმალური გეგმის მიღების შემდეგ ვადგენთ ზედმეტ და არასაკმარის ხაზებს. აქ ხაზი არასაკმარისია , ვინაიდან გამგზავრების წერტილის რეზერვები სრულად არის გამოყენებული და დანიშნულების ადგილის მოთხოვნილებები ნაწილობრივ დაკმაყოფილებულია. დეფიციტის რაოდენობა შეადგენს 80 ერთეულს.
სიმები და ზედმეტია, რადგან წარმოშობის მარაგები და მთლიანად არ არის განაწილებული. ამ შემთხვევაში, ხაზის ჭარბი რაოდენობა უდრის 60 ერთეულს, ხოლო ხაზი უდრის ერთეულს.
თითოეული სვეტისთვის ჭარბი და არასაკმარისი მწკრივების დადგენის შემდეგ ვხვდებით განსხვავებებს ზედმეტ მწკრივებში ჩაწერილ მინიმალურ ტარიფებსა და შევსებულ უჯრედებში არსებულ ტარიფებს შორის. IN ამ შემთხვევაშიეს განსხვავებები შესაბამისად უდრის 5, 4, 2, 1 (ცხრილი 11). განსხვავება სვეტისთვის განუსაზღვრელია, რადგან ამ სვეტში შემოხაზული რიცხვი დადებით მწკრივშია. სვეტში წრეში რიცხვი ტოლია, ხოლო მოცემული სვეტის უჯრებში ზედმეტ მწკრივებში უმცირესი რიცხვია რიცხვი. მაშასადამე, ამ სვეტის სხვაობა უდრის სხვა სვეტებსაც: for; ამისთვის; ამისთვის. .
აღმოჩენილი სხვაობებიდან ვირჩევთ უმცირესს, რაც არის შუალედური ქირა. ამ შემთხვევაში შუალედური ქირა უდრის და არის სვეტში . შუალედური ქირა რომ ვიპოვეთ, გადავდივართ მე-11 ცხრილში.
ამ ცხრილში, სტრიქონებში და (რომლებიც ზედმეტია) გადავწერთ შესაბამის ტარიფებს მე-10 სტრიქონიდან ცხრილიდან. ხაზის ელემენტები (რომელიც არასაკმარისი იყო) მიიღება ხაზების ცხრილში მდებარე შესაბამისი ტარიფების დამატებით. 10, შუალედური ანუიტეტი, ე.ი.
მაგიდაზე 11, შევსებული უჯრედების რაოდენობა გაიზარდა ერთით. ეს გამოწვეულია იმით, რომ ამ ცხრილის თითოეულ სვეტში მინიმალური ტარიფების რაოდენობა გაიზარდა ერთით, კერძოდ, ახლა სვეტს აქვს ორი მინიმალური ელემენტი. ამ ციფრებს წრეებში ვამაგრებთ; უჯრედები, რომელშიც ისინი დგანან, უნდა იყოს შევსებული. ასევე აუცილებელია სხვა სვეტებისთვის ყველაზე დაბალი ტარიფების შემცველი უჯრების შევსება. ეს არის ცხრილის უჯრედები. 11, რომელშიც წრეებშია ჩასმული შესაბამისი ტარიფები.
ცხრილი 11.
|
გამგზავრების წერტილები |
მიმართულებები |
ნაკლი ჭარბი ( |
|||||||||
|
| |||||||||||
|
|
|
|
| ||||||||
|
| |||||||||||
|
საჭიროებებს | |||||||||||
|
განსხვავება | |||||||||||
მითითებული უჯრედების განსაზღვრის შემდეგ, ჩვენ ვადგენთ მათი შევსების თანმიმდევრობას. ამისათვის ჩვენ ვპოულობთ სვეტებს (სტრიქონებს), რომლებშიც მხოლოდ ერთი უჯრედია შევსებული. გარკვეული უჯრედის ამოცნობისა და შევსების შემდეგ, ჩვენ გამოვრიცხავთ შესაბამის სვეტს (რიგს) განხილვისაგან და გადავდივართ შემდეგი უჯრედის შევსებაზე. ამ შემთხვევაში, ჩვენ ვავსებთ უჯრედებს შემდეგი თანმიმდევრობით. ჯერ უჯრედებს ვავსებთ ,,,, ვინაიდან ისინი ერთადერთი უჯრედებია, რომლებიც ავსებენ სვეტებს მითითებული უჯრედების შევსების შემდეგ, შეავსეთ უჯრედი, რადგან ის ერთადერთია, რომელიც ავსებს მწკრივს . ამ უჯრის შევსების შემდეგ (ცხრილი 2.16), ჩვენ გამოვრიცხავთ ხაზს განხილვისგან . შემდეგ სვეტში მხოლოდ ერთი უჯრა რჩება შესავსებად. ეს არის გალია , რომელსაც ჩვენ ვავსებთ. უჯრედების შევსების შემდეგ ვაყენებთ ზედმეტ და არასაკმარის ხაზებს (ცხრილი 11). როგორც მე-11 ცხრილიდან ჩანს, ჯერ კიდევ არის გაუნაწილებელი ნაშთი. შესაბამისად, მიღებულია პრობლემის პირობითად ოპტიმალური გეგმა და უნდა გადავიდეთ ახალ ცხრილში. ამისათვის, თითოეული სვეტისთვის ვპოულობთ განსხვავებას ამ სვეტის წრეში ჩაწერილ რიცხვსა და მის მიმართ უმცირეს რიცხვს შორის, რომელიც მდებარეობს ზედმეტ რიგებში (ცხრილი 11). ამ განსხვავებებს შორის ყველაზე მცირეა. ეს არის შუალედური ქირა. გადავიდეთ ახალ ცხრილზე (ცხრილი 12).
თუ პოტენციური მეთოდის გამოყენებით სატრანსპორტო პრობლემის ოპტიმალური გეგმის დადგენისას ჯერ იქნა ნაპოვნი რაიმე ძირითადი გეგმა, შემდეგ კი ის მუდმივად გაუმჯობესდა, მაშინ დიფერენციალური ქირის მეთოდით სატრანსპორტო პრობლემის გადაწყვეტის პოვნისას, ტვირთის ნაწილი ჯერ საუკეთესოდ ნაწილდება დანიშნულების ადგილებს შორის (ე.წ პირობითად ოპტიმალური განაწილება) და შემდგომ გამეორებებში თანდათან შეამცირეთ გამოუყენებელი მარაგების მთლიანი რაოდენობა. საწყისი დატვირთვის განაწილების ვარიანტი განისაზღვრება შემდეგნაირად. სატრანსპორტო დავალების მონაცემთა ცხრილის თითოეულ სვეტში არის მინიმალური ტარიფი. ნაპოვნი ნომრები ჩასმულია წრეებში და ივსება მითითებული ნომრების შემცველი უჯრები. მათში იწერება მაქსიმალური შესაძლო რიცხვები. შედეგად, მიიღება ტვირთის მარაგების გარკვეული განაწილება დანიშნულების ადგილებზე. ეს განაწილება ზოგადად არ აკმაყოფილებს თავდაპირველი ტრანსპორტის პრობლემის შეზღუდვებს. აქედან გამომდინარე, შემდეგი ნაბიჯები უნდა იყოს ეტაპობრივი შემცირება გაუნაწილებელი ტვირთის მიწოდების ისე, რომ ტრანსპორტირების მთლიანი ღირებულება დარჩეს მინიმალური. ამისათვის ჯერ განსაზღვრეთ ზედმეტი და არასაკმარისი რიგები.
არასაკმარისად ითვლება ხაზები, რომლებიც შეესაბამება მომწოდებლებს, რომელთა ინვენტარი სრულად არის გამოყოფილი და რომელთა მოთხოვნა არ არის დაკმაყოფილებული იმ მიმართულებებიდან, რომლებიც დაკავშირებულია ამ მომხმარებლების დაგეგმილ გადაზიდვებთან. ამ ხაზებს ზოგჯერ უარყოფით ხაზებსაც უწოდებენ. ხაზები, რომლებიც არ არის მთლიანად ამოწურული, ითვლება ჭარბად. ზოგჯერ მათ პოზიტიურსაც უწოდებენ.
ჭარბი და არასაკმარისი მწკრივების დადგენის შემდეგ, თითოეული სვეტისთვის აღმოჩენილია განსხვავებები წრეში მოცემულ რიცხვსა და ზედმეტ მწკრივში ჩაწერილ უახლოეს ტარიფს შორის. თუ წრეში რიცხვი დადებით ხაზშია, მაშინ განსხვავება არ არის განსაზღვრული. მიღებულ რიცხვებს შორის იპოვეთ ყველაზე პატარა. ამ ნომერს ეძახიან შუალედური ქირავდება. შუალედური ანუიტეტის განსაზღვრის შემდეგ გადადიან ახალ მაგიდაზე. ეს ცხრილი მიიღება წინა ცხრილიდან, უარყოფითი რიგების შესაბამის ტარიფებზე შუალედური ქირის დამატებით. დარჩენილი ელემენტები იგივე რჩება. ამ შემთხვევაში ახალი ცხრილის ყველა უჯრედი თავისუფლად ითვლება. ახალი ცხრილის აგების შემდეგ იწყება მისი უჯრედების შევსება. ახლა შევსებული უჯრედების რაოდენობა ერთით მეტია, ვიდრე წინა ეტაპზე. ეს დამატებითი უჯრედი არის სვეტში, რომელშიც ჩაიწერა შუალედური ანუიტეტი. ყველა სხვა უჯრედი განლაგებულია თითო სვეტში და შეიცავს უმცირეს რიცხვებს მოცემული სვეტისთვის, წრეებში ჩასმული. წრეებში ჩასმულია ორი იდენტური რიცხვი სვეტში, რომელშიც შუალედური ანუიტეტი იყო ჩაწერილი წინა ცხრილში.
ვინაიდან ახალ ცხრილში შევსებული უჯრედების რაოდენობა სვეტების რაოდენობაზე მეტია, უჯრედების შევსებისას უნდა გამოიყენოთ სპეციალური წესი, რომელიც არის შემდეგი. აირჩიეთ გარკვეული სვეტი (რიგი), რომელშიც არის ერთი უჯრედი, რომელშიც მოთავსებულია წრე. ეს უჯრედი ივსება და ეს სვეტი (სტრიქონი) გამორიცხულია განხილვისგან. ამის შემდეგ აიღეთ გარკვეული მწკრივი (სვეტი), რომელშიც არის ერთი უჯრედი, რომელშიც მოთავსებულია წრე. ეს უჯრედი ივსება და ეს მწკრივი (სვეტი) გამორიცხულია განხილვისაგან. ასე გაგრძელდება, სასრული რაოდენობის საფეხურების შემდეგ, ივსება ყველა ის უჯრა, რომელშიც მოთავსებულია წრეები თანდართული რიცხვებით. თუ გარდა ამისა, შესაძლებელია გამგზავრების წერტილებში არსებული ყველა ტვირთის გადანაწილება დანიშნულების პუნქტებს შორის, მაშინ მიიღება სატრანსპორტო ამოცანის ოპტიმალური გეგმა. თუ ოპტიმალური გეგმა არ იქნა მიღებული, მაშინ ისინი გადადიან ახალ მაგიდაზე. ამისათვის იპოვეთ ზედმეტი და არასაკმარისი რიგები, შუალედური ქირა და ამის საფუძველზე ააწყვეთ ახალი ცხრილი. ამ შემთხვევაში, შეიძლება წარმოიშვას გარკვეული სირთულეები სტრიქონის ნიშნის განსაზღვრისას, როდესაც მისი გამოუყენებელი ნაშთი ნულის ტოლია. ამ შემთხვევაში, მწკრივი ითვლება დადებითად იმ პირობით, რომ მეორე შევსებული უჯრედი, რომელიც მდებარეობს ამ მწკრივთან დაკავშირებულ სვეტში სხვა შევსებული უჯრედის მიერ, მდებარეობს დადებით რიგში.
ზემოთ აღწერილი გამეორებების სასრული რაოდენობის შემდეგ, გაუნაწილებელი ნაშთი ხდება ნული. შედეგად მიიღება მოცემული სატრანსპორტო ამოცანის ოპტიმალური გეგმა.
ზემოთ აღწერილი სატრანსპორტო პრობლემის გადაჭრის მეთოდს აქვს უფრო მარტივი ლოგიკური გაანგარიშების სქემა, ვიდრე ზემოთ განხილულ პოტენციურ მეთოდს. ამიტომ, უმეტეს შემთხვევაში, კომპიუტერის გამოყენებით კონკრეტული სატრანსპორტო პრობლემების გადაჭრის მიზნით, გამოიყენება დიფერენციალური ქირის მეთოდი.
5.6 სატრანსპორტო პრობლემების ოპტიმალური გეგმის განსაზღვრა, რომლებსაც გარკვეული გართულებები აქვთ მათ ფორმულირებაში.
რიგი სპეციფიკური სატრანსპორტო პრობლემების გადაჭრისას, ხშირად საჭიროა გავითვალისწინოთ დამატებითი შეზღუდვები, რომლებიც არ იყო ზემოთ განხილვისას. მარტივი პარამეტრებიამ ამოცანებს. მოდით უფრო დეტალურად ვისაუბროთ ტრანსპორტის პრობლემების ფორმულირების ზოგიერთ შესაძლო გართულებაზე.
1. ზოგიერთისთვის რეალური პირობებისაქონლის ტრანსპორტირება კონკრეტული გამგზავრების წერტილიდან , თქვენს დანიშნულებამდე , არ შეიძლება განხორციელდეს. ასეთი პრობლემების ოპტიმალური გეგმების დასადგენად, ვარაუდობენ, რომ ტვირთის ერთეულის გადაზიდვის ტარიფი წერტილიდან წერტილამდე , არის თვითნებურად დიდი მ,და ამ პირობებში, ახალი სატრანსპორტო პრობლემის გადაწყვეტა ნაპოვნია ცნობილი მეთოდების გამოყენებით. ამ დაშვებით, ტვირთის გადაზიდვის შესაძლებლობა წერტილიდან წერტილამდე გამორიცხულია სატრანსპორტო ამოცანის ოპტიმალური გეგმის მიხედვით. . ტრანსპორტის პრობლემის გადაჭრის ამ მიდგომას ე.წ ტრანსპორტირების აკრძალვა ან ბლოკირება დავალების მონაცემთა ცხრილის შესაბამისი უჯრედი.
2. ცალკეულ სატრანსპორტო ამოცანებში დამატებით პირობას წარმოადგენს გარკვეული რაოდენობის ტვირთის შესაბამისი მარშრუტების გადაზიდვის უზრუნველყოფა. მოდით, მაგალითად, გამგზავრების ადგილიდან დანიშნულების პუნქტამდე აუცილებელია ტვირთის ერთეულების გადატანა. შემდეგ მითითებული ნომერი იწერება სატრანსპორტო დავალების მონაცემთა ცხრილის უჯრედში, რომელიც მდებარეობს მწკრივისა და სვეტის კვეთაზე და მომავალში ეს უჯრედი განიხილება თავისუფლად თვითნებურად დიდი ტრანსპორტის ტარიფით. მ.ამ გზით მიღებული ახალი სატრანსპორტო ამოცანისთვის მოიძებნება ოპტიმალური გეგმა, რომელიც განსაზღვრავს თავდაპირველი პრობლემის ოპტიმალურ გეგმას.
3. ზოგჯერ საჭიროა სატრანსპორტო პრობლემის გადაწყვეტის მოძიება, რომლის დროსაც ტვირთის მოცემული რაოდენობა მაინც უნდა იყოს მიტანილი გამგზავრების ადგილიდან დანიშნულების ადგილამდე. ასეთი პრობლემის ოპტიმალური გეგმის დასადგენად მიჩნეულია, რომ ნივთის რეზერვები და ნივთის საჭიროებები ერთეულების მიხედვით რეალურზე ნაკლებია. ამის შემდეგ მოიძებნება ახალი სატრანსპორტო პრობლემის ოპტიმალური გეგმა, რომლის საფუძველზეც დგინდება საწყისი პრობლემის გადაწყვეტა.
4. ზოგიერთი სატრანსპორტო პრობლემის დროს აუცილებელია გადაზიდვის ოპტიმალური გეგმის მოძიება იმ პირობით, რომ ტვირთის ერთეულზე მეტი გადაზიდვა მოხდება გამგზავრების ადგილიდან დანიშნულების ადგილამდე, ე.ი.
ჩამოყალიბებული პრობლემა შეიძლება გადაწყდეს შემდეგნაირად. საწყისი ამოცანის მონაცემების ცხრილში, ყოველი მეათე შეზღუდვისთვის (1) მოცემულია დამატებითი სვეტი, ანუ შეყვანილია დამატებითი დანიშნულება. ამ სვეტში იწერება იგივე ტარიფები, რაც სვეტშია, გარდა იმ ტარიფისა, რომელიც მდებარეობს მე-6 რიგში. ამ ხაზის დამატებით სვეტში, ტარიფი განიხილება რაიმე თვითნებურად დიდი რიცხვის ტოლფასად. ამ შემთხვევაში, წერტილის მოთხოვნილებები განიხილება თანაბარი, ხოლო ახლად შემოტანილი დანიშნულების მოთხოვნილებები - თანაბარი. მიღებული სატრანსპორტო პრობლემის გადაწყვეტა შესაძლებელია პოტენციალების მეთოდით და ამით დადგინდება ოპტიმალური გეგმა ან დადგინდება თავდაპირველი პრობლემის გადაუჭრელობა. გაითვალისწინეთ, რომ თავდაპირველი სატრანსპორტო პრობლემა გადაიჭრება მხოლოდ იმ შემთხვევაში, თუ არსებობს მისთვის მინიმუმ ერთი საცნობარო გეგმა.
ზემოაღნიშნული პრობლემის გადაჭრა შესაძლებელია ამ გზით. შეზღუდვის (1) გათვალისწინებით, საცნობარო გეგმა აგებულია მინიმალური ელემენტის წესის გამოყენებით. უფრო მეტიც, თუ მნიშვნელობა ჩაწერილია ეს ნაბიჯირიცხვის შესაბამის უჯრაში განისაზღვრება მხოლოდ შეზღუდვით (1), შემდეგ მხოლოდ შევსებული უჯრედი გამოირიცხება განხილვისაგან. სხვა შემთხვევებში საწყისიმოსაზრებები გამორიცხავს რიგს ან სვეტს (ან ერთს ან მეორეს).
თუ მიწოდების გეგმის შედგენის შედეგად განაწილებულია გამგზავრების პუნქტების ყველა არსებული მარაგი და დაკმაყოფილებულია დანიშნულების წერტილებში საჭიროებები, მაშინ მიიღება სატრანსპორტო ამოცანის ძირითადი გეგმა.
თუ რომელიმე სტრიქონში (და შესაბამისად სვეტში) არის გაუნაწილებელი ნაშთი ტოლი , შემდეგ დაინერგება დამატებითი დანიშნულება და დამატებითი გამგზავრების წერტილი მოთხოვნები და მარაგი ტოლი . დამატებითი დანიშნულების სვეტისა და დამატებითი გასასვლელის მწკრივის გადაკვეთაზე მდებარე უჯრედში ტარიფი ითვლება ნულის ტოლფასად. მოცემული მწკრივისა და სვეტის ყველა სხვა უჯრედში ტარიფები ითვლება რაღაც თვითნებურად დიდი რიცხვის ტოლი მ.შედეგად მიღებული ტრანსპორტის პრობლემა მოგვარებულია პოტენციური მეთოდით. სასრული რაოდენობის საფეხურების შემდეგ ან დგინდება, რომ თავდაპირველ პრობლემას არ აქვს საცნობარო გეგმა, ან მოიძებნება მისი ოპტიმალური გეგმა. სადაც – თავდაპირველი პრობლემის ოპტიმალური გეგმა თუ
დიფერენციალური ქირის მეთოდის ალგორითმი
თუ პოტენციური მეთოდის გამოყენებით ოპტიმალური TK გეგმის განსაზღვრისას, ჯერ იქნა ნაპოვნი საცნობარო გეგმა, შემდეგ კი ის მუდმივად გაუმჯობესდა, მაშინ დიფერენციალური ქირის მეთოდის გამოყენებით TZ გადაწყვეტის პოვნისას, ტვირთის ნაწილი ჯერ ნაწილდება დანიშნულების ადგილებს შორის ( ეგრეთ წოდებული ოპტიმალური განაწილება) და შემდგომ გამეორებებში გამოუყენებელი მარაგების ჯამური რაოდენობა. საწყისი დატვირთვის განაწილების ვარიანტი განისაზღვრება შემდეგნაირად.მონაცემთა ცხრილის თითოეულ სვეტში არის მინიმალური ტარიფი. ნაპოვნი ნომრები ჩასმულია წრეებში და ივსება მითითებული ნომრების შემცველი უჯრები. მათში იწერება მაქსიმალური შესაძლო რიცხვები. შედეგად, მიიღება ტვირთის მარაგების გარკვეული განაწილება დანიშნულების ადგილებზე. ეს განაწილება ზოგადად არ აკმაყოფილებს თავდაპირველი ტრანსპორტის პრობლემის შეზღუდვებს. აქედან გამომდინარე, შემდეგი ნაბიჯები უნდა იყოს ეტაპობრივი შემცირება გაუნაწილებელი ტვირთის მიწოდების ისე, რომ ტრანსპორტირების მთლიანი ღირებულება დარჩეს მინიმალური. ამისათვის ჯერ განსაზღვრეთ ზედმეტი და არასაკმარისი რიგები.
არასაკმარისად ითვლება ხაზები, რომლებიც შეესაბამება მომწოდებლებს, რომელთა ინვენტარი სრულად არის გამოყოფილი და რომელთა მოთხოვნა არ არის დაკმაყოფილებული იმ მიმართულებებიდან, რომლებიც დაკავშირებულია ამ მომხმარებლების დაგეგმილ გადაზიდვებთან. ამ ხაზებს ზოგჯერ უარყოფით ხაზებსაც უწოდებენ. ხაზები, რომლებიც არ არის მთლიანად ამოწურული, ითვლება ჭარბად. ზოგჯერ მათ პოზიტიურსაც უწოდებენ.
ჭარბი და არასაკმარისი რიგების დადგენის შემდეგ, თითოეული სვეტისთვის იპოვება განსხვავება წრეში არსებულ რიცხვსა და ზედმეტ მწკრივში ჩაწერილ უახლოეს ტარიფს შორის. თუ წრეში რიცხვი დადებით ხაზშია, მაშინ განსხვავება არ არის განსაზღვრული. მიღებულ რიცხვებს შორის იპოვეთ ყველაზე პატარა. ამ რიცხვს შუალედური ანუიტეტი ეწოდება. შუალედური ანუიტეტის განსაზღვრის შემდეგ გადადიან ახალ მაგიდაზე. ეს ცხრილი მიიღება წინა ცხრილიდან, უარყოფითი რიგების შესაბამის ტარიფებზე შუალედური ქირის დამატებით. დარჩენილი ელემენტები იგივე რჩება. ამ შემთხვევაში ახალი ცხრილის ყველა უჯრედი თავისუფლად ითვლება. ახალი ცხრილის აგების შემდეგ იწყება მისი უჯრედების შევსება. ახლა შევსებული უჯრედების რაოდენობა ერთით მეტია, ვიდრე წინა ეტაპზე. ეს დამატებითი უჯრედი არის სვეტში, რომელშიც ჩაიწერა შუალედური ანუიტეტი. ყველა სხვა უჯრედი განლაგებულია თითო სვეტში და შეიცავს უმცირეს რიცხვებს მოცემული სვეტისთვის, წრეებში ჩასმული. წრეებში ჩასმულია ორი იდენტური რიცხვი სვეტში, რომელშიც შუალედური ანუიტეტი იყო ჩაწერილი წინა ცხრილში.
ვინაიდან ახალ ცხრილში შევსებული უჯრედების რაოდენობა სვეტების რაოდენობაზე მეტია, უჯრედების შევსებისას უნდა გამოიყენოთ სპეციალური წესი, რომელიც არის შემდეგი. აირჩიეთ გარკვეული სვეტი (რიგი), რომელშიც არის ერთი უჯრედი, რომელშიც მოთავსებულია წრე. ეს უჯრედი ივსება და ეს სვეტი (სტრიქონი) გამორიცხულია განხილვისგან. ამის შემდეგ აიღეთ გარკვეული მწკრივი (სვეტი), რომელშიც არის ერთი უჯრედი, რომელშიც მოთავსებულია წრე. ეს უჯრედი ივსება და ეს მწკრივი (სვეტი) გამორიცხულია განხილვისაგან. ასე გაგრძელდება, სასრული რაოდენობის საფეხურების შემდეგ, ივსება ყველა ის უჯრა, რომელშიც მოთავსებულია წრეები თანდართული რიცხვებით. თუ გარდა ამისა, შესაძლებელია მთელი დატვირთვის განაწილება, მაშინ მიიღება ოპტიმალური გეგმა. თუ ტექნიკური მახასიათებლების ოპტიმალური გეგმა არ არის მიღებული, გადადით ახალ ცხრილში. ამისათვის იპოვეთ ზედმეტი და არასაკმარისი რიგები, შუალედური ქირავდება და ააგეთ ახალი ცხრილი. ამ შემთხვევაში, შეიძლება წარმოიშვას გარკვეული სირთულეები სტრიქონის ნიშნის განსაზღვრისას, როდესაც მისი გამოუყენებელი ნაშთი ნულის ტოლია. ამ შემთხვევაში, მწკრივი ითვლება დადებითად იმ პირობით, რომ მეორე შევსებული უჯრედი, რომელიც მდებარეობს ამ მწკრივთან დაკავშირებულ სვეტში სხვა შევსებული უჯრედის მიერ, მდებარეობს დადებით რიგში.
ზემოაღნიშნული გამეორებების შემდეგ, გაუნაწილებელი ნაშთი ხდება ნული. შედეგი არის ოპტიმალური ტექნიკური მახასიათებლების გეგმა.