Устройство для оптимизации плана перевозок в транспортной сети Советский патент 1989 года по МПК G06G7/122 

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

Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации плана перевозок в транспортной сети с ограниченной ПРОПУСКНОЙ СПОСОбнОСТЬЮ.

На фиг, 1 представлена функциональная схема примера реализации устройства; на фиг. 2 - обобщенная структурная схема устройства.

из выходных пспюсов 27f1...27T , выходной полюс 28, третью группу из п выходных полюсов 29,... 29„ и четвертую группу из Т выходных полюсов

зо,...зот.

На обобщенной структурной схеме устройства (фиг. 2) обозначены: блок 31 счетчиков, первый блок 32 элементов ИЛИ, второй блок 33 элементов ИЛИ, с первого по третий блоки 34... ...36 таймеров, блок 37 элементов памяти, блок 38 выбора минимального кода, блок 39 приоритетов, матрицу 40

Изобретение относится к вычислительной технике и может быть использовано для решения транспортных задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации плана перевозок в транспортной сети с ограниченной пропускной способностью. Устройство содержит блок 31 счетчиков, первый блок 32 элементов ИЛИ, второй блок 33 элементов ИЛИ, с первого по третий блоки 34-36 таймеров, блок 37 элементов памяти, блок 38 выбора минимального кода, блок 39 приоритетов и матрицу 40 элементов ИЛИ. Кроме того цифровые обозначения имеют тактовый вход 41 устройства и выходы 42 плана перевозок из пунктов отправления в пункты назначения. Перед началом работы в (К,М)-ый элемент памяти блока 37 заносят код коэффициента транспортных затрат при перевозках из К-го пункта отправления в М-й пункт назначения, обнуляют счетчики блока 31, в К-й таймер блока 35 заносят код количества запасов в К-м пункте отправления, в М-й таймер блока 36 - потребности М-го пункта назначения, в (К,М)-й таймер блока 34 - ограничения на пропускную способность линии связи из К-го пункта отправления в М-й пункт назначения.При подаче на вход 41 устройства тактовых импульсов на выходе (К,М) -го счетчика блока 31 формируется план перевозок из К-го пункта отправления в М-й пункт назначения, 2 ил.

Устройство содержит блок 1 матрич-15 элементов ИЛИ, тактовый вход 41 устной модели транспортной сети, блок 2 максимального коэффициента транспортных затрат, блок 3 управления, блок 4 индикации и блок 5 расчета целевого функционала. Схемная pea- лизация и функциональное предназначение блоков 2, 4 и 5 аналогичны известному устройству.

Блок матричной модели транспортной сети предназначен для задания напряжений U $ м (К 1 ,2, . ,., Т; М 1,2, ,.,,п, где Т - количество пунктов отправления; п - число пунктов требления в матричной модели транспортной сети), пропорциональных ко- эффициентам транспортных затрат, и содержит матрицу из ячеек, каждая из которых содержит элемент И 6

k/Vv

электронный ключ 7Кми переменный резистор 8

третью группу из Т п.

9-гм, первую

КМ

входных полюсов 9 , группу из Т входных полюсов 10,... ...10-г, вторую группу из п входных полюсов 11, , . . 1 1 h, группу из Тхп выходных полюсов 2 1Л . . . 1 2 тп,

Блок управления предназначен для управления работой устройства и содержит генератор 13 импульсов, матрицу из элементов И 14 ,,,... 1 4 Тп, матрицу из счетчиков 1 5 1Л. . . I 5 Tn первую группу из п элементов ИЛИ 16 .,...16, вторую группу из Т элементов ИЛИ 17,... 17 т, первую группу из п счетчиков 18,,...18П, вторую группу из Т счётчиков 19,...19Т, первую группу из п элементов НЕ 201...20П, вторую группу из Т элементов НЕ 21 ,. .,.21Т, матрицу из Txrt элементов НЕ 22 ,, . . . 22 Тп, первую группу из выходных полюсов 23 1Л . . .23 т,,, группу из Т«п вх однык полюсов 24 н . . .24 т„, пятую группу из п выходных полюсов 25 ,..,25,,, шестую группу из Т выходных полюсов 2&1...26.,, вторую группу

0

0

ройства и выходы 42 плана перевозок из пунктов отправления в пункты назначения ,

Устройство работает следующим образом.

Перед началом работы с помощью переменных резисторов 8 ,.,... 8 Тп, задают напряжение U«M, пропорциональное величинам (R-3 VAJ , где , 5 Зкм, а 3 bv - коэффициенты транспорт- Счетчики 1 8 f. . . 1 8М 1 5 ,, . . . 1 5 т п устанавливают

5

0

0

5

км ных затрат.

и

в состояние (N-V ), (N-WH) и (N-A kM) соответственно, где Vk равно запасам К-го пункта отправления, W м- потребностям М-го потребления, А км- максимально возможные перевозки на маршруте из К-го пункта отправления в М-й пункт назначения, N - емкость счетчика. При поступлении сигнала на вход пуска устройства импульсы с выхода генератора 13 импульсов поступают на первые входы элементов И 14 ...14Т(1, на другой вход одного из которых через соответствующий полюс группы входных полюсов 24 ... ,..24Тп поступает сигнал с блока 2 выбора максимального коэффициента транспортных затрат. С выхода элемента И 14КМ, соответствующего минимальному элементу матрицы коэффициентов II 3 КДЛ11 транспортных затрат, импульсы поступают на счетный вход счетчика 15 Кт, соответствующего минимальному элементу, и через элементы ИЛИ 16Н и 17 подаются на счетные входы счетчиков 18 ми 19«, соответствующих столбцу и строке, на пересечении которых находится этот минимальный элемент. При заполнении одного из счетчиков 15ии, 18 м или 19 к сигнал о переполнении поступает на вход соответствующего элемента НЕ 22 kM, 20м или 21-к и через соответствующий полюс

первой группы выходных полюсов 23 1 . ...23тп пятой группы выходных полюсов 25,.. .25 или шестой группы выходных полюсов 261...26Г блока 3 через соответствующий полюс третьей группы входных полюсов 9 ,., .. . 9 г„, второй группы входных полюсов II, .. ... I Ih или первой группы входных по- ,люсов I 0(... I О т поступает на вход одного или нескольких элементов И 6 К блока I. При этом срабатывают электронные ключи 7 цм и снимается напряжение с одной ячейки или строки, столбца матрицы матричной модели и соответствующих полюса или полюсов группы выходных полюсов I 2 (1 .. . I 2 т„, а также сигнала с полюса группы входных полюсов 24 . . . 24 Тп блока 3. При этом прекращается подача импульсов на счетные входы счетчиков 15

км

8М

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

Для возврата схемы в исходное состояние необходимо снять напряжение с шин питания устройства.

В общем случае работа устройства может быть изложена следующим образом (фиг.2).

Перед началом работы в (К,М)-й элемент памяти блока 37 заносят код коэффициента транспортных затрат при перевозках из К-го пункта отправления в М-й пункт назначения, обнуляют счетчики блока 31, в К-й таймер блока 35 заносят код количества запасов в К-м пункте отправления, в М-й таймер блока 36 - потребности М-го пункта назначения, в (К,М)-й таймер блока 34 - ограничения на пропускную способность линии связи из К-го пункта отправления в М-й пункт назначе- ния, После подачи тактовых импульсов на вход 41 устройства разрешается работа К-го таймера блока 35, М-го таймера блока 36 и (К,М)-го таймера блока 34, если (К,М)-й коэффициент транспортных затрат минимальный. Переполнение ддного из указанных таймеров приводит к блокировке чтения информации из тех элементов памяти блока 37, которые выбраны матрицей 40. 1то приводит к выбору нового разрешенного пути с минимальным коэффициентом транспортных затрат, и работа устройства повторяется. План перево

. . JQ $

20

35

25

30Qд50

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

Формула изобретения

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

514746686

чтения К,М-го элемента памяти блока, ка и к счетным входам всех таймеров тактовый вход устройства подключен первого, второго и третьего тайме к счетным входам всех счетчиков бло- ров.