მესამე რიგს ვყოფთ საკვანძო ელემენტზე 5-ის ტოლი, ვიღებთ ახალი ცხრილის მესამე რიგს.

საბაზისო სვეტები შეესაბამება ერთ სვეტს.

ცხრილის დარჩენილი მნიშვნელობების გაანგარიშება:

"BP - ძირითადი გეგმა":

; ;

"x1": ; ;

"x5": ; .

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

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

დავალება ნომერი 2

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

იმიტომ რომ შიფრის ბოლო ციფრი არის 8, შემდეგ A=2; B=5.

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

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

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

ეს ფართობი არის ABC სამკუთხედი წვეროების კოორდინატებით: A(0; 2); B(4; 6) და C(16/3; 14/3).

ობიექტური ფუნქციის დონეები არის წრეები, რომლებიც ორიენტირებულია წერტილზე (2; 5). რადიუსების კვადრატები იქნება ობიექტური ფუნქციის მნიშვნელობები. შემდეგ ნახაზი აჩვენებს, რომ ობიექტური ფუნქციის მინიმალური მნიშვნელობა მიღწეულია H წერტილში, მაქსიმალური მნიშვნელობა არის A წერტილში ან C წერტილში.

ობიექტური ფუნქციის მნიშვნელობა A წერტილში: ;

ობიექტური ფუნქციის მნიშვნელობა C წერტილში: ;

ეს ნიშნავს, რომ ფუნქციის მაქსიმალური მნიშვნელობა მიიღწევა A(0; 2) წერტილში და უდრის 13-ს.

ვიპოვოთ H წერტილის კოორდინატები.

ამისათვის განიხილეთ სისტემა:

ó

ó

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

მერე ; ; - ფუნქციის მინიმალური მნიშვნელობა.

2) შეადგინეთ ლაგრანგის ფუნქცია მინიმალური ამოხსნის საპოვნელად:

ზე x 1 =2.5; x 2 =4.5 ჩვენ ვიღებთ:

ó

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

ჩვენ ვადგენთ Lagrange ფუნქციას მაქსიმალური ამოხსნის საპოვნელად:

საკმარისი პირობები ექსტრემისთვის:

ზე x 1 =0; x 2 =2 ჩვენ ვიღებთ:

ó ó

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

პასუხი:მიზნობრივი ფუნქციის მინიმუმი მიღწეულია ; ; მაქსიმალური ობიექტური ფუნქცია მიიღწევა როცა ; .

დავალება ნომერი 3

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

i=8, k=1.

A=2200; k 1 =6; k2=1; n=0.2; m=0.5.

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

მთელი 4 წლის პერიოდი დაყოფილია 4 ეტაპად, რომელთაგან თითოეული უდრის ერთ წელს. ეტაპები დავთვალოთ პირველი წლიდან დაწყებული. მოდით X k და Y k იყოს A და B საწარმოებისთვის შესაბამისად გამოყოფილი თანხები k-ე ეტაპზე. მაშინ ჯამი X k + Y k =a k არის k - ამ ეტაპზე გამოყენებული სახსრების ჯამური რაოდენობა და დარჩენილი წინა ეტაპიდან k - 1. პირველ ეტაპზე გამოყენებულია ყველა გამოყოფილი თანხა და 1 =2200 ერთეული. შემოსავალი, რომელიც მიიღება k-ის ეტაპზე, როდესაც X k და Y k ერთეულები გამოიყოფა, იქნება 6X k + 1Y k. კ-დან დაწყებული ბოლო ეტაპებზე მიღებული მაქსიმალური შემოსავალი - ეს ეტაპი არის f k (a k) ერთეული. მოდით დავწეროთ ბელმანის ფუნქციონალური განტოლება, რომელიც გამოხატავს ოპტიმალურობის პრინციპს: როგორიც არ უნდა იყოს საწყისი მდგომარეობა და საწყისი ამონახსნები, შემდეგი ამონახსნი უნდა იყოს ოპტიმალური საწყისი მდგომარეობის შედეგად მიღებული მდგომარეობის მიმართ:

თითოეული ეტაპისთვის თქვენ უნდა აირჩიოთ მნიშვნელობა X k და მნიშვნელობა Y k=აკ- Xკ. ამის გათვალისწინებით, ჩვენ ვიპოვით შემოსავალს k-ე ეტაპზე:

ბელმანის ფუნქციური განტოლება ასე გამოიყურება:

განვიხილოთ ყველა ეტაპი, ბოლოდან დაწყებული.

(რადგან წრფივი ფუნქციის მაქსიმუმი მიიღწევა სეგმენტის ბოლოს x 4 = a 4-ზე);

საკონტროლო სამუშაო დისციპლინაზე:

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

ვარიანტი ნომერი 8

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

,

.

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

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

9x1 +3x2 ≥30, (1)

X 1 + x 2 ≤4, (2)

x 1 + x 2 ≤8, (3)

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

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

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

პირდაპირ
კვეთს რეგიონს C წერტილში. ვინაიდან C წერტილი მიიღება (4) და (1) წრფეების გადაკვეთის შედეგად, მაშინ მისი კოორდინატები აკმაყოფილებს ამ წრფეების განტოლებებს:
.

განტოლებათა სისტემის ამოხსნის შემდეგ მივიღებთ: x 1 = 3,3333, x 2 = 0.

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

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

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

პირდაპირ
კვეთს რეგიონს B წერტილში. ვინაიდან B წერტილი მიიღება (2) და (3) წრფეების გადაკვეთის შედეგად, მაშინ მისი კოორდინატები აკმაყოფილებს ამ წრფეების განტოლებებს:

.

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

პასუხი:
და
.

2 . ამოხსენით წრფივი პროგრამირების ამოცანა სიმპლექსის მეთოდით:

.

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

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

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

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

მნიშვნელობის პირველ უტოლობაში (≥) შემოგვაქვს ძირითადი ცვლადი x 3 მინუს ნიშნით. მნიშვნელობის მე-2 უტოლობაში (≤) შემოგვაქვს ძირითადი ცვლადი x 4 . მე-3 მნიშვნელობის უტოლობაში (≤), შემოგვაქვს ძირითადი ცვლადი x 5 .

შემოვიტანოთ ხელოვნური ცვლადები : 1-ელ ტოლობაში შემოგვაქვს ცვლადი x 6 ;

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

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

მიღებულ საფუძველს ეწოდება ხელოვნური, ხოლო ამოხსნის მეთოდს ეწოდება ხელოვნური ბაზის მეთოდი.

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

განტოლებიდან გამოვხატავთ ხელოვნურ ცვლადებს: x 6 \u003d 4-x 1 -x 2 +x 3, რომელსაც ვანაცვლებთ ობიექტურ ფუნქციაში: ან.

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

მოდით ამოხსნათ განტოლებათა სისტემა ძირითადი ცვლადების მიმართ: x 6 , x 4 , x 5.

თუ დავუშვებთ, რომ თავისუფალი ცვლადები არის 0, ჩვენ ვიღებთ პირველ საბაზისო ხაზს:

X1 = (0,0,0,2,10,4)

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

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

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

ამიტომ მე-2 ხაზი ლიდერობს.

გამხსნელი ელემენტი უდრის (2) და მდებარეობს წამყვანი სვეტისა და წინა რიგის გადაკვეთაზე.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

ჩვენ ვქმნით სიმპლექსის ცხრილის შემდეგ ნაწილს. x 4 ცვლადის ნაცვლად, x 2 ცვლადი შევა გეგმა 1-ში.

1 გეგმაში x 2 ცვლადის შესაბამისი წრფე მიიღება გეგმის 0 სტრიქონის x 4 წრფის ყველა ელემენტის RE=2 ჩამრთველ ელემენტზე გაყოფით. განმსაზღვრელი ელემენტის ადგილას ვიღებთ 1. x 2 სვეტის დარჩენილ უჯრედებში ვწერთ ნულებს.

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

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 მ

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

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

გადამწყვეტი ელემენტი უდრის (1 1/2) და მდებარეობს წამყვანი სვეტისა და წამყვანი მწკრივის კვეთაზე.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 მ

ჩვენ ვქმნით სიმპლექსის ცხრილის შემდეგ ნაწილს. x 6 ცვლადის ნაცვლად, ცვლადი x 1 ჩართული იქნება გეგმა 2-ში.

ჩვენ ვიღებთ ახალ სიმპლექს ცხრილს:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

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

სიმპლექსის ცხრილის საბოლოო ვერსია:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

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

ოპტიმალური გეგმა შეიძლება დაიწეროს შემდეგნაირად: x 1 \u003d 2, x 2 \u003d 2:.

უპასუხე:
,
.

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

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

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

მოდით შევამოწმოთ პრობლემის გადაჭრის აუცილებელი და საკმარისი პირობა:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

ბალანსის პირობა დაცულია. მარაგებს თანაბარ საჭიროებებს. ამიტომ ტრანსპორტის პრობლემის მოდელი დახურულია.

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

საჭიროებებს

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

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

სასურველი ელემენტია 4. ამ ელემენტისთვის მარაგები არის 300, საჭიროებები 250. ვინაიდან მინიმალური არის 250, გამოვაკლებთ მას: .

			300 - 250 = 50
250 - 250 = 0

სასურველი ელემენტია 2. ამ ელემენტისთვის მარაგები არის 50, საჭიროებები 400. ვინაიდან მინიმალური არის 50, გამოვაკლებთ მას: .

			50 - 50 = 0
	400 - 50 = 350

სასურველი ელემენტია 5. ამ ელემენტისთვის მარაგები არის 300, საჭიროებები 350. ვინაიდან მინიმალური არის 300, გამოვაკლებთ მას:

			300 - 300 = 0
	350 - 300 = 50

სასურველი ელემენტია 3. ამ ელემენტისთვის მარაგები არის 200, საჭიროებები 50. ვინაიდან მინიმალური არის 50, გამოვაკლებთ მას:

			200 - 50 = 150
	50 - 50 = 0

სასურველი ელემენტია 6. ამ ელემენტისთვის მარაგები არის 150, საჭიროებები 150. ვინაიდან მინიმალური არის 150, გამოვაკლებთ მას:

			150 - 150 = 0
		150 - 150 = 0

საჭიროებებს

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

F= 2x 1 + 3x 2 ® მაქს

შეზღუდვებით

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

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

განვიხილოთ პირველი უტოლობა.

ავაშენოთ სასაზღვრო ხაზი ორი წერტილიდან. აღნიშნეთ ხაზი (L1) (ან რიგით1). კოორდინატები X 2 ჩვენ ვითვლით ფორმულების მიხედვით:

ასაშენებლად აირჩიეთ სკატერის ნაკვეთი

სწორი ხაზისთვის მონაცემების შერჩევა

შეცვალეთ ხაზის სახელი:

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

სწორი ხაზი (L1) სქემაზე:

მკაცრი უტოლობის გამოსავალი შეიძლება მოიძებნოს ერთი ტესტის წერტილის გამოყენებით, რომელიც არ ეკუთვნის წრფეს (L1). მაგალითად, (0; 0)W(L1) წერტილის გამოყენებით.

0+3×0< 18 или 0 < 18 .

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

შემდეგ ვხსნით უტოლობას (2).

ავაშენოთ სასაზღვრო ხაზი 2 ორი წერტილიდან. აღნიშნეთ ხაზი (L2).

სწორი ხაზი (L2) სქემაზე:

მკაცრი უტოლობა 2-ის ამოხსნა შეიძლება მოიძებნოს ერთადერთი სატესტო წერტილის გამოყენებით, რომელიც არ ეკუთვნის წრფეს (L2). მაგალითად, (0; 0)W(L2) წერტილის გამოყენებით.

წერტილის (0; 0) კოორდინატების ჩანაცვლებით ვიღებთ უტოლობას

2×0 + 0< 16 или 0 < 16 .

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

შემდეგ ვხსნით უტოლობას (3).

ავაშენოთ სასაზღვრო ხაზი ორი წერტილიდან. აღნიშნეთ ხაზი (L3).

სწორი ხაზი (L3) სქემაზე:

მკაცრი უტოლობა 2-ის ამოხსნა შეიძლება მოიძებნოს ერთადერთი სატესტო წერტილის გამოყენებით, რომელიც არ ეკუთვნის წრფეს (L3). მაგალითად, (0; 0)W(L3) წერტილის გამოყენებით.

წერტილის (0; 0) კოორდინატების ჩანაცვლებით ვიღებთ უტოლობას

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

შემდეგ ვხსნით უტოლობას (4).

ავაშენოთ სასაზღვრო ხაზი ორი წერტილიდან. აღნიშნეთ ხაზი (L4).

დაამატეთ მონაცემები Excel ფურცელზე

სწორი ხაზი (L4) სქემაზე:

მკაცრი უტოლობის ამოხსნა 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

წერტილის (0; 0) კოორდინატების ჩანაცვლებით ვიღებთ უტოლობას

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

ორი უტოლობის ამოხსნით (5) და (6)

არის 1 მეოთხედი, რომელიც შემოიფარგლება კოორდინატთა ხაზებით და .

უტოლობების სისტემა მოგვარებულია. ამ მაგალითში (1) - (6) უტოლობათა სისტემის ამონახსნი არის ამოზნექილი მრავალკუთხედი ფიგურის ქვედა მარცხენა კუთხეში, შემოსაზღვრული ხაზებით L1, L2, L3, L4 და კოორდინატთა ხაზებით და . თქვენ შეგიძლიათ დარწმუნდეთ, რომ მრავალკუთხედი სწორად არის არჩეული სატესტო წერტილის ჩანაცვლებით, მაგალითად (1; 1) თავდაპირველი სისტემის თითოეულ უტოლობაში. (1; 1) წერტილის ჩანაცვლებით მივიღებთ, რომ ყველა უტოლობა, ბუნებრივი შეზღუდვების ჩათვლით, ჭეშმარიტია.

ახლა განვიხილოთ ობიექტური ფუნქცია

F= 2x 1 + 3x 2 .

მოდით ავაშენოთ დონის ხაზები ფუნქციის მნიშვნელობებისთვის F=0და F=12(რიცხობრივი მნიშვნელობები არჩეულია თვითნებურად). დაამატეთ მონაცემები Excel ფურცელზე

დონის ხაზები სქემაზე:

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

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

მაგალითები

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

განტოლებათა ნებისმიერი სისტემის ამოხსნის პრობლემა

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\ დასაწყისი(მატრიცა)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\ბოლო(მატრიცა) )\ მართალია.)

შეიძლება ჩამოყალიბდეს როგორც ობიექტური ფუნქციის მინიმიზაციის პრობლემა

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots,x_(M))\qquad(1))

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

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

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

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

კომბინაციური ოპტიმიზაცია

კომბინატორიული მიზნობრივი ფუნქციის ტიპიური მაგალითია მოგზაური გამყიდველის პრობლემის ობიექტური ფუნქცია. ეს ფუნქცია უდრის გრაფიკზე ჰამილტონის ციკლის ხანგრძლივობას. იგი მოცემულია გრაფიკის წვეროების n − 1 (\displaystyle n-1) პერმუტაციის სიმრავლეზე და განისაზღვრება გრაფიკის კიდეების სიგრძის მატრიცით. ასეთი პრობლემების ზუსტი გადაწყვეტა ხშირად მოდის ვარიანტების ჩამოთვლაზე.

თავი 1. ხაზოვანი პროგრამირების ძირითადი ამოცანის გამოთქმა

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

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

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

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

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

ნარევების პრობლემა (პროდუქტების შემადგენლობის დაგეგმვა);

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

სატრანსპორტო ამოცანები (საწარმოს ადგილმდებარეობის ანალიზი, საქონლის გადაადგილება).

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

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

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

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

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

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

ზოგადად, მოდელი იწერება შემდეგნაირად:

ობიექტური ფუნქცია

(1.1) შეზღუდვების მიხედვით

(1.2) არაუარყოფითი მოთხოვნები

(1.3) სადაც x ჯ– ცვლადები (უცნობი);

- ხაზოვანი პროგრამირების ამოცანის კოეფიციენტები.

პრობლემა არის ფუნქციის (1.1) ოპტიმალური მნიშვნელობის პოვნა, რომელიც ექვემდებარება შეზღუდვებს (1.2) და (1.3).

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

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

1.2. წრფივი პროგრამირების ამოცანების გადაჭრის მარტივი მეთოდი

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

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

სტანდარტული სახით მოცემული LP ამოცანის დასაშვები ამოხსნა (დაშვებული გეგმა) არის რიცხვების მოწესრიგებული ნაკრები (x1, x2, ..., xn), რომელიც აკმაყოფილებს შეზღუდვებს; არის წერტილი n-განზომილებიან სივრცეში.

დასაშვები გადაწყვეტილებების ნაკრები ქმნის LP პრობლემის დასაშვები გადაწყვეტილებების (SDR) არეალს. ODR არის ამოზნექილი მრავალკუთხედი (პოლიგონი).

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

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

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

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

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

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

მისი გამოყენება შესაძლებელია ნებისმიერი წრფივი პროგრამირების პრობლემის გადასაჭრელად.

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

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

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

სიმპლექსის მეთოდის გამოყენების პროცესი მოიცავს მისი სამი ძირითადი ელემენტის განხორციელებას:

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

საუკეთესო (უფრო ზუსტად, არა უარეს) გადაწყვეტაზე გადასვლის წესი;

ნაპოვნი ამოხსნის ოპტიმალურობის შემოწმების კრიტერიუმი.

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

6.1 შესავალი

ოპტიმიზაცია. Ნაწილი 1

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

6.2 ოპტიმიზაციის თეორიის საფუძვლები

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

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

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

დიზაინის პარამეტრები

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

X1, x2, x3,...,xn.

ობიექტური ფუნქცია

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

M=M(x 1, x 2,...,x n).

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

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

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

ნახ. 1. ერთგანზომილებიანი ობიექტური ფუნქცია.

ნახ.6.2.ორგანზომილებიანი ობიექტური ფუნქცია.

დახურული მათემატიკური ფორმა, სხვა შემთხვევაში შეიძლება

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

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

მინიმალური და მაქსიმალურის პოვნა

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

დიზაინის სივრცე

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

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

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

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

დამაკმაყოფილებელი გადაწყვეტა. შეზღუდვები იყოფა ორ ჯგუფად: შეზღუდვები - თანასწორობები და შეზღუდვები - უტოლობები.

შეზღუდვები - თანასწორობა

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

C 1 (x 1 , x 2 ,..., x n) = 0,

C 2 (x 1 , x 2 ,..., x n) = 0,

..................

C j (x 1, x 2,...,x n)=0.

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

შეზღუდვები - უტოლობები

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

z 1 r 1 (x 1 , x 2 ,..., x n) Z 1

z 2 r 2 (x 1 , x 2 ,..., x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

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

ადგილობრივი ოპტიმალური

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

ნახ.6.4 თვითნებურ ობიექტურ ფუნქციას შეიძლება ჰქონდეს რამდენიმე

ადგილობრივი ოპტიმა.

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

გლობალური ოპტიმუმი

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

მაგალითი 6.1

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

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

დიზაინის პარამეტრები: x 1 , x 2 , x 3 .

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

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.

შეზღუდვა - თანასწორობა:

მოცულობა \u003d x 1 x 2 x 3 \u003d 1 მ3.

შეზღუდვა - უთანასწორობა:

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

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

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

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

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

AT ზოგადი ხედი LP პრობლემას აქვს შემდეგი ფორმა:

, (5.1)

, , (5.2)

, , (5.3)

სადაც , , მოცემულია მუდმივები.

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

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

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

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

,

, , (5.5)

.

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

,

.

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

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

კანონიკური LP ამოცანის ვექტორული ფორმა.