Материалы по курсу (часть 2)

9. Отыскание оптимального решения основной задачи линейного программирования на основе табличного алгоритма замены переменных.

В задаче линейного программирования (ЛП) кроме уравнений-ограничений

∑ = ; = ̅̅̅̅̅̅1, ; = ̅̅̅̅̅1,

=1

существует ещё и линейная функция

= 0 + 1 1 + + + + = 0 − ( 1 1 + + + + ),

которую нужно минимизировать.

Для нахождения опорного решения, обращающего в минимум линейную функцию,

удобно воспользоваться табличным алгоритмом замены ↔ .

Для нахождения оптимального решения симплекс-методом необходимо чтобы оно удовлетворяла правилам:

1.Если все свободные члены (не считая строки L) в симплекс таблице неотрицательны,

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

2.Если в строке L есть положительный элемент, а в столбце, соответствующем ему,

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

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

Рассмотрим пример:

Необходимо найти решение задачи ЛП с уравнениями:

1 = 2 − (1 ∙ 1 + 1 ∙ 2 − 2 ∙ 3);2 = 1 − (1 ∙ 1 − 1 ∙ 2 + 1 ∙ 3);3 = 5 − (1 ∙ 2 + 1 ∙ 3);4 = 2 − (1 ∙ 1 + 1 ∙ 2 − 2 ∙ 3);

обращающее в минимум линейную функцию = 0 − (− 1 + 2 ∙ 2 + 3).

Решение:

Т.к. все свободные члены неотрицательны, то опорное решение:

1 = 2 = 3 = 0; 1 = 4 = 2; 2 = 1; 3 = 5; = 0.

Это решение не оптимально, т.к. коэффициент при 2 и 3 положительны. Выберем 3,

его надо поменять.

Составим таблицу:

Сначала рассчитываем значения, находящиеся на строке и столбце, которые мы меняем, а затем остальные ячейки в формулы для которых подставляем изначальные значения коэффициентов. В полученной таблице на основных строке и столбце тёмно-серым выделены новые коэффициенты.

Т.к. в строке L есть положительные элементы, то оптимальное решение не достигнуто.

Следует произвести замену одной из свободных переменных на одну из базисных.

11 = 1 - для строки 2; 51 = 5 - для строки 2; По min выбираем 2.

Проводим аналогичные расчёты с заменой.

То же самое

Т.к. в строке L нет ни одного положительного элемента, то оптимальное решение

достигнуто.

Ответ: 1 = 3 = 1 = 0; 2 = 2 = 4; 3 = 1; 4 = 6; = −9.

10. Метод динамического программирования (ДП). Алгоритм решения задач управления состоянием организма в биотехнических системах. Основное рекуррентное уравнение ДП.

Метод динамического программирования (ДП)

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

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

В зависимости от содержания целевой функции в процессе оптимизации ее стремятся либо максимизировать, либо минимизировать.

Будем рассматривать оптимизацию, при которой W→min.

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

Представим себе процесс управления, состоящий из конечного числа последовательных шагов. В этом случае траектория перехода G из S0 в Sm будет иметь вид последовательности промежуточных состояний S0, S1, S2…Sm, которая является результатом пошагового управления x, также имеющего вид последовательности x0, x1, x2… xm (обычно не числа, а вектора, функции, какие-либо предписания и т.п.). Si обозначает состояние системы G, а xi - управление на i-м шаге для произвольной траектории. Для конкретной же траектории конкретное управление xi’ переводит в конкретное состояние Si'.

Пусть на каждом отдельном i-м шаге, заключающемся в переходе из Si-1 в Si, известно значение целевой функции W которое обозначается wi. Считая выбранный критерий аддитивным, т.е. полагая, что

задача оптимизации формулируется следующим образом:

Требуется найти такое оптимальное управление x* = x0*, x1*, x2*… xm* (xi*, где - оптимальное шаговое управление на i-м шаге), при котором целевая функция W принимает минимальное значение, т.е.

Последовательность оптимальный шаговых управлений x1*, x2*… xm* приводит к оптимальной траектории S0, S1, S2…Sm перевода G из S0 в Sm.

Рассмотрим пример, приведенный на рис.2.2.

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

Если W’ > W’’, то второй вариант является оптимальным, т.е. x* = x’’, W*= W’’

•Поиск оптимального управления x* методом динамического программирования основан на использовании принципа оптимальности:

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

После выбора способа описания состояний управляемой системы и разбиения всего процесса управления на шаги применяется следующая процедура:

1.Перечислить набор шаговых управлений xi для каждого шага и налагаемые на них ограничения.

2.Для каждого i-го шага определить значение wi в функции от состояния Si-1 на -м шаге и от шагового управления xi.

3.Определить, как изменяется состояние Si-1 системы G под влиянием управления xi на i-м

шаге: оно переходит в новое состояние

4.Пусть Wi (Si-1) - условный оптимум целевой функции, получаемый на всех последующих шагах, начиная с i-го и до конца. Надо записать основное рекуррентное уравнение динамического программирования, выражающее Wi (Si-1) через уже известную функцию Wi+1 (Si)

Этому условному оптимуму целевой функции Wi (Si-1) соответствует условное оптимальное управление на i-м шаге xi (Si-1), которое совместно с оптимальным управлением на всех последующих шагах обращает целевую функцию на всех оставшихся шагах, начиная с данного, в минимум.

5.Произвести условную оптимизацию последнего (m-го) шага, задаваясь множеством состояний Sm-1, из которых можно за один шаг дойти до конечного состояния,

вычисляя для каждого Sm-1 условный оптимум целевой функции по формуле

и находя условное оптимальное управление xm (Sm-1), для которого этот минимум достигается.

6.Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле:

полагая в ней i = (m-1), (m-2),… и для каждого из шагов указать условное оптимальное управление xi(Si-1),при котором достигается минимум.

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

Это и есть оптимум функции цели за весь процесс перевода:

W* = W1(S0)

7.Произвести безусловную оптимизацию управления, учитывая выработанные ранее рекомендации на каждом шаге. На первом шаге оптимальное шаговое управление x1*= x1(S0),. Пользуясь (2.1), находим изменившееся состояние системы S1, для него определяем оптимальное управление на втором шаге x2* и т.д. до конца.

11. Управление переходом организма из исходного в конечное состояние методом ДП: использование ориентированного графа.

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

W=W(x) – целевая функция, х – выбранное управление.

Введя какую-либо W=W(x), можно сравнивать (по величине W) траектории друг с другом и искать оптимальную, при которой достигается экстремум W. В зависимости от содержания целевой функции в процессе оптимизации ее стремятся либо максимизировать, либо минимизировать. Далее будет рассматриваться оптимизация, при которой W → min. Таким образом, задача заключается в отыскании оптимального управления x *, при котором целевая функция W достигает своего минимального значения W *, т. е. = min{ ( )}.

Представим себе процесс управления состоящим из конечного числа последовательных шагов. В этом случае траектория перехода G из S0 в Sm будет иметь вид последовательности промежуточных состояний S0, S1, S2, …, Sm, которая является результатом пошагового управления x, также имеющего вид последовательности =

Для конкретной же траектории конкретное управление xi' переводит G в конкретное состояние Si’. Нужно иметь в виду, что управления x1, x2, …, xm в общем случае не числа, а

векторы, функции, какие-либо предписания и т. п.

Пусть на каждом отдельном i-м шаге, заключающемся в переходе из Si-1 в Si, известно значение целевой функции W, которое обозначается wi. Считая выбранный критерий W

– оптимальное шаговое управление на i-м шаге), при котором целевая функция W

принимает минимальное значение, т.е.

= ∑=1 → .

Пример:

Поиск оптимального управления методом ДП основан на использовании принципа оптимальности: каково бы ни было состояние S системы G в рез-те какого-то числа шагов, мы должны выбирать управление на ближайшем шаге так, чтобы оно в совокупности с оптимальным управление на всех последующих шагах приводило к минимальному значению целевой функции на всех оставшихся шагах, включая данный.

1.Перечислить набор шаговых управлений xi для каждого шага и налагаемые на них ограничения.

2.Для каждого i-го шага определить значение wi в функции от состояния Si-1 на (i-1)-м шаге и от шагового управления xi

= ( −1, ).

3. Определить, как изменяется состояние Si-1 системы G под влиянием управления xi на (i-1)- м шаге: оно переходит в новое состояние

= ( −1, ).

4. Пусть Wi(Si-1) – условный оптимум целевой функции, получаемый на всех последующих шагах, начиная с i-го и до конца. Надо записать основное рекуррентное уравнение