25. Градієнтний метод. Ідея методу.

Градієнтні методи належать до наближених методів розв’язування задач нелінійного програмування і дають лише пев­не наближення до екстремуму, причому за збільшення обсягу обчислень можна досягти результату з наперед заданою точністю, але в цьому разі є можливість знаходити лише локальні екстремуми цільової функції. Зауважимо, що такі методи можуть бути застосовані лише до тих типів задач нелінійного програмування, де цільова функція і обмеження є диференційовними хоча б один раз. Зрозуміло, що градієнтні методи дають змогу знаходити точки глобального екстремуму тільки для задач опуклого програмування, де локальний і глобальний екстремуми збігаються.

В основі градієнтних методів лежить основна властивість градієнта диференційовної функції — визначати напрям найшвидшого зростання цієї функції. Ідея методу полягає у переході від однієї точки до іншої в напрямку градієнта з деяким наперед заданим кроком.

26. Описати алгоритм симплексного методу розв’язування задач лінійного програмування.

Загалом алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.

4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунками елементів нової симплексної таблиці.

5. Повторення дій, починаючи з п. 3.

Далі ітераційний процес повторюють, доки не буде визначено оптимальний план задачі.

27. Метод приведеного градієнта (метод Якобі). Введення залежних та незалежних змінних для компонент вектора Х = (х1, х2, …. Х4)

Метод Якобі — класичний ітераційний метод розв'язку системи лінійних рівнянь.

Для квадратної системи з n лінійних рівнянь: де: Матрицю A можна розкласти на два доданки: діагональну матрицю D, та все інше R:

Систему лінійних рівнянь можна переписати в вигляді: Ітераційний метод Якобі виражається формулою:

28. Базисні та вільні вектори. Базисні та вільні змінні.

Використовуючи симплекс метод, вектори, що утворюють одиничну матрицю коефіцієнтів з системи обмежень, називають базисними, всі інші вільними, якщо з поданих векторів одиничну матрицю утворити неможливо, їх вводять штучно з потрібними коефіцієнтами, коефіцієнти вводять в систему обмежень, такі вектори називають штучними.

Базисними змінними називаються змінні при базисних векторах, інші змінні є вільними.