Operational Research

Operational Research (OR) is the scientific, mathematical approach to decision making that applies analytical methods (modelling, optimisation, statistics, simulation) to help management find the best, or an optimal, solution for complex problems involving the allocation and use of limited resources such as men, machines, money and materials. Examples are transportation, assignment, inventory, queueing and replacement problems.

General methods for solving OR models

1. Analytical (deductive) methods: The model is solved mathematically to get an exact optimal solution, e.g. calculus-based EOQ formula, linear programming (graphical, simplex), transportation and assignment algorithms.
2. Numerical (iterative) methods: Start with a trial solution and improve it step by step according to rules until no further improvement is possible, e.g. simplex method, Hungarian method. Used when analytic solution is not available.
3. Monte Carlo (simulation) method: The system is imitated using random numbers and probability distributions to estimate its behaviour when mathematical solution is too complex or analytical solution is impossible, e.g. queueing and inventory simulations.
4. Heuristic methods: Rule-of-thumb or approximate procedures that give good, not necessarily optimal, solutions for very large problems.

The OR approach follows the steps: define the problem, construct the model, solve it, test and validate the solution, then implement and control it.

The Hungarian algorithm solves the assignment problem (assign $n$ jobs to $n$ workers, one each, with minimum total cost).

Steps

1. Balance the problem: if the number of rows and columns differ, add a dummy row or column of zero costs. For maximisation, subtract every entry from the largest entry (or multiply by $-1$) to convert to minimisation.
2. Row reduction: subtract the smallest element of each row from all the elements of that row.
3. Column reduction: subtract the smallest element of each column from all the elements of that column.
4. Cover zeros: draw the minimum number of horizontal and vertical lines to cover all zeros.
5. Test for optimality: if the number of lines equals $n$, an optimal assignment is possible; go to step 7.
6. If the number of lines is less than $n$: find the smallest uncovered element, subtract it from all uncovered elements, add it to the elements at the intersection of two lines, and leave other covered elements unchanged. Return to step 4.
7. Make assignments: start with a row or column having exactly one zero, assign that zero and cross out the other zeros in its row and column. Repeat until all assignments are made.
8. Compute total cost from the original cost matrix using the assigned cells.

Primal: Minimise $z=4x_1+2x_2+3x_3$

subject to $2x_1+4x_3\ge5$, $\ 2x_1+3x_2+x_3\ge4$, $\ x_1,x_2,x_3\ge0$.

Dual (one variable $y_1,y_2$ per constraint; one constraint per primal variable):

Maximise $w=5y_1+4y_2$

$2y_1+2y_2\le4$

$3y_2\le2$

$4y_1+y_2\le3$

$y_1,y_2\ge0$

Solving the dual graphically

Simplified constraints: $y_1+y_2\le2$, $y_2\le\tfrac23$, $4y_1+y_2\le3$. Corner points of the feasible region:

The maximum is $w=\tfrac{67}{12}$ at $y_1=\tfrac7{12},\ y_2=\tfrac23$. The constraint $2y_1+2y_2=2.5<4$ is not binding, so $x_1=0$ (complementary slackness).

Primal solution

Since $y_1,y_2>0$, both primal constraints hold as equalities with $x_1=0$:

$4x_3=5\Rightarrow x_3=\tfrac54$

$3x_2+x_3=4\Rightarrow x_2=\tfrac{11}{12}$

Check: $z=2\left(\tfrac{11}{12}\right)+3\left(\tfrac54\right)=\tfrac{11}{6}+\tfrac{15}{4}=\tfrac{67}{12}$, equal to the dual optimum.

Optimal solution: $x_1=0,\ x_2=\tfrac{11}{12},\ x_3=\tfrac54$, minimum $z=\tfrac{67}{12}\approx5.58$.

Primal (minimisation):

$\text{Min } z = 20x_1 + 40x_2$

subject to $3x_1 + 6x_2 \ge 600,\; 5x_1 + 12x_2 \ge 36,\; 20x_1 + 10x_2 \ge 100,\; x_1,x_2 \ge 0$.

Step 1: Formulate the dual. Let $y_1, y_2, y_3$ be dual variables for the three constraints.

$\text{Max } w = 600y_1 + 36y_2 + 100y_3$

subject to

$3y_1 + 5y_2 + 20y_3 \le 20$

$6y_1 + 12y_2 + 10y_3 \le 40$

$y_1, y_2, y_3 \ge 0$

Step 2: Solve the dual by simplex. Add slack variables $s_1, s_2$.

$y_1$ enters. The ratios are $20/3$ and $40/6$, equal (a tie), so take $s_1$ as leaving. Divide row 1 by 3.

All $Z_j - C_j \ge 0$, so this is optimal: $y_1 = 20/3,\; y_2 = y_3 = 0,\; w_{max} = 4000$.

Step 3: Read the primal solution from the $Z_j - C_j$ row under the slack columns: $x_1 = 200$ (under $s_1$) and $x_2 = 0$ (under $s_2$).

Check: $3(200) = 600 \ge 600$, $5(200) = 1000 \ge 36$, $20(200) = 4000 \ge 100$, and $z = 20(200) = 4000$, which equals $w$.

$x_1 = 200,\; x_2 = 0,\; z_{min} = \text{Rs } 4000$

(Since $z = 20(x_1 + 2x_2)$, any point on $x_1 + 2x_2 = 200$ also gives 4000, so alternative optima exist.)

Queueing models are classified using Kendall's notation $(a/b/c):(d/e)$, where $a$ is the arrival distribution, $b$ the service-time distribution, $c$ the number of servers, $d$ the queue discipline and $e$ the system capacity (calling source). $M$ stands for Markovian (Poisson arrivals, exponential service), $D$ for deterministic and $G$ for general.

Classification

1. By the number of servers
   • Single channel $(M/M/1)$: one server, e.g. a single-counter ticket booth.
   • Multi-channel $(M/M/c)$: several parallel servers, e.g. a bank with many tellers.
2. By the capacity of the system
   • Infinite capacity $(M/M/1):(\infty/FCFS)$.
   • Finite capacity $(M/M/1):(N/FCFS)$, e.g. a clinic waiting room with a limited number of chairs.
3. By the queue discipline: FCFS (first come first served), LIFO, SIRO (service in random order), priority discipline (emergency patients first).
4. By the distribution of arrivals and service: $(M/M/1)$, $(M/D/1)$ (constant service time, e.g. an automatic car wash), $(M/G/1)$.
5. By the stages of service: single-phase (one service point) and multi-phase or series queues (e.g. registration, then doctor, then pharmacy).
6. By the source population: infinite or finite calling population (machines in a factory needing repair).

(a) EOQ (Economic Order Quantity)

EOQ is the order size that minimises the total yearly inventory cost, the sum of ordering cost and holding (carrying) cost, under constant demand and instantaneous replenishment with no shortages.

$\text{Total cost}=\frac{D}{Q}C_o+\frac{Q}{2}C_h$

Minimising with respect to $Q$ gives

$Q^*=\sqrt{\frac{2DC_o}{C_h}}$

where $D$ is annual demand, $C_o$ the ordering cost per order and $C_h$ the holding cost per unit per year. At EOQ, ordering cost equals holding cost. Example: $D=1000$, $C_o=\text{Rs }100$, $C_h=\text{Rs }5$ gives $Q^*=\sqrt{40000}=200$ units. Number of orders per year $=D/Q^*=5$.

(b) Kendall's notation

Queueing models are written as $(a/b/c):(d/e)$ where $a$ is the arrival (inter-arrival) distribution, $b$ the service-time distribution, $c$ the number of servers, $d$ the queue discipline (FCFS, LIFO, SIRO, priority) and $e$ the maximum number allowed in the system. Symbols: $M$ = Markovian (Poisson arrivals or exponential service), $D$ = deterministic, $G$ = general. Example: $(M/M/1):(\infty/FCFS)$ is a single server with Poisson arrivals, exponential service, infinite capacity and first-come-first-served discipline.

(c) Duality theorem

Every linear programming problem (primal) has a related dual problem. The duality theorem states that if either the primal or the dual has a finite optimal solution, then the other also has one, and the optimal values of the objective functions are equal: $\text{Max } Z_{\text{primal}}=\text{Min } W_{\text{dual}}$. If one is unbounded, the other is infeasible. Complementary slackness also holds between them. Duality is useful because the dual may be easier to solve (fewer constraints) and its variables give shadow prices.

Inventory costs

1. Purchase (unit) cost: price paid per unit, or production cost if made in-house; it may include quantity discounts.
2. Ordering (set-up) cost: cost incurred each time an order is placed or production is set up, e.g. clerical work, transport, inspection, set-up. It is fixed per order, so total ordering cost falls with larger order size.
3. Holding (carrying) cost: cost of keeping stock: storage space, insurance, taxes, obsolescence, deterioration, pilferage and interest on the capital tied up. It rises with the quantity stored, usually expressed as a percentage of inventory value per year.
4. Shortage (stock-out) cost: cost of not having an item when demanded: lost sales, loss of goodwill, penalty, idle production, back-order handling.

The aim of inventory control is to minimise the total of these costs.

ABC analysis

ABC analysis classifies items by the annual consumption value (annual usage $\times$ unit cost) so that control effort is focused where value is highest (Pareto principle).

Example: 10 items with annual consumption value (Rs): P 50,000; Q 20,000; R 10,000; S 6,000; T 4,000; U 3,000; V 2,500; W 2,000; X 1,500; Y 1,000. Total $=\text{Rs }100,000$.

• Item P (10% of items) accounts for 50% of value; P and Q (20% of items) account for 70% of value, so they are class A.
• R, S (cumulative 86%) are class B.
• T, U, V, W, X, Y (the remaining 60% of items with 14% of value) are class C.

Class A items thus receive the closest management attention.

Let $x$ = number of chairs of type A and $y$ = number of type B per week.

LPP

Maximise $Z=500x+300y$

$6x+8y\le120$

$3x+5y\le100$

$12x+4y\le144$

$x,y\ge0$

Corner points of the feasible region

• $O(0,0)$: $Z=0$
• $A(12,0)$ from machine Z ($12x=144$): $Z=6000$ (check X: $72\le120$, Y: $36\le100$)
• $B$: intersection of $6x+8y=120$ and $12x+4y=144$. From the second, $y=36-3x$; substituting, $6x+288-24x=120\Rightarrow x=\tfrac{28}{3}=9.33$, $y=8$. Check machine Y: $3(9.33)+5(8)=68\le100$. $Z=500(9.33)+300(8)=4666.67+2400=7066.67$
• $C(0,15)$ from machine X ($8y=120$): Y: $75\le100$, Z: $60\le144$. $Z=4500$

The maximum is at $B$.

Result: produce about $9.33$ chairs of type A and $8$ of type B per week, giving a maximum profit of Rs 7,066.67. (If whole chairs are required: 9 of A and 8 of B gives Rs 6,900, which is the best feasible integer combination.)

Algorithm to solve a minimisation LPP by the simplex method

1. Standard form: Convert the problem so all constraints are equations with non-negative right-hand sides. Add slack variables for $\le$ constraints. For $\ge$ constraints subtract surplus variables and add artificial variables. For equality constraints add artificial variables.
2. Handle artificial variables: Use the Big-M method (assign cost $+M$ to artificial variables in the objective of a minimisation problem) or the two-phase method.
3. Initial table: Take the slack/artificial variables as the basic variables to form the initial basic feasible solution. Compute $Z_j$ and the net evaluation row $\Delta_j=C_j-Z_j$ (or $Z_j-C_j$).
4. Optimality test: For a minimisation problem the solution is optimal if all $\Delta_j=C_j-Z_j\ge0$ (equivalently all $Z_j-C_j\le0$). If so, stop. If any artificial variable stays in the basis at positive level, the problem is infeasible.
5. Entering variable: Choose the non-basic variable with the most negative $C_j-Z_j$; its column is the key column.
6. Leaving variable: Compute the ratio $\dfrac{\text{RHS}}{\text{key column element}}$ for positive key column entries; the row with the minimum ratio is the key row (leaving variable). If no positive element exists, the solution is unbounded. The intersection is the pivot element.
7. Iterate: Divide the key row by the pivot element, then make the other elements of the key column zero by row operations. Update $Z_j$ and $C_j-Z_j$.
8. Repeat steps 4 to 7 until the optimality condition is met. The values of the basic variables (RHS) and the objective value $Z$ give the optimal solution.

(A maximisation problem can be converted into minimisation by $\text{Min } Z'=-\text{Max } Z$.)

The problem involves 200 street lamps, with the cost of replacing a bulb individually taken as Rs 2 and the cost per bulb under group replacement as Rs 0.50. The probability of failure at the end of each week is found from the cumulative probabilities (0, 0.1, 0.3, 0.5, 0.7, 1.0).

Expected life of a bulb $=\sum i\,p_i=0.1+0.4+0.6+0.8+1.5=3.4$ weeks.

Policy 1: individual replacement

Bulbs replaced per week $=\dfrac{200}{3.4}=58.8$

$\text{Cost per week}=58.8\times2=\text{Rs }117.65$

Policy 2: group replacement

Expected number of failures (replacements) at the end of week $n$ with $N_0=200$:

$N_n=200\,p_n+\sum_{i=1}^{n-1}N_i\,p_{n-i}$

• $N_1=200(0.1)=20$
• $N_2=200(0.2)+20(0.1)=42$
• $N_3=200(0.2)+20(0.2)+42(0.1)=48.2$
• $N_4=200(0.2)+20(0.2)+42(0.2)+48.2(0.1)=57.22$

Group replacement of all lamps at the end of week $t$ costs $200\times0.50=\text{Rs }100$ plus individual replacements of failures before week $t$.

The cost is lowest at $t=2$.

Conclusion: Group replacement every 2 weeks costs Rs 70 per week, which is cheaper than individual replacement (Rs 117.65 per week), so group replacement every 2 weeks is the optimal policy.

Single channel queueing model $(M/M/1):(\infty/FCFS)$

A system with one server where customers arrive according to a Poisson process with mean arrival rate $\lambda$, service times are exponential with mean service rate $\mu$, queue capacity and calling population are infinite, and customers are served first come first served. Traffic intensity $\rho=\lambda/\mu<1$ is required for a steady state.

Assumptions

• Arrivals follow a Poisson distribution with rate $\lambda$ (inter-arrival times exponential).
• Service times follow an exponential distribution with rate $\mu$.
• There is a single server.
• Queue discipline is FCFS.
• Infinite waiting space and infinite calling population.
• No balking, reneging or jockeying; arrivals are independent of each other.
• System is in steady state ($\lambda<\mu$).

Results

$P_n=(1-\rho)\rho^n,\quad L_s=\frac{\lambda}{\mu-\lambda},\quad L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}$

$W_s=\frac{1}{\mu-\lambda},\quad W_q=\frac{\lambda}{\mu(\mu-\lambda)}$

Example: Patients arrive at a clinic with one doctor at $\lambda=6$ per hour; the doctor serves $\mu=10$ per hour. Then $\rho=0.6$, $L_s=6/4=1.5$ patients in the system, $L_q=36/40=0.9$ in the queue, $W_s=1/4$ hour (15 minutes) and $W_q=6/40=0.15$ hour (9 minutes). The doctor is idle $1-\rho=40\%$ of the time.

(a) Kendall's notation

Kendall's notation describes a queueing system in the form $(a/b/c):(d/e/f)$, or $A/S/c/K/N/D$:

• A: arrival (inter-arrival time) distribution, e.g. M (Markovian, Poisson arrivals), D (deterministic), G (general).
• S: service time distribution, e.g. M (exponential), D, $E_k$ (Erlang), G.
• c: number of parallel servers.
• K: system capacity (maximum customers allowed), default $\infty$.
• N: size of the calling population, default $\infty$.
• D: queue discipline, e.g. FCFS, LCFS, SIRO, priority; default FCFS.

Example: $M/M/1/\infty/\infty/FCFS$ is a single-server queue with Poisson arrivals, exponential service, infinite capacity and population, served first come first served. It is usually shortened to $M/M/1$.

(b) Big M method

The Big M (penalty) method solves LP problems whose constraints are of the $\ge$ or $=$ type, where no obvious initial basic feasible solution exists.

1. Convert the problem to standard form. Subtract a surplus variable from each $\ge$ constraint and add a slack variable to each $\le$ constraint.
2. Add an artificial variable $A_i$ to each $\ge$ and $=$ constraint so that an identity basis is available.
3. Give each artificial variable a very large penalty $M$ in the objective: $-M$ for maximisation and $+M$ for minimisation. This forces the artificial variables out of the solution.
4. Start the simplex iterations from the artificial basis. Compute $Z_j - C_j$ with $M$ treated as a large number and remove artificial variables as they leave the basis.
5. At optimality, if an artificial variable is still in the basis at a positive level, the problem is infeasible. Otherwise the solution is optimal.

(c) Importance and advantage of duality

Every LP problem (primal) has an associated dual problem, and both have the same optimal objective value.

• Solving the dual can be easier when the primal has many constraints and few variables, because the simplex tableau has fewer rows.
• The optimal values of the dual variables are shadow prices. They measure how much the objective changes per unit change in a resource.
• It gives economic interpretation and helps in sensitivity analysis.
• It allows checking the correctness of an optimal solution (complementary slackness).
• It supports the dual simplex method, used when a solution is optimal but infeasible, such as after adding a new constraint.

Operations research (OR) applies scientific methods to decision problems. Its tools and techniques are of two kinds.

1. Tools (what OR uses)

• Mathematical models: equations and inequalities that represent the real system.
• Statistics and probability: for forecasting, sampling and describing uncertainty.
• Computers and software: such as Excel Solver, LINDO and TORA, to solve large models.
• Economic and management theory: for cost, profit and organisational analysis.

2. Techniques (methods of solving problems)

• Linear programming (simplex, graphical): optimum use of limited resources to maximise profit or minimise cost.
• Transportation and assignment models: minimum cost distribution of goods, and allocation of jobs to workers.
• Queueing theory: analysis of waiting lines to balance waiting cost and service cost.
• Inventory control (EOQ, ABC): decides when and how much to order.
• Game theory: decision making in competitive situations.
• Network analysis (PERT/CPM): planning, scheduling and controlling projects.
• Simulation: experiments on a model of a system that is too complex for analytical solution.
• Decision theory, dynamic programming, replacement and sequencing models: other techniques for sequential and risky decisions.

ABC inventory planning system

ABC analysis classifies inventory items by their annual consumption value (annual usage $\times$ unit cost) so that control effort is spent where it matters most.

• A items: about 10-20% of items but 60-70% of the total value. Tight control, frequent review, accurate records and small safety stocks.
• B items: about 20-30% of items and about 20-30% of the value. Moderate control.
• C items: about 50-60% of items but only 5-10% of the value. Simple control, bulk ordering and larger safety stocks.

EOQ

$D = 18000$, $C_o = 250$, $P = 25$, $C_h = 25\% \times 25 = \text{Rs } 6.25$ per unit per year.

$EOQ = \sqrt{\frac{2DC_o}{C_h}} = \sqrt{\frac{2 \times 18000 \times 250}{6.25}} = \sqrt{1{,}440{,}000} = 1200 \text{ units}$

Total annual cost at EOQ (1200)

• Purchase cost: $18000 \times 25 = \text{Rs } 450{,}000$
• Ordering cost: $(18000/1200) \times 250 = 15 \times 250 = \text{Rs } 3{,}750$
• Carrying cost: $(1200/2) \times 6.25 = \text{Rs } 3{,}750$
• Total $= \text{Rs } 457{,}500$

With the discount (Q = 3000)

New price $= 25 \times 0.95 = \text{Rs } 23.75$. Carrying cost per unit $= 25\% \times 23.75 = \text{Rs } 5.9375$.

• Purchase cost: $18000 \times 23.75 = \text{Rs } 427{,}500$
• Ordering cost: $(18000/3000) \times 250 = 6 \times 250 = \text{Rs } 1{,}500$
• Carrying cost: $(3000/2) \times 5.9375 = \text{Rs } 8{,}906.25$
• Total $= \text{Rs } 437{,}906.25$

Decision: The discount offer lowers the total cost from Rs 457,500 to Rs 437,906.25, a saving of Rs 19,593.75 per year. So accept the discount offer and order 3000 units each time.

This is an M/M/1 queue with arrival rate $\lambda = 5$ per hour and service rate $\mu = 60/10 = 6$ per hour. The traffic intensity is $\rho = \lambda/\mu = 5/6$.

(a) Proportion of time the shop is empty

$P_0 = 1 - \rho = 1 - \frac{5}{6} = \frac{1}{6} \approx 0.167 \;(16.7\%)$

(b) Average number of customers

In the system:

$L_s = \frac{\lambda}{\mu - \lambda} = \frac{5}{6-5} = 5 \text{ customers}$

In the queue:

$L_q = \frac{\lambda^2}{\mu(\mu-\lambda)} = \frac{25}{6 \times 1} = 4.17 \text{ customers}$

(c) Average time spent

In the queue:

$W_q = \frac{L_q}{\lambda} = \frac{25/6}{5} = \frac{5}{6} \text{ hour} = 50 \text{ minutes}$

In the system (queue plus service):

$W_s = \frac{1}{\mu - \lambda} = 1 \text{ hour} = 60 \text{ minutes}$

(d) Probability of at least five customers

$P(n \ge 5) = \rho^5 = \left(\frac{5}{6}\right)^5 = \frac{3125}{7776} \approx 0.402$

Meaning of duality

Every linear programming problem (the primal) has a companion LP problem called its dual. If the primal is a maximisation problem the dual is a minimisation problem, and vice versa. The variables of the dual correspond to the constraints of the primal, and the constraints of the dual correspond to the variables of the primal. By the duality theorem, if both have optimal solutions, their optimal objective values are equal.

Steps of formulating the dual

1. Write the primal in standard form: for Max, all constraints are $\le$; for Min, all constraints are $\ge$ (multiply by $-1$ where needed; replace an equality by two inequalities).
2. Introduce one dual variable $y_i$ for each primal constraint.
3. Swap the objective: Max becomes Min and Min becomes Max. The RHS constants of the primal become the objective coefficients of the dual.
4. The objective coefficients of the primal become the RHS constants of the dual.
5. Take the transpose of the coefficient matrix: each primal variable gives one dual constraint, with the inequality reversed ($\le$ becomes $\ge$ for Max to Min).
6. All dual variables are $\ge 0$ for inequality constraints. An equality constraint gives a free (unrestricted) dual variable.

Example

Primal:

$\text{Max } z = 3x_1 + 5x_2$

subject to $x_1 \le 4,\; 2x_2 \le 12,\; 3x_1 + 2x_2 \le 18,\; x_1, x_2 \ge 0$.

Dual:

$\text{Min } w = 4y_1 + 12y_2 + 18y_3$

subject to

$y_1 + 3y_3 \ge 3$

$2y_2 + 2y_3 \ge 5$

$y_1, y_2, y_3 \ge 0$

Solving gives the primal optimum $x_1 = 2,\; x_2 = 6,\; z = 36$, and the dual optimum $y_1 = 0,\; y_2 = 3/2,\; y_3 = 1,\; w = 18 + 18 = 36$. The optimal values are equal, which verifies the duality theorem.

(a) Degeneracy in a transportation problem

A basic feasible solution of an $m \times n$ transportation problem must have exactly $m + n - 1$ occupied (allocated) cells, all independent. If the number of allocated cells is less than $m + n - 1$, the solution is degenerate. This happens when a row and a column are exhausted at the same time during the initial allocation (e.g. in the North-West Corner or VAM method), or when an allocation becomes zero during the MODI improvement.

To resolve it, place a very small quantity $\varepsilon$ ($\varepsilon \to 0$) in one or more unoccupied cells, chosen so that the cells remain independent (no closed loop). The $\varepsilon$ cells are treated as occupied, the MODI test is applied, and $\varepsilon$ is set to zero in the final answer.

(b) Queueing theory

Queueing theory is the mathematical study of waiting lines. Customers arrive at a service facility, wait if the server is busy, are served and leave. Its aim is to find the balance between the cost of providing service (more servers) and the cost of waiting (lost customers and time).

Its main elements are:

• the input (arrival) process, usually Poisson;
• the service mechanism, usually exponential;
• the number of servers;
• the queue discipline (FCFS, LIFO and so on);
• the system capacity.

The measures of performance include the average number in the system ($L_s$) and in the queue ($L_q$), the average waiting time ($W_s$, $W_q$) and the server utilisation $\rho = \lambda/\mu$. For the M/M/1 model, $L_s = \lambda/(\mu - \lambda)$. Examples are banks, hospitals, ticket counters and repair shops.

(c) Assignment problem algorithm (Hungarian method)

1. Balance the matrix. If it is not square, add dummy rows or columns with zero cost. For maximisation, convert to a cost matrix by subtracting every entry from the largest entry.
2. Row reduction: subtract the smallest element of each row from all elements of that row.
3. Column reduction: subtract the smallest element of each column from all elements of that column.
4. Cover all zeros with the minimum number of horizontal and vertical lines.
5. If the number of lines equals $n$ (the order of the matrix), an optimal assignment exists. Go to step 7.
6. If the number of lines is less than $n$, find the smallest uncovered element. Subtract it from all uncovered elements and add it to elements at line intersections. Return to step 4.
7. Make the assignments, starting with rows or columns having a single zero, and cross out the other zeros in that row and column. The total cost is the sum of the original costs of the assigned cells.

Meaning of game theory

Game theory is a mathematical tool for decision making in competitive situations where two or more rational opponents (players) have conflicting interests, and the outcome for each depends on the choices made by all. Each player chooses a strategy to maximise their own gain (or minimise their loss). It was developed by John von Neumann and Oskar Morgenstern.

Assumptions

1. There is a finite number of players (competitors), and each has a finite number of possible strategies.
2. Each player knows all the strategies available to themselves and their opponent, and the resulting payoffs.
3. Players are rational and act in their own best interest, assuming the opponent is also intelligent.
4. Players choose their strategies simultaneously and independently, without knowing the opponent's choice.
5. The payoff of one player is the loss of the other (zero-sum game) in the basic model, so the gains and losses sum to zero.
6. The game is repeated, and each player's objective is to maximise the minimum gain (maximin) or minimise the maximum loss (minimax).

Importance to business decisions

• It helps firms choose strategies in competitive markets, such as pricing, advertising, product launches and market share battles.
• It supports bargaining and negotiation, for example with labour unions and suppliers.
• It models oligopoly, where firms must anticipate competitors' reactions (price wars, collusion).
• It helps in bidding and tendering decisions.
• It gives a systematic way to analyse risk by considering the worst case and the best response of the rival.
• It forces managers to look at problems from the competitor's viewpoint, which leads to better, more consistent decisions.

Its limitation is that real players do not always have full information or behave rationally, and complex games are hard to solve.

$\text{Max } z = 5x_1 + 3x_2$

subject to $2x_1 + x_2 \le 5,\; x_1 + x_2 \le 4,\; x_1, x_2 \ge 0$.

Standard form: add slack variables $s_1, s_2$.

$2x_1 + x_2 + s_1 = 5,\qquad x_1 + x_2 + s_2 = 4$

Initial table

$x_1$ enters (most negative) and $s_1$ leaves.

Iteration 1

$x_2$ enters and $s_2$ leaves.

Iteration 2

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

$x_1 = 1,\quad x_2 = 3,\quad z_{max} = 5(1) + 3(3) = 14$

Check: $2(1) + 3 = 5 \le 5$ and $1 + 3 = 4 \le 4$.

Operational research (OR)

Operational research is the application of scientific methods, mainly mathematical and statistical models, to problems of managing and operating organisations, in order to give decision makers an optimal or near-optimal solution. It treats the organisation as a system and usually uses a team of experts from different fields.

General method of solving an OR problem (phases)

1. Formulating the problem: state the objective, the decision variables, the constraints and the alternative courses of action.
2. Constructing a mathematical model: express the objective function and constraints as equations or inequalities, for example in LP form.
3. Deriving the solution from the model: solve the model with a suitable technique (simplex, MODI, Hungarian, EOQ formula, simulation).
4. Testing the model and its solution: check whether the model predicts the real system correctly, using past data, and carry out sensitivity analysis.
5. Establishing control over the solution: identify the parameters that make the solution sensitive, and update the solution when these change.
6. Implementing the solution: put the results into practice with the cooperation of management and monitor the results.

Limitations

• Models are only an approximation of reality, and it is hard to include all factors.
• Quantifying all variables, especially human and qualitative factors, is difficult.
• Solving large, complex models needs expensive computers, data and trained experts.
• Collecting accurate data is time-consuming and costly.
• Managers may resist OR solutions that change existing practice.
• OR gives support to decisions, not the decision itself, and results can become outdated when conditions change.

Formulation

Let $x_1$ and $x_2$ be the kg of factor 1 and factor 2 used.

$\text{Min } Z = 25x_1 + 10x_2$

subject to

$x_1 + x_2 = 100,\qquad x_1 \ge 50,\qquad x_2 \le 60,\qquad x_1, x_2 \ge 0$

Standard form (Big M): subtract a surplus variable $s_1$, add a slack variable $s_2$, and add artificial variables $A_1, A_2$.

$x_1 + x_2 + A_1 = 100,\quad x_1 - s_1 + A_2 = 50,\quad x_2 + s_2 = 60$

$\text{Min } Z = 25x_1 + 10x_2 + MA_1 + MA_2$

Table 1. For a minimisation, the entering variable has the most negative $C_j - Z_j$.

$x_1$ enters and $A_2$ leaves.

Table 2

$x_2$ enters and $A_1$ leaves.

Table 3

All $C_j - Z_j \ge 0$, so this is optimal.

$x_1 = 50 \text{ kg},\quad x_2 = 50 \text{ kg},\quad Z_{min} = 25(50) + 10(50) = \text{Rs } 1750$

Queueing process

A queueing process describes how customers arrive at a service facility, wait in a line if the servers are busy, receive service and then leave the system. Its components are:

1. Input (arrival) process: customers arrive according to some distribution, usually Poisson with rate $\lambda$.
2. Queue: the waiting line, with its capacity and the queue discipline (FCFS, LCFS, priority, SIRO).
3. Service mechanism: the number of servers (single or multiple, in series or parallel) and the service time distribution, usually exponential with rate $\mu$.
4. Departure: the customer leaves the system after service.

Example: M/M/1 model (a single-counter bank or a repair shop)

Customers arrive at rate $\lambda$ and are served at rate $\mu$ by one server. For $\lambda < \mu$, with $\rho = \lambda/\mu$:

• $P_0 = 1 - \rho$ and $P_n = \rho^n(1 - \rho)$
• $L_s = \dfrac{\lambda}{\mu - \lambda}$ and $L_q = \dfrac{\lambda^2}{\mu(\mu - \lambda)}$
• $W_s = \dfrac{1}{\mu - \lambda}$ and $W_q = \dfrac{\lambda}{\mu(\mu - \lambda)}$

Assumptions

• Arrivals follow a Poisson process, so inter-arrival times are exponential and independent.
• Service times are exponentially distributed and independent of arrivals.
• Queue discipline is FCFS.
• The queue length may be unlimited (infinite capacity) and the calling population is infinite.
• Customers do not balk (refuse to join), renege (leave) or jockey (change queues).
• The system is in a steady state ($\lambda < \mu$), so the probabilities do not change with time.

(a) Kendall's notation

Kendall's notation describes a queueing system as $A/S/c/K/N/D$:

• A: arrival distribution (M = Poisson/Markovian, D = deterministic, G = general).
• S: service time distribution (M = exponential, D, $E_k$, G).
• c: number of parallel servers.
• K: system capacity (default $\infty$).
• N: calling population size (default $\infty$).
• D: queue discipline (FCFS, LCFS, SIRO, priority; default FCFS).

Example: $M/M/1/\infty/\infty/FCFS$ is written $M/M/1$, a single-server queue with Poisson arrivals and exponential service.

(b) Types of inventory systems

1. Fixed order quantity (Q) system: a fixed quantity (the EOQ) is ordered whenever stock falls to the reorder point. It needs continuous monitoring and suits high-value (A-class) items.
2. Periodic review (P) system: stock is checked at fixed intervals and an order is placed to bring it up to a target level. The order quantity varies and review is simpler.
3. Two-bin system: stock is kept in two bins; when the first is empty, an order is placed while the second is used. It is suitable for low-value items.
4. ABC system: items are classified into A, B and C by consumption value, and different control levels are used for each class.
5. Min-max (S, s) system: an order is placed when stock falls to the minimum level $s$, bringing it up to the maximum level $S$.

Inventory models may also be classified as deterministic or probabilistic, depending on whether demand and lead time are known with certainty.

(c) Importance and advantage of duality

• The dual is often easier to solve because it has fewer constraints (rows) when the primal has many constraints and few variables.
• The dual variables are shadow prices, showing the worth of one extra unit of each resource.
• It helps in economic interpretation and sensitivity analysis.
• Both problems have the same optimal objective value, which lets us verify the solution.
• It supports the dual simplex method, used when a solution is optimal but infeasible.
• Solving one problem gives the optimal solution of the other.

Rows are Company 1's strategies and columns are Company 2's strategies, in the order: coupons (C), decrease price (D), maintain (M), advertising (A). Payoffs are gains for Company 1.

Saddle point test

The row minima are $-2, 1, -3, -3$, so maximin $= 1$. The column maxima are $6, 2, 12, 6$, so minimax $= 2$. Since $1 \ne 2$, there is no saddle point and mixed strategies are needed.

Dominance

• Column M is dominated by column C (Company 2 prefers smaller values, and every entry of C is at most that of M). Delete M.
• Rows C and A are dominated by row D (6, 1, 3 is at least 2, -2, 1 and 2, -3, 1). Delete them.
• Column A is then dominated by column D (1 and 2 are at most 3 and 6). Delete A.

The reduced game is:

Solution of the 2 x 2 game

Let Company 1 play D with probability $p$ and M with probability $1 - p$. Equating the expected payoffs against C and D:

$6p - 3(1-p) = p + 2(1-p) \;\Rightarrow\; 9p - 3 = 2 - p \;\Rightarrow\; p = \tfrac{1}{2}$

Let Company 2 play C with probability $q$ and D with probability $1 - q$:

$6q + (1-q) = -3q + 2(1-q) \;\Rightarrow\; 1 + 5q = 2 - 5q \;\Rightarrow\; q = \tfrac{1}{10}$

Value of the game $= 9(0.5) - 3 = 1.5$.

Optimal strategies

• Company 1: Decrease price with probability $1/2$, Maintain present strategy with probability $1/2$ (never give coupons or increase advertising).
• Company 2: Give coupons with probability $1/10$, Decrease price with probability $9/10$.
• Value of the game $= 1.5$ (an average gain of 1.5 in market share for Company 1).

Check against the original matrix: Company 2's mix gives Company 1 only $-1.6$ (row C) and $-2.5$ (row A), both below 1.5. Company 1's mix gives Company 2 payoffs 6 (column M) and 4.5 (column A), both above 1.5, so neither deviation helps.

$\text{Min } Z = 300X_1 + 800X_2$

subject to $X_1 + X_2 = 200,\; X_1 \le 40,\; X_2 \ge 30,\; X_1, X_2 \ge 0$.

Step 1: Write in standard primal form (all constraints $\ge$ or $=$):

$X_1 + X_2 = 200,\qquad -X_1 \ge -40,\qquad X_2 \ge 30$

Step 2: Dual. Let $y_1$ (free, since the constraint is an equality), $y_2 \ge 0$ and $y_3 \ge 0$ be the dual variables.

$\text{Max } W = 200y_1 - 40y_2 + 30y_3$

subject to

$y_1 - y_2 \le 300 \quad (\text{for } X_1)$

$y_1 + y_3 \le 800 \quad (\text{for } X_2)$

$y_1 \text{ unrestricted},\; y_2, y_3 \ge 0$

Step 3: Solve the dual. Since $y_3$ has a positive coefficient (30) in $W$, but using it needs $y_1 + y_3 \le 800$, $y_3$ takes value 0 at the best point. Then $W = 200y_1 - 40y_2$ is largest when $y_1$ is as large as possible, and $y_2$ as small as possible, so both dual constraints are tight:

$y_1 = 800,\qquad y_2 = y_1 - 300 = 500,\qquad y_3 = 0$

$W = 200(800) - 40(500) + 30(0) = 160{,}000 - 20{,}000 = 140{,}000$

Step 4: Primal solution. Since $y_2 > 0$, the constraint $X_1 \le 40$ is tight, so $X_1 = 40$. From $X_1 + X_2 = 200$, $X_2 = 160$. Since $y_3 = 0$, $X_2 \ge 30$ may be slack, and indeed $160 > 30$.

Check: $Z = 300(40) + 800(160) = 12{,}000 + 128{,}000 = 140{,}000$, which equals $W$.

$X_1 = 40,\quad X_2 = 160,\quad Z_{min} = \text{Rs } 140{,}000$