Linear Programming Problem

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:

Linear Programming Problems

Let me know in the comments if you have any questions on Linear programming problem and your thoughts on this article.

VRCBuzz co-founder and passionate about making every day the greatest day of life. Raju is nerd at heart with a background in Statistics. Raju looks after overseeing day to day operations as well as focusing on strategic planning and growth of VRCBuzz products and services. Raju has more than 25 years of experience in Teaching fields. He gain energy by helping people to reach their goal and motivate to align to their passion. Raju holds a Ph.D. degree in Statistics. Raju loves to spend his leisure time on reading and implementing AI and machine learning concepts using statistical models.

Leave a Comment