Key Points

A Linear Programming Problem (LPP) is a mathematical method for finding the optimal value (maximum or minimum) of a linear function, subject to a set of linear inequalities called constraints.

The objective function is a linear function of the form $Z = ax + by$, where $a$ and $b$ are constants. The goal of an LPP is to maximize or minimize this function.

The variables, typically $x$ and $y$, whose values need to be determined to find the optimal solution are called decision variables. These variables are always non-negative, meaning $x \geq 0$ and $y \geq 0$.

Constraints are the set of linear inequalities or equations that restrict the values of the decision variables. For example, an investment constraint could be $2500x + 500y \leq 50000$.

The feasible region is the common area on a graph determined by all constraints, including the non-negative constraints ($x \geq 0, y \geq 0$). It is always a convex region.

Any point within or on the boundary of the feasible region represents a feasible solution. Any point outside the feasible region is an infeasible solution.

An optimal solution is a point in the feasible region that provides the optimal (maximum or minimum) value for the objective function.

Theorem 1 states that if an optimal solution exists, it must occur at a corner point (vertex) of the feasible region. This is the basis of the Corner Point Method.

A feasible region is bounded if it can be enclosed within a circle. For a bounded region, the objective function will have both a maximum and a minimum value, each occurring at a corner point.

To solve an LPP graphically: 1. Graph the constraints to find the feasible region. 2. Determine the coordinates of all corner points (vertices). 3. Evaluate the objective function $Z$ at each corner point to find the optimal value.

If the feasible region is unbounded, an optimal value may not exist. To check if a maximum value $M$ found at a corner point is valid, graph $ax+by > M$. If this half-plane has no common points with the feasible region, $M$ is the maximum.

To check if a minimum value $m$ is valid in an unbounded region, graph $ax+by < m$. If this half-plane has no points in common with the feasible region, then $m$ is the minimum value; otherwise, no minimum exists.

If the objective function has the same optimal value at two distinct corner points, then every point on the line segment connecting these two points also represents an optimal solution.

If there is no region on the graph that satisfies all the constraints simultaneously, the problem has no feasible region and therefore no feasible or optimal solution.