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

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

X წერტილი ეწოდება ამოზნექილი ხაზოვანი კომბინაციაქულები, თუ პირობები დაკმაყოფილებულია

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

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

თეორემა 1.1. ამოზნექილი n-პოლიტოპი არის მისი კუთხის წერტილების ამოზნექილი წრფივი კომბინაცია.

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

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

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

მატრიცული აღნიშვნა:

Აქ თან- მწკრივის მატრიცა, ა- სისტემის მატრიცა, NS- ცვლადების მატრიცა-სვეტი, ვ- თავისუფალი წევრების მატრიცა-სვეტი:

ვექტორული აღნიშვნა:

სადაც ვექტორები შეესაბამება კოეფიციენტების სვეტებს უცნობისთვის.

შემდეგი თეორემა ზემოთ იყო ნათქვამი, მაგრამ არ დადასტურდა ზოგადი ფორმით.

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

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

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

ე.ი. გამოსავალი Xაკმაყოფილებს სისტემას (1.3). მაგრამ მას შემდეგ NS> 0, ე.ი. გამოსავალი აკმაყოფილებს არაუარყოფითობის პირობას.

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

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

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

მტკიცებულება:ჩვენ ვივარაუდებთ, რომ ხსნარის პოლიტოპი შემოსაზღვრულია. მოდით აღვნიშნოთ მისი კუთხის წერტილები , და ოპტიმალური გადაწყვეტა გადის X *... მერე F (X *)³ F (X)ყველა პუნქტისთვის NSხსნარების პოლიედონი. თუ X *არის კუთხის წერტილი, მაშინ დადასტურებულია თეორემის პირველი ნაწილი.

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

იმიტომ რომ F (X)არის წრფივი ფუნქცია, ვიღებთ

ამ გაფართოებაში ჩვენ ვირჩევთ მაქსიმალურ მნიშვნელობას მნიშვნელობებს შორის. დაე, ის შეესაბამებოდეს კუთხის წერტილს X კ(1 £ კ£ რ); მოდით აღვნიშნოთ მ,იმათ. . შეცვალეთ თითოეული მნიშვნელობა გამოხატულებაში (1.5) ამ მაქსიმალური მნიშვნელობით მ.მერე

ვარაუდით NS* არის ოპტიმალური გადაწყვეტა, მაშასადამე, ერთი მხრივ, მაგრამ, მეორე მხრივ, დადასტურებულია, რომ
F (X *)£ მ,აქედან გამომდინარე, სად X კ- კუთხის წერტილი. ასე რომ, არის კუთხის წერტილი X კრომელშიც წრფივი ფუნქცია იღებს თავის მაქსიმალურ მნიშვნელობას.

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

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

ამ შემთხვევაში იმის გათვალისწინებით, რომ ფუნქცია F (X)- ხაზოვანი, მივიღებთ

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

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

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

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

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

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

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

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

სადაც (ვვარაუდობთ, რომ, წინააღმდეგ შემთხვევაში, წერტილი NSემთხვევა წერტილს NS 1 ან NS 2).

ვწერთ ვექტორულ ტოლობას (1.6) კოორდინატთა სახით:

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

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

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

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

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

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

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

შემდგომ ლექციებზე დეტალურად იქნება გაანალიზებული MS Excel-ის დანამატის "Search for Solution" გამოყენებით ტიპიური ოპტიმიზაციის პრობლემების გადაჭრისა და მართვის გადაწყვეტილებების მიღების მაგალითები. ამოცანებს, რომლებიც საუკეთესოდ სრულდება ამ ხელსაწყოს მიერ, აქვს სამი ძირითადი თვისება:

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

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

• უცნობის რაოდენობა - 200;
• უცნობებზე ფორმულის შეზღუდვების რაოდენობა - 100;
• შეზღუდვის პირობების რაოდენობა უცნობისთვის არის 400.

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

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

MS Excel-ის გამოყენებით ეკონომიკური და მათემატიკური მოდელირების ამოცანების ამოხსნისას შესრულებული აუცილებელი მოსამზადებელი სამუშაოების თანმიმდევრობა ნაჩვენებია ნახაზი 1.6-ის ბლოკ დიაგრამაზე.

ბრინჯი. 1.6.

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

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

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

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

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

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

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

სისტემის საწყისი ელემენტების რაოდენობა

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

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

ბრინჯი. 1.7.

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

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

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

ეკონომიკურ ანალიზს აქვს შემდეგი მიზნები:

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

ანალიზის შესაძლო მეთოდები ნაჩვენებია დიაგრამაზე 1.8.

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

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

• "რა იქნება თუ…"
• "რაც საჭიროა..."

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

ვარიანტის ანალიზი შემდეგი ტიპისაა:

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

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

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

ამ განმარტებების მიხედვით, LP პრობლემა შეიძლება ჩამოყალიბდეს შემდეგნაირად: ამოზნექილი რეგიონის ყველა წერტილს შორის, რომელიც წარმოადგენს შეზღუდვების სისტემის ამოხსნას, აირჩიეთ ერთი, რომლის კოორდინატები მინიმუმამდე (მაქსიმალურად ამცირებენ) ხაზოვან ფუნქციას. ფ = თან 1 x + თან 2 წ.
გაითვალისწინეთ, რომ ცვლადები x, წ LPP-ში, როგორც წესი, იღებენ არაუარყოფით მნიშვნელობებს ( x≥ 0, წ≥ 0), ამიტომ რეგიონი მდებარეობს კოორდინატთა სიბრტყის I მეოთხედში.

განვიხილოთ წრფივი ფუნქცია ფ = თან 1 x + თან 2 წდა დააფიქსირეთ მისი ზოგიერთი მნიშვნელობა ფ... მოდით, მაგალითად, ფ= 0, ე.ი. თან 1 x + თან 2 წ= 0. ამ განტოლების გრაფიკი იქნება სწორი ხაზი, რომელიც გადის კოორდინატების (0; 0) საწყისზე (ნახ.).
ნახატი
ამ ფიქსირებული მნიშვნელობის შეცვლისას ფ = დ, სწორი თან 1 x+ თან 2 y = დპარალელურად იმოძრავებს და მთელ სიბრტყეს „კვალს მიჰყვება“. დაე იყოს დ- მრავალკუთხედი - შეზღუდვების სისტემის ამოხსნის არე. როცა იცვლება დსწორი თან 1 x + თან 2 წ = დ, რაღაც ღირებულებით დ = დ 1 მიაღწევს მრავალკუთხედს დ, დავარქვათ ეს წერტილი ა"შესვლის წერტილი" და შემდეგ, პოლიგონის გავლისას, გარკვეული მნიშვნელობით დ = დ 2 ჩვენ გვექნება მასთან ბოლო საერთო წერტილი ვ, დავურეკოთ ვ"გასასვლელი წერტილი".
ცხადია, მისი უმცირესი და უდიდესი მნიშვნელობის ობიექტური ფუნქცია ფ=თან 1 x + თან 2 წმიაღწევს შესასვლელ პუნქტებს ადა "გასვლა" ვ.
იმის გათვალისწინებით, რომ ობიექტური ფუნქცია იღებს ოპტიმალურ მნიშვნელობას შესაძლო გადაწყვეტილებების სიმრავლეზე რეგიონის წვეროებზე დ LPP-ის გადაჭრის შემდეგი გეგმა შეიძლება შემოთავაზებული იყოს:

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

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

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

შემთხვევა 1
სურათი 6
სწორი მოძრაობისას თან 1 x + თან 2 წ= დ"შესვლა" ან "გასვლა" (როგორც სურათზე) მოხდება პოლიგონის მხარეს. ეს მოხდება, თუ მრავალკუთხედს აქვს გვერდები სწორი ხაზის პარალელურად. თან 1 NS+ თან 2 ზე = დ .
ამ შემთხვევაში, "გასასვლელი" ("შესვლის") წერტილები უთვალავია, კერძოდ, სეგმენტის ნებისმიერი წერტილი. AB... ეს ნიშნავს, რომ ობიექტური ფუნქცია იღებს მაქსიმალურ (მინიმალურ) მნიშვნელობას არა ერთ წერტილში, არამედ მრავალკუთხედის შესაბამის მხარეს მდებარე ყველა წერტილში. დ.

შემთხვევა 2
განვიხილოთ შემთხვევა, როდესაც დასაშვები მნიშვნელობების დიაპაზონი შეუზღუდავია.
შეუზღუდავი არეალის შემთხვევაში, ობიექტური ფუნქცია შეიძლება განისაზღვროს ისე, რომ შესაბამის სწორ ხაზს არ ჰქონდეს „გასასვლელი“ (ან „შესასვლელი“) წერტილი. მაშინ ფუნქციის მაქსიმალური მნიშვნელობა (მინიმუმი) არასოდეს მიიღწევა - ამბობენ, რომ ფუნქცია შეზღუდული არ არის.
ნახატი
აუცილებელია ობიექტური ფუნქციის მაქსიმალური მნიშვნელობის პოვნა ფ = 4x + 6წ→ max, შეზღუდვების სისტემით
ავაშენოთ შესაძლებელი გადაწყვეტილებების რეგიონი, ე.ი. გრაფიკულად მოვაგვარებთ უტოლობათა სისტემას. ამისათვის ვაშენებთ თითოეულ წრფეს და განვსაზღვრავთ უტოლობებით მოცემულ ნახევრად სიბრტყეებს.
x + წ = 18

x	12	9
წ	6	9

0,5x + წ = 12

x	12	18
წ	6	3

x= 12 - ღერძის პარალელურად OY ;
წ= 9 - ღერძის პარალელურად ოქსი ;
x= 0 - ღერძი OY ;
წ = 0 - ღერძი ოქსი;
x OY;
წ≥ 0 - ნახევრად სიბრტყე ღერძის ზემოთ ოქსი;
წ≤ 9 - ნახევრად სიბრტყე ქვემოთ წ = 9;
x ≤ 12 - ნახევრად თვითმფრინავი მარცხნივ x = 12;
0,5x + წx + წ = 12;
x + წ x + წ = 18.
ნახატი
ყველა ამ ნახევრად სიბრტყის კვეთა აშკარად ხუთკუთხედია OAVSD, წერტილებში წვეროებით ო(0; 0), ა(0; 9), ვ(6; 9), თან(12; 6), დ(12; 0). ეს პენტაგონი ქმნის პრობლემის შესაძლო გადაწყვეტის რეგიონს.

ფ = 4x + 6წ→ მაქს.

x	3	0
წ	–2	0

ფ = 0: 4x + 6წ x+ 6წ თან(12; 6). მასშია ფ = 4x + 6წ
აქედან გამომდინარე, ამისთვის x = 12, წ= 6 ფუნქცია ფ ფ= 4 ∙ 12 + 6 ∙ 6 = 84, ტოლია 84-ის. წერტილი კოორდინატებით (12; 6) აკმაყოფილებს შეზღუდვების სისტემის ყველა უტოლობას და მასში ობიექტური ფუნქციის მნიშვნელობა ოპტიმალურია. ფ* = 84 (ოპტიმალური მნიშვნელობა აღინიშნა "*"-ით).
პრობლემა მოგვარებულია. ასე რომ, აუცილებელია I ტიპის 12 და II ტიპის 6 პროდუქტის წარმოება, ხოლო მოგება იქნება 84 ათასი რუბლი.

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

მაგალითი No2. მაღარო ავითარებს ორ ნაკერს. პირველ ფენაში ჭრის გამოსავალი არის a1%; მეორეზე - a2%. პირველი ფენისთვის გრძელი კედლის მაქსიმალური წარმოებაა B1 ათასი ტონა წელიწადში, მეორე ფენისთვის - B2 ათასი ტონა წელიწადში. სამუშაო ტექნოლოგიის მიხედვით, მეორე ფენიდან წარმოება არ შეიძლება აღემატებოდეს პირველი ფენის წარმოებას. მაღაროში მაღაროს გამომუშავება არ უნდა აღემატებოდეს C1 ათას ტონას წელიწადში. წელიწადში ორ ფენაზე მთლიანი დატვირთვა უნდა იყოს მინიმუმ C2 ათასი ტონა წელიწადში. შექმენით მათემატიკური მოდელი და შექმენით დასაშვები დატვირთვის მნიშვნელობების ნაკრები წელიწადში პირველი და მეორე ფენებისთვის.

მაგალითი No3. მაღაზიაში იყიდება 2 სახის გამაგრილებელი სასმელი: კოლა და ლიმონათი. ერთი ქილა კოლას შემოსავალი 5 ცენტია, ხოლო ერთი ქილა ლიმონათიდან 7 ცენტი. საშუალოდ, მაღაზია დღეში ყიდის არაუმეტეს 500 ქილა ორივე სასმელს. მიუხედავად იმისა, რომ კოლას აწარმოებს ცნობილი ბრენდი, მყიდველები უპირატესობას ანიჭებენ ლიმონათს, რადგან ის გაცილებით იაფია. შეფასებულია, რომ კოლას და ლიმონათის გაყიდვები უნდა იყოს მინიმუმ 2: 1, ხოლო მაღაზიაში ცნობილია დღეში მინიმუმ 100 ქილა კოლას გაყიდვა. თითოეული სასმელის რამდენი ქილა უნდა ჰქონდეს მაღაზიას დღის დასაწყისში, რომ მაქსიმალური შემოსავალი იყოს?

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

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

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

მაგალითი No7. ხაზოვანი პროგრამირების ამოცანის ამოხსნა გრაფიკული მეთოდით, პრობლემის შეზღუდვების სისტემის დაქვემდებარებაში ჟორდანია-გაუსის გარდაქმნებით. პრობლემის შეზღუდვების სისტემა შემდეგია:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
გაიდლაინები... ჟორდანი-გაუსის ტრანსფორმაციები შეიძლება განხორციელდეს ამ სერვისის გამოყენებით ან SLAE-ების შესწავლით.

მაგალითი No8. საწარმო აწარმოებს ორი სახის პროდუქციას A და B, რომელთა წარმოებისთვის გამოიყენება სამი სახის ნედლეული. A პროდუქტის ერთეულის დასამზადებლად საჭიროა თითოეული ტიპის ნედლეულის დახარჯვა, შესაბამისად, a1, a2, a3 კგ, ხოლო B პროდუქტის ერთეულისთვის - b1, b2, b3 კგ. წარმოება უზრუნველყოფილია თითოეული ტიპის ნედლეულით, შესაბამისად Р1, Р2, Р3 კგ ოდენობით. A პროდუქტის ერთეულის ღირებულებაა C1 რუბლი, ხოლო B პროდუქტის ერთეული არის C2 რუბლი. საჭიროა A და B პროდუქციის წარმოების გეგმის შედგენა, რომელიც უზრუნველყოფს მზა პროდუქტის მაქსიმალურ ღირებულებას.

მაგალითი No2. აუცილებელია ობიექტური ფუნქციის მაქსიმალური მნიშვნელობის პოვნა ფ = 4x + 6წ→ max, შეზღუდვების სისტემით:

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

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

სურათი 3
x= 12 - ღერძის პარალელურად OY;
წ= 9 - ღერძის პარალელურად ოქსი;
x> = 0 - ღერძი OY
წ= 0 - ღერძი ოქსი;
x≥ 0 - ნახევრად სიბრტყე ღერძის მარჯვნივ OY;
წ≥0 - ნახევრად სიბრტყე ღერძის ზემოთ ოქსი;
წ≤ 9 - ნახევრად სიბრტყე ქვემოთ წ = 9;
x≤ 12 - ნახევრად თვითმფრინავი მარცხნივ x = 12;
0,5x + წ≤ 12 - ნახევრად სიბრტყე სწორი ხაზის ქვემოთ 0,5 x + წ = 12;
x + წ≤ 18 - ნახევრად სიბრტყე სწორი ხაზის ქვემოთ x + წ = 18.

ყველა ამ ნახევრად სიბრტყის კვეთა არის ხუთკუთხედი Ა Ბ Ც Დ Ე, წერტილებში წვეროებით ა(0; 0), ბ(0;9), C(6; 9), დ(12;6), ე(12; 0). ეს პენტაგონი ქმნის პრობლემის შესაძლო გადაწყვეტის რეგიონს.

განვიხილოთ პრობლემის ობიექტური ფუნქცია ფ = 4x + 6წ→ მაქს.

x	3	0
წ	–2	0

ჩვენ ვაშენებთ სწორ ხაზს, რომელიც შეესაბამება ფუნქციის მნიშვნელობას ფ = 0: 4x + 6წ= 0. ამ წრფეს პარალელურად გადავიტანთ. ხაზების მთელი ოჯახიდან 4 x + 6წ= შეადგინეთ ბოლო წვერო, რომლის მეშვეობითაც გადის სწორი წრფე, როცა მრავალკუთხედის საზღვრებს გასცდება, იქნება წვერო თან(12; 6). მასშია ფ = 4x + 6წაღწევს მაქსიმალურ მნიშვნელობას.

აქედან გამომდინარე, ამისთვის x = 12, წ= 6 ფუნქცია ფაღწევს მაქსიმალურ მნიშვნელობას ფ= 4 ∙ 12 + 6 ∙ 6 = 84, ტოლია 84-ის. წერტილი კოორდინატებით (12; 6) აკმაყოფილებს შეზღუდვების სისტემის ყველა უტოლობას და მასში ობიექტური ფუნქციის მნიშვნელობა ოპტიმალურია. ფ* = 84.

ტესტი დისციპლინაში "ოპერაციების კვლევა"

(სწორი პასუხები პირველია)

1. ტერმინი „ოპერაციების კვლევა“ გაჩნდა ...

მეორე მსოფლიო ომის დროს

XX საუკუნის 50-იან წლებში

XX საუკუნის 60-იან წლებში

XX საუკუნის 70-იან წლებში

XX საუკუნის 90-იან წლებში

XXI საუკუნის დასაწყისში

2. ოპერაციების კვლევის საშუალებები (აირჩიეთ ყველაზე შესაფერისი ვარიანტი) ...

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

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

ჩაფიქრებული გეგმის განხორციელების მეთოდების ნაკრები

წარმოების ორგანიზაციაში რესურსების განაწილების მეცნიერული მეთოდები

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

პრობლემის ფორმულირება

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

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

აგებული მათემატიკური მოდელის საფუძველზე ჩამოყალიბებული ამოცანების ამოხსნა

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

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

4. ოპერაციების კვლევისას, ოპერაცია გაგებულია ...

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

ნებისმიერი უკონტროლო მოვლენა

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

5. ამოხსნას ოპტიმალური ჰქვია, ...

თუ სასურველია ამა თუ იმ მიზეზის გამო

თუ რაციონალურია

თუ შეთანხმებულია ხელისუფლებასთან

საერთო კრების დამტკიცების შემთხვევაში

6. მათემატიკური პროგრამირება ...

ეწევა ექსტრემალური პრობლემების შესწავლას და მათი გადაჭრის მეთოდების შემუშავებას

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

წყვეტს მათემატიკურ ამოცანებს კომპიუტერზე

7. ხაზოვანი პროგრამირების ამოცანაა ...

წრფივი ფუნქციის უდიდესი (უმცირესი) მნიშვნელობის პოვნა წრფივი შეზღუდვების არსებობისას

ხაზოვანი პროგრამის შექმნა შერჩეულ პროგრამირების ენაზე, რომელიც შექმნილია პრობლემის გადასაჭრელად

მოცემული პრობლემის გადაჭრის წრფივი ალგორითმის აღწერა

8. კვადრატული პროგრამირების პრობლემაში ...

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

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

შეზღუდვები შეიცავს კვადრატულ ფუნქციებს

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

უცნობებს შეუძლიათ მხოლოდ მთელი რიცხვების აღება

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

სამიზნე ფუნქცია არის რიცხვითი მუდმივი

10. პარამეტრული პროგრამირების ამოცანებში ...

ობიექტური ფუნქცია და/ან შეზღუდვის სისტემა შეიცავს პარამეტრებს

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

ცვლადების რაოდენობა შეიძლება იყოს მხოლოდ ლუწი

11. დინამიური პროგრამირების პრობლემებში ...

გამოსავლის ძიების პროცესი მრავალსაფეხურიანია

საჭიროა დინამიტის წარმოების რაციონალიზაცია

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

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

ფ(NS 1, NS 2) = 5NS 1 + 6NS 2→ მაქს

0.2NS 1 + 0.3NS 2 ≤ 1.8,

0.2NS 1 + 0.1NS 2 ≤ 1.2,

0.3NS 1 + 0.3NS 2 ≤ 2.4,

NS 1 ≥ 0, NS 2 ≥ 0.

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

ფ(NS 1, NS 2)= 5NS 1 + 6NS 2 → მაქს,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

ფ(NS 1, NS 2)= 6NS 1 + 5NS 2 → წთ,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

ფ(NS 1, NS 2)= 50NS 1 + 60NS 2 → მაქს,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

ფ(NS 1, NS 2)= 5NS 12 + 6NS 22 → მაქს,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

3NS 1 + NS 2 ≤ 2.4,

NS 1 ≥ 0,

NS 2 ≥ 0.

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

ფ=12x1+20x2-3 0x3→წთ

ფ= →წთ

ფ=→მაქს

ფ=→მაქს.

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

15. სიმპლექსის მეთოდია:

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

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

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

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

16. წრფივი პროგრამირების ამოცანაა:

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

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

წრფივი განტოლებათა სისტემის შედგენა და ამოხსნა

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

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

18. წრფივი პროგრამირების ამოცანის სამიზნე ფუნქცია შეიძლება იყოს ფუნქცია:

ფ=12x1+20x2-3 0x3→წთ

ფ= →წთ

ფ=→მაქს

ფ=→მაქს.

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

20. წრფივი პროგრამირების ამოცანის შესაძლო ამონახსნების რეგიონი ასეთია:

ფ(NS 1, NS 2)= 3NS 1 + 5NS 2 უდრის...

21. ხაზოვანი პროგრამირების ამოცანის შესაძლო ამონახსნების რეგიონს აქვს ფორმა:

შემდეგ ფუნქციის მაქსიმალური მნიშვნელობა ფ(NS 1, NS 2)= 5NS 1 + 3NS 2 უდრის...

22. ხაზოვანი პროგრამირების ამოცანის შესაძლო ამონახსნების რეგიონს აქვს ფორმა:

შემდეგ ფუნქციის მაქსიმალური მნიშვნელობა ფ(NS 1, NS 2)= 2NS 1 - 2NS 2 უდრის...

23. ხაზოვანი პროგრამირების ამოცანის შესაძლო ამონახსნების რეგიონს აქვს ფორმა:

ფ(NS 1, NS 2)= 2NS 1 - 2NS 2 უდრის...

24. არაწრფივი პროგრამირების პრობლემის შესაძლო გადაწყვეტილებების რეგიონს აქვს ფორმა:

შემდეგ ფუნქციის მაქსიმალური მნიშვნელობა ფ(NS 1, NS 2)= NS 2 – NS 12 უდრის...

25. ობიექტური ფუნქციის მაქსიმალური მნიშვნელობა ფ(NS 1, NS 2)= 5NS 1 + 2NS 2 შეზღუდვებით
NS 1 + NS 2 ≤ 6,

NS 1 ≤ 4,

NS 1 ≥ 0, NS 2 ≥ 0, უდრის ...

26. მცირე ბიზნესი აწარმოებს ორი სახის პროდუქტს. A ტიპის ერთი პროდუქტის დასამზადებლად იხარჯება 2 კგ ნედლეული, B ტიპის ერთი პროდუქტის დასამზადებლად - 1 კგ. სულ 60 კგ ნედლეულია. საჭიროა საწარმოო გეგმის შედგენა, რომელიც უზრუნველყოფს ყველაზე დიდი შემოსავლის მიღებას, თუ A ტიპის ერთი პროდუქტის გაყიდვის ღირებულება არის 3 ერთეული, ტიპი B არის 1 ერთეული. ანუ, A ტიპის პროდუქტები უნდა დამზადდეს არაუმეტეს 25, ხოლო B ტიპის არაუმეტეს 30.

ეს ამოცანა არის...

ხაზოვანი პროგრამირების პრობლემა

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

ქსელის დაგეგმვის ამოცანა.

27. მცირე ბიზნესი აწარმოებს ორი სახის პროდუქტს. A ტიპის ერთი პროდუქტის დასამზადებლად იხარჯება 2 კგ ნედლეული, B ტიპის ერთი პროდუქტის დასამზადებლად - 1 კგ. სულ 60 კგ ნედლეულია. საჭიროა საწარმოო გეგმის შედგენა, რომელიც უზრუნველყოფს ყველაზე დიდი შემოსავლის მიღებას, თუ A ტიპის ერთი პროდუქტის გაყიდვის ღირებულება არის 3 ერთეული, ტიპი B არის 1 ერთეული. ანუ, A ტიპის პროდუქტები უნდა დამზადდეს არაუმეტეს 25, ხოლო B ტიპის არაუმეტეს 30.

ამ ამოცანის ობიექტური ფუნქცია არის ფუნქცია ...

ფ(x1, x2)=3x1+x2→მაქს

ფ(x1, x2)=25x1+30x2→მაქს

ფ(x1, x2)=2x1+x2→მაქს

ფ(x1, x2)=60 -2x1 - x2→წთ

28. მცირე ბიზნესი აწარმოებს ორი სახის პროდუქტს. A ტიპის ერთი პროდუქტის დასამზადებლად იხარჯება 2 კგ ნედლეული, B ტიპის ერთი პროდუქტის დასამზადებლად - 1 კგ. სულ 60 კგ ნედლეულია. საჭიროა საწარმოო გეგმის შედგენა, რომელიც უზრუნველყოფს ყველაზე დიდი შემოსავლის მიღებას, თუ A ტიპის ერთი პროდუქტის გაყიდვის ღირებულება არის 3 ერთეული, ტიპი B არის 1 ერთეული. ანუ, A ტიპის პროდუქტები უნდა დამზადდეს არაუმეტეს 25, ხოლო B ტიპის არაუმეტეს 30.

ამ ამოცანის სწორი გეგმა არის გეგმა:

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. ორ A1 და A2 პუნქტში არის შესაბამისად 60 და 160 ერთეული საქონელი. ყველა საქონლის ტრანსპორტირება საჭიროა B1, B2, B3 პუნქტებში, შესაბამისად 80, 70 და 70 ერთეულის ოდენობით. სატარიფო მატრიცა ასეთია:. დაგეგმეთ ტრანსპორტი ისე, რომ ღირებულება იყოს მინიმალური.

ეს ამოცანა არის...

სატრანსპორტო დავალება

არაწრფივი პროგრამირების პრობლემა

მოგზაური გამყიდველის პრობლემა

დავალების დავალება

30. ორ A1 და A2 პუნქტში არის შესაბამისად 60 და 160 ერთეული საქონელი. ყველა საქონლის ტრანსპორტირება საჭიროა B1, B2, B3 პუნქტებში, შესაბამისად 80, 70 და 70 ერთეულის ოდენობით. სატარიფო მატრიცა ასეთია:. დაგეგმეთ ტრანსპორტი ისე, რომ ღირებულება იყოს მინიმალური

ამ ამოცანის ძირითადი გეგმა არის გეგმა:

;

31. ორ A1 და A2 პუნქტში არის შესაბამისად 60 და 160 ერთეული საქონელი. ყველა საქონლის ტრანსპორტირება საჭიროა B1, B2, B3 პუნქტებში, შესაბამისად 80, 70 და 70 ერთეულის ოდენობით. სატარიფო მატრიცა ასეთია:. დაგეგმეთ ტრანსპორტი ისე, რომ ღირებულება იყოს მინიმალური.

ამ ამოცანის ობიექტური ფუნქციაა ფუნქცია:

ფ=4x11+6x12 + 8x13+5x21+8x22+7x23→წთ

ფ= →წთ

ფ=60x1+160x2 + 80x3+70x4+705 →მაქს

ფ=60x1+160x2– 80x3– 70x4– 705 →წთ

32. ორ A1 და A2 პუნქტში არის შესაბამისად 60 და 160 ერთეული საქონელი. ყველა საქონლის ტრანსპორტირება საჭიროა B1, B2, B3 პუნქტებში, შესაბამისად 80, 70 და 70 ერთეულის ოდენობით. სატარიფო მატრიცა ასეთია:. დაგეგმეთ ტრანსპორტი ისე, რომ ღირებულება იყოს მინიმალური.

ამ ამოცანის ოპტიმალური გეგმა არის გეგმა:

;

.

;

;

33. ტრანსპორტის პრობლემა

დაიხურება თუ...

34. ტრანსპორტის პრობლემა

არის…

გახსნა

დახურული

უხსნადი

35. ტრანსპორტის პრობლემა

არის…

დახურული

გახსნა

უხსნადი

36. შემდეგი სატრანსპორტო პრობლემის გადასაჭრელად

უნდა შეხვიდე...

ფიქტიური მომხმარებელი

ფიქტიური მიმწოდებელი;

ეფექტური ტარიფი

37. შემდეგი სატრანსპორტო პრობლემის გადასაჭრელად

უნდა შეხვიდე...

ფიქტიური მიმწოდებელი;

ფიქტიური მომხმარებელი

ეფექტური ტარიფი

ეფექტური საპროცენტო განაკვეთი.

38. ამ სატრანსპორტო ამოცანებს შორის

დახურულია...

39. ტრანსპორტის პრობლემის საწყისი საბაზისო გეგმა შეიძლება შედგეს ...

ყველა ზემოთ ჩამოთვლილი მეთოდით

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

მინიმალური ტარიფის მეთოდით

ორმაგი უპირატესობის მეთოდი

ვოგელის დაახლოების მეთოდით

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

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

ორმაგ პრობლემას გამოსავალი არ აქვს

ორმაგ პრობლემას უსასრულოდ ბევრი გამოსავალი აქვს

41. მოცემულია წრფივი პროგრამირების ამოცანა:

ფ(NS 1, NS 2)= 2NS 1 + 7NS 2 → მაქს,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

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

F *(y1, y2) = 14y1 + 8y2 → წთ,

3 წ 1 + y2 ³ 7,

წ 1 ≥ 0, y2 ≥ 0.

F *(y1, y2) = 2y1 + 7y2 → წთ,

2y1 + 3y2 ³ 14,

წ 1 + y2 ³ 8,

წ 1 £ 0, y2 £ 0.

F *(y1, y2) = 2y1 + 7y2 → წთ,

3 წ 1 + y2 ³ 7,

წ 1 £ 0, y2 £ 0.

F *(y1, y2) = 14y1 + 8y2 → წთ,

წ 1 + y2 ³ 7,

წ 1 ≥ 0, y2 ≥ 0.

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

ხოლო მეორეს აქვს ოპტიმალური გეგმა

მეორეს არ აქვს ოპტიმალური გეგმა

მეორეს არ აქვს რეალური გადაწყვეტილებები

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

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

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

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

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

სხვა ამოცანას არ აქვს სწორი გეგმები

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

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

45. არაწრფივი პროგრამირების ზოგიერთი ამოცანის ამოხსნისას გამოიყენება ...

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

გაუსის მეთოდი

ვოგელის დაახლოების მეთოდი

გომორის მეთოდი

46. ​​დაყენებულია არაწრფივი პროგრამირების პრობლემა

ფ(NS 1, NS 2)= NS 12 + NS 22 → მაქს,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

ფ(NS 1, NS 2) …

მიუწვდომელია (+ ¥)

47. დაყენებულია არაწრფივი პროგრამირების პრობლემა

ფ(NS 1, NS 2)= NS 12 + NS 22 → მin,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

ფ(NS 1, NS 2) …

48. დაყენებულია არაწრფივი პროგრამირების პრობლემა

ფ(NS 1, NS 2)= NS 12 + NS 22 → მაქს,

NS 1 + NS 2 =6,

NS 1, NS 2 - ნებისმიერი.

ობიექტური ფუნქციის უმაღლესი მნიშვნელობა ფ(NS 1, NS 2) …

მიუწვდომელია (+ ¥)

49. დაყენებულია არაწრფივი პროგრამირების პრობლემა

ფ(NS 1, NS 2)= NS 12 + NS 22 → მin,

NS 1 + NS 2 =6,

NS 1, NS 2 - ნებისმიერი.

ობიექტური ფუნქციის უმცირესი მნიშვნელობა ფ(NS 1, NS 2) …

მიუწვდომელი (- ¥)

50. არაწრფივი პროგრამირების პრობლემის შესაძლო გადაწყვეტილებების რეგიონს აქვს ფორმა:

შემდეგ ფუნქციის მაქსიმალური მნიშვნელობა ფ(NS 1, NS 2)= NS 12 +NS 22 უდრის...

51. არაწრფივი პროგრამირების პრობლემის შესაძლო გადაწყვეტილებების რეგიონს აქვს ფორმა:

შემდეგ ფუნქციის მინიმალური მნიშვნელობა ფ(NS 1, NS 2)= NS 12 +NS 22 უდრის...

52. ტრანსპორტის პრობლემის გადასაჭრელად შეიძლება გამოყენებულ იქნას ...

პოტენციური მეთოდი

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

გაუსის მეთოდი

დეზორიენტაციის მეთოდი

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

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

მხოლოდ უთანასწორობა შეიძლება იყოს

შეიძლება იყოს როგორც განტოლებები, ასევე უტოლობა

მხოლოდ განტოლებები შეიძლება იყოს

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

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

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

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

56. წრფივი პროგრამირების პრობლემა

ფ(NS 1, NS 2)= 2NS 1 + 7NS 2 → მაქს,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

ჩაწერილია...

სტანდარტული (სიმეტრიული) ფორმა

კანონიკური (ძირითადი) ფორმა

სიტყვიერი ფორმა

57. დავალების ჩასაწერად

ფ(NS 1, NS 2)= 2NS 1 + 7NS 2 → მაქს,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

კანონიკური ფორმით...

58. დავალების ჩასაწერად

ფ(NS 1, NS 2)= 2NS 1 + 7NS 2 → მაქს,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

კანონიკური ფორმით...

აუცილებელია სამი დამატებითი არაუარყოფითი ცვლადის შემოღება

აუცილებელია ორი დამატებითი არაუარყოფითი ცვლადის შემოღება

აუცილებელია ოთხი დამატებითი არაუარყოფითი ცვლადის შემოღება

59. დავალების ჩასაწერად

ფ(NS 1, NS 2)= 2NS 1 + 7NS 2 → მაქს,

2NS 1 + 3NS 2 = 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

კანონიკური ფორმით...

აუცილებელია ორი დამატებითი არაუარყოფითი ცვლადის შემოღება

აუცილებელია სამი დამატებითი არაუარყოფითი ცვლადის შემოღება

აუცილებელია ოთხი დამატებითი არაუარყოფითი ცვლადის შემოღება

აუცილებელია ხუთი დამატებითი არაუარყოფითი ცვლადის შემოღება

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

გომორის მეთოდი

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

გაუსის მეთოდი

ვოგელის დაახლოების მეთოდი

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

ოკამის საპარსი

პრინციპი "კბილი კბილზე, თვალი თვალისთვის"

ჰაიზენბერგის პრინციპი

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

(კონფლიქტი, კონფლიქტი, კონფლიქტი, კონფლიქტი)

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

(თამაში, თამაში)

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

(თამაშის წესები, თამაშის წესები)

65. თამაშის შედეგების რაოდენობრივი შეფასება ეწოდება ...

(გადახდით, გადახდით, გადახდით)

66. თუ თამაშში მხოლოდ ორი მხარე (ორი ადამიანი) მონაწილეობს, მაშინ თამაშს ეწოდება ...

(ორმაგი, დუბლი, დუბლი, დუბლი)

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

(ნულოვანი ჯამი)

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

(მოთამაშის სტრატეგია, მოთამაშის სტრატეგია, სტრატეგია, სტრატეგია)

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

(ოპტიმალური, ოპტიმალური, ოპტიმალური სტრატეგია, ოპტიმალური სტრატეგია)

70. დავუშვათ, a იყოს დაბალი ფასი და b მაღალი ფასი ნულოვანი ჯამის ორმაგი თამაშისა. მაშინ განცხადება მართალია...

71. დავუშვათ, რომ a იყოს დაბალი ფასი და b მაღალი ფასი ნულოვანი ჯამის ორმაგი თამაშისა. თუ a = b = v, მაშინ რიცხვი v ეწოდება ...

თამაშის ფასად

წონასწორობის წერტილი

ოპტიმალური სტრატეგია

შერეული სტრატეგია

72. ვთქვათ a არის დაბალი ფასი და b მაღალი ფასი ნულოვანი ჯამის ორმაგი თამაშისა. თუ a = b, მაშინ თამაშს ეწოდება ...

უნაგირის წერტილის თამაში

გადაუჭრელი კონფლიქტი

თამაში წესების გარეშე

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

შერეული სტრატეგია

მიმართულების ვექტორი

ნორმალური ვექტორი

გრადიენტი

74. გადახდის მატრიცით მოცემული მატრიცული თამაშის დაბალი ფასი უდრის ...

უფრო დაბალი ფასი

ქვედა ფასის ტოლი

არ არსებობს

81. მატრიცული თამაში, რომელიც მოცემულია ანაზღაურების მატრიცით, ...

აქვს უნაგირის წერტილი

არ აქვს უნაგირის წერტილი

არ არის დაწყვილებული

82. თამაშის ფასი, რომელიც მოცემულია ანაზღაურების მატრიცით, არის ...

83. მატრიცული თამაში, რომელიც მოცემულია ანაზღაურების მატრიცით ...

არის დაწყვილებული

აქვს უნაგირის წერტილი

არ არის დაწყვილებული

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

ხაზოვანი პროგრამირების პრობლემა

არაწრფივი პროგრამირების პრობლემა

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

კლასიკური ოპტიმიზაციის პრობლემა

85. გადახდის მატრიცით მოცემული მატრიცული თამაშის დაბალი ფასი არის ...

უფრო დაბალი ფასი

ქვედა ფასის ტოლი

არ არსებობს

92. მატრიცული თამაში, რომელიც მოცემულია ანაზღაურების მატრიცით ...

არ აქვს უნაგირის წერტილი

აქვს უნაგირის წერტილი

არ არის დაწყვილებული

93. გადახდის მატრიცით მოცემული თამაშის ფასი არის ...

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

რეგულარული

ორგანიზებული

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

სტაციონარული

მიედინება შედეგების გარეშე

უმარტივესი

პუასონი

96. თუ ერთ-ერთ თვითნებურად არჩეულ დროის ინტერვალზე მოვლენის რაოდენობა არ არის დამოკიდებული მეორეზე, ასევე თვითნებურად არჩეულ დროის ინტერვალზე მოვლენის რაოდენობაზე, იმ პირობით, რომ ეს ინტერვალები არ იკვეთება, მაშინ მოვლენათა შესაბამისი ნაკადი ე.წ. ...

მიედინება შედეგების გარეშე

რეგულარული

საჩვენებელი

ნორმალური

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

ჩვეულებრივი

არაჩვეულებრივი

ნორმალური

პუასონი

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

უმარტივესი (პუასონი)

ნორმალური

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

100. ერთარხიანი სისტემა ჩავარდნებით არის ყოველდღიური ავტოგასარეცხი სადგური. აპლიკაცია - მანქანა, რომელიც ჩამოვიდა იმ მომენტში, როდესაც პოსტი დაკავებულია - იღებს მომსახურებაზე უარის თქმა. მანქანის ნაკადის სიჩქარე λ = 1.0 (მანქანა საათში). მომსახურების საშუალო დროა 1.8 საათი. მანქანის ნაკადი და მომსახურების ნაკადი ყველაზე მარტივია. შემდეგ, სტაბილურ მდგომარეობაში, მანქანების პროცენტი, რომლებიც იღებენ მომსახურებაზე უარის თქმას, არის ...

წრფივი პროგრამირების პრობლემის (LPP) ზოგადი ფორმულირება. LPP-ის მაგალითები

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

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

C1x1 + c2x2 + ... + cnxn> max (მინ); - შეზღუდვები:

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

არანეგატიურობის მოთხოვნა:

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

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

1. რესურსების ოპტიმალური გამოყენების პრობლემა წარმოების დაგეგმვაში. ამ კლასის ამოცანების ზოგადი მნიშვნელობა ასეთია. საწარმო აწარმოებს n სხვადასხვა პროდუქტს. მათი წარმოება მოითხოვს სხვადასხვა ტიპის რესურსებს (ნედლეული, მასალები, შრომის დრო და ა.შ.). რესურსები შეზღუდულია, მათი რეზერვები დაგეგმვის პერიოდში არის, შესაბამისად, b1, b2, ..., bm ჩვეულებრივი ერთეული. ასევე ცნობილია aij ტექნოლოგიური კოეფიციენტები, რომლებიც გვიჩვენებს, თუ რამდენი ერთეულია i-ე რესურსი საჭირო j-ე ტიპის პროდუქტის ერთეულის წარმოებისთვის (). საწარმოს მიერ j-ე ტიპის პროდუქტის რეალიზაციით მიღებული მოგება უდრის cj. დაგეგმვის პერიოდში, aij, bi და cj-ის მნიშვნელობები მუდმივი რჩება. საჭიროა ისეთი წარმოების გეგმის შედგენა, რომლის განხორციელებისას საწარმოს მოგება ყველაზე დიდი იქნება. ქვემოთ მოცემულია ამ კლასის დავალების მარტივი მაგალითი.

კომპანია სპეციალიზირებულია ჰოკეის ჯოხებისა და ჭადრაკის ნაკრების წარმოებაში. თითოეული კლუბი გამოიმუშავებს $2 მოგებას კომპანიისთვის და $4 ყოველი ჭადრაკის ნაკრებისთვის. A საიტზე ერთი კლუბის შექმნას ოთხი საათი სჭირდება და B საიტზე ორი საათი. ჭადრაკის ნაკრები მზადდება ექვსი საათით A საიტზე, ექვსი საათი B საიტზე და ერთი საათი C საიტზე. ხელმისაწვდომი საწარმოო სიმძლავრე A საიტზე არის 120 ნმ - საათი დღეში, სექცია B - 72 ნ-საათი და სექცია C - 10 ნ-საათი. რამდენი კლუბი და ჭადრაკის ნაკრები უნდა აწარმოოს კომპანიამ ყოველდღიურად, რომ მაქსიმალური მოგება მიიღოს?

ამ კლასის პრობლემების პირობები ხშირად წარმოდგენილია ცხრილის სახით (იხ. ცხრილი 2.1).

ამ პირობით, ჩვენ ვაყალიბებთ ხაზოვანი პროგრამირების პრობლემას. დავნიშნოთ: x1 - ყოველდღიურად წარმოებული ჰოკეის ჯოხების რაოდენობა, x2 - ყოველდღიურად წარმოებული ჭადრაკის ნაკრები. ZLP ფორმულირება:

4x1 + 6x2? 120,

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

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