(a) Solve the following Linear Programming problem using Two Phase method : Maximize Z = 3x₁ - x₂ Subject to 2x₁ + x₂ ≥ 2, x₁ + 3x₂ ≤ 2, x₂ ≤ 4, x₁ ≥ 0, x₂ ≥ 0

(b)(i) Solve the above assignment problem. Cell values represent cost of assigning job A,

Question

(a) Solve the following Linear Programming problem using Two Phase method : Maximize Z = 3x₁ - x₂ Subject to 2x₁ + x₂ ≥ 2, x₁ + 3x₂ ≤ 2, x₂ ≤ 4, x₁ ≥ 0, x₂ ≥ 0

(b)(i) Solve the above assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

(b)(ii) Write down the dual for the given primal problem. Max Z = 6x₁ - 5x₂ + 7x₃ + x₄ Subject to 2x₁ + 4x₂ - x₃ + x₄ ≤ 4, x₁ - x₂ + 6x₃ + 7x₄ ≥ 5, 2x₁ + 2x₂ + 4x₃ + 5x₄ = 6, x₁ + 8x₂ + x₃ = 7; x₁ and x₄ unrestricted, x₂ ≥ 0, x₃ ≥ 0

(c) What is a basic Economic Order Quantity (EOQ) model in Inventory Control and state the assumption made. A Company estimates that it will sell 12000 units of its products for the forthcoming year. The ordering cost is ₹100 per order and the carrying cost per year is 20% of the purchase price per unit. The purchase price per unit is ₹50. Find (i) EOQ (ii) Number of orders per year (iii) Time between successive orders.

UPSC Answer Check · Accepted Answer

(a) Convert to equality form. For 2x₁ + x₂ ≥ 2, subtract surplus s₁ and add artificial a₁: 2x₁ + x₂ - s₁ + a₁ = 2. For x₁ + 3x₂ ≤ 2 add slack s₂: x₁ + 3x₂ + s₂ = 2. For x₂ ≤ 4 add slack s₃: x₂ + s₃ = 4. All variables are non-negative.

Phase I minimises W = a₁. Initial basis is a₁, s₂, s₃, with a₁ = 2, s₂ = 2, s₃ = 4. From row 1, a₁ = 2 - 2x₁ - x₂ + s₁, so W = 2 - 2x₁ - x₂ + s₁. The most negative coefficient is -2, so x₁ enters. Ratio test: a₁ row gives 2/2 = 1, s₂ row gives 2/1 = 2; hence a₁ leaves. Pivot on the coefficient 2 in row 1.

After pivot:
x₁ = 1 - 1/2x₂ + 1/2s₁ - 1/2a₁,
s₂ = 1 - 5/2x₂ - 1/2s₁ + 1/2a₁,
s₃ = 4 - x₂,
W = a₁.
With nonbasic variables x₂ = s₁ = a₁ = 0, W = 0 and the reduced costs are non-negative. Thus Phase I is optimal and the artificial variable is removed. The basic feasible solution is x₁ = 1, x₂ = 0, s₂ = 1, s₃ = 4.

Phase II maximises Z = 3x₁ - x₂. Using the x₁ row with a₁ = 0,
Z = 3(1 - 1/2x₂ + 1/2s₁) - x₂ = 3 - 5/2x₂ + 3/2s₁.
For maximisation, s₁ enters because its coefficient is positive. Ratio test: only s₂ decreases as s₁ increases, since s₂ = 1 - 5/2x₂ - 1/2s₁; ratio is 1/(1/2) = 2, so s₂ leaves. Pivot gives s₁ = 2 - 5x₂ - 2s₂.

Updated equations:
x₁ = 2 - 3x₂ - s₂,
s₁ = 2 - 5x₂ - 2s₂,
s₃ = 4 - x₂,
Z = 6 - 10x₂ - 3s₂.
All nonbasic coefficients in the Z-row are non-positive, so the tableau is optimal at x₂ = s₂ = 0. Hence x₁ = 2, x₂ = 0 and maximum Z = 6; this point satisfies 4 ≥ 2, 2 ≤ 2 and 0 ≤ 4.

(b)(i) Use Hungarian method to minimise total cost. Row minima are 10, 5, 11, 8. Subtracting row minima gives:
A: 0, 2, 9, 1; B: 0, 5, 2, 3; C: 1, 3, 2, 0; D: 0, 7, 3, 1.
Column minima are 0, 2, 2, 0. Subtracting column minima gives:
A: 0, 0, 7, 1; B: 0, 3, 0, 3; C: 1, 1, 0, 0; D: 0, 5, 1, 1.
Independent zeros can be assigned as A-II, B-III, C-IV, D-I. Since four independent zeros exist, the assignment is optimal. The total row and column reduction is 38; because the selected cells are zero in the reduced matrix, their original cost equals this lower bound. Minimum cost is 12 + 7 + 11 + 8 = 38. Assignment: A to II, B to III, C to IV, D to I; minimum cost = 38 cost units.

(b)(ii) Let y₁, y₂, y₃, y₄ be dual variables for the four primal constraints. Since the primal is a maximisation problem, the dual is a minimisation problem. For a max primal, a ≤ constraint gives a non-negative dual variable, a ≥ constraint gives a non-positive dual variable, and an equality constraint gives an unrestricted dual variable. Thus y₁ ≥ 0, y₂ ≤ 0, y₃ and y₄ are unrestricted. Since x₁ and x₄ are unrestricted, their dual constraints are equalities; since x₂ and x₃ are non-negative, their dual constraints are ≥. The left-hand sides are obtained by taking the coefficients of each primal variable down the columns.

Dual: Minimise W = 4y₁ + 5y₂ + 6y₃ + 7y₄ subject to
2y₁ + y₂ + 2y₃ + y₄ = 6,
4y₁ - y₂ + 2y₃ + 8y₄ ≥ -5,
-y₁ + 6y₂ + 4y₃ + y₄ ≥ 7,
y₁ + 7y₂ + 5y₃ = 1,
with y₁ ≥ 0, y₂ ≤ 0, y₃, y₄ unrestricted.

(c) A basic EOQ model is a deterministic single-item inventory model. It assumes constant annual demand D, fixed ordering cost S per order, constant unit purchase price P, linear holding cost H per unit per year, no shortages, instantaneous replenishment, constant lead time, and no quantity discounts. The formula is valid when D, S and H are positive and the order quantity is treated as continuous; if whole units are required, the result is rounded.

Here D = 12000 units/year, S = ₹100/order, P = ₹50/unit. The holding cost is 20% of purchase price, so H = 20% × 50 = ₹10/unit/year.

The EOQ formula is Q = √(2DS/H). Therefore
Q = √(2 × 12000 × 100 / 10) = √240000 = 200√6 units.

Number of orders per year:
N = D/Q = 12000/(200√6) = 10√6 orders/year.

Time between successive orders:
T = 1/N = √6/60 year. If a 365-day year is taken, T = 365√6/60 = 73√6/12 days.

EOQ = 200√6 units; number of orders = 10√6 orders/year; time between orders = √6/60 year (73√6/12 days for 365 days/year).

(a) Solve the following Linear Programming problem using Two Phase method : Maximize Z = 3x₁ - x₂ Subject to 2x₁ + x₂ ≥ 2, x₁ +…

The figure this question refers to, in words

Model answer

What "Solve" is asking you to do

Structure that answers it

Where marks are lost

How this answer will be evaluated

Approach

Key points expected

Evaluation rubric

Must cover

Loses marks

Earns more

Extra mark

Must cover

Loses marks

Earns more

Extra mark

Must cover

Loses marks

Earns more

Extra mark

Must cover

Loses marks

Earns more

Extra mark

Practice this exact question

More from Statistics 2023 Paper II