авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 ||

«Вестник ПГТУ. Прикладная математика и механика, 2010 Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального ...»

-- [ Страница 4 ] --

Кроме того, естественно, алгоритм автоматической укладки гра фа на плоскости должен быть эффективным по времени исполнения (полиномиальной сложности).

Таким образом, разработчик должен решить задачу многокрите риальной оптимизации.

Классификация алгоритмов укладки графа выглядит следующим образом [4]:

алгоритмы на основе физической модели, аналитические алгоритмы, генетические алгоритмы.

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

Вводят так называемую штрафную функцию, которую минимизируют.

Выделяют «пружинный метод» и метод отжига.

В «пружинном методе» [3] граф интерпретируется как некоторая упругая механическая система, в вершинах которой находятся точки системы, а ребра соответствуют упругим силовым связям («пружин кам»). Штрафная функция – потенциальная энергия системы, а ее ми нимуму соответствует условие равновесия системы.

Вестник ПГТУ. Прикладная математика и механика, Если силовые связи подчиняются закону Гука, то сила натяжения пружины пропорциональна ее длине. В этом случае потенциальная энергия системы представляет собой положительную функцию wij d 2 ( pi, p j ), W 2 ( pi, p j )E где Е множество ребер графа;

d2 (pi, pj) квадрат расстояния между вершинами графа pi, pj, декартовы координаты которых (xi уi) и (xj, yj);

d2(pi, pj) = (xi xj)2 + (yi yj)2;

wij произвольные положительные веса этих ребер (в частности, можно взять все веса равными 1).

Функция W зависит от координат вершин, не принадлежащих внешней грани: W ( xi, yi ).

Далее для нахождения минимума используется условие равенства W W 0;

0;

первых производных нулю, т.е.

xi yi После несложных преобразований:

xi wij wij x j wij x j, p j V ( pi ) p j V out ( pi ) p jV in ( pi ) wij wij y j yi wij y j, p j V ( pi ) p j V out ( pi ) p jV in ( pi ) где V(pi) окрестность вершины pi, т.е. множество смежных с pi вер шин;

Vin(pi) множество вершин из V (pi), не принадлежащих внешней грани;

Vout (pi) множество вершин из V (pi), принадлежащих внешней грани.

Нетрудно заметить, что данный алгоритм имеет полиномиальную сложность.

Можно выделить следующие недостатки «пружинного метода»:

необходимо выделять внешнюю грань;

алгоритм позволяет от ветить на вопрос о планарности графа, но не позволяет выделить мак симальный планарный подграф, что не позволяет работать с произ вольными графами;

алгоритм не дает возможность учитывать размеры вершин гра фа, что не удовлетворяет поставленному вначале третьему требова нию;

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

Вестник ПГТУ. Прикладная математика и механика, Модификацией данного алгоритма является нелинейный силовой метод [3]. Укладка связного графа обеспечивается уравновешиванием сил притяжения и отталкивания, зависящих от расстояния между вер шинами d: для всех пар вершин действует сила отталкивания R(d), мо нотонно убывающая с ростом d, для всех пар смежных вершин дейст вует сила притяжения A(d), монотонно возрастающая с ростом d. В этом случае нивелируется первый недостаток предыдущего метода, но по-прежнему остается нерешенной вторая и третья проблема. Более того, минимизация штрафной функции сводится к решению нелиней ной системы дифференциальных уравнений, что приводит к дополни тельным вычислительным расходам, а также накладывает ограниче ния на начальные условия (например, при решении системы методом градиентного спуска).

Следующий метод на основе физической модели – метод отжига.

Это техника оптимизации, использующая упорядоченный слу чайный поиск на основе аналогии с процессом образования веществом кристаллической структуры с минимальной энергией при охлаждении [8].

Идея данного метода состоит в следующем: граф представляет собой некоторую систему. Вводится понятие «энергетического уров ня» системы, т.е. каждому состоянию системы, а именно раскладке графа, соответствует энергия E, пропорциональная, например, количе ству пересечений ребер графа. Пусть E f ( x), x S, где S – множест во различных укладок графа. Теперь необходимо минимизировать E.

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

В каждый момент времени предполагается заданной температура системы, которая с течением времени охлаждается. Каждое следующее состояние выбирается в соответствии с заданным вероятностным се мейством распределений G( x, T ). После генерации нового состояния x l G ( x, T ) система с вероятностью H (E, T ) (вероятность принятия нового состояния) переходит к следующему шагу в состояние x l, ина че процесс генерации xl повторяется. E f ( x l ) f ( x). В качестве H (E, T ) обычно берут следующую функцию: H (E, T ) (E / T ).

При ее использовании H (E, T ) больше единицы в случае E 0, то гда соответствующая вероятность считается равной единице. Таким образом, если новое состояние дает лучшее значение оптимизируемой функции, то переход в это состояние произойдет в любом случае.

Вестник ПГТУ. Прикладная математика и механика, Итак, конкретная схема отжига определяется следующими пара метрами:

выбором закона распределения температуры от шага T (k );

выбором порождающего семейства распределений G( x, T );

выбором функции вероятности принятия нового состояния H (E,T ).

Существуют более эффективные схемы отжига, например сверх быстрый отжиг [8], который позволяет довольно быстро искать гло бальный минимум.

Достоинства метода:

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

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

Недостатки:

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

эффективно работает только для небольших графов (в связи с трудоемкостью метода);

не учитывается размер вершин графа;

сложно подобрать функцию E для быстрой сходимости данного метода.

Аналитические алгоритмы. На практике аналитические алго ритмы представляют собой последовательность преобразований графа, приводящих к укладке графа. Главное преимущество данной группы алгоритмов состоит в том, что с их помощью получается гарантиро ванный результат, в отличие от алгоритмов на базе физической моде ли. К данной группе алгоритмов можно отнести гамма-алгоритм, алго ритм GIOTTO, а также другие алгоритмы [7], не рассматриваемые в данной работе.

Гамма-алгоритм основан на выделении сегментов в графе и их определенной укладке в нужным образом выбранных гранях графа [2].

Достоинством данного алгоритма является возможность производить укладку графа с криволинейными ребрами. Но главным недостатком данного алгоритма является то, что он лишь позволяет укладывать планарные графы, что противоречит первому требованию, поставлен Вестник ПГТУ. Прикладная математика и механика, ному в начале данной работы. Более того, данный алгоритм плохо под дается модификации.

Наиболее эффективным является алгоритм GIOTTO [6]. Основ ные шаги данного алгоритма:

1. Преобразование графа в связный;

2. Преобразование графа в двусвязный;

3. Выделение планарного подграфа;

4. Построение st-графа;

5. Построение планарного «надграфа»;

6. Разбиение вершин инцидентностью больше четырех на цепоч ки;

7. Построение ортогонального представления;

8. Минимизация площади, занимаемой уложенным графом;

9. Удаление фиктивных элементов, созданных в процессе преды дущих шагов;

10. Восстановление информации об ориентации ребер (информа ция теряется на четвертом шаге).

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

Генетические алгоритмы (ГА). Данные алгоритмы, подобно методу отжига являются универсальными с точки зрения решения оп тимизационных задач [5] и имеют аналогию с природным механизмом.

Все внешние данные особи кодируются ее цепью ДНК (геноти пом). Отдельные участки этой цепи (гены) определяют различные па раметры особи. Согласно теории эволюции Чарльза Дарвина, особи популяции конкурируют между собой за пищу и за привлечение брач ного партнера. Те особи, которые наиболее приспособлены к окру жающим условиям, проживут дольше и создадут более многочислен ное потомство, чем их собратья. Скрещиваясь, они будут передавать потомкам часть своего генотипа. Некоторые дети совместят в себе час ти цепи ДНК, отвечающие за наиболее удачные качества родителей и, таким образом, окажутся еще более приспособленными.

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

Вестник ПГТУ. Прикладная математика и механика, Изредка происходит мутация: некоторый случайный нуклеотид цепи ДНК особи может измениться на другой. Если полученная цепь будет использоваться для создания потомства, то у детей возможно по явление совершенно новых качеств.

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

Теперь, пусть необходимо найти максимум (минимум) функции f ( x1, x2,..., xn ). Эта функция называется функцией приспособленности (fitness function) и используется для вычисления приспособленности особей. Она должна принимать неотрицательные значения, а ее об ласть определения должна быть ограниченным множеством. В случае задачи планаризации графа функцией приспособленности может вы ступать, например, как самый тривиальный вариант, функция количе ства пересечений ребер графа (требуется найти ее минимум).

Каждый параметр функции приспособленности будет кодиро ваться битовой строкой. Особью [5] будет называться строка, являю щаяся конкатенацией строк всего упорядоченного набора параметров:

101100 11001011 01101100 1100 1 | x1 | x2 | | | | xn | Приспособленность особи высчитывается следующим образом:

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

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

Вестник ПГТУ. Прикладная математика и механика, Отбор Создание начальной популяции Скрещивание Переход к новому поколению Мутация Результат Рис. Основные этапы генетического алгоритма В классическом гинетическом алгоритме [5] начальная популя ция формируется случайным образом. Фиксируется размер популяции (количество особей N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L-битная строка, где L длина кодировки особи, она тоже фиксирована и для всех осо бей одинакова.

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

Шаг алгоритма состоит из трех стадий (рисунок): генерация про межуточной популяции (intermediate generation) путем отбора (selection) текущего поколения (current generation), скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения (next generation), и мутация нового поколения.

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

Вероятность, что особь попадет в промежуточную популяцию, пропорциональна ее приспособленности, т.е. работает пропорциональ ный отбор.

Вестник ПГТУ. Прикладная математика и механика, После отбора особи промежуточной популяции случайным обра зом разбиваются на пары. Каждая из них с вероятностью pc скрещива ется, т.е. к ней применяется оператор кроссовера, в результате чего по лучаются два потомка. Они записываются в новое поколение. Если же паре не выпало скрещиваться, в новое поколение записываются сами особи этой пары.

В классическом гинетическом алгоритме [5] применяется одно точечный оператор кроссовера (1-point crossover): для родительских хромосом случайным образом выбирается точка раздела, и они обме ниваются отсеченными частями. Полученные две строки являются по томками:

11010 01100101101 10110 10110 10011101001 11010 К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью pm инвертируется. Эта вероятность обычно очень мала, менее 1 %.

1011001100101101 Таким образом, процесс отбора, скрещивания и мутации приво дит к формированию нового поколения. Шаг алгоритма завершается объявлением нового поколения текущим. Далее все действия повторя ются.

Вообще говоря, такой процесс эволюции может продолжаться до бесконечности. Критерием останова может служить либо заданное ко личество поколений, либо достижение состояния схождения (convergence) популяции.

Состоянием схождения называется такое состояние популяции, когда все особи популяции почти одинаковы (различаются в несколько нуклеотидов) и находятся в области некоторого экстремума. В такой ситуации кроссовер практически никак не изменяет популяции. А вышедшие из этой области за счет мутации особи склонны вымирать, т.к. чаще имеют меньшую приспособленность, особенно если данный экстремум является глобальным максимумом.

В [1] разработан генетический алгоритм, выполняющий планар ную укладку графа за полиноминальное время. Для определения пла нарности графа используется критерий Мак-Лейна, сформулирован ный в терминах базиса циклов. Использован оригинальный способ ко дирования решений. Так, каждая хромосома имеет p+3 генов (разря дов): p разрядов – это комбинация циклов, представляющая собой ва Вестник ПГТУ. Прикладная математика и механика, риант плоской укладки графа, последние три разряда несут информа цию о том, какие ребра и сколько раз содержатся в выбранной комби нации (0, 1 или 2 раза соответственно для (p+1), (p+2), (p+3)-генов). В качестве функции приспособленности промежуточных решений ис пользуется аддитивная функция двух переменных f ( H ) (, Nc ), m где относительное увеличение числа ребер, Nc относительное m увеличение числа циклов. Количественное значение функции приспо собленности рассчитывается из числа совпадений ребер в соответст вующих разрядах анализируемых решений, а также числа циклов, ко торые добавляются (удаляются) в базовом решении. В качестве опера тора кроссинговера используется двухточечный суммирующий крос синговер.

Следует выделить следующие преимущества генетических алго ритмов при решении задачи планаризации графов:

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

Недостатки:

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

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

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

данный алгоритм позволяет не только определить, планарен ли граф, но и выделить максимальный планарный подграф в непланарном гра фе. Более того, алгоритм гибок, легко поддается модификации, нет привязки к координатам вершин на плоскости, так что можно исполь зовать эффективные методы поуровневой визуализации [3] с учетом размера вершин графа, а также минимизации площади, занимаемой графом. Кроме того, генетический алгоритм можно будет модифици ровать, используя островную модель [5].

Вестник ПГТУ. Прикладная математика и механика, БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Гладков Л.А. Решение задачи планаризации графов на основе бионических технологий // Вестник ЮНЦ РАН. Т. 1. Вып. 2. 2005.

2. Иринев А., Каширин В. Алгоритм плоской укладки графов.

URL: rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout/layout-2006.

3. Касьянов В.Н., Евстигнеев В.А. Графы в программировании:

обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

1104 с.

4. Коротков М.А. Разработка и реализация алгоритма укладки диаграмм состояний. URL: rain.ifmo.ru/cat/view.php/theory/graph coloring-layout/uml-layout-2005.

5. Яминов Б. Генетические алгоритмы. URL: rain.ifmo.ru/cat/ view.php/theory/unsorted/genetic-2005.

6. Graph Drawing. Algorithms for the Visualization of Graphs / G.

Battista [et al.]. New Jersey: Prentice Hall, 1999.

7. Sigiyama K. Graph Drawing and Applications for Software and Knowledge Engineers. Singapore: Mainland Press, 2003. – 218 p.

8. Лопатин А. Метод отжига. URL:cs-seminar. spb.ru/reports/52.

pdf.

УДК 519. М.О. ГАВРИЛОВА Пермский государственный технический университет О ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С КУСОЧНО-ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ Рассматривается задача линейного программирования с кусочно постоянными коэффициентами системы ограничений и целевой функции.

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

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

Вестник ПГТУ. Прикладная математика и механика, n min(max) z x c j x x j (1) j при ограничениях i 1, m, n a x x bi x, (2) ij j j n aij x x j bi x, x j 0, j 1, n, (3) j 1 где aij x, bi x и c j x – некоторые кусочно-постоянные функции аргумента x ( x1, x2,, xn ).

Функции aij x, bi x и c j x определены на одном и том же множестве G x G R n, и существует такое конечное разбиение G Gk, k 1, l, что в каждом подмножестве G k функции постоян ны, причем G k и Gk 1 могут пересекаться только по своим границам.

Область допустимых решений т.е. множество M, x ( x1, x2,, xn ), удовлетворяющих системе (2)(3), во многом в так поставленной задаче зависит от семейства подобластей G и функций коэффициентов aij x, bi x и c j x. Здесь, безусловно, возможна по теря областью M выпуклости, связности и других свойств, которые обычно используются при решении подобных задач.

Приведем пример нарушения связности области допустимых ре шений. Рассмотрим область, заданную следующей системой уравне ний:

3x 3 y 48, 2 x 3 y 3, 2 x 3 y 3, x 6 y 33, x 6 y 33, x y 16, (4) x 9, y 7, x 9, y 7, x 9, y 7.

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

Вестник ПГТУ. Прикладная математика и механика, у х 0 9 Рис.

Отсюда следует, что говорить о решении поставленной задачи (1)(3) имеет смысл, если есть дополнительные предположения. Таки ми предположениями, например, могут являться выпуклость целевой функции и функций ограничений. Целью данной статьи является изу чение именно указанных случаев.

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

Прежде всего потребуем дополнительных условий на области G и G k. Будем считать, что G параллелепипед: G П [0, a1 ] [0, a2 ] [0, an ]. Таким образом, условие (3) можно не рас сматривать. Каждое G k также является параллелепипедом, грани кото рого параллельны координатным гиперплоскостям. Более того, мы бу дем считать выполненным следующее требование: существует конеч ное разбиение параллелепипеда П, например П Пkaa ka 1, sa, где ka П набор параллелепипедов, на каждом из которых функция a ka aij x является постоянной. Аналогично можно представить П Пbb k kb k и П конечные на 1, sb, kc 1, sc, где П bb или П Пcc c b kc k k kc боры параллелепипедов с постоянными bi x и c j x соответственно.

Из этого следует, что существует конечное разбиение множества G П на параллелепипеды Gk Пk, такое, что П Пabc, abc k k П П П П и функции aij x, bi x и c j x посто abc a b c k ka kb kc Вестник ПГТУ. Прикладная математика и механика, янны для каждого Пabc. При этом соседние параллелепипеды Пabc и k k П abc пересекаются только по границе.

k Наконец, потребуем, чтобы в задаче (1)(3) целевая функция n z( x) и функции ограничений fi ( x) aij x x j bi x были непре j рывны и выпуклы. Условия для выпуклости целевой функции и функ ции ограничений мы не выписываем. Такие условия можно получить, используя условие выпуклости для дифференцируемых функций и ап проксимацию полиэдральных функций дифференцируемыми функ циями.

Можно выделить несколько методов решения задачи (1)(3) при таких предположениях.

1. Самым очевидным из них [1] является простой перебор конеч ного числа параллелепипедов Пabc, т.к. в каждом из Пabc мы будем k k иметь дело с обычной задачей линейного программирования с линей ной целевой функцией и выпуклой областью допустимых решений.

Для каждого Пabc находится оптимальный план x k, а решением задачи k (1)(3) является x*, для которого целевая функция минимальна:

z * ( x* ) min z x k.

k 2. Другой подход к решению задачи (1)(3) основан на итераци онном методе решения экстремальных задач [2]. Для этого используем следующий алгоритм.

На множестве П П abc зададим некоторую сетку точек с доста k k точно малым шагом 0. Отметим, что для каждого параллелепипеда Пabc соответствующая часть области допустимых решений системы (2) k представляет собой выпуклый многогранник M k Пk, а целевая abc функция линейна.

На предварительном этапе решения задачи (1)(3) находится на чальный опорный план на произвольно выбранном Пabc. Для этого ре k шается стандартная задача линейного программирования:

n z k x c k x j min, (5) j j Вестник ПГТУ. Прикладная математика и механика, n a x j bik, i 1, m, k (6) ij j x j 0, j 1, n, (7) x ( x1, x2,, xn ) Пkabc с помощью любого известного метода, например симплекс-методом. В результате решения данной задачи находится точка xk M k Пabc.

k Первый шаг алгоритма заключается в переходе из x k в ближай шую узловую точку сетки, принадлежащую области допустимых ре шений M, т.е. в такую точку x M, для которой выполнено соотно k x k x min x k x шение по всем окрестным узловым точкам k x M x M.

На втором шаге алгоритма определяются смежные с x узловые k t 1, p, принадлежащие области допустимых реше точки сетки xt k ний. Каждая из найденных узловых точек xt может принадлежать од k ному или одновременно нескольким параллелепипедам из П. Для ка ждого «затронутого» точками xt параллелепипеда решается соответ k ствующая задача линейного программирования (5)(7), затем среди множества полученных решений выбирается оптимальное x k 1, такое, для которого целевая функция принимает минимальное значение.

Далее опять производится переход из x k 1 в ближайшую узловую точку x 1 и осуществляется повтор второго шага алгоритма. Алгоритм k завершает свою работу, когда найденное решение x k 1 окажется рав ным оптимальному решению x k, полученному на предыдущем этапе.

3. Далее рассмотрим способ решения, который основан на ис пользовании метода линейной аппроксимации и выпуклого симплекс метода [3].

Для этого возьмем разбиение множества П на параллелепипеды Пab, такое, что П П ab, Пab Пka Пbb. Функции коэффици a k k k k k ентов aij x и bi x постоянны для каждого Пab, следовательно, для k каждого Пab соответствующая часть области допустимых решений за k Вестник ПГТУ. Прикладная математика и механика, дачи является выпуклым многогранником M k Пk. В силу наложен ab ных ранее условий целевая функция z ( x) выпукла и непрерывна на каждом Пab. Таким образом, на каждом Пab мы имеем дело с задачей k k нелинейного программирования с линейными ограничениями. Методы решения таких задач известны под названиями метода линейной ап проксимации и выпуклого симплекс-метода и подробно рассмотрены, например в работе [3].

Алгоритм решения задачи (1)(3) заключается в следующем. Как и ранее, решение задачи начинается с нахождения начального опорно го плана на произвольно выбранном множестве Пab. Для этого с по k мощью известных методов необходимо решить задачу нелинейного программирования с линейными ограничениями:

n z x c j x x j min, (8) j n a x j bik, i 1, m, k (9) ij j x j 0, j 1, n, (10) x ( x1, x2,, xn ) Пab.

k В результате решения указанной задачи находится точка x M k Пab.

k k Далее необходимо осуществить переход к следующему паралле лепипеду из П. Для этого можно предложить итерационный метод, известный как метод проекции субградиента [2]:

x1 PM xk k ck, k 0, ck z xk, k 1, 2,, k (11) где k длина шага, ck и z xk соответственно субградиент и суб дифференциал функции z x в точке xk, PM проекция точки xk k ck на множество M. Субградиент ck выбирается из z xk произвольным образом. Для выбора величины k в градиентных ме тодах существует насколько способов, наиболее распространенные из них рассмотрены в работе [2].

Вестник ПГТУ. Прикладная математика и механика, Найденная с помощью (11) точка x 1 определяет некоторый па k раллелепипед Пab 1 : x1 Пab 1, для которого снова решается задача k k k (8)(10) и находится последующее решение x k 1. Если при некотором k окажется, что xk 1 xk, то процесс прекращается, а x k является ре шением задачи (1)(3).

4. Рассмотрим далее подход к решению задачи (1)(3), основан ный на переходе к двойственной задаче.

Для этого рассмотрим еще один вариант разбиения множества П на параллелепипеды Пac, таким образом, что П П ac, k k k П П П. В силу разбиения для каждого П постоянными ac a c ac k ka kc k являются функции aij x и c j x, и для каждого Пac мы можем запи k сать следующую задачу с кусочно-постоянными коэффициентами:

n z k x c k x j min, (12) j j n a x j bi x, i 1, m, k (13) ij j x j 0, j 1, n, (14) x ( x1, x2,, xn ) Пac.

k Далее для задачи (12)(14) запишем двойственную задачу:

m g y bi x yi max, (15) i m a yi c k, j 1, n, k (16) ij j i yi 0, i 1, m. (17) Целевая функция двойственной задачи g y является непрерыв ной и выпуклой [4]. Таким образом, задача (15)(17) представляет со бой задачу нелинейного программирования с линейными ограниче ниями, аналогичную задаче (8)(10), и также может быть решена с по Вестник ПГТУ. Прикладная математика и механика, мощью метода линейной аппроксимации или выпуклого симплекс метода.

Найденному решению y k двойственной задачи (15)(17) соот ветствует решение прямой задачи (12)(14) x k Пkac. Для перехода к следующему параллелепипеду П ac 1 может быть использован метод k проекции субградиента, описанный соотношениями (11).

Далее, аналогично алгоритму предыдущего пункта, для П ac 1 ре- k шается задача (12)(14) путем перехода к двойственной (15)(17) и на ходится последующее решение x k 1. Алгоритм завершает работу, ко гда xk 1 xk, т.к. в этом случае x k является решением задачи (1)(3).

Сходимость каждого из перечисленных методов решения задачи (1)(3) устанавливается известными способами [2], [3].

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Гаврилова М.О., Первадчук В.П., Севодин М.А. К задаче о наилучшем использовании ресурсов с переменной матрицей техноло гических коэффициентов // Сборник научных трудов. Шестая между народная научно-прикладная конференция. Варна, 2006.

2. Васильев Ф.П. Численные методы решения экстремальных за дач. – М.: Наука, 1988. – 552 с.

3. Зангвилл У. Нелинейное программирование. Единый подход. – М.: Советское радио, 1973. – 312 с.

4. Обен Ж.-П. Нелинейный анализ и его экономические прило жения. – М.: Мир, 1988. – 264 с.

Вестник ПГТУ. Прикладная математика и механика, УДК 336. А.А. РЫБАКОВ Пермский государственный технический университет МОДЕЛИРОВАНИЕ ДЕЛЬТА-НЕЙТРАЛЬНОГО ДИНАМИ ЧЕСКОГО ХЕДЖИРОВАНИЯ Предметом исследования являются изменения опционных коэффици ентов и характеристик при операциях покупки и продажи деривативов на ор ганизованном биржевом рынке. Построена модель системы, обеспечивающей торговлю волатильностью. Оптимизированы параметры модели. Сформиро ваны хедж-интервалы на основе параметров «дельта» и «историческая вола тильность», а также выявлено поведение оптимального шага рехеджирова ния на этих интервалах. Даны практические рекомендации инвестору по из менению шага дельта-хеджирования при переходе из одного хедж-интервала в другой, решающие проблему управления риском и получения дохода в ус ловиях как падающего, так и растущего рынка.

Современный российский рынок ценных бумаг находится на ста дии интенсивного развития. Ежегодно растет ликвидность рынка, новые компании осуществляют размещение ценных бумаг, доля ВВП, распре деляемая через рынок ценных бумаг, растет. При этом, наиболее широ кий круг инвесторов действует на фондовом рынке, в силу молодости и неразвитости рынка производных финансовых инструментов. Однако во многих странах мира (США, Германия, Япония) объемы торгов на срочном рынке значительно превышают объемы фондового рынка. Воз никновение такого дисбаланса было поэтапным. Исторически необхо димость действовать в условиях неопределенности и привела к появле нию срочных контрактов, определяющих условия сделки в будущем.

Многие производные бумаги создавались именно с целью снижения риска потерь от будущего изменения цены. С развитием биржевой тор говли появлялись новые инструменты, торговые обороты по ним росли, и со временем возникла новая функция – спекулятивная. Производные ценные бумаги начинают включаться в портфель не только для сниже ния рисков, но и с целью получения спекулятивного дохода. В XX в.

на стыке финансов, математики и компьютерных технологий возникает новая наука – финансовый инжиниринг. Предметом науки, в частности, является создание новых финансовых инструментов, управление риска Вестник ПГТУ. Прикладная математика и механика, ми и прибылью за счет создания торговых стратегий. Благодаря разви тию этой науки, появились опционные стратегии торговли волатильно стью.

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

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

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

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

Единственной площадкой проведения опционной торговли явля ется рынок ФОРТС. Перед нами встает выбор инструментов для заня тия позиций. На основании сравнительного обзора рынка по степени ликвидности представляется разумным конструировать портфель из опциона колл на фьючерс на индекс РТС и базового актива.

Вестник ПГТУ. Прикладная математика и механика, Таким образом, мы определились с типом стратегии, финансовы ми инструментами и местом реализации стратегии. Прежде чем стро ить модель торговой системы, перечислим ее ключевые параметры:

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

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

Мы находимся в рамках модели Блэка Шоулза [1]. В соответст вии с ней С SN (d1 ) Ke( rt ) N (d2 ) ;

(1) S ln( ) (r )t K 2;

d1 (1.1) t S ln( ) (r )t K 2 d t, d2 (1.2) t где C теоретическая премия по опциону колл;

S текущая цена базовых активов;

t время, остающееся до срока истечения опцио на, выраженное как доля года (количество дней до даты истече ния/365 дней);

K цена исполнения опциона (цена страйк);

r – без рисковая ставка;

N(x) – функция стандартного нормального распре деления;

е – экспонента;

2 – дисперсия доходности базового актива Вестник ПГТУ. Прикладная математика и механика, (доходность измеряется в виде ставки непрерывных процентов);

– волатильность (годовое стандартное отклонение).

Историческую волатильность будем находить по формуле (2)[2]:

n n ui2 ( ui ) V k, i 1 i (2) n-1 n(n-1) pi натуральный логарифм отношения двух последова где ui ln pi тельных цен;

k – годовое количество интервалов, принимаемых к рас чету.

Ценовые значения примем медианными, т.е. равным среднему арифметическому между максимальным и минимальным значением бара. Волатильность будем выражать в процентах. Вычисление коэф фициентов дельта и гамма будем производить с использованием фор мул (3) и (4) соответственно.

C Delta N (d1 ) ;

(3) S N (d1 ) e d1 0, 2C Delta Gamma 2, (4) S S S V T S V 2T где T – срок опциона.

Затраты на приобретение соответствуют биржевым и комиссион ным вознаграждениям, связанным с открытием и закрытием позиций.

Поскольку мы не используем маржируемые опционы, то вариационная маржа начисляется ежедневно и только по фьючерсам. Вариационная маржа рассчитывается по следующим формулам [3]:

ВМо = (РЦт – Цо) W / R;

(5) ВМт = (РЦт – РЦп) W / R, (6) где ВМо – вариационная маржа по контракту, по которому расчет ва риационной маржи ранее не осуществлялся;

ВМт – вариационная маржа по контракту, по которому расчет вариационной маржи осуще ствлялся ранее;

Цо – цена заключения контракта;

РЦт – текущая (по следняя) расчетная цена контракта;

РЦп – предыдущая расчетная цена Вестник ПГТУ. Прикладная математика и механика, контракта (или начальная расчетная цена контракта);

W – стоимость минимального шага цены (курс доллара США используется с точно стью, устанавливаемой Центральным Банком РФ);

R – минимальный шаг цены.

Остальные параметры не рассчитываются, их значения общедос тупны. Расчетная цена, спот публикуются на официальном сайте ФОРТС, страйк и срок жизни выбираются из числа доступных инст рументов. Дивиденды мы принимаем равными нулю, безрисковая ставка 7 % годовых (на основании доходности по долгосрочным госу дарственным облигациям). Обменный курс принимаем постоянным на все время существования стратегии и равным официальному курсу Банка России на день вхождения в рынок. Это, во-первых, упростит модель, а во-вторых, избавит от потенциальных «шумов», искажаю щих прибыль за счет колебаний курса.

Чтобы систематизировать процессы и расчеты, присутствующие в модели, построим для начала общую блок-схему (рис. 1).

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

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

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

Нейтрализация портфеля по дельте позволит зафиксировать прибыль, войдя в риск-нейтральное состояние.

Вестник ПГТУ. Прикладная математика и механика, Заметим, что под входом в рынок будем понимать занятие ретро спективных позиций, т.к. модель тестируется на исторических данных.

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

Начало Данные о торгах Выбор деривати вов Выбор момента входа в рынок Нахождение оп тимального шага Оптимальный шаг Конец Рис. 1. Общая блок-схема поиска оптимального шага дельты Шаг будем называть оптимальным, если он обеспечивает макси мальную вариационную маржу, накопленную на конец периода. Таким образом, определим вариационную маржу, накопленную на момент Вестник ПГТУ. Прикладная математика и механика, завершения стратегии, как целевую функцию, максимизируемую в на шей модели.

Детализированная блок-схема представлена на рис. 2. Реализация алгоритма осуществлена на языке Visual Basic for Applications.

Исходными данными являются информация о торгах по фьючер сам RTS06.09 и RTS09.09, а также по опционам со всеми возмож ными страйками на эти фьючерсы. Поскольку временным распадом мы пренебрегаем, то стратегия формируется на 3 мес. по опционам, дата истечения которых отдалена минимум на 3 мес. после завершения стратегии. Сначала расчеты проводились на дневных интервалах, но при этом игнорировались внутридневные колебания. Построенная стратегия является спекулятивной, т.е. с использованием дневных ба ров прибыльность снижалась. Переход на 5-минутные графики привел к тому, что вследствие низкой ликвидности рынка длительные перио ды проходили без сделок, т.е. бары превращались в прямые линии (рис. 3 и 4). Очевидно, волатильность на таком интервале равна нулю, что в корне искажало результаты и делало модель неприменимой. Рас чет волатильности за более длительные периоды (50 свечей и более) не улучшил ситуацию. Тестирование на различных периодичностях баров привело к решению о переходе на получасовые (30-минутные) графи ки. Это позволило применять модель с большей степенью точности (рис. 5). Расчет волатильности производится по данным 30 предыду щих баров (свечей).

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

Вестник ПГТУ. Прикладная математика и механика, Рис. 2. Детализированная блок-схема определения оптимального шага рехеджирования Вестник ПГТУ. Прикладная математика и механика, Рис. 3. Дневной график торгов фьючерса на индекс РТС RIM Рис. 4. 5-минутный график торгов фьючерса на индекс РТС RIM Вестник ПГТУ. Прикладная математика и механика, Рис. 5. 30-минутный график торгов по фьючерсу на индекс РТС RIM Тестирование стратегии на разных инструментах позволило сде лать еще одно важное наблюдение. Ликвидность инструментов увели чивается при приближении их к состоянию «около денег», в то время как опционы вне денег или в деньгах с длительным сроком до испол нения могут торговаться на ничтожных объемах.

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

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

Таким образом, оптимизация параметров модели включала в се бя:

Вестник ПГТУ. Прикладная математика и механика, 1. Выбор наиболее подходящих инструментов (параметров).

2. Выбор наиболее подходящего времени существования страте гии.

3. Выбор наиболее подходящей периодичности ценовых рядов.

4. Выбор наиболее целесообразного метода расчета и оценки во латильности.

5. Выбор наиболее подходящего времени реализации стратегии.

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

Таблица Численные характеристики распределения оптимального шага по интервалам Волатильность (20 %;

60 %] (60 %;

100 %] Гамма (0,8105;

1,6105] M1[x] = 0,25 M2[x] = 0, 1 1 = 0,003 2 =0, (1,6105;

2,6105] M3[x] =0,16 M4[x] = 0, 3 3 = 0,005 4 = 0, Результаты вычислений можно интерпретировать следующим образом: при попадании в высоковолатильный интервал с высокой гаммой оптимальный шаг рехеджирования минимален. Следовательно, требуется частое хеджирование для максимальной фиксации прибыли.

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

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

Вестник ПГТУ. Прикладная математика и механика, Таблица Рекомендации корректировки шага рехеджирования в зависимо сти от хедж-интервала В 1 2 3 Из Х Уменьшить Уменьшить Уменьшить Увеличить Х Уменьшить Уменьшить Увеличить Увеличить Х Уменьшить Увеличить Увеличить Увеличить Х Итак, даны практические рекомендации для изменения шага ре хеджирования при реализации стратегии длинной дельта-нейтральной торговли волатильностью. Чтобы оценить целесообразность и приме нимость таких рекомендаций, а также значимость полученных резуль татов, выделим преимущества и недостатки исследования.


Преимущества.

1. Рекомендуемые действия по изменению шага рехеджирования не были найдены автором в существующих научных публикациях. С определенной уверенностью можно утверждать научную новизну вы явленного поведения оптимального шага дельты в хедж-интервалах.

2. Очевидна практическая значимость результатов: применение не ограничивается будущими научными изысканиями. Формирование и реализация стратегий нацелены, в первую очередь, на извлечение спекулятивной прибыли. Соблюдение рекомендаций может способст вовать конструированию более эффективной стратегии торговли вола тильностью.

3. Сравнительно большое количество тестирований свидетель ствует о снижении случайной составляющей выявленных тенденций 4. Расчеты модели в большой степени автоматизированы.

5. Модель может быть усовершенствована внесением простых корректив в алгоритм.

6. В абсолютном большинстве случаев реализация стратегии обеспечивала положительную накопленную вариационную маржу.

После обработки данных получено математическое ожидание до ходности стратегии, равное 4,55 % (что эквивалентно 18,2 % годовых).

Среднеквадратическое отклонение при этом составило 0,98 %. Рассчи таем коэффициент вариации Вестник ПГТУ. Прикладная математика и механика, x 0,98 % K var 0,215.. (7) M [ x] 4,55 % Таким образом, величина риска характеризуется значением 21, %. Отметим достаточно неплохое соотношение риска и доходности.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Black F., Scholes M. The Pricing of Options and Corporate Lia bilities // Journal of Political Economy. 1973. № 81 (3) С. 637–654.

2. Чекулаев М.А. Риск-менеджмент: управление финансовыми рисками на основе анализа волатильности. – М.: Альпина Паблишер, 2002. – 344 с.

3. Правила совершения срочных сделок открытого акционерного общества «Фондовая биржа РТС»: Решение Совета директоров ОАО «Фондовая биржа РТС» от 15 апреля 2009 года, Протокол № 09-08 1504. URL: www.rts.ru..

Вестник ПГТУ. Прикладная математика и механика, УДК 517. В.Ю. МИТИН Пермский государственный университет РАЗЛИЧНЫЕ ПОДХОДЫ К ВЫЧИСЛЕНИЮ ИНДЕКСА НУЛЕВОЙ ИЗОЛИРОВАННОЙ ОСОБОЙ ТОЧКИ ВЕКТОРНОГО ПОЛЯ И ИХ РЕАЛИЗАЦИЯ ДЛЯ НЕКОТОРЫХ КЛАССОВ ПЛО СКИХ ВЕКТОРНЫХ ПОЛЕЙ Рассмотрены различные методы вычисления индекса нулевой изолиро ванной особой точки векторного поля. Для плоских векторных полей, обра зованных многочленами степени не выше 2, предложен полный алгоритм вы числения индекса нулевой изолированной особой точки. Рассмотрены также частные случаи плоских векторных полей, образованных многочленами бо лее высоких степеней, среди которых основное внимание уделено векторным полям с ненулевой вырожденной производной Фреше.

Пусть плоское непрерывное векторное поле Ф с компонентами P(x,y) и Q(x,y), т.е. непрерывное отображение Ф: R2 R2, определено на замыкании ограниченной области МR2 и не вырождено (нигде не обращается в нуль) на ее границе. Тогда вращение (Ф, М) на границе Г области М численно равно количеству целых оборотов, совершаемых вектором Фz, в то время пока точка z = x,y совершает полный обход по кривой Г в положительном направлении. В книге [1] описаны раз личные подходы к определению понятия «вращение», которые могут быть применены и к векторным полям в любых конечномерных про странствах.

Пусть a R2 – изолированная особая точка векторного поля Ф (нули будем тоже относить к числу особых точек и рассматривать только этот класс особых точек). Тогда вращение векторного поля Ф на границе любого круга, внутри которого нет других особых точек, будет равняться одному и тому же числу, которое называется индексом изолированной точки a поля Ф и обозначается ind(a, Ф). Доказательст во корректности данного определения приведено, например, в книге [1].

Не теряя общности, можно ограничиться рассмотрением случая a =, поскольку этого всегда можно добиться путем простой замены переменных.

Вестник ПГТУ. Прикладная математика и механика, При вычислении индекса нулевой изолированной особой точки (у неизолированных особых точек индекса не существует) могут пред ставиться два случая.

1) Определитель производной Фреше (матрицы Якоби) не об ращается в нуль в точке. Этот случай назовем «регулярным». Индекс нулевой особой точки при этом выражается простой формулой:

ind(, Ф) = sign det Ф' (), (1) где Ф' – производная Фреше векторного поля Ф.

2) Определитель производной Фреше (матрицы Якоби) обраща ется в нуль в точке. Этот случай назовем «критическим». Простые общие формулы для произвольных конечномерных векторных полей в критическом случае неизвестны. Для плоского векторного поля суще ствуют алгоритмы, обладающие достаточной степенью общности, од нако использование их обычно приводит к громоздким вычислениям.

К ним относятся, в частности, использование формулы Пуанка ре, приведенной и доказанной в книге [1] (Ф(z) = Ф([z(t)]), t[a,b]):

P(t )Q '(t ) Q(t ) P '(t ) b (Ф, Г) (2) dt, P 2 (t ) Q 2 (t ) a а также алгоритмы вычисления искомого индекса путем определения вращения векторного поля на границах некоторых элементарных кри вых. Приведем один из подобных алгоритмов.

Алгоритм вычисления вращения на замкнутой кривой:

Пусть Г – замкнутая кривая, заданная уравнением z = z(t), при ус ловии t[a,b] z(a)=z(b);

Ф – непрерывное векторное поле без нулевых векторов на Г.

1. Находим P(t)=P(z(t)) и Q(t)=Q(z(t)).

2. Находим все корни функции Q на [a,b).

3. Из найденных корней функции Q отбираем только те значения t, для которых Р(t)0.

4. По множеству отобранных корней tk находим числа:

n1 – количество точек, где Q убывает, n2 – количество точек, где Q возрастает, 5. Вычисляем вращение: (Ф, Г)= n2 – n1.

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

В связи с этим возникает необходимость исследования новых методов вычисления индекса изолированной особой точки, которые бы были более наглядны и просты в применении, допускали перенос на пространства бльших размерностей, позволяли взглянуть на одну и ту же проблему с разных сторон, были достаточно эффективны хотя бы в некоторых частных случаях. При изучении таких методов были ис пользованы идеи из книг [1] и [2].

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

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

метод гомотопий, алгебраический метод, метод малых деформаций, геометрический метод.

Наиболее эффективные методы помещены в начало списка. Да дим краткую характеристику каждого метода.

Метод гомотопий. Основная идея метода состоит в переходе от исходного векторного поля Ф к векторному полю В, гомотопному ис ходному полю на сферах достаточно малого радиуса. Из того, что го мотопные векторные поля имеют одинаковые вращения (см., напри мер, книгу [1]), можно заключить, что индексы нулевых изолирован ных особых точек Ф и В одинаковы. Для того чтобы использование данного перехода было небессмысленным, индекс нулевой изолиро ванной точки векторного поля В должен находиться непосредственно Вестник ПГТУ. Прикладная математика и механика, либо, по крайней мере, проще, чем для векторного поля Ф. Поскольку гомотопность – отношение эквивалетности, в частности, транзитивное отношение, то можно осуществлять несколько гомотопических пере ходов.

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

Рассмотрим несколько простых примеров (нижние индексы со ответствуют порядку однородности слагаемых).

m Pi ( x, y ) x x i 2 Пример 1. Векторные поля B = k и Ф = k n y y xRk 1 Q j ( x, y ) j k гомотопны на сферах достаточно малого радиуса с центром в нуле.

Гомотопность сохранится, если к компонентам поля добавить слагае мые более высоких порядков малости.


m k Pi ( x, y ) Pr ( x) Пример 2. Векторные поля Ф = и i k r k n y xRk 1 Q j ( x, y ) j k k Pr ( x) B= гомотопны на сферах достаточно мало r k n y xRk 1 Q j ( x, y ) j k го радиуса с центром в нуле.

Алгебраический метод. Основная идея метода состоит в исполь зовании алгебраических преобразований компонент поля, которые со храняют свойства изолированности особой точки и не изменяют ее ин декса либо изменяют его известным образом. Рассмотрим несколько наиболее простых и полезных преобразований.

А) Перестановка переменных плоского векторного поля меняет знак индекса его нулевой изолированной особой точки на противопо ложный. Аналогичный эффект получается при перестановке компо нент плоского векторного поля. Для многомерных векторных полей Вестник ПГТУ. Прикладная математика и механика, использование таких преобразований опирается на теорию перестано вок и подстановок (см., например, книгу [3]). Именно при каждом та ком преобразовании индекс умножается на (1) k, где k – число инвер сий в соответствующей перестановке, т.е. для четной перестановки ин декс не меняется, а для нечетной умножается на 1.

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

В) Умножение одной или нескольких компонент векторного по ля на знакопостоянное в окрестности нулевой изолированной особой точки выражение. Если множитель положителен, то индекс не меняет ся, если отрицателен, индекс меняет только знак.

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

Метод малых деформаций. Основная идея метода состоит в том, чтобы преобразовать посредством малого возмущения векторного поля при помощи одного или нескольких положительных параметров нуле вую изолированную особую точку, соответствующую критическому случаю, в несколько регулярных изолированных особых точек, индекс которых может быть найден по формуле (1). Тогда индекс нулевой изолированной особой точки исходного векторного поля равен сумме индексов полученных регулярных изолированных особых точек, что следует из теоремы об алгебраическом числе особых точек, приведен ной в книге [1].

Метод малых деформаций применим и для конечномерных век торных полей в пространствах большей размерности.

При использовании метода малых деформаций можно исполь зовать следующий алгоритм.

Алгоритм метода малых деформаций:

1. Задать малую деформацию векторного поля Ф с помощью ма лых положительных параметров i.

Вестник ПГТУ. Прикладная математика и механика, 2. Решить систему уравнений, которая получится, если прирав нять компоненты к нулю.

3. Выписать решения полученной системы (для двумерного слу чая с одним параметром: xi = xi(), yi = yi(), zi = xi, yi).

4. Найти производную Фреше Ф' векторного поля Ф.

5. Определить значения sign det(Ф') во всех точках, cчитая, что +0. Если хотя бы для одной точки получилось sign det(Ф'(zi)) = 0, предложить новую деформацию (вернуться к пункту 1).

6. Иначе ind(, Ф) равен сумме выражений sign det(Ф' (zi)), где суммирование происходит только по тем точкам, компоненты которых остаются бесконечно малыми при +0.

Приведем простейший пример, иллюстрирующий использование метода.

x2 y Пример. Пусть дано векторное поле Ф =. Найти ин y декс его изолированной особой точки.

Решение. Заметим, что изолированная особая точка соответст 0 0. Воспользуемся вует критическому случаю, т.к. det (Ф' ()) = методом малых деформаций. Добавим ко второй компоненте положи тельный параметр. Получим следующую систему уравнений:

x 2 y y Решения этой системы:, 0, –, 0.

2 x 2 x.

det(Ф') = 0 Для первой точки: –2 (функция sign принимает значение –1).

Для второй точки: 2 (функция sign принимает значение 1).

Имеем: –1+1 = 0, следовательно, индекс изолированной особой точки равен 0.

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

Вестник ПГТУ. Прикладная математика и механика, Геометрический метод. Основная идея метода состоит в рас смотрении соответствия между плоским векторным полем c компонен тами P(x,y) и Q(x,y) (для простоты ограничимся случаем многочленов) и парой плоских кривых, описываемых в декартовой системе коорди нат уравнениями P(x,y) = 0 и Q(x,y) = 0. Иногда по их виду и взаимно му расположению можно найти индекс нулевой изолированной особой точки или, по крайней мере, его модуль.

Рассмотрим несколько примеров.

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

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

Использование геометрического метода особенно удобно для плоских векторных полей, образованных многочленами степени не выше 2, поскольку этот случай опирается на классические математиче ские теории – линейную геометрию и теорию кривых второго порядка.

Геометрический смысл функции комплексного переменного zzn (nN) и геометрическое истолкование понятия «вращение» по зволяют без лишних вычислений сделать непосредственный вывод о том, что индекс нулевой изолированной особой точки векторного поля Re( z n ) Ф= Im( z n ) равен n.

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

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

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

Пусть векторное поле имеет вид:

Вестник ПГТУ. Прикладная математика и механика, A x 2 B1 xy C1 y 2 D1 x E1 y F Ф 1 A x B xy C y 2 D x E y F. (3) 2 2 2 2 Для вычисления индекса нулевой изолированной особой точки векторного поля вида (3) можно использовать следующий алгоритм.

1. Убедиться в том, что – изолированная особая точка (для не изолированных особых точек понятие индекса не существует).

2. Если обе компоненты линейные, то перейти к пункту 3. Если одна компонента линейная, другая имеет степень 2, то перейти к п. 4.

Если обе компоненты имеют степень 2, то перейти к п. 5.

3. ind(, Ф) = sign det Ф'(). Вычисление завершено.

4. Вычислить det Ф'(), ind(, Ф) = sign det Ф'(). Вычисление завершено.

5. Найти Ф'(). Если Ф'() невырожденная матрица, то ind(, Ф) = sign det Ф' (). Вычисление завершено. Если Ф'() нулевая мат рица, то перейти к п. 6. Если Ф'() ненулевая вырожденная матрица, то перейти к п. 8.

6. Определить четыре числа:

D1 = A1B2 – B1A2;

D2 = B1C2 – C1B2;

D3 = A1C2 – C1A;

D = D1D2 – 4D32.

7. Если D 0, то ind(, Ф) = 0. Вычисление завершено.

Если D 0, D1 0, то ind(, Ф) = 2. Вычисление завершено.

Если D 0, D1 0, то ind(, Ф) = –2. Вычисление завершено.

8. Определить тип производной Фреше (буквами обозначены не нулевые элементы).

D1 0 0 – перейти к п. 8.1.

0 D 0 – перейти к п. 8.2.

2 0 E 0 0 – перейти к п. 8. Вестник ПГТУ. Прикладная математика и механика, 0 0 E – перейти к п. 8.4.

D1 E 0 0 – перейти к п. 8.5.

0 D E – перейти к п. 8.6.

2 D1 D 0 – перейти к п. 8.7.

2 0 E 0 E – перейти к п. 8.8.

D1 E1 D D E – вычислить k = D, перейти к п. 8.9.

2 2 8.1. Если С1 0, то ind(, Ф) = 0. Вычисление завершено.

Если С1 = 0, то ind(, Ф) = –sign(C1B2D1). Вычисление завершено.

8.2. Если С2 0, то ind(, Ф) = 0. Вычисление завершено.

Если С2 = 0, то ind(, Ф) = sign(C2B1D2). Вычисление завершено.

8.3. Если A2 0, то ind(, Ф) = 0. Вычисление завершено.

Если A2 = 0, то ind(, Ф) = sign(A1B2E1). Вычисление завершено.

8.4. Если A1 0, то ind(, Ф) = 0. Вычисление завершено.

Если A1= 0, то ind (, Ф) = –sign(A2B1E2). Вычисление завершено.

E1 E 8.5. Если A2 2 B2 1 C2 0, то ind(, Ф) = 0. Вычисление за D D вершено.

E1 E Если A2 2 B2 1 C2 = 0, то ind(, Ф) = D D E2 E B E B2 2 C2 ) ( 1 2 A =фsign(( A2 ).

D D2 D D Вычисление завершено.

E E 8.6. Если A1 2 2 B1 2 C1 0, то ind(, Ф)=0. Вычисление за D D вершено.

Вестник ПГТУ. Прикладная математика и механика, E2 E B1 2 C1 =0, то ind(, Ф) = Если A1 iD D2 B E E E =sign(( A2 2 2 B2 2 C2 )( 1 2 A1 )). Вычисление завершено.

D D2 D D D 8.7. Если (C2 2 C1 ) 0, то ind(, Ф) = 0. Вычисление заверше D но.

D D Если (C2 2 C1 ) = 0, то ind(, Ф) = –sign(С1D1 ( В2 2 B1 ) ).

D1 D Вычисление завершено.

E 8.8. Если ( A2 2 A1 ) 0, то ind(, Ф) = 0. Вычисление заверше E но.

E E Если ( A2 2 A1 ) = 0, то ind(, Ф) = sign(A1E1 ( В2 2 B1 ) ). Вы E E числение завершено.

E12 E 8.9. Если ( A2 kA1 ) 2 ( B2 kB1 ) 1 (C2 kC1 ) 0, то ind(,Ф) = 0.

D1 D Вычисление завершено.

E2 E Если ( A2 kA1 ) 12 ( B2 kB1 ) 1 (C2 kC1 ) = 0, то ind(, Ф) = D1 D B kB E12 E E B1 1 C1 )( 2 2( A2 kA1 ) 12 )). Вычисление = –sign(( A1 D1 D1 D1 D завершено.

Замечание. Если одна из компонент векторного поля равна нулю (т.е. многочлену, не имеющему степени), то индекс особой точки, в случае ее изолированности, равен нулю. Если одна из компонент – многочлен нулевой степени, то нулевая точка не может быть особой.

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

Методы, описанные выше, часто оказываются полезными при вычислении индекса нулевой изолированной особой точки векторных полей, образованных многочленами более высоких степеней, чем вто рая. Например, они достаточно эффективны для исследования вектор ных полей вида:

Вестник ПГТУ. Прикладная математика и механика, P( x, y ) A1 x B1 x y C1 xy D1 y E1 x F1 xy G1 y x 3 2 2 3 2 Ф= =. (4) Q( x, y ) A2 x B2 x y C2 xy D2 y E2 x F2 xy G2 y 3 2 2 3 2 Используя линейную замену переменных, к виду (4) нетрудно привести любое векторное поле, образованное многочленами третьей степени без квадратичной части с ненулевой вырожденной производ ной Фреше.

Представим компоненты векторного поля Ф в виде суммы од нородных слагаемых:

P(x,y) = a3(x,y) + a2(x,y) + x;

Q(x,y) = b3(x,y) + b2(x,y).

(нижний индекс соответствует степени однородного слагаемого). Для них удобно сочетать элементарные преобразования поля с использова нием теоремы из книги [2], основанной на гомотопическом переходе:

Теорема. Пусть b1(x,y) = … = bk-1(x,y) = 0, bk(0,1) 0. Тогда осо бая точка изолированна и справедлива формула:

1 (1)k ind(, Ф)= sign bk (0, 1). (5) Если для векторного поля вида (4) непосредственное примене ние формулы (5) невозможно, то его можно попытаться привести к ви ду, описанному в условии теоремы, с помощью нескольких преобразо ваний вида Г) из алгебраического метода. Полученное при этом зна чение k является порядком малости однородных слагаемых, опреде ляющих индекс нулевой изолированной особой точки векторного поля.

Максимальный порядок малости однородных слагаемых, определяю щих индекс, равен 9 (проверено, что для аналогичных векторных полей с многочленами степени n он равен n2).

Для векторных полей вида (4) при построении алгоритма вы числения индекса нулевой изолированной особой точки, в зависимости от коэффициентов поля, наибольшую сложность представляют «за труднительные случаи»:

1. G2 = 0, D2 0, G1F2 = D2;

2. G2 = 0, D2 = 0, G1F2 = 0, R1(x,y) 0, P2(x,y) 0;

3. G2 = 0, D2 = 0, F2 = 0, R1(x,y) 0, P2(x,y) = 0;

4. G2 = 0, D2 = 0, G1C2 = 0, R1(x,y) = 0, P2(x,y) 0;

5. G2 = 0, D2 = 0, G1C2 = 0, R1(x,y) = 0, P2(x,y) = 0, R2(x,y) 0, P3(x,y) 0, Вестник ПГТУ. Прикладная математика и механика, Q( x, y ) D2 y где R(x,y)= =R1(x,y)+R2(x,y) – разложение в сумму одно x родных многочленов.

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

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Красносельский М.А., Забрейко П.П. Геометрические методы нелинейного анализа. М.: Наука. 1975.

2. Красносельский М.А. Векторные поля на плоскости / Красно сельский [и др.]. М.: Физматгиз, 1963.

3. Курош А.Г. Курс высшей алгебры. М.: Наука, 1971.

Вестник ПГТУ. Прикладная математика и механика, СОДЕРЖАНИЕ И.П. МОСКАЛЕНКО, М.А. СЕВОДИН О ПОСТРОЕНИИ ОБОБЩЕННОГО ПОКАЗАТЕЛЯ ФИНАНСОВОЙ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ............................................................................ М.А. СЕВОДИН, Е.С. СМИРНОВА О РОЛИ СПЕКУЛЯЦИЙ В УСТАНОВЛЕНИИ РАВНОВЕСНОЙ ЦЕНЫ........... Т.Ф. ПЕПЕЛЯЕВА, С.В. ИВАНКИНА ФИНАНСОВОЕ ПЛАНИРОВАНИЕ КОММЕРЧЕСКОГО БАНКА...................... Д.Б. ШУМКОВА, О.В. ЧЕРДЖИЕВА ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ПРОЦЕССА ВЫТЯЖКИ ОПТИЧЕСКОГО ВОЛОКНА................................................................................................................... В.А. СОКОЛОВ, А.Ю. ФОМИНА ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ МОДЕЛИ ВАЛЬРАСА – ЭВАНСА – САМУЭЛЬСОНА С УЧЕТОМ ЗАВИСИМОСТИ СПРОСА И ПРЕДЛОЖЕНИЯ ОТ СКОРОСТИ ИЗМЕНЕНИЯ ЦЕНЫ.................................. Е.В. БРЮХОВА, Т.А. ОСЕЧКИНА ПРОГНОЗИРОВАНИЕ ГОСУДАРСТВЕННОГО ДОЛГА: МОДЕЛИ И ОЦЕНКИ...................................................................................................................... И.В. МОРДОВИНА, Т.А. ОСЕЧКИНА ФОРМИРОВАНИЕ ОПТИМАЛЬНОЙ КОРЗИНЫ ВАЛЮТ.................................. А.Р. ДАВЫДОВ, М.Ю. ЧЕРЕНКОВА СТАТИСТИЧЕСКИЙ КОНТРОЛЬ КАЧЕСТВА ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА.................................................................................................................. В.А. ОНЯНОВ, М.В. ШАДРИН ЧИСЛЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О ВЫТЯЖКЕ ПОЛЫХ КВАРЦЕВЫХ ВОЛОКОН.......................................................................................... С.Ю. КУЛТЫШЕВ, Л.М. КУЛТЫШЕВА ПРИБЛИЖЕННАЯ ИДЕНТИФИКАЦИЯ ПРИ ИЗМЕРЕНИЯХ С ПОГРЕШНОСТЯМИ............................................................................................... В.Ю. СОКОЛОВ К ВОПРОСУ О РЕЛАКСАЦИИ НАПРЯЖЕНИЙ В ГОРНОМ МАССИВЕ В ОКРЕСТНОСТИ ВЫРАБОТКИ............................................................................. И.П. НЕПОРОЖНЕВ РАСКРАСКИ РЕБЕР ПОЛНОГО 5-ВЕРШИННОГО ГРАФА БЕЗ ПЕТЕЛЬ........ Вестник ПГТУ. Прикладная математика и механика, И.П. НЕПОРОЖНЕВ МИНИМАЛЬНЫЕ И БЛИЗКИЕ К МИНИМАЛЬНЫМ РАСКРАСКИ РЕБЕР ОБЫКНОВЕННОГО ПОЛНОГО 6-ГРАФА............................................................. В.Н. КЕТИКОВ, А.М. ФЕДОСЕЕВ ПОЛУЧЕНИЕ НЕКОТОРЫХ ЭКСТРЕМАЛЬНЫХ ХАРАКТЕРИСТИК СЛОЖНЫХ ХИМИЧЕСКИХ РЕАКЦИЙ................................................................. В.П. КАРАНДАШОВ, Е.В. ЗАДОРОЖНАЯ РЕШЕНИЕ ЗАДАЧИ ОБ ОПТИМАЛЬНОМ ВЫБОРЕ РИСКОВЫХ СИТУАЦИЙ В СТРАХОВАНИИ..................................................................................................... В.П. КАРАНДАШОВ, А.А. МАТВЕЕВА МЕТОД СЦЕНАРИЕВ В ОЦЕНКЕ ИНВЕСТИЦИОННЫХ ПРОЕКТОВ........... М.Г.БОЯРШИНОВ, Н.В.ПЕТЕРЛЕВИЧ ОЦЕНКА ЭФФЕКТИВНОСТИ «ЗАРПЛАТНОГО» (КАРТОЧНОГО) ПРОЕКТА КОММЕРЧЕСКОГО БАНКА................................................................................... М.Г. БОЯРШИНОВ, О.С. САЛИХОВА ОПТИМАЛЬНАЯ ЗАГРУЗКА БАНКОМАТА ДЕНЕЖНЫМИ КУПЮРАМИ... Г.А. ПУШКАРЕВ ОБ ОДНОМ ЧАСТНОМ СЛУЧАЕ ФУНКЦИОНАЛЬНО ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ 1-ГО ПОРЯДКА................................ Л.Я. ЛЬВОВСКИЙ К ВОПРОСУ О ДЕЛЕНИИ МНОГОЧЛЕНОВ....................................................... Г.В. СОКОЛОВ АНАЛИЗ АЛГОРИТМОВ АВТОМАТИЧЕСКОЙ УКЛАДКИ ГРАФОВ НА ПЛОСКОСТИ В РАМКАХ ЗАДАЧИ ВИЗУАЛИЗАЦИИ МОДЕЛЕЙ НА ГРАФАХ.............................................................................................................. М.О. ГАВРИЛОВА О ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С КУСОЧНО ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ............................................................ А.А. РЫБАКОВ МОДЕЛИРОВАНИЕ ДЕЛЬТА-НЕЙТРАЛЬНОГО ДИНАМИЧЕСКОГО ХЕДЖИРОВАНИЯ.................................................................................................... В.Ю. МИТИН РАЗЛИЧНЫЕ ПОДХОДЫ К ВЫЧИСЛЕНИЮ ИНДЕКСА НУЛЕВОЙ ИЗОЛИРОВАННОЙ ОСОБОЙ ТОЧКИ ВЕКТОРНОГО ПОЛЯ И ИХ РЕАЛИЗАЦИЯ ДЛЯ НЕКОТОРЫХ КЛАССОВ ПЛОСКИХ ВЕКТОРНЫХ ПОЛЕЙ..................................................................................................................................... Вестник ПГТУ. Прикладная математика и механика, Научное издание ВЕСТНИК ПГТУ ПРИКЛАДНАЯ МАТЕМАТИКА И МЕХАНИКА № Редакторы и корректоры Л.В. Лыкова, Е.В. Богомягкова, Н.А. Московкина Подписано в печать 10.12.2009. Формат 70100/16.

Тираж 100 экз. Заказ № 251/2009.

Издательство Пермского государственного технического университета.

Адрес: 614990, г. Пермь, Комсомольский пр., 29, к. 113.

Тел. (342) 219-80-33.



Pages:     | 1 |   ...   | 2 | 3 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.