Математика / 5. Математическое моделирование

УДК 519.876.5

к.т.н. Мохов В.А., магистрант Туровский Ф.А.

Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова, Россия

К вопросу о единообразии постановки некоторых задач дискретной оптимизации

 

В последнее десятилетие существенное развитие получило научное направление, связанное с применением популяционных алгоритмов (или агентных метаэвристик) [1, 2].

Данные алгоритмы нашли широкое применение в решении оптимизационных задач, общая постановка которых предполагает нахождение допустимого множества решений [3]:

                                               ,                         (1)

где D – является гиперкубом,  – искомое оптимальное решение,  – значение целевой функции, f – вектор-функция, представленная следующим образом:

,

.

На практике множество решений (1) может быть конечным, но его мощность часто настолько велика, что методы перебора в решении указанной задачи становятся неэффективными. При этом имеется ряд задач из различных предметных областей, для которых существует актуальная востребованность в их решении: создание траекторий космических перелётов с использованием гравитационного маневра [4], организация перевозок товаров с ограниченным сроком годности [5], маршрутизация в распределённых программно-конфигурируемых сетях [6] и некоторые другие.

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

Рассмотрим задачу прокладки маршрута между двумя удалёнными планетами p0 и pn в комическом пространстве. Примем во внимание, что для получения дополнительного разгона (и сокращения издержек по расходу топлива) за счёт известного «эффекта пращи» [7] полёт космического аппарата проходит мимо n-1 промежуточных планет с целью выполнения около них соответствующих гравитационных маневров. Полёт будет проходить на протяжении T (T≤n) временных интервалов (каждый из которых соответствует перелёту между двумя планетами pj и pj+1). Абстрагируясь от деталей, будем считать, что переменными являются усреднённые значения собственной скорости космического аппарата  на интервале t и скорости, полученной дополнительно  в начале этого периода. Также предположим, что для каждого временного интервала  известно неотрицательное значение снижения скорости .

В соответствии с техническими требованиями, в каждом периоде собственная скорость космического аппарата должна быть не менее  и не более единиц измерения, а интервал возможного изменения дополнительной скорости располагается соответственно между  и . Логично предположить, что эти параметры неотрицательны (скорость должна быть достаточно велика, чтобы не возымел эффект падения космического аппарата на одну из планет). Ради простоты будем считать, что в начале межпланетного перелета собственная скорость задана положительной константой из интервала , а первый импульс дополнительной скорости можно получить, только начиная с маневра около планеты p1 (т.е. в начале 2-го периода). Также предположим, что известны некоторые вогнутые функции  и , первая из которых определяет длительность времени межпланетного перелёта в периоде t, (или длину траектории от pj до pj+1), а вторая – средний объём расхода топлива в единицу времени (или на единицу расстояния) в зависимости от . Важно отметить, что указанные функции имеют соответствующие ограничения  и  снизу и  и  сверху на области допустимых значений.

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

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

,

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

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

Литература:

1.     Карпенко А. П. Популяционные алгоритмы глобальной поисковой оптимизации          //Обзор новых и малоизвестных алгоритмов// Приложение к журналу «Информационные технологии. – 2012. – №. 7. – С. 1-32.

2.     Скобцов, Ю. А. Метаэвристики : монография / Ю. А. Скобцов, Е. Е. Фёдоров, Донец. нац. техн. ун-т, Донец. акад. автомоб. трансп.– Донецк : Ноулідж (Донец. відділення), 2013.– 426 с.

3.     Карпенко А. П. Современные алгоритмы поисковой оптимизации //Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. НЭ Баумана. – 2014. – 446 с.

4.     Culler, Glen J., Fried, Burton D., Universal Gravity Turn Trajectories // Journal of Applied Physics, vol.28, no.6, pp.672-676, Jun 1957.

5.     Создание социально-ориентированной системы управления качеством транспортных услуг //Транспортное дело России. – 2010. – №. 12. – С. 200-203

6.     RFC 4271. A Border Gateway Protocol 4 (BGP-4).

7.     Белоусов С. В., Ивашкин В. В. Анализ траекторий перелёта от земли на геостационарную орбиту с гравитационным маневром у Луны //Москва. – 2012. – Т. 24. – С. 27.