От трех поставщиков A1, A2 и A3 необходимо перевезти некий однородный груз пяти потребителям

От трех поставщиков A1, A2 и A3 необходимо перевезти некий однородный груз пяти потребителям B1, B2, B3, B4 и B5. Известны запасы груза поставщиков 24, 51, 25 и потребности потребителя 16, 31, 12, 30, 11. Кроме того, известна стоимость перевозки cij от любого поставщика Ai каждому потребителю Bj – эти стоимости заданы в виде матрицы 𝐶 размерности 3×5. Требуется составить такой план перевозки груза от поставщиков к потребителям, при котором суммарная стоимость перевозки была бы минимальной. C=10711788810711910669

Представим задачу в табличной форме:
B1
B2
B3
B4
B5
Запасы
A1
10 7 8 11 6 24
A2
7 8 10 9 6 51
A3
11 8 7 10 9 25
Потребности 16 31 12 30 11
Проверим баланс задачи:
ai=24+51+25=100; bj=16+31+12+30+11=100
Имеем задачу закрытого типа.
Построим опорный план методом минимальной стоимости. Для этого в ячейку минимальной стоимости (1;5) помещаем максимально возможное перемещение min(24;11)=11. При этом потребности потребителя B5 удовлетворены полностью, а у поставщика A1 остается 13 ед. запаса. Вычеркиваем пятый столбец из дальнейшего построения.
Из оставшихся в ячейки минимальной стоимости (1;2), (2;1) и (3;4) помещаем максимально возможные перемещения min(13;31)=13, min(51;16)=16 и min(25;12)=12. При этом потребности потребителей B1 и B3 удовлетворены полностью, запасы поставщика A1 исчерпаны, у поставщиков A2 и A3 остается 35 и 13 ед

. запаса соответственно, а у потребителя B2 остается потребность еще 18 ед. Вычеркиваем из дальнейшего построения первую строку, а также первый и третий столбцы.
Из оставшихся в ячейку минимальной стоимости (2;2) помещаем максимально возможное перемещение min(35;18)=18. При этом потребности потребителя B2 удовлетворены полностью, а у поставщика A2 остается 17 ед. запаса. Вычеркиваем из дальнейшего построения второй столбец.
В ячейки (2;4) и (3;4) распределяем оставшиеся ресурсы в размерах 17 и 13 ед. соответственно. Получаем опорный план:
B1
B2
B3
B4
B5
Запасы
A1
10
7
13 8
11
6
11 24/13/0
A2
7
16 8
18 10
9
17 6
51/35/17/0
A3
11
8
7
12 10
13 9
25/13/0
Потребности 16/0 31/18/0 12/0 30/0 11/0
Стоимость перевозок составит:
F=7∙13+6∙11+7∙16+8∙18+9∙17+7∙12+10∙13=780
Проверим оптимальность плана методом потенциалов.
Т.к