Разработка операционных моделей

Исследование операций в транспортных системах

Конспект лекций

по курсу « Исследование операций в транспортных системах»

для студентов направления подготовки

6.070101 «Транспортные технологии»

дневной и заочной форм обучения

Мариуполь

УДК 656.13:004.312.02 (075.8)

Украинский Е.А. Исследование операций в транспортных системах [Электронный ресурс]: конспект лекций по курсу «Исследование операций в транспортных системах» для студентов направления подготовки 6.070101 «Транспортные технологии» дневной и заочной форм обучения / Е.А. Украинский. – Мариуполь: ГВУЗ «ПГТУ», 2015. – 92 с. – Режим доступа: http://mo.pstu.edu/

Конспект лекций включает содержание, краткий лекционный материал, согласно программе курса, контрольные вопросы, список основной, дополнительной литературы, информационные ресурсы.

Автор Е.А. Украинский, ассистент

Рецензент А.А. Лямзин, к.т.н., доцент

Утверждено на заседании кафедры «Технологии международных перевозок и логистика»

протокол № 6 от 06 января 2015 г.

Утверждено

методической комиссией факультета транспортных технологий

протокол № 5 от 13 января 2015 г.

© ГВУЗ «ПГТУ», 2015

содержание

ВВЕДЕНИЕ
Лекция 1. ИСТОРИЧЕСКИЕ ПРЕДПОСЫЛКИ ВОЗНИКНОВЕНИЯ ДИСЦИПЛИНЫ «ИССЛЕДОВАНИЕ ОПЕРАЦИЙ». ОСНОВНЫЕ ТЕРМИНЫ. ОТЛИЧИТЕЛЬНЫЕ ОСОБЕННОСТИ
1.1. История развития научного направления «исследование операций»
1.2. Назначение дисциплины
1.3. Базовая терминология
1.4. Отличительные особенности ИСО
1.4.1. Системный подход
1.4.2. Комплексные научные коллективы
Контрольные вопросы
Лекция 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. Характеристика задач ИСО, направленных на решение проблем транспорта
Контрольные вопросы
СПИСОК РЕКОМЕНДОВАННОЙ ЛИТЕРАТУРЫ

введение

Курс «Исследование операций в транспортных системах» читается студентам 2-го курса факультета транспортных технологий и относится к категории теоретических, но всё внимание здесь сосредоточено на решении практических проблем транспортной отрасли.

Математические модели в исследовании операций применяются широко, но, как правило, использовать без переделки классическую модель математики невозможно, поскольку реальная среда, которая моделируется, значительно сложнее и ситуативно богаче.

Основные цели и задачи изучения курса следующие:

– формирование теоретических знаний, необходимых для усвоения и понимания терминологии изучаемого курса;

– привить студентам навыки и умения практического использования математических методов исследования операций

– сформировать цельное представление и знания об использовании линейного, целочисленного и динамического программирования, сетевых методов планирования и управления, моделирования систем массового обслуживания в задачах транспорта.

В качестве базовых дисциплин, обеспечивающих успешное освоение курса, являются: математика, теория вероятностей и математическая статистика, философия, а также профессиональные дисциплины, которые формируют общее представление студента о транспортных процессах.

Лекция 1

исторические предпосылки возникновения дисциплины «исследование операций». основные термины. отличительные особенности

План

1.1. История развития научного направления «исследование операций»

1.2. Назначение дисциплины

1.3. Базовая терминология

1.4. Отличительные особенности ИСО

1.4.1. Системный подход

1.4.2. Комплексные научные коллективы

1.1. История развития научного направления «исследование операций»

Первыми авторами монографии по «исследованию операций» были американские учёные Р. Акоф и М. Сасиени. Их научный труд «Основы исследования операций» был издан в 1968 г. в США, а в 1971 году, с разрешения авторов, книга была издана в СССР.

Согласно версии названных авторов, алгоритмы новой дисциплины впервые были использованы в Англии, при разработке военных операций в период второй мировой войны.

Именно тогда для решения неординарных задач военного характера к решению проблем были привлечены гражданские учёные различных специальностей, из которых были образованы группы «исследования операций».

Организация таких групп представляла известные трудности, поскольку проблемная ситуация требовала разрешения неординарных задач, в короткий период, с максимальным напряжением сил. Одной из задач, которая была решена, стала система эффективного использования новых радиолокационных средств в воздушной битве за Англию. После окончания войны принципы операционных исследований были перенесены и на гражданские отрасли в условиях рыночной экономики.

Методология «исследования операций» было воспринято положительно, и в СССР и, соответственно, введено в качестве учебной дисциплины в систему высшего образования для всех специализаций технического и экономического профиля.

Пути реализации методик несколько отличались, в силу различий экономического устройства, но методы системного подхода к решению задач, во многом, совпадали.

С переходом к рынку, принципы построения экономических систем стали очень похожими.

Назначение дисциплины

Исследование операций (ИСО) — составная часть выработки и принятия решений. Они основаны на точном формализованном описании ситуации, количественном анализе факторов, определяющих возможности достижения поставленных целей.

Исследование операций – это совокупность научных методов соизмерения затрат и результатов, связанных с выработкой и реализацией оптимальных решений в сложных человеко- машинных системах.

Процесс принятия решений, кроме стадий анализа ситуации и синтеза оптимальных решений, включает стадию выбора и обоснования целей, сравнение различных вариантов, оценку их возможных последствий, непосредственно принятие самого решения, его реализацию и влияние на последующие решения.

Совокупность методологических средств, используемых для подготовки и обоснования решений по сложным проблемам, в том числе, экономического и технического характера, предоставляет системный анализ.

Системный анализ опирается на ряд математических дисциплин и современных методов управления. Конечная процедура системного анализа - это построение обобщённой модели системы, отображающей взаимосвязи объектов реальной действительности.

Дисциплина «исследование операций» широко используется и в науке, и при решении практических задач в отраслях отечественной экономики, включая и транспортную отрасль.

Несмотря на некоторые различия в реализации операционных задач, содержание и принципы построения курсов «исследования операций» в разных странах принципиально не отличаются, а взаимно дополняют друг друга.

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

Для этого потребовалась разработать теорию расчёта бесстыкового пути, затем провести теоретико-экспериментальные исследования, далее разработать конструкцию, провести внедрение самого масштабного проекта. Наряду со стратегическими масштабными исследованиями было проведено большое количество исследований тактического уровня, которые можно рассматривать как операционные, по их содержанию.

Отличительной особенностью развития исследования операций (ИСО), в отечественных условиях, стал высокий уровень математизации курсов. Специалисты математического профиля в равной степени со специалистами других отраслей знаний считают эту дисциплину своей.

Базовая терминология

Как и большинство профессионально-ориентированных дисциплин «Исследование операций в транспортных системах» опирается на собственную теминологическую базу. Целесообразно выделить основные термины.

Исследование операций - это комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений при проведении операций.

Операция – система управляемых действий, объединенная единым замыслом и направленная на достижение определенной цели.

Система — множество составляющих единство элементов, их связей и взаимодействий между собой, между ними и внешней средой, образующих присущую данной системе целостность, качественную определённость и целенаправленность.

Модель - это некоторое существенное описание или представление реальной или “будущей” действительности (в целом или в её частях), полезное для решения системных проблем.

Целевая функция - это количественный показатель предпочтительности или эффективности решений.

Операционная модель — это абстрактное представление применяемых способов и порядка реализации корпоративной стратегии в повседневной деятельности компании.

Лицо, принимающее решение (ЛПР) – субъект решения (менеджер), наделённый определёнными полномочиями и несущий ответственность за последствия принятого и реализованного управленческого решения. ЛПР — один или несколько человек (коллектив), на которых лежит ответственность за принятое решение.

Отличительные особенности ИСО

Особенности и заключаются в том, сложилась практика использования дисциплины в решении актуальных задач организаций на основе использования:

a) системного подхода,

b) с использованием комплексных научных коллективов,

c) путём применения научного метода к задачам управления.

Рассмотрим теперь каждую из этих особенностей более подробно.

Системный подход

Системный подход основан на том, что в организационных системах поведение любой части системы некоторым образом влияет на все остальные части. Не все такие влияния существенны, а часть из них даже невозможно обнаружить. Поэтому суть этого подхода заключается в систематическом поиске существенных взаимодействий при оценке деятельности или стратегии любой части организации.

Такой подход к организационным задачам кардинально отличается от подхода, связанного с приведением задачи к приемлемому размеру. Операционисты почти всегда расширяют первоначальное представление в предложенной им задаче, включая в нее взаимодействия, не учтенные в формулировке, данной руководством.

Использование комплексных научных коллективов

Оно становится необходимым ввиду того, что предметом интересов являются сложные ранее не решаемые задачи различного масштаба. Притом, сама организационная часть связывается с привлечением специалистов, которые могут организовать исследования. Руководитель операционных исследований должен обладать достаточно широким научным кругозором, чтобы привлечь специалистов знакомых с некоторым кругом специальных задач.

Расчленение научных знаний на отдельные конкретные дисциплины —явление сравнительно новое. Этот процесс относится к ХIХ в.

Примерно с середины позапрошлого века естественные науки разделились на физику и химию. Немного времени спустя, в самостоятельный предмет выделилась биология, а к концу века также и физиология.

По этому поводу авторы монографии по ИСО, Р. Акоф и А.Сасиени (США) иронически восклицают:

«Мы настолько привыкли классифицировать научные знания в соответствии с кафедральной структурой университетов, что подчас считаем, будто такая организация соответствует структуре самой природы. Нет ничего более далекого от истины. Не существует таких вещей, как физические, биологические, психологические, экономические задачи и т. д. Существуют просто задачи.

Научные же дисциплины представляют собой различные методы исследования этих задач. На любую задачу можно взглянуть с позиций любой научной дисциплины. Но, естественно, далеко не всегда это целесообразно делать.

В сущности это та же мысль, которая была высказана уже ранее, но в другой форме: для организации не существует самостоятельных производственных, сбытовых или финансовых задач.

Такое расчленение (то есть декомпозиция – по терминологии системного анализа – комментарий наш) отражает лишь различные подходы к рассмотрению одних и тех же организационных задач.»

Так, например, столкновение автомашины с локомотивом на переезде можно объяснить законами движения или техническим отказом сигнальных устройств, или состоянием здоровья водителя, или состоянием его психики, или общественным использованием автомашин как средства самоубийства.

Позиция, с которой мы рассматриваем событие, определяется причинами, вызывающими наш интерес к нему. Если, допустим, мы стремились бы предотвратить повторение подобного события, то мы рассматривали бы эту задачу так, чтобы получить эффективное решение в кратчайшее время при наименьших затратах.

На основе нашего опыта мы находим эффективные способы анализа большинства часто возникающих задач. При решении незнакомых и сложных задач мы склонны использовать тот же подход, который нам известен.

Поэтому нет ничего удивительного в том, что если, скажем, перед специалистом по психологии персонала ставится задача увеличения производительности, то он старается решить ее путем подбора наиболее квалифицированных рабочих или улучшения их профессиональной подготовки. Инженер- механик старается усовершенствовать сами станки.

Специалист по организации производства пытается улучшить размещение оборудования, упростить операции, выполняемые рабочими, или предложить более эффективные меры стимулирования.

Специалист по анализу систем и процедур стремится усовершенствовать поток информации, циркулирующей внутри предприятия, и т. д.

Каждый из этих специалистов может добиться определенных улучшений, но какое из них или какая их комбинация является наилучшей? В отношении сложных задач мы редко знаем это заранее. Поэтому целесообразно рассмотреть и оценить, возможно, более широкий диапазон подходов к задаче. Поскольку в настоящее время существует уже более сотни чистых и прикладных научных дисциплин, то очевидно, что нет возможности использовать представителей каждой из них при выполнении каждого научно-исследовательского проекта. Поэтому желательно представить в этом коллективе как можно большее число дисциплин и подвергнуть критическому анализу работу коллектива с позиций наиболее широкого круга дисциплин, не представленных в нём.

Здесь имеется в виду, что диапазон компетенции участников ИСО должен быть достаточно широк, и, не мешало бы, иметь опыт в решении такого рода задач. Заметим, что теперь, в отечественных условиях, тоже становится возможной временная концентрация специалистов и учёных на решении масштабных проблемных задач, причём при условии достойной оплаты.

Задачи исследования операций, в силу своей относительно малой масштабности, не претендуют на обязательное упоминание в каждом случае, поскольку их повторяемость неизбежна, и практика закрепляется повтором решений.

Контрольные вопросы

1. Назовите «основоположников» научного направления «исследование операций».

2. Охарактеризуйте назначение дисциплины.

3. Назовите примеры решения практических задач в рамках исследования операций.

4. Какова роль математических дисциплин в развитии направления «исследование операций»?

5. Дайте определение понятию «исследование операций»

6. Охарактеризуйте термин «операция»

7. Объясните сущность понятия «система»

8. В качестве чего может быть выражен критерий оптимальности?

9. Что такое «целевая функция»?

10. Охарактеризуйте понятия «модель» и «операционная модель».

11. Перечислите основные отличительные особенности ИСО.

12. В чем заключается сущность системного подхода?

13. Почему возникает необходимость использования комплексных научных коллективов в ИСО?

Лекция 2

Операционные проекты и постановка операционных задач

План

2.1. Разработка операционных моделей

2.2. Поиск приемлемого плана исследований

2.3. Операционные проекты

2.4. Классы операционных задач

2.5. Постановка задач и определение целей

2.5.1. Постановка задачи

2.5.2. Определение целей

2.5.3. Классификация задач

Разработка операционных моделей

При изложении сущности научного метода в большинстве случаев утверждается, что его отличительной особенностью является эксперимент. Однако когда речь идет о государственных, военных или промышленных организациях, эксперимент в узком смысле слова, т. е. физическое изменение значения переменных, часто, бывает, невозможен или нецелесообразен.

Так, например, промышленная фирма не может рисковать своим существованием ради проведения успешного эксперимента.

Конечно, эксперимент иногда возможен, особенно на уровне подсистем, и он действительно играет важную роль в ИСО. Тем не менее, как правило, вся система, являющаяся объектом изучения, не может быть подвергнута эксперименту. Поэтому, в большинстве случаев, исследуя систему в целом, необходимо применять подход, не связанный с проведением эксперимента (в узком смысле, т. е. требующего физических изменений изучаемого объекта).

А это значит, что операционист должен сам разрабатывать теоретическую модель реальной системы.

Операционные модели имеют форму уравнений, которые, хотя и могут быть сложными с математической точки зрения, но обобщаются очень простой первоначальной структурой:

где: U - есть полезность или значение критерия, характеризующего качество функционирования системы; X_i - переменные, которыми можно управлять; Y_j - переменные (и постоянные), не поддающиеся управлению, но влияющие на U, и f -функция, задающая соотношения между U, X_i, Y_j.

Кроме того, одно или несколько уравнений или неравенств часто требуются для выражения того факта, что некоторые из управляемых переменных могут изменяться в определенных пределах. Так, например, количество машинного времени, отводимое на производство изделий, не может быть меньше нуля или больше общего ресурса машинного времени.

Сумма ассигнований, направляемых в различные подразделения фирмы, не может превышать общего количества наличных денег.

Уравнение, выражающее целевую функцию, совместно с ограничениями, образует модель системы или задачи, которую мы хотим решить. Следовательно, здесь идет речь: как о модели принятия решения, так и о модели системы.

Целевая функция представляет собой обобщающий результат эффективности, выраженный, чаще всего, в количественной денежной форме.

Поиск приемлемого плана исследований

Если модель построена, то ее можно использовать для отыскания точных или приближенных оптимальных значений управляемых переменных, т. е. таких значений, которые обеспечивают наилучший показатель качества функционирования системы при заданных значениях неуправляемых переменных.

Иными словами, можно получить решение задачи на модели.

Как именно получается это решение, зависит от характера используемой модели.

Решение может быть получено на модели экспериментально (т. е. путем изменения параметров модели) или с помощью математического анализа.

В ряде случаев математический анализ можно провести, не зная конкретных значений переменных (т. е. в абстрактной или символической форме). В других случаях значения переменных должны быть заданы численно.

Для некоторых типов функций (например, элементарных алгебраических функций), если число ограничений не слишком велико, классические методы математики являются эффективным средством отыскания оптимальных значений управляемых переменных.

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

С другой стороны, функция f может представлять собой набор вычислительных правил (алгоритмов), которые позволяют вычислять значение критерия качества функционирования системы при любом заданном множестве значений управляемых и неуправляемых переменных, но не обеспечивают непосредственного отыскания оптимальных значений управляемых переменных.

Обычно можно также определить процедуру последовательного выбора значений управляемых переменных таким образом, чтобы эти значения сходились к оптимальному решению.

В некоторых алгоритмах затраты на отыскание оптимального решения могут оказаться слишком большими по сравнению с выгодой, даваемой таким решением, в сравнении с достаточно «хорошим» решением, которое иногда можно определить сравнительно просто.

Всякий раз, когда вычисляется значение U, соответствующее новому набору значений Х при заданных значениях У получают некоторую новую информацию о том, как функционирует система.

Из этой информации можно сделать вывод, что иной набор значений Х обеспечивает определенное улучшение функционирования системы. Если есть возможность оценить размер улучшения до выполнения вычислений, то можно сравнить затраты на вычисления и решить, целесообразны ли дальнейшие попытки.

В ряде случаев роль человека, принимающего решения в системе, невозможно достаточно хорошо описать, так что не удается выразить в явном виде его функции с помощью модели. В такой ситуации моделирование могут осуществить сами люди.

Этот вид моделирования носит название операционных игр.

Независимо от того, какой метод используется, всегда отыскивается оптимальное, или близкое к нему, решение.

Оптимальным является решение, которое минимизирует или максимизирует (в зависимости от существа задачи) критерий качества на модели при заданных условиях и ограничениях, представленных в этой модели.

Термин критерий, напомним, означает численную оценку.

Если решение, ради отыскания которого проводится исследование, принадлежит к категории многократных, то, учитывая характер систем, изучаемых в ИСО, вполне вероятно, что в интервале между принятиями решений изменяются значения некоторых неуправляемых переменных и даже структура самой системы.

Поэтому необходимо в системах, которые многократно рассчитываются, обнаруживать и существенные изменения: как в системе, так и в окружающей систему внешней среде.

Иначе говоря, результаты, представляющие собой правила принятия многократных решений или же решения, применяемые в течение длительных интервалов времени, следует подстраивать, т. е. контролировать корректность их применения.

При многократном формировании решений в моделирование вовлекаются и разнообразные виды моделей. При развитой системе организации решений формируется и парк моделей, которые образуют более сложный и развитый научный базис.

Мобильное сочетание различных частных методик по решению проблем мы наблюдаем в крупном бизнесе. Привлечение специалистов высокого класса и разработка комплексных решений, а далее и стратегий стало достаточно типичным для современных тенденций в практичном использовании операционных проектов.

Дата добавления: 2015-10-29