Linear Programming
Getting the most from limited resources — turning a real decision into linear inequalities, drawing the region they allow, and reading the best answer straight off its corners
- The vocabulary of optimisation: objective function, decision variables and constraints.
- How to formulate a real-world decision as a linear programming problem (LPP).
- The feasible region as the intersection of half-planes, and why it is always convex.
- The graphical method and the corner-point theorem for finding the optimum.
- The difference between bounded and unbounded regions and what each means for a solution.
- Special cases — multiple optima, infeasibility, an unbounded objective — and the standard manufacturing, diet and transportation problems.
The Language of Optimisation
Most practical decisions come down to making something as large or as small as possible — profit as large, cost as small — while staying within limits on time, material or money. Linear programming handles exactly this when the quantity to optimise and all the limits are linear. The quantities we choose are the decision variables \(x,y\); the function to be optimised is the objective function \(Z\); and the limits are the constraints, written as linear inequalities.
The conditions \(x\ge 0,\ y\ge 0\) are the non-negativity restrictions — you cannot make a negative number of tables. A point that satisfies every constraint is a feasible solution; among all of these, one that optimises \(Z\) is an optimal solution.
Formulating an LPP
The hardest part of a linear programming problem is usually translating words into mathematics. The recipe is fixed: name the decision variables, write the objective in terms of them, then turn each resource limit into an inequality. A table of the data makes the structure obvious before any algebra begins.
First, let \(x\) and \(y\) be the amounts of each product or activity. Second, write \(Z=ax+by\) for the profit or cost. Third, for each limited resource write "amount used \(\le\) amount available", using \(\ge\) for minimum requirements. Always close with \(x,y\ge 0\).
The Feasible Region
Each linear inequality such as \(2x+y\le 60\) describes a half-plane — everything on one side of the boundary line. The set of points that satisfy all the constraints at once is their overlap, the feasible region. Because it is an intersection of half-planes it is always a convex polygon (possibly open), and its straight edges meet at corner points, or vertices.
To plot a constraint, draw its boundary line and test a point not on it — usually the origin \((0,0)\). If the origin satisfies the inequality, shade its side; otherwise shade the other. The feasible region is the area shaded by every constraint together.
The Graphical Method
For two variables the whole problem can be solved by drawing. Sketch the feasible region, then slide the objective line \(ax+by=Z\) — a family of parallel lines, one for each value of \(Z\) — across it. Pushing the line as far as the region allows in the direction of increasing \(Z\) finds the maximum; the last point of contact is the answer, and it is always a corner.
In practice we skip the sliding line altogether: find the coordinates of every corner point, evaluate \(Z\) at each, and pick the largest (for a maximum) or smallest (for a minimum). This works because of the theorem in the next section.
The Corner-Point Theorem
The reason a finite check of vertices suffices is one of the most useful results in applied mathematics: a linear objective on a convex region can only reach its extreme values at the boundary, and in fact at a corner. The interior and the middle of an edge can never beat both ends.
More precisely: if \(R\) is the feasible region and \(Z=ax+by\) attains an optimal value, that value is taken at a vertex of \(R\). If two adjacent vertices both give the optimum, then every point on the edge joining them is optimal too — the source of multiple optimal solutions.
Bounded & Unbounded Regions
Whether an optimum is guaranteed depends on the shape of the feasible region. A bounded region fits inside some circle; an unbounded one stretches to infinity in at least one direction. The distinction decides whether both a maximum and a minimum must exist.
On an unbounded region a maximum (or minimum) may fail to exist. When checking such a region, a candidate value \(M\) is the true maximum only if the open half-plane \(ax+by>M\) shares no point with \(R\); for a minimum \(m\), the test is that \(ax+by
Special Cases
Not every problem has a single, tidy answer. Three situations recur often enough to recognise on sight, and each leaves a clear fingerprint on the graph.
Multiple optima occur when the objective line is parallel to a binding constraint, so a whole edge is optimal. A problem is infeasible when the constraints contradict and the feasible region is empty. And the objective is unbounded when the region runs off to infinity in the direction that improves \(Z\), so no finite optimum exists.
Standard Types of Problems
Almost every textbook LPP is one of three classics, and recognising the type tells you immediately whether you are maximising or minimising.
The manufacturing problem chooses production levels to maximise profit against limits on labour and material (constraints of the \(\le\) type). The diet problem chooses quantities of foods to minimise cost while meeting minimum nutritional requirements (constraints of the \(\ge\) type, giving an unbounded region). The transportation problem chooses how much to ship from each source to each destination to minimise total cost while meeting supply and demand. In every case the formulation recipe of Section 33-2 applies unchanged.
Putting It to Work
Problem. A workshop makes tables and chairs. A table needs \(2\) h of carpentry and \(1\) h of polishing; a chair needs \(1\) h of each. There are \(40\) carpentry hours and \(30\) polishing hours available, and the profit is \(₹70\) per table and \(₹50\) per chair. Set up the LPP.
Solution. Let \(x\) tables and \(y\) chairs be made:
Problem. Maximise \(Z=4x+3y\) subject to \(x+y\le 40,\ 2x+y\le 60,\ x,y\ge 0\).
Solution. The corners are \((0,0),(30,0),(20,20),(0,40)\), where \((20,20)\) is the intersection of the two lines. Evaluate \(Z\):
The maximum is \(Z=140\) at \((20,20)\).
Problem. Minimise \(Z=50x+70y\) subject to \(2x+y\ge 8,\ x+2y\ge 10,\ x,y\ge 0\).
Solution. The corners of the (unbounded) region are \((0,8),(2,4),(10,0)\):
Since \(50x+70y<380\) has no point in the region, the minimum is \(Z=380\) at \((2,4)\).
Problem. Maximise \(Z=x+2y\) subject to \(x+2y\le 10,\ x\le 6,\ y\le 4,\ x,y\ge 0\).
Solution. The corners are \((0,0),(6,0),(6,2),(2,4),(0,4)\):
Two corners tie at \(Z=10\), so every point on the edge from \((6,2)\) to \((2,4)\) is optimal.
Problem. Foods \(F_1,F_2\) cost \(₹4\) and \(₹3\) per unit. A unit of \(F_1\) gives \(3\) units of protein and \(2\) of iron; a unit of \(F_2\) gives \(1\) and \(4\). The diet needs at least \(12\) of protein and \(16\) of iron. Set up the LPP.
Solution. Let \(x,y\) be the units of each food:
Problem. Can \(Z=3x+2y\) be maximised subject to \(x-y\le 1,\ x+y\ge 3,\ x,y\ge 0\)?
Solution. The feasible region is unbounded above and to the right, so \(Z\) grows without limit:
A minimum, however, does exist at a corner — unboundedness only blocks the optimum in the improving direction.
Chapter Summary
Optimise \(Z=ax+by\) over linear constraints with \(x,y\ge 0\).
Variables → objective → constraints; test "used \(\le\) available".
Intersection of half-planes; always convex with straight edges.
Any optimum sits at a vertex; evaluate \(Z\) at each corner.
Bounded guarantees a max and min; unbounded may have neither.
Multiple optima (parallel edge), infeasible (empty \(R\)), unbounded \(Z\).
Problems
For each problem, formulate where needed, sketch the feasible region, list the corners, and evaluate the objective at each. Difficulty rises down the list.
- Shade the region given by \(x+y\le 5,\ x,y\ge 0\) and name its corner points.
- Maximise \(Z=3x+2y\) subject to \(x+y\le 4,\ x,y\ge 0\).
- Maximise \(Z=5x+4y\) subject to \(x+y\le 6,\ x\le 4,\ x,y\ge 0\).
- Minimise \(Z=3x+5y\) subject to \(x+y\ge 6,\ x,y\ge 0\).
- Maximise \(Z=4x+3y\) subject to \(2x+y\le 10,\ x+3y\le 15,\ x,y\ge 0\).
- Minimise \(Z=200x+500y\) subject to \(x+2y\ge 10,\ 3x+4y\ge 24,\ x,y\ge 0\).
- A factory makes two toys at profits \(₹5\) and \(₹3\). Each of the first needs \(2\) machine-hours, each of the second \(1\); \(800\) hours are available. Formulate the LPP to maximise profit.
- Show that maximising \(Z=x+y\) over \(x-y\le 1,\ x+y\ge 3,\ x,y\ge 0\) has no finite maximum.
- Maximise \(Z=2x+4y\) subject to \(x+2y\le 8,\ x\le 5,\ y\le 3,\ x,y\ge 0\) and identify any multiple optima.
- A dealer has \(₹50{,}000\) and space for \(60\) items. A fan costs \(₹1000\) (profit \(₹250\)) and a sewing machine \(₹1200\) (profit \(₹180\)). Formulate the LPP to maximise profit.
- A diet must supply at least \(8\) units of vitamin A and \(10\) of vitamin C from foods costing \(₹5\) and \(₹7\) per unit, with given vitamin contents. Set up the cost-minimising LPP.
- Solve Problem 5 graphically, giving the optimal vertex and value of \(Z\).
- Two factories supply two markets at known unit transport costs. Set up the transportation LPP that minimises total cost subject to the supply and demand constraints.