2205 M (Pages: 3) Reg. No. .................
Name ......................
MSc DEGREE EXAMINATION, NOVEMBER 2020
Second Semester
MSc Mathematics
BMMM210: Optimization Techniques
(2019 Admission)
Time: 3 Hours Maximum: 75 Marks
Part A
Answer any fifteen questions. Each question carries 1 marks.
1. Define a feasible solution of a linear programming problem.
2. Define an optimal solution of the Linear programming problem.
3. Give an upperbound for the number of basic solutions of a linear programming problem
of m equations in n unknowns.
4. Describe degeneracy in linear programming problem.
5. Write the dual of the LPP,
Min: z = x1 − 3x2 − 2x3
subject to 2x1 − 4x2 ≥ 12
3x1 − x2 + 2x3 ≤ 7
−4x1 + 3x2 + 8x3 = 10
x 1 , x2 , x3 ≥ 0
6. What makes a transportation problem balanced?
7. What is a triangular basis in a transportation problem?
8. The assignment problem is said to be highly degenerate. Justify.
9. Find a basic feasible solution of the following transportation problem; Di and Oi
denotes the destination and origin respectively.
D1 D2 D3 D4 ai
O1 4 2 3 1 25
O2 2 3 5 3 10
O3 7 2 3 4 50
bj 10 15 20 40
10. What is the number of non zero basic variables required for an assignment problem?
11. Write the general form of a convex linear programming problem.
12. If the saddle point of (x1 + 1)2 + (x2 − 2)2 + y1 (x1 − 2) + y2 (x2 − 1) is (0, 1, 0, 2). Then
what is the minimum point of (x1 +1)2 +(x2 −2)2 subject to the constraints x1 −2 ≤ 0,
x2 − 1 ≤ 0, x1 ≥ 0, x2 ≥ 0.
13. Let f (X) = P X + X T CX; X ∈ En , C is an n ∗ n symmetric matrix and P is a
row n vector. If X T CX is positive semi definite and P 6= 0 then f (X) may have an
unbounded minimum. Justify your answer.
14. Sum of two convex functions is convex. Justify.
Turn over
(Page 2 of 3)
15. What are the characteristics of queueing process?
16. Write Little’s formulas.
17. Write the necessary and sufficient condition for the existence of the solution for the
steady state probabilities.
18. Write global balance equations. Why is it called so?
(15×1=15)
Part B
Answer any four questions. Each question carries 15 marks.
19. (a) The manager of an agriculture farm of 80 hectares learns that for effective protec-
tion against insects, he should spray at least 15 units of chemical A and 20 units
of chemical B per hectare. Three bands of insecticides are available in the market
which contain these chemicals. One brand contains 4 units of A and 8 units of B
per Kg and costs Rs 5 per Kg, the second band contains 12 and 8 units respectively
and costs Rs 8 per Kg, and the third contains 8 and 4 units respectively and costs
Rs 6 per Kg. It is also learn that more than 2.5 Kg per hectare of insecticides will
be harmful to the crops. Determine the quantity of each insecticide he should buy
to minimize the total costs for the whole farm.
OR
(b) Prove that if SF , the set of feasible solutions is non empty, the objective function
f (X) has either an unbounded minimum or it is minimum at a vertex of SF .
20. (a) (i) Prove that the transportation problem has a triangular basis.
(ii) A company wishes to manufacture 5 Products A,B,C,D and E in its three
workshops W1 , W2 , W3 whose production capacities are 90,40,60 units re-
spectively. The potential sales of the 5 products are 60,30,40,70,40 units
respectively. Product D can not be produced in W3 . What quantity of each
product should be produced at each workshop to minimize cost?
The producing cost per unit are given in the following table
A B C D E
W1 14 19 20 16 21
W2 13 20 15 16 19
W3 18 15 18 20
OR
(b) Solve the following problem of transportation with transhipment with sources S1 ,
S2 , sinks D1 , D2 and junction J for minimum cost.
Transhipment cost capacity S1 S2 J D1 D2
4 3 1 3 5
60 40 35 45
S1 4 3 10 5
S2 4 2 5 6
Transportation cost J 4 2 8 7
D1 11 4 6 4
D2 5 7 5 4
(Page 3 of 3)
21. (a) State and prove Kuhn - Tucker Theorem.
OR
(b) Find the optimum value of
Minimize f (X) = −6x1 + 2x21 + 2x22 − 2x1 x2
subject to x1 + x2 ≤ 2
x1 , x2 ≥ 0
λ
22. (a) (i) Derive the formula pn = (1 − ρ)ρn , (ρ = < 1) for steady state probabil-
µ
ities in a single server queue using probability generating function P (Z) =
P∞ n
n=0 pn z ; z ∈ C, | z |< 1.
(ii) Derive the formula for steady state probabilities in a single server queue using
operators.
OR
(b) (i) Derive Erlang -C Formula.
(ii) Calls to a technical support center arrive according to a Poisson process with
rate 30 per hour. The time for a support person to serve one customer is
exponentially distributed with a mean of 5 minutes. The support center has
3 technical staff to assist callers. What is the probability that a customer is
able to immediately access a support staff, without being delayed on hold?
(Assume that customers do not abandon their calls.)
(4×15=60)
