ბოროტების კანონიკურ ფორმაზე გადასვლა. წრფივი პროგრამირების პრობლემის გადაჭრის მარტივი მეთოდი
კანონიკური ფორმა, თუ გსურთ ობიექტური ფუნქციის მაქსიმიზაცია, სისტემის ყველა შეზღუდვა არის განტოლება და არაუარყოფითობის პირობა დაწესებულია ყველა ცვლადზე.
ხაზოვანი პროგრამირების პრობლემა მოცემულია სიმეტრიული ფორმა, თუ საჭიროა ობიექტური ფუნქციის მაქსიმიზაცია, სისტემის ყველა შეზღუდვა არის უტოლობა „“ (ან ობიექტური ფუნქციის მინიმიზაცია, სისტემის ყველა შეზღუდვა არის უტოლობა „“) და არაუარყოფითობის პირობა დაწესებულია ყველა ცვლადზე.
რიცხვების ნაკრები ეწოდება მისაღები გადაწყვეტა (გეგმა), თუ ის აკმაყოფილებს ZLP-ის შეზღუდვების სისტემას.
ყველა შესაძლო გადაწყვეტილებების ნაკრები ეწოდება შესაძლებელი გადაწყვეტილებების არეალი(ODR).
დასაშვებ გამოსავალს, რომლისთვისაც მიღწეულია ფუნქციის მაქსიმალური (მინიმალური) მნიშვნელობა ეწოდება ოპტიმალური PAP გეგმა.
ტერმინები „გეგმა“ და „ოპტიმალური გეგმა“ მომდინარეობს ეკონომიკური აპლიკაციებიდან.
ZLP ჩაწერის სამივე ფორმა ექვივალენტურია იმ გაგებით, რომ არსებობს ერთი ფორმიდან მეორეზე გადასვლის ალგორითმები. ამრიგად, თუ არსებობს პრობლემის გადაჭრის გზა ერთ-ერთი ფორმით, მაშინ ყოველთვის შესაძლებელია განისაზღვროს ოპტიმალური გეგმა ნებისმიერი სხვა ფორმით მოცემული პრობლემისთვის. სიმეტრიული ფორმით პრობლემა წყდება გრაფიკული მეთოდით, ხოლო კანონიკური სახით სიმპლექსის მეთოდით.
განვიხილოთ ერთი ფორმიდან მეორეზე გადასვლის ალგორითმები.
სიმეტრიული კანონიკური.გადასვლა ხორციელდება ყოველი უტოლობის მარცხენა მხარეს დამატებითი არაუარყოფითი ცვლადის დამატებით. თუ უტოლობა იყო "≤", მაშინ ბალანსის ცვლადი ემატება უტოლობის მარცხენა მხარეს "+" ნიშნით. თუ უტოლობა იყო „“, მაშინ ბალანსის ცვლადი ემატება უტოლობის მარცხენა მხარეს „–“ ნიშნით. შემოღებულ ახალ ცვლადებს ე.წ ბალანსი. Z ფუნქციის მინიმიზაციის პრობლემა ჩანაცვლებულია ფუნქციის (–Z) მაქსიმიზაციის ამოცანებით და მისი გამოყენებით min Z = –max (–Z).
კანონიკური სიმეტრიული.ასეთი გადასვლის განსახორციელებლად მოიძებნება განტოლებათა სისტემის ზოგადი ამოხსნა – შეზღუდვები, სამიზნე ფუნქცია გამოიხატება თავისუფალი ცვლადების სახით. შემდეგი, საბაზისო ცვლადების არანეგატიურობით სარგებლობით, ჩვენ შეგვიძლია გამოვრიცხოთ ისინი პრობლემისგან. პრობლემის სიმეტრიული ფორმა შეიცავს უტოლობას, რომელიც ეხება მხოლოდ თავისუფალ ცვლადებს და ობიექტურ ფუნქციას, რომელიც დამოკიდებულია მხოლოდ თავისუფალ ცვლადებზე. ძირითადი ცვლადების მნიშვნელობები ნაპოვნია განტოლებათა ორიგინალური სისტემის ზოგადი ამონახსნით.
ზოგადი კანონიკური.ყოველი ცვლადი, რომელზეც არ იყო დაწესებული არაუარყოფითი პირობა, წარმოდგენილია ორი ახალი არაუარყოფითი ცვლადის სხვაობით. უტოლობები გარდაიქმნება განტოლებად, თითოეული უტოლობის მარცხენა მხარეს ბალანსის ცვლადის შემოღებით, ისევე, როგორც აღწერილი იყო სიმეტრიულიდან კანონიკურ ფორმაზე გადასვლისას. Z ფუნქციის მინიმიზაციის პრობლემა ჩანაცვლებულია ფუნქციის (–Z) მაქსიმიზაციის ამოცანებით, როგორც აღწერილი იყო სიმეტრიულიდან კანონიკურ ფორმაზე გადასვლისას.
ხაზოვანი პროგრამირების პრობლემის გადაჭრის გრაფიკული მეთოდი
პუნქტების სიმრავლე ე.წ ამოზნექილი, თუ ნაკრების ნებისმიერი ორი წერტილისთვის ის შეიცავს მათ დამაკავშირებელ სეგმენტს.
მაგალითი 1
სიბრტყეზე წერტილების შემდეგი ნაკრები ამოზნექილია:
სიბრტყეზე წერტილების შემდეგი ნაკრები არ არის ამოზნექილი: 
თეორემა 1 ამოზნექილი სიმრავლეების ნებისმიერი რაოდენობის კვეთა არის ამოზნექილი სიმრავლე.
თეორემა 2 მოდით იყოს ორი თვითნებური წერტილი სივრცეში რ ნ. შემდეგ სეგმენტის ნებისმიერი წერტილისთვის [ PQ] უნდა შესრულდეს: .სადაც .
ჰიპერპლანისივრცეში რ ნარის პუნქტების ნაკრები, რომელიც აკმაყოფილებს განტოლებას. გაითვალისწინეთ, რომ ორგანზომილებიან შემთხვევაში ჰიპერპლანი არის სწორი ხაზი.
ნახევარი სივრცეარის პუნქტების ერთობლიობა, რომელიც აკმაყოფილებს ერთ-ერთ უტოლობას ან . ჰიპერთვითმფრინავი სივრცეში წერტილებს ორ ნახევრად სივრცედ ყოფს. ორგანზომილებიან შემთხვევაში, ჰიპერპლანი არის ნახევრად სიბრტყე.
თეორემა 3 ნახევარსივრცე არის ამოზნექილი ნაკრები.
შედეგი ნახევრად სივრცის ნებისმიერი რაოდენობის გადაკვეთა არის ამოზნექილი სიმრავლე.
პოლიედონიეწოდება ერთი ან მეტი ნახევარსივრცის კვეთა. ორგანზომილებიან შემთხვევაში მრავალკუთხედს მრავალკუთხედი ეწოდება.
მაგალითი 2
შემდეგი კომპლექტები მრავალკუთხედებია.
შეზღუდული კომპლექტი
შეუზღუდავი ნაკრები
ერთი წერტილი
ცარიელი ნაკრები
ამოზნექილი სიმრავლის წერტილი ეწოდება კუთხოვანი, თუ ის არ დევს რომელიმე სეგმენტის შიგნით, რომელიც აკავშირებს კომპლექტიდან ორ სხვა წერტილს.
მაგალითი 3
სამკუთხედის კუთხის წერტილები მისი წვეროებია (არის სამი). წრის კუთხის წერტილები არის წრის წერტილები, რომლებიც ზღუდავს მას (არის უსასრულო რაოდენობა).
მრავალედრონის კუთხის წერტილს მისი ეწოდება ზედა.
განვიხილოთ ZLP მოცემული სიმეტრიული ფორმით.
თეორემა 4 ZLP-ის ოპტიმალური გეგმა შეესაბამება გადაწყვეტილების პოლიედრონის წვეროს, რომელიც განისაზღვრება მისი შეზღუდვების სისტემით.
მიზნობრივი ფუნქციისა და შეზღუდვების სისტემის ჩაწერა სხვადასხვა წრფივი პროგრამირების ამოცანებში არ არის ერთნაირი: ზოგ ამოცანში საჭიროა ობიექტური ფუნქციის მინიმუმის პოვნა, ზოგში კი - მაქსიმალური; ზოგ შემთხვევაში საჭირო ცვლადები დამოკიდებულია ერთ ინდექსზე, ზოგ შემთხვევაში კი ორზე; ზოგიერთ ამოცანში შეზღუდვები მითითებულია წრფივი უტოლობების სისტემის სახით, ხოლო ზოგიერთში - წრფივი განტოლებათა სისტემის სახით. პრაქტიკაში ასევე შესაძლებელია ისეთი პრობლემების არსებობა, რომლებშიც ზოგიერთი შეზღუდვა წრფივი უტოლობების სახითაა, ზოგი კი წრფივი განტოლებების სახით. ასევე, ყველა პრობლემას არ შეუძლია მოითხოვოს ცვლადების არანეგატიურობა.
ხაზოვანი პროგრამირების ამოცანების ასეთი მრავალფეროვნების გათვალისწინება მოითხოვს მათი ცალკეული კლასების გადაჭრის სპეციალური მეთოდების შემუშავებას. ჩვენ ყურადღებას გავამახვილებთ წრფივი პროგრამირების ზოგადი თვისებებისა და მეთოდების შესწავლაზე, დაწერილი ე.წ კანონიკური ფორმით.
თუ წრფივი პროგრამირების ამოცანაში საწყისი შეზღუდვების სისტემა იღებს განტოლების ფორმას, როგორიცაა
და თქვენ უნდა იპოვოთ ხაზოვანი მიზნობრივი ფუნქციის მაქსიმუმი
მაშინ ხაზოვანი პროგრამირების ამოცანა ითვლება კანონიკური ფორმით დაწერილად.
ნებისმიერი წრფივი პროგრამირების პრობლემა შეიძლება ადვილად შემცირდეს კანონიკურ ფორმამდე. ზოგადად, ამისათვის საკმარისია, პირველ რიგში, შევძლოთ ობიექტური ფუნქციის მინიმიზაციის პრობლემა მისი მაქსიმიზაციის პრობლემამდე, მეორეც, გადავიდეთ უთანასწორობის შეზღუდვებიდან თანასწორობის შეზღუდვებზე და მესამე, შეცვალოთ ის ცვლადები, რომლებიც არ ექვემდებარება არაუარყოფითობის პირობას.
იმ შემთხვევაში, როდესაც თქვენ გჭირდებათ ფუნქციის მინიმუმის პოვნა
, შეგვიძლია გავაგრძელოთ ფუნქციის მაქსიმუმის პოვნა
, რადგან შემდეგი განცხადება მართალია: 
.
თავდაპირველი პრობლემის უთანასწორობის შეზღუდვა, რომელსაც აქვს ფორმა " 
", შეიძლება გადაიქცეს განტოლების შეზღუდვად დამატებითი არაუარყოფითი ცვლადის დამატებით მის მარცხენა მხარეს და ფორმის უთანასწორობის შეზღუდვით" 
” – მისი მარცხენა მხრიდან დამატებითი არაუარყოფითი ცვლადის გამოკლებით.
გაითვალისწინეთ, რომ შემოღებული დამატებითი არაუარყოფითი ცვლადების რაოდენობა ყოველთვის უდრის უტოლობების რაოდენობას შეზღუდვების თავდაპირველ სისტემაში.
შემოღებულ დამატებით ცვლადებს ძალიან სპეციფიკური ეკონომიკური მნიშვნელობა აქვს. ამრიგად, თუ ორიგინალური ხაზოვანი პროგრამირების პრობლემის შეზღუდვები ასახავს წარმოების რესურსების ხარჯებს და ხელმისაწვდომობას, მაშინ დამატებითი ცვლადის რიცხვითი მნიშვნელობა აჩვენებს შესაბამისი გამოუყენებელი რესურსის რაოდენობას.
გაითვალისწინეთ ისიც, რომ თუ ზოგიერთი ცვლადი 
არ ემორჩილება არაუარყოფითობის პირობას, მაშინ ის უნდა შეიცვალოს ორი არაუარყოფითი ცვლადით 
და 
, რომელმაც მიიღო 
.
მაგალითი. დაწერეთ შემდეგი წრფივი ოპტიმიზაციის ამოცანა კანონიკური ფორმით: იპოვეთ ფუნქციის მინიმუმი
შეზღუდვების ქვეშ
გამოსავალი
ამ პრობლემაში თქვენ უნდა იპოვოთ ობიექტური ფუნქციის მინიმუმი, ხოლო შეზღუდვების სისტემა მოიცავს ოთხ უტოლობას. იმისათვის, რომ დაწეროთ იგი კანონიკური ფორმით, თქვენ უნდა გადახვიდეთ უტოლობის შეზღუდვებიდან განტოლების შეზღუდვებზე და ასევე გარდაქმნათ ობიექტური ფუნქცია.
ვინაიდან პრობლემის შეზღუდვების სისტემაში შემავალი უტოლობების რაოდენობა უდრის ოთხს, ეს გადასვლა უნდა განხორციელდეს ოთხი დამატებითი არაუარყოფითი ცვლადის შემოღებით. უფრო მეტიც, მეორე და მეოთხე უტოლობებში არის ნიშანი " 
", ასე რომ, ჩვენ ვამატებთ დამატებით ცვლადებს მათ მარცხენა მხარეს. პირველ და მესამე უტოლობაში არის ნიშანი " 
", რაც ნიშნავს, რომ ჩვენ ვაკლებთ დამატებით ცვლადებს მათ მარცხენა მხარეს.
ჩვენ ასევე გარდაქმნით ობიექტურ ფუნქციას, ვცვლით ყველა ნიშანს საპირისპიროდ და ვპოულობთ მის მაქსიმუმს.
ამრიგად, ეს ხაზოვანი პროგრამირების პრობლემა დაიწერება შემდეგი კანონიკური ფორმით:
იპოვნეთ ფუნქციის მაქსიმუმი 
შეზღუდვების ქვეშ 
გვერდი 1
პრობლემის კანონიკური ფორმა ხასიათდება შემდეგი სამი თავისებურებით: 1) შეზღუდვების ერთგვაროვანი სისტემა განტოლებათა სისტემის სახით; 2) ჰომოგენური არაუარყოფითი პირობები, რომლებიც ეხება პრობლემაში ჩართულ ყველა ცვლადს და 3) წრფივი ფუნქციის მაქსიმიზაცია. ამ პრობლემაში სამივე მახასიათებელი ირღვევა.
პრობლემის კანონიკური ფორმა ხასიათდება შემდეგი სამი თავისებურებით: 1) შეზღუდვების ერთგვაროვანი სისტემა განტოლებათა სისტემის სახით; 2) ჰომოგენური არაუარყოფითი პირობები, რომლებიც ეხება პრობლემაში ჩართულ ყველა ცვლადს და 3) წრფივი ფუნქციის მაქსიმიზაცია. ამ პრობლემაში სამივე მახასიათებელი ირღვევა.
ხაზოვანი პროგრამირების პრობლემის კანონიკური ფორმა მოსახერხებელია იმით, რომ ადვილია შესაძლებელი რეგიონის საწყისი წვერის პოვნა.
განვიხილოთ წრფივი პროგრამირების პრობლემის კანონიკური ფორმა და ჟორდანია-გაუსის ელიმინაციის მეთოდი.
ხაზოვანი პროგრამირების პრობლემის კანონიკური ფორმა ხშირად მოსახერხებელია.
წრფივი პროგრამირების პრობლემის კანონიკურ ფორმად შეზღუდვების სისტემის გარდაქმნისას, უტოლობები (12) და (13) უნდა შეიცვალოს ტოლობებით. ამისათვის შემოღებულია დამატებითი არაუარყოფითი ცვლადები.
დაამტკიცეთ, რომ წყვილში გადაადგილებული რეალური მატრიცები ერთდროულად მცირდება ამოცანის კანონიკურ ფორმამდე 1128 ორთოგონალური მატრიცის გამოყენებით მსგავსების გარდაქმნით.
არსებითად (4) - (5) შეიძლება ჩაითვალოს არაწრფივი პროგრამირების ამოცანის კანონიკურ ფორმად, რადგან თავში ასახული მეთოდები. როგორც წესი, არაწრფივი პროგრამირების ამოცანებში არ არის მოთხოვნა, რომ ცვლადები იყოს მთელი რიცხვი.
| შეზღუდვების სახეები და მათი ტრანსფორმაციის მეთოდები. |
პრობლემის კანონიკური ფორმა ხასიათდება შეზღუდვების სისტემის ერთგვაროვნებით განტოლებათა სისტემის სახით; ობიექტური ფუნქციის მაქსიმიზაცია; პრობლემაში ჩართული ყველა ცვლადის არანეგატიურობის პირობა.
პრობლემების კანონიკური ფორმა არ მატებს რაიმე დამატებით მახასიათებლებს განსახილველ გამოთვლით სქემას.
ჯერ განვიხილოთ მინიმალური პრობლემის მეორე კანონიკური ფორმა.
Simplex-mete ალგორითმი შეიძლება დაიყოს ორ ეტაპად. პირველ ეტაპზე, ძირითადი გამოსავალი არის ნაპოვნი ცვლადების აღმოფხვრით. თუ აღმოჩენილია, მაშინ გვაქვს პრობლემის კანონიკური ფორმა მეორე ეტაპზე გადასასვლელად. მეორე ნაბიჯი არის იმის შემოწმება, არის თუ არა შემოსაზღვრული ოპტიმუმი. თუ ის არსებობს, მაშინ განისაზღვრება დასაშვები ძირითადი გადაწყვეტილებები და საიდანაც შეირჩევა ოპტიმალური.
თუ პრობლემა მოგვარებულია კანონიკური ფორმით, მაშინ გამოიყენება მეორე პუნქტში წარმოდგენილი ოპერაციების მხოლოდ ნაწილი. ამრიგად, კანონიკური მინიმალური ამოცანისთვის რეალიზებულია მხოლოდ 3.4.1 პუნქტის შემთხვევა და საჭიროა მხოლოდ სვეტების ციკლური გადაწყობის ოპერაციები, სვეტის ვერტიკალური სასაზღვრო ზონის გავლით, სტრუქტურული დარღვევების გამოსწორება და შეკვეცის ოპერაციის ნაწილი. სიმეტრიულად, კანონიკური მაქსიმალური ამოცანის ამოხსნისას რეალიზებულია მხოლოდ 3.4.2 პუნქტის შემთხვევა და ხდება სიმების ციკლური გადაწყობის ოპერაციები, სტრიქონის გავლა ჰორიზონტალურ სასაზღვრო ზონაში, სტრუქტურული დარღვევების გამოსწორება და შეკვეცის ოპერაციის სხვა ნაწილი. საჭირო. წინააღმდეგ შემთხვევაში, პრობლემის კანონიკური ფორმა არ მატებს რაიმე დამატებით სპეციფიკას.
შესავლის პირველ აბზაცში ნაჩვენებია, თუ როგორ შეიძლება შემცირდეს ზოგადი წრფივი პროგრამირების პრობლემა ერთ-ერთ კანონიკურ ფორმამდე. კანონიკური პრობლემებისთვის, თანმიმდევრული გაუმჯობესების მეთოდის აღწერა ოფიციალურად გამარტივებულია, რადგან არ არის საჭირო ოპტიმალური პირობების დარღვევის ორი ვარიანტის განხილვა და შემდეგი წვეროს მიღწევის ორი ვარიანტი, თუმცა, ეს ზრდის საბაზისო მატრიცის ზომას [. /, J ], რომელიც ძირითადად განსაზღვრავს სირთულეს თუმცა, ხშირ შემთხვევაში მეთოდის გამოყენება პრობლემის კანონიკურ ფორმებზე სასურველია და ამ განყოფილებაში შევეხებით კონკრეტული წრფივისთვის მიღებულ მეთოდის ვარიანტებს. პროგრამირების პრობლემები.
გვერდები: 1
ZLP-ის კანონიკური ფორმა- ax = b ფორმის წრფივი პროგრამირების ამოცანა, სადაც a არის კოეფიციენტის მატრიცა, b არის შეზღუდვის ვექტორი.მომსახურების მიზანი. ონლაინ კალკულატორი შექმნილია PPP-ის KZLP-ზე გადასვლისთვის. პრობლემის კანონიკურ ფორმამდე მიყვანა ნიშნავს, რომ ყველა შეზღუდვას ექნება თანასწორობის ფორმა დამატებითი ცვლადების შემოღებით.
თუ შეზღუდვა არ არის დაწესებული რომელიმე ცვლადზე x j, მაშინ ის იცვლება დამატებითი ცვლადების სხვაობით, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.
ინსტრუქციები. აირჩიეთ ცვლადების რაოდენობა და რიგების რაოდენობა (შეზღუდვების რაოდენობა). შედეგად მიღებული გამოსავალი ინახება Word ფაილში.
როგორ შევიყვანოთ წრფივი პროგრამირების პრობლემა კანონიკურ ფორმამდეZLP-ის მათემატიკური მოდელი ე.წ ძირითადი, თუ მასში შეზღუდვები წარმოდგენილია განტოლებების სახით იმ პირობით, რომ ცვლადები არაუარყოფითია.
მათემატიკური მოდელი ე.წ კანონიკური, თუ მისი შეზღუდვების სისტემა წარმოდგენილია m წრფივი დამოუკიდებელი განტოლებების სისტემის სახით (სისტემის რანგი r=m), სისტემა გამოიყოფა. ერთეულის საფუძველი, განსაზღვრულია თავისუფალი ცვლადები და ობიექტური ფუნქცია გამოიხატება თავისუფალი ცვლადების სახით. ამ შემთხვევაში, განტოლებების მარჯვენა მხარეები არაუარყოფითია (b i ≥ 0).
ცვლადებს, რომლებიც შედის სისტემის ერთ-ერთ განტოლებაში კოეფიციენტით ერთი და არ არსებობს სხვა განტოლებებში, ე.წ. ძირითადი უცნობიდა ყველა სხვა - უფასო.
სისტემის გამოსავალი ე.წ ძირითადი, თუ მასში არსებული თავისუფალი ცვლადები 0-ის ტოლია და მას აქვს ფორმა:
X ფუძეები = (0, 0; b 1 , ..., b m), f(X ფუძეები) = c 0
ძირითადი გადაწყვეტაარის სისტემის ამონახსნთა სიმრავლის კუთხის წერტილი, ე.ი. განსაზღვრავს მოდელის ამოხსნის მრავალკუთხედის წვეროს. ასეთ გადაწყვეტილებებს შორის არის ის, რომელშიც ობიექტური ფუნქცია იღებს ოპტიმალური ღირებულება.
საბაზისო ამოხსნას ეწოდება საცნობარო გამოსავალი, თუ ის დასაშვებია, ე.ი. სისტემის განტოლებების (ან უტოლობების) ყველა მარჯვენა მხარე დადებითია b i ≥ 0.
კანონიკური მოდელის კომპაქტური ფორმაა:
AX = ბ
X ≥ 0
Z = CX (მაქს)
დასაშვები ამოხსნის კონცეფცია, დასაშვები ამონახსნების რეგიონი, ხაზოვანი პროგრამირების პრობლემის ოპტიმალური გადაწყვეტა.
განმარტება 1. ვექტორს X, რომელიც აკმაყოფილებს ZLP შეზღუდვების სისტემას, მათ შორის არაუარყოფითობის პირობებს, ასეთის არსებობის შემთხვევაში, ეწოდება ZLP-ის დასაშვები ამოხსნა.
განმარტება 2. ყველა დასაშვები ხსნარის ნაკრები ქმნის PLP-ის დასაშვები ხსნარების (ADA) რეგიონს.
განმარტება 3. განხორციელებულ გადაწყვეტას, რომლისთვისაც ობიექტური ფუნქცია აღწევს მაქსიმუმს (ან მინიმუმს) ეწოდება ოპტიმალური გადაწყვეტა.
მაგალითი No1. შეამცირეთ შემდეგი LP პრობლემა კანონიკურ ფორმამდე: F(X) = 5x 1 + 3x 2 → max შეზღუდვების მიხედვით:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
მოდელი დაწერილია სტანდარტული ფორმით. მოდით შემოვიტანოთ ბალანსის არაუარყოფითი ცვლადები x 3 , x 4 , x 5 , x 6 , რომლებსაც ვუმატებთ უტოლობის შეზღუდვების მარცხენა მხარეს. ჩვენ შევიყვანთ ყველა დამატებით ცვლადს ობიექტურ ფუნქციაში ნულის ტოლი კოეფიციენტებით:
მნიშვნელობის პირველ უტოლობაში (≤) შემოგვაქვს ძირითადი ცვლადი x 3 . მნიშვნელობის მე-2 უტოლობაში (≤) შემოგვაქვს ძირითადი ცვლადი x 4 . მესამე უტოლობაში შემოგვაქვს ძირითადი ცვლადი x 5 . მე-4 უტოლობაში - ძირითადი ცვლადი x 6. ჩვენ ვიღებთ მოდელის კანონიკურ ფორმას:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max
მაგალითი No2. იპოვნეთ სისტემის ორი საცნობარო გადაწყვეტა
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2
დეპუტატის დავალებები
გენერალური ZLP ე.წ <,=,>=)bi (i=1,n) (2) მოწოდებულია xj>
სიმეტრიული < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > კანონიკური შერეული.
min f(x) = -max(-f(x))
<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>
ობიექტური ფუნქციისა და ZLP-ის შეზღუდვების გეომეტრიული ინტერპრეტაცია. ZLP-ის გეომეტრიული ფორმულირება.
მოცემულია ამოცანა f=c1x1+c2x2-max (1).
a11x1+a12x2<=b1 }
am1x1 + am2x2<=bm}
x1>=0, x2>=0 (3)
ამოცანის გეგმა (x1,x2) არის წერტილი სიბრტყეზე. თითოეული უტოლობა-ჩვენ 2 წარმოდგენა. არის ნახევრად თვითმფრინავი. ნახევრად თვითმფრინავი არის ამოზნექილი ნაკრები. ამოზნექილისიმრავლეს უწოდებენ, რომელშიც სიმრავლეს ეკუთვნის აგრეთვე ამ სიმრავლის კუთვნილი სეგმენტის (x1 და x2) შემაერთებელი წერტილები. C-ma 2 წარმოადგენს ნახევრად სიბრტყეების კვეთას. გადაკვეთისას შეგიძლიათ მიიღოთ:
1) ამოზნექილი მრავალკუთხა დახურული უბანი.
2) ამოზნექილი ღია მრავალკუთხა ფართობი
3) ერთი წერტილი
4) ცარიელი ნაკრები
5) სხივი და სეგმენტი
ობიექტური ფუნქციის გეომეტრიული ინტერპრეტაცია:ფუნქცია 1 არის პარალელური სწორი ხაზების ოჯახი, რომელსაც ეწოდება დონის ხაზები (ობიექტური ფუნქციის მუდმივი მნიშვნელობის ხაზები). ფუნქციის ნაწილობრივი წარმოებულები x1 და x2-ის მიმართ გვიჩვენებს ღერძების კოორდინატების გასწვრივ ობიექტური ფუნქციის გაზრდის სიჩქარეს. გრადიენტის ვექტორიგვიჩვენებს ობიექტური ფუნქციის უსწრაფესი ზრდის მიმართულებას 1-3 ამოცანისთვის გრადიენტის ვექტორი = (c1;c2) ტოვებს წერტილს (0,0) და მიმართულია წერტილისკენ (c1;c2). გრადიენტის ვექტორი დონის ხაზების პერპენდიკულარულია. ნახევრად სიბრტყეების გადაკვეთას ჩვეულებრივ უწოდებენ დასაშვები ხსნარების ფართობი (ADD).
LP-ის მთავარი თეორემა. ZLP-ის ამოხსნის სქემატური დიაგრამა, რომელიც გამომდინარეობს ამ თეორემიდან.
თუ ZLP-ს აქვს გამოსავალი, მაშინ ობიექტური ფუნქცია აღწევს უკიდურეს მნიშვნელობას გეგმის პოლიედრონის ერთ-ერთ უკიდურეს წერტილში მაინც. თუ ობიექტური ფუნქცია აღწევს უკიდურეს მნიშვნელობას ერთზე მეტ უკიდურეს წერტილში, მაშინ იგი აღწევს ერთსა და იმავე მნიშვნელობას, რომელიც არის მათი ამოზნექილი წრფივი კომბინაცია, ნებისმიერ წერტილში. ZLP-ის ხელით გადაჭრისას მოსახერხებელია ცხრილის ჩანაწერის გამოყენება.
| BP | SP -Xm+1 -Xm+2 -Xn | |
| x1 | b1o | b11 b12 b1n-m |
| x2 | b2o | b21 b22 b2n-m |
| xm | ბმ | bm1 bm2 bmn-m |
| ვ | ბოუ | bo1 bo2 bon-m |
სიმპლექსის მეთოდის ალგორითმი.
1. პრობლემის მოდელის კანონიკურ ფორმამდე მიყვანა;
2. იპოვეთ საწყისი საცნობარო გეგმა;
3. დაწერეთ პრობლემა მარტივად. მაგიდა;
5. ახალ საცნობარო გეგმაზე გადასვლა, ახალ სიმპტომზე. მაგიდა. ახალ საცნობარო გეგმაზე გადასასვლელად საკმარისია ერთი ძირითადი ცვლადის ჩანაცვლება უფასოთ. საფუძველში შემავალი ცვლადი და შესაბამისი გარჩევადობის სვეტი განისაზღვრება f- რიგის უდიდესი აბსოლუტური უარყოფითი ელემენტით. ცვლადი, რომელიც გამორიცხავს საფუძვლიდან და შესაბამისი გადამწყვეტი ხაზი განისაზღვრება უმცირესი სიმპლექსის შეფარდებით, ე.ი. ერთეული სვეტის ელემენტების ურთიერთობა რეზოლუციის სვეტის შესაბამის ელემენტთან. სიმპლექსის თანაფარდობა არის არაუარყოფითი სიდიდე. განმსაზღვრელი მწკრივისა და განმსაზღვრელი სვეტის გადაკვეთაზე არის განმსაზღვრელი ელემენტი, რომლის მიმართაც მარტივი ტრანსფორმაცია ხორციელდება შემდეგნაირად. წესი: 1. დასაშვები სტრიქონის ელემენტები იყოფა დასაშვებ ელემენტად; 2. გამხსნელი სვეტის ელემენტები იყოფა გამხსნელ ელემენტად და ცვლის მათ ნიშანს საპირისპიროდ; 3. ცხრილის დარჩენილი ელემენტები ხელახლა დალაგებულია მართკუთხედის წესის მიხედვით:
ბიჯ ბის bkj=(bkj*bis-bij*bks)/bi
მეორე ორმაგობის თეორემა.
თუ ორმაგ პრობლემათაგან ერთს აქვს ოპტიმალური გეგმა, მაშინ მეორეც გადასაჭრელია, ე.ი. აქვს ოპტიკური გეგმა. ამ შემთხვევაში, ობიექტური ფუნქციების უკიდურესი მნიშვნელობები ემთხვევა (j=1-დან n-მდე) Σcjxj*= (i=1-დან m)Σbiyi* თუ ორიგინალშია. პრობლემა, ობიექტური ფუნქცია შეუზღუდავია გეგმების სიმრავლეზე, მაშინ ორმაგ პრობლემაში შეზღუდვების სისტემა არათანმიმდევრულია.
თეორემა TK მატრიცის რანგზე.
სატრანსპორტო ამოცანის A მატრიცის რანგი ერთით ნაკლებია განტოლებათა რიცხვზე: r(A)=m+n-1.
39. ZLP-ის საწყისი საცნობარო გეგმის აგების ალგორითმი.
საწყისი საცნობარო გეგმის მოსაძებნად შეგვიძლია შემოგთავაზოთ შემდეგი ალგორითმი:
1. დაწერეთ ამოცანა იორდანიის ცხრილის სახით ისე, რომ თავისუფალი ტერმინების სვეტის ყველა ელემენტი იყოს არაუარყოფითი, ე.ი. უტოლობა aio>=0 (i=1,m) დაკმაყოფილდა. ის განტოლებები, რომლებშიც თავისუფალი წევრები უარყოფითია, ჯერ მრავლდება -1-ზე.
| -x1….. -xn | ||
| 0= | a1o | a11…. a1n |
| ….. | ….. | ……………………….. |
| 0= | ამო | am1…..amn |
| f= | -c1…. -გნ |
შეცვალეთ ცხრილი იორდანიის აღმოფხვრის საფეხურების გამოყენებით, შეცვალეთ ნულები მარცხენა სვეტში შესაბამისი x-ით. ამავდროულად, ყოველ ნაბიჯზე დასაშვები შეიძლება შეირჩესნებისმიერი სვეტი, რომელიც შეიცავს მინიმუმ ერთ დადებით ელემენტს. განმსაზღვრელი მწკრივი განისაზღვრება განმსაზღვრელი სვეტის შესაბამის დადებით ელემენტებთან თავისუფალი ტერმინების შეფარდების უმცირესობით. თუ აღმოფხვრის პროცესში შეგვხვდება 0-რიგი, რომლის ყველა ელემენტი არის ნული, ხოლო თავისუფალი წევრი არის არანულოვანი, მაშინ შეზღუდვის განტოლებათა სისტემას არ აქვს ამონახსნები. თუ შევხვდებით 0-რიგს, რომელშიც თავისუფალი წევრის გარდა სხვა დადებითი ელემენტები არ არის, მაშინ შემზღუდველ განტოლებათა სისტემას არ გააჩნია არაუარყოფითი ამონახსნები ერთობლივი, შემდეგ გარკვეული რაოდენობის ნაბიჯების შემდეგ მარცხენა სვეტის ყველა ნული შეიცვლება x-ით და ამით მიიღება გარკვეული საფუძველი და, შესაბამისად, შესაბამისი საცნობარო გეგმა.
40. ZLP-ის ოპტიმალური საცნობარო გეგმის აგების ალგორითმი.
ჰოს თავდაპირველი მხარდაჭერის გეგმა განიხილება ოპტიმალურად.
თუ f- მწკრივში არ არის უარყოფითი ელემენტები (თავისუფალ ტერმინს არ ჩავთვლით), -გეგმა ოპტიმალურია. თუ ასევე არ არის ნულოვანი ელემენტები f- მწკრივში, მაშინ არსებობს მხოლოდ ერთი ოპტიმალური გეგმა; თუ ელემენტებს შორის არის მინიმუმ ერთი ნული, მაშინ არის ოპტიმალური გეგმების უსასრულო რაოდენობა. თუ f- მწკრივში არის მინიმუმ ერთი უარყოფითი ელემენტი, ხოლო შესაბამის სვეტში არ არის დადებითი ელემენტები, მაშინ ობიექტური ფუნქცია არ არის შეზღუდული შესაძლებელ რეგიონში. პრობლემა არ არის მოსაგვარებელი. თუ f- მწკრივში არის მინიმუმ ერთი უარყოფითი ელემენტი და ასეთი ელემენტის თითოეულ სვეტში არის მინიმუმ ერთი დადებითი ელემენტი, მაშინ შეგიძლიათ გადახვიდეთ ახალ საცნობარო გეგმაზე, რომელიც უფრო ახლოს არის ოპტიმალურთან. ამისათვის, f- მწკრივში უარყოფითი ელემენტის მქონე სვეტი აღებულია როგორც დასაშვები; ისინი განსაზღვრავენ გადაწყვეტის სტრიქონს მინიმალური სიმპლექსის მიმართებიდან და ასრულებენ ჯორდანის ელიმინაციის საფეხურს. შედეგად მიღებული საცნობარო გეგმა კვლავ განიხილება ოპტიმალურად. ეს მეორდება მანამ, სანამ არ მოიძებნება ოპტიმალური საცნობარო გეგმა ან არ დადგინდება პრობლემის გადაუჭრელობა.
გომორის მეთოდის ალგორითმი.
1. სიმპლექსის მეთოდის გამოყენებით მოიძებნება პრობლემის ოპტიმალური გეგმა. თუ ოპტიმალური გეგმის ყველა კომპონენტი მთელი რიცხვია, მაშინ ის ოპტიმალურია. წინააღმდეგ შემთხვევაში, გადადით მე-2 ნაბიჯზე
2. არამთლიან კომპონენტებს შორის უნდა აირჩიოთ ის, რომლის წილადი ნაწილი ყველაზე დიდია და სიმპლექსის ცხრილის შესაბამისი ხაზის გამოყენებით ჩამოაყალიბოთ სწორი წყვეტა ფორმულის გამოყენებით.
(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)
3. ფორმულირებული უტოლობა გადააქციეთ ეკვივალენტურ ნულოვან ტოლობაში და ჩართოთ იგი სიმპლექს ცხრილში არამთლიანი ოპტიმალური გეგმით.
4. მიღებული გაფართოებული პრობლემა წყდება სიმპლექსის მეთოდით. თუ მიღებული გეგმა არ არის მთელი რიცხვი, გადადით მე-2 საფეხურზე.
თუ ამოხსნის პროცესში ჩნდება წრფე არამთლიანი თავისუფალი წევრით და სხვა მთელი რიცხვითი კოეფიციენტებით, მაშინ შესაბამის განტოლებას არ აქვს ამონახსნი მთელ რიცხვებში. ამ შემთხვევაში, თავდაპირველი პრობლემა მთელ რიცხვებშიც გადაუჭრელია. მისი დახმარებით მიზანშეწონილია მცირე პრობლემების მოგვარება, რადგან... ურთიერთქმედებების რაოდენობა შეიძლება იყოს ძალიან დიდი.
ZLP-ის აღნიშვნის სხვადასხვა ფორმები (ზოგადი, კანონიკური, სიმეტრიული)
დეპუტატის დავალებები: ოპტიმალური გეგმის განსაზღვრა, გამომუშავების ოპტიმალური მოცულობის განსაზღვრა, კულტურების ოპტიმალური კომბინაციის განსაზღვრა, აქტივების ოპტიმალური პაკეტის ფორმირება, ბანკის მოგების მაქსიმიზაცია და ა.შ.
გენერალური ZLP ე.წ მაქსიმიზაციის (მინიმიზაციის) პრობლემაწრფივი ფუნქცია f=Σcj*xj-max(min) (1) წრფივი შეზღუდვების ქვეშ ∑aij *xj(=<,=,>=)bi (i=1,n) (2) მოწოდებულია xj>=0(j=1,n1), xj-თვითნებური (j=n1+1,n)(3) სადაც cj,aij, ბი-მუდმივებია რიცხვები .
სიმეტრიული ZLP-ის ჩაწერის ფორმას ეწოდება ფუნქციის (1) მაქსიმიზაციის პრობლემა ხელმოწერილი უტოლობების ხაზოვანი შეზღუდვების ქვეშ.< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >ან = და არაუარყოფითი ცვლადები. კანონიკური ZLP-ის ჩაწერის ფორმას ეწოდება მაქსიმალური ფუნქციის (1) პრობლემა ტოლობებისა და არაუარყოფითი ცვლადების წრფივი შეზღუდვების ქვეშ. ნებისმიერ სხვა ფორმას უწოდებენ შერეული.
min f(x) = -max(-f(x))
უტოლობის გადაქცევა განტოლებად და პირიქით ხდება ლემის საფუძველზე: უტოლობის ყოველი ამონახსნი x1...xn a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) და პირიქით. მე-6 განტოლების x1…xn,xn+1 და მე-7 უტოლობის ყოველი ამონახსნი შეესაბამება x1…xn უტოლობის 5 ამონახს.
უკანა სიმ ფორმიდან უკანა კანონიკურ ფორმაზე გადასასვლელად, თქვენ უნდა შეიყვანოთ ბალანსის (გათანაბრების) ცვლადები.ეს ეფუძნება უტოლობის თეორემას: ნებისმიერი უტოლობა შეიძლება წარმოდგენილი იყოს როგორც განტოლება ან მარტივი უტოლობა.