Б) Метод наименьшей стоимости (наименьших затрат (тарифов), минимального элемента)

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

Таблица начинает заполняться с той клетки, в которой наименьший тариф c_ij. Пусть это будет клетка (i, j). В эту клетку записывается максимально возможная поставка с учетом ограничений i- й строки и j- го столбца, т.е. значение . Если a_i > b_j, тогда этой поставкой обеспечивается потребность потребителя B_j, и этот потребитель (столбец) исключается из дальнейшего рассмотрения, а запасы поставщика A_i становятся равными величине (a_i – b_j). Если же a_i < b_j, то от поставщика забирается весь груз, и тогда этот поставщик (строка) исключается из дальнейшего рассмотрения, а потребность потребителя B_j становится равной величине (b_j – a_i). Исключаемый столбец (или строка) нумеруется, и этот номер записывается на краю этого столбца (или строки). Строка и столбец, исключаемые одновременно, отмечаются одним номером.

Процесс повторяется до тех пор, пока не будут зачеркнуты все столбцы и строки.

Если ТЗ открытая, и введены фиктивный поставщик или потребитель, то сначала заполняются клетки для действительных поставщиков и потребителей, и в последнюю очередь – для фиктивных.

На последнем шаге строка и столбец заполняются одновременно, следовательно, в благоприятном случае должно быть (m + n -1) заполненных клеток. Такой план является невырожденным.

Вырожденный план появляется при одновременном зачеркивании строки и столбца (кроме последнего шага), когда число заполненных клеток будет меньше, чем r = m + n -1. Для дальнейших расчетов его надо дополнить до невырожденного плана нулями, записав их в клетки, расположенные в строке или в столбце, которые одновременно исключены из рассмотрения, т.е. имеют один номер шага. При этом клетки, заполненные нулями, не должны составлять цикл (контур) с прочими заполненными клетками и, кроме того, на момент одновременного зачеркивания строки и столбца принадлежат столбцам, для которых сохраняется потребность в грузе.

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

Пример 2. Построить начальный опорный план методом наименьшей стоимости и найти транспортные расходы для ТЗ. Исходные данные такие же, как в примере 1.

Решение. Задача закрытая, так как .

Строим распределительную таблицу и начинаем ее заполнять с клетки (1; 1), т. к. в ней наименьший тариф (с ₁₁ = 1): х ₁₁ = min(90; 70) = 70. Из дальнейшего рассмотрения исключаем 1-й столбец, отметив его номером 1).

		1)	3)	6)	5)
2)
4)
6)

Затем заполняем клетку (1; 4) с наименьшим тарифом с ₁₄ = 1:

х ₁₄ = min(а ₁ – х ₁₁; b ₄) = min(90-70; 70) = min(20; 70) = 20. Из дальнейшего рассмотрения исключаем 1-ю строку, отметив ее номером 2).

Далее (с ₂₂ = 1): х ₂₂ = min(100; 60) = 60;

(с ₂₄ = 3): х ₂₄ = min(а ₂ – х ₂₂; b ₄ – х ₁₄) = min(100-60; 70-20) = min(40; 50) = 40;

(с ₃₄ = 4): х ₃₄ = min(а ₃; b ₄ – х ₁₄ – х ₂₄) = min(90; 70-20-40) = min(90; 10) = 10;

(с ₃₃ = 5): х ₃₃ = min(а ₃ – х ₃₄; b ₃) = min(90-10; 80) = min(80; 80) = 80.

Стоимость перевозок: .

Ранг матрицы системы и число заполненных клеток 6 (= r). Следовательно, полученный план – невырожденный.

Сравнивая значения Z в примерах 1 и 2, видим, что затраты при 2-м методе (с учетом стоимости перевозок) значительно меньше.

Рассмотрим пример невырожденного плана:

Пример 3. Построить начальный опорный план методом наименьшей стоимости. Решение: Задача закрытая, так как .

Ранг матрицы , а число заполненных клеток (компонентов) – 5 (< r). Следовательно, опорный план – вырожденный.

При заполнении таблицы на 4-м шаге одновременно зачеркнуты 2-я строка и 4-й столбец. Отмеченная уголком и звездочкой клетка (2, 3) заполняется нулем. В клетку (2, 1) нуль не пишем, так как она составляет цикл с заполненными клетками (70), (50) и (20). В клетку (3, 4) нуль не пишем, так как на момент зачеркивания на 4-м шаге линий i =2 и j =4 потребность в 70 ед. для столбца j =4 не остается.

После построения начального опорного плана он проверяется на оптимальность методом потенциалов.

Проверка опорного плана на оптимальность методом потенциалов

Потенциалы – это набор из m + n чисел α _i и β _j, которые удовлетворяют условиям:

- при решении задачи на минимум (Z → min):

I. – для всех заполненных клеток;

II. или – для всех пустых клеток. Разности называются оценками.

- при решении задачи на максимум (Z → max):

I. - для занятых клеток;

II. или – для свободных клеток.

Так как число переменных (потенциалов) m + n этой системы больше числа уравнений m + n -1, то система данных уравнений не определена и имеет ∞ множество решений.

Поэтому для однозначного определения потенциалов один из них берут произвольно, например, α ₁=0. Остальные потенциалы находятся последовательно с использованием условия I. Для занятых клеток значения оценок будут нулевыми ( =0).

Потенциалы записываются в дополнительных столбце и строке таблицы.

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

Условие оптимальности плана для задачи на max: оценки всех свободных клеток .

Замечание. Потенциалы могут быть рассчитаны только для невырожденного плана. Если план вырожденный (число заполненных клеток меньше, чем m + n -1), то вносятся нули в свободные клетки так, чтобы общее число занятых клеток стало равным m + n -1. Нуль вводят в клетку, расположенную в столбце или строке, вычеркиваемых одновременно при составлении начального плана.

5.4 Переход к не худшему опорному плану. Построение цикла