List of Practical Experiments (Official Syllabus)

1. IBFS of transportation problem using North-West Corner rule, LCEM and VAM.
2. Optimum solution to balanced & unbalanced transportation problems by MODI method (minimization cases).
3. Solution of assignment problem using Hungarian method (minimization cases).
4. Solution of sequencing problem — n jobs through two machines.
5. Solution of sequencing problem — n jobs through three machines.
6. Project scheduling of a given project (deterministic case — CPM).
7. Project scheduling of a given project (probabilistic case — PERT).
8. Solution of m × n games by dominance rule.

Experiment 1 — IBFS by NWCM, LCEM and VAM

1. Problem

Find the initial basic feasible solution of the transportation problem below by the North-West Corner (NWCM), Least-Cost (LCEM) and Vogel's Approximation (VAM) methods.

	D₁	D₂	D₃	D₄	Supply
S₁	3	1	7	4	300
S₂	2	6	5	9	400
S₃	8	3	3	2	500
Demand	250	350	400	200	1200

2. Aim

To obtain an initial basic feasible solution by each of the three rules and compare their costs.

3. Formula

Applying it:

1. NWCM: allocate at the top-left cell, exhaust its row/column, move right/down.
2. LCEM: allocate to the least-cost available cell repeatedly.
3. VAM: for each row/column compute the penalty (difference of the two smallest costs); allocate in the line with the largest penalty, at its least-cost cell; recompute penalties and repeat.

4. Calculation

Blank working table:

Method	Total cost
NWCM
LCEM
VAM

NWCM: x₁₁=250, x₁₂=50, x₂₂=300, x₂₃=100, x₃₃=300, x₃₄=200 ⇒ \(250(3)+50(1)+300(6)+100(5)+300(3)+200(2) = 4400\).

LCEM: x₁₂=300, x₂₁=250, x₂₃=150, x₃₂=50, x₃₃=250, x₃₄=200 ⇒ \(300(1)+250(2)+150(5)+50(3)+250(3)+200(2) = 2850\).

VAM: x₂₁=250, x₁₂=300, x₃₂=50, x₂₃=150, x₃₃=250, x₃₄=200 ⇒ \(250(2)+300(1)+50(3)+150(5)+250(3)+200(2) = 2850\).

Method	Total cost
NWCM	4400
LCEM	2850
VAM	2850

5. Result

NWCM gives the poorest start (4400); LCEM and VAM both give 2850, which (as Experiment 2 confirms) is already the optimum. VAM is the best rule for a low-cost starting solution.

Experiment 2 — MODI Method (Balanced & Unbalanced)

1. Problem

Starting from the VAM/LCEM solution of Experiment 1, test optimality and improve it if necessary by the MODI (u–v) method. Also outline how an unbalanced problem is handled.

2. Aim

To reach the optimal transportation cost using the MODI optimality test and closed-loop adjustments.

3. Formula

Applying it:

1. For the basic cells solve \(u_i + v_j = c_{ij}\) (set \(u_1 = 0\)).
2. For each non-basic cell compute \(d_{ij} = c_{ij} - (u_i + v_j)\).
3. If all \(d_{ij} \ge 0\), the solution is optimal; otherwise form a closed loop at the most negative \(d_{ij}\) and adjust by \(\theta\).
4. Unbalanced: if \(\sum\text{supply} \ne \sum\text{demand}\), add a dummy source/destination with zero cost, then proceed.

4. Calculation

Blank working table:

Quantity	Value
All \(d_{ij} \ge 0\)?
Optimal cost

Applying \(u_i + v_j = c_{ij}\) to the six basic cells and computing \(d_{ij}\) for the remaining cells gives all \(d_{ij} \ge 0\); the VAM/LCEM solution is therefore optimal with no closed-loop improvement possible.

Quantity	Value
All \(d_{ij} \ge 0\)?	Yes
Optimal cost	2850

Unbalanced example: supply 100, 150; demand 80, 100, 90 (supply 250 < demand 270) — add a dummy source of supply 20 at zero cost, then apply VAM + MODI as above.

5. Result

The optimal transportation cost is 2850. Because VAM already attained it, the MODI test only confirms optimality (all \(d_{ij} \ge 0\)).

Experiment 3 — Hungarian Method (Assignment)

1. Problem

Assign 4 workers W₁–W₄ to 4 jobs J₁–J₄ to minimise total cost:

	J₁	J₂	J₃	J₄
W₁	10	12	19	11
W₂	5	10	7	8
W₃	12	14	13	11
W₄	8	15	11	9

2. Aim

To find the minimum-cost one-to-one assignment by the Hungarian method.

3. Formula

Applying it:

1. Row reduction: subtract each row's minimum.
2. Column reduction: subtract each column's minimum.
3. Cover all zeros with the minimum number of lines; if fewer than \(n\), adjust and repeat.
4. Make the assignment through independent zeros.

4. Calculation

Blank working table (after row + column reduction):

	J₁	J₂	J₃	J₄
W₁
W₂
W₃
W₄

Row minima (10, 5, 11, 8) then column minima (0, 2, 2, 0) give the reduced matrix:

	J₁	J₂	J₃	J₄
W₁	0	0	7	1
W₂	0	3	0	3
W₃	1	1	0	0
W₄	0	5	1	1

Independent zeros give W₁→J₂, W₂→J₃, W₃→J₄, W₄→J₁, with cost \(12 + 7 + 11 + 8 = 38\).

5. Result

The optimal assignment is W₁→J₂, W₂→J₃, W₃→J₄, W₄→J₁ at a minimum total cost of 38.

Experiment 4 — Sequencing: n Jobs on 2 Machines

1. Problem

Five jobs are processed on machine M₁ then M₂ (times below). Find the sequence minimising total elapsed time and the machine idle times.

Job	M₁	M₂
A	5	2
B	1	6
C	9	7
D	3	8
E	10	4

2. Aim

To sequence \(n\) jobs on two machines by Johnson's rule and compute the makespan.

3. Formula

Applying it:

1. Find the smallest processing time. If it is on M₁, place the job as early as possible; if on M₂, as late as possible.
2. Remove the job and repeat, filling the sequence from both ends.
3. Compute the schedule (completion times on each machine) and the total elapsed time.

4. Calculation

Blank working table:

Job (in sequence)	M₁ in–out	M₂ in–out

Johnson's rule gives the sequence B → D → C → E → A.

Job	M₁ in–out	M₂ in–out
B	0–1	1–7
D	1–4	7–15
C	4–13	15–22
E	13–23	23–27
A	23–28	28–30

5. Result

Total elapsed time = 30 hours; idle time on M₂ = 3 hours and on M₁ = 2 hours.

Experiment 5 — Sequencing: n Jobs on 3 Machines

1. Problem

Four jobs are processed on M₁, M₂, M₃ in order (times below). Sequence them to minimise the total elapsed time.

Job	M₁	M₂	M₃
A	8	5	4
B	10	6	9
C	6	2	8
D	7	3	6

2. Aim

To sequence \(n\) jobs on three machines by converting to Johnson's two pseudo-machines and compute the makespan.

3. Formula

Applying it:

1. Check the applicability condition: \(\min(M_1) \ge \max(M_2)\) or \(\min(M_3) \ge \max(M_2)\).
2. Form pseudo-machines \(G = M_1 + M_2\) and \(H = M_2 + M_3\).
3. Apply Johnson's rule to \((G, H)\); then compute the full three-machine schedule.

4. Calculation

Blank working table (pseudo-machines):

Job	G = M₁+M₂	H = M₂+M₃
A
B
C
D

Condition: \(\min(M_1) = 6 = \max(M_2) = 6\) ✓, so the method applies.

Job	G = M₁+M₂	H = M₂+M₃
A	13	9
B	16	15
C	8	10
D	10	9

Johnson's rule on \((G, H)\) gives the sequence C → B → A → D. The three-machine schedule:

Job	M₁ in–out	M₂ in–out	M₃ in–out
C	0–6	6–8	8–16
B	6–16	16–22	22–31
A	16–24	24–29	31–35
D	24–31	31–34	35–41

5. Result

The optimal sequence is C → B → A → D with a total elapsed time of 41 hours.

Experiment 6 — CPM (Deterministic Project Scheduling)

1. Problem

For the project below, find the project duration, the critical path and the total float of each activity.

Activity	Predecessors	Duration (days)
A	—	3
B	—	5
C	A	7
D	B	3
E	B	5
F	C, D	4
G	E	2

2. Aim

To carry out the forward and backward passes, identify the critical path and compute total floats.

3. Formula

Applying it:

1. Forward pass: earliest start/finish (ES, EF) for each activity.
2. Backward pass: latest start/finish (LS, LF).
3. Total float \(= LS - ES = LF - EF\); critical activities have zero float.

4. Calculation

Blank working table:

Activity	A	B	C	D	E	F	G
Total float

Path lengths: A→C→F = 3+7+4 = 14; B→D→F = 5+3+4 = 12; B→E→G = 5+5+2 = 12. The longest is 14, so the critical path is A → C → F.

Activity	A	B	C	D	E	F	G
Total float	0	2	0	2	2	0	2

5. Result

Project duration = 14 days; critical path A → C → F (zero float). Activities B, D, E, G each have 2 days of float.

Experiment 7 — PERT (Probabilistic Project Scheduling)

1. Problem

The same network has three time estimates \((a, m, b)\) per activity. Find the expected project duration and the probability of completion within 15 and 16 days, and the time for 95 % confidence.

Activity	a	m	b
A	2	3	4
B	3	5	7
C	5	7	9
D	1	3	5
E	4	5	6
F	3	4	5
G	1	2	3

2. Aim

To compute expected activity times and variances, then the completion probabilities on the critical path using the normal approximation.

3. Formula

Applying it:

1. \(t_e = (a + 4m + b)/6\) and \(\sigma^2 = ((b - a)/6)^2\) for each activity.
2. Sum \(t_e\) and \(\sigma^2\) along the critical path (A → C → F).
3. \(P(T \le x) = \Phi((x - T_e)/\sigma)\); for 95 %, \(x = T_e + 1.645\sigma\).

4. Calculation

Blank working table:

Activity	\(t_e\)	\(\sigma^2\)
A
C
F
Critical path total

Activity	\(t_e\)	\(\sigma^2\)
A	3	0.111
C	7	0.444
F	4	0.111
Critical path (A→C→F) total	14	0.666

\(\sigma = \sqrt{0.666} = 0.816\). \(P(T \le 15) = \Phi(1.225) = 0.890\); \(P(T \le 16) = \Phi(2.449) = 0.993\); 95 % time \(= 14 + 1.645(0.816) = 15.34\) days.

5. Result

Expected duration = 14 days (\(\sigma = 0.816\)). The project finishes within 15 days with probability 0.890, within 16 days with 0.993, and 95 % confidence corresponds to 15.34 days.

Experiment 8 — Game Theory by Dominance Rule

1. Problem

Solve the \(4\times 4\) game (payoffs to player A) by the dominance rule and find its value and optimal strategies.

	B₁	B₂	B₃	B₄
A₁	3	2	4	0
A₂	3	4	2	4
A₃	4	2	4	0
A₄	0	4	0	8

2. Aim

To reduce the game by pure and mixed (convex) dominance and solve the resulting \(2\times 2\) game.

3. Formula

Applying it:

1. Check for a saddle point (maxmin vs minimax).
2. Delete dominated rows (A prefers larger payoffs) and dominated columns (B prefers smaller).
3. Use convex dominance (a row/column dominated by an average of others) where no pure dominance applies.
4. Solve the final \(2\times 2\) game by the closed-form mixed-strategy formula.

4. Calculation

Blank working table:

Quantity	Value
Saddle point?
Reduced game
Value \(V\)
A's strategy / B's strategy

Row minima (0, 2, 0, 0) give maxmin = 2; column maxima (4, 4, 4, 8) give minimax = 4 ⇒ no saddle point. Dominance steps:

• A₁ = (3,2,4,0) ≤ A₃ = (4,2,4,0) ⇒ delete A₁.
• Column B₁ = (3,4,0) ≥ B₃ = (2,4,0) ⇒ delete B₁ (B minimises).
• B₂ = (4,2,4) is dominated by ½(B₃ + B₄) = (3,2,4) ⇒ delete B₂.
• A₂ = (2,4) equals ½(A₃ + A₄) over the remaining columns ⇒ delete A₂.

This leaves the \(2\times 2\) game (rows A₃, A₄; columns B₃, B₄):

	B₃	B₄
A₃	4	0
A₄	0	8

\(V = \dfrac{4(8) - 0}{4 + 8 - 0 - 0} = \dfrac{32}{12} = \dfrac{8}{3} \approx 2.67\); \(p(A_3) = 8/12 = 2/3,\; p(A_4) = 1/3\); \(q(B_3) = 8/12 = 2/3,\; q(B_4) = 1/3\).

5. Result

The value of the game is \(V = 8/3 \approx 2.67\). A plays A₃ and A₄ with probabilities \((2/3, 1/3)\) (never A₁, A₂); B plays B₃ and B₄ with probabilities \((2/3, 1/3)\) (never B₁, B₂).

Lab Record Format (to be followed for every experiment)

1. 1. Problem — the data and what is to be optimised.
2. 2. Aim — the method the experiment demonstrates.
3. 3. Formula — the formula or algorithm, then the numbered steps that apply it.
4. 4. Calculation — the filled working (tableau, schedule, reduction) with the arithmetic.
5. 5. Result — the optimal answer and its interpretation.