Завдання опуклого програмування. опукле програмування

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

Найбільш загальна задача нелінійного програмування може бути сформульована таким чином:

потрібно визначити значення n змінних x 1, x 2, ..., x n, які задовольняють m рівнянь або нерівностей виду

i \u003d 1, 2, ..., m.

і звертають в максимум (або мінімум) функцію мети

f (X) \u003d f (x 1, x 2, ..., x n).(2.2)

Припустимо, що f і g i - нелінійні задані функції, b i - відомі константи. Зазвичай вважається, що всі або принаймні деякі змінні повинні бути невід'ємними.

В окремому випадку лінійного програмування передбачається, що функції f і g i є лінійними, т. Е.

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

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

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

де на функції f j (x j) повинні в свою чергу бути накладені деякі обмеження. Це так звана сепарабельном функція. В іншому випадку цільова функція може бути записана як сума лінійної і квадратичної функцій:

Нелінійні задачі такого типу називаються завданнями квадратичного програмування. Для того щоб знайти оптимальне рішення, на величини d ij необхідно накласти деякі додаткові обмеження.

Завдання з нелінійними обмеженнями більш важкі, ніж з лінійними. Щоб в цих завданнях отримати оптимальне рішення, до функцій g i і f повинні бути пред'явлені дуже жорсткі вимоги. Зокрема, оптимальне рішення нелінійної задачі може бути отримано в тому випадку, якщо обмеження g i, задані нелінійними нерівностями, визначають опукле безліч в просторі змінних (див. Гл. 1, § 3) і функція мети є нелінійної гладкою опуклою або увігнутою функцією. Надалі буде дано суворе визначення опуклої й увігнутої функцій. Тут же тільки необхідно вказати, що властивість опуклості функцій f забезпечує існування лише одного мінімуму, а властивість угнутості f - лише одного максимуму f всередині області, що задається обмеженнями. На цьому і будуються алгоритми визначення оптимального значення функції мети. При відсутності опуклості або угнутості рішення задачі математичного програмування наштовхується на наявність локальних мінімумів або максимумів, до відшукання яких в загальному випадку можна застосувати класичні методи.

Розгляд цього класу задач зазвичай починається з викладу методу невизначених множників Лагранжа. Для цього покладемо, що / (х ь ..., х ") і g (x b ..., х ") - безперервні функції разом зі своїми приватними похідними, знімемо поки умови невід'ємності змінних і сформулюємо наступну задачу на умовний екстремум:

Щоб знайти її рішення, введемо множники Лагранжа у ь / = 1, ті складемо так звану функцію Лагранжа:

знайдемо і прирівняємо до нуля її частинні похідні по всім змінним

отримавши систему п + т рівнянь щодо невідомих х ь х п,

Уї -, уп-

якщо функція f (x h ..., х ") в точці має екстремум, то існує такий вектор У (0\u003e \u003d (у, 0, ..., у °), Що точка (А г (0), F (0)) є рішенням системи (2.23). Отже, вирішуючи систему (2.23), ми отримаємо точки, в яких функція (2.20) може мати екстремум. Далі знайдені точки досліджують так само, як при вирішенні задачі на безумовний екстремум.

Таким чином, метод множників Лагранжа включає виконання наступних етапів.

• 1. Скласти функцію Лагранжа.
• 2. Знайти приватні похідні по Xj і у, від функції Лагранжа і прирівняти їх до нуля.
• 3. Вирішуючи систему (2.23), знайти точки, в яких цільова функція може мати екстремум.
• 4. Серед точок-претендентів на екстремум знайти такі, в яких екстремум досягається, і обчислити значення функції f (x, ..., х ")в цих точках.

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

Визначення 1.функція f (x,..., х п), задана на опуклій множині X, називається опуклою, якщо для будь-яких точок Х, Х 2 з Хі для будь-якого числа X, 0 X 1 виконується нерівність

Визначення 2.Функція / (*, х"), Задана на опуклій множині X, називається увігнутою, якщо для будь-яких точок Х х, Х 2 з Хі для будь-якого числа X, 0 X

Визначення 3.Безліч допустимих рішень задачі опуклого програмування задовольняє умові регулярності, якщо існує принаймні одна точка Xj, що належить області допустимих рішень, для якої g ^ XJ) \u003db h i = 1, т.

Теорема 1.Будь-який локальний екстремум завдання опуклого програмування є глобальним.

Визначення 4.Функцією Лагранжа завдання опуклого програмування є функція

де у, - множник Лагранжа.

Визначення 5.Крапка (Х (0), Т (0)) = (Х, °, ..., х ( ', у, 0,..., у " ) називається сідловою функції Лагранжа, якщо

Наведемо дві короткі теореми, що носять допоміжний характер.

Теорема 2.оптимальний план Х (0)завдання НП- це

де ДА) - нелінійна функція, що диференціюється, що задовольняє умовам

де - градієнт функції /

в точці А "(0).

Доведення.

Розкладемо цільову функцію в ряд Тейлора в околі точки Х (())

де АХ - вектор малих збільшень Х (0);

I - позначення норми (довжини) вектора.

З виразу (2.26) випливає, що якщо будь-яке значення координати вектора х | 0)\u003e 0, то обов'язково буде дорівнює нулю похідна

, Так як в противному випадку з координування х до можна, можливо,

при фіксованих значеннях інших змінних, продовжити мінімізацію цільової функції, зменшуючи значення х [0), якщо похідна більше нуля, або збільшуючи xf якщо похідна менше

нуля. Якщо ж х | 0) \u003d 0, то має бути оскільки

в іншому випадку можна було б зменшити значення f (X m), збільшивши 4 0) на величину Дх *, не змінюючи значень інших змінних. Отже, для будь-якого до виконується рівність:

Теорема доведена.

Визначимо тепер необхідні і достатні умови існування сідлової точки функції Лагранжа.

Теорема 3.Щоб точка (А 10 *, І 0)) з невід'ємними координатами була сідловою диференціюється L (X, Y),повинні виконуватися умови:

Доведення.

1) Необхідність. Нехай (Х (0), У "(0)) - сідлова точка, тобто .:

Формула (2.29) рівносильна виразу

На підставі (2.29) і (2.30) умови (2.27) і (2.28) виконані. Необхідність, таким чином, доведена.

• 2) Достатність. Покладемо, що виконані умови (2.27) і (2.28). розкладемо функцію L (X, Y) в ряд Тейлора в околі точки

З розкладання (2.31) і з урахуванням умов (2.27) і (2.28) випливає, що

Два останніх вирази рівносильні формулою (2.29). Теорема доведена.

Після наведених теорем сформулюємо практично очевидну тепер уже теорему Куна - Таккера.

Теорема 4 (Куна - Таккера).Для завдання опуклого програмування (2.20) - (2.21), безліч допустимих рішень якої має властивість регулярності, точка Х (0) \u003d (Xj 0 *, ..., х '0)), х, - 0\u003e\u003e 0, / \u003d 1, п є оптимальним планом тоді, і тільки тоді, коли існує такий вектор Т \u003d (у 1 (0), ..., yi 0)), У / 0)\u003e 0, / \u003d 1, т, що точка (Т (0), Н 0\u003e) є сідловою функції Лагранжа.

Якщо в задачі опуклого програмування (2.20) - (2.21) цільова функція і обмеження безперервно мають похідні, то теорему Куна - Таккера можна доповнити аналітичними виразами, що визначають необхідні і достатні умови того, щоб точка (Х (0), У i (l), ) була сідловою функції Лагранжа, тобто була рішенням завдання опуклого програмування. Це вираження (2.27) і (2.28). Їм задовольняє завдання квадратичного програмування. Для її остаточного формулювання наведемо кілька визначень і одну теорему.

Визначення 6.Квадратичною формою щодо змінних Х [..., х " називається числова функція цих змінних, що має вигляд:

Визначення 7.квадратична форма F називається позитив- але / негативно певної, якщо F (X)\u003e 0/ F (X) 0 для всіх значень змінних, складових вектор X.

Визначення 8.квадратична форма F називається позитив- але / негативно полуопределенной, якщо F (X ")\u003e О / ТАК ") X, і, крім того, існує такий набір змінних - компонент вектора X ", що F (X ") \u003d 0.

Теорема 5.Квадратична форма є опуклою / увігнутою функцією, якщо вона позитивно / негативно полуопределена.

визначення9. Завдання, що складається в мінімізації / максимізації значення функції

при обмеженнях

де - позитивно / негативно полуопределенная квадратична форма, називається завданням квадратичного програмування (ЗКП).

Для цього завдання функція Лагранжа має вигляд:

Якщо функція Лагранжа має седловую точку, то в ній виконуються умови (2.27), (2.28). Вводячи тепер додаткові змінні, що звертають нерівності в рівності (цей прийом використовується і при вирішенні задач ЛП), запишемо ці умови у вигляді:

Для знаходження рішення ЗКП треба визначити невід'ємне рішення системи лінійних алгебраїчних рівнянь (2.32). Таке рішення можна знайти методом штучного базису, застосованого для знаходження мінімального значення штучної цільової функції F \u003d ^ Pj, гдеру-штучні змінні. Метод, какіз-

відомо, за кінцеве число кроків знайде оптимальний план або встановить нерозв'язність завдання.

Отже, процес знаходження рішення ЗКП включає виконання наступних етапів.

• 1. Складають функцію Лагранжа.
• 2. У вигляді виразів (2.27), (2.28) записують необхідні і достатні умови існування сідлової точки функції Лагранжа.
• 3. Використовуючи метод штучного базису, встановлюють відсутність сідлової точки для функції Лагранжа або знаходять її координати.
• 4. Записують оптимальне рішення вихідної задачі і знаходять значення цільової функції.

Розглянемо елементарний числовий приклад (№ 1) з книги І. Л. Акулича «Математичне програмування в прикладах і завданнях». За планом виробництва продукції підприємство повинно виготовити 180 виробів. Вони можуть бути виготовлені за двома технологіями. при виробництві Х виробів 1-м способом витрати склали xf +4 х, руб., А при виготовленні х 2 виробів 2-м способом вони рівні х + 8х 2 руб. Визначити, скільки виробів кожним способом слід виготовити для мінімізації вартості замовлення.

Рішення. Мінімізувати слід наступну функцію:

за умов:

Функція Лагранжа в цьому випадку буде виглядати наступним чином:

Обчислимо приватні похідні цієї функції по Х, х 2, у і прирівняємо їх до нуля:

Переносячи в першому і другому рівнянні у в праву частину і прирівнюючи ліві частини, отримаємо після очевидних скорочень:

Вирішуючи це рівняння спільно з третім рівнянням системи, знайдемо, що Це точка - претендент на екстремум.

Використовуючи другі приватні похідні, неважко показати, що знайдена точка є умовний мінімум функції /

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

Для закріплення теми розглянемо еше один числовий приклад (№ 2). Знайти максимальне значення функції

за умов:

Рішення. Функція / є увігнутою, так як є сумою лінійної функції f \u003d 2х 2 + 4х ьяку можна розглядати як увігнуту, і квадратичної форми / 2 = х -2x1, яка негативно визначена. Обмеження містять тільки лінійні обмеження. Отже, можна скористатися теоремою Куна - Таккера і схемою рішення ЗКП.

1. Складемо функцію Лагранжа:

2. Запишемо необхідні і достатні умови існування сідлової точки функції L.

3. Введемо в систему лінійних нерівностей додаткові невід'ємні змінні v b V2, w, w 2, звертають нерівності в рівності. Отримаємо систему рівнянь:

При цьому, природно, виконуються умови:

Необхідно знайти базисне рішення системи рівнянь (2.33) для визначення координат сідлової точки функції Лагранжа. З цією метою скористаємося методом штучного базису. Мінімізуємо штучну цільову функцію

де Zi, Zi - штучні змінні, за умов:

Тут очевидне базисне допустиме рішення виглядає наступним чином:

цільову функцію Fвисловимо через небазисних змінні:

Закінчуючи міркування, відзначимо, що вона звертається в нуль при Xj (0) \u003d 1, \u003d 1 і інших змінних з нульовими значеннями. Таким чином, Т (0) \u003d (1, 1) - це оптимальний план вихідної задачі,

Лекція 11.опукле програмування

Визначення 1. З адачі опуклого програмування називається задача нелінійного програмування, де всі функції є опуклими.

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

(1)

, (2)

. (3)

Нам знадобляться деякі допоміжні побудови в просторі
векторів
. Вектор з перших
компонент точки будемо позначати через . Отже,
.

Для завдання (1) - (3) визначимо безліч

де
.

Лемма . Для завдання опуклого програмування (1) - (3) безліч опукло.

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

З отриманих нерівностей і випливає опуклість безлічі .

Теорема 1. (Теорема Куна-Таккера в формі про седловой точці функції Лагранжа завдання опуклого програмування ) Нехай в задачі опуклого програмування (1) - (3) система (2) задовольняє умові Слейтера щодо був рішенням завдання (1) - (3), необхідно і достатньо, щоб існував ненегативний вектор такий, що
- сідлова точка функції Лагранжа.

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

Необхідність. нехай - рішення задачі (1) - (3). покладемо
. Очевидно, що
, так як
,
і
.

Переконаємося, що
. Припустимо гидке. Це означає, що знайдеться точка
така, що
. отже, - така допустима точка, значення цільової функції в якій менше мінімального. Отримуємо протиріччя з тим, що - рішення задачі опуклого програмування.

Отже,
. Згідно лемі безліч опукло. Отже, виконуються всі вимоги теореми 8.2. Тому існує ненульовий

вектор
опорний в точці до безлічі :

Переконаємося далі, що всі координати вектора непозитивні. Припустимо гидке. Нехай існує координата
. Зафіксуємо у вектора всі компоненти, крім -ої. Тоді, враховуючи, що твір
може приймати як завгодно великі значення (в силу необмеженість зверху координати ), Отримуємо протиріччя з нерівністю (4).

Легко побачити, що при будь-якому
вектори
включаються в безліч . Тоді з (4) маємо:

Покажемо, що
. Нехай це не так. тоді
. отже,
. За умовою Слейтера існує вектор
такий, що
. Тому
. Отримане протиріччя і означає, що
.

позначимо
. Покажемо, що побудований вектор являє собою шуканий вектор множників Лагранжа. Очевидно, що
і з (5) отримуємо

Звідси при
слід

. (7)

З іншого боку, так як
(оскільки
) і
, Отримуємо нерівність

. Звідси і з (7) випливає, що в точці
виконується умова доповнює нежорсткості:

. (8)

З (6) і (8) маємо

або, що те ж саме,

Далі, нехай
. тоді
. Звідси і з (8) отримуємо нерівність

Нерівності (9), (10) і означають, що
- сідлова точка функції Лагранжа завдання випук-

лого програмування. Що й треба було.

Перш, ніж познайомитися з ще одним варіантом теореми Куна-Таккера, наведемо наступну теорему, яка представляє собою критерій умовного мінімуму в термінах конусів опорних векторів.

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

. (11)

Доказ випливає безпосередньо з теореми 6.5 і визначення конуса
опорних векторів в точці до безлічі
.

теорема 3. (Теорема Куна-Таккера в диференціальної формі для завдання опуклого програмування ) Нехай дана задача опуклого програмування у вигляді (1), (2), де всі функції
безперервно мають похідні, система (2) задовольняє умові Слейтера. Тоді для того, щоб вектор
був рішенням завдання (1), (2), необхідно і достатньо, щоб існував ненегативний вектор такий, що виконуються умови

, (12)

.

Доведення. Покажемо, що умови (12) і (13) еквівалентні включенню (11). нехай точка
така, що
. тоді
і
.

нехай тепер
. Тоді з теорем 2 і 10.5 випливає, що необхідною і достатньою умовою екстремуму є існування таких множників
,
, для яких
. покладемо
для всіх
і отримаємо з останнього рівності умови (12) і (13). Що й треба було.

На закінчення параграфа наведемо формулювання двох теорем Куна-Таккера для задачі ви-

пукли програмування з лінійними обмеженнями.

Теорема 4. Нехай в задачі опуклого програмування (1) - (3) система обмежень (2) має вигляд

, B - вектор розмірності
. Тоді для того, щоб ненегативний вектор був рішенням завдання, необхідно і достатньо, щоб

існував ненегативний вектор такий, що
- сідлова точка функції Лагранжа даного завдання.

Відзначимо, що в цьому випадку функція Лагранжа має вигляд.

теорема 5. Нехай в задачі опуклого програмування (1), (2) цільова функція неперервно диференційовна, система обмежень (2) має вигляд
, Де A - матриця розмірності
, B - вектор розмірності
. Тоді для того, щоб вектор
був рішенням завдання, необхідно і достатньо, щоб існував ненегативний вектор такий, що виконуються умови
,
.

Зауважимо, що в теоремах 4 і 5 не потрібно виконання умови Слейтера, тому вони не є окремими випадками теорем 1 і 3 і вимагають самостійного докази.

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

Поділіться роботою в соціальних мережах

Якщо ця робота Вам не підійшла внизу сторінки є список схожих робіт. Так само Ви можете скористатися кнопкою пошук

лекція №12

опуклого програмування

Широкий клас задач математичного програмування пов'язаний з мінімізацією опуклих функцій багатьох змінних, визначених на опуклому безлічі. Такі завдання називають завданнями опуклого програмування (ЗВП).

Завдання математичного програмування

(12.1)

називається завданням опуклого програмування, якщо всі функції є опуклими функціями.

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

Елементи опуклого аналізу

Наведемо деякі визначення і розглянемо конкретні приклади опуклих множин. Ми будемо надалі мати справу з функціями, визначеними на безлічі конечномерного евклідового просторуE n.

Визначення 12.1. безліч виду

(12.2)

називається відрізком, що з'єднує точки і, і позначається.

Очевидно, при точкаX співпаде з одним з кінців відрізка (), при з іншим (), а при - з деякою внутрішньою точкою відрізка.

Визначення 12.2. безліч називаєтьсяопуклим , Якщо разом з будь-якими двома точками і йому належить і відрізок їх з'єднує.

Опуклість безлічі означає, що з приналежності і безлічі слід, що належить для всіх.

Очевидно, в випуклі відрізок, полупрямая, пряма, коло, трикутник, напівплощина і вся площину.

Весь простір, очевидно, утворює опукле безліч. Порожня множина і безліч, що складається з однієї точки, зручно вважати опуклими.

Теорема 12.1. Теорема Фаркаша.Нехай задані матриця розмірності і вектор. Нерівність виконується для всіх в тому і тільки тому випадку, якщо існує вектор такий, що.

Доведення.Достатність. Нехай виконуються співвідношення і. Тоді для будь-якого вектора буде

Необхідність. Нехай для всіх справедливо. Розглянемо конус. Якщо, то теорема доведена. Припустимо, що. Безліч, за визначенням 12.2, опукло і замкнуто, тому в силу теореми отделимости існує вектор такий, що

(12.3)

для всіх.

Так як при всіх, то з (12.3) отримуємо, що при всіх. Значить. З іншого боку. Тобто і так як це має місце для всіх, то

. (12.4)

Але, тому з (12.3) слід

. (12.5)

Взявши, з (12.4) і (12.5) отримуємо протиріччя умовам теореми.

Зауваження. Наведемо геометричне тлумачення теореми Фаркаша. нехай

і. Конус є сукупність всіх векторів, які утворюють з кожним з векторів негострі кути. На рис 12.1 конус заштрихован вертикальними лініями, а конус - горизонтальними. Геометричний сенс теореми такий. Щоб для будь-якого вектора кут між і був негострим, необхідно і достатньо, щоб належав конусу.

рис 12.1

Визначення 12.3. Функція, задана на опуклій множині, називаєтьсяопуклою , Якщо для будь-яких точок і будь-якого виконується нерівність

(12.6)

функція називаєтьсястрого опуклою , Якщо для всіх нерівність (12.6) виконується як суворе. функція називаєтьсясильно опуклою , Якщо існує таке число, (константа сильної опуклості), Що для всіх і будь-якого виконується нерівність

(12.7)

Будь-яка сильно опукла функція є строго опуклою і тим більш опуклою функцією, але не навпаки.

Прикладом опуклою функції служить квадратична функція з позитивно певної матрицею.

Теорема 12.2. Лінійна комбінація з невід'ємними коефіцієнтами опуклих на опуклому безлічі функцій є опукла функція на даному множині.

Доведення. Нехай функції, визначені на опуклому безлічі, є опуклим на. Покажемо, що функція

, (12.8)

де опукла на.

Для довільних точок і з і будь-якого числа маємо

У цьому ланцюжку співвідношень перша нерівність справедливо, оскільки функції опуклі. Отриманий результат показує, що функція, яка визначається формулою (12.8) є опуклою на множині.

Теорема 12.3. Якщо опукла на опуклому безлічі, то для будь-яких точок і будь-яких чисел, таких що виконується нерівність Йєнсена

. (12.9)

Д о к а з а т е л ь с т в о (по індукції). При нерівність (12.9) очевидно. Справді, якщо, то і, тобто (12.9) виконується як рівність. Припустимо, що (12.9) має місце для, тобто для опуклою комбінації з точок. Покажемо, що тоді воно справедливо і для опуклою комбінації з точок множини, тобто

При цьому, якщо, то і в (12.9) очевидно рівність. Якщо ж. Те з опуклості і індуктивного припущення випливає

Кажуть, що безліч задовольняєумові регулярності, Якщо для кожного існує точка така, що, тобто

(12.10)

Неважко показати, що умовою (12.10) еквівалентно іншу умову, званеумовою регулярності Слейтера.

Теорема 12.4. Якщо для безлічі виконується умова регулярності(12.10), то безліч регулярно по Слейтеру, А саме існує точка, в якій всі обмеження виконуються строго

. (12.11)

Доведення. Нехай виконується умова регулярності (12.10). Виберемо точку, яка є опуклою комбінацією крапок і, отже, належить. Тоді при будь-якому матимемо

тобто . У цьому ланцюжку співвідношень перша нерівність справедливо в силу нерівності Йєнсена, а друге оскільки, по крайней мере, один член суми, а саме строго менше. Ці нерівності показують, що для розглянутого має місце умова регулярності Слейтера.

Наведемо без доведення наступну важливу властивість опуклих функцій.

Опукла функція, певна на опуклому безлічі неперервна в кожній внутрішній точці цієї множини і має в кожній внутрішній точці похідну по будь-якому напрямку

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

Теорема 12.5. Функція, що диференціюється на опуклому безлічі, опукла тоді і тільки тоді, коли для будь-яких і, що належать виконується нерівність

. (12.12)

Доведення.необхідність . Нехай опукла. Тоді для будь-яких і, () і всіх таких, що справедливо нерівність

або

звідки

Переходячи до межі в останньому нерівності при, отримаємо

достатність . Нехай тепер виконується умова (12.12) для будь-яких двох точок безлічі. Тоді для точки при, що належить, справедливі нерівності

Помноживши перша нерівність на, друге - на й склавши отримані нерівності, маємо

або, враховуючи, що маємо

тобто, що опукла функція на множині.

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

Теорема 12.6. Будь-яка точка локального мінімуму функції на опуклому безлічі є точкою глобального мінімуму

Доведення. Нехай - точка локального мінімуму функції на. Тоді за визначенням точки локального мінімуму існує деяка околиця цієї точки така, що виконується нерівність

. (12.13)

Припустимо, що не є точкою глобального мінімуму функції, тобто що існує точка така, що. Розглянемо точки виду.

тобто . Але це суперечить умові, що - точка локального мінімуму, оскільки при досить малих точка знаходиться в околиці, де має місце (12.13).

Отже, - точка глобального мінімуму на.

Теорема 12.7. Безліч точок мінімуму опуклої функції на опуклому безлічі є опуклим безліччю.

Доведення. Нехай - безліч точок мінімуму опуклої функції на опуклому безлічі, тобто

Виберемо дві будь-які точки і. Оскільки і - опукле безліч, то для будь-якого буде

а з огляду на опуклості функції маємо

Тобто. Крім того, оскільки - мінімальне значення функції на, то. А, значить, тобто . Отже, - опукле безліч.

Теорема 12.8. Строго опукла функція на опуклому безлічі досягає свого мінімуму не більше ніж в одній точці.

Доведення. Нехай - строго опукла функція на опуклому безлічі, тобто для будь-яких і всіх виконуватися суворе нерівність

Нехай \u003d.

Припустимо, що знайдеться точка, така, що

Тоді для будь-якого точка належить множині і в силу суворої опуклості функції буде

тобто . Це суперечить умові, що - точка мінімуму. Отже, точка єдина.

Контрольні роботи

1. Наведіть постановку задачі опуклого програмування.

2. Дайте визначення опуклого безлічі.

3.Пріведіте формулювання теореми Фаркаша.

4. Дайте геометричне тлумачення теореми Фаркаша.

5. Дайте визначення опуклою, строго опуклою і сильно опуклою функції на опуклому безлічі.

6. Наведіть приклади опуклих функцій.

7. Сформулюйте умову регулярності безлічі.

8. Сформулюйте умову регулярності по Слейтеру, безлічі.

9. Наведіть необхідна і достатня умова опуклості функції, дифференцируемойна опуклому безлічі .

10. переказати основні екстремальні властивості опуклих функцій на опуклому безлічі.

PAGE 131

Нехай дана система нерівностей виду

(4.3) і функція

Z \u003d f (x 1, x 2, ..., x n), (4.4)

причому всі функції є опуклими на деякому опуклому безлічі M, а функція Z або опукла на безлічі М, або увігнута.

Завдання опуклого програмування полягає в знаходженні такого рішення системи обмежень (4.3), при якому цільова функція Z досягає мінімального значення, або увігнута функція Z досягає максимального значення. (Умови невід'ємності змінних можна вважати включеними в систему (4.3)).

З огляду на властивості 3 0 будь-яка задача лінійного програмування є окремим випадком завдання опуклого програмування. У загальному випадку завдання опуклого програмування є задачами нелінійного програмування. Виділення завдань опуклого програмування в спеціальний клас пояснюється екстремальними властивостями опуклих функцій: всякий локальний мінімум опуклої функції (локальний максимум увігнутої функції) є одночасно і глобальним; крім того, з огляду на властивості 2 0 опукла (увігнута) функція, задана на замкнутому обмеженому безлічі, досягає на цій множині глобального максимуму і глобального мінімуму. Звідси випливає, що якщо цільова функція Z є строго опуклою (строго ввігнутої) і якщо область рішень системи обмежень не порожня і обмежена, то завдання опуклого програмування завжди має єдине рішення.

Функція F (X) \u003d F (x 1, x 2, ..., x n) називається сепарабельном, Якщо її можна представити у вигляді суми функцій, кожна з яких залежить тільки від однієї змінної, тобто якщо

(Не виключено, що F i (x i) \u003d 0 при деяких i).

Нехай в задачі опуклого програмування задані система обмежень (4.3) і цільова функція (4.4), при цьому і функція мети Z, і всі обмеження, є сепарабельном. Тоді задача має вигляд:

Знайти мінімум опуклою (максимум - увігнутою) функції

при обмеженнях

Ідея методу кусково-лінійної апроксимації полягає в тому, що всі f i, і все замінюються ламаними лініями, що складаються з прямолінійних відрізків. При цьому вихідна задача опуклого програмування замінюється нової, наближеною завданням, яка є завданням лінійного програмування. Це завдання вирішується зазвичай симплексним методом, і її рішення є наближеним рішенням вихідної задачі опуклого програмування.

Малюнок 12. Рішення задачі лінійного програмування методом кусочно-лінійної апроксимації

Для побудови наближеної завдання розглянемо кусочно-лінійну апроксимацію функції однієї змінної h (х), заданої на відрізку. Розіб'ємо цей відрізок на r частин точками x 0

Рівняння ділянки ламаної між точками (x k; h k) і (x k + 1; h k + 1) має вигляд (рівняння прямої по двох точках). Якщо кожне з відносин в цій рівності позначити через, то отримаємо:

Відзначимо, що для кожного існує єдине значення, яке задовольняє умовам (4.7). Позначивши можна переписати (4.7) у вигляді:

[Рівняння (4.8) називаються параметричними рівняннями відрізка.

Якщо h (x) \u003d 0, то другий з цих рівнянь звертається в тотожність 0 \u003d 0, а перше набирає вигляду (4.1) - рівняння відрізка, що лежить на осі абсцис].

Таким чином, для будь-якого рівняння ламаної можна записати у вигляді:

причому завжди відмінні від нуля тільки два значення (якщо х є внутрішньою точкою k-гo відрізка розбиття) або одне (якщо х збігається з кінцем відрізка).

Повертаючись до задачі опуклого програмування з сепарабельном функціями, відзначимо, що перш за все (в залежності від системи обмежень) потрібно визначити інтервал зміни кожної змінної x j. Потім кожен цей інтервал розбивається на частини точками x jk і з використанням формул (4.9) будується кусочно-лінійна апроксимація для функцій f j і. Після цього можна для вихідної завдання (4.6) записати наближену задачу:

Знайти максимум функції

при обмеженнях (4.10)

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

Відмінність отриманої завдання (4.10) від звичайної задачі лінійного програмування полягає в тому, що для кожного x j є не більше двох сусідніх ненульових і, отже, не можна брати в якості основних змінних два з однаковим j і несоседних k. Зауважимо також, що для умов невід'ємності змінних доданків f j (x j) і (якщо такі виявляться) кусочно-лінійну апроксимацію проводити, звичайно, не потрібно.

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