Схема исследования задач типа (1)

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 2

1) Проверяем условие существования решения задачи (1), при этом применяется критерий существования решения . В общем случае, при , вызывает трудности проверка условий существования решения, так как в редких случаях можно представить (построить) множество уровня.

2) Составляем систему (4) и находим стационарные точки функции (все). Только среди них может находиться оптимальный план и все локально-оптимальные планы. Пусть – все стационарные точки функции .

3) Для каждой стационарной точки проверяем выполнение или невыполнение условий (3)-(5). Пусть – стационарная точка, тогда возможны случаи:

а) . Тогда, согласно теореме 3 – локально-оптимальный план.

б) . Тогда для нее выполн. условия теор.2, но не выполн. условия теор.3. Тем не менее, она остается подозрительной на решение зад.(1) (т.е. она может оказаться и оптимальным планом и локально-оптимальным планом).

в)Не выполн. ни а)ни б).Тогда эту точку исключают из дальнейшего рассмотр-я.

4) Делаем вывод: среди точек, оказавшихся либо локально-оптимал. планами, либо подозрительных на решение, находим лучшую, т.е. подставляем точки в целевую ф-цию и лучшей будет точка с наименьшим значением ф-ции. Если док-но существование реш-я и построены все стационарные точки, то лучшая точка будет оптимал. планом. В общем случае, из-за сложности функции и невозможности найти все решения системы (4) исследование нельзя провести полностью и лучшая точка остается подозрительной на решение задачи.

3часть______________________________________________________

Общая схема метода ветвей и границ. Задача о рюкзаке.

Метод ветвей и границ явл. одним из самых популярных методов перебора, кот. позволяет сокращать объём перебираемых планов за счёт исключения бесперспективных подмн-в планов, т.е. таких, кот. заведомо не содержат реш-я.

Метод применяют к зад.: , (1).

Общая схема. В методе на каждой итерации строится список из перспективных подмн-тв, одно из кот., по крайне мере содержит оптимал. план. На нулевой итерации . Вычисляем оценку итерации , рекорд итерации .

Вычисляем разность . Возможны случаи:

1. . В этом случае рекордный план будет оптимальным планом задачи, так как на нём достигалась нижняя граница.

2. , где -малое положит. число, заданная точность вычисления. В этом случае рекордный план можно взять в качестве - оптимального, т.е. приближённого реш-я задачи (1).

3. . Тогда заданная точность не достигнута. Переходим к первой итерации. Для этого в соответствие с первым предположением ветвим на более мелкие. Для каждого вычисл. границу по второму предположению, и бесперспективные подмн-ва отбрасываем,а перспективные включаем в список для 1-вой итерации.

Постановка зад. о рюкзаке. Имеется неделимых предметов и для каждого предмета известно его вес и стоимость. Требуется некоторую часть этих предметов уложить в рюкзак, причём так, чтобы их суммарная стоимость была не меньше , и вес рюкзака был минимальным.

Математическая модель. Введём неизвестные

тогда ограничения по стоимости будут: . Целевая функция: . Для реш. этой задачи эффективен метод ветвей и границ.

Минимизация унимодальных функций. Равномерный перебор.

Рассм. задачу , (1) где – некоторые числа ().

Методы минимизации унимодал. ф-ций. Опр. Ф-ция наз. унимодальной на [ ], если сущ.точка т, что на ф-ция монотонно убывает, а на монотонно возрастает. - оптимал. план задачи (1).

В зад.(1)унимодальная ф-ция имеет единств. оптимал. план и не имеет локал. минимумов. Если в задаче (1) (3) , то ф-ция строго выпукла и явл. унимодальной. Если в зад.(1) ф-ция не унимодальная, то в некоторых случаях [a,b] с помощью нерав-ва (3) её удаётся разбить на интервалы унимодальности, затем чтобы реш. исходную зад.(1) достаточ. на каждом таком отрезке реш. задачу минимизации унимодал. ф-ции и простым перебором найти оптимал. план.

Будем решать задачу (1), в которой - унимодальная функция.

Поставим цель: по заданному найти на [a,b] такую часть (длиною ) и чтобы . Эта задача называется задачей локализации точки минимума.

Если задача локализации решена, то в любую точку из (например, середину) принимают в качестве приближённого решения задачи (1).

Метод равномерного поиска

Выбираем некоторое и разбиваем исходный отрезок [ ] на частей точками …, где и поочерёдно начиная с вычисляем значение функции . В силу унимодальности будут выполняться неравенства . Тогда ясно, что

Если , то задача локализации решена. В противном случае выбираем и разбиваем его на некоторое количество частей и операцию поиска повторяем. В конце концов, задача (1) будет решена.

Замечание. Можно сразу подобрать таким образом, чтобы выполнялось , но это не рационально, так как количество точек перебора будет очень большим. Лучше на 1-ом этапе исходный отрезок разбить на количество частей , потом количество точек увеличить.

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности