Устройство для решения транспортных задач Советский патент 1987 года по МПК G06F15/173 

1 . 1

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

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

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

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

Матричная модель 1 транспортной сети содержит матрицу ш- п ячеек 4, где m - число строк, an- число столбцов матрицы, источник 5 опорного напряжения, переключатель 6, группу злементов ИЛИ 7, группу регистров 8, первую 9, вторую 10 и третью 11 группы входных полюсов, первую 12, вторую 13 и третью 14 группы выходных полюсов. Каждая ячейка 4 матрицы матричной модели 1 транспортной сети содержит первый задатч1-ж 15 коэффициентов транспортных затрат, второй задатчик 16 коэффициентов тра спортных затрат, операционный усили™ тель 17, второй ключ 18, первый ключ 19, аналого-цифровой преобразователь 20 и элемент И 21.

Блок 2 управления содержит эле- .мент 22 индикации, источник 23 опорного напряжения, первый.переключатель 24, генератор 25 одиночных импульсов, первую группу входньш полюсов 26, первую 27 и вторую 28 груп- пь1 эыходных полюсов, вторую группу 29 входных полюсов, третью группу вход- ных полюсов 30, первую.группу элементов НЕ 31, вторую группу элементов НЕ -32, первую группу элементов ИЛИ 33, вторую группу элементов ИЛИ 34, первую группу счетчиков 35, вторую группу счетчиков 36, третью группу счетчиков 37 и четвертую группу счетчиков 38, группу операционных усилителей 39, шифратор 40, первый элемент И 41, второй элемент И 42, элемент ИЛИ 43, узел 44 регистрации.

5

ключ 45,

5 симально,

второй переключатель 46, матрицу 47 элементов И.

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

предназначена для задания напряжений HUfj (i 1,2, ...,in; j 1,2,,..,п),

0

5

0

где m - число строк, а п - число столбцов в матрице матричной модели транспортной сети) определяемых по значениям коэффициента транспортных затрат с;: и коэффициента использования единицы ресурса dj: (соответственно коэффициент недоиспользования грузоподъемности и грузоподъемность транспортного средства i-ro вида по j-му виду груза в транспортно-рас- пределительной 3aji;a4e).

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

Блок 3 выбора максимума предназначен для определения ячейки L;; матрицы модели 1,

d

/Uij

в которой отношение нап- с

на полюсах 11

пропорциональное отношению

и

ряжений и- 10;

d ; /С; - jfj. В математической постановке распределительной задачи, максимально,

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

Перед началом решения распределительной задачи (после включения выключателя б модели 1) с помощью за- 15с .и 16- задаются напря- и U;: , пропорциональные

датчиков жения U;: величинам с

М

(коэффициенту транспортных затрат) и dji (коэффициенту использования единицы ресурса), так как они поступают от датчиков исходной информации, а также включением второго переключателя 46 блока 2 переводятся в нулевое состояние счетчики 35IJ , а счетчики 37 и состояние (N - а) и (N - b

38; - в ) соответственно, где а; равны запасам 1-го

313057054

ресурса (например, i-ro вида тран- пает и на управляющий вход клгзча 18,, спортных средств в транспортно-рас- пределительной задаче) ,Ь . - потребностям j-ro вида (например, j-ro вида грузов в транспортно-распредели- тельной задаче), N - емкость счетчика (i 1,2,...,тп; 3 1,2,..,,п).

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

через исполнительную цепь которого напряжение и с задатчика 16„ поступает на вход аналого-цифрового 5 преобразователя 20, , осуществляющий

поразрядный алгоритм преобразования. По завершении преобразования аналогового сигнала в цифровой код, что заключается в обнулении регистра включается выключатель 24 блока 2 fO сдвига в преобразователе 20„ , с его управления. При этом с выхода генера- инвертирующего выхода поступит сигнал .тора 25 одиночных импульсов на один на вход элемента ИЛИ 7,. С выхода пре- из входов матрицы 47 элементов И по- образователя 20 „ параллельный циф- ступают импульсы. В каждой ячейке 4, ровой код поступает на соответствую- матрицы модели 1 операционный усили- 15 щий вход регистра 8, (на другие его тель.17; производит деление U- входы могут поступать сигналы от ij d;: /с- напряжений U,- и U-j , сня- ячеек первого столбца матрицы матрич- тых с помощью задатчиков 16;j и 15;j ной модели 1, где отнощение Ujj соответственно. С выхода операционно- d;j /с,-- lS ;j y,, ,, /с„ .С выхода

20 элемента ИЛИ 7, сигнал поступает на вход управления считыванием регистра 8, , содержимо е которого через выходной полюс 13) матричной модели 1 и входной полюс 26, блока 2 поступает на второй вход операционного усилителя 39, блока 2. Одновременно с выхода элемента ИЛИ 7, матричной модели 1 сигнал через выходной полюс 12, матричной модели 1 и входной по-

го усилителя 17;: аналоговый сигнал, пропорциональный d,-; /с ;; через замкнутую исполнительную цепь электронного ключа 19, ; поступает на выходной полюс 14л модели 1 и далее на вход 48; блока 3. На выходе 49ij блока 3, соответствующем ячейке 4-: матрицы модели 1 с максимальным отношением U;- /и- dq /с, , пойвится сигнал. Для определенности в дальнейшем считаем, что таковыми являются 30 люс 30, блока 2 поступает на вход уп25

выход 49,. блока 3 и соответственно ячейка 4, матрицы матричной модели 1. С выхода 49,, блока 3 через входной полюс 29 (, блока 2 сигнал поступает

равления считыванием счетчика 36, второй группы счетчиков блока 2, содержимое которого при этом поступает на первый вход операционного усилитена первый вход элемента И 47,, матри-з5 ля 39, . Операционный усилитель 39, цы. Элемент И 47,, открывается и счет- производит перемножение величин d,.

чик 35,. начинает суммировать ими X,

определяя таким образом велипульсы, поступающие от генератора 25 чину потребления ресурса на коммуни- одиночных импульсов блока 2, реализуя кации из а, в Ь, . С выхода операцион- таким образом запоминание назначения 40 ного усилителя 39, произведение d,,«

xj.- на коммуникацию из d, в Ь, . По цепи вьщачи счетчика 35,, его содержимое через шифратор 40 поступает на узел регистрации 44, визуально отображающий в соответствующий позиции экрана величину назначения на коммуникацию из а, в Ь,. Кроме того, с выхода элемента И 47„ импульсы поступают через элемент ИЛИ 33, на

fx,| поступает на счетный вход счетчика 38 I третьей группы счетчиков блока 2. В дальнейшем устройство работает аналогично. При заполнении 45 счетчика 38 ; третьей группы счетчи- IKOB блока 2, что соответствует удовлетворению потребностей j-ro вида, сигнал о переполнении с выхода счетчика поступает на вход элемента НЕ

счетньй вход счетчика 36, , а через 32 и на j-й вход элемента И 41, При

элемент ИЛИ 34, - и на счетный вход счетчика 37, . Суммирование импульсов в счетчике 37, с его содержимым соответствует уменьшению запасов а, первого вида на величину назначения х;- на коммуникацию из а, в Ь, .

С выхода 49(, блока 3 через входной полюс 9(, блока 1 сигнал посту55

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

пает и на управляющий вход клгзча 18,,

через исполнительную цепь которого напряжение и с задатчика 16„ поступает на вход аналого-цифрового преобразователя 20, , осуществляющий

20

30

25

равления считыванием счетчика 36, второй группы счетчиков блока 2, содержимое которого при этом поступает на первый вход операционного усилитеи X,

определяя таким образом вели fx,| поступает на счетный вход счетчика 38 I третьей группы счетчиков блока 2. В дальнейшем устройство работает аналогично. При заполнении счетчика 38 ; третьей группы счетчи- KOB блока 2, что соответствует удовлетворению потребностей j-ro вида, сигнал о переполнении с выхода счетчика поступает на вход элемента НЕ

32 и на j-й вход элемента И 41, При

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

полному исчерпанию запасов вида ресурсов, оказывается отключенной от источника опорного напряжения i-я строка матрицы ячеек .4;: модели 1. При заполнении всех счетчиков 38 тре- 5 тьей группы или всех счетчиков 37t первой группы сигнал с выхода элемента И 41 или И 42 соответственно через элемент ИЛИ 43 поступает на уп13057056

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

равляющий вход ключа 45 блока 2, ключ О элемент ИЛИ, ключ, элемент индика 5

45 подключает элемент 22 индикации к источнику 23 опорного напряжения, Загорание элемента индикации свидетельствует об окончании решения. Оптимальный план распределения ресурсов в цифровом виде высвечивается на экране узла регистрации.

Устройство допускает решение транспортной задачи линейного программирования, реализуя тем самым возмож- 20 ности известного устройства. Для этого перед началом решения (после включения выключателя 6 матричной модеза.-25

ли 1) с помощью задатчиков 15;j даются напряжения Uj: , пропорциональ ные С -коэффициентам транспортных затрат, а на задатчиках устанавливается напряжение uf- 1 (в милливольтах или микровольтах в зависимости от избранной единицы измерения напряжения). Нажатием выключателя кнопочного блока 2 счетчики 37; и 38j блока 2 устанавливаются в состояние (N-a) и (N-bj) соответственно, где а; - запасы в i-м пункте отправления, а bj - потребности в j-м пункте назначения, N - емкость счетчика. Устройство при этом работает аналогично, а план перевозок оказывается при этом высвеченным на устройстве

отображения в цифровом виде.

„о

Дпя возврата схемы в исходное состояние размыкают первьй переключатель 24 блока 2 и переключатель 6 блока 1,

ции, источник опорного напряжения, первый и второй переключатели, причем первые входы элементов И матрицы блока управления объединены и подключены к выходу генератора одиночных ш-шульсов, вход запуска-которого подклгючен через первый переключатель блока управления к выходу источника опорного напряжения блока управления, выход каждого из элементов И матрицы блока управления подключен к счетному входу одноименного счетчика первой . группы,входы начальной установки всех счетчиков первой и третьей групп блока управления объединены и через второй переключатель подключены к выходу источника опорного напряжения блока управления, вькод источника опорного напряжения блока управления подключен к информационному входу ключа о блока управления, выход которого подключен к входу элемента индикации блока управления, выходы первого и второго элементов И блока управления 5 подключены соответственно к первому и второму входам элемента ИЛИ, выход которого подключен к управляющему входу ключа блока управления, выход каждого j-ro элемента ИЛИ первой группы блока управления подключен к счетному входу j-ro счетчика второй группы блока управления, выход каж- . доГо элемента ШШ второй группы бло- (ка управления подключен к счетному

30

40

отсоединяя элементы схемы от источни- входу i-ro счетчика третьей группы

ков опорного напряжения.

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

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

чиков, первьй и второй Элементы И,

элемент ИЛИ, ключ, элемент индика5

0

5

ции, источник опорного напряжения, первый и второй переключатели, причем первые входы элементов И матрицы блока управления объединены и подключены к выходу генератора одиночных ш-шульсов, вход запуска-которого подклгючен через первый переключатель блока управления к выходу источника опорного напряжения блока управления, выход каждого из элементов И матрицы блока управления подключен к счетному входу одноименного счетчика первой . группы,входы начальной установки всех счетчиков первой и третьей групп блока управления объединены и через второй переключатель подключены к выходу источника опорного напряжения блока управления, вькод источника опорного напряжения блока управления подключен к информационному входу ключа о блока управления, выход которого подключен к входу элемента индикации блока управления, выходы первого и второго элементов И блока управления 5 подключены соответственно к первому и второму входам элемента ИЛИ, выход которого подключен к управляющему входу ключа блока управления, выход каждого j-ro элемента ИЛИ первой группы блока управления подключен к счетному входу j-ro счетчика второй группы блока управления, выход каж- . доГо элемента ШШ второй группы бло- (ка управления подключен к счетному

0

0

0

5

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

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

да, б, 3l}n: 2Sn.

±

гЗтп.

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

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

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

Техред В.Кадар Корректор И.Муска

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

ВНИИПИ Государственного комитета СССР

. по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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