§ 3. Задачи логического проектирования

В самые последние годы для моделей дискретного программирования наметилось одно совершенно новое поле приложений. Речь идет о довольно разнообразном круге задач оптимизации, связанных, с одной стороны, с вопросами проектирования логических и вычислительных устройств, а с другой — примыкающих к некоторым современным проблемам теоретической кибернетики (прежде всего — дискретного анализа). В этом параграфе описаны некоторые характерные постановки задач такого рода.

3.1. Рассмотрим задачу о расположении производственных единиц. Пусть имеется неделимых производственных единиц, которые в дальнейшем мы для крат-» кости будем называть центрами; каждую из этих производственных единиц требуется расположить в одном из возможных мест. Затраты, связанные непосредственно с помещением центра на место («затраты на установку»), равны Известны «расстояния» от места до места (числа вовсе не обязаны равняться соответствующим геометрическим расстояниям; они являются лишь оценкой затрат, связанных с перемещением из Заданы, кроме того, производственные «потоки» из центра в центр

Отметим, что, не умаляя общности, можно положить Действительно, в случае введем дополнительные фиктивные центры положив для них при при или

Нашей целью является назначение (закрепление) центров по местам, минимизирующее суммарные затраты. Каждое такое назначение представляет собой перестановку чисел ( при этом любое из проводимых закреплений центра за местом описывается соответствием Для любого назначения мы имеем, во-первых, «непосредственные» затраты, равные во-вторых, затраты на взаимосвязь между парами центров; мы будем предполагать, что эти затраты при помещении центра

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

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

В случае независимости производственных центров и задача минимизации (3.1) по всем перестановкам превращается в задачу о назначениях, описанную в § 2 гл. 3. В этом случае можно интерпретировать как своеобразую «меру нежелательности» назначения или, попросту говоря, как убытки, связанные с таким назначением. Наоборот, в других задачах можно пренебречь затратами на установку (или считать все эти затраты одинаковыми), так что речь будет идти только о минимизации суммарных «затрат по взаимодействию», т. е. второго слагаемого в (3.1).

Модель (3.1) -(3.2) имеет весьма широкие практические приложения, отражая существенные черты многих современных задач проектирования. Так, она может быть использована в вопросах планирования расстановки оборудования в цехах машиностроительных или химических предприятий. С другой стороны, она же может найти применения для задач о проектировании расположения деталей в ячейках вычислительных и управляющих устройств (например, при нахождении схем монтажа платы, минимизирующих суммарную длину соединений). Здесь эта модель описана в нарочито общих терминах в надежде, что различные более конкретные интерпретации читатель найдет сам.

Уже обращалось внимание на родство модели (3.1) — (3.2) с задачей о назначениях; действительно, целевая функция (3.1) отличается от целевой функции задачи о назначениях наличием дополнительного слагаемого, зависящего уже не от всевозможных назначений, а от всевозможных пар назначений. Сформулируем одну дискретную модель, известную под названием квадратичной задачи о назначениях, и продемонстрируем сведение к ней модели (3.1) -(3.2).

Квадратичная задача о назначениях заключается в следующем. Даны числа Требуется найти набор переменных принимающих значения и 1, минимизирующий

при условиях

Для сведения модели (3.1) — (3.2) к квадратичной задаче о назначениях введем, как и в обычной задаче о назначениях, переменные

Положим теперь

Очевидно, что каждое слагаемое в (3.3) будет равно в том и только в том случае, когда в противном случае оно равно нулю. Соотношения

же в терминах перестановок равносильны Получаем

Таким образом, целевая функция квадратичной задачи о назначениях преобразована к виду (3.1). Условия (3.4) — (3.5) этой задачи очевидны и интерпретируются точно так же, как и в обычной задаче о назначениях.

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

Решение квадратичной задачи о назначениях является с вычислительной точки зрения нелегким делом. В настоящее время для нее создано несколько точных и приближенных методов; правда, точные методы реализуемы лишь для задач сравнительно небольших размеров. Описание и сравнение (по результатам - численных экспериментов; нескольких приближенных методов дано в статье Хиллиера и Коннорса [96]; там же приведена библиография по данному вопросу.

3.2. Рассмотрим под несколько иным углом зрения описанные выше модели задач о покрытии (см. § 3 гл. 2). Напомним, что задача о покрытии заключается в минимизации

при условиях

причем все коэффициенты равны или 1.

Наряду с задачей о покрытии часто рассматривается взвешенная задача о покрытии, заключающаяся в минимизации

при условиях (3.8). Здесь заданные вещественные числа.

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

Сначала дадим общее описание вопроса в терминах синтеза схем. Задачу синтеза схем можно представить следующим образом. Под схемой понимается некоторое устройство с булевыми входами и одним булевым выходом. Требования к этой схеме предъявляются в виде списка, сопоставляющего каждой из возможных комбинаций нулей или единиц на входе соответствующее значение (О или 1) на выходе. Тем самым указанный список (таблица) задает некоторую булеву функцию, т. е. функцию, заданную на множестве -мерных векторов с компонентами и 1 и принимающую значения и 1 (см. [9а]). Это обстоятельство дает возможность параллельной интерпретации вопросов синтеза на логическом языке; однако мы будем проводить соответствующие аналогии лишь мимоходом.

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

Схема синтезируется из элементов, которые могут представлять собой реле, электронные лампы, полупроводниковые приборы и т. п. Однако техническая реализация этих элементов (и схем в целом) для нас сейчас совершенно безразлична. Важно лишь, что каждый элемент может находиться в одном из двух состояний (например, реле замкнуто — реле разомкнуто). Состоянию элемента «выключено» мы будем сопоставлять 0, состоянию «включено» — 1. Элементы можно соединять в блоки (цепи) двух типов: а) блоки, дающие на выходе 1 только в том случае, если все входы равны 1, б) блоки, дающие на выходе 1, если хотя бы один из входов равен 1. Блоки типа а) представляют собой последовательное соединение элементов, а блоки типа б) — параллельное соединение. Можно ограничиться рассмотрением схем, состоящих из нескольких блоков типа а) (входы которых являются входами схемы), соединенных в один блок типа б); выход последнего и является выходом схемы.

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

(см. скан)

а соединению их в блоки типа б) — операцию «сложения» с правилами

Определенные этими таблицами операции умножения и сложения называются булевыми операциями; полученная нами система с этими операциями представляет собой простейший случай так называемых булевых алгебр. Мы видим, что «булева арифметика» отличается от обычной лишь тождеством

Далее, булевы операции предполагаются ассоциативными:

и дистрибутивными;

Кроме того, для любого элемента а единственным образом определено его дополнение а обладающее свойством

Здесь под a, b, с понимаются любые элементы булевой алгебры (в нашем случае — нули и единицы). Дополнением нуля является единица, дополнением единицы — нуль. Дополнение а часто обозначают через 1 — а.

Отметим, что в логике булеву умножению отвечает конъюнкция, булеву сложению — дизъюнкция, дополнению — отрицание.

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

Итак, пусть нам задана таблица значений булевой функции т. е. таблица, в которой каждому из 2? векторов размерности состоящих из нулей и единиц, сопоставляется нуль или единица. Будем искать аналитическое выражение этой функции. Известный способ его построения заключается в

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

где

Произведения вида (3.13) называются фундаментальными произведениями. Составим теперь фундаментальное произведение для каждой строки в которой (количество таких строк обозначим через и образуем булеву сумму этих Р:

Формула (3.14) и дает нам аналитическое выражение требуемого вида. Теперь можно перейти ко второй проблеме синтеза — нахождению «простейшего», или «наиболее экономного» в определенном смысле аналитического выражения; сами эти понятия будут уточнены далее.

Введем еще одно важное понятие. Импликантом функции называется произведение вида

где некоторое подмножество множества индексов обладающее тем свойством, что из следует и такое, что при любом произведение

(т. е. любой собственный подмножитель (3.15)) этим свойством уже не обладает. Иначе говоря, импликант есть произведение переменных и их дополнений, составленное из минимального числа сомножителей и равное 1 только в случае Наиболее экономное представление мы будем искать в виде булевой суммы импликантов, содержащей минимальное число слагаемых.

Таким образом, нам нужно знать способ построения всех импликантов функции Для этого исходят из представления (3.14) и пытаются упростить его путем применения следующих двух правил.

Правило Если представление (3.14) содержит выражение вида где слагаемое входит множителем в то вычеркнуть из суммы

Правило II. Если представление содержит выражение вида 70 прибавить к сумме выражение при условии, что: а) не содержит произведений вида (ибо в этом случае не содержит подмножителя, уже фигурирующего в сумме в качестве отдельного слагаемого.

Формирование импликантов происходит следующим образом. К (3.14) последовательно применяют правило если его применение невозможно — правило II. Если невозможным становится применение обоих правил, процесс окончен, полученная в результате сумма состоит из всех импликантов.

Только теперь мы, наконец, подготовлены к формулировке задачи оптимального синтеза схемы в виде задачи о покрытии. Пусть фундаментальные произведения функции ее имплпканты. Положим

Иначе говоря, означает, что из следует Введем теперь переменные

Требуется найти набор с минимальным количеством импликантов. Это значит, что следует минимизировать функцию (3.7) (мы переходим теперь от булевого сложения к обычному!) при условии, что все единичные значения функции будут при этом обеспечены. Очевидно, что последнее требование как раз и выражается неравенствами, фигурирующими в (3.8). Таким образом, мы действительно пришли к задаче о покрытии.

Можно считать также, что каждому импликанту приписан «вес» (который может отражать, скажем, затраты на техническую реализацию соответствующего этому импликанту блока). В этом случае можно говорить о нахождении схемы с минимальным суммарным «весом». Ясно, что это требование описывается взвешенной задачей о покрытии (3.7), (3.8).

Обилие и новизна введенных в этом пункте понятий делают желательным иллюстративный пример. Пусть функция от четырех

булевых переменных описывается приводимой ниже таблицей.

(см. скан)

Здесь (соответствующие строки отмечены слева звездочками), так что представление (3.14) будет иметь вид

Теперь приступим к поиску импликантов. Рассмотрим первые два слагаемых (3.14) и применим к ним правило II. Тогда к этим слагаемым добавится произведение т. е. после этого двукратное применение правила I вычеркнет первые два слагаемых, и мы получим

Применяя теперь правило II к первому и третьему слагаемым полученного выражения, добавим к нему произведение а затем, согласно правилу 1, вычеркнем последнее слагаемое Таким образом,

Еще раз применяем правило II ко второму и третьему слагаемым ( пользуемся затем правилом I и окончательно получаем представление

к которому правила I и II уже неприменимы. Таким образом, и мы получили импликанты

Теперь можно составить -матрицу по правилу (3.16). Первый импликант входит в первое и второе фундаментальные произведения, второй — в первое и четвертое, третий — в третье и четвертое. Тем самым

и наша задача о покрытии приобретает вид: минимизировать

при условиях

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

Из приведенного примера видно, что решение задач о покрытии часто облегчается учетом специфической структуры матрицы ограничений. Действительно, имеется ряд простых приемов сокращения матриц задач о покрытии; они основаны на идеях, близких к идеям доминирования стратегий в матричных играх. По этому поводу см., например, обзорную статью Балинского [50].

Отметим, что в логике и дискретном анализе описанной проблеме отвечает проблема минимизации дизъюнктивных нормальных форм.

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