книги из ГПНТБ / Большие системы и управление
..pdf100
Для этой матрицы все требуемые неравенства выполняются. Дейст вительно,
6 |
+ |
8 с |
6 |
+ |
п. |
8 + 9 |
«с |
10 |
+ |
13, |
||
6 + 6 |
< 5 + 9, |
8 + 3 |
С 4 + 9, |
|||||||||
6 |
+ |
9 |
< |
4 |
+ |
12, |
6 |
+ 9 |
С |
10 |
+ |
I I |
6 + 3 |
< 2 |
+ |
8, |
6 + 3 |
С |
7 + 7, |
||||||
8 + |
6 |
< |
7 |
+ |
15, |
9 |
+ 3 |
■«*£. |
8 + |
14 |
||
Искомое |
решение |
|
|
S = 6 + 8 + 6 + 9 + 3 |
32. |
Это решение |
оптимальное. |
|
При рассмотрении последнего примера нам удалось проиллю |
||
стрировать |
высказанное ранее утверждение, |
что учет равенства |
и применение алгоритма к матрице, содержащей найденное решение на главной диагонали, иногда позволяют получить вместо квазиоптимального оптимальное решение.
Другим любопытным моментом в решении данного примера яв ляется иллюстрация очень характерного свойства данного алгорит ма, заключающееся в том, что основная перестройка матрицы про исходит чаще всего на первом шаге алгоритма.
Наконец, интересной особенностью найденных оптимального и квазиоптимального решений является отсутствие в них числа 2, являющегося независимым элементом исходной матрицы.
IOI
Кандидат технических наук Л.И. ГРИГОРЬЕВА
О ШБОРЕ КРИТЕРИЯ В ЗАДАЧЕ ПЛАНИРОВАНИЯ ПЕРЕВОЗОК
Задача перевозок является одной из операционных задач боль шой системы - системы снабжения. Поэтому критерий эффективно сти задачи планирования перевозок определяется критерием эффек тивности функционирования системы снабжения. Минимизируемый функционал по критерию стоимости в линейном варианте имеет сле дующий вид:
фг £ £ |
Xi* |
(D |
где ||C ;J - заданная матрица затрат, а элементы матрицы Х=||х^|| удовлетворяют условиям:
Е х ц ■=а - ,
|
|
£ х ч - ь> 1 |
где а19 |
Ь: * |
с/;;-'ц елы е числа, удовлетворяющие условиям |
L |
V ~ |
La |
Ь:> 0 • о £ d a - 00 •
дНа практике*часто приходится иметь дело с нелинейными функ
ционалами [i] ^ . Так, минимизируемый функционал может иметь вид
Литература помещена после статьи автора "Стохастический метод решения задали коммивояжера" (стр. ).
102
Фг = £ |
£ c ii x ii + bi, |
( 2) |
i=l |
4 |
4 ' |
Иногда дополнительная плата взимается за сам факт перевозки, тогда минимизируемый функционал принимает вид
т п |
|
|
(3 ) |
|
ф3= £ |
|
|
||
c a x 4 + mi i E ( x i ^ ' |
||||
где /л; - плата, взимаемая |
за |
наличие перевозки по маршруту |
||
Е(х)~ функция единичного скачка, |
определяемая следующим |
|||
образом: |
0, |
если |
х = О, |
|
E ( x h |
||||
1, |
если |
0. |
||
|
||||
В частном случае стоимость перевозки может вообще не зави сеть от количества перевозимого груза, что имеет место при пе ревозке малогабаритных грузов. Тогда целевой функционал запи шется з виде:
Ф = Е Е С ; ; Е ( * Ф - |
(4) |
1=7 <И |
|
В этом случае минимизируется полный пробег транспорта. В общем случае минимизируемый функционал можно записать в следующем виде
где |
- заданные |
нелинейные функции одного аргумента. |
|
|
В настоящее время разработанным считается метод решения |
||
нелинейной транспортной задачи по стоимостному критерию для |
|||
случая вогнутых |
выпуклых вниз) [ i ] . |
|
|
|
Планирование перевозок груза, длительное пребывание |
которо |
|
го |
в пути ухудшает качество, следует производить по критерию |
||
"минимум времени доставки". |
|
||
|
Минимизируемый функционал в атом случае имеет вид |
|
|
|
$ 6 = max t Li |
(6) |
|
Ц
103
где t - - время перевозки груза из пункта i в пункт j , неза висящее от количества груза*
При планировании перевозок иногда важно учитывать надеж ность доставки груза к месту назначения* Наличие случайного воздействия при транспортировке (неисправность дорог, транс порта и некоторые другие факторы) может привести к потере груза в пути. Вследствие сказанного груз к месту назначения может при быть к назначенному сроку лишь с некоторой вероятностно. Отсюда представляет интерес критерий "минимум потерь груза в пути при доставке в заданные сроки".
Целевой функционал в этом случае имеет |
вид |
|
|
Ф7 = Ъ Р ( Ц ) х ц . |
(?) |
Выражение (7) представляет собой математическое ожидание |
||
потерь груза; |
есть вероятность потери груза при передви |
|
жении от пункта L |
до пункта j . Если маршрут (L,j) не задан, |
|
то функционал |
выражает нелинейную зависимость. |
|
План перевозок, построенный согласно предлагаемому крите |
||
рию [7 ], позволяет |
сократить потери груза |
в пути по сравнению |
Рис.12. Представление транспортной сети в виде неориентирован ного графа
с планом перевозок по критерию "минимум времени". Рассмотрим
иллюстративный пример |
(рис.1 2 ). |
Имеется 4 пункта отправления |
(1 ,2 ,3 ,4 ) и 6 пунктов |
назначения |
(5 ,6 ,7 ,1 0 ,1 1 ,1 2 ). В пунктах |
|
|
104 |
|
|
отправления находится запас а г= |
5, а г = 4, а3= 15, |
а = 17 еди |
||
ниц груза; |
в пунктах назначения |
существует потребность Ь$= 12, |
||
Ь6 = 5, 67= |
6, Ъ10~ 3, Ьп = Ю, bJZ= 5 единиц этого же груза.Вре- |
|||
мена следования на кратчайших маршрутах приведены в табл.2, |
||||
вероятности потери груза на кратчайших маршрутах |
P*(L,j)- в |
|||
табл. 4 . |
|
|
|
|
В клетках табл .4, соответствующих маршрутам, |
неудовлетво |
|||
ряющим ограничению по времени, |
стоит достаточно большое число |
|||
R . Оптимальный план перевозок |
по критерию "минимум времени |
|||
доставки" изображен на таблице |
3, а оптимальный план перевозок |
|||
по критерию "минимум потерь груза в пути при доставке в задан
ные |
сроки" |
- на |
табл.5 . |
Ограничения по времени для пунктов на |
|||||||||||||||||
значения приняты одинаковыми и равными |
tj = Т = пип max t^E(xL- |
||||||||||||||||||||
|
|
|
|
|
Т а б л и ц а 2 |
|
|
|
|
|
|
|
|
|
|
W |
|||||
|
|
|
|
/ |
|
|
|
|
|
Т а б л и ц а 3 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N i |
|
5 |
6 |
7 |
10 |
II |
12 |
|
X i |
5 |
6 |
7 |
|
10 |
II |
|
12 |
|
|
||
L |
N |
|
L \ |
|
|
|
|
||||||||||||||
|
I 12 |
5 |
8 |
3 I I 14 |
|
I 0 I I |
|
3 |
0 |
0 |
|
5 |
|||||||||
|
2 |
12 |
6 |
9 |
4 |
12 |
14 |
|
2 |
0 |
4 |
0 |
|
0 |
0 |
|
0 |
|
4 |
||
|
3 |
|
2 |
5 |
2 |
7 |
|
5 |
4 |
|
3 |
12 |
0 |
3 |
|
0 |
0 |
0 |
|
15 |
|
|
4 |
|
7 |
4 |
I |
6 |
|
4 |
5 |
|
4 0 0 2 |
|
0 10 |
|
5 |
17 |
|||||
|
|
|
|
|
|
|
|
|
|
|
ч |
12 |
5 |
6 |
|
3 |
10 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Средние потери по критерию "минимум времени" составляют |
|||||||||||||||||||
LT = |
0,72 + |
0,5 + 3*0,9 + 4*0,58 |
+ 12*0,8 + 3*0,54 + 2*0,9 + |
||||||||||||||||||
|
|
|
|
+ |
10*0,81 |
+ |
0,28 |
~ 25 |
(единиц груза). |
|
|
|
|
|
|||||||
|
|
|
|
|
Т а б л и ц а 4 |
|
|
|
|
|
Т а б л и ц а 5 |
||||||||||
|
|
5 |
|
6 |
7 |
10 |
|
I I |
12 |
|
|
\<* |
5 |
6 7 10 I I 12 |
|
||||||
|
|
|
|
|
|
L \ |
|
||||||||||||||
I |
|
R |
|
0,72 |
0,5 |
0,9 |
|
R |
R |
|
|
I |
0 |
0 |
5 |
0 |
0 |
0 |
5 |
||
2 |
|
R |
|
0,58 |
R |
0,72 |
|
R |
R |
|
|
2 |
0 |
4 |
0 |
0 |
0 |
0 |
4 |
||
3 |
0,8 |
|
0,38 |
0,54 |
0,32 |
0,48 |
0,48 |
|
|
3 |
0 |
I |
I |
3 |
10 |
0 |
15 |
||||
4 |
0,18 |
0,9 |
0,9 |
0,72 |
0,9 |
0,28 |
|
|
4 |
12 |
0 |
0 |
0 |
0 |
5 |
17 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
12 |
5 |
e |
3 |
10 |
5 |
|
|
Средние потери груза в пути при плане перевозок, оптималь ном по критерию "минимум потерь груза в пути при доставке в заданные сроки", составляют
105
L p= 5*0,5 + 4*0,58 + 3*0,38 + 0,54 + 3*0,32 + 10*0,48 +
+ 12*0,48 + |
5*0,28^18 (единиц груза). |
|||
Таким образом, в этом |
случае |
потери |
в 1,4 |
раза мень |
ше потерь при доставке по |
плану |
при |
критерии |
"минимум |
времени доставки". |
|
|
|
|
106
Кандидат технических наук Л.И. ГРИГОРЬЕВА,
В.Я. АНТОНОВ
МЕТОДЫ ОТЫСКАНИЯ ВСЕВОЗМОЖНЫХ ПУТЕЙ НА СЕТИ
При решении некоторых операционных задач, возникающих при автоматизации управления сложными системами, представленными в виде сети, возникает необходимость перечисления всевозможных путей между фиксированными узлами этой сети. Задачи такого ро
да возникают при передаче информации в информационных системах при наличии промежуточных коммутационных узлов и каналов связи, когда качество передачи данных требуется оценить сразу по не скольким критериям (достоверность, скорость передачи данных и т . д . ) . Вопросы необходимости перечисления всевозможных путей
на сети возникают при построении в некотором смысле оптимальных релейноконтактных схем, а также при планировании грузопотоков на транспортной сети.
Рассмотрим некоторые методы отыскания всевозможных путей между двумя заданными пунктами на транспортной сети.
Пусть транспортная сеть задана в виде , матрицы инциденций (соединений, переходов) [2 ]. Примем обычное в транспортных за - дачах предположение о том, что груз проходит через пункт не более одного раза. Такой маршрут обычно называют простым (эле ментарным) ,
Рассмотрим метод [3] нахождения пути заданной длины, если
под длиной иметь в виду число участков |
сети, соединяющих за |
|||||
данные пункты. |
|
|
|
|
||
Обозначим через |
множество путей длины, кукоторые ведут |
|||||
из пункта |
i |
в пункт J. . |
Множество |
|
, которое состоит из од |
|
ного участка, ведущего из |
i |
в j , |
обозначим через иц. Если |
|||
/?;; пусто, |
то |
ему придается |
значение |
0. |
В соответствии со ска |
|
жет |
|
|
|
|
|
|
|
107 |
|
|
ванным выше путь длины к , |
представляющий собой упорядоченную |
||
последовательность участков |
uLl , иг ^ , . . ., |
иь |
символически |
можно изобразить упорядоченным произведением |
и ^ и ь L и ь ь ... иL |
||
Так как несуществующий участок соответствует нулевому coW omh-*'^ телю, то*если хотя бы один участок на пути не существует, сим волическое произведение, отвечающее данному пути, обращается в нуль.
Множество путей длины к между пунктами i и j можно пред ставить в виде неупорядоченной суммы произведений (каждое про изведение является элементом этого множества):
Q |
0 |
а |
|
R W - Е |
Е . |
. Е |
(D |
г,= / |
|
iк-1Uu, |
|
где компоненты, равные нулю, соответствуют несуществующим пу тям.
Справедливо следующее рекуррентное соотношение, устанавли вающее связь между множеством путей длины к и Ы , соединяю щих пункты L и J :
(к - 1 ) |
® |
(к) |
( 2) |
|
« ы |
“ ^ |
Ui4 R 4i |
||
|
Это следует из того, что с учётом (I) имеет место:
4 |
U- |
(к) |
= Е U iq |
( Е Е . . |
. |
Е и |
J U, , |
|
|
и |
|
||||
Е |
Rq; |
• . . |
|
||||||||||||
ц= 1 |
У |
^ |
<{=1 |
^ |
|
1г=1 |
1Н_ = 1 |
Ч 1' |
1( 1г |
|
|
|
|
||
|
|
= Е Е Е . |
Р . . и( г иг Ч и1 |
lk-ii |
|
|
|||||||||
|
|
|
я^ if1 Ч |
|
|
|
|
|
|
|
|
|
|
|
|
|
Заменяя |
индекс |
на |
l v индексы |
l h , |
h = |
1 , 2 , . . . , |
/г - |
I на |
||||||
Z |
в выражении |
(3), |
получим |
|
|
|
|
|
|
|
|
||||
|
|
|
Q |
Q |
|
9 |
Цц и, . |
|
■Ut ;= |
R |
(k+l) |
(4) |
|||
|
|
= Е |
Е |
|
£ |
|
Ц |
' |
|
||||||
|
|
|
1,=1 |
i2=i |
|
1 =1 |
и 1 |
Ч 1г |
|
|
|
|
|
||
При помощи матриц инциденций шсших порядков можно указать способ нахождения множествапутей заданной длины между двумя пунктами.
|
|
|
|
|
|
|
108 |
|
|
|
Матрица инциденций первого порядка |
ла) определяется еле- |
|||||||||
дующим образом: |
|
|
|
|
|
|
|
|
|
|
|
|
|
О) |
|
|
|
(£ >i — 7* 2 , . . . 5 ф * |
|
||
|
А = А |
|
|
|
|
|||||
где а — = / |
? |
- |
и: \ $ |
т*е. |
элементы матрицы А(1 *соответствуют |
|||||
LJr |
ч |
|
L6 |
Если пункт |
I связан с пунктом j |
неко |
||||
связям между пунктами* |
||||||||||
торым участком |
сети, то |
а-1*= и Л |
и. ; - символическое изобра- |
|||||||
жение участка), |
в |
противном случае |
а - |
- 0. |
|
|||||
Элемент |
(к) |
матрицы |
А |
(£) |
|
^ |
|
поряд |
||
а ц |
|
(матрицы соединений к -го |
||||||||
ка) определяется |
согласно |
соотношению |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
(5) |
Умножение матриц переходов высших порядков определяется в этом случае аналогично умножению обычных матриц, за исключением того, что порядок сомножителей в каждом произведении должен быть сохранен ( т .е . умножение элементов матриц ассоциативно и дистрибутивно по отношению к сложению, но не коммутативно):
|
|
|
|
|
А |
( к + 1 ) |
|
(к) |
|
|
|
|
|
(6 ) |
|
|
|
|
|
|
АА |
|
|
|
|
|
|||
Действительно, элемент произведения матриц |
А А(к) (по правилу |
|||||||||||||
умножения матриц переходов) |
является суммой |
I |
|
|
. с |
|||||||||
гласно |
выражениям (2) |
и |
(5) |
эта |
сутв представляет собой |
эле- |
||||||||
мент |
' (к+1) |
|
|
(к+1) |
|
|
|
|
|
|
|
|
||
а ;; |
матрицы А |
|
|
|
|
|
|
|
|
|
||||
|
По индукции устанавливается равенство |
|
|
|
|
|||||||||
|
|
|
|
|
|
AW = a \ |
|
|
|
|
|
(7) |
||
Для к = I равенство справедливо по построению. Пусть это равен |
||||||||||||||
ство |
справедливо для |
к - |
h , |
тогда, используя |
(б ), получим |
|||||||||
|
|
|
|
Jh+1) |
|
(h) |
h |
= |
h + 1 |
|
|
( 8) |
||
|
|
|
|
А |
= АА |
= |
ДА |
А |
|
|
|
|||
|
Элемент (L, J ) матрицы |
А |
( к - 1,2 , * ..) является множест |
|||||||||||
вом всех путей |
длины |
к |
, ведущих из |
пункта |
I |
в пункт |
J |
• Та |
||||||
ким образом, множество всех путей длины |
к |
, ведущих из |
пункта |
|||||||||||
l |
в пункт |
j |
, может быть получено |
возведением матрицы |
А в |
|||||||||
к -ю степень. Нижние индексы |
содержащихся в матрице путей соот- |
|||||||||||||
109
ветствуют номерам пунктов транспортной сети, через которые про
ходят эти пути* Путь |
и и |
u L |
L . . |
■, ведущий из |
пункта i |
|||||
в пункт |
j , |
является |
элементарным путём длины |
к |
, |
если индек |
||||
сы 1,1п |
|
|
различны* Длина элементарного пути на сети, |
|||||||
содержащей т + п + п1пунктов, не может быть больше |
т + п+ п 1- 1. |
|||||||||
Если в матрице |
переходов |
д*исключить все члены uiLjUljL^... UiK_^7 |
||||||||
у которых не |
все индексы 1у1р |
|
различны, |
то |
элементы |
|||||
матрицы |
А* |
, полученной в результате такого исключения, пред |
||||||||
ставляют собой множество всех элементарных путей длины к , ве |
||||||||||
дущих из |
пункта |
I в |
пункт J |
• В задаче перевозок рассматрива |
||||||
ются элементарные пути. |
|
|
|
|
|
|
||||
Матрица А*(т) является матрицей соединений, |
у которой все |
|||||||||
диагональные |
элементы |
заменены нулями |
(Д, 0 , = |
А'). |
|
|||||
Рис.13. Изменение количества путей в зависимости от числа участков
Алгоритм отыскания элементарных путей длины стоит в следующем. Полагаем I = I и строим
А |
i+i |
А АП |
к ( к> I) со
(9)
В произведении матриц каждый член, представляющий не элементар ный путь, заменяется нулем. Если 1 + 1^ к , то увеличиваем I
на I и повторяем операцию умножения матриц, определяемую выра-