선형계획법 (Linear Programming)

2 선형계획법  목표값을 최대화 또는 최소화하는 의사 결정문제를 다루는 기법  강의 내용 선형계획법 모형 수립 도해법 심플렉스법 엑셀 최적화도구 – 해 찾기 기능

3 선형계획법 응용 분야  기업경영  ( 마케팅 ) 광고매체선정, 유통단지입지선정  ( 재무관리 ) 포트폴리오 구성, 자금운용계획, 자금조달방법결정  ( 인사관리 ) 인력수급계획, 교대근무계획  ( 생산관리 ) 생산계획 및 재고관리문제, 생산제품배합문제, 생산 및 배분 문제  식단 문제  원료혼합문제

4 현실문제와 LP 모형  LP 모형 구성 요소  의사결정변수 (decision variables)  목적함수 (objective function) 의사결정변수의 1 차함수로 표현1 차함수  제약조건식 (constraints) 의사결정변수의 1 차함수로 표현  현실문제와 LP 모형 대응관계  선택 대안 의사결정변수  목표 목적함수  상황적 제약 / 조건 제약조건식

5 선형계획법 문제의 모형화  최대화문제  목적함수식의 값을 최대로 하고자 하는 문 제  ( 예 ) 총수익을 최대화하고자 하는 경우  최소화문제  목적함수식의 값을 최소로 하고자 하는 문 제  ( 예 ) 총비용을 최소화하고자 하는 경우

6 ( 예제 2-1) 생산 제품 배합 문제  문제 정의  생산제품 : 갑, 을  공정 : 절삭공정, 조립공정  선택대안 : 갑, 을 제품 생산량  목표 : 판매 수익 최대화  상황적 제약  절삭공정 : 100 시간  조립공정 : 150 시간

7 개당 소요시간 갑을 가용공정시간 (1 주일당 ) 제품 공정 절삭 공정 조립 공정 시간 150 시간 개당 판매이익 20 만원 10 만원

8 결정변수, 목적함수, 제약조건식  결정변수 x 1 : 제품 ‘ 갑 ’ 생산량 x 2 : 제품 ‘ 을 ’ 생산량  목적함수 Max z = 20x x 2

9 결정변수, 목적함수, 제약조건식  제약조건식 x x 2 ≤ 100 ( 절삭 공정 ) 3x 1 + x 2 ≤ 150 ( 조립 공정 ) x 1 ≥ 0, x 2 ≥ 0 ( 비음제약조건 )

10 수학적모형 Max z = 20x x 2 s.t. x 1 + 2x 2 ≤ 100 3x 1 + x 2 ≤ 150 x 1 ≥ 0, x 2 ≥ 0

11 ( 예제 2-2) 사료 배합 문제  문제 정의  사료 : A, B  영양분 : 1, 2, 3  선택대안  사료 A, B 의 1 일 최적 구입량 결정  목표  사료 구입비용 최소화  상황적 제약  영양분 1 일 최소 섭취량

12 kg 당 영양분함유량 AB 최소 필요량 (1 일당 ) 사료 영양분 kg 당 구입비용 5 천원 7 천원

13 결정변수, 목적함수, 제약조건식  결정변수 x 1 : 사료 A 구입량 x 2 : 사료 B 구입량  목적함수 Min z = 5,000x 1 + 7,000x 2

14 결정변수, 목적함수, 제약조건식  제약조건식 0.2 x x 2 ≥ 30 ( 영양분 1) 0.3 x x 2 ≥ 50 ( 영양분 2) 0.3 x 2 ≥ 20 ( 영양분 3) x 1 ≥ 0, x 2 ≥ 0 ( 비음제약조건 )

15 수학적모형 Min z = 5000x x 2 s.t. 0.2 x x 2 ≥ x x 2 ≥ x 2 ≥ 20 x 1 ≥ 0, x 2 ≥ 0

16 ( 예제 2-3) 수송 및 배분 문제 각 물류창고에서 대리점으로의 TV 개당 수송비 대리점 물류창고 123 공급량 수요량 ( 단위 : 천원 )

17 ( 예제 2-3) 수송 및 배분 문제  문제 정의  물류창고 1, 2, 3  대리점 1, 2, 3  선택대안  물류창고 i 에서 대리점 j 로의 TV 수송량  목표  총수송비를 최소로 하는 수송방법을 결정  상황적 제약  각 물류창고의 TV 보유량  각 대리점의 TV 수요량

18 결정변수, 목적함수, 제약조건식  결정변수 x ij : 물류창고 i 에서 대리점 j 로의 TV 수송량 ( i=1, 2, 3, j =1, 2, 3 )  목적함수 Min z = 12x x x x x x x x x 33

19 결정변수, 목적함수, 제약조건식  제약조건식 x 11 + x 12 + x 13 = 300 ( 물류창고 1 의 공급량 ) x 21 + x 22 + x 23 = 150 ( 물류창고 2 의 공급량 ) x 31 + x 32 + x 33 = 150 ( 물류창고 3 의 공급량 ) x 11 + x 21 + x 31 = 200 ( 대리점 1 의 수요량 ) x 12 + x 22 + x 32 = 220 ( 대리점 2 의 수요량 ) x 13 + x 23 + x 33 = 180 ( 대리점 3 의 수요량 ) x ij ≥ 0, i=1, 2, 3, j =1, 2, 3 ( 비음제약조건 )

20 수학적모형 Min z = 12x x x x x x x x x 33 s.t. x 11 + x 12 + x 13 = 300 x 21 + x 22 + x 23 = 150 x 31 + x 32 + x 33 = 150 x 11 + x 21 + x 31 = 200 x 12 + x 22 + x 32 = 220 x 13 + x 23 + x 33 = 180 x ij ≥ 0, i=1, 2, 3, j =1, 2, 3

21 도해법 (Graphical Method)  ( 정의 ) 실행가능영역  모든 제약조건식들을 공통적으로 만족하는 영역 실행가능영역을 통과하는 목적함수식 그래프 중 가장 좋은 목적함수값을 제공해주는 실행가능영역상의 점을 찾음.  도해법의 기본원리  Simplex 법의 원리를 알아보기 위한 방법  결정변수 개수가 2 개일 때만 적용 가능  2 차원 좌표 평면에 제약조건식 그래프를 표시

22 ( 예제 2-4) 경동산업 ( 주 ) Max z = 40x x 2 s.t. x 1 + x 2 ≤ 180 4x 1 + 8x 2 ≤ x 1 + 6x 2 ≤ 1440 x 1 ≥ 0, x 2 ≥ 0 수학적 모형

23 Max z = 40x1 + 30x2 s.t. x1 + x2 ≤ 180 ① 4x1 + 8x2 ≤1,120 ② 9x1 + 6x2 ≤1,440 ③ x1≥0, x2≥0 ① ② ③

24 실행가능영역 ① ② ③ Max z = 40x1 + 30x2 s.t. x1 + x2 ≤ 180 ① 4x1 + 8x2 ≤1,120 ② 9x1 + 6x2 ≤1,440 ③ x1≥0, x2≥0

25 최적해  실행가능해 (feasible solution)  ( 기하학적 정의 ) 실행가능영역 내의 점 ( 예 ) ( x 1, x 2 )=(100, 50)  ( 대수학적 정의 ) 모든 제약조건을 만족하는 해  실행불가능해 (infeasible solution)  실행가능영역 밖의 점 ( 예 ) ( x 1, x 2 )=(100,120)  최적해 (optimal solution)  實行可能解들 중에서 가장 좋은 목적함수값을 제공 해 주는 解

26 목적함수식 그래프 z = 40x x 2 x 2 = - 4/3 x 1 + 1/30 z  p.25 [ 그림 2-3] ※ 기울기의 절대값이 클수록 직선의 경사는 급해진다.  최적해 : x 1 * =120, x 2 * =60, z * = 6,600

27 최적해 x 1 * =120, x 2 * =60 z * = 40 x x 2 = 6,600 Max z = 40x1 + 30x2 s.t. x1 + x2 ≤ 180 ① 4x1 + 8x2 ≤1,120 ② 9x1 + 6x2 ≤1,440 ③ x1≥0, x2≥0 x 2 = - 4/3 x 1 + 1/30 z ① ② ③

28 목적함수식 계수 변화  제품 A 의 개당 판매수익이 45 만원으로 변할 때, z = 45x x 2 x 2 = - 3/2 x 1 + 1/30 z

29 복수 최적해 Max z = 45x1 + 30x2 s.t. x1 + x2 ≤ 180 ① 4x1 + 8x2 ≤1,120 ② 9x1 + 6x2 ≤1,440 ③ x1≥0, x2≥0 ① ② ③

30 Simplex Method  LP 의 실행가능영역  볼록집합 (convex set)  극점 O, A, B, C, D  실행가능기저해 (BFS : Basic Feasible Solution)  최적해는 극점에서 발생  극점의 수는 유한 개 (finite)  특정 극점에서의 목적함수값이 인접한 극점보다 좋으면 이 특정 극점이 최적해임.  극점의 3 가지 특성 심플렉스법의 원리

31 실행가능영역 Max z = 40x1 + 30x2 s.t. x1 + x2 ≤ 180 4x1 + 8x2 ≤1,120 9x1 + 6x2 ≤1,440 x1≥0, x2≥0

32 Simplex Method 적용 1. 점 O(0, 0) z=0 2. 점 D(160, 0) z=6, 점 C(120, 60) z=6, 점 B(80, 100) z=6,200 점 C(120, 60) 가 최적해 최초의 극점으로부터 출발하여 인접한 극점으로 옮겨가는 반복적 연산과정

33 정규형과 표준형  LP 수학적 모형 형태  심플렉스법은 표준형을 대상으로 설계  정규형 (Canonical Form) ( 최대화 문제 ) : 제약조건식의 부등호가 모두 ‘≤’ 형태 ( 최소화 문제 ) : 제약조건식의 부등호가 모두 ‘≥’ 형태  표준형 (Standard Form) 제약조건식이 모두 등식으로 표시된 형태

34 엑셀 최적화도구 LP 모형스프레드시트 모형 결정변수 목적함수값 제약조건식 값을 바꿀 셀 목표 셀 제한조건

35 엑셀 스프레드시트 입력모형

36 셀 입력 - 입력 데이터  B6:C6 ( 제품 단위당 판매수익 )  B9:C11 ( 제품 단위당 생산에 소요되는 자원의 양 )  E9:E11 ( 다음 한 달 동안 자원의 조달가능량 )

37 변경할 셀, 목표 셀  셀범위 B5:C5  초기값으로 0 을 입력한다.  값을 바꿀 셀  목표 셀  셀 D6  총 판매수익을 나타냄.  D6 : =B6*B5+C6*C5

38 제한조건을 위한 입력 셀  D9:D11  D9 : = B9*$B$5+C9*$C$5  D9 를 D10:D11 에 복사한다.  각 자원의 실제 사용량

39 [ 해 찾기 ] 실행 방법 1) 엑셀 도구 (T) 메뉴의 해 찾기 (V) 명령 선택 2) 목표 셀 (E) 과 값을 바꿀 셀 (B) 에 해당 셀들 을 입력 3) 해의 조건 지정 4) 제한 조건 (U) 에 입력하기 위해 추가 (A) 버턴 을 클릭 5) 옵션 (O) 지정 6) 해 찾기 모델 설정 대화상자에서 실행 (S) 을 선택

40 제한조건  $D$9:$D$11 <= $E$9:$E$11  각 자원의 실제사용량이 가용량보다 적어야 한다는 조건  비음조건  $B$5:$C$5 >= 0

41 해 찾기 모델 설정

42 옵션 (O) 선택 - 선형모델 가정 체크

43 실행 (S) 선택

44 해 찾기 결과

45 최적해

46 최적해와 미사용자원량  최적해 x 1 * =120, x 2 * =60, z * = 6,600  미사용자원량  유리 : 180 – ( ) = 0  알루미늄 : 1120 – (4× ×60) = 160  제조공정시간 : 1440 – (9× ×60) = 0