Об одной модели многопродуктовой транспортной задачи

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Журбенко, Н.Г., Чумаков, Б.М.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/85053
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Об одной модели многопродуктовой транспортной задачи / Н.Г. Журбенко, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 119-123. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85053
record_format	dspace
spelling	irk-123456789-850532015-07-19T03:02:07Z Об одной модели многопродуктовой транспортной задачи Журбенко, Н.Г. Чумаков, Б.М. Приводится описание математической модели и метода решения одного класса задач перевозок на транспортной сети. Метод решения основан на использовании алгоритмов негладкой оптимизации. Предлагается приближенный алгоритм решения задачи с учетом ограничений дискретного характера. Наводиться опис математичної моделі та методу розв'язання одного класу задач перевезень на транспортній мережі. Метод рішення оснований на використанні алгоритмів негладкої оптимізації. Пропонується наближений алгоритм розв'язання задачі з урахуванням обмежень дискретного характеру. The article describes mathematical model and solution method for a class of transportation on transport network problem. The solution method utilises nonsmooth optimization algorithm. The approximate solution algorithm of the problem with account of discrete constraints is proposed. 2013 Article Об одной модели многопродуктовой транспортной задачи / Н.Г. Журбенко, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 119-123. — Бібліогр.: 3 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85053 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Приводится описание математической модели и метода решения одного класса задач перевозок на транспортной сети. Метод решения основан на использовании алгоритмов негладкой оптимизации. Предлагается приближенный алгоритм решения задачи с учетом ограничений дискретного характера.
format	Article
author	Журбенко, Н.Г. Чумаков, Б.М.
spellingShingle	Журбенко, Н.Г. Чумаков, Б.М. Об одной модели многопродуктовой транспортной задачи Теорія оптимальних рішень
author_facet	Журбенко, Н.Г. Чумаков, Б.М.
author_sort	Журбенко, Н.Г.
title	Об одной модели многопродуктовой транспортной задачи
title_short	Об одной модели многопродуктовой транспортной задачи
title_full	Об одной модели многопродуктовой транспортной задачи
title_fullStr	Об одной модели многопродуктовой транспортной задачи
title_full_unstemmed	Об одной модели многопродуктовой транспортной задачи
title_sort	об одной модели многопродуктовой транспортной задачи
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
url	http://dspace.nbuv.gov.ua/handle/123456789/85053
citation_txt	Об одной модели многопродуктовой транспортной задачи / Н.Г. Журбенко, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 119-123. — Бібліогр.: 3 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT žurbenkong obodnojmodelimnogoproduktovojtransportnojzadači AT čumakovbm obodnojmodelimnogoproduktovojtransportnojzadači
first_indexed	2025-07-06T12:12:58Z
last_indexed	2025-07-06T12:12:58Z
_version_	1836899610474315776
fulltext	Теорія оптимальних рішень. 2013 119 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Приводится описание математи- ческой модели и метода решения одного класса задач перевозок на транспортной сети. Метод ре- шения основан на использовании алгоритмов негладкой оптимиза- ции. Предлагается приближенный алгоритм решения задачи с уче- том ограничений дискретного характера.  Н.Г. Журбенко, Б.М. Чумаков, 2013 ÓÄÊ 519.8 Í.Ã. ÆÓÐÁÅÍÊÎ, Á.Ì. ×ÓÌÀÊÎÂ ÎÁ ÎÄÍÎÉ ÌÎÄÅËÈ ÌÍÎÃÎÏÐÎÄÓÊÒÎÂÎÉ ÒÐÀÍÑÏÎÐÒÍÎÉ ÇÀÄÀ×È Математические модели многих задач опти- мального проектирования, управления и планирования коммуникаций систем описы- ваются многопродуктовыми сетевыми транс- портными задачами. В данной работе приво- дится описание метода решения одного класса таких задач, основанный на использо- вании алгоритмов негладкой оптимизации [1]. Математическая модель описывается на концептуальном уровне. Входные данные модели помечаются словом data, выходные – result. Транспортная сеть представляется ориен- тированным графом }.,{ JIG = I (data) – множество вершин (узлов, станций) графа; i – индекс перечисления вершин. J (data) – множество ориентируемых ребер (дуг, уча- стков) графа; j – индекс перечисления ре- бер. ))()(( iJiJ −+ (data) – множество ребер, входящих в вершину (выходящих из верши- ны) i ; ))()(( jiji +− (data) – начальная (ко- нечная) вершина ребра .j L (data) – множе- ство типов продуктов (грузов); l – индекс перечисления типов продуктов. Q (data) – множество корреспонденций; q – индекс перечисления корреспонденций. Для кор- респонденции Qq ∈ определены следующие данные: тип груза ql (data); прогнозируемый объем перевозки qb (data). В модели будет использоваться следующая вариантная схема реализации корреспонденций. Эта схема основана на том, что для каждой Н.Г. ЖУРБЕНКО, Б.М. ЧУМАКОВ 120 Теорія оптимальних рішень. 2013 корреспонденции q априори задано множество способов ее реализации qΩ (data). Для каждой реализации qω∈Ω определены следующие данные: маршрут ( )qℜ ω (data); тариф стоимости перевозки единицы груза ( )qc + ω (data). Маршрут ( )qℜ ω определяется последовательным списком участков сети. Начальная станция 1( ) ( )qi i j − −ω = маршрута ( )qℜ ω ) – одна из станций отправления коррес- понденции. Конечная станция ( ) ( )qn qi i j + +ω = маршрута ( )qℜ ω – одна из стан- ций назначения корреспонденции. Представленная форма данных вариантов реализаций корреспонденций ин- формационно избыточна. Однако такая форма описания вариантов реализаций корреспонденций обеспечивает компактность записи и простоту интерпретации модели. Кроме того она имеет высокую форму общности и обеспечивает учет различных вариантов постановки задачи. Формально множество вариантов реа- лизаций корреспонденции рассматривается в модели как входные данные. Как правило, эти данные программно генерируются. При этом в качестве маршрутов корреспонденций могут, например, выбираться кратчайшие по выбранным кри- териям (по расстоянию; по эксплуатационным расходам; времени реализации) пути на транспортной сети, соединяющие станции отправления и назначения корреспонденции. При генерировании маршрутов корреспонденций могут учи- тываться дополнительные (технологические, экологические) требования, кото- рые в явном виде в модели не отражены. Каждой реализации ω корреспонденции q соответствует переменная мо- дели ( ) 0qx ω ≥ (result) – объем перевозки корреспонденции q по варианту ее реализации ω . Множество всех переменных ( )qx ω обозначим .+ X Общий объем реализуемых перевозок корреспонденции должен быть не большим, чем заданный прогнозируемый максимальный объем корреспонден- ции qb . Обозначим 0≥− qx (result) – нереализованный объем корреспонденции q . − qc (data ) – штрафной множитель за наличие единицы нереализованного объема корреспонденции q . Заметим, что штрафные множители − qc отражают, как правило, не реальные финансовые потери за отказ от полной реализации корреспонденции, а являются управляющими параметрами модели. Эти пара- метры позволяют ранжировать корреспонденции по степени важности реализа- ции их перевозок. Кроме того, введение переменных − qx обеспечивает формаль- ную совместность ограничений модели. ОБ ОДНОЙ МОДЕЛИ МНОГОПРОДУКТОВОЙ ТРАНСПОРТНОЙ ЗАДАЧИ Теорія оптимальних рішень. 2013 121 Переменные ( )qx ω и − qx удовлетворяют балансовым соотношениям: { ( ) \| } , ,q q q qx x b q Q −ω ω∈Ω + = ∈∑ ( ) 0, 0.q qx x −ω ≥ ≥ (1) Множество всех переменных − qx будет обозначаться .− X Общий «доход» )( ++ XF от реализаций корреспонденций и общий «штраф» )( −− XFb за наличие нереализованных перевозок определяются равенствами ( ) { ( ) ( ) \| ; },q q qF X c x q Q + + += ω ω ω∈Ω ∈∑∑ ( ) { \| }.b q qF X c x q Q − − − −= ∈∑ Пусть )( jw q (result) – перевозимый по участку j объем корреспонденции q . Значения )( jw q однозначно определяются значениями переменных ( ) :qx ω ( ) { ( ) \| ( ); }.q q q qw j x j= ω ∈ℜ ω ω∈Ω∑ Тогда условие ограниченности пропускной способности участка Jj ~ ∈ бу- дет соответствовать следующим ограничениям: { ( ) \| } , ,q q jw j q Q r j Jγ ∈ ≤ ∈∑ % (2) где qγ (date) – масштабирующий коэффициент, определяемый типом коррес- понденции .q Общие эксплуатационные затраты на перевозки всех корреспонденций )( +− XFc определяются следующим образом: ( ) { ( ) \| ; },q c qjF X c w j q Q j J − + −= ∈ ∈∑ где qjc − – затраты на перевозку единицы объема корреспонденции q на участке j. Задача состоит в максимизации целевой функции ),( −+ XXF – максимиза- ции «общего дохода»: )()()(),(max −−+−++−+ −−=← XFXFXFXXF c (3) при ограничениях (1), (2). Основными переменными задачи являются переменные реализаций вариан- тов перевозок корреспонденций ,+ X и переменные нереализованных их объе- мов .+ X Остальные переменные и указанные выше соотношения являются вспомо- гательными и введены для компактности записи и простоты интерпретации модели. Задача (1) – (3) является задачей линейного программирования. Основной особенностью реальных задач рассматриваемого класса является их большая размерность. Кроме того, при разработке метода решения предусмотрена возможность учета нелинейности отдельных функционалов модели (например, эксплуатационных затрат реализации перевозки от ее объема). Поэтому использо- вание стандартного программного обеспечения для их решения неэффективно. Н.Г. ЖУРБЕНКО, Б.М. ЧУМАКОВ 122 Теорія оптимальних рішень. 2013 Для реализации приведенного класса задач разработаны специализирован- ные численные методы, учитывающие особенности математической модели: сетевой характер многих соотношений задачи, блочную структуру переменных и ограничений. В качестве базовых элементов разработанные методы решения задач ис- пользуют следующие алгоритмы: • алгоритм нахождения кратчайших путей на графе [2] (используется для генерации возможных маршрутов реализаций перевозок корреспонденции на транспортной сети); • алгоритм негладкой оптимизации в схемах декомпозиции блочных задач математического программирования [1] (используется для решения двойствен- ной относительно ограничений (2)). Трудоемкость решения задачи в основном определяется решением двойст- венной, относительно ограничений (2), задачи. Решение задачи многоэтапное. Во-первых, это связано с тем, что определенный после решения задачи факт невозможности реализации всех перевозок (наличие положительных значений для переменных − qx ) может быть связан не только с ограниченностью пропуск- ных способностей участков сети (ограничения (2)). Это может быть связано с учетом не всех возможных реализаций перевозок корреспонденций («бедность» множеств qΩ ). Поэтому, на основе анализа уже полученного решения, выпол- няется пополнение множеств )(ωqℜ – возможных маршрутов реализаций пере- возок и решается таким образом модифицированная задача. В предельном слу- чае (если позволяет мощность компьютера), можно учесть все маршруты реали- зации перевозки, т. е. перейти к традиционной задаче определения потоков на сетях. Во-вторых, для реальных задач рассматриваемого класса часто имеется сле- дующее требование (дискретного характера) на допустимость перевозки (неко- торых) корреспонденций: перевозка должна производиться только по одному варианту ее возможных реализаций. Адекватный учет такого требования приво- дит к задаче с булевыми переменными. Для задачи большой размерности можно рассчитывать на получение лишь приближенного ее решения (обычно без оцен- ки точности). Поэтому предлагается следующий алгоритм приближенного ре- шения таких задач. В результате решения двойственной задачи для большинства корреспонденций реализация будет выполнятся только по одному из заданных вариантов. Тогда для таких корреспонденций полученный вариант принимается за решение задачи. После исключения этих корреспонденций размерность зада- чи может оказаться приемлемой для ее решения с учетом булевости перемен- ных. Отметим еще один способ получения приближенного решения на основе ОБ ОДНОЙ МОДЕЛИ МНОГОПРОДУКТОВОЙ ТРАНСПОРТНОЙ ЗАДАЧИ Теорія оптимальних рішень. 2013 123 решения двойственной задачи. В процессе работы алгоритма решения двойст- венной задачи будут генерироваться множество «одновариантных» реализаций корреспонденций, соответствующих решению внутренней задачи используемой схемы декомпозиции. Разумеется, «полезные» одновариантные решения будут на итерациях алгоритма вблизи оптимального решения двойственной задачи. Кроме того, для такой генерации вариантов можно использовать обобщенный градиентный метод с постоянным шагом (см., например, [3]), стартующий с уже найденного приближенного решения. В процессе его работы производим отбор наилучшего одновариантного решения (наилучшего в смысле минимального нарушения ограничений (2)). Таким образом найденное решение обычно прием- лемо при решении реальных задач перспективного планирования, поскольку, ограничения на пропускную способность задаются на основе прогноза с доста- точно большой неопределенностью. М.Г. Журбенко, Б.М. Чумаков ПРО ОДНУ МОДЕЛЬ БАГАТОПРОДУКТОВОЇ ТРАНСПОРТНОЇ ЗАДАЧІ Наводиться опис математичної моделі та методу розв'язання одного класу задач перевезень на транспортній мережі. Метод рішення оснований на використанні алгоритмів негладкої оптимізації. Пропонується наближений алгоритм розв'язання задачі з урахуванням обмежень дискретного характеру. N.G. Zhurbenko, B.M. Chumakov ON ONE MODEL OF MULTICOMMODITY TRANSPORTATION PROBLEM The article describes mathematical model and solution method for a class of transportation on transport network problem. The solution method utilises nonsmooth optimization algorithm. The approximate solution algorithm of the problem with account of discrete constraints is proposed. 1. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. – Киев: Наук. думка, 1979. – 199 с. 2. Филипс Д., Гарсиа-Диа А. Методы анализа сетей. – М.: Мир, 1984. – 496 с. 3. Беляева Л.В., Шор Н.З., Журбенко Н.Г. О методе решения одного класса динамических распределительных задач // Экономика и математические методы. – 1978. – 14, вып. 1. – С. 137 – 146. Получено 27.03.2013

Об одной модели многопродуктовой транспортной задачи

Institution

Ähnliche Einträge