Main Content

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

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

이 예제에서는 혼합 정수 선형 문제를 푸는 방법을 보여줍니다. 이 예제는 복잡하지 않지만, 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에서 확인할 수 있습니다.

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

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

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

Alloy%Carbon%MolybdenumCostTon186$500277$450368$400Scrap39$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는 빈 행렬([])입니다.

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 = []을 설정하여 정수 제약 조건 없이 문제를 푸는 경우 어떠한 효과가 있는지 확인해 보십시오. 해가 다르며 현실적이지 않습니다. 주괴는 일부만 구매할 수 없기 때문입니다.

관련 항목