Operations Research - 1 Spring 2007 OR-1 2007

Origins of OR Contribution of scientists and engineers during world war II. Air war in France, Battle of Britain (radar site selection and control), Submarine warfare, Design of B-29, .. Air war in France(1939): requests for 10 fighter squadron (120), losses 3 squadrons/2 days. -> retreat of fighters from France. Battle of Britain: integration of radar(hardware) and warning and control system. Addition of radar sites causes problems. (the name operational research (research in (military) operations) Maintenance of aircraft: For 350 flying hours, need 7 minor inspections( 2-5 days each) and a major inspection (14 days). Each aircraft had a devoted aircrew and a ground crew  change to central garage system. : Flying hour increased by 61% over previous best record. OR-1 2007

In 1941, attack kill probability was 2% - 3% Submarine warfare: Needed 170 man-hours by maintenance and ground staff to produce one hour of operational flying. More than 200 hours of flying to produce one attack on a surfaced U-boat. (34,000 man-hours for an attack) In 1941, attack kill probability was 2% - 3% -> 1.1M  1.7M man-hours needed to destroy one U-boat. (needed improvements) Important decision variables: Depth (time) setting for depth charge explosion Lethal radius Aiming errors in dropping the stick Orientation of the stick with respect to the U-boat Spacing between successive depth charges in the stick Low level bombsights OR-1 2007

Attack along U-boat track. Originally set 30/45 meters. Pilot reports showed, at time of attack, the U-boat still visible or submerged less than 15 seconds in 40% of attacks. Lethal radius of depth charge was around 5-6 meters. : Use shallower setting. 15m -> 10m (new fuses) -> 8m 250lb(110Kg) depth charges used: change to 600lb(270 Kg)(Air staff) or 100lb(45Kg)(ORS) charges? “aiming off” (aiming ahead): analysis showed 50% more kills without aiming off. Attack along U-boat track. Initially set 12m. ORS calculated 33m would increase kills by 35%. Pilot acted also as bomb aimer/release. -> recommended low level bombsight. 1943, increase kills per attack by 35% Overall effect: By 1945, the attack kill probability had risen to over 40%. OR-1 2007

After the war, methodologies used by the scientists adopted by government, industry. Called Operations Research, Operational Research (운용과학), Management Science (경영과학) 특징 : Use of mathematical models to solve decision problems arising in management of industry, government, military, …. E=mC2, F=ma, … OR-1 2007

Nature of OR “research on operations” Applied mathematics + computer science + management Models : Deterministic models (확정적 모형, OR-I) Stochastic models (확률적 모형, OR-II) Needed background: Algebra, calculus, discrete mathematics, probability, statistics, data structure, algorithm, data base, programming skills, …) Important thrusts in early stages   1. Technical progress (Simplex method for linear programming, Dantzig, 1947) 2.  Invention of computer and PC OR-1 2007

연구분야 Deterministic models Linear programming(선형계획법, linear optimization):1975, Nobel prize, Kantorovich, Koopmans (efficient allocation of resources) Nonlinear programming(비선형계획법):1990 Nobel prize, Markowitz (portfolio selection) OR-1 2007

Integer Programming(정수계획법), Combinatorial optimization (조합최적화) Knapsack problem Traveling salesman problem (외판원문제) n 개의 도시와 각 도시간의 거리가 주어져 있을 때 모든 도시들을 정확히 한번 씩 방문하고 출발 도시로 돌아올 때 이동거리를 최소화하는 도시들의 방문 순서는? ( PCB조립, Off-shore drilling, 배달문제등에 응용) site: http://www.tsp.gatech.edu/ OR-1 2007

각 도시들이 모두 연결되도록 도로 (통신선)를 놓으려면 어느 도로(통신선)를 건설해야 하는가? Networks and graphs 인천에서 강릉으로 가는 가장 빠른 길은? 각 도시들이 모두 연결되도록 도로 (통신선)를 놓으려면 어느 도로(통신선)를 건설해야 하는가? 서울에서 부산까지 화물을 최대한 얼마까지 보낼 수 있는가? 인천 강릉 대전 광주 부산 대구 서울 OR-1 2007

여러 단계(stage)를 거치며 시스템이 변화해 나갈 때 각 단계에서 어떤 의사결정을 내리는 것이 최적인가? Dynamic programming 여러 단계(stage)를 거치며 시스템이 변화해 나갈 때 각 단계에서 어떤 의사결정을 내리는 것이 최적인가? 정형화된 문제가 아니고 DP 알고리듬을 적용할 수 있는 구조를 갖는 문제들을 포함하여 지칭 Game theory 둘 혹은 그 이상의 사람이나 집단의 의사결정에 따라서 결과가 다르게 나타날 때 어떤 의사결정을 내리는 것이 최선인지, 협력이나 경쟁의 결과가 어떻게 나타나는지 연구 경제학, 마케팅 (1994, Nobel prize, Nash, Harsanyi, Selten) Computational complexity: 어떤 문제를 쉽게 풀 수 있는지 혹은 풀기가 어려운 지를 이론적으로 규명, 최적화의 기본 OR-1 2007

Queueing theory (대기이론) : 슈퍼마켓 계산대, 고속도로 톨게이트, 통신망의 패킷 딜레이 등 Stochastic models Markov chain: 어느 시점에서의 시스템의 상태에서 다음 시점에서 시스템이 가질 수 있는 상태의 확률이 알려져 있을 때 장기적으로 시스템이 어느 상태로 가고 또 이에 걸리는 평균 시간등을 분석 Queueing theory (대기이론) : 슈퍼마켓 계산대, 고속도로 톨게이트, 통신망의 패킷 딜레이 등 Decision analysis Simulation Reliability OR-1 2007

Steps of OR approaches Identifying the problem (problem may be vague, find appropriate objective (there frequently exist multiple objectives)) Construct a (math) model and data acquisition. Find model appropriate for objective. Deriving a solution (optimal or good enough solution) (Note that finding a good enough solution can be a serious challenge. e.g. air line crew scheduling problem, steel company, ship building, …) Test the model and the solution. Establishing control over the solution (documentation, maintenance) Implementation OR-1 2007

OR (최적화) 적용 분야 제조 스케쥴링 및 재고관리 전자회로 디자인 기계설비 배치 정유공정 생산공정관리 … 유통 유통망 설계 물류센터위치선정 수송 계획 결정 운송노선 결정 인력관리 … 통신 통신망설계 통신망 경로설정 기지국 위치선정 Power control … 공공 도시건설 도로건설 교통시스템 수립 상하수도 네트웍 설계 … … OR-1 2007

OR(최적화) 기법의 사용현황 문제점 훈련된 인력의 부족 ( 수학, 정보기술등에 고도의 훈련 필요) 문제해결 자체의 어려움 ( 지능화 프로젝트), 만병통치약의 부재 데이터의 부족과 부정확 사용 가능한 도구의 부족과 도구에의 과도한 의존 환경의 변화 단순 자료처리보다 DB자료를 이용해 고부가가치의 정보를 창출할 필요성 증대. {SCM(Supply chain management, CRM(Customer relationship management, APS (Advanced planning and scheduling), BI (Business Intelligence, …} ERP(Enterprise resource planning) 등의 도입 확대에 따른 자료의 정확성과 즉시성 확보 컴퓨터 발전에 따른 계산능력의 향상 인터넷의 도입에 따른 경영의 통합화 (내부, 외부) 로 신속하고 정확한 의사결정 필요 OR-1 2007

현황과 미래 기업 시스템의 통합관리 신속하고 정확한 의사 결정 필요 (수작업의 한계) computer의 발전 computing 환경의 일반화 정보의 공유 (ERP) 최적화 요구 증가 최적화 가능성 제고 최적화 기법의 적용 증가 OR-1 2007