Linear Programming

Linear Programming

A mathematical technique used to determine the optimal outcome in a system modeled with linear relationships involving decision variables, constraints, and an objective function.

Objective Function

A linear formula representing the goal of the model, either to maximize or minimize a particular value, such as profit or cost.

Decision Variable

A symbolic representation of controllable elements whose values are determined in the optimization process to achieve the objective.

Constraints

Linear conditions that restrict the possible values of decision variables, often due to limited resources or required specifications.

Parameters

Fixed numerical values that define the coefficients in the objective function and constraints, representing resources or contributions.

Model Formulation

The structured process of converting a real-world problem into a linear programming model composed of decision variables, an objective function, and constraints.

Feasible Solution

A set of values for decision variables that satisfies all constraints in the model.

Infeasible Solution

A set of values for decision variables that violates one or more constraints.

Optimal Solution

The feasible solution that results in the most favorable value of the objective function, whether maximum or minimum.

Nonnegativity Constraint

A condition requiring decision variables to be zero or greater, reflecting realistic conditions such as nonnegative production levels.

Maximization Model

A linear programming model in which the objective function is designed to achieve the highest possible value, such as maximum profit.

Minimization Model

A model aimed at achieving the lowest possible value of the objective function, typically minimizing costs or losses.

Slack Variable

A variable added to a ≤ constraint to convert it into an equation, representing unused resources.

Surplus Variable

A variable subtracted from a ≥ constraint to transform it into an equation, representing excess above the requirement.

Standard Form

A version of a linear programming model where all constraints are equations and decision variables are nonnegative.

Graphical Solution

A visual method used to solve linear programming problems with two decision variables by plotting constraints and identifying the feasible region and optimal solution.

Feasible Region

The area on a graph where all constraints overlap, representing all combinations of decision variables that satisfy the constraints.

Extreme Point

A corner point of the feasible region where the optimal solution is often found in a graphical method.

Product Mix Problem

A common type of linear programming application where a firm determines the optimal combination of products to produce within resource limits to maximize profit.

Sensitivity Analysis

An evaluation of how changes in model parameters (such as resource availability or profit coefficients) affect the optimal solution.

Binding Constraint

A constraint that forms part of the optimal solution boundary and is fully utilized in the solution.

Nonbinding Constraint

A constraint that does not affect the optimal solution directly, as it is not fully used at the optimal point.

Shadow Price

The amount by which the objective function value would improve if there were one more unit of a binding resource.

Graphical Method Limitations

Constraints of the graphical method, which only works for problems with two decision variables and cannot handle higher dimensions.

Slope of Objective Function

The rate at which the objective function increases or decreases, used in graphical solutions to move the objective line to its optimal position.

Multiple Optimal Solutions

A condition where more than one point on the boundary of the feasible region yields the same optimal value.

Degeneracy

A condition where more than one optimal solution occurs at the same extreme point due to overlapping constraints.

Certainty Assumption

The presumption in linear programming that all coefficients in the model are known and fixed.

Additivity

A property where the total effect of all decision variables is the sum of their individual effects.

Proportionality

A linear programming assumption that the contribution of each decision variable is directly proportional to its level.

Divisibility

An assumption that decision variables can take on any fractional value, allowing continuous solutions.

Integer Linear Programming

A variation of linear programming where some or all decision variables are restricted to integer values.

Balanced Transportation Model

A transportation problem where total supply equals total demand, and all constraints are equalities.

Unbalanced Transportation Model

A model where supply does not equal demand, leading to inequality constraints.

Model Components

The essential parts of a linear programming model: decision variables, objective function, and constraints.

Model Summary

A concise representation of a linear programming model including variables, objective, and constraints.

Model Interpretation

The analysis of a model’s results to guide real-world decision-making and understand the implications of the solution.

QM for Windows

A software used for solving linear programming models through graphical and simplex methods.

Excel Solver

A Microsoft Excel add-in tool used to define and solve linear programming problems by specifying objective functions, variables, and constraints.

Dual Value

Also called shadow price, it indicates how much the objective function will change with a one-unit increase in a resource.

Ranging

A sensitivity analysis method used to determine the range of values over which an objective coefficient or right-hand side value can vary without changing the optimal solution.

Systematic Format

A structured approach to model formulation involving sequential steps: defining variables, formulating objective function, and setting constraints.

Modeling Example

A practical case used to illustrate linear programming concepts by applying them to a real or hypothetical scenario.

Constraint Line

A graphical representation of a constraint equation showing the boundary between feasible and infeasible areas.

Intersection Point

A point on the graph where two constraint lines meet, often representing a potential optimal solution.

Inactive Constraint

A constraint that does not limit the feasible solution space at the optimal point and thus does not impact the solution.

Binding Resource

A resource that is fully utilized at the optimal solution point, limiting the achievement of a better outcome.

Excess Capacity

The amount of a resource that is not fully used in the optimal solution, represented by slack variables.

Idle Resource

A resource that is available but not used in the solution due to optimality considerations.

Inequality Types in LP

The three types of inequalities used in linear programming: ≤ (less than or equal to), = (equal to), and ≥ (greater than or equal to).