დინამიური პროგრამირების მეთოდის ძირითადი წინაპირობები. დინამიური პროგრამირება, ძირითადი პრინციპები. II ეტაპი. უპირობო ოპტიმიზაცია

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

დავუშვათ, რომ დაშეიძლება შეირჩეს ისე, რომ iA ≥ წმ. შემდეგ ნებისმიერისთვის X≥ 0 უტოლობა მართალია

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

ფ თუ დაყენებულია კანონიკური პრობლემა LP

შემდეგ LP პრობლემა

დაურეკა ორმაგიმასთან მიმართებაში. შესაბამისად დავალება (დ,ფ) არანაირი კავშირი არ აქვს

(დ*, ვ*) დაურეკა პირდაპირი (ან ორიგინალი).

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

ფ თუ ზოგადი LP პრობლემაა მოცემული

ვ(x) = გ 1 x 1 + ... + c j x j + c j +1 x j+ 1 + ... + n x n-ით →მაქს, xÎ D, (1.50)

სადაც D განისაზღვრება განტოლებათა და უტოლობათა სისტემით:

რომორმაგიამასთან დაკავშირებით ზოგადი LP პრობლემა ეწოდება

სადაც D* განისაზღვრება განტოლებათა და უტოლობათა სისტემით:

OPLP-ის მიმართ ორმაგი პრობლემის აგების წესები ნათლად არის წარმოდგენილი დიაგრამით, რომელიც ნაჩვენებია ბრინჯი. 1.9.

როგორც ზემოთ მოყვანილი დიაგრამადან ჩანს, პირდაპირი LP პრობლემისგან ორმაგზე გადასვლისას:

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

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

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

4. ცვლადების ინდექსების ერთობლიობა, რომელზედაც დაწესებულია არანეგატიურობის პირობა პირდაპირ პრობლემაში (მაგ. x j≥ 0 ან u j≥ 0), განსაზღვრეთ შეზღუდვების რაოდენობა, რომლებსაც აქვთ უტოლობების ფორმა ორმაგ ამოცანაში ( ა ჯ უ ≥ ჯ-თან ერთადან a i x ≤ ბ ჯ).

5. შეზღუდვების რიცხვების ერთობლიობა, რომლებსაც აქვთ უტოლობის ფორმა პირდაპირ პრობლემაში (მაგ. a i x ≤ ბ ჯან ა ჯ უ ≥ ჯ)დაადგინეთ ცვლადების ინდექსების სიმრავლე, რომლებზედაც დაწესებულია არანეგატიურობის პირობა ორმაგ ამოცანაში ( u i≥ 0 ან x i ≥ 0).

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

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

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

განვიხილოთ ორმაგი პრობლემის აგების პროცესი კონკრეტული მაგალითის გამოყენებით. მიეცით OLP ( დ, ვ):

მაშინ მისი ორმაგი პრობლემა იქნება ( D*, ვ*):

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

მტკიცებულება.

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

რა ვექტორი დაარის სწორი დავალების გეგმა ( დ*, ვ*), აქედან გამომდინარეობს iA ≥თან. ამ უტოლობის მარცხენა და მარჯვენა მხარის ვექტორზე გამრავლება X≥ 0, ვიღებთ უტოლობათა ეკვივალენტურ სისტემას

ამავდროულად, x ვექტორისთვის, რომელიც არის პრობლემის დასაშვები გეგმა ( დ,ფ), თანასწორობა მართალია Ax=b. ეს ამტკიცებს ამას иb ≥ сх.ა

კომენტარი.თეორემა 1.4, რა თქმა უნდა, ასევე შეესაბამება ორმხრივი პრობლემების ოპტიმალურ გეგმებს: f(x*) ≤ f*(u*),სად X*და u*-ნებისმიერი ოპტიმალური დავალების გეგმა ( დ,ფ) და ( დ*, ვ*). სინამდვილეში, როგორც ქვემოთ ჩანს, თანასწორობა f(x*) = f*(u*).

მტკიცებულება.

თეორემა 1.4-ის მიხედვით, ყველა დასაშვები გეგმისთვის Xამოცანები ( დ,ფ) უტოლობა მართალია cx < ბ. თეორემის პირობების მიხედვით f()=f()ან, რა არის იგივე, c = b. მაშასადამე, შემდეგი დებულება მართალია: ნებისმიერი x О D c > cx, ე.ი. Xარის პრობლემის ოპტიმალური გეგმა ( დ,ფ).

დასაბუთება გეგმის ოპტიმალურობის დასადასტურებლად ამოცანისთვის ( D*,ვ*), ტარდება ანალოგიურად. ა

მტკიცებულება.

თუ დავუშვებთ, რომ ორმაგი პრობლემა ( დ*,ვ*) არის მინიმუმ ერთი მოქმედი გეგმა და, მაშინ, თეორემა 1.4-ის მიხედვით, ნებისმიერი დასაშვები გეგმისთვის Xამოცანები ( დ,ფ) უტოლობა მართალია f(x) ≤ ვ*( ) <+∞. Последнее означает, что целевая функция ვამოცანები ( დ,ფ) შემოიფარგლება ზემოდან. ვინაიდან ეს ეწინააღმდეგება თეორემის პირობებს, ორმაგი პრობლემის დასაშვები გეგმების არსებობის დაშვება ( დ*, ვ*) არასწორია. ა

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

მტკიცებულება.

ვექტორები X*და და *,როგორც შესაბამისი ამოცანების დასაშვები გეგმები, აკმაყოფილებს პირობებს: ცული* = ბ, x* > 0 და u*A-c ≥ 0. მოდი ვიპოვოთ სკალარული პროდუქტი

თეორემა 1.2-ის შენიშვნის მიხედვით, ორმხრივი ამოცანების ობიექტური ფუნქციების ოპტიმალური მნიშვნელობები ემთხვევა, ე.ი. . u*b=сх*.ეს უკანასკნელი იმას ნიშნავს (u*A-c)x*= 0. თუმცა, ორი არაუარყოფითი ვექტორის სკალარული ნამრავლი შეიძლება იყოს მხოლოდ ნული, თუ მათი შესაბამისი კოორდინატების ყველა წყვილი ნამრავლი ნულია. ამიტომ, თუ x j *> 0, მაშინ უ*ა ჯ – ჯ-თან ერთად= 0, თუ x j= 0, მაშინ ეს შესაძლებელია უ*ა ჯ – ჯ-ით≥ 0, რაც არის ნათქვამი თეორემაში. ა

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

ისევ მაგიდას დავუბრუნდეთ თ 2 (ქ) (ბრინჯი. 1.8), მიღებული პროცედურის საბოლოო გამეორებისას შეცვლილი სიმპლექსის მეთოდი. მოდით უფრო ახლოს მივხედოთ Δ -1 მატრიცის ნულოვან მწკრივს (β ( ქ)), რისთვისაც აღნიშვნა δ 0 (β ( ქ)). ის შეიძლება დაიწეროს ელემენტად ელემენტად შემდეგი ფორმა:

შემოვიღოთ ვექტორი = (δ 0.1 (β ( ქ)), δ 0.2 (β ( ქ)),..., δ 0, მ (β ( ქ))). რეიტინგის ხაზის შემოწმება მარტივია ა 0 (β ( ქ)) შეიძლება წარმოდგენილი იყოს შემდეგნაირად:

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

ამავე დროს ელემენტი ბ 0 (β ( ქ)), რომელიც შეიცავს ობიექტური ფუნქციის მიმდინარე მნიშვნელობას და ტოლია ბოლო გამეორებისას f (x*),წარმომადგენლობას აღიარებს

თეორემის მიხედვით 1.5 ტოლობიდან ვ(X*) = ვ*(ũ ) აქედან გამომდინარეობს, რომ ვექტორი ũ ემსახურება ორმაგი პრობლემის ოპტიმალურ გეგმას: u = ũ.

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

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

მკითხველს როგორც დამოუკიდებელი ვარჯიშიშემოთავაზებულია ამოცანის აგება ორმაგი (1.34)-(1.35), რომლის ამოხსნა მოცემულია 1.5.2 განყოფილებაში და დარწმუნდით, რომ ვექტორი u= (-10, 32, 2) მიღებული ცხრილში თ 2 (3) არის მისთვის მისაღები და ოპტიმალური გეგმა.

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

დავუშვათ, რომ ზოგიერთი ღირებულებისთვის ა, ბდა თანნაპოვნია ოპტიმალური გეგმა X*მთლიანი შემოსავლის მაქსიმუმს ( cx}=cx*. საკმაოდ ბუნებრივია კითხვა: როგორ შეიცვლება ოპტიმალური გეგმა? X* შეზღუდვის ვექტორის კომპონენტების შეცვლისას ბდა, კერძოდ, რა ვარიაციით ბოპტიმალური გეგმა X* უცვლელი დარჩება? ეს ამოცანამიიღო სახელი მდგრადობის საკითხები ოპტიმალური გეგმა. აშკარაა, რომ მდგრადობის კვლევა X* აქვს ასევე პირდაპირი პრაქტიკული მნიშვნელობა, ვინაიდან რეალურ წარმოებაში არსებული რესურსების მოცულობები ბ ი; შეიძლება მნიშვნელოვნად მერყეობდეს დაგეგმვის გადაწყვეტილების მიღების შემდეგ X*.

როდესაც შეზღუდვის ვექტორი ბიცვლება Δ ბან, როგორც ამბობენ, იღებს Δ-ს ბ, მაშინ შესაბამისი ვარიაციები წარმოიქმნება ოპტიმალური გეგმისთვის x*(b+Δ ბ)და ობიექტური ფუნქციის მნიშვნელობები f( X*(ბ+Δ ბ)). ვთქვათ ნამატი Δ ბარის ისეთი, რომ არ იწვევს პრობლემის ოპტიმალური საფუძვლის ცვლილებას, ე.ი. x*(b+Δ ბ)≥0. მოდით განვსაზღვროთ ფუნქცია ფ(ბ), დაბრუნება ოპტიმალური ღირებულებაპრობლემის ობიექტური ფუნქცია ( დ(ბ), ვ) ამისთვის სხვადასხვა მნიშვნელობაშეზღუდვის ვექტორები ბ

განვიხილოთ მისი ზრდის თანაფარდობა F(b+Δ ბ)-F(ბ)არგუმენტის ზრდა Δ ბ. თუ ზოგიერთისთვის მეპირდაპირი Δ ბ ი→ 0, მაშინ მივიღებთ

იმის გათვალისწინებით, რომ თეორემა 1.5-ის შესაბამისად

და (1.57) (1.56) ჩანაცვლებით, მივდივართ გამოსახულებამდე

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

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

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

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

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

ფ ფ თუ ორმაგი ამოცანის j-e ოპტიმალური გეგმის გამოყენებისას შეზღუდვა დაკმაყოფილებულია როგორც მკაცრი უტოლობა, მაშინ პირდაპირი ამოცანის შესაბამისი ცვლადის ოპტიმალური მნიშვნელობა უნდა იყოს ნულის ტოლი, ე.ი. 1, j u 1 * +...და m, j და m – ერთად j > 0, შემდეგ x j * = 0.

ორმაგი შეფასებების ეკონომიკური შინაარსის გათვალისწინებით u 1 *,...,u m, გამოხატულება ა 1, j u 1 * +…a m, j u m *შეიძლება განიმარტოს, როგორც ერთეულის ხარჯები ჯე პროცესი. ამიტომ, თუ ეს ხარჯები აღემატება ერთეულის გაყიდვით მიღებულ მოგებას ჯ-ე პროდუქტი, შემდეგ წარმოება ჯპროდუქტი წამგებიანია და არ უნდა იყოს შეტანილი წარმოების ოპტიმალურ გეგმაში ( x j * =0).

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

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

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

ასევე, PLP-ის ოპტიმალური გეგმის სტაბილურობის პრობლემის შინაარსი ობიექტური ფუნქციის ვარიაციებთან მიმართებაში შეიძლება ილუსტრირებული იყოს პირველი გეომეტრიული ინტერპრეტაციის გამოყენებით. ჩართულია ბრინჯი. 1.10გვიჩვენებს განხორციელებადი გეგმების ერთობლიობას დ LP-ის გარკვეული პრობლემა. როგორც ნახატიდან ჩანს, ობიექტური ფუნქცია ვ(მისი ქცევა აისახება სქელი წერტილოვანი ხაზით ნაჩვენები დონის ხაზით) აღწევს უკიდურეს მნიშვნელობას წერტილში X* და მისი კოეფიციენტების ცვლილება თანრომ თან"ან თან"ფიგურაში შეესაბამება დონის ხაზის ბრუნვას შედარებით X*. აქტიური, ანუ თანასწორობად გადაქცევა, შეზღუდვები წერტილში X* შეესაბამება ხაზებს (1) და (2). სანამ, ვექტორის ცვლილებით გამოწვეული შემობრუნებისას თან, ობიექტური ფუნქციის დონის ხაზი არ სცილდება შეზღუდვის ხაზებით წარმოქმნილ კონუსს, X*რჩება ოპტიმალურ გეგმად. როგორც ნაჩვენებია ბრინჯი. 1.10, ეს გეგმა არ იცვლება დან გადასვლისას თანრომ თან"და, პირიქით, დან გადასვლისას თანრომ თან"ობიექტური ფუნქციის დონის ხაზი f(x)=c"xგადაკვეთს ხაზს (2), რაც გამოიწვევს ოპტიმალური საბაზისო ხაზის ცვლილებას, რომელიც ახლა იქნება წერტილი .

ZLP გეგმის ოპტიმალური პირობების გამოყენება

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

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

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

2. სვეტი რშედის ოპტიმალურ საფუძველში ( რÎ ნ(β ( ქ))). ამ შემთხვევაში ოპტიმალურობის შესანარჩუნებლად მიმდინარე გეგმადასჭირდება შესრულება ყველა არასაბაზისო სვეტისთვის ( ჯ Ï ნ(β ( ქ))) პირობები

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

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

ორმაგობის თეორიის ძირითადი განმარტებები.

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

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

F=3 X 1 + 5X 2 + 4X 3 + 5X 4 → მაქს.

ორმაგი ამოცანის შედგენის ზოგადი წესები:

პირდაპირ	ორმაგი
ობიექტური ფუნქცია (წთ)	შეზღუდვების მარჯვენა მხარე
შეზღუდვების მარჯვენა მხარე	ობიექტური ფუნქცია (მაქს.)
A - შეზღუდვის მატრიცა	A T - შეზღუდვის მატრიცა
მე-ე შეზღუდვა: ≥ 0, (≤ 0)	ცვლადი y i ≥ 0, (≤ 0)
მე-ე შეზღუდვა: = 0	ცვლადი y i ≠ 0
ცვლადი x j ≥ 0	j-ე შეზღუდვა: ≤ 0
ცვლადი x j ≠ 0	j-ე შეზღუდვა: = 0

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

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

გაითვალისწინეთ, რომ I დავალების მატრიცის რიგები არის II დავალების მატრიცის სვეტები. მაშასადამე, II ამოცანაში y i ცვლადების კოეფიციენტები, შესაბამისად, I ამოცანაში i-ის უტოლობის კოეფიციენტებია.
შედეგად მიღებული მოდელი არის პრობლემის ეკონომიკურ-მათემატიკური მოდელი, რომელიც ორმაგია უშუალო პრობლემის მიმართ.

ისრებით დაკავშირებული უტოლობები იქნება ზარის კონიუგატი.
ორმაგი პრობლემის მნიშვნელოვანი ფორმულირებაიპოვნეთ რესურსების ფასების ისეთი ნაკრები (შეფასება) Y = (y 1, y 2 ..., y m), რომლის დროსაც რესურსების ჯამური ხარჯები იქნება მინიმალური, იმ პირობით, რომ რესურსების ხარჯები თითოეული ტიპის წარმოებაში პროდუქტი არ იქნება ნაკლები მოგებაზე (შემოსავალზე) ამ პროდუქტების გაყიდვიდან.
რესურსების ფასებმა y 1, y 2 ..., y m მიიღო სხვადასხვა სახელები ეკონომიკურ ლიტერატურაში: ბუღალტრული, იმპლიციტური, ჩრდილოვანი. ამ სახელების მნიშვნელობა არის ის, რომ ეს არის პირობითი, "ყალბი" ფასები. განსხვავებით "გარე" ფასებისგან c 1, c 2 ..., c n პროდუქტებისთვის, რომლებიც ცნობილია, როგორც წესი, წარმოების დაწყებამდე, რესურსების ფასები c 1, c 2 ..., c n არის შიდა, რადგან ისინი არ არის მითითებული გარედან, მაგრამ განისაზღვრება უშუალოდ პრობლემის გადაჭრის შედეგად, ამიტომ მათ უფრო ხშირად უწოდებენ რესურსების შეფასებას.
უშუალო და ორმაგ პრობლემებს შორის კავშირი მდგომარეობს, კერძოდ, იმაში, რომ ერთ-ერთი მათგანის გადაწყვეტა შეიძლება მიღებულ იქნას უშუალოდ მეორის გადაწყვეტიდან.

ორმაგობის თეორემები

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

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

თუ I და II ორმაგი ამოცანების წყვილიდან ერთი ამოსახსნელია, მაშინ მეორე ამოსახსნელია და ოპტიმალურ გეგმებზე ობიექტური ფუნქციების მნიშვნელობები ემთხვევა, ფ(x*) = გ(წ*), სადაც x *, y * არის I და II ამოცანების ოპტიმალური გადაწყვეტილებები

მეორე ორმაგობის თეორემა.

გეგმები x * და y * ოპტიმალურია I და II ამოცანებში, თუ და მხოლოდ იმ შემთხვევაში, თუ მათი I და II ამოცანების შეზღუდვების სისტემაში ჩანაცვლებისას, შესაბამისად, რომელიმე კონიუგატური უტოლობებიდან ერთი მაინც გადაიქცევა თანასწორობაში.
ეს ფუნდამენტური ორმაგობის თეორემა. სხვა სიტყვებით რომ ვთქვათ, თუ x * და y * არის შესაძლებელი ამონახსნები პირდაპირი და ორმაგი ამოცანების და თუ c T x * = b T y *, მაშინ x * და y * არის ოპტიმალური ამონახსნები ორმაგი ამოცანების წყვილისთვის.

მესამე ორმაგობის თეორემა. y i ცვლადების მნიშვნელობები ორმაგი ამოცანის ოპტიმალურ გადაწყვეტაში არის შეზღუდვების სისტემის თავისუფალი ტერმინების b i გავლენის შეფასება - პირდაპირი ამოცანის უტოლობები ამ პრობლემის ობიექტური ფუნქციის მნიშვნელობაზე:
Δf(x) = b i y i

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

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

1. ერთ პრობლემაში ისინი მაქსიმუმს ეძებენ ხაზოვანი ფუნქცია, მეორეში - მინიმუმი.
2. ერთი ამოცანის წრფივ ფუნქციაში ცვლადების კოეფიციენტები მეორეში შეზღუდვების სისტემის თავისუფალი წევრებია.
3. თითოეული დავალება მითითებულია სტანდარტული ფორმადა მაქსიმიზაციის ამოცანაში ≤ ფორმის ყველა უტოლობა, ხოლო მინიმიზაციის ამოცანაში ≥ ფორმის ყველა უტოლობა.
4. ორივე ამოცანის შეზღუდვის სისტემაში ცვლადების კოეფიციენტების მატრიცები გადატანილია ერთმანეთზე:
5. ერთი პრობლემის შეზღუდვების სისტემაში უტოლობების რაოდენობა ემთხვევა მეორე პრობლემის ცვლადების რაოდენობას.
6. ცვლადების არანეგატიურობის პირობები ორივე პრობლემაშია.

ასე რომ, ჩვენ გვაქვს თავდაპირველი პრობლემა მე და მისი ოპტიმალური გადაწყვეტა x * = (0, 40, 0, 100) და ფ(X*) = 700.

ორმაგობის თეორემის გამოყენებით, ჩვენ ვიღებთ გამოსავალს ორმაგი ამოცანის თვალსაზრისით ცნობილი გამოსავალიორიგინალური დავალება.
ვიპოვოთ გამოსავალი ორმაგი ამოცანის II y* = ( ზე 1 , ზე 2 , ზე 3), მარტივი მეთოდის გამოყენების გარეშე, მაგრამ გამოყენებით მეორე ორმაგობის თეორემადა ცნობილი ოპტიმალური გეგმა x *.

განვიხილოთ I ამოცანის უტოლობების შესრულება ჩანაცვლების ქვეშ X* შეზღუდვების სისტემაში.

5x 1 +0.4x 2 +2x 3 +0.5x 4 ≤400	5*0+0,4*40+2*0+0,5*100=66<400	შეზღუდვა დაკმაყოფილებულია როგორც მკაცრი უთანასწორობა, ე.ი. პირველი ტიპის რესურსი ბოლომდე არ არის გამოყენებული. ეს ნიშნავს, რომ ეს რესურსი არ არის მწირი და მისი შეფასება ოპტიმალურ გეგმაში არის y 1 = 0.
5x 2 +x 3 +x 4 ≤300	5*40 + 0 + 100 = 300 = 300	პირდაპირი პრობლემის შეზღუდვა დაკმაყოფილებულია როგორც თანასწორობა. ეს ნიშნავს, რომ მე-2 რესურსი სრულად არის გამოყენებული ოპტიმალურ გეგმაში, მწირია და მისი შეფასება მეორე ორმაგობის თეორემის მიხედვით განსხვავდება ნულისაგან (y 2 ≠ 0)
x 1 + x 3 + x 4 ≤ 100	0 + 0 + 100 = 100 = 100	y 3 ≠ 0
x 1 ≥ 0	x 1 = 0	ორმაგ პრობლემაში პირველი შეზღუდვა იქნება უთანასწორობა 5y 1 + y 3 ≥ 3
x 2 ≥ 0	x 2 = 40 > 0	მეორე შეზღუდვა ორმაგ პრობლემაში იქნება თანასწორობა 0.4 წ 1 + 5 წ 2 = 5
x 3 ≥ 0	x 3 = 0	მესამე შეზღუდვა ორმაგ პრობლემაში იქნება უთანასწორობა 2y 1 + y 2 + y 3 ≥ 4
x 4 ≥ 0	x 4 = 100 > 0	ორმაგ პრობლემაში მეოთხე შეზღუდვა იქნება თანასწორობა 0.5y 1 + y 2 + y 3 = 5

ვინაიდან 1, 5, 7 უტოლობები მკაცრია (მათ აქვთ ნიშანი "<" или ">"), მაშინ II ამოცანის შესაბამისი უტოლობა წყვილთა წყვილიდან უნდა იქცეს ტოლებად. გვაქვს:

ან

იმათ. ზე* = (0, 1, 4) - ოპტიმალური გადაწყვეტა.

გაითვალისწინეთ, რომ ნამდვილად გ(წ*) = 400წ 1 + 300წ 2 + 100წ 3 = 400 0 + 300 1 + 100 4 = 700 = ფ(x*).

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

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

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

დავწეროთ ცხრილი x i და y j ცვლადებს შორის შესაბამისობის გათვალისწინებით.

		ზე 4	ზე 2	ზე 6	ზე 3
	ძირითადი	-X 1	-X 6	-X 3	-X 7	უფასო
ზე 1	X 5					334
ზე 5	X 2					40
ზე 7	X 4					100
	-ფ	1	1	1	4	700

შესაბამისობისა და II ორმაგობის თეორემის ძალით ცვლადები ზე 1 , ზე 5 , ზე 7 უნდა უდრის 0-ს, რადგან X 5 , X 2 , X 4 >0 მკაცრად. და ცვლადები 4-ზე, 2-ზე, 6-ზე, 3-ზე იღებენ მნიშვნელობებს ინდექსის ხაზიდან 1, 1, 1, 4, შესაბამისად, რადგან მათი შესაბამისი ცვლადები X 1 , X 6 , X 3 , X 7 = 0, როგორც უფასო. ასე რომ, II ამოცანის ბოლო ცხრილიდან, ყოველგვარი გამოთვლების გარეშეც კი და მხოლოდ ცვლადების შესაბამისობის გამოყენებით:

ზე* = (ზე 1 *, ზე 2 *,ზე 3 *, ზე 4 *, ზე 5 *, ზე 6 *, ზე 7 *) = (0, 1, 4, 1, 0, 1, 0).

ჩვენ ვისწავლეთ თავდაპირველი პრობლემის გადაჭრა ორმაგი პრობლემის გადაჭრის შესახებ. ეს შესაძლებელი გახდა ცვლადებს შორის ღრმა კავშირის გამო Xმედა y j. რჩება ამის გარკვევა

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

კარგი სამუშაოსაიტზე">

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

გამოქვეყნებულია http://www.allbest.ru/

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

დაგეგმეთ

1. ორმაგი პრობლემის დებულება და მოდელი

2. გადაწყვეტის მეთოდები

3. ორმაგობის თეორიის თეორემები და მისი ეკონომიკური შინაარსი

1. ორმაგი პრობლემის განცხადება და მოდელი

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

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

მე) და = თან 1 X 1 + თან 2 X 2 + … + თან ნX ნ მაქს.

II) ა 11 X 1 + ა 12 X 2 + … + ა 1 ნX ნ ? ბ 1 ,

ა 21 X 1 + ა 22 X 2 + … + ა 2 ნX ნ ? ბ 2 ,

………………………………

ა მ 1 X 1 + ა მ 2 X 2 + … + ა წთX ნ ? ბ მ.

III) X ჯ ? 0, ჯ = 1, 2, …, ნ.

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

შემდეგ, ე.წ ორმაგი მოდელიობიექტური ფუნქცია აღწერს მყიდველი მხარის ინტერესს, შეზღუდვების სისტემა აღწერს გამყიდველი მხარის ინტერესებს. (აუცილებელია შეფასდეს რესურსები, რომლებიც მოხმარდება წარმოების ერთეულის წარმოებას და შეზღუდოს ამ რესურსების ღირებულება გაყიდული წარმოების ერთეულის ფასზე). მესამე პირობა (არაუარყოფითი ცვლადები) შესრულდება იმის გამო, რომ რესურსის ერთეულის ფასი არ შეიძლება იყოს უარყოფითი. რესურსის ერთეულის ფასის სახით ღირებულების შეყვანით u მე 0 (მე = 1, 2, …, მ), მას ასევე უწოდებენ რესურსების შეფასება(ან ორმაგი შეფასება), ვიღებთ შემდეგ მოდელს:

მე) ფ = ბ 1 u 1 + ბ 2 u 2 + … + ბ მu მწთ.

II) ა 11 u 1 + ა 21 u 2 + … + ა მ 1 u მ გ 1 ,

ა 12 u 1 + ა 22 u 2 + … + ა მ 2 u მ გ 2 ,

………………………………

ა 1 ნu 1 + ა 2 ნu 2 + … + ა წთu მ გ ნ.

III) u მე 0, მე = 1, 2, …, მ.

მოდით შევადაროთ ორივე ამოცანა:

პირველი არის ამოცანა მაქსიმალურად ( ზმაქსიმალური), მეორე - მინიმუმამდე ( ფწთ);

პირველში არის ტიპის შეზღუდვების სისტემა, მეორეში;

პირველ პრობლემაში ნუცნობი და მშეზღუდვები, მეორეში მუცნობი და ნშეზღუდვები;

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

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

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

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

1) იცვლება ობიექტური ფუნქციის ექსტრემუმის ტიპი;

2) თავდაპირველი ამოცანის თითოეული შეზღუდვა ასოცირდება ორმაგი პრობლემის ცვლადთან;

3) საწყისი ამოცანის თავისუფალი ტერმინები ხდება ორმაგი ამოცანის ობიექტური ფუნქციის ცვლადების კოეფიციენტები;

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

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

ორიგინალური დავალება:

მე) ზ = 6x 1 + 4x 2 მაქს.

II) 2x 1 +4 x 2 ? 8,

2x 1 + x 2 ? 6.

III) x 1 ? 0, x 2 ? 0.

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

მე) ფ = 8u 1 + 6u 2 წთ.

II) 2 u 1 + 2u 2 ? 6,

4u 1 + u 2 ? 4.

III) u 1 ? 0, u 2 ? 0.

უნდა აღინიშნოს, რომ:

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

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

2. გადაწყვეტის მეთოდები

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

სიმპლექსის ცხრილში ჩასაწერად მომზადებული მოდელები ასე გამოიყურება:

ორიგინალური პრობლემა (წარმოგიდგენთ წ მე 0):

მე) და = თან 1 X 1 + თან 2 X 2 + … + თან ნX ნ მაქს.

II) წ 1 = -ა 11 X 1 - ა 12 X 2 - … - ა 1 ნX ნ + ბ 1 ,

წ 2 = -ა 21 X 1 - ა 22 X 2 - … - ა 2 ნX ნ + ბ 2 ,

…………………………………..

წ მ = -ა მ 1 X 1 - ა მ 2 X 2 - … - ა წთX ნ + ბ მ.

III) X ჯ ? 0, ჯ = 1, 2, …, ნ.

ორმაგი პრობლემა (წარმოგიდგენთ ვ ჯ 0):

მე) ფ = ბ 1 u 1 + ბ 2 u 2 + … + ბ მu მწთ.

II) ვ 1 = ა 11 u 1 + ა 21 u 2 + … + ა მ 1 u მ - გ 1 ,

ვ 2 = ა 12 u 1 + ა 22 u 2 + … + ა მ 2 u მ - გ 2 ,

……………………………………

ვ ნ = ა 1 ნu 1 + ა 2 ნu 2 + … + ა წთu მ - გ ნ.

III) u მე 0, მე = 1, 2, …, მ.

ორივე მოდელი იწერება ორმაგი სიმპლექსის ცხრილში შემდეგნაირად (ცხრილი 4):

ცხრილი 4 - ორმაგი სიმპლექსის მაგიდა

					ვ ნ
					-x ნ	უფასო წევრები
					ა 1 ნ
					ა 2 ნ
u მ	წ მ	ა მ 1	ა მ 2		ა წთ	ბ მ
უფასო წევრები					-გ ნ

შენიშვნები:

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

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

მე) ზ = 4x 1 + 2x 2 + 3x 3 წთ.

II) -4 x 1 - 3x 2 +x 3 ? -4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0,

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

მე) ზ = 4x 1 + 2x 2 + 3x 3 წთ.

II) 4 x 1 + 3x 2 - x 3 ? 4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0.

მაშინ ორმაგი პრობლემა ასე გამოიყურება:

მე) ფ = 4u 1 +6u 2 მაქს.

II) 4 u 1 + 5u 2 ? 4,

3u 1 + u 2 ? 2,

-u 1 + 2u 2 ? 3.

III) u 1 ? 0; u 2 ? 0;

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

3. ორმაგობის თეორიის ძირითადი თეორემები და მისი ეკონომიკური შინაარსი

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

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

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

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

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

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

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

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

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

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

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

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

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

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

გამოქვეყნებულია Allbest.ru-ზე

...

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

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

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


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

ლექციების კურსი, დამატებულია 14/07/2011


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

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


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

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


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

დავალება, დამატებულია 29/12/2013


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

ტესტი, დამატებულია 09/08/2010


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

კურსის სამუშაო, დამატებულია 12/09/2008


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

ტესტი, დამატებულია 04/11/2012


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

ტესტი, დამატებულია 01/15/2009


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

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

პირდაპირი პრობლემა ორიგინალური ფორმით:

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

.

პრობლემის ორმაგობის პირობების ჩამოსაყალიბებლად ვადგენთ შემდეგ დიაგრამას (ნახ. 7.1).

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

1) პირდაპირი ამოცანის თითოეული შეზღუდვა შეესაბამება ორმაგი ამოცანის ცვლადს;

2) პირდაპირი ამოცანის თითოეული ცვლადი შეესაბამება ორმაგი ამოცანის შეზღუდვას;

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

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

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

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

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

მაგალითი 7.1

პირდაპირი დავალება:

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

ორმაგი პრობლემა:

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

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

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

2) პირდაპირი პრობლემის გადაჭრის პროცესის ნებისმიერ განმეორებაზე:

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

, (7.1)

სადაც ვარსკვლავი (*) ნიშნავს, რომ ცვლადების მნიშვნელობები აღებულია პირდაპირი და ორმაგი ამოცანების ოპტიმალური გადაწყვეტილებებიდან;

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

თუ, მაშინ, (7.2)

თუ, მაშინ, (7.3)

თუ, მაშინ, (7.4)

თუ , მაშინ . (7.5)

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

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

2. თუ რესურსი სრულად არის გამოყენებული ოპტიმალურ გეგმაში, მაშინ მისი შეფასება დადებითია (იხ. ფორმულა (7.2)), მაგრამ თუ რესურსი სრულად არ არის გამოყენებული ოპტიმალურ გეგმაში, მაშინ მისი შეფასება ნულის ტოლია (იხ.

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

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

განვიხილოთ განხილული დებულებები შემდეგი მაგალითით.

მაგალითი 7.2

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

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

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

; ; .

გამოსავალი.პრობლემის მოდელი მიიღებს ფორმას:

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

,

რომლის დროსაც ფუნქცია მაქსიმუმს აღწევს.

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

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

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

ამავე დროს . არის დაუხარჯავი მეორე რესურსის დარჩენილი ნაწილი.

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

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

3. მე-2, მე-3 და მე-4 პროდუქცია (ამ სახეობის პროდუქცია იწარმოება) მომგებიანია, ხოლო 1 წამგებიანი. ორმაგი ჩანაცვლება პირველ შეზღუდვაში

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

რაც არის 0.6 მეტი ფასიამ პროდუქტის ერთეული უდრის 4-ს (გაითვალისწინეთ, რომ რიცხვი 0.6 არის სვეტის სავარაუდო ხაზში " x 1" ცხრილში 7.1).

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

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

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

განვიხილოთ რესურსების გამოყენების პრობლემა.

საწარმოს აქვს t ტიპის რესურსები b i (i = 1, 2, ..., მ) ერთეულის ოდენობით, საიდანაც იწარმოება n ტიპის პროდუქტი. წარმოებისთვის 1 ერთეული. მე-ე პროდუქტი მოიხმარს ij ერთეულს. t-ე რესურსი, მისი ღირებულებაა C j ერთეული. აუცილებელია განისაზღვროს წარმოების გეგმა, რომელიც უზრუნველყოფს მის მაქსიმალურ გამომუშავებას ღირებულების თვალსაზრისით. ავიღოთ x j (j =1,2, ..., n) ერთეულების რაოდენობად. j-ე პროდუქტები.

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

a 11 x 1 + a 12 x 2 + … + a 1n x n Ј b 1,

a 21 x 1 + a 22 x 2 + … + a 2n x n Ј b 2, x j і 0 (j =1,2, ..., n)

a m 1 x 1 + a m 2 x 2 + … + a mn x n Ј b m,

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

Z = C 1 x 1 + C 2 x 2 + … + C n x n,

მოდით განვსაზღვროთ რესურსები, რომლებიც საჭირო იქნება პროდუქტის წარმოებისთვის. მოდი აღვნიშნოთ რესურსების ღირებულების ერთეული, როგორც წარმოებული საქონლის ღირებულების ერთეული. და y i (j =1,2, ..., m) მეშვეობით i-ე რესურსის ერთეულის ღირებულება. იმათ. ყველა დახარჯული რესურსის ღირებულება, რომელიც გამოიყენება J-ე პროდუქტის ერთეულის გამოსაგონებლად არის. მოხმარებული რესურსების ფასი არ უნდა აღემატებოდეს საბოლოო პროდუქტის ფასს. ამრიგად, უტოლობა і C j , j =1,2, ..., n უნდა დაკმაყოფილდეს. ხელმისაწვდომი რესურსების ფასი არის.

მოდით ჩამოვაყალიბოთ ორმაგი პრობლემა.

აუცილებელია განვსაზღვროთ ვექტორი Y =(y 1 , y 2 , …, y n), რომელიც აკმაყოფილებს შეზღუდვებს

a 11 y 1 + a 12 y 2 + … + a m1 y m Ј C 1,

a 12 y 1 + a 22 y 2 + … + a m2 y m Ј C 2, y j і 0 (i =1,2, ..., m)

a 1n y 1 + a 2n y 2 + … + a mn y m Ј C m,

ვექტორი Y =(y 1, y 2, …, y n) არის წრფივი ფუნქციის მინიმალური მნიშვნელობა

f = b 1 y 1 + b 2 y 2 + … + b m y m

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

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

და ჩვენ განვსაზღვრავთ საწყის პრობლემას შემდეგნაირად: რამდენი და რა პროდუქტი x j (j =1.2, ..., n) უნდა წარმოიქმნას ისე, რომ მოცემული ხარჯებით C j (j =1.2, ..., n) ერთეული. ხელმისაწვდომი რესურსების წარმოება და ზომა b i (i =1,2, ..., n) მაქსიმალური გამომუშავების ღირებულების თვალსაზრისით.

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