2. Определение рациональных вариантов грузопотоков

Для определения рациональных вариантов грузопотоков необходимо:

сформулировать математическую модель задачи;

выбрать способ составления базисного плана;

определить метод оптимизации базисного плана;

показать промежуточные и конечные результаты расчета.

Рассмотрим применение метода потенциалов на следующем примере.

Задача. Из трех грузообразующих пунктов А₁, А₂, А₃ необходимо перевезти однородный груз четырем потребителям В₁, В₂, В₃, В₄. Количество груза в пункте А₁ = 300т, в пункте А₂ = 500т, А₃ = 800т. Спрос потребителей на данный груз составляет: В₁ = 200т, В₂ = 350т, В₃ = 650т, В₄ = 400т. Расстояние между грузоотправителями и грузополучателями приведены в таблице 2.2.

Таблица 2.2. Расстояния между грузообразующими и грузопоглощающими пунктами, км

Грузопоглощающие	Грузообразующие пункты
пункты	А1	А2	А3
В1 В2 В3 В4	11 7 9 5	5 13 7 8	3 12 5 9

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

Для решения задачи обозначим через х_ij количество тонн груза, которое должно быть перевезено от i поставщика j потребителю. Тогда ограничения задачи выразятся системой уравнений (2.8), а целевая функция, представляющая собой сумму произведений расстояний на соответствующий объем перевозок груза в тоннах, уравнением (2.9).

х₁₁+х₁₂+х₁₃+х₁₄ = 300 (1)

х₂₁+х₂₂+х₂₃+х₂₄ = 500 (2)

х₃₁+х₃₂+х₃₃+х₃₄ = 800 (3)

х₁₁+ х₂₁+ х₃₁ = 200 (4) (2.8)

х₁₂+ х₂₂+ х₃₂ = 350 (5)

х₁₃+ х₂₃+ х₃₃ = 650 (6)

х₁₄+ х₂₄+ х₃₄ = 400 (7)

Минимизировать 11х₁₁+7х₁₂+9х₁₃+5х₁₄+5х₂₁+13х₂₂+7х₂₃+8х₂₄+

3х₃₁+12х₃₂+5х₃₃+9х₃₄. (2.9)

Полученная система уравнений (2.8) является линейно зависимой, так как любое ее уравнение можно представить в виде линейной комбинации остальных уравнений. Действительно, если из суммы уравнений 1, 2, 3 вычесть сумму уравнений 4, 5, 6, то получим уравнение 7 и т.п. Число линейно независимых уравнений должно быть меньше на одно общего числа уравнений в системе, т.е. базис системы должен быть равен количеству уравнений в системе ограничений за вычетом единицы. Так как общее число уравнений в системе определяется суммой поставщиков и потребителей, то в базисе должно быть уравнений

m + n - 1,

где m - число поставщиков;

n - число потребителей.

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

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

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

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

Таблица 2.3. Базисный план, составленный способом наименьшего элемента по строке

Грузопоглоща-	Грузообразующие пункты			Итого
ющие пункты	А1	А2	А3
В1	11	5	3 200	200
В2	7 300	13	12 50	350
В3	9	7 100	5 550	650
В4	5	8 400	9	400
Итого	300	500	800	1600

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

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

l_ij = U_i + V_j ,

где U_i - значение потенциала столбца;

V_j - значение потенциала строки.

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

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

Потенциалы незагруженных (свободных) клеток определяются по формуле

E_ij = l_ij - (U_i + V_j) ,

где E_ij - потенциал свободной клетки.

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

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

Проверим на оптимальность базисный план, составленный способом наименьшего элемента по строке. Для этого матрицу дополним столбцом и строкой, таблица 2.4.

Таблица 2.4.

Грузопогло-	Грузообразующие пункты				Потенци-
щающие пункты	А1	А2	А3	Итого	алы строк
В1	+2 11	0 5	0 3 200	200	0
В2	0 7 300	-1 13	0 12 50	350	9
В3	+9 9	0 7 100	0 5 550	650	2
В4	+4 5	0 8 400	+3 9	400	3
Итого	300	500	800	1600
Потенциалы столбцов	-2	5	3

Поставим в строке В₁ величину потенциала равную нулю. Тогда, согласно формулы (2.11) потенциал столбца А₃ будет равен 3. Потенциал строки В₃ будет равен 2, а столбца А₂ - 5 и т.д., таблица 2.4.

Потенциалы незагруженных клеток находим по формуле (2.12).

В результате проверки допустимого плана на оптимальность получена клетка А₂ - В₂, имеющая отрицательный потенциал. Это указывает на то, что план не оптимален и необходимо выполнить перераспределение закрепления поставщиков за потребителями. Это выполняется следующим образом: строится контур. Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы соединений между которыми равны 90. Строится контур так, чтобы все углы, кроме одного, располагались в загруженных клетках, а один угол в свободной, наиболее потенциальной клетке. При соблюдении этих правил для каждой свободной (незагруженной) клетки можно построить только один контур. Определяют положительные (+) и отрицательные (-) углы контура. Первый положительный угол лежит в незагруженной клетке для которой строится контур, рядом с ним находятся отрицательные углы.

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

Ранее загруженные клетки, которые не оказались расположенными в углах контура, переносятся в матрицу нового варианта закрепления потребителей груза за поставщиками без изменения, таблица 2.5.

Таблица 2.5.

Грузопогло-	Грузообразующие пункты				Потенци-
щающие пункты	А1	А2	А3	Итого	алы строк
В1	11	5	3 200	200	0
В2	7 300	13 50	12	350	8
В3	9	7 50	5 600	650	2
В4	5	8 400	9	400	3
Итого	300	500	800	1600
Потенциалы столбцов	-1	5	3

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

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

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

углы контура обозначить попеременно знаками “плюс” и “минус”. Углу, лежащему в загруженной клетке, для которой построен контур, присваивается знак “плюс”;

выявить наименьшую загрузку в клетках, занятых углами, со знаком “плюс” и вычесть ее из всех этих клеток и прибавить во все клетки, занятые углами со знаком “минус”.

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

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