Operations Research Assignment: Optimization Problems & Algorithms

This assignment solution covers optimization problems and network analysis, including the application of the simplex method and Dijkstra's algorithm. Problem A involves determining the optimal solution for a linear programming problem and analyzing the impact of additional constraints. Problem B applies Dijkstra’s algorithm to find the shortest path between two nodes in a network. Problem C focuses on network analysis, including task and event-oriented network construction, algorithm formulation, and critical path determination. The document provides detailed steps and calculations for each problem, offering a comprehensive understanding of operations research techniques. Desklib provides access to this and many other solved assignments and past papers for students.

PROBLEM A
(a) For x1=36 , x2=0∧x3 =6 ,
z=6 ( 36 )+14 ( 0 ) +13 ( 6 ) =294
The constraints on the other hand become :
1
2 ( 36 ) +2 ( 0 ) +6 ≤ 24 ; satisfied
36+2 ( 0 ) +4 ( 6 ) ≤ 60 →60 ≤ 60; satisfied
¿
x1 , x2∧x3 are all greater than 0
∴ The solution remains optimal irregardless of the imposition of the inspectioncontraint
(b)
With inclusion of the constraint x1 +x2 + x3 + x6=30 , after pivoting , the new tableau isas follows :
Basic
variable
Current
values
x1 x2 x3 x4 x5
x1 36 1 6 4 -1
x3 6 -1 1 -1 ½
x6 30 1 1 1
-z -324 -9 -½
∴ The table now appears∈dual−canonical form
(c) Application of the dual-simplex method
Pivoting of the elements of thetable yield ,
( −3+2 t ) x1 + ( −1+3 t ) x2−t x4 −z=2 t
Ensuringthat the coefficient of each variable remains negative ,
−3+2 t ≤ 0 ;t ≤ 3
2
−1+3 t ≤ 0 ;t ≤ 1
3
−t ≤ 0 ; t ≥ 0
Setting t= 1
3 maintains the optimal conditions
The v ariable ¿ leavethe basis is chosen by ,
br=min { bi }=min {−1 ,−2 } =¿ b2 ¿
By dual−ratio test ,
cs
ar s
=minj { c j
ar j
∣ar j <0 }=min { −3
−2 , −1
−3 }= c2
a22

P ivoting∈ x2∈the second constraint givesthe new canonical form thereinthe table au :
Basic
variable
Current
values
x1 x2 x3 x4
x3 -1/3 -1/3 1 -1/3
x2 2/3 2/3 1 -1/3
-z 2/3 -7/3 -1/3
Pivoting again yields the folowing table au :
Basic
variable
Current
values
x1 x2 x3 x4
x4 1 1 -3 1
x2 1 1 1 -1
-z 1 -2 -1
Sincebi ≥ 0 fori=1,2∧c j ≤0 for j=1,2, … , 4 ,the solutionis optimal

PROBLEM B
Given,
Applying Dijkstra’s Algorithm,
Initialization Step
 Node S is designated the current node with every other remaining node being of
temporary label. The new network appears as below:

1st Iteration Process
 Current node: S(0,p)
 Nodes A,B and C can be reached from S.
 Update the distance values for A, B and C i.e.
d A =min { ∞ , 0+1 }=1 ; A status is (1,t)
d B=min { ∞ , 0+6 } =6 ; A status is (6,t)
d A =min { ∞ , 0+3 }=3 ; A status is (3,t)
 The network is then re-drawn as shown below with updated parameters summarized in
the table:
Distance Label
d(S) 0
d(A) 1
d(B) 6
d(C) 3
d(D) ∞
d(E) ∞
d(S) ∞
Permanent nodes
S X
A
B
C
D
E
T

2nd Iteration Process
 Current node: A(1,p)
 Nodes B and D can be reached from A.
 Update the distance values for B and D i.e.
d B=min { 6,1+4 }=5 ; B status is (5,t)
d D=min { ∞ , 1+6 } =7 ; D status is (7,t)
 The network is then re-drawn as shown below with updated parameters summarized in
the table:
Permanent nodes
S X
A X
B
C
D
E
T
Distance Label
d(S) 0
d(A) 1
d(B) 5
d(C) 3
d(D) 7
d(E) ∞
d(S) ∞

3rd Iteration Process
 Current node: C(3,p)
 Node E can be reached from C.
 Update the distance values for E i.e.
d E=min { ∞, 3+2 }=5 ; E status is (5,t)
 The network is then re-drawn as shown below with updated parameters summarized in
the table:
Permanent nodes
S X
A X
B
C X
D
E
T
Distance Label
d(S) 0
d(A) 1
d(B) 5
d(C) 3
d(D) 7
d(E) 5
d(S) ∞

4th Iteration Process
 Current node: B(5,p)
 Nodes D and T can be reached from B.
 Update the distance values for D and T i.e.
d D=min { 7,5+1 }=6 ; D status is (6,t)
dT =min { ∞ ,5+5 }=10 ; T status is (10,t)
 The network is then re-drawn as shown below with updated parameters summarized in
the table:
Permanent nodes
S X
A X
B X
C X
D
E
T
Distance Label
d(S) 0
d(A) 1
d(B) 5
d(C) 3
d(D) 6
d(E) 5
d(S) 10

5th Iteration Process
 Current node: D(6,p)
 T can be reached from D.
 Update the distance value of T i.e.
dT =min { 10,6+2 }=8 ; T status is (8,t)
 The network is then re-drawn as shown below with updated parameters summarized in
the table:
Final Iteration Process
Permanent nodes
S X
A X
B X
C X
D X
E
T
Distance Label
d(S) 0
d(A) 1
d(B) 5
d(C) 3
d(D) 6
d(E) 5
d(S) 8

 Current node: T(8,p)
 Since no node can be accessed from T, E is consequently changed to a permanent state
i.e. E (5,p).
 The final network is then drawn as shown below with updated parameters summarized in
the table:
PROBLEM C
(a). From the tableau of tasks in question, the event and task-
oriented networks are as follows:
i. Task-Oriented Network
ii. Event-Oriented Network
Permanent nodes
S X
A X
B X
C X
D X
E X
T X
Distance Label
d(S) 0
d(A) 1
d(B) 5
d(C) 3
d(D) 6
d(E) 5
d(S) 8

(b). Formulation of the Algorithm and determination of the Critical path
The tableau below gives the formulated algorithm from the drawn networks in (a):
X12 X15 X26 X36 X47 X58 X59 X6-
10
X7-
10
X8-
12
X8-
11
X10-11 X10-12 X12-13 Relation
Node 1 1 1 = 1
Node 2 -1 1 = 0
Node 3 1 = 0
Node 4 1 = 0
Node 5 -1 1 1 = 0
Node 6 -1 -1 1 = 0
Node 7 -1 1 = 0
Node 8 -1 1 1 = 0
Node 9 -1 = 0
Node 10 -1 -1 1 1 = 0
Node 11 -1 -1 = 0
Node 12 -1 -1 1 = 0
Node 13 -1 = -1
Distances 2 2 1 1 2 6 10 5 5 3 3 3 3 2 = zmin

Therefore, from the formulated algorithm, the critical path is 3-6-10-12-13