Имеется четыре грузообразующих пункта А1,А2,А3,А4 из которых следует вывести груз пяти потребителям (B1, B2,

Имеется четыре грузообразующих пункта А1,А2,А3,А4 из которых следует вывести груз пяти потребителям (B1, B2, B3, B4, B5) соответственно 15, 85, 40, 70 т. Расстояния между грузоотправителями и потребителями указаны в таблиц. При этом потребителю B1 необходимо доставить 40 т. груза, B2 – 40 т., B3 – 80 т., B4 – 40 т. и B5 – 10 т. Необходимо так закрепить потребителей за грузоотправителями, чтобы общая транспортная работа была минимальной. Таблица 4 B1 B2 B3 B4 B5 A1 8 7 9 16 17 A2 12 10 11 14 20 A3 15 14 19 16 19 A4 23 11 14 18 20

A=15+85+40+70=210;
b= 40+40+80+40+10=210 .
a =b= 210. Следовательно, модель задачи – закрытая.
Заполним первоначальную таблицу методом северо-западного угла.
x11 = min(15,40) = 15;
x21 = min(85,25) = 25;
x22 = min(60,40) = 40;
x23 = min(20,80) = 20;
x33 = min(40,60) = 40;
x43 = min(70,20) = 20;
x44 = min(50,40) = 40;
x45 = min(10,10) = 10.
Получим первый опорный план:
Таблица 5
B1 B2 B3 B4 B5 ai (Запасы) ai (Потенциалы)
A1 8
15 1 7 2 9 5 16 4 17 15 0
A2 12
25 10
40 11
20 -1 14 3 20 85 -4
A3
-5 15
-4 14 19
40 - -7 16
+ -6 19 40 -12
A4
8 23 -2 11 14
20 + 18
40 - 20
10 70 -7
Bj (Потребности) 40 40 80 40 10 210
Bj (Потенциалы) -8 -6 -7 -11 -13
Таким образом, все потребности удовлетворены и все запасы исчерпаны. Проверим, является ли план, составленный методом минимального элемента опорным, т.е. число базисных (заполненных) клеток должно быть m+n-1=8. Действительно, решение является опорным, так как базисных клеток в таблице 8.
Минимальная транспортная работа при первом опорном плане составят:
L(x) = 8*15 + 12*25 + 10*40 + 11*20 + 19*40 + 14*20 + 18*40 + 20*10 = 3000.
Проверим план на оптимальность и при необходимости улучшим его

.
Ui+Vj=-Сij (Заполненные клетки)
u1 + v1 = -8; u1 = 0; v1 = -8;u2 + v1 = -12; u2 = -4; v2 = -6;
u2 + v2 = -10; u3 = -12; v3 = -7;u2 + v3 = -11; u4 = -7; v4 = -18;u3 + v3 = -19; v5 = -13 ;
u4 + v3 = -14;
u4 + v4 = -18;
u4 + v5 = -20;
Занесем значения u1, u2, u3, u4, v1, v2, v3, v4, v5 в таблицу 5 и посчитаем оценки.
=Ui+Vj+Сij (Пустые клетки)
12 = 0 – 6 + 7 = 1
13 = 0 – 7 + 9 = 2
14 = 0 – 11 + 16 = 5
15 = 0 – 13 + 17 = 4
24 = - 4 - 11 + 14 = -1
25 = -4 - 13 + 20 = 3
31 = -12 - 8 + 15 = -5
32 = -12 - 6 + 14 = -4
34 = -12 - 11 + 16 = -7
35 = -12 - 13 + 19 = -6
41 = -7 – 8 + 23 = 8
42 = -7 – 6 + 11 = -2
План не оптимален, т.к. есть отрицательные оценки. Следовательно, улучшим план, построив цикл пересчета.
Min(-1,-5,-4,-7,-6,-2) = -7. (Минимальое значение из полученных оценок). Следовательно, выбираем клетку 34. Ставим в этой клетке «+» и рисуем цикл.
Цикл пересчета: (3,4 → 3,3 → 4,3 → 4,4).
Min(40,40) = 40. (Смотрим на значения в минусовых клетках и выбираем из них наименьшее значение).
Прибавляем и вычитаем 40 в ячейках цикла и формируем новую таблицу 6.
Таблица 6
B1 B2 B3 B4 B5 ai (Запасы) ai (Потенциалы)
A1 8
15 1 7 2 9 12 16 4 17 15 0
A2 12
25 10
40 11
20 6 14 3 20 85 -4
A3
-5 15
-4 14 19
- 0 16
40 -6 19
+ 40 -12
A4
8 23 -2 11 14
60 + 7 18
20
10 - 70 -7
Bj (Потребности) 40 40 80 40 10 210
Bj (Потенциалы) -8 -6 -7 -4 -13
Проверим план на оптимальность и при необходимости улучшим его.
Аналогичным образом находим потенциалы и оценки и отображаем результаты в таблице 6.
План не оптимален, т.к