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

В в е д е н и е .'.

Глава I. ДЕКОМПОЗИЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

СПЕЦИАЛЬНОЙ СТРУКТУРЫ

§ I.I. Задачи блочного программирования со связующими переменными и ограничениями

§ 1.2. Сведение дробно-линейных блочных задач к решению линейных задач блочного программирования

§ 1.3. Параметрический метод решения задач дробно-линейного программирования

§ 1.4. Принцип разложения по ограничениям с применением метода обобщенного градиентного спуска.

§ 1.5. Принцип разложения по переменным с применением метода обобщенного градиентного спуска.

§ 1.6. Метод решения обобщенной задачи дробнолинейного программирования

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

ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ТРАНСПОРТНОГО ТИПА.

§ 2.1. Алгоритмы решения дробно-линейных транспортных задач.

§ 2.2. Производственно-транспортные задачи с дробно-линейным функционалом

§2.3. Алгоритмы решения распределительной задачи дробно-линейного программирования

Глава 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ ПЕРЕВОЗОЧНОГО ПРОЦЕССА

НА АВТОМОБИЛЬНОМ ТРАНСПОРТЕ.

§ 3.1. Задачи оптимизации перевозочного процесса на автомобильном транспорте

§ 3.2. Определение годового клиентурного плана грузовых перевозок автотранспортных предприятий

§ 3.3. Определение оптимальной структуры подвижного состава и его рациональное использование

§ 3.4. Задача маршрутизации автомобильных грузовых перевозок.

Значительное расширение областей применения вычислительной техники, более детальное описание моделируемых объектов и более высококачественный уровень использования экономико-математических моделей приводит к необходимости решения задач большой размерности. Поэтому проблема исследования и разработки эффективных методов решения подобных задач является достаточно актуальной и перспективной.

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

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

В настоящее время получен ряд теоретических и практических результатов по разработке и использованию декомпозиционных методов решения задач математического программирования большой размерности [13, 14, 16 , 22, 26 , 29 , 44, 46 , 56 , 74, 81, 93 , 99, 109, НО].

Одним из наиболее распространенных методов является принцип декомпозиции Данцига-Вулфа [96], на основе которого разработаны вычислительные алгоритмы решения блочных задач линейного [26, 90, 92, 120], дробно-линейного [91, 100, 101, 104, 106] и нелинейного [26, 46, III, 112, 114] программирования. Этот метод позволяет свести исходную задачу к решению вспомогательной (координирующей) задачи некоторым общим алгоритмом, на каждом шаге которого решаются подзадачи для каждого блока в отдельности.

Другим декомпозиционным методом, который эффективно используется в последнее время для решения больших задач специальной структуры, является принцип разложения по переменным и ограничениям с применением метода обобщенного градиентного спуска (0ГС) [83]. Такой метод, построенный на основе функции Лагранжа и теории двойственности, позволяет свести решение исходной задачи к решению задачи безусловной оптимизации выпуклой или вогнутой функции (как правило недифференцируемой). Для решения задачи безусловной оптимизации используется метод 0ГС, на каждом шаге которого эффективно решается задача определения значений обобщенного градиента. На основе принципа разложения по переменным и ограничениям разработаны алгоритмы решения задач линейного и выпуклого программирования блочной структуры [I, 2, 17, 81-83, 85, 87, 88] и ряда практических задач [II, 78, 84, 89].,

В диссертационной работе эти методы обобщаются на задачи дробно-линейного программирования (ДЛП) большой размерности.

Необходимость разработки декомпозиционных методов решения задач ДЛП объясняется наличием математических моделей с дробно-линейным функционалом [6, 7, 9, 34, 41, 42, 75, 77, 80], часто встречающихся в практике планирования и управления народным хозяйством. В таких моделях в качестве критерия оптимальности используются некоторые удельные технико-экономические показатели,такие, как себестоимость конечной продукции, фондоемкость, фондоотдача, рентабельность и др. Использование таких показателей приводит к необходимости решения общей задачи ДЛП, в которой требуется минимизировать или максимизировать отношение двух линейных функционалов при линейных ограничениях.

Для решения общей задачи ДЛП разработаны различные алгоритмы [10, 19 , 22, 40 , 73 , 75 , 79 , 95 , 97 , 98, 100, 102, 107, 115, 116, 119, 121]. Эти алгоритмы могут быть разделены на две группы. К первой группе относятся алгоритмы, в которых симплекс-метод модифицируется для решения задач ДЛП [19, 79, 98, 100, 102, 107, Пб]. Ко второй группе относятся алгоритмы, в которых задача ДЛП сводится к решению одной, двух или конечной последовательности линейных задач. В [10, 40, 95, 121] с помощью введения дополнительной переменной и проведения соответствующего преобразования системы ограничений задача ДЛП сводится к решению одной или двух (в зависимости от знака знаменателя) задач линейного программирования. В [22, 97] задача ДЛП сводится к анализу и решению некоторой задачи параметрического линейного программирования на множестве исходных ограничений .

Для решения задач ДЛП специальной структуры разработаны соответствующие алгоритмы, в которых учитывается структура системы ограничений. Для решения задач блочной структуры в [91, 100, 105] приводятся алгоритмы, основанные на принципе декомпозиции Данцига-Вулфа, а в [15 ] - на методе параметрической декомпозиции. В [24, 75, 79, 101] рассматриваются задачи ДЛП транспортного типа, для решения которых приводятся алгоритмы метода потенциалов и принципа декомпозиции Данцига-Вулфа. Для решения задач размещения с дробными функционалами в [33, 45, 76] приводятся приближенные алгоритмы метода последовательных расчетов. В [7, 42, 49] рассматриваются дробно-линейные целочисленные задачи специальной структуры, для решения которых приводятся алгоритмы метода последовательного анализа вариантов.

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

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

В работе рассматриваются:

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

- обобщенные задачи ДЛП;

- дробно-линейные транспортные задачи;

- задачи размещения с дробно-линейным функционалом.

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

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

10. Результаты работы внедрены в Министерстве автомобильного транспорта Молдавской ССР (годовой экономический эффект свыше 500 тыс. руб.).

1. Аимбетов Н.К. Вычислительный опыт использования одного алгоритма решения квазиблочных задач линейного программирования.-В кн.: Методы решения задач нелинейного и дискретного программирования. Киев: ИК АН УССР, 1984, с. 67-72.

2. Аникевич A.A., Грибов А.Б., Сурин С.С. Сменно-суточное планирование работы грузовых автомобилей на ЭВМ. М.: Транспорт, 1976. - 152 с.

3. Аникевич A.A., Грибов А.Б., Романовский И.В. Об одной задаче маршрутизации перевозок. Кибернетика, 1966, № I,с. 65-71.

4. Бадинер С.М., Бобарыкин В.А., Дагович В.М. Автоматизированные системы управления на автомобильном транспорте. М.: Транспорт, 1977. - 160 с.

5. Бакаев A.A., Ахметов Л.А., Данилина И.А., Умаров У.Т. Вопросы математического обеспечения оптимизационных транспортных процессов. Ташкент: ФАН, 1976. - 140 с.

6. Беленкий A.C. Об одной минимаксной задаче с линейными ограничениями. Автоматика и телемеханика, 1980, № 4,c. I5I-I58.

7. Беленкий А.С. Минимаксные задачи планирования с линейными ограничениями и методы их решения. Автоматика и телемеханика, 1981, № 10, с. 157-170.

8. Белых В.М., Гавурин М.К. Алгоритм минимизации дробно-линейной функции. Вестн. Ленингр. ун-та, 1980, № 19, с. 10-15.

9. Беляева Л.В., Журбенко Н.Г., Шор Н.Э. 0 методе решения одного класса динамических распределительных задач. Экономика и матем. методы, 1978, 14, № I, с. 137-146.

10. Бобарыкин В.А. Оптимальное сменно-суточное планирование грузовых перевозок. М.: Транспорт, 1968. - 94 с.

11. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования.- М.: Наука, 1977.- 367 с.

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

13. Верина Л.Ф. Алгоритм параметрической декомпозиции для одного класса задач дробного программирования. Минск, 1975, II е., (Рукопись деп. в ВИНИТИ № 2939-75 Деп.).

14. Верина Л.Ф., Танаев B.C. Декомпозиционные подходы к решению задач математического программирования./ Обзор. Экономика и матем. методы, 1975, II, № 6, с. II60-II72.

15. Вычислительные методы выбора оптимальных проектных решений./ B.C. Михалевич, Н.З. Шор, Л.А. Галустова и др. -Киев: Наукова думка, 1977. 178 с.

16. Гаврилов А.А., Гельц Г.А. и др. Экономико-математическое моделирование региональных транспортных систем. /Препринт/. М.: ЦЭМИ АН СССР, 1981. - 36 с.

17. Гавурин М.К. Дробно-линейное программирование на неограниченном множестве. Вестн. Ленингр. ун-та, 1982, № 19, с. 12-16.

18. Голыитейн Е.Г. Двойственные задачи выпуклого и дробно-выпуклого программирования. В сб.: Исследования по математическому программированию. - М.: Наука, 1968, с. 10-108.

19. Голыитейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 197I. - 351 с.

20. Голыитейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов. Радио, 1966. - 524 с.

21. Голыитейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 153 с.

22. Громовой Э.П., Тарасова И.П. Распределительная задача дробно-линейного программирования. В кн.: Труды 4-й Зимней школы по матем. программированию и смежные вопросы, Дрогобыч, 197I. - M., 1972, вып. 4, с. 42-49.

23. Давыдова И.М. Задачи размещения. В кн. : Исследование операций и статистическое моделирование. - Л.: Изд-во Ленингр. ун-та, 1977, вып. 4, с. 50-80.

24. Данциг Дж. Линейное программирование, его обобщения и применения. М.: Прогресс, 1966. - 600 с.

25. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982, -432 с.

26. Емеличев В.А., Комлик В.И. Методы построения последовательности планов для решения задач дискретной оптимизации. -М.: Наука, 1981. 208 с.

27. Ермольев Ю.М., Ермольева Л.Г. Метод параметрической декомпозиции. Кибернетика, 1972, № 2, с. 66-69.

28. Задачи маршрутизации (вычислительный аспект). Препринт. -М.: Институт проблем управления, 1981. 50 с.-11931. Житков В.А. Планирование автомобильных перевозок грузов мелкими партиями. М.: Транспорт, 1976. - 110 с.

29. Житков В.А., Ким К.В. Методы оперативного планирования грузовых автомобильных перевозок. М.: Транспорт, 1982. -184 с.

30. Жусупбаев А. 0 двухэтапных задачах размещения производства с дробно-выпуклым функционалом и искомыми объемами производства, потребления и переработки. В кн.: Матем. методы решения экономико-математических задач. - Фрунзе: Илим,1974, с. 20-27.

31. Илюкович A.A., Колыбельникова Л.С., Кривицкая Л.Е. Использование дробно-линейной функции при оптимизации производственной программы предприятия. Сб. науч. тр. Центр, н.и.и проект.-технол. ин-т организ. и техн. упр. М. 1976, № 4(26), с. II3-II9.

32. Ирматов М. Применение математических методов и ЭВМ в работе автотранспорта Узбекистана. Ташкент: Фан, 1971.- 112 с.

33. Карманов В.Г. Математическое программирование. М.: Наука,1975. 272 с.

34. Каталог ЕС ЭВМ, т. 2. Программное обеспечение. М.: Строй-издат, 1978.

35. Кафтанюк Ю.А. Отраслевая автоматизированная система управления автомобильном транспортом. М.: Транспорт, 1977. -ПО с.

36. Ким К.В. Задача отыскания оптимальных маршрутов. Экономика и матем. методы, 1965, I, №5, с. 772-775.

37. Клевачев В.И. О решении задач дробно-линейного программирования. Кибернетика, 1968, № 6, с. 27-31.

38. Крупицкий А.Е. Минимизация суммы двух дробно-линейных функций на выпуклом многогранном множестве. Вестник ЛГУ, 1983, № 13, с. 15-21.

39. Левин Г.М., Танаев B.C. Декомпозиционные метода оптимизации проектных решений. Минск: Наука и техника, 1978. - 240 с.

40. Ланге Э.Г., Жусупбаев А. О методах решения задачи размещения. Изв. АН СССР. Техническая кибернетика, № 6, 1982, с. 79-86.

41. Лэсдон Л.С. Оптимизация больших систем. М.: Наука, 1975. -432 с.

42. Михалевич B.C., Сергиенко И.В. и др. Пакет прикладных программ для решения задач производственно-транспортного планирования большой размерности (ПЛАНЕР). Кибернетика, 1983, № 3, с. 57-70.

43. Нестеров Ю.Е. Методы минимизации негладких функций. Экономика и матем. методы, 1984, 20, № 3, с. 519-531.

44. Никитин А.И., Нуриев У.Г. Эвристический алгоритм решения одной задачи дробно-линейного булева программирования. -Изв. АН Азерб. ССР, сер. физ.-техн. и матем. наук, 1982, № 5, с. II2-II7.

45. Олейник-Овод Ю.А. Разработка математических методов планирования перевозок и внедрение их в практику работы автомобильного транспорта (на примере г. Москвы). Доклад о содержании совокупности опубликованных и выполненных работ.М., 1965. 24 с.

46. Оптимальное планирование на автомобильном транспорте (из опыта Главмосавтотранса)./ Под общей ред. А.З. Синицкого.-121М.: Транспорт, 1969. 76 с.

47. Пакет анализа оптимизационных экономических моделей ППП ПАОЭМ ЕС. Задачи транспортного типа. Калинин: НПО "Центр-программсистем", 1982. - 244 с.

48. Пакет анализа оптимизационных экономических моделей ППП ПАОЭМ ЕС. Модули линейного и квадратического программирования. Калинин: НПО "Центрпрограммсистем", 1982. - 124 с.

49. Панов С.А. Совершенствование планирования перевозок на автомобильном транспорте. М.: Наука, 1973. - 151 с.

50. Панов С.А. Модели маршрутизации на автомобильном транспорте. М.: Транспорт, 1974. - 152 с.

51. ПервозЕанский А.А., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. М.: Наука, 1979. -342 с.

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

53. Соломон Д.И. Об одной процедуре преобразования задач математического программирования, имеющих связующие ограничения и переменные. В кн.: Мат. исслед. - Кишинев: Штиинца, 1979, вып. 52, с. 199-205.

54. Соломон Д.И., Шаров В.Н., Зоти А.Г. Моделирование на ЭВМ процесса годового планирования автомобильных грузовых перевозок. В кн.: Мат. исслед. - Кишинев: Штиинца, 1982, вып. 68, с. 125-134.

55. Соломон Д.И. Применение метода обобщенного градиентного спуска при решении задач дробно-линейного программирования. Изв. АН МССР, сер. физ.-техн. и мат. наук, 1983, № I, с. 7-13.

56. Соломон Д.й. Об одной задаче целочисленного дробно-линейного программирования. В кн.: Мат. исслед. - Кишинев: Штиинца, 1983, вып. 72, с. I22-I3I.

57. Соломон Д.И. Обобщение линейной и дробно-линейной транспортной задачи. Изв. АН МССР, сер. физ.-техн. и мат. наук, 1984, № I, с. 13-18.

58. Соломон Д.И. Обобщенный градиентный метод в дробном прог-рамировании. В кн.: Тезисы докладов Второй Всесоюзной школе-семинаре по оптимизации и ее приложениям к экономике. - Ашхабад, 1984, с. 216-217.

59. Тетерев А.Г. Об одном обобщении задач линейного и дробнолинейного программирования. Экономика и матем. методы, 1969, 5, № 3, с. 440-447.

60. Трубин В.А. 0 некоторых задачах размещения. В кн.: Применение математических методов в экономических исследованиях и планировании. - Киев, 1968, вып. I, с. 3-20.

61. Трубин В.А. О решении задачи размещения на сети в форме дерева. В кн.: Математические метода исследования и оптимизации систем. - Киев, 1971, с. 3-10.

62. Хачатуров В.Р. Алгоритм и программа решения задачи размещения предприятий с неограниченными объемами производства. Экономика и матем. методы, 1967, 3, № 2, с. 240-252.

63. Хачатуров В.Р. Определение оптимального и всех близких к нему вариантов размещения с ограниченными сверху объемами производства. Изв. АН Каз. ССР, сер. физ.-мат. наук, 1967, № 3, с. 38-43.

64. Хачиан Л.Г. Полиномиальные алгоритмы в линейном программировании. Ж. вычисл. матем. и матем. физики, т. 20,I, 1980, с. 51-68.

65. Цурков В.И. Декомпозиция в задачах большой размерности. -М.: Наука, 1981. 530 с.

66. Чернов Ю.П., Ланге Э.Г. Задачи нелинейного программирования с удельными экономическими показателями (методы и приложения). Фрунзе: Илим, 1978. - 296 с.

67. Чернов Ю.П., Ланге Э.Г., Жусупбаев А. Применение метода последовательных расчетов для решения задач размещения производства с дробно-выпуклым (разрывным) функционалом. -Изв. АН Киргизкой ССР, 1979, № 2, с. 27-34.

68. Шварцман А.П. Об одном алгоритме дробно-линейного программирования. Экономика и матем. методы, 1965, I, № 4,с. 558-566.

69. Шварцман А.П., Громовой Э.П. Математические методы управления и планирования на морском транспорте. М.: Транспорт, 1970. - 384 с.

70. Шор Н.З. Применение обобщенного градиентного спуска в блочном программировании. Кибернетика, 1967, № 3, с. 53-55.

71. Шор Н.З. Обобщенные градиентные методы минимизации негладких функций и их применение к задачам математического программирования. (Обзор). Экономика и матем. методы, 1976, 13, вып. 2, с. 337-356.

72. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. - 200 с.

73. Шор Н.З., Горбач Г.И. Решение задач распределительного типа методом обобщенного градиентного спуска. В кн.: Тр. семинара Науч. Совета АН УССР по кибернетике "Теория оп-тим. решений". - Киев, 1968, № I, с. 59-71.

74. Шор Н.З., Иванова Л.И. Об одном итеративном методе решения задач линейного программирования и матричных игр. В кн.: Тр. семинара Науч. совета АН УССР по кибернетике "Теория оптим. решений". - Киев, 1969, № 3, с. 22-30.

75. Шор Н.З., Журбенко Н.Г. Методы минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов. Кибернетика, 1971,3, с. 51-59.

76. Шор Н.З., Росина Н.И. Схема разложения задач линейного и выпуклого программирования и ее применение для решения задач планирования перевозок. В кн.: Докл. I Всесоюз. конф. по оптимизации и моделированию транспорт, сетей. -Киев, 1967, с. 225-237.

77. Шор Н.З., Щепакин М.Б. Алгоритм решения двухэтапной задачи стохастического программирования. Кибернетика, 1968,3, с. 56-58.

78. Anand P. Dual and parametric methods in decomposition for linear fractional program. Studia Scintiarum Mathemati-carum Hungarica, 1971» 6, p. 267-275»

79. Bell E.J. Primal-dual decomposition programming./ Ph. D. (Thesis, Operations Research Center. University of California at Berkeley, 1965, Rept. ORC 65-23.

80. Benders J.P. Partitioning procedures for solving mixed variables programming problems. Numerische mathematik, 1962, 4, p. 238-252.

81. Lata M., Mittal B.S. A decomposition, method for interval linear fractional programming. — Z» Angew. Math.» Mech. , 1976, 56, 4, p. 153-159.

82. Martos B. Hyperbolic programming. Naval res. log. quart., 1964, 14, 2-3, p. 135-156.

83. Rosen J.B. Primal partition programming for blok diagonal matrices. Numerische Mathematik, 1964, 6, 3,p. 250-260.

84. Sanders J. A nonlinear decomposition principle. Oper. Res., 1965, 13, 2.

85. Silverman G. Primal decomposition of mathematical programs by resource allocation. Oper. res., 1972, 20, 1.113* Snigh C. Optimality conditions in fractional programming. J. Optim. Theory andAppl., 1981, 33, 2, p. 287-294.

86. S war up Z. Linear fractionals functionals programming.Oper. Res., 1965, 13(6), p. 1029-1036.117* Swarup K. Duality for transportation problem in fractional programming. Cah. cent. etud. rech. oper., 1968, 10, 1, p. 46-54.

87. Wdowiak J. Dyskretne zagadnienie programownia wymierno-liniowego, C-1. Przeglad Statystyczny, 1977, 24, 4, p. 483-497•119* Wagner H.M., Yuan J.S.C. Algogithmic equivalence in linear fractional programming. Management Science, 1968, 14, 5, p. 301-306.

88. Williams A.C. A treatment of transportation problems by decomposition. J. Soc. Ind. Appl. Math., 1962, 10, 1, p. 35-48.

89. Zionts S. Programming with linear fractional functionals. -Naval Res. Logist. Quart., 1968, 15, 3, p. 449-451.