Решение Транспортной Задачи Методом Потенциалов

1. Проверка баланса

Суммарная мощность поставщиков: \(30 + 30 + 30 + 10 = 100\)

Суммарная потребность потребителей: \(20 + 20 + 20 + 20 + 20 = 100\)

Задача сбалансирована, так как суммарная мощность равна суммарной потребности.

2. Построение опорного плана методом северо-западного угла

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

Таблица затрат:

Заполняем опорный план:

Ячейка (1,1): \(x_{11} = \min(30, 20) = 20\). Остаток у поставщика 1: \(30 - 20 = 10\). Потребность потребителя 1 удовлетворена.

Ячейка (1,2): \(x_{12} = \min(10, 20) = 10\). Остаток у поставщика 1: \(10 - 10 = 0\). Потребность потребителя 2: \(20 - 10 = 10\).

Ячейка (2,2): \(x_{22} = \min(30, 10) = 10\). Остаток у поставщика 2: \(30 - 10 = 20\). Потребность потребителя 2 удовлетворена.

Ячейка (2,3): \(x_{23} = \min(20, 20) = 20\). Остаток у поставщика 2: \(20 - 20 = 0\). Потребность потребителя 3 удовлетворена.

Ячейка (3,4): \(x_{34} = \min(30, 20) = 20\). Остаток у поставщика 3: \(30 - 20 = 10\). Потребность потребителя 4 удовлетворена.

Ячейка (3,5): \(x_{35} = \min(10, 20) = 10\). Остаток у поставщика 3: \(10 - 10 = 0\). Потребность потребителя 5: \(20 - 10 = 10\).

Ячейка (4,5): \(x_{45} = \min(10, 10) = 10\). Остаток у поставщика 4: \(10 - 10 = 0\). Потребность потребителя 5 удовлетворена.

Опорный план:

В скобках указаны затраты на перевозку.

Количество занятых ячеек: \(m + n - 1 = 4 + 5 - 1 = 8\). В нашем плане 7 занятых ячеек. Это означает, что план вырожденный. Для применения метода потенциалов необходимо ввести фиктивную перевозку в одну из свободных ячеек с нулевым объемом.

Выберем ячейку (1,3) для фиктивной перевозки \(x_{13} = 0\).

Обновленный опорный план:

3. Расчет потенциалов \(u_i\) и \(v_j\)

Для занятых ячеек \(c_{ij} = u_i + v_j\). Примем \(u_1 = 0\).

Из \(c_{11} = u_1 + v_1 \Rightarrow 14 = 0 + v_1 \Rightarrow v_1 = 14\)

Из \(c_{12} = u_1 + v_2 \Rightarrow 20 = 0 + v_2 \Rightarrow v_2 = 20\)

Из \(c_{13} = u_1 + v_3 \Rightarrow 7 = 0 + v_3 \Rightarrow v_3 = 7\)

Из \(c_{22} = u_2 + v_2 \Rightarrow 4 = u_2 + 20 \Rightarrow u_2 = -16\)

Из \(c_{23} = u_2 + v_3 \Rightarrow 14 = -16 + v_3 \Rightarrow v_3 = 30\). (Противоречие! Это означает, что выбор фиктивной ячейки был неудачным или есть ошибка в расчетах. Давайте перепроверим.)

Давайте пересчитаем потенциалы, используя другой подход. Выберем \(u_1 = 0\).

Занятые ячейки: (1,1), (1,2), (1,3), (2,2), (2,3), (3,4), (3,5), (4,5).

Из \(c_{11} = u_1 + v_1 \Rightarrow 14 = 0 + v_1 \Rightarrow v_1 = 14\)

Из \(c_{12} = u_1 + v_2 \Rightarrow 20 = 0 + v_2 \Rightarrow v_2 = 20\)

Из \(c_{13} = u_1 + v_3 \Rightarrow 7 = 0 + v_3 \Rightarrow v_3 = 7\)

Из \(c_{22} = u_2 + v_2 \Rightarrow 4 = u_2 + 20 \Rightarrow u_2 = -16\)

Из \(c_{23} = u_2 + v_3 \Rightarrow 14 = -16 + v_3 \Rightarrow v_3 = 30\). (Это действительно противоречие. Значит, ячейка (1,3) не подходит для фиктивной перевозки, так как она образует цикл с другими занятыми ячейками при расчете потенциалов. Нужно выбрать такую ячейку, чтобы граф занятых ячеек оставался деревом.)

Вернемся к исходному опорному плану без фиктивной ячейки и найдем цикл для вырожденности. Опорный план:

Количество занятых ячеек: 7. Требуется 8. Мы можем добавить фиктивную перевозку в любую свободную ячейку, которая не образует цикл с существующими занятыми ячейками. Попробуем добавить \(x_{13} = 0\).

Занятые ячейки: (1,1), (1,2), (1,3), (2,2), (2,3), (3,4), (3,5), (4,5).

Потенциалы:

\(u_1 = 0\)

\(c_{11} = u_1 + v_1 \Rightarrow 14 = 0 + v_1 \Rightarrow v_1 = 14\)

\(c_{12} = u_1 + v_2 \Rightarrow 20 = 0 + v_2 \Rightarrow v_2 = 20\)

\(c_{13} = u_1 + v_3 \Rightarrow 7 = 0 + v_3 \Rightarrow v_3 = 7\)

\(c_{22} = u_2 + v_2 \Rightarrow 4 = u_2 + 20 \Rightarrow u_2 = -16\)

\(c_{23} = u_2 + v_3 \Rightarrow 14 = -16 + 7 \Rightarrow 14 = -9\). Это неверно. Значит, ячейка (1,3) не подходит.

Давайте попробуем другую фиктивную ячейку. Например, (2,1).

Занятые ячейки: (1,1), (1,2), (2,1), (2,2), (2,3), (3,4), (3,5), (4,5).

\(u_1 = 0\)

\(c_{11} = u_1 + v_1 \Rightarrow 14 = 0 + v_1 \Rightarrow v_1 = 14\)

\(c_{12} = u_1 + v_2 \Rightarrow 20 = 0 + v_2 \Rightarrow v_2 = 20\)

\(c_{21} = u_2 + v_1 \Rightarrow 18 = u_2 + 14 \Rightarrow u_2 = 4\)

\(c_{22} = u_2 + v_2 \Rightarrow 4 = 4 + 20 \Rightarrow 4 = 24\). Это неверно. Значит, ячейка (2,1) тоже не подходит.

Проблема в том, что метод северо-западного угла может создавать вырожденные опорные планы, и выбор фиктивной ячейки требует внимательности. Давайте перепроверим, какие ячейки заняты и какие свободны. Занятые: (1,1), (1,2), (2,2), (2,3), (3,4), (3,5), (4,5).

Попробуем добавить фиктивную перевозку в ячейку (3,3).

Занятые ячейки: (1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (3,5), (4,5).

\(u_1 = 0\)

\(c_{11} = u_1 + v_1 \Rightarrow 14 = 0 + v_1 \Rightarrow v_1 = 14\)

\(c_{12} = u_1 + v_2 \Rightarrow 20 = 0 + v_2 \Rightarrow v_2 = 20\)

\(c_{22} = u_2 + v_2 \Rightarrow 4 = u_2 + 20 \Rightarrow u_2 = -16\)

\(c_{23} = u_2 + v_3 \Rightarrow 14 = -16 + v_3 \Rightarrow v_3 = 30\)

\(c_{33} = u_3 + v_3 \Rightarrow 16 = u_3 + 30 \Rightarrow u_3 = -14\)

\(c_{34} = u_3 + v_4 \Rightarrow 12 = -14 + v_4 \Rightarrow v_4 = 26\)

\(c_{35} = u_3 + v_5 \Rightarrow 20 = -14 + v_5 \Rightarrow v_5 = 34\)

\(c_{45} = u_4 + v_5 \Rightarrow 7 = u_4 + 34 \Rightarrow u_4 = -27\)

Потенциалы:

\(u_1 = 0, u_2 = -16, u_3 = -14, u_4 = -27\)

\(v_1 = 14, v_2 = 20, v_3 = 30, v_4 = 26, v_5 = 34\)

4. Расчет оценок для свободных ячеек

Оценка свободной ячейки \((i,j)\) рассчитывается как \(\Delta_{ij} = c_{ij} - (u_