Скелетный алгоритм решения обобщенной задачи линейного программирования и его применение в задачах коррекции движения и планирования эксперимента тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Горяинов, Александр Владимирович

• Горяинов, Александр Владимирович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Горяинов, Александр Владимирович

Введение

0.1. Основные сведения из теории линейного программирования

0.1.1. Постановка задачи. Симплекс-метод.

0.1.2. Вырожденность решения

0.2. Обобщенные задачи линейного программирования.

0.2.1. Постановка задачи и алгоритм решения.

0.2.2. О сходимости алгоритма генерации столбцов.

0.3. Цели и структура работы.

1. Скелетный алгоритм решения задачи линейного программирования

1.1. Теоретические основы алгоритма.

1.1.1. Расширенная и вспомогательная задачи.

1.1.2. Построение серии вспомогательных задач.

1.1.3. Основные теоремы.

1.2. Описание итераций.'.

1.2.1. Решение одномерной задачи.

1.2.2. Подъем и спуск.

1.3. Пошаговое описание алгоритма.

2. Модификация скелетного алгоритма для обобщенной задачи линейного программирования

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

2.2. Пошаговое описание алгоритма.

2.3. О сходимости скелетного алгоритма.

3. Применение скелетного алгоритма

3.1. Преодоление проблемы вырожденных итераций

3.1.1. Случай вырожденного решения.

3.1.2. Случай почти вырожденного решения.

3.2. Нахождение выпуклой оболочки конечного числа векторов . 67 3.2.1. Численные эксперименты.

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

3.3.1. Постановка задачи и ее сведение к обобщенной задаче линейного программирования.

3.3.2. Численные эксперименты.

3.4. Задача оптимальной идеальной линейной импульсной коррекции траектории.

3.4.1. Постановка задачи и ее сведение к обобщенной задаче линейного программирования.

3.4.2. Численные эксперименты.

3.5. Задача ^-оптимального планирования эксперимента.

3.5.1. Постановка задачи и сведение к обобщенной задаче линейного программирования.

3.5.2. Численные эксперименты.

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

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

К задачам линейного программирования сводится множество практических задач, встречающихся в разных областях экономики и техники. Теоретическая и практическая сторона решения задачи линейного программирования на сегодняшний день хорошо разработана (см., например, [34,41]), однако отдельные вопросы, связанные с так называемой проблемой вырожденности были разрешены не так давно [4, 12, 15]. Полученные в рамках борьбы с вырожденностью результаты представляют самостоятельный интерес и являются основой для предлагаемого в настоящей работе нового алгоритма.

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

Различные задачи теории планирования эксперимента рассматриваются в работах [14,24,27,32,38,50]. Применение в теории планирования эксперимента методов линейного программирования рассматривается в работах [12-14, 16,17]. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится задача Ь-оптимального планирования эксперимента [14]. К обобщенным задачам линейного программирования более сложного вида сводятся задачи МУ- и Е'-оптимального планирования эксперимента и задача робастного оценивания [6,16].

Задачи обобщенного линейного программирования, впервые рассмотренные в [23], обсуждались затем в работах [4, 13, 25, 28, 29]. Алгоритм решения обобщенной задачи линейного программирования, называемый методом генерации столбцов, представляет собой модификацию симплекс-метода [23, 33]. В отличие от обычных задач линейного программирования, для обобщенных задач достаточные условия оптимальности текущего решения могут не выполняться в силу бесконечного числа векторов условий. Поэтому для прекращения вычислений используется ионятие е-оптимальности, для проверки которой применяются оценки, позволяющие установить степень близости текущего значения целевой функции к оптимальному. Примеры таких оценок для целевых функций специального вида можно найти в работах [4,12,15,25].

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

0.1. Основные сведения из теории линейного программирования

0.1.1. Постановка задачи. Симплекс-метод

Приведем теперь основные сведения из теории линейного программирования в соответствии с работами [34,41]. Будем рассматривать следующую задачу линейного программирования (далее для удобства эту задачу будем называть основной): по заданным векторам аг-, Ъ £ И771', г = 1,п, с £ М"', найти вектор х* £ Мп такой, что здесь и далее штрихом обозначается операция транспонирования).

Оптимальное значение с'х* целевой функции далее будем называть значением задачи (1). Будем также считать, что линейная оболочка векторов ах, .,ап совпадает с К771, иначе следует перейти к соответствующему подпространству.

Любую систему т линейно независимых столбцов щ будем называть базисом, матрицу В, составленную из этих столбцов — базисной матрицей. Определим вектор хв £ по формуле

1) хв = В'Ч.

2)

Вектор х — (х'в, 0,., 0)' будем называть базисным решением задачи (1). Если при всех г выполняется условие Х{ > 0, то решение будем называть допустимым.

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

Перенумеровав при необходимости переменные, приведем матрицу А = (аь ., ап) к виду

А = (В,ЛГ), где N - матрица размерности т х (п — га). Соответственно разобьем векторы х и с: х> = (х'в> х'ы) с' = (с5> сд/0

Рассмотрим вспомогательный вектор тг (вектор двойственных переменных для задачи (1)):

7Г ' = с'вВ~1.

Тогда справедливо равенство с'вхв = с'вВ~1Ь = п'Ь.

Рассмотрим также вектор относительных оценок:

Д' = с' - тх'А. (3)

Пусть х — текущее допустимое базисное решение, соответствующее базису В. Рассмотрим произвольное допустимое решение х ф х и найдем значение целевой функции с'х: dx = с'х + (с'вх в — тг 'Ъ) = с'вхв + (с'х — -к' Ах) = с'вхв + (с' — п'А)х = с'х +

4)

Отсюда следует, что текущий базис В оптимален тогда и только тогда, когда

А'х >0 Ух ф х. (5)

В частности, достаточным условием оптимальности является условие

А > 0.

Предположим, что это достаточное условие не выполняется, т.е. существует номер s такой, что As < 0. Увеличивая значение компоненты xs вектора ж, как следует из формулы (4), мы будем уменьшать значение целевой функции. При этом, однако, должно выполняться условие

Вхв + asxs = b, откуда хв = В~1(Ь-а3ха) > 0 или хв — хв — axs > 0, где a = B~1as. Из последнего неравенства находим min < — : а{ > 0 > — в = — 1<г<т l^ttj J аг максимально возможное значение хшЧ, при котором вектор х остается допустимым. Если же оц < 0 при всех 1 < г < т, то компоненту xs можно неограниченно увеличивать, не нарушая при этом условий допустимости. Из формулы (4) следует, что в этом случае целевая функция с'х неограни-чена. В остальных случаях, полагая xs = в, получим хг = 0 и с'х = с'х + А'х = с'х + А'дгЖдг = с'х + As9, так как А'в = с'в — ж'В = 0.

На основе изложенных выше рассуждений основан симплекс-метод: итерационный алгоритм нахождения оптимального решения х* задачи (1). Ш аг 1.

Пусть В — некоторый базис, допустимый для задачи (1). Вычисляется вектор 7Г из условия тг' = dBB~\ (6)

Ш а г 2.

Вычисляется вектор Д относительных оценок по формуле (3). Заметим, что условие (6) эквивалентно условию

Ав = св- 7Г'В = 0, поэтому на практике при заданном базисе В вычисляют только вектор

А N — (Am+i,., Ап)'. Ш а г 3.

Вычисляется минимальная относительная оценка

Amin = A.s = min Д?;. (7) m+l<i<n

Ш а г 4.

Проверяется достаточное условие оптимальности

Amin > 0. (8)

Если это условие выполняется, то текущий базис В оптимален, и вычисления завершаются. В противном случае столбец as вводится в базис. Ш а г 5.

Вычисляется вектор а = B~las координат вектора as в базисе В, и ищется величина

0 = min /— : > ol . (9)

OLr 1<г<т [ 0¿i J

Если вектор а не содержит положительных компонент, то целевая функция z(x) = с'х неограничена на множестве допустимых решений, и вычисления завершаются. В противном случае столбец аг выводится из базиса. Ш а г 6.

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

Xi = Xi — а{6, (10) z = z + Amine. (11)

9ij 9rj ar 5 г t1 r-, 1

9rj —, г = r, ar где gij - элементы матрицы B~l.

После этого происходит возврат к шагу 1. Новый допустимый базис В будет состоять из векторов щ, г = 1,., т, г г и вектора а.,.

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

В приведенных выше рассуждениях подразумевалось, что в матрице А всегда можно указать некоторый начальный допустимый базис В. Однако при решении практических задач непосредственно сделать это бывает невозможно. Для построения допустимого базиса задачи (1) применяются специальные методы, один из которых описан в [34]. Рассмотрим его более подробно.

Рассмотрим следующую вспомогательную задачу:

Г п т Л е'у* = min ie'y: ^ зд + ^ где» = 6, ж > О, 2/ > 0 > , (12)

Х,У I г=1 г=1 J где х G Шп — вектор переменных задачи, е G Шт — вектор с единичными компонентами, у G Mm — вектор вспомогательных переменных, называемых искусственными, ei,.^™ — столбцы единичной матрицы порядка т.

Задача (12) представляет собой задачу линейного программирования с матрицей условий размерности тх(п~\-т). Для этой задачи непосредственно можно указать допустимый базис, состоящий из столбцов ±еi,.,±em (знак при каждом столбце выбирается в зависимости от знака соответствующей компоненты вектора Ъ правых частей). В [34] показано, что если значение целевой функции е'у* на оптимальном решении задачи (12) положительно, то построение допустимого базиса задачи (1) невозможно, так как в задаче (12) такому базису соответствовало бы нулевое значение целевой функции е'у. Если же оптимальное значение целевой функции е'у* равно нулю, и оптимальный базис не содержит столбцов ±ei,.,±em, то этот базис, очевидно, является допустимым для задачи (1). Если же оптимальный базис задачи (12) содержит какие-либо из столбцов ±ei, .,=tem, то эти столбцы необходимо заменить на столбцы матрицы А. Если последнее возможно, то построенный таким образом базис (возможно вырожденный) будет допустимым для задачи (1). В противном случае ограничения этой задачи несовместны.

0.1.2. Вырожденность решения

Рассмотрим случай, когда в текущем базисном решении в векторе (2) присутствуют нулевые компоненты, т.е. вектор хв имеет вид (здесь и далее нумерация условна) хв = {xi,.,xk,0, .,0)'. (13)

В этом случае текущее допустимое базисное решение будем, следуя [12], называть вырожденным, а число m — к — степенью вырожденности.

Представим матрицу В в виде

В = (и,У), (14) где I/ — матрица размерности тх к, составленная из столбцов а.1,., а/-, V — матрица размерности т х (т — к), составленная из остальных столбцов матрицы В. Обозначим хи = (хи Тогда равенство (2) примет вид ихи = Ъ. (15)

Матрицу и будем называть матрицей строгого базиса [4] в отличие от составной базисной матрицы В = (£/, V). Пространство Мт раскладывается в прямую сумму

Жт= и® V подпространств Ы и V размерности к и гп — к соответственно, базисами которых являются столбцы матриц V и V. Иными словами, щ, г < к, ще Ы, VI Е V. (16)

Щ + Уг, % > к

Допустим, что на шаге 5 алгоритма симплекс-метода найдена положительная компонента вектора а с номером, большим к. В этом случае, очевидно,

0 = ^1 = 0 (г > к + 1). (17) аг

Это означает, что произведенный затем на шаге 6 алгоритма переход к новому базису будет чисто формальным. Фактические значения всех параметров задачи, как следует из формул (10)-(11), останутся прежними. Итерацию, для которой справедливо равенство (17), будем называть вырожденной, а само равенство (17) — критерием вырожденности.

Вырожденные задачи линейного программирования стали объектом изучения фактически сразу после возникновения линейного программирования как самостоятельной научной дисциплины. Однако в первое время вырожденность рассматривалась исключительно в контексте проблемы зацикливания симплекс-метода [23,41]. В подавляющем большинстве работ того периода указывалось, что на практике случаи вырождения весьма редки, а зацикливания при решении практических задач никогда не наблюдается (см., например, [41]). Проблема построения примеров зацикливания представляла самостоятельный научный интерес, этому вопросу посвящались отдельные работы как в начале развития теории линейного программирования (см. [44]), так и в дальнейшем (см., например, [48,53]).

Однако с развитием области применений линейного программирования и ростом размерности решаемых задач при практических расчетах все чаще стали возникать ситуации, когда зацикливания не происходило, однако на больших последовательностях итераций целевая функция не изменялась, или ее изменение было пренебрежимо мало. Это явление привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью. Однако большинство классических методов теории вырожденного линейного программирования по-прежнему было посвящено лишь борьбе с зацикливанием, избежать вырожденных итераций при использовании таких методов не удавалось. Указанные методы сводились либо к специальному выбору выводимого из базиса вектора [23], либо к выбору вводимого в базис вектора [47], либо к одновременному выбору обоих этих векторов [45]. Разрабатывались также методы, основанные на применении теории двойственности [43].

Первым методом, позволяющим эффективно преодолевать вырожденность, был метод А.Чарнса [46]. Он сводился к модификации правила выбора выводимой из базиса переменной в случае возникновения вырожденности. Следующим в череде предложенных методов борьбы с вырожденностью стал метод Вулфа, предложенный впервые в [52] и модифицированный в [51]. Суть метода состоит в решении построенной особым образом вспомогательной задачи, по итогам которого строится новое невырожденное решение. Однако метод Вулфа имеет два недостатка. Во-первых, размерность вспомогательной задачи совпадает с размерностью исходной. Во-вторых, при решении вспомогательной задачи также могут возникнуть вырожденные итерации, что приводит к необходимости рекурсивного применения предложенной процедуры. Б.Ц.Бахшияном в работе [4] был предложен другой алгоритм, сходный с алгоритмом Вулфа по подходу к преодолению вырожденности, но отличающийся по принципу построения вспомогательной задачи и по ее виду. Полученные в [4] результаты были развиты Б.Ц. Бахшияном, А.И. Матасовым и К.С. Федяевым в работах [12,15].

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

0.2. Обобщенные задачи линейного программирования

0.2.1. Постановка задачи и алгоритм решения

Рассмотрим следующую задачу оптимизации

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

XI > 0

18) по переменным Х{, так и по векторам Задача (18) получила название обобщенной задачи линейного программирования. замечание 0.1. Отметим, что даже в случае выпуклости множеств Л п условие = Ь делает множество допустимых решений задачи невыг—1 пуклым. Пусть 0 < А < 1 и (х«.^, •.,«£>) , XV = (**>, „?>,., <$) допустимые решения задачи (18), т.е. верно п. х<я>0, а^еАг, ^хФаФ =Ь, ¿ = 1,2. г=1

Тогда х®, а[3\ ., = Х^ = XX™ + (1 - \)Х® =

- (\х<П + (1 - Х)х^2\ Ха{1) + (1 - А)а?\ Аа£ + (1 - А)а<?) вообще говоря не является допустимым решением, так как п п

Е Л® = Е К' + (1 - А)*«И) Н" + (1 - А)а,И) * 6. г=1 г=1

В [23] задача вида (18) рассматривалась лишь для случая выпуклых множеств А, и называлась обобщенной задачей Вулфа. В монографии [13] рассматривался случай, когда Л{ представляли собой границы выпуклых множеств, и выполнялось условие с,- > 0. В работе [4] была разработана теория решения задачи (18) уже в общем виде, приведены теоремы о существовании ее решения, критерий оптимальности и общая идея алгоритма. Метод решения задачи (18) представляет собой модификацию симплекс-метода, в которой на каждом шаге вводимый базис вектор выбирается специальным образом. Процедура выбора состоит в том, что сначала из каждого множества Л{ выбирается «наилучший» вектор, а затем среди них находится вектор с минимальной относительной оценкой. Такой метод получил название метода генерации столбцов.

Рассмотрим алгоритм решения обобщенной задачи подробно. Прежде всего отметим, что методом генерации столбцов фактически решается видоизмененная задача (18), в которой условия а7; Е Aj Vi заменены условием ai Е U AjVi [28]. Поэтому в дальнейшем будем рассматривать задачу (18) з именно в такой постановке.

Пусть В — текущая базисная матрица задачи (18), х — соответствующее базисное решение. Обозначим через Xß множество индексов базисных компонент.

Алгоритм решения задачи (18) состоит из следующих шагов. Ш а г 1.

Находим вектор 7Г по формуле ж' = с'вВ~1. Ш а г 2.

Находим для каждого множества Aj, j — 1,.,п, и вектора а Е Aj величину Д(а) = с(а) — -к'а и ищем min А (а) = A(ö7')> a&Aj где äj — вектор, на котором достигается искомый минимум в последнем равенстве. Задача нахождения вектора äj решается отдельно для каждого вида множеств Aj. Ш а г 3.

Если Д1Пт = minA(äj) > Ü, то текущее решение задачи (18) оптималь-з ио. В противном случае обозначим s = arg min A(äj). Тогда вектор äs Е As з вводится в базис вспомогательной задачи. Ш а г 4.

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

Если индекс г определяется, то производится обычная итерация: вектор а3 вводится в базис вместо вектора аг. Если же при всех г выполняется условие щ < 0, то задача (18) не имеет решения.

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

0.2.2. О сходимости алгоритма генерации столбцов

На каждом шаге метода генерации столбцов целевая функция уменьшается на — 0Amjn. Отсюда получаем следующее утверждение. Утверждение 0.1.

Если 0Amin не стремится к нулю с увеличением числа итераций, то алгоритм сходится за конечное число шагов к оптимальному решению.

На практике случай, указанный в утверждении 0.1 обычно не имеет места. Рассмотрим другой случай. Утверждение 0.2.

Пусть задача (18) разрешима (т.е. целевая функция ограничена на множестве допустимых решений). Тогда, если ДШт стремится к нулю, то алгоритм сходится к оптимальному решению по функционалу. в = хг

Д7; = min(q — 7г'а), aeAt

19)

Утверждение 0.2 следует из известного неравенства [12]: с'х* > с'х + МАт{п, которое справедливо и для обобщенной задачи. Здесь постоянная М опреп деляется из условия х\ < М. г=1

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

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

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

0.3. Цели и структура работы

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

Диссертация объемом 93 листа состоит из введения, трех глав, заключения и списка литературы (53 наименования).

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Горяинов, Александр Владимирович

Основные результаты выносимые на защиту:

1) Разработан скелетный алгоритм решения задачи линейного программирования, не использующий операцию обращения матриц [11,42].

2) Предложенный алгоритм модифицирован для решения обобщенной задачи линейного программирования [8-10].

3) Доказана сходимость скелетного алгоритма. Таким образом, впервые предложен алгоритм, позволяющий за конечное число шагов получить приближенное решение обобщенной задачи линейного программирования с любой заданной наперед точностью [21,22].

4) С помощью предложенного алгоритма реализованы эффективные способы решения задач идеальной коррекции траектории и ¿/-оптимального планирования эксперимента [9,10,42].

Заключение

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

В первой главе были развиты результаты работ [12] и [15] и на их основе предложен алгоритм решения задачи линейного программирования, основанный на построении серии вспомогательных задач с меньшим числом ограничений.

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

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

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

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

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

Эффективность предложенного метода в ряде случаев подтверждается также результатами численного моделирования.

Список литературы диссертационного исследования кандидат физико-математических наук Горяинов, Александр Владимирович, 2010 год

1. Бажинов И.К., Почукаев В.Н. Оптимальное планирование навигационных измерений в космическом полете. - М.: Машиностроение, 1976.

2. Бахшиян Б.Ц. Выбор оптимальных моментов независимых траектор-ных измерений // Косм, исследования. 1970. Т.8. № 1. С. 3-?.

3. Бахшиян Б.Ц. Критерии оптимальности и алгоритмы решения вырожденной и обобщенной задач линейного программирования // Экономика и математические методы. 1989. Т. 28. №2. с. 314-324.

4. Бахшиян Б.Ц. Некоторые задачи оценки точности прогнозирования параметров траектории и алгоритмы их решения // Косм, исследования. 1974. Т. 12. № 6.

5. Б.Ц. Бахшиян, М.И. Бойсковский. О возможности эффективного решения задачи оценивания при линейных ограничениях на оцениваемый вектор// Известия РАН. Теория и системы управления. 2003. №4.

6. Бахшияи Б.Ц., Войсковский М.И., Пак Ч.В. Об оптимальной линейной идеальной коррекции при ограничениях на корректирующие импульсы //Космические исследования.1997.Т.35. № 4. С. 387-395.

7. Бахшиян Б.Ц., Горяинов A.B. Об алгоритме нахождения выпуклой оболочки конечного множества векторов. // Международная конференция по математической теории управления и механике. 2009. Суздаль. Тезисы докладов, с. 39-40

8. Бахшиян Б.Ц., Горяинов A.B. Решение задачи L-оптимального планирования эксперимента при помощи скелетного алгоритма. // Автоматика и телемеханика. 2010. №4. с. 3-15.

9. Бахшиян Б.Ц., Горяинов A.B. Решение задачи оптимальной линейной идеальной коррекции траектории летательного аппарата с помощью скелетного алгоритма. // 8-я Международная конференция «Авиация и космонавтика 2009». Москва. Тезисы докладов, с. 220

10. Бахшиян Б.Ц., Горяинов A.B. Скелетный алгоритм решения задач линейного программирования и его применение для решения оптимальных задач оценивания. // Вестник Московского авиационного института. 2008. Т. 5. т. с. 5-16.

11. Бахшиян Б.Ц., Матасов А.И., Федяев К. С. О решении вырожденных задач линейного программирования. // Автоматика и телемеханика. 2000. JM. с. 105-117.

12. Бахшиян Б.Ц., Назиров P.P., Элъясберг П.Е. Определение и коррекция движения. М.: Наука, 1980.

13. Бахшиян Б.Ц., Соловьев В.Н. Теория и алгоритмы решения задач L-и MV-оптимального планирования эксперимента. // Автоматика и телемеханика, 1998. №8. с. 80-96.

14. Бахшиян Б.Ц., Федяев К.С. О решении почти вырожденных и плохо обусловленных задач линейного программирования, возникающих при управлении системой. // Известия РАН. Теория и системы управления. 2005. №6. с. 77-88.

15. Войсковский М.И. Симплексный алгоритм поиска ^-оптимальных планов// Известия РАН. Теория и системы управления. 2001. №2. с. 7074.

16. Войсковский М.И. Симплексный алгоритм решения задачи MV-оптимального планирования эксперимента. // Препринт 1979 Института космических исследований РАН. 1998.

17. Войсковский A4.И, Меринов И.Е. Симплексный алгоритм решения минимаксной задачи оценивания//Препринт 1697 Института космических исследований АН СССР. 1990.

18. Голъштейн Е.Г Выпуклое программироание. Элементы теории. М.: Наука, 1989.

19. Горяинов A.B. О сходимости скелетного алгоритма решения обобщенной задачи линейного программирования. // Тезисы международной конференции «Системный анализ управление и навигация» 2010. Евпатория.

20. Горяинов A.B. О сходимости скелетного алгоритма решения обобщенной задачи линейного программирования. // Электронный журнал Труды Московского авиационного института. 2010. №41.

21. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966. (G.B.Dantzig. Linear Programming and Extensions. Princeton U.P., 1963.)

22. Ермаков С.M., Жиглявский A. A. Математическая теория оптимального эксперимента. M.: Наука, 1987.

23. Лидов М.Л. Математическая аналогия между некоторыми оптимальными задачами коррекции траекторий и выбора состава измерений и алгоритмы их решения. // Космические исследования. 1971. Т.9. №5. с. 687-706.

24. Лидов М.Л. О модификации симплекс-метода линейного программирования в случае вырождения. // Космические исследования. 1991. Т.29. № 4.

25. Лидов М.Л. Эффективный алгоритм решения задачи о выборе оптимальной программы измерений // Космические исследования. 1985. Т.23. №4. С. 499

26. Лидов М.Л. Бахшиян Б.Ц., M атасов А. И. Об одном направлении в проблеме гарантирующего оценивания // Космические исследования. 1991. Т.29. Вып.5. С.659-684.

27. Лэсдон Л. С. Оптимизация больших систем. М.: Наука, 1975.

28. Малышев В.В., Кибзун А.И. Анализ и синтез высокоточных систем управления летательными аппаратами. М.: Машиностроение, 1987.

29. Математическая теория планирования эксперимента /Под ред. Ермакова С.М. М.: Наука, 1983.

30. Мелас В. Б. Одна теорема двойственности и ^-оптимальность// Заводская лаборатория. Т.82. №3. С. 48-50.

31. Мину М. Математическое программирование. Теория и алгоритмы: пер. с фр. М.: Наука, 1990.

32. Муртаф А. Современное линейное программирование. М.: Мир. 1984. (A.Murtagh. Advanced Linear Programming: Computation and Practice. McGraw-Hill International Book Company, 1981.)

33. Пшеничный Б.Н. Необходимые условия экстремума.М.: Наука, 1982.

34. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

35. Тихомиров В.М. Выпуклый анализ. В книге: Современные проблемы математики, фундаментальные направления. Анализ-8, М.: ВИНИТИ, 1987, с. 5- 101.

36. Федоров В. В. Активные регрессионные эксперименты // Математические методы планирования эксперимента. Новосибирск: Наука, 1983.

37. Р. Хорн, Ч.Джонсон. Матричный анализ.М.:Мир, 1989.

38. Эльясберг П.Е. Измерительная информация: сколько ее нужно? как ее обрабатывать? М.: Наука, 1983.

39. Юдин Д.Б., Голъштейн Е.Г. Линейное программирование. Теория, методы и приложения. М.: Наука, 1969.

40. E.Barnes, V.Chen, B.Gopalakrishnan, E.L.Johnson. A least-squares primal-dual algorithm for solving linear program ming problems // Operation Research Letters. 2002. V. 30. P. 289-294.

41. Beale E.M.L. Cycling in the dual simplex algorithm. // Nav. Res.Logist.Quart, 1955, v.2, p.269-275.

42. Bland R.G. New finite pivot rules for simplex method // Math.Oper.Res. 1977. V.2. P.103-107.

43. Charnes A. Optimality and degeneracy in linear programming // Econometrica, 1952, V.20, P. 160-170.

44. Dantzig G.B. Making progress during a stall in the simplex algorithm // Linear Algebra and its Applications. 1989. V.114/115. P. 251-259.

45. S.I.Gass, S.Vinjamuri. Cycling in linear programming problems // Computers & Operations Research. 2004. No 31. P. 303-311

46. Kibzun A.I., Kan Yu.S. Stochastic Programming Problems (with Probability and Quantile Functions). John Wiley and Sons, Chichester-New York-Brisbane-Toronto- Singapore, 1996.

47. Pukelsheim F. Optimal design of experiments. New York: J.Wiley and Sons, 1993.

48. Ryan D.M., Osborne M.R. On the solution of higly degenerate linear programmes // Mathematical Programming, v.41, 1988.

49. Wolfe P. A technique for resolving degeneracy in linear programming // Journal Soc. Indust. Appl. Math., v.11, 1963.

50. P.Zdrnig. Systematic construction of examples for cycling in the simplex method // Computers k Operations Research. 2006. No 33. P.2247-2262.