შესავალი
კაცობრიობის განვითარების თანამედროვე ეტაპი განსხვავდება იმით, რომ ენერგეტიკის საუკუნე ინფორმატიკის ხანით იცვლება. მიმდინარეობს ახალი ტექნოლოგიების ინტენსიური დანერგვა ადამიანის საქმიანობის ყველა სფეროში. არსებობს ინფორმაციულ საზოგადოებაზე გადასვლის რეალური პრობლემა, რისთვისაც განათლების განვითარება პრიორიტეტული უნდა გახდეს. იცვლება საზოგადოებაში ცოდნის სტრუქტურაც. ფუნდამენტური ცოდნა, რომელიც ხელს უწყობს ინდივიდის შემოქმედებით განვითარებას, სულ უფრო მნიშვნელოვანი ხდება პრაქტიკული ცხოვრებისთვის. ასევე მნიშვნელოვანია შეძენილი ცოდნის კონსტრუქციულობა, მისი მიზნის შესაბამისად სტრუქტურირების უნარი. ცოდნის საფუძველზე ყალიბდება საზოგადოების ახალი საინფორმაციო რესურსები. ახალი ცოდნის ჩამოყალიბება და შეძენა უნდა ეფუძნებოდეს სისტემატური მიდგომის მკაცრ მეთოდოლოგიას, რომლის ფარგლებშიც ცალკე ადგილი უჭირავს სამოდელო მიდგომას. მოდელირების მიდგომის შესაძლებლობები უკიდურესად მრავალფეროვანია როგორც გამოყენებული ფორმალური მოდელების, ასევე მოდელირების მეთოდების დანერგვის გზების თვალსაზრისით. ფიზიკური მოდელირება შესაძლებელს ხდის საიმედო შედეგების მიღებას საკმაოდ მარტივი სისტემებისთვის.
ამჟამად შეუძლებელია ადამიანის საქმიანობის სფეროს დასახელება, რომელშიც, ამა თუ იმ ხარისხით, მოდელირების მეთოდები არ იქნება გამოყენებული. ეს განსაკუთრებით ეხება სხვადასხვა სისტემის მენეჯმენტს, სადაც მთავარია მიღებული ინფორმაციის საფუძველზე გადაწყვეტილების მიღების პროცესები.
1. პრობლემის განცხადება
მინიმალური მიზნობრივი ფუნქცია
გადაწყვეტილების მრავალკუთხედით განსაზღვრული შეზღუდვების სისტემისთვის ობიექტური ფუნქციის მინიმალური პოვნის ამოცანის ამოხსნა ამოცანის No16 ვარიანტის შესაბამისად. გადაწყვეტილების პოლიგონი ნაჩვენებია ნახაზ 1-ში:
სურათი 1 - პრობლემის გადაწყვეტის პოლიგონი
შეზღუდვების სისტემა და პრობლემის ობიექტური ფუნქცია წარმოდგენილია ქვემოთ:
პრობლემის გადაჭრა აუცილებელია შემდეგი მეთოდების გამოყენებით:
LP ამოცანების გადაჭრის გრაფიკული მეთოდი;
LP ამოცანების ამოხსნის ალგებრული მეთოდი;
LP ამოცანების გადაჭრის მარტივი მეთოდი;
LP პრობლემების შესაძლო გადაწყვეტის პოვნის მეთოდი;
ორმაგი LP პრობლემის გადაჭრა;
მთელი რიცხვი LP ამოცანების ამოხსნის „ტოტები და საზღვრები“ მეთოდი;
გომორის მეთოდი მთელი რიცხვითი LP ამოცანების ამოხსნისათვის;
ბალაშის მეთოდი ლოგიკური LP ამოცანების გადაჭრისთვის.
შეადარეთ ამოხსნის შედეგები სხვადასხვა მეთოდით ნამუშევარზე შესაბამისი დასკვნების გამოსატანად.
2. ხაზოვანი პროგრამირების ამოცანის გრაფიკული ამოხსნა
ხაზოვანი პროგრამირების ამოცანების გადაჭრის გრაფიკული მეთოდი გამოიყენება იმ შემთხვევებში, როდესაც უცნობის რაოდენობა არ აღემატება სამს. მოსახერხებელია ამონახსნების თვისებების ხარისხობრივი შესწავლისთვის და გამოიყენება სხვა მეთოდებთან ერთად (ალგებრული, განშტოება და შეკრული და სხვ.). მეთოდის იდეა ემყარება წრფივი უტოლობების სისტემის გრაფიკულ გადაწყვეტას.
ბრინჯი. 2 LP პრობლემის გრაფიკული გადაწყვეტა
დაბალი წერტილი
სწორი ხაზის განტოლება, რომელიც გადის ორ A1 და A2 წერტილებზე:
AB: (0;1); (3;3)
მზე: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
შეზღუდვებით:
წრფივი პროგრამირების ამოცანის ამოხსნა ალგებრული სიმპლექსის მეთოდით
პრობლემის გადასაჭრელად ალგებრული მეთოდის გამოყენება მოითხოვს LP პრობლემის წარმოდგენის განზოგადებას. უტოლობების სახით მოცემული შეზღუდვების თავდაპირველი სისტემა გარდაიქმნება სტანდარტულ აღნიშვნაში, როდესაც შეზღუდვები მოცემულია ტოლობის სახით. შეზღუდვების სისტემის სტანდარტულ ფორმად გადაქცევა მოიცავს შემდეგ ნაბიჯებს:
გადააქციეთ უტოლობები ისე, რომ ცვლადები და თავისუფალი წევრები იყოს მარცხნივ, ხოლო 0 მარჯვნივ, ე.ი. რომ მარცხენა მხარე იყოს ნულის მეტი ან ტოლი;
შემოიტანეთ დამატებითი ცვლადები, რომელთა რაოდენობა უდრის შეზღუდვების სისტემაში არსებული უტოლობების რაოდენობას;
დამატებული ცვლადების არანეგატიურობის შესახებ დამატებითი შეზღუდვების შემოღება, უტოლობის ნიშნები ჩაანაცვლეთ მკაცრი ტოლობის ნიშნებით.
LP ამოცანის ალგებრული მეთოდით ამოხსნისას ემატება პირობა: ობიექტური ფუნქცია მინიმუმამდე უნდა იყოს მიდრეკილი. თუ ეს პირობა არ დაკმაყოფილდა, საჭიროა ობიექტური ფუნქციის სათანადოდ გარდაქმნა (გამრავლება -1-ზე) და მინიმიზაციის პრობლემის გადაჭრა. ამოხსნის აღმოჩენის შემდეგ, ჩაანაცვლეთ ცვლადების მნიშვნელობები თავდაპირველ ფუნქციაში და გამოთვალეთ მისი მნიშვნელობა.
ალგებრული მეთოდის გამოყენებით პრობლემის გადაწყვეტა ოპტიმალურად ითვლება, როდესაც ყველა ძირითადი ცვლადის მნიშვნელობები არაუარყოფითია, ხოლო თავისუფალი ცვლადების კოეფიციენტები ობიექტური ფუნქციის განტოლებაში ასევე არაუარყოფითია. თუ ეს პირობები არ არის დაკმაყოფილებული, აუცილებელია უტოლობათა სისტემის ტრანსფორმაცია, ზოგიერთი ცვლადის გამოხატვა სხვების (თავისუფალი და ძირითადი ცვლადების შეცვლა) ზემოაღნიშნული შეზღუდვების მისაღწევად. ყველა თავისუფალი ცვლადის მნიშვნელობა ითვლება ნულამდე.
წრფივი პროგრამირების ამოცანების გადაჭრის ალგებრული მეთოდი ერთ-ერთი ყველაზე ეფექტური მეთოდია მცირე ზომის ამოცანების ხელით გადასაჭრელად. არ საჭიროებს არითმეტიკული გამოთვლების დიდ რაოდენობას. ამ მეთოდის მანქანური განხორციელება უფრო რთულია, ვიდრე, მაგალითად, სიმპლექსის მეთოდისთვის, რადგან ალგებრული მეთოდით ამოხსნის ალგორითმი გარკვეულწილად ევრისტიკულია და ამოხსნის ეფექტურობა დიდწილად დამოკიდებულია პირად გამოცდილებაზე.
უფასო ცვლადები
ჩიხი ქ - დაამატე. ნაკრები
არაუარყოფითი პირობები დაკმაყოფილებულია, შესაბამისად, ნაპოვნია ოპტიმალური გადაწყვეტა.
3. წრფივი პროგრამირების ამოცანის ამოხსნა სიმპლექსის ცხრილის გამოყენებით
ამოხსნა: მოდი, დავალება მივიყვანოთ სტანდარტულ ფორმაში სიმპლექსის ცხრილის გამოყენებით ამოხსნისთვის.
სისტემის ყველა განტოლებას ვამცირებთ ფორმამდე:
ჩვენ ვაშენებთ სიმპლექსის ცხრილს:
ცხრილის თითოეული უჯრედის ზედა კუთხეში შევიყვანთ კოეფიციენტებს განტოლებათა სისტემიდან;
ჩვენ ვირჩევთ მაქსიმალურ დადებით ელემენტს F მწკრივში, გარდა ამისა იქნება ზოგადი სვეტი;
იმისათვის, რომ ვიპოვოთ ზოგადი ელემენტი, ჩვენ ვაშენებთ კავშირს ყველა დადებითისთვის. 3/3; 9/1;- მინიმალური თანაფარდობა ხაზში x3. აქედან გამომდინარე - ზოგადი სტრიქონი და =3 - ზოგადი ელემენტი.
ჩვენ ვპოულობთ =1/=1/3. ჩვენ შემოვიყვანთ უჯრედის ქვედა კუთხეში, სადაც განლაგებულია ზოგადი ელემენტი;
ზოგადი ხაზის ყველა შეუვსებელ ქვედა კუთხეში შევიყვანთ მნიშვნელობის ნამრავლს უჯრედის ზედა კუთხეში;
აირჩიეთ ზოგადი ხაზის ზედა კუთხეები;
ზოგადი სვეტის ყველა ქვედა კუთხეში შევიყვანთ მნიშვნელობის ნამრავლს ზედა კუთხეში - და ვირჩევთ მიღებულ მნიშვნელობებს;
ცხრილის დარჩენილი უჯრები ივსება, როგორც შესაბამისი შერჩეული ელემენტების პროდუქტები;
შემდეგ ვაშენებთ ახალ ცხრილს, რომელშიც შებრუნებულია ზოგადი სვეტისა და მწკრივის ელემენტების უჯრედების აღნიშვნები (x2 და x3);
ყოფილი ზოგადი მწკრივისა და სვეტის ზედა კუთხეში იწერება მნიშვნელობები, რომლებიც ადრე ქვედა კუთხეში იყო;
წინა ცხრილის ამ უჯრედების ზედა და ქვედა კუთხის მნიშვნელობების ჯამი იწერება დარჩენილი უჯრედების ზედა კუთხეში.
4. წრფივი პროგრამირების ამოცანის ამოხსნა შესაძლებელი ამოხსნის მოძიებით
მოდით მივცეთ წრფივი ალგებრული განტოლებათა სისტემა:
შეგვიძლია ვივარაუდოთ, რომ ყველაფერი, წინააღმდეგ შემთხვევაში ვამრავლებთ შესაბამის განტოლებას -1-ზე.
ჩვენ შემოგთავაზებთ დამხმარე ცვლადებს:
ჩვენ ასევე შემოგთავაზებთ დამხმარე ფუნქციას
ჩვენ შევამცირებთ სისტემას შეზღუდვების (2) და პირობების მიხედვით.
განხორციელებული გადაწყვეტის პოვნის წესი: სისტემის (1) შესაძლო გადაწყვეტის საპოვნელად, ჩვენ ვამცირებთ ფორმას (3) შეზღუდვების ქვეშ (2), როგორც თავისუფალ უცნობებს ვიღებთ xj-ს, როგორც ძირითადს.
Simplex მეთოდით პრობლემის გადაჭრისას შეიძლება წარმოიშვას ორი შემთხვევა:
min f=0, მაშინ ყველა i უნდა იყოს ნულის ტოლი. და შედეგად მიღებული მნიშვნელობები xj იქნება სისტემის (1) შესაძლო გადაწყვეტა.
min f>0, ე.ი. თავდაპირველ სისტემას არ აქვს გამოსავალი.
წყაროს სისტემა:
გამოყენებულია წინა თემის პრობლემის პირობა.
მოდით დავამატოთ დამატებითი ცვლადები:
ნაპოვნია ორიგინალური ამოცანის დასაშვები გადაწყვეტა: x1 = 3, x2 = 3, F = -12. მიღებული შესაძლებელი გადაწყვეტის საფუძველზე ვპოულობთ ორიგინალური პრობლემის ოპტიმალურ გადაწყვეტას სიმპლექსის მეთოდით. ამისათვის ჩვენ ავაშენებთ ახალ სიმპლექს ცხრილს ზემოთ მოპოვებული ცხრილიდან მწკრივისა და დამხმარე ამოცანის სამიზნე ფუნქციის მქონე მწკრივის წაშლით:
აგებული სიმპლექსის ცხრილის გაანალიზებით, ჩვენ ვხედავთ, რომ საწყისი პრობლემის ოპტიმალური გადაწყვეტა უკვე ნაპოვნია (ობიექტური ფუნქციის შესაბამისი მწკრივის ელემენტები უარყოფითია). ამრიგად, დამხმარე პრობლემის გადაჭრისას ნაპოვნი შესაძლებელი გადაწყვეტა ემთხვევა თავდაპირველი პრობლემის ოპტიმალურ გადაწყვეტას:
6. წრფივი პროგრამირების ორმაგი პრობლემა
შეზღუდვების საწყისი სისტემა და პრობლემის ობიექტური ფუნქცია ნაჩვენებია ქვემოთ მოცემულ ფიგურაში.
შეზღუდვებით:
გამოსავალი: ჩვენ მივყავართ შეზღუდვების სისტემას სტანდარტულ ფორმაში:
ამ დავალების ორმაგი ამოცანა ასე გამოიყურება:
ორმაგი პრობლემა მოგვარდება სიმპლექსის მეთოდით.
მოდით გადავცვალოთ ობიექტური ფუნქცია ისე, რომ მინიმიზაციის პრობლემა გადაიჭრას და ჩავწეროთ შეზღუდვების სისტემა სტანდარტული ფორმით სიმპლექსის მეთოდით ამოსახსნელად.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??წთ
მოდით ავაშენოთ საწყისი სიმპლექსის ცხრილი ორმაგი LP პრობლემის გადასაჭრელად.
სიმპლექსის მეთოდის მეორე ნაბიჯი
ასე რომ, სიმპლექსის მეთოდის მესამე საფეხურზე მინიმიზაციის პრობლემის ოპტიმალური გადაწყვეტა იქნა ნაპოვნი შემდეგი შედეგებით: y2 = -7 /8, y1 = -11/8, Ф = 12. ორმაგი პრობლემის ობიექტური ფუნქცია, ჩვენ ვცვლით ძირითადი და თავისუფალი ცვლადების ნაპოვნი მნიშვნელობებს მაქსიმიზაციის ფუნქციაში:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
ვინაიდან პირდაპირი და ორმაგი ამოცანების ობიექტური ფუნქციის მნიშვნელობა ერთნაირია, პირდაპირი ამოცანის ამოხსნა ნაპოვნია და უდრის 12-ს.
Fmin \u003d Fmax \u003d -12
7. მთელი წრფივი პროგრამირების ამოცანის ამოხსნა „ტოტები და საზღვრები“ მეთოდით
მოდით გადავიტანოთ თავდაპირველი ამოცანა ისე, რომ მთელი რიცხვი არ დაკმაყოფილდეს ჩვეულებრივი მეთოდებით ამოხსნისას.
მთელი რიცხვითი პროგრამირების ამოცანის ამონახსნების საწყისი პოლიგონი.
მოდით ავაშენოთ შეზღუდვების ახალი სისტემა ტრანსფორმირებული ამოხსნის მრავალკუთხედისთვის.
შეზღუდვების სისტემას ვწერთ ტოლობის სახით, ალგებრული მეთოდით ამოხსნისთვის.
ამოხსნის შედეგად აღმოჩნდა ოპტიმალური დავალების გეგმა: x1 = 9/4, x2 = 5/2, F = -41/4. ეს გამოსავალი არ აკმაყოფილებს პრობლემაში დადგენილ მთლიანობის პირობას. თავდაპირველი ამოხსნის მრავალკუთხედს ვყოფთ ორ რეგიონად, მისგან 3 რეგიონის გამოკლებით შეიცვალა პრობლემის გადაწყვეტის პოლიგონი მოდით შევადგინოთ შეზღუდვების ახალი სისტემები ამოხსნის მრავალკუთხედის ჩამოყალიბებული უბნებისთვის. მარცხენა უბანი არის ოთხკუთხედი (ტრაპეცია). ამოხსნის მრავალკუთხედის მარცხენა რეგიონის შეზღუდვის სისტემა წარმოდგენილია ქვემოთ. შეზღუდვის სისტემა მარცხენა რეგიონისთვის მარჯვენა რეგიონი წარმოადგენს C წერტილს. სწორი გადაწყვეტილების ზონისთვის შეზღუდვების სისტემა წარმოდგენილია ქვემოთ. ახალი შეზღუდვის სისტემები არის ორი დამხმარე პრობლემა, რომლებიც უნდა გადაიჭრას ერთმანეთისგან დამოუკიდებლად. გადავჭრათ ამოხსნის მრავალკუთხედის მარცხენა რეგიონის მთელი რიცხვითი პროგრამირების პრობლემა. ამოხსნის შედეგად აღმოჩნდა ოპტიმალური დავალების გეგმა: x1 = 3, x2 = 3, F = -12. ეს გეგმა აკმაყოფილებს პრობლემაში მთელი ცვლადების მდგომარეობას და შეიძლება იქნას მიღებული, როგორც ოპტიმალური საცნობარო გეგმა თავდაპირველი მთელი რიცხვის წრფივი პროგრამირების პრობლემისთვის. აზრი არ აქვს გადაწყვეტის განხორციელებას სწორი გადაწყვეტის რეგიონისთვის. ქვემოთ მოყვანილი სურათი გვიჩვენებს ხის სახით მთელი რიცხვითი წრფივი პროგრამირების ამოცანის ამოხსნის პროგრესს. გომორის მეთოდით მთელი რიცხვითი წრფივი პროგრამირების ამოცანის ამოხსნის კურსი. ბევრ პრაქტიკულ გამოყენებაში დიდი ინტერესია მთელი რიცხვების პროგრამირების პრობლემა, რომელშიც მოცემულია წრფივი უტოლობების სისტემა და წრფივი ფორმა. საჭიროა ვიპოვოთ (1) სისტემის მთელი რიცხვი ამონახსნის, რომელიც ამცირებს ობიექტურ ფუნქციას F და ყველა კოეფიციენტი არის მთელი რიცხვები. მთელი რიცხვების პროგრამირების პრობლემის გადაჭრის ერთ-ერთი მეთოდი შემოგვთავაზა გომორიმ. მეთოდის იდეაა უწყვეტი ხაზოვანი პროგრამირების მეთოდების გამოყენება, კერძოდ, სიმპლექსის მეთოდი. 1) სიმპლექსის მეთოდის გამოყენებით განისაზღვრება ამოცანის (1), (2) ამონახსნი, რისთვისაც ამოღებულია მოთხოვნა, რომ ამონახვა იყოს მთელი რიცხვი; თუ ამონახსნი მთელი რიცხვი აღმოჩნდება, მაშინ მოიძებნება მთელი რიცხვის ამოცანის სასურველი ამოხსნაც; 2) წინააღმდეგ შემთხვევაში, თუ რომელიმე კოორდინატი არ არის მთელი რიცხვი, ამოცანის მიღებული ამოხსნა მოწმდება მთელი რიცხვის ამოხსნის არსებობის შესაძლებლობისთვის (მთლიანი წერტილების არსებობა დასაშვებ პოლიედრონში): თუ წილადის თავისუფალ წევრთან რომელიმე წრფეში, ყველა სხვა კოეფიციენტი აღმოჩნდება მთელი რიცხვები, მაშინ არ არის მთელი რიცხვები, წერტილები დასაშვებ პოლიედრონში და მთელი რიცხვის პროგრამირების პრობლემას არ აქვს გამოსავალი; წინააღმდეგ შემთხვევაში, დაინერგება დამატებითი წრფივი შეზღუდვა, რომელიც წყვეტს დასაშვებ პოლიედრონს ნაწილს, რომელიც არაპერსპექტიულია მთელი რიცხვითი პროგრამირების პრობლემის გადაწყვეტის მოსაძებნად; 3) დამატებითი წრფივი შეზღუდვის ასაგებად აირჩიეთ l-ე მწკრივი წილადი თავისუფალი წევრით და ჩაწერეთ დამატებითი შეზღუდვა სადაც და არის, შესაბამისად, კოეფიციენტების წილადი ნაწილები და თავისუფალი წევრი. მოდით შემოვიტანოთ დამხმარე ცვლადი შეზღუდვაში (3): მოდით განვსაზღვროთ კოეფიციენტები და შედის შეზღუდვაში (4): სადაც და არის უახლოესი ქვედა მთელი რიცხვები და შესაბამისად. გომორიმ დაამტკიცა, რომ ასეთი ნაბიჯების სასრული რაოდენობა იწვევს ხაზოვანი პროგრამირების პრობლემას, რომლის ამოხსნა არის მთელი რიცხვი და, შესაბამისად, სასურველი. ამოხსნა: ჩვენ ვამცირებთ წრფივი შეზღუდვების სისტემას და მიზნის ფუნქციას კანონიკურ ფორმამდე: მოდით განვსაზღვროთ წრფივი შეზღუდვების სისტემის ოპტიმალური გადაწყვეტა, დროებით გამოვრიცხოთ მთელი რიცხვი. ამისთვის ვიყენებთ სიმპლექსის მეთოდს. ქვემოთ მოყვანილი ცხრილები თანმიმდევრულად წარმოადგენენ პრობლემის საწყის გადაწყვეტას, ხოლო თავდაპირველი ცხრილის გარდაქმნები მოცემულია პრობლემის ოპტიმალური გადაწყვეტის მისაღებად: ლოგიკური LP ამოცანების ამოხსნა ბალაშის მეთოდით. დამოუკიდებლად შეადგინეთ ვარიანტი მთელი რიცხვითი წრფივი პროგრამირების ამოცანისთვის ლოგიკური ცვლადებით, შემდეგი წესების გათვალისწინებით: ამოცანა იყენებს მინიმუმ 5 ცვლადს, მინიმუმ 4 შეზღუდვას, შეზღუდვების კოეფიციენტები და ობიექტური ფუნქცია არჩეულია თვითნებურად, მაგრამ ასეთში. ისე, რომ შეზღუდვების სისტემა თავსებადია. ამოცანაა ZCLP-ის ამოხსნა ლოგიკური ცვლადებით ბალაშის ალგორითმის გამოყენებით და ამომწურავი ძიებით ამოცანის ამოხსნასთან დაკავშირებით გამოთვლითი სირთულის შემცირება. შეზღუდვების შესრულება F მნიშვნელობა ფილტრის შეზღუდვა: გაანგარიშების შემცირების განსაზღვრა ამომწურავი ძიების მეთოდით ამოცანის ამოხსნა არის 6*25=192 გამოთვლილი გამონათქვამი. ბალაშის მეთოდით ამოცანის ამოხსნა არის 3*6+(25-3)=47 გამოთვლილი გამონათქვამი. ამომწურავი ძიების მეთოდით პრობლემის გადაჭრასთან დაკავშირებით გამოთვლების სირთულის მთლიანი შემცირება არის. დასკვნა მუდმივად იხვეწება ახალი საინფორმაციო ტექნოლოგიების დანერგვის საინფორმაციო სისტემების დიზაინის პროცესი. სულ უფრო რთული სისტემები ხდება სისტემების ინჟინრების ყურადღების ცენტრში, რაც ართულებს ფიზიკური მოდელების გამოყენებას და ზრდის მათემატიკური მოდელების და სისტემების კომპიუტერული სიმულაციის მნიშვნელობას. მანქანების მოდელირება გახდა ეფექტური ინსტრუმენტი რთული სისტემების კვლევისა და დიზაინისთვის. მათემატიკური მოდელების აქტუალობა მუდმივად იზრდება მათი მოქნილობის, რეალური პროცესების ადეკვატურობის, თანამედროვე კომპიუტერების ბაზაზე დანერგვის დაბალი ღირებულების გამო. უფრო და უფრო მეტი შესაძლებლობა ეძლევა მომხმარებელს, ანუ სპეციალისტს კომპიუტერული ტექნოლოგიების საშუალებით მოდელირების სისტემების. მოდელირების გამოყენება განსაკუთრებით ეფექტურია ავტომატური სისტემების დიზაინის ადრეულ ეტაპებზე, როდესაც მცდარი გადაწყვეტილებების ღირებულება ყველაზე მნიშვნელოვანია. თანამედროვე გამოთვლითმა ინსტრუმენტებმა შესაძლებელი გახადა მნიშვნელოვნად გაზარდოს სისტემების შესწავლაში გამოყენებული მოდელების სირთულე, შესაძლებელი გახდა კომბინირებული, ანალიტიკური და სიმულაციური მოდელების აგება, რომლებიც ითვალისწინებენ რეალურ სისტემებში მომხდარ ფაქტორების მთელ მრავალფეროვნებას. ე.ი. მოდელების გამოყენება, რომლებიც უფრო ადეკვატურია შესასწავლი ფენომენების მიმართ. ლიტერატურა: 1. ლიაშჩენკო ი.ნ. ხაზოვანი და არაწრფივი პროგრამირება / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - კ .: "უმაღლესი სკოლა", 1975, 372 გვ. 2. დისციპლინაში „გამოყენებითი მათემატიკა“ საკურსო პროექტის განხორციელების გზამკვლევი სპეციალობის სტუდენტებისთვის „კომპიუტერული სისტემები და ქსელები“ სწავლის სრულ განაკვეთზე და ნახევარ განაკვეთზე სწავლების ფორმები / შემდგენელი: ი.ა.ბალაკირევა, ა.ვ.სკატკოვი - სევასტოპოლი: SevNTU Publishing House, 2003. - 15გვ. 3. დისციპლინის „გამოყენებითი მათემატიკა“ შესწავლის სახელმძღვანელო განყოფილება „გლობალური ძიების მეთოდები და ერთგანზომილებიანი მინიმიზაცია“ / შედ. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31s. 4. "გამოყენებითი მათემატიკა" დისციპლინის შესწავლის ინსტრუქციები სპეციალობის სტუდენტებისთვის "კომპიუტერული სისტემები და ქსელები" განყოფილება "მთლიანი წრფივი პროგრამირების ამოცანების ამოხსნა" განათლების სრული და კორესპონდენციური ფორმების / შემდგენელი: I.A. Balakireva, A.V. Skatkov - Sevastopol. : გამომცემლობა SevNTU, 2000. - 13გვ. 5. აკულიჩ ი.ლ. მათემატიკური პროგრამირება მაგალითებში და ამოცანებში: 6. პროკ. შემწეობა სტუდენტური მეურნეობისთვის. სპეციალისტი. უნივერსიტეტები.-მ.: უმაღლესი. სკოლა, 1986.- 319წ., ილ. 7. ანდრონოვი ს.ა. დიზაინის ოპტიმალური მეთოდები: ლექციის ტექსტი / SPbGUAP. SPb., 2001. 169 გვ.: ill. წრფივი პროგრამირების ამოცანების ამოხსნის ალგორითმი სიმპლექსის მეთოდით. წრფივი პროგრამირების ამოცანის მათემატიკური მოდელის აგება. ხაზოვანი პროგრამირების პრობლემის გადაჭრა Excel-ში. მოგების პოვნა და ოპტიმალური წარმოების გეგმა. საკურსო ნაშრომი, დამატებულია 21/03/2012 პრობლემის გრაფიკული გადაჭრა. მათემატიკური მოდელის შედგენა. ობიექტური ფუნქციის მაქსიმალური მნიშვნელობის განსაზღვრა. ამოხსნა სიმპლექსის მეთოდით კანონიკური წრფივი პროგრამირების პრობლემის ხელოვნური საფუძვლით. გადაწყვეტის ოპტიმალურობის შემოწმება. ტესტი, დამატებულია 04/05/2016 ხაზოვანი პროგრამირების თეორიული საფუძველი. წრფივი პროგრამირების ამოცანები, ამოხსნის მეთოდები. ოპტიმალური გადაწყვეტის ანალიზი. ერთინდექსის წრფივი პროგრამირების ამოცანის ამოხსნა. პრობლემის განცხადება და მონაცემების შეყვანა. მოდელის აგება და გადაწყვეტის ეტაპები. საკურსო ნაშრომი, დამატებულია 12/09/2008 მათემატიკური მოდელის აგება. წრფივი პროგრამირების პირდაპირი ამოცანის ამოხსნის მეთოდის შერჩევა, დასაბუთება და აღწერა სიმპლექსის მეთოდით, სიმპლექსის ცხრილის გამოყენებით. ორმაგი პრობლემის ფორმულირება და გადაწყვეტა. მოდელის ანალიზი მგრძნობელობისთვის. საკურსო ნაშრომი, დამატებულია 31.10.2014 საწარმოს მაქსიმალური მოგების გაზრდის მიზნით მათემატიკური მოდელის აგება, პრობლემის გრაფიკული გადაწყვეტა. პრობლემის გადაჭრა SOLVER დანამატის გამოყენებით. რესურსების რეზერვების ცვლილებების ანალიზი. ობიექტური ფუნქციის კოეფიციენტების ცვლილების ზღვრების განსაზღვრა. საკურსო ნაშრომი, დამატებულია 17.12.2014 მათემატიკური პროგრამირება. ხაზოვანი პროგრამირება. ხაზოვანი პროგრამირების პრობლემები. ხაზოვანი პროგრამირების პრობლემის გადაჭრის გრაფიკული მეთოდი. ხაზოვანი პროგრამირების პრობლემის ეკონომიკური ფორმულირება. მათემატიკური მოდელის აგება. საკურსო ნაშრომი, დამატებულია 13/10/2008 ხაზოვანი პროგრამირების პრობლემის გრაფიკული მეთოდით გადაჭრა, მისი გადამოწმება MS Excel-ში. პროგრამაში პრობლემის გადაჭრის შიდა სტრუქტურის ანალიზი. წარმოების გეგმის ოპტიმიზაცია. პრობლემის გადაჭრა სიმპლექსის მეთოდით. მრავალარხიანი რიგის სისტემა. ტესტი, დამატებულია 05/02/2012 წრფივი პროგრამირების ამოცანის ამოხსნა სიმპლექსის მეთოდით: ამოცანის დაყენება, ეკონომიკური და მათემატიკური მოდელის აგება. სატრანსპორტო პრობლემის გადაჭრა პოტენციალების მეთოდით: საწყისი საცნობარო გეგმის აგება, მისი ოპტიმალური მნიშვნელობის განსაზღვრა. ტესტი, დამატებულია 04/11/2012 ფორმულირება არაწრფივი პროგრამირების პრობლემის შესახებ. სტაციონარული წერტილების და მათი ტიპის განსაზღვრა. დონის ხაზების აგება, ობიექტური ფუნქციის სამგანზომილებიანი გრაფიკი და შეზღუდვები. პრობლემის გრაფიკული და ანალიტიკური გადაწყვეტა. მომხმარებლის სახელმძღვანელო და ალგორითმის სქემა. საკურსო ნაშრომი, დამატებულია 17.12.2012 წრფივი პროგრამირების ამოცანის ამოხსნის ანალიზი. მარტივი მეთოდი სიმპლექსის ცხრილების გამოყენებით. LP ამოცანების მოდელირება და გადაწყვეტა კომპიუტერზე. პრობლემის ოპტიმალური გადაწყვეტის ეკონომიკური ინტერპრეტაცია. ტრანსპორტის პრობლემის მათემატიკური ფორმულირება. მესამე რიგს ვყოფთ საკვანძო ელემენტზე 5-ის ტოლი, ვიღებთ ახალი ცხრილის მესამე რიგს. საბაზისო სვეტები შეესაბამება ერთ სვეტს. ცხრილის დარჩენილი მნიშვნელობების გაანგარიშება: "BP - ძირითადი გეგმა": ; "x1": "x5": ინდექსის მწკრივის მნიშვნელობები არაუარყოფითია, ამიტომ ვიღებთ ოპტიმალურ გადაწყვეტას: , ; პასუხი:წარმოებული პროდუქციის რეალიზაციიდან მაქსიმალური მოგება, რომელიც უდრის 160/3 ერთეულს, უზრუნველყოფილია მხოლოდ მეორე ტიპის პროდუქციის გამოშვებით 80/9 ერთეულის ოდენობით. მოცემულია არაწრფივი პროგრამირების პრობლემა. იპოვეთ ობიექტური ფუნქციის მაქსიმუმი და მინიმუმი გრაფიკულ-ანალიზური მეთოდის გამოყენებით. შეადგინეთ ლაგრანგის ფუნქცია და აჩვენეთ, რომ საკმარისი მინიმალური (მაქსიმალური) პირობები დაკმაყოფილებულია უკიდურეს წერტილებში. რადგან შიფრის ბოლო ციფრი არის 8, შემდეგ A=2; B=5. რადგან შიფრის ბოლო ციფრი არის 1, მაშინ უნდა აირჩიოთ დავალების ნომერი 1. გადაწყვეტილება: 1) დავხატოთ ფართობი, რომელსაც განსაზღვრავს უტოლობათა სისტემა. ეს ფართობი არის ABC სამკუთხედი წვეროების კოორდინატებით: A(0; 2); B(4; 6) და C(16/3; 14/3). ობიექტური ფუნქციის დონეები არის წრეები, რომლებიც ორიენტირებულია წერტილზე (2; 5). რადიუსების კვადრატები იქნება ობიექტური ფუნქციის მნიშვნელობები. შემდეგ ნახაზი აჩვენებს, რომ ობიექტური ფუნქციის მინიმალური მნიშვნელობა მიღწეულია H წერტილში, მაქსიმალური მნიშვნელობა არის A წერტილში ან C წერტილში. ობიექტური ფუნქციის მნიშვნელობა A წერტილში: ; ობიექტური ფუნქციის მნიშვნელობა C წერტილში: ; ეს ნიშნავს, რომ ფუნქციის მაქსიმალური მნიშვნელობა მიიღწევა A(0; 2) წერტილში და უდრის 13-ს. ვიპოვოთ H წერტილის კოორდინატები. ამისათვის განიხილეთ სისტემა: წრფე არის წრეზე ტანგენსი, თუ განტოლებას აქვს უნიკალური ამონახსნები. კვადრატულ განტოლებას აქვს უნიკალური ამონახსნი, თუ დისკრიმინანტი არის 0. 2) შეადგინეთ ლაგრანგის ფუნქცია მინიმალური ამოხსნის საპოვნელად: ზე x 1
=2.5;
x 2
=4.5
ჩვენ ვიღებთ: სისტემას აქვს გამოსავალი, ე.ი. საკმარისი ექსტრემალური პირობები დაკმაყოფილებულია. ჩვენ ვადგენთ Lagrange ფუნქციას მაქსიმალური ამოხსნის საპოვნელად: საკმარისი პირობები ექსტრემისთვის: ზე x 1
=0;
x 2
=2
ჩვენ ვიღებთ: სისტემას აქვს გამოსავალიც, ე.ი. საკმარისი ექსტრემალური პირობები დაკმაყოფილებულია. პასუხი:მიზნობრივი ფუნქციის მინიმუმი მიღწეულია თანხები გამოყოფილია ორ საწარმოს დერთეულები. როდესაც გამოყოფილია პირველ საწარმოზე ერთი წლით xსახსრების ერთეულები ის უზრუნველყოფს შემოსავალს კ 1
xერთეულები და მეორე საწარმოსთვის გამოყოფისას წსახსრების ერთეულები, ის უზრუნველყოფს შემოსავალს კ 1
წერთეულები. პირველი საწარმოს წლის ბოლოს სახსრების ნაშთი უდრის nxდა მეორესთვის ჩემი. როგორ გავანაწილოთ ყველა თანხა 4 წლის განმავლობაში ისე, რომ მთლიანი შემოსავალი იყოს ყველაზე დიდი? პრობლემის გადაჭრა დინამიური პროგრამირებით. i=8, k=1. A=2200; k 1 =6; k2=1; n=0.2; m=0.5. გადაწყვეტილება: 4 წლის მთელი პერიოდი დაყოფილია 4 ეტაპად, რომელთაგან თითოეული უდრის ერთ წელს. ეტაპები დავთვალოთ პირველი წლიდან დაწყებული. მოდით X k და Y k იყოს A და B საწარმოებისთვის შესაბამისად გამოყოფილი სახსრები k-ე ეტაპზე. მაშინ ჯამი X k + Y k =a k არის k - ამ ეტაპზე გამოყენებული სახსრების ჯამური რაოდენობა და დარჩენილი წინა ეტაპიდან k - 1. პირველ ეტაპზე გამოყენებულია ყველა გამოყოფილი თანხა და 1 =2200 ერთეული. შემოსავალი, რომელიც მიიღება k-ის ეტაპზე, როდესაც X k და Y k ერთეულები გამოიყოფა, იქნება 6X k + 1Y k. მოდით მაქსიმალური შემოსავალი მიღებული ბოლო ეტაპებზე დაწყებული k-დან - ეს ეტაპი არის f k (a k) ერთეული. მოდით დავწეროთ ბელმანის ფუნქციური განტოლება, რომელიც გამოხატავს ოპტიმალურობის პრინციპს: როგორიც არ უნდა იყოს საწყისი მდგომარეობა და საწყისი ამონახსნები, შემდგომი ამონახსნი უნდა იყოს ოპტიმალური საწყისი მდგომარეობის შედეგად მიღებული მდგომარეობის მიმართ: თითოეული ეტაპისთვის თქვენ უნდა აირჩიოთ მნიშვნელობა X k და მნიშვნელობა Y k=აკ- Xკ. ამის გათვალისწინებით, ჩვენ ვიპოვით შემოსავალს k-ე ეტაპზე: ბელმანის ფუნქციური განტოლება ასე გამოიყურება: განვიხილოთ ყველა ეტაპი, ბოლოდან დაწყებული. (რადგან წრფივი ფუნქციის მაქსიმუმი მიიღწევა სეგმენტის ბოლოს x 4 = a 4-ზე); ობიექტური ფუნქცია- რამდენიმე ცვლადის რეალური ან მთელი რიცხვი ფუნქცია, რომელიც ექვემდებარება ოპტიმიზაციას (მინიმიზაციას ან მაქსიმიზაციას) ოპტიმიზაციის პრობლემის გადაჭრის მიზნით. ტერმინი გამოიყენება მათემატიკურ პროგრამირებაში, ოპერაციების კვლევაში, ხაზოვან პროგრამირებაში, სტატისტიკური გადაწყვეტილების თეორიაში და მათემატიკის სხვა სფეროებში, ძირითადად გამოყენებითი ხასიათის, თუმცა ოპტიმიზაციის მიზანი შეიძლება იყოს თავად მათემატიკური პრობლემის გადაწყვეტაც. ობიექტური ფუნქციის გარდა, ოპტიმიზაციის პრობლემაში ცვლადებს შეიძლება დაექვემდებაროს შეზღუდვები ტოლობების ან უტოლობების სისტემის სახით. ზოგად შემთხვევაში, ობიექტური ფუნქციის არგუმენტები შეიძლება მითითებული იყოს თვითნებურ სიმრავლეებზე. განტოლებათა ნებისმიერი სისტემის ამოხსნის პრობლემა ( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\ დასაწყისი(მატრიცა)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\ბოლო(მატრიცა) )\ მართალია.) შეიძლება ჩამოყალიბდეს როგორც ობიექტური ფუნქციის მინიმიზაციის პრობლემა S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots,x_(M))\qquad(1)) თუ ფუნქციები გლუვია, მაშინ მინიმიზაციის პრობლემა შეიძლება მოგვარდეს გრადიენტური მეთოდებით. ნებისმიერი გლუვი ობიექტური ფუნქციისთვის შეიძლება გაუტოლდეს 0-ს (\displaystyle 0) ნაწილობრივი წარმოებულები ყველა ცვლადის მიმართ. ოპტიმალური ობიექტური ფუნქცია იქნება განტოლებათა ასეთი სისტემის ერთ-ერთი ამოხსნა. ფუნქციის (1) შემთხვევაში (\displaystyle (1)) ეს იქნება უმცირესი კვადრატების (LSM) განტოლებების სისტემა. თავდაპირველი სისტემის ნებისმიერი ამონახსნი არის უმცირესი კვადრატების სისტემის ამოხსნა. თუ ორიგინალური სისტემა არათანმიმდევრულია, მაშინ LSM სისტემა, რომელსაც ყოველთვის აქვს გამოსავალი, შესაძლებელს ხდის ორიგინალური სისტემის სავარაუდო ამოხსნის მიღებას. LSM სისტემის განტოლებათა რაოდენობა ემთხვევა უცნობთა რაოდენობას, რაც ზოგჯერ ხელს უწყობს ერთობლივი საწყისი სისტემების ამოხსნას. ობიექტური ფუნქციის კიდევ ერთი ცნობილი მაგალითია წრფივი ფუნქცია, რომელიც გვხვდება ხაზოვანი პროგრამირების ამოცანებში. კვადრატული ობიექტური ფუნქციისგან განსხვავებით, წრფივი ფუნქციის ოპტიმიზაცია შესაძლებელია მხოლოდ იმ შემთხვევაში, თუ არსებობს შეზღუდვები წრფივი ტოლობების ან უტოლობების სისტემის სახით. კომბინატორიული მიზნობრივი ფუნქციის ტიპიური მაგალითია მოგზაური გამყიდველის პრობლემის ობიექტური ფუნქცია. ეს ფუნქცია უდრის გრაფიკზე ჰამილტონის ციკლის ხანგრძლივობას. იგი მოცემულია გრაფიკის წვეროების n − 1 (\displaystyle n-1) პერმუტაციის სიმრავლეზე და განისაზღვრება გრაფიკის კიდეების სიგრძის მატრიცით. ასეთი პრობლემების ზუსტი გადაწყვეტა ხშირად მოდის ვარიანტების ჩამოთვლაზე. ხაზოვანი პროგრამირება არის მათემატიკური პროგრამირების ფილიალი, რომელიც სწავლობს ექსტრემალური ამოცანების გადაჭრის მეთოდებს, რომლებიც ხასიათდება ცვლადებსა და ხაზოვან კრიტერიუმს შორის წრფივი ურთიერთობით. ასეთი ამოცანები ფართო გამოყენებას პოულობს ადამიანის საქმიანობის სხვადასხვა სფეროში. ამ ტიპის პრობლემების სისტემატური შესწავლა დაიწყო 1939–1940 წლებში. ლ.ვ.-ის შემოქმედებაში. კანტოროვიჩი. ხაზოვანი პროგრამირების მათემატიკური ამოცანები მოიცავს სპეციფიკური წარმოების და ეკონომიკური სიტუაციების შესწავლას, რომლებიც ამა თუ იმ ფორმით არის განმარტებული, როგორც შეზღუდული რესურსების ოპტიმალური გამოყენების პრობლემა. ხაზოვანი პროგრამირების მეთოდებით გადაჭრილი ამოცანების დიაპაზონი საკმაოდ ფართოა, მაგალითად: წარმოების დაგეგმვისას რესურსების ოპტიმალური გამოყენების პრობლემა; ნარევების პრობლემა (პროდუქტების შემადგენლობის დაგეგმვა); საწყობებში შესანახად სხვადასხვა ტიპის პროდუქციის ოპტიმალური კომბინაციის პოვნის პრობლემა (ინვენტარის მართვა ან); სატრანსპორტო ამოცანები (საწარმოს ადგილმდებარეობის ანალიზი, საქონლის გადაადგილება). ხაზოვანი პროგრამირება არის მათემატიკური პროგრამირების ყველაზე განვითარებული და ფართოდ გამოყენებული განყოფილება (გარდა ამისა, მასში შედის: მთელი რიცხვი, დინამიური, არაწრფივი, პარამეტრული პროგრამირება). ეს აიხსნება შემდეგნაირად: დიდი რაოდენობის ეკონომიკური ამოცანების მათემატიკური მოდელები წრფივია საჭირო ცვლადების მიმართ; ამ ტიპის პრობლემები ამჟამად ყველაზე შესწავლილია. მისთვის შემუშავებულია სპეციალური მეთოდები, რომლებითაც წყდება ეს პრობლემები და შესაბამისი კომპიუტერული პროგრამები; ხაზოვანი პროგრამირების ბევრმა პრობლემამ, მოგვარებულმა, ფართო გამოყენება ჰპოვა; ზოგიერთი პრობლემა, რომელიც არ არის წრფივი თავდაპირველ ფორმულირებაში, რიგი დამატებითი შეზღუდვებისა და დაშვებების შემდეგ, შეიძლება გახდეს წრფივი ან შეიძლება შემცირდეს ისეთ ფორმამდე, რომ მათი გადაჭრა შესაძლებელია ხაზოვანი პროგრამირების მეთოდებით. ნებისმიერი წრფივი პროგრამირების ამოცანის ეკონომიკური და მათემატიკური მოდელი მოიცავს: ობიექტურ ფუნქციას, რომლის ოპტიმალური მნიშვნელობა (მაქსიმალური ან მინიმალური) უნდა მოიძებნოს; შეზღუდვები წრფივი განტოლებების ან უტოლობების სისტემის სახით; ცვლადების არანეგატიურობის მოთხოვნა. ზოგადად, მოდელი იწერება შემდეგნაირად: ობიექტური ფუნქცია (1.1) შეზღუდვების მიხედვით პრობლემა არის ფუნქციის (1.1) ოპტიმალური მნიშვნელობის პოვნა, რომელიც ექვემდებარება შეზღუდვებს (1.2) და (1.3). შეზღუდვების სისტემას (1.2) ეწოდება პრობლემის ფუნქციური შეზღუდვები, ხოლო შეზღუდვებს (1.3) - პირდაპირი შეზღუდვები. ვექტორს, რომელიც აკმაყოფილებს (1.2) და (1.3) შეზღუდვებს ეწოდება წრფივი პროგრამირების ამოცანის განხორციელებადი ამოხსნა (გეგმა). გეგმას, რომლისთვისაც ფუნქცია (1.1) აღწევს მაქსიმალურ (მინიმალურ) მნიშვნელობას, ოპტიმალური ეწოდება. სიმპლექსის მეთოდი შეიმუშავა და პირველად გამოიყენა ამოცანების გადასაჭრელად 1947 წელს ამერიკელმა მათემატიკოსმა ჯ.დანციგმა. ორგანზომილებიანი ხაზოვანი პროგრამირების ამოცანები წყდება გრაფიკულად. შემთხვევისთვის N=3 შეგვიძლია განვიხილოთ სამგანზომილებიანი სივრცე და ობიექტური ფუნქცია მიაღწევს თავის ოპტიმალურ მნიშვნელობას პოლიედრონის ერთ-ერთ წვეროზე. სტანდარტული სახით მოცემული LP ამოცანის დასაშვები ამოხსნა (დაშვებული გეგმა) არის რიცხვების მოწესრიგებული ნაკრები (x1, x2, ..., xn), რომელიც აკმაყოფილებს შეზღუდვებს; არის წერტილი n-განზომილებიან სივრცეში. დასაშვები გადაწყვეტილებების ნაკრები ქმნის LP პრობლემის დასაშვები გადაწყვეტილებების (SDR) არეალს. ODR არის ამოზნექილი მრავალკუთხედი (პოლიგონი). ზოგადად, როდესაც N-უცნობები მონაწილეობენ პრობლემაში, შეგვიძლია ვთქვათ, რომ შეზღუდვის პირობების სისტემით განსაზღვრული შესაძლებელი გადაწყვეტილებების ფართობი წარმოდგენილია ამოზნექილი პოლიედრონით n-განზომილებიან სივრცეში და მიზნის ოპტიმალური მნიშვნელობით. ფუნქცია მიიღწევა ერთ ან მეტ წვეროზე. ამონახსნის ეწოდება ძირითადი, თუ ყველა თავისუფალი ცვლადი ნულის ტოლია. საცნობარო გამოსავალი არის ძირითადი არაუარყოფითი გადაწყვეტა. დამხმარე ხსნარი შეიძლება იყოს არადეგენერაციული და გადაგვარებული. დამხმარე ამონახსნის ეწოდება არადეგენერატი, თუ მისი არა-ნულოვანი კოორდინატების რაოდენობა სისტემის რანგის ტოლია, წინააღმდეგ შემთხვევაში ის დეგენერატია. განხორციელებულ გადაწყვეტას, რომელშიც ობიექტური ფუნქცია აღწევს უკიდურეს მნიშვნელობას, ეწოდება ოპტიმალური და აღინიშნება ძალიან რთულია ამ პრობლემების გრაფიკულად გადაჭრა, როდესაც ცვლადების რაოდენობა 3-ზე მეტია. არსებობს ხაზოვანი პროგრამირების ამოცანების გადაჭრის უნივერსალური გზა, რომელსაც სიმპლექსის მეთოდს უწოდებენ. მარტივი მეთოდი არის უნივერსალური მეთოდი LP პრობლემების გადასაჭრელად, რომელიც არის განმეორებითი პროცესი, რომელიც იწყება ერთი გადაწყვეტით და საუკეთესო ვარიანტის ძიებაში მოძრაობს შესაძლებელი გადაწყვეტილებების არეალის კუთხის წერტილების გასწვრივ, სანამ არ მიაღწევს ოპტიმალურ მნიშვნელობას. . მისი გამოყენება შესაძლებელია ნებისმიერი წრფივი პროგრამირების პრობლემის გადასაჭრელად. სიმპლექსის მეთოდი ემყარება მიღებული ხსნარის თანმიმდევრული გაუმჯობესების იდეას. სიმპლექსის მეთოდის გეომეტრიული მნიშვნელობა მდგომარეობს იმაში, რომ თანმიმდევრულად გადავიდეს შეზღუდვის პოლიედრონის ერთი წვეროდან მეზობელზე, რომელშიც ობიექტური ფუნქცია იღებს საუკეთესო (ან თუნდაც არა ყველაზე უარეს) მნიშვნელობას, სანამ არ მოიძებნება ოპტიმალური ამონახსნები - წვერო, სადაც ოპტიმალური მნიშვნელობა მიღწეულია მიზნის ფუნქცია (თუ პრობლემას აქვს სასრული ოპტიმუმი). ამრიგად, კანონიკურ ფორმამდე დაყვანილი შეზღუდვების სისტემა (ყველა ფუნქციური შეზღუდვა თანასწორობის სახითაა), ადამიანი იპოვის ამ სისტემის ნებისმიერ ძირითად გადაწყვეტას, ზრუნავს მხოლოდ მის პოვნაზე რაც შეიძლება მარტივად. თუ პირველი ნაპოვნი ძირითადი გადაწყვეტა დასაშვები აღმოჩნდა, მაშინ ის მოწმდება ოპტიმალურად. თუ ეს არ არის ოპტიმალური, მაშინ ხდება გადასვლა სხვა, აუცილებლად დასაშვებ, ძირითად გადაწყვეტაზე. სიმპლექსის მეთოდი იძლევა გარანტიას, რომ ამ ახალი ამოხსნით, ობიექტური ფუნქცია, თუ ის არ აღწევს ოპტიმამს, მაშინ უახლოვდება მას (ან სულაც არ შორდება მას). ახალი დასაშვები ძირითადი ხსნარით, იგივე კეთდება მანამ, სანამ არ მოიძებნება ოპტიმალური გამოსავალი. სიმპლექსის მეთოდის გამოყენების პროცესი მოიცავს მისი სამი ძირითადი ელემენტის განხორციელებას: პრობლემის ზოგიერთი საწყისი შესაძლო ძირითადი გადაწყვეტის განსაზღვრის მეთოდი; საუკეთესო (უფრო ზუსტად, არა უარეს) გადაწყვეტაზე გადასვლის წესი; ნაპოვნი ამოხსნის ოპტიმალურობის შემოწმების კრიტერიუმი. Simplex მეთოდი მოიცავს რამდენიმე საფეხურს და შეიძლება ჩამოყალიბდეს როგორც მკაფიო ალგორითმი (მკაფიო ინსტრუქცია თანმიმდევრული ოპერაციების შესასრულებლად). ეს საშუალებას გაძლევთ წარმატებით დააპროგრამოთ და განახორციელოთ იგი კომპიუტერზე. მცირე რაოდენობის ცვლადების და შეზღუდვების პრობლემების გადაჭრა შესაძლებელია მარტივი მეთოდით ხელით. ოპტიმიზაცია. Ნაწილი 1 ოპტიმიზაციის მეთოდები საშუალებას გაძლევთ აირჩიოთ საუკეთესო დიზაინის ვარიანტი ყველა შესაძლო ვარიანტიდან. ბოლო წლებში დიდი ყურადღება დაეთმო ამ მეთოდებს და შედეგად, შეიქმნა არაერთი მაღალეფექტური ალგორითმი, რომელიც შესაძლებელს ხდის ციფრული კომპიუტერის გამოყენებით დიზაინის ოპტიმალური ვარიანტის პოვნას. ეს თავი ასახავს ოპტიმიზაციის თეორიის საფუძვლებს, განიხილავს ოპტიმალური გადაწყვეტილებების ალგორითმების აგების პრინციპებს, აღწერს ყველაზე ცნობილ ალგორითმებს და აანალიზებს მათ უპირატესობებსა და ნაკლოვანებებს. ლიტერატურაში ტერმინი „ოპტიმიზაცია“ ეხება პროცესს ან ოპერაციების თანმიმდევრობას, რომელიც საშუალებას გაძლევთ მიიღოთ დახვეწილი გადაწყვეტა. მიუხედავად იმისა, რომ ოპტიმიზაციის საბოლოო მიზანი არის საუკეთესო, ან „ოპტიმალური“ გადაწყვეტის პოვნა, ჩვეულებრივ, უნდა დაკმაყოფილდეს ცნობილი გადაწყვეტილებების გაუმჯობესებით და არა მათი სრულყოფით. ამიტომ, ოპტიმიზაცია უფრო მეტად აღიქმება, როგორც სრულყოფილებისკენ სწრაფვა, რომელიც, შესაძლოა, ვერ მიიღწევა. ზოგიერთი თვითნებური სისტემის გათვალისწინებით, რომელიც აღწერილია m განტოლებებით n უცნობით, შეგვიძლია გამოვყოთ პრობლემის სამი ძირითადი ტიპი. თუ m=n, პრობლემას ალგებრული ეწოდება. ასეთ პრობლემას ჩვეულებრივ აქვს ერთი გამოსავალი. თუ m>n, მაშინ პრობლემა ხელახლა არის განსაზღვრული და, როგორც წესი, გამოსავალი არ აქვს. საბოლოოდ, მ სანამ ოპტიმიზაციის საკითხების განხილვას გავაგრძელებთ, შემოგთავაზებთ რამდენიმე განმარტებას. დიზაინის პარამეტრები
ეს ტერმინი აღნიშნავს დამოუკიდებელ ცვლადის პარამეტრებს, რომლებიც სრულად და ცალსახად განსაზღვრავენ მოგვარებულ დიზაინის პრობლემას. დიზაინის პარამეტრები უცნობი სიდიდეებია, რომელთა მნიშვნელობები გამოითვლება ოპტიმიზაციის პროცესში. ნებისმიერი ძირითადი ან წარმოებული რაოდენობა, რომელიც ემსახურება სისტემის რაოდენობრივ აღწერას, შეიძლება იყოს დიზაინის პარამეტრები. ასე რომ, ეს შეიძლება იყოს სიგრძის, მასის, დროის, ტემპერატურის უცნობი მნიშვნელობები. დიზაინის პარამეტრების რაოდენობა ახასიათებს ამ დიზაინის პრობლემის სირთულის ხარისხს. როგორც წესი, დიზაინის პარამეტრების რაოდენობა აღინიშნება n-ით, ხოლო თავად დიზაინის პარამეტრები x-ით შესაბამისი ინდექსებით. ამრიგად, ამ პრობლემის n დიზაინის პარამეტრები აღინიშნა ობიექტური ფუნქცია
ეს არის გამოხატულება, რომლის ღირებულების ინჟინერი ცდილობს მაქსიმალურად ან მინიმუმამდე დაიყვანოს. ობიექტური ფუნქცია საშუალებას გაძლევთ რაოდენობრივად შეადაროთ ორი ალტერნატიული გადაწყვეტა. მათემატიკური თვალსაზრისით, ობიექტური ფუნქცია აღწერს ზოგიერთ (n + 1) - განზომილებიან ზედაპირს. მისი ღირებულება განისაზღვრება დიზაინის პარამეტრებით M=M(x 1, x 2,...,x n). ობიექტური ფუნქციის მაგალითები, რომლებიც ხშირად გვხვდება საინჟინრო პრაქტიკაში, არის ღირებულება, წონა, ძალა, ზომები, ეფექტურობა. თუ არსებობს მხოლოდ ერთი დიზაინის პარამეტრი, მაშინ ობიექტური ფუნქცია შეიძლება წარმოდგენილი იყოს მრუდით სიბრტყეზე (ნახ. 6.1). თუ არსებობს ორი დიზაინის პარამეტრი, მაშინ სამიზნე ფუნქცია წარმოდგენილი იქნება ზედაპირით სამი განზომილების სივრცეში (ნახ. 6.2). სამი ან მეტი დიზაინის პარამეტრით, ობიექტური ფუნქციით მითითებულ ზედაპირებს ჰიპერზედაპირები ეწოდება და მათი გამოსახვა შეუძლებელია. ჟენია ჩვეულებრივი საშუალებები. ობიექტური ფუნქციის ზედაპირის ტოპოლოგიური თვისებები მნიშვნელოვან როლს თამაშობს ოპტიმიზაციის პროცესში, რადგან მათზეა დამოკიდებული ყველაზე ეფექტური ალგორითმის არჩევანი. ობიექტურმა ფუნქციამ ზოგიერთ შემთხვევაში შეიძლება მიიღოს ყველაზე მოულოდნელი ფორმები. მაგალითად, ყოველთვის არ არის შესაძლებელი მისი გამოხატვა ნახ. 1. ერთგანზომილებიანი ობიექტური ფუნქცია. ნახ.6.2.ორგანზომილებიანი ობიექტური ფუნქცია. დახურული მათემატიკური ფორმა, სხვა შემთხვევაში შეიძლება იყოს ცალმხრივი გლუვი ფუნქცია. ობიექტურმა ფუნქციამ შეიძლება ზოგჯერ მოითხოვოს ტექნიკური მონაცემების ცხრილი (მაგალითად, ორთქლის მდგომარეობის ცხრილი) ან შეიძლება საჭირო გახდეს ექსპერიმენტის ჩატარება. ზოგიერთ შემთხვევაში, დიზაინის პარამეტრები იღებენ მხოლოდ მთელ მნიშვნელობებს. მაგალითად შეიძლება იყოს კბილების რაოდენობა მექანიზმში ან ჭანჭიკების რაოდენობა ფლანგში. ზოგჯერ დიზაინის პარამეტრებს აქვს მხოლოდ ორი მნიშვნელობა - დიახ ან არა. ოპტიმიზაციის პროცესში ძნელი გასათვალისწინებელია ისეთი ხარისხობრივი პარამეტრები, როგორიცაა მომხმარებელთა კმაყოფილება, სანდოობა, ესთეტიკა, რადგან მათი რაოდენობრივი დადგენა თითქმის შეუძლებელია. თუმცა, რა ფორმითაც არ უნდა იყოს წარმოდგენილი ობიექტური ფუნქცია, ის უნდა იყოს დიზაინის პარამეტრების ერთმნიშვნელოვანი ფუნქცია. ოპტიმიზაციის რიგ პრობლემებში საჭიროა ერთზე მეტი ობიექტური ფუნქციის დანერგვა. ზოგჯერ ერთი მათგანი შეიძლება შეუთავსებელი იყოს მეორესთან. ამის მაგალითია თვითმფრინავის დიზაინი, როდესაც საჭიროა ერთდროულად უზრუნველყოს მაქსიმალური სიძლიერე, მინიმალური წონა და მინიმალური ღირებულება. ასეთ შემთხვევებში, დიზაინერმა უნდა შემოიტანოს პრიორიტეტების სისტემა და მივანიჭოს რაიმე განზომილებიანი მულტიპლიკატორი თითოეულ ობიექტურ ფუნქციას. შედეგად, ჩნდება "კომპრომისის ფუნქცია", რომელიც საშუალებას იძლევა გამოიყენოს ერთი შედგენილი ობიექტური ფუნქცია ოპტიმიზაციის პროცესში. მინიმალური და მაქსიმალურის პოვნა
ზოგიერთი ოპტიმიზაციის ალგორითმი ადაპტირებულია მაქსიმუმის საპოვნელად, სხვები კი მინიმალური. თუმცა, მიუხედავად მოგვარებული ექსტრემალური პრობლემის ტიპისა, შეიძლება გამოყენებულ იქნას იგივე ალგორითმი, რადგან მინიმიზაციის პრობლემა ადვილად გადაიქცევა მაქსიმალურ პრობლემად ობიექტური ფუნქციის ნიშნის საპირისპიროდ შეცვლით. ეს ტექნიკა ილუსტრირებულია სურათზე 6.3. დიზაინის სივრცე
ეს არის ყველა n დიზაინის პარამეტრით განსაზღვრული არეალის სახელი. დიზაინის სივრცე არ არის ისეთი დიდი, როგორც შეიძლება ჩანდეს, რადგან ის ჩვეულებრივ შემოიფარგლება რამდენიმე პირობები, რომლებიც დაკავშირებულია პრობლემის ფიზიკურ არსთან. შეზღუდვები შეიძლება იყოს იმდენად ძლიერი, რომ დავალება არ იყოს ნახ.6.3 ობიექტური ფუნქციის ნიშნის საპირისპიროდ შეცვლა მაქსიმალური დავალება იქცევა მინიმალურ ამოცანად. დამაკმაყოფილებელი გამოსავალი. შეზღუდვები იყოფა ორ ჯგუფად: შეზღუდვები - თანასწორობები და შეზღუდვები - უტოლობები. შეზღუდვები - თანასწორობა
შეზღუდვები - თანასწორობები - არის დამოკიდებულება დიზაინის პარამეტრებს შორის, რომელიც უნდა იქნას გათვალისწინებული გადაწყვეტის პოვნისას. ისინი ასახავს ბუნების კანონებს, ეკონომიკას, უფლებებს, გაბატონებულ გემოვნებას და საჭირო მასალების ხელმისაწვდომობას. შეზღუდვების რაოდენობა - თანასწორობა შეიძლება იყოს ნებისმიერი. ჰგვანან C 1 (x 1 , x 2 ,..., x n) = 0, C 2 (x 1 , x 2 ,..., x n) = 0, .................. C j (x 1, x 2,...,x n)=0. თუ რომელიმე ამ ურთიერთობებიდან შეიძლება გადაწყდეს დიზაინის ერთ-ერთი პარამეტრის მიმართ, მაშინ ეს საშუალებას გაძლევთ გამორიცხოთ ეს პარამეტრი ოპტიმიზაციის პროცესიდან. ეს ამცირებს დიზაინის სივრცის ზომების რაოდენობას და ამარტივებს პრობლემის გადაჭრას. შეზღუდვები - უტოლობები
ეს არის განსაკუთრებული სახის შეზღუდვა, რომელიც გამოხატულია უტოლობებით. ზოგადად, მათი რიცხვი შეიძლება იყოს ნებისმიერი და ყველა მათგანს აქვს ფორმა z 1 r 1 (x 1 , x 2 ,..., x n) Z 1 z 2 r 2 (x 1 , x 2 ,..., x n) Z 2 ....................... z k r k (x 1 , x 2 ,...,x n) Z k უნდა აღინიშნოს, რომ ძალიან ხშირად, შეზღუდვების გამო, ობიექტური ფუნქციის ოპტიმალური მნიშვნელობა არ მიიღწევა იქ, სადაც მის ზედაპირს აქვს ნულოვანი გრადიენტი. ხშირად საუკეთესო გამოსავალი არის დიზაინის დომენის ერთ-ერთ საზღვარზე. ადგილობრივი ოპტიმალური
ეს არის წერტილის სახელწოდება საპროექტო სივრცეში, სადაც ობიექტურ ფუნქციას აქვს ყველაზე დიდი მნიშვნელობა მის მნიშვნელობებთან შედარებით, მის უშუალო სამეზობლოში არსებულ ყველა სხვა წერტილში. ნახ.6.4 თვითნებურ ობიექტურ ფუნქციას შეიძლება ჰქონდეს რამდენიმე ადგილობრივი ოპტიმა. ნახ. სურათი 6.4 გვიჩვენებს ერთგანზომილებიან ობიექტურ ფუნქციას, რომელსაც აქვს ორი ლოკალური ოპტიმა. ხშირად დიზაინის სივრცე შეიცავს ბევრ ლოკალურ ოპტიმას და ზრუნვა უნდა იქნას მიღებული, რომ პირველი არ შეცდეს პრობლემის ოპტიმალურ გადაწყვეტაში. გლობალური ოპტიმუმი
გლობალური ოპტიმუმი არის ოპტიმალური გადაწყვეტა მთელი დიზაინის სივრცისთვის. ის უკეთესია, ვიდრე ადგილობრივი ოპტიმის შესაბამისი ყველა სხვა გადაწყვეტა და სწორედ ამას ეძებს დიზაინერი. შესაძლებელია საპროექტო სივრცის სხვადასხვა ნაწილში განლაგებული რამდენიმე თანაბარი გლობალური ოპტიმის შემთხვევა. როგორ არის დასმული ოპტიმიზაციის პრობლემა, საუკეთესოდ ჩანს მაგალითით. მაგალითი 6.1
მოდით, საჭირო გახდეს მართკუთხა კონტეინერის დაპროექტება 1 მ მოცულობით, რომელიც განკუთვნილია შეუფუთავი ბოჭკოს ტრანსპორტირებისთვის. სასურველია, რომ რაც შეიძლება ნაკლები მასალა დაიხარჯოს ასეთი კონტეინერების წარმოებაზე (კედლის მუდმივი სისქის გათვალისწინებით, ეს ნიშნავს, რომ ზედაპირის ფართობი უნდა იყოს მინიმალური), რადგან ეს უფრო იაფი იქნება. იმისათვის, რომ კონტეინერის ასაღებად მოსახერხებელი იყოს, მისი სიგანე უნდა იყოს მინიმუმ 1,5 მ. მოდით ჩამოვაყალიბოთ ეს პრობლემა ოპტიმიზაციის ალგორითმის გამოსაყენებლად მოსახერხებელი ფორმით. დიზაინის პარამეტრები: x 1 , x 2 , x 3 . ობიექტური ფუნქცია (რომელიც მინიმუმამდე უნდა შემცირდეს) არის კონტეინერის გვერდითი ზედაპირის ფართობი: A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2. შეზღუდვა - თანასწორობა: მოცულობა \u003d x 1 x 2 x 3 \u003d 1 მ3. შეზღუდვა - უთანასწორობა: ხაზოვანი პროგრამირება (LP)არის მათემატიკური პროგრამირების ერთ-ერთი განყოფილება - დისციპლინა, რომელიც სწავლობს ექსტრემალურ (ოპტიმიზაციის) ამოცანებს და შეიმუშავებს მათ გადაჭრის მეთოდებს. ოპტიმიზაციის პრობლემაარის მათემატიკური პრობლემა, რომელიც შედგება ობიექტური ფუნქციის ოპტიმალური (ანუ მაქსიმალური ან მინიმალური) მნიშვნელობის პოვნაში, ხოლო ცვლადების მნიშვნელობები უნდა მიეკუთვნებოდეს დასაშვები მნიშვნელობების გარკვეულ არეალს (ODV). ზოგადად, მათემატიკური პროგრამირების ექსტრემალური პრობლემის ფორმულირება მოიცავს ფუნქციის უდიდესი ან უმცირესი მნიშვნელობის განსაზღვრას, ე.წ. ობიექტური ფუნქცია, პირობებში (შეზღუდვები) , სადაც და მოცემულია ფუნქციები და მოცემულია მუდმივები. ამავდროულად, შეზღუდვები თანასწორობისა და უტოლობების სახით განსაზღვრავს შესაძლებელი გადაწყვეტილებების სიმრავლეს (რეგიონს) და ე.წ. დიზაინის პარამეტრები. მათემატიკური პროგრამირების ფუნქციებისა და ამოცანების ტიპის მიხედვით იყოფა რამდენიმე კლასად (წრფივი, არაწრფივი, ამოზნექილი, მთელი რიცხვი, სტოქასტური, დინამიური პროგრამირება და ა.შ.). AT ზოგადი ხედი LP პრობლემას აქვს შემდეგი ფორმა: , სადაც , , მოცემულია მუდმივები. ფუნქციას (5.1) ეწოდება ობიექტური ფუნქცია; სისტემები (5.2), (5.3) - შეზღუდვების სისტემით; პირობა (5.4) არის საპროექტო პარამეტრების არანეგატიურობის პირობა. დიზაინის პარამეტრების ნაკრები, რომელიც აკმაყოფილებს შეზღუდვებს (5.2), (5.3) და (5.4) ე.წ. მისაღები გადაწყვეტაან გეგმა. ოპტიმალური გადაწყვეტაან ოპტიმალური გეგმა LP პრობლემას ეწოდება შესაძლებელი გადაწყვეტა, რომელშიც ობიექტური ფუნქცია (5.1) იღებს ოპტიმალურ (მაქსიმალურ ან მინიმალურ) მნიშვნელობას. სტანდარტული დავალება LP ეწოდება ობიექტური ფუნქციის (5.1) მაქსიმალური (მინიმალური) მნიშვნელობის პოვნის პრობლემას (5.2) და (5.4) პირობებში, სადაც , , ე.ი. იმათ. შეზღუდვები მხოლოდ უტოლობების სახით (5.2) და დიზაინის ყველა პარამეტრი აკმაყოფილებს არაუარყოფითობის პირობას და არ არსებობს პირობები ტოლობის სახით: კანონიკური (მთავარი) დავალება LP ეწოდება ობიექტური ფუნქციის (5.1) მაქსიმალური (მინიმალური) მნიშვნელობის პოვნის პრობლემას (5.3) და (5.4) პირობებში, სადაც , , ე.ი. იმათ. შეზღუდვები მხოლოდ ტოლობის სახით (5.3) და დიზაინის ყველა პარამეტრი აკმაყოფილებს არაუარყოფითობის პირობას და არ არსებობს პირობები უტოლობის სახით: კანონიკური LP პრობლემა ასევე შეიძლება დაიწეროს მატრიცული და ვექტორული ფორმით. კანონიკური LP ამოცანის მატრიცულ ფორმას აქვს შემდეგი ფორმა: კანონიკური LP ამოცანის ვექტორული ფორმა. თუ არსებობს მხოლოდ ერთი შემზღუდველი ფაქტორი (მაგალითად, მწირი მანქანა), გამოსავალი შეგიძლიათ იპოვოთ მარტივი ფორმულების გამოყენებით (იხილეთ ბმული სტატიის დასაწყისში). თუ არსებობს რამდენიმე შემზღუდველი ფაქტორი, გამოიყენება ხაზოვანი პროგრამირების მეთოდი. ხაზოვანი პროგრამირებაეს არის სახელწოდება მენეჯმენტის მეცნიერებაში გამოყენებული ინსტრუმენტების ერთობლიობას. ეს მეთოდი წყვეტს მწირი რესურსების განაწილების პრობლემას კონკურენტ აქტივობებს შორის, რათა მაქსიმალურად ან მინიმუმამდე დაიყვანოს გარკვეული რიცხვითი მნიშვნელობა, როგორიცაა ზღვრული მოგება ან ხარჯები. ბიზნესში, ის შეიძლება გამოყენებულ იქნას ისეთ სფეროებში, როგორიცაა წარმოების დაგეგმვა მოგების მაქსიმიზაციისთვის, კომპონენტების შერჩევა ხარჯების შესამცირებლად, საინვესტიციო პორტფელის შერჩევა მაქსიმალური მომგებიანობისთვის, საქონლის ტრანსპორტირების ოპტიმიზაცია მანძილების შესამცირებლად, პერსონალის განაწილება სამუშაო ეფექტურობის გაზრდის მიზნით და სამუშაოს დაგეგმვა. დროის დაზოგვის მიზნით. ჩამოტვირთეთ შენიშვნა ში, ნახატები ფორმატში ხაზოვანი პროგრამირება გულისხმობს განსახილველი პრობლემის მათემატიკური მოდელის აგებას. ამის შემდეგ გამოსავალი შეგიძლიათ იხილოთ გრაფიკულად (განხილულია ქვემოთ), Excel-ის (ცალკე განხილული) ან სპეციალიზებული კომპიუტერული პროგრამების გამოყენებით. შესაძლოა მათემატიკური მოდელის აგება წრფივი პროგრამირების ყველაზე რთული ნაწილია, რომელიც მოითხოვს განსახილველი პრობლემის გადატანას ცვლადების, განტოლებებისა და უტოლობების სისტემაში - პროცესი, რომელიც საბოლოოდ დამოკიდებულია ადამიანის უნარებზე, გამოცდილებაზე, შესაძლებლობებსა და ინტუიციაზე. მოდელის შემდგენელი. განვიხილოთ ხაზოვანი პროგრამირების მათემატიკური მოდელის აგების მაგალითი ნიკოლაი კუზნეცოვი მართავს მცირე მექანიკურ ქარხანას. მომავალ თვეში ის გეგმავს ორი პროდუქტის (A და B) წარმოებას, რისთვისაც კონკრეტული ზღვრული მოგება, შესაბამისად, 2500 და 3500 რუბლს შეადგენს. ორივე პროდუქტის წარმოება მოითხოვს დამუშავების, ნედლეულის და შრომის ხარჯებს (ნახ. 1). A პროდუქტის თითოეული ერთეულის დასამზადებლად გამოიყოფა 3 საათი მანქანათმშენებლობა, 16 ერთეული ნედლეული და 6 ერთეული შრომა. B განყოფილების შესაბამისი მოთხოვნებია 10, 4 და 6. ნიკოლაი პროგნოზირებს, რომ მომავალ თვეში მას შეუძლია უზრუნველყოს 330 საათი დამუშავება, 400 ერთეული ნედლეული და 240 ერთეული სამუშაო. წარმოების პროცესის ტექნოლოგია ისეთია, რომ B პროდუქტის მინიმუმ 12 ერთეული უნდა იყოს წარმოებული ნებისმიერ თვეში. ბრინჯი. 1. რესურსების გამოყენება და უზრუნველყოფა ნიკოლაის სურს შექმნას მოდელი, რათა დადგინდეს პროდუქციის A და B ერთეულების რაოდენობა, რომლებიც უნდა აწარმოოს მომდევნო თვეში, რათა მაქსიმალურად გაზარდოს ზღვრული მოგება. ხაზოვანი მოდელი შეიძლება აშენდეს ოთხ ეტაპად. ეტაპი 1. ცვლადების განმარტება არის სამიზნე ცვლადი (მოდით ავღნიშნოთ Z), რომელიც უნდა იყოს ოპტიმიზირებული, ანუ მაქსიმიზებული ან მინიმუმამდე დაყვანილი (მაგალითად, მოგება, შემოსავალი ან ხარჯები). ნიკოლაი ცდილობს ზღვრული მოგების მაქსიმიზაციას, ამიტომ სამიზნე ცვლადია: Z = მთლიანი ზღვრული მოგება (რუბლით) მიღებული მომდევნო თვეში A და B პროდუქტების წარმოების შედეგად. არსებობს მრავალი უცნობი უცნობი ცვლადი (მოდით აღვნიშნოთ ისინი x 1, x 2, x 3 და ა.შ.), რომელთა მნიშვნელობები უნდა განისაზღვროს ობიექტური ფუნქციის ოპტიმალური მნიშვნელობის მისაღებად, რაც, ჩვენს შემთხვევაში, არის მთლიანი ზღვრული მოგება. ეს წვლილის ზღვარი დამოკიდებულია წარმოებული პროდუქტების A და B რაოდენობაზე. ამ რაოდენობების მნიშვნელობები უნდა გამოითვალოს და, შესაბამისად, ისინი მოდელში სასურველი ცვლადებია. ასე რომ, აღვნიშნოთ: x 1 = მომდევნო თვეში წარმოებული A პროდუქტის ერთეულების რაოდენობა. x 2 = მომდევნო თვეში წარმოებული B პროდუქტის ერთეულების რაოდენობა. ძალიან მნიშვნელოვანია ყველა ცვლადის მკაფიოდ განსაზღვრა; განსაკუთრებული ყურადღება მიაქციეთ გაზომვის ერთეულებს და დროის პერიოდს, რომელსაც ეხება ცვლადები. სცენა. 2. ობიექტური ფუნქციის აგება ობიექტური ფუნქცია არის წრფივი განტოლება, რომელიც უნდა იყოს მაქსიმალურად ან მინიმუმამდე. იგი შეიცავს სამიზნე ცვლადს გამოხატულს სასურველი ცვლადების მიხედვით, ანუ Z გამოხატულია x 1 , x 2 ... წრფივი განტოლების სახით. ჩვენს მაგალითში, თითოეული წარმოებული პროდუქტი A მოაქვს 2500 რუბლს. ზღვრული მოგება, ხოლო x 1 ერთეული A პროდუქტის წარმოებაში, ზღვრული მოგება იქნება 2500 * x 1. ანალოგიურად, ზღვრული მოგება x 2 ერთეული B პროდუქტის წარმოებიდან იქნება 3500 * x 2. ამრიგად, მომდევნო თვეში მიღებული ჯამური ზღვრული მოგება x 1 ერთეული A პროდუქტის და x 2 ერთეული B პროდუქტის წარმოების გამო, ანუ მიზნობრივი ცვლადი Z იქნება: Z = 2500 * x 1 + 3500 * x 2 ნიკოლაი ცდილობს მაქსიმალურად გაზარდოს ეს მაჩვენებელი. ამრიგად, ობიექტური ფუნქცია ჩვენს მოდელში არის: მაქსიმუმი Z = 2500 * x 1 + 3500 * x 2 სცენა. 3. შეზღუდვების განმარტება შეზღუდვები არის წრფივი განტოლებების და/ან უტოლობების სისტემა, რომელიც ზღუდავს საჭირო ცვლადების მნიშვნელობებს. ისინი მათემატიკურად ასახავს რესურსების ხელმისაწვდომობას, ტექნოლოგიურ ფაქტორებს, მარკეტინგულ პირობებს და სხვა მოთხოვნებს. შეზღუდვები შეიძლება იყოს სამი სახის: "ნაკლები ან ტოლი", "დიდი ან ტოლი", "მკაცრად ტოლი". ჩვენს მაგალითში, პროდუქტები A და B წარმოებისთვის საჭიროებს დამუშავების დროს, ნედლეულს და შრომას და ამ რესურსების ხელმისაწვდომობა შეზღუდულია. ამ ორი პროდუქტის წარმოების მოცულობა (ანუ მნიშვნელობები x 1 / 2) შესაბამისად შემოიფარგლება იმით, რომ წარმოების პროცესში საჭირო რესურსების რაოდენობა არ შეიძლება აღემატებოდეს ხელმისაწვდომს. განვიხილოთ სიტუაცია მანქანის დამუშავების დროს. A პროდუქტის თითოეული ერთეულის წარმოებას სჭირდება სამსაათიანი მანქანა დამუშავება, ხოლო თუ x 1 ერთეული იწარმოება, მაშინ დაიხარჯება ამ რესურსის 3 * x 1 საათი. B პროდუქტის თითოეული ერთეულის წარმოებას სჭირდება 10 საათი და, შესაბამისად, თუ x 2 პროდუქტი იწარმოება, მაშინ საჭირო იქნება 10 * x 2 საათი. ამრიგად, მანქანის დროის ჯამური რაოდენობა, რომელიც საჭიროა x 1 ერთეული პროდუქტის A და x 2 ერთეული პროდუქტის B წარმოებისთვის არის 3 * x 1 + 10 * x 2. მანქანის მთლიანი დრო არ შეიძლება აღემატებოდეს 330 საათს. მათემატიკურად ეს ასე იწერება: 3 * x 1 + 10 * x 2 ≤ 330 მსგავსი მოსაზრებები ვრცელდება ნედლეულსა და შრომაზე, რაც საშუალებას იძლევა ჩამოწეროთ კიდევ ორი შეზღუდვა: 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 და ბოლოს, უნდა აღინიშნოს, რომ არსებობს პირობა, რომლის მიხედვითაც უნდა დამზადდეს მინიმუმ 12 ერთეული პროდუქტი B: ეტაპი 4. არაუარყოფითობის პირობების წერა საჭირო ცვლადები არ შეიძლება იყოს უარყოფითი რიცხვები, რომლებიც უნდა დაიწეროს როგორც უტოლობები x 1 ≥ 0 და x 2 ≥ 0. ჩვენს მაგალითში მეორე პირობა ზედმეტია, რადგან ზემოთ დადგინდა, რომ x 2 არ შეიძლება იყოს 12-ზე ნაკლები. ნიკოლაის წარმოების პრობლემის სრული ხაზოვანი პროგრამირების მოდელი შეიძლება დაიწეროს შემდეგნაირად: მაქსიმიზაცია: Z = 2500 * x 1 + 3500 * x 2 იმ პირობით, რომ: 3 * x 1 + 10 * x 2 ≤ 330 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 განვიხილოთ ხაზოვანი პროგრამირების პრობლემის გადაჭრის გრაფიკული მეთოდი. ეს მეთოდი შესაფერისია მხოლოდ ორი საჭირო ცვლადის მქონე პრობლემებისთვის. მეთოდის საჩვენებლად გამოყენებული იქნება ზემოთ აგებული მოდელი. გრაფიკზე ღერძები წარმოადგენს ორ უცნობ ცვლადს (ნახ. 2). არ აქვს მნიშვნელობა, რომელი ცვლადი რომელ ღერძზე გამოსახოს. მნიშვნელოვანია აირჩიოთ მასშტაბი, რომელიც საბოლოოდ მოგცემთ საშუალებას შექმნათ ვიზუალური დიაგრამა. ვინაიდან ორივე ცვლადი უნდა იყოს არაუარყოფითი, მხოლოდ 1-ლი კვადრატი შედგენილია. ბრინჯი. 2. ხაზოვანი პროგრამირების გრაფიკის ღერძები განვიხილოთ, მაგალითად, პირველი შეზღუდვა: 3 * x 1 + 10 * x 2 ≤ 330. ეს უტოლობა აღწერს ფართობს ხაზის ქვემოთ: 3 * x 1 + 10 * x 2 = 330. ეს წრფე კვეთს x ღერძს 1. x 2 \u003d 0-ზე, ანუ განტოლება ასე გამოიყურება: 3 * x 1 + 10 * 0 \u003d 330 და მისი ამოხსნა: x 1 \u003d 330 / 3 \u003d 110 ანალოგიურად, ჩვენ ვიანგარიშებთ გადაკვეთის წერტილებს x 1 და x 2 ღერძებთან ყველა შეზღუდვის პირობებისთვის: გრაფიკულად, პირველი შეზღუდვა ნაჩვენებია ნახ. 3. ბრინჯი. 3. პირველი შეზღუდვისთვის შესაძლებელი გადაწყვეტილებების დომენის აგება ნებისმიერი წერტილი არჩეულ სამკუთხედში ან მის საზღვრებში შეესაბამება ამ შეზღუდვას. ასეთ წერტილებს უწოდებენ მართებულს, ხოლო წერტილებს სამკუთხედის გარეთ - არასწორი. ანალოგიურად, ჩვენ ასახავს დანარჩენ შეზღუდვებს დიაგრამაზე (ნახ. 4). მნიშვნელობები x 1 და x 2 დაჩრდილულ ზონაში ან შიგნით ABCDE შეესაბამება მოდელის ყველა შეზღუდვას. ასეთ რეგიონს დასაშვები გადაწყვეტილებების დომენი ეწოდება. ბრინჯი. 4. მთლიანი მოდელისთვის შესაძლებელი გადაწყვეტილებების არეალი ახლა, შესაძლებელი გადაწყვეტილებების მიდამოში, აუცილებელია განვსაზღვროთ მნიშვნელობები x 1 და x 2, რომლებიც მაქსიმალურ Z-ს. ამისათვის, ობიექტური ფუნქციის განტოლებაში: Z = 2500 * x 1 + 3500 * x 2 ჩვენ ვყოფთ (ან ვამრავლებთ) კოეფიციენტებს x 1-მდე და x 2-მდე იმავე რიცხვით, ისე რომ მიღებული მნიშვნელობები მოხვდეს გრაფიკზე ნაჩვენები დიაპაზონში; ჩვენს შემთხვევაში, ასეთი დიაპაზონი არის 0-დან 120-მდე; ასე რომ, კოეფიციენტები შეიძლება დაიყოს 100-ზე (ან 50-ზე): Z = 25x 1 + 35x 2 შემდეგ მიანიჭეთ Z მნიშვნელობას ტოლი კოეფიციენტების ნამრავლის x 1 და x 2-მდე (25 * 35 = 875): 875 = 25 x 1 + 35 x 2 და ბოლოს, იპოვნეთ წრფის გადაკვეთის წერტილები x 1 და x 2 ღერძებით: მოდით გამოვსახოთ ეს სამიზნე განტოლება გრაფიკზე ისევე, როგორც შეზღუდვები (ნახ. 5): ბრინჯი. 5. ობიექტური ფუნქციის (შავ წერტილოვანი ხაზი) გამოყენება შესაძლებელი გადაწყვეტილებების არეალზე Z მნიშვნელობა მუდმივია ობიექტური ფუნქციის ხაზში. x 1 და x 2 მნიშვნელობების საპოვნელად, რომლებიც მაქსიმალურ Z-ს, საჭიროა პარალელურად გადაიტანოთ ობიექტური ფუნქციის ხაზი ისეთ წერტილში დასაშვები გადაწყვეტილებების არეალის საზღვრებში, რომელიც მდებარეობს მაქსიმუმ. მანძილი ობიექტური ფუნქციის საწყისი ხაზიდან მაღლა და მარჯვნივ, ანუ C წერტილამდე (ნახ. 6). ბრინჯი. 6. ობიექტური ფუნქციის ხაზმა მაქსიმუმს მიაღწია შესაძლებელი ამონახსნების რეგიონში (C წერტილში) შეიძლება დავასკვნათ, რომ ოპტიმალური გადაწყვეტა განთავსდება გადაწყვეტილების არეალის ერთ-ერთ უკიდურეს წერტილში. რომელში, ეს დამოკიდებული იქნება ობიექტური ფუნქციის დახრილობაზე და იმაზე, თუ რა პრობლემას ვწყვეტთ: მაქსიმიზაციას თუ მინიმიზაციას. ამრიგად, არ არის აუცილებელი ობიექტური ფუნქციის დახატვა - საჭიროა მხოლოდ x 1 და x 2 მნიშვნელობების დადგენა თითოეულ უკიდურეს წერტილში დიაგრამიდან წაკითხვით ან შესაბამისი წყვილი განტოლებების ამოხსნით. აღმოჩენილი x 1 და x 2 მნიშვნელობები შემდეგ ჩანაცვლდება ობიექტურ ფუნქციაში Z-ის შესაბამისი მნიშვნელობის გამოსათვლელად. ოპტიმალური გამოსავალი არის ის, რომელშიც მიიღება Z-ის მაქსიმალური მნიშვნელობა მაქსიმიზაციის პრობლემის გადაჭრისას, ხოლო მინიმალური. მინიმიზაციის პრობლემის გადაჭრისას. მოდით განვსაზღვროთ, მაგალითად, x 1 და x 2-ის მნიშვნელობები C წერტილში. გაითვალისწინეთ, რომ წერტილი C არის ხაზების გადაკვეთაზე: 3x 1 + 10x 2 = 330 და 6x 1 + 6x 2 = 240. განტოლებათა ამ სისტემის ამოხსნა იძლევა: x 1 = 10, x 2 = 30. გაანგარიშების შედეგები შესაძლებელი ამონახსნების ფართობის ყველა წვეროზე მოცემულია ცხრილში: ამრიგად, ნიკოლაი კუზნეცომ მომდევნო თვისთვის უნდა დაგეგმოს 10 ელემენტი A და 30 ელემენტი B წარმოება, რაც მას საშუალებას მისცემს მიიღოს ზღვრული მოგება 130 ათასი რუბლი. მოკლედ, ხაზოვანი პროგრამირების ამოცანების გადაჭრის გრაფიკული მეთოდის არსი შეიძლება ასე ჩამოყალიბდეს: საკონტროლო სამუშაო დისციპლინაზე: "ოპტიმალური გადაწყვეტილებების მეთოდები" ვარიანტი ნომერი 8 1.
ხაზოვანი პროგრამირების ამოცანის ამოხსნა გრაფიკული მეთოდით. იპოვეთ ფუნქციის მაქსიმუმი და მინიმალური მოცემული შეზღუდვების მიხედვით: გადაწყვეტილება აუცილებელია ვიპოვოთ ობიექტური ფუნქციის მინიმალური მნიშვნელობა და მაქსიმალური, შეზღუდვების სისტემის მიხედვით: 9x1 +3x2 ≥30, (1) X 1 + x 2 ≤4, (2) x 1 + x 2 ≤8, (3) ავაშენოთ დასაშვები გადაწყვეტილებების დომენი, ე.ი. გრაფიკულად ამოხსნის უტოლობათა სისტემას. ამისთვის ვაშენებთ თითოეულ სწორ ხაზს და განვსაზღვრავთ უტოლობებით მოცემულ ნახევრად სიბრტყეებს (ნახევარი სიბრტყეები აღინიშნება მარტივი ასოებით). ნახევრად სიბრტყეების კვეთა იქნება ფართობი, რომლის წერტილების კოორდინატები აკმაყოფილებს ამოცანის შეზღუდვების სისტემის უტოლობათა პირობას. ავღნიშნოთ ამოხსნის მრავალკუთხედის რეგიონის საზღვრები. ავაშენოთ F = 0 ფუნქციის მნიშვნელობის შესაბამისი სწორი ხაზი: F = 2x 1 +3x 2 = 0. ობიექტური ფუნქციის კოეფიციენტებისგან შედგენილი გრადიენტის ვექტორი მიუთითებს F(X-ის მინიმიზაციის მიმართულებაზე). ვექტორის დასაწყისი არის წერტილი (0; 0), დასასრული არის წერტილი (2; 3). გადავიტანოთ ეს ხაზი პარალელურად. ვინაიდან ჩვენ გვაინტერესებს მინიმალური გადაწყვეტა, ჩვენ გადავაადგილებთ სწორ ხაზს დანიშნულ არეზე პირველ შეხებამდე. დიაგრამაზე ეს ხაზი მითითებულია წერტილოვანი ხაზით. პირდაპირ განტოლებათა სისტემის ამოხსნის შემდეგ მივიღებთ: x 1 = 3,3333, x 2 = 0. სად ვიპოვოთ ობიექტური ფუნქციის მინიმალური მნიშვნელობა: . განვიხილოთ პრობლემის ობიექტური ფუნქცია. ავაშენოთ F = 0 ფუნქციის მნიშვნელობის შესაბამისი სწორი ხაზი: F = 2x 1 +3x 2 = 0. ობიექტური ფუნქციის კოეფიციენტებისგან შედგენილი გრადიენტის ვექტორი მიუთითებს F(X-ის მაქსიმიზაციის მიმართულებაზე). ვექტორის დასაწყისი არის წერტილი (0; 0), დასასრული არის წერტილი (2; 3). გადავიტანოთ ეს ხაზი პარალელურად. ვინაიდან ჩვენ გვაინტერესებს მაქსიმალური გადაწყვეტა, სწორ ხაზს გადავაადგილებთ დანიშნული უბნის ბოლო შეხებამდე. დიაგრამაზე ეს ხაზი მითითებულია წერტილოვანი ხაზით. პირდაპირ სად ვიპოვოთ ობიექტური ფუნქციის მაქსიმალური მნიშვნელობა: . პასუხი: 2
.
ამოხსენით წრფივი პროგრამირების ამოცანა სიმპლექსის მეთოდით: გადაწყვეტილება წრფივი პროგრამირების პირდაპირი ამოცანა გადავჭრათ სიმპლექსის მეთოდით, სიმპლექსის ცხრილის გამოყენებით. მოდით განვსაზღვროთ ობიექტური ფუნქციის მინიმალური მნიშვნელობა პირველი საცნობარო გეგმის ასაგებად, ჩვენ ვამცირებთ უტოლობათა სისტემას განტოლებათა სისტემამდე დამატებითი ცვლადების შემოღებით. მნიშვნელობის პირველ უტოლობაში (≥) შემოგვაქვს ძირითადი ცვლადი x 3
მინუს ნიშნით. მნიშვნელობის მე-2 უტოლობაში (≤) შემოგვაქვს ძირითადი ცვლადი x 4
. მე-3 მნიშვნელობის უტოლობაში (≤), შემოგვაქვს ძირითადი ცვლადი x 5 . შემოვიტანოთ ხელოვნური ცვლადები მინიმუმზე დავალების დასაყენებლად ობიექტურ ფუნქციას ვწერთ შემდეგნაირად: . ობიექტურ ფუნქციაში შეყვანილი ხელოვნური ცვლადების გამოყენებისთვის დაწესებულია ეგრეთ წოდებული M-ის ჯარიმა, ძალიან დიდი დადებითი რიცხვი, რომელიც ჩვეულებრივ არ არის მითითებული. მიღებულ საფუძველს ეწოდება ხელოვნური, ხოლო ამოხსნის მეთოდს ეწოდება ხელოვნური ბაზის მეთოდი. უფრო მეტიც, ხელოვნური ცვლადები არ არის დაკავშირებული ამოცანის შინაარსთან, მაგრამ ისინი საშუალებას გაძლევთ შექმნათ საწყისი წერტილი და ოპტიმიზაციის პროცესი აიძულებს ამ ცვლადებს მიიღონ ნულოვანი მნიშვნელობები და უზრუნველყონ ოპტიმალური გადაწყვეტის დასაშვებობა. განტოლებიდან გამოვხატავთ ხელოვნურ ცვლადებს: x 6 \u003d 4-x 1 -x 2 +x 3, რომელსაც ვანაცვლებთ ობიექტურ ფუნქციაში: ან. კოეფიციენტების მატრიცა მოდით ამოხსნათ განტოლებათა სისტემა ძირითადი ცვლადების მიმართ: x 6
, x 4
, x 5.
თუ დავუშვებთ, რომ თავისუფალი ცვლადები არის 0, ჩვენ ვიღებთ პირველ საბაზისო ხაზს: X1 = (0,0,0,2,10,4) ძირითადი გამოსავალი ეწოდება დასაშვებს, თუ ის არაუარყოფითია. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 4
x 5
მიმდინარე საბაზისო არ არის ოპტიმალური, რადგან ინდექსის მწკრივში არის დადებითი კოეფიციენტები. ჩვენ ავირჩევთ x 2 ცვლადის შესაბამის სვეტს წამყვანად, რადგან ეს არის ყველაზე დიდი კოეფიციენტი. გამოთვალეთ მნიშვნელობები დ მე ამიტომ მე-2 ხაზი ლიდერობს. გამხსნელი ელემენტი უდრის (2) და მდებარეობს წამყვანი სვეტისა და წინა რიგის გადაკვეთაზე. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 4
x 5
ჩვენ ვქმნით სიმპლექსის ცხრილის შემდეგ ნაწილს. x 4 ცვლადის ნაცვლად, x 2 ცვლადი შევა გეგმა 1-ში. 1 გეგმაში x 2 ცვლადის შესაბამისი ხაზი მიიღება გეგმის 0 სტრიქონის x 4 წრფის ყველა ელემენტის RE=2 ჩამრთველ ელემენტზე გაყოფით. განმსაზღვრელი ელემენტის ადგილას ვიღებთ 1. x 2 სვეტის დარჩენილ უჯრედებში ვწერთ ნულებს. ამრიგად, ახალ გეგმაში ივსება 1 სტრიქონი x 2 და სვეტი x 2. ახალი გეგმის 1-ის ყველა სხვა ელემენტი, ინდექსის მწკრივის ელემენტების ჩათვლით, განისაზღვრება მართკუთხედის წესით. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 2
x 5
1 1/2 +1 1/2 მ მიმდინარე საბაზისო არ არის ოპტიმალური, რადგან ინდექსის მწკრივში არის დადებითი კოეფიციენტები. ჩვენ ვირჩევთ x 1 ცვლადის შესაბამის სვეტს წამყვანად, რადგან ეს არის ყველაზე დიდი კოეფიციენტი. გამოთვალეთ მნიშვნელობები დ მერიგების მიხედვით, როგორც გაყოფის კოეფიციენტი: აქედან გამომდინარე, პირველი ხაზი ლიდერობს. გადამწყვეტი ელემენტი უდრის (1 1/2) და მდებარეობს წამყვანი სვეტისა და წამყვანი მწკრივის კვეთაზე. x 1
x 2
x 3
x 4
x 5
x 6
x 6
1
1
/
2
x 2
x 5
-1
1
/
2
+1
1
/
2
მ ჩვენ ვქმნით სიმპლექსის ცხრილის შემდეგ ნაწილს. x 6 ცვლადის ნაცვლად, ცვლადი x 1 ჩართული იქნება გეგმა 2-ში. ჩვენ ვიღებთ ახალ სიმპლექს ცხრილს: x 1
x 2
x 3
x 4
x 5
x 6
x 1
x 2
x 5
ინდექსის რიგის არცერთი მნიშვნელობა არ არის დადებითი. ამიტომ, ეს ცხრილი განსაზღვრავს ოპტიმალურ დავალების გეგმას. სიმპლექსის ცხრილის საბოლოო ვერსია: x 1
x 2
x 3
x 4
x 5
x 6
x 1
x 2
x 5
ვინაიდან ოპტიმალურ გადაწყვეტაში არ არის ხელოვნური ცვლადები (ისინი ნულის ტოლია), ეს გამოსავალი შესაძლებელია. ოპტიმალური გეგმა შეიძლება დაიწეროს შემდეგნაირად: x 1 \u003d 2, x 2 \u003d 2:. უპასუხე: 3.
კომპანია „სამი მსუქანი“ ეწევა ხორცის კონსერვის მიწოდებას ქალაქის სხვადასხვა კუთხეში მდებარე სამი საწყობიდან სამ მაღაზიამდე. საწყობებში არსებული დაკონსერვებული საკვების მარაგი, ასევე მაღაზიებიდან შეკვეთების მოცულობა და მიწოდების ტარიფები (ჩვეულებრივ ფულად ერთეულებში) წარმოდგენილია სატრანსპორტო ცხრილში. იპოვეთ სატრანსპორტო გეგმა, რომელიც უზრუნველყოფს ყველაზე ნაკლებ ფულადი ხარჯებს (შეასრულეთ ორიგინალური სატრანსპორტო გეგმა "ჩრდილო-დასავლეთი კუთხის" მეთოდით). გადაწყვეტილება მოდით შევამოწმოთ პრობლემის გადაჭრის აუცილებელი და საკმარისი პირობა: ბალანსის პირობა დაცულია. მარაგებს თანაბარ საჭიროებებს. ამიტომ ტრანსპორტის პრობლემის მოდელი დახურულია. შევიტანოთ საწყისი მონაცემები განაწილების ცხრილში. საჭიროებებს ჩრდილო-დასავლეთი კუთხის მეთოდის გამოყენებით ავაშენებთ სატრანსპორტო ამოცანის პირველ საბაზისო გეგმას. გეგმის შევსება იწყება ზედა მარცხენა კუთხიდან. სასურველი ელემენტია 4. ამ ელემენტისთვის მარაგები არის 300, საჭიროებები 250. ვინაიდან მინიმალური არის 250, გამოვაკლებთ მას: . 300 - 250 = 50
250 - 250 = 0
სასურველი ელემენტია 2. ამ ელემენტისთვის მარაგები არის 50, საჭიროებები 400. ვინაიდან მინიმალური არის 50, გამოვაკლებთ მას: . 50 - 50 = 0
400 - 50 = 350
სასურველი ელემენტია 5. ამ ელემენტისთვის მარაგები არის 300, საჭიროებები 350. ვინაიდან მინიმალური არის 300, გამოვაკლებთ მას: 300 - 300 = 0
350 - 300 = 50
სასურველი ელემენტია 3. ამ ელემენტისთვის მარაგები არის 200, საჭიროებები 50. ვინაიდან მინიმალური არის 50, გამოვაკლებთ მას: 200 - 50 = 150
50 - 50 = 0
სასურველი ელემენტია 6. ამ ელემენტისთვის მარაგები არის 150, საჭიროებები 150. ვინაიდან მინიმალური არის 150, გამოვაკლებთ მას: 150 - 150 = 0
150 - 150 = 0
საჭიროებებს
მსგავსი დოკუმენტები
;
; 
;
; 
.
.
დავალება ნომერი 2
ó
ó 
მერე 
; ; 
- ფუნქციის მინიმალური მნიშვნელობა.
ó 
ó 
ó 
; ; მაქსიმალური ობიექტური ფუნქცია მიიღწევა როცა 
; .
დავალება ნომერი 3
მაგალითები
გლუვი ფუნქციები და განტოლებათა სისტემები
ხაზოვანი პროგრამირება
კომბინაციური ოპტიმიზაცია
თავი 1. ხაზოვანი პროგრამირების ძირითადი ამოცანის გამოთქმა
ხაზოვანი პროგრამირება
(1.2) არაუარყოფითი მოთხოვნები
(1.3) სადაც x ჯ– ცვლადები (უცნობი);
- ხაზოვანი პროგრამირების ამოცანის კოეფიციენტები.1.2. წრფივი პროგრამირების ამოცანების გადაჭრის მარტივი მეთოდი
.6.1 შესავალი
6.2 ოპტიმიზაციის თეორიის საფუძვლები
X1, x2, x3,...,xn.
ხაზოვანი პროგრამირების პრობლემები
, (5.1)
, , (5.2)
, (5.3) , , , (5.5)
. ,
.
მისაღები დიაპაზონი
ნებადართული მნიშვნელობების ლიმიტი
გადაკვეთა x ღერძთან 1
გადაკვეთა x ღერძთან 2
3 * x 1 + 10 * x 2 ≤ 330
3 * x 1 + 10 * x 2 = 330
x 1 = 110; x 2 = 0
x 1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400
16 * x 1 + 4 * x 2 = 400
x 1 = 25; x 2 = 0
x 1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240
6 * x 1 + 6 * x 2 = 240
x 1 = 40; x 2 = 0
x 1 = 0; x 2 = 40
x 2 ≥ 12
x 2 = 12
არ კვეთს; გადის x ღერძის 1-ის პარალელურად
x 1 = 0; x 2 = 12
Წერტილი
მნიშვნელობა x 1
მნიშვნელობა x 2
Z \u003d 2500x 1 + 3500x 2
მაგრამ
22
12
97 000
AT
20
20
120 000
თან
10
30
130 000
დ
0
33
115 500
ე
0
12
42 000
,
.
კვეთს რეგიონს C წერტილში. ვინაიდან C წერტილი მიიღება (4) და (1) წრფეების გადაკვეთის შედეგად, მაშინ მისი კოორდინატები აკმაყოფილებს ამ წრფეების განტოლებებს: 
.
კვეთს რეგიონს B წერტილში. ვინაიდან B წერტილი მიიღება (2) და (3) წრფეების გადაკვეთის შედეგად, მაშინ მისი კოორდინატები აკმაყოფილებს ამ წრფეების განტოლებებს: 
.
და 
.
.
შემდეგი პირობებით - შეზღუდვები: 
.
: 1-ელ ტოლობაში შემოგვაქვს ცვლადი x 6
;
განტოლებათა ამ სისტემას აქვს ფორმა: 
.
და აირჩიეთ მათგან ყველაზე პატარა: min(4: 1, 2: 2, 10: 2) = 1.
და მათგან ვირჩევთ უმცირესს: წთ (3: 1 1/2, -, 8: 2) = 2.
,
.
=
300 + 300 + 200 = 800 .
=
250 + 400 + 150 = 800.
