Решение транспортной задачи методом потенциалов

Пример 2.5. Решить следующую ТЗ методом потенциалов.

а=(40,30,20),

b=(30,25,15,20),

Решение. Проверим условие:

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

Таблица 1.

	M1	M2	M3	M4
P1
P2	1 -		2 +
P3	2 + z		5 -
					ai bj

Затем в этой же таблице строим начальный ОП методом "минимальной стоимости" (об этом и других методах построения начального ОП можно прочитать, например:

План является вырожденным, так как m+n-1=6, (см. свойство 4), а для X⁰число ненулевых перевозок равно 5.

Проверим данный план на оптимальностьприпомощи критерия (21)-(22)Сначала для x_ij>0 в плане X⁰ вычислим потенциалы по формуле(21):

u₁+v₂=c₁₂=3

u₁+v₄=c₁₄=4

u₂+v₁=c₂₁=1 (17)

u₃+v₃=c₃₃=5

u₃+v₄=c₃₄=7

В этой системе 7 неизвестных и 5 уравнений, т.е. ее нельзя решить. Поэтому выбираем сами u₁=0 (см. примечание ниже). Тогда из первых двух уравнений найдем: v₂=3, v₄=4; Из последних двух: u₃=3, v₃=2. Далее вычисления прерываются (следствие вырожденности плана Х⁰). В таких случаях вводят фиктивные перевозки, записывая в соответствующие клетки 0, но считая эти перевозки ненулевыми. Существует много способов определения фиктивного маршрута (клетки) так, чтобы система потенциалов определялась однозначно.

Для фиктивных перевозок мы выберем клетку (2,3) по следующим соображениям:

а) этот маршрут наиболее дешевый (c₂₃ =2)

б) при добавлении уравнения

u₂+v₃=c₂₃=2

система (23) разрешается однозначно:

u₁=0, u₂=0, u₃=3;

v₁=1, v₂=3, v₃=2, v₄=4;

Теперь проверим выполнение неравенств (17) для нашего плана (для х_ij=0 в X⁰):

u₁+v₁-c₁₁=-3<0

u₁+v₃-c₁₃=-4<0

u₂+v₂-c₂₂=-3<0

u₂+v₄-c₂₄=-4<0

u₃+v₁-c₃₁=+2>0 ←

u₃+v₂-c₃₂=+2>0 ←

Видим, что критерий оптимальности не выполнен (последние два неравенства), так что план X⁰ неоптимален.

Надо построить новый план перевозок. Идея состоит в изменении объема перевозок по некоторым из маршрутов. Для определения этих маршрутов строим цикл - последовательность ненулевых клеток таблицы (маршрутов), в которой соседними являются две и только две ненулевые клетки одного столбика или одной строки, а последняя клетка последовательности находится либо в том же столбике, либо в той же строке, что и начальная клетка последовательности. "Вершины" цикла (т.е. клетки, вошедшие в цикл) и показывают те маршруты, по которым нужно изменить объемы перевозок. Остается определить начальную клетку цикла - клетку с наихудшей (положительной) оценкой в системе (24).

В данном случае можно взять как клетку (3,1) так и (3,2). Возьмем клетку (3,1) и напишем в эту клетку пока неизвестное число z (в таблицу 1). Начиная с этой клетки, строим цикл (см. таблицу 1): (3,1) → (3,3) → (2,3) → (2,1). Впишем в начальную клетку знак "+" и далее последовательно ''-'', "+" по вершинам цикла, как это показано в таблице 1. Значение z (объем новых перевозок по маршруту (3,1)) определяется из условия: z=min{ }, где - объем перевозок по маршрутам, отмеченным знаком "-". Итак z=min{15,30}=15. Эту величину 15 отнимаем из объема перевозок, отмеченных знаком “-“, и прибавляем к объемам перевозок, отмеченных знаком "+" (балансируем). Результаты записываем в новую таблицу, перенося туда остальные перевозки без изменения:

Таблица 2.

	M1	M2	M3	M4
P1				4 +
P2
P3		4 + z		7 -	-
					ai bj

Получим новый ОП:

Видно, что он невырожденный, следовательно при проверке на оптимальность плана X⁰⁰ система (21) разрешится однозначно (не нужно будет вводить фиктивные перевозки).

Самостоятельно проверьте, что ОП X⁰⁰ неоптимален, и что на третьей итерации получается оптимальный опорный план (выполнены все неравенства (17)):

Вычислите суммарные стоимости перевозок по X⁰, X⁰⁰, X⁰⁰⁰ по формуле (5) и убедитесь в оптимальности плана перевозок X⁰⁰⁰.

Как видно из решенного примера, алгоритм метода потенциалов следующий:

1) Занести данные задачи (транспортные издержки, спросы и предложения) в специальную рабочую таблицу;

2) Вычислить начальный ОП;

3) Проверить ОП на оптимальность;

3.1) Найти значения потенциалов для данного ОП по формуле (21); если ОП вырожденный, то ввести фиктивные перевозки;

3.2) Проверить выполнение неравенств (22): если они все выполнены, то данный ОП оптимален - вычисления прекратить; если нет, то перейти к пункту 4;

4) Построить новый ОП;

4.1) Построить цикл;

4.2) Изменить по вершинам цикла объемы перевозок;

4.3) Заполнить новую рабочую таблицу и перейти к пункту 3.

Примечания к методу потенциалов.

1. Систему потенциалов однозначно можно вычислить только для невырожденного ОП, при этом одному из потенциалов нужно придать произвольное значение (обычно u₁=0, т.к. всистеме ограничений закрытой ТЗ имеется одно линейно зависимое ограничение).

2. В случае вырожденного ОП нужно ввести фиктивные перевозки с таким расчетом, чтобы из системы (21) однозначно вычислить все потенциалы.

3. Цикл всегда существует и единственен для каждой свободной клетки таблицы (для невырожденного ОП).

4. Если для какой-то свободной клетки (x_ij= 0) оптимального ОП в соотношении (22) достигается строгое равенство, то это говорит о неединственности оптимального ОП.

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