Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

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

라이브 스크립트 열기

이 예제에서는 혼합 정수 선형 문제를 푸는 방법을 보여줍니다. 이 예제는 복잡하지 않지만, 문제 기반 접근법을 사용하여 문제를 정식화하는 일반적인 단계를 보여줍니다. 이 예제를 보여주는 비디오는 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에서 확인할 수 있습니다.

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

IngotWeightinTons%Carbon%MolybdenumCostTon1553$3502343$3303454$3104634$280

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

Alloy%Carbon%MolybdenumCostTon186$500277$450368$400Scrap39$100

문제 정식화하기

문제를 정식화하려면 먼저 제어 변수를 결정해야 합니다. 주괴 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톤을 구입하십시오.

관련 항목