|
следующие этапы.
а. Построение первого опорного плана.
б. Проверка вырожденности плана. Потенциалы аi и bj могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (т + п- 1), то не хватит количества уравнений для определения потенциалов, поэтому вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m + n - 1). Нуль вводят в клетку с наименьшим тарифом, например в клетку одновременно вычеркиваемых строки и столбца таблицы при составлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы.
в. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клетками таблицы.
г. Проверка условия оптимальности. Так как число переменных больше числа уравнений (m + п > т + п - 1), то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов аi, bj задают произвольное значение, например, для простоты вычислений полагаем а1 = 0. Тогда остальные потенциалы определяются из приведенных соотношений.
В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы.
Определяем оценки свободных клеток ij.
Если все ij 0 (задача решается на минимум целевой функции) либо все ij 0 (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки ij > 0 (задача поставлена на минимум) или ij < 0 (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспределение груза.
д. Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных - наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т. е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых и связанных с заполняемой так называемым циклом.
Циклом, или прямоугольным контуром, в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл.
Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «-».
Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его . Перераспределяем величину по циклу, прибавляя у к соответствующим объемам груза, стоящим в плюсовых клетках и вычитая из объемов груза, находящихся в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной.
Полученный новый опорный план проверяется на оптимальность, т. е. возвращаемся к четвертому этапу алгоритма.
Примечания:
1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения xij, то при перераспределении объемов груза освобождаются две (или несколько) клеток, и план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наилучшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (т + п - 1).
2. Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю (ij = 0), то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.
3. Значение целевой функции на каждой итерации можно рассчитать следующим образом.
|
