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

 

Изобретение относится к автоматике и вычислительной технике. Целью изобретения является разработка устройства, обеспечивающего более высокое быстродействие. Устройство включает К блоков памяти 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