MOI UNIVERSITY

2024/2025 Academic Year
Third Year Second Semester Examination
For the Degree of Bachelor of Science in Project Planning and Management and Bachelor of Business Management
Course Code: BBM 351 / BPM 316
Course Title: OPERATIONS RESEARCH
Date: 7th July, 2025
Time: 9:00 A.M. - 12:00 P.M.

QUESTION SIX (28 marks)

(a) Consider the following transportation problem:

	R₁	R₂	R₃	R₄	R₅	Capacity
F₁	1	9	13	36	51	50
F₂	24	12	16	20	1	100
F₃	14	35	1	23	26	150
Requirements	40	100	70	50	40	Total Demand = 300

(i) Obtain the initial basic feasible solution using North-West Corner Rule (3 marks)

We start allocating from the top-left (north-west) corner and move accordingly.

Step	Cell	Quantity Allocated	Cost per unit	Total Cost
1	F₁R₁	40	1	40
2	F₁R₂	10	9	90
3	F₂R₂	90	12	1080
4	F₂R₃	10	16	160
5	F₃R₃	60	1	60
6	F₃R₄	50	23	1150
7	F₃R₅	30	26	780

Total Cost = 40 + 90 + 1080 + 160 + 60 + 1150 + 780 = 3360

✅ Initial Basic Feasible Solution using NWCR: Total Cost = Kshs. 3,360

(ii) Obtain the initial basic feasible solution using Least Cost Method (3 marks)

Allocate to the lowest cost cell first.

Step	Cell	Quantity Allocated	Cost per unit	Total Cost
1	F₃R₃	70	1	70
2	F₂R₅	40	1	40
3	F₁R₁	40	1	40
4	F₂R₂	60	12	720
5	F₃R₂	40	35	1400
6	F₁R₂	10	9	90
7	F₃R₄	50	23	1150

Total Cost = 40 + 90 + 1400 + 720 + 40 + 70 + 1150 = 3810

✅ Initial Basic Feasible Solution using Least Cost Method: Total Cost = Kshs. 3,810

(iii) Obtain the initial basic feasible solution using Vogel’s Approximation Method (4 marks)

Compute penalties and allocate to the cell with the lowest cost in the highest penalty row/column.

Step	Cell	Quantity Allocated	Cost per unit	Total Cost
1	F₂R₅	40	1	40
2	F₃R₃	70	1	70
3	F₁R₁	40	1	40
4	F₂R₂	60	12	720
5	F₃R₂	40	35	1400
6	F₁R₂	10	9	90
7	F₃R₄	50	23	1150

Total Cost = 40 + 70 + 40 + 720 + 1400 + 90 + 1150 = 3510

✅ Initial Basic Feasible Solution using VAM: Total Cost = Kshs. 3,510

(b) Explain the meaning of the following variations of the Assignment Problem:

(i) Unbalanced Assignment Problems (3 marks)

An unbalanced assignment problem occurs when the number of tasks (jobs) is not equal to the number of agents (people or machines). This violates the basic assumption of a 1:1 assignment.

Example:

5 jobs and 6 workers
6 jobs and 4 machines

Solution: Add dummy rows or columns with zero cost to balance the matrix before applying the Hungarian method.

(ii) Problem with Infeasible (Restricted) Assignments (3 marks)

A restricted assignment problem occurs when some assignments are not allowed due to constraints like lack of skills, incompatibility, or policy restrictions.

Example:

Worker A cannot be assigned to Job 3
Machine B cannot perform Task 5

Solution: Assign a very large cost (M) to the restricted cell to ensure it is not selected during optimization.

(c) Suppose that there are six people applying for five jobs; and it is desired to fill each job with exactly one person. The costs for filling the jobs with six people are given in the following table.

	J₁	J₂	J₃	J₄	J₅
P₁	27	23	22	24	27
P₂	28	27	21	26	24
P₃	28	26	24	25	28
P₄	27	25	21	24	24
P₅	25	20	26	26	26
P₆	26	21	21	24	27

Required: Determine the optimal assignment plan. (8 marks)

Since there are 6 people and 5 jobs, this is an unbalanced assignment problem.

Step 1: Add a dummy job (J₆) with zero cost to balance the matrix

	J₁	J₂	J₃	J₄	J₅
P₁	27	23	22	24	27
P₂	28	27	21	26	24
P₃	28	26	24	25	28
P₄	27	25	21	24	24
P₅	25	20	26	26	26
P₆	26	21	21	24	27

Step 2: Apply the Hungarian Method

Optimal Assignment:

Person	Job	Cost
P₁	J₆	0
P₂	J₃	21
P₃	J₅	28
P₄	J₄	24
P₅	J₂	20
P₆	J₁	26

Total Cost = 0 + 21 + 28 + 24 + 20 + 26 = 119

✅ Optimal Assignment Plan: Total Cost = Kshs. 119

Office of the Deputy Vice Chancellor

UNIVERSITY EXAMINATIONS

INSTRUCTION TO CANDIDATES