12.1.1 Formulating a Linear Programming Problem

Introduction

Linear Programming (LP) is a mathematical method used to optimize an objective function, such as maximizing profit or minimizing cost, subject to a set of constraints.

This note explains how to formulate problems as linear programs and introduces the concepts of slack, surplus, and artificial variables, which are essential for solving LP problems using methods like the Simplex algorithm.

Key Steps in Formulating a Linear Programming Problem

1. Define the Variables
2. Write the Objective Function
3. Write the Constraints
4. Non-Negativity Constraints

---

1. Define the Variables

Identify decision variables $x, y, z, \dots$ that represent quantities to be determined.

---

2. Write the Objective Function

Formulate the objective function to be maximised or minimised:

$$Z = ax + by + cz + \dots$$

where $a, b, c, \dots$ are coefficients that represent the contribution of each variable to the objective.

---

3. Write the Constraints

Express all constraints as linear inequalities or equalities:

$$a_1x + b_1y + c_1z \leq d_1, \quad a_2x + b_2y + c_2z \geq d_2, \quad \text{etc.}$$

where $a_i, b_i, c_i, \dots$ are coefficients, and $d_i$ is the limiting value.

---

4. Non-Negativity Constraints

Ensure that all decision variables are non-negative:

$$x, y, z \geq 0$$

---

Slack, Surplus, and Artificial Variables

Slack Variables

Definition: Added to $\leq$ (less-than-or-equal-to) constraints to convert them into equations.

$$a_1x + b_1y \leq d_1 \quad \Rightarrow \quad a_1x + b_1y + s_1 = d_1$$

where $s_1 \geq 0$ is the slack variable representing unused capacity.

Surplus Variables

Definition: Subtracted from $\geq$ (greater-than-or-equal-to) constraints to convert them into equations.

$$a_2x + b_2y \geq d_2 \quad \Rightarrow \quad a_2x + b_2y - s_2 = d_2$$

where $s_2 \geq 0$ is the surplus variable representing excess quantity.

Artificial Variables

Definition: Introduced for $\geq$ or $=$ constraints to start the Simplex algorithm. These variables are used temporarily and are eliminated during optimization.

$$a_3x + b_3y - s_3 = d_3 \quad \Rightarrow \quad a_3x + b_3y - s_3 + t_1 = d_3$$

where $t_1 \geq 0$ is the artificial variable.

Worked Examples

Note Summary