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

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

 

Таблица 2.6

Поставщики	Потребители	Объемы вывоза, тонн
М1	М2	М3	М4
П1
П2
П3
Объемы завоза, т

 

 

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

 

Таблица 2.7

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

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

М1

М2

М3

М4

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

П1

П2

П3

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

 

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

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

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

Обозначив потенциалы строк 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.7.

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

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

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

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

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

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

Таблица 2.8

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

 

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

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

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

 

 

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

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

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

 

Таблица 2.9

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

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

М1

М2

М3

М4

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

П1

П2

П3

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

 

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

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

 

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

 

Шифры клеток	П1–М3	П1–М4	П2–М1	П3–М1	П3–М3	П3–М4
Характеристики	+12	+12		+9	+15	+15

 

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

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

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

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

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