Linear Programming | CBSE Class 12 Maths Notes

Linear Programming in Mathematics covers optimisation, decision variables, objective functions, linear constraints, feasible regions, the graphical method, corner-point evaluation, bounded and unbounded regions, multiple optimal solutions and problems with no feasible solution.

What does a linear programming problem ask us to find?

An optimisation problem seeks a best possible outcome, such as maximum profit, minimum cost or minimum use of resources. A linear programming problem is a special kind of optimisation problem in which the objective and the restrictions are linear.

The task has two connected parts: describe the choices allowed by the restrictions, then identify the allowed choice giving the greatest or smallest objective value. A choice that gives an attractive profit but breaks a restriction cannot solve the problem.

What are decision variables and the objective function?

Decision variables represent the quantities to be chosen. Let $x$ and $y$ denote two such quantities. Let $Z$ denote the value to be maximised or minimised, and let $a$ and $b$ denote fixed coefficients.

Definition: A linear objective function has the form $Z=ax+by$. Its optimal value is its maximum or minimum value under the given constraints.

The letters acquire their practical meanings from the problem. In the furniture problem, the variables count tables and chairs, while the objective measures profit. In a purely graphical problem, the variables may simply be the coordinates used to describe the feasible region.

What does linear programming mean?

Linear refers to the linear mathematical relations used in the problem. Programming refers to determining a programme or plan of action. Here the method is graphical: draw the restrictions in two variables, locate their common region and evaluate the objective appropriately.

Constraints are the equations, inequalities or restrictions on the variables. Non-negative restrictions are included among them. An objective function alone does not specify a complete problem: the direction of optimisation and the full set of constraints must also be stated.

How is the furniture dealer's problem formulated?

A furniture dealer has ₹50,000 to invest and space for at most 60 pieces. A table costs ₹2,500 and a chair costs ₹500. The profit is ₹250 per table and ₹75 per chair. Assume that all purchased items can be sold.

Let $x$ be the number of tables purchased and $y$ the number of chairs purchased. Let $Z$ be the total profit in rupees. The dealer wants to choose the purchases that give the greatest profit while respecting both investment and storage limits.

How do the words become inequalities?

1. Step 1: Non-negativity. Numbers of purchased items cannot be negative: $$x\geq0,\qquad y\geq0.$$
2. Step 2: Investment. Multiply each quantity by its purchase price, then compare the total with the available capital: $$2500x+500y\leq50000.$$
3. Step 3: Simplification. Divide the investment inequality by the positive number 500: $$5x+y\leq100.$$
4. Step 4: Storage. Both kinds of furniture occupy places in the total allowance: $$x+y\leq60.$$
5. Step 5: Objective. Add the profits from the two purchases: $$Z=250x+75y.$$ Maximise this expression subject to all four restrictions.

The phrase at most permits using less than the available amount. It therefore produces an inequality rather than a requirement that all capital or all storage must be used. The boundary equation is useful for drawing, but the inequality represents the permitted side.

Formulation must keep purchase costs separate from profits. The prices belong in the investment constraint; the profits belong in the objective function. Exchanging them would describe a different problem even if the resulting graph were drawn correctly.

How do feasible regions and feasible solutions differ?

The feasible region is the common region satisfying every constraint, including non-negativity. Each inequality selects a half-plane. Intersecting all those half-planes gives the set of choices that the problem actually permits.

A feasible solution is a point within or on the boundary of this region. An infeasible solution lies outside it. The distinction concerns all restrictions together: satisfying just the investment condition or just the storage condition is insufficient.

How can a proposed solution be checked?

For the furniture model, check the given feasible point $(10,50)$, where the first coordinate counts tables and the second counts chairs. Also compare the point $(25,40)$, which is infeasible.

1. Step 1: For the first point, the investment expression is $$5(10)+50=100.$$ It satisfies the investment constraint at equality.
2. Step 2: Its storage expression is $$10+50=60.$$ Both coordinates are non-negative, so every restriction is satisfied.
3. Step 3: For the second point, investment requires a bound of 100, but $$5(25)+40=165>100.$$
4. Step 4: Its total number of items is also excessive: $$25+40=65>60.$$ It lies outside the feasible region.

An optimal feasible solution does more than meet the constraints: it gives the required maximum or minimum of the objective. A feasible point may therefore be acceptable without being best. Testing feasibility and testing optimality answer different questions.

What is a corner point?

A corner point, also called a vertex, is the intersection of two boundary lines that belongs to the feasible region. Intersections outside the common region are excluded. The furniture region has four vertices, which will provide a finite set of candidates for maximising profit.

Why can the graphical method focus on corner points?

Let $R$ denote the feasible region. Continue to use $Z=ax+by$, where $Z$ is the objective value, $x$ and $y$ are decision variables, and $a$ and $b$ are constants. Corner-point results connect the region's geometry with optimisation.

Theorem: An existing optimum occurs at a vertex

If the objective has an optimal value on the feasible region, that value occurs at a corner point. This is an existence-conditioned statement. It identifies where an optimum can be found when an optimum exists; it does not guarantee one for every unbounded problem.

Theorem: A bounded feasible region has both extrema

For a non-empty bounded feasible region, the objective has both a maximum and a minimum, each attained at a corner point. A region is bounded if it can be enclosed within a circle. An unbounded region extends indefinitely in some direction.

Result: Equal optimal corner values give multiple optima

If two corner points give the same maximum value, every point on the line segment joining them gives that maximum. The corresponding statement holds for a shared minimum. Thus a corner-point optimum need not be the only optimal solution.

What are the steps of the corner-point method?

1. Locate the region. Graph all constraints and identify their common feasible region, including the coordinate restrictions.
2. Find the vertices. Read obvious intercepts or solve the simultaneous boundary equations. Retain intersections that satisfy all constraints.
3. Evaluate the objective. Calculate its value at every corner. Let $M$ be the largest corner value and $m$ the smallest corner value.
4. Check boundedness. For a bounded feasible region, these are the maximum and minimum. For an unbounded region, perform the additional half-plane test.

For an unbounded region, $M$ is a maximum if the open half-plane $ax+by>M$ has no common point with the feasible region. Similarly, $m$ is a minimum if $ax+by<m$ has no common point with it.

Note: A table of corner values completes a bounded problem. In an unbounded problem, the same table gives candidates whose optimality still needs checking.

How does the dealer obtain the maximum profit?

The furniture model provides a complete example of bounded optimisation. The restrictions on money and storage cut out a finite region in the first quadrant. The two sloping boundaries meet at the purchase combination where both resources are fully used.

Worked example 1. Maximise profit $Z=250x+75y$, where $x$ counts tables and $y$ counts chairs, subject to $5x+y\leq100$, $x+y\leq60$, $x\geq0$ and $y\geq0$.

1. Step 1: Axis vertices. On the horizontal axis, $y=0$, so investment gives $5x\leq100$ and hence $x\leq20$. On the vertical axis, $x=0$, and storage gives $y\leq60$. Include the origin $(0,0)$.
2. Step 2: Boundary intersection. Subtract the storage boundary from the investment boundary: $$(5x+y)-(x+y)=100-60,\qquad4x=40,\qquad x=10.$$
3. Step 3: Second coordinate. Substitute into the storage boundary: $$10+y=60,\qquad y=50.$$ Thus the fourth vertex is $(10,50)$.
4. Step 4: Objective values. At the four corners calculate $$Z(0,0)=0,\qquad Z(20,0)=250(20)+75(0)=5000,$$ $$Z(10,50)=250(10)+75(50)=6250,\qquad Z(0,60)=250(0)+75(60)=4500.$$
5. Step 5: Compare. The region is bounded, and the largest corner value is $6250$, attained at $(10,50)$.

Answer: Buy 10 tables and 50 chairs for a maximum profit of ₹6,250.

The blue feasible region lies in the first quadrant, bounded by the axes and the lines $5x+y=100$ and $x+y=60$. Its labelled non-origin vertices are $(20,0)$, $(10,50)$ and $(0,60)$.

See Fig. 12.1 in your NCERT textbook

How is the purchase plan checked?

1. Step 1: Investment check. $$2500(10)+500(50)=25000+25000=50000.$$
2. Step 2: Storage check. $$10+50=60.$$
3. Step 3: Profit check. $$250(10)+75(50)=2500+3750=6250.$$

The notation $Z(10,50)$ means the objective value obtained by substituting that ordered pair. It does not represent a new restriction. Keeping the coordinates beside each computed value helps connect the arithmetic to the corresponding purchase plan.

The practical answer states both the quantities and the profit. A number alone would omit the investment strategy the dealer needs. Here the optimal plan uses the entire capital and storage allowance, as the final checks confirm.

How is a bounded maximisation problem solved?

A graphical problem may supply its objective and constraints directly. In that case the modelling has already been done, but the reasoning still requires a feasible region, its vertices and a comparison of objective values. The intersection of the sloping lines is not automatically optimal.

Worked example 2. Let $x$ and $y$ be decision variables and $Z$ the objective value. Maximise $Z=4x+y$ subject to $x+y\leq50$, $3x+y\leq90$, $x\geq0$ and $y\geq0$.

1. Step 1: Axis limits. Setting $y=0$ gives the tighter horizontal limit $x=30$. Setting $x=0$ gives the tighter vertical limit $y=50$. The origin satisfies all constraints.
2. Step 2: Intersection. Solve the two boundary equations by subtraction: $$(3x+y)-(x+y)=90-50,\qquad2x=40,\qquad x=20.$$
3. Step 3: Complete the point. $$20+y=50,\qquad y=30.$$ The vertices are $(0,0)$, $(30,0)$, $(20,30)$ and $(0,50)$.
4. Step 4: Evaluate. $$Z(0,0)=0,\qquad Z(30,0)=4(30)+0=120,$$ $$Z(20,30)=4(20)+30=110,\qquad Z(0,50)=4(0)+50=50.$$
5. Step 5: Select. The feasible region is bounded. Its largest corner value is $120$, which occurs at $(30,0)$.

Answer: The maximum value is $Z=120$ at $(30,0)$.

The graph shades the first-quadrant region below both sloping boundaries. It labels the feasible corners $(30,0)$, $(20,30)$ and $(0,50)$, together with the origin.

See Fig. 12.2 in your NCERT textbook

Why does the intersection not win?

The objective attaches different coefficients to the two variables. Although $(20,30)$ lies on both sloping boundaries, its objective value is smaller than the value at $(30,0)$. The objective comparison, rather than the appearance of the graph, decides which corner is best.

Axis intercepts must also be checked against the other inequality. An intercept belonging to one boundary line can lie outside the feasible region. The correct vertex list records the limits permitted by the whole system, not every intercept used while drawing individual lines.

How does minimisation work when inequalities face different ways?

A lower-bound condition and an upper-bound condition can enclose a bounded feasible region together. Do not assume that the origin belongs to every problem in the first quadrant. It must satisfy the original inequalities just as any other candidate point must.

Worked example 3. Let $x$ and $y$ be decision variables and $Z$ the objective value. Minimise $Z=200x+500y$ subject to $x+2y\geq10$, $3x+4y\leq24$, $x\geq0$ and $y\geq0$.

1. Step 1: Vertical vertices. With $x=0$, the inequalities require $y\geq5$ and $y\leq6$. The vertical boundary therefore contributes $(0,5)$ and $(0,6)$.
2. Step 2: Eliminate a variable. Double the first boundary equation to obtain $2x+4y=20$. Subtract this from the second: $$(3x+4y)-(2x+4y)=24-20,\qquad x=4.$$
3. Step 3: Find the intersection. $$4+2y=10,\qquad2y=6,\qquad y=3.$$ The third vertex is $(4,3)$.
4. Step 4: Evaluate each corner. $$Z(0,5)=200(0)+500(5)=2500,$$ $$Z(4,3)=200(4)+500(3)=800+1500=2300,$$ $$Z(0,6)=200(0)+500(6)=3000.$$
5. Step 5: Conclude. The triangular feasible region is bounded. The smallest corner value is $2300$.

Answer: The minimum value is $Z=2300$ at $(4,3)$.

The small shaded triangle has labelled vertices $(0,5)$, $(4,3)$ and $(0,6)$. Its sloping sides lie on $x+2y=10$ and $3x+4y=24$.

See Fig. 12.3 in your NCERT textbook

What does the inequality direction change?

The first constraint selects the side at or above its boundary in this graph, while the second selects the side at or below its boundary. Their common region, together with non-negativity, is the triangle between the three feasible vertices.

The lower bound excludes the origin. Including it would introduce a false objective value smaller than the true minimum. Drawing the selected half-planes and checking the final vertices prevents this error. Minimisation uses the same corner-point framework as maximisation, with the comparison reversed.

How can a problem have more than one optimal solution?

The largest objective value may appear at two corners. This does not mean there are only two optimal solutions. When the corners share the optimum, the segment joining them also shares it. The graph therefore identifies a whole set of equally good choices.

Worked example 4. Let $x$ and $y$ be decision variables and $Z$ the objective value. Minimise and maximise $Z=3x+9y$ subject to $x+3y\leq60$, $x+y\geq10$, $x\leq y$, $x\geq0$ and $y\geq0$.

1. Step 1: Vertical corners. With $x=0$, the active limits give $y=10$ and $y=20$. Call these vertices $A=(0,10)$ and $D=(0,20)$.
2. Step 2: Lower diagonal corner. On the boundary $x=y$, the equation $x+y=10$ becomes $2x=10$. Hence $x=y=5$, giving $B=(5,5)$.
3. Step 3: Upper diagonal corner. On the same boundary, $x+3y=60$ becomes $4x=60$. Hence $x=y=15$, giving $C=(15,15)$.
4. Step 4: Compare values. $$Z(A)=3(0)+9(10)=90,\qquad Z(B)=3(5)+9(5)=60,$$ $$Z(C)=3(15)+9(15)=180,\qquad Z(D)=3(0)+9(20)=180.$$
5. Step 5: Identify the whole maximum set. Along the feasible segment joining $C$ and $D$, $$x+3y=60,\qquad Z=3(x+3y)=3(60)=180.$$

Answer: The minimum is $60$ at $(5,5)$. The maximum is $180$ at every point on the segment from $(15,15)$ to $(0,20)$.

The shaded quadrilateral has vertices $(0,10)$, $(5,5)$, $(15,15)$ and $(0,20)$. The upper sloping side joins the two corners whose objective values are both $180$.

See Fig. 12.4 in your NCERT textbook

What must be stated in the conclusion?

Separate the optimal value from the optimal solutions. The maximum value is a single number, but the coordinate pairs that produce it are multiple. Naming only the two end points would leave out the other optimal points on their joining segment.

The expression for the objective explains the equality directly: it is three times the boundary expression. This calculation confirms the geometric result without checking an endless list of individual points. The segment remains inside the feasible region, so these equal objective values are attainable.

Why does an unbounded region need an extra test?

An unbounded feasible region continues indefinitely. Its vertices provide useful candidate values, but they do not by themselves settle whether a maximum or minimum exists. The objective can take better values farther into the region than those recorded at the corners.

Worked example 5. Let $x$ and $y$ be decision variables and $Z$ the objective value. Minimise $Z=-50x+20y$, subject to $2x-y\geq-5$, $3x+y\geq3$, $2x-3y\leq12$, $x\geq0$ and $y\geq0$.

1. Step 1: Vertical boundary. At $x=0$, the first two inequalities give $y\leq5$ and $y\geq3$. Thus the vertical vertices are $(0,5)$ and $(0,3)$.
2. Step 2: Horizontal boundary. At $y=0$, the second and third inequalities give $x\geq1$ and $x\leq6$. Thus the horizontal vertices are $(1,0)$ and $(6,0)$.
3. Step 3: Corner values. $$Z(0,5)=-50(0)+20(5)=100,\qquad Z(0,3)=-50(0)+20(3)=60,$$ $$Z(1,0)=-50(1)+20(0)=-50,\qquad Z(6,0)=-50(6)+20(0)=-300.$$
4. Step 4: Test the candidate. The region is unbounded, so draw the open half-plane $$-50x+20y<-300,\qquad -5x+2y<-30.$$ This half-plane has points in common with the feasible region.
5. Step 5: Decide. The extra test rejects $-300$ as a minimum. The objective has no minimum value under the stated constraints.

Answer: There is no minimum value; $-300$ is only the smallest value among the corners.

What does the graph test establish?

The test asks whether feasible points can lie on the side giving a value strictly smaller than the candidate. The strict inequality matters: points on the equal-value line do not improve the objective. The open half-plane represents values beyond that line.

The blue region extends to the right beyond the four labelled corners. A dashed line labelled $-5x+2y=-30$ passes through the region, illustrating the extra test for the candidate minimum.

See Fig. 12.5 in your NCERT textbook

Unbounded region and no minimum are not interchangeable statements. Some unbounded problems do have a minimum. The absence of a minimum here follows from the additional test for this objective and these constraints, not from the word unbounded alone.

What happens when the constraints have no common region?

A linear programming problem may have no feasible solution. This means there is no point satisfying all the restrictions simultaneously. Calculating objective values at selected boundary intersections cannot repair that failure, because the proposed choices are not permitted by the complete system.

Worked example 6. Let $x$ and $y$ be decision variables and $Z$ the objective value. Minimise $Z=3x+2y$, subject to $x+y\geq8$, $3x+5y\leq15$, $x\geq0$ and $y\geq0$.

1. Step 1: First boundary. The line $x+y=8$ meets the axes at $(8,0)$ and $(0,8)$. Select the half-plane satisfying the greater-than-or-equal restriction.
2. Step 2: Second boundary. The line $3x+5y=15$ meets the axes at $(5,0)$ and $(0,3)$. Select the half-plane satisfying the less-than-or-equal restriction.
3. Step 3: Algebraic check. From $x+y\geq8$ and $y\geq0$, obtain $$3x+5y=3(x+y)+2y\geq24.$$
4. Step 4: Contradiction. The same expression is required to be at most 15. Since $24>15$, no point can satisfy both requirements.

Answer: There is no feasible or optimal solution: the constraints would require the same expression to be at least $24$ and at most $15$.

How is infeasibility different from an unbounded objective?

In the preceding unbounded example, feasible points existed but there was no minimum. Here feasibility fails first. The distinction is essential: one conclusion concerns how the objective behaves on an existing region; the other concerns the absence of that region.

The graph labels the intercepts $(0,8)$, $(8,0)$, $(0,3)$ and $(5,0)$. The selected regions for the two sloping boundaries do not overlap in the first quadrant.

See Fig. 12.6 in your NCERT textbook

How do further examples bring the method together?

The same procedure handles a simple triangular region and an unbounded region with multiple minima. These cases help separate the shape of the feasible set from the behaviour of the objective. First identify the region; then apply the appropriate optimisation argument.

How is a single-constraint maximum found?

Worked example 7. Let $x$ and $y$ be decision variables and $Z$ the objective value. Maximise $Z=3x+4y$, subject to $x+y\leq4$, $x\geq0$ and $y\geq0$.

1. Step 1: Draw the boundary. The equation $x+y=4$ has intercepts $(4,0)$ and $(0,4)$.
2. Step 2: Select the region. Together with non-negativity, the inequality gives the bounded triangle with vertices $(0,0)$, $(4,0)$ and $(0,4)$.
3. Step 3: Evaluate. $$Z(0,0)=0,\qquad Z(4,0)=3(4)+4(0)=12,\qquad Z(0,4)=3(0)+4(4)=16.$$
4. Step 4: Compare. The largest corner value is $16$, so it is the maximum on the bounded region.

Answer: The maximum is $Z=16$ at $(0,4)$.

Can an unbounded region have multiple minima?

Worked example 8. Let $x$ and $y$ be decision variables and $Z$ the objective value. Minimise $Z=x+2y$, subject to $2x+y\geq3$, $x+2y\geq6$, $x\geq0$ and $y\geq0$. Show that more than two points give the minimum.

1. Step 1: Identify a lower bound. One constraint is already the objective expression: $$Z=x+2y\geq6.$$ Therefore no feasible point can give a smaller value.
2. Step 2: Locate the equal-value segment. The line $x+2y=6$ meets the axes at $(0,3)$ and $(6,0)$. On the segment between these points, $$y=3-\frac{x}{2},\qquad0\leq x\leq6.$$
3. Step 3: Check the other constraint. Substitution along this segment gives $$2x+y=2x+3-\frac{x}{2}=3+\frac{3x}{2}\geq3.$$ Both coordinates are non-negative there.
4. Step 4: Evaluate the whole segment. $$Z=x+2\left(3-\frac{x}{2}\right)=6.$$ The lower bound is attained at every point of the segment.

Answer: The minimum is $6$, attained throughout the segment from $(0,3)$ to $(6,0)$, giving more than two optimal points.

The final example also completes the open-half-plane test directly. The condition $x+2y<6$ cannot share a point with the feasible region, because it contradicts one of the original constraints. Thus the unbounded region has an attained minimum.

Glossary

• Linear programming problem — A problem optimising a linear objective while satisfying linear constraints and non-negative restrictions.
• Optimisation — Finding a maximum or minimum value while respecting the restrictions imposed on the choices.
• Decision variables — Quantities whose values are chosen to determine a feasible plan and its objective value.
• Objective function — The linear function whose maximum or minimum value is required under the given constraints.
• Constraints — Equations, inequalities or restrictions that the variables of a linear programming problem must satisfy.
• Non-negative restrictions — Conditions requiring the decision variables to be zero or positive rather than negative.
• Feasible region — The common region satisfying every constraint, including the restrictions that variables are non-negative.
• Feasible solution — A point within or on the boundary of the region satisfying all constraints.
• Infeasible solution — A point outside the feasible region because it fails to satisfy the full constraint system.
• Optimal solution — A feasible point giving the required maximum or minimum value of the objective function.
• Corner point — A vertex in the feasible region formed by the intersection of two boundary lines.
• Bounded region — A feasible region that can be enclosed completely within a circle.
• Unbounded region — A feasible region that extends indefinitely and cannot be enclosed within a circle.
• Multiple optimal solutions — More than one feasible point giving the same required maximum or minimum objective value.

Common errors and misconceptions

• Misconception: Any point satisfying one inequality is feasible. Correct: A feasible point must satisfy every constraint, including non-negativity.
• Misconception: Only points strictly inside the region are feasible. Correct: Points on its included boundaries are feasible too.
• Misconception: The intersection of the sloping boundaries must be optimal. Correct: Evaluate the objective at all feasible corners before comparing values.
• Misconception: An unbounded region cannot have a minimum. Correct: A minimum may exist; test whether any feasible point lies in the improving open half-plane.
• Misconception: The smallest corner value proves a minimum in every problem. Correct: An unbounded region requires the additional half-plane check.
• Misconception: Two equally optimal corners mean exactly two optimal solutions. Correct: Every point on their joining segment gives the same optimum.
• Misconception: An empty feasible region means the objective value is zero. Correct: It means no feasible solution exists, so there is no optimal solution.

Exam-style questions with model answers

Q1. Distinguish a feasible solution from an optimal solution in linear programming. [2 marks]

1. A feasible solution is any point within or on the boundary of the region satisfying all constraints.
2. An optimal solution is a feasible point that also gives the required maximum or minimum value of the objective function.

Q2. A dealer has ₹50,000 and storage for 60 pieces. Tables cost ₹2,500 each and chairs ₹500 each. Profits are ₹250 and ₹75 respectively, and all purchases can be sold. Formulate the profit-maximisation problem. [3 marks]

1. Let $x$ count tables, $y$ count chairs and $Z$ represent profit in rupees. The quantities cannot be negative, so $x\geq0$ and $y\geq0$.
2. The purchase expenditure cannot exceed the investment: $2500x+500y\leq50000$, or $5x+y\leq100$.
3. The combined storage requirement gives $x+y\leq60$. Total profit is $Z=250x+75y$. Maximise this function subject to the investment, storage and non-negative constraints together.

Q3. Maximise $Z=4x+y$ subject to $x+y\leq50$, $3x+y\leq90$, $x\geq0$ and $y\geq0$, where $x,y$ are decision variables and $Z$ is the objective value. Show the corner-point calculations. [5 marks]

1. The non-negative constraints restrict the region to the first quadrant. On the horizontal axis, the tighter bound is $x=30$; on the vertical axis it is $y=50$. The origin is also feasible.
2. Subtract the boundary equations: $(3x+y)-(x+y)=90-50$, so $2x=40$ and $x=20$. Then $y=50-20=30$.
3. The common region is bounded, with vertices $(0,0)$, $(30,0)$, $(20,30)$ and $(0,50)$.
4. Evaluate the objective at each: $Z(0,0)=0$, $Z(30,0)=4(30)+0=120$, $Z(20,30)=4(20)+30=110$ and $Z(0,50)=4(0)+50=50$.
5. The largest of these values is $120$. The bounded-region theorem therefore gives a maximum of $120$ at $(30,0)$. Both the optimum and the point producing it are required in the conclusion.

Q4. Minimise $Z=200x+500y$ subject to $x+2y\geq10$, $3x+4y\leq24$, $x\geq0$ and $y\geq0$, where $x,y$ are decision variables and $Z$ is the objective value. [4 marks]

1. On the vertical axis the constraints give vertices $(0,5)$ and $(0,6)$. For the sloping-line intersection, double $x+2y=10$, giving $2x+4y=20$.
2. Subtract from $3x+4y=24$ to obtain $x=4$. Substitution gives $4+2y=10$, so $y=3$.
3. The bounded triangular region has corners $(0,5)$, $(4,3)$ and $(0,6)$. Their objective values are $2500$, $800+1500=2300$ and $3000$, respectively.
4. The minimum is therefore $2300$ at $(4,3)$.

Q5. A bounded feasible region has vertices $(0,10)$, $(5,5)$, $(15,15)$ and $(0,20)$. Find the minimum and maximum of $Z=3x+9y$, where $x,y$ are coordinates and $Z$ is the objective value. Describe all maximum solutions. [4 marks]

1. Evaluate the objective at the vertices: $Z(0,10)=90$, $Z(5,5)=15+45=60$, $Z(15,15)=45+135=180$ and $Z(0,20)=180$.
2. Because the region is bounded, the smallest and largest corner values are the extrema. The minimum is $60$ at $(5,5)$.
3. The maximum is $180$. Both $(15,15)$ and $(0,20)$ attain it.
4. Every point on their joining segment is also optimal. Along that segment, $x+3y=60$, giving $Z=3(x+3y)=180$.

Q6. Explain why the problem of minimising $Z=3x+2y$ subject to $x+y\geq8$, $3x+5y\leq15$, $x\geq0$ and $y\geq0$ has no feasible solution. Here $x,y$ are decision variables and $Z$ is the objective value. [3 marks]

1. Begin with the lower bound $x+y\geq8$. Multiplying by three gives $3(x+y)\geq24$.
2. Since $y\geq0$, adding $2y$ cannot decrease that expression. Thus $3x+5y=3(x+y)+2y\geq24$.
3. This contradicts the required upper bound $3x+5y\leq15$. No coordinate pair can satisfy the constraints simultaneously. Hence the common feasible region is empty, and there is no feasible solution or minimum objective value.

Key takeaways

• A linear programming problem optimises a linear objective subject to linear constraints and non-negative restrictions on its decision variables.
• The feasible region is the common part of all constraint regions, including its permitted boundary points.
• For a non-empty bounded feasible region, both extrema exist and can be found by comparing objective values at its corners.
• In an unbounded region, candidate corner values require an additional open-half-plane test before an optimum can be claimed.
• If two corners share an optimal value, every point on the segment joining them shares that value.
• No common feasible region means no feasible solution, which differs from an existing region with an unbounded objective.
• In a practical problem, report both the optimal decision-variable values and the resulting objective value with its meaning.

Test yourself

What does the word programming mean in this chapter?

It means determining a particular programme or plan of action under the given restrictions.

Must a feasible solution lie strictly inside the feasible region?

No. Points on the boundary also represent feasible solutions when they satisfy every constraint.

How is a bounded feasible region defined?

It is a feasible region that can be enclosed within a circle.

Why is the largest corner value insufficient in an unbounded maximisation problem?

Other feasible points may give larger values. Check the open half-plane where the objective exceeds that candidate.

What follows if two corners give the same minimum value?

Every point on the line segment joining those corners gives the same minimum value.

What is the first conclusion when all constraint half-planes have no common point?

The problem has no feasible region and therefore no feasible solution.

Can an unbounded feasible region still have an attained minimum?

Yes. A minimum can exist if the open half-plane giving smaller objective values contains no feasible points.