Решение задачи линейного программирования графическим и симплекс-методом. Решение игры с заданными платежными матрицами

Задание

1. Решить задачу линейного программирования графическим и симплекс-методом.

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

3. Решить игру с заданными платежными матрицами а)                                               б)

1. Решить задачу линейного программирования графическим и симплекс-методом.

1) Графический способ

Строим опорную область.

Рисунок 1 – Опорная область

Максимальному значению целевой функции соответствуют значения

.

Значение целевой функции при этом:

2) Симплекс-метод.

Приводим систему к канонической форме, вводим выравнивающие коэффициенты :

Базисному решению соответствуют нулевые значения свободных переменных    ().

Строим симплекс-таблицу.

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

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

Таблица 1 – Симплекс-таблица

		Базис
				1	3	0	0	0
исх. сист.	0		10	1	2	1	0	0	14	10
	0		20	-1	2	0	1	0	22
	0		45	3	1	0	0	1	50	15
перв. итерац.	1		10	1	2	1	0	0	14	5
	0		30	0	4	1	1	0	36	30/4
	0		15	0	-5	-3	0	1	8
втор. итерац.	3		5	0,5	1	0,5	0	0	7
	0		10	-2	0	-1	1	0	8
	0		40	2,5	0	-0,5	0	1	43

Так как положительны, то  является максимальным, при ,

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

Методом минимального элемента составим опорный план перевозок.

Таблица 2 – Оптимальный план перевозок

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

Таблица 3 – Метод потенциалов

Для ненагруженных клеток рассчитываем значения их оценок по формуле

Значение целевой функции определим по формуле

Для улучшения предыдущего плана составляем контур перераспределения нагрузки (см. таблицу 3). Исходный узел расположен в свободной клетке с положительным значением оценки. Догружаем клетки с «+» и разгружаем клетки с  «–»  на 45, получаем таблицу 4.

Таблица 4 – Метод потенциалов

Для ненагруженных клеток рассчитываем значения их оценок:

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

Значение целевой функции является минимальным

3. Решить игру с заданными платежными матрицами а)                                               б)

а) Максиминная стратегия I игрока:

Минимаксная стратегия II игрока:

Так как  то точка  является седловой и

 - чистая цена игры.

б) Графическим методом решим в смешанных стратегиях матричную игру со следующей платежной матрицей:

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

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

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

Рисунок 2 – Графическое решение матричной игры

Цена игры = 8.