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

• Автор: Басова, Алина Викторовна
• Шифр специальности: 05.13.18, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Ростов-на-Дону
• Количество страниц: 126 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА 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 Выводы.
ЗАКЛЮЧЕНИЕ.
Библиографический список
ВВЕДЕНИЕ
Актуальность


ПбГТУ, Санкт-Петербург, ), на XXX юбилейной международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (1Т+8Е’)» (Украина, Ялта-Гурзуф, ), на VI международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (МГАПИ, Москва, ). Публикации. Результаты диссертации отражены в 9 печатных работах. Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 1 наименования и двух приложений. Содержание диссертационной работы изложено на 0 страницах, в том числе рисунков, таблиц. Во введении обоснована актуальность диссертационной работы, сформулирована цель работы, приведены сведения о научной новизне и практической значимости, апробации диссертационной работы, дано краткое содержание основных разделов диссертации. В первой главе описаны математические модели нелинейных транспортных и распределительных задач с вогнутыми функциями стоимости. Дан краткий анализ существующих методов решения нелинейных транспортной и распределительной задач. Изучены процессы эволюции в живой природе, представляющие интерес в аспекте генетических алгоритмов. Проведено теоретическое исследование существующих генетических операторов и схем селекции с целью изучения возможности их применения в разрабатываемых алгоритмах решения транспортной и распределительной задач. Во второй главе представлен разработанный генетический алгоритм решения нелинейной транспортной задачи. Описаны способ кодирования решения и процедура инициализации начальной популяции. Приведена оценка быстродействия разработанного алгоритма. Предложен модифицированный генетический алгоритм решения задачи, в котором использованы идеи моделирования макроэволюции. В третьей главе разработана математическая модель задачи оптимизации межцеховых перевозок на предприятии с разветвленной сетью внутризаводских грузопотоков, являющаяся распределительной задачей. Предложен генетический алгоритм решения нелинейной распределительной задачи. Разработана процедура инициализации начальной популяции, ориентированная на специфику решаемой задачи. Приведена оценка быстродействия алгоритма. В четвертой главе сформулированы цели- экспериментального исследования. Проведено тестирование разработанных методов с использованием математического моделирования и вычислительного эксперимента. Обосновано применение данных методов и комплекса проблемно-ориентированных программ для решения прикладных задач. ГЛАВА 1. Среди приложений математического программирования большое место занимают проблемы производственно-транспортного типа. Это задачи распределения заказов между предприятиями с учетом затрат на производство и транспортных издержек; размещения производства, складов и технических средств; проектирования сложных сетей и объектов (дорог, проду кто проводов, тепловых и электрических сетей); рационального распределения грузопотоков между различными видами транспорта. Вычислительные сложности, возникающие при решении производственнотранспортных задач, зачастую связаны с их большой размерностью, многоэкстремальностью, наличием дискретных переменных [1]. Рассмотрим задачу минимизации вогнутой целевой функции на транспортных многогранниках различных типов. Если соединить отрезком прямой любые две точки, принадлежащие графику вогнутой функции, то данный отрезок будет лежать целиком не выше графика самой функции. Если вторая производная непрерывной и дифференцируемой функции во всех допустимых точках отрицательна, то такая функция является вогнутой. Па практике вогнутость целевой функции связана прежде всего с так называемым законом экономии от масштаба, в соответствии с которым удельные затраты на транспортировку продукции убывают с ростом объемов перевозок [2] (Рис. Указанный график может описывать стоимость транспортировки некоторого груза, при перевозках больших партий которого можно получить определенную скидку с номинальной цены. При этом целевая функция имеет вид у(х)=Аха, где А- константа, а а<1. Второй причиной, обуславливающей вогнутость целевой функции, является наличие фиксированных доплат. Рис 1. И2 - стоимость текущих затрат. Зачастую в реальных условиях может возникнуть комбинированная задача, объединяющая оба описанных случая (Рис 1.