Пункт
назначения
Пункт
отправления 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) занесем меньшее из чисел a1, 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
Допустимыйплан методом северо-западного угла
Алгоритм состоитиз двух шагов:
Предварительныйшаг
Общеповторяющийсяшаг
Предварительныйшаг:
Находимдопустимый ациклический план.
Составляемсистему потенциалов.
Анализируемсистему на потенциальность.
Общеповторяющийсяшаг:
Положительныеразности />,находим наибольшую, включаем эту клетку в набор и строим на ней цикл.
Означиваемцикл.
Выбираемнаименьшее значение перевозки в клетках отрицательной полуцепи.
Из перевозокв каждой клетке отрицательной полуцепи вычитаем 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 - 5 24 24 Потребность 25 19 24 28
Делаем сдвигпо циклу на 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
Стоимостьперевозок Z = 294
Значениецелевой функции изменилось на 56 единиц по сравнению с предыдущим этапом.
Этап 2
Полагаяпотенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1.. m, j=1… n), просматривая все занятые клетки.
ПотенциалыUi, Vj:
U1=0 V1=C1,1-U1=1 U4=C1,4-V1= 0 V4=C4,4-U4= 5 U3=C4,3-V4= — 2 V3=C3,3-U3= 9 U2=C3,2-V3= — 8 V2=C2,2-U2=9 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток
S1,2 = c1,2 — (u1 + v2) = — 2.
S1,3 = c1,3 — (u1 + v3) = — 6.
S1,4 = c1,4 — (u1 + v4) = 1.
S2,1 = c2,1 — (u2 + v1) = 14.
S2,4 = c2,4 — (u2 + v4) = 7.
S3,1 = c3,1 — (u3 + v1) = 4.
S3,2 = c3,2 — (u3 + v2) = — 4.
S4,2 = c4,2 — (u4 + v2) = — 6.
S4,3 = c4,3 — (u4 + v3) = — 4. 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.
Строим длянее цикл, помечая клетки цикла знаками «плюс» и «минус».
Делаем сдвигпо циклу на величину перевозок в 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 4 2 6 A4 2
Так как всеоценки Si,j>=0, то полученный план является оптимальным.
Транспортнаязадача решена. Поставщик Потребитель Запасы груза 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
Стоимостьперевозок F= 192
Методминимального элемента
1111 33333 455 6 777
Пункт
назначения
Пункт
отправления 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
Z = 1×22+1×19+1×7+3×25+1×4+5×17+5×3=226,в методе северо-западного угла стоимость перевозки была выше и составляла 350. Распределительный метод
Распределительныйметод представляет собой набор следующих действий: вначале строится исходныйопорный план перевозок по одному из вышеизложенных правил, а затем последовательнопроизводится его улучшение до получения оптимального. Для этого для каждойсвободной клетки строят замкнутый цикл. Если в матрице перевозок содержитсяопорный план, то для каждой свободной клетки можно образовать и притом толькоодин замкнутый цикл, содержащий эту свободную клетку и некоторую часть занятыxклеток.
Тарифы вклетках, находящихся в нечетных вершинах цикла, берем со знаком плюс, а вчетных — со знаком минус. По каждому циклу подсчитываем алгебраическую сумму Sij тарифов.
Еслизамкнутый цикл имеет вид: (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
наименьшаяперевозка 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
Оптимальный план получившийся распределительным методом,аналогичен оптимальному плану, получившемуся методом потенциалов