Пункт назначения Пункт отправления	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	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 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 <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 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 Оптимальный план получившийся распределительным методом, аналогичен оптимальному плану, получившемуся методом потенциалов 1. Курсовая на тему Использование метафоры в поэзии С Есенина 2. Реферат Формы и системы оплаты труда на предприятии 3. Реферат Отчет о прибылях и убытках и порядок формирования финансовых результатов 4. Реферат на тему When Did The First Americans Appear Essay 5. Курсовая Маркетинговое исследование предложения сотовых телефонов 6. Реферат Биографии Коко Шанель 7. Реферат на тему Internet Censorship Essay Research Paper I work 8. Реферат Гладиаторские бои 9. Реферат на тему For Love Or Money 10. Реферат Зарплата сущность, виды и уровень, человеческий капитал Bukvasha Правила Контакты