Chapter 12: Linear Programming

We have to maximise $$Z = 4x + y$$ subject to $$x + y \le 50$$, $$3x + y \le 90$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Draw the constraint lines. The line $$x + y = 50$$ passes through $$(50, 0)$$ and $$(0, 50)$$. The line $$3x + y = 90$$ passes through $$(30, 0)$$ and $$(0, 90)$$.

Step 2 — Identify the feasible region. Testing the origin: $$0 + 0 = 0 \le 50$$ and $$3(0) + 0 = 0 \le 90$$, so both inequalities are satisfied at $$(0,0)$$. Hence each region lies on the origin side of its line. Together with $$x \ge 0$$ and $$y \ge 0$$, the feasible region is the bounded quadrilateral $$OABC$$ lying in the first quadrant.

Step 3 — Find the corner points.

• $$O = (0, 0)$$ — the origin, intersection of the two coordinate axes.
• $$A = (30, 0)$$ — where $$3x + y = 90$$ cuts the $$x$$-axis. (Note that $$30 \lt 50$$, so the binding constraint along the $$x$$-axis is $$3x + y \le 90$$, not $$x + y \le 50$$.)
• $$B = (20, 30)$$ — the intersection of the lines $$x + y = 50$$ and $$3x + y = 90$$. We solve this system explicitly.

  The two equations are

  $$x + y = 50 \quad \cdots (1)$$
  $$3x + y = 90 \quad \cdots (2)$$

  Subtracting (1) from (2) eliminates $$y$$:

  $$(3x + y) - (x + y) = 90 - 50$$
  $$2x = 40$$
  $$x = 20.$$

  Substituting $$x = 20$$ back into equation (1):

  $$20 + y = 50 \;\Longrightarrow\; y = 30.$$

  Hence $$B = (20, 30)$$.

• $$C = (0, 50)$$ — where $$x + y = 50$$ cuts the $$y$$-axis.

Step 4 — Evaluate $$Z = 4x + y$$ at each corner.

The largest value of $$Z$$ is $$120$$, occurring at $$A(30, 0)$$.

Hence the maximum value of $$Z$$ is $$120$$, attained at $$x = 30$$, $$y = 0$$.

We have to minimise $$Z = 200x + 500y$$ subject to $$x + 2y \ge 10$$, $$3x + 4y \le 24$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Draw the constraint lines. The line $$x + 2y = 10$$ passes through $$(10, 0)$$ and $$(0, 5)$$. The line $$3x + 4y = 24$$ passes through $$(8, 0)$$ and $$(0, 6)$$.

Step 2 — Identify the feasible region. At the origin, $$0 + 0 = 0 \ge 10$$ is false, so $$x + 2y \ge 10$$ holds on the side of its line away from the origin. Also $$3(0) + 4(0) = 0 \le 24$$ is true, so $$3x + 4y \le 24$$ holds on the origin side. The feasible region is the bounded triangle $$ABC$$.

Step 3 — Find the corner points.

• $$A = (0, 5)$$: where $$x + 2y = 10$$ meets the y-axis (check $$3(0) + 4(5) = 20 \le 24$$, valid).
• $$B = (4, 3)$$: intersection of $$x + 2y = 10$$ and $$3x + 4y = 24$$. From the first, $$x = 10 - 2y$$; substituting, $$3(10 - 2y) + 4y = 24 \Rightarrow 30 - 2y = 24 \Rightarrow y = 3$$, so $$x = 10 - 6 = 4$$.
• $$C = (0, 6)$$: where $$3x + 4y = 24$$ meets the y-axis (check $$0 + 2(6) = 12 \ge 10$$, valid).

Step 4 — Evaluate $$Z = 200x + 500y$$ at each corner.

The smallest value of $$Z$$ is $$2300$$, occurring at $$B(4, 3)$$. As the feasible region is bounded, this is indeed the minimum.

Hence the minimum value of $$Z$$ is $$2300$$, attained at $$x = 4$$, $$y = 3$$.

We have to minimise and maximise $$Z = 3x + 9y$$ subject to $$x + 3y \le 60$$, $$x + y \ge 10$$, $$x \le y$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Draw the constraint lines. The line $$x + 3y = 60$$ passes through $$(60, 0)$$ and $$(0, 20)$$; the line $$x + y = 10$$ passes through $$(10, 0)$$ and $$(0, 10)$$; the line $$x = y$$ passes through the origin with slope $$1$$.

Step 2 — Identify the feasible region. $$x + 3y \le 60$$ holds on the origin side ($$0 \le 60$$); $$x + y \ge 10$$ holds away from the origin ($$0 \ge 10$$ is false); $$x \le y$$ holds above the line $$x = y$$ (e.g. $$(0, 10)$$ gives $$0 \le 10$$). The feasible region is the bounded quadrilateral $$ABCD$$.

Step 3 — Find the corner points.

• $$A = (0, 10)$$: intersection of $$x = 0$$ and $$x + y = 10$$.
• $$B = (5, 5)$$: intersection of $$x + y = 10$$ and $$x = y$$. Then $$2x = 10 \Rightarrow x = y = 5$$.
• $$C = (15, 15)$$: intersection of $$x + 3y = 60$$ and $$x = y$$. Then $$y + 3y = 60 \Rightarrow 4y = 60 \Rightarrow y = 15$$, so $$x = 15$$.
• $$D = (0, 20)$$: intersection of $$x = 0$$ and $$x + 3y = 60$$.

Step 4 — Evaluate $$Z = 3x + 9y$$ at each corner.

The minimum value of $$Z$$ is $$60$$, attained at $$B(5, 5)$$.

The maximum value $$180$$ is attained at two corner points, $$C(15, 15)$$ and $$D(0, 20)$$. When the maximum occurs at two corners, it also occurs at every point of the line segment joining them. Hence $$Z$$ is maximum ($$= 180$$) at every point of the segment joining $$(15, 15)$$ and $$(0, 20)$$.

We have to find the minimum value of $$Z = -50x + 20y$$ subject to $$2x - y \ge -5$$, $$3x + y \ge 3$$, $$2x - 3y \le 12$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Draw the constraint lines. Replacing each inequality by an equality gives the boundary lines, whose intercepts are listed below.

• $$2x - y = -5$$ passes through $$(-2.5, 0)$$ and $$(0, 5)$$;
• $$3x + y = 3$$ passes through $$(1, 0)$$ and $$(0, 3)$$;
• $$2x - 3y = 12$$ passes through $$(6, 0)$$ and $$(0, -4)$$.

Step 2 — Identify the feasible region. Test the origin in each inequality:

• $$2(0) - 0 = 0 \ge -5$$ (true), so $$2x - y \ge -5$$ holds on the origin side of its line;
• $$3(0) + 0 = 0 \ge 3$$ (false), so $$3x + y \ge 3$$ holds on the side away from the origin;
• $$2(0) - 3(0) = 0 \le 12$$ (true), so $$2x - 3y \le 12$$ holds on the origin side.

Together with $$x \ge 0$$ and $$y \ge 0$$, we restrict to the first quadrant. The common region satisfying all five constraints is unbounded; it extends indefinitely in the positive $$x$$-direction.

Step 3 — Find the corner points of the feasible region.

• $$(0, 5)$$: where $$2x - y = -5$$ meets the $$y$$-axis.
• $$(0, 3)$$: where $$3x + y = 3$$ meets the $$y$$-axis.
• $$(1, 0)$$: where $$3x + y = 3$$ meets the $$x$$-axis.
• $$(6, 0)$$: where $$2x - 3y = 12$$ meets the $$x$$-axis.

Step 4 — Evaluate $$Z = -50x + 20y$$ at each corner.

The smallest value among the corner points is $$-300$$, at $$(6, 0)$$.

Step 5 — Test whether $$-300$$ is really the minimum. Because the feasible region is unbounded, the smallest corner value need not be the global minimum. The standard rule is to check whether the open half-plane

$$-50x + 20y \lt -300$$

has any point in common with the feasible region. If it does, then $$Z$$ has no minimum on the region; if it does not, then $$-300$$ is the minimum.

Take the test point $$(7, 1)$$ and verify that it satisfies every constraint:

• $$2(7) - 1 = 13 \ge -5$$;
• $$3(7) + 1 = 22 \ge 3$$;
• $$2(7) - 3(1) = 11 \le 12$$;
• $$x = 7 \ge 0$$ and $$y = 1 \ge 0$$.

Hence $$(7, 1)$$ is feasible, and at this point

$$Z(7, 1) = -50(7) + 20(1) = -350 + 20 = -330 \lt -300.$$

So the open half-plane $$-50x + 20y \lt -300$$ does meet the feasible region, which means $$-300$$ is not the minimum value of $$Z$$.

In fact, starting from $$(6, 0)$$ and moving along the boundary line $$2x - 3y = 12$$ via the parametrisation $$(x, y) = (6 + 3t,\ 2t)$$, $$t \ge 0$$, each such point stays in the feasible region (every other constraint is satisfied with slack), and

$$Z(t) = -50(6 + 3t) + 20(2t) = -300 - 110t \;\longrightarrow\; -\infty \quad \text{as } t \to \infty.$$

Therefore $$Z$$ can be made smaller than any prescribed real number while remaining feasible.

Conclusion. The objective function $$Z = -50x + 20y$$ has no minimum value on the given feasible region.

We have to minimise $$Z = 3x + 2y$$ subject to $$x + y \ge 8$$, $$3x + 5y \le 15$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Draw the constraint lines. The line $$x + y = 8$$ passes through $$(8, 0)$$ and $$(0, 8)$$. The line $$3x + 5y = 15$$ passes through $$(5, 0)$$ and $$(0, 3)$$.

Step 2 — Identify the regions. The inequality $$x + y \ge 8$$ is satisfied on the side of $$x + y = 8$$ away from the origin (since $$0 \ge 8$$ is false). The inequality $$3x + 5y \le 15$$ is satisfied on the side of $$3x + 5y = 15$$ towards the origin (since $$0 \le 15$$ is true).

Step 3 — Look for a common region. With $$x, y \ge 0$$, every point of the region $$3x + 5y \le 15$$ lies inside the small triangle with vertices $$(0, 0)$$, $$(5, 0)$$, $$(0, 3)$$, and all such points satisfy $$x + y \le 5$$. But the region $$x + y \ge 8$$ requires $$x + y \ge 8$$. Since $$x + y \le 5$$ and $$x + y \ge 8$$ cannot hold together, the two regions do not overlap.

There is no point satisfying all the constraints simultaneously. Hence the feasible region is empty and the problem has no feasible solution (so $$Z$$ has no minimum value).

We maximise $$Z = 3x + 4y$$ subject to $$x + y \le 4$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Feasible region. The line $$x + y = 4$$ passes through $$(4, 0)$$ and $$(0, 4)$$. At the origin, $$0 + 0 = 0 \le 4$$ is true, so $$x + y \le 4$$ holds on the origin side. Together with $$x \ge 0$$ and $$y \ge 0$$, the feasible region is the bounded triangle $$OAB$$ with vertices $$O(0, 0)$$, $$A(4, 0)$$ and $$B(0, 4)$$.

Step 2 — Evaluate $$Z = 3x + 4y$$ at the corner points.

The greatest value is $$16$$, attained at $$B(0, 4)$$.

Hence the maximum value of $$Z$$ is $$16$$, at $$x = 0$$, $$y = 4$$.

We minimise $$Z = -3x + 4y$$ subject to $$x + 2y \le 8$$, $$3x + 2y \le 12$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Feasible region. The line $$x + 2y = 8$$ passes through $$(8, 0)$$ and $$(0, 4)$$; the line $$3x + 2y = 12$$ passes through $$(4, 0)$$ and $$(0, 6)$$. At the origin both inequalities hold ($$0 \le 8$$, $$0 \le 12$$), so each region is on the origin side. The feasible region is the bounded quadrilateral $$OABC$$.

Step 2 — Corner points.

• $$O = (0, 0)$$.
• $$A = (4, 0)$$: where $$3x + 2y = 12$$ meets the x-axis.
• $$B = (2, 3)$$: intersection of $$x + 2y = 8$$ and $$3x + 2y = 12$$. Subtracting the first from the second: $$2x = 4 \Rightarrow x = 2$$, then $$2 + 2y = 8 \Rightarrow y = 3$$.
• $$C = (0, 4)$$: where $$x + 2y = 8$$ meets the y-axis.

Step 3 — Evaluate $$Z = -3x + 4y$$ at each corner.

The smallest value is $$-12$$, attained at $$A(4, 0)$$.

Hence the minimum value of $$Z$$ is $$-12$$, at $$x = 4$$, $$y = 0$$.

We maximise $$Z = 5x + 3y$$ subject to $$3x + 5y \le 15$$, $$5x + 2y \le 10$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Feasible region. The line $$3x + 5y = 15$$ passes through $$(5, 0)$$ and $$(0, 3)$$; the line $$5x + 2y = 10$$ passes through $$(2, 0)$$ and $$(0, 5)$$. The origin satisfies both inequalities, so each region is on the origin side. The feasible region is the bounded quadrilateral $$OABC$$.

Step 2 — Corner points.

• $$O = (0, 0)$$.
• $$A = (2, 0)$$: where $$5x + 2y = 10$$ meets the x-axis.
• $$B = \left(\dfrac{20}{19}, \dfrac{45}{19}\right)$$: intersection of $$3x + 5y = 15$$ and $$5x + 2y = 10$$. Multiplying the first equation by $$2$$ and the second by $$5$$ gives $$6x + 10y = 30$$ and $$25x + 10y = 50$$. Subtracting: $$19x = 20 \Rightarrow x = \dfrac{20}{19}$$. Then $$5 \cdot \dfrac{20}{19} + 2y = 10 \Rightarrow 2y = 10 - \dfrac{100}{19} = \dfrac{90}{19} \Rightarrow y = \dfrac{45}{19}$$.
• $$C = (0, 3)$$: where $$3x + 5y = 15$$ meets the y-axis.

Step 3 — Evaluate $$Z = 5x + 3y$$ at each corner.

The greatest value is $$\dfrac{235}{19}$$, attained at $$B\left(\dfrac{20}{19}, \dfrac{45}{19}\right)$$.

Hence the maximum value of $$Z$$ is $$\dfrac{235}{19}$$ (about $$12.37$$), at $$x = \dfrac{20}{19}$$, $$y = \dfrac{45}{19}$$.

We minimise $$Z = 3x + 5y$$ subject to $$x + 3y \ge 3$$, $$x + y \ge 2$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Feasible region. The line $$x + 3y = 3$$ passes through $$(3, 0)$$ and $$(0, 1)$$; the line $$x + y = 2$$ passes through $$(2, 0)$$ and $$(0, 2)$$. At the origin, $$0 \ge 3$$ and $$0 \ge 2$$ are both false, so each region lies away from the origin. The feasible region is unbounded.

Step 2 — Corner points.

• $$A = (3, 0)$$: where $$x + 3y = 3$$ meets the x-axis (check $$x + y = 3 \ge 2$$, valid).
• $$B = \left(\dfrac{3}{2}, \dfrac{1}{2}\right)$$: intersection of $$x + 3y = 3$$ and $$x + y = 2$$. Subtracting the second from the first: $$2y = 1 \Rightarrow y = \dfrac{1}{2}$$, then $$x = 2 - \dfrac{1}{2} = \dfrac{3}{2}$$.
• $$C = (0, 2)$$: where $$x + y = 2$$ meets the y-axis (check $$x + 3y = 6 \ge 3$$, valid).

Step 3 — Evaluate $$Z = 3x + 5y$$ at each corner.

The smallest corner value is $$7$$ at $$B\left(\dfrac{3}{2}, \dfrac{1}{2}\right)$$. Since the region is unbounded, we check whether the open half-plane $$3x + 5y < 7$$ has any point in common with the feasible region. It has none — every feasible point gives $$3x + 5y \ge 7$$.

Hence the minimum value of $$Z$$ is $$7$$, at $$x = \dfrac{3}{2}$$, $$y = \dfrac{1}{2}$$.

We maximise $$Z = 3x + 2y$$ subject to $$x + 2y \le 10$$, $$3x + y \le 15$$, $$x \ge 0$$ and $$y \ge 0$$.

Step 1 — Feasible region. The line $$x + 2y = 10$$ passes through $$(10, 0)$$ and $$(0, 5)$$; the line $$3x + y = 15$$ passes through $$(5, 0)$$ and $$(0, 15)$$. The origin satisfies both inequalities, so each region is on the origin side. The feasible region is the bounded quadrilateral $$OABC$$.

Step 2 — Corner points.

• $$O = (0, 0)$$.
• $$A = (5, 0)$$: where $$3x + y = 15$$ meets the x-axis.
• $$B = (4, 3)$$: intersection of $$x + 2y = 10$$ and $$3x + y = 15$$. From the second, $$y = 15 - 3x$$; substituting, $$x + 2(15 - 3x) = 10 \Rightarrow x + 30 - 6x = 10 \Rightarrow -5x = -20 \Rightarrow x = 4$$, then $$y = 15 - 12 = 3$$.
• $$C = (0, 5)$$: where $$x + 2y = 10$$ meets the y-axis.

Step 3 — Evaluate $$Z = 3x + 2y$$ at each corner.

The greatest value is $$18$$, attained at $$B(4, 3)$$.

Hence the maximum value of $$Z$$ is $$18$$, at $$x = 4$$, $$y = 3$$.

Step 1 : Draw the lines corresponding to the constraints

Convert each inequality into an equality.

• $$2x+y=3\quad\Rightarrow\quad\text{Line }L_1$$
• $$x+2y=6\quad\Rightarrow\quad\text{Line }L_2$$
• The coordinate axes $$x=0$$ and $$y=0$$ give the first-quadrant restriction $$x\ge 0,\;y\ge 0$$.

Intercepts of the two lines

Thus both lines pass through the common point $$(0,3)$$.

Step 2 : Identify the feasible half-planes

Take the test point $$(0,0)$$ (the origin).

• For $$2x+y\ge 3$$ : $$2(0)+0=0<3\;\Rightarrow\;(0,0)$$ does not satisfy. Hence the required half-plane for $$L_1$$ is the side away from the origin.
• For $$x+2y\ge 6$$ : $$0+0=0<6\;\Rightarrow\;(0,0)$$ again fails. Hence the half-plane for $$L_2$$ is also the side away from the origin.

Since $$x, y\ge 0$$ we restrict ourselves to the first quadrant. The common region that satisfies all inequalities is the shaded region bounded below by the two lines and extending indefinitely to the north-east. (Draw the two lines, shade the region that is simultaneously above both lines and in the first quadrant.)

Step 3 : Corner (extreme) points of the feasible region

The region is unbounded, but the two boundary lines together with the axes give the following corner points:

• $$A(0,3)$$ – intersection of $$L_1$$ and $$L_2$$ (and the $$y$$-axis)
• $$B(6,0)$$ – intersection of $$L_2$$ with the $$x$$-axis

(No other corner point arises, because $$L_1$$ meets the $$x$$-axis at $$(1.5,0)$$, but this point does not satisfy $$x+2y\ge 6$$.)

Step 4 : Evaluate the objective function at the corner points

Both corner points give the same value $$Z=6$$. Therefore, the minimum value of $$Z$$ cannot be less than $$6$$. To decide whether it is attained only at these two points or at more points, we examine the line that gives $$Z=6$$.

Step 5 : The isocost line for $$Z=6$$

Put $$Z=6$$ in the objective equation $$x+2y=Z$$ :

\[x+2y=6\tag{1}\]

Equation (1) is exactly the same as $$L_2$$. Hence every point on the segment of $$L_2$$ that is in the feasible region will give $$Z=6$$.

Which part of $$L_2$$ is feasible? On $$L_2$$ we already have $$x+2y=6$$ with equality, so the second constraint is satisfied automatically. We only have to ensure $$2x+y\ge 3$$ and $$x, y\ge 0$$. If we take any point on $$L_2$$ between $$A(0,3)$$ and $$B(6,0)$$, write it in the parametric form

$$(x,y)=\bigl(6\lambda,\;3(1-\lambda)\bigr), \;0\le\lambda\le 1,$$

then

$$2x+y=2\bigl(6\lambda\bigr)+3(1-\lambda)=12\lambda+3-3\lambda=3+9\lambda\ge 3,$$

and clearly $$x\ge 0,\;y\ge 0$$ for all $$\lambda\in[0,1]$$. Thus every point on the segment joining $$A(0,3)$$ and $$B(6,0)$$ is feasible and yields $$Z=6$$.

Conclusion

The minimum value of the objective function is

$$Z_{\min}=6.$$

This minimum is not confined to the two corner points; it is attained at all points on the line segment joining $$(0,3)$$ and $$(6,0)$$. Hence the minimum occurs at infinitely many points, i.e. at more than two points, as required.

Objective function and constraints

Minimise and maximise  $$Z = 5x + 10y$$  subject to

• $$x + 2y \le 120$$ (1)
• $$x + y \ge 60$$   (2)
• $$x - 2y \ge 0 \;\Longleftrightarrow\; x \ge 2y$$     (3)
• $$x \ge 0,\;y \ge 0$$     (4)

Step 1 :  Draw the feasible region

1. Plot the straight lines $$x+2y=120$$, $$x+y=60$$ and $$x=2y$$ in the first quadrant.
2. The required region is
   • below the line $$x+2y=120$$ (because of "≤");
   • above the line $$x+y=60$$ (because of "≥");
   • to the right of the line $$x=2y$$ (because of "≥");
   • in the first quadrant (because $$x,y\ge 0$$).

Shade the set of points that satisfy all these conditions – it turns out to be a convex quadrilateral.

(When drawing the figure, mark the lines, show the arrows indicating the appropriate half–planes, then darken the common region; finally label all corner points that lie in it.)

Step 2 :  Locate the corner (extreme) points

The point $$(0,60)$$ (intersection of (1) and (2)) is not feasible because it violates $$x\ge 2y$$. No other axis intersection satisfies every inequality. Hence the feasible vertices, going round the region, are

$$A(60,0),\;B(120,0),\;C(60,30),\;D(40,20).$$

Step 3 :  Evaluate $$Z$$ at each vertex

Step 4 :  Identify the optimum values

• Minimum value  $$Z_{\min}=300$$ which occurs at the single point $$(60,0).$$
• Maximum value  $$Z_{\max}=600$$ which occurs at every point on the line segment joining $$(120,0)$$ and $$(60,30)$$ (because along that segment $$x+2y=120$$ implies $$Z=5x+10y=600$$).

Result

• Minimum $$Z = 300$$ at $$x = 60,\;y = 0.$$
• Maximum $$Z = 600$$ at all feasible points satisfying $$x+2y=120$$ and $$2y \le x \le 120$$, in particular at $$(120,0)$$ and $$(60,30).$$

Step 1 : Convert the constraints into straight-line equations

• $$x+2y=100$$
• $$2x-y=0\ \;\;(\text{or }y=2x)$$
• $$2x+y=200$$
• Coordinate axes $$x=0,\;y=0$$

Each inequality represents the half-plane indicated below:

• $$x+2y\ge 100$$ → region on or above the line $$x+2y=100$$.
• $$2x-y\le 0$$ → region on or above the line $$y=2x$$.
• $$2x+y\le 200$$ → region on or below the line $$2x+y=200$$.
• $$x\ge0,\;y\ge0$$ keep us in the first quadrant.

Step 2 : Draw the three lines

Make a rough table of intercepts (all points in units):

On graph paper plot these lines and mark the required half-planes; the common shaded part in the first quadrant is the feasible region.

Description for the sketch :

1. Draw the triangle formed by the axes and $$2x+y=200$$.
2. Shade the strip bounded below by $$y=2x$$ and above by $$y=200-2x$$.
3. Further keep only the part lying on or above $$x+2y=100$$ (this chops off the small triangle near the origin).

The result is a convex quadrilateral with the following corner points (verify by solving the simultaneous equations):

• $$A(0,50)$$     (intersection of $$x=0$$ and $$x+2y=100$$)
• $$B(0,200)$$  (intersection of $$x=0$$ and $$2x+y=200$$)
• $$C(50,100)$$ (intersection of $$y=2x$$ and $$2x+y=200$$)
• $$D(20,40)$$ (intersection of $$y=2x$$ and $$x+2y=100$$)

Step 3 : Evaluate the objective function $$Z=x+2y$$ at all vertices

Step 4 : Identify the optimum values

• Maximum value $$Z_{\max}=400$$ attained at $$B(0,200)$$.
• Minimum value $$Z_{\min}=100$$ attained at both $$A(0,50)$$ and $$D(20,40)$$. In fact, every point of the line segment joining $$A$$ and $$D$$ (where $$x+2y=100\;\,(0\le x\le20)$$) gives the same minimum.

Conclusion

$$Z_{\min}=100\;\;\text{and}\;\;Z_{\max}=400$$ subject to the given constraints.

Step 1 – Write the data in standard form

Objective function: $$Z=-x+2y$$

Constraints:

• $$x\ge 3$$
• $$x+y\ge 5$$
• $$x+2y\ge 6$$
• $$y\ge 0$$

Because every inequality already has the required “$$\ge$$” sign and both variables appear explicitly, no further conversion is needed.

Step 2 – Plot the constraint lines

Draw the following straight lines on the $$xy$$-plane:

1. $$x=3$$ – a vertical line through $$x=3$$.
2. $$x+y=5$$ – intercepts: $$x=5$$ when $$y=0$$, $$y=5$$ when $$x=0$$ (draw the line through these two points).
3. $$x+2y=6$$ – intercepts: $$x=6$$ when $$y=0$$, $$y=3$$ when $$x=0$$.
4. $$y=0$$ – the $$x$$-axis.

Mark the half-planes indicated by “$$\ge$$”:

• For $$x\ge3$$ shade the region to the right of $$x=3$$.
• For $$x+y\ge5$$ shade the region above the line $$x+y=5$$.
• For $$x+2y\ge6$$ shade the region above the line $$x+2y=6$$.
• For $$y\ge0$$ take the region above the $$x$$-axis.

The feasible region is the common part of all the shaded areas; it lies to the right of $$x=3$$ and above both oblique lines. It is unbounded in the positive $$y$$-direction.

(Describe this region in the sketch: a wedge whose left boundary is $$x=3$$, whose lower oblique edges meet the line $$x=3$$, and whose top opens indefinitely upward.)

Step 3 – Locate the corner (extreme) points

Because the region is a polygonal wedge, list its vertices:

Step 4 – Evaluate $$Z$$ at these vertices

So the greatest value among the listed vertices is $$1$$ at $$A(3,2)$$.

Step 5 – Test unboundedness

Because the feasible region has no upper boundary, choose any point that keeps $$x=3$$ (the least possible value of $$x$$) and increases $$y$$:

Let $$P(3,\,y)$$ with $$y\ge2$$. All constraints are satisfied because

• $$x=3\Rightarrow x\ge3$$,
• $$3+y\ge5$$ if $$y\ge2$$,
• $$3+2y\ge6$$ if $$y\ge1.5$$ (already true when $$y\ge2$$),
• $$y\ge0$$.

At such a point $$Z_P=-3+2y$$. By taking $$y$$ as large as we please, $$2y$$ can exceed any prescribed number, so

$$Z_P \rightarrow \infty\quad\text{as}\;y\rightarrow \infty$$.

Hence $$Z$$ is unbounded above in the feasible region; therefore there is no finite maximum value.

Conclusion

The linear programming problem has no maximum; the objective function can be made arbitrarily large while respecting all the constraints.

Step 1 – Write the L.P.P. in standard (mathematical) form
Maximise $$Z = x + y$$
subject to
$$x - y \le -1$$
$$-x + y \le 0$$
$$x \ge 0,\;y \ge 0$$

Step 2 – Convert each inequality to an equation to obtain its boundary line

• For $$x - y \le -1$$  ⇒ boundary line: $$x - y = -1$$ or  $$y = x + 1$$
• For $$-x + y \le 0$$  ⇒ boundary line: $$-x + y = 0$$ or  $$y = x$$
• Coordinate axes $$x = 0$$ and $$y = 0$$ form the other boundaries.

Step 3 – Identify the half-planes corresponding to each inequality

• Take the test point $$O(0,0)$$ in $$x - y \le -1$$:
  $$0 - 0 = 0 \nleq -1$$, so the origin is not in the required half-plane. Hence the feasible side of $$y = x + 1$$ lies above the line.
• Again test $$O(0,0)$$ in $$-x + y \le 0$$:
  $$0 \le 0$$  is true, so the origin is in the required half-plane. Thus the feasible side of $$y = x$$ lies below (or on) the line.
• Finally $$x, y \ge 0$$ restrict the region to the first quadrant.

(On graph paper draw the first-quadrant axes, the line $$y = x + 1$$, and the line $$y = x$$. Shade the half-plane above $$y = x + 1$$ and below $$y = x$$ simultaneously. It is immediately seen that the two shaded portions do not overlap anywhere in the first quadrant or elsewhere.)

Step 4 – Feasibility test
The two conditions $$y \ge x + 1$$ and $$y \le x$$ must hold together.
But $$y \ge x + 1$$ implies $$y - x \ge 1$$,
whereas $$y \le x$$ implies $$y - x \le 0$$.
Both can be true only if $$1 \le 0$$, which is impossible.

Therefore no point in the first quadrant (or anywhere) satisfies all the constraints simultaneously. In other words, the feasible region is empty.

Step 5 – Conclusion for the objective function
Because there is no feasible solution, there is no point at which the objective function $$Z = x + y$$ can be evaluated. Hence the linear-programming problem is infeasible; a maximum value of $$Z$$ does not exist.