Исследование некоторых классов экстремальных задач типа стандартизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
Алиакбаров, Сулейман Мусаевич
АВТОР
|
||||
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
Москва
МЕСТО ЗАЩИТЫ
|
||||
1991
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ вмени М.В.ЛОМОНОСОВА.
Научно-исследовагелъскнй вычислительный центр
На правах рукописи
АЛИАКЕ&ГОВ СШЙМАН МУСШИЧ
УДК 517,988.68:519.65
ИССЛЕДОВАНИЕ НЕКОТОРЫХ КЛАССОВ ЗКСТШШГЬШХ ЗАДАЧ ТИПА. СТАНДАРТИЗАЦИИ
(01.01.09 - математическая кибернетика)
АВТОРЕФЕРАТ
диссертации на соискание учёной степени кандидата фаэико-датематжчеоких наук
Москва - 1991 г.
Работа заполнена на кафедре математической фяавкж факультета шчислительноЯ иахвиатаки и кибернетики Моокоаского государственного униаерситета ии.Ы.В.Лоионосова.
Научный руководитель: доктор фи^яко-ыатематнчесгах наук,
прсфассор ВАСИЛЬЕВ Ф.П.
Официальные оппонента: доктор фиаико-ыатеаатических науч.
ст.н.с. БЕРВЗНЕВ В.А.
кандидат Фиаико-1!атзиатач.1.ь^к, доцент ДЕНИСОВ Д.В.
Вздуцая организация - Вычислительный центр АН СССР.
44 ри^р 1Э9& в
Вадита ссогоится " I ода ч 15 часов
на заседании спэцягшЕпрэзанного совета К.053.05.84 £ Носкогс-коы государ'зкзявса ушЕврсктате им.Ч.ВЛгзгонссега пе адресу: 119899, Ыаскха, МГУ, НаучЕо-пссяедоЕательский хачнсинтелышй цонтр, кон|ерэнц-зал.
С днсоертацаей «огяс сазакештьоя в библиотеке Научно-иссге-дахательскегс юткслигсгвяего «еитра МГУ.
44
Автореферат разеслая " < Т ^ ^д^ г>
Ученый секретарь специаливврманнсго совета
к.ф.-и.н. ^ Й5©са М.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
■ ; Актуальность темы. В последние десятилетия интенсивно развивалась теопил экстремальных задач, были созданы и исследованы методы решения пироких классов таких задач. Однако в связи с запросами практики возникают все новые и новзе классы экстремальных задач, для исследования которых известные подходы недостаточны или непосредственно неприменимы, требуют определенной доработки, и в изучении таких задач успеха удается достичь путем тщательного учета конкретных специфических свойств рассматриваемой задачи.
В настоящей диссертационной работе исследуются задачи, тесно связанные с так называемыми задачами стандартизации, унификации. Рассматриваемые в работе задачи з научной литературе почти не изучались: в известных нам публикациях приводились лишь частные случаи таких задач с сепарабельной целевой функцией и к ним применялся метод динамического программирования без строгого обоснования и в предположении, что исходные данные заданы точно.
Цель работы: исследовать применимость метода динамического программирования к задаче типа стандартизации с сепарабель-ной целевой функцией при условии, когда исходные данные известны с погрешностью, выделить классы корректных задач типа стандартизации и рассмотреть возможности использования методов регуляризации .для нахозденют приближенного решения в случае их некорректности.
Методика выполнения исследований. При выполнении работы использованы теория и методы экстремальных задач, теория и методы решения неустойчивых (некорректных) задач.
Научная новизна. Дано строгое обоснование метода динамического программирования для одноуровневой задачи типа стандартизации с сепарабельной целевой функцией при условии, когда целевая функция известна с погрешностью и каждый шаг метода реализуется неточно; получена оценка погрешности метода по функции, Для одноуровневых и двухуровневых задач типа стандартизации указаны классы корректности, а для некорректных■задач предложены методы регуляризации, дано их обоснование.
Теоретическая и практическая ценность. Теоретическое значение работы определяется тем, что в работе исследованы малоизученные классы задач типа стандартизации, предложенные численные методы могут быть положены в основу алгоритмов, удобных для реализации на ЭВМ, и могут быть использованы для получения приближенного решения конкретных прикладных задач типа стандартизации.
Апробация работы. Результаты диссертации докладывались на Всесоюзной конференции по теории и приложениям функционально-дифференциальных уравнений (г. Душанбе, 1987), на Всесоюзной конференции по вопросам оптимизации и их приложениям (г. Душанбе, 1987), на международной школе-семинаре по методам оптимизации и их приложениям (г. Иркутск, 1989), на 11~м Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (г.Кострома, 1990), на республиканской научной конференции, посвященной памяти Сабирова Т. "О некоторых применениях функционального анализа в теории дифференциальных уравнений"(г. Душанбе-Ордаоникидзеабад, 1990), обсуждались на научно-исследовательском семинаре кафедры функционального анализа и дифференциальных уравнений (рук. .профессор Мухамадиев Э.М.) и др.
Публикации. Основные результаты диссертации опубликованы в работах [I - 14"] .
Структура и объем работы. Диссертация состоит из введения, трех глав, списка литературы.
Работа изложена на страницах машинописного.текста.
Библиография содержит 71 наименование.
Во введении приведены постановки рассматриваемых задач, дан обзор литературы, перечислены по главам основные результаты диссертации.
В первых двух главах рассматривается задача минимизации функции
СОДЕРЖАНИЕ РАБОТЫ
на множестве X , которое определяется условиями
Л, г 2 л
^ «я-V'2 (3)
С=1
2. ^ т-,
0=1
здесь & ^бЯ*1, ■${<£) _ заданная целевая функция,
- заданные положительные числа, Задача (1)-(4) возникает в приложениях при исследовании вопросов стандартизации. Приведен пример содержательной постановки задачи Пусть сталелитейный завод может выпускать Ц- сортов стали, пусть потребность в К-ом сорте стали, к^^Л,,,, ,Л • Предположи«, что сталь К-го сорта по своим качествам лучше сортов стали с номерами К+З. и при необходимости макет использоваться
вместо них; в частности 1-кй сорт стали может заменить все ос-
1 а **
талыше сорта. Отсюда следует, что количества 'х. ^,---, X каадого сорта стали, выпускаемые заводом, удовлетворяют условиям (2),(3). Предполагается, что по техническим причинам завод не может выпускать больше, чем Щ- сортов стали, поэтому возникает ограничение (4). Пусть затрата на производство требуемых сортов стали равна ^(«л = | (о^, ^Л-- » .
Требуется определить, какие сорта стали и в каких количествах необходимо произвести, чтобы с одной стороны удовлетворить потребителей (с учетом заменяемости сортов), и с другой стороны затраты на производство требуемых сортов стали бнла наименьшей. Отметим, что если функция ^х) линейна, то есть имеет вид 13. п
и, кроме того, п , то задача (1)-(4) превращается в
хорошо изученную задачу линейного программирования, так как при
л условие (4) выполняется тривиально и становится ненужным. Однако при задача (.!>—( 4) становится нели-
нейной даже для линейной целевой функции «тСзс) и аппарат линейного программирования для ее анализа'неприменим. Далее, наличие условия (4), содержащего разрывные невыпуклке функции , приводит к тому, что множество (2)-(4), вообще говоря, становится невыпуклым. и задача (1)-(4) даже с выпуклой целе-
классу задач выпуклого программирования, становится многоэкстремальной. Отметим также, что исследование задачи (1)-(4) затрудняется viлеи, что множество, определенное условиями (2)-(4), неограничено и поэтому не является компактным.
Задача (1)-(4) на сегодняшний день исследована мало. Нам известны лишь работы Бэрковича М.М. Полуэктова P.A., Пу~ цима И.М.,3^ в которых давалась постановка задачи (1)~(4) в конкретных содержательных областях, применялся метод динамического программирования в случае, когда целевая функция ^С01) является сепарабельной, то есть имеет вид
исследовались некоторые свойства оптимальных решений. В работах метод динамического программирования рассматривался в предположении точно заданных исходных данных, точной реализации каждого шага этого метода.
1) Берковпч М.М., Решение одной комбинаторной задачи.-Экономика и матем.метода, 1368, т.4, Л 2, с.350-356.
2) Беркович М.М. Задачи стандартизации и некоторые методы их решения.- Экономика л матем.методы, 1969,т.5,.К2,с.285-299.
3) Полуэктов P.A., Пуцима И.М. Модель комплекса электроизмерительных средств для построения нормальных рядов приборов. Труды ЕНЮШ, № 6, Л., 1970.
относиться к хорошо изученному
(6)
Глава I посвящена развитию метода динамического программирования применительно к задаче (1)-(4),(6).
В § I выводится уравнение Беллмана для задачи (1)-(4),(6), именно, показывается, что функция Беллмана
I, к "
где
" С
С=1
удовлетворяет уравнению Беллмана
при всех ..... И-1, ]-©> 1>»-щд (
или имеют место равенства
1 а
0г>-
«г V*
Ст-1
М1П
1 СП? .
(9)
ке1*л ^ 1,1,..., П.
ж« 1 сиЕ + те ,
сФ* V с-К
СП
_ в -
В § 2 приводится вычислительная схема метода динамического программирования в предположении, что целевая функция известна точно, метод реализуется таюке точно и дается обоснование этого метода.
В § 3 изучаются свойства функции Беллмана и приводятся достаточные условия, при выполнении которых нижние грани в (7)-(9) достигаются и метод динамического программирования получает строгое обоснование. В частности, верка следующая
Теорема 1.4. Пусть функция конечна, ограничена
снизу и полунепрерывна снизу при , пусть 14*0-+оо
1*^,2,... я.
Тогда ^ = и| = \4ф }
* ал*
б соотношениях (7)-(9) нижние грани конечны и достигаются при всех о , и точка Оц , построенная методом динамического программирования, принадлежит .
В § 4 изучается метод динамического программирования для случая, когда целевая функция в задаче (1)-(4),(6) известна с погрешностью: вместо точных ^ С*) , известны их приближения ^ (эс1 • такие, что
, ос^о, С= 1,1,..»« •
Тогда в качестве.приближения функций С2) предлагается 1зять функции "тк^К'С2^ ) последовательно определяемые из условий: ^
а^ОЬ »»аоф; V2} ,
I, ~ к
V?»«Г^-Ь^ ' ' '
/-о, I,..., м-й., ?
£ ) ( х х (г) ; «иг (о,- "г^-? \
К • и
Мея функции и точки , Ц^'""
из (II)—(13), далее последовательно полагается
ос* ^ {? \ "I , <14>
Е^ - ЗСУ„ , 1Ъ1 глУ' 0 ¿3 £ г*
< 1
2К* = + = •' •4 н •
- 10 -
Если в (14) окажется, что то процесс (14)
заканчивается определением величин
2 « (15)
Если при каком-то номере и0<1а будет ,
~ ' тогяа пРоцесс (14) прекращается при
^ ^ определением величин
) « ос}-' и
* (16)
® 0 И ^
Остальные переменные £5*. определяются так
причем среда величин ОсЛ I.") , и
Пв«Я-1.ь» по"Аг 7 ® ' ~ '
лишь одна может быть положительной, остальные все равны нулю.
Теорема 1.5. Пусть вместо точной функции (»О известно ее приближение 5 , удовлетворяющее условию (10). Цусть функции определены согласно (7)-(9), а
£ (-2.") ^ определены условиями (11)-(13), точка + Кд г в *
) определена согласно (14)-(16). Тогда точка X и является приближенный решением
задачи (1)-(4),(6), справедлива оценка
Теорема 1.6. Пусть функции С*) конечны, ограничены снизу, полунепрерывны снизу при ос^о и =
Тогда в задаче (1)-(4),(6), 1^-°°' ^^ 0 и для точек 2С. , , полученных из (14)—{16), справедливо равенство
о
В § 5 исследуется задача (1)-(4),(6) с кусочно-линейной целевой функцией, когда
' • (17)
Показывается, что функции
неотрицательны, не возрастают, полунепрерывны снизу, непрерывны справа и кусочно-линейны при • Указанные свойства функции Беллыана
существенно облегчают численнуи реализацию метода динамического программирования для задачи (1)-(4),(6),(17).
Глава 2 посвящена исследовании корректности задачи (1)~(4), то есть вопросам существования оптимального решения, устойчивости решения по отношению к возмущениям исходных данных.
В § I приведены'достаточные условия для существования решения задачи (1)-(4). Сформулируем некоторые из полученных здесь результатов. I)
Теорема 2.2. Пусть - полунепрерывная сйизу, неу-
бывающая функция на . Тогда в задаче (1)-(4)
^ ф и более того, множества С\2ф 0 , где
2= (х1,эс^) £ X: ОсЧ—Ч-ос \ . Если, кроме
того, строго возраставшая функция на , тоХ^^-
р.
Теорема 2.4. Пусть функция 1 вогнута и неотрицательна на ^ . Тогда в задаче (X)—(4) ^ф0>
и более того, множество г* Ф , где
- множество всех наборов 113 Целых чисел
..., и , таких, что ... < ¿|> ^ п .
Если строго вогнута на , то ^с Г
В § 2 главы 2 выделяются классы устойчивых (корректных) задач (1)-(4). Здесь предполагаете!:, что вместо точней функции
, У-й ^ , и точных величии X д
такие, что
А
4 .
известны их приближения 4гЧхЛ ^^ 8,10. г ... г _,
0 + ' 1Р' ' пЗГ'
осе 5>о, (18)
15 1 '
Тогда вместо задачи (1)-(4) можно попытаться рассмотреть следующую приближенную задачу
I с*) - с4 ,
& п
V (¿„.Л**;:
и решая ее с помощью какого-либо подходящего метода минимизации, определить точку ос-Х^Б", £) из условий
надеясь на то, что найденная точка ос (_&,£> будет близка ко множеству У^. , а значение близко к Д^.
и эту точку можно будет принять за приближенное решение задачи (1)-(4); здесь подразумевается, что ^^Ф •
Такой подход оправдан лить .для задач, которые устойчивы к возмущениям исходных данных. \ Определение. Пусть в задаче (1)-(4)
пусть .{ >_ СО, хи*) - 1 *е ?■],£>о .
Говорят, что задача (1)-(4) устойчива к возмущениям исходных данных, взятых из (18),если
Нетрудно привести примеры, показывающие, что задача (I)-(4) в общем случае не является устойчивой. В связи с эти.! представляется важным выделение подмножества задач (1)-(4), которые устойчивы к возмущениям исходных данных. Сформулируем здесь один из полученных результатов.
Теорема 2.6. Пусть не убывает, и равномерно неп-
рерывна на Ц.^1 , приближения удовлетворяют
условиям (18). Тогда задача (1)-(4) устойчива к возмущени^л исходных данных.
В § 3 главы 2 для решения неустойчивых задач (1)-(4), предлагаются три метода регуляризации, представляющие собой модификации применительно к рассматриваемой задаче (1)-(4), известных методов стабилизации,невязки и квазиреиений, основанных на идее расширения множества. Пусть какой-либо стабилизатор задачи (1)-(4), например, ИСх>-=О*1}\(Ьс")^,
. Будем предполагать, что вместо точных
i ¡)
тСх), известны их приближения JjgCjxo ^^ f
гакие, что
5 , fc" , 5> o,
Введем множество
i. А . *
ъ
где 'у, р i )
Так как 7. > - 5" , то Ус "Wx при всех > So и
о , так что множество "W^ является расширением исходного множества у
Кратко ошшем предлагаемые методы регуляризации для решения неустойчивых задач (1)-(4) и приведем соответствующие теоремы сходимости.
Метод квазирешений, Пусть известно число tC>o , та--кое, что для какой-либо точки £ у^ справедлива оценка
К • ~ ,7 п, . ..
Введем множество Ug " W5 '- AL R J , о .
В методе квазирешений приближенно решается задача
Хе. О < и определяется точка '-Х-С О . принадлежа-
щая множеству
Теорема 2.9. Пусть функция <|полунепрерывна снизу
на В", 1^-«°,
приближения удовлетворяют условиям (19).
Тогда где
Метод А.Н.Тихонова (метод стабилизации). Составим функцию Тихонова
и приближенно решая задачу минимизации "^О)- СП? ,
определим точку О:-схсй, £) , принадлежащую множест-
ву
Теорема 2.10. Пусть в задаче (1)-(4) функция , ос с- удовлетворяет условию Липшица:
1, V &+П, ¿=0*^20)
-й-С«.-) - какой-либо непрерывный стабилизатор задачи (I)-(4); приближения (.х), Тс5 для
удовлетворяет условиям (19); параметры ^(д изменяются согласованно с параметром погрешности о так« 4,10
£=£Сг.')>о, 0<«<?>Л"т 1-3)=0
+ о ¿(О- ' '
Тогда
хеУсв)
где = \ - множество
** и =»
нормальных решений задачи (1)~(4), Утверждение теоремы 2.10
сохраняют силу, если вместо условия (20) потребовать, чтобы
функция .|(зс) была выпуклой и полунепрерывной снизу на.
Метод невязки. Введем множество I _ ""-ОБ
ГД6 I £«
л
В методе невязки приближенно решается задача: Осе и определяется точка ос- ос. СБ", <3, V) , принад-
лежащая множеству ^
Ус«- 1хетб лк^^
Теорема 2.12. Пусть в задаче (1)-(4), Х^ $,
выполнено условие (20) (вместо (20) можно потребовать выпуклость и полунепрерывность снизу |(зо на ) ; _0.(ро -какой-либо непрерывный стабилизатор задачи (1)-(4); приближения (осо , Т- с б 4Сх"), ^ удовлетворяют условиям (19), параметры 5 , ^ изменяются согласованно с параметром погрешности 8 так, что
Тогда справедливы равенства (21). п
Цусть -оператор, который кавдому набору
г^ 5Л из (19) ставит в соответствие точку
п5* где множество введено
выше при описании методов регуляризации (в методе квазирешений
- 17 -
). Из утверадений теорем 2.9-2.12 следует, что при согласованном изменении параметров такой оператор явля-
ется регуляризирукщим.
Задачу (1)-(4) принято называть одноуровневой задачей типа стандартизации. Естественным обобщением такой задачи является двухуровневая задача типа стандартизации, которой посвящена глава 3 диссертации. В ней рассматривается следующая задача
(22)
* С * К I ^"с
ы С=1
* С 1 I г
' па.' (25)
здесь X = х) , у, Са'-.Л > Д
- заданная функция ^Да,,.,., -заданные положительные числа, ~ заданные целые.числа,
Задача (22)-{25) ранее почти не изучалась, Нам известна лишь одна работа^, в которой рассмотрен частный случай задачи (22)-
4) Беркович М.М., Очеретяний С.М. Двухуровневые задачи унификации. Из». АН СССР, техническая кибернетика, 1974, № 4,с.43-51.
(25) к которой применен метод динамического программирования.
В 8 I глазы 5 приведены примеры задачи (22)~(25) в содержательных терминах.
В § 2 сформулирован*; достаточные условия, при которых существует реиение зацачи (22)-(25).
В .§ 3 дано описание и исследована сходимость методов регуляризации для неустойчивых задач (22)-(25),
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ:
1. Развит метод динамического программирования применительно к одноуровневым задачам типа стандартизации с сепара-бельной целевой функцией с неточно заданными исходными данными, дано обоснование этого метода, получена оценка погрешности метода по функции.
2. Выделены классы корректных задач типа стандартизации.
3. Предложены метода регуляризации для неустойчивых одноуровневых и двухуровневых задач типа стандартизации, дано их обоснование,
ПУБЛИКАЦИИ ПО ТШЕ ДИССЕРТАЦИИ.
1. Алиакбаров С.М., Мухамадиев Э.М. О корректности одной экстремальной задачи стандартизации. Докл. А.Н.Тадж.ССР. 1986, т. 29, № I, с. 3-6.
2. Алиакбаров С.М., Мухамаднев Э.М. Исследование корректности одной экстремальной задачи. Журн.вычисл.матем. и матем.физики. 1986, т. 26, № 10, д. 1443-1454.
3. Алиакбаров С.И. Функциональные уравнения Беллмана в одной задаче стандартизации. Тезисы докл. Всесоюзной конф. по теории и приложениям функционально-дифференциальных уравнений. 28-30 сентября 1987, г. Душанбе, с. 22-23.
4. Алиакбаров С.М. Об устойчивости одной экстремальной задачи стандартизации. Докл. АН Тада. ССР, 1987, г. 30, № 4,
с. 199-202.
5. Алиакбаров С.М. Применение метода динамического программирования к одной задаче стандартизации. Тезисы докл. Всесоюзн. конф. „По вопросам оптимизации и их приложениям!' Душанбе,
1987, с. 83-85.
6. Алиакбаров С.М. Функция Беллмана и некоторые ее свойства в задаче стандартизации. Докл. АН Ттда.ССР. 1988, т. 31, № 8, с. 4Р9-492. Р i) 1) р 1)
V. Лсакйагог oj/ сЫ-> с\ тппАптк
-SeWi'nat op-tiw L-ta-ti'on Ae-Uools
«tíOllg .
¿acicat, USSft,io-H «е^чи&а, I9¿3>1?.S-G.
8. Алиакбаров С.М. Некоторые метода решения многоуровневой задачи стандартизации. В сб.: Прикладные вопросы математики. Научные труды мех.-мата Таи. ун-та, 1989, вып. 2,с.46-52.
9. Алиакбаров С.М. О применении метода динамического программирования к задачам типа стандартизации. Ьурн.вычисл.матем. и матем. физики. 1990,. т. 30, № I, с. 33-42.
10.Алиакбаров С.М., Васильев Ф.П. 0 методах регуляризации для решения неустойчивых задач типа стандартизации. Бестн.Моск. ун-та, сер. 15, вычксл.матем. и кибзрн., 1990, ü 3,с.18-24,
11.Алиакбаров С.М. Об одной кусочно-линейной задаче типа стандартизации, Тезисы докл.на II Все с оюзн. симпозиуме,, Системы программного обеспечения решения задач оптимального планирования^ 21-29 мая г. Кострома, 1990, с. 85-86.
12.Алиакбаров С.М. Метода регуляризации для решения неустойчивых двухуровневых задач типа стандартизации. Материалы респ. научн. конф., посвящ. памяти Сабирова Т.„О некоторых применениях функционального анализа в теории дкфференциаль:-их уравнений,'''29-30 апреля г. Душанбе-Орджоникидзеабад., 1990, с. 13-16.
13.Алиакбаров С.М. К вопросу обоснования динамического программирования для задач типа стандартизации. В сб. .-„Прикладные вопросы математики? Научные труды мех.-мата Тадж.ун-та, 1991, вып. 3, с. 34-43.
14.Алиакбаров С.М., Васильев Ф.П. Методы регуляризации для неустойчивых двухуровневых задач типа стандартизации. Журн. вычисл.матем. и матем. физики. 1991, т. 31, № 3, с. 363-371.