본문 바로가기
OR(1) Mathematical Model

  OR(1) -Mathematical Model


▶강의개요

  • 교과목명 : 경영과학(1)
  • 교과구분 : 전공필수
  • 학점/시간 : 3학점/3시간
  • 교재 : 경영과학(1)-수리계획모형 (강진규, 한밭대학교 출판부)
  • 참고도서 :  현대경영과학(김세헌, 무역경영사), Operations Research(Taha, McMillan)

▶강의내용, 방법, 평가기준

  • 강의목표 및 내용

    - 시스템적 접근방법(Systems approach), 최적화(optimization), trade-off의 개념을 익힌다.

    - 수리모형의 개념을 익히고, 현실속에서 간단한 수리모형을 수립할수 있는 능력을 기른다.

    - 대표적인 최적화 프로그램인 LINDO와 관련 On-line 프로그램의 사용법을 익힌다.

    - 팀워크를 이용하여 문제를 해결하는 방법과 태도를 익힌다.

  • 강의방법
    -
    출석수업을 원칙으로 하고, 경우에 따라 인터넷 수업으로 대신하거나 보완함
    - 매 단원 시작 또는 종료시 퀴즈(MVS 선발전)나 수시평가를 실시함
    조별 발표 및 토론 수업을 전반기와 후반기에 각각 한차례씩 실시함
    - 필요에 따라 홈페이지를 통하여 수업 내용이나 시사 관련의 주요 주제에 대하여 토론을 실시함
  • 성적평가기준
    - 출석 : 10%
    - 과제물 및 발표 : 10%
    - 퀴즈(MVS) 및 수시평가 : 20%
    - 중간고사 : 25%
    - 기말고사 : 25%
    - 수업참여도(질문, 대답, 사이버 학습, 게시판 활동 등) : 10%

▶강의일정

  • 1주 : 강의내용, 방법, 일정 소개, 홈페이지 이용법
  • 2주 : 경영과학의 기초
  • 3주 : 선형계획법 - 기본개념과 모형화, 과제물(1)
  • 4-5주 : 심플렉스법과 해의 분석(Lindo/Lingo 실습), 수시평가(1)
  • 6주 : 쌍대이론과 민감도 분석(On-line 프로그램 실습), 과제물(2)
  • 7주 : 선형계획법 적용사례 - 발표 및 토론 수업
  • 8주 : 중간고사
  • 9주-10주 : 수송모형과 할당모형, 과제물(3)
  • 11주 : 정수계획법, 수시평가(2)
  • 12주 : 목표계획법, 과제물(4)
  • 13주 : 네트워크 모형 - 발표 및 토론 수업
  • 14주: 동적계획법, 비선형계획법
  • 15주 : 기말고사

강의내용 요약

1. 선형계획법(LP)

  선형계획법은 수리계획법중 가장 기본적이고 널리 이용되는 기법으로 기업 등의 조직에서 최적의사결정이 필요한 경우 기본적으로 고려되는 분석도구이다. LP모형은 의사결정상황을 1차식의 함수로 표시한 것으로서 몇가지 가정을 필요로 하는데 일단 모형화가 이루어지면 심플렉스법에 의해 쉽게 해를 구할 수 있다.

  그러나 LP모형의 가정은 현실에 부합되지 않는 정적인 측면이 있기 때문에, 이를 보완하기 위한 방법이 필요하다. 즉, 초기의 조건이 달라짐에  따라 이미 구한 해가 어떻게 달라지는지를 검토해야 하는데 이를 민감도 분석이라 하며, 이에 기초가 되는 이론이 쌍대이론이다.  LP에서 다루는 주요 내용은

  • 선형계획법의 모형화와 한계
  • 심플렉스법과 해의 분석
  • 쌍대이론민감도분석
  • 선형계획법 적용사례

등이다. 

 

2. 수송모형과 할당모형

  수송모형(transportation model)과 할당모형(assignment model)은 선형계획모형 중 특수한 경우로서, 그 형태상 네트워크 모형(network model)의 일종이라고도 할 수 있다.

  수송모형은 제품이나 원료를 공급하는 몇 개의 공급지와 그것들을 필요로 하는 몇 개의 수요지 사이에 설정되어 있는 각 수송경로에 대해, 수송해야 할 최적의 양을 결정하는 문제를 말한다. 수송모형의 특수한 형태로서 공급지와 수요지 사이에 중간 경유지를 고려하는 중개수송모형(transshipment model)과 일명 짝짓기 문제라 하는 할당모형이 있다.

  여기서는 각 모형의 특성과 해법, 그리고 실제상황의 적용례 등을 중점적으로 공부한다.

 

3. 정수계획법(IP)

  선형계획법은 의사결정변수의 값이 정수가 아니더라도 실행가능하다고 가정하였으나 현실은 그렇지 않은 경우가 있다. 즉, 의사결정변수가 사람이나 기계 등의 수를 나타낸다면, 해가 소수가 나와서는 그대로 실행에 옮길 수 없다. 이렇게 의사결정변수가 정수의 값만을 갖도록 하는 조건이 추가된 수리계획법 문제를 정수계획법(IP ; Integer Programming)이라고 한다.

  정수계획모형에도 의사결정변수의 특성에 따라 일부만 정수 값을 요구하는 경우도 있는데, 이를 혼합정수계획모형(mixed IP model)이라 하며, 모든 변수가 정수이어야 하는 경우를 순수정수계획모형(pure IP model)이라 한다. 또한 특수한 경우로서 모든 변수가 0 또는 1의 값을 갖는 모형을 0-1 정수계획모형(0-1 IP model)이라고 한다.

  이 단원에서는 몇가지 사례에 대하여 정수계획법으로 모형화하는 방법과 정수계획법의 대표적인 해법인 분단탐색법에 대하여 주로 공부한다.

 

4. 목표계획법(GP)

  기업이나 기타 조직사회의 경영 목표는 반드시 이익 또는 비용의 최대화나 최소화만 추구하지 않는 경우도 있다. 예를 들어 이익의 최대화 뿐만 아니라 시장점유율의 유지, 위험률의 최소화, 가동시간 유지 등 금액으로 직접 환산하기 곤란하며 서로 상충되기도 하는 목표들이 동시에 존재할 수 있다. 이와 같이 이익 최대화나 비용 최소화라는 단 하나의 목표 이외에 서로 상충되는 여러개의 목표가 있는 경우에 최적 의사결정을 하기 위한 접근방법이 목표계획법(GP ; goal programming)이다. 목표계획법에서는 LP와는 달리 정해진 목표에 대하여 편차변수와 목표제약조건이 도입되며 목적함수는 항상 편차 합의 최소화로 표현된다.

  이 단원에서는 목표계획법의 모형화 과정과 목표계획법의 해법으로서 도해법수정심플렉스법에 대하여 공부한다.

 

5. 네트워크 모형

  네트워크(network, 망)모형은 실제 사회에서 흔히 볼 수 있는 것으로서, 예를 들면 통신망, 전화망, 도로망, 수송망, 항공망 등이 있으며, 전자제품에 사용되는 부품들의 회로망도 네트워크의 전형적인 예라 할 수 있다. 수송모형과 프로젝트의 일정관리에 이용되는 PERT/CPM도 네트워크 모형의 일종이다.

  여기서는 다음과 같은 3가지의 대표적인 네트워크 문제에 대한 특성 및 해법에 대하여 알아본다.

  • 최단경로문제(shortest route problem) : 두 지점 사이의 최단경로, 즉, 가장 작은 비용 또는 가장 짧은 거리나 시간에 도착할 수 있는 경로를 찾는 문제로서, 여러 방문지를 들러야 하는 외판원의 경로선택문제 등이 이에 속한다.  
  • 최소걸침나무문제(minimum spanning tree problem) :네트워크상의 모든 마디를 연결하는 방법 중에서 가장 작은 비용 또는 시간으로 연결할 수 있는 방법을 찾는 문제로서, 공장내의 설비배치문제, 컴퓨터 네트워크 설계문제 등이 그 예이다.
  • 최대흐름문제(maximal flow problem) : 네트워크상의 한 지점에서 다른 지점으로 보낼 수 있는 최대의 유통량을 찾는 문제로서, 교통흐름 분석문제나 송유관 설계문제 등을 들 수 있다.

 

6. 동적계획법(DP)

  동적계획법(dynamic programming; DP)은 의사결정상황을 시간적 공간적으로 여러 단계로 나누어 취급하며, 따라서 해를 구하는 과정도 의사결정변수를 한꺼번에 결정하는 것이 아니라 각 단계마다 대상이 되는 결정변수의 값만 고려한다. 이와 같은 '단계적 결정'이라는 특성 때문에 동적계획법을 간혹 다단계계획법(multistage programming)이라 부르기도 한다.

  동적계획법은 현실문제를 고정된 상황으로 파악하지 않고 여러 단계로 변화하는 상황을 고려하기 때문에 모형의 개념상 선형계획법보다 우위에 있다고 할 수 있으나 선형계획법과 같이 잘 개발된 해법이 존재하지 않기 때문에 문제의 특성에 따라 서로 다른 해법이 필요하다.

  따라서 동적계획법에서는 여러 형태의 문제를 파악하는 것이 중요한데, 이 장에서는 대표적인 유형의 동적계획모형과 이들의 해법에 공통적으로 적용되는 최적성의 원리(principle of optimality)와 순환식(recursive equation)에 대하여 중점적으로 공부한다.

 

7. 비선형계획법(NLP)

  수리계획법은 현실의 의사결정상황을 수식으로 모형화하여 이를 해결함으로써 최적의사결정을 추구하는 것이다. 그런데 현실의 상황을 수식화하면 많은 경우는 1차식이 아닌 함수, 즉, 비선형함수로 나타나는데 이러한 경우에 최적해를 찾고자 하는 것이 비선형계획법(NLP ; non-linear programming)이다.

  비선형계획법은 모형의 함수가 매우 다양하게 나타나기 때문에 선형계획법의 심플렉스법과 같은 효율적인 해법이 존재하지 않는다. 여기서는 비선형계획모형의 최적해가 가지는 성질의 파악에 초점을 맞추어, 여러 상황에 대해 최적해의 필요조건과 충분조건에 대해 공부한다