Методы учета ограничений в задачах нелинейного программирования

Страницы работы

9 страниц (Word-файл)

Содержание работы

Лабораторная работа №3

Содержание:

  • Общие сведения
  • Учет ограничений в форме равенств
    • Метод прямой оптимизации
    • Метод приведенного градиента
    • Метод множителей Лагранжа
  • Учет ограничений в форме неравенств
    • Теорема Куна-Такера
    • Метод штрафных функций
  • Программное обеспечение
  • Порядок выполнения работы
  • Контрольные вопросы

МЕТОДЫ УЧЕТА ОГРАНИЧЕНИЙ В ЗАДАЧАХ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Цель работы: изучение и исследование методов учета ограничений в форме равенств и неравенств в задачах нелинейного программирования.

Общие сведения

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

http://esls.susu.ac.ru/download/ACS/labs/lab_3_1.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_2.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_3.gif

где X = (X1,X2,...,Xn) - вектор неизвестных, G(Х)={g1(X),g2(X),...,gm(X)}-вектор-функция ограничений.

Подобные математические модели применяются довольно часто.

Рассмотрим лишь два примера из области энергетики.

1. Оптимизация распределения нагрузки между ТЭС.

Критерием является минимум расхода топлива на всех n ТЭС системы. В качестве неизвестных принимаются мощности Рi ТЭС, образующие вектор Р. Ограничения определяются балансом мощностей в системе без учета или с учетом потерь в сети и рабочим диапазоном мощностей при заданном составе работающего оборудования ТЭС.

Математическая модель имеет вид:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_4.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_5.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_6.gif

Вi(Pi)– расходные характеристики ТЭС, http://esls.susu.ac.ru/download/ACS/labs/lab_3_7.gif(P)– функция потерь в сети, Pн – суммарная нагрузка системы, Pimax– предельно-допустимая мощность i-ой ТЭС.

2. Выбор схемы развития сети.

Критерием выбора является минимум затрат на сооружение ЛЭП. Вектор неизвестных P включает потоки Ps по ветвям расчетного графа сети, имеющего избыточные ветви. Вектор-функция ограничений учитывает балансы в узлах сети.

Математическая модель:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_8.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_9.gif

где http://esls.susu.ac.ru/download/ACS/labs/lab_3_10.gif– функция затрат в ветвь s,M– матрица инциденций узлы-ветви, Рвн – вектор узловых мощностей.

вернуться к началу

1. Учет ограничений в форме равенств.

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

http://esls.susu.ac.ru/download/ACS/labs/lab_3_2.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_11.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_12.gif

где X=(X1,X2,...,Xn) - вектор неизвестных, G(Х)={g1(X),g2(X),...,gm(X)}– вектор-функция ограничений типа gi(X)=0.

вернуться к началу

1.1. Метод прямой оптимизации.

В этом методе вектор-функцию G(X)=0 рассматривают как систему из m уравнений для n неизвестных при m<n. Такая система уравнений имеет множество решений, найти которое можно выразив m неизвестных из вектора X через остальные k=n-m переменных.

Первые m переменных назовем зависимыми и обозначим через Y, за вторыми k-независимыми сохраним обозначение Х.

Функциональный вид Y(Х) определяется системой G(X)=0. С учетом зависимости Y(Х) и целевую функцию можно преобразовать к новому виду

http://esls.susu.ac.ru/download/ACS/labs/lab_3_13.gif

и найти любым методом безусловной оптимизации такие значения независимых Х=(x1,x2,..,xk), которые отвечают минимуму F(Х). По найденным Х определяются и остальные переменные Y(Х).

Рассмотрим пример оптимизации режима работы 3-x ТЭС на общую нагрузку, равную 100 МВт. Расходные характеристики ТЭС заданы аналитически в виде:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_14.gif

Математическая модель:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_15.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_16.gif

Таким образом, имеем систему ограничений, для которой m =1, n =3, k=n-m=2. В качестве независимых примем Р1 и Р2. Тогда зависимые Р3=100–Р–Р2; и

http://esls.susu.ac.ru/download/ACS/labs/lab_3_17.gif

Решая градиентным методом, получаем Р1=23 МВт, Р2=31 МВт. Зависимая переменная Р3=100–Р1–Р2=46 МВт. Оптимальный расход топлива составляет 67.0 тут.

вернуться к началу

1.2. Метод приведенного градиента.

Метод прямой оптимизации применим, когда удается решением системы G(X)=G(Y,Х)=0 найти аналитическую зависимость Y(Х). Однако часто вектор-функция G(X) нелинейна и решение можно получить только численными методами.

Рассмотрим такой случай:

F(Y,Х) = min, G(Y,Х) = 0 , где Y,Х –подмножества зависимых и независимых переменных исходного вектора X.

При бесконечно малых приращениях составляющих векторов Х и Y имеем:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_18.gif

Кроме того для вектор-функции запишем

http://esls.susu.ac.ru/download/ACS/labs/lab_3_19.gif

Здесь все производные берутся с учетом явной зависимости от Y и Х.

Решим последнее уравнение относительно dY и, подставив в приращение функции dF, получим:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_20.gif

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

http://esls.susu.ac.ru/download/ACS/labs/lab_3_21.gif

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

http://esls.susu.ac.ru/download/ACS/labs/lab_3_22.gif

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

вернуться к началу

Метод множителей Лагранжа

Рассмотрим вновь задачу http://esls.susu.ac.ru/download/ACS/labs/lab_3_2.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_11.gif

Решение ее лежит в точке, где приведенный градиент равен нулю

http://esls.susu.ac.ru/download/ACS/labs/lab_3_23.gif

Обозначим часть вычитаемого через U

http://esls.susu.ac.ru/download/ACS/labs/lab_3_24.gif

С учетом этого предыдущее условие можно записать в виде эквивалентной системы уравнений:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_25.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_26.gif

Полученная система соответствует условию минимума некоторой функции, называемой функцией Лагранжа,

http://esls.susu.ac.ru/download/ACS/labs/lab_3_27.gif

где U – вектор множителей Лагранжа.

Оказывается, функцию Лагранжа можно составить для исходной задачи без разделения вектора X на зависимые Y и независимые Х подмножества:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_28.gif

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

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

В практических задачах оптимизации метод имеет ограниченное применение. Однако он широко используется при теоретическом анализе и в инженерных методах оптимизации в энергетике.

Рассмотрим ,например, задачу распределения нагрузки между ТЭС в системе, математическая модель которой была ранее составлена:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_15.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_16.gif

Запишем функцию Лагранжа

http://esls.susu.ac.ru/download/ACS/labs/lab_3_29.gif

и условия минимума ее:

http://esls.susu.ac.ru/download/ACS/labs/lab_3_30.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_31.gif

http://esls.susu.ac.ru/download/ACS/labs/lab_3_32.gifhttp://esls.susu.ac.ru/download/ACS/labs/lab_3_33.gif

Решение этой системы: u=0.92, Р1=23, Р2=31, Р3=46.

Похожие материалы

Информация о работе

Тип:
Отчеты по лабораторным работам
Размер файла:
127 Kb
Скачали:
0