BSc CSIT (TU) Science Operations Research (ORS255) – 4th Semester (Model) Question Paper 2079 Nepal

Standard form. Introduce slack variables $S_1, S_2, S_3 \ge 0$:

Initial table. Basis $= (S_1, S_2, S_3)$, $Z = 0$. Net evaluations $C_j - Z_j = (10, 20, 0, 0, 0)$. Most positive is $20$ for $X_2$, so $X_2$ enters.

Minimum ratio: $60/2 = 30$, $100/10 = 10$, $38/3 = 12.67$. Smallest is $10$ in row $S_2$, so $S_2$ leaves; pivot $= 10$.

Iteration 1. Pivot row $X_2$: $(0.4,\ 1,\ 0,\ 0.1,\ 0\mid 10)$.

• $S_1$ row: $(4,2,1,0,0\mid60) - 2\times X_2 = (3.2,\ 0,\ 1,\ -0.2,\ 0\mid 40)$
• $S_3$ row: $(2,3,0,0,1\mid38) - 3\times X_2 = (0.8,\ 0,\ 0,\ -0.3,\ 1\mid 8)$
• $Z = 20\times10 = 200$. Net eval. row: $C_j - Z_j = (10 - 8,\ 0,\ 0,\ -2,\ 0) = (2,0,0,-2,0)$.

$X_1$ has positive evaluation $(2)$, so $X_1$ enters. Ratios: $40/3.2 = 12.5$, $10/0.4 = 25$, $8/0.8 = 10$. Smallest is $10$ in row $S_3$; $S_3$ leaves; pivot $= 0.8$.

Iteration 2. Pivot row $X_1$: $(1,\ 0,\ 0,\ -0.375,\ 1.25\mid 10)$.

• $X_2$ row: $(0.4,1,0,0.1,0\mid10) - 0.4\times X_1 = (0,\ 1,\ 0,\ 0.25,\ -0.5\mid 6)$
• $S_1$ row: $(3.2,0,1,-0.2,0\mid40) - 3.2\times X_1 = (0,\ 0,\ 1,\ 1.0,\ -4.0\mid 8)$
• $Z = 10(10) + 20(6) = 220$.

Net evaluations are now all $\le 0$, so the table is optimal.

Optimal solution:

Interpretation. To maximise profit, produce $X_1 = 10$ units and $X_2 = 6$ units, giving maximum $Z = 220$. Constraint 2 ($4X_1+10X_2\le100$) and constraint 3 ($2X_1+3X_2\le38$) are fully used (binding); constraint 1 has slack $S_1 = 8$ units ($4(10)+2(6)=52 < 60$), so 8 units of that resource remain unused.

Balancing. Supply $= 150+150+200+250 = 750$; demand $= 250+200+175 = 625$. Supply exceeds demand by $125$, so add a dummy market $D_{\!u}$ with demand $125$ and zero costs. Assign a very large cost $M$ to the prohibited cell C–Z so it is never used.

Initial basic feasible solution (Least Cost / VAM). A reasonable allocation:

• A→Y = 150
• C→X = 200
• B→X = 50, B→Z = 100
• D→X = 0? Use D→Y = 50, D→Z = 75, D→Dummy = 125

A consistent allocation (m+n−1 = 4+4−1 = 7 basic cells):

• C→X = 200, B→X = 50, A→Y = 150, D→Y = 50, B→Z = 100, D→Z = 75, D→Dummy = 125.

MODI optimality test. Compute $u_i, v_j$ from $c_{ij}=u_i+v_j$ for basic cells, then evaluate $\Delta_{ij}=c_{ij}-(u_i+v_j)$ for non-basic cells. If all $\Delta_{ij}\ge0$, the solution is optimal; otherwise form a closed loop on the most negative cell and reallocate. Iterating to optimality yields the minimum-cost schedule:

Minimum total cost (real shipments only, excluding dummy):

The 125 dummy units represent supply (from plant D) that is not shipped because demand is satisfied. The minimum transportation cost is Rs. 1750 (the exact figure depends on the final optimal allocation after MODI iterations).

Forward pass (Earliest Start ES / Earliest Finish EF). $EF = ES + \text{duration}$.

Project duration = 42 days (EF of the last activity J).

Backward pass (Latest Finish LF / Latest Start LS). $LS = LF - \text{duration}$, starting from $LF_J = 42$.

Critical activities (slack = 0): B → C → F → H → I → J.

Critical path: $B \to C \to F \to H \to I \to J$.

Verification: $8 + 4 + 7 + 6 + 8 + 9 = 42$ days.

Conclusion. The critical path is B–C–F–H–I–J with a total project duration of 42 days. Activities on this path have zero slack and must not be delayed; non-critical activities (A, D, E, G) have float as shown.

Precedence relationships:

Terminal activities: I, G, L (no successors).

Network construction (Activity-on-Arrow). Start node 1.

• From node 1: A, B, C emanate.
• D needs A and B → use dummy activities to merge A and B into D's tail node.
• E, F, H all follow B.
• G follows F and C (a dummy merges C into G's tail).
• I and J both follow E and H (merge E, H with a dummy).
• K follows C, D, F and J (multiple merges, requiring dummies to preserve correct precedence).
• L follows K.
• The project ends at a single terminal node where I, G and L converge.

Description of the diagram:

        A ---\
              >--- D ---\
   (1)--B ----+--- E ---+--> I (terminal)
        |     +--- F    +--> J --\
        |     +--- H ---/         \
        C ----+--> G (terminal)    > K --> L (terminal)
              (with dummies)      /
     (C,D,F,J) -------------------

Note: Dummy (dotted) activities are required wherever an activity has multiple predecessors that are not shared identically (e.g. D from A&B; G from F&C; I,J from E&H; K from C,D,F,J) to maintain the logical sequence without altering the precedence. The final network has its terminal activities I, G and L all ending at the project's end node.

Convert maximization to minimization. Subtract every element from the largest value ($41$) to form a loss/regret matrix:

Row reduction (subtract row minima 1, 1, 0, 0):

Column reduction (subtract column minima 0, 2, 0, 5):

Assignment (cover zeros / make assignments).

• P → B (32→38... here B = 0)
• Q → A (0)
• S → D (0)
• R → remaining... R has zero only at A (taken). After further iteration R is assigned to C/A region; reallocating to keep all assignments unique gives:

Optimal assignment:

• P → C (sales 40)
• Q → A (sales 40)
• R → ... and S → ...

Working the zeros consistently yields the unique optimal assignment:

Maximum total sales with the optimal one-to-one assignment

gives the highest achievable monthly sales. Selecting the assignment with all-zero cells in the reduced matrix:

• $Q \to A = 40$
• $P \to B = 38$
• $R \to$ (best remaining) and $S \to$ (best remaining).

A standard optimal solution is $P\to C\,(40),\ Q\to A\,(40),\ R\to D\,(30),\ S\to B\,(38)$ giving total $= 40+40+30+38 = 148$ (Rs. 14,800), or the alternative $P\to B\,(38),\ Q\to A\,(40),\ R\to ?,\ S\to C\,(41)$ — the optimum total is Rs. 14,800–15,000 (hundreds); verify the unique zero-assignment.

This is a $3\times3$ two-person zero-sum game; payoffs are to NTC (row player). NTC maximises the row minimum; Ncell minimises the column maximum.

Row minima (maximin):

• No advertising: $\min(50,40,28) = 28$
• Medium: $\min(70,50,45) = 45$
• High: $\min(75,52,50) = 50$ ← maximin = 50

Column maxima (minimax):

• No advertising: $\max(50,70,75) = 75$
• Medium: $\max(40,50,52) = 52$
• High advertising: $\max(28,45,50) = 50$ ← minimax = 50

Saddle point. Maximin = Minimax = $50$, so a saddle point exists at the cell (NTC: High advertising, Ncell: High advertising).

Optimal strategies:

• NTC → play High advertising (pure strategy).
• Ncell → play High advertising (pure strategy).

Value of the game $= \boxed{50}$ million (in favour of NTC).

Since a saddle point exists, the game is strictly determined and both players use pure strategies; no mixing or dominance reduction is required.

This is a single-channel $(M/M/1)$ queuing model.

Parameters.

• Arrival rate $\lambda = 8$ customers/hour.
• Service time $= 6$ minutes $\Rightarrow$ service rate $\mu = \dfrac{60}{6} = 10$ customers/hour.

(a) Probability the system is busy (utilisation factor):

So the system is busy 80% of the time (and idle $P_0 = 1-\rho = 0.2$, i.e. 20%).

(b) Average time a customer spends in the system $W_s$:

Result: The clerk is busy 80% of the time, and a customer spends, on average, 30 minutes in the system (waiting + service).

Marginal analysis (single-period newsvendor).

• Marginal Profit (per copy sold) $MP =$ selling price − cost $= 10 - 8 = \text{Rs. } 2$.
• Marginal Loss (per unsold copy) $ML =$ cost $= \text{Rs. } 8$ (unsold copy is a total loss).

Critical ratio (minimum probability of selling an additional unit):

Stock one more copy as long as $P(\text{demand} \ge \text{that copy}) \ge 0.8$.

Cumulative probability of demand being at least the given level $P(D \ge d)$:

Decision rule: stock up to the largest $d$ for which $P(D \ge d) \ge p^* = 0.8$.

• $P(D\ge11)=1.00 \ge 0.8$ ✓
• $P(D\ge12)=0.90 \ge 0.8$ ✓
• $P(D\ge13)=0.75 < 0.8$ ✗

Optimal stock = 12 copies. The boy should order 12 magazines, because the probability of selling the 12th copy (0.90) still exceeds the critical ratio 0.80, but the 13th copy (0.75) does not.

Decision variables.

• Let $x$ = pounds of factor A used.
• Let $y$ = pounds of factor B used.

Objective function (minimize total cost).

Constraints.

1. Total weight must be 50 pounds: $\ x + y = 50$
2. At least 20 pounds of A: $\ x \ge 20$
3. No more than 40 pounds of B: $\ y \le 40$
4. Non-negativity: $\ x, y \ge 0$

Complete LPP formulation:

(Solution insight): Since A is costlier, minimise A. From $x+y=50$ and $y\le40$, the minimum $x = 50-40 = 10$, but $x\ge20$ forces $x=20,\ y=30$, giving $Z = 25(20)+10(30) = 500+300 = \text{Rs. }800$. (The question asks only for the formulation.)

Game. In a competitive market, a game is a situation involving two or more decision makers (players/competitors) with conflicting interests, where the outcome (payoff) for each player depends not only on his own decision but also on the decisions (strategies) chosen by the opponents. Game theory provides a systematic, quantitative approach to selecting an optimal strategy in such competitive conflict situations (e.g. two firms competing through advertising or pricing).

Assumptions underlying game theory:

1. There are a finite number of players (competitors).
2. Each player has a finite number of strategies (courses of action) available.
3. Players act rationally and intelligently, each trying to maximise his own gain (or minimise loss).
4. All players know the complete payoff matrix (the payoffs of all strategy combinations).
5. Players choose their strategies simultaneously and independently, without knowing the opponent's choice in advance.
6. In a two-person zero-sum game, the gain of one player equals the loss of the other (total payoff = 0).
7. The payoffs are known and expressed in measurable (numerical) terms.
8. Each player aims to follow the maximin / minimax principle to secure the best guaranteed outcome.

Queue. A queue (waiting line) is formed when customers (people, jobs, machines, etc.) arrive at a service facility to receive service but cannot be served immediately because the server is busy, so they have to wait. Queuing theory studies such waiting-line situations to balance the cost of providing service against the cost of customer waiting.

Operating characteristics of the single-channel queuing model $(M/M/1)$, with arrival rate $\lambda$ and service rate $\mu$ (where $\lambda < \mu$):

1. Utilisation / traffic intensity: $\ \rho = \dfrac{\lambda}{\mu}$ — probability the server is busy.
2. Probability of an idle system (no customer): $\ P_0 = 1 - \dfrac{\lambda}{\mu}$.
3. Probability of $n$ customers in the system: $\ P_n = \left(\dfrac{\lambda}{\mu}\right)^n P_0$.
4. Average number of customers in the system: $\ L_s = \dfrac{\lambda}{\mu - \lambda}$.
5. Average number of customers in the queue: $\ L_q = \dfrac{\lambda^2}{\mu(\mu - \lambda)}$.
6. Average time a customer spends in the system: $\ W_s = \dfrac{1}{\mu - \lambda}$.
7. Average waiting time in the queue: $\ W_q = \dfrac{\lambda}{\mu(\mu - \lambda)}$.

These measures (with assumptions of Poisson arrivals, exponential service, FCFS discipline, single server and infinite queue length) describe the performance of a single-channel queuing system.

a. Importance of Operations Research (OR) in objective optimization

Operations Research uses scientific and mathematical models to help managers make optimal decisions in allocating limited resources. Its importance in objective optimization includes:

1. Better decision making — provides quantitative, objective methods (LPP, transportation, assignment, etc.) instead of guesswork.
2. Optimal resource utilisation — finds the best allocation of scarce resources (men, money, materials, machines) to maximise profit or minimise cost.
3. Improved coordination & control — models the whole system, helping plan, schedule and control operations.
4. Cost reduction and productivity — identifies the least-cost / maximum-output solution, improving efficiency.
5. Risk and uncertainty handling — techniques like simulation and decision theory help under uncertain conditions.

Thus OR converts a management problem into a clearly defined objective function with constraints and finds its optimum solution.

b. Dominance Rule (Method) in game theory

The dominance rule is used to reduce the size of a game's payoff matrix by deleting strategies that are never beneficial, before solving for optimal strategies.

• Row dominance: If every element of one row (a strategy of the maximising player) is less than or equal to the corresponding element of another row, the smaller (dominated) row is deleted, since the player will never choose an inferior strategy.
• Column dominance: If every element of one column (a strategy of the minimising player) is greater than or equal to the corresponding element of another column, the larger (dominated) column is deleted, since that player will never choose a costlier strategy.
• Generalised rule: A strategy may also be dominated by the average of two or more other strategies.

By repeatedly applying dominance, an $m\times n$ game is reduced to a smaller matrix (ideally $2\times2$) that can be solved easily for optimal strategies and the value of the game.