42. Условная и безусловная оптимизация.

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

Оптимизация бывает: условная и безусловная.

Условной оптимизации - содержит некоторые ограничения по независимым переменным на множестве G. Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих равенствам или неравенствам.

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линей-ной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации. Существуют также приближенные методы решения нелинейных задач. Это мето-ды основанные на методе кусочно-линейной аппроксимации.

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

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

Задача безусловной оптимизации состоит в нахождении минимума или максимума функции в от-сутствие каких-либо ограничений.

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

Решение безусловной оптимизации является более простым и легко реализуется в современных ма-тематических пакетах. Для решения поставленной задачи используются средства программы MathCAD.

43. Задачи нелинейного программирования самого различного физического смысла допускают геометрическую интерпретацию.

Процесс нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации включает следующие этапы:

1.Находят область допустимых решений задачи, определяемую соотношениями (если она пуста, то задача не имеет решения).

2.Строят гиперповерхность f (x1, x2, …, xn) = h.

3.Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функций сверху (внизу) на множестве допустимых решений.

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

Или приводят задачу нелинейного программирования к задаче линейного программирования и решают нижеизложенными способами.

Задача является задачей линейного программирования, а следовательно, ее решение можно найти известными методами: 1) графический; 2) табличный (прямой, простой) симплекс – метод; 3) метод искусственного базиса; 4) модифицированный симплекс – метод; 5) двойственный симплекс – метод.

44. Метод множителей Лагранжа - метод нахождения условного экстремума функции  , где  , относительно   ограничений φ_i(x) = 0, где   меняется от единицы до  .

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

Метод множителей Лагранжа применяется:

• при решении задач нелинейного программирования, возникающих во многих областях;

• Основной метод решения задачи об оптимизации качества кодирования аудио и видео данных при заданном среднем бит рейте.

Описание метода множителей Лагранжа:

1. Составим функцию Лагранжа в виде линейной комбинации функции f и функций φ_i, взятых с коэффициентами, называемыми множителями Лагранжа — λ_i: , где  .

2. Составим систему из n + m уравнений, приравняв к нулю частные производные функции Лагранжа   по x_j и λ_i.

3. Если полученная система имеет решение относительно параметров x'j и λ'i, тогда точка x' может быть условным экстремумом, то есть решением исходной задачи. Заметим, что это условие носит необходимый, но не достаточный характер.

45. Решение оптимизационных задач в Excel с использованием настройки Поиск решения

Для решения оптимизационных задач в Excel предназначена надстройка «Поиск решения».

Средство поиска решения Microsoft Excel использует алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2). Поиск решений является частью блока задач, который иногда называют анализ "что - если". Процедура поиска решения позволяет найти оптимальное значение формулы содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки.

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

Для решения общей оптимизационной задачи в Excel с использованием настройки Поиск решения следует выполнить следующие действия:

• Ввести формулу для целевой функции;

• Ввести формулы для ограниченй оптимизационной задачи;

• Выбрать в Excel пункт меню Сервис/Поиск решения;

• В окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения;

• Нажать кнопку Выполнить, после чего будет получено решение оптимизационной задачи.

Программа Поиск решений – дополнительная надстройка табличного процессора MS Excel, которая предна-значена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации.