Раздел 3. Решение транспортной задачи. Матричные игры

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

3.1. Математическая постановка транспортной задачи

Изучаемые вопросы:

· Общая формулировка транспортной задачи;

· Пример.

Некоторая фирма имеет n пунктов производства однородной продукции: A 1, A 2,…, A n, и m пунктов потребления (рынков сбыта): B 1, B 2,…, Bm.

Предположим, что заданы величины a 1, a 2,…, an, b 1, b 2,…, b m, которые определяют максимальные производительности пунктов производства и минимальные потребности пунктов потребления соответственно.

Обозначим:

cij – стоимость перевозок единицы продукции из пункта производства Ai в пункт потребления Bj;

xij – количество продукции, направляемое из пункта производства A i в пункт потребления Bj. Совокупность чисел { x ij} образует план перевозок.

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

Транспортные расходы составят величину:

. (3.1.1)

Неравенство

(3.1.2)

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

Аналогично неравенство

(3.1.3)

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

Таким образом, математически в транспортной задаче требуется найти план перевозок { x ij}, который минимизирует транспортные расходы

(3.1.1)

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

, (3.1.2)

, (3.1.3)

x _ij ≥ 0. (3.1.4)

Отсюда следует, что транспортная задача является задачей линейного программирования. План перевозок xij назовем допустимым, если он удовлетворяет ограничениям (3.1.2)-(3.1.3). Допустимый план перевозок назовем оптимальным, если на этом плане транспортные расходы минимальны.

Для совместимости ограничений (3.1.2)-(3.1.3) необходимо выполнение неравенства

, (3.1.5)

т.е. суммарная производительность всех производств не меньше суммарного минимального потребления.

Пример 3.1.1

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

A 1, A 2, A 3 изготавливается однородная продукция в количествах: a 1=30, a 2=40, a 3=20 соответственно. Эту продукцию требуется доставить в четыре пункта потребления: B 1, B 2, B 3, В 4 в количествах b 1 = 20, b 2 = 30, b 3 = 30, b 4 = 10 соответственно. Матрица C задает стоимости перевозок единицы продукции cij из пункта производства Ai в пункт потребления Bj:

.

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

Запишем математическую модель данной транспортной задачи.

Обозначим xij – количество продукции, направляемое из пункта производ-ства A i в пункт потребления B j (табл.3.1.1). Составим матрицу перевозок из величин xij

Таблица 3.1.1

Сумма элементов первой строки: x 11 + x 12 + x 13 + x 14 определяет количество продукции, вывозимое из пункта производства A 1. По условию задачи эта величина не может превосходить максимального количества продукции a 1 = 30, производимого в этом пункте, т.е. должно выполняться неравенство

x 11 + x 12 + x 13 + x 14 ≤ 30.

Аналогично сумма элементов второй строки x 21 + x 22 + x 23 + x 24 определяет количество продукции, вывозимое из пункта производства A 2. По условию задачи эта величина не может превосходить максимального количества продукции a 2=40, производимого в этом пункте, т.е. должно выполняться неравенство: x 21 + x 22 + x 23 + x 24 ≤ 40.

Сумма элементов третьей строки x 31 + x 32 + x 33 + x 34 определяет количество продукции, вывозимое из пункта производства A 3. По условию задачи эта величина не может превосходить максимального количества продукции a 3=20, производимого в этом пункте, т.е. должно выполняться неравенство

x 31 + x 32 + x 33 + x 34 ≤ 20.

Сумма элементов первого столбца x 11 + x 21 + x 31 определяет количество продукции, ввозимое в пункт B 1. По условию задачи эта величина не меньше минимального количества продукции b 1=20, необходимого в этом пункте потребления, т.е. должно выполняться неравенство: x 11 + x 21 + x 31 ≥ 20.

Аналогично для всех остальных пунктов потребления должны выполняться неравенства:

x 12 + x 22 + x 32 ≥ 30,

x 13 + x 23 + x 33 ≥ 30,

x 14 + x 24 + x 34 ≥ 10.

Математически транспортную задачу можно сформулировать следующим образом:

- найти переменные xij, которые минимизируют транспортные расходы

T = 2 x 11+3 x 12+3 x 13+4 x 14+3 x 21+2 x 22+5 x 23+ x 24+4 x 31+3 x 32+2 x 33+6 x 34 (3.1.6)

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

x 11+ x 12+ x 13+ x 14 ≤ 30,

x 21+ x 22+ x 23+ x 24 ≤ 40, (3.1.7)

x 31+ x 32+ x 33+ x 34 ≤ 20,

x 11+ x 21+ x 31 ≥ 20,

x 12+ x 22+ x 32 ≥ 30,

x 13+ x 23+ x 33 ≥ 30, (3.1.8)

x 14+ x 24+ x 34 ≥ 10,

xij ≥ 0.

Решение этой задача в Excel составляет содержание лабораторной работы 2.

Вопросы для самопроверки

1. Сформулировать условие совместимости ограничений транспортной задачи?

2. В чем состоит экономический смысл ограничений 3.1.2?

3. В чем состоит экономический смысл ограничений 3.1.3

3.2. Матричные игры. Основные понятия

Изучаемые вопросы:

· Матричные игры;

· Чистые стратегии;

· Ситуация равновесия.

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

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

Допустим, что игрок I имеет множество своих стратегий, которые можно перенумеровать числами 1, 2,…, n. Игрок II имеет множество своих стратегий, которые можно перенумеровать числами 1, 2,…, m. Если игрок I выбирает из множества своих стратегий стратегию с номером i, а игрок II выбирает стратегию с номером j, то в возникшей ситуации (i,j) игрок I получает выигрыш равный a ij (игрок II в этой ситуации получает выигрыш равный - a ij). В этом случае все возможные выигрыши игрока I можно записать в виде матрицы

Чистой стратегией игрока I является выбор одной из n строчек матрицы выигрышей A, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы. Если игрок I выбирает строку номером i, а игрок II выбирает столбец с номером j, то в возникшей ситуации (i,j) выигрыш игрока

I равен элементу aij (игрок II в этой ситуации получает выигрыш равный - aij).Такие игры называют матричными антагонистическими играми двух лиц с нулевой суммой. Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I. В дальнейшем для удобства элементы матрицы aij будем обозначать a (i,j).

Решить матричную игру в чистых стратегиях означает найти такую ситуацию (i *, j *), в которой выигрыш игрока I удовлетворяет неравенствам:

a (i, j *) ≤ a (i *, j *) ≤ a (i *, j) (3.2.1)

для всех чистых стратегий i, j обоих игроков. Ситуация (i *, j *) называется ситуацией равновесия или седловой точкой матричной игры в чистых стратегиях. Стратегия i * игрока I состоит в выборе строки с номером i * и называется его оптимальной чистой стратегией игрока I, а стратегия j * игрока II состоит в выборе столбца с номером j * и называется его чистой оптимальной стратегией игрока II. Число a (i*,j*) является выигрышем игрока I и называется значением или ценой игры и обозначается v (A).

Левая часть неравенства означает:

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

Аналогично правая часть неравенства означает:

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

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

v (A)=(max) i (min) j a (i,j) = (min) j (max) i a (i, j) (3.2.2)

В матричной игре может не существовать ситуации равновесия в чистых стратегиях, т.е. не выполняется равенство (3.2.2). Рассмотрим примеры.

Пример 3.2.1

Допустим, что матрица выигрышей игрока I имеет вид:

Найдем минимальные элементы в каждой строке и максимальные элементы в каждом столбце

min в строке

max в столбце

Отсюда следует, что максимальное среди минимальных в строке равно

max min {9,8,8,10}=10

и минимальное среди максимальных в столбце равно

min max{10,14,14,16} =10.

Следовательно, для этой матричной игры выполняется равенство

max min {9,8,8,10}= min max{10,14,14,16} =10,

т.е. значение игры v (A) = 10. В матрице выигрышей три элемента равны 10. Из них только элемент в четвертой строке в первом столбце a (4,1) будет минимальным в строке и максимальным в столбце. Отсюда следует, что оптимальной стратегией игрока I является выбор четвертой строки, а оптимальной стратегией игрока II является выбор первого столбца. Заметим, что выбор игроком I четвертой строки гарантирует ему выигрыш 10. Аналогично выбор игроком II первого столбца гарантирует ему выигрыш 10.

Замечание. Изменение матрицы выигрышей может нарушить ситуацию равновесия в игре.Допустим, что в матрице выигрышей предыдущего примера элемент a₄₃ = 10 равен 9

min в строке

max в столбце

Тогда максимальное среди минимальных в строке равно

max min {9,8,8,9} =9, а минимальное среди максимальных в столбце равно

min max {10,14,14,16} =10.

Для этой матричной игры max min {9,8,8,9}≠ min max{10,14,14,16} =10 и, следовательно, решение игры в чистых стратегиях не существует.

Вопросы для самопроверки

1. Какие игры называются антагонистическими?

2. Чему равен выигрыш игрока II в матричной игре, если выигрыш игрока I равен 5?

3. Как определяются чистые стратегии игроков в матричной игре?

4. Дать определение ситуации равновесия в чистых стратегиях?

5. Всегда существует ситуация равновесия в чистых стратегиях?

3.3. Решение матричных игр в смешанных стратегиях

Изучаемые вопросы:

· Определение смешанных стратегий;

· Ситуация равновесия в смешанных стратегиях.

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

Смешанной стратегией игрока I называется любой упорядоченный набор из n чисел p = (p 1, p 2,…, pn) удовлетворяющий условиям

p 1 + p 2 +…+ pn = 1, pi ≥ 0.

Число pi определяет вероятность, с которой игрок I выбирает строку i матрицы выигрышей. Среди смешанных стратегий игрока I содержатся все его чистые стратегии. Если все числа p i равны 0, кроме значения p k = 1, то эта стратегия означает выбор игроком строки с номером k. Аналогично определяются смешанные стратегии игрока II.

Смешанной стратегией игрока II называется любой упорядоченный набор из m чисел q = (q 1, q 2,…, qm), удовлетворяющий условиям

q 1 + q 2,+…+ q m=1, q j ≥ 0.

Число qj определяет вероятность, с которой игрок II выбирает столбец j матрицы выигрышей. Среди смешанных стратегий игрока II содержатся все его чистые стратегии. Если все числа qj равны 0, кроме значения qs =1, то эта стратегия означает выбор игроком II столбца с номером s.

Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбирать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш, т.е. максимизировать математическое ожидание своего выигрыша. Аналогично, игрок II должен выбирать свои смешанные стратегии так, чтобы минимизировать математическое ожидание выигрыша игрока I. Найдем математическое ожидание выигрыша игрока I, если он выбирает смешанную стратегию p = (p 1, p 2,…, p n), а игрок II – смешанную стратегию q = (q 1, q 2,…, qm), по формуле:

.

Стратегии

, ,

называются оптимальными смешанными стратегиями игроков, если выполняются неравенства

(3.3.1)

при любых смешанных стратегиях игроков p, q. В этом случае пару стратегий (p *, q *) называют ситуацией равновесия матричной игры в смешанных стратегиях, а число v * = V (p *, q *) – значением матричной игры.

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

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

Пример 3.3.1

Рассмотрим игру, в которой оба игрока одновременно объявляют одно из целых чисел. Если сумма окажется четной, то игрок I проигрывает одно очко. Если сумма окажется нечетной, то игрок I выигрывает одно очко. Стратегиями обоих игроков являются выбор четного или нечетного числа. Будем считать, что первая строка означает выбор игроком I четного числа, вторая строка – нечетного числа. Для игрока II первый столбец означает выбор четного числа, второго столбца – нечетного числа. Матрица выигрышей игрока I имеет вид

min в строке

max в столбце 1 1

Отсюда следует, что максимальное среди минимальных в строке равно -1

max min =-1

и минимальное среди максимальных в столбце равно 1

min max =1

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

первый игрок объявляет противнику, что он будет выбирать четное число с вероятностью p ₁, нечетное число – с вероятностью p ₂,

второй игрок объявляет противнику, что он будет выбирать четное число с вероятностью q ₁, нечетное число – с вероятностью q ₂. Таким образом, стратегией игрока I является выбор пары чисел

,

стратегией игрока II является выбор пары чисел

.

Так как игроки выбирают числа случайным образом, то их сумма будет случайной и, следовательно, выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбирать свои смешанные стратегии p = (p ₁, p ₂) так, чтобы получить максимальный средний выигрыш, т.е. максимизировать математическое ожидание своего выигрыша. Аналогично, игрок II должен выбирать свои смешанные стратегии q = (q ₁, q ₂) так, чтобы минимизировать математическое ожидание выигрыша игрока I.

Пусть игрок I выбирает смешанную стратегию

а игрок II - смешанную стратегию . Тогда выигрыш первого игрока равен

В общем виде математическое ожидание выигрыша игрока I, если он выбирает смешанную стратегию p = (p ₁, p ₂), а игрок II – смешанную стратегию q = (q ₁, q ₂) будет равно

Заметим, что при стратегии игрока I математическое ожидание его выигрыша равно 0 для любой смешанной стратегии игрока II q = (q ₁, q ₂), т.е. . Аналогично, при стратегии игрока II математическое ожидание выигрыша игрока I равно 0 для любой смешанной стратегии игрока I p =(p ₁, p ₂), т.е. . Следовательно, стратегия игрока I и стратегия игрока II являются оптимальными и означают, что оба игрока выбирают четное и нечетное числа с одинаковыми вероятностями. При этом средний выигрыш игрока I равен , т.е. значение этой игры равно 0. Эту игру можно назвать справедливой, т.к. в среднем ни один игрок не выигрывает.

Вопросы для самопроверки

1. Дать определение смешанных стратегий игроков I и II.

2. Как определяется выигрыш игрока I в смешанных стратегиях?

3. Дать определение ситуации равновесия в смешанных стратегиях.

4. Всегда ли существует ситуация равновесия в смешанных стратегиях?

3.4. Решение матричных игр симплекс-методом

Изучаемые вопросы:

· Формулировка матричной игры как задачи линейного программирования;

· Определение оптимальных стратегий в Excel.

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

(3.4.1)

для всех строк i и всех столбцов j.

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

max v (3.4.2)

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

для всех j = 1, 2,…, m (3.4.3)

p 1 + p 2 +…+ p n = 1 (3.4.4)

p i ≥ 0 (3.4.5)

v не имеет ограничения на знак (3.4.6)

Для определения значения игры и оптимальных стратегий игрока II необходимо решить задачу линейного программирования: найти переменные v, qj, которые минимизируют выигрыш v игрока I

min v (3.4.7)

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

для всех i = 1, 2,…, n (3.4.8)

q 1 + q 2 +…+ q m = 1 (3.4.9)

q j ≥ 0 (3.4.10)

v не имеет ограничения на знак (3.4.11)

Заметим, что задачи определения значения игры и оптимальных стратегий (3.4.2) – (3.4.6) и (3.4.7) – (3.4.11) образуют пару двойственных задач линейного программирования.

Заметим, что выигрыш игрока II равен – v. Поэтому для определения значения игры и оптимальных стратегий игрока II необходимо решить задачу линейного программирования:

найти переменные v, q j, которые максимизируют выигрыш - v игрока II

max – v (3.4.12)

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

для всех i =1, 2,…, n (3.4.13)

q 1 + q 2,+…+ q m =1 (3.4.14)

q j ≥ 0 (3.4.15)

v не имеет ограничения на знак (3.4.16)

Пример 3.4.1

Рассмотрим игру с матрицей выигрышей игрока I

Для игрока I обозначим p 1 вероятность выбора первой строки,

p 2 – вероятность выбора второй строки,

p 3 –вероятность выбора третьей строки,

p 4 – вероятность выбора четвертой строки.

Для игрока II обозначим q 1 вероятность выбора первого столбца,

q 2 – вероятность выбора второго столбца,

q 3 – вероятность выбора третьего столбца,

q 4 – вероятность выбора четвертого столбца.

Определение значения игры и оптимальной стратегии игрока II по задаче (3.4.12) – (3.4.16):

найти переменные v, q 1, q 2, q 3, q 4, которые максимизируют выигрыш - v игрока II

max – v

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

q 1 + q 2,+ q 3+ q 4 =1,

11 q 1 +12 q 2,+12 q 3+16 q 4 - v ≤ 0, (3.4.17)

9 q 1 +14 q 2,+9 q 3+8 q 4 - v ≤ 0, (3.4.18)

15 q 1 +12 q 2,+02 q 3+10 q 4 - v ≤ 0, (3.4.19)

10 q 1 +12 q 2,+10 q 3+13 q 4 - v ≤ 0, (3.4.20)

q 1≥ 0 q 2≥ 0 q 3≥ 0 q 4≥ 0,

v не имеет ограничения на знак.

Оптимальные стратегии игрока I равны значениям двойственных переменных этой задачи линейного программирования.

Смысл неравенств (3.4.17) – (3.4.20) состоит в следующем. Если игрок II использует свои оптимальные стратегии, а игрок I использует свои чистые стратегии, выбирая строки матрицы выигрышей, то его выигрыш в среднем будет не больше значения игры v.

Вопросы для самопроверки

1.Дать определение смешанных стратегий игроков I и II.

2. Как определяется выигрыш игрока I в смешанных стратегиях?

3. Дать определение ситуации равновесия в смешанных стратегиях.

4. Всегда ли существует ситуация равновесия в смешанных стратегиях?

Допустим, что матрица выигрышей игрока I имеет вид

5. Чему равен выигрыш игрока II, если игрок I всегда выбирает вторую строки?

6. Проверить равенство

(max)_i (min)_j a (i,j) = (min)_j (max)_i a (i,j)

Существует ли решение игры в чистых стратегиях?

7. Найти выигрыш игрока I, если игрок I выбирает смешанную стратегию

, а игрок II выбирает смешанную стратегию .

Поиск по сайту: