이중 선형 프로그램

주어진 선형 프로그램(LP)의 이중은 다음과 같은 개략적인 방법으로 원래의 (원초) LP로부터 파생된 또 다른 LP이다.

원시 LP의 각 변수는 이중 LP의 제약조건이 된다.
원시 LP의 각 제약조건은 이중 LP에서 변수가 된다.
목표 방향은 뒤집혀져 있다. 원시 방향의 최대값은 이중에서 최소가 되며 그 반대의 경우도 마찬가지다.

취약한 이중성 정리는 실현 가능한 해결책에서 이중 LP의 객관적 가치는 항상 실현 가능한 해결책(최소화 문제인지 최소화 문제인지에 따라 상한 또는 하한)에서 원시 LP의 목적에 대한 구속이라고 명시하고 있다.사실, 이 경계 특성은 이중 LP와 원시 LP의 최적 값을 유지한다.

강한 이중성 정리는, 더구나 원시인에게 최적의 용액이 있다면 이중에도 최적의 용액이 있으며, 두 최적성은 동일하다고 기술하고 있다.^[1]

이러한 이론들은 최적화에서 더 큰 종류의 이중성 이론에 속한다.강한 이중성 정리는 이중성 격차(원추의 최적과 이중의 최적 사이의 간극)가 0인 경우 중 하나이다.

듀얼 LP 구성

Primal LP가 주어지면, 듀얼 LP를 구성하는 데 다음과 같은 알고리즘을 사용할 수 있다.^[1]^{: 85}원시 LP는 다음과 같이 정의된다.

n 변수 집합: x $x_{1},\ldots ,x_{n}$ , $x_{1},\ldots ,x_{n}$ $x_{1},\ldots ,x_{n}$ ${\$ $x_{n}.$
For each variable $x_{i}$ , a sign constraint – it should be either non-negative ( $x_{i}\geq 0$ ), or non-positive ( $x_{i}\leq 0$ ), or unconstrained ( $x_{i}\in \mathbb {R}$ ).
목표함수: ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ + ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ + c ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ n ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ {\ $displaystyle {\text{maximize}~~~c_{$ 1} $x_{1}+\cdots +{n}x_$ {n}x_ ${n}}}}}}}}$ 을(를) ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$ 하는 기능
m 제약 조건 목록.Each constraint j is: $a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}$ where the symbol before the $b_{j}$ can be one of $\geq$ or $\leq$ or $=$ .

듀얼 LP는 다음과 같이 구성된다.

각각의 원시적 제약은 이중 변수가 된다.그래서 m $y_{1},\ldots ,y_{m}$ 가 있다: $y_{1},\ldots ,y_{m}$ 1, $y_{1},\ldots ,y_{m}$ y $y_{1},\ldots ,y_{m}$ ${\$
각 이중 변수의 부호 구속조건은 원시 구속조건의 부호에 "반대"이다.So " $\geq b_{j}$ " becomes $y_{j}\leq 0$ and " $\leq b_{j}$ " becomes $y_{j}\geq 0$ and " $=b_{j}$ " becomes $y_{j}\in \mathbb {R}$ .
이중 목표 기능은 b ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ 1 ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ + ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ + ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ + b ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ m ${\$ 1} $y_{1}+\cdots +b_{m}y_{m}}}}}}}$ ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$ 하는 것이다.
각 원시 변수는 이중 구속조건이 된다.그래서 제약이 없다.이중 구속조건에서 이중 변수의 계수는 원시 구속조건에서 원시 변수의 계수다.따라서 각 제약조건 i는 $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ 1 $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ + $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ + $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ {\ $displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\leseqgtr c_{i$ 여기서 $c_{i}$ $c_{i}$ ${\$ 은 초기 LPari 변수에 대한 기호 제약조건과 유사하다 $c_{i}$ .So $x_{i}\leq 0$ becomes " $\leq c_{i}$ " and $x_{i}\geq 0$ becomes " $\geq c_{i}$ " and $x_{i}\in \mathbb {R}$ becomes " $=c_{i}$ ".

이 알고리즘을 보면 듀얼의 이중성이 원초임을 쉽게 알 수 있다.

벡터 제형

모든 제약조건이 동일한 기호를 갖는 경우 매트릭스와 벡터를 사용하여 위의 레시피를 보다 짧은 방법으로 제시할 수 있다.다음 표는 다양한 종류의 영장류와 이중류 사이의 관계를 보여준다.

원시	이중	참고
Ax ≤ b, x ≥ 0에 따라 cx^T 최대화	Ay^T ≥ c, y ≥ 0에 따라 최소화^T	이를 "대칭적" 이중 문제라 한다.
Ax ≤ b에 따라 cx^T 최대화	Ay^T = c, y ≥ 0에 따라 최소화^T	이를 "비대칭적" 이중 문제라 한다.
Ax = b, x ≥ 0에 따라 cx^T 최대화	Ay^T ≥ c의 대상별^T 최소화

이중성의 정리.

아래에서 원시 LP가 "[불규칙]에 따라 cx를^T 최대화"하고 이중 LP가 "[불규칙]에 따라^T 최소화"된다고 가정해 보자.

약한 이중성

약한 이중성 정리는 각각의 실현 가능한 해결책 x와 각각의 실현 가능한 해결책 y: cx^T ≤ by를^T 말한다.즉, 이중의 실현 가능한 각 해결책의 객관적 가치는 원추형의 객관적 가치에 대한 상한값이며, 원추형의 실현 가능한 각 해결책의 객관적 가치는 이중의 객관적 가치에 대한 하한값이다.이는 다음을 암시한다.

max_x cx^T ≤ min_y by^T

특히 원시(위로부터)가 결합되지 않은 경우(위로부터) 이중은 실현 가능한 해결책이 없고, 이중이 결합되지 않은 경우(아래로부터) 원시인은 실현 가능한 해결책이 없다.

약한 이중성 정리는 비교적 간단하게 증명할 수 있다.원시 LP가 "Ax ≤ b, x ≥ 0에 따라 cx^T 최대화"라고 가정한다.제약 조건의 x 계수가 c 이상^T 되도록 양의 계수를 사용하여 제약 조건의 선형 조합을 만든다고 가정합시다.이 선형 결합은 우리에게 목적의 상한을 준다.이중 LP의 변수 y는 이 선형 조합의 계수다.이중 LP는 결과 상한을 최소화하는 계수를 찾으려고 한다.이를 통해 LP에 "Ay^T c c, y 0 0의 대상별^T 축소"^[1]^{: 81–83}를 부여한다.아래의 작은 예를 보라.

강한 이중성

강한 이중성 정리는 두 문제 중 하나가 최적의 해결책을 가지고 있다면 다른 문제 역시 마찬가지며 약한 이중성 정리에 의해 주어진 한계는 팽팽하다는 것을 말한다. 즉, 다음과 같다.

최대_x cx^T = 최소_y 기준^T

강한 이중성 정리는 증명하기가 더 어렵다; 증명은 보통 약한 이중성 정리를 서브루틴으로 사용한다.

한 가지 증거는 심플렉스 알고리즘을 사용하며 적절한 피벗 규칙으로 정확한 솔루션을 제공한다는 증명에 의존한다.이 증거는 일단 심플렉스 알고리즘이 원시 LP에 대한 솔루션으로 마무리되면, 듀얼 LP에 대한 솔루션인 최종 테이블라우에서 읽을 수 있다는 것을 입증한다.그래서, 심플렉스 알고리즘을 실행함으로써, 우리는 원시적인 것과 이중적인 것에 대한 해결책을 동시에 얻는다.^[1]^{: 87–89}

또 다른 증거는 파카스 보조정리기를 사용한다.^[1]^{: 94}

이론적 함의

1. 취약한 이중성 정리는 하나의 실현 가능한 해결책을 찾는 것이 최적의 실현 가능한 해결책을 찾는 것만큼 어렵다는 것을 의미한다.LP가 주어진 경우 임의의 실현 가능한 솔루션을 찾는 신탁이 있다고 가정합시다.LP "Ax b b, x ≥ 0의 대상 cx^T 최대화"를 고려할 때 이 LP와 이중 LP를 결합해 또 다른 LP를 구성할 수 있다.결합된 LP는 x와 y를 모두 변수로 가지고 있다.

최대화 1

Ax ≤ b, Ay^T ≥ c, cx^T ≥ by^T, x ≥ 0, y ≥ 0의 대상

결합된 LP가 실현 가능한 솔루션(x,y)을 가지고 있다면, 약한 이중성에 의해, cx^T = by^T.그래서 x는 원시 LP의 최대용액이어야 하고 y는 이중 LP의 최소용액이어야 한다.조합된 LP가 실현 가능한 해결책이 없다면 원초적인 LP도 실현 가능한 해결책이 없다.

2. 강한 이중성 정리는 어떤 가치 t가 어떤 LP의 최적치임을 쉽게 증명할 수 있다는 점에서 LP의 최적치에 대한 "좋은 특성화"를 제공한다.증명은 두 단계로 진행된다.^[2]^{: 260–261}

primal LP에 값 t와 함께 실현 가능한 해결책을 제시하라; 이것은 최적값이 적어도 t라는 것을 증명한다.
값 t가 있는 듀얼 LP에 실현 가능한 솔루션을 제시하십시오. 이는 최적값이 최대 t임을 입증한다.

예

작은 예

두 개의 변수와 하나의 제약 조건을 갖는 원시 LP를 고려하십시오.

{\cHB{Aligned}{\text{data.}}{{1}+4x_{2}\\{\text{{}}}}{}&5x_{1}+6x_{2에 연결}}=7\\\&x_{1}\geq 0,x_{2}\geq 0\end{arged}}

위의 레시피를 적용하면 다음과 같은 이중 LP를 얻을 수 있으며, 한 가지 변수와 두 가지 제약조건이 있다.

{\begin{aigned}{\text{7y_}{1}\{1}\{1}{1}{1}에 해당하는 {}&5y_{1}\geq 3\\&6y_{1}}\geq 4\&y_{1}\in \mathb {R} \end{aigned}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

x를₁ 하한(0)으로 최소화하고, x를₂ 제약(7/6) 아래에서 상한(7/6)으로 최대화하면 원시 LP의 최대치가 달성되는 것을 쉽게 알 수 있다.최대치는 4 · 7/6 = 14/3이다.

마찬가지로, 이중 LP의 최소치는 y가₁ 제약조건에 따라 하한으로 최소화될 때 얻어진다. 첫 번째 제약조건은 하한 3/5를 주는 반면 두 번째 제약조건은 4/6을 더 엄격하게 하는 반면, 따라서 실제 하한은 4/6이고 최소는 7/4/6 = 14/3이다.

강한 이중성 정리에 따라, 원시성의 최대치는 이중의 최소값과 같다.

우리는 이 사례를 이용하여 취약한 이중성 정리의 증거를 설명한다.Suppose that, in the primal LP, we want to get an upper bound on the objective $3x_{1}+4x_{2}$ . We can use the constraint multiplied by some coefficient, say $y_{1}$ . For any $y_{1}$ we get: $y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}$ $y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}$ . Now, if $y_{1}\cdot 5x_{1}\geq 3x_{1}$ and $y_{1}\cdot 6x_{2}\geq 4x_{2}$ , then ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2$ $}}\geq 3x_{1}+4x_{2$ $7y_{1}\geq 3x_{1}+4x_{2}$ 7 $7y_{1}\geq 3x_{1}+4x_{2}$ $7y_{1}\geq 3x_{1}+4x_{2}$ $7y_{1}\geq 3x_{1}+4x_{2}$ $7y_{1}\geq 3x_{1}+4x_{2}$ $7y_{1}\geq 3x_{1}+4x_{2}$ 1 $7y_{1}\geq 3x_{1}+4x_{2}$ + 4 $7y_{1}\geq 3x_{1}+4x_{2}$ 2 ${\$ 따라서 이중 LP의 목적은 원시 LP의 목적상 상한이다.

농부 예

일부 L 토지, F 비료 및 P 농약을 정해진 공급으로 밀과 보리를 재배할 수 있는 농부를 생각해 보십시오. $밀$ 1단위를 재배하려면 1단위의 토지 $P_{1}$ , $1단위$ 의 비료 $,$ $P_{1}$ 의 $F_{1}$ 농약, $P$ 의 농약을 사용해야 한다 $.$ 마찬가지로 보리 1단위를 재배하기 위해서는 토지의 $F_{2}$ , 비료 $F_{2}$ 2{\ $displaystyle F_{2$ }}단위 $F_{2}$ , 농약 $P_{2}$ ${\$ 2}} $단위$ 를 사용해야 $P_{2}$ 한다.

원시적인 문제는 만약 판매 가격이 개당 $S_{2}$ $S_{1}$ $S_{1}$ ${\$ } 및 $S_{2}$ $S_{2}$ ${\$ $displaystyle$ S_{2}}개일 경우 밀( $x_{1}$ $x_{2}$ ${\$ $x_{1}})$ 과 보리( $x_{2}$ 2 ${\$ $displaystystyle S_{$ 2}}개 $x_{2}$ 의 재배량을 결정하는 농부일 것이다.

최대화: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ + S $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ x $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ ${\$ 1}\cdot x_{ $1}+S_{2}\cdot x_{2$ }}		(밀과 보리를 생산하여 얻은 수입)
대상:	$x_{1}+x_{2}\leq L$	(사용 가능한 토지보다 더 많은 토지 사용)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(사용 가능한 비료보다 더 많이 사용)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(사용 가능한 농약보다 농약을 많이 사용함)
	$x_{1},x_{2}\geq 0$	(이것은 음의 양의 밀이나 보리를 생산한다.)

행렬 형태에서 이것은 다음과 같이 된다.

최대화:

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

[

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

[ x

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

{\

2}\

end

{bmatrix

}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

대상:

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

[

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

1 F

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

2

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

2

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

[

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

2

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

[

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

P

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

[

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

2

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

{\displaystyle {\begin{bmatrix}1&1\\\\\\

F_{1}&F_{2}\\P_{1}\P_{2}\end{bmatrix}{\gin{bmatrix}x_{1}\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\\\

\F\\P\end{bmatrix},\,\\\begin{bmatrix}x_{1}\x_{2}\end{bmatrix}\geq 0.}

이중 문제의 경우, 이러한 각 생산 수단(입력)에 대한 y 단가는 계획 위원회가 정하는 것으로 가정한다.계획위원회의 일은 정해진 투입물량을 조달하는 데 드는 총비용을 최소화하는 동시에 농부에게 각 작물(출고물), 밀(밀₁)용₂ S, 보리용 S의 단가를 바닥으로 제공하는 것이다.이는 다음과 같은 LP에 해당한다.

최소화: $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ y $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ + $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ + P $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ y $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ ${\$ y_{ $P}}}}}}$		(생산수단의 총비용을 "계산함수"로 한다)
대상:	$y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}$	(농부는 밀에 대해₁ S이하로 받아야 한다)
	${\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}}:$	(농부는 보리로 S이하의₂ 것을 받아야 한다.
	$y_{L},y_{F},y_{P}\geq 0$	(비정도는 음수일 수 없다).

행렬 형태에서 이것은 다음과 같이 된다.

최소화:

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

[ L

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

[

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

P

{\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}

{\

begin{bmatrix}}}}{{{bmatrix}}}}}}}}}}{{{{{}}}}}}}}}}}

L}\\y_{F}\\y_{{F}\\y_{{

P}\end{bmatrix}}

대상:

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

[

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

1 P

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

P

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

[ y

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

[ S

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

[

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

Y

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

],

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

{\displaystyle {\begin{bmatrix}1&

gt;

F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\bgin{bmatrix}y_{{{}}}}}}{\begin{bmatrix}y_{{{}}}}}}}}}{{{}}}}}}}

L}\\y_{F}\\y_{{F}\\y_{{

P}\end{bmatrix}\geq {\begin{bmatrix}S_{1}\\\S_{2}\end{bmatrix}},\\\begin{bmatrix}y_{{\

L}\\y_{F}\\y_{{F}\\y_{{

P}\end{bmatrix}\geq 0.}

원시적인 문제는 물리적인 양을 다룬다.모든 입력을 제한된 양으로 사용할 수 있고, 모든 출력의 단가를 가정했을 때, 총 수익을 극대화하기 위해 어떤 양의 출력을 생산해야 하는가?이중 문제는 경제적 가치를 다룬다.모든 출력 단가에 대한 바닥 보증과 모든 입력물의 가용 수량이 알려져 있다고 가정할 때, 총 지출을 최소화하기 위해 어떤 입력 단위의 가격 책정 방식을 설정해야 하는가?

원시 공간의 각 변수에 대해 출력 유형에 의해 지수화된 이중 공간에서 만족해야 하는 불평등에 대응한다.원시 공간에서 만족하는 각 불평등에는 입력 유형에 의해 지수화된 이중 공간의 변수에 해당된다.

원시 공간의 불평등을 구속하는 계수는 이중 공간의 목표, 즉 이 예에서 입력량을 계산하는 데 사용된다.원시 공간의 목표를 계산하는 데 사용된 계수는 이중 공간의 불평등, 즉 이 예에서 출력 단가를 구속했다.

원시 문제와 이중 문제 모두 동일한 행렬을 사용한다.원시 공간에서 이 매트릭스는 정해진 양의 출력을 생성하는 데 필요한 입력의 물리적 양의 소비를 표현한다.이중 공간에서는 설정 입력 단가의 산출물과 관련된 경제적 가치의 창출이 표현된다.

각 불평등은 평등과 느슨한 변수로 대체될 수 있기 때문에, 이것은 각 원시 변수가 이중 슬랙 변수에 대응하고, 각 이중 변수는 원시 슬랙 변수에 대응한다는 것을 의미한다.이 관계는 우리가 보완적 느슨함에 대해 말할 수 있게 해준다.

실행 불가능한 프로그램

LP는 무한하거나 실현 불가능할 수도 있다.이중성 이론은 우리에게 다음과 같이 말한다.

원뿔이 한계에 도달하지 않은 경우, 이중은 실현 불가능한 것이다.
이중이 한이 없는 경우, 원초는 실현 불가능하다.

그러나 이중과 원초 둘 다 실현 불가능한 것은 가능하다.예를 들면 다음과 같다.

최대화: $2x_{1}-x_{2}$ $2x_{1}-x_{2}$ $2x_{1}-x_{2}$ - $2x_{1}-x_{2}$ ${\$ 2}}
대상:	$x_{1}-x_{2}\leq 1$
	$-x_{1}+x_{2}\leq -2$
	$x_{1},x_{2}\geq 0.$

적용들

max-flow min-cut 정리는 강한 이중성 정리의 특별한 경우로서 flow-maximization은 primal LP, cut-minimization은 dual LP이다.Max-flow 최소 절삭 정리#선형 프로그램 제형을 참조하십시오.

다른 그래프 관련 이론들은 강한 이중성 정리, 특히 코닉의 정리를 사용하여 증명할 수 있다.^[3]

제로섬 게임에 대한 미니맥스 정리는 강이중성 정리를 이용하여 증명할 수 있다.^[1]^{: sub.8.1}

대체 알고리즘

때로는 프로그램 매트릭스를 보지 않고 듀얼 프로그램을 얻는 것이 더 직관적일 수 있다.다음 선형 프로그램을 고려하십시오.

최소화	$\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}}}}}}$
의 대상이 되다	$\sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j}}}$	$1\leq j\leq n}$
	$f_{i}x_{i}+\sum _{j=1}^{nb_{ij}t_{j}\geq h_{i}}}}}$	$1\leq i\leq m}$
	$x_{i}\geq 0,\,t_{j}\geq 0,$	$1\leq i\leq m, 1\leq j\leq n}$

우리는 m + n 조건을 가지고 있고 모든 변수는 음이 아니다.m_j + n 이중 변수 y와 s를_i 정의한다.다음 정보를 얻으십시오.

최소화	$\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}}}}}}$
의 대상이 되다	$\sum \sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\j}\geq g_{j}\cdot y_{j}}}}},$	$1\leq j\leq n}$
	$f_{i}x_{i}\cdot s_{i}+\sum _{j=1}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i}}}, {i}},$	$1\leq i\leq m}$
	$x_{i}\geq 0,\,t_{j}\geq 0,$	$1\leq i\leq m, 1\leq j\leq n}$
	$y_{j}\geq 0,\,s_{i}\geq 0,$	$1\leq j\leq n, 1\leq i\leq m}$

이것은 최소화의 문제이기 때문에, 우리는 원형의 하한인 이중 프로그램을 얻고 싶다.즉, 각 원시 변수에 대해 계수의 합이 선형 함수의 계수를 초과하지 않는 조건에서 제약 조건의 모든 우측 합계가 최대값이 되기를 바란다.예를 들어, x는₁ n + 1 제약조건에 나타난다.그 제약조건의 계수를 합하면 우리는 Ay_1,1₁ + Ay_1,2₂ + ...을 얻는다.+ a_1,;;n;;y_n + f₁s₁.이 합계는 기껏해야 c일₁ 것이다.그 결과 다음과 같은 이점을 얻을 수 있다.

극대화하다	$\sum _{j=1}^{ng_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}}}}}}}$
의 대상이 되다	$\sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i}}}}$	$1\leq i\leq m}$
	$e_{j}y_{j}+\sum_{i=1}^{m}b_{ij}s_{i}\leq d_{j}}}$	$1\leq j\leq n}$
	$y_{j}\geq 0,\,s_{i}\geq 0,$	$1\leq j\leq n, 1\leq i\leq m}$

계산 단계에서는 프로그램이 표준 형식이라고 가정한다는 점에 유의하십시오.그러나 모든 선형 프로그램은 표준 형태로 변환될 수 있으며 따라서 제한 요인이 아니다.

실생활해석

이중성 정리는 경제적 해석을 가지고 있다.원시 LP를 고전적인 '자원 할당' 문제로 해석하면 이중 LP를 '자원 평가' 문제로 해석할 수 있다.섀도 가격을 참조하십시오.

이중성 정리에는 물리적인 해석도 있다.^[1]^{: 86–87}

참조

^ ^a ^b ^c ^d ^e ^f ^g Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. 81-104페이지.
^ Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
^ A. A. Ahmadi (2016). "Lecture 6: linear programming and matching" (PDF). Princeton University.

[gm06-1] ^ ^a ^b ^c ^d ^e ^f ^g Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. 81-104페이지.

[lp-2] Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[3] A. A. Ahmadi (2016). "Lecture 6: linear programming and matching" (PDF). Princeton University.

[1]

[2]

[3]

Search