TaeKyoung's Study Blog

지금까지 심플렉스 방법을 소개하면서 대수적 형태와 표의 형태로 설명하였다. 심플렉스 방법을 행렬형으로 검토하면 더 깊은 통찰을 얻을 수 있다. 다음은 앞서 다뤘던 예제 문제이다.$$\begin{align*}\text{Maximize} \quad & Z = 3x_1 + 5x_2 \\\text{Subject to} \quad & x_1 \leq 4 \\ & 2x_2 \leq 12 \\ & 3x_1 + 2x_2 \leq 18 \\ & x_1 \geq 0, \quad x_2 \geq 0\end{align*}$$ 이 표준형 예제를 행렬형으로 표기하면 다음과 같다.\[ \begin{aligned} ..

OR에서 문제의 시나리오가 바뀔 경우 최적해를 다시 찾아야 하는 경우가 있는데, 이를 효율적으로 해결하는 것은 매우 중요한 과제이다. 시나리오가 바뀐다는 것은 다음을 의미할 수 있다.제품 생산량당 얻는 단위 이득의 변화허용된 자원의 양의 한계치가 변화이 때 문제를 처음부터 다시 풀 수도 있겠지만, 그러기보다는 이전 문제의 최적해와 바뀐 문제의 최적해가 서로 멀리 떨어져 있지 않을 것이라 가정하고 접근하는 재최적화 방법을 쓰는 것이 일반적이다. 아래와 같은 예제가 있다고 하자. 각 결정변수는 제품 1,2를 각각 얼마나 생산할 지를 나타내는 변수이고, 목적함수의 계수는 제품 1, 2의 단위 생산량 당 이득으로 생각할 수 있다. 각각의 제약식은 제품1, 2를 생산하는데 드는 자원1,2,3에 대한 제약으로, 계..

비표준형 모형지금까지 우리는 표준형 (기능제약식이 모두 $\leq$ 이며, 모든 변수가 비음이며 목적함수는 최대화) 이라는 가정 하에서 심플렉스 방법을 적용하였다. 이번 포스팅에서는 이러한 표준형이 아닌 모형 (기능제약식이 등식이거나 $\geq$ 형태인 경우)를 다룰 것이다. 기능 제약식이 (= 또는 $\geq$형태)인 경우의 문제는 초기해를 찾는 것에서 발생한다. 표준형태에서는 여유변수를 초기 기저변수로 잡으면 각 변수의 값이 비음이 되므로 초기해가 편리하게 찾아졌다. 그러나 비표준 형태에서는 여유변수를 두어도 비음을 만족시키지 못할 가능성이 있으므로 추가적인 접근법을 도입해야 한다. 그 접근법을 인공변수라고 한다. 빅 $M$ 방법 등호 제약식 문제$$\begin{align*}\text{Maximize..