ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
ИНСТИТУТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ
Яретенко Н. И.
Математика (Исследование операций)
Курс лекций
для направления подготовки (специальности)
230105.65 «Прикладная информатика (Программное обеспечение ВТ и АС)»,
080801.65«Прикладная информатика (в экономике)»,080507.65 «Менеджмент организации»,080105.65 «Финансы и кредит», 080109.65 «Бухгалтерский учет, анализ и аудит».
(C применением элементов дистанционного обучения)
Мурманск
2010 г.
Автор - Н.И. Яретенко,
к. воен. наук, доцент
кафедры Информационных систем и
прикладной математики МГТУ.
Курс лекций
рассмотрен
и одобрен кафедрой ИС и ПМ
«__» _______ 2010 г.
Рецензенты:
В.В. Ковальчук,
д.т.н., профессор, зав.кафедрой
ИС и ПМ МГТУ.
Н. Н. Морозов зав. кафедрой
Физики МГТУ.
ОГЛАВЛЕНИЕ
Лекция. Основы теории принятия решений
1.1. Общие положения………………………………………………………….6
1.2. Основные понятия системного анализа…………………………………..8
1.3. Основные понятия исследования операций…………………………….12
1.4. Постановка задач принятия оптимальных решений……………………13
1.5. Методология и методы принятия решений………………………………15
Контрольные вопросы………………………………………………...17
2. Лекция. Экономико – математическое моделирование
2.1.Основные понятия.............................................................................18
2.2.Классификация моделей....................................................................19
2.3.Классификация решаемых экономических задач...............................21
Контрольные вопросы....................................................................22
Лекция. Линейное программирование
3.1.Общая постановка задачи..................................................................23
3.2. Двойственность в задачах линейного программирования……………25
3.3.Теоремы двойственности...................................................................26
3.4.Решение задач линейного программирования геометрическим
методом................................................................................................28
3.5.Симплексный метод решения задач линейного программирования...35
Контрольные вопросы..................................................................39
Лекция.Транспортная задача
4.1.Постановка задачи..............................................................................41
4.2.Алгоритм решения транспортных задач………………………….………42
4.3.Метод наименьшего элемента..............................................................43
4.5.Метод потенциалов.............................................................................44
4.6.Примеры решения транспортных задач................................................45
Контрольные вопросы..................................................................55
5.Лекция.Целочисленное программирование
5.1.Постановка задачи целочисленного программирования........................57
5.2.Графический метод решения задач целочисленного программирования.....................................................................................58
5.3.Пример решения задачи целочисленного программирования…………..59
5.4.Задача о коммивояжере……………………………………………………..61
5.5.Пример решения задачи о коммивояжере…………………………………62
Контрольные вопросы...........................................................64
Лекция. Динамическое программирование
6.1. Постановка задачи............................................................................65
6.2.Принцип оптимальности Беллмана....................................................66
6.3.Задача распределения средств на 1 год…………………………………67
6.4. Задача распределения средств на 2 года............................... ……….72
Контрольные вопросы........................................................72
7. Лекция. Управление производством
7.1.Задача о замене оборудования …………………………………………73
7.2 Управление запасами. Складская задача ……………………………….79
Контрольные вопросы..........................................................81
Лекция. Теория игр
8.1.Основные понятия………………………………………………………..82
8.2.Антагонистические игры ………………………………………………..83
8.3.Игры с «природой»...........................................................................85
Контрольные вопросы………………………………………….93
Лекция. Системы массового облуживания
9.1.Формулировка задачи и характеристики СМО………………………..94
9.2.СМО с отказами…………………………………………………………..96
9.3.СМО с неограниченным ожиданием.................................................96
9.4. СМО с ожиданием и с ограниченной длиной очереди……………….97
9.5. Примеры решения задач...................................................................98
Контрольные вопросы……………………………………….…..101
Лекция. Сетевое планирование
10.1. Основные понятия метода сетевого планирования.........................101
10.2. Расчет сетевых графиков................................................................105
Контрольные вопросы………………………………………...…109
Лекция. Нелинейное программирование
11.1. Основные понятия……………………………………………………..109
11.2. Безусловный экстремум …………………………………..………….109
11.3. Условный экстремум …………………………………………………111
Контрольные вопросы................................................................112
Перечень задач для решения при усвоении материала …………………. 112
Литература ............................................................................... 128
Вопросы для самопроверки ………………………………….…………. 129
Приложение: Греческий алфавит……………………………….…131
ВВЕДЕНИЕ
Курс «Математика. Исследование операций» занимает ключевую позицию в образовательных программах студентов большинства производственных и экономических специальностей. В процессе его усвоения у студентов должно сформироваться понимание принципов, математических моделей, формулируемых в рамках этих моделей задач и соответствующих методах поиска их решения.Все эти вопросы образуют фундамент, необходимый в современных условиях любому квалифицированному специалисту для решения задач управления различными организационными системами.
Начало развития исследования операций как науки связывают с сороковыми годами двадцатого столетия.Само название дисциплины связано с применением математических методов для управления военными операциями.
Одним из первых исследований является работа Л. В. Канторовича,, Математические методы организации и планирования производства,,, вышедшая в 1939 г., а в зарубежной литературе – вышедшая в 1947 г. работа Дж. Данцинга, посвященная решению экстремальных линейных задач. В 1975 г. Л. В. Канторович стал лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике.
50-е и последующие годы были отмечены широким применением в практику полученных фундаментальных теоретических исследований и связанных с этим переосмыслением потенциальных возможностей теории исследования операций. Важный вклад в развитие новой науки также внесли такие видные ученные, как Дж. Фон. Нейман, Д. Гейл, К. Эрроу, Р. Беллман, Р. Гомори, Е. С. Вентцель, М. К. Гавурин и др.ученные.
Курс лекций разработан на основании рабочих программ для направления подготовки (специальности) 230105.65 «Прикладная информатика (Программное обеспечение ВТ и АС)»,080801.65«Прикладная информатика (в экономике)»,080507.65 «Менеджмент о рганизации»,080105.65 «Финансы и кредит», 080109.65 «Бухгалтерский учет, анализ и аудит».
При изложении содержания тем лекций указываются наиболее важные их элементы с рассмотрением теоретических вопросов и примеров практических задач, а также вопросы для самоконтроля. В заключительной части приводятся многочисленные варианты задач по каждой теме, которые позволят студентам лучше усвоить материал при самостоятельном изучении дисциплины в процессе подготовки к сдаче экзамена или зачета.
В перечнях основной и дополнительной литературы указаны современные учебные и периодические издания, включающие задачи с решениями прикладной направленности.
Лекция. Основы теории принятия решений.
1.1. Общие положения
1.2. Основные понятия системного анализа
1.3. Основные понятия исследования операций
1.4. Постановка задач принятия оптимальных решений
1.5. Методология и методы принятия решений.
Общие положения
Человек наделён сознанием, существо свободное и обречено на выбор решений, стараясь сделать всё наилучшим образом.
Теория принятия оптимальных решений в наиболее общем смысле представляет собой совокупность математических и численных методов, ориентированных на нахождение наилучших вариантов из множества альтернатив и позволяющих избежать их полного перебора.
Так как размерность практических задач, как правило, достаточно велика, а расчеты в соответствии с алгоритмами оптимизации требуют значительных затрат времени, поэтому методы принятия оптимальных решений ориентированы главным образом на реализацию их с помощью ЭВМ.
Практическая потребность общества в научных основах принятия решений возникла с развитием науки и техники.
В XVIII веке началом науки "Теория принятия решений" следует считать работу Жозефа Луи Лагранжа, смысл которой заключался в следующем:
сколько земли должен брать на лопату землекоп, чтобы его сменная производительность была наибольшей.
Оказалось, что утверждение "бери больше, кидай дальше" неверен.
Бурный рост технического прогресса, особенно во время и после второй мировой войны, ставил все новые и новые задачи, для решения которых привлекались и разрабатывались новые научные методы.
Научно-техническими предпосылками становления "Теории принятия решений" являются:
· удорожание "цены ошибки". Чем сложнее, дороже, масштабнее планируемое мероприятие, тем менее допустимы в нем "волевые" решения и тем важнее становятся научные методы, позволяющие заранее оценить последствия каждого решения, заранее исключить недопустимые варианты и рекомендовать наиболее удачные;
· ускорение научно-технической революции техники и технологии. Жизненный цикл технического изделия сократился настолько, что "опыт" не успевал накапливаться и требовалось применение более развитого математического аппарата в проектировании;
· развитие ЭВМ. Размерность и сложность реальных инженерных задач не позволяло использовать аналитические метода.
Эта наука, с одной стороны, стала определенной ветвью других более общих наук (теория систем, системный анализ, кибернетика и т.д.), а с другой, стала синтезом определенных фундаментальных более частных наук (исследование операций, оптимизация и т.д.), создав при этом и собственную методологию.
Экономика теснейшим образом связана с совокупностями объектов, которые принято называть сложными системами.Они характеризуются многочисленными и разнообразными по типу связями между отдельно существующими элементами системы и наличием у системы функции назначения, которой нет у составляющих ее частей.
На первый взгляд каждая сложная система имеет уникальную организацию. Однако более детальное изучение способно выделить общее в системе команд ЭВМ, в процессах проектирования машины, самолета и космического корабля.
В научно-технической литературе существует ряд терминов, имеющих отношение к исследованию сложных систем.
Наиболее общий термин "теория систем". Его основными частями являются:
· системный анализ, который понимается как исследование проблемы принятия решения в сложной системе,
· кибернетика, которая рассматривается как наука об управлении и преобразовании информации.
Кибернетика изучает отдельные и строго формализованные процессы, а
системный анализ - совокупность процессов и процедур.
Очень близкое к термину "системный анализ" понятие - "исследование операций", которое традиционно обозначает математическую дисциплину, охватывающую исследование математических моделей для выбора величин, оптимизирующих заданную математическую конструкцию (критерий).
Системный анализ может сводиться к решению ряда задач исследования операций, но обладает свойствами, не охватываемыми этой дисциплиной.
Однако в зарубежной литературе термин "исследование операций" не является чисто математическим и приближается к термину "системный анализ."
Системный анализ, опираясь на исследование операций, включает:
· постановку задачи для принятия решения;
· описание множества альтернатив;
· исследование многокритериальных задач;
· методы решения задач оптимизации;
· обработку экспертных оценок;
· работу с макромоделями системы.
Основные понятия системного анализа
Системный анализ - наука, занимающаяся проблемой принятия решения в условиях анализа большого количества информации различной природы.
цель системного анализа(к конкретной проблеме)-повышение степени обоснованности принимаемого решения из множества вариантов, среди которых производится выбор, с одновременным указанием способов отбрасывания заведомо невыгодных.
В системном анализе выделяют
· методологию;
· аппаратную реализацию;
· практические приложения.
Методология включает определения используемых понятий и принципы системного подхода.
