Документация Engee
Notebook

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

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

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

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

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

In [ ]:
Pkg.add(["JuMP", "HiGHS"])

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

Алгоритм решения оптимизационной задачи с помощью 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:

In [ ]:
using JuMP;

В данном примере мы используем библиотеку решателя HiGHS.jl. Подключите библиотеку HiGHS:

In [ ]:
using HiGHS;

Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:

In [ ]:
optimization_problem = Model(HiGHS.Optimizer)
Out[0]:
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Используйте макрос @variable для определения переменных решения. Укажите границы значений переменных x и y:

In [ ]:
@variable(optimization_problem, x >= 1);
@variable(optimization_problem, 0 <= y <= 20);

Задайте целевую функцию, подлежащую оптимизации, с помощью макроса @objective:

In [ ]:
@objective(optimization_problem, Min, 13x + 22y);

Задайте первое условие решения оптимизационной задачи с помощью макроса @constraint:

In [ ]:
@constraint(optimization_problem, c1, 3x + 8y >= 20)
Out[0]:
$$ 3 x + 8 y \geq 20 $$

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

In [ ]:
@constraint(optimization_problem, c2, 6x + 10y <= 100)
Out[0]:
$$ 6 x + 10 y \leq 100 $$

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

In [ ]:
optimize!(optimization_problem)
Running HiGHS 1.11.0 (git hash: 364c83a51e): Copyright (c) 2025 HiGHS under MIT licence terms
LP   has 2 rows; 2 cols; 4 nonzeros
Coefficient ranges:
  Matrix [3e+00, 1e+01]
  Cost   [1e+01, 2e+01]
  Bound  [1e+00, 2e+01]
  RHS    [2e+01, 1e+02]
Presolving model
2 rows, 2 cols, 4 nonzeros  0s
2 rows, 2 cols, 4 nonzeros  0s
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
P-D objective error :  0.0000000000e+00
HiGHS run time      :          0.00

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

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

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

In [ ]:
task_status = termination_status(optimization_problem)
println("Статус: ", task_status)
Статус: OPTIMAL

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

Заключение

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