метод фогеля
.rtf
Транспортная задача.
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
12 |
13 |
4 |
14 |
8 |
145 |
|
2 |
9 |
8 |
11 |
16 |
7 |
165 |
|
3 |
14 |
8 |
12 |
6 |
7 |
200 |
|
4 |
5 |
7 |
12 |
6 |
9 |
385 |
|
5 |
15 |
12 |
5 |
13 |
11 |
300 |
|
Потребности |
145 |
155 |
182 |
193 |
520 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 145 + 165 + 200 + 385 + 300 = 1195
∑b = 145 + 155 + 182 + 193 + 520 = 1195
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
12 |
13 |
4 |
14 |
8 |
145 |
|
2 |
9 |
8 |
11 |
16 |
7 |
165 |
|
3 |
14 |
8 |
12 |
6 |
7 |
200 |
|
4 |
5 |
7 |
12 |
6 |
9 |
385 |
|
5 |
15 |
12 |
5 |
13 |
11 |
300 |
|
Потребности |
145 |
155 |
182 |
193 |
520 |
|
Этап I. Поиск первого опорного плана.
Находим разности по строкам.
Для строки N=1 первый минимальный элемент min11 = 4, второй минимальный элемент min21 = 8. Их разность равна d = min21 - min11 = 4.
Для строки N=2 первый минимальный элемент min12 = 7, второй минимальный элемент min22 = 8. Их разность равна d = min22 - min12 = 1.
Для строки N=3 первый минимальный элемент min13 = 6, второй минимальный элемент min23 = 7. Их разность равна d = min23 - min13 = 1.
Для строки N=4 первый минимальный элемент min14 = 5, второй минимальный элемент min24 = 6. Их разность равна d = min24 - min14 = 1.
Для строки N=5 первый минимальный элемент min15 = 5, второй минимальный элемент min25 = 11. Их разность равна d = min25 - min15 = 6.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min11 = 5. второй минимальный элемент min21 9. Их разность d = min21 - min11 = 4.
Для столбца N=2 первый минимальный элемент min12 = 7. второй минимальный элемент min22 8. Их разность d = min22 - min12 = 1.
Для столбца N=3 первый минимальный элемент min13 = 4. второй минимальный элемент min23 5. Их разность d = min23 - min13 = 1.
Для столбца N=4 первый минимальный элемент min14 = 6. второй минимальный элемент min24 6. Их разность d = min24 - min14 = 0.
Для столбца N=5 первый минимальный элемент min15 = 7. второй минимальный элемент min25 7. Их разность d = min25 - min15 = 0.
Вычислив все разности, видим, что наибольшая из них соответствует строке (5). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (5) и столбца (3).
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
Разности по строкам |
|
1 |
12 |
13 |
4 |
14 |
8 |
145 |
4 |
|
2 |
9 |
8 |
11 |
16 |
7 |
165 |
1 |
|
3 |
14 |
8 |
12 |
6 |
7 |
200 |
1 |
|
4 |
5 |
7 |
12 |
6 |
9 |
385 |
1 |
|
5 |
15 |
12 |
5 |
13 |
11 |
300 |
6 |
|
Потребности |
145 |
155 |
182 |
193 |
520 |
0 |
0 |
|
Разности по столбцам |
4 |
1 |
1 |
0 |
0 |
0 |
|
Искомый элемент равен 5
Для этого элемента запасы равны 300, потребности 182. Поскольку минимальным является 182, то вычитаем его.
x53 = min(300,182) = 182.
|
0 |
0 |
x |
0 |
0 |
0 |
|
0 |
0 |
x |
x |
0 |
0 |
|
0 |
0 |
x |
x |
0 |
0 |
|
0 |
0 |
x |
x |
0 |
0 |
|
0 |
0 |
0 |
x |
0 |
300 - 182 = 118 |
|
0 |
x |
182 - 182 = 0 |
x |
x |
x |
Находим разности по строкам.
Для строки N=1 первый минимальный элемент min11 = 8, второй минимальный элемент min21 = 12. Их разность равна d = min21 - min11 = 4.
Для строки N=2 первый минимальный элемент min12 = 7, второй минимальный элемент min22 = 8. Их разность равна d = min22 - min12 = 1.
Для строки N=3 первый минимальный элемент min13 = 6, второй минимальный элемент min23 = 7. Их разность равна d = min23 - min13 = 1.
Для строки N=4 первый минимальный элемент min14 = 5, второй минимальный элемент min24 = 6. Их разность равна d = min24 - min14 = 1.
Для строки N=5 первый минимальный элемент min15 = 11, второй минимальный элемент min25 = 12. Их разность равна d = min25 - min15 = 1.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min11 = 5. второй минимальный элемент min21 9. Их разность d = min21 - min11 = 4.
Для столбца N=2 первый минимальный элемент min12 = 7. второй минимальный элемент min22 8. Их разность d = min22 - min12 = 1.
Для столбца N=4 первый минимальный элемент min14 = 6. второй минимальный элемент min24 6. Их разность d = min24 - min14 = 0.
Для столбца N=5 первый минимальный элемент min15 = 7. второй минимальный элемент min25 7. Их разность d = min25 - min15 = 0.
Вычислив все разности, видим, что наибольшая из них соответствует строке (1). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (5).
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
Разности по строкам |
|
1 |
12 |
13 |
4 |
14 |
8 |
145 |
4 |
|
2 |
9 |
8 |
11 |
16 |
7 |
165 |
1 |
|
3 |
14 |
8 |
12 |
6 |
7 |
200 |
1 |
|
4 |
5 |
7 |
12 |
6 |
9 |
385 |
1 |
|
5 |
15 |
12 |
5 |
13 |
11 |
118 |
1 |
|
Потребности |
145 |
155 |
0 |
193 |
520 |
0 |
0 |
|
Разности по столбцам |
4 |
1 |
- |
0 |
0 |
0 |
|
Искомый элемент равен 8
Для этого элемента запасы равны 145, потребности 520. Поскольку минимальным является 145, то вычитаем его.
x15 = min(145,520) = 145.
|
x |
x |
0 |
x |
0 |
145 - 145 = 0 |
|
0 |
x |
x |
x |
x |
x |
|
0 |
0 |
0 |
0 |
0 |
x |
|
0 |
0 |
0 |
0 |
0 |
x |
|
0 |
0 |
0 |
0 |
0 |
x |
|
0 |
0 |
0 |
0 |
520 - 145 = 375 |
x |
Находим разности по строкам.
Для строки N=2 первый минимальный элемент min12 = 7, второй минимальный элемент min22 = 8. Их разность равна d = min22 - min12 = 1.
Для строки N=3 первый минимальный элемент min13 = 6, второй минимальный элемент min23 = 7. Их разность равна d = min23 - min13 = 1.
Для строки N=4 первый минимальный элемент min14 = 5, второй минимальный элемент min24 = 6. Их разность равна d = min24 - min14 = 1.
Для строки N=5 первый минимальный элемент min15 = 11, второй минимальный элемент min25 = 12. Их разность равна d = min25 - min15 = 1.
Находим разности по столбцам.
Для столбца N=1 первый минимальный элемент min11 = 5. второй минимальный элемент min21 9. Их разность d = min21 - min11 = 4.
Для столбца N=2 первый минимальный элемент min12 = 7. второй минимальный элемент min22 8. Их разность d = min22 - min12 = 1.
Для столбца N=4 первый минимальный элемент min14 = 6. второй минимальный элемент min24 6. Их разность d = min24 - min14 = 0.
Для столбца N=5 первый минимальный элемент min15 = 7. второй минимальный элемент min25 7. Их разность d = min25 - min15 = 0.
Вычислив все разности, видим, что наибольшая из них соответствует столбцу (1). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (1).
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
Разности по строкам |
|
1 |
12 |
13 |
4 |
14 |
8 |
0 |
- |
|
2 |
9 |
8 |
11 |
16 |
7 |
165 |
1 |
|
3 |
14 |
8 |
12 |
6 |
7 |
200 |
1 |
|
4 |
5 |
7 |
12 |
6 |
9 |
385 |
1 |
|
5 |
15 |
12 |
5 |
13 |
11 |
118 |
1 |
|
Потребности |
145 |
155 |
0 |
193 |
375 |
0 |
0 |
|
Разности по столбцам |
4 |
1 |
- |
0 |
0 |
0 |
|
Искомый элемент равен 5
Для этого элемента запасы равны 385, потребности 145. Поскольку минимальным является 145, то вычитаем его.
x41 = min(385,145) = 145.
|
0 |
0 |
0 |
0 |
0 |
0 |
|
x |
x |
0 |
0 |
0 |
0 |
|
x |
x |
0 |
0 |
0 |
0 |
|
0 |
x |
0 |
0 |
0 |
385 - 145 = 240 |
|
x |
x |
x |
x |
x |
x |
|
145 - 145 = 0 |
x |
0 |
0 |
0 |
0 |
Находим разности по строкам.
Для строки N=2 первый минимальный элемент min12 = 7, второй минимальный элемент min22 = 8. Их разность равна d = min22 - min12 = 1.
Для строки N=3 первый минимальный элемент min13 = 6, второй минимальный элемент min23 = 7. Их разность равна d = min23 - min13 = 1.
Для строки N=4 первый минимальный элемент min14 = 6, второй минимальный элемент min24 = 7. Их разность равна d = min24 - min14 = 1.
Для строки N=5 первый минимальный элемент min15 = 11, второй минимальный элемент min25 = 12. Их разность равна d = min25 - min15 = 1.
Находим разности по столбцам.
Для столбца N=2 первый минимальный элемент min12 = 7. второй минимальный элемент min22 8. Их разность d = min22 - min12 = 1.
Для столбца N=4 первый минимальный элемент min14 = 6. второй минимальный элемент min24 6. Их разность d = min24 - min14 = 0.
Для столбца N=5 первый минимальный элемент min15 = 7. второй минимальный элемент min25 7. Их разность d = min25 - min15 = 0.
Вычислив все разности, видим, что наибольшая из них соответствует строке (5). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (5) и столбца (5).
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
Разности по строкам |
|
1 |
12 |
13 |
4 |
14 |
8 |
0 |
- |
|
2 |
9 |
8 |
11 |
16 |
7 |
165 |
1 |
|
3 |
14 |
8 |
12 |
6 |
7 |
200 |
1 |
|
4 |
5 |
7 |
12 |
6 |
9 |
240 |
1 |
|
5 |
15 |
12 |
5 |
13 |
11 |
118 |
1 |
|
Потребности |
0 |
155 |
0 |
193 |
375 |
0 |
0 |
|
Разности по столбцам |
- |
1 |
- |
0 |
0 |
0 |
|
Искомый элемент равен 11
Для этого элемента запасы равны 118, потребности 375. Поскольку минимальным является 118, то вычитаем его.
x55 = min(118,375) = 118.
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
x |
|
0 |
0 |
0 |
0 |
0 |
x |
|
0 |
0 |
0 |
0 |
0 |
x |
|
0 |
x |
0 |
x |
0 |
118 - 118 = 0 |
|
0 |
x |
x |
x |
375 - 118 = 257 |
x |