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

ВВЕДЕНИЕ.

1. Обзор методов решения задач дискретной оптимизации.

2. Метод последовательного исследования плоскостей уровня для задачи ЦЛП общего вида.

2.1. Постановка задачи и описание метода.

2.2. Результаты вычислительных экспериментов.

2.3. Применение метода для решения задачи замены оборудования.

3. Приближенное решение задачи ДЛИ с матрицей ограничений специального вида.

3.1. Постановка задачи и анализ применимости метода вектора спада для ее решения.

3.2. Метод замен.

3.3. Выводы и результаты вычислительного эксперимента.

4. Задачи перспективного планирования в угольной промышленности.

4.1. Задача перспективного развития действующих шахт.

4.2. Задача оптимального проектирования шахты.

В "Основных направлениях экономического и социального развития СССР на I98I-I985 гг. и период до 1990 г.", принятых на ХХУ1 съезде КПСС, указано, что для ускорения перевода экономики на путь интенсивного развития, повышения эффективности общественного производства необходимо, в частности, направить усилия на "совершенствование вычислительной техники, ее элементной базы и математического обеспечения." /33/.

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

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

Целью диссертационной работы является:

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

- разработать и исследовать новые методы решения задач полностью целочисленного линейного программирования (ЦЛП) общего и некоторых специальных видов;

- разработать программное обеспечение для решения задач ЦЛП "Библиотеки программ оптимизации и исследования операций для

СМ ЭВМ";

- используя созданное программное обеспечение, решить задачу о замене оборудования машиностроительного завода;

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

Предметом исследований стали следующие классы задач:

- задача ЦЛП общего вида с двусторонними ограничениями на неизвестные;

- задача ЦЛП, матрица ограничений которой наряду с ограничениями-неравенствами содержит ограничения-равенства специального вида;

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

Методологическую основу работы составляют методы построения последовательности решений и вектора спада.

Диссертация состоит из введения, 4 глав, списка литературы, заключения и приложения.

ЗАКЛЮЧЕНИЕ

1. Разработан и исследован точный метод решения задачи ЦЛП с матрицей ограничений общего вида и двусторонними ограничениями на неизвестные.

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

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

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

5. Для предложенных в работе алгоритмов разработано стандартное математическое обеспечение, реализованное на ЕС ЭВМ и СМ ЭВМ. Разработанное автором программное обеспечение вошло в качестве составной части в "Библиотеку программ оптимизации и ИСО для СМ ЭВМ", что позволит расширить круг пользователей СМ ЭВМ и круг решаемых задач.

6. С помощью созданного программного обеспечения решена практическая задача - задача замены оборудования в механосборочных цехах завода "Славтяжмаш" с целью омоложения парка металлорежущих станков (МРС), что позволило в совокупности с другими расчетами обосновать основные направления развития парка МРС завода на I985-1990 г.

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

1. Артеменко В.И. О двух подходах к приближенному решению задач частично-целочисленного линейного программирования.- В кн.: Вычислительные аспекты в пакетах прикладных программ. Киев: ИК АН УССР, 1980, с. 16-25.

2. Артеменко В.И., Сергиенко Й.В. Об одном методе решения задач линейного программирования с булевыми переменными.- Докл. АН УССР. Сер. А, 1980, № 4, с. 72-75.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ.- М.: Мир, 1979, 535 с.

4. Бабаев Дж.А., Мамедов К.Ш. Агрегация одного класса систем целочисленных уравнений. Ж ВМ и Ш, 1978, № 3, с. 614-619.

5. Большакова Н.Ю., Ситникова О.Д. Совершенствование структуры парка металлорежущих станков на основе принципа пропорций. В кн.: Автоматизация технологической подготовки и совершенствование организации производства, 1984, Краматорск, НИИПмаш,с.66"?Я

6. Велиев Г.П., Мамедов К.Ш. Метод решения задачи о ранце.-ЖВМ, 1981, 21, № 3, с. 605-611.

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

8. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачии эффективные приближенные алгоритмы (обзор). Изв.АН СССР. Техн. киберн., 1979, № 6.

9. Гене Г.В., Левнер Е.В. Эффективные приближенные алгоритмы для комбинаторных задач. Предпринт.М.: ЦЭМИ АН СССР, 1981.

10. Гершович В.И., Шор Н.З. Метод эллипсоидов, его обобщения и приложения. Кибернетика, 1982, № 5, с. 61-69.

11. Гери М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи: Пер. с англ.- М.: Мир, 1982. 416 с.

12. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения. I. Кибернетика, 1971, № б, с. 97-110.

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

14. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981 - с. 340.

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

16. Емеличев В.А., Краверский И.М. Машинный эксперимент по решению задач целочисленного линейного программирования методом построения последовательности планов. SBM и 1973, 13, № 2, с. 467-471.

17. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации.- Изв. АН СССР. Техн.кибернет., 1982, № 6, с. 25-45.

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

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

20. Карп P.M. Сводимость комбинаторных проблем.- В кн. Кибернетический сборник, М.: Мир, 1975, вып. 12, с. 16-38.

21. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Минск.: БГУ, 1977, с. 191.

22. Ковалёв М.М., Котов В.И. Субоптимальные алгоритмы в целочисленном программировании,- Докл. АН БССР, 1982, 26, № II, с. 969-972.

23. Ковалев М.М., Пирьянович В.А.Локально- стохастические алгоритмы дискретной оптимизации (эксперименты, опыт применения). Кибернетика, 1982, № I, с. I08-II2.

24. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко И.В. Вопросы устойчивости, параметрический и постоптимальный анализ задач дискретной оптимизации. Кибернетика, 1983, № 4, с. 71-80.

25. Корбут А.А., Сигал И.Х., Финкелыптейн Ю.Ю. Метод ветвей и границ (обзор теории, алгоритмов, программ и приложений).сиЫь. Operations -fonkch-. t, O/rtinuMtfaon,1977, 8, № 2, с. 253 280.

26. Корбут А.А., Финкелыптейн Ю.Ю. Приближенные методы дискретного программирования. Изв. АН СССР. Техн.киберн., 1983,1. I, с. 165 176.

27. Кузгорин Н.Н. 0 сложности приближенных алгоритмов решения задачи целочисленного программирования. ЖВМ и Ш, 1984, Т, 24, № I, с. 157 - 160.

28. Лебедева Т.Т., Михалевич B.C., Рощин В.А., Сергиенко И.В., Стукало А.С., Трубин В.А., Шор Н.З. Структура, состав и назначение пакета программ ДИСПР0 для решения задач дискретной оптимизации. Изв. АН СССР. Техн.киб., 1983, № I, с. 193- 196.

29. Лебедев С.С., Шейнман O.K. Двойственный подход в целочисленном программировании. Изв.АН СССР, Техн.кибернет., 1983,1. I, с. 181 187.

30. Леонтьев В.К. Дискретные экстремальные задачи.- В кн.: Итоги науки и техн. ВИНИТИ. Сер.Теория вероятностей. Мат. стат. Теор.киберенет., 1979, 16, с. 39-101.

31. Мамедов К.Ш. Агрегирование системы линейных диофантовых уравнений.- Изв. АН Азерб.ССР, № 3, 1977, с. 52 57.

32. Материалы ХХУ1 съезда КПСС.- М.: Политиздат, 1981. -262 с.

33. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М., Наука, 1983, с. 207.

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

35. Михалевич В.С.Последовательные алгоритмы оптимизации и их применение.- Кибернетика, 1965, № 2, с. 85 89.

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

37. Михалевич B.C., Шор Н.З. Метод последовательного анализа вариантов при решении вариационных задач управления, планирования и проектирования. В кн.: Докл. на 1У Всесоюз.мат.съезде. М., 1961. - 91 с.

38. Перепелица В.А. Асимптотический подход к решению некоторых экстремальных задач на графах. В сб.: Проблемы кибернетики.вып. 26. М.: Наука, 1973.

39. Пирьянович В.А. Генераторы тестовых задач целочисленного линейного программирования. Деп. в ВИНИТИ, 1978, № 166278 дал.

40. Пирьянович В.А. Машинные эксперименты по решению задач целочисленного линейного программирования с помощью локально-стохастических алгоритмов.- ЖВМ и Ш>, 1979, 19, № I, с. 79 87.

41. Поздняков Ю.М. Декомпозиционная схема решения задачи целочисленного линейного программирования. ЖВМ и Ш, 1982, 22, № I, с. 57-67.

42. Проектирование и комплексная оптимизация параметров шахт. М.: Недра, 1972, 3680. Авт: А.С.Бурчаков, Б.М.Воробьев, А.С.Малкин и др.

43. Проектирование угольных шахт.М., Недра, 1976, 400с. Авт.: И.К.Станченко, Е.В.Петренко, Ю.И.Свирекий и др.

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

45. Ромашкин И.П.Перспективное планирование в угольной промышленности. М.: Наука, 1982,-170 с.

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

47. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук, думка, 1981. - 258 с.

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

49. Сергиенко И.В. 0 некоторых направлениях в развитии методов дискретной оптимизации и их программного обеспечения. Кибернетика, 1982, № б, с. 45-53.

50. Ситникова О.Д. Алгоритмы решения задачи перспективного развития действующих шахт. ИЭП АН УССР, Донецк, препринт 84-2-МО, 1984, - 9 с.

51. Ситникова О.Д. Решение диофантова уравнения при двусторонних ограничениях на неизвестные для случая повторяющихся коэффициентов. Деп. в УкрНИИНТИ, 1983, № 358Ук - Д83, 5 с.

52. Ситникова О.Д. Решение задачи линейного программирова -ния с двусторонними ограничениями на неизвестные.- Киев, ИК АН УССР, 1980, РШ № 5775, 10 с.

53. Ситникова О.Д. Поиск целочисленных решений систем линейных неравенств и уравнений частного вида. В кн. Математическое обеспечение пакетов прикладных программ и методы дискретной оптимизации. Киев: ИК АН УССР, 1984, с. 90-97.

54. Ситникова О.Д., Штерн Ю.М., Игнатьева Н.А., Костин В.И. Библиотека программ оптимизации для СМ ЭВМ.- В кн.: Тезисы Всесоюзного научно-технического семинара "Программное обеспечение мини- и микро-ЭВМ семейства СМ ЭВМ", М., ИНЭУМ, 1984.

55. Терзи Д.Г. 0 приближенном решении задачи целочисленного линейного программирования.- В кн. Мат.исслед., Кишинев, 1983,72, с. 132-135.

56. Уздемир А.П. Схема последовательной декомпозиции в задачах оптимизации. Автом. и телемех., 1980, № II, с. 94-105.

57. Финкельштейн Ю.Ю. 0 полиномиальном алгоритме £ оптимизации в многомерной задаче о ранце. - ЖВМ и Ш>, 1980,203.

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

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

60. Фрумкин М.А. 0 числе натуральных решений системы линейных диофантовых уравнений. Мат.заметки, 1980, 28, № 3, с.321-334.

61. Фрумкин М.А. Сложноетные вопросы теории чисел. Зап. науч. семин. ЛОМИ, 1982, Т. 118.

62. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании. Докл. АН СССР, 1979 , 244, № 5, с. 1093 - 1096.

63. Хачиян Л. Г. Полиномиальная разрешимость задач выпуклого диофантового программирования с фиксированным числом переменных. Изв. АН СССР. Тех.киб., 1983, I.

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

65. Шевченко В.Н. Задача о размене, задача Фробениуса и задача групповой минимизации. В кн.: Комбинаторно-алгебраические методы в прикладной математике, Горький, 1982, с. 166-179.

66. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979, - 272 с.

67. BALAS EGON, GUIGNARD . REPORT OF THE CESSION CN BRACH AND BCUND/IMPLJCIT ENUMERATION. DISCRETE OPTIMIZATION, VOL. 2. A STERDA E.A., 1979, P. 185 191.

68. COOPER L., COOPER M.W. ALL-INTEGER LINEAR PROGRAMMING A NEW APPROACH VIA DUN AMI С PROGRAMMING, - NEY* RES. LOG. QUART, 25, N 3, 1978, P. 51 - 63.

69. DANTZIG G.B. DISCRETE-YARIABLE EXTREMUM PROBLEMS. OPER. RES., 1957, 5, N 2, P. 266 - 277.

70. GLOVER FR.NEW RESULTS ON EQUIVALENT INTEGER PROGRAMMING FORMULATIONS, MATH. PROGR. 8, 1975, - P. 84-90.

71. GOMORy R.E. AN ALGORITHM FOR THE MIXED INTEGER PROBLEM. -RAND. GORP., P 1885, SANTA MONIGA, CALIFORNIA, I960, 22.

72. GOMORy R.E. AN ALL-INTEGER PROGRAMMING ALGORITHM. IBM RECEARCH CENTER, i960 JAN. RES. REP. RC-189*

73. GONDRAN MICHEL, SIMEONE BRUNO. REPORT OF THE SESSION ON CUTTING PLANES. DISCRETE OPTIMIZATION. VOL. 2. AMSTERDAM E.A., 1979, P. 193 194.

74. KAN NAN R., BACHEM A. POLUNOMIAL ALGORITHMES FOR COMPUTI NG THE SMITH AND HERMITE FORMS OF AN INTEGER MATRIX. SIA M.J. COMPUT. 1979, V 8, N 4, P. 499 - 507.

75. KANNAN R. POLYNOMIAL-TIME AGGREGATION OF INTEGER PROGRAMMING PROBLEMS. У. ASSOC. COMPUT. MACH, 1983, 30, N 1, P. 133 - 145.

76. KORTE BERNHARD, SCHRADER RAINER. ON THE EXISTENCE OF PAST APPROXIMATION SCHEMES. NONLINEAR PROGRAM. 4. PROC. 4TH SYMP., MADISON, WISC., JULY 14 - 16, 1980, NEW-YORK R.A, 1981, P. 415 - 437.

77. KRAHI RUDIGER. ZUR ANWENDUNG DER STELLVERTRERNEBENDING-GUNG DEI LINEAREN 0-1 OPTIMIERUNGSPROBLEMSEN. SEMINARLER. HUMBOLDT - UNiy. BERLIN. SEK. MATH, 1981, N 39, 125 - 136.

78. LAND A.H., DOIG A.G. AN AUTOMATIC METHOD OP SOLVING DISCRETE PROGRAMMING PROBLEMS. ECONOMETRICA, I960, 28, N 3, P. 497 - 520.

79. LENSTRA A.W. JR. INTEGER PROGRAMMING WITH A FIXED NUMBER OF VARIABLES. UNIV. OF AMSTERDAM, REPORT 81-03, 1981.

80. MAGAZINE M.J., OGUZ 0. A FULIY POLYNOMIAL APPROXIMATION ALGORITHM FOR THE 0 1 KNAPSACK PROBLEM. - EUR. J. OPER. RES., 1981, 8, N 3.

81. PETERSEN C.C. COMPUTATIONAL EXPERIENCE WITH VARIANTS OF THE BALASH ALGORITHM APPLIED TO THE SELECTION OF R AND D PROJECTS. MANAG. SCI. 1967, 13, N 9, P. 736 750.

82. SAHNI S., GONZALES T.P. COMPLETE APPROXIMATION PROBLEMS. = J* ASSOC. COMPUT. MACH.f 1976, 23.

83. SELMER E.S. ON THE LINEAR BIOPHANTINE PROBLEM OF FROBE-NIUS, У. REINE AND ANGEW. MATH., 1977, 293/294, 1 17.

84. SMORYNSKI L. SKOLEM'S SOLUTION TO A PROBLEM OF FROBENIUS, MATH. INTELL., 1981, 3, 3, P. 123 132.

85. TROUTH C.A., WOOLSEY R.E. INTEGER LINEAR PROGRAMMING: STUDY IN COMPUTATIONAL EFFICIENCY. MANAG SCI., 1969, 15, N 9, P. 481 - 493.

86. YOUNG R.D. A PRIMAL (ALL-INTEGER) INTEGER PROGRAMMING ALGORITHM. J. RES. NAT. STAND. B, 1965, 69, N 3, P. 213 - 250.