На головну

алгоритм методу

  1. I. Внесення відомостей в форму ДМВ-1 при використанні методу визначення митної вартості за ціною угоди із ввезених товарів
  2. II. Вимоги до методів вимірювання і контролю показників мікроклімату
  3. III. Внесення відомостей у форму ДТС-2 при застосуванні резервного методу визначення митної вартості
  4. N Вибір методу пайки залежить від програми випуску виробів, особливостей конструкції, вимог до якості.
  5. N Необхідна точність досягається методами автоматичного отримання розмірів на налаштованих верстатах при забезпеченні взаємозамінності оброблюваних заготовок і що збираються вузлів.
  6. А) негативно ставилися до особи І. В. Сталіна і його методам будівництва соціалізму
  7. А) Квадратна матриця і її визначник. б) Особлива і неособлива квадратні матриці. в) Приєднана матриця. г) Матриця, зворотна даної, і алгоритм її обчислення.

1. Здійснити приведення вихідної матриці С = || Cij || по рядках. В результаті чого отримати З'= || C'ij ||. C'ij = Cij - Min Cij

j

2. Здійснити приведення матриці С' за стовпцями і отримати матрицю Ск = || Cкij ||. Cкij = C'ij - Min C'ij

i n n

3. Обчислити суму призводять констант: hk = ? min Cij + ? min C'ij

i = 1 j j = 1 i

 Сума призводять констант на 1 етапі приведення h' є нижньою межею для безлічі Х. W (x) = h1 .

4. Вибрати претендентів для розгалуження в безліч y. Це будуть всі пари міст (i = 1, n), (j = 1, n), (i ? j), для яких зij = 0.

5. Для виділених претендентів підраховуємо величину Qij: Qij = Min C'ij + Min C'ij

j '?j i '?i

min C'ij - В рядку i вибирається те місто, виключаючи j, якому відповідає мінімальне j '?j відстань наведеної матриці.

min C'ij - В стовпці j вибирається те місто, виключаючи i, якому відповідав би мінімальний i '?i елемент.

6. З підрахованих Qij вибрати максимальне: Qkl = Max Qij.

7. Пару міст (k, l) включити до множини y (вона ж є забороненою для y).

8. Підрахувати оцінку для безлічі y. Вона буде дорівнює раніше виробленим затратам і величиною Qkl. W (k, l) = W (x) + Qkl.

9. З кожного міста можна виїхати тільки 1 раз, тому з подальшого розгляду виключити рядок к. У кожне місто можна в'їхати тільки 1 раз, тому виключити стовпець l. Щоб уникнути замкнутих підциклів, заборонити переїзд з міста l в місто до. Тобто відповідного елементу привласнити ?. Зlk= ?.

10. Отримана усічена матриця містить 2 допустимі пари міст, які є замикаючими для деякого циклу без петель. Тому на даному етапі перевіряється розмірність матриці. Якщо вона 2х2, то перейти до пункту 12, в іншому випадку - до пункту 11.

11. Перевірити, чи є отримана матриця наведеної, якщо так, то оцінка для безлічі y дорівнює оцінці того безлічі, з якого вона отримана. W (Ym) = W (Ym-1). Якщо немає, то здійснити приведення отриманої матриці і підрахувати суму призводять констант hk. Тоді оцінка для безлічі y дорівнюватиме: W (Ym) = W (Ym-1) + Hk.

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

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



Формування нижніх і верхніх оцінок цільової функції | комбінаторні методи

Математичне формулювання завдань дискретного програмування | Метод відсікань. Формулювання вірного відсікання. алгоритм методу | Переваги та недоліки алгоритму. | Метод лексикографічного перебору | Метод неявного перебору по векторної решітці | наближені методи | Алгоритм симплекс методу | Друга стандартна форма | Вихідна задача в канонічній формі | Xi |

© um.co.ua - учбові матеріали та реферати