linprog
선형 계획법 문제 풀기
구문
설명
선형 계획법 솔버
다음으로 지정된 문제의 최솟값을 구합니다.
f, x, b, beq, lb, ub는 벡터이고 A와 Aeq는 행렬입니다.
참고
linprog
솔버는 솔버 기반 접근법에만 적용됩니다. 두 가지 최적화 접근법에 대한 설명은 먼저 문제 기반 접근법 또는 솔버 기반 접근법 중 선택하기 항목을 참조하십시오.
은 x
= linprog(problem
)problem
에 설명되어 있는 구조체인 problem
의 최솟값을 구합니다.
mpsread
를 사용하여 MPS 파일에서 problem
구조체를 가져올 수 있습니다. 또는 prob2struct
를 사용하여 OptimizationProblem
객체에서 problem
구조체를 만들 수도 있습니다.
예제
선형 계획, 선형 부등식 제약 조건
선형 부등식으로 정의된 단순한 선형 계획 문제를 풉니다.
이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
목적 함수 을 사용합니다.
f = [-1 -1/3];
선형 계획 문제를 풉니다.
x = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
선형 부등식 및 선형 등식이 있는 선형 계획
선형 부등식 및 선형 등식으로 정의된 단순한 선형 계획 문제를 풉니다.
이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
선형 등식 제약 조건 을 사용합니다.
Aeq = [1 1/4]; beq = 1/2;
목적 함수 을 사용합니다.
f = [-1 -1/3];
선형 계획 문제를 풉니다.
x = linprog(f,A,b,Aeq,beq)
Optimal solution found.
x = 2×1
0
2
모든 제약 조건 유형이 있는 선형 계획
선형 부등식, 선형 등식, 범위가 있는 단순한 선형 계획 문제를 풉니다.
이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
선형 등식 제약 조건 을 사용합니다.
Aeq = [1 1/4]; beq = 1/2;
범위를 다음과 같이 설정합니다.
lb = [-1,-0.5]; ub = [1.5,1.25];
목적 함수 을 사용합니다.
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'
알고리즘을 사용하여 선형 계획 문제를 풉니다.
이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
선형 등식 제약 조건 을 사용합니다.
Aeq = [1 1/4]; beq = 1/2;
범위를 다음과 같이 설정합니다.
lb = [-1,-0.5]; ub = [1.5,1.25];
목적 함수 을 사용합니다.
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 풀기
이 예제에서는 문제 기반 접근법을 사용하여 문제를 설정한 다음 솔버 기반 접근법을 사용하여 이 문제를 푸는 방법을 보여줍니다. 문제는 다음과 같습니다.
이 문제를 나타내는 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 항목을 참조하십시오.
목적 함수 값 반환하기
단순한 선형 계획의 해와 목적 함수 값을 계산합니다.
부등식 제약 조건은 다음과 같습니다.
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
목적 함수는 입니다.
f = [-1 -1/3];
문제를 푼 후 목적 함수 값을 반환합니다.
[x,fval] = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
fval = -1.1111
더 많은 출력 정보를 얻어 풀이 과정 검토하기
종료 플래그와 output 구조체를 가져와서 풀이 과정과 해의 품질을 더 정확히 파악할 수 있습니다.
이 예제에서는 다음 선형 부등식 제약 조건을 사용합니다.
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
선형 등식 제약 조건 을 사용합니다.
Aeq = [1 1/4]; beq = 1/2;
범위를 다음과 같이 설정합니다.
lb = [-1,-0.5]; ub = [1.5,1.25];
목적 함수 을 사용합니다.
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 = [-5; -4; -6];
다음 선형 부등식 제약 조건을 사용합니다.
A = [1 -1 1 3 2 4 3 2 0]; b = [20;42;30];
모든 변수가 양수가 되도록 제약 조건을 적용합니다.
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이 아닙니다. 이는 두 번째 및 세 번째 선형 부등식 제약 조건이 다음 등식을 충족함을 나타냅니다.
다음 결과가 맞는지 확인합니다.
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
개의 요소를 갖는 열 벡터입니다.
예를 들어, 다음 부등식을 살펴보겠습니다.
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 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
개의 요소를 갖는 열 벡터입니다.
예를 들어, 다음 등식을 살펴보겠습니다.
x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 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
인 행렬입니다.
예를 들어, 다음 부등식을 살펴보겠습니다.
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 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
인 행렬입니다.
예를 들어, 다음 등식을 살펴보겠습니다.
x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 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 | 다음 최적화 알고리즘을 선택합니다.
알고리즘을 선택하는 방법에 대한 자세한 내용은 선형 계획법 알고리즘 항목을 참조하십시오. |
Diagnostics | 최소화하거나 풀려는 함수에 대한 진단 정보를 표시합니다. |
| 표시 수준입니다(반복 과정 표시 참조):
|
| 허용되는 최대 반복 횟수로, 양의 정수입니다. 디폴트 값은 다음과 같습니다.
허용오차와 중지 기준 항목과 반복 횟수와 함수 실행 횟수 항목을 참조하십시오.
|
| 쌍대 문제(Dual) 실현가능성에 대한 종료 허용오차로, 양의 스칼라입니다. 디폴트 값은 다음과 같습니다.
|
interior-point 알고리즘 | |
ConstraintTolerance | 제약 조건에 대한 실현가능성 허용오차로, 음이 아닌 스칼라입니다.
|
Dual-Simplex 알고리즘 | |
ConstraintTolerance | 제약 조건에 대한 실현가능성 허용오차로,
|
MaxTime | 알고리즘이 실행되는 최대 시간(단위: 초)입니다. 디폴트 값은 |
Preprocess | 쌍대 문제 단체 알고리즘 반복 전의 LP 전처리 수준입니다. |
예: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')
problem
— 문제 구조체
구조체
문제 구조체로, 다음 필드를 가진 구조체로 지정됩니다.
필드 이름 | 항목 |
---|---|
| 선형 목적 함수 벡터 f |
| 선형 부등식 제약 조건에 대한 행렬 |
| 선형 부등식 제약 조건에 대한 벡터 |
| 선형 등식 제약 조건에 대한 행렬 |
| 선형 등식 제약 조건에 대한 벡터 |
lb | 하한으로 구성된 벡터 |
ub | 상한으로 구성된 벡터 |
| 'linprog' |
| optimoptions 로 생성되는 옵션 |
problem
구조체에 최소한 solver
필드를 제공해야 합니다.
데이터형: struct
출력 인수
x
— 해(Solution)
실수형 벡터 | 실수형 배열
해로, 실수형 벡터나 실수형 배열로 반환됩니다. x
의 크기는 f
의 크기와 같습니다.
fval
— 해에서 계산된 목적 함수 값
실수
해에서 계산된 목적 함수 값으로, 실수로 반환됩니다. 일반적으로 fval
= f'*x
입니다.
exitflag
— linprog
가 중지된 이유
정수
linprog
가 중지된 이유로, 정수로 반환됩니다.
| 이 해는 상대 |
| 함수가 해 |
| 반복 횟수가 |
| 실현가능점을 찾을 수 없습니다. |
| 문제가 비유계입니다. |
| 알고리즘 실행 도중 |
| 원문제(Primal)와 쌍대 문제(Dual) 모두 실현 가능하지 않습니다. |
| 탐색 방향이 너무 작아졌습니다. 더 이상 진행할 수 없습니다. |
| 솔버가 실현가능성을 잃었습니다. |
종료 플래그 3
과 -9
는 실현불가능성이 큰 해와 관계가 있습니다. 이런 종료 플래그는 보통 큰 조건수를 갖는 선형 제약 조건 행렬이나 큰 해 성분이 있는 문제에서 비롯됩니다. 이런 문제를 해결하려면 계수 행렬을 스케일링하거나 중복된 선형 제약 조건을 제거하거나 변수에 대해 더 엄밀한 범위를 지정해 보십시오.
output
— 최적화 과정에 대한 정보
구조체
최적화 과정에 대한 정보로, 다음 필드를 가진 구조체로 반환됩니다.
iterations | 반복 횟수 |
algorithm | 사용된 최적화 알고리즘 |
cgiterations | 0(interior-point 알고리즘만 해당, 이전 버전과의 호환성을 위해 포함됨) |
message | 종료 메시지 |
constrviolation | 제약 조건 함수의 최댓값 |
firstorderopt | 1차 최적성 측정값 |
lambda
— 해에서의 라그랑주 승수
구조체
해에서의 라그랑주 승수로, 다음 필드를 가진 구조체로 반환됩니다.
선형 제약 조건에 대한 라그랑주 승수는 length(f)
개의 성분을 가지는 다음 방정식을 충족합니다.
이는 다음과 같은 라그랑주 함수를 기반으로 합니다.
이 부호 규칙은 비선형 솔버의 규칙과 일치합니다(제약 조건이 있는 최적성 이론 참조). 그러나 이 부호는 여러 선형 계획법 문헌에서 사용하는 부호와 반대입니다. 즉, 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 이전에 개발됨
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)