1. 정의

• 목적 함수가 선형 함수이고, 모든 제약식이 선형 등식 혹은 선형 부등식으로 주어지는 최적화 문제

2. 표준형

(1) 조건

• 목적 함수를 최대화한다.
• 모든 변수는 음의 값을 갖지 않는다.(non-negative constraint)
• 비음 제약 조건을 제외하면, 제약 조건의 좌변항은 우변항보다 작거나 같아야 한다.

(2) 표준형으로 변환하는 방법

• 최소화 문제는 음수로 바꿔서 최대화 하면 된다.
• 등식 제약은 2개의 부등식 제약으로 치환한다.

$$ \sum_{j=1}^{N}a_{ij}x_j = b_i \iff \sum_{j=1}^{N}a_{ij}x_j \leq b_i, \sum_{j=1}^{N}a_{ij}x_j \geq b_i $$

• 비음 제약 조건을 갖지 않는 변수는 비음 제약 조건을 갖는 2개의 변수를 도입해서 치환한다.

  $$ x_j = x_j^+ - x_j^- $$

• 부등호가 반대 방향인 제약 조건은 양변에 -1을 곱해서 부등호 방향을 바꾼다.

$$ \sum_{j=1}^{N}a_{ij}x_j \geq b_i \iff \sum_{j=1}^{N}(-a_{ij})x_j \leq -b_i $$

(3) 예시

A. 원래 문제

$$ min \quad 3x_1 + 4x_2 -2x_3 \\ s.t \quad 2x_1 + x_2 = 4 \\ x_1 - 2x_3 \leq 8 \\ 3x_2 + x_3 \geq 6\\x_1 \geq 0, x_2 \geq 0 $$

B. 표준형