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

ВВЕДЕНИЕ.

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

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

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

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

§ Поиск целочисленного /'-максимума множества, заданного системой векторных неравенств.

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

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

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

§ 8. Параллельные вычисления в алгоритмах.

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

§ 9. Модификация двойственного алгоритма отсечения

§ 10. Применение "опережающих" отсечений для решения задач с недискретно определенной целевой функцией.

ВЫВОДЫ.

АКТУАЛЬНОСТЬ РАБОТЫ. В настоящее время в решении дискретных задач оптимизации достигнут определенный прогресс. Однако существующие методы решения этих задач не всегда удовлетворяют потребностям практики. При оценке того или иного метода, как правило, наравне с количеством операций, необходимых для решения задачи, учитывается и сложность реализации соответствующих алгоритмов на ЭВМ. Эта сложность обусловливается как искажающим влиянием накапливаемых в процессе решения ошибок округления, так и запоминанием большого переменного объема промежуточной информации. Реализация алгоритмов в условиях округления результатов счета оказывает настолько пагубное влияние на процесс решения задачи, что в конечном итоге можно получить решение, далеко отстоящее от истинного, и даже может оказаться, что задача неразрешима, в то время как она имеет решение. Запоминание большого объема промежуточных результатов при реализации алгоритмов на ЭВМ связана с необходимостью использования медленно действующей памяти. Это в конечном счете значительно увеличивает время решения задач на ЭВМ и, кроме того, усложняет программирование. В связи с указанной сложностью решения дискретных задач оптимизации на ЭВМ особое значение приобретают алгоритмы, позволяющие избежать или, по крайней мере, уменьшить эти трудности. Весьма актуальной является и разработка алгоритмов, хорошо приспособленных для распараллеливания вычислений и удобных для реализации на многопроцессорных ЭВМ.

Как следует из работ [39-44] , решение упомянутых проблем может быть основано на линейном (лексикографическом) упорядочении дискретного множества. Ери этом каждый алгоритм решения дискретной или частично дискретной задачи представляет собой лексикографический поиск, в итоге которого строится лексикографически монотонная последовательность точек в пространстве /2. . В общей схеме лексикографического поиска имеется возможность выполнения каждого шага на основании исходной информации о задаче (что позволяет избавиться от накапливаемых ошибок округления при переходе от шага к шагу), а также выполнения каждого шага вне зависимости от информации, полученной на предыдущих шагах (что позволяет избегать запоминания информации на этих предыдущих шагах). Кроме того, поиск точек строящейся лексикографически монотонной последовательности можно производить параллельно - поэтому эти алгоритмы хорошо приспособлены для реализации на многопроцессорных ЭВМ.

ЦЕЛЬЮ РАБОТЫ является:

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

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

- практическая реализация построенных алгоритмов на ЭВМ.

МЕТОДИКА ИССЛЕДОВАНИЙ. В основу исследований, связанных с построением и обоснованием алгоритмов лексикографического поиска, положены результаты теории лексикографической оптимизации. Исследования, связанные с построением алгоритмов решения частично дискретной задачи линейного программирования, основаны на идеях лексикографической оптимизации и метода отсечений.

НАУЧНАЯ НОВИЗНА. Разработаны алгоритмы лексикографического поиска решения задачи дискретного программирования с монотонными по каждой переменной вектор-функциями в ограничениях.

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Разработанные в диссертации алгоритмы лексикографического поиска могут быть использованы для решения широкого класса полностью дискретных задач оптимизации, система ограничений которых описывается с помощью системы вектор-функций, монотонных по каждой переменной. К классу этих задач принадлежит, например, полностью дискретная задача линейного программирования. Эти алгоритмы позволяют уменьшить искажающее влияние накапливаемых ошибок округления и не требуют дополнительного объема памяти для хранения промежуточной информации. Кроме того, эти алгоритмы хорошо приспособлены к распараллеливанию поиска и удобны для реализации на многопроцессорных вычислительных системах. Предлагаемые в диссертации алгоритмы решения частично дискретной задачи линейного программирования также обладают указанными достоинствами.

АПРОБАЦИЯ РАБОТЫ. Материалы диссертации докладывались на I и П конференциях молодых ученых Западного научного центра АН УССР /Ужгород, 1974- г.; Ужгород, 1975 г./, на Республиканских конференциях "Вычислительная математика в научно-техническом прогрессе" /Канев, 1974- г.; Киев, 1978 г.; Канев, 1982 г./, на Всесоюзном совещании "Математическое моделирование, системный анализ и оптимизация химико-технологических и энерготехнологических систем и оборудования" /Ужгород, 1981 г./, на 35 и 36 научных конференциях профессорско-преподавательского состава Ужгородского госуниверситета /Ужгород, 1982 г.; Ужгород, 1983 г./, на П Республиканской школе-семинаре по дискретной оптимизации /Ужгород, 1983 г./. Программные модули, реализующие предлагаемые в диссертации алгоритмы, включены в пакет прикладных программ ДИСПРО, разработанный в Институте кибернетики им. В.М.Глушкова АН УССР.

ПУБЛИКАЦИИ. Материалы диссертации опубликованы в работах [8-11, 4-0, 43, 45-4б].

СТРНТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, двух глав, выводов, двух приложений и списка литературы, содержащего 55 наименований. Общий объем работы 181 страница. Объем работы без приложений III страниц, в том числе 7 рисунков и 7 страниц литературы.

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

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

2. Разработаны алгоритмы лексикографического поиска для ре-шенифногомерной задачи о ранце с булевыми и целочисленными переменными. Поиск -/-максимумов и -/-минимумов для этой задачи производится особенно просто. Алгоритм решения задачи о ранце с булевыми переменными, основанный на поиске -/-максимумов, а также алгоритм решения этой задачи, основанный на поочередном поиске -/-максимумов и -/-минимумов, реализованы на ЭВМ (язык программирования Ф0РТРАН-1У). С помощью разработанных программных модулей проведено экспериментальное исследование этих алгоритмов при решении тестовых задач. Приведенные результаты вычислительных экспериментов подтверждают эффективность разработанных алгоритмов, что позволило включить программные модули в программное обеспечение пакета прикладных программ ДИСПРО.

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

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

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

6. Осуществлена программная реализация возвращающегося алгоритма и предложенного автором алгоритма приближенного решения частично дискретных задач линейного программирования с булевыми и целочисленными переменными (язык программирования ФОРТРАН-1У). Проведено экспериментальное исследование этих алгоритмов при решении тестовых задач на ЭВМ. Результаты вычислительных экспериментов подтверждают устойчивость алгоритмов к ошибкам округления. Разработанные программные модули включены в программное обеспечение пакета прикладных программ ДИСПРО.

1. Булавский В.А., Звягина P.A., Яковлева М.А. Численные методылинейного программирования (специальные задачи).- М.: Наука, 1977.- 368 с.

2. Венгерова Н.В., Финкельштейн Ю.Ю. Экспериментальное исследование метода отсечения и ветвления.- Изв. АН СССР. Техническая кибернетика, 1974, № 3, с. 85-90.

3. Венгерова Н.В., Финкельштейн Ю.Ю. К вопросу об эффективностиметода ветвей и границ,- Экономика и матем. методы, 1975, т. XI, № I, с. 186-193.

4. Волкович В.Л., Волошин А.Ф. Об одной общей схеме метода последовательного анализа и отсеивания вариантов.- Кибернетика, 1978, №4, с. 98-105.

5. Вотяков A.A. Целочисленное программирование, сравнение отсечений.- Экономика и матем.методы, 1972, т. УШ, вып. I, с. 107-116.

6. Глушков В.М. О системной оптимизации.- Кибернетика, 1980,5, с. 89-90.

7. Глушков В.М., Иванов В.В., Михалевич B.C., Сергиенко Н.В.,

8. Стогний A.A. Резервы оптимизации вычислений.- Киев: 1977.54 с. (Препринт/ АН УССР. Институт кибернетики; 77-67).

9. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения, I-П.- Кибернетика, 1971, № 6, с. 2-6; 1972, № 2, с. 72-75.

10. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования.- М.: Наука, 1976.- 192 с.

11. Журавлев Ю.И. Локальные алгоритмы вычисления информации, 1-П.

12. Кибернетика, 1965, № I, с. 12-19; 1966, № 2, с. 1-Й.

13. Журавлев Ю.И., Финкельштейн Ю.Ю. Сфера применения методов дискретного программирования.- В кн.: Применение исследованияопераций в экономике.- М.: Экономика, 1977, с. 29-69.

14. Калашников B.B. Некоторые задачи лексикографической оптимизации.- В кн.: Оптимизация, вып. 21 (38).- Новосибирск,1978, с. 109-120.

15. Карманов В.Г. Математическое программирование.- М.: Наука,1980.- 256 с.

16. Ковалев М.М. Дискретная оптимизация (целочисленное программирование).- Минск: йзд-во Белорусского ун-та, 1977.- 192 с.

17. Корбут A.A., Финкелынтейн Ю.Ю. Дискретное программирование.1. М.: Наука, 1969.- 368 с.

18. Михалевич B.C. Последовательные алгоритмы оптимизации и ихприменение.- Кибернетика, 1965, fö I, с. 45-56; № 2, с. 8588.

19. Михалевич B.C., Ермольев Ю.М., Шкурба В.В., Шор Н.З. Сложныесистемы и решение экстремальных задач.- Кибернетика, 1967, № 5, с. 29-39.

20. Михалевич B.C., Сергиенко Н.В., Быков В.Н. и др. О математическом обеспечении пакета программ ДИСПРО для решения задач дискретного программирования.- Киев, 1979.- 59 с.-(Препринт/АН УССР, Институт кибернетики; 79-3).

21. Михалевич B.C., Сергиенко Н.В., Кукса А.Н. и др. Результатыэкспериментального исследования эффективности методов, включенных в пакет прикладных программ ДИСПРО.- Киев,1980.-68 е.- (Препринт/АН УССР. Институт кибернетики; 80-47).

22. Моисеев H.H. Элементы теории оптимальных систем.- М.: Наука,1975.- 526 с.

23. Романовский И.В. Алгоритмы решения экстремальных задач.- М.:1. Наука, 1977.- 352 с.

24. Сергиенко И.В. Вопросы построения и использования математического обеспечения методов оптимизации.- Киев, 1979.- 67 с.-(Препринт/АН УССР. Институт кибернетики; 79-38).

25. Сергиенко И.В., Быков В.Н. Метод решения обобщенной задачи оранце с использованием параллельных вычислений.- Докл. АН УССР, 1980, серия "А", № 7, с. 81-83.

26. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методырешения дискретных задач оптимизации.- Киев: Наукова думка, 1980.- 276 с.

27. Сергиенко И.В., Гуляницкий Л.Ф. Фронтальные алгоритмы оптимизации для многопроцессорных ЭВМ.- Кибернетика, 1981, № 6, с. 1-4.

28. Федоров В.В. Численные методы максимина.- М.: Наука, 1979.280 с.

29. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования.- М.: Наука, 1976.- 264 с.

30. Ху Т. Целочисленное программирование и потоки в сетях.- М.:1. Мир, 1974.- 520 с.

31. Червак Ю.Ю. Об одном методе отсечений для дискретных задач.

32. Укр. матем. журнал, 1971, № 6, с. 839-843.

33. Червак Ю.Ю. Алгоритм лексикографического поиска решения дискретных задач линейного программирования.- Киев, 1971.-II с. (Препринт/АН УССР. Институт кибернетики; 71-37).

34. Червак Ю.Ю. Определение оптимальной целочисленной выпуклойлинейной комбинации точек. Общий дискретный случай.- В кн.: Матем. методы решения экономических задач. Сборник 3.- М.:1. Наука, 1972, с. 130-132.

35. Червак Ю.Ю. 0 методе лексикографического поиска решения длядискретных задач линейного программирования.- Экономика и матем. методы, 1973, т. IX, вып. 6, с. П38-П41.

36. Червак Ю.Ю. Методы лексикографического поиска решения для дискретных задач выпуклого программирования.- Укр. матем. журнал, 1974, т. ХХУ1, вып. 2, с. 269-272.

37. Червак Ю.Ю. Лексикографический поиск решений задач дискретного программирования (текст лекций). Ужгород: Изд-во Ужгородского ун-та, 1977.- 43 с.

38. Червак Ю.Ю. Возвращающийся алгоритм метода отсечений и методветвей и границ.- Экономика и матем. методы, 1978, т. Х1У, вып. 5, с. 1002-1005.

39. Червак Ю.Ю. Поиск лексикографически максимальной дискретноопределенной точки выпуклого множества.- В кн.: Матем. методы решения экономических задач. Сборник 8, Наука, 1979, с. 69-75.

40. Червак Ю.Ю., Гренджа В.И., Кузка А.И. Модель целочисленногопрограммирования задачи оптимального планирования обслуживания требований в системе приборов.- Ужгород, 1981.- Деп. ВИНИТИ, tö 1019-82 Деп.- 7 с.

41. Червак Ю.Ю. Об условиях существования решений задач лексикографической оптимизации.- Изв. АН СССР. Техническая кибернетика, 1982, № 6, с. 65-71.

42. Шкурба В.В. Интервалы очередности в задачах упорядочения.- Кибернетика, 1970, № 2, с. 77-79.

43. Шор Н.З. Методы минимизации недифференцируемых функций и их