이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.
혼합 정수 선형 계획법 기본 사항: 문제 기반
이 예제에서는 혼합 정수 선형 문제를 푸는 방법을 보여줍니다. 이 예제는 복잡하지 않지만, 문제 기반 접근법을 사용하여 문제를 정식화하는 일반적인 단계를 보여줍니다. 이 예제를 보여주는 비디오는 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에서 확인할 수 있습니다.
네 가지 강철 주괴를 구매할 수 있습니다. 각 주괴 중 하나만 사용할 수 있습니다.
세 가지 등급의 합금강과 한 가지 등급의 고철강을 구매할 수 있습니다. 합금강과 고철강은 소수점 단위의 수량으로 구매할 수 있습니다.
문제 정식화하기
문제를 정식화하려면 먼저 제어 변수를 결정해야 합니다. 주괴 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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.
해를 봅니다.
sol.ingots
ans = 4×1
1
1
0
1
sol.alloys
ans = 3×1
7.0000
0.5000
0
sol.scrap
ans = 3.5000
fval
fval = 8495
최적의 구매 비용은 $8,495입니다. 주괴 1, 2, 4를 구입하되, 주괴 3은 구입하지 말고, 합금강 1은 7.25톤, 합금강 3은 0.25톤, 고철강은 3.5톤을 구입하십시오.