Page 1 of 12
UNIVERSITY OF RWANDA
COLLEGE OF BUSINESS AND ECONOMICS
SCHOOL OF ECONOMICS
Continuous Assessment Test
Duration: 90 Minutes
Date: 30 January 2024; 14:00 – 15:30 AM
Level III Applied Statistics, Gikondo Campus
Specialization: Common Module
Trimester II, Academic year: 2022-2023
Module AST3231: Operations Research
---------------------------------------------------------------------------------------------------------------------------------
Instructions: - Write your registration number and name on the cover page of this CAT paper;
- Write your number on the attendance list on the cover page (below your name);
- This CAT paper is composed of 12 pages, including a cover page and two draft pages.
- The CAT is out of 30 Marks.
- A student is allowed to have access to only one copy of this CAT paper;
- This CAT paper has TWO sections and shall be used for answering administrated questions;
- Section A has SIX compulsory Theoretical Multiple-Choice questions out of 6 marks;
- Section B is composed of compulsory long analytical questions out of 24 marks;
- Use the provided draft pages for calculations and put the answer in the appropriate place;
- This is a closed-book test; any kind of electronic gadget is prohibited in the examination
room;
- Borrowing and lending calculators are not allowed in the examination room;
- Round to three decimal places (only) for figures with decimals, if any;
- Only a blue pen shall be used to answer this CAT Paper.
- Use clear handwriting.
---------------------------------------------------------------------------------------------------------------------------------
Reg. N
o
Names ……………………………………………………………………………………………………
Number on the Attendance List
Page 2 of 12
Section A: This section is composed of SIX questions. Different potential answers are proposed to each question,
but only one of them is strictly correct. For each question, you are requested to cycle ONE LETTER
ONLY, corresponding to an answer that is strictly correct. If a student cycles more than ONE
LETTER to any question, the student will get a ZERO grade for that specific question. The same is
true for a question where a student cleans the first chosen letter and goes for another different letter
for that specific question. Actually, a student is better off by clearly cycling ONE LETTER ONLY to
each question. Each correct answer carries 1 Mark.
Question A1. In the graphical method for solving linear programming problems, the number of constraints
(___________________) and the bounded region combining all the allowed constraints is
known as (___________________).
A. (is restricted to not more than 2 constraints) ; (solution region)
B. (is not restricted to any number of constraints) ; (optimal region)
C. (is restricted to not more than 2 constraints) ; (feasible solution region)
D. (is not restricted to any number of constraints) ; (solution region)
E. (is restricted to not more than 2 constraints) ; (basic solution region)
F. (is not restricted to any number of constraints) ; (basic solution region)
G. (is not restricted to any number of constraints) ; (feasible solution region)
H. (is restricted to not more than 2 constraints) ; (optimal region)
I. (is restricted to not more than 2 constraints) ; (feasible solution region)
J. (is not restricted to any number of constraints) ; (optimal region)
Question A2. If the primal linear programming problem is a maximization problem, the ‘optimal value of
dual variable 𝑦𝑖
’ is read in Row “0” emanating from the objective function in the optimal
tableau where 𝑦𝑖 = ___________________.
A. The coefficient of slacki if constraint i is a <= constraint); the –‘coefficient of surplusi if constraint
i is a >= constraint); and/or the coefficient of artificial variable +M if constraint i is a = constraint
B. The coefficient of slacki if constraint i is a >= constraint); the –‘coefficient of surplusi if constraint
i is a >= constraint); and/or the coefficient of artificial variable –M if constraint i is a = constraint
C. The coefficient of slacki if constraint i is a <= constraint); the –‘coefficient of surplusi if constraint
i is a >= constraint); and/or the coefficient of artificial variable –M if constraint i is a = constraint
D. The coefficient of slacki if constraint i is a < constraint); the –‘coefficient of surplusi if constraint
i is a >= constraint); and/or the coefficient of artificial variable –M if constraint i is a = constraint
E. None of the Above
F. Uncertain
Question A3. When solving transportation problems, one disadvantage of using North-West Corner rule to
find initial solution is that (___________________); while the method of finding an initial
solution based upon opportunity costs is called (___________________).
A. (it leads to a degenerate initial solution) ; (Vogel’s approximation)
B. (it is complicated to use) ; (the northwest corner rule)
C. (it does not take into account transportation cost) ; (the northwest corner rule)
D. (it does not take into account transportation cost) ; (Vogel’s approximation)
E. (it leads to a degenerate initial solution) ; (Hungarian method)
F. (it is complicated to use) ; (Vogel’s approximation)
G. (it does not take into account transportation cost) ; (Hungarian method)
H. All of the above
I. None of the Above
J. Uncertain
Page 3 of 12
Question A4. Ignoring the xij = 0 or xij = 1 restriction in the linear programming problem presentation of the
assignment problem, an assignment problem can be viewed as a special case of balance
transportation problem in which each supply point has a supply of ___________________
unit(s) and each demand point has a demand of ___________________ unit(s).
A. infinity; infinity
B. finity; finity
C. 0; 0
D. 1; 1
E. None of the above
F. All of the above
G. Uncertain
Question A5. The (___________________) defines the shortest route between the origin and the destination;
the (___________________) defines the maximum length that can be transported from a given
source to a given sink; while the (___________________) problem defines the minimum path
between each pair of nodes.
A. (shortest-path problem) ; (maximum flow problem) ; (minimum spanning tree)
B. (shortest-path problem) ; (minimum spanning tree) ; (maximum flow problem)
C. (minimum spanning tree) ; (shortest-path problem) ; (maximum flow problem)
D. (minimum spanning tree) ; (maximum flow problem) ; (shortest-path problem)
E. (maximum flow problem) ; (shortest-path problem) ; (minimum spanning tree)
F. (maximum flow problem); (minimum spanning tree) ; (shortest-path problem)
G. All of the above
H. None of the above
I. Uncertain
Question A6. Given three nodes i, j, and k, it is shorter to reach j from i passing through k if dik + dkj < dij and
in that case, it is optimal to replace the direct route from i → j with the indirect route i → k →
j. This defines the triple operation exchange applied in the (___________________) to the
distance matrix to reach the shortest route when solving shortest path problem.
A. Prim’s algorithm
B. Dijkstra’s algorithm
C. Kruskal’s algorithm
D. Floyd’s algorithm
E. Recursive computation algorithm
F. All of the above
G. None of the above
H. Uncertain
Page 4 of 12
Section B: Attempt all questions.
Question B1. Form the Dual of the following Primal. (4 Marks)
Max Z = 3𝑥1 + 4𝑥2 + 7𝑥3
Subjected to
𝑥1 + 𝑥2 + 𝑥3 ≤ 10
4𝑥1 − 𝑥2 + 𝑥3 ≥ 15
𝑥1 + 𝑥2 + 𝑥3 = 7
𝑥1, 𝑥2 ≫ 0, 𝑥3 → 𝑢𝑛𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑.
Question B2. Use the TWO-PHASE SIMPLEX METHOD to find the optimal solution for the below LPP.
(8 Marks)
Min Z = 10𝑥1 + 6𝑥2 + 2𝑥3
Subjected to
−𝑥1 + 𝑥2 + 𝑥3 ≥ 1
3𝑥1 + 𝑥2 − 𝑥3 ≥ 2
𝑥1, 𝑥2, 𝑥3 ≥ 0
Page 5 of 12
Page 6 of 12
Page 7 of 12
Question B3:
Wood Business ADARWA is a lumber company with three wood sources and five markets to be supplied.
The annual availability of wood at sources A, B, and C is 120, 60, and 80 million board feet, respectively.
The amount that can be sold annually at markets 1, 2, 3, 4, and 5 is 45, 35, 60, 50, and 70 million board feet,
respectively.
1 2 3 4 5
A 5 6 5 9 9
B 6 9 10 6 5
C 8 4 6 4 8
The objective is to determine the overall shipping plan that minimizes the total equivalent uniform annual
cost (including shipping cost).
An intern student from Applied Statistics managed to find the following table as one of the basic feasible
solutions obtained by using one of the following methods: North-West Corner method, Minimum Cost
method, Minimum Row Cost method or Vogel’s Method.
1 2 3 4 5
A 5
45
6
5
5
60
9
10
B 5
60
C 4
30
4
50
You, as the head of the OR team at ADARWA that has been assigned to supervise the intern during his
internship period:
A. Among the three proposed approaches, which one gave the basic initial solution in the above
transportation tableau? (2 Marks)
B. What is the transport cost from the table proposed by the intern? (1 Marks)
C. Check for him the optimality test to know if the above solution is the optimum; (2 Marks)
D. If the optimality test fails for the above transport cost, determine the leaving variable(s) by using the
simplex feasibility condition and improve it until you show the optimum solution. (3 Marks)
Answer A:
Page 8 of 12
Answer B:
Answer C:
Page 9 of 12
Answer D:
Page 10 of 12
Question B4:
Suppose it is desired to establish a cable communication network that links major areas in Kigali City, which
are shown in the figure. Determine how the areas are connected such that the total cable mileage is
minimized. Hint: A minimum spanning tree will be the result. (4 Marks)
Answer 4:
Good Luck !!
Page 11 of 12
Draft page one
Page 12 of 12
Draft page two