단체법 (알고리즘)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 개요
4. 알고리즘
5. 예제
6. 고급 주제
7. 다른 알고리즘
8. 선형-분수 계획법(Linear-fractional programming)
참조

1. 개요

단체법은 1947년 조지 단치히가 고안한 선형 계획법 문제를 푸는 알고리즘이다. 제2차 세계 대전 중 군사 작전 계획 연구에서 영감을 받아 개발되었으며, 산업, 금융 등 다양한 분야에서 활용된다. 단체법은 표준형으로 변환된 선형 계획 문제를 심플렉스 표를 사용하여 나타내고, 피벗 연산을 통해 기저 변수를 변경하며 해를 찾아나가는 방식으로 작동한다. 진입 변수와 이탈 변수 선택 규칙, 초기 표준형 표 찾기 과정이 알고리즘의 핵심 요소이다.

단체법은 개선된 심플렉스 알고리즘, 퇴화, 효율성 등의 고급 주제를 가지며, 다른 알고리즘과 비교하여 선형 계획법 문제를 해결하는 데 사용된다. 선형 계획법의 일반화인 선형-분수 계획법에도 적용될 수 있다.

더 읽어볼만한 페이지

1947년 컴퓨팅 - 트랜지스터
트랜지스터는 전류 증폭 및 스위칭 기능을 하는 반도체 소자로, BJT와 MOSFET 등의 다양한 유형이 개발되어 현대 전자기기의 핵심 기반이 되었으며, 특히 MOSFET은 집적회로 기술 발전에 크게 기여했다.
선형 계획법 - 자료 포락 분석
자료 포락 분석(DEA)은 여러 입력과 출력을 가진 의사결정단위(DMU)의 효율성을 측정하는 방법으로, 선형 계획법을 활용해 경험적 생산 기술 경계를 추정하며, 생산 함수 형태를 가정할 필요 없이 여러 입출력을 동시에 고려할 수 있지만, 변수 선택에 민감하다는 단점도 있다.
선형 계획법 - 일차 부등식
일차 부등식은 미지수의 최고차항이 1차인 부등식으로, ax > b, ax < b, ax ≥ b, ax ≤ b (단, a ≠ 0)의 형태로 표현되며, 해를 구하는 것은 부등식을 만족하는 미지수 x의 값을 찾는 것이고, 연립일차부등식은 각 부등식을 동시에 만족하는 해를 구하는 것을 목표로 한다.
최적화 알고리즘 - 기댓값 최대화 알고리즘
최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.

단체법 (알고리즘)
개요
종류	선형 계획법 알고리즘
역사
개발자	조지 단치히
알고리즘 특징
범주	최적화 알고리즘
자료구조	행렬
복잡도	지수 시간 (최악의 경우)
최적	지역 최적 (선형 계획 문제에선 전역 최적)
활용
활용 분야	운송 문제 할당 문제 기타 선형 계획 문제

2. 역사

1947년 미국의 수리경제학자 조지 단치히가 심플렉스법을 고안하였다.

조지 단치히는 제2차 세계 대전 중 미국 육군 항공대에서 탁상용 계산기를 사용하여 계획 방법을 연구했다. 1946년, 그의 동료는 그가 다른 직업을 갖지 못하도록 계획 프로세스를 기계화하도록 제안했다. 단치히는 바실리 레온티예프의 연구에서 영감을 받아 문제를 선형 부등식으로 공식화했지만, 당시에는 공식의 일부로 목표를 포함하지 않았다. 목표가 없으면 엄청난 수의 해가 가능하므로 "최상의" 가능한 해를 찾기 위해 목표 자체를 지정하는 대신 목표를 달성하는 방법을 설명하는 군사 지정 "기본 규칙"을 사용해야 했다. 단치히의 핵심 통찰력은 이러한 기본 규칙의 대부분을 최대화해야 하는 선형 목적 함수로 변환할 수 있다는 것을 깨달은 것이다.^[7] 심플렉스 방법의 개발은 점진적으로 이루어졌으며 약 1년 동안 진행되었다.^[8]

1947년 중반 단치히가 공식의 일부로 목적 함수를 포함시킨 후, 문제는 수학적으로 더 다루기 쉬워졌다. 단치히는 그가 잘못 이해했던 그의 교수 예르지 네이만의 수업 과제(그리고 실제로 나중에 해결된) 중 하나가 선형 계획법 알고리즘을 찾는 데 적용할 수 있다는 것을 깨달았다. 이 문제는 0과 1 사이의 범위에 있고 르베그 적분 형태로 표현된 선형 제약을 만족하는 연속 변수에 대한 일반 선형 계획법의 라그랑주 승수의 존재를 찾는 것과 관련되었다. 단치히는 나중에 박사 학위를 받기 위해 그의 "숙제"를 논문으로 발표했다. 이 논문에서 사용된 열 기하학은 단치히에게 심플렉스 방법이 매우 효율적일 것이라고 믿게 만드는 통찰력을 주었다.^[9]

3. 개요

선형 계획법에서 심플렉스 알고리즘은 표준형 문제, 즉 다음 형태의 문제에 적용된다.

목적 함수를 최대화한다.
: c1x1 + c2x2 + ... + cnxn
문제 제약 조건:
: a11x1 + a12x2 + ... + a1nxn = b1
: a21x1 + a22x2 + ... + a2nxn = b2
: ...
: am1x1 + am2x2 + ... + amnxn = bm
: x1, x2, ..., xn ≥ 0

실행 가능 영역은 볼록 다포체를 이루며, 이 다포체의 꼭짓점은 기저 실행 가능 해(BFS)라고 불린다. 목적 함수가 실행 가능 영역에서 최대값을 가지면, 이 값은 적어도 하나의 꼭짓점에서 가진다. 심플렉스 알고리즘은 다포체의 모서리를 따라 더 큰 목적 값을 갖는 꼭짓점으로 이동한다.

선형 계획법의 해는 두 단계로 이루어진다.

3. 1. 표준형

선형 계획법을 표준형으로 변환하는 방법은 다음과 같다.^[15]

0이 아닌 하한이 있는 각 변수에 대해, 변수와 경계의 차이를 나타내는 새로운 변수를 도입한다. 그런 다음 원래 변수를 치환하여 제거한다. 예를 들어, 다음 제약 조건이 주어졌다고 가정한다.

::

x_1 \ge 5

새로운 변수 $y_1$ 을 도입하면 다음과 같다.

::

\begin{align} y_1 = x_1 - 5\\x_1 = y_1 + 5 \end{align}

두 번째 방정식을 사용하여 선형 계획법에서 $x_1$ 을 제거할 수 있다. 이러한 방식으로 모든 하한 제약 조건을 비음수 제약으로 변경할 수 있다.

남은 각 부등식 제약에 대해, 해당 제약을 등식 제약으로 변경하기 위해 ''슬랙 변수''라고 하는 새로운 변수를 도입한다. 이 변수는 부등식의 양변 간의 차이를 나타내며, 비음수로 간주된다. 예를 들어, 다음과 같은 부등식이 있다.

::

\begin{align}x_2 + 2x_3 &\le 3\\

x_4 + 3x_5 &\ge 2

\end{align}

위 부등식은 다음과 같이 바뀐다.

::

\begin{align}x_2 + 2x_3 + s_1 &= 3\\

x_4 + 3x_5 - s_2 &= 2\\

s_1,\, s_2 &\ge 0\end{align}

이러한 형태의 부등식은 대수적 조작을 수행하기가 훨씬 쉽다. 두 번째 부등식과 같이 ≥가 나타나는 부등식에서 일부 저자는 도입된 변수를 ''잉여 변수''라고 부른다.

각 제한 없는 변수는 선형 계획법에서 제거된다. 이것은 두 가지 방법으로 수행할 수 있는데, 하나는 변수가 나타나는 방정식 중 하나에서 변수를 풀고 치환하여 변수를 제거하는 것이다. 다른 방법은 변수를 두 개의 제한된 변수의 차이로 대체하는 것이다. 예를 들어, $z_1$ 이 제한이 없다면 다음과 같이 작성한다.

::

\begin{align}&z_1 = z_1^+ - z_1^-\\&z_1^+,\, z_1^- \ge 0\end{align}

이 방정식을 사용하여 선형 계획법에서 $z_1$ 을 제거할 수 있다.

이 과정이 완료되면, 실행 가능한 영역은 다음과 같은 형태가 된다.

:

\mathbf{A}\mathbf{x} = \mathbf{b},\, \forall  \ x_i \ge 0

또한

\mathbf{A}

의 랭크가 행의 수와 같다고 가정하는 것이 유용하다. 그렇지 않으면

\mathbf{A}\mathbf{x} = \mathbf{b}

시스템에 제거할 수 있는 중복 방정식이 있거나, 시스템이 일관성이 없어 선형 계획법에 해가 없기 때문에 일반성을 잃지 않는다.^[16]

3. 2. 심플렉스 표(Simplex tableau)

표준 형식의 선형 계획법은 다음과 같은 형태의 심플렉스 표로 나타낼 수 있다.^[17]

1	$-\mathbf{c}^T$	0
$\mathbf{0}$	$\mathbf{A}$	$\mathbf{b}$

첫 번째 행은 목적 함수를 정의하고, 나머지 행은 제약 조건을 지정한다. 첫 번째 열의 0은 벡터 $\mathbf{b}$ 와 동일한 차원의 영 벡터를 나타낸다.^[17] 만약 $\mathbf{A}$ 의 열을 재정렬하여 $p$ 차 단위 행렬( $\mathbf{A}$ 의 행 수)을 포함하도록 할 수 있다면, 이 표는 ''정규 형식''이라고 한다.^[17] 단위 행렬의 열에 해당하는 변수를 ''기저 변수''라고 하고, 나머지 변수를 ''비기저 변수'' 또는 ''자유 변수''라고 한다. 비기저 변수의 값을 0으로 설정하면, 기저 변수의 값은 $\mathbf{b}$ 의 항목으로 쉽게 얻을 수 있으며, 이 해는 기저 가능 해이다.

기저 가능 해가 주어지면, 0이 아닌 변수에 해당하는 열을 비특이 행렬로 확장할 수 있다. 해당 표에 이 행렬의 역행렬을 곱하면 결과는 정규 형식의 표가 된다.^[18]

예를 들어 다음과 같은 표를 생각해 보자.

1	$-\mathbf{c}^T_B$	$-\mathbf{c}^T_D$	0
0	$I$	$\mathbf{D}$	$\mathbf{b}$

행 추가 변환을 적용하여 목적 함수에서 계수 $\mathbf{c}^T_B$ 를 제거할 수 있다. 이 과정을 ''프라이싱 아웃(pricing out)''이라고 하며, 다음과 같은 정규 표가 생성된다.^[19]

1	0	$-\bar{\mathbf{c}}^T_D$	$z_B$
0	$I$	$\mathbf{D}$	$\mathbf{b}$

여기서 $z_B$ 는 해당 기저 가능 해에서의 목적 함수 값이다. 업데이트된 계수는 ''상대 비용 계수''라고도 하며, 비기저 변수에 대한 목적 함수의 변화율이다.^[19]

3. 3. 피벗 연산(Pivot operations)

기본 실행 가능 해에서 인접한 기본 실행 가능 해로 이동하는 기하학적 연산은 ''피벗 연산''으로 구현된다. 먼저, 비기본 열에서 0이 아닌 ''피벗 요소''가 선택된다. 이 요소를 포함하는 행은 역수를 곱하여 이 요소를 1로 변경한 다음, 행의 배수를 다른 행에 더하여 열의 다른 항목을 0으로 변경한다. 결과적으로, 피벗 요소가 행 ''r''에 있으면 해당 열은 항등 행렬의 ''r''번째 열이 된다. 이 열에 대한 변수는 이제 기본 변수가 되어, 연산 전 항등 행렬의 ''r''번째 열에 해당하는 변수를 대체한다. 실제로 피벗 열에 해당하는 변수는 기본 변수 집합에 들어가며 ''진입 변수''라고 하고, 대체되는 변수는 기본 변수 집합을 떠나며 ''이탈 변수''라고 한다. 테이블은 여전히 정규 형식에 있지만, 기본 변수 집합은 하나의 요소로 변경된다.^[13]^[19]

4. 알고리즘

선형 계획법이 정규 꼴 표로 주어졌을 때, 단체법(심플렉스법)은 연속적인 피벗 연산을 수행하여 개선된 기본 가능 해를 찾는다. 각 단계에서 피벗 요소는 해를 개선하는 방향으로 선택된다.

단체법의 일반적인 흐름은 다음과 같다.

1. 제한 표준형 변환: 선형 계획 문제를 제한 표준형으로 변형한다.

슬랙 변수를 추가하여 부등식을 등식으로 바꾼다.
인공 변수를 추가하고, 목적 함수 ''z''를 최대화(또는 최소화)하는 문제로 만든다.

2. 심플렉스 표 작성: 문제의 계수를 정리한 심플렉스 표(Simplex Tableau)를 작성한다.

3. 기저 변수 선택: 식의 수만큼 기저 변수를 정한다. 목적 함수 z는 반드시 기저 변수로 선택한다.

4. 최적해 확인: 초기 기저 변수에서 얻어진 연립 방정식의 해가 최적인지 확인한다. 최적이면 종료하고, 그렇지 않으면 다음 단계를 수행한다.

5. 기저 변수와 비기저 변수 조합 변경:

비기저 변수 중에서 새롭게 기저 변수로 할 변수를 선택한다. 여러 개가 존재할 경우, 가장 효과가 높은 변수를 선택한다. (피벗 열 결정)
기저에서 제거할 변수를 결정한다. 증가 한계(상수항을 새 기저 변수의 계수로 나눈 값)를 기준으로 결정하는 경우가 많다. (피벗 행 결정)
피벗을 중심으로 소거법 등을 이용하여 새로운 실행 가능 해를 구하고, 4단계로 돌아가 반복한다.

4. 1. 진입 변수 선택

일반적으로 진입 변수는 0에서 양수로 증가하기 때문에, 이 변수에 대한 목적 함수의 미분 값이 음수이면 목적 함수의 값은 감소한다. 즉, 테이블의 목적 행에서 해당 항목이 양수이도록 피벗 열을 선택하면 목적 함수의 값이 증가한다.^[20]

목적 행의 항목이 양수인 열이 여러 개 있는 경우, 기본 변수 집합에 추가할 열을 선택하는 것은 다소 임의적이며, Devex 알고리즘^[21]과 같은 여러 "진입 변수 선택 규칙"이 개발되었다.^[20]

목적 행의 모든 항목이 0 이하이면, 진입 변수를 선택할 수 없으며, 실제로 해가 최적이다.

4. 2. 이탈 변수 선택

피벗 열이 선택되면, 결과 해가 실행 가능해야 한다는 요구 사항에 따라 피벗 행을 선택한다. 우선, 피벗 열의 양수 항목만 고려하는데, 이는 들어오는 변수의 값이 음수가 아님을 보장하기 위해서이다. 만약 피벗 열에 양수 항목이 없다면, 들어오는 변수는 해가 실행 가능한 상태를 유지하면서 모든 음수가 아닌 값을 가질 수 있다. 이 경우 목적 함수는 아래로 무제한이 되어 최소값이 없다.

다른 모든 기본 변수가 양수를 유지하도록 피벗 행을 선택해야 한다. 이는 들어오는 변수의 결과 값이 최소일 때 발생한다. 즉, 피벗 열이 ''c''이면 피벗 행 ''r''은 다음을 만족하도록 선택한다.

:

b_r / a_{rc}\,

''a''_''rc'' > 0인 모든 ''r''에 대해 최소값. 이를 최소 비율 테스트라고 한다.^[20] 최소값이 여러 행에서 나타나는 경우, 변수 탈락 선택 규칙을 사용하여 결정을 내릴 수 있다.^[22]

4. 3. 초기 표준형 표 찾기

일반적으로 선형 계획법은 표준 형식으로 주어지지 않으므로, 심플렉스 알고리즘을 시작하기 전에 동등한 표준 테이블을 찾아야 한다. 이는 인공 변수를 도입하여 수행할 수 있다. 항등 행렬의 열이 이러한 변수에 대한 열 벡터로 추가된다. 제약 방정식에 대한 b 값이 음수이면, 항등 행렬 열을 추가하기 전에 방정식이 부정된다. 이는 실행 가능한 해의 집합이나 최적의 해를 변경하지 않으며, 슬랙 변수가 초기 실행 가능한 해를 구성하도록 보장한다. 새로운 테이블은 표준 형식으로 되어 있지만, 원래 문제와 동일하지 않다. 따라서 인공 변수의 합과 같은 새로운 목적 함수가 도입되고, 심플렉스 알고리즘이 적용되어 최소값을 찾는다. 수정된 선형 계획법을 ''Phase I'' 문제라고 한다.^[23]

Phase I 문제에 적용된 심플렉스 알고리즘은 새로운 목적 함수의 최소값으로 종료되어야 한다. 이는 음이 아닌 변수의 합이기 때문에 그 값은 0 아래로 제한되기 때문이다. 최소값이 0이면 인공 변수를 결과 표준 테이블에서 제거하여 원래 문제와 동등한 표준 테이블을 생성할 수 있다. 그런 다음 심플렉스 알고리즘을 적용하여 해를 찾을 수 있으며, 이 단계를 ''Phase II''라고 한다. 최소값이 양수이면, 인공 변수가 모두 0인 Phase I 문제에 대한 실행 가능한 해가 없다. 이는 원래 문제에 대한 실행 가능한 영역이 비어 있음을 의미하므로 원래 문제에는 해가 없다.^[13]^[19]^[25]

5. 예제

다음은 선형 계획법 문제의 예시와 심플렉스법을 이용한 풀이 과정을 보여준다.
예제 1:X₁과 X₂에 관한 제약 조건과 목적 함수 P는 다음과 같다.

제약 조건
목적 함수	Max. P = QX₁ + RX₂ (단, 상수 Q, R은 양수)

목적 함수 P를 최대화하는 해 (X₁, X₂)는 다음과 같이 구할 수 있다.

1. 다음 연립 방정식들의 해를 구한다.

식 (1)과 식 (2)
식 (1)과 식 (3)
식 (1)과 식 (4)
식 (1)과 식 (5)
식 (2)와 식 (3)
식 (2)와 식 (4)
식 (2)와 식 (5)
식 (3)과 식 (4)
식 (3)과 식 (5)
식 (4)와 식 (5)

2. 위에서 구한 10개의 해 중에서 목적 함수 P 값을 최대화하는 해를 찾는다.
예제 2: (참고)

다음 선형 계획법 문제를 심플렉스법으로 풀어보자.
최소화:Z = -2x - 3y - 4z
제약 조건:

1. 표준형 변환: 여유 변수 s와 t를 추가하여 표준형으로 변환한다.

: $\begin{bmatrix} 1 & 2 & 3 & 4 & 0 & 0 & 0 \\ 0 & 3 & 2 & 1 & 1 & 0 & 10 \\ 0 & 2 & 5 & 3 & 0 & 1 & 15 \end{bmatrix}$

기본 변수: s, t
기본 가능 해: x = y = z = 0, s = 10, t = 15

2. 피벗 열 선택: 열 2, 3, 4 중에서 선택 가능하다. 여기서는 열 4를 선택한다.

3. 피벗 행 선택: z 값을 계산하여 최소값을 가지는 행을 선택한다.

행 2: 10 / 1 = 10
행 3: 15 / 3 = 5
따라서 행 3을 피벗 행으로 선택한다.

4. 피벗 연산 수행: :

\begin{bmatrix}    1 &            -\frac{2}{3} &             -\frac{11}{3} & 0 & 0 & -\frac{4}{3} & -20 \\    0 &  \frac{7}{3} &   \frac{1}{3} & 0 & 1 &  -\frac{1}{3} &  5 \\    0 &  \frac{2}{3} &   \frac{5}{3} & 1 & 0 &  \frac{1}{3} & 5    \end{bmatrix}

기본 변수: z, s
기본 가능 해: x = y = t = 0, z = 5, s = 5

5. 최적해 확인: 목적 행에 음수가 없으므로 최적해에 도달했다.

:

Z = -20 + \frac{2}{3}x+\frac{11}{3}y+\frac{4}{3}t

따라서 Z의 최소값은 -20이다.

6. 고급 주제

단체법은 실제 문제에서 매우 효율적으로 작동하며, 푸리에-모츠킨 소거법과 같은 이전의 방법들보다 훨씬 개선되었다.^[32] 그러나 1972년 클리와 민티는 클리-민티 큐브라는 예시를 통해 단체법의 최악의 경우 복잡도가 지수 시간임을 보였다.^[32] 즉, 특정한 경우에는 단체법이 매우 오랜 시간이 걸릴 수 있다는 것이다. 이후 단체법의 거의 모든 변형에 대해 성능이 좋지 않은 선형 계획법 문제들이 존재한다는 것이 밝혀졌다.

단체법이 다항 시간 내에 문제를 해결할 수 있는 변형이 존재하는지는 여전히 풀리지 않은 문제이지만, 준지수 피벗 규칙은 알려져 있다.^[33]

2014년에는 단체법의 특정 변형이 NP-강력하다는 것이 증명되었다. 이는 알고리즘 실행 중에 암묵적으로 NP에 있는 모든 문제를 다항식 오버헤드로 해결할 수 있음을 의미한다. 또한, 주어진 입력에 대해 알고리즘 실행 중에 특정 변수가 기저에 들어가는지 여부를 결정하고, 주어진 문제를 해결하는 데 필요한 반복 횟수를 결정하는 것은 모두 NP-어려움 문제이다.^[34] 거의 동시에 출력을 계산하는 인공 피벗 규칙이 존재하며, 이는 PSPACE-완전하다는 것이 밝혀졌다.^[35] 2015년에는 단치히의 피벗 규칙 출력을 계산하는 것이 PSPACE-완전하다는 것이 증명되었다.^[36]

이러한 이론적인 결과에도 불구하고, 심플렉스 알고리즘은 실제 문제에서 놀라운 효율성을 보인다. 이러한 현상을 설명하기 위해 다양한 복잡도 척도가 개발되었다. 예를 들어, 심플렉스 알고리즘은 다양한 확률 분포 하에서 평균 사례 복잡도가 다항 시간 내에 해결된다.^[37]^[38] 즉, 평균적으로는 단체법이 빠르게 문제를 해결한다는 것이다. 일반 위상수학의 베어 범주 이론을 이용한 연구도 진행되었다.

심플렉스 알고리즘의 성능을 분석하는 또 다른 방법은 작은 변화에도 최악의 시나리오가 유지되는지, 아니면 해결 가능하게 되는지를 연구하는 것이다. 이를 스무딩 분석이라고 하며, 심플렉스 방법을 연구하기 위해 도입되었다. 연구 결과, 잡음이 있는 입력에 대한 심플렉스 방법의 실행 시간은 변수의 수와 섭동의 크기에 대해 다항식이다.^[39]^[40]

6. 1. 개선된 심플렉스 알고리즘

표준 심플렉스 알고리즘은 저장 및 계산 오버헤드가 크다. 이러한 구현은 "표준" 심플렉스 알고리즘이라고 불리며, 이 방식은 대규모 선형 계획법 문제를 해결하는 데 있어 비용이 매우 많이 드는 접근 방식이 될 수 있다.

개선된 심플렉스 알고리즘은 행렬 '''B'''의 가역적 표현을 활용하여 효율성을 높인다.^[24] 각 심플렉스 반복에서 필요한 데이터는 표의 첫 번째 행, 들어오는 변수에 해당하는 피벗 열, 그리고 우변이다. 피벗 열과 피벗 행은 '''B''' 행렬과 '''A'''를 사용한 행렬-벡터 곱셈을 포함하는 선형 방정식 시스템의 해를 사용하여 직접 계산할 수 있다.

대규모 선형 계획법 문제에서 '''A'''는 일반적으로 희소 행렬이며, '''B'''의 희소성을 활용하여 개선된 심플렉스 알고리즘은 표준 심플렉스 방법보다 훨씬 효율적이다. 상용 심플렉스 솔버는 개선된 심플렉스 알고리즘을 기반으로 한다.^[25]^[24]^[26]^[27]^[28]

6. 2. 퇴화(Degeneracy): 지체(Stalling)와 순환(Cycling)

기본 변수의 값이 모두 엄격하게 양수이면, 피벗은 목적 함수 값의 개선을 가져와야 한다. 이런 경우가 항상 발생하면, 기본 변수의 집합이 두 번 나타나지 않으며, 단순법은 유한한 단계 후에 종료되어야 한다. 기본 변수 중 적어도 하나가 0인 기본 실행 가능 해는 "퇴화"라고 불리며, 목적 함수 값의 개선이 없는 피벗을 발생시킬 수 있다. 이 경우 실제 해의 변화는 없으며, 기본 변수의 집합만 변경된다. 이러한 피벗이 여러 번 연속으로 발생하면 개선이 없다. 대규모 산업 응용 분야에서 퇴화는 흔하며, 이러한 "지체"는 주목할 만하다.

지체보다 더 심각한 것은 동일한 기본 변수 집합이 두 번 나타날 가능성인데, 이 경우 단순법의 결정적 피벗 규칙은 무한 루프 또는 "사이클"을 생성한다. 퇴화는 실제 상황에서 일반적이고, 지체는 흔하지만, 사이클은 실제 상황에서 드물다. 실제 사이클의 예는 파드버그에서 논의된다.^[25] 블랜드 규칙은 사이클을 방지하므로 단순법이 항상 종료됨을 보장한다.^[25]^[29]^[30] 또 다른 피벗 알고리즘인 교차 알고리즘은 선형 계획법에서 절대 사이클을 발생시키지 않는다.^[31]

자데 규칙 및 커닝햄 규칙과 같은 기록 기반 피벗 규칙은 특정 변수가 얼마나 자주 사용되는지 추적한 다음, 가장 적게 사용된 변수를 선호하여 지체 및 사이클 문제를 해결하려고 시도한다.

6. 3. 효율성

단순 방법(Simplex method)은 실제로는 매우 효율적이며, 푸리에-모츠킨 소거법과 같은 이전 방법보다 훨씬 개선되었다.^[32] 1972년 클리와 민티는 클리-민티 큐브를 예로 들어 단치히가 공식화한 단순 방법의 최악의 경우 복잡성이 지수 시간임을 보여주었다.^[32] 그 이후로, 이 방법의 거의 모든 변형에 대해, 성능이 좋지 않은 선형 계획법의 일족이 있다는 것이 밝혀졌다. 다항 시간을 갖는 변형이 있는지에 대한 여부는 열린 질문이지만, 준지수 피벗 규칙은 알려져 있다.^[33]

2014년에는 단순 방법의 특정 변형이 NP-강력하다는 것이 증명되었으며, 이는 알고리즘 실행 중에 암묵적으로 NP에 있는 모든 문제를 다항식 오버헤드로 해결하는 데 사용할 수 있음을 의미한다. 또한, 주어진 입력에 대한 알고리즘 실행 중에 주어진 변수가 기본에 들어가는지 여부를 결정하고 주어진 문제를 해결하는 데 필요한 반복 횟수를 결정하는 것은 모두 NP-어려움 문제이다.^[34] 거의 동시에 출력을 계산하는 인공 피벗 규칙이 존재하며, 이는 PSPACE-완전하다는 것이 밝혀졌다.^[35] 2015년에는 이것이 강화되어 단치히의 피벗 규칙의 출력을 계산하는 것이 PSPACE-완전하다는 것을 보여주었다.^[36]

심플렉스 알고리즘은 최악의 경우 지수 시간 복잡도를 가짐에도 불구하고 실제로는 효율적이라는 관찰 결과, 실제 효율성을 분석하고 정량화하여 다른 복잡성 척도가 개발되었다. 심플렉스 알고리즘은 다양한 확률 분포 하에서 평균 사례 복잡도가 다항 시간 내에 해결되며, 심플렉스 알고리즘의 정확한 평균 사례 성능은 랜덤 행렬에 대한 확률 분포의 선택에 따라 달라진다.^[37]^[38] 일반 위상수학의 베어 범주 이론을 사용하는 "전형적인 현상"을 연구하는 또 다른 접근 방식도 있다.

심플렉스 알고리즘의 성능을 분석하는 또 다른 방법은 작은 섭동 하에서 최악의 시나리오의 동작을 연구하는 것이다. 이는 최악의 시나리오가 작은 변화(구조적 안정성의 의미에서)에 안정적인지, 아니면 해결 가능하게 되는지를 알아보는 것이다. 스무딩 분석이라고 불리는 이 연구 분야는 심플렉스 방법을 연구하기 위해 특별히 도입되었다. 실제로, 잡음이 있는 입력에 대한 심플렉스 방법의 실행 시간은 변수의 수와 섭동의 크기에 대해 다항식이다.^[39]^[40]

7. 다른 알고리즘

선형 계획법 문제를 해결하기 위한 다른 알고리즘은 선형 계획법 문서에 설명되어 있다. 또 다른 기저 교환 피벗 알고리즘은 크리크로스 알고리즘이다.^[41]^[42] 내점법을 사용하는 선형 계획법을 위한 다항 시간 알고리즘에는 하지얀의 타원 알고리즘, 카르마르카의 사영 알고리즘, 경로 추적 알고리즘 등이 있다.^[14] 빅 M 방법은 단일 단계 심플렉스를 사용하여 선형 프로그램을 해결하기 위한 대체 전략이다.

8. 선형-분수 계획법(Linear-fractional programming)

선형 계획법(LP)에서 목적 함수는 선형 함수인 반면, 선형-분수 계획법(LFP)의 목적 함수는 두 개의 선형 함수의 비율이다. 즉, 선형 프로그램은 분모가 모든 곳에서 값 1을 갖는 상수 함수인 분수 선형 프로그램이다. 선형-분수 계획법은 단순 알고리즘^[43]^[44]^[45]^[46]의 변형 또는 크리-크로스 알고리즘으로 해결할 수 있다.^[47]

참조

_[1] 서적 Linear programming http://www.computer.[...] John Wiley & Sons
_[2] harvtxt
_[3] harvtxt
_[4] 간행물 The simplex and projective scaling algorithms as iteratively reweighted least squares methods
_[5] 간행물 Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods
_[6] 간행물 Karmarkar's algorithm and its place in applied mathematics 1987-06-01
_[7] 간행물 Reminiscences about the origins of linear programming https://apps.dtic.mi[...] 1982-04
_[8] 간행물 An Interview with George B. Dantzig: The Father of Linear Programming http://www.phpsimple[...] 1986
_[9] 백과사전 Origins of the simplex method http://apps.dtic.mil[...] Association for Computing Machinery 1987-05
_[10] harvtxt
_[11] harvtxt
_[12] harvtxt
_[13] 문서 George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
_[14] 웹사이트 Robert J. Vanderbei, Linear Programming: Foundations and Extensions http://www.princeton[...] Springer Verlag 2008
_[15] harvtxt
_[16] harvtxt
_[17] harvtxt
_[18] harvtxt
_[19] 문서 Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
_[20] harvtxt
_[21] 문서 Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28
_[22] harvtxt
_[23] harvtxt
_[24] 서적 Linear Programming 2: Theory and Extensions Springer-Verlag
_[25] 서적 Linear Optimization and Extensions Springer-Verlag
_[26] 서적 Linear Optimization and Extensions: Problems and Solutions Springer-Verlag
_[27] 서적 Advances in linear and integer programming Oxford Science
_[28] 서적 Computational techniques of the simplex method Kluwer Academic Publishers
_[29] 간행물 New finite pivoting rules for the simplex method 1977-05
_[30] harvtxt
_[31] 문서 There are abstract optimization problems, called oriented matroid programs, on which Bland's rule cycles (incorrectly) while the criss-cross algorithm terminates correctly.
_[32] 서적 Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin) Academic Press
_[33] Citation Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
_[34] 간행물 The Simplex Algorithm Is NP-Mighty 2018-11-01
_[35] Citation Integer Programming and Combinatorial Optimization
_[36] 간행물 Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
_[37] 서적 Theory of Linear and Integer Programming John Wiley & sons
_[38] 서적 The simplex method: A probabilistic analysis Springer-Verlag
_[39] 서적 Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing ACM
_[40] 논문 A Friendly Smoothed Analysis of the Simplex Method https://epubs.siam.o[...] 2020-01-01
_[41] 논문 Pivot rules for linear programming: A Survey on recent theoretical developments
_[42] 논문 Criss-cross methods: A fresh view on pivot algorithms http://infoscience.e[...] North-Holland Publishing
_[43] 문서
_[44] 서적 Fractional programming Heldermann Verlag
_[45] 논문 Pseudolinear programming
_[46] 논문 A nonlinear programming algorithm for hospital management
_[47] 논문 The finite criss-cross method for hyperbolic programming http://www.cas.mcmas[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com