МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ
имени ВЛАДИМИРА ДАЛЯ
Методические указания
к практическим занятиям
по дисциплине “Исследование операций в транспортных системах”
(для студентов специальностей “Организация перевозок и управление на транспорте”, “Транспортные системы”)
Часть 2 Модуль 2
УТВЕРЖДЕНО
на заседании кафедры
“Транспортные технологии”
протокол № _ от ________ г.
Луганск 2008
УДК 658
Методические указания к практическим занятиям по дисциплине “Исследование операций в транспортных системах” (для студентов специальностей “Организация перевозок и управление на транспорте”, “Транспортные системы”) часть 2 модуль 2/ Сост.: О.М. Балицкая, Е.И. Кичкина, – Луганск: Изд-во Восточноукр. нац. ун-та им. В. Даля, 2008. – 20 с.
Методические указания предназначены в помощь студентам, обучающимся по направлению «Транспортные технологии» при выполнении практических заданий по дисциплине «Введение в исследование операций в транспортных системах» (второй модуль). Указания содержат методы решения задач, примеры решений отдельных задач, список литературы. Данные методические указания рекомендуются для студентов дневной и заочной форм обучения при проведении практических занятий.
Составители: О.М. Балицкая, асс.
Е.И. Кичкина, доц.
Отв. за выпуск
Рецензент:
Общие сведения
На практических занятиях второго модуля рассматриваются следующие задачи: задачи целочисленного программирования, решаемые методом отсекающих плоскостей, методом ветвей и границ и венгерским методом; транспортная задача с ограничением пропускной способности; транспортная задача по критерию времени. При выполнении практических заданий студент приобретает навыки в решении целочисленного программирования разными методами, решении транспортных задач в зависимости от того, какая задача и какие условия поставлены в том или ином случае.
ЗАДАЧА 1
Венгерский метод в задаче о назначениях и в задаче о кратчайшем пути.
Венгерский метод решения назван в честь венгерского математика Кёнига. Суть метода основывается на следующей лемме 1.
Лемма 1. В задаче типа
(1)
оптимальное решение Y= (уij) не изменится, если из любой строки или столбца матрицы С ={сij}, где i = i,2,...,M,j = i,2,...,N, вычесть (или прибавить) постоянную величину.
Задание: Необходимо распределить пятерых работников Аi между пятью работами Вj если затраты Сij, обусловленные выполнением работником Ai работы Вj приведены в табл. 1.
Таблица 1
Параметры задачи и выбор min cij
I \ j |
B1 |
B2 |
B3 |
B4 |
B5 |
Min cij |
A1 |
4 |
5 |
7 |
4 |
6 |
4 |
A2 |
6 |
7 |
5 |
6 |
7 |
5 |
A3 |
6 |
5 |
6 |
5 |
6 |
5 |
A4 |
5 |
6 |
7 |
6 |
7 |
5 |
A5 |
7 |
5 |
6 |
5 |
6 |
5 |