Linear Programming: questions with answers

What is to be optimised, and in which direction, is stated by the problem: the firm wants the cost as small as possible, so $Z$ is to be minimised. The direction of the constraint inequalities has nothing to do with it - the chapter minimises $Z = 200x + 500y$ in Example 2 where one constraint is of the $\leq$ type, and maximises $Z$ elsewhere over regions cut out by $\geq$ constraints.

The linear function whose maximum or minimum is being sought is the objective function. Here that function is $Z = 6x + 2y$. The inequalities written under 'subject to' are the constraints, $x$ and $y$ are the decision variables, and a feasible solution is a point of the region those constraints cut out.

The linear inequalities or restrictions on the variables of a linear programming problem are its constraints; $x \geq 0$ and $y \geq 0$ are the non-negative restrictions and are constraints too. The objective function is the single function $Z = 7x + 8y$ being maximised; the feasible region is the region these constraints cut out, not the constraints themselves.

Read the three corner points off the figure and substitute: $Z(A) = 144$, $Z(B) = 141$ and $Z(C) = 90$. The region is bounded, so the largest of these, $144$, is the maximum. $B$ is the vertex furthest from the origin but $141$ is not the largest value, and $90$ answers the opposite question.

Read the three corner points off the figure and substitute: $Z(A) = 126$, $Z(B) = 153$ and $Z(C) = 105$. The region is bounded, so the smallest of these, $105$, is the minimum. $A$ is the vertex nearest the origin but $126$ is not the smallest value, and $153$ answers the opposite question.

Yes. Theorem 2 attaches to the REGION, not to the question: a bounded feasible region gives $Z$ both a maximum and a minimum, each at a corner point. The problem asking only for the maximum changes what has to be reported, not what exists, and the position of the origin is irrelevant.

When the half-planes determined by the constraints have no point in common there is no feasible region, so there is no feasible solution at all and the problem has no solution. There is nothing to evaluate $Z$ at, so reporting a value of $0$, or a value at the origin, invents a solution the problem does not have; and an empty region is not the same thing as an unbounded one.

A feasible region of a system of linear inequalities is bounded if it can be enclosed within a circle; otherwise it is unbounded, meaning it extends indefinitely in some direction. Lying in the first quadrant is not enough - the region $x \geq 0$, $y \geq 0$, $x + y \geq 8$ lies there and runs on for ever - and the direction of the inequality signs settles nothing either.

Every feasible point has $x \geq 0$, $y \geq 0$ and $x + y \leq 20$, so $x$ and $y$ each lie between $0$ and $20$ and the whole region fits inside a circle. The region is therefore bounded, even though one of its constraints is of the $\geq$ type. Boundedness is a property of the region, not of the inequality signs.

The first problem has an empty feasible region: no point satisfies all the constraints, so there is no feasible solution and nothing to optimise. The second has infinitely many feasible solutions - the region is full, it merely runs on for ever - and the failure is only that no feasible point maximises $Z$. Both end with the word 'no', but they fail in different places, and an optimum of $0$ is not on offer in either.

The two tests are independent and they answer differently here. Nothing below the smallest corner value $30$ is feasible, so $30$ is the minimum of $Z$. Something above the largest corner value $140$ IS feasible, so $140$ is beaten and $Z$ has no maximum. An unbounded region neither guarantees an optimum nor forbids one; only the test decides, and it can decide the two extremes differently.

The corner values are $36$, $38$ and $24$, so the smallest is $24$. The region is unbounded, so that value only becomes the minimum once the test is passed - and here it is passed, because the open half plane below it misses the region entirely. So the minimum of $Z$ is $24$; an unbounded region does not automatically mean no optimum.

If $Z$ takes the same value at two corner points, the line $px + qy = Z$ passes through both. So it lies along the edge joining them, parallel to that edge. This is about the slope $-p/q$ matching the slope of the edge, not about $p$ and $q$ being equal. Every point of that edge gives the same optimal value, so the optimal set is far more than the two corners.

Both corners give $Z = 36$. The segment joining them has this value throughout, and $(2, 13)$ lies inside it. The point $(2, 14)$ is off the segment and gives $38$. The origin gives $0$, below the stated minimum, so it is infeasible.

Both corner points give $Z = 116$. When two corner points produce the same maximum value, every point on the line segment joining them gives that same value as well - the objective line lies flush along that edge. A segment contains infinitely many points, so the maximum is attained at infinitely many points, not just at the two vertices the corner-point table happened to list.