Економічні науки/8.Математичні методи в економіці
К.т.н.  Федорчук Є. Н., ст. викл. Федорчук  А. І., к.е.н. Шайда О. Є.

Національний  університет “Львівська політехніка”

Моделювання дискретних задач оптимізації для пошукових критеріїв у базах даних.

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

1. Класи задач планування та проектування. Їх моделі  у формі задач неперервної оптимізації.

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

Ф = (сi – Сk)2                                                                               (1)

де сi  - вартості  для n –складових елементів комп”ютера; Ск- - задана вартість комп”ютера.

 при  прямих обмеженнях на окремі вартості

                                                          сі min  <= ci <= ci max.  ,                                                                                                                   

де сі min  та ci max – мінімальні та максимальні значення вартості елемента в  його групі. В такій постановці задача  розв’язується, як задача  неперервної  оптимізації.

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

знайти                                      min Ф=  ,             (2)

де- n- кількість груп;  ki  - кількість елементів в і-тій групі; ci – вартість і-того елемента; Сзад -  задана вартість набору. Обмеження задачі включають :

Ø  обмеження на     вартість елементів в  і-тій групі:    

сі min <=   с і <= сі  max ;    (3)

Ø  обмеження  на кількість елементів   в і-тій групі:

                                            1<= ki  <= ki max                 (4)

Після знаходження рішення  задачі значення с і   уточнюють шляхом пошуку у масиві вартостей найближчих значень. Значення ki   - кількості  елементів у і-тій групі, заокруглюють до найближчого цілого.

         Розглянемо приклади задач і їх математичну постановку у вигляді (2)- (4).

1.2. Задача планування прибутку від реалізації товару чи послуг.

                                          Знайти  min Ф=  ,   (5)

де: - n- кількість груп; ki  - кількість товару(послуг) в і-тій групі; ci – вартість і-того товару(послуги)  ; Сзад - прогнозна вартість  реалізації  набору товарів ( послуг). Обмеження задачі включають :

       обмеження на     вартість  товару(послуг)  в окремій групі;     

                                                сі min <=   с і <= сі  max ; 

обмеження  на кількість  товару(послуг)  в і-тій групі:

1<= ki  <= ki max

Після знаходження рішення  задачі значення с і   уточнюють шляхом пошуку найближчих  дискретних значень у масиві вартостей. Аналогічно поступають і для значень ki   - кількостей  послуг  в і-тій групі.

1.3. Задача  оптимізації пасажирських перевезень. Є ряд  засобів, які  перевозять пасажирів, товари. Засоби відрізняються місткістю та вартістю перевезень. Необхідно знайти оптимальні плани перевезень.  

                         Знайти  min Ф=  +        ( 6)

де- mi- місткість транспорту i- тої  групи; ki  - наявність засобів к є (0,1); ci – вартість і-того перевезення; Сзад - прогнозна вартість перевезень;  Nзад  - кількість перевезень пасажирів, товарів. Обмеження задачі включають :

·         обмеження на     вартість  перевезень в окремій групі;     

сі min <=   с і <= сі  max ; 

·         обмеження на     місткість  транспортного засобу і-тої групи;     

mі min <=   m і <= mі  max ; 

·         обмеження  на кількість  типів транспорту ;

0<= ki  <= 1

Після знаходження рішення  задачі значення с і  , m і    уточнюють шляхом пошуку у масивах  найближчих значень. Значення ki   заокруглюють  до значень 0 або 1.

2. Алгоритм рішення неперервної задачі оптимізації

Алгоритм рішення  вище розглянутих задач може включати дві групи  операцій. Перша група виконує:

·      аналіз бази даних  задачі і визначення кількості груп елементів;

·      Вибірки Смін, Смах та Ммін та Ммах   у групах;

·      Визначення  необхідної вартості набору;

Друга  група виконує:

·         рішення задачі оптимізації;

·        пошук елементів  плану(конфігурації) в базі даних  за результатами рішення.

Проміжні рішення задач (1 - 6) дають оптимальні   цінові  кластери – набори товарів. Аналіз кластерів допомагає вибрати найбільш оптимальні за ціною  і за  кількістю. Це дозволяє планувати   стратегії торговельних операцій.  Кожен кластер може аналізуватися за визначеними емпіричними правилами на предмет його додаткових  характеристик.

 

Є. Федорчук___________ А. Федорчук______________  О. Шайда___________