Сущность метода состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной cij. Если такая клетка не единственная, то лучше заполнять ту, по вертикали и горизонтали которой встречаются бόльшие значения cij, а в принципе заполняется любая из них.
Таблица начинает заполняться с той клетки, в которой наименьший тариф cij. Пусть это будет клетка (i, j). В эту клетку записывается максимально возможная поставка с учетом ограничений i- й строки и j- го столбца, т.е. значение . Если ai > bj, тогда этой поставкой обеспечивается потребность потребителя Bj, и этот потребитель (столбец) исключается из дальнейшего рассмотрения, а запасы поставщика Ai становятся равными величине (ai – bj). Если же ai < bj, то от поставщика забирается весь груз, и тогда этот поставщик (строка) исключается из дальнейшего рассмотрения, а потребность потребителя Bj становится равной величине (bj – ai). Исключаемый столбец (или строка) нумеруется, и этот номер записывается на краю этого столбца (или строки). Строка и столбец, исключаемые одновременно, отмечаются одним номером.
|
|
Процесс повторяется до тех пор, пока не будут зачеркнуты все столбцы и строки.
Если ТЗ открытая, и введены фиктивный поставщик или потребитель, то сначала заполняются клетки для действительных поставщиков и потребителей, и в последнюю очередь – для фиктивных.
На последнем шаге строка и столбец заполняются одновременно, следовательно, в благоприятном случае должно быть (m + n -1) заполненных клеток. Такой план является невырожденным.
Вырожденный план появляется при одновременном зачеркивании строки и столбца (кроме последнего шага), когда число заполненных клеток будет меньше, чем r = m + n -1. Для дальнейших расчетов его надо дополнить до невырожденного плана нулями, записав их в клетки, расположенные в строке или в столбце, которые одновременно исключены из рассмотрения, т.е. имеют один номер шага. При этом клетки, заполненные нулями, не должны составлять цикл (контур) с прочими заполненными клетками и, кроме того, на момент одновременного зачеркивания строки и столбца принадлежат столбцам, для которых сохраняется потребность в грузе.
Необходимо отметить, что при наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными.
Пример 2. Построить начальный опорный план методом наименьшей стоимости и найти транспортные расходы для ТЗ. Исходные данные такие же, как в примере 1.
Решение. Задача закрытая, так как .
Строим распределительную таблицу и начинаем ее заполнять с клетки (1; 1), т. к. в ней наименьший тариф (с 11 = 1): х 11 = min(90; 70) = 70. Из дальнейшего рассмотрения исключаем 1-й столбец, отметив его номером 1).
|
|
1) | 3) | 6) | 5) | ||||||
2) | |||||||||
4) | |||||||||
6) | |||||||||
Затем заполняем клетку (1; 4) с наименьшим тарифом с 14 = 1:
х 14 = min(а 1 – х 11; b 4) = min(90-70; 70) = min(20; 70) = 20. Из дальнейшего рассмотрения исключаем 1-ю строку, отметив ее номером 2).
Далее (с 22 = 1): х 22 = min(100; 60) = 60;
(с 24 = 3): х 24 = min(а 2 – х 22; b 4 – х 14) = min(100-60; 70-20) = min(40; 50) = 40;
(с 34 = 4): х 34 = min(а 3; b 4 – х 14 – х 24) = min(90; 70-20-40) = min(90; 10) = 10;
(с 33 = 5): х 33 = min(а 3 – х 34; b 3) = 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, то система данных уравнений не определена и имеет ∞ множество решений.
Поэтому для однозначного определения потенциалов один из них берут произвольно, например, α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, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяется на оптимальность методом потенциалов.
Улучшение планов проводят до тех пор, пока на очередном шаге все оценки в незаполненных клетках будут неотрицательными (). В этом случае опорный план является оптимальным, для него находится значение Zmin, задача решена.
При заполнении клеток тарифами, поставками, оценками для контраста используют разные цвета, выделяют рамками, цикл в таблице или выносят отдельно, или выделяют отдельным цветом или штриховой линией.
Рассмотрим пример проверки оптимальности плана методом потенциалов и построения цикла.
Пример 4. Условия и таблица взяты из последнего примера 3:
Решение. Задача закрытая, .
План вырожденный (базисных клеток 5<rang= m + n -1=4+3-1=6). Метод потенциалов применим только для невырожденного плана, т.е. для определения потенциалов нужна еще одна занятая клетка. Такой клеткой будет (2, 3), ее заполняем нулем (так как находится во 2-й строке, вычеркнутой одновременно с 4-м столбцом на 4-м шаге, не является вершиной цикла и на момент зачеркивания на 4-м шаге линий i =2 и j =4 для столбца j =3 сохранилась потребность в 80 ед.).
В уме определяем потенциалы из системы для всех базисных клеток и заносим их в эту же таблицу:
α1=0, α1 + β4 =1 => β4 = 1,
α2 + β4 =3 => α2 = 2,
α2 + β2 =1 => β2 = -1,
α1 + β1 =1 => β1 = 1,
α2 + β3 =4 => β3 = 2,
α3 + β3 =5 => α3 = 3.
Вычислим оценки для всех свободных клеток, используя 2-е условие оптимальности . Результаты запишем в центре клетки.
Δ12=5-0+1=6, Δ13=6-0-2=4, Δ21=4-2-1=1,
Δ31=3-3-1=-1, Δ32=3-3+1=1, Δ34=6-3-1=2.
Подчеркнем, что для занятых клеток .
Матрица оценок будет иметь вид: . Имеем одну отрицательную оценку Δ31 = -1. План неоптимальный, необходимо его улучшать.
Стоимость этого плана (стоимость перевозок):
Z (X 1)=70·1+20·1+60·1+50·3+80·5=700.
Для перераспределения груза строим цикл с началом в клетке (3, 1) с отрицательной оценкой Δ31 = -1. Для его пересчета выносим цикл отдельно.
Минимальную поставку (объем перепоставки) груза определяем по вершинам с «–» знаками: Θ=min(70, 50, 80)=50. Эту величину вычтем из вершин c «–» знаками и прибавим к вершинам с «+» знаками. Старые поставки запишем вне цикла, а новые – внутри него. Клетка (3, 1) была свободной, после перераспределения свободной стала клетка (2, 4).
Строим новую таблицу, в которую заносим новый план, состоящий из старых поставок, не вовлеченных в цикл, и новых – в вершинах рассмотренного цикла. Получили невырожденный план, в нем 6 отличных от нуля компонент, тогда как в первом вырожденном плане было 5 отличных от нуля компонент.
Методом потенциалов определяем оценки клеток. Отрицательных оценок нет (): план оптимален. Его стоимость равна
Z (X 2)=20·1+70·1+60·1+50·4+50·3+30·5=650.
Ответ: Оптимальный план перевозок
Стоимость плана Z (X 2) = 650.