Алгоритм решения задач оптимизации

В данном примере мы рассмотрим стандартный алгоритм решения задач оптимизации с помощью библиотеки JuMP.

JuMP.jl – это библиотека с открытым исходным кодом. В этой библиотеке реализован язык алгебраического моделирования, позволяющий пользователям формулировать и решать широкий спектр задач оптимизации, применяя различные решатели.

Установка библиотек

Если в вашем окружении не установлена последняя версия пакета JuMP, раскомментируйте и запустите ячейку ниже:

#Pkg.add("JuMP");

Для запуска новой версии библиотеки после завершения установки нажмите на кнопку «Личный кабинет»:

Затем нажмите на кнопку «Стоп»:

Перезапустите сессию нажатием кнопки «Старт Engee»:

Алгоритм решения задачи

Алгоритм решения оптимизационной задачи с помощью JuMP включает в себя несколько систематических шагов – от формулировки задачи до получения и интерпретации результатов. Вот стандартный алгоритм решения задачи:

1. подключение библиотеки JuMP,
2. выбор и подключение библиотеки решателя,
3. создание оптимизационной задачи,
4. объявления переменных,
5. формулировка целевой функции,
6. формулировка условия,
7. решение задачи,
8. вывод результатов,
9. анализ результатов.

Описание задачи

В данном примере мы найдем значения переменных 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)

A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Используйте макрос @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)

$$ 3 x + 8 y \geq 20 $$

Задайте второе условие решения оптимизационной задачи:

@constraint(optimization_problem, c2, 6x + 10y <= 100)

$$ 6 x + 10 y \leq 100 $$

Решите оптимизационную задачу:

optimize!(optimization_problem)

Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
2 rows, 2 cols, 4 nonzeros
2 rows, 2 cols, 4 nonzeros
Presolve : Reductions: rows 2(-0); columns 2(-0); elements 4(-0) - Not reduced
Problem not reduced by presolve: solving the LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     1.3000046544e+01 Pr: 1(17) 0s
          1     5.9750000000e+01 Pr: 0(0) 0s
Model   status      : Optimal
Simplex   iterations: 1
Objective value     :  5.9750000000e+01
HiGHS run time      :          0.00

Выведите найденные оптимальные значения x и y:

println("Оптимальное значение x: ", value(x))
println("Оптимальное значение y: ", value(y))

Оптимальное значение x: 1.0
Оптимальное значение y: 2.125

Выведите статус результата работы решателя:

status = termination_status(optimization_problem)
println("Статус: ", status)

Статус: OPTIMAL

Статус OPTIMAL означает, что решатель нашел глобально-оптимальное решение задачи.

Заключение

В данном примере мы разобрали алгоритм решения базовой задачи оптимизации с помощью библиотек JuMP и HiGHS. Библиотека JuMP позволяет сформулировать задачу оптимизации, задать условия и решить её с помощью решателя, определенного пользователем. Вы можете ознакомиться с практическими применениями библиотеки JuMP в нашем курсе Основы оптимизации.