Реферат по предмету "Информатика, программирование"


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

Пункт
назначения
Пункт
отправления 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
Оптимальный план получившийся распределительным методом,аналогичен оптимальному плану, получившемуся методом потенциалов


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Уголовно-процессуальная профилактика в сфере незаконного оборота наркотических средств и психотропных
Реферат Общие принципы радикальных операций на желудке и кишечнике
Реферат Конвертер программы с подмножества языка Си в Паскаль с использованием LL(1) метода синтаксического анализа (выражения)
Реферат Особенности загрязнения, заражения и обеззараживания помещений и территорий на сельскохозяйственных объектах
Реферат Cry The Beloved Country From Paper To
Реферат Кредитна дiяльнiсть Банкiв
Реферат Автоматизированная система управления эффективностью бизнеса
Реферат Влияние условий среднегорья на подготовку лыжника гонщика
Реферат Калининградская область в 90 е годы XX века
Реферат Религиозные обрядовые праздники и обычаи народов Чечни
Реферат Alfred Wegener Essay Research Paper Alfred Wegener
Реферат Повышение продуктивности скота за счет изменения рациона кормления а так же анализ эффективности
Реферат Сочинение-размышление на морально-этическую тему 2
Реферат Формирование у дошкольников 6-7 лет элементарных математических представлений
Реферат Туристские ресурсы Республики Башкортостан для развития религиозного туризма