Linear Programming - Graphical Method of Solution

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

Step 1: Convert inequalities to equations to find intercepts. For $3x + 5y = 15$: When $x=0, y=3 \implies (0,3)$; When $y=0, x=5 \implies (5,0)$. For $5x + 2y = 10$: When $x=0, y=5 \implies (0,5)$; When $y=0, x=2 \implies (2,0)$.

Step 2: Plot the lines and find the feasible region. Since both constraints are $\leq$, the region is towards the origin. The non-negativity constraints $x, y \geq 0$ limit the region to the first quadrant.

Step 3: Find the intersection point of $3x + 5y = 15$ and $5x + 2y = 10$. Multiplying the first by 2 and the second by 5: $6x + 10y = 30$ $25x + 10y = 50$ Subtracting: $19x = 20 \implies x = \frac{20}{19} \approx 1.05$ Substitute $x$: $3(\frac{20}{19}) + 5y = 15 \implies 5y = 15 - \frac{60}{19} = \frac{225}{19} \implies y = \frac{45}{19} \approx 2.37$.

Step 4: Evaluate $Z$ at corner points:

• At $O(0,0): Z = 5(0) + 3(0) = 0$
• At $A(2,0): Z = 5(2) + 3(0) = 10$
• At $B(\frac{20}{19}, \frac{45}{19}): Z = 5(\frac{20}{19}) + 3(\frac{45}{19}) = \frac{100+135}{19} = \frac{235}{19} \approx 12.37$
• At $C(0,3): Z = 5(0) + 3(3) = 9$

Maximum value of $Z$ is $\frac{235}{19}$ at $x = \frac{20}{19}, y = \frac{45}{19}$.

We first identify the boundary lines and shade the region satisfied by all inequalities. The feasible region is a quadrilateral with vertices $(0,0), (2,0), (\frac{20}{19}, \frac{45}{19}),$ and $(0,3)$. We then test the objective function at each vertex to find the maximum value.

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

Step 1: Find intercepts for boundary lines. Line 1: $x + 2y = 10 \implies (10,0)$ and $(0,5)$. Line 2: $3x + 4y = 24 \implies (8,0)$ and $(0,6)$.

Step 2: Identify the Feasible Region. Since constraints are $\geq$, the region is 'unbounded' and away from the origin (above the lines).

Step 3: Find the corner points of the unbounded region.

• Intersection of $x + 2y = 10$ and the y-axis: $(0,6)$ (since $(0,6)$ is higher than $(0,5)$).
• Intersection of the two lines: $3x + 4y = 24$ $2x + 4y = 20$ (Line 1 multiplied by 2) Subtracting: $x = 4$. Substituting $x$: $4 + 2y = 10 \implies 2y = 6 \implies y = 3$. Corner point: $(4,3)$.
• Intersection of $3x + 4y = 24$ and the x-axis: $(10,0)$ (since $(10,0)$ is further right than $(8,0)$).

Step 4: Evaluate $Z$ at corner points:

• At $(0,6): Z = 2(0) + 10(6) = 60$
• At $(4,3): Z = 2(4) + 10(3) = 38$
• At $(10,0): Z = 2(10) + 10(0) = 20$

Minimum value of $Z$ is $20$ at $(10,0)$.

In this minimization problem with $\geq$ constraints, the feasible region is unbounded in the first quadrant. The corner points are $(0,6), (4,3),$ and $(10,0)$. After testing these points, we find the minimum value at $(10,0)$.

1. Plot lines: $x + y = 50$ (intercepts $(50,0), (0,50)$) and $3x + y = 90$ (intercepts $(30,0), (0,90)$).
2. Identify Feasible Region vertices by solving equations:

• Intersection of $x+y=50$ and $3x+y=90$: Subtraction gives $2x = 40 \Rightarrow x=20, y=30$. Vertex is $(20, 30)$.
• Other vertices: $(0, 0), (30, 0), (0, 50)$.

1. Evaluate $Z$ at vertices:

• At $(0,0): Z = 0$
• At $(30,0): Z = 4(30) + 0 = 120$
• At $(20,30): Z = 4(20) + 30 = 110$
• At $(0,50): Z = 4(0) + 50 = 50$ Max value is 120 at $(30, 0)$.

We identify the corner points of the shaded region bounded by the two lines and the axes. The maximum value of the linear function $Z$ is found by testing each corner point.

1. Plot boundary lines: $2x + y = 8$ (intercepts $(4,0), (0,8)$) and $x + 2y = 10$ (intercepts $(10,0), (0,5)$).
2. The region is unbounded 'above' the lines.
3. Solve for intersection: $2(2x+y=8) \Rightarrow 4x+2y=16$. Subtract $x+2y=10 \Rightarrow 3x=6 \Rightarrow x=2$. Then $y=4$. Intersection is $(2, 4)$.
4. Vertices: $(0, 8), (2, 4), (10, 0)$.
5. Evaluate $Z$:

• At $(0,8): Z = 3(0) + 5(8) = 40$
• At $(2,4): Z = 3(2) + 5(4) = 26$
• At $(10,0): Z = 3(10) + 5(0) = 30$ Minimum value is 26 at $(2, 4)$.

Since the inequalities are $\geq$, the feasible region is the area above and to the right of the boundary lines. The minimum occurs at the vertex closest to the origin.