Громова Н.М.

Одеський національний політехнічний університет

ПРО ЕФЕКТИВНІСТЬ ЗАСТОСУВАННЯ АЛГОРИТМІВ

Громова Н.М. Про ефективність застосування алгоритмів. Розглянуті три алгоритми методу гілок та мереж. Запропоновані алгоритми дослідженні на задачах з різними типами матриць умов. Наведені результати експерименту.

Gromova N.N. About the efficiency of algorithms. We consider three algorithms for branches and bounds. The proposed algorithms to study problems with different types of matrix conditions. The results of the experiment are described.

У розв’язанні задач цілочисельного лінійного програмування (ЦЛП) останнім часом широко використовується схема гілок і меж, різні прийоми послідовного відсіювання варіантів у процесі конструювання рішення

Ідея методу гілок та мереж полягає в наступному: вирішуючи дискретну екстремальну задачу, множина всіх можливих варіантів розбивається на класи, потім будуються оцінки для них. У результаті стає можливим відкидати розв’язання цілими класами, якщо їх оцінка гірше деякого рекордного значення [1].

Алгоритмізація методу полягає у визначенні оцінки та способу галуження, стратегії вибору початкової вершини і подальшого вибору вершин з дерева розв’язань. Оцінювання можно проводити шляхом розв’язання відповідної задачі лінійного програмування або через многомірну задачу про ранець. Галуження, як послідовна побудова розв’язання, можливо виконувати за допомогою конкретизації змінної згідно з номером j=j+1, або виборочно згідно з визначеним правилом [2].

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

Прискорений алгоритм з конкретизацією змінної

Розглядається задача цілочисельного лінійного програмування (ЦЛП) у постановці

Z = max (1)

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

; (2)

x_j{0;1} ; (3)

де всі складові задачі ЦЛП a_ij, bj, с_j, - невід'ємні числа.

Така задача є об'єктом для побудови алгоритму методу.

Введемо деякі позначення:

вектор (k<n) називається частковим розв'язанням довжини k, якщо компонентам () присвоєно конкретні цілочисельні значення та їх сукупність задовольняє умовам обмежень. Перехід від часткового розв'язання до здійснюється шляхом введення S_k+1 компоненти з певним значенням так, щоб залишилася частковим розв'язанням. Визначення значення компоненти називається конкретизацією. Перехід від до називається компонуванням розв'язання. Формально    

,

де — конкретизована змінна

Змінні, що конкретизуються, в послідовній побудові розв'язання при переході від часткового розв'язання до вибираються відповідно до наступного правила.

Нехай множина містить індекси конкретизованих компонент на s-кроці компонування, тоді      

.

Компонента, яка повинна бути конкретизованою на s+1 кроці, вибирається з безлічі "добрих" компонент . Множина містить лише ті індекси j, з якими компоненти x_j, можуть прийняти значення, відмінні від нуля, тобто
для всіх

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

, (4).

Конкретизації підлягає компонента з індексом j₀, якщо

.

Згідно з запровадженими визначеннями і позначеннями, запропонована ідея реалізується алгоритмом [3]:

- визначається порядок присвоєння значень, щр дорівнюють одиниці змінним x_j при визначенні значень Z_i, i= і знаходження оцінок підмножин варіантів, що розглядаються:

k=0; s=1; ; , i=;

- визначається компонента, що підлягає конкретизації (j₀);

- формується часткове рішення довжини k +1:

- вибирається підмножина G_q (), що має максимальну оцінку;

- k = k +1; якщо k≤n - перехід до визначення компоненти, що підлягає конкретизації, інакше - до наступного пункту;

- перевірка на оптимальність варіантів розв’язання; якщо знайдено оптимальне розв’язання - робота алгоритму завершена, інакше - перехід до наступного пункту;

- відповідно до заданої функції переваги (4) визначається підмножина варіантів G(), що підлягають подальшому перегляду за схемою методу гілок і мереж.

Послідовний алгоритм

Як и для прискореного алгоритму з конкретізацією зміної, об’єктом для побудови алгоритму метода є задача ЦЛП в постановці (1)...(3). Алгоритм послідовної побудови розв’язання приведен нижче.

1 крок . Обчислюємо оцінку при х_j=0 и х_j=1 (х_j=). Переходимо на крок 2.

2 крок. Галуження продовжуємо по тій гілці, значення оцінки якої більше. Переходимо на крок 3.

3 крок. Якщо всі змінні перебрано и оцінки всіх відкинутих гілок менше отриманого розв’язання, то варіант оптимальний; якщо ні - вертаємося до найближчої відкинутої гілки, оцінка якої неменше отриманого результату та виконуємо крок 1.

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

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

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

Результати наведені у таблицях.

Таблиця 1

Задачі розмірності 5х9

Тип задачі	Алгоритм
	Послідовний		Модифікація послід-ого		Прискорений
	Час	Ефект-сть	Час	Ефект-сть	Час	Ефект-сть
Повна	100	100	63	99	20	96
Розряджена (0,4)	100	100	59	100	45	78
Розряджена блочної структури	100	100	63	100	40	70

Таблиця 2

Задачі розмірності 9х12

Тип задачі	Алгоритм
	Послідовний		Модифікація послід-ого		Прискорений
	Час	Ефект-сть	Час	Ефект-сть	Час	Ефект-сть
Повна	100	100	75	98	20	92,7
Розряджена (0,4)	100	100	50	98	35	80
Розряджена блочної структури	100	100	85	90	45	70

Таблиця 3

Задачі розмірності 12х20

Тип задачи	Алгоритм
	Послідовний		Модифікація послід-ого		Прискорений
	Час	Ефект-сть	Час	Ефект-сть	Час	Ефект-сть
Повна	100	100	80	97	20	95
Розряджена (0,4)	100	100	45	90	30	75
Розряджена блочної структури	100	100	75	90	45	75

Дані уявляють собою процентний час виконання у середньому задач приведених розмірностей. За 100 % береться час виконання розв’язань послідовним алгоритмом.

Експериментально досліджуючи запропоновані алгоритми на збіжність та точність отриманого розв’язку можемо зробити такі висновки:

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

б) модифікація послідовного алгоритму близька за своєю результативністю до попереднього алгоритму, проте для задач більшої розмірності (наприклад 12х20) з матрицею обмежень повного типу дає результат швидше за нього. Найбільш вдалим є його застосування для задач, у яких матриця обмежень розряджена з коефіцієнтом наповненості 0,4.

в) прискорений алгоритм з конкретизацією змінної виявився найкращим за швидкістю збіжності. Його недоліком є невелика неточність знаходження розв’язку задач з розрядженими типами матриць. Для задач з повною матрицею обмежень є досить ефективним; вдалим буде його застосування на задачах великої розмірності.

Литература:

1. А.В. Кузнецов, В.А. Саколович, Н.И. Холод «Высшая математика.Математическое программирование» - Минск Высшэйшая школа 1984

2. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. - М.: Наука, 1969. - 368 с.

3. Юхіменко Б.І. Вибір ефективного алгоритму розв’язання задач цілочисленного лінійного програмування // Тр. Одес. Политехн. Ун-та – 2003.- Вип..2