Документ: Учебное пособие Немирко Манило, страницы 91-95

L = x1 + x2 +... + xm

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

Нахождение SB* . Оптимальная стратегия SB* находится аналогично. Разница заключается в том, что игрок B стремится не максимизировать, а минимизировать выигрыш, а значит максимизировать величину 1γ. Следовательно, вместо условий (3.13) должны соблюдаться условия

		a11y1 +a12 y2	+... +a1n yn ≤1;
		a21y1 +a22 y2	+... +a2n yn ≤1;	(3.14)
		...............................................
		am1y1 +am2 y2 +... +amn yn ≤1,
где y j = q j γ,	j =1,	2, ..., n .
Требуется	так	выбрать неотрицательные значения		переменных

y1, y2, ..., yn , чтобы они удовлетворяли условиям (3.14) и обращали в максимум линейную функцию

L = y1 + y2 +... + yn =1γ

или, что то же самое, обращали в минимум линейную функцию L′= −L:

L′= −y1 − y2 −... − yn = −1γ.

Таким образом, любая конечная игра m ×n сводится к паре задач линейного программирования.

Пример 3.8. Рассмотрим игру «Три пальца», которая формулируется следующим образом. Два игрока одновременно и независимо показывают 1, 2 или 3 пальца. Выигрыш равен сумме показанных пальцев. Если это число четное, то выигрывает игрок А, а если нечетное, то выигрыш достается игроку В. Платежная матрица этой игры имеет вид, как в табл. 3.25.

91

			Таблица 3.25

Ai		Bj

	B1	B2		B3
	B1	B2		B3

A1	2	–3		4
A2	–3	4		–5
A3	4	–5		6

			Таблица 3.26

Ai		Bj

	B1	B2		B3
	B1	B2		B3

A1	7	2		9
A2	2	9		0
A3	9	0		11

Прибавив ко всем членам этой матрицы число М = 5, сделаем их неотрицательными. Тогда матрица примет вид, как в табл. 3.26.

Найдем стратегию S*A . Для этого по полученной матрице составим с и- стему линейных неравенств (3.13):

7x1 +2x2 +9x3 ≥1;

2x1 +9x2 ≥1;

9x1 +11x3 ≥1,

а функцию L = x1 + x2 + x3 устремим к минимуму.

Внимание! Неравенства составляются по столбцам этой матрицы. Введя новые переменные y1, y2, y3, которые, как и x1, x2, x3 , должны

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

y1 = 7x1 +2x2 +9x3 −1;
y2 = 2x1 +9x2 −1;
y3 = 9x1 +11x3 −1.	(n = 6) – и 3 уравнения
Получаем 6 переменных: x1, x2, x3, y1, y2, y3	(n = 6) – и 3 уравнения
(m = 3), следовательно, n −m = 3. Как видно из пр	иведенных выражений,

нужны 3 свободные переменные. Выберем в качестве свободных x1, x2, x3 . Тогда y1, y2, y3 – базисные переменные. Пробуем первое опорное решение: x1 = x2 = x3 = 0 . Это решение недопустимо, так как все переменные y1, y2, y3 в этом случае становятся отрицательными.

Для нахождения опорного решения нужно шаг за шагом обменивать базисные переменные со свободными (так, чтобы число отрицательных сво-

92

бодных членов уменьшалось или при этом убывали их абсолютные величины). Осуществим замену переменных:

x3 ↔ y3

и переразрешим систему уравнений относительно новых базисных переменных y1, y2, x3. Тогда получим систему уравнений

y1 = −114 x1 +2x2 +119 y3 −112 ; y2 = 2x1 +9x2 −1;

x3 = −119 x1 +111 y3 +111 .

Пробуем следующее опорное решение: x1 = x2 = y3 = 0 . Оно также не подходит, поскольку y1 = −112 , y2 = −1. Но это решение лучше предыдуще-

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

x2 ↔ y2 ;

			y	= −	80 x		+ 2 y				2		+			9		y	3	+		4	;
			y	= −	80 x		+ 2 y						+		11			y		+	99		;
			1		99	1		9							11						99
			x	= −	2 x +			1 y		2		+		1		;
			2		9	1		9		2				9
			x	= −	9	x	+		1	y		3		+		1		.
			x	= −	11	x	+			y				+				.
			3		11	1		11								11									1					1
	Пробуем опорное решение					x		= y		2		= y				3	= 0 ,				при этом x			=	1	,	x	=		1	,
	Пробуем опорное решение					x		= y				= y					= 0 ,				при этом x			=	9	,	x	=	11		,
						1																	2		9		3		11
y =		4	. Все переменные положительны,													поэтому							это решение				является
y =	99		. Все переменные положительны,													поэтому							это решение				является
1	99

опорным. Вычислим целевую функцию

L = x1 + x2 + x3 = − 994 x1 + 19 y2 +111 y3 + 9920 .

В нашей опорной точке L = 9920 . Так как коэффициент при x1 имеет от-

рицательный знак, то, сделав x1 больше нуля, можно еще значительнее уменьшить L. Однако при этом надо сделать равной нулю какую-то переменную из базисных ( y1, x2, x3) . Из последней системы уравнений видно, что

93

при увеличении x1 быстрее всего станет равным нулю переменная y1. Поэтому нужно снова осуществить замену переменных:

x1 ↔ y1;

x1 = − 8099 y1 + 1140 y2 + 8081 y3 + 201 ;

			x =			11 y +				1		y		2	−		9	y +					1	;
			x =			11 y +			20			y			−	40		y +				10		;
			2			40		1	20							40			3			10
			x =			81 y +			9			y	2		−	59 y			3		+	1		;
			x =			81 y +			40			y			−	59 y					+	20		;
			3			80		1	40							80						20
			L =				1	y +			1	y		2	+		1	y		3	+	1 .
			L =			20		y +	10			y			+	20		y			+	1 .
						20		1	10							20						5				1
Полагая y	= y	2	= y	3	= 0 ,			получаем									опорное							решение x	= x =	1	,
Полагая y	= y		= y		= 0 ,			получаем									опорное							решение x	= x =		,
1																								1	3	20
																										20

x2 = 101 , L = 15 . Это – оптимальное решение, так как в L все коэффициенты

положительны и никакое увеличение y1, y2, y3 сверх нуля не приведет к

уменьшению значения целевой функции.

Итак, оптимальное решение основной задачи ЛП найдено. Теперь найдем решение нашей игры 3×3:

	γ′=		1	= 5; γ = γ′−5 = 0 ,
	γ′=		L	= 5; γ = γ′−5 = 0 ,
	1		min				1				1 .
а вероятности p1 = x1γ′=	1	; p2 = x2γ′=					1	;	p3	= x3γ′=	1 .
	4						2				4
		*			1	,	1	,	1
Оптимальная стратегия SA =					4	,	2	,	4	, а цена игры γ = 0 .
					4		2		4

Аналогично решается задача поиска оптимальной стратегии SB* игрока

*	1	,	1	,	1
B . Можно показать, что SB =	4		2		4	.

94

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

1.Клементьев А. А. Разработка количественных моделей для решения задач управления в здравоохранении. – М.: Наука, 1985. – 125 с.

2.Кант В. И. Математические методы и моделирование в здравоохранении. – М.: Медицина, 1987. – 224 с.

3.Биотехнические системы: Теория и проектирование: Учеб. пособие / В. М. Ахутин, А. П. Немирко, Н. Н. Першин и др.; Под ред. В. М. Ахутина. – Л.: Изд-во Ленингр. ун-та, 1981. – 220 с.

4.Шортлифф Э. Х., Буканан Б. Г., Фейгенбаум Э. А. Формальное представление знаний для принятия решений в медицине: Обзор автоматизированных средств принятия клинических решений // ТИИЭР. – 1979. – Т. 67,

№9. – С. 30–52.

5.Ластед Л. Введение в проблему принятия решений в медицине. – М.: Мир, 1971. – 282 с.

6.Вентцель Е. С. Исследование операций: задачи, принципы, методология. – М.: Наука, 1988. – 208 с.

7.Вентцель Е. С. Исследование операций. – М.: Сов. радио, 1972. –

552 с.

8.Хай Г. А. Теория игр в хирургии. – Л.: Медицина, 1978. – 224 с.

9.Головкин Б. А. Машинное распознавание и линейное программирование. – М.: Сов. радио, 1973. – 100 с.

10.Проблемы медицинской кибернетики / О. П. Минцер, Л. П. Чепкий, А. А. Цыганий, С. Я. Заславский. – М.: Наука, 1972. – 311 с.

11.Быховский М. Л., Вишневский А. А. Кибернетические системы в медицине. – М.: Наука, 1971. – 407 с.

12.Превозванский А. А. Распознавание абстрактных образов как задача линейного программирования // Изв. Академии наук СССР. Сер. Техническая кибернетика. – 1965. –№ 4. С. 41–44.

13.Таха Х. А. Введение в исследование операций. 6-е изд. //Пер. с англ. – М.: Вильямс, 2001. – 912 с.

14.Вагнер Г. Основы исследования операций: В 3 т. – М.: Мир, 1972–

1973. – Т. 3.

95

Материал: Учебное пособие Немирко Манило

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

Смотрите также: