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

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

СКЕЛЕТНЫЙ АЛГОРИТМ

РЕШЕНИЯ ОБОБЩЕННОЙ ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ЕГО

ПРИМЕНЕНИЕ В ЗАДАЧАХ КОРРЕКЦИИ ДВИЖЕНИЯ

И ПЛАНИРОВАНИЯ ЭКСПЕРИМЕНТА

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва – 2010

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Хаметов Владимир Минирович кандидат физико-математических наук, доцент Рыбаков Константин Александрович

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

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

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

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

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

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

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

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

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

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

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

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

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

К обобщенным задачам линейного программирования более сложного вида сводятся также задачи M V - и E-оптимального планирования эксперимента и задача робастного оценивания (эти результаты были получены М.И. Войсковским).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кибзуна (МАИ, 2010), Механика, управление и информатика под руководством проф. Р.Р. Назирова (Институт космических исследований РАН, 2009).

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

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

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

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

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

Рассмотрим задачу линейного программирования Здесь xi скалярные переменные оптимизации; остальные параметры являются заданными: ci столбцы матрицы уравнений относительно xi, b Rm вектор правой части, причем b = 0. Величину L будем называть значением задачи (1).

Пусть IB множество из m индексов столбцов допустимого базиса {ai, i IB }, т.е. xi ai = b, xi 0 и векторы базиса линейно незавиiIB симы. Вектор, состоящий из компонентов xi, i IB, называют базисным вектором, а вектор x = (x1,..., xn ), содержащий все компоненты базисного вектора (и имеющий, очевидно, равными нулю остальные компоненты), называется допустимым базисным решением. Обозначим Сопоставим задаче (1) задачу линейного программирования с одним дополнительным столбцом a0 и дополнительной переменной x0 :

Теорема 1) Допустимое решение x0 = 1, x1 = 0,..., xn = 0 задачи (2) дает то же значение целевой функции, что и базисное решение задачи (1), соответствующее базису {ai, i IB }, т.е. L = L.

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

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

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

любое решение уравнения 0 a0 = 0, любой вектор, для котоb рого совместны ограничения во вспомогательной задаче (3), а векторы ai находятся по формулам Теорема Если задача (3) имеет решение, то текущее вырожденное базисное решение эквивалентной задачи (2) оптимально.

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

Пусть IB состоит из индексов столбцов, входящих в текущий базис B вспомогательной задачи (3). Из теории линейного программирования известно, что если целевая функция задачи (3) не ограничена на множестве допустимых решений, то на некотором шаге симплекс-метода находится небазисный вектор ap, такой, что коэффициенты j его разложения по базису, определяемые однозначно из уравнений удовлетворяют неравенствам Обозначим Q = {j : j IB, pj < 0}.

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

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

В противном случае ( > 0) при замене строгого базиса a0 на векторы {ap, ai, i Q} целевая функция задачи (2) уменьшается на величину.

Указанное в теореме 3 уменьшение будет мало по сравнению с модулем текущего значения L целевой функции (итерация является почти вырожD| денной), только если мала величина. Однако в этом случае, отличие текущего значения целевой функции от ее минимума есть C, где велиL| чина C сравнима с единицей. Это означает, что при малой величине (т.е. при появлении почти вырожденной итерации) мы находимся вблизи оптимума. Если же не малая величина, то уменьшение целевой функL| ции в задаче (2) также не мало. В этом состоит основное преимущество предлагаемого ниже метода по сравнению с симплекс методом, не гарантирующим отсутствие почти вырожденных итераций.

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

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

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

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

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

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

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

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

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

Как только найдено k такое, что k > 0, j 0, j < k, переходим к шагу 4.

Шаг 4. Спуск.

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

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

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

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

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

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

В работе рассматривается распространенный частный случай, когда множества Ai имеют вид Ai = {a : a = Pi, = 1}.

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

Основное отличие состоит в том, что при построении вспомогательных задач не требуется вычислять и хранить в памяти все массивы столбцов ai размерности от m 1 до 1. Фактически процедура построения серии вспомогательных задач сводится к рекуррентному вычислению матриц Pi и векторов ui, которые определяют коэффициенты ci (ci = ui ).

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

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

В разделе 2.3 диссертационной работы получена оценка сверху для разности между значениями целевой функции на текущем решении и наилучшем среди допустимых базисных решений и оценка снизу для улучшения целевой функции на каждой итерации алгоритма. Эти оценки позволяют сформулировать и доказать следующую теорему Теорема Для каждой из вспомогательных задач решение, обеспечивающее значение целевой функции, отличное от обеспечиваемого наилучшим допустимым базисным решением, не более чем на, может быть найдено не более чем за итераций, где M и N числа, все более точK ные оценки которых вычисляются на каждой итерации (под итерацией понимается последовательность спусков и подъемов, приводящих к очередному улучшению значению целевой функции).

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

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

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

Наконец, в пятом разделе разбирается задача L-оптимального планирования эксперимента.

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

Таблица 1.

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

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

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

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

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

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

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

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

4) Bakhshiyan B.Ts., Goryainov A.V. A New Linear Programming Algorithm for Optimal Estimation and Correction of an Aircraft Trajectory // 4th International Scientic Conference on Physics and Control, PHYSCON 2009, Catania, Italy. Electronic Publication. P. 1-6.

http://lib.physcon.ru/?item= 5) Бахшиян Б.Ц., Горяинов А.В. Об алгоритме нахождения выпуклой оболочки конечного множества векторов. // Тезисы докладов международной конференции по математической теории управления и механике 2009. Суздаль, 2009. С. 39- 6) Бахшиян Б.Ц., Горяинов А.В. Решение задачи оптимальной линейной идеальной коррекции траектории летательного аппарата с помощью скелетного алгоритма. // Тезисы докладов VIII международной конференции Авиация и космонавтика. Москва, 2009. С. 7) Горяинов А.В. Новый алгоритм решения обобщенной задачи линейного программирования и его применение для коррекции траектории движения летательного аппарата // Тезисы докладов XIV международной конференции Системный анализ управление и навигация. Евпатория, 2009. С. 8) Горяинов А.В. О сходимости скелетного алгоритма решения обобщенной задачи линейного программирования. // Тезисы докладов XV международной конференции Системный анализ управление и навигация. Евпатория, 2010. С. 146-