Лексикографические алгоритмы дискретной оптимизации и их реализация

• Автор: Гренджа, Владимир Иванович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Ужгород
• Количество страниц: 182 c. : ил

Глава I. АЛГОРИТМ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

§ I. Предварительные сведения

§ 2. Прямой поиск /-максимума ограниченного декартова множества при дополнительных ограничениях

§ 3. Поиск /-максимума множества при наличии

лексикографического ограничения

§ 4. Поиск целочисленного -/-максимума множества,

заданного системой векторных неравенств

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

§ 6. Иллюстрация алгоритмов

§ 7. Алгоритмы поиска для многомерной задачи о

ранце
§ 8. Параллельные вычисления в алгоритмах
Глава 2. АЛГОРИТМ ЧАСТИЧНО ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
§ 9. Модификация двойственного алгоритма отсечения
§ 10. Применение "опережающих" отсечений для решения задач с недискретно определенной целевой функцией
ВЫВОДЫ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ А. Программные реализации алгоритмов поиска
решения многомерной задачи о ранце
ПРИЛОЖЕНИЕ Б. Программные реализации алгоритмов частично дискретной оптимизации

АКТУАЛЬНОСТЬ РАБОТЫ. В настоящее время в решении дискретных задач оптимизации достигнут определенный прогресс. Однако существующие методы решения этих задач не всегда удовлетворяют потребностям практики. При оценке того или иного метода, как правило, наравне с количеством операций, необходимых для решения задачи, учитывается и сложность реализации соответствующих алгоритмов на ЭВМ. Эта сложность обусловливается как искажающим влиянием накапливаемых в процессе решения ошибок округления, так и запоминанием большого переменного объема промежуточной информации. Реализация алгоритмов в условиях округления результатов счета оказывает настолько пагубное влияние на процесс решения задачи, что в конечном итоге можно получить решение, далеко отстоящее от истинного, и даже может оказаться, что задача неразрешима, в то время как она имеет решение. Запоминание большого объема промежуточных результатов при реализации алгоритмов на ЭВМ связана с необходимостью использования медленно действующей памяти. Это в конечном счете значительно увеличивает время решения задач на ЭВМ и, кроме того, усложняет программирование. В связи с указанной сложностью решения дискретных задач оптимизации на ЭВМ особое значение приобретают алгоритмы, позволяющие избежать или, по крайней мере, уменьшить эти трудности. Весьма актуальной является и разработка алгоритмов, хорошо приспособленных для распараллеливания вычислений и удобных для реализации на многопроцессорных ЭВМ.
Как следует из работ [39-44-] , решение упомянутых проблем может быть основано на линейном (лексикографическом) упорядочении дискретного множества. При этом каждый алгоритм решения дискретной или частично дискретной задачи представляет собой лексикографический поиск, в итоге которого строится лексикографически монотонная последовательность точек в пространстве Я, . В общей схеме лексикографического поиска имеется возможность выполнения каждого шага на основании исходной информации о задаче (что позволяет избавиться от накапливаемых ошибок округления при переходе от шага к шагу), а также выполнения каждого шага вне зависимости от информации, полученной на предыдущих шагах (что позволяет избегать запоминания информации на этих предыдущих шагах). Кроме того, поиск точек строящейся лексикографически монотонной последовательности можно производить параллельно - поэтому эти алгоритмы хорошо приспособлены для реализации на многопроцессорных ЭВМ.
ЦЕЛЬЮ РАБОТЫ является:
- построение и обоснование алгоритмов лексикографического поиска решения задачи дискретного программирования с монотонными по каждой переменной вектор-функциями в ограничениях;
- построение и исследование алгоритмов решения частично дискретной задачи линейного программирования, основанных на идеях лексикографического поиска и метода отсечений;
- практическая реализация построенных алгоритмов на ЭВМ.
МЕТОДИКА ИССЛЕДОВАНИЙ. В основу исследований, связанных
с построением и обоснованием алгоритмов лексикографического поиска, положены результаты теории лексикографической оптимизации. Исследования, связанные с построением алгоритмов решения

fm <0). Отсюда следует, что X * ї ф , и -/-максимумом этого множества является -/-максимум множества
[сс е P О °x
Таким образом, координаты точки 0С.*6пазс. X вычисляем по формулам:
х/= таосjcx I fXocx>b)=ocf-8 * о; 0^ссх^2 3 эсл- целое ] =2,
JC^mcuc^x2^3(j2,^) = //-2oc2£0) 0 Точка ОС = (£,4; не удовлетворяет неравенству (6.2), поэтому ищем -/-максимум множества
X *« P применяя алгоритм, описанный в пункте 2 из § 3. Так как выполняется условие
[ос2е[ор]^ф,ОС^ ±0 + 6ос^30ьос^3^ ОС^- целое]/0 (6.7)
(здесь /с 2,хе) принимает минимальное значение в точке С£,о) и (Хор) <30), ТО X X 0 И / -максимумом этого множества является -/-максимум множества (6.7). Следовательно, координаты точки ОС 2=&псих. X ‘ ’вычисляем следующим образом:
о2 ох
ocl=ocx =£,
ос°й~гг1С1эс[э(:£^Х2,осг)**0+6Э!:2*зо-, о*осл*зу огл- целов}=д
°г
Точка -X = (2,3 ) удовлетворяет условиям (6.2)-(6.6), поэтому она является -/-максимумом ос множества X , причем ^О(ос) = Для этого условие Д(ос) = cc.x*(pc£~s)X 8+* представляем в виде неравенства
£о$ш-*£-их1л-5)г9 (6.8)
и с помощью алгоритма, описанного в пункте 2 из § 3, ищем /-