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

linprog

선형 계획법 문제 풀기

구문

x = linprog(f,A,b)

x = linprog(f,A,b,Aeq,beq)

x = linprog(f,A,b,Aeq,beq,lb,ub)

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

x = linprog(problem)

[x,fval] = linprog(___)

[x,fval,exitflag,output] = linprog(___)

[x,fval,exitflag,output,lambda] = linprog(___)

설명

선형 계획법 솔버

다음으로 지정된 문제의 최솟값을 구합니다.

$$\underset{x}{\min }{f}^{T}x\text{ such that }\{\begin{array}{c}A\cdot x\le b,\\ Aeq\cdot x=beq,\\ lb\le x\le ub.\end{array}$$

f, x, b, beq, lb, ub는 벡터이고 A와 Aeq는 행렬입니다.

참고

linprog 솔버는 솔버 기반 접근법에만 적용됩니다. 문제 기반 접근법에는 solve를 사용하십시오. 두 가지 최적화 접근법에 대한 설명은 먼저 문제 기반 접근법 또는 솔버 기반 접근법 중 선택하기 항목을 참조하십시오.

x = linprog(f,A,b)는 최솟값 f'*x를 구합니다. 여기에는 A*x ≤ b라는 조건이 적용됩니다.

x = linprog(f,A,b,Aeq,beq)는 등식 제약 조건 Aeq*x = beq를 포함합니다. 부등식이 존재하지 않을 경우 A = [] 및 b = []을 설정하십시오.

x = linprog(f,A,b,Aeq,beq,lb,ub)는 해가 항상 범위 lb ≤ x ≤ ub 내에 있도록 설계 변수 x에 대한 하한 및 상한 집합을 정의합니다. 등식이 존재하지 않을 경우 Aeq = [] 및 beq = []을 설정하십시오.

참고

문제에 대해 지정된 입력값 범위에 모순이 있는 경우 출력값 fval은 []이 됩니다.

x = linprog(f,A,b,Aeq,beq,lb,ub,options)는 options로 지정된 최적화 옵션을 사용하여 최소화합니다. 이 옵션을 설정하려면 optimoptions를 사용하십시오.

x = linprog(problem)은 problem에 설명되어 있는 구조체인 problem의 최솟값을 구합니다.

mpsread를 사용하여 MPS 파일에서 problem 구조체를 가져올 수 있습니다. 또는 prob2struct를 사용하여 OptimizationProblem 객체에서 problem 구조체를 만들 수도 있습니다.

[x,fval] = linprog(___)는 임의의 입력 인수에 대해 해 x에서의 목적 함수 fun의 값을 반환합니다(fval = f'*x).

[x,fval,exitflag,output] = linprog(___)는 종료 조건을 설명하는 값 exitflag와 최적화 과정에 대한 정보가 포함된 구조체 output을 추가로 반환합니다.

[x,fval,exitflag,output,lambda] = linprog(___)는 추가로 해 x에서의 라그랑주 승수가 필드에 포함된 구조체 lambda를 반환합니다.

예제

선형 계획, 선형 부등식 제약 조건

선형 부등식으로 정의된 단순한 선형 계획 문제를 풉니다.

이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.

$$x(1)+x(2)\le 2$$

$$x(1)+x(2)/4\le 1$$

$$x(1)-x(2)\le 2$$

$$-x(1)/4-x(2)\le 1$$

$$-x(1)-x(2)\le -1$$

$$-x(1)+x(2)\le 2.$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

목적 함수 $$-x(1)-x(2)/3$$을 사용합니다.

f = [-1 -1/3];

선형 계획 문제를 풉니다.

x = linprog(f,A,b)

Optimal solution found.

x = 2×1

    0.6667
    1.3333

선형 부등식 및 선형 등식이 있는 선형 계획

선형 부등식 및 선형 등식으로 정의된 단순한 선형 계획 문제를 풉니다.

이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.

$$x(1)+x(2)\le 2$$

$$x(1)+x(2)/4\le 1$$

$$x(1)-x(2)\le 2$$

$$-x(1)/4-x(2)\le 1$$

$$-x(1)-x(2)\le -1$$

$$-x(1)+x(2)\le 2.$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

선형 등식 제약 조건 $$x(1)+x(2)/4=1/2$$을 사용합니다.

Aeq = [1 1/4];
beq = 1/2;

목적 함수 $$-x(1)-x(2)/3$$을 사용합니다.

f = [-1 -1/3];

선형 계획 문제를 풉니다.

x = linprog(f,A,b,Aeq,beq)

Optimal solution found.

x = 2×1

     0
     2

모든 제약 조건 유형이 있는 선형 계획

선형 부등식, 선형 등식, 범위가 있는 단순한 선형 계획 문제를 풉니다.

이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.

$$x(1)+x(2)\le 2$$

$$x(1)+x(2)/4\le 1$$

$$x(1)-x(2)\le 2$$

$$-x(1)/4-x(2)\le 1$$

$$-x(1)-x(2)\le -1$$

$$-x(1)+x(2)\le 2.$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

선형 등식 제약 조건 $$x(1)+x(2)/4=1/2$$을 사용합니다.

Aeq = [1 1/4];
beq = 1/2;

범위를 다음과 같이 설정합니다.

$$-1\le x(1)\le 1.5$$

$$-0.5\le x(2)\le 1.25.$$

lb = [-1,-0.5];
ub = [1.5,1.25];

목적 함수 $$-x(1)-x(2)/3$$을 사용합니다.

f = [-1 -1/3];

선형 계획 문제를 풉니다.

x = linprog(f,A,b,Aeq,beq,lb,ub)

Optimal solution found.

x = 2×1

    0.1875
    1.2500

'interior-point' 알고리즘을 사용한 선형 계획

'interior-point' 알고리즘을 사용하여 선형 계획 문제를 풉니다.

이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.

$$x(1)+x(2)\le 2$$

$$x(1)+x(2)/4\le 1$$

$$x(1)-x(2)\le 2$$

$$-x(1)/4-x(2)\le 1$$

$$-x(1)-x(2)\le -1$$

$$-x(1)+x(2)\le 2.$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

선형 등식 제약 조건 $$x(1)+x(2)/4=1/2$$을 사용합니다.

Aeq = [1 1/4];
beq = 1/2;

범위를 다음과 같이 설정합니다.

$$-1\le x(1)\le 1.5$$

$$-0.5\le x(2)\le 1.25.$$

lb = [-1,-0.5];
ub = [1.5,1.25];

목적 함수 $$-x(1)-x(2)/3$$을 사용합니다.

f = [-1 -1/3];

'interior-point' 알고리즘을 사용하도록 옵션을 설정합니다.

options = optimoptions('linprog','Algorithm','interior-point');

'interior-point' 알고리즘을 사용하여 선형 계획 문제를 풉니다.

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

Solution found during presolve.

x = 2×1

    0.1875
    1.2500

linprog에 대해 문제 기반 접근법을 사용하여 LP 풀기

이 예제에서는 문제 기반 접근법을 사용하여 문제를 설정한 다음 솔버 기반 접근법을 사용하여 이 문제를 푸는 방법을 보여줍니다. 문제는 다음과 같습니다.

$$\underset{x}{\max }(x+y/3)subjectto\{\begin{array}{l}x+y\le 2\\ x+y/4\le 1\\ x-y\le 2\\ x/4+y\ge -1\\ x+y\ge 1\\ -x+y\le 2\\ x+y/4=1/2\\ -1\le x\le 1.5\\ -1/2\le y\le 1.25\end{array}$$

이 문제를 나타내는 prob라는 OptimizationProblem 객체를 만듭니다.

x = optimvar('x','LowerBound',-1,'UpperBound',1.5);
y = optimvar('y','LowerBound',-1/2,'UpperBound',1.25);
prob = optimproblem('Objective',x + y/3,'ObjectiveSense','max');
prob.Constraints.c1 = x + y <= 2;
prob.Constraints.c2 = x + y/4 <= 1;
prob.Constraints.c3 = x - y <= 2;
prob.Constraints.c4 = x/4 + y >= -1;
prob.Constraints.c5 = x + y >= 1;
prob.Constraints.c6 = -x + y <= 2;
prob.Constraints.c7 = x + y/4 == 1/2;

문제 객체를 문제 구조체로 변환합니다.

problem = prob2struct(prob);

결과로 생성된 문제 구조체를 풉니다.

[sol,fval,exitflag,output] = linprog(problem)

Optimal solution found.

sol = 2×1

    0.1875
    1.2500

fval = 
-0.6042

exitflag = 
1

output = struct with fields:
         iterations: 0
          algorithm: 'dual-simplex-highs'
    constrviolation: 0
            message: 'Optimal solution found.'
      firstorderopt: 0

해 성분이 양수일지라도 반환되는 fval은 음수입니다. prob2struct가 내부적으로 최대화 문제를 음을 취한 목적 함수의 최소화 문제로 바꿉니다. 목적 함수 최대화하기 항목을 참조하십시오.

sol의 어떤 성분이 어떤 최적화 변수에 해당할까요? prob의 Variables 속성을 검토합니다.

prob.Variables

ans = struct with fields:
    x: [1×1 optim.problemdef.OptimizationVariable]
    y: [1×1 optim.problemdef.OptimizationVariable]

예상하는 바와 같이, sol(1)은 x에 해당하고, sol(2)는 y에 해당합니다. Algorithms 항목을 참조하십시오.

목적 함수 값 반환하기

단순한 선형 계획의 해와 목적 함수 값을 계산합니다.

부등식 제약 조건은 다음과 같습니다.

$$x(1)+x(2)\le 2$$

$$x(1)+x(2)/4\le 1$$

$$x(1)-x(2)\le 2$$

$$-x(1)/4-x(2)\le 1$$

$$-x(1)-x(2)\le -1$$

$$-x(1)+x(2)\le 2.$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

목적 함수는 $$-x(1)-x(2)/3$$입니다.

f = [-1 -1/3];

문제를 푼 후 목적 함수 값을 반환합니다.

[x,fval] = linprog(f,A,b)

Optimal solution found.

x = 2×1

    0.6667
    1.3333

fval = 
-1.1111

더 많은 출력 정보를 얻어 풀이 과정 검토하기

종료 플래그와 output 구조체를 가져와서 풀이 과정과 해의 품질을 더 정확히 파악할 수 있습니다.

이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.

$$x(1)+x(2)\le 2$$

$$x(1)+x(2)/4\le 1$$

$$x(1)-x(2)\le 2$$

$$-x(1)/4-x(2)\le 1$$

$$-x(1)-x(2)\le -1$$

$$-x(1)+x(2)\le 2.$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

선형 등식 제약 조건 $$x(1)+x(2)/4=1/2$$을 사용합니다.

Aeq = [1 1/4];
beq = 1/2;

범위를 다음과 같이 설정합니다.

$$-1\le x(1)\le 1.5$$

$$-0.5\le x(2)\le 1.25.$$

lb = [-1,-0.5];
ub = [1.5,1.25];

목적 함수 $$-x(1)-x(2)/3$$을 사용합니다.

f = [-1 -1/3];

'dual-simplex' 알고리즘을 사용하도록 옵션을 설정합니다.

options = optimoptions('linprog','Algorithm','dual-simplex');

선형 계획 문제를 푼 후 함수 값, 종료 플래그, output 구조체를 요청합니다.

[x,fval,exitflag,output] = linprog(f,A,b,Aeq,beq,lb,ub,options)

Optimal solution found.

x = 2×1

    0.1875
    1.2500

fval = 
-0.6042

exitflag = 
1

output = struct with fields:
         iterations: 0
          algorithm: 'dual-simplex-highs'
    constrviolation: 0
            message: 'Optimal solution found.'
      firstorderopt: 0

• 목적 함수 값 fval은 더 많은 제약 조건이 있기 때문에 목적 함수 값 반환하기보다 더 큽니다.

• exitflag = 1은 해를 신뢰할 수 있음을 나타냅니다.

• output.iterations = 0은 linprog가 풀이 전처리 중에 해를 발견했으므로 반복해야 할 필요가 전혀 없음을 나타냅니다.

해와 라그랑주 승수 구하기

단순한 선형 계획 문제를 푼 후 해와 라그랑주 승수를 검토합니다.

다음 목적 함수를 사용합니다.

$$f(x)=-5x_1-4x_2-6x_3.$$

f = [-5; -4; -6];

다음 선형 부등식 제약 조건을 사용합니다.

$$x_1-x_2+x_3\le 20$$

$$3x_1+2x_2+4x_3\le 42$$

$$3x_1+2x_2\le 30.$$

A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20;42;30];

모든 변수가 양수가 되도록 제약 조건을 적용합니다.

$$x_1\ge 0$$

$$x_2\ge 0$$

$$x_3\ge 0.$$

lb = zeros(3,1);

Aeq 및 beq를 선형 등식 제약 조건이 없음을 나타내는 []로 설정합니다.

Aeq = [];
beq = [];

라그랑주 승수를 구하는 linprog를 호출합니다.

[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb);

Optimal solution found.

해와 라그랑주 승수를 검토합니다.

x,lambda.ineqlin,lambda.lower

x = 3×1

     0
    15
     3

ans = 3×1

         0
    1.5000
    0.5000

ans = 3×1

     1
     0
     0

lambda.ineqlin이 x의 두 번째 성분과 세 번째 성분에 대해 0이 아닙니다. 이는 두 번째 및 세 번째 선형 부등식 제약 조건이 다음 등식을 충족함을 나타냅니다.

$$3x_1+2x_2+4x_3=42$$

$$3x_1+2x_2=30.$$

다음 결과가 맞는지 확인합니다.

A*x

ans = 3×1

   -12
    42
    30

lambda.lower가 x의 첫 번째 성분에 대해 0이 아닙니다. 이는 x(1)이 그 하한인 0에 있음을 나타냅니다.

입력 인수

f — 계수 벡터

실수형 벡터 | 실수형 배열

계수 벡터로, 실수형 벡터나 실수형 배열로 지정됩니다. 계수 벡터는 목적 함수 f'*x를 나타냅니다. 이 표기법은 f가 열 벡터라고 가정하지만, 행 벡터 또는 배열을 사용할 수 있습니다. 내부적으로 linprog는 f를 열 벡터 f(:)으로 변환합니다.

예: f = [1,3,5,-6]

데이터형: double

A — 선형 부등식 제약 조건

실수 행렬

선형 부등식 제약 조건으로, 실수 행렬로 지정됩니다. A는 M×N 행렬입니다. 여기서 M은 부등식 개수이고 N은 변수 개수(f의 길이)입니다. 대규모 문제의 경우, A를 희소 행렬로 전달하십시오.

A는 다음과 같이 M개의 선형 부등식을 인코딩합니다.

A*x <= b,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, b는 M개의 요소를 갖는 열 벡터입니다.

예를 들어, 다음 부등식을 살펴보겠습니다.

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

다음 제약 조건을 입력하여 부등식을 지정합니다.

A = [1,2;3,4;5,6];
b = [10;20;30];

예: 총합이 1보다 작거나 같도록 x 성분을 지정하려면 A = ones(1,N) 및 b = 1을 지정하십시오.

데이터형: double

Aeq — 선형 등식 제약 조건

실수 행렬

선형 등식 제약 조건으로, 실수 행렬로 지정됩니다. Aeq는 Me×N 행렬입니다. 여기서 Me는 등식 개수이고 N은 변수 개수(f의 길이)입니다. 대규모 문제의 경우, Aeq를 희소 행렬로 전달하십시오.

Aeq는 다음과 같이 Me개의 선형 등식을 인코딩합니다.

Aeq*x = beq,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, beq는 Me개의 요소를 갖는 열 벡터입니다.

예를 들어, 다음 등식을 살펴보겠습니다.

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

다음 제약 조건을 입력하여 등식을 지정합니다.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

예: 합이 1이 되도록 x 성분을 지정하려면 Aeq = ones(1,N) 및 beq = 1을 지정하십시오.

데이터형: double

b — 선형 부등식 제약 조건

실수형 벡터

선형 부등식 제약 조건으로, 실수 벡터로 지정됩니다. b는 A 행렬과 관련된, 요소를 M개 가진 벡터입니다. b를 행 벡터로 전달하면 솔버는 내부적으로 b를 열 벡터 b(:)으로 변환합니다.

b는 다음과 같이 M개의 선형 부등식을 인코딩합니다.

A*x <= b,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, A는 크기가 M×N인 행렬입니다.

예를 들어, 다음 부등식을 살펴보겠습니다.

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

다음 제약 조건을 입력하여 부등식을 지정합니다.

A = [1,2;3,4;5,6];
b = [10;20;30];

예: x 성분의 합이 1 이하가 되도록 지정하려면 A = ones(1,N) 및 b = 1을 사용하십시오.

데이터형: single | double

beq — 선형 등식 제약 조건

실수형 벡터

선형 등식 제약 조건으로, 실수 벡터로 지정됩니다. beq는 Aeq 행렬과 관련된, 요소를 Me개 가진 벡터입니다. beq를 행 벡터로 전달하면 솔버는 내부적으로 beq를 열 벡터 beq(:)으로 변환합니다.

beq는 다음과 같이 Me개의 선형 등식을 인코딩합니다.

Aeq*x = beq,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, Aeq는 크기가 Me×N인 행렬입니다.

예를 들어, 다음 등식을 살펴보겠습니다.

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

다음 제약 조건을 입력하여 등식을 지정합니다.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

예: x 성분의 합이 1이 되도록 지정하려면 Aeq = ones(1,N) 및 beq = 1을 사용하십시오.

데이터형: single | double

lb — 하한

실수형 벡터 | 실수형 배열

하한으로, 실수형 벡터나 실수형 배열로 지정됩니다. f의 길이가 lb의 길이와 같은 경우 lb는 다음을 지정합니다.

모든 i에 대해 x(i) >= lb(i)

numel(lb) < numel(f)이면 lb는 다음을 지정합니다.

1 <= i <= numel(lb)

x(i) >= lb(i).

이 경우 솔버가 경고를 발생시킵니다.

예: 모든 x 성분이 양수가 되도록 지정하려면 lb = zeros(size(f))를 사용하십시오.

데이터형: double

ub — 상한

실수형 벡터 | 실수형 배열

상한으로, 실수형 벡터나 실수형 배열로 지정됩니다. f의 길이가 ub의 길이와 같은 경우 ub는 다음을 지정합니다.

모든 i에 대해 x(i) <= ub(i).

numel(ub) < numel(f)이면 ub는 다음을 지정합니다.

1 <= i <= numel(ub)

x(i) <= ub(i)

이 경우 솔버가 경고를 발생시킵니다.

예: 모든 x 성분이 1보다 작도록 지정하려면 ub = ones(size(f))를 사용하십시오.

데이터형: double

options — 최적화 옵션

optimoptions의 출력값 | optimset이 반환하는 구조체

최적화 옵션으로, optimoptions의 출력값 또는 optimset 등이 반환하는 구조체로 지정됩니다.

옵션에 따라 모든 알고리즘에 적용되는 옵션이 있고 특정 알고리즘에만 유효한 옵션이 있습니다. 자세한 내용은 최적화 옵션 참조 항목을 참조하십시오.

일부 옵션은 optimoptions 표시에 나타나지 않습니다. 이러한 옵션은 다음 표에서 기울임꼴로 표시되어 있습니다. 자세한 내용은 최적화 옵션 보기 항목을 참조하십시오.

모든 알고리즘
Algorithm	다음 최적화 알고리즘을 선택합니다. "dual-simplex-highs"(디폴트 값) "interior-point" "interior-point-legacy" 알고리즘을 선택하는 방법에 대한 자세한 내용은 선형 계획법 알고리즘 항목을 참조하십시오.
Diagnostics	최소화하거나 풀려는 함수에 대한 진단 정보를 표시합니다. "off"(디폴트 값) 또는 "on"을 선택합니다.
Display	표시 수준입니다(반복 과정 표시 참조): "final"(디폴트 값)은 최종 출력값만 표시합니다. "off" 또는 "none"은 출력값을 표시하지 않습니다. "iter"은 각 반복마다 출력값을 표시합니다.
MaxIterations	허용되는 최대 반복 횟수로, 음이 아닌 정수입니다. 디폴트 값은 다음과 같습니다. "dual-simplex-highs" 알고리즘의 경우 대략 2.1475e+09인 intmax "interior-point" 알고리즘의 경우 200 "interior-point-legacy" 알고리즘의 경우 85 허용오차와 중지 기준 항목과 반복 횟수와 함수 실행 횟수 항목을 참조하십시오. optimset의 경우, 이 이름은 MaxIter입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
OptimalityTolerance	쌍대 문제(Dual) 실현가능성에 대한 종료 허용오차로, 음이 아닌 스칼라입니다. 디폴트 값은 다음과 같습니다. "dual-simplex-highs" 알고리즘의 경우 1e-7 "interior-point" 알고리즘의 경우 1e-6 "interior-point-legacy" 알고리즘의 경우 1e-8 optimset의 경우, 이 이름은 TolFun입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
Dual-Simplex-Highs 알고리즘
ConstraintTolerance	제약 조건에 대한 실현가능성 허용오차로, 음이 아닌 스칼라입니다. ConstraintTolerance는 원문제(primal) 실현가능성 허용오차를 측정합니다. 디폴트 값은 1e-7입니다.
MaxTime	알고리즘이 실행되는 최대 시간(단위: 초)입니다. 디폴트 값은 Inf입니다.
풀이 전처리	쌍대 문제 단체 알고리즘 반복 전의 LP 풀이 전처리의 수준입니다. "auto"(디폴트 값), "off" 또는 "on"을 지정합니다.
Interior-Point 알고리즘
ConstraintTolerance	제약 조건에 대한 실현가능성 허용오차로, 음이 아닌 스칼라입니다. ConstraintTolerance는 원문제(primal) 실현가능성 허용오차를 측정합니다. 디폴트 값은 1e-6입니다. optimset의 경우, 이 이름은 TolCon입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
코드 생성
Algorithm	"interior-point"여야 함
ConstraintTolerance	제약 조건에 대한 실현가능성 허용오차로, 음이 아닌 스칼라입니다. ConstraintTolerance는 원문제(primal) 실현가능성 허용오차를 측정합니다. 디폴트 값은 1e-6입니다.
Display	표시 수준: "off", "none" 또는 "final"은 출력값을 표시하지 않습니다. "iter"은 각 반복마다 출력값을 표시합니다. 생성된 코드는 종료 메시지를 표시하지 않습니다.
MaxIterations	허용되는 최대 반복 횟수로, 음이 아닌 정수입니다. 디폴트 값은 200입니다. 허용오차와 중지 기준 항목과 반복 횟수와 함수 실행 횟수 항목을 참조하십시오.
OptimalityTolerance	상대적 쌍대 격차에 대한 종료 허용오차로, 음이 아닌 스칼라입니다. 정의는 수식 5 항목을 참조하십시오. 디폴트 값은 1e-6입니다.

예: options = optimoptions("linprog",Algorithm="interior-point",Display="iter")

problem — 문제 구조체

구조체

문제 구조체로, 다음 필드를 가진 구조체로 지정됩니다.

필드 이름	항목
f	선형 목적 함수 벡터 f
Aineq	선형 부등식 제약 조건에 대한 행렬
bineq	선형 부등식 제약 조건에 대한 벡터
Aeq	선형 등식 제약 조건에 대한 행렬
beq	선형 등식 제약 조건에 대한 벡터
lb	하한으로 구성된 벡터
ub	상한으로 구성된 벡터
solver	'linprog'
options	optimoptions로 생성되는 옵션

problem 구조체에 최소한 solver 필드를 제공해야 합니다.

데이터형: struct

출력 인수

x — 해(Solution)

실수형 벡터 | 실수형 배열

해로, 실수형 벡터나 실수형 배열로 반환됩니다. x의 크기는 f의 크기와 같습니다.

fval — 해에서 계산된 목적 함수 값

실수

해에서 계산된 목적 함수 값으로, 실수로 반환됩니다. 일반적으로 fval = f'*x입니다.

exitflag — linprog가 중지된 이유

정수

linprog가 중지된 이유로, 정수로 반환됩니다.

3	이 해는 상대 ConstraintTolerance 허용오차를 기준으로는 실현 가능하지만, 절대 허용오차를 기준으로는 실현 불가능합니다.
1	함수가 해 x로 수렴되었습니다.
0	반복 횟수가 options.MaxIterations를 초과하거나 풀이 시간(단위: 초)이 options.MaxTime을 초과했습니다.
-2	실현가능점을 찾을 수 없습니다.
-3	문제가 비유계입니다.
-4	알고리즘 실행 도중 NaN 값이 발견되었습니다.
-5	원문제(Primal)와 쌍대 문제(Dual) 모두 실현 가능하지 않습니다.
-7	탐색 방향이 너무 작아졌습니다. 더 이상 진행할 수 없습니다.
-8	스텝이 정의되지 않았습니다. 특이(singular) 시스템으로 인해 알고리즘을 계속 진행할 수 없습니다. 코드 생성은 희소 형식 데이터로만 가능합니다. 희소 형식 데이터 대신 비희소 형식 데이터로 전환하면 솔버가 성공적으로 완료하는 데 도움이 될 수 있습니다.
-9	솔버가 실현가능성을 잃었습니다.
-10	문제가 수치적으로 불안정합니다(codegen만 해당).

생성된 코드는 종료 플래그 1, 0, -2, -3, -7, -8, -10을 반환할 수 있습니다.

종료 플래그 3과 -9는 실현불가능성이 큰 해와 관계가 있습니다. 이런 종료 플래그는 보통 큰 조건수를 갖는 선형 제약 조건 행렬이나 큰 해 성분이 있는 문제에서 비롯됩니다. 이런 문제를 해결하려면 계수 행렬을 스케일링하거나 중복된 선형 제약 조건을 제거하거나 변수에 대해 더 엄밀한 범위를 지정해 보십시오.

output — 최적화 과정에 대한 정보

구조체

최적화 과정에 대한 정보로, 다음 필드를 가진 구조체로 반환됩니다.

iterations	반복 횟수
algorithm	사용된 최적화 알고리즘
cgiterations	0(interior-point 알고리즘만 해당, 이전 버전과의 호환성을 위해 포함됨, 생성된 코드에는 포함되지 않음)
message	종료 메시지(생성된 코드에는 포함되지 않음)
constrviolation	제약 조건 함수의 최댓값
firstorderopt	1차 최적성 측정값

lambda — 해에서의 라그랑주 승수

구조체

해에서의 라그랑주 승수로, 다음 필드를 가진 구조체로 반환됩니다.

lower	lb에 대응하는 하한
upper	ub에 대응하는 상한
ineqlin	A와 b에 대응하는 선형 부등식
eqlin	Aeq와 beq에 대응하는 선형 등식

선형 제약 조건에 대한 라그랑주 승수는 length(f)개의 성분을 가지는 다음 방정식을 충족합니다.

$$\text{f}+{\text{A}}^T{\lambda }_{\text{ineqlin}}+{\text{Aeq}}^T{\lambda }_{\text{eqlin}}+{\lambda }_{\text{upper}}-{\lambda }_{\text{lower}}=0,$$

이는 다음과 같은 라그랑주 함수를 기반으로 합니다.

$${\text{f}}^{T}x+{\lambda }_{\text{ineqlin}}^T\left(\text{A}x-\text{b}\right)+{\lambda }_{\text{eqlin}}^T\left(\text{Aeq}x-\text{beq}\right)+{\lambda }_{\text{upper}}^T\left(x-\text{ub}\right)+{\lambda }_{\text{lower}}^T\left(\text{lb}-x\right).$$

이 부호 규칙은 비선형 솔버의 규칙과 일치합니다(제약 조건이 있는 최적성 이론 참조). 그러나 이 부호는 여러 선형 계획법 문헌에서 사용하는 부호와 반대입니다. 즉, linprog 라그랑주 승수는 관련 "잠재 가격(shadow price)"의 음의 값입니다.

세부 정보

향상된 종료 메시지

다음 몇 가지 항목은 linprog에서 반환될 수 있는 향상된 종료 메시지를 나열한 것입니다. 향상된 종료 메시지에는 자세한 정보를 볼 수 있는 링크가 메시지의 첫 문장으로 제공됩니다.

제약 조건을 충족하는 최솟값을 찾음

솔버가 모든 범위와 선형 제약 조건을 충족하는 최소화 점을 찾았습니다. 문제가 볼록 문제이므로 최소화 점은 전역 최솟값입니다. 자세한 내용은 국소 최적해와 전역 최적해 항목을 참조하십시오.

풀이 전처리 동안 해를 구함

솔버가 풀이 전처리 단계에서 해를 구했습니다. 이는 범위, 선형 제약 조건 및 f(선형 목적 함수 계수)에서 바로 해를 구했다는 의미입니다. 자세한 내용은 풀이 전처리/풀이 후처리 항목을 참조하십시오.

반복 한도를 초과함

linprog가 반복 한도를 초과했습니다. linprog는 MaxIterations 옵션(허용오차)을 중지 기준으로 사용합니다.

점 표기법을 사용하여 옵션의 값을 변경할 수 있습니다.

options.MaxIterations = 5e4;

optimoptions를 사용하여 값을 변경할 수도 있습니다.

options = optimoptions(options,MaxIterations=5e4);

시간 제한을 초과함

linprog는 MaxTime 옵션(허용오차)을 중지 기준으로 사용합니다.

점 표기법을 사용하여 옵션의 값을 변경할 수 있습니다.

options.MaxTime = 5e4;

optimoptions를 사용하여 값을 변경할 수도 있습니다.

options = optimoptions(options,MaxTime=5e4);

문제가 비유계임

선형 계획법 문제의 해가 없으므로 linprog가 중지되었습니다. 모든 목표값에 대해 목적 함수 값이 목표값보다 작은 실현가능점이 있습니다.

할당된 메모리를 초과함

linprog에 메모리가 부족합니다. 문제를 다시 구성하면 해를 구하는 것이 가능할 수도 있습니다. Williams [1]를 참조하십시오.

실현 가능한 해를 찾지 못함

linprog가 실현가능점을 찾지 못했으므로 중지되었습니다. 문제가 실현 가능하지 않을 수 있습니다. 계속 진행하려면 제약 조건을 확인하거나 다른 linprog 알고리즘을 사용해 보십시오. 선형 제약 조건이 모순되는지 검토하는 데 도움이 필요하면 Investigate Linear Infeasibilities 항목을 참조하십시오.

문제가 실현 불가능함

풀이 전처리 중에 솔버가 문제에 모순된 정식화가 있음을 발견했습니다. 단일 점 x에서 일부 제약 조건을 충족할 수 없다는 의미에서 모순입니다. 자세한 내용은 풀이 전처리/풀이 후처리 항목을 참조하십시오.

문제가 비유계임

풀이 전처리 중에 목적 함수가 한계 없이 감소하는 실현 가능한 방향을 솔버가 찾았습니다. 자세한 내용은 풀이 전처리/풀이 후처리 항목을 참조하십시오.

문제가 비유계인 것처럼 보임

선형 계획법 문제의 해가 없으므로 linprog가 중지되었습니다. 모든 목표값에 대해 목적 함수 값이 목표값보다 작은 실현가능점이 있는 것 같습니다.

종료 메시지에 대한 정의

다음 몇 가지 항목은 linprog 종료 메시지에 나오는 용어에 대한 정의를 포함합니다.

허용오차

일반적으로, 허용오차는 이 값을 넘는 경우 솔버의 반복이 중지되는 임계값입니다. 허용오차에 대한 자세한 내용은 허용오차와 중지 기준 항목을 참조하십시오.

다른 알고리즘 실행

LargeScale을 "off"로 설정할 수 있습니다. 이제 linprog는 LargeScale 옵션을 무시합니다.

이전에는 LargeScale을 "off"로 설정하면 linprog가 중간 규모 알고리즘을 사용했습니다.

경고 및 오류가 표시되지 않도록 하려면 다음을 수행하십시오.

• LargeScale 옵션을 사용하지 않습니다.

• Algorithm 옵션을 사용하여 알고리즘을 선택합니다.

팁

경고가 표시되지 않도록 하려면 optimoptions를 사용하여 옵션을 설정하십시오.

다른 알고리즘 선택

linprog "active-set", "simplex" 및 "dual-simplex-legacy" 알고리즘이 제거되었습니다. 현재 옵션 설정에서는 이러한 알고리즘 중 하나를 지정하고 있습니다. 경고가 표시되지 않도록 하고 코드가 오류 없이 실행되도록 보장하려면 Algorithm 옵션을 디폴트 "dual-simplex-highs" 알고리즘으로 설정하거나 "interior-point" 또는 "interior-point-legacy" 알고리즘 중 하나로 설정하십시오. 알고리즘 선택에 대한 자세한 내용은 선형 계획법 알고리즘 항목을 참조하십시오.

알고리즘

Dual-Simplex-Highs 알고리즘

설명은 Dual-Simplex-Highs 알고리즘 항목을 참조하십시오.

Interior-Point-Legacy 알고리즘

"interior-point-legacy" 방법은 메로트라(Mehrotra)의 예측자-수정자 알고리즘[2]의 변형인 원문제-쌍대 문제(Primal-Dual) interior-point 방법에 해당하는 LIPSOL(선형 내점 솔버, [3])을 기반으로 합니다. 알고리즘이 반복 작업을 시작하기 전에 다수의 전처리 스텝이 실행됩니다. Interior-Point-Legacy 선형 계획법 항목을 참조하십시오.

알고리즘의 첫 번째 단계에는 제약 조건의 전처리 작업이 포함될 수 있습니다(Interior-Point-Legacy 선형 계획법 참조). 여러 조건으로 인해 linprog가 실현불가능성 메시지와 함께 종료될 수 있습니다. 각각의 경우에 linprog는 실패를 나타내는 음수 exitflag를 반환합니다.

• 모두 0으로 구성된 행이 Aeq에서 감지되었지만 beq에서 이에 대응하는 요소가 0이 아닌 경우 종료 메시지는 다음과 같습니다.

  Exiting due to infeasibility: An all-zero row in the
  constraint matrix does not have a zero in corresponding
  right-hand-side entry.

• x의 요소 중 하나에 하한이 없는 것으로 확인된 경우 종료 메시지는 다음과 같습니다.

  Exiting due to infeasibility: Objective f'*x is unbounded below.

• Aeq의 행 중 하나가 0이 아닌 요소를 하나만 가지는 경우 x에 있는 연결된 값을 한원소(Singleton) 변수라고 합니다. 이 경우, x에서 해당 성분의 값은 Aeq 및 beq에서 계산될 수 있습니다. 계산된 값이 다른 제약 조건을 위반하는 경우 종료 메시지는 다음과 같습니다.

  Exiting due to infeasibility: Singleton variables in
  equality constraints are not feasible.

• 한원소 변수에 대해 풀 수 있지만 해가 상한 또는 하한을 위반하는 경우 종료 메시지는 다음과 같습니다.

  Exiting due to infeasibility: Singleton variables in
  the equality constraints are not within bounds.

참고

전처리 스텝은 누적적입니다. 예를 들어, 제약 조건 행렬이 모두 0으로 구성된 행으로 시작하지 않는 경우에도 다른 전처리 스텝으로 인해 이러한 행이 발생할 수 있습니다.

전처리가 완료되면 중지 기준이 충족될 때까지 알고리즘의 반복 부분이 시작됩니다. 잔차, 원문제, 쌍대 문제, 관련 중지 기준에 대한 자세한 내용은 Interior-Point-Legacy 선형 계획법 항목을 참조하십시오. 잔차가 작아지지 않고 증가하거나 잔차가 늘어나지도 축소되지도 않는 경우 다음 두 종료 메시지 중 하나가 각각 표시됩니다.

One or more of the residuals, duality gap, or total relative error 
has grown 100000 times greater than its minimum value so far:

또는

One or more of the residuals, duality gap, or total relative error 
has stalled:

이러한 메시지 중 하나가 표시된 후에는 쌍대 문제, 원문제 또는 두 문제 모두 실현 가능하지 않은 것처럼 보인다는 것을 나타내는 다음 메시지 중 하나가 표시됩니다.

• The dual appears to be infeasible (and the primal unbounded). (The primal residual < OptimalityTolerance.)

• The primal appears to be infeasible (and the dual unbounded). (The dual residual < OptimalityTolerance.)

• The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(OptimalityTolerance). (The primal residual < 10*OptimalityTolerance.)

• The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(OptimalityTolerance). (The dual residual < 10*OptimalityTolerance.)

• The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.

• The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.

• Both the primal and the dual appear to be infeasible.

예를 들어, 원문제(목적 함수)는 비유계일 수 있으며, 원문제 제약 조건 충족 정도에 대한 측정값인 원문제 잔차는 작을 수 있습니다.

Interior-Point 알고리즘

"interior-point" 알고리즘은 "interior-point-legacy"와 유사하지만, 분해 루틴이 더욱 효율적이고 전처리가 다릅니다. linprog의 Interior-Point 알고리즘 항목을 참조하십시오.

코드 생성 알고리즘

linprog는 coneprog 솔버를 사용하여 코드를 생성합니다. 이 경우 coneprog 솔버는 2차 원뿔 제약 조건을 사용하지 않습니다. 반복 과정 표시는 coneprog 솔버와 동일한 필드를 보여줍니다. coneprog 알고리즘에 대한 자세한 내용은 Second-Order Cone Programming Algorithm 항목을 참조하십시오.

대체 기능

앱

최적화 라이브 편집기 작업은 linprog에 대한 시각적 인터페이스를 제공합니다.

참고 문헌

[1] Dantzig, G.B., A. Orden, and P. Wolfe. “Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints.” Pacific Journal Math., Vol. 5, 1955, pp. 183–195.

[2] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp. 575–601.

[3] Zhang, Y., “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment.” Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.

확장 기능

C/C++ 코드 생성

MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• linprog는 codegen (MATLAB Coder) 함수 또는 MATLAB^® Coder™ 앱을 사용한 코드 생성을 지원합니다. 코드를 생성하려면 MATLAB Coder 라이선스가 있어야 합니다.

• 타깃 하드웨어는 표준 배정밀도 부동소수점 계산을 지원해야 합니다.

• 코드 생성 대상은 MATLAB 솔버와 동일한 수학 커널 라이브러리를 사용하지 않습니다. 따라서 특히 조건이 나쁜 문제인 경우에 코드 생성의 해가 솔버의 해와 다를 수 있습니다.

• linprog는 코드 생성 시 problem 인수를 지원하지 않습니다.

  [x,fval] = linprog(problem) % Not supported

• A, Aeq, lb, ub 같은 linprog 입력 행렬은 모두 비희소 행렬이거나 희소 행렬일 수 있습니다. 희소 형식 입력값을 사용하려면 동적 메모리 할당을 활성화해야 합니다. Code Generation Limitations (MATLAB Coder) 항목을 참조하십시오. 적은 부분이 0이 아닌 요소로 구성된 경우 솔버는 희소 형식 입력값에 대해 우수한 성능을 보입니다.

• lb 인수와 ub 인수는 선형 목적 함수 벡터 f와 동일한 개수의 요소를 가지거나 비어 있어야 합니다([]).

• 타깃 하드웨어가 무한 범위를 지원하지 않는 경우 optim.coder.infbound를 사용하십시오.

• 임베디드 프로세서가 사용되는 고급 코드 최적화의 경우에는 Embedded Coder^® 라이선스도 필요합니다.

• linprog에 대한 옵션을 포함하고 optimoptions를 사용하여 옵션을 지정해야 합니다. 옵션에는 "interior-point"로 설정된 Algorithm 옵션이 포함되어야 합니다.

  options = optimoptions("linprog",Algorithm="interior-point");
  [x,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,ub,options);

• 코드 생성에 지원되는 옵션은 다음과 같습니다.

  • Algorithm — "interior-point"여야 함

  • ConstraintTolerance

  • Display — 표시하지 않는 경우 "off", "none" 또는 "final"로 지정되고, 반복 과정 표시의 경우 "iter"로 지정됨

  • MaxIterations

  • OptimalityTolerance

• 생성된 코드는 옵션에 대해 제한적인 오류 검사를 수행합니다. 옵션을 업데이트할 때 권장하는 방법은 optimoptions가 아니라 점 표기법을 사용하는 것입니다.

  opts = optimoptions("linprog",Algorithm="interior-point");
  opts = optimoptions(opts,MaxIterations=1e4); % Not recommended
  opts.MaxIterations = 1e4; % Recommended

• linprog는 코드에서 생성된 옵션뿐만 아니라 솔버에 전달된 옵션도 지원합니다.

• 지원되지 않는 옵션을 지정하면 일반적으로 코드 생성 시에 해당 옵션이 무시됩니다. 안정된 결과를 얻기 위해, 지원되는 옵션만 지정하십시오.

버전 내역

R2006a 이전에 개발됨

R2025a: linprog에 대한 코드 생성

linprog "interior-point" 알고리즘은 C 또는 C++ 코드를 생성할 수 있습니다. A, Aeq, lb, ub 같은 입력 행렬은 모두 비희소 행렬이거나 희소 행렬일 수 있습니다. 자세한 내용은 Code Generation for linprog Background 항목을 참조하십시오.

R2025a: linprog "interior-point" 알고리즘의 다른 전처리 방식

linprog "interior-point" 알고리즘은 레거시 전처리 모듈 대신 HiGHS 전처리(풀이 전처리라고도 함)를 사용합니다. 대부분의 테스트 사례에서 linprog는 HiGHS 전처리를 통해 속도가 향상되었고 결과는 거의 변하지 않았습니다.

HiGHS 전처리를 사용하는 경우 문제가 신속하게 풀리지 않거나 양수가 아닌 종료 플래그가 있는 경우 OptimalityTolerance와 ConstraintTolerance 옵션을 느슨하게 설정해 보십시오. 예를 들어, optimoptions를 사용하여 하나 또는 둘 다를 1e-5로 설정해 보십시오. 거의 모든 테스트 사례에서 이러한 조정을 통해 linprog "interior-point" 알고리즘은 문제를 빠르고 정확하게 풀 수 있습니다.

R2025a: "dual-simplex-legacy" 알고리즘은 제거됨

linprog "dual-simplex-legacy" 알고리즘은 제거되었습니다.

R2024b: "dual-simplex-legacy" 알고리즘은 제거될 예정임

linprog "dual-simplex-legacy" 알고리즘은 향후 릴리스에서 제거될 예정입니다.

R2024a: 새 "dual-simplex-highs" 알고리즘이 디폴트 값임

linprog는 이제 디폴트 알고리즘인 "dual-simplex-highs" 알고리즘을 가집니다. 대부분의 문제에서 이 알고리즘은 "dual-simplex-legacy"로 이름이 변경된 이전 디폴트 알고리즘보다 더 나은 성능을 발휘합니다. "dual-simplex-highs" 알고리즘은 HiGHS 오픈소스 코드를 기반으로 합니다.

이전의 디폴트 알고리즘을 사용하려면 optimoptions를 사용하여 Algorithm 옵션을 "dual-simplex-legacy"로 설정하십시오. 반복 과정 표시가 이전과 다릅니다.

참고 항목

intlinprog | mpsread | optimoptions | prob2struct | quadprog | 최적화

도움말 항목

• 선형 계획 설정하기, 솔버 기반
• Typical Linear Programming Problem
• Maximize Long-Term Investments Using Linear Programming: Solver-Based
• 솔버 기반 최적화 문제 설정
• 선형 계획법 알고리즘