Introduction to Operations Research, 9th Edition

Presentation on theme: "Introduction to Operations Research, 9th Edition"— Presentation transcript:

1 Introduction to Operations Research, 9th Edition
Fred S. Hillier

2 Chapter 3 Wyndor Glass Co. Mary’s Radiation Therapy
Distribution Unlimited Co. Minimum Cost Flow

3

4

5

6 의사결정변수(Decision Variable)
: 모형은 활동의 수준에 대한 결정을 𝑥 1 , 𝑥 2, ···· 𝑥 𝑛 목적함수 (Objective Function) 기능 제약식 (Functional Constraints) , 구조적 제약식 (Structural Constraints) 비음 제약식 (Nonnegativity Constraints) , 비음 조건(nonnegativity)

7 가능해 (feasible solution) : 모든 제약조건이 만족하는 해
불가능해 (infeasible solution) : 제약조건 중 적어도 하나가 만족되지 않는 해 가능해 영역 (feasible region)은 모든 가능해 집합 최적해(optimal solution) : 목적함수가 가장 좋은 값을 갖는 가능해 가장 좋은 값 (most favorable value) : 목적함수가 최대화되면 가장 큰 값이고 목적함수가 최소화되면 가장 작은 값

8 꼭짓점 가능해 (corner-point feasible(CPF) solution, CPF해) : 가능해 영역의 꼭짓점에 놓여 있는 가능해
: 가장 좋은 CPF해가 최적해가 됨. 문제가 하나의 최적해만 갖는다면, 그것은 반드시 CPF해가되며 만일 문제가 복수의 최적해를 갖는다면, 그중 최소한 2개는 CPF 해이다. 예) Wyndor 유리회사 예제는 유일한 최적해 ( 𝑥 1 , 𝑥 2 )=(2,6)을 가지는 동시에 CPF해가 된다. 여러 개의 최적해를 갖도록 변경되면 2개의 최적해 (2,6)과 (4,3)들이 CPF해가 된다.

9 선형계획의 가정들 비례성(Proportionality) 가합성 (Additivity) 가분성 (Divisibility) 확실성 (Certainty)

10 Minimize Z=0.4 𝑥 𝑥 2 subject to 0.3 𝑥 𝑥 2 ≤ 2.7 0.5 𝑥 𝑥 2 = 6 0.6 𝑥 𝑥 2 ≥ 6 𝑥 1 ≥ 0 , 𝑥 2 ≥ 0

11