Алгоритм венгерського методу

Приведення до канонічного вигляду. Задача повинна бути закритою.

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

1. Перерахунок по стовпцям (віднімання від максимального елемента)

2. Та по рядкам (віднімання мінімального елемента).

3. Формування по стовпцям істотних нулів (позначення стовпців).

4. Рішення знайдено (кількість позначок”+”повинна дорівнювати розмірності задачі (і)).Якщо рішення не знайдено:

Перевірка на зацикленість (кількість ітерацій “< ” чи “=”).

5. Формування ланцюжка 0`®0<sup>*</sup>®…®0`, де

0^* - істотний нуль;

0` - виділений нуль в рядку з 0^*.

Побудова ланцюжка здійснюється від 0` в невиділеному стовпчику до 0<sup>*</sup> в рядку, потім прямуємо до 0` в стовпці,..., закінчуючи 0`.

При побудові ланцюжка необхідно відмічати рядки “+” та знімати позначення стовпців.

6. Якщо ланцюжок побудовано, то замінюємо: 0`«0^*.Переходимо до п.4.

7. Генерація нових нулів. Визначення h> 0 серед невиділених елементів.

Визначення мінімального з них.

8. Віднімання h від невиділених рядків та додавання h до виділених стовпців.

Перехід до п.3.

значення Z повинне дорівнювати значенню .

З метою програмування необхідно оголосити наступні файли:

C: array [1..M] of real;

A: array [1..N, 0..M] of real;

D: array [ 0..M] of real;

K: longint;

B: array [1..N] of byte;

Необхідно розподілити партію комп’ютерів (6) між підрозділами ВУЗу (8).

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

max

1 і=1, 6

1 j=1, 8

E { 0, 1};