Помощь в написании студенческих работ
Антистрессовый сервис

Математические модели и генетические методы решения нелинейных задач транспортного типа

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

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на международной научно-технической конференции «Интеллектуальные САПР» (ТРТУ, Таганрог-Гурзуф, 1997), на IV всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТРТУ, Таганрог, 1998), на региональной конференции «Информатизация… Читать ещё >

Математические модели и генетические методы решения нелинейных задач транспортного типа (реферат, курсовая, диплом, контрольная)

Содержание

  • ГЛАВА 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ И МЕТОДЫ ИХ РЕШЕНИЯ. д
    • 1. 1. Прикладные задачи производственно-транспортного планирования как объект математического моделирования
    • 1. 2. Основные виды многоэкстремальной оптимизации
    • 1. 3. Математические модели и классические методы решения транспортной и распределительной задач
    • 1. 4. Модели процессов оптимизации в природе
    • 1. 5. Исследование методов генетического поиска
    • 1. 6. Выводы
  • ГЛАВА 2. РАЗРАБОТКА ЭФФЕКТИВНОГО ГЕНЕТИЧЕСКОГО МЕТОДА РЕШЕНИЯ НЕЛИНЕЙНОЙ ТРАНСПОРТНОЙ ЗАДАЧИ
    • 2. 1. Математическая модель и кодировка решения
    • 2. 2. Моделирование начальной популяции
    • 2. 3. Функция оценки годности
    • 2. 4. Моделирование процессов кроссинговера и мутации
    • 2. 5. Формирование репродукционной группы и моделирование естественного отбора
    • 2. 6. Общая структура разработанного метода решения нелинейной транспортной задачи и его свойства
    • 2. 7. Применение моделирования макроэволюции для повышения качества решения
    • 2. 8. Выводы
  • ГЛАВА 3. РАЗРАБОТКА ЭФФЕКТИВНОГО ГЕНЕТИЧЕСКОГО МЕТОДА РЕШЕНИЯ НЕЛИНЕЙНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ
    • 3. 1. Математическая модель и кодировка решения
    • 3. 2. Моделирование начальной популяции
    • 3. 3. Функция оценки годности
    • 3. 4. Обоснование применения оператора кроссинговера
    • 3. 5. Моделирование процесса мутации
    • 3. 6. Общая структура разработанного метода решения нелинейной распределительной задачи и его свойства
    • 3. 7. Модифицированный ГА с усложненной структурой
    • 3. 8. Выводы
  • ГЛАВА 4. ОБОСНОВАНИЕ И ТЕСТИРОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ
    • 4. 1. Цели экспериментального исследования
    • 4. 2. Исследование эффективности алгоритмов с использованием математического моделирования и вычислительного эксперимента
    • 4. 3. Применение разработанных методов и комплекса проблемно-ориентированных программ для решения прикладных задач
    • 4. 4. Выводы

Актуальность темы

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

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

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

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

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

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

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

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

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

• Построен новый генетический оператор кроссинговера, ориентированный на специфику нелинейных транспортной и распределительной задач;

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

• Усовершенствован известный оператор мутации с учетом нелинейности решаемых задач.

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

Реализация результатов работы. Разработанные алгоритмы использованы при выполнении федеральных госбюджетных научно-исследовательских работ в Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения (РГАСХМ): «Теоретические основы эволюционного моделирования генетических алгоритмов», «Основы вычислительного представления генетических алгоритмов для решения оптимизационных задач», «Развитие эволюционного моделирования для решения оптимизационных задач» и «Теория поисковой адаптации для решения избранных комбинаторных задач оптимизации». Результаты диссертационной работы использованы при оптимизации межцеховых перевозок в ООО «Ростовский литейный завод». Материалы диссертации используются в учебном процессе на кафедре прикладной математики и вычислительной техники РГАСХМ при проведении лекционных и практических занятий по курсам «Основы САПР» и «Программные средства САПР». Акты об использовании результатов работы приведены в приложениях к диссертации.

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на международной научно-технической конференции «Интеллектуальные САПР» (ТРТУ, Таганрог-Гурзуф, 1997), на IV всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТРТУ, Таганрог, 1998), на региональной конференции «Информатизация, автоматизация и роботизация в машиностроении» (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции «Проблемы совершенствования зерноуборочной техники: конструирование, организация производства, эксплуатация и ремонт» (РГАСХМ, Ростов-на-Дону, 1999), на международной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2000), на региональной научно-технической конференции «Интеграция отраслевой и вузовской науки: проблемы современного машиностроения» (РГАСХМ, Ростов-на-Дону, 2002, 2003), на студенческой научной конференции Ростовского государственного педагогического университета (РГПУ, Ростов-на-Дону,.

2003), на XVI международной научной конференции «Математические методы в технике и технологиях» (С.-ПбГТУ, Санкт-Петербург, 2003), на XXX юбилейной международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (1Т+8Е'2003)» (Украина, Ялта-Гурзуф, 2003), на VI международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (МГАПИ, Москва, 2003).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 101 наименования и двух приложений. Содержание диссертационной работы изложено на 120 страницах, в том числе 15 рисунков, 11 таблиц.

4.4. Выводы.

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

2. Экспериментальным путем определена вычислительная сложность предложенных алгоритмов, составившая величину порядка о (п2), что подтвердило теоретические оценки, приведенные в главе 2 и главе 3.

3. Разработанный генетический алгоритм применен для решения прикладной нелинейной распределительной задачи оптимизации межцеховых (внутризаводских) перевозок ООО «Ростовский литейный завод».

ЗАКЛЮЧЕНИЕ

:

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

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

3. Разработан оператор кроссинговера Cross 2, производящий легальные (допустимые) решения и имеющий вычислительную сложность 0(п2). Усовершенствован оператор мутации Mutation 1, отличающийся от известного тем, что точки мутации определяются не случайно, а с использованием знаний о целевой функции.

4. Смоделирована генетическая процедура инициализации начальной популяции для распределительной задачи, основанная на методе последовательного насыщения строк и столбцов матрицы допустимого плана задачи. Данная процедура имеет вычислительную сложность 0(тпр), где р — размер популяции. Сформулировано и доказано утверждение, которое позволяет использовать для распределительной задачи оператор кроссинговера Cross 2, разработанный для нелинейной транспортной задачи.

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

6. Разработанные методы протестированы с использованием ЭВМ. Проведенные исследования подтвердили теоретические оценки вычислительной сложности методов, составившие величину порядка 0(гГ). По сравнению с известными методами разработанные алгоритмы являются более эффективными, в частности, улучшение по качеству составило 3−12%, а по времени — на 1−2 порядка.

Показать весь текст

Список литературы

  1. B.C., Трубин В. А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. — М.: Наука, 1986 259 с.
  2. B.C., Гупал A.M., Норкин В. И. Методы невыпуклой оптимизации. М.: Наука, 1987.
  3. .Т. Введение в оптимизацию. М.: Наука, 1983 — 384 с.
  4. П., Барнес Д. Потоковое программирование. М.: Радио и связь, 1984.
  5. А.З. Разработка и исследование генетических методов размещения двумерных геометрических объектов: Автореф. дис. канд. тех. наук. Таганрог: ТРТУ, 1996.
  6. Cohoon J.P., Martin W. N., Richards D.S. A multi-population genetic algorithm for solving the k-partition problem on huper-cube. San Diego, 1991.
  7. Cohoon J.P., Herde S.V., Martin W. N., Richards D. S. Distributed genetic algorithms for the floorplan design problem. IEEE Trans on CAD, vol. 10, April, 1991, pp. 483−491.
  8. Hitchcock F.L. Distribution of a product from several sources to numerous localities.//J. Math. Puys, 1941.
  9. Holland J.H. Adaptation in natural and artificial systems: an introductory analysis with application to biology, control, and artificial intelligence. University of Michigan, 1975.
  10. Adolf Hofmaifar. A new approat on the travelling salesman problem by genetic algorithms. Department of electrical engineering North Carolina A&T State University Greensboro. North Carolina.
  11. Crefenstette J., Rajiv Gopal, Rosmaito В., Gurcht D.V. Genetic algorithms for the travelling salesman problem. Computer Sciens Department. Vanderbild, 1989.
  12. Handbook of genetic algorithms, Edited by Lawrence Davis, Van Nostrand Reinhold, New York, 1991.
  13. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company, inc. 1989.
  14. Mange A.P., Mange E.J. Genetics: human aspects. Saunder College, Philadelphia, 1982.
  15. П.Голынтейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.
  16. И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.
  17. А.Н. Методы устранения нерациональных перевозок при планировании. М.: Социалистический транспорт, 1939.
  18. Л.В., Гавурин М. К. Применение математических методов в вопросах анализа грузопотоков. М.: Издательство АН СССР, 1949.
  19. Кун Х. У. Венгерский метод решения задачи о назначениях // В сб. «Методы и алгоритмы решения транспортной задачи. М.: Госстандарт, 1963.
  20. С.А. Современные экономико-математические методы в управлении и планировании на автомобильном транспорте. М.: Высшая школа, 1969.
  21. .Л. Математические методы планирования грузовых автомобильных перевозок. М.: Транспорт, 1972.
  22. В.И., Кузнецов Ю. Н., Волощенко А. Б. Математическое программирование. Киев, 1973.
  23. .Ю., Лившиц В. И. Нелинейные сетевые транспортные задачи. М.: Транспорт, 1972.
  24. Жак С. В. Математическое программирование. Ростов-на-Дону, РГУ, 1972.
  25. С.Г. Алгоритмы и программы нелинейной оптимизации. -Новочеркасск, 1992.
  26. Проблемы нелинейного программирования. Оптимизация. АН СССР. -Новосибирск, 1978.
  27. О.И. Вычисление нижних оценок в многоэкстремальной задаче о потоке минимальной стоимости. М.: АН СССР, 1988.
  28. Ю. Э. Эффективные методы в нелинейном программировании. -М.: Радио и связь, 1989.
  29. О.И. Метод ветвей и границ для решения задачи о многопродуктовом потоке с вогнутой функцией стоимости. М.: АН СССР, 1987.
  30. Е.С. Исследование операций. Задачи, принципы, методология. -М.: Наука, 1988.
  31. М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982.
  32. Е.М., Левит Б. Ю., Лившиц В. Н. Нелинейные транспортные задачи на сетях. М.: Финансы и статистика, 1981.
  33. Malek-Zavarei М., Frisch I.F. On the fixed-cost flow problem. International Journal of control, 1972.
  34. Florian M., Robillard P. An implict enumeration algorithm for the concave cost network flow problem. Managment Science, 1971.
  35. Klein M. A primal methpd for minimal cost flows with applications to the assignment and transportation problems. Managment science, 1967.
  36. Zangwill W.A. Blacklogging model and a multi-echelon model of a dynamiic economic lot size production system a network approat. Managment science, 1969.
  37. Efroymson M.A., Ray T.L. A branch and bound algorithms for plant location operations research, 1966.
  38. С.С. Конечный метод решения нелинейных задач транспортного типа // Экономика и математические методы. М.: Наука, 1965.
  39. Л.П. Алгоритм решения нелинейной транспортной задачи. // Экономика и математические методы. Т4. — В6. — М.: Наука, 1968.
  40. A.A. Целочисленные задачи линейного программирования.// Экономика и математические методы. ВЗ. М.: Наука, 1965.
  41. Д.Б. Методы количественного анализа сложных систем // Известия АН СССР. Техническая кибернетика. М. 1965.
  42. Хоанг Туй. Вогнутое программирование при линейных ограничениях// Доклады Академии наук СССР. Т 159.- М., 1964.
  43. С.Л. Вычислительные алгоритмы и опыт минимизации вогнутой функции на выпуклом многограннике. М.: ВЦ АН СССР, 1990.
  44. В.Р., Уткин С. Л. Решение многоэкстремальных задач вогнутого программирования аппроксимационно-комбинативным методом M.: ВЦ АН СССР, 1988.
  45. В.Р., Монтлевич В. М. Решение нелинейных производственно-транспортных задач с неделимыми потребителями. М.: ВЦ АН СССР, 1987−22 с.
  46. C.B., Лебедев С. С. Новый алгоритм метода условных векторов целочисленного программирования // Экономика и математические методы. М.: Наука, 2002. — Т. 38. — № 1. — С. 121−129.
  47. С.П. Модели эффективного развития сети автомобильных дорог // Экономика и математические методы. М.: Наука, 2002. — Т. 38. -№ 3. — С. 54−62.
  48. М.Д., Маракуев A.B., Паринов С. И. Применение новых информационных технологий в экономических исследованиях. // Экономика и математические методы. М.: Наука, 2003. — Т. 39. — № 2. -С. 155−157.
  49. О.М. К вопросу о модели нелинейных тарифов // Экономика и математические методы. М.: Наука, 2003. — Т. 39. — № 1. — С. 43−47.
  50. В.Н., Петрова T.B. Релаксационный метод минимизации с растяжением пространства в направлении субградиента // Экономика и математические методы. М.: Наука, 2003. — Т. 39. — № 1. — С. 106−111.
  51. П.М. О неразрешимости задач гарантированного поиска в достаточно большой области // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. М.: Изд-во Московского университета, 2000. — № 1. — С. 44−48.
  52. М.К. Конструктор генетических алгоритмов и способы кодирования хромосом // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. М.: Изд-во Московского университета, 2001. — № 3. — С. 43−49.
  53. Д.Ф. Генетика с основами селекции. М.: Высшая школа, 1971. -410 с.
  54. Большая советская энциклопедия. Третье издание. М.: Советская энциклопедия, 1975.
  55. В.В. Механизмы генетической рекомбинации. Ленинград, 1971.
  56. В.В. Элементарные процессы генетики. Ленинград, 1973.
  57. П.П. Избранные труды. М., 1973.
  58. Л.А. Случайный поиск в эволюционных вычислениях// Обозрение прикладной и промышленной математики. М.: ТВП, 1996.
  59. Vignaux G. A, Michalewicz Z. Genetic algorithm for the linear transportation problem. IEEE transactions on system, man, and cybernetic, 1991.
  60. В.В. Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС: Автореф. дис. канд. тех. наук.- Таганрог: ТРТУ, 1995. 16 с.
  61. Э. Эволюционные вычисления и ГА // Обозрение прикладной и промышленной математики. М.: ТВП, 1996.
  62. В.М. Генетические алгоритмы. Учебник для вузов. Таганрог: ТРТУ, 1998.
  63. . Современное линейное программирование. — М.: Мир, 1984.
  64. Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
  65. Л.В. Экономический расчет наилучшего использования ресурсов. М.: Изд-во АН СССР, 1959.
  66. Л.Г., Кириченко И. О. Многоиндексные задачи линейного программирования. — М.: Радио и связь, 1982.
  67. С. Линейное программирование (методы и приложения)./пер. с англ.- М.: Физматгиз, 1961.
  68. X. Комбинаторная оптимизация. М.: Мир, 1984.
  69. Д.Б., Гольшьейн Е. Г. Задачи и методы линейного программирования. М.: Сов. радио, 1961.78.3уховицкий С.И., Авдеева Л. И. Линейное и выпуклое программирование. -М.: Наука, 1967.
  70. . Б. Основы линейного программирования. / пер. с англ. М.: Радио и связь, 1989.
  71. Д.Б., Голыитейн Е. Г. Линейное программирование. Теория, методы и приложения. — М.: Наука, 1969.
  72. В.А., Звягина P.A., Яковлева М. А. Численные методы линейного программирования. М.: Наука, 1976.
  73. Э. Алгоритмы оптимизации на сетях и графах. — М.: мир, 1981.
  74. Е.Б. Задачи математического программирования транспортного типа. М.: Сов. радио, 1967.
  75. Ю.О., Басова A.B. Генетические алгоритмы для решения нелинейных задач транспортного типа // Известия ТРТУ, № 2, Таганрог, 1998.-С. 259−260.
  76. A.B. Транспортировка сельскохозяйственной продукции: новый подход. // Интеграция отраслевой и вузовской науки: проблемы современного машиностроения. Материалы международной научно-технической конференции. Ростов-на-Дону, РГАСХМ, 2000. — С. 30.
  77. A.B. Методика отбора особей для кроссинговера в генетических алгоритмах. //Сборник тезисов докладов студенческой научной конференции РГПУ. Ростов-на-Дону, 2003. — С. 260.
  78. A.B. Генетический метод отыскания глобального минимума многоэкстремальных задач. //Математические методы в технике и технологиях. Сборник трудов XVI международной научной конференции. Т.2. Санкт-Петербург, 2003. — С. 141−143.
  79. E.H. Статистические методы построения эмпирических формул. — М.: Высшая школа, 1988. 239 с.
  80. А.К. Техника статистических вычислений. М.: Наука, 1971.-576 с.
  81. Ю.П. Введение в планирование эксперимента. — М.: Металлургия, 1969.- 157 с.
  82. С. А. Статистическое исследование зависимостей. — М.: Металлургия, 1968. 227 с.
  83. С.Д., Гурвич Ф. Г. Математико-статистические методы экспертных оценок. М.: Статистика, 1980. — 264 с.
  84. Н., Смит Г. Прикладной регрессионный анализ. М.: Финансы и статистика, 1986. — 365 с.
Заполнить форму текущей работой

Сессия? Спокойно!