Метод сетевого программирования в задачах управления строительным производством тема диссертации и автореферата по ВАК РФ 05.13.10, кандидат технических наук Аснина, Наталия Георгиевна

• Аснина, Наталия Георгиевна
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Аснина, Наталия Георгиевна

ВВЕДЕНИЕ.

1. МЕТОДЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ.

1.1 Постановка задач дискретного программирования.

1.2 Методы решения задач дискретного программирования

Методы отсечения.

Комбинаторные методы. Метод ветвей и границ.

1.3 Методы математического программирования.

Метод двойственных оценок.

Адаптивный метод.

Алгоритм Удзавы.

1.4 Генетические алгоритмы.

1.5 Метод дихотомического программирования.

1.6 Метод сетевого программирования.

1.7 Выводы.

2. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ НА ГРАФАХ.

2.1 Основные понятия.

2.2 Задача определения циркуляции максимальной величины.

2.3 Задача о минимальном разрезе.

2.4 Задача о минимальном разрезе.

2.5 Задача о максимальном независимом множестве.

3. ЗАДАЧА О МАКСИМАЛЬНОЙ ЗАГРУЗКЕ.

3.1. Постановка задачи о максимальной загрузке.

3.2 Алгоритм в задаче о камнях.

3.3 Обобщение метода на случай различных объемов групп.

3.4 Априорные оценки.

3.5 Непрерывный вариант задачи о загрузке оборудования.

4. ФОРМИРОВАНИЕ ОПТИМАЛЬНОЙ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ ПРОЕКТНО-СТРОИТЕЛЬНОГО ПРЕДПРИЯТИЯ.

4.1 Распределение единиц проектирования между структурными подразделениями.

4.2 Определения работ для передачи на субподряд.

4.3 Другие критерии распределения работ.

Введение диссертации (часть автореферата) на тему «Метод сетевого программирования в задачах управления строительным производством»

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

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

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

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

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

2. Поставить ряд прикладных задач, моделируемых при помощи графов:

- задача о циркуляции максимальной величины;

- задача о разрезе минимальной пропускной способности;

- задача о максимальном независимом множестве.

3 Разработать алгоритмы решения поставленных задач на основе метода сетевого программирования.

4 Поставить задачу о загрузке оборудования, как задачу о камнях с различными объемами групп.

5 Разработать алгоритм решения поставленной задачи на основе метода сетевого программирования.

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

7 Применить разработанные методы к решению практических задач.

Методы исследования: В диссертации используются методы исследования операция, теории графов, теории активных систем, дискретной оптимизации.

Научная новизна роботы состоит в следующем:

1. Введено понятие агрегируемого графа и доказано, что агрегируемый граф допускает сетевое представление вида дерева.

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

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

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

5. Разработан алгоритм решения задачи о максимальном независимом множестве на основе метода сетевого программирования.

6. Разработан алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования.

7. Предложен способ определения априорных оценок для задачи о камнях.

8. Разработан эффективный метод решения соответствующей непрерывной задачи на основе декомпозиции системы ограничений.

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

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

Разработанные алгоритмы и модели на практике используются в работе предприятия ООО УК «Жилпроект» и ООО «Агрокс-2».

Модели и алгоритмы, разработанные в диссертационной работе, включены в состав учебных курсов и дисциплин: «Теория экономических и информационных систем», «Теория систем и системный анализ», «Оптимизационные задачи в экономике», читаемых в Воронежском государственном архитектурно - строительном университете.

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

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

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

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

Апробация работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях, симпозиумах и научных совещаниях в 2004-2005 гг, в том числе

- Международная школа-семинар «Современные проблемы механики и прикладной математики» (Воронеж, 2004г.)

- 27-я международная школа семинар «Системное моделирование социально-экономических процессов» (Орел, 2004г.)

- 13-я международная конференция «Математика. Экономика. Образование» (Ростов-на-Дону, 2005г.)

- 12-я международная конференция «Математика. Компьютер. Образование» (Москва-Пущино, 2005г.)

- Международная научно-практическая конференция «Теория активных систем» (Москва, 2005г.);

- Научно-техническая конференция «Современные сложные системы управления» (Воронеж, 2005 г.);

Публикации. По теме диссертации опубликовано 8 печатных работ.

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: В работе [54] автору принадлежат: математическая модель и вывод достаточного условия совместности системы линейных уравнений дубльтранспортного типа. В работах [55], [56] автору принадлежат математические модели различных задач, сводящихся к задачам дубльтранспортного типа, а также алгоритмы, основанные на идее декомпозиции. В работах [57], [58], [61], [62] автору принадлежат постановки задач, доказательство основных теорем и алгоритм, основанный на методе сетевого программирования.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, приложений. Она содержит 123 страницы основного текста, 52 рисунка, 35 таблиц. Библиография включает 63 наименования

Заключение диссертации по теме «Управление в социальных и экономических системах», Аснина, Наталия Георгиевна

ЗАКЛЮЧЕНИЕ.

В диссертационной работе получены следующие основные результаты:

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

2. Дана постановка задачи о загрузке работами подразделений, как задачи о камнях с различными объемами групп, и разработан алгоритм решения поставленной задачи на основе метода сетевого программирования.

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

4. разработанные методы применены к решению задачи оптимального распределения проектных работ между группами проектировщиков по критерию равномерности загрузки; задачи оптимального выделения части работ для передачи на субподряд; задачи распределения проектных работ по группам проектировщиков по двум критериям одновременно (критерий равномерности загрузки и финансирования).

Список литературы диссертационного исследования кандидат технических наук Аснина, Наталия Георгиевна, 2006 год

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

2. Johnson S.M. Optimal Two and The Stage Production Schedules with Set Up Times Included / S.M. Johnson // Nav. Res. Log. Quart.-1954.- V.l, №1.-P. 61-68.

3. Bellman R. Some Combinatorial Problems Arising in the Theory of Multistage Processes / R. Bellman, O. Gross // J. Soc. Indust. and Appl. Math. 1954. -V.2,№3.-P. 175-183.

4. Bellman R. Mathematical Aspects of Scheduling Theory / R. Bellman // J. Soc.Indust and Appl. Math. 1956. - V.4, №3. - P. 168-205.

5. Конвей P.B. Теория расписаний / P.B. Конвей, B.JI. Максвелл, JI.B. Миллер. -М.: Наука, 1975.

6. Танаев B.C. Теория расписаний. Многостадийные системы / B.C. Танаев, Ю.Н. Сотсков, В.А. Струсевич М.: Наука, 1989.

7. Хоботов Е.Н. Некоторые замечания к теореме Джонсона / Е.Н. Хоботов// Автомат. И телемех.-1995.-№ 10.-С. 186-187.

8. Исследование операций. Т.2. / Под ред. Моудера Дж., Элмаграби С. М.: Мир, 1981.

9. ВагнерГ. Основы исследования операций/ Г. Вагнер-Т. 1,2.-М. :Мир, 1973.

10. Беллман Р. Прикладные задачи динамического программирования /Р. Беллман, С. Дрейфус-М.: Наука, 1965.

11. Хореев В.И. Итеративные алгоритмы определения расписаний в информационно-вычислительных системах / В.И. Хареев // Автоматика и вычислит, техника. 1987.-№4. С.8-14.

12. Муравьев В.И. Использование метода переменного базиса для решения непрерывного аналога задачи Джонсона / В.И. Муравьев, И.В. Романовский // Исследование операций и статист. Моделирование.- Л., 1974.-Вып. 2.-С.27-37.

13. Gilio R.J. Approximate Solutions to the Three- Machine Scheduling Problems / R.J Gilio, H.M. Wagner // Oper. Res. 1964. -V.12 №2.-P. 305-324.

14. Story A.E. Computational Experience with Integer Programming for Job-Shop Scheduling / A.E. Story, H.M. Wagner Englewood Cliffs, N.J.: Prentice-Hall,1963.-Ch. 14.

15. Ленина А.Я. Приближенные методы решения задач теории расписаний на основе двойственных оценок / А.Я. Аснина // Экономико-математические модели и методы: Сб. науч. трудов. Воронеж: ВГУД989. - С. 162-368.

16. Аснина А.Я. Об опыте решения задач Джонсона с произвольным числом станков / А.Я. Аснина, Р.А. Тищенкова // Системный анализ и моделирование социально-экономических процессов: Тр. II Всесоюз. семинара. -М.,1981.

17. Аснина А.Я. Оптимизация гибкого производства БИС на основе модели календарного планирования / А.Я. Аснина, Т.О. Толстых // Модели и алгоритмы оптимизации сложных систем. Воронеж, 1985.

18. Аснина А.Я. Об одном алгоритме решения задачи Джонсона / А.Я. Аснина, Г.Д. Чернышева //Тр. 4-й Междунар. конференции женщин-математиков, Волгоград, 27-31 мая 1996. Н.Новгород, 1997. - Т.4, вып.1-С. 82-86.

19. Ворожеева СВ. Вероятностный алгоритм формирования поисковых функций при решении задач условной оптимизации / СВ. Ворожеева, Г.Д. Чернышева // Алгоритмы моделирования и оптимизации автоматизированных систем. Воронеж, 1990. - С. 115-121.

20. Мину М. Математическое программирование. Теория и алгоритмы. / М. Мину -М.: Наука, 1990.

21. Ленина А.Я. О двух модификациях задачи Беллмана Джонсона: модели и алгоритм решения / А.Я. Ленина, СЮ. Балашева // Вестник ВГТУ. Серия «САПР и системы автоматизации производства» - Воронеж: ВГТУ, 2001.-Выпуск 3.1 -С 34-39.

22. Goldberg D. Е. Genetic algorithms in search, optimization, and machine learning. Reading/ Goldberg D. E. // MA: Addison-Wesley. 1989.

23. Holland J. H. Adaptation in natural and artificial systems./ Holland J. H. //Ann Arbor: University of Michigan Press. 1975.

24. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации./ Еремеев А.В. // Дисс. канд.физ.-мат.наук. Омск, 2000.

25. Александров Н.И. Моделирование организации и управления решением научно-технических проблем./ Н.И. Александров, Н.И. Комков, // М.: Наука, 1988. -216 с.

26. Алтаев В.Я., Теория сетевого планирования и управления/ В.Я. Алтаев, В.Н.Бурков, А.И. Тейман // Автоматика и Телемеханика. 1966. № 5.

27. Баркалов С. А.Минимизация упущенной выгоды в задачах управления проектами/ С.А. Баркалов, В. Н. Бурков, Н.М. Гилязов, П. И. Семенов., -М.: 2001.

28. Баркалов П.С., Задачи распределения ресурсов в управлении проектами./ П.С Баркалов., И.В. Буркова, А.В. Глаголев, В.Н. Колпачев// М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН), 63 с

29. Бурков В.Н. Прикладные задачи теории графов./ В.Н. Бурков, И.А. Горгидзе, С.Е.Ловецкий // -Тбилиси: Мецниереба, 1974. 234 с

30. Арнольд В.И. О функциях трех переменных./ В.И. Арнольд// ДАН СССР, 1957, №2

31. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных./ А.Н. Колмогоров //-ДАН СССР, 1956, 108, №2

32. Баркалов С.А. Прикладные модели в управлении организационными системами./ С.А. Баркалов, В.Н. Бурков, и др.// ИПУ РАН, ВГАСУ, ТГУ, Тула. 2002.

33. Баркалов С.А., Методы агрегирования в управлении проектами./ С.А, Баркалов, В.Н. Бурков, Н.М. Гилязов // М.: ИПУ РАН, 1999. 55 с.

34. Баркалов П.С. Задачи распределения ресурсов в управлении проектами/ П.С. Баркалов, В.Н. Бурков, А.В, Глогольев, В.Н. Колпачев // Москва, ИПУ РАН, 2002г. 52с.

35. Баркалов П.С. Эвристические алгоритмы календарного планирования при управлении проектом/ П.С. Баркалов, В.Н. Бурков, В.Н. Колпачев// Современные сложные системы: сборник трудов Международной конференции,- Воронеж, 2003г. Том1 С.204-207.

36. Бурков В.Н. Теория графов в управлении организационными системами. /В.Н. Бурков, А.Ю. Заложнев, Д.А. Новиков.- М.: СИНТЕГ, 2001. 124 с.

37. Бурков В.Н. Методы решения экстремальных задач комбинаторного типа (обзор)./ В.Н. Бурков, С.Е. Ловецкий // Автоматика и телемеханика 1968, № 11.

38. Бурков В.Н., Методы решения экстремальных комбинаторных задач (обзор)./В.Н. Бурков, С.Е. Ловецкий //Техническая кибернетика-1968, № 4.

39. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации. -Материалы международной научно-технической конференции «Системные проблемы качества, математического моделирования, информационных и электронных технологий», Радио и связь, 2003. С. 2328.

40. Басакер Р., Конечные графы и сети. / Басакер Р., Саати Т. М: Наука, 1973. - 368 с.

41. Берж К. Теория графов и ее применения. / Берж К.- М.: Иностранная литература, 1962. 319 с.50.

42. Оре О. Теория графов/ О. Ope.- М: Наука.-1968.-350с.

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

44. Танаев B.C. Теория расписаний. Одностадийные системы./ B.C. Танаев, B.C. Гордон, Я.М. Шафранский. М.: Наука, 1984. - 230 с.

45. Аснина Н.Г. Двойственность в задачах дискретной оптимизации/ Н.Г. Аснина, Н.В. Буркова, П.А. Колесников, Н.В. Попок// Теория активных систем: Труды международной практической конференции. М: ИПУ РАН, 2005.-с. 15

46. Ленина Н.Г. Задача о максимальной циркуляции для агрегируемых графов/ Н.Г. Ленина, С.А. Баркалов, И.В. Буркова // Вестник Воронежского государственного технического университета. -Воронеж: ВГТУ, 2006. том 2, №2 с. 35-42

47. Ленина А .Я. О существовании неотрицательных решений систем линейных уравнений и неравенств специального вида/ Л.Я. Ленина// Вопросы оптимального программирования в производственных задачах. -Воронеж: Изд-во ВГУ, 1980.-С.23-32

48. Ленина Н.Г. Задача о максимальном независимом множестве/ Н.Г. Ленина // Вестник Воронежского государственного технического университета. -Воронеж: ВГТУ, 2006. том 2, №2 с. 20-25

49. Ленина А.Я Модели, алгоритмы, оценки в задаче оптимизации загрузки / А.Я Ленина, Н.Г. Ленина, И.В. Буркова, И.В. Попок// Вестник Воронежского государственного технического университета. Воронеж: ВГТУ, 2006. том 2, №2 с. 3-16

50. Ленина Н.Г. Выбор оптимального набора продуктов/ Н.Г. Ленина, С.В. Серенько, Г.Д. Юшин// Современные сложные системы управления: Сборник трудов научно-практической конференции. Воронеж: ВГАСУ, 2005.-том 2, стр. 123-125

51. Ленина Н.Г. Оптимальная модель последовательности выполнения проектов/ Н.Г. Ленина, И.В. Бурков, A.M. Котенко // Сборник трудов научно-практической конференции. Воронеж: ВГАСУ, 2005.-том 1, стр. 89-941. УТВЕРЖДАЮ1. АКТ

52. Настоящим подтверждаем, что результаты кандидатской диссертации Лениной Н.Г.:----

53. Модель загрузки оборудования, приводящаяся к задаче о камнях с различными объемами групп;

54. Моделирование системы управления в виде графа, имеющего контуры, обнаружение этих контуров и их ликвидация с минимальными потерями;

55. Декан факультета автоматизации и информационных систем, доцент1. Д.К. Проскурин1. УТВЕРЖДАЮнеральный директор1. АКТ19 декабря 2005 г.г. Воронеж

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

57. В период с 5 сентября 2005 г. по 16 декабря 2005 г. в ООО «Агрокс 2» проводилась научно-исследовательская работа по совершенствованию процесса планирования производственной деятельности предприятия.

58. Результатом работы явилась разработка ряда методических материалов по созданию и практическому использованию моделей и методов, основанных на применении методов математического программирования.1. В их числе:

59. Модель загрузки оборудования, приводящаяся к задаче о камнях с различными объемами групп;

60. Моделирование системы управления в виде графа, имеющего контуры, обнаружение этих контуров и их ликвидация с минимальными потерями;

61. Модель выбора множества объектов максимальной суммарной ценности при ограничении на несовместимость пар объектов.

62. Результаты работ получили поддержку и одобрение на заседаниях техник ческого совета.1. Начальник ПТО26 декабря 2005 г.1. АКТг. Воронеж

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

64. Модель загрузки структурных подразделений, приводящаяся к задаче о камнях с различными объемами групп;

65. Модель выбора множества объектов максимальной суммарной ценности при ограничении на несовместимость пар объектов.

66. Результаты работ получили поддержку и одобрение на заседаниях технического совета.1. Начальник ПТО