Linear Programming Problem

Table to Content,

01.What is Linear Programming

Basic Terminologies
The process to define a LP problem.

02.Solve Liner Program by Graphical Method

03. Simplex Method

What is Linear Programming Problem

Linear programming is one of the simplest way to perform optimization it helps to solve some very complex optimization problems by making a few simplifying assumptions. Linear Programming is used for obtaining the most optimal solution for a problem with given constraints. It involves an objective function, linear inequalities with subject to constraints.

Eg:

consider a chocolate manufacturing company that produce only two types of 1 2 chocolates (A and B).Both chocolates require milk and chocolate as follow;

The Company has total of 5 units of milk and 12 units f chocolate. On each sale the company make profit of,

	Rs.6/= per unit A sold.
	Rs.5/= per unit B sold.

Let the total number of units produced by A=x

B=y

The total profit is given by the total number of units A and B produced, multiplied by its’ per unit profit of Rs.6/= and Rs.5/= respectively.

Profit Z max =6x+5y

As the above table, each unit A and b requires 1 unit of milk. The total amount of milk available is 5 units to represent as,
        1x+11 ≤ 5
        x+y ≤ 5

Also each unit of A and B requires 3 and 2 units chocolate respectively. The total amount of chocolate available is 12 units,
        3x+2y≤12

Now we have two more constraints, 
        x+y ≤5
        3x+2y≤15 
        x,y ≥ 0

The chocolate manufacturing company can make profit by the above inequalities have to be satisfied. There are some terminologies used in Linear Programming.

1. Decision Variables The decision variables are the variables that will decide output to solve any problem. We first need to identify the decision variables as above. eg: The total number of units for A and B denoted by x and y respectively are the decision variables. 2. Objective Function It is defined as the of making decisions as above example profit is the objective function. Zmax = 6x+5y

3. Constraints The constraints are the restrictions or limitations on the decision variables. In above example the limit on the availability of measures of milk of chocolate For all linear programs the decision variables should always take non negative values. It means values should be greater than or equal to 0. Steps to define a Linear Programming Problem 1.Identify the decision variables.

2.Write the objective function. 3. Mention the constraints. 4. Solve the problem. For a problem to be a LPP the decision variables, objective function and constraints all have to be linear functions. It all 3 conditions are satisfied it is called as Linear Programming Problem.

Solve LPP by using Graphical Method

There are multiple methods to solve the LPP. If you have only two decision variables , you should have used the graphical method to find the optimal solution.

Eg:

A farmer has 110 hectares piece of land and he decide to grow wheat and barley on that land. He can sell the entire production of wheat and barley. He wants to know how to plat each variety in the 10 hectares, given the costs, net profit and labour requirement according to following data.

The farmer has a budget of Rs.10 000/= and availability of 1200 man days during the planning horizon. Step 01: Identify the decision variables. The total area for growing wheat= x

The total area for growing barley= y Step 02:Write the objective function. The farmer earns a net profit of Rs.50/= for each hectare of wheat and 120 hours for each hectare of barley. Zmax =50x+120y

Step 03:Write the constraints. It is given that farmer has total budget of Rs.10 000/=. The cost producing wheat anxd barley per hectare is also given, 100x+200y ≤ 10 000 .The availability of the total number of man days for the planning horizon,

10x+30y ≤ 1200 The 3rd constraint is the total area present for plantation. x+y ≤ 110 The values of x and y will be greater than or equal to 0. x+y ≥ 0 The plot for the graph for above equations, first need simply all the equations. 100x+200y ≤ 10 000 x+y≤ 110 01

10x+30y ≤ 1200 x+y≤120 02

01-02,

x+2y-x-3y=100-120 -y =-20 y =20//

When y=20,

x+2y=100

x =60//

The values for x and y is (60,20) to maximize profit should produce wheat and barley in 60 hectares of land respectively.

Zmax =50x + 120y

Rs.5400/=

Simplex Method Simplex method is one of the most powerful and popular method for LPP. A linear programming function is in its standard from if it seeks to maximize the objective function

Z = c1 x1 + c2 x 2+…..+c nx n Subjects to Constraint, a11 x 1 + a12 x2……≤ b1 a21 x 1 + a22 x2……≤ b2

SLACK variables the corresponding system of constraint equation is, a11 x 1 + a12 x2…… a1n x n + S1 = b1 a21 x 1 + a22 x2…… a1n x n + S2 = b2

The variable S1 and S2 called SLACK variables. They are non negative numbers that are added to remove the inequalities from an equalities.

Eg: Zmax = x1 + 2x 2+3x3

S.T.C, x1 + x 2+ x3 ≤ 12 2x1 + x 2+ 3x3 ≤ 18

x1 , x 2, x3 ≥ 0

Step o1: Make standard form Zmax = x1 + 2x 2+3x3 +0S1 +0S2

x1 + x 2+ x3+S1 =12 2x1 + x 2+ 3x+ S2=18

Step 02: Find basic feasible solutions

x1 = 0 x2 =0 x3 = 0

S1 = 12 S2 = 18

Step 03: Display in a table

Incoming variable

Pivot Value

By observing Cj-Ej, mark the maximum positive value that column as a key column, variable is called as incoming variable. Then to get value bi should be divided into key column. Least positive value in 𝜃 column as know as the outgoing variable. 3 is the pivot value.

In next table pivot value should be 1 and other must be 0 (above and below values of pivot value)

When Cj-Ej values are 0 or negative the solution is optimal. Substitute the values to objective function to get the profit,

x1 = 0 , x2 = 9 , x3 = 3

Zmax = x1 + 2x2+3x3

= 0+(2*9)+(3*3)

=27//

Applications of Linear Programming

Linear Programming is heavily used in microeconomics and company management, such as planning, production, transportation, technology and other issues, either to maximize the income or minimize the costs of a production scheme. In the real world the problem is to find the maximum profit for a certain production.

Tutorial Created By B.A.S.U.Balasuriya & J.K.H.Nishadi