Page 177 - 5637

3) перевірка допустимості даного рішення;

4) перевірка зміни (поліпшення) цільової функції при даному допустимому

рішенні.

Основне значення в роботі програми має реалізація процедури перебору

елементів довільної околиці Хеммінга з даними центром. Для цього використовується

процедура створення розбиття довільного позитивного цілого числа на довільне число

частин GENER, а також процедура всіх послідовних перестановок цих розбиття PERM.

Ці процедури є модифікованими варіантами відповідних процедур, розроблених на

мові Алгол [62].

Приклад. Цілоцисельна мінімізація функції ( , ) = + при наявності

обмеження + > 1.

Вихідні дані: Х0(1) = 4, Х0(2) = 2; N = 2, MAXR = 3, MAXN = 200.
Точне значення допустимого мінімуму X0(1) = X0(2) = 1, F0 = 2 отримано на
ЕОМ ЄС-1050 за 0,5 с.

8.4. Оптимізація дискретних параметрів методом напрямних околиць

Для наближеного рішення задачі цілочислового програмування (8.1) – (8.3) за

допомогою локальної оптимізації вихідної початкової точки призначений метод

напрямних околиць. В основу методу покладені ідеї методу можливих напрямків Г.

Зойтендейка [75], розробленого для вирішення завдань опуклого програмування.

Трансформація методу на дискретні системи досягається за допомогою введення

характеристик убування цільової функції в заданому напрямку і вибору з усіх

можливих відповідного напряму для оптимізації. У методі напрямних істотно

використовуються основні ідеї та поняття методу вектора спаду (див. §8.3).

Нехай безліч допустимих рішень ( ⊆ ) є перетином – деякого опуклого

підмножини ⊂ , а – опукла функція на . (Безліч називається опуклим, якщо

для будь-яких точок , ∈ і довільних чисел , > 0, таких, що + = 1,

= + ∈ . Функція ( ) ( ∈ ) називається опуклою, якщо для будь-яких

точок , ∈ і довільних чисел , > 0, таких, що + = 1, маємо

( ) ≤ ( ) + ( ).)