Математическое моделирование линейных систем, разработка методов оценивания параметров математической модели - Математическое моделирование в научных исследованиях

Основным методом решения задач линейного программирования является симплекс-метод, основанный на итеративной процедуре.

В том случае, когда область ограничения задается одним линейным уравнением, задача не имеет решения для всех х > 0.

Квадратичное программирование. Представлению задач линейного программирования n-мерными плоскостями и гипервыпуклыми многоугольниками поставим в соответствие n-мерными векторами в n-мерной ортогональной системе координат:

- целевая функция n - мерный вектор

V = e1с1х1 + e2с2х2 + ...+ enспхп,

- ограничения n-мерные вектора

Е1а11х1 + е2а12х2 +...+ еп а1п xn = В1 ,

Е1а21х1 + е2а22х2 +...+ еп а2п xn = В2 ,

Е1ак1х1 + е2ак2х2 + ...+ епакпхп = Вк.

Здесь еi - единичные базисные вектора, для которых выполняются условия ортогональности ei ej = 0 , e2i = 1 , i, j = 1, 2, ...

Векторным представлениям построим в соответствие квадратичные формы как квадраты длин векторов для целевой функции

V2 = (e1с1х1 + e2с2х2 + ...+ enспхп )2 = с21х21 + с22х22 +...+ с2пх2п,

И ограничений в виде произведения единичного вектора и векторов ограничений

(е1 + е2 +...+ еп ) (е1а11х1 + е2а12х2 +...+ еп а1п xn ) =

= а11х 1 + а12х2 +...+ а1п x n = С1 ,

(е1 + е2 +...+ еп) (е1а21х1 + е2а22х2 +...+ еп а2п xn) =

= а21х1 + а22х2 +...+ а2п xn = С2 ,

(е1 + е2 + ...+ ел) (е1ак1х1 + е2ак2х2 + ...+ епакпхп) =

= ак1х1 + ак2х2 + ...+ акпхп = Ск.

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

На квадратичных формах целевой функции и линейных форм ограничений стандартная задача оптимизации ставится следующим образом:

- найти минимум целевой функции как минимальной длины вектор (минимальный квадратичный функционал)

Ф =V2 = с21х21 + с22х22 +...+ с2пх2п > min,

При ограничениях

А11х1 + а12х 2 +...+ а1п x n = С 1 ,

А21х1 + а22х2 +...+ а2п xn = С2 ,

Ак1х1 + ак2х2 + ...+ акпхп = Ск.

Здесь целевая функция Ф обладает непрерывными частными производными первого и второго порядка по своим аргументам.

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

Т = с21х21 + с22х22 +...+ с2пх2п + л1(а11х 1 + а12х 2 +...+ а1п xn -

С1) + л2(а21х1 + а22х2 +...+ а2п xn - С2) + лк(ак1х1 + ак2х2 + ...+

Акпхп - Сk).

Минимизация целевой функции обеспечивается условием ?2Ф/?х2 > 0.

Стационарное значение целевой функции Ф находится путем решения системы ( n + k ) уравнений, получаемых из условий

    ?Т / ?хi = 0 , i = 1, 2, ..., n, и ?Т / ?лj = 0 , j = 1, 2, ..., k, 2с21 х1 + ?аj1 лj = 0 , 2с22 x2 + ?aj2 лj = 0 , 2с2п xn + ?ajk лk + 0 ,

А11х1 + а12х2 +...+ а1п xn = С1,

А21х1 + а22х2 +...+ а2п xn = С2

Ак1х1 + ак2х2 + ...+ акпхп = Ск.

Размерность пространства решения задачи равна ( n + k ).

Система уравнений является линейной и замкнутой по числу неизвестных x и, поэтому ее решение находится по формуле Крамера

Xi = di / d,

Где d - определитель основной матрицы системы уравнений, di - определитель матрицы, получающейся из определителя основной матрицы путем замены i-того столбца столбцом из свободных членов.

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

Квадратичный функционал связан с линейным условием

V2 = F2 n.

В качестве иллюстрации представления предлагаемого метода оптимизации запишем решения линейной, плоской и 4-х мерной задач.

Линейная задача:

Найти минимальный квадратичный функционал

С21 х21 + с22 х2 2 > min,

При линейном ограничении

Х1 + х2 = С1 ,

Решение имеет вид

Х1 = с22 С1(с21 + с22) . х2 = с21 С1 / (с21 + с22) .

Плоская задача:

Найти минимальный квадратичный функционал

С21 х21 + с22 х2 2 + с23 х23 > min,

При линейном ограничении

Х1 + х2 + х3 = С1 ,

Решение имеет вид

Х1 = с22 с23 С1 / ( с21 с22 + с21 с23 + с22 с23) ,

Х2 = с21 с23 С1 / ( с21 с22 + с21 с23 + с22 с23) ,

Х3 = с21 с22 С1 / ( с21 с22 + с21 с23 + с22 с23) ,

4-х мерная задача:

Найти минимальный квадратичный функционал

С21 х21 + с22 х2 2 + с23 х23 + с24 х24 > min,

При линейном ограничении

Х1 + х2 + х3 + х4 = С1 ,

Решение имеет вид

Х1 = с22 с23 с24 С1 / ( с21 с22 с23 + с21 с23 с24 + с21 с22 с24 + с22 с23 с24) ,

Х2 = с21 с23 с24 С1 / ( с21 с22 с23 + с21 с23 с24 + с21 с22 с24 + с22 с23 с24) ,

Х3 = с21 с22 с24 С1 / ( с21 с22 с23 + с21 с23 с24 + с21 с22 с24 + с22 с23 с24) ,

Х4 = с21 с22 с23 С1 / ( с21 с22 с23 + с21 с23 с24 + с21 с22 с24 + с22 с23 с24) ,

Решения позволяют выстраивать оптимальную организацию

Общего лесозаготовительного процесса при наличии нескольких технологий, имеющих различную себестоимость единицы лесопродукции. В этом случае с - стоимость 1м3 лесопродукции для отдельной технологии, х - объем лесопродукции, производимой отдельной технологией, а С - общий объем заготовки леса.

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

Ti = xi / ni,

Здесь ni - производительность огдельной технологии в комплексе.

Задачи на максимум выстраиваются как двойственная минимуму

Н - Ф > mах,

Где Н - постоянная, и условием - ?2Ф/?х2 < 0.

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

В тоже время множество задач линейного программирования можно решать представленным методом квадратичного программирования.

Нелинейное программирование. Задача представлена нелинейными формами.

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

Пример. Процесс состоит из ступеней: n, n-1, n-2,.., 1. Преобразование и доход определяются функциями T(x, D) и P(x, D) соответственно (x - переменная состояния, D - управляющая переменная)

Целевая функция fn(x) и управление Dn на n-й ступени удовлетворяют функциональному уравнению

Fn(x) = ext (Dn) {fn-1[T(x, Dn)] + Pn(x, Dn)},

Принцип максимума. (принцип быстродействия) Состояние процесса задается числами х1, х2, ...,хп, называемыми координатами фазового пространства процесса, движение объекта управляется параметрами u1, u2,..., ur; координаты фазового пространства и управляющие переменные зависят от времени, управляемый процесс описывается системой дифференциальных уравнений

Dxi/dt = fi (x1,..., xn, u1, ..., ur) , i = 1, 2, .., n.

Или в векторной форме

Dx/dt = f [x(t), u(t)] ,

Интегральный функционал

J = ?f(x1, x2,.., xn, u1, u2,...,ur)dt,

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

Похожие статьи




Математическое моделирование линейных систем, разработка методов оценивания параметров математической модели - Математическое моделирование в научных исследованиях

Предыдущая | Следующая