Operations Research I (2017)

lazy5f edited this page Jan 3, 2018 · 36 revisions

This course introduces the basic mathematical programming models. It includes basic concept of optimizations, feasibility, boundness, convexity and optimality. It covers linear programming models, simplex methods, duality, transportation problem and assignment problem. This course leads students to the understanding of more complex problems and solution methods as well.

시험 성적(PLMS에 게시)

  • 중간고사
    • 100점 만점으로 환산된 점수입니다. 실제 점수는 피드백에 적어두었습니다.
    • 중간고사 확인 후 바뀐 점수로 수정되었습니다. 확인바라겠습니다.
    • 총점: 235점 -- 평균: 126.8, 중앙값: 131.8, 표준편차: 40.9, 최소: 3, 최대: 199
  • 기말고사
    • 총점: 94점 -- 평균: 40.6, 중앙값: 44, 표준편차: 17.4, 최소: 1, 최대: 67

Course Objectives

  • Students should be able to solve the real world problems by linear programming
  • Students should be able to obtain necessary data and use the appropriate tools for the optimization
  • Students should be able to model and formulate the linear programming problems
  • Students should be able to define the variables and build the mathematical models

Requirements & Grading

  • Attendance (10%), Homework Assignment (20%), Midterm Exam (30%), Final Exam (40%)

Textbooks

  • Taha, Operations Research: An Introduction, 10th Ed., Pearson, 2017
  • Taha (최인찬, 문일경, 류춘호, 김재희 옮김), 경영과학, 9판, 교보문고, 2012 (번역서)

Schedule (Tentative)

  1. What Is Operations Research?
  2. Modeling with Linear Programming
  3. The Simplex Method and Sensitivity Analysis
    1. Transition from graphical to algebraic solution
    2. Simplex method
    3. Sensitivity analysis
  4. Duality and Post-Optimal Analysis
    1. Definition of dual problem and primal-dual relationships
    2. Interpretation of duality, addition simplex algorithms, and post-optimal analysis
  5. Transportation Model and Its Variants
  6. Network Models
    1. Minimum spanning tree algorithm and shortest-path algorithm (Floyd's algorithm)
    2. Maximal flow model and CPM & PERT
  7. Advanced Linear Programming
    1. Revised simplex method and duality
    2. Bounded-variable algorithm and Parametric linear programming
  8. Goal Programming
  9. Integer Linear Programming
    1. Integer programming algorithms
  10. What Is Operations Research, Again?

Assignments

  • Textbook problem은 모두 10판을 기준으로 합니다. 예를 들어 2-17과 2-18의 경우 9판과 10판의 문제가 다릅니다. 9판으로 공부하는 학생들은 10판을 빌려보고 확인해주세요.
  1. Textbook problem 1-1, 1-5.

    • 채점 안 함, 보고서 제출 필요 없음, 풀어보고 수업시간에 같이 살펴볼 계획임
  2. (9/19 수업시간까지) Textbook problem 2-17, 2-19.

    • 보고서 제출(워드 프로세싱 안하고 손으로 써서 내는 것이 더 도움이 될 것으로 생각됨)
  3. (9/26 수업시간 전까지) Excel solver와 ampl 연습: Textbook problem 2-19 (PLMS 제출)

    • Excel solver
      • P2-19.xlsx 파일 제출
      • Decision variable은 녹색으로, objective value는 노란색으로 셀 색깔을 칠할 것
      • "해 찾기"를 실행해서 제대로 푸는 경우 점수를 받을 수 있음
    • ampl
      • P2-19.txt 파일 제출
      • 모델을 로드했을 때 해가 제대로 출력되어야 점수를 받을 수 있음
    • 참고: 수업시간에 이야기했듯이 결과가 정수가 아닙니다. 정수 결과를 얻기 위해서는 선형계획(linear programming)이 아니라 정수계획(integer programming)을 사용해야 합니다. 정수해(integer solution)를 얻는 것이 별 것 아닌 것 같이 보이지만, 사실 상당히 어려운 문제입니다. 그 내용은 이번 강의 후반부(교재의 9장)에서 다룰 예정입니다. 어쨌든 이 숙제에 대한 답은 정수가 아닌 것이 맞습니다(선형계획을 작성하는 것이므로).
  4. (10/10 수업시간까지) 아래 LP를 Simplex method로 풀이하시오.

    • 보고서 제출(워드 프로세싱 안하고 손으로 써서 내도 괜찮습니다.)
      • 풀이 과정에 필요한 Simplex tableau를 모두 적어주세요.
    1. 기본
      max. 60 x1 +  30 x2 +  20 x3
      s.t.  8 x1 +   6 x2 +     x3 <= 48
            4 x1 +   2 x2 + 1.5 x3 <= 20
            2 x1 + 1.5 x2 + 0.5 x3 <= 8
                       x2          <= 5
                        x1, x2, x3 >= 0
      
    2. M-method 사용
      max.   2 x1 +   3 x2
      s.t. 1/2 x1 + 1/4 x2 <= 4
               x1 +   3 x2 >= 20
               x1 +     x2 == 10
                    x1, x2 >= 0
      
    3. Two-phase method 사용
      max. 12 x1 + 15 x2
      s.t.  4 x1 +  3 x2 == 12
            2 x1 +  5 x2 >= 10
                  x1, x2 >= 0
      
  5. (11/7 수업시간까지) Textbook problem 3-65, 3-70, 3-79

    • 보고서 제출(워드 프로세싱 안하고 손으로 써서 내도 괜찮습니다.)
  6. (11/23 수업시간까지) Textbook problem 4-9, 4-10, 4-18, 4-21, 4-24

    • 보고서 제출(워드 프로세싱 안하고 손으로 써서 내도 괜찮습니다.)
  7. (11/28 수업시간까지) Textbook problem 4-29, 4-34, 4-35, 4-36, 4-54

    • 보고서 제출(워드 프로세싱 안하고 손으로 써서 내도 괜찮습니다.)
    • Problem 4-29: Solver (Excel, AMPL 등)를 사용해서 dual price를 구하세요. 참고로, 해답이 교재에 나와 있지만 이 문제를 숙제로 하는 이유는 solver를 사용하여 분석하는 경험을 해보기 위해서입니다.
    • Problem 4-36: Equality constraint는 두 개의 inequality constraint로 바꾸면 됩니다.
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.