лекции(II курс)

Отметим, что количество заполненных клеток по-прежнему 8.

F2 = 50 + 75 + 240 + 135 + 75 + 60 + 160 + 75 = 870 äåí.åä.

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

6.3. Перераспределение поставок.

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

(перераспределение) поставок происходит в цикле.

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

Теорема. Если распределение в таблице таково, что заполнено ровно k+l−1 клеток,

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

Циклы могут иметь различную конфигурацию:

Размер поставки, которая перемещается по циклу равен min числу из поставок в клетках, отмеченных знаком −.

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

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

zij = cij + ui + vj.

Числа ui è vj подбираются таким образом, чтобы оценки заполненных клеток равня-

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

111

Пример. Оценим, например, распределение поставок, приведенное в последней таб-

ëèöå
		85		65				80			75			70		vj
	100	4		2				3			1			2		-4
					25								75
	125	6		5				3			4			3		-6
									80						45
	75	1		2				5			6			5		-1
			75
	75	6		4				5			2			3		-6
			10		40										25
	ui	0		2				3			3			3
Для удобства выпишем все оценки в виде матрицы оценок
					0	0		2	0		1
					0	1		0	1		0
									−
					0	3		7			7
					0	0		2		1	0

Экономический смысл оценок.

Åñëè zij < 0, это означает, что изменение поставки в эту клетку уменьшит стоимость перевозки 1 ед. груза на zij, т.е. выгодные клетки.

Åñëè zij > 0, то изменение поставки в эту клетку увеличит стоимость перевозки 1 ед.

груза на zij, т.е. невыгодные клетки.

Отсюда вытекает критерий оптимальности при решении ТЗ: если в матрице оценок клеток нет отрицательных элементов, то полученное распределение поставок оптимально.

Отметим, что полученное распределение в примере, не является оптимальным. Замечание. Наличие в матрице оценок, не содержащей отрицательных оценок, нуле-

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

6.5. Открытая модель ТЗ.

Как было отмечено выше, если суммарная стоимость поставщиков не равна суммарному потребительскому спросу, то модель ТЗ называется открытой. Здесь возможны два случая:

1) Объем мощностей поставщиков меньше суммарного спроса потребителей

k	l
∑	∑
ai <	bj;
i=1	j=1

2) Объем мощностей поставщиков больше суммарного спроса потребителей

k	l
∑	∑
ai >	bj;
i=1	j=1

112

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

Чтобы замкнуть модель в первом∑l случае,∑k вводят фиктивного поставщика, мощность которого принимается равной j=1 bj > i=1 ai. В качестве коэффициентов затрат на

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

Замечание. Считая число заполненных клеток по формуле k + l − 1, в число постав-

щиков включаем и фиктивного.

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

счет мощностей реальных поставщиков.	∑	∑
Коэффициенты затрат у фиктивного потребителя также лучше всего
В случае 2) вводится фиктивный потребитель, спрос которого равен		ik=1 ai − jl =1 bj.

принять равными

íóëþ.

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

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

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

что оно является базисным, т.е. число заполненных клеток равно k+l−1. Если базисность

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

3) Проверяем критерий оптимальности методом оценок клеток. Если критерий опти- мальности выполнен, то вычисляем Fmin и записываем ответ. В противном случае пере-

ходим к пункту 4.

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

к поставкам клеток со знаком + и отнимается из поставок клеток со знаком −. Ïîëó-

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

матрице оценок клеток не будет отрицательных элементов. Пример. Решить ТЗ.

	20	20	30	40
20	4	3	2	1
30	2	3	5	6
50	6	7	9	12

Проверим модель задачи, в данном случае модель открытая, введем фиктивного по-

113

ставщика с мощностью 10.
		20	20	30	40
	20	4	3	2	1
	30	2	3	5	6
	50	6	7	9	12
	Ô10	0	0	0	0

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

	20	20	30	40
20	4	3	2	1
	20			0
30	2	3	5	6
		20	10
50	6	7	9	12
			20	30
Ô10	0	0	0	0
				10

Теперь количество заполненных клеток 4 + 4 −1 = 7. Проверим на оптимальность данное

распределение поставок, допишем строку и столбец и подберем потенциалы ui è vj, òàê чтобы оценки заполненных клеток равнялись нулю:

	20	20	30	40		vj
20	4	3	2	1		-4
	20				0
30	2	3	5	6		-11
		20	10
50	6	7	9	12		-15
			20		30
Ô10	0	0	0	0		-3
					10
ui	0	8	6	3

Составим матрицу оценок для данного распределения:

−9		0	0	−2			не оптимальна.
	0	7	4	0
	−3					−
		5	3	0
	−	0	0	0
	9

Составим цикл для клетки с наименьшей оценкой, например, для клетки 21.

114

4 - 20 1 + 0

2 + - 5 - 10

9 + 20 12 -30

По циклу перемещается величина, равная min{10, 20, 30} = 10. Выполним перераспределение поставок, получим

	20	20	30	40		vj
20	4	3	2	1		-4
	10				10
30	2	3	5	6		-2
	10	20
50	6	7	9	12		-15
			30		20
Ô10	0	0	0	0		-3
					10
ui	0	-1	6	3

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

	0	−2	4	0
	0	0	9	7

−9 −9 0 0 −3 −3 3 0

которая так же является не оптимальной. Дадим поставку в клетку с номером 32. Составим цикл для этой клетки

4 - 10										1	+		10
2	+				3	-
			10					20
					7	+		-		12	-
													20

По циклу перемещается величина, равная min{10, 20} = 10. Выполним перераспреде-

115

ление поставок, получим

		20					20				30	40	vj
	20	4					3				2	1	5
												20
	30	2					3				5	6	-2
				20				10
	50	6					7				9	12	-6
								10			30	10
	Ô10	0					0				0	0	6
												10
	ui	0					-1				-3	-6
Составим матрицу оценок							−2
			0	0	0						не оптимальна.
			9	7	4		0
			6	5	3		2		−
			0	0	0		0

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

3 - 10 6 + -

7	+ 10		12 -
			10

По циклу перемещается величина, равная min{10, 10} = 10, т.к. клетки со знаком −

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

		20			20				30		40		vj
	20	4			3				2		1		3
												20
	30	2			3				5		6		-2
			20				0					10
	50	6			7				9		12		-6
							20			30
	Ô10	0			0				0		0		4
												10
	ui	0			-1				-3		-4
Составим матрицу оценок:
			0	0	0	0				оптимальна.
			7	5	2	0
			4	3	1	0		−
			0	0	0	2

116

После этого переходим к подсчету минимальных затрат

Fmin = 20 + 40 + 60 + 140 + 270 = 530 äåí.åä.

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

117

Тема 7. Основы теории игр и принятие решений.

Понятие об игровых моделях. Платежная матрица. Нижняя и верхняя цены игры. Седловая точка. Основная теорема теории игр. Решение игры в чистых и смешанных стратегиях. Сведение задач теории игр к двойственным задачам ЛП.

7.1. Основные понятия.

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

1)определенность;

2)ðèñê;

3)неопределенность;

4)конфликт.

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

Ðèñê промежуточный случай между определенностью и неопределенностью. Рисковые ситуации часто встречаются на практике. Для условий риска используется функция распределения вероятностей наступления событий. Если при решении задач линейного программирования, показателем качества решения является максимум прибыли, то для условий риска используется другой критерий: математическое чистого дохода, математи-

ческое ожидание прибыли.

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

матрицы.

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

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

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

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

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

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

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

Личный сознательный выбор игроков одного из возможных действий. Случайный случайно выбранное действие.

118

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

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

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

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

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

Рассмотрим парную конечную игру: пусть игрок A располагает m стратегиями A1, A2, . . . Am, а игрок B n стратегиями B1, B2, . . . , Bn. В этом случае говорят, что игра имеет размерность m × n. В результате выбора стратегий AiBj, i = 1, . . . , m, j = 1, . . . , n однозначно определяется исход игры, aij выигрыш A, −aij проигрыш B. Пусть зна- чения aij известны для каждой пары AiBj

Матрица P = (aij), элементами которой являются выигрыши называется платежной

матрицей или матрицей игры. Платежная матрица является экономико математиче- ской моделью теории игр.

	a11	a12	. . . a1n		.
P =	a21	a22	. . .	a2n
		a. . .	.. .. ..	a. . .
	a. . .
	m1	m2		mn

Пример. Составим платежную матрицу для игры "поиск": игрок A может спрятаться в одном из двух убежищ (I или II), игрок B ищет игрока A, и если находит, то получает штраф 1 ден.ед от A, в противном случае платит игроку A 1 äåí. åä.

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

A1, в убежище II A2. Игрок B может искать первого игрока в убежище I стратегия B1, в убежище II стратегия B2. Если игрок A находится в убежище I и там его обнаруживает игрок B, т.е. осуществляется пара стратегий A1B1, то игрок A платит штраф, т.е. a11 = −1, аналогично получаем a22 = −1. Очевидно, что стратегии A1B2 è A2B1 äàþò игроку A выигрыш 1, поэтому a21 = a12 = 1, таким образом для игры "поиск"размера 2 × 2 получаем платежную матрицу

()

P =	−1	1 .
	1	−1

7.3. Седловая точка.

Рассмотрим парную игру m × n с платежной матрицей P, определим для игрока A наилучшую среди его стратегий. Выбирая стратегию Aj, игрок A должен рассчитывать, что игрок B ответит на нее той из стратегий Bi, чтобы выигрыш A был минимален.

Обозначим αi = minj=1;:::;n aij по строкам. Среди всех чисел αi выберем наибольшее и обозначим его α.

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

α = max min aij.

i=1;:::;m j=1;:::;n

119

Аналогично игрок B заинтересован в том, чтобы уменьшить выигрыш игрока A и выбирая стратегию Bj учитывает максимально возможный выигрыш игрока A.

Обозначим βj = maxi=1;:::;m aij по столбцам. Среди всех βj выберем наименьшее и обо- значим его β.

Определение. β верхняя цена игры или минимакс. Это максимальный гарантированный проигрыш игрока B, β вычисляется по формуле

β = min max aij.

j=1;:::;n i=1;:::;m

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

	1	5	3
	21	1	3
	2	4	2
P =
−		2	0

Решение. Для удобства вычисления, добавим к матрице еще одну строчку и столбец:

				αi
	1	5	3	1
	2	4	2	2
	8	2	0	0
	-1	1	3	-1
				α = 2
βj	8	5	3	β = 3

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

не зависящий от поведения игрока B выигрыш ν, а игрок B добивается минимально гарантированного не зависящего от поведения A проигрыша.

В противном случае, в отсутствии седловой точки α ≠ β, цена игры заключена в

пределах

α < ν < β.

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

	5	6	8
	7	6	6
P =	9	7	8	.

Решение. Допишем к матрице еще одну строку и столбец

				αi
	5	6	8	5
	9	7	8	7
	7	6	6	6
βj				α = 7
	9	7	8	β = 7

Ò.ê. α = β, то седловая точка есть.

120