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

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

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

იღებს მაქსიმალურ ან მინიმალურ მნიშვნელობას შეზღუდვების პირობებში

(8.2)

(8.3)

- მთელი რიცხვები. (8.4)

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

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

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

დაჭერის მეთოდები. გომორის მეთოდი

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

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

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

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

ამონახსნების თავდაპირველ პოლიედრონში და შესაბამისად ამ პოლიედრონით მიღებული ოპტიმალური ამონახსნები იქნება მთელი რიცხვი (სურ. 8.1).

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

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

(8.5)

ასე რომ (8.1)-(8.3) ამოცანის ოპტიმალური გადაწყვეტა არის i, რომელშიც, მაგალითად, β; - არამთლიანი კომპონენტი. ამ შემთხვევაში შეიძლება დადასტურდეს, რომ უთანასწორობა ჩამოყალიბდა მე-სისტემის განტოლებამდე (8.5), აქვს რეგულარული წყვეტის ყველა თვისება.

გომორის მეთოდით მთელი წრფივი პროგრამირების ამოცანის (8.1)-(8.4) ამოსახსნელად გამოიყენება შემდეგი ალგორითმი.

• 1. სიმპლექსის მეთოდის გამოყენებით ამოხსენით ამოცანა (8.1)-(8.3) მთელი რიცხვის პირობის გათვალისწინების გარეშე. თუ ოპტიმალური გეგმის ყველა კომპონენტი მთელი რიცხვია, მაშინ ის ოპტიმალურია მთელი რიცხვითი პროგრამირების ამოცანისთვის (8.1)-(8.4). თუ პირველი ამოცანა (8.1)-(8.3) გადაუჭრელია (ანუ მას არ აქვს საბოლოო ოპტიმუმი ან მისი პირობები წინააღმდეგობრივია), მაშინ მეორე ამოცანაც (8.1)-(8.4) გადაუჭრელია.
• 2. თუ ოპტიმალური ამონახსნის კომპონენტებს შორის არის არა მთელი რიცხვები, მაშინ შეარჩიეთ კომპონენტი, რომელსაც აქვს უდიდესი მთელი ნაწილი და სისტემის შესაბამისი განტოლების გამოყენებით (8.5) ჩამოაყალიბეთ სწორი წყვეტა (8.6).
• 3. დამატებითი არაუარყოფითი მთელი ცვლადის შემოტანით უტოლობა (8.6) გარდაქმნას ეკვივალენტურ განტოლებად და ჩართეთ შეზღუდვების სისტემაში (8.2).
• 4. მიღებული გაფართოებული ამოცანის ამოხსნა სიმპლექსის მეთოდით. თუ ნაპოვნი ოპტიმალური გეგმა არის მთელი რიცხვი, მაშინ მოგვარებულია მთელი რიცხვის პროგრამირების პრობლემა (8.1)–(8.4). წინააღმდეგ შემთხვევაში, დაუბრუნდით ალგორითმის მე-2 საფეხურს.

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

1 უტოლობაში (8.6) არის სიმბოლო ( ), რაც ნიშნავს რიცხვის წილად ნაწილს. რიცხვის მთელი ნაწილი aარის უდიდესი მთელი რიცხვი, რომელიც არ აღემატება ა, რიცხვის წილადი ნაწილი– რიცხვი (ა), ამ რიცხვსა და მის მთელ ნაწილს შორის სხვაობის ტოლი, ე.ი. (a) = a-[b].

მაგალითად, for (შენიშვნა, ზუსტად -3, არა -2) და

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

8.1. მარცვლეულის დასახარისხებელი ტექნიკის შესაძენად ფერმერი გამოყოფს 34 დენს. ერთეულები აღჭურვილობა უნდა განთავსდეს არაუმეტეს 60 კვადრატულ მეტრ ფართობზე. მ ფერმერს შეუძლია შეუკვეთოს ორი სახის აღჭურვილობა: ნაკლებად ძლიერი მანქანები, როგორიცაა აღირს 3 დენ. ერთეულები, რომლებიც საჭიროებენ საწარმოო ფართობს 3 კვ. მ (პასების ჩათვლით) და პროდუქტიულობა თითო ცვლაში 2 ტონა მარცვლეული და უფრო ძლიერი მანქანები, როგორიცაა INღირს 4 დენ. ერთეულები, რომლებიც იკავებს 5 კვ. მ, ხოლო პროდუქტიულობა ცვლაზე 3 ტონა მაღალი ხარისხის მარცვლეული.

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

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

(!!!8.8)

შეზღუდვებით:

(8.2)

- მთელი რიცხვები. (8.4)

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

(8.5)

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

ნახ. 8.2 OKLM- პრობლემის შესაძლო გადაწყვეტის არეალი (8.D)–(8.3"), შემოიფარგლება სწორი ხაზებით (1), (2), (3) და კოორდინატთა ღერძებით; ლ(2/3; 8) – ამოცანის ოპტიმალური, მაგრამ არამთლიანი ამოხსნის წერტილი (8.1")–(8.3"); (4) – სწორი ხაზი, რომელიც წყვეტს ამ არამთლიანი ამონახსნის; OKNM- გაფართოებული პრობლემის შესაძლო გადაწყვეტილებების ფართობი (8.1") - (8.3"), (8.6"); N( 2; 7) – ოპტიმალური მთელი რიცხვის ამოხსნის წერტილი.

ნაბიჯი I. ძირითადი ცვლადები არასაბაზისო ცვლადები

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

ჩემი. შესაბამისი წრფივი ფუნქციის მნიშვნელობა

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

მიიღეთ შეზღუდვების სისტემა, რომელიც ეფუძნება მინიმალური შესაბამისი ურთიერთობების პირობას:

იმათ. ამომხსნელი (მონიშნული) განტოლება მესამეა. ზე X. 2 = 8 ამ განტოლებაში X- = 0, და ცვლადი გადადის არასაბაზისოზე X 5.

ნაბიჯი II.ძირითადი ცვლადები X 2, X 3, X 4.

მცირე ცვლადები.g, xy

გარდაქმნების შემდეგ ვიღებთ

გადაიყვანეთ მთავარ ცვლადზე ხოლო არამთავარებში x4.

III ნაბიჯი.ძირითადი ცვლადები x, X 2, X 3.

არამთავარი ცვლადები x4, x5.

გარდაქმნების შემდეგ ვიღებთ

ძირითადი გადაწყვეტა X., ოპტიმალური ამოცანისთვის (8.1")–(8.3") (), ვინაიდან წრფივი ფუნქციის გამოხატულებაში

არ არსებობს არაძირითადი ცვლადები დადებითი კოეფიციენტებით.

თუმცა, გამოსავალი X 3 არ აკმაყოფილებს მთელი რიცხვის პირობას (8.4") პირველი განტოლების გამოყენებით x ცვლადი, რომელიც იღებს არამთლიანი მნიშვნელობას ოპტიმალურ ამონახსნში (2/3), ჩვენ ვქმნით დამატებით შეზღუდვას (8.6):

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

ვინაიდან წილადი ნაწილები ,

, ვწერთ ბოლო უტოლობას

(8.6")

დამატებითი მთელი რიცხვი x6 ცვლადის შემოღებით ≥ 0, ჩვენ ვიღებთ განტოლებას უტოლობის ექვივალენტური (8.6")

(8.7")

განტოლება (8.7") უნდა იყოს შეტანილი თავდაპირველი კანონიკური ამოცანის შეზღუდვების სისტემაში (8.5") და შემდეგ გაიმეოროთ პრობლემის გადაჭრის პროცესი მარტივი მეთოდის გამოყენებით გაფართოებულ პრობლემასთან მიმართებაში. ამ შემთხვევაში საფეხურების (იტერაციების) რაოდენობის შესამცირებლად რეკომენდებულია პრობლემის გადაჭრის ბოლო საფეხურზე (მთლიანი პირობის გარეშე) მიღებულ სისტემაში დამატებითი განტოლების (8.7") შეტანა.

IV ნაბიჯი.ძირითადი ცვლადები xვ X 2, x3, χβ.

არამთავარი ცვლადები x4, x5.

ძირითადი გამოსავალი დაუშვებელია

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

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

V ნაბიჯი.ძირითადი ცვლადებია x, x2, x3, x5.

არამთავარი ცვლადები x4, x6.

ჩვენ ვიღებთ ტრანსფორმაციების შემდეგ

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

ასე რომ, Zmax = 25 ოპტიმალური მთელი რიცხვის ამოხსნისთვის X* = X 5 = (2; 7; 19; 0; 1; 0), ე.ი. ცვლაში 25 ტონა მაღალი ხარისხის მარცვლეულის მაქსიმალური პროდუქტიულობის მიღება შესაძლებელია L ტიპის 2 და 7 ტიპის მანქანის შეძენით. INამავდროულად, შენობის დაუსახლებელი ფართი იქნება 19 კვადრატული მეტრი. მ, გამოყოფილი სახსრების ნაშთი არის ნული, შესყიდვის რეზერვი არის 1 ტიპის მანქანა IN(მეექვსე კომპონენტს აზრი არ აქვს).

კომენტარი. Ox, x2 სიბრტყეზე (იხ. სურ. 8.2) კვეთის (8.6") ​​გეომეტრიული ინტერპრეტაციისთვის აუცილებელია მასში შემავალი ცვლადები. X 4 და X-გამოხატეთ x და x2 ცვლადების მეშვეობით. ვიღებთ (იხ. შეზღუდვების სისტემის მე-2 და მე-3 განტოლებები (8.5"))

• (იხ. ამოჭრილი ხაზი (4) ნახ. 8.2-ზე).
• 8.2. მორები საკმაოდ დიდია 3 მ სიგრძის მორები უნდა დაიჭრას ორ ტიპად: 1.2 და 0.9 მ სიგრძისა და მინიმუმ 50 და 81 ცალი თითოეული ტიპის სამუშაო ნაწილიდან. შესაბამისად. თითოეული მორი შეიძლება დაიჭრას მითითებულ ნაჭრებად რამდენიმე გზით: 1) 2 ნაწილად, მაგრამ 1,2 მ; 2) 1 ცალი 1,2 მ და 2 ცალი 0,9 მ; 3) 3 ცალი 0,9 მ თითოეული მეთოდით იპოვეთ მორების რაოდენობა ისე, რომ ნებისმიერი ტიპის ცალი მიიღება მორების უმცირესი რაოდენობით.

გამოსავალი.მოდით აღვნიშნოთ X() x2, x3 მორების რაოდენობა, 1, 2 და 3 მეთოდის გამოყენებით, შესაბამისად. მათგან შეგიძლიათ მიიღოთ 2xj +x2 ბლანკები თითო 1,2 მ და 2x x +3x2 ბლანკები თითო 0,9 მ. მოდით აღვნიშნოთ მორების საერთო რაოდენობა ზ.შემდეგ ფორმას მიიღებს პრობლემის მათემატიკური მოდელი

შეზღუდვებით:

დამატებითი ცვლადების შემოტანით

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

(8.5")

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

III ნაბიჯი.ძირითადი ცვლადები xვ X 2.

არაძირითადი ცვლადები Xზე Xა , X 5.

ანუ ოპტიმალური გადაწყვეტით

აღმოჩნდა, რომ ოპტიმალური გადაწყვეტის ორი კომპონენტი არ აკმაყოფილებს მთელი რიცხვის პირობას (8.4") და კომპონენტს აქვს უდიდესი მთელი რიცხვი X 2. ∏-ის შესაბამისად. 2 ალგორითმი მთელი რიცხვითი პროგრამირების პრობლემის გადასაჭრელად (იხ. გვ. 166) ამ ცვლადის შემცველი მეორე განტოლების გამოყენებით X 2, ჩვენ ვქმნით დამატებით შეზღუდვას (8.6):

ვიპოვოთ წილადი ნაწილები

და ჩაწერეთ ბოლო უტოლობა ფორმაში

(8.6")

დამატებითი ცვლადის შემოღებით ვიღებთ

განტოლება უტოლობის ექვივალენტური (8.6"):

(8.7")

მოდით გამოვხატოთ (8.7") დამატებითი ცვლადი x6 და მიღებული განტოლება შევიტანოთ შეზღუდვების სისტემაში, რომელიც გვქონდა ამოცანის ამოხსნის ბოლო, III, საფეხურზე (8.1") - (8.3") (მთლიანი პირობის გარეშე. ).

IV ნაბიჯი. ძირითადი ცვლადები X{, Xზე X 6.

არაძირითადი ცვლადები X 3, x4, X 5.

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

V ნაბიჯი. ძირითადი ცვლადები x); X 2, x3.

არამთავარი ცვლადები x4, x5, xb.

ანუ ოპტიმალური გადაწყვეტით

გაფართოებული პრობლემის შედეგად მიღებული ოპტიმალური გადაწყვეტა (8.1")–(8.3"), (8.6") ​​ისევ არ აკმაყოფილებს მთელი რიცხვის პირობას (8.4"). პირველი განტოლების მიხედვით Xj ცვლადთან არა მთელი მნიშვნელობის მიღება ოპტიმალურად

გამოსავალი (), ჩვენ ვტოვებთ მეორე დამატებით ზღვარს

კითხვა (8.6):

რომელიც ჩვენ გვახსოვს

დამატებითი ცვლადის გამოყენება

ჩვენ ვამცირებთ ამ უტოლობას ეკვივალენტურ განტოლებამდე, რომელსაც ჩავრთავთ გაფართოებული ამოცანის ამოხსნის ბოლო V საფეხურზე მიღებულ შეზღუდვების სისტემაში (8.G")–(8.3"), (8.6") ​​გამოყენებით სიმპლექსის მეთოდი.

VI ნაბიჯი. ძირითადი ცვლადები xვ X 2, Xზე Xთ

არაძირითადი ცვლადები X 4, X-, x 6.

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

VII ნაბიჯი. ძირითადი ცვლადები xვ X t x3, Xგ

არაძირითადი ცვლადები xვ X 6, Xთ

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

უნდა აღინიშნოს, რომ Z წრფივი ფუნქციის გამოსახულებაში არ არის უმნიშვნელო ცვლადები Xდ) და X 6. ეს ნიშნავს, რომ, ზოგადად რომ ვთქვათ, არსებობს ოპტიმალური ამონახსნების უსასრულო ნაკრები (ნებისმიერი, არა აუცილებლად მთელი რიცხვი), რომლისთვისაც Z" = Zmjn = 46. ეს ამონახსნები მიიღება არამთავარი ცვლადის მნიშვნელობისთვის. X 7 (ჩართულია Z-ის გამოხატულებაში), ტოლია ნულის (ე.ი. როცა X 7 = 0) და ზე ნებისმიერიარასაბაზისო ცვლადების მნიშვნელობები x5 და X 6 (არ შედის Z-ის გამოთქმაში), რომლის მიღების უფლებას შეზღუდვების სისტემა: 0<лг5 X 5 ≤ 1 და 0< x(i ≤ 1. მაგრამ მთელი რიცხვის მდგომარეობის გამო, ცვლადები X-და X(> შეუძლია მიიღოს მხოლოდ 0 ან 1 მნიშვნელობები. ამიტომ პრობლემას ექნება ოთხი მთელი რიცხვი ოპტიმალური ამონახსნები, როდესაც X.და *6 ნებისმიერ კომბინაციაში მიიღეთ მნიშვნელობები 0 ან 1 და X 7 = 0. ამ მნიშვნელობების VII საფეხურზე შეზღუდვების სისტემაში ჩანაცვლებით, ჩვენ ვპოულობთ ამ ოპტიმალურ გადაწყვეტილებებს:

ალტერნატიული ოპტიმალური მთელი რიცხვების გადაწყვეტილებების არსებობა შესაძლებელს ხდის მათგან ერთ-ერთის არჩევას, დამატებითი კრიტერიუმებით ხელმძღვანელობით, რომლებიც არ არის გათვალისწინებული პრობლემის მათემატიკურ მოდელში. მაგალითად, ამ პრობლემის პირობებიდან გამომდინარეობს, რომ მორების დამუშავება არ წარმოქმნის ნარჩენებს მხოლოდ მე-3 მეთოდის გამოყენებით, ამიტომ, ოთხი ოპტიმალური გადაწყვეტილებიდან ერთ-ერთის არჩევისას, ბუნებრივია უპირატესობა მიენიჭოს გამოსავალს. X^ 3 რომელშიც არის ჟურნალების მაქსიმალური რაოდენობა ( X 2 = 41) ხერხდება ნარჩენების გარეშე.

ასე რომ, Zmin=46 ოპტიმალური მთელი რიცხვების ამონახსნებისთვის (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). ოპტიმალური ამონახსნების ჩაწერისას დავტოვეთ მხოლოდ პირველი სამი კომპონენტი, რომლებიც გამოვხატავთ მოჭრილი ლოგების რაოდენობას, შესაბამისად, 1-ლი, მე-2 და მე-3 მეთოდების მიხედვით და გამოვრიცხეთ ბოლო ოთხი კომპონენტი, რომლებსაც სემანტიკური მნიშვნელობა არ აქვთ.

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

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

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

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

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

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

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

იპოვეთ ობიექტური ფუნქციის მაქსიმუმი (წრფივი ფორმა)

შეზღუდვების სისტემის ქვეშ

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

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

გომორის მეთოდი მთელი რიცხვითი პროგრამირების ამოცანების გადაჭრისთვის

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

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

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

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

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

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

.

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

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

(ზე x3 ),

(ზე x4 ).

ხოლო წილადი ნაწილების პოვნის ზოგადი წესი ასეთია: ნამდვილი რიცხვის მთელი ნაწილით აუდიდეს მთელ რიცხვს ეწოდება [ ა] , არ აღემატება ა; რეალური რიცხვის წილადი ნაწილი აგანსხვავებას უწოდებენ {ა} = ა - [ა] თავად ნომერი ადა მისი მთელი ნაწილი [ ა] .

.

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

.

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

შეზღუდვების სისტემის ქვეშ

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

დამატებითი უცნობები x3 და x4 ავიღოთ როგორც ძირითადი. მოდით გამოვხატოთ ძირითადი უცნობები და მიზნის ფუნქცია არაძირითადი ცვლადების მიხედვით:

მოდით შევქმნათ სიმპლექსის ცხრილი კოეფიციენტებიდან:

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

ცხრილი 3
ძირითადი უცნობები	უფასო წევრები	უფასო უცნობები		დამხმარე კოეფიციენტები
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
თან	65/7	10/7	1/7	1/2

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

ცხრილის საფუძველზე პირველი განტოლება დაიწერება შემდეგნაირად:

.

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

ან დამატებითი ცვლადის შემოღებით,

.

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

ცხრილი 4
ძირითადი უცნობები	უფასო წევრები	უფასო უცნობები		დამხმარე კოეფიციენტები
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
თან	65/7	10/7	1/7	1/2

ჩვენ ვასრულებთ მარტივი მეთოდის საფეხურს და ვიღებთ ცხრილს:

ცხრილი 5
ძირითადი უცნობები	უფასო წევრები	უფასო უცნობები		დამხმარე კოეფიციენტები
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
თან	55/6	4/3	1/6	-1/7

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

.

შევქმნათ შემდეგი ცხრილი:

ცხრილი 6
ძირითადი უცნობები	უფასო წევრები	უფასო უცნობები		დამხმარე კოეფიციენტები
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
თან	55/6	4/3	1/6	-1/7

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

ცხრილი 7
ძირითადი უცნობები	უფასო წევრები	უფასო უცნობები		დამხმარე კოეფიციენტები
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
თან	9	6/5	1/5	-1/6

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

,

ხოლო მიზნის ფუნქციის მაქსიმუმი არის 9.

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

შეზღუდვების სისტემის ქვეშ

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

.

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

გადასაჭრელი ამოცანების სიაში შედის 1 ამოცანა:

გამეორება 1.

Ნაბიჯი 1.Გამოყენებით სიმპლექსის მეთოდიპირველი პრობლემის გადაწყვეტა იქნა მიღებული:

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

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

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

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

მოდით X* = (x1, x2, …, xm, …, xn) იყოს ოპტიმალური გეგმა, რომელიც ნაპოვნია სიმპლექსის მეთოდით, სადაც საფუძველია ვექტორები A1, A2,…, Am. მოდით xi იყოს წილადი რიცხვი (რიცხვი B სვეტში i-ე მწკრივში). მაშინ შესაძლებელია, რომ i-ე სტრიქონში:

1. ყველა xij არის მთელი რიცხვი, ეს ნიშნავს, რომ პრობლემას არ აქვს მთელი რიცხვის ამოხსნა

2. ზოგიერთი xij არის წილადი

[xi] და [xij] იყოს xi და хij რიცხვების მთელი ნაწილები, ხოლო (xi) და (хij) წილადი ნაწილები.

ავღნიშნოთ qi = (хi) და qij = (хij) და შევადგინოთ განსხვავებები.

(qi1Х1+ qi1Х2+…+ qi1Хn)- qi ≥0

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

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

თქვენ ასევე შეგიძლიათ იპოვოთ თქვენთვის საინტერესო ინფორმაცია სამეცნიერო საძიებო სისტემაში Otvety.Online. გამოიყენეთ საძიებო ფორმა:

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

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

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

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

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

მაქსიმიზაცია

პირობებში

x j≥ 0, x j - მთლიანი.

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

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

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

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

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

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

მთელი რიცხვითი პროგრამირების პრობლემების გადაჭრის რამდენიმე მეთოდი არსებობს. Ყველაზე ცნობილი გომორის მეთოდი, სიმპლექსის მეთოდის გამოყენებაზე დაყრდნობით.

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

Მაგალითად: 5 / 3 ≡ 2 / 3 , იმიტომ 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , იმიტომ - 1 / 3 - 2 / 3 = 1.

ყველა მთელი რიცხვი თანმიმდევრულია ერთმანეთთან და თანმიმდევრულია ნულთან. არამთლიანი ელემენტები შეიძლება წარმოდგენილი იყოს რიცხვის მთელი და წილადი ნაწილების ჯამის სახით ა = [ა ] + {ა ). კვადრატული ფრჩხილები ნიშნავს მათში ჩასმული რიცხვის მთელი ნაწილის აღებას, ხვეული ფრჩხილები ნიშნავს რიცხვის წილადი ნაწილის აღებას.

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

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

მაგალითად, ამისთვის ა = 2 1 / 3 [ა ]= 2 (ა) = 1 / 3

ამისთვის = - 2 1 / 3 [ა ]= -3 (ა) = 2 / 3

რიცხვების თანხვედრის თვისებები:

1. თუ ა ≡ ბ , ეს ( ა } = {ბ }.

2. {ა +ბ } = {ა } + {ბ }.

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

na ≡ {na } ≡ ნ {ა }.

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

ბრინჯი. 13. გომორის ათვლის მეთოდი

მაგალითიმთელი რიცხვის პროგრამირების პრობლემის გადაჭრა. ახალი საწარმოო უბნისთვის აღჭურვილობის შესაძენად გამოიყო 20 ფულადი ერთეული. მოწყობილობა უნდა განთავსდეს არაუმეტეს 38 მ2 ფართობზე. საწარმოს შეუძლია შეუკვეთოს ორი ტიპის აღჭურვილობა: უფრო მძლავრი ტიპის A მანქანები, რომლის ღირებულებაა 5 ფულადი ერთეული, რომელიც მოითხოვს საწარმოო ფართობს 8 მ 2 (გადასასვლელების ჩათვლით) და უზრუნველყოფს 7 ათასი ერთეული წარმოების პროდუქტიულობას ცვლაში; B ტიპის ნაკლებად მძლავრი მანქანები ღირს 2 ფულადი ერთეული, იკავებს 4 მ 2 ფართობს და აწარმოებს 3 ათას ერთეულ პროდუქციას ცვლაში.

მოდით აღვნიშნოთ X 1 ნომერი შეძენილი მანქანები A და შემდეგ X 2 - შეძენილი მანქანების რაოდენობა B, ვიღებთ პრობლემის მათემატიკურ პირობებს:

მაქსიმიზაცია 7x 1 + 3x 2 → მაქს

პირობებში: 5x 1 + 2x 2 ≤ 20

8x 1 + 4x 2 ≤ 38

x 1, x 2 ≥ 0 (მთლიანი რიცხვები).

დამატებითი ცვლადების x 3 და x 4 დახმარებით, თავდაპირველი უტოლობები გარდაიქმნება განტოლებად (დაყვანილი კანონიკურ ფორმამდე):

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

თუ ძირითადი ცვლადები x 1 და x 2 არის მთელი რიცხვები, მაშინ განტოლებებიდან დაუყოვნებლივ გამომდინარეობს, რომ x 3 და x 4 ცვლადებს შეუძლიათ მხოლოდ მთელი რიცხვების აღება.

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

სიმპლექსის ცხრილი ასე გამოიყურება:

საფუძველი	თან	Გეგმა					θ
X 1	X 2	X 3	X 4
X 1 → X 3							20/5=4 წთ
X 4							38/8=4,75
f(x) = 0	-7	-3
X 1				2/5	1/5		4:2/5=10
X 2 →X 4				4/5	-8/5		6:4/5=7,5 წთ
f(x) =28		-1/5	7/5
X 1						-1/2
X 2		7,5			-2	5/4
f(x) =29.5				1/4

ოპტიმალურ გეგმაში X 1 = 1, X 2 = 7.5; ობიექტური ფუნქციის მაქსიმუმია 29.5. ამრიგად, აუცილებელია შეიძინოს A ტიპის ერთი მანქანა და B ტიპის 7 მანქანა (არ არის საკმარისი ფული ან ადგილი 8 მანქანისთვის), მაშინ წარმოების მოცულობა იქნება f(x) = 7 × 1 + 3 × 7. = 28 ათასი ერთეული წარმოება.

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

7.5 = X 2 – 2X 3 + 1.25X 4.

X 2 = 7,5 + 2X 3 – 1,25X 4.

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

ვინაიდან X 2 არის მთელი რიცხვი, განტოლების მარჯვენა მხარეს გამოსახული ასევე მთელი რიცხვია; ამრიგად, ამ განტოლების მარჯვენა მხარის მნიშვნელობა ნულის ტოლია:

7,5 + 2Х 3 – 1,25Х 4 ≡ 0,

–2Х 3 + 1,25Х 4 ≡ 7,5.

კონგრუენტობის ზემოაღნიშნული თვისებების გათვალისწინებით და ასევე იმ ფაქტის გათვალისწინებით, რომ X 3 და X 4 არის მთელი რიცხვები, ეს გამოხატულება შეიძლება გარდაიქმნას შემდეგში:

(-2)X 3 + (1.25)X 4 ≡ {7,5} ;

აქედან ვიღებთ:

0.25X 4 ≡ 0,5.

ვინაიდან X 4 არის არაუარყოფითი მთელი რიცხვი, გვაქვს:

0.25X 4 = 0.5, ან 1.5, ან 2.5, ...;

აქედან გამომდინარე,

0,25X 4 ≥ 0,5.

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

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

0,25x 4 – x 5 = 0,5.

ამოხსნის პროცესის გამეორებით მარტივი მეთოდის გამოყენებით შეზღუდვების გაფართოებულ სისტემასთან მიმართებაში, ვიღებთ ახალ ოპტიმალურ გეგმას, რომელშიც საფუძველში შემავალი ცვლადების მნიშვნელობები უდრის: X 1 = 2; X 2 = 5; X 4 = 2 (დარჩენილი თავისუფალი ტერიტორია).

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

პრაქტიკული გაკვეთილი

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

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

განვიხილოთ მოდელი

შეზღუდვების ქვეშ

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

H j ≤ X j ≤ V j ; j=1,2,…,k,…,n.

ჩვეულებრივ ჰჯ = 0, მაგრამ ეს პირობა არ არის აუცილებელი. პრობლემა მოგვარებულია სიმპლექსის მეთოდით. თუ Xk იღებს წილადის მნიშვნელობებს, ჩვენ გვჯერა, რომ პრობლემის ოპტიმალური გადაწყვეტა დააკმაყოფილებს ხაზოვან შეზღუდვას X k ≤ D k , ან ხაზოვანი შეზღუდვა X k ≤ D k + 1 , სად დკ =[Xk ] – უახლოესი მთელი რიცხვი მნიშვნელობიდან ქვემოთ Xk ; D k + 1 – უახლოესი მთელი რიცხვი ზემოთ Xk . სადაც H j ≤ D k ≤ V j – 1 . შემდეგ აუცილებელია ხაზოვანი პროგრამირების რამდენიმე ამოცანის გადაჭრა სიმპლექსის მეთოდით:

ა.

IN.

ჩვენ ვიღებთ განმეორებით პროცესს, რომელიც წარმოდგენილია ხის სახით, რომლის ზედა ნაწილი შეესაბამება თავდაპირველი ამოცანის ამოხსნას და მასთან დაკავშირებული ორი ტოტი არის ამონახსნები A და B წრფივი პროგრამირების ამოცანების წყვილისთვის. მიღებული მნიშვნელობები ობიექტური ფუნქციები შეიძლება იყოს ორიგინალური ამოცანის ობიექტური ფუნქციის მნიშვნელობაზე ნაკლები ან ტოლი f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . მიღებული ორი ახალი ტოტის წვეროდან თითოეულს შეიძლება ჰქონდეს საკუთარი შემდგომი ტოტები.

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

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

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

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

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

თუ შერჩეული დავალება იწვევს შესვენებას (ჩიხს) ან ფუნქციის მნიშვნელობა ნაკლებია, ვიდრე დავალება B.1-ში f(X) A.4< f(X)­ В,1 ., შემდეგ ხდება B.1 დავალების დაბრუნება და ახალი განშტოება.

სურ. 14. ფილიალების და შეკრული ალგორითმის ნაკადის სქემა

ბრინჯი. 15. ტოტი და შეკრული მეთოდი

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

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

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

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

1. უნდა იყოს წრფივი;

2. უნდა ამოწყვიტოს ნაპოვნი ოპტიმალური არამთლიანი გეგმა;

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

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

მთელი რიცხვების პროგრამირება.

1. ააგეთ კოორდინატთა სისტემა x 1 0x 2 და აირჩიეთ მასშტაბი.

2. იპოვეთ ამოცანის შეზღუდვების სისტემის დასაშვები ამონახსნების (ADS) რეგიონი.

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

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

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

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

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

7. ახალი კოორდინატების განსაზღვრა და გრაფიკის აგება.

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

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

ეს მეთოდი ეფუძნება სიმპლექსის მეთოდს.

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

ხაზოვანი;

აღმოჩენილი ოპტიმალური არამთლიანი გეგმის ამოჭრა;

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

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

შეზღუდვა დაწესებულია არა მთელი რიცხვის ცვლადზე ან ცვლადზე, რომელსაც აქვს უფრო დიდი წილადური მნიშვნელობა. შეზღუდვა დაწესებულია არა მთელი რიცხვის ცვლადზე არაპირველადი ცვლადების მეშვეობით. შეზღუდვა შედგენილია შემდეგი წესით: თავისუფალი წევრის წილადი ნაწილი აღებულია იმავე ნიშნით, რაც მას აქვს განტოლებაში, ხოლო არაპირველადი ცვლადების წილადი ნაწილები აღებულია საპირისპირო ნიშნით და დადებითი წილადი არის ხაზგასმულია. მაგალითად, (a)=a, (-a)=(-A+a * ), სადაც A არის უარყოფითი რიცხვის მთელი რიცხვი, ხოლო * დადებითი წილადია.

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

სადაც x n+1 არის ახლად შემოღებული ცვლადი,

x j - ცვლადები, რომლებიც არ შედის საფუძველში.

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

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

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

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

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

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

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

ტვირთის ტიპი	თ		ფულადი ერთეულები

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

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

მოდით შემოგთავაზოთ შემდეგი აღნიშვნა: X 1 – პირველი ტიპის ტვირთის რაოდენობა, X 2 – მეორე ტიპის ტვირთის რაოდენობა. შემდეგ პრობლემის ეკონომიკური და მათემატიკური მოდელი მიიღებს ფორმას:

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

ძირითადი სიმპლექსის მეთოდის ალგორითმის გამოყენებით, ჩვენ ვავსებთ სიმპლექსის ცხრილს ZLP-ის ამოსახსნელად:

*
	-10	-12*
	*	5/2			-1/2	19/2
	1/2			1/2	5/2
	-4*				-30
				2/5	-1/5	19/5
			-1/5	3/5	3/5
			8/5	26/5	-226/5

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

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

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

,

.

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

.

მოდით გავაგრძელოთ პრობლემის გადაჭრა ორმაგი სიმპლექსის მეთოდის გამოყენებით, მათ შორის ახალი შეზღუდვა ოპტიმალურ სიმპლექს ცხრილში ZLP-ის გადასაჭრელად:

				2/5	-1/5		19/5
			-1/5	3/5		3/5
			-2/5	-4/5		-4/5
			8/5*	26/5		-226/5
					-5/2
						-42

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