OR(경영과학)간단개념정리-면접준비용

1.선형계획 심플렉스 방법

선형계획에서 심플렉스 방법은 주어진 자원과 제약 조건 하에 목표 함수를 최적화하는 데 사용되는 효율적인 알고리즘이다. 이 방법은 1947년 조지 댄지크에 의해 처음 제안되었으며, 이후 많은 분야에서 널리 활용되고 있다. 심플렉스 방법은 주로 선형 방정식과 부등식을 포함하는 문제를 해결하는 데 적합하다. 선형계획 문제는 일반적으로 다음과 같은 형태로 정의된다. 특정한 목적 함수 Z를 최대화(또는 최소화)하려고 하며, 제약 조건으로 주어진 여러 개의 부등식이 있다. 목적 함수와 제약 조건은 모두 선형이어야 하며, 주어진 변수들은 비음수 여야 한다. 이와 같은 조건을 만족하는 변수의 조합을 찾아 가장 큰(또는 작은) 값을 얻는 것이 선형계획의 목표다. 심플렉스 방법은 해의 공간을 정점으로 나뉜 다면체로 보고, 이 정점들 중 일부를 탐색하면서 최적해에 도달한다. 초기 해결책은 보통 기본 가짓수를 사용하여 결정된다. 이를 위해서 기본 해를 구성하고, 그 해가 제약 조건을 만족하는지 확인한 뒤, 목표 함수의 값을 평가한다. 이때, 초기 기본 해는 보통 인위적으로 설정하기도 하며, 때로는 인공 변수를 도입하여 해결…