Chapter 12: Linear Programming (Linear Programming)

The feasible region is the triangle OAB (bounded).

Maximum Z = 16 at (0, 4)

Intersection of $x+2y=8$ and $3x+2y=12$: subtracting, $2x=4\Rightarrow x=2$, $y=3$. The region OABC is bounded.

Minimum Z = −12 at (4, 0)

Intersection of $3x+5y=15$ and $5x+2y=10$: $6x+10y=30$ and $25x+10y=50$ give $19x=20$, so $x=\frac{20}{19}$, $y=\frac{45}{19}$.

Maximum Z = 235/19 at (20/19, 45/19)

Intersection of $x+3y=3$ and $x+y=2$: $2y=1$, so $y=\frac{1}{2}$, $x=\frac{3}{2}$. The feasible region is unbounded.

Since the region is unbounded, check the half-plane $3x+5y<7$: its boundary line touches the region only at B, and it has no point in common with the region. So 7 is the minimum.

Minimum Z = 7 at (3/2, 1/2)

Intersection: $x=10-2y$ in $3x+y=15$ gives $30-5y=15$, $y=3$, $x=4$.

Maximum Z = 18 at (4, 3)

The lines $2x+y=3$ and $x+2y=6$ meet at (0, 3). The feasible region (unbounded) has corners A(6, 0) and B(0, 3).

The half-plane $x+2y<6$ has no common point with the region (it is excluded by the constraint $x+2y\ge 6$), so 6 is the minimum. Because Z has the same value 6 at A and B and the objective line is the boundary $x+2y=6$ itself, every point of segment AB gives Z = 6.

Minimum Z = 6 at all points of the line segment joining (6, 0) and (0, 3)

Corners: $x+y=60$ meets the x-axis at A(60, 0); $x+2y=120$ meets it at B(120, 0); $x+2y=120$ and $x=2y$ meet at C(60, 30); $x+y=60$ and $x=2y$ meet at D(40, 20).

Minimum Z = 300 at (60, 0); maximum Z = 600 at all points on the segment joining (120, 0) and (60, 30)

Corners: A(0, 50) (x = 0 on $x+2y=100$); B(20, 40) ($y=2x$ with $x+2y=100$: $5x=100$); C(50, 100) ($y=2x$ with $2x+y=200$: $4x=200$); D(0, 200).

Minimum Z = 100 at all points on the segment joining (0, 50) and (20, 40); maximum Z = 400 at (0, 200)

Corners: A(3, 2) ($x=3$, $x+y=5$); B(4, 1) ($x+y=5$, $x+2y=6$); C(6, 0). The region is unbounded.

Check the half-plane $-x+2y>1$: it contains feasible points, e.g. (3, 5) gives $-3+10=7>1$. So Z can be made as large as we like.

Z has no maximum value.

$x-y\le -1$ means $y\ge x+1$, while $-x+y\le 0$ means $y\le x$. No point can satisfy both ($x+1\le y\le x$ is impossible). The two half-planes lie on opposite sides of the parallel lines $y=x+1$ and $y=x$.

There is no feasible region, so Z has no maximum value.