Змістовна постановка задачі. В об'єднанні знаходиться n автомобілів, здатних кожен перевозити в місяць Qi тонн вантажу (i = 1,2, ..., n). З їх допомогою необхідно забезпечити перевезення вантажів (пиломатеріал, шурупи і т.д.) від постачальників до споживачів по n маршрутами в кількості Rj тонн в місяць (j = 1,2, ..., n).
Завдання полягає в тому, щоб перевезти всі вантажі з мінімальними витратами, для цього треба кожен автомобіль пустити по одному і тільки його маршруту. Якщо можливість автомобіля в перевезенні вантажу нижче потреби споживача цього вантажу, то на даний маршрут автомобіль не може бути призначений. Тому складається матрицю С, що характеризує витрати i-го автомобіля, в разі, якщо він буде призначений на j-й маршрут.
Угорський метод рішення завдань про призначення
Алгоритм угорського методу.
Задача про призначення є окремим випадком транспортної задачі. тому для її вирішення можна скористатися будь-яким алгоритмом лінійного програмування, однак більш ефективним є угорський метод.
Специфічні особливості завдань про призначення послужили приводом до появи ефективного угорського методу їх вирішення. Основна ідея угорського методу полягає в переході від вихідної квадратної матриці вартості З до еквівалентної їй матриці Се з невід'ємними елементами і системою n незалежних нулів, з яких ніякі два не належать одній і тій же рядку або одному і тому ж стовпчику. Для заданого n існує n! допустимих рішень. Якщо в матриці призначення X розташувати n одиниць так, що в кожному рядку і стовпці знаходиться тільки по одній одиниці, розставлених відповідно до розташованими n незалежними нулями еквівалентної матриці вартості Се, то отримаємо допустимі рішення задачі про призначення.
Слід мати на увазі, що для будь-якого неприпустимого призначення відповідна йому вартість умовно покладається рівною досить великому числу М в задачах на мінімум. Якщо вихідна матриця не є квадратної, то слід ввести додатково необхідну кількість рядків або стовпців, а їх елементам привласнити значення, які визначаються умовами завдання, можливо після редукції, а домінуючі альтернативи дорогі або дешеві виключити.