- •Исследование операций в транспортных системах
- •6.070101 «Транспортные технологии»
- •Содержание
- •Введение
- •Лекция 1 исторические предпосылки возникновения дисциплины «исследование операций». Основные термины. Отличительные особенности
- •1.1. История развития научного направления «исследование операций»
- •1.2 Назначение дисциплины
- •1.3. Базовая терминология
- •1.4.1. Системный подход
- •1.4.2. Использование комплексных научных коллективов
- •1.4. Отличительные особенности исо
- •Лекция 2 операционные проекты и постановка операционных задач
- •2.1. Разработка операционных моделей
- •2.2. Поиск приемлемого плана исследований
- •2.3. Операционные проекты
- •2.4. Классы операционных задач
- •2.5. Постановка задач и определение целей
- •2.5.1. Постановка задачи.
- •2.5.2. Определение целей
- •2.5.3. Классификация задач
- •Лекция 3 транспортная задача линейного программирования
- •3.1. Формулировка задачи
- •3.2.Нахождение опорного решения методом «северо-западного угла»
- •3.3. Нахождение опорного решения методом «минимального элемента»
- •Лекция 4 Алгоритм циклических преобразований опорного решения транспортной задачи
- •4.1. Описание алгоритма однократного замещения
- •4.2. Метод «северо-западного угла»
- •4.2.1. Алгоритм решения
- •4.3. Метод «потенциалов»
- •4.3.1. Алгоритм решения
- •Лекция 5 теория графов. Сетевое планирование
- •5.1. Основы теории графов
- •5.2. Особенности и постановка задач сетевого планирования
- •Лекция 6 Методика построения и оптимизации сетевых моделей
- •6.1. Алгоритм графоаналитического метода построения сетевых моделей
- •6.2. Методика оптимизации сетевых моделей
- •Лекция 7 вероятностные модели исследования операций. Дискретная случайная величина. Непрерывная случайная величина
- •7.1. Терминология
- •7.2. Принципы исследования систем с помощью вероятностных моделей
- •7.3. Дискретная случайная величина
- •7.4. Непрерывная случайная величина
- •Лекция 8 Моделирование систем массового обслуживания
- •8.1. Постановка задач
- •8.2. Классификация систем массового обслуживания
- •8.3. Исследование характеристик потоков
- •8.3.1. Входящий поток
- •8.3.2. Выходящий поток
- •8.4. Принципы реализации модели
- •Лекция 9 имитационные модели массового обслуживания
- •9.1. Постановка задачи
- •9.2. Разработка модели
- •9.3. Графоаналитическая модель имитации обслуживания.
- •Лекция 10 Динамическое программирование
- •10.1. Особенности применения динамического программирования
- •10.2. Алгоритм реализации метода
- •10.3. Методика решения задач на основе принципа оптимальности Беллмана
- •Лекция 11 Теория игр и принятие решений
- •11.1. Общее представление о теории игр
- •11.2. Стратегии. Нормальная форма игры
- •11.3. Ситуации равновесия
- •11.4. Антагонистические игры. Игры с нулевой суммой
- •11. 5. Нормальная форма
- •11.6. Теорема о минимаксе
- •11.7. Другие виды игр
- •Лекция 12 экспертные методы принятия решений
- •12.1. Общая информация о методах экспертных оценок
- •12.2. Общая схема экспертизы
- •12.3. Задача оценивания
- •12.4. Подготовка экспертизы
- •12.5. Методы обработки экспертной информации
- •12.5.1. Начальные операции
- •12.5.2. Классификация методов
- •Лекция 13 Основы прогнозирования
- •13.1. Общее описание алгоритма прогнозирования
- •13.2. Прогнозная экстраполяция
- •13.3. Выбор формы кривой (тренда)
- •Лекция 14 реализация принципов и методов исо в сфере транспорта
- •14.1. Оценка возможностей.
- •14.2. Определение эффективности решения
- •14.3. Характеристика задач исо, направленных на решение проблем транспорта
- •Список рекомендованной литературы Основная
- •Дополнительная
- •Информационные ресурсы
3.2.Нахождение опорного решения методом «северо-западного угла»
Реализацию метода целесообразно пояснить на примере (рис 3.2).
Рис. 3.2. Опорное решение, полученное по методу «северо-западного угла»
Сущность метода «северо-западного угла» заключается в том, что на каждом очередном этапе или максимально исчерпываются ресурсы отправителей, или максимально удовлетворяются потребности потребителей.
Целевая функция для матрицы (рис. 3.2) составляет Z1 = 1130.
Последовательность действий при заполнении представленной выше матрицы следующая:
распределение ресурсов начинается с клетки, расположенной на «северо-западе», то есть в левом верхнем углу. Ей соответствует ресурс а1 = 20 и потребность b1 = 10. Удовлетворяем потребность полностью, остаётся ресурс, равный 10;
затем, по правилу, «дораспределяется» остаток ресурса, передав его следующей потребности b2 которая его забирает, но с нехваткой относительно её потребности;
нехватка ресурса для потребности b2 восполняется уже за счёт ресурса a2, расположенного уже во второй строчке таблицы;
действия повторяются таким же образом и далее, с образованием ряда ступенек, ведущих в правый нижний угол, где и заканчивается процесс начального распределения.
При нахождении опорного решения данным образом следует иметь в виду, что иногда на некоторой клетке таблицы одновременно заканчиваются и ресурсы, и потребности. Тогда для дальнейшего продвижения (по правилам расчёта) записывается базисный ноль - либо в последующей клетке той же строчки, либо в последующей клеточке того же столбца.
В законченном расчёте любого опорного решения количество заполненных клеток должно быть равно рангу системы (r). В противном случае, реализация алгоритма нахождения опорного решения становится невозможной.
Как первое, так и все последующие решения являются возможными для практического осуществления, а эффективность каждого оценивается значением целевой функции. Целевая функция практически служит критерием эффективности того или иного плана, записанного в виде корреспонденций груза в каждой клеточке распределительной таблицы.
3.3. Нахождение опорного решения методом «минимального элемента»
Метод «минимального элемента» строится на том же принципе исчерпания ресурсов для обеспечения потребностей, но есть одна разница.
Сущность метода предлагаемого метода сводится к тому, что, в отличие от метода северо-западного угла, последовательное исчерпание ресурсов за счёт потребностей проводится, через клетки, в уголках которых находятся (по возможности) наименьшие значения единичной стоимости.
Рис. 3.3. Опорное решение, полученное по методу «минимального элемента»
Целевая функция для матрицы (рис. 3.3) составляет Z2 = 970.
Стрелками показан маршрут прохождения клеток с минимальными элементами, начиная с самой выгодной минимальной клетки. Метод минимального элемента, в данной задаче, обеспечил меньшее значение целевой функции, чем метод «северо-западного угла». Таким образом, была сокращена трудоёмкость расчётов.
Контрольные вопросы
В чем состоит сущность транспортной задачи линейного программирования?
Какой показатель эффективности используется в транспортной задаче?
Что такое «ранг системы»?
Какие ограничения устанавливаются при решении транспортной задачи?
Опишите общую методику решения транспортной задачи
Охарактеризуйте особенности метода «северо-западного угла»
Охарактеризуйте особенности метода «минимального элемента»
