От трех поставщиков 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
загрузка...