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

Задание 6

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

1. Формулировка задачи:

У нас есть два поставщика (обозначим их \(a_i\)) с объемами поставок 30 и 130 единиц.
У нас есть три потребителя (обозначим их \(b_j\)) с потребностями 60, 60 и 40 единиц.
Таблица содержит стоимости перевозки единицы продукции от каждого поставщика к каждому потребителю.

Проверка сбалансированности:
Сумма предложений: \(30 + 130 = 160\).
Сумма потребностей: \(60 + 60 + 40 = 160\).
Задача сбалансирована.

2. Нахождение начального допустимого плана (метод северо-западного угла):

• Начинаем с левого верхнего угла таблицы.
• Поставщик \(a_1\) имеет 30 единиц, а потребитель \(b_1\) требует 60. Мы можем перевезти 30 единиц от \(a_1\) к \(b_1\).
  • Остаток у \(a_1\): \(30 - 30 = 0\). Строка \(a_1\) закрывается.
  • Остаток у \(b_1\): \(60 - 30 = 30\).

• Переходим к следующей свободной ячейке в первом столбце (где осталась потребность). Это ячейка \((a_2, b_1)\). Поставщик \(a_2\) имеет 130 единиц, а потребитель \(b_1\) требует 30. Мы можем перевезти 30 единиц от \(a_2\) к \(b_1\).
  • Остаток у \(a_2\): \(130 - 30 = 100\).
  • Остаток у \(b_1\): \(30 - 30 = 0\). Столбец \(b_1\) закрывается.

• Переходим к следующей свободной ячейке в первой строке (которая теперь закрыта) или в первом столбце (который теперь закрыт). Следующая свободная ячейка - \((a_2, b_2)\). Поставщик \(a_2\) имеет 100 единиц, а потребитель \(b_2\) требует 60. Мы можем перевезти 60 единиц от \(a_2\) к \(b_2\).
  • Остаток у \(a_2\): \(100 - 60 = 40\).
  • Остаток у \(b_2\): \(60 - 60 = 0\). Столбец \(b_2\) закрывается.

• Переходим к следующей свободной ячейке - \((a_2, b_3)\). Поставщик \(a_2\) имеет 40 единиц, а потребитель \(b_3\) требует 40. Мы можем перевезти 40 единиц от \(a_2\) к \(b_3\).
  • Остаток у \(a_2\): \(40 - 40 = 0\). Строка \(a_2\) закрывается.
  • Остаток у \(b_3\): \(40 - 40 = 0\). Столбец \(b_3\) закрывается.

Начальный допустимый план:
* \(x_{11} = 30\)
* \(x_{21} = 30\)
* \(x_{22} = 60\)
* \(x_{23} = 40\)

Стоимость начального плана:
\(C = 30 \times 5 + 30 \times 6 + 60 \times 12 + 40 \times 18 = 150 + 180 + 720 + 720 = 1770\).

3. Проверка оптимальности и переход к методу потенциалов:

Количество базисных переменных (ненулевых перевозок) равно \(m + n - 1 = 2 + 3 - 1 = 4\). У нас их 4, что соответствует условию.

Теперь используем метод потенциалов. Обозначим потенциалы строк как \(u_i\) и потенциалы столбцов как \(v_j\). Для базисных переменных (направлениях перевозок с ненулевым объемом) выполняется условие: \(u_i + v_j = c_{ij}\), где \(c_{ij}\) - стоимость перевозки.

Выберем \(u_1 = 0\).
* Для \(x_{11} = 30\): \(u_1 + v_1 = c_{11} \Rightarrow 0 + v_1 = 5 \Rightarrow v_1 = 5\).
* Для \(x_{21} = 30\): \(u_2 + v_1 = c_{21} \Rightarrow u_2 + 5 = 6 \Rightarrow u_2 = 1\).
* Для \(x_{22} = 60\): \(u_2 + v_2 = c_{22} \Rightarrow 1 + v_2 = 12 \Rightarrow v_2 = 11\).
* Для \(x_{23} = 40\): \(u_2 + v_3 = c_{23} \Rightarrow 1 + v_3 = 18 \Rightarrow v_3 = 17\).

Мы нашли все потенциалы: \(u_1=0, u_2=1, v_1=5, v_2=11, v_3=17\).

Теперь вычисляем избыточные стоимости (или разности потенциалов) для небазисных переменных: \(\Delta_{ij} = c_{ij} - (u_i + v_j)\).

• Ячейка \((a_1, b_2)\): \(\Delta_{12} = c_{12} - (u_1 + v_2) = 7 - (0 + 11) = 7 - 11 = -4\).
• Ячейка \((a_1, b_3)\): \(\Delta_{13} = c_{13} - (u_1 + v_3) = 12 - (0 + 17) = 12 - 17 = -5\).
• Ячейка \((a_2, b_1)\): \(\Delta_{21}\) - это базисная переменная, уже учтена.

Так как мы нашли отрицательные избыточные стоимости (\(\Delta_{12} = -4\) и \(\Delta_{13} = -5\)), текущий план не является оптимальным. Нам нужно внести изменения, чтобы уменьшить общую стоимость.

4. Улучшение плана:

Выбираем ячейку с самой отрицательной избыточной стоимостью для введения в базис. Это ячейка \((a_1, b_3)\) с \(\Delta_{13} = -5\).

Строим цикл:
1. Вводим ячейку \((a_1, b_3)\).
2. Чтобы сохранить баланс, находим ячейку в той же строке (\(a_1\)) или столбце (\(b_3\)), которая является базисной. Ближайшая базисная ячейка в строке \(a_1\) - это \((a_1, b_1)\).
3. От \((a_1, b_1)\) переходим к базисной ячейке в том же столбце (\(b_1\)) - это \((a_2, b_1)\).
4. От \((a_2, b_1)\) переходим к базисной ячейке в той же строке (\(a_2\)) - это \((a_2, b_2)\) или \((a_2, b_3)\). Нам нужна ячейка, которая позволит замкнуть цикл. Ближайшая к \((a_2, b_1)\) в строке \(a_2\) - это \((a_2, b_3)\).
5. От \((a_2, b_3)\) переходим к базисной ячейке в том же столбце (\(b_3\)) - это \((a_2, b_3)\) (но это введенная ячейка).

Цикл: \((a_1, b_3) \rightarrow (a_1, b_1) \rightarrow (a_2, b_1) \rightarrow (a_2, b_3)\).

Базисные ячейки: \((1,1), (2,1), (2,2), (2,3)\).
Вводим \((1,3)\). Цикл: \((1,3) \rightarrow (1,1) \rightarrow (2,1) \rightarrow (2,3)\).

• В ячейку \((a_1, b_3)\) добавляем \(\theta\).
• В ячейку \((a_1, b_1)\) (крест, минус) вычитаем \(\theta\).
• В ячейку \((a_2, b_1)\) (крест, плюс) добавляем \(\theta\).
• В ячейку \((a_2, b_3)\) (крест, минус) вычитаем \(\theta\).

Текущие объемы в базисных ячейках: \(x_{11}=30, x_{21}=30, x_{22}=60, x_{23}=40\).
* \(x_{11}\) становится \(30 - \theta\).
* \(x_{21}\) становится \(30 + \theta\).
* \(x_{23}\) становится \(40 - \theta\).

Чтобы сохранить неотрицательность, \(\theta\) должно быть минимальным из положительных значений, которые вычитаются:
\(\theta = \min(30, 40) = 30\).

Вычитаем \(\theta=30\) из ячейки \((a_1, b_1)\), которая становится \(30 - 30 = 0\). Таким образом, ячейка \((a_1, b_1)\) выходит из базиса.
Добавляем \(\theta=30\) в ячейку \((a_1, b_3)\), которая становится \(0 + 30 = 30\).
Добавляем \(\theta=30\) в ячейку \((a_2, b_1)\), которая становится \(30 + 30 = 60\).
Вычитаем \(\theta=30\) из ячейки \((a_2, b_3)\), которая становится \(40 - 30 = 10\).

Новый план (первая итерация):
* \(x_{11} = 0\) (вышла из базиса)
* \(x_{13} = 30\) (вошла в базис)
* \(x_{21} = 60\)
* \(x_{22} = 60\)
* \(x_{23} = 10\)

Стоимость нового плана:
\(C = 0 \times 5 + 30 \times 12 + 60 \times 6 + 60 \times 12 + 10 \times 18 = 0 + 360 + 360 + 720 + 180 = 1620\).

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

5. Проверка оптимальности нового плана (метод потенциалов):

Базисные переменные: \((1,3), (2,1), (2,2), (2,3)\).
Пусть \(u_1 = 0\).
* Для \(x_{13} = 30\): \(u_1 + v_3 = c_{13} \Rightarrow 0 + v_3 = 12 \Rightarrow v_3 = 12\).
* Для \(x_{23} = 10\): \(u_2 + v_3 = c_{23} \Rightarrow u_2 + 12 = 18 \Rightarrow u_2 = 6\).
* Для \(x_{21} = 60\): \(u_2 + v_1 = c_{21} \Rightarrow 6 + v_1 = 6 \Rightarrow v_1 = 0\).
* Для \(x_{22} = 60\): \(u_2 + v_2 = c_{22} \Rightarrow 6 + v_2 = 12 \Rightarrow v_2 = 6\).

Потенциалы: \(u_1=0, u_2=6, v_1=0, v_2=6, v_3=12\).

Теперь вычисляем избыточные стоимости для небазисных переменных:
* Ячейка \((a_1, b_1)\): \(\Delta_{11} = c_{11} - (u_1 + v_1) = 5 - (0 + 0) = 5\).
* Ячейка \((a_1, b_2)\): \(\Delta_{12} = c_{12} - (u_1 + v_2) = 7 - (0 + 6) = 7 - 6 = 1\).
* Ячейка \((a_2, b_1)\): \(\Delta_{21}\) - базисная.
* Ячейка \((a_2, b_2)\): \(\Delta_{22}\) - базисная.
* Ячейка \((a_2, b_3)\): \(\Delta_{23}\) - базисная.

Все избыточные стоимости (\(\Delta_{11}=5, \Delta_{12}=1\)) неотрицательны. Следовательно, текущий план оптимален.

Оптимальный план перевозок:
* От \(a_1\) к \(b_3\): 30 единиц.
* От \(a_2\) к \(b_1\): 60 единиц.
* От \(a_2\) к \(b_2\): 60 единиц.
* От \(a_2\) к \(b_3\): 10 единиц.

(Перевозки \(x_{11}\) и \(x_{21}\) равны 0, т.е. эти направления не используются).

Оптимальная стоимость перевозок:
\(C_{min} = 30 \times 12 + 60 \times 6 + 60 \times 12 + 10 \times 18 = 360 + 360 + 720 + 180 = 1620\).