Master Linear Programming: From Basics to Graphical Solutions

1 Introduction to Linear Programming

In mathematics, linear programming (LP) is an optimization method that seeks to maximize or minimize a target function subject to linear constraints.

The term combines “linear,” indicating first‑order relationships among variables, and “programming,” meaning the process of selecting the best solution from alternatives.

An LP model consists of linear functions expressed as equations or inequalities, providing a powerful technique for optimal resource utilization.

Linear programming is widely applied in fields such as economics, business, telecommunications, and manufacturing.

2 Components of Linear Programming

Basic components of an LP are:

Decision variables : quantities that can be changed, e.g., how many units to produce or which route to choose. LP decision variables may be continuous, integer, or binary (0‑1).

Objective function : a linear function of the decision variables that is either maximized or minimized. For example, profit = 6A + 5B.

Constraints : linear inequalities representing limits on time, space, labor, material, etc., such as resource availability.

3 Example of a Linear Programming Problem

A chocolate manufacturer produces two types of chocolate, A and B. Each unit of A requires 1 unit of milk and 3 units of chocolate; each unit of B requires 1 unit of milk and 2 units of chocolate. The factory has 5 units of milk and 12 units of chocolate available.

Profit per unit: A yields 6 rupees, B yields 5 rupees. The company wants to maximize total profit.

3.1 Decision Variables

A = number of units of chocolate A to produce

B = number of units of chocolate B to produce

Profit = total profit

3.2 Objective Function

Maximize Profit = 6A + 5B.

3.3 Constraints

Milk constraint: 1·A + 1·B ≤ 5

Chocolate constraint: 3·A + 2·B ≤ 12

Non‑negativity and integrality: A, B ≥ 0 and must be integers.

4 Standard Form of Linear Programming

In standard form, the objective is expressed as a minimization problem and all constraints are written as ≤ inequalities, often using matrix notation. Converting to standard form facilitates algorithmic solution.

5 Graphical Method

For LP problems with two decision variables, the feasible region can be drawn on a graph. The optimal solution lies at a corner point of this region.

The feasible region is shown below:

By shifting the objective line outward until it touches the feasible region, the optimal point (2, 3) is found, yielding the maximum profit.

6 Summary

This article introduced the concept of linear programming, demonstrated its components through a chocolate production case, presented the standard formulation, and explained how to solve a two‑variable problem graphically. Future posts will explore additional LP techniques.

References

https://www.analyticsvidhya.com/blog/2017/02/lintroductory-guide-on-linear-programming-explained-in-simple-english/

https://github.com/ThomsonRen/mathmodels