Алгоритм решения транспортной задачи с нарушенным балансом, страница 3

5)  переходят к следующему шагу. В соответствии с требованиями предыдущего шага алгоритма из исходной матрицы стоимостей удалена строка или столбец (или одновременно и строка, и столбец) и выполняется возврат к первому шагу алгоритма. Процесс повторяется до тех пор, пока не будут распределены все ресурсы [3, 4, 5].

1.2.7 Создание оптимального плана перевозок

Полученный опорный план перевозок необходимо проверить на оптимальность. Для получения оптимального плана перевозок разработано несколько методов.

1.2.8. Распределительный метод

Суть распределительного метода состоит в том, что ресурсы, назначенные потребителям по опорному плану, перераспределяются. Алгоритм перераспределения ресурсов следующий.

1. Выбирается свободный (незаполненный) элемент опорного плана.

2. От выбранного свободного элемента строится кратчайший прямоугольный замкнутый контур. Остальные вершины замкнутого контура (кроме первой) проходят через заполненные элементы опорного плана перевозок. Поворот осуществляется только на 90 и только в заполненных элементах.

3.Каждой вершине контура присваивается коэффициент, равный соответствующему значению элемента из матрицы стоимости.

4.Каждому коэффициенту в вершинах контура строго поочерёдно присваивается знак «+» или «-». начиная с пустой клетки.

5. Выполняется алгебраическое суммирование коэффициентов по всему контуру.

6.Пункты с 1 по 5 выполняются для каждого нулевого (пустого) элемента опорного плана.

7.Проверяются результаты суммирования по всем контурам на оптимальность.

8. Если план перевозок не оптимален, то выполняется перераспределение ресурсов и возвращаются к п. 1.

Если при решении транспортной задачи оптимальное решение должно быть минимальным, то алгебраические суммы по всем контурам должны быть положительными или равными нулю.

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

Если план перевозок не оптимален, то перераспределение ресурсов выполняется следующим способом:

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

- в вершинах выбранного контура расставляются фактические перевозки с теми знаками, которые были указаны при вычислении коэффициентов. Рассматриваются вершины только с отрицательными значениями. Выбирается вершина с минимальным по модулю отрицательным значением. Значение этой вершины алгебраически вычитается из всех вершин контура;

- проверяется сохранение баланса перевозок по строкам и столбцам;

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

- проверяется условие оптимальности.

1.2.9. Метод потенциалов

Имея опорный план перевозок, в методе потенциалов выполняют анализ клеток матрицы плана перевозок. Все заполненные клетки матрицы перевозок называются базисными, все незаполненные клетки - свободными.

Для каждой свободной клетки, аналогично распределительному методу, можно построить замкнутый контур  (цикл) и перераспределить ресурсы между поставщиками и потребителями. Отличие этого метода состоит в том, что определяется потенциал каждой клетки и, в зависимости от значения потенциала,  выполняется  перемещение только  по  одному контуру (циклу).

План перевозок будет оптимальным, если он содержит m+n

положительных чисел u и v, которые называются потенциалами строк и столбцов соответственно. Для вычисления потенциалов в матрицу плана перевозок добавляют одну строку сверху и один столбец слева.

Для определения  потенциалов строк и столбцов используют формулу u+v=c, подставляя в нее значения из базисных клеток.