- Corner point : 제약식들의 경계들의 교점 (교점이 feasible한지 infeasible한지 중요하지 않음)
n개의 결정변수를 갖는 문제에서 n개의 경계의 교점
- CPF solution(corner-point feasible solution), extreme point : feasible한 corner point
- Adjacent(인접한) : n개의 결정변수를 갖는 문제에서, n-1개의 경계를 공유하는 경우
- Edge : 두 인접한 CPF solution을 연결하는 선분
- Optimality test : Consider any linear programming problem that possess at leat one optimal solution.
If a CPF solution(= extreme point) has no adjacent CPF solutions that are better (as measured by Z), then it must be an optimal solution.
=> optimal solution이 존재하는 LP라면 extreme point 중 하나는 optimal solution이다.
- Optimality test 방법
1. initialization : (0,0)을 초기 CPF solution으로 선택
2. optimality test : (0,0)과 인접한 CPF solution 중에 (0,0)보다 더 좋은 게 있는지 확인
3. Iteration 1
3-1. Z = 3X1 + 5X2 : X 계수가 3 < 5 이므로 X2축을 따라야함
3-2. 새로운 경계 2X2 = 12에서 정지
3-3. 새로운 교점 2X2 = 12, X1 = 0으로 구할 수 있음 -> (0,0)
4. optimal solution을 찾을 때까지 2, 3 반복
- Key solution concepts
1. Solution concept 1 : focus solely on CPF solutions
2. Solution concept 2 : the simplex method is an iterative algorithm
3. Solution concept 3 : If possible, choose the origin to be the initial CPF solution
4. Solution concept 4: Consider only adjacent CPF solutions
5. Solution concept 5: move along the edge with the largest rate of improvement in Z
6. Solution concept 6: If none of the edges give a positive improvement in Z, then the current CPF solution is optimal