На олевущей итерации выберем систему направлений поиска
СГо) р(о) с'0) „fol Г,<о) "Л i °3 •> • • • 1 "1 , "2 - "/ •
Два последних из них являются сопряженными. Переоборначим эту систеглу направлений как 5м, S^,..., S^. Примем U^ •= U^ • Осуществим теперь минимизацию в направлении S^ , получив точку у^ , а затем серию минимизаций во всех п направлениях <>!11 ^i'1 > •••у •S'я ' Получим точку U1,11 • При этом в силу
теопезд 2 вектор и^-й^ будет сопряжен к двум направлениям
еа) p(i)
"п-1 " ^п • - , _,
Вкйирая на следующей итерации направление U.'^' - U11' .в качестве последнего направления поиска S^' и исключая из рассмотрения направление S^ = S^ , получаем после' переобозначения соответствующих векторов новую систему направлений поиска
С») рЛ) '^(f)
!>^ , ^i , ..., ->л .
В этой с с теме три последних вектора ^/^-r^^fi ^"являют-ся сопряженными.
Таки.т образом, производится поочередяая замена принятых вначале координатных направлений поиска на сопряженные направления. При этом на ( П -1)-й итерации будет получена система из П сой-' ряхенннх направлений, а на П -и итерации будет найден минимум i 1адратичисй формы.
Р заключение описания алгоритма сделаем следующие замечания.
1. Несмотря на то, что понятие сопряженных направлений определено только для квадратичной функпии, описанный алгоритм построен так, '.то его можно формально применять для произвольной |*-ункчии. Разумеется, при ртом для одномерной минимизации необхо-гп\'о аспрчьчовпть поисковые нетодн.
2. !'поле дуемая в работе программная реализация алгоритма оо-пглт-с'-]"!-? чпггз.члечий отличается рядом специальных усоверпенство-нр-ч"'"' ^ '.] , '^пчазчачечнмх для повышента сходимости &>ггоритма я, в "-1ст;'"^тч, ai". пчключечэд позкокности появления линейно-зависи-•ч./- 'пп;??'^"'"!" поиска.
3. В качестве алгоритма одномерной минимизации в программе использована процедура квадратичной интерполянии C.3,5J .
3. ПОРЯДОК ВЫП(Ж1И{ИЯ РАБОТЫ
"3.1. Расчетная часть
3.1.1. Построить графически линии равных значений целевой функции для трех вариантов исходных данных:
1) квадратичной формы вида (5) о хорошо обусловленной матрицей А ' •,
2) квадратичной формы вида (5) о плохо обусловленной матрицей' А ;
3) неквадратичной функции.
3.1.2. Опрецелить собственные значения матрицы А для ' первого и второго вариантов исходных даняьос.
3.1.3. Для первого варианта исходных данных построить гра- ' фически траекторию поиска методом покоординатного спуска.
3.1.4. Для второго варианта исходных данных построить аналитическое решение методом сопряженных направлений. Представить результаты этого решения графически.
3.1.5. Coo TaaHTbJ на языке Си подпрохрамну вычдслений заданной наквадратичааВ функции, оформив ее в вице процедуры.
3.2. Экспериментальная часть
3.2.1. Для первых двух вариантов исходных данных получить результаты машинного решения с помощью предлагаемых программ МПС и МСН, предназначенных для минимизации квадратичной формы.
3.2.2. Ввести в ЕВМ процедуру вычисления заданной неквадратичной функции, осуществить ее трансляцию и компоновку совместно о прелагаемой основной програктюй МСЯ.
3.2.3. Получить результаты машинного решения задачи минимизации заданной нёкэадратичной функции' с йэмощьи программы, обздаяиоУ в~п.3.2.2.
4. СОДЕРЖАНИЕ ОТЧЕТА ПО РАБОТЕ
1. Исходное задание на исследование.
2. Результаты, полученные впп.3.1.1 - 3.1.5 ракетной части.
3. Результаты машинного решения по пп.3.2.1 и 3.2.3, представленные в виде таблиц и траекторий поиска на графиках линий равных значений .целевой функции, предварительно построенннх в' п.3.1.1.
4. Анализ результатов экспериментального исследования и. сопоставление их с теоретическими результатами;
5.'Выводы по работе.
• 5. KOiITPOAWIB ВОПРОЯЦ
1. П чем суть iioHRKOBliX методов параметрической оптимизации?
2. Как работает МПС и какой основной его недостаток?
3. Какие теоремы лета т с основе МЛН?
4. Как осуществляется выбор н.чправлений поиска в МОН?
5. Выпишите чапгя.пления полек'1 дта ЖН в случае втанимизаипи F(U)=2U1 ^U^-UU,, начиная яз точки Z/^-г [З^]1'-
6. НнСдите направление, ортогональное вектору л г -f ^ i I7
_ ^-L^.-^'-^J
и точке U^Q,0,OY .
"fi" il:i re напра^.юние, сопряженное к S цля оелевой функ-:i:;ii F(U)s Ufi-.tU.^-UfU^ в то:1 же точке.
Библиографический опасок
I. Черенков i!.n. Введение в автоматизированное проек.тирова-•nie технических устройств и систем. ?.!.: Пысшая пжола, 1980. 200 с.
*. Ильин Н.Н. Ма"инное проектирование электронных схем. М.:
Глергия, [972. 270 о.
3. Хию.-ельблау Д. Прикладное нелинейное программирование. М.: :,?нр, T'^S. 534 с.
4. Чотееев Н.й., Иоани-.юв г).П., Столярова Е.М. Методы опти-мтаатп!. ?.1.: Наука, 1^Р. ЗЖ с. • .-.——— и. Каяиткин П.Н. Чясленнне методы. ' М.: Наука, 1978. .5120.
Лабораторная работа № 3
ИССЛЕДОВАНИЕ КОМБИНАТОРНОГО МЕТОДА. ВЕТВЕЙ И ГРАНИЦ
1. ЦЕЛЬ РАБОТЫ
Целью настоящей работы являются изучение и анализ метода ветвей и границ (МВГ), применяемого для решения задач дискретного программирования (ДД), к математическим моделям которых оводитоя большое число задач структурной оптимизации конструкций ЭВА. Исследование проводится на примере задачи выбора оптимальной совокупности конструктивных единиц.
2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ '
2.1. Метод ветвей и границ
Рассмотрим задачу ДП в следующей оощей форме: найти оптималь-"ное решение X*f б такое, что
J(^*)^mu,J(X), (^
J хе<г
где .7 - целевая, функция, ff - некоторое конечное мнскество допустимых вариантов решения.
; МВГ относится к числу комбинат арных методов, основанных на идее направленного перебора.вариантов. В его основе лежат следующие построения, позволяющие в ряде случаев существенно сократить объем перебсра.
Часто тем или иным опооооом, зависящим от конкретного содержания задачи, удается определить нижнюю границу целевой функции J(X.) на мнокестве допустимых решений G , т.е. найти такое число ^(ff), которое заведомо не больше, чем значение функции ^(Х) на любом допустимом решении.
Получение такого рода оценки иногда бывает значительно более простой задачей, чем задача получения оптимального решения. Например, если рассматривается какая-либо задача целочисленного.линейного программирования (ЦДЛ), то в качестве такой оценки можно использовать. значение целевой функции для соответствующей задачи линейного программирования, не стесненной требованиями целочисленности переменных. Очевидно, это значение будет заведомо не больше, чем любое (включая и оптимальное) значение целевой функции исходной задачи. ЩШ.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.