1. 문제 정의의 제한

선형계획법은 선형적인 문제에만 적용이 가능한다. 이는 선형성(linearity)을 가정해야 하기 때문에 현실의 많은 문제에서 제약이 발생한다. 일반적으로 목적 함수와 제약 조건이 모두 선형이어야 하는데, 실제 세계의 문제는 비선형인 경우가 많다. 선형계획법의 주요 가정 중 하나는 각 변수의 영향을 독립적으로 분석하며, 이는 다음과 같이 수식으로 표현할 수 있다.

위 수식에서, 목적 함수인 $\mathbf{c}^\top \mathbf{x}$는 각 변수 $x_i$에 대한 선형 조합으로 표현된다. 하지만 현실에서는 비선형 목적 함수나 제약 조건이 흔히 존재한다. 예를 들어, 비선형적인 관계는 다음과 같은 형태를 가질 수 있다.

이러한 비선형 문제는 선형계획법으로는 다룰 수 없으므로 비선형 계획법 등의 다른 방법론을 적용해야 한다.

2. 정수성 제약의 부재

많은 실제 문제에서는 변수들이 정수(integer)로만 이루어져야 하는 경우가 있다. 예를 들어, 공장을 최적화할 때 기계의 대수를 정수로 표현해야 하는 상황이 존재한다. 그러나 선형계획법에서는 연속적인 값만을 다루므로, 변수가 실수(real number)로 제한된다. 이는 현실적인 상황과 괴리가 발생할 수 있다.

정수 제약을 포함한 문제는 다음과 같은 형식을 갖는다.

하지만, 선형계획법 자체는 이러한 정수 제약을 처리하지 못하므로 정수계획법을 사용해야 한다. 이로 인해 최적 해가 실수로 나올 경우, 이를 정수로 반올림하거나 절사해야 하는데, 이는 최적화의 정확도를 떨어뜨릴 수 있다.

3. 데이터 불확실성에 대한 민감성

선형계획법은 문제의 입력 데이터가 정확하다는 가정하에 해를 구한다. 하지만, 현실에서 입력 데이터는 불확실하거나 변동될 수 있다. 입력 데이터가 약간만 변경되어도 최적 해는 크게 변동할 수 있으며, 이로 인해 민감도 분석(sensitivity analysis)이 필요해진다. 예를 들어, 계수 벡터 $\mathbf{c}$ 또는 제약 조건 행렬 $\mathbf{A}$의 작은 변동이 결과에 큰 영향을 미칠 수 있다.

이를 수식으로 표현하면, 계수 벡터가 $\mathbf{c}$에서 $\mathbf{c} + \Delta \mathbf{c}$로 변할 때, 목적 함수는 다음과 같이 변한다.

이러한 변동에 따라 해가 크게 달라질 수 있으므로, 데이터의 불확실성에 대한 처리가 부족하다는 한계가 존재한다.

4. 스케일링 문제

선형계획법은 변수와 제약 조건의 스케일에 매우 민감한다. 즉, 문제에 포함된 변수들 사이의 크기 차이가 클 경우, 계산 과정에서 오차가 발생할 가능성이 커진다. 예를 들어, 일부 변수는 매우 큰 값을 갖는 반면, 다른 변수는 매우 작은 값을 가질 수 있다. 이런 상황에서 스케일링 문제는 단체법(Simplex Method) 같은 알고리즘이 수렴하지 않거나, 부정확한 해를 도출할 위험이 있다.

스케일링 문제를 방지하기 위해 변수의 크기를 조정하는 사전 처리가 필요할 수 있다. 스케일링을 적용하면 문제는 다음과 같이 변환된다.

여기서, $\mathbf{D_A}$와 $\mathbf{D_b}$는 스케일링 행렬로, 각 변수 및 제약 조건의 단위를 표준화한다. 그러나 스케일링 자체가 최적화 결과를 보장하지 않으며, 문제의 스케일에 따른 해결 방법이 추가로 요구된다.

5. 퇴행성 문제 발생 가능성

단체법을 포함한 선형계획법의 알고리즘은 퇴행성 문제(degeneracy)를 겪을 수 있다. 퇴행성 문제란, 최적 해를 찾는 과정에서 여러 개의 최적 해가 존재하거나, 알고리즘이 무한 루프에 빠지는 상황을 말한다. 예를 들어, 단체법에서는 여러 개의 기저 해가 동일한 값을 가질 때 퇴행이 발생할 수 있으며, 이로 인해 알고리즘의 수렴 속도가 저하되거나 수렴하지 않는 경우도 생깁니다.

이를 수식적으로 표현하면, 다음과 같은 경우에 퇴행이 발생할 수 있다.

이 경우, 알고리즘은 해를 찾아도 새로운 해가 기존 해와 동일한 경우가 발생하여, 무한히 반복되는 문제가 생길 수 있다.

6. 최적 해의 다수성 문제

때로는 선형계획 문제에서 여러 개의 최적 해가 존재할 수 있다. 이는 목적 함수가 여러 개의 기저 해에서 동일한 값을 가질 때 발생하는 문제이다. 이러한 다수의 해가 존재할 때, 사용자는 이 중에서 어느 해를 선택해야 할지 어려움을 겪을 수 있다. 다수성 문제는 주로 평행한 제약 조건이 존재하는 문제에서 발생하며, 이는 수학적으로 다음과 같이 표현될 수 있다.

여기서 $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_k$는 모두 동일한 목적 함수 값을 갖는 최적 해이다. 이러한 경우에는 추가적인 기준을 통해 가장 적합한 해를 선택하는 절차가 필요할 수 있다.

7. 시간 복잡성과 계산 효율성

선형계획법은 문제의 크기가 커질수록 계산 비용이 급격히 증가한다. 특히, 제약 조건의 수나 변수의 수가 많아지면, 단체법과 같은 고전적인 알고리즘의 시간 복잡도가 기하급수적으로 커질 수 있다. 이는 대규모 문제에서는 계산 자원의 한계를 초과하거나, 해결에 너무 많은 시간이 걸리는 문제로 이어질 수 있다.

단체법의 최악의 경우 시간 복잡도는 다음과 같이 표현된다.

여기서 $n$은 변수의 개수이다. 하지만 실제로는 평균적으로 이보다 훨씬 적은 시간이 걸리지만, 이론적으로는 최악의 경우가 발생할 수 있다. 이로 인해 대규모 문제에서는 내부점 방법(Interior-Point Method) 등의 대안이 필요할 수 있다. 이러한 방법은 시간 복잡도를 개선하여 대규모 문제에서도 효율적으로 해결할 수 있게 도와준다.

8. 불완전한 대칭성 처리

선형계획법은 종종 문제의 대칭성을 충분히 고려하지 못할 수 있다. 대칭적인 구조를 가진 문제에서는 동일한 결과를 여러 방식으로 표현할 수 있으며, 이러한 대칭성을 적절히 처리하지 않으면 계산량이 크게 늘어날 수 있다. 예를 들어, 두 변수 $x_1$과 $x_2$가 대칭적인 역할을 할 수 있음에도 불구하고 이를 별개의 변수로 취급하면 불필요한 중복 계산이 발생할 수 있다.

이 문제는 대칭성을 분석하고 이를 고려한 문제 재구성으로 어느 정도 해결할 수 있지만, 일반적인 선형계획법 알고리즘은 이러한 대칭성을 자동으로 처리하지 않는다.

9. 제약 조건의 강성

선형계획법은 제약 조건을 매우 엄격하게 적용한다. 즉, 문제 내의 모든 제약 조건을 반드시 만족시켜야만 해를 도출할 수 있다. 하지만 현실 세계에서는 일부 제약 조건을 어느 정도의 유연성을 가지고 완화하거나 우선순위를 조정할 필요가 있다. 선형계획법의 고전적인 접근은 이러한 유연성을 고려하지 않으므로, 현실적인 문제 해결에 있어 제한적일 수 있다.

수학적으로 제약 조건은 다음과 같이 표현된다.

이 때, 일부 제약 조건을 완화하여 다음과 같은 형태로 처리할 수 있다.

여기서 $\epsilon$은 허용 오차를 나타내며, 이를 통해 제약 조건을 완화할 수 있다. 그러나 이러한 방식은 기본적인 선형계획법 알고리즘에서는 적용되지 않으며, 추가적인 기법이 필요하다.

10. 비현실적인 가정

마지막으로, 선형계획법은 여러 가지 비현실적인 가정을 기반으로 한다. 예를 들어, 선형계획법은 자원의 무한 분할 가능성을 가정하는데, 이는 현실에서 불가능한 경우가 많다. 또한, 선형계획법은 결정론적(Deterministic) 접근을 따르며, 모든 입력 데이터가 확실하다는 가정을 전제로 한다. 그러나 실제 상황에서는 불확실성이 존재할 수 있으며, 이는 선형계획법의 적용 범위를 제한하는 요소로 작용한다.

이러한 비현실적인 가정은 문제의 단순화를 통해 해결할 수 있지만, 이는 문제의 본질적인 복잡성을 무시하는 결과를 초래할 수 있다.