3.1.3. Линейное программирование

Для решения задачи проектирования фильтров, описанной в предыдущем разделе, можно применить метод оптимизации, известный как линейное программирование [19, 20]. Наиболее общая задача линейного программирования формулируется следующим образом:

если

где число ограничений в виде неравенства, -число ограничений в виде равенства, число нормальных случайных переменных, число свободных (не имеющих ограничений)

переменных. Целевая функция состоит из постоянной стоимости и линейной функции переменных. Векторы транспонированные соответственно) в совокупности называют вектором стоимости, векторы вектором ограничений, векторы вектором программы; совокупность матриц называют матрицей коэффициентов [20].

Указанная задача линейного программирования называется основной. С каждой основной задачей связана еще одна задача линейного программирования, называемая двойственной, которая может быть сформулирована следующим образом:

если

В двойственной задаче имеется по одной нормальной случайной переменной для каждого ограничения в виде неравенства основной задачи, по одной свободной переменной для каждого ограничения в виде равенства, по одному ограничению в виде неравенства для каждой нормальной случайной переменной и по одному ограничению в виде равенства для каждой свободной переменной [20].

Между основной и двойственной задачами могут существовать самые различные соответствия [20]. Для обсуждаемой проблемы важное значение имеют соответствия двух типов. Во-первых, легко показать, что задача, двойственная по отношению к двойственной задаче, есть основная задача. Во-вторых, можно показать, что если основная (двойственная) задача имеет оптимальное решение, то двойственная (основная) задача также имеет оптимальное решение, причем

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

Задачи линейного программирования решают с помощью алгоритма, называемого симплексным [19, 20]. Большая часть подробного описания этого алгоритма в данном контексте не представляет интереса. Следует только отметить, что алгоритм

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

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

где — искомая частотная характеристика, а изменяются в пределах некоторого подмножества области Иногда желательно получить наилучшую аппроксимацию на бесконечном числе точек Чтобы можно было решать такие задачи с помощью линейного программирования, необходимо выделить из бесконечномерного множества некоторое конечномерное подмножество. Процесс выделения конечномерного подмножества называется отбором, а вносимые при этом ошибки называются ошибками отбора. Можно показать [6], что эти ошибки уменьшаются по мере повышения плотности конечномерного подмножества в бесконечномерном множестве. Влияние эффекта отбора при решении задачи проектирования фильтров рассматривается ниже в п. 3.2.5.

Предположим, что отобрано некоторое конечномерное множество точек и что выражается с помощью (3.5). Тогда задачу проектирования фильтра можно сформулировать

как основную задачу линейного программирования следующего вида [см. (3.9)]:

если

где

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

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

если

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

(кликните для просмотра скана)

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

Автор пользовался комплексом программ для линейного программирования фирмы ИБМ, имеющим название «Система математического программирования 360» (регистрационный номер причем применялась ЦВМ типа . В этой системе используется переработанный симплексный алгоритм, причем пользователь может дополнять систему своими собственными программами на ФОРТРАНе. Ряд возможностей системы, основанных на использовании структурных особенностей ЦВМ «Система/360», позволяют быстро находить точные решения задач линейного программирования.