Двойственная функция этой задачи имеет вид

Условие нормализации представляется уравнением

а условия ортогональности – системой:

Эти условия образуют систему, состоящую из четырех линейных уравнений с четырьмя неизвестными, и имеют единственное решение ( ):

Значение двойственной функции в точке δ* таково:

Так как δ* является единственной точкой области определения υ(δ), из теоремы двойственности мы заключаем, что минимум функции

Следует обратить внимание на то, что условный минимум функции f(x) был определен до нахождения минимизирующего вектора ( ). Исходя из смысла двойственной переменной как весового коэффициента позинома, можно записать для ЦФ и ,

для ограничений и .

Чтобы определить значения , прологарифмируем обе части представленных выше соотношений. Мы получим, что значения удовлетворяют системе:

которая линейна относительно переменных lnx₁, lnx₂ иlnx₃. Она имеет единственное решение (-ln2, 0, 0), а это означает, что f(x) достигает условного минимума в точке (1/2, 1, 1).

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

Если степень трудности равна нулю, то максимизирующий вектор δ* не зависит от коэффициентов позинома. Требование ортогональности, например, трехкомпонентного вектора δ двум векторам–столбцам матрицы показателей полностью определяет вектор на некотором двумерном подпространстве трехмерного пространства. Поэтому условие ортогональности может быть сформулировано следующим образом: вектор решения должен быть ортогонален пространству показателей. Любой нормализованный вектор, ортогональный пространству показателей, называется двойственным вектором. Для его построения используется метод Бранда, который может быть использован к любой матрице показателей.

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

В предыдущей задаче размерность вектора показателей п была ровно на единицу больше размерности пространства показателей m, в результате чего условие ортогональности однозначно определяло двойственный вектор без проведения операции нормализации. Однако в общем случае n > m + 1, и поэтому условие ортогональности определяет лишь двойственное пространство. Размерность этого пространства равна n - m. Очевидно, что произвольный n-мерный вектор v может быть записан как v=e+δ,

где е—вектор показателей; δ - двойственный вектор.

С целью записи общего выражения для вектора δ, лежащего на гиперплоскости нормализации, вводится понятие вектора невязки. Вектор невязки δ^(s) определяется как вектор, удовлетворяющий условию нормализации вида:

.

Затем выбирается произвольный вектор δ, удовлетворяющий данному условию, например b⁽⁰⁾. Тогда общее выражение для вектора δ, лежащего на гиперплоскости нормализации, будет иметь вид

.

Здесь d на единицу меньше размерности двойственного подпространства, а именно d=n-(m+1). Ранее величина d была названа степенью трудности задачи. Коэффициенты r_s, общее число которых равно d, называются базисными переменными.

Рис. 2.3. Графическая иллюстрация вектора нормализации и невязки

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

Для демонстрации использования векторов нормализации и невязки рассмотрим задачу минимизации, представленную выражением:

,

при условии .

Ниже для рассматриваемой задачи приведена матрица для пространства показателей и ее двойственное пространство:

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

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

Задача 2.Пусть нужно минимизировать позином

при

Соответствующая этой задаче двойственная задача состоит в максимизации двойственной функции:

при двойственных ограничениях:

δ₁≥0, δ₂≥0, δ₃≥0, δ₄≥0, δ₅≥0 - условие неотрицательности,

δ₁ + δ₂ + δ₃ = 1 - условие нормализации,

-δ₁ + δ₂ + δ₃ - 2δ₄ = 0,

-1/2δ₁ + δ₃ - 2δ₄ + 1/2δ₅ = 0, - условие ортогональности.

-δ₁ + δ₂ + δ₃ - δ₅ = 0.

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

(2.24)

Результирующая матрица «диагонального типа» может быть записана в более удобной форме:

(2.25)

в которой третью и пятую строки матрицы (2.24) необходимо было поменять местами, чтобы получить единичную (3 x 3) матрицу в верхней части преобразуемой матрицы. Далее, берут с обратным знаком матрицу, транспонированную к матрице, лежащей ниже единичной (3 x 3) матрицы, и дописывают к ней снизу единичную (2 x 2) матрицу, в результате получается:

. (2.26)

Из построения ясно, что любой вектор-столбец этой матрицы ортогонален ко всем векторам–столбцам матрицы (2.25). Однако нумерация компонент этих векторов–столбцов не соответствует нумерации в матрице (2.24), так как при переходе от (2.24) к (2.25) третья и пятая строки поменялись местами. Поэтому, меняя местами третью и пятую строки матриц (2.25) и (2.26), получают соответственно следующие матрицы:

(2.27) и . (2.28)

Векторы–столбцы матрицы (2.28) по построению ортогональны к векторамстолбцам матрицы (2.27). Так как матрицы (2.27) и (2.24) одинаковы, а (2.24) получена из матрицы экспонент при помощи элементарных операций над столбцами, можно заключить, что векторы–столбцы матрицы (2.28) ортогональны векторам–столбцам матрицы экспонент. Кроме того, векторы–столбцы матрицы (2.28) линейно независимы, они образуют базис пространства решений условий ортогональности, т. е. базис двойственного пространства.

Разделив первый вектор-столбец матрицы (2.28) на сумму первых трех его компонент, можно получить вектор

(2.29)

который удовлетворяет как условию ортогональности, так и условию нормализации. Таким образом, b⁽⁰⁾ является вектором нормализации для задачи 2.

Так как матрица (2.28) имеет только два столбца, то для задачи существует лишь один вектор невязки b⁽¹⁾. Чтобы получить его, необходимо вычесть из оставшегося вектора–столбца матрицы (2.28) произведение суммы первых трех его компонент на вектор нормализации b⁽⁰⁾. В результате получается вектор

(2.30)

Общее решение условий нормализации и ортогональности имеет вид

или

(2.31)

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

Из полученных уравнений ясно, что δ удовлетворяет условиям неотрицательности только при таких значениях r:

. (2.32)

Подставляя в соотношения (2.30) значения r, равные, например, 1/4, 3/10 и 7/20, и вычисляя соответствующие значения двойственной функции, можно получить

(2.33)

Вычисляя f(x) для пробных значений x₁, x₂, x₃, которые удовлетворяют ограничениям прямой программы, получим

(2.34)

Из соотношения двойственности можно записать

,

где x* - минимизирующий вектор задачи 2, a x и δ - произвольные векторы, удовлетворяющие соответственно ограничениям прямой задачи и двойственным ограничениям.

Следовательно, (2.33) дает оценки снизу для значения f(x*), тогда как (2.34) дает оценки сверху. В частности,

.

Следовательно, можно считать, что условный минимум ЦФ равен 100 с погрешностью, не превышающей 4 %.