книги из ГПНТБ / Косенко Б.Ф. Многоэтапная транспортная задача монография

ВОЕННАЯ АКАДЕМИЯ ТЫЛА И ТРАНСПОРТА

КОСЕНКО Б. Ф.

МНОГОЭТАПНАЯ

ТРАНСПОРТНАЯ ЗАДАЧА

МОНОГРАФИЯ

Л е н и н г р а д

1 9 6 4

1

*

ГЛАВА 1

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ МНОГОЭТАПНОЙ ТРАНСПОРТНОЙ ЗАДАЧИ

ПРЕДМЕТ МНОГОЭТАПНОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1

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

Характерной особенностью транспортного процесса в совре­ менных условиях является его комплексность и многоэтапность.

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

сов и т. д.

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

3

района при доставке в центральные области преходит ряд эта­ пов, последовательность которых определяется выбранным нап­ равлением перевозки.

Если избрано направление порт Каспийского моря—Волга— конечный пункт, то перевозка осуществляется: морским, речным,,

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

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

Исследуемая проблема, в связи с ее актуальностью, привле­ кает к себе внимание многих исследователей как в нашей стра­

шения задач подобного рода на ЭЦВМ [7]. В работе академика Канторовича Л. В. и Гавурина М. К. [1] приводится метод по­ тенциалов для решения задачи выбора кратчайших расстоянии между двумя пунктами. Юдин Д. Б. и Гольштейн Е. Г. [2] при­

Представляет интерес сетевая постановка транспортной зада­ чи, в которой сеть задается графом. Недостатком сетевой пос­ тановки задачи является значительная трудоемкость, практи­ чески исключающая возможность ручного решения [6 и 7].

Анализ состояния вопроса показывает, что в настоящее вре­ мя в этом направлении сделаны только первые шаги и пробле-

4

*ма пока еще не нашла удовлетворительного решения’ Алгорит­ мы задач о перевозках в многоэтапной транспортной системе, осложненные ограничениями пропускной способности коммуни­ каций, работой различных видов транспорта и другими допол­ нительными условиями, пока еще недостаточно разработаны. Более того, их анализ требует построения специальных алго­ ритмов [б].

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

5

\

циального алгоритма для ее решения. К этим свойствам отно­ сится многоэтапность процесса транспортировки, а для военно­

транспортных задач и направленность потока материальных средств.

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

небольшой емкостью оперативной памяти, а также вручную. Последнее обстоятельство объясняется тем, что сеть разбива­

Кроме того, в военно-транспортных задачах характерным является недостаточная устойчивость транспортной сети, под­ вергающейся непрерывному воздействию со стороны противника,

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

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

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

6

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

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

втранзитных пунктах.

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

ОСНОВНЫЕ ПОНЯТИЯ, ОПРЕДЕЛЕНИЯ И ТЕРМИНОЛОГИЯ

МНОГОЭТАПНОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Основные элементы цепи транспортировки

Условимся записывать цепь транспортировки в виде

А- © Fe© • • • © sFes© Bj>

где Ai ( i = l , 2,..., m) —пункты, в которые прибывают матери­ альные средства из центра (пункты входа в транспортную сис­ тему— распорядительные, станции, порты, вход трубопровода центра и аэродромы материального обеспечения, на которые

транзитные пункты, сопрягающие элементы цепи транспорти­ ровки (базы, склады, выгрузочные станции и порты, через которые материальные средства проходят в процессе пере­ возки);

7

ег=1 У=1

Терминология многоэтапной транспортной задачи

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

Рассмотрим в этой последовательности элементы цепи.

Транзитные пункты и коммуникации. Условимся считать транзитные пункты и коммуникации однородными при нали-

8

\

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

s

£ а / < Л , ; Р г >1. Z—-1

Аналогичное условие примем и для коммуникаций pi. > 1.

Так как излишек пропускной способности

т

А/ = / в— £ я,- /=1

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

9