Теория игр для математического решения задач

2.3 Исследование операций

Скажем несколько слов об основных методологических принципах Исследования операций:

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

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

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

Назовём теперь основные этапы исследования операций:

· Содержательная постановка задачи

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

· Решение задачи на модели

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

· Построение конкурирующего алгоритма

· Реализация решения

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

Общая задача линейного программирования заключается в отыскании вектора(х1, х2,..., хn) максимизирующего (минимизирующего) критерий оптимальности (функцию цели задачи)

при ограничениях линейного типа в виде равенств:

в виде неравенств:

и ограничениях на переменные состояния:

Эта задача при наличии двух (или трех) переменных имеет наглядноегеометрическое представление.

Пусть целевая функция имеет вид . Если на плоскости переменных и принимает некоторое постоянное значение то определяемое последним соотношением множество точек плоскости (,) является линией равного значения уровня (линией уровня) целевой функции. Причем, при = = 0 эта линия «сжимается» в точку (рис. 1), при имеем и линия равного уровня является прямой линией, проходящей через точки и

Рис. 1 - Геометрическое представление целевой функции

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

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

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

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

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

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

Довольно часто отправным моментом построения моделей служило сходство с моделями, используемыми другими науками. Таким образом, новые теоретические направления были развиты в основном в послевоенное время. Основы теории ведения боевых действий заложены Ланчестером в 1916г., и, хотя во время войны математические аспекты этой теории исследовались достаточно интенсивно, непосредственного применения при разработке операций военного времени она не нашла; действительно, вплоть до 1954г. Эта теория не была достаточно проверена.

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

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

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

Пример задачи о производстве красок Задача фирмы Reddy Mikks Небольшая фабрика фирмы Reddy Mikks изготовляет два вида красок: для внутренних (I) и наружных (E) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта-А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т соответственно. Расходы А и В на 1 т соответствующих красок и максимально возможный запас приведены в таблице.

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме этого установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. долл. для краски Е 2 тыс. долл. для краски I.

Какое количество краски каждого вида должна производить фабрика, чтобыдоход от реализации продукции был максимальным?

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

Процесс построения математической модели для решения поставленной задачи можно начать с ответов на три следующие вопроса:

1. Для определения, каких величин должна быть построена модель?

2. Какие ограничения должны быть наложены на переменные, чтобывыполнялись условия, для моделируемой системы?

3. В чем состоит цель, для достижения которой из всех допустимых значенийпеременных нужно выбрать те, которые будут соответствовать оптимальному(наилучшему) решению задачи?

Отвечая на поставленные вопросы, сформулируем суть проблемы. Фирме требуется определить объемы производства (в тоннах) каждой из красок, который максимизирует доход (в тысячах долларов) от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов.

Введем переменные: так как нужно определить объемы производства каждого вида краски, то переменными в модели являются

xE - суточный объем производства краски Е (в тоннах)

xI - суточный объем производства краски I (в тоннах).

Так как стоимость 1 т краски Е равна 3 тыс. долл., суточный доход от ее продажи составит 3 xE тыс. долл. Аналогично доход от реализации xI тонн краски I составит 2 xI тыс. долл. в сутки. При допущении независимости объемов сбыта каждой из красок можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения xЕ и xI, максимизирующие величину общего дохода Ограничения: При решении рассматриваемой задачи должны быть учтены ограничения на расход исходных продуктов и спрос на изготовляемые краски. Ограничение на расход исходных продуктов можно записать следующим образом:

Это приводит к следующим двум ограничениям: (для А) (для В) Ограничения на величину спроса красок имеют вид

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

Что определяет линейный характер построенной модели? С формальных позиций данная модель является линейной потому, что все входящие в нее функции (ограничения и целевая функция) линейны. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности.

1 Пропорциональность означает, что вклад каждой переменной хЕ и хI вцелевую функцию прямо пропорционален этим переменным.

2 Аддитивность заключается в том, что целевая функция представляет собойсумму вкладов от различных переменных. Однако если фирма производит дваконкурирующих вида продукции, увеличение сбыта одного из которыхотрицательно сказывается на объеме реализации другого, то такая модель необладает свойством аддитивности.

Задача о пищевом рационе.

Пусть имеется 4 вида продуктов: . Стоимость единицы каждого продукта . Согласно этим условиям, требуется составить пищевой рацион, в котором должны содержаться белки, в количестве не менее единиц, углеводов - не менее единиц, жиров - не менее единиц.

Составим таблицу.

() - какие то определённые числа. Первый индекс указывает номер продукта, второй - номер элемента (белки, жиры углеводы). Требуется составить пищевой рацион таким образом, чтобы условия по белкам, жирам и углеводам были выполнены. Математическая модель будет выглядеть следующим образом: - количества продукции входящих в рацион. Показатель эффективности L - стоимость рациона (эту величину требуется минимизировать). Запишем линейную зависимость . Учитывая, что в одной единице продукта содержится единиц белка, в единицах - единиц белка, в единицах продукта содержится единиц белка и т.д. получим три неравенства: эти линейные неравенства

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

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

Математическую форму поставленной задачи изучим на следующем числовом примере.

Допустим, что предприятие выпускает единиц продукции вида и единиц продукции вида . Для этого потребуется единиц сырья (на основании таблицы 2.5). Так как в наличии имеется всего 19 единиц сырья , то должно выполняться неравенство . Неравенство, а не точное равенство появляется в связи с тем, что максимальный доход может быть достигнут предприятием и в том случае, когда запасы сырья вида используются не полностью.

Аналогичные рассуждения, проведённые для остальных видов сырья, позволяют записать следующие неравенства:

(сырьё )

(сырьё )

(сырьё ).

При этих условиях доход , получаемый предприятием, составит .

Таким образом, математически рассматриваемую экономическую ситуацию можно сформулировать так.

Дана система четырёх линейных неравенств и линейная целевая функция

Требуется среди неотрицательных решений системы (4) выбрать такое, при котором целевая функция принимает наибольшее значение (максимизировать).

Рассмотрим на примере ещё несколько игр. Игра Морро. Игроки показывают одновременно 1 или 2 пальца и в тоже время называют число. Если число, названное одним игроком, совпадает с общим числом пальцев, то игрок получит от своего противника выигрыш, равный этому числу. Если оба угадают верно, то чистый платёж будет равен нулю.

Оборона города («Игра полковника Блотто»)

Полковник Блотто имеет m полков, а его противник - n полков. Противник защищает 2 позиции. Позиция будет защищена полковником, если на ней наступающие полки окажутся в численном превосходстве. Противоборствующим сторонам тре6уется распределить полки между двумя позициями. Если игрок 1 (полковник) имеет на позиции больше полков, то выигрыш равен числу полков противника плюс один (занимаемая позиция равносильна захвату одного полка). Если у противника (игрока 2) больше полков на позиции, то игрок 1 таким образом теряет свои полки на этой позиции и ещё единицу. Если обе стороны имеют одинаковое количество полков на позиции, то имеет место ничья. Посмотрим на стратегии игроков.

Игрок 1 имеет следующие стратегии:

- послать все полки на первую позицию

- послать полков на первую позицию, а полков - на вторую позицию и т.д.

- послать все полки на вторую позицию

Игрок 2 имеет такие стратегии:

- послать все полки на первую позицию

- послать полков на первую позицию, а полков - на вторую позицию и т.д.

- послать все полки на вторую позицию

Пусть m=4, n=3. Тогда рассмотрев всевозможные ситуации, получим матрицу выигрышей, для этой игры

Основная задача линейного программирования.

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

и обращали бы в максимум линейную функцию этих переменных: . Если функцию L требуется обратить в минимум, то для этого нужно изменить знак этой функции (т.е. максимизировать не L, а ). Рассмотрим конкретный пример, объясняющий эту позицию.

Пример. Пусть требуется найти неотрицательные значения переменных , удовлетворяющих ограничениям - неравенствам и обращающие в максимум линейную функцию . Приведём условия в фигурной скобке к стандартному виду. Получим (1). А теперь обозначим левые части неравенств через y1 и y2 => (2). Из условий (1) и (2) следует что переменные y1 и y2 тоже должны быть неотрицательными.

Выводы

1 Представлены основные понятия теории игр и исследования операций.

2 Приведены примеры игр в чистой и смешанной стратегиях (задача Борьба двух предприятий за рынок продукции региона»).

3 Представлена основная теорема Теории игр (с доказательством) и использован принцип сведения теоретико-игровой модели к ЗЛП (задаче линейного программирования)

4 В работе приведена серия задач, связанных с теорией игр и исследованием операций (в частности - основная задача линейного программирования).

5 Раскрыто современное понятие «Принятие решений» на основе математических методов и моделей Теории игр

Литература

1. Борисова С.П., Власова И.А., Коваленко А.Г. Теория игр и исследование операций - Издательство «Самарский университет», 2006.

2. Берж Л. Общая теория игр нескольких лиц - М.: ГИФМЛ, 1961. 327.стр.

3. Барсов А.С. Линейное программирование в технико-экономических задачах. М.: Наука, 1964. - 278 с.

4. Воробьёв Н.Н. Матричные игры - М.: Физматгиз, 1961.

5. Власов Д.А., Монахов Н.В., Монахов В.М. Математические модели и методы внутримодельных исследований - Издательство «Альфа», 2007.

6. Вентцель Е.С. Исследование операций. Задачи, принципы, методология - М.: Дрофа, 2006. 208 страниц.

7. Гасс С. Линейное программирование (методы и приложения) - М., 1961.

8. Гамецкий А.Ф., Слободенюк В.А., Спиридонова Г.В. Теория игр, исследование операций - Издательство КГУ, 1987.

9. Громенко Г.Н. Теория игр - М.: Издательство МГОУ, 2005. 198 стр.

10. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр - М.: Наука, 1989. 310 стр.

12. Давыдов Э.Г. Исследование операций: учебное пособие - М., 1990.

13. Зайченко Ю.П. Исследование операций - Киев, 1979. 278 стр.

14. Краснов М.Л., Киселёв А.И. Высшая математика, том 5 - М.: Издательство ЛКИ, 2007. 300 стр.

15. Конюховский П.В. Математические методы исследования операций в экономике - СПб.: Издательство СПбГУ. 394 стр.

16. Карлин С. Математические методы в теории игр, программировании и экономике - М., 1964. 400 стр.

17. Льюис Р.Д., Райфа Г. Игры и решения. - М.: ИЛ, 1961 285 стр.

18. Лагунов В.Н. Игры преследования и введение в теорию игр. Т., 1993

19. Мак-Кинси Дж. Введение в теорию игр. - М.: Физматгиз, 1960.

20. Малыхин В.И.. Статкус А.В. Теория принятия решений. МИУ, М., 1989. 382 стр.

21. Мулен Э Теория игр с примерами из математической экономики - М.: Мир 1985.

22. Нейман Дж. Фон, Моргенштерн О. Теория игр и экономическое поведение - М.: Издательство «Наука», 2007. 420 стр.

23. Нестеров Е.П. Транспортные задачи линейного программирования - М.: Транспорт 1971. 216 стр.

24. Оуэн Г. Теория игр - М.: Издательство ЛКИ, 2007. 232 стр.

25. Петросян Л.А. Теория игр - М.: Издательство «Высшая школа», 1998.

26. Протасов И.Д. Теория игр и исследование операций - М.: Издательство «Гелиос» АРВ, 2006. 368 страниц.

27. Парфёнов Г.Н. Принципы теории игр - Издательство СПбГУ, 2001.

28. Секацкий В.В., Худякова Г.И. Элементы теории матричных игр в курсе математики.// Ярославский педагогический вестник. 2000, №1(23).

29. Терехов Л.Л. Применение математических методов в экономике - М.: Статистика, 1968. 188 стр.

30. Таха Х. Введение в исследование операций - М.: издательство «Вильямс», 2001.

31. Фатхутдинов Р.А. Управленческие решения - М.: нфра 2007.

32. Хорн Р., Джонсон Ч. Матричный анализ - М.: Мир, 1989. 427 стр.

33. Хазанова Л.Э. Математические методы в экономике - М.: издательство БЕК, 2002. 144 стр.

34. Шикин Е.В. От игр к играм - М.: УРСС, 1997. 149 стр.

35. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы, приложения - М.: «Наука», 1969. 364 стр.

36. Яновская Е.Б. Антагонистические игры // Проблемы кибернетики. - М.: Наука, 1978. С. 221 - 246.

Размещено на Allbest.ru