На этой странице вы познакомитесь с другими инструментами оптимизации, способными производить расчет с десятками тысяч переменных. Познакомитесь с бесплатными облачные сервисами. Узнаете, как составить файл с заданием для расчета в облачном сервисе Neos.
Здесь рассматриваются бесплатные облачные инструменты оптимизации:
Возможность облачных вычислений на удаленных серверах предоставляют многие порталы: как широко известные Microsoft Azure, Google, Amazon, IBM, Яндекс, …
так и существенно менее известные ( Neos, GAMS, AMPL, Gurobi, …). Ресурсы предоставляются не только на коммерческой основе, но и бесплатно (для решения относительно небольших задач и обучения).
Привлекательность облачных сервисов обусловлена как возможностью использовать для решения своих задач удаленные (облачные) вычислительные мощности, что позволяет радикально снизить требования к техническим характеристикам собственного компьютера, так и возможностью отказаться от развертывания и поддержки на своем компьютере различного специализированного ПО.
Рассмотрим подробнее вопросы облачной оптимизации.
Штатный инструмент MS Excel «Поиск решения (Solver) - всего лишь один из множества инструментов оптимизации.
Инструменты оптимизации (солверы) разрабатываются многими компаниями и научными коллективами. Зачастую эти инструменты сугубо коммерческие, но все же чаще имеется возможность бесплатного использования таких инструментов.
На сегодняшний день общее количество даже наиболее известных инструментов оптимизации превышает полусотню. Большая их часть ориентирована не на задачи линейной оптимизации, а на разного рода сложные научные задачи общей (нелинейной) оптимизации. Ведь постоянно возникают специфические проблемы науки или управления, которые очень плохо решаются стандартными солверами, поэтому требуют разработки новых инструментов.
Однако большинство бизнес-задач могут быть решены с помощью одного-двух подходящих солверов.
Как правило, различные виды оптимизаторов - это универсальные инструменты, не требующие какого-то специфического программного обеспечения.
Большинство из них слабо ориентированы на Excel, поэтому исходные данные и формулы для оптимизации должны быть представлены в текстовом формате.
Составить задание можно в любом текстовом редакторе любой операционной системы и в нем же (или прямо в браузере) просмотреть результаты.
И это - огромная ценность.
Однако человеку, привыкшему к удобству представления данных в Excel, бывает сложно использовать эти инструменты.
Зато с помощью таких инструментов можно решать бесплатно и в любой момент гораздо более объемные задачи, чем с помощью интегрированного в MS Office «Поиска решения». ("Поиск решения" решает задачи до 200 переменных и до 100 ограничений.)
Конечно, ограничения (разные) есть и в других солверах. Но вы не всегда сможете даже заметить эти ограничения. Так свободно распространяемый солвер COIN-OR CBC позволяет решать задачи с 100 тысями целочисленных переменных. И этого достаточно для очнь многих бизнес-задач.
Разумеется, когда решение требуется ежедневно для управления реальным бизнесом, нет никаких препятствий для покупки лицензии на коммерческий оптимизатор и процессорное время облачных сервисов. Однако сначала весьма желательно понять, как вообще решать имеющуюся проблему, и будет ли достигнут какой-то эффект с помощью оптимизации. И на этой стадии (вероятно, стадии инициативной личной разработки) возможность использовать необходимый инструмент бесплатно оказывается весьма значимой.
Наиболее известен сегодня бесплатный облачный сервис-агрегатор NEOS (neos-server.org), который дает возможность обратиться к множеству различных оптимизаторов.
NEOS
Сайт https://neos-server.org представляет собой бесплатный интернет-сервис для решения численных задач оптимизации. Сервер NEOS Висконсинского университета (University of Wisconsin) обеспечивает доступ к более 60 внедренным solver’ам, каждый из которых имеет больше десятка категорий оптимизации. Серверы, производящие вычисления, располагаются в США, в Австрии и Португалии. Однако, у этого бесплатного сервиса вычислительные мощности не слишком велики.
Сложность задач ограничена, чтобы пользователи не мешали друг другу. Но фактически задачи оптимизации могут быть довольно большими, так как разрешенная длительность поиска оптимума - 8 часов.
Для работы с сервисом нужно (желательно) зарегистрироваться. Регистрационные данные затем указываются везде, включая инструменты установленные локально.
Задание оформляется в виде текстового файла и отправляется через веб на сервер. В браузере можно посмотреть и результаты расчетов. Отчеты о решенных задачах
оттправляются на указанную при регистрации электронную почту. Так что решения всех задач всегда сохраняются.
В журнале отчета могут быть приведены только данные о значении целевой функции, а полные результаты приводятся в конце отчета в виде ссылки.
Как составить текстовый файл задания в формате GAMS
Сначала необходимо дать название зданию. Назовем задание Confectionery Model (Кондитерская модель). С помощью команды $title запишем:
$title Confectionery factory model (CF)
Затем нужно описать, что вычисляется в задаче и записать ключевые слова. Блок начинается с команды $onText и заканчивается командой $offText
Мы хотим вычислить максимальную прибыль, составив оптимальный план производства.
Ключевыми словами будут линейное программирование и название целевой функции (maximum revenue\profit plan)
$onText
Maximum revenue\profit plan for confectionery factory.
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), запишем единицу измерения (руб/кг), и перечислим значения удельной прибыли для каждого продукта:
Второй параметр — отпускная цена ( revenue ). Обозначим d(n), запишем единицу измерения (руб/кг), и перечислим значения отпускной цены для каждого продукта:
Третий параметр — остатки склада сырья ( stock ). Обозначим s(f), запишем единицу измерения (кг), и перечислим значения остатков
склада для каждого вида сырья:
Теперь необходимо ввести данные о составе сырья в каждом виде продукта. Ввести эти данные нужно в табличном виде.
Обозначим a(f,n) зависимость между продуктом и соответствующим сырьем. Нужно явно указать, что это таблица и дать название этой таблице.
Table a(f,n) 'the composition of the product'
Определим переменные. Это будет план производства - количество продуктов, которые нужно произвести. Обозначим план выпуска x(n), наименование кг.
Positive Variable x(n) 'quantity of products produced (kg)';
Определим целевую функцию. Это Прибыль (Free Variable profit)
Free Variable profit, revenue;
Запишем уравнения связывающие переменные. Сначала укажем, что это блок уравнение Equation. Затем введем обозначия: nb(f) — сколько сырья будет израсходовано для производства
продуктов (спрос на сырьё), выручки (переменная ocr), которую фабрика получит после продажи произведенных продуктов и прибыли ocp.
Мы можем в одинарных ковычках записать название величины для своего удобства или формулу расчета, чтобы помнить, что вычислялось в задаче.
Напишем формулы расчета, чтобы затем скопировать из, и записать ниже без ковычек. При определении выручки в одинарных ковычках запишем наименование и уравнение для её вычисления. Чтобы рассчитать выручку, нужно вес произведенного продукта умножить на его отпускную цену и сложить эти произведения (складываем n раз - столько, сколько продуктов производим).
Расчет прибыли аналогичен расчету выручки. Поэтому в выражении для расчета выручки заменим отпускную цену d(n) на удельную прибыль b(n).
В коде это выглядит так:
Equation
Теперь запишем сами уравнения. Сначала вычислим, сколько сырья потребуется на производство продуктов, и сравним его с остатками склада по каждому виду сырья.
Для расчета количества сырья по каждому виду продукции умножим количество продуктов, которые нужно произвести x(n) на a(f,n). А затем сравним полученные результаты с остатками склада по каждому виду сырья s(f). В идеальном случае расход сырья должен быть равен остатку склада.
Уравнения для расчета прибыли и выручки скопируем из предыдущего блока. При записи уравнений кавычки не нужны. Зато в конце строки после каждого уравнения нужно поставить точку с запятой:
В конце нужно написать, что нужно провести моделирование, указав имя программы, которое было записвно в начале после команды $title и указать уравнения, которые нужно согласовать между собой:
Model cf 'Confectionery factory model' / all /;
И в последней стоке файла указать цель и как ее достигнуь: решить (указать сокращеное название файла cf), максимизируя прибыль с помощью линейного программирования:
solve cf maximizing profit using lp;
Для того, чтобы не переписывать всю программу еще раз добавим еще одну строку, закомментировав ее с помощью *. В этой строке попросим найти максимум выручки.
Тогда выполнив одно решение (например, посчитав максимум прибыли), мы можем поставить звездочку в начале строки, где просим разчитать максимум прибыли, и убрать звездочку в строке, где просим расчитать максимум выручки. После этих минимальных изменений, отправив задание еще раз, мы получим решение, в котором находится максимум выручки.
*solve cf maximizing revenue using lp;
Всё, файл создан. Набрать его можно в любом текстовом редакторе и сохранить под любым именем, но с расширением gms, например, alisa.gms.
Посмотрите готовый файл:
Как отправить задание
Чтобы отправить задание alisa.gms на облачный сервер, нужно на начальной страничке сервера NEOS (https://neos-server.org) кликнуть команду Submit a job to NEOS.
На странице выбора движка оптимизации выбираем вид задачи:
линейная оптимизация (Linear Programming LP)
или
смешанная целочисленная линейная оптимизация ( Mixed Integer Linear Programming MIP).
В подменю выбираем конкретный движок. Для той формы задачи, которая представлена в файле ***.gms, следует выбрать CPLEX [GAMS].
На открывшейся страничке CPLEX оптимайзера внизу находим
и заполняем форму Web Submission Form.
Во-первых, выбираем файл с заданием. Для этого нажмите Выберите файл, найдите нужный файл в проводнике. После этого название файла появится рядом с кнопкой Выберите файл, файл загрузился.
Во-вторых, имеет смысл запросить файл листинга выполненного задания Return GAMS listing file ( расширение этого файла lst), который содержит основную информацию. На всякий случай можно попросить и лог-файл с диагностикой Return log file.
В-третьих, укажите адрес электронной почты, на который нужно прислать результаты и щелкнете Submit to NEOS.
Short Priority указывать не обязательно, обычно задача и так выполняется быстро и в очереди заданий не стоит. Но если вы не уверены, что задача решится за 5 минут, Short Priority запрашивать точно не нужно.
Сервер проверит ошибки и в случае их отсутствия сообщит в новом окне, что задание принято.
Через несколько секунд или минут, в зависимости от очереди заданий у сервера и сложности вашей задачии, сервер выдаст результат.
Простые задачи с малым количеством переменных не требуют более нескольких секунд времени.
Как выглядит полученное решение
Листинг результатов для задачи про кондитерскую фабрику выглядит так:
В конце лога есть и ссылка на архив с результатами, в котором содержатся файлы с логом выполнения задания и с отчетом по заданию.
Обычно, файл лога выполнения не нужен, но если в задании или модели были ошибки, и оно до расчетов не дошло, то этот файл подскажет, где возникли ошибки.
Решение задачи оптимизации содержится в блоке:
Значения параметра MARGINAL - это приведенные стоимости продуктов из отчета об устойчивости, который был получен
при решении задачи с помощью Поиска решений MS Excel.
А этот блок листинга - таблица ограничений отчета об устойчивости с теневыми ценами (значения параметра MARGINAL):
Необходимо отметить, что формат заданий на оптимизацию несколько отличается у солверов разных производителей.
Различаются и требования к формату вводимых данных. Однако, уровень сложности формы заданий хоть в специфических форматах движков оптимизации,
хоть в форме программы на языке Phyton, практически не различается. Можно пользоваться тем, что нравится или чем владеете.
Конечно, отчет о результатах для задачи в тысячу переменных смотрится не очень вдохновляюще. :)
Но есть и обнадеживающие тенденции. Буквально в последние годы инструменты оптимизации поворачиваются лицом к Excel
и в плане более удобного чтения данных прямо из файлов Excel и в плане удобных интерфейсов «Excel – сервисы оптимизации».
OpenSolver
OpenSolver ( https://opensolver.org ) – этo надстройка к MS Excel, полностью бесплатная, содержит линейный, целочисленный и нелинейный оптимизатор
с открытым исходным кодом. Разрешено свободное модифицирование инструмента для собственных целей.
На странице OpenSolver можно выбрать версию для Windows или Mac в модификациях только линейная оптимизация (Linear) или линейная + нелинейная оптимизация (Advanced).
Фактически OpenSolver содержит распространенные и известные оптимизационные движки (разрешенные к бесплатному использованию),
а некоторые другие ( например, Gurobi) может использовать при наличии у пользователя лицензии (в том числе бесплатной).
Надстройка не устанавливается инсталлятором, ее нужно распаковать в удобное место
(очень желательно в какую-то стандартную папку, путь к которой не содержит символов кириллицы или юникода)
и подгружается либо прямым запуском файла opensolver.xlam, либо подключением из меню подключения надстроек Excel
Файл\Параметры\Надстройки -> кнопка «Обзор» + выбор файла opensolver.xlam + галочка на OpenSolver
Появляется панель надстройки там же, где и штатный Поиск решения в меню Данные
Надстройка OpenSolver проста в использовании.
В ней нет ограничений на число переменных и условий, так как использует в основном свободно распространяемые солверы.
Первый этап решения вашей задачи - построение модели. Для этого используется кнопка Model.
Описание панели OpenSolver-Model
После клика по кнопке Model появляетсят окно, практически полностью идентичное окну Поиск решения
Параметры задачи вводятся также как в Поиске решения.
Блок Constraints (Ограничения).
Для того, чтобы добавить ограничение
Выделите курсором команду Add new constraint.
Введите отдельно левую и правую часть ограничения, а знак между ними.
Нажмите кнопку Add constraint.
Для того, чтобы исправить ограничение
Щелкните ограничение в окне.
Сделайте необходимые исправления.
Нажмите кнопку Update constraint
Для того, чтобы удалить ограничение
Щелкните ограничение в окне.
Нажмите на клавишу Delete selected constraint.
Для решения большинства задач необходимо отметить галочкой поле Make unconstrainted variable cells non-negative
(Сделать переменные без ограничений неотрицательными).
Если вы используете именованные диапазоны (задают через меню Формулы\Задать имя), то OpenSolver предлагает показывать такие имена в установках ограничений.
Для этого используется команда Show named ranges in constraint list. Если отметить этот пункт, то OpenSolver дописывает эти имена после диапазона ячеек в скобках.
Блок Sensitivity Analysis.
В этом блоке можно запросить:
вывод отчета об устойчивости на отдельный лист. Для этого:
отметьте галочкой команду Output Sensitivity Analysis
отметьте команду on a new sheet
вывод отчета об устойчивости на тот же лист. Для этого:
отметьте галочкой команду List sensitivity analysis on the same sheet with top left cell
задать адрес ячейки текущего листа, начиная от которой надо вставить отчет
Блок Solver Engine.
В этом блоке необходимо прямо выбрать движок оптимизации, нажав на кнопку Solver Engine...
Появится панель OpenSolver - Choose Solver, на которой нужно выделить подходящий вам движок, или оставить рекомендуемый COIN-OR CBC (Linear solver).
Движок CBC (COIN-OR CDC(Linear solver)) вполне достаточен для решения любых линейных задач.
Показанные в списке движки могут быть недоступны.
В версии надстройки «OpenSolver2.9.4_ AdvancedWin» имеются доступные по умолчанию Bonmin, Couenne, Nomad - движки нелинейной оптимизации.
Движок Gurobi будет доступен только если установить доступную версию этого движка с сайта производителя.
Движки с именем Neos… вызываются прямо из облачного сервиса, поэтому без подключения к интернет не работают.
Чтобы эта опция работала корректно, нужно в меню Model\Option\Email… указать свой регистрационный адрес на NEOS или любой действующий мэйл.
Время решения задачи с использованием движков Neos... удлиняется за счет связывания с облачным сервером.
После того, как все данные задачи внесены (модель построена), нажмите кнопку Save Model.
Затем запустите решение задачи.
Как запустить решение задачи в OpenSolver.
Для того, чтобы запустить оптимизацию нажмите кнопку Solve.
Либо полную, со всеми ограничениями, либо с игнорированием целых ограничений (Solve relaxation), что весьма удобно для пользователя.
Так как решение целочисленных задач оптимизации гораздо более длительно по времени, чем решение обычных задач линейной оптимизации,
то опция игнорировать целые ограничения существенно сокращает время расчетов.
Поэтому имеет смысл сначала попробовать решить задачу «Поиском решения» или другим движком оптимизации без условия целочисленности, а затем, в случае успеха, пробовать решать задачу с целочисленными ограничениями.
Команда Show/Hide Model подсвечивает или снимает подсветку диапазонов данных, фигурирующих в установках модели.
Собственно, подсветка не особенно удобна, поскольку накрывает данные полупрозрачными фигурами, блокируя их изменение с клавиатуры.
Представляется более простым самостоятельно выделять цветом «играющие» диапазоны ячеек.
Но для контроля введенных параметров опция может быть полезна.
Команда Quick solve позволяет быстро провести оптимизацию, если в данных произошли небольшие изменения.
Команда OpenSolver разворачивает список возможных технических отчетов об оптимизации (лог результатов со временем счета, ошибки и проч…).
Следует отметить, что надстройка OpenSolver подхватывает и показывает сохраненные установки «Поиска решения», кроме технических.
Так как применение надстройкой облачных сервисов оптимизации не отличается от использования встроенных движков, надстройка позволяет использовать облачные сервисы оптимизации так же легко, как и локальный инструмент.
Отчет об устойчивости в OpenSolver.
Отчет об устойчивости выглядит и формируется практически так же, как в «Поиске решения».
С тем отличием, что в отчете «Поиска решения» ограничения, наложенные прямо на переменные, не отображаются вообще,
а в OpenSolver – отображаются в таблице Constraints.
Здесь приведен отчет об устойчивости для решения кейса Кондитерская фабрика Алиса,
в котором задано условие: минимальный объем производства всех конфет должен быть не ниже 5000 кг.
По этому отчету можно понять, что увеличение нижней границы производства для «Райского вкуса» до 5000+30674,8 кг будет сопровождаться потерями
в прибыли 144,27 руб на каждый дополнительный кг. Если нижнюю границу поднять выше, до 50 тыс кг, например, теневая цена ограничения возрастет (по модулю).
Google Docs
Существует вариант надстройки OpenSolver для популярных облачных таблиц из Google Docs.
1
Откройте список приложений Google
например, в Chrome/Сервисы и кликнете Таблицы
2
Загрузите ваш файл
Для этого:
— На панели Таблицы создайте пустой файл
После этого появится новая таблица.
— Нажмите команды Файл и Импортировать
Откроется панель Импорт.
— На панели Импорт кликните Загрузка
Теперь вы можете либо перетащить мышкой свой файл, либо выбрать его через кнопку Выбрать файл на устройстве.
3
Подключите OpenSolver
Для этого:
— В окне Новая таблица или в окне с вашим файлом нажмите команды Дополнения и Установить дополнения
— Появится окно Google Workspace Marketplace. Наберите в строке Поиск, начало названия нужной программы open и в выпадающем списке выберите OpenSolver
— После этого поиск выдаст ярлык программы OpenSolver.
— Кликните по ярлыку программы OpenSolver. Появится новое окно, в котором нажмите кнопку Установить
После этого OpenSolver будет установлен после вашей автроризации в Google.
4
Запустите OpenSolver
Для этого:
— В меню Дополнения выберите OpenSolver, а затем Open sidebar
5
Работа с OpenSolver
Окно OpenSolver в Таблицах GoogleDocs внешне мало чем, отличается от штатного интерфейса OpenSolver.
Однако, в нем сначала нужно выделить диапазон ячеек, а потом нажать кнопку Add или Update у нужного окошка ввода.
В этой надстройке также имеется возможность выбора варианта оптимизатора. В ней, в том числе, можно выбрать один из оптимизаторов с сайта NEOS.
Движок оптимизации Google Apps Script Linear Optimization Service,который используется по умолчанию, позволяет решать довольно большие задачи (тысячи переменных).
Однако, оптимизация проходит довольно медленно. Поэтому возможность использования облачного оптимизатора NEOS COIN-OR Cbc может оказаться полезной.
Необходимо отметить, что движок Satalia(последний в списке) требует подписки.
5
Ограничения OpenSolver в Таблицах GoogleDocs
Установки OpenSolver for Google Sheet запоминаются и сохраняются для каждой страницы документа google-таблиц.
Можно предположить, что облачный сервис Google Docs постепенно улучшит свой оптимизатор до лучших образцов, но пока в нем отсутствуют:
возможность нелинейной оптимизации;
возможность целочисленной оптимизации;
отчета о чувствительности.
Все вычисления инструментом Таблицы GoogleDocs производятся на стороне клиента, т.е. на вашем компьюторе.
Впрочем, наличие даже самого простого инструмента оптимизации в Таблицах Google – замечательно полезная вещь.
LibreOffice и OpenOffice
LibreOffice и OpenOffice (libreoffice.org, openoffice.org) -
это родственные проекты бесплатных кроссплатформенных аналогов MS Office, ответвившиеся от одного корня и потому очень схожие.
Эти программы:
открывают файлы MS Excel;
сохраняют файлы в формате MS Excel;
cодержат движок оптимизации Решатель, являющийся в значительной степени аналогом «Поиска решения», но существенно менее проработан;
не имеют специальных лимитов по числу переменных и ограничений.
Решатель находится по адресу Calc/Сервис/Решатель.
В Решателе LibreOffice имеются и нелинейные движки оптимизации, в OpenOffice – только движок линейной оптимизации.
Отчета о чувствительности нет в обоих Решателях.
Несмотря на очевидные недостатки и тот и другой Решатели могут быть использованы
для поиска оптимального решения в задаче с большим числом переменных.
Причем, сам файл может быть сформирован в Excel, а потом открыт в Calc\LibreOffice, например,
оптимизирован Решателем и сохранен в том же формате Excel.
В бесплатных аналогах Excel имеются не все функции MS Excel, но актуальные при оптимизации функции присутствуют.
К глубокому прискорбию, установки задачи, сделанные в Решателе, не сохраняются при закрытии файла
и в следующий раз их приходится задавать вновь.
Во-вторых, имеет смысл запросить файл листинга выполненного задания
В-третьих, укажите адрес электронной почты, на который нужно прислать результаты и щелкнете 
