Objective of Linear Programming

Linear programming (LP) is a mathematical technique used to find the best possible outcome (maximum profit or minimum cost) in a problem where both the objective and the constraints are linear. Its main objectives are:

1. Optimal resource allocation — To allocate limited resources (money, labour, machines, raw materials, time) among competing activities in the most efficient way.

2. Maximisation of profit or contribution — To determine the product mix or activity levels that yield the highest possible profit or total contribution, subject to given limitations.

3. Minimisation of cost — To find the least-cost combination of inputs, transportation routes, or production plans that still satisfies all requirements.

4. Optimal decision-making — To provide a scientific, quantitative basis for managerial decisions instead of relying on intuition or trial and error.

5. Efficient use of scarce resources — To identify which resources are fully utilised (binding constraints) and which are in surplus, so that capacity can be adjusted accordingly.

6. Feasible solution selection — Among all feasible solutions satisfying the constraints, to select the one that optimises the objective function.

In short, the objective of linear programming is to optimise (maximise or minimise) a linear objective function subject to a set of linear constraints, thereby giving the best possible use of limited resources.

For a maximisation primal, the dual is a minimisation problem. Each primal constraint gives one dual variable, and each primal variable gives one dual constraint.

Rules used

• $\le$ constraint: dual variable $Y_1 \ge 0$
• $\ge$ constraint: dual variable $Y_2 \le 0$
• $=$ constraint: dual variable $Y_3$ unrestricted in sign
• All primal variables are $\ge 0$, so every dual constraint is of the $\ge$ type
• Dual objective coefficients are the primal right-hand sides; dual right-hand sides are the primal objective coefficients

Dual problem

$\text{Min } Z^* = 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$

where $Y_1 \ge 0$, $Y_2 \le 0$, and $Y_3$ is unrestricted in sign.

(Equivalently, if the $\ge$ constraint is first multiplied by $-1$ to make it $\le$, the corresponding dual variable becomes non-negative.)

Dual problem

Minimize (W = \text{Rs. } 800Y_1 + \text{Rs. } 1000Y_2 + \text{Rs. } 1500Y_3)

Subject to

[ 2Y_1 + 0Y_2 + 3Y_3 \ge 30 ]

[ 3Y_1 + 2Y_2 + 2Y_3 \ge 50 ]

[ 0Y_1 + 5Y_2 + 4Y_3 \ge 40 ]

and (Y_1, Y_2, Y_3 \ge 0)

Working (rules used)

• Primal is a maximization problem with all (\le) constraints, so the dual is a minimization problem with all (\ge) constraints.
• Number of dual variables = number of primal constraints = 3, so (Y_1, Y_2, Y_3).
• Number of dual constraints = number of primal variables = 3, so one constraint each for (X_1, X_2, X_3).
• Coefficients of the dual constraints are the columns of the primal constraint matrix, and the right-hand sides are the primal objective coefficients (30, 50, 40).
• The dual objective coefficients are the primal right-hand sides (800, 1000, 1500).
• Since the primal variables are non-negative, the dual constraints are inequalities ((\ge)); since the primal constraints are inequalities, the dual variables are non-negative.

CPM vs PERT

CPM (Critical Path Method) and PERT (Program Evaluation and Review Technique) are both network-based project scheduling techniques, but they differ in the following basic ways:

In short: CPM is used when activity times are known with certainty and the aim is to minimise time and cost, whereas PERT is used when activity times are uncertain and the aim is to estimate the probability of completing the project within a specified time.

Sequencing Problem

A sequencing problem is a type of operations research problem in which we have to determine the order (sequence) in which a number of jobs are to be processed on a number of machines so that some measure of performance is optimised. In practice, a job may have to pass through several machines in a fixed technological order, and each machine can process only one job at a time. The objective is usually to minimise the total elapsed time (makespan), the total idle time of machines, or the total waiting time of jobs. A very common case is the n jobs on 2 machines problem, solved by Johnson's rule.

Assumptions of the Sequencing Problem

1. No job can be processed on more than one machine at a time, and no machine can process more than one job at a time.
2. The processing times of each job on each machine are known and constant (deterministic).
3. The order of processing of each job on the machines is fixed and known in advance (technological order).
4. Machines are available throughout the period, i.e., there are no breakdowns.
5. Jobs are independent of one another and are available at the start (no job arrives late).
6. Pre-emption is not allowed — once a job starts on a machine, it must be completed without interruption.
7. No passing is allowed — each job must pass through the machines in the same order.
8. The setup, transportation, and inspection times are either negligible or included in the processing times.
9. The objective is to find the sequence that minimises the total elapsed time (or total idle time).

Given:

• Annual demand, $D = 100$ units/year
• Storage cost, $C_h = Rs.\ 6$ per unit per year
• Set-up cost per run, $C_o = Rs.\ 40$
• Shortages are not allowed.

Formula: For optimum run size (EOQ), $Q^*=\sqrt{\frac{2DC_o}{C_h}}$

Minimum average yearly cost: $TC_{\min}=\sqrt{2DC_oC_h}$

Calculation: $Q^*=\sqrt{\frac{2\times100\times40}{6}}$ $Q^*=\sqrt{\frac{8000}{6}}=\sqrt{1333.33}=36.51\text{ units}$

$TC_{\min}=\sqrt{2\times100\times40\times6}$ $TC_{\min}=\sqrt{48000}=Rs.\ 219.09$

Result:

• Optimum run size, $Q^* = 36.51$ units per run (approximately 37 units)
• Minimum average yearly cost = Rs. 219.09

This is an assignment problem (4 jobs, 4 contractors, minimisation), solved by the Hungarian method. Costs are in Rs lakh.

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

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

Step 3: Cover the zeros. Row a, column 2 and column 3 cover all zeros: only 3 lines, fewer than 4, so a complete zero assignment is not yet possible. The smallest uncovered element is 1. Subtract 1 from every uncovered element and add 1 where two lines cross.

Row a, row c and column 3 again cover all zeros (3 lines). The smallest uncovered element is 2. Subtract 2 from the uncovered elements and add 2 at the crossings.

Step 4: Assignment. Now at least 4 lines are needed, so an optimal assignment exists on the zeros: contractor 4 has a zero only in row a, so a-4 is forced; then b-1, c-2, d-3.

$\text{Minimum total cost} = 9 + 24 + 28 + 10 = \text{Rs } 71 \text{ lakh}$

Other assignments with the same total exist, for example a-4, b-2, c-1, d-3 (9 + 22 + 30 + 10 = 71).

Network diagram

flowchart LR
  n1((1)) -->|4| n2((2))
  n1 -->|6| n3((3))
  n2 -->|8| n6((6))
  n3 -->|7| n4((4))
  n3 -->|4| n5((5))
  n4 -->|6| n6
  n5 -->|5| n6
  n5 -->|19| n7((7))
  n6 -->|10| n7

Event times

Activity times

EST = earliest start time, EFT = earliest finish time
LST = latest start time, LFT = latest finish time

Critical paths and critical activities

There are two critical paths:

1. (1-3-4-6-7)
   Duration (= 6+7+6+10 = 29) days

2. (1-3-5-7)
   Duration (= 6+4+19 = 29) days

Therefore, the critical activities are:

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

Project completion time:

[ \boxed{29 \text{ days}} ]

Activity (5-6) is not critical; it has a total float of 4 days.

Let
(x) = number of units of product A
(y) = number of units of product B

1. Formulation of LPP

Maximize profit: [ Z=40x+35y ]

Subject to raw material and labour constraints: [ 2x+3y\le 60 ] [ 4x+3y\le 96 ] [ x\ge 0,\quad y\ge 0 ]

2. Standard form

Introduce slack variables (s_1) and (s_2):

[ 2x+3y+s_1=60 ] [ 4x+3y+s_2=96 ] [ Z-40x-35y=0 ]

3. Simplex tableaus

Initial tableau:

Entering variable: (x)
Leaving variable: (s_2)
Pivot element: (4)

First iteration:

Entering variable: (y)
Leaving variable: (s_1)
Pivot element: (\frac32)

Second iteration:

Since all coefficients in the (Z)-row are non-negative, the optimal solution is reached.

4. Optimal solution

[ x=18,\qquad y=8 ]

Maximum profit: [ Z=40(18)+35(8) ] [ Z=720+280=1000 ]

[ \boxed{\text{Product A}=18\text{ units},\quad \text{Product B}=8\text{ units},\quad \text{Maximum profit}=Rs.\ 1000} ]

Verification: [ 2(18)+3(8)=36+24=60 ] [ 4(18)+3(8)=72+24=96 ]

Both resources are fully used at the optimum.

Given data. Supply: X = 55, Y = 25, Z = 35 (total 115). Demand: A = 35, B = 45, C = 35 (total 115). Supply equals demand, so the problem is balanced.

The entry Z to C (printed 524) is expensive in any reading (it may be a misprint for 24 or 54), and the optimal plan below never uses that route, so the answer does not depend on it.

Step 1: Initial solution by Vogel's Approximation Method

Column A has the largest penalty (the gap between its two smallest costs, 54 - 16, is 38). Allocate Y to A = 25 (Y is exhausted; A needs 10 more).

With X and Z left, column B has the largest penalty (58 - 16 = 42). Allocate Z to B = 35 (Z is exhausted; B needs 10 more).

X must then supply the rest: X to A = 10, X to B = 10, X to C = 35.

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

Step 2: Optimality test (MODI)

The 5 occupied cells equal $m + n - 1 = 5$. Put $u_X = 0$: $v_A = 54$, $v_B = 58$, $v_C = 58$, $u_Y = 16 - 54 = -38$, $u_Z = 16 - 58 = -42$.

For empty cells, $\Delta_{ij} = c_{ij} - u_i - v_j$:

• Y to B: $24 + 38 - 58 = 4$
• Y to C: $16 + 38 - 58 = -4$ (negative, so improve)
• Z to A: $58 + 42 - 54 = 46$
• Z to C: positive in every reading of the misprint

Step 3: Improvement. Enter Y to C with the loop Y-C (+), X-C (-), X-A (+), Y-A (-). The shift is $\theta = \min(35, 25) = 25$.

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

• Y to A: $16 + 42 - 54 = 4$
• Y to B: $24 + 42 - 58 = 8$
• Z to A: $58 + 42 - 54 = 46$
• Z to C: $524 + 42 - 58 = 508$ (still positive for 24 or 54 as well)

All $\Delta_{ij} \ge 0$, so the solution is optimal.

Optimal 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$

I. Network and expected project completion time

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

Network. Event 1 is the start and event 6 is the finish. Events and the activities leaving them:

Activity 2-6 goes straight from event 2 to the finish event 6.

Paths from 1 to 6

The longest path, 1-3-4-5-6, is the critical path, so the expected project duration is $T_e = 36$ days.

Variance along the critical path:

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

II. Probability of taking 5 days more than expected

Time considered: $36 + 5 = 41$ days.

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

$P(T > 41) = P(Z > 1.336) = 1 - 0.9092 \approx 0.0908$

The probability is about 9.08%.

III. Completion time with 95% confidence

For 95% confidence $Z = 1.645$:

$T = T_e + Z\sigma = 36 + 1.645(3.742) = 36 + 6.15 \approx 42.15 \text{ days}$

The project should be planned for about 42.15 days to be 95% sure of finishing on time.

"Operation search" in this question refers to Operations Research (OR), the scientific, quantitative approach to decision-making in organisations. The objectives of Operations Research are:

1. To find the optimal solution. Select the best course of action (maximum profit or minimum cost) from all feasible alternatives.
2. To improve decision-making. Give managers quantitative, objective information in place of guesswork or intuition.
3. To provide a systematic, scientific procedure. Define the problem, build a mathematical model, solve it, test it and implement it, replacing trial and error.
4. To reduce cost and time. Make the best use of men, machines, materials and money so that waste is minimised.
5. To handle complex problems with many interrelated variables. Take the whole system (production, marketing, finance, personnel) into account rather than a single department.
6. To allocate scarce resources efficiently. Methods such as linear programming, transportation, assignment, PERT/CPM and queuing support this.
7. To improve productivity and control. Help managers plan, schedule and monitor operations so that organisational goals are achieved.

In short, OR aims to give the management of an organisation a scientific basis for choosing the optimal solution under limited resources.

Given:

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

a) Optimal order size (EOQ)

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

[ EOQ=\sqrt{\frac{2 \times 10{,}400 \times 6}{3}} ]

[ EOQ=\sqrt{41{,}600}=203.96 \approx 204 \text{ packages} ]

Optimal order size = 204 packages per order.

---

b) Total annual cost of carrying and holding paper

At EOQ, annual carrying cost equals annual ordering cost.

Annual carrying cost:

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

Annual ordering cost:

[ \frac{D}{Q}S = \frac{10{,}400}{204} \times 6 = Rs.,305.88 ]

Total annual inventory cost:

[ Rs.,306 + Rs.,305.88 = Rs.,611.88 \approx Rs.,612 ]

Total annual cost of carrying and holding paper = Rs. 611.88 (approximately Rs. 612).

This is a balanced transportation problem (total supply = total demand = 55). We need a basic feasible solution with minimum cost.

Basic feasible solution

Here $m + n - 1 = 3 + 4 - 1 = 6$ basic cells are needed, and the two zero allocations ($O_1D_4$ and $O_3D_4$) are added so that the solution has the required 6 basic cells (it is a degenerate solution).

Optimality test (MODI). Take $u_{O_2} = 0$. From the basic cells:

• $O_2D_1$: $v_1 = 8$
• $O_2D_4$: $v_4 = 10$
• $O_1D_4$: $u_1 = 9 - 10 = -1$
• $O_1D_2$: $v_2 = 8 + 1 = 9$
• $O_3D_4$: $u_3 = 11 - 10 = 1$
• $O_3D_3$: $v_3 = 11 - 1 = 10$

Opportunity cost $\Delta_{ij} = c_{ij} - u_i - v_j$ for the empty cells:

All $\Delta_{ij} \ge 0$, so the solution is optimal (the zeros show that alternative optimal solutions exist).

Minimum cost

$Z = 15(8) + 15(8) + 10(10) + 15(11) = 120 + 120 + 100 + 165 = \text{Rs } 505$

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

Use the Hungarian method (minimisation).

Cost matrix

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

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

Step 3: Cover zeros. Row W, column J2 and column J3 cover every zero (W's zeros lie in J1 and J4). Only 3 lines are needed, which is less than 4, so the solution is not yet optimal. The smallest uncovered element is 1. Subtract 1 from the uncovered elements and add 1 at the crossings.

Row W, row X and column J3 cover all zeros again (3 lines). The smallest uncovered element is 2. Subtract 2 from the uncovered elements and add 2 at the crossings.

Step 4: Assignment. Four lines are now needed, so an optimal assignment exists. Y can only take J3, so Z takes J4; W then takes J1, and X takes J2.

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

Activity dependencies. In the printed table activity J lists "I, J" as predecessors, which is a misprint; J is taken to follow I only. Activity L follows K. J and L are therefore the last activities.

PERT network (activity on arrow). Events are numbered 1 to 11 and no dummy activity is needed.

Event 1 is the start of the project and event 11 is its end.

Forward and backward pass

Critical path. Activities with zero float are B, E, G, H, I and J:

$B \to E \to G \to H \to I \to J, \qquad 2 + 4 + 6 + 3 + 3 + 5 = 23 \text{ days}$

The project duration is 23 days.

Let
(x) = units of product X,
(y) = units of product Y,
(z) = units of product Z.

The linear programming model is:

[ \text{Maximize } 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 ]

Introduce slack variables (s_1,s_2,s_3):

[ x+2y+z+s_1=36 ]

[ 2x+y+4z+s_2=60 ]

[ 2x+5y+z+s_3=45 ]

Using the simplex method:

Initial simplex tableau

Enter (z), pivot row (s_2).

First iteration

Enter (x), pivot row (s_3).

Final simplex tableau

Since all coefficients in the objective row are non-negative, the optimal solution is reached.

[ x=20,\qquad y=0,\qquad z=5 ]

Maximum profit:

[ P=40(20)+25(0)+50(5) ]

[ P=800+0+250=1050 ]

Therefore, the optimum product mix is:

[ \boxed{\text{Produce 20 units of X, 0 units of Y and 5 units of Z}} ]

[ \boxed{\text{Maximum total profit} = \text{Rs. }1050} ]

Raw material B and C are fully used, while 11 units of raw material A remain unused.

Check for Johnson's rule with three machines. The rule applies if the smallest time on machine A is at least the largest time on machine B (or the smallest on C is at least the largest on B).

$\min A = 5 \ge \max B = 5$

so the condition holds. Form two fictitious machines $G = A + B$ and $H = B + C$:

Johnson's rule. Pick the smallest time; if it is in $G$, place the job as early as possible, and if it is in $H$, as late as possible.

• Smallest is 5 (Job 1, in $H$): last.
• Next smallest is 8 (Job 2, in $G$): first. Job 5 ($G = 8$) goes second.
• Next is 9 (Job 3, in $H$): last of the remaining places. Then Job 4 takes the middle.

Optimal sequence: 2 - 5 - 4 - 3 - 1

Time table (hours)

Minimum total elapsed time = 41 hours.

Idle time (over the 41-hour period):

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

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 points) to several destinations (demand points) so as to minimise the total transportation cost. The standard steps are as follows:

Step 1: Formulate the problem

• Identify the number of sources (supply centres) and destinations (demand centres).
• Prepare the transportation cost matrix showing the cost of transporting one unit from each source to each destination.
• Write down the supply available at each source and the demand required at each destination.

Step 2: Check the balance condition

Compare total supply with total demand:

• If total supply = total demand, the problem is a balanced transportation problem.
• If they are unequal, the problem is unbalanced. Add a dummy row (if demand exceeds supply) or a dummy column (if supply exceeds demand) with zero transportation cost to make it balanced.

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 the minimum of supply and demand, moving right or down.
2. Least Cost Method (LCM) — allocate to the cell having the smallest cost in the whole table, then eliminate the satisfied row or column.
3. Vogel's Approximation Method (VAM) — compute the penalty (difference between the two smallest costs) for each row and column, select the row/column with the largest penalty, and allocate to its least-cost cell. VAM usually gives the best initial solution.

Step 4: Test the optimality of the initial solution

Check whether the solution is optimal by using:

1. Stepping Stone Method — trace closed loops for empty cells and compute the net cost change (opportunity cost).
2. Modified Distribution (MODI) Method / u–v method — find dual variables (u_i) and (v_j) using (u_i + v_j = c_{ij}) for occupied cells, then compute the opportunity cost (c_{ij} - (u_i + v_j)) for every empty cell.

Step 5: Improve the solution (if not optimal)

• If any opportunity cost is negative, the solution is not optimal.
• Select the cell with the most negative opportunity cost, draw a closed loop, and shift the maximum possible quantity to that cell (alternating + and − at the corners of the loop).
• This gives a new, improved basic feasible solution.

Step 6: Repeat until optimality is reached

Repeat Steps 4 and 5 until all opportunity costs are zero or positive. The resulting solution is the optimal solution.

Step 7: Compute the minimum total cost

Multiply the allocated quantity in each occupied cell by its unit transportation cost and add all such products:

[ \text{Minimum total cost} = \sum_{i}\sum_{j} c_{ij},x_{ij} ]

---

Note: For an (m \times n) transportation problem, a basic feasible solution must have exactly (m + n - 1) occupied cells. If the number of occupied cells is less than (m + n - 1), the solution is degenerate, and a zero allocation must be placed in an independent empty cell to proceed with the MODI method.