ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №4

Транспортная задача (ТЗ)

Простейшими ТЗ являются задачи о перевозках некоторого однородного груза из пунктов отправления в пункты назначения, или от поставщиков к потребителям, при обеспечении минимальных затрат на перевозки. Как правило, начальные условия таких задач записываются в таблицу. Для m поставщиков и n потребителей таблица имеет вид:

Мощность поставщиков	Спрос потребителей
N1	N2	---	Nn
	a11 x11	a12 x12	---	a1n x1n
	a21 x21	a22 x22	---	a2n x2n
---	---	---	---	---
	am1 xm1	am2 xm2	---	amn xmn

Показатели a_ij означают затраты на перевозку единицы груза от i-го поставщика к j-му потребителю ( i = 1; 2; ...; m; j = 1; 2; ...; n);

M_i - мощность (предложение) i- го поставщика;

N_j - спрос j - го потребителя;

x_ij - поставка (количество груза), от i-го поставщика к j-му потребителю.

Суммарные затраты на перевозку всего груза выражаются целевой функцией

Если суммарная мощность поставщиков (предложение) равна суммарному спросу потребителей, то соответствующая модель ТЗ называется закрытой.

,

Если , то модель ТЗ называется открытой.

Алгоритм решения ТЗ

1. Определяют модель ТЗ.

Если модель ТЗ открытая, то в случае

(объем мощностей поставщиков превышает объем спроса потребителей) вводят фиктивного потребителя ФN со спросом равным разности

Если

(объем спроса потребителей превышает объем мощностей поставщиков), то вводят фиктивного поставщика ФМ с мощностью равной разности

Затраты на перевозки к ФN или ФМ считают равными нулю (или произвольными, но одинаковыми).

2. Составляют первоначальный план распределения поставок по методу «северо-западного угла» или методу учета наименьших затрат.

При этом должно быть заполнено клеток.

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

3. Полученное распределение поставок оценивают методом потенциалов.

При этом если все оценки клеток окажутся неотрицательные, то полученное распределение является оптимальным.

Тогда подсчитывают суммарные затраты на перевозки.

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

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

5. Полученное распределение поставок опять проверяют на оптимальность методом потенциалов.

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

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

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

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

1. Первоначальное распределение поставок

методом «Северо–западного угла»

Сначала заполняют клетку (1.1): . Если M₁ не полностью использована в (1.1), то заполняют клетку (1.2): и так далее пока не будет полностью использована мощность M₁. Оставшиеся незаполненные клетки в первой строке мысленно вычеркиваются. Затем переходят ступенькой к распределению мощности M₂ по второй горизонтали и так далее пока не дойдут до клетки в m-й строке.

После распределения поставок необходимо выполнить контроль:

1) - весь объем продукции у поставщиков должен быть вывезен;

2) - все заказы удовлетворены;

3) - имеем закрытую модель ТЗ;

4) число заполненных грузами клеток

где m – число строк, n – число столбцов.

Пример 1. Выполнить распределение поставок по методу «Северо – западного угла» в транспортной задаче:

- вектор поставщиков,

- вектор потребителей,

- матрица тарифов.

Решение.

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

Потребители   Поставщики	В1	В2	В3	В4
А1 – 70			-	-
А2 – 80	-			-
А3 – 50	-	-

2. Распределим поставки по методу «Северо–западного угла».

Для этого в клетку (1; 1) запишем груз . Так как спрос потребителя В₁ выполнен, мысленно вычеркиваем клетки (2; 1) и (3;1). У первого поставщика осталось 20 единиц груза. В клетку (1; 2) запишем груз . Так как мощность первого поставщика выбрана вся, то клетки (1; 3) и (1; 4) мысленно вычеркиваем. Переходим на вторую горизонталь. Спрос второго потребителя не удовлетворен. В клетку (2; 2) запишем груз . Так как спрос второго потребителя выполнен, то мысленно вычеркнем клетку (3; 2). У второго поставщика осталось еще 30 единиц груза. В клетку (2; 3) запишем груз . Так как мощность второго поставщика выбрана полностью, то мысленно вычеркнем клетку (2; 4). Переходим на третью горизонталь. Спрос третьего потребителя не удовлетворен. В клетку (3; 3) запишем поставку: . Спрос третьего потребителя удовлетворен. Мысленно вычеркиваются клетки в третьем столбце под клеткой (3; 3). У третьего поставщика осталось 40 единиц груза. Четвертому потребителю требуется 40 единиц груза. В клетку (3; 4) запишем поставку . Спрос четвертого потребителя удовлетворен. Мысленно вычеркиваются клетки в четвертом столбце после клетки (3; 4). Вся мощность третьего потребителя выбрана – мысленно вычеркиваются клетки в третьей строке после клетки (3; 4).

Распределение поставок закончили. Выполним контроль:

1. Баланс сохранен (все мощности использованы, все спросы удовлетворены).

2. Число заполненных клеток должно быть . Выполнено.

Получили опорный план:

Вычислим суммарные затраты всех поставок:

2. Первоначальное распределение поставок

методом учета наименьших затрат

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

Пример 2. Выполнить распределение поставок с учетом наименьших затрат для ТЗ в примере 1.

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

Потребители   Поставщики	В1	В2	В3	В4
А1 – 70	-		-	-
А2 – 80			-
А3 – 50		-		-

2. Распределим поставки с учетом наименьших затрат.

Выберем клетки с наименьшими тарифами. Такими клетками являются – одна клетка (3; 3), с тарифом 1. Заполним ее поставкой: . Так как спрос третьего потребителя удовлетворен, то клетки (1; 3) и (2; 3) мысленно вычеркиваем. У третьего поставщика осталось 10 единиц груза. Далее выбираем клетки с тарифами 2. Таковыми являются клетки (1; 2) и (3; 1). Поставки: в клетку (1; 2): ; в клетку (3; 1): . Спрос второго потребителя выполнен, значит, мысленно вычеркиваем клетки (2; 2) и (2; 3). Мощности первого и третьего поставщиков изъяты полностью, значит, мысленно вычеркиваем клетки (1; 1), (1; 4) и (3; 4). Далее выбираем клетку (2; 1) с оставшимся наименьшим тарифом в 4 - . Спрос первого потребителя удовлетворен, у второго поставщика осталось еще 40 единиц груза. Невычеркнутой осталась клетка (2; 4) с тарифом 7. В нее заполним поставку четвертому потребителю от второго поставщика - .

Проведем контроль.

1. Баланс сохранен.

2. Число заполненных клеток: 5 – условие не выполнено. В этом случае в произвольную клетку, например, (2;2) дадим поставку равную 0. Тогда число заполненных клеток поставками будет равно 6, то есть столько, сколько должно быть.

Ответ: опорный план

3. Нахождение оптимального плана распределение поставок

методом потенциалов

Метод потенциалов служит для определения оптимальности полученного распределения поставок.

Потенциалы вводят для поставщиков: V_i и для потребителей: U_j. Всего потенциалов будет:

.

Для получения значений потенциалов пользуются следующим правилом.

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

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

Продемонстрируем решение по условию примера 1.

Построим таблицу.

Bj Ai	В1	В2	В3	В4	Vi
А1 – 70			(-1)	(-2)
А2 – 80	(-2)			(-2)	-1
А3 – 50	(0)	(5)
Uj	-5	-2	-4	-8

Пусть нулю равно значение V₁, т.е. . Тогда согласно правилу, получим: оценка клетки (1; 1) равна:

оценка клетки (1; 2) равна:

оценки других клеток равны:

Далее находятся оценки свободных клеток по формуле

.

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

Для нашего примера оценки незаполненных клеток равны:

	оценки клеток внесены в таблицу 3 – записаны в кружках.

Проверяем критерий оптимальности: опорный план оптимальный, если оценки всех свободных клеток неотрицательны.

Опорный план, построенный по методу «Северо-западного угла» не являет оптимальным, так как есть оценки клеток меньше нуля. Для получения оптимального плана следует выполнить перераспределение поставок. Для этого строят цикл для клетки с наименьшей отрицательной оценкой.

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

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

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

Построение цикла проиллюстрируем на примере построения цикла для клетки (2;1).

№2 (1; 1) (50) 0 №3 (1; 2) (20) 70

№1 (2;1) (0) 50 №4 (2; 2) (50) 0

.

Так как освободилось две клетки, а должна освободится только одна, то оставим нулевую поставку, например, в клетке (2; 2).

Заносим новый план в таблицу.

Bj Ai	В1	В2	В3	В4	Vi
А1 – 70	(2)	70 (0)	(-1)	(-2)
А2 – 80	50 (0)	0 (0)	30 (0)	(-2)
А3 – 50	(2)	(5)	10 (0)	40 (0)
Uj	-4	-3	-5	-9

Проводим контроль:

1) Баланс – сохранен.

2) Число заполненных клеток – 6 – выполнено.

По методу потенциалов определяем оценки клеток полученного распределения. Так как есть отрицательные оценки, то полученное распределение не является оптимальным. Можно построить циклы для клеток (1; 4) или (2; 4).

Опять построим цикл для клетки (2; 4), т. к. он проще:

№4 (2; 3) (30) 0 №1 (2; 4) (0) 30

№3 (3;3) (10) 40 №2 (3; 4) (40) 10

.

Занесем новое распределение поставок в таблицу.

Bj Ai	В1	В2	В3	В4	Vi
А1 – 70	(2)	70 (0)	(1)	(0)
А2 – 80	50 (0)	0 (0)	(2)	30 (0)
А3 – 50	(0)	(1)	40 (0)	10 (0)
Uj	-4	-3	-3	-7

Проведем контроль:

1) Баланс – сохранен.

2) Число заполненных клеток – выполнено.

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

Ответ:

;

Примечание.

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

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

Теория игр – это математическая теория конфликтных ситуаций.

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

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

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

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

Целью теории игр является определение оптимальной стратегии для каждого игрока.

В ходе игры каждый игрок выбирает ту или иную стратегию.

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

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

Игра состоит из двух ходов: игрок А выбирает одну из своих возможных стратегий ; игрок В выбирает одну из своих возможных стратегий .

При этом игрок А получает выигрыш, который обозначим через , а игрок В получает выигрыш, который обозначим через .

Так как сумма выигрышей должна быть равна 0, то

.

Тогда, если обозначить , то

.

Парная игра с нулевой суммой формально задается системой чисел

,

то есть матрицей

,

элементы a_ij которой определяют выигрыш первого игрока (лица А) и соответственно проигрыш второго (лица В), если первый игрок выбирает i – ю строку (А_i стратегию), а второй игрок выбирает j – й столбец (В_j стратегию).

Матрица М называется платежной или матрицей игры.

В каждой i – й строке игроку А гарантирован минимальный выигрыш, то есть . Игрок А стремится максимизировать свой минимальный выигрыш, то есть получить

(1)

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

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

(2)

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

Примечание. Всегда .

Если , то имеем в матрице М элемент

который является максимальным в j – м столбце и минимальным в i – й строке.

Этот элемент называется седловой точкой.

Его индексы: - указывает оптимальную стратегию игрока А,

- указывает оптимальную стратегию игрока В.

Значит, в этом случае матричная игра решается в чистых стратегиях: игрок А получает оптимальную стратегию , игрок В получает оптимальную стратегию , цена игры .

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

.

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

.

Основная теорема теории игр

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

Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры:

.

Применение игроком А оптимальной стратегии обеспечивает ему выигрыш не менее цены игры V, то есть

.

Применение игроком В оптимальной стратегии обеспечивает ему проигрыш, не превышающий цены игры V, то есть

.