Objective of Linear Programming

The objective of linear programming (LP) is to find the best possible (optimal) solution to a problem in which limited resources must be allocated among competing activities. In formal terms, LP seeks to maximize or minimize a linear objective function subject to a set of linear constraints and non-negativity restrictions.

The main objectives are:

1. Optimal allocation of scarce resources — To use limited resources such as labour, money, time, materials, and machine capacity in the most efficient way so that the desired outcome is achieved.

2. Maximization of profit or contribution — When the goal is profit, LP determines the production or sales mix that yields the highest total profit within the available resources.

3. Minimization of cost, time, or effort — When the goal is economy, LP finds the combination of activities (e.g., transportation routes, diet, staffing) that gives the lowest total cost or the least time.

4. Best possible decision under constraints — It provides a systematic, quantitative basis for choosing among many feasible alternatives, instead of relying on trial and error or intuition.

5. Feasibility and efficiency — It identifies whether a feasible solution exists at all, and among all feasible solutions selects the one that is most efficient with respect to the stated objective.

6. Aid to planning and control — The optimal solution and the shadow prices (dual values) obtained from LP help management in planning resource use, pricing, and deciding where additional capacity would be most valuable.

In short, the objective of linear programming is to optimize (maximize or minimize) a linear objective function over a region defined by linear inequalities, thereby providing the most effective use of available resources.

The primal is a maximisation problem with mixed constraints ($\le$, $\ge$, $=$) and non-negative variables. Take one dual variable per primal constraint.

Primal

$\text{Max } Z = 15X_1 + 10X_2 + 25X_3$

subject to

$X_1 + X_2 - X_3 \le 3$ $2X_1 + 10X_2 + 6X_3 \ge 180$ $-X_1 + X_2 - 3X_3 = 80$

$X_1, X_2, X_3 \ge 0$

Rules used (primal is Max)

• The dual is a minimisation problem; the primal right-hand sides (3, 180, 80) become the dual objective coefficients.
• The primal objective coefficients (15, 10, 25) become the dual right-hand sides.
• Each primal variable is $\ge 0$, so each dual constraint is of the $\ge$ type, and the coefficient matrix is transposed.
• A $\le$ constraint gives $Y_1 \ge 0$, a $\ge$ constraint gives $Y_2 \le 0$, and an $=$ constraint gives $Y_3$ unrestricted in sign.

Dual

$\text{Min } W = 3Y_1 + 180Y_2 + 80Y_3$

subject to

$Y_1 + 2Y_2 - Y_3 \ge 15$ $Y_1 + 10Y_2 + Y_3 \ge 10$ $-Y_1 + 6Y_2 - 3Y_3 \ge 25$

$Y_1 \ge 0,\quad Y_2 \le 0,\quad Y_3 \text{ unrestricted in sign}$

(Equivalently, rewrite the $\ge$ constraint as $-2X_1 - 10X_2 - 6X_3 \le -180$ and let $Y_2' = -Y_2 \ge 0$.)

Let me verify the conversion by checking the primal-dual correspondence.

Primal:

• Maximize $Z = 30X_1 + 50X_2 + 40X_3$
• Constraints:
  • $2X_1 + 3X_2 + 0X_3 \le 800$
  • $0X_1 + 2X_2 + 5X_3 \le 1000$
  • $3X_1 + 2X_2 + 4X_3 \le 1500$
• $X_1, X_2, X_3 \ge 0$

Dual construction:

• Since primal is maximization with $\le$ constraints and non-negative variables, dual is minimization with $\ge$ constraints and non-negative dual variables.
• Dual variables: $Y_1, Y_2, Y_3$ (one per primal constraint).
• Dual objective: Minimize $W = 800Y_1 + 1000Y_2 + 1500Y_3$ (RHS of primal constraints become coefficients).
• Dual constraints: Transpose of primal coefficient matrix, with primal objective coefficients as RHS.

Primal coefficient matrix: $A = \begin{pmatrix} 2 & 3 & 0 \\ 0 & 2 & 5 \\ 3 & 2 & 4 \end{pmatrix}$

Transpose: $A^T = \begin{pmatrix} 2 & 0 & 3 \\ 3 & 2 & 2 \\ 0 & 5 & 4 \end{pmatrix}$

Dual constraints:

• $2Y_1 + 0Y_2 + 3Y_3 \ge 30$
• $3Y_1 + 2Y_2 + 2Y_3 \ge 50$
• $0Y_1 + 5Y_2 + 4Y_3 \ge 40$

This matches the model answer exactly. The model answer is correct and complete.

OK

CPM vs PERT

Both CPM (Critical Path Method) and PERT (Program Evaluation and Review Technique) are network-based project management techniques used for planning, scheduling and controlling projects. However, they differ in the following basic ways:

In short: CPM is a deterministic, activity-oriented technique used for repetitive projects where activity times are known, while PERT is a probabilistic, event-oriented technique used for uncertain, one-time projects where activity times are estimated from three values.

Sequencing Problem

A sequencing problem is a type of operations-research problem in which a number of jobs (tasks) must be processed through a number of machines (or service facilities) in a fixed technological order, and we must decide the order (sequence) in which the jobs should be processed so that some measure of performance is optimised. The most common objective is to minimise the total elapsed time (makespan) — the time from the start of the first job on the first machine to the completion of the last job on the last machine — and/or to minimise the idle time of machines and the waiting time of jobs.

Formally, if there are $n$ jobs $J_1, J_2, \dots, J_n$ and $m$ machines $M_1, M_2, \dots, M_m$, and each job must be processed on the machines in the order $M_1 \to M_2 \to \dots \to M_m$ with known processing times $t_{ij}$ (time of job $i$ on machine $j$), the sequencing problem is to find the permutation of jobs that gives the minimum total elapsed time. A very common special case is the $n$-jobs–2-machines problem, solved by Johnson's rule: job $i$ precedes job $k$ if $\min(t_{i1}, t_{k2}) \le \min(t_{k1}, t_{i2})$.

Assumptions of the Sequencing Problem

1. Known processing times — The time taken by each job on each machine is known in advance and is constant (deterministic).
2. Fixed order of machines — Every job is processed on the machines in the same technological order; no job can skip a machine or be processed out of order.
3. No pre-emption — Once a job starts on a machine, it must be completed without interruption.
4. One job at a time on a machine — A machine can process only one job at a time.
5. One machine at a time per job — A job cannot be processed on more than one machine simultaneously.
6. No passing — Jobs cannot overtake one another; the sequence of jobs remains the same on all machines.
7. All jobs available at the start — Every job is ready for processing at time zero (no release dates).
8. Machines are available throughout — Machines are never breakdown-prone and are available for the whole period (no breakdowns, no set-up times, or set-up times are included in processing times).
9. Independent jobs — Jobs are independent of one another; the processing of one job does not affect another.
10. Objective is well defined — The criterion of optimality (usually minimum total elapsed time) is clearly specified.

Given:
Annual demand, (D = 100) units/year
Holding/storage cost, (C_h = \text{Rs. } 6) per unit per year
Set-up cost per run, (C_o = \text{Rs. } 40)

Shortages are not allowed, so this is the basic EOQ model.

Optimum run size (EOQ):

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

[ Q^*=\sqrt{\frac{2 \times 100 \times 40}{6}} ]

[ Q^*=\sqrt{\frac{8000}{6}} ]

[ Q^*=\sqrt{1333.33}=36.51 \text{ units} ]

So, the optimum run size is approximately:

[ \boxed{Q^* \approx 36.51 \text{ units}} ]

If whole units are required, take (Q^* = 37) units.

---

Minimum average yearly cost:

[ TC_{\min}=\sqrt{2DC_oC_h} ]

[ TC_{\min}=\sqrt{2 \times 100 \times 40 \times 6} ]

[ TC_{\min}=\sqrt{48000} ]

[ TC_{\min}=219.09 ]

[ \boxed{TC_{\min} \approx \text{Rs. } 219.09 \text{ per year}} ]

So, the optimum run size is about 36.51 units, and the minimum average yearly inventory cost is about Rs. 219.09.

This is an assignment problem (4 jobs, 4 contractors, minimise cost, amounts in lakh Rs). Use the Hungarian method.

Step 1: Row reduction (row minima 9, 20, 28, 10)

Step 2: Column reduction (column minima 1, 0, 0, 0)

Step 3: Test for optimality. The zeros can be covered by 3 lines (row a, column 2, column 3), fewer than 4, so no complete assignment exists yet. The smallest uncovered element is 1. Subtract 1 from uncovered elements and add 1 at line intersections (a-2, a-3):

Still only 3 lines are needed (row a, row c, column 3), because b and d both have a zero only in column 3. The smallest uncovered element is 2. Subtract 2 from uncovered elements and add 2 at intersections (a-3, c-3):

Now 4 lines are needed, so an optimal assignment exists. Row a has zeros in columns 1 and 4, row c in columns 1 and 2, row d in columns 2 and 3, row b in columns 1, 2 and 3. One complete assignment is a-4, c-1, b-3, d-2.

Optimal assignment

$\text{Minimum total cost} = 9 + 20 + 30 + 12 = \text{Rs } 71 \text{ lakh}$

An alternative optimum is a-4, b-1, c-2, d-3, costing $9+24+28+10 = \text{Rs } 71$ lakh.

Network diagram

No dummy activity is needed. The network is:

             4             8
      ┌────────▶ 2 ───────────────┐
      │                            ▼
(1) ──┤                          (6) ──10──▶ (7)
      │ 6                          ▲  ▲        ▲
      └────▶ (3) ──7──▶ (4) ──6────┘  │        │
              │  \                    │        │
              │   \ 4                5│       19
              │    ▼                  │        │
              └──▶ (5) ───────────────┘        │
                    └──────────────────────────┘

---

Event times

Let (E_i) = earliest event time and (L_i) = latest event time.

Forward pass:

[ E_1=0 ] [ E_2=0+4=4,\qquad E_3=0+6=6 ] [ E_4=6+7=13,\qquad E_5=6+4=10 ] [ E_6=\max(4+8,;13+6,;10+5)=\max(12,19,15)=19 ] [ E_7=\max(10+19,;19+10)=\max(29,29)=29 ]

Backward pass:

[ L_7=29 ] [ L_6=29-10=19 ] [ L_5=\min(19-5,;29-19)=\min(14,10)=10 ] [ L_4=19-6=13 ] [ L_3=\min(13-7,;10-4)=\min(6,6)=6 ] [ L_2=19-8=11 ] [ L_1=\min(11-4,;6-6)=\min(7,0)=0 ]

Project duration = 29 days.

---

Activity start and completion times

[ ES=E_i,\qquad EF=ES+d ] [ LF=L_j,\qquad LS=LF-d ] [ \text{Total float}=LS-ES=LF-EF ]

---

Critical activities and critical paths

Activities with zero total float are critical:

[ \boxed{1-3,;3-4,;4-6,;6-7,;3-5,;5-7} ]

There are two critical paths:

[ \boxed{1 \to 3 \to 4 \to 6 \to 7} ]

[ \boxed{1 \to 3 \to 5 \to 7} ]

Both have duration:

[ 6+7+6+10=29 ]

[ 6+4+19=29 ]

Hence the project completion time is 29 days.

1. Formulation of the LPP

Let
$x_1$ = number of units of product A produced per week
$x_2$ = number of units of product B produced per week

Profit per unit: A = Rs. 40, B = Rs. 35.

Maximize total profit:

$$Z = 40x_1 + 35x_2$$

Subject to the constraints:

Raw material:

$$2x_1 + 3x_2 \le 60$$

Labour hours:

$$4x_1 + 3x_2 \le 96$$

Non-negativity:

$$x_1 \ge 0,\quad x_2 \ge 0$$

---

2. Standard form

Introduce slack variables $s_1$ and $s_2$:

$$2x_1 + 3x_2 + s_1 = 60$$ $$4x_1 + 3x_2 + s_2 = 96$$

Objective function:

$$Z - 40x_1 - 35x_2 = 0$$

---

3. Initial simplex tableau

The most negative entry in the $Z$-row is $-40$, so $x_1$ enters.

Ratio test:

$$\frac{60}{2}=30,\qquad \frac{96}{4}=24$$

Minimum ratio is 24, so $s_2$ leaves. Pivot element = 4.

---

4. First iteration

Divide pivot row by 4:

$$x_1:\quad [1,\ \tfrac34,\ 0,\ \tfrac14,\ 24]$$

Update $s_1$-row:

$$s_1:\quad [0,\ \tfrac32,\ 1,\ -\tfrac12,\ 12]$$

Update $Z$-row:

$$Z:\quad [0,\ -5,\ 0,\ 10,\ 960]$$

So the tableau becomes:

Now the most negative entry in the $Z$-row is $-5$, so $x_2$ enters.

Ratio test:

$$\frac{12}{3/2}=8,\qquad \frac{24}{3/4}=32$$

Minimum ratio is 8, so $s_1$ leaves. Pivot element = $\frac32$.

---

5. Second iteration

Divide pivot row by $\frac32$:

$$x_2:\quad [0,\ 1,\ \tfrac23,\ -\tfrac13,\ 8]$$

Update $x_1$-row:

$$x_1:\quad [1,\ 0,\ -\tfrac12,\ \tfrac12,\ 18]$$

Update $Z$-row:

$$Z:\quad [0,\ 0,\ \tfrac{10}{3},\ \tfrac{25}{3},\ 1000]$$

Final tableau:

Since there is no negative entry in the $Z$-row, the optimal solution is reached.

---

6. Optimal solution

$$x_1 = 18,\qquad x_2 = 8$$ $$Z_{\max} = 40(18) + 35(8) = 720 + 280 = 1000$$

Therefore, the firm should produce:

• 18 units of product A
• 8 units of product B

per week to earn the maximum profit of:

$$\boxed{\text{Rs. } 1000}$$

Data. Supply: X = 55, Y = 25, Z = 35 (total 115). Demand: A = 35, B = 45, C = 35 (total 115), so the problem is balanced. The cost of Z to C is printed as 524; this is taken as a misprint for 24.

Initial solution by Vogel's Approximation Method (VAM)

Penalties (difference of two smallest costs): rows X 4, Y 0, Z 8; columns A 38, B 8, C 8.

1. Largest penalty is 38 (column A). Cheapest cell is Y-A = 16. Allocate $\min(25, 35) = 25$. Y is exhausted; A needs 10 more.
2. Remaining rows X, Z; penalties: rows X 4, Z 8; columns A 4, B 42, C 34. Largest is 42 (column B). Cheapest is Z-B = 16. Allocate 35. Z is exhausted; B needs 10 more.
3. Only row X remains: X-A = 10, X-B = 10, X-C = 35.

There are $m + n - 1 = 5$ allocations.

$\text{Cost} = 10(54) + 10(58) + 35(58) + 25(16) + 35(16) = 540 + 580 + 2030 + 400 + 560 = \text{Rs } 4110$

MODI test. Put $u_X = 0$. From occupied cells: $v_A = 54$, $v_B = 58$, $v_C = 58$, $u_Y = 16 - 54 = -38$, $u_Z = 16 - 58 = -42$.

Opportunity cost $d_{ij} = c_{ij} - (u_i + v_j)$ for empty cells:

Y-C is negative, so the solution is not optimal. The loop is Y-C (+), Y-A (-), X-A (+), X-C (-). The smallest value on the minus cells is $\min(25, 35) = 25$. Shift 25 units: Y-C = 25, Y-A = 0, X-A = 35, X-C = 10.

Re-test. With $u_X = 0$: $v_A = 54$, $v_B = 58$, $v_C = 58$, $u_Y = 16 - 58 = -42$, $u_Z = 16 - 58 = -42$.

All are positive, so the solution is optimal.

Optimal transportation plan: X to A 35, X to B 10, X to C 10, Y to C 25, Z to B 35.

$\text{Minimum cost} = 35(54) + 10(58) + 10(58) + 25(16) + 35(16) = 1890 + 580 + 580 + 400 + 560 = \text{Rs } 4010$

Expected time and variance of each activity: $t_e = \dfrac{a + 4m + b}{6}$, $\sigma^2 = \left(\dfrac{b - a}{6}\right)^2$.

I. Network and expected completion time

Nodes 1 to 6 with arcs 1-2, 1-3, 2-4, 2-6, 3-4, 3-5, 4-5, 5-6. The paths from node 1 to node 6 are:

The critical path is 1-3-4-5-6, so the expected project completion time is $T_E = 36$ days.

II. Probability of taking 5 days more than expected (41 days)

Variance of the project is the sum along the critical path:

$\sigma^2 = 4 + 9 + 0 + 1 = 14,\qquad \sigma = \sqrt{14} = 3.74$

$Z = \frac{41 - 36}{3.74} = 1.336$

$P(T \le 41) = P(Z \le 1.336) \approx 0.909$

So there is about a 91% chance that the project finishes within 41 days (and about 9% chance that it takes longer).

III. Completion time with 95% confidence

For 95%, $Z = 1.645$:

$T = 36 + 1.645 \times 3.74 \approx 42.15 \text{ days}$

The project will be completed in about 42 days with 95% confidence.

Operation Search was a counter-insurgency operation of the Royal Nepal Army, launched on 26 November 2001 after the breakdown of peace talks with the Maoists and the declaration of a state of emergency. Its objectives were:

1. To suppress the Maoist insurgency by breaking down their armed structure and organisational network.
2. To restore law and order and re-establish state authority in the insurgency-affected areas.
3. To protect government offices, infrastructure, communication towers and public property from attacks.
4. To give the general public security against extortion, intimidation, abduction and violence.
5. To safeguard national sovereignty and territorial integrity by preventing "liberated zones" and parallel governments.
6. To support the civil administration and police in enforcing law and order.
7. To disrupt the flow of arms, finance and logistics to the insurgents.
8. To create conditions for a political settlement and peace talks from a position of strength.

The operation was criticised by human rights organisations over alleged violations during the conflict.

Given:

• Daily demand = 40 packages/day
• Operating days = 260 days/year
• Annual demand, (D = 40 \times 260 = 10{,}400) packages/year
• Ordering cost, (S = \text{Rs. } 6) per order
• Holding/carrying cost, (H = \text{Rs. } 3) per package per year

a) Optimal order size (EOQ):

[ EOQ = \sqrt{\frac{2DS}{H}} ]

[ EOQ = \sqrt{\frac{2 \times 10400 \times 6}{3}} ]

[ EOQ = \sqrt{41600} = 203.96 \approx 204 \text{ packages} ]

Optimal order size = 204 packages (approximately).

---

b) Total annual cost of carrying and holding paper:

At EOQ, ordering cost equals carrying cost.

Carrying/holding cost:

[ \frac{Q}{2}H = \frac{204}{2} \times 3 = 102 \times 3 = \text{Rs. } 306 ]

Ordering cost:

[ \frac{D}{Q}S = \frac{10400}{204} \times 6 = \text{Rs. } 305.88 ]

Total annual inventory cost:

[ 306 + 305.88 = \text{Rs. } 611.88 ]

Total annual cost of carrying and holding paper = Rs. 611.88 approximately.
(If only the carrying/holding cost is required, it is Rs. 306.)

Total supply = 15 + 25 + 15 = 55 = total demand, so the problem is balanced. Since there are 3 sources and 4 destinations, a basic feasible solution has $m + n - 1 = 6$ allocations.

Initial solution by Vogel's Approximation Method (VAM)

1. Penalties: rows $O_1$ 0, $O_2$ 2, $O_3$ 1; columns $D_1$ 0, $D_2$ 2, $D_3$ 0, $D_4$ 1. The largest is 2 (tie); choose row $O_2$. Cheapest is $O_2D_1 = 8$. Allocate 15. $D_1$ is satisfied; $O_2$ has 10 left.
2. Remaining: $O_1$ (15), $O_2$ (10), $O_3$ (15); $D_2$ (15), $D_3$ (15), $D_4$ (10). Penalties: rows $O_1$ 1, $O_2$ 0, $O_3$ 1; columns $D_2$ 2, $D_3$ 0, $D_4$ 1. Largest is 2 (column $D_2$). Cheapest is $O_1D_2 = 8$. Allocate 15. $O_1$ is exhausted.
3. Remaining: $O_2$ (10), $O_3$ (15); $D_3$ (15), $D_4$ (10). Penalties: rows $O_2$ 0, $O_3$ 0; columns $D_3$ 1, $D_4$ 1. Take $D_3$: cheapest is $O_2D_3 = 10$. Allocate 10. $O_2$ is exhausted.
4. Only $O_3$ remains: $O_3D_3 = 5$, $O_3D_4 = 10$.

Only 5 cells are occupied, so one more is needed. Add a zero allocation at $O_1D_4$ (degenerate).

$\text{Cost} = 15(8) + 15(8) + 10(10) + 5(11) + 10(11) = 120 + 120 + 100 + 55 + 110 = 505$

Optimality test (MODI). Put $u_1 = 0$. From $O_1D_2$: $v_2 = 8$. From $O_1D_4$: $v_4 = 9$. From $O_3D_4$: $u_3 = 2$. From $O_3D_3$: $v_3 = 9$. From $O_2D_3$: $u_2 = 1$. From $O_2D_1$: $v_1 = 7$.

No value is negative, so the solution is optimal (the zeros indicate alternative optima).

Optimal solution: $O_1 \to D_2$ = 15, $O_2 \to D_1$ = 15, $O_2 \to D_3$ = 10, $O_3 \to D_3$ = 5, $O_3 \to D_4$ = 10.

$\text{Minimum transportation cost} = 505$

Use the Hungarian method on the cost matrix (machines W, X, Y, Z; jobs 1 to 4).

Step 1: Row reduction (row minima 3, 1, 2, 1)

Step 2: Column reduction (column minima 0, 0, 0, 1)

Step 3: Cover the zeros. Y and Z both have their only zero in column 3, so at most 3 independent zeros exist. The zeros are covered by 3 lines (row W, row X, column 3), which is less than 4, so the matrix is not optimal.

Step 4: Improve. The smallest uncovered element is 3 (Z-4). Subtract 3 from all uncovered elements (rows Y, Z in columns 1, 2, 4) and add 3 at the intersections (W-3, X-3).

Now 4 lines are needed, so an optimal assignment exists among the zeros. Y has its only zero in column 3, so Y takes job 3. Then Z must take its other zero in column 4, X takes column 2 and W takes column 1.

Optimal assignment

$\text{Minimum cost} = 3 + 1 + 2 + 5 = 11$

Step 1: Dependencies. A and B start the project. C follows A; D and E follow B; F needs C and D; G follows E; H and L follow F; I needs G and H; J follows I; K follows J.

Step 2: Network (activity on arrow). Events are numbered 1 to 10; no dummy activity is needed.

          A(8)        C(1)
   (1) ----------> (2) ----------> (4) --F(5)--> (6) --H(3)--> (7) --I(3)--> (8) --J(5)--> (9) --K(2)--> (10)
    \                               ^             \             ^                                          ^
     \ B(2)         D(9)           /               \ L(3)       | G(6)                                    |
      +-----> (3) ---------------->+                +-------------------------------------------------->+
               \                                                |
                +---------------- E(4) --> (5) ----------------+

Event 4 is reached by C and D; event 7 is reached by G (from event 5) and H (from event 6); event 10 is the end, reached by K and L.

Step 3: Forward pass (earliest event times).

$E_1 = 0,\ E_2 = 8,\ E_3 = 2,\ E_4 = \max(8+1,\ 2+9) = 11,\ E_5 = 6,\ E_6 = 16,\ E_7 = \max(6+6,\ 16+3) = 19,\ E_8 = 22,\ E_9 = 27,\ E_{10} = \max(27+2,\ 16+3) = 29$

Step 4: Backward pass (latest event times).

$L_{10} = 29,\ L_9 = 27,\ L_8 = 22,\ L_7 = 19,\ L_6 = \min(19-3,\ 29-3) = 16,\ L_5 = 19-6 = 13,\ L_4 = 11,\ L_3 = \min(11-9,\ 13-4) = 2,\ L_2 = 11-1 = 10,\ L_1 = \min(10-8,\ 2-2) = 0$

Step 5: Activity floats (total float = $L_j - E_i - t$).

Critical path: B - D - F - H - I - J - K, with duration $2 + 9 + 5 + 3 + 3 + 5 + 2 = 29$ time units. This is the project completion time.

Formulation. Let $X, Y, Z$ be the units of products X, Y, Z produced.

$\text{Max } P = 40X + 25Y + 50Z$

subject to

$X + 2Y + Z \le 36 \quad (\text{raw material A})$ $2X + Y + 4Z \le 60 \quad (\text{raw material B})$ $2X + 5Y + Z \le 45 \quad (\text{raw material C})$

$X, Y, Z \ge 0$

Simplex method. Add slack variables $S_1, S_2, S_3$.

Initial table ($C_j - Z_j$: 40, 25, 50, 0, 0, 0)

$Z$ enters (largest $C_j - Z_j = 50$) and $S_2$ leaves (minimum ratio 15).

Second table ($C_j - Z_j$: 15, 12.5, 0, 0, -12.5, 0)

$X$ enters and $S_3$ leaves (minimum ratio 20).

Final table ($C_j - Z_j$: 0, -35, 0, 0, -10, -10)

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

Optimum product mix: $X = 20$ units, $Y = 0$, $Z = 5$ units.

$\text{Maximum profit} = 40(20) + 25(0) + 50(5) = 800 + 250 = \text{Rs } 1050$

Raw materials B and C are fully used; 11 units of A remain unused ($S_1 = 11$). The shadow prices are Rs 0 for A, Rs 10 per unit for B and Rs 10 per unit for C, and the dual objective $60(10) + 45(10)$ is also Rs 1050.

Check for Johnson's rule with three machines. The smallest time on machine A is 5, and the largest time on machine B is 5. Since $\min A \ge \max B$, the problem can be converted into a two-machine problem with fictitious machines $G = A + B$ and $H = B + C$.

Johnson's rule. The smallest value is 5 (job 1 on H), so job 1 goes last. Next smallest is 8 (jobs 2 and 5, both on G), so they go first. Of the remaining jobs 3 and 4, the smallest is 9 (job 3 on H), so job 3 goes after job 4.

Optimal sequence: $2 - 5 - 4 - 3 - 1$ (the sequence $5 - 2 - 4 - 3 - 1$ gives the same total time).

Time table (hours)

Minimum total elapsed time = 41 hours.

Idle times

• Machine A: it finishes at hour 36, so idle time is $41 - 36 = 5$ hours.
• Machine B: it works $2+1+4+5+3 = 15$ hours, so idle time is $41 - 15 = 26$ hours.
• Machine C: it works $3+7+5+6+7 = 28$ hours, so idle time is $41 - 28 = 13$ hours (8 hours at the start and 5 hours waiting).

Steps of Solving a Transportation Problem

A transportation problem is a special case of a linear programming problem in which a commodity is transported from several sources (supply/origin points) to several destinations (demand points) so as to minimise the total transportation cost. It is solved in the following steps.

Step 1: Formulate the problem as a transportation table

Let there be (m) sources (S_1, S_2, \dots, S_m) with supplies (a_1, a_2, \dots, a_m) and (n) destinations (D_1, D_2, \dots, D_n) with demands (b_1, b_2, \dots, b_n). Let (c_{ij}) be the cost of transporting one unit from source (i) to destination (j), and (x_{ij}) the number of units shipped from source (i) to destination (j).

The problem is:

$$\text{Minimise } Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}\,x_{ij}$$

subject to

$$\sum_{j=1}^{n} x_{ij} = a_i \quad (i = 1,2,\dots,m)$$ $$\sum_{i=1}^{m} x_{ij} = b_j \quad (j = 1,2,\dots,n)$$ $$x_{ij} \ge 0$$

Step 2: Check whether the problem is balanced or unbalanced

Compute the total supply (\sum a_i) and the total demand (\sum b_j).

• If (\sum a_i = \sum b_j), the problem is balanced and can be solved directly.
• If (\sum a_i \ne \sum b_j), the problem is unbalanced. Add a dummy source (if demand exceeds supply) or a dummy destination (if supply exceeds demand) with the difference as its supply or demand. The transportation cost for the dummy row/column is taken as zero.

Step 3: Find an initial basic feasible solution (IBFS)

Use any one of the following methods:

1. North-West Corner Rule (NWCR) — start from the top-left cell and allocate as much as possible, moving right or down.
2. Least Cost Method (LCM) — repeatedly allocate to the cell with the smallest cost in the remaining table.
3. Vogel's Approximation Method (VAM) — compute the penalty (difference between the two smallest costs) for each row and column, choose the row/column with the largest penalty, and allocate to its least-cost cell. VAM usually gives the best initial solution.

The number of basic (occupied) cells must be (m + n - 1); if fewer, the solution is degenerate and a zero allocation must be introduced in an independent cell.

Step 4: Test the solution for optimality

Check whether the current solution is optimal using either:

• Stepping Stone Method, or
• Modified Distribution (MODI) / u–v Method (more efficient).

For the MODI method:

1. Set (u_i + v_j = c_{ij}) for all occupied cells, taking (u_1 = 0), and solve for all (u_i) and (v_j).
2. Compute the opportunity cost (net evaluation) (d_{ij} = c_{ij} - (u_i + v_j)) for every unoccupied cell.
3. If all (d_{ij} \ge 0), the solution is optimal. If any (d_{ij} < 0), the solution can be improved.

Step 5: Improve the solution (if not optimal)

1. Select the unoccupied cell with the most negative (d_{ij}) as the entering cell.
2. Draw a closed loop (stepping-stone path) starting and ending at this cell, with right-angle turns only at occupied cells.
3. Assign (+) and (-) signs alternately along the loop, starting with (+) at the entering cell.
4. Find the minimum allocation among the cells marked (-). This is the quantity to be shifted.
5. Add this quantity to (+) cells and subtract it from (-) cells. The entering cell becomes occupied and one of the (-) cells becomes empty.
6. This gives a new basic feasible solution with the same number of occupied cells.

Step 6: Repeat until optimality is reached

Repeat Steps 4 and 5 for the new solution. Each iteration reduces (or keeps equal) the total cost. Continue until all opportunity costs (d_{ij} \ge 0). The resulting solution is the optimal solution, and the corresponding value of (Z) is the minimum transportation cost.

Step 7: Interpret the result

Read the final allocations (x_{ij}) from the table, compute the total cost, and interpret it in terms of the actual problem (how many units to ship from each source to each destination).

---

Note: For a maximisation-type transportation problem, first convert it into a minimisation problem by subtracting all costs from the largest cost in the table (or by using profit as negative cost), then follow the same steps.