автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Математические модели, методы и проблемно-ориентированные системы дробно-линейной оптимизации

Академия наук Украины Ордена Ленина Институт кибернетики имени В. М. Глушкова

На правах рукописи

СОЛОМОН Дмитрий Ильич

УДК 519.852.67:330.115

МАТЕМАТИЧЕСКИЕ МОДЕЛИ, МЕТОДЫ И ПРОБЛЕМНО-ОРИЕНТИРОВАННЫЕ СИСТЕМЫ ДРОБНО-ЛИНЕЙНОЙ ОПТИМИЗАЦИИ

(на примере задач планирования автомобильных грузовых перевозок)

05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Киев 1992

Работа выполнена в Институте математики с Вычислительным центром Академии наук Республики Молдова.

Научный консультант: член-корреспондент АН Украины,

доктор физико-математических наук, профессор ШОР Н. 3.

Официальные оппоненты: доктор физико-математических

наук, профессор ЕМЕЛИЧЕВ В. А.,

доктор технических наук ЮН Г. Н.,

доктор экономических наук СУСЛОВ О. П.

Ведущая организация: Центральный экономико-математический институт Российской АН.

Защита состоится «-» - 19 г. в

часов на заседании специализированного совета Д 016.45.03 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу:

252207 Киев 207, проспект Академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

Автореферат разослан «--»

Ученый секретарь специализированного совета

РЫБАК В. И.

ОБЩАЯ 1&?АКТЕН:СГ>1КА РАБОТЫ

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

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

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

ванных систем дробно-линейной оптимизации перевозочных процессов.

Вопросами оптимизации и моделирования на AT занимаются уже более 30 лет. Taraie известные ученые, как A.A. Бакаев, Б.Л. Геронимус, В.А. Жгтков, К.В. Ким, B.C. Михалевич, С.А. Панов, И.В. Романовский, Н.З. Шор, Г-Н. Юн и другие внесли существенный вклад в развитие математических методов, экономико-математических моделей и информационных технологий планирования и управления перевозочными процесса;.».

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

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

- исследование задач ДЛП блоча--диагональной структуры и разработка декомпозиционных алгоритмов их решения;

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

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

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

- анализ и систематизация математических методов и программного обеспечения репен^я задач оптимизации перевозочного процесса на AT;

- разработка информационных технологий моделирования транспортных сетей (ТС) и расчета кратчайших расстояний;

- разработка комплекса зкокомико-математических моделей оптимизации структуры подвижного состава и грузовых перевозок АТОП;

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

- разработка математических моделей и алгоритмов закрепления маршрутов за автотранспортным предприятием (АТП);

- разработка математических моделей и алгоритмов решения задач составления сменно-суточных заданий (ССЗ) по заявкам постоянной клиентуры;

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

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

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

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

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

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

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

Связь с пмтахи научит: исследований. В основу исследований по данной проблема были полозкены результаты научно-исследовательских работ, проводимых автором по темам "Разработать систему экономико-математических моделей оптимального прогнозирования развития и размещения общественного производства Молдавской ССР на перспективу" (1980 - 1985 гг.) и "Разработать математические модели и методы решения нелинейных оптимизационных задач планирования и управления в многоуровневых социально-экономических системах" (1936. - 1990 гг.), а такяе в рамках хоздоговорной работы с Министерством транспорта Республики Молдова "Разработка математического обеспечения (модели, алгоритмы и программы) оптимизации перевозочного процесса на автомобильном транспорте" (1937 - 1990 гг. ).

На-цчг'ю новизну диссеутции представляют . следующие основные результаты, которые выносятся на защиту:

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

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

- декомпозиционные методы и алгоритмы решения различных классов задач ДЛП;

- информационная технология и системы MÏS. KRS и SETRAZ моделирования ТС, расчета кратчайших расстояний и решения сетевых транспортных задач с линейными и дробно-линейными функционалами;

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

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

- кокплэкс матэматлческих модэ^ой, ялгоритмоп и прогреем (система РСР) определения голевого клиентурного плана грузопг-: перевозок;

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

- математические модели и алгоритмы решения задач закрепления маршрутов за АТП и выбора оптимального подвкгиого состава для выполнения перевозок;

- система БЮЕКА оперативного планирования и управления междугородными автомобильными перевозками массовых грузов;

- автоматизированное рабочее место диспетчера грузовых перевозок АЯМ СР;

- математические модели и алгоритмы решения задач кольцевой маршрутизации, а такте системы АЬРАХ и ИКР оперативного планирования и управления автомобильными контейнерными перевозками:

- модификации параметрического метода и эффективные алгоритмы типа Кармаркара - Дикияа решения задач ДЛП общего вида;

- декомпозиционные методы решения задэт ДЛП, основанные на схемах разложения по переменным и ограничениям в сочетании с методом обобщенного градиентного спуска (ОГС);

- декомпозиционные метопы решения задач обобщенного ДЛП, основанные на схемах разложения по ограничениям, принципе Корнай -Липтака и субградиентных методах;

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

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

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

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

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

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

Практическая реализации результатов работы. Основные результаты работы в виде проблемно-ориентированных систем внедрены в отраслевом Вычислительном центре (ВЦ), в Производственном объединении (ПО) "Мекавтотранс" и непосредственно на производственных объектах Министерства транспорта Республики Молдова (Минтранс РМ).

Основные внедрения:

- алгоритм и программы на ЕС ЭВМ для решения задач маршрутизации междугородных перевозок массовых грузов (ВЦ и Управление грузовых перевозок Минтранса РМ. 1980 г.);

- математическая модель, алгоритм и комплек. программ определения оптимального плана закрепления клиентуры за автохозяйствами (ВЦ и Управление грузовых перевозок Минтранса РМ, 1982 г.);

- математическая модель, алгоритмы и программы на ЭВМ- для решения задач оптимизации структуры подвижного состава автопредприятий республики (ВЦ и Управление грузовых перевозок Минтранса РМС 1984 г.);

- система оперативного планирования и управления междугородными автомобильными перевозками (Управление грузовых перевозок Минтранса РЫ, 1988 г.);

- моделирование транспортной сети и расчет матрицы кратчайших расстояний (ВЦ Минтранса РЫ, 1990 г.);

- математические метода и программное обеспечение решения задачи оптимизации структуры подвижного состава автотранспортных предприятий (ВЦ Минтранса РЫ. 1990 г.);

- автоматизированное рабочее место диспетчера грузовых перевозок (ПО "Бендертранс" и АТП Минтранса РМ, 1990 г.);

- автоматизированная система планирования и управления авто-

мобильными контейнерными перевозками (ПО "Мекавтотраг.с", 1991г.);

- система генерации маршрутов (СИГЕМА) с пакетом прикладах программ для компьютера, работающего в составе вычислительной сети (ПО "Межавтотранс" и АТП Минтранса РМ, 1991 г.).

Основные положения диссертационной работы докладывались и обсуждались яа различных республиканских и всесоюзных научных конференциях: на 2-й и 3-й Всесоюзной сколе-семинаре "Проблемы управления и моделирования социально-эконсмичес-кого развития региона" (Свердловск, 1978, 1980 гг.); на республиканской конференции "Проблемы создания и внедрения асу и средств вычислительной техники в условиях улучшения планирования и совершенствования хозяйственного механизма" (Кипикев, 1350 г.); на Всесоюзной школе-семинаре "Дискретная оптимизация и ее приложения, з том числе экономические" (Кишинев, 1933 г.); па 2-й Всесоюзной сколе-семинарс "Оптимизация и ее приложения к экономике" (Ашхабад, 1984 г.); на IX, X и XI Всесоюзной иколз-с::мпозпумэ "Системы программного обеспечения решения задач оптимального планирования" (Минск, 1986 г., Нарва, тсес г., Кострома, 1920 г.); на Республиканской научно-практической конференции "Применение экономико-математических методов и ВТ в планировании и управлении народным хозяйством МСС?" (Кишинев, 1923 г.); на Всесоюзной конференции "Метода математического программирования и программное обеспечений" (СвердлсЕск, 1989 г.); на Республиканской научно - практической конференции "Проблемы математизации народного хозяйства НССР" (Кишинев, 1990 г.).

ОийбШШУ:*. По результатам исследований опубликовано 35 научных работ в Известиях АН Ш (серия технических и физико-математических наук; серия "Математика") и в трудах Института математики с ВЦ АН ИЛ (серия "Математичеизю исследования"). В издательстве "Штиинца" в 1929 году вышла монография в соавторстве с Шором Н.З.

Структура Оиссернации. Диссертация является самостоятельно выполненным научным трудом и состоит из введения, семи глаз и приложения, содержит 17 рисунков, 5 таблицы и список литературы, включащий 205 наименований. Основное содержание работы изложено на 346 страницах машинописного текста.

С0ДЕР2АНИЕ РАБОТЫ

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

.Первые три главы диссертации посвящены вопросам разработки математических методов и эффективных вычислительных алгоритмов решения задач ДЛП, которые встречаются при оптимизации перевозочного процесса на AT. В первой и второй главах приводятся декомпозиционные методы решения общей задачи ДЛП, а в третьей - различные алгоритмы решения задач ДЛП транспортного типа. По некоторым алгоритмам составлены программые модули, которые сданы в ГосФАП СССР и использованы в разработанных системах оптимизации на АГ.

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

С(Х) n п

min (F(x) =-= f Е с, сп) / ( £ d, х. + d.));

X е R(r) D(x) 3=1 3 J ° 3=1 3 3 °

n ___

R(X) = С x: £ X3 = b±, i = 1.m; X} » 0, 1 = 1,11 ),

d которой предполагается, что D(x) > О для любого х е Rix), а многогранное выпуклое множество R(x) ограниченно.

Для решения задачи Pi разработаны различные алгоритмы, которые условно можно разделить на пять груш: модификации симплекс-методе, метод "линеаризации", параметрический метод, полиномиальные и декомпозиционные алгоритмы. Ниже приведем некоторую мо-■дификацию алгоритма параметрического метода. Для этого рассмотрим

задачу Р2: найти min { Z(x, X) = С(х) - X D(x) ). х е R(x)

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

Предварительный (О-й) шаг. Берем \ = ц0= 0 и находим оптимальное решение задачи Р2 при X = p.Q.

Общий (к-й) шаг. Пусть имеется некоторый оптимальный план Xй"1 задачи Р2, полученный на предыдущем шаге алгоритма. Тогда:

- определяем значение параметра Я = ^ = 1);

- находим оптимальное решение & задачи Р2 при к -

- если Т(з^) = то план х* является оптимальным для задачи Р1.

Далее приводятся эффективные алгоритмы решения задач Р1, основанные на модификациях алгоритмов типа Кармаркар - Ддакин. Если ввести обозначения х = (х., х ), с = (е., с_, ...

1с- П 1С.

.... сп>, й = (в,, сз^, ..., йп), ь = , ьг, .... ьш;, к = (х^, \г, .... Хт), А = то общая схема таких алгоритмов кмзет

вид.

Первоначальный (Ой) шаг. Пусть х° > О, удовлетворяющее Аг°= = &, будет первоначальным допустимым решением задачи Р1.

Обедай (к-й шаг). Пусть Iх - некоторое решение, полученное на предыдущем шаге. Тогда:

- определяем Вк = й1а£(з^, х£. .... х^);

- находим (АВ^Г^АЕ^. (С(х*)й -

- вычисляем новые значения ¿г1"1 > О по формуле

- - А?К.)

а* - й

!кГСсЛй - L(3*)c -где 0 < R < 1.

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

С(х) р Р

Шп (?(х) =-- ( Z с х + cQ) / ( Z d. х. ♦ d0 )),

х € Ы(х) D(x) 3 3 0 J=1 3 3 0

И(х) = (x: ZA3x3* Ь. В^ Zj $ by i = TTi: x^ > 0. з = TTpJ.

где Су йу х} - вектор! размерностью пу, Ъ - и-мерный вектор; bj - вектор размерностью п^; А^ - матриц размерностью ш i

Sj - матрица размерностью m^ х n^; с0, dQ - постоянные числа. Для задачи РЗ построим функцию Лагранка

L(x,и) = (С(х) + (и, Ъ -ß^AjZj)) / D(x)

и рассмотрим задачу пах ( Ъ* Си) = min L(x.u) ). где и 5-О х г S(x)

u = fu,. ... , ит) - множители Лагранжа для связующих ограничений, a S(x) = (х: BjXj $ b^, j=77p: х3 z 0. з=Т~р).

Тогда задача РЗ сводится к решению задачи max L*(u). На

и > О

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

1. Решить задачу я in L(x,u) при фиксированных значе-

X € S(X)

киях и = ut. Для решения этой задачи применим параметрический метод и получим следующую блочную задачу параметрического линейного программирования: найти

min ( £ (с. - и* А. - X ä.) xj. х € S(x) 3=1 3 3 33

На каждом шаге параметрического метода при фиксированных

значениях \ решаются р задач вида: найти

min ( (с. - иь А. - \ dj хJ,

X € SjfXj) 33 33

где SjCXj) = fay BjTj $ bj, х^ ъ О ).

2. Определить значения обобщенного градиента функции Ь*(и) в точке иь по формуле Gfu*; = Г (Ъ - £ А. х*(и*)) / Dd'fu*)) ),

3=1 3 3

где х*(иъ) - оптимальное решение задачи min L(х,и*).

х € S(х)

3. Вычислить новые значения

ut+1 = max ( и, иъ + 7it+1 G (их) ),

где - величина шага.

Для решения задач ДПП с сепарабельными функционалами

I °зхз* с°з

РА: найти min I F(x) = У -— ).

xtH(x) £

ю

Р5: найти шШ ( F(x) = глт --— )

х <= U(x) з dj Xj c^

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

методы. Тогда ка t-м шаге субградиентного метода необходимо

решить р задач вида

- сз х3 * °3 t

n(n {--— u Ajc. ).

X € S](X3) djXjt cfij

Далее рассматривается задача дробно-выпуклого программирования Рб: найти

С(х.у) _

min С Fix.у) = - : /АХ,у) $ О, 1 = i.m: ).

D(x,y) 1

где х = Сх:, хг, .... хп) е ir; у - (уу, у?, .... уkJ е гг. для решения которой используется схема декомпозиции по переменным.

Обозначил через М(х,у) множество значений переменных (х,у), удовлетворяющих ограничениям задачи Рб, и предположим, что для всех (х,у) е М(х,у) С(х,у) > О и D(x,y) > О, а функции С(х,у),

-D(x.y), f±(x,y), t = TTrä, - выпуклые и необязательно дифференцируемые по совокупности переменных г и у. Тогда функция Р(х,у) является квазивыпуклой на выпуклом множестве Н(х,у). Построим функцию Лагранка задачи Рб по формуле

L(x,y.u) = ( С(х,у) + | и. f.(x,y) ) / D(x,y), 1-1 1 1

где и = fu...... и ) - соответствующие множители Лагранжа.

Для задачи Рб выполняются- необходимые и достаточные условия Куна - Таккера и существует пара ((х*,у*),и*), которая является седловой точкой функции L(x.y.u). Для решения задачи Рб используется схема декомпозиции по переменным, для чего фиксируются

переменные х =■ х и рассматривается задача Р7: найти

С(х,у) _ _

min Г ?(х,у) = —-— : f.(x.y) < О, i = i.m D(x.y) 1

Для тех значений х, для которых разрешима задача Р7, определим функцию OfxJ - min _ F (х. у), где R(x) - множества

У € R(X)

значений переменных у, удовлетворяющих ограничениям задачи Р7.

Тогда функция является квазизыпуклой на некотором выпуклом подмнокестве Если для некоторого х е V выполнено условие

Слег.тера, то обобщенный градиент функции Ф(х) в точке х = х вычисляется по формуле = {£(х,у(х)), где Ъ - функция

Лаграяха задачи Р6; у(х) - одно из оптимальных значений в задачи Р7; и = (и^ - множители Лагракка задачи Р7, полученные в соответствии с теоремой Куна - Такхера; ¿^(х.уСх)) - проекция такого обобщенного градиента функции Кг,и) = Кх,у,и) на подпространство Е®, у которого проекция на подпространство Е* равна нули

21 У

(обобщенный градиент берется в точке г = (х,у(х))).

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

- решить задачу Р7 при х = 5* и определить вектор мнохителей Лагранжа и(х= { и±(х*) > :

- вычислить субградиент функции Ф(х) в точке х = Xх \

- определить новые значения х|!+1 = х* - где ?г1.+1 - величина шага.

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

Т8: найти ш1п Т(х,у). (Х.у) € Б(х.у)

Р9: найти т.1п Т(х.у),

(Х.у) € Щх,у)

а функционал ?(х,у) и мн^дества Б(х.у) и М(х,у) имеют вид

Р(х,у) = ( £ с, х. + с у ) / ( £ <3, х, + й у ),

3=1 33 3=1 ^ 3

р

М(х,у)= ( (х,у): хз + р0У ,

вз Х1 * * 3 = у * хз * 3 ~ ^ Б(х.у) = { (х.у): В3 х3 + Р3 У « Ь3, з = Тп:

y > О, Х} £V. 3 = 1 .п. },

где с, й, у - векторы размерностью k: F0 - матрица размерности и х к: - матрицы размерностью z к.

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

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

Для решения задач Р4 и Р5 мохет быть использована схема декомпозиции типа Корнай - Липтака с последующим использованием субградиентных методов. Для этого представил вектор ресурсов в виде равенств

Ъ = + гг* ...+ zn. Тогда задачи Р4 и Р5 разлагаются на р подзадач типа РЮ: найти

сз xi * со

min (S.(x.) =- ; А. х. = z., Bjc. i Ъ., х. i О }.

J J rf г r1 J J JJJ JJ QJ * O

Пусть x^z ) - оптимальнее решение задачи РЮ при заданном Zy a í u'iZjJ ) - оптимальные значения мнокителей Лагранха, соответствующие связующим ограничениям, где функция Лагранза определяется по формуле

VjV Wi* 2jV b3v3 + °0

ЪАх.. и , у ; ---.

iiii a3x3>d0

Для задачи Р5 определим функцию Ф(г) = таг ФJxUz.)). Так

i 333

как Ф^Гх*(zj; являются строго квазивыпуклыми, то функция ,Z/(z)

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

g$(z) = (g3(z3) = ( u*3(z3) / (d3 x'3(z3) + a0))).

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

р .

Относительно задачи рл функция <S>(z) = £ QAxaz.)) не

3=1 J 3 3

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

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

В завершении второй главы рассматриваются некоторые классы обобщенных задач дробно-Еыпуклого программирования, в которых система ограничений имеет блочно-диагональную структуру со связующими ограничениями. Пусть имеются р групп переменных i, = ( i',

р П.. ГЦ п

of:,..., хе к J, образующих вектор х - (хл, ..., х ) е R , где 3 р Р

п= £ п.. На множестве каддой группы переменных х. определяются

3=1 3 3

следующие непрерывные функции: qy ф^, ff*, С^: R 3 —» к.

Рассматривается задачи Р11: найти min Р (х), г = 771,

__х € S(x) г

в которых функции Рг(х), г = 1,4, определяются по формулам

JiW W

F. (х) = —-; F (х) = max-;

I Ф/rJ 2 a W

3=1 J 3

p q3(x}) p y3(x3) F-(x) = J - ; F,(x) = П -•

3=1 w У w

а множество S(x) системы ограничений имеет блочно-диагональную структуру:

S(x) = (x: £ nL.(x.) s a., i = i.n;

3=1 J 3

Q](x.) $ Ъ1.. l = 7X: 3 = T7p: J.

j л л ^

1 q-t -

гдо a = fa1.....Gm; г к b.= , .... b^ J e R J, J = Up.

а функции (i=Um). Q^ (1=1Tq}) - выпуклы.

В обдом случае задачи Р11 являются мцогокхстрсмальнкмя и для их ревония необходимо использовать методы глобальной оптимизация. Однако если для функций i?i(xi) и ф^я^ потребовать выполнении некоторых дополнительных услотй, то функционалы Гу(х), Fr,(x), Р3(х) и FJx) будут квазютшуклыга, а задачи Р11 станут одноок-стремальнымл.

Пусть выполняются сл<?ду?гке условия: все функции yjz^ -выпуклы, о Ф/г^ - вогнуты; » О и '\>}(хл) > О для" любого

х с S(x); 'fjx^) = / является одновременно

монотонно возраставгсг-гл или монотонно угыважда'л на Sfx;. Тогда

функции F^.(x), r=T7I, являются кзазиЕыпуклькг,' на ifTj.

Таким образом, при дачных предположениях г^дачи Р11 являются .задачей КЕазшглпуклога програжировашт, в которых > "обходимо минимизировать относешш внпувлых и вогнута: £ушсц™онадсв на 1.210-sscr_-j ограничений специальной структуры. Для пх ресенкя щиво-дятсл дексгаозяциоппыо алгоритмы, оснозаатго па схеме разложения по огргакче»пям и принципе Корная - Лжгг&ка с прюеиенаем субгра-ДНЗПТЕЫ7. методов.

В разделе задач ДЛП транспортного тага рассматринезтся следущиэ задачи:

n п ип

Р12: найтл Шп (?(х) = £ £ с ^ / £ V d.^J. X J(X) 1=13 = 1 3 1=13 = 1

n

U(x) •-=■ f x1;J ^ alt 1 = i.-a;

j=1

n _____

£ x = 3 = i.n; x. , >■ 0, 1 = i.n; 3 = i.n ); X—1

P13: пайгл ntn F(x), x с Qfx;

Qfzj = f it3: Д fl} xi3 i by f = T^;

£ xL3 = a±, 1 =. i.m; z13 > 0, i = i.m; 3 = i.n );

m n n

s £ C1Aa + l с A} + С ¿=1 3=1 13 13 i=1 ;rj . u

P14: найти nln i- );

(x.y) € S(x.y) m n n

E 1 * I <î y t ûQ

i=ij=i 13 13 3=1 3 3 u

n __ m _

S(x,y) = (Xiy y3:Zz±3 = 1 - 1 ï.^ xi3 * У y 1 = i.n»

__f a,.

a i y « L 3 = i.n; xia =\ 1 — — J; 3 3 3 13 I 0 , 1 = 1.ш: з = 1.n

P15: найти nin f + ? £ p. jr.,

x с tffxj 1=13=1 13

J.

Для решения задач P12 - P15 разработаны алгоритмы, основанные на методах потенциалов, покоординатного спуска, параметрического метода, декомпозиционные алгоритмы принципа Данцига - Вулфа и субградиентного метода. Для задачи Р14 приводится также прибли-езнный алгоритм метода вектора спада. .

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

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

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

Рассматриваются вопросы информационной технологии моделирования ТС, расчета кратчайших расстояний и решения оптимизационных задач на ТС. Процесс моделирования ТС содержит две группы задач. В первую группу входят задачи построения информационных моделей на ЭВМ для хранения транспортной сети. Каждая информационная

модель ТС вклшаэт структуру и содержание файлов данных и предназначена для хранения параметров ТС в памяти ЗВМ и ее зашей в базу данных.

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

* Система KTS предназначена для автоматизации пропсса моделирования ТС автомобильных дорог, расчета матриц и таблиц кратчайших расстояний и является основным инструментом подготовки информации о кратчайших расстояниях ео всех приведенных системах оптмизацки перевозочного процесса на AT. С помощью систе?.и HI5 смоделированы различные транспортные сем от республиканской ТС автомобильных дорог до районных и городских ТС.

Система KR3 слугят для расчета кратчайших расстояний между пунктами погрузки-разгрузки па базе смоделированной .ранее ТС, базовой матрица кратчайших расстояний и таблицы привязки, а та:са для обеспечения импорта-экспорта файлов мезду системам HS DOS, MTS и dBASE. Она является промежуточным этапом мезхду системой KTS и прикладными системами, в расчетах которых используются кратчайшие расстояния.

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

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

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

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

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

Д ЪЦ < V PiV 1 = f Да ^ V hJo- k = Т^; »

а R3 Tr3 Öt3 ^ r. R3 Tr3 ^

Z Z Z —r <B- s Z Z Pl3 « P: 3=1 r=i t=i D 3=1 r=i t=i

R. T . E, T .

n 3 r3 n 1 rj

Z Г Z < S; Z Z Z ^ > П;

3-1 r=i t=1 bJ 3=1 r=1 t=1 J J

m Ci n p n

z -- Z y13 Z -- Z z i Kl

1=1 D p±70 3=1 1J 1C=1 P^cT0 3=1 *3-

TrJ

£ P?3 <3. * ^3 ' г = ^3= 3 = ^

R3 Tx-3

r=1 t=1

-f«.« E13 h3L- 1=1 J=1>n:

_ _

^ <3 - 2k3 * C*3 Tk3 k=1,p: J=1'n;

? 0. г=ТТтг3: i^TTR^: 3=T7ri;

D Ö13 Pi To « Ухз * D T« Pi ToD Физ ^3 ^ To- k=T7*!

необходимо найти

п п3 ТгЗ „ „ П т с1 5н

тт ( р, = Е Е Е <, аГ, + Е Е :-У13 +

1 3=1 г=1 *=1 " "3 3=1 1=1 о р т0 13

п р ^к ^ п *3 ГГЗ ,

* Е Е г-Г- 2кз ;; «"^г- & ^ £ Р^

3=1 к=1 О ^ ^ 3=1 Р=1

п Н3 ТгЗ

П(П г р3 = р, / р2 ): Ю г Р, - Д £ £ ^ <3

П «3 ТгЗ ^3

таг { р4 / + Е Е Е <з ;

° 3=1 г=1 4=1 I) <г\ и д

я ГП р ^ '

шх г ? / № + Е Г Е ---у13 + Е --2к ;;

3=1 1=1 5 Р1Т0 в [уг0 113

гдэ" М1 и ?1с - количество транспортных единиц автомобилей 1-й марки и прицепов к-й марки, которые необходимо распределить; р1 и - коэффициент поставки автомобилей 1-й марки и прицепов к-й марки; 70 - коэффициент выхода на линии новой техники: А^ - объем транспортной работы при перевозке грузов г-й линии з-го АТП? и ^ - количество транспортных единиц автомобилей 1-й марки и прицепов 1<-й марки, тлеющихся в з-м АТП; р2^ - производительность работы г-го транспортного агрегата при перевозке грузов на г-й линии з-го АТП; а^ - коэффициент, равный единице, если автомобиль 1-й марки з-го АТП входит в состав г-го агрегата, г-й линии, и равный нулю в противнем случае; Ъt;¡ - коэффициент, указывающий количество прицепов или полуприцепов к-й марки з-го АТП, входящих в состав г-го агрегата 1-й линии; х^ - количество транспортных единиц 4-го агрегата, используемых при" перевозке грузов н£ г-й .линии з~го АТП; у и - количество распределенных автомобилей 1-й марки п прицепов к-й марки з-му АТП; и г,,^ - коэффициент выпуска на линию автомобилей 1-й марки п прицепов к-й марки автомобиля з-го АТП; В.^, 71;) и ф^, срк^ - минимальное и максимальное количество автомобилей 1-й марта и прицепов к-й марки, которые мохно распределить з-му АТП; - остаточная балансовая стоимость г-го транспортного агрегата г-й линии З-го АТП; с± :: ^ - оптовые цены автомобилей 1-й марки и прицепов

к-й марки; з^. ^ и а^ - себестоимость, прибыль и доходы выполненной транспортной работы г-м агрегатом при перевозке груза 1-й линии з-го АТП; а^ - коэффициент выхода на линю г-го агрегата г-й линии з-го АТП; Ф1 - общие основные фонда на конец года; Ф0 - основные фонда на конец года без учета подвижного состава; К - выделенные капитальные вложения на приобретение новой техники; В - максимальная остаточная балансовая стоимость ПС; Б - максимальные затраты на перевозку грузов; Р - максимальный объем транспортной работы; П - минимальная прибыль; I) - количество календарных дней в планируемом периоде.

Математическая модель М1 мохет быть использована для решения еле дующих задач

1) определение оптимальной структуры подвижного состава;

2) распределение поставки новой техники;

3) определение оптимального плана использования подвшяого состава на линиях перевозки;

4) перераспределение подвигного состава между АТП;

5) определение плана грузовых перевозок.

Для решения любой из перечисленных задач используется общая модель Ы1. Моделирование конкретной задачи осуществляется с помощь» изменения значений правых частей системы ограничений модели и выбора необходимого критерия оптимальности. Линейные задачи модели М1 решаются пакетом ЛП-АСУ. Для решения дробно-линейных задачи- применяется метод "линеаризации" или параметрический метод сведения ее к линейным задачам с последующим применением пакета ЛП-АСУ.

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

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

"почасовых" автомобилей введем следующие обозначения: аА -квартальные потребности в автомобилях по 1-й заявке: квартальные провозные возможности з-го АТП; x±J - количество автомобилей з-го АТП, выделенных для обслуживания клиента 1-й заявки; di3 ~ нулевые пробеги между з-м АТП и пунктом расположения клиента i-й заявки; c±i - экспертная оценка производственно-договорных связей з-го АТП с клиентом i-й заявки.

Тогда математическая модель имеет вид К2: найти

m Ii an n __

min ( т. Т. / т. У. с. je. ^ г V г„ =

¿¿1 ¿3?, : 3=1 Xli = 1 = 1,и;

13 * Ь3 • •1 = ^ Х13

а

Е1 ^ . .1 = 1*п; 1нЯЗ,1 = 1,и; з = 1.П }.

Модель 112 является задачей транспортного типа • с дробно-ли-иейным функционалом, для решения которой можно использовать алгоритмы метода потенциалов или параметрического метода. В случае, когда в каждом АТП можно варьировать количеством "почэсоеых" автомобилей, это даст возможность более свободного закрепления почасовых заявок без деления их объема по разным АТП. Если провозные возможности з-го АТП обозначить переменной уч, значения

У

которой находятся в некотором заданном интервале [aJf , то математическая модель И2 имеет вид МЗ: найти

ain { JJi у U : 1 = 0l' 1 = ТТ™;

J^irV7^ аз < Уз * Pj- 3 = ^ хи = { ~ ri'

Модель U3 решается по приближенным алгоритмам метода вектора спада пли обобщенного градиентного спуска.

При определении клиентурного плана грузовых перевозок для "сдельных" автомобилей формируются кольцевые маршруты, которые закрепляются за АТП по следующим моделям:

m n t , .

S4: найти viln f Е Е Е РТЛ^ X € М(Х) 1=13=11=1 3 3

U5: найти max f Е Е Е / П Е Р^« Л

X € Ы(Х) 1=13=11=1 3 3 1=13=11=1 3 3

п. t

Н(х) = (х : £ £ ^ = Ъ.а., 1 = 1,в; 13 3=11=1 3

Е ^чз 5 ъз* 3 = 1 ,п; ^з 55 1 = 1,и: 1 = 1,п! 1 = здесь" а± - квартальные объемы перевозки грузов на 1-м маршруте (заявке); - груженной пробег на 1-м маршруте; Ь* - квартальные провозные возможности з-го АТП по 1-му типу подвижного состава; Р±-> Е й13 ~ пР11БеД8Нше затраты и доходы на I ткм работы автомобилей 1-го типа подвижного состава з-го АТП при выполнении перевозок на 1-м маршруте; - объем транспортной работы, выполненный автомобилями 1-го типа подвитого состава з-го АТП на 1-м маршруте.

Линейная траиспортная задача 114 решается на минимум приведенных затрат при выполнении всех перевозок, а дробно-линейная транспортная задача М5 на максимум рентабельности перевозок. Для решения задач ¡14 к Ы5 используются метод потенциалов, параметрический и субградиентный методы. Кроме моделей М4 и 115 для составления клиентурного плана применяется поэтапный алгоритм, в котором задачи решаются для каадого типа подвижного состава в отдельности. Для решения на ЭВМ задач определения клиентурного плана разработана система РйР.

Последняя глава работы посвяцана вопросам математического моделирования и решения задач оперативного планирования и управления перевозочным процессом на автомобильном транспорте. Рассматриваются четыре взаимосвязанные мезду собой системы БЮША, АЕК СР, АБРАК и ККР. в каздой из которых решаются три оптимизационные задачи: определение кольцевых маршрутов (задача маршрутизации), закрепление маршрутов за АТП (задача закрепления) и составление сменно-суточных заданий (ССЗ) выполнения грузовых перевозок по заявкам постоянной клиентуры.

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

Приведем математическую модель построения одного (к-го)

кольцевого маршрута, удовлетворяющего заданным ограничениям. Пусть заданы М пунктов погрузки, N пунктов разгрузки и R пунктов, в которых расположены АТП. Введем обозначения: ci3 - расстояние между 1-м пунктом погрузки и з-м пунктом разгрузки; -расстояние между з-м пунктом разгрузки и i-м пунктом погрузка;

- расстояние между г-м АТП и i-м пунктом погрузки; -расстояние между з-м пунктом разгрузки и r-м АТП; К - количество всевозможных допустимых кольцевых маршрутов; х^^ - переменная, равная единице, если в k-й маршрут входит груженный пробег <i,j>, и нулю в противном случае; - переменная, равная единице, если в к-й маршрут входит порожний пробег <j.i>, и нулю в противном случае; - переменная, равная единице, если в к-й маршрут входит нулевой пробег <r.з>, и нулю в противном случае; -переменная, равная единице, если в к-й маршрут входит нулевой пробег <з.г>, и нулю в противном случае.

Кольцевой (к-й) маршрут записывается в виде последовательности

с _ г ,.1к .Je . „к . _к . .Je . Jk . ,2k , к- «т 1 "1 1 '11 ' 1 1 ••••• 1 • 1 'i/1r''

К 0 1 1131 3112 2 2 3t-1lt H3t 3trO

Тогда математическая модель решения задачи определения одного (k-го) кольцевого маршрута имеет вид Мб:

Е rf * I, i . ТЛ7; ? « I, J = ТТУ;

3=1 3 1=1 3

ff Jf

1 «i s I, i = 772; E z* $ I, з = 77У;

3=1 31 1=1 31

ft ® llr ' ft

E I Й = i; E E ^ = I!

r=1 1=1 " 3=1 P=1 Jr

2 2 2 - o. i - ТЛГ:

3=1 13 . 3=1 31 Г=1 rl

* ? 231" z ^ = o. 3 = 777?;

1=1 i3 1=1 31 r=1 зг

If ,, ff „. MB.

E Уг1~ E У^ = о, r . 777?; E E < :

J=1 " 3=1 3 1=13=1 3

M N NM

Li < Z E e « a* + E E ^ +

1 1=13=1 13 13 3=11=1 31 31

а м л «« я я л Л1,

* А А* А А ^ ^5 ^

И N к Я и ъ

Е Е ( 1 - е0) С ¿1 - £ Е Р0 ^ -

1=13=1 и 13 13 3=11=1 и 31 31

-Е Е Ро/^Ум- 2 2 Ро^г^зг 55 05

г=1 1=1 Г1 • 3=1 Г=1 и зг зг

М N . N М = Е Е О а£ + Е Е 2* ♦

к ,1=13=1 3 3 3=11=1 3 3

й и 1 1к Н Й О

+ Е Е 41 + 2 2 У2^ -► пах.

г=1 1=1 3=1 г=1 зг

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

характеризующие эффективность Еыбранного маршрута.

Математическая модель Ы6 может быть использована в декомпозиционном алгоритме решения следующей задачи комплексной маршрутизации для определения оптимального маршрута при заданных ограничениях. Введем дополнительные обозначения: - объем перевозки груза между 1-м и з-м пунктами; Аг - провозные возможности 1*-го АТП; шк - интенсивность к-го маршрута. Тогда математическая модель решения задачи комплексной маршрутизации имеет вид ИТ: кия . Е Е Е с,, а* щ.

к=1 1=13=1 13 13 к

К ( М N ИМ

Е Е Е ои 41 + Е Е а г*± ♦

ic=i li=i 3=i 3 3 3=11=1 31 31

+ Е Е fU Уг1 + Е Е fjT Ufr I

r=1l=1 " rl 3=1r=1 3 зг J

тах

»к * D13' 1 = 3 =

К' м

Е Е l/pi \ = Ар, г = T7R;

к=11=1

> 0, к = 77!; ( а%3. у^ е к = 7Х

Математическая модель М7 представляет собой обобщенную задачу ДЛП с неизвестными коэффициентами, для репения которой можно применять декомпозиционные алгоритмы. Если задача МТ имеет небольшое число ненулевых 0±3, то для ее решения используются методы декомпозиции Данцига - Вулф?.. Для более общего случая применяется алгоритм, основанный на схемах декомпозиции по ограничениям и переменным с использованием субградиентных методов.

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

п 1п ( ®(Х) = £ £ х., = а,, 1 = 77^;

1=1 3=1 13 з=1 13 1 п _____

^ х±3 = а3, 3 = 1.п; х13 ? О, х±3 = х31, 1 = 1.п; з = 1.п ).

Здесь а± - объем перевозки по 1-й заявке, /13 - порожние пробеги на маршруте (1.з); х13 - интенсивность маршрута (1.3).

Таким образом, оптимальное решение задачи ДО дает нам систему двухзвенных. кольцевых маршрутов. Одновременно с планом закольцовывания заявок в результате решения задачи М8 получаем а значения интенсивности каждого маршрута, т.е. х*3 - объем перевозки по каждому звену двухзвенного кольцевого маршрута.

Далее приводятся математические модели и алгоритмы решения задач закрепления маршрутов за АТП и выбора оптимального подвижного состава для выполнения грузовых перевозок по ним. В результате решения задачи двухзвенной кольцевой маршрутизации получаем оптимальную систему маршрутов в = (g1..... которые необходимо закрепить за АТП. В зависимости от производственной ситуации и технологии выполнения перевозок задача закрепления может быть

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

Рассмотрим модели решения задачи закрепления маршрутов, по которым перевозятся однородные грузы. Пусть заданы п АТП с провозными возможностями Ьу соответствующими общим грузополъем-ностям всех автомобилей з-го АТП. Если через ctJ обозначить коэффициент увеличения порожнего пробега при закреплении 1-го маршрута за з-м АТП, а через xi3 - объем закрепленого груза 1-го маршрута за з-м АТП, то математическая модель закрепления маршрутов за АТП будет иметь вид М9: найти

m n п _

min ( Т. У. с. je. Т. x,, = g4. 1 = i.m;

{ 2 Е с1зг13 ; Е Х1 з = *f

1=13=1 13 13 J=1 13 ■

с

Е Xt йЬу J = 1.a; XL} Z 0, 1 = I.m: J : l,n ).

При решении задачи U9 находятся объемы перевозки для каждого АТП. Конкретный тип автомобилей и их количество определяются в АТП в зависимости от закрепленных маршрутов. Для каждого з-го АТП решается следующая математическая модель. В результате решения задачи М9 для каждого з-го АТП имеем: - количество закрепленных маршрутов за з-м АТП; g^ - объем перевозки по t-му маршруту З-го АТП. Введем дополнительные обозначения: и у3ъ -

соответственно себестоимость, доходы и объемы перевозки i-м автомобилем з-го АТП на t-м маршруте; ф^ и - максимально возможные величины отклонения объема перевозки от интенсивности t-ro маршрута з-го АТП. Тогда математическая модель выбора марки автомобилей и их количество на каждом маршруте имеет вид НЮ: найти

"з аз пз шз

«юг f £ X /ЕЕ a y :

i=it=i " 1=1 t=i A

_ пз _

xE ylt < si * Ф*. .t = i,Bj; £ ylt > 83t - чф t = i,Bj: nJ « — f я:

t«i * 3 l о . i = 1.П^; t = i.Bj

Задача маршрутизации может быть решена двухэтапным методом отдельно для- каждого типа подвижного состава. Пусть заданы ю маршрутов с интенсивностями Sz> ••• » вщ и п АТП, в каждом из которых имеются tj типов подвижного состава с грузоподъем-

ностями и в количестве к^ транспортных единиц для каждого 1-го типа автомобиля. Пусть с^ - коэффициент увеличения порожнего пробега при закреплении 1-го типа подвижного состава з-го А'ГП за 1-м маршрутом; р±- экспертная оценка штрафа за отклонение от интенсивности 1-го маршрута; Ь^ - общая грузоподъемность автомобилей 1-го типа з-го АТП; и v1 - отклонения от интенсивности 1-го маршрута: - объем груза 1-го маршрута, перевезенного г-м типом подвижного состава з-го АТП. Тогда математическая модель закрепления маршрутов за АТП имеет вид М11: найти

сТ.

ш п 3 13 т

тт ( £ £ £ —— ; £ р ( и - V ) )

1=13=1г=1 3 1=1 1 1 1

при ограничениях

» ^ —

Е1уЕ 4з + и1 " У1 = 1 =

т ___

Е ^ $ Ь^, з = 1.п; г =

= (О, .... к^ с^), 1 = ТТт; з = ТГп; г = 77^;

ui * 1 = 1

При решении двухкритериальной задачи И11 можно применить

модель Н12г найти

ш п *з с13 _ п *з „ _

min С £ Е Е. —— Е Е ^ i = i.m;

1=13=ir=i 3 з=1р=1

ta ___.

0 5 ^13 s ).

где fi± ~ mod (g±, q^J, i=77m; з=Т7й; r=TTtj - максимальный объем i-го маршрута, который может быть закреплен за r-м типом подвижного состава з-го АТП.

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

много запретов, модель М12 эффективнее решать в сетевом виде.

Кроме задач маршрутизации и закрепления, при планировании грузовых перевозок решается задача составления ССЗ по заявкам постоянной клиентуры, в которых задаются минимальные и максимальные дневные объемы перевозки. Требуется распределить имещейся подвижной состав по заявкам и составить ССЗ с целью снижения затрат на перевозку и повышение доходов с обязательным выполнением минимальных дневных объемов по всем заявкам. Для описания общей математической модели решения данной задачи введем следующие обозначения: m и п - количество заявок и автомобилей; i и j -индекс заявки и автомобиля: aj и а^' - минимальный и максимальный объем работы; pLj - объем. выполненной работы (производительность); ci3 и <JLJ - затраты и доходы на единицу работы; х13 -булева переменная. Тогда общая математическая модель закрепления автомобилей для выполнения грузовых перевозок по заявкам постоянной клиентуры будет иметь вид M13i найти

min { ¿1 11 у J,|, ;

Jt Pli > °Î- 1 = ^ Д Pu Xi3 * а1' 1 =

m

1=1

-Г" - -

L О . 1 = 1.m: 3 = 1 .п

Е < U з = i.n; xi3 = { _ _ )

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

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

Для автоматизации процесса оперативного планирования и управления междугородными автомобильными перевозками массовых грузов в пределах заданного региона разработана система БШЕМА, которая позволяет организовать централизованный сбор и обработку заявок на междугородные перевозки: определить оптимальные кольцевые маршруты перевозки грузов на всей территории региона; распределить маршруты между АТП региона и закрепить оптимальный подвиж-

ной состав для выполнения перевозок по ним.

информационное обеспечение системы SIGEJA состоит из трех частей. Это информация о ТС и кратчайших расстояниях, база Еорма-тивно-справочной информации (НСИ), заявки на междугородные перевозки и провозные возможности подвижного состава.

Моделирование ТС и расчет матриц кратчайших расстояний, таблиц привязки и соответствия осуществляются с помощью систем MTS и KRS. База НСИ формируется системой SIGEMA, а заявка на междугородные перевозки вводятся и корректируются оперативно. з каждом АТП системой ABM GP. Подготовленные заявки передаются системе SIGEMA для централизованной обработки и формирования кольцевых маршрутов. На основе этой информации решается задача маршрутизации, которая состоит из следующих этапов: подготовка необходимой информации о заявках, провозных возможностях и кратчайших расстояниях; решение задачи кольцевой маршрутизации; решение задачи закрепления маршрутов за АТП; анализ и корректировка маршрутов. Разработанные маршруты передаются в АТП и используются системой АРМ GP для расчета ССЗ.

Система AHM GP предназначена для автоматизации процесса оперативного планирования и управления автомобильными грузовыми перевозками в АТП, завершающим этапом которой является составление ССЗ для каждого автомобиля. Она может быть использована автономно в каждом АТП в качестве автоматизированного рабочего места диспетчера для ежедневного формирования ССЗ грузовых автомобилей или в сети с системой SIGEMA. ' _ '

Опишем общую схему применения системы АШ GP. Предварительно формируется база НСИ и готовится информация о ТС и кратчайших расстояниях. Ежедневно вводятся новые или корректируются старые заявки' на перевозку грузов и провозные возможности подвижного состава. Планирование грузовых перевозок осуществляется на заданный дегь и проводится в целом по АТП или в отдельности по филиалам, колоннам и бригадам. На основе полученных планов для междугородных, зональных я городских перевозок рассчитываются ССЗ для каждого автомобиля. Отдельно формируются ССЗ для автомобилей, работающих на условиях почасовой или сдельной оплаты по заявкам постоянной клиентуры. По каждому ССЗ рассчитываются временные и стоимостные показатели работы автомобиля, а также расстояния

перевозки и расход топлива.

В завершении работа рассматриваются задачи организационного управления контейнерными автомобильными перевозками. Централизация автомобильных контейнерных перевозок осуществляется ПО "Меж-автотранс" через грузовые автостанции (ГАС) и контейнерные площадки (КП) путем составления кольцевых маршрутов на междугородные перевозки.

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

Пусть имеется m заявок на перевозку, в которых ai ~ количество контейнеров; р± - пункт погрузки; qi - пункт разгрузки. Построим множество всевозможно допустимых двухзвенных кольцевых маршрутов (i,J) кз i-й и з-й заявок по следующим признакам: коэффициент использования на маршруте должен быть больше заданного числа, а количество контейнеров по i-й заявке должно соответствовать количеству контейнеров по з-й заявке. Для этих маршрутов определяются значения коэффициентов с^, которые приравниваются к порожним пробегам на маршрутах (t,J) и d±y принимающие значение единицы, если в 1-х или з-х заявках, формирующих допустимый двух-звешшй кольцевой маршрут, хотя бы один из пунктов погрузки иш разгрузки совпадает с пунктом грузоотправителей или грузополучателей, указанным в товарно-транспортных накладных. Если через xîj обозначить переменную, принимающую значение единицы, если 1-я и з-я заявки фордируют двухзвенный кольцевой маршрут, и нуль в противном случае, то математические модели определения оптимальных двухзвенных кольцевых маршрутов будут клеть вид:

М14: найти min < V У с.. х. « };

X € R(x) 1=13=1 13 i3

MIS: найти aln ( £ £ с x / £ £ d x J;

X € R(X) 1=13=1 3 3 1=13=1 3 3 m _

R(x) = ( x. .: £ x. . = J , 1 = 1 .m: 3 3=1 3

Е X.. = 1, 3 = l.m; X. . г О, 1 = 1 .га: 3 = 1 ,п ).

1=1 1J 3

Задачи i114 и М15 представляют собой задачи о Егзнзчес'Я!.

Если учесть запретные элементы моделей, то они могут быть .переформулированы в виде задачи о минимальном парасочетании в ориентированном двудольном графе.

Пусть в результате решения задачи Ы14 или Mi5 определена оптимальная система из к двухзвенных кольцевых маршрутов с интея-сивностями (gr), где gr - количество контейнеров, которые необходимо перевести по каждой заявке маршрута. Тогда для перевозки контейнеров по маршрутам необходимо закрепить их за ГАС и выбрать для них подходящий автомобиль. Пусть по всем ГАС имеется р заказанных автомобилей и для каждого из них изгестны провозные возможности которые соответствуют количеству

контейнерных мест на i-f автомобиле. Введем обозначения: уг1 -переменная, принимающая значение единицы, если на .г—м маршруте закрепляется 1-й автомобиль, и нуль в противном случае; /г1 -величина изменения порожних пробегов, если на г-м маршруте закрепляется 1-й автомобиль: с х и drl - затраты и доходы при перевозке контейнеров r-го маршрута i-м автомобилем. , тогда для решения задачи закрепления автомобилей за маршрутами используется одна из следующих моделей:

Ы16: найти min ( £ £ f у )-. у е R(y) г=11=1 ri

к р к р

¡117: найти min Г £ £ с у / £ £ d у )-, у € R(y) г=11=1 ri ri r=1l=1 T1 T1 ■

Р _ к _

■R(y) = ( yrl: Е Уг1 = 1. * = Е Уг1 < и 1 = 1.р;

1=1 r=1

Уг1 > О, г = ТТк: 1 = ТТР ).

Задачи М16 и 1117 также могут быть сведены к задачам о назначение.

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

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

управления автомобильными контейнерными перевозками- Она используется в качестве автоматизированного рабочего места диспетчера для оперативного формирования заданий водителям грузовых автомобилей и управления мзкдугородными и городскими контейнерными перевозками. Основными функциями системы /БРАК является: прием и отправка контейнеров с площадки; регистрация контейнерных перевозок; оперативный учет использования контейнеров; инвентаризация контейнерного парка; учет выполнения клиентурного плана перевозок; расчет оплаты за предоставленные клиенту услуги; . ведение НСИ.

Система МКР предназначена для маршрутизации контейнерных перевозок в междугородных и технологических направлениях. Она информационно взаимосвязана с системой АБРАК и готовит для нее кольцевые маршруты. Кольцевые маршруты на междугородные перевозки определяются на базе полученных от КП заявок на перевозку. Информационные и вычислительные процессы соответствуют системе Б1СЕМА. В МКР решаются математические модели М14 - М17. Построенные кольцевые маршруты передаются на КП. которые в дальнейшем используются в системе АБРАК при организации перевозочного процесса автомобильных контейнеров.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

Получены следующие научные и прикладные результата.

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

2. Исследованы различные классы задач ДЛП, для решения которых предложены общие математические методы, конкретные вычислительные алгоритмы и программы на ЭВМ.

3. Исследованы задачи ДЛП общего вида, для решения которых предложены модификации параметрического котода и эффективные алгоритмы типа Кармаркара - Дикина.

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

5. Изучен класс задач обобщенного ДЛП и разработаны декомпозиционные алгсритш с использованием принципов Данцига - Вулфа и'Корнай - Лйптака в сочетании с субградиентнымя методами. Аналогичные алгоритмы предложены для ресешя различных задач обобщенного дробно-выпуклого программирования.

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

?. Предложена новая информационная технология и разработаны системы ЫТЗ, КГБ и БЕТЙАг моделирования. ТС, расчета кратчайших расстояний и решения сетевых транспортных задач с линейными и дробпо-линв' дыми функционалами.

8. Ра фаботаны математические модели, алгоритмы и система Т1Ш определения структуры грузовых перевозок по видам транспорта на основе транспортного баланса. Проведены расчеты по составлению транспортного баланса Республики Молдова. Результаты использованы в Министерстве транспорта ИИ.

9. Исследован класс задач оптимизации структуры подвижного

состаза к грузовых перевозок АТОП, для решения которых разработана система математических моделей, декомпозиционные алгоритмы, программное обеспечение и информационная технология их реализации ка г;з!,1 (система STR). Использование результатов на практике позволяю повысить эффективность перевозочного процесса за счет синения себестоимости перевозок и повышения производительности подЕггаого состава.

10. Разработан комплекс математических моделей, алгоритмов и программ определения годового клиентурного плана грузовых перевозок (система PGP).

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

12. Исследованы математические задачи закрепления маршрутов за АТП и предложен комплекс математических моделей дробно-линейного програ:.иирования и эффективные алгоритмы их решения.

13. Разработано семейство автоматизированных систем SIGEMA оперативного планирования и управления междугородными автомобильными перевозками массовых грузов, в которых используются различные модели и алгоритмы решения задач составления кольцевых маршрутов и закрепления их за АТП. Системы SIGEMA применяются в те--.сею 10 лет в №шистерстве транспорта РМ для централизации мэидугородных перевозок.

14. Разработано автоматизированное рабочее место диспетчера грузоБЫХ перевозок АРМ GP, которое в сочетании с системой SIGMA формирует единую информационную технологию совершенствования процесса управления и планирования в АТП.

15. Исследованы задает кольцевой маршрутизации автомобильных контейнерных перевозок и разработаны математические модели, алгоритмы и системы ASPAK и МКР, которые используются в оперативном резаке для автоматизации процесса принятия решений при выборе направлений и маршрутов перевозки контейнеров.

Основные результаты диссертации опубликованы в следующих работах.

I. Соломон Д.И. Обобщенные задачи дробно-линейного програм-

».мровакия // Математические исследования. - 1979. - Вып. 52: Математическое моделирование экономических систем.'- С. 205 - 215.

2. Соломон Д.И. Об одном методе решения задач дробно-лкней-ного программирования с матрицами блочно-диагональной структуры // Изв. АН МССР. Сер. физ.-техн. и мат. наук. - 1979. - J5 3. -С. 68 - 70.

3. Соломон Д.И.. Шаров В.Н., Зоти А.Г. Моделирование на ЭВМ процесса годового планирования автомобильных грузовых перевозок // Математические исследования. - 1982. - Вып. 68: Модели и алгоритмы решения задач планирования и управления. - С. 125 - 134.

4. Соломон Д.И. Применение метода обобщенного градиентного спуска при решении задач дробно-линейного программирования // Изв. АН МССР. Сер. физ.-техн. и мат. наук. - 1983. - Я I. -С. 7- 13.

5. Соломон Д.И. Об одной задаче целочисленного дробно-линейного программирования // Математические исследования. - 1983. .Вып. 72: Математические модели и методы оптимизации экономических систем. - С. 122 - 131.

6. Соломон Д.И. Обобщение линейной и дробно-линейной транспортной задачи // Изв. АН МССР. Сер. физ.-техн. и мат. наук. -1984. — JS I. - С. 13 - 18.

7. Соломон Д.И. Применение схем разложения по переменном с использованием метода обобщенного градиентного спуска при решении задач дробно-линейного программирования // Математические исследования. - 1985. - Вып. 82: Математические модели и методы оптимизации. - С. 121 - 134

8. Соломон Д.И. Итеративный алгоритм решения обобщенной задачи дробно-линейного программирования // Математические исследования. - 1985. - Вып. 87: Моделирование и оптимизация'в задачах планирования и управления. - С. 161 - 164.

9. Со юмон Д.И. Параметрический метод ресения задач дробно-линейного программирования // Математические исследования. -1987. - Еып. 95: Оптимизация и обработка данных. - С. 124 - 134.

.„10. Соломон Д.И.. Шаров В.Н. Оптимизация структуры подвижного состава автотранспортных предприятий // Там т.е. -С. 135 - 145.

II. Соломон Д.И. Декомпозиционные методы в дробно-линейном

программировании // Математические исследования. - 1988. -Вып. 100: Системы оптимизации и обработки данных. - С. 115 - 132.

12. Соломон Д.И. Декомпозиционные алгоритмы решения обобщенных задач дробно-линейного программирования // Там же. -С. 133 - 143.

13. Соломон Д.И. Математические модели решения задач маршрутизации автомобильных грузовых перевозок // Математические исследования. - 1939. - Вып. НО: Математическое моде.яирование и 'оптимизация. - С. 107 - 115.

14. Шор Н.З., Соломон Д.И. Декомпозиционные методы в дробно-лннейном программировании. - Кишинев: Штиинца, 1989. - 202 с.

15. Соломон Д.И. Математическая модель построения кольцевых маршрутов // Изв. АН МССР. Сер. Математика. - 13Э0. - JC I. -С. 50-55.

16. Соломок Д.И. Математические модели решения задач закрепления маршрутов за автотранспорными предприятиями // Математические исследования. - 1990. - Вып. 114: Математическое моделирование экономических процесов. - С. 109 - 119.

17. Соломон Д.И., Кеденко З.С.. Кроитору ?.В. Программное обеспечение системы оперативного планирования и управления междугородными автомобильными грузовыми перевозками // Математически? Исследования. - 1991. - Вып. 121: Оптимизация и обработка данных. - С. 133 - 138.

Распределение личных результатов автора по совместным работам таково: [3. 10, 17] - постановка задач, математические модели, алгоритмы и программное обеспечение решения задач оптимизации; [141 - 5 1.2; § 1.4; полиномиальные алгоритмы решения задач ДЛП из 5 2.5; главы 3-5.

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