Устройство для оптимального решения системы линейных неравенств

(5 Н 4 С 06 Р 15 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(7 1) Куйбышевский институт инженеров железнодорожного транспорта (72) Б.И.Горохов(56) Авторское свидетельство СССР У 635488, кл, С 06 Р 15/20, 1976.Авторское свидетельство СССР У 1315996, кл С 06 Р 15/20, 1985. (54) УСТРОЙСТВО ЛЛЯ ОПТИМАЛЬНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения произвольной конечной системы линейных неравенств. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит регистр 1 векторов, Ь групп по С ключей 2,-2 гдеЬ и С - разрядность и соответственночисло входных векторов, блок 3 вычисления среднего значения векторов,блок 4 вычисления текущего векторагрупп блоков 5, -5 вычисления скалярного произведения, блок 6 определенияминимума, первый блок 7 вычисленияскалярного произведения, первый блок8 деления, блок 9 анализа максимума,выходной регистр 10, блок 11 вычисления модуля вектора, умножитель 12,блок 13 сравнения, элемент И 14,блок15 индикации блок 16 синхронизации,блок 17 вычитания, второй 18 и третий Я19 блоки вычисления скалярного произведения, второй блок 20 деления, блок21 выбора минимума двух величин,1 эеп ф лы 3 илИзобретение относится к автоматикеи вычислительной технике и можетбыть использовано для решения произвольной конечной системы линейныхнеравенств.Цель изобретения - повышение быстродействия устройства.На фиг,1 приведена структурнаясхема устройства; на фиг.2 - струк- Отурная схема блока вычисления текущего вектора; на фиг.З - временные диаграммы работы блока синхронизации.Устройство содержит регистр 1 векторов, Ъ групп ключей 2-2, блок 3 5 вычисления среднего значения векторов, блок 4 вычисления текущего вектора, группу из Ъ блоков 5, -5 вычисления скалярного произведения,.блок бопределения минимума, первый блок 7 20вычисления скалярного произведения,первый блок 8 деления, блок 9 аналйза максимума, выходной регистра 10,блок 1 1 вычисления модуля вектора, умножитель 12, блок 13 сравнения, 25элемент И 14, блок 15 индикации,блок 16 синхронизации, блок 17 вычитания, второй 18 и третий 19 блоки вычисления скалярного произведения, второй блок 20 деления и блок 21 вы- ЗО бора минимума двух величин, выход 22 устройства.Блок 4 вычисления текущего вектора содержит первый сумматор 23, умножитель 24, второй .сумматор 25, регистР 35 2 б и группу из С элементов НЕ 27, информационные входы 28, выходы 29,управляющий вход 30 и вход 31 синхронизации.Нахождение оптимального решения 40 системы линейных неравенств сводится к следующему.Пусть задана система линейных неравенства,; х) О, 61,Ь. 451"- Коэффициенты а представляют собой множество В векторов (точек) в С-мерном пространстве. Для нахождения оптимального решения требуется найти 50 такую гиперплоскость, проходящую через начало координат, расстояние от которой до ближайшей точки множества В максимально при всевозможных расположениях гиперплоскостей. Множество В является множеством входных векторов, а оптимальный вектор решения системы линейных неравенств - оптимальным вектором структуры. Оптимальным вектором структуры называется такой единичный вектор, минимальное значение скалярных произведений которого на все входные векторы (минимальное значение взвешенной суммы) является максимальным среди всех единичных векторов.Вычисления текущего вектора структуры производятся циклически, причем направление движения в Е-м цикле остается неизменным и задается вектоРом У - Як, где 3- выходной вектор блока вычисления текущего вектора, у - выходной вектор блока вычисления среднего значения векторов. Максимальное изменение модуля текущего вектора структуры в цикле будет в том случае, когда новый вектор структуры перпендикулярен направлению ук- Як, так как этот перпендикуляр является наименьшим расстоянием от .отрезка у - 1 до начала координат.Вычисление текущего вектора структуры в Е-м цикле производится по формуле"к+ = "к+Ч к (Ук к )Блок 17 вычитания производит вычисление вектора к -у, блок 18 вычисления скалярного произведения определяет модуль этого вектора, а блок 19 вычисления скалярного произведения определяет скалярное произведение этого вектора на текущий вектор структуры. Делитель 20 и блок 21 выбора минимума двух величин вычисляют ц.Модуль текущего вектора структуры в пределе стремится к значению минимальной взвешенной суммы для опти-:. мального вектора. Поэтому, чем быстрее этот вектор приблизится к оптимальному, тем быстрее приблизится его минимальная взвешенная сумма к значению минимальной взвешенной суммы для оптимального вектора, Таким образом, выбор в каждом цикле в качестве текущего вектора структуры перпендикуляра к направлению движения этого вектора обеспечивает более быстрое уменьшение его модуля по сравнению с известным устройством.Процесс нахождения оптимального решения системы линейных неравенств происходит следующим образом.В регистр 1 векторов предварительно записываются все координаты всех входных векторов, определяющих систему линейных неравенств. В блок 4= Я+ (у-Я),где у - выходной вектор блока 3;с = ш 1 п(1, " ),(як, Як -к )Ч(Я-у )2Запись текущего вектора структурыв блок 4 происходит при поступлениитактирующего импульса с четвертоговыхода блока 16 синхронизации. Таккак текущий вектор структуры изменяется в каждом цикле, то изменяютсязначения скалярных произведений этого 50 55 записывается начальный вектор структуры, в качестве которого можно взять любой из входных векторов, В блок 9 анализа максимума в качестве мини 5 мальной взвешенной суммы записывается максимальное по абсолютной величине отрицательное число.Вычисления производятся циклически. Началом цикла считается импульс на четвертом выходе блока 16 синхронизации. Поэтому первый цикл вычислений отличается от остальных отсутствием первого тактирующего импульса на входе синхронизации блока 4, так 15 как в этом блоке уже записан начальный вектор структуры.В течение одного цикла устройство работает следующим образом.После записи в блок 4 текущий вектор структуры перемножается скалярно со всеми входными векторами в блоках 5 -5вычисления скалярного произведения, минимальное значение из всех скалярных произведений определяется с 5 в блоке 6 определения минимума, у которого появляются единичные сигналы на тех выходах, которым соответствуют минимальные значения взвешенных сумм на входе. 30Возбужденные выходыблока 6 определения минимума открывают соответствующие ключи 2, -2и соответствующие этим ключам входные векторы поступают на входы блока 3 вычисления среднего значения векторов. На выходе последнего образуется вектор, значение каждой координаты равно среднему арифметическому значений координат Всех Входных векторов на входе При 40 поступлении тактирующего импульса на вход синхронизации блока 3 в нем происходит запоминание этого вектора.Блок 4 производит вычисление текущего вектора структуры в к-м цикле 45 по формуле вектора со всеми входными векторамина выходах блоков 5,-5вычисленияскалярного произведения группы, врезультате чего возбуждаются другиевыходы в блоке 6 определения ьпнимума. При этом оказываются открытымидругие из ключей 2,-2 и другие входные векторы подаются из регистра 1векторов на входы блока 3, что приводит к изменению выходного вектора уэтого блока в каждом цикле. Такимобразом, на вход блока 4 всегда подается вектор, скалярное произведениекоторого на текущий вектор структурыминимально для всех входных векторов,так как ч вычисляется в цикле послезаписи в память текущего вектораструктуры.Изменение выходного вектора блока4 Я приводит к увеличению минимальной взвешенной суммы, Однако это изменение происходит не обязательно монотонно, так как среди входных векторов находятся такие, для которыхскалярное произведение ( Я, х; ) приэтом уменьшается и может стать меньшезначения Е . Вместе с тем происходитмонотонное уменьшение модуля текущего вектора структуры - Я 1 , так как1 Я всегда больше минимальной взвешенной суммы - Е, т .е. Як 1 3 Я (В) ъ) Е. Поэтому, значение минимальнойвзвешенной суммы в целом увеличивается в ходе вычислений, стремясь в пределе к значению Я 1,После записи в память выходноговектора блока 3 блок 7 вычисленияскалярного произведения и блок 8 деления вычисляют значение минимальнойвзвешенной суммы, которое анализируется блоком 9 анализа максимума. Еслиэто значение не превьппает значенияминимальной взвешенной суммы, запомненное в блоке, то на выходе блока 9анализа максимума имеется нулевойсигнал, который повторяется на выходеэлемента И 14, поэтому запись в выходной регистр 1 О в данном цикле запрещена.Модуль выходного вектора блока 4вычисляется в блоке 11 вычисления модуля вектора и в блоке 13 сравненияпроизводится сравнения этого модуля,умноженного в умножителе 2 на коэффициент 1-6, поступающий на первыйвход задания настроечного параметраустройства со значением минимальнойвзвешенной суммы на выходе блока 8(1-6)71Если это условие выполняется, т.е. сигнал с выхода умножителя 12 не превышает значенияминимальной взвешенной суммы, то вы,ходной сигнал блока 13 сравненияравен нулю. В противном случае онравен единице. При поступлении нуле 1вого сигнала на вход блока 15 индикации последний сигнализирует о том,что заданная точность вычислений до 1 стигнута,Блок 17 вычитания вычисляет разность векторов, поступающих с выходов 1блока 4 и блока 3, Квадрат модулявыходного вектора блока 17 вычитанияопределяется в блоке 18 вычисленияскалярного произведения, а скалярноепроизведение этого вектора на выходной вектор больше 4 определяется вблоке 19 вычисления скалярного произведения. Блок 20 деления и блок 21ыбора минимума двух величин вычисляют коэффициент, определяющий величину 25шага текущего вектора структуры вцикле.На первом входе элемента И 14 единичный сигнал появляется, когда значение минимальной взвешенной суммы 30на выходе блока 8 деления превышаетвсе предыдущие его значения, на втором входе элемента И 14 единичныйсигнал поддерживается до момента достижения заданной точности вычислений,сигнал на третьем входе элемента И14 является разрешающим для записивыходного вектора блока 4 в выходной,регистр, Таким образом, запись этоговектора производится при возрастании 40минимальной взвешенной сумм на выходеблока 8 деления, пока заданная точ"ность вычислений еще не достигнута.При достижении заданной точности вычислений в выходном регистре записан 45вектор, для которого минимальнаявзвешенная сумма максимальна за всевремя работы устройства, т.е. векторотличающийся от оптимального с заданной погрешностью,Формула изобретения1. Устройство для оптимального решения системы линейных неравенств,Я содержащее регистр векторов, Ь групп по С ключей в кажцой, где С и Ь - разрядность и число входных векторов соответственно, блок определения минимума, группу из Ъ блоков вычисленияскалярного произведения, блок вычисления среднего значения векторов,блок вычисления текущего вектора, выходной регистр, первый блок вычисления скалярного произведения, первыйблок деления, блок анализа максимума,блок вычисления модуля вектора, умножитель, блок сравнения, элемент И,блок синхронизации, причем входы векторов устройства подключены к информационным входам регистра векторов,1 -я группа выходов регистра векторов,где 1 =1,26, подключена к информационным входам 1 -й группы ключейи к первой группе информационных входов 1 -го блока вычисления скалярногопроизведения группы, выход которогоподключен к 1-му информационному входу блока определения минимума, 1 -йвыход которого подключен к управляющему входу ключей 1-й группы, выходыкоторых .подключены к 1-й группе информационных входов блока вычислениясреднего значения векторов, выходыкоторого подключены к первой группеинформационных входов первого блокавычисления скалярного произведенияи к информационным входам блока вычисления среднего значения векторов,выходы, которого подключены к второйгруппе информационных входов первогоблока вычисления скалярного произведения, к вторым группам информационных входов блоков вычисления скалярных произведений группы, к информационным входам выходного регистра ик информационным входам блока вычисления модуля вектора, выход которогоподключен к первым информационнымвходам первого блока деления и умножителя, второй информационный входпервого блока деления подключен квыходу первого блока вычисления скалярного произведения, выход первого .блока деления подключен к информационному входу блока анализа максимумаи к первому входу блока сравнения,выход блока анализа максимума подключен к первому входу элемента И, выходкоторого подключен к входу синхронизации выходного регистра, выход блокасравнения подключен к второму входуэлемента И и является выходом признака окончания вычислений усгройства,второй информационный вход умножителяподключен к первому входу заданиянастроечного параметра устройства, 1411774выход умножителя подключен к второму входу блока сравнения, с первого по четвертый выходы блока синхронизации подключены соответственно к входу синхронизации блока вычисления среднего значения векторов, к третьему входу элемента И, к входу синхронизации блока анализа максимума и к входу синхронизации блока вычисления теку щего вектора, выходы выходного регистра подключены к выходам результата устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстро Действия, устройство содержит блок вычитания, второй и третий блоки вычисления скалярного произведения, второй блок деления и блок выбора минимума двух величин, причем выходы блока вычисления среднего значения 20 векторов подключены соответственно к первой группе информационных входов блока вычитания, выходы которого подключены к первой и второй группам информационных входов второго блока 25 вычисления скалярного произведения и к первой группе информационных входов третьего блока вычисления скалярного произведения, выходы блока вычисления текущего векторы подключены 30 к второй группе информационных входов .блока вычитания и к второй группе информационных входов третьего блока вычисления скалярного произведения, выходы второо и реянье бо вы числения скалярного произведения подключены соответственно к первому и второму информационным входам второго блока деления, выход которого подключен к первому информационному входу блока выбора минимума двух величин, второй вход которого подключен к второму входу задания настроечного параметра устройства, выход блока выбора минимума двух величин подключен к управляющему входу блока вычисления текущего вектора.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок вычисления текущего вектора содержит два сумматора, умножитель, регистр и группу из С элементов НЕ, причем информационные входы блока вычисления текущего вектора подключены к первой группе информационных входов первого сумматора, выход которого подключен к первому информационному входу умно- жителя, второй информационный вход которого подключен к управляющему входу блока вычисления текущего вектора, выходы умножителя подключены к первой группе информационных входов второго сумматора, выход которого подключен к информационному входу регистра, вход синхронизации которого подключен к входу синхронизации блока вычисления текущего вектора,: выходы регистра подключены к входам элемен,тов НЕ группы, к второй группе информационных входов второго сумматора и к выходам блока вычисления текущего вектора, выходы элементов НЕ группы подключены соответственно к второй группе информационных входов первого сумматора.в Обручар Заказ 3656/46 а венно-полиграфическое предприятие, г. Ужгород Произ Проектн Составитель В.Смирдактор Н.Бобкова Техред А.Кравчук Тираж 704 ВНИИПИ Государственного ко по делам изобретений и о 113035, Москва, Ж, Раушска