Линейное программирование

свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=Линейное программирование), 2 – свою j-ю стратегию (j=Линейное программирование), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij | ). На этом игра заканчивается.

Каждая стратегия игрока i=Линейное программирование; j = Линейное программирование часто называется чистой стратегией.

Если рассмотреть матрицу


А = Линейное программирование


то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.

Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =Линейное программирование) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2


Линейное программированиеаij (i = Линейное программирование)


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


Линейное программированиеЛинейное программированиеаij = Линейное программирование= Линейное программирование (1).

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

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

Линейное программированиеаij , т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию,

затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит


Линейное программированиеЛинейное программированиеaij = Линейное программирование= Линейное программирование (2).


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

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

Определение. Если в игре с матрицей А Линейное программирование=Линейное программирование, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры


u = Линейное программирование=Линейное программирование.


Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство Линейное программирование = Линейное программирование. В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:


Линейное программирование Линейное программирование


где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент Линейное программирование является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент Линейное программирование, называется решением игры. При этом iо и jо называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.


2.3 Решение матричных игр в смешанных стратегиях путём сведения к задаче линейного программирования


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

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

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


xi >= 0 (i = 1,m), Линейное программирование= 1.


Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел


y = (y1, ..., yn), yj >= 0, (j = 1,n), Линейное программирование= 1.


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

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

Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

E (A, x, y) =Линейное программирование= x A yT


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


Линейное программирование Е (А, х, y).


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


Линейное программирование Е (А, х, y).


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


Линейное программирование Е (А, х, y) =Линейное программирование Е (А, х, y) = Е (А, хо, уо).


Величина Е (А, хо ,уо) называется при этом ценой игры и обозначается через u.

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

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


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

Основная теорема матричных игр имеет вид :

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины


Линейное программирование Е (А, х, y) и Линейное программирование Е (А, х, y) существуют и равны между собой.


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

Пусть игра m Ч n задана платежной матрицей p = (aij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A1 , A2 , ..., Am , игрок В — стратегиями B1 , B2 , ..., Bm . Необходимо определить оптимальные стратегии S*A = ( p*1 , p*2 , ... , p*m ) и S*B = ( q*1 , q*2 , ... , q*n ), где p*i, q*j — вероятности применения соответствующих чистых стратегий Ai , Bj, p*1 + p*2 +...+ p*m =1, q*1 + q*2 +...+ q*n = 1.

Оптимальная стратегия S*A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы aij ≥ 0. Если игрок А применяет смешанную стратегию S*A = ( p*1 , p*2 , ... , p*m ) против любой чистой стратегии Bj игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша aj = a1j p1 + a2j p2 +...+ am j pm , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A1 , A2 , ..., Am и результаты складываются).

Для оптимальной стратегии S*A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:


Линейное программирование (2.3.1)


Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:


x1 = p1/v, x2 = p2/v , ..., pm/v (2.3.2)


Тогда система (2.3.1) примет вид:


Линейное программирование (2.3.3)


Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v.

Разделив на v ≠ 0 равенство p1 + p2 + ...+ pm = 1 , получаем, что переменные x1 (i = 1, 2, ..., m) удовлетворяют условию: x1 + x2 + ...+ xm = 1/v. Максимизация цены игры v эквивалентна минимизации величины1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных xi ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (2.3.3) и при этом линейная функция


Z = x1 + x2 + ...+ xm, (2.3.4)

обращалась в минимум. Это задача линейного программирования. Решая задачу (2.3.3)—( 2.3.4), получаем оптимальное решение p*1 + p*2 + ...+ p*m и оптимальную стратегию SA .

Для определения оптимальной стратегии S*B = (q*1 + q*2 + ...+ q*n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти Линейное программирование. Переменные q1 , q2 , ..., qn удовлетворяют неравенствам:


Линейное программирование (2.3.5)


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


yj = qj/v, j = 1, 2, ..., n, (2.3.6)


то получим систему неравенств:


Линейное программирование (2.3.7)


Переменные yj (1, 2, ..., n) удовлетворяют условию Линейное программирование.

Игра свелась к следующей задаче

Определить значения переменных yj ≥ 0, j = 1, 2, ..., n, которые удовлетворяют системе неравенств (2.3.7) и максимизируют линейную функцию

Z' = y1 + y2 + ...+ yn, (2.3.8)


Решение задачи линейного программирования (2.3.6), (2.3.7) определяет оптимальную стратегию S*B = (q*1 + q*2 + ...+ q*n) . При этом цена игры


v = 1 / max, Z' = 1 / min Z (2.3.9)


Составив расширенные матрицы для задач (2.3.3), (2.3.4) и (2.3.7), (2.3.8), убеждаемся, что одна матрица получилась из другой транспонированием:


Линейное программирование


Таким образом, задачи линейного программирования (2.3.3), (2.3.4) и (2.3.7), (2.3.8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.

3. Практическая часть


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


Продукция/сырьё А В С Запасы сырья, ед.
I 4 2 0 ≤ 19
II 0 1 1 = 8
III 1 2 0 ≤ 24
Прибыль, ден. ед. 3 7 2 ≥ max

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

Вид таблицы по заданию поставленной задачи:


Вид сырья Нормы затрат сырья (кг) на единицу продукции

А В С

I

II

III

4

0

1

2

1

2

0

1

0

Цена единицы продукции (руб.) 3 7 2

Решение поставленной задачи:

Предположим, что производится x1 изделий А, Линейное программированиеизделий В и Линейное программированиеизделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

3.1.Построим математическую модель задачи:


тогда функция цели:


Z-0 = 3X1 + 7X2 + 2X3 – совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать.


Подсчитаем затраты сырья:

Сырье 1-го типа: 4 х1 + 2 х2 + 0 х3 , по условию затраты не превосходят 19,

Сырье 2-го типа: 0 х1 + 1 х2 + 1 х3, по условию затраты не превосходят 8,

Сырье 3-го типа: 1x1 + 2x2 + 0x3, по условию затраты не превосходят 24.

при следующих условиях:


4 X1 + 2 X2 + 0 X3 + X4 ≤ 19
0 X1 + 1 X2 + 1 X3 + X5 = 8
1 X1 + 2 X2 + 0 X3 + X6 ≤ 24

X1, X2, X3 ≥ 0.

4X1+2X2+X4 ≤ 19

X2 + X3 +X5 = 8

X1+ 2X2+X6 ≤24


3.2 Выбираем метод решения и приводим задачу к каноническому виду:


Пришли к задаче линейного программирования:

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

Получили математическую модель. Необходимо максимизировать функцию цели ↓


Z-0 (x1, x2, x3) = 3X1 + 7X2 + 2X3 → max


Введем дополнительные переменные X4, X5, X6.


Z-0= 3 X1 + 7 X2 + 2 X3 а(max)
при системе ограничений:









Преобразуем первое ограничение:


4 X1 + 2 X2 + 0 X3 + X4 = 19
0 X1 + 1 X2 + 1 X3 + X5 = 8
1 X1 + 2 X2 + 0 X3 + X6 = 24

Получили задачу:


4X1+2X2+X4 = 19

X2 + X3 +X5 = 8

X1+2X2 +X6 =24


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


Xi≥0 ; 0-Z= -3X1- -7X2- -2X3


Приведем задачу к канонической форме.

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

Требуется найти вектор Линейное программирование, доставляющий максимум линейной форме


Линейное программирование


при условиях


Линейное программирование

Линейное программирование

где Линейное программирование

Решим задачу симплекс-методом

Строим начальную симплекс-таблицу:

Базисные переменные X1 X2 X3

X4 X5 X6 Свободные члены
X4 4 2 0

1 0 0 19
X5 0

1

1

0 1 0 8
X6 1 2 0

0 0 1 24
0-Z -3 -7 -2

0 0 0 0


Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-7). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу:

Базисные переменные X1 X2 X3 X4 X5 X6

Свободные члены
X4

4

-2 -2 1 0 0

3
X2 0 1 1 0 1 0

8
X6 1 -2 -2 0 0 1

8
0-Z -3 7 5 0 0 0

56

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-3). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Тогда каноническую форму задачи ЛП можно представить в следующем матричном виде эквивалентном первоначальному:


Z=CX →max,

AX=B,

X≥0.


где 0 - нулевая матрица-столбец той же размерности, что и матрица X.

замечание.

Не ограничивая общности, можно полагать, что свободные члены неотрицательны, т.е. b i ≥ 0, где i =Ї1,m (иначе ограничительные уравнения можно умножить на (-1)).

Пересчитаем таблицу:


Базисные переменные X4 X5 X3 Свободные члены
X1 1/4 -1/2 -1/2 3/4
X2 0 1 1 0
X6 -1/4 -3/2 -3/2 29/4
0-Z 3/4 11/2 7/2 233/4

Эта таблица является последней, по ней читаем ответ задачи.

Найдено оптимальное базисное решение:

При котором Z max = 233/4= 58,25 ден. ед.

План производства:

X1 =3/4= 0,75; X2 = 0; X3 = 0; X4 = 3; X5 = 0; X6 = 29/4= 7,25

Соответственно по решению, вычисляем:

Z= 3*0,75+7*0+2*0+3+7,25= 24

Z= 24

Ответ поставленной задачи: План выпуска продукции (Z) для получения максимальной прибыли, при том, что сырьё IIвида было израсходовано полностью равен 24 (Z= 24). Из хода решения задачи по условию мы видим, что оценен каждый из видов сырья, используемых для производства продукции.

Блок-схемы основных процедур при решении и программировании задач

Алгоритм программы → Рис. 1. ↓


Линейное программирование


Линейное программирование


Линейное программированиеЛинейное программирование


Линейное программирование

Линейное программирование

Линейное программирование

Линейное программированиеЛинейное программированиеЛинейное программирование

Линейное программирование

Линейное программирование

Линейное программирование


Линейное программированиеЛинейное программирование


Линейное программированиеЛинейное программированиеЛинейное программирование

Линейное программирование


Линейное программированиеЛинейное программированиеЛинейное программирование

Линейное программирование

Линейное программирование

Линейное программированиеЛинейное программирование


Линейное программированиеЛинейное программированиеЛинейное программирование

Линейное программирование

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: