Устройство для решения транспортных задач

 

Изобретение относится к вычислительной технике и может быть использовано для решения распределительных задач и, кроме того, транспортных залинейного программирования. Цель изобретения - расширение класса решаемых задач за счет распределения ресурсов по работам. Устройство содержит ,матричную модель 1 транспортной сети, блок 3 выбора максимума и блок 2 управления. Новым в устройстве является конструктивное выполнение матричной модели транспортной сети и конструктивное выполнение блока управления , Устройство позволяет за конечное число шагов решать как распределительные , так и транспортные задачи линейного программирования. 3 ил.

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

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

РЕСПУБЛИК (51)4 С 06 Р 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3971171/24-24 (22) 30.10.85 (46) 23.04.8?. Вюл. 9 15 (72) О.Г.Алексеев, В.М.Крикун, А.Н.Мардас, В.П.Темнов и Н.И.Ячкула (53) 681.333 (088.8) (56) Авторское свидетельство СССР К- 219924, кл. G 06 G 7/122, 1968,.

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

9 1263094, кл. G 06 С 7/122, 01984. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ (57) Изобретение относится к вычислительной технике и может быть использовано для решения распределительных

„„SU„„>305705 задач и, кроме того, транспортных за дач линейного программирования, Цель изобретения — расширение класса решаемых задач за счет распределения ресурсов по работам. Устройство содержит матричную модель 1 транспортной сети, блок 3 ьыбора максимума и блок

2 управления, Новым в устройстве является конструктивное выполнение матричной модели транспортной сети и конструктивное выполнение блока управления, Устройство позволяет за конечное число шагов решать как распределительные, так и транспортные задачи линейного программирования. 3 ил.

1 13057

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

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

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

Устройство для решения транспортных задач содержит матричную модель

1 транспортной сети, блок 2 управления и блок 3 выбора максимума.

Матричная модель 1 транспортной сети содержит матрицу ш и ячеек 4, где ш — число строк а и — число

У

25 столбцов матрицы, источник 5 опорного напряжения, переключатель 6, группу элемен-ов ИЛИ 7, группу регистров

8, первую 9, вторую 10 и третью 11 группы входных полюсов, первую 12, вторую 13 и третью 14 группы выход30 ных полюсов. Каждая ячейка 4 матрицы матричной модели 1 транспортной сети содержит первый задатчик 15 коэффициентов транспортных затрат, . второй задатчик 16 коэффициентов тран- 35 апортных затрат, операционный усилитель 17, второй ключ 18, первый ключ

19, аналого -цифровой преобразователь

20 и элемент И 21.

Блок 2 управления содержит эле .мент 22 индикации, источник 23 опорного напряжения, первый переключатель 24, генератор 25 одиночных импульсов, первую группу входных полюсов 26, первую 27 и вторую 28 группы выходных полюсов, вторую группу 29 входных полюсов, третью группу входных полюсов 30, первую. группу элементов НЕ 31, вторую группу элементов НЕ 32, первую группу элементов ИЛИ 33, вторую группу элементов ИЛИ

34, первую группу счетчиков 35, вто" рую группу счетчиков 36, третью группу счетчиков 37 и четвертую группу счетчиков 38, группу операционных усилителей 39, шифратор 40, первый ,элемент И 41, второй элемент И 42, элемент ИЛИ 43, узел 44 регистрации, ключ 45, второй переключатель 46, матрицу 47 элементов И.

Кроме того, фиг.1 обозначена группа входов 48 блока 3 выбора максимума и 1 руппа выходов 49 блока 3 выбора максимума, Задатчики 15 и 16 коэффициентов транспортных затрат могут быть выполнены на потенциометрах.Матричная модель 1 транспортной сети предназначена для задания напряжений

U" и П. (z — 1,2, ...,m; g — 1,2,..., n), с

ir где m — число строк, а п — число столбцов в матрице матричной модели транспортной сети) определяемых по значениям коэффициента. транспортных затрат с, и коэффициента использова1J ния единицы ресурса d; (соответственно коэффициент недоиспользования грузоподъемности и грузоподъемность транспортного средства i-го вида по

j-му виду груза в транспортно-распределительной задаче).

Блок 2 управления предназначен для управления работой устройства в ходе решения задачи, индикации результатов и сигнализации об окончании решения.

Блок 3 выбора максимума предназначен для определения ячейки .;„ матрицы модели 1 в которой отношение нап9 ряя<ений U, /П;„на полюсах 11, „ и

10;", пройорциональное отношению

d " "/с = М в математической постац нонке распределительной задачи, максимально.

В основу принципа работы устройства положено определение плана распределения ресурсов путем максималь" но возможного назначения на коммуникацию с максимальным отношением коэффициента использования единицы ресурса и коэффициенту транспортных затрат, т.e, d; /с„

Перед началом решения распределительной задачи (после включения вы- ключателя б модели 1) с помощью задатчиков 15 и 16 " задаются напрясг 3 жения П,; и П;, йропорциональные величинам с„" (коэффициенту транспортных затрат) и Й, „ (коэффициенту использования единицы ресурса), так как они поступают от датчиков исходной информации, а также включением второго переключателя 46 блока 2 переводятся в нулевое состояние счетчики 35, а счетчики 37; и 38i — в состояние (И вЂ” а, ) и (И вЂ” Ь ) соответственно, где а, равны запасам -го

3 13057 ресурса (например, i-ro вида транспортных средств в транспортно-распределительной задаче),Ъ вЂ” потребностям j-ro вида (например, j-го вида грузов в транспортно-распредели- 5 тельной задаче), N — - емкость счетчика (i = 1, 2, ...,m; j = 1, 2,...,n).

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

Включается выключатель 24 блока 2 10 управления. При этом с выхода генератора 25 одиночных импульсов на один из входов матрицы 47 элементов И поступают импульсы. В каждой ячейке 4; матрицы модели 1 операционный усили- 15 тель ° 17 производит деление U; /Б; с с

= d " /с напряжений U. и U" сня1< i3 1i 1< У тых с помощью з адатчиков 1 6; и 1 5;; соответственно . С выхода опе р ационйого усилителя 1 7 аналоговый сигнал, 20

1) пропорциональныи Й„ /с; через замкнутую исполнительную цепь электронного ключа 19 поступает на выход11 ной полюс 14; модели 1 и далее на вход 48 блока 3. На выходе 49," 25

11 блока 3, соответствующем ячейке 4;. матрицы модели 1 с максимальным отс ношением U; /U; =d /с;>, появится сигнал. Для определенности в дальнейшем считаем, что таковыми являются 30 выход 49„ блока 3 и соответственно ячейка 4„ 1.

С выхода 49н блока 3 через входной полюс 29„ блока 2 сигнал поступает на первый вход элемента И 47« матри-35 цы. Элемент И 47„ открывается и счетчик 35 начинает суммировать им« пульсы, поступающие от генератора 25 одиночных импульсов блока 2, реализуя таким образом запоминание назначения 40

<). х . на коммуникацию из d< в b< . По цепи выдачи счетчика 35„ его содержимое через шифратор 40 поступает на узел регистрации 44, визуально отображающий в соответствующий позиции экрана величину назначения на коммуникацию из а, в Ъ,. Кроме того, с выхода элемента И 47„ импульсы поступают через элемент ИЛИ 33, на счетный вход счетчика 36,, а через элемент ИЛИ 34< — и на счетный вход счетчика 37, . Суммирование импульсов в счетчике 37< с его содержимым соответствует уменьшению запасов а< первого в да на величину назначения 55 х " на коммуникацию из а, в Ь< .

1<

С выхода 49и блока 3 через входной полюс 9<, блока 1 сигнал посту05 4 пает и на управляющий вход клича 18«, через исполнительную цепь которого напряжение Б„ с задатчика 16„ nod ступает на вход аналого-цифрового преобразователя 20«, осуществляющий поразрядный алгоритм преобразования.

По завершении преобразования аналогового сигнала в цифровой код, что заключается в обнулении регистра сдвига в преобразователе 20«, с его инвертирующего выхода поступит сигнал на вход элемента ИЛИ 7< . С выхода преобразователя 20 „параллельный цифровой код поступает на соответствующий вход регистра 8, (на другие его входы могут поступать сигналы от ij ячеек первого столбца матрицы матричс ной модели 1, где отношение U " /U, элемента ИЛИ 7, сигнал поступает на вход управления считыванием регистра 8<, содержимое которого через выходной полюс 13, матричной модели 1 и входной полюс 26, блока 2 поступает на второй вход операционного усилителя 39, блока 2. Одновременно с выхода элемента ИЛИ 7< матричной модели 1 сигнал через выходной полюс .

12< матричной модели 1 и входной полюс 30< блока 2 поступает на вход управления считыванием счетчика 36< второй группы счетчиков блока 2, содержимое которого при этом поступает на первый вход операционного усилителя 39< . Операционный усилитель 39< производит перемножение величин Й« и x<, определяя таким образом величину потребления ресурса на коммуникации из а, в b ° С выхода операционного усилителя 39< произведение d« х

x х поступает на счетный вход счетн чика 3$ < третьей группы счетчиков блока 2. В дальнейшем устройство работает аналогично. При заполнении счетчика 38 третьей группы счетчи1

<ков блока 2, что соответствует удовлетворению потребностей j-ro вида, I сигнал о переполнении с выхода счетчика поступает на вход элемента НЕ

32 и на 1-й вход элемента И 41. При этом исчезает сигнал на входах элементов И 21<„ ячейки 4 1-ro столбца матрицы матричной модели 1 транспортной сети и )-й столбец оказывается отключенным от источника опорного напряжения. Аналогично при заполнении счетчика 37< первой группы счетчиков блока 2, что соответствует

13057 полному исчерпанию запасов i-ro вида ресурсов, оказывается отктпоченной от источника опорного напряжения i-я строка матрицы ячеек .4;„ модели 1.

При заполнении всех счетчиков 38 тре- 5 тьей группы или всех счетчиков 37 первой группы сигнал с выхода элемента И 4j или И 42 соответственно .через элемент ИЛИ 43 поступает на управляющий вход ключа 45 блока 2, ключ 1О

45 подключает элемент 22 индикации к источнику 23 опорного напряжения.

Загорание элемента индикации свидетельствует об окончании решения. Оп" тимальный план распределения ресур"

Сов в цифровом виде высвечивается на экране узла регистрации.

Устройство допускает решение транспортной задачи линейного программирования, реализуя тем самым возможности известного устройства. Для этого перед началом решения (после включения выключателя 6 матричной модели 1) с помощью задатчиков 15, эа25 даются напряжения U;. пропорциональные с, „ - коэффициентам транспортных затрат, а на задатчиках 16," устанавливается напряжение U; = 1 (в мила ливольтах или микровольтах в зависимости от избранной единицы измерения напряжения). Нажатием выключателя кнопочного блока 2 счетчики 37 и

38 блока 2 устанавливаются в состоя1. ние (N-a; ) и (N-b ) соответственно, где а; - запасы в i-м пункте отправ- 35 ления, а b — потребности в j-м пункте назначения, N — емкость счетчика.

Устройство при этом работает аналогично, а план перевозок оказывается при этом высвеченным на устройстве @ отображения в цифровом виде. о

Для возврата схемы в исходное состояние размыкают первый переключатель

24 блока 2 и переключатель 6 блока 1, отсоединяя элементы схемы от источников опорного напряжения.

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

50 . Устройство для решения транспортных задач, содержащее матричную модель транспортной сети, блок выбора максимума и блок управления, матричная модель транспортной сети содер55 жит матрицу ш п ячеек, каждая ячейка которой содержит первый задатчик коэффициентов транспортных затрат, 05 6 первый ключ и элемент И, выход которого подключен к управляющему входу первого ключа, блок управления содержит генератор одиночных импульсов, матрицу m п элементов И, первую группу из ш и счетчиков, первую группу элементов НЕ, две группы элементов ИЛИ, вторую и третью. группы счетчиков, первый и второй элементы И, элемент ИЛИ, ключ, элемент индикации, источник опорного напряжения, первый и второй переключатели, причем первые входы элементов И матрицы блока управления объединены и подключены к выходу генератора одиночных импульсов, вход запуска-которого подключен через первый переключатель блока управления к выходу источника опорного напряжения блока управления, выход каждого из элементов И матрицы блока управления подключен к счетному входу одноименного счетчика первой . группы, входы начальной установки всех счетчиков первой и третьей групп блока управления объединены и через второй переключатель подключены к выходу источника опорного напряжения блока управления, выход источника опорного напряжения блока управления подключен к информационному входу ключа блока управления, выход которого подключен к входу элемента индикации блока управления, выходы первого и второго элементов И блока управления подключены соответственно к первому и второму входам элемента ИЛИ, выход которого подключен к управляющему входу ключа блока управления, выход каждого j-го элемента ИЛИ первой группы блока управления подключен к счетному входу j-ro счетчика второй группы блока управления, выход каж- . дого элемента ИЛИ второй группы бло(KB управления подключен к счетному входу i-ro счетчика третьей группы блока управления, выход которого подключен к входу i-го элемента НЕ первой группы блока управления, выход каждого j-ro элемента И каждой i-й строки матрицы блока управления подключен к j-му входу i-ro элемента ИЛИ второй группы блока управления, выход каждого i-го элемента И каждого

j-го столбца матрицы блока управления подключен к i-му входу j-ro Элемента

ИЛИ первой группы блока управления, первые входы элементов И всех ячеек каждой i-й строки матрицы матричной

7 13057 модели транспортной сети объединены и подключены к выходу i-го элемента

НЕ первой группы блока управления, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых за- 5 дач за счет распределения ресурсов по работам, матричная модель транспортной сети содержит источник опорного напряжения, переключатель, группу из и элементов ИЛИ, группу из ш регист- 10 ров, в блок управления введены узел регистрации, вторая группа элементов

НЕ, четвертая группа счетчиков, группа операционных усилителей, каждая ячейка матрицы матричной модели тран- 15 спортной сети содержит второй задатчик коэффициентов транспортных затрат, операционный усилитель, второй ключ, аналого-цифровой преобразователь, причем входы задатчиков козф- 20 фициентов транспортных затрат объединены и через переключатель матричной модели транспортной сети подключены к выходу источника опорного нап= ряжения матричной модели транспортной25 сети, выходы первого и второго задатчиков коэффициентов транспортных затрат каждой ячейки матрицы матричной модели транспортной сети подключены соответственно к первому и второму 30 информационным входам операционного усилителя той же ячейки матрицы матричной модели транспортной сети, выход второго задатчика коэффициентов транспортных затрат каждой ячейки 35 матрицы подключен к информационному входу второго ключа той же ячейки матрицы матричной модели транспортной сети, выход которого подключен к входу аналого-цифрового преобразова- 40 теля той же ячейки матрицы, прямой выход аналого-цифрового преобразователя каждой i-й ячейки (i=1,2,...,m) каждого j-го столбца (j=1, 2, . °,,и) матрицы матричной модели транспорт- 45 ной сети подключен к i-му информационному входу j-ro регистра группы матричной модели транспортной сети, инверсный выход аналого-цифрового преобразователя каждой i-й ячейки каждого j-ro 50 столбца матрицы матричной модели транспортной сети подключен к i-му входу j-го элемента ИЛИ группы матричной модели транспортной сети, выход которого подключен к входу управ-55

05 8 ления считыванием одноименного регистра группы матричной модели транспортной сети и к входу управления считыванием одноименного счетчика второй группы блока управления, вы- ход операционного усилителя каждой ячейки матрицы матричной модели транспортной сети подключен к информационному входу первого ключа той же ячейки матрицы матричной модели транспортной сети, вторые входы элементов

И всех ячеек каждого j-го столбца матрицы матричной модели транспортной сети объединены и подключены к выходу j-го элемента НЕ второй группы блока управления, управляющий вход, второго ключа каждой ячейки матрицы матричной модели транспортной сети подключен к соответствующему выходу блока выбора максимума, выход первого ключа каждой ячейки матрицы матричной модели транспортной сети подключен к соответствующему входу блока выбора максимума, каждый выход блока выбора максимума подключен к второму входу соответствующего элемента И матрицы блока управления,входы начальной установки всех счетчиков четвертой группы блока управления объединены и через второй переключатель подключены к выходу источника опорного напряжения блока управления, выход каждого счетчика первой группы подключен к соответствующему входу . шифратора, выход которого подключен к входу узла регистрации, выход каждого j ãî счетчика второй группы блока управления подключен к первому информационному входу j-го операционно-, го усилителя группы блока управления, второй информационный вход которого подключен к выходу j-ro регистра группы матричной модели транспортной сети, выход j-ro операционного усилителя группы блока управления подключен к счетному входу j — ro счетчика четвертой группы блока управления, выход которого подключен к входу j-ro элемента НЕ второй группы блока управления и к j ìó входу первого элемента И блока управления, выход каждого i-ro счетчика третьей группы блока управления годключен к i-му входу второго элемента И блока управления, 1305705 ав

Составитель Т.Сапунова

Техред В.Кадар

Корректор И.Муска

Редактор С.Пекарь

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

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4