Решай задачу 14 с 4 способом
Опорные планы найти
1)северо-западного угла
2) минимальной стоимости
3) двойного предпочтения
4) ФогеляРешай
Нажмите для увеличения
lightbulb
Краткий ответ
Представлено подробное решение задачи 14 транспортной задачи методом Фогеля. Найден опорный план, необходимый для дальнейшей оптимизации транспортных издержек.
check_circle
Подробное решение
Хорошо, давайте решим задачу 14, используя метод Фогеля для нахождения опорного плана.
Задача 14 представляет собой транспортную задачу. У нас есть:
* Три поставщика (или пункта отправления) с запасами \(a_1 = 250\), \(a_2 = 190\), \(a_3 = 200\).
* Пять потребителей (или пунктов назначения) с потребностями \(b_1 = 180\), \(b_2 = 100\), \(b_3 = 130\), \(b_4 = 140\), \(b_5 = 90\).
* Матрица стоимостей перевозок \(C\):
\[
C =
\begin{pmatrix}
8 & 2 & 5 & 3 & 4 \\
3 & 7 & 9 & 5 & 6 \\
2 & 9 & 6 & 5 & 4
\end{pmatrix}
\]
Прежде чем начать, проверим баланс задачи:
Сумма запасов: \( \sum a_i = 250 + 190 + 200 = 640 \)
Сумма потребностей: \( \sum b_j = 180 + 100 + 130 + 140 + 90 = 640 \)
Задача сбалансирована, так как \( \sum a_i = \sum b_j \).
Теперь приступим к нахождению опорного плана методом Фогеля.
Метод Фогеля
Метод Фогеля основан на расчете "штрафов" для каждой строки и столбца. Штраф для строки (или столбца) - это разница между двумя наименьшими стоимостями в этой строке (или столбце). Мы выбираем строку или столбец с наибольшим штрафом и в ячейку с минимальной стоимостью в этой строке (или столбце) назначаем максимально возможное количество груза.
Шаг 1: Начальная таблица и расчет штрафов
Запишем исходную транспортную таблицу с запасами, потребностями и стоимостями.
B1 (180)
B2 (100)
B3 (130)
B4 (140)
B5 (90)
Запасы \(a_i\)
Штраф по строке
A1
8
2
5
3
4
250
A2
3
7
9
5
6
190
A3
2
9
6
5
4
200
Потребности \(b_j\)
180
100
130
140
90
Штраф по столбцу
Рассчитаем штрафы:
* Штрафы по строкам:
* A1: \(2, 3, 4, 5, 8\). Два наименьших: 2 и 3. Штраф: \(3 - 2 = 1\).
* A2: \(3, 5, 6, 7, 9\). Два наименьших: 3 и 5. Штраф: \(5 - 3 = 2\).
* A3: \(2, 4, 5, 6, 9\). Два наименьших: 2 и 4. Штраф: \(4 - 2 = 2\).
* Штрафы по столбцам:
* B1: \(2, 3, 8\). Два наименьших: 2 и 3. Штраф: \(3 - 2 = 1\).
* B2: \(2, 7, 9\). Два наименьших: 2 и 7. Штраф: \(7 - 2 = 5\).
* B3: \(5, 6, 9\). Два наименьших: 5 и 6. Штраф: \(6 - 5 = 1\).
* B4: \(3, 5, 5\). Два наименьших: 3 и 5. Штраф: \(5 - 3 = 2\).
* B5: \(4, 4, 6\). Два наименьших: 4 и 4. Штраф: \(4 - 4 = 0\).
Обновим таблицу:
B1 (180)
B2 (100)
B3 (130)
B4 (140)
B5 (90)
Запасы \(a_i\)
Штраф по строке
A1
8
2
5
3
4
250
1
A2
3
7
9
5
6
190
2
A3
2
9
6
5
4
200
2
Потребности \(b_j\)
180
100
130
140
90
Штраф по столбцу
1
5
1
2
0
Шаг 2: Выбор ячейки и распределение груза
Наибольший штраф равен 5 (столбец B2). В столбце B2 наименьшая стоимость - 2 (ячейка A1-B2).
Назначим в ячейку A1-B2 максимально возможное количество груза.
Запас A1 = 250, Потребность B2 = 100.
Отправляем 100 единиц груза из A1 в B2.
* Потребность B2 удовлетворена (100 - 100 = 0). Столбец B2 вычеркиваем.
* Запас A1 уменьшается (250 - 100 = 150).
Обновим таблицу:
B1 (180)
B2 (0)
B3 (130)
B4 (140)
B5 (90)
Запасы \(a_i\)
Штраф по строке
A1
8
2 (100)
5
3
4
150
A2
3
7
9
5
6
190
A3
2
9
6
5
4
200
Потребности \(b_j\)
180
0
130
140
90
Штраф по столбцу
-
Шаг 3: Пересчет штрафов
* Штрафы по строкам:
* A1: \(3, 4, 5, 8\). Два наименьших: 3 и 4. Штраф: \(4 - 3 = 1\).
* A2: \(3, 5, 6, 9\). Два наименьших: 3 и 5. Штраф: \(5 - 3 = 2\).
* A3: \(2, 4, 5, 6\). Два наименьших: 2 и 4. Штраф: \(4 - 2 = 2\).
* Штрафы по столбцам:
* B1: \(2, 3, 8\). Два наименьших: 2 и 3. Штраф: \(3 - 2 = 1\).
* B3: \(5, 6, 9\). Два наименьших: 5 и 6. Штраф: \(6 - 5 = 1\).
* B4: \(3, 5, 5\). Два наименьших: 3 и 5. Штраф: \(5 - 3 = 2\).
* B5: \(4, 4, 6\). Два наименьших: 4 и 4. Штраф: \(4 - 4 = 0\).
Обновим таблицу:
B1 (180)
B2 (0)
B3 (130)
B4 (140)
B5 (90)
Запасы \(a_i\)
Штраф по строке
A1
8
2 (100)
5
3
4
150
1
A2
3
7
9
5
6
190
2
A3
2
9
6
5
4
200
2
Потребности \(b_j\)
180
0
130
140
90
Штраф по столбцу
1
-
1
2
0
Шаг 4: Выбор ячейки и распределение груза (повтор)
Наибольший штраф равен 2. Таких штрафов несколько: A2, A3, B4. Выберем, например, строку A2.
В строке A2 наименьшая стоимость - 3 (ячейка A2-B1).
Назначим в ячейку A2-B1 максимально возможное количество груза.
Запас A2 = 190, Потребность B1 = 180.
Отправляем 180 единиц груза из A2 в B1.
* Потребность B1 удовлетворена (180 - 180 = 0). Столбец B1 вычеркиваем.
* Запас A2 уменьшается (190 - 180 = 10).
Обновим таблицу:
B1 (0)
B2 (0)
B3 (130)
B4 (140)
B5 (90)
Запасы \(a_i\)
Штраф по строке
A1
8
2 (100)
5
3
4
150
A2
3 (180)
7
9
5
6
10
A3
2
9
6
5
4
200
Потребности \(b_j\)
0
0
130
140
90
Штраф по столбцу
-
-
Шаг 5: Пересчет штрафов
* Штрафы по строкам:
* A1: \(3, 4, 5\). Два наименьших: 3 и 4. Штраф: \(4 - 3 = 1\).
* A2: \(5, 6, 9\). Два наименьших: 5 и 6. Штраф: \(6 - 5 = 1\).
* A3: \(4, 5, 6\). Два наименьших: 4 и 5. Штраф: \(5 - 4 = 1\).
* Штрафы по столбцам:
* B3: \(5, 6, 9\). Два наименьших: 5 и 6. Штраф: \(6 - 5 = 1\).
* B4: \(3, 5, 5\). Два наименьших: 3 и 5. Штраф: \(5 - 3 = 2\).
* B5: \(4, 4, 6\). Два наименьших: 4 и 4. Штраф: \(4 - 4 = 0\).
Обновим таблицу:
