NETWORK SCHEDULING BY PERT/CPM

PERT- Program Evaluation Review Technique
CPM-Critical Path Method

NETWORK SCHEDULING
Its a technique used for planning and scheduling large project.Its a method for minimizing troubleshoots such as delays, interruption.
There are two basic planning & Control techniques.:
   PERT
   CPM

NETWORK:
Its the graphical representation of logically and sequentially connected arrows and nodes representing activities and events in the project.Its an arrow diagram.

ACTIVITY:
An activity represents some action and its  a time concuming effort necessary to complete a parrticular part of the overall project.

EVENT:
The beginning and the end points of an activity are called events/nodes.

MERGE EVENT:
Its not necessary for an event to be ending event for only one activity as it can be the ending event of two or more activity such a event is defined as merge event.

BURST EVENT:
If the event happens to be the beginning event of two or more activities then they are called as Burst event.

We have the following types of activities

1. Preceding
2. Succeeding
3.Concurrent
4.Dummy Activity

DUMMY ACTIVITY:
Certain activities which neither consume type or resources but are used simply to represent a connection/link between events are known as Dummy Activity.

CONSTRUCTION OF NETWORK:
Construct the network for the project whose activities and preceding relationships are shown below

ACTIVITIES            A              B               C                D             E             F
IMMEDIATE    
PREDECESSOR     -                 A              A                -               D           B,C,E

DOMINANCE PROPERTY

Q1. Solve

                        Player B
                          B1    B2    B3
Player A   A1   [ 1      7        2
                 A2     6      2        7
                 A3     5      1        6]

Soln:
STEP 1:
Find out the maximin and minimax values

 [ 1      7        2     1
    6      2        7    2     maximin=2
    5      1        6]   1

   6        7        7
minimax=6

maximin != minimax
Therefore no saddle point.

STEP II:
Now compare each row and check whether they are minimum values. If so then delete that row.

Compare A1 and A2 , here few values are minimum and few are maximum.
Now compare  A2 and A3, A3 has minimum values therefore delete A3.

By dominance Property,       B1       B2        B3
                                    A1    1           7         2
                                    A2     6          2         7
STEP III:
Now compare each column and check whether they are maximum values. If so then delete that column.

Compare B1 and B2 , here few values are minimum and few are maximum.
Now compare  B1 and B3, B3 has maximum values therefore delete B3.

          B1         B2
A1     1             7        1
A2     6             2        2         maximin=2
           6             7
minimax=6

maximin!=minimax
Therefore no saddle point

STEP IV:
                a22-a12
p1=--------------------------
       (a22+a11)-(a12+a21)

p1=1/2     p2=1/2

             a22-a21
q1=--------------------------
       (a22+a11)-(a12+a21)

q1=2/5    q2=3/5

                            a11a22-a21a12
value of game=-------------------------- =4
                        (a22+a11)-(a12+a21)

SA= [ A1       A2        A3
          1/2        1/2        0]

SB=[B1       B2         B3
        2/5      3/5          0]

GRAPHICAL METHOD FOR GAME THEORY

Q1.Solve the following 2 x 3 game graphically

                               Player B
Player A    [ 1          3         11
                    8          5          2]



STEP I :
 A's expected pay off against B's pure move is given by:


B's PURE MOVE                     A's EXPECTED PAY OFF E(P)
     B1                                              E1(P)=8-7P1
     B2                                              E2(P)=5-2P1
     B3                                              E3(P)=2P1+2

STEP II:
Now for the graph consider Axis 1 as  A2 and Axis 2 as A1

STEP III:
The reduced Pay off matrix is given by

          B2           B3    --------> the intersection point
A1 [   3              11       3
A2      5               2]      2     maxmin=3

           5               11
minimax=5

maxmin != minmax
Therefore  there exists no saddle point

P1=9/11          p2=2/11

q1=3/11           q2=8/11


Value of game = 49/11

The optimal Strategy is given by
            [  A1          A2
SA  =      9/11       2/11]

           [  B1          B2       B3
SB =      0             3/11     8/11]


NOTE:
The left out matrix value is given as '0'
For 2 x n matrix find lower envelope, find maximin (maximum values)
For m x 2 matrix find upper envelope, find minimax (minimum values)

GRAPHICAL METHOD FOR GAMES 2 x n / m x 2 MATRIX

Consider the following 2 x n games

           B1       B2 .............Bn
A1 [    a11       a12.............a1n
A2      a21       a22.............a2n]


Let the mixed strategy for Player A is given by
          [  A1        A2
SA =     P1        P2]         such that p1+ p2=1   and p1,p2 >=0


Now the Pure Strategy for A available to B would be as follows

B's PURE MOVE                   A's EXPECTED PAY OFF
    B1                                         E1(P)=a11P1+a21P2
    B2                                         E2(P)=a12P1+a22P2
     .
     .
     .
     .
    Bn                                         En(P)=a1nP1+a2nP2

GAME THEORY : (WITHOUT SADDLE POINT)

Q1.Solve the following Pay off Matrix

                   B1         B2
     A1   [   5              1
     A2       3              4]

Soln:

STEP I:
Find the row minima and colmn maxima, and find out the maximin amd minimax values.

[5      1       1
 3      4]      3        maximin=3

 5       4
minimax=4

maximin != minimax
Therefore there is no saddle point.

              a22-a12
p1=   --------------------
        (a11+a22)-(a12+a21)

p1=(4-1) / (5+4)-(1+3)

p1=3/5      p2=1-p1=1-3/5=2/5  
p2 = 2/5


        a22-a21
q1=   --------------------
        (a11+a22)-(a12+a21)

q1=1/5    q2=4/5

                            a22a11-a12a21
Value of game= ---------------------------   =17/5
                             (a11+a22)-(a12+a21)

Optimum Strategies are given by
       
           [ A1        A2
SA=     3/5        2/5]

             [B1       B2
SB =       1/5      4/5]

GAMES (2 x 2) WITHOUT SADDLE POINT

Consider a 2 x 2 , 2 person zero sum game without any saddle point having the pay off matrix for player as

          B1       B2
A1  [ a11        a12
A2    a21        a22]

The optimum strategy for A is given as
              [  A1       A2
 SA  =       p1        p2]

The optimm strategy for B is given as
            [ B1        B2
SB =      q1         q2]

             a22-a12
p1= ---------------------
       (a11+a22)-(a12+a21)

p1+p2=1
p2=1-p1


             a22-a21
q1 =  ----------------------
          (a11+a22)-(a12+a21)

q1+q2=1
q2=1-q1

                              a11a22 - a12a21
Value of game  = -----------------------------------
                              (a11+a22)-(a12+a21)

Game Theory Example

Q1.Solve the game whose Pay off Matrix is given by

                           B1          B2          B3           Player B
Player A  A1   [  1              3            1
               A2       0             -4          -3
               A3       1              5           -1]


Soln:
STEP I:
Find out the Row minima and column maxima.

              [1       3       1        1
               0       -4      -3      -4        maximin=1
               1        5       -1]     -1

               1         5        1
  minimax=1

STEP II:
maximin=minimax=1
There exists a saddle point value of game = 1
The optimal strategy is (A1,B1)    -->  this  value is the intersection of maxima and minima.
The game is strictly determined since maximin=minima   is not equal to  0

Q2. Solve:

[ 0      2
 -1      4]

Soln:
STEP I:
     [ 0      2   0
      -1      4]  -1     maximin=0
       0       4
minimax=0

STEP II:
maximin=minimax=0
there exists a saddle point value of game=0
The optimum strategy is (A1,B1)
The game is fair since maximin=minimax=0

MAXMIN MINIMAX Principle

MAXIMIN=MINIMAX PRINCIPLE

MAXIMIN- Maximum of  Minimum among the row
MINIMAX- Minimum of Maximum among the column

If maximin=minimax value then the corresponding stratifies are called Optimal Strategies and the game is said to have a Saddle Point.
The value of the game is given by the saddle point.

SADDLE POINT:
Saddle point is the position in which the maximum of row coincides with the minimum of column maxima.

Game Theory

COMPETITION:
Its a watch word of modern life.A competitive situation is called a game.
The term game represents the conflict between two or more parties.
STRATEGY:
It is defined as a complete set of plans of action.Its a decision rule for making a choice fom the list of course of action.
Two types of Strategy:
1. Pure Strategy
2. Mixed Strategy

A strategy is called pure if one knows in advance of the play that its certain to be adapted irrespective of the strategy the other player might choose.

The optimal strategy mixed for each player may be determined by assigning to each strategy its probability of being chosen.
ie., the probabilistic combination of available choices of strategy.

PAY OFF:
Pay off is the outcome of playing the game.If a Player 'A' has 'm' course of action and Player 'B' has 'n' course of action then the Pay off matrix may be constructed as

                      Player B
                      1          2          ........................ n
                1[ a11     a12         ................... ....a1n
Player A  2   a21    a22       ...........................a2n           -----> Out come of A
                .
                .
                .
                m    am1     am2   .........................amn]
----> Out come of B

TYPES OF GAME:
1. 2 Person Game
2. n Persons Game

ZERO SUM GAME:
Its one in which the sum of payment to all the competitors is zero for every possible outcome of game.

Sum of points won= sum of points lost

TWO PERSON ZERO SUM GAME:
Gain of one player=Loss of other player

A game with 2 players where the gain of one player equals to the loss of other.

TSP Example

Q2.A salesman has to visit 5 cities the distance between the 5 cities are as follows:

                             To City
                          A         B         C         D           E

From City   A[infi         7            6          8            4
                   B 7         infi            8          5            6
                   C 6           8           infi         9            7
                   D 8           5            9        infi            8
                   E  4           6            7          8           infi]

If the sales man starts from city A and has to come back to his starting point which route should he select so that the total distance covered is minimum.

Soln:'

If we solve this problem, the final distance matrix will be.

           A             B               C              D           E
A      infi              3                0              4             0
B       3              infi                1              0             1
C       0               1                infi             2             0
D       4               0                  2            infi            3
E        0               1                  0             3           infi

The travel is given as A-->E-->B-->D-->C-->A

Distance=4+5+6+9+6
             =30 Km

TSP Example

Q1.A Travelling salesman has to visit 5 cities the cost of going from one city to another is shown below.

                    A        B        C        D        E
From  A [  infi         4         10      14        2
City    B     12       infi         6        10        4
          C     16       14         infi        8       14
          D      24       8          12        infi     10
          E        2        6           4        16      infi ]

Soln:

STEP I:
Process row wise

[ infi   2      8      12      0
   8    infi     2       6      0
   8     6     infi      0      6
  16    0      4      infi     2
   0     4      2      14    infi ]

STEP II:
 Process column wise. Strike out either horizontally / vertically in such a way that maximum number of zeros are covered.

[ infi     2      6     12     0
  8      infi      0      6     0
  8        6     infi     0     6
 16       0      4     infi    2
  0        4      0     14   infi ]

STEP III:
Number of Straight lines N=5
Order of matrix n=5
N=n. Therefore the optimal solution is

                   A             B               C             D           E
A     [       infi               2                 6           12            0
B              8               infi                 0             6            0
C              8                 6                infi            0            6
D             16                0                 4            infi           2
E               0                 4                 0             14         infi ]

A-->E; E-->A          B-->C;C-->D;D-->B

A-->E-->A;
B-->C-->D-->B     There is a break in the travel.

STEP IV:
When this situation occurs find the minimum value from the above cost matrix. Here it is  2 cancel this value and the other minimum value '0' in that row.

                   A             B               C             D           E
A     [       infi               2                 6           12            0
B              8               infi                 0             6            0
C              8                 6                infi            0            6
D             16                0                 2            infi           2
E               0                 4                 0             14         infi ]

A-->B;   B-->C;   C-->D;  D-->E;  E-->A

therefore the optimum sequence is A-->B-->C-->D-->E-->A
                                                    4+6+8+10+2
cost=Rs.30

Travelling Salesman Problem (TSP)

Assuming the salesman has to visit 'n' cities.He wishes to start from a particular city visit each city once and return to his starting point.His objective is to select a sequence in which the total travelling time is minimized.

MATHEMATICAL FORMULATION:
Let Cij be the distance or time or cost of going from city 'i' to city 'j'.
Let the decision variable Xij=1, if the salesman travels from city'i' to city 'j', otherwise 0.
The objective is to minimize the travelling time.

Hungarian Method- Unbalanced Assignment Problem

Q1.
                   Machines
                 A        B          C          D        E
Jobs   1[    4         3          6           2         7
          2[     10       12       11          14       16
          3[    4          3         2            1        5
          4[    8          7         6            9         6]

Soln:
STEP I:
The given matrix is unbalanced matrix.Hence add a row of "0"

[ 4    3     6      2       7
  10  12   11    14      16
  4      3    2     1        5
  8     7      6    9        6
  0     0      0     0       0]

STEP II:
Process row wise.
[ 2     1      4     0     5
  0     2      1     4     6
  3     2      1     0     4
  2     1       0     3     1
  0     0       0     0     0]

Number of straight lines N=4
Order of matrix n=5
N<n

Therefore the smallest value   in the previous matrix is  "1" subtract from the remaining values and add in the intersecting points.
[ 2   0  3  0  4
  0   1   0  4  5
  3   1   0  0  3
  3   1   0  4  1
  1   0   0  1   0]

Number of Straight Lines N =5
Order of Matrix n=5
N=n

Assign the jobs to machines.
      A        B         C         D         E
1[  2          0         3          0         4
2[  0            1        0          4         5
3 [ 3            1        0          0         3
4 [3            1        0           4        1
5[ 1           0         0           1         0]


1----->B  ; 2-->A ; 3-->D;  4---> C ; 5-->E

Cost= 3+10+1+6+0
       =Rs.20

      

Hungarian Method

Q1. Using the following Cost matrix determine (i) Optimal Job Assignment
                                                                       (ii)The cost of the assignment


                                       Jobs
                              1          2           3           4          5
Mechanic    A[     10          3            3           2          8
                   B       9            7           8           2           7
                   C       7            5           6           2           4
                   D       3            5           8           2           4
                   E       9            10          9           6         10


Soln:
STEP I:
Since the given matrix is a square Matrix (5 x 5) its balanced.
STEP II:

Process row wise

[ 8  1   1   0  6
  7  5   6   0  5
  5  3   4   0  2
  1  3   6   0  2
  3  4   3   0  4]

STEP III:

Process  Column wise for the above matrix

[ 7   0   0    0    4
  6   4   5    0    3
  4   2   3    0    0
  0   2   5    0    0
  2   3   2    0    2]

STEP IV:
Now we have drawn horizontal and vertical lines in such a way that most of the zeros are covered.
The number of Straight lines N=4
The order of matrix n=5
N<n

STEP V:
Since N<n
Therefore find out the smallest value from the above matrix .The smallest value is "2". Now subtract 2 fro the remaining values . Add "2" in the intersecting places "&" and "$" in the first row are the intersecting points.

[ 9  0   0  2   6
 6   2   3   0   3
 4   0   1   0   0
 0   0   3   0   0
 2   1   0   0   2]

Here all the columns are striked out as we have to cover most of the zeros.
Number of Straight lines N =5
Order of matrix n=5
Thus we get the optimal solution.

STEP VI:
Now we have to assign the jobs to the persons:
      1       2        3         4          5
A[  9       0        0         2          6
B   6        2        3        0           3
C   4        0        1        0           0
D   0        0        3        0           0
E   2        1        0         0           2]

1--> D ;  2-->A ;  3--->E ;  4--> B; 5--> C

Now we have to consider the original matrix and assign the values (ie., in each row we have "0" the value being assigned to the jobs) find the corresponding value in the original matrix

Minimum Cost= 3+3+9+2+4=Rs.21(this value no need to be unique as each of us will assign in different method)

Assignment Problem (AP)

Assignment Problem can be stated in the form of n x n matrix Cij of real numbers as given in the following table.

                        Jobs
                      1       2        3               ..............n
Person   1 [    c11   c12    c13..........................c1n
              2        c21   c22    c23..........................c2n
               .
               .

               .
              n        cn1     cn2   cn3............................cnn]

Mathematical Formulation :

An Assignment problem can be stated as

Hungarian Method:
These are the steps to be followed in Hungarian Method for Optimal Job Assignment and for cost assignmnet.
STEP I: Check whether the given matrix is a square matrix.If its so then its balanced.If not balanced add "0" in either the row/column based on the matrix.
STEP II: Process row wise entries.Find out the smallest value and subtract the entire row value.
STEP III:Process  column wise entries.Find out the smallest value and subtract the entire column value.
STEP IV:Draw horizontal/vertical lines in such a way that they cover all the zeros ie., it should be crossed in minimum number of straight lines.
STEP V:Check whether Number of Straight lines(N) = Order of Matrix(n).
If N=n then we get the optimal solution.
If N<n then again find out the smallest value from the above matrix and subtract with the other values in the matrix.Leave the rows and columns that are being striked out.In the intersection point add the smallest value.
STEP VI:Finally assign the jobs to the correct person by assigning "0".Find the minimum cost.

MODI Method / Modification Distribution

Q1.Solve the TP.

                 D1       D2      D3       D4       Supply
O1            11        20       7           8           50
O2            21        16      20         12          40
O3             8         12       8            9          70
Demand    30        25      35          40


Soln:
STEP I:
Eai=160 Ebj=130.The given TP is unbalnced Therefore add a Destination Column.

               D1     D2       D3      D4     D5      Supply
O1          11      20         7         8       0           50
O2          21      16        20       12      0           40
O3            8       12         8         9      0           70
Demand   30      25        35       40    30

Eai=Ebj=160.Now the TP is Balanced.

STEP II:
Now calculate the IBFS using VAM .
The Solution will be,

                      35
11     20      7        8     0
                               10    30
21     16     20      12     0
   30      25   15        15
8       12     8         9       0


In the above table we have 7 independent non negative allocation and m=n-1=7. non degenerate Basic feasible solution is obtained.

Total Cost= Rs.1160

STEP III:
Now select the row or column which has the maximum number of allocations.
Here in the above table we have the maximum number of allocations in the 3rd row.
Therefore assign u3=0
-----------------------------------------
4            9                  35      0         4
  11          20            7            8           0            u1=-1
------------------------------------------
10          1             9                 10        30
   21         16           20          12          0           u2=3
------------------------------------------
   30            25           15          15     3
8              12           8             9           0             u3=0
--------------------------------------------
v1=8       v2=12     v3=8      v4=9     v5=-3


c31=u3+v1=8      c32=u3+v2=12      c33=u3+v3=8      c34=u3+v4=9

c24=u2+v4=12    c25=u2+v5=0        c13=u1+v3=7
         u2=3               v5=-3                         u1=-1


Now calculate

This should be calculated for all the cells which where not allocated.(This should be calculated for the cells in the table which was obtained as a result of applying VAM)

Now (Delta)ij >=0 .Therefore Optimal Solution with Total Cost= Rs.1160.

Vogel's Approximation Method / Unit Cost Penalty Method

Q1.Find the IBFS for the following TP by VAM.


                D1        D2         D3          D4          Supply
O1            11        13          17           14            250
O2            16        18          14           10            300
O3            21        24          13           10            400
Demand   200       225       275          250

Soln:
STEP I:
The given TP is a balanced one. Since Eai=Ebj=950.Therefore there exists a Feasible Solution.

STEP II:
Calculate Penalty (The difference between the Smallest and next smallest cost in each row and column).

        D1       D2     D3     D4          Supply        P1
        ------------------------
          200
O1  11        13      17        14         250              2(13-11)
O2  16        18       14        10        300              4
O3  21        24      13         10       400               3
      200     225     275        250
P2   5         5         1            0

Among the Penalty calculated Select the highest value and choose the cell which has the lowest cost.

                                                  P1
     50
13           17       14         250     1(14-13)
18           14       10          300    4
24           13       10         400     3
225        275      250
5               1         0   P2


Similarly if we calculate the final one will be      

    125
10       250
125


Solution is given by

   200       50
11        13        17     14
                175               125
16        18        14      10
                             275    125
21        24        13       10

The values are independent ie., the number of closed cycles is m+n-1=3+4-1=6

There are six positive independent allocation which equals to m+n-1=6.This ensures that the solution is non-degenerate Basic Feasible solution.

Transportation Cost=(11 x 200)+(13 x 50)+(18 x 175)+(10 x 125)+(13 x 275)+( 10 X 125)
                              =Rs.12075

Least Cost Method / Matrix Minima Method

Q1.Obtain the initial feasible solution for the following TP using Matrix Minima Method.


                 D1          D2        D3        D4       Supply
O1             1            2            3            4          6
O2             4            3            2            0          8
O3             0            2            2            1         10
Demand     4             6           8             6

Soln:  
STEP I:
Sum up Demand and Supply.
Since Eai=Ebj=24. There exists a feasible solution for TP.

STEP II:
In the Least Cost Method, we have to find out the least value in the given problem and start from there.
In this problem the least value is "0", so start from there,

------------------
1      2      3      4        6
4      3      2      0        8
   4
0      2       2     1       10
------------------
4      6       8      6



-----------------
2        3         4          6
                         6
3         2         0          8
2         2         1          6
------------------
6         8         6

------------
    6
2           3           6
3           2           2
2           2           6
------------
6           8


----------
3        2        2
    0
2         2        6
---------
0         8

Here we have subtracted the demand and supply values , in the previous steps the least values were "0" therefore we did not subtract it .

----
   2
2        2
2        6
---
8

-----
    6
2           6
-----
6

STEP III:
The Solution is given by:

                   6
1             2            3             4
                                 2              6
4              3            2             0
   4               0            6
0               2            2             1


Total Cost = (2 x 6)+(2 x 2)+(0 x 6)+(0 x 4)+(2  x 0)+(2 x 6)
                 = Rs.28

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