Алгоритм решения задач оптимизации¶
В данном примере мы рассмотрим стандартный алгоритм решения задач оптимизации с помощью библиотеки JuMP.
JuMP.jl – это библиотека с открытым исходным кодом. В этой библиотеке реализован язык алгебраического моделирования, позволяющий пользователям формулировать и решать широкий спектр задач оптимизации, применяя различные решатели.
Установка библиотек¶
Если в вашем окружении не установлена последняя версия пакета JuMP, раскомментируйте и запустите ячейку ниже:
#Pkg.add("JuMP");
Для запуска новой версии библиотеки после завершения установки нажмите на кнопку «Личный кабинет»:
Затем нажмите на кнопку «Стоп»:
Перезапустите сессию нажатием кнопки «Старт Engee»:
Алгоритм решения задачи¶
Алгоритм решения оптимизационной задачи с помощью JuMP включает в себя несколько систематических шагов – от формулировки задачи до получения и интерпретации результатов. Вот стандартный алгоритм решения задачи:
- подключение библиотеки
JuMP, - выбор и подключение библиотеки решателя,
- создание оптимизационной задачи,
- объявления переменных,
- формулировка целевой функции,
- формулировка условия,
- решение задачи,
- вывод результатов,
- анализ результатов.
Описание задачи¶
В данном примере мы найдем значения переменных x и y, которые приведут к наименьшему возможному значению линейной целевой функции: $$F = 13x + 22y \rightarrow min$$ с учетом следующих условий: $$3x + 8y >= 20 Условие 1$$ $$6x + 10y <= 100 Условие 2$$ Мы также обозначим следующие границы значений переменных x и y: $$x >= 1$$ $$0 <= y <= 20$$
Решение задачи¶
Подключите библиотеку JuMP:
using JuMP;
В данном примере мы используем библиотеку решателя HiGHS.jl. Подключите библиотеку HiGHS:
using HiGHS;
Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:
optimization_problem = Model(HiGHS.Optimizer)
Используйте макрос @variable для определения переменных решения. Укажите границы значений переменных x и y:
@variable(optimization_problem, x >= 1);
@variable(optimization_problem, 0 <= y <= 20);
Задайте целевую функцию, подлежащую оптимизации, с помощью макроса @objective:
@objective(optimization_problem, Min, 13x + 22y);
Задайте первое условие решения оптимизационной задачи с помощью макроса @constraint:
@constraint(optimization_problem, c1, 3x + 8y >= 20)
Задайте второе условие решения оптимизационной задачи:
@constraint(optimization_problem, c2, 6x + 10y <= 100)
Решите оптимизационную задачу:
optimize!(optimization_problem)
Выведите найденные оптимальные значения x и y:
println("Оптимальное значение x: ", value(x))
println("Оптимальное значение y: ", value(y))
Выведите статус результата работы решателя:
status = termination_status(optimization_problem)
println("Статус: ", status)
Статус OPTIMAL означает, что решатель нашел глобально-оптимальное решение задачи.
Заключение¶
В данном примере мы разобрали алгоритм решения базовой задачи оптимизации с помощью библиотек JuMP и HiGHS. Библиотека JuMP позволяет сформулировать задачу оптимизации, задать условия и решить её с помощью решателя, определенного пользователем. Вы можете ознакомиться с практическими применениями библиотеки JuMP в нашем курсе Основы оптимизации.