1. minimization problem이나 maximization problem으로 나뉘고
2. constraint는 equation이나 inequality 둘다 될 수 있으며
3. variable은 nonnegative로 제한이 될 수도 안 될 수도 있다.
때문에 너무 다양한 linear program이 존재하는데 이는 좀더 간단한 standard form으로 reduce 될 수 있다.
1. minimization problem
2. constraint는 equation만
3. variable은 nonnegative로 제한
모든 general linear program을 standard form으로 reduce하는 방법은
1. maximization problem의 경우 objective function에 -1을 곱한다.
2a. inequality의 경우
\sum_{i=1}^{n}a_{i}x_{i} \le b
일 때, 이는
\sum_{i=1}^{n}a_{i}x_{i}+s = b
s \ge 0
으로 바꿔줄 수 있다.
여기서 s는 slack variable.
2b. equality를 inequality로 바꾸는건 ax=b를 ax>=b, ax<=b로 바꾸면 됨.
3. nonnegative로 제한하는 방법은 새로운 variable x+, x-(>0)를 만들어서 x를 (x+ - x-)로 바꿔주면 된다.
역시 블로그는 수식 쓰는 기능이 없어서 불편하다.
댓글 없음:
댓글 쓰기