심플렉스법 계산기
선형 계획 문제를 온라인으로 풀어보세요, 무료, 빠름, 완전한 단계별 피벗 연산 제공.
당사의 심플렉스법 계산기는 최대화, 최소화, 2단계, Big M, 쌍대, 수정 심플렉스 방식을 지원합니다. 목적 함수와 제약 조건을 입력하면 계산기가 모든 피벗 연산을 자동으로 수행합니다.
심플렉스 계산기
심플렉스법 계산기 작동 방식
LP 문제 입력
목적 함수의 계수와 각 제약 행을 우변 값과 함께 입력합니다.
최대화 또는 최소화 선택
최적화 목표를 선택합니다. 도구가 여유 변수를 포함한 초기 태블로를 자동으로 구성합니다.
피벗 반복 실행
계산기는 Cj-Zj로 피벗 열을 식별하고 비율을 계산하며 최적이 될 때까지 기본 행 연산을 수행합니다.
최적해 확인
최종 태블로는 최적 변수 값, Zj 행, 최대/최소 목적값을 표시합니다.
심플렉스 태블로 출력 예시
2변수 최대화 문제에 대한 태블로 반복 예시
| Basis | x1 | x2 | s1 | s2 | RHS | Cj-Zj |
|---|---|---|---|---|---|---|
| x1 | 14 | 0 | 0 | 1 | 14 | 0 |
| x2 | 7 | 1 | 0 | 0 | 7 | 5 |
| Zj | 35 | 5 | 0 | 0 | 35 |
심플렉스법이란?
심플렉스법은 선형계획법(LP) 문제를 푸는 데 가장 널리 사용되는 알고리즘입니다. 1947년 조지 단치히가 개발했으며, 일련의 선형 제약 조건 아래에서 선형 목적함수의 최적값을 찾습니다. 심플렉스법 계산기는 이 과정을 자동화합니다. 목적함수와 제약 조건을 입력하면 계산기가 최적해에 도달할 때까지 모든 피벗 연산을 수행하며, 그 과정의 각 단체표(타블로)를 보여줍니다.
선형계획 모형은 어디에나 나타납니다. 이익 최대화, 비용 최소화, 자원 배분, 생산 계획, 그리고 수송 문제와 식단 문제 해결 등입니다. 관계가 선형인 한, 심플렉스법은 실행 가능 영역의 한 꼭짓점에서 다음 꼭짓점으로 효율적으로 이동하며, 더 이상 개선이 불가능할 때까지 각 단계에서 목적을 개선합니다.
심플렉스법 공식과 표준형
알고리즘을 적용하기 전에 문제를 표준형으로 작성합니다. 최대화 문제의 경우 각 제약 조건을 방정식으로 변환하는데, 여유변수(slack variable)를 더하고(이하 제약의 경우), 잉여변수(surplus variable)를 빼며(이상 제약의 경우), 필요한 경우 인공변수(artificial variable)를 추가합니다. 목적은 최대화 Z = c1x1 + c2x2 + ... + cnxn 으로 작성되며, 제약 방정식을 따르고 모든 변수는 0 이상입니다.
이 계수들이 첫 번째 심플렉스 타블로를 채웁니다. 타블로 계산기는 이 표를 자동으로 작성하고, 각 반복에 대해 Zj 행과 Cj 빼기 Zj 행을 계산하므로 계산 과정을 정확히 따라갈 수 있습니다.
심플렉스법을 단계별로 푸는 방법
예시로 최대화 Z = 3x1 + 5x2, 제약 x1 + 2x2 가 14 이하, x1 + x2 가 8 이하를 들어 봅시다. 첫째, 두 제약에 여유변수를 더해 초기 타블로를 구성합니다. 둘째, Cj 빼기 Zj 를 계산하고 가장 양수인 값을 들어오는 변수(피벗 열)로 선택합니다. 셋째, 각 우변 값을 피벗 열의 양수 항목으로 나누는 비율 검정을 적용하고, 가장 작은 음이 아닌 비율을 선택하여 나가는 변수(피벗 행)를 찾습니다. 넷째, 기본 행 연산을 사용하여 피벗합니다. 마지막으로 모든 Cj 빼기 Zj 값이 0 이하가 될 때까지 반복합니다.
이 예시의 최적해는 x1 = 2, x2 = 6 이며 Z = 36 입니다. 이 페이지의 단계별 계산기는 각 반복을 보여주므로 종이에 직접 재현할 수 있습니다.
최대화 대 최소화
심플렉스법은 두 방향을 모두 처리합니다. 최대화 문제에서는 알고리즘이 양수인 Cj 빼기 Zj 가 남지 않을 때까지 Z 를 증가시킵니다. 최소화 문제는 동등한 최대화로 변환하거나(Z 최소화는 음의 Z 최대화와 같음), 가장 음수인 Cj 빼기 Zj 를 선택하여 풉니다. 최소화 문제는 종종 이상 제약을 포함하며, 이는 빅 M 기법이나 2단계 기법을 필요로 합니다.
빅 M 법과 2단계 법
문제에 이상 제약이 포함되면 인공변수가 도입됩니다. 빅 M 법은 이 인공변수들에 매우 큰 벌점(penalty)을 부여하여 알고리즘이 그것들을 기저(basis)에서 몰아내도록 합니다. 2단계 심플렉스법은 같은 목표를 두 단계로 달성합니다. 1단계는 실행 가능한 출발점을 찾기 위해 인공변수의 합을 최소화하고, 2단계는 실제 목적을 최적화합니다. 둘 다 동일한 최적해에 도달합니다.
쌍대 및 개정 심플렉스법
쌍대(dual) 심플렉스법은 최적이지만 실행 불가능한 타블로에서 시작하여 실행 가능성을 회복하며, 이는 이미 푼 문제에 제약이 추가될 때 효율적입니다. 개정(revised) 심플렉스법은 전체 타블로 대신 기저 행렬의 역행렬만 저장하여, 대규모 문제에서 메모리 효율이 훨씬 높으면서도 동일한 결과를 산출합니다.
그래핑 또는 TI-84 계산기에서의 심플렉스법
그래핑 계산기에서 행렬 행 연산을 사용하여 심플렉스 알고리즘을 손으로 실행할 수 있습니다. TI-84에서는 타블로를 행렬로 저장한 다음, MATRIX MATH 메뉴의 rowSwap, 행 곱하기, 행 곱하여 더하기를 사용하여 피벗합니다. Casio 공학용 계산기에는 내장 심플렉스 기능이 없지만, 그 Matrix 모드에서 동일한 행 연산을 수동으로 수행할 수 있습니다. 수동 피벗 없이 즉시 결과를 얻으려면 이 페이지의 온라인 계산기가 모든 단계를 대신 수행합니다.
심플렉스법 대 도해법
도해법은 2변수 문제에서만 작동하며, 실행 가능 영역을 그리고 꼭짓점에서 최적값을 읽어냅니다. 심플렉스법에는 그러한 제한이 없어 변수의 수에 관계없이 문제를 풉니다. 교과서 예제에는 2변수 계산기를, 문제가 그래프로 그릴 수 있는 범위를 넘어 커질 때는 3변수 및 4변수 계산기를 사용하세요.
선형계획 문제(LPP)
선형계획 문제(LPP)는 선형 목적과 선형 제약을 결합합니다. LPP 심플렉스법 계산기와 일반 선형계획 계산기는 최대화 및 최소화 LPP를 온라인에서 풀며, 전체 타블로 과정을 보여주므로 실제 문제를 풀면서 방법을 배울 수 있습니다.
모든 심플렉스 계산기 살펴보기
필요한 특정 선형 계획 도구를 선택하세요
자주 묻는 질문
계산기로 심플렉스법을 어떻게 하나요?
계산기 입력란에 목적 함수와 제약 조건을 입력하고 최대화(Maximize) 또는 최소화(Minimize)를 선택한 다음 풀기를 클릭하세요. 도구가 모든 피벗 연산을 자동으로 수행하고 최적해를 표시합니다.
계산기로 심플렉스법을 어떻게 푸나요?
LP 변수, 계수, 제약 조건을 입력하세요. 심플렉스 계산기는 각 테이블로(tableau) 반복을 거치며 최적해에 도달할 때까지 단계별 피벗 과정을 보여줍니다.
계산기로 심플렉스법을 어떻게 사용하나요?
변수의 개수를 선택하고, 목적 함수 행을 입력하고, 각 제약 조건 행을 RHS(우변) 값과 함께 추가하고, 목표(최대/최소)를 선택한 다음 계산을 눌러 전체 해를 얻으세요.
계산기를 사용하여 심플렉스법을 어떻게 찾나요?
온라인에서 '심플렉스법 계산기'를 검색하여 무료 도구를 여세요. 선형 계획 문제를 입력하면 계산기가 심플렉스 알고리즘을 적용하여 최적해를 자동으로 찾아냅니다.
선형 계획법에서 심플렉스법을 어떻게 계산하나요?
결정 변수와 여유(slack) 변수로 초기 심플렉스 테이블로를 설정하세요. 가장 음수인 Cj-Zj 값을 피벗 열로 식별하고, 비율을 계산하여 피벗 행을 찾은 다음, 기본 행 연산을 수행하여 반복하세요.
계산기를 사용하여 심플렉스법을 어떻게 최소화하나요?
심플렉스 최소화 계산기를 열고 최소화(Minimize) 옵션을 선택한 다음, 비용 함수 계수와 제약 조건 값을 입력하고 풀기를 클릭하면 최소 목적값과 최적 변수값을 얻을 수 있습니다.
심플렉스법에서 Zj를 어떻게 계산하나요?
Zj = 각 열 j에 대한 (Cbi × aij)의 합. 여기서 Cbi는 행 i에 있는 현재 기저 변수의 목적 계수이고, aij는 해당 열의 대응하는 테이블로 요소입니다.
그래핑 계산기를 사용하여 심플렉스법을 어떻게 푸나요?
TI-84에서는 MATRIX > EDIT를 사용하여 테이블로를 행렬에 저장한 다음, MATRIX > MATH(rowSwap, *row, *row+)를 통해 행 연산을 사용하세요. 또는 TI 계산기용으로 제공되는 전용 심플렉스 앱을 사용할 수도 있습니다.
계산기가 심플렉스법을 할 수 있나요?
네. 온라인 심플렉스 계산기는 초기 테이블로 설정부터 최종 최적해까지 전체 알고리즘을 처리하며, 모든 피벗 선택과 행 연산을 자동으로 포함합니다.
Casio로 심플렉스법 피벗 연산을 계산할 수 있나요?
Casio 공학용 계산기에는 내장된 심플렉스 기능이 없습니다. 그러나 Casio의 Matrix 모드를 사용하여 행렬 행 연산을 수동으로 수행함으로써 각 피벗 단계를 처리할 수 있습니다.
A부터 Z까지 심플렉스법 계산기란?
완전한 심플렉스법 계산기는 모든 것을 다룹니다: LP 문제 입력, 초기 테이블로 설정, 모든 피벗 반복 수행, 최적 기저 식별, 그리고 모든 변수값을 포함한 최종 해 표시입니다.
심플렉스법이란 무엇입니까?
심플렉스법은 선형 계획 문제를 풀기 위해 1947년 조지 단치그(George Dantzig)가 개발한 반복 알고리즘입니다. 실행 가능 영역의 한 꼭짓점(모서리 점)에서 인접한 꼭짓점으로 이동하며, 각 단계마다 목적 함수를 개선하여 최적해에 도달할 때까지 진행합니다.
심플렉스법은 선형 계획법과 같은 것입니까?
아닙니다. 선형 계획법(LP)은 문제의 유형으로, 선형 제약 조건 하에서 선형 목적 함수를 최적화하는 것입니다. 심플렉스법은 선형 계획 문제를 푸는 데 사용되는 알고리즘 중 하나이며, 다른 것으로는 그래프법과 내부점법이 있습니다.
여유 변수, 잉여 변수, 인공 변수란 무엇입니까?
여유 변수(slack)는 ≤ 제약을 등식으로 만들기 위해 더하고, 잉여 변수(surplus)는 ≥ 제약에서 빼며, 인공 변수(artificial)는 초기 기저 실행 가능해를 제공하기 위해 ≥ 및 = 제약에 더합니다. 인공 변수는 Big M 법 또는 2단계법(two-phase) 과정에서 제거됩니다.
Big M 법과 2단계법의 차이는 무엇입니까?
둘 다 ≥ 및 = 제약의 인공 변수를 다룹니다. Big M 법은 큰 벌칙 상수 M을 포함하는 단일 목적 함수를 사용하는 반면, 2단계법(two-phase)은 먼저 인공 변수를 최소화하고(1단계), 그다음 실제 목적을 최적화합니다(2단계). 둘 다 동일한 최적해에 도달합니다.
피벗 열과 피벗 행은 어떻게 선택합니까?
최대화의 경우 피벗 열(들어오는 변수)은 Cj − Zj 값이 가장 양수인 열입니다. 피벗 행(나가는 변수)은 최소 비율 검정으로 찾습니다. 각 우변 값을 피벗 열의 양수 항목으로 나누고 가장 작은 음이 아닌 비율을 선택합니다.
심플렉스 태블로(tableau)는 언제 최적입니까?
태블로는 더 이상 개선이 불가능할 때 최적입니다. 최대화 문제에서는 모든 Cj − Zj 값이 0 이하일 때, 최소화에서는 모든 Cj − Zj가 0 이상일 때 그렇습니다.
심플렉스법으로 최소화 문제를 풀 수 있습니까?
예. 최소화는 동등한 최대화로 변환하거나(Z 최소화는 −Z 최대화와 같음), 가장 음수인 Cj − Zj를 들어오는 변수로 선택하여 풉니다. ≥ 형 제약은 잉여 변수와 인공 변수로 처리합니다.
쌍대 심플렉스법은 어떻게 작동합니까?
쌍대(dual) 심플렉스법은 최적이지만 실행 불가능한(일부 우변 값이 음수) 태블로에서 시작합니다. 먼저 나가는 변수(가장 음수인 우변)를 선택한 다음 쌍대 비율 검정으로 들어오는 변수를 선택하여, 최적성을 유지하면서 실행 가능성을 회복합니다.
개정 심플렉스법(revised)이란 무엇입니까?
개정 심플렉스법은 표준법과 동일한 반복을 수행하지만, 전체 태블로 대신 기저 행렬의 역행렬(B⁻¹)만 저장합니다. 이로 인해 메모리 효율이 훨씬 높아지며, 전문적인 선형 계획 솔버의 기반이 됩니다.
비유계해는 무엇을 의미합니까?
선형 계획은 모든 제약을 만족하면서 목적 함수를 (최대화에서) 무한히 증가시키거나 (최소화에서) 무한히 감소시킬 수 있을 때 비유계(unbounded)입니다. 심플렉스법에서는 비율 검정을 위한 피벗 열에 양수 항목이 하나도 없을 때 감지됩니다.
심플렉스법에서 퇴화해란 무엇입니까?
퇴화(degeneracy)는 종종 최소 비율 검정에서의 동점 때문에 태블로 내 기저 변수가 0과 같아질 때 발생합니다. 퇴화는 알고리즘이 목적을 개선하지 않고 태블로를 반복하는 순환(cycling)을 일으킬 수 있으며, 블랜드 규칙(Bland's rule) 같은 순환 방지 규칙이 이를 막습니다.
심플렉스법은 몇 개의 변수를 다룰 수 있습니까?
고정된 한계는 없습니다. 그래프법은 두 변수로 제한되지만, 심플렉스법은 임의의 수의 결정 변수와 제약에 대해 작동합니다. 두 변수의 작은 교과서 문제부터 수천 개의 변수를 가진 산업용 모델까지 다룹니다.
수송 심플렉스법이란 무엇입니까?
수송 문제는 공급지에서 수요지로 물품을 운송하는 비용을 최소화하는 특수한 선형 계획입니다. 일반 심플렉스법으로 풀 수 있지만, 전문화된 버전(MODI 법이나 디딤돌법 등)은 그 구조를 활용하여 효율을 높입니다.
왜 그래프법 대신 심플렉스법을 사용합니까?
그래프법은 실행 가능 영역을 2차원으로 그려야 하기 때문에 두 변수 문제에만 적용됩니다. 심플렉스법은 그런 제약이 없으며 임의의 수의 변수를 가진 문제를 대수적으로 풀 수 있어 표준적인 접근법입니다.