OR

大二运筹学，包含图解法、Simple Method、Transportation、Assignment、Shortest path/ minimum spanning tree等等。

OR

• 图解法
  • L-P Graphical Method-1
    • A Variation
      • No feasible solution
    • Another Variation
      • An infinite number of optimal solutions
  • L-P Graohical Method-2
• Simple Method
  • with M
    • Equality Constraints
    • Constraints in “greater-than” sign
    • Negative RHS
      • x1 −x2 ≤−1 → −x1 +x2 ≥1
    • Minimization problems
      • minZ =x1 +x2 → max−Z =−x1 −x2
    • Variables allowed to be negative
      • Bounded negative values:
        • x1 ≥ −10 → x1 + 10 ≥ 0; x′1=x1+10 & x′1≥0
      • Unbounded negative values:
        • x1 is unrestricted-in-sign; x +1 , x −1 : x 1 = x +1 − x −1 & x +1 , x −1 ≥ 0
  • without M
    • More than one optimal solutions
    • Standard form
      • maximize Z
      • constraints in ≤ form
      • nonnegativity of all the DVs
      • nonnegativity of all the RHS coefficients
• Transportation
  • 3 rules for initial solution adjustment test no, adjustment
  • Northewst corner rule:
  • Minimum cost rule:
  • Vogel’s method
    • determine the difference for each row and column: the difference between the smallest cost and next-to-the-smallest cost
    • find the row or column with the largest difference, and then fill the cell with the smallest cost
    • recalculate the difference
  • 概要
• Assignment
  • 标注
    • There are n tasks need to be assigned to exactly n workers (machines)
    • Each task is assigned to exactly 1 worker
    • Each worker performs exactly 1 task
    • There is a cost cij associated with worker i performing task j
    • The objective is to determine how all n assignments should be made to minimize the total cost
  • Example 1 (n = 2)
  • Example 2 (n = 3)
  • Example 3 (n = 4)
  • Example 4 (n = 5)
    • • • Could not find a best solution!
  • Example 5 (n = 4)
  • 概要
• Shortest path/ minimum spanning tree
  • n-1
  • 手动求解，带过程
  • Shortest path
    • Mathematical model
    • Dijkstra’s Algorithm
      • Directed Network
    • Undirected Network
  • Minimum Spanning Tree
    • Select any node arbitrarily, and then connect it (i.e., add a link) to the nearest distinct node
    • Identify the unconnected node that is closest to a connected node, and then connect these two nodes (i.e., add a link between them). Repeat this step until all nodes have been connected.
• Maximum flow/Minimum cost flow
  • 建模
  • Maximum Flow Problem
  • Minimum Cost Flow Problem
• Integer Progrmming
  • 建模
  • integer programming (IP) problem
  • mixed integer programming (MIP)
  • Binary integer programming (BIP)
  • 概要