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

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

Федяев Константин С'срюсвич

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

05 13 01 Системный анализ управчеиие и обработка информации

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

Москва 2007

003059085

Рлбоы выполнена в Институте космических исследовании РАН

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

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

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

Снротин Андрей Никочаевич

кандидат физико-математических наук Ахмедова Наталья Казанфаровна

Ведущая ортпизация Институт системного анализа РАН

Защита состоится 2007 г в ч1 60

г в

мни на заседа-

нии Диссертационного совета Д212 133 01 при Московском государственном институте электроники и математики но адресу 109028 Москва, Б Трехсвя-тнтельский пер , д 3/12

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

Ученый секретарь Диссертационного сове кандидат технических наук, доцент

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

Объект исследования G днссерьшноппои работе изучаются вырожденные почти вырожденные п ичо\о оби човчеиные задачи линейного npoi рам-мнроваиня и обобщенною чппепиою npoi раммпровапня

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

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

Первым методом позво мющнм эффективно преодочевать вырожденность быч метод А Чарпса Оп сводился к модификации правила выбора выводимой из базиса псрсменноп в сч\чае возникновения вырожденности Среди других методов борьбы с вырожденностью можно выдечить метод П Вочьфа основанный па случайном возмущении путевых базисных переменных, соответствующем преобразовании правых час теп oi раппченин и последующем решении почучепнон невырожденной задачи с измененным правилом выбора выводимой из базиса переменной В рез\ [ьтагс решения такой невырожденной задачи в неходноп задаче строится новый базпе соответствующий меньшему значению целевом срункцни, нчп делается вывод об оптимальности текущею базиса Таким образом метод Вочьфа требует решения па каждой вырождепноп итерации ве номен ате 1ыюй задачи лниеппою npoi раммпрова-нпя размерность котороп равна 1)азмсрпостп исходнон задачи В резучыазе н])оцссс поиска онтнмл 1ыюю решения исходной задачи становится строю монотонным

Друшм меюдом схоцплм с методом Вочьфа по подходу' к преодолечшю

вырождсшюсш по отминающимся 110 принципу построения вс помел атечыюп задачи и по ее ищу явчястся метод, предчожеппый Б Ц Бачшияном В этом методе вспомслатечьпая задача имеет размерность равную чис 1\ п\ чевых компонент вектора базисных переменных, тс строю меньшую размерности исходной задачи Это обстоитечьство дало основание предпочагать что ач-горитм Бахшняпа окажется на практике более эффективным чем алгоритм Вочьфа Однако ранее алгоритм Бахшняпа не был программно реализован что затрудни чо ио применение при решении практических задач

Несмотря на то что в задачах большой размерности вырожденность становится практически реальным явчепнем юраздо чаще ндб'подается так называемый с ч\ чай почти вырожденности ко!да в текущем базисном решении часть компонент оказывается бчизка к нулю В этом случае изменение цсчс-вой функции при переходе от базиса к базису становится пренебрежимо мало по сравнению с се тск\ щим значением При этом известные методы борьбы г вырожденное тыо вообще говоря, неприменимы так как малые компоненты базиспо1 о вектора все же отличны от нуля Пробчема почти вырожденности в настоящее время мало изучена несмотря на свою актуальность Среди рабог, в которых затрл1 ивалась эта пробчема, можно отметить работу М П Тндова (1991) в которой оценивалось изменение цечевой функции при обнулении малых компонент ба знс но1 о решения Решение проблемы почти вырожденное тп в задачах чиненною программирования явчяется основной темой настоящей работы

Ряд зад, 14 теории оценивания и пчанироваппя эксперимента сводится к задачам которые по виду напоминают задачи чинейиою программирования однако в них векторы условий-равенств не фиксированы, но выбираются произвочыго из некоторых заранее заданных множеств Такие задачи по iv-чшш название обобщенных (многонараметрпчсских) задач линейною программирования Методы решения обобщенных задач обсуждались в работах ДжДапцш а Ч 1эсдона М Мину, М П Лндова Б Ц Бахшняпа и др Решение таких задач иредставчяст собой реализацию в обобщенном чиненном программировании так называемого метода генерации столбцов Этот метод заключается в том что задачу обобщенною линейною программирования трактуют как обычимо задачу чинейного программирования с бесконечным числом векторов ус човнн и решают обычным симплекс-методом, выбирая на каждом ша1с вводимый вектор сначала по каждому из соответствующих множеств а затем выбирая панчучшнй вектор по всем множествам При этом в отличие от обычных задач лииейпо! о программирования дчя обобщенных задач дос гаточпые усчовпя оптпмачыюстн тек\щего базисного решения мси\т

нс выпо шяться в силу бесконечного числа векторов ■условий Поэтому дчя прекращения вычнепенни используется понятие Ег-ошнмальпосги, дня проверки которой применяются оценки, позволяющие установить степень близости текущею значения целевой функции к оптимальному Этот вопрос обсуждался в работах М П Чидова, Б Ц Бахшияна

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

Одной из обчастеп, в которых особенно широко применяются методы линейною про1 раммировапия, является математическая теория планирования эксперимента Различные задачи теории планирования эксперимента рассматриваются в работах В В Федорова, С М Ермакова А А Жиглявского В В Меласа Ф Пукельхсйма, М Л Лндова, В Н Соловьева Применение в теории планирования эксперимента методов линейного программирования рассматривается в работах Б Ц Бахшияна, РРНазирова, П Е Эльясбсрга, А И Матаеова, М И Войсковского, В Н Соловьева К задачам обобщенного линейною про1 раммировапия сводится, например, задача идеальной линейной импульсной коррекции К задаче оптимальной чпнсйной импучьспой коррекции со специально построенными матрицами ус ювнй (а следовательно, и к задаче обобщенного линейного программирования) сводится задача //-оптимальною планирования эксперимента К решению серии обобщенных задач линейного программирования может быть сведена задача МК-онти-мального планирования К обобщенным задачам чинейною программирования более счожпою вида сводятся задача ^-оптимальною планирования эксперимента и задача робастпого оценивания

Цели и задачи работы

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

2 Решение апало1 ичной пробчемы дчя обобщенных задач линейною программирования

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

4 Проведение сравнения алюритма преодочеиия вырожденности в задачах линейного нро1 раммировапия, предложенною Б Ц Бахшияном, с дрм 11-ми аналогичными алюрптмдмп

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

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

1 Разработан н программно реализован метод решения почти вырожденных задач линейного программирования

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

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

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

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

Апробация работы Результаты работы докладывались и обсуждались

на

- Воронежской весенней математической школе "Современные методы в теории краевых задач" ("Поитрягипскне чтения - VIII")(Воронеж, 1997),

- VI Международной конференции «Идентификация систем и задачи управления» БЮРГЮ '07 (Москва, 2007),

- научном семинаре "Управление и устойчнвость"нод руководством профессоров В Н Афанасьева, В Б Кочмановского, В Р Носова, МИЭМ (Москва,

2007)

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

IV Конференции молодых ученых «Фундаментальные и прикладные космические исследования» ИКИ РАН (Москва, 2007)

Публикации Основные результаты работы изложены в двух статьях и трех тезисах докладов на научных конференциях

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

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

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

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

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

тт|^с,:г, =Ь, х = (хь ,.!„)'>()|, (1)

п

1де с, коэффициенты функции :(.г) = которую будем далее назы-

1=1

вать и,(левой а, £ К"' векторы условии Ь вектор правых частей системы 01 раниченнй

*1ю6ую систему т линейно независимых векторов а, будем называть ба-тсом задачи (1) матрицу В составлсип} ю из этих векторов, соответству-ю1цсн бапинои матрицей 1 Размерность тп базиса будем называть размерностью задачи Вектор х в котором отчнчпы от нуля не более т компонент,

'Далее дчя упрощения из юления будем использовать выражение "базис В имея в впд\ базис составленный из векторов образмощих столбцы базисной матрицы В

будем называть базисным решением задачи (1) Еечп при всех г выполняется условие г, > 0 то решение будем называть допустимый Определим также веьтор базисных переменных хв G R'" по формуле

гв = В~1Ъ (2)

и вектор fß £ R'" коэффициентов целевой ф\нкции соответствующих компонентам вектора хв

Из теории линейною программирования счедует что решение задачи (1) может быть сведено к перебору всевозможных допустимых базисных решении и выбору среди них того для которою значение цечевоп функции z(x) минимально Идея симплекс-метода состоит в том чтобы сдсчать такой перебор паиравчеипым рассматривая па каждой посчсдующен итерации только те допустимые базисные решения па которых значение цечевой функции будет не бочьше чем на текущем допустимом базисном решении

Рассмотрим некоторый базис В обозначим через Zß множество индексов векторов входящих в базис, и рассмотрим соответствующее этому базису базисное решение х Для каждою из векторов «], п„ рассмотрим отиоси-тельпу ю оценку

Д, = А(а,) = с, - n'a,, (3)

1дс 7Г = (В~1)'св вектор двойственных переменных (очевидно, что Д, = О при i G 2ß ) Тогда зиачснпс цечевоп функции дчя произвольного допустимою решения х ф х связано с ее текущим значением соотношением

с^фО + ^Д.т, (4)

Из это1 о соотношения следует что достаточным ус човием оптимальности базиса В явчяется выполнение неравенства

min Д, = Д,шп > 0 (5)

Ее m это условие не выполняется то можно рассмотреть величину

0= —= mini— a, >ol, (6)

ar ieZß l^a, J

1де a = ß_1ns вектор коэффициентов разложения вектора as, на котором достигается минимум в (5), но векторам базиса Тома при замене в рассматриваемом базисе вектора аГ на вектор as цечевая функция уменьшается на величину |0ДШШ| В случае, когда все компоненты вектора a неположительны задача (1) не имеет конечною решения

Рассмотрим случай когда дчя текмцсчо базиса В вектор (2) содержит пулевые компоненты В этом случае текущее допустимое базисное решение будем называть выро неденны м чисто иучевых компонент вектора хв степенью выроэ/гдеииости а базис В вырожденным Рассмотрим множество Х+ = {г х, > 0} Гшда для вырожденного базиса \1+\ < \Тц\

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

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

{-г, ? е 1+, 1, 1е1в\1+,

0 иначе

Соответственно преобразуется вектор Ь правых частей системы охраиичс-нии рассматривается вектор

ЬП = Ь+ а,1„

<61Н\1+

где 1, с чучаппые чисча После этою рассматривается следующая вспомо-ычельиая задача линейною программирования

Ш111|ЁС'Т' ¿>% = Ь°. Х°>О| (7)

Решение задачи (7) проводится при \с ювии (6), преобразованном к виду

о-" Г 1

0 = — = Ш1п I — а, > 0 V а, -ет,дт+ [а, J

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

Б Ц Бахшияпом быч нредчожен дрмоп метод решения вырожденной задачи линейного про1 раммировання основанный на построении вспомогательной задачи размерность которой строю меньше размерности основной зада-чп (1)

П\сть I матрица составчспная из векторов «,, / 6 Хв\£+- соотвситв\-ющнх нучевым компонентам вектора хв, V = £{У) нодпросгранство размерности т — к, натянутое на сточбцы матрицы V, 5' матрица перехода пз пространства И"1 в подпространство V

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

где у € вектор переменных задачи, Д, отноентечьные оценки

Ъ,1 = 5а, Е V образы векторов а,, г € 1, ,п\Х+, с/ е К'"'к нроизвочь-ный вектор правых частей задаваемый из условия совместности ограничений В сч\час, когда существует конечное решение задачи (8), текмцпй базис В исходной задачи оптимален В противном сл\.'1ас в задаче (1) может быть построен новый базис путем замены группы векторов текмцею базиса этой задачи векторами а,, 1 6 5, где 5 некоторое множество индексов, |<5| < гп — к + 1 Доказано, что при таком переходе происходит строх ое уменьшение значения цечевой функции на величину, пропорциональную значению любой из выводимых переменных

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

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

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

зультатов приведенных в главе 1 Рассмотрим этот алгоритм более подробно Дчя этою рассмотрим некоторый текущий базис В и дчя упрощения из поженил будем считать что Хд = {1, т} (к такому случаю легко сводится общий сл\чан п) тем соответствующей перенумерации переменных)

Предпо южпм что в тск\ щем решении (2) задачи (1) компоненты гд.ц, х„ малы по сравнению с компонентами хь ,хд (здесь, как и выше нумерация Условна) Рассмотрим множество индексов в которое включим индексы к + 1, ,т всех малых компонент вектора базисных переменных и один индекс </, соответствующий немалой компоненте (д < к + 1) Рассмотрим вектор

Яо = £ А,а,. Л, = (9)

К1

Зададим соответствующий этому вектору коэффициент целевой функции

со = ^>с< 11 рассмотрим следующую расширенную задачу линейною нро-

/е х,

граммироваппя

пин < ^^ г*1!* '/<"< — Ь, У, > 0, г = О, , ?) > (10)

I 1=0 1=0 J

дчя которой компоненты вектора переменных у определим по формуле

г 6 1\

(здесь х, = 0 если / Х\ и Хд) Тогда справедливы равенства

Уоао = ^ у,а,, со2/о = с,г/" (12)

из которых вытекает счедующнй результат

Лемма 1 Вектор (11) яв гяется вырожденным допустимым базисным решением для расширенной задачи (10) Это решение имеет порядок вырожденности, не меньшие ve.ni \Т\\, и дает то оке значение целевой функции, что и вектор х в основной задаче (1)

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

Обратный переход ог расширенной задачи (10) к основной осуществляется следующим образом Пусть вектор у = (3/0,3/1, , У»)' является допустимым

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

Тогда справедливы счедующие утверждения

Лемма 2 Вектор г с компонентами (13) является допустимым д!я основной задачи 1 и дает то же тачение и,елевой функции, что и вектор у в расширенной задаче (10)

Лемма 3 Если вектор у оптимален для расширенной задачи (10) то вектор х оптимален для основной задачи (1)

Заметим, что если уо ^ 0 то допустимое решение ? не является вообще ю-воря, базисным, даже если допустимое решение у базисное Действительно пусть 2",/+ = {? у, > 0} множество почожптслышх компонент базисного решения задачи (10) Если Тч+ п не имеют общих элементов, то число ноложитечьных компонент соответствующею допустимою решения задачи (1), полученное из (11) может быть равным т — \ + т—\Т\\ + \ = 2т — \Т\ \ Таким образом, каждому допустимому базисному решению в основной задаче (1) соответствует вырожденное допустимое базисное решение в расширенной задаче (10) При этом ненулевые компоненты последнею решения не являются малыми, что даст возможность уменьшить целевую функцию в задаче (10) на величину, сравнимую с текущим значением эгоп функции

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

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

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

(13)

линейного программирования, прсдставиыыс в виде

111111 ¿а".«. = ь, 2". > °> а, 6 Л С И'"} (14)

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

Для метода 1 операции столбцов, вообще говоря, не доказана сходимость к оптимальному решению Это связано с тем, что целевая функция на каждой итерации уменьшается на величину |0ДШШ| Если с увеличением числа итерации Дшш —> 0, то имеет место сходимость к оптимальному решению Ее 'ш же Дшш 0, а в —♦ 0, то имеет место сходимость к вырожденному, по не обязательно оптимальному решению В этом случае оптимум в задаче достшается за бесконечное число итераций

Решение обобщенной задачи (14) в случае вырождения проводится с помощью с чедующею алюрптма, являющеюся обобщением ала оритма Бахши-япа Пусть В некоторый текущий базис этой задачи, дчя которою в векторе гц положительны только к компонент Пусть 2+ множество индексов этих ночожнтельпых компонент, 1ц множество индексов базисных переменных Рассмотрим матрицу V, столбцы которой образованы векторами, соответствующими нулевым компонентам вектора хд, и матрицу 5 размерности ((>н — А) х т), составленную из строк матрицы В"1 с номерами, принадлежащими множеству Х/ДХ, матрицу линейного преобразования из пространства Я"' в подпространство С(У) Рассмотрим вспомо1атсльную обобщенную задачу линейного программирования вида

/ п-1 п-к Ч

ПИП А,у, ^ У'к' = У' - Л* 6 п' ^ К"'"*) • (15)

1де Л, — {/1 Н = 5а,, а, 6 -Д,}, образы множеств Л, при рассматриваемом чшюйпом преобразовании Если задача (15) имеет конечное решение,

то текущий базис В исходной задачи (14) оптимален Если же конечною оптимума в задаче (15) не существует то в исходной задаче (14) может быть построен новый базис которому будет соответствовать строю меньшее значение целевой функции

Если во вспомогательной задаче (15) снова возникает вырожденность, то

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

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

Задача оптимальной линейной идеааъиои коррекции траектории движения космического аппарата Пусть I 6 /?"' вектор параметров (напр , фазовых координат) космического аппарата который может быть изменен путем проведения серии импульсных коррекций Коррекция заключается в мгновенном изменении некоторых параметров в моменты времени ¿1 , 1„ Такое изменение в каждый момент t, будем характеризовать корректирующим вектором (импульсом) и, 6 11"'' Будем рассматривать идеальную лнпен-н\ю коррекцию, тс нредпочагать, что нми\ чьсы производятся без ошибок, и изменение вектора I в момент равно Р,и, где Р1 матрица размерности (утгхт,), характеризующая влияние пмпу н.са Пусть Ь требуемое изменение вектора I Тогда импульсы и, должны удов ютворлть условию = Ь

Пусть р, (и,) - затраты на коррекцию в момент I, То1да задача минимизации суммарных затрат на коррекцию имеет вид

Представляя вектор и, в виде и, = х,'), 1де вектор 6 И"1' ирипадчежпт множеству {7, р,{■у,) = 1}, х, = р,(и,) > 0, запишем задачу нахождения оптимальной коррекции в виде

описанная процедура применяется рекурсивно те рассматривается вторая

(1С)

где А, = {а а = Р,7,, p,{h) = 1} чиненные образы множеств р(7,) = 1

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

mmj^r, ^^ х,а, — Ь, т, > 0 а, е Л Vî | (17)

Мы приведем результаты вычислении дчя счучая, когда Р - диагональ-пая матрица с элементами Р„ = г, г = 1, , ггс'при различных значениях m В табч 1 приведено сравнение числа итераций для стандартного алгоритма и нового метода При этом для нового метода указано суммарное число итерации в расширенной и во вспомо1атслыюй задачах

ТАБЛИЦА 1 Результаты расчетов для задачи идеальной коррекции

m Число итераций

Стандартный алгоритм Новый алгоритм

2 8 6

3 21 16

4 42 28

5 41 33

6 81 59

7 123 84

8 161 135

9 216 113

Задача L-оптимального планирования эксперимента имеет следующий вид Пусть в G Rm вектор неизвестных параметров системы, и при г = 1, ,п проводятся г, измерений вектор-функций H[9 € R"' Пусть уг средние арифметические г, значении, измеренных в г-й момент времени Тогда осрсднсниыс уравнения измерений могут быть записаны в виде

y, = H't0 + e„ i=l, ,п, . (18)

где ошибки измерений е, некоррелированпы, Ме = 0, De, = ^

Пусть N = общее число измерений Рассмотрим вектор р с коорди-

натами р, = rt/N, г = 1, , п, и, пренебрегая целочисленностью г,, будем считать, что р непрерывный план эксперимента,

ТС peEn = {peRn р, > о, = 1, г = 1, ,п}

Пусть I— b'jO, j = 1, , s контролируемые параметры (Ь} 6 Rm - известные векторы) При заданном плане р рассмотрим линейные оценки каждого из этих параметров

15

с методом Вольфа

h = Y1 фчу" Tv= ^ Pi> °ь

(19)

где параметры Ф,,, называемые оцеинвателямн удовлетворяют условиям несмещенности Y1 = Ь,, j = 1, , s <е 1Р

Основные публикации по теме работы

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

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

3 Бахшияи Б Ц Федяев К С О решении почти вырожденных и плохо обусловленных задач навшацни методами линейною npoi раммнрованил // Труды VI Международной конференции "Идентификация систем и задачи упрлвлсння"81СРГЮ 07 М 2007 С 1513-1532

4 Бахшияи Б Ц , Федясв К С О применении критерия оптимальности для решения вырожденных задач линейною npoi раммпроваппя Тезисы докладов па Воронежской весенней математической шкоче "Современные методы в теории краевь х задач"("Поптря1 ннскне чтения - VIII") Воронеж 1997 С 20

5 Федяев КС Применение алюршма преодочеппя вырожденных итераций при решении задачи ¿-оптимальною оценивания параметров системы ,'/ Тезисы док [адов па IV Конференции молодых \ ченых «Фун ментальные и прикладные космические исследования» М ПКП РАН 2007 С 49-50

055(02)2 Ротапринт ИКИ РАН

Москва, 117997, ул Профсоюзная, 84/32

Подписано к печати 19 04 2007

Заказ 2088

Формат 70 х 108/32

Тираж 100

0,9 уч -изд л

Введение

1 Основные сведения из теории линейного программирования. Вырожденность, методы ее преодоления

1.1. Постановка задачи и алгоритм симплекс-метода.

1.2. Построение допустимого базисного решения

1.3. Проблема вырожденности. Формальное описание

1.4. Алгоритм Вольфа.

1.5. Алгоритм Бахшияна.

1.6. Сведение задачи 3 к задаче 5.

1.7. Сравнение алгоритмов Вольфа и Бахшияна на примере решения задачи большой размерности.

2 Почти вырожденные задачи линейного программирования и методы их решения

2.1. Введение.

2.2. Постановка задачи.

2.3. Демонстрация основных идей на примерах.

2.3.1. Об алгоритме решения строго вырожденной задачи.

2.3.2. Идеи алгоритма в случаях почти вырожденной или плохо обусловленной задач линейного программирования.

2.4. Конструирование расширенной задачи в общем случае

2.5. Решение расширенной вырожденной задачи

2.5.1. Алгоритм для расширенной задачи.

2.5.2. Об эффективности нового алгоритма и условиях прекращения вычислений.

3 Решение вырожденных обобщенных задач линейного программирования и практические приложения

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

3.2. Решение вырожденной обобщенной задачи.

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

3.4. Оптимальная задача линейной идеальной коррекции

3.4.1. Постановка задачи.

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

3.5. Задача L-оптимального планирования и ее сведение к оптимальной задаче линейной коррекции

3.5.1. Постановка задачи и сведение к задаче идеальной коррекции.

3.5.2. Решение L-задачи.

3.5.3. Построение вырожденной L-задачи и ее решение.

3.5.4. Построение начального базиса в L-задаче.

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

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

Актуальность работы. Вырожденные задачи линейного программирования стали объектом изучения фактически сразу после возникновения линейного программирования как самостоятельной научной дисциплины. Однако в первое время вырожденность рассматривалась исключительно в контексте проблемы зацикливания симплекс-метода [12, 25]. В подавляющем большинстве работ того периода указывалось, что на практике случаи вырождения весьма редки, а зацикливания при решении практических задач никогда не наблюдается (см., например, [25]). Проблема построения примеров зацикливания представляла самостоятельный научный интерес, этому вопросу посвящались отдельные работы как в начале развития теории линейного программирования (см. [27]), так и в дальнейшем (см., например, [31, 36]).

Однако с развитием области применений линейного программирования и ростом размерности решаемых задач при практических расчетах все чаще стали возникать ситуации, когда зацикливания не происходило, однако на больших последовательностях итераций целевая функция не изменялась, или ее изменение было пренебрежимо мало. Это явление привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью. Однако большинство классических методов теории вырожденного линейного программирования по-прежнему было посвящено лишь борьбе с зацикливанием, избежать вырожденных итераций при использовании таких методов не удавалось. Указанные методы сводились либо к специальному выбору выводимого из базиса вектора (лексикографическое правило и правило случайного выбора [12]), либо к выбору вводимого в базис вектора (правило Данцига [30]), либо к одновременному выбору обоих этих векторов (правило Блэнда [28]). Разрабатывались также методы, основанные на применении теории двойственности [26].

Первым методом, позволяющим эффективно преодолевать вырожденность, был метод А.Чарнса [29]. Он сводился к модификации правила выбора выводимой из базиса переменной в случае возникновения вырожденности. Одним из наиболее эффективных методов борьбы с вырожденностью в настоящее время является метод Вольфа, предложенный впервые в [35] и модифицированный в [34]. Этот метод основан на случайном возмущении нулевых базисных переменных, соответствующем преобразовании правых частей системы ограничений и последующем решении полученной таким образом невырожденной задачи с измененным правилом выбора выводимой из базиса переменной. В результате решения невырожденной задачи строится новый базис исходной вырожденной задачи, соответствующий меньшему значению целевой функции, или делается вывод об оптимальности текущего базиса вырожденной задачи. Таким образом, метод Вольфа требует решения на каждой вырожденной итерации вспомогательной задачи линейного программирования. В результате процесс поиска оптимального решения исходной задачи становится строго монотонным. Однако метод Вольфа имеет два недостатка. Во-первых, размерность вспомогательной задачи совпадает с размерностью исходной. Во-вторых, при решении вспомогательной задачи также могут возникнуть вырожденные итерации, что приводит к необходимости рекурсивного применения предложенной процедуры.

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

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

Ряд задач теории оценивания и планирования эксперимента сводится к задачам, которые получили в литературе название задач обобщенного линейного программирования [12, 20, 4]. Эти задачи по виду напоминают задачи линейного программирования, однако в них векторы условий-равенств не фиксированы, но выбираются произвольно из некоторых заранее заданных множеств. Такие задачи иногда также называют многопараметрическими задачами линейного программирования. Методы решения обобщенных задач обсуждались в работах Дж.Данцига, Л.Лэсдона, М.Мину, М.Л.Лидова, Б.Ц.Бахшияна и др. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится также задача L-оптимального планирования эксперимента [5]. К решению серии обобщенных задач линейного программирования может быть сведена также задача MV^-оптимального планирования [9]. К обобщенным задачам линейного программирования более сложного вида сводятся задача ^-оптимального планирования эксперимента [10] и задача робастного оценивания [2].

Задачи обобщенного линейного программирования, впервые рассмотренные в [12], обсуждались затем в работах [18, 4,14, 1, 17]. Алгоритм решения обобщенной задачи линейного программирования представляет собой реализацию так называемого метода генерации столбцов в обобщенном линейном программировании [12, 20]. Метод генерации столбцов заключается в том, что задачу обобщенного линейного программирования трактуют как обычную задачу линейного программирования с бесконечным числом векторов условий и решают обычным симплекс-методом, выбирая вводимый вектор из соответствующего множества. Однако в отличие от обычных задач линейного программирования, для обобщенных задач достаточные условия оптимальности текущего базисного решения могут не выполняться в силу бесконечного числа векторов условий. Поэтому для прекращения вычислений используется понятие ^-оптимальности, для проверки которой применяются оценки, позволяющие установить степень близости текущего значения целевой функции к оптимальному. Примеры таких оценок для целевых функций специального вида можно найти в работах [14, 1].

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

Одной из областей, в которых особенно широко применяются методы линейного программирования, является математическая теория планирования эксперимента. Различные задачи теории планирования эксперимента рассматриваются в работах [23, 13, 19, 33, 15, 5]. Применение в теории планирования эксперимента методов линейного программирования рассматривается в работах [4, 3, 9, 10, 5]. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится задача L-оптимального планирования эксперимента [5]. К решению серии обобщенных задач линейного программирования может быть сведена задача MVS-оптимального планирования [9]. К обобщенным задачам линейного программирования более сложного вида сводятся задача ^-оптимального планирования эксперимента и задача робастного оценивания [10, 2].

Цели и задачи работы.

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

2. Решение аналогичной проблемы для обобщенных задач линейного программирования.

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

4. Проведение сравнения алгоритма преодоления вырожденности в задачах линейного программирования, предложенного Б.Ц.Бахшияном, с другими аналогичными алгоритмами.

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

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

1. Разработан и программно реализован метод решения почти вырожденных задач линейного программирования.

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

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

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

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

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

- Воронежской весенней математической школе "Современные методы в теории краевых задач"("Понтрягинские чтения - VIII")(Воронеж, 1997),

- VI Международной конференции «Идентификация систем и задачи управления» SICPRO '07 (Москва, 2007),

- научном семинаре "Управление и устойчивость "под руководством профессоров В.Н.Афанасьева, В.Б.Колмановского, В.Р.Носова, МИЭМ (Москва, 2007),

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

- IV Конференции молодых ученых «Фундаментальные и прикладные космические исследования» ИКИ РАН (Москва, 2007).

Публикации. Основные результаты работы изложены в двух статьях [3, 6] и трех тезисах докладов на научных конференциях [7, 8, 24].

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

Заключение

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

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

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

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

4. Программная реализация метода Бахшияна преодоления вырожденных итераций в задачах линейного программирования и сравнение этого метода с методом Вольфа.

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

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

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

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

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

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

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

7. Бахшиян Б.Ц., Федяев К. С. О решении почти вырожденных и плохо обусловленных задач навигации методами линейного программирования // Труды VI Международной конференции "Идентификация систем и задачи управления "SICPRO'07 М., 2007.

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

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

10. В.А.Гамулин. Решение МУ-задачи оптимального планирования эксперимента для полиномиальной и тригонометрической моделей измерений // Известия РАН. Теория и системы управления. 2003. №3. С.97-102

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

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

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

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

15. JIudoe M.JI. О модификации симплекс-метода линейного программирования в случае вырождения // Космические исследования. 1991. Т.29. № 4. С.499-508.

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

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

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

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

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

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

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

23. Федяев К. С. Применение алгоритма преодоления вырожденных итераций при решении задачи L-оптимального оценивания параметров системы: Тез. докл. IV Конф. молодых ученых «Фундаментальные и прикладные космические исследования» М.: ИКИ РАН, 2007.

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

25. 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. .

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

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

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

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

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

31. Kotiun T.C. Т., Steinberg D.I. On the possibility cycling with the simplex method // Oper.Res. 1984. V. 26. No. 2. P. 374-376. ;

32. Pukelsheim F. Optimal design of experiments. New York: J.Wiley and1. Sons, 1993. •i i

33. Ryan D.M., Osborne M.R. On the solution of higly degenerate linear programmes // Mathematical Programming, v.41, 1988. P.385-392.

34. Wolfe P. A technique for resolving degeneracy in linear programming / / Journal Soc. Indust. Appl. Math., v.ll, 1963. P.205-211.

35. P.Zornig. Systematic construction of examples for cycling in the simplex method // Computers к Operations Research. 2006. No 33. P.2247-2262.