Метод целевого программирования

Целевое программирование

Постановка задачи

Целевое программирование (ЦП) — это относительно новая концепция, развивающая идеи линейного программирования (ЛП) и призванная помочь в разработке управленческих решений в условиях многих целей. Как известно, одним из условий, при которых задача оптимального планирования может быть сформулирована и решена в рамках ЛП является наличие единого, четко сформулированного и количественно определенного критерия оптимальности плана в виде целевой функции. Обычно это минимум затрат или максимум прибыли. Но практика хозяйственной деятельности показывает, что это не единственные, а порой и не самые главные цели, которые приходится ставить и решать, планируя работу на перспективу. В ЛП предусматривается возможность объединения нескольких целей в одну, но в этом случае цели должны измеряться в одних и тех же единицах ( например, в рублях). В реальной жизни цели настолько разнообразны, а порой и противоречивы, что свести их в одну не всегда представляется возможным. Это цели и престижа фирмы, и охраны окружающей среды, и налаживания международных связей, и организация грамотной логистики и грузоперевозок, и поддержания определенного социально-психологического климата в коллективе и т.д., которые и в отдельности измерить не просто.

Одним из возможных направлений реализации подобного рода задач и явилась разработка в начале 60-х годов идей целевого программирования.

Ясно, что в условиях многих целей и ограниченности ресурсов не все цели могут быть достигнуты. В ЦП предусматривается такая возможность и для ее отражения вводится новый тип переменных, показывающий степень отклонения достигнутого уровня целей от желаемого (запланированного). Такие переменные будем называть отклонениями. Не следует смешивать их с балансовыми переменными, рассматриваемыми в ЛП. Балансовые переменные в ЛП показывают, на сколько правая часть ограничения отличается от левой, а переменные-отклонения в ЦП -степень недо- или перевыполнения конкретной цели. Кроме этих особенностей ЛП И ЦП отличаются конструкцией целевых функций. Если в ЛП непосредственно максимизируется или минимизируется одна конкретная цель, то в ЦП минимизируются отклонения между желаемыми и достигнутыми в пределах ограничений по ресурсам уровнями многих целей. Отсюда и роль отклонений. Если в ЛП балансовые переменные являются вспомогательными, то в ЦП отклонения играют решающую роль и формируют целевую функцию.

В условиях многих целей, их сложности и противоречивости, а так же ограниченности ресурсов, одни цели могут быть достигнуты за счет других. А это приводит к необходимости установления определенной иерархии целей так, чтобы цели нижнего приоритета выполнялись бы при условии реализации целей высшего приоритета. А поскольку возможна ситуация, когда не все цели могут быть достигнуты, то ЦП реализует алгоритм достижения возможного (удовлетворительного) уровня многих целей. Этим оно отличается от ЛП, в котором получают оптимальное решение для одной цели.

Для установления приоритетности целей, отклонения в целевой функции ЦП взвешиваются при помощи специальных коэффициентов. Каждая цель формируется при помощи целевого ограничения, включающего отклонения от этой цели. Кроме целевых ограничений, модель задачи ЦП может содержать обычные, системные ограничения. Поскольку отклонения от цели могут быть двоякими, то для каждой цели обычно вводят по две отклоняющих переменных, показывающих недо- и перевыполнение цели (обозначаются d- и d+).

Как уже отмечалось, будучи сформулированной, задача ЦП может быть решена методами, используемыми идеей ЛП. Не следует задачи ЦП отождествлять с многокритериальными задачами или с задачами векторной оптимизации. Это особые разделы математического программирования, которые здесь не рассматриваются.

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

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

1. Получить не менее 30 ед. прибыли.

2. По возможности максимально использовать ресурс 1 вида.

3. Желательно не перерасходовать ресурс 2 вида.

4. Обеспечить контрактную поставку продукции 2 вида не менее 7 единиц.

Для формулировки модели задачи предположим, что прибыль от реализации единицы продукции равна соответственно 7 и 6 единиц, расход 1ресурса на выпуск единицы каждого продукта равен 2 и 3 единицы, соответственно, а объем 1 ресурса равен 12 единиц. Для 2 ресурса соответственно 6 и 5, и 30 единиц.

Составим модель задачи ЦП.

Основные неизвестные модели: Хi — объем производства продукции 1 вида; X2 — второго.

По прибыли: 7x₁+6x₂+d₁ — -d1 + =30 слева записан объем прибыли с учетом недовыполнения 1-й цели (d1-) или ее перевыполнения (d1+ ). Если цель будет недовыполнена, то величина недовыполнения (d1-) будет больше нуля (d₁ — >0) а перевыполнения (d1+) равна нулю (d1- = 0). И наоборот, в случае перевыполнения цели d₁ + >0, a d₁ — =0.

Если цель будет выполнена в точности, то d1+ = d1- = 0. В любом случае, по крайней мере одна из этих переменных будет равна нулю. Поскольку первая по приоритетности цель предусматривает получение не менее 30 ед.прибыли. то в целевой функции будем минимизировать недовыполнение, т.е. для этой цели, Z = P1d1-, где Р1 — весовой коэффициент.

соответственно недо- и перевыполнение 2-й цели. Для максимизации использования 1-го вида ресурса будем минимизировать d2-, следовательно, на этом этапе Z=P₁d₁ — +P₂d₂, причем P₁>>P₂ (P₁ много больше P₂).

Для реализации 4-й цели необходимо произвести продукции 2-го вида не менее 7 ед_. следовательно, целевое ограничение примет вид: x₂+d₁ — -d₁ + =7, а целевая функция: Z = P₁d — + P₂d₂ — + P₃d₃ + + P₄d₄ —

Геометрическая интерпретация и графическое решение задач линейного программирования.

Целевое программирование. Метод весовых коэффициентов.

11. Целевое программирование. Метод приоритетов.

Задачи линейного программирования. Ограничения и дополнительные переменные. Стандартная форма задачи ЛП и ее базисные решения.

Основная теорема двойственности линейного программирования

Пусть рассматривается пара двойственных задач:

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

Решение транспортной задачи методом потенциалов

Сепарабельное программирование.

Целевое программирование. Метод весовых коэффициентов.

11. Целевое программирование. Метод приоритетов.

Задачи линейного программирования. Ограничения и дополнительные переменные. Стандартная форма задачи ЛП и ее базисные решения.

Геометрическая интерпретация и графическое решение задач линейного программирования.

15. Симплекс-метод решения задач линейного программирования. Алгоритм симплекс-метода (Метод Гаусса-Жордана).

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

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

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

Алгоритм:
Шаг 0. Составление исходной симплекс таблицы.
Шаг 1. Находится начальное допустимое базисное решение.
Шаг 2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.
Шаг 3. На основе условия допустимости выбирается исключаемая переменная.
Шаг 4. Методом Гаусса–Жордана вычисляется новое базисное решение. Переход к шагу 2.

Условие оптимальности. Вводимой переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая наибольший отрицательный (положительный) коэффициент в z – строке. Если в z – строке есть несколько таких коэффициентов, то выбор вводимой переменной делается произвольно. Оптимальное решение достигнуто тогда, когда в z – строке все коэффициенты при небазисных переменных будут неотрицательными (неположительными)

Условие допустимости. Как в задаче максимизации, так и в задаче минимизации, в качестве исключаемой выбирается базисная переменная, для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если базисных переменных с таким свойством несколько, то выбор исключаемой переменной выполняется произвольно. Вычисление нового базисного решения основывается на методе исключения переменных (методе Гаусса–Жордана).

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

16. Искусственное начальное решение. М-метод. Двухэтапный метод.
Искусственное начальное решение.
В простом симплексе при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми.
В задачах линейного программирования, где все ограничения являются неравенствами типа « =» ?

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

Для объяснения двухэтапного метода объясним сначала концепцию М-метода.

Пусть задача ЛП записана в стандартной форме. Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введём искусственную переменную Ri, которая далее войдёт в начальное базисное решение. Но поскольку эта переменная искусственна (другими словами, не имеет никакого «физического смысла» в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

Переменная Ri, с помощью достаточно большого положительного числа М, штрафуется путём ввода в целевую функцию выражения –MRi в случае максимизации целевой функции и выражения +MRi – в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведёт к нулевому значению переменной Ri.

При использовании М-метода следует обратить внимание на следующие два обстоятельства.
1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это «индикатор» того, что задача не имеет допустимого решения.

2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой.

Алгоритм двухэтапного метода.
Двухэтапный метод полностью лишён тех недостатков, которые присущи М-методу. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведётся поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.

Этап 1. Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные (как и в М-методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями (r=R1+R2+…Rk). Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. (Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.

Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.

17. Двойственная задача. Принцип построения. Соотношения двойственности.
Исходную задачу линейного программирования будем называть прямой. Двойственная задача — это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи.

Пример задачи целевого программирования;

Постановка задачи целевого программирования

Задания для самостоятельной работы

Решить задачу для самостоятельной работы из п. 6.9 с помощью Excel.

Результаты работы необходимо оформить в виде отчета, который должен содержать:

1. Описание проблемы принятия решения;

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

3. Результаты решения задачи с помощью Excel, в т.ч. итоговую таблицу с оптимальным решением (указать имя файла Excel);

4. Сеть с оптимальным планом транспортировки.

ТЕМА 8. Целевое программирование

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

В методе весовых коэффициентов единственная целевая функция формируется как взвешенная сумма исходных частных целевых функций.

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

Рассмотрим основные этапы решения на следующем примере.

Новое рекламное агентство Simpson & Son, в составе которого 10 рекламных агентов, получило контракт на рекламу нового продукта. Агентство может провести рекламную акцию на радио и телевидении. В таблице (см. Табл. 1) приведены данные об аудитории, охватываемой каждым видом рекламы, стоимость этой рекламы и количество необходимых рекламных агентов. Все данные относятся к одной минуте рекламного времени.

Табл. 46 Данные рекламного агентства Simpson & Son

Реклама на радио и телевидении должна охватить не менее 45 миллионов человек, но контракт запрещает использовать более 6 минут рекламы на радио. Рекламное агентство может выделить на этот проект бюджет, не превышающий $100 000. Как наилучшим образом агентству спланировать рекламную акцию?

Обозначим через и количество минут рекламного времени, закупленного соответственно на радио и телевидении.

Математическая модель проблемы имеет вид

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

1. Минимизировать недостаток рекламной аудитории;

2. Минимизировать перерасход бюджета.

Нетрудно убедиться, что у этой задачи ЛП нет допустимого решения.

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

В нашем случае в первое и второе неравенства (соответствующие целям) введем по две дополнительных переменных. Обозначим их через для первой цели и — для второй. Запишем с их помощью наши целевые ограничения. Математическая модель принимает вид:

Переменная равна значению недостатка аудитории до 45 миллионов, а — избытку (превышению) аудитории над 45 миллионами. Так, если и , то обеспечивается аудитория в 44 миллиона человек, т.е. и общие расходы равны 99,5 тысяч долларов, т.е. . Аналогично и для переменных .

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

С помощью введенных переменных отклонения можно записать частные целевые функции:

1. Минимизировать (для выполнения условий по рекламной аудитории);

2. Минимизировать (для выполнения условий по бюджету).

Графический метод оптимизации линейных моделей

Цель лекции: Показать возможность графического решения задач с двумя неизвестными.

Математическое программирование занимается исследованием детерминированных и одноцелевых задач. Слово » программирование » в данном случае означает «планирование». К математическому программированию относится:

1. Линейное программирование: нахождение экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные.
2. Нелинейное программирование:целевая функция и ограничения могут быть нелинейными функциями.
3. Целочисленное программирование: особый случай в задачах линейного и нелинейного программирования, когда на оптимальные решения накладывается условие целочисленности искомых параметров.
4. Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом.
5. Теория графов, с помощью которой решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д.

Математическая модель любой задачи линейного программирования включает в себя:

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

Решение практической задачи всегда связано с исследованием, с преобразованием некоторого объекта (материального или информационного) или с управлением им (рисунок 1.1).

При решении «стандартной» задачи в линейном программировании нужно определить максимум линейной целевой функции

Здесь целевая функция формируется как скалярное произведение двух векторов. Один из них — вектор искомых переменных . Компонентами другого вектора являются целевые коэффициенты . Условия задачи можно сформулировать так: «Расход не должен превышать имеющиеся ресурсы «. Вектор расхода есть сумма произведений матрицы нормированных коэффициентов на вектор искомых переменных .

Основной аналитический метод решения задач линейного программирования — это симплексный метод . Он сводится к вычислительной процедуре, основанной на принципе последовательного улучшения решений — перехода от одной базисной точки к другой, для которой значение целевой функции больше. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса (n-мерного тетраэдра). Симплекс -метод послужил исходным пунктом для разработки целого семейства алгоритмов решения как линейных, так и нелинейных выпуклых задач оптимизации.

Документация

Многоцелевые алгоритмы оптимизации

Многоцелевое определение оптимизации

Существует два Optimization Toolbox™ многоцелевые решатели: fgoalattain и fminimax .

fgoalattain решает проблему сокращения набора нелинейных функций _Fi (x) ниже набора целей _F*i. С тех пор существует несколько функций _Fi (x), не всегда ясно, что это означает решать эту проблему, особенно когда вы не можете достигнуть всех целей одновременно. Поэтому проблема повторно формулируется к той, которая всегда четко определена.

unscaled goal attainment problem должен минимизировать максимум _Fi (x) – _F*i .

Существует полезное обобщение немасштабированной проблемы. Учитывая набор положительных весов _wi, goal attainment problem пытается найти, что x минимизирует максимум

Эта минимизация, как предполагается, выполняется при удовлетворении всех типов ограничений: c (x) ≤ 0, ceq (x) = 0, A·x ≤ b, Aeq·x = beq и l ≤ x ≤ u .

Если вы устанавливаете все веса, равные 1 (или любая другая положительная константа), целевая проблема достижения совпадает с немасштабированной целевой проблемой достижения. Если _F*i положителен, и вы устанавливаете все веса как _wi = _F*i , целевая проблема достижения становится минимизацией относительной разницы между функциями _Fi (x) и цели _F*i.

Другими словами, целевая проблема достижения состоит в том, чтобы минимизировать слабую переменную γ, заданную как максимум по i выражений в уравнении 1. Это подразумевает выражение, которое является формальным оператором целевой проблемы достижения:

fminimax решает проблему минимизации максимума набора нелинейных функций согласно всем типам ограничений:

min x max i F i ( x )

Безусловно, этой проблемой является особый случай немасштабированной целевой проблемы достижения с _F*i = 0 и _wi = 1 .

Алгоритмы

Целевой метод достижения

В этом разделе описываются целевой метод достижения Gembicki [3]. Этот метод использует набор целей проекта, F * = < F 1 * , F 2 * , . , F m * >, сопоставленный с набором целей, F (x) = <F ₁ (x), F ₂ (x). _Fm (x)> . Проблемная формулировка позволяет целям быть под — или сверхдостигнута, позволяя разработчику быть относительно неточной о начальных целях проекта. Относительной степенью под — или сверхдостижение целей управляет вектор взвешивания коэффициентов, w = <w ₁, w ₂. _wm> , и выражают как стандартная задача оптимизации с помощью формулировки

таким образом, что F i ( x ) − w i γ ≤ F i * , i = 1 , . , m .

Термин _wiγ вводит элемент застоя в проблему, которая в противном случае налагает, что целям твердо удовлетворяют. Вектор взвешивания, w, позволяет разработчику выразить меру относительных компромиссов между целями. Например, установка взвешивающего векторного w, равного начальным целям, указывает, что тот же процент под — или сверхдостижение целей, F*, достигается. Можно включить трудные ограничения в проект путем обнуления особого фактора взвешивания (т.е. _wi = 0 ). Целевой метод достижения обеспечивает удобную интуитивную интерпретацию проблемы проектирования, которая является разрешимыми использующими стандартными процедурами оптимизации. Иллюстративные примеры использования целевого метода достижения в проекте системы управления могут быть найдены во фламандце ([10] и [11]).

Целевой метод достижения представлен геометрически в фигуре ниже в двух измерениях.

Рисунок 8-1, геометрическое представление целевого метода достижения

Спецификация целей, < F 1 * , F 2 * >, задает целевую точку, P. Вектор взвешивания задает направление поиска от P до выполнимого функционального пространства, Λ (γ) . Во время оптимизации варьируется γ, который изменяет размер выполнимой области. Ограничительные контуры сходятся к точке уникального решения F _1s, F _2s .

Улучшения алгоритма для целевого метода достижения

Целевой метод достижения имеет преимущество, что это может быть изложено как проблема нелинейного программирования. Характеристики проблемы могут также быть использованы в алгоритме нелинейного программирования. В последовательном квадратичном программировании (SQP) выбор оценочной функции для поиска строки не легок, потому что во многих случаях трудно “задать” относительную важность между улучшением целевой функции и сокращением ограничительных нарушений. Это привело ко многим различным схемам построения оценочной функции (см., например, Щиттковского [36]). В целевом достижении, программирующем может быть более соответствующая оценочная функция, которой можно достигнуть путем изложения уравнения 2 как минимаксная проблема

Λ i = F i ( x ) − F i * w i , i = 1 , . , m .

После аргумента Brayton и др. [1] для минимаксной оптимизации с помощью SQP, с помощью оценочной функции уравнения 30 для целевой проблемы достижения уравнения 3 дает

Когда оценочная функция уравнения 4 используется в качестве основания процедуры поиска строки, затем, несмотря на то, что ψ (x, γ) может уменьшиться для шага в данном поисковом направлении, функциональном max Λ_i может как это ни парадоксально увеличиться. Это принимает ухудшение в худшей цели случая. Поскольку худшая цель случая ответственна за значение целевой функции γ, это принимает шаг, который в конечном счете увеличивает целевую функцию, которая будет минимизирована. С другой стороны ψ (x, γ) может увеличиться когда max Уменьшения Λ_i, подразумевая отклонение шага, который улучшает худшую цель случая.

После строк Brayton и др. [1], решение состоит в том, чтобы поэтому установить ψ (x) , равный худшей цели случая, т.е.

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

Чтобы преодолеть эту проблему, все еще сохраняя функции уравнения 5, оценочная функция объединена с тем из уравнения 31, дав следующее:

Другой функцией, которая может быть использована в SQP, является целевая функция γ. От уравнений KKT можно показать, что приближение к Гессиану функции Лагранжа, H, должно иметь нули в строках и столбцах, сопоставленных с переменной γ. Однако это свойство не появляется, если H инициализируется как единичная матрица. H поэтому инициализируется и сохраняется, чтобы иметь нули в строках и столбцах, сопоставленных с γ.

Эти изменения делают Гессиан, H, неопределенный. Поэтому H будет иметь нули в строках и столбцах, сопоставленных с γ, за исключением диагонального элемента, который установлен в маленькое положительное число (например, 1e — 10). Это позволяет использование быстрого сходящегося положительного определенного метода QP, описанного в Решении для Квадратичного программирования.

Предыдущие модификации были реализованы в fgoalattain и, как находили, сделали метод более устойчивым. Однако из-за быстрой сходимости метода SQP, требование, чтобы оценочная функция строго уменьшалась иногда, требует большего количества функциональных оценок, чем реализация SQP использование оценочной функции уравнения 30.

Минимизация максимальной цели

fminimax использует целевой метод достижения. Это берет цели 0 и веса 1. С этой формулировкой целевая проблема достижения становится

min i max x ( f i ( x ) − g o a l i w e i g h t i ) = min i max x f i ( x ) ,

который является минимаксной проблемой.

Между прочим, вы можете ожидать fminimax превратить многоцелевую функцию в одну цель. Функция

Ссылки

[1] Brayton, R. K. S. W. Директор, Г. Д. Хэчтель, и Л.Видигэл, “Новый Алгоритм для Статистического Проектирования схем На основе Приближенных методов ньютона и Функционального Разделения”, Транзакции IEEE на Схемах и Системах, издании CAS-26, стр 784-794, сентябрь 1979.

[2] Фламандец, П.Дж. и А.П. Пашкевич, Компьютер помог Проекту Системы управления Используя Многоцелевой Подход Оптимизации, Управление 1 985 Конференций, Кембридж, Великобритания, стр 174-179.

[3] Gembicki, F.W., “Векторная оптимизация для управления с индексами производительности и чувствительности параметров”, диссертация доктора философии, случай западный резервный унив, Кливленд, OH, 1974.

[4] Изящество, A.C.W., “автоматизированный проект системы управления Используя методы оптимизации”, кандидатская диссертация, Уэльский университет, Бангор, Гвинед, Великобритания, 1989.

[5] Ханьцы, S.P., “Глобально Конвергентный Метод Для Нелинейного программирования”, Журнал Теории Оптимизации и Приложений, Издания 22, p. 297, 1977.

[6] Мэдсен, K. и Х. Шджэер-Джэйкобсен, “Алгоритмы для худшей оптимизации допуска случая”, сделка IEEE схем и систем, издания CAS-26, сентябрь 1979.