Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

;

.

Тобто ,

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі:

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

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі:

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

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розв’язку.

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розв’язку.

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розв’язку.

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розв’язку.

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

З другого обмеження задачі маємо:

Отже в якості параметру візьмемо . Тоді

Точка належить допустимій множині задачі. Обчислимо значення штрафної функції в цій точці: .

І так далі продовжується процес пошуку нового наближення до розв’язку задачі.

Як бачимо, метод штрафних функцій сходиться значно повільніше, ніж метод Франка-Вулфа. Це може бути пов’язано з тим, що початкове наближення знаходиться далеко від мінімуму функції, або ж необхідно обрати більший крок.

5. Розв’язання задачі цілочислового програмування

Розв’яжемо задачу цілочислового програмування

а) графічно:

Оскільки число невідомих задачі дорівнює двом, рішення можна знайти, використовуючи геометричну інтерпретацію заадчі. Для цього, насамперед, побудуємо багатокутник рішення задачі, що складає у визначенні максимальне значення лінійної функції (1) при виконанні умов (2) і (3) (мал. 1). Координати всіх точок побудованого багатокутника рішення ОАВС задовольняють систему лінійних нерівностей 2-3. Разом з тим умові (4), тобто умові цілочисельності змінних, задовольняють координати лише 20 точок, відзначених на мал. 1.

Щоб знайти точку, координати якої визначають рішення вихідної задачі, замінимо багатокутник ОАВС багатокутником, що містить усі припустимі точки з цілочисловими координатами і таким, що координати кожної з вершин є цілими числами. Виходить, якщо знайти точку максимуму функції (1) на отриманому багатокутнику, то координати цієї точки і визначать оптимальний план задачі.

Для цього побудуємо вектор =(4; 1) – градієнт цільової функції і перпендикуляр до неї – лінію рівня цільової функції, тобто лінію, в точках якої цільова функція приймає одне й те ж значення. Побудовану пряму пересуваємо в напрямку вектора доти, поки вона не пройде через останню загальну точку її з даним багатокутником. Координати цієї точки і визначають оптимальний план, а значення цільової функції в ній є максимальним.

У даному випадку шуканою є точка Е(2;3), у якій цільова функція приймає максимальне значення . Отже, координати точки Е визначають оптимальний план задачі 1 — 4.

б) методом Гоморі:

Для рішення задачі цілочислового програмування методом Гоморі спочатку визначимо симплекс-методом оптимальний план задачі 1 —3 без умови цілочисельностісті змінних:

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

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

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

в ) методом Ленг і Дойг

Як і у випадку знаходження розв’язку задачі цілочислового програмування за допомогою методу Гоморі, спочатку визначаємо симплекс-методом оптимальний план задачі (1) —(3) без умови цілочисельності змінних. З попереднього пункту маємо оптимальне для задачі лінійного програмування (1-3): , при цьому .

Оскільки оптимальне рішення задачі лінійного програмування 1-3 не задовольняє умові цілочисельності, метод Ленг і Дойг заміняє простір рішень задачі лінійного програмування так, що в кінцевому результаті отримуємо рішення задачі цілочислового лінійного програмування. Для цього спочатку обираємо змінну, значення якої не є цілочисловим, тобто . Область простору допустимих рішень задачі лінійного програмування не містить цілочислових значень змінної , тому вона може бути виключена із розгляду, як безперспективна. Це еквівалентно заміні вихідної задачі лінійного програмування 1-3 двома новими задачами лінійного програмування, котрі визначаються наступним чином:

а) задача 1:

б) задача 2:

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

Спочатку розв’яжемо задачу 1. Для цього спочатку з останньої симплекс-таблиці задачі 1-3 змінну виразимо через небазисні невідомі:

Тепер нове додаткове обмеження запишемо в канонічній формі і допишемо його до останньої симплекс-таблиці задачі 1-3:

Отже за допомогою двоїстого симплекс-методу можемо розв’язати задачу 1:

Оптимальним розв’язком задачі 1 буде , а максимальне значення цільової функції відповідно - . Оптимальне рішення задачі 1 задовольняє умову 5, тобто умову цілочисленості.

В цій ситуації ми не можемо оцінити якість рішення, отриманого при розгляді задачі 1, оскільки розв’язок задачі 2 може привести до кращого цілочисельного розв’язку(з більшим значенням цільової функції). Поки що ми можемо лише сказати, що значення