Задача 1
Вирішити графоаналітичним методом:
min j (X) = - 2 x 1 - x 2 + x 3 (1)
при
2 x 1 - x 2 + 6 x 3 £ 12 (2)
3 x 1 + 5 x 2 - 12 x 3 = 14 (3)
3 x 1 + 6 x 2 + 4 x 3 £ 18 (4)
X ³ 0 (5)
Рішення:
Етап 1. Побудова простору допустимих рішень
Вибираємо прямокутну систему координат: по горизонтальній осі вказуємо значення змінної х 1, по вертикальній - х 2.
Далі розглянемо умова невід'ємності змінних (5):
х 1 ³ 0; х 2 ³ 0 і х 3 ³ 0. (6)
Перші два обмеження показують, що простір допустимих рішень буде лежати в першому квадранті (тобто вище осі х 1 і правіше осі х 2).
З обмеження (3) можна отримати:
3 x 1 + 5 x 2 - 12 x 3 = 14 ® , (7)
з урахуванням умови неотрицательности третьої змінної (6) отримуємо нове обмеження:
. (8)
Підставляємо в обмеження (2) знайдене значення (7):
2 x 1 - x 2 + 6 x 3 £ 12 ® ®
® (9)
Підставляємо в обмеження (4) знайдене значення (7):
3 x 1 + 6 x 2 + 4 x 3 £ 18 ® ®
® (10)
Щоб врахувати отримані обмеження, простіше за все замінити нерівності на рівності, в результаті чого отримаємо рівняння прямих:
,
,
.
Тепер розглянемо, як графічно інтерпретуються нерівності. Кожне нерівність ділить площину (х1, х2) на два півпростору, які розташовуються по обидві сторони прямий, яка відповідає даному нерівності.
Точки площині, розташовані по один бік прямої, задовольняють нерівності (припустиме півпростір), а точки, що лежать по інший бік - ні.
На рис.1 допустимі півпростору показані стрілками.
Рис.1. Знаходження оптимального рішення
Обмеження:
(А)
(В)
(С)
х 2 ³ 0 (D)
х 1 ³ 0 (E)
Етап 2. Знаходження оптимального рішення
Точки простору допустимих рішень, показаного на мал.1, задовольняють одночасно всім обмеженням. Це простір обмежений відрізками прямих, які з'єднуються в кутових точках F, G, H, J і K.
Будь-яка точка, розташована всередині або на межі області, обмеженою ламаної FGHJK, є допустимим рішенням, т.к задовольняє всім обмеженням.
Простір допустимих рішень містить нескінченну кількість точок.
Знаходження оптимального рішення вимагає визначення напрямку убування цільової функції (1):
min j (X) = - 2 x 1 - x 2 + x 3.
Підставляємо в цільову функцію знайдене значення (7):
.
Ми прирівнюємо j (X) до кількох убутним значенням, наприклад, (- 5) та (- 8). Ці значення, підставлені замість j (X) у вираз цільової функції, породжують рівняння прямих; для значень (- 5) та (- 8) отримуємо рівняння прямих:
і
.
На рис.2 ці прямі показані штрих-пунктирними лініями, а напрям убування цільової функції - товстої стрілкою.
Цільова функція може спадати до тих пір, поки прямі, відповідні убутним значенням цієї функції, перетинають область допустимих рішень. Точка перетину області допустимих рішень і прямої, що відповідає мінімально можливого значення цільової функції, і буде точкою оптимуму.
З рис.2 видно, що оптимальне рішення відповідає точці Н. Ця точка є місцем перетину прямих (В) і (С), тому її координати х 1 і х 2 знаходяться як рішення системи рівнянь, які задають ці прямі:
Рішенням цієї системи буде:
х 1 = 5,36
х 2 = 0,16
при цьому значення цільової функції дорівнює:
.
Оптимальне рішення:
х 1 = 5,36
х 2 = 0,16
при цьому значення цільової функції дорівнює:
j (X) = - 10,621.
Рис.2. Знаходження оптимальної точки
Задача 2
Знайти екстремуми методом множників Лагранжа.
Рішення проілюструвати графічно.
extr j (X) = 3 x 1 2 + 2 x 1 + 2 x 2 2 + 4 x 2 x 3
при
x 1 + 2 x 2 = 19
x 1 + 2 x 3 = 11.
Рішення:
Позначимо:
g 1 (X) = x 1 + 2 x 2 - 19 = 0, g 2 (X) = x 1 + 2 x 3 - 11 = 0.
Функція Лагранжа має вигляд:
Звідси отримуємо необхідні умови екстремуму у вигляді системи рівнянь:
,
,
,
,
.
Вирішуємо систему рівнянь через визначники.
Головний визначник:
.
Матриця - стовпець лівої частини системи (вільних членів):
.
Знаходимо інші визначники:
,
,
,
,
.
Знаходимо рішення системи рівнянь:
,
,
,
,
.
Таким чином, отримали одну екстремальну крапку.
Визначаємо матрицю Гессе:
Матриця Гессе позитивно визначена, тому в знайденої точці
функція Лагранжа L (X, l) опукла і, отже, є мінімум.
Для графічної ілюстрації рішення висловимо координату х 3 з функції обмеження g 2 (X):
g 2 (X) = x 1 + 2 x 3 - 11 = 0 ® .
Підставимо отримане значення в цільову функцію:
j (X) = 3 x 1 2 + 2 x 1 + 2 x 2 2 + 4 x 2 x 3 = 3х 1 2 + 2х 1 +2 х 2 2 + 4х 2 (5,5 - 0,5 х 1) =
j (X) = 3х 1 2 + 2х 1 +2 х 2 2 + 22х 2 - 2х 1 х 2.
Отримали загальне рівняння кривої другого порядку.
Для отримання канонічного виду рівняння виробляємо поворот системи координат, звільняючись від члена, що містить твір координат.
Кут повороту j визначається формулою:
®
радіан.
При цьому отримуємо нові координати y і z:
,
.
Підставляємо отримані вирази в цільову функцію:
j (y, z) = 3х 1 2 + 2х 1 +2 х 2 2 + 22х 2 - 2х 1 х 2 =
,
,
,
Отримали рівняння еліпса з центром у точці (y = 1,3633; z = - 7,1513), причому лінії симетрії еліпса нахилені на кут j = - 0,55375 радіан відносно початкової системи координат х 1 х 2.
Перерахуємо координати центру еліпса:
,
.
На рис.3 представлено графічне рішення.
З малюнка видно, що графік рівняння обмеження g 1 (X) (суцільна лінія) перетинається з графіком цільової функції (пунктирна лінія) в точці А.
У точці А з координатами (5,2222; 6,8889) є мінімум цільової функції:
j (X) = 3х 1 2 + 2х 1 +2 х 2 2 + 22х 2 - 2х 1 х 2 = 3 * 5,22222 + 2 * 5,2222 + 2 * 6,88892 + 22 * 6,8889 - 2 * 5,2222 * 6,8889 = 266,78.
На рис.3 представлена також цільова функція з великим значенням:
j (X) = 350.
Центр еліпсів позначений точкою N (-2,6; -6,8).
Є одна точка екстремуму - точка мінімуму (5,2222; 6,8889), при цьому цільова функція дорівнює:
j (X) = 266,78.
Рис.3. Графічне рішення
Задача 3
Вирішити на основі умов Куна-Таккера.
Рішення проілюструвати графічно.
extr j (X) = (x 1 - 4) 2 + (x 2 - 3) 2
при
3 x 1 - 2 x 2 £ 18
x 1 + 2 x 2 £ 8
Рішення:
Позначимо:
g 1 (X) = 3 x 1 - 2 x 2 - 18 £ 0, g 2 (X) = - x 1 + 2 x 2 - 8 £ 0.
Записуємо функцію Лагранжа:
L (X, S, l) = j (X) - l 1 (g 1 (X) + S 1 2) - l 2 (g 2 (X) + S 2 2)
L (X, S, l) = (x 1 - 4) 2 + (x 2 - 3) 2 - l 1 (3x 1 - 2x 2 - 18 + S 1 2) - l 2 (- x 1 + 2x 2 - 8 + S 2 2)
Звідси отримуємо необхідні і достатні умови екстремуму (умови Куна-Таккера) у вигляді системи рівнянь:
,
,
,
,
,
.
Приймаються (з третього і четвертого рівнянь системи):
.
З першого і другого рівнянь системи знаходимо:
®
,
®
,
з п'ятого рівняння системи:
®
,
з шостого рівняння системи:
®
.
Таким чином, знайшли першу точку:
.
Приймаються (з третього і четвертого рівнянь системи):
.
З першого і другого рівнянь системи знаходимо:
®
,
®
,
підставляємо у п'яте рівняння системи:
®
®
.
визначаємо координати точки екстремуму:
,
,
з шостого рівняння системи:
®
.
Таким чином, знайшли другу точку:
.
Приймаються (з третього і четвертого рівнянь системи):
.
З шостого рівняння системи знаходимо:
®
.
Підставляємо отримане значення в перше і друге рівняння системи:
®
,
®
®
®
,
.
Підставляємо також отримані значення у п'яте рівняння системи:
®
.
Таким чином, знайшли третю точку:
.
У результаті рішення системи отримуємо вектори:
.
У точці
маємо глобальний мінімум цільової функції:
j (X) = (x 1 - 4) 2 + (x 2 - 3) 2 = (4 - 4) 2 + (3 - 3) 2 = 0.
У точці
маємо сідлової точку цільової функції:
j (X) = (x 1 - 4) 2 + (x 2 - 3) 2 = (6,7692 - 4) 2 + (1,1538 - 3) 2 = 11,077.
У точці
маємо сідлової точку цільової функції:
j (X) = (x 1 - 4) 2 + (x 2 - 3) 2 = (2,8 - 4) 2 + (5,4 - 3) 2 = 7,2.
Для графічної ілюстрації рішення будуємо графіки рівнянь обмежень:
g 1 (X) = 3 x 1 - 2 x 2 - 18 £ 0 ® ,
g 2 (X) = - x 1 + 2 x 2 - 8 £ 0 ®
суцільні лінії на рис.4 (графіки прямих).
Також будуємо графіки цільової функції для сідлових точок (що проходять через точки А і В)
j (X) = (x 1 - 4) 2 + (x 2 - 3) 2 = 11,077 ® ,
j (X) = (x 1 - 4) 2 + (x 2 - 3) 2 = 7,2 ® ,
і мінімуму (проходить через точку С) - центр окружності:
j (X) = (x 1 - 4) 2 + (x 2 - 3) 2 = 0 ®
пунктирні лінії на рис.4 (графіки кіл з центром у точці ).
З графіка також видно, що глобального максимуму цільової функції досягти неможливо!
Рис.4. Графічне рішення
Відповідь:
У точці С
маємо глобальний мінімум цільової функції:
j (X) = 0.
У точці В
маємо сідлової точку цільової функції:
j (X) = 11,077.
У точці А
маємо сідлової точку цільової функції:
j (X) = 7,2.
Глобального максимуму цільової функції досягти неможливо.
Задача 4
Отримати вираз розширеної цільової функції (РЦФ) і скласти блок-схему алгоритму чисельного розв'язання задачі методом штрафних функцій в поєднанні з одним із методів безумовної мінімізації.
Вирішити завдання засобами MS Excel.
Рішення проілюструвати графічно.
max j (X) = - 2 x 1 + 8 x 2 - x 1 2 - x 2 лютого (11)
при
x 1 + 2 x 2 £ 12
x 1 + x 2 ³ - 8
X ³ 0
Рішення:
Позначимо обмеження:
,
.
Розширена цільова функція утворюється сумою цільової функції і штрафний функції
:
.
Штрафну функцію можна побудувати різними способами. Однак, найбільш часто вона має вигляд:
Де
,
- Деякі константи, що представляють собою вагові коефіцієнти.
Використовуючи штрафну функцію, послідовно переходимо від однієї розрахункової точки в іншу до тих пір, поки не отримаємо прийнятне рішення. При цьому координати наступної точки знаходимо за формулою:
(12)
де - Крок обчислень.
Чим менше і
, Тим швидше знаходиться прийнятне рішення, проте точність визначення його знижується. Тому ітераційний процес зазвичай починають при порівняно малих значеннях
і
але, продовжуючи його, ці значення поступово збільшують.
Отже, процес знаходження рішення задачі включає наступні етапи:
1. Визначення вихідного допустимого рішення.
2. Вибір кроку обчислень.
3. Розташування за всім змінним приватних похідних від цільової функції і функцій, що визначають область допустимих рішень.
4. За вказаною раніше формулою (12) знаходження координати точки, що визначає можливе нове рішення.
5. Перевірка, чи задовольняють координати знайденої точки системі обмежень задачі. Якщо ні, то перехід до наступного етапу. Якщо координати знайденої точки визначають допустиме рішення, то дослідження необхідності переходу до подальшого допустимому рішенню. У разі такої потреби перехід до етапу 2, в іншому випадку знайдено прийнятне рішення завдання.
6. Установка значення вагових коефіцієнтів і перехід до кроку 4.
Побудуємо область допустимих рішень задачі (рис.5) і лінії рівня, що визначаються цільовою функцією (11):
j (X) = - 2 x 1 + 8 x 2 - x 1 2 - x 2 лютого
j (X) = - (x 1 2 + 2х 1 + 1) + 1 - (x 2 2 - 8х 2 + 16) + 16
j (X) = - (x 1 + 1) 2 + 1 - (x 2 - 4) 2 + 16
j (X) = - (x 1 + 1) 2 - (x 2 - 4) 2 + 17 (13)
Рис.5. Область допустимих рішень
Лініями рівня служать кола з центром у точці (- 1;
4). Точка дотику однієї з цих кіл з областю допустимих рішень і є шуканої точкою максимального значення цільової функції.
З виду цільової функції (11) можна зробити висновок:
чим далі точка від центру кола, тим все менше цільова функція, максимум цільової функції буде в точці дотику кола вертикальної осі координат (точка А на рис.5), при цьому: х 1 = 0; х 2 = 4
і цільова функція дорівнює:
j (X) = - (x 1 + 1) 2 - (x 2 - 4) 2 + 17 = - (0 + 1) 2 - (4 - 4) 2 + 17 = 16.
Для вирішення задачі методом штрафних функцій приймемо початкове значення допустимого рішення:
.
Вибираємо крок обчислень і точність обчислень:
і
.
Приймаються вагові коефіцієнти:
,
.
Знаходимо приватні похідні від цільової функції:
,
.
Визначаємо приватні похідні від функцій обмеження:
,
,
,
.
Далі обчислення виробляємо в середовищі MS Excel (див. файл KursR _ MMPR. Xls) за алгоритмом, наведеним на Рис.6.
Результат розрахунку в середовищі MS Excel представлено в таблиці 1.
Графічно рішення представлене на рис.5, де максимальне значення цільової функції досягається у точці А (0;
4) і дорівнює:
j (X) = 16.
Відповідь:
У точці
маємо глобальний максимум цільової функції:
j (X) = 16.
Таблиця 1. Результат розрахунку в середовищі MS Excel
№ ітерації | Поточне | Допустиме рішення? | | | | | | | | | Нове | Допустиме рішення? | Кінець розрахунку? | ||
| | | | ||||||||||||
1 | 3 | 2 | Так | 0 | 0 | -8 | 4 | -1 | -2 | -1 | 1 | 2,2 | 2,4 | Так | Ні |
2 | 2,2 | 2,4 | Так | 0 | 0 | -6,4 | 3,2 | -1 | -2 | -1 | 1 | 1,56 | 2,72 | Так | Ні |
3 | 1,56 | 2,72 | Так | 0 | 0 | -5,12 | 2,56 | -1 | -2 | -1 | 1 | 1,048 | 2,976 | Так | Ні |
4 | 1,048 | 2,976 | Так | 0 | 0 | -4,096 | 2,048 | -1 | -2 | -1 | 1 | 0,6384 | 3,1808 | Так | Ні |
5 | 0,6384 | 3,1808 | Так | 0 | 0 | -3,2768 | 1,6384 | -1 | -2 | -1 | 1 | 0,31072 | 3,34464 | Так | Ні |
6 | 0,31072 | 3,34464 | Так | 0 | 0 | -2,62144 | 1,31072 | -1 | -2 | -1 | 1 | 0,048576 | 3,475712 | Так | Ні |
7 | 0,048576 | 3,475712 | Так | 0 | 0 | -2,09715 | 1,048576 | -1 | -2 | -1 | 1 | 0 | 3,58057 | Так | Ні |
8 | 0 | 3,58057 | Так | 0 | 0 | -2 | 0,838861 | -1 | -2 | -1 | 1 | 0 | 3,664456 | Так | Ні |
9 | 0 | 3,664456 | Так | 0 | 0 | -2 | 0,671089 | -1 | -2 | -1 | 1 | 0 | 3,731565 | Так | Ні |
10 | 0 | 3,731565 | Так | 0 | 0 | -2 | 0,536871 | -1 | -2 | -1 | 1 | 0 | 3,785252 | Так | Ні |
11 | 0 | 3,785252 | Так | 0 | 0 | -2 | 0,429497 | -1 | -2 | -1 | 1 | 0 | 3,828201 | Так | Ні |
12 | 0 | 3,828201 | Так | 0 | 0 | -2 | 0,343597 | -1 | -2 | -1 | 1 | 0 | 3,862561 | Так | Ні |
13 | 0 | 3,862561 | Так | 0 | 0 | -2 | 0,274878 | -1 | -2 | -1 | 1 | 0 | 3,890049 | Так | Ні |
14 | 0 | 3,890049 | Так | 0 | 0 | -2 | 0,219902 | -1 | -2 | -1 | 1 | 0 | 3,912039 | Так | Ні |
15 | 0 | 3,912039 | Так | 0 | 0 | -2 | 0,175922 | -1 | -2 | -1 | 1 | 0 | 3,929631 | Так | Ні |
16 | 0 | 3,929631 | Так | 0 | 0 | -2 | 0,140737 | -1 | -2 | -1 | 1 | 0 | 3,943705 | Так | Ні |
17 | 0 | 3,943705 | Так | 0 | 0 | -2 | 0,11259 | -1 | -2 | -1 | 1 | 0 | 3,954964 | Так | Ні |
18 | 0 | 3,954964 | Так | 0 | 0 | -2 | 0,090072 | -1 | -2 | -1 | 1 | 0 | 3,963971 | Так | Так |
Література
1. Таха Х. Введення в дослідження операцій, 7-е видання: Пер з англ. - М.: Изд. дім "Вільямс", 2005.
2. Реклейтіс Г., Рейвіндран А., Регсдел К. Оптимізація у техніці / Пер. з англ. У 2-х кн. Кн.1 - М: Світ, 1986.; Кн.2 - М: Світ, 1986.
3. Акулич І.Л. Математичне програмування в прикладах і завданнях: Навчальний посібник. - М.: Вища школа, 1986.