Linear Programming

Given: Objective function $Z = 3x + 4y$

Constraints: $x + y \leq 4,\ x \geq 0,\ y \geq 0$

Step 1: Find the corner points of the feasible region.

The constraint $x + y = 4$ meets the axes at $A(4, 0)$ and $B(0, 4)$.

With $x \geq 0,\ y \geq 0$, the feasible region is the triangle with vertices:
- $O(0, 0)$
- $A(4, 0)$
- $B(0, 4)$

Step 2: Evaluate $Z$ at each corner point.

| Corner Point | $Z = 3x + 4y$ |
|---|---|
| $O(0,0)$ | $3(0)+4(0) = 0$ |
| $A(4,0)$ | $3(4)+4(0) = 12$ |
| $B(0,4)$ | $3(0)+4(4) = 16$ |

Step 3: Conclusion.

The maximum value of $Z$ is $\boxed{16}$ at the point $B(0, 4)$.

Given: Objective function $Z = -3x + 4y$

Constraints: $x + 2y \leq 8,\ 3x + 2y \leq 12,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

- Line $x + 2y = 8$ meets axes at $(8, 0)$ and $(0, 4)$.
- Line $3x + 2y = 12$ meets axes at $(4, 0)$ and $(0, 6)$.

Intersection of the two lines:
Subtract $x + 2y = 8$ from $3x + 2y = 12$:
$$2x = 4 \implies x = 2$$
$$2 + 2y = 8 \implies y = 3$$
Intersection point: $C(2, 3)$.

Corner points of the feasible region:
- $O(0, 0)$
- $A(4, 0)$
- $C(2, 3)$
- $B(0, 4)$

Step 2: Evaluate $Z$ at each corner point.

| Corner Point | $Z = -3x + 4y$ |
|---|---|
| $O(0,0)$ | $0$ |
| $A(4,0)$ | $-12$ |
| $C(2,3)$ | $-6+12 = 6$ |
| $B(0,4)$ | $16$ |

Step 3: Conclusion.

The minimum value of $Z$ is $\boxed{-12}$ at the point $A(4, 0)$.

Given: Objective function $Z = 5x + 3y$

Constraints: $3x + 5y \leq 15,\ 5x + 2y \leq 10,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

- Line $3x + 5y = 15$ meets axes at $(5, 0)$ and $(0, 3)$.
- Line $5x + 2y = 10$ meets axes at $(2, 0)$ and $(0, 5)$.

Intersection of the two lines:
From $5x + 2y = 10$: $y = \dfrac{10 - 5x}{2}$

Substitute into $3x + 5y = 15$:
$$3x + 5 \cdot \frac{10-5x}{2} = 15$$
$$6x + 50 - 25x = 30$$
$$-19x = -20 \implies x = \frac{20}{19}$$
$$y = \frac{10 - 5(20/19)}{2} = \frac{10 - 100/19}{2} = \frac{(190-100)/19}{2} = \frac{90}{38} = \frac{45}{19}$$

Intersection point: $C\!\left(\dfrac{20}{19},\ \dfrac{45}{19}\right)$

Corner points:
- $O(0,0)$
- $A(2,0)$
- $C\!\left(\dfrac{20}{19}, \dfrac{45}{19}\right)$
- $B(0,3)$

Step 2: Evaluate $Z$ at each corner point.

| Corner Point | $Z = 5x + 3y$ |
|---|---|
| $O(0,0)$ | $0$ |
| $A(2,0)$ | $10$ |
| $C\!\left(\frac{20}{19},\frac{45}{19}\right)$ | $\frac{100}{19}+\frac{135}{19} = \frac{235}{19} \approx 12.37$ |
| $B(0,3)$ | $9$ |

Step 3: Conclusion.

The maximum value of $Z$ is $\dfrac{235}{19}$ at $\left(\dfrac{20}{19},\ \dfrac{45}{19}\right)$.

$$\boxed{Z_{\max} = \frac{235}{19} \approx 12.37}$$

Given: Objective function $Z = 3x + 5y$

Constraints: $x + 3y \geq 3,\ x + y \geq 2,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

- Line $x + 3y = 3$ meets axes at $A(3, 0)$ and $B(0, 1)$.
- Line $x + y = 2$ meets axes at $C(2, 0)$ and $D(0, 2)$.

Intersection of the two lines:
Subtract $x + y = 2$ from $x + 3y = 3$:
$$2y = 1 \implies y = \frac{1}{2},\quad x = 2 - \frac{1}{2} = \frac{3}{2}$$
Intersection point: $E\!\left(\dfrac{3}{2},\ \dfrac{1}{2}\right)$

The feasible region is unbounded (above both lines in the first quadrant). Corner points:
- $D(0, 2)$
- $E\!\left(\dfrac{3}{2}, \dfrac{1}{2}\right)$
- $A(3, 0)$

Step 2: Evaluate $Z$ at each corner point.

| Corner Point | $Z = 3x + 5y$ |
|---|---|
| $D(0,2)$ | $0 + 10 = 10$ |
| $E\!\left(\frac{3}{2},\frac{1}{2}\right)$ | $\frac{9}{2}+\frac{5}{2} = 7$ |
| $A(3,0)$ | $9 + 0 = 9$ |

Step 3: Check for unbounded minimum.

The smallest value is $7$ at $E\!\left(\dfrac{3}{2}, \dfrac{1}{2}\right)$. Since the feasible region is unbounded, we check whether 3x + 5y < 7 has any point in the feasible region. The half-plane 3x + 5y < 7 has no common point with the feasible region.

Conclusion: The minimum value of $Z$ is $\boxed{7}$ at $\left(\dfrac{3}{2},\ \dfrac{1}{2}\right)$.

Given: Objective function $Z = 3x + 2y$

Constraints: $x + 2y \leq 10,\ 3x + y \leq 15,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

- Line $x + 2y = 10$ meets axes at $(10, 0)$ and $(0, 5)$.
- Line $3x + y = 15$ meets axes at $(5, 0)$ and $(0, 15)$.

Intersection of the two lines:
From $3x + y = 15$: $y = 15 - 3x$
Substitute into $x + 2y = 10$:
$$x + 2(15 - 3x) = 10 \implies x + 30 - 6x = 10 \implies -5x = -20 \implies x = 4$$
$$y = 15 - 12 = 3$$
Intersection point: $C(4, 3)$

Corner points:
- $O(0,0)$
- $A(5,0)$
- $C(4,3)$
- $B(0,5)$

Step 2: Evaluate $Z$ at each corner point.

| Corner Point | $Z = 3x + 2y$ |
|---|---|
| $O(0,0)$ | $0$ |
| $A(5,0)$ | $15$ |
| $C(4,3)$ | $12+6 = 18$ |
| $B(0,5)$ | $10$ |

Step 3: Conclusion.

The maximum value of $Z$ is $\boxed{18}$ at the point $C(4, 3)$.

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

Constraints: $2x + y \geq 3,\ x + 2y \geq 6,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

- Line $2x + y = 3$ meets axes at $A\!\left(\dfrac{3}{2}, 0\right)$ and $B(0, 3)$.
- Line $x + 2y = 6$ meets axes at $C(6, 0)$ and $D(0, 3)$.

Intersection of the two lines:
From $2x + y = 3$: $y = 3 - 2x$
Substitute into $x + 2y = 6$:
$$x + 2(3-2x) = 6 \implies x + 6 - 4x = 6 \implies -3x = 0 \implies x = 0,\ y = 3$$
Intersection point: $D(0, 3)$

Note: Both lines meet at the same point on the $y$-axis, $D(0,3)$. The feasible region is unbounded with corner points:
- $C(6, 0)$
- $D(0, 3)$

Step 2: Evaluate $Z$ at each corner point.

| Corner Point | $Z = x + 2y$ |
|---|---|
| $C(6,0)$ | $6 + 0 = 6$ |
| $D(0,3)$ | $0 + 6 = 6$ |

Step 3: Check for unbounded minimum.

Both corner points give $Z = 6$. We check whether x + 2y < 6 has any point in the feasible region. The half-plane x + 2y < 6 has no common point with the feasible region.

Step 4: Conclusion — minimum at more than two points.

Since $Z = 6$ at both $C(6,0)$ and $D(0,3)$, by the property of linear programming, every point on the line segment $CD$ also gives $Z = 6$.

The line segment joining $C(6,0)$ and $D(0,3)$ lies on $x + 2y = 6$, which is the same as the constraint boundary. Every point $(x, y)$ on this segment satisfies all constraints and gives $Z = 6$.

Hence, the minimum value of $Z$ is $\boxed{6}$, and it occurs at infinitely many points (all points on the segment joining $(6,0)$ and $(0,3)$), i.e., at more than two points.

Given: Objective function $Z = 5x + 10y$

Constraints: $x + 2y \leq 120,\ x + y \geq 60,\ x - 2y \geq 0,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

Key lines:
1. $x + 2y = 120$
2. $x + y = 60$
3. $x = 2y$ (i.e., $x - 2y = 0$)

Intersection of lines (2) and (3): $x = 2y$ and $x + y = 60$
$$2y + y = 60 \implies y = 20,\ x = 40 \implies A(40, 20)$$

Intersection of lines (1) and (3): $x = 2y$ and $x + 2y = 120$
$$2y + 2y = 120 \implies y = 30,\ x = 60 \implies B(60, 30)$$

Intersection of lines (1) and (2): $x + 2y = 120$ and $x + y = 60$
$$y = 60,\ x = 0 \implies C(0, 60)$$
But check $x - 2y \geq 0$: 0 - 120 = -120 < 0. Not feasible.

Check line (2) on $x$-axis: $x + y = 60$ at $y=0$ gives $x=60$. Check $x-2y \geq 0$: $60 \geq 0$ ✓. Check $x+2y \leq 120$: $60 \leq 120$ ✓. Point $D(60, 0)$.

Check line (1) on $x$-axis: $x + 2y = 120$ at $y=0$ gives $x=120$. Check $x-2y\geq 0$: $120\geq 0$ ✓. Check $x+y\geq 60$: $120\geq 60$ ✓. Point $E(120, 0)$.

Corner points of feasible region:
- $A(40, 20)$
- $B(60, 30)$
- $E(120, 0)$
- $D(60, 0)$

Step 2: Evaluate $Z = 5x + 10y$ at each corner point.

| Corner Point | $Z = 5x + 10y$ |
|---|---|
| $A(40,20)$ | $200 + 200 = 400$ |
| $B(60,30)$ | $300 + 300 = 600$ |
| $E(120,0)$ | $600 + 0 = 600$ |
| $D(60,0)$ | $300 + 0 = 300$ |

Step 3: Conclusion.

- Minimum value of $Z$ is $\boxed{300}$ at $D(60, 0)$.
- Maximum value of $Z$ is $\boxed{600}$, which occurs at both $B(60, 30)$ and $E(120, 0)$, and hence at every point on the line segment joining $B$ and $E$.

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

Constraints: $x + 2y \geq 100,\ 2x - y \leq 0,\ 2x + y \leq 200,\ x \geq 0,\ y \geq 0$

Step 1: Find corner points of the feasible region.

Key lines:
1. $x + 2y = 100$
2. $2x - y = 0 \implies y = 2x$
3. $2x + y = 200$

Intersection of (1) and (2): $y = 2x$ into $x + 2y = 100$:
$$x + 4x = 100 \implies x = 20,\ y = 40 \implies A(20, 40)$$

Intersection of (2) and (3): $y = 2x$ into $2x + y = 200$:
$$2x + 2x = 200 \implies x = 50,\ y = 100 \implies B(50, 100)$$

Intersection of (1) and $x$-axis ($y=0$): $x = 100$. Check $2x-y\leq 0$: $200 \leq 0$? No. Not feasible.

Intersection of (3) and $y$-axis ($x=0$): $y = 200$. Check $x+2y\geq 100$: $400\geq 100$ ✓. Check $2x-y\leq 0$: $-200\leq 0$ ✓. Point $C(0, 200)$.

Intersection of (1) and $y$-axis ($x=0$): $2y=100 \implies y=50$. Check $2x-y\leq 0$: $-50\leq 0$ ✓. Check $2x+y\leq 200$: $50\leq 200$ ✓. Point $D(0, 50)$.

Corner points of feasible region:
- $A(20, 40)$
- $B(50, 100)$
- $C(0, 200)$
- $D(0, 50)$

Step 2: Evaluate $Z = x + 2y$ at each corner point.

| Corner Point | $Z = x + 2y$ |
|---|---|
| $A(20,40)$ | $20 + 80 = 100$ |
| $B(50,100)$ | $50 + 200 = 250$ |
| $C(0,200)$ | $0 + 400 = 400$ |
| $D(0,50)$ | $0 + 100 = 100$ |

Step 3: Conclusion.

- Minimum value of $Z$ is $\boxed{100}$, occurring at both $A(20, 40)$ and $D(0, 50)$, and hence at every point on the segment $AD$.
- Maximum value of $Z$ is $\boxed{400}$ at $C(0, 200)$.

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

Constraints: $x \geq 3,\ x + y \geq 5,\ x + 2y \geq 6,\ y \geq 0$

Step 1: Find corner points of the feasible region.

Key lines:
1. $x = 3$
2. $x + y = 5$
3. $x + 2y = 6$

Intersection of (1) and (3): $x=3$ into $x+2y=6$: $3+2y=6 \implies y=\dfrac{3}{2}$. Point $A\!\left(3,\ \dfrac{3}{2}\right)$.

Intersection of (1) and (2): $x=3$ into $x+y=5$: $y=2$. Point $B(3, 2)$.

Check: At $B(3,2)$: $x+2y = 3+4=7\geq 6$ ✓.
At $A(3, 3/2)$: x+y=3+3/2=9/2 < 5. Not satisfying constraint (2).

Intersection of (2) and (3): Subtract: $(x+2y)-(x+y)=6-5 \implies y=1,\ x=4$. Point $C(4,1)$.
Check $x\geq 3$: $4\geq 3$ ✓.

The feasible region is unbounded. Corner points:
- $B(3, 2)$
- $C(4, 1)$
- and the region extends to infinity.

Also check along $x=3$ upward: as $y\to\infty$, $Z=-3+2y\to\infty$.

Step 2: Evaluate $Z = -x + 2y$ at corner points.

| Corner Point | $Z = -x + 2y$ |
|---|---|
| $B(3,2)$ | $-3+4 = 1$ |
| $C(4,1)$ | $-4+2 = -2$ |

Step 3: Conclusion.

Since the feasible region is unbounded and $Z$ increases without bound as $y \to \infty$ (along $x=3$), $Z$ has no maximum value.

The feasible region is unbounded, so $Z = -x + 2y$ has no maximum (it can be made arbitrarily large).

Given: Objective function $Z = x + y$

Constraints: $x - y \leq -1,\ -x + y \leq 0,\ x \geq 0,\ y \geq 0$

Step 1: Analyse the constraints.

- $x - y \leq -1 \implies y \geq x + 1$ ... (i)
- $-x + y \leq 0 \implies y \leq x$ ... (ii)

Step 2: Check for feasibility.

From (i): $y \geq x + 1$, which means y > x.

From (ii): $y \leq x$.

These two conditions y > x and $y \leq x$ cannot be satisfied simultaneously for any real values of $x$ and $y$.

Step 3: Conclusion.

There is no feasible region (the constraints are contradictory). Hence, the given linear programming problem has no feasible solution, and therefore $Z = x + y$ has no maximum value.