선형 규칙의 간략한 역사

비선형 프로그래밍은 1950년대에야 구체화되기 시작한 새로운 분야입니다. 1951년 H.W. Kuhn과 A.W. Tucker가 출판한 최적 조건(나중에 Kuhn-Tucker 조건이라고 함)에 관한 논문은 비선형 프로그래밍의 공식적인 탄생을 보여주는 중요한 상징이었습니다. 1950년대에는 분리 가능 계획법과 2차 계획법에 대한 n개의 해법도 도출되었으며, 대부분은 G.B. Danzik이 제안한 선형 계획법을 해결하기 위한 단순 방법을 기반으로 했습니다. 1950년대 후반부터 1960년대 후반까지 비선형 계획법 문제를 해결하기 위한 효과적인 알고리즘이 많이 등장했으며, 1970년대에 더욱 발전했습니다. 비선형 프로그래밍은 엔지니어링, 경영, 경제, 과학 연구, 군사 및 기타 분야에서 널리 사용되며 최적의 설계를 위한 강력한 도구를 제공합니다.

수학적 모델 실제 기획 문제를 정량적으로 분석하기 위해서는 수학적 모델을 수립해야 한다. 수학적 모델을 구축하기 위해서는 먼저 적절한 목표변수와 의사결정변수를 선택하고, 목표변수와 의사결정변수 간의 함수적 관계를 구축해야 하는데 이를 목적함수라고 한다. 그런 다음 다양한 제약 조건이 추상화되고 의사 결정 변수가 충족해야 하는 일부 방정식 또는 부등식이 파생되는데, 이를 제약 조건이라고 합니다. 비선형 계획법 문제의 일반적인 수학적 모델은 제약 조건이 충족되도록 알 수 없는 변수 x1, x2,..., xn을 찾는 것으로 표현될 수 있습니다.

gi(x1,...,xn) ≥0　i=1,..., m

hj(x1,…,xn)=0　j=1,…,p

그리고 목적 함수 f(x1 ,…,xn)이 최소값(또는 최대값)에 도달합니다. 그 중 f, gi, hj는 모두 n차원 벡터공간 Rn의 특정 부분집합 D(도메인)에 정의된 실수 함수이고, 그 중 적어도 하나는 비선형 함수이다.

위 모델은 다음과 같이 축약될 수 있습니다:

min f(x)

s.t.gi(x)≥0　i=1,…,m

hj(x)=0 j=1,…,p

x=(x1,…,xn)이 도메인 D에 속하는 경우 기호 min은 “최소값을 찾는 것”을 의미합니다. ” 및 기호 s.t.는 "대상"을 의미합니다.

제약조건을 충족하는 도메인 D의 점을 문제에 대한 실현 가능한 솔루션이라고 합니다. 모든 실현 가능한 해의 집합을 문제의 실현 가능한 집합이라고 합니다. 실행 가능한 해 x*의 경우 x*의 이웃이 있는 경우 x*에서 목적 함수의 값 f(x*)는 이웃의 다른 모든 실행 가능한 해보다 낫습니다(보다 크지도 작지도 않음을 의미). . 함수 값이면 x*를 문제의 로컬 최적 솔루션(로컬 솔루션이라고 함)이라고 합니다. f(x*)가 모든 가능한 솔루션에서 목적 함수 값보다 나은 경우 x*를 문제의 전체 최적 솔루션(전체 솔루션이라고 함)이라고 합니다. 실용적인 비선형 프로그래밍 문제에는 전역 솔루션이 필요하지만 기존 솔루션 방법은 대부분 로컬 솔루션만 찾습니다.