Методы оптимальных решений

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

1) строится графическое изображение игры для игрока А;

2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры v;

3) определяется пара стратегий игрока В, пересекающихся в точке оптимума. Эти стратегии и являются активными стратегиями игрока В.

Таким образом, игра 2xn сведена к игре 2x2, которую более точно можно решить алгебраическим методом.

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

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

Пример. Найти решение игры, платежная матрица которой имеет вид:

 

Bj   Ai	B1	B2	B3
A1	2	5	8
A2	7	4	3

 

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

Точка N (максимин) является точкой оптимума. В этой точке пересекаются линии, соответствующие активным стратегиям В1 и В2 игрока В. Таким образом, исключая стратегию В3, получаем матричную игру 2x2 с платежной матрицей вида

Bj   Ai	B1	B2
A1	2	5
A2	7	4

 

Используя алгебраический метод решения этой игры, получаем точное решение

;          ;

;            ;

.

Ответ: ;  ;  .

 

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

Задание 1

Допустим предприятие выпускает три вида изделий (И1, И2, И3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблицах. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков ресурсов. Найти решение задачи симплексным методом с представлением всех симплексных таблиц (промежуточных шагов решения) и проанализировать полученные результаты. Составить двойственную задачу. Определить двойственные оценки из последней симплексной таблицы и провести анализ последней симплексной таблицы.

Таблица 1

	И1	И2	И3	З
Р1	7	8	3	81
Р2	4	1	6	68
Р3	5	1	7	54
П	2	5	6

Решение.

Пусть – объемы продукции планируемой к выпуску. Математическая модель прямой задачи:

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

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

Составим первую симплекс-таблицу. Первым опорным планом является план . На этом плане значение целевой функции равно 0.

Таблица 2

Первая симплекс-таблица

БП	Сб, сi	В, bi	Х1	Х2	Х3	Х4	Х5	Х6
			2	5	6	0	0	0
Х1	0	81	7	8	3	1	0	0	27
Х3	0	68	4	1	6	0	1	0	11,3
Х5	0	54	5	1	7	0	0	1	7,7
		0	-2	-5	-6	0	0	0

 

Заполним последнюю строчку первой симплекс-таблицы, считая по формуле:

 получились отрицательные, наибольшее  по модулю значение: , поэтому вводим в базис вектор Х3. Чтобы определить, какой вектор нужно вывести из базиса, заполним столбец оценок θ симплекс-таблицы:

следовательно исключаем из базиса вектор Х6. Элемент является разрешающим.

Перейдем к новому опорному плану, осуществив перерасчет симплекс-таблицы:

1. В столбце «базис» в r-й строке оставим вектор Х3, а в столбце Сб в r-й строке записываем ck.

2. Элементы направляющей строки, начиная с третьего столбца, делим на разрешающий элемент:

3. Элементы других строк преобразуются по формулам:

Таблица 3

Вторая симплекс-таблица

БП	Сб, сi	В, bi	Х1	Х2	Х3	Х4	Х5	Х6
			2	5	6	0	0	0
X4	0	57,857	4,857	7,571	0	1	0	-0,429	7,6
X5	0	21,714	-0,286	0,143	0	0	1	-0,857	152
X3	6	7,714	0,714	0,143	1	0	0	0,143	54
		46,286	2,286	-4,143	0	0	0	0,857

 

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

В базис вводится вектор Х2, то выводится из базиса вектор Х4. Получаем третью симплекс-таблицу.

Таблица 4

Третья симплекс-таблица

БП	Сб, сi	В, bi	Х1	Х2	Х3	Х4	Х5	Х6
			2	5	6	0	0	0
Х2	5	7,642	0,642	1	0	0,132	0	-0,057
Х5	0	20,623	-0,377	0	0	-0,019	1	-0,849
Х3	6	6,623	0,623	0	1	-0,019	0	0,151
		77,943	4,943	0	0	0,547	0	0,623

 

Поскольку среди оценок нет отрицательных, то это значит, что найдено оптимальное решение. Из таблицы видно, что при оптимальном плане следует выпускать изделий вида И2 в количестве 7,6 штук, изделий И3 – 6,6 штук. При этом остаются неиспользованными 20,623 кг ресурса второго вида, а общий доход от продажи изделий составит 77,943 ден. ед. Из таблицы также видно, что оптимальным решением двойственной задачи является , поскольку решение двойственной задачи находится в столбцах, соответствующих дополнительным переменным исходной задачи (Х4, Х5, Х6).

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

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

Выпускать продукцию типа И1 невыгодно, а принудительный выпуск единицы данной продукции уменьшит доход на 4,943 ден. ед. и будет равен 73 ден. ед.

Так, увеличение количества ресурсов первого вида на 1 кг приведет к новому оптимальному плану производства изделий, при котором доход возрастет на 0,547 и станет равным 78,49 ден. ед. При этом числа, стоящие в столбце Х4 последней симплексной таблицы, покажут, что это может быть достигнуто за счет увеличения выпуска изделий И2 на 0,132 единицы и сокращения выпуска изделий И3 на 0,019 единиц. Использование ресурча второго вида увеличится при этом на 0,019 кг.

Также увеличение на 1 кг ресурса третьего вида дает новый оптимальный план, при котором доход возрастет на 0,623 ден. ед. и составит 78,566 ден. ед. Это будет достигнуто за счет увеличения выпуска изделия И3 на 0,151 единицу и уменьшения выпуска изделия И2 на 0,057 единиц, причем объем используемого ресурса второго вида уменьшится на 0,849 кг.

Вычислим минимальное значение целевой функции двойственной задачи:

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

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

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

 

Задание 2

Решить задачу графическим и аналитическим методами. Х1 и Х2 принимают неотрицательные значения.

а)

.

б)

.

Решение.

а)

Решим задачу симплекс-методом. Приведем задачу к каноническому виду, введя четыре переменные Х3, Х4, Х5, Х6.

Первым опорным планом является план . Составим симплекс-таблицу.

Таблица 5

Номер итерации	БП	Сб	А0	Х1	Х2	Х3	Х4	Х5	Х6
				-5	2	0	0	0	0
0	Х3	0	57	3	3	1	0	0	0	19
	Х4	0	60	-12	15	0	1	0	0	4
	Х5	0	621	23	27	0	0	1	0	23
	Х6	0	90	18	-10	0	0	0	1
			0	0	5	-2	0	0	0	0
Номер итерации	БП	Сб	А0	Х1	Х2	Х3	Х4	Х5	Х6
				-5	2	0	0	0	0
1	Х3	0	45	5,4	0	1	-0,2	0	0
	Х2	2	4	-0,8	1	0	0,06666667	0	0
	Х5	0	513	44,6	0	0	-1,8	1	0
	Х6	0	130	10	0	0	0,66666667	0	1
			8	13	6	8	8	8	8