Дипломы, курсовые, рефераты, контрольные...
Срочная помощь в учёбе

Разработка и исследование некоторых методов решения задач целочисленного линейного программирования общего и специального видов

Диссертация: Разработка и исследование некоторых методов решения задач целочисленного линейного программирования общего и специального видов
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • 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, № 166 278 дал.
  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.
Заполнить форму текущей работой

Заказал и сдал!