Operations Research Lecture Notes Flashcards

TERMINOLOGY AND DEFINITION OF OPERATIONS RESEARCH

• Terminology Variation: The field is referred to as "operational research" in Britain and Europe, whereas Americans use the term "operations research". Both are commonly shortened to OR.
• Additional Terms: The field is also known as Management Science (MS). In the USA, these are often combined into OR/MS or ORMS. Other related terms include Industrial Engineering (IE), Decision Science (DS), and Problem Solving. In recent years, "OR" has become the standard global term.
• Definition: Operations Research (Management Science) is a scientific approach to decision-making that seeks to best design and operate a system, usually under conditions requiring the allocation of scarce resources.
• Definition of a System: A system is an organization of interdependent components that work together to accomplish the goal of the system.

THE SEVEN-STEP METHODOLOGY OF OR

1. Step 1: Formulate the Problem: The OR analyst defines the organization's problem, including specific objectives and the parts of the system that must be studied.
2. Step 2: Observe the System: The analyst collects data to estimate parameter values affecting the problem. These estimates are necessary for model development and evaluation.
3. Step 3: Formulate a Mathematical Model: The analyst develops an idealized mathematical representation of the problem.
4. Step 4: Verify the Model and Use for Prediction: The analyst determines if the model accurately represents reality and checks its validity for the current situation.
5. Step 5: Select a Suitable Alternative: Given a set of alternatives and restrictions/constraints, the analyst chooses the option that best meets the objectives. If a perfect alternative is too costly or impossible to find, the best available is chosen.
6. Step 6: Present Results and Conclusions: Recommendations are presented to decision-makers. If the recommendations are rejected due to incorrect definitions or lack of involvement, the analyst returns to Steps 1, 2, or 3.
7. Step 7: Implement and Evaluate Recommendation: After acceptance, the analyst aids in implementation. The system must be monitored and updated dynamically as environments change.

HISTORY OF OPERATIONS RESEARCH

• Origins: OR began systematically in the UK in the late 1930s.
• Early Military Context:
  • 1936: The British Air Ministry established Bawdsey Research Station near Felixstowe, Suffolk, for pre-war radar experiments.
  • 1936: RAF Fighter Command was created; it lacked effective aircraft and used elementary control systems initially.
  • Biggin Hill Experiments: Tests were conducted to integrate radar data with ground-based observer data for fighter interception.
  • 1937-1938 Exercises: Early air-defense exercises showed that radar was technically feasible but operational achievements were poor due to conflicting information from multiple stations.
• Coining the Term: A.P. Rowe, Superintendent of Bawdsey Research Station, proposed research into "operational" rather than just "technical" aspects. The term "operational research" (research into military operations) was coined.
• Strategic Impact: In May 1940, OR analysts used graphs to show Winston Churchill that sending ten more fighter squadrons to France would deplete RAF strength too rapidly. The squadrons were saved for the Battle of Britain.
• Scientific Minds: Early workers included physicists, physiologists, and surveyors. Four wartime OR personnel eventually won Nobel prizes in their peacetime fields.
• Post-WWII Growth: OR spread to the US and UK in different ways. The expansion over the last 30 years is largely attributed to the increasing power and availability of computers for complex numeric calculations.

BASIC OR CONCEPTS AND MODELING

• Mathematical Model Components:
  • Decision Variables: The unknowns to be determined by the solution.
  • Constraints: Physical limitations of the system.
  • Objective Function: The mathematical expression sought to be optimized.
• Feasibility and Optimality:
  • Feasible Solution: Satisfies all constraints.
  • Optimal Solution: A feasible solution that yields the best objective function value.
• Two Mines Example Case Study:
  • Mines: Mine X (Cost: $\pounds 180,000/day$) and Mine Y (Cost: $\pounds 160,000/day$).
  • Production (tons/day):
    • Mine X: High (6), Medium (3), Low (4)
    • Mine Y: High (1), Medium (1), Low (6)
  • Contract Requirements: High (12 tons), Medium (8 tons), Low (24 tons) per week.
  • Formulation:
    • Variables: $x$ (days per week Mine X), $y$ (days per week Mine Y).
    • Objective: Minimize $z = 180x + 160y$
    • Constraints:
      • $6x + y \ge 12$
      • $3x + y \ge 8$
      • $4x + 6y \ge 24$
      • $x \le 5, y \le 5, x, y \ge 0$
  • General Modeling Rules: Choose inequalities over equalities to allow more flexibility in optimization. Over-constrained systems (like replacing $\ge$ with $=$ in the Two Mines example) often have no solution.

LINEAR PROGRAMMING (LP) ASSUMPTIONS

1. Proportionality: The contribution of each variable to the objective and LHS of constraints is proportional to its value. Production of 4 units costs exactly 4 times the production of 1 unit.
2. Additivity: The contribution of any variable is independent of others. The total objective value is the sum of individual contributions.
3. Divisibility: Variables are allowed to assume fractional values (e.g., $1.69$ boats).
4. Certainty: Each parameter is known with absolute certainty.

LINEAR PROGRAMMING FORMULATION EXAMPLES

• Giapetto Wood Carving:
  • Objective: Maximize profit $z = 3x_1 + 2x_2$
  • Constraints: Finishing ($2x_1 + x_2 \le 100$), Carpentry ($x_1 + x_2 \le 80$), Demand for soldiers ($x_1 \le 40$).
  • Result: $x_1=20, x_2=60, z=180$.
• Advertisement Example:
  • Objective: Minimize cost $z = 50x_1 + 100x_2$
  • Constraints: High-income women ($7x_1 + 2x_2 \ge 28$), High-income men ($2x_1 + 12x_2 \ge 24$).
  • Result: $x_1=3.6, x_2=1.4, z=320$.
• Diet Example:
  • Minimize total cents $w = 50x_1 + 20x_2 + 30x_3 + 80x_4$
  • Constraints for calories, chocolate, sugar, and fat based on intake requirements.
• Sailco Multi-period Inventory:
  • Links inventory across periods: $i_t = i_{t-1} + x_t + y_t - d_t$. Minimizes regular time ($x_t$), overtime ($y_t$), and holding costs.

THE SIMPLEX ALGORITHM

• Concept: Moves between adjacent vertices of the feasible region to improve the objective function until optimality.
• Standard Form: All constraints are equations (using slack or excess variables), and all variables are non-negative.
• Steps:
  1. Convert to standard form.
  2. Identify starting Basic Feasible Solution (BFS).
  3. Perform ratio test to find leaving variable: $\min \left( \frac{\text{RHS}}{\text{Coefficient of entering variable}} \right)$ for positive coefficients.
  4. Pivot using Elementary Row Operations (EROs) to update basis.
• Unbounded LP: Occurs if the ratio test fails because no positive coefficients exist in the pivot column.
• Alternative Optimal Solutions: Occur if a non-basic variable has a coefficient of 0 in the optimal Row 0.

THE BIG M METHOD FOR ARTIFICIAL VARIABLES

• Usage: For constraints of type $\ge$ or $=$, where a starting BFS is not obvious.
• Steps:
  1. Add an artificial variable $a_i$ to $\ge$ (which also have excess variables $e_i$) and $=$ constraints.
  2. For a minimization problem, add $Ma_i$ to the objective function (where $M$ is a very large positive number). For maximization, add $-Ma_i$.
  3. Eliminate $a_i$ from Row 0 using EROs before starting simplex.
• Interpretation: If any $a_i > 0$ in the optimal solution, the original problem is infeasible.

DUALITY IN LINEAR PROGRAMMING

• Primal-Dual Relationships: Every Max problem has an associated Min problem.
  • Primal Max ($\le$) $\rightarrow$ Dual Min ($\ge$).
  • Primal objective coefficients $\rightarrow$ Dual RHS.
  • Primal RHS $\rightarrow$ Dual objective coefficients.
• Non-normal Transitions:
  • If primal constraint $i$ is $\ge$, dual variable $y_i \le 0$.
  • If primal constraint $i$ is $=$, dual variable $y_i$ is unrestricted in sign (urs).
  • If primal variable $x_j$ is urs, dual constraint $j$ is an equality.
• Dual Theorem: The optimal objective values of the primal and dual are equal ($z = w$).
• Weak Duality: For any feasible solution, Max Primals are always $\le$ Min Duals ($z \le w$).
• Economic Interpretation: Dual variables represent the Shadow Price of resources.

SENSITIVITY ANALYSIS

• Reduced Cost: The amount by which a non-basic variable's objective coefficient must improve before it can become a basic variable.
• Shadow Price: The improvement in the optimal objective value ($z$) if the RHS of a constraint increases by 1 unit.
  • Max problems: $z_{\text{new}} = z_{\text{old}} + (\Delta \text{RHS} \times \text{Shadow Price})$.
  • Min problems: $z_{\text{new}} = z_{\text{old}} - (\Delta \text{RHS} \times \text{Shadow Price})$.
• 100% Rule for Objective Coefficients: If changes occur to variables with zero reduced costs, calculate $r_j = \frac{\Delta c_j}{\text{Allowable Increase/Decrease}}$. If $\sum r_j \le 1$, the current basis remains optimal.
• 100% Rule for RHS: Similarly, calculate $r_i = \frac{\Delta b_i}{\text{Allowable Increase/Decrease}}$. If $\sum r_i \le 1$, current basis remains optimal, though variable values may change.

TRANSPORTATION PROBLEMS

• Definition: Shipping goods from $m$ supply points ($s_i$) to $n$ demand points ($d_j$) at minimum cost ($c_{ij}$).
• Balanced Problem: $\sum s_i = \sum d_j$. If unbalanced, add dummy points with zero cost.
• Initial BFS Methods:
  • Northwest Corner (NWC): Assigns values starting from the top-left cell.
  • Minimum Cost Method: Assigns values to the cell with the lowest unit cost.
  • Vogel's Method: Uses "penalties" (difference between two smallest row/column costs) to prioritize assignments.
• Transportation Simplex: Uses multipliers $u_i$ and $v_j$ such that $u_1=0$ and $u_i + v_j = c_{ij}$ for basic variables. Optimality is reached when $u_i + v_j - c_{ij} \le 0$ for all non-basic cells.
• Loops: A closed path of at least four cells used to pivot in transportation problems.
• Transshipment: Conversion involves supply/demand points and transshipment points. Transshipment point supply/demand becomes $\text{Original} + S$ (where $S = \text{total supply}$).
• Assignment Problem: Specialized transportation where $s_i = 1$ and $d_j = 1$. Solved using the Hungarian Method.

INTEGER PROGRAMMING (IP) FORMULATION

• Types: Pure IP (all integers), Mixed IP (some integers), Binary IP (0-1 variables).
• Fixed Charge Logic: To model a fixed cost for an activity $x$, introduce binary variable $y$ and constraint $x \le My$.
• Either-Or Constraints: To ensure either $f(x) \le 0$ or $g(x) \le 0$ is met:
  • $f(x) \le My$
  • $g(x) \le M(1-y)$
• If-Then Constraints: To model "If $f(x) > 0$ then $g(x) \ge 0$":
  • $-g(x) \le My$
  • $f(x) \le M(1-y)$
• Traveling Salesperson Problem (TSP): Finds the cheapest tour visiting $N$ cities exactly once.
  • Subtour elimination: $u_i - u_j + Nx_{ij} \le N - 1$ for $i, j > 1$.

SOLVING INTEGER PROGRAMS

• LP Relaxation (LR): Solving the IP as a standard LP by dropping integrality constraints. The optimal LR value provides a bound ($z_{\text{LR}} \ge z_{\text{IP}}$ for max, $z_{LR} \le z_{IP}$ for min).
• Branch-and-Bound (B&B):
  • Divides the problem into sub-problems by branching on fractional variables (e.g., $x_i \le 3$ and $x_i \ge 4$ if $x_i = 3.75$).
  • Fathoming: A node is inactive if it is infeasible, yields an integer solution, or has a worse optimal value than the current Lower Bound (LB).
• Knapsack Inspection: For $\max \sum c_ix_i$ s.t. $\sum a_ix_i \le b$, compute ratios $r_i = c_i / a_i$. Fill the knapsack starting with the highest ratio.
• Heuristics for TSP:
  • Nearest-Neighbor: Visit the closest unvisited city.
  • Cheapest-Insertion: Add cities to a subtour where they increase total length the least.
• Gomory Cutting Planes: Strengthens LR by adding constraints that cut off fractional solutions.
  • A cut is generated as: $\text{Fractional parts of LHS} \ge \text{Fractional part of RHS}$.
  • Specifically: $\text{RHS fractional part} - \sum (\text{coeff fractional parts}) \times \text{variable} \le 0$.