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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4229962/24-24 (22) 13, 04 ° 87 (46) 23.04.89. Бюл. 15 (72) О.Г. Алексеев, С.А. Васильковский, А.А. Гончар, В,M. Крикун и E,Н, Полевов (53) 681 .333(088.8) (56) Гольдштейн E.Г., Юдин Д.В. Зада— чи линейного программирования транспортного типа. — M. Наука, 1969.

Авторское свидетельство СССР

Ф 1362319, кл. G 06 G 7/122, 1986 . (54) УСТРОЙСТВО ДЛЯ ОПТИМИЗАЦИИ ПЛА-.

НА ПЕРЕВОЗОК В ТРАНСПОРТНОЙ СЕТИ (57) Изобретение относится к вычис.лительной технике и может .быть использовано для решения транспортных задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет оптимизации плана перевозок в транспортной сети с ограниченной пропускной способностью. Устройство содержит блок 31 счетчиков, первый блок 32 элементов ИЛИ, второй блок 33 элементов ИЛИ, с первого по

SU 1474668 А 1 (51) 4 G 06 F 15/20, G 06 С 7/122 третий блоки 34-36 таймеров, блок 37 элементов памяти, блок 38 выбора минимального кода, блок 39 приоритетов и матрицу 40 элементов ИЛИ. Кроме того, цифровые обозначения имеют тактовый вход 41 устройства и выходы 42 плана перевозок из пунктов отправления в пункты назначения, Перед началом работы в (K,M) é элемент памяти блока 37 заносят код коэффициента транспортных затрат при перевозках иэ К-ro пункта отправления в M-й пункт назначения > обнуляют счетчики блока 31, в К-й таймер блока 35 заносят код количества запасов в К-м пункте отправления, в M-й таймер блока 36 — потребности M-го пункта назначения, в (K,M) é таймер блока

34 — ограничения на пропускную способность линии связи иэ К-го пункта С отправления в M-й пункт назначения.

При подаче на вход 41 устройства так- Д товых импульсов на выходе (К,М)-ro счетчика блока 31 формируется план перевозок из К-го пункта отправления в M-й пункт назначения, 2 ил °

4:ь

1474668

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

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

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

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

Блок 1 матричной модели транспортной сети .предназначен для задания 25 напряжений U «„„ (К=1,2...,,Т; И=1,2, ° . ...,п, где Т вЂ” количество пунктов отправления; n — число пунктов по требления в матричной модели транспортной сети), пропорциональных ко- 3Р эффициентам транспортных затрат, и содержит матрицу из Тхп ячеек, каждая из которых содержит элемент И 6 „„, электронный ключ 7 „и переменный резистор 8 „, третью группу из Т п входных полюсов 9 „,... 9 „, первую группу из Т входных полюсов 10,... ... 10„вторую группу из и входных полюсов 11, ...11, группу из Т ° n выходных полюсов 12,„...12 4О

Блок управления предназначен для управления работой устройства и содержит генератор 13 импульсов, матрицу из Ткп элементов И 14 „... 14 „, матрицу из Тхп счетчиков 15 „„...15 „, „5 первую группу из и элементов ИЛИ

16,.. ° 16, вторую группу из Т элементов ИЛИ 17,...17 „ первую группу из

Il счетчиков 18„...18,, вторую группу из Т счетчиков 19,...19,, первую группу из и элементов НЕ 20,,20„, вторую группу из Т элементов НЕ 21 „.. ...21,.; матрицу из Т п элементов

НЕ 22 „ ...22,„, первую группу из Т и

ых полюсов иэ Т п входных полюсов 24,„;..24 т„, пятую группу из и выходных полюсов

25,,25 » шестую группу из Т выходных полюсов 26„...26„ вторую группу из Т«п выходных полюсов 27,„ ...27 Г и выходной полюс 28, третью группу из и выходных полюсов 29,...29 „ и четвертую группу из Т выходных полюсов

30,... 307.

На обобщенной структурной схеме устройства (фиг. 2) обозначены: блок

31 счетчиков, первый блок 32 элементов ИЛИ, второй блок 33 элементов

ИЛИ, с первого по третий блоки 34... ...36 таймеров, блок 37 элементов па- . мяти, блок 38 выбора минимального кода, блок 39 приоритетов, матрицу 40 элементов ИЛИ, тактовый вход 41 устройства и выходы 42 плана перевозок из пунктов отправления в пункты назначения.

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

Перед началом работы с помощью переменных резисторов 8 „ ...8 „, задают напряжение U „, пропорциональное величинам (R-3„ ), где Къмакс, 3 ц, а 3 „ — коэффициенты транспортных затрат. Счетчики 18,...18„, 19,...19 и 15 „ ...15 „ устанавливают в состояние (N-V ), (N-W„) и (N-А „ ) соответственно, где V равно запасам

К-ro пункта отправления, W „ — потребностям М-ro потребления, А „„— максимально возможные перевозки на маршруте из К-го пункта отправления в M-й пункт назначения, N — емкость счетчика. При поступлении сигнала на вход пуска устройства импульсы с выхода генератора 13 импульсов поступают на первые входы элементов И

14,„ ...14 т„, на другой вход одного из которых через соответСтвующий по— люс группы входных полюсов 24, ...24 » поступает сигнал с блока 2 выбора максимального коэффициента транспортных затрат. С выхода элемента И 14 соответствующего минимальному элементу матрицы коэффициентов

II 3 „„11транспортных затрат, импульсы поступают на счетный вход счетчика

15 соответствующего минимальному элементу, и через элементы ИЛИ 16„ и 17 подаются на счетные входы счетk, чиков 18 и 19 „, соответствующих столбцу и строке, на пересечении которых находится этот минимальный элемент. При заполнении одного иэ счетчиков 15 18 „или 19 к сигнал о переполнении поступает на вход соответствующего элемента НЕ 22, 20 или

21 и через соответствующий полюс

1474668 первой группы выходных полюсов 23

11 ...23», пятой группы выходных полюсов 25,...25 „ кли шестой группы выходных полюсов 26„...26г блока 3 через соответствующий полюс третьей

5 группы входных полюсов 9,„... 9,-„, второй группы входных полюсов 1, ...11„или первой группы входных по, люсов 10,...10, поступает на вход одного или нескольких элементов И 6 „„ блока 1. При этом срабатывают элект— ронные ключи 7 „„ и снимается напряжение с одной ячейки или строки, столбца матрицы матричной модели и соответствующих полюса или полюсов гp fllllbl BblXop,HblX ITOJHOCOB I 2 „... 1 2 т „, а также сигнала с полюса группы входных полюсов 24,„ ...24 блока 3. При этом прекращается подача импульсов 20 на счетные входы счетчиков 15 „, 18 11 и 19к. Далее снова определяется минимальный элемент матрицы транспортных затрат и устройство работает аналогично рассмотренному первому 25 шагу решения.

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

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

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

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

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

Устройство для оптимкзацкк плана перевозок в транспортной сети, содержащее блок кз Т.п (где Т вЂ” коли чество пунктов отправления; Il — коли чество пунктов потребления в транспортной сети) элементов памяти, блок выбора минимального кода и блок приоритетов, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет оптимизации плана перевозок в транспортной сети с ограниченной пропускной способностью, в него введены блок из Т и счетчиков, первый блок из Т элементов ИЛИ, второй блок ,из и элементов ИЛИ, первый блок из п Т - àéìåðîâ,,второй блок из Т таймеров, третий блок из п таймеров к матрица элементов ИЛИ, причем выход

К,M-го элемента памяти блока (К=l ...,Т, M=I,...,n), подключен к К,М-му информационному входу блока выбора минимального кода, К;Г1-й выход позиции мипимальногo кода которого подключен к К,М-му входу блока приорктетов, выход позиции с К,М-м приоритетом которого подключен к входу разрешения работы К,M-ro таймера первого блока, к М-му входу К-ro элемента

ИЛИ первого блока, к К-му входу М-го элемента ИЛИ второго блока и к входу разрешения счета К,М-ro счетчика блока, информационный выход которого является выходом плана перевозок из

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

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

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

ИЛИ М-й строки матркцы, выход которого подключен к входу блокировки!

474668

Составитель А. Мишин

Редактор О. Юрковецкая Техред Л.Сердюкова Корректор И. Муска

Заказ 1896/48 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, 3-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 чтения К,M ro элемента памяти блока, тактовый вход устройства подключен к счетным входам всех счетчиков блока и к счетным входам всех таймеров первого, второго и третьего таймеров,