Материал: Учебное пособие Немирко Манило

Прямая и двойственная задачи так тесно взаимосвязаны, что оптимальное решение одной задачи можно получить из решения другой. Это обстоятельство обусловливает возможность проведения вычислений именно по той задаче (прямой или двойственной), которая требует меньших вычислительных затрат. Например, если прямая задача имеет 100 переменных и 500 ограничений, то предпочтительнее нахождение оптимального решения двойственной задачи, поскольку трудоемкость вычислений в большей степени зависит от числа ограничений, чем от числа переменных.

Возвращаясь к проблеме решения задачи (1.33), рассмотрим следующую частную задачу линейного программирования, записав ее в виде

или в матричной записи:

max c, x ;

Ax ≤ b,

где целевая функция представлена в виде скалярного произведения c, x

двух векторов x = (x1, x2, , xn ), c = (c1,c2, ,cn ) , а вектор ограничений – в виде матрицы-столбца b = (b1, b2, , bm ). Здесь, как и в (1.33), на коорди-

наты вектора x не накладывается никаких дополнительных условий. Двойственной к (1.38) будет задача линейного программирования от

m переменных y1, y2, , ym вида

где yi ≥ 0 (i =1,m), или в матричной записи:

31

min b, y ;

Aтy = c; y ≥ 0,

где y = (y1, y2, , ym ).

Как видно из (1.39), переменных столько же, сколько строк в матрице A задачи (1.38). Матрица ограничений в (1.39) – транспонированная матрица A . Вектором правой части ограничений в (1.39) служит вектор коэффициентов максимизируемой линейной функции (1.38), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (1.39) выступает линейная форма, коэффициенты которой задаются вектором правой части ограничений задачи (1.38). При этом символ max меняется

на min . На двойственные переменные yi , i =1, m накладывается условие неотрицательности.

В соответствии со второй теоремой двойственности (теоремой равновесия) оптимальный план x* = (x1*, x2*, , xn* ) прямой задачи (1.38) однозначно

связан с решением двойственной задачи (1.39) y* = (y1*, y2*, , ym* ). Суще-

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

Таким образом, если в прямой задаче (1.38) число ограничений m значительно превосходит число переменных n , целесообразно вначале решить двойственную задачу (1.39), представленную в канонической форме, а затем, перейти к составлению системы уравнений и ее решению относительно неизвестных x* = (x1*, x2*, , xn* ).

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

32

решений сопряженных задач, ориентированный на практическое применение, подробно рассмотрен в [13].

Итак, сформулированную задачу отыскания разделяющей гиперплоскости (1.33) можно решить на основе двойственной задачи. Условия ограничения в (1.33) можно привести к виду

ные значения которых входят в уравнения двух параллельных гиперплоскостей. Число ограничений определено количеством объектов, образующих классы LA и LB . Оно задает и число неизвестных x j , j L ( j LA, j LB)

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

Следуя правилам построения сопряженных задач (1.38) и (1.39), ее можно представить следующим образом. Найти

b = (0, 0, ,0,1,1). m

Линейные ограничения (1.43), заданные в матричной форме, можно записать в виде системы уравнений-ограничений

∑ −p1 j x j + ∑ p1 j x j = 0;

j LA j LB

∑ −p2 j x j + ∑ p2 j x j = 0 ;

j LA j LB

33

……………………………….

∑ −pmj x j + ∑ pmj x j = 0;

где все x j ≥ 0.

В данной задаче, имеющей каноническую форму, имеется лишь m +2 ограничения, что значительно упрощает ее решение. Это связано с тем, что число объектов, как правило, значительно превышает размерность пространства признаков, в котором строится разделяющая гиперплоскость. Если общее число объектов равно n , то число свободных переменных x j будет рав-

но n −(m +2). Выразив m базисных переменных через выбранные свобод-

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

множество оптимальных значений (x*j , j L), из которых лишь m +2 переменных будут иметь ненулевые значения. Если найденный оптимальный план этой задачи представить в виде (x1*, x2*, , xm* +2, 0, 0, , 0), то лишь для первых m +2 переменных будет составлена система уравнений-ограни- чений прямой задачи следующего вида:

−(λ1 p1 j +λ2 p2 j + +λm pmj )+λ′= −1,

если j LA;

λ1 p1 j +λ2 p2 j + +λm pmj +λ′=1,

если j LB.

Как следует из (1.40), форму равенства приобретают только те неравенства из ограничений (1.41), (1.42), в которых индексы j однозначно связаны

с ненулевыми значениями (x1*, x2*, , xm* +2 ). Решение этой системы уравнений позволяет найти оптимальные значения переменных

(λ1, λ2, , λm , λ′, λ′)* .

34

При наличии значительного числа признаков m для решения этой задачи целесообразно применить итерационный симплекс-метод, что позволяет одновременно находить решение и прямой задачи [13].

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

2.УПРАВЛЕНИЕ СОСТОЯНИЕМ ОРГАНИЗМА

ВБИОТЕХНИЧЕСКИХ СИСТЕМАХ

НА ОСНОВЕ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1. Метод динамического программирования

Рассмотрим управляемый процесс, который переводит некоторую систему G из начального состояния S0 в конечное состояние Sm . При наличии

промежуточных состояний такой перевод представляется в виде траектории, состоящей из конкретной последовательности промежуточных состояний (рис. 2.1). Если промежуточные состояния могут быть различными, то траектория перевода G из S0 в Sm неоднозначна и зависит от вырабатываемых управляющих воздействий x .

ции в процессе оптимизации ее стремятся либо максимизировать, либо ми-

управления x *, при котором целевая функция W достигает своего минимального значения W *, т. е.

W* = min{W (x)}.

x

35