24. Розвязування дробово-лінійної оптимізаційної задачі зведенням до задачі лінійного програмування.

Розв’язуючи економічні задачі, часто як критерії оптимальнос­ті беруть рівень рентабельності, продуктивність праці тощо. Ці показники математично виражаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так: позначимо через прибуток від реалізації одиниці -го виду продукції, тоді загальний прибуток можна виразити формулою: ; якщо — витрати на виробницт­во одиниці -го виду продукції, то — загальні витрати на виробництво. У разі максимізації рівня рентабельності вироб­ництва цільова функція має вигляд:

за умов виконання обмежень щодо використання ресурсів: ;

.Позначимо і введемо заміну змінних . Тоді цільова функція матиме вигляд: .Отримали цільову функцію, що виражена лінійною залежністю.Оскільки , то звідси маємо: . Підставимо виражені через нові змінні значення в систему обмежень: Крім того, з початкової умови

.Умова стосовно невід’ємності змінних набуває виг­ляду:

Виконані перетворення приводять до такої моделі задачі:

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

Допустимо, що оптимальний розв’язок останньої задачі існує і позначається:

.Оптимальні значення початкової задачі визначають за формулою: .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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