Назначение бригад на лесосеки для получения максимальной выгоды. Задача о назначениях бригад на лесосеки

Страницы работы

3 страницы (Word-файл)

Содержание работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное агентство по образованию РФ

Санкт – Петербургская ГЛТА им. С.М. Кирова

Кафедра Сухопутного транспорта леса

Лесопромышленная логистика

Расчетно – графическая работа № 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 со звездочкой. После завершения цепочки начинаем преобразование нулей со штрихом.

*

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

Похожие материалы

Информация о работе