книги из ГПНТБ / Большие системы и управление

112

м- { ^ 2 k ’ и г г аЗЫ U27 U13 U3*+? U23U35 U5iff UZ1U13U35U5bl

Если транспортную сеть представляется возможным изобразить в виде ориентированного графа (перевозки на каждом участке се­ ти совершаются в заданном направлении) без контуров, то отыска­ ние путей между заданными пунктами сводится к следующему* Для перечисления путей между двумя заданными пунктами 10 и ] 0 не­ обходимо перенумеровать узлы транспортной сети таким образом,

Рис.15. Пример ориентированной сети

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

где и£0 - множество дуг, входящих в вершину J0 . Используя рекуррентную формулу ( I I ) , можно определить все элементарные пути между заданными пунктами [5 J.

и з

Р а с с м о т р и м п р и м е р о п р е д е л е н и я в с е й п у т е й м е ж д у п у н к т а м и I

и 8 д л я с е т и , и з о б р а ж е н н о й н а р и с . 1 5 .

Ми’г)= ц п -, Л?(7,3= и 13 ; М( Ш = М (иг)и 2, У М (ЬЗ)и3, V t / „ =

= u n u zlf\Jut3u3^\lu1lt’, M (h5>= M (,’‘f,u ltSW (,’3)u35 =

^>Jnu2ku^ slu,3u3fu^s ^иши‘и Уи13и35 ь H ° ’S>= М °’г)игеУ

W MAhb)a^6 = и}2 и26Уи12и^и^6 Уи13и3^и^6 \/u }¥u^6 ;

~ Ujz u2if UifS u58 ^ U13 U3b Ub5 U58 ^ ^ lb Ub5 US8^ U13 U35 U58^U12U27Ur?8V

Описанные методы перечисления путей для задач больших раз­ мерностей трудно реализуемы на ЦВМ» требуют выполнения такого объема вычислений, который часто не может быть выполнен в при­ емлемые сроки.

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

-устойчивость к размерности задачи;

-статистический характер метода снижает влияние сбоев ЦВМ на результаты решения;

-програшы для реализации метода на ЦВМ сравнительно про­

сты;

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

115

Кандидат технических наук Л.И. ГРИГОРЬЕВА

МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ТРАНСПОРТНОЙЗАДАЧИ ДО КРИТЕРИЮ "МИНИМУМПОТЕРЬ ГРУЗА В ПУТИПРИ ДОСТАВКЕ В ЗАДАННЫЕ СРОКИ"

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

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

Математически это можно записать в следующем виде. Имеет­ ся т пунктов отправления и п пунктов назначения. В каждом

bj единиц этого же груза. Для промежуточных пунктов j'Q = 1,2у.-,п) количество ввозимого груза равно количеству вывозимого. Неко­ торые пункты отправления и назначения также могут быть пункта­ ми, через которые груз частично перевозится.

lie

Пункта отправления, назначения и промежуточные пункта сое­ динены транспортной сетью, состоящей из N участков* Транс­ портную сеть можно представить либо в виде неориентированного

(соответствует участкам сети ). На рис.16 изображена сеть, где W = AVBVC , А - множество пунктов отправления, В - множество пунктов назначения, С - множество промежуточных пунктов* Транс­

Рис *16* Изображение транспортной сети в виде графа

117

ются условия 1 - 4 , определяет допустимые маршруты и объемы

118

перевозок на них. План перевозок, для которого выполняется и условие 5, является оптимальным.

Заметим, что следствием условий 2 и 3 является неравенство

как введением фиктивного пункта назначения указанное неравен­ ство сводится к равенству.

Если суммарные запасы пунктов отправления меньше общей по­ требности пунктов назначения, то для приведения к равенству вводится фиктивный пункт отправления иш+ I й, в котором сосре­ доточено

для получения-равенства вводится фиктивный пункт назначения "п + Г о потребностью

Критериальная функция (условие 5) представляет собой нелиней­ ную функцию целочисленных искомых переменных • Таким образом, сформулированную задачу построения плана перевозок с минимумом потерь груза в пути при доставке в заданные сроки можно отнести к задачам нелинейного целочисленного программи­ рования.

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