Завдання 1 (16.88)
Мінімізувати функцію f (x) на всій числовій осі методом Ньютона. Критерієм досягнення необхідної точності вважати виконання нерівності .
Рішення:
Знайдемо першу і другу похідні вихідної функції:
Виберемо початкове наближення . І здійснимо обчислення за формулою
Результати запишемо в таблиці
n
0
0
2
1
1
-0,2
1,91
-0,1649
2
-0,175697
1,908525
-0,0032
3
-0,17520305
1,908524
-0,0000013
n = 1
n = 2
n = 3
n = 4
Далі ми закінчуємо обчислення, тому що дана точність досягнута. У результаті ми отримуємо:
і
.
Здійснимо перевірку за допомогою вбудованої функції Minimize:
,
Відповідь:
і
Задача 2 (16.115)
Виписати матрицю Q квадратичної функції f (x), знайти її градієнт в точці
і переконатися в опуклості f (x) у
.
,
Рішення:
Запишемо вихідну функцію в наступному вигляді:
,
де
Тоді матриця Q прийме вигляд:
Знайдемо градієнт в точці
за формулою
, Де r - вектор-стовпець і дорівнює
:
Підставляючи в отриману матрицю , Ми отримуємо таке значення градієнта в даній точці:
Тепер переконаємося в опуклості f (x) у . Для того, щоб вихідна функція була опуклою в
, Достатньо, щоб матриця Q була позитивно визначена. Для цього знайдемо кутові мінори
матриці Q і якщо вони будуть більше нуля, то функція f (x) буде опуклою в
.
,
Так як ,
, То функція f (x) опукла в
.
Перевірка в Mathcad:
Перевірка на опуклість і знаходження градієнта в точці x 0
Відповідь: градієнт дорівнює і функція f (x) буде опуклою в
.
Завдання 3 (16.136)
Мінімізувати квадратичну функцію методом найшвидшого спуску, закінчуючи обчислення при ,
.
Рішення:
Тоді похідні вихідної функції будуть мати вигляд:
Виберемо початкове наближення . Тоді
Для знаходження точки мінімуму функції знайдемо нулі її похідної:
Знаючи , Ми визначимо
наступним чином:
І так далі по вище описаній ланцюжку.
Реалізуємо рішення даної задачі в математичному пакеті Mathcad.
Функція має вигляд:
Тоді коефіцієнти будуть рівні
Візьмемо такі початкове наближення і
:
Далі пишемо програму
У результаті отримуємо шукане рішення і функцію
:
Відповідь:
і
Завдання 4 (16.155)
Мінімізувати функцію f (x) методом спряжених напрямків, закінчуючи обчислення при ,
.
Рішення:
Тоді приватні похідні вихідної функції будуть мати вигляд:
Рішення будемо шукати за наступним алгоритмом:
Крок 1.
Вибравши початкове наближення
,
Для знаходження точки мінімуму функції використовуємо метод перебору:
=>> , Звідки
Крок 2.
Для знаходження точки мінімуму функції використовуємо метод перебору:
=>> ,
звідки
Крок 3.
Для знаходження точки мінімуму функції використовуємо метод перебору:
=>> , Звідки
Крок 4.
отже необхідна точність досягнута і
Відповідь:
Завдання 5 (16.193)
Вирішити задачу лінійного програмування графічним методом.
Рішення:
Зобразимо на площині наш багатокутник ABCDE (червоного кольору) і одну з ліній рівня
(Рожевого кольору).
Лінії AB відповідає рівняння , BC відповідає
, CD відповідає
, DE відповідає
і EA відповідає
Напрямок спадання функції вказує вектор
. Здійснюючи паралельний перенесення лінії рівня вздовж напрямку
, Знаходимо її крайнє положення. У цьому положенні пряма
проходить через вершину
багатокутника ABCDE. Тому цільова функція
приймає мінімальне значення
в точці
, Причому
Відповідь: і
Завдання 6 (16.205)
Вирішити задачу лінійного програмування в канонічному вигляді графічним методом.
Рішення:
Матриця системи буде мати наступний вигляд:
Ранг цієї матриці дорівнює . Тоді число вільних змінних дорівнює
, Тому для вирішення завдання можна використовувати графічний метод. Вирішивши систему обмежень - рівностей щодо базисних змінних
,
, Отримаємо:
Виключаючи за допомогою отриманої системи змінні ,
з виразу для цільової функції, одержуємо:
З урахуванням умови неотрицательности ,
, І останніх рівностей отримуємо таку задачу:
Зобразимо на площині наш багатокутник ABCDEJ (червоного кольору) і одну з ліній рівня
(Рожевого кольору).
Лінії AB відповідає рівняння , BC відповідає
, CD відповідає
, DE відповідає
, EJ відповідає
і JA відповідає
.
Напрямок спадання функції вказує вектор
. Здійснюючи паралельний перенесення лінії рівня вздовж напрямку
, Ми бачимо, що цільова функція містить бік AB багатокутника ABCDEJ. Таким чином, всі крапки відрізка AB є точками мінімуму функції
. Так як кінці A і B мають координати
і
відповідно, то знайдемо звідси координати
і
:
Тоді будь-яка точка мінімуму бути подана в вигляді
де . Мінімальне значення цільової функції
Відповідь: нескінченна безліч рішень
, Де
і
.
Задача 7 (16.216)
Вирішити задачу лінійного програмування симплекс - методом, знаходячи початкову кутову точку методом штучного базису.
Рішення:
Матриця системи має вигляд
.
Її ранг дорівнює 3. Введемо додаткові змінні і запишемо умову допоміжної задачі лінійного програмування для розглянутого випадку:
Вважаючи додаткові змінні базисними, запишемо симплекс таблицю цього завдання, відповідну кутовий точці
:
3
-2
3
2
9
1
2
-1
1
0
-1
-1
2
1
6
-3
1
-4
-4
-15
Зробимо перетворення вихідної симплекс-таблиці симплекс-методом наступним чином:
дивимося на нижній рядок - вибираємо той стовпець, в якому нижній елемент негативний, якщо таких стовпців кілька, то вибираємо будь-який (у нашому випадку вибираємо перший стовпець
);
далі дивимося на останній і вибраний стовпці - порівнюємо відносини елементів останнього і вибраного стовпців (у вибраному стовпці беремо тільки позитивні числа), і вибираємо той елемент вибраного стовпця, де ставлення елементів буде найменшим (в нашому випадку 9 / 3 і 0 / 1, так як друге ставлення найменше, отже, опорним елементом буде 1);
міняємо місцями змінні
, Інші змінні залишаємо на своїх місцях;
на місце опорного елемента ставимо ставлення 1 / (опорний елемент);
на решті місць роздільної рядка записуємо відповідні елементи вихідної таблиці, поділені на опорний елемент;
на вільні місця дозволяє стовпця ставимо зі знаком мінус відповідні елементи вихідної таблиці, поділені на опорний елемент;
залишилися вільні місця в новій симплекс-таблиці заповнюємо порядково наступним чином: з рядка елементів вихідної таблиці віднімаємо твір її елемента з дозволяючого стовпця на вже заповнену роздільну рядок нової таблиці.
Виробляючи перетворення симплекс-методу, отримаємо таку послідовність симплекс-таблиць:
- 3
- 8
6
-1
9
1
2
-1
1
0
1
1
1
2
6
3