선형 계획법 솔버

선형 계획법 솔버 정보

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

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

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

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

심플렉스법 작동 원리

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

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

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

그래픽 해법 (2변수용)

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

입력 구문

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

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

문제 풀이 예제

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

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

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

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

활용 분야

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

이 계산기 사용 방법

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

자주 묻는 질문

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

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

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

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

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

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

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

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

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

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

솔버는 몇 개의 변수와 제약 조건을 수용하나요?

최대 8개의 결정 변수와 20개의 제약 조건입니다. 대화형 실행 가능 영역 플롯은 2변수 문제에 대해서만 그려지며, 3개 이상의 변수의 경우에도 전체 수치적 심플렉스 해, 단계별 표 및 유효 제약 조건 보고서를 제공합니다.

더 읽어보기

• 선형 계획법 — 위키백과
• 심플렉스 알고리즘 — 위키백과
• Big M method — Wikipedia (영문)
• 최적화의 쌍대성 — 위키백과

고급 수학 연산 도구:

• 앤티로그 계산기
• 베타 함수 계산기
• 이항 계수 계산기
• 이항 확률 분포 계산기
• 비트-계산기
• 중심극한정리 계산기
• 조합 계산기
• 상보 오차 함수 계산기
• 복소수 계산기
• 엔트로피 계산기
• 오차 함수 계산기
• 지수 붕괴 계산기 - 높은 정밀도
• 지수 성장 계산기 높은 정밀도
• 지수 적분 계산기
• 지수 계산기 (높은 정확도)
• 팩토리얼 계산기
• 감마 함수 계산기
• 황금비율 계산기
• 반감기 계산기
• 백분율 성장 계산기 추천
• 순열 계산기
• 포아송 분포 계산기
• 다항식 근 계산기와 상세한 단계
• 확률 계산기 추천
• 확률 분포 계산기
• 비례식 계산기 추천
• 이차 공식 계산기
• 공학용 계산기 추천
• 과학적 표기법 계산기
• 유효숫자 계산기 새로운
• 큐브 합계 계산기
• 연속 숫자의 합 계산기
• 제곱합 계산기
• 진리표 생성기
• 집합론 계산기
• 벤 다이어그램 생성기 (3세트)
• 중국인의 나머지 정리 계산기
• 오일러 피 함수 계산기
• 확장 유클리드 알고리즘 계산기
• 모듈러 곱셈 역원 계산기
• 연분수 계산기
• 다익스트라 최단 경로 계산기
• 최소 신장 트리 계산기
• 그래프 차수열 검증기
• 완전순열 (부분계승) 계산기
• 스털링 수 계산기
• 비둘기집 원리 계산기
• 마르코프 체인 정상 상태 계산기
• 반올림 계산기 새로운
• 음이항분포 계산기 새로운
• 중복순열 계산기 새로운
• 모듈러 거듭제곱 계산기 새로운
• 원시근 계산기
• 불 대수 간소화기 새로운
• 카르노 맵 (K-Map) 솔버 새로운
• 그래프 채색 계산기 새로운
• 위상 정렬 계산기 새로운
• 인접 행렬 계산기 새로운
• 포함배제 계산기 새로운
• 선형 계획법 솔버 새로운
• 외판원 문제 솔버 (TSP) 새로운
• 해밀턴 경로 검사기 (Hamiltonian Path Checker) 새로운
• 평면 그래프 검사기 새로운
• 네트워크 플로우 계산기 (최대 유량) 새로운
• 안정된 결혼 문제 해결기 새로운
• 군론 위수 계산기 새로운
• 환과 체 계산기 새로운