Задание на семестровую работу
1. Найти допустимый план решения транспортной задачи:
а) методом северо-западного угла;
б) методом минимального элемента;
Сравнить полученную стоимость перевозок и выбрать опорный план для дальнейшего решения задачи.
2. Найти оптимальный план решения транспортной задачи по критерию стоимости методом потенциалов.
Ход решения необходимо пояснять.
Исходные данные представлены в таблице:
| №2 | B1 | B2 | B3 | B4 | Всего (запасы) |
| A1 | 2 | 1 | 1 | 2 | 25 |
| A2 | 2 | 5 | 5 | 7 | 25 |
| A3 | 4 | 5 | 7 | 6 | 26 |
| A4 | 4 | 6 | 5 | 3 | 21 |
| Всего (потребности) | 17 | 22 | 19 | 39 |
Сначала проверим баланс транспортной задачи. Сумма запасов должна быть равна сумме потребностей.
Сумма запасов: \(25 + 25 + 26 + 21 = 97\)
Сумма потребностей: \(17 + 22 + 19 + 39 = 97\)
Задача сбалансирована, так как сумма запасов равна сумме потребностей (\(97 = 97\)).
1. Найти допустимый план решения транспортной задачи:
а) Методом северо-западного угла
Суть метода заключается в том, что заполнение таблицы начинается с левого верхнего угла (северо-западного) и продолжается до тех пор, пока не будут исчерпаны все запасы и удовлетворены все потребности.
Исходная матрица стоимостей (тарифы на перевозку):
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 2 | 1 | 1 | 2 | 25 |
| A2 | 2 | 5 | 5 | 7 | 25 |
| A3 | 4 | 5 | 7 | 6 | 26 |
| A4 | 4 | 6 | 5 | 3 | 21 |
| Потребности | 17 | 22 | 19 | 39 |
Шаг 1: Ячейка (A1, B1). Запас A1 = 25, Потребность B1 = 17. Отгружаем \(x_{11} = \min(25, 17) = 17\). Запас A1 становится \(25 - 17 = 8\). Потребность B1 удовлетворена (0). Столбец B1 вычеркиваем.
Шаг 2: Ячейка (A1, B2). Запас A1 = 8, Потребность B2 = 22. Отгружаем \(x_{12} = \min(8, 22) = 8\). Запас A1 исчерпан (0). Потребность B2 становится \(22 - 8 = 14\). Строка A1 вычеркиваем.
Шаг 3: Ячейка (A2, B2). Запас A2 = 25, Потребность B2 = 14. Отгружаем \(x_{22} = \min(25, 14) = 14\). Запас A2 становится \(25 - 14 = 11\). Потребность B2 удовлетворена (0). Столбец B2 вычеркиваем.
Шаг 4: Ячейка (A2, B3). Запас A2 = 11, Потребность B3 = 19. Отгружаем \(x_{23} = \min(11, 19) = 11\). Запас A2 исчерпан (0). Потребность B3 становится \(19 - 11 = 8\). Строка A2 вычеркиваем.
Шаг 5: Ячейка (A3, B3). Запас A3 = 26, Потребность B3 = 8. Отгружаем \(x_{33} = \min(26, 8) = 8\). Запас A3 становится \(26 - 8 = 18\). Потребность B3 удовлетворена (0). Столбец B3 вычеркиваем.
Шаг 6: Ячейка (A3, B4). Запас A3 = 18, Потребность B4 = 39. Отгружаем \(x_{34} = \min(18, 39) = 18\). Запас A3 исчерпан (0). Потребность B4 становится \(39 - 18 = 21\). Строка A3 вычеркиваем.
Шаг 7: Ячейка (A4, B4). Запас A4 = 21, Потребность B4 = 21. Отгружаем \(x_{44} = \min(21, 21) = 21\). Запас A4 исчерпан (0). Потребность B4 удовлетворена (0).
Полученный допустимый план методом северо-западного угла:
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 17 (2) | 8 (1) | 25 | ||
| A2 | 14 (5) | 11 (5) | 25 | ||
| A3 | 8 (7) | 18 (6) | 26 | ||
| A4 | 21 (3) | 21 | |||
| Потребности | 17 | 22 | 19 | 39 |
В скобках указаны тарифы.
Рассчитаем общую стоимость перевозок для этого плана:
\[ C_{СЗУ} = 17 \cdot 2 + 8 \cdot 1 + 14 \cdot 5 + 11 \cdot 5 + 8 \cdot 7 + 18 \cdot 6 + 21 \cdot 3 \] \[ C_{СЗУ} = 34 + 8 + 70 + 55 + 56 + 108 + 63 = 394 \]Общая стоимость перевозок методом северо-западного угла составляет 394.
Количество базисных клеток (заполненных) равно \(m + n - 1 = 4 + 4 - 1 = 7\). У нас 7 заполненных клеток, значит, план невырожденный.
б) Методом минимального элемента
Суть метода заключается в том, что на каждом шаге выбирается ячейка с минимальной стоимостью перевозки, и в нее отгружается максимально возможное количество товара.
Исходная матрица стоимостей:
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 2 | 1 | 1 | 2 | 25 |
| A2 | 2 | 5 | 5 | 7 | 25 |
| A3 | 4 | 5 | 7 | 6 | 26 |
| A4 | 4 | 6 | 5 | 3 | 21 |
| Потребности | 17 | 22 | 19 | 39 |
Шаг 1: Находим минимальный тариф. Это 1 в ячейках (A1, B2) и (A1, B3). Выберем (A1, B2).
Ячейка (A1, B2). Тариф = 1. Запас A1 = 25, Потребность B2 = 22. Отгружаем \(x_{12} = \min(25, 22) = 22\). Запас A1 становится \(25 - 22 = 3\). Потребность B2 удовлетворена (0). Столбец B2 вычеркиваем.
Шаг 2: Следующий минимальный тариф в оставшихся ячейках. Это 1 в ячейке (A1, B3).
Ячейка (A1, B3). Тариф = 1. Запас A1 = 3, Потребность B3 = 19. Отгружаем \(x_{13} = \min(3, 19) = 3\). Запас A1 исчерпан (0). Потребность B3 становится \(19 - 3 = 16\). Строка A1 вычеркиваем.
Шаг 3: Следующий минимальный тариф. Это 2 в ячейке (A2, B1).
Ячейка (A2, B1). Тариф = 2. Запас A2 = 25, Потребность B1 = 17. Отгружаем \(x_{21} = \min(25, 17) = 17\). Запас A2 становится \(25 - 17 = 8\). Потребность B1 удовлетворена (0). Столбец B1 вычеркиваем.
Шаг 4: Следующий минимальный тариф. Это 3 в ячейке (A4, B4).
Ячейка (A4, B4). Тариф = 3. Запас A4 = 21, Потребность B4 = 39. Отгружаем \(x_{44} = \min(21, 39) = 21\). Запас A4 исчерпан (0). Потребность B4 становится \(39 - 21 = 18\). Строка A4 вычеркиваем.
Шаг 5: Следующий минимальный тариф. Это 5 в ячейке (A2, B3) (или (A3, B2), но B2 уже вычеркнут).
Ячейка (A2, B3). Тариф = 5. Запас A2 = 8, Потребность B3 = 16. Отгружаем \(x_{23} = \min(8, 16) = 8\). Запас A2 исчерпан (0). Потребность B3 становится \(16 - 8 = 8\). Строка A2 вычеркиваем.
Шаг 6: Осталась одна строка A3 и два столбца B3, B4. Минимальный тариф в оставшихся ячейках - 6 в (A3, B4).
Ячейка (A3, B4). Тариф = 6. Запас A3 = 26, Потребность B4 = 18. Отгружаем \(x_{34} = \min(26, 18) = 18\). Запас A3 становится \(26 - 18 = 8\). Потребность B4 удовлетворена (0). Столбец B4 вычеркиваем.
Шаг 7: Осталась одна ячейка (A3, B3).
Ячейка (A3, B3). Тариф = 7. Запас A3 = 8, Потребность B3 = 8. Отгружаем \(x_{33} = \min(8, 8) = 8\). Запас A3 исчерпан (0). Потребность B3 удовлетворена (0).
Полученный допустимый план методом минимального элемента:
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 22 (1) | 3 (1) | 25 | ||
| A2 | 17 (2) | 8 (5) | 25 | ||
| A3 | 8 (7) | 18 (6) | 26 | ||
| A4 | 21 (3) | 21 | |||
| Потребности | 17 | 22 | 19 | 39 |
В скобках указаны тарифы.
Рассчитаем общую стоимость перевозок для этого плана:
\[ C_{МЭ} = 22 \cdot 1 + 3 \cdot 1 + 17 \cdot 2 + 8 \cdot 5 + 8 \cdot 7 + 18 \cdot 6 + 21 \cdot 3 \] \[ C_{МЭ} = 22 + 3 + 34 + 40 + 56 + 108 + 63 = 326 \]Общая стоимость перевозок методом минимального элемента составляет 326.
Количество базисных клеток (заполненных) равно \(m + n - 1 = 4 + 4 - 1 = 7\). У нас 7 заполненных клеток, значит, план невырожденный.
Сравнение полученной стоимости перевозок и выбор опорного плана:
Стоимость методом северо-западного угла: \(C_{СЗУ} = 394\)
Стоимость методом минимального элемента: \(C_{МЭ} = 326\)
Метод минимального элемента дал меньшую стоимость перевозок (\(326 < 394\)). Поэтому выбираем план, полученный методом минимального элемента, в качестве опорного для дальнейшего решения задачи.
Опорный план (полученный методом минимального элемента):