이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.
혼합 정수 선형 계획법 기본 사항: 솔버 기반
이 예제에서는 혼합 정수 선형 문제를 푸는 방법을 보여줍니다. 이 예제는 복잡하지 않지만, intlinprog
의 구문으로 문제를 정식화하는 일반적인 단계를 보여줍니다.
이 문제에 대한 문제 기반 접근법은 혼합 정수 선형 계획법 기본 사항: 문제 기반 항목을 참조하십시오.
문제 설명
다양한 화학 성분과 강철을 혼합하여 특정 화학 성분이 포함된 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에서 확인할 수 있습니다.
네 가지 강철 주괴를 구매할 수 있습니다. 각 주괴 중 하나만 사용할 수 있습니다.
세 가지 등급의 합금강과 한 가지 등급의 고철강을 구매할 수 있습니다. 합금강과 고철강은 소수점 단위의 수량으로 구매할 수 있습니다.
문제를 정식화하려면 먼저 제어 변수를 결정해야 합니다. 주괴 1을 구매한다는 것을 나타내려면 변수 x(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)
첫 번째 인수(f
)부터 마지막 인수(ub
)까지 intlinprog
에 대한 입력값을 만듭니다.
f
는 비용 계수의 벡터입니다. 주괴의 비용을 나타내는 계수는 주괴 중량에 톤당 비용을 곱한 값입니다.
f = [350*5,330*3,310*4,280*6,500,450,400,100];
정수 변수는 처음 4개입니다.
intcon = 1:4;
팁: 이진 변수를 지정하려면 변수를 intcon
에서 정수가 되도록 설정하고 하한과 상한을 각각 0
과 1
로 지정해야 합니다.
문제에 선형 부등식 제약 조건이 없으므로 A
와 b
는 빈 행렬([]
)입니다.
A = []; b = [];
문제에 3개의 등식 제약 조건이 있습니다. 첫 번째는 총 중량이 25톤이라는 것입니다.
5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) + x(6) + x(7) + x(8) = 25
두 번째 제약 조건은 탄소의 중량이 25톤의 5%, 즉 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];
각 변수의 하한은 0입니다. 정수 변수의 상한은 1입니다.
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);
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 3 rows, 8 cols, 24 nonzeros 3 rows, 8 cols, 18 nonzeros Solving MIP model with: 3 rows 8 cols (4 binary, 0 integer, 0 implied int., 4 continuous) 18 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 8125.6 inf inf 0 0 0 4 0.0s R 0 0 0 0.00% 8495 8495 0.00% 5 0 0 5 0.0s Solving report Status Optimal Primal bound 8495 Dual bound 8495 Gap 0% (tolerance: 0.01%) Solution status feasible 8495 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.01 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 5 (total) 0 (strong br.) 1 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
해를 봅니다.
x,fval
x = 8×1
1.0000
1.0000
0
1.0000
7.2500
0
0.2500
3.5000
fval = 8495
최적의 구매 비용은 $8,495입니다. 주괴 1, 2, 4를 구입하되, 주괴 3은 구입하지 말고, 합금강 1은 7.25톤, 합금강 3은 0.25톤, 고철강은 3.5톤을 구입하십시오.
intcon = []
을 설정하여 정수 제약 조건 없이 문제를 푸는 경우 어떠한 효과가 있는지 확인해 보십시오. 해가 다르며 현실적이지 않습니다. 주괴는 일부만 구매할 수 없기 때문입니다.