Построение оптимального плaна

Когда исходный план получен и рассчитана соответствующая ему суммарная тонно-километровая работа, определяют, является ли этот план оптимальным. Для проверки плана на оптимальность применяется метод потенциалов.

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

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

Таблица 2.5

Поставщики	Потребители	Объемы вывоза, тонн
М₁	М₂	М₃	М₄
П₁
П₂
П₃
Объемы завоза, т

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

Таблица 2.6

Поставщики и объемы вывоза, т

Потребители и объемы завоза

М₁

М₂

М₃

М₄

Потенциалы строк

П₁

П₂

П₃

Потенциалы столбцов

Потенциалы строк и столбцов определяются по заполненным клеткам, находящимся на их пересечении.

Элемент заполненной клетки должен равняться сумме потенциалов строки и столбца, на пересечении которых находится эта заполненная клетка.

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

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

Из основного требования = u_i + Vj вытекает:

u_i = - Vj; Vj = - u_i

Из этих выражений видно, что для расчета потенциала строки необходимо иметь заполненную клетку, в столбце которой потенциал уже определен, а для расчета потенциала столбца нужна заполненная клетка, имеющая потенциал в строке.

В таблице для строки П₁ условно принимаем потенциал, равный 0. Эта строка имеет две заполненные клетки, по которым можно определить потенциалы двух столбцов М₁ и М₂:

для М₁V₁ = 18 – 0 = 18;

для М₂ V₂ = 15 – 0 = 15.

Имея потенциал столбца М₂, можно рассчитать потенциал строки П₂ по заполненной клетке П₂М₂. Потенциал для П₂ будет равен:

u₂ = 21 – 15 = 6.

По клеткам П₂М₃ и П₂М₄ определяются потенциалы столбцов М₃, М₄. Они будут равны соответственно:

V₃ = - u₂ = 12 – 6 = 6;

V₄ = - u₂ = 15 – 6 = 9.

Для строки П₃ - потенциал определяется по метке П₃М_4.

Он равен:

u₃ = - V₄ = 27 – 9 = 18

Потенциалы показаны в таблице 2.6.

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

Сравнение суммы потенциалов с величиной элемента в свободных клетках позволяет определить, нужно ли заполнять эту клетку или ее нужно оставить свободной.

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

Иными словами, если характеристика, значение которой равно разности - (u_i + Vj), положительная, то свободная метка не заполняется при решении задачи на минимум функции. И наоборот, если она отрицательная, то клетка не заполняется при решении задачи на максимум функции.

Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неизменным.

Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице 2.7.

Таблица 2.7

Шифры клеток	П₁–М₃	П₁–М₄	П₂–М₁	П₃–М₁	П₃–М₂	П₃–М₃
Суммы потенциалов
Значение элементов
Характеристики	+1	+12		-6	-15

В первоначальном плане две клетки имеют положительные характеристики, в двух клетках характеристики равны нулю (суммы потенциалов равны значениям элементов) и в двух клетках характеристики отрицательные.

Так как задача решается на минимум целевой функции, то именно эти две последние клетки должны быть заполнены поставщиками. Но заполнение свободной клетки и связанное с ним перераспределение поставок производится не изолированно, а в связи с несколькими заполненными клетками. Эта связь выявляется путем построения замкнутых многоугольников, вершинами которых являются клетки таблицы. Одна вершина многоугольника находится в свободной клетке, а все остальные - в заполненных клетках. Многоугольник, или как его называют цепь, имеет прямые углы и четное число вершин.

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

Те клетки цепи, у которых поставки увеличиваются, называются положительными, а те, у которых поставки уменьшаются - отрицательными. Каждая цепь имеет одинаковое число положительных и отрицательных вершин (клеток). Положительные и отрицательные вершины чередуются. Для свободных клеток, имеющих отрицательные характеристики, цепи показаны ниже.

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

Таблица 2.8

Поставщики и объемы вывоза, т

Потребители и объемы завоза

М₁

М₂

М₃

М₄

Потенциалы строк

П₁

П₂

П₃

Потенциалы столбцов

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

В примере запись поставки, равной 9, произведена в клетке П₃-М₂ и перераспределение, вызванное этой записью, показано в таблице (табл. 2.8).

Объем работ составит:

27 * 18 + 9 * 15 + 9 * 21 + 27 * 12 + 27 * 15 + 9 * 18 = 1701 ткм.

Характеристики свободных клеток последнего плана равны:

Шифры клеток	П₁–М₃	П₁–М₄	П₂–М₁	П₃–М₁	П₃–М₃	П₃–М₄
Характеристики	+12	+12		+9	+15	+15

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

Для решения задач методом потенциалов исходный план должен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчитать потенциалы, а без них нельзя проверить план на оптимальность.

Случаи, когда в плане число заполненных клеток меньше m + n – 1, называются вырождением. Вырождение в задаче устраняется путем заполнения недостающих до m + n – 1 клеток нулевыми поставками. Выбор клеток для записей нулевых поставок производится с таким расчетом, чтобы все m + n – 1 заполненные клетки могли быть вычеркнуты, если последовательно производить вычеркивание заполненных клеток единственных в своем столбце или в своей строке.

Если в транспортных задачах не сбалансируются итоги (объемы вывоза превышают объемы завоза или объемы вывоза ниже объемов завоза), то для баланса вводятся дополнительные поставщики или потребители.

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

Вопросы для сaмопроверки к главе2

1. Кaково знaчение перевозок в развитии производственной деятельности?

2. Кaкой из мaтемaтических методов используется при оптимизaции плaнов перевозок?

3. Нaзовите перечень необходимой информaции для рaзрaботки оптимaльного плaнa перевозок.

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

5. Сформулируйте постановку мaтемaтической модели трaнспортной зaдaчи и ее рaзновидности.