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

15.02.2019

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

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

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

თეორიული მასალა ტრანსპორტის პრობლემის შესახებ

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

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

აქვს შემდეგი ფორმა:

სად: ზ- საქონლის ტრანსპორტირების ხარჯები;
X- ტვირთის მოცულობა;
C- ტვირთის ერთეულის ტრანსპორტირების ღირებულება (ტარიფი);
ა- მომწოდებლის მარაგი;
ბ- მომხმარებლის მოთხოვნა;
მ- მომწოდებლების რაოდენობა;
ნ- მომხმარებელთა რაოდენობა.

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

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

მისი არსი შემდეგია: ჩვენ ვპოულობთ გარკვეულ საცნობარო გეგმას და ვამოწმებთ მას ოპტიმალურობა (Z → წთ). თუ გეგმა ოპტიმალურია, გამოსავალი ნაპოვნია. თუ არა, გააუმჯობესეთ გეგმა რამდენჯერაც საჭიროა, სანამ არ მოიძებნება ოპტიმალური გეგმა.

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

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

დეტალური ინსტრუქციები ტრანსპორტის პრობლემის გადასაჭრელად

1. სატრანსპორტო მაგიდის აგება

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

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

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

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

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

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

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, ამიტომ ტრანსპორტის ეს პრობლემა დახურულია.

3. საცნობარო გეგმის შედგენა

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

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

ა) ჩრდილო-დასავლეთის კუთხის მეთოდი. ჩვენება

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

მეთოდის დეტალური აღწერა და მაგალითი შეგიძლიათ იხილოთ.

ბ) მინიმალური ელემენტის მეთოდი. ჩვენება

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

გ) ვოგელის დაახლოება. ჩვენება

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

დ) ორმაგი უპირატესობის მეთოდი. ჩვენება

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

4. გადაგვარების მხარდაჭერის გეგმის შემოწმება

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

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

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

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

ძირითადი უჯრედების რაოდენობა = 5

m + n – 1 = 3 + 3 – 1 = 5

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

5. პოტენციალების გაანგარიშება ტრანსპორტირების გეგმისთვის

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

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

ასე რომ, მოდით შევადაროთ თითოეული მიმწოდებელი Ai და თითოეული მომხმარებელი Bj მნიშვნელობებთან Uiდა ვჯშესაბამისად, ისე, რომ გეგმის ყველა ძირითადი უჯრედისთვის დაკმაყოფილებულია შემდეგი მიმართება:

Ui + Vj = Cij

დაამატეთ ტრანსპორტის მაგიდას დამატებითი ხაზიდა სვეტი Ui-სა და Vj-სთვის.

დავუშვათ, რომ U1 = 0.

შემდეგ შეგვიძლია ვიპოვოთ V3 = C13 – U1 = 1 – 0 = 1.

ვიცოდეთ V3, ახლა შეგვიძლია ვიპოვოთ U3:

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

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

გეგმის თითოეული თავისუფალი უჯრედისთვის, ჩვენ ვიანგარიშებთ განსხვავებებს

ΔCij = Cij – (Ui + Vj)

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

გეგმა არის ოპტიმალური, თუ ყველა განსხვავება ΔCij ≥ 0.

IN ამ შემთხვევაშიგეგმა - არაოპტიმალური(ΔC22< 0), и его следует улучшить путем перераспределения поставок.

7. მარაგების გადანაწილება

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

მოდი, უჯრა უარყოფითი სხვაობით ΔCij აღვნიშნოთ „+“ ნიშნით, შემდეგი – „-“ ნიშნით და ასე შემდეგ, სათითაოდ.

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

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

ვინაიდან m + n – 1-ზე მეტი ძირითადი უჯრედია, ჩვენ ვაქცევთ ნულოვანი მნიშვნელობის ძირითად უჯრედს თავისუფლად:

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

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

8. თუ ოპტიმალური გამოსავალი მოიძებნა, გადადით მე-9 საფეხურზე, თუ არა, გადადით მე-5 საფეხურზე.

ჩვენ ვიპოვეთ ოპტიმალური გადაწყვეტა, ამიტომ გადადით მე-9 პუნქტზე.

9. საქონლის ტრანსპორტირების ჯამური ხარჯების გაანგარიშება

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

ზმინ = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 დენ. ერთეულები

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

10. ტრანსპორტირების გრაფიკის აგება

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

შედეგი იქნება ქვემოთ მოყვანილი გრაფიკის მსგავსი:

ესე იგი, ტრანსპორტის პრობლემა მოგვარებულია. გილოცავ!

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

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

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

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

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

მდგომარეობა:
ერთგვაროვანი ტვირთი კონცენტრირებულია m მომწოდებლებს შორის 1, a 2, ... a m ტომებში.
ეს ტვირთი უნდა მიეწოდოს n მომხმარებელს ტომებში b 1, b 2 ... b n.
ცნობილი C ij, i=1,2,...მ; j=1,2,...n — ტვირთის გადაზიდვის ღირებულება ყოველი მე-ე მიმწოდებლიდან თითოეულ j-ე მომხმარებელს.
საჭიროა სატრანსპორტო გეგმის შედგენა, რომელშიც ყველა მიმწოდებლის მარაგები ტრანსპორტირდება სრულად, ყველა მომხმარებლის მოთხოვნა სრულად დაკმაყოფილებულია და ყველა საქონლის ტრანსპორტირების ჯამური ხარჯები მინიმალურია.

სატრანსპორტო დავალების საწყისი მონაცემები იწერება ცხრილის სახით:

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

ვექტორი A=(a 1 ,a 2 ,...,a m) მომწოდებლების მარაგები
ვექტორი B=(b 1 ,b 2 ,...,b n) მომხმარებელთა მოთხოვნები
ხარჯების მატრიცები:

ტრანსპორტის პრობლემის მათემატიკური მოდელი

ტრანსპორტის ამოცანის ცვლადები (უცნობები) არის x ij , i=1,2,...,m j=1,2,...,n - ტრანსპორტირების მოცულობა i-ე მიმწოდებლიდან თითოეულ j-მდე. მომხმარებელი.
ეს ცვლადები შეიძლება დაიწეროს როგორც სატრანსპორტო მატრიცა:

ვინაიდან პროდუქტი C ij *X ij განსაზღვრავს საქონლის ტრანსპორტირების ხარჯებს მე-ე მიმწოდებლიდან j-ე მომხმარებელამდე, ყველა საქონლის ტრანსპორტირების ჯამური ხარჯები უდრის:

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

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

n განტოლების მეორე ჯგუფი გამოხატავს ყველა n მომხმარებლის მოთხოვნების სრულად დაკმაყოფილების მოთხოვნას და აქვს ფორმა:

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

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

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

სატრანსპორტო პრობლემის მათემატიკური ფორმულირებაარის: იპოვე დავალების ცვლადები X=(x ij), i=1,2,...,m; j=1,2,...,n, შეზღუდვების სისტემის დაკმაყოფილება (ნომერი 2 მათემატიკური მოდელის), (3), არაუარყოფითი პირობების (4) და მინიმუმის უზრუნველყოფა. ობიექტური ფუნქცია (1)

მაგალითი 34.1

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

გამოსავალი:
1. ჩვენ წარმოგიდგენთ დავალების ცვლადებს (სატრანსპორტო მატრიცა):

2. ჩვენ ვწერთ ხარჯების მატრიცას:

3. ამოცანის ობიექტური ფუნქცია უდრის C და X მატრიცების ყველა შესაბამისი ელემენტის ნამრავლების ჯამს.

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

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

ეს ნიშნავს, რომ მომწოდებლების მარაგები მთლიანად ამოღებულია.

X მატრიცის თითოეულ სვეტში ტრანსპორტირების რაოდენობა უნდა იყოს შესაბამისი მომხმარებლების მოთხოვნების ტოლი:

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

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

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

ინსტრუქციები. სატრანსპორტო პრობლემის გადაჭრის მიზნით ონლაინ რეჟიმიშეარჩიეთ სატარიფო მატრიცის განზომილება (მიმწოდებლების რაოდენობა და მაღაზიების რაოდენობა).

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

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

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

წაშლა (ორმაგი უპირატესობის მეთოდი);
ჩრდილო-დასავლეთი კუთხე;
მინიმალური ელემენტი;
ვოგელის მიახლოებები.

სატრანსპორტო პრობლემის საცნობარო გადაწყვეტა

სატრანსპორტო პრობლემის საცნობარო გადაწყვეტაარის ნებისმიერი შესაძლებელი გამოსავალი, რომლისთვისაც დადებითი კოორდინატების შესაბამისი პირობის ვექტორები წრფივად დამოუკიდებელია. შესამოწმებლად ხაზოვანი დამოუკიდებლობაგამოიყენება დასაშვები ხსნარის კოორდინატებთან შესაბამისი პირობების ვექტორები, ციკლები.
ციკლისატრანსპორტო დავალების ცხრილის უჯრედების თანმიმდევრობას ეწოდება, რომელშიც ორი და მხოლოდ მიმდებარე უჯრედი განლაგებულია იმავე მწკრივში ან სვეტში, ხოლო პირველი და ბოლო ასევე იმავე სტრიქონში ან სვეტში. სატრანსპორტო პრობლემის პირობების ვექტორების სისტემა წრფივად დამოუკიდებელია, თუ და მხოლოდ იმ შემთხვევაში, თუ ცხრილის შესაბამისი უჯრედებიდან ციკლის ფორმირება შეუძლებელია. მაშასადამე, ტრანსპორტის პრობლემის დასაშვები გადაწყვეტა, i=1,2,...,m; j=1,2,...,n არის მითითება მხოლოდ იმ შემთხვევაში, თუ მის მიერ დაკავებული ცხრილის უჯრებიდან ციკლის ფორმირება შეუძლებელია.

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

მაგალითი No1. სატარიფო მატრიცა (აქ მომწოდებლების რაოდენობაა 4, მაღაზიების რაოდენობა 6):

	1	2	3	4	5	6	რეზერვები
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	10	1	100	60
საჭიროებებს	10	30	40	50	70	30

გამოსავალი. წინასწარი ეტაპიტრანსპორტის პრობლემის გადაჭრა დამოკიდებულია მისი ტიპის განსაზღვრაზე, ღიაა თუ დახურული. შევამოწმოთ პრობლემის გადაჭრის აუცილებელი და საკმარისი პირობა.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
ბალანსის პირობა დაცულია. უზრუნველყოფს თანაბარ საჭიროებებს. ასე რომ, ტრანსპორტის პრობლემის მოდელი დახურულია. თუ მოდელი ღია იქნებოდა, საჭირო იქნებოდა დამატებითი მომწოდებლების ან მომხმარებლების შემოყვანა.
ჩართულია მეორე ეტაპისაცნობარო გეგმის ძებნა ხდება ზემოთ მოცემული მეთოდების გამოყენებით (ყველაზე გავრცელებული არის ყველაზე დაბალი ღირებულების მეთოდი).
ალგორითმის საჩვენებლად წარმოგიდგენთ მხოლოდ რამდენიმე გამეორებას.
გამეორება No1. მინიმალური მატრიცის ელემენტი ნულის ტოლი. ამ ელემენტისთვის, ინვენტარი არის 60 და მოთხოვნები 30. მათგან ვირჩევთ მინიმალურ რიცხვს 30 და ვაკლებთ (იხ. ცხრილი). ამავდროულად, ცხრილიდან მეექვსე სვეტს ვკვეთთ (მისი საჭიროებები 0-ის ტოლია).

3	20	8	13	4	x	80
4	4	18	14	3	0	60 - 30 = 30
10	4	18	8	6	x	30
7	19	17	0	1	x	60
10	30	40	50	70	30 - 30 = 0	0

გამეორება No2. ჩვენ კვლავ ვეძებთ მინიმუმს (0). წყვილიდან (60;50) ვირჩევთ მინიმალურ რიცხვს 50. გადაკვეთეთ მეხუთე სვეტი.

3	20	8	x	4	x	80
4	4	18	x	3	0	30
10	4	18	x	6	x	30
7	19	17	0	1	x	60 - 50 = 10
10	30	40	50 - 50 = 0	70	0	0

გამეორება No3. ჩვენ ვაგრძელებთ პროცესს მანამ, სანამ არ შევარჩევთ ყველა საჭიროებას და მარაგს.
გამეორება No N. ელემენტი, რომელსაც ეძებთ არის 8. ამ ელემენტისთვის, მარაგი უდრის მოთხოვნებს (40).

3	x	8	x	4	x	40 - 40 = 0
x	x	x	x	3	0	0
x	4	x	x	x	x	0
x	x	x	0	1	x	0
0	0	40 - 40 = 0	0	0	0	0

	1	2	3	4	5	6	რეზერვები
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	0	1	100	60
საჭიროებებს	10	30	40	50	70	30

დავთვალოთ ცხრილის ოკუპირებული უჯრედების რაოდენობა, არის 8, მაგრამ ის უნდა იყოს m + n - 1 = 9. შესაბამისად, მხარდაჭერის გეგმა დეგენერირებულია. ჩვენ ვაშენებთ ახალი გეგმა. ზოგჯერ თქვენ უნდა ააწყოთ რამდენიმე საცნობარო გეგმა, სანამ იპოვით არადეგენერატულ გეგმას.

	1	2	3	4	5	6	რეზერვები
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	0	1	100	60
საჭიროებებს	10	30	40	50	70	30

შედეგად, მიიღება პირველი დამხმარე გეგმა, რომელიც მოქმედებს, ვინაიდან ცხრილის დაკავებული უჯრედების რაოდენობა არის 9 და შეესაბამება ფორმულას m + n - 1 = 6 + 4 - 1 = 9, ე.ი. საცნობარო გეგმა არის არადეგენერატი.
მესამე ეტაპიშედგება ნაპოვნი საცნობარო გეგმის გაუმჯობესებაში. აქ ისინი იყენებენ პოტენციურ მეთოდს ან განაწილების მეთოდს. ამ ეტაპზე გადაწყვეტის სისწორის მონიტორინგი შესაძლებელია ღირებულების ფუნქციის F(x) მეშვეობით. თუ ის მცირდება (ექვემდებარება ხარჯების მინიმიზაციას), მაშინ გამოსავალი სწორია.

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

	30	50	70	10	30	10
40	2	4	6	1	1	2
80	3	4	5	9	9	6
60	4	3	2	7	8	7
20	5	1	3	5	7	9

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

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

მაგალითი No4. ობიექტების ასაშენებლად აგურის მიწოდება ხდება სამი (I, II, III) ქარხნიდან. ქარხნებს საწყობებში, შესაბამისად, 50, 100 და 50 ათასი ერთეული აქვთ. აგური ობიექტებს ესაჭიროებათ შესაბამისად 50, 70, 40 და 40 ათასი ცალი. აგური ტარიფები (დენ. ერთეული/ათას ერთეული) ნაჩვენებია ცხრილში. შექმენით სატრანსპორტო გეგმა, რომელიც მინიმუმამდე დაიყვანოს მთლიანი ტრანსპორტირების ხარჯები.

დაიხურება თუ:
ა) a=40, b=45
ბ) a=45, b=40
ბ) a=11, b=12
დახურული სატრანსპორტო ამოცანის მდგომარეობა: ∑a = ∑b
ვპოულობთ, ∑a = 35+20+b = 55+b; ∑b = 60+a
ვიღებთ: 55+b = 60+a
თანასწორობა დაფიქსირდება მხოლოდ მაშინ, როდესაც a=40, b=45