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 솔버는 솔버 기반 접근법에만 적용됩니다. 두 가지 최적화 접근법에 대한 설명은 먼저 문제 기반 접근법 또는 솔버 기반 접근법 중 선택하기 항목을 참조하십시오.

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)

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in feasible directions, to within the function tolerance, and constraints are satisfied to within the constraint tolerance.

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: 1
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

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

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

prob.Variables

ans = struct with fields:
    x: [1x1 optim.problemdef.OptimizationVariable]
    y: [1x1 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: 1
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      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를 희소 벡터로 전달하십시오.

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을 사용하십시오.

데이터형: double

beq — 선형 등식 제약 조건

실수형 벡터

선형 등식 제약 조건으로, 실수 벡터로 지정됩니다. beq는 Aeq 행렬과 관련된, 요소를 Me개 가진 벡터입니다. beq를 행 벡터로 전달하면 솔버는 내부적으로 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을 사용하십시오.

데이터형: 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'(디폴트 값) 'interior-point-legacy' 'interior-point' 알고리즘을 선택하는 방법에 대한 자세한 내용은 선형 계획법 알고리즘 항목을 참조하십시오.
Diagnostics	최소화하거나 풀려는 함수에 대한 진단 정보를 표시합니다. 'off'(디폴트 값) 또는 'on'을 선택합니다.
Display	표시 수준입니다(반복 과정 표시 참조): 'final'(디폴트 값)은 최종 출력값만 표시합니다. 'off' 또는 'none'은 출력값을 표시하지 않습니다. 'iter'은 각 반복마다 출력값을 표시합니다.
MaxIterations	허용되는 최대 반복 횟수로, 양의 정수입니다. 디폴트 값은 다음과 같습니다. 'interior-point-legacy' 알고리즘의 경우 85 'interior-point' 알고리즘의 경우 200 'dual-simplex' 알고리즘의 경우 10*(numberOfEqualities + numberOfInequalities + numberOfVariables) 허용오차와 중지 기준 항목과 반복 횟수와 함수 실행 횟수 항목을 참조하십시오. optimset의 경우, 이 이름은 MaxIter입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
OptimalityTolerance	쌍대 문제(Dual) 실현가능성에 대한 종료 허용오차로, 양의 스칼라입니다. 디폴트 값은 다음과 같습니다. 'interior-point-legacy' 알고리즘의 경우 1e-8 'dual-simplex' 알고리즘의 경우 1e-7 'interior-point' 알고리즘의 경우 1e-6 optimset의 경우, 이 이름은 TolFun입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
interior-point 알고리즘
ConstraintTolerance	제약 조건에 대한 실현가능성 허용오차로, 음이 아닌 스칼라입니다. ConstraintTolerance는 원문제(primal) 실현가능성 허용오차를 측정합니다. 디폴트 값은 1e-6입니다. optimset의 경우, 이 이름은 TolCon입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
Dual-Simplex 알고리즘
ConstraintTolerance	제약 조건에 대한 실현가능성 허용오차로, 1e-9에서 1e-3까지의 스칼라 값입니다. ConstraintTolerance는 원문제(primal) 실현가능성 허용오차를 측정합니다. 디폴트 값은 1e-4입니다. optimset의 경우, 이 이름은 TolCon입니다. 현재 옵션 이름과 이전 옵션 이름 항목을 참조하십시오.
MaxTime	알고리즘이 실행되는 최대 시간(단위: 초)입니다. 디폴트 값은 Inf입니다.
Preprocess	쌍대 문제 단체 알고리즘 반복 전의 LP 전처리 수준입니다. 'basic'(디폴트 값) 또는 'none'을 지정합니다.

예: 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	탐색 방향이 너무 작아졌습니다. 더 이상 진행할 수 없습니다.
-9	솔버가 실현가능성을 잃었습니다.

종료 플래그 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)"의 음의 값입니다.

알고리즘

Dual-Simplex 알고리즘

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

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에 대한 시각적 인터페이스를 제공합니다.

참고 문헌

[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.

버전 내역

R2006a 이전에 개발됨

참고 항목

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

도움말 항목

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

×

예제 열기

이 예제의 수정된 버전이 있습니다. 사용자가 편집한 내용을 반영하여 이 예제를 여시겠습니까?

아니요, 수정된 버전을 덮어씁니다. 예