Решение Транспортной Задачи Методами Северо-Западного Угла и Минимального Элемента

Вот решение задачи, оформленное так, чтобы его было удобно переписать в тетрадь школьнику. Задания на семестровую работу. Дана транспортная задача со следующими данными: Таблица 1. Исходные данные транспортной задачи. \[ \begin{array}{|c|c|c|c|c|c|} \hline \text{№} & B_1 & B_2 & B_3 & B_4 & \text{Всего} \\ \hline A_1 & 2 & 1 & 1 & 2 & 25 \\ A_2 & 2 & 5 & 5 & 7 & 25 \\ A_3 & 4 & 5 & 7 & 6 & 26 \\ A_4 & 4 & 6 & 5 & 3 & 21 \\ \hline \text{Всего} & 17 & 22 & 19 & 39 & \\ \hline \end{array} \] Проверим баланс задачи: Сумма запасов: \(25 + 25 + 26 + 21 = 97\) Сумма потребностей: \(17 + 22 + 19 + 39 = 97\) Задача сбалансирована. 1. Найти допустимый план решения транспортной задачи: а) методом северо-западного угла; б) методом минимального элемента. Сравнить полученную стоимость перевозок и выбрать опорный план для дальнейшего решения задачи. а) Метод северо-западного угла. Шаг 1. Заполняем ячейку \((A_1, B_1)\). Запас \(A_1 = 25\), потребность \(B_1 = 17\). Присваиваем \(x_{11} = \min(25, 17) = 17\). Запас \(A_1\) уменьшается до \(25 - 17 = 8\). Потребность \(B_1\) удовлетворена. Шаг 2. Заполняем ячейку \((A_1, B_2)\). Остаток запаса \(A_1 = 8\), потребность \(B_2 = 22\). Присваиваем \(x_{12} = \min(8, 22) = 8\). Запас \(A_1\) исчерпан. Потребность \(B_2\) уменьшается до \(22 - 8 = 14\). Шаг 3. Заполняем ячейку \((A_2, B_2)\). Запас \(A_2 = 25\), остаток потребности \(B_2 = 14\). Присваиваем \(x_{22} = \min(25, 14) = 14\). Запас \(A_2\) уменьшается до \(25 - 14 = 11\). Потребность \(B_2\) удовлетворена. Шаг 4. Заполняем ячейку \((A_2, B_3)\). Остаток запаса \(A_2 = 11\), потребность \(B_3 = 19\). Присваиваем \(x_{23} = \min(11, 19) = 11\). Запас \(A_2\) исчерпан. Потребность \(B_3\) уменьшается до \(19 - 11 = 8\). Шаг 5. Заполняем ячейку \((A_3, B_3)\). Запас \(A_3 = 26\), остаток потребности \(B_3 = 8\). Присваиваем \(x_{33} = \min(26, 8) = 8\). Запас \(A_3\) уменьшается до \(26 - 8 = 18\). Потребность \(B_3\) удовлетворена. Шаг 6. Заполняем ячейку \((A_3, B_4)\). Остаток запаса \(A_3 = 18\), потребность \(B_4 = 39\). Присваиваем \(x_{34} = \min(18, 39) = 18\). Запас \(A_3\) исчерпан. Потребность \(B_4\) уменьшается до \(39 - 18 = 21\). Шаг 7. Заполняем ячейку \((A_4, B_4)\). Запас \(A_4 = 21\), остаток потребности \(B_4 = 21\). Присваиваем \(x_{44} = \min(21, 21) = 21\). Запас \(A_4\) исчерпан. Потребность \(B_4\) удовлетворена. План перевозок методом северо-западного угла: \[ \begin{array}{|c|c|c|c|c|} \hline \text{№} & B_1 & B_2 & B_3 & B_4 \\ \hline A_1 & 17 & 8 & & \\ A_2 & & 14 & 11 & \\ A_3 & & & 8 & 18 \\ A_4 & & & & 21 \\ \hline \end{array} \] Стоимость перевозок \(Z_{СЗУ}\): \(Z_{СЗУ} = 17 \cdot 2 + 8 \cdot 1 + 14 \cdot 5 + 11 \cdot 5 + 8 \cdot 7 + 18 \cdot 6 + 21 \cdot 3\) \(Z_{СЗУ} = 34 + 8 + 70 + 55 + 56 + 108 + 63 = 394\) б) Метод минимального элемента. Шаг 1. Находим минимальный элемент в таблице. Минимальный элемент \(c_{12} = 1\). Запас \(A_1 = 25\), потребность \(B_2 = 22\). Присваиваем \(x_{12} = \min(25, 22) = 22\). Запас \(A_1\) уменьшается до \(25 - 22 = 3\). Потребность \(B_2\) удовлетворена. Столбец \(B_2\) исключается. Шаг 2. Находим следующий минимальный элемент среди оставшихся. Минимальный элемент \(c_{13} = 1\). Остаток запаса \(A_1 = 3\), потребность \(B_3 = 19\). Присваиваем \(x_{13} = \min(3, 19) = 3\). Запас \(A_1\) исчерпан. Строка \(A_1\) исключается. Потребность \(B_3\) уменьшается до \(19 - 3 = 16\). Шаг 3. Находим следующий минимальный элемент. Минимальный элемент \(c_{44} = 3\). Запас \(A_4 = 21\), потребность \(B_4 = 39\). Присваиваем \(x_{44} = \min(21, 39) = 21\). Запас \(A_4\) исчерпан. Строка \(A_4\) исключается. Потребность \(B_4\) уменьшается до \(39 - 21 = 18\). Шаг 4. Находим следующий минимальный элемент. Минимальный элемент \(c_{21} = 2\). Запас \(A_2 = 25\), потребность \(B_1 = 17\). Присваиваем \(x_{21} = \min(25, 17) = 17\). Запас \(A_2\) уменьшается до \(25 - 17 = 8\). Потребность \(B_1\) удовлетворена. Столбец \(B_1\) исключается. Шаг 5. Находим следующий минимальный элемент. Минимальный элемент \(c_{23} = 5\). Остаток запаса \(A_2 = 8\), остаток потребности \(B_3 = 16\). Присваиваем \(x_{23} = \min(8, 16) = 8\). Запас \(A_2\) исчерпан. Строка \(A_2\) исключается. Потребность \(B_3\) уменьшается до \(16 - 8 = 8\). Шаг 6. Находим следующий минимальный элемент. Остался только \(c_{33} = 7\) и \(c_{34} = 6\). Минимальный элемент \(c_{34} = 6\). Запас \(A_3 = 26\), остаток потребности \(B_4 = 18\). Присваиваем \(x_{34} = \min(26, 18) = 18\). Запас \(A_3\) уменьшается до \(26 - 18 = 8\). Потребность \(B_4\) удовлетворена. Столбец \(B_4\) исключается. Шаг 7. Заполняем последнюю ячейку. Остаток запаса \(A_3 = 8\), остаток потребности \(B_3 = 8\). Присваиваем \(x_{33} = \min(8, 8) = 8\). Запас \(A_3\) исчерпан. Потребность \(B_3\) удовлетворена. План перевозок методом минимального элемента: \[ \begin{array}{|c|c|c|c|c|} \hline \text{№} & B_1 & B_2 & B_3 & B_4 \\ \hline A_1 & & 22 & 3 & \\ A_2 & 17 & & 8 & \\ A_3 & & & 8 & 18 \\ A_4 & & & & 21 \\ \hline \end{array} \] Стоимость перевозок \(Z_{МЭ}\): \(Z_{МЭ} = 22 \cdot 1 + 3 \cdot 1 + 17 \cdot 2 + 8 \cdot 5 + 8 \cdot 7 + 18 \cdot 6 + 21 \cdot 3\) \(Z_{МЭ} = 22 + 3 + 34 + 40 + 56 + 108 + 63 = 326\) Сравнение стоимостей: \(Z_{СЗУ} = 394\) \(Z_{МЭ} = 326\) Так как \(Z_{МЭ} < Z_{СЗУ}\), то опорный план, полученный методом минимального элемента, является более выгодным. Его и выбираем для дальнейшего решения задачи. 2. Найти оптимальный план решения транспортной задачи по критерию стоимости методом потенциалов. Ход решения необходимо пояснить. Используем опорный план, полученный методом минимального элемента: \[ \begin{array}{|c|c|c|c|c|} \hline \text{№} & B_1 & B_2 & B_3 & B_4 \\ \hline A_1 & & 22 & 3 & \\ A_2 & 17 & & 8 & \\ A_3 & & & 8 & 18 \\ A_4 & & & & 21 \\ \hline \end{array} \] Количество базисных клеток (заполненных) равно \(m+n-1 = 4+4-1 = 7\). В нашем плане 7 заполненных клеток, значит, план невырожденный. Метод потенциалов: Для каждой базисной клетки \((i, j)\) должно выполняться условие \(c_{ij} = u_i + v_j\). Для свободных клеток \((i, j)\) вычисляем оценки \(\Delta_{ij} = c_{ij} - (u_i + v_j)\). Если все \(\Delta_{ij} \ge 0\), то план оптимален. Если есть отрицательные оценки, то план можно улучшить. Присвоим \(u_1 = 0\). Из базисных клеток: 1. \((A_1, B_2)\): \(c_{12} = 1\). \(u_1 + v_2 = 1 \Rightarrow 0 + v_2 = 1 \Rightarrow v_2 = 1\). 2. \((A_1, B_3)\): \(c_{13} = 1\). \(u_1 + v_3 = 1 \Rightarrow 0 + v_3 = 1 \Rightarrow v_3 = 1\). 3. \((A_2, B_1)\): \(c_{21} = 2\). \(u_2 + v_1 = 2\). 4. \((A_2, B_3)\): \(c_{23} = 5\). \(u_2 + v_3 = 5 \Rightarrow u_2 + 1 = 5 \Rightarrow u_2 = 4\). 5. \((A_3, B_3)\): \(c_{33} = 7\). \(u_3 + v_3 = 7 \Rightarrow u_3 + 1 = 7 \Rightarrow u_3 = 6\). 6. \((A_3, B_4)\): \(c_{34} = 6\). \(u_3 + v_4 = 6 \Rightarrow 6 + v_4 = 6 \Rightarrow v_4 = 0\). 7. \((A_4, B_4)\): \(c_{44} = 3\). \(u_4 + v_4 = 3 \Rightarrow u_4 + 0 = 3 \Rightarrow u_4 = 3\). Теперь найдем \(v_1\): Из \((A_2, B_1)\): \(u_2 + v_1 = 2 \Rightarrow 4 + v_1 = 2 \Rightarrow v_1 = -2\). Потенциалы: \(u_1 = 0, u_2 = 4, u_3 = 6, u_4 = 3\) \(v_1 = -2, v_2 = 1, v_3 = 1, v_4 = 0\) Вычислим оценки для свободных клеток \(\Delta_{ij} = c_{ij} - (u_i + v_j)\): \(\Delta_{11} = c_{11} - (u_1 + v_1) = 2 - (0 + (-2)) = 2 - (-2) = 4\) \(\Delta_{14} = c_{14} - (u_1 + v_4) = 2 - (0 + 0) = 2\) \(\Delta_{22} = c_{22} - (u_2 + v_2) = 5 - (4 + 1) = 5 - 5 = 0\) \(\Delta_{24} = c_{24} - (u_2 + v_4) = 7 - (4 + 0) = 7 - 4 = 3\) \(\Delta_{31} = c_{31} - (u_3 + v_1) = 4 - (6 + (-2)) = 4 - 4 = 0\) \(\Delta_{32} = c_{32} - (u_3 + v_2) = 5 - (6 + 1) = 5 - 7 = -2\) \(\Delta_{41} = c_{41} - (u_4 + v_1) = 4 - (3 + (-2)) = 4 - 1 = 3\) \(\Delta_{42} = c_{42} - (u_4 + v_2) = 6 - (3 + 1) = 6 - 4 = 2\) \(\Delta_{43} = c_{43} - (u_4 + v_3) = 5 - (3 + 1) = 5 - 4 = 1\) Есть отрицательная оценка: \(\Delta_{32} = -2\). Это означает, что текущий план не является оптимальным, и его можно улучшить. Вводим в базис клетку \((A_3, B_2)\). Строим цикл пересчета для клетки \((A_3, B_2)\). Начинаем с \((A_3, B_2)\) и двигаемся по базисным клеткам. Цикл: \((A_3, B_2) \rightarrow (A_3, B_3) \rightarrow (A_1, B_3) \rightarrow (A_1,