Решения задач смешанного целочисленного линейного программирования¶
В этом примере показано, как решить задачу смешанного целочисленного линейного программирования (англ. Mixed Integer Linear Programming, MILP). Здесь приведены типичные шаги по формулированию проблемы с использованием проблемно-ориентированного подхода.
Установка библиотек¶
Если в вашем окружении не установлена последняя версия пакета JuMP, раскомментируйте и запустите ячейку ниже:
#Pkg.add("JuMP");
Для запуска новой версии библиотеки после завершения установки нажмите на кнопку «Личный кабинет»:
Затем нажмите на кнопку «Стоп»:
Перезапустите сессию нажатием кнопки «Старт Engee»:
Описание задачи¶
Вам необходимо смешать стали с различным химическим составом, чтобы произвести 25 тонн стали с определенным химическим составом. В результате должна получиться сталь, содержащая 5% углерода и 5% молибдена от общего веса, что означает 1,25 тонны углерода и 1,25 тонны молибдена.
Цель оптимизационной задачи состоит в том, чтобы минимизировать затраты на смешивание стали.
Для закупки доступны четыре различных слитка стали. При этом вы можете купить только один слиток каждого вида.
| Слиток | Вес в тоннах | % углерода | % молибдена | Стоимость за тонну |
|---|---|---|---|---|
| 1 | 5 | 5 | 3 | $350 |
| 2 | 3 | 4 | 3 | $330 |
| 3 | 4 | 5 | 4 | $310 |
| 4 | 6 | 3 | 4 | $280 |
В продаже также имеются три сорта легированной стали и один сорт стального лома. Легированные стали и лом можно приобрести в дробных количествах.
| Сплав | % углерода | % молибдена | Стоимость за тонну |
|---|---|---|---|
| 1 | 8 | 6 | $500 |
| 2 | 7 | 7 | $450 |
| 3 | 6 | 8 | $400 |
| Лом | 3 | 9 | $100 |
Подключение библиотек¶
Подключите библиотеку JuMP:
using JuMP;
Подключите библиотеку решателя GLPK:
using GLPK;
Создание задачи оптимизации¶
Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:
steel_prob = Model(GLPK.Optimizer)
Создайте переменную ingots, содержащую четыре значения (по количеству доступных для закупки слитков). Так как слитки не могут быть закуплены в дробных количествах, укажите тип переменной Int. Нижняя граница для всех переменных будет равна 0, ведь мы не можем закупить отрицательное количество. Каждый из слитков доступен в единственном экземпляре, поэтому для данной переменной укажите верхнюю границу 1.
@variable(steel_prob, ingots[1:4], Int; lower_bound = 0, upper_bound = 1);
Создайте переменную alloys, содержащую три значения (по количеству доступных для закупки сплавов). Стальной лом мы выделим в отдельную переменную. Так как сплавы могут быть закуплены в дробных количествах, указывать тип переменной не нужно.
@variable(steel_prob, alloys[1:3], lower_bound = 0);
Создайте переменную scrap для стального лома. Поскольку лом может быть закуплен в дробных количествах, указывать тип переменной не нужно.
@variable(steel_prob, scrap, lower_bound = 0);
Так как вес каждого из слитков отличается, для расчета затрат на закупку слитков нужно сначала создать переменную weightIngots. Рассчитайте затраты на каждый из компонентов и создайте переменную cost, содержащую общую сумму затрат на закупку компонентов. В рамках решения нашей задачи мы найдем минимальное значение этой переменной.
weightIngots = [5,3,4,6];
costIngots = weightIngots.*[350,330,310,280];
costAlloys = [500,450,400];
costScrap = 100;
cost = sum(costIngots.*ingots) + sum(costAlloys.*alloys) + sum(costScrap*scrap)
Создайте целевую функцию для минимизации затрат для решения нашей оптимизационной задачи:
@objective(steel_prob, Min, cost)
Создайте переменную totalWeight, содержащую общий вес всех компонентов:
totalWeight = sum(weightIngots.*ingots) + sum(alloys) + scrap
Рассчитайте общую массу углерода в стали:
carbonIngots = [5,4,5,3]/100;
carbonAlloys = [8,7,6]/100;
carbonScrap = 3/100;
totalCarbon = sum((weightIngots.*carbonIngots).*ingots) + sum(carbonAlloys.*alloys) + sum(carbonScrap.*scrap)
Рассчитайте общую массу молибдена в стали:
molybIngots = [3,3,4,4]/100;
molybAlloys = [6,7,8]/100;
molybScrap = 9/100;
totalMolyb = sum((weightIngots.*molybIngots).*ingots) + sum(molybAlloys.*alloys) + sum(molybScrap.*scrap)
Формулировка условий¶
Задайте первое условие решения оптимизационной задачи, что общий вес полученной стали должен составлять 25 тонн:
@constraint(steel_prob, C1, totalWeight == 25)
Задайте второе условие решения оптимизационной задачи, что общий вес углерода в полученной стали должен составлять 1,25 тонн:
@constraint(steel_prob, C2, totalCarbon == 1.25)
Задайте третье условие решения оптимизационной задачи, что общий вес молибдена в полученной стали должен составлять 1,25 тонн:
@constraint(steel_prob, C3, totalMolyb == 1.25)
Решение задачи¶
Решите оптимизационную задачу:
optimize!(steel_prob)
Проверьте, было ли найдено оптимальное решение:
if !is_solved_and_feasible(steel_prob)
error("Solver did not find an optimal solution")
end
Сохраните интересующие значения в переменных. Вы можете использовать функцию round, чтобы округлить избыточно точные значения.
ingots_value = value.(ingots);
alloys_value = round.(value.(alloys); digits = 3);
scrap_value = round(value.(scrap); digits = 3);
fval = objective_value(steel_prob);
Выведите результаты оптимизации:
println("Ingots: ", ingots_value)
println("Alloys: ", alloys_value)
println("Scrap: ", scrap_value)
println("Objective Value: ", fval)
Оптимальная цена закупки $8495. Таким образом, следует закупить слитки 1, 2 и 4, но не 3. А также закупить 7,25 тонны сплава 1, 0,25 тонны сплава 3 и 3,5 тонны стального лома.
Заключение¶
В данном примере мы решили задачу смешанного целочисленного линейного программирования и нашли оптимальный комплект и количество компонентов для получения 25 тонн стали с необходимым химическим составом по минимальной цене.