Page 171 - 5637

Основні етапи роботи:

1) присвоєння відсутніх початкових значень елементів матриці ;

2) перевірка умови невід'ємності всіх, крім самого верхнього, елементів

останнього стовпця матриці ; в разі позитивної відповіді поточні значення вектора

та функції оголошуються оптимальними;

3) перевірка наявності в матриці рядки, в якій всі елементи, крім, можливо,

останнього, невід'ємні, що означає відсутність рішення задачі;

4) організація перерізів за методом Гоморі;

5) формування вихідних параметрів програми.

Приклад. Рішення двох задач мінімізації функцій:

1) = + при наявності обмежень − − ≤ −1, 2 − ≤ 1;

2) = 14 + 25 при наявності обмежень 3 − 5 ≤ −11, 7 + 2 ≤ −13.

Для отримання вірного рішення першого завдання = 1, = 0, = 1 знадобилося

0,3 с, другого завдання = 142, = 3, = 4 – 0,35 с на ЕОМ ЄС-1050.

8.3. Оптимізація дискретних параметрів методом вектора спаду
Для вирішення різноманітних завдань цілочисельного програмування (лінійного,
комбінаторного, булевого), а також частково цілочисельного широко застосовується
метод вектора спаду [69]. Метод вектора спаду є метод локальної оптимізації функції

, заданої на цілочисельної решітці . В основу методу покладено принцип перебору
елементів відповідним чином певної околиці даного початкового рішення, щоб

виявити найкраще, яке, в свою чергу, стає центром нової околиці локальної

оптимізації. Весь процес багаторазово повторюється до тих пір, поки стане

неможливим поліпшити рішення. Природно, що для використання цього підходу

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

цього методу є його здатність ефективно вирішувати задачі цілочислового

програмування (8.1) – (8.3) з нелінійними функціями .

Нехай – метричний простір, тобто на безлічі задана метрика (функція
відстані) ( , ) наприклад