Ручное решение задачи (венгерский метод)

 

Дана матрица стоимостей:

 

 

дополним её нулями до вида матрицы N x N. так, поступим по приведенному выше алгоритму:

Приведем ее к такому виду, что она содержала хотя бы по одному нулевому элементу в каждой строке и столбце:

 

 

По полученной матрице видно, что звездочки можно расставить несколькими способами, то есть мы можем получить несколько равнозначных (по величине целевой функции) решений. В данном случае правильных ответов два:

Таким образом оптимальным решением задачи является следующее распределение приборных систем по организациям:

· 1-ю систему отправить на изготовление 9-ой или 10-ой организации.

· 2-ю систему – 6-ой организации.

· 3-ю систему – 4-ой организации.

· 4-ю систему – 5-ой организации.

· 5-ю систему – 2-ой организации.

· 6-ю систему – 3-ой организации.

На это решение у нас получаются затраты минимальны и составляют 10 условных единиц.

 

Рассчитаем затраты на производство каждой системы определенной организацией, пользуясь формулой расчета :

 

 

Причем  берется при данном расчете из начальной матрицы, полученные результаты приведены в таблице для обоих решений:

Таблица 2 – Результаты решения задачи по венгерскому методу

Организация	Система	Затраты 1е решение	Затраты 2е решение
2	5	1	1
3	6	2	2
4	3	2	2
5	4	1	1
6	2	1	1
9	1	3	0
10	1	0	3
Суммарные затраты		10

 

Таким образом, оба решения дают одинаковые суммарные затраты.

 

Решение задачи с использованием компьютерных средств

Компьютерное решение задачи производится с помощью пакета экономических решений PER, имеющего доступный DOS-интерфейс. Решение задачи осуществляется в соответствии со следующим алгоритмом:

1. Вызвать программу;

2. Выбрать тип решаемой задачи ( в данном случае задача о назначении):

3.

Рисунок 1 – выбор типа решаемой задачи

 

4. В главном меню выбрать пункт «Ввод новой задачи»:

 

Рисунок 2 – Ввод новой задачи

 

5. Задать признак оптимизации– максимизировать/минимизировать, ввести количество объектов и заданий:

Рисунок 3 – задание признаков оптимизации

6. Ввести необходимые числовые данные задачи:

 

Рисунок 4 – ввод данных в программу

 

7. Выбрать в главном меню пункт «Решение задачи»:

Рисунок 5 – команда решения задачи

8. Выбрать просмотр решения задачи:

 

Рисунок 6 – выходные данные

 

Из приведенного выше решения следует, что для распределения работ с минимальными затратами:

· организация 2 (объект 02) должна разрабатывать систему 5 (задание Т5)

· организация 3 (объект 03) должна разрабатывать систему 6 (задание Т6)

· организация 4 (объект 04) должна разрабатывать систему 3 (задание Т3)

· организация 5 (объект 05) должна разрабатывать систему 4 (задание Т4)

· организация 6 (объект 06) должна разрабатывать систему 2 (задание Т2)

· организация 9 (объект 09) должна разрабатывать систему 1 (задание Т1)