Решение задач методом северо-западного угла, рапределительного, минимального и максимального элемента по строке

2





Пункт 

назначения

Пункт

отправления

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

 = 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) <b 2, то запасы первого поставщика исчерпаны и первая строка таблицы в дальнейшем в расчет не принимается. Переходим к аналогичному распределению запаса груза второго поставщика. Если 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

 = 96



Стоимость перевозок Z = 121+47+119+13+721+34+524 = 350

Допустимый план методом северо-западного угла

Алгоритм состоит из двух шагов: 

Предварительный шаг

Общеповторяющийся шаг

Предварительный шаг: 

Находим допустимый ациклический план. 

Составляем систему потенциалов. 

Анализируем систему на потенциальность. 

Общеповторяющийся шаг: 

Положительные разности , находим наибольшую, включаем эту клетку в набор и строим на ней цикл. 

Означиваем цикл. 

Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи. 

Из перевозок в каждой клетке отрицательной полуцепи вычитаем , а к положительным перевозка прибавляется. Эта операция – сдвиг по циклу на величину . 

Пересчитываем систему потенциалов. 

Проверяем систему на потенциальность. 

Если система не потенциальна, то переходим к пункту 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

 

0

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 4 55 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

 = 96



Z = 122+119+17+325+14+517+53=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 <0, то переходят к следующему пункту алгоритма; 

перемещают по циклу количество груза, равное наименьшему из чисел, размещенных в четных клетках цикла (в клетках со знаком минус). Далее возвращаются к пункту с. Если 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

 = 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

 = 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

Оптимальный план получившийся распределительным методом, аналогичен оптимальному плану, получившемуся методом потенциалов