Linear Programming

We talked about some of the interesting statistical computations in my earlier posts. Now, let’s get into Linear Programming.

Programming here, does not refer to computer programming. It refers to statistical operations.

Linear programming helps in planning to obtain optimum result that meets a specific goal after considering all the possible options. It is widely used to calculate the optimum allocation of scarce resources among competing demands. Formulation of linear programing is the representation of the problem situation in a mathematical form.

Properties or prerequisites for linear programming model

  1. Relationship among the decision variables must be linear.
  2. A model must have an objective function
  3. Constraints like resource constraints should exist.
  4. None of the constraint should be a negative number

Steps for the formulation of linear programming model

  1. Identify the objective of the model
  2. Identify the suitable variables and their appropriate unit to measure
  3. Identify the required constraints and other parameters
  4. Assign right algebraic symbols to the objective function (Z) and the variables (x1, x2 … xn)
  5. Form the objective function z = c1x1 + c2x2 + .. .. .. + cnxn
  6. Include all the constraints
    ai1x1 + ai2x2 + .. .. .. +ainxn ≤ bi
    0 ≤ xj
    where i = 1 ~ m and j = 1 ~ n

Simplex Algorithm

This is an algorithm for starting at some extreme feasible point and by using a sequence of exchanges, moving on to other such points until a final solution point is found.

Example

Lets look at an example. A popular car maker in GST near Chennai has the following resources available per day.

  • 18 tonnes of raw materials
  • 9 hours of machine hours
  • 8 hours of man power

This manufacturing plant of the company gets 5 lakhs and 2 lakh as profit from SUV and Sedan type cars respectively.  How many SUV and Sedan cars should be produced by the company to maximize total profit?

Resources Requirement per unit Daily Availability
SUV Sedan
Raw material 2 1 18 tonnes
Machine 2 3 9 hours
Man Power 4 2 8 hours
Profit 5 2 lakhs

Let’s perform the steps one by one.

Identify the key variables

Let x1 be the number of SUVs
Let x2 be the number of Sedans

Define the objective function

Based on the profit, company gets 3 Lakhs and 1 Lakh as benefit from x1 and x2. So,

Zmax = f(x,y) = 5x1+2x2

Include the constraints

Availability of the raw materials, machine hours and man power are our constraints.

Raw material 2 x1+1 x2≤18
machine hours 2 x1+3 x2≤9
Man Power 4 x1+2 x2≤8

Non-negative constraints:

The plant cannot produce -ve cars. So,

x1≥0
x2≥0

Hence our linear programming model for this case is given as:

Max Z = 5x1+2x2

Subject to constraints,

2 x1+1 x2≤18
2 x1+3 x2≤9
4 x1+2 x2≤8
x1≥0
x2≥0

Graphical method

Remove the inequalities to form equations

2x1+1x2=18  ————– Constraint 1
2x1+3x2=9  ————– Constraint 2
4x1+2x2=8  ————– Constraint 3
x1=0
x2=0

Substitute x1 = 0 in first equation.

2x1+1x2=18
0x1+1x2=18
x2=18

Now substitute x2 = 0

2x1+1x2=18
2×1+0x2=18
x1=9

So our data points for first constraint is given as below

x1 0 9
x2 18 0

Similarly compute the data points for constraints 2 and 3.

Data points for constraint 2 is given below.

x1 0 4.5
x2 3 0

Data points for constraint 2 is given below.

x1 0 2
x2 4 0

Let’s plot the x-y or scatter graph now.

Maximation with Linear Programming with 3 constraints using graphical method

All our constraints are ≤. So we need to find an area in the graph which is lesser than all three constraints. This is highlighted in the below given graph.

Maximation with Linear Programming with 3 constraints using graphical method feasible area

So we have 4 data points a, b, c and d. Lets find those values from the graph.

  a b c d
x1 0 0.8 2 0
x2 3 2.5 0 0

So we have got 4 sets of values, which is to be substituted in the objective function to find the maximization.

Max Z = 5x1+2x2

Substituting the values of data point a – (0, 3).

Max Z = 5(0)+2(3) = 6.

Substituting the values of data point b – (0.8, 2.5).

Max Z = 5(0.8)+2(2.5) = 9.

Substituting the values of data point c – (2, 0).

Max Z = 5(2)+2(0) = 10.

Substituting the values of data point d – (0, 0).

Max Z = 5(0)+2(0) = 0.

So, based on our finding, 2 SUV and 0 Sedan would give us best profit.

You may look at the following tutorial videos –

Advertisements

2 thoughts on “Linear Programming

  1. Pingback: Linear Programming with LibreOffice Calc Solver | JavaShine

  2. Pingback: Linear Programming – Covering Model using LibreOffice Calc Solver | JavaShine

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s