제약이 없는 비선형계획모형 등식제약하의 비선형계획모형 부등식제약하의 비선형계획모형 secom.hanabt.ac.kr

Presentation on theme: "제약이 없는 비선형계획모형 등식제약하의 비선형계획모형 부등식제약하의 비선형계획모형 secom.hanabt.ac.kr"— Presentation transcript:

1 제약이 없는 비선형계획모형 등식제약하의 비선형계획모형 부등식제약하의 비선형계획모형 secom.hanabt.ac.kr
경영과학(Ⅰ) 제 11 장 비선형계획법 제약이 없는 비선형계획모형 등식제약하의 비선형계획모형 부등식제약하의 비선형계획모형 secom.hanabt.ac.kr

2 ▶ 제약이 없는 비선형계획모형 비선형계획법(NLP ; non-linear programming) : 목적함수나 제약조건이 1차식이 아닌 함수(비선형함수)로 표시되는 수리계획법 현실의 비선형성을 선형계획법에서는 민감도분석에 의해 보완하지만, 근본적인 방법은 비선형계획모형 으로 수식화하여 최적해를 구하는 것이다. 비선형계획법은 선형계획법의 심플렉스법과 같은 효율적인 해법이 존재하지 않는다.

3 ▶ 제약이 없는 비선형계획모형 최대(소)치와 극대(소)치의 개념 극대치 = 최대치 극소치 극대치 극소치 = 최소치

4 ▶ 제약이 없는 비선형계획모형 ◁ 변수가 하나인 경우 ▷ 미분가능 비선형함수 f(x)에 대하여, 가 극대치가 되기 위한 조건
◁ 변수가 하나인 경우 ▷ 미분가능 비선형함수 f(x)에 대하여, 가 극대치가 되기 위한 조건 필요조건 : 함수 f(x)가 x = 에서 극대치를 가지면, f '( ) = 0 충분조건 : f(x)가 x = 에서 2차 미분가능하고, f '( ) = 0, f ''( ) < 이면 는 f(x)의 극대치이다. 극소치의 경우 : 필요조건은 같고, 충분조건은 f ''( ) > 0 이다.

5 ▶ 제약이 없는 비선형계획모형 예제 모형 가정용 요리기구를 생산ㆍ판매하고 있는 E사의 판매가격 결정문제
신제품에 대한 가격 p(단위 : 만원), 월별 수요 d라 표시하면  d = 1, p 제품의 단위당 원가가 5만원일 때, 이익을 최대로 하는 판매가격을 결정

6 ▶ 제약이 없는 비선형계획모형 이익함수를 f(p)로 나타내면, f(p) = pㆍd - 5ㆍp
      = p(1, p) - 5(1, p)      = -100p2 + 1,700p - 6,000 따라서 최적 판매가격 는 다음의 두 조건을 만족해야 한다. (1) f'( ) = (2) f''( ) < 0 (1) f'(p) = -200p + 1,700 = 0 에서 = 8.5(만원) (2) f''(p) = -200 < 0 즉, = 8.5는 f(p) 최대화를 위한 필요조건과 충분조건을 모두 만족 따라서 신제품에 대한 E사의 최적결정가격은 8만 5천원, 예상 총이익은 1,225만원이다.

7 ▶ 제약이 없는 비선형계획모형 ◁ 변수가 여러개인 경우 ▷ 제약이 없고 변수가 여러개인 비선형함수의 극대(소)치 필요조건
◁ 변수가 여러개인 경우 ▷ 제약이 없고 변수가 여러개인 비선형함수의 극대(소)치 필요조건 필요조건 함수 f(x1, x2, …, xn)가 (x1, x2, …, xn)에서 극대(소)치를 가지면,                                 ∂f(x1, x2, …, xn)  n개의 편미분함수, ─────── = 0 이다.                                         ∂xi

8 ▶ 제약이 없는 비선형계획모형 예제 모형 H전자의 최적주문량 결정 문제 대형 칼라TV의 1년간 예상판매대수 : 120대
대당 연간 재고유지비 : 8만원 월간 재고부족비 : 1만원 1회 주문비용 : 2만원

9 ▶ 제약이 없는 비선형계획모형 1회 주문량 Q, 누적된 재고부족분을 S라 하면, 연간 총비용 T(Q, S),
               240         4(Q-S)2         6S2 T(Q, S) = ─── + ───── + ───                        Q             Q                Q 변수가 2개인 비선형계획모형 T(Q, S)를 Q와 S에 대해 편미분을 하여 그 값을 0으로 놓으면, ∂T(Q, S)         240         8(Q-S)         4(Q-S)2     6S2 (1) ───── = ─── + ───── - ──── - ───  = 0        ∂Q             Q2            Q                   Q2         Q2  ∂T(Q, S)           8(Q-S)      12S (2) ─────  = - ──── + ─── = 0        ∂S                   Q          Q 위의 연립방정식을 풀면, Q = 10, S = 4 , 총비용 T = 48(만원) ☞ 이것이 총비용을 최소로 하는 값이라고 단정할 수는 없다. (충분조건 검토 필요)

10 ▶ 등식제약하의 비선형계획모형 n개의 결정변수(x1, x2, …, xn)와 m개의 등식제약하의 비선형모형
Max.(또는 Min.)   f(x1, x2, …, xn)  s.   t.                 g1(x1, x2, …, xn) = 0                          g2(x1, x2, …, xn) = 0                                   :                         gm(x1, x2, …, xn) = 0

11 ▶ 등식제약하의 비선형계획모형 라그랑지 승수법(Lagrange multiplier method) 원래의 모형에 대해 라그랑지 승수를 도입하여 목적함수와 등식의 제약식을 연결하는 라그랑지 함수(Lagrange function)를 만들어 제약이 없는 비선형계획모형으로 변환한 후 극치를 찾는다. i 번째 제약식에 대응하는 라그랑지 승수를 λi라 하면, 라그랑지 함수 L(x1, x2, …, xn, λ1, λ2, …, λm)    = f(x1, x2, …, xn) + λ1[g1(x1, x2, …, xn)]                         + λ2[g2(x1, x2, …, xn)]                                        :                             + λm[gm(x1, x2, …, xn)]

12 ▶ 등식제약하의 비선형계획모형 등식제약하에서 라그랑지승수법의 필요조건 필요조건
(x1, x2, …, xn)가 원래 모형의 최적해가 되려면, 라그랑지 함수 L에 대하여 다음의 조건을 만족하여야 한다.  ∂L ── = 0,  j = 1, 2, …, n   ∂xj  ∂L ── = 0,  i = 1, 2, …, m   ∂λi

13 ▶ 등식제약하의 비선형계획모형 예제 모형 S기계의 특수장비 생산계획문제 향후 2년간 1,000대의 특수장비를 제작ㆍ공급계획
생산비용은 각각 금년 100(만원)과 내년 80(만원)으로 추정 금년과 내년의 생산량이 다르면 생산량 차이의 제곱에 비례하는 추가 비용이 발생 금년의 생산량을 x1, 내년의 생산량을 x2라 하면 추가비용 C(x1, x2) 는                    (x1 - x2) C(x1, x2) = ──────                        100

14 ▶ 등식제약하의 비선형계획모형 총비용 TC = 정상생산비용 + 추가비용이므로, 다음의 비선형계획모형이 된다.
                                              (x1 - x2) Min. TC(x1, x2) = 100x1 + 80x2 + ──────                                                      100 s.  t.    x1 + x2 = 1,000 라그랑지 승수를 λ라 하면, 라그랑지 함수는 다음과 같다.                                            (x1 - x2) L(x1, x2, λ) = 100x1 + 80x2 + ────── + λ(x1 + x2 - 1,000)                                                  100 이를 x1, x2, λ에 대해 각각 편미분하여 이를 0으로 놓으면,  

15 ▶ 등식제약하의 비선형계획모형 ∂L (x1 - x2) ─── = 100 + ────── - λ = 0 ∂x1 50
위 식을 풀면, x1 = 250, x2 = 750, λ = 90, TC = 87,500(만원) (x1, x2) = (250, 750)이 총비용을 최소로 하는 값인지를 확인하기 위하여는, 2차 편미분 필요 라그랑지 승수 λ = 90의 의미 : 최적 상태에서 특수장비를 한 대 더 생산하면 90의 비용이 추가적으로 소요됨(LP의 쌍대변수값)

16 ▶ 부등식제약하의 비선형계획모형 가장 일반적인 의사결정상황을 표현 → 반면에 최적해를 구하기는 훨씬 복잡
 가장 일반적인 의사결정상황을 표현 → 반면에 최적해를 구하기는 훨씬 복잡 쿤-터커 정리(Kuhn-Tucker Theorem) : 주어진 점이 최적해가 되기 위한 필요조건을 규정 일반적인 부등식제약하의 최대화 비선형계획모형 (모든 함수 미분가능, 편미분벡터 선형독립) Max.   f(x1, x2, …, xn) s. t.   g1(x1, x2, …, xn) ≤ b1     g2(x1, x2, …, xn) ≤ b2                    :        gm(x1, x2, …, xn) ≤ bm              xj ≥ 0, j = 1, …, n

17 ▶ 부등식제약하의 비선형계획모형 쿤-터커 정리 (필요조건)
: (x1, x2, …, xn)이 원래 모형의 최적해라면, 다음 조건을 만족시키는 라그랑지 승수 λ1, λ2, …, λm이 존재한다.          ∂f       m      ∂gi  ① ── - ∑ λi ── ≤ 0, j = 1, 2, …, n        ∂xj      i=1    ∂xj ② gi(x1, x2, …, xn) - bi ≤ 0, i = 1, 2, …, m ③ xj ≥ 0, j = 1, 2, …, n ④ λi ≥ 0, i = 1, 2, …, m                        ∂f       m     ∂gi  ⑤ xj = 0 또는 ── - ∑ λi ── = 0, j = 1, 2, …, n                         ∂xj     i=1     ∂xj ⑥ λi = 0 또는 gi(x1, x2, …, xn) - bi = 0, i = 1, 2, …, m

18 ▶ 부등식제약하의 비선형계획모형 예제 모형 앞의 S기계 예제 : 특수장비를 800대 이하로 생산해야 하는 경우의 최적 생산계획
부등식제약식(  x1 + x2 ≤ 800 )이 추가된 비선형계획모형                                                  (x1 - x2) Min. TC(x1, x2) = 100x1 + 80x2 + ──────                                                       100 s. t.        x1 + x2 ≤ 800                     x1, x2 ≥ 0

19 ▶ 부등식제약하의 비선형계획모형 쿤-터커의 필요조건 적용 ∂TC (x1 - x2) ─── = 100 + ───── ∂x1 50
   ∂g            ∂g ─── = ─── =    ∂x1           ∂x2

20 ▶ 부등식제약하의 비선형계획모형 따라서 최적해가 되려면 다음과 같은 조건이 만족되어야 한다.
                 (x1 - x2)                            (x1 - x2)   ① ────── - λ ≤ 0, 80 - ────── - λ ≤ 0                        50                                   50 ② x1 + x ≤ 0 ③ x1 ≥ 0, x2 ≥ 0 ④ λ ≥ 0                                 (x1 - x2) ⑤ x1 = 0 또는 ────── - λ = 0                                         50                                (x1 - x2)     x2 = 0 또는 80 - ────── - λ =                                     50 ⑥ λ = 0 또는 x1 + x2 = 800

21 ▶ 부등식제약하의 비선형계획모형 ⑤번과 ⑥번의 조건을 세분화하면 다음과 같은 8가지 경우가 나온다.
⑴ x1 = 0, x2 = 0, λ = 0 ⑵ x1 = 0, x2 = 0, x1 + x2 = 800 ⑶ x1 = 0, -x1 + x2 - 50λ + 4,000 = 0, λ = 0 ⑷ x1 = 0, -x1 + x2 - 50λ + 4,000 = 0, x1 + x2 = 800 ⑸ x1 - x2 - 50λ + 5,000 = 0, x2 = 0, λ = 0 ⑹ x1 - x2 - 50λ + 5,000 = 0, x2 = 0, x1 + x2 = 800 ⑺ x1 - x2 - 50λ + 5,000 = 0, -x1 + x2 - 50λ + 4,000 = 0, λ = 0 ⑻ x1 - x2 - 50λ + 5,000 = 0, -x1 + x2 - 50λ + 4,000 = 0, x1 + x2 = 800

22 ▶ 부등식제약하의 비선형계획모형 이중 앞의 ①, ②, ③, ④번 조건을 만족시키는 경우는 ⑷, ⑹, ⑻의 세가지이다. 즉,
이중 앞의 ①, ②, ③, ④번 조건을 만족시키는 경우는 ⑷, ⑹, ⑻의 세가지이다. 즉, ⑷ x1 = 0, x2 = 800, λ = 96 ⑹ x1 = 800, x2 = 0, λ = 116 ⑻ x1 = 150, x2 = 650, λ = 90 x1과 x2 는 매년의 생산량이므로 0이 될 수 없다. → 쿤-터커의 필요조건을 만족시키는 해는 (x1, x2) = (150, 650), λ = 90이 된다. 따라서 이 문제의 최적해는 (x1, x2) = (150, 650), 총비용은 ,500(만원)이라고 추측 부등식제약하에서의 쿤-터커 조건은 등식제약하에서의 라그랑지승수법과 같은 개념

23 제 11 장 비선형계획법 수고하셨어요!! secom.hanabt.ac.kr