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

Глава I. Локальные алгоритмы решения квазиблочных задач дискретного программирования.

§1. Основные определения. ГО

§2. Прикладные квазиблочные задачи.

§3. Локальный алгоритм как частная реализация метода последовательного анализа вариантов.

§4. Связь локального алгоритма с постоптимальным анализом в дискретном программировании.

§5. Эффективная реализация и структурная оптииизация локального алгоритма.

Глава П.Исследование эффективности локального алгоритма

§1. Сравнение оценок эффективности при решении задач дискретного программирования с помощью локального алгоритма.

§2. Оценка эффективности локального алгоритма при использовании постоптимального анализа.г.

§3. Оценки эффективности локального алгоритма

§4. Исследование эффективности локального алгоритма с помощью машинного эксперимента.

Глава Ш. Исследование свойств квазиблочных матриц.

§1. Необходимое условие к -квазиблочности матрицы и оценка числа всевозможных к -квазиблочных матриц.

§2. Оценка максимального числа слабо связанных блоков для данной матрицы.

§3. Оценки числа всевозможных разбиений данной матрицы на слабо связанные блоки.

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

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

3 а кл ю ч е н и е

ДГ и т е р а т у р а

ПРЮЮ1ЕНИЕ.

В настоящее время весьма актуальной является задача разработки методов решения задач дискретного программирования большой размерности, которые появляются во многих приложениях исследования операций [I] . К настоящему времени разработано немало перспективных алгоритмов в дискретном программировании [2-2^ , однако большие размеры задач - камень преткновения для них: "Достижения в применении, вычислительных аспектах и теории целочисленного программирования значительны., однако размеры задачи остаются главным ограничением" [29^ .

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

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

Аддитивный алгоритм Балаша £35,3б] модифицирован авторами раэтот метод подвергся модификации другие алгоритжены решения задачи целочисленного программирования, имеющей следующий вид: = С ОС —^ пъСп, при ограничениях где матрица имеет блочную структуру.

В [зв] построена динамическая модель развития отрасли пластмасс, имеющая блочную структуру.

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

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

Впервые локальный алгоритм применен к задачам булевского линейного программирования в [45] . В [46, 47] локальный алгоритм модифицирован для решения квазиблочных задач с дополнительными ограничениями. Исследованию локальных алгоритмов посвящены также работы [48,49] . Отметим, что эффективность локального алгоритма, вопросы его конкретной реализации, свойства квазиблочных матриц совершенно не были исследованы.

Перейдем к постановке задаче. Рассматривается локальный алгоритм у в сочетании с алгоритмом дискретного программирования, имеющим оценку эффективности ^(п), для решения к -квази блочной задачи дискретного программирования с п> булевскими переменными. Локальный алгоритм ОЬусводит решение задачи к решению к пакетов задач Задачи

1 / каждого пакета можно упорядочить Сструктуризовать) и ре шать их согласно этому упорядочению, используя при решении задач информацию, полученную в процессе решения задач предшествующих. Возникают следующие задачи: I. Задача структурной оптимизации локального алгоритма ОС»-. 2. Сравнить ^(^г) и оценку эффективности локального алгоритма 01з. Найти пьаос (К, к\ пь^щ £п^*?,к)} (ЕосуО**))^где л матрица условий линейной задачи 2 ; Найти оценки для

I ^ А I 9 где ^ А ~ множество всех разбиений на к слабо связанных блоков матрицы ; 5. Оценить ) - число слабо связанных блоков, на которые можно оазбить Д ; 6. Найти к ,

Я^КлТакие, что игн кК нахождение оптим 1 а Л»СО ОХш мального разбиения).

К)

Итак, изложим основные цели работы:

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

2. Исследование эффективности локальных алгоритмов на классе квазиблочных задач дискретного программирования (оценки эффективности определяются согласно [50 - 52]|).

3. Выяснение влияния характеристик квазиблочных задач на эффективность их решения и исследование комбинаторных свойств квазиблочных матриц.

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

Перейдем к изложению структуры работы.

В главе I рассматриваются вопросы эффективной реализации локальных алгоритмов решения квазиблочных задач дискретного программирования. В §1 даются основные определения, необходимые для дальнейших рассмотрений: излагается локальный алгоритм, дается определение квазиблочных матриц, приводится алгоритм разбиения на слабо связанные блоки произвольной матрицы, описывается метод неявного перебора , даются определения оценок эффективности алгоритмов. В §2 выделен класс прикладных задач с квазиблочной структурой - класс задач оптимального резервирования ресурса, распределенного во времени, частными случаями которых является задача оптимального предварительного резервирования гостиничных номеров, задача оптимального резервирования ресурсов на турбазах, задача оптимальной аренды складских помещений £53,54] , задача оптимального выбора научно-исследовательских проектов [55] , задача оптимального планирования электроснабжения при аварии, задача оптимальной госпитализации больных и др. В §3 показывается, что локальный алгоритм является частной реализацией общей схемы последовательного анализа вариантов [56,57] . В §4 вскрывается связь локального алгоритма с постоптимальным анализом в дискретном программировании [58 - 68] , показывается, что эффективность локального алгоритма будет тем выше, чем выше эффективность процедуры постоптимального анализа, используемой в сочетании с локальным алгоритмом. В §5 связь между локальным алгоритмом и постоптимальным анализом используется при эффективной реализации и структурной оптимизации локального алгоритма. Здесь рассматриваются различные варианты организации вычислительного процесса. В частном случае, когда каждый блок задачи содержит по одному ограничению, постоптимальный анализ реализуется совсем просто, т.к. задачи внутри блоков представляют собой задачи о ранце, для решения которых используется метод динамического программирования.

Глава П посвящена исследованию эффективности локального алгоритма решения квазиблочных задач дискретного программирования. В §1 сравниваются оценки эффективности локального алгоритма при решении задач булевского линейного программирования в следующих двух случаях: I) когда задачи внутри блоков решаются с помощью полного перебора. В этом случае показывается, что локальный алгоритм в сочетании с полным перебором эффективнее полного перебора; 2) когда задачи внутри блоков решаются с помощью неявного перебора. Здесь показывается, что при достаточно небольшой перемычке между блоками локальный алгоритм в сочетании с неявным перебором эффективнее неявного перебора. В §2 находится оценка эффективности постоптимального анализа при решении пакета задач булевского линейного программирования методом неявного перебора и на основе этой оценки находится оценка эффективности локального алгоритма в сочетании с постоптимальным анализом для неявного перебора. В §3 исследуются оценки эффективности локального алгоритма в сочетании с полным перебором: найдены экстремальные значения оценок эффективности и среднее значение оценки эффективности локального алгоритма на классе квазиблочных задач дискретного программирования. В §4 исследуется эффективность локального алгоритма с помощью машинного эксперимента для класса задач оптимального резервирования. Данные задач порождаются с помощью генератора случайных чисел. Машинный эксперимент показывает, что локальный алгоритм эффективен при достаточно небольших перемычках, связывающих блоки.

В главе Ш исследуется ряд свойств квазиблочных матриц. В §1 выводится необходимое условие разбиваемости матрицы на |< слабо связанных блоков.Попутно находятся максимальное и минимальное число элементов внутри блоков. На основе этих оценок находится оценка числа всевозможных булевских |< -квазиблочных матриц.

Минимальное и максимальное число слабо связанных блоков, на которые можно разбить данную матрицу, находятся в §2. Для характеристики разреженности матрицы вводятся такие параметры, как максимальное и минимальное число элементов в столбце, максимальное и минимальное число строк матрицы, связанных с данной строкой. Здесь же найдено достаточное условие разбиваемости матрицы на к слабо связанных блоков. В §3 оценивается число всевозможных разбиений данной матрицы на слабо связанные блоки, причем разбиения матрицы получаются из заданного разбиения матрицы, построенного с помощью алгоритма {69^] , описанного в §1 главы I. В §4 дается оценка числа всевозможных разбиений матрицы инциденций задачи оптимального резервирования на слабо связанные блоки, здесь же получены оценки для минимального и максимального числа блоков в разбиении, причем в качестве параметров, характеризующих разреженность матрицы, взяты минимальная и максимальная длина заявки. В §5 ставится и решается для матрицы инциденций задачи оптимального резервирования задача оптимального разбиения матрицы на слабо связанные блоки, причем в качестве критерия эффективности берется оценка эффективности локального алгоритма при решении полученной квазиблочной задачи. Матрице инциденций задачи оптимального резервирования ставится в соответствие некоторая сеть, причем разбиениям матрицы на слабо связанные блоки соответствуют некоторые пути в сети, так что задача оптимального разбиения на блоки сводится к задаче отыскания кратчайшего пути в эквивалентной сети.

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

1. Исследована эффективность локального алгоритма на классе квазиблочных задач дискретного программирования; в случае неявного перебора и полного перебора показано, что локальный алгоритм в сочетании с алгоритмом дискретного программирования эффективнее, чем алгоритм дискретного программирования сам по себе.

2. Найдены экстремальные значения оценки эффективности локального алгоритма в сочетании с полным перебором, а так^е средняя величина оценки эффективности при !< =2 и асимптотическая формула для средней величины при к^-^ . Этим самым показано, что локальный алгоритм в сочетании с полным перебором при решении квазиблочных задач дискретного программирования существенно эффективнее полного перебора.

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

Локальный алгоритм реализован на ЭВМ в 3-х вариантах (I вариант - локальный алгоритм в сочетании с неявным перебором для решения задач оптимального резервирования; П вариант - локальный алгоритм в сочетании с неявным перебором и постоптимальным анализом для решения тех же задач; Ш вариант - локальный алгоритм в сочетании с алгоритмом динамического программирования для решения квазиблочных задач дискретного программирования, у которых каждый блок содержит одно ограничение) и произведен сравнительный машинный эксперимент с целью исследования реальных вычислительных возможностей локального алгоритма.

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

6. Исследован ряд свойств квазиблочных матриц : получены максимальное и минимальное число элементов внутри блоков к -квазиблочной матрицы, необходимое условие к -квазиблочности матрицы, достаточное условие к -квазиблочности матрицы, оценка числа всех к -квазиблочных матриц с элементами 0-1, оценка максимального числа блоков, на которые можно разбить данную матрицу; оценка числа разбиений на слабо связанные блоки заданной матрицы; решена задача оптимального разбиения матрицы инциденций задачи оптимального резервирования на слабо связанные блоки и реализован соответствующий алгоритм на ЭВМ.

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

ЗАКЛЮЧЕНИЕ.

1. Михалевич B.C., Ермольев Ю.М. Некоторые вопросы исследования операций. Тезисы докладов П Всесоюзной конференции по исследованию операций. М., 1976, 71-79.

2. Емедичев В.А. Дискретная оптимизация, последовательностные схемы решений I. Кибернетика , 1971, 7, №6, 109 121.

3. Емеличев В.А. Дискретная оптимизация, последовательностные схемы решений П. Кибернетика, 1972, 8, №2, 92-103.

4. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М., изд-во "Наука", 1969.

5. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование. М., изд-во "Мир", 1977.

6. Лебедев С.С. Целочисленное программирование и множители Лагран-жа. Экономика и математические методы, 1974, 10, №3, 592 610.

7. Романовский И.В. Методы неявного перебора для решения задач целочисленного программирования с бивалентными переменными. Известия вузов, Математика , 1970, 4, Ш, 17 29.

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

9. Фридман А.А. О некоторых современных направлениях в дискретной оптимизации. Экономика и математические методы,1977, 13, №5, III5 II3I.

10. Beale E.M.L., Tomlin J.A. An integer programming approach to a class of combinatorial problems. Mathematical Programming, 1972, 5, N5, 339-544.

11. Bradley G.H. Equivalent integer programs and canonical problems. Management Science, 1971, 17, N5, 354-366.

12. Breu R. tBurdet G. Branch and bound experiments in zero-one programming. Mathematical Programming Study 2, 1974, N.Y., 1-50.

13. Dakin R.J. A tree searcli algorithm for mixed integer programming problems. Computer Journal, 1965, 8, N3, 250-255.

14. Forrest J.J.H., Hirst J.P.H., Tomlin J.A. Practical solution of large mixed integer programming problems with UMPIRE. Management Science, 1974, 20, N5, 736-773.

15. Geoffrion A.M. An improved implicit enumeration approach for integer programming. Operations Research, 1969, 17, N3, 437-434.

16. Geoffrion A.M. A guided tour of recent practical advances in integer linear programming. Omega, 1976, 4, N1, 49-57*

17. Geoffrion A.M., Marsten R.E. Integer programming algorithms: a framework and state-of-the-art survey. Management Science, 1972, 18, N9, 465-491.

18. Gorrj G.A., Shapiro J.ff. An adaptive group theoretic algorithm for integer programming problems. Management Science, 197^, ^7, N5, 285-306.

19. Gorry G.A., Wolsey L.A. Relaxation methods for pure and mixed integer programming problems. Management Science,1972, 18, N5, 229-239.

20. Gue R.L., Liggett 3L.C., Cain K.C. Analysis of algorithms for the zero-one programming problems. Communications ACM,1968, 11, N12, 837-844.

21. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. Econometrica, 1960, 28, N3, 497-520.

22. Lemke C.E., Spielberg K. Direct search algorithms for zero-one and mixed-integer programming. Operations Research, 1967, 15, N5, 892-914.

23. Tomlin J.A. Branch-and-bound methods for integer and non-convex programming. In: Abadie J. (ed.) Integer and Nonlinear Programming, North Holland, Amsterdam, 1970.

24. Tomlin J.A. An improved branch-and-bound method for integerprogramming. Operations Research, 1971, 19, N4, 1070-1075.29«Garfinkel R*» Hemhauser G.L. Integer programming. N.Y., 1972.

25. Benders J.F. Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 1962, 4, N3, 238-252.

26. Hrouda J. Modifikovany Bendersuv algorithmus. Ekonomicko-mate-maticky obzor, 1975, 11, N4, 423-443.

27. Бахтин A.E., Колоколов А.А. Декомпозиционный метод решения целочисленных производственно-транспортных задач. В сб. "Вопросы анализа сложных систем", Новосибирск, 1974, 15 36.

28. Бахтин А.Е., Горстко А.Б. О решении нелинейных экстремальных задач с линейными ограничениями специального вида. В сб."Математическое программирование", М., изд-во "Наука", 1966, 40-45.

29. Иоффе B.M. и др. Система моделей и методы оптимизации производства пластмасс. Экономика и математические методы , 1970, 6, И, 30 42.

30. Тьюарсон Р. Разреженные матрицы. М., изд-во "Мир", 1977.

31. О.Верина 31.Ф. О декомпозиции задач линейного программирования квазиблочной структуры. Известия АН БССР. Серия физ.-мат. наук, 1975, №6, 18 21.

32. Журавлев 10. И. Об одном классе алгоритмов над конечными множествами. ДАН СССР, 1963, 151, №5, 1025 1028.

33. Журавлев Ю.И. Оценка сложности локальных алгоритмов для некоторых экстремальных задач на конечных множествах. ДАН СССР , 1964, 153, №5, IOI8 IC2I.43.1уравлев Ю.И. Локальные алгоритмы вычисления информации. I. Кибернетика, 1965, I, №1, 12 19.

34. Журавлев Ю.И. Локальные алгоритмы вычисления информации. П. Кибернетика, 1966, 2, №2, I II.

35. Журавлев Ю.И., Финкельштейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования. В сб. "Проблемы кибернетики", М., изд-во "Наука", 1965, вьтп.14, 289 295.

36. Финкельштейн Ю.Ю. О решении задач дискретного программирования специального вида. Экономика и математические методы, 1965, I, №2, 262 270.

37. Финкельштейн Ю.Ю. Об одном классе задач дискретного программирования. Экономика и математические методы,1968,4,!Е4,652-655.

38. Фесенко В.И. О локальном алгоритме решения задач линейного программирования. В сб. "Алгоритмы и программы по вероятностной статистике и экономике", Краснодар, 1974, 139 142.

39. Guba W. Ein maximaler lokaler Algorithmus fur Aufgaben der ganzzahligen linearen Optimierung. Elektronische Informationsverarbeitung; und Kybernetik, 1975, 11, N10-12, 394-399«

40. Гришухин В.П. Оценка сложности алгоритма Балаша. В сб."Математические методы решения экономических задач", М., изд-во "Наука", 1972, Ю9 93 105.

41. Гришухин В.П. Эффективность метола ветвей и границ в задачах с булевыми переменными. В сб. "Исследования по дискретной оптимизации", М., изд-во "Наука", 1976, 203 230.

42. Гришухин В.П. Алгоритмы ветвей и границ в задачах с булевыми переменными, оценка их эффективности. Экономика и математические методы, 1976, 12, М, 757 766.

43. Щербина О.А. Математическая модель оптимального предварительного резервирования гостиничных номеров. "Сборник работ по математической кибернетике", М., ВЦ АН СССР,1976,вып.1,90 101.

44. Щербина О.А. О задаче оптимизации предварительного резервирования гостиничных номеров. В сб. "Исследование операций и АСУ*/ Киев, 1976, вып.7, 105 112.

45. Лихтенштейн В.Е. Модели дискретного программирования. М., изд-во "Наука", 1971.

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

47. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. П. Кибернетика, 1965, I, №2, 85 88.

48. Nauss R. Parametric integer programming. Ph.D. Dissertation. Graduate School of Management. University of California, Los Angeles, December, 1974.

49. Noltemeier H. Sensitivitatsanalyse bei diskreten linearen Optimierungsproblemen. Springer, Berlin, 1970.

50. Piper C.J., Zoltners A.A. Some easy postoptimality analysis for zero-one programming. Management Science, 1976, 22, N7, 759-765.

51. Piper C.J,, Zoltners A. A. Implicit enumeration based algorithms for postoptimizing zero-one programs. Naval Research Logistics Quarterly , 1976, 22, I\T4, 791-809.

52. Roodman G.M. Postoptimality analysis in zero-one programming by implicit enumeration. Naval Research Logistics Quarterly, 1972, 19, N3, 435-447.

53. Roodman G.M. Postoptimality analysis in integer 1rogramming: The mixed integer case. Naval Research Logistics 'Quarterly. 1974, 21, N4, 595-607.

54. Travnicek J. An approach to the solution of the parametric zero-one integer programming problem with the parameter in one right-hand side. Ekonomicko-matematicky obzor, 1972, 8, N1, 85-98.

55. Parametric zero-one programming with the parame tilled Objective function.Ekonomicko-mat;.obzor,1972,8,N4,417-425.

56. Финкельштейн Ю.Ю.¡Методы решения некоторых дискретных задач математического программирования. Кандидатская диссертация.1. М., ЦЭМИ АН СССР, 1966.

57. Щербина О.А. Модели оптимальной организации и развития системы рекреационных маршрутов. В сб."Применение математических методов в экономических исследованиях и планировании",Киев,1976,33-4

58. Щербина О.А., Сошина Л.М. Модель рекреационной системы с учетом сезонности. В сб."Применение математических методов в экономических исследованиях и планировании", Киев, 1977, 53 59.

59. Brualdi R.A., Foregger Т.Н. Packing boxes with harmonic oriciis. Journal on Combinatorial Theory, 1974, B17, N2, 81-114.75»ffulkerson D.R., Gross Q.A. Incidence^matrices and interval grap' Pacific Journal of Mathematics, 19&5, 15, N5, 835-855«

60. Kendall D.G. Incidence matrices, interval graphs and seriation in archaeology. Pacific Journal of Mathematics, 1988, 28, N3, 565-570.

61. Kendall D.G. Seriation from abundance matrices. Mathematics in the Archaeological ahd Historical Sciences. Edinburgh University Press, 1971, 215-252.

62. Wilkinson E.M. Archaeological seriation and the travelling sale man problem. Mathematics in the Archaeological and Historical Sciences. Edinburgh University Press, 1971, 276-287.

63. Gordon M.t Wilkinson E.M. Determinants of Petrie matrices. Pacific Journal of Mathematics, 1974, 51, N2, 451-453.

64. Glover P., Woolsey R.E.D. Aggregating diophantine equations. Zeitschrift fur Operations Research, 1972, A16, N1, 1-10.81 .Salkin H.M., de Kluyver O.A. The knapsack problem: a survey. Naval Research Logistics Quarterly, 1975, 22, N1, 127-144-.

65. Белдман P. Динамическое программирование. M., ИЛ, 1962.

66. Щербина O.A. Об оценках эффективности локального алгоритма для решения квазиблочных задач дискретного программирования. ДАН СССР (в печати).

67. Щербина O.A. О квазиблочных экономико-математических моделях. Веб. "Экономико-математическое моделирование развития отраслей и транспорта", Киев, изд. ИК АН УССР, 1978, 32-42.

68. Зыков A.A. Гиперграфы. УМН, 1974, 29, №6, 89-154.

69. Эрдеш П., Клейтмен Д.Дж. Экстремальные задачи о подмножествах конечного множества. В кн.: П.Эрдеш, Дж.Спенсер "Вероятностные методы в комбинаторике". М., изд. "Мир", 1976.

70. Щербина O.A. Оптимальное разбиение на блоки одной квазиблочной задачи булевого программирования. "Сборник работ по математической кибернетике", М., ВЦ АН СССР, 1976, вып.1, 81-89.