COMM 225 — Production and Operations Management
CHAPTER 6S: LINEAR PROGRAMMING
Comprehensive Exam Preparation Notes
1. Introduction and Linear Programming Model
Linear programming (LP) is a powerful quantitative tool used to obtain optimal solutions to
problems that involve requirements or limitations for resources — such as available material,
budget, labour, and machine time. These problems are referred to as constrained optimization
problems. Linear programming has been applied successfully across a wide range of decisions,
including:
• Determining optimal blends of animal feed and gasoline ingredients.
• Developing optimal production schedules.
• Identifying the optimal mix of products to produce in a factory.
LP techniques consist of a sequence of steps that will lead to an optimal solution to linear-
constrained problems, if an optimum exists. There are special-purpose and general-purpose LP
techniques. This chapter covers the two general-purpose solution techniques: graphical linear
programming (visual, limited to two variables) and computer solutions (practical for large real-
world problems).
A linear programming model is a mathematical representation of a constrained optimization
problem. It has four components:
Component Description
Represent choices — amounts of inputs to use or outputs to produce. Each
Decision Variables
unknown quantity is assigned a variable (e.g., x₁, x₂).
A mathematical expression of the decision variables representing a single
Objective Function
goal — either maximized (profit, revenue) or minimized (cost, time, distance).
Restrictions or limitations on choices — ≤ (upper limit on resources), ≥
Constraints (minimum requirement), or = (exact requirement). Together they define the
feasible solution space.
The numerical values (coefficients) in the objective function and constraints.
Parameters
These are fixed inputs to the model.
Feasible solution space: The set of all feasible combinations of values of the decision
variables — the region defined by all constraints simultaneously. The LP algorithm searches this
space for the optimal combination of decision variables.
, Assumptions of Linear Programming
For a linear programming model to be used effectively, four assumptions must be satisfied:
Assumption Meaning
The impact of each decision variable is linear — doubling x doubles its
Linearity contribution to the objective and constraints. No products of variables, no
exponents.
Non-integer (fractional) values of decision variables are acceptable. If a
Divisibility
recurring process, a non-integer per-period average is generally fine.
Values of all parameters (coefficients) are known and constant. Sensitivity
Certainty
analysis is used later to examine what happens when parameters change.
No decision variable can be negative. Variables must be ≥ 0. This is always
Non-negativity
explicitly stated as a constraint.
Model Formulation
Model formulation is the process of assembling information about a problem into an LP model.
Follow this structured approach:
1. Identify and define decision variables.
Decision variables are typically 'the quantity of' something (e.g., x₁ = Quantity of product
1 to produce per day). Variables usually have a profit, cost, or time coefficient associated
with them.
2. Write the objective function.
Include every decision variable. State whether it is maximized or minimized. Use the
letter Z for the objective function value.
3. Write the constraints.
Each constraint restricts one or more decision variables. Give each constraint a
descriptive name (e.g., 'Labour', 'Material 1'). Standard form: all variables on the left
side, constant on the right side. Three common constraint types you will encounter:
◦ A ratio constraint: e.g., 'the ratio of x₁ to x₂ must be at least 3 to 2'. Set up x₁/x₂ ≥
3/2, cross-multiply to get 2x₁ ≥ 3x₂, then rearrange to standard form: 2x₁ − 3x₂ ≥ 0.
The direction of the inequality is preserved.
◦ A percentage constraint: e.g., 'x₁ cannot exceed 20% of the total mix (x₁ + x₂ + x₃)'.
Write x₁ ≤ 0.20(x₁ + x₂ + x₃), expand the right side, then move all variables to the left:
0.80x₁ − 0.20x₂ − 0.20x₃ ≤ 0.
◦ A minimum production constraint: e.g., 'Make at least 10 units of product 1': x₁ ≥
10. If a variable has a coefficient of 1, it need not be shown explicitly.
4. Add non-negativity constraints.
Always include x₁, x₂, … ≥ 0 on a single line. These prevent meaningless negative
solutions.
CHAPTER 6S: LINEAR PROGRAMMING
Comprehensive Exam Preparation Notes
1. Introduction and Linear Programming Model
Linear programming (LP) is a powerful quantitative tool used to obtain optimal solutions to
problems that involve requirements or limitations for resources — such as available material,
budget, labour, and machine time. These problems are referred to as constrained optimization
problems. Linear programming has been applied successfully across a wide range of decisions,
including:
• Determining optimal blends of animal feed and gasoline ingredients.
• Developing optimal production schedules.
• Identifying the optimal mix of products to produce in a factory.
LP techniques consist of a sequence of steps that will lead to an optimal solution to linear-
constrained problems, if an optimum exists. There are special-purpose and general-purpose LP
techniques. This chapter covers the two general-purpose solution techniques: graphical linear
programming (visual, limited to two variables) and computer solutions (practical for large real-
world problems).
A linear programming model is a mathematical representation of a constrained optimization
problem. It has four components:
Component Description
Represent choices — amounts of inputs to use or outputs to produce. Each
Decision Variables
unknown quantity is assigned a variable (e.g., x₁, x₂).
A mathematical expression of the decision variables representing a single
Objective Function
goal — either maximized (profit, revenue) or minimized (cost, time, distance).
Restrictions or limitations on choices — ≤ (upper limit on resources), ≥
Constraints (minimum requirement), or = (exact requirement). Together they define the
feasible solution space.
The numerical values (coefficients) in the objective function and constraints.
Parameters
These are fixed inputs to the model.
Feasible solution space: The set of all feasible combinations of values of the decision
variables — the region defined by all constraints simultaneously. The LP algorithm searches this
space for the optimal combination of decision variables.
, Assumptions of Linear Programming
For a linear programming model to be used effectively, four assumptions must be satisfied:
Assumption Meaning
The impact of each decision variable is linear — doubling x doubles its
Linearity contribution to the objective and constraints. No products of variables, no
exponents.
Non-integer (fractional) values of decision variables are acceptable. If a
Divisibility
recurring process, a non-integer per-period average is generally fine.
Values of all parameters (coefficients) are known and constant. Sensitivity
Certainty
analysis is used later to examine what happens when parameters change.
No decision variable can be negative. Variables must be ≥ 0. This is always
Non-negativity
explicitly stated as a constraint.
Model Formulation
Model formulation is the process of assembling information about a problem into an LP model.
Follow this structured approach:
1. Identify and define decision variables.
Decision variables are typically 'the quantity of' something (e.g., x₁ = Quantity of product
1 to produce per day). Variables usually have a profit, cost, or time coefficient associated
with them.
2. Write the objective function.
Include every decision variable. State whether it is maximized or minimized. Use the
letter Z for the objective function value.
3. Write the constraints.
Each constraint restricts one or more decision variables. Give each constraint a
descriptive name (e.g., 'Labour', 'Material 1'). Standard form: all variables on the left
side, constant on the right side. Three common constraint types you will encounter:
◦ A ratio constraint: e.g., 'the ratio of x₁ to x₂ must be at least 3 to 2'. Set up x₁/x₂ ≥
3/2, cross-multiply to get 2x₁ ≥ 3x₂, then rearrange to standard form: 2x₁ − 3x₂ ≥ 0.
The direction of the inequality is preserved.
◦ A percentage constraint: e.g., 'x₁ cannot exceed 20% of the total mix (x₁ + x₂ + x₃)'.
Write x₁ ≤ 0.20(x₁ + x₂ + x₃), expand the right side, then move all variables to the left:
0.80x₁ − 0.20x₂ − 0.20x₃ ≤ 0.
◦ A minimum production constraint: e.g., 'Make at least 10 units of product 1': x₁ ≥
10. If a variable has a coefficient of 1, it need not be shown explicitly.
4. Add non-negativity constraints.
Always include x₁, x₂, … ≥ 0 on a single line. These prevent meaningless negative
solutions.
