Воденин Д.Р. Специальные задачи и методы линейного программирования

Учебное методическое пособие, Ульяновск, 2008 г.
В учебно-методическом пособии представлены классические результаты по решению транспортной задачи и задачи о назначениях. Приведены известные алгоритмы решения этих задач: метод потенциалов и венгерский алгоритм. Рассмотрены примеры.
Пособие предназначено для студентов старших курсов и аспирантов факультета математики и информационных технологий.
Глава
1. Транспортная задача
1.1. Постановка транспортной задачи
1.2. Транспортные сети и маршруты
1.3. Базисные решения транспортной задачи
1.4. Построение начального допустимого решения транспортной задачи
1.5. Метод потенциалов для решения транспортной задачи
1.6. Алгоритм метода потенциалов
1.7. Пример решения транспортной задачи методом потенциалов
1.8. Открытые транспортные задачи
1.9. Другие виды транспортных задач
Глава
2. Задача о назначениях
2.1. Постановка задачи о назначениях
2.2. Эквивалентные матрицы
2.3. Венгерский алгоритм для задачи о назначениях
2.4. Пример решения задачи о назначениях
2.5. Венгерский алгоритм для транспортной задачи
2.6. Обоснование венгерского алгоритма для транспортной задачи
2.7. Пример решения транспортной задачи венгерским алгоритмом