이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

혼합 정수 선형 계획법 기본 사항: 솔버 기반

이 예제에서는 혼합 정수 선형 계획을 푸는 방법을 보여줍니다. 이 예제는 복잡하지 않지만, intlinprog의 구문으로 문제를 정식화하는 일반적인 단계를 보여줍니다.

이 문제에 대한 문제 기반 접근법은 Mixed-Integer Linear Programming Basics: Problem-Based 항목을 참조하십시오.

문제 설명

다양한 화학 성분과 강철을 혼합하여 특정 화학 성분이 포함된 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에서 발췌한 것입니다. 이에 대한 초록은 http://interfaces.journal.informs.org/content/7/2/39.abstract에서 확인할 수 있습니다.

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

주괴중량(단위: 톤)탄소 비율(%)몰리브덴 비율(%)톤당 비용
1553$350
2343$330
3454$310
4634$280

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

합금강탄소 비율(%)몰리브덴 비율(%)톤당 비용
186$500
277$450
368$400
고철강39$100

문제를 정식화하려면 먼저 제어 변수를 결정해야 합니다. 주괴 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에서 정수가 되도록 설정하고 하한과 상한을 각각 01로 지정해야 합니다.

선형 부등식 제약 조건이 없으므로 Ab는 빈 행렬([])입니다.

등식 제약 조건은 세 개입니다. 첫 번째는 총 중량이 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,[],[],Aeq,beq,lb,ub);

해를 봅니다.

x,fval
x =

    1.0000
    1.0000
         0
    1.0000
    7.2500
         0
    0.2500
    3.5000


fval =

   8.4950e+03

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

intcon = []을 설정하여 정수 제약 조건 없이 문제를 푸는 경우 어떠한 효과가 있는지 확인해 보십시오. 해가 다르며 합당하지 않습니다. 주괴는 일부만 구매할 수 없기 때문입니다.