Пункт
назначения
Пункт
отправления
1
2
3
4
Запасы
1
1
7
3
6
21
2
7
1
1
4
26
3
3
3
7
3
25
4
1
3
5
5
24
Потребности
25
19
24
28
S = 96
Допустимый план методом северо-западного угла
Сущность его состоит в следующем. Будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клетки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1; 1) занесем меньшее из чисел a 1, b 1, т.е. x 11 =min (a 1, b 1). Если а 1 >b 1, то x 11 =b 1 и первый потребитель В 1 будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принимается; в нем переменные. Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел (a 1 — b 1) и b 2, т.е. x 12 = min ((a 1 — b 1), b 2). Если (a 1 — b 1) a 1 то х 11 =min (a 1, b 1) =а 1. При этом запас первого поставщика будет исчерпан, а потому. Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2; 1) заносим наименьшее из чисел (a 2, b 1 — а 1). Заполнив таким образом клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по второй, третьей и последующим строкам (столбцам) производится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы.
Ai* — излишек нераспределенного груза от поставщика Ai
Bj* — недостача в поставке груза потребителю Bj
Помещаем в клетку (1,1) меньшее из чисел A1*=21 и B1*=25
Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимается
Помещаем в клетку (2,1) меньшее из чисел A2*=26 и B1*=4
Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимается
Помещаем в клетку (2,2) меньшее из чисел A2*=22 и B2*=19
Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимается
Помещаем в клетку (2,3) меньшее из чисел A2*=3 и B3*=24
Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимается
Помещаем в клетку (3,3) меньшее из чисел A3*=25 и B3*=21
Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшем в расчет не принимается
Помещаем в клетку (3,4) меньшее из чисел A3*=4 и B4*=28
Так как запасы поставщика A3 исчерпаны, то строка 3 в дальнейшем в расчет не принимается
Помещаем в клетку (4,4) меньшее из чисел A4*=24 и B4*=24
Пункт
назначения
Пункт
отправления
1
2
3
4
Запасы
1
1
21
7
-
3
-
6
-
21
2
7
4
1
19
1
3
4
-
26
3
3
-
3
-
7
21
3
4
25
4
1
-
3
-
5
-
5
24
24
Потребности
25
19
24
28
S = 96
Стоимость перевозок Z = 1×21+4×7+1×19+1×3+7×21+3×4+5×24 = 350
Допустимый план методом северо-западного угла
Алгоритм состоит из двух шагов:
Предварительный шаг
Общеповторяющийся шаг
Предварительный шаг:
Находим допустимый ациклический план.
Составляем систему потенциалов.
Анализируем систему на потенциальность. --PAGE_BREAK--
Общеповторяющийся шаг:
Положительные разности />, находим наибольшую, включаем эту клетку в набор и строим на ней цикл.
Означиваем цикл.
Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи.
Из перевозок в каждой клетке отрицательной полуцепи вычитаем Q, а к положительным перевозка прибавляется. Эта операция – сдвиг по циклу на величину Q.
Пересчитываем систему потенциалов.
Проверяем систему на потенциальность.
Если система не потенциальна, то переходим к пункту 1 общеповторяющегося шага.
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1… m, j=1… n), просматривая все занятые клетки.
Потенциалы Ui, Vj:
U1=0 V1=C1,1-U1= 1 U2=C1,2-V1= 6 V2=C2,2-U2= — 5 V3=C2,3-U2= — 5 U3=C3,3-V3= 12 V4=C3,4-U3= — 9 U4=C4,4-V4= 14 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток S1,2 = c1,2 — (u1 + v2) = 12.
S1,3 = c1,3 — (u1 + v3) = 8.
S1,4 = c1,4 — (u1 + v4) = 15.
S2,4 = c2,4 — (u2 + v4) = 7.
S3,1 = c3,1 — (u3 + v1) = — 10.
S3,2 = c3,2 — (u3 + v2) = — 4.
S4,1 = c4,1 — (u4 + v1) = — 14.
S4,2 = c4,2 — (u4 + v2) = — 6.
S4,3 = c4,3 — (u4 + v3) = — 4.
B1
B2
B3
B4
A1
12
8
15
A2
7
A3
-10
-4
A4
-14
-6
-4
Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (4,1).
Для нее оценка равна — 14.
Строим для нее цикл, помечая клетки цикла знаками «плюс» и «минус».
Поставщик
Потребитель
Запасы груза
B1
B2
B3
B4
A1
1
21
7
3
6
21
A2
-
7
4
1
19
+
1
3
4
26
A3
3
3
-
7
21
+
3
4
25
A4
+
1
3
5 продолжение
--PAGE_BREAK--
-
5
24
24 --PAGE_BREAK--
B1
B2
B3
B4
A1
-2
-6
1
A2
14
7
A3
4
-4
A4
-6
-4
Поставщик
Потребитель
Запасы груза
B1
B2
B3
B4
A1
-
1
21
7
+
3
6
21
A2
7
1
19
1
7
4
26
A3
3
3
-
7
17
+
3
8
25
A4
+
1
4
3
5
-
5
20
24
Потребность
25
19
24
28
Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,3). Для нее оценка равна — 6.
Строим для нее цикл, помечая клетки цикла знаками «плюс» и «минус». продолжение
--PAGE_BREAK--
Делаем сдвиг по циклу на величину перевозок в 17 единиц, прибавляя эту величину к грузу в клетках со знаком «плюс» и отнимая ее от груза в клетках со знаком «минус».
В результате перемещения по циклу получим новый план:
Поставщик
Потребитель
Запасы груза
B1
B2
B3
B4
A1
1
4
7
3
17
6
21
A2
7
1
19
1
7
4
26
A3
3
3
7
3
25
25
A4
1
21
3
5
5
3
24
Потребность
25
19
24
28
Стоимость перевозок Z= 192
Значение целевой функции изменилось на 102 единиц по сравнению с предыдущим этапом.
Этап 3
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1… m, j=1… n), просматривая все занятые клетки.
Потенциалы Ui, Vj:
U1=0 V1=C1,1-U1= 1 V3=C1,3-U1= 3 U4=C1,4-V1= 0 U2=C3,2-V3= — 2 V2=C2,2-U2= 3 V4=C4,4-U4= 5 U3=C4,3-V4= — 2 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток
S1,2 = c1,2 — (u1 + v2) = 4.
S1,4 = c1,4 — (u1 + v4) = 1.
S2,1 = c2,1 — (u2 + v1) = 8.
S2,4 = c2,4 — (u2 + v4) = 1.
S3,1 = c3,1 — (u3 + v1) = 4.
S3,2 = c3,2 — (u3 + v2) = 2.
S3,3 = c3,3 — (u3 + v3) = 6.
S4,2 = c4,2 — (u4 + v2) = 0.
S4,3 = c4,3 — (u4 + v3) = 2.
B1
B2
B3
B4
A1
4
1
A2
8
1
A3 продолжение
--PAGE_BREAK----PAGE_BREAK--
2
7
-
1
19
1
7
4
-
26
3
3
-
3
-
7
-
3
25
25
4
1
4
3
-
5
17
5
3
24
Потребности
25
19
24
28
S = 96
Z = 1×22+1×19+1×7+3×25+1×4+5×17+5×3=226, в методе северо-западного угла стоимость перевозки была выше и составляла 350.
Распределительный метод
Распределительный метод представляет собой набор следующих действий: вначале строится исходный опорный план перевозок по одному из вышеизложенных правил, а затем последовательно производится его улучшение до получения оптимального. Для этого для каждой свободной клетки строят замкнутый цикл. Если в матрице перевозок содержится опорный план, то для каждой свободной клетки можно образовать и притом только один замкнутый цикл, содержащий эту свободную клетку и некоторую часть занятыx клеток.
Тарифы в клетках, находящихся в нечетных вершинах цикла, берем со знаком плюс, а в четных — со знаком минус. По каждому циклу подсчитываем алгебраическую сумму S ij тарифов.
Если замкнутый цикл имеет вид: (i, j) — >(k, j) — >(k, l) — >(t, l) — >… ->(u, v) — >(i, v), то S ij =C ij — C kj + C kl — C tl +… + C uv — C iv, где (i,j) — свободная клетка.
Если алгебраическая сумма S ij отрицательна, то путем изменения значений, стоящих в клетках замкнутого цикла, можно получить план с меньшим значением целевой функции. Критерием оптимальности при нахождении минимума функции служит неотрицательность алгебраических сумм S ij. Если указанное требование не соблюдено, план не оптимален и подлежит улучшению.
Вычисления при решении транспортной задачи распределительным методом ведутся по следующему алгоритму:
исходные данные задачи располагают в распределительной таблице;
строят исходный опорный план по правилу «северо-западного угла», или по правилу «минимального элемента», или методом Фогеля; при этом должны оказаться занятыми r=m+n-1 клеток. Однако, если опорный план является вырожденным, то это условие не соблюдается. Для сохранения числа занятых клеток r=m+n-1 неизменным проделывают следующие шаги: в таблице отыскивают клетку, имеющую минимальный тариф и не образующую цикла с занятыми клетками, помещают в нее базисный нуль и считают ее в дальнейшем занятой. Процесс поиска таких клеток продолжается до тех пор, пока число занятых клеток не станет равным m+n-1;
производят оценку первой свободной клетки путем построения замкнутого цикла и вычисления по этому циклу величины S ij. Если S ij
перемещают по циклу количество груза, равное наименьшему из чисел, размещенных в четных клетках цикла (в клетках со знаком минус). Далее возвращаются к пункту с. Если S ij >=0, то оценивают следующую свободную клетку, и т.д., пока не обнаружат клетку с отрицательной оценкой. Среди всех клеток с oценкой меньше нуля нужно найти клетку с наибольшим нарушением оптимальности, т.е. клетку с наименьшей оценкой. Если, наконец, оценки всех свободных клеток окажутся неотрицательными, то оптимальное решение найдено.
Пункт
назначения
Пункт
отправления
1
2
3
4
Запасы
1
1
21
7
-
3
-
6
-
21
2
7
-
1
19
1
7
4
-
26
3
3
-
3
-
7
-
3
25
25
4
1
4
3
-
5
17
5
3
24
Потребности
25
19
24
28
S= 96
(1,2) = c1,2-c1,1+c4,1-c4,3+c2,3-c2,2 = 2 (1,3) = c1,3-c1,1+c4,1-c4,3 = — 2 (1,4) = c1,4-c1,1+c4,1-c4,4 = 1 (2,1) = c2,1-c2,3+c4,3-c4,1 = 10 (2,4) = c2,4-c2,3+c4,3-c4,4 = 3 (3,1) = c3,1-c3,4+c4,4-c4,1 = 4 (3,2) = c3,2-c3,4+c4,4-c4,3+c2,3-c2,2 = 0 (3,3) = c3,3-c3,4+c4,4-c4,3 = 4 (4,2) = c4,2-c4,3+c2,3-c2,2 = — 2 продолжение
--PAGE_BREAK--
наименьшая перевозка 17, делаем сдвиг
Пункт
назначения
Пункт
отправления
1
2
3
4
Запасы
1
1
4
7
-
3
17
6
-
21
2
7
-
1
19
1
7
4
-
26
3
3
-
3
-
7
-
3
25
25
4
1
21
3
-
5
-
5
3
24
Потребности
25
19
24
28
S = 96
(1,2) = c1,2-c1,3+c2,3-c2,2 = 4 (1,4) = c1,4-c1,1+c4,1-c4,4 = 1 (2,1) = c2,1-c2,3+c1,3-c1,1 = 8 (2,4) = c2,4-c2,3+c1,3-c1,1+c4,1-c4,4 = 1 (3,1) = c3,1-c3,4+c4,4-c4,1 = 4 (3,2) = c3,2-c3,4+c4,4-c4,1+c1,1-c1,3+c2,3-c2,2 = 2 (3,3) = c3,3-c3,4+c4,4-c4,1+c1,1-c1,3 = 6 (4,2) = c4,2-c4,1+c1,1-c1,3+c2,3-c2,2 = 0 (4,3) = c4,3-c4,1+c1,1-c1,3 = 2
Оптимальный план получившийся распределительным методом, аналогичен оптимальному плану, получившемуся методом потенциалов