[OR] Gauss 소거법

소개글

OR에서의 가장 기본적인 선형계획법의 풀이방법인 가우스 소거법입니다.

목차

가우스 소거법
가우스 소거법 예제

본문내용

가우스 소거법(Gaussian Elimination)

주어진 로부터 연립방정식의 해 를 구하는 문제에서 크래머 법칙을 이용하여 역행렬을 구하는 방법은 수치적으로 효율적인 방법이 아니다. 가우스 소거법(Gaussian elimination)은 보다 효율적으로 연립방정식의 해를 구할 수 있는 방법이다. 이 방법의 첫 번째 과정은 원소 로 이루어진 배열의 번째 열에 값들을 덧붙이는 것이다. 그 다음에는 방정식의 해를 바꾸지 않는 선형연산들을 적용하여 대각의 계수가 모두 인 삼각형 형태의 배열로 변환한다. 이 변환은 대각 인덱스 를 로 놓고 시작하여 차례로 만큼 증가시키면서 가 이 될 때까지 진행되는데, 각 과정은 두 단계를 거친다. 첫 번째 단계는 번째 방정식의 대각 원소 를 모두 로 정규화(normalize)하는 것으로서, 대각 원소와 그보다 오른쪽에 위치한 원소들을 모두 로 나눈다. 두 번째 단계는 번째부터 번째까지의 방정식들의 번째 열의 계수들을 모두 으로 바꾸는 것으로서, 가 에서 까지 변하고 가 에서 까지 변할 때 모든 원소들을 로 바꾼다.

참고 자료

INTRODUCTION TO OPERATION RESEARCH