Достаточные условия оптимальности, их развитие и применение для решения задач дискретной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

5ОС^ . . ... ЬИо^О Г£яА

йосковскяЛ ордена Ашягаа, Ордена Октябрьской Реэолвцки и Ордена Трудового Красного Знаиеня Государственный Университет йй. 8;В. Лононосова

Факультет вичислитаяъной сатекаткки н кибернетики

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

Сергеев Сергей Иванович

Щ 519.688;519.&54

достаточнее ашвна штпмьности. их разанш и

ПРИМЕНЕНИЕ т РЕВЕННЯ ЗАДАЧ ДИСКРЕТНОЙ ОЛТИМЭЙЦИИ

О1.01.09 - Математическая кибернетика

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

Иосква - 1992г.

Работа выполнена в НИМ экономики, планирования и упразленкя авиационной провнолвнности. Официальна оппонент»:

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

Булатоз В.П.,

доктор оиэико-цатеиатических наук, профессор

Еиелнчев В.д.,

доктор фязико-натеиатических наук, профессор

Хрусталев U.M. Веддцая организация: Институт проблей управления Pfili

За^нта состоится 1992г. в часов на заседании

Специализированного совета Д.053,ОБ.38 Н4 по математике при ИГ9 ни. В.В. Ломоносова Л < ёпГ Адрес: 119899, ГСП, Носква В-234, Ленинские горы, ЙГЫ,

факультет Вычислительной иатеиатккн и кибернетики Ю, ауд.

С диссертацией аояно ознакомится в библиотеке Факультета Ввчислительной иатекатики и кибернетики ИГУ

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

Ученый секретарь Специализированного совета профессор

Н.П. Трифонов

Общая характеристика работы

Актуальность темы. Математическими моделями многих задач планирования и управления производством являются модели дискретной (целочисленной) оптимизации.Точные алгоритмы решения задач дискретной оптимизации (ДО) базируется на таких общих подходах как 1) методы последовательного анализа вариантов (включая динамическое программирование), 2)методы ветвей и границ, 3)методы отсечений, 4)методы построения последовательности решений, 5)методы, использующие обобщенные функции (множители) Ла-гранжа. Отметим, что среди перечисленных, подходы 1), 2) и 4) позволяют в принципе строить двусторонние алгоритмы. Приближенные алгоритмы базируются, в основном, на схемах локальной и субградиентной оптимизации. Несмотря на успехи в решении отдельных классов (главным образом линейных) задач ДО с несколькими сотнями переменных, в общем случае нельзя быть уверенным в решении произвольных задач с 30-40 целочисленными переменными, поэтому разработка новых универсальных подходов по-прежнему актуальна. Особенно это относится к подходам, позволяющим в рамках единой теоретической схемы строить двусторонние алгоритмы решения задач ДО.

Определенные новые возможности для решения широкого класса задач оптимизации, в том числе и задач дискретной (представляемых в виде многошаговых процессов с одно- и многомерным аргументом), предоставляются используемыми здесь достаточными условиями оптимальности В.Ф. Кротова, ядром которых является задание разрешающей функции Ч^'ЦУ ) .Реализация тех или иных условий оптимальности для заданной функции Ц'СЬ,^) позволяет строить в основном двусторонние алгоритмы решения задач ДО, осуществляющие приближение по функционалу как "сверху",так и "снизу". Конкретизация вида функции (линейный, нелинейный) позволяет получить алгоритмы различной степени "силы" (и, соответственно, сложности). Помимо перечисленных "методологических" свойств функции с ее помощью часто удается учесть специфику конкретной рассматриваемой задачи, в силу чего как показывает опыт разработки алгоритмов, включая численный эксперимент, последние обладают определенной новизной и эффективностью. Вместе с тем подход, связанный с заданием функции ^(Л,У ) позволяет исполь-

зовать и полезные идеи, полученные' ранее с помощью других подходов .

Большинство рассмотренных в диссертации алгоритмов осуществляет приближение "снизу" по функционалу. Основой алгоритмов этой группы является дальнейшая конкретизация способов построения фун-^ кции -элементарная операция (ЭО) улучшения функции

с помощью которой последовательно увеличивается значение определенной нижней границы исходного функционала - (!-функционала. В работе проводится дальнейшее развитие идей, основанных на реализации ЭО, особенно в применении к многоиндексным задачам ДО. Определенная идейная общность последнего подхода прослеживается с подходами 2), 3), 4) и особенно 5), то есть с методами, использующими в той или иной степени следующую универсальную идею: расширёние множества допустимых решений за счет отбрасывания части ограничений исходной задачи или введения функционалов-минорант, решение задачи оптимизации на расширенном множестве и затем аппроксимация допустимыми решениями решения на расширенном множестве.

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

Вместе с тем развиваемый в диссертации подход можно использовать не только для решения перечисленных выше классов статических задач ДО, но и динамических, а также многошаговых задач оптимального управления с одно- и многомерным аргументом с ограничениями на управление (на все или только часть) топологи-

*)Кротов В.Ф. Вычислительные алгоритмы решения и оптимизации управляемых систем уравнений, I II.-Изв. АН СССР,Сер. Техническая кибернетика, 1975, N5, с.3-15; 1975, N6,0. 3-13.

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

Цель и задачи исследования - создание нового подхода для решения широкого класса задач ДО (и некоторых специальных задач теории оптимального управления) на основе единой теоретической базы - достаточных условий оптимальности, и разработка на его основе новых, главным образом двусторонних алгоритмов решения этих задач.

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

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

В диссертации получены следующие основные результаты: 1 .Доказана теорема о достаточных условиях оптимальности для многошаговых процессов управления с многомерным аргументом, частным случаем которых являются статические многоиндексные задачи ДО (теорема 1.2).

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

ДО двусторонние алгоритмы (теоремы 6.2 и 6.3 для многомерной задачи о ранце с линейными связями и сепарабельным функционалом) .

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

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

-обобщенная задача назначения с границей лучшей, чем для одной из релаксаций Росса-Соланда (теорема 2.1);

-трипланарная задача назначения с границей лучшей, чем доставляемой алгоритмом В. Иванова (теорема 3.4); -задача коммивояжера с границей, полученной независимо и более "резкой", чем доставляемая Процедурами Ограничений 1-3 в алгоритме Балаша-Кристофидеса (теоремы 4.1,4.4 и 4.2); -квадратичная задача назначения с границей лучшей, чем доставляемой алгоритмом Гаветта-ПлайтераСтеорема 5.1 и лемма 5.2); -задача о многомерном ранце с линейными связями и сепарабель-ным функционалом с границей более "резкой", чем доставляемой схемой обобщенных множителей Лаграяжа(теорема 6.1); -точный алгоритм решения линейной задачи назначения с оценкой

1 5»

0(n )+0(Rn ) числа операций (теорема 3.3).

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

Первая группа задач связана с проблемой проектирования, создания и функционирования реальной информационно-вычислительной сети. Разработанный комплекс алгоритмов и программ (последние частью выполнены под научным руководством автора Мотусом O.A.) внедрен в ВИНИТИ ГКНТ и АН СССР с годовым экономическим эффектом 35 тыс. руб. в год. Имеется акт о внедрении.

Вторая группа задач - с созданием системы автоматизированного проектирования двусторонних печатных плат повышенной плотности. Разработанный комплекс алгоритмов и программ (последние частью выполнены под научным руководством автора Герасимовым А.Л.) внедрены в НИИ радиотехники Министерства радиопромышленности. Имеется акт о внедрении.

Третья группа задач - с решением ряда задач оптимального распределения ресурсов, встретившихся в практике отраслевого планирования. Первая из этой группы задач - об оптималььном целочисленном распределении неоднородных средств, вторая - об оптимальном резервировании. Разработанные алгоритмы и программы внедрены в НИИ экономики, планирования и управления Министерства авиационной промышленности. Имеется акт о внедрении.

Кроме того, ряд алгоритмов,разработанных в диссертации, использовался в учебном процессе Московского экономико-статистического института MB и ССО СССР на кафедре Экономической кибернетики.

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

союзном совещании-семинаре по управлении, большими системами (Алма-Ата 1978г.), на IX, XIII, XIV Всесоюзном семинаре "Системные исследования ГАСНТИ" (Ереван 1979г, Тбилиси 1982г., Минск 1983г.), на VIII и XI Всесоюзных совещаниях по проблемам управления (Таллин 1980г., Ташкент 1989г.), на 1,11,111 Всесопзном совещании "Методы и программы решения оптимизационных задач на сетях и графах" (Новосибирск 1980г.,1982г, Ташкент 1984г.), Республиканском семинаре по дискретной оптимизации (Киев 1987г.), Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеризация" (Таштагол 1987г.), 8-й Всесоюзной конференции по теоретической кибернетике (Горький 1988г.).Всесоюзном семинаре "Дискретная оптимизация и исследование операций" (Новосибирск 1990г.), Международной конференции по методам оптимизации и их приложениям (Иркутск 1989г.), а также на ряде научных семинаров в Московском экономико-статистическом институте МВ и ССО СССР под руководством проф. Кротова В.Ф. (1975-1984),семинарах в ИПУ АН СССР (1980,1988), ВЦ АН СССР (1988,1990), ИК АН УССР (1987), Московском авиационном институте МВ и ССО СССР (1989).

Публикации. По теме диссертации опубликовано 52 работы.

Объем и структура работы.Работа состоит из введения, 6 глав, заклпчения, списка литературы из 2Л7 наименований и четырех приложений, содержащих результаты численного эксперимента по результатам внедрения разработанных в диссертации алгоритмов,и документов, отражающих внедрение результатов работы. Общий объем работы з&о страниц страниц основного текста, 951 страниц

приложений, включая S рисунков и 20 таблиц.

Основное содержание работы

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

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

Изложению методов 1)~4) посвящены г.1.1.4.1-1.1.4.4 диссертации. Особенно подробно в п. 1.1.4.5 освещаются двойственные подходы в ДО, связанные с использованием обобщенных множителей и функций Лагранжа, суррогатной и комбинированной двойственностей.

Стандартной статической формулировкой задачи ДО, рассматриваемой в диссертации, является следующая:

где И ^ь ~ аддитивные функции, а Ы-ц Д 1!

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

мерным аргументом)*^ и решены некоторые вопросы существования и разрешимости ЭО улучшения функции

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

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

Рассматривается управляемый процесс, характеризуемый аргументом "Ь , состоянием У и управлением 14 , пробегающими множества 'Т,,17 , соответственно. Каждому 1 е.'Г поставлено в соответствие подмножество Л/^ прямого произведения *ЛТ. Среди всех пар функций V/-{Ч-ь ДЦ*^ задано множество допустимых при помощи условий . .

И^иООГ (4)

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

*)Кротов В.Ф. Достаточные условия оптимальности для дискретных управляемых систем .-Доклады АН СССР, 1967 ,т. 172, с.18-21.

**)см. ссылку на стр.2

и^,Рассматриваются две модели такого рода.

1.Многошаговый процесс управления с одномерным.аргументом. Множество Т -целочисленный ряд £0,1, . . . , ^ Ъ> И Х1-век-

торные пространства размерности - И я1> , соответственно; уравнения связи имеют вид:

Л (5а)

УЧо)-У1о, (¿Н,...,«), (5б)

где ^ |У, 14 ) -вектор-функция, заданная на прямом произведении и принимающая значения в

2.Многошаговый процесс управления с многомерным аргументом. МножествоТ -прямое произведение множествТ* }, > 1. ,

где

-целочисленный ряд

{0,1.....Т,* КУиТГ -векторные пространства размерности Л и Ч/ , соответственно; уравнения связи имеют вид: ^ ___

(66)

где ^ -Ч ("^-тV» ^ > ^ = ^Iт ^ -функции, заданные

на прямом произведении Т *^ , Введем в рассмотрение следующие вектор-функции^иЗ,^)1 (и-Ч, И = МП ). Кроме того, введем множество Е пар функций и^ удовлетворяющих условию (4). На множестве Б задан функционал вида

г--о Ч^.о -ь^'О (7)

,0

для каждой модели соответственно, где 3 VI ) заданные

на'ТхУ*\Г функции.

На функции помимо перечисленных условий наложены

дополнительные условия. Введем в рассмотрение следующие множества:"^/^ —проекции множества

на множестваУ и V соответственно; , , Для первой модели £> - значение ^

- подмножество множества при^.-'С, Для второй модели

& - совокупность значений Ь~ С "Ц ^^ ^образующих границу прямоугольника Т :0 ¿"Ц £ 1Г(>,,. 7 О 4"С"^ Л*/- множество вектор-функций .заданных на $ и таких, что ^^у" ■> ^ £ £ < Ставятся следующие две задачи.

1.Отыскание допустимого процесса, где требуется найти последовательность процессов ^У^ ^Ц^д^ ^ сходящуюся в специально

оговоренном смысле к

2.Минимизация функционала I на С, когда помимо п.1 от последовательности { требуется ^ 1 ^^

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

Введем в рассмотрение соответственно рассматриваемым моделям функцию ) и вектор-функцию -(Ч1^""^111 ) и построим с их помощью следующие стандартные конструкции:

ГЧ> ИМ Чв.чИ'^,

,11 Ч> VI I ...I1 +

(^и^У* V) «л*/

ем =

- -Цго Ьт-О

Введем в рассмотрение класс П функций вектор-функций

1?и.|Ч)-0?1,Ч'т )) таких,что величины 1*1 и С (.4) определены. Исследуется и обосновывается следующий универсальный прием ре-

*)см. ссылку на стр.2.

шения поставленных выше задач 1 и 2: отыскивать последовательность такую, что - <1 'Искомая последовательность функций строится с помощью элементарной операции улучшения начиная с произвольного Ч*о £ П , Приведем основные конструкции этой операции.

Пусть имеется функция .которой соответствуют

К 1 , 14 (. Ч ) , а также множество V* пар _

у^^ обеспечивающих максимум | М ^ на"\/" , множествоЛ'/^

функций У £), обеспечивающих минимум па\[

и множество Е^ пар функций удовлетворяющих условиям:

при всех^ФЧ^»-,

Функцию будем искать в виде

где ^(^Ч) и Я -функция и положительное число, подлежащие определению. Определим соответственно моделям следующие функционалы:

У*, д.

О

Обозначим через ^(.^^и^Л и т.д. конструкции,

соответствующие функции , и пусть, соответственно:

4 УечлДА) 4 7

¿о -Ьо^ У10Л -х^

Определение. 30 улучшения функции Ч^^У ) считается задан-

ной, если функция V^j строится в виде (9), где ^ и /Ц выбираются произвольно в пределах следующих требований:

а)S4(4,U}>0 - _ (10а)

хотя бы при одном значении (Я4)

б) Ч^-Ч^+а^еП. (106)

Известны два способа реализации условий (10а),(106). Первый способ состоит в том, что ^ и выбираются произвольно в пределах, соответственно, требований:

5Ц0)>0, (На)

Второй способ состоит в том, что задается некоторое правило, согласно которому из выделяется единственный элемент ^(А)^

U^A } а функция выбирается из условий непрерывности по А

и положительности ^jl^); U^l^i 3 ПРИ А -О , Тогда при дос-

таточно малом (Л) > О и условие (10а) выполняется.

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

для решения задач ДО это направление было успешно использовано

\

Хелдом и Карпом ' , Балашем и Кристофидесом ' и независимо Кротовый и автором (1975г.)

Здесь же приводится доказательство теоремы, играющей основополагающую роль при исследовании многошаговых процессов управления с многомерным аргументом вида(6) с помощью реализации 30 улучшения функции 44t,4\ona является обобщением (в части достаточных условий) на многоиндексные процессы управления результата доказанного Кротовым''**) для одноиндексных _задач.

Теорема 1.2. Для того, чтобы элемент У^ДН^Т) минимизировал функционал I на D, достаточно существования такой вектор-функции 44t,y ) что

_ _ (12а)

")Held М., Кагр R. The traveling salesman problem and minimum Spanning Trees.- Operations Research,1970, N6, p.1139-1162.

**)Balas E..Cristofides N. A restricted lagrangean approach to the traveling salesman problem.-Mathematical Programming, 1981, v.21 N1, p.19-46.

** * )см. ссылку на стр-í»

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

В главе 1 приведен, в основном, весь теоретический аппарат для решения задач ДО с помощью подхода, основанного на достаточных условиях оптимальности. Его суть (на примере одноинденс-ной задачи вида (5),(7)) состоит в следующем.

1.0т статической задачи ДО в виде (1)-(3) переходят к эквивалентному многошаговому процессу управления с одномерным аргументом вида (5),(7).

2.Задается разрешающая функция

3) , с помощью которой

выписываются стандартные конструкции для {ЦЧЧ вида (8).

3.Наложение условий (необходимых) на функцию чад)

вида

йС-ь Уо^.чвШ)--»^ (13а)

у

= ё^и-Т, (136)

У

где ,Ц0

позволяет получить серию новых алго-

II

ритмов осуществляющих приближение "сверху к оптимальному значению функционала.

4.Наложение условий (достаточных) на функцию вида (12а),(126) позволяет получить серию новых алгоритмов (в худшем случае — новых "резких" нижних границ) осуществляющих приближение "снизу" к оптимальному значению функционала.

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

двойственных задач вида С(Ч) различных алгоритмов суб-

Ч <= Л

градиентной оптимизации (ч, -алгоритм Шора.реализация ЭО улучшения функции ЧЧЦЧ ) позволяет получить еще одну новую серию

алгоритмов.

Разработанные в диссертации методы решения задач ДО вида (1)—(3) могут рассматриваться как методы решения специальных задач теории оптимального управления - многошаговых процессов уп- ■ равления с одно- и многомерным аргументом и ограничениями на управление топологического характера (несвязанность множества, которому принадлежит управление, в том числе целочисленнасть и т.д.). К задачам такого рода с одномерным аргументом, например, сводятся многие задачи распределения ресурсов на графах, сетях, в иерархических системах. Основополагающую роль при исследовании таких задач данным подходом играет доказанная здесь теорема 1.2 .

В главе 2 описывается применение первого способа реализации условий (11а),(116) для решения некоторых задач математического программирования.

В п.2.1 изучается следующая задача выпуклого программирования: м L о

J[u)--l <14> hl

ti а^и^П^й), eis)

оit t J\ (-ь Cm), (16)

где У V - * > (i ЧП -,t= C«) -

заданные соответственно матрица коэффициентов, вектор_ограничений, векторы коэффициентов квадратичной формы; 0.;д Ct^-t^ioi^fc^ -действительные числа. Для этой задачи предлагается отыскивать функции и ) соответственно в виде:

t=i i-i

где У - фазовая координата в ^-м уравнении эквивалентного для задачи (14)-(16) многошагового процесса управления вида (5а), (56), (7); f = ) | -векторы. Обосновывается простей-

шая реализация 30, для которой Ч^-О V" t £к}где Ц -заданное значение среди 1<=1 ,п, а Л ^>0 определяется процедурой одномерного поиска.

В применении к задаче линейного программирования с двусторонними ограничениями (частный случай задачи (14)-(16)) Ä«, определяется по конечным формулам и отмечается, что в принципе такие реализации ЭО могут быть усилены, например, использовани-

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

Предложенная простейшая реализация ЭО активно использовалась автором для решения задач математического программирования (непрерывных и целочисленных), начиная с 1975г. Независимо (и в других терминах) эту же идею использовал в рамках монотропно-го программирования Рокафеллар * ^ для решения задач выпуклого непрерывного программирования и Бергсекас-Тзенг * *) для создания нового конечного метода решения задач непрерывного линейного программирования.

В п.2.2 изучается следующая обобщенная задача назначения:

(П л

I I Сл'Х;,

¿=1 ул 4 4 (17)

о т

.1 Хс^и^ГЮ.

(18а)

.1 а8б)

(19>

Для нее строится реализация ЭО на уровне простейшей, состоящая в общем случае из конечной последовательности повторений п.п. а)-г) этапа I. Показывается, что ее применение к задаче (17)—(19) приводит в общем случае к новой границе снизу L R »,1^) для которой

- известные границы Росса-Соланда*"**.) Граница uR^lA') при фиксированном Л связана с решением простейшей задачи минимизации и

*)Bocafellar R.T. Monotropic programming: descent algorithms and duality.In Nonlinear programming-4. Academic Press,New York,p.327-36Ь

*")Tseng P., Bertsekas D. Helaxtion methods for linear programs.-Mathematics of Operations research, 1987,v.12, N4,p. 569-596.

**")Ross T.,Soland R. A branch and bound algorithm for the generalized assignment problem.-Mathematical Programming,1975, v.8, N1, p.91-103.

требует 0(т»п) операций для своего вычисления, ЬК^) - с решением многомерной булевой задачи о ранде, что достаточно трудоемко. Трудоемкость вычисления границы я, (.Я ) сравнима с трудоемкостью вычисления границы и намного меньше трудоемкости вычисления границы ¿дЯд.(^.Обоснование этой реализации 30 дает

Теорема 2.1 1. ЭО, состоящая из последовательного повторения п.п. а)-г) этапа I и примененная к данному вектору р=р ,

о

обеспечивает положительное приращение нижней границы за 0(т<п+т+п+5) операций.

г.и^^ЬКзСЯ) ^ ЬМ*)-

В главе 3 общие результаты п.1.2 применяются для изучения следующих задач ДО: транспортной, распределения, линейной и три-планарной задач назначения.

В п.3.1 исследуется транспортная задача, под которой здесь понимается следупщая задача ДО:

—

I и:: б&Лсм.т), с20>

г5-

Л и--® 0..' (21а)

и^ (о,О, (216)

*\

М I (22)

где й.' и - целые неотрицательные числа; С Л'-неотрицательные

4 -VI „ Л «

числа,Ь'Ъ-1.. 0.'. Для задачи (20)-(22) предлагается отыскивать в'ектор-функции и У 1 ^ ) соответственно в виде ,

где У1 -(У ^^ ,, ,, ^ ^ М^-СУ^! ч^г! )-фазовые координаты в эквивалентном для задачи (20)-(22) многошаговом процессе управления вида (5), (У); векторы. Конструктивный алгоритм задания на каждом шаге вектора У и числа О приводится только для частного случая задачи (20)-(22), а именно задачи распределения (п.3.2):

а) Л и:: ±Ь; (23а)

■ с «.I' 4 1 '

с

б)Л Ц-Ы» (23б)

^Н; а 4

1-1 L lyi IU' -»"ttldfl. (25)

Здесь M,N -множества, соответственно, всех работ и всех исполнителей; -подмножество допустимых исполнителей j-й работы; N"CD -подмножество допустимых работ i-ro исполнителя. Условия непустоты класса D допустимых управлений W^1 ,то есть разрешимости системы уравнений (23а),(236), сформулированы в виде теоремы. .

Л \ \ 'Л

Пусть МсМ, НСН, N(14) - объединение множеств N , Ufe. М,то

есть минимальное множество уравнений группы б),содержащих все

переменные Ц»/ .входящие в подмножество МСМ уравнений группы а).

Г* Ч , i Л

Аналогично M(N) -обгединение множеств М^ , д fe N.

Теорема 3.1 Пусть задана задача (23)-(25). Для разрешимости уравнений (23а),(236) (в замкнутом варианте) необходимо и достаточно выполнение следующих условий.

А

1,Для любого множества М е.18

¿ft^W».,

2.Для любого множества NCN

-i (27) «-éMlN) t ' K¿1)

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

формулу (28)),

а не только на клетках как это происходит в венгер-

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

Л А

для множеств М и N, находимых более простыми, чем в общем случае, способами (так называемые "разрешимые" случаи нахождения множеств

Л /V

М и N).

Новый точный алгоритм решения задачи распределения состоит в основном в следующем. Пусть заданы произвольно вектор Р^г ^{Л'^З } )-) S - номер итерации. Вве-

дем конструкции: .

"Ч > С28Э

h¿¡{h)>0,

* \0v< Ц-1*0=0',

м I . V\ И К! И

i-4 ¡Л ^ ¿s4 *

Тогда алгоритм решения задачи (23)-(25) состоит из конечной последовательности повторений этапов 1,11, определяющих собственно 30.

Этап I реализует, по сути дела, первый способ реализации Э0 (11а),(116), этап II - второй способ, состоящий в нарушении определенного вида неравенств (типа (26),(27)) на специальным образом конструируемых множествах. Здесь удалось найти дополнительно к общим конструкциям, основанных на неравенствах типа (26),(27), еще по три разрешимых случая нахождения множеств, на которых происходит увеличение Z-функционала с меньшими, чем в общем случае, вычислительным! затратами (с указанием величины сдвига для числа Д ). Обоснование а. горитма дает

Теорема 3.2. 1.В результате применения построенной 30 к данному вектору р=р^ возможна следующая альтернатива: а)на выходе Э0 определено управление (Д¿j(Р) допустимое и оптимальное; б)если управление (Р) определено, но не допустимо, то выходом Э0 является увеличение X, -функционала, причем

2.Последовательность Э0, начинающаяся с произвольного вектора Р , приводит к оптимальному решению Ц ) через конечное

ч

число шагов. а

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

ИР),, ,в го время как новый алгоритм -оценку, основанную

Р6 íWlPUO}' и р Гол „

на реализации безусловного максимума ti." / . Заметим, что за рубежом в приложении к линейной ЗН идея безусловной максимизации i (Р) была позже и несколько иначе (в рамках монотропного программирования реализована в*^.

*)см. ссылку на стр.'Ь

* *)Bertsekas D. A new algorithm for the assignment problem. -Mathematical Programming,1981,v.21,p.152-171.

*)

Алгоритм ВерТсекаса совпадает во многом с алгоритмом, основанным на теореме 3.2, если не использовать в последнем "раз* Л

рёшимые" случаи нахождения множеств М и N. Для такой версии алгоритма основанной на теореме 3.2, справедлива следующая теорема.

Пусть Ц0,ЙЗ - отрезок, из которого берутся целые случайные числа для заполнения матрицы С в линейной задаче назначения, п -целое число.

Теорема 3.3. В линейной задаче назначения с плотно запол-неной целыми числами матрицей С оценка числа операций не превышает числа 0(п*)+0(Кп2).

Приведенная теоретическая оценка хуже, чем у венгерского алгоритма, однако, как показал обширный численный эксперимент проведенный Бертсекасом для своего алгоритма*^ , также основанного на идее безусловной максимизации (НР) . средняя вычислительная сложность все же ниже, чем у венгерского алгоритма.

В п.3.2.4 предлагается другая реализация 30 (в применении

к линейной ЗН), бйлее близкая к классическому алгоритму Манкреса

г

с оценкой числа операцийК ) действий. Эта реализация 30_ позволяет,как правило, получить большее значениеД.^1., (где ,а р - значение вектора р, соответствующее опти-

мальному решению ЗН). Отмеченное свойство является важным при решении задачи коммивояжера алгоритмом, изложенным в главе 4.

В п.3.3 изучается трипланарная задача назначения следующего вида:

XII (31)

иЦ'еХкьК *

(32а) (326)

Л I = д & I,

<32В>

= (оД^.СбХ^ьЗ^еК, (зз)

где Ь(А7т1г, КЧ^^С^^оС^^З.к^)

-действительные числа.

Для этой задачи предлагается линейное задание (по соответствующим фазовым координатам в эквивалентном многошаговом про-

*)см. ссылку на стр.^&

цессе с трехмерным аргументом вида (6)-(7)) функции Ч'С'Ь^)» Такое задание функции позволило построить для задачи

(31)~(33) реализацию ЭО, состоящую из конечной последовательности применений этапов I и XI. Этап I реализует, по сути дела., первый способ реализации ЭО (11а),(116), этап II - второй способ , состоящий в нарушении определенного вида неравенств на специальным образом конструируемых множествах. Удалось найти четыре типа неравенств или всего двенадцать разрешимых случаев нахождения множеств, на которых происходит увеличение £-функционала (с указанием величины "сдвига" для числа Я ).

Пусть^ =гаах(т,п,р), -нижняя граница, полученная после применения к данному вектору р=р^ в задаче (31)-(33) конечной последовательности этапов I и II, 2-(, -граница, полученная после применения к задаче (31)-(33) идей приведения, предложенных в алгоритме Литтла и др. для задачи коммивояжера (для трипланар-ной задачи назначения в настоящее время более сильных нижних границ не известно и они получаются за ) операций).Обос-

нование порученного способа вычисления нижней границы дает

Теорема 3.А.1.Построенная 30, примененная, к данному вектору Р=Р^ , обеспечивает положительное приращение нижней границы ьЕЛР'Л^О за 0(йг+ 3^^+12^+14) операций.

2.? »ей.

В главе 4 изучается задача коммивояжера (ЗК) в следующей целочисленной формулировке:

ч -- ко,

(37)

I I . (38)

«-ег ¿ьг * -

где N=^1,2,. . . , п^- и условия (38) справедливы

для любых подмножеств 2 , таких, что £ 1Д £ IV . ^ ^ .

Введем в рассмотрение распределение где РМР;))Р//-(Рр1<^ЧЮ -векторы, знакомые по ЗН;^'{2)

*) Иванов В.В. О трехиндексной задаче назначения.-Экономика и математические методы,1974, N2,0.336-339.

-функции подмножества 2 Н . заданные на множестве всех подмножествМ. Определим конструкции:

о?)

гдеЧ-(£)^0 для. всех осталь-

ных 1, ^ ;ч// (гО/й, если (з.,,]) г}и ч ^(г)=0 для всех

остальных 1,о;

о ЦЧРДи))^? (40)

«V и » Ч

* 1-1 4-1 в® гх « '1

Для задачи (34)-(38) предлагается отыскивать вектор-функции ЧЧ^У) и ПЗД соответственно в виде: '/ 2. / ч

здесь

фазовые координаты в эквивалентном для задачи (34)-(38) многошаговом процессе управления вида (6),(7) А} -функции подмножества 2' при фиксированном значении £=А ^ЭД > ^д ^Ч'д -скаляры.

Тогда алгоритм решения ЗК состоит в следующем. Решается содержащаяся в ЗК задача назначения (34)-(37) алгоритмом, изложенным выше в п.3.2.4. Пусть при некотором р=р=|р'р " ^эта последняя решена, но получена совокупность несвязанных между собой подциклов. Тогда на следующей итерации алгоритма задается распределение (р( виде р =р, (г)=0, (и)=0УгсК и определяется 30 его улучшения. Она состоит в общем случае из п. п. Iе ,2°, Зиа),э"б), 3 в) разной степени "силы" при увеличении £-функционала и соответственно сложности.

В терминах теории графов п.п. 1°,2° 30 связаны с нахождением разреза К^. из дуг графа, соответствующего значениям Ь^(р)>г0, для которого А. =0 или А =0 (Здесь А - подмножество городов г=Ае-Н) на котором нарушаются условия (38), А(/А =Ю . Величина сдвига по Я принимается равной первому или второму значению из упорядоченного соответственно списка значений \ й ^ Трудоемкость

вычисления приращения А^ О для совместного применения п:п. 1® 2й составляет л, 0(п** ) операций.

о

П.З ЭО применяется при отсутствии вышеописанных разрезов К^ и является более универсальным алгоритмом. Основой этого пункта ЭО является алгоритм, который позволяет либо найти множества клеток исходной матрицы С, на которых происходит увеличение ¿-функционала, либо указать на отсутствие таковых. Этому алгоритму помимо алгебраического описания придано и наглядное графическое истолкование в терминах теории графов. Величина сдвига по Л принимается равной первому или второму значению из упорядоченного соответственно списка значений 11 ¿^ (р^.сц) на выделяемых этим алгоритмом множествах. Трудоемкость вычисления приращения А. этим алгоритмом в общем

случае составляет ^оСп^ ) операций. В общем случае п.3° ЭО состоит из подпунктов 3°а),б),в) со своими способами нахождения множеств, на которых происходит увеличение Ь -функционала, и вычисления значений Д. Обоснование построенной 30 улучшения, состоящей из п.п. 1°,2°, 3°а) ,3°б) ,3°в) дает

Теорема 4.1 Построенная ЭО, состоящая из п.п. 1°,2°, 3°а), 3 б),3°в) и примененная к данному распределению обеспе-

чивает положительное приращение нижней границы ( 4 % ( Р1>) > О } за число операций не превышающее соответственно: 0(п^(п.п.1° и 2°), 0(пЪ(п.З° а)), 0(п"Хп.п.З° б) и в)).

Устанавливается связь предложенного алгоритма (1980г.) с другими известными алгоритмами. Выясняется, что наиболее близок разработанный алгоритм к алгоритму Балаша-Кристофидеса (1981г. - самому эффективному на сегодняшний день алгоритму решения асимметричных задач коммивояжера, опубликованному полностью несколько позже. Алгоритм ' состоит в общем случае из Процедур Ограничений (ПО) П01-П06, увеличивающих за полиномиальное число операций нижнюю границу - -функционал. П01-П03 увеличивают ее, опираясь на решение ЗН, соответствующее исходной матрице С (см.(34)), П04-П06

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

о о

В диссертации показывается, что п.п.1 ,2 ЭО с точностью

до выбора значения приращения ¿-функционала совпадают с П01.

П.3°а) ЭО не имеет аналога в алгоритме , поскольку связан с

алгоритмом решения ЗН алгоритмом гл.З, для которого допустимыми

клетками в матрице Н являются клетки (Р) >0 . Относительно

ос ^

связи п.п. 3 б), 3 в) и П02-П03 имеет место

Теорема 4.4.Пусть 11 -граница снизу, полученная после применения Процедур Ограничений 1-3 в алгоритме Балаша-Кристофидеса

*)см. ссылку на стр.^0

к задаче (34)-(38)., ^-после применения п;п. 1°,2С.З^а),3°б), 3°в) . Тогда I ¡г, Ь Ь \ ,

Результаты теоремы становятся возможными из-за наложения

ции <0

меньшего числа связей при реализации п.п.1С,2°,3° ЭО, чем при

использовании П01-П03 в алгоритме

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

¿(¿.¿^К^Ч * * _ (42)

Здесь К ) -множество вершин, обладающих свойствами:

а)их удаление из одного и того же подцикла ^ множества допустимых дуг графа ^¿¿(РД^О} нарушает связность графа 0-о ; б)все эти вершины принадлежат ориентированному маршруту, составленному из множества дуг решения ЗН, для которого (РД)^О.

Опираясь на связи (42) исключения подциклов в решении ЗН, в главе предложен п.4 ЭО, существо которого состоит в следующем.

4.Находится множество К .удовлетворяющее условиям а) и б). Тогда улучшенное распределение (РяЧ)ЯлЫ ) задается в виде:

где Л - второе по порядку значение (Р^ (ц^Н^И К^ ^ если расположить их в порядке неубывания. ,

Пусть граница снизу, полученная после применения ПОЗ , - после применения п.4° ЭО. Обоснование п.4° дает Теорема 4.2. 1.30, состоящая из п.4° и примененная к данному распределению (р.,а.) обеспечивает положительное приращение ниж-

« * и

ней границы ( до (р. ) >0) за О(п^) операций.

- I, ± Р

Частным случаем п.4 ЭО является ПОЗ

с о

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

*)см. ссылку на стр.40

Беллмора-Мэлоуна ' (с усилениями Гарфинкеля). Модификации касаются как применения более простых, чем решение ЗН до конца границ снизу, основанных на использовании свойств -функционала, так и использования новой схемы устранения подциклов, наряду с классической схемой

^ I

Беллмора-Мэлоуна ' . Обоснование новой схеме в случае соответствия распределению ) (решению ЗН с матрицей С-^ ) неединственного

значения функционала I., С^ Идает лемма 4.2. Пусть

{}И-М ¿К)- упорядоченная в порядке неубывания соответствующих им значений функционала Т^С^О последовательность распределений.

Лемма 4.2.Пусть задано распределение и ему соот-

ветствует неединственное ^значение функционала й ^ „Выделим среди них распределение и поставим ему в соответствие

распределение ^¿Л ^ так, что Х^-^Т£ ,

о V * Т

Тогда оценкой снизу оптимального значения функционала 4 ЗК с

матрицей С (см.(34)) является значение функционала У ЗН с матрицей расстояний, полученной из матрицы С^ следующим образом:

1)отыскивается дуга (^Д) со свойствами (й^)* =1, (и^)^ =0, (р ,ч)=0, (и^- )д =(и^ для всех остальных дуг (з.,о) подцикла

■р распределения, содержащего дугу

2)в матрице С ^ соответствующее значение 0полагается равным бесконечности. _

В случае соответствия распределению Й^'(.Р^Дд,) единственного значения функционала имеется своя версия леммы.

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

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

В п.4.6 приводятся результаты ограниченного численного эксперимента на ЕС 1055 по программе, составленной на языке Форт-ран-1У. Решались известные тестовые задачи коммивояжера размерности от п=5 до п =20. В частности, выяснена перспективность применения новой схемы устранения подциклов по сравнению с классической. Кроме того, выяснены преимущества применения стратегии выбора Л.. , при которой выбирается, когда возможно, второе зна-

*)Bellmore M.,Maione J. Pathalogy of traveling salesman subtour-elimination algorithms.-Operations Research,1971, N2,p.278-301

1° . Для (1,*) находим

Где целое,и1Л4',(ни^сЬ.,имЛ .

2°.Из уравнения (53а) и начального условия (536), замкнутого управлением и=1Л° 1Л |Ч ) , определяемого согласно (56), находим управление (Ло^-Ц (.ЦМ ) и процесс

3 , Строится функция , обеспечивавшая выполнение

условий (13а),(136) для задачи (52)-(54), где функции ^ и (у вычисляются с помощью найденной I Далее для этой функции

операции 1° и 2° повторяются, в результате чего находится процесс-и а ,

Обоснование алгоритму дает

Теорема 6.2. Для процессов и и ^справедливо неравенство:

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

X * ^

Итак, алгоритм п.6.3 осуществляет приближение "сверху" по функционалу и тем самым в п.п. 6.2, 6.3 построены•на основании задания функции (^Ч V в виде (55) новые двусторонние алгоритмы.

В п. 6.4 рассматривается процедура сведения одной нелинейной транспортной задачи целочисленного программирования (в которую, в частности, укладывается квадратичная задача назначения из главы 5) к- модели вида (49)-(51).

В п. 6.5 с помощью нелинейного задания функции Ч^^У) и приближения "снизу" по функционалу п.6.2 решаются три нетривиальных модельных примера невысокой размерности, "плохо берущиеся" с помощью схемы множителей Лагранжа.

В Приложениях 1,2,3 многие из разработанных в главах 1-6 алгоритмов применяются для решения конкретных проблем.

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

объемы накопителей данных для каждого вычислительного центра. Второй класс задач возникал в процессе функционирования сети и был связан с решением отдельных задач С типа АСУ), необходимых для поддержания работы ИФВЦ.

В П.1.1.1 и ПЛ.1.2 приводятся постановка задачи и оптимизационная модель ИФВЦ с коммутацией сообщений, а также ее алгоритмическое обеспечение (разработанное совместно с Ыотусом O.A.), основанное на декомпозиции исходной задачи на две подзадачи.

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

П.1.2 рассматривается одна из типичных задач второго класса, связанная собственно с функционированием ИФВЦ. - задача формирования информационных массивов. В П.1.2Л приводятся содержательная постановка задачи и ее линейная целочисленная модель. В ПЛ.2.2 - один разрешимый случай (задача размещения диагональных элементов), знание решения которой позволяет построить допустимое решение (с оценкой степени оптимальности по функционалу - П.1.2.3) для общей задачи, поставленной в ПЛ.2.1. Для выделения решения в разрешимом случае используются результаты п.3.2 по задаче распределения.

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

Результаты разработок, представленных в П.1.1, ПЛ.2 внедрены в ВИНИТИ ГК и АН СССР с годовым экономическим эффектом 35 тыс. рубле в год.

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

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

В П.2.1 изучается задача формирования пар максимально связанных элементов, сводящаяся к симметричной ЗН (отличающейся от классической ЗН наличием дополнительных связей вида и^« = и^ 1,^ £ N=^1,2, . . . Для нее предлагается новый алгоритм на основе предложенной в п.4.2 реализации ЭО для задачи коммивояжера.

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

Результаты разработок, представленных в П.2.1 и П.2.2, внедрены в НИИ Радиотехники Министерства радиопромышленности.

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

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

Таким образом, для этой задачи с числом ограничений 2^-15 реализованы двусторонние алгоритмы. По существу разработанное программное обеспечение для задачи оптимального резервирования представляет собой инструментарий для численного решения задач выпуклого целочисленного программирования.

В П.3.2 рассматривается вторая задача - об оптимальном распределении неоднородных средств (задача целераспределения). Непрерывный вариант этой задачи хорошо изучен в исследовании операций, для дискретного варианта к настоящему времени не получено сильных алгоритмов, Здесь приводится постановка задачи целераспределения, в которой учитывается дополнительное ограничение на распределение ассигнований, выделяемых на закупку вооружений и военной техники, и развивается новый способ вычисления нижней границы, основанный на линейном задании функции M^t,^). Решены две прикладные задачи: оптимальное распределение самолетов противолодочной обороны, оснащенных различными средствами обнаружения, по районам театра военных действий; оптимальное распределение адьтернативных типов самолетов стратегической авиации по аэродромам базирования в условиях ограниченного ядерного конфликт,}, при разовом вылете самолетов. Представлены результаты решения конкретных задач размерностей т=5, п=7 и га—20. п=24 .

Результаты разработок, представленных в П.3.1, П.3.2 внедрены в НИИ экономики, планирования и управления Министерства авиационной промышленности.

Основные результаты диссертации получены автором лично. Результатами, полученными автором совместно являются:

1.с В.Ф. Кротовым:

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

сдвига по А при максимизации функционала 2СЧ*) j

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

2.с O.A. Мотусом:

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

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

описываемая обобщенной задачей назначения; 3.с А.Л. Герасимовым:

-здесь автору принадлежит разработка ¿лгоритма решения задачи формирования пар максимально связанных элементов (симметричной задачи назначения) и разработка алгоритма решения задачи формирования последовательности пар максимально связанных элементов (задачи маршрутизации) ;

-фортрановская реализация алгоритмов решения задач назначения и коммивояжера.

По теме диссертации опубликованы следующие основные работы:

1.Кротов В.Ф.,Сергеев С.И. Методы решения задач дискретного программирования —М.:Моек. эконом.-стат. ин-т,1981,154с.

2.Кротов В.Ф..Сергеев С.И. Применение достаточных условий оптимальности для решения задач линейного и линейного-целочисленного программирования. -В кн.:Моделирование технико-экономических процессов. -М.:Моск. эконом.-стат. ин-т,1978,с.4-42.

3.Кротов В.Ф..Сергеев С.И. Задача распределения. Труды V Всесоюзного совещания-семинара по управлению большими системами.-Алма-Ата:1978, с.112-113.

4.Кротов В.Ф.,Сергеев С.И. Точный алгоритм решения задачи коммивояжера. -Тезисы докладов I Всесоюзного совещания "Методы и программы решения оптимизационных задач на сетях и графах". Новосибирск,1980, с.39-41.

5.Кротов В.Ф..Сергеев С.И. Новый точный алгоритм решения задачи о коммивояжере.-В кн.:Методы и модели экономической кибернетики.-М.: Моск. эконом.-стат. ин-т,1980, с.3-39.

6.Кротов В.Ф..Сергеев С.И. Вычислительные алгоритмы решения задач линейного целочисленного программирования, основанные на достаточных условиях оптимальности.-Тезисы докладов VIII Всесоюзного совещания

по проблемам управления. Кн.2. Москва-Талин,1980, с.459-461.

7.Кротов В.Ф.,Сергеев С.И. Вычислительные алгоритмы решения некоторых задач линейного и линейно-целочисленного программирования, I.-Автоматика и телемеханика,1980, N12, с.86-96.

8.Кротов В.Ф.,Сергеев С.И. Вычислительные алгоритмы решения некоторых

задач линейного и линейно-целочисленного программирования,II.-Автома-»

тика и телемеханика,1981, N1, с.86-96.

9.Кротов В.Ф..Сергеев С.И. Вычислительные алгоритмы решения некоторых задач линейного и линейно-целочисленного программирования, III.-Автоматика и телемеханика,1981, N3, с.83-94.

10.Кротов В.Ф..Сергеев С.И. Вычислительные алгоритмы решения некоторых

задач линейного и линейно-целочисленного программирования, IV.-Автоматика и телемеханика,1981, N4, с.103-112.

11.Сергеев С.И. Приближенное решение одной задачи размещения.-В кн.: Опыт применения прикладных методов математики и вычислительной техники в народном хозяйстве,Ч.III.М.:ВСНТО,1980,с.9-19.

12.Сергеев С.И. Алгоритм решения задачи коммивояжера (обзор).-В кн. Моделирование технико-экономических процессов,-М.:Моек. экономико-статист. ин-т,

13.Сергеев С.И. Улучшенный алгоритм решения задачи коммивояжера.-Тезисы докладов II Всесоюзного совещания "Методы и программы решения оптимизационных задач на сетях и графах" ,ч.2, Новосибирск, 1982,

с.133-136.

14.Сергеев С.И. Об одном точном алгоритме решения задачи коммивояжера. -В кн.Моделирование экономических процессов.-М.:Моск. экономико-статист. ин-т, 1983, с.3-27.

15. Мотус О.А.,Сергеев С.И.Оптимизационная модель сети вычислительных центров с учетом распределения баз данных.-Тезисы докладов III Всесоюзного совещания на сетях и графах" ,ч.I, Новосибирск,1984,

с.151-153.

16.Сергеев С.П., Мотус O.A. Новая граница снизу для обобщенной задачи назначения.-В кн.Актуальные вопросы автоматизации обработки данных

и использование математических методов в экономических исследованиях -М.:Моск. экономико-статист, ин-т,1986, с.56-73.

17.Сергеев С.И. Новая нижняя граница для квадратичной задачи назначения.-Журнал вычислительной математики и мат. физики,1987, N12,

с. 1802-1810.

18.Кротов В.Ф.,Сергеев С.И. Двусторонние методы решения задач дискретной оптимизации.-Тезисы докладов III Всесоюзной школы "Дискретная оптимизация и компьютеры".-М.:1987, с.124-125.

19.Сергеев С.И. Нижние границы и алгоритмы решения некоторых задач с взаимозависимыми назначениями.-Деп. в ВИНИТИ (Москва) (Представлено ред. журн. "Техническая кибернетика), N 1191-В88 от 11.02.88, 56с.

20.Сергеев С.И. Границы для квадратичной задачи назначения. В кн.: Модели и методы исследования операций. Наука, Новосибирск,1988, с. 112-134.

21.Герасимов А.Л..Сергеев С.И. Алгоритм размещения при автоматизированном проектировании двусторонних печатных плат повышенной плотности.-Деп. в ВИНИТИ (Москва) (Представлено ред. журн. "Управляющие системы и машины) N 8013-В88 от II.II.08,14с.

22.Кротов В.ф..Сергеев С.И. К общему подходу решения задач дискретной 32

оптимизации. В кн.Моделирование и оптимизация управляемых динамических систем. Институт Проблем Управления,М.:1989, с.5-11.

23.рергеев С.И, Фельдман Л.И. Оптимальное резервирование элементов.-Экономика и управление, N 1,М.:1989, с.10-17.

24.Герасимов А.Д..Сергеев С.И. Локальный САПР для проектирования двусторонних печатных плат.-Тезисы докладов XI Всесоюзного совещания по проблемам управления.М.:1989, с.479.

25.Меламед И.И.,Сергеев С.И.¡Сигал И.Х. Вычислительные алгоритмы решения задачи коммивояжера. Общие результаты, I,-Автоматика и телемеханика, 1989, N 9, с.3-33.

26.Меламед И.И.,Сергеев С.И.,Сигал И.Х. Вычислительные алгоритмы решения задачи коммивояжера. Точные алгоритмы,11,-Автоматика и телемеханика, 1989, N 10, с.3-29.

27.Меламед И.И.,Сергеев С.И.,Сигал И.Х. Вычислительные алгоритмы решения задачи коммивояжера. Приближенные методы,III,-Автоматика и телемеханика, 1989, НИ, с.3-26.

28.Кротов В.Ф., Лагоша Б.А., Лобанов С.М.,Сергеев С.И, Данилина Н.И. Основы теории оптимального управления. Под. ред. Кротова В.Ф.,М.:Высшая школа,1990, 30п.л. (из них автору принадлежат бп.л.).

29.Методы решения задач теории оптимального управления на основе принципа расширения. Под ред. Гурмана В.И., Константинова Г.Н.,Новосибирск, Наука, 1990, 12п. л . (из них автору принадлежат 2.2п.л.).

30.Сергеев С.И. Общий подход для решения задач дискретной оптимизации. Тезисы докладов Международной школы-семинара по методам оптимизации и их приложениям. Иркутск 1989, с.177-178.

31.Сергеев С.И. Алгоритмы решения сепарабельной задачи дискретной оптимизации. -Журнал вычислительной математики и мат. физики,1990, N8, с.1273-1275.

32.Герасимов А.Л.,Сергеев С.И. Алгоритмы размещения для проектирования двусторонних печатных плат.-Автоматика и телемеханика, 1990, N7, с.115-124.

Подп. к печ. 08.04.92

Типография МАП.

Зак. 365

Тир, 100