Решение задач методом северо-западного угла, рапределительного, минимального и максимального элемента по строке (стр. 1 из 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	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) <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	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

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