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

10.01.2022

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

სლაიდი 2

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

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

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

სლაიდი 3

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

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

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

სლაიდი 5

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

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

სლაიდი 7

IN მოკლე შენიშვნა ZLP-ს აქვს ფორმა: შეზღუდვებით

სლაიდი 8

ZLP-ის მათემატიკური მოდელის შედგენისთვის საჭიროა: 1) ცვლადების დანიშვნა;

2) ობიექტური ფუნქციის შექმნა;

3) ჩამოწერეთ შეზღუდვების სისტემა პრობლემის მიზნის შესაბამისად;

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

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

სლაიდი 9

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

1.რესურსების ოპტიმალური განაწილების პრობლემა.

დავუშვათ, რომ საწარმო აწარმოებს სხვადასხვა პროდუქტს. მათი წარმოება მოითხოვს

სხვადასხვა სახის

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

სლაიდი 11

საჭიროა საწარმოო გეგმის შედგენა, რომელშიც საწარმოს მოგება იქნება ყველაზე დიდი.

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

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

სლაიდი 15

მსგავსი მსჯელობის გამოყენებით ჩვენ შეგვიძლია შევქმნათ შეზღუდვების სისტემა

სლაიდი 16

ახლა შევქმნათ ობიექტური ფუნქცია. A ტიპის პროდუქციის გაყიდვიდან მოგება იქნება 10, B ტიპის პროდუქციის გაყიდვიდან -14 და C-12 ტიპის პროდუქციის გაყიდვიდან მთლიანი მოგება იქნება

სლაიდი 17

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

სლაიდი 18

მაგალითი 2

ქალაქის რძის ქარხნის პროდუქტებია რძე, კეფირი და არაჟანი, დაფასოებული კონტეინერებში. 1 ტონა რძის, კეფირის და არაჟნის დასამზადებლად საჭიროა, შესაბამისად, 1010, 1010 და 9450 კგ რძე. ამასთან, 1 ტონა რძისა და კეფირის ჩამოსასხმელად საჭირო სამუშაო დრო შეადგენს 0,18 და 0,19 სამანქანო საათს. სპეციალური მანქანები 1 ტონა არაჟნის 3,25 საათის განმავლობაში შეფუთვით არიან დაკავებული.

სლაიდი 19

მთლიანობაში, ქარხანას შეუძლია გამოიყენოს 136000 კგ რძე მთლიანი რძის პროდუქტების წარმოებისთვის. ძირითადი აღჭურვილობა შეიძლება დაიკავოს 21,4 სამანქანო საათის განმავლობაში, ხოლო არაჟნის შესაფუთი მანქანები 16,25 საათის განმავლობაში. 1 ტონა რძის, კეფირის და არაჟნის გაყიდვიდან მიღებული მოგება შესაბამისად 30, 22 და 136 რუბლს შეადგენს. ქარხანამ ყოველდღიურად უნდა აწარმოოს მინიმუმ 100 ტონა ჩამოსხმული რძე. სხვა პროდუქტების წარმოებაზე შეზღუდვები არ არსებობს.

სლაიდი 20

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

სლაიდი 21

გამოსავალი

მცენარემ აწარმოოს ტონა რძე, ტონა კეფირი და ტონა არაჟანი.

მაშინ მას სჭირდება კგ რძე.

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

სლაიდი 22

დროის შეზღუდვები რძის და კეფირის შეფუთვაზე და არაჟნის შეფუთვაზე.

ვინაიდან ყოველდღიურად 100 ტონა რძე მაინც უნდა იწარმოებოდეს.

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

სლაიდი 23

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

სლაიდი 24

პრობლემა ნარევებთან დაკავშირებით.

გამოსავალი

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

სლაიდი 25

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

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

სლაიდი 28

შემოვიღოთ შემდეგი აღნიშვნა: - ნარევში შემავალი j-ე მასალის რაოდენობა; - მე-4 ტიპის მასალის ფასი; არის ნარევში i-ე კომპონენტის მინიმალური საჭირო შემცველობა.

კოეფიციენტები გვიჩვენებს i-ე კომპონენტის სპეციფიკურ სიმძიმეს j-ე მასალის ერთეულში

სლაიდი 29

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

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

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

ეს ვარიანტი

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

სლაიდი 31

გამოსავალი. დავუშვათ, რომ ასობით ქსოვილი იჭრება jth ვარიანტის გამოყენებით. ვინაიდან j-ე ვარიანტის მიხედვით ქსოვილის ჭრისას მიიღება i-th ტიპის ნაწილები, გამოყენებული ქსოვილებიდან ჭრის ყველა ვარიანტისთვის, ნარჩენების მთლიანი რაოდენობა იქნება ყველა ჭრის ვარიანტისთვის.

სლაიდი 35

LP-ის მთავარი ამოცანა

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

სლაიდი 36

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

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

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

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

დოკუმენტით არქივის ჩამოსატვირთად, ქვემოთ მოცემულ ველში შეიყვანეთ ხუთნიშნა ნომერი და დააჭირეთ ღილაკს "არქივის ჩამოტვირთვა"

მსგავსი დოკუმენტები

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

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

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

კურსის სამუშაო, დამატებულია 03/27/2011ზოგადი დავალებები

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

კურსის სამუშაო, დამატებულია 24/10/2012

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

რეზიუმე, დამატებულია 08/21/2008

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

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

კურსის სამუშაო, დამატებულია 02/11/2011

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

პრეზენტაციის გადახედვის გამოსაყენებლად, შექმენით ანგარიში თქვენთვის ( ანგარიში) Google და შედით: https://accounts.google.com

სლაიდის წარწერები:

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

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

დავალება. არსებობს 14 რადიო სარელეო საკომუნიკაციო არხი (RRC) და 9 ტროპოსფერული არხი. მათზე აუცილებელია 3 ტიპის ინფორმაციის გადაცემა: A, B, C. უფრო მეტიც, ინფორმაცია A უდრის 600 აშშ დოლარს, B – 3000 აშშ დოლარი, C – 5500 აშშ დოლარი. (ინფორმაცია შეიძლება გავიგოთ, როგორც რიცხვი სატელეფონო საუბრები, მონაცემთა გადაცემა და ა.შ.). არხების შესაძლებლობები და თითოეული არხის მომსახურების ხარჯები მოცემულია ცხრილში. აუცილებელია მოიძიოთ ორივე ტიპის ჩართული არხების რაოდენობა, რომლებიც აუცილებელია საჭირო ინფორმაციის გადასაცემად, რათა ოპერაციის ღირებულება მინიმალური იყოს.

ინფორმაციის ტიპები საკომუნიკაციო არხები ინფორმაციის საჭირო რაოდენობა, ერთეული ტროპოსფერული RRS A 80 40 600 B - 1000 3000 C 300 800 5500 ერთი არხის მომსახურების ხარჯები, რუბ. 3000 2000

ZLP-ის ამოხსნის ეტაპები: SDR-ის აგება. ააგეთ ობიექტური ფუნქციის გრადიენტის ვექტორი X 0 რაღაც წერტილში, რომელიც ეკუთვნის ODR – (c 1 ;c 2) . ააგეთ სწორი ხაზი c 1 x 1 + c 2 x 2 = h, სადაც h არის ნებისმიერი დადებითი რიცხვი, სასურველია, რომ დახატული სწორი ხაზი გაიაროს ამოხსნის მრავალკუთხედში.

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

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

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

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

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

ხაზოვანი პროგრამირება▪ ხაზოვანი პროგრამირების პრობლემა – სლაიდი 3.
▪ PLP ამოხსნის გეომეტრიული მეთოდი – სლაიდი 26.
▪ ხაზოვანი პროგრამირების პრობლემა სტანდარტული ფორმით – სლაიდი 32.
▪ ZLP ამოხსნის მარტივი მეთოდი – სლაიდი 42.
▪ გაუსის მეთოდი – 48 სლაიდი.
▪ Simplex მეთოდი – 58 სლაიდი.
▪ ხელოვნური ბაზის მეთოდი – 76 სლაიდი.
▪ წრფივი პროგრამირების ამოცანების ორმაგობა – სლაიდი 87.