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

3. Перевіряють чи виконується умова

. Якщо не виконується, то переходять до наступного кроку, якщо виконується , то .

4. Покладають, що

і переходять до кроку 2.

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

Запишемо штрафну функцію:

і розв’яжемо тепер задачу мінімізації для цієї функції.

За точність обчислень оберемо

, а крок , а початкову точку візьмемо таку ж як ми брали у методі Франка-Вулфа, тобто . Отже

;

.

Тобто

,

Точка

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

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

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

Точка

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

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

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

Точка

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

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

.

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

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

Точка

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

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

.

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

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

Точка

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

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

.

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

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

Точка

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

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

.

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

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

Точка

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

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

Отже в якості параметру

візьмемо . Тоді

Точка

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

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

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

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

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

а) графічно:

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

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

Для цього побудуємо вектор

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