선형 프로그래밍

2개의 변수와 6개의 부등식이 있는 단순한 선형 프로그램을 그림으로 표현합니다.실현 가능한 해법 세트는 노란색으로 표시되고 다각형인 2차원 폴리토프를 형성합니다.선형 비용 함수의 최적값은 빨간색 선이 폴리곤과 교차하는 지점입니다.빨간색 선은 비용 함수의 수준 집합이며, 화살표는 최적화하는 방향을 나타냅니다.

세 개의 변수를 가진 문제의 닫힌 실현 가능 영역은 볼록 다면체이다.목표 함수의 고정 값을 제공하는 표면은 평면입니다(표시되지 않음).선형 프로그래밍 문제는 가능한 가장 높은 값을 가진 평면에 있는 다면체에서 점을 찾는 것입니다.

선형 최적화라고도 불리는 선형 프로그래밍(LP)은 요구사항이 선형 관계로 표현되는 수학적 모델에서 최상의 결과(최대 이익 또는 최소 비용 등)를 달성하기 위한 방법입니다.선형 프로그래밍은 수학적 프로그래밍(수학적 최적화라고도 함)의 특수한 경우입니다.

좀 더 형식적으로 선형 프로그래밍은 선형 목적 함수의 최적화를 위한 기술이며, 선형 등식과 선형 부등식 제약 조건이 적용됩니다.그것의 실현 가능한 영역은 볼록 폴리토프이며, 이것은 각각 선형 부등식에 의해 정의되는 최종 다수의 반공간의 교집합으로 정의된 집합이다.그것의 목적 함수는 이 다면체에서 정의된 실제 값 아핀(선형) 함수이다.선형 프로그래밍 알고리즘은 폴리토프에서 이 함수가 가장 작은(또는 가장 큰) 값을 갖는 점을 찾습니다.

선형 프로그램은 표준 형식으로 다음과 같이 표현될 수 있는 문제입니다.

{begin{aligned}&{\text{Find a vector}&\mathbf {x}&\mathbf {c}&\mathbf {x}&\text}&\mathbf {x}&A\leq \mathbf {x}&{text

여기서 x의 성분은 결정되는 변수이고, c 및 b는 벡터( $\mathbf {c} ^{T}$ T $\mathbf {c} ^{T}$ {c $}^{T$ }})가 주어지며, A는 주어진 행렬이다.값을 최대화 또는 최소화하는 함수( $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ 경우 x $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ T $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ \ $displaystyle \mathbf {x}$ \ $mapsto \mathbf {c}$ ^{ $T}\mathbf {x}$ ）를 $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ 목적 함수라고 한다.부등식 Ax b b와 x 0 0은 목적 함수를 최적화하는 볼록 폴리토프를 지정하는 제약 조건이다.이 문맥에서 두 벡터는 동일한 치수를 가질 때 비교할 수 있습니다.제1의 각 엔트리가 제2의 대응하는 엔트리와 같거나 작다면 제1의 벡터는 제2의 벡터보다 작거나 같다고 할 수 있다.

선형 프로그래밍은 다양한 연구 분야에 적용할 수 있습니다.이것은 수학에서 널리 사용되며, 사업, 경제, 그리고 몇몇 공학적인 문제에서 덜 사용됩니다.선형 프로그래밍 모델을 사용하는 산업에는 운송, 에너지, 통신 및 제조업이 포함됩니다.이는 계획, 라우팅, 스케줄링, 할당 및 설계와 같은 다양한 유형의 문제를 모델링하는 데 유용한 것으로 입증되었습니다.

역사

레오니트 칸토로비치

요한 폰 노이만

선형 부등식의 시스템을 푸는 문제는 적어도 푸리에까지 거슬러 올라가며,^[1] 푸리에-모츠킨 제거 방법은 1827년에 푸리에-모츠킨 제거 방법을 발표했다.

1939년 소련의 수학자이자 경제학자인 레오니드 칸토로비치가 문제를 ^[2]푸는 방법을 제안하면서 일반적인 선형 프로그래밍 문제와 동등한 문제의 선형 프로그래밍 공식이 제공되었습니다.이는 제2차 세계대전 중 그가 군비를 절감하고 ^{[citation needed]}적에게 가해지는 손실을 늘리기 위해 지출과 수익을 계획하는 방법이다.칸토로비치의 연구는 처음에 ^[3]소련에서 무시되었다. 칸토로비치와 거의 같은 시기에 네덜란드계 미국인 경제학자 T. C. 쿱만은 고전적인 경제 문제를 선형 프로그램으로 공식화했다.칸토로비치와 쿱만은 1975년 노벨 ^[1]경제학상을 공동 수상했다.1941년, Frank Lauren Hitchcock은 또한 운송 문제를 선형 프로그램으로 공식화했고 나중에 나온 심플렉스 ^[2]방법과 매우 유사한 해결책을 제시했습니다.히치콕은 1957년에 사망했고 노벨상은 사후에 수여되지 않는다.

1946~1947년 조지 B. Dantzig는 미국 ^[4]공군의 문제를 계획하는 데 사용할 일반적인 선형 프로그래밍 공식을 독자적으로 개발했다.1947년, 단치히그는 또한 대부분의 ^[4]경우에 선형 프로그래밍 문제를 효율적으로 해결하는 심플렉스 방법을 발명했다.단치히가 그의 심플렉스 방법을 논의하기 위해 존 폰 노이만과의 만남을 주선했을 때, 노이만은 그가 게임 이론에서 연구해 온 문제가 ^[4]동등하다는 것을 깨닫고 즉시 이중성 이론을 추측했다.단치히는 1948년 ^[3]1월 5일 출판되지 않은 보고서 "선형 불평등에 관한 정리"에서 공식적인 증거를 제공했다.단치히의 작품은 1951년에 대중에게 공개되었다.전후 몇 년 동안, 많은 산업체들이 그들의 일상 계획에 그것을 적용했다.

단치히의 원래 예는 70명의 직업에 70명을 할당하는 최적의 방법을 찾는 것이었다.최적의 할당을 선택하기 위해 모든 순열을 테스트하는 데 필요한 컴퓨팅 능력은 매우 큽니다. 가능한 구성의 수는 관측 가능한 우주의 입자 수를 초과합니다.그러나 문제를 선형 프로그램으로 상정하고 심플렉스 알고리즘을 적용하면 최적의 해결책을 찾는 데 몇 분밖에 걸리지 않습니다.선형 프로그래밍의 이면에 있는 이론은 점검해야 할 가능한 해결책의 수를 크게 줄여줍니다.

선형 프로그래밍 문제는 1979년 ^[5]레오니드 카치얀에 의해 다항식 시간에 해결 가능한 것으로 처음 나타났지만, 1984년 나렌드라 카르마르카(Narendra Karmarkar)가 선형 프로그래밍 ^[6]문제를 해결하기 위한 새로운 내부 포인트 방법을 도입하면서 이 분야에서 더 큰 이론적이고 실용적인 돌파구가 열렸다.

사용하다

선형 프로그래밍은 여러 가지 이유로 널리 사용되는 최적화 분야입니다.운영 연구의 많은 실제 문제들은 선형 프로그래밍 ^[3]문제로 표현될 수 있습니다.네트워크 플로우 문제나 멀티 커머시티 플로우 문제 등 선형 프로그래밍의 특정 특수한 케이스는 솔루션을 위한 전문 알고리즘에 대한 많은 연구가 이루어졌을 정도로 중요한 것으로 간주됩니다.다른 유형의 최적화 문제에 대한 많은 알고리즘은 LP 문제를 하위 문제로 해결함으로써 작동합니다.역사적으로, 선형 프로그래밍의 아이디어는 이중성, 분해, 볼록성의 중요성과 일반화와 같은 최적화 이론의 많은 중심 개념에 영감을 주었습니다.마찬가지로, 리니어 프로그래밍은 미시경제학의 초기 형성에 많이 사용되었고, 현재는 기획, 생산, 운송, 기술 등 기업 경영에 활용되고 있다.현대의 관리 문제는 끊임없이 변화하고 있지만, 대부분의 기업은 한정된 리소스로 수익을 극대화하고 비용을 최소화하고자 합니다.구글은 유튜브 동영상을 ^[7]안정시키기 위해 선형 프로그래밍을 사용한다.따라서 많은 문제가 선형 프로그래밍 문제로 특징지어질 수 있습니다.

표준형식

표준 형식은 선형 프로그래밍 문제를 설명하는 가장 직관적이고 일반적인 형식입니다.다음 세 부분으로 구성됩니다.

최대화할 선형 함수

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

:

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

f (

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

1,

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

)

=

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

1

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

+

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

2 ({

displaystyle

f

(x_{1

},

x_{

2})=

c_{1}x_{1}+c_{2

})

}x_{2}}

다음 형식의 문제 제약 사항

예.

{\displaystyle {time}a_{11}x_{1}+a_{12}x_{2}\leq b_{1}x_{1}+leq b_{2}\a_{31)x_{1}+leq b_{32}x_{2}\le

비음수 변수

예.

{displaystyle}x_{1}\geq 0\x_{2}\geq 0\end{display}

이 문제는 보통 매트릭스 형식으로 표현되며, 그 후 다음과 같이 됩니다.

\displaystyle \max\{,\mathbf {c} ^{\mathbf {T} } \mathbb {x} \in \mathbb {R} ^{n} \land A \mathbf {x} \leq \mathbf {b} \geq \ } } }

최소화 문제, 대체 형태 제약 문제, 부정적인 변수와 관련된 문제 등과 같은 다른 형태는 항상 표준 형태에서 동등한 문제로 고쳐 쓸 수 있다.

예

한 농부가 밀이나 보리를 심거나 둘 중 하나를 심을 수 있는 농경지(예: Lkm²)를 가지고 있다고 가정합니다.농부는 제한된 양의 비료 Fkg과 살충제 Pkg을 가지고 있다.밀 1평방 킬로미터 당 F 킬로그램의 비료와₁ P 킬로그램의 농약을 필요로₁ 하는 반면, 보리 1평방 킬로미터 당 F 킬로그램의 비료와₂ P 킬로그램의 농약을 필요로₂ 한다.S를 1평방킬로미터당 밀의 판매가격으로 하고₂ S를 보리의 판매가격으로 합니다₁.밀과 보리가 심어진 땅의 면적을 각각 x와₂ x로₁ 나타내면 x와₂ x에 대한₁ 최적의 값을 선택함으로써 이익을 극대화할 수 있습니다.이 문제는 다음과 같은 선형 프로그래밍 문제를 표준 형식으로 나타낼 수 있습니다.

$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}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ 1 + $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ 2 $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ † $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ 2 { $displaystyle S_{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$	(비료 한도)
	$\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(농약 제한)
	$x_{1}\geq 0,x_{2}\geq 0$	(마이너스 영역에 심습니다).

매트릭스 형식에서 이는 다음과 같습니다.

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

S

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

S

{\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}}

2

]{

displaystyle

{

begin

{

bmatrix }S_{1}\end {bmatrix}{\begin {bmatrix}x_{1}\x_{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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\end{bmatrix}}.

1

{\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\end{bmatrix}}.

1

{\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\end{bmatrix}}.

[ L

{\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 {\begin{bmatrix}0\\0\end{bmatrix}}.

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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\end{bmatrix}}.

x 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 {\begin{bmatrix}0\\0\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 {\begin{bmatrix}0\\0\end{bmatrix}}.

。\ display {

begin

{

bmatrix }

1

&

\

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

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

}

증강 폼(슬랙 폼)

심플렉스 알고리즘의 공통 형식을 적용하기 위해 선형 프로그래밍 문제를 증강 형식으로 변환할 수 있습니다.이 형식은 부등식을 제약조건의 동등성으로 대체하기 위해 음이 아닌 느슨한 변수를 도입한다.이 문제는 다음 블록 매트릭스 형식으로 기술할 수 있습니다.

z

최대화(\

displaystyle

z

z

{\mathbf {c} ^{T}&\0\mathbf {A}&\mathbf {I} \end{bmatrix} {\mathbf {x} \\mathbf {s} \end{bmatrix} = 0matrix

\displaystyle \mathbf {x} \geq 0,\mathbf {s} \geq 0}

$\mathbf {s}$ 서 s $\$ 는 $\mathbf {s}$ 새로 도입된 슬랙 변수, $\$ 는 $\mathbf {x}$ 결정 변수, $\displaystyle$ z는 $z$ 최대화할 변수입니다.

예

위의 예는 다음과 같은 증강 형식으로 변환됩니다.

$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}$ $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ 1 + $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ 2 $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ † $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ 2 { $displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2$ }		(점화 함수)
대상:	$x_{1}+x_{2}+x_{3}=L$	(표준 제약)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F$	(표준 제약)
	$P_{1}\cdot x_{2}\cdot x_{2}+x_{5}=P$	(표준 제약)
	$x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\geq 0 .$

$x_{3},x_{4},x_{5}$ 서 $x_{3},x_{4},x_{5}$ 3, $x_{3},x_{4},x_{5}$ 4, x $({$ 는 $x_{3},x_{4},x_{5}$ (음수가 아닌) 느슨한 변수로, 이 예에서 미사용 면적, 미사용 비료의 양 및 미사용 농약의 양을 나타냅니다.

매트릭스 형식에서 이는 다음과 같습니다.

z

최대화(\

displaystyle

z

z

{\displaystyle\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0&1&1&0&0&0&0&F_{1}&F_{2}&0&1&0\0&P_{1}&P_{2}&0&1\\end{bmatrix}{\begin{bmatrix}}{\x_{1}\x_{2}\x_{4}\end{5}\end{bmatrix}=sbegin{matrix}\x_0\xbegin{1}\x_{2}L\F\P\end{bmatrix},{\begin{bmatrix}x_{1}\x_{2}\x_{3}\x_{4}\end{bmatrix}\geq 0.}

이중성

원시 문제로 불리는 모든 선형 프로그래밍 문제는 이중 문제로 변환될 수 있으며, 이는 원시 문제의 최적 값에 대한 상한을 제공합니다.매트릭스 형식에서는 다음과 같이 근본적인 문제를 표현할 수 있습니다.

Ax b b, x 0 0에 따라 cx를^T 최대화합니다.

해당 대칭 이중 문제를 해결합니다.

Ay c c, y 0 0에 따라^T 최소화합니다^T.

대체 기본 공식은 다음과 같습니다.

Ax † b에 따른 cx^T 최대화

대응되는 비대칭 이중 문제를 안고 있습니다.

Ay = c, y 0 0을 조건으로^T 최소화합니다^T.

이중성 이론에는 두 가지 기본 아이디어가 있다.하나는 (대칭 듀얼의 경우) 듀얼 선형 프로그램의 듀얼이 원래 기본 선형 프로그램이라는 사실이다.또한 선형 프로그램에 대한 모든 실행 가능한 해법은 이중의 목적 함수의 최적 값에 대한 경계를 부여합니다.약한 이중성 정리는 실현 가능한 해에서 이중의 객관적 함수 값이 항상 실현 가능한 해에서 원점의 객관적 함수 값보다 크거나 같다는 것을 말한다.강한 이중성 정리는 원형이 최적해 x를^* 가지면, 쌍대 또한 최적해^* y를 가지며 cx^T^*^T^*=by를 갖는다는 것이다.

선형 프로그램은 제한되지 않거나 실행 불가능할 수도 있습니다.이원성 이론은 만약 원형이 무한하다면, 이원성은 약한 이원성 정리에 의해 실현 불가능하다고 우리에게 말한다.마찬가지로, 쌍수가 제한되지 않은 경우, 원점은 실현 불가능해야 합니다.그러나 듀얼과 프라이머리는 모두 실현 불가능할 수 있습니다.자세한 내용은 이중 선형 프로그램을 참조하십시오.

바리에이션

커버/패킹 이중화

커버 LP는 다음과 같은 형태의 선형 프로그램입니다.

최소화: 기준^T,

대상:Ay^T c c, y 0 0,

행렬 A와 벡터 b와 c가 음이 아닌 경우.

피복 LP의 이중은 다음과 같은 형태의 선형 프로그램인 패킹 LP입니다.

최대화: cx^T,

대상: Ax b b, x 0 0,

행렬 A와 벡터 b와 c가 음이 아닌 경우.

예

LP 커버 및 패킹은 일반적으로 조합 문제의 선형 프로그래밍 이완으로 발생하며 근사 ^[8]알고리즘 연구에 중요합니다.예를 들어 세트 패킹 문제의 LP 완화, 독립 세트 문제, 매칭 문제가 LP 패킹이다.세트 커버 문제, 정점 커버 문제, 지배적인 세트 문제의 LP 완화도 LP를 커버하고 있습니다.

그래프의 부분 색상을 찾는 것은 커버 LP의 또 다른 예입니다.이 경우 그래프의 각 정점에 대해 하나의 제약 조건이 있고 그래프의 각 독립적인 집합에 대해 하나의 변수가 있습니다.

보완적 느슨함

상보적 느슨성 정리를 이용하여 원점에 대한 최적해만을 알 수 있을 때 이중에 대한 최적해를 얻을 수 있다.이 정리는 다음과 같이 기술한다.

x =(x₁, x₂, ..., x_n)가 원시 실현 가능하고 y =(y₁, y₂, ..., y_m)가 이중 실현 가능하다고 가정합니다.(w₁, w₂, ..., w_m)는 대응하는 초기 슬랙 변수를 나타내고 (z₁, z₂, ..., z_n)는 대응하는 듀얼 슬랙 변수를 나타냅니다.x와 y는 각각의 문제에 최적입니다.

x_j_j z = 0, j = 1, 2, ..., n, 및
w_i_i y = 0(i = 1, 2, ..., m일 경우).

따라서 primal의 i번째 슬랙 변수가 0이 아니면 dual의 i번째 변수는 0이 됩니다.마찬가지로 이중의 j번째 슬랙 변수가 0이 아닌 경우, 원점의 j번째 변수는 0이 됩니다.

최적화를 위해 필요한 이 조건은 상당히 단순한 경제 원칙을 전달한다.표준 형식(최대화 시)에서 제약이 있는 원시 리소스에 여유가 있는 경우(즉, "리프트오버"가 있는 경우) 해당 자원의 추가 수량은 가치가 없어야 합니다.마찬가지로, 이중(그림자) 가격 비음성 제약 요건이 느슨한 경우, 즉 가격이 0이 아닌 경우에는 공급이 부족해야 한다('남은' 없음).

이론.

최적의 솔루션 존재

기하학적으로 선형 제약조건은 볼록 다면체인 실현 가능한 영역을 정의합니다.선형 함수는 볼록 함수이며, 이는 모든 로컬 최소값이 전역 최소값임을 나타냅니다. 마찬가지로 선형 함수는 오목 함수이며, 이는 모든 로컬 최대값이 전역 최대값임을 의미합니다.

최적의 솔루션은 두 가지 이유로 존재할 필요가 없습니다.첫째, 제약조건에 일관성이 없는 경우 실현 가능한 해결책은 존재하지 않습니다.예를 들어, 제약 x 2 2와 x cannot 1을 동시에 만족시킬 수 없습니다.이 경우 LP는 실현 불가능하다고 할 수 있습니다.둘째, 폴리토프가 목적함수의 구배방향(여기서 목적함수의 구배는 목적함수의 계수의 벡터)으로 제한되지 않을 경우, 목적함수의 유한값보다 더 나은 것이 항상 가능하기 때문에 최적값이 달성되지 않는다.

다면체의 최적 꼭지점(및 광선)

그 이외의 경우, 실현 가능한 해법이 존재하고 제약조건 집합이 경계가 되어 있는 경우, 선형함수는 볼록함수와 오목함수 모두이기 때문에 볼록함수의 최대원리(또는 오목함수의 최소원리)에 의해 항상 제약조건 집합의 경계에서 최적값이 달성된다.그러나, 어떤 문제들은 명확한 최적의 해결책을 가지고 있다. 예를 들어, 선형 부등식 시스템에 대한 실현 가능한 해결책을 찾는 문제는 목표 함수가 0 함수인 선형 프로그래밍 문제이다(즉, 모든 곳에서 0 값을 갖는 상수 함수).목적 함수의 제로 함수에 대한 이러한 실현 가능성 문제의 경우, 만약 두 개의 다른 해법이 있다면, 해법의 모든 볼록한 조합은 해법이다.

폴리토프의 꼭지점은 기본 실현 가능한 해라고도 불린다.이 이름을 선택한 이유는 다음과 같습니다.d는 변수의 수를 나타냅니다.그러면 선형 부등식의 기본 정리는 (실현 가능한 문제의 경우) LP의 모든 정점^* x에 대해, LP로부터 일련의 d(또는 그 이하) 부등식 제약이 존재하며, 우리가 이러한 d 제약 조건을 동등하게 취급할 때, 고유한 해는 x가 된다는^* 것을 암시한다.따라서 LP 솔루션의 연속체가 아닌 모든 제약 조건 집합(이산 집합)의 특정 하위 집합을 통해 이러한 정점을 연구할 수 있다.이 원리는 선형 프로그램을 해결하기 위한 심플렉스 알고리즘의 기초가 됩니다.

알고리즘

선형 프로그래밍 문제에서 일련의 선형 제약조건은 이러한 변수에 가능한 값의 볼록한 실행 가능한 영역을 생성합니다.2-변수의 경우 이 영역은 볼록한 단순 다각형 모양입니다.

기저 교환 알고리즘

단치히의 심플렉스 알고리즘

1947년 조지 단치히에 의해 개발된 심플렉스 알고리즘은 폴리토프의 정점에 실현 가능한 솔루션을 구성한 후 최적치에 확실히 도달할 때까지 폴리토프의 가장자리에 있는 정점으로 가는 경로를 따라 걸음으로써 LP 문제를 해결한다.많은 실제 문제에서 "고정"이 발생합니다. 즉, 많은 피벗이 목표 ^[9]^[10]함수의 증가 없이 만들어집니다.드문 실제 문제이지만, 심플렉스 알고리즘의 일반 버전은 실제로 "사이클"^[10]될 수 있습니다.사이클을 피하기 위해 연구자들은 새로운 피벗 ^[11]^[12]^[9]^[10]^[13]^[14]규칙을 개발했습니다.

실제로 심플렉스 알고리즘은 매우 효율적이며 사이클링에 대한 특정 예방조치를 취하면 글로벌 최적치를 찾을 수 있습니다.심플렉스 알고리즘은 "랜덤" 문제를 효율적으로 해결하는 것으로 입증되었으며,^[15] 이는 실제 문제에 ^[9]^[16]대한 동작과 유사합니다.

그러나 심플렉스 알고리즘은 최악의 경우 동작이 좋지 않습니다.Klee와 Minty는 심플렉스 메서드가 ^[9]^[12]^[13]문제의 크기를 지수적으로 나타내는 여러 단계를 수행하는 선형 프로그래밍 문제의 패밀리를 구축했습니다.사실, 한동안 선형 프로그래밍 문제가 다항식 시간, 즉 복잡도 클래스 P에서 해결 가능한지 여부는 알려지지 않았다.

십자형 알고리즘

Dantzig의 심플렉스 알고리즘과 마찬가지로 criss-cross 알고리즘은 베이스 간에 피벗하는 베이스 교환 알고리즘입니다.단, criss-cross 알고리즘은 실현가능성을 유지할 필요는 없지만 실현가능한 베이스에서 실현 불가능한 베이스로 피벗할 수 있습니다.criss-cross 알고리즘은 선형 프로그래밍에 대한 다항식 시간 복잡성을 가지지 않습니다.두 알고리즘 모두 최악의 ^[14]^[17]경우 치수 D의 (교란된) 큐브의 두 모서리^D, 즉 Klee-Minty 큐브를 방문합니다.

내부점

다면체 집합의 정점 사이를 횡단하여 최적의 솔루션을 찾는 심플렉스 알고리즘과 달리 내부 포인트 방법은 실행 가능한 영역의 내부를 통과합니다.

Khachiyan에 이은 Ellipsoid 알고리즘

이것은 선형 프로그래밍에서 발견된 최초의 최악의 다항식 시간 알고리즘입니다.변수가 n개이고 L 입력 비트로 부호화할 수 있는 문제를 해결하기 위해 이 알고리즘은 O $O(n^{6}L)$ 6 $)\displaystyle$ O $(n^{6}L)}$ 회 $O(n^{6}L)$ ^[5] $O(n^{6}L)$ 됩니다.레오니드 카치얀은 1979년 타원체법의 도입으로 이 해묵은 복잡성 문제를 해결했다.수렴 분석에는 선행(실수) 방법, 특히 Naum Z가 개발한 반복 방법이 있다. Arkadi Nemirovski와 D의 Shor와 근사 알고리즘.유딘이.

카르마르카 투영 알고리즘

Khachiyan의 알고리즘은 선형 프로그램의 다항 시간 용해성을 확립하는 데 획기적인 중요성을 가지고 있었다.이 알고리즘은 특별히 구성된 선형 프로그램 패밀리를 제외한 모든 패밀리에 대해 심플렉스 방법이 더 효율적이기 때문에 계산상의 돌파구가 아니었다.

그러나 Khachiyan의 알고리즘은 선형 프로그래밍에 대한 새로운 연구 라인에 영감을 주었습니다.1984년 N. Karmarkar는 선형 프로그래밍을 위한 투영 방법을 제안했다.Karmarkar의 알고리즘은^[6] Khachiyan의 최악의^[5] 다항식 경계( $O(n^{3.5}L)$ ( $O(n^{3.5}L)$ . $O(n^{3.5}L)$ L $))$ 에서 개선되었습니다.\ $displaystyle$ O ( $n^{3.5$ } $L)}).$ Karmarkar는 그의 알고리즘이 심플렉스 방식보다 실용적인 LP에서 훨씬 빨랐다고 주장했는데, 이는 내부 포인트 방식에 ^[18]큰 관심을 불러일으켰습니다.카르마르카르의 발견 이후, 많은 내부 지점 방법들이 제안되고 분석되었다.

바이디아의 87 알고리즘

1987년, Vaidya는 O $O(n^{3})$ ^[19] $O(n^{3})$ 3) $O(n^{3})$ { $displaystyle$ O $(n^{3})$ 시간으로 $O(n^{3})$ $O(n^{3})$ 되는 알고리즘을 제안했습니다.

바이디아의 89 알고리즘

1989년, Vaidya는 $O(n^{2.5})$ O( $O(n^{2.5})$ 2.5 $)$ {^[20] $displaystyle O(n^{2$ .5 $})$ $O(n^{2.5})$ 으로 $O(n^{2.5})$ $O(n^{2.5})$ 되는 알고리즘을 개발했습니다.정식적으로는 알고리즘은 $O((n+d)^{1.5}nL)$ O( $O((n+d)^{1.5}nL)$ ( $O((n+d)^{1.5}nL)$ n + $O((n+d)^{1.5}nL)$ ) 1. $O((n+d)^{1.5}nL)$ L $)$ {{ $displaystyle$ O( ( $n$ + $d )^{$ 1 $.5}nL}}$ 의 $O((n+d)^{1.5}nL)$ 산술 연산을 사용합니다. $d$ 서 d ${\displaystyle$ d $}$ 는 $d$ 제약 조건의 수, $n$ {\ $displaystyle$ n $}$ 은 $n$ 변수의 수, $L$ {\ $displaystyle$ L $}$ 은 $L$ 비트의 수입니다.

입력 희소성 시간 알고리즘

2015년에 Lee와 Sidford는 O ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ ~ ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ ( n ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ z ( ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ ) + ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ 2 ) ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ L ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ ( \ $displaystyle$ { $O$ } ( $nz$ ( $A$ ) + $d$ ^ {2} { \ $sqrt {d}$ L } }^[21] ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ 으로 ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ 해결할 수 있음을 보여주었다. 여기서 $nnz(A)$ ( $)$ { $display nstyle$ n} $（ A$ )최악의 $경우$ }L $O(n^{2.5}L)$ )}입니다 $.$

전류 행렬 곱셈 시간 알고리즘

2019년 코헨, 리, 송은 O ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ ( ( n ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ + ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ .5 ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ - ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ / ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ + ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ 2 + ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ / ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ ) $)(\displaystyle {O}(n^{\obe }+n^{2.$ 5- $\alpha /2}+n^{2+1/6})$ 로 ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ 시간을 개선했다. $L)}$ 시간 ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ , $\omega$ {\ $displaystyle \omega}$ 는 $\omega$ 행렬 곱셈의 지수, $\alpha$ α {\ $displaystyle \alpha}$ 는 $\alpha$ 행렬 ^[22]곱셈의 이중 지수이다. $\alpha$ α $\alpha$ {\ $displaystyle$ $\alpha }$ 는 $\alpha$ n $n\times n$ × $n\times n$ $n\times n^{\alpha }$ $행렬$ 에 $n\times n$ n $n\times n^{\alpha }$ {\ $displaystyle$ n $\times$ $n\times n$ n $^{\alpha}$ $O(n^{2})$ 을 $n\times n^{\alpha }$ O $O(n^{2})$ 2) ${\displaystyle$ O $(n^2})$ 시간으로 $O(n^{2})$ 곱할 수 있는 최대수로 정의된다.리, 송, 장의 후속작에서는 다른 ^[23]방법으로 같은 결과를 재현한다.이 두 알고리즘은 $\omega =2$ $\omega =2$ $\omega =2$ ${\displaystyle \obe = 2$ } $\alpha =1$ α $\alpha =1$ $\alpha =1$ {\ $displaystyle \alpha = 1$ 일 때 ${\tilde {O}}(n^{2+1/6}L)$ O ${\tilde {O}}(n^{2+1/6}L)$ ~ ( ${\tilde {O}}(n^{2+1/6}L)$ 2 + $1$ / $L$ ) { $displaystyle {O}$ ( n^ ${\tilde {O}}(n^{2+1/6}L)$ 2 + 1 / 6 $L )$ }인 ${\tilde {O}}(n^{2+1/6}L)$ 채로 ${\tilde {O}}(n^{2+1/6}L)$ .장, 송, 웨인스타인 및 장에 의해 O ${\tilde {O}}(n^{2+1/6}L)$ 2 ${\tilde {O}}(n^{2+1/6}L)$ + ${\tilde {O}}(n^{2+1/6}L)$ / ${\tilde {O}}(n^{2+1/6}L)$ L $)({displaystyle$ ${O})(n^{2$ + ${\tilde {O}}(n^{2+1/6}L)$ $1$ / $6}$ $L)$ 가 ${\tilde {O}}(n^{2+1/6}L)$ O ${\tilde {O}}(n^{2+1/18}L)$ 2 $+$ / $18$ L ${\tilde {O}}(n^{2+1/18}L)$ ^[24]로 ${\tilde {O}}(n^{2+1/6}L)$ 되었습니다.

내부점법과 심플렉스 알고리즘의 비교

현재의 의견은 심플렉스 기반 방법과 내부 포인트 방법의 좋은 구현의 효율성은 선형 프로그래밍의 일상적인 적용에 유사하다는 것이다.단, 특정 유형의 LP 문제에 대해서는 한 유형의 솔버가 다른 유형의 솔버보다 우수할 수 있으며(때로는 훨씬 우수할 수 있음), 내부 포인트 방법과 심플렉스 기반 방법에 의해 생성된 솔루션의 구조가 크게 달라서 일반적으로 후자의 ^[25]액티브 변수 세트가 작을 수 있습니다.

미해결 문제 및 최근 작업

컴퓨터 과학에서 해결되지 않은 문제:

선형 프로그래밍은 강력한 다항식 시간 알고리즘을 허용합니까?

(컴퓨터 사이언스의 미해결 문제 증가)

선형 프로그래밍 이론에는 몇 가지 미해결 문제가 있는데, 그 해답은 수학의 근본적인 돌파구를 나타내며 대규모 선형 프로그램을 풀 수 있는 우리의 능력에 있어 잠재적으로 큰 진보를 나타낼 수 있다.

LP는 강력한 다항 시간 알고리즘을 허용합니까?
LP는 엄밀하게 상호 보완적인 솔루션을 찾기 위해 강력한 다항식 시간 알고리즘을 허용합니까?
LP는 계산의 실수(단위 비용) 모델에서 다항 시간 알고리즘을 허용합니까?

스티븐 스메일은 21세기의 가장 큰 미해결 문제 18개 중 하나로 이와 밀접하게 관련된 문제들을 언급했습니다.스메일의 말에 따르면, 문제의 세 번째 버전은 "선형 프로그래밍 이론의 주요 미해결 문제"이다.타원체 방법 및 내부점 기법과 같은 약한 다항식 시간에 선형 프로그래밍을 해결하기 위한 알고리즘이 존재하지만, 제약 조건의 수와 변수의 수에서 다항식 시간 성능을 강하게 허용하는 알고리즘은 아직 발견되지 않았다.이러한 알고리즘의 개발은 이론적으로 매우 흥미로울 것이며, 아마도 큰 LP를 해결하는 데 있어서도 실질적인 이득을 얻을 수 있을 것이다.

허쉬의 추측은 최근 더 높은 차원에 대해 반증되었지만, 여전히 다음과 같은 의문점을 남겨두고 있다.

다항식-시간 단순 변형을 유도하는 피벗 규칙이 있습니까?
모든 다상 그래프는 다항식 경계가 있는 직경을 가지고 있습니까?

이러한 질문은 심플렉스와 유사한 방법의 성능 분석 및 개발에 관한 것입니다.지수 시간 이론 성능에도 불구하고 실제로 심플렉스 알고리즘의 엄청난 효율성은 다항식 또는 심지어 강하게 다항식 시간에 실행되는 심플렉스의 변화가 있을 수 있음을 암시합니다.특히 LP가 강력한 다항식 시간에 해결될 수 있는지 여부를 결정하는 접근법으로서 그러한 변형이 존재하는지 여부를 아는 것은 매우 실용적이고 이론적으로 중요하다.

심플렉스 알고리즘과 그 변형은 에지 추종 알고리즘의 패밀리에 속하며, 폴리토프의 가장자리를 따라 정점에서 정점으로 이동함으로써 선형 프로그래밍 문제를 해결한다고 해서 붙여진 이름입니다.즉, LP 폴리토프의 두 꼭지점 사이의 최대 에지 수에 따라 이론적인 성능이 제한됩니다.그 결과, 우리는 다상 그래프의 최대 그래프 이론 직경을 아는 데 관심이 있다.모든 폴리톱이 지수 이하의 직경을 갖는다는 것이 증명되었다.최근 허쉬 추측의 반증은 어떤 폴리토프가 초다항 직경을 가지고 있는지 증명하는 첫 번째 단계이다.이러한 폴리토프가 존재하는 경우, 다항식 시간에 에지 추종 변형을 실행할 수 없습니다.폴리토프 직경에 대한 질문은 수학적으로 독립적입니다.

심플렉스 피벗 방식은 기본(또는 이중) 실현 가능성을 유지합니다.한편, CRISS-Cross 피벗 방식은 실현가능성(프라이머리 또는 듀얼)을 유지하지 않습니다.원래의 실현가능성, 이중의 실현가능성, 또는 원시와 이중의 실현불능의 베이스에 임의의 순서로 액세스 할 수 있습니다.이러한 유형의 피벗 방법은 1970년대부터 ^{[citation needed]}연구되어 왔습니다.기본적으로, 이러한 방법들은 선형 프로그래밍 문제 하에서 배치 폴리토프 상의 최단 피벗 경로를 찾으려고 시도합니다.폴리톱 그래프와 달리 배열 폴리톱 그래프는 지름이 작은 것으로 알려져 일반 폴리톱 ^[14]직경에 대한 질문을 해결하지 않고 강력한 다항식 시간 십자 피벗 알고리즘의 가능성을 가능하게 한다.

알 수 없는 정수

모든 미지의 변수가 정수여야 하는 경우 이 문제를 정수 프로그래밍(IP) 또는 정수 선형 프로그래밍(ILP) 문제라고 합니다.최악의 경우 효율적으로 해결할 수 있는 선형 프로그래밍과는 대조적으로, 정수 프로그래밍 문제는 많은 실제 상황(유계 변수를 가진 문제) NP-hard에 있습니다.0 – 1 정수 프로그래밍 또는 이진 정수 프로그래밍(BIP)은 변수가 (임의 정수가 아닌) 0 또는 1이어야 하는 정수 프로그래밍의 특별한 경우입니다.이 문제는 NP-hard로도 분류되며, 실제로 결정 버전은 Karp의 21개의 NP-완전 문제 중 하나였습니다.

알 수 없는 변수 중 일부만 정수여야 하는 경우 이 문제를 혼합 정수(선형) 프로그래밍(MIP 또는 MILP) 문제라고 합니다.이것들은 ILP 프로그램보다 훨씬 일반적이기 때문에 일반적으로 NP-hard이기도 합니다.

그러나 IP 및 MIP 문제에는 효율적으로 해결할 수 있는 몇 가지 중요한 서브클래스가 있습니다.특히 제약조건 매트릭스가 완전히 단일한 문제이며 제약조건의 우측이 정수이거나 시스템이 Total Dual Integrity(TDI; 총 이중 적분성) 속성을 갖는 문제가 가장 두드러집니다.

정수 선형 프로그램을 해결하기 위한 고급 알고리즘은 다음과 같습니다.

절단면법
분기 및 경계
분기 및 절단
지점 및 가격
문제가 추가적인 구조를 가지고 있는 경우 지연된 컬럼 생성을 적용할 수 있습니다.

이러한 정수 프로그래밍 알고리즘은 Padberg와 Beasley에 의해 논의된다.

통합 선형 프로그램

실변수에서의 선형 프로그램은 정수값만으로 이루어진, 즉 적분된 적어도 하나의 최적 솔루션을 갖는 경우 적분이라고 한다.마찬가지로, $P=\{x\mid Ax\geq 0\}$ P $=$ { $P=\{x\mid Ax\geq 0\}$ A $P=\{x\mid Ax\geq 0\}$ 0 $}$ { $displaystyle$ P=\{ $x\mid$ Ax $\geq$ 0 $\}$ 은 $P=\{x\mid Ax\geq 0\}$ 모든 유계 실현 가능한 목표 함수 c에 대해 선형 프로그램 $\{\max cx\mid x\in P\}$ $\{\max cx\mid x\in P\}$ x $\{\max cx\mid x\in P\}$ P $}$ { $displaystyle \{\max cx\mid$ x\ $in$ P\}}가 $\{\max cx\mid x\in P\}$ $x^{*}$ x $\$ in P $\}$ 인 경우 적분이라고 한다 $x^{*}$ 1977년 Edmonds와 Giles에 의해 관측된 바와 같이, 모든 유계 실현 가능한 적분 목적 함수 c에 대해 $\{\max cx\mid x\in P\}$ 선형 $\{\max cx\mid x\in P\}$ { $\{\max cx\mid x\in P\}$ c $\{\max cx\mid x\in P\}$ p x $\{\max cx\mid x\in P\}$ P $}$ 의 최적값({\displaystyle \{\ $max cx\mid$ x\in P $\})$ 이 정수라면 $다면체$ P{ $displaystyle$ P $}$ 는 $P$ 적분이라고 말할 수 있다.

적분 선형 프로그램은 문제의 대체 특성을 제공하기 때문에 조합 최적화의 다면체 측면에서 가장 중요하다.특히, 어떤 문제든, 솔루션의 볼록한 껍질은 일체형 다면체이다. 이 다면체가 훌륭하고 콤팩트한 기술을 가지고 있다면, 우리는 어떤 선형 목표에서도 최적의 실현 가능한 솔루션을 효율적으로 찾을 수 있다.반대로, 선형 프로그래밍 완화가 필수적이라는 것을 증명할 수 있다면, 그것은 실현 가능한 (통합적인) 솔루션의 볼록한 선체에 대한 바람직한 기술이다.

전문용어는 문헌 전체에서 일관성이 없기 때문에 다음 두 가지 개념을 구별하는 데 주의해야 한다.

앞의 절에서 설명한 정수 선형 프로그램에서는 변수가 정수로 강제 구속되며, 이 문제는 일반적으로 NP-hard이다.
이 절에서 기술된 적분 선형 프로그램에서 변수는 정수로 구속되지 않고 오히려 연속 문제가 항상 적분 최적값을 갖는다는 것을 어떻게든 증명했고, 이 최적값은 모든 다항식 크기 선형 프로그램이 다항식 시간에 해결될 수 있기 때문에 효율적으로 찾을 수 있다..

다면체가 일체형임을 증명하는 한 가지 일반적인 방법은 그것이 완전히 단일모형이라는 것을 보여주는 것이다.정수 분해 특성 및 전체 이중 적분성을 포함한 다른 일반적인 방법이 있습니다.기타 잘 알려진 통합 LP에는 일치하는 폴리토프, 격자 다면체, 서브모듈러 흐름 다면체 및 두 개의 일반화 다면체/g-다면체의 교차가 포함된다(예: Schrijver 2003 참조).

솔버 및 스크립트(프로그래밍) 언어

허가 라이선스:

이름.	면허증.	간단한 정보
게코	MIT 라이선스	대규모 LP, QP, QCQP, NLP 및 MIP 최적화를 해결하기 위한 오픈 소스 라이브러리
동작하지 않다	Apache v2	구글의 오픈 소스 리니어 프로그래밍 해결사
표모	BSD	대규모 선형, 혼합 정수 및 비선형 최적화를 위한 오픈 소스 모델링 언어
쑤안슈	Apache v2	Java에서 LP, QP, SOCP, SDP, SQP를 해결하기 위한 오픈 소스 최적화 알고리즘 스위트

카피레프트(호기) 라이선스:

이름.	면허증.	간단한 정보
카소워리 구속 해결사	LGPL	선형 평등과 불평등 시스템을 효율적으로 해결하는 증분 제약 해결 도구 키트
CLP	CPL	COIN-OR의 LP 솔버
째깍째깍	GPL	GNU 선형 프로그래밍 키트. 네이티브 C API 및 기타 언어용 다수의 서드파티제 래퍼를 갖춘 LP/MILP 솔버입니다.플로우 네트워크의 스페셜리스트 지원.AMP와 같은 GNU MathProg 모델링 언어 및 번역기를 번들합니다.
코코아	GPL	다양한 목표 함수를 가진 선형 방정식 시스템을 점진적으로 풀기 위한 라이브러리
R프로젝트	GPL	통계 컴퓨팅과 그래픽스를 위한 프로그래밍 언어와 소프트웨어 환경

MINTO(Mixed Integer Optimizer, 분기 및 바인딩 알고리즘을 사용하는 정수 프로그래밍 솔버)는 공개적으로 사용 가능한 소스^[26] 코드를 가지고 있지만 오픈 소스는 아닙니다.

자체 라이선스:

이름.	간단한 정보
AIMMS	선형, 혼합 정수 및 비선형 최적화 모델을 모델링할 수 있는 모델링 언어입니다.또한 구속조건 프로그래밍을 위한 도구도 제공합니다.알고리즘은 휴리스틱스나 정확한 방법(브런치 앤 컷 또는 컬럼 생성 등)의 형태로도 구현할 수 있습니다.이 툴은 CPLEX 등의 적절한 솔버를 호출하여 당면한 최적화 문제를 해결합니다.학사 자격증은 무료입니다.
앰프	사용 가능한 학생 제한 버전(500개의 변수 및 500개의 제약 조건)으로 대규모 선형, 혼합 정수 및 비선형 최적화에 널리 사용되는 모델링 언어입니다.
Analytica	일반적인 모델링 언어 및 대화형 개발 환경.영향도를 통해 사용자는 의사결정 변수, 목표 및 제약조건에 대한 노드를 사용하여 문제를 그래프로 공식화할 수 있습니다.Analytica Optimizer Edition에는 선형, 혼합 정수 및 비선형 솔버가 포함되어 있으며 문제에 맞는 솔버를 선택합니다.XPRESS, 구로비, 아르텔리스 니트로, 모섹 등 다른 엔진도 플러그인으로 사용할 수 있다.
AP 모니터	MATLAB 및 Python에 대한 API.MATLAB, Python 또는 웹 인터페이스를 통해 선형 프로그래밍(LP) 문제의 예를 해결합니다.
컴플렉스	여러 프로그래밍 언어용 API와 함께 인기 있는 해결사이며 모델링 언어도 있으며 AIMMS, AMPL, GAMS, MPL, OpenOpt, OPL Development Studio 및 TOMLAB와 함께 작동합니다.학구용 무료.
Excel 솔버 함수	함수 평가가 재계산 셀을 기반으로 하는 스프레드시트에 맞게 조정된 비선형 솔버입니다.Excel의 표준 애드온으로서 이용 가능한 베이직 버전.
포트 MP
GAMS
IMSL 수치 라이브러리	C/C++, Fortran, Java 및 C#/에서 사용할 수 있는 산술 및 통계 알고리즘 모음.NET. IMSL 라이브러리의 최적화 루틴에는 제약이 없는, 선형 및 비선형 제약이 있는 최소화 및 선형 프로그래밍 알고리즘이 포함됩니다.
린도	확률적 프로그래밍 확장을 가진 선형, 정수, 2차, 원뿔 및 일반 비선형 프로그램의 대규모 최적화를 위한 API를 갖춘 솔버.연속 변수와 이산 변수를 가진 일반 비선형 프로그램에 대해 전지구적으로 최적의 솔루션을 찾기 위한 글로벌 최적화 절차를 제공합니다.또한 Monte-Carlo 시뮬레이션을 최적화 프레임워크에 통합하기 위한 통계 샘플링 API가 있다.대수 모델링 언어(LINGO)가 있으며 스프레드시트(What's Best) 내에서 모델링이 가능합니다.
메이플	기호 및 수치 컴퓨팅을 위한 범용 프로그래밍 언어입니다.
매트랩	수치 계산을 위한 범용 매트릭스 지향 프로그래밍 언어입니다.MATLAB에서 선형 프로그래밍을 수행하려면 기본 MATLAB 제품 외에 Optimization Toolbox가 필요합니다. 사용 가능한 루틴은 INTLINPROG 및 LINPROG입니다.
매스캐드	WYSIWYG 산술 편집기.선형 및 비선형 최적화 문제를 모두 해결하기 위한 기능이 있습니다.
매스매티카	기호 및 숫자 기능을 포함한 수학용 범용 프로그래밍 언어입니다.
모섹	여러 언어(C++, java,.net, Matlab 및 python)에 대한 API를 통한 대규모 최적화 솔루션.
NAG 수치 라이브러리	수치 알고리즘 그룹이 여러 프로그래밍 언어(C, C++, Fortran, Visual Basic, Java 및 C#) 및 패키지(MATLAB, Excel, R, LabVIEW)를 위해 개발한 수학 및 통계 루틴 모음입니다.NAG 라이브러리의 최적화 장에는 스퍼스 및 비스퍼스 선형 구속조건 행렬의 선형 프로그래밍 문제에 대한 루틴과 비선형, 비선형 또는 비선형 함수의 제곱합 최적화를 위한 루틴이 포함되어 있습니다.NAG 라이브러리에는 로컬 및 글로벌 최적화 및 연속 또는 정수 문제에 대한 루틴이 있습니다.
OptimJ	Java 기반 모델링 언어(무료 버전 사용 가능)^[27]^[28]로 최적화할 수 있습니다.
SAS/또는	선형, 정수, 비선형, 무파생, 네트워크, 조합 및 제약 최적화용 솔버 제품군, 대수 모델링 언어 OPTMODEL 및 특정 문제/시장을 겨냥한 다양한 수직 솔루션. 이 모든 것이 SAS 시스템과 완전히 통합됩니다.
SCIP	MIP에 중점을 둔 범용 제약 정수 프로그래밍 솔버. Zimpl 모델링 언어와 호환됩니다.학회용으로 무료이며 소스 코드로 제공됩니다.
XPRESS	대규모 선형 프로그램, 2차 프로그램, 일반 비선형 및 혼합 정수 프로그램용 솔버.여러 프로그래밍 언어에 대한 API를 가지고 있으며, 모델링 언어 Mosel을 가지고 있으며, MPL, GAMS와 함께 작동합니다.학술용 무료입니다.
VisSim	동적 시스템을 시뮬레이션하기 위한 시각적 블록 다이어그램 언어입니다.

「」를 참조해 주세요.

메모들

^ ^a ^b Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (3rd ed.). CRC Press. p. 1. ISBN 978-1498710169.
^ ^a ^b Alexander Schrijver (1998). Theory of Linear and Integer Programming. John Wiley & Sons. pp. 221–222. ISBN 978-0-471-98232-6.
^ ^a ^b ^c George B. Dantzig (April 1982). "Reminiscences about the origins of linear programming" (PDF). Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Archived from the original on May 20, 2015.
^ ^a ^b ^c Dantzig, George B.; Thapa, Mukund Narain (1997). Linear programming. New York: Springer. p. xxvii. ISBN 0387948333. OCLC 35318475.
^ ^a ^b ^c Leonid Khachiyan (1979). "A Polynomial Algorithm for Linear Programming". Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.
^ ^a ^b Narendra Karmarkar (1984). "A New Polynomial-Time Algorithm for Linear Programming". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150. S2CID 7257867.
^ (PDF) https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf. {{cite web}}:누락 또는 비어 있음 title=(도움말)
^ Vazirani (2001, 페이지 112)
^ ^a ^b ^c ^d 단치히 & 타파 (2003)
^ ^a ^b ^c Padberg(1999년)
^ 싱겁다(1977년)
^ ^a ^b 머티(1983년)
^ ^a ^b 파파디미트리우 & 슈타이글리츠
^ ^a ^b ^c Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.
^ 보그워트(1987년)
^ Todd (2002)
^ Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483.
^ Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.
^ Vaidya, Pravin M. (1987). An algorithm for linear programming which requires ${O}(((m+n)n^{2}+(m+n)^{1.5}n)L)$ arithmetic operations. 28th Annual IEEE Symposium on Foundations of Computer Science. FOCS.
^ Vaidya, Pravin M. (1989). "Speeding-up linear programming using fast matrix multiplication". 30th Annual Symposium on Foundations of Computer Science. 30th Annual Symposium on Foundations of Computer Science. FOCS. pp. 332–337. doi:10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.
^ Lee, Yin-Tat; Sidford, Aaron (2015). Efficient inverse maintenance and faster algorithms for linear programming. FOCS '15 Foundations of Computer Science. arXiv:1503.01752.
^ Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018). Solving Linear Programs in the Current Matrix Multiplication Time. 51st Annual ACM Symposium on the Theory of Computing. STOC'19. arXiv:1810.07896.
^ Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. Conference on Learning Theory. COLT'19. arXiv:1905.04447.
^ Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). Faster Dynamic Matrix Inverse for Faster LPs. arXiv:2004.07470.
^ Illés, Tibor; Terlaky, Tamás (2002). "Pivot versus interior point methods: Pros and cons". European Journal of Operational Research. 140 (2): 170. CiteSeerX 10.1.1.646.3539. doi:10.1016/S0377-2217(02)00061-9.
^ "COR@L – Computational Optimization Research At Lehigh". lehigh.edu.
^ http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf Munster 대학의 혼합 모델 조립 라인에 대한 최적화 모델에 사용되는 OptimJ
^ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 OptimJ는 반복 게임에 대한 대략적인 서브게임-완벽 평형 계산 기법에 사용됩니다.

레퍼런스

Kantorovich, L. V. (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [A new method of solving some classes of extremal problems]. Doklady Akad Sci SSSR. 28: 211–214.
F. L. 히치콕:여러 출처에서 여러 지역으로의 제품 배포, 수학 및 물리학 저널, 20, 1941, 224–230.
G.B Dantzig: 선형 부등식의 대상이 되는 변수의 선형 함수의 최대화, 1947.T.C.에서 339–347페이지 발행.Koopmans(편집):생산 및 할당 액티비티 분석(뉴욕 런던 1951년)(Wiley & Chapman-Hall)
J. E. 비즐리 편집장선형 및 정수 프로그래밍이 발전합니다.옥스퍼드 사이언스, 1996년 (조사집)
Bland, Robert G. (1977). "New Finite Pivoting Rules for the Simplex Method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647.
Karl-Heinz Borgwardt, Simplex Algorithm: 확률론적 분석, 알고리즘과 조합론, Volume 1, Springer-Verlag, 1987. (랜덤 문제에 대한 평균 거동)
리처드 W. 코틀, ED베이직 조지 B 단치히Stanford Business Books, Stanford University Press, California, Stanford, 2003. (조지 B의 논문 선택). 단치히)
조지 B.단치히와 무쿤드엔.타파, 1997년선형 프로그래밍 1: 소개.스프링거-벨라그.
조지 B.단치히와 무쿤드엔.타파, 2003년선형 프로그래밍 2: 이론과 확장.Springer-Verlag. (포괄적으로 피벗 및 내부점 알고리즘, 대규모 문제, Dantzig에 따른 분해 등)Wolfe와 Benders, 확률 프로그래밍 도입)
Edmonds, Jack; Giles, Rick (1977). "A Min-Max Relation for Submodular Functions on Graphs". Studies in Integer Programming. Annals of Discrete Mathematics. Vol. 1. pp. 185–204. doi:10.1016/S0167-5060(08)70734-9. ISBN 978-0-7204-0765-5.
Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.
Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley (ed.). Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky.
Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547. (comprehensive reference to classical approaches).
에바 D. 네링과 알버트 W. 터커, 1993년, 리니어 프로그램과 관련 문제, 학술 출판사.(표준)
M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999. (Oddyseus의 출장 세일즈맨 문제를 특징으로 하는 정수 선형 프로그래밍의 도입과 함께 원시 및 듀얼 심플렉스 알고리즘과 투영 알고리즘에 대해 주의 깊게 기술)
Christos H. Papadimitriou 및 Kenneth Steiglitz, 조합 최적화: 알고리즘과 복잡성, 새로운 서문으로 수정된 공화국, 도버.(컴퓨터 사이언스
Michael J. Todd (February 2002). "The many facets of linear programming". Mathematical Programming. 91 (3): 417–436. doi:10.1007/s101070100261. S2CID 6464735. (국제수학프로그래밍심포지엄 초청조사)
Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Springer Verlag.
Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 978-3-540-65367-7. (컴퓨터 사이언스)

추가 정보

Dmitris Alevras와 Manfred W. Padberg, Linear Optimization and Extensions, Universitext, Springer-Verlag, 2001. (Padberg의 솔루션 문제)
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 978-3-540-65620-3.{{cite book}}: CS1 유지: 여러 이름: 작성자 목록 (링크) 4장: 선형 프로그래밍: 페이지 63~94.선형 프로그래밍을 위한 무작위 하프플레인 교차 알고리즘을 설명합니다.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP1: INTEGER 프로그래밍, 페이지 245. (컴퓨터 과학, 복잡도 이론)
Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. (수학자 및 컴퓨터 과학자를 위한 사전 소개)
Cornelis Roos, Tamas Terlaky, Jean-Philippe Vial, Interior Point Methods for Linear Optimization, 제2판, Springer-Verlag, 2006년)
Alexander Schrijver (2003). Combinatorial optimization: polyhedra and efficiency. Springer.
알렉산더 슈라이버, 선형 및 정수 프로그래밍 이론John Wiley & sons, 1998, ISBN 0-471-98232-6 (수학)
Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice. CRC Press. ISBN 978-1-498-71016-9.
Gerard Sierksma; Diptesh Ghosh (2010). Networks in Action; Text and Computer Exercises in Network Optimization. Springer. ISBN 978-1-4419-5512-8. (선형 최적화 모델링)
H. P. Williams, 수학 프로그래밍 모델 구축, 제5판, 2013년. (모델링)
Stephen J. Wright, 1997, SIAM, Primal-Dual Interior-Point Methods (대학원 수준)
Yinyu Ye, 1997, Interior Point Algorithms: 이론과 분석, Wiley (고졸)
지글러, 귄터 M., 1994년 뉴욕 스프링거-벨라그 폴리토프 강의 1장-3절과 6장-7절. (기하학)

외부 링크

[SierksmaZwols2015-1] Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (3rd ed.). CRC Press. p. 1. ISBN 978-1498710169.

[Schrijver1998-2] Alexander Schrijver (1998). Theory of Linear and Integer Programming. John Wiley & Sons. pp. 221–222. ISBN 978-0-471-98232-6.

[dantzig1982-3] George B. Dantzig (April 1982). "Reminiscences about the origins of linear programming" (PDF). Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Archived from the original on May 20, 2015.

[:0-4] Dantzig, George B.; Thapa, Mukund Narain (1997). Linear programming. New York: Springer. p. xxvii. ISBN 0387948333. OCLC 35318475.

[khachiyan79-5] Leonid Khachiyan (1979). "A Polynomial Algorithm for Linear Programming". Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.

[karmarkar84-6] Narendra Karmarkar (1984). "A New Polynomial-Time Algorithm for Linear Programming". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150. S2CID 7257867.

[7] (PDF) https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf. {{cite web}}:누락 또는 비어 있음 title=(도움말)

[8] Vazirani (2001, 페이지 112)

[DT03-9] 단치히 & 타파 (2003)

[Padberg-10] Padberg(1999년)

[Bland-11] 싱겁다(1977년)

[Murty-12] 머티(1983년)

[PS-13] 파파디미트리우 & 슈타이글리츠

[FukudaTerlaky-14] Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.

[15] 보그워트(1987년)

[Todd-16] Todd (2002)

[Roos-17] Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483.

[Strang-18] Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.

[19] Vaidya, Pravin M. (1987). An algorithm for linear programming which requires ${O}(((m+n)n^{2}+(m+n)^{1.5}n)L)$ arithmetic operations. 28th Annual IEEE Symposium on Foundations of Computer Science. FOCS.

[20] Vaidya, Pravin M. (1989). "Speeding-up linear programming using fast matrix multiplication". 30th Annual Symposium on Foundations of Computer Science. 30th Annual Symposium on Foundations of Computer Science. FOCS. pp. 332–337. doi:10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.

[21] Lee, Yin-Tat; Sidford, Aaron (2015). Efficient inverse maintenance and faster algorithms for linear programming. FOCS '15 Foundations of Computer Science. arXiv:1503.01752.

[22] Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018). Solving Linear Programs in the Current Matrix Multiplication Time. 51st Annual ACM Symposium on the Theory of Computing. STOC'19. arXiv:1810.07896.

[23] Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. Conference on Learning Theory. COLT'19. arXiv:1905.04447.

[24] Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). Faster Dynamic Matrix Inverse for Faster LPs. arXiv:2004.07470.

[25] Illés, Tibor; Terlaky, Tamás (2002). "Pivot versus interior point methods: Pros and cons". European Journal of Operational Research. 140 (2): 170. CiteSeerX 10.1.1.646.3539. doi:10.1016/S0377-2217(02)00061-9.

[26] "COR@L – Computational Optimization Research At Lehigh". lehigh.edu.

[27] ttp://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf Munster 대학의 혼합 모델 조립 라인에 대한 최적화 모델에 사용되는 OptimJ

[28] ttp://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 OptimJ는 반복 게임에 대한 대략적인 서브게임-완벽 평형 계산 기법에 사용됩니다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

v t 상보성 문제와 알고리즘
상보성의 문제	선형 프로그래밍(LP) 2차 프로그래밍(QP) 선형보완성문제(LCP) 혼합 선형(MLCP) 혼합(MCP) 비선형(NCP)
베이스 교환 알고리즘	심플렉스(Dantzig) 개정된 심플렉스 십자 십자형 렘케

Search

선형 프로그래밍

네임스페이스

더

목차

역사

사용하다

표준형식

예

증강 폼(슬랙 폼)

예

이중성