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

განვიხილოთ წრფივი პროგრამირების ძირითადი პრობლემა (LPP): იპოვნეთ x1, x2,…, xn ცვლადების არასასურველი მნიშვნელობები, რომლებიც აკმაყოფილებენ m პირობებს - ტოლობები

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

მარტივად, ჩავთვლით, რომ ყველა პირობა (1) წრფივად დამოუკიდებელია (r \u003d მ) და ამ ვარაუდის მიხედვით ვიმსჯელებთ.

X1, x2,…, xn არა უარყოფითი მნიშვნელობების სიმრავლე, რომელიც აკმაყოფილებს პირობებს (1), ეწოდება LPLP- ის დასაშვებ ხსნარს. ოპტიმალური ამოხსნა არის დასაშვები გადაწყვეტილებების მიღება, რომელიც მაქსიმალურად ზრდის ფუნქციას (2). საჭიროა ოპტიმალური გადაწყვეტის პოვნა.

ამ პრობლემას ყოველთვის აქვს გამოსავალი? არა ყოველთვის.

LPP არ არის გადაწყვეტილი (არ აქვს ოპტიმალური გადაწყვეტა):

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

სურათი 1 - შეზღუდვების სისტემის შეუსაბამობა

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

დიაგრამა 2 - ობიექტური ფუნქციის შეუზღუდაობა გადაწყვეტილებების ნაკრებზე

LPP მოგვარებადია:

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

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

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

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

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

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

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

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

ამ მეთოდის გამოყენება სადიპლომო პროექტში LP პრობლემის გადასაჭრელად განპირობებულია შემდეგი ფაქტორებით:

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

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

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

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

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

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

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

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

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

ამრიგად, მარტივი მეთოდის გამოყენება ორ ეტაპად იყოფა:

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

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

შემდეგი შესაძლო გადაწყვეტაზე გადასვლის ალგორითმი ასეთია:

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

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

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

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

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

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

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

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

C1x1 + c2x2 + ... + cnxn\u003e მაქს (წთ); - შეზღუდვები:

a11x1 + a12x2 + ... + a1nxn (? \u003d?) b1,

a21x1 + a22x2 + ... + a2nxn (? \u003d?) b2

am1x1 + am2x2 + ... + amnxn (? \u003d?) ბმ;

უარყოფითი მოთხოვნა:

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

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

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

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

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

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

4x1 + 6x2? 120,

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

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

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

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

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

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

(1.2)

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

OZLP- ის ZLP- ის კანონიკურ ფორმაში მოყვანა:

ორიგინალი მინიმიზაციის პრობლემის მაქსიმიზაციის პრობლემით ჩანაცვლება (ან პირიქით, მაქსიმიზაციის პრობლემა მინიმიზაციის პრობლემით), საკმარისია ობიექტური ფუნქციის გამრავლება "-1" -ზე და მოძებნოთ მიღებული ფუნქციის მაქსიმალური (მინიმუმი);

თუ შეზღუდვებს შორის უთანასწორობაა, მაშინ დამატებითი არაუარყოფითი ცვლადების შემოღებით x n +1 ≥ 0 ისინი გადადიან ტოლობებად:

უთანასწორობა ა მე 1 x 1 +…+ა წელს x n ბ მე შეიცვალა თანასწორობით ა მე 1 x 1 +…+ა წელს x ნ + x n +1 \u003d ბ მე,

უთანასწორობა ა მე 1 x 1 +…+ა წელს x ნ ბ მე შეიცვალა თანასწორობით ა მე 1 x 1 +…+ა წელს x ნ + x n +1 \u003d ბ მე;

თუ რაიმე ცვლადი x კ არ გააჩნია ნიშნის შეზღუდვები, შემდეგ იგი შეიცვლება (ობიექტურ ფუნქციაში და ყველა შეზღუდვაში) ორ ახალ არაუარყოფით ცვლადს შორის სხვაობით: x კ = x" კ – x” კ , სად x" კ ≥ 0. x” კ ≥ 0.

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

LPP– ს ორი უცნობი ფორმა აქვს:

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

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

გამოსავალი დონის უთანასწორობა ა მე 1 x 1 +ა მე 2 x 2 ≤ ბ i არის ორი ნახევრად თვითმფრინავიდან, რომელთაკენაც მიდის ხაზი ა მე 1 x 1 +ა მე 2 x 2 = ბ ამ უტოლობის შესაბამისი i ყოფს კოორდინატთა სიბრტყეს. იმის დასადგენად, რომელია ორი ნახევარპლანტიდან რომელია ამოხსნების რეგიონი, საკმარისია შეცვალოთ რომელიმე წერტილის კოორდინატები, რომელიც არ არის განლაგებული გამყოფი ხაზის უთანასწორობაში:

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

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

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

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

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

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

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

გრაფიკული მეთოდის ალგორითმი LPP– ს გადასაჭრელად ორი უცნობით:

ააშენეთ SDT.

ნორმალური ვექტორის აგება გ = (გ 1 , გ 2) და დონის ხაზი დან 1 x 1 +დან 2 x 2 \u003d 0 წარმოშობის გავლით და ვექტორის პერპენდიკულარულად ფრომიდან.

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

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

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

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

მარტივი მეთოდი LPP– ს გადაჭრისთვის

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

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

LPP– ს ოპტიმალური გადაწყვეტა SDT– ის ერთ – ერთი კუთხის წერტილია. ODR კუთხის წერტილები ალგებრულად წარმოადგენს LPP შეზღუდვის სისტემის ზოგიერთ ძირითად (დამხმარე) გადაწყვეტილებას.

LPP– ის ძირითადი (დამხმარე) გადაწყვეტა ეწოდება ასეთ დასაშვებ გადაწყვეტილებას X 0 =( x 10 , x 20 , ..., x მ 0, 0, ... 0), რომელთათვისაც პირობების ვექტორები (შეზღუდვების სისტემაში უცნობი კოეფიციენტების სვეტები) ხაზობრივად დამოუკიდებელია.

ნულოვანი კოორდინატები x 10 , x 20 , ..., x მ 0 გამოსავალი X 0 ეწოდება ძირითად ცვლადებს, ამოხსნის დანარჩენ კოორდინატებს X 0 - უფასო ცვლადები. მითითების ამოხსნის არაზულოვანი კოორდინატების რაოდენობა არ შეიძლება იყოს წოდებაზე მეტი რ LPP შეზღუდვების სისტემები (ხაზოვანი დამოუკიდებელი განტოლებების რაოდენობა LPP შეზღუდვების სისტემაში). გარდა ამისა, ვივარაუდებთ, რომ LPP შეზღუდვების სისტემა შედგება წრფივი დამოუკიდებელი განტოლებებისგან, ე.ი. რ = მ.

მარტივი მეთოდის მნიშვნელობა მოიცავს LPP– ის ერთი საცნობარო ხსნარიდან მეორეში (ანუ SDT– ის ერთი კუთხიდან მეორეზე) მიზანმიმართულ გადასვლაში ექსტრემალური მიმართულებით და შედგება ეტაპების თანმიმდევრობით:

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

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

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

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

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

მოდით LPP მიეცეს კანონიკური ფორმით (1.2) და პირობით

ბ მე ≥ 0, მე=1,2,…,მ, (1.3)

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

თავდაპირველი პრობლემა (1.2), (1.3) შემცირდეს ფორმაში, სადაც ძირითადი ცვლადები იქნება x 1 , x 2 , ..., x m გამოხატულია თავისუფალი ცვლადების მიხედვით x მ + 1 , x მ + 2 , ..., x ნ

(1.4)

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

ცხრილი 1

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

ალგორითმიიმპლექსის მეთოდი:

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

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

3. გადაჭრის ხაზისა და ამოხსნის სვეტის გადაკვეთაზე არის გადაჭრის ელემენტი.

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

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

ცხრილი 2

6. ცხრილი 2-ის ელემენტი, რომელიც შეესაბამება 1 ცხრილის ნებადართულ ელემენტს, ტოლია ნებართვის ელემენტის ორმხრივი.

7. ცხრილი 2-ის მწკრივის ელემენტები, რომლებიც შეესაბამება ცხრილი 1-ის სანებართვო ხაზის ელემენტებს, მიიღება 1-ლი ცხრილის შესაბამისი ელემენტების დაყოფის ელემენტზე დაყოფით.

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

9. დანარჩენი ელემენტები გამოითვლება მართკუთხედის წესი: გონებრივად დახაზეთ მართკუთხედი ცხრილში 1, რომლის ერთი მწვერვალი ემთხვევა ამოხსნის ელემენტს (Re), ხოლო მეორე ელემენტს, რომელსაც ვეძებთ; მოდით, აღვნიშნოთ ელემენტი ახალ ცხრილში 2 – დან (Ne) –მდე და ელემენტი, რომელიც ძველ ცხრილში 1 – ზე დგას (Se). დანარჩენი ორი წვერი A და B ასრულებს ფორმას მართკუთხედისკენ. მაშინ მე -2 ცხრილიდან Ne- ის ძებნილი ელემენტი Ne \u003d Se - A * B / Re უდრის.

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

11. თუ ამოხსნის სვეტში ყველა ელემენტი უარყოფითია, მაშინ პრობლემას არ აქვს ამოხსნები (მინიმუმი არ არის მიღწეული).

LPP– ს გადაჭრის ხელოვნური საფუძვლის მეთოდი

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

ხელოვნური საფუძვლის მეთოდი ემყარება ხელოვნური საფუძვლის ცვლადების დანერგვას y 1 , y 2 ,…, y მ, რომელთანაც LPP შეზღუდვების სისტემაა (2.2)

(1.5)

შეიძლება გადაკეთდეს ფორმაში

(1.6)

სისტემები (1.5) და (1.6) ექვივალენტური იქნება, თუ ყველა y მე ნულის ტოლი იქნება. როგორც ადრე, ჩვენ გვჯერა, რომ ყველაფერი ბ მე ≥ 0. რომ საათზე მე ტოლი იყო 0, პრობლემა უნდა გადავაკეთოთ ისე, რომ ყველა ხელოვნური საფუძვლის ცვლადი y მე გადავიდა თავისუფალ ცვლადებში. ასეთი გადასვლა შეიძლება განხორციელდეს მარტივი მეთოდის ალგორითმით დამატებითი ობიექტური ფუნქციის მიმართ

ვ(y) = y 1 + y 2 + ... + y მ \u003d დ 0 – (დ 1 x 1 + დ 2 x 2 +…+დ ნ x ო) (2.7)

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

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

წრფივი პროგრამირების პრობლემა (LPP) არის წრფივი ფუნქციის უდიდესი (ან ყველაზე მცირე) მნიშვნელობის პოვნის პრობლემა ამოზნექილ პოლიედრალურ ნაკრებზე.

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

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

(1)

(2)

(3)

ხელოვნური საფუძვლის მეთოდი

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

მოდით, საჭირო იყოს ფუნქციის მაქსიმუმის პოვნა

პირობებში

სად არიან პირველი ნ ელემენტები ნულებია. ცვლადები ხელოვნურს უწოდებენ. ვექტორების სვეტები

(28)

ქმნიან ე.წ ხელოვნურ საფუძველს მ-განზომილებიანი ვექტორული სივრცე.

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

თეორემა 4. თუ ოპტიმალურ გეგმაში ხელოვნური ცვლადების გაფართოებული პრობლემის (24) - (26) მნიშვნელობები შემდეგ არის პრობლემის ოპტიმალური გეგმა (21) - (23).

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

ობიექტური ფუნქციის მნიშვნელობა საცნობარო გეგმით (27):

Გაითვალისწინე F (X) და შედგება ორი დამოუკიდებელი ნაწილისგან, რომელთაგან ერთი დამოკიდებულია მდა სხვა არა.

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

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

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

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

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

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

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

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

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

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

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

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

მათემატიკური მოდელი ამოცანას ეწოდება მათემატიკური ურთიერთობების ერთობლიობა, რომელიც აღწერს ამოცანის არსს.

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

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

ცვლადების ამოცანები მოუწოდა მნიშვნელობებს X1, X2, Xn, რომლებიც სრულად ახასიათებს ეკონომიკურ პროცესს. ჩვეულებრივ, ისინი იწერება როგორც ვექტორი: X \u003d (X1, X2, ..., Xn).

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

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

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

ეს აღნიშვნა ნიშნავს შემდეგს: იპოვნეთ ობიექტური ფუნქციის უკიდურესი ნაწილი (1) და შესაბამისი ცვლადები X \u003d (X1, X2, ..., Xn), იმ პირობით, რომ ეს ცვლადები აკმაყოფილებენ შეზღუდვების სისტემას (2) და არა-ნეგატიური პირობების პირობებს (3).

სწორი გამოსავალია ხაზოვანი პროგრამირების პრობლემის (გეგმა) არის ნებისმიერი n- განზომილებიანი ვექტორი X \u003d (X1, X2, ..., Xn), რომელიც აკმაყოფილებს შეზღუდვებისა და არა-ნეგატიური პირობების სისტემას.

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

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

მათემატიკური მოდელის შედგენის მაგალითი რესურსების (ნედლეულის) გამოყენების პრობლემა

მდგომარეობა: N ტიპის პროდუქციის წარმოებისათვის გამოიყენება m ტიპის რესურსები. შეადგინეთ მათემატიკური მოდელი.

ცნობილია:

• bi (i \u003d 1,2,3, ..., მ) - თითოეული მე – მეორის რესურსის მარაგი;
• aij (i \u003d 1,2,3, ..., m; j \u003d 1,2,3, ..., n) - თითოეული მე –4 ტიპის რესურსის ხარჯები j– ის ტიპის პროდუქტის მოცულობის ერთეულის წარმოებისათვის;
• cj (j \u003d 1,2,3, ..., n) - მოგება პროდუქტის j- ის ტიპის მოცულობის ერთეულის გაყიდვიდან.

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

გადაწყვეტილება:

ჩვენ შემოგთავაზებთ ცვლადების X \u003d (X1, X2, ..., Xn) ვექტორს, სადაც xj (j \u003d 1,2, ..., n) არის პროდუქტის j- ე ტიპის წარმოების მოცულობა.

მოცემული მოცულობის xj პროდუქციის წარმოების მე –7 ტიპის რესურსის ხარჯები უდრის aijxj– ს, შესაბამისად, ყველა სახის პროდუქციის წარმოებისთვის რესურსების გამოყენების შეზღუდვა
პროდუქტის მე -13 ტიპის გაყიდვიდან მოგება cjxj უდრის, ამიტომ ობიექტური ფუნქცია უდრის:

პასუხი - მათემატიკური მოდელია:

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

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

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

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

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

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

• А - განტოლებების სისტემის კოეფიციენტების მატრიცა
• X - ამოცანის ცვლადების მატრიცა-სვეტი
• Ao - შეზღუდვების სისტემის მარჯვენა მხარეების მატრიცა-სვეტი

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

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

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

ეს შეიძლება გაკეთდეს შემდეგნაირად:

აიღეთ წრფივი უტოლობა a1x1 + a2x2 + ... + anxn≤b და დაამატე გარკვეული მნიშვნელობა xn + 1 მის მარცხენა მხარეს, ისე, რომ უთანასწორობა გადაიქცეს a1x1 + a2x2 + ... + angn + xn + 1 \u003d b თანასწორობაში. უფრო მეტიც, ეს მნიშვნელობა xn + 1 არ არის უარყოფითი.

მოდით, მაგალითზე განვიხილოთ ყველაფერი.

მაგალითი 26.1

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

გადაწყვეტილება:
მოდით მივმართოთ ობიექტური ფუნქციის მაქსიმუმის პოვნის პრობლემას.
ამისათვის ვცვლით ობიექტური ფუნქციის კოეფიციენტების ნიშნებს.
შეზღუდვების სისტემის მეორე და მესამე უტოლობების განტოლებებად გადასაკეთებლად შემოგვყავს არაუარყოფითი დამატებითი ცვლადები x4 x5 (მათემატიკურ მოდელზე, ეს ოპერაცია აღინიშნება ასო D- ით).
ცვლადი x4 შემოდის მეორე უტოლობის მარცხენა მხარეს "+" ნიშნით, ვინაიდან უტოლობას აქვს ფორმა "≤".
X5 ცვლადი შემოტანილია მესამე უტოლობის მარცხენა მხარეს "-" ნიშნით, რადგან უტოლობა არის "≥".
X4 x5 ცვლადები შედის ობიექტურ ფუნქციაში კოეფიციენტით. ნულის ტოლია.
ჩვენ ვაწერთ დავალებას კანონიკური ფორმით: