Operations Research - Study Notes
Chapter Summary
Operations Research (O.R.) is an analytical method of problem solving and decision making used in management. This unit covers the transportation problem, the assignment problem and decision theory.
10.1 Transportation Problem
- Formulated by Frank Lauren Hitchcock (1875-1957) in 1941.
- There are m origins with supplies ai and n destinations with demands bj. The unit cost from origin i to destination j is cij and the quantity shipped is xij.
- Objective: minimise Z = sum of cij xij over all routes, subject to row sums = ai (supply constraints), column sums = bj (demand constraints) and xij ≥ 0.
- Balanced: total supply = total demand. Otherwise unbalanced. An initial basic feasible solution is found only for a balanced problem.
Definitions
| Term | Meaning |
|---|---|
| Feasible solution | Non-negative values xij satisfying all constraints |
| Basic feasible solution | A feasible solution with not more than m + n - 1 allocations |
| Optimal solution | A feasible solution (not necessarily basic) that minimises total cost |
| Non-degenerate BFS | Exactly m + n - 1 allocations in independent positions |
| Degenerate BFS | Fewer than m + n - 1 allocations |
Methods for an initial basic feasible solution
- North-West Corner rule (NWC): start at the top left cell, allocate x11 = min(a1, b1). If the demand is exhausted move right; if the supply is exhausted move down; if both, move diagonally. Repeat until all allocations are made.
- Least Cost Method (LCM): pick the cell with the least cost, allocate the maximum feasible quantity, eliminate the exhausted row or column and repeat. If the least cost is not unique, the choice is arbitrary. It starts with a lower beginning cost than NWC.
- Vogel's Approximation Method (VAM): find the penalty (difference between the least and the next higher cost) of each row and column, select the line with the largest penalty, allocate to its least cost cell, eliminate and repeat. VAM gives a solution very close to the optimum.
10.2 Assignment Problem
- Assign n jobs to n machines, one job per machine, at minimum total cost. Devised by Kuhn and Flood (1956); named the Hungarian method after theorems of Koneig (1950) and Egervary (1953).
- A special case of the transportation problem: numbers of sources and destinations are equal and every supply and demand is 1. xij = 1 if job i goes to machine j, otherwise 0.
- Balanced when rows = columns. If not, add a dummy row or column with all entries zero.
Hungarian method
- Subtract the least element of each row from every element of that row.
- Subtract the least element of each column from every element of that column.
- Examine rows with exactly one zero, mark it as an assignment and cross other zeros in its column; then do the same for columns.
- If each row and each column has exactly one assignment, the solution is optimal.
Adding or subtracting a constant from all elements of a row or column does not change the optimum schedule. If all Cij > 0, a schedule with total of Cij xij = 0 is optimal.
10.3 Decision Theory
- Decision maker: the person or group responsible for choosing a course of action.
- Acts: the alternative courses of action; together they form the action space.
- Events (states of nature): occurrences outside the decision maker's control.
- Pay-off: the monetary gain or loss of each act-event combination. With k alternatives and n states there are k × n pay-offs in the pay-off matrix.
- Certainty: only one state of nature exists. Uncertainty: only pay-offs are known; nothing is known about the likelihood of each state.
- Maximin: find the lowest pay-off of each alternative and choose the maximum of these (pessimistic criterion).
- Minimax: find the highest pay-off of each alternative and choose the minimum of these.
More for this chapter
Book Back Questions13 textbook MCQs · solved
Additional MCQs21 extra MCQs · solved
Practice TestInteractive · instant score
Book Back TestTest yourself on the textbook set
Additional MCQ TestTest yourself on the extra set
Formula SheetAll key formulas