Linear Programming - Graphical method of solution for problems in two variables

Maximize $Z = 4x + y$ subject to the constraints: $x + y \leq 50$, $3x + y \leq 90$, $x \geq 0, y \geq 0$.

Step 1: Convert inequalities to equations to find boundary lines: $L_1: x + y = 50$ and $L_2: 3x + y = 90$. Step 2: Find the intercepts for $L_1$: $(50, 0)$ and $(0, 50)$. Find the intercepts for $L_2$: $(30, 0)$ and $(0, 90)$. Step 3: Solve $L_1$ and $L_2$ simultaneously to find the intersection point: Subtracting $x + y = 50$ from $3x + y = 90$ gives $2x = 40 \implies x = 20$. Substituting into $L_1$ gives $20 + y = 50 \implies y = 30$. The intersection is $B(20, 30)$. Step 4: Identify the feasible region (bounded by the axes and these lines in the first quadrant). The corner points are $O(0, 0)$, $A(30, 0)$, $B(20, 30)$, and $C(0, 50)$. Step 5: 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 = 110$
• At $C(0, 50): Z = 4(0) + 50 = 50$ Step 6: The maximum value of $Z$ is $120$ at the point $(30, 0)$.

We use the graphical method to find the intersection of the constraints. Since the region is bounded, we evaluate the objective function at all vertices of the shaded polygon to find the highest value.

Minimize $Z = 20x + 10y$ subject to: $x + 2y \geq 40$, $3x + y \geq 30$, $x, y \geq 0$.

Step 1: Boundary lines are $L_1: x + 2y = 40$ (intercepts $(40, 0), (0, 20)$) and $L_2: 3x + y = 30$ (intercepts $(10, 0), (0, 30)$). Step 2: Find intersection of $L_1$ and $L_2$: Multiply $L_1$ by $3 \implies 3x + 6y = 120$. Subtract $L_2$ from this: $(3x + 6y) - (3x + y) = 120 - 30 \implies 5y = 90 \implies y = 18$. Then $x + 2(18) = 40 \implies x = 4$. Intersection is $(4, 18)$. Step 3: The feasible region is unbounded and lies above the lines $L_1$ and $L_2$. The corner points are $A(40, 0)$, $B(4, 18)$, and $C(0, 30)$. Step 4: Evaluate $Z = 20x + 10y$:

• At $A(40, 0): Z = 20(40) + 0 = 800$
• At $B(4, 18): Z = 20(4) + 10(18) = 80 + 180 = 260$
• At $C(0, 30): Z = 20(0) + 10(30) = 300$ Step 5: The minimum value is $260$ at $(4, 18)$. (Since the region is unbounded, we verify if $20x + 10y < 260$ has points in common with the feasible region; it does not, so 260 is the actual minimum).

This is a minimization problem with an unbounded feasible region extending away from the origin. The corner point with the smallest $Z$ value is the candidate for the minimum.

1. Plot lines $x + 3y = 3$ (points (3,0), (0,1)) and $x + y = 2$ (points (2,0), (0,2)).
2. The intersection point of $x + 3y = 3$ and $x + y = 2$ is found by subtraction: $(x+3y) - (x+y) = 3 - 2 \Rightarrow 2y = 1 \Rightarrow y = 0.5, x = 1.5$.
3. Corner points of the unbounded feasible region are $A(3, 0)$, $B(1.5, 0.5)$, and $C(0, 2)$.
4. Evaluate $Z$ at each point:

• 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$

1. Minimum value is 7 at $(1.5, 0.5)$. Since the region is unbounded, we check if $3x + 5y < 7$ has points in common with the feasible region. It does not, so 7 is the minimum.

Identify the feasible region above the lines, find vertices, and apply the corner point method.

1. Plot lines $3x + 5y = 15$ (intercepts (5,0), (0,3)) and $5x + 2y = 10$ (intercepts (2,0), (0,5)).
2. Find intersection: $2(3x+5y) = 30$ and $5(5x+2y) = 50 \Rightarrow 6x+10y=30, 25x+10y=50$. Subtracting gives $19x = 20 \Rightarrow x = \frac{20}{19} \approx 1.05$. Substituting $x$ gives $y = \frac{45}{19} \approx 2.37$.
3. Corner points: $O(0,0)$, $A(2,0)$, $B(\frac{20}{19}, \frac{45}{19})$, $C(0,3)$.
4. Evaluate $Z$:

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

1. Maximum value is $\frac{235}{19}$ at $(\frac{20}{19}, \frac{45}{19})$.

The feasible region is a bounded quadrilateral. The maximum value occurs at the intersection of the two constraint lines.