Operations Research

Add slack variables $s_1, s_2, s_3$:

$\text{Max } Z = 4A + 3B + 6C + 0s_1 + 0s_2 + 0s_3$ $2A + 3B + 2C + s_1 = 440,\quad 4A + 3C + s_2 = 470,\quad 2A + 5B + s_3 = 430$

Initial table (basis $s_1, s_2, s_3$; $Z_j = 0$; $C_j - Z_j$ = 4, 3, 6, 0, 0, 0). Entering variable: $C$ (largest, 6).

$s_2$ leaves (pivot 3).

Iteration 1

$Z = 6 \times 470/3 = 940$. $B$ enters and $s_1$ leaves (pivot 3).

Iteration 2 (optimal)

All $C_j - Z_j \le 0$, so the solution is optimal.

Result

$A = 0,\quad B = \tfrac{380}{9} \approx 42.22,\quad C = \tfrac{470}{3} \approx 156.67,\quad Z_{max} = \tfrac{3200}{3} \approx 1066.67$

Interpretation

• Product A should not be produced, since its reduced cost is $10/3$ per unit. Making one unit would reduce profit by about 3.33.
• Resources 1 and 2 are fully used ($s_1 = s_2 = 0$), so they are scarce. Their shadow prices are 1 and $4/3$ per unit: each extra unit of resource 1 raises profit by 1 and each extra unit of resource 2 by 1.33.
• Resource 3 has $s_3 = 1970/9 \approx 218.9$ units unused, so its shadow price is 0 and more of it adds nothing.

Use the Big-M method. Add slack $s_1$ to the first constraint, surplus $s_2, s_3$ and artificial $a_2, a_3$ to the $\ge$ constraints:

$\text{Min } Z = 20A + 10B + 0s_1 + 0s_2 + 0s_3 + Ma_2 + Ma_3$ $A + 2B + s_1 = 40,\quad 4A + 3B - s_2 + a_2 = 60,\quad 3A + B - s_3 + a_3 = 30$

Start with basis $s_1, a_2, a_3$. Optimality for minimisation: all $C_j - Z_j \ge 0$.

Table 0 ($Z = 90M$)

A enters (most negative), $a_3$ leaves (ratio 30/3 = 10, against 15 for $a_2$ and 40 for $s_1$).

Table 1 ($Z = 20M + 200$)

B enters, $a_2$ leaves (ratios: 18, 12, 30).

Table 2 ($Z = 240$)

All $C_j - Z_j \ge 0$ and no artificial variable remains in the basis, so the solution is optimal.

Result: $A = 6$, $B = 12$, $Z_{min} = 20(6) + 10(12) = \textbf{240}$.

Interpretation

• The minimum cost is 240, obtained by using 6 units of A and 12 units of B.
• Constraint 1 has slack $s_1 = 10$: $A + 2B = 30 \le 40$, so 10 units of capacity are unused.
• Constraints 2 and 3 are binding ($4A + 3B = 60$ and $3A + B = 30$ are met exactly).
• Dual values: 2 for constraint 2 and 4 for constraint 3. Raising the requirement 60 by one unit raises the minimum cost by 2, and raising 30 by one unit raises it by 4.

Problem: Minimize $Z = 25A + 10B$ subject to $A+B=50$, $A\ge20$, $B\le40$, $A,B\ge0$.

Standard form (Big-M method). Add surplus $s_1$ and artificial variables $a_1, a_2$ for the first two constraints, and slack $s_2$ for the third:

$A+B+a_1 = 50,\qquad A - s_1 + a_2 = 20,\qquad B + s_2 = 40$

$\text{Minimize } Z = 25A+10B+Ma_1+Ma_2$

Initial basis: $a_1 = 50$, $a_2 = 20$, $s_2 = 40$.

Iteration 1. $A$ has the most negative net evaluation (it has the largest effect in reducing the $M$ terms). Ratios: $50/1$, $20/1$; the minimum is 20, so $a_2$ leaves and $A$ enters. Row operations give $A=20$, $a_1 = 30$ (row: $B + s_1 + a_1 = 30$), $s_2=40$.

Iteration 2. $B$ enters (its net evaluation is still negative because of the $M$ attached to $a_1$). Ratios: $30/1$ and $40/1$, so $a_1$ leaves. Now $B=30$, $A=20$, $s_2 = 10$.

Optimality. The basis is $A=20$, $B=30$, $s_2=10$. Writing $A = 20 + s_1$ and $B = 30 - s_1$:

$Z = 25(20+s_1) + 10(30-s_1) = 800 + 15s_1$

The net evaluation of $s_1$ is $+15 \ge 0$ (and artificials are out), so the solution is optimal.

Result: $A = 20$, $B = 30$, minimum $Z = 25(20)+10(30) =$ 800.

Interpretation. The requirement $A+B=50$ is met using the cheaper item $B$ as far as possible, and since $A$ must be at least 20, the minimum amount of $A$ is used. The $A\ge20$ constraint is binding (surplus $s_1=0$). The constraint $B\le40$ is not binding, with slack $s_2 = 10$ (B = 30). Each extra unit forced into $A$ in place of $B$ raises cost by $25-10=$ 15 per unit.

The dominance rule reduces the size of a game's payoff matrix when there is no saddle point, by removing strategies that a rational player would never choose.

Rules (Player A chooses rows and maximises; Player B chooses columns and minimises):

1. Row dominance: if every payoff in row $i$ is greater than or equal to the corresponding payoff in row $k$, row $i$ dominates row $k$ and row $k$ is deleted, since A would never prefer it.
2. Column dominance: if every payoff in column $j$ is less than or equal to the corresponding payoff in column $l$, column $j$ dominates column $l$ and column $l$ is deleted, since B would never choose it.
3. Averaging: a row (or column) can also be dominated by a convex combination (weighted average) of two or more other rows (or columns).

Procedure: delete dominated rows and columns, repeating until none remain. Then look for a saddle point in the reduced matrix, or solve it by the algebraic, graphical or linear programming method. Strategies deleted are played with probability zero in the optimal mixed strategy.

Example: in the matrix with rows $(3,5)$ and $(2,4)$, the first row dominates the second, because $3\ge2$ and $5\ge4$.

Queue: a queue (waiting line) is formed when customers or units arrive at a service facility and must wait because the facility is busy. Examples are patients at a clinic, customers at a bank counter and vehicles at a toll plaza.

Single-channel (M/M/1) model: Poisson arrivals at rate $\lambda$, one server with exponential service at rate $\mu$, FCFS discipline, infinite population and queue length, with $\rho = \lambda/\mu < 1$.

Operating characteristics:

These satisfy Little's law: $L_s = \lambda W_s$ and $L_q = \lambda W_q$. They also satisfy $L_s = L_q + \lambda/\mu$.

Network (activity-on-arrow, events 1 to 8)

Event 5 is the start of F (after D, and after C through the dummy 4 to 5). Event 6 is the start of E (after B, and after C through the dummy 4 to 6). E and F both end at event 7, where G starts, and G ends at event 8.

Forward and backward pass

Path lengths: $A\text{-}C\text{-}E\text{-}G = 7+5+7+6 = 25$; $A\text{-}B\text{-}E\text{-}G = 24$; $A\text{-}D\text{-}F\text{-}G = 24$; $A\text{-}C\text{-}F\text{-}G = 23$.

Critical path: $A \to C \to E \to G$, with project duration 25 days.

Bottleneck (critical) activities: A, C, E and G, which have zero slack. Any delay in them delays the whole project. B, D and F each have 1 day of slack.

Solve by the Big-M method (artificial variables are needed for the $\ge$ constraints). Add slack $s_1$ to the first constraint, surplus $s_2, s_3$ and artificial $a_2, a_3$ to the $\ge$ constraints:

$\text{Min } Z = 20A + 10B + 0s_1 + 0s_2 + 0s_3 + Ma_2 + Ma_3$ $A + 2B + s_1 = 40,\quad 4A + 3B - s_2 + a_2 = 60,\quad 3A + B - s_3 + a_3 = 30$

Start with basis $s_1, a_2, a_3$. Optimality for minimisation: all $C_j - Z_j \ge 0$.

Table 0 ($Z = 90M$)

A enters (most negative), $a_3$ leaves (ratio 30/3 = 10, against 15 for $a_2$ and 40 for $s_1$).

Table 1 ($Z = 20M + 200$)

B enters, $a_2$ leaves (ratios: 18, 12, 30).

Table 2 ($Z = 240$)

All $C_j - Z_j \ge 0$ and no artificial variable remains in the basis, so the solution is optimal.

Result: $A = 6$, $B = 12$, $Z_{min} = 20(6) + 10(12) = \textbf{240}$.

Interpretation

• The minimum cost is 240, obtained by using 6 units of A and 12 units of B.
• Constraint 1 has slack $s_1 = 10$: $A + 2B = 30 \le 40$, so 10 units of capacity are unused.
• Constraints 2 and 3 are binding ($4A + 3B = 60$ and $3A + B = 30$ are met exactly).
• Dual values: 2 for constraint 2 and 4 for constraint 3. Raising the requirement 60 by one unit raises the minimum cost by 2, and raising 30 by one unit raises it by 4.

Operating characteristics measure the performance of a queuing system. For the single-channel (M/M/1) model with arrival rate $\lambda$ and service rate $\mu$ ($\lambda<\mu$):

• Utilisation (traffic intensity): $\rho=\dfrac{\lambda}{\mu}$, the fraction of time the server is busy. Probability the system is empty: $P_0=1-\rho$.
• Probability of $n$ customers in the system: $P_n=(1-\rho)\rho^n$.
• Average number in the system: $L_s=\dfrac{\lambda}{\mu-\lambda}$.
• Average number waiting in the queue: $L_q=\dfrac{\lambda^2}{\mu(\mu-\lambda)}$.
• Average time in the system: $W_s=\dfrac{1}{\mu-\lambda}$.
• Average waiting time in the queue: $W_q=\dfrac{\lambda}{\mu(\mu-\lambda)}$.
• Average length of non-empty queue: $\dfrac{\mu}{\mu-\lambda}$.
• Probability that waiting time exceeds $t$: $P(W_s>t)=e^{-(\mu-\lambda)t}$.

They are linked by Little's law, $L_s=\lambda W_s$ and $L_q=\lambda W_q$, and $L_s=L_q+\rho$. If $\lambda\ge\mu$, the queue grows without bound.

Maximize $Z=4A+3B+6C$ subject to $2A+3B+2C\le440$, $4A+3C\le470$, $2A+5B\le430$, $A,B,C\ge0$.

Add slack variables $s_1,s_2,s_3$. The initial basis is $s_1,s_2,s_3$ with $Z_j-C_j=(-4,-3,-6)$.

Iteration 1. $C$ enters (most negative). Ratios: $440/2=220$, $470/3=156.67$ (minimum), third row has coefficient 0. So $s_2$ leaves (pivot 3).

Iteration 2. $B$ enters. Ratios: $(380/3)/3=42.22$, $430/5=86$. So $s_1$ leaves (pivot 3).

All $Z_j-C_j\ge0$, so the solution is optimal.

Result: $A=0$, $B=\dfrac{380}{9}\approx42.22$, $C=\dfrac{470}{3}\approx156.67$, and

$Z_{max}=3\left(\tfrac{380}{9}\right)+6\left(\tfrac{470}{3}\right)=\tfrac{3200}{3}\approx1066.67$

Interpretation:

• Product A should not be produced, since its reduced cost is $10/3$: producing one unit would lower profit by $10/3$.
• Produce about 42.22 units of B and 156.67 units of C for a maximum profit of about 1066.67.
• Resources 1 and 2 are fully used, with shadow prices 1 and $4/3$ per unit (the $Z_j-C_j$ values under $s_1$ and $s_2$). Resource 3 has slack of about 218.9 units and shadow price 0.

Network (precedence form): A is first. B, C and D follow A. E follows B and C. F follows C and D. G follows E and F, and is the last activity.

Forward pass (days):

Paths:

• A-B-E-G: $7+4+7+6=24$
• A-C-E-G: $7+5+7+6=25$
• A-C-F-G: $7+5+5+6=23$
• A-D-F-G: $7+6+5+6=24$

Critical path: A - C - E - G, with project duration 25 days.

Bottleneck (critical) activities: A, C, E and G, which have zero slack. Any delay in them delays the whole project, while B, D and F each have 1 day of slack.

Supply: X = 5, Y = 20, Z = 20 (total 45). Demand: A = 20, B = 15, C = 10 (total 45). The problem is balanced.

Cost matrix

Initial solution (Vogel's approximation method)

Allocations: Y to C = 10, Y to A = 10, X to A = 5, Z to A = 5, Z to B = 15. Cost $= 5(9)+10(10)+10(8)+5(13)+15(10) = 45+100+80+65+150 = 440$.

Optimality test (MODI). Basic cells XA, YA, YC, ZA, ZB: set $u_X=0$, giving $v_A=9$, $u_Y=1$, $u_Z=4$, $v_C=7$, $v_B=6$. Opportunity costs $d_{ij}=c_{ij}-u_i-v_j$ for empty cells: XB $=4$, XC $=3$, YB $=7$, ZC $=8-4-7=-3$. ZC is negative, so the solution can be improved.

Improvement. Loop: $+ZC, -ZA, +YA, -YC$. Shift $\theta=\min(5,10)=5$: ZC = 5, ZA = 0, YA = 15, YC = 5.

New solution

Re-test. $u_X=0, v_A=9, u_Y=1, v_C=7, u_Z=1, v_B=9$. Empty cells: XB $=10-9=1$, XC $=10-7=3$, YB $=14-10=4$, ZA $=13-10=3$. All are $\ge 0$, so this is optimal.

Minimum cost $= 5(9)+15(10)+5(8)+15(10)+5(8) = 45+150+40+150+40 =$ Rs 425 (in the units of cost given).

Schedule: X sends 5 to A; Y sends 15 to A and 5 to C; Z sends 15 to B and 5 to C.

Network diagram. Events (nodes) 1 to 7 with dummy activity as required:

• Start node 1; A: 1 to 2; B: 1 to 3.
• C: 2 to 5; D: 3 to 4; F: 3 to 5.
• E (needs A and D): 4 to 5, with a dummy activity from node 2 to node 4 so that A also precedes E.
• G (needs C, E, F): 5 to 6; H: 6 to 7 (end).

Forward and backward pass (weeks)

Here $ES$ of each activity is the largest EF among its predecessors (e.g. G: $\max(11,17,18)=18$), and the backward pass gives $LF$ as the smallest LS of its successors.

Critical activities (zero slack): B, F, G, H.

Critical path: B - F - G - H, with length $12+6+14+22 = 54$.

Minimum project duration = 54 weeks.

This is a maximisation problem, so first convert to an opportunity-loss matrix by subtracting every entry from the largest entry, 115.

Row reduction (subtract row minima 5, 5, 10, 0):

Column reduction (column minima 0, 10, 0, 0):

The minimum number of lines covering all zeros is 4 (columns Honda, Hero, Bajaj, Yamaha), which equals $n=4$, so an optimal assignment exists.

Assignment (start with rows that have a single zero): A has only Bajaj; C then takes Yamaha; D has only Honda; B takes Hero.

Maximum revenue = 110 + 100 + 105 + 115 = Rs 430 thousand (Rs 4,30,000).

Cost price Rs 60, selling price Rs 70, so profit is Rs 10 per litre sold and loss is Rs 60 per litre unsold (no scrap value). For stock $s$ and demand $d$:

$\text{Payoff} = 70\min(s,d) - 60s$

Payoff table (Rs)

EMV calculations

• Stock 11: $110$
• Stock 12: $0.10(50)+0.90(120) = 5+108 = 113$
• Stock 13: $0.10(-10)+0.15(60)+0.75(130) = -1+9+97.5 = 105.5$
• Stock 14: $0.10(-70)+0.15(0)+0.30(70)+0.45(140) = -7+0+21+63 = 77$
• Stock 15: $0.10(-130)+0.15(-60)+0.30(10)+0.25(80)+0.20(150) = -13-9+3+20+30 = 31$

Optimal stock = 12 litres, with the maximum EMV of Rs 113.

(a) Scope of operations research

Operations research (OR) applies scientific and mathematical methods (modelling, optimisation, simulation) to find the best decision for a complex system. Its scope covers:

• Industry and production: product mix, production scheduling, inventory control and plant location.
• Marketing: media selection, pricing, sales-force allocation and market-share competition (game theory).
• Finance and accounting: portfolio selection, budgeting, credit policy and break-even analysis.
• Personnel and HR: manpower planning, recruitment and job assignment.
• Transport and logistics: routing, transportation costs and fleet scheduling.
• Services: queue management in banks, hospitals and airports.
• Project management: planning and control with PERT/CPM.
• Government, defence and agriculture: resource allocation, crop planning and public-service planning.

(b) Dominance rule method in game theory

The dominance rule reduces the size of a payoff matrix before solving a game without a saddle point. Dominated strategies are never chosen by a rational player, so they can be deleted.

• Rows (maximiser A): row $i$ dominates row $k$ if every entry of row $i$ is $\ge$ the corresponding entry of row $k$. Delete the dominated row $k$.
• Columns (minimiser B): column $j$ dominates column $l$ if every entry of column $j$ is $\le$ the corresponding entry of column $l$. Delete the dominated column $l$.
• A strategy may also be dominated by a convex combination (average) of other strategies.
• Repeat until no more rows or columns can be deleted. The reduced matrix, often $2\times 2$, is then solved by the arithmetic, algebraic or graphical method. Deleted strategies get probability zero.

This is an M/M/1 queue (single server, Poisson arrivals, exponential service).

Arrival rate: $\lambda = \dfrac{96}{24} = 4$ patients per hour. Service rate: $\mu = \dfrac{60}{10} = 6$ patients per hour. Utilisation: $\rho = \lambda/\mu = 4/6 = 0.667 < 1$, so the queue is stable.

Expected queue length (patients waiting, excluding the one being served):

$L_q = \frac{\lambda^2}{\mu(\mu-\lambda)} = \frac{16}{6\times 2} = 1.33 \text{ patients}$

Expected waiting time before service:

$W_q = \frac{L_q}{\lambda} = \frac{1.33}{4} = 0.333 \text{ hour} = 20 \text{ minutes}$

(For reference, $L_s = 2$ patients in the system and $W_s = 30$ minutes.)

Rows are A's strategies, columns are B's strategies.

Maximin (A) $= \max(40, 20, 10) = 40$. Minimax (B) $= \min(40, 40, 90, 50) = 40$.

Maximin equals minimax, so the game has a saddle point and is solved in pure strategies.

• Optimal strategy for A: play A1.
• Optimal strategy for B: play B1 (B2 is equally good, since both have column maximum 40).
• Value of the game: $V = 40$ in favour of A.

Decision variables: let $x_1, x_2, x_3$ be the number of units of foods F1, F2, F3 bought.

Objective function (minimise total cost):

$\text{Minimise } Z = 20x_1 + 24x_2 + 18x_3$

Subject to the vitamin requirements:

$20x_1 + 10x_2 + 10x_3 \ge 300 \quad (\text{vitamin } V_1)$ $10x_1 + 10x_2 + 10x_3 \ge 200 \quad (\text{vitamin } V_2)$ $10x_1 + 20x_2 + 10x_3 \ge 240 \quad (\text{vitamin } V_3)$

Non-negativity: $x_1, x_2, x_3 \ge 0$.

The MODI (modified distribution, or $u$-$v$) method tests whether a basic feasible solution of a transportation problem is optimal, and improves it if not.

Steps:

1. Obtain an initial basic feasible solution (NWCR, least cost or VAM) with exactly $m+n-1$ occupied cells. If fewer, add a zero allocation (degeneracy).
2. Assign a row number $u_i$ to each row and a column number $v_j$ to each column. Put one of them (usually $u_1$) equal to 0, then solve $u_i + v_j = c_{ij}$ for every occupied cell.
3. For every unoccupied cell compute the opportunity cost (cell evaluation)

$d_{ij} = c_{ij} - (u_i + v_j)$

4. Optimality test (minimisation): if all $d_{ij} \ge 0$ the solution is optimal. If some $d_{ij} < 0$, it is not optimal, and a zero $d_{ij}$ indicates an alternative optimum.
5. Improvement: choose the cell with the most negative $d_{ij}$ as the entering cell. Draw a closed loop through it using occupied cells (horizontal and vertical moves only) and mark the corners alternately $+$, $-$.
6. The smallest allocation on the $-$ corners is shifted: add it at $+$ corners, subtract it at $-$ corners. One occupied cell becomes empty.
7. Recompute $u$, $v$ and $d_{ij}$ and repeat until all $d_{ij} \ge 0$.

Unbalanced problems are first balanced with a dummy row or column of zero cost.

The network is drawn in activity-on-arrow form. Each activity is an arrow between two event nodes, and dummy activities (dotted arrows, zero duration) keep the precedence relations correct.

Precedence logic

• P and Q have no predecessor, so both start at the start node 1.
• R needs both P and Q, so dummies join the end of P (node 2) and the end of Q (node 3) into node 4, where R starts.
• T needs only P, so T starts at node 2.
• S needs only Q, so S starts at node 3.
• V needs T and U, so T ends at node 7 and a dummy joins the end of U (node 6) to node 7. V starts at node 7.
• W needs S and U, so S ends at node 8 and a dummy joins node 6 to node 8. W starts at node 8.
• X needs V and W, so both end at node 9, where X starts. X ends at the finish node 10.

Arrows of the network

Read from the table: start node 1 splits into P and Q; the dummies merge them at node 4 for R; U ends at node 6, which feeds both V and W through dummies; V and W meet at node 9 before X.

Expected times and variances

$t_e = \dfrac{o + 4m + p}{6}$, $\sigma^2 = \left(\dfrac{p-o}{6}\right)^2$

(a) PERT network (events 1 to 7, no dummy needed)

Event 4 is where B and D end (F and G start). Event 6 is where C and F end (H starts). Event 7 is the finish.

(b) Critical activities

Earliest event times: $E_1 = 0$, $E_2 = 4$, $E_4 = \max(6, 4+5) = 9$, $E_5 = 4+15 = 19$, $E_6 = \max(13, 9+10) = 19$, $E_7 = \max(9+6,\ 19+16,\ 19+10) = 35$.

Critical activities (zero slack): A, D, F, H, so the critical path is $A \to D \to F \to H$.

(c) Project completion time and variance

$T_E = 4 + 5 + 10 + 16 = 35 \text{ weeks}$

$\sigma^2 = \frac49 + 1 + \frac49 + 9 = \frac{98}{9} \approx 10.89$

so $\sigma \approx 3.30$ weeks.

Profit per unit sold (marginal profit) $MP = 70 - 60 = \text{Rs } 10$. Loss per unsold unit (marginal loss) $ML = \text{Rs } 60$.

Conditional profit for stock $Q$ and demand $D$ is $70\min(Q,D) - 60Q$.

(a) Quantity maximising EMV

Marginal analysis: stock the $Q$th litre if $P(D \ge Q) \ge \dfrac{ML}{MP+ML} = \dfrac{60}{70} = 0.857$.

Check by expected monetary value:

For example, $Q = 12$: profit is Rs 120 if $D \ge 12$ (probability 0.9) and Rs 50 if $D = 11$ (probability 0.1). So $\text{EMV} = 0.9(120) + 0.1(50) = 113$.

Optimal stock = 12 litres, maximum EMV = Rs 113.

(c) EPPI (the best action for each demand is to stock exactly $D$, earning $10D$):

$\text{EPPI} = 10(11\times0.10 + 12\times0.15 + 13\times0.30 + 14\times0.25 + 15\times0.20) = 10\times 13.3 = \text{Rs } 133$

(b) Minimum EOL

$\text{EVPI} = \text{EPPI} - \text{EMV}_{max} = 133 - 113 = \text{Rs } 20$

and the minimum expected opportunity loss equals EVPI, so min EOL = Rs 20 (at $Q = 12$).

Check: opportunity losses at $Q = 12$ are Rs 60 for $D = 11$, 0 for $D = 12$, 10 for $D = 13$, 20 for $D = 14$ and 30 for $D = 15$. So $\text{EOL} = 60(0.10) + 0 + 10(0.30) + 20(0.25) + 30(0.20) = 6 + 3 + 5 + 6 = 20$.