Solution of L.P.P. by graphical methods

Formal definitions related to L.P.P.:

1. Solution of an L.P.P. — a set of values of the decision variables $x_1,x_2,\dots,x_n$ which satisfies the

   conditions of the given L.P.P. is called a solution to that problem.

2. Feasible solution — a solution which satisfies ALL the given constraints (including non-negativity) is called a

   feasible solution.

3. Optimal feasible solution — a feasible solution which maximizes or minimizes the objective function, as required

   by the problem, is called an optimal feasible solution.

4. Feasible region — the region of the plane determined by (common to) ALL the constraints of the L.P.P. is called

   the feasible region.

There are two standard methods to find the solution of an L.P.P.: the Graphical method and the Simplex method;

this chapter restricts itself entirely to the graphical method, which only works conveniently for at most two decision

variables.

Two theorems (stated without proof), the foundation of the graphical method:

• Theorem 1: the set of all feasible solutions of an L.P.P. — the feasible region — is a convex set.
• Theorem 2 (Convex Polygon Theorem): the objective function of an L.P.P. attains its optimum value (maximum or minimum) at (at least) one of the vertices of the convex polygon that is the feasible region.

The Corner-Point Method — five steps:

1. Convert every inequation constraint into its boundary equation.
2. Draw each boundary line in the $X$–$Y$ plane.
3. Locate the region common to all the constraints — this is the feasible region.
4. Find every vertex (corner point) of the feasible region.
5. Evaluate the objective function $z$ at every vertex found; the largest value is the maximum and the smallest is the minimum of $z$ over the whole feasible region.

The reasoning behind step 5 is that the feasible region, being a convex region bounded by straight lines, can be swept by

imagining the line $ax+by=c$ (an "iso-value" line of the objective $z=ax+by$) sliding across the plane as $c$ varies —

the LAST point of the feasible region this sweeping line touches (for a maximum) or the FIRST point it touches (for a

minimum) is always a vertex of the polygon, unless the sweeping line becomes exactly parallel to one whole edge, in which

case every point of that edge is simultaneously optimal.

Solved Example 1 — an ordinary bounded maximum. Maximize $z=9x+13y$ subject to $2x+3y\le18,\ 2x+y\le10,\ x\ge0,\ y\ge0$. Draw $L_1: 2x+3y=18$ (through $(9,0)$ and $(0,6)$) and $L_2: 2x+y=10$ (through $(5,0)$ and $(0,10)$); testing the

origin, both constraints shade their origin side. The feasible region $OABC$ has vertices $O(0,0)$, $A(5,0)$ (on $L_2$),

$B(3,4)$ (solving $L_1$ and $L_2$ together: from $L_2$, $y=10-2x$; substituting into $L_1$, $2x+3(10-2x)=18 \Rightarrow 2x+30-6x=18 \Rightarrow -4x=-12 \Rightarrow x=3,\ y=4$), and $C(0,6)$ (on $L_1$). Evaluating $z$: $z(O)=0$, $z(A)=45$,

$z(B)=9(3)+13(4)=27+52=79$, $z(C)=78$. The maximum value is $z=79$, occurring at $B(3,4)$, i.e. $x=3,\ y=4$.

Solved Example 2 — a mislabelled optimization (the textbook's own worked example, reproduced honestly). The text

states: "Maximize $z=5x+2y$ subject to $5x+y\ge10,\ x+y\ge6,\ x\ge0,\ y\ge0$." Its feasible region has vertices

$A(6,0)$, $B(1,5)$, $C(0,10)$, tabulated as $z(A)=30,\ z(B)=15,\ z(C)=20$. Since BOTH constraints only impose LOWER

($\ge$) bounds with no matching upper cap, this region is actually unbounded toward increasing $x$ and $y$ — for

example, $(x,y)=(100,0)$ still satisfies $5x+y\ge10$ and $x+y\ge6$, giving $z=500$, far larger than any of the three

tabulated vertex values. So if $z$ is genuinely to be MAXIMIZED here, no finite maximum exists at all. What the text's own

working actually computes is the SMALLEST of the three tabulated values, $15$ at $B(1,5)$ — which is exactly what a

MINIMIZATION of the same objective over the same region would give (minimizing over a region that is bounded below, even

though unbounded above, does have a genuine finite optimum at a vertex). This strongly suggests the problem was intended

to read "Minimize," and the printed "maximum value of $z=15$" is very likely a proofreading slip for "minimum value" —

this platform reports both readings rather than silently reproducing a number that does not actually answer the stated

problem: as literally printed (Maximize), the true answer is "unbounded, no finite maximum"; as very likely intended

(Minimize), the answer is $z=15$ at $x=1,\ y=5$, matching the book's own corner-point table.

Solved Example 3 — the unbounded, no-finite-maximum case. Maximize $z=3x+4y$ subject to $x-y\ge0,\ -x+3y\le3,\ x\ge0,\ y\ge0$. Drawing $L_1: x=y$ and $L_2: -x+3y=3$ (through $(0,1)$ and $(-3,0)$), the common shaded region is

unbounded (not a closed polygon) — it opens up indefinitely toward increasing $x$ (and correspondingly increasing $y$,

staying above the line $x=y$). In such a case the iso-value line $3x+4y=c$ can be slid further and further from the

origin, always finding more of the feasible region to cross, so $z$ can be made as large as desired: there is NO finite

maximum value of $z$ within this feasible region. This is the chapter's own explicit demonstration that boundedness of

the feasible region (section 7.1.1's convex-set note (ii), revisited) is not just a technical curiosity but something

that must be checked before declaring any "maximum" answer.

…