Задание на семестровую работу
1. Найти допустимый план решения транспортной задачи:
Дана следующая таблица с тарифами и объемами:
| №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 \]Задача сбалансирована, так как сумма предложения равна сумме спроса.
а) методом северо-западного угла;
Заполняем ячейки, начиная с левого верхнего угла (северо-западного), пока не исчерпаем запасы или потребности.
Шаг 1: Ячейка (A1, B1). Предложение A1 = 25, Спрос B1 = 17. Отгружаем 17. Остаток A1 = 25 - 17 = 8. Спрос B1 = 0.
Шаг 2: Ячейка (A1, B2). Предложение A1 = 8, Спрос B2 = 22. Отгружаем 8. Остаток A1 = 0. Спрос B2 = 22 - 8 = 14.
Шаг 3: Ячейка (A2, B2). Предложение A2 = 25, Спрос B2 = 14. Отгружаем 14. Остаток A2 = 25 - 14 = 11. Спрос B2 = 0.
Шаг 4: Ячейка (A2, B3). Предложение A2 = 11, Спрос B3 = 19. Отгружаем 11. Остаток A2 = 0. Спрос B3 = 19 - 11 = 8.
Шаг 5: Ячейка (A3, B3). Предложение A3 = 26, Спрос B3 = 8. Отгружаем 8. Остаток A3 = 26 - 8 = 18. Спрос B3 = 0.
Шаг 6: Ячейка (A3, B4). Предложение A3 = 18, Спрос B4 = 39. Отгружаем 18. Остаток A3 = 0. Спрос B4 = 39 - 18 = 21.
Шаг 7: Ячейка (A4, B4). Предложение A4 = 21, Спрос B4 = 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 |
Общая стоимость перевозок методом северо-западного угла:
\[ 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 \]б) методом минимального элемента;
Заполняем ячейки, начиная с ячейки с минимальной стоимостью, пока не исчерпаем запасы или потребности.
Исходная таблица тарифов:
| 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 = 25, Спрос B2 = 22. Отгружаем 22. Остаток A1 = 25 - 22 = 3. Спрос B2 = 0. Столбец B2 вычеркиваем.
Шаг 2: Следующий минимальный тариф = 1 (в ячейке (A1, B3)). Предложение A1 = 3, Спрос B3 = 19. Отгружаем 3. Остаток A1 = 0. Спрос B3 = 19 - 3 = 16. Строка A1 вычеркивается.
Шаг 3: Следующий минимальный тариф = 2 (в ячейках (A1, B1) - вычеркнута, (A1, B4) - вычеркнута, (A2, B1)). Выберем (A2, B1). Предложение A2 = 25, Спрос B1 = 17. Отгружаем 17. Остаток A2 = 25 - 17 = 8. Спрос B1 = 0. Столбец B1 вычеркиваем.
Шаг 4: Следующий минимальный тариф = 3 (в ячейке (A4, B4)). Предложение A4 = 21, Спрос B4 = 39. Отгружаем 21. Остаток A4 = 0. Спрос B4 = 39 - 21 = 18. Строка A4 вычеркивается.
Шаг 5: Следующий минимальный тариф = 5 (в ячейках (A2, B3), (A3, B3)). Выберем (A2, B3). Предложение A2 = 8, Спрос B3 = 16. Отгружаем 8. Остаток A2 = 0. Спрос B3 = 16 - 8 = 8. Строка A2 вычеркивается.
Шаг 6: Осталась одна ячейка (A3, B4) и (A3, B3). Ячейка (A3, B3). Предложение A3 = 26, Спрос B3 = 8. Отгружаем 8. Остаток A3 = 26 - 8 = 18. Спрос B3 = 0.
Шаг 7: Ячейка (A3, B4). Предложение A3 = 18, Спрос B4 = 18. Отгружаем 18. Остаток A3 = 0. Спрос B4 = 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 |
Общая стоимость перевозок методом минимального элемента:
\[ 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\)
Метод минимального элемента дал меньшую стоимость перевозок, поэтому выбираем план, полученный методом минимального элемента, в качестве опорного для дальнейшего решения задачи.
Опорный план:
| 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 |
2. Найти оптимальный план решения транспортной задачи по критерию стоимости методом потенциалов.
Ход решения необходимо пояснить.
Используем опорный план, полученный методом минимального элемента. Количество занятых ячеек (базисных переменных) равно \(m + n - 1 = 4 + 4 - 1 = 7\). В нашем плане 7 занятых ячеек, что соответствует условию невырожденности.
Опорный план:
| 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_{ij}\) для занятых ячеек:
\(c_{12} = 1\)
\(c_{13} = 1\)
\(c_{21} = 2\)
\(c_{23} = 5\)
\(c_{33} = 7\)
\(c_{34} = 6\)
\(c_{44} = 3\)
Метод потенциалов заключается в нахождении потенциалов \(u_i\) для строк и \(v_j\) для столбцов, используя равенство \(u_i + v_j = c_{ij}\) для занятых ячеек. Примем \(u_1 = 0\).
1. \(u_1 + v_2 = c_{12} \Rightarrow 0 + v_2 = 1 \Rightarrow v_2 = 1\)
2. \(u_1 + v_3 = c_{13} \Rightarrow 0 + v_3 = 1 \Rightarrow v_3 = 1\)
3. \(u_2 + v_3 = c_{23} \Rightarrow u_2 + 1 = 5 \Rightarrow u_2 = 4\)
4. \(u_2 + v_1 = c_{21} \Rightarrow 4 + v_1 = 2 \Rightarrow v_1 = -2\)
5. \(u_3 + v_3 = c_{33} \Rightarrow u_3 + 1 = 7 \Rightarrow u_3 = 6\)
6. \(u_3 + v_4 = c_{34} \Rightarrow 6 + v_4 = 6 \Rightarrow v_4 = 0\)
7. \(u_4 + v_4 = c_{44} \Rightarrow u_4 + 0 = 3 \Rightarrow u_4 = 3\)
Потенциалы:
\(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} - (