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

Позначимо

і введемо заміну змінних . Тоді цільова функція матиме вигляд:

.

Отримали цільову функцію, що виражена лінійною залежністю.

Оскільки , то звідси маємо: . Підставимо виражені через нові змінні значення в систему обмежень (7.2):

Крім того, з початкової умови

.

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

.

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

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

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

.

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

32. Як отримати приведений градієнт?

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

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

Розглянемо метод Франка — Вульфа, процедура якого передбачає визначення оптимального плану задачі шляхом перебору розв’язків, які є допустимими планами задачі.

Нехай необхідно відшукати

за лінійних обмежень:

;

Допустимо, що Х0 — початкова точка, що належить множині допустимих планів даної задачі. В деякому околі цієї точки нелінійну цільову функцію замінюють лінійною і потім розв’язують задачу лінійного програмування. Нехай розв’язок лінійної задачі дав значення цільової функції F0, тоді з точки Х0 в напрямку F0 необхідно рухатись доти, поки не припиниться зростання цільової функції

Розглянемо детальніше перехід від k-ої ітерації методу до (k + 1)-ої ітерації.

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

.

Значення градієнта функції задає в даній точці напрям най­швидшого її зростання.

Замінюємо цільову функцію задачі лінійною функцією виду:

.

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

за умов:

;

.

Нехай розв’язком такої задачі є точка .

З початкової точки в напрямку рухаємося з деяким довільним кроком , визначаючи координати нової точки у такий спосіб:

Для точки Хk+1 повторюємо розглянутий процес, для чого знову розраховуємо значення градієнта і т. д.

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

33. Симплексний метод. Умова оптимальності задач лінійного програування.

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. 1949 року такий метод був запропонований американським вченим Дж. Данцігом — так званий симплексний метод, або симплекс-метод.

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

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

Отже, симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування.

Умова оптимальності плану задачі на відшукання мінімального значення функціонала: якщо для деякого плану розклад всіх векторів у даному базисі задовольняє умову

то план Х0 є оптимальним розв’язком задачі лінійного програмування.

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