Linear Programming - Constraints, Objective Function, Optimization

Maximize $Z = 5x + 3y$ subject to the constraints: $x + y \leq 6$, $2x + y \leq 8$, $x \geq 0, y \geq 0$.

1. Identify the Boundary Lines:

• $L_1: x + y = 6$ (passes through $(0,6)$ and $(6,0)$)
• $L_2: 2x + y = 8$ (passes through $(0,8)$ and $(4,0)$)

1. Find the Intersection Point of $L_1$ and $L_2$: \nSubtract $x + y = 6$ from $2x + y = 8$: $(2x - x) + (y - y) = 8 - 6 \implies x = 2$. \nSubstitute $x = 2$ into $x + y = 6 \implies 2 + y = 6 \implies y = 4$. \nIntersection Point: $(2, 4)$.

2. Determine the Feasible Region: \nSince both constraints are $\leq$, the region is toward the origin. The vertices of the bounded feasible region are:

• $O(0, 0)$
• $A(4, 0)$ (from $L_2$)
• $B(2, 4)$ (Intersection)
• $C(0, 6)$ (from $L_1$)

1. Evaluate the Objective Function $Z = 5x + 3y$ at each vertex:

• At $O(0, 0): Z = 5(0) + 3(0) = 0$
• At $A(4, 0): Z = 5(4) + 3(0) = 20$
• At $B(2, 4): Z = 5(2) + 3(4) = 10 + 12 = 22$
• At $C(0, 6): Z = 5(0) + 3(6) = 18$

1. Conclusion: \nThe maximum value of $Z$ is $22$, which occurs at the point $(2, 4)$.

We use the Corner Point Method by first sketching the linear equations on a graph to find the feasible region in the first quadrant. By calculating $Z$ at every vertex of this region, we identify the highest value as the optimal solution.

Minimize $Z = 200x + 500y$ subject to: $x + 2y \geq 10$, $3x + 4y \geq 24$, $x \geq 0, y \geq 0$.

1. Identify the Boundary Lines:

• $L_1: x + 2y = 10$ (Intersects axes at $(10,0)$ and $(0,5)$)
• $L_2: 3x + 4y = 24$ (Intersects axes at $(8,0)$ and $(0,6)$)

1. Find the Intersection Point: \nMultiply $L_1$ by $2$: $2x + 4y = 20$. \nSubtract this from $L_2$: $(3x - 2x) + (4y - 4y) = 24 - 20 \implies x = 4$. \nSubstitute $x = 4$ into $L_1$: $4 + 2y = 10 \implies 2y = 6 \implies y = 3$. \nIntersection Point: $(4, 3)$.

2. Determine the Feasible Region: \nSince both constraints are $\geq$, the region is 'Unbounded' and away from the origin. Vertices are:

• $A(10, 0)$
• $B(4, 3)$
• $C(0, 6)$

1. Evaluate $Z = 200x + 500y$:

• At $A(10, 0): Z = 200(10) + 0 = 2000$
• At $B(4, 3): Z = 200(4) + 500(3) = 800 + 1500 = 2300$
• At $C(0, 6): Z = 0 + 500(6) = 3000$

1. Conclusion: \nThe minimum value of $Z$ is $2000$ at the point $(10, 0)$.

For minimization with $\geq$ constraints, the feasible region is typically unbounded away from the origin. We identify the 'outer' corner points and evaluate the cost function to find the minimum value.

1. Plot the lines $x + y = 50$ and $3x + y = 90$.
2. Identify the feasible region bounded by the axes and these lines.
3. Find corner points: $O(0, 0)$, $A(30, 0)$, $B(20, 30)$ (intersection of both lines), and $C(0, 50)$.
4. Evaluate $Z$ at each point:

• At $O(0, 0): Z = 4(0) + 0 = 0$
• At $A(30, 0): Z = 4(30) + 0 = 120$
• At $B(20, 30): Z = 4(20) + 30 = 110$
• At $C(0, 50): Z = 4(0) + 50 = 50$

Max value is 120 at $(30, 0)$.

The maximum value is found by testing all vertices of the convex polygon formed by the constraints. The point $(30, 0)$ yields the highest $Z$.

1. Plot $x + 3y = 3$ and $x + y = 2$.
2. The feasible region is unbounded and lies above/right of the lines.
3. Corner points: $A(3, 0)$, $B(1.5, 0.5)$, and $C(0, 2)$.
4. Evaluate $Z$:

• At $A(3, 0): Z = 3(3) + 5(0) = 9$
• At $B(1.5, 0.5): Z = 3(1.5) + 5(0.5) = 4.5 + 2.5 = 7$
• At $C(0, 2): Z = 3(0) + 5(2) = 10$

Minimum value is 7 at $(1.5, 0.5)$.

For an unbounded region, we find the minimum at the corner points. Since the coefficients of $Z$ are positive and the region is restricted to the first quadrant, a minimum exists.