Економічна модель оптимізації закупівель та поставок кондитерських виробів на прикладі товариства з обмеженою відповідальністю "Гермес-Груп" (стр. 10 из 22)

Задача зведена до перебування локального (глобального) екстремуму для функції (2.1.11) від n-m перемінних. Якщо в точці Х⁰ =

функція (2.1.11) має екстремум, то в точці функція

має умовний екстремум.

Метод множників Лагранжа

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

Нехай вирішується задача визначення умовного екстремуму функції

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

Складемо функцію, що називається функцією Лагранжа.

, (2.1.12)

де

постійні множники (множники Лагранжа). Відзначимо, що множникам Лагранжа можна додати економічний зміст. Якщо — доход, що відповідає планові , а функція — витрати і-го ресурсу, що відповідають цьому планові, то — ціна (оцінка) і-го ресурсу, що характеризує зміну екстремального значення цільової функції в залежності від зміни розміру і-го ресурсу (маргінальна оцінка). L(X) — функція m+n перемінних . Визначення стаціонарних точок цієї функції приводить до рішення системи рівнянь

(2.1.13)

Легко помітити, що

, тобто в (5.10) входять рівняння зв'язку. Таким чином, задача перебування умовного екстремуму функції

зводиться до перебування локального екстремуму функції L(X). Якщо стаціонарна точка знайдена, то питання про існування екстремуму в найпростіших випадках вирішується на підставі достатніх умов екстремуму — дослідження знака другого диференціала d²L(X) у стаціонарній точці за умови, що перемінні збільшення ∆_xj зв'язані співвідношеннями, отриманими шляхом диференціювання рівнянь зв'язку.

(2.1.14)

Задача опуклого програмування (ОП)

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

(2.1.15)

і функція

(2.1.16)

причому усі функції

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

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

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

Функція

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

(2.1.17)

(не виключено, що F_i(x_i) = 0 при деяких i).

Нехай у задачі ОП (2.1.15), (2.1.16) і функція мети Z, і всі обмеження

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

(2.1.18).

Ідея методу кусочно-лінійної апроксимації полягає в тому, що всі f_i, і всі

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

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

Рисунок 2.1.1 – Кусочно-лінійна апроксимація функції однієї перемінної

Обчислимо значення функції h_k(x), у цих точках. З'єднаємо попарно точки (х_k; h_k) і (х_k+1; h_k+1) відрізками прямих. Складена з цих відрізків ламана h(х) апроксимує функцію h(х) на відрізку [0, а]. (Не розглядаючи тут оцінку точності наближення, відзначимо тільки, що точність можна збільшити за рахунок більш дрібної розбивки відрізка).

Рівняння ділянки ламаної

(х) між точками (х_k; h_k) і (х_k+1; h_k+1) має вигляд

(рівняння прямої по двох точках). Якщо кожне з відносин у цій рівності позначити через

, то одержимо (2.1.19):

(2.1.19)

причому

Відзначимо, що для кожного

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

(2.1.20)

де

(Рівняння (2.1.20) називаються параметричними рівняннями відрізка. Якщо h(x)=0, те друге з цих рівнянь звертається в тотожність 0 = 0.

Таким чином, для будь-якого

рівняння ламаної можна записати у виді:

(2.1.21)

причому завжди відмінні від нуля тільки два значення

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

Повертаючи до задачі ОП із сепарабельними функціями, відзначимо, що насамперед (у залежності від системи обмежень) потрібно визначити інтервал зміни кожної перемінної х_j. Потім кожен цей інтервал розбивається на частині точками х_jk і з використанням формул (2.1.21) будується кусочно-лінійна апроксимація для функцій f_j і

. Після цього можна для вихідної задачі (2.1.18) записати наближену задачу:

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

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

(2.1.22)

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

з однаковим j і несусідніми k. Помітимо також, що для умов незаперечності перемінних що складаються f_j(x_j) і (якщо такі виявляться) кусочно-лінійну апроксимацію проводити, звичайно, не потрібно.[9]