Смешано-целочисленные линейные основы программирования: основанный на проблеме

В этом примере показано, как решить смешано-целочисленную линейную программу. Пример не является комплексным, но он показывает типичные шаги в формулировке проблемы для подхода, основанного на проблеме. Для видео, показывающего этот пример, смотрите, Решают Смешано-целочисленную Задачу линейного программирования с помощью Моделирования Оптимизации.

Для основанного на решателе подхода к этой проблеме смотрите Смешано-целочисленные Линейные Основы Программирования: основанный на решателе.

Описание проблемы

Вы хотите смешать стали с различными химическими составами, чтобы получить 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Стоимость/Тонна
1553$350
2343$330
3454$310
4634$280

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

Сплав%Carbon%MolybdenumСтоимость/Тонна
186$500
277$450
368$400
Фрагмент39$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 тонны стали фрагмента.

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте