Linear Programming Study Notes, Formulas & Summary

1. Introduction

Linear programming (LPP) is a mathematical technique for optimising a linear objective function subject to a set of linear constraints. Typical examples include maximising profit given limited raw materials, minimising cost of transportation subject to supply and demand, and allocating resources efficiently. Because the objective and all constraints are linear, the problem can be solved geometrically when only two variables are involved, which is the case studied in this chapter.

The chapter defines the key terms of a linear programming problem: the decision variables, the objective function, the constraints, the feasible region, and the optimal solution. It then develops the graphical method for two variables, showing that the optimum value, if it exists, occurs at a corner point (vertex) of the feasible region. Problems with unbounded feasible regions are also analysed, where a maximum or minimum may or may not exist.

Linear programming is one of the most applied topics in the entire syllabus, used in industry for production planning, in agriculture for crop selection, and in transportation and logistics. The board examination usually presents one word problem that must be converted into a mathematical LPP and then solved graphically. Mastery of the corner-point method and careful graphing give full, reliable marks.

2. Formulating a Linear Programming Problem

A linear programming problem in two variables has the structure:

Decision variables: x and y.
Objective function: $Z = ax + by$, to be maximised or minimised.
Constraints: a set of linear inequalities such as $a_1x + b_1y \leq c_1$, $x, y \geq 0$.

The non-negativity restrictions $x \geq 0$, $y \geq 0$ are almost always present because quantities like production and cost cannot be negative.

Steps in Formulation

Identify the decision variables and denote them x and y.
Express the objective as a linear function Z = ax + by.
Convert each given restriction into a linear inequality.
Include the non-negativity constraints x >= 0, y >= 0.
State clearly whether Z is to be maximised or minimised.

3. The Feasible Region and Corner Points

The set of all points (x, y) satisfying all the constraints simultaneously is the feasible region. It is the intersection of the half-planes determined by each inequality.

The feasible region is always a convex polygon (possibly unbounded).
The corner points (vertices) of this polygon are the candidates for the optimum.
A point is feasible if it satisfies every constraint; otherwise it is infeasible.

The fundamental theorem of linear programming states: if a linear programming problem has an optimal solution, then it occurs at one of the corner points of the feasible region. Consequently, the graphical method evaluates Z at each corner point and selects the best value.

4. The Graphical Method

Plot each constraint inequality as a line, shading the half-plane that satisfies the inequality.
Determine the feasible region as the intersection of all shaded half-planes, including x >= 0 and y >= 0.
Find the coordinates of all corner points of the feasible region by solving pairs of boundary equations.
Evaluate the objective function Z at each corner point.
Choose the corner point that gives the maximum (or minimum) value of Z as the optimal solution.

Example

Maximise $Z = 3x + 2y$ subject to $x + y \leq 4$, $x, y \geq 0$.

The feasible region is the triangle with vertices (0, 0), (4, 0), (0, 4). Evaluating: - Z(0, 0) = 0 - Z(4, 0) = 12 - Z(0, 4) = 8

The maximum is 12 at (4, 0).

5. Unbounded Feasible Regions

If the feasible region is unbounded, an optimal maximum may not exist. The test: maximise (or minimise) Z, and check whether Z can be made arbitrarily large (or small) within the feasible region. If so, no finite optimum exists; otherwise, the corner-point evaluation still gives the optimum.

The typical exam problem asks to minimise a cost; if the feasible region is unbounded but Z has a lower bound enforced by constraints, the minimum will still occur at a corner point.

6. Different Types of Solutions

Unique optimal solution: exactly one corner point gives the optimum.
Multiple optimal solutions: two adjacent corner points give the same optimum value, in which case every point on the connecting edge is also optimal.
No feasible solution: the constraints are inconsistent and the feasible region is empty.
Unbounded solution: the objective can be improved without bound.

7. Worked Application Problem

A manufacturer produces two products, A and B. Each unit of A requires 3 hours on machine I and 1 hour on machine II; each unit of B requires 1 hour on machine I and 2 hours on machine II. The machines are available for at most 12 and 8 hours respectively. Profit per unit is Rs 5 for A and Rs 4 for B. Maximise the profit.

Variables: x units of A, y units of B. Constraints: $3x + y \leq 12$, $x + 2y \leq 8$, $x, y \geq 0$. Maximise $Z = 5x + 4y$.

The corner points are (0, 0), (4, 0), (0, 4), and the intersection of $3x + y = 12$ and $x + 2y = 8$, which is (16/5, 12/5). Evaluating Z: Z(0,0) = 0, Z(4,0) = 20, Z(0,4) = 16, Z(16/5, 12/5) = 80/5 + 48/5 = 128/5 = 25.6. The maximum profit is 25.6 at x = 16/5, y = 12/5.

Quick Revision Tables

Table 1: Key Terms of an LPP

Term	Meaning
Decision variables	x and y being optimised
Objective function	Z = ax + by, maximised or minimised
Constraints	Linear inequalities restricting x and y
Non-negativity	x >= 0, y >= 0
Feasible region	Set of all points satisfying all constraints
Corner points	Vertices of the feasible region

Table 2: Graphical Method Steps

Step	Action
1	Draw the lines for each constraint
2	Shade the feasible half-planes
3	Identify the feasible region
4	List all corner points
5	Evaluate Z at each corner point
6	Select the best value

Table 3: Types of Solutions

Case	Condition
Unique optimum	Single corner point best
Multiple optima	Two adjacent corner points tie
No feasible solution	Constraints inconsistent
Unbounded	Z can be improved without bound

Mind Map

graph TD
    A["Linear Programming"] --> B["Formulation"]
    A --> C["Feasible Region"]
    A --> D["Corner Point Method"]
    A --> E["Types of Solutions"]
    A --> F["Applications"]
    B --> B1["Objective Z = ax + by"]
    B --> B2["Constraints as inequalities"]
    B --> B3["x, y >= 0"]
    C --> C1["Intersection of half-planes"]
    C --> C2["Convex polygon"]
    D --> D1["Find all corner points"]
    D --> D2["Evaluate Z at each"]
    D --> D3["Pick best value"]
    E --> E1["Unique, multiple, none, unbounded"]
    F --> F1["Profit maximisation"]
    F --> F2["Cost minimisation"]

Important Diagrams (SVG)

Diagram 1: Feasible Region and Corner Points

Diagram 2: Profit Maximisation in a Two-Constraint Problem

Common Mistakes

Forgetting the non-negativity constraints x >= 0 and y >= 0, which restrict the feasible region to the first quadrant.
Shading the wrong side of a constraint line; test a point such as the origin to confirm the correct half-plane.
Listing interior points of the feasible region as candidates; only corner points matter.
Inconsistent constraints producing an empty feasible region, yet claiming a solution exists.
In an unbounded feasible region, assuming a maximum always exists; if Z can grow without bound, there is no finite maximum.
Solving a pair of constraint equations to find a corner point that is not actually part of the feasible region.
Maximising when the problem asks to minimise, or vice versa; read the objective carefully.
Failing to convert a word problem's units (hours, days, quantity) consistently when writing constraints.
Rounding a fractional optimal solution when the problem requires integral quantities (e.g., number of units).
Forgetting to state the final answer in the context of the problem, e.g., "maximum profit is Rs ..." rather than just giving the point.

Exam Tips

In word problems, define x and y clearly at the start and write each constraint as an inequality, checking the direction with a test point.
Draw the lines accurately, mark the feasible region, and list every corner point with its coordinates.
For the corner point that is the intersection of two constraint lines, solve the two equations simultaneously; do not guess from the graph.
When the feasible region is unbounded, verify whether the objective can be improved indefinitely; if yes, state that no maximum (or minimum) exists.
Evaluate Z at every corner point in a neat table; this makes the comparison explicit and earns method marks.
Check your final point is feasible by substituting into all constraints.
If two adjacent corner points give the same optimum, note that all points on the edge joining them are also optimal.
Practise converting the standard production, diet, and transportation problems into LPP form, since these recur in the examination.

Conclusion

Linear programming is a beautiful example of how a simple geometric idea solves practical optimisation problems. By translating a real-world situation into a linear objective function and linear constraints, and then finding the feasible region and its corner points, the optimum solution is obtained in a few arithmetic steps. The fundamental theorem that the optimum lies at a corner point is what makes the method efficient and reliable, and it is the entire basis of the graphical technique. Although the chapter is short, its ideas are the foundation of operations research and management science, where high-dimensional linear programs are solved by the simplex method. For the board examination, the ability to formulate word problems correctly and to present the graphical solution clearly is the key to securing full marks in this predictable and scoreable chapter.

Linear Programming — Study Notes