5.6. Альтернативный оптимум в транспортных задачах

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

,

где .

Пример. На трёх складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырём хлебозаводам в количестве: 30, 80, 60, 110 т соответственно.

Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей

.

РЕШЕНИЕ. Составим распределительную таблицу 5.6.

Таблица 5.6

b j ai		1	2	3	4	ui
		30	80	60	110
1	60	6 20	8	15	4 40	0
2	130	9	15	2 60	3 70	-1
3	90	6 10	12 80	7	10	0
vj		6	12	3	4

По методу минимального тарифа найдём исходное решение. Определим потенциалы строк и столбцов. Найдём оценки свободных клеток:

Так как , то перераспределим грузы относительно клетки (1, 2):

Занесём полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток (табл. 5.7).

Таблица 5.7

b j ai		1	2	3	4	ui
		30	80	60	110
1	60	6	8 20	15	4 40	0
2	130	9	15	2 60	3 70	-1
3	90	6 30	12 60	7	10	4
vj		2	8	3	4

Получим

Так как , то задача имеет альтернативный оптимум и одно из решений равно

.

Стоимость транспортных расходов составляет: усл. ед.

Произведём перераспределение грузов относительно клетки (3, 3):

Занесём в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток (табл. 5.8):

Таблица 5.8

b j ai		1	2	3	4	ui
		30	80	60	110
1	60	6	8 60	15	4	0
2	130	9	15	2 20	3 110	-1
3	90	6 30	12 20	7 40	10	4
vj		2	8	3	4

Получили ещё одно решение:

.

Стоимость транспортных расходов составит усл. ед.

Данная задача имеет два оптимальных решения и , общее решение находится по формуле , где

Найдём элементы матрицы общего решения:

Итак,

.

Стоимость транспортных расходов составляет 1550 усл. ед.