МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное агентство по образованию РФ
Санкт – Петербургская ГЛТА им. С.М. Кирова
Кафедра Сухопутного транспорта леса
Лесопромышленная логистика
Расчетно – графическая работа № 7
Назначение бригад на лесосеки для получения максимальной выгоды.
Выполнил:
Студент ЛИФ V – 4
№ ЗК 13030
Проверил:
Оценка_____________
Санкт – Петербург
2007 г.
Задача о назначениях бригад на лесосеки.
;
Имея исходные данные по лесосекам, распределяем бригады в произвольном порядке так, чтобы получить максимальную выгоду с данных лесосек:
|
4 |
2 |
3 |
1 |
5 |
|
2 |
3 |
3 |
4 |
1 |
|
3 |
2 |
2 |
2 |
4 |
|
5 |
4 |
6 |
5 |
3 |
|
3 |
4 |
4 |
2 |
2 |
Венгерский метод:
Предварительный этап состоит из двух преобразований.
а). Из максимального элемента столбца вычитаем все элементы этого столбца.
|
1 |
2 |
3 |
4 |
0 |
|
3 |
1 |
3 |
1 |
4 |
|
2 |
2 |
4 |
3 |
1 |
|
0 |
0 |
0 |
0 |
2 |
|
1 |
0 |
2 |
3 |
3 |
б). Из всех элементов строк вычитаем минимальный.
|
1 |
2 |
3 |
4 |
0 |
|
2 |
0 |
2 |
0 |
3 |
|
1 |
1 |
3 |
2 |
0 |
|
0 |
0 |
0 |
0 |
2 |
|
2 |
0 |
2 |
3 |
3 |
Решение:
Отмечаем произвольный ноль в столбце (*), и далее во всех столбцах так, чтобы в каждом столбце и в каждой строке было по 10*.
Получаем отсутствие двух нулей со звездочкой. Пользуемся блок-схемой венгерского метода для решения этой задачи.
+ + +
|
1 |
2 |
3 |
4 |
* 0 |
|
2 |
* _ 0 _ |
_ _2 _ |
│ _ _0 |
3 |
|
1 |
│ │ 1 |
3 |
2 |
0 |
|
* 0 |
│ │ 0 |
│ 0 |
0 |
2 |
|
2 |
│ 0 |
2 |
3 |
3 |
Выделяем штрихом 0 в строке, и во второй строке первого столбца и проведем цепочку через 0 со звездочкой. После завершения цепочки начинаем преобразование нулей со штрихом.
|
* 0 |
2 |
2 |
4 |
0 |
|
1 |
0 |
1 |
* 0 |
3 |
|
0 |
1 |
2 |
2 |
* 0 |
|
0 |
1 |
* 0 |
1 |
3 |
|
1 |
* 0 |
1 |
3 |
3 |
Получаем звездочки во всех строках и столбцах. Оптимальный выбор получен.
Значения выделенных нулей.
|
1,1 |
2,4 |
3,5 |
4,3 |
5,2 |
|
4 |
4 |
4 |
6 |
4 |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.