Шаг 3. Нахождение нового базисного решения. Если получены несколько отрицательных характеристик, то перераспределение делают для той клетки, у которой оценка (по абсолютной величине) наибольшая

Если получены несколько отрицательных характеристик, то перераспределение делают для той клетки, у которой оценка (по абсолютной величине) наибольшая. В данном случае, поскольку имеются две одинаковые отрицательные оценки в клетках А₂Б₂ и А₂Б₃, выбор клетки произвольный.

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

Для перераспределения поставки выберем одну из двух клеток с наименьшей отрицательной характеристикой, например клетку А₂Б₁. Цепь, построенная для данной клетки, представлена в табл. 11.

Таблица 11

Нахождение нового плана (формирование цепи для клетки с отрицательной характеристикой)

Для определения поставки в незанятую вершину поступают следующим образом. В вершинах цепи отыскивают наименьшую (по абсолютной величине) отрицательную поставку, на которую уменьшают все поставки с отрицательным знаком и увеличивают поставки с положительным знаком. В рассматриваемой цепи наименьшая по абсолютной величине отрицательная поставка содержится в клетке А₃Б₁, следовательно, незанятая клетка получит 30 т.

Новый план перевозок товара между складами после перераспределения поставок представлен в табл. 12.

Таблица 12

Нахождение нового плана (перераспределение поставок)

Значение целевой функции полученного распределения, т.е. транспортная работа составляет

Таким образом, первоначальное базисное распределение удалось улучшить на 1630 – 1510 = 120 ткм.

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

Шаг 2. Анализ распределения и проверка плана перевозок на оптимальность.

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

Таблица 13

Проверка нового плана перевозок товара между складами

на оптимальность (расчет потенциалов)

Таблица 14

Проверка нового плана перевозок товара между складами

на оптимальность (расчет характеристик незанятых клеток)

В рассматриваемом распределении имеется одна незанятая клетка с отрицательной характеристикой – А₁Б₄, следовательно, план является неоптимальным и требуется нахождение нового базисного решения.