Пример решения задачи методом потенциалов

Предварительный шаг.

1. Найдем допустимый ациклический план методом северо-западного угла (возьмем план из табл. 13).

2. Второй этап предварительного шага: определение системы потенциалов.

Потенциал приписывается каждому пункту отправления (обоз­начается u_i) и каждому пункту назначения (v_j). Всего потенци­алов m + n чисел. Они вносятся в специально отведенные для этого строку и столбец макета (табл. 14).

Для базисных тарифов c_ij, должны выполняться равенства

.

Эти равенства и будут служить теми уравнениями, из которых.находятся потенциалы. Однако таких уравнений будет только (m + n – 1), а неизвестных в системе (m + n), т. е. на единицу больше. Такая система уравнений имеет бесчисленное множество решений, любое из которых годится для нашей цели. Чтобы найти какое-то одно решение, значение одного потенциала вы­бираем произвольно (например, полагаем u₁ = 0). Остальные потенциалы определяем из решения системы.

Продолжим решение приведенного выше примера. Перепишем основную часть табл. 13 с найденным в ней допустимым планом; потенциалы пунктов пока запишем буквами (табл. 14).

Таблица 14

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

Пункты назн. Пункты отправ.		B1	B2	B3	B4	Запасы груза
	vj ui	v1	v2	v3	v4
A1	u1		–	–	–
А2	u2			–	–
A3	u3	–
Потребности в грузе

В макете m + n – 1 = 6 и число компонент плана тоже рав­но 6. Можно отыскивать потенциалы. (Если бы число компонент плана было меньше 6, надо было бы включить в план недо­стающее число клеток с нулевыми перевозками, но чтобы при этом не было циклов.) Для базисных клеток составляем равенства:

Мы получили шесть уравнений с семью неизвестными. Пола­гаем u₁ = 0 и остальные потенциалы вычисляем последова­тельно: v₁ = 2, u₂ = 1, v₂ = 4, u₃ = — 4, v₃ = 9, v₄ = 3. С этими потенциалами получаем табл. 15.

Таблица 15

Определение потенциалов

vj ui					Запасы груза
		–	–	–
			–	–
–4	–
Потребности в грузе

Потенциалы можно вычислить в таблице: при движении вверх тариф к потенциалу прибавляется, вниз — вычитается.

3. Третий этап предварительного шага: испытание системы потенциалов на потенциальность.

Потенциальность заключается в том, чтобы неравенство

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

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

После исследования клетки (1, 3) сразу можно было сказать, что план не потенциален. Однако такие вычисления всегда надо производить для всех свободных клеток.

Выделим случаи нарушения условий и запишем их в виде

В общем случае выделяем положительные разности δ_ij:

На этом предварительный шаг закончен.

Общий повторяющийся шаг.

1. Из положительных разностей δ_ij находим наибольшую разность, :

.

Наибольшая разность δ₀ = 3 имеет место для клетки (1,3). Вклю­чаем эту клетку в набор и строим на цикл (табл. 16).

2. Означиваем цикл, т. е. расставляем знаки в его верши­нах. В исходной клетке (включаемой в набор) ставим плюс, двигаемся по ходу или против хода часовой стрелки и ставим знаки попеременно минус, плюс, — пока не придем к исходной вершине.

Таблица 16

Сдвиг по циклу на 80

3. Выбираем наименьшее значение перевозки θ в клетках отри­цательной полуцепи (х_ij)^–.

min (x_ij)^– = θ.

Наименьшая перевозка в отрицательной полуцепи равна 80, причем она в двух клетках: (2, 2) и (3, 3). Возьмем θ = 80 в клетке (3, 3).

4. Делаем сдвиг по циклу на величину θ.

В клетку (1, 3), включенную в набор, запишем перевозку 80; к перевозкам в клетках (3, 2), (2, 1) прибавим по 80; из перевозок в клет­ках (1, 1), (2, 2) и (3, 3) вычитаем по 80. В клетке (3, 3) ноля не пишем, так как она из плана исключается. В клетке (2, 2) записываем ноль: она остается в плане для сохранения в нем числа базисных клеток, которое равно (m + n – 1). В результате приходим к плану, помещенному в табл. 17.

Таблица 17

Плен не оптимален, делаем сдвиг на 100

5. Для полученного после сдвига плана составляем новую систему потенциалов. Их можно найти исправлением уже имеющейся системы. Для клетки (1, 3) оставим u₁ = 0, а v₃ исправим с 9 на 6, тогда

.

По остальным занятым клеткам равенства выполняются со ста­рыми потенциалами. Так новая система потенциалов получена одним исправлением.

6. Производим исследование новой системы на потенциаль­ность. Для этого проверяем выполнение неравенств

для всех незанятых клеток.

Условие не выполнено только в одной клетке (3, 1). Вклю­чаем ее в набор, выделяем цикл, делаем сдвиг (табл. 17). На­ходим новый план (табл. 18). Исправляем для него потенциалы и записываем их в таблицу.

Таблица 18

Оптимальный план, полученный методом потенциалов

vj ui					Запасы груза
		–		–
			–	–
–2			–
Потребности в грузе

Испытываем эту систему на потенциальность:

Для всех свободных клеток разность потенциалов меньше или равна тарифу; система потенциальна, план оптимален.

Стоимость перевозок по данному плану будет наименьшей:

.

Характерно, что в клетке (2, 1) перевозка равна нулю, хотя там и наименьший тариф. Получаемый от этого по первому пункту назначения перерасход перекрывается экономией на других маршрутах. Оптимальный план здесь не очевиден.

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

Окончательный (оптимальный) план проверяется по формуле, вытекающей из доказательства основной теоремы:

при этом контролируются и потенциалы. Для примера из табл. 18 имеем:

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

Лекция 4.