В этом примере показано, как решить смешано-целочисленную линейную программу. Пример не является комплексным, но он показывает типичные шаги в формулировке проблемы для подхода, основанного на проблеме. Для видео, показывающего этот пример, смотрите, Решают Смешано-целочисленную Задачу линейного программирования с помощью Моделирования Оптимизации.
Для основанного на решателе подхода к этой проблеме смотрите Смешано-целочисленные Линейные Основы Программирования: основанный на решателе.
Вы хотите смешать стали с различными химическими составами, чтобы получить 25 тонн стали с определенным химическим составом. Результат должен иметь 5%-й углерод и 5%-й молибден в развес, означая 25 tons*5% = 1,25 тонны углерода и 1,25 тонны молибдена. Цель состоит в том, чтобы минимизировать стоимость для смешивания стали.
Эта проблема взята от Карла-Хенрика Вестерберга, Бенгта Бйорклюнда и Эскила Хултмена, “Приложение Частично-целочисленного программирования в шведском Сталелитейном заводе”. Издание 7 февраля 1977 интерфейсов, стр № 2 39–43, чей краткий обзор в http://interfaces.journal.informs.org/content/7/2/39.abstract
.
Четыре слитка стали доступны для покупки. Только один из каждого слитка доступен.
Слиток | Вес в тоннах | %Carbon | %Molybdenum | Стоимость/Тонна |
---|---|---|---|---|
1 | 5
| 5
| 3
| $350 |
2 | 3
| 4
| 3
| $330 |
3 | 4
| 5
| 4
| $310 |
4 | 6
| 3
| 4
| $280 |
Три сорта легированной стали доступны для покупки и одного сорта стали фрагмента. Сплавьте и фрагментируйте стали, может быть куплен в дробных суммах.
Сплав | %Carbon | %Molybdenum | Стоимость/Тонна |
---|---|---|---|
1 | 8
| 6
| $500 |
2 | 7
| 7
| $450 |
3 | 6
| 8
| $400 |
Фрагмент | 3
| 9
| $100 |
Чтобы сформулировать проблему, сначала выберите контрольные переменные. Возьмите переменную ingots(1) = 1
означать, что вы покупаете слиток 1, и ingots(1) = 0
означать, что вы не покупаете слиток. Точно так же переменные ingots(2)
через ingots(4)
бинарные переменные, указывающие, покупаете ли вы слитки 2 - 4.
Переменные alloys(1)
через alloys(3)
количества в тоннах сплавов 1, 2, и 3, что вы покупаете. scrap
количество в тоннах стали фрагмента, которую вы покупаете.
Создайте задачу оптимизации и переменные.
steelprob = optimproblem; ingots = optimvar('ingots',4,'Type','integer','LowerBound',0,'UpperBound',1); alloys = optimvar('alloys',3,'LowerBound',0); scrap = optimvar('scrap','LowerBound',0);
Создайте выражения для затрат, сопоставленных с переменными.
weightIngots = [5,3,4,6]; costIngots = weightIngots.*[350,330,310,280]; costAlloys = [500,450,400]; costScrap = 100; cost = costIngots*ingots + costAlloys*alloys + costScrap*scrap;
Включайте стоимость как целевую функцию в проблеме.
steelprob.Objective = cost;
Существует три ограничения равенства. Первое ограничение состоит в том, что общая масса составляет 25 тонн. Вычислите вес стали.
totalWeight = weightIngots*ingots + sum(alloys) + scrap;
Второе ограничение состоит в том, что вес углерода составляет 5% 25 тонн или 1,25 тонн. Вычислите вес углерода в стали.
carbonIngots = [5,4,5,3]/100; carbonAlloys = [8,7,6]/100; carbonScrap = 3/100; totalCarbon = (weightIngots.*carbonIngots)*ingots + carbonAlloys*alloys + carbonScrap*scrap;
Третье ограничение состоит в том, что вес молибдена составляет 1,25 тонны. Вычислите вес молибдена в стали.
molybIngots = [3,3,4,4]/100; molybAlloys = [6,7,8]/100; molybScrap = 9/100; totalMolyb = (weightIngots.*molybIngots)*ingots + molybAlloys*alloys + molybScrap*scrap;
Включайте ограничения в проблему.
steelprob.Constraints.conswt = totalWeight == 25; steelprob.Constraints.conscarb = totalCarbon == 1.25; steelprob.Constraints.consmolyb = totalMolyb == 1.25;
Теперь, когда у вас есть все входные параметры, вызовите решатель.
[sol,fval] = solve(steelprob);
Solving problem using intlinprog. LP: Optimal objective value is 8125.600000. Cut Generation: Applied 3 mir cuts. Lower bound is 8495.000000. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
Просмотрите решение.
sol.ingots sol.alloys sol.scrap fval
ans = 1.0000 1.0000 0 1.0000 ans = 7.2500 0 0.2500 ans = 3.5000 fval = 8.4950e+03
Оптимальная покупка стоит 8 495$. Купите слитки 1, 2, и 4, но не 3, и купите 7,25 тонн сплава 1, 0,25 тонны сплава 3 и 3,5 тонны стали фрагмента.