혼합 정수 선형 계획법 기본 사항: 문제 기반

라이브 스크립트 열기

이 예제에서는 혼합 정수 선형 문제를 푸는 방법을 보여줍니다. 이 예제는 복잡하지 않지만, 문제 기반 접근법을 사용하여 문제를 정식화하는 일반적인 단계를 보여줍니다. 이 예제를 보여주는 비디오는Solve a Mixed-Integer Linear Programming Problem using Optimization Modeling을 참조하십시오.

이 문제에 대한 솔버 기반 접근법은혼합 정수 선형 계획법 기본 사항: 솔버 기반항목을참조하십시오。

문제 설명

다양한화학성분과강철을혼합하여특정화학성분이포함된25톤짜리 강철을 얻으려 한다고 가정하겠습니다. 결과는 중량을 기준으로 5% 탄소와 5% 몰리브덴을 포함해야 하며, 이는 25톤*5% = 탄소 1.25톤 및 몰리브덴 1.25톤을 의미합니다. 여기서의 목적은 강철을 혼합하는 데 드는 비용을 최소화하는 것입니다.

이 문제는 칼-헨릭 웨스터버그(Carl-Henrik Westerberg), 벵트 비요클룬드(Bengt Bjorklund), 에스킬 훌트먼(Eskil Hultman)의 “An Application of Mixed Integer Programming in a Swedish Steel Mill.” Interfaces February 1977 Vol. 7, No. 2 pp. 39–43에서 발췌한 것입니다. 이에 대한 초록은https://doi.org/10.1287/inte.7.2.39에서 확인할 수 있습니다.

네 가지 강철 주괴를 구매할 수 있습니다. 각 주괴 중 하나만 사용할 수 있습니다.

$\begin{array}{ccccc} I n g o t & W e i g h t i n T o n s & % C a r b o n & % M o l y b d e n u m & \frac{C o s t}{T o n} \\ 1 & 5 & 5 & 3 & $ 350 \\ 2 & 3 & 4 & 3 & $ 330 \\ 3 & 4 & 5 & 4 & $ 310 \\ 4 & 6 & 3 & 4 & $ 280 \end{array}$

세 가지 등급의 합금강과 한 가지 등급의 고철강을 구매할 수 있습니다. 합금강과 고철강은 소수점 단위의 수량으로 구매할 수 있습니다.

$\begin{array}{cccc} A l l o y & % C a r b o n & % M o l y b d e n u m & \frac{C o s t}{T o n} \\ 1 & 8 & 6 & $ 500 \\ 2 & 7 & 7 & $ 450 \\ 3 & 6 & 8 & $ 400 \\ S c r a p & 3 & 9 & $ 100 \end{array}$

문제 정식화하기

문제를 정식화하려면 먼저 제어 변수를 결정해야 합니다. 주괴1을 구매한다는 것을 나타내려면 변수ingots(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;

문제에 3개의 등식 제약 조건이 있습니다. 첫 번째 제약 조건은 총 중량이 25톤이라는 것입니다. 강철의 중량을 계산합니다.

totalWeight = weightIngots*ingots + sum(alloys) + scrap;

두 번째 제약 조건은 탄소의 중량이 25톤의 5%, 즉 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

ans =4×11.0000 1.0000 0 1.0000

sol.alloys

ans =3×17.2500 0 0.2500

sol.scrap

ans = 3.5000

fval

fval = 8.4950e+03

최적의 구매 비용은 $8,495입니다. 주괴1,2,4를 구입하되, 주괴3은 구입하지 말고, 합금강1은 7.25톤, 합금강3은 0.25톤, 고철강은 3.5톤을 구입하십시오.

혼합 정수 선형 계획법 기본 사항: 문제 기반

문제 설명

문제 정식화하기

문제 풀기

관련 항목