Introduction to Operations Research, 9th Edition Fred S. Hillier
Chapter 3 Wyndor Glass Co. Mary’s Radiation Therapy Distribution Unlimited Co. Minimum Cost Flow
의사결정변수(Decision Variable) : 모형은 활동의 수준에 대한 결정을 𝑥 1 , 𝑥 2, ···· 𝑥 𝑛 목적함수 (Objective Function) 기능 제약식 (Functional Constraints) , 구조적 제약식 (Structural Constraints) 비음 제약식 (Nonnegativity Constraints) , 비음 조건(nonnegativity)
가능해 (feasible solution) : 모든 제약조건이 만족하는 해 불가능해 (infeasible solution) : 제약조건 중 적어도 하나가 만족되지 않는 해 가능해 영역 (feasible region)은 모든 가능해 집합 최적해(optimal solution) : 목적함수가 가장 좋은 값을 갖는 가능해 가장 좋은 값 (most favorable value) : 목적함수가 최대화되면 가장 큰 값이고 목적함수가 최소화되면 가장 작은 값
꼭짓점 가능해 (corner-point feasible(CPF) solution, CPF해) : 가능해 영역의 꼭짓점에 놓여 있는 가능해 : 가장 좋은 CPF해가 최적해가 됨. 문제가 하나의 최적해만 갖는다면, 그것은 반드시 CPF해가되며 만일 문제가 복수의 최적해를 갖는다면, 그중 최소한 2개는 CPF 해이다. 예) Wyndor 유리회사 예제는 유일한 최적해 ( 𝑥 1 , 𝑥 2 )=(2,6)을 가지는 동시에 CPF해가 된다. 여러 개의 최적해를 갖도록 변경되면 2개의 최적해 (2,6)과 (4,3)들이 CPF해가 된다.
선형계획의 가정들 비례성(Proportionality) 가합성 (Additivity) 가분성 (Divisibility) 확실성 (Certainty)
Minimize Z=0.4 𝑥 1 + 0.5 𝑥 2 subject to 0.3 𝑥 1 + 0.1 𝑥 2 ≤ 2.7 0.5 𝑥 1 + 0.5 𝑥 2 = 6 0.6 𝑥 1 + 0.4 𝑥 2 ≥ 6 𝑥 1 ≥ 0 , 𝑥 2 ≥ 0