Численные методы глобальной минимизации функций, имеющих вогнутую миноранту на выпуклых многогранниках, и их приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



УЛАРСХБЕННЫЙ КиЖТЕТ ПО КИЧ-'ЛНС-КУ ОЕГА^ЬАКЖ ИРКУTCKIS ГОСУЛАРСТЕЕЙИЙ yiîiEE'JlïïET

На правах эп^-янел

КАСИЕСКАЯ Лашса Иосифовна

ЧИСЛЕННЫЕ НЕГОЛЬ' ГЛОБАЛЬНОЙ ИЖМОДШИ ФУНКШ?, ИМЕКШХ ВОГНГОЮ МИНОРАНТУ НА ЕЫШХШХ ШОГОГРАНШКАХ, И IS ПР111С2КШ

Ü.CM.O&. - мзтемзпг-еская Ш15етзн=

^ « С..-м tj

CHCKSHIî^ '"IcHCii

кандидата í;i3 икс - м я т-зкз е еких .чпук

,:кут:к - 2

Работа гшолнена в .лаборатории "Исследование операций" Сибирского энергетического института СО АН СССР.

Научный, руководитель - доктор физико-математических .наук,

профессор В.Д.Булатов.

Официальные оппоненты - доктор технических наук

профессор А.Е.Бахтин, - кандидат физико-математических наук доцент А.С.Стрекаловский.

Ведущая организация - Вычислительный* центр

АН СССР (г.Москва).

Зашита состоятся » У «сг/^р"- 1992г. Е •• ^ « часов кз заседании специализированного Ученого совета К 063.32.06 по присуждению ученой степени кандидата физико-математических наук в Иркутском государственном университете по адресу г.Иркутск, бул.Гагарина, 20, корн.1, ИГУ.

С диссертацией можно ознакомиться в Научной библиотеке Иркутского государственного университета (бул.Гагарина 24).

„Л 1 „сги \л

Автореферат разослан " " 1992г.

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

IT ЙЙЙ'Ц - . -

Г..........ОВДАЯ ХАРАКТЕРИСТИКА РАБОТЫ

дел Актуальность проблема. Минимизация вогнутой функции с

ртация!

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

п

Предполсай!, что Г с,т - линейная функция цели, где х,-ifrj 1 1 1

величина каждого 1-го продукта; с - стоимость единицы продукта. При возрастаний х стоимость единицы продукта уменьшается. Таким образом, каэкаое с(есть уоьващая функция от х(. Еслй с аппрокейшгров&ва лгнейной функцией, то

п

с,х =(d,+ ех,)х,, где е\-отрйцательны, а Т сх- вогнутая

lililí i ^ L* ^ i i

функция. Минимизация стсгагаотеЯ с. линейнши ограничениями, которые, конечно, доданы включать и определение минимума общего продукта, соответствует максимизации выпуклой функцин с линейными ограничениями. Естественно, в ситуации конкуренции, где себестоимость не преобладает над рыночными ценами, и увеличение количества продукта не означает повышения стоимости, экономическое толкование заключается, н максимизации прибыли, что означает максимизацию выпуклой функции.

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

выпуклого прбгражйтро'вйния,- разраОочшназ!-в настоящее- время.

Вопроса -исследования к -разработки' методов б теории глобальной огшшзащси посвящена ' обдирная литература (работы Д.Й.Батш&ва, В .П. Булатова, -БЛ-ЬБеловз, Л.ТМгЦшкова, А-.М.Гу-пала, Ю.Ы.-Дашй&а, Ю. Г.Евтушенко. .В.В.Леонова, Б-..С.ййхалевм~ ча, И.-БД'лшсуса, В.-К.Кврдаа, С-.А.Йкявскогс, Л.А.Растрйгина, К.Ритора, РьГ.СтранШгач й.,Г.суха|звва, Х.Ту-я, Р,Хорета, Ф. Шварта и друтШ)

• Несмотря- на вое возрастащую активность исследований, пока не существуй?'- общей теорий- глобальной оггйшйзашш, но работа ведется йо разнв» налравлейиям -■ разрабатывайся ин-формацисано-сгатйсткескк« • катодаделаются попытки -обобщения методов локальной''Ьйтшайащй; на. »йюгйэкстр^налкннй случая, разрабатываются -кшимаксные алгоритма и тжшкенше численные методы. Разрабатываются метода'и алгоритмы глобальной даякшзащи для вогнут фушсцйй, ..йюгаих вогнутую

миноранту, лицевых фувдий,'-кёаДрзтйШй^и т.д.-

Решение любой яз. подбОШх задач встречается о очень большими ■ слогШое?йда, так как для. йойучвййя ОЙШума даже'' - ь самой "простой*-, задаче.' из области глобальной . оптимизации требуется, по'существу, .-создание своего особого^.аппарата, методов и алгори'ШО'в. Кроме ; того,-' разрэботайнке методы и алгорктмытреОуот как логического-завершения реаДизада их на ЭШ. Вычислительный -эксперимент часто необходим как одно из доказательств сходимости клиг конечности разработанного алгоритма, более того,, в некоторых случая?..' .'с помощью-вычислительного эксдаршентй шяМясрся' какие-либо' недостатки метода- и выясняются -пути ' устранения зтй* недостатков'

для достижения конечного результата.

Из всего сказанного можно сделать вывод об актуальности исследований проблемы глобальной оптимизации, разработки новах методов н алгоритмов и реализации их на ЭЕМ.

Цель работы: -

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

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

- исследование вопросов г-ффектиачости методов с подааьв разработавши на ЭШ irpcrpsr-м.

Научная новизна:

- предлогов нт-еращгокньй: процесс Для решения задачи минимизации вогнутой функции- на многограннике и доказана его сходность за коночное число нагов; "

- поставлейа задача йикшшции функций, имеадих вогнутую ?.®норанту на выпуклей многограннике; разработан'метод peso-' кия этой задачи, аналогичной методу X-Туя; предложена меди-, фикация этого метода::

- разработаны методы аппроксимации границы допустимой области для задач вогнутого программирования на-основе одного иг> из методов отсечения (выпуклого программирования) с двухсторонней оценкой погрешности приближенного решения;:

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

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

тальных работ по штшзйже и кформатжке СО АН -СССР.

Практическая вначкиоеть работы определяется возможностью использования разработанных численных методов б задачах эко-нсшкн, в некоторых задачам яроекшрозагшя н вооОде в задача! ошшзшда. Нащшкер, «адфщированнш методом Х.Туя решения надави волтутого программирования с дшэйныш ограниченная была решив задача оптимизации трассировки трубопроводаш.

с2ст6м.

Алгорггш раненая общей задачи выпуклого щю1ршлафо-вания методам опорного конуса," который использовался в алгоритмах ноаска локального к глобального шнещ^з да нахождения начально! Точки итерационного процесса, был принят в Гоефовд алгоритмов и программ.

Апробация работы. Основные результаты работы докладыза- .

лись на совещаниях-семинарах "Ыа-тейатичесшШ городское

сегиаар" (Иркутск, СЗй СО АК СССР, 1981 У, 111 ВсесоизяоЗ коа|©решош ш исследованию операций (Горький, 1978), V Все-соазной конференции по проблемам теоретической каберне®® (Новосибирск, 1980), ¥ и VI Сибирской шкаш-смашара по иь~ тодшл ошпмизации и кх щшожешям (Иркутск, Байкал, 1978, 1931), Первом шздународном семинаре по глобальйс*. оптимкза-ции (Шапроа, Взнграя, 1986).

Публикации. Основное содержание диссертации изложено в работах [1-9]-

Спзуктура и осьем работа. Диссертационная работа состоит кз введения, двух глав и списка литературы из 53 наименований. Основной печатай текст зашшает 85 страниц.

' . КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность те?,» диссертации, определяйся. цели исследования,, освещаются вопросы научной; новизщ, подученных, результатов, дается краткая характеристика работы...

Пешая глава -"Обзор существует*. катодов глобальной оп-тнгжзащпГ. В это2- глазе приводятся поетаясшса. задачи гло-бальнол. опта'газацшх,. описываются- раздпчнкв- подхода к проблеме, ставится, задача,- минимизации-' вогнутой фушщпп, на выпуклом шогограшшка, -рассматряваш}«. Ш?ож погрузния и отсечения, продсествукххге. разрийот2ншгд< в- дзссерташ-п.

Дается постановка.задачи: глобальней слгая^'паздЕЗГ-. Крзжо описывается которая развития; проста - схзав дшнсглэтесного щ^зтязгащюващя. Бадлмана.; сведжэт- кгогетлоргоЗ- многоэкет-ре?,:алыю& зада® к одюмврша®« с пслй*ьз кршх-. Пааио; обобщение потодов локальной оптагизипл* па- щогошсстр2:,:ш1ьннй случай;'.щв|юр«шдаонно-ста"1|йстэт8СКйе катода.

Далее, в-, главе 1 приводится, кратко®. описаянэ идеи методов отсекащо. плоскостей для:зада®М2шн?аз2цш, вогнутой фушс-циа на вкпутслсч многогрэншко. Исследуется ютод Х.Туя решения задачи: найта-йХоЬаЬ п^р. Г(х) где Их) - вогнутая

функция и Р - многогранник-.в К". Цдоя г.зтода заюшчается в покрнтш Р выпуклшлп-многогранник конуса:® и в решения вспомогательных подзадач, соот! ¡тствугоцих эти?.! кснусаа.

Далее приводится- более подробное опасаннэ алгоритма X. Гуя, геометрическое истолховааяэ метода "раацашшада-гося" конуса-врекомендации о назоздензщ начальной (первой)

ВЭрШЕН I . •

В раосх-е йварта был дан оргшер использования ьштода X. Туя, в котарс« последовательность подзадач является неограниченной. В далънейвем несколькими авторши были -предлокены методы, модифицировавшие подход X. Туя да получения сходящейся процедуры шш для получения прнйлагвя-ного решения.

Вторая глава - "Численные катоды глобальной щшкщзацш вогнутой функции". В этой главе•разрабатываются численные методы поиск. глобального экстремума вогнутой 'функции на многограннике; функций, имаиш-вогнутуь «яяоранту на вшу-клоч многограннике. Предлагаются методы миш&изацш вогнутой функции на выпуклом произвольно?,! множестве, рассматриваются алгоритмы решения задач вогнутого программирования с помощью отсечений в Е"*1. Определяются условия сходикости построенных алгоритмов. '

В 5 1 решается задача шщшнзашш вогнутой функции на многограннике.-.

Пусть даны, непрерывная вогнутая функция $(х) и вшуклай замкнутый шюгогранник

Н = ! 1 : Ах 4 Ь ),- <1)

где . Л - матрица пьт, ш>п,

Ь - вектор-столбец размерности ш. Требуется найти абсолотшй

ш1п { : иИ >. ' (2)

Основная идея ыетода решения задачи •( 1)-{2) заключается в последовательном построении множеств Я",..:, Як, Нк<1, "пок-рываши1" ынсгэство И и "отсекашкх" верршы Iе,...х*. являющиеся точками локального минимума ^(г) на Н, причем на каждом шаге итерационного процесса. запоминается величина:

1=1.....К .и

■ соответствующая. ей. вершина ..Я .

На 1с-ом ¡лаге процесса определяется одюеаещй и множество •

Значение которое определяет отсечение -я^йЛ , находи, .решая на к-ом шаге итерационного процесса .вапо^т^тедьнуй

■ задачу :

найти га1п зкхН, ,

где-. 1»к=|х : ацХ5йь| - невнрс^еда^ конус, • г^адратяая

ца 'а" ' которого еодергит. п строк .нетрицы

аи э4

Процесс, заакгшвайтся,' когда вновь.. построе:шОе ¿но,ггество Н1"1-пусто. .

Очевидно,, что запомненная' на предшущем шага величина соответствушая. з вершина 'й разрешает .задачу (,1.)-(2). Сходимость метода решения задачи П)-(2) доказывается следующей теоремой:

Т е о р е м а 1.1. Пусть 1) ук 1*ае>0, 2)|А"1 * с <».

Тогда. сутп.Аствует последовательность эке Б* такая, что, начиная с; некоторого _ номера N¿1.

, В 5 2 ставится задача минимизации функций, икеши. вогнутую миноранту на выпуклом многогранника. ' Пусть р(х) - скалярия -функция векторного аргумента' х е Ея;

R = t х : As 5 b ) - выгукщй ограниченны* -многогранник; А - матрица размеров тхп, ra>n; b - вектор размерности ш.

Допустим, что ?(х) в каждой точке х* с R имеет вогнутую миноранту * (х), такую, что

f{XJ) = ¥J(XJ) И f(X)a¥ (X), X * Х!.

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

?(х) -» min, х с R. (3)

Очевидно, ч1") задача (3) - многоэкстремэльная. Причем, известно, что как локальные, так и «^солютнуй минимумы вогнутой миноранты ¥ (х) на выпуклом многограннике достигаются на множестве его вориин. Этот факт позволяет при решении задачи (3) применять аналоги метода X. Туя.

Приведем краткую схему метода решения задачи (3). Пусть у°~ произвольная вершина R. Любим ,13 методиь математического программирования, отправляясь от т<>чки у", .найдем точку х° локального минимума ?(х) на иноаестьч R.

Пусть к" - неьцрокденная матрица размеров пхп, образованная из строк матрицы А, таких, что A°y°-l'n, t>° - компоненты вектора Ь* соответствующие А".

Запишем уравнения лучей, исходящих ю точки у° ь направлении реб*р конуса j: y°J-y° •

где k *G, зо1 - столбцы матрицы, обратной ап.

НаЯдем » пах { X/ ?о(у°-Х,й'") ßo г J. J-bn.

где f (хв>. т (у"> = ?(у°). ¥ (у) ^ о(у;. у с R,

О

т (У) - вогнутая на Е" Функция.

о

е- точность вычисления абсолютного «ганимума.

Если I^ не огршшвш сверху, то их кохео вкйрать произвольно. В салу лшеЗвоа независимости строк матрицы А° векторы такзэ линейно независим. Вшшзем уравяеше

плоскости з°х - 1; , проходяг,еЗ через точит 7°К и построим

полупространство заг д г . не содержащее у°.

Опрадолгд 2/хсИ, з°л ^ %а

Если а, то 2° разрешает, задачу (3). пргавнш- случав найден произвольную вершину у1« На д-точку-х1 локального жшнмума р(х) на Н°, соотввтствущг» заззазехз1, вметаюсь прб-иштш у1, для которых.так на, ках;т дел х?",?"'йоегреей-

иолуарсстренстпо

. т

* з1

1

Ь - 1, Еэ-'ссдзржцэа у1

и определим ¿нотостео Н1=-^хДей, акх * к= 0,1|.

Если Я1» 0, то итсра0),??*!1)} разрзггнот задачу (3). В противном случае найдем произвольную верзилу у3« Я1, точку ха локального ьтшщгт $ на н1, состветстпузпув начальному приближении у3 а т.д.

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

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

Л о м м а 2. !. Пусть существует такое, что Ек- а.

Тогда

-е + pel) s ,

где f= argain С?(х)/хеЕ}.

При рэшэнка практических задач наблюдался следующий отрицательный аффект: на мноааствах R", R1, ., йк» образованных добавлением к основнш ограничениям уравнений отсокакднх плоскостей, появлял» Уо Еовиэ "логныв" Евршнны локальных минимумов вогнутоЗ функщш д(ж). При этом сагш отсекащиэ плоскости становшшсь почта параллельными, из-аа пэго происходило зацкклнваизе процесса решения задачи. Чтобы набежать этого в § 2 прадлогана шдщшшцпя катода для шнншзащш лшшшевых цэлевах функций.

Идея щщфгкадан состоит в параллельном переносе отсека-каэдз§ плоскости

Ek2=t «>

Si

на расстояние.h1, такое, что |р(х)-р(у)| « Н|х-у| s ГШ1« с,

где х удовлетворяет (4), у - проекция вектора х на плоскость

ь, II - константа Лшшица. О сходаоста шдафщарованного мотода свидетельствует сле-духзая . '

Л е и и е 2. 2. Пуст-ь, ограниченные шог^стза R и R такова, чю

Е£Й-Ein ' |у-х| = Ь (5)

КчП? i/'Sfi

п 5C2) - £ншдщев2 $jwam с константой Н, такая, что *<2)« sin viz) 2 * E1Q Р(у). Тогда l9(f)-0(y)| * ifli.

S"cxos2e 15) аадаат mscsia&Eo bcsmosuS нарзялельнай нерэ-

нее плоскости (4), гзрантхфувдий получение е-оптпиальнсгс

решения. Справедлива следующая

Теорема ¿.и Существует tesO, такое, что Rh=e.

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

найти отх, где R - выпуклое ограниченное г,естество.

Здесь мы используем методику для :ян£,:ззгцяз Еогзутса функции на произвольна* выпуклом ¡жсествэ. Так как вогнутая функция достигает как своих локальных, так к абсолютного • кшглума на множестве вершин многогранника, удобнее первоначально погрузить R в п-игрньй стаахзае К° как ¡лгогсгранник, .такотЗ яазхеньпее число вершин.

Допустим, что уне состроена последовательности а1,- -.. х*) и И Xй), q. - aln р (х ÍR1, R2,..., R"}

ISi £1«

и известно подано^эство (.у1) варен кЧ R, т.е. конечное множество точек

(6)

<7 ч

гакое. что шах > < qtr v (у1).

1 5 1 <Ц

9

Найдем xk*l= argnin. фЧу 5. Если

с. (7)

тс x"1*1 разрезает ясхсдяую задачу. В противном случае, найдем течку zk*1 перзеочення отеззка X«Í0,11

е границе^ ынозаства R. В точке построта, полупространство, спорное к Р.:

а^'а-г^'Ю. (8)

Пусть + am fp(ib"'1) ,qv >. Пересечение полупространства (8) с cojy1.....у ч| генерирует новое (sl> шозэство

верш. Пусть та:сое.его подмножество, что

шах o(sl)<q vis1).

Допусти, что |у1, у kt| - такое поданогество вершин (6) ,41

1. max gfy,;1) < q ;

ISiSh, t

2. {у .У4} i i о).

Обозначим, .....у<ЬМ>ч j = | г1...., гк'| и |у '.....у"1}.

г , (к+1) >

Очевидно, что |у ..... у ч| есть поданозшство вершин

некоторого иногограшшха Rk*1 со свойствами: х1""1« Rk*f, RS Rh*S R, причем

Ein хсйк<1|. г ain^d): xcR|.

Затем ваЗдем следущее щшблиЕеша xk*a= argalu ^(y1) и т.д.

!£|£(k«I>

Ч

Предложенный в 5 3 метод внешней аппроксимаций основан на упорядоченной переборе верша выпуклых ыногограанжов R*.

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

принадлежащая отсекающему полупространству t

a1' (x-xk)s 0.

Это позволяет рассчитывать на подучещхз пре^ркого решения еще до . таланта катастрофического увэлгнонпя числа запсанаемых вершн | у 4 | при рвиенш! npaimnecisix задач.

В 5 4 для решения задачи вогнутого прогрзг.еарования предложен метод отсечения в S п*\

Пусть требуется найти абсолтщй min íp(x): хсЮ,

где R = (х: ÄSsb), А - матрица ранга п размеров пьд, га>п. Допусти?.!, что упэ найдена последовательность х°, х1,..., xk_1 и известно выпуклое за»гкнутоэ ограниченное снизу '.аосесгво

{у: AkysbkJ,

такое, что Rn"l= íx, х : XsR, ?(x)sx Л, int R

k I n+t n+tj

т.е. R^*1 содержит надграфин функции <?(x) на R. Здесь Ак- матрица размеров mk*(n+1),

и а п+1, !>"* В."к. у=(х, X .) « S"+t.

* Я ♦ I

Пусть пара х", хк , разрешает еледувдую задачу линейного щюграшировання:

rain (х : XcR, х.х ,е R?*1!.

^ п+1 a*i к J

По разработанной в § Д метода» определяем отсеваадэе полупространство аку s ßk„ не содержащее пари хк, х^,,

инон9СТБо'й^1=^у:убй^',1| , и слвдущеэ хдвйязшвние Xм*1 псшучзш из раненая лшэ£ной задачи:

min (х ,: х, 1 ,е Б"*' хсн).

[ n»l п«-1 к»1 j

По построению последовательность х**1 монотонно неубывающая, ограниченная сверху а так как f(xk) а то

i^s f's f>(xk). -Следовательно, как .только |xk - p(xk) |se, итерационный процесс,заканчивается получением гюптшального решения. _

Мз геометрических еообрааени! .справедлива ü е и м а 4.1. Полупространство' s ß ксодсрят надгра- ■ фзх функции fix) на flv t

Доказательство сходаости -итерационного процесса дает следующая теорема: ■.■.-'

Теорема 4; U Ilm Ilm gk= <p*.

Далее в 5 4 аналогично итерационным процессам, рассматриваемым в §§ 1-3, методы отсечения в Е"*1 • распространен ддя более общих задач минимизации функций, .имещих вогнутую -миноранту на выпуклой шюгогранаике,. а для общей задачи вогнутого програшнровання.

В § 5 в качества примера практического применения-разработанных методов приводятся решение -задачи выбора экономически наивыводвеаиеа трассировки трубопроводных систем, ко-.

торая формулируется следуЕЕм образом.'

На исходной; избыточной схе;ш сета задаю рагуещеш^е го уз-ли потребителей а источников с известная вашчинамя соответственно нагрузок и проззводЕтельностн.. На этоЗ нзбаточноЗ сети необходЕ.га выделять еодсс-ть, ссэдпадизуэ пункты производства и потребления тггсп образец, чтобы шерггизнровать су-к?дарныв расчетные затраты на строительство и гкеллуатацгю сети. Поофоонга' ьитеотадевзх шдэдзЗ для решения подобных задач привода к слогзду кщогоэкстрегшльнк:! задачам с критериальными: фушешки, вапрш сдотщю структуру, нещшвр, с в'дтукле -вегаупг.з фушщшкз цели, Система ограничений тшеп. задач состоит из условна ?лзтерп:адъного баланса во всех узлах сатя (первого закона Кирхгофа) н анергетячесгазго баланса для всей целя з целом', юторш в 'матртшой форде имеют взд

Ах'= 'а, 1атх = Э, где. г, 1х - исксгзе взктерн расходов к напоров; 0 - заданий вектор нагрузок, его копюяен'ш 1С*.еют знак если з узле расположен источник, н знак."-", еелн в узле потребитель;

} } ' отвечавшая заданной избыточной схеме матрица ин-

цнденшй п ветей и а-1 линейно независимых узлов размеров (и-1)хп; ^-О^М); Э - энергия С5юте:лы в единицу времена.

Требуется найти

ЯШ 3 =(В+Ге)К 4- СэЭг. (9)

Здесь К-капиталовложения в сеть; Е-нор<штивйы8 кооффгщвент

Постановка задачи была сделана в лаборатории оптимизация трубопроводных слете?* СЭИ СО АН СССР.

эффективности; I; - доля, отчислений; на амортизацию и ремонт сети; Са- удельная стоимость, электроэнергии-;. Эр» годовая потребность в злектроэяергш.

кашкадьные: затрата, по. сет Еыршшется. следдашл, образш: ш/....., йп) ^ГГ,«!,)!,. где стоимостная, фркцза. Г! (Д1) для- непрерывной модели:.

г, (<11) 5 1 1 1 . .. (.10)

[ О ■ , (1- =0. ■ Учитывая, зашик^ать дщгмра. <Ц .от-напора, и,-расхода на участке

й = ¥ тЯ^-«!« • ПО )

ацтакда выра^нне для. расхода .-энергии (на привод сетевнх насосов). футщ затрат (9): конкрв',щзг1ру.ется следуизга образш:

где допачнитально к.;црюдш1у!ае?4у;. , 1)экономическая

характеристика.участка; пг- число часов использования нагрузки в.год; Ьшс- КЦ5.васосно->4аторюй установки.

Нетрщо убедиться, что.функция Р(х.Ь.Э) - 3 является ВЫПУКЛОЙ"; функциой ПО_ Ь1 Е . вогнутой ПО X, при 0<и<

Бсюполъзоваваась выпуклостью функции затрат Р(х,1г.Э) по' Ь-, перейдем от задачи (11) к эквйвалои'тнсй' ей задаче с . поддаю ластичной фунйш Лагранжа. Тогда исходная задача ак-швалентна .ьарзезацш вогнутой функции

а!д Р(х)

на Ештуклсхз гоюгогранншсе Ах^О, х а х £ г, при -дополните-льньас условиях (13'), которке перепишем в вида

(12)

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

Данная задача без учета ограничений (12)'решалась в аналога*.® кэтодоз, описанных з этом параграф. При п=Ш0 время счета нз В2С*?~6 составило 1ч.

Аналогичные позтанозхи задач возможны тшше и для друггг трубопроводных снстб'М.

(КЙ02ННЕ РЕЗУЛЬТАТЫ РШШ1

1. Разрзбо'тан «етоД решения задачи Шнгшзащш 'всгнутоЗ функции на шогогразйикз. Подучены условия сходимости метода.

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

3. распространен ода из вариантов катодов отсечения с двухсторонней оценкой погрешности прйб-ййсенного решения на решение задачи гшшизацйи вогнутой функции на произвольная выпукла.? 1,йо^9сТв&.

4. Реализована на Э£\! и прошли опытную зкснлуатащш алгоритмы:

- решение задачи выпуклого программирования методом опорных конусов [1];

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

- решение, задачи вогнутого прора'&отровання - с ляяей-

ншн огршгчешяащ щозфщированша пйюлш, X. Туя .

По иатеркалгк. диссертации опубликованы сдедушие работк:

1. Касннская Л.В. Алгоритм й преграда решения общей задачи вещпшзго програамировавня кевдсы опоршх ксаусов//Аяго-рягш и црогра'лпы рзгеная задач • линейной алгебры и математического прохрагашроваЕШь.-Иркутск:СЗй СО Ш СССР, 1974.-С.34-45. '' '

2. Касйнская ЛЯ.ищтх реаешя ваши вапуклого прогрзкль рования штодш опорах шгуеов/Досфонд.алгорттшв и про-ГфглгАлгортш и прографи.- 1Ю0167?.-КГ11,1976. ,

3. Еулзтсз В.П. Методы погружения в задачах ошжизацш /Дополнение 1Т:Каен32Еая 1.1L isropms дайска- локального

■ рашашя вогнутей задача-математического программирования с лжейшаи ограй!шашж»21.ЧйэвоопонрсЕ:Наука.СЕб. отд-ние, 1977-С.144-151.

4. Булатов В.П.,КасЕнская JLiL Об одном методе покргш в шогоэксщшальшх задачах /Дез. докл. III Всесоюзной ковфврандаи. по .исследованию шзращй.-Горький, 1978. -С. 312.

5. Булатов В.П., Каснасквя 1.И. Об. одной интерпретации метода Х.Туя решения задачи вогнутого цро1р8ашфачашя//Пр-кладаая штаматика.-Иркутск:СЭй СО дн'СССР. 1978.-С.206-208.

6. Касшская 1-Й: Алгоритм поиска - локального решения вогнутой задачи катшаткчаского. прграширшания с линейныш' ограш!чвнижи//1лгор®21 е програшы решения 'задач линейной алгебры и штеиатичвекого прграшфования.-Иркутек: С2И СО АН СССР, 1979.-ВШ.2.-С.9в~104.

7. Касшская Л.И. Решение' задачи- вогнутого програ?.ашрования с. ливеЯшла ограничениям! моди&щироваышм методом Х.Туя //Алгоратгш и црограмг-.ш решения задач линейной алгебры и математического- программирования -йркутск:СЗй СО АН СССР,

f979.-C.7S-S*.

8.. Булатов Б.П., Каскнская Л.й. Метод поиска абсолютного мя-■ нслуна фуннщй, кгденеда вогну ту» йиноранту//Тез.докл. V Всессгшо^конфэренцнй по проблемам теоретической кнберне-тнка.-Ксмспбирсх, 1930.-С.'

9..Булатов В.П., Касинская Л.И. Некоторые методы минимизации вогаутса функции на выпуклом многограннике и из приложение // Методы опткдаацЕа и ах приложения.-Новосибирск:Наука, Сиб.ОТД-ЕИв.1982.-С.71-80. ■