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

ОВЕТСНИХИСТИЧЕСНИХ УБЛИН) )бИСАНИЕ ИЭОБРЕТЕНИ АНС ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРУ 219924, кл. С 06 С 7/76, 1968.Авторское свидетельство СССРпо заявке В 3853670/24,кл. С 06 С 7/122, 1985,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРПОРТНЫХ ЗАДАЧ(57) Изобретение относится к вычислительной технике и может быть использовано при решении транспортных задач по критерию времени. Целью изобретения является упрощение устройства. Функциональная схема устройства разработана таким образом, чтоустройство может быть выполнено какна стандартных элементах вычислительной техники, так и на специальныхмодулях, практически совпадающих с блоками. Использование таких модулейдает возможность решать транспортныезадачи любой размерности беэ изменения структуры устройства и за короткий промежуток времени. Устройствосодержит блок эадатчиков коэффициентов транспортных затрат,коммутатор,блок сравнения, блок выбора максимума, блок хранения промежуточногорезультата и блок управления. Подготовка устройства к работе достаточнопроста и не требует высокой квалификации оператора, а результаты реше"ния выдаются на индикаторных счетчиках в удобном цифровом виде. Крометого, при замене потенциометров-аналогов датчиками исходной информациии при подключении через цифроаналоговые преобразователи к исполнительным механизмам устройство может использоваться в автоматизированныхили автоматических системах управляющих процессами или объектами.6 ил, 379787 гИзобретение относится к вычислительной технике и может быть ис 40 пользовала для решения транспортныхзадач па критерию времени, к которым сводится широкий класс зкономических и инженерных задач.Цель изобреТения - упрощение устройства.На Фиг.1 изображена функциональная схема устройства для решениятранспортных задач; на фиг, 2структурная схема блока заданиякоэффициента транспортных затрат;на фиг.З - 6 - структурные схемы 5блоков сравнения, выбора максимума,коммутации и хранения промежутачнага результата соответственно,устройство для решения транспортных задач содержит блок 1 задания 20коэффициентов транспортных затрат,выполненный в виде матрицы задатчиков коэффициентов транспортных затрат, блок 2 сравнения, блок 3 выборамаксимума, блок 4 коммутации, блок 5 25хранения промежуточного результатаи блок 6 управления.Блок 1 задания коэффициентовтранспортных затрат (Фиг.2) содержитгруппу входов 7, - 7 , группу входов ЗО8, - 8, вход 9, задатчики 1 О коэффициентов транспортных затрат, элементы И 11, ключи 12 с пративафазнымуправлением (где Б - прямой, а К -инверсный управляющие входы ), потенциометры 13, коммутаторы 14, выход 15окончания просмотра всех строк истолбцов, выходы 16- 16, вход 17,входы 18, - 18 , входы 19- 19разделительные диоды 20, - 20(ши)-входовый элемент И 21Блок 2 сравнения (фиг. 3) содержитэлементы И 22- 22 , элемент ИЛИ23, генератор 24 единичных импульсов,группу входов 25 - 25 группы 45входов 26 - 26 и 27, - 27 и выход 28,Блок 3 выбора максимума (фиг,4)содержит входные резисторы 29,. -29, операционные усилители 30-30, резисторы 3- 31обратнойсвязи, диоды 32- 32обратнойсвязи, развязывающие диоды 33-33 , ключи 34- 34 , группу входов3 5 1135 группувь адов 3-36 п,55Блок 4 коммутации (фиг,5) содержит ключи 37, - 37 с противафазнымуправлением, элементы 38- 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 индикации,Иь фвыключатели 75 и 76, группу входов77 - 77 , входы 78 - 80, выходы8 - 83.Кроме этого, в блоке 1 заданиякоэффициентов транспортных затратимеется выключатель 84. Блок 1 задания коэффициентов транспортныхзатрат предназначен для задания напряжений, определяемых по значениямкоэффициентов транспортных затратС решаемой задачи,Количество задатчиков 10 опре 1деляется числами ш - количествомпунктов отправления и п - количеством пунктов назначения, причем индексация совпадает с индексацией соот 1379787ветствующих элементов математической поставноки транспортной задачи.Блок 2 сравнения предназначен для определения эадатчика 1 О, , соответствующего запрещаемому элементу матрицы транспортных затрат при решении задачи по критерию времени.Блок 3 выбора максимума предназначен для определения задатчика 10 10; , имеющего максимальное напряжение на потенциометре 13; и соответствующего минимальному элементу матрицы задатчиков коэффициентов транспортных затрат.Блок 4 коммутации предназначен для подключения эадатчиков О; соответствующих запрещенным маршрутам при решении транспортной задачи по критерию времени, к цифрово му вольтметру блока 6 и для исключе" ния их иэ рассмотрения на последующих шагах.Блок 5 хранения промежуточного результата предназначен для запомина ния результатов решения задачи на каждом шаге.Блок 6 управления предназначен для управления работой устройства в ходе решения задачи, индикации 30 результатов и окончания процесса решения.Принцип работы устройства основан на определении плана перевозок и времени их завершения методом реализации максимально возможных назначений по минимальным элементам матрицы транспортных затрат с последующим запрещением перевозки с макси" мальным временем. 40Перед началом решения транспортной задачи по критерию времени коммута"тор 67 устанавливается в положение "Решение задачи по критерию времени, с помощью потенциометров 13 , 45 ,313 ,.,13 , после включения выключателей 84 и 75 задаются напряжения У,пропорциональные величинам д;1 С-с,1. где С - достаточно большое число такое, что С 1 а с . с .- " коэффициенты111транспортных затрат (либо они поступают от датчиков исходной информации ), а также нажатием релейно-кноночного ключа 69 блока 6 переводят ся в нулевое состояние регистрирующие счетчики со сдвигающим регистром 72 721,, 7 2 ,72а счетчики 49,49 и 50,50переходят в состояни(1. 1 ш; 1 1п).Решение начинается включением выключателя 76, при этом импульсы от распределителя 68 подаются на входы элементов 46 46 , .,46 ,46 , на другой вход одного иэ которых подан сигнал с соответствующего"входа, на который сигнал подан с соответствующего выхода 36; блока 3. На этот выходной полюс напряжение подается от шины питания через исполнительную цепь электронного ключа 34;, соответствующего задатчику 1 О; с наибольшим по абсолютной величине значением выходного сигнала. При этом в начале ре" шения с выходов инверторов 51, 51 и 52,52, сигналы поступают через выходы 62,62и 6363 блока 5 и входы 7,8 блока 1 на входылементов Н 1111, ф1111 сигналы с выходов которых через ключи 12 с яротивофазным управлением поступают на управляющие входы ключей 14.141414 которые соединяют подвижные контакты потенциометров 3 1313 ,13с выходами ка 1. В этот момент ключи 12 находятся в исходном состоянми, так как сигналы с выходов перечисленных инверторов поступают на инвертируе" мые управляющие входы всех ключей 53,53и 5454 блока 5.С выхода элемента И 46, , соответствующего минимальному элементу матрицы задатчиков коэффициентов транспортных затрат. //с;1//, импульсы подаются через элементы 47 и 48, на счетный вход счетчиков 49 и 50;, соответствующих столбцу и строке матрицы, на пересечении которых находится этот минимальный элемент, а также через выходы 66,. блока 5 и вход 77; блока 6 на счетный входрегистрирующего счетчика 72;. со сдвигающим регистром, соответствующего этому минимальному элементу.При заполнении одного из счетчи" ков 49 или 50; блока 5, что со 379787ответствует удовлетворению потребностей 1-го пункта назначения илииспользованию всех запасов 1-го пункта отправления, сигнал о переполнении поступает на вход соответствующего инвертора 51 или 52 и прек 11ращается поступление импульсов через соответствующие выходы 62 и63, блока 5 и входы 7, или 7; блока 1 на входы соответствующих эадатчиков коэффициентов транспортныхзатрат матрицы блока 1, а также науправляющий вход соответствующегоключа 53 или 54При этом потен 1циометры 13 задатчиков 10 соответствующие 1-й строке или 1-мустолбцу матрицы задатчиков коэффициентов транспортных затрат, отключаются от соответствующих выходов 20блока 1, так как снимается напряжение с управляющих входов ключей14;., обесточивается ранее сработавший ключ 34блока 3 и прекращаетсч подача импульсов на входы соответствующих счетчиков блока 5 и регистрирующего счетчика блока 6. Этотмомент соответствует определению величины перевозки Х . из 1-го пунктаотправления в 3-й пункт назначенияпри транспортных затратах с;,. Далее определяется следующий минимальный элемент матрицы транспортныхзатрат и устройство работает аналогично рассмотренному вьппе первому35шагу решения,После каждого шага решения срабатывает один или несколько из ключей 5353и 54..,54 , блока 5, которые подключают к шинам40питания выходы 64,64 и 65,,65 этого блока, напряжение с которых поступает на входы 26,26и 27 .27 блока 2 и подаетсяна входы элементов И 2222 . 45При этом на элемент 22 индексыкоторого соответствуют минимальномуэлементу матрицы задатчиков коэффициентов транспортных затрат, сигналпоступает на оба входа. С выходаэтого элемента через выход 25;блока 2, входы 18, блока 1 сигйалпоступает на управляющий Я-вход ключа 12;, а через вход 43; и элемент38 . задержки и на управляющий Б-вход55элемент ИЛИ 23 блока 2, Ключи 12отключают соответствующий задатчик10 а ключи 37; подключают цифровой вольтметр 70 блока 6 к потен циометру 13,. блока11Напряжение на входе цифрового вольтметра соответствует транспортным затратам С . С выхода элемента 23 блока 2 сигнал запускает генератор 24 одиночных импульсов этого блока, сигнал с которого поступает на К-входы всех ключей 12блока 1, устанавливая эти ключи в исходное состояние и замыкая исполнительные цепи ключа 14;, и на К-входы всех ключей 37 блока 4, разрывая их исполнительные цепи. В этот момент сигнал с элемента 38, задержки1поступает на Б-вход электронного ключа 37, , соответствующего последнему выбранному минимальному элементу матрицы задатчиков коэффициентов транспортных затрат, и оставляет подключенным соответствующий ему выход 16; блока 1 к цифровому вольтмеТру 70 блока 6.По окончании просмотра всех строк и столбцов блока 1 матричной модели на всех входах (ш .и)-входового элемента И 21 блока 1 присутствует сигнал, элемент 21 открывается и с его выхода через выход 15 блока 1 сигнал поступает на вход 45 блока 4 и на вход 79 блока 6, причем с входа 45 сигнал поступает на один из входов формирователей 39 39 39,39 импульсов, а на другойов одного из нихответствующего подключенному к цифровому вольтметру 70 подвижному контакту потенцибметра 13,1 поступает постоянное напряжение. Формирователь 39; импульсов срабатывает, и с его выхода на управляющий Я-вход ключа 121 поступает импульс, длительность которого несколько превышает длительность цикла решения задачи, Таким образом, до конца решения эадатчик 10; отключен от входов блока 1, что соответствует запрету элемента Св матрице коэффициентов транспортных затрат.С входа 79 блока 6 сигнал поступает на входы коммутатора 67, а через них на управляющий вход коммутатора 7, который своими исполнительными цепями включает элемент 73 индикацииРешение задачи по критерию времени" и подключает соответствующий выход распределителя 68 импульсов на входы регистрирующих счетчиков со сдвигающим регистром 72,1и на элемент 38 задержки.На счетчиках 72 7272. 72 высвечивается первыйплан перевозок, а на цифровом вольтметре 70 - максимальное время ихзанершения, Спустя время задержки 10элемента 38 сигнал с его выхода поступает на управляющий вход релейнокнопочного ключа 69, замкнувшиесяконтакты которого пропускают импульсот распределителя 68, регистрирующиесчетчики 72 72 ,72,1172обнуляются, а счетчики 4949и 50,50переходят в исходное состояние, Контакты релейнокнопочного ключа 69 размыкаются, и 20устройство приступает к определениюочередного плана перевозок.При повторении либо превышениимаксимального времени перевозок,определяемого по показаниям цифрового вольтметра 70, оператор размыка"ет выключатель 75, останавливая работу устройства по решению задачи.При этом на регистрирующих счетчиах 721, 72 ,172со сдвигающим регистром фиксируется окончательный план перевозок,а время их завершения соответствуетпоказанию, снятому с цифрового вольтметра 70 на предыдущем цикле решения.35Устройство допускает решениетранспортной задачи линейного программирования, Для этого коммутатор67 блока 6 устанавливается в положение Решение транспортной задачи 40линейного программирования". Устройство при этом работает аналогично,причем уже в первом цикле решенияпри поступлении сигнала переполнения с последнего счетчика 49,49 или 50,50 блока 5 появляется сигнал на выходе элемента И 55или 56 соответственно. Этот сигналпоступает на вход элемента ИЛИ 57, ас выхода последнего на управляющийвход коммутатора 71, исполнительнаяцепь которого включает элемент 74индикации "Решение транспортной задачи линейного программирования"и подключает соответствующий выходраспределителя 68 на входы регистрирующих счетчиков 7272, ,72 , .72со сдвигающим регистром для выдачи плана перевозок. Поскольку при этом на управляющий вход релейно-кнопочного ключа 69 сигнал не поступает, то загорание элемента 74 индикации свидетельствует об окончании решения, завершившегося определением ппана перевозок по способу минимального элемента. Наличие двух элементон И 55 и 56 позволяет беэ дополнительных преобразований решать транспортные задачи с неправильным балансом.Для возврата схемы в исходное состояние выключаются выключатели 84 блока 1, 75 и 76 блока 6 и снимается напряжение с шин питания устройства.Формула изобретенияУстройство для решения -ранспортных задач, содержащее блок сравнения, блок коммутации, блок выбора максимума, блок управления и блок задания коэффициентов транспортных затрат, выполненный в виде матрицы задатчиков коэффициентов, каждый из которых содержит потенциометр, первые выводы всех потенциометров эадатчиков коэффициентов матрицы объединены и подключены к шине питания, вторые ныводы всех потенциометров эадатчиков коэффициентов матрицы подключены к шине нулевого потенциала, блок управления содержит первый и второй коммутаторы, элементы индикации, элемент задержки, первый м второй информационные выходы первого коммутатора подключены к входам одноименных элементов индикации, выходы которых подключены к шине нулевого потенциала, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введен блок хранения промежуточного результата,в каждый эадатчик коэффициентов матрицы блока задания коэффициентов транспортных затрат введены элемент И, - коммутатор, ключ с противофаэным управлением и разделительный диод, кроме этого, в блок задания коэффициентов транспортных затрат введен (ши)-входовый элемент И, в блок управления введены ключ, цифровой вольтметр, группа регистрирующих счетчиков, распределитель импульсов и выключатель, н каж 1379787дом задатчике коэффициентов матрицы блока задания коэффициейтов транспортных затрат подвижный контактпотенциометра подключен к первому5информационному входу коммутатора,управляющий вход которого подключенк выходу ключа с противофаэным управлением, информационный вход которого подключен к выходу элемента И, 1 Опрямой управляющий вход ключа с противофазным управлением подключен ккатоду разделительного диода, вторыеинформационные входы всех коммутаторов матрицы объединены и подключенык первому входу распределителя им.пульсов блока управления, первыевходы всех элементов И каждого -гостолбца матрицы задатчиков коэффициентов (д=1,2п) объединены 20и подключены к 1.-му вьводу группы выходов значений запасов д-гопункта отправления блока хранения промежуточного результата,вторые входы всех элементов И 25каждой -й строки матрицы задатчиковкоэффициентов, (где= 1,2,щ)объединены и подключены к -му выходу группы выходов значений потребностей -го пункта назначения блока хра- ЗОнения промежуточного результата,инверсные управляющие входы всехключей с противофазным управлениемматрицы эадатчиков коэффициентовобъединены с инверсным управляющим35входом блока коммутации и подключены к выходу блока сравнения, анодразделительного диода каждого д-гозадатчика коэффициентов 1-й строкиматрицы эадатчиков коэффициентов 40подключен к Ц-му входу первой группы информационных входов блока сравнения и к 1-му управляющему входугруппы прямых управляющих входовблока коммутации, прямой управляющийвход ключа с противофазным управлением каждого -го эадатчика коэффициентов 1-й строки матрицы задатчиков коэффициентов подключен кд)-му выходу группы информационныхвыходов блока коммутации, первый информационный выход коммутатора каждого )-го задатчика коэффициентовкаждого д-го столбца матрицы задатчиков коэффициентов подключен к55д-му входу (ш ч и)-входового элемента И, выход которого подключен к первому информационному входу первогокоммутатора блока управления и к входу разрешения формирования выходного сигнала блока коммутации, дополнительный информационный выход блока коммутации подключен к входу цифрового вольтметра блока управления,второй информационный выход коммутатора каждого -го задатчика коэффициентов каждого -го столбца матрицызадатчиков коэффициентов подключенк 1.1-му входу группы входов блокавыбора максимума, группа выходов которого подключена к группе входовблока хранения промежуточного результата, каждый выход группы выходоврегистрации номера максимального канала которого подключен к информационному входу одноименного регистрирующего счетчика группы блока управления, входы начальной установкивсех регистрирующих счетчиков группыблока управления объединены междусобой, объединены с входом начальнойустановки блока хранения промежуточного результата, подключены к выходуключа блока управления, информационный вход которого подключен к второму выходу распределителя импульсов,управляющий вход ключа блока управления подключен к выходу элементазадержки, вход которого объединен спервым информационным входом первогокоммутатора блока управления, второй информационный вход которогоподключен к выходу индикации работыблока хранения промежуточного резуль"тата, каждый выход группы выходовпронормированных значений запасов-го пункта отправления и потребностей 1-го пункта назначения которогоподключен к одноименному входу второй группы информационных входовблока сравнения, тактирующий входблока хранения промежуточного результата через выключатель подключен ктретьему выходу распределителя импульсов, выходы разрещения записирегистрирующих счетчиков группы блокауправления объединены и подключенык первому информационному выходувторого коммутатора блока управления, первый информационный вход которого подключен к четвертому выходу распределителя импульсов, второй информационный вход второго коммутатора блока управления объединенс входом запуска распределителя импульсов и является входом запускаблока управления, второй информационный выход второго коммутатора блока управления подключен к третьему информационному входу первогокоммутатора блока управления, третий информационный выход которого подключен к управляющему входу второго коммутатора блока упранлепия..Пата орре одписное ФФ 43 йт И,ФЗ,Составитель Т. Сапуновактор В.Петраш Техред Л.Сердюкова аэ 981/50 Тиразк 704 ВНИИПИ Государственного комитета С по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., Пронэводственно-полиграфическое пред ие, г.уигород, ул.Проектная