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

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

ზმისტ

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

სიმეტრიული ორმხრივი დავალება

მოდით შევხედოთ ხაზოვანი პროგრამირების პრობლემას შეტევითი ტიპის საზღვრის გადაკვეთის სისტემაში უხილავი ცვლილებებით:
(1.1) ;
(1.2)
არის ათობითი რიცხვები. სისტემის სტრიქონებს (1.2) აქვს დარღვევები და ნიშნები.

(2.1) ;
(2.2)
აქ ჩვენ ვიყენებთ სისტემის რიგებს (2.2) დარღვევებით და ნიშნებით. სისტემის კოეფიციენტების მატრიცა იცვლება (2.2) ტრანსპონირებული სისტემის მატრიცასთან (1.2). Vaughn შურისძიების რიგები და stovptsiv. დაიცავით ცვლილების თანმიმდევრობა. Usі zminnі nevid'єmnі.

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

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

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

;

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

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

მოუთმენლად ველოდები:
;

;

ასიმეტრიული ორმხრივი დავალება

გამოწვევა მაქსიმუმამდე

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

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

Vіdmіnіst ასიმეტრიული ფსონი zavdan (3) და (4) vіd სიმეტრიული ფსონი (1) i (2) at tsomu, scho system obezhen (3.2) შურისძიების თანასწორობა და სისტემა (4.2) vіdsutnі გონება და ცვლილების არანეგატიურობა.

მინიმალური შეკვეთა

ახლა მოდით შევხედოთ მინიმუმ ხაზოვანი პროგრამირების კანონიკურ ამოცანას:
(5.1) ;
(5.2)

მოუთმენლად ველოდები:
(6.1) ;
(6.2)

გაცვლის სისტემა (6.2) მორგებულია (4.2) იმით, რომ ნიშნები არათანაბარია.

Zvyazok іz სიმეტრიული წყვილი ორმაგი zavdan

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

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

დარღვევები ნიშნებით გამრავლებული -1 :

სისტემა obmezhen maє nerіvnosti.

ფორმულები (1)-(2) მოითხოვს დამოკიდებულ ამოცანას:
;


ორი დავალება არ შეიძლება შეიცვალოს:
.
არ აქვს მნიშვნელობა, რა ცვლილებებია?
.

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

І mi otrimuєmo დაქვემდებარებული zavdannya (4):
(4.1) ;
(4.2)

თუ დავალებას ვიღებთ შაბათ-კვირისთვის (4), მაშინ, ყველა მოვალეობის დარღვევით სწორი თანმიმდევრობით, ვიღებთ დავალებას (3).

ანალოგიურად შესაძლებელია დაქვემდებარებული ამოცანის ამოღება (5) (6) და დავალებიდან (6) დაქვემდებარებული ამოცანის (5) ამოღება.

ზმიშანე ზავდანნია

ახლა მოდით შევხედოთ zmіshan zavdannya.

ნება მომეცით პირდაპირ წინ წავიდე (1) მაქსიმუმამდე; ტოდი ორმაგად ზავდანნიას შეიძლება ეძებოს (2) ერთი ბრალი - ცვლილება შეიძლება იყოს როგორც დადებითი, ასევე უარყოფითი. Tobto vіdsutnє obezhennya.

იგივე მოხდება, როგორც ჩვენ შეგვიძლია პირდაპირ zavdannya (2) მინიმუმ, სისტემაში obmezhenie, ასეთი რიგი არის ეჭვიანობა. ძირითადი დავალება შეიძლება ნახოთ (1) ერთი ბრალის გამო - ცვლილება შეიძლება იყოს ერთგვარი ნიშანი.

ახლა ნება მომეცით პირდაპირ მივიდე (1) მაქსიმუმამდე, მაგრამ არ არის დაბინძურება. Tobto ცვლილება შეიძლება იყოს როგორც დადებითი, ასევე უარყოფითი. ამგვარად, მენეჯერს შეუძლია ორმაგად გამოიყურებოდეს (2) ერთი ბრალისთვის - სისტემის რიგი obmezhen є rіvnіstyu.

მე აქ ვარ, ნება მომეცით პირდაპირ წავიდე (2) მინიმუმამდე, მაგრამ გაცვლა არ არის . ამგვარად, მენეჯერს შეუძლია ორჯერ გამოიყურებოდეს (1) ერთი ბრალი - obmezhen სისტემის რიგი є rіvnіstyu.

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

ორმაგი ამოცანების დასაკეცი წესები

1. გამომავალი მიზნისთვის მაქსიმუმამდე, სასაზღვრო პირობების სისტემის ყველა უთანასწორობა მცირდება შემდეგამდე:
.
მინიმუმ გარე ამოცანისთვის, ყველა შეუსაბამობა მიყვანილია თვალსაზრისამდე:
.
თუ საჭიროა ნიშნის შეცვლა, მაშინ ვამრავლებთ დარღვევების დამრღვევ ნაწილებს -1 .
2. ვაკეცებთ ფსონს ისევე, როგორც სიმეტრიული ფსონი.
3. რაც შეეხება გარე მენეჯერს, სისტემის რიგი obmezhen є rіvnіst, შემდეგ vikreslyuєmo გონებაში ორმაგი ამოცანების შეცვლის უხილავობა.
4. რაც შეეხება vihіdnomu zavdanny-ს, -ї zminnoї-სთვის გონების უხილავობის დღეს, მაშინ ორმაგი ამოცანის მე-3 რიგში ვცვლით უთანასწორობის ნიშანს თანასწორობის ნიშანზე.

კონდახის მარაგი

ხაზოვანი პროგრამირების ამოცანა მოცემულია:
;

დადე საცვალი.

მიზნის ფუნქცია არის ბოლო წევრი 5. იმისათვის, რომ її გამოვიდეს (2.1), შემოგვაქვს დოდამოს თანასწორობის ცვლილება. წინ გავიხედავ, რომ ვნახო:

;

Tse zavdannya є zavdannya მინიმალური ცვლილებისთვის. ამიტომ მთელი ნერვიულობა დედის ნიშნების გამოა. მესამე nerіvnіst შურისძიების ნიშანი. მოდით გავამრავლოთ იოგა -1 :

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

მატრიცა

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

საწყობი podvyne zavdannya მოსწონს სიმეტრიული ფსონი.
;

სისტემის გასასვლელი მენეჯერის 1, 2 და მე-4 მწკრივზე ფრაგმენტები გარშემორტყმულია თანასწორობით, მაშინ ცვლილების დამოკიდებულ მენეჯერში შეიძლება იყოს ნიშანი. უხილავი zminnoy є ნაკლები. ამასთან, გაითვალისწინეთ, რომ საშინელის უხილავობა შეიძლება გამოიყურებოდეს:
.

Oskіlki u vihіdny zavdnі zminnі і შეუძლია დედა dovіlnі ნიშნები, შემდეგ სისტემის მე-3 და მე-4 რიგები გარშემორტყმულია ორი ამოცანის ტოლობით.

ასეთ რანგში, ორი გზით, მე ვხედავდი:
;

მეოთხე მეოთხედიდან. მოდით შევცვალოთ її მნიშვნელობები და გავამრავლოთ მესამე მწკრივი -1 .

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

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

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

თუმცა, როგორც ჩანს, ხაზოვანი პროგრამირების კანის ამოცანას ე.წ. ხედვის (ორი) ამოცანა. ამავდროულად, სტრიქონები უნდა გადაიკვეთოს ღუმელებთან, უთანასწორობა ცვლის ნიშანს, მაქსიმუმი იცვლება მინიმალურით (წინააღმდეგ შემთხვევაში, მინიმალურის ჩანაცვლება არის მაქსიმალური). Zavdannya, podviyne მეორე - იგივე vihіdne zavdannya.

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

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

Virishennya პირდაპირი პრობლემა ოპტიმალური პროგრამირების პროგრამის შესახებ

ამ რესურსის ყველაზე მნიშვნელოვანი კორისტუვაჩივის მათემატიკური მომზადების მაღალი დონე არ არღვევს ბალანსებს ზედა და ქვედა გაცვლებთან და შესავალი დამატებითი ცვლილებების თანასწორობაზე გადასვლისთვის. ამასთან, მე აღვნიშნავ ცვლილების ნიშნებს, რომლებიც გამარჯვებულია გადაწყვეტილებებს შორის:
N - ვირუსების სახეობების რაოდენობა;
მ-ვიკორული სიროვინის ტიპების რაოდენობა;
b_ub - ხელმისაწვდომი რესურსების ვექტორი m;
A_ub არის m×N ზომის მატრიცა, კანის ელემენტი, რომელიც არის i ტიპის ყველაზე გავრცელებული რესურსი ერთი ტიპის j ტიპისთვის;
s - ვექტორი pributu vіd virobnitstvа one virobu dermal species;
x - კანის მოვლის ღონისძიებები (დასუფთავების ოპტიმალური გეგმა), რომელიც უზრუნველყოფს მაქსიმალურ მოგებას.

მეთიუ ფუნქცია
maxF(x)=c×x

Გაცვლა
A×x≤b

ცვლილების რიცხვითი მნიშვნელობები:
N=5; m=4; b_ub=; A_ub = [, , ,]; c=.

მენეჯერი
1. იცოდე x მაქსიმალური მოგების უზრუნველსაყოფად
2. იცოდეთ ყველაზე გავრცელებული რესურსები ღამის საათისთვის გვ.1
3. იცოდე რესურსების ჭარბი რაოდენობა (როგორიცაა სუნი є) pіd h vykonanny p.1

მაქსიმუმის მინიჭებისთვის (საკეტისთვის მინიჭებულია ფუნქციის ფუნქციის კოეფიციენტების მინიმალური, საჭიროა ჩაწეროთ უარყოფითი ნიშნით c = [-25, -35, -25, -40, -30] და იგნორირება მინუს ნიშანი მოგებამდე.

Wikoristannya აღიარების შედეგების ნახვისას:
x- ცვლილების მნიშვნელობების მასივი, რომელიც აწვდის მინიმალურ (მაქსიმალურ) სამიზნე ფუნქციას;
მოდუნებული- დამატებითი ცვლილებების მნიშვნელობა. ობმეჟენნუ-ნერვნოსტის შემთხვევაში კანი იცვლება. ცვლილების ნულოვანი მნიშვნელობა ნიშნავს, რომ ბირჟა აქტიურია;
წარმატება- მართალია, რადგან ფუნქცია შორს არის ოპტიმალური გადაწყვეტის ცოდნა;
სტატუსი- რეზოლუციის სტატუსი:
0 - ოპტიმალური გადაწყვეტის ძიება წარმატებით დასრულდა;
1 - მიაღწია ლიმიტს გამეორებების რაოდენობისთვის;
2 - გამოსავალი არ არის;
3 - სამიზნე ფუნქცია შეზღუდული არ არის.
nit- გატეხილი გამეორებების რაოდენობა.

ოპტიმიზაციის პირდაპირი ამოცანის ჩამონათვალი

#!/usr/bin/python # -*- კოდირება: utf-8 -*- იმპორტი scipy from scipy.optimize import linprog # LP ბიბლიოთეკის იმპორტი c = [-25, -35,-25,-40,-30] # პუნქტის ფუნქციის კოეფიციენტების სია b_ub = # რესურსის ელემენტების სია A_ub = [, ელემენტის რესურსის მნიშვნელობების # მატრიცა, , ] d=linprog(c, A_ub, b_ub) # საძიებო გადაწყვეტა გასაღებისთვის,val d.item-ში( ): print(key ,val) # scipy.array(b_ub)-scipy.array(q) #ჭარბი რესურსების ბეჭდვა(" b_ub-A_ub*x", q1)

ამოცანის გადაწყვეტის შედეგები
nit 3
სტატუსი 0

წარმატება მართალია
x [0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
გართობა -5863.63636364
slack[0.0.0.90.90909091]

ვისნოვკი

1. იპოვნეთ ოპტიმალური გეგმა პროდუქციის ტიპებისთვის
2. ნაპოვნია რეალურად რამდენიმე რესურსი
3. ნაპოვნია ჭარბი არა-ვიკორის მეოთხე ტიპის რესურსი [0. 0 0.0 0.0 90.909]
4. არ არის საჭირო მე-3 პუნქტის გადახდის გადახდა, რათა იგივე შედეგი გამოჩნდეს შეცვლილ სლაკში

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

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

გააცნო shukanoy zminnoy x-ის ახალი აღიარება, როგორც ერთგვარი "ჩრდილოვანი" ფასი, რომელიც განსაზღვრავს მოცემული რესურსის ღირებულებას იმ პროდუქციის გაყიდვაში, რომელიც გამოშვებულია.

გ - ხელმისაწვდომი რესურსების ვექტორი;
b_ub - კანის სახეობის ერთი ვარიანტის სიჭარბის ვექტორი;
A_ub_T - მატრიცა A_ub გადატანილია.

მეთიუ ფუნქცია
minF(x)=c×x

Გაცვლა
A_ub_T ×x≥ b_ub

რიცხვითი მნიშვნელობა და spivvіdnoshennia ცვლილებისთვის:
თ =; A_ub_T ტრანსპოზირება (A_ub); b_ub=.

მენეჯერი:
Know x გვიჩვენებს რესურსის კანის სახეობის მნიშვნელობას.

გადაწყვეტის მახასიათებლები scipy ბიბლიოთეკით. ოპტიმიზაცია
საზღვარზე ცეცხლის საზღვრის ქვემოდან ჩანაცვლებისთვის საჭიროა გავამრავლოთ მინუს საზღვრის ერთ-ერთი დამრღვევი ნაწილი - A_ub_T ×x≥ b_ub ... A_ub_T = - scipy.transpose(A_ub).

ორი ოპტიმიზაციის პრობლემის გამოყოფის ჩამონათვალი

#!/usr/bin/python # -*- კოდირება: utf-8 -*- იმპორტი scipy-დან scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) გასაღებისთვის,val d.items(): print(key,val)

ამოცანის გადაწყვეტის შედეგები
nit7
შეტყობინების ოპტიმიზაცია წარმატებით დასრულდა.
fun5863.63636364
x [2.27272727 1.81818182 6.36363636 0.]
slack [5.45454545 2.27272727 0. 0. 0. ]
სტატუსი 0
წარმატება მართალია

ვისნოვკი

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

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

1. პროდუქციის გამოშვების დაგეგმვის შესაძლებლობების გაფართოების ამოცანის აღება, მაგრამ სციპიის დახმარებით. ოპტიმიზაცია აჯობებს პირდაპირ გამეორებების რაოდენობას ორჯერ.
2. შეცვალეთ მოდუნება, რათა აჩვენოს ინფორმაცია ტერიტორიის აქტივობის შესახებ დარღვევების არსებობისას, რომელიც შეიძლება გამოყენებულ იქნას, მაგალითად, სიროვინის ჭარბი ანალიზისთვის.
3. პირდაპირი შეკვეთები მაქსიმიზაციისთვის, ხოლო ხაზის ქვეშ - მინიმიზაციისთვის და ნავპაკი.
4. p align=" justify">
5. პირდაპირი დავალების გაცვლა ხდება მეთოდის ფუნქციის კოეფიციენტები ქვეღვინებში.
6. ცვლაში დარღვევების ნიშნები იცვლება საპირისპიროებით.
7. ტრანსპონირებულია თანასწორობათა სისტემის მატრიცა.

პოსილანნია

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

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

ინსტრუქცია. აირჩიეთ ცვლილებების რაოდენობა და ობიექტების რაოდენობა პირდაპირი ხაზის პროგრამირებისთვის, დააჭირეთ Dali. გამოსავალი აღებულია Word და Excel ფაილებიდან. რა ტიპის ბირჟაზე x i ≥ 0არ ენდო. როგორც LP-ის პირდაპირი ამოცანა, გამოსავალი არ არის, მაგრამ აუცილებელია ჩამოყარეთ ორი ბრძანებაან ერთ-ერთი ბოლო x i არ არის დაყენებული, შეგიძლიათ გამოიყენოთ კალკულატორი .

ორმაგობის თეორიის მთავარი იდეა: წრფივი პროგრამირების (LP) კანის ამოცანაა LP-ის მთავარი ამოცანა, რომელიც მჭიდროდ არის დაკავშირებული პირდაპირ ხაზთან. Ვისთან ერთად:

• ორმაგი ამოცანის ქვედანაყოფის მატრიცა (DZ) - პირდაპირი ამოცანის მატრიცა გადატანილია;
• ვექტორი "tsіn" პირდაპირი ამოცანისთვის არის დისტანციური ზონდირების და ნავპაკის პრობლემის საზღვრის მარჯვენა ნაწილების ვექტორი.

ორი დავალების დასაკეცი ზოგადი წესები ():

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

კონდახი. მნიშვნელოვანია, რომ მიზნობრივი ფუნქციის მაქსიმალური მნიშვნელობა F(X) = 3x1+5x2+4x3 შემტევი გონების დელიმიტაციისთვის.
0.1x1 + 0.2x2 + 0.4x3 ≤1100
0.05x1 + 0.02x2 + 0.02x3 ≤120
3x1 + x2 + 2x3 ≤8000

ვირიშიმო უშუალოდ სიმპლექსის მეთოდის გამოყენებით.
პირველი საბაზისო გეგმის დანერგვის მიზნით, დამატებითი ცვლილებების მიწოდების გზით მოხდება დარღვევების სისტემა თანასწორობის სისტემაზე აყვანა.
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1+0.02x2+0.02x3+0x4+1x5+0x6=120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
ძირითადი ცვლილებები არის ცვლილებები, რომლებიც შედის ობმეჟენის მხოლოდ ერთ თანაბარ სისტემაში და მანამდე ერთიანი კოეფიციენტით.
მოდით დავშალოთ ძირითადი ცვლილებების გათანაბრების სისტემა: x 4 , x 5 , x 6
იმის მიხედვით, თუ რა შეგიძლიათ შეცვალოთ 0-ის დასამატებლად, ჩვენ ვიღებთ პირველ საცნობარო გეგმას: X1 = (0,0,0,1100,120,8000)
ამოცანის ფრაგმენტები მასშტაბირება ხდება მაქსიმუმამდე, შემდეგ სახელმძღვანელო ხაზი არჩეულია მაქსიმალური უარყოფითი რიცხვისა და ინდექსის მწკრივისთვის. ყველა ტრანსფორმაცია ხორციელდება წერტილებით, წერტილები არ ჩანს დადებითი ელემენტების ინდექსის რიგში.
გადავდივართ სიმპლექსის მეთოდის მთავარ ალგორითმზე.

Გეგმა	საფუძველი	ზე	x 1	x2	x 3	x4	x5	x6	წთ
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
ინდექსის მწკრივი	F(X1)	0	-3	-5	-4	0	0	0	0

გამეორება №0
მიმდინარე საცნობარო გეგმა არ არის ოპტიმალური, ინდექსის მწკრივში მწვერვალები უარყოფითი კოეფიციენტებია
როგორც წამყვანი vibero stovpets, როგორც წამყვანი ცვლადი x 2 ისე როგორც ყველაზე დიდი კოეფიციენტის მოდული.
ოტჟე, პირველი რიგი განხორციელდება. ცალკე ელემენტი უფრო ძვირია 0.2 და მდებარეობს მავთულის რიგის მავთულის ხაზზე. სიმპლექსის ცხრილის ნაწილი. შეცვალეთ x ცვლილება გეგმაზე 1 ცვლილება ცვლილება x 2 . რიგი, რომელიც ცვლის x 2-ს გეგმა 1-ში, ამოღებულია x 4 რიგის ყველა ელემენტის გეგმის 0-ზე დამატების შედეგად ცალკე შენობის ელემენტისთვის PE = 0.2. 1 გეგმაში გამანაწილებელი ელემენტის ადგილას აღებულია 1.
ამ თანმიმდევრობით, ახალ გეგმას აქვს 1 მწკრივი x 2 და მწკრივი x 2.
ახალი გეგმის 1-ის ყველა ელემენტის რეშტა, ინდექსის მწკრივის ელემენტების ჩათვლით, მიჰყვება მართკუთხედის წესს.
რისთვისაც არჩეულია ძველი გეგმის მიხედვით, ზოგიერთი რიცხვი, იაკ roztashovanі მართკუთხედის ზედა ნაწილში და zavzhd მოიცავს ცალკე სამშენებლო ელემენტს PE.
NOT = CE - (A * B) / PE
CTE - ძველი გეგმის ელემენტი, PE - ცალკე შენობის ელემენტი (0.2), A და B - ძველი გეგმის ელემენტები, რომლებიც ქმნიან ოთხკუთხედს CTE და PE ელემენტებით.

Გეგმა	საფუძველი	ზე	x 1	x2	x 3	x4	x5	x6	წთ
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
ინდექსის მწკრივი	F(X2)	27500	-0.5	0	6	25	0	0	0

გამეორება №1
მიმდინარე საცნობარო გეგმა არ არის ოპტიმალური, ინდექსის მწკრივში მწვერვალები უარყოფითი კოეფიციენტებია. როგორც წამყვანი vibero stovpets, მთავარი ცვლადი x 1, სასწორები არის ყველაზე დიდი კოეფიციენტის მოდული.
მოდით გამოვთვალოთ D i მნიშვნელობები მწკრივებისთვის, ასევე ქვეხაზში და მათგან ავირჩიოთ ყველაზე მცირე:
Otzhe, კიდევ ერთი რიგი є provіdnim. ცალკე ელემენტი უფრო ძვირია 0.04 და მდებარეობს მავთულის რიგის მავთულის ხაზზე. სიმპლექსის ცხრილის ნაწილი. შეცვალეთ x გეგმის 2 ცვლილება შეცვალეთ x 1. მწკრივი, რომელიც იყო მთავარი ცვლილება x 1 გეგმა 2-ში, ამოღებულ იქნა 1 გეგმაში x 5 რიგის ყველა ელემენტის დაყოფის შედეგად ცალკე შენობის ელემენტისთვის PE = 0.04. გეგმა 2-ში გამანაწილებელი ელემენტის ადგილას აღებულია 1.
ამ თანმიმდევრობით, ახალ გეგმას აქვს 2 მწკრივი x 1 და მწკრივი x 1.
ახალი გეგმის 2-ის ყველა ელემენტის რეშტა, ინდექსის მწკრივის ელემენტების ჩათვლით, მიჰყვება მართკუთხედის წესს.
ჩვენ ვხედავთ კანის ელემენტის ზრდას ცხრილში:

მაგალითი ნომერი 2. ვიკონანიისთვის აუცილებელია ფრენა 1-ლი ტიპის 50 AK, მე-2 ტიპის 30 აკ და მე-3 ტიპის 45 აკ. ა.კ. როზთაშოვანი I და II აეროდრომებზე. წარმოდგენების ცხრილში ზლოტის საშუალო საათი (წამებში) მოცემული ტიპის ერთი თვითმფრინავის ერთი აეროდრომიდან.

აეროდრომის ნომერი	ტიპი AK
	1	2	3
მე	4	10	10
II	6	8	20

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

გამოსავალი. მნიშვნელოვანი მეშვეობით:
x 11 - AK 1-ლი ტიპი პირველ აეროდრომზე,
x 12 - AK 1 ტიპის სხვა აეროდრომზე,
x 21 - AK ტიპი 2 პირველ აეროდრომზე,
x 22 - AK ტიპი 2 სხვა აეროდრომზე,
x 31 - AK მე-3 ტიპი პირველ აეროდრომზე,
x 32 - AK მე-3 ტიპი სხვა აეროდრომზე,

Გაცვლა
4x11 + 6x12 = 50
10x21 + 8x22 = 30
10x31 + 20x32 = 45
x 11, x 12, x 21, x 22, x 31, x 32 ≥ 0
x 11, x 12, x 21, x 22, x 31, x 32 - ნომრები

დანიშნულების ფუნქცია
4x 11 + 6x 12 + 10x 21 + 8x 22 +10x 31 + 20x 32 → წთ

აღმოჩენილი გადაწყვეტის შემდეგ, პირველი კვების წყაროდან გამომდინარე, ცვლილების მნიშვნელობები იქნება x 11 x 12 x 21 x 22 x 31 x 32. ინფორმაცია სხვა კვებაზე მუშაობის შესახებ განთავსდება ჯანმრთელობის ფუნქციის სტაბილურობის კოეფიციენტების ინტერვალის განაწილებისას.

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

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

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

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

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

თეორემა 2. ოპტიმალური გეგმის კომპონენტები ორი ამოცანისთვის ( vodіyut გონებრივი სიბნელე) თანაბარი კოეფიციენტების აბსოლუტური მნიშვნელობები

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

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

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

. (7.2)

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

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

ყოველკვირეული დანიშვნა	შემცვლელი zavdannya

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

ყოველკვირეული დანიშვნა	შემცვლელი zavdannya

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

იყიდება pіdbags rіshennya კონდახით 5.2. დარჩენილი გამეორების მარტივი ცხრილი (ცხრილი 5.10) შეიძლება გამოიყურებოდეს:

ცხრილი 9.3

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

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

ოტჟე,.

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

თეორემა 1-ის მსგავსი, .

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

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

ყოველკვირეული დანიშვნა	შემცვლელი zavdannya

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

ყოველკვირეული დანიშვნა	შემცვლელი zavdannya

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

ყოველკვირეული დანიშვნა	შემცვლელი zavdannya

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

ცხრილი 9.4

Vidpovіdnіst zmіnnih dvostiї ფსონი

Virіshimo vyhіdne zavdannya simplex მეთოდი.

ჟორდანია-გაუსის ვიკორისტოვიუჩის მეთოდი, რომელიც ჩანს გამომავალი ქარხნის გარემოს სისტემაში, როგორც ძირითადი ცვლილება ( შენიშვნა:არ გაიმარჯვო, როგორც ძირითადი ფიქტიური ცვლილებები).

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

.

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

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

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

Simplex-მეთოდის ამოხსნის შედეგად საბოლოო დავალება ხელახლა დალაგდა დანარჩენი გამეორებისთვის, გამოჩნდება simplex-ცხრილი:

ცხრილი 9.5

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

თქვენ შეგიძლიათ იმღეროთ სიმღერის წოდებით, რათა გააკეთოთ დღე სხვა დავალების (წრფივი პროგრამირება), რომელსაც ე.წ ორმაგიან pov'yazanoї დანიშვნის გზით vihіdnoї ან პირდაპირი ამოცანები. დამოს გაფართოებით ორ დავალებაზეა დანიშნული ხაზის პროგრამირების ხელმძღვანელი, რაც ემატება, როგორც უკვე ვიცით, ფუნქციის მაქსიმალურ მნიშვნელობაზე

გონებისთვის

(33)

(34)

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

გონებისთვის

(36)

(37)

დაურეკა მეტროსთვისპაემანზე დანიშვნით (32) - (34). ამოცანები (32) - (34) და (35) - (37) ადგენენ ამოცანების წყვილს, როგორც მათ უწოდებენ ხაზოვან პროგრამირებაში ორმაგი წყვილი. Porіvnyuyuchi დავალების ორი ფორმულირება, ბაჩიმო, რომ ორმაგი დავალება იკეცება შემდეგი წესებით:

1. გამომავალი ამოცანის (32) - (34) მიზნობრივი ფუნქცია დაყენებულია მაქსიმუმზე, ხოლო ორობითი (35) - (37) მიზნობრივი ფუნქცია მინიმალურია.

2. მატრიცა

(38)

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

(39)

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

3. ცვლილებების რაოდენობა დამოკიდებული ქარხნისთვის (35) - (37) იგივეა, რაც სისტემის (33) ცვლილებების რაოდენობა გამავალი ამოცანისთვის (32) - (34) და ცვლილებების რაოდენობა ორმაგი დავალების სისტემა (36) არის ცვლილებების რაოდენობა გამავალი ქარხნისთვის.

4. ორობითი ამოცანის (35) - (37) არამთლიანი ფუნქციების (35) კოეფიციენტები არის გარე ამოცანის (32) - (34) სისტემის (33) თავისუფალი წევრები და მარჯვენა ნაწილები. ორობითი ამოცანის სისტემის (36) თანმიმდევრული მიმართებების - კოეფიციენტები უცნობი ფუნქციის (32) გამომავალი ამოცანებისთვის.

5. როგორი ცვალებადია xjგამომავალი ამოცანა (32) - (34) შეიძლება მხოლოდ დადებითი მნიშვნელობების დაგროვება, მაშინ ჯ-ე სისტემის გონება (36) ორმხრივი დავალება (35) - (37) є არათანაბარი გონება “? ". რა ცვლილებაა xjშეუძლია მიიღოს როგორც დადებითი, ასევე უარყოფითი მნიშვნელობები, მაშინ 1 – spіvvіdnoshennia სისტემაში (54) є vnyannâ. მსგავსი კავშირები შეიძლება მოიძებნოს გარე მცენარის (32) - (34) ბირჟებს (33) და ორმაგი მცენარის ცვლილებას (35) - (37) შორის. იაკშო მე- Spivvіdnoshennia სისტემაში (33) გამავალი ამოცანის є nerіvnіstyu, შემდეგ მევცვლი ორ ამოცანას. სხვაგვარად, შეცვალეთ ზე ჯ შეგიძლიათ მიიღოთ როგორც დადებითი, ასევე უარყოფითი მნიშვნელობები.

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

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

(40)

გონებისთვის

(41)

გამოსავალი.ვისთვის

і

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

გამავალი დავალების მიზნობრივი ფუნქცია (40) - (42) აღწევს მაქსიმუმს, ხოლო გონების სისტემა (41) ნაკლებად თანაბარია. ამიტომ ორმაგ ამოცანაში მიზნის ფუნქცია მცირდება მინიმუმამდე და її zminnі-ს შეუძლია ნებისმიერი მნიშვნელობის (მათ შორის უარყოფითის) მიღება. თუ სამივე ცვალებადმა ამოცანამ (40) - (42) იძენს უხილავზე ნაკლებ მნიშვნელობას, მაშინ ორმხრივი ამოცანის გონების სისტემამ შესაძლოა „? ". ასევე, ამოცანისთვის (40) - (42) შემდეგი ამოცანაა: იცოდე გონებისთვის მინიმალური ფუნქცია

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

გონებისთვის

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

გამოსავალი.ვისთვის

,

Vіdpovіdno zagalnyh წესები zavdannya, podvіyne vіyne vіdnoshennі to danї, ჩამოყალიბებული მომავალი რანგის მიხედვით: იცოდე ფუნქციის მინიმალური გონებისთვის

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

მოდით გადავხედოთ რამდენიმე ორმაგ ამოცანას, მე დავაფიქსირებ წრფივი პროგრამირების ძირითად ამოცანებს და მის წინა ორ დავალებას. Out of box: იცოდე ფუნქციის მაქსიმუმი

გონებისთვის

(44)

მთავარი ამოცანა: იცოდე ფუნქციის მინიმუმი

გონებისთვის

(47)

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

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

ლემა 1.თუ X არის გამომავალი ამოცანის მიმდინარე გეგმა (43) - (45), Y არის ორმაგი ამოცანის დამატებითი გეგმა (46), (47), მაშინ გამომავალი ამოცანის სამიზნე ფუნქციის მნიშვნელობა X გეგმით აკეთებს. ყოველთვის არ აღემატებოდეს ორმაგი დავალების სამიზნე ფუნქციის მნიშვნელობას გეგმით Y, tobto.

ლემა 2.თუ არსებობს რაიმე გეგმები X * და Y * დავალება (43) - (45) და (46), (47), მაშინ X * არის შაბათ-კვირის დავალების ოპტიმალური გეგმა, ხოლო Y * არის ორმაგი დავალების ოპტიმალური გეგმა. .

თეორემა 8(პირველი ორმაგობის თეორემა). ვინაიდან ერთ-ერთი ორმხრივი ფსონის ამოცანა (43) - (45) და (46), (47) შეიძლება იყოს ოპტიმალური გეგმა, მეორე შეიძლება იყოს ოპტიმალური გეგმა და ამოცანის მიზნობრივი ფუნქციების მნიშვნელობა მათი ოპტიმალურისთვის. გეგმები ერთმანეთის ტოლია, ტობტო.

ისე, ერთი დავალების გოლის ფუნქცია ორჯერადი ფსონისთვის არ არის შეზღუდული (ორმაგისთვის (43) - (45) - ზევით, ორმაგისთვის (46), (47) - ქვევით), შემდეგ ამოცანა არ არის დაგეგმილი.

თეორემა 9(კიდევ ერთი ორმაგობის თეორემა). Გეგმა ამოცანა (43) - (45) რომ გეგმა ამოცანები (46), (47) - ამ ამოცანების ოპტიმალური გეგმები არის ხანდახან და მხოლოდ ხანდახან, თუ თანასწორობა მოიპოვება ნებისმიერ შემთხვევაში.

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

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

მაგალითი 3.

დაკეცეთ ორი დავალება და იცოდეთ ორივე ამოცანის ამოხსნა.

გამოსავალი.ორ მენეჯერს ჰყავს ას ასი თავი, რომლებიც განიხილება გონებისთვის ფუნქციის განსაზღვრული მინიმალური მნიშვნელობით

შაბათ-კვირის მსგავსად, და ორმაგი დავალება, nevіdomih dovnyuє ორი. ასევე, შესაძლებელია ვიცოდეთ ხაზოვანი პროგრამირების პრობლემის მისი ვარიანტის, ვიკორისტული გეომეტრიული ინტერპრეტაცია (სურ. 7 და 8).

როგორც ჩანს ნახ. 8, გამომავალი ამოცანის სამიზნე ფუნქციის მაქსიმალური მნიშვნელობა აღებულია წერტილში Ხელოვნება.ოტჟე, x*=(2, 6) არის ოპტიმალური გეგმა, რომლისთვისაც . ორმაგი ამოცანის მიზნის ფუნქციის მინიმალური მნიშვნელობა დაყენებულია წერტილამდე ე(ნახ. 8). ანუ, ი* =(1; 4) არის ორმაგი დავალების ოპტიმალური გეგმა, ასეთი რანგით, ორმაგი და ორმაგი ამოცანების სამიზნე ფუნქციების მნიშვნელობა მათი ოპტიმალური გეგმებისთვის უდრის ერთმანეთს.

3 ნახ. 7 ჩანს, რომ მომავლის ნებისმიერი გეგმის შემთხვევაში სამიზნე ფუნქციის სამიზნე მნიშვნელობა 46-ზე მეტია. ერთბაშად, როგორც ჩანს ნახ. 8, დამოკიდებული ამოცანის სამიზნე ფუნქციის მნიშვნელობა ნებისმიერი გეგმის შემთხვევაში არ არის 46-ზე ნაკლები. ამ რანგის, vihіdnoї დავალების ნებისმიერი გეგმის შემთხვევაში, სამიზნე ფუნქციის მნიშვნელობა არ აღემატება მნიშვნელობას. წარმატებული გეგმის შემთხვევაში დამოკიდებული ამოცანის მიზნობრივი ფუნქცია.

კონდახი 4.

იცოდე ორმაგი ფსონის გადაწყვეტა.

ყოველკვირეული დანიშვნა;

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

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

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

ორი ამოცანის ამოხსნის მნიშვნელობა. მოდით შევხედოთ რამდენიმე ორ ამოცანას - ხაზოვანი პროგრამირების მთავარი ამოცანა (43) - (45) და ორი ამოცანა (46), (47).

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

საგრძნობლად მეშვეობით ვექტორ-სერიები, ამოცანების (43) - (45) არადომინანტური ფუნქციებით (43) კოეფიციენტების შეკრება და – მატრიცა, საპირისპირო მატრიცა რდაკეცვა კომპონენტებიდან ვექტორულ საფუძველზე. Todi maє mіsce ასეთი სიმტკიცე.

თეორემა 10.როგორც ხაზოვანი პროგრამირების მთავარი ამოცანა, ოპტიმალური გეგმა X * არის ოპტიმალური გეგმა ორმაგი ამოცანისთვის.

ამ გზით, იმისათვის, რომ ვიცოდეთ ამოცანის (43) - (45) ოპტიმალური გეგმა სიმპლექსის მეთოდით, მაშინ, სიმპლექსის მაგიდა, შეგიძლიათ მიუთითოთ დამატებითი მხარდაჭერა იცოდეს ორმაგი ამოცანის ოპტიმალური გეგმა (46), (47).

ამ შემთხვევაში, თუ სისტემაში უცნობის კოეფიციენტებიდან დაკეცილი შუა ვექტორები უდრის (44), є თერთეულებში, მატრიცა ნაჩვენებია პირველის რიცხვების დასაკმაყოფილებლად თრიგები დანარჩენი სიმპლექსის ცხრილში, რომელიც უნდა იყოს ამ ვექტორების ზედა ნაწილში.თუმცა, არ არის საჭირო ორმაგი პრობლემის ოპტიმალური გეგმის განსაზღვრა გამრავლებით მ+1) – stovptsіv ცალ ვექტორიანის მე-ე მწკრივი, მოცემული კოეფიციენტის სახით და დაამატეთ მე-ე რიგისა და იაკშოს იგივე ელემენტის ჯამი.

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

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

შეაერთეთ ორი ამოცანა და იცოდეთ її ამოხსნა.

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

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

ოპტიმალური ორი ქულა აკმაყოფილებს დამოკიდებული მუშის ულვაშ გონებას. მეტროს ქარხნის სამიზნე ფუნქციის ნებისმიერი მინიმალური მნიშვნელობით მეტია zbіgaєtsya გამომავალი ამოცანის სამიზნე ფუნქციის მაქსიმალური მნიშვნელობით.

ცხრილი 12

მე	საფუძველი	ვ ბ	p0	1	2	-1	0	0	-მ
				p1	p2	გვ 3	p4	p5	p6
1 2 3 4 5 1 2 3 4 1 2 3 4	p4 p5 p6 P4 p5 p1 P2 p5 p1	0 0 -მ 0 0 1 2 0 1	12 17 4 0 -4 14 15 2 2 4 9 4 12	-1 1 2 -1 -2 0 0 1 0 0 0 1 0	4 1 -1 -2 1 7/2 3/2 -1/2 -5/2 1 0 0 0	-2 2 2 1 -2 -1 1 1 2 -2/7 13/7 6/7 9/7	1 0 0 0 0 1 0 0 0 2/7 -3/7 1/7 5/7	0 1 0 0 0 0 1 0 0 0 1 0 0	0 0 1 0 0 1/2 -1/2 1/2 1/2 1/7 -5/7 4/7 6/7

ორმაგი ამოცანების ეკონომიკური ინტერპრეტაცია

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

მაგალითი 6.სამი სახის შერჩევის შერჩევისთვის ა ,ზეі ვ vikoristovuetsya სამი სხვადასხვა vidi syrovini. სიროვინის სახეობის ტყავს შეიძლება ჰქონდეს ვიკორისტანია, მაგრამ არაუმეტეს 180, 210 და 244 კგ. კანის ტიპის ვიტრატის ნორმები ამ ტიპის პროდუქტის ერთეულისთვის და კანის ტიპის პროდუქტის ერთეულის ფასი მოცემულია ცხრილში 13.

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

ცხრილი 13

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

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

(52)

იაკ ბაჩიმო, დავალება (48) - (50) და (51) - (53) დაადგინეთ ორმაგი ამოცანების სიმეტრიული წყვილი. პირდაპირი პრობლემის გადაწყვეტა იძლევა ნიმუშების შერჩევის ოპტიმალურ გეგმას. ა, ზეі ვდა ორმაგი გადაწყვეტილება - სიროვინის შეფასების ოპტიმალური სისტემა, ამ სელექციების ვიკარული შერჩევა. იმისათვის, რომ განვსაზღვროთ rozvyazannya tsikh zavdan, შემდეგ ვიცოდეთ გამოსავალი, იქნება ეს მათგან. Oskіlki system obmezhenie zavdannya (48) - (50) შურისძიება გონების უთანასწორობაზე ” ”, უკეთ იცოდეთ ამ ამოცანის დაშლა. Її გადაწყვეტილება მიიღება ცხრილში 14.

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

ცხრილი 14

მე	საფუძველი	ვ ბ	p0	10	14	12	0	0	0
				p1	p2	გვ 3	p4	p5	p6
1 2 3	p2 p5 გვ 3	14 0 12	82 80 16 1340	19/8 23/8 -3/4 57/4	1 0 0 0	0 0 1 0	5/8 1/8 -1/4 23/4	0 1 0 0	-1/8 -5/8 1/4 5/4

ცვლილებები და მნიშვნელობები ნიშნავს ერთი სიროვინის ორ ქულას, როგორც ჩანს, I და III ტიპებს. ქულები აღინიშნება როგორც ნული, ხოლო სიროვინა 1 და III გამარჯვებულია პროდუქციის წარმოების ოპტიმალური გეგმით. ერთი სეროტიპის II ტიპის ქვექულა ნულს უახლოვდება. ამ ტიპის სიროვინი კვლავ გამარჯვებული იქნება ვირობნიციის ოპტიმალური გეგმით.

ამგვარად, დადებითი ხაზგასმა შეიძლება აიღოთ თქვენ, თითქოს უფრო გამარჯვებული ქულების შერჩევის ოპტიმალური გეგმით. ამასთან, დაბალ შეფასებას განსაზღვრავს სიროვინის დეფიციტი, რომელიც მოიგებს ვალდებულებას. უფრო მეტიც, ორმაგი შეფასების მნიშვნელობა გვიჩვენებს, თუ რამდენად იზრდება პირდაპირი დავალების სამიზნე ფუნქციის მაქსიმალური მნიშვნელობა მსგავსი ტიპის სიროვინის რაოდენობის ზრდით 1 კგ-ზე. ამრიგად, პირველი ტიპის სიროვინის ოდენობის ზრდა 1 კგ-ზე დამზადდა მანამ, სანამ შესაძლებელი გახდებოდა ვირობივის წარმოების ახალი ოპტიმალური გეგმის ცოდნა, მომზადებული პროდუქციის დიდი მრავალფეროვნებით, ზრდა 5,75 რუბლით. . და გახდება ტოლი 1340+5.7 5= 1345,75 რუბლი ამ რიცხვით, რომელიც უნდა იყოს ვექტორული ცხრილის ზედა 14-ში, აჩვენეთ, რომ მზადდება პროდუქტების მთლიანი რაოდენობის ზრდა შესაძლებელია რაჰუნოკისთვის. zbіlshennya vypusku vrobіv ზე 5/8 ერთისთვის. რომ ვირობივის მოკლევადიანი გამოშვება ვ 1/4-ისთვის. რის შედეგადაც მეორე ტიპის მამხილებელი შეიცვლება 1/8 კგ-ით. ასე რომ, III ტიპის სიროვინის 1 კგ-ის მატება საშუალებას გაძლევთ იცოდეთ სირობების წარმოების ახალი ოპტიმალური გეგმა, მომზადებული პროდუქტების დიდი მრავალფეროვნებით, ზრდა 1,25 რუბლით. მე დავაყენე 1340 +1.25 = 1341.25 რუბლი. Ce მიიღწევა ხმების გათავისუფლების გაზრდის შემთხვევაში ვ 1/4-ისთვის. რომ ვირობივის მომზადების ცვლილება 1/8 ერთით, უფრო მეტიც, ეს იყო II ტიპის ზრდის სავალდებულო ვიკორი სიროვინი 5/8 კგ-ით.

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

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

უპირველეს ყოვლისა, ორმხრივი ამოცანა სუვორის შეუსაბამობავით გადაილახება. ცე ნიშნავს, რომ სიროვინის შეფასება ამაღლებულია, რომ ის გამარჯვებულია ერთი ტიპის არჩევისთვის ა, მეტი tsіni tsgogo virobu i, otzhe, დაე ვირობი გონება აუხილავი. ეს მრავალფეროვნება არ არის გადალახული პირდაპირი პრობლემის ოპტიმალური გეგმით. მეორე და მესამე ორმხრივი ამოცანების გაცვლა გამარჯვებულია, როგორც სუვორის ეკვივალენტობა. ცე ნიშნავს, რომ არსებობს სიროვინის ორი ქულა, რომ ის არის გამარჯვებული ერთი ადამიანის არჩევანისთვის. ზეі ვზუსტად მათი ფასების ტოლია. ამიტომ ჩვენ გთავაზობთ ორ სახეობის პროდუქტს ორი შეფასებისთვის ეკონომიურად და ეკონომიურად. ამ ცვალებადობას ანაცვლებს პირდაპირი მიწოდების ოპტიმალური გეგმა.

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