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

Сущность метода состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной 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 не остается.

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

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

Потенциалы – это набор из 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 Переход к не худшему опорному плану. Построение цикла

Переход к не худшему опорному плану осуществляется при помощи построения цикла перераспределения груза. Цикл – это замкнутая ломаная, звенья которой взаимно перпендикулярны, а вершины цикла находятся в занятых клетках, кроме одной – начала цикла.

Начало цикла находится в той свободной клетке, которая имеет наибольшую величину нарушения условия оптимальности II, т.е. наименьшую отрицательную (максимальную по модулю) оценку .

Цикл перераспределения груза обладает свойствами:

- все его вершины, кроме начальной, расположены в занятых клетках;

- звенья (стороны) расположены в строках и столбцах, т.е. две соседние вершины расположены либо в одной строке, либо в одном столбце;

- в каждой вершине встречаются ровно два звена под прямым углом (одно звено находится в строке, другое – в столбце);

- на звеньях могут быть занятые клетки, но они не являются вершинами;

- точки пересечения ломаной линии цикла не являются вершинами.

Два последних свойства обеспечивают некоторую минимальность цикла: он не должен распадаться на объединение двух или более меньших циклов.

На рис.1 изображено несколько циклов с началом в незанятой клетке. Обозначения: О – незанятая клетка (начало цикла), * – занятая клетка; возможные места расположения занятых клеток отмечены черным кружком на звеньях.

Рис.1

На рис.2 изображено несколько замкнутых ломаных, не являющихся циклами: «так нельзя». Штриховыми линиями обозначены возможности сокращения цикла или распада цикла на объединение (сумму) нескольких циклов.

Рис.2

 

Построение циклов и перераспределение поставок груза будем выносить за пределы таблицы и рассматривать отдельно.

После построения цикла клетке начала цикла присваивают знак «+», начиная с неё, остальным вершинам цикла знаки присваиваются поочередно: «–», «+» и т.д. Из всех клеток цикла (объемов груза, величин поставок) со знаком «–» выбирают ту, в которой находится минимальный груз (обозначим Θ). Это количество груза Θ перераспределяется (сдвигается) по циклу, т.е. в клетках со знаком «+» величина Θ прибавляется, а в клетках со знаком «–» – вычитается. Клетка в начале цикла, которая ранее была свободной, становится занятой (базисной), а одна из занятых «–» клеток (с меньшим значением Θ) становится пустой (свободной).

Если наименьшее значение Θ появляется сразу в нескольких «–» клетках, то для перераспределения величины Θ выбирается любая из них. При перераспределении поставок эти клетки с одинаковыми значениями Θ будут освобождаться, и план станет вырожденным (число заполненных клеток будет меньше m+n-1). Поэтому для продолжения решения необходимо в эти одновременно освобождающиеся клетки (кроме той, которая станет свободной) поставить значение «0», причем предпочтение отдается клеткам с наименьшим тарифом. Нулей вводим столько, чтобы во вновь полученном плане число заполненных клеток стало равно m+n-1.

Клетки, которые не задействованы в цикле, остаются неизменными.

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

Улучшение планов проводят до тех пор, пока на очередном шаге все оценки в незаполненных клетках будут неотрицательными ( ). В этом случае опорный план является оптимальным, для него находится значение Z_min, задача решена.

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

Рассмотрим пример проверки оптимальности плана методом потенциалов и построения цикла.

Пример 4. Условия и таблица взяты из последнего примера 3:

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

План вырожденный (базисных клеток 5<rang=m+n-1=4+3-1=6). Метод потенциалов применим только для невырожденного плана, т.е. для определения потенциалов нужна еще одна занятая клетка. Такой клеткой будет (2, 3), ее заполняем нулем (так как находится во 2-й строке, вычеркнутой одновременно с 4-м столбцом на 4-м шаге, не является вершиной цикла и на момент зачеркивания на 4-м шаге линий i=2 и j=4 для столбца j=3 сохранилась потребность в 80 ед.).

В уме определяем потенциалы из системы для всех базисных клеток и заносим их в эту же таблицу:

α₁=0, α₁ + β₄ =1 => β₄ = 1,

α₂ + β₄ =3 => α₂ = 2,

α₂ + β₂ =1 => β₂ = -1,

α₁ + β₁ =1 => β₁ = 1,

α₂ + β₃ =4 => β₃ = 2,

α₃ + β₃ =5 => α₃ = 3.

Вычислим оценки для всех свободных клеток, используя 2-е условие оптимальности . Результаты запишем в центре клетки.

Δ₁₂=5-0+1=6, Δ₁₃=6-0-2=4, Δ₂₁=4-2-1=1,

Δ₃₁=3-3-1=-1, Δ₃₂=3-3+1=1, Δ₃₄=6-3-1=2.

Подчеркнем, что для занятых клеток .

Матрица оценок будет иметь вид: . Имеем одну отрицательную оценку Δ₃₁ = -1. План неоптимальный, необходимо его улучшать.

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

Z(X₁)=70·1+20·1+60·1+50·3+80·5=700.

Для перераспределения груза строим цикл с началом в клетке (3, 1) с отрицательной оценкой Δ₃₁ = -1. Для его пересчета выносим цикл отдельно.

Минимальную поставку (объем перепоставки) груза определяем по вершинам с «–» знаками: Θ=min(70, 50, 80)=50. Эту величину вычтем из вершин c «–» знаками и прибавим к вершинам с «+» знаками. Старые поставки запишем вне цикла, а новые – внутри него. Клетка (3, 1) была свободной, после перераспределения свободной стала клетка (2, 4).

Строим новую таблицу, в которую заносим новый план, состоящий из старых поставок, не вовлеченных в цикл, и новых – в вершинах рассмотренного цикла. Получили невырожденный план, в нем 6 отличных от нуля компонент, тогда как в первом вырожденном плане было 5 отличных от нуля компонент.

Методом потенциалов определяем оценки клеток. Отрицательных оценок нет ( ): план оптимален. Его стоимость равна

Z(X₂)=20·1+70·1+60·1+50·4+50·3+30·5=650.

Ответ: Оптимальный план перевозок

Стоимость плана Z(X₂) = 650.