Linear Programming

A problem given in the form of following format is called linear programming problem+/L.P problem

Z = Rs(10x+4y)........... (1)

Maximize subject to  ................ (2)

3x + 5y ≤ 50 & 2x + y ≤ 100 .......... (3)

x, y ≥ 0 ............ (4)

A L.P problem usually consist of

1. Objective function
2. Objective
3. Constraint
4. Non-negativity condition (NNC)

Objective function: A linear function representing the total profit/ total cost is called objective function

Objective: The process of maximizing the total profit or minimizing total cost is called objective. A l.P problem should have one and only one objective

Constraint: The restrictions on the availability of resources, that are expressed in the form of linear inequalities are called constraints. A L.P problem should have minimum 2 constraints

Non-negativity condition (NNC): In L.P x&y represent the no. of units of the product produced & sold. Therefore they can't be negative

 

A L.P problem can be solved by:

• SIMPLEX method
• Graphical Method

 

SIMPLEX method:

A L.P problem with 2 or more products can be solved by a specific method known as simplex method. This method consist of systematic calculations that are indicated in a tabular form known as simplex tables. For applying simplex method the problem should be modified i.e. all the constraints should be expressed in the form of equality sign.

Modification Rule:

All the constraints of less than (≤) type should be converted into equality sign by subtracting a variable on the left hand side of the equality sign. The variable thus attached is called slack variable.

The contribution/unit of slack variable towards profit is REO.

Initial basic solution:

If a L.P problem is given, the constraints should be converted into equation. Assign each decision variable (x,y) =0. The resulting solution is called initial basic solution. (Discussed in videos)

TYPE1:  SIMPLEX Method

Consider the following L.P problem

Z = 10X₁ + X₂ + 2X₃

Maximize subject to

X₁ + X₂ – 2X₃ ≤ 10

4X₁ + X₂ +X₃ ≤ 20

X₁, X₂, X₃ ≥ 0

The given LP problem has a decision variables namely X₁, X₂, X₃ ( the variables figuring in the objective in are called decision variables). The problem has 2 constraints. They can be converted into equation by attaching 2 slack variables.

X₁ + X₂ – 2X₃ + S₁ = 10

4X₁ + X₂ +X₃ + S₂ = 20

Put each decision variable = 0 i.e. X₁, X₂, X₃ = 0

therefore S₁ = 10 & S₂  = 20 ( initial sol.)

Constructing table no.1

1. Select largest NER & encircle & put an arrow as shown (see 10 in last row)
2. Encircle that column & name it as Key column (KC). The nos. inside the KC are called Key column no's for S₁ & S₂ 
3. Divide the qty by key no's , indicate the results in col. 9 ( 10 & 5 in last column). Select the least +ve value. (  5 in this case)
4. Encircle that row and name it as key row (KR)
5. The element lying in both KC & KR is called Pivotal Element (PE). ( 4 highlighted in orange)
6. Prepare table two:

All the entries in NER are Zeroes or negative , Hence simplex process is over and optimal sol. is arrived.

Perform the following for the table Two:

1. Mention the incoming variable name & its profit. Divide the key row by the pivotal element & indicate the result.
2. Indicate the slack variable (S₁ in this case) & its profit. Calculate the following ( write the old no's & calculate the new no's by given formula:Key col of S₁ * KR / pivotal element, (here key col for S₁ is 1 & pivotal no is 4), find the difference of the two rows

Indicate the results against  S₁ in the simplex table.

Optimal Sol.

X₁  = 5

X₂   = 0

X₃  = 0

Max Z = Rs. 50 (10*5)