Linear Programming Problem (LPP)
Optimization Problem
Problems which seek to maximize or minimize a numerical function of a variables with the variables subject to certain constraints from a general class is called optimization problem.
Programming Problem
The term programming refers to the process of determining a particular program or plan of action.
Programming problem deals with determining optimal allocations of limited resources to meet given objectives. Programming problem deals with situations where a number of resources, such as men, material, machine and land are available and are to be combined to yield one or more product.
There are certain restrictions on all or some of the following broad categories, i.e. on the total amount of each resource available, on the quantity of each product made, on the quality of each product. Even within these restrictions there will exist many feasible allocations. Out of all permissible allocations of resources, it is desired to find one or ones which maximizes or minimizes some numerical quantity such as profit or cost.
Linear Programming Problem
Linear programming problem is the mthematical representation of constraint optimization problem.
Linear programming deals with that class of programming problem for which all relations among the variables are linear. The relations must be linear both in the constraints and in the function to be optimized.
Components of Linear Programming Problem
The four components of linear programming problem are as follows:
- Decision Variables
- Objective function
- Constraint Conditions
- Non-negativity Restrictions.
Decision Variables
Decision variables are the unknown quantities that the decision makers wish to find
Objective Function
The objective function is a linear mathematical expression of decision variables that needs to be maximised (in case of profit) or minimized (in case of cost).
Constraints
Constraints are nothing but the limitations that restrict the various alternatives available to the decision makers. Thus constraints are linear mathematical expression of decision variables in terms of availability and requirement of the resources.
The three types of constraints are less than or equal ($\leq$), greater than or equal ($\geq$) and equality $=$).
Non-negativity Restriction
The decision variables should always take non-negative values. That is decision variables should always be greater than or equal to 0.
General Linear Programming Problem
The general LPP can be described as follows :
Given a set of $m$ linear inequalities and / or equations in $n$ variables, we wish to find non-negative values of these variables which will satisfy the constraints and optimize (i.e. maximize or minimize) some linear function of the variables.
Mathematically, the general LPP can be written as
$$ \begin{equation}\label{obj} \max \text{ or } \min z = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n \end{equation} $$
subject to $m$ linear inequalities and / or equations
$$ \begin{eqnarray}\label{const}\nonumber a_{11} x_1 + a_{12} x_2 + \ldots + a_{1j}x_j + \ldots + a_{1n}x_n &\{\leq\; = \; \geq \}& b_1 \\\nonumber a_{21} x_1 + a_{22} x_2 + \ldots + a_{2j}x_j + \ldots + a_{2n}x_n &\{\leq\; = \; \geq \}& b_2 \\\nonumber \vdots \qquad\qquad \vdots \qquad\qquad \vdots &\{\leq\; = \; \geq \}& \vdots \\ a_{i1} x_1 + a_{i2} x_2 + \ldots + a_{ij}x_j + \ldots + a_{in}x_n &\{\leq\; = \; \geq \}& b_i \\\nonumber \vdots \qquad\qquad \vdots \qquad\qquad \vdots &\{\leq\; = \; \geq \}& \vdots \\\nonumber a_{m1} x_1 + a_{m2} x_2 + \ldots + a_{mj}x_j + \ldots + a_{mn}x_n &\{\leq\; = \; \geq \}& b_m \end{eqnarray} $$
and
$$ \begin{equation}\label{rest} x_j \geq 0,\; j = 1,2,\ldots,n \end{equation} $$
where constraints may be in the form of any inequality ($\leq$ or $\geq$) or even in the form of an equation ($=$). All the $a_{ij}$, $b_i$, $c_j$ are assumed to be known constants.
The function in equation \eqref{obj} is called the objective function. The conditions in \eqref{const} are called constraint conditions and the condition in \eqref{rest} are called non-negativity restrictions.
Endnote
In this tutorial you learn about what is linear programming problem?, what is the general form of linear programming problem? and components of linear programming problem
To learn more about linear programming problem, please refer to the following tutorials:
Let me know in the comments if you have any questions on Linear programming problem and your thoughts on this article.
