Этот пример показывает, как решить смешано-целочисленную линейную программу. Пример не является комплексным, но он показывает типичные шаги в формулировке проблемы в синтаксисе для intlinprog
.
Для основанного на проблеме подхода к этой проблеме смотрите Смешано-целочисленные Линейные Основы Программирования: основанный на проблеме.
Вы хотите смешать стали с различными химическими составами, чтобы получить 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 |
Чтобы сформулировать проблему, сначала выберите контрольные переменные. Возьмите переменную x(1) = 1
, чтобы означать, что вы покупаете слиток 1, и x(1) = 0
, чтобы означать, что вы не покупаете слиток. Точно так же переменные x(2)
через x(4)
являются бинарными переменными, указывающими, что вы покупаете слитки 2 - 4.
Переменные x(5)
через x(7)
являются количествами в тоннах сплавов 1, 2, и 3 вы покупаете, и x(8)
является количеством стали фрагмента, которую вы покупаете.
Сформулируйте проблему путем определения входных параметров для intlinprog
. Соответствующий синтаксис intlinprog
следующие.
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Создайте входные параметры для intlinprog
от первого (f
) через последний (ub
).
f
является вектором коэффициентов стоимости. Коэффициенты, представляющие затраты на слитки, являются временами весов в слитках их стоимость на тонну.
f = [350*5,330*3,310*4,280*6,500,450,400,100];
Целочисленные переменные являются первыми четырьмя.
intcon = 1:4;
Чтобы задать бинарные переменные, установите переменные быть целыми числами в intcon
и давать им нижнюю границу 0
и верхнюю границу 1
.
Нет никаких линейных ограничений неравенства, таким образом, A
и b
являются пустыми матрицами ([]
).
Существует три ограничения равенства. Прежде всего, общая масса составляет 25 тонн.
5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) + x(6) + x(7) + x(8) = 25
.
Второе ограничение состоит в том, что вес углерода составляет 5% 25 тонн или 1,25 тонн.
5*0.05*x (1) + 3*0.04*x (2) + 4*0.05*x (3) + 6*0.03*x (4)
.
+ 0.08*x (5) + 0.07*x (6) + 0.06*x (7) + 0.03*x (8) = 1.25
Третье ограничение состоит в том, что вес молибдена составляет 1,25 тонны.
5*0.03*x (1) + 3*0.03*x (2) + 4*0.04*x (3) + 6*0.04*x (4)
.
+ 0.06*x (5) + 0.07*x (6) + 0.08*x (7) + 0.09*x (8) = 1.25
В матричной форме, Aeq*x = beq
, где
Aeq = [5,3,4,6,1,1,1,1; 5*0.05,3*0.04,4*0.05,6*0.03,0.08,0.07,0.06,0.03; 5*0.03,3*0.03,4*0.04,6*0.04,0.06,0.07,0.08,0.09]; beq = [25;1.25;1.25];
Каждая переменная ограничена ниже нулем. Целочисленные переменные ограничены выше одной.
lb = zeros(8,1); ub = ones(8,1); ub(5:end) = Inf; % No upper bound on noninteger variables
Теперь, когда у вас есть все входные параметры, вызовите решатель.
[x,fval] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
Просмотрите решение.
x,fval
x = 1.0000 1.0000 0 1.0000 7.2500 0 0.2500 3.5000 fval = 8.4950e+03
Оптимальная покупка стоит 8 495$. Купите слитки 1, 2, и 4, но не 3, и купите 7,25 тонн сплава 1, 0,25 тонны сплава 3 и 3,5 тонны стали фрагмента.
Установите intcon = []
видеть эффект решения проблемы без целочисленных ограничений. Решение отличается, и не разумно, потому что вы не можете купить часть слитка.