- 운영에 관한 연구
- 조직의 설계, 운영, 관리에 관한 의사결정을 계량적으로, 체계적으로 분석, 해결하고자 하는 학문
경영과학의 대상 : 합리적인 의사결정이 요구되는 분야
역할 : 의사결정자에게 최적의 의사결정을 할 수 있도록 정보를 제공
OR모형 접근 방법
절차
- 문제를 정의하고 관련자료를 수집
- 문제를 정의하는 수학적 모형을 설립
- 모형으로부터 해를 찾는 절차의 개발
- 모형을 검증한 후 개선
- 실행
모델링 예제
수학적 언어로 표현해야 함
의사결정 변수를정의 -> 제약식 정의 -> 목적함수 정의
의사결정변수
- 의사 결정 되어야 할 미지의변수
# 매일밤 A, B 기계의 가동 횟수
x = 기계 A의 가동 횟수
y = 기계 B의 가동 횟수 제약조건
- 해결책이 되기 위해 반드시 만족해야 하는 조건
기계A를 x번, B를 y번 작동시킬 떄 만들어지는 도넛의 양
#초코
400x + 100y >= 1000
# 슈가
300x + 100y >= 800
# 크림
300x + 500y >= 2000
# 의사결정변수의 제약 조건
X,y >= 0목적 함수
- 달성하고자 하는 목표
#총 가동 비용(Minimize)
150x + 130y
알고리즘 개발
- 문제의 해답을 도출하기 위한 절차
- 최적해(Optional solution), 실행가능해(feasible solution)를 찾도록 노력
근사해법
- 발견적 기법
- 메타휴리스틱
- 부분최적해 등이 존재
모형의 검증/구현 및 실행
모형을 검증하고 개선
모형의 결점
- 제약조건의 미반영
- 파라미터의 추정 오류 등
모형의 유효성 검증
- 얻어진해에 대하여 유용성, 적절성 등의 측면에서 실행 가능성을 검토
- 구한 해가 현실적으로 의사결정에 옮길 수 없는 것이라면, 문제점의 단계나 모형 수립 단계에서 제약조건을 추가/수정 해야 함
선형계획 개론
수리계획 모형
최적화 문제 : 가용자원이 제한된 상황에서 최적의 답을 구하고자 하는 의사결정 문제
- 결정변수 : 의사결정자의 결정사항을 구체화
- 제약조건 : 결정 변수 결정시 가해진 제약 및 고려사항
- 목적 : 의사결정에서 달성하고자 하는 목표
수리계획 모형
- 변수, 제약, 목적의 관계를 수리적으로 정형화한 실체
구조
- 의사결정 변수들로 표현(목적함수와 제약식)
선형계획
- 수리모형의 하나
- 많은 현실적인 문제들을 모델링 가능
- 손으로 쉽게 풀 수 있다
형태는 다음과 같다
-
모든 결정 변수들이 연속형
- 연속형(실수값) / 이산형(정수 or 자연수)
-
하나의 목적함수
-
목적함수와 제약식이 결정 변수들의 선형식으로 표현
선형
두 변수의 관계
- 하나의 변수의 변화에 따른 다른 하나의 변수의 변화 비율이 일정함
예제에서
- 결정변수 x, y는 연속형
- 목적함수또한 선형
- 제약식도 선형
선형 계획 모델링 순서
- 결정변수를 결정
- 목적 함수를 결정변수의 선형식으로 표현
- 문제의 제약들을 선형의 부등식 또는 등식으로 표현
Simplex method
임의의 CPF 해에서 시작하여 더 좋은 인접 CPF 해로 이동
-> 최적해에 도달할때까지 반봅
CP해 : 2개 이상의 제약식의 교차점
- 교차하는 제약식을 동시에 등호로 만족시키는 점
CPF 해
- feasible한 해
N개의 의사결정 변수
- n개의 제약식의 교차점
- 두개의 CPF해가 n-1개의제약식 경계를 공통으로 가지고 있으면 인접하다고 함
- 인접합 CPF 해 : 공통으로 가진 제약식의 경계를 하나의 선분으로 연결
최적해 검사
- 최소한 하나의 최적해를 가지는 선형계획 문제의 어떤 CPF해가
인접한 더 좋은 목적값을 가지는 CPF해가 없다면, 그 해는 최적해이다
핵심 개념들
simplex 방법은 CPF해에 초점을 두는 방식
- 가장 좋은 CPF해 == 하나의 최적해
반복적 알고리즘
- 초기화 : 초기 cpf해를 찾고 반복을 준비
- 최적화 검사 : 현재 CPF해가 최적해인가?
- 반복 : 더 좋은 CPF해를 찾아서 이동
simplex 방법 준비
모형의 확장형
- 모든 제약식이 등식
- 모든 변수는 비음
- 우변 상수는 비음
여유 변수
- 부등식을 등식으로 변환하기 위해 사용
x1 <= 4 //일때
여유변수 x3 = 4 - x1
x1 <= 4 -> x1 + x3 = 4, x3 >= 0여유 변수의 값이 0이면 : 해당 제약식의 경계선에 놓여 있다
여유 변수의 값 > 0이면 : 해당 제약식의 가능해 영역에 놓여 있다
여유 변수의 값 < 0이면 : 해당 제약식의 불가능해 영역에 놓여 있다
변수의 갯수 : 5
방정식의 수 : 3
기저해의 성직
- 변수는 비기저변수 혹은 기저변수로 설정
- 기저변수의 개수는 기능제약식 (등식)의 개수(m), 비기저 변수의 개수
는 전체변수의 수 – 기능제약식 수 (n - m) - 비기저 변수는 0
- 기저변수의 값은 linear system을 풀어서 얻는다. (기저변수의 집합 : 기
저(basis) ) - 기저변수가 비음조건을 만족하면, 기저 가능해 (BFS)
쌍대 이론
bound(한계)
A given LP
- 동일한 데이터로생성, 다른 structure
- given lp를 풀지 않고 최적의 목적식 값에 대한 상한을 제공
목적함수 값(optimization problem)
- 하한(하나의 실행가능해) <= 최적값 <= 상한(완화문제 or 쌍대 문제)
민감도 분석
매개변수의 변화에 대한 최적해의 변화
민감한 매개변수
LP 모델 수립 당시 상황에 변화가 생겼을 경우
-
돌발 상황을 인한 값의 변화
-> 원유 값 상승으로 인한 오븐 가동 비용의 증가
-> 공장 1 설비 교체로 인한 사용가능 시간의 변화 -
때로는 어떤 의사결정을 내리기전 그 영향을 체크하기 위해 의도적으로 상수값을 바꿔가며 테스트 해보기도 함
변화의 발생시
- 문제를 다시 풀어서 새로운 의사결정
- 문제를 풀어서 얻은 데이터를 이용하여 변경되는 의사결정 값을 파악
-> 민감도 데이터를 이용
민감도 데이터를 구하는 방법 중 하나는 엑셀을 이용하는 것
- 해찾기 기능을 사용하여 얻을 수 있는 세가지 보고서 중 하나
