13.Метод северо-западного угла построения исходного опорного плана транспортной задачи
Метод северо-западного угла
Метод состоит из конечного числа шагов, а именно m+n-1 шагов.
Пример: а1=15,а2=16,а3=17. В1=11,в2=12,в3=12,в4=13.
1)определение разрешимости задачи.
Т.к они равны, задача разрешима.
Шаг 1
Х11=min(a1,b1)=min(15,11)=11.
Шаг 2. Х12=min(4,12)=4
|
11 |
12 |
12 |
13 |
15 |
11 |
4 |
0 |
0 |
16 |
0 |
8 |
8 |
0 |
17 |
0 |
0 |
4 |
13 |
План, полученный методом с-з угла является опорным.
14.Метод минимального элемента построения исходного опорного плана транспортной задачи
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
B1 |
B2 |
B3 |
B4 |
Запасы |
A1 |
1 |
2 |
4 |
3 |
6 |
A2 |
4 |
3 |
8 |
5 |
8 |
A3 |
2 |
7 |
6 |
3 |
10 |
Потребности |
4 |
6 |
8 |
6 |
|
Проверим необходимое и достаточное условие разрешимости задачи. сумма а=суммеВ 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
|
1 |
2 |
3 |
4 |
Запасы |
1 |
1[4] |
2[2] |
4 |
3 |
6[0] |
2 |
4 |
3[4] |
8 |
5[4] |
8[0] |
3 |
2 |
7 |
6[8] |
3[2] |
10[0] |
Потребности |
4[0] |
6[0] |
8[0] |
6[0] |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи