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

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

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

Алибеков Байрамбек Исаевич

Махачкала - 2013

1. Общая характеристика работы

Актуальность темы исследования.

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

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

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

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

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

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

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

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

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

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

Достижение поставленной цели обеспечивается решением в диссертационной работе следующих задач:

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

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

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

- проведение вычислительных экспериментов по оценке адекватности и точности модельного аппарата исследования сложных систем на примере транспортной системы.

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

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

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

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

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

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

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

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

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

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

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

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

Теоретическая и методологическая основы исследования.

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

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

Основные положения, выносимые на защиту:

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

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

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

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

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

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

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

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

Приведенные в работе методы и модели были применены для:

а) составления расписания обработки танкеров при разработке АСУ Новороссийского нефтеналивного порта;

б) размещения и развития депо по ремонту подвижного состава железнодорожного транспорта СКЖД;

в) размещения и развития сахарных заводов и промежуточных перевалочных пунктов на Северном Кавказе;

г) размещения и развития базовых сортировочных станций и определения сферы их влияния в Ростовском отделении СКЖД.

д) решения комбинаторной задачи организации вагонопотоков для 21 станции СКЖД (результаты приведены в приложении диссертации).

Разработанные в данной диссертации технологические и экономико-математические модели, методы, алгоритмы и программы на современных языках визуального программирования Delphi и VBA для Excel используются и могут быть применены для решения комплекса проблем планирования и прогнозирования производственно-транспортных задач.

Апробация работы. Материалы исследования и результаты работы докладывались и получили одобрение на следующих конференциях и заседаниях научных школ: Всесоюзная конференция по транспортно-экономическим связям и размещению производства, Алма-Ата 1983г.; Научно-практическая конференция «Актуальные проблемы развития транспорта черноморского побережья России», Туапсе 2004 г.; Третий Южно-Российский логистический форум. Ростов-на-Дону 2006г.; Международная научно - практическая конференция «Проблемы и перспективы развития транспортного комплекса: образование, наука, производства», Ростов-на-Дону, 2009г.; Научно-практическая конференция VI Южно - Российский логистический форум. Ростов-на-Дону 2009 г.; Международная научно - практическая конференция «Перспективы экономической интеграции прикаспийских государств и их регионов», Махачкала 2009г.; Всероссийская научно - практической конференции «ТРАНСПОРТ -2009». Ростов-на-Дону 2009 г.; Всероссийская научно - практическая конференция «Транспорт-2010», Ростов-на-Дону 2010 г.; Восьмая международная научно-практическая конференция «Телекоммуникационные, информационные и логистические технологии на транспорте» «Телеком Транс-2011» Ростов-на-Дону, 2011 г.; «Функционально дифференциальные уравнения и их приложения», международная научная конференция, посвященной 80-летию Дагестанского государственного университета, Махачкала 2011 г.

Разработанные алгоритмы и программы включены в Государственный фонд алгоритмов и программ и регистрированы отделом регистрации программ для ЭВМ Федерального института промышленной собственности:

а) «Алгоритм определения приближенного решения двухэтапной задачи размещения», инвентарный номер 11000804 от 17.04.74;

б) «О задаче на размещение с ограниченными мощностями», инвентарный номер 11001411 от 26.05.75.22;

в) «Программный комплекс оптимального размещения объектов транспортных систем и управления грузовыми потоками на ООП Delphi», свидетельство о государственной регистрации программ для ЭВМ №2012612271, 29 февраля 2012 г.;

г) «Программный комплекс оптимального размещения объектов транспортных систем и управления грузовыми потоками на языке VBA для Excel», свидетельство о государственной регистрации программ для ЭВМ №2012612093, 24 февраля 2012 г.

Автор диссертации, будучи членом Северо-Кавказского филиала Комиссии АН СССР по проблемам транспорта, утвержденной 21.06.1989 года, участвовал в выполнении хоздоговорной научно - исследовательской темы »Моделирование транспортного комплекса региона», включенной в программу фундаментальных исследований по проблемам транспорта АН СССР (РАН) за 1989-2000 годы. За активное участие в создании производственной базы научного и производственного комплекса «Электровоз» и в развитии творческих связей производством, расширение научных исследований по транспортной тематике, автор диссертации награжден почетными грамотами руководствами НЭВЗа и РИИЖТа.

Публикации. По теме диссертации опубликовано 48 работ общим объемом более 37,5 п.л., в том числе 2 монографии, 15 работ в изданиях ведущих рецензируемых научных журналах и изданиях, определенных ВАК, 2 свидетельства о государственной регистрации программ для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Объем работы 274 страниц машинописного текста, содержит 30 таблиц, 23 рисунка, 3 приложений, список литературы включает 305 наименований.

транспортный алгоритмический дискретный программирование

2. Краткое содержание работы

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

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

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

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

- прогнозирование;

- планирование производства и потребления продукции;

- определение грузопотока;

- определение потока транспортных единиц, размещение и развитие транспортных узлов, переработка транспортных единиц, погрузка-выгрузка;

- надежность функционирования транспортного комплекса;

- ресурсное обеспечение развития транспортного комплекса.

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

Зная транспортные издержки и выпуск продукции в пунктах , решается задача размещения и развития производства первичных ресурсов.

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

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

=, ,…,.

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

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

Обозначим разность структур и .

Параметры , и структуры определяются после преобразования параметров и структуры . Для определенной структуры глубиной под преобразованиями понимаются решения множество задач дискретного программирования по схеме (рисунок 3) По следующей схеме после преобразования получим , после преобразования получим

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

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

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

,

где -время, -значения показателя, -темп изменения показателя (скорость) и - темп темпа (ускорение). Оказалась, что модель

можно использовать для анализа некоторых вариантов реальных временных рядов. Виды решений уравнения (2) при различных значениях параметров и показывают, что модель (1) охватывает широкий класс часто используемых при прогнозировании детерминированных логистических кривых.

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

,

где , , - решение уравнений (2). Определяется тригонометрический полином

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



Рисунок 1 - График среднеарифметических значений рядов статистики грузопотоков хлебных грузов за 2000-2007 годы

Рисунок 2 - График среднеарифметической величины рядов грузопотоков хлебных грузов за 2000-2007 годы

При исследовании метода допускается, что M=2 и и . Параметры определяются методами Крылова, Гаусса и ортогонализации.



Функция, полученная методом ортогонализации, после обработки статистики грузопотока хлебных грузов за 2000-2007 годы имеет вид:

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

Во второй главе «Модели организации взаимодействия различных видов транспорта» разработана имитационная модель организации и взаимодействия различных объектов транспортного узла.

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

Известно:

a) число пунктов, в которые (из которых) доставляются (вывозятся) грузы;

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

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

г) длительность планирования перевозок.

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

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

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

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

Имитируется прибытие (подача) групп вагонов в каждый грузовой район под разгрузку, погрузку и на сортировку.

Имитируется работа погрузочно-разгрузочных механизмов, их выход из строя и восстановление (ремонт).

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

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

О возможностях модели можно судить по набору участвующих в ней параметров. Их более двадцати на каждый из 4-х грузовых районов. Практически любой параметр может быть рассчитан в комплексе. Группа параметров является небольшой. Последнее объясняется тем, что существует степенная зависимость между размером группы и затрачиваемым машинным временем на компьютере, потребляемым на решение подобной задачи. Модель может быть легко настроена на заданный набор численных значений параметров системы, легко перенастраиваться, отключать от своего состава тот или иной грузовой район (что значительно сокращает затраты времени на реализацию вариантов модели). Программа на Delphi занимает 120 стр. Подробная блок-схема, основные параметры, формулы вычисления, функции распределения процессов, протекающих на транспортном узле, и математические модели планирования работы транспортного узла приведены в приложении диссертации ст. 340-415. Главная форма программы (модуль Mainfm.pas).

Рисунок 3 - Форма размещения компонентов



Рисунок 4 - Форма для ввода данных

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

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

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

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

,

Обозначим , , где - малое число, . Тогда (3) можно аппроксимировать следующей задачей: найти план , минимизирующий функцию

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

(5)

.

Решив пару задач, определяем планы , доставляющие минимум функции (5), =1,…, [p/2]. Из свойства функции (5) вытекает неравенство . При минимизации можно сужать область , вводя после решения очередной задачи и получения значения ограничения вида , , ?=1,…,[p/2]. Таким образом, будут решаться задачи:

,

 - оптимальные планы задач (6). Формальное описание процесса. Пусть , где (т.е. ? принимает значения ? и p-?). Положим и . Пусть план минимизирует функцию

,

где определяется условиями , и k меняется с изменением ?, а , если , или определяется из условия . План минимизирует (5) на . План доставляет локальный минимум функции (4). в окрестности .

Оптимальные планы задач (3), (7), или приближенной задачи (4), (7) определяются алгоритмами, разработанными, а диссертации.

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

_,

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

, (9)

,

.

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

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

.

Вагонопоток, перерабатываемый на всех сортировочных станциях -го маршрута, рассчитывается по формуле .

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

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

,

и удовлетворяющим ограничениям

,

Численные метод решения задачи (8)-(9) модифицируется для решения задач (8), (9) и (10-12) и дается оценка методов в диссертации.

Численные методы оптимизации размещения и развития сортировочных станции транспортного комплекса региона.

Рассмотрим постановку задачи оптимального размещения и развития сортировочных станции. Имеется региональная железнодорожная сеть.

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

- вагонопоток, то есть число вагонов доставляемых из станции в станцию .

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

Функция зависит от мощности перерабатываемых вагонов .

Далее введем следующие обозначения:

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

- наличие каналов вида , , необходимых для выполнения единицы операций (работы) подвижных единиц для -й станции, , в момент времени .

-функция условных потерь, неотрицательная, монотонно неубывающая функция времени, , .

Цель оптимального планирования состоит в минимизации функции условных потерь:

, j=1,2,…,n

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

,

Ограничения на порядок выполнения работ во времени имеет вид где -множество пар работ, для которых выполнено отношение предшествование.

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

Ограничения на порядок выполнения операции во времени имеет вид , . - средняя длина поезда, формируемая из вагонопотока (в вагонах), . - параметр накопления (вагоно-часы), зависящий от объема вагонопотока . - затраты (вагоно-часы) на переработку вагонов для -й станции, j=1,2,…,n.

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

Тогда задача развития и размещения СС формулируется как задача размещения в вариантной постановке следующим образом. Найти план перевозки , доставляющий минимум функции

,

, ,

В диссертации разработан итерационный метод решения последней задачи, состоявший из трех этапов: использования теории массового обслуживания (ТМО), теории сетевого планирования и управления (СПУ) и математического программирования.

Выводы

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

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

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

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

4. Рассмотрены многоэкстремальные задачи типа размещения с нелинейной функцией цели и линейными ограничениями (размещения: производства сырья, переработки ресурсов, транспортных предприятий, сортировочных станций, складов, депо по ремонту подвижного состава и др.). Выпуклая вверх исходная функция цели автором заменяется кусочно-линейной функцией, и исходная задача сводится к частично-целочисленной приближенной задаче. Для решения приближенной задачи предложен эффективный двухсторонний итерационный метод определения плана, близкого к оптимальному плану, даются оценки аппроксимации и метода. Разработанными программами на компьютере решены тестовые и производственные нелинейные задачи размещения с разными ограничениями и размерами матриц 100*40, 80*60, 90*20 и т.д. Результаты вычислительных экспериментов приводятся в диссертации.

5. Организация перевозок на железнодорожном транспорте опирается на решение NP-сложной задачи организации вагонопотоков. Комбинаторная задача организации вагонопотоков сводится к многоэкстремальной задаче размещения. Полученная задача решается методом, разработанным в диссертации. Комплексная задача развития пропускных и сортировочных мощностей региональной железнодорожной транспортной сети решается на основе приведенной модели, которая аналогична модели размещения производств и относится к классу задач синтеза сетей. Численный пример и результаты, полученные при решении задачи организации вагонопотоков для 21 станции СКЖД, приведены в приложении.

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

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

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

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

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

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

Таблица 1. Название проблем, методов их решения и языки программирования

№ П/п	Название задачи	Метод решения	Языки программирования
1	Прогнозирования
1.1.	Выявление скрытых периодичностей	Метод Крылова и метод наименьших квадратов	VBA для Excel, Delphi
1.2.		Метод Крылова и метод наименьших квадратов, метод Гаусса

Подобные документы

• Математическое и программное моделирование системы автоматического управления с помощью программного обеспечения MatLab и Simulink

  Обзор методов составления математических моделей систем автоматического управления. Математические модели системы в векторно-матричной форме записи. Моделирование в пакете программы Simulink. Оценка устойчивости системы, рекомендации по ее применению.
  
  курсовая работа [514,5 K], добавлен 10.11.2011
  

• Разработка модели и решение задачи линейного программирования на примере задачи об оптимизации размещения рекламы. Компания "Медиа Оптимизатор"

  Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
  
  курсовая работа [607,2 K], добавлен 13.03.2015
  

• Разработка математической модели и численное исследование технологической схемы теплотехнической системы

  Расчет тепловой схемы с применением методов математического моделирования. Разработка алгоритма реализации модели. Составление программы для ПЭВМ, ее отладка и тестирование. Проведение численного исследования и параметрическая оптимизация системы.
  
  курсовая работа [2,8 M], добавлен 01.03.2013
  

• Разработка и исследование модели распространения эпидемии в среде программирования Anylogic 6.0

  AnyLogic как инструмент компьютерного моделирования нового поколения. Процесс разработки моделей и реализация имитационных моделей для распространения эпидемического заболевания. Разработка систем обратной связи (диаграммы потоков и накопителей).
  
  контрольная работа [1,8 M], добавлен 21.07.2014
  

• Имитационное моделирование

  Сущность, принципы и описание методов и этапов имитационного моделирования. Процессы и применение дискретного и непрерывного алгоритма. Характеристика методов построения математических моделей для решения управленческих задач банковской системы.
  
  курсовая работа [80,5 K], добавлен 29.05.2014
  

• Автоматизированное проектирование информационно-измерительной системы на основе SCADA

  Разработка операторского интерфейса системы мониторинга и управления объекта, обладающего инерционными свойствами. Создание программного обеспечения для отображения данных системы в среде программирования ST. Моделирование имитаторов объекта управления.
  
  курсовая работа [3,1 M], добавлен 14.02.2016
  

• Исследование методов автоматизированного проектирования динамических систем

  Структурно-информационный анализ методов моделирования динамических систем. Математическое моделирование. Численные методы решения систем дифференциальных уравнений. Разработка структуры програмного комплекса для анализа динамики механических систем.
  
  дипломная работа [1,1 M], добавлен 14.05.2010
  

• Математическое моделирование

  Изучение современных принципов, подходов и методов моделирования сложно формализуемых объектов. Решение задач структурной и параметрической идентификации. Характеристики вычислительных систем как сложных систем массового обслуживания. Теория потоков.
  
  курс лекций [2,3 M], добавлен 18.02.2012
  

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

  Возможности среды программирования delphi при разработке приложения с визуальным интерфейсом. Разработка спецификации программного обеспечения и на ее основе кода программного продукта. Отладка программы "трассировкой", ее тестирование и оптимизация.
  
  курсовая работа [501,4 K], добавлен 07.12.2016
  

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

  Математическое моделирование. Изучение приёмов численного и символьного интегрирования на базе математического пакета прикладных программ, а также реализация математической модели, основанной на методе интегрирования. Интегрирование функций MATLAB.
  
  курсовая работа [889,3 K], добавлен 27.09.2008
  

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