단순 방법

심플렉스 방법은 선형 계획법 문제를 해결하는 데 가장 일반적으로 사용되며 효과적인 알고리즘 중 하나입니다.

단순법은 1947년 조지 댄치히(George Dantzig)가 처음 제안했습니다. 지난 70년 동안 많은 변형이 개발되었지만 기본 개념은 동일합니다. 선형 계획법 문제에 대한 최적의 해가 존재하는 경우 해당 해는 실현 가능 영역의 정점 중에서 찾아야 합니다. 이를 바탕으로 심플렉스 방법의 기본 아이디어는 다음과 같습니다. 먼저 실현 가능 영역에서 정점을 찾고 특정 규칙에 따라 최적인지 판단하고 그렇지 않은 경우 인접한 다른 정점으로 전환하여 목적 함수를 만듭니다. value more Optimal, 최적의 솔루션을 찾을 때까지 이 작업을 계속합니다.

선형계획법의 최적해를 찾기 위한 선택방법을 사용하기 위해서는 다음 세 가지 문제를 해결해야 한다.

(1) 최적해 기준, 즉 반복 종료 기준;

(2) 베이스 변경 작업, 즉 하나의 베이스 실현 가능 솔루션에서 다른 베이스 실현 가능 솔루션으로 반복하는 방법

(3) 선택 즉, 적절한 열을 선택하면 염기 변경 작업에 열을 사용할 수 있어 목적 함수의 값을 크게 줄일 수 있습니다.

향상된 단순 방법:

원래 단순 방법은 그다지 경제적인 알고리즘이 아닙니다. 1953년 미국 수학자 G.B. Danziger는 단순법의 각 반복에서 누적되는 캐리 오류를 개선하기 위해 개선된 단순법을 제안했습니다. 기본 단계는 단순 방법과 거의 동일하며, 주요 차이점은 더 이상 연속 반복에서 가우스 제거 방법을 기반으로 하지 않고 이전 기저의 역행렬에서 새 기저 행렬의 역행렬을 직접 계산한다는 것입니다. 매트릭스를 선택한 다음 테스트 번호를 결정합니다. 이렇게 하면 반복의 누적 오류를 줄이고 계산 정확도를 높이며 컴퓨터의 저장 공간도 줄일 수 있습니다.