Облачные инструменты оптимизации

На этой странице вы познакомитесь с другими инструментами оптимизации, способными производить расчет с десятками тысяч переменных. Познакомитесь с бесплатными облачные сервисами. Узнаете, как составить файл с заданием для расчета в облачном сервисе Neos.
Здесь рассматриваются бесплатные облачные инструменты оптимизации:
Штатный инструмент MS Excel Поиск решения (Solver) - лишь один из множества инструментов оптимизации, которые разрабатываются многими компаниями и научными коллективами. Зачастую эти инструменты сугубо коммерческие, но все же чаще (при не слишком сложных и объемных задачах) имеется возможность использования таких инструментов бесплатно . Количество таких инструментов уже сегодня превышает полусотню. И большая их часть ориентирована не на задачи линейной оптимизации, а на разного рода сложные научные задачи нелинейной оптимизации, более сложные в решении.

Но имеется и несколько широко известных инструментов для линейной оптимизации: GAMS.com, AMPL.com, Gurobi.com, IBM.com (ILOG CPLex) и другие, для которых есть возможность использовать бесплатные версии.

Различные версии оптимизаторов слабо ориентированы на Excel. Обычно для работы с такими инструментами данные должны быть представлены в текстовом формате. Так что человеку, привыкшему к удобству представления данных в Excel, бывает сложно использовать эти инструменты.

Сложно, но можно!

Ибо эти инструменты позволяют решать бесплатно гораздо более объемные задачи, чем задачи, решаемые интегрированным в MS Office «Поиском решения». Вы можете сформулировать и решить задачу, содержащую десятки тысяч переменных.
Конечно использовать весь спектр оптимизаторов на практике не требуется никому, но выработать навык работы с одним-двумя инструментами вполне реально, особенно, если это необходимо для дела.

Наибольший интерес вызывает возможность использовать для решения задач облачные сервисы, и таким образом, радикально снизить требования к техническим характеристикам собственного компьютера.

Наиболее известен сегодня бесплатный облачный сервис-аггрегатор NEOS (neos-server.org), который дает возможность обратиться к множеству различных оптимизаторов.

NEOS

Сайт https://neos-server.org представляет собой бесплатный интернет-сервис для решения численных задач оптимизации.
Сервер NEOS Висконсинского университета (University of Wisconsin) обеспечивает доступ к более 60 внедренным solver’ам, каждый из которых имеет больше десятка категорий оптимизации. Серверы, производящие вычисления, располагаются в США и в Европе. Однако, у этого бесплатного сервиса вычислительные мощности не слишком велики: всего несколько штук обычных, пусть и мощных, серверов. Для того, чтобы пользователи не мешали друг другу, сервис ограничивает сложность задач оптимизации. Однако это не мешает моделировать и решать весьма большие задачи, так как длительность поиска оптимального решения ограничена 8 часами.

Для работы с сервисом нужно (желательно) зарегистрироваться. Регистрационные данные затем указываются везде, включая инструменты установленные локально.
Задание оформляется в виде текстового файла и отправляется через веб на сервер. Через веб после решения задачи можно посмотреть результаты расчетов. Отчеты о решенных задачах оттправляются на указанную при регистрации электронную почту. Так что решения всех задач всегда сохраняются.
В журнале отчета могут быть приведены только данные о значении целевой функции, а полные результаты приводятся в конце отчета в виде ссылки.

Ниже приведен пример составления задания в формате GAMS для решения кейса Кондитерская фабрика Алиса.

Как составить текстовый файл задания в формате GAMS

Сначала необходимо дать название зданию. Назовем задание Confectionery Model (Кондитерская модель). С помощью команды $title запишем:
$title Confectionery Model (CONFECTIONERY,SEQ=1)
Затем нужно описать, что вычисляется в задаче и записать ключевые слова. Блок начинается с команды $onText и заканчивается командой $offText Мы хотим вычислить максимальную прибыль, составив оптимальный план производства. Ключевыми словами будут линейное программирование и название целевой функции (maximum revenue\profit plan)
$onText
Maximum revenue\profit plan for сonfectionery.
Keywords: linear programming, maximum revenue\profit plan
$offText
Теперь необходимо перечислить все переменные и параметры, которые есть в нашем кейсе. Описание начинаем со служебного слова Set и перечисляем все данные, вводя обозначения.
Пусть n — продукты, которые выпускает фабрика (перечислим названия продуктов через запятую), а f — сырье, из которого продукты изготовлены (перечисляем название всех видов сырья через запятую). Обратите внимание на синтаксис: расшифровка имени переменоой пишется в одинарных кавычках 'products' переперечисленные продукты и сырьё ограничены скобками / ... / и в самом конце ставится точка с запятой ";"
Set
  n 'products' / NutRinging, ParadiseTaste, GoldenBar, SiberianSquirrel, LateEvening, FirstForfeit /
  f 'raw material' / DarkChocolate, LightChocolate, Sugar, Caramel, Nuts /;
Далее начинаем вводить числовые данные. Первый параметр — удельная прибыль ( profit ). Обозначим b(n), запишем единицу измерения (руб/кг), и перечислим значения удельной прибыли для каждого продукта:
Parameter b(n) 'profit (rur\kg)'
   / NutRinging 257.5, ParadiseTaste 214.0, GoldenBar 191.5,
   SiberianSquirrel 214.5, LateEvening 199.5, FirstForfeit 262.0 /;
Второй параметр — отпускная цена ( revenue ). Обозначим d(n), запишем единицу измерения (руб/кг), и перечислим значения отпускной цены для каждого продукта:
Parameter d(n) 'revenue (rur\kg)'
   / NutRinging 1020, ParadiseTaste 765, GoldenBar 900,
   SiberianSquirrel 895, LateEvening 945, FirstForfeit 1000 /;
Третий параметр — остатки склада сырья ( stock ). Обозначим s(f), запишем единицу измерения (кг), и перечислим значения остатков склада для каждого вида сырья:
Parameter s(f) 'stock (kg)'
   / DarkChocolate 58200, LightChocolate 7450, Sugar 19000, Caramel 22800, Nuts 39000 /;
Теперь необходимо ввести данные о составе сырья в каждом виде продукта. Ввести эти данные нужно в табличном виде.
Обозначим a(f,n) зависимость между продуктом и соответствующим сырье. Нужно явно указать, что это таблица и дать название этой таблице.
Table a(f,n) 'the composition of the product'
NutRinging ParadiseTaste GoldenBar SiberianSquirrel LateEvening FirstForfeit
DarkChocolate 0.36 0.36 0.34 0.35 0.53 0.59
LightChocolate 0.09 0.07 0.04 0.03 0.00 0.11
Sugar 0.14 0.29 0.21 0.23 0.00 0.03
Caramel 0.09 0.21 0.10 0.12 0.33 0.27
Nuts 0.32 0.07 0.31 0.27 0.14 0.00
Определим переменные. Это будет план производства - количество продуктов, которые нужно произвести. Обозначим план выпуска x(n), наименование кг.
Positive Variable x(n) 'quantity of products produced (kg)';
Определим целевую функцию. Это Прибыль (Free Variable profit)
Free Variable profit 'profit or revenue';
Запишем уравнения связывающие переменные. Сначала укажем, что это блок уравнение Equation. Затем введем обозначия: nb(f) — сколько сырья будет израсходовано для производства продуктов (спрос на сырьё) и выручки (переменная cb), которую фабрика получит после продажи произведенных продуктов. При определении выручки в одинарных ковычках запишем наименование и уравнение для её вычисления. Чтобы рассчитать выручку, нужно вес произведенного продукта умножить на его отпускную цену и сложить эти произведения (складываем n раз - столько, сколько продуктов производим). В коде это выглядит так:
Equation
  nb(f) 'demand of raw material'
  cb   'profit or revenue =e= sum(n, d(n)*x(n))';
Теперь запишем сами уравнения. Сначала вычислим, сколько сырья потребуется на производство продуктов и сравним его с остатками склада по каждому виду сырья. Для расчета количества сырья по каждому виду продукции умножим количество продуктов, которые нужно произвести x(n) на a(f,n). А затем сравним полученные результаты с остатками склада по каждому виду сырья s(f). В идеальном случае расход сырья должен быть равен остатку склада.
nb(f).. sum(n, a(f,n)*x(n)) =l= s(f);
Осталось вычислить прибыль, которую получит фабрика после продажи произведенных продуктов. Расчет прибыли аналогичен расчету выручки. Поэтому в выражении для расчета выручки заменим отпускную цену d(n) на удельную прибыль b(n). При записи уравнений никакие кавычки не нужны.
cb..   profit =e= sum(n, b(n)*x(n));
В конце нужно написать, что нужно провести моделирование, указав имя программы, которое было записвно в начале после команды $title и указать уравнения, которые нужно согласовать между собой:
Model confectionery 'Confectionery Model' / nb, cb /;
И в последней стоке файла указать цель и как ее достигнуь: решить (указать название файла), максимизируя прибыль с помощью линейного программирования:
solve confectionery maximizing profit using lp;
Всё, файл создан. Набрать его можно в любом текстовом редакторе и сохранить под именем confectionery.gms Посмотрите готовый файл:
$title Confectionery Model (CONFECTIONERY,SEQ=1)
$onText
Maximum revenue\profit plan for сonfectionery.
Keywords: linear programming, maximum revenue\profit plan
$offText
Set
  n 'products' / NutRinging, ParadiseTaste, GoldenBar, SiberianSquirrel, LateEvening, FirstForfeit /
  f 'raw material' / DarkChocolate, LightChocolate, Sugar, Caramel, Nuts /;

Parameter b(n) 'profit (rur\kg)'
   / NutRinging 257.5, ParadiseTaste 214.0, GoldenBar 191.5,
   SiberianSquirrel 214.5, LateEvening 199.5, FirstForfeit 262.0 /;

Parameter d(n) 'revenue (rur\kg)'
   / NutRinging 1020, ParadiseTaste 765, GoldenBar 900,
   SiberianSquirrel 895, LateEvening 945, FirstForfeit 1000 /;

Parameter s(f) 'stock (kg)'
   / DarkChocolate 58200, LightChocolate 7450, Sugar 19000, Caramel 22800, Nuts 39000 /;

Table a(f,n) 'the composition of the product'
NutRinging ParadiseTaste GoldenBar SiberianSquirrel LateEvening FirstForfeit
DarkChocolate 0.36 0.36 0.34 0.35 0.53 0.59
LightChocolate 0.09 0.07 0.04 0.03 0.00 0.11
Sugar 0.14 0.29 0.21 0.23 0.00 0.03
Caramel 0.09 0.21 0.10 0.12 0.33 0.27
Nuts 0.32 0.07 0.31 0.27 0.14 0.00
Positive Variable x(n) 'quantity of products produced (kg)';

Free Variable profit 'profit or revenue';

Equation
  nb(f) 'demand of raw material'
  cb   'profit or revenue =e= sum(n, d(n)*x(n))';

nb(f).. sum(n, a(f,n)*x(n)) =l= s(f);
cb..   profit =e= sum(n, b(n)*x(n));

Model confectionery 'Confectionery Model' / nb, cb /;

solve confectionery maximizing profit using lp;

Как отправить задание

Готовый файл нужно загрузить на сервер NEOS. Для этого на страничке подачи заявки укажите файл с заданием, Форма для отправки файла с заданием попросите вывести результаты в текстовые файлы Форма для вывода результата и нажмите кнопку отправки. Клавиша для отправки файла с заданием Сервер проверит ошибки и в случае их отсутствия сообщит в новом окне, что задание принято. Через несколько секунд или минут, в зависимости от очереди заданий у сервера и сложности вашей задачии, сервер выдаст результат. Простые задачи с малым количеством переменных не требуют более нескольких секунд времени.

Как выглядит полученное решение

Листинг результатов для задачи про кондитерскую фабрику выглядит так:
GAMS 34.2.0 r6925a71 Released Feb 5, 2021 LEX-LEG x86 64bit/Linux - 02/23/21 15:57:56 Page 1
Confectionery Model (CONFECTIONERY,SEQ=1)
C o m p i l a t i o n

COMPILATION TIME    =    0.001 SECONDS   3 MB 34.2.0 r6925a71 LEX-LEG
GAMS 34.2.0 r6925a71 Released Feb 5, 2021 LEX-LEG x86 64bit/Linux - 02/23/21 15:57:56 Page 2
Confectionery Model (CONFECTIONERY,SEQ=1)
Model Statistics  SOLVE confectionery Using LP From line 49


MODEL STATISTICS

BLOCKS OF EQUATIONS      2    SINGLE EQUATIONS      6
BLOCKS OF VARIABLES      2    SINGLE VARIABLES      7
NON ZERO ELEMENTS       34


GENERATION TIME    =    0.001 SECONDS   4 MB 34.2.0 r6925a71 LEX-LEG
GAMS 34.2.0 r6925a71 Released Feb 5, 2021 LEX-LEG x86 64bit/Linux - 02/23/21 15:57:56 Page 3
Confectionery Model (CONFECTIONERY,SEQ=1)
Solution Report    SOLVE confectionery Using LP From line 49


         S O L V E    S U M M A R Y

   MODEL   confectionery    OBJECTIVE   profit
   TYPE   LP          DIRECTION   MAXIMIZE
   SOLVER  CPLEX        FROM LINE   49

**** SOLVER STATUS    1 Normal Completion
**** MODEL STATUS    1 Optimal
**** OBJECTIVE VALUE      33596856.7493

  RESOURCE USAGE, LIMIT      0.007 10000000000.000
  ITERATION COUNT, LIMIT     4   2147483647
--- GAMS/Cplex licensed for continuous and discrete problems.
--- GMO memory 0.50 Mb (peak 0.50 Mb)
--- Dictionary memory 0.00 Mb
--- Cplex 20.1.0.0 link memory 0.00 Mb (peak 0.00 Mb)
--- Starting Cplex
--- LP status (1): optimal.
--- Cplex Time: 0.00sec (det. 0.02 ticks)

Optimal solution found
Objective:  33596856.749311
---- EQU nb demand of raw material
           LOWER   LEVEL    UPPER   MARGINAL
DarkChocolate    -INF   57907.466 58200.000    .
LightChocolate   -INF    7450.000  7450.000  1626.501
Sugar             -INF   19000.000  19000.000  405.041
Caramel        -INF   22800.000 22800.000   604.545
Nuts         -INF   38060.165 39000.000    .

           LOWER   LEVEL    UPPER   MARGINAL
---- EQU cb      .      .      .      1.000

 cb profit or revenue =e= sum(n, d(n)*x(n))

---- VAR x quantity of products produced (kg)
           LOWER   LEVEL    UPPER   MARGINAL
NutRinging       .   69303.030   +INF       .
ParadiseTaste     .      .     +INF    -144.272
GoldenBar       .      .     +INF    -19.073
SiberianSquirrel   .   40424.242   +INF       .
LateEvening      .   35490.358   +INF       .
FirstForfeit     .      .     +INF    -92.294

           LOWER   LEVEL    UPPER   MARGINAL
---- VAR profit   -INF  3.3597E+7    +INF      .

 profit profit or revenue

**** REPORT SUMMARY :      0    NONOPT
                  0 INFEASIBLE
                  0  UNBOUNDED

EXECUTION TIME     =     0.015 SECONDS    4 MB  34.2.0 r6925a71 LEX-LEG

USER: NEOS Server License prod-exec-1.neos-server.orgS201022/0001AB-GEN
mac@44:a8:42:25:df:6c DCE917
License for teaching and research at degree granting institutions