Анализ алгоритма покоординатного подъема для задач дискретной оптимизации

• Автор: Шенмайер, Владимир Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Новосибирск
• Количество страниц: 109 с.

Оглавление
Введение
1 Условия точности алгоритма
в случае линейного целевого функционала
1.1 Постановки задач и описание алгоритма
1.2 Новые обобщения теоремы Радо-Эдмондса
« . '"Г"'
1.3 Условия точности в терминах доминирования
1.4 Сильное обменное свойство
1.5 Достаточные условия точности
2 Условия точности алгоритма
в случае сепарабельного целевого функционала
2.1 Постановка задачи и описание алгоритма
2.2 Известные результаты
2.3 Критерий точности в общем случае
2.4 Достаточные условия точности
2.5 Одно обобщение матроидов и
целочисленных полиматроидов
3 Оценки погрешности алгоритма
3.1 Постановки задач и описание алгоритма
3.2 Известные результаты
3.3 Обобщенные ранговые функции
3.4 Оценки относительной точности алгоритма
3.5 Субмодулярность и монотонность
обобщенных ранговых функций
3.6 Два примера: задача коммивояжера
и обобщенная задача коммивояжера
Заключение
Список литературы
Публикации автора по теме диссертации

Введение
Исследуется вопрос о разрешимости задач дискретной оптимизации алгоритмом покоординатного подъема (жадным алгоритмом). Цели диссертации: нахождение условий точности и оценок погрешности алгоритма, отыскание классов задач, разрешимых им с приемлемой (например, константной) точностью, выявление свойств множества допустимых решений, влияющих на точность алгоритма.
Рассматриваются две основные задачи: задача целочисленного программирования с линейным целевым функционалом и задача целочисленного программирования с вогнутым сепарабельным целевым функционалом. Также рассматриваются задача максимизации аддитивного функционала на семействе множеств, задача о длиннейшем пути в специальной постановке, задача коммивояжера и одна обобщенная задача коммивояжера.
Для решения данных задач предлагается использовать алгоритм, действующий по схеме покоординатного подъема с единичным шагом. Алгоритм начинает работу с некоторого начального решения (например, нулевого вектора) и на каждом шаге увеличивает на единицу одну из компонент текущего решения таким образом, чтобы целевой функционал имел максимально возможное приращение.
Идея алгоритма настолько проста и естественна, что невозможно проследить, кто первым ее придумал. Исследования алгоритма проводились еще в 1920-е годы [17]. В последние десятилетия интерес к

Теорема 1.7. Пусть система достижимых векторов 3 С N1 удовлетворяет следующему условию:
если X < У, X £ 3, У 6 0(3?), * £ ./(X) и Х(г) - У(г), то У + е,- — е_/ £ 3 при некотором ] £ <7(Х) П /(У — X). (1.14)
Тогда алгоритм покоординатного подъема находит оптимальное решение задачи (1.1).
Доказательство. Согласно теореме 1.5 достаточно ограничиться случаем, когда ш > 0. Пусть вектор X получен по правилам алгоритма покоординатного подъема. Тогда «/(X) = 0 и X может быть представлен в виде X = 5*, где 5 = (г(1)
Предположим, что некоторый вектор У £ #(3) обладает свойством гг (У) > -ш(Х) и среди всех таких векторов вектор У определяет максимальный номер п такой, что < У. Так как Д(Х) = 0, то согласно условию достижимости (1.3) имеем X £ #(3) и, следовательно, п < к. При этом элемент г = г(п + 1) принадлежит множеству «/(£„) и 5„(г) = У(г). Отсюда и из (1.14) следует, что существует элемент ; £ /(£„) такой, что 5„(у) < У (у) и У + ег- — е_,- £ 3. В силу неравенства 5П < У имеем 5„+1 = Sn + ei < У + е,- — ер С другой стороны, у £ /(5„) и, следовательно, согласно правилам алгоритма покоординатного подъема получаем го(г) > ии). Поэтому го (У + е,- - еу) > го (У).
Пусть У' — такой вектор, что У' £ Н(3) и У' > У + ег- — ер Тогда в силу неотрицательности функционала го справедливо неравенство го(У') > го (У + е* — еу). Следовательно, го (У') > го(У). С другой стороны, 5„+1 < У'. Но это противоречит выбору вектора У. Теорема доказана.