6.3. Метод повного перебору (метод сіток)

Ідея метода полягає в тому, що допустиму область задачі нелінійного програмування розбивають площинами ( - номер змінної, k_i - номер площини, h_i - крок), перпендикулярними висям координат, на ряд підобластей. На перетині цих площин в області допустимих значень отримуємо точки В кожній з них обчислюємо значення цільової функції f(X) і отримуємо множину значень . З цієї множини значень вибираємо максимальне значення, якщо задача розв’язується на максимум цільової функції або мінімальне значення, якщо задача розв’язується на мінімум. Точка M_r, яка відповідає екстремальному значенню функції f(X) і вважається розв’язком задачі. Слід відмітити, що чим менше крок h_i, тим більше треба будувати площин і обчислювати точок M_s і тим точніше розв’язується задача. Але, чим більше точок M_s, тим більше обчислень треба провести, а чим більше змінних, тим більше точок M_s. Тому такий метод найчастіше використовується для задач з двома змінними.

Приклад. Знайти максимум функції

при обмеженнях

Розв’язання. У даному прикладі x₁₀=0, x₂₀=1. Оберемо крок h₁=0,4 та h₂=0,2. Відрізок [0, 2] для змінної розбиваємо на 6 частин:

.

Відрізок [1, 2] змінної x₂ поділимо теж на 6 частин:

.

Для кожної пари значень отримуємо точку. Оскільки k₁ і k₂ приймають 6 значень, то кількість всіх точок складає 36.

Визначимо максимальне значення функції f(X)=6 при x₁=2,0 і x₂=1,0, що і є рішенням задачі.

6.4. Алгоритм дихотомічного пошуку

Початковий етап.

Необхідно вибрати константу 2  0 і кінцеву допустиму довжину інтервалу невизначеності l0. Визначити а, в і к=1 та перейти до основного етапу.

Основний етап.

Шаг 1. Якщо в_к  а_к  l, то кінець розрахунків; точка мінімуму належить інтервалу а, в. В іншому випадку треба розрахувати

х₁= х₂=

і перейти до шагу 2.

Шаг 2. Якщо f(x₁)  f(x₂), то необхідно прийняти а_к+1 = а_к і в_к+1 = х₂. В іншому випадку треба прийняти а_к+1 = х₁ і в_к+1 = в_к. Замінити к на к+1 і перейти до шагу 1.

Довжина інтервалу невизначеності в початку (к+1)-ої ітерації дорівнює

(в_к+1 - а_к+1) = (в₁ – а₁) + 2(1 - ).

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

7. Рекомендована література

7.1. Основна

1. Українець А.І., Гуржій А.М., Самсонов В.В., Кривець Т.О., Городенська В.Я. Задачі лінійного та нелінійного програмування програмування. Навч. Посібник.- К.:НУХТ, 2007. – 156 с.

2. Бейко И.В., Бублик Б.Н., Зінько П.Н. Методы и алгоритмы решения задач оптимизации.- К.: Вища школа. Головное изд-во. 1983. –512с.

3. Ляшенко И.Н., Карагодова Е.А., Чернишова Н.В., Шор Н.З. Линейное и нелинейное программирование. .- К.: Вища школа. Головное изд-во. 1975. –372с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. –М.: Высш. Шк., 1986. –319 с.

5. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. –М.: Физматгиз, 1963. –776с.

6. Вагнер Г. Основы исследования операций, 3т.: Пер. с анг.. –М.: Мир, 1973.

7. Базара М., Шести К. Нелинейное программирование. Теория и алгоритмы: Пер. с анг.. –М.: Мир, 1982. –583с.

8. Бєліков М.І., Гуржій А.М., Кігель В.Р., Самсонов В.В. Розв’язування оптимізаційних задач за допомогою методів лінійного програмування. –К.: УДУХТ, 1994. –132с.

9. Самсонов В.В., Гуржій А.М. Задачі оптимізації в практичної діяльності фахівця. –К.: УДУХТ, 1997. –176.

10. Задачі лінійного та нелінійного програмування: Навч. Посібник / А.І.Українець, А.М. Гуржий, В.В.Самсонов та ін. – К.: НУХТ, 2007. – 156 с.