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

 

Изобретение относится к вычислительной технике и может быть использовано при решении транспортных задач по критерию времени, Целью изобретения является упрощение устройства . Функциональная схема устройства разработана таким образом, что устройство может быть выполнено как на стандартных злементах вычислительной техники, так и на специальных модулях, практически совпадающих с блоками. Использование таких модулей; дает возможность решать транспортные задачи любой размерности без изменения структуры устройства и за короткий промежуток времени. Устройство содержит блок задатчиков коэффициентов транспортных затрат, коммутатор, блок сравнения, блок выбора максимума , блок хранения промежуточного результата и блок управления. Подготовка устройства к работе достаточно проста и не требует высокой квалификации оператора,- а результаты решения выдгиотся на индикаторных счетчиках в удобном цифровом виде. Кроме того, при замене потенциометров-аналогов датчиками исходной информации и при подключении через цифроаналоговые преобразователи к исполнительным механизмам устройство может использоваться в автомат 1зированных или автоматических системах управляющих процессами или объектами. 6 ил. а 5 (Л со vj со | 00

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

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

РЕСПУБЛИК

„„SU„„1379?87 А 1 (" > с.и д

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К ASTOPCKOMY СВИДЕТЕЛЬСТВУ (21) 3931221/24-24 (22) 18.07.85 (46) 07.03.88. Бюл. Р 9 (72) О.Г.Алексеев, В.М.Крикун, А.Н.Иардас и Н.И.Ячкула (53) 681.3 (088,8) (56) Авторское свидетельство СССР

Ф 219924, кл. G 06 G 7/76, 1968.

Авторское свидетельство СССР по заявке В 3853670/24, кл. С 06 G 7/122, 1985, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ (57) Изобретение относится к вычислительной технике и иожет быть использовано при решении транспортных задач по критерию времени. Целью изобретения является упрощение устройства. Функциональная схема устройства разработана таким образом, что устройство может быть выполнено как на стандартных элементах вычислительной техники, так и на специальных модулях, практически совпадающих с блоками. Использование таких модулей дает возможность решать транспортные задачи любой размерности беэ изменения структуры устройства и за короткий промежуток времени. Устройство содержит блок эадатчиков коэффициентов транспортных затрат, -коммутатор, блок сравнения, блок выбора максимума, блок хранения промежуточного результата и блок управления. Подготовка устройства к работе достаточно проста и не требует высокой квалифи, кации оператора, а результаты решения выдаются на индикаторных счетчиках в удобном цифровом виде. Кроме того, при замене потенциометров-аналогов датчиками исходной информации и при подключении через цифроаналоговые преобразователи к исполнительным механизмаи устройство может использоваться в автоматизированных или автоматических системах управляющих процессами или объектаии.

6 ил, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

1379787 г

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

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

»а фиг.3 — 6 — структурные схемы 15 блоков сравнения, выбора максимума, коммутации и хранения промежутачнага результата соответственно. устройство для решения транспортных задач содержит блок l задания 20 коэффициентов транспортных затрат, выполненный в виде матрицы задатчиков коэффициентов транспортных затрат, блок 2 сравнения, блок 3 выбора максимума, блок 4 коммутации, блок 5 хранения промежуточного результата и блок 6 управления.

Блок 1 задания коэффициентов транспортных затрат (фиг.2) содержит группу входов 7, — 7, группу входов 30

8,- 8п вход 9, задатчики 10 коэффициентов транспортных затрат, элементы И 11, ключи 12 с пративафазным управлением (где S — прямой, а К— инверсный управляющие входы ), потенциометры 13, коммутаторы 14, выход 15 окончания просмотра всех строк и столбцов, выходы 16„- 16„„, вход 17, входы 18,„— 18„„, входы 19„- 19 разделительные диоды 20,„ — 20 (m п)-входовый элемент И 21 °

Блок 2 сравнения (фиг. 3) содержит элементы И 22 „— 22 „, элемент ИЛИ

23, генератор 24 единичных импульсов, группу входов 25„ — 25,, группы 45 входов 26„— 26 „и 27, — 27 и выход 28.

Блок 3 выбора максимума (фиг ° 4) содержит входные резисторы 29,,—

29„, операционные усилители 30 „—

30 „ 31 „ - 31 „ обратной связи, диоды 32 „ — 32 „ обратной связи, развязывающие диоды 33 „33 „„, ключи 34 „ - 34 „, группу входов

35 „— 35,„„, группу выходов 36 „- 36„,„, Блок 4 коммутации (фиг, 5 ) содержит клкчи 37,„ — 37 „с противафазным управлением, элементы 38«- ЗЯ,„„залержки, формирователи 39 „ — 39 „ импульсав, группу информационных входов

40„ — 40 „, группу информационных выходов 41 „ — 41 „, дополнительный информационный выход 42, группу прямых управляющих входов 43»- 43„, инверсный управляющий вход 44, вход

45 разрешения формирования выходного сигнала, Блок 5 хранения промежуточного результата (фиг,Ь ) содержит группу элементов И 46„- 46 „, первую группу элементов ИЛИ 47, — 47„, вторую группу элементов ИЛИ 48„- 48„„, первую группу счетчиков 49, — 49„, вторую группу счетчиков 50, — 50, первую группу инверторов 51, — 51„, вторую группу инверторов 52„- 52, первую группу ключей 53, — 53 „ с инвертирующим управляющим входом, вторую группу ключей 54, — 54 с инвертирующим управляющим входом, элементы

И 55 и 56, элемент ИЛИ 57, вход 58 начальной установки, тактирующий вход 59, группу информационных входов 60 „ — 60 „, выход 61 индикации работы, группу выходов 62, — 62 „ значений запасов пунктов отправления, группу выходов 63„- 63 значений потребностей пунктов назначения, группу выходов 64,- 64 пронормированных значений запасов пунктов отправления, группу выходов 65,- 65 „ пронормированных значений потребностей пунктов назначения, группу выходов 66,„ - 66 „ регистрации номера максимального канала.

Блок 6 управления содержит первый коммутатор 67, распределитель 68 импульсов, ключ 69, цифровой вольтметр 70, второй коммутатор 71, группу регистрирующих счетчиков 72„,—

72, элементы 73 и 74 индикации, 1Т выключатели 75 и 76, группу входов

77 „— 77 „, входы 78 - 80, выходы

8l — 83.

Кроме этого, в блоке 1 задания коэффициентов транспортных затрат имеется выключатель 84. Блок 1 задания коэффициентов транспортных затрат предназначен для задания напряжений, определяемых по значениям коэффициентов транспортных затрат

С решаемой задачи. 5

Количество задатчиков 10 . опре11 деляется числами m — - количеством пунктов отправления и и — количеством пунктов назначения, причем индексация r..авпядает с индексацией соот1379787 ветствующих элементов математической поставноки транспортной задачи.

Блок 2 сравнения предназначен для определения эадатчика 10,, соответствующего запрещаемому элементу матрицы транспортных затрат при решении задачи по критерию времени.

Блок 3 выбора максимума предназначен для определения задатчика 10

10;, имеющего максимальное напряжение на потенциометре 13;. и соответствующего минимальному элементу матрицы задатчиков коэффициентов транспортных затрат.

Блок 4 коммутации предназначен для подключения эадатчиков !О; соответствующих запрещенным маршрутам при решении транспортной задачи по критерию времени, к цифрово- 20 му вольтметру блока 6 и для исключения их иэ рассмотрения на последующих шагах.

Блок 5 хранения промежуточного результата предназначен для запомнив- 25 ния результатов решения задачи на каждом шаге.

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

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

Перед началом решения транспортной задачи по критерию времени коммута-!! тор 67 устанавливается в положение

"Решение задачи по критерию времени !, с помощью потенциометров 13 „, 45 ...,13„,,...,13 „„,...,13 „,„после включения выключателей 84 и 75 задаются напряжения U;;,ïðîïîðöèîнальные величинам d;> - С-с,1. где

С вЂ” достаточно большое число такое, что С ai !а! с . с .- - коэффициенты

31 э i)

lj транспортных затрат (либо они поступают от датчиков исходной информации ), а также нажатием релейно-кноночного ключа 69 блока 6 переводят- 55 ся в нулевое состояние регистрирующие счетчики со сдвигающии регистром 72,„,...,72i 72 „,, ...,72,„„, а счетчики 49,...,,49„ и 50,,...,50 переходят в состояни (N-b;) и (N-a,) соответственно, где а; — запасы i-ro пункта отправления; Ь1 — потребности j-ro пункта назначенйя; N - емкость счетчика (il!...,m; j l,...,п).

Решение начинается включением выключателя 76, при этом импульсы от распределителя 68 подаются на входы элементов 46 „,...,46 „,.. .,46 ...,46 „, на другой вход одного иэ которых подан сигнал с соответствующего"входа, на который сигнал подан с соответствующего выхода 36; блока 3. На этот выходной полюс напряжение подается от шины питания через исполнительную цепь электронного ключа 34;, соответствующего звдатчику 10; с наибольшим по абсолютной величине значением выходного сигнала. При этом в начале ре" шения с выходов инверторов 51,,..., 51„ и 52,,...,52,„ сигналы поступают через выходы 62,,...,62 „и

63,,...,63„„ блока 5 и входы 7,,..., 7 и 8,,...,8 „блока 1 на входы элементов И ll,...,11,,...„11 ! t!

1l„„, сигналы с выходов которых через ключи 12 с лротивофазныи управлением поступают на управляющие входы ключей 14„,...,14,...,14,„,,..., 14 » которые соединяют подвижные контакты потенциоиетров !3

11

13,„,...,13,,...,13 „ с выходаии ка 1. В этот момент ключи 12 находятся в исходнои состоянии, так квк сйгналы с выходов перечисленных инверторов поступают на инвертируемые управляющие входы всех ключей, ° ° ° 53 и 54 ° ° ° 54 блока 5

С выхода элемента И 46,, соответствующего иинииальному элементу матрицы задатчиков коэффициентов транспортных затрат //с;! //, импульсы подаются через элементы 47. и

48; на счетный вход счетчиков 49. и

50;, соответствующих столбцу и строке матрицы, на пересечении которых находится этот иинимальный элемент, а также через выходы 66,. блока 5 и !

1 вход 77; блока 6 на счетный вход ! ) регистрирующего счетчика 72;. со сдвигающии регистром, соответствующего этому минимальному элементу.

При заполнении одного из счетчи" ков 49 или 50; блока 5, что со1379787 ответствует удовлетворению потребностей j ãî пункта назначения или использованию всех запасов i-го пункта отправления, сигнал о переполнении поступает на вход соответствующего инвертора 51 или 52 и прек1

1 ращается поступление импульсов через соответствующие выходы 62 и

63, блока 5 и входы 7. или 7; бло- 10 ка l на входы соответствующих эадатчиков коэффициентов транспортных затрат матрицы блока 1, а также на управляющий вход соответствующего ключа 53 или 54 ° При этом потен1 циометры 13;; задатчиков 10;, соответствующие i-й строке или 1-му столбцу матрицы задатчиков коэффициентов транспортных затрат, отключаются от соответствующих выходов 20 блока 1, так как снимается напряжение с управляющих входов ключей

14;., обесточивается ранее сработавший ключ 34 блока 3 и прекращаетil сч подача импульсов на входы соот- 25 ветствующих счетчиков блока 5 и регистрирующего счетчика блока 6. Этот момент соответствует определению величины перевозки Х .. из i-го пункта

1 отправления в j-й пункт назначения 30 при транспортных затратах с;,. Далее определяется следующий минимальный элемент матрицы транспортных затрат и устройство работает аналогично рассмотренному вьппе первому

35 шагу решения.

После каждого шага решения срабатывает один или несколько из ключей 53,,...,53 „ и 54,,. ° .,54,„ блока 5, которые подключают к шинам

40 питания выходы 64,,...,64 „и 65 „, ...,65„ этого блока, напряжение с которых поступает на входы 26„ °,26 „ и 27,. ..,27 блока 2 и подается на входы элементов И 22 „ ...,,22 „. 45

При этом на элемент 22;, индексы которого соответствуют минимальному элементу матрицы задатчиков коэффициентов транспортных затрат, сигнал поступает на оба входа. С выхода этого элемента через выход 25; блока 2, входы 18; блока 1 сигйал поступает на управляющий S-вход ключа 12 1 » а через вход 43;! и элемент

38 - задержки и на управляющий S-вход

1! 55 элемент ИЛИ 23 блока 2, Ключи 12

1! отключают соответствующий задатчик

10,, а ключи 37; подключают цифровой вольтметр 70 блока 6 к потен циометру 13,. блока

1!

Напряжение на входе цифрового вольтметра соответствует транспортным затратам Ci . С выхода элемента

23 блока 2 сигнал запускает генератор 24 одиночных импульсов этого блока, сигнал с которого поступает на R-входы всех ключей 12 „ блока 1, устанавливая эти ключи в исходное состояние и замыкая исполнительные цепи ключа 14;, и íà R-входы всех ключей 37;; блока 4, разрывая их исполнительные цепи. В этот момент сигнал с элемента 38, задержки

11 поступает на S-вход электронного ключа 37,, соответствующего последнему выбранному минимальному элементу матрицы задатчиков коэффициентов транспортных затрат, и оставляет подключенным соответствующий ему выход 16; блока 1 к цифровому вольтмеТру 70 блока 6.

По окончании просмотра всех строк и столбцов блока 1 матричной модели на всех входах (ш - n)-входового элемента И 21 блока 1 присутствует сигнал, элемент 21 открывается и с его выхода через выход 15 блока 1 сигнал поступает на вход 45 блока 4 и на вход 79 блока 6, причем с входа 45 сигнал поступает на один из входов формирователей 39 „,...,39,„,..., 39„,...,,39„„импульсов, а на другой

H3 ВХОДОВ 0QHOI O HS HHX» 39 i!» CO ответствующего подключенному к цифровому вольтметру 70 подвижному контакту потенцибметра 13;

1!» поступает постоянное напряжение.

Формирователь 39;. импульсов срабатывает, и с его выхода на управляющий S-вход ключа 12 поступает импульс, длительность которого несколько превышает длительность цикла решения задачи, Таким образом, до конца решения эадатчик

10;. отключен от входов блока I что соответствует запрету элемента С;; в матрице коэффициентов транспортных затрат.

С входа 79 блока 6 сигнал поступает на входы коммутатора 67, а через них на управляющий вход коммутатора 7!, который своими исполнительными цепями включает элемент 73 индикации 1Решение задачи по критерию времени" и подключает соответ1379787 ствующий выход распределителя 68 импульсов на входы регистрирующих счетчиков со сдвигающим регистром 72,1 и на элемент 38 задержки.

На счетчиках 72 „,...,72,„,..., 72 „ . ..72 высвечивается первый план перевозок, а на цифровом вольтметре 70 — максимальное время их занершения, Спустя время задержки 10 элемента 38 сигнал с его выхода поступает на управляющий вход релейнокнопочного ключа 69, замкнувшиеся контакты которого пропускают импульс от распределителя 68, регистрирующие счетчики 72,...,72,„,...,72„,, ° ...

11

72 „обнуляются, а счетчики 49...,,, 49 „ и 50,,...,50 переходят в исходное состояние, Контакты релейнокнопочного ключа 69 размыкаются, и 20 устройство приступает к определению очередного плана перевозок.

При повторении либо превышении максимального времени перевозок, определяемого по показаниям цифрового вольтметра 70, оператор размыкает выключатель 75, останавливая работу устройства по решению задачи.

При этом на регистрирующих счетчиках 72 „, . .,72,„,...,72 „,..., 72 со сдвигающим регистром фикси1йИ руется окончательный план перевозок, а время их завершения соответствует показанию, снятому с цифрового вольтметра 70 на предыдущем цикле решения.

Устройство допускает решение транспортной задачи линейного программирования, Для этого коммутатор

67 блока 6 устанавливается в положе ние "Решение транспортной задачи 40 линейного программирования". Устройство при этом работает аналогично, причем уже в первом цикле решения при поступлении сигнала переполнения с последнего счетчика 49,,..., 49„ или 50,,...,50 блока 5 появляется сигнал на выходе элемента И 55 или 56 соответственно. Этот сигнал поступает на вход элемента ИЛИ 57, а с выхода последнего на управляющий вход коммутатора 71, исполнительная цепь которого включает элемент 74 индикации "Решение транспортной задачи линейного программирования" и подключает соответствующий выход распределителя 68 на входы регистрирующих счетчиков 72„ ° ° . °,72,„, ° ° °, 72,,...,72 „ co сдвигающим регистром для выдачи плана перевозок.

Поскольку при этом на управляющий вход релейно-кнопочного ключа 69 сигнал не поступает, то загорание элемента 74 индикации свидетельствует об окончании решения, завершившегося определением ппана перевозок по способу минимального элемента.

Наличие двух элементон И 55 и 56 позволяет беэ дополнительных преобразований решать транспортные задачи с неправильным балансом.

Для возврата схемы в исходное состояние выключаются выключатели 84 блока 1, 75 и 76 блока 6 и снимается напряжение с шин питания устройства.

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

Устройство для решения -ранспортных задач, содержащее блок сравнения, блок коммутации, блок выбора максимума, блок управления и блок задания коэффициентов транспортных затрат, выполненный в виде матрицы задатчиков коэффициентов, каждый из которых содержит потенциометр, первые выводы всех потенциометров эадатчиков коэффициентов матрицы объединены и подключены к шине питания, вторые ныводы всех потенциометров эадатчиков коэффициентов матрицы подключены к шине нулевого потенциала, блок управления содержит первый и второй коммутаторы, элементы индикации, элемент задержки, первый g второй информационные выходы первого коммутатора подключены к входам одноименных элементов индикации, выходы которых подключены к шине нулевого потенциала, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введен блок хранения промежуточного результата, в каждый эадатчик коэффициентов матрицы блока задания коэффициентов транспортных затрат введены элемент И, - коммутатор, ключ с противофаэным управлением и разделительный диод, кроме этого, в блок задания коэффициентов транспортных затрат введен (ш и)-входовый элемент И, в блок управления введены ключ, цифровой вольтметр, группа регистрирующих счетчиков, распределитель импульсов и выключатель, н каж1379787 дом задатчике коэффициентов матрицы блока задания коэффициейтон транспортных затрат подвижный контакт потенциометра подключен к первому

5 информационному входу коммутатора, управляющий вход которого подключен к выходу ключа с противофаэным управлением, информационный вход которого подключен к выходу элемента И, lð прямой управляющий вход ключа с противофазным управлением подключен к катоду разделительного диода, вторые информационные входы всех коммутаторов матрицы объединены и подключены к первому входу распределителя импульсов блока управления, первые нходы всех элементов И каждого i-го столбца матрицы эадатчиков коэффициентов (i=1,2,...,n) объединены 2р и подключены к i-му ньиоду группы выходов значений запасов i-го пункта отправления блока хранения промежуточного результата, вторые нходы всех элементов И 25 каждой j-й строки матрицы задатчиков коэффициентов, (где j = 1,2...,m) объединены и подключены к j-му выходу группы выходов значений потребностей j-ro пункта назначения блока хра- Зр нения промежуточного результата, инверсные управляющие входы всех ключей с противофазным управлением матрицы эадатчиков коэффициентов объединены с инверсным управляющим

35 входом блока коммутации и подключены к выходу блока сравнения, анод разделительного диода каждого i-ro задатчика коэффициентов j-й строки матрицы эадатчиков коэффициентов 4р подключен к ij-My входу первой группы информационных входов блока сравнения и к ij-му управляющему входу группы прямых упранляющих входов блока коммутации, прямой управляющий 45 вход ключа с противофазным управлением каждого i-го эадатчика коэффициентов j --й строки матрицы задатчиков коэффициентов подключен к

ij-му выходу группы информационных выходов блока коммутации, первый информационный выход коммутатора каждого j-ro задатчика коэффициентов каждого i-rn столбца матрицы задатчиков коэффициентов подключен к

ij -му входу (m n) — входового элемента И, выход которого подключен к первому информационному входу перного коммутатора блока управления и к входу разрешения формирования выходного сигнала блока коммутации, дополнительный информационный выход блока -коммутации подключен к входу цифрового вольтметра блока управления, второй информационный выход коммутатора каждого j-го задатчика коэффициентов каждого i-ro столбца матрицы эадатчиков коэффициентов подключен к ij ìó входу группы входов блока выбора максимума, группа выходов которого подключена к группе входов блока хранения промежуточного результата, каждый выход группы выходов регистрации номера максимального канала которого подключен к информационному входу одноименного регистрирующего счетчика группы блока управления, входы начальной установки всех регистрирующих счетчиков группы блока упранления объединены между собой, объединены с входом начальной установки блока хранения промежуточного результата, подключены к выходу ключа блока управления, информационный вход которого подключен к второму ныходу распределителя импульсов, управляющий вход ключа блока управления подключен к выходу элемента задержки, вход которого объединен с первым информационным входом первого коммутатора блока управления, второй информационный вход которого подключен к выходу индикации работы блока хранения промежуточного результата, каждый выход группы выходов пронормиронанных значений запасов

i-го пункта отправления и потребностей j-ro пункта назначения которого подключен к одноименному входу второй группы информационных нходов блока сравнения, тактирующий вход блока хранения промежуточного результата через выключатель подключен к третьему выходу распределителя импульсов, выходы разрещения записи регистрирующих счетчиков группы блока управления объединены и подключены к первому информационному выходу второго коммутатора блока управления, первый информационный вход которого подключен к четвертому выходу распределителя импульсов, второй информационный вход второго коммутатора блока управления объединен с входом запуска распределителя импульсов и является входом запуска блока управления, второй информаци1!

l 379787 онный выход второго коммутатора блока управления подключен к третьему информационному входу первого коммутатора блока управления, третий информационцый выход которого подключен к управляющему входу второ го коммутатора блока уп ра и ления.

1379787

1379787

litt ФЗ((Ф3т, ft3, 43

60„

rli

4Оя

4о

42 фий5

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

Редактор В.Петраш Техред Л.Сердюкова Корректор Л.Патай

Закаэ 981/50 Тира к 704 Лодписное

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

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

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

И„

Я<

66,„