Контрольная работа

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

Работа добавлена на сайт bukvasha.net: 2014-11-09

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 26.12.2024


Пункт
назначения
Пункт
отправления
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. Реферат на тему The Working Class Essay Research Paper The
2. Реферат на тему Don Pepe Figueres Essay Research Paper Like
3. Реферат Роль секса в рекламе
4. Краткое содержание Ю-ю
5. Реферат Генная инженерия 4
6. Диплом Стратегия ценообразования розничного магазина
7. Реферат на тему Основные матмодели в теории надежности Выбор числа показателей надежности Достоверность статистической
8. Реферат на тему Джерела екологічного права
9. Реферат на тему The Lasting Effect Of The Crusades Essay
10. Реферат Понятие и сущность юридического лица 3