Застосування Xpress Optimizer для вирішення задач моделювання та оптимізації
У статті наведено огляд пакету Xpress Optimizer, призначеного для вирішення задач математичного моделювання та оптимізації. Цей програмний продукт протягом кількох років розробляється компанією Dash Optimization. Його скорочена версія доступна для вільного завантаження на сайті компанії.
За допомогою Xpress Optimizer можна реалізовувати математичні моделі різної складності та проводити їх оптимізацію за всілякими параметрами. Гнучка мова опису математичних моделей дозволяє враховувати широкий спектр обмежень, а введені до нього елементи функціонального програмування дозволяють уникнути багатьох складнощів з формалізацією моделі.
У основі пакета лежить ядро математичних функцій, реалізованих C++. При цьому до математичного ядра поставляється Xpress IVE – графічне середовище розробки спеціалізованою мовою програмування Mosel.
Програма Mosel називається моделлю. Вона компілюється в проміжний формат, а потім запускається на ядрі оптимізатора, що є набором реалізованих чисельних оптимізаційних методів. При цьому скомпільовану модель можна запустити на консольному варіанті Optimizer, встановленому, наприклад, кластері або суперкомп'ютері. Варто зазначити, що консольна версія Optimizer підтримує компіляцію моделей та з мови Mosel з командного рядка.
Мова програмування Mosel є процедурною мовою, яка підтримує умовні та циклічні оператори. Графічна середовище розробки IVE підтримує кілька майстрів автогенерації коду, за допомогою яких можна в режимі помічника реалізувати та оптимізувати математичну модель, яка не містить складних умов. Також моваПрограмування підтримує реалізацію функцій. В цілому, як видно з наступних прикладів, синтаксис mosel сильно нагадує синтаксис мови програмування Pascal.
Далі розглянемо просту програму на Mosel, яка демонструє роботу з безліччю:
Далі розглянемо застосування Xpress Optimizer для вирішення найпростішого оптимізаційного завдання.
Це завдання є модель управління доставками. Як вихідні дані програмі надаються безлічі виробників і споживачів, виробничі потужності постачальників і попит споживачів, і навіть витрати на доставку одиниці виробленої продукції від виробника до споживача. Метою оптимізації є мінімізація транспортних витрат за умови задоволення попиту всіх споживачів. Як змінні завдання приймаються обсяги доставки від виробника споживачеві. Усі вихідні дані завантажуються із файлів. Результат роботи програми виводиться в консоль оптимізатора та файл. Також програма будує стовпчасту діаграму, що показує завантаження виробників. Діаграма відображається у відповідному вікні Xpress Optimizer.
Нижче наведено лістинг розробленої програми на Mosel.
На відміну від попередньої програми, у цьому прикладі було підключено два модулі: лінійну оптимізацію та модуль, відповідальний за малювання графіків (mmive). У розділі declarations окрім множин string оголошуються масиви, що індексуються за даними множинами, а також скалярні змінні. Слід окремо відзначити тип mpvar – це тип змінних завдань. За ними ядро оптимізації вестиме роботу. Ініціалізація даних проводиться з файлів за допомогою команди initializations from, далі слідує ім'я файлу. Дані у файлі повинні бути рівно в тому порядку, в якому вони наводяться всередині командиініціалізації. Приклад такого файлу для першої ініціалізації наведемо нижче:
Після ініціалізації динамічно проініціалізуємо змінні задачі. Вони створюються лише тих пар клієнт-постачальник, котрим задані транспортні витрати. Такий прийом дозволяє заощадити системну пам'ять у випадку, якщо кількість постачальників і споживачів буде значною, а інформація про витрати на доставку буде задана не для всіх можливих пар. Змінні завдання створюються таким кодом:
Функція exisits перевіряє наявність об'єкта в пам'яті. Ініціалізація змінних завдання проводиться у циклі, що ітерує за підмножиною декартові твори множин Customers і Developers, для кожного з яких виконується умова, записана після символу .
Далі оголошується цільова функція TotalCost – функція лінійного програмування. Потім задаються обмеження щодо виробничих потужностей та задоволення попиту.
Після завдання обмежень командою minimize проведемо розв'язання задачі лінійного програмування.
У наступному коді проводиться аналіз результатів розв'язання задачі:
Функція getprobstat отримує статус завдання (вирішена, необмежена чи несумісна). Константа 2 означає, що завдання вирішено. У такому випадку здійснюється одержання значень змінних за допомогою команди getsol. Перевірка getsol(x(c,d))>0 необхідна, оскільки завдання вирішується чисельно, і деякі нульові значення змінних визначаються з невеликою похибкою.
Далі відбувається побудова стовпчастої діаграми, що показує завантаження виробників.
Потім за допомогою команди initializations відбувається запис результатів у текстовий файл.
У цьому прикладі розглянуто завдання лінійного програмування. Однак ядро Xpress Optimizer надає функціїдля вирішення задач квадратичного програмування (у тому числі цілих і змішаних). При цьому мова mosel дозволяє розробнику вказувати метод розв'язання – симплекс або евристичні алгоритми як параметр функції minimize.
Крім мінімізації, доступна також максимізація (функція maximize).
Загалом мова mosel за своїм синтаксисом нагадує Pascal. У ньому доступна реалізація процедур, функцій, додаткових модулів, зокрема C++.
Як висновок можна відзначити, що використання Mosel і Xpress Optimizer дозволяє розробнику не акцентувати увагу на технічну реалізацію методів оптимізації, а більше часу приділити побудові моделі та формалізації завдання.