Operations Research Lecture Notes Flashcards

Flashcards covering vocabulary, methodology, assumptions, and core algorithms of Operations Research, including Linear Programming, Duality, Transportation, Assignment, and Integer Programming.

Operations Research (OR)

A scientific approach to decision making that seeks to best design and operate a system, usually under conditions requiring the allocation of scarce resources.

System

An organization of interdependent components that work together to accomplish the goal of the system.

Mathematical Model

An idealized representation of a system consisting of decision variables, constraints and an objective function.

Decision Variables

The unknowns to be determined by the solution to a mathematical model.

Optimal Solution

A set of variable values that are feasible (satisfy all constraints) and lead to the best possible value (maximum or minimum) of the objective function.

Proportionality (LP Assumption)

The assumption that the contribution to the objective function and the row constraints from each decision variable is directly proportional to its value.

Additivity (LP Assumption)

The assumption that the contribution of a decision variable to the objective function and constraints is independent of the values of other decision variables.

Divisibility (LP Assumption)

The assumption that each decision variable is allowed to assume fractional or non-integer values.

Certainty (LP Assumption)

The assumption that each parameter in the linear programming model is known with complete certainty.

Feasible Region

The set of all points (values of decision variables) that satisfy all of a model's constraints and sign restrictions simultaneously.

Binding Constraint

An active or tight constraint where the left-hand side equals the right-hand side ($LHS = RHS$) when the optimal values of the decision variables are substituted.

Simplex Algorithm

An iterative procedure developed by Dantzig that moves from one vertex of the feasible region to an adjacent vertex to improve the objective function value until an optimal solution is reached.

Standard Form

A format of a linear program where all constraints are expressed as equations and all variables are required to be nonnegative.

Slack Variable

A variable added to a $\leq$ constraint to convert it into an equality.

Excess Variable

A variable subtracted from a $\geq$ constraint to convert it into an equality.

Artificial Variable

A variable added to $\geq$ or $=$ constraints in the Big M method to provide an initial basic feasible solution.

Big M Method

A version of the Simplex Algorithm used when a starting basis is not readily apparent, involving a very large positive number ($M$) in the objective function to penalize artificial variables.

Dual Problem

A related linear program associated with a primal problem that provides economic insights and sensitivity analysis.

Shadow Price

The amount by which the optimal $z$ value is improved if the right-hand side ($RHS$) of the $i^{th}$ constraint is increased by $1$, provided the current basis remains optimal.

Reduced Cost

For any nonbasic variable, the amount by which its objective function coefficient must be improved before the variable will become a basic variable in some optimal solution.

100% Rule

A guideline used to determine if the current basis remains optimal when multiple objective function coefficients or multiple right-hand side values change simultaneously.

Balanced Transportation Problem

A transportation model where the total supply points capacity equals the total demand points requirements.

Loop

In transportation problems, an ordered sequence of at least four different cells where consecutive cells share a row or column and no three consecutive cells share the same row or column.

Transshipment Point

A location in a logistics network that can both receive goods from other points and send goods to additional destinations.

Assignment Problem

A special class of transportation problem where each supply point must be assigned to exactly one demand point, typically with each supply and demand being exactly $1$.

Hungarian Method

An efficient algorithm for solving assignment problems by manipulating the cost matrix through row and column reductions.

Integer Program (IP)

A mathematical optimization model in which some or all of the decision variables are restricted to take only integer values.

LP Relaxation (LR)

The linear program obtained by omitting all integer or $0-1$ constraints from an Integer Programming model.

Knapsack Problem

A type of Integer Program with a single constraint representing a weight or size capacity and non-negative coefficients in the objective and constraints.

Branch-and-Bound Method

A tree-search approach that systematically enumerates feasible solutions by dividing the problem into smaller sub-problems to find the optimal integer solution.

Fathomed Node

A sub-problem in the Branch-and-Bound tree that is marked inactive because it is infeasible, yields an all-integer solution, or cannot yield an objective value better than the current Lower Bound.

Traveling Salesperson Problem (TSP)

A combinatorial problem seeking the cheapest round-trip route that visits a specific number of cities exactly once and returns to the starting point.

Gomory Cut

A valid inequality added as a constraint in a cutting-plane algorithm to eliminate fractional solutions from the LP relaxation without removing any integer feasible points.