- •Математические методы исследования операций и теории иГр
- •Введение
- •Глава 1. Задачи линейного программирования
- •1. Постановка задачи линейного программирования (злп)
- •2. Графический метод решения злп
- •3. Симплекс – метод решения злп
- •Метод искусственного базиса
- •Двойственные злп
- •Двойственный симплекс-метод
- •Алгоритм двойственного симплекс-метода.
- •Метод ветвей и границ решения задачи цлп
- •Алгоритм метода ветвей и границ
- •Оптимальность по Парето
- •Множество Парето
- •Постановка задачи
- •Метод идеальной точки
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 2. Теория игр
- •1. Основные понятия теории игр
- •Принцип доминирования
- •2. Задачи теории игр и линейное программирование
- •3. Игры с природой
- •Применение матричных игр в прикладных задачах
- •Переговоры о заключении контракта между профсоюзом и администрацией
- •Локальный конфликт
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Имитационное моделирование
- •Основные понятия
- •Типы имитационных моделей.
- •Принципы построения дискретных имитационных моделей
- •Метод Монте-Карло (метод статистических испытаний)
- •Применение имитационных моделей в системах массового обслуживания
- •Вопросы для повторения.
- •Глава 4. Сетевое планирование
- •1. Сетевой график
- •Оптимизация пути на сети
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Заключение
- •Библиографический список
- •Оглавление
- •3 94026 Воронеж, Московский просп., 14
ФГБОУ ВПО «Воронежский государственный технический университет»
А.В. Ряжских
А.Н. Шелковой
Математические методы исследования операций и теории иГр
Утверждено Редакционно-издательским советом университета в качестве учебного пособия
Воронеж 2015
УДК 519.617 (075.8)
Ряжских А.В. Математические методы исследования операций и теории игр: учеб. пособие [Электронный ресурс]. – Электрон. текстовые, граф. данные (3,2 Мб) / А.В. Ряжских, А.Н. Шелковой. Воронеж: ФГБОУ ВПО «Воронежский государственный технический университет», 2015. – 1 электрон. диск (CD-ROM). – Систем. требования: ПК 500 и выше ; 256 Мб ОЗУ ; Windows XP ; MS Word 2007 или более поздняя версия ; 1024×768 ; CD-ROM ; мышь. Загл. с экрана.
Настоящее учебное пособие состоит из четырёх глав: первая глава посвящена задачам линейного программирования, во второй главе рассматриваются вопросы теории игр, в третьей главе – имитационное моделирование, в четвёртой главе рассматриваются задачи сетевого планирования.
Издание соответствует требованиям Федерального государственного образовательного стандарта высшего профессионального образования по специальности 090303.65 «Информационная безопасность автоматизированных систем», дисциплине «Исследование операций и теория игр».
Табл. 2. Ил. 24. Библиогр.: 23 назв.
Рецензенты: кафедра нелинейных колебаний
Воронежского государственного уни-
верситета
(д-р физ.-мат. наук, проф. А.Г. Баскаков);
д-р техн. наук, проф. О.Н. Чопоров
Ряжских А.В., Шелковой А.Н., 2015
Оформление. ФГБОУ ВПО «Воронежский
государственный технический университет», 2015
Введение
Это учебное пособие написано на основе лекций, читаемых одним из авторов на факультете информационных технологий и компьютерной безопасности ВГТУ по курсу «Исследование операций и теория игр».
В пособии изложены необходимые основы математического аппарата и примеры его использования: задачи линейного программирования, вопросы теории игр, имитационное моделирование, задачи сетевого планирования. Такой объём знаний актуален сегодня для студентов, получающих образование по специальностям в области защиты информации, и соответствует требованиям государственных стандартов по этим специальностям.
Изложение материала проведено почти без доказательств – основной упор сделан на приобретение навыков использования математического аппарата. Каждый раздел сопровождается решением характерных задач и соответствующих приложений. Пособие содержит также подборку вопросов для повторения, задач и упражнений для самостоятельного решения по каждой теме.
Глава 1. Задачи линейного программирования
1. Постановка задачи линейного программирования (злп)
Линейное программирование - наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений. Математическое выражение целевой функции и её ограничений называется математической моделью задачи.
В общем виде ЗЛП ставится следующим образом (общая ЗЛП): найти максимум (минимум) функции
(1)
при ограничениях
(2)
где ( ) - управляющие переменные или решения задачи
(1)-(2), аij, bi, сj, i= , j= , - заданные числа (параметры), F-целевая функция или критерий эффективности (оптимальности) задачи.
Функция (1) - линейная, ограничения (2) - линейные. Задача содержит n переменных и m ограничений.
Решить ЗЛП - это значит найти значения управляющих переменных xj, j= , удовлетворяющих ограничения (2), при которых целевая функция (1) принимает экстремальное значение.
Основной (канонической) ЗЛП называется задача, состоящая в определении максимума целевой функции при ограничениях, заданных равенствами и .
Допустимым решением (планом) ЗЛП называется вектор X=(x1, x2, …, xn), удовлетворяющий системе ограничений (2).
Множество допустимых решений образует область допустимых решений (ОДР).
Допустимое решение Х*= , при котором целевая функция достигает своего экстремального значения, называется оптимальным решением ЗЛП.