The ______ variable is chosen by examining the cost coefficents in the objective function.
Aentering
Bleaving
Cpositive slack
Dnegative slack
The entering variable is picked from the objective-row (cost) coefficients; the leaving variable comes from the ratio test.
2.
★ Final term paper (screens, paper 2)Lecture 21
It is a property of simplex method that there always exist infinite numbers of basic feasible solutions. (True/False)
ATrue
BFalse
An LP has only a finite number of basic feasible solutions (at most C(n,m)).
3.
★ Final term paper (screens, paper 2)Lecture 21
If the objective function of a linear programming problem needs further improvement then which of the following will have to proceed?
Aa new decision variable to be entered and other decision variable to leave the basis
Ba new slack variable to be entered and other slack to leave the basis
Ca new non-degenerate variable to be entered and other non-generate to leave the basis
Da new basic variable to be included and other basic variable to leave the basis
Each simplex iteration brings an entering variable into the basis and removes a leaving basic variable.
4.
★ Final term paper (screens, paper 2)Lecture 21
The constrained 3x1 + 2x2 <= 18 in standard form can be written as: (Where R is artificial variable and S1 is Slack variable)
A3x1 + 2x2 + S1 + R = 18
B3x1 + 2x2 + S1 - R = 18
C3x1 + 2x2 - S1 + R = 18
D3x1 + 2x2 + S1 = 18
A <= constraint only needs a slack variable added; no artificial variable is required.
5.
★ Final term 2012Lecture 23
While solving a linear programming problem by big M – Method, traditionally the ______ variables are chosen in the initial basic feasible solution.
Aneagtive slack
Bpositive slack
Centering
Dartificial
Big M adds artificial variables to ≥ and = constraints and starts with them in the initial basis.
6.
★ Final term 2012Lecture 23
In the big-M method, if the introduced ______ variables do not leave the basis in the final iteration, then this indicates that the give linear programming problem cant be optimized.
Aentering
Bpositive slack
Cnegative slack
Dartificial
A positive artificial variable left in the final basis means the problem has no feasible solution.
7.
★ Final term paper (screens, paper 2)Lecture 23
If no ____ variable appears in the basis and the optimality conditions are satisfied, then the current solution will be optimal one.
Aartificial
Bnon basic
Cslack
Dsurplus
An optimal tableau is valid for the original problem only if no artificial variable remains in the basis.
8.
★ Final term 2012Lecture 25
By using Two phase method to solve a linear programming problem, in phase I, a new objective function is formed by assigning on left hand side, zero to every original variable (including slack and surplus variables) and -------- to each of the artificial variables.
AM
B−M
C+1
D−1
The Phase I objective (maximize form) gives cost 0 to original variables and −1 to each artificial variable, i.e. Max Z* = −ΣA; M is used only in the Big M method.
9.
★ Final term 2012Lecture 25
For the linear programming problem; Max Z = 2x + 3y Subject to x ≥ 2, y ≤ 3, x, y ≥ 0 ⇒ x − s1 + A = 2, y + s2 = 3, x, y, s1, s2, A ≥ 0. Which of the following is associated objective function of the 1st phase?
AMax Z = 2x + 3y + A
BMin Z = 2x + 3y + A
CMax Z = A
DMin Z = A
Phase I minimizes the sum of the artificial variables, here only A.
10.
★ Final term paper (screens, paper 2)Lecture 25
Min. Z = 0 and no artificial variable appears in the basic variables. ____ solution to original problem has been found and we proceed to phase II method.
AA basic feasible
BAn optimal
CAn infeasible
Phase I ending with Z = 0 and no artificials in the basis gives a basic feasible solution to start Phase II.
11.
★ Final term paper (screens, paper 2)Lecture 25
If the problem has a ____ solution such that the minimum value of the objective function is zero along with zero values of artificial variables. Then proceed to phase II method.
Aunbounded
Bfeasible
Cnon feasible
Dde-generate feasible solution
Phase I with minimum zero and all artificials zero means a feasible solution exists, so Phase II follows.
12.
★ Final term Fall 2005Lecture 25
The Phase-I objective function Minimize R0 = sum_{i=1}^{n} R_i, where R_i are artificial variables is obtained by
ADividing the Big-M method's objective function by 'M' and then dropping the negligible terms
BDividing the Big-M method's objective function by '-M' and then dropping the negligible terms
CMultiply the Big-M method's objective function by 'M' and then dropping the negligible terms
DMultiply the Big-M method's objective function by '-M' and then dropping the negligible terms
Dividing Min Z = sum cx + M sum R by M and letting M grow leaves only sum R, the Phase-I objective.
13.
★ Final term paper (screens, paper 2)Lecture 26
If the degeneracy arises in the initial stage, then which of the following is true?
AOne of the basic variables is zero.
BMore than one variable is eligible to leave the basis.
CTie in the ratio of each row, by taking right hand side of each row and dividing by the corresponding element of the key column.
DIterative Cycling of basic solution exists without reaching the optimality.
Initial degeneracy means a basic variable starts at zero (a zero right-hand side); ties in the ratio test cause degeneracy in later iterations.
14.
★ Final term paper (screens, paper 2)Lecture 26
Consider the following simplex table corresponding to the maximization problem: Z: x1 0, x2 0, x3 M+1/2, x4 M, A1 16M-11, A2 0, RHS -0.6M-5.7 | x1: 1, 0, 5, 0, -1, 0, 3 | x2: 0, 1, -5, 0, 3, 0, 9 | A2: 0, 0, -1, -1, -0.6, 1, 0.6. This is the indication that problem has----------.
Ainfeasible Solution
Btemporarily Degenerate Solution
Cunbounded Solution
Ddegenerate Solution
All Z-row entries are non-negative (optimal) but artificial A2 stays in the basis at a positive value 0.6, so the problem is infeasible.
15.
★ Final term paper (screens, paper 2)Lecture 26
In the Simplex table, if the coefficient of non-basic variable says x1 in the z-row is zero, then it indicates that value of z ------------.
Aincrease
Bdecreases
Cdoes not change
Dbecomes infinity
Bringing in a non-basic variable with zero z-row coefficient leaves z unchanged, indicating alternative optima.
16.
★ Final term paper (screens, paper 2)Lecture 29
A primal's constraint equation produces ____ dual variable.
Anon basic
Ban unrestricted
Cartificial
Dbasic
An equality constraint in the primal corresponds to a dual variable unrestricted in sign.
17.
★ Final term Fall 2006Lecture 29
An unrestricted primal variable will result in an equality dual constraint.
ATrue
BFalse
A free primal variable corresponds to an equality constraint in the dual.
18.
★ Final term Fall 2006Lecture 29
The dual of the dual problem yields the original primal
ATrue
BFalse
Duality is symmetric: taking the dual twice returns the primal.
19.
★ Final term 2012Lecture 31
Any set of non negative allocations (Xij > 0) which satisfies the row and column sum is called a ______ solution.
Afeasible
Bnon basic feasible
Cbasic infeasible
Doptimal
Non-negative allocations meeting all supply and demand constraints form a feasible solution.
20.
★ Final term 2012Lecture 31
In which of the following models, Simplex algorithm is not preferred to use due to laborious computations?
ATransportations models
BDegenerate Linear models
CNon-degenerate Linear models
DDual or unbounded linear models
Transportation problems have many variables and constraints, so special methods (NWC, VAM, MODI) replace the laborious simplex.
21.
★ Final term 2012Lecture 31
Transportations models consist of ------- like the production centers and --------- which may be the sales centers.
A(sinks, sources)
B(sources, sinks)
C(origins, sources)
D(sinks, destinations)
Production centres are sources (origins) and sales centres are sinks (destinations).
22.
★ Final term paper (screens, paper 2)Lecture 31
Transportation problem is a special class of linear programming problem in which transport a commodity from the source to a destination in such a way that the total transportation cost is -------.
AZero
BMaximum
CMinimum
DAverage
The transportation problem minimizes total shipping cost while meeting supply and demand.
23.
★ Final term paper (screens, paper 2)Lecture 32
The Vogel Approximation method is an iterative procedure for computing a ______________ solution of the transportation problem.
Abasic feasible
Bnon basic feasible
Cbasic infeasible
Doptimal
VAM gives an initial basic feasible solution, which is then tested for optimality.
24.
★ Final term 2012Lecture 34
To convert the transportation problem into a maximization model we have to------------.
Awrite the inverse of the coefficient matrix
Bmultiply the feasibility condition by −1
Cmultiply the coefficient matrix by −1
DWe can't convert the transportation problem into a maximization problem, as it is basically a minimization problem.
A maximization transportation problem is solved by multiplying the profit (coefficient) matrix by −1 (or subtracting from the largest value) and minimizing.
25.
★ Final term 2012Lecture 35
Degeneracy in a 5×6 transportation problem occurs when the number of occupied cell is less than
A20 but greater than 10
B10
CZero
DInfinity
A non-degenerate basic solution needs m+n-1 = 5+6-1 = 10 occupied cells, so fewer than 10 is degenerate.
26.
★ Final term 2012Lecture 35
If a basic feasible solution contains less than "m + n – 1" (Here m is the number of rows, n is the number of columns in transportation problem) non negative allocation, then it is said to be
ADegenerate
BMultiple Solutions
CNon degenerate
DAlternative Optima
Fewer than m+n-1 basic allocations means the solution is degenerate.
27.
★ Final term Fall 2005Lecture 35
A transportation problem is degenerate, if while deriving a feasible solution an allocation to any cell
ASatisfies the Column requirements
BSatisfies the Row requirements
CSatisfies column as well as row requirements simultaneously
DNone of the above
When one allocation exhausts a row and a column together, fewer than m+n-1 cells get filled, giving degeneracy.
28.
★ Final term 2012Lecture 36
The cost matrix in assignment problem is always ___ (screen text: 'is always diagonal matrix')
Asquare matrix
Bidentity matrix
Czero matrix
An assignment problem needs equal rows and columns (adding dummies if needed), so its cost matrix is square.
29.
★ Final term 2012Lecture 36
Which of the following binary operation in assignment problem among all the elements in the given profit matrix from the highest element in the matrix
ASubtraction
BDivision
CMultiplication
DAddition
A maximization assignment is converted by subtracting every profit from the largest element.
30.
★ Final term paper (screens, paper 2)Lecture 36
Transportation technique or the simplex method cannot be used to solve the assignment problem because of
ADegeneracy
BInvolvement of dummy activities
CLooping among the entries of assignment matrix
DInequilibrium between demand and supply
An n×n assignment has only n positive allocations instead of 2n-1, so it is highly degenerate.
31.
★ Final term paper (screens, paper 2)Lecture 36
In assignment problem, each job requires exactly one resource.
ATrue
BFalse
CMay not be true
Assignment is one-to-one: each job gets exactly one resource and each resource one job.
32.
★ Final term Fall 2006Lecture 36
In assignment problem each job requires
AExactly one resource
BAt least one resource
CAt most one resource
Each job is assigned to exactly one resource and each resource to exactly one job.
33.
★ Final term paper (screens, paper 2)Lecture 37
The name of the method in getting the optimum assignment is
ASimplex method
BNorth west corner method
CVogal approximation method
DHungarian method
The Hungarian method is the standard algorithm for the optimal assignment.
34.
★ Final term 2012Lecture 38
If the mean arrival and mean service rates are 4 and 7 respectively in a queue then expected waiting time in the system is
A1/3
B3
C28
D7/4
Ws = 1/(μ-λ) = 1/(7-4) = 1/3.
35.
★ Final term 2012Lecture 38
In a bank, every 15 minutes one customer arrives for cashing the cheque. The staff in the payment counter takes only 10 minutes for serving a customer on an average, then the service rate "μ" = ______.
A6 per hour
B4 per hour
C10 per hour
D1/6 per hour
One service per 10 minutes means μ = 60/10 = 6 per hour.
36.
★ Final term 2012Lecture 38
A duplicating machine maintained for office use is used and operated by people in the office who need to make copies. Since the work to be copied varies in length (number of pages of the original) and copies required, the service rate is randomly distributed, the arrival rate is 5 per hour and the service rate is 10 per hour then the equipment utilization "ρ" is equal to
A0.50
B0.20
C5
D2
ρ = λ/μ = 5/10 = 0.5.
37.
★ Final term 2012Lecture 38
A repairman services three machines. For each machine the time between service requirements is 8 hours following exponential distribution. The time of repair also has the same distribution with a mean of 2 hours. Then the average rate "λ" is
A1/8 = 0.125
B8
C4
D¼ = 0.25
Each machine calls for service once per 8 hours on average, so λ = 1/8 per hour.
38.
★ Final term Fall 2005Lecture 38
The formula for expected number of customers in a system is
AL = lambda/(mu - lambda)
BL = lambda/(lambda - mu)
CL = mu/(lambda - mu)
DL = mu/(mu - lambda)
For M/M/1, Ls = lambda/(mu - lambda).
39.
★ Final term 2012Lecture 40
During a replacement if the value of money decreases at the rate of 3% then the present worth factor of unit amount to be spent after one year is given by
A0.25
B0.333
C0.9708
D4
v = 1/(1+0.03) = 0.9708.
40.
★ Final term 2012Lecture 40
If the money carries a rate of interest of 12% per year, the present worth factor of one rupee due in one year is
A0.08333
B0.89285
C0.0769
D13
v = 1/1.12 = 0.89285.
41.
★ Final term 2012Lecture 40
We go in probabilistic replacement model when period between installation and failure is
Avarying exponentially
Bvarying linearly
CConstant
Dis not constant (varying arbitrarily)
Probabilistic replacement models handle items whose life until failure is random, not a fixed or regular pattern.
42.
★ Final term 2012Lecture 40
If "Ni" be the Number of replacement made at the end of the ith week and "Pi" be the probability of failure during the ith week, then N1 = ______.
AN0P1
BN1P1
CN0P0
DN1P2
Replacements at the end of week 1 are the original N0 items times the probability P1 of failing in week 1.
43.
★ Final term 2012Lecture 40
The present worth of a rupee to be spent after a year is denoted by v and given by
Av = 1/(1 + r)
Bv = (1 + r)
Cv = (1 + r)/10
Dv = (1/r)
Discounting one year at rate r gives v = 1/(1+r).
44.
★ Final term 2012Lecture 40
Formula for a geometric series "x + vx + v^2x + ... + v^(n-1)x" is
AP(n) = x(1 - v^n)/(1 - v)
BP(n) = (1 - v^n)/(1 - v)
CP(n) = x(1 - v)/(1 - v^n)
DP(n) = (1 - v)/(1 - v^n)
The sum of n terms with first term x and ratio v is x(1-v^n)/(1-v).
45.
★ Final term paper (screens, paper 2)Lecture 40
Under the individual replacement policy an item is replaced on its
ASuccess
BFailure
CMaximum utilization
DMinimum utilization
Individual replacement means each item is replaced only when it fails.
46.
★ Final term paper (screens, paper 2)Lecture 40
In replacement Models, Capital Cost = (Item / Machine Cots) - (--------------------).
AResale Cost
BRunning Cost
CMaintenance Cost
DOperating Cost
Capital cost is purchase price minus resale (scrap) value.
47.
★ Final term Fall 2005Lecture 40
According to ______ strategy, replace an item if it fails before the optimum period 'P'
AIR
BIPR
CCPR (Common Preventive Replacement)
In individual preventive replacement an item is replaced on failure before age P, or preventively at P.
48.
★ Final term paper (screens, paper 2)Lecture 42
Many decision making problems involve a process that takes place in multiple stages in such a way that at each stage, the process is dependent on the strategy chosen. Such types of problems are called
ALinear Programming problems
BInteger programming problems
CDynamic programming problems
DAssignment problems
Multistage decision processes where each stage depends on the chosen policy are solved by dynamic programming.
49.
★ Final term 2012
In sequencing problems, the Johnson's algorithm in finding the optimal ordering of n jobs through 3 machines can be applied, if the problem is converted into following number of machines problems
A3n
B3n!
C2×3 = 6
D2
The n-jobs 3-machines case is reduced to an equivalent 2-machine problem (G = A+B, H = B+C) and Johnson's rule is applied.
50.
★ Final term 2012
Standard Deviation (S.D.) = ______ MAD
A√(2π/3)
B√(2/π)
C√(π/2)
D√(3π/2)
For a normal distribution SD ≈ 1.25 MAD = √(π/2) MAD.
51.
★ Final term 2012
MAD = ______ S.D.
A√(2/π)
B√(π/2)
C√(2π/3)
D√(3π/2)
For a normal distribution MAD ≈ 0.8 SD = √(2/π) SD.
52.
★ Final term 2012
If a company manufacture 'x' units of product 'A' and 'y' units of 'B' with associated profits of Rs.5 and Rs.3 then which of the following is the objective function to maximize is the profit?
Az = 15xy
Bz = 5x − 3y
Cz = 3x − 5y
Dz = 5x + 3y
Total profit is 5 per unit of A times x plus 3 per unit of B times y.
53.
★ Final term 2012
Zero valued artificial variables may appear as ______ variables in the final solution, when one or more of the original constraints equations is redundant.
Anon basic
Bbasic
Cslacks
Dsurplus
With redundant constraints an artificial variable can stay in the final basis at zero level, i.e. as a basic variable.
54.
★ Final term 2012
The inequality 2x + 3y ≥ 18 is equivalent to
A2x + 3y ≤ −18
B−2x − 3y ≥ 18
C−2x − 3y ≥ −18
D−2x − 3y ≤ −18
Multiplying both sides by −1 reverses the inequality sign.
55.
★ Final term paper (screens, paper 2)
The representation of reality in some physical form or in some form of mathematical equations may be discussed under the topic entitled as
ATransportation problems
BGame theory
CSimulation
DReplacement problems
Simulation imitates reality using a physical or mathematical model of the system.
56.
★ Final term paper (screens, paper 2)
Search and cutting methods are used to solve following types of problems
ATransportation
BAssignment
CInteger Programming
DQueuing problems
Branch-and-bound (search) and cutting-plane methods are integer programming techniques.
57.
★ Final term Fall 2005
For LP problem with 'n' decision variables, each of its corner point solution is at the intersection of ______ constraint boundaries.
A(n - 1) constraint boundaries
B'n' constraint boundaries
C(n + 1) constraint boundaries
DNone of the above
In n dimensions a corner point is fixed by n intersecting constraint boundaries.
No MCQs match this filter.Is filter mein koi MCQ nahi.
1.
★ Final term 2012Lecture 402 marks
The cost of a new machine is Rs. 5000. The maintenance cost during the nth year is given by Mn = Rs. 500 (n − 1), where n = 1, 2, 3, ---. If the discount rate per year is 0.05, determine discount factor (v^(r−1)) for each year.
Show answerJawab dekhein
v = 1/(1 + 0.05) = 0.9524. Discount factor v^(r−1): year 1: 1.0000; year 2: 0.9524; year 3: 0.9070; year 4: 0.8638; year 5: 0.8227; year 6: 0.7835; year 7: 0.7462; year 8: 0.7107 (continue multiplying by 0.9524 for later years).
2.
★ Final term 2012Lecture 312 marks
Determine whether the following Transportation model has initial feasible solution? Supply: O1 = 6, O2 = 8, O3 = 10 | Demand: D1 = 4, D2 = 6, D3 = 8, D4 = 6 (cells x11 … x34)
Show answerJawab dekhein
A transportation model has a feasible solution when it is balanced. Total supply = 6 + 8 + 10 = 24; total demand = 4 + 6 + 8 + 6 = 24. Supply = demand, so the model is balanced and an initial feasible solution exists (e.g. by the North-West Corner rule: x11 = 4, x12 = 2, x22 = 4, x23 = 4, x33 = 4, x34 = 6, using m + n − 1 = 6 cells).
3.
★ Final term 2012Lecture 423 marks
An oil company has 8 unit of money available for exploration of three sites. If oil is present at a site, the probability of finding it depends upon the amount allocated for exploiting the site as given below: units 0–8: Site I: 0.0, 0.0, 0.1, 0.2, 0.3, 0.5, 0.7, 0.9, 1.0 | Site II: 0.0, 0.1, 0.2, 0.3, 0.4, 0.6, 0.7, 0.8, 1.0 | Site III: 0.0, 0.1, 0.1, 0.2, 0.3, 0.5, 0.8, 0.9, 1.0. The probability that the oil exits at sites I, II and III is 0.4, 0.3 and 0.2 respectively; we have to find the optimal allocating of money. Stage I is given below; only do stage II. Stage I: Max Z = 0.4P1(x1) + 0.3 P2(x2) Subject to: x1 + x2 + x3 ≤ 8. f1(x1) for x1 = 0–8: 0, 0, 4, 8, 12, 20, 28, 36, 40
Show answerJawab dekhein
Values are scaled by 100: site II return = 100 × 0.3 × P2(x2) = 0, 3, 6, 9, 12, 18, 21, 24, 30 for x2 = 0–8. Stage II: f2(x) = max over x2 = 0..x of [30·P2(x2) + f1(x − x2)]. Results: x = 0: f2 = 0 (x2 = 0); 1: 3 (x2 = 1); 2: 6 (x2 = 2); 3: 9 (x2 = 3); 4: 12 (x2 = 0 or 4); 5: 20 (x2 = 0); 6: 28 (x2 = 0); 7: 36 (x2 = 0); 8: 40 (x2 = 0). E.g. for x = 8: x2 = 0 gives 0 + 40 = 40, x2 = 1 gives 3 + 36 = 39, x2 = 5 gives 18 + 12 = 30, so f2(8) = 40.
4.
★ Final term paper (screens, paper 2)Lecture 312 marks
Transportation table: Table (cost top-right, allocation bold): Row1: c=0,2,1 alloc (1,1)=5,(1,3)=1, supply 6 | Row2: c=2,1,5 alloc (2,2)=5,(2,3)=2, supply 7 | Row3: c=2,4,3 alloc (3,3)=7, supply 7 | Demand 5, 5, 10. What is the total shipping cost of the above table?
Assignment (reduced) matrix, Programmers 1-4 vs jobs A-D: 1: 30, 10, 0, 10 | 2: 0, 10, 40, 0 | 3: 0, 30, 20, 0 | 4: 0, 0, 0, 10. Assign each job to each programmer.
Show answerJawab dekhein
Assign on zeros, one per row and column. Row 1 has a single zero at C: 1->C. Column B has a single zero at row 4: 4->B. Rows 2 and 3 both have zeros at A and D: 2->A and 3->D (or alternatively 2->D and 3->A). Optimal assignment: 1-C, 2-A, 3-D, 4-B (alternative optimum 1-C, 2-D, 3-A, 4-B), with zero cost in the reduced matrix.
7.
★ Final term paper (screens, paper 2)Lecture 403 marks
A company has a machine whose cost is Rs. 30,000. Its maintenance cost and resale value at the end of different years are: Year 1-6 Maintenance: 4500, 4700, 5000, 5500, 6500, 7500 | Resale: 27000, 25300, 24000, 21000, 18000, 13000. Determine capital cost for each year.
Show answerJawab dekhein
Capital cost = purchase price - resale value: Year 1: 30000-27000 = 3000; Year 2: 30000-25300 = 4700; Year 3: 30000-24000 = 6000; Year 4: 30000-21000 = 9000; Year 5: 30000-18000 = 12000; Year 6: 30000-13000 = 17000.
8.
★ Final term paper (screens, paper 2)Lecture 313 marks
Express the following Transportation problem (T.P) table into algebraic form with proper objective function and non-negative constraints: O1: c11, c12, c13, supply 5 | O2: c21, c22, c23, supply 3 | O3: c31, c32, c33, supply 10 | Demand: 4, 6, 8.
Show answerJawab dekhein
Let xij = units shipped from Oi to Dj. Minimize Z = sum over i,j of cij xij = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23 + c31x31 + c32x32 + c33x33. Supply: x11 + x12 + x13 = 5; x21 + x22 + x23 = 3; x31 + x32 + x33 = 10. Demand: x11 + x21 + x31 = 4; x12 + x22 + x32 = 6; x13 + x23 + x33 = 8. xij >= 0 for all i, j. (Balanced: total supply 18 = total demand 18.)
9.
★ Final term Fall 2005Lecture 313 marks
A manufacturer has distribution centers at X, Y and Z. These centers have availability of 45, 20 and 30 units of the product. His retail outlets at A, B, C, D and E require 25, 10, 20, 30 and 15 units respectively. Cost per unit: X: 50, 30, 40, 50, 50 | Y: 35, 30, 100, 45, 60 | Z: 40, 60, 85, 35, 30 (columns A-E). Is this model balanced? If 'NO' balance the above Transportation model.
Show answerJawab dekhein
Total supply = 45+20+30 = 95; total demand = 25+10+20+30+15 = 100. Supply < demand, so the model is NOT balanced. Add a dummy distribution centre (row) with availability 100-95 = 5 units and zero transport cost to every outlet: Dummy: 0, 0, 0, 0, 0 (supply 5). Now supply = demand = 100 and the problem can be solved; whatever is 'shipped' from the dummy is unmet demand.
1.
★ Final term paper (screens, paper 2)Lecture 335 marks
★ Final term paper (screens, paper 2)Lecture 295 marks
Write down the dual of the following Linear Programming problem; Min. Z = 3x1 + 4x2 + 6x3 subject to: x1 + x2 - x4 >= 10; -x1 - x2 + x4 <= -10; x1 - x5 = 0; x2 + x6 = 0; x3 - x7 = 0; x1, x3, x4, x5, x6, x7 >= 0.
Show answerJawab dekhein
Write constraint 2 as x1 + x2 - x4 >= 10. Dual variables: y1, y2 >= 0 for the two >= constraints; w3, w4, w5 unrestricted for the three equalities. x2 is unrestricted (not in the sign list), so its dual constraint is an equality. Dual: Maximize W = 10y1 + 10y2 subject to: (x1) y1 + y2 + w3 <= 3; (x2) y1 + y2 + w4 = 4; (x3) w5 <= 6; (x4) -y1 - y2 <= 0; (x5) -w3 <= 0; (x6) w4 <= 0; (x7) -w5 <= 0; y1, y2 >= 0; w3, w4, w5 unrestricted.
3.
★ Final term Fall 2005Lecture 385 marks
The arrival rate of customers at a banking counter follows Poisson distribution with a mean of 45 customers per hour. The service rate of the counter clerk also follows Poisson distribution with a mean of 60 customers per hour. Find the following 1. The probability of having 10 customers in the system 2. Average number of customers waiting in the system 3. Average number of customers waiting in the queue 4. Average waiting time of customers in the system 5. Average waiting time of customers in the queue
Consider the following LP problem: Minimize Z = 12x1 + 18x2 + 15x3 subject to 4x1 + 8x2 + 6x3 >= 64; 3x1 + 6x2 + 12x3 >= 96; x1, x2, x3 >= 0. (a) Write the associated Dual Problem of the above Primal Problem. (b) The optimal table for phase-I is given: Z row: 0, 0, 0, 0, 0, 0, 1 | 1 (cols x1, x2, x3, s1, s2, R1, R2 | RHS); x2: 1/2, 1, 0, -1/5, 1/10, 1/5, -1/10 | 16/5; x3: 0, 0, 1, 1/10, -2/15, -1/10, 2/15 | 32/5. Using this table find the Optimal Solution for Phase-II.
Show answerJawab dekhein
(a) Dual: Maximize W = 64y1 + 96y2 subject to 4y1 + 3y2 <= 12; 8y1 + 6y2 <= 18; 6y1 + 12y2 <= 15; y1, y2 >= 0. (b) Phase II: drop R1, R2 columns and use the original objective Min Z = 12x1 + 18x2 + 15x3 with basis x2 = 16/5, x3 = 32/5. Z-row (zj - cj): x1: 18(1/2) + 15(0) - 12 = -3; s1: 18(-1/5) + 15(1/10) - 0 = -2.1; s2: 18(1/10) + 15(-2/15) - 0 = -0.2; x2, x3: 0. RHS Z = 18(16/5) + 15(32/5) = 57.6 + 96 = 153.6. For minimization all zj - cj <= 0, so the table is already optimal: x1 = 0, x2 = 16/5 = 3.2, x3 = 32/5 = 6.4, Min Z = 153.6. Check: 8(3.2) + 6(6.4) = 64 and 6(3.2) + 12(6.4) = 96. Dual values y1 = 2.1, y2 = 0.2 give W = 134.4 + 19.2 = 153.6 (equal objectives confirm optimality).
5.
★ Final term Fall 20057 marks
A manager has to allocate five different jobs to five workers. Times: Job1: 10, 12, 15, 12, 8 | Job2: 7, 16, 14, 14, 11 | Job3: 13, 14, 7, 9, 9 | Job4: 12, 10, 11, 13, 10 | Job5: 8, 13, 15, 11, 15 (columns W1-W5). How the manager should assign one job to a worker so as to minimize the total man-hours?
Consider the following LP problem: Maximize Z = 10x1 + 3x2 subject to 2x1 + 3x2 <= 18; 6x1 + 5x2 >= 60; x1, x2 >= 0. Solve the above problem by Graphical Method.
Show answerJawab dekhein
Plot 2x1 + 3x2 = 18 through (9, 0) and (0, 6); the region <= 18 lies below it toward the origin. Plot 6x1 + 5x2 = 60 through (10, 0) and (0, 12); the region >= 60 lies above it. Over the first region the largest value of 6x1 + 5x2 is at its corners: (0,0) 0, (9,0) 54, (0,6) 30, all below 60. So the two regions do not overlap in the first quadrant: there is no feasible solution and the LP is infeasible (no optimum value of Z).
7.
★ Final term Fall 20044 marks
Define the followings. (a) Impossible Assignment (b) Unbounded Solution.
Show answerJawab dekhein
(a) Impossible assignment: in an assignment problem, a particular job cannot (or must not) be given to a particular worker/machine (e.g. machine cannot do that job). It is handled by putting a very large cost M (or a dash) in that cell, so the Hungarian method never selects it. (b) Unbounded solution: an LP whose objective can be increased (max) or decreased (min) without limit while staying feasible, because the feasible region is open in the improving direction. In the simplex table it shows up when the entering variable's column has no positive entry, so no leaving variable (ratio test) exists.
8.
★ Final term Fall 2004Lecture 2310 marks
Consider the problem: maximize z = x1 + 5x2 + 3x3 subject to x1 + 2x2 + x3 = 3; 2x1 - x2 = 4; x1, x2, x3 >= 0. The variable x3 plays the role of a slack. Use big M-method to solve the problem.
Show answerJawab dekhein
Add artificial R in the 2nd constraint: Max z = x1 + 5x2 + 3x3 - MR; x1 + 2x2 + x3 = 3; 2x1 - x2 + R = 4. Initial basis x3 = 3, R = 4. Substituting x3 = 3 - x1 - 2x2 and R = 4 - 2x1 + x2 in the objective gives z = (9 - 4M) + (2M - 2)x1 - (M + 1)x2, so the Z-row entries (zj - cj) are x1: -(2M - 2), x2: M + 1, RHS 9 - 4M. Iteration 1: x1 enters (most negative zj - cj = -(2M - 2)). Ratios: x3 row 3/1 = 3, R row 4/2 = 2 -> R leaves, pivot 2. New R-row: x1 - 1/2 x2 + 1/2 R = 2. New x3-row: 5/2 x2 + x3 - 1/2 R = 1. Z-row: z = 5 - 2x2 - (M - 1)R, i.e. zj - cj for x2 = 2 >= 0 and for R = M - 1 >= 0. All zj - cj >= 0, so optimal: x1 = 2, x2 = 0, x3 = 1, maximum z = 5. Check: 2 + 0 + 1 = 3 and 4 - 0 = 4.
9.
★ Final term Fall 2004Lecture 354 marks
How the problem of the degeneracy arises in a transportation problem?
Show answerJawab dekhein
A basic feasible solution of an m x n transportation problem must have m + n - 1 positive allocations in independent cells. Degeneracy arises when fewer than m + n - 1 cells are occupied. This happens (i) in the initial solution (NWC, LCM or VAM) when one allocation satisfies a row supply and a column demand simultaneously, so both are crossed out together, or (ii) during improvement (MODI / stepping stone) when two or more cells in the loop reach zero at the same time. With too few occupied cells the u_i, v_j cannot all be found. Remedy: put a very small quantity epsilon (treated as zero) in a suitable independent unoccupied cell (usually least cost) to make the count m + n - 1, then continue and set epsilon = 0 at the end.
10.
★ Final term Fall 2004Lecture 384 marks
Define the followings in Queuing Theory. a. Customer b. Server c. Priority
Show answerJawab dekhein
(a) Customer: the unit that arrives requiring service, e.g. people, machines, ships, jobs or calls; arrivals form the input process. (b) Server: the facility or person that provides the service, e.g. clerk, counter, repairman or machine; there may be one or several servers in parallel or in series, each with a service-time distribution. (c) Priority: a queue discipline in which some customers are served before others regardless of arrival time, e.g. emergency patients; it may be pre-emptive (higher-priority customer interrupts the one in service) or non-pre-emptive (waits until current service ends).
11.
★ Final term Fall 2004Lecture 264 marks
What are the variants of the simplex method? Write few lines about the followings. (a) Unbounded solution. (b) Unrestricted variables.
Show answerJawab dekhein
Variants (special cases) of the simplex method: degeneracy, alternative (multiple) optima, unbounded solutions, infeasible solutions, and unrestricted (free) variables. (a) Unbounded solution: the objective can improve without limit; detected when the entering variable's column has all entries <= 0, so no ratio exists and no variable can leave. Usually the model is missing a constraint. (b) Unrestricted variables: a variable allowed to be negative, zero or positive. Simplex needs non-negative variables, so replace it by the difference of two non-negative ones, x = x' - x'' (x', x'' >= 0); at most one of them is basic, and x is recovered at the end.
12.
★ Final term Fall 2006Lecture 2310 marks
Solve the following problem with Big M - Method. Minimize Z = 3X1 + 2X2 + X3 subject to X1 + X2 = 7; 3X1 + X2 + X3 >= 10; X1, X2, X3 >= 0
In a college, every 15 minutes one student arrives for admission information. The staff in the only information counter takes 10 minutes for serving a student on an average. State suitable assumption and find. I. The average queue length. II. Increase in the arrival rate in order to justify for second counter (when the waiting time of a student is at least 15 minutes the management will increase one more counter).
Show answerJawab dekhein
Assumptions: single server (M/M/1), Poisson arrivals, exponential service times, first-come-first-served, infinite population and queue capacity. lambda = 60/15 = 4 per hour, mu = 60/10 = 6 per hour, rho = 4/6 = 2/3. I. Average queue length Lq = lambda^2/(mu(mu - lambda)) = 16/(6 x 2) = 4/3 = 1.33 students (average length of non-empty queue = mu/(mu - lambda) = 3). II. Second counter is justified when Wq = lambda'/(mu(mu - lambda')) >= 15 min = 1/4 hr: lambda'/(6(6 - lambda')) = 1/4 -> 4 lambda' = 36 - 6 lambda' -> lambda' = 3.6 per hour (one student every 16.7 minutes). The present Wq = 4/(6 x 2) = 1/3 hr = 20 minutes already exceeds 15 minutes, so no increase is needed: at the current rate of 4 per hour (anything at or above 3.6 per hour) the second counter is already justified.
15.
★ Final term Fall 2006Lecture 4010 marks
A machine costs Rs. 8000. Annual operating cost are Rs. 1000 for the first year, and then increase by Rs. 500 every year. Resale price are Rs. 4000 for the first year and then decrease by Rs. 500 every year. Determine at which age it is profitable to replace the machine.
Show answerJawab dekhein
Average annual cost A(n) = [C - S(n) + cumulative running cost]/n with C = 8000. Year n: running cost R(n), cumulative R, resale S(n), total cost C - S + cumR, average: n=1: 1000, 1000, 4000, 5000, 5000; n=2: 1500, 2500, 3500, 7000, 3500; n=3: 2000, 4500, 3000, 9500, 3166.67; n=4: 2500, 7000, 2500, 12500, 3125; n=5: 3000, 10000, 2000, 16000, 3200; n=6: 3500, 13500, 1500, 20000, 3333.33. The average annual cost is lowest (Rs. 3125) at n = 4 and rises after that, so the machine should be replaced at the end of the 4th year.