선형계획법(2변수) 계산기

목적함수의 등고선이 직선이고 실행가능영역이 볼록하기 때문입니다. 볼록한 영역 위에서 직선을 밀어 나가면 마지막으로 닿는 곳은 꼭짓점이거나 한 변 전체입니다. 영역 안의 어떤 점도 꼭짓점들의 볼록결합으로 쓸 수 있고 목적함수가 선형이라 그 값은 꼭짓점 값들의 볼록결합인데, 볼록결합은 가장 큰 성분을 넘지 못합니다. 그래서 무한히 많은 점 대신 유한한 꼭짓점만 보면 됩니다.

제약식 두 개씩의 경계선이 만나는 점을 모두 구한 뒤, 그중 모든 제약을 만족하는 것만 남깁니다. 남은 점들이 꼭짓점이고, 그것들이 이루는 볼록다각형이 실행가능영역입니다.

아주 큰 값이 있는 것이 아니라 값이 존재하지 않는다는 뜻입니다(비유계). 영역이 한쪽으로 끝없이 뻗어 있고 그 방향으로 갈수록 목적함수가 계속 커지기 때문입니다. 실제 문제에서 이 결과가 나왔다면 대개 예산·설비·시간 같은 위쪽 한계 제약을 빠뜨린 것입니다.

꼭짓점만 봐서는 알 수 없어서 영역이 뻗어 나가는 방향(후퇴원뿔)을 따로 봅니다. 2차원에서 후퇴원뿔은 원점을 지나는 반평면들의 교집합이고, 그 극단 방향은 각 제약 경계선과 나란한 ±(−b, a) 중에 있습니다. 그 방향들만 검사해 목적함수를 키우는 것이 있는지 봅니다.

목적함수의 등고선이 어느 제약의 경계선과 평행하기 때문입니다. 그 변 위의 모든 점이 같은 값을 내므로 답이 하나가 아니라 선분 하나입니다. 실무에서는 오히려 반가운 결과로, 계산에 넣지 않은 다른 기준으로 고를 여지가 생깁니다.

제약이 서로 어긋나 모두를 동시에 만족하는 점이 없다는 뜻입니다. 부등호 방향을 뒤집어 넣지 않았는지, 단위가 섞이지 않았는지 확인하세요. x ≥ 0과 y ≥ 0이 자동으로 붙는다는 점도 함께 보세요.

표준형이기도 하지만 판정을 엄밀하게 만들기 위해서입니다. 1사분면으로 가두면 영역이 뾰족해져 비어 있지 않은 한 반드시 꼭짓점이 생기므로, «꼭짓점이 하나도 없다 = 실행불가능»이라고 말할 수 있습니다. 이 조건이 없으면 y ≤ 1처럼 꼭짓점 없이 뻗은 띠가 실행가능한데도 실행불가능과 구별되지 않습니다.

되지 않습니다. 변수가 늘면 꼭짓점 수가 제약 수에 대해 폭발적으로 늘어 전부 훑는 방법을 못 씁니다. 그때는 꼭짓점을 하나씩 걸어가는 심플렉스법이 필요합니다.

안전하지 않습니다. 꼭짓점이 정수점이라는 보장이 없어서, 반올림하면 제약을 벗어나거나 최적이 아니게 되는 일이 흔합니다. 정수해가 필요한 문제는 정수계획이라는 다른 문제이며 분기한정법 같은 별도 방법을 씁니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이루어지며 입력값은 이 기기에만 남습니다.