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

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

Цель изобретения - упрощение устройства .

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

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

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

Блок 2 сравнения (фиг,3) содержит элементы И 22 „- 22, элемент ИЛИ 23, генератор 24 единичных импульсов группу входов 25,1- 25, группы входов 26,1 26р и 27,- 27 и выход 28,

Блок 3 выбора максимума (фиг.4) содержит входные резисторы 29 „ - 29п,п, операционные усилители 30 ,, - 30, резисторы 31 „- 3 „ обратной связи, диоды 32,,- обратной связи, развязывающие диоды 33,, - , ключи 34,,- 34,р, группу входо 35,, - 35 „ ,группу выходов 36,,- 36„г

Блок 4 коммутации (фиг.5) содержит ключи 37 ,, - противофазным управлением, элементы 38,,- 38,,,„задержки , формирователи 39 ,,- „ импульсов, группу информационных входов 40„ - 40„р, группу информационных выходов 41,, - 41, дополнительный информационный выход 42, группу прямых управляющих входов 43,,- 43 , ий m п

версный управляющий вход 44, вход 45 разрешения формирования выходного сигнала.

Блок 5 хранения промежуточного результата (фиг,6) содержит группу элементов И 46„- , первую группу элементов ИЛИ 47,- 47„,вторую группу элементов ИЛИ 48,- 48,, первую группу счетчиков 49,- 49, вторую группу счетчиков 50,- 50„, первую группу инверторов 51,- 51„, вторую группу инверторов 52,- 52, первую группу ключей 53,- 53, с инвертирующим управляющим входом, вторую группу ключей 54-,- 54 с инвертирующим управляющим входом, элементы И 55 и 56, элемент ИЛИ 57, вход 58 начальной установки, тактирующий вход 59, группу информационных входов 60,,- , выход 61 индикации работы, группу выходов 62,- 62 значений запасов пунктов отправления, группу выходов 63,- 63 значений потребностей пунктов назначения, группу выходов 64,- 64 пронормированных значений запасов пунктов отправления, группу выходов 65,- 65 пронормированных значений потребностей пунктов назначения, группу выходов 66, - 66 „ регистрации номера максимального канала.

Блок 6 управления содержит первый коммутатор 67, распределитель 68 импульсов, ключ 69, цифровой вольтметр 70, второй коммутатор 71, группу регистрирующих счетчиков - 72, элементы 73 и 74 индикации, выключатели 75 и 76, группу входов 77,, - 77п,„, входы 78 - 80, выходы 81 - 83,

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

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

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

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

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

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

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

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

Перед началом решения транспортно задачи по критерию времени коммутатор 67 устанавливается в положение Решение задачи по критерию времени, с помощью потенциометров 13,,, .. .,13, ,.. .,13,,... ,13 после включения выключателей 84 и 75 задаются напряжения U ij ,пропорциональные величинам d С-с ц . где С - достаточно большое число такое, что С г wa«c.. ; с .- - коэффициенты

м .

транспортных затрат (либо они поступают от датчиков исходной информации ), а также нажатием релейно-кно- почного ключа 69 блока 6 переводят- ся в нулевое состояние регистрирующие счетчики со сдвигающим регистром 72 „ ,... ,72,„,... ,72 , ,

..«,72„„, а счетчики 49,49

и 50 ,...,50 переходят всостояние

(N-b ) и (N-a.) соответственно,

где а i - запасы i-ro пункта отправления; bj - потребности j-ro пункта назначения; N - емкость счетчика

(,... ,т; j « 1п).

Решение начинается включением выключателя 76, при этом импульсы о распределителя 68 подаются на входы элементов 46 , ,... ,46 ,„,... ,46

...,46, на другой вход одного из которых подан сигнал с соответствующего входа, на который сигнал подан с соответствующего выхода 36 - блока 3. На этот выходной полюс напряжение подается от шины питания через исполнительную цепь электронного ключа 34, J, соответствующего задатчику lOjj с наибольшим по абсолютной величине значением выходного сигнала. При этом в начале решения с выходов инверторов 5Ц,.,., 51 „ и 52,,..,,52 сигналы поступают через выходы 62,,...,62 и 63,,...,63 блока 5 и входы 7,,..., 7 и 8,,,..,8|, блока 1 на входы элементов И 1 1,,,,.., П,„,..., И ,,.. , сигналы с выходов которых через ключи I2 с противофазным управлением поступают на управляющие входы ключей 14„,...,14,...,14,,..., , которые соединяют подвижные контакты потенциометров 13 ,...,

13

-in

,,...,13

hin

С выходами

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

С выхода элемента И 46;, соответствующего минимальному элементу матрицы задатчиков коэффициентов транспортных затрат , импульсы подаются через элементы 47 j н 48 на счетный вход счетчиков 49 н 50;, соответствуюяр1Х столбцу и строке матрицы, на пересечении которых находится этот минимальный элемент, а также через выходы 66 блока 5 и вход 77f блока 6 на счетный вход регистрирующего счетчика 72 ц со сдвигаюва м регистром, соответствующего этому минимальному элементу.

При заполнении одного из счетчиков 49: или 50 блока 5, что соответствует удовлетворению потребностей j-ro пункта назначения или использонанию всех запасов i-ro пункта отправления, сигнал о переполнении поступает на вход соответствующего инвертора 51: или 52, и прекращается поступление импульсов через соответствующие выходы 62

63, блока 5 и входы 7.- или 1 блока I на входы соответствующих задат- чиков коэффициентов транспортных затрат матрицы блока I, а также на управляющий вход соответствующего ключа 53- или 5. При этом потенциометры 13,; задатчиков lOj:, соответствующие i-й строке или j-му столбцу матрицы задатчиков коэффициентов транспортных затрат, отключаются от соответствую1цих выходов блока 1, так как снимается напряжение с управляющих входов ключей 14 ;., обесточивается ранее сработавший ключ ЗА ,., блока 3 и прекращает- сч подача импульсов на входы соответствующих счетчиков блока 5 и регистрирующего счетчика блока 6, Этот момент соответствует определению величины перевозки X . j из i-ro пункта отправления в j-й пункт назначения при транспортных затратах с ,-j. Далее определяется следующий минимальный элемент матрицы транспортных затрат и устройство работает аналогично рассмотренному выше первому шагу решения.

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

и 27,,...,27 блока 2 и подается на входы элементов И 22 ,...,22 . При этом на элемент 22 ,- , индексы которого соответствуют минимальному элементу матрицы задатчиков коэффициентов транспортных затрат, сигнал поступает на оба входа. С выхода

этого элемента через выход 25

М

блока 2, входы 18; блока 1 сигнал поступает на управляющий S-вход ключа 12 j- , а через вход 43 ,; и элемент задержки и на управляющий S-вход элемент ИЛИ 23 блока 2. Ключи 2 . отключают соответствующий задатчик

10

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

Напряжение на входе цифрового вольтметра соответствует транспортным затратам С): , С выхода элемента 23 блока 2 сигнал запускает генератор 24 одиночных импульсов этого блока, сигнал с которого поступает на R-входы всех ключей блока 1, устанавливая эти ключи в исходное состояние и замыкая исполнительные

цепи ключа 14,-., и на R-входы всех ключей 37 ,-j блока 4, разрывая их исполнительные цепи. В этот момент сигнал с элемеита 38 ; задержки поступает на S-вход электронного

ключа 37j; , нему выбранному

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

выход 16;; бЛОКа 1 К ЦИФРОВОМУ ВОЛЬТMetpy 70 блока 6.

По окончании просмотра всех строк и столбцов блока 1 матричной модели на всех входах (т п)-входового элемента И 21 блока 1 присутствует сигнал, элемент 21 открьшается и с его

выхода через выход 15 блока 1 сигнал поступает на вход 45 блока 4 и на вход 79 блока 6, причем с входа 45 сигнал поступает на один из входов формирователей 39 ,, ,. . . ,39 , ,. .., 39,, ,... ,39 импульсов, а на другой из входов одного из них, 39 ,., соответствующего подключенному к цифровому вольтметру 70 подвижному контакту потенциометра 3,-. , .

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

10

отключен от входов блока I, что

соответствует запрету элемента С

Ч

в матрице коэффициентов транспортных затрат.

С входа 79 блока 6 сигнал поступает на входы коммутатора 67, а через них на управляющий вход коммутатора 71, который своими исполнительными цепями включает элемент 73 индикации Решение задачи по критерию времени и подключает соответЧ

ствующий выход распределителя 68 импульсов на входы регистрирующих счетчиков со сдвигающим регистром 72 и на элемент 38 задержки.

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

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

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

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

тс е , ,,

к, т.

, 10

15

20

25

30

35

40

45

50

55

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

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

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

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

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

тей j-ro пункта назначения блока хра- о ления подключен к выходу элемента

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

5

0

5

0

5

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

ОННЫЙ выход второго коммутатора блока управления подключен к третьему информационному входу первого- коммутатора блока управления, тре1379787

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

fl..«, 3

Г

а

п

гллО

-J

1

I hI

.J

2е„ 27г27„ Фиг.З

9 Йп

(7

.

20м.д

5С.

f

/вм

/fw

J5« ... f ... I5it - JJ

2i% 2i-

J(« .- Ум - lf«r

fui.

4 V H/...... /....

АО,

ss

5/ f2, 62n S3, S3, Put.S