суспільство, з необхідності задоволення насущних потреб, з умов виробничих і технологічних процесів. Математично обмеження виражаються у вигляді рівнянь і нерівностей. Їх сукупність утворює область допустимих рішень.
Т.ч., модель задачі математичного програмування прийме вигляд:
Знайти план х = (х 1 , х 2 , ..., х n ), який доставляє екстремальне значення цільової функції F (x) ? max (min), при обмеженнях g i (x)? (=,?) B i , i = .
З економічних або фізичних міркувань на план задачі або деякі його компоненти, як правило, накладаються умови невід'ємності, хj? 0, іноді - цілочисельності. p> План х, що задовольняє системі обмежень задачі, називають допустимим. Допустимий план, який доставляє цільової функції екстремальне значення, називають оптимальним. Оптимальний план позначають х *, екстремальне значення функції F (x *) = F *. p> Залежно від особливостей цільової функції F (x) і функцій обмежень gi (x), задачі математичного програмування діляться на ряд типів.
Задача лінійного програмування (ЗЛП) - завдання оптимізації лінійної функції при лінійних обмеженнях.
Задача нелінійного програмування (ЗНП) - завдання оптимізації нелінійної функції при обмеженнях або без них (коли або F (x) та/або g i (x) нелінійні).
Завдання дискретного (зокрема цілочисельного) програмування - Завдання оптимізації, в якій на змінні накладено додаткову вимогу приймати лише дискретні (зокрема цілочисельні) значення.
Задача динамічного програмування - задача оптимізації динамічних систем (тобто розвиваються з плином часу).
Завдання імовірнісного або стохастичного програмування - задача оптимізації, що містить випадкові величини.
Основні поняття теорії оптимізації
Кажуть, що функція F (x) має в т. х * (х 1 , х 2 , ..., х n ) локальний максимум (мінімум), якщо існує така околиця т. х *, в якій для будь-якого х виконується нерівність F (x)? F (x *) (F (x)? F (x *)).
Необхідна умова екстремуму: щоб F (x) мала в т. х * екстремум необхідно, щоб? F (x *) /? xj = 0,.
Достатня умова екстремуму: якщо F (x) в т. х * має? F (x *) /? xj = 0,, то щоб у цій точці F (x) мала екстремум досить , щоб квадратична форма
була позитивно (мінімум) або негативно (максимум) визначена.
Очевидно, що точки локального екстремуму можуть не давати найбільшого або найменшого значень функції в деякій області, крім того, їх може бути декілька. Велике значення в цьому зв'язку набуває поняття опуклості безлічі допустимих значень і опуклості (угнутості) функції. p> Безліч S називається опуклим, якщо для будь-яких двох точок цієї множини воно містить і відрізок, що з'єднує ці точки:
Функція F (x), визначена на опуклій множині S, опукла, якщо її графік цілком лежить нижче (не вище) відрізка, що з'єднує будь-які дві точки графіка:
Функція F (x), визначена на опуклій множині S, увігнута, якщо її графік цілком лежить вище (не нижче) відрізка, що з'єднує будь-які дві точки графіка:
Теорема 1: перетин опуклих множин є опуклою множиною.
Теорема 2: сума опуклих функцій є опуклою функцією, сума увігнутих функцій - увігнутою функцією. p> Теорему 3 (основна властивість опуклих задач):
Всякий локальний оптимум є глобальним.
Теорема Вейєрштрасса:
Безперервна функція, визначена на Непорожнє замкнутому обмеженому безлічі, досягає максимуму (мінімуму) принаймні в одній точці цієї множини.
Зі сказаного можна визначити загальний принцип вирішення завдань оптимізації: максимум (мінімум) F (x) при х, що належать замкнутому допустимому безлічі, якщо воно існує, є або точкою екстремуму, або граничною точкою допустимої множини, або і тим і іншим одночасно .
При чисельних розрахунках часто необхідно використовувати ще два важливих поняття.
Вектор, який вказує напрямок найшвидшого зростання функції, називається градієнтом функції grad F (x) = (? F /? x 1 , ...,? F/ ? x n ). Протилежний йому вектор називають антіградіентом, він вказує напрямок найшвидшого убування функції.
Лінією рівня (або лінією рівного значення) функції F (x) називають геометричне місце точок, координати яких задоволь...
