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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения произвольной конечной системы линейных неравенств. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит регистр 1 векторов , b групп по С ключей 2,-2, где b и С - разрядность и соответственно число входных векторов, блок 3 вычисления среднего значения векторов, блок 4 вычисления текущего вектора групп блоков 5, -5 вычисления скалярного произведения, блок 6 определения минимума, первый блок 7 вычисления скалярного произведения, первьй блок 8 деления, блок 9 анализа максимума, выходной регистр 10, блок 11 вычисления модуля вектора, умножитель 12, блок 13 сравнения, элемент И 14,блок 15 индикации, блок 16 синхронизации, блок 17 вычитания, второй 18 и третий 19 блоки вычисления скалярного произведения , второй блок 20 деления, блок 21 выбора минимума двух величин, 1 з.п. ф-лы, 3 ил. S

А"!

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

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

РЕСПУБЛИН (!9! (!!! (5!1 4 С 06 F 15/31

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4170868/24-24 (22) 30.12.86 (46) 23.07.88. Бюл. У 27 (7 1) Куйбышевский институт инженеров железнодорожного транспорта (72) Б.И.Горохов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 635488, кл. G 06 F 15/20, 1976.

Авторское свидетельство СССР

У 1315996, кл.. С 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ ОПТИМАЛЬНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения произвольной конечной системы линейных неравенств. Цель изобретения — повышение быстродействия устройства. Поставленная цель достигается тем, что

I устройство содержит регистр 1 векторов, Ь групп по С ключей 2, -2, где

b и С вЂ” разрядность и соответственно число входных векторов, блок 3 вычисления среднего значения векторов, блок 4 вычисления текущего вектора групп блоков 5, -5 вычисления скалярного произведения, блок 6 определения минимума, первый блок 7 вычисления скалярного произведения, первый блок

8 деления, блок 9 анализа максимума, выходной регистр 10, блок 11 вычисления модуля вектора, умножитель 12, блок 13 сравнения, элемент И 14,блок

15 индикации, блок 16 синхронизации, блок 17 вычитания, второй 18 и третий

19 блоки вычисления скалярного произведения, второй блок 20 деления, блок

21 выбора минимума двух величин, 1 з.п. ф-лы, 3 ил.

1411774

Изобретение относится к автоматике и вычислительной технике и может

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

Цель изобретения — повышение быстродействия устройства.

На фиг.1 приведена структурная схема устройства; на фиг.2 — струк- !О турная схема блока вычисления текущего вектора; на фиг.3 — временные диаграммы работы блока синхронизации.

Устройство содержит регистр 1 векторов, Ъ групп ключей 2»-21,, блок 3 I5 вычисления среднего значения векторов, блок-4 вычисления текущего вектора, группу из Ъ блоков 5, -5(вычисления скалярного произведения,.блок б определения минимума, первый блок 7 20 вычисления скалярного произведения, первый блок 8 деления, блок 9 аналй-. за максимума, выходной регистра IO, блок 1 1 вычисления модуля вектора, умножитель 12, блок 13 сравнения, элемент И 14, блок 15 индикации, блок 16 синхронизации, блок 17 вычитания, второй 18 и третий 19 блоки вычисления скалярного произведения, второй блок 20 деления и блок 21 вы- ЗО бора минимума двух величин, выход 22 устройства. (Блок 4 вычисления текущего вектора ° содержит первый сумматор 23, умножитель 24, второй .сумматор 25, регистр

26 и группу из С эпементов НЕ 27, информационные входы 28, выходы 29, управляющий вход 30 и вход 31 синхро низации.

Нахождение оптимального решения 40 системы линейных неравенств сводится к следующему.

Пусть задана система линейных неравенств а,; х ° ) О, i 6 1,Ь. 45

1"- »

Коэффициенты а представляют собой множество В векторов (точек) в

С-мерном пространстве. Для нахождения оптимального решения требуется найти 50 такую гиперплоскость, проходящую через начало координат, расстояние от которой до ближайшей точки множества

В максимально при всевозможных расположениях гиперплоскостей. Множество

В является множеством входных векторов, а оптимальный вектор решения системы линейных неравенств - оптимальным вектором струк-туры.

Оптимальным вектором структуры называется такой единичный вектор, минимальное значение скалярных произведений которого на все входные векторы (минимальное значение взвешенной суммы) является максимальным среди всех единичных векторов.

Вычисления текущего вектора структуры производятся циклически, причем направление движения в k-м цикле остается неизменным и задается вектором у„ - Як, где Я„- выходной вектор блока вычисления текущего вектора, у„ — выходной вектор блока вычисления среднего значения векторов. Максимальное изменение модуля текущего вектора структуры в цикле будет в том случае, когда новый вектор структуры перпендикулярен направлению ук- 1к, так как этот перпендикуляр является наименьшим расстоянием от .отрезка y — 9 до начала координат.

Вычисление текущего вектора структуры в k-м цикле производится по формуле

"к+» = "к+Ч к (Ук »к ) °

Блок 17 вычитания производит вычисление вектора 4 -у„, блок 18 вычисления скалярного произведения определяет модуль этого вектора, а блок

19 вычисления скалярного произведения определяет скалярное произведение этого вектора на текущий вектор структуры. Делитель 20 и блок 21 выбора минимума двух величин вычисляют Ч„.

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

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

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

В регистр 1 векторов предварительно записываются все координаты всех входных векторов, определяющих систему линейных неравенств. В блок 4

1411774 — Я„+<1 „(У„Я„), где y„ — IIbI HoH IIe ToII oK 3;

q = пп.п(1, ). (a», к к )

К (-у )2

Запись текущего вектора структуры в блок 4 происходит при поступлении тактирующего импульса с четвертого выхода блока 16 синхронизации. Так как текущий вектор структуры изменяется в каждом цикле, то изменяются значения скалярных произведений этого

55

".àïèñûâàåòñÿ начальный вектор структуры, в качестве которого можно взять любой из входных векторов. В блок 9 анализа максимума в качестве мини5 мальной взвешенной суммы записывается максимальное по абсолютной величине отрицательное число.

Вычисления производятся циклически. Началом цикла считается импульс на четвертом выходе блока 16 синхронизации. Поэтому первый цикл вычислений отличается от остальных отсутствием первого тактирующего импульса на входе синхронизации блока 4, так как в этом блоке уже записан начальный вектор структуры.

В течение одного цикла устройство работает следующим образом.

После записи в блок 4 текущий век-20 тор структуры перемножается скалярно со всеми входными векторами в блоках

5» -5 вычисления скалярного произведения, минимальное значение из всех скалярных произведений определяется ?5 в блоке 6 определения минимума, у которого появляются единичные сигналы на тех выходах, которым соответствуют минимальные значения взвешенных сумм на входе. 30

Возбужденные выходы блока 6 определения минимума открывают соответствующие ключи 2, -2 и соответствующие этим ключам входные векторы поступают на входы блока 3 вычисления среднего значения векторов. На выходе последнего образуется вектор, значение каждой координаты равно среднему арифметическому значений координат

Всех ВхОдных ВектОрОВ на ВхОде ° IIpH 40 поступлении тактирующего импульса на вход синхронизации блока 3 в нем происходит запоминание этого вектора.

Блок 4 производит вычисление текущего вектора структуры в k-м цикле 45 по формуле вектора со всеми входными векторами на выходах блоков 5,-5 вь|числения скалярного произведения группы, в результате чего возбуждаются другие выходы в блоке 6 определения ьп нимума. При этом оказываются открытыми другие из ключей 2,-21, и другие входные векторы подаются из регистра 1 векторов на входы блока 3, что приводит к изменению выходного вектора у этого блока в каждом цикле. Таким образом, на вход блока 4 всегда подается вектор, скалярное произведение которого на текущий вектор структуры минимально для всех входных векторов, так как у вычисляется в цикле после записи в память текущего вектора структуры.

Изменение выходного вектора блока

4 „ приводит к увеличению минимальной взвешенной суммы. Однако это изменение происходит не обязательно монотонно, так как среди входных векторов находятся такие, для которых скалярное произведение (Я, х; ) при этом уменьшается и может стать меньше значения Е„ . Вместе с тем происходит монотонное уменьшение модуля текущеI o вектора структуры — 11 1, так как

Ih„l всегда больше минимальной взвешенной суммы — Е„, т.е. (2„!) / (В)Ъ.

) E„. Поэтому, значение минимальной взвешенной суммы в целом увеличивается в ходе вычислений, стремясь в пределе к значению Я .

После записи в память выходного вектора блока 3 блок 7 вычисления скалярного произведения и блок 8 деления вычисляют значение минимальной взвешенной суммы, которое анализируется блоком 9 анализа максимума. Если это значение не превьппает значения минимальной взвешенной суммы, запомненное в блоке, то на выходе блока 9 анализа максимума имеется нулевой сигнал, который повторяется на выходе элемента И 14, поэтому запись в выходной регистр 1О в данном цикле запрещена.

Модуль выходного вектора блока 4 вычисляется в блоке 11 вычисления модуля вектора и в блоке l3 сравнения производится сравнения этого модуля, умноженного в умножителе !2 на коэффициент 1-&, поступающий на первый вход задания настроечного параметра устройства со значением минимальной взвешенной суммы на выходе блока 8

1411774 деления, т.е. проверяется условие „> (1-Ь)1 „1 ° Если это условие вы. полняется, т.е. сигнал с выхода ум ножителя 12 не превышает значения ! минимальной взвешенной суммы, то вы, ходной сигнал блока 13 сравнения равен нулю. В противном случае он равен единице. При поступлении нуле1 вого сигнала на вход блока 15 индика-10 ции последний сигнализирует о том, :что заданная точность вычислений до стигнута. !

Блок 17 вычитания вычисляет раз-! ность векторов, поступающих с выходов15 блока 4 и блока 3. Квадрат модуля выходного вектора блока 17 вычитания определяется в блоке 18 вычисления скалярного произведения, а скалярное произведение этого вектора на выход- 20 ной вектор больше 4 определяется в блоке 19 вычисления скалярного произведения. Блок 20 деления и блок 21

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

На первом входе элемента И 14 еди ничный сигнал появляется, когда значение минимальной взвешенной суммы на выходе блока 8 деления превышает все предыдущие его значения, на втором входе элемента И 14 единичный сигнал поддерживается до момента достижения заданной точности вычислений, сигнал на третьем входе элемента И

14 является разрешающим для записи выходного вектора блока 4 в выходной ,регистр. Таким образом, запись этого ( вектора производится при возрастании 4g минимальной взвешенной сумм на выходе блока 8 деления, пока заданная точ" ность вычислений еще не достигнута.

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

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

1. Устройство для оптимального решения системы линейных неравенств, 55 содержащее регистр векторов, Ь групп по С ключей в кажцой, где С и Ь вЂ” разрядность и число ;;входных векторов соответственно, блок определения минимума, группу из Ъ блоков вычисления скалярного произведения, блок вычисления среднего значения векторов, блок вычисления текущего вектора, выходной регистр, первый блок вычисления скалярного произведения, первый блок деления, блок анализа максимума, блок вычисления модуля вектора, умножитель, блок сравнения, элемент И, блок синхронизации, причем входы векторов устройства подключены к информационным входам регистра векторов, i -я группа выходов регистра векторов, где 1 =1,2,...,6, подключена к информационным входам 1 -й группы ключей и к первой группе информационных входов i -ro блока вычисления скалярного произведения группы, выход которого подключен к 1-му информационному входу блока определения минимума, 1 -й выход которого подключен к управляющему входу ключей 1-й группы, выходы которых .подключены к 1-й группе информационных входов блока вычисления среднего значения векторов, выходы которого подключены к первой группе информационных входов первого блока вычисления скалярного произведения и к информационным входам блока вычисления среднего значения векторов, выходы, которого подключены к второй группе информационных входов первого блока вычисления скалярного произведения, к вторым группам информационных входов блоков вычисления скалярных произведений группы, к информационным входам выходного регистра и к информационным входам блока вычисления модуля вектора, выход которого подключен к первым информационным входам первого блока деления и умножителя, второй информационный вход первого блока деления подключен к выходу первого блока вычисления скалярного произведения, выход первого блока деления подключен к информационному входу блока анализа максимума и к первому входу блока сравнения, выход блока анализа максимума подключен к первому входу элемента И, выход которого подключен к входу синхронизации выходного регистра, выход блока сравнения подключен к второму входу элемента И и является выходом признака окончания вычислений усгройства, второй информационный вход умножителя подключен к первому входу задания настроечного параметра устройства, 1411774 выход умножителя подключен к второму входу блока сравнения, с первого по четвертый выходы блока синхронизации подключены соответственно к входу синхронизации блока вычисления среднего значения векторов, к третьему входу элемента И, к входу синхронизации блока анализа максимума и к входу синхронизации блока вычисления теку- 1О щего вектора, выходы выходного регистра подключены к выходам результата устройства, отличающееся тем, что, с целью повышения быстро Действия, устройство содержит блок вычитания, второй и третий блоки вычисления скалярного произведения, второй блок деления и блок выбора минимума двух величин, причем выходы блока вычисления среднего значения 20 векторов подключены соответственно к первой группе информационных входов блока вычитания, выходы которого подключены к первой и второй группам информационных входов второго блока 25 вычисления скалярного произведения и к первой группе информационных входов третьего блока вычисления скалярного произведения, выходы блока вычисления текущего векторы подключены gg к второй группе информационных входов .блока вычитания и к второй группе информационных входов третьего блока вычисления скалярного произведения, Bblxopbl BTop01 0 H третьего 6JIGKQB Bbl 35 числения скалярного произведения подключены соответственно к первому и второму информационным входам второго блока деления, выход которого подключен к первому информационному входу блока выбора минимума двух величин, второй вход которого подключен к второму входу задания настроечного параметра устройства, выход блока выбора минимума двух величин подключен к управляющему входу блока вычисления текущего вектора.

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок вычисления текущего вектора содержит два сумматора, умножитель, регистр и группу из С элементов НЕ, причем информационные входы блока вычисления текущего вектора подключены к первой группе информационных входов первого сумматора, выход которого подключен к первому информационному входу умножителя, второй информационный вход которого подключен к управляющему входу блока вычисления текущего вектора, выходы умножителя подключены к первой группе информационных входов второго сумматора, выход которого подключен к информационному входу регистра, вход синхронизации которого подключен к входу синхронизации блока вычисления текущего вектора,: выходы регистра подключены к входам элемен,тов НЕ группы, к второй группе ин » формационных входов второго сумматора и к выходам блока вычисления текущего вектора, выходы элементов НЕ группы подключены соответственно к второй группе информационных входов первого сумматора.

1411774

BN .!

Составитель В.Смирнов

Редактор Н.Бобкова Техред А.Кравчук

Корректор А.Обручар

Заказ 3656/46 Тираж 704 Подписное

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

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

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