선형 계획법 솔버

심플렉스법을 사용하여 온라인에서 선형 계획법 문제를 해결하세요. 최대화 또는 최소화 목적 함수, 혼합 ≤/≥/= 제약 조건을 지원하며, 최대 8개의 결정 변수를 사용할 수 있습니다. 2변수 LP의 경우 모든 꼭짓점과 최적점이 표시된 대화형 가용 영역 그래프를 제공합니다.

선형 계획법 솔버

Embed 선형 계획법 솔버 Widget

선형 계획법 솔버 정보

선형 계획법 솔버는 일련의 선형 부등식 또는 등식 제약 조건하에서 선형 목적 함수의 최대값 또는 최소값을 찾아주는 온라인 계산기입니다. 심플렉스법(Big-M 변형)을 사용하여 <=, >= 및 = 제약 조건을 자유롭게 혼합할 수 있으며, 2변수 문제의 경우 모든 꼭짓점과 최적점이 강조된 대화형 실행 가능 영역 플롯을 그려줍니다.

선형 계획법이란 무엇인가요?

선형 계획법(LP) 문제는 다음과 같은 형식을 가집니다:

최대화 (또는 최소화): Z = c₁ x₁ + c₂ x₂ + … + c_n x_n 제약 조건: a₁₁ x₁ + … + a_1n x_n (≤, ≥, 또는 =) b₁ a₂₁ x₁ + … + a_2n x_n (≤, ≥, 또는 =) b₂ … a_m1 x₁ + … + a_mn x_n (≤, ≥, 또는 =) b_m x₁, x₂, …, x_n ≥ 0

모든 제약 조건을 만족하는 점들의 집합을 실행 가능 영역(볼록 다면체)이라고 합니다. 선형 계획법의 기본 정리에 따르면, LP에 유한한 최적 해가 존재하는 경우 이는 반드시 다면체의 꼭짓점(극점)에서 달성됩니다. 이것이 꼭짓점에서 꼭짓점으로 이동하는 심플렉스법이 매우 효과적인 이유입니다.

심플렉스법 작동 원리

실행 가능한 꼭짓점에서 시작하여 심플렉스법은 더 나은 값을 가진 인접한 꼭짓점으로 피벗함으로써 목적 함수를 반복적으로 개선합니다. 주요 메커니즘은 다음과 같습니다:

표준형 변환: LP를 Ax = b, x ≥ 0 조건하의 최대화 c^Tx 문제로 변환합니다. <= 제약 조건에는 여유(slack) 변수를 추가하고, >=에는 잉여(surplus) 변수를 뺀 후 큰 페널티 −M을 가진 인공(artificial) 변수를 추가합니다. 등식에는 인공 변수를 추가합니다.
초기 심플렉스 표: 기저는 여유 변수와 인공 변수로 구성되어 명백한 시작 꼭짓점을 제공합니다.
들어오는 변수: 축소 비용 $ c_j - z_j $가 가장 큰 비기저 변수를 선택합니다. 그러한 변수가 없으면 현재 해가 최적입니다.
나가는 변수: 들어오는 열에서 최소 비율 테스트를 수행합니다. 각 행의 RHS를 해당 행의 들어오는 열의 양수 항목으로 나누고, 가장 작은 비율을 가진 행을 선택합니다. 양수 항목이 없으면 LP는 무한 해를 가집니다.
피벗: 가우스 소거법을 사용하여 들어오는 열을 단위 벡터로 만들고, 나가는 행에 1을 배치합니다.
중단 기준을 만족할 때까지 반복합니다.

종료 시 기저에 양수 값을 가진 인공 변수가 남아 있으면 원래 LP는 해를 찾을 수 없는(불능) 상태입니다.

그래픽 해법 (2변수용)

2변수 문제의 경우 실행 가능 영역은 2D 볼록 다각형입니다. 최적 해는 항상 꼭짓점에 있으므로, 모든 꼭짓점을 나열하고 거기서 목적 함수를 평가하는 것만으로도 문제를 해결할 수 있습니다. 이 계산기는 모든 제약 조건 경계 쌍의 교차점을 찾고, 다른 모든 제약 조건을 만족하는 교차점만 남긴 뒤, 시각화를 위해 반시계 방향으로 정렬하여 이를 수행합니다.

입력 구문

첫 번째 줄에 목적 함수를 작성하고, 그 다음 줄부터 한 줄에 하나의 제약 조건을 작성합니다. 변수 이름은 어떠한 식별자(x, y, x1, profit…)도 가능합니다. 연산자는 <=, >= 및 =를 사용합니다. 비음 제약 조건은 x, y >= 0과 같이 단축하여 작성할 수 있습니다.

Maximize 3x + 5y x + y <= 10 2x + y <= 16 x + 3y <= 18 x, y >= 0

빈 줄과 #로 시작하는 주석은 무시됩니다. 솔버는 최대 8개의 결정 변수와 20개의 제약 조건을 수용합니다.

문제 풀이 예제

테이블과 의자를 만드는 가구 공방을 가정해 보겠습니다. 테이블 하나당 \\$3의 이익이 발생하며 나무 1단위와 노동 2단위가 필요합니다. 의자 하나당 \\$5의 이익이 발생하며 나무 1단위, 노동 1단위, 바니시 3단위가 필요합니다. 가용 자원: 나무 10, 노동 16, 바니시 18. x를 테이블 수, y를 의자 수라고 할 때 LP는 다음과 같습니다:

Maximize Z = 3x + 5y x + y <= 10 (나무) 2x + y <= 16 (노동) x + 3y <= 18 (바니시) x, y >= 0

실행 가능 영역은 오각형입니다. 각 꼭짓점에서 Z를 평가하면 다음과 같습니다:

꼭짓점 (x, y)	Z = 3x + 5y	실행 가능 여부
(0, 0)	0	예
(8, 0)	24	예
(6, 4)	38 ← 최적	예
(0, 6)	30	예

따라서 공방은 최대 이익 \\$38을 위해 테이블 6개와 의자 4개를 제작해야 합니다. 나무와 노동 제약 조건은 유효(binding)합니다(최적점에서 RHS와 동일함). 바니시 또한 여유 변수가 0(이 경우 역시 유효함)으로, 세 가지 자원이 모두 소진됨을 의미합니다.

일반적인 문제점 및 솔버 감지 사항

상황	증상	해결 방법
무한 해 (Unbounded LP)	솔버가 "Unbounded"라고 보고함	누락된 상한 제약 조건을 추가하세요. 실행 가능 영역이 개선 방향으로 무한히 뻗어 있어 목적 함수가 한계 없이 커질 수 있습니다.
불능 해 (Infeasible LP)	솔버가 "Infeasible"이라고 보고함	제약 조건들이 서로 모순됩니다 (예: `x >= 10`이면서 `x <= 5`). 모든 제약 조건 쌍을 검토하세요.
대안 최적 해	경고 배지 표시; 최적 꼭짓점은 하나지만 모서리를 따라 동일한 Z가 달성됨	목적 함수 벡터가 유효 모서리와 평행할 때 발생합니다. 해당 모서리의 두 꼭짓점 사이의 모든 선형 조합도 최적입니다.
퇴화(Degeneracy) / 순환(Cycling)	Z가 개선되지 않고 심플렉스 반복이 지속됨	교과서적인 문제에서는 드뭅니다. Bland의 규칙이나 섭동법으로 해결할 수 있습니다. 이 솔버는 무한 루프를 방지하기 위해 반복 횟수를 제한합니다.

활용 분야

제품 혼합 및 생산 계획 — 자원 제한 하에서 최대 이익을 얻기 위한 각 제품의 생산량 결정.
식단 및 혼합 문제 — 영양소 최소 기준을 충족하면서 식단 또는 사료의 비용 최소화.
운송 및 할당 — 공급과 수요의 균형을 맞추면서 운송 비용 최소화.
포트폴리오 최적화 — 리스크 또는 노출 제약 하에서 기대 수익 최대화(선형화된 경우).
네트워크 유량 — 최대 유량 및 최소 비용 유량 문제는 선형 계획법으로 환원됩니다.
스케줄링 — 교대 근무 요건 및 총 근로 시간 제한 하에서의 인력 배치.

이 계산기 사용 방법

텍스트 상자에 LP 문제를 입력합니다. 첫 번째 줄은 Maximize 또는 Minimize로 시작해야 합니다. 이후 각 줄에 제약 조건을 하나씩 입력합니다.
단축키 x, y >= 0을 사용하여 나열된 모든 변수에 대해 비음 제약 조건을 한 번에 선언할 수 있습니다.
선형 계획법 문제 해결 클릭. 솔버는 최적값 Z, 모든 결정 변수의 최적값, 유효 제약 조건 목록 및 2변수 LP에 대한 대화형 실행 가능 영역 플롯을 보고합니다.
플롯의 꼭짓점 위에 마우스를 올리면 좌표와 Z 값을 볼 수 있습니다. 최적점은 별표로 표시됩니다.
심플렉스 표를 검토하여 모든 피벗 과정과 방법이 어떻게 Z를 개선하는지 추적하세요. 들어오는 열은 황색으로, 나가는 행은 붉은색으로 강조됩니다.

자주 묻는 질문

선형 계획법 문제란 무엇인가요?

선형 계획법(LP) 문제는 일련의 선형 부등식 또는 등식을 만족하는 결정 변수 세트에 대해 선형 목적 함수의 최대값 또는 최소값을 찾는 문제입니다. 실행 가능 집합은 볼록 다면체이며, 최적값은 항상 꼭짓점 중 하나에서 달성된다는 점이 심플렉스법이 활용하는 핵심 사실입니다.

심플렉스법은 어떻게 작동하나요?

심플렉스법은 실행 가능 다면체의 꼭짓점을 따라 이동합니다. 각 단계("피벗")는 기저 변수 중 하나를 다른 변수와 교체하여 더 나은 목적 함수 값을 가진 인접 꼭짓점으로 이동합니다. 더 이상 Z를 개선할 수 있는 피벗이 없으면 알고리즘이 중단되며, 이때의 꼭짓점이 최적입니다. 이 도구는 <=, >= 및 = 제약 조건을 혼합할 수 있도록 Big-M 변형을 사용합니다.

실행 가능 영역이란 무엇인가요?

실행 가능 영역은 모든 제약 조건을 동시에 만족하는 모든 변수 값의 집합입니다. 2변수의 경우 2D 볼록 다각형이며, n개 변수의 경우 n차원 다면체입니다. 비어 있는 다면체는 LP가 불능임을 의미하며, 개선 방향으로 무한히 확장되는 다면체는 LP가 무한 해를 가짐을 의미합니다.

선형 계획법에서 "무한 해(unbounded)"는 무엇을 의미하나요?

LP가 무한 해를 가진다는 것은 실행 가능 영역이 목적 함수가 계속 개선되는 방향으로 무한히 뻗어 있음을 의미합니다. 예를 들어, Maximize x (제약 조건 x ≥ 0)는 유한한 최대값이 없습니다. 무한 해가 나오는 실제 LP는 종종 자원이나 변수에 대한 상한 제약 조건이 누락되었음을 나타냅니다.

"대안 최적 해(alternate optima)"는 무엇을 의미하나요?

대안 최적 해는 둘 이상의 지점에서 동일한 최적 목적 함수 값을 달성할 때 발생합니다. 기하학적으로 목적 함수가 다각형의 유효 모서리와 평행하므로, 해당 모서리 위의 모든 점(및 양 끝점의 모든 볼록 조합)이 최적입니다. 솔버는 종료 시 비기저 결정 변수의 축소 비용이 0인 경우 이를 표시합니다.