비선형 프로그래밍 : 방법 및 연습 - 수학 - 2026

비선형 프로그래밍 차례로 제한 될 수있는 여러 가지 독립 변수에 의존하는 함수를 최적화하는 방법이다.

하나 이상의 제한 또는 최대화 또는 최소화 할 함수 (목적 함수라고 함)가 변수의 선형 조합으로 표현되지 않으면 비선형 계획법 문제가있는 것입니다.

그림 1. 비선형 프로그래밍 문제 (NLP). 여기서 G는 제약 조건에 의해 결정되는 녹색 영역에서 최적화 할 (비선형) 함수입니다. 출처 : F. Zapata.

따라서 선형 계획법의 절차와 방법을 사용할 수 없습니다.

예를 들어, 잘 알려진 Simplex 방법은 사용할 수 없으며 목적 함수와 제약 조건이 모두 문제에있는 변수의 선형 조합 인 경우에만 적용됩니다.

선형 프로그래밍 방법

비선형 프로그래밍 문제의 경우 사용되는 주요 방법은 다음과 같습니다.

1.- 그래픽 방법.

2.-솔루션 영역의 경계를 탐색하기위한 라그랑주 승수.

3. 목적 함수의 극단을 탐색하기위한 기울기 계산.

4.- 널 그라디언트 포인트를 찾기 위해 내림차순 방법.

5.- 라그랑주 승수의 수정 된 방법 (Karush-Kuhn-Tucker 조건 사용).

그래픽 방법을 사용한 솔루션의 예

그래픽 방법을 사용한 솔루션의 예는 그림 2에서 볼 수있는 것입니다.

그림 2. 비선형 제한 및 그래픽 솔루션이있는 비선형 문제의 예. 출처 : F. Zapata.

식

-연습 문제 1 (그래픽 방법)

특정 회사의 이익 G는 제품 X의 판매량과 제품 Y의 판매량에 따라 달라지며, 이익은 다음 공식에 의해 결정됩니다.

G = 2 (X-2) ² + 3 (Y-3) ²

금액 X 및 Y에는 다음과 같은 제한이있는 것으로 알려져 있습니다.

X≥0; Y≥0 및 X + Y ≤ 7

최대 이득을 생성하는 X 및 Y 값을 결정하십시오.

그림 3. 비선형 프로그래밍을 사용하여 최대 수익을 찾기 위해 회사의 수익을 수학적으로 모델링 할 수 있습니다. 출처 : Pixabay.

해결책

이 문제에서 목적 함수는 비선형이지만 제약 조건을 정의하는 부등식은 있습니다. 이것은 비선형 프로그래밍 문제입니다.

이 문제의 해결을 위해 그래픽 방법이 선택됩니다.

먼저 솔루션 영역이 결정되며 이는 제한 사항에 의해 제공됩니다.

X≥0으로; Y≥0, 해는 XY 평면의 1 사분면에서 찾아야하지만 X + Y ≤ 7도 사실이어야하므로 해는 X + Y = 7 선의 아래쪽 절반 평면에 있습니다.

해 영역은 선의 아래쪽 절반 평면과 1 사분면의 교차점으로 해가 발견되는 삼각형 영역이됩니다. 그림 1에 표시된 것과 동일합니다.

반면에 게인 G는 데카르트 평면에서도 표현할 수 있습니다. 방정식은 중심이있는 타원 (2,3)이기 때문입니다.

타원은 다양한 G 값에 대해 그림 1에 나와 있습니다. G 값이 높을수록 이득이 커집니다.

지역에 속하는 솔루션이 있지만 최대 G 값을 제공하지 않는 반면 G = 92.4와 같은 다른 솔루션은 녹색 영역, 즉 솔루션 영역 밖에 있습니다.

그런 다음 X와 Y가 솔루션 영역에 속하는 G의 최대 값은 다음과 같습니다.

G = 77 (최대 이득), X = 7 및 Y = 0에 대해 제공됩니다.

흥미롭게도 최대 이익은 제품 Y의 판매량이 0이고 제품 X의 양이 가능한 최대 값에 도달 할 때 발생합니다.

-연습 2 (분석 방법 : 라그랑주 승수)

영역 g (x, y) = x ² + y ^2-1 = 0 에서 함수 f (x, y) = x ² + 2y ^2를 최대로 만드는 해 (x, y)를 찾습니다 .

해결책

목적 함수 f (x, y)와 제한 g (x, y) = 0이 둘 다 변수 x와 y의 선형 조합이 아니기 때문에 이것은 분명히 비선형 프로그래밍 문제입니다.

먼저 라그랑주 함수 L (x, y, λ)을 정의해야하는 라그랑주 승수 방법이 사용됩니다.

L (x, y, λ) = f (x, y)-λ g (x, y) = x ² + 2y ² -λ (x ² + y ^2-1 )

여기서 λ는 라그랑주 승수라고하는 매개 변수입니다.

제한 g (x, y) = 0으로 주어진 솔루션 영역에서 목적 함수 f의 극단 값을 결정하려면 다음 단계를 따르십시오.

-x, y, λ에 대한 라그랑주 함수 L의 편도 함수를 찾습니다.

-각 미분을 0으로 균등화하십시오.

다음은 이러한 작업의 순서입니다.

1. ∂L / ∂x = 2x-2λx = 0
2. ∂L / ∂y = 4y-2λy = 0
3. ∂L / ∂λ =-(x ² + y ^2-1 ) = 0

가능한 시스템 솔루션

이 시스템의 가능한 솔루션은 λ = 1이므로 첫 번째 방정식이 충족되고,이 경우 y = 0이므로 두 번째가 충족됩니다.

이 솔루션은 세 번째 방정식이 충족 될 때 x = 1 또는 x = -1임을 의미합니다. 이러한 방식으로 두 가지 솔루션 S1 및 S2를 얻었습니다.

S1 : (x = 1, y = 0)

S2 : (x = -1, y = 0).

다른 대안은 λ = 2이므로 y 값에 관계없이 두 번째 방정식이 충족됩니다.

이 경우 첫 번째 방정식이 충족되는 유일한 방법은 x = 0입니다. 세 번째 방정식을 고려할 때 S3 및 S4라고하는 두 가지 가능한 솔루션 만 있습니다.

S3 : (x = 0, y = 1)

S4 : (x = 0, y = -1)

이러한 솔루션 중 목적 함수를 최대화하는 솔루션을 찾기 위해 f (x, y)로 대체합니다.

S1 : f (1, 0) = ¹² + 2.0 ² = 1

S2 : f (-1, 0) = (-1) ² + 2.0 ² = 1

S3 : f (0, 1) = 0 ² + 2.1 ² = 2

S4 : f (0, -1) = 0 ² + 2 (-1) ² = 2

x와 y가 원주 g (x, y) = 0에 속할 때 f를 최대화하는 해는 S3과 S4라는 결론을 내립니다.

값 쌍 (x = 0, y = 1) 및 (x = 0, y = -1)은 해 영역 g (x, y) = 0에서 f (x, y)를 최대화합니다.

-연습 문제 3 (널 그래디언트)

목적 함수에 대한 해 (x, y)를 찾습니다.

f (x, y) = x ² + 2 y ²

영역 g (x, y) = x ² + y ^2-1 ≤ 0 에서 최대 값을 지정하십시오 .

해결책

이 연습은 연습 2와 유사하지만 솔루션 (또는 제한) 영역은 원주 g (x, y) = 0, 즉 원 g (x, y) ≤ 0의 내부 영역까지 확장됩니다. 여기에는 다음이 포함됩니다. 원주와 내부 영역에.

경계의 솔루션은 연습 2에서 이미 결정되었지만 내부 영역은 아직 탐구해야합니다.

이를 위해 함수 f (x, y)의 기울기를 계산하고 0으로 설정하여 솔루션 영역에서 극단 값을 찾아야합니다. 이것은 x와 y에 대해 각각 f의 편도 함수를 계산하고 0으로 설정하는 것과 같습니다.

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

이 연립 방정식에는 원 g (x, y) ≤ 0에 속하는 유일한 해 (x = 0, y = 0)가 있습니다.

함수 f에서이 값을 대체하면 다음과 같은 결과가 나타납니다.

f (0, 0) = 0

결론적으로 (x = 0, y = 1) 및 (x = 0, y = -1) 값에 대해 함수가 해 영역에서 취하는 최대 값은 2이고 해 영역의 경계에서 발생합니다. .

참고 문헌

1. Avriel, M. 2003. 비선형 프로그래밍. 도버 출판.
2. 바 자라. 1979. 비선형 프로그래밍. John Wiley & Sons.
3. Bertsekas, D. 1999. 비선형 프로그래밍 : 2 판. Athena Scientific.
4. Nocedal, J. 1999. 수치 최적화. Springer-Verlag.
5. Wikipedia. 비선형 프로그래밍. 출처 : es.wikipedia.com