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

604612603

На правах рукописи

Горяинов Александр Владимирович

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

05.13.01 - Системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2010 ^ 1 НОЯ 2010

004612603

Работа выполнена на кафедре «Теория вероятностей» Московского авиационного института (государственного технического университета) МАИ

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

старший научный сотрудник Бахшиян Борис Цолакович

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

профессор Хаметов Владимир Минирович

Защита состоится «12» ноября 2010 г. в 12 ч. 00 мин. на заседании Диссертационного совета Д.212.125.04 при Московском авиационном институте по адресу: 125993, г. Москва, Волоколамское шоссе, д. 4.

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

кандидат физико-математических наук, доцент Рыбаков Константин Александрович

Ведущая организация: Московский государственный технический

университет им. Н.Э. Баумана

Ученый секретарь Диссертационного совета Д 212.125.04, кандидат физико-математиче

М.В. Ротанина

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Различные задачи теории планирования эксперимента рассматриваются в книгах В.В. Налимова, В.В. Федорова, С.М. Ермакова, A.A. Жиг-лявского, В.Б. Меласа, Ф. Пукельсгейма, а также в работах М.Л. Ли-

дова, М.Б. Малютова, В.Н. Соловьева и других авторов. Применение в теории планирования эксперимента методов линейного программирования рассматривается в работах Г. Элфвинга, П.Е. Эльясберга, БД. Бахшпяпа, P.P. Назирова, М.И. Войсковского, В.Н. Соловьева. Задача L-оптимального планирования эксперимента сводится, как показали Б.Ц. Бахшиян и В.Н. Соловьев, к задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий. Последняя же в работах M.JI. Лидова была сведена к обобщенной задаче линейного программирования. К обобщенным задачам линейного программирования более сложного вида сводятся также задачи MV- и ^-оптимального планирования эксперимента и задача робастного оценивания (эти результаты были получены М.И. Войсковским).

Задачи обобщенного линейного программирования, рассматривались еще П. Вулфом и Дж. Данцигом, которые предложили для их решения метод генерации столбцов, представляющий собой модификацию симплекс-метода. Дальнейшее развитие этот алгоритм получил в работах Л.С. Лэ-сдона, М. Мину и других авторов. В отличие от обычных задач линейного программирования, для обобщенных задач достаточные условия оптимальности могут не выполняться ни на одной итерации метода генерации столбцов, и число итераций метода обычно бесконечно. Поэтому для прекращения вычислений используется понятие е-оптимальности, для проверки которой применяются оценки, позволяющие установить степень близости текущего значения целевой функции к оптимальному. Примеры таких оценок для целевых функций специального вида можно найти в работах М.Л. Лидова, Б.Ц. Бахшияна, А.И. Матасова, К.С. Федяева.

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

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

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

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

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

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

Достоверность результатов обеспечивается

1) строгостью постановок и доказательств утверждений;

2) корректным использованием математических моделей современной теории линейного программирования;

3) рассмотрением численных примеров, которые демонстрируют достоверность полученных теоретических результатов.

Научная новизна работы.

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

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

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

4. Проведен сравнительный анализ различных алгоритмов решения обобщенных задач линейного программирования.

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

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях: Международная конференция по математической теории управления и механике. (Суздаль, 2009); XIV Международная конференция «Системный анализ управление и навигация» (Евпатория, Украина, 2009); IV Международная научная конференция по физике и управлению (International Scientific Conference on Physics and Control, PHYSCON) (Катания, Италия, 2009); VIII Международная конференция «Авиация и космонавтика» (Москва, 2009); XV Международная конференция «Системный анализ управление и навигация» (Евпатория, Украина, 2010), а также на научных семинарах под руководством проф. А.И. Кибзуна (МАИ, 2010), «Механика, управление и информатика» под руководством проф. Р.Р. Назирова (Институт космических исследований РАН, 2009).

Публикации. Основные результаты диссертации опубликованы в 2 статьях [1,2] в журналах, входящих в перечень ВАК, статьях в других журналах [3], сборниках трудов [4] и тезисов [5-8] научных конференций.

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

СОДЕРЖАНИЕ РАБОТЫ

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

G

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

Рассмотрим задачу линейного программирования

inn ^

L* = min < L — CjXi : ^^ зад = b, Xi > 0, г = 1,..., п > . (1)

I i=i i=i J

Здесь Xi — скалярные переменные оптимизации; остальные параметры являются заданными: с* — коэффициенты целевой функции, а; € Km — столбцы матрицы уравнений относительно а:;, 6 6 К™ — вектор правой части, причем Ь ф 0. Величину L* будем называть значением задачи (1).

Пусть /в — множество из т индексов столбцов допустимого базиса {а,-, г € /д}, т.е. Y1 xia* = b, Xi > 0 и векторы базиса линейно незави-

Шв

симы. Вектор, состоящий из компонентов Xi, г € Iß, называют базисным вектором, а вектор х = (xi,...,, содержащий все компоненты базисного вектора (и имеющий, очевидно, равными нулю остальные компоненты), называется допустимым базисным решением. Обозначим

«0 = ЗД =Ь, С{) = <kxi-

Шв Шв

Сопоставим задаче (1) задачу линейного программирования с одним дополнительным столбцом ао и дополнительной переменной Хо:

{п п ^

L = COXQ + ^CjXj : xqüq + = 6, Xi > 0, г = 0,1, ...,п > .

¡=i i=i )

(2)

Теорема 1

1) Допустимое решение хо — l,xi = 0, ...,хп = 0 задачи (2) дает то же значение целевой функции, что и базисное решение задачи (1), соответствующее базису {a*, i 6 1в}, т.е. L = L.

2) Значения задач (1) и (2) совпадают, т.е. L* = L*.

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

вырожденности т — 1 (только одна компонента хо = 1 положительна в текущем базисном решении).

Рассмотрим вспомогательную задачу линейного программирования с т—1 независимыми ограничениями-равенствами:

Здесь Ci = Ai = c¡ — tt'üí — так называемая относительная оценка, ir

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

Теорема 2

Если задача (3) имеет решение, то текущее вырожденное базисное решение эквивалентной задачи (2) оптимально.

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

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

(3)

— любое решение уравнения До — 7г'оо = О, Ь — любой вектор, для кото-

(4)

удовлетворяют неравенствам

¿e'é

Обозначим Q = {j : j 6 I¡¡, aPJ < 0}.

Теорема 3

Пусть задача (3) неразрешима.

Тогда если а < 0, то целевая функция задачи (2) не ограничена па множестве своих допустимых решений, т.е. задача (2) неразрешима. В противном случае (а > 0) при замене строгого базиса ао на векторы

{а„,щ, г € <2} целевая функция задачи (2) уменьшается на величину -—-.

(X

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

текущего значения целевой функции от ее минимума есть сЩгг, где вели-

\Ц

чина С сравнима с единицей. Это означает, что при малой величине

\Ц

(т.е. при появлении почти вырожденной итерации) мы находимся вблизи Ю\

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

Будем называть размерностью задачи число ее ограничений-равенств (т.е. размерность векторов-столбцов матрицы ограничений). Дальнейшая идея состоит в том, что решение задачи (2) (имеющей размерность т — 1) аналогично можно свести к решению задачи размерности т — 2, потом перейти к задаче размерности т — Зч т.д. При этом далее мы воспользуемся правом произвольно выбирать правую часть ограничений во вспомогательных задачах меньшей размерности из условия их совместности. Естественно, мы выберем правую часть равной одному из столбцов матрицы ограничений и сразу получим вырожденное базисное решение со строгим базисом из одного вектора. Это позволит сразу без дополнительных вычислений получить эквивалентную расширенную задачу.

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

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

Таким образом, пошаговое описание скелетного алгоритма имеет следующий вид.

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

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

Шаг 2. Решение одномерной задачи.

Решаем одномерную задачу. Если она разрешима, то переходим к шагу 5, в противном случае — к шагу 3.

Шаг 3. Подъем.

Из соотношений между векторами ао вспомогательных задач, последовательно вычисляем коэффициенты ау, $ = 1,2,3..., характеризующие разрешимость вспомогательной задачи размерности ]. Если а^ > 0, вспомогательная задача размерности j разрешима, если 04 < 0 — неразрешима. Как только найдено к такое, что а* > 0, <0, ] < к, переходим к шагу 4.

Шаг 4. Спуск.

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

при этом не установлено, разрешима ли задача. Это означает, что значение целевой функции можно улучшить. Новое значение вычисляется как линейная комбинация коэффициентов с,- целевой функции (коэффициентами линейной комбинации служат вычисленные на шаге 3 числа а;). Коэффициенты линейной комбинации запоминаются и хранятся в памяти вплоть до окончания следующего «подъема». После этого пересчитываем коэффициенты с; целевой функции для вспомогательных задач размерности к — 1, к — 2,..., 1 и переходим к шагу 2.

Шаг 5. Окончание решения задачи.

Решение задачи дает текущий строгий базис задачи размерности т.

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

\Ц

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

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

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

В работе рассматривается частный случай, когда множества А{ имеют вид

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

А = {а:а = Ра, 1Ы1 = 1}-

Основное отличие состоит в том, что при построении вспомогательных задач не требуется вычислять и хранить в памяти все массивы столбцов а; размерности от т — 1 до 1. Фактически процедура построения серии вспомогательных задач сводится к рекуррентному вычислению матриц Р* и векторов щ, которые определяют коэффициенты С{ (с; = и[7).

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

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

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

Теорема 4

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

не более чем за - итераций, где М и N — числа, все более точ-

м + к

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

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

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

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

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

Сравнительная эффективность методов для задачи коррекции.

размерность задачи время, с

метод ген. столбцов скелетный алгоритм

2 0,8 0,6

3 2Д 1,0

4 4,2 2,8

5 4,1 3,3

6 8,1 5,9

7 12,3 8,4

8 16,1 13,5

9 21,6 11,3

Основные результаты диссертационной работы, выносимые на защиту

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

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

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

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

Публикации в журналах из перечня ВАК

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

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

Публикации в других изданиях

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

4) Dakhshiijan В. Ts., Goryainov А. V. A New Linear Programming Algorithm for Optimal Estimation and Correction of an Aircraft Trajectory // 4th International Scientific Conference on Physics and Control, PHYSCON 2009, Catania, Italy. Electronic Publication. P. 1-6. http://lib.physcon.ru/?item=1916

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

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

7) Горяинов A.B. Новый алгоритм решения обобщенной задачи линейного программирования и его применение для коррекции траектории движения летательного аппарата // Тезисы докладов XIV международной конференции «Системный анализ управление и навигация». Евпатория, 2009. С. 25

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

Подписано в печать:

24.09.2010

Заказ № 4222 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499)788-78-56 www.autoreferat.ru

Введение

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. Например, это имеет место для рассмотренной нами минимаксной задачи оценивания, для которой возможные моменты измерений заполняют отрезок.

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

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

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.