Linear programming Problem

1. General Linear Equations & Inequations

Standard Form & Half-Planes
A linear equation in two variables $ax+by+c=0$ (where $a, b, c \in R$ and $a, b$ are not zero simultaneously) represents a straight line.

The sets of points $\{(x,y)|ax+by+c<0\}$ and $\{(x,y)|ax+by+c>0\}$ are two open half planes.

The sets of points $\{(x,y)|ax+by+c \le 0\}$ and $\{(x,y)|ax+by+c \ge 0\}$ are two half planes with a common boundary $\{(x,y)|ax+by+c=0\}$.
Linear Inequation in Two Variables
A linear inequation in two variables $x, y$ is a mathematical expression of the form $ax+by < c$ or $ax+by > c$.

Graphical representation of $ax+by (\le \text{or} \ge) c$ is a region on any one side of the straight line $ax+by=c$.
The Origin Test
To find solutions graphically, consider $O(0,0)$ as a test point.

If $O(0,0)$ satisfies the given inequation $ax+by \le c$, then the required region is on the origin side; otherwise shade the other half plane (non-origin side).

Line passing through the origin, defining half planes.

Definition of a Convex Set
A set of points in a plane is said to be a convex set if the line segment joining any two points of the set entirely lies within the set.

Convex sets may be bounded or unbounded.
Convex Polygon Theorem (Theorem 1 & 2)
Theorem 1: The set of all feasible solutions of L.P.P. is a convex set.

Theorem 2: The objective function of L.P.P. attains its optimum value (either maximum or minimum) at least at one of the vertices of the convex polygon.

Visual comparison of Convex and Non-Convex sets.

Meaning of L.P.P.
A L.P.P. may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints (equations or inequations).
Decision Variables & Constraints
Decision Variables: The variables involved in L.P.P. ($x, y$ or $x_1, x_2$).

Constraints: Conditions under which the objective function is to be optimized.

Non-negativity Constraints: Restrictions indicating the values of variables must be positive or zero ($x \ge 0, y \ge 0$).
Objective Function
A linear function of variables which is to be optimized (e.g., maximized or minimized), generally represented as $z = ax + by$.
Mathematical Formulation of L.P.P.
Step 1: Identify the decision variables ($x, y$) and introduce non-negativity constraints ($x \ge 0, y \ge 0$).

Step 2: Identify the objective function to be optimized and express it as a linear function ($z = ax + by$).

Step 3: Identify the constraints and express them as mathematical inequations (e.g., $a_1x + b_1y \le c_1$).

Types of Solutions
Solution: A set of values of the decision variables which satisfy the conditions of the given L.P.P.

Feasible Solution: A solution which satisfies all the constraints.

Feasible Region: The common region determined by all the constraints of the L.P.P.

Optimal Feasible Solution: A feasible solution which maximizes or minimizes the objective function.
Corner Point Method (Algorithm)
1) Convert all inequations of the constraints into equations.

2) Draw the lines in X - Y plane.

3) Locate common region indicated by the constraints (feasible region).

4) Find the vertices of feasible region.

5) Find the value of the objective function $z = ax + by$ at all vertices of the feasible region.

Evaluating Corner Points

Set up an evaluation table to test the function $z$ at each vertex of the feasible region.

Vertex of Feasible Region $(x,y)$	Value of Objective Function $z = ax + by$
$O(0,0)$	$z = a(0) + b(0) = 0$
$A(x_1, 0)$	$z = a(x_1) + b(0)$
$B(x_2, y_2)$	$z = a(x_2) + b(y_2)$ (Optimal Value)
$C(0, y_1)$	$z = a(0) + b(y_1)$

Graphical Solutions (Bounded, Unbounded, Infinite)
If the feasible region is unbounded, there may be no finite maximum value of $z$ within the region.

If two distinct points produce the same minimum/maximum value, then the optimum value occurs at every point on the segment joining them (infinite number of optimal solutions).

Left: Standard bounded feasible region. Right: Unbounded region (may lack a finite maximum).