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

ზოგიერთ შემთხვევაში, შედეგები შეიძლება დამრგვალდეს. მაგალითად, თუ ოპტიმალური გეგმა ითვალისწინებს 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.გამოყენებით სიმპლექსის მეთოდიპირველი პრობლემის გადაწყვეტა იქნა მიღებული:

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

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

6 პასუხი

მიჰყევით ამ მაგალითს: დავუშვათ, განტოლებებია:

7 = x + 3y + 4z + 9w 12 = 4x + 2y + 3z + 7w

არის 2 განტოლება და 4 უცნობი. თქვენ შეგიძლიათ დააყენოთ 2 უცნობიდან პარამეტრებად, ასე რომ სისტემას ექნება იმდენი განტოლება, რამდენიც უცნობია:

7 - (4z + 9w) = x + 3y 12 - (3z + 7w) = 4x + 2y

ჩვენ გამოვიყენებთ x და y როგორც უცნობი. ის შეიძლება ამოხსნას და დატოვოს w და ​​z პარამეტრებად ხაზოვან ამონახსნში:

X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10

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

ზოგადად, თქვენ აკეთებთ ამას:

• შეარჩიეთ პარამეტრები ისე, რომ იმდენი უცნობი იყოს, რამდენიც განტოლება. შეეცადეთ დატოვოთ უცნობი, რომლებიც წარმოქმნიან უმცირეს აბსოლუტურ მნიშვნელობას დეტერმინანტისთვის (მაგალითში ეს იყო 10, მაგრამ y და z არჩევა უკეთესი იქნება, რადგან ეს იქნება |det|=3)
• ამოხსენით წრფივი სისტემა და შექმენით პასუხი პარამეტრების მიხედვით
• შეამოწმეთ პარამეტრის მნიშვნელობები 1-დან det-ის აბსოლუტურ მნიშვნელობამდე (თუ გამოსავალი არსებობს, თქვენ იპოვით მას იმ წერტილში), სანამ არ იქნება მთელი ამონახსნი ყველა უცნობისთვის (ამიტომ ირჩევთ მანამდე ყველაზე პატარა განმსაზღვრელ მნიშვნელობას) და შეამოწმეთ არის თუ არა ის დადებითი (ეს არ იყო ილუსტრირებული მაგალითში).

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

რედაქტირება 1

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

22 = 3w + z (თანმიმდევრული, მოდ 10) 16 = 29w + 13z (კონგრუენტი, მოდ 10)

მოდულის გამოყენება:

2 = 3w + z (კონგრუენტი, მოდ 10) 6 = 9w + 3z (კონგრუენტი, მოდ 10)

თქვენ შეგიძლიათ გააკეთოთ კონგრუენციის სისტემა სამკუთხა (გაუსის ელიმინაცია) კონგრუენტობის გამრავლებით მის შებრუნებულ მოდულზე 10 და შეჯამებით სხვებთან. 9 მოდულო 10-ის შებრუნებული არის -1, ამიტომ ვამრავლებთ ბოლო თანხვედრას:

2 = 3w + z (კონგრუენტი, მოდ 10) -6 = -9w + -3z (კონგრუენტი, მოდ 10)

ექვივალენტი:

2 = 3w + z (კონგრუენტი, მოდ 10) 4 = w + 7z (კონგრუენტი, მოდ 10)

შემდეგ გაამრავლეთ -3-ზე და დაამატეთ პირველს:

2 - 3*4 = 3w + z -3w - 21z (კონგრუენტი, მოდ 10) 4 = w + 7z (კონგრუენტი, მოდ 10)

ექვივალენტი:

10 = -20z (თანმიმდევრული, მოდ 10) 4 = w + 7z (კონგრუენტი, მოდ 10)

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

შემატყობინეთ, თუ არის კიდევ რაიმე გაუგებარი!

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

თანასწორობის შეზღუდვა ჰგავს Aeqx = beq. Aeq მატრიცა ორი პაკეტისთვის ოთხი ბრენდისთვის (numVarsnumPackages) ასე გამოიყურება:

21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50

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

შეზღუდვების მეორე ნაკრები (უთანასწორობა) ეხება ბრენდების ჯგუფს, რომელიც მე მაქვს. უტოლობის შეზღუდვა ჰგავს A * x = b. მატრიცა A 4 მარკისა და 8 ცვლადისთვის (numPackages * numStampDenominations) ასე გამოიყურება:

1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x<= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20

დანახარჯების ფუნქცია არის f"*x, რომელიც წარმოადგენს ჯამების რაოდენობას. მისი კოეფიციენტები არის უბრალოდ ერთეულები, მითითებული, როგორც სვეტის ვექტორი.

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

% თითოეული მარკის ღირებულება ხელმისაწვდომია 4x1 მატრიცის სახით sv = [.21; .68; .47; .01]; % თითოეული მარკის რაოდენობა ხელმისაწვდომია 4x1 მატრიცის სახით კვ = ; % დემონსტრაციების რაოდენობა m = ზომა(sv, 1); % თითოეული პაკეტისთვის საჭირო საფოსტო გადასახადი, როგორც 4x1 მატრიცა % -- ალბათ წაკითხული ფაილიდან postage = [.89;.50;1.01;.47;.47]; % პაკეტების რაოდენობა -- მხოლოდ საფოსტო რიგების რაოდენობა პაკეტიCount = ზომა(ფოსტა, 1); % ცვლადების რაოდენობაა m*packageCount numVar = m*packageCount; % ქვედა ზღვარი -- მოცემული ნომინალის ნულოვანი მარკები lb = zeros(numVar,1); % ზედა ზღვარი - გამოიყენეთ შეზღუდვები ზედა ზღვარისთვის ub =; % ღირებულება ფუნქცია -- შეამცირეთ გამოყენებული მარკების რაოდენობა % min(f"*x) f = ones(numVar,1); % მთელი რიცხვის შეზღუდვები intcon = 1:numVar; % შეადგინეთ საფოსტო გადასახადის შეზღუდვის მატრიცა Aeq = ნულები(numVar,packCount i = 1:packageCount first = i*m - 3 last = first + 3 (first:last,i) = sv(:) Construction stamp count constraint matrix (numVar); ) r = 1:m j = 1:m c = (j-1)*m + 1 დასასრული x = intlinprog(f, intcon, A", b, Aeq ", beq, lb, ub)

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

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

მაგალითი:

Y=x+3

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

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

(x, x+3)

გაოცება:

თუ სადმე არის ირაციონალური რიცხვი, არ არის მთელი რიცხვი ამონახსნები:

(x, x+pi) => აქ არც 1 და არც მე-2 რიცხვი ერთდროულად არ შეიძლება იყოს მთელი

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

ვთქვათ, თქვენ გაქვთ შემდეგი ვექტორი:

(3x, (2/5)y, y, x, x+y)

მაშინ მთელი გამოსავალი შეიძლება იყოს:

X=3 y=10/2

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

შესავალი

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

3. პარამეტრული პროგრამირება

3.1 პრობლემა პარამეტრთან ობიექტურ ფუნქციაში

3.2 პარამეტრის პრობლემა შეზღუდვის სისტემის თავისუფალ პირობებში

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

4. მთელი რიცხვითი პარამეტრული პროგრამირება

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

4.2 მთელი რიცხვითი პროგრამირების პრობლემის გადაჭრის მაგალითი პარამეტრით შეზღუდვის სისტემის თავისუფალ პირობებში

დასკვნა

ცნობები

შესავალი

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

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

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

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

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

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

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

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

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

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

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

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

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

დიპლომის დაწერისას გამოყენებული იქნა შემდეგი საცნობარო ლიტერატურა: კუზნეცოვი Yu.N., Kuzubov V.I., Voloshchenko A.B. მათემატიკური პროგრამირება, Ashmanov S.A. ხაზოვანი პროგრამირება. რამდენიმე მაგალითი აღებულია ვ.ი.კოპილოვის წიგნებიდან. ლექციები და პრაქტიკული მეცადინეობები მათემატიკური პროგრამირების შესახებ, აკულიჩ ი.ლ. მათემატიკური პროგრამირება მაგალითებში და ამოცანებში. მთელი და პარამეტრული პროგრამირების ამოცანების ამოხსნის ალგორითმები, ჩემი აზრით, ყველაზე ხელმისაწვდომი და სრულყოფილია აკულიჩის წიგნში.

1. წრფივი პროგრამირების ძირითადი ცნებები

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

სტანდარტული დავალება

(1.1) (1.2)

მატრიცის სახით ამოცანას (1.1) - (1.2) აქვს ფორმა:

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

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

ან მატრიცის სახით:

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

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

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

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

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

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

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

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

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

(2.1.1)

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

(2.1.2) (2.1.3)
- მთლიანი. (2.1.4)

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

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

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

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

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

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

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