Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2018-01-04 | 249 |
5.00
из
|
Заказать работу |
|
|
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0)
a0,l=min{a0,i }
l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0
k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.
Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
21. Постановка наиболее распространённых задач дискретной оптимизации: задача коммиво-яжера и задача об укладке ранца.
Одним из подходов к решению задачи является формулировка её в виде задачи дискретной оптимизации, при этом решения представляются в виде переменных, а связи — в виде отношений неравенства между ними. Таким образом, возможно несколько вариантов. Например, симметричную задачу можно представить в виде множества ребер V {\displaystyle V}. Каждому ребру {I,j}{\displaystyle \{i,j\}} сопоставляется двоичная переменная {\displaystyle x_{ij}\in \{0,1\}}, равная 1, если ребро принадлежит маршруту, и 0 — в противном случае. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства.
|
Каждая вершина должна сообщаться через пару ребер с остальным вершинам, то есть, через входное и выходное ребро:
Классическая постановка задачи об укладке ранца:
Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. Также имеется рюкзак определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.
22. Постановка наиболее распространённых задач дискретной оптимизации: задача о покрытии множества и задача о назначении.
Исходными данными задачи о покрытии множества является конечное множество U {\displaystyle {\mathcal {U}}} и S семейство {\displaystyle {\mathcal {S}}} его подмножеств. Покрытием называют семейство {\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}} наименьшей мощности, объединением которых является U {\displaystyle {\mathcal {U}}}. В случае постановки вопроса о разрешении на вход подаётся пара {\displaystyle ({\mathcal {U}},{\mathcal {S}})} и целое число k {\displaystyle k}; вопросом является существование покрывающего множества мощности k {\displaystyle k} (или менее).
В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков S {\displaystyle S}. Также есть группа людей, владеющих некоторыми из этих навыков. Необходимо сформировать минимальную группу для выполнения задания, включающую в себя носителей всех необходимых навыков.
|
Методы решения.
Жадный приближенный алгоритм:
Жадный алгоритм выбирает множества руководствуясь следующим правилом: на каждом этапе выбирается множество, покрывающее максимальное число ещё не покрытых элементов.
Можно показать, что такой алгоритм показывает время работы (O(H(s) {\displaystyle O(H(s))}, где s {\displaystyle s} — мощность наибольшего множества, и H(n){\displaystyle H(n)} — это сумма первых n {\displaystyle n} членов гармонического ряда.{\displaystyle H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1}
Часто задача о покрытии множества формулируется, как задача целочисленного программирования:
Точное решение может быть получено за полиномиальное время, в случае, когда матрица A{\displaystyle A} вполне унимодулярна.
Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве.
В частности, когда каждый столбец матрицы {\displaystyle A}содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где n {\displaystyle n} или m {\displaystyle m} ограничены константой, задача за полиномиальное время решается методами полного перебора.
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.
23. Область применения и общая идея решения оптимизационных задач методом динамического программирования (ДП). Суть восходящего и нисходящего ДП.
Алгоритм, основанный на МДП (или, короче, ДП-алгоритм), позволяет решить каждую из подзадач один раз и ответ занести в специальную таблицу, для того чтобы в том случае, если на одном из последующих шагов оптимизации эта задача встретится ещё раз, можно было воспользоваться ранее полученным решением.
|
Динамическое программирование обычно придерживается двух подходов к решению задач:
· нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
· восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.
24. Последовательность решения задачи определения критических путей сети с помощью метода динамическогопрограммировання.
Наиболее продолжительный полный путь в сетевом графике называется критическим. Критическими также называются работы и события расположенные на этом пути. Работы этого пути определяют общий цикл завершения всего комплекса работ, планируемых при помощи сетевого графика.
Время n(t) завершения последнего n - го узла назовем критическим временем завершения всего комплекса работ. Критическое время обозначим символом Tкр; Критическим путем назовем путь, который строится обратным ходом, начиная от последнего n - го узла, и достигает первого узла при помощи выделения стрелок, реализующих критическое время; Операции, составляющие критический путь, называются критическими. Замечание. Критический путь может быть неединственным.
Рисунок 1. Критический путь
Из рисунка 11 вытекает, что сетевой график содержит 5 этапов, Tкр 28 часов. Заметим также, что сетевой график имеет два критических пути, которые на рис. 11 изображены жирными линиями и состоят из следующих узлов:
1 →4 →3 →5 →8 →10 и 1 →4→ 3→ 6→ 8→ 10.
На каждом из критических путей критическое время одно и тоже 28 часов. Свободные резервы времени на некритических операциях с Рij на рисунке проставлены в скобках.
|
25. Последовательность решения задачи коммивояжёра с помощью метода динамическогопрограммировання.
Псевдокод:
Сложность:
26. Представлениезадачи о покрытии множества в видезадачицелочисленногобулевоголинейногопрограммирования.
27. Представлениезадачи о назначении, 0-1-задачи о рюкзаке и задачи коммивояжёра в видезадачицелочисленногобулевоголинейногопрограммирования.
Задача о ранце.
Имеются n предметов, которые необходимо поместить в рюкзак (ранец). Пусть известны вес aj и «ценность» cj каждого предмета (j= 1,2,...,n). Требуется заполнить рюкзак, не превышая его грузоподъемности (объема) b и максимизируя суммарную ценность груза. Получаем следующую булеву ЗЦЛП (задача о рюкзаке):
Задача о целочисленном рюкзаке. Предположим теперь, что каждый предмет имеется в неограниченном числе экземпляров, и требуется также максимизировать суммарную ценность груза, не превышая грузоподъемности. Получаем так называемую задачу о целочисленном рюкзаке:
Максимизировать общий вес рюкзака.
Решение. I этап. Условная оптимизация.
f1(L) = max(2x1); 0 < x1 < 1; x1 = 0,1.
f1(0) = max[0*2] = 0
f1(1) = max[0*2, 1*2] = 2
f1(2) = max[0*2, 1*2] = 2
f1(3) = max[0*2, 1*2] = 2
f1(4) = max[0*2, 1*2] = 2
f1(5) = max[0*2, 1*2] = 2
f1(6) = max[0*2, 1*2] = 2
f1(7) = max[0*2, 1*2] = 2
Таблица 1 – Расчет значения функции f1(L)
f2(L) = max[3x2 + f1(L - 2x2)]; 0 < x2 < 3; x2 = 0,1,2,3.
f2(0) = max[0*3+0] = 0
f2(1) = max[0*3+2] = 2
f2(2) = max[0*3+2, 1*3+0] = 3
f2(3) = max[0*3+2, 1*3+2] = 5
f2(4) = max[0*3+2, 1*3+2, 2*3+0] = 6
f2(5) = max[0*3+2, 1*3+2, 2*3+2] = 8
f2(6) = max[0*3+2, 1*3+2, 2*3+2, 3*3+0] = 9
f2(7) = max[0*3+2, 1*3+2, 2*3+2, 3*3+2] = 11
Таблица 2 – Расчет значения функции f2(L)
f3(L) = max[2x3 + f2(L - 3x3)]; 0 < x3 < 3; x3 = 0,1,2,3.
f3(0) = max[0*2+0] = 0
f3(1) = max[0*2+2] = 2
f3(2) = max[0*2+3] = 3
f3(3) = max[0*2+5, 1*2+0] = 5
f3(4) = max[0*2+6, 1*2+2] = 6
f3(5) = max[0*2+8, 1*2+3] = 8
f3(6) = max[0*2+9, 1*2+5, 2*2+0] = 9
f3(7) = max[0*2+11, 1*2+6, 2*2+2] = 11
Таблица 3 – Расчет значения функции f3(L)
f4(L) = max[4x4 + f3(L - 1x4)]; 0 < x4 < 1; x4 = 0,1.
f4(0) = max[0*4+0] = 0
f4(1) = max[0*4+2, 1*4+0] = 4
f4(2) = max[0*4+3, 1*4+2] = 6
f4(3) = max[0*4+5, 1*4+3] = 7
f4(4) = max[0*4+6, 1*4+5] = 9
f4(5) = max[0*4+8, 1*4+6] = 10
f4(6) = max[0*4+9, 1*4+8] = 12
f4(7) = max[0*4+11, 1*4+9] = 13
Таблица 4 – Расчет значения функции f4(L)
f5(L) = max[1x5 + f4(L - 1x5)]; 0 < x5 < 2; x5 = 0,1,2.
f5(0) = max[0*1+0] = 0
f5(1) = max[0*1+4, 1*1+0] = 4
f5(2) = max[0*1+6, 1*1+4, 2*1+0] = 6
f5(3) = max[0*1+7, 1*1+6, 2*1+4] = 7
f5(4) = max[0*1+9, 1*1+7, 2*1+6] = 9
f5(5) = max[0*1+10, 1*1+9, 2*1+7] = 10
f5(6) = max[0*1+12, 1*1+10, 2*1+9] = 12
f5(7) = max[0*1+13, 1*1+12, 2*1+10] = 13
Таблица 5 – Расчет значения функции f5(L)
II этап. Безусловная оптимизация.
Таким образом, максимальный вес рюкзака f5(7) равна 13 кг.
При этом x5 = 0, так как f5(7) = 13 достигается при х5=0 (см. таблицу 5).
Предметы остальных типов распределяются следующим образом:
L = 7 - 1 * 0 = 7
f4(7) = 13 достигается при х4 = 1 (см. таблицу 4).
L = 7 - 1 * 1 = 6
f3(6) = 9 достигается при х3 = 0 (см. таблицу 3).
L = 6 - 3 * 0 = 6
f2(6) = 9 достигается при х2 = 3 (см. таблицу 2).
L = 6 - 2 * 3 = 0
f1(0) = 0 достигается при х1 = 0 (см. таблицу 1).
L = 0 - 1 * 0 = 0
В итоге наилучший вариант загрузки рюкзака достигается при значениях: x1 = 0, x2 = 3, x3 = 0, x4 = 1, x5 = 0
|
28. Обобщённая схема классического генетического алгоритма. Краткая характеристика основных операторов генетического алгоритма (операторы репродукции, кроссинговера, мутации).
Основные операторы ГА
Оператор репродукции (селекции) – искуственная версия естественного отбора, основанного на принципе выживания более приспособленных особей. В результате выполнения этого оператора хромосомы копируются в промежуточную популяцию для дальнейшего «размножения» согласно их значениям фитнесс-функции.
Оператор кроссинговера (скрещивания) – основан на принципе наследования потомками генетической информации родителей и определяет передачу признаков (наследственной информации) родителей потомкам.
Оператор мутации – основан на принципе резкого изменения свойств потомков и приобретении у них свойств, отсутствующих у родителей; позволяет повысить разнообразие (изменчивость) особей в популяции (множество решений).
Рисунок 1 – Блок-схема классического (простого) ГА
ПРАКТИКА:
1. Используя программную среду MATLAB, произвестилокальнуюлинейную интерполяцию, а такжеинтерполяцию на основе кубического сплайнафункциональнойзвисимостиy = f(x), представленной рядом значенийxиy:
X -3,5 -2,4 -1,8 0,14 2,12 3,64 5,29 7,72
Y 1,2 2,5 7,3 11,6 12,8 14,9 20,1 24,0.
|
|
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!