Коваленко А.Г.

Самостоятельные работы студентов

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

(для студентов технических и экономических специальностей)

Алматы 2009

Содержание

1. Введение 4

1.1. Основные методологические принципы 5

1.2. Основные определения 6

1.3. Этапы моделирования 7

2. О принципах принятия решений 9

2.1. Принятие решений в условиях неопределенности критерия. 9

Самостоятельная работа №1. 14

2.2. Принятие решения в условиях неопределенности состояния окружающей среды 19

Самостоятельная работа №2 24

3. Задачи выпуклого векторного программирования. 27

3.1. Некоторые сведения выпуклого анализа 27

3.2. Понятие оптимальности по Слейтеру и Парето 32

3.3. Возможные (допустимые) и подходящие направления. 33

3.4. Задача выпуклого векторного программирования с ограничениями типа неравенства. Поиск подходящих направлений. 34

Самостоятельная работа №3. 37

38

3.4. Теорема Куна–Таккера для задачи выпуклого векторного программирования 38

Самостоятельная работа № 4. 40

4. Некоторые задачи теория игр 41

4.1. Анализ матричных антагонистических игр двух игроков . 42

Самостоятельная работа № 5. 48

4.2. Анализ матричных игр двух игроков с нулевой суммой в смешанных стратегиях. 49

Самостоятельная работа №6 52

4.3. Биматричные неантагонистические игры. 52

Самостоятельная работа № 7. 56

4.4. Взаимосвязь равновесий по Нешу и Парето в играх. 56

Самостоятельная работа № 8. 58

4.5. Динамические игры с полной информацией 58

Самостоятельная работа № 9 60

5. Задачи дискретного программирования. 63

5.1. Методы отсечения для решения задач целочисленного линейного программирования. 63

Самостоятельная работа № 10. 66

5.2. Комбинаторные методы решения задач целочисленного линейного программирования. 68

5.3. Алгоритм Ленд–Дойг. 69

Самостоятельная работа № 11. 73

5.4. Метод ветвей и границ для решения задачи о коммивояжере. 73

Самостоятельная работа № 12. 81

6. Транспортные задачи линейного программирования 86

6.1. Транспортная задача в сетевой постановке 86

Самостоятельная работа 13. 92

6.2. Транспортная задача в матричной постановке. 93

Самостоятельная работа 14. 101

7. Динамическое программирование и потоки в сетях 104

7.1. Задача оптимизации многошаговых процессов, задача о ранце. 104

Самостоятельная работа 15. 108

7.2 .Задача отыскания кратчайшего расстояния в сети между парами вершин 109

Самостоятельная работа 16. 120

7.2. Задача о максимальном потоке в сети. 121

Самостоятельная работа 17. 129

Литература. 132

1. Введение

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

Большой вклад в развитие и формирование новой науки внесли зарубежные ученые Р.Акоф, Р. Беллман, Г. Данциг, Г. Кун, Т. Саати, Р. Черчмен, А. Кофман, Р. Фор и др.

Важная роль в создании математического аппарата и развития ряда направлений исследования операций принадлежит советским ученым Л.В Канторовичу, Б.В. Гнеденко, Н.П. Бусленко, Д.Б. Юдину, Н.П. Федоренко и др.

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

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

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

Впоследствии общее определение исследования операций было сведено к следующему:

Исследование Операций – это наука о методах принятия и обоснования решений при проведении целенаправленных действий (операций).

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

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

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

1. Формализация исходной проблемы

2. Построение математической модели

3. Выбор критерия

4. Решение задачи с использованием математического аппарата

5. Проверка адекватности модели

6. Реализация решения

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