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

.

У залежності від характеру побудови dⁿ чисельні методи розділяються на прямі (без використання похідних), методи спуска (з використанням перших похідних) і методи з використанням других похідних.

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

Класичні методи визначення екстремумів

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

Можна виділити клас нелінійних задач, що відносяться до класичних методів оптимізації. Припустимо, що серед обмежень математичної моделі немає нерівностей, не обов'язкові умови незаперечності, перемінні не є дискретними, m < n, а цільові функції безперервні і мають частки похідні принаймні другого порядку. У цьому випадку задачу оптимізації можна сформулювати так: знайти перемінні х_1, х₂,..., х_M, що задовольняють системі рівнянь

(2.1.4)

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

(2.1.5)

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

Прикладом типової і простої нелінійної задачі є наступна: дане підприємство для виробництва якогось продукту витрачає два засоби в кількості х₁ і х₂ відповідно. Це фактори виробництва, наприклад, машини і праця, два різних види сировини і т.п., а величини х₁ і х₂ — витрати факторів виробництва. Фактори виробництва надалі будемо вважати взаємозамінними. Якщо це "праця" і "машини", то можна застосовувати такі методи виробництва, при яких величина витрат машин у зіставленні з величиною витрат праці виявляється більше або менше (виробництво більш-менш трудомістке). У сільському господарстві взаємозамінними факторами можуть бути посівні площі або мінеральні добрива (екстенсивний або інтенсивний метод виробництва).

Обсяг виробництва (виражений у натуральних або вартісних одиницях) є функцією витрат виробництва Ця залежність називається виробничою функцією. Витрати залежать від витрати обох факторів (х₁ і х₂) і від цін цих факторів (з₁ і з₂). Сукупні витрати виражаються формулою b=c₁x₁+c₂x₂. Потрібно при даних сукупних витратах визначити таку кількість факторів виробництва, що максимізує обсяг продукції z.

Математична модель цієї задачі має вигляд:

Визначити такі перемінні х₁ і х₂, що задовольняють наступним умовам

c₁x₁+c₂x₂= b, (2.1.6)

x₁ ≥ 0, x₂ ≥ 0 (2.1.7)

при яких функція досягає максимуму.

Як правило, функція (2.1.7) може мати довільний нелінійний вид.

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

Будемо думати, що функція двічі діфференцується в точці , і в деякій її околиці. Якщо для всіх точок X цієї околиці , то говорять, що функція f(X) має екстремум у X^* (відповідно максимум або мінімум).

Точка Х^*, у якій усі частки похідні функції z = f (X) рівні 0, називається стаціонарною точкою.

Необхідна умова екстремуму. Якщо в точці Х^* функція z = f (X) має екстремум, то частки похідні функції в цій точці рані нулеві:

Отже, точки екстремуму функції z = f (X) задовольняють системі рівнянь (1.5.5):

(2.1.8)

Як і у випадку одна перемінної, необхідне умова не є достатнім для того, щоб стаціонарна точка була точкою екстремуму. Для одержання достатніх умов варто визначити в стаціонарній точці знак диференціала другого порядку. Диференціал другого порядку позначається d² f (x₁, x₂,…,x_n)і дорівнює сумі добутків часток похідних другого порядку на відповідні збільшення аргументів. Якщо від частинної похідної знайти частинну похідну по перемінній х_j, то одержимо частинну похідну другого порядку по перемінним х_i, х_j, що позначається . У цьому випадку

Достатні умови екстремуму:

а) у стаціонарній точці X⁰ функція має максимум, якщо < 0, і мінімум, якщо > 0, при будь-яких ; (у цих випадках Х⁰ = Х^*), що не звертаються в нуль одночасно;

6) якщо може приймати в залежності від і позитивні, і негативні значення, то в точці X⁰ екстремуму немає;

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

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

Знайдемо значення часток похідних другого порядку в стаціонарній точці Х⁰(х⁰₁,х⁰₂):

(можна переконатися, що а₁₂ = а₂₁). Позначимо через ∆ визначник, складений з а_ij для i, j = 1,2:

Тоді достатні умови екстремуму функції двох перемінних мають вигляд:

а) якщо ∆ > 0 і а₁₁ < 0 (а₂₂ < 0), те в точці Х⁰ функція має максимум: якщо ∆ > 0 і а₁₁ > 0 (а₂₂ > 0), те в точці Х⁰ — мінімум (у цих випадках Х⁰ = Х ^');

б) якщо ? < 0, те екстремуму немає;

в) якщо ∆ = 0, то питання про екстремум залишається відкритим.

Схема визначення екстремуму функції n перемінних збігається з правилами визначення локального екстремуму функції однієї перемінної.

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

Нехай необхідно знайти екстремум функції за умови, що перемінні задовольняють рівнянням (2.1.9)

(2.1.9)

Передбачається, що функції f і φ_i, мають безперервні частки похідні по всім перемінним. Рівняння (2.1.9) називають рівняннями зв'язку.

Говорять, що в точці Х⁰ = , що задовольняє рівнянням зв'язку (1.5.6), функція має умовний максимум (мінімум), якщо нерівність має місце для всіх точок X, координати яких задовольняють рівнянням зв'язку.

Легко помітити, що задача визначення умовного екстремуму збігається з задачею нелінійного програмування (2.1.4), (2.1.5).

Один зі способів визначення умовного екстремуму застосовується в тому випадку, якщо з рівнянь зв'язку (2.1.9) n перемінних, наприклад можна явно виразити через що залишилися n-m перемінних:

(2.1.10)

Підставивши отримані вираження для , у функцію z, одержимо

(2.1.11)

Задача зведена до перебування локального (глобального) екстремуму для функції (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)

і функція