Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5 |
3 |
2[100] |
3 |
0 |
100 |
|
2 |
3[170] |
5 |
4 |
3[30] |
0 |
200 |
|
3 |
4 |
2[80] |
3[40] |
7[10] |
0[20] |
150 |
|
4 |
8 |
6 |
7 |
2[150] |
0 |
150 |
|
Потребности |
170 |
80 |
140 |
190 |
20 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
|
|
v1=6 |
v2=1 |
v3=2 |
v4=6 |
v5=-1 |
|
u1=0 |
5 |
3 |
2[100] |
3 |
0 |
|
u2=-3 |
3[170] |
5 |
4 |
3[30] |
0 |
|
u3=1 |
4 |
2[80] |
3[40] |
7[10] |
0[20] |
|
u4=-4 |
8 |
6 |
7 |
2[150] |
0 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;4): 3
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
5 |
3 |
2[100][-] |
3[+] |
0 |
100 |
|
2 |
3[170] |
5 |
4 |
3[30] |
0 |
200 |
|
3 |
4 |
2[80] |
3[40][+] |
7[10][-] |
0[20] |
150 |
|
4 |
8 |
6 |
7 |
2[150] |
0 |
150 |
|
Потребности |
170 |
80 |
140 |
190 |
20 |
|