Сведение матричной игры к задаче линейного программирования

Алгоритм метода

1. Запишем задачу в форме (5.7), при этом все элементы столбца свободных членов должны быть неотрицательны , . Уравнения системы (5.5), в которых свободные члены отрицательны, предварительно нужно умножить на - 1.

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

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

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

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

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

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

Выбор разрешающего элемента производят иначе, а именно.

1. Просматривают строку, соответствующую какому-либо отрицательному свободному члену. Выбирают в ней какой-либо отрицательный элемент - соответствующий этому элементу столбец будет разрешающим.

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

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

6. Двойственные задачи линейного программирования

6.1 Взаимодвойственные задачи

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

Таблица 6.1. Исходные данные

Цены на ресурсы	Запасы сырья	Продукция
		П1	П2		Пn
	Прибыль с единицы продукции

Запишем в общем виде экономико-математическую модель задачи об использовании ресурсов. Для этого введём переменные , - количество продукции j-го вида. Тогда ограничения на сырье запишутся в виде

(6.1)

Целевая функция, определяющая максимум прибыли, имеет вид

; (7.2)

, .

По этим же исходным данным сформулирую задачу по предприятию №2.

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

1) общая стоимость ресурсов для предприятия №2 должна быть минимальной;

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

Обозначу цены, по которым предприятие №2 покупает ресурсы у предприятия №1, через , . Запишу экономико-математическую модель для предприятия №2 с учётом вышеуказанных условий 1) и 2).

Целевая функция, определяющая минимальную суммарную стоимость ресурсов, имеет вид

. (6.3)

В соответствии с условием 2) запишем систему ограничений:

(6.4)

Сравню математические модели задач (6.1), (6.2) и (6.3), (6.4):

1) число неизвестных одной задачи равно числу ограничений другой задачи;

2) матрица коэффициентов системы ограничений получается одна из другой путём транспортирования;

3) неравенства в системах ограничений имеют противоположный смысл;

4) свободные члены системы ограничений одной из задач становится коэффициентами целевой функции другой задачи, коэффициенты целевой функции превращаются в свободные члены ограничений;

5) целевые функции в задачах имеют противоположный смысл: в первой - максимум, во второй - минимум.

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

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

основная задача

(6.5)

; (6.6)

, ;

двойственная задача

(6.7)

(6.8)

Эти задачи отличаются от симметричной пары двумя особенностями:

1) ограничения задачи (6.5) - (6.6) выражены уравнениями вместо неравенств;

2) в задаче (6.7) - (6.8) отсутствуют условия не отрицательности переменных , .

Общее правило построения двойственной пары.

К пяти признакам сформулированным ранее, необходимо добавить следующие:

1) в исходной ограничения неравенства следует записывать со знаком , если целевая функция стремится к минимуму, и со знаком , если целевая функция стремится к максимуму;

2) каждому ограничению неравенства исходной задачи соответствует в двойственной задаче условие не отрицательности переменных ;

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

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

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

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

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

Соотношениям отыскания и можно поставить в соответствие эквивалентные им задачи

(7.1)

Здесь есть математическое ожидание выигрыша первого игрока.

Тогда для любой чистой стратегии y(j) игрока В

можно записать

, (7.2)

а для любой чистой стратегии x(i) игрока А

можно записать

. (7.3)

Следовательно, задачи (7.1) - (7.3) допускают следующую запись в форме задач линейного программирования

, (7.4)

. (7.5)

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

Для задачи (7.4) положим и , (7.6)

а для задачи (7.5) положим и . (7.7)

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

минимизировать линейную функцию

(7.8)

при условиях

, ; , , (7.9)

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

максимизировать линейную функцию

(7.10)

при условиях

, ; , . (7.11)

Исходя из основной теоремы теории двойственности, задачи (7.8) - (7.11) имеют конечное решение и .

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

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

По данным наблюдений за предшествующие одиннадцать лет предприятие в течение апреля - мая в условиях тёплой погоды может реализовать 600 костюмов, 2000 платьев и 300 плащей, в условиях прохладной погоды - 1000 костюмов, 500 платьев и 800 плащей и в условиях обычной погоды 800 костюмов, 1100 платьев и 600 плащей. Затраты на единицу продукции в течение указанных месяцев составили для костюмов 30 ден. ед., для платьев 10 ден. ед. и плащей 15 ден. ед., а цена реализации равна соответственно 50 ден. ед., 20 ден. ед. и 28 ден. ед.

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

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

Первоочередной задачей является построение платёжной матрицы.

Предприятие располагает тремя чистыми стратегиями: стратегия Р₁ с расчетом на тёплую погоду, стратегия Р₂ с расчётом на прохладную погоду и стратегия Р₃ с расчётом на обычную погоду.

Природа, рассматривается как второй игрок, также располагает тремя стратегиями: обычная погода (стратегия П₁), прохладная погода (стратегия П₂) и тёплая погода (стратегия П₃).

Если предприятие выберет стратегию Р₁, то в случае обычной погоды (стратегия природы П₁) доход составит

в случае прохладной погоды (стратегия природы П₂) доход будет равен

и в случае теплой погоды (стратегия природы П₃) имеем доход, равный

Если предприятие выберет стратегию Р₂, то реализация продукции в условиях обычной погоды даёт доход

в условиях холодной погоды доход будет

а в условиях тёплой погоды имеем доход

Если предприятие выберет стратегию Р₃, то в случае обычной погоды доход будет равен

при прохладной погоде имеем доход, равный

и в случае тёплой погоды доход составит

Результаты вычислений сведены в табл. 7.1.

Платёжная матрица рассматриваемой производственной ситуации имеет вид

. (7.12)

Таблица 7.1. Платёжная матрица

Стратегия природы Стратегия предприятия	Обычная П1	Прохладная П2	Тёплая П3
Тёплая - Р1	17900	5900	35900
Прохладная - Р2	22000	35400	6400
Обычная - Р3	34800	22800	16000

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

Для матрицы (7.12), исходя из общей постановки (7.8) - (7.11), имеем следующую пару двойственных задач:

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

(7.13)

при ограничениях

 (7.14)

Оптимальную стратегию игрока 2 определим, решив задачу линейного программирования: найти максимум функции

(7.15)

при ограничениях

(7.16)

Решаю более простую обратную задачу (7.15) - (7.16). Вводя положительные базисные переменные (б.п.) , систему неравенств (7.16) записываем в виде системы уравнений

(7.17)

Систему (7.17) запишем в виде симплекс-таблицы 7.2.

Таблица 7.2. Симплекс-таблица

С.П. Б.П.	U1	U2	U3	1
U4	17900	5900	35900	1
U5	22000	35400	6400	1
U6	34800	22800	16000	1
Z	-1	-1	-1	0

Совершив три шага жордановых исключений, получаем табл. 7.3.

Так как в табл. 7.3 все элементы в z - строке и 1 - столбце неотрицательны, то получаем оптимальное решение.

Таблица 7.3. Симплекс-таблица

С.П. Б.П.	U6	U5	U4	1
U3
U2
U1

Переходим к решению прямой задачи. Установим соответствие переменных двойственных задач:

С.П.Б.П.

Транспортируем табл. 7.3, знаки перед всеми элементами, кроме элементов z - строки, меняем на обратные, переменные заменяем на соответствующие переменные , получаем табл. 7.4.

Таблица 7.4. Транспортированная симплекс-таблица 7.3

С.П. Б.П.				1
Т

Из табл. 7.4 получаем оптимальное решение. Так как , то цена игры . Из получаем . Аналогично получим и .

Это означает, что означает, что стратегию Р₁ нужно применять с вероятностью , стратегию Р₂ - с вероятностью , и стратегию Р₃ - с вероятностью .

Формируем оптимальный план производства:

Таким образом, предприятие при производстве 801 костюма, 1239 платьев и 554 плащей получит наибольшую прибыль, которая в среднем составит 20833 ден. ед.

Для приведённой формулировки производственной задачи получили однозначный ответ.

Недостатком данного метода является достаточно большой объём вычислительных операций даже для матрицы с размером . Однако применение ЭВМ снимает это неудобство.

7.1 Сведение задачи линейного программирования к матричной игре

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

Отмечу, что задача (7.4) имеет и непосредственный экономический: к ней сводится оптимизация плана выпуска продукций в заданном ассортименте.

Пусть имеется режимов работы некоторого оборудования с фондом полезного времени для выпуска продуктов; за I час работы в режиме выпускается продукта . Требуется максимизировать выпуск продукции в заданном ассортименте, причём, один ассортиментный набор содержит продукта .

Решение. Обозначая через R искомое количество ассортиментных наборов и через затраты времени на работу в режиме i, получаем задачу.

Найти вектор и число R, удовлетворяющие условиям

, (7.18)

, (7.19)

, (7.20)

. (7.21)

Полагая , , , сведём задачу (7.18) - (7.21) к виду (7.4):

. (7.22)

Следовательно, матрица выигрышей имеет вид . К задачам (7.4) - (7.4), а следовательно, (7.8) - (7.9) и (7.10) - (7.11), сводятся некоторые варианты задачи минимизации времени выполнения заданной программы выпуска.

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

Заключение

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

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

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

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

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

Среди задач математического программирования самыми простыми (и лучше всего изученными) являются так называемые задачи линейного программирования. Характерно для них то, что показатель эффективности (целевая функция) W линейно зависит от элементов решения x₁, x₂, …, x_n. И ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно x₁, x₂, …, x_n.

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

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

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

Список литературы

1. Е.С. Вентцель. Исследование операций. Задачи, принципы методология: учеб. для вузов - 4-е изд., стереотип. - М.: Дрофа. 2006. - 206, [2] с.: ил.

2. Теория вероятностей и математическая статистика. Учеб. пособие для втузов. Изд. 5-е, перераб. и доп. М., «Высш. школа», 1977.

3. Е.В. Бережная, В.И. Бережной. Математические методы моделирование экономических систем: Учеб. пособие. - 2-е изд.; перераб. доп. - М.: Финансы и статистика 2008. - 232 С.: ил.

4. Карпелевич Ф.И., Садовский Л.Е. Элемементы линейной алгебры и линейного программирования. М.: Наука, 1967.

5. Зуховидский С.И., Авдеева Л.И. Линейное и выпуклое программирование. - М.: Наука, 1964.

6. Общий курс высшей математики для экономистов. Под ред. В.И. Ермакова. - М., 2003.

7. Вентцель Е.С. Элементы теории игр. - М. Физматгиз, 1969.

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

9. Льюс Р.Д., Райфа Х. Игры и решения. - М.: Иностранная литература, 1961.

10. Красс М.С., Чупрынов Б.П. «Основы математики и ее приложения в экономическом образовании», Издательство «Дело», Москва 2001 г.

11. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

12. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Нау-ка», 1980 г.

13. Чеснокова О.В. Delphi 7. Алгоритмы и программы. - М.: Пресс, 2008. - 368 С.: ил.

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