Проверка на оптимальность опорного плана транспортной задачи
От трех поставщиков A1, A2 и A3 необходимо перевезти некий однородный груз пяти потребителям B1, B2, B3, B4 и B5. Известны запасы груза поставщиков {a1,a2,a3} и потребности потребителя {b1,b2,b3,b4,b5}. Кроме того, известна стоимость перевозки cij от любого поставщика Ai каждому потребителю Bj - эти стоимости заданы в виде матрицы С размерности3 x 5. Требуется составить такой план перевозки груза от поставщиков к потребителям, при котором суммарная стоимость перевозки была бы минимальной.
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16 | 21 | 19 | 950 |
| 2 | 4 | 4 | 9 | 5 | 300 |
| 3 | 3 | 8 | 14 | 10 | 1350 |
| 4 | 24 | 33 | 36 | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 950 + 300 + 1350 + 450 = 3050
∑ b = 250 + 1000 + 700 + 1100 = 3050
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16 | 21 | 19 | 950 |
| 2 | 4 | 4 | 9 | 5 | 300 |
| 3 | 3 | 8 | 14 | 10 | 1350 |
| 4 | 24 | 33 | 36 | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Искомый элемент равен 3
Для этого элемента запасы равны 1350, потребности 250. Поскольку минимальным является 250, то вычитаем его.
x |
16 |
21 |
19 |
950 |
x |
4 |
9 |
5 |
300 |
3 |
8 |
14 |
10 |
1100 |
x |
33 |
36 |
34 |
450 |
0 |
1000 |
700 |
1100 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 300, потребности 1000. Поскольку минимальным является 300, то вычитаем его.
| x | 16 | 21 | 19 | 950 |
| x | 4 | x | x | 0 |
| 3 | 8 | 14 | 10 | 1100 |
| x | 33 | 36 | 34 | 450 |
| 0 | 700 | 700 | 1100 | 0 |
Искомый элемент равен 8
Для этого элемента запасы равны 1100, потребности 700. Поскольку минимальным является 700, то вычитаем его.
| x | x | 21 | 19 | 950 |
| x | 4 | x | x | 0 |
| 3 | 8 | 14 | 10 | 400 |
| x | x | 36 | 34 | 450 |
| 0 | 0 | 700 | 1100 | 0 |
Искомый элемент равен 10
Для этого элемента запасы равны 400, потребности 1100. Поскольку минимальным является 400, то вычитаем его.
| x | x | 21 | 19 | 950 |
| x | 4 | x | x | 0 |
| 3 | 8 | x | 10 | 0 |
| x | x | 36 | 34 | 450 |
| 0 | 0 | 700 | 700 | 0 |
Искомый элемент равен 19
Для этого элемента запасы равны 950, потребности 700. Поскольку минимальным является 700, то вычитаем его.
| x | x | 21 | 19 | 250 |
| x | 4 | x | x | 0 |
| 3 | 8 | x | 10 | 0 |
| x | x | 36 | x | 450 |
| 0 | 0 | 700 | 0 | 0 |
Искомый элемент равен 21
Для этого элемента запасы равны 250, потребности 700. Поскольку минимальным является 250, то вычитаем его.
| x | x | 21 | 19 | 0 |
| x | 4 | x | x | 0 |
| 3 | 8 | x | 10 | 0 |
| x | x | 36 | x | 450 |
| 0 | 0 | 450 | 0 | 0 |
Искомый элемент равен 36
Для этого элемента запасы равны 450, потребности 450. Поскольку минимальным является 450, то вычитаем его.
| x | x | 21 | 19 | 0 |
| x | 4 | x | x | 0 |
| 3 | 8 | x | 10 | 0 |
| x | x | 36 | x | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16 | 21[250] | 19[700] | 950 |
| 2 | 4 | 4[300] | 9 | 5 | 300 |
| 3 | 3[250] | 8[700] | 14 | 10[400] | 1350 |
| 4 | 24 | 33 | 36[450] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 21; 0 + v3 = 21; v3 = 21
u4 + v3 = 36; 21 + u4 = 36; u4 = 15
u1 + v4 = 19; 0 + v4 = 19; v4 = 19
u3 + v4 = 10; 19 + u3 = 10; u3 = -9
u3 + v1 = 3; -9 + v1 = 3; v1 = 12
u3 + v2 = 8; -9 + v2 = 8; v2 = 17
u2 + v2 = 4; 17 + u2 = 4; u2 = -13
| v1=12 | v2=17 | v3=21 | v4=19 | |
| u1=0 | 12 | 16 | 21[250] | 19[700] |
| u2=-13 | 4 | 4[300] | 9 | 5 |
| u3=-9 | 3[250] | 8[700] | 14 | 10[400] |
| u4=15 | 24 | 33 | 36[450] | 34 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 17 > 16; ∆12 = 0 + 17 - 16 = 1
(2;4): -13 + 19 > 5; ∆24 = -13 + 19 - 5 = 1
(4;1): 15 + 12 > 24; ∆41 = 15 + 12 - 24 = 3
max(1,1,3) = 3
Выбираем максимальную оценку свободной клетки (4;1): 24
Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16 | 21[250][+] | 19[700][-] | 950 |
| 2 | 4 | 4[300] | 9 | 5 | 300 |
| 3 | 3[250][-] | 8[700] | 14 | 10[400][+] | 1350 |
| 4 | 24[+] | 33 | 36[450][-] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 250. Прибавляем 250 к объемам грузов, стоящих в плюсовых клетках и вычитаем 250 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16 | 21[500] | 19[450] | 950 |
| 2 | 4 | 4[300] | 9 | 5 | 300 |
| 3 | 3 | 8[700] | 14 | 10[650] | 1350 |
| 4 | 24[250] | 33 | 36[200] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 21; 0 + v3 = 21; v3 = 21
u4 + v3 = 36; 21 + u4 = 36; u4 = 15
u4 + v1 = 24; 15 + v1 = 24; v1 = 9
u1 + v4 = 19; 0 + v4 = 19; v4 = 19
u3 + v4 = 10; 19 + u3 = 10; u3 = -9
u3 + v2 = 8; -9 + v2 = 8; v2 = 17
u2 + v2 = 4; 17 + u2 = 4; u2 = -13
| v1=9 | v2=17 | v3=21 | v4=19 | |
| u1=0 | 12 | 16 | 21[500] | 19[450] |
| u2=-13 | 4 | 4[300] | 9 | 5 |
| u3=-9 | 3 | 8[700] | 14 | 10[650] |
| u4=15 | 24[250] | 33 | 36[200] | 34 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 17 > 16; ∆12 = 0 + 17 - 16 = 1
(2;4): -13 + 19 > 5; ∆24 = -13 + 19 - 5 = 1
max(1,1) = 1
Выбираем максимальную оценку свободной клетки (1;2): 16
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16[+] | 21[500] | 19[450][-] | 950 |
| 2 | 4 | 4[300] | 9 | 5 | 300 |
| 3 | 3 | 8[700][-] | 14 | 10[650][+] | 1350 |
| 4 | 24[250] | 33 | 36[200] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 450. Прибавляем 450 к объемам грузов, стоящих в плюсовых клетках и вычитаем 450 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16[450] | 21[500] | 19 | 950 |
| 2 | 4 | 4[300] | 9 | 5 | 300 |
| 3 | 3 | 8[250] | 14 | 10[1100] | 1350 |
| 4 | 24[250] | 33 | 36[200] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 16; 0 + v2 = 16; v2 = 16
u2 + v2 = 4; 16 + u2 = 4; u2 = -12
u3 + v2 = 8; 16 + u3 = 8; u3 = -8
u3 + v4 = 10; -8 + v4 = 10; v4 = 18
u1 + v3 = 21; 0 + v3 = 21; v3 = 21
u4 + v3 = 36; 21 + u4 = 36; u4 = 15
u4 + v1 = 24; 15 + v1 = 24; v1 = 9
| v1=9 | v2=16 | v3=21 | v4=18 | |
| u1=0 | 12 | 16[450] | 21[500] | 19 |
| u2=-12 | 4 | 4[300] | 9 | 5 |
| u3=-8 | 3 | 8[250] | 14 | 10[1100] |
| u4=15 | 24[250] | 33 | 36[200] | 34 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;4): -12 + 18 > 5; ∆24 = -12 + 18 - 5 = 1
Выбираем максимальную оценку свободной клетки (2;4): 5
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16[450] | 21[500] | 19 | 950 |
| 2 | 4 | 4[300][-] | 9 | 5[+] | 300 |
| 3 | 3 | 8[250][+] | 14 | 10[1100][-] | 1350 |
| 4 | 24[250] | 33 | 36[200] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 300. Прибавляем 300 к объемам грузов, стоящих в плюсовых клетках и вычитаем 300 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 12 | 16[450] | 21[500] | 19 | 950 |
| 2 | 4 | 4 | 9 | 5[300] | 300 |
| 3 | 3 | 8[550] | 14 | 10[800] | 1350 |
| 4 | 24[250] | 33 | 36[200] | 34 | 450 |
| Потребности | 250 | 1000 | 700 | 1100 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 16; 0 + v2 = 16; v2 = 16
u3 + v2 = 8; 16 + u3 = 8; u3 = -8
u3 + v4 = 10; -8 + v4 = 10; v4 = 18
u2 + v4 = 5; 18 + u2 = 5; u2 = -13
u1 + v3 = 21; 0 + v3 = 21; v3 = 21
u4 + v3 = 36; 21 + u4 = 36; u4 = 15
u4 + v1 = 24; 15 + v1 = 24; v1 = 9
| v1=9 | v2=16 | v3=21 | v4=18 | |
| u1=0 | 12 | 16[450] | 21[500] | 19 |
| u2=-13 | 4 | 4 | 9 | 5[300] |
| u3=-8 | 3 | 8[550] | 14 | 10[800] |
| u4=15 | 24[250] | 33 | 36[200] | 34 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj <= cij.
Минимальные затраты составят:
F( x) = 16*450 + 21*500 + 5*300 + 8*550 + 10*800 + 24*250 + 36*200 = 44800
