ПРЕДЕСЛОВИЕ

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

Книга написана на основе лекций, прочитанных на механико-математическом факультете и на факультете экономики и управления Самарского государственного университета.

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

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

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

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

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

Глава 5 посвящена задачам дискретного программирования. В этой главе рассмотрены классические методы решения задач целочисленного программирования: метод Гомори и метод ветвей и границ. В книге также показано применение метода ветвей и границ к решению задачи о ранце и к решению задачи о коммивояжере. Для каждого рассмотренного случая приведены примеры задач с решениями. В конце главы представлены 4 лабораторные работы с вариантами заданий для самостоятельного решения.

Классическая транспортная задача, представленная в главе 6, рассмотрена в сетевой и матричной постановках. Для её решения использованы численные методы поиска начального базисного решения и метод потенциалов. Все методы сопровождены примерами задач с решениями. В конце раздела предложены две лабораторные работы с вариантами для самостоятельного решения.

В главе 7 динамическое программирование представлено двумя задачами: задачей о максимальном потоке в сетях и задачей нахождения кратчайшего расстояния на графе. Для решения первой задачи использован алгоритм Беллмана-Калабы, для второй задачи алгоритмы Беллмана-Калабы, Флойда и Дейкстры. Все методы содержат примеры задач с решениями. В конце главы представлены 3 лабораторные работы с вариантами заданий.

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

Для решения задач теории игр и исследования операций с успехом могут быть применены современные информационные технологии. Поэтому при выполнении лабораторных работ настоящего пособия студенты могут использовать MS Excel, Maple, MatCad, среду программирования Delphi, Си++, пакеты прикладных программ StatGraphiс и др.

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

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

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

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