홍라이프 계산기꼭짓점 방법 계산기 쉽게 이해하기 — 개념과 원리
이 계산기는 변수가 두 개인 선형계획법 문제를 꼭짓점 방법으로 풉니다. 최대화하거나 최소화할 목적함수 z = c₁x + c₂y와 일차 제약조건을 넣으면, 실행 가능 영역의 모든 꼭짓점을 찾아 각 점에서 z를 계산하고 가장 좋은 값을 고릅니다. 생산 계획, 일정, 식단처럼 유한수학과 경영수학 문제에 쓸 수 있습니다.
계산 방법
- 각 제약조건 a·x + b·y ≤ c(또는 ≥, =)의 경계선 a·x + b·y = c를 그립니다. x ≥ 0, y ≥ 0도 넣을 수 있습니다.
- 경계선을 두 개씩 짝지어 교점을 구합니다.
- 모든 제약조건을 만족하는 교점만 남기며, 이것이 꼭짓점입니다.
- 각 꼭짓점에서 z = c₁x + c₂y를 계산해 최대화면 가장 큰 값, 최소화면 가장 작은 값을 고릅니다.
- 두 꼭짓점이 같으면 그 사이 변 위의 모든 점이 최적입니다. 좋아지는 방향으로 영역이 끝없이 열려 있으면 최적값이 없습니다.
원리
일차 제약조건들은 곧은 변으로 둘러싸인 볼록한 영역을 만듭니다. 목적함수는 위에서 보면 c₁x + c₂y = 상수인 평행선들의 모임입니다. 이 직선을 좋아지는 방향으로 밀어 가면, 영역을 벗어나기 직전에 마지막으로 닿는 곳은 항상 꼭짓점(또는 변 전체)입니다. 그래서 꼭짓점만 확인하면 되고, 무한히 많은 점을 찾는 문제가 유한한 계산으로 바뀝니다.
예제 풀이
기본값: x + y ≤ 12, 2x + y ≤ 16, x ≥ 0, y ≥ 0에서 40x + 30y 최대화.
- 사용한 제약조건은 x, y ≥ 0을 포함해 4개입니다.
- 꼭짓점: (0, 0), (0, 12), x + y = 12와 2x + y = 16이 만나는 (4, 8), (8, 0)의 4개입니다.
- z 값: (0, 0) → 0, (0, 12) → 360, (4, 8) → 160 + 240 = 400, (8, 0) → 320입니다.
- 최적 꼭짓점은 (4, 8), 최적값은 400입니다.
| 목적함수: y의 계수 | 목적함수의 최적값 |
|---|---|
| 7.5 | 320 |
| 15 | 320 |
| 22.5 | 340 |
| 30 | 400 |
| 37.5 | 460 |
| 45 | 540 |
| 60 | 720 |
결과 해석
기본 예에서 x와 y는 시간당 40과 30을 버는 두 일의 근무 시간이고, 근무는 최대 12시간, 준비 시간은 최대 16시간입니다. 가장 좋은 계획은 첫째 일 4시간, 둘째 일 8시간입니다. 최적 꼭짓점을 지나는 제약조건은 꽉 찬(구속하는) 조건이라 이를 완화하면 결과가 좋아지고, 나머지 조건에는 여유가 있습니다.
흔한 실수
- 문제에 함축된 x ≥ 0, y ≥ 0을 빼먹는 경우
- 다른 제약조건을 어기는 교점까지 남기는 경우
- ≥를 ≤로 잘못 넣어 영역이 뒤집히는 경우
- 열린 영역인데도 최적값이 있다고 가정하는 경우
자주 묻는 질문
꼭짓점 정리란?
선형계획 문제에 최적값이 있으면 실행 가능 영역의 꼭짓점에서 나타난다는 정리입니다.
두 꼭짓점의 값이 같으면요?
두 점을 잇는 변 위의 모든 점이 최적입니다.
최소화도 되나요?
네, '최소화'를 고르면 가장 작은 꼭짓점 값을 알려 줍니다.
출처: R. Sekhon & R. Bloom, Applied Finite Mathematics (LibreTexts), §3.1 Maximization Applications