Розповідь з демонстрацією можливостей градиентного методу пошуку оптимального рішення.
Завдання оптимізації (пошуку найкращого рішення) не самі популярні в середовищі 1С-негов. Дійсно, одна справа - облік виконання будь-яких рішень, і зовсім інша справа - прийняття цих самих рішень. Останнім часом, однак, мені здається 1С кинулася наздоганяти конкурентів в даному питанні. Дійсно захоплююче об'єднати під одним дахом всі, що може знадобитися сучасному менеджеру, наздоганяючи в цьому питанні SAP і замінюючи MS Project та інші системи планування.
Отже, перша тема - метод градієнтного спуску.
Сфера застосування методу - будь-які завдання на знаходження масиву з n змінних, що забезпечують мінімальне (максимальне) значення цільової функції. Цільова функція при цьому - функція від цих самих n змінних самого довільного виду - єдина умова, що накладається методом на цільову функцію - її безперервність принаймні на відрізку пошуку рішення. Безперервність на практиці означає, що для будь-якого поєднання значень змінних можна знайти дійсне значення цільової функції.
Давайте введемо позначення:
- Безліч змінних Х, від яких залежить значення цільової функції
І сама цільова функція Z, що обчислюється самим довільним чином з безлічі Х
Тепер пояснимо, що ж таке градієнт. Градієнт це вектор багатовимірного простору, який вказує напрямок найбільшого зростання деякої функції. Компонентами градієнта є диференціали всіх змінних функції Z.
Ось звідси і випливає головне обмеження застосовності методу градієнтного спуску - дифференцируемость (безперервність) функції на всьому протязі області пошуку рішення. Якщо дана умова дотримується, то пошук оптимального рішення питання суто технічне.
Класичний метод градієнтного спуску реалізовується для мінімізації цільової функції через антіградіента (тобто вектор протилежний градієнту), який виходить з градієнта найпростішим чином - множенням на -1 всіх компонентів градієнта. Або в позначеннях:
Тепер найголовніше питання: а як нам знайти ці самі dZ і dX1. dX2 і т.д. Дуже просто! dXn - це нескінченно малий приріст змінної Xn. скажімо 0,0001 від її поточної величини. Або 0,0000000001 - головне, щоб воно (приріст) було дійсно малим :)
А як же обчислюється dZ. Теж елементарно! Обчислюємо Z для набору змінних X. а потім змінюємо в цьому наборі змінну Xn на величину dXn. Знову обчислюємо значення цільової функції Z для цього злегка модифікованого набору (Zn) і знаходимо різницю - це і буде dZ = Zn - Z. Ну а тепер коли нам відомі dXn і dZ знайти dZ / dXn простіше простого.
Знайшовши послідовно всі компоненти градієнта і антіградіента ми отримуємо напрямок зміни змінних, яке найшвидшим образом дозволить досягти мінімуму функції.
На наступному (k + 1) етапі, потрібно обчислити нові значення масиву змінних X. Очевидно, що для наближення до мінімуму цільової функції Z ми повинні коригувати значення X попереднього (k-го) етапу в напрямку антіградіента за такою формулою:
Залишається розібратися з цією самою альфою у формулі. Навіщо вона потрібна і звідки вона береться.
α - це коефіцієнт на який домножается антіградіента для забезпечення досягнення можливого мінімуму функції в заданому напрямку. Сам по собі градієнт або антіградіента не є мірою зсуву змінної, а вказують лише напрямок руху. Геометричний сенс градієнта - це тангенс кута нахилу дотичної до функції Z в точці Xn (відношення протилежного катета dZ до прилеглого dXn), але рухаючись по дотичній ми неминуче відхилимося від лінії функції до досягнення її мінімуму. Сенс дотичній в тому, що вона дає відображення у вигляді прямої довільної криволінійної функції в дуже вузькому проміжку - околицях точки Xn.
Пошук значення параметра α виконується одним з методів одновимірної оптимізації. Значення змінних нам відомі, відомі і їх градієнти - залишається мінімізувати цільову функцію в околицях поточного рішення по одній єдиній параметру: α.
Зупинятися на одновимірної оптимізації я тут на буду - методи досить прості для розуміння і реалізації, скажу лише, що я використовував в своєму рішенні метод "золотого перетину". ОДЗ для α знаходиться в проміжку від 0 до 1.
Отже, резюмуючи написане, сформулюємо послідовність кроків для пошуку рішення методом градієнтного спуску:
- Формуємо початкове опорне рішення, привласнюючи шуканим змінним випадкові значення з ОДЗ.
- Знаходимо градієнти і антіградіента для кожної змінної як відносини приросту цільової функції при відносно малому збільшенні значення змінної до значення приросту цієї самої змінної.
- Знаходимо коефіцієнт α. на який потрібно множити антіградіента перед додаванням до початкових значень опорного рішення методом одновимірної оптимізації. Критерій оптимізації - найменше з можливих значення цільової функції для скоригованих таким чином значень.
- Перераховуємо відповідно до одягну значеннями антіградіента і коефіцієнта зсуву α.
- Перевіряємо досягнута необхідна точність (ε) обчислення мінімуму цільової функції:
6. Якщо умова виконана і від етапу до етапу значення цільової функції змінилося нижче встановленого нами ж критерію це означає, що необхідна точність досягнута і поточний безліч є вирішенням завдання, інакше - перехід до кроку 2.
Тепер давайте перейдемо до практичної задачі, яка вирішена в обробці.
За умовою завдання необхідно встановити ціну на якийсь товар таким чином, щоб прибуток від його реалізації в планованому періоді була максимальною. При цьому потрібно враховувати, що обсяг реалізації залежить від встановленої нами ціни, а закупівельна ціна товару (впливає на валовий прибуток) також залежить від обсягу закупівлі товару: постачальник готовий надавати знижки тим більше, чим більше буде обсяг нашої закупівлі. Тобто нам потрібно одночасно з встановленням ціни розуміти, скільки товару ми зможемо реалізувати і за якою ціною і, отже, скільки товару нам потрібно для цього закупити, і тоді ми будемо знати, яка буде закупівельна ціна. Загалом, така трохи рекурсивна логіка пошуку рішення :)
Найголовніше, що ми маємо - це безперервність змінних (ціни і обсягу закупівлі / реалізації) і цільової функції (прибуток є завжди і може приймати будь-яке значення, навіть якщо вона з мінусом, то називається збиток), а значить, метод градієнтного спуску - саме воно.
Для вирішення завдання даний метод застосовується двічі: на першому етапі ми знаходимо параметри рівняння попиту на продукцію за даними продажів попередніх періодів. Тобто, припускаючи якийсь вид залежності попиту від ціни, обчислюємо значення параметрів цієї залежності, мінімізуючи суму квадратів відхилень між розрахунковими і фактичними даними про продажі. На другому етапі, користуючись знайденими параметрами залежності між обсягом продажів і ціною реалізації, ми оптимізуємо прибуток і теж методом градієнтного спуску, хоча б застосовуваним всього для однієї змінної. Так як метод градієнтного спуску мінімізує цільову функцію, а прибуток як ніщо інше потребує максимізації, ми використовуємо не твіальную цільову функцію з назвою "МінусПрібиль", яка всього-то й робить, що обчислює прибуток за отриманим значенням ціни, а перед поверненням примножує її на -1 :) І адже працює! Тепер чим менше стає "МінусПрібиль", тим більше насправді там не є реальний прибуток від продажів.
Приклад рішення в обробці, як і універсальна функція пошуку рішення методом градієнтного спуску. Суть універсальності в тому, що змінні передаються в неї у вигляді масиву, а цільова функція передається як параметр рядком. Цільову ж функцію, яка приймає масив змінних і повертає значення, пишіть самі якого завгодно виду - головне, щоб вона повертала число. І таке число, що чим менше воно буде, тим ближче поданий масив аргументів до оптимального рішення.
Чому не привів тут готову процедуру, а викладаю обробку? По-перше, процедура і без того задовга, а по-друге, без цільових функцій вона не працює, так що потрібно затягувати все, та й ще у взаємозв'язку. Я сподіваюся, що викладена у статті теорії цілком достатньо для того, щоб Ви змогли реалізувати своє рішення, можливо, навіть кращим, ніж у мене, чином. Ну якщо вже зовсім не буде виходити - качайте готову обробку і користуйтеся :)