Linear Programming - Introduction, related terminology (constraints, objective function, optimization)

Maximize $Z = 3x + 4y$ subject to the constraints: $x + y \le 4$, $x \ge 0$, $y \ge 0$.

1. Convert the inequality to an equation: $x + y = 4$. The line passes through $(4, 0)$ and $(0, 4)$.
2. Since the constraint is $x + y \le 4$, the feasible region is the area below the line $x + y = 4$ in the first quadrant (due to $x, y \ge 0$).
3. The corner points of the feasible region are $O(0, 0)$, $A(4, 0)$, and $B(0, 4)$.
4. Evaluate $Z$ at each corner point:

• At $O(0, 0): Z = 3(0) + 4(0) = 0$
• At $A(4, 0): Z = 3(4) + 4(0) = 12$
• At $B(0, 4): Z = 3(0) + 4(4) = 16$

1. Comparing the values, the maximum value of $Z$ is $16$ at the point $(0, 4)$.

The problem asks for the maximum value of a linear function. By plotting the boundary and identifying the vertices of the resulting triangle (feasible region), we test each vertex in the objective function to find the highest value.

Minimize $Z = 5x + 10y$ subject to: $x + 2y \ge 120$, $x + y \ge 60$, $x, y \ge 0$.

1. Plot the boundary lines: $L_1: x + 2y = 120$ (intercepts $(120, 0), (0, 60)$) and $L_2: x + y = 60$ (intercepts $(60, 0), (0, 60)$).
2. The constraints are 'greater than or equal to', so the feasible region is the area above both lines in the first quadrant (unbounded region).
3. Find the corner points of the feasible region: $A(120, 0)$ and $B(0, 60)$. Note that the intersection of the two lines is at $(0, 60)$.
4. Evaluate $Z$ at the corner points:

• At $A(120, 0): Z = 5(120) + 10(0) = 600$
• At $B(0, 60): Z = 5(0) + 10(60) = 600$

1. Since the value is the same at both points, any point on the line segment joining $(120, 0)$ and $(0, 60)$ that satisfies the constraints will give the minimum value of $600$.

This example demonstrates a minimization problem with an unbounded feasible region. It also shows a special case where multiple points (an entire line segment) provide the same optimal value.

1. Identify corner points by solving boundary equations:

• Line 1: $x + 2y = 10$. Intercepts are $(10, 0)$ and $(0, 5)$.
• Line 2: $3x + 4y = 24$. Intercepts are $(8, 0)$ and $(0, 6)$.

1. Intersection of $x + 2y = 10$ and $3x + 4y = 24$: Multiply Line 1 by 2: $2x + 4y = 20$. Subtract from Line 2: $(3x - 2x) = 24 - 20 \Rightarrow x = 4$. Substitute $x=4$ in Line 1: $4 + 2y = 10 \Rightarrow 2y = 6 \Rightarrow y = 3$.
2. Corner points of feasible region: $A(0, 5)$, $B(0, 6)$, $C(4, 3)$.
3. Evaluate $Z$ at corners:

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

The feasible region is the small triangular area bounded by the $y$-axis and the two intersecting lines. The minimum occurs at the intersection point $(4, 3)$ because it has the lowest cost coefficient weight.

1. Analyze constraints:

• Constraint 1: $y \ge x + 1$
• Constraint 2: $y \le x$

1. Check for common region:

• The first inequality represents the region above the line $y = x + 1$.
• The second inequality represents the region below the line $y = x$.

1. Since the lines $y = x + 1$ and $y = x$ are parallel and the required regions are in opposite directions, there is no point that satisfies both conditions simultaneously.
2. Therefore, the feasible region is empty.

When constraints are contradictory, no feasible region exists. In such cases, the LPP has no optimal solution.