о евклідового простору називають опуклим, якщо разом з будь-якими двома точками x (1) і x (2) йому належить і сполучає їх відрізок.
Функцію? (x), визначену на опуклому безлічі X, називають опуклою, якщо для будь-яких x (1), x (2) і всіх?, що змінюються від 0 до 1, виконується нерівність
Вкажемо декілька властивостей оптимальних рішень, які належить знайти.
). Якщо випуклі функція? (X) і безліч X, то будь-яка точка x0, що належить X, що є точкою локального мінімуму, буде оптимальною точкою для задачі оптимізації функції? (X) на множині X (точкою глобального мінімуму).
). Якщо випуклі функція? (X) і безліч X, то безліч оптимальних точок опукло.
). Якщо? (X) строго опукла на опуклому безлічі X і точка x0 належить X оптимальна, т.е.
то для всіх x, що належать X і нерівних x0 буде? (x) gt; ? (x0) і, значить, точка x0 єдина.
Завданням лінійного програмування називається задача знаходження мінімуму лінійної функції від змінних, підлеглим лінійним обмеженням. Традиційно виділяють умови невід'ємності змінних, які часто зустрічаються в задачах економічного характеру і для дотримання яких стандартні алгоритми лінійного програмування спеціальним чином підготовлені.
У кінцевому рахунку, кожна задача лінійного програмування може бути приведена до наступного вигляду:
Основна задача лінійного програмування
Нехай задані дві кінцевих безлічі M і N, вектори b [M] та c [N], матриця A [M, N]. Нехай задані також розбиття M=M1 + M2 і N=N1 + N2. Потрібно знайти вектор x [N], що задовольняє умовам
X [N1]? 0 [N1],
a [M1, N]? x [N]? b [M1], [M2, N]? x [N]=b [M2] [N]? x [N].
Випадок, коли M=M2 і N=N1, нас буде цікавити особливо. Таке завдання буде називатися стандартної задачею лінійного програмування.
Динамічне програмування розглядає рух систем і його оптимізацію. Система в динамічному програмуванні представляється аналітично як вектор стану x, вектор управління u і заданий правило перетворення T вектора стану x в процесі руху.
Нехай вектор стану в вихідний момент x (0). Застосувавши деякий управління u (0), по x (0) і u (0) за допомогою заданого перетворення T (припустимо воно дано у вигляді функції) можна отримати вектор x (1)=T (x (0), u (0) ). Обравши деякий вектор управління u (1), по x (1) і u (1) можна підрахувати вектор x (2)=T (x (1), u (1))=T [T (x (0), u (0)), u (1)] і т.д. Таким чином, можна отримати для прийнятих x (0) і управлінь u (0, u (1), ..., u (n), ... дискретне безліч векторів x (1), x (2), ..., x (n),..., яке називають багатокроковим процесом. Якщо число кроків обмежена, то процес називають N-кроковим. Вектори управління u вибирають з безлічі допустимих управлінь Wu, обумовленого деякими обмеженнями. Вектор стану x також має свої обмеження і x? Wx. Отже, задовольняючи обмеженням u ? Wu і x? Wx, можна вказати деякий N-кроковий процес
Динамічне програмування припускає, що перетворення T володіє одиничністю, тобто обрання деякого x (0) і конкретних управлінь u (0), u (1), ..., u (N - 1) визначає єдиним чином N-кроковий процес - послідовність векторів x (0), x (1), x (2 ), ..., x (n), ..., x (N), підрахованих по вище приведених формулах. Одним з головних положень, на якому ґрунтується динамічне програмування і яке випливає з єдиності перетворення T, є незалежність подальшого руху від предистории, наприклад, рух системи, починаючи з вектора стану x (n) до вектора x (N), не залежить від історії, яка призвела систему в стан, що характеризується вектором x (n - 1).
Основи теорії оптимального управління. Нехай функціонування об'єктів в часі описується системою диференціальних рівнянь
де шукані функції xi=xi (t) характеризують стан об'єкта в кожен момент часу t;
fi - задані функції зазначених аргументів;
u1=u1 (t), ..., ur=ur (t) - функції, звані управлінням.
Прийнято функціонування або роботу об'єкта відповідно до диференціальнимирівняннями називати рухом системи, незважаючи на те, що вони можуть описувати і немаханічне рух. Якщо рівняння лінійні, то говорять про рух лінійних систем.
Вважають, що розглядається рух деякої системи на відрізку часу t ?? t? t? при заданих початкових умовах
.
У векторній формі рівняння і початкові умови можуть бути записані у вигляді
Рівняння і початкові умови - це математична модель реально існуючого руху. У зв'язку з цим будемо вимагати, щоб вибір управління u=u (t) здійснювався з таких міркувань, щоб підстановка його в систему робила її вирішуваною, причому єдиним чином, за допомогою початкових умов. Вектор функцію u=u (t) називають можливим управлінням, якщо підстановка u=u (t) в диференціальне рівняння руху робить його на відрізку часу t ?? t? T? вирішуваним, причому єдиним чином, за допомогою початкової умови Можливими управління...
