Quick answerA Linear Programming Problem (LPP) optimises a linear objective function subject to a system of linear constraints and non-negativity restrictions.
A Linear Programming Problem (LPP) is a problem that seeks to maximise or minimise a linear function of several variables, called the objective function, subject to certain conditions expressed as linear equations or inequalities, called constraints. Because both the objective function and the constraints are linear in the variables, such problems are called linear programming problems.
Every LPP has three essential parts:
Decision variables — the unknown quantities (usually x, y, or x₁, x₂, …) whose values are to be determined.
Objective function — the linear function Z = ax + by (or Z = c₁x₁ + c₂x₂ + …) that has to be optimised.
Constraints — linear inequalities or equations, arising from limited resources (time, money, raw material, labour), that the decision variables must satisfy.
In addition, almost every practical LPP carries non-negativity restrictions, x ≥ 0 and y ≥ 0, since quantities such as the number of items produced or the amount of money invested cannot be negative.
Worked example (identifying the parts). A shopkeeper sells two items, pens and notebooks. Each pen gives a profit of ₹2 and each notebook gives a profit of ₹5. The shopkeeper can stock at most 200 items in all, and he never keeps more than 80 notebooks. Identify the decision variables, objective function and constraints.
Let x = number of pens and y = number of notebooks stocked. Objective function (to be maximised): Z = 2x + 5y. Constraints: x + y ≤ 200 (stock limit), y ≤ 80 (notebook limit), x ≥ 0, y ≥ 0 (non-negativity).
This one objective function together with a system of linear inequalities is exactly what defines an LPP; the next sections show how to build such a system from a word problem and how to solve it graphically.
Objective function (general form)Z = c₁x₁ + c₂x₂ + … + cₙxₙLinear function of the decision variables that is to be maximised or minimised
General linear constrainta₁x₁ + a₂x₂ + … + aₙxₙ ≤ b (or =, ≥)Each constraint restricts the combination of decision variables allowed
Non-negativity restrictionx₁, x₂, …, xₙ ≥ 0Decision variables cannot be negative in real applications
Remember
LPP optimises a linear objective function subject to linear constraints.
Decision variables represent the quantities to be decided (e.g., units produced).
Non-negativity restrictions (x ≥ 0, y ≥ 0) are almost always present in real applications.
Constraints usually arise from limited resources such as time, money, labour or raw material.
'Optimise' means either maximise (e.g., profit) or minimise (e.g., cost).
Mathematical Formulation of an LPP
Quick answerFormulating an LPP means turning a word problem into a decision variable, an objective function, and a set of linear constraints in four systematic steps.
Formulating an LPP means translating a real-world decision problem into precise mathematical language. The general procedure has four steps.
Identify and label the decision variables (usually x and y for two-variable problems).
Express the quantity to be maximised or minimised as a linear objective function Z = ax + by in terms of the decision variables.
Translate every restriction given in words (on resources, time, capacity, requirements) into a linear inequality or equation in x and y.
Add the non-negativity restrictions x ≥ 0, y ≥ 0, since the decision variables denote physical quantities.
Worked example. A furniture workshop makes two products — bookshelves and study tables — using carpentry and finishing labour. Each bookshelf needs 3 hours of carpentry and 1 hour of finishing; each study table needs 2 hours of carpentry and 2 hours of finishing. The workshop has at most 42 carpentry hours and 24 finishing hours available per week. The profit is ₹300 per bookshelf and ₹250 per study table. Formulate this as an LPP to maximise profit.
Step 1 — Let x = number of bookshelves made per week and y = number of study tables made per week. Step 2 — Objective function: Maximise Z = 300x + 250y. Step 3 — Carpentry-hour restriction: 3x + 2y ≤ 42. Finishing-hour restriction: x + 2y ≤ 24. Step 4 — Non-negativity: x ≥ 0, y ≥ 0.
The complete mathematical model is: Maximise Z = 300x + 250y subject to 3x + 2y ≤ 42, x + 2y ≤ 24, x ≥ 0, y ≥ 0. This model is solved graphically in the next section.
Word clues help identify the type of inequality to use: 'at most', 'not more than', 'no greater than' give a ≤ constraint; 'at least', 'not less than', 'a minimum of' give a ≥ constraint; 'exactly', 'equal to' gives an = constraint.
Two-variable objective functionZ = ax + bya, b are the per-unit profit/cost coefficients
Resource constraint (example)3x + 2y ≤ 42Carpentry-hour restriction in the worked example
Resource constraint (example)x + 2y ≤ 24Finishing-hour restriction in the worked example
Remember
Formulation has four steps: define variables, write objective function, write constraints, add non-negativity.
Phrases like 'at most' mean ≤; 'at least' means ≥; 'exactly' means =.
The objective function is always linear: no x², xy or 1/x terms are allowed.
Every resource restriction in the problem statement becomes one linear inequality.
A correctly formulated LPP fully specifies Z, all constraints, and x, y ≥ 0.
Graphical Method and the Feasible Region
Quick answerEach linear constraint defines a half-plane; the intersection of all these half-planes with the first quadrant is the feasible region, whose vertices are the corner points.
The graphical method is used to solve LPPs having exactly two decision variables. Each linear constraint ax + by ≤ c (or ≥, =) represents a straight line ax + by = c in the xy-plane, and this line divides the plane into two half-planes. The correct half-plane is found quickly by the test-point method: substitute a convenient point, usually the origin (0, 0) (provided it does not lie on the line), into the inequality; if the inequality holds, the half-plane containing the origin is the required region, otherwise it is the other half-plane.
The feasible region of an LPP is the common (intersection) region of all the half-planes obtained from the constraints, together with the non-negativity restrictions x ≥ 0, y ≥ 0 (which confine the region to the first quadrant). Every point inside or on the boundary of the feasible region is a feasible solution; a point outside it is an infeasible solution. If the feasible region can be enclosed inside a sufficiently large circle it is called bounded; otherwise it is unbounded. The corner points (vertices) of the feasible region — where two boundary lines meet — play the central role in solving the LPP, as shown in the next section.
Worked example. Continuing the workshop model from the previous section — 3x + 2y ≤ 42, x + 2y ≤ 24, x ≥ 0, y ≥ 0 — find the feasible region and its corner points.
Both constraints are of the '≤' type and the origin satisfies them (3(0)+2(0)=0≤42 and 0+2(0)=0≤24), so the origin lies inside both half-planes; the non-negativity restrictions confine the region to the first quadrant.
Intercepts: 3x + 2y = 42 meets the axes at (14, 0) and (0, 21); x + 2y = 24 meets the axes at (24, 0) and (0, 12). Solving the two equations simultaneously (subtracting x + 2y = 24 from 3x + 2y = 42 gives 2x = 18, so x = 9, y = 7.5) gives their intersection point (9, 7.5). Testing each candidate point against both constraints shows the feasible region is the bounded quadrilateral with corner points O(0, 0), A(14, 0), B(9, 7.5) and C(0, 12).
Boundary line of a constraintax + by = cThe straight line associated with the inequality ax+by ≤ c or ≥ c
Intersection of two boundary linesSolve a₁x + b₁y = c₁ and a₂x + b₂y = c₂ simultaneouslyGives the coordinates of a corner point of the feasible region
Remember
Each constraint ax + by ≤ c defines a half-plane bounded by the line ax + by = c.
The test-point (origin) method quickly tells which half-plane satisfies a ≤ or ≥ constraint.
The feasible region is the intersection of all constraint half-planes and the first quadrant.
A feasible region is bounded if it fits inside a circle of finite radius, otherwise unbounded.
Corner points (vertices) are where two boundary lines of the feasible region meet.
Corner Point Method (Fundamental Theorem of LPP)
Quick answerThe Fundamental Theorem of Linear Programming shows that the optimum of Z always occurs at a corner point, reducing the search to evaluating Z at a handful of vertices.
The Fundamental Theorem of Linear Programming guarantees that we do not need to test every point of the (infinite) feasible region — only its corner points.
Theorem 1. Let R be the feasible region (a convex polygon) for an LPP and let Z = ax + by be the objective function. When Z has an optimum value (maximum or minimum) on R, and R is bounded, that optimum value must occur at a corner point (vertex) of R.
Theorem 2. If R is unbounded, a maximum or minimum value of Z may not exist. However, if one does exist, it must still occur at a corner point of R.
These theorems give a simple algorithm, the Corner Point Method:
Find the feasible region and determine the coordinates of all its corner points (by solving the boundary equations pairwise, or reading intercepts).
Evaluate the objective function Z at each corner point.
If the region is bounded, the largest of these values is the maximum of Z and the smallest is the minimum of Z.
If the region is unbounded, identify the largest value M and smallest value m among the corner points, then check whether the open half-plane ax + by > M (for a maximum) or ax + by < m (for a minimum) shares any point with the feasible region. If it does not, M or m is indeed the required optimum; if it does, that optimum does not exist.
Worked example. Maximise Z = 50x + 15y subject to 5x + y ≤ 100, x + y ≤ 60, x ≥ 0, y ≥ 0.
Solving 5x + y = 100 and x + y = 60 simultaneously (subtracting gives 4x = 40, so x = 10, y = 50) gives the point (10, 50). The line 5x + y = 100 meets the x-axis at (20, 0), which satisfies x + y ≤ 60, so it is feasible. The line x + y = 60 meets the y-axis at (0, 60), which satisfies 5x + y ≤ 100, so it too is feasible. The feasible region is the bounded quadrilateral O(0,0), A(20,0), B(10,50), C(0,60).
Evaluating Z = 50x + 15y:
O(0, 0): Z = 0
A(20, 0): Z = 1000
B(10, 50): Z = 500 + 750 = 1250
C(0, 60): Z = 900
The largest value is 1250, obtained at B(10, 50). Since the feasible region is bounded, by Theorem 1 the maximum value of Z is 1250, attained at x = 10, y = 50.
Objective function (worked example)Z = 50x + 15yEvaluated at each corner point to find the maximum
Unbounded-region maximum testax + by > MIf this open half-plane shares a point with the feasible region, Z has no maximum
Unbounded-region minimum testax + by < mIf this open half-plane shares a point with the feasible region, Z has no minimum
Remember
Fundamental Theorem: on a bounded feasible region, the optimum of Z always occurs at a corner point.
Corner Point Method: list all vertices, evaluate Z at each, pick the largest/smallest.
For an unbounded region, an apparent maximum/minimum must be confirmed with the open half-plane test.
If the open half-plane ax + by > M meets the feasible region, no maximum exists.
The method converts an infinite search over the region into a finite check of a few points.
Types of Linear Programming Problems
Quick answerManufacturing, diet, allocation and transportation problems are the recurring LPP categories; all are solved by formulating, then applying the graphical corner-point method.
Most examination questions on linear programming are word problems that fall into a few recurring categories:
Manufacturing / product-mix problems — decide how many units of each product to make, given limited machine-hours or labour-hours, to maximise profit.
Diet problems — decide the quantity of each food to include in a diet, given nutrient requirements, to minimise cost (or, as in some problems, to minimise an undesirable nutrient).
Allocation / investment problems — decide how to distribute a fixed budget, space or time among activities to maximise return or output.
Transportation-type problems — decide how much of a commodity to send so as to minimise transportation cost, subject to supply and demand limits (two-variable versions are solved by the same graphical method).
Whatever the category, the same three-part approach applies: define the decision variables, write the linear objective function, and translate every stated restriction into a linear inequality.
Worked example (allocation problem). A dealer wishes to purchase electric fans and sewing machines. He has only ₹5,760 to invest and has storage space for at most 20 items in all. A fan costs ₹360 and a sewing machine costs ₹240. He earns a profit of ₹22 on every fan and ₹18 on every sewing machine sold. Assuming he can sell every item he buys, how many of each should he purchase to maximise his profit?
Let x = number of fans and y = number of sewing machines purchased. Maximise Z = 22x + 18y subject to 360x + 240y ≤ 5760, i.e. 3x + 2y ≤ 48; x + y ≤ 20; x ≥ 0, y ≥ 0.
Solving 3x + 2y = 48 and x + y = 20 simultaneously (y = 20 − x, so 3x + 2(20 − x) = 48 ⇒ x + 40 = 48 ⇒ x = 8, y = 12) gives (8, 12). The intercepts give the remaining feasible vertices: (16, 0) from 3x + 2y = 48 (16 ≤ 20, feasible) and (0, 20) from x + y = 20 (3(0)+2(20)=40 ≤ 48, feasible).
Evaluating Z = 22x + 18y: at (0,0), Z = 0; at (16,0), Z = 352; at (8,12), Z = 176 + 216 = 392; at (0,20), Z = 360. The maximum value is 392, attained at x = 8, y = 12 — the dealer should buy 8 fans and 12 sewing machines for a maximum profit of ₹392.
Objective function (worked example)Z = 22x + 18yTotal profit from x fans and y sewing machines
Storage constraint (worked example)x + y ≤ 20At most 20 items can be stored
Remember
Manufacturing, diet, allocation and transportation problems are the common LPP archetypes in the syllabus.
Diet problems often minimise cost or a nutrient, subject to ≥ requirements on other nutrients.
Allocation problems typically have a budget constraint and a total-quantity/space constraint.
The same formulate → graph → corner-point-evaluate method solves every category.
Units in the problem (₹, hours, grams) must be kept consistent when writing constraints.
Special Cases: Infeasible, Unbounded and Multiple Optimal Solutions
Quick answerAn LPP can have no solution (infeasible), an optimum that fails to exist (unbounded region), or infinitely many optimal solutions along an edge of the feasible region.
Not every LPP behaves like the tidy bounded examples seen so far. Three special situations are important to recognise.
Infeasible problem. If the constraints are mutually contradictory, the feasible region is empty — there is no point satisfying every constraint simultaneously, and the LPP has no solution. This typically happens when a problem demands, say, x + y ≤ 10 and x + y ≥ 20 at the same time.
Unbounded feasible region. When the constraints are mostly of the '≥' type, the feasible region often extends indefinitely in some direction. On such a region a maximum of Z = ax + by (with a, b > 0) usually does not exist, because Z can be made arbitrarily large; but a minimum may still exist and must be confirmed using the open half-plane test described earlier.
Multiple optimal solutions. If the objective function line is parallel to one edge (boundary segment) of the feasible region at the point of optimum, then every point on that entire edge gives the same optimal value of Z — the LPP then has infinitely many optimal solutions, not just one.
Worked example (multiple optimal solutions). Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, y ≥ 0.
Solving 2x + y = 3 and x + 2y = 6 simultaneously (from the first, y = 3 − 2x; substituting, x + 2(3 − 2x) = 6 ⇒ −3x = 0 ⇒ x = 0, y = 3) gives the corner point (0, 3), which lies on both lines. The other corner point, where x + 2y = 6 meets the x-axis, is (6, 0); it also satisfies 2x + y ≥ 3 (12 ≥ 3). Since both constraints are '≥' type, the region is unbounded, and only these two finite corner points need to be checked, together with the open half-plane test.
Evaluating Z = x + 2y: at (0, 3), Z = 6; at (6, 0), Z = 6. Both corner points give the same value. Testing the open half-plane x + 2y < 6 shows it has no point in common with the feasible region, since the constraint x + 2y ≥ 6 excludes it entirely — so Z = 6 is genuinely the minimum. Because the entire boundary segment joining (0, 3) and (6, 0) lies on the line x + 2y = 6, every point on this segment — not only the two corner points — gives Z = 6. This LPP therefore has infinitely many optimal solutions, all lying on the segment from (0, 3) to (6, 0).
Finally, linear programming has its own boundaries as a modelling tool: it can only model problems where the objective and every constraint are linear in the decision variables; it assumes divisibility (fractional values of x, y are allowed, even though a real 'answer' may need rounding in practice); and problems with more than two decision variables generally need algebraic methods (such as the Simplex method) rather than the graphical method used in this chapter.
Objective function (worked example)Z = x + 2yAttains the same minimum value at every point of an entire edge, illustrating multiple optimal solutions
Binding constraint (worked example)x + 2y ≥ 6The edge on which every point gives the minimum value of Z in the worked example
Remember
An infeasible LPP has contradictory constraints and no feasible region at all.
On an unbounded region, a maximum may fail to exist even though a minimum does (or vice versa) — always apply the half-plane test.
Multiple optimal solutions occur when the objective line is parallel to an edge of the feasible region at the optimum.
When multiple optimal solutions exist, every point on the connecting edge — not just its two endpoints — is optimal.
Linear programming assumes linearity and divisibility, and the graphical method works only for two decision variables.
The formula sheet
Every formula in this chapter, in one place — screenshot it before your exam.
Tap an answer to check it instantly — you'll see why it's right, and what to revise if it isn't.
0 correct · 0/12 answered
Q1Basic terminologyeasy
In a linear programming problem, the linear function that is to be maximised or minimised is called the ____.
The function Z = ax + by whose optimum value is sought is called the objective function; constraints are the restrictions on the variables.
Q2Basic terminologyeasy
The common region determined by all the constraints (including non-negativity restrictions) of a linear programming problem is called the ____.
The set of all points satisfying every constraint simultaneously is the feasible region; every point in it is a feasible solution.
Q3Basic terminologyeasy
The points where two boundary lines of the feasible region meet are called the ____ of the feasible region.
These vertices, also called corner points or extreme points, are the only points that need to be checked to find the optimal value of Z.
Q4Special casesmedium
If the set of all feasible solutions of an LPP is empty, the linear programming problem is said to be:
When the constraints contradict one another so that no point satisfies all of them, the feasible region is empty and the problem is called infeasible — it has no solution.
Q5Corner point theoremmedium
Let R be the feasible region of an LPP with objective function Z = ax + by. If R is bounded, then:
By the Fundamental Theorem of Linear Programming, if the feasible region is bounded, the objective function always attains both a maximum and a minimum, each at a corner point of the region.
Q6Multiple optimal solutionsmedium
The corner points of the feasible region of an LPP are (0, 3), (1, 1) and (3, 0). If Z = px + qy (p, q > 0) attains its minimum value at both (1, 1) and (0, 3), then which relation must hold?
Equal minimum values require p(1)+q(1) = p(0)+q(3), i.e. p + q = 3q, so p = 2q; checking the third point (3,0) gives Z = 3p = 6q, which is larger, confirming the other two are indeed the minimum points.
Q7Corner point methodmedium
Maximise Z = 3x + 2y subject to x + 2y ≤ 10, 3x + y ≤ 15, x ≥ 0, y ≥ 0. What is the maximum value of Z?
The corner points are (0,0), (5,0), (4,3) and (0,5); Z equals 0, 15, 18 and 10 respectively, so the maximum is 18 at (4, 3).
Q8Corner point methodhard
Minimise Z = 3x + 5y subject to x + 3y ≥ 3, x + y ≥ 2, x ≥ 0, y ≥ 0. What is the minimum value of Z?
The relevant corner points are (3,0), (3/2, 1/2) and (0,2), giving Z = 9, 7 and 10 respectively; the minimum is 7 at (3/2, 1/2).
Q9Unbounded feasible regionhard
On an unbounded feasible region, the largest value M of an objective function Z = ax + by (a, b > 0) among its corner points is found. This M can be declared the true maximum of Z only if:
On an unbounded region a maximum may not exist even though one corner point gives the largest value among vertices; it is confirmed as the true maximum only if the open half-plane ax+by > M shares no point with the feasible region.
Q10LPP applicationhard
A firm makes two products A and B using gold and silver. Each unit of A needs 3 g gold and 1 g silver; each unit of B needs 1 g gold and 2 g silver. Only 9 g gold and 8 g silver are available. Profit is ₹40 per unit of A and ₹50 per unit of B. What is the maximum profit?
Corner points are (0,0), (3,0), (2,3) and (0,4); Z = 40x+50y gives 0, 120, 230 and 200 respectively, so the maximum profit is ₹230 at (2, 3).
Q11Multiple optimal solutionshard
An LPP attains its optimal value of Z at two distinct corner points X and Y of a bounded feasible region. Which statement correctly describes the set of optimal solutions?
When the objective line is parallel to an edge of the feasible region at the optimum, both endpoints of that edge and every point between them give the same optimal value of Z — the LPP has infinitely many optimal solutions.
Q12Corner point methodhard
Maximise Z = 2x + 3y subject to x + y ≤ 6, x ≥ 2, y ≥ 2. What is the maximum value of Z?
The feasible region is the triangle with corner points (2,2), (2,4) and (4,2); Z equals 10, 16 and 14 respectively, so the maximum is 16 at (2, 4).
NCERT solutions & previous-year questions
Step-by-step model answers — tap a question to reveal the full solution.
NCERT questions 6
1Maximise Z = 3x + 4y subject to the constraints x + y ≤ 4, x ≥ 0, y ≥ 0.Corner point method
The constraints x ≥ 0, y ≥ 0 restrict the region to the first quadrant. The line x + y = 4 meets the axes at (4, 0) and (0, 4); since the origin satisfies 0 + 0 ≤ 4, the feasible region is the triangle bounded by the origin and these two intercepts.
Corner points: O(0, 0), A(4, 0), B(0, 4).
Evaluating Z = 3x + 4y:
O(0, 0): Z = 0
A(4, 0): Z = 12
B(0, 4): Z = 16
Since the feasible region is bounded, the maximum of Z is the largest of these values. Hence the maximum value of Z is 16, attained at x = 0, y = 4.
2Minimise Z = −3x + 4y subject to x + 2y ≤ 8, 3x + 2y ≤ 12, x ≥ 0, y ≥ 0.Corner point method
Solving x + 2y = 8 and 3x + 2y = 12 simultaneously: subtracting gives 2x = 4, so x = 2 and y = 3, giving the point (2, 3). The line x + 2y = 8 meets the axes at (8, 0) and (0, 4); (8,0) fails 3x+2y≤12 (24 ≤ 12 is false), so it is not feasible, but (0,4) satisfies 3(0)+2(4)=8≤12, so it is feasible. The line 3x + 2y = 12 meets the axes at (4, 0) and (0, 6); (4,0) satisfies x+2y≤8 (4≤8), so it is feasible, but (0,6) fails x+2y≤8 (12≤8 is false).
The smallest value is −12. Since the region is bounded, the minimum value of Z is −12, attained at x = 4, y = 0.
3Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, y ≥ 0.Corner point method
Solving 3x + 5y = 15 and 5x + 2y = 10 simultaneously: from the second equation, y = (10 − 5x)/2. Substituting, 3x + 5·(10 − 5x)/2 = 15 ⇒ 6x + 50 − 25x = 30 ⇒ −19x = −20 ⇒ x = 20/19, and y = (10 − 100/19)/2 = 45/19. This gives the corner point (20/19, 45/19).
The line 5x + 2y = 10 meets the x-axis at (2, 0); checking against 3x + 5y ≤ 15 gives 6 ≤ 15, true, so (2, 0) is feasible. The line 3x + 5y = 15 meets the y-axis at (0, 3); checking against 5x + 2y ≤ 10 gives 6 ≤ 10, true, so (0, 3) is feasible.
The maximum value of Z is 235/19 (≈ 12.37), attained at x = 20/19, y = 45/19.
4Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, y ≥ 0. Show that the minimum of Z occurs at more than one point.Multiple optimal solutions
Solving 2x + y = 3 and x + 2y = 6 simultaneously: from the first, y = 3 − 2x; substituting, x + 2(3 − 2x) = 6 ⇒ −3x = 0 ⇒ x = 0, y = 3. So the two lines meet at (0, 3).
The line x + 2y = 6 meets the x-axis at (6, 0); this point satisfies 2x + y ≥ 3 since 12 ≥ 3. Since both constraints are '≥' type, the feasible region is unbounded, and its only two finite corner points are (0, 3) and (6, 0).
Evaluating Z = x + 2y: at (0, 3), Z = 6; at (6, 0), Z = 6. Both corner points give the same value.
To confirm this is genuinely the minimum, test the open half-plane x + 2y < 6. This half-plane has no point in common with the feasible region, because the constraint x + 2y ≥ 6 excludes it entirely. Hence Z = 6 is indeed the minimum value, and since it is attained at both corner points of the same boundary edge, it is attained at every point of the line segment joining (0, 3) and (6, 0) — the minimum occurs at more than one point (infinitely many optimal solutions).
5A dietician has to develop a special diet using two foods P and Q. Each packet of food P contains 12 units of calcium, 4 units of iron, 6 units of cholesterol and 6 units of vitamin A, while each packet of food Q contains 3 units of calcium, 20 units of iron, 4 units of cholesterol and 3 units of vitamin A. The diet requires at least 240 units of calcium, at least 460 units of iron and at most 300 units of cholesterol. How many packets of each food should be used to minimise the amount of vitamin A in the diet? What is the minimum amount of vitamin A?Diet problem (minimisation)
Let x = number of packets of food P and y = number of packets of food Q used.
Minimise Z = 6x + 3y (vitamin A) subject to: 12x + 3y ≥ 240, i.e. 4x + y ≥ 80 (calcium) 4x + 20y ≥ 460, i.e. x + 5y ≥ 115 (iron) 6x + 4y ≤ 300, i.e. 3x + 2y ≤ 150 (cholesterol) x ≥ 0, y ≥ 0.
Finding the corner points by solving the boundary lines pairwise:
4x + y = 80 and x + 5y = 115: from the first, y = 80 − 4x; substituting, x + 5(80 − 4x) = 115 ⇒ −19x = −285 ⇒ x = 15, y = 20. Point (15, 20); check 3(15)+2(20) = 85 ≤ 150 ✓.
4x + y = 80 and 3x + 2y = 150: from the first, y = 80 − 4x; substituting, 3x + 2(80 − 4x) = 150 ⇒ −5x = −10 ⇒ x = 2, y = 72. Point (2, 72); check x + 5y = 362 ≥ 115 ✓.
x + 5y = 115 and 3x + 2y = 150: from the first, x = 115 − 5y; substituting, 3(115 − 5y) + 2y = 150 ⇒ −13y = −195 ⇒ y = 15, x = 40. Point (40, 15); check 4(40)+15 = 175 ≥ 80 ✓.
(No axis-intercept of these lines satisfies all three constraints simultaneously, so the feasible region is exactly the triangle with these three corner points.)
Evaluating Z = 6x + 3y:
(2, 72): Z = 12 + 216 = 228
(15, 20): Z = 90 + 60 = 150
(40, 15): Z = 240 + 45 = 285
The smallest value is 150. Hence the dietician should use 15 packets of food P and 20 packets of food Q, giving a minimum vitamin A content of 150 units.
6A manufacturing company makes two types of items, Model A and Model B. Each piece of Model A requires 9 labour hours for fabricating and 1 labour hour for finishing. Each piece of Model B requires 12 labour hours for fabricating and 3 labour hours for finishing. The maximum labour hours available per week for fabricating and finishing are 180 and 30 respectively. The company makes a profit of ₹8,000 on each piece of Model A and ₹12,000 on each piece of Model B. How many pieces of Model A and Model B should be manufactured per week to realise a maximum profit? What is the maximum profit per week?Manufacturing (maximisation)
Let x = number of pieces of Model A and y = number of pieces of Model B made per week.
Maximise Z = 8000x + 12000y subject to: 9x + 12y ≤ 180, i.e. 3x + 4y ≤ 60 (fabricating hours) x + 3y ≤ 30 (finishing hours) x ≥ 0, y ≥ 0.
Solving 3x + 4y = 60 and x + 3y = 30 simultaneously: from the second, x = 30 − 3y; substituting, 3(30 − 3y) + 4y = 60 ⇒ 90 − 5y = 60 ⇒ y = 6, x = 12. Point (12, 6).
The line 3x + 4y = 60 meets the x-axis at (20, 0); checking x + 3y ≤ 30 gives 20 ≤ 30, true, so (20, 0) is feasible. The line x + 3y = 30 meets the y-axis at (0, 10); checking 3x + 4y ≤ 60 gives 40 ≤ 60, true, so (0, 10) is feasible.
The maximum value is 1,68,000, attained at (12, 6). Hence the company should manufacture 12 pieces of Model A and 6 pieces of Model B per week for a maximum profit of ₹1,68,000 per week.
Previous-year board questions 4
Q1A furniture dealer deals in only two items, tables and chairs. He has ₹50,000 to invest and a space to store at most 60 pieces. A table costs him ₹2,500 and a chair ₹500. He estimates that from the sale of one table he can make a profit of ₹250, and from the sale of one chair a profit of ₹75. He wants to know how many tables and chairs he should buy from the available money so as to maximise his total profit, assuming he can sell all the items he buys. Formulate this as an LPP and solve it graphically. 20235 marks
Let x = number of tables and y = number of chairs purchased.
Maximise Z = 250x + 75y subject to: 2500x + 500y ≤ 50000, i.e. 5x + y ≤ 100 (investment) x + y ≤ 60 (storage space) x ≥ 0, y ≥ 0.
Solving 5x + y = 100 and x + y = 60 simultaneously: subtracting gives 4x = 40, so x = 10, y = 50. Point (10, 50).
The line 5x + y = 100 meets the x-axis at (20, 0); checking x + y ≤ 60 gives 20 ≤ 60, true. The line x + y = 60 meets the y-axis at (0, 60); checking 5x + y ≤ 100 gives 60 ≤ 100, true.
The maximum value of Z is 6,250, attained at (10, 50). The dealer should buy 10 tables and 50 chairs to earn a maximum profit of ₹6,250.
Q2The corner points of the feasible region determined by a system of linear inequalities are O(0, 0), A(4, 0), B(2, 4) and C(0, 5). If the objective function is Z = 3x + 4y, find the maximum value of Z and the point at which it is attained. 20222 marks
Evaluate Z = 3x + 4y at each corner point:
O(0, 0): Z = 0
A(4, 0): Z = 12
B(2, 4): Z = 6 + 16 = 22
C(0, 5): Z = 20
The largest value is 22. Since the feasible region is bounded, by the Corner Point Theorem the maximum value of Z is 22, attained at the corner point B(2, 4).
Q3Minimise Z = 200x + 500y subject to x + 2y ≥ 10, 3x + 4y ≤ 24, x ≥ 0, y ≥ 0. 20245 marks
Solving x + 2y = 10 and 3x + 4y = 24 simultaneously: from the first, x = 10 − 2y; substituting, 3(10 − 2y) + 4y = 24 ⇒ 30 − 2y = 24 ⇒ y = 3, x = 4. Point (4, 3).
At x = 0: from x + 2y ≥ 10, y ≥ 5; from 3x + 4y ≤ 24, y ≤ 6. So both (0, 5) and (0, 6) lie on the boundary of the feasible region.
For x > 4 the two inequalities y ≥ (10−x)/2 and y ≤ (24−3x)/4 become incompatible (e.g. at x = 6, the first needs y ≥ 2 but the second needs y ≤ 1.5), confirming the feasible region is the bounded triangle with corner points (0, 5), (0, 6) and (4, 3).
Evaluating Z = 200x + 500y:
(0, 5): Z = 2,500
(0, 6): Z = 3,000
(4, 3): Z = 800 + 1,500 = 2,300
The smallest value is 2,300. Since the feasible region is bounded, the minimum value of Z is 2,300, attained at x = 4, y = 3.
Q4Maximise Z = 4x + y subject to the constraints x + y ≤ 50, 3x + y ≤ 90, x ≥ 0, y ≥ 0. 20215 marks
Solving x + y = 50 and 3x + y = 90 simultaneously: subtracting gives 2x = 40, so x = 20, y = 30. Point (20, 30).
The line 3x + y = 90 meets the x-axis at (30, 0); checking x + y ≤ 50 gives 30 ≤ 50, true. The line x + y = 50 meets the y-axis at (0, 50); checking 3x + y ≤ 90 gives 50 ≤ 90, true.
