Теория игр и исследование операций


Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ






Б.Ю. ЛЕМЕШКО



ТЕОРИЯ ИГР
И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ



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












НОВОСИБИРСК

2013

УДК 519.8
      Л 442


Рецензенты: д-р техн. наук, профессор А.А. Попов', д-р физ.-мат. наук, профессор В.А. Селезнев



   Работа подготовлена на кафедре прикладной математики для студентов IV курса ФПМИ (направление 010400 - Прикладная математика и информатика, направление 010500 - Математическое обеспечение и администрирование информационных систем) и утверждена Редакционно-издательским советом университета в качестве конспекта лекций.




            Лемешко Б.Ю.


Л 442 Теория игр и исследование операций: конспект лекций / Б.Ю. Лемешко. - Новосибирск: Изд-во НГТУ, 2013.- 167 с.

         ISBN 978-5-7782-2198-7

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












УДК 519.8


ISBN 978-5-7782-2198-7

                     © Лемешко Б.Ю., 2013
© Новосибирский государственный

технический университет, 2013

ОГЛАВЛЕНИЕ


1. Введение в исследование операций............................. 5

   1.1. Предмет исследования операций.........................
   1.2. Основные этапы операционного исследования.............
   1.3. Типичные классы задач.................................
   1.4. Некоторые принципы принятия решений в ИО..............
   1.5. Принятие решений в условиях определенности............
   1.6. Методика определения полезности.......................
   1.7. Принятие решений в условиях риска.....................
   1.8. Принятие решений в условиях неопределенности..........
   1.9. Принятие решений в условиях конфликтных ситуаций или противодействия ..............................................

5
6
8
9
10
12
16
17

25

2. Элементы теории игр................................. 26

    2.1. Вводная часть......................................
    2.2. Стратегии. Нормальная форма игры...................
    2.3. Ситуации равновесия................................
    2.4. Антагонистические игры. Игры с нулевой суммой......
    2.5. Нормальная форма...................................
    2.6. Смешанные стратегии................................
    2.7. Теорема о минимаксе................................
    2.8. Вычисление оптимальных стратегий...................
    2.9. Игры с ограничениями...............................
   2.10. Бесконечные игры...................................
   2.11. Игры на квадрате...................................
   2.12. Игры с непрерывным ядром...........................
   2.13. Вогнуто-выпуклые игры..............................
   2.14. Игры с выбором момента времени.....................

26
30
32
33
34
35
38
44
48
50
51
52
56
58

3. Дискретное программирование................................. 66
   3.1. Вводная часть.......................................... 66
   3.2. Некоторые понятия и определения, используемые в методах отсечения................................................... 69
   3.3. Лексикографическая модификация метода последовательного уточнения оценок............................................ 71

3

   3.4. Первый алгоритм Гомори................................
   3.5. Доказательство конечности первого алгоритма Гомори....
   3.6. Второй алгоритм Гомори................................
   3.7. Третий алгоритм Гомори................................
       3.7.1. Построение целочисленного правильного отсечения для третьего алгоритма Гомори..............................
       3.7.2. Построение начальной L-нормальной целочисленной симплексной таблицы ......................................
       3.7.3. Алгоритм........................................
       3.7.4. Выбор X.........................................
   3.8. Доказательство конечности третьего алгоритма Гомори...
4. Дополнительные главы нелинейного программирования..........
   4.1. Классические методы решения задач оптимизации с ограничениями типа равенств........................................
   4.2. Метод множителей Лагранжа.............................
   4.3. Теорема Куна-Таккера..................................
   4.4. Квадратичное программирование.........................
       4.4.1. Условия Куна-Таккера для задачи квадратичного программирования .............................................
       4.4.2. Метод Баранкина и Дорфмана......................
       4.4.3. Метод Франка и Вулфа............................
   4.5. Метод возможных направлений...........................
       4.5.1. Метод выбора возможного направления.............
       4.5.2. Алгоритм метода возможных направлений...........
   4.6. Метод условного градиента.............................
       4.6.1. Правило выбора длины шага.......................
       4.6.2. Алгоритм метода условного градиента.............
       4.6.3. Сходимость алгоритма условного градиента........
       4.6.4. Метод Ньютона...................................
   4.7. Динамическое программирование.........................
Библиографический список......................................

74
83
87
97

98

100
101
103
110
114


114
116
124
129

129
132
141
149
150
153
155
155
156
157
158
159
165

                1. ВВЕДЕНИЕ
                В ИССЛЕДОВАНИЕ ОПЕРАЦИЙ




            1.1. ПРЕДМЕТ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ


   Исследование операций (ИО) - наука, которая занимается разработкой и практическим применением методов наиболее эффективного (или оптимального) управления, в основном организационными системами.
   Предметом исследования операций чаще всего бывают системы организационного типа (организации), которые состоят из большого числа подразделений, взаимодействующих друг с другом. Причем интересы подразделений не всегда согласуются между собой и могут быть противоположными.
   Цель исследования операций - количественное обоснование принимаемых решений по управлению организациями (системами).
   Решение, наиболее выгодное всей организации, называется оптимальным. Решение, выгодное одному или нескольким подразделениям, - субоптимальное.
   Надо заметить, что решение, оптимальное для всей организации, необязательно оптимально для входящих в нее подразделений.
   Исследование операций характеризуется следующими основными особенностями.
   1.   Системный подход к анализу поставленной проблемы. Системный подход (анализ) - основной принцип исследования операций. Любая задача, какая бы ни была частная, рассматривается с точки зрения ее влияния на критерий функционирования всей системы.
   2.   Для исследования операций характерно, что при решении каждой новой проблемы возникают все новые задачи. Наибольший эффект

5

достигается при непрерывном исследовании, обеспечивающем преемственность при переходе от одной задачи к другой.
   3.    Стремление к нахождению оптимального решения поставленной задачи, хотя определить оптимальное решение не всегда возможно из-за ограничений, накладываемых имеющимися в наличии ресурсами (или уровня развития современной науки). В этом случае довольствуются субоптимальным решением.
   4.    Один из создателей исследования операций - Т. Саати - определил эту пару как «искусство давать плохие ответы на те практические вопросы, на которые делаются еще худшие ответы другими методами».
   5.    Исследования всегда проводятся комплексно по многим направлениям. Для проведения такого исследования системы организационного типа создается группа специалистов различного профиля из разных областей (инженеры, экономисты, психологи ит. д.). Задача такой группы - комплексное исследование всего множества факторов, влияющих на решение проблемы, и использование идей и методов различных наук.


            1.2.       ОСНОВНЫЕ ЭТАПЫ ОПЕРАЦИОННОГО ИССЛЕДОВАНИЯ


   Любое операционное исследование, при всем возможном многообразии конкретных работ по исследованию операций, проходит следующие этапы:
   1) постановка задачи;
   2) построение математической модели;
   3) нахождение метода решения (выбор, разработка);
   4) проверка и корректировка модели;
   5) реализация найденного решения на практике.
   Постановка задачи. Чрезвычайно ответственный этап операционного исследования. Первоначально задачу формулируют с точки зрения заказчика. Такая постановка никогда не бывает окончательной. Во время анализа исследуемой системы постановка всегда уточняется. На этом этапе роль исследования операций состоит в тщательном анализировании объекта, изучении множества факторов, влияющих на результаты исследования процесса.


6

    Формализация задачи. В самом общем случае математическая модель задачи имеет вид
max Е - max f (х, у )
при
gi⁽х, У⁾ ^ bi, i ⁻ ¹ т,
где Е - f (х, у) - целевая функция (показатель качества или эффективность системы);
   х - вектор управляемых переменных;
   у - вектор неуправляемых переменных;
   gᵢ - функция потребления i-го ресурса;
   bᵢ - величина i-го ресурса.
    Нахождение метода решения. Для нахождения оптимального решения х₃ₚₜ в зависимости от структуры целевой функции и ограничений применяют те или иные методы теории оптимальных решений.
    • Линейное программирование, если /ng- линейные функции.
    •     Нелинейное программирование, если fftg- нелинейные функции.
    •    Динамическое программирование, если f имеет специфическую структуру, т. е. является аддитивной или мультипликативной функци                                          п
ей от переменных х и у , например, f (х, у) - ^ fᵢ (xᵢ, у,).
                                          i -I
   •  Геометрическое программирование, если целевая функция f (х) = Е Citf⁴--' хтт ,а gi⁽х ⁾ ^ 1   i
    •     Стохастическое программирование, когда у - случайная величина, а вместо функции f (х, у) рассматривается ее математическое ожидание Еу [ f (х, у )].
    •     Дискретное программирование, если на х и у наложено требование дискретности (например, целочисленности).
    •     Эвристическое программирование применяют при решении тех задач, в которых точный оптимум найти алгоритмическим путем невозможно из-за огромного числа вариантов.

7

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


            1.3. ТИПИЧНЫЕ КЛАССЫ ЗАДАЧ


   По содержательной постановке наиболее часто возникают следующие типичные классы задач.
   •    Задачи управления запасами. Такие задачи обладают некоторой особенностью: с увеличением запасов возрастают расходы на хранение, но уменьшаются потери из-за возможной их нехватки. (Логистика)
   •    Задачи распределения ресурсов. Такие задачи возникают, когда существует определенный набор работ, которые необходимо выполнить, а наличных ресурсов для их выполнения должным образом не хватает.
   •    Задачи ремонта и замены оборудования появляются в тех случаях, когда работающее оборудование изнашивается, устаревает и со временем подлежит замене.
   •    Задачи массового обслуживания рассматривают вопросы образования и функционирования очередей, с которыми приходится сталкиваться в повседневной практике, при управлении технологическими процессами, в линиях связи и компьютерных сетях.
   •    Задачи календарного планирования, или составления расписания.
   •    Задачи сетевого планирования и управления. Здесь рассматриваются соотношения между сроком окончания крупного комплекса операций и моментами начала всех операций комплекса. Они актуальны при разработке сложных и дорогостоящих проектов.
   •    Задачи выбора маршрута, или сетевые задачи. В основном встречаются при исследовании разнообразных процессов на транспорте и в системах связи (компьютерные сети). Часто задачи оказываются комбинированными.


8

            1.4. НЕКОТОРЫЕ ПРИНЦИПЫ ПРИНЯТИЯ РЕШЕНИЙ В ИО


   В процессе принятия решений всегда возникают многочисленные трудности.
   1.    Большое количество критериев, которые не всегда согласованы между собой. Например, требования максимальной надежности и минимальной стоимости; или требование максимальной мощности изделия при минимальных габаритах. Такие критерии противоречивы. Поэтому часто возникает задача выбора некоторого компромисса между такими требованиями.
   2.    Высокая степень неопределенности, которая обусловлена недостаточной информацией для обоснованного принятия решения.
   Любой процесс принятия решения включает следующие элементы.
   •    Цель. Необходимость принятия решения определяется целью или несколькими целями, которые должны быть достигнуты.
   •    Лицо, принимающее решение, должно нести ответственность за последствия этих решений.
   •    Наличие альтернативных решений (различных вариантов достижения целей).
   •    Наличие внешней среды (совокупности внешних факторов, влияющих на исход решения).
   •    Исходы решений, т. е. результаты, к которым приходят в результате реализации принятых решений.
   •    Правила выбора решений (решающие правила). Эти правила позволяют определить предпочтительные в смысле выбранного критерия решения. Решающее правило отражает информированность лица, принимающего решение, о возможных исходах выбранных решений, а также предпочтительность тех или иных исходов.
   Теория принятия решений использует различные процедуры, позволяющие формализовать предпочтения, т. е. выразить их в единой количественной мере. Основой для таких процедур служит теория полезности, разработанная Дж. фон Нейманом и О. Моргенштерном. Ее математическая основа - система аксиом, в которых утверждается, что существует некоторая мера ценности, позволяющая упорядочить результаты решений. Эта мера называется функцией полезности решений или полезностью.

9

   В зависимости от условий внешней среды и степени информированности лица, принимающего решение, существует следующая кла-сификация задач принятия решений:
   •     в условиях определенности;
   •     в условиях риска;
   •     в условиях неопределенности;
   •     в условиях конфликтных ситуаций, или противодействия (активного противника).



            1.5. ПРИНЯТИЕ РЕШЕНИЙ
            В УСЛОВИЯХ ОПРЕДЕЛЕННОСТИ



   Характеризуется однозначной, или детерминированной, связью между принятым решением и его исходом. Основная трудность - наличие многих критериев, по которым следует сравнивать исходы.
   В таких ситуациях возникает задача принятия решения при так называемом «компромиссном критерии». Пусть имеется совокупность критериев F₁ (х), F₂ (х), ..., Fₙ (х), х е X . Пусть для определенности все F (х) ^ max , тогда можно рассмотреть следующие случаи.
   1.     Если все критерии измеряются в одной шкале, то обобщенный критерий F)(х) можно записать в виде взвешенной суммы критериев
n       n
Fo(*) = Х wf^ ),£ wᵢ ₌ 1, i-|             i-|


где wᵢ - вес соответствующего критерия. В этом случае необходимо найти
max Fₒ (х) .
х е X


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

min Fₒ( х ) - min хе X      х g X

i-I

F( х*)- Fi (х) |f( *)

n

Z Wi

10

где
fAх* ) = max Fₜ(x), f(х* ) * 0,
                           х e X
т.   e. требуется свести к минимуму взвешенную сумму отклонений каждого критерия от его максимального значения.
   При таком формировании обобщенного критерия можно добиться высоких показателей по одним критериям за счет ухудшения показателей по другим.
   2.     Часто требуется, чтобы значения некоторых частных критериев не оказались меньше предельно допустимых значений F (х) > F доп . Допустим, что по каждому критерию определены значения F-доп, i = 1, п. В таком случае формируемый обобщенный критерий может быть дополнен системой ограничений и задача принимает следующий вид:
п
max F₀ (х ) = max ^ wᵢFᵢ (х )
                    хе X      х e X -=1
при
F( х) > F^ₒₙ,i = 1л.
   3.     Бывает, что критерии упорядочены по предпочтению F₁(х) > > F₂ (х) > ... > Fₙ (х), тогда задача отыскания оптимального решения может быть записана следующим образом:
max F₁ (х )
х e X
при
F2( х) > /-.


Fn (х) > F оп.
    4.     Бывают ситуации, когда критерии F₁(х), F₂(х), ..., Fₙ(х) могут принимать только два значения (0 или 1): Fᵢ(х) = 1, если i-я цель достигнута, Fᵢ (х) = 0 - в противном случае.

11

   Тогда обобщенный критерий может быть образован логическим объединением отдельных критериев:
   а)     в виде конъюнкции критериев Fᵢ (X), если общая цель операции состоит в выполнении всех целей одновременно, т. е.
п
Fₒ( X ) П Fi( X);
i-I

   б)     в виде дизъюнкции критериев, когда общая цель достигается, если достигается хотя бы одна частная цель, т. е.
п
Fo(X) - 1 -П(1 -Fi(X)) . i-1


            1.6. МЕТОДИКА ОПРЕДЕЛЕНИЯ ПОЛЕЗНОСТИ


   Очень часто в реальных условиях критерии носят качественный характер и не могут быть выражены в количественной мере. Но решение надо принимать, каким-то образом проранжировав критерии. Это также соответствует принятию решения в условиях определенности. Для принятия решений необходимо установить предпочтения различных критериев (меру полезности) для лица, принимающего решения (Р. Акофф, М. Сасиени).
   Применение теории полезности основывается на следующих аксиомах.
   1.     Результат xᵢ оказывается предпочтительнее Xj тогда и только тогда, когда U(Xᵢ) > U (Xⱼ.), где U(xᵢ) и U(Xj )- полезность результатов xᵢ и Xj соответственно.
   2.    Транзитивность. Если xᵢ > Xj, a Xj > Xₖ, то U(xᵢ)> U (Xₖ ).
   3.    Линейность. Если некоторый результат x представлен в виде
x — (1 - a)x₁ + аx₂,
то полезность его
U(x) - (1 -a)U(x₁) + аU(x₂).

12