Задача 40. Решение.Составляем начальную транспортную таблицу с нулевыми перевозками. Поставщик Потребитель Запасы груза

Решение. Составляем начальную транспортную таблицу с нулевыми перевозками.

Поставщик

Потребитель

Запасы груза

Потребность

Транспортная задача имеет закрытый тип, так как суммарный запас груза

70+100+160=330

равен суммарным потребностям

80+140+110=330.

Найдем опорный план по методу минимального тарифа.

Находим незанятую клетку с минимальным тарифом: (3,2). Помещаем туда меньшее из чисел 160 и 140.
Находим незанятую клетку с минимальным тарифом: (3,3). Помещаем туда меньшее из чисел 20 и 110.
Находим незанятую клетку с минимальным тарифом: (1,1). Помещаем туда меньшее из чисел 70 и 80.
Находим незанятую клетку с минимальным тарифом: (2,1). Помещаем туда меньшее из чисел 100 и 10.
Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел 90 и 90.

Получили:

Поставщик

Потребитель

Запасы груза

Потребность

Стоимость перевозок по этому плану равна:

F = 70*3+10*4+90*5+140*1+20*2 = 880.

Будем решать задачу методом потенциалов. Проверяем найденный план на оптимальность. Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j, просматривая все занятые клетки.
Потенциалы:
U₁=0
V₁=C_1,1-U₁= 3
U₂=C_2,1-V₁=1
V₃=C_2,3-U₂= 4
U₃=C_3,3-V₃=-2
V₂=C_3,2-U₃= 3

Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,2 = C_1,2 - (U₁ + V₂) = 5.
S_1,3 = C_1,3 - (U₁ + V₃) = 2.
S_2,2 = C_2,2 - (U₂ + V₂) = -1.
S_3,1 = C_3,1 - (U₃ + V₁) = 9.

Выбираем клетку (2,2) с отрицательной оценкой -1. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы груза

+

-

-
140

+

Потребность

Перемещаем по циклу груз величиной в 90 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы груза

Потребность

Стоимость перевозок F = 70*3+10*4+90*3+50*1+110*2=790.

Проверяем найденный план на оптимальность. Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j, просматривая все занятые клетки.
Потенциалы:
U₁=0
V₁=C_1,1-U₁= 3
U₂=C_2,1-V₁=1
V₂=C_2,2-U₂= 2
U₃=C_3,2-V₂=-1
V₃=C_3,3-U₃= 3

Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,2 = C_1,2 - (U₁ + V₂) = 6.
S_1,3 = C_1,3 - (U₁ + V₃) = 3.
S_2,3 = C_2,3 - (U₂ + V₃) = 1.
S_3,1 = C_3,1 - (U₃ + V₁) = 8.

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

План перевозок:

Задача 70. Найти решение и цену игры, заданной следующей платежной матрицей:

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

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

Аналогично для второго игрока. Найдем максимальные значения выигрыша по столбцам: , и минимальное из этих чисел - верхняя цена игры, стратегия В2.

Так как верхняя и нижняя цены игры различны, игра не имеет решения в чистых стратегиях (седловой точки нет), цена игры находится в промежутке от 5 до 9 (между нижней и верхней ценой игры).

Решим данную игру аналитическим методом.

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

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

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

Решаем эту систему и находим:

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