§ 2. Критерий оптимальности плана
Для оптимальности допустимого плана необходимо и достаточно, чтобы существовали оценочные числа (потенциалы) а1, а2, …, а n , удовлетворяющие условиям:
а) аjs – аis = Cs (s = 1, …, r) – для Хs > 0 , т.е. для участков, где существует перевозка;
б) аjs – аis ≤ Cs - для Хs = 0, т.е. для участков, где перевозка не осуществляется (разность потенциалов не превосходит затрат по перемещению единицы груза на данном участке).
Любая транспортная задача в сетевой постановке может быть преобразована в матричную. Однако при большом количестве m и n получается очень громоздкая матрица. Практически транспортные задачи чаще решаются в сетевой постановке.
§ 3. Пример решения задачи
Алгоритм решения задачи проиллюстрируем на следующем примере.
Дано: 3 пункта производства:
А с объёмом производства QА = 50 ед. ( например, 50 вагонов и т.д.);
С c объёмом производства QC = 150 ед.
F c объёмом производства QF = 100 ед.
5 Пунктов потребления:
В с объёмом потребления QB = 105 ед.
E с объёмом потребления QE = 30 ед.
L с объёмом потребления QL = 30 ед.
K с объёмом потребления QK = 70 ед.
D с объёмом потребления QD = 65 ед.
Каждый пункт производства связан с каждым пунктом потребления участком сети.
Известны затраты на перевозку по каждому участку сети. (Смотри схему 1). Например, затраты на перевозку из пункта А в пункт В единицы груза равны 60 ед. и т.д.
Требуется составить такой план перевозок, чтобы суммарные затраты на перевозку были минимальными. Если нас интересует суммарный минимальный пробег, то вместо затрат на перевозку принимают расстояния между пунктами, и задача решается таким образом.
Решение задачи
Составляем первоначальный план перевозок.
Стрелки красным карандашом.
Прямоугольники – пункты производства.
Кружки – пункты потребления.
Схема 1. Первоначальный план перевозки
Исходя из первого условия критерия оптимальности, а именно: ajs – ais = Cs для Xs > 0 определяем систему оценочных чисел (потенциалов).
Пусть аА = 100 (первый потенциал задаём произвольно), тогда следуя по сети участков где осуществляются перевозки, определяем оценочные числа для других пунктов (если перевозки (стрелки) совпадают с направлением движения – суммируем затраты по перевозке на участке, если направлены против движения – вычитаем), таким образом получим:
аЕ = 100 + 25 = 125
аL = 100 + 28 = 128
aF = 128 – 30 = 98
aK = 98 + 30 = 128
aD = 98 + 60 = 158
aC = 158 – 100 = 58
aB = 58 + 80 = 138
Проверяем выполнение второго условия критерия оптимальности, а именно: ajs – ais ≤ Cs для участков, на которых не осуществляется перевозка.
aB – aA = 138 – 100 = 38 < 60
aD – aA = 158 – 100 = 58 < 60
aK – aC =128 – 58 = 70 > 50
Из проверки видно, что на участке КС не выполнено второе условие критерия оптимальности (70 > 50). Следовательно, по участку СК нужно осуществлять перевозку.
Для того, чтобы определить, какое количество груза следует везти из пункта С в пункт К, нужно:
во-первых, построить кольцо, связывающее пункты, между которыми есть связь перевозок (кольцо включает один свободный участок с нарушением, а остальные участки обязательно должны быть заняты) - это кольцо пройдёт по участкам СК, KF, FD, DC;
и во-вторых, определить минимальное количество грузов среди участков кольца, на которых стрелки (перевозки) направлены в противоположном кольцу направлении (кольцо направлено на участке с нарушением в сторону пункта с большим оценочным числом.
Наименьшим количеством грузов, перевозимым на указанных участках будет 45 ед. (участок DC). Снимаем это количество груза с участка СD и направляем его по участку СК.
Чтобы сохранился баланс перевозок – эти 45 ед. снимаем с участков кольца, по которым грузопоток идёт в противоположном кольцу направлению, и добавляем к участкам кольца, по которым грузопоток идёт в направлении кольца.
Таким образом, мы приходим к плану (схема 2).
Схема 2
В результате улучшения (перераспределения) плана затраты на перевозку уменьшились на (+ 50 – 30 + 60 – 100) х 45 = - 900
Исходя из первого условия критерия оптимальности, а именно: аjs – аis = Сs для хs > 0 определяем систему оценочных чисел.
Пусть аA = 100 (задаём произвольно), тогда
aE = 100 + 25 = 125
aL = 100 + 28 = 128
aF = 128 – 30 = 98
aD = 98 + 60 = 158
aK = 98 + 30 = 128
aC = 128 – 50 = 78
aB = 78 + 80 = 158.
Проверим выполнение второго условия критерия оптимальности, а именно аjs - аis ≤ Сs для участков, на которых не осуществляется перевозка.
aB – аA = 158 – 100 = 58 < 60
aD – аA = 158 – 100 = 58 < 60
aD – аC = 158 – 78 = 80 < 100
aE – аC = 125 – 78 = 47 > 40 - нарушение!
Из проверки видно, что на участке СE не выполнено первое условие критерия оптимальности (47 > 40).
Следовательно, по участку СЕ нужно осуществить перевозку. Строим кольцо (см. схему 2) и путём перераспределения вводим перевозку по участку СЕ. Получаем новый план (схема 3).
∆Э 3-2 = [(90 + 28 + 30) – (25 + 30 + 50)] … х 10... = - 70 ед. ?
Дальнейший процесс решения идентичен рассмотренному выше (составление системы оценочных чисел, проверка критерия оптимальности, введение перевозки на участке, где не выполнен критерий оптимальности).
Схема 3
aA = 100
aL = 100 + 28 = 128
aE = 100 + 25 = 125
aC = 125 – 40 = 85
aB = 85 + 80 = 165
aK = 85 + 50 = 135
aF = 135 – 30 = 105
aD = 105 + 60 = 165
aL – аF = 128 – 105 = 23 < 30
aD – аC = 165 – 85 = 80 < 100
aB –аA = 165 – 100 = 65 > 60 - нарушение!
В результате получим новый план (схема 4).
Выигрыш: ∆ Э 4-3 = [ (60 + 40) – (80 + 25) ] х 20 = -100
∆ Э 4-1 = - (900 + 70 + 100) = -1070.
Схема 4
aA = 100
aL = 100 + 28 = 128
aB = 100 + 60 = 160
aC = 160 – 80 = 80
aE = 80 + 40 = 120
aK = 80 + 50 = 130
aF = 130 – 30 = 100
aD = 100 + 60 = 160
aE – aA = 120 – 100 = 20 < 25
aL – aF = 128 – 100 = 28 < 30
aD –aC = 160 – 80 < 100
aD –aA = 160 – 100 = 60 = 60
Этот план является оптимальным, так как удовлетворяет обоим условиям оптимальности.
При полученной схеме перевозок суммарные затраты равны
60 х 20 + 80 х 85 + 40 х 30 + 50 х 35 + 30 х 35 + 28 х 30 + 60 х 65 = 16740 ед. против 17810 в первоначальном плане, экономия – 1070 ед.
По приведённому алгоритму можно также решить задачу с ограниченными пропускными способностями участков и установить, насколько необходимо увеличить пропускную способность лимитирующих участков (приёмных пунктов), чтобы обеспечить перевозку грузов с минимальными затратами. В случае, если XS > qS (где qS - пропускная способность S -го участка), для оптимальности плана необходимо и достаточно выполнение условий:
1) аJS - аIS = СS + dS для XS > 0
2) аJS - аIS ≤ СS + dS для XS = 0
где dS - рента (прокатная оценка) отчётных участков пути, рассчитанная на единицу груза;
3) dS ≥ 0
dS = 0, если XS < qS , т.е. когда объём перевозки на S -том участке меньше его пропускной способности.
Прокатные оценки – это постоянные элементы специального экономического расчёта, учитывающие лимитированность и дефицитность отдельных видов оборудования (в частности, ограничения по пропускной способности). Прокатная оценка показывает, какую экономию труда можно достигнуть введя дополнительное количество наиболее экономичных машин (или повышая пропускную способность на участке пути с минимальной себестоимостью). Для случая транспортной задачи прокатная оценка определяется, например, если вследствие ограниченной пропускной способности пути перевозки с железнодорожного или водного транспорта передаются на более дорогостоящий автомобильный и т.п.
В настоящее время эти оценки по существу пока не учитываются.
Размер прокатной оценки в транспортной задаче определяется через потенциалы. Если пункты рассматриваемой сети разбиваются на несколько групп, не связанных между собой грузопотоками, потенциалы определяются через систему неравенств.
При решении транспортной задачи в сетевой постановке, как и при матричной, могут встретиться некоторые осложнения (например, «вырождённость»). Этого можно избежать, как и в матричной задаче, путём изменения начальных данных и введения «фиктивного» очень малого потока.
Существует несложное доказательство того, что если в модели с промежуточными пунктами суммарный объём производства отличен от суммарного объёма потребления, то допустимых решений не существует. Иными словами, в сетевой постановке может решаться только «закрытая» модель транспортной задачи.
Если сетевая задача решается на минимум пробега, могут быть использованы упрощённые методы, в частности, графический и метод круговых разниц.
Для установления прямых связей между поставщиками и потребителями на длительный период (2 – 5 лет) целесообразно решать параметрическую транспортную задачу, учитывая изменяющиеся объёмы производства и потребления.