Sales Toll Free No: 1-855-666-7446

# Linear Programming

Top
 Sub Topics Linear Programming is a linear optimization process of mathematics. LLP is the abbreviated of linear programming. This programming is used to optimize different linear terms. There are two types of linear programming graphs linear equality or linear inequality graph according to this the linear programming equations are determined. In this process after finding the optimized values of particular region the next step is to substitute the values in cost equation and then find the most suitable optimum result which is said to be the solution for given set of equation.

## Linear Programming Definition

Linear programming Definition says that it is used to determine maximum profit or minimum cost or minimum profit or maximum cost out of list of different Linear Equations or relationships. LP problems can involve only two variables. These problems can be solved by graphical techniques.

## Linear Programming Duality

The theory of duality is very important concept within the field of linear programming, but it has many applications in several related areas like networking, gaming theory and non linear programming.There are two theorem of duality, Weak duality theorem and Strong duality theorem. Whenever there is a linear programming problem, we need to solve two problems. One is prime resources allocation and another in dual resources valuation problem. In prime problem n will be the variables and m will be constants. In dual problem m will be the valuation and n will be the constants.
Weak duality theorem:
$c^{T}x >= b^{T}y$

Strong duality theorem:
$c^{T}x^{*} = b^{T}y^{*}$

## Integer Linear Programming

The integer linear programming is a optimization program in which all the variables or some variables are restricted to be integer. The two main applications of ILP are, variables represent quantities and variables represent decisions. If ILPs are not in a standard form then it can be converted into a standard form by replacing variables or eliminating inequalities.

## Linear Programming Graph

Now let us consider an example assuming 'Z' as cost of set of equations or inequalities. And there are three inequalities constituting in set of linear equations. Firstly we will find out the satisfiable values of 'x' and 'y' for each equation and create a graph which involves all three equations as part of it. These three equations form a common region or may be uncommon region which satisfies the cost for a set of inequalities. This region if it is common then optimized maximum profit is and if regions are not common then the cost found will be minimum. Consider the following graph, in this way we have a set of two inequalities say:

x + y < 2 and x = 2. One is an inequality and other one is an equation.

The region thus obtained considering these two lines and cost is as follows:

## Linear Programming Simplex Method

LP simplex method is one of the most common technique to solve LPP. Any business or industry's first is to make decision, so decision making is the most important aspect. The computing steps of simplex method of linear programming are given below,

Step 1: Convert the given into standard maximization linear programming problem.

Step 2: To initiate the iterations select an initial basic solution.

Step 3: Check the objective function and find whether some non basic variable exist or not, that improve the objective function.

Step 4: Test the result for optimality.

Step 5: Continue the above steps until either get an optimum solution or any unbounded solution.

## Linear Programming Graphing Method

Linear Programming Graphing Method is an essential part of mathematics to solve problems of Linear Programming involving Linear Inequalities.

We can find applications of Linear Programming Graphical method in commercial and administration fields to plan the use of resources. It’s an important tool to reduce problems that contain a large number of variables making them simple and easy to understand.

To solve Linear Programming Graphing first you need to find all inequalities that are possible in the problem. For example, if you are trying to Set value of a certain quantity to maximize your profits, there can be a relationship between the value of that quantity and its sale in the market. This relationship can be described by just drawing a straight line graph describing profitability on one side and non - profitability on other side. There can be several situations in linear programming problem that you need to highlight in order to optimize the problem.

All lines of such inequalities have to be graphed on one graph paper. Intersection of these lines will form a polygonal shape inscribing area within the boundaries that describes the LPP. But it is not necessary that area will always be bounded, it can be open from one or more sides. Lines that are responsible for Intersection with Polygon represent the factors that were counted by factors making the boundaries of polygon. Next step would be optimization of your problem on complete analysis. Important factors or variables are optimized to make them stay inside the polygon. Say if one side of polygon is formed by line that represents the value of your quantity, stay on the side of that line inside of polygon. Also allowing other side of the polygon to represent the market sale of that quantity. This is all about linear programming graphing.

## Linear Programming Examples

Some of the solved examples of linear programming are given below:
Question 1: Solve the given linear program maximize $4x_{1} + 5x_{2}$ subject to

$x_{1} - x_{2} ≥ 3$

$5x_{1} + 4x_{2} ≤ 35$

$x_{1} ≥ 0$

$x_{2} ≥ 0$

Solution:

Given:

$5x_{1} + 4x_{2}$

and

$x_{1} - x_{2} = 3$

Solving simultaneously, rather than by reading values off the graph, we have that

$5(3 + x_{2}) + 4x_{2} = 35$

$15 + 5x_{2} + 4x_{2} = 35$

$15 + 9x_{2} = 35$

$x_{2}$ = $\frac{20}{9}$

$x_{2} = 2.22$

$x_{1} = 5.22$

Now the maximize is

= $4x_{1} + 5x_{2}$

= $4(5.22) + 5(2.22)$

= $31.98$
Question 2: A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week. Formulate this problem as a linear programming problem.

Solution:

Step 1:  Variables

Let

$x_{T}$ = number of tables made per week

$x_{C}$ = number of chairs made per week

Step 2:  Constraints

Total work time

$6x_{T} + 3x_{C}$

customer demand

$x_{C} >= 3x_{T}$

storage space

$(\frac{x_c}{4})$ + $x_{T}$
all variables >= 0

Step 3:  Objective

maximize $30x_{T} + 10x_{C}$

The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of

$(\frac{x_c}{4})$ + $x_{T} = 4$ and $6x_{T} + 3x_{C} = 40$

Solving these two equations simultaneously we get xC = 10.667, xT = 1.333 and the profit = £146.667

$x_{C} = 10.667$, $x_{T}= 1.333$ and the profit = £146.667