기본 실현 가능한 해결책

이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "기본적인 실현 가능한 해결책" – 뉴스 · 신문 · 도서 · 학자 · JSTOR(2018년 12월)

선형 프로그래밍 이론에서 기본적인 실현 가능한 솔루션(BFS)은 0이 아닌 변수의 최소 집합을 갖는 솔루션이다.기하학적으로, 각 BFS는 실현 가능한 해결책의 다면체의 한 구석에 해당한다.최적의 해결책이 있다면 최적의 BFS가 존재한다.따라서 최적의 솔루션을 찾기 위해서는 BFS-s를 고려하는 것으로 충분하다.이 사실은 일부 BFS에서 최적의 BFS가 발견될 때까지 이동하는 심플렉스 알고리즘에 의해 사용된다.^[1]

정의

BFS를 정의하기 위해 먼저 선형 프로그램을 소위 등가 형태로 제시한다.

${C\mathbf{}}^{}$ ${}^{}\mathbf{}$ ${\$$T} \mathbf {x} }$

${\displaystyle 대상\mathbf{}}$:${\displaystyle }$A ${\displaystyle x\mathbf{}}$ =$$b {\$displaystyle$A\$mathbf$ {x$}$=\$mathbf {$b$$} 및 ${$$$0 {\$displaystyle \mathbf${x} \$geq$ 0$}$

여기서:

• ${\$$T}}}$ 및$$ $x{\displaystyle \mathbf{}}$ ${\$x$} }$은(는) n 크기의 벡터$$(변수의 수)임.
• ${\displaystyle }$b $[\$}은(는) m 크기의 벡터$$(제한조건 수)이다.
• $[\displaystyle A}$은(는) m-by-n 행렬이다.
• ${\displaystyle \mathbf{x}}$ ${\displaystyle \ge }$ ${\displaystyle 0}$ ${\displaystyle \mathbf {x} \geq 0}$은(는) 모든 변수가 음수가 아님을 의미한다$$.

어떤 선형 프로그램이라도 느슨한 변수를 추가하면 등분형 형태로 변환할 수 있다.

예비 정리 단계로서 다음을 검증한다.

• 시스템 $A{\displaystyle }$ ${\displaystyle x\mathbf{}}$= ${\displaystyle b\mathbf{}}$ ${\$에는 솔루션이 하나$$ 이상 있음(그렇지 않으면 전체 LP에 솔루션이 없고 더 이상 할 일이 없음);
• $매트릭스{\displaystyle }$ A {\$displaystyle A}$의 모든 m 행은 선형적으로 독립적이다$$. 즉, 그 순위는 m이다(그렇지 않으면 LP를 변경하지 않고 중복 행만 삭제할 수 있다).

일반적으로 m < n이므로 시스템 ${\displaystyle A\mathbf{}}$ x${\displaystyle }$= ${\displaystyle b\mathbf{}}$ ${\$는) 여러 가지 솔루션을$$ 가지고 있으며, 각각의 솔루션은 LP의 실현 가능한 솔루션이라고 불린다.

B를 {1,...,n}의 m 인덱스의 하위 집합으로 두십시오.A ${\displaystyle B_{}}$ ${\$을(를) 사용하여 지수화한 $A{\displaystyle }$ ${\displaystyle A}$의 m 열로 만든 제곱 m-by-m 행렬을 나타낸다.$A{\displaystyle {}_{}}$ ${\displaystyle B_{}}$ ${\$가 비일상이라면 B가 지수화한 기둥은 $A{\displaystyle }$ ${\displaystyle A}$의 열 공간의 기초가 된다$.$ 이 경우 우리는 B를 LP의 기초라고 부른다.$A$의 순위 ${\displaystyle A}$이(가) m이기 때문에 적어도 하나의 기준이 있고, $A{\displaystyle }$ ${\displaystyle A}$은(는) n개의 열이 있으므로$$ 최대${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$ m )${\$ {$n}{m}}}$개의 기본값이$$ 있다.

근거 B를 제시하면, 실현 $가능$한 솔루션 $x{\displaystyle \mathbf{}}$ ${\$}은(는) 모든 비 영변수가 B에 의해 색인화된 경우, 즉 모든 j${\displaystyle :x_{}}$ ${\displaystyle j{}_{}}$= ${\displaystyle 0}$ ${\displaystyle j\not \in$ B$:~x_{j}=0}$에 의해 실현 가능한 기본 솔루션이라고 한다$.$

특성.

1. BFS는 LP(매트릭스 $A{\displaystyle }$ ${\displaystyle A}$ 및$$ $벡터{\displaystyle \mathbf{}}$ b ${\$})의 제약조건에 의해서만 결정되며,$$ 최적화 목적에 따라 달라지지 않는다.

2. 정의에 따르면 BFS는 최소 m 0이 아닌 변수와 최소 n-m 0 변수를 가진다.BFS는 m 비 영점 변수보다 작을 수 있다. 이 경우 BFS는 0이 아닌 변수의 지수를 포함하는 다양한 기준을 가질 수 있다.

3. 실현 가능한 솔루션 $x{\displaystyle \mathbf{}}$ ${\$ ${\displaystyle {행렬}_{}}$ A$${\$displaystyle A_{K}$의 열이 선형적으로 독립되어 있다면$$, 여기서$$ K는 $\$의 0이 아닌 원소의 지수 집합이다.

4. BFS는 base B에 의해 고유하게 결정된다: 각 base B에 대해 base B와 함께$$ bFS x ${\displaystyle {B\mathbf{}}_{}}$ ${\displaystyle$ \$mathbf${x_${B}}}}$이(가) 있다.그 $이유$는 ${\displaystyle {x\mathbf{}}_{}}$ B$${\$displaystyle \mathbf {x_{B}}}}}$이(가) ${\displaystyle {}_{}{\mathbf{}}_{}}$ x${\displaystyle {}_{}{B\mathbf{}}_{}}$ = ${\displaystyle b}${\$displaystyle A_{B}}$ 제약조건을 충족해야$$ 하며$,$ 기초적으로 ${\displaystyle {매트릭스}_{}}$ A ${\$ =$b}$를 충족해야$$ 하기 때문에 제약조건에 고유한 해결책이 있기 때문이다.그 반대는 사실이 아니다: 각각의 BFS는 많은 다른 근거에서 올 수 있다.

${\displaystyle A}$ ${\displaystyle B_{}}$ ${\displaystyle {}_{}{\mathbf{}}_{}}$ ${\displaystyle {B\mathbf{}}_{}}$= b ${\displaystyle A_{B}\mathbf {x_{B}}}$ =$b}$의 고유한 솔루션이 비부정성 제약 조건을 만족하면$$ 그 근거를 실현 가능한 기준이라고 한다.

5. 선형 프로그램에 최적의 해결책(즉, 실현 가능한 해결책이 있고, 실현 가능한 해결책의 집합이 경계)이 있다면, 최적 BFS를 가진다.이것은 Bauer 최대 원칙의 결과물이다: 선형 프로그램의 목적은 볼록하다; 실현 가능한 해결책의 집합은 볼록하다(과급 영역의 교차점이다). 따라서 목적은 실현 가능한 해결책 집합의 극한 지점에서 최대치를 달성한다.

BFS-s의 수는 유한하고${\displaystyle }$(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ $){\$에 의해 한정되어 있으므로$,$ 모든${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$ m$){\$BFS-s에서$$ 객관적 기능을 평가하기만 하면 모든 LP에 대한 최적의 솔루션을 유한한 시간에 찾을 수 있다.이것은 LP를 해결하는 가장 효율적인 방법이 아니다; 심플렉스 알고리즘은 훨씬 더 효율적인 방법으로 BFS-s를 검사한다.

예

다음과 같은 제약 조건이 있는 선형 프로그램을 고려하십시오.

${\displaystyle {\required}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}}}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}}}&=7\\\\all i\in \{1,\ldots ,5\}x_{i}&\geq 0\end{aigned}}}}}$

매트릭스 A는 다음과 같다.

${\displaystyle A={\begin{pmatrix}1&5&3&4&6\\\0&1&3&5&6\end{pmatrix}~~~~\mathbf {b} =(14~7)}$

여기서 m=2와 2개의 지수에 10개의 하위 집합이 있지만 모두 베이스는 아니다. 3열과 5열은 선형 종속적이므로 집합 {3,5}이(가) 기준이 아니다.

매트릭스 A =( 5 ) ${\$ 매트릭스가 비싱글이기 때문에 세트 B={2,4}는 기본이다.

이 기준에 해당하는 고유 BFS는 ${\displaystyle x_{}}$ B${\displaystyle {}_{}}$=${\displaystyle }$( ${\displaystyle 0}$ ${\displaystyle 2\mathrm{}}$ ${\displaystyle 0\mathrm{}}$ ${\displaystyle 1\mathrm{}}$ ${\displaystyle 0\mathrm{}}$) ${\displaystyle x_{B}=(0~2~0~$0~$1~0)}$이다$.$

기하학적 해석

실현 가능한 모든 해결책의 집합은 하이퍼스페이스의 교차점이다.따라서 볼록한 다면체다.만약 그것이 경계를 이루었다면, 그것은 볼록한 폴리토프다.

각 BFS는 이 폴리토프의 정점에 해당한다.^{[1]: 53–56}

Simplex 알고리즘의 응용 프로그램

심플렉스 알고리즘은 실행의 각 지점에서 "현재 기준" B(n 변수 중 m의 부분 집합), "현재 BFS" 및 "현재 테이블라우"를 유지한다.Tableau는 기본 변수가 비기본적인 변수에 의해 표현되는 선형 프로그램을 나타낸다.

여기서 $x{\displaystyle {}_{}}$ ${\displaystyle B_{}}$ ${\$는 m 기본 변수의 벡터, ${\displaystyle x_{}}$ $N{\displaystyle {}_{}}$ ${\$은 n개의 비기본 변수의 벡터, $z{\displaystyle }$ ${\displaystyle z}$은 최대화 목표다.비기본 변수가 0이므로 현재 $BFS$는 p ${\displaystyle p}$이고$,$ 현재 최대화 목표는 ${\displaystyle {z\mathrm{}}_{}}$ $0{\displaystyle {}_{}}$ ${\$이다$.$

$r{\displaystyle }$ ${\displaystyle r}$의 모든 계수가 음수일$$ 경우 ${\displaystyle {z\mathrm{}}_{}}$ 0 ${\$은(는) 모든 변수(모든 비기본 변수를 포함)가 0 이상이어야 하므로 두 번째 선은 $z{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$을 암시하므로 $최적$의 솔루션이다$.$

$r{\displaystyle }$ ${\displaystyle r}$의 일부 계수가 양의$$ 값이면 최대화 대상을 늘릴 수 있다.예를 들어, ${\displaystyle {x\mathrm{}}_{}}$ 5 ${\$가 비기본적이고 r ${\displaystyle r}$의 계수가 양수인$$ 경우, 이를 0 이상으로 증가시키면 $z{\displaystyle }$ ${\displaystyle$ z$}$이(가) 커질$$ 수 있다.다른 제약조건을 위반하지 않고 그렇게 할 수 있다면 증가된 변수는 기본("기준에 도달한다")이 되고, 또 다른 비기본 변수는 0으로 감소하여 평등 제약조건을 유지함으로써 비기본("기준에 도달한다")이 된다.

이 과정을 주의 깊게 진행하면 최적의 BFS에 도달할 때까지 $z{\displaystyle }$ ${\displaystyle$ z$}$이(가) 증가한다는$$ 보장이 가능하다.

참조