North West Corner Rule (NWCR)

Q1.Obtain the Initial Basic Feasible Solution to a TP , whose cost and requirements are given:

Origin/Destination       D1         D2              D3          Supply
 O1                              2            7                4              5
 O2                              3            3                1              8
 O3                              5            4                7              7
 O4                              1            6                2             14
Demand                       7            9                18           34

Soln:
STEP I: 
Sum up Demand and Supply ,

Eai=Ebj=34, The given TP is a balanced one and there exists a feasible solution to TP.

STEP II:

-----------------
    5
2         7       4         5
3         3       1         8      
5         4        7        7        
1         6        2        14    
-----------------              
7         9         18

  In this step select the North West corner cell and check its demand and supply, among these two which has the minimum value put it at the top of the NWC  cell. and cancel it . If the supply is the minimum value cancel row other wise cancel column..

----------------
    2
3      3        1       8    
5      4        7        7  
1      6        2        14
--------------
2       9        18

 As in the previous step we have minimum supply we have to reduce the value in   demand , (7-5=2)this becomes the new demand value for the next one.   

----------    
   6              
3        1     6  
4        7      7
6        2      14
---------
9      18

------------
     3
4          7        7
6          2        14
----------
3        18

----
   4
7       4
2      14
---
18

-----
    14
2        14
-----
14

Both demand and supply are the same for a balanced TP.

STEP III:

The solution is given by:

   5
2          7        4

   2          6
3          3         1

               3          4      
5           4         7        

                          14
1           6         2

Finally for the given problem allocate their respective demand and supply based on  the places where they get strike out.This is IBFS

Total Cost =(2 x 5)+(3 x 2) + (3 x 6)+( 4 x 3)+(7 x 4)+(2 x 14)
                 = 10+ 6+18+12+28+28
                  =Rs.102

Transportation Problem (TP)

• Feasible Solution: Any set of non-negative allocation which satisfies row and column sum is called a feasible solution.
• Basic Feasible Solution(BFS): A feasible solution is called BFS if the number of non-negative allocation is equal to m+n-1, where m- number of rows , n- number of columns
• Non Degenerated Basic Feasible Solution: Any feasible solution of a TP containing m origins and n destinations are said to be Non Degenerated, if it contains m+n-1 occupied cells and each allocation is in independent positions.
• Allocations are said to be independent if it is impossible to form a closed path.
• Closed Path: It means by allowing horizontal and vertical lines and all the corner cells are occupied.

• Degenerated Basic Feasible Solution:If a BFS contains less than m+n-1 non-negative allocations it is said to be degenerated.

OPTIMAL SOLUTION:

It is a feasible solution which minimizes the total cost.

The solution of a TP can be obtained in two stages namely

1. Initial solution
2. Optimal solution

Initial solution can be obtained by any one of the following methods

• North West Corner Rule(NWCR)
• Least Cost Method (LCM) or Matrix Minima Method
• Vogel's Approximation Method (VAM)

Transportation Problem (TP)

TRANSPORTATION PROBLEM:

Its one of the sub classes of LPP. 

The Linear Programming model is representing TP is given by:

The given transportation problem is said to be blanced if :

Graphical Method Example

Q1.Solve the following  LPP. This is an example for unbounded solution.

Maximize z = 3x1+2x2
subjected to  x1-x2 <= 1
                    x1+x2 >= 3
and x1,x2 >=0

Soln:                    

STEP I:
Let x1-x2 =1 --(1)
      x1+x2 =3 --(2)

(1) x1- x2 =1             (2) x1+ x2=3
Put x1=0                    Put x1=0
[x2 = -1] (0,-1)            [x2=3] (0,3)
Put x2=0                    Put x2=0
[x1=1] (1,0)                [x1=3] (3,0)

(1) (1,-1)                     (2) (3,3)

STEP II:

The solution space is unbounded. The maximum value of z occurs at infinity. Hence the problem has unbounded solution.


Q3. Max z=x1+x2
Subjected to x1+x2 <=1
-3x1 + x2 >=3
and x1, x2>=0.

This problem will provide a solution where there will be no common point and hence the feasible region cant be decided.

Graphical Method

 Graphical Method:

Feasible Region:

The points lying in the common region that satisfies all the constraints simultaneously.

The common closed region thus obtained is called the Feasible Region.

Examples for Graphical Method:

Q1. Solve the following LPP by Graphical Method:

Maximum z = 3x1+4x2;

Subjected to 5x1+4x2 <= 200

                    3x1+5x2 <= 150

                    5x1+4x2 >= 100

                    8x1+4x2 >= 80

and x1,x2 >=0

Soln:

STEP I:

Let  5x1+4x2 =200 --- (1)

       3x1+5x2 =150 ---(2)

       5x1+4x2 = 100 ---(3)

       8x1+4x2 = 80  ---(4)

(1) 5x1+4x2 = 200                          (2) 3x1+5x2=150                 (3)5x1+4x2=100

Put x1=0; 4x2=200                           Put x1=0; 5x2=150                 Put x1=0; 4x2=100

        [x2=50]   (0,50)                              [x2=30]  (0,30)                       [x2=25]  (0,25)

Put x2=0; 5x1=200                           Put x2=0; 3x1=150                 Put x2=0; 5x1=100

        [x1=40] (40,0)                                [x1=50] (50,0)                        [x1=20]  (20,0)

(1) --(40,50)                                      (2) --(50,30)                             (3) --(20,25)

(4)8x1+4x2=80

Put x1=0; 4x2=80

      [x2=40]  (0,20)

Put x2=0; 8x1=80

      [x1=10]  (10,0)

(4) --(10,20)

STEP II:

STEP III:

 C is the intersection of  3x1+5x2=150 --(i)

                                     5x1+4x2=200 --(ii)

(i) x 4 => 12x1+20x2=600

(ii) x 5 =>25x1+20x2=1000

               (-)     (-)       (-)

               -----------------------

               -13x1         = -400

                       [x1= 30.8]

 3x1+5x2=150

3(30.8) + 5x2 =150

5x2=57.6

  [x2=11.52]

C(30.8,11.52)

     CORNER POINTS                   VALUE OF Z

     A(20,0)                                            60

     B(40,0)                                           120

     C(30.8,11.52)                                 (138.48)

     D(0.30)                                           120

     E(0,25)                                            100

The unique optimal solution  is given by max z= 138.48 for x1= 30.8 and x2=11.52.

Explanation:

As per the given problem , first assume all the constraints as equality form. Next "Put x1=0 and x2=0" and find out their respective points in the form of (x1,0) (0,x2) and (x1,x2).

 Develop a graphical representation by substituting (x1,x2) for all the subjected constraints.In this graph locate the points where the lines intersect with x1 and x2 .

The corner points of the feasible region is mentioned as A(x1,x2) B(x1,x2) C(x1,x2) D(x1,x2) and E(x1,x).

Here all the corner points will have their respective values except the intersecting point "C".

To find their values , identify the lines which intersect to form the point "C" and find the values of C.

Finally provide all the corner points of the feasible region and mention their corresponding optimal solution by substituting the values to the maximize equation.

        

Linear Programing Problem LPP Examples

Q1. A Company produces two types of watches one for gents and another for ladies, both are to be processed on three machines, the processing time required and the total time available per week on each machine are as follows:

MACHINE          MODEL                 AVAILABLE TIME
                    GENTS    LADIES

M1                 3                3                    36
M2                 5                2                    50
M3                 2                6                    60

The contribution of profit for each unit of gents watch is Rs.20 and each unit of ladies watch is Rs.30. How should the company schedule the production to the maximum profit formulate the problem as LPP.

Soln:
Maximize z = 20x1+30x2
Subjected to :
3x1+3x2 <= 36
5x1+2x2 <= 50
2x1+6x2 <= 60
and decision variables x1, x2 >=0.
Explanation:
As per the problem given we have two variables
(i)Gents watch--x1 (ii)Ladies watch --x2
They are processed in three machines therefore we will have 3 sets of constraints.
We have to maximize the profit, hence the problem should maximize the profit therefore the objective function should be maximize z.

Q2. A leading leather good company manufactures two types of cricket ball A and B. Each type of ball requires work by both skilled and semi skilled employees , the available time per month and time required for each ball is given below.

TYPES OF EMPLOYES             MANUF. TIME                AVAILABLE TIME
                                               A                    B
SEMI SKILLED                      2                     3                       320
SKILLED                                4                     6                       600

The cost of the hour of semi skilled labor is Rs.10 & skilled labor is  Rs.15. To meet the monthly demands for at least 60 balls of type A and at least 40 balls of type B must be manufactured. Formulate LPP to minimize the cost of production.

Soln:
Minimize z = (2hrs)(10Rs)x1+(4hrs)(15Rs)x1+(3hrs)(10Rs)x2+(6hrs)(15Rs)x2
                 =80x1+120x2
Subjected to
2x1+3x2 <= 320
4x1+6x2 <= 600
x1>=60
x2>=40

and decision variables x1,x2 >=0

Explanation:
As per the problem given we havve two types of variables
(i) Ball A--x1 (ii)Ball B --x2
They are processed by two types of employees Skilled & semi skilled hence two sets of constraints.
We have to minimize the cost of production hence the objective function Minimize z.
Cost of labor and number of balls to be manufactured should be calculated as the objective functions.
Here the number of balls to be manufactured is provided as at least therefore the decision variables are given as >=

Linear Programing Problem(LPP)

Linear Programming Problem(LPP)

An equation with same degree/variable/power is a Ist order equation.

LP model has few basic elements which are described below.

Decision Variable  - The variable whose values determine the solution of a problem.

Objective function - the generalized format of an objective function is given as

maximize or minimize z =c1x1+c2x2 +.........+cnxn

where c1,c2,...cn are cost variables and x1,x2 ...xn are decision variables.

Technical Coefficient : (aij)

aij is the amount of resource i required for the activity j where i varies from 1 to m and j varies from 1 to n.

The generalized format of technical coefficient is 

[ a11 a12 .....a1n

  a21 a22 .....a2n 

  .

  .

  am1 am2 ... amn ]

Resource Availability: (bi)

The constant bi is the amount of resource i available during the planning period.

The general format is given as,

[b1

 b2

 .

 .

 bm]

Set of Constraints:

A constraint is a kind of restriction on the total amount of a particular resource required to carry out activities atvarious levels.

The generalized format is given as:

a11x1+a12x2+...+a1nxn <=,= or  >= b1

a21x1+a22x2+...+a2nxn <=, = or >= b2

.

.

am1x1+am2x2+...+amnxn<= ,= or >=bm

Non negativity constraint:

Each and every decision variable in LP model is a non negative variable.

The general format is

x1,x2..xn >=0

Mathematical formulation of LPP:

The general format is given by

Maximize/Minimize z = c1x1+c2x2+...+cnxn  --- (1 )

subjected to constraints

a11x1+a12x2+...+a1nxn <=,= or >= b1

a21x1+a22x2+...+a2nxn <=,= or >= b2

.                                                                        ---(2)

.

an1xn+anx2+...+amnxn<= , = or >=bm

and x1,x2,...xn >=0                                         ---(3)

variables are involved .

Definition of LPP :

Linear Programming problem deals with optimization of functions of decision variables known as objective functions subject to a set of simultaneous linear eqution known as constraints.

Applications:

LP technique is used in many indusrial and economic problems , airlines , railways, food processing etc.,

 

Operation Research Introduction

OPERATION RESEARCH -INTRODUCTION

OPERATION RESEARCH:(OR)

• It is the study of optimization technique.
• It is an applied decision theory.
• Rapid Development and invention of new techniques occurred since the world war II because of the necessity to win the war with the limited resources available. Different teams had to research on military operations , in order to invent techniques to manage with the available resources so as to obtain the desired objective.

SCOPES / USES / APPLICATIONS OF OR:

1. Project Management
2. Inventory Control Problems
3. Maintenance and replacement Problems
4. Assignment of jobs to applicants in order to maximize the total profit or minimize the total cost
5. Shortest route Problem like Travelling Salesman Problem
6. Game theory
7. Sequencing and scheduling problems

ROLES OF OR IN BUSINESS & MANAGEMENT:

1. Marketing Management- Product Selection ,competitive strategies, Advertising strategy
2. Production Management
3. Finance Management
4. Personal Management
5. Purchasing and Procurement
6. Distribution