Имеется четыре грузообразующих пункта А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
Ответ
Минимальная транспортная работа составляет 2640
при оптимальном плане: 1500 0 025060 0 000040020400 010.
Решение
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.
План не оптимален, т.к
Задать вопрос
на новый заказ в Автор24.
