Linear Programming · Lesson 4 of 4

Chapter Summary and Practice

“Connect modeling, feasible geometry, vertex calculations, and the different possible optimisation outcomes.”

Learning Objectives

• Build a complete linear programming model from a planning situation. • Connect inequalities, feasible regions, and vertex tables. • Select the correct method for bounded, unbounded, and empty regions. • Recognise unique optima and entire segments of optimal solutions. • Explain results in context and diagnose common reasoning errors.

One chain of reasoning

Linear programming joins two tasks: describing allowed choices and deciding which allowed choice best meets a goal. A good solution makes both tasks visible. The graph shows permission; the objective function ranks the permitted points.

Begin by defining decision variables with units. Translate every limit into a constraint, including non-negative restrictions. Then write the linear objective and state whether to maximise or minimise it. Only after the model is complete should you graph its feasible region.

Idea	Meaning	Question to ask
Decision variables	Quantities we can choose	What do x and y count or measure?
Constraints	Restrictions that all hold together	Which plans are allowed?
Objective	The quantity to optimise	What does a larger or smaller value mean?
Feasible region	Common solution set of the constraints	Is there any overlap? Is it bounded?
Optimal solution	A feasible point attaining the best value	Is the claimed value attainable and unbeatable?

The common objective formLaTeX

Z = a x + b y

The variables are x and y; a and b are fixed contributions per unit; Z measures the chosen goal. Its units follow from the coefficients and variables.

Example — A complete planning problem

Problem
A craft shop can make at most 12 items. A frame requires 2 material units and a stand requires 1; at most 18 units are available. Profits are ₹50 per frame and ₹30 per stand. Find the most profitable plan.

1.Let $x$ count frames and $y$ count stands. Maximise $Z = 50 x + 30 y$ subject to $x + y \leq 12$ , $2 x + y \leq 18$ , and $x, y \geq 0$ .
2.The feasible region is bounded. Its axis vertices are $(0, 0)$ , $(9, 0)$ , and $(0, 12)$ . Subtracting the boundary equations gives $x = 6$ , so the remaining vertex is $(6, 6)$ .
3.The vertex profits are 0, 450, 360, and 480 rupees respectively. The largest value is ₹480 at $(6, 6)$ .
4.Make 6 frames and 6 stands. This uses $6 + 6 = 12$ item places and $2 (6) + 6 = 18$ material units, so the optimal plan satisfies both limits and uses whole numbers.

Use the shape before the table

A table has different force depending on the feasible region. In a nonempty bounded region, the largest and smallest vertex values settle the problem. In an unbounded region, they are candidates requiring an extra check. If there is no common region, there is nothing to evaluate.

Region or objective pattern	Correct action	Possible result
Nonempty and bounded	Evaluate all vertices	A maximum and minimum, possibly shared along an edge
Unbounded with a minimum candidate m	Test the feasible overlap with the strict lower half-plane	Finite minimum or no finite minimum
Unbounded with a maximum candidate M	Test the feasible overlap with the strict upper half-plane	Finite maximum or no finite maximum
No common feasible point	Explain the incompatible constraints	No feasible solution
Two vertices tie at the required optimum	Examine their connecting segment	Every point of that segment is also optimal

The corner-point results depend on linearity and the straight-sided convex feasible regions in this chapter. They are not a general instruction to test a few special points in every optimisation problem. Always check that the model has the structure required by the method.

Example — Read a tied vertex table correctly

Problem
Maximise $Z = 2 x + 2 y$ subject to $x + y \leq 8$ , $x, y \geq 0$ . Describe all optimal solutions.

1.The feasible triangle has vertices $(0, 0)$ , $(8, 0)$ , and $(0, 8)$ . Their objective values are 0, 16, and 16.
2.The region is bounded, so 16 is the maximum. The two nonzero vertices are not the only maximisers.
3.Every point of the joining edge satisfies $x + y = 8$ and therefore $Z = 2 (x + y) = 16$ . All maximum points are $(t, 8 - t)$ for $0 \leq t \leq 8$ .
4.A statement listing only $(8, 0)$ and $(0, 8)$ would miss the interior maximum points, such as $(3, 5)$ .

Existing optima and endlessly improving values

A value is a minimum only if it is reached by a feasible point and no feasible point gives a smaller value. The analogous statement defines a maximum. This wording keeps finite best values separate from directions in which the objective grows or decreases indefinitely.

Example — One region, two different conclusions

Problem
Find the minimum and maximum of $Z = 2 x + y$ subject to $x + y \geq 4$ and $x, y \geq 0$ .

1.The region is unbounded and has vertices $(4, 0)$ and $(0, 4)$ , giving objective values 8 and 4.
2.For any feasible point, $Z = 2 x + y = (x + y) + x \geq 4$ . The feasible point $(0, 4)$ attains 4, so 4 is the minimum.
3.For points $(0, t)$ with $t \geq 4$ , all constraints hold and $Z = t$ . These values increase indefinitely, so there is no finite maximum.
4.The largest vertex value, 8, is not a maximum. For example, the feasible point $(0, 10)$ already gives 10.

Example — Diagnose a model before optimising

Problem
A proposed model requires $x + y \geq 7$ , $2 x + 2 y \leq 10$ , and $x, y \geq 0$ . Can any objective have an optimal feasible solution?

1.Divide the second inequality by 2 to obtain $x + y \leq 5$ .
2.The model simultaneously demands that the same sum be at least 7 and at most 5. These intervals do not overlap.
3.The feasible region is empty. Consequently no objective can have an optimal feasible solution under these constraints.
4.The difficulty is in the restrictions, so choosing another profit or cost function does not solve it. Recheck the assumptions if the model is intended to represent a real situation.

Explain and check your solution

Finish a solution with an interpretation, not an unexplained number. State which point or set of points is optimal, give the objective value, and identify the reason that your comparison is conclusive. When no optimum exists, state whether the cause is incompatibility or unbounded improvement.

Common shortcuts that fail

A point on one boundary may violate another constraint. Using every available resource need not maximise the objective. Two equal vertex values need not be optimal unless they are the required extreme. An unbounded region need not lack a minimum. Rounding a continuous answer need not produce an allowed decision.

Non-negative restrictions include $x = 0$ and $y = 0$ . Their axes become boundary pieces wherever the other inequalities permit those points.

Quick check

A point satisfies three of four constraints. How should it be classified?

Quick check

Which equation represents points with a fixed objective value $k$ for $Z = a x + b y$ ?

Quick check

A bounded feasible polygon has vertex objective values 5, 12, 12, and 8. What can be concluded about maximisation?

Quick check

In an unbounded region, the largest corner value is 20, but a feasible point gives 25. What follows?

Quick check

For $x + y \geq 4$ and $x, y \geq 0$ , what is the minimum of $2 x + y$ ?

Quick check

Why is the model $x + y \geq 7$ , $2 x + 2 y \leq 10$ infeasible?

Quick check

Which statement gives the most complete conclusion for the craft shop example?

Practice Problems

Define decision variable, constraint, objective function, feasible region, vertex, and optimal solution in your own words, connecting the definitions in one example.
Reconstruct the furniture dealer model and solve it from beginning to end without referring to a vertex table.
Maximise $Z = 6 x + 4 y$ subject to $x + y \leq 9$ , $2 x + y \leq 12$ , and $x, y \geq 0$ . Include a labelled graph and an exact vertex table.
Find both extrema of $Z = x + 3 y$ subject to $x + 3 y \leq 12$ and $x, y \geq 0$ . Describe every maximum point.
Minimise $Z = 4 x + 2 y$ subject to $x + y \geq 5$ and $x, y \geq 0$ . Prove that your proposed minimum is unbeatable.
For $Z = - x + 2 y$ under $x \geq 3$ , $x + y \geq 5$ , $x + 2 y \geq 6$ , and $y \geq 0$ , distinguish feasibility from existence of a maximum.
Explain why $x - y \leq - 1$ and $- x + y \leq 0$ cannot hold at the same point. Can changing the objective help?
Two feasible vertices give the same value 18, while another gives 25. Explain what can and cannot be said about the joining segment for maximisation and minimisation.
Create a two-variable model for a shop with a budget and storage limit. Choose numbers for which the best point can be interpreted as whole items, and solve your model.
Draw an unbounded region with a finite minimum and infinitely many minimum points. State an objective and justify the whole optimal set.
For an unbounded region with smallest corner value 7, explain exactly what a common point with $a x + b y < 7$ tells you. Then explain what no such common point tells you.
Audit this claim: “The graph has two lines, so their intersection must be the best point.” List the checks missing from the reasoning.

For $Z = 6 x + 4 y$ , the vertices are $(0, 0)$ , $(6, 0)$ , $(3, 6)$ , and $(0, 9)$ ; the maximum is 42 at $(3, 6)$ . For $Z = x + 3 y \leq 12$ , the minimum is 0 at the origin and the maximum is 12 along the segment from $(12, 0)$ to $(0, 4)$ . For $Z = 4 x + 2 y$ under $x + y \geq 5$ , the minimum is 10 at $(0, 5)$ because $Z = 2 (x + y) + 2 x \geq 10$ .

Key Takeaways

Model first: define variables, restrictions, and the direction of optimisation. Graph the common feasible region before selecting candidate points. For a nonempty bounded region, both extrema are obtained from vertex values. For an unbounded region, test each objective direction beyond the corner table. An optimal edge contains infinitely many best points; an empty region contains no permitted point. Report the decision, its objective value, and the reason the conclusion is valid.

Previous · Lesson 3

Unbounded and Infeasible Problems

End of chapter

One chain of reasoning

Use the shape before the table

Existing optima and endlessly improving values

Explain and check your solution

Quiz

Practice Problems

Key Takeaways