Игровые модели

Теоретические основы игровых моделей. Предмет, задачи, терминология и классификация игр. Смешанные стратегии в матричных играх. Аналитическое решение задачи с помощью игровых моделей. Решение задачи теории игр с помощью MS Excel "Поиск решения".

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 18.11.2016
Размер файла 505,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

Структура работы: Курсовой проект состоит из 2-х глав, имеется также список использованных источников, состоящих из 8 источников.

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

Во 2-ой главе представлены результаты расчета и анализа игровых моделей в MS Excel и в разработанной программе.

Объем проекта составляет 34 страниц.

1. Теоретические основы игровых моделей

1.1 История развития теории игр

Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior). Эта область математики нашла некоторое отражение в общественной культуре.

В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр, а в 2001 по мотивам книги был снят фильм «Игры Разума». Большим вкладом в применение теории игр стала работа Томаса Шеллинга, нобелевского лауреата по экономике 2005 г. «Стратегия конфликта». Т. Шеллинг рассматривает различные «стратегии» поведения участников конфликта. Эти стратегии совпадают с тактиками управления конфликтами и принципами анализа конфликтов в конфликтологии (это психологическая дисциплина) и в управлении конфликтами в организации (теория менеджмента). В психологии и других науках используют слово «игра» в других смыслах, нежели чем в математике. Некоторые психологи и математики скептически относятся к использованию этого термина в других смыслах, сложившихся ранее.

Понятие игры встречается в концепции Эрика Бёрна «Игры, в которые играют люди, люди, которые играют в игры». Это сугубо психологические игры, основанные на транзакционном анализе. Понятие игры у Й. Хёзинга отличаться от интерпретации игры в теории конфликтов и математической теории игр.

Математическая теория игр сейчас бурно развивается, рассматриваются динамические игры. Однако, математический аппарат теории игр сложен и дорог.

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

1.2 Предмет и задачи теории игр

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

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

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

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

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

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

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

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

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

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

Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, “удивление” его чем-то совершенно новым, непредвиденным.

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

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

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

1.3 Терминология и классификация игр

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

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

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

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

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

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

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

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

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

Всякая игра состоит из отдельных партий.

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

Ходом называется выбор и реализация игроком одного из допустимых вариантов поведения.

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

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

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

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

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

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

По виду функции выигрыша игры делятся на матричные, биматричные, непрерывные, выпуклые, сепарабельные и др.

Матричной игрой (при двух участниках) называется игра, в которой выигрыши первого игрока (проигрыши второго игрока) задаются матрицей.

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

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

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

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

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

1.4 Решение задач игр с природой

Рассмотрим игры с природой на примере следующей задачи. Необходимо закупить уголь для обогрева дома. Количество хранимого угля ограничено и в течение холодного периода должно быть, полностью израсходовано. Предполагается, что неизрасходованный зимой уголь в лето пропадает. Покупать уголь можно в любое время, однако летом он дешевле, чем зимой. Неопределенность состоит в том, что не известно, какой будет зима: суровой, тогда придется докупать уголь, или мягкой, тогда часть угля может остаться неиспользованной. Очевидно, что у природы нет злого умысла и она ничего против человека «не имеет». С другой стороны, долгосрочные прогнозы, составляемые метеорологическими службами, неточны и поэтому могут использоваться в практической деятельности только как ориентировочные при принятии решений. Имеются следующие данные о количестве и ценах угля, необходимого зимой для отопления дома (табл. 1). Вероятности зим: мягкой - 0,35; обычной - 0,5; холодной - 0,15.

Таблица 1

Количество и цена угля

Зима

Количество тонн угля

Средняя цена за 1 т, тг

Мягкая

4

7

Обычная

5

7,5

Холодная

6

8

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

Пользуясь исходными данными, строим матрицу игры. Стратегиями игрока 1 (человек) являются различные показатели количества тонн угля, которые ему, возможно, следует купить. Состояниями природы выступают вероятности видов зимы.

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

Следовательно, расчет платы за уголь будет 5 6 - при заготовке, и зимой 8 1. Аналогично производятся расчеты при других сочетаниях.

В итоге получим следующую платежную матрицу в игре с природой (табл. 2).

Таблица 2

Платежная матрица

Вероятность

Зима

0,35

0,5

0,15

Мягкая

Обычная

Холодная

Мягкая(4т)

-(4 6)

-(4 6 + 1 7,5)

-(4 6 + 2 8)

Обычная(5т)

-(5 6)

-(5 6 + 0 7,5)

-(5 6 + 1 8)

Холодная(6т)

-(6 6)

-(6 6 + 0 7,5)

-(6 6 + 0 8)

Произведем расчет ожидаемой средней платы за уголь (табл. 3).

Таблица 3

Средняя плата за уголь

Зима

Средняя ожидаемая плата

Мягкая

-(24 0,35 + 31,5 0,5 + 40 0,15) = -30,15

Обычная

-(30 0,35 + 30 0,5 + 38 0,15) = -31,2

Холодная

-(36 0,35 + 36 0,5 + 36 0,15) = - 36

Как видно из таблицы 3, наименьшая ожидаемая средняя плата приходится на случай мягкой зимы (30,15 тг.). Соответственно если не учитывать степени риска, то представляется целесообразным летом закупить 4 т угля, а зимой, если потребуется, докупить уголь по более высоким зимним ценам. Однако, привлекая дополнительную информацию в форме расчета среднеквадратичного отклонения как индекса риска. Мы можем уточнить принятое на основе максимума прибыли или минимума издержек решение. Дополнительные рекомендации могут оказаться неоднозначными, зависящими от склонности к риску ЛПР.

Где D и М - соответственно символы дисперсии и математического ожидания.

Проводя соответственно вычисления для всех случаев по такому принципу:

Мягкая зима:

М(о2) = - (242 0,35 + 31,52 0,5 + 402 0,15) = - 937,725

(Мо)2 = -(30,152 ) = - 909,0225

Dо =937,725- 909,0225 = 28,7025

Для мягкой зимы = 5,357

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

для мягкой зимы = 5,357;

для обычной зимы = 2,856;

для холодной зимы = 0.

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

Вывод. Мы склоняемся к варианту покупки угля для обычной зимы, так как ожидаемая средняя плата за уголь по сравнению с вариантом для мягкой зимы возрастает на 3,5%, а степень риска при этом оказывается почти в 2 раза меньшей ( = 2,856 против 5,357).

Отношение среднеквадратичного отклонения к математическому ожиданию. Вариабельность (средний риск на затрачиваемый 1 тг) для обычной зимы составляет 2,856/31,2 = 0,0915. Против аналогичного показателя для мягкой зимы равного 5,357/30,15 = 0,1777, т.е. вновь различие почти в 2 раза.

Эти соотношения и позволяют рекомендовать покупку угля, ориентируясь не на мягкую, а на обычную зиму.

1.5 Смешанные стратегии в матричных играх

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

Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2., m, то его смешанная стратегия x - это набор чисел x = (., ) удовлетворяющих соотношениям:

>= 0 (i = 1, m), = 1

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y - это набор чисел y = (,…, ):

>= 0, (j = 1, n), = 1

Чистая стратегия есть частный случай смешанной стратегии. Если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е (А, х, y), а второй - за счёт своих смешанных стратегий стремится сделать Е (А, х, y) минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена игры:

б = min max Е (А, х, y)

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть:

б = max min Е (А, х, y)

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

Е (А, х, y) max min = Е (А, х, y) = Е (А, , )

Величина Е (А, , ) называется ценой игры и обозначается через v.

Имеется и другое определение оптимальных смешанных стратегий: , называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е (А, х, )<= Е (А, , )<= Е (А, , у)

Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

2. Применение игровых моделей

2.1 Аналитическое решение задачи

Мебельное предприятие планирует к массовому выпуску новую модель офисной мебели. Спрос на эту мебель не может быть точно определен. Однако можно предположить, что его величина характеризуется тремя возможными состояниями спроса - I, II, III.

С учетом этих состояний спроса анализируются три возможных варианта выпуска данной модели - А, Б, В. Каждый из этих вариантов требует своих затрат и обеспечивает, в конечном счете, различный эффект.

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

Найти значения переменных ..., при которых функция:

Q=

принимает максимальное значение, при условии следующих ограничений:

, , ? 0

Шаг:1

Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3 неотрицательные балансовые переменные , , .

(1)

(2) (3) , , , , , ? 0

Шаг:2

Ищем в системе ограничений базисные переменные. Из последней системы ограничений можно выделить базисные переменные s1,s2,s3.Теперь мы можем сформировать начальную симплекс-таблицу. (Табл. 4)

Шаг:3

Таблица 4

Начальная симплекс-таблица

БП

x1

x2

x3

s1

s2

s3

Решение

Отношение

s1

15

17

19

1

0

0

1

1

/

19

=

0.052

s2

17

18

17

0

1

0

1

1

/

17

=

0.058

s3

19

19

17

0

0

1

1

1

/

17

=

0.058

Q

1

1

1

0

0

0

0

--

Таблица 5

Итерация 1

БП

x1

x2

x3

s1

s2

s3

Решение

Отношение

x3

0.789

0.894

1

0.052

0

0

0.052

0.052

/

0.789

=

0.066

s2

3.578

2.789

0

-0.894

1

0

0.105

0.105

/

3.578

=

0.029

s3

5.578

3.789

0

-0.894

0

1

0.105

0.105

/

5.578

=

0.018

Q

0.210

0.105

0

-0.052

0

0

-0.052

--

Таблица 6

Итерация 2

БП

x1

x2

x3

s1

s2

s3

Решение

Отношение

x3

0

0.358

1

0.179

0

-0.141

0.037

--

s2

0

0.358

0

-0.320

1

-0.641

0.037

--

x1

1

0.679

0

-0.160

0

0.179

0.018

--

Q

0

-0.037

0

-0.018

0

-0.037

-0.056

--

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Оптимальное значение функции Q(x)=

0.056

2.2 Решение задачи в MS Excel

Решим задачу в чистых стратегиях б-это max в min, в-это min в max

Таблица 7

Матрица

Ai/Bj

б

15

17

19

15

10

18

19

10

18

17

17

17

в

18

18

19

В=18,б=17

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

Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана матрицей.

Определим нижнюю и верхнюю цены игры. Так как б?в, то седловая точка отсутствуют, и оптимальное решение следует искать в смешанных стратегиях игроков:

v= =

Обозначив =/v, =/v, составим две взаимно-двойственные задачи линейного программирования.

Задача 1. Игрок А

Задача 2. Игрок В

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

Свободные (первоначальные) переменные:

¦ ¦ ¦

Базисные (дополнительные) переменные:

¦ ¦ ¦

То есть х*=(0; 0; 0,059), у*=(0; 0,006; 0,052)

Используя первую теорему двойственности, получим Z min=max=0,058. По формуле v=1/0,058=17,1. Учитывая, что =/v, =/v, получим:

=•v; =0•17,1=0; =0•17,1=0; =0,059•17,1=0,6.

=•v; =0,006•17,1=0,1; =0,052•17,1=0,9; =0•17,1=0.

Оптимальная стратегия игрока A-=(0; 0; 0,6), игрока B-=(0,1; 0,9; 0) представлена на рисунке 1.

Рисунок 1 Решение задачи теории игр с помощью MS Excel “Поиск решения” игра модель матричный задача

2.3 Блок-схема алгоритма решения задач

2.4 Решение задачи в разработанной программе

Программа для решения задачи находится в папке «Simplex». Для ее запуска нужно нажать на файл LP. После запуска откроется интерфейс программы, затем в меню выбираем Файл >новый. Интерфейс представлен на рисунке 2.

Рисунок 2 Интерфейс программы

Следующие действия выбираем в меню Вычисления >параметры задачи. В появившемся окне вводим значение целевой функции и с необходимостью регулируем размерность задачи (рис. 3).

Рисунок 3 Параметры задачи

Во вкладке «Ограничения» указываем коэффициенты ограничения, знак и чему равен. Далее нажимаем на кнопку добавить, после этого все коэффициенты добавятся в задачу (рис. 4).

Рисунок 4 Ограничения

После всех выполненных вышеизложенных операции выбираем в меню Вычисления > Симплекс-метод. На форме «Задача 1» будет показан результат решения (рис. 5).

Рисунок 5 Результат

Заключение

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

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

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

Список использованной литературы

1. Мур, Джеффри, Уэдерфорл, Лари Л., и др. Экономическое моделирование в Microsoft Excel. М.: Издательский дом «Вильямс», 2004.

2. Орлова И.В. Экономико-математические методы и модели. Выполнение расчетов в среде EXCEL / Практикум: Учебное пособие для вузов. М.: ЗАО «Финстатинформ», 2000.

3. Окулов С.М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний, 2002.

4. Леоненков А. В. Решение задач оптимизации в среде MS Excel. СПб.: БХВ-Петербург, 2005.

5. Дьяконов В.П. MathCAD 8 - 12 для всех. М.: СОЛОН - Пресс, 2005.

6. Стивене Р. Delphi. Готовые алгоритмы - М.: ДМК Пресс ; СПб.: Питер, 2004.

7. Громов Ю.Ю., Татаренко С.И. Языки С и С ++ для решения инженерных и экономических задач.Тамбов, Издательство ТГТУ, 2001.

8. Таха X. Введение в исследование операций. Т. 1.2. М. Мир. 2002г.

Приложения

Приложение 1

Листинг программы

//Симплекс-метод

procedure TMainForm.N6Click(Sender: TObject);

var

SimplexTable,SimplexTableNew:array of array of extended;

GoalFun:array of extended;

ArtFun:array of extended;

ExtrEstimation:extended;

k,i,j,MoreCount,LessCount,EquallyCount,extrItem,WLine,IterCount: integer;

Art,bil:boolean;

label fin,up;

begin

Art:=true;bil:=false;IterCount:=0;

SimplexTable:=nil;

MoreCount:=0;LessCount:=0;EquallyCount:=0;

{1}//Сортировка ограничений: 1) >=; 2) =; 3) <=.

{2}//Порождение начального базиса

{3}//Итерационное построение симплекс-таблиц

{1}//---------------------------------------------------------------------------

//Сортировка "Больше"

with MainForm.ActiveMDIChild as TChildForm do

begin

//строки в таблицах дочернего окна нумеруются с 1

//нулевая строка резервная

for i:=1 to SignsChild.RowCount-1 do

begin

if (SignsChild.Cells[0,i]='>') or (SignsChild.Cells[0,i]='>=') then

begin

inc(MoreCount);

SetLength(SimplexTable,LimChild.ColCount+2,MoreCount);

//коэффициенты

for j:=0 to LimChild.ColCount-1 do

SimplexTable[j+2,MoreCount-1]:=StrToFloat(LimChild.cells[j,i]);

//Пока нули (потом базис...)

SimplexTable[0,MoreCount-1]:=0;

//Значение (B i-ый)

SimplexTable[1,MoreCount-1]:=StrToFloat(BChild.cells[0,i]);

end;

end;

//Сортировка "Равно"

for i:=1 to SignsChild.RowCount-1 do

begin

if SignsChild.Cells[0,i]='=' then

begin

inc(EquallyCount);

SetLength(SimplexTable,LimChild.ColCount+2,MoreCount+EquallyCount);

//коэффициенты

for j:=0 to LimChild.ColCount-1 do

SimplexTable[j+2,MoreCount+EquallyCount[1]:=StrToFloat(LimChild.cells[j,i]);

//Пока нули (потом базис...)

SimplexTable[0,MoreCount+EquallyCount-1]:=0;

//Значение (B i-ый)

SimplexTable[1,MoreCount+EquallyCount-1]:=StrToFloat(BChild.cells[0,i]);

end;

end;

//Сортировка "Меньше"

for i:=1 to SignsChild.RowCount-1 do

begin

if (SignsChild.Cells[0,i]='<') or (SignsChild.Cells[0,i]='<=') then

begin

inc(LessCount);

SetLength(SimplexTable,LimChild.ColCount+2,MoreCount+EquallyCount+LessCount);

//коэффициенты

for j:=0 to LimChild.ColCount-1 do

SimplexTable[j+2,MoreCount+EquallyCount+LessCount-1]:=StrToFloat(LimChild.cells[j,i]);

//Пока нули (потом базис...)

SimplexTable[0,MoreCount+EquallyCount+LessCount-1]:=0;

//Значение (B i-ый)

SimplexTable[1,MoreCount+EquallyCount+LessCount-1]:=StrToFloat(BChild.cells[0,i]);

end;

end;

end;

{2}//---------------------------------------------------------------------------

//Порождение начального базиса

//2.1 Добавить коэф. -1 (>=)

for j:=0 to MoreCount-1 do

begin Setlength(SimplexTable,length(SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i:=length(SimplexTable)-MoreCount+1 to length(SimplexTable)-1 do

SimplexTable[i,j]:=0;

SimplexTable[length(SimplexTable)-1,j]:=-1;

end;

//2.2 Добавить коэф. 1 (<=)

for j:=MoreCount+EquallyCount to MoreCount+EquallyCount+LessCount-1 do

begin

Setlength(SimplexTable,length(SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i:=length(SimplexTable)-LessCount+2 to length(SimplexTable)-1 do

SimplexTable[i,j]:=0;

SimplexTable[length(SimplexTable)-1,j]:=1;

end;

//2.3 Добавить искусственные коэф. (>= и =)

for j:=0 to MoreCount+EquallyCount-1 do

begin Setlength(SimplexTable,length(SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i:=length(SimplexTable)-MoreCount+1 to length(SimplexTable)-1 do

SimplexTable[i,j]:=0;

SimplexTable[length(SimplexTable)-1,j]:=1;

end;

//Целевая функция GoalFun

GoalFun:=nil;

with MainForm.ActiveMDIChild as TChildForm do

begin

SetLength(GoalFun,GoalChild.ColCount+1);

for i:=1 to GoalChild.ColCount do

begin

if parametersForm.Min.Checked then GoalFun[i]:=StrToFloat(goalChild.Cells[i-1,1])

else GoalFun[i]:=-1*StrToFloat(goalChild.Cells[i-1,1]);

end;

end;

//Искусственная функция ArtFun

ArtFun:=nil;

SetLength(ArtFun,length(SimplexTable)-1-MoreCount);

//i=1 - Значение иск. функции

for i:=1 to length(SimplexTable)-3 do

for j:=0 to MoreCount-1 do ArtFun[i-1]:=ArtFun[i-1]-SimplexTable[i,j];

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

...

Подобные документы

  • Решение в среде Microsoft Excel с помощью программной модели "Поиск решения" транспортной задачи, системы нелинейных уравнений, задачи о назначениях. Составление уравнения регрессии по заданным значениям. Математические и алгоритмические модели.

    лабораторная работа [866,6 K], добавлен 23.07.2012

  • Математическая модель задачи: расчет объема производства, при котором средние постоянные издержки минимальны. Построение графика функции с помощью графического редактора MS Excel. Аналитическое исследование функции, зависящей от одной переменной.

    курсовая работа [599,7 K], добавлен 13.02.2010

  • Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

  • Развитие и закрепление навыков работы с табличным процессором MS Excel. Определения элементов теории контракта. Симметричная и асимметричная информация об усилиях работника. Решение задачи с помощью графического способа и надстройки "Поиск решения".

    курсовая работа [3,0 M], добавлен 13.05.2014

  • Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.

    курсовая работа [1,1 M], добавлен 27.08.2012

  • Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.

    курсовая работа [844,3 K], добавлен 16.06.2011

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

    задача [3,2 M], добавлен 15.02.2010

  • Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.

    реферат [157,5 K], добавлен 21.08.2008

  • Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.

    курсовая работа [514,8 K], добавлен 04.02.2011

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

    курсовая работа [2,4 M], добавлен 17.12.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.