Linear Programming - Graphical method of solving linear programming problems

Solve the following linear programming problem graphically: Maximize $Z = 4x + y$ subject to the constraints: $x + y \leq 50$, $3x + y \leq 90$, $x \geq 0, y \geq 0$.

1. Convert inequalities to equations to find boundary lines: Line 1: $x + y = 50$. Points: $(0, 50)$ and $(50, 0)$. Line 2: $3x + y = 90$. Points: $(0, 90)$ and $(30, 0)$.

2. Find the feasible region: The region satisfies $x + y \leq 50$ (region below the line) and $3x + y \leq 90$ (region below the line), restricted to the first quadrant ($x \geq 0, y \geq 0$).

3. Determine corner points of the feasible region: The intersection of $x + y = 50$ and $3x + y = 90$: Subtracting the equations: $(3x + y) - (x + y) = 90 - 50 \implies 2x = 40 \implies x = 20$. Then $20 + y = 50 \implies y = 30$. Point: $(20, 30)$. Corner points are $O(0, 0)$, $A(30, 0)$, $B(20, 30)$, and $C(0, 50)$.

4. Evaluate $Z = 4x + y$ at each corner 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 = 80 + 30 = 110$
   • At $C(0, 50)$: $Z = 4(0) + 50 = 50$

Maximum value of $Z$ is 120 at point $(30, 0)$.

We first identify the feasible region by plotting the constraints on a graph. The shaded area where all conditions overlap is the feasible region. We then use the Corner Point Method, checking the value of the objective function at every vertex of this region to find the maximum.

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

1. Boundary lines: $L_1: x + 2y = 10 \implies (0, 5), (10, 0)$ $L_2: 3x + 4y = 24 \implies (0, 6), (8, 0)$

2. Find intersection of $L_1$ and $L_2$: Multiply $L_1$ by 2: $2x + 4y = 20$ Subtract from $L_2$: $(3x + 4y) - (2x + 4y) = 24 - 20 \implies x = 4$ Substitute $x=4$ in $L_1$: $4 + 2y = 10 \implies 2y = 6 \implies y = 3$. Point: $(4, 3)$.

3. Corner points of feasible region: The region is bounded by points $(0, 5)$, $(0, 6)$, $(4, 3)$, and $(8, 0)$ is not possible because of the intersection directions. Checking valid region: Constraints: Above $x + 2y = 10$ and below $3x + 4y = 24$. Corner points: $A(0, 5)$, $B(0, 6)$, $C(4, 3)$. (Note: $(8,0)$ and $(10,0)$ check: $8+0 \geq 10$ is False, so $(8,0)$ is out. $3(10)+0 \leq 24$ is False, so $(10,0)$ is out).

4. Evaluate $Z$:

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

Minimum value is 2300 at $(4, 3)$.

Identify the intersection points of the lines and determine which corner points satisfy all inequalities. Calculating $Z$ at these vertices reveals the minimum value.

1. Plot lines: $L_1: x + 3y = 60$ (points (0,20), (60,0)), $L_2: x + y = 10$ (points (0,10), (10,0)), $L_3: x = y$.
2. Identify Feasible Region vertices: $A(0,10)$, $B(5,5)$, $C(15,15)$, $D(0,20)$.
3. Evaluate $Z$ at vertices: At $A(0,10), Z = 3(0) + 9(10) = 90$ At $B(5,5), Z = 3(5) + 9(5) = 15 + 45 = 60$ At $C(15,15), Z = 3(15) + 9(15) = 45 + 135 = 180$ At $D(0,20), Z = 3(0) + 9(20) = 180$
4. Since $Z$ is 180 at both $C$ and $D$, the maximum value is 180 and occurs at every point on the line segment $CD$.

The problem demonstrates a case of multiple optimal solutions because the objective function is parallel to one of the constraint boundaries ($x + 3y = 60$).

1. Find corner points of feasible region by solving intersection of lines: $L_1: x + 2y = 120$ $L_2: x + y = 60$ $L_3: x = 2y$
2. Corner points: $A(40,20)$, $B(60,30)$, $C(120,0)$, $D(60,0)$.
3. Calculate $Z$: At $A(40,20), Z = 5(40) + 10(20) = 400$ At $B(60,30), Z = 5(60) + 10(30) = 600$ At $C(120,0), Z = 5(120) + 10(0) = 600$ At $D(60,0), Z = 5(60) + 10(0) = 300$
4. Minimum value is 300 at point $(60,0)$.

We identify the intersection points of the boundary lines and use the Corner Point Method to evaluate the objective function.