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

Вы хотите смешать стали с различными химическими составами для получения 25 тонн стали с определенным химическим составом. Результат должен иметь 5% углерода и 5% молибдена по весу, что означает 25 тонн * 5% = 1,25 тонн углерода и 1,25 тонн молибдена. Цель состоит в том, чтобы минимизировать затраты на смешивание стали.

Эта задача взята у Карла-Хенрика Вестерберга, Бенгта Бьорклунда и Эскиля Хультмана, «Применение смешанного целочисленного программирования на шведском металлургическом комбинате». Интерфейсы Февраль 1977 Vol. 7, № 2 pp. 39-43, аннотация которого находится в https://doi.org/10.1287/inte.7.2.39.

Для покупки доступны четыре слитка стали. Доступен только один из слитков.

Для покупки доступны три сорта легированной стали и один сорт металлолома. Сплав и лом стали можно приобрести в фракционных количествах.

Чтобы сформулировать задачу, сначала решите вопрос о переменных управления. Примите переменные   x(1) = 1 то есть вы покупаете слитки 1, и   x(1) = 0 означает, что вы не покупаете слиток. Точно так же переменные x(2) через x(4) являются двоичными переменными, указывающими, приобретаете ли вы слитки с 2 по 4.

Переменные x(5) через x(7) количество в тоннах сплавов 1, 2 и 3, которые вы покупаете, и x(8) количество металлолома, который вы покупаете.

Состав MATLAB ®

Сформулируйте задачу путем определения входов для 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 являются пустыми матрицами ([]).

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,A,b,Aeq,beq,lb,ub);

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).

Просмотрите решение.

x,fval

x = 8×1

    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 = [] увидеть эффект решения задачи без целочисленных ограничений. Решение отличается, и нереалистично, потому что вы не можете приобрести часть слитка.