Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях

Подождите немного. Документ загружается.

каждый элемент ). Тогда еще одна фундаментальная концепция, используемая в методе

Данцига-Вулфа, заключается в том, что любая точка множества может быть представлена

в виде

(6.12)

где (6.13)

а - вершины (крайние точки) множества .

Мы можем, следовательно, переформулировать исходную задачу (6.9)-(6.11) в виде: из всех

ешений, определяемых соотношениями (6.11), найти те, которые удовлетворяют уравнению

(6.10) и максимизируют .

Используя равенство (6.12) , выражение (6.9) преобразуем к виду:

максимизировать , (6.14)

а уравнение (6.10) к виду

(6.15)

Если мы определим

и ,

тогда выражения (6.12)-(6.15) определят задачу линейного программирования относительно

переменных , называемую

координирующей задачей

максимизировать (6.16)

словиях

(

6.17

)

(6.18)

Отметим, что эта задача имеет только , строк, в то время как исходная задача имела

строк; таким образом мы получаем значительную потенциальную экономию.

Назначение координирующей задачи - приписать соответствующие весовые коэффициенты

решениям , удовлетворяющим соотношениям (6.11).

Однако число столбцов координирующей задачи равно числу вершин множества , k =

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

используем метод генерации столбцов, создавая их по мере необходимости.

Предположим, что решая координирующую задачу, мы вычислили вектор оценок

ограничений и теперь нам нужен небазисный столбец для вычисления его относительной

оценки.

Относительная оценка небазисного столбца, соответствующего переменной ,равна

Разбив вектор на части , отвечающие уравнениям (6.11), мы можем представить

в виде:

Поиск наиболее отрицательной относительной оценки эквивалентен решению задачи

линейного программирования, называемой

k-й подзадачей

максимизировать (6.19)

при условиях (6.20)

Решение, которое обозначим через , будет крайней точкой множества и будет

соответствовать наиболее отрицательной относительной оценке. Таким образом, мы

сгенерируем требуемый столбец

который теперь можно ввести в базис координирующей задачи, а соответствующий

коэффициент целевой функции определим по формуле .

Этот процесс повторяется для всех k=1,...,t, и решение, соответствующее наиболее

отрицательной относительной оценке среди всех

подзадач, определяет столбец для ввода в

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

вычислению нового вектора относительных оценок на следующей итерации.

В качестве альтернатив решению каждой подзадачи в отдельности можно осуществлять

агрегирование, определив

Тогда координирующая задача будет иметь строк вместо и только одну

подзадачу:

максимизировать (6.21)

при условиях (6.22)

Эта задача может быть решена решением

индивидуальных подзадач с последующим

агрегированием их решений.

Преимущество первого варианта решения задачи (6.16)-(6.18) -

его гибкость; плата за эту

гибкость - лишние (t-1) строк в координирующей задаче.

Существующие вычислительные алгоритмы решения задач нелинейного программирования

можно подразделить на следующие группы:

1. Применение аппарата линейного программирования для задач нелинейного

программирования путем использования процедуры последовательной линейной

аппроксимации [233]. Применяются также методы квадратичной аппроксимации [122] с

ешением на каждом шаге задачи квадратичного программирования.

2. Декомпозиция задачи нелинейного программирования с ограничениями в эквивалентную

ей последовательность простых задач (например, безусловной оптимизации) путем введения в

ассмотрение штрафных функций и т.д. [233].

3. Применение интервальной и нечеткой арифметики, позволяющей оперировать в процессе

ешения задач оптимизации с областями допустимых и нечетких решений (с изменяющейся

степенью допустимости решения) [134, 166].

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

их последовательной об

аботкой по отдельным

ур

авнениям и пе

еменным.

Описание, потенциальные возможности и сравнительный анализ ряда существующих методов

и пакетов программ для ЭВМ по решению задач нелинейного программирования приведены в

аботах [233, 280]. Сравнительный анализ и рекомендации по условиям применимости этих

пакетов сделаны с учетом следующих характеристик: точность, быстродействие, сходимость,

азмерность решаемых задач, эффективность работы, ограничение на число переменных и

ограничений, наличие сервисных средств (ввода описаний, редактирования, использования

отображения в графической форме процесса сходимости и т.д.) [280].

Методы линейной аппроксимации

. Наличие ППП для решения задач линейного

программирования большой размерности при наличии ограничений-равенств и ограничений-

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

нелинейного программирования с помощью процедуры линеаризации с применением

итерационного процесса. В этом случае задача нелинейного программирования в общей

постановке

, (6.23)

при ограничениях

; (6.24)

; (6.25)

может быть модифицирована путем записи каждой из нелинейных функций этой задачи

двумя первыми числами в соответствующем разложении в ряд Тейлора в окрестности и

сведена к задаче линейного программирования:

; (6.26)

при ограничениях

; (6.27)

. (6.28)

Сходимость этих методов к решению гарантируется, если [40]:

вляются непрерывными и дифференцируемыми

функциями;

2) функция выпуклая, а выпуклая в допустимой области D;

3) представляют собой вогнутые функции;

)

множество D замкн

тое, вып

клое и неп

стое;

5) все фигурирующие в условиях функции ограничены.

При отсутствии выполнения условий 1-5 алгоритмы, использующие методы линейной

аппроксимации, позволяют найти локальный оптимум.

Задача линейного программирования (ЛП) с целью координации решений и учета допущений

дополняется условием, ограничивающим длину шага при перемещении в том или ином

направлении малой величиной

. (6.29)

Полученное решение задачи (6.26)-(6.28) дает возможность вычислить следующую точку

. (6.30)

Повторением приведенной выше процедуры при постепенном уменьшении достигают

такой ситуации, когда минимизирующая поправка к найденному на предыдущем шаге

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

вектор оказывается вне пределов допустимой области D, вводятся искусственные

переменные , добавляемые в ограничения равенства и неравенства.

Принадлежащий к этому классу алгоритмов метод обобщенного приведенного градиента

(GRG) применяется в алгоритмах оптимизации работы газопровода [146]. В качестве

достоинств этого метода отмечаются:

простота формулировки целевой функции для трубопровода как функции независимых

и зависимых переменных;

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

местами зависимых и независимых переменных;

устойчивость алгоритма к нарушению исходных предпосылок и его надежность;

оптимальные решения находятся даже при больших интервалах задания начальных

условий.

Однако этот метод успешно применяется только при решении задач с непрерывной и

дифференцируемой по управляющим переменным функцией цели, когда параметры в задаче

имеют непрерывные диапазоны.

Когда управляющие или координирующие параметры имеют дискретные значения

(например, при выборе схемы включения ГПА на КС)

используются другие методы,

например, динамическое программирование [53, 146]. Декомпозиция задач позволяет

использовать при решении каждой локальной задачи тот метод, который наиболее

эффективен для данной ситуации. Так в работе [146] для оптимизации режима работы

газопровода в целом используется метод ПКП, а для оптимизации режима работы КС -

динамическое п

ог

амми

ование.

Декомпозиционные методы

ринцип параметрической декомпозиции

. Производится фиксация r параметров

и решается основная задача (6.23)

(6.31)

, (6.32)

азмерность которой сокращается на r [90]. В результате решения этой задачи линейного

программирования находятся базисные, небазисные переменные и двойственные оценки

для ограничений (6.31). После этого решается вторая задача

(6.33)

при ограничениях

; (6.34)

Все небазисные переменные в (6.34), найденные при решении задачи (6.31)-(6.32)

приравниваются нулю, осуществляется линейная аппроксимация ограничений (6.34) (иногд

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

[90]). Решение задачи (6.33)-(6.34) используется для нахождения нового решения задачи

(6.31)-(6.32) и процедура повторяется , пока не будет достигнута заданная точность решения.

Одним из примеров интерактивной оптимизации является метод крупноформатных

электронных таблиц (КЭТ) [226], который представляет собой выгодную альтернативу

алгоритмам линейного программирования.

Проведение

структурной декомпозиции

исходной задачи путем линеаризации исходной

модели позволяет использовать новый класс моделей - линейных моделей с переменными

коэффициентами.

Применение этих моделей дает возможность решить задачу следующего вида [90]:

;

(

6.35

)

;

. (6.36)

где - заданные функции управлений .

Такую модель можно записать, когда работа каждого элемента описывается линейной

моделью с переменными коэффициентами вида

(6.37)

. (6.38)

Модели элементов (агрегатов) вида (6.37)-(6.38) имеют широкую область применения в

нефтехимии [90], электроэнергетике и т.д. Модель отдельного элемента (агрегата) можно

ассматривать как результат линеаризации нелинейной модели

(6.39)

по входным параметрам , например, путем разложения функции в ряд

Тейлора в окрестности некоторого значения входных параметров и пренебрегая в этом

азложении членами второго порядка и выше [90].

Для аппроксимации производственных возможностей агрегатов, допускающих различные

ежимы работы внутри интервала , используется понятие граничного режима [90].

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

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

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

значений с использованием принципа параметрической декомпозиции можно получить

последовательность оптимальных значений функционала F и затем выбрать решение, дающее

наименьшее значение F.

Иногда для моделирования сложных процессов применяются

диапазонные модели

вида [90]

; (6.40)

;

где - векто

ы; - мат

ицы коэ

фф

ициентов; - векто

ы входных и выходных

потоков объекта; - вектор переменных, обеспечивающих диапазонную зависимость

выходов и входов.

Сведение задач к стандартным задачам по решению систем линейных уравнений, линейного

программирования позволяет воспользоваться хорошо разработанными стандартными

алгоритмами и программами [153, 193, 224], для которых определены условия существования

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

задач даны в работе [193].

В качестве численных методов решения системы алгебраических уравнений вида

(6.41)

применяются метод Ньютона-Рафсона и алгоритмы работы с симметричными разреженными

матрицами - метод -факторизации и метод автоматической перенумерации узлов [175,

177]. Метод перенумерации узлов обеспечивает минимум ширины ленты матрицы , а метод

-факторизации - возможность представления матрицы в виде

. (6.42)

Тогда (6.41) может быть записано в виде

; (6.43)

. (6.44)

Сначала решается уравнение (6.43) относительно , затем (6.44) относительно [98].

Имеются также методы параллельного решения на N процессорах систем линейных

алгебраических уравнений [167].

В случае наличия ошибок замеров параметров в уравнении (6.41) вместо истинных

параметров могут замеряться искаженные ошибками значения . То есть, возникает

необходимость найти последовательность решений , сходящуюся к истинному решению

, на основе последовательности , сходящейся к истинным данным . Однако решения

в этом случае будут неустойчивыми, так как обратный оператор в общем случае не

ограничен (а иногда может не существовать).

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

значительным отклонениям в решении, эта задача относится к классу некорректных задач [81,

138, 165].

Основными методами решения некорректных задач являются [81]:

метод регуляризации А.Н.Тихонова;

метод статистической

ег

ля

изации;

прямые и итерационные методы.

Рассмотрим регуляризацию функционала

, (6.45)

где Е и Х - пространства данных и решений соответственно.

Тогда согласно теореме, доказанной в [302], если сходится к в Е, а последовательность

положительных чисел выбрана так, что

при ,

существует последовательность ( выпуклое замкнутое подмножество Х)

такая, что

а) , (6.46)

б) сильно сходится к в Х.

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

систем. В этом случае задача идентификации будет трактоваться как задача оптимизации

некоторых квадратичных функционалов [302].

Задача вида (6.45) может быть использована и для идентификации параметров моделей. В

этом случае вместо записывается выражение для оцениваемых параметров

L. Задача оценивания может быть поставлена и для более сложного случая

, когда

- то есть, одновременно необходимо и оценивать параметры состояния и уточнять

коэффициенты моделей . В этом случае задача оценивания может быть сведена к

определению значений и в двухэтапной задаче оптимизации [326]

, (6.47)

при условиях, определяемых системой уравнений (6.46).

Для определения параметра регуляризации

используется целый ряд методов [165]. Они

основаны на оценивании параметра регуляризации

из дополнительного условия

, (6.48)

где

- нелинейный

фу

нкционал, оп

еделенный на

ешениях задачи

(

6.45

)

, а -ап

ио

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

В работе [352] рассмотрены три способа выбора параметров регуляризации :

(принцип невязки) (6.49)

(принцип квазирешений) (6.50)

(6.51)

(принцип сглаживающего функционала).

Величина характеризует задаваемый уровень невязки и определяется по методу невязки.

Величина связана с априорными сведениями о размере области, в которой находится

искомое решение, и определяется методом квазирешений. Величина практически

выбирается из тех же соображений , что и .

Если , , принадлежат множествам значений функций

, то уравнения (6.49)-

(6.51) однозначно разрешимы [165].

Это связано с тем , что функции , и непрерывны при , причем и

строго монотонно возрастают , а строго монотонно убывает. В той же работе

приводятся модификации этих уравнений, к которым применимы быстро сходящиеся

алгоритмы ньютоновского типа.

Из детерминированных методов неплохо зарекомендовал себя при

параметрической

идентификации

метод наименьших квадратов с использованием теории чувствительности

[108], который заключается в определении отклонения фактических параметров

от их номинальных значений в предположении, что величина является малой. Для

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

моделей такое предположение является естественным ввиду монотонного характера

изменения коэффициентов эффективности для линейных участков (ЛУ) и незначительного

изменения потоков газа в магистральных газотранспортных сетях между проводимыми

часовыми и суточными расчетами.

Однако из-за некорректности задачи (замеры давления имеются не во всех вершинах сети)

осуществляется минимизация функционала J вида (6.45) с регуляризующей добавкой.

Переменные в условиях малых отклонений от номинальных могут быть

едставлены п

иближенно в виде