Linear Programming.

Presentation on theme: "Linear Programming."— Presentation transcript:

1 Linear Programming

2 복잡한 세상 읽기 복잡한 세상에서 명확한 답을 찾자 흙수저라서 가지고 있건 별로 없는데 최고의 효율을 내자
Mathematical Programming 최적화 Optimization

3 Optimization A field of management science that finds the optimal, or most efficient, way of using limited resources to achieve the objectives of an individual of a business.

4 Optimization(최적화) (마케팅) 광고매체선정, 유통단지입지선정
(마케팅) 광고매체선정, 유통단지입지선정 (재무관리) 포트폴리오 구성, 자금운용계획, 자금조달방법결정 (인사관리) 인력수급계획, 교대근무계획 (생산관리) 생산계획 및 재고관리문제, 생산제품배합문제, 생산 및 배분 문제 재테크를 하려고 합니다. 100만원이 있는데 어디에 투자할까요? 내일 A,B과목이 시험인데 내가 잘하는 건 A과목, 어느 과목에 얼마의 시간을 투자해야 만족스러운 결과를 얻을까요?

5 최적화 문제에 필요한 기본 3가지 목적함수 의사결정변수 제약조건

6 Subject to: f1(X1, X2, …, Xn)<=b1
최적화 문제의 기본 형식 MAX (or MIN): f0(X1, X2, …, Xn) Subject to: f1(X1, X2, …, Xn)<=b1 : fk(X1, X2, …, Xn)>=bk fm(X1, X2, …, Xn)=bm Note: If all the functions in an optimization are linear, the problem is a Linear Progra mming (LP) problem

7 Linear Programming 세상이 Linear(선)으로
MAX (or MIN): c1X1 + c2X2 + … + cnXn Subject to: a11X1 + a12X2 + … + a1nXn <= b1 : ak1X1 + ak2X2 + … + aknXn >=bk am1X1 + am2X2 + … + amnXn = bm

8 Linear Programming 그래프 Simplex Method (George Danzig)
Interior Point Method (Narendra Karmarkar)

9 Linear Programming - Example
Blue Ridge Hot Tubs사는 두 가지 종류의 욕조를 만든다 최대의 이익을 내도록 하려면 각각 몇 개를 제작해야 하는가 아쿠아 스파 하이드로 럭스 펌프 1 개 1 개 노동시간 9 시간 6 시간 배관 12 feet 16 feet 개당 이익 $350 $300 200개의 펌프, 1566의 노동 시간, 2880 feet의 배관을 사용가능

10 Linear Programming – 5단계 방법
문제이해하기 2. 의사결정변수 파악하기 X1= 아쿠아 스파 제작 개수 X2= 하이드로 럭스 제작 개수 3. 의사결정변수를 이용해선형의 목적식 작성 MAX: 350X X2

11 Linear Programming – 5단계 방법
4. 의사결정변수를 이용해 제약식 작성 1X1 + 1X2 <= 200 } 펌프 9X1 + 6X2 <= 1566 } 노동시간 12X1 + 16X2 <= 2880 } 배관 5. 의사결정변수의 상한과 하한을 정함 X1 >= 0 X2 >= 0

12 Linear Programming - Example
MAX: 350X X2 1X1 + 1X2 <= 200 } 펌프 9X1 + 6X2 <= 1566 } 노동시간 12X1 + 16X2 <= 2880 } 배관 X1 >= 0 X2 >= 0

13 boundary line of pump constraint
첫번째 제약식 그리기 X2 X1 250 200 150 100 50 (0, 200) (200, 0) boundary line of pump constraint X1 + X2 = 200

14 boundary line of labor constraint
두번째 제약식 그리기 X2 X1 250 200 150 100 50 (0, 261) (174, 0) boundary line of labor constraint 9X1 + 6X2 = 1566

15 boundary line of tubing constraint
세번째 제약식 그리기 X2 X1 250 200 150 100 50 (0, 180) (240, 0) boundary line of tubing constraint 12X1 + 16X2 = 2880 Feasible Region

16 실행 가능해(Feasible solution)
X2 X1 250 200 150 100 50

17 목적함수로 최적해 찾기 X2 X1 최적해 optimal solution 250 200 150 $66,100 100 50
최적해 optimal solution X1=122, X2=200-X1=78 $66,100

18 Thank you