Устройство для решения задач целочисленного линейного программирования

 

Изобретение относится к автоматике и вычислительной технике. Целью изобретения является разработка устройства, обеспечивающего более высокое быстродействие. Устройство включает К блоков памяти 3 (К 2), К счетчиков 2, К-1 элементов ИЛИ 4, К-1 блоков формирования переноса 12, сумматор 7, К+1 цифроаналоговых преобразователей 5, элементы И 1 и 10, блоки сравнения 8 и 9. Технический результат - повышение быстродействия достигается за счет исключения перебора заведомо непригодных комбинаций управляемых переменных. 2 ил.

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

Известные устройства (АС СССР N 1180925 G 06 F 15/32, 15/20 от 1984 г., АС СССР N 1247888 G 06 F 15/32, 15/20 от 30.07.1986, бюл. N 28) позволяют решать целочисленные задачи математического программирования, но имеют низкое быстродействие, связанное со значительными затратами времени на перебор заведомо непригодных альтернатив, возникающих при определенных обстоятельствах.

Наиболее близким к заявляемому по своей технической сущности является "Устройство для решения целочисленных задач математического программирования" (АС СССР N 1247888 G 06 F 15/32, G 06 F 15/20 от 30.07.1986, бюл. N 28), выбранное в качестве устройства-прототипа.

Устройство-прототип содержит K блоков памяти, K цифроаналоговых преобразователей, первый и второй блоки сравнения, сумматор, первый и второй элементы И, K-1 элементов ИЛИ, элемент НЕ, K-2 блоков формирования переноса, K счетчиков, выход каждого из которых подключен к входу соответствующего цифроаналогового пре образователя и к первому информационному выходу устройства, выход первой схемы сравнения является выходом сигнала окончания решения устройства, адресный вход каждого блока памяти соединен с выходом соответствующего счетчика, выходы цифроаналоговых преобразователей, кроме K-го, соединены соответственно с входами сумматора, один из входов которого соединен с информационным входом устройства, выход K-го цифроаналогового преобразователя соединен с первым информационным входом первого блока сравнения, выход сумматора соединен со вторым информационным входом первого блока сравнения и с информационным входом второго блока сравнения, разрешающий вход которого и первый вход первого элемента И соединены с тактовым входом устройства, выход первого элемента И соединен с разрешающим входом первого блока сравнения, выход второго блока сравнения соединен со вторым входом первого элемента И, первый вход первого элемента ИЛИ соединен с выходом первого блока памяти, выход первого элемента ИЛИ соединен со входом сброса первого счетчика, с входом считывания второго блока памяти и со счетным входом второго счетчика, выход K-го блока памяти является вторым информационным выходом устройства, первый вход каждого из блоков формирования переноса, начиная с первого, соединен с выходом соответствующего счетчика, второй вход первого блока формирования переноса соединен с выходом элемента НЕ, второй вход i-го блока формирования переноса соединен с первым выходом (i-1)-го блока формирования переноса, первый вход i-го элемента ИЛИ соединен с выходом i-го блока памяти, а выход соединен с входом сброса i-го счетчика, со счетным входом (i+1)-го счетчика и с входом считывания (i+1)-го блока памяти, первый выход (K-2)-го блока формирования переноса соединен со вторым входом (K-1)-го элемента ИЛИ, второй выход i-го блока формирования переноса соединен со вторым входом 1-го элемента ИЛИ, выход (K-1)-го элемента ИЛИ соединен с установочным входом первого счетчика, первый вход второго элемента И соединен с тактовым входом устройства, второй вход подключен к выходу элемента НЕ, выход второго элемента И соединен со счетным входом первого счетчика и с входом считывания первого блока памяти, вход элемента НЕ соединен с выходом второй схемы сравнения, причем блок формирования переноса содержит два элемента И, элемент НЕ и элемент НЕ-И, вход которого является первым входом блока, а выход соединен с первым входом первого элемента И и через элемент НЕ - с первым входом второго элемента И, вторые входы первого и второго элементов И соединены со вторым входом блока, выходы первого и второго элементов И являются соответственно первым и вторым выходами блока.

Устройство-прототип предназначено для решения задач, например, раскроя с минимальными остатками материала длиной L на заготовки длиной I_i с потребным количеством каждого типа N_i: найти при L = L-(n₁I₁+n₂I₂+...+n_kI_n) 0, где n_i - целое, 0 n_i N_i; L L_max; L, I_i, N_i > 0- заданные величины.

Известное техническое решение обладает низким быстродействием, связанным со значительными затратами времени на перебор заведомо непригодных комбинаций управляемых переменных n_i, доставляющих целевой функции L значения в диапазоне от нуля до L_min, где L_min - минимальное значение величины допуска, получаемое разбиением L_max на M частей: L_min= L_max/M. Целью изобретения является разработка устройства, обеспечивающего более высокое быстродействие за счет исключения перебора заведомо непригодных комбинаций управляемых переменных.

Поставленная цель достигается тем, что в устройство для решения задач целочисленного линейного программирования, содержащее K блоков памяти, где K 2, K цифроаналоговых преобразователей, первый и второй блоки сравнения, сумматор, первый и второй элементы И, K-1 элементов ИЛИ, элемент НЕ, K-2 блоков формирования переноса, K счетчиков, выходы каждого из которых поразрядно подключены к входам соответствующего цифроаналогового преобразователя и к соответствующим выходам первой группы информационных выходов устройства, выход первого блока сравнения является выходом сигнала окончания решения устройства, адресные входы каждого блока памяти поразрядно соединены с выходами соответствующего счетчика, выход i-го цифроаналогового преобразователя соединен с (i+1)-м входом сумматора, первый вход которого является информационным входом устройства, выход K-го цифроаналогового преобразователя соединен с первым информационным входом первого блока сравнения, выход сумматора соединен со вторым информационным входом первого блока сравнения и с первым информационным входом второго блока сравнения, разрешающий вход которого и первый вход первого элемента И соединены с тактовым входом устройства, выход первого элемента И соединен с разрешающим входом первого блока сравнения, выход второго блока сравнения соединен со вторым входом первого элемента И и входом элемента НЕ, первая группа входов первого элемента ИЛИ соединена с выходами первого блока памяти, выход первого элемента ИЛИ соединен со входом сброса первого счетчика, со входом считывания второго блока памяти и со счетным входом второго счетчика, выходы K-го блока памяти являются второй группой информационных выходов устройства, первая группа входов каждого из блоков формирования переноса, начиная с первого, поразрядно соединена с выходами соответствующего счетчика, второй вход первого блока формирования переноса соединен с выходом элемента НЕ, второй вход i-го блока формирования переноса соединен с первым выходом (i-1)-го блока формирования переноса, первая группа входов i-го элемента ИЛИ поразрядно соединена с выходами i-го блока памяти, а выход соединен со входом сброса i-го счетчика, со счетным входом (i+1)-го счетчика и со входом считывания (i+1)-го блока памяти, первый выход (K-2)-го блока формирования переноса соединен со вторым входом (K-1)-го элемента ИЛИ, второй выход i-го блока формирования переноса соединен со вторым входом i-го элемента ИЛИ, выход (K-1)-го элемента ИЛИ соединен с установочным входом первого счетчика, входы занесения данных которого являются первой установочной шиной устройства, первый вход второго элемента И соединен с тактовым входом устройства, второй вход второго элемента И подключен к выходу элемента НЕ, выход второго элемента И соединен со счетным входом первого счетчика и со входом считывания первого блока памяти, дополнительно введен (K+1)-й цифроаналоговый преобразователь. Группа входов последнего соединена со входами занесения данных K-го счетчика и одновременно является второй установочной шиной устройства, а выход (K+1)-го цифроаналогового преобразователя подключен к второму информационному входу второго блока сравнения.

Перечисленная новая совокупность существенных признаков заявленного устройства обеспечивает более высокое быстродействие за счет исключения перебора заведомо непригодных комбинаций управляемых переменных, доставляющих целевой функции L значения в диапазоне от нуля до L_min. Так, из [1, 2] известно, что при решении задач целочисленного линейного программирования вида (1) число переборов возможных комбинаций управляемых переменных можно сократить за счет применения ограничения L < L_min. В устройстве-прототипе условием, запрещающим перебор непригодных комбинаций, является условие L < 0 (проверяемое во втором блоке сравнения).

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

Устройство для решения задач целочисленного линейного программирования, показанное на фиг. 1, содержит K блоков памяти 3₁, 3₂, ..., 3_K, K+1 цифроаналоговых преобразователей 5₁, 5₂, ..., 5_K+1, первый 9 и второй 8 блоки сравнения, сумматор 7, первый 10 и второй 1 элементы И, K-1 элементов ИЛИ 4₁, 4₂, ..., 4_K-1, элемент НЕ 11, K-2 блоков формирования переноса 12₁, 12₂, ... , 12_K-2 и K счетчиков 2₁, 2₂, ..., 2_K. Выходы каждого из K счетчиков 2₁, 2₂, . . . , 2_K поразрядно подключены к входам соответствующего цифроаналогового преобразователя 5₁, 5₂, ..., 5_K и к соответствующим выходам 16₁, 16₂, ..., 16_K первой группы информационных выходов устройства. Выход первого блока сравнения 9 является выходом 17 сигнала окончания решения устройства. Адресные входы каждого блока памяти 3₁, 3₂, ..., 3_K поразрядно соединены с выходами соответствующего счетчика 2₁, 2₂, ..., 2_K. Выход i-го цифроаналогового преобразователя 5_i соединен с (i+1)-ым входом сумматора 7. Первый вход сумматора 7 является информационным входом 15 устройства. Выход K-го цифроаналогового преобразователя 5_K соединен с первым информационным входом первого блока сравнения 9. Выход сумматора 7 соединен со вторым информационным входом первого блока сравнения 9 и с первым информационным входом второго блока сравнения 8. Разрешающий вход второго блока сравнения 8 и первый вход первого элемента И 10 соединены с тактовым входом 13 устройства. Выход первого элемента И 10 соединен с разрешающим входом первого блока сравнения 9. Выход второго блока сравнения 8 соединен со вторым входом первого элемента И 10 и входом элемента НЕ 11. Первая группа входов первого элемента ИЛИ 4₁ соединена с выходами первого блока памяти 3₁. Выход первого элемента ИЛИ 4₁ соединен со входом сброса первого счетчика 2₁, со входом считывания второго блока памяти 3₂ и со счетным входом второго счетчика 2₂. Выходы K-го блока памяти 3_K являются второй группой информационных выходов 18 устройства. Первая группа входов каждого из блоков формирования переноса 12₁, 12₂, . . ., 12_K-2, начиная с первого, поразрядно соединена с выходами соответствующего счетчика 2₁, 2₂, ..., 2_K-2. Второй вход первого блока формирования переноса 121 соединен с выходом элемента НЕ 11. Второй вход i-го блока формирования переноса 12_i соединен с первым выходом (i-1)-го блока формирования переноса 12_i-1. Первая группа входов i-го элемента ИЛИ 4_i поразрядно соединена с выходами 1-го блока памяти 3_i, а выход соединен со входом сброса i-го счетчика 2_i, со счетным входом (i+1)-го счетчика 2_i+1 и со входом считывания (i+1)-го блока памяти 3_i+1. Первый выход (K-2)-го блока формирования переноса 12_K-2 соединен со вторым входом (K-1)-го элемента ИЛИ 4_K-1. Второй выход i-го блока формирования переноса 12_i соединен со вторым входом i-го элемента ИЛИ 4_i. Выход (K-1)-го элемента ИЛИ 4_K-1 соединен с установочным входом первого счетчика 2₁. Входы занесения данных первого счетчика 2₁ являются первой установочной шиной 14 устройства. Первый вход второго элемента И 1 соединен с тактовым входом 13 устройства, а второй вход подключен к выходу элемента НЕ 11. Выход второго элемента И 1 соединен со счетным входом первого счетчика 2₁ и со входом считывания первого блока памяти 3₁. Группа входов (K+1)-го цифроаналогового преобразователя 5_K+1 соединена со входами занесения данных K-го счетчика 2_K и одновременно является второй установочной шиной 19 устройства. Выход (K+1)-го цифроаналогового преобразователя 5_K+1 подключен к второму информационному входу второго блока сравнения 8.

Блок формирования переноса 12, показанный на фиг. 2, содержит первый 123 и второй 124 элементы И, элемент НЕ 122 и элемент НЕ-И. Входы последнего являются первой группой входов 12.1 блока 12. Выход элемента НЕ-И 121 соединен с первым входом второго элемента И 124 и через элемент НЕ 122 - с первым входом первого элемента И 123. Вторые входы первого 123 и второго 124 элементов И соединены с вторым входом 12.2 блока 12. Выходы первого 123 и второго 124 элементов И являются соответственно первым 12.3 и вторым 12.4 выходами блока 12.

Заявленное устройство работает следующим образом.

В исходном состоянии счетчики 2₁, 2₂, ..., 2_K-1 обнулены. В i-ом блоке памяти 3_i записана единица по тому адресу, код которого равен N_i. Запись этой информации производится занесением кода N_i в соответствующий счетчик 2_i и подачей сигнала "Запись "1" на блоки памяти 3_i (эти входы с целью упрощения не показаны). В K-м блоке памяти 3_K записан код числа M ~ L_max. На информационный вход 15 устройства подан сигнал, пропорциональный величине L. На первую установочную шину 14 подается код числа n^* = min {N₁, [L/I₁]}, где [L/I₁] - целая часть от L/I₁. На установочной шине 19 присутствует код числа L_min. Последнее заносится в счетчик 2_K и используется в качестве текущего значения L_тек целевой функции, с которым будет производится поиск оптимального решения.

На вход 13 устройства поступает тактовый сигнал и, если элемент И 1 открыт, увеличивает на единицу содержимое первого счетчика 2₁. Его код поступает на первый цифроаналоговый преобразователь 5₁, на выходе которого появляется сигнал, пропорциональный n₁. Поскольку коэффициент передачи сумматора 7 по первому входу равен I₁, то на выходе сумматора 7 появляется сигнал L = (L-n₁I₁). Тактовый сигнал 13 разрешает сравнение в блоке сравнения 8. Если (L-n₁I₁) L_min, то выходной сигнал блока сравнения 8, пройдя через элемент И 10, разрешает сравнение в блоке сравнения 9. Если (L-n₁I₁) < L_тек (последнее поступает со счетчика 2_K через цифроаналоговый преобразователь 5_K), то сигнал на выходе 17 означает, что искомое решение найдено и с выходов 16₁ может быть считано значение n₁, а с выходов 16_K - значение L_тек, при котором это решение найдено. На этом работа устройства заканчивается.

Если решение не найдено, то к первому счетчику 2₁ вновь прибавляется единица и процесс повторяется. Пусть в некоторый момент в i-ом счетчике 2_i величина n_i > N_i, тогда единица, считываемая из соответствующего блока памяти 3_i, пройдя элементы ИЛИ 4₁, 4₂, ..., 4_K-2, сбрасывает этот i-ый счетчик 2_i и прибавляет единицу к (i+1)-му счетчику 2_i+1. Таким образом, обеспечивается условие n_i N_i. Если решение с L_тек не найдено, то аналогичным образом увеличивается содержимое счетчика 2_i+1, а следовательно, L_тек.
При L_тек> L_max сигнал с блока памяти 3_K поступает на выход устройства 18, что свидетельствует о невозможности нахождения решения с заданными L_max. Пусть в некоторый момент времени значение L, полученное на выходе сумматора 7, меньше L_min, тогда сигнал с выхода блока сравнения 8, пройдя через элемент НЕ 11, закрывает элемент И 1 и прекращает подачу тактовых импульсов на первый счетчик 2₁ и блок памяти 3₁. Кроме того, он поступает на второй вход первого блока формирования переноса 12₁. Если в данный момент счетчик 2₁ обнулен, то на втором выходе первого блока формирования переноса 12₁ формируется сигнал переноса, который поступает на второй вход следующего блока формирования переноса 12₂. Таким образом, сигнал с элемента НЕ 11 минует все счетчики 2_i, в которых записан код нуля. Наконец, достигнув некоторого счетчика 2_m, содержимое которого отлично от нуля, этот сигнал проходит на первый выход соответствующего блока формирования переноса 12_m и поступает на элемент ИЛИ 4_m. В результате сигнал с выхода последнего сбрасывает счетчик 2_m, прибавляет единицу к следующему счетчику 2_m+1 и считывает содержимое блока памяти 3_m+1. Наконец, если причина того, что L < L_min, - ненулевое состояние (K-1)-го счетчика 2_K-1 или n_K-1 N_K, то выходной сигнал с (K-1)-го элемента ИЛИ 4_K-1, кроме указанных выше действий, подается на установочный вход первого счетчика 2₁. В результате код числа n^*, подаваемый на установочную шину 13, записывается в первый счетчик 2₁. Последнее действие целесообразно произвести, поскольку в этот момент все счетчики 2_i обнулены и поиск оптимального решения имеет смысл начинать только с некоторой комбинации управляемых переменных n^*, 0, ..., 0. Далее цикл работы устройства по нахождению оптимального решения повторяется по вышеописанному алгоритму.

Входящие в структурную схему заявляемого устройства элементы известны и описаны, например, в [3]. Так, в указанном источнике описаны принципы построения и примеры реализации:
счетчиков 2 - на с. 85-86 (можно реализовать на микросхеме К155ИЕ5):
блоков памяти 3 - на с. 171- 174 (можно реализовать на микросхеме К155ПР6);
Элементы И 1 и 10, ИЛИ 4 и НЕ 11 можно реализовать на микросхемах соответственно К155ЛИ1, К155ЛЕ4 и К155ЛН1.

Принципы построения цифроаналоговых преобразователей 5 подробно изложены в [4] на с. 115-286. Можно реализовать, например, на микросхемах типа monoDAC-02 (см. [4], с. 186, рис. 4.72).

Принципы построения сумматора 7 известны и изложены, например, в [5] на с. 16-18 и с. 34-36. Может быть реализован на операционном усилителе (например, микросхема К140УД8А) с входными сопротивлениями, обеспечивающими коэффициент передачи от i-го цифроаналогового преобразователя, пропорциональный I_i.

Принцип работы блоков сравнения 8 и 9 известен и описан в [6] на с. 234-257. Можно реализовать на микросхемах К561ИП2 (см. [7] на с. 114, рис. 4.12 б).

Реализация блоков формирования переноса 12 известна из описания устройства-прототипа и приведена на фиг. 2.

Литература
1. Г. Вагнер. Основы исследования операций. Том 3. -М.: Мир, 1973. -С. 284-294.

2. Малышев С.P., Подымов В.А. Управление временными ресурсами спутниковой системы связи.// Радиотехника, 1997. N 10. -С. 15-18.

3. В. Л. Шило. Популярные цифровые микросхемы. Справочник. -М.: Радио и связь, 1988.

4. Гнатек Ю.Р. Справочник по цифроаналоговым и аналого-цифровым преобразователям: Пер. с англ./ Под ред. Ю.А. Рюжина. -М.: Радио и связь, 1982.

5. Лихачев В.Д. Практические схемы на операционных усилителях. -М.: ДОСААФ, 1981.

6. Ю. В. Гаврилов, А.Н. Пучко. Арифметические устройства быстродействующих ЭЦВМ. -М.: Советское радио, 1970.

7. В. Н. Вениаминов, О.Н. Лебедев, А.И. Мирошниченко. Микросхемы и их применение. Справочное пособие, 3-е изд. перераб. и дополн. -М.: Радио и связь, 1989.

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

Устройство для решения задач целочисленного линейного программирования, содержащее К блоков памяти, где К 2, К цифроаналоговых преобразователей, первый и второй блоки сравнения, сумматор, первый и второй элементы И, К-1 элементов ИЛИ, элемент НЕ, К-2 блоков формирования переноса, К счетчиков, выходы каждого из которых поразрядно подключены к входам соответствующего цифроаналогового преобразователя и к соответствующим выходам первой группы информационных выходов устройства, а входы занесения данных К-го счетчика являются второй установочной шиной устройства, выход первого блока сравнения является выходом сигнала окончания решения устройства, адресные входы каждого блока памяти поразрядно соединены с выходами соответствующего счетчика, выход i-го цифроаналогового преобразователя соединен с (i+1)-м входом сумматора, первый вход которого является информационным входом устройства, выход К-го цифроаналогового преобразователя соединен с первым информационным входом первого блока сравнения, выход сумматора соединен со вторым информационным входом первого блока сравнения и с первым информационным входом второго блока сравнения, разрешающий вход которого и первый вход первого элемента И соединены с тактовым входом устройства, выход первого элемента И соединен с разрешающим входом первого блока сравнения, выход второго блока сравнения соединен со вторым входом первого элемента И и входом элемента НЕ, первая группа входов первого элемента ИЛИ соединена с выходами первого блока памяти, выход первого элемента ИЛИ соединен со входом сброса первого счетчика, со входом считывания второго блока памяти и со счетным входом второго счетчика, выходы К-го блока памяти являются второй группой информационных выходов устройства, первая группа входов каждого из блоков формирования переноса, начиная с первого, поразрядно соединена с выходами соответствующего счетчика, второй вход первого блока формирования переноса соединен с выходом элемента НЕ, второй вход i-го блока формирования переноса соединен с первым выходом (i-1)-го блока формирования переноса, первая группа входов i-го элемента ИЛИ поразрядно соединена с выходами i-го блока памяти, а выход соединен со входом сброса i-го счетчика, со счетным входом (i+1)-го счетчика и со входом считывания (i+1)-го блока памяти, первый выход (К-2)-го блока формирования переноса соединен со вторым входом (К-1)-го элемента ИЛИ, второй выход i-го блока формирования переноса соединен со вторым входом i-го элемента ИЛИ, выход (К-1)-го элемента ИЛИ соединен с установочным входом первого счетчика, входы занесения данных которого являются первой установочной шиной устройства, первый вход второго элемента И соединен с тактовым входом устройства, второй вход второго элемента И подключен к выходу элемента НЕ, выход второго элемента И соединен со счетным входом первого счетчика и со входом считывания первого блока памяти, отличающееся тем, что дополнительно введен (К+1)-й цифроаналоговый преобразователь, группа входов которого соединена со входами занесения данных К-го счетчика, а выход подключен к второму информационному входу второго блока сравнения.

РИСУНКИ

Рисунок 1, Рисунок 2