8.4. Теоретичні властивості оптимального рішення

У цьому розділі приводиться трохи тісно пов’язаних між собою формулювань умов, що як необхідні, так і достатні для того, щоб точка була оптимальним рішенням. Такі результати корисні принаймні в трьох відношеннях, оскільки ці умови:

1) дозволяють розробити чисельні методи перевірки оптимальності пропонованого рішення;

2) подають інформацію про чутливість рішення;

3) приводять до алгоритмічних методів знаходження оптимального рішення.

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

У попередньому розділі було відзначено, що існування напрямків поліпшення в точці x^k, що перевіряється, можна встановити, вирішуючи наступну задачу лінійного програмування:

Максимізувати х₀ (8.21)

при умові

(8.22)

де М = т+ п. (8.23)

На знаки х₀ та всіх d_j обмежень не накладається. (8.24)

Для досягнення поставлених тут цілей немає необхідності додатково вводити умови регуляризації для кожного d_j, тому такі обмеження, як (8.25) у модель не включаються:

(8.25)

де b – довільно обрана позитивна константа (наприклад, 1).

Точка x^k є дійсним оптимумом у тому й тільки тому випадку, коли оптимальне значення х₀ у задачі (8.21) – (8.24) дорівнює нулю.

Тепер припустимо, що – оптимальна точка, і нехай у (8.22) та (8.23) , так що х₀ = 0 є оптимумом для задачі (8.21) – (8.24).

Розглянемо відповідну двоїсту задачу лінійного програмування:

Мінімізувати (8.26)

при умовах (8.27)

(8.28)

(8.29)

Теорема подвійності забезпечує існування оптимальних значень , а також рівність нулю оптимального значення виразу (8.26), за умови що – оптимальна точка. Отже, після перестановки і спрощення членів (8.28) можна зробити наступне твердження.

Умови оптимальності. Якщо для та справедлива характеристика системи обмежень і допущення I) — VI), приведені вище, точка х є оптимальною в тому й тільки тому випадку, коли

(8.30)

де М = т+ п, а також існують такі що

(8.31)

(8.32)

де та задовольняють умовам (8.26) – (8.29). Обмеження (8.31) виражають умови додаткової нежорсткості.

Співвідношення (8.31) – (8.32) часто називають умовами Куна —Такера, за іменами математиків, які довели їхню справедливість.

Нерівності (8.30) включають умови незаперечності кожної з перемінних, отже, ці нерівності попросту означають, що точка х повинна бути допустимою. Легко показати, що обмеження (8.31) можна одержати розподілом вираження (8.26) на > 0, зауважуючи при цьому, що результуюча сума в точці оптимуму як і раніше дорівнює нулю; остання означає, що нулю дорівнює кожен член суми окремо, оскільки всі та . Нарешті, неважко перевірити, що обмеження (8.32) можна одержати, розділивши (8.28) на . Отже, умови оптимальності можна вивести виходячи з того, що задача лінійного програмування (8.21) – (8.24) застосовна для перевірки оптимальності точки х. Якщо приймемо для , a для , то можна показати, що з (8.31) та (8.32) походить

(8.33)

(8.34)

(8.35)

Помітимо, що в (8.33) при дорівнює нулю ; при в (8.34) дорівнює 0 відповідний вираз в (8.35).

Умови (8.30), (8.31) та (8.32) залишаються достатніми для оптимальності рішення х й за трохи більш слабких допущень щодо виду і . Говорячи менш строго, функції A_і(х) повинні бути такими, щоб обумовлена ними область допустимих рішень була опуклою; при одночасному урахуванні виду це дозволяє зробити висновок, що локальний оптимум одночасно є і глобальним оптимумом.

Замість того, щоб виключати у₀, можна сформулювати умови оптимальності (8.31) – (8.32) у такий спосіб: існують , причому не всі дорівнюють нулю, так що

(І)

(ІІ)

[Співвідношення (I) і (II) іноді називають умовами Джона]. Та обставина, що не всі дорівнюють нулю, є наслідком з (8.27). Це формулювання дуже важливе, оскільки при дуже загальних допущеннях умови (8.30), (I) і (II) необхідні для того, щоб оптимальному рішенню відповідала точка . Єдине необхідне допущення полягає в тому, щоб усі функції та мали безперервні перші часткові похідні для всіх значень ; при виконанні цього вони можуть мати будь-який вигляд. Щоб при настільки слабких обмеженнях умови (8.30), (8.31) та (8.32) залишалися також і необхідними, варто ввести якесь додаткове допущення, наприклад таке, що забезпечило б виконання нерівності .

Умови оптимальності корисні у всіх трьох відношеннях, зазначених на початку цього розділу. Далі буде показано, як їх можна використовувати для перевірки оптимальності або знаходження оптимального рішення задачі невеликої розмірності. Потім демонструється важливість цих умов для перевірки стійкості, а також для розробки алгоритмів рішення задач великої розмірності.

Функція Лагранжа та її сідлова точка. Необхідні та достатні умови оптимальності рішення , що перевіряється, можуть бути також сформульовані за допомогою так називаної функції Лагранжа. Нехай

(8.36)

Кажуть, що функція Лагранжа має сідлову точку, що відповідає парі векторів та , де кожне значення , якщо (8.37)

при будь-яких та ненегативних .

У цьому контексті перемінні іменуються множниками Лагранжа. Говорячи не строго, значення функції зменшується в міру віддалення х від , а значення функції зростає в міру віддалення и від .

Можна показати, що пари та , що задовольняють умовам оптимальності (8.30), (8.31) та (8.32), є також сідловою точкою , і навпаки. Отже, використовуючи підхід Лагранжа, можна сформулювати наступні умови.

Умови оптимальності Лагранжа. Якщо для функцій та виконуються умови, обумовлені характеристикою системи обмежень, то крапка буде оптимальна в тому й тільки тому випадку, якщо існує точка , така, що пари є сідловою точкою функції . При цьому для сідлової точки сума в правій частині (8.36) дорівнює нулю. [Цікаво відзначити, що достатня умова оптимальності у тому випадку, коли пара є сідлова точка, зберігає свою силу і тоді, коли ми відмовимося від усіх зроблених допущень щодо вигляду та гладкості функцій та ].

Помітимо, що функція Лагранжа увігнута по х при та лінійна відносно и. Зв’язок між раніше висловленими розуміннями й умовами оптимальності Лагранжа можна установити у такий спосіб. Відповідно до (8.35) у сідловій точці перші часткові похідні функції по кожному з x_j повинні бути непозитивними. Далі, відповідно до (8.34) або , або перша часткова похідна по x_j (або обидві ці величини одночасно) повинна дорівнювати нулю, тому що в супротивному випадку значення можна збільшити, змінюючи . Аналогічно цьому, відповідно до (8.30) перша часткова похідна по кожному u_і повинна бути ненегативною. При цьому відповідно до (8.33) або , або перша часткова похідна по u_і (або обидві ці величини одночасно) повинна дорівнювати нулю.

Оскільки в сідловій точці дорівнює оптимальному значенню , чутливість останнього до змін параметрів можна установити, обчислюючи вплив цих змін на .

Так, наприклад, якщо обмеження i замінити на , де е – дуже мале позитивне число, те оптимальне значення зросте приблизно на (за винятком тих випадків, коли при нескінченно малих значеннях е величини та не є безперервними функціями е).

Функцію Лагранжа можна також використовувати для безпосереднього знаходження оптимального рішення. Існує багато методів виконання цього; два з них коротенько описані нижче.

Нехай модель включає тільки одне нелінійне обмеження, наприклад , а всі інші обмеження лінійні. Замінимо цільову функцію задачі на та виключимо із системи обмежень. Почавши з и = 0, вирішимо модель, що тепер має нелінійну цільову функцію й тільки лінійні обмеження; для такої задачі застосовні методи, викладені раніше. Якщо при и = 0 одержуємо рішення, в якому , то це рішення оптимальне. У супротивному випадку будемо збільшувати значення и доти, поки не почне виконуватися умова . При цьому ми, власне кажучи, знаходимо сідлову точку функції Лагранжа (8.36), і відповідне рішення є оптимальним.

Такий же підхід застосуємо і до рішення деяких задач динамічного програмування, як, наприклад, до задачі розподілу ресурсів. Наприклад, задачу з двома обмеженнями можна звести до задачі з одним обмеженням. Відповідно для рішення модифікованої задачі може бути використано рекурентне співвідношення динамічного програмування для одної перемінної стану. Однак, якщо значення керуючих перемінних повинні бути цілочисельними, то остаточне рішення, знайдене за допомогою зазначеного підходу, може виявитися не більш ніж наближеним рішенням вихідної задачі.

Іншим обчислювальним застосуванням функції Лагранжа є так називані малокрокові градієнтні алгоритми. При використанні таких методів будується система диференціальних рівнянь, заснованих на перших часткових похідних функції Лагранжа по кожному з х_j та u_і. При визначених допущеннях траєкторії перемінними, обумовленими диференціальними рівняннями, сходяться до оптимального рішення.

двоїстість. Використовуючи функцію Лагранжа (8.36), можна сформулювати наступну оптимізаційну задачу, що називається двоїстою: знайти х та и, и > 0, такі, що

Мінімізується (8.38)

при умовах

(8.39)

Можна довести наступну теорему.

Теорема двоїстості нелінійного програмування. Нехай для функцій та є справедливими умови, обумовлені характеристикою системи обмежень і допущеннями І) – VI), приведеними вище. Тоді:

I) Якщо – оптимальне рішення задачі нелінійного програмування, то існує така, що пари та є рішенням двоїстої задачі (8.38) – (8.39). Далі, якщо х є припустимим при урахуванні умов вихідної задачі, а х та и – допустимими при урахуванні умов двоїстої задачі, то ; рівність дотримується для оптимальної пари та .

II) Навпаки, якщо пари та є рішенням двоїстої задачі (8.38) – (8.39), причому для кожного i, а також якщо строго увігнута, або існує таке k_, що A_k(х) строго опукла та , то є рішенням вихідної задачі нелінійного програмування. При цьому .