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

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

Алгоритм определения кратчайших расстояний методом потенциалов:

Шаг 1. Начальной точке сети, за которую может быть принята любая из вершин, присваивают потенциал, равный нулю (v_i = 0);

Шаг 2. Определяют потенциалы соседних с начальной точкой вершин сети по формуле:

v_j = v_i + l_ij

где v_i - потенциал предшествующей (соседней) вершины;

l_ij - длина эвена, соединяющего вершины i и j.

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

Шаг 3. Определяют потенциалы вершин, соседних с выбранной вершиной, и из всей совокупности потенциалов выбирают наименьший, который проставляют у соответствующей вершины и т.д.

Полное решение задачи включает столько этапов, сколько вершин включает транспортная сеть, поскольку каждый раз определяют кратчайшие расстояния от начальной точки до остальных.

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

На 1 этапе за начальную точку принята вершина А. Её потенциал равен нулю, т. е. v_A=0 (min 1). Соседними к точке А являются вершины: Б, Г, Е, В. Их потенциалы:

v_Б= v_A+l_АБ=0+5=5; min 2

v_В= v_A+l_АВ=0+6=6; min 3

v_Г= v_A+l_АГ=0+7=7; min 4

v_Е= v_A+l_АЕ=0+8=9; min 6

Из всех вычисленных потенциалов наименьшим является потенциал точки Б, равный 5. Этот потенциал проставляют у вершины Б на рисунке в прямоугольной рамке и отмечают в расчетах, чтобы к нему не возвращаться. На рисунке кратчайшую связь отмечают стрелкой от точки Ак точке Б.

Затем определяют потенциалы точек Ви Д, соседних к точке Б:

v_В= v_Б+l_БВ=5+3=8;

v_Д= v_Б+l_БД=5+4=9. min 5

Из совокупности потенциалов (кроме v_А и v_Б, которые уже выбраны) наименьший потенциал соответствует точке В и равен 6. Это число проставляют у вершины В, отмечают кратчайшую связь от точки Ак точке В. Этой же вершине соответствуют еще потенциал равный 8, но поскольку это значение выше выбранного, то его вычеркивают.

Потенциалы точек Г и Д, рассчитанные через потенциал точки В, равны

v_Г= v_В+l_ВГ=6+6=12;

v_Д= v_В+l_ВД=6+5=11;

Из невыбранных потенциалов наименьший 7 соответствует точке Г. Его присваивают этой точке и делают соответствующие отметки.

Используя потенциал точки Г, определяют значения потенциалов для соседних с ней точек Е, Ж

v_Е= v_Г+l_ГЕ=7+4=11;

v_Ж= v_Г+l_ГЖ=7+7=14; min 7

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

v_Е= v_Д+l_ДЕ=9+4=13;

v_З= v_Д+l_ДЗ=9+5=14; min 9

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

Определяют потенциал точки Ж через потенциал точки Е

v_Ж= v_Е+l_ЖЕ=9+4=13; min 8

Из всех х потенциалов наименьшим является потенциал точки Ж, равный 13.

Потенциал вершины З, вычисленный через потенциал точки Ж равен 17.

Чтобы продолжить решение задачи, рассматривают оставшуюся совокупность потенциалов. Наименьшим в совокупности является потенциал 14 для точки З.

Потенциалы всех вершин определены, это значит, что найдены кратчайшие расстояния от точки А к остальным вершинам транспортной сети. На рис. 1.1 они отмечены стрелками. Кратчайшая транспортная сеть для точки Аотдельно изображена на рис. 1.2.

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

Метод «метлы»

Общие положения решения задачи определения кратчайших расстояний методом «метлы» сводятся к следующему:

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

2. Определяют длину звеньев, соединяющих начальную вершину с соседними, и расстояния М заменяют в таблице на меньшие, фактические (поскольку требуется найти кратчайшие расстояния между пунктами сети).

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

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

5. Процесс решения (цикл) повторяют до тех пор, пока из таблицы не будут вычеркнуты все знаки проверки для вершин сети.

6. Для определения кратчайших расстояний между всеми вершинами сети процесс решения повторяют сначала (пункты 1-5).

Рассмотрим метод «метлы» на конкретном примере.

Задана транспортная сеть: ее вершины, звенья и их длина (рис. 1.3).

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

Таблица 1.1
Наименование вершин сети (пунктов)	Рассто-яние	Знак проверки	Соседние вершины
А			-
Б	М	-
В	М	-
Г	М	-
Д	М	-	-
Е	М	-	-
Ж	М	-	-

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

В табл. 1.1 за начальную вершину принята вершина А, поэтому для нее проставляют расстояние, равное нулю, а для остальных вершин - пока неизвестная величина, равная М, где М - большое положительное число. В графу 3 проставляют единицу против той вершины, для которой необходимо определить или проверить расстояние между ней и другими вершинами. В данном случае единица как условный знак проверки проставлена против вершины А. В графу 4 ставят единицу против вершин, которые являются соседними с начальной, т.е. связаны звеньями с вершиной А. Такими вершинами являются Б, В, Г (рис. 1.3).

Таблица 1.2
Наименование вершин сети (пунктов)	Рассто- яние	Знак проверки	Соседние вершины
А		+	-
Б			-
В
Г			-
Д	М	-
Е	М	-	-
Ж	М	-	-

Так как можно, пользуясь схемой дорожной сети, определить расстояние от начальной вершины до ее соседних вершин, составляется новая табл. 1.2, в которой в графе 2 у вершин, соседних с начальной и отмеченных единицей в графе 4 табл. 1.1, значения М меняются на фактические длины звеньев АБ, АВ, и AГ.

В графе 3 табл. 1.2 знак проверки 1 ставится против той вершины, для которой изменилось расстояние М на фактическое, т.е. в данном примере у вершин Б, В, Г. В той же графе для вершины А ставится знак «+», т.е. вершина А проверена. Просматриваются подряд все вершины, имеющие знак проверки - единицу в графе 3. Следующей проверяемой вершиной, таким образом, является вершина Б.

В графе 4 табл. 1.2 отмечаются единицами вершины, соседние с вершиной Б. Такими на рис. 1.3 являются вершины В и Д.

Таблица 1.3
Наименование вершин сети (пунктов)	Рассто- яние	Знак проверки	Соседние вершины
А		+	-
Б		+	-
В			-
Г
Д		-
Е	М	-
Ж	М	-	-

Определяются звенья, соединяющие проверяемую вершину Б с соседними вершинами, отмеченными в графе 4 (В, Д), и вычисляется длина этих звеньев (БВ и БД) как сумма расстояния, указанного в графе 2 для проверяемой вершины Б, и расстояния просматриваемого звена. Полученные результаты заносятся в новую табл. 1.3 в графу 2 вместо чисел М у соответствующих вершин.

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

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

Следующей проверяемой вершиной по порядку является вершина В. Для нее в графе 4 табл. 1.3 отмечаются соседние вершины Г, Д и Е и вычисляются значения.

Предыдущая вершина Б считается проверенной, поэтому знак проверки 1 в строке Б заменяется на знак «+» (графа 3).

Решение задачи методом «метлы» выполняют до тех пор, пока все единицы (знаки проверки) не будут вычеркнуты из столбца проверки (графа 3).

Окончательные результаты расчетов кратчайших расстояний от начальной вершины А до остальных вершин сети представлены в табл. 1.4. и на рис 1.4.

Таблица 1.4
Наименование вершин сети (пунктов)	Рассто- яние	Знак проверки	Соседние вершины
А		+	+
Б		+	+
В		+	+
Г		+	+
Д		+	+
Е		+	+
Ж		+	+

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

ТЕМА 4: ТРАНСПОРТНАЯ ЗАДАЧА. ПОСТРОЕНИЕ МОДЕЛЕЙ ТРАНСПОРТНОЙ ЗАДАЧИ. МЕТОДЫ НАХОЖДЕНИЯ ОПОРНЫХ ПЛАНОВ. МЕТОДЫ ОПТИМИЗАЦИИ.

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

Экономико-математическая модель транспортной задачи в общем виде выглядит следующим образом:

где i – количество грузоотправителей (ГО); j – количество грузополучателей (ГП); a_i - ограничения по предложению; b_j – ограничения по спросу; c_ij – элементы целевой функции; x_ij – объем корреспонденции между i- й и j- й точками.

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

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

Если это условие выполняется, то ТЗ называется сбалансированной (закрытой), в противном случае – несбалансированной (открытой). В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный (реально не существующий) пункт потребления, который будет формально потреблять существующий излишек запасов, т.е.

.

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

.

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

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

.

Таблица 2.1
ГО	ГП
В1	В2	В3	В4
Расстояние, км
А1 А2 А3

Рассмотрим пример транспортной задачи.

Пусть имеются три грузоотправителя А₁, А₂, А₃, от которых следует вывезти однородный груз четырем грузополучателям (В₁, В₂, В₃, В₄) соответственно 400, 600, и 1000т. При этом ГП В₁ необходимо доставить 200 т груза, В₂ - 400, В₃ - 800 и В₄ - 600т.

Расстояния между ГО и ГП указаны в табл. 2.1.

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

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

Обозначим через x_ij объем груза, который должен быть перевезен от i -го поставщика j -му потребителю. Тогда модель задачи выразится следующей системой уравнений:

х₁₁ + х₁₂ + х₁₃ + х₁₄ = 400

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 600

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 1000

х₁₁ + х₂₁ + х₃₁ = 200

х₁₂ + х₂₂ + х₃₂ = 400

х₁₃ + х₂₃ + х₃₃ = 800

х₁₄ + х₂₄ + х₃₄ = 600

Целевая функция будет представлять собой сумму произведений расстояний на соответствующий объем перевозок груза, т:

(16x₁₁+6x₁₂+10x₁₃+4x₁₄+8x₂₁+2x₂₂+12x₂₃+14x₂₄+2x₃₁+18x₃₂+8x₃₃+6x₃₄)→min

Все неизвестные могут принимать положительные значения или равняться нулю, т.е. x_ij ≥ 0.

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

Решение транспортной задачи в основном ведется в табличной форме.

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

МЕТОДЫ НАХОЖДЕНИЯ ОПОРНЫХ ПЛАНОВ

Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

Метод северо-западного угла (диагональный)

Построение опорного плана начинается с верхней левой клетки и заканчивается в нижней правой клетке матрицы. В клетки заносят максимально возможную поставку, учитывая соотношение ресурсов ГО и спрос ГП.

Таблица 2.2
ГО	ГП	Итого по вывозу, т
В1	В2	В3	В4
А1
А2
А3
Итого по ввозу, т

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

Согласно исходному опорному плану, составленному способом северо-западного угла (см. табл. 2.2), суммарная транспортная работа равна

L(x)=200*16+200*6+200*2+400*12+400*8+600*6= 16 400 т*км