Метод наименьших затрат.

Задача: Найти методом наименьших затрат первоначальное распределение поставок в задаче п.1.2..

Р е ш е н и е: Найдем в таблице поставок клетку с наименьшим коэффициентом затрат. Это клетки (1; 1) и (2; 1) (коэффициент затрат равен 1). Максимально возможные поставки для этих клеток х₁₁ = min (20; 60) = 20, х₂₁ = min (120; 60) = 20. Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, в клетку (2; 1) и спрос первого потребителя удовлетворен полностью.

Мощность поставщиков	Потребители и их спрос


	х₁₁		х₁₃	х₁₄
		х₂₂	х₂₃
	х₃₁

В оставшейся таблице наименьшим коэффициентом затрат обладают клетки (1; 2) и (2; 4) (коэффициент равен 2). Максимально возможные поставки для этих клеток соответственно равны х₁₂ = min (110; 60) = 60, х₂₄ = min (120-20; 110) = 100. Даем поставку в клетку (2; 4). В клетку (1; 2) пойдет поставка х₁₂= min (110; 60) = 60. Дальнейшее заполнение таблицы аналогично. Суммарные затраты F = 120+20+200+150+280+40 = 810. Как видим, затраты уменьшились и значение F ближе к оптимальному.

Критерий оптимальности базисного распределения поставок.

Теорема (критерий оптимальности). Базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.

Как найти оценки свободных клеток?

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

Решение: найдем оценку свободной клетки (1;3). В эту клетку дадим единичную поставку. При этом заполнение других клеток произойдет следующим образом:

Мощность поставщиков	Потребители и их спрос


	х₁₁			х₁₄
		х₂₂	х₂₃
	х₃₁

Изменение суммарных затрат при этом DF = F_н – F_п = - 1 – это же будет и оценкой клетки (1; 3). b₁₃ = -1. Таким образом, полученное распределение поставок не является оптимальным.

Искать вышеописанным способом оценки всех клеток долго.

Теорема (о потенциалах ). Оценка свободной клетки не изменится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число, прибавленное к коэффициентам затрат, называют потенциалом данной строки (столбца).

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

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

Р е ш е н и е: Найдем оценки свободных клеток по правилу. Изменение коэффициентов затрат можно начинать с любого столбца (строки). Потенциал столбца (строки), избранного для начала, может быть произвольным. Начнем с первого столбца. Пусть потенциал этого столбца равен нулю. Чтобы коэффициент затрат в клетке (2; 1) стал = 0, ко второй строке прибавим -1 (шаг 2) (т.е. потенциал 2-ой строки равен -1). Чтобы коэффициент затрат в клетке (2; 4) стал = 0, к 4-му столбцу добавим потенциал -1(шаг 3). И.т.д.

1				-2 (7)
				-1 (2)
				-3 (4)
0 (1)	0 (6)	-4 (5)	-1 (3)

Измененные коэффициенты затрат запишем в виде матрицы оценок:

Элементы матрицы оценок, соответствующие свободным клеткам таблицы поставок, равны оценкам этих свободных клеток. ■

Распределительный метод решения транспортной задачи

Задача: найти оптимальное распределение поставок транспортной задачи.

Р е ш е н и е: Рассмотрим распределение поставок, полученное методом наименьших затрат. Как установлено выше это распределение не оптимально. Оценка свободной клетки – это коэффициент при соответствующей переменной. Так, учитывая, что в пункте 6.2 F = 810, то имеем F = 810 – х₁₃ – х₁₁ +5 х₂₂ + 3х₃₁. Начнем с рассмотрения переменной х₁₃, коэффициент при которой отрицателен. Будем увеличивать поставку х₁₃ в клетке (1; 3) до тех пор, пока поставка в одной из заполненных клеток не станет равной нулю (эту клетку мы должны найти). Цикл пересчета представлен ниже.

(1; 2) (1;3)

₂ - ₅ ₊

⁶⁰

(3; 2) (3;3)

3 + ₇^-

^{50 40}

Если в клетку (1;3) передать некоторую поставку р, то в клетках (3;3) и (1;2) поставки уменьшаться на р (это клетки со знаком «- ». Очевидно, искомая клетка – одна из этих двух, причем она имеет минимальную поставку среди таких клеток. Итак, min (60; 40) = 40. Это клетка (3;3). И для обнуления поставки в этой клетке по циклу следует передать поставку 40.

Итак, поставка, передаваемая по циклу, определяется как min среди поставок в клетках цикла со знаком «- ».

Теперь клетка (1;3) будет заполненной, а клетка (3;3) – свободной. Получим

20
			-2
			-1
			-3
	-3	-1

Опять найдем матрицу оценок свободных клеток:

Как видим, клетка (1;1) с отрицательной оценкой и полученное распределение не является оптимальным. И передача поставки в клетку (1;1) ведет к уменьшению суммарных затрат. Проделаем аналогичные операции, как для клетки (1;3). Цикл пересчета:

_{(1;1) (1;2)}

_{+ --}