1. Terms of Linear Programming:

Linear Programming is a tool to solve optimization problems.

The following are the terms used in linear programming:

(i) Objective function: The linear function which is to be optimized (maximized or minimized) is called the objective function of the linear programming problem.

(ii) Constraints: The conditions of the problem expressed as simultaneous equations or inequations are called constraints.

(iii) Non-negative constraints: The value of the variables in the objective function of a linear programming problem are always non-negative. The inequations which represent such constraints are called non-negative constraints.

(iv) Basic variables: The $m$ variables associated with columns of the $m \times n$ non-singular matrix which may be different from zero, are called basic variables.

(v) Basic solution: A solution in which the vectors associated to $m$ variables are linear and the remaining $(n - m)$ variables are zero, is called a basic solution.

(vi) Feasible solution: The set of values of the variables which satisfies the set of constraints of linear programming problem is called a feasible solution of the linear programming problem.

(vii) Optimal solution: A feasible solution for which the objective function is minimum or maximum is called an optimal solution.

2. Mathematical Formulation of a Linear Programming Problem:

The formulation of the Linear Programming Problem $(LPP)$ as a mathematical model is done in the following steps:

(i) Identify the decision variables to be determined and express them in terms of algebraic symbols.

(ii) Identify the objective which is to be optimized and express it as a linear function of the defined decision variables.

(iii) Identify all the constraints in the given problem and then express them as linear equations or inequalities in terms of the defined decision variables.

(iv) Apply non-negative restrictions on decision variables.

3. Solution of Linear Programming Problems:

(i) Graphical method of solving linear programming problems:

A linear programming problem is solved graphically in the following steps:

(a) Graph the constraints to form a bounded or unbounded area on the coordinate plane called the feasibility region.

(b) Find the coordinates of the corners of this feasibility region.

(c) Test these corner points in the optimization equation for which the maximum or minimum value of the objective function is obtained.

Note: If feasible region is unbounded, then a maximum or a minimum value of the objective function may not exist.

(ii) Fundamental theorems of linear programming problem:

(a) Theorem 1:

If $Z = a x + b y$ be the objective function and $R$ be the feasible region for a linear programming problem, then $Z$ has an optimal value at a corner point (vertex) of the feasible region, where the variables $x$ and $y$ are subject to constraints described by the constraints.

(b) Theorem 2:

Let $Z = a x + b y$ be the objective function and $R$ be the feasible region for a linear programming problem. If $R$ is bounded, then the objective function $Z$ has both a maximum and a minimum value on $R$ and each of these occurs at a corner point of $R .$

(iii) Corner point method:

The method comprises of the following steps:

(a) Find the feasible region of the linear programming problem and determine its corner points by solving the two equations of the lines intersecting at that point.

(b) Find the value of the objective function $Z = a x + b y$ at each corner point. Let $M$ and $m$ denote the largest and smallest values of these points, respectively.

(d) In case, the feasible region is unbounded,

$M$ is the maximum value of $Z$ , if the open half plane determined by $a x + b y > M$ has no point in common with the feasible region. Otherwise, $Z$ has no maximum value.

$m$ is the minimum value of $Z$ , if the open half plane determined by $a x + b y < m$ has no point in common with the feasible region. Otherwise, $Z$ has no minimum value.

The corner points of the feasible region are A50, 50, B10, 50, C60, 0 and D60, 40. The objective function is P=52x+32y+410. The minimum value of P is at point

Important Questions on Linear Programming Problems

Learn and Prepare for any exam you want !

The corner points of the feasible region are $A (50, 50), B (10, 50), C (60, 0)$ and $D (60, 40)$ . The objective function is $P = \frac{5}{2} x + \frac{3}{2} y + 410 .$ The minimum value of $P$ is at point