● QT MIDTERM
πŸ” /
QUANTITATIVE TECHNIQUESβ€ΊREVISIONβ€ΊPRACTICE PROBLEMS

Practice Problems

Extra problems per topic, each with a twist the past papers did not use β€” solved one step per line. Work the question yourself first, then compare.

HOW TO USE THIS PAGE

Every solution is broken into numbered steps, and every step shows one line of working at a time. Nothing is compressed onto a single line, because that is where mistakes hide. Where a problem has a deliberate twist β€” a ratio constraint, a tie in the ratio test, an out-of-range RHS β€” it is flagged so you can spot the pattern next time.

A Β· LPP Formulation Unit 1

A1 β€” Two products with an extra market limit

A furniture firm makes desks and bookshelves. A desk needs 6 hours machining and 4 hours polishing; a bookshelf needs 3 hours machining and 5 hours polishing. Weekly capacity is 180 machining hours and 200 polishing hours. Profit is β‚Ή500 per desk and β‚Ή350 per bookshelf. The firm can sell at most 25 desks a week. Formulate the LPP.

  1. Step 1 β€” Build the resource table
    ResourceDesk (X₁)Bookshelf (Xβ‚‚)Available
    Machining (hrs)63180
    Polishing (hrs)45200
    Profit (β‚Ή/unit)500350maximise
  2. Step 2 β€” Decision variables Let X₁ = number of desks produced per week Let Xβ‚‚ = number of bookshelves produced per week
  3. Step 3 β€” Objective function Max Z = 500X₁ + 350Xβ‚‚ ← total weekly profit in β‚Ή
  4. Step 4 β€” Constraints, one per row of the table 6X₁ + 3Xβ‚‚ ≀ 180 ← machining hours 4X₁ + 5Xβ‚‚ ≀ 200 ← polishing hours X₁ ≀ 25 ← market limit on desks
  5. Step 5 β€” Non-negativity X₁, Xβ‚‚ β‰₯ 0
The twist: "can sell at most 25 desks" is a single-variable constraint β€” it uses only X₁. Students often try to force it into the resource table and lose it. Write it as its own labelled line.

A2 β€” A minimisation (feed mix) problem

A poultry farmer mixes two feeds. Feed A costs β‚Ή12/kg and supplies 40 units of protein and 20 units of fat per kg. Feed B costs β‚Ή8/kg and supplies 25 units of protein and 30 units of fat per kg. The daily mix must supply at least 2000 units of protein and at least 1200 units of fat. Formulate to minimise cost.

  1. Step 1 β€” Spot the direction from the wording

    "Costs" + "minimise" ⟹ Min objective. "At least" ⟹ β‰₯ constraints. This is the mirror image of A1.

  2. Step 2 β€” Decision variables Let X₁ = kg of Feed A used per day Let Xβ‚‚ = kg of Feed B used per day
  3. Step 3 β€” Objective function Min Z = 12X₁ + 8Xβ‚‚ ← total daily feed cost in β‚Ή
  4. Step 4 β€” Constraints 40X₁ + 25Xβ‚‚ β‰₯ 2000 ← protein requirement 20X₁ + 30Xβ‚‚ β‰₯ 1200 ← fat requirement
  5. Step 5 β€” Non-negativity X₁, Xβ‚‚ β‰₯ 0

A3 β€” A ratio constraint (portfolio)

An investor has β‚Ή10 lakh. Bonds return 8% and equity returns 14%. At most 60% of the amount invested may go into equity, and at least β‚Ή2 lakh must go into bonds. Formulate to maximise return.

  1. Step 1 β€” Decision variables Let X₁ = β‚Ή lakh invested in bonds Let Xβ‚‚ = β‚Ή lakh invested in equity
  2. Step 2 β€” Objective function Max Z = 0.08X₁ + 0.14Xβ‚‚ ← annual return in β‚Ή lakh
  3. Step 3 β€” Fund and minimum constraints X₁ + Xβ‚‚ ≀ 10 ← total funds available X₁ β‰₯ 2 ← minimum in bonds
  4. Step 4 β€” Turn the percentage into a linear constraint

    "At most 60% of the amount invested" means equity ≀ 0.6 Γ— (total invested):

    Xβ‚‚ ≀ 0.6 (X₁ + Xβ‚‚) Xβ‚‚ ≀ 0.6X₁ + 0.6Xβ‚‚ Xβ‚‚ βˆ’ 0.6Xβ‚‚ ≀ 0.6X₁ 0.4Xβ‚‚ βˆ’ 0.6X₁ ≀ 0 βˆ’0.6X₁ + 0.4Xβ‚‚ ≀ 0 ← the equity-share constraint
  5. Step 5 β€” Non-negativity X₁, Xβ‚‚ β‰₯ 0
⚠ The trap in every percentage constraint

If the question had said "at most 60% of the β‚Ή10 lakh", the constraint would simply be Xβ‚‚ ≀ 6. It says "of the amount invested", which may be less than 10 β€” so the fraction is of (X₁ + Xβ‚‚) and must be rearranged. Read whether the percentage is of a fixed total or of a variable total. If ambiguous, state which reading you took.

A4 β€” Three variables with a proportionality link

A workshop makes items A, B and C. Time per unit on Machine I is 2, 3 and 1 hours; on Machine II it is 4, 1 and 2 hours. Machine I has 100 hours available, Machine II has 120. Profit is β‚Ή30, β‚Ή20 and β‚Ή25 per unit. Production of C must be at least twice that of A. Formulate.

  1. Step 1 β€” Decision variables Let X₁ = units of A, Xβ‚‚ = units of B, X₃ = units of C
  2. Step 2 β€” Objective function Max Z = 30X₁ + 20Xβ‚‚ + 25X₃
  3. Step 3 β€” Machine constraints 2X₁ + 3Xβ‚‚ + 1X₃ ≀ 100 ← Machine I hours 4X₁ + 1Xβ‚‚ + 2X₃ ≀ 120 ← Machine II hours
  4. Step 4 β€” Rearrange the linking condition

    Every constraint must have all variables on the left and a constant on the right:

    X₃ β‰₯ 2X₁ βˆ’2X₁ + X₃ β‰₯ 0 ← production-mix constraint
  5. Step 5 β€” Non-negativity X₁, Xβ‚‚, X₃ β‰₯ 0

A5 β€” Two plants meeting one demand

A company produces a chemical at two plants. Plant 1 costs β‚Ή15,000 per thousand litres and can make at most 12 thousand litres; Plant 2 costs β‚Ή18,000 per thousand litres and can make at most 9 thousand litres. Total production must be at least 16 thousand litres. Formulate to minimise cost.

  1. Step 1 β€” Decision variables (note the unit!) Let X₁ = thousand litres produced at Plant 1 Let Xβ‚‚ = thousand litres produced at Plant 2
  2. Step 2 β€” Objective function Min Z = 15000X₁ + 18000Xβ‚‚ ← total production cost in β‚Ή
  3. Step 3 β€” Capacity constraints (≀, one per plant) X₁ ≀ 12 ← Plant 1 capacity Xβ‚‚ ≀ 9 ← Plant 2 capacity
  4. Step 4 β€” Demand constraint (β‰₯, because it is a requirement) X₁ + Xβ‚‚ β‰₯ 16 ← minimum total production
  5. Step 5 β€” Non-negativity X₁, Xβ‚‚ β‰₯ 0
Why the units matter: the cost is quoted "per thousand litres", so the variable must also be in thousand litres. Define X₁ as "litres" and your objective is off by a factor of 1000. Always copy the unit from the cost figure into the variable definition.

B Β· Graphical Method Unit 1 Β· numerical

B1 β€” Standard maximisation

Max Z = 5X₁ + 4Xβ‚‚ s.t. 6X₁ + 4Xβ‚‚ ≀ 24 X₁ + 2Xβ‚‚ ≀ 6 X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Convert to equations and find two points on each line
    LineSet X₁ = 0Set Xβ‚‚ = 0
    6X₁ + 4Xβ‚‚ = 24Xβ‚‚ = 6 β†’ (0, 6)X₁ = 4 β†’ (4, 0)
    X₁ + 2Xβ‚‚ = 6Xβ‚‚ = 3 β†’ (0, 3)X₁ = 6 β†’ (6, 0)
  2. Step 2 β€” Find the intersection by solving the pair simultaneously 6X₁ + 4Xβ‚‚ = 24 …(i) X₁ + 2Xβ‚‚ = 6 …(ii) Multiply (ii) by 2: 2X₁ + 4Xβ‚‚ = 12 …(iii) (i) βˆ’ (iii): 4X₁ = 12 X₁ = 3 Substitute in (ii): 3 + 2Xβ‚‚ = 6 β†’ Xβ‚‚ = 1.5 Intersection point B = (3, 1.5)
  3. Step 3 β€” List the corner points of the feasible region O (0, 0) A (0, 3) B (3, 1.5) C (4, 0)

    A is (0,3) not (0,6), because (0,6) violates X₁ + 2Xβ‚‚ ≀ 6. Always test a candidate corner in every constraint before accepting it.

  4. Step 4 β€” Evaluate Z at every corner point
    Corner(X₁, Xβ‚‚)Z = 5X₁ + 4Xβ‚‚
    O(0, 0)0
    A(0, 3)5(0) + 4(3) = 12
    B(3, 1.5)5(3) + 4(1.5) = 21
    C(4, 0)5(4) + 4(0) = 20
  5. Step 5 β€” State the answer in full X₁ = 3, Xβ‚‚ = 1.5, Max Z = 21
Cross-check: problem D1 solves this same LPP by the simplex method and reaches X₁ = 3, Xβ‚‚ = 1.5, Z = 21. If your two methods disagree, one of them has an arithmetic error.

B2 β€” Minimisation with an unbounded feasible region

Min Z = 6X₁ + 10Xβ‚‚ s.t. 2X₁ + 5Xβ‚‚ β‰₯ 20 3X₁ + Xβ‚‚ β‰₯ 15 X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Intercepts
    LineSet X₁ = 0Set Xβ‚‚ = 0
    2X₁ + 5Xβ‚‚ = 20(0, 4)(10, 0)
    3X₁ + Xβ‚‚ = 15(0, 15)(5, 0)
  2. Step 2 β€” Intersection From 3X₁ + Xβ‚‚ = 15 β†’ Xβ‚‚ = 15 βˆ’ 3X₁ Substitute: 2X₁ + 5(15 βˆ’ 3X₁) = 20 2X₁ + 75 βˆ’ 15X₁ = 20 βˆ’13X₁ = βˆ’55 X₁ = 55/13 β‰ˆ 4.23 Xβ‚‚ = 15 βˆ’ 3(55/13) = (195 βˆ’ 165)/13 = 30/13 β‰ˆ 2.31 Intersection = (55/13, 30/13) β‰ˆ (4.23, 2.31)
  3. Step 3 β€” Identify the corner points

    Both constraints are β‰₯, so the feasible region lies away from the origin and is unbounded above. Its corner points are where the boundary turns:

    (0, 15) (55/13, 30/13) (10, 0)
  4. Step 4 β€” Evaluate Z
    CornerZ = 6X₁ + 10Xβ‚‚Value
    (0, 15)6(0) + 10(15)150
    (55/13, 30/13)(330 + 300)/13 = 630/13β‰ˆ 48.46
    (10, 0)6(10) + 10(0)60
  5. Step 5 β€” Answer X₁ β‰ˆ 4.23, Xβ‚‚ β‰ˆ 2.31, Min Z β‰ˆ 48.46
⚠ Unbounded region β‰  unbounded solution

The feasible region here goes on for ever upward and to the right β€” but because we are minimising, the optimum sits at a finite corner. An unbounded region only produces an unbounded solution when the objective improves in the direction the region is open. Say this explicitly if a question asks whether the answer is valid.

B3 β€” Multiple optimal solutions

Max Z = 4X₁ + 6Xβ‚‚ s.t. 2X₁ + 3Xβ‚‚ ≀ 12 X₁ ≀ 4 , Xβ‚‚ ≀ 3 X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Notice the slopes before you plot Objective: 4X₁ + 6Xβ‚‚ β†’ ratio 4 : 6 = 2 : 3 Constraint: 2X₁ + 3Xβ‚‚ β†’ ratio 2 : 3 Same ratio ⟹ the objective line is PARALLEL to constraint 1

    That is the signature of multiple optimal solutions. Spotting it here saves you from being surprised at step 4.

  2. Step 2 β€” Corner points Xβ‚‚ = 3 meets 2X₁ + 3Xβ‚‚ = 12: 2X₁ + 9 = 12 β†’ X₁ = 1.5 β†’ (1.5, 3) X₁ = 4 meets 2X₁ + 3Xβ‚‚ = 12: 8 + 3Xβ‚‚ = 12 β†’ Xβ‚‚ = 4/3 β†’ (4, 4/3) Corners: O(0,0), (0,3), (1.5,3), (4, 4/3), (4,0)
  3. Step 3 β€” Evaluate Z
    CornerZ = 4X₁ + 6Xβ‚‚
    (0, 3)0 + 18 = 18
    (1.5, 3)6 + 18 = 24
    (4, 4/3)16 + 8 = 24
    (4, 0)16 + 0 = 16
  4. Step 4 β€” State the answer as a set, not a point Two corner points both give Z = 24 Every point on the segment joining (1.5, 3) and (4, 4/3) is optimal, with Max Z = 24

    Management implication: the firm can pick whichever of those production plans it prefers on other grounds β€” the profit is identical.

B4 β€” Three constraints, from the lecture deck

Weekly production cannot exceed 25 units of P1 or 35 units of P2. The company employs 60 worker-weeks; P1 needs 2 weeks of labour, P2 needs 1. Profit β‚Ή60 on P1, β‚Ή40 on P2. (Graphical deck p. 2)

  1. Step 1 β€” Formulate Let X₁ = units of P1, Xβ‚‚ = units of P2 Max Z = 60X₁ + 40Xβ‚‚ X₁ ≀ 25 ← P1 production limit Xβ‚‚ ≀ 35 ← P2 production limit 2X₁ + Xβ‚‚ ≀ 60 ← labour, worker-weeks
  2. Step 2 β€” Corner points (solve each intersecting pair) Xβ‚‚ = 35 meets 2X₁ + Xβ‚‚ = 60: 2X₁ = 25 β†’ X₁ = 12.5 β†’ E (12.5, 35) X₁ = 25 meets 2X₁ + Xβ‚‚ = 60: Xβ‚‚ = 60 βˆ’ 50 = 10 β†’ G (25, 10) Corners: O(0,0), A(0,35), E(12.5,35), G(25,10), C(25,0)
  3. Step 3 β€” Evaluate Z
    CornerZ = 60X₁ + 40Xβ‚‚Value
    A (0, 35)0 + 1400β‚Ή1,400
    E (12.5, 35)750 + 1400β‚Ή2,150
    G (25, 10)1500 + 400β‚Ή1,900
    C (25, 0)1500 + 0β‚Ή1,500
  4. Step 4 β€” Answer X₁ = 12.5, Xβ‚‚ = 35, Max Z = β‚Ή2,150

    A fractional answer (12.5 units) is acceptable in an LP. If the question insisted on whole units, it would be an ILP instead β€” that is precisely the divisibility assumption at work.

C Β· Simplex Method Unit 1 Β· numerical

C1 β€” Full simplex, all iterations

Max Z = 5X₁ + 4Xβ‚‚ s.t. 6X₁ + 4Xβ‚‚ ≀ 24 X₁ + 2Xβ‚‚ ≀ 6 X₁, Xβ‚‚ β‰₯ 0

The same LPP as B1 β€” so you can check the two methods against each other.

  1. Step 1 β€” Add slack variables to turn ≀ into = 6X₁ + 4Xβ‚‚ + S₁ = 24 X₁ + 2Xβ‚‚ + Sβ‚‚ = 6 Setting X₁ = Xβ‚‚ = 0 gives the starting basis: S₁ = 24, Sβ‚‚ = 6, Z = 0
  2. Step 2 β€” Iteration 1
    CBBasisbiX₁Xβ‚‚S₁Sβ‚‚Ratio
    Cj β†’5400
    0S₁24641024/6 = 4 ←
    0Sβ‚‚612016/1 = 6
    Zj00000
    Cj βˆ’ Zj5 ↑400
    Entering variable: X₁ (largest Cβ±Ό βˆ’ Zβ±Ό = 5) Leaving variable: S₁ (smallest positive ratio = 4) Pivot element = 6
  3. Step 3 β€” Build the new rows New R1 = Old R1 Γ· 6 β†’ b = 4, X₁ = 1, Xβ‚‚ = 2/3, S₁ = 1/6, Sβ‚‚ = 0 New R2 = Old R2 βˆ’ (1 Γ— New R1) β†’ b = 6 βˆ’ 4 = 2, X₁ = 0, Xβ‚‚ = 2 βˆ’ 2/3 = 4/3, S₁ = βˆ’1/6, Sβ‚‚ = 1
  4. Step 4 β€” Iteration 2
    CBBasisbiX₁Xβ‚‚S₁Sβ‚‚Ratio
    5X₁412/31/604 Γ· 2/3 = 6
    0Sβ‚‚204/3βˆ’1/612 Γ· 4/3 = 1.5 ←
    Zj20510/35/60
    Cj βˆ’ Zj02/3 β†‘βˆ’5/60
    Cβ±Ό βˆ’ Zβ±Ό for Xβ‚‚ = 4 βˆ’ 10/3 = 2/3 > 0 ⟹ not yet optimal Entering: Xβ‚‚ ; Leaving: Sβ‚‚ ; Pivot element = 4/3
  5. Step 5 β€” Build the new rows again New R2 = Old R2 Γ· (4/3) β†’ b = 1.5, X₁ = 0, Xβ‚‚ = 1, S₁ = βˆ’1/8, Sβ‚‚ = 3/4 New R1 = Old R1 βˆ’ (2/3 Γ— New R2) β†’ b = 4 βˆ’ 1 = 3 β†’ S₁ = 1/6 βˆ’ (2/3)(βˆ’1/8) = 1/6 + 1/12 = 1/4 β†’ Sβ‚‚ = 0 βˆ’ (2/3)(3/4) = βˆ’1/2
  6. Step 6 β€” Iteration 3 (optimal table)
    CBBasisbiX₁Xβ‚‚S₁Sβ‚‚
    5X₁3101/4βˆ’1/2
    4Xβ‚‚1.501βˆ’1/83/4
    Zj21543/41/2
    Cj βˆ’ Zj00βˆ’3/4βˆ’1/2
    All Cβ±Ό βˆ’ Zβ±Ό ≀ 0 ⟹ STOP, the table is optimal X₁ = 3, Xβ‚‚ = 1.5, Max Z = 21 βœ“ same as the graphical answer in B1

C2 β€” A simplex run that goes degenerate

Max Z = 3X₁ + 9Xβ‚‚ s.t. X₁ + 4Xβ‚‚ ≀ 8 X₁ + 2Xβ‚‚ ≀ 4 X₁, Xβ‚‚ β‰₯ 0

The degeneracy example from the Special Cases deck p. 1, run all the way through.

  1. Step 1 β€” Standard form X₁ + 4Xβ‚‚ + S₁ = 8 X₁ + 2Xβ‚‚ + Sβ‚‚ = 4
  2. Step 2 β€” Iteration 1: the ratio test ties
    CBBasisbiX₁Xβ‚‚S₁Sβ‚‚Ratio
    0S₁814108/4 = 2
    0Sβ‚‚412014/2 = 2
    Cj βˆ’ Zj39 ↑00
    Both ratios equal 2 β€” a TIE. This is what causes degeneracy. Break the tie arbitrarily: let S₁ leave. Pivot element = 4.
  3. Step 3 β€” Iteration 2: a basic variable hits zero New R1 = R1 Γ· 4 β†’ b = 2, X₁ = 1/4, Xβ‚‚ = 1, S₁ = 1/4, Sβ‚‚ = 0 New R2 = R2 βˆ’ 2(New R1) β†’ b = 4 βˆ’ 4 = 0, X₁ = 1/2, Xβ‚‚ = 0, S₁ = βˆ’1/2, Sβ‚‚ = 1
    CBBasisbiX₁Xβ‚‚S₁Sβ‚‚Ratio
    9Xβ‚‚21/411/402 Γ· 1/4 = 8
    0Sβ‚‚01/20βˆ’1/210 Γ· 1/2 = 0 ←
    Zj189/499/40
    Cj βˆ’ Zj3/4 ↑0βˆ’9/40
    Sβ‚‚ is BASIC with value 0 β€” this is a degenerate basic feasible solution.
  4. Step 4 β€” Iteration 3: a degenerate pivot, Z does not improve New R2 = R2 Γ· (1/2) β†’ b = 0, X₁ = 1, Xβ‚‚ = 0, S₁ = βˆ’1, Sβ‚‚ = 2 New R1 = R1 βˆ’ (1/4)(New R2) β†’ b = 2 βˆ’ 0 = 2, S₁ = 1/4 + 1/4 = 1/2, Sβ‚‚ = βˆ’1/2
    CBBasisbiX₁Xβ‚‚S₁Sβ‚‚
    9Xβ‚‚2011/2βˆ’1/2
    3X₁010βˆ’12
    Zj18393/23/2
    Cj βˆ’ Zj00βˆ’3/2βˆ’3/2
    Z stayed at 18 across the pivot β€” the hallmark of degeneracy.
  5. Step 5 β€” Answer, with the diagnosis All Cβ±Ό βˆ’ Zβ±Ό ≀ 0 ⟹ optimal X₁ = 0, Xβ‚‚ = 2, Max Z = 18 β€” a DEGENERATE optimal solution (X₁ is basic at zero)

    What to write: "The solution is degenerate because the basic variable X₁ has value zero. Degeneracy arose from the tie in the replacement ratios at iteration 1, and it caused a pivot that left Z unchanged at 18. Repeated degenerate pivots can cause cycling, which is prevented by anti-cycling rules such as Bland's Rule."

D Β· Special Case Identification Unit 1

Each of these gives you a tableau fragment and asks the Q7A question: which special case is this, what is your evidence, and what does it imply?

D1 β€” Multiple optimal solutions

CBBasisbiX₁Xβ‚‚S₁Sβ‚‚
Cj β†’4600
6Xβ‚‚32/311/30
0Sβ‚‚11/30βˆ’1/31
Zj184620
Cj βˆ’ Zj00βˆ’20
  1. Step 1 β€” Check optimality first All Cβ±Ό βˆ’ Zβ±Ό ≀ 0 ⟹ the table is optimal
  2. Step 2 β€” Look at which variables are basic Basic variables: Xβ‚‚ and Sβ‚‚ Non-basic variables: X₁ and S₁
  3. Step 3 β€” Find the tell-tale zero X₁ is NON-BASIC and its Cβ±Ό βˆ’ Zβ±Ό = 0 ⟹ MULTIPLE OPTIMAL SOLUTIONS
  4. Step 4 β€” State the implication

    X₁ can be brought into the basis without changing Z. There is therefore more than one optimal production plan, and every point on the line segment joining the two optimal corners is also optimal. Management can choose between them on non-cost grounds.

D2 β€” Unbounded solution

CBBasisbiX₁Xβ‚‚S₁Sβ‚‚Ratio
Cj β†’5400
5X₁710107 Γ· 0 = ∞
0Sβ‚‚10βˆ’1βˆ’111 Γ· (βˆ’1) = βˆ’1
Cj βˆ’ Zj04 β†‘βˆ’50
  1. Step 1 β€” Identify the entering variable Xβ‚‚ has Cβ±Ό βˆ’ Zβ±Ό = +4 > 0 ⟹ Xβ‚‚ should enter
  2. Step 2 β€” Do the ratio test Row X₁ : column entry = 0 β†’ ratio = ∞ Row Sβ‚‚ : column entry = βˆ’1 β†’ ratio = βˆ’1 (negative) NO positive replacement ratio exists ⟹ there is no leaving variable
  3. Step 3 β€” Diagnose and explain ⟹ UNBOUNDED SOLUTION

    Xβ‚‚ can be increased indefinitely without any constraint becoming binding, so Z grows without limit. Since no real business earns infinite profit, an unbounded solution always indicates that the problem has been formulated incorrectly β€” usually a missing constraint.

D3 β€” Infeasible solution

CBBasisbiX₁Xβ‚‚S₁A₁
Cj β†’200βˆ’3000βˆ’M
200X₁4001100
βˆ’MA₁10000.5βˆ’11
Cj βˆ’ Zj0≀ 0≀ 00
  1. Step 1 β€” Check the optimality condition All Cβ±Ό βˆ’ Zβ±Ό ≀ 0 ⟹ the simplex algorithm has terminated
  2. Step 2 β€” Look for artificial variables still in the basis A₁ is an ARTIFICIAL variable A₁ is BASIC, and its value is 100 β‰  0
  3. Step 3 β€” Diagnose ⟹ INFEASIBLE SOLUTION

    An artificial variable exists only to give the algorithm a starting basis; it has no physical meaning. If one remains in the basis at a non-zero value when optimality is reached, no point satisfies all the original constraints simultaneously β€” the constraints contradict one another.

  4. Step 4 β€” The distinction to state

    If an artificial variable remained basic at value zero, the solution would be feasible but degenerate, not infeasible. The non-zero value is what makes this infeasibility.

D4 β€” Degeneracy at optimality

CBBasisbiX₁Xβ‚‚S₁Sβ‚‚
Cj β†’3900
9Xβ‚‚2011/2βˆ’1/2
3X₁010βˆ’12
Cj βˆ’ Zj00βˆ’3/2βˆ’3/2
  1. Step 1 β€” Rule out multiple optima first Non-basic variables are S₁ and Sβ‚‚ Their Cβ±Ό βˆ’ Zβ±Ό are βˆ’3/2 and βˆ’3/2 β€” both STRICTLY negative ⟹ not multiple optima

    The zeros you see in the Cβ±Ό βˆ’ Zβ±Ό row sit under X₁ and Xβ‚‚, which are basic β€” a zero there is expected and means nothing.

  2. Step 2 β€” Look in the Quantity column X₁ is BASIC with value b = 0 ⟹ DEGENERATE optimal solution
  3. Step 3 β€” Implication

    Degeneracy can cause cycling β€” the algorithm pivots to a new basis but returns to one already visited, with no improvement in Z, and may loop indefinitely. Anti-cycling rules such as Bland's Rule prevent it.

The two-second check that separates D1 from D4: a zero in the Cβ±Ό βˆ’ Zβ±Ό row on a non-basic column ⟹ multiple optima. A zero in the Quantity column on a basic row ⟹ degenerate. Different row, different column, different answer.

E Β· Duality Unit 1

E1 β€” All constraints already ≀ (the easy case)

Max Z = 3X₁ + 5Xβ‚‚ s.t. X₁ ≀ 4 2Xβ‚‚ ≀ 12 3X₁ + 2Xβ‚‚ ≀ 18 X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Check canonical form Primal is Max, and all three constraints are already ≀ ⟹ nothing to convert
  2. Step 2 β€” Count the dual variables 3 primal constraints, no equalities ⟹ 3 dual variables Y₁, Yβ‚‚, Y₃
  3. Step 3 β€” Dual objective: Max β†’ Min, RHS becomes the coefficients Min W = 4Y₁ + 12Yβ‚‚ + 18Y₃
  4. Step 4 β€” One constraint per primal variable, reading DOWN its column X₁ column: 1, 0, 3 β†’ Y₁ + 3Y₃ β‰₯ 3 Xβ‚‚ column: 0, 2, 2 β†’ 2Yβ‚‚ + 2Y₃ β‰₯ 5
  5. Step 5 β€” Write the complete dual Min W = 4Y₁ + 12Yβ‚‚ + 18Y₃ s.t. Y₁ + 3Y₃ β‰₯ 3 2Yβ‚‚ + 2Y₃ β‰₯ 5 Y₁, Yβ‚‚, Y₃ β‰₯ 0

E2 β€” A Min primal (direction reverses)

Min Z = 10X₁ + 6Xβ‚‚ s.t. 2X₁ + Xβ‚‚ β‰₯ 8 X₁ + 3Xβ‚‚ β‰₯ 9 X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Canonical form for a Min problem is all β‰₯ Both constraints are already β‰₯ ⟹ nothing to convert
  2. Step 2 β€” Dual objective: Min β†’ Max Max W = 8Y₁ + 9Yβ‚‚
  3. Step 3 β€” Dual constraints are ≀ (opposite of the Max case) X₁ column: 2, 1 β†’ 2Y₁ + Yβ‚‚ ≀ 10 Xβ‚‚ column: 1, 3 β†’ Y₁ + 3Yβ‚‚ ≀ 6
  4. Step 4 β€” Complete dual Max W = 8Y₁ + 9Yβ‚‚ s.t. 2Y₁ + Yβ‚‚ ≀ 10 Y₁ + 3Yβ‚‚ ≀ 6 Y₁, Yβ‚‚ β‰₯ 0

E3 β€” A β‰₯ constraint inside a Max problem

Max Z = 4X₁ + 2Xβ‚‚ s.t. X₁ + Xβ‚‚ ≀ 10 X₁ βˆ’ Xβ‚‚ β‰₯ 2 ← wrong direction X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Fix the direction by multiplying by βˆ’1 X₁ βˆ’ Xβ‚‚ β‰₯ 2 Multiply the WHOLE row by βˆ’1 (coefficients and RHS): βˆ’X₁ + Xβ‚‚ ≀ βˆ’2
  2. Step 2 β€” The canonical primal
    ConstraintX₁Xβ‚‚RHSDual var
    C11110Y₁
    C2 (flipped)βˆ’11βˆ’2Yβ‚‚
  3. Step 3 β€” Dual objective (note the negative RHS carries through) Min W = 10Y₁ βˆ’ 2Yβ‚‚
  4. Step 4 β€” Dual constraints (β‰₯, one per primal variable) X₁ column: 1, βˆ’1 β†’ Y₁ βˆ’ Yβ‚‚ β‰₯ 4 Xβ‚‚ column: 1, 1 β†’ Y₁ + Yβ‚‚ β‰₯ 2
  5. Step 5 β€” Complete dual Min W = 10Y₁ βˆ’ 2Yβ‚‚ s.t. Y₁ βˆ’ Yβ‚‚ β‰₯ 4 Y₁ + Yβ‚‚ β‰₯ 2 Y₁, Yβ‚‚ β‰₯ 0

E4 β€” An equality constraint (splits into two dual variables)

Min Z = 2X₁ + 3Xβ‚‚ s.t. X₁ + Xβ‚‚ = 5 ← equality X₁ βˆ’ 2Xβ‚‚ β‰₯ 1 X₁, Xβ‚‚ β‰₯ 0
  1. Step 1 β€” Split the equality into two inequalities X₁ + Xβ‚‚ = 5 is the same as X₁ + Xβ‚‚ β‰₯ 5 AND X₁ + Xβ‚‚ ≀ 5
  2. Step 2 β€” Make every constraint β‰₯ (canonical for a Min primal) X₁ + Xβ‚‚ β‰₯ 5 β†’ Y₁ X₁ + Xβ‚‚ ≀ 5 β†’ Γ—(βˆ’1) β†’ βˆ’X₁ βˆ’ Xβ‚‚ β‰₯ βˆ’5 β†’ Yβ‚‚ X₁ βˆ’ 2Xβ‚‚ β‰₯ 1 β†’ Y₃ 2 printed constraints, but one is an equality ⟹ 3 dual variables
  3. Step 3 β€” Dual objective (Min β†’ Max) Max W = 5Y₁ βˆ’ 5Yβ‚‚ + Y₃
  4. Step 4 β€” Dual constraints, ≀, reading down each primal column X₁ column: 1, βˆ’1, 1 β†’ Y₁ βˆ’ Yβ‚‚ + Y₃ ≀ 2 Xβ‚‚ column: 1, βˆ’1, βˆ’2 β†’ Y₁ βˆ’ Yβ‚‚ βˆ’ 2Y₃ ≀ 3
  5. Step 5 β€” Complete dual Max W = 5Y₁ βˆ’ 5Yβ‚‚ + Y₃ s.t. Y₁ βˆ’ Yβ‚‚ + Y₃ ≀ 2 Y₁ βˆ’ Yβ‚‚ βˆ’ 2Y₃ ≀ 3 Y₁, Yβ‚‚, Y₃ β‰₯ 0

E5 β€” Three variables, an equality AND a wrong-direction constraint

Max Z = X₁ + 2Xβ‚‚ + 3X₃ s.t. X₁ + Xβ‚‚ + X₃ ≀ 12 2X₁ βˆ’ Xβ‚‚ + X₃ β‰₯ 4 ← wrong direction X₁ + 2Xβ‚‚ = 8 ← equality X₁, Xβ‚‚, X₃ β‰₯ 0

This is the hardest shape the exam uses β€” the same structure as Final Q1A, with one extra variable.

  1. Step 1 β€” Canonical form: Max primal ⟹ every constraint must be ≀
    OriginalActionCanonicalDual var
    X₁ + Xβ‚‚ + X₃ ≀ 12already ≀X₁ + Xβ‚‚ + X₃ ≀ 12Y₁
    2X₁ βˆ’ Xβ‚‚ + X₃ β‰₯ 4Γ— (βˆ’1)βˆ’2X₁ + Xβ‚‚ βˆ’ X₃ ≀ βˆ’4Yβ‚‚
    X₁ + 2Xβ‚‚ = 8the ≀ halfX₁ + 2Xβ‚‚ ≀ 8Y₃
    the β‰₯ half, Γ— (βˆ’1)βˆ’X₁ βˆ’ 2Xβ‚‚ ≀ βˆ’8Yβ‚„
    4 dual variables (the equality counted twice)
  2. Step 2 β€” Dual objective Min W = 12Y₁ βˆ’ 4Yβ‚‚ + 8Y₃ βˆ’ 8Yβ‚„
  3. Step 3 β€” Read down each primal column
    VariableY₁Yβ‚‚Y₃Yβ‚„Dual constraint
    X₁1βˆ’21βˆ’1Y₁ βˆ’ 2Yβ‚‚ + Y₃ βˆ’ Yβ‚„ β‰₯ 1
    Xβ‚‚112βˆ’2Y₁ + Yβ‚‚ + 2Y₃ βˆ’ 2Yβ‚„ β‰₯ 2
    X₃1βˆ’100Y₁ βˆ’ Yβ‚‚ β‰₯ 3
  4. Step 4 β€” Complete dual Min W = 12Y₁ βˆ’ 4Yβ‚‚ + 8Y₃ βˆ’ 8Yβ‚„ s.t. Y₁ βˆ’ 2Yβ‚‚ + Y₃ βˆ’ Yβ‚„ β‰₯ 1 Y₁ + Yβ‚‚ + 2Y₃ βˆ’ 2Yβ‚„ β‰₯ 2 Y₁ βˆ’ Yβ‚‚ β‰₯ 3 Y₁, Yβ‚‚, Y₃, Yβ‚„ β‰₯ 0

F Β· Sensitivity Analysis Unit 1 Β· numerical

The report used for F1–F4
VariableValueReduced CostOrig. CoeffLowerUpper
X₁200402560
Xβ‚‚150302048
X₃0725βˆ’βˆž32
ConstraintDual ValueSlack/SurplusOrig. RHSLowerUpper
Labour120300240380
Material50200150260
Machine hrs025150125∞

F1 β€” Binding constraints and the current profit

  1. Step 1 β€” Apply the two-part binding test
    ConstraintSlackDualVerdict
    Labour012Binding
    Material05Binding
    Machine hrs250Not binding
  2. Step 2 β€” Compute the current objective value Z = 40(20) + 30(15) + 25(0) Z = 800 + 450 + 0 Z = β‚Ή1,250

F2 β€” A shadow price used inside its range

Labour hours are increased from 300 to 340. By how much does profit change, and is the answer valid?

  1. Step 1 β€” Check the change is inside the allowable range New RHS = 300 + 40 = 340 Allowable range for Labour = 240 to 380 340 lies inside the range ⟹ the shadow price is valid
  2. Step 2 β€” Apply the shadow-price formula Ξ”Z = shadow price Γ— Ξ”RHS Ξ”Z = 12 Γ— 40 Ξ”Z = + β‚Ή480
  3. Step 3 β€” State the new profit New Z = 1250 + 480 = β‚Ή1,730
  4. Step 4 β€” The economic sentence

    Each additional labour hour is worth β‚Ή12 of extra profit, so the firm should be willing to pay up to β‚Ή12 per hour of overtime β€” but only for the first 80 extra hours, after which the range is exhausted.

F3 β€” A shadow price used BEYOND its range the twist

Labour hours are increased from 300 to 400. What happens to profit?

  1. Step 1 β€” Check the range FIRST New RHS = 400 Allowable upper bound = 380 400 > 380 ⟹ the change goes OUTSIDE the allowable range
  2. Step 2 β€” Split the change at the boundary Valid portion: 300 β†’ 380 is +80 hours Ξ”Z over that portion = 12 Γ— 80 = + β‚Ή960
  3. Step 3 β€” Say what you cannot say about the rest Remaining portion: 380 β†’ 400 is +20 hours The shadow price of 12 does NOT apply here β€” the basis changes beyond 380

    Profit will still rise, but by less than 12 per hour, and the problem must be re-solved to say how much. The correct answer is: "profit rises by at least β‚Ή960; beyond 380 hours the current basis is no longer optimal and the shadow price is no longer valid."

⚠ The most common sensitivity error

Multiplying the shadow price by the whole change without checking the range: 12 Γ— 100 = β‚Ή1,200. That is wrong. Always check the range before you multiply. Examiners set this deliberately.

F4 β€” Reduced cost, and a coefficient change

  1. Step 1 β€” Interpret the reduced cost of X₃ X₃ has value 0 ⟹ it is NOT produced Reduced cost = 7 X₃'s profit coefficient must rise by β‚Ή7 β€” from 25 to 32 β€” before it becomes worth producing Check: the table's upper bound for X₃ is 32 = 25 + 7 βœ“ internally consistent

    Equivalently: forcing one unit of X₃ into the solution would reduce total profit by β‚Ή7.

  2. Step 2 β€” X₁'s coefficient rises from 40 to 55 β€” does the solution change? Allowable range for X₁ = 25 to 60 55 lies inside the range ⟹ The optimal QUANTITIES are unchanged: X₁ = 20, Xβ‚‚ = 15, X₃ = 0
  3. Step 3 β€” But recompute Z, because the objective value DOES change New Z = 55(20) + 30(15) + 25(0) New Z = 1100 + 450 New Z = β‚Ή1,550 (up from β‚Ή1,250)
  4. Step 4 β€” Machine hours are increased by 30. Any effect? Machine hours: dual value = 0, slack = 25 No change in profit β€” Ξ”Z = 0 Γ— 30 = 0

    There are already 25 unused machine hours. Adding more of a resource you are not fully consuming cannot help. The constraint is non-binding.

G Β· Integer Linear Programming Unit 2

G1 β€” Project selection with a prerequisite and a mutual exclusion

A firm is choosing among five R&D projects with a β‚Ή150 lakh budget and 60 engineer-months available.

ProjectCost (β‚Ή lakh)Engineer-monthsProfit (β‚Ή lakh)
A401255
B552072
C301038
D602585
E25830

Rules: B can only be done if A is done. C and D cannot both be selected. At least three projects must be chosen. Formulate an ILP to maximise profit.

  1. Step 1 β€” Decide the variable type

    "Which projects should be chosen" ⟹ a yes/no decision per project ⟹ binary.

    Let Xα΅’ = 1 if project i is selected, 0 otherwise, for i = A, B, C, D, E
  2. Step 2 β€” Objective function Max Z = 55X_A + 72X_B + 38X_C + 85X_D + 30X_E
  3. Step 3 β€” Resource constraints, one per column 40X_A + 55X_B + 30X_C + 60X_D + 25X_E ≀ 150 ← budget 12X_A + 20X_B + 10X_C + 25X_D + 8X_E ≀ 60 ← engineer-months
  4. Step 4 β€” Translate each logical rule, one at a time "B only if A" β†’ X_B ≀ X_A ← prerequisite "not both C and D" β†’ X_C + X_D ≀ 1 ← mutual exclusion "at least 3 projects" β†’ X_A + X_B + X_C + X_D + X_E β‰₯ 3
  5. Step 5 β€” The binary condition (a full mark on its own) X_A, X_B, X_C, X_D, X_E are binary (0, 1)
Why X_B ≀ X_A works: if X_B = 1 the inequality forces X_A β‰₯ 1, so A must be selected. If X_B = 0 it reads 0 ≀ X_A, which leaves A free. That is exactly the English rule.

G2 β€” Mixed ILP with batch production

A plant makes cement (in whole truckloads of 20 tonnes) and loose sand (any quantity in tonnes). A truckload of cement gives β‚Ή8,000 profit; sand gives β‚Ή150 per tonne. Cement uses 4 machine-hours per tonne, sand 1 machine-hour per tonne; 900 machine-hours are available. Storage is 500 tonnes total. Formulate.

  1. Step 1 β€” Decide which variable is integer and which is continuous Cement is sold only in whole truckloads β†’ integer Sand is sold by the tonne, any amount β†’ continuous ⟹ this is a MIXED integer programme
  2. Step 2 β€” Define the variables, handling the batch size Let X₁ = number of TRUCKLOADS of cement produced (integer) Then tonnes of cement = 20X₁ Let Xβ‚‚ = tonnes of sand produced (continuous)
  3. Step 3 β€” Objective function Max Z = 8000X₁ + 150Xβ‚‚
  4. Step 4 β€” Constraints, converting truckloads to tonnes where needed Machine hours: 4(20X₁) + 1(Xβ‚‚) ≀ 900 80X₁ + Xβ‚‚ ≀ 900 Storage: 20X₁ + Xβ‚‚ ≀ 500
  5. Step 5 β€” Restrictions X₁, Xβ‚‚ β‰₯ 0 and X₁ is an integer
⚠ The batch-size trap

If you define X₁ as "tonnes of cement" you cannot express "whole truckloads" β€” 20 tonnes is not the same as "X₁ integer". Define the variable as the number of batches and multiply by the batch size wherever tonnes are needed. The class notes use exactly this device for "tables in multiples of 10" Note 2 p. 20.

G3 β€” Fixed-charge facility location

A company may open depots at two sites. Opening Site 1 costs β‚Ή90 lakh, Site 2 costs β‚Ή110 lakh. An open depot can serve up to 120 units. Two markets need 70 and 90 units. Shipping costs per unit:

DepotMarket 1Market 2
Site 158
Site 274

Formulate to minimise total cost.

  1. Step 1 β€” You need TWO kinds of variable Let Xα΅’β±Ό = units shipped from depot i to market j (continuous, β‰₯ 0) Let Yα΅’ = 1 if depot i is opened, 0 otherwise (binary)
  2. Step 2 β€” Objective: fixed costs plus shipping costs Min Z = 90Y₁ + 110Yβ‚‚ ← fixed opening costs + 5X₁₁ + 8X₁₂ + 7X₂₁ + 4Xβ‚‚β‚‚ ← shipping costs
  3. Step 3 β€” Demand must be met exactly X₁₁ + X₂₁ = 70 ← Market 1 demand X₁₂ + Xβ‚‚β‚‚ = 90 ← Market 2 demand
  4. Step 4 β€” The linking constraint: you cannot ship from a closed depot X₁₁ + X₁₂ ≀ 120Y₁ X₂₁ + Xβ‚‚β‚‚ ≀ 120Yβ‚‚

    If Y₁ = 0 the right-hand side is 0, forcing all shipments from depot 1 to zero. If Y₁ = 1 the capacity is 120. That single inequality encodes "only if opened".

  5. Step 5 β€” Restrictions Xα΅’β±Ό β‰₯ 0 ; Y₁, Yβ‚‚ are binary (0, 1)

G4 β€” Pure ILP: staffing with minimum coverage

A call centre runs three shifts. It needs at least 8 agents in the morning, 6 in the afternoon and 5 at night. An agent works exactly one shift. Total agents available: 22. Calls handled per agent per shift: 30 (morning), 25 (afternoon), 18 (night). The night shift must have at least half as many agents as the morning shift. Formulate to maximise calls handled.

  1. Step 1 β€” Variables (counts of people ⟹ integer, not binary) Let X₁, Xβ‚‚, X₃ = number of agents on morning / afternoon / night shift
  2. Step 2 β€” Objective function Max Z = 30X₁ + 25Xβ‚‚ + 18X₃ ← total calls handled
  3. Step 3 β€” Minimum coverage per shift X₁ β‰₯ 8 Xβ‚‚ β‰₯ 6 X₃ β‰₯ 5
  4. Step 4 β€” Total workforce X₁ + Xβ‚‚ + X₃ ≀ 22
  5. Step 5 β€” Rearrange the ratio rule "night at least half of morning" β†’ X₃ β‰₯ 0.5X₁ Move all variables to the left: βˆ’0.5X₁ + X₃ β‰₯ 0 (or equivalently βˆ’X₁ + 2X₃ β‰₯ 0)
  6. Step 6 β€” Integrality X₁, Xβ‚‚, X₃ β‰₯ 0 and are integers

G5 β€” Either–or: two mutually exclusive production modes

A factory can run a product on either Line A or Line B, but not both. Line A needs 3 hours per unit with 240 hours available; Line B needs 2 hours per unit with 180 hours available. Profit is β‚Ή40 per unit either way. Formulate an ILP to maximise profit.

  1. Step 1 β€” Variables Let X = number of units produced (integer, β‰₯ 0) Let Y = 1 if Line A is used, 0 if Line B is used (binary)
  2. Step 2 β€” Objective function Max Z = 40X
  3. Step 3 β€” Only ONE line's constraint should bind β€” use a big-M switch

    Let M be a large number (say 10,000). Write both constraints, each relaxed when its line is not chosen:

    3X ≀ 240 + M(1 βˆ’ Y) ← binds only when Y = 1 (Line A chosen) 2X ≀ 180 + MΒ·Y ← binds only when Y = 0 (Line B chosen)
  4. Step 4 β€” Check the switch works If Y = 1: 3X ≀ 240 and 2X ≀ 180 + 10000 (always true, relaxed) If Y = 0: 3X ≀ 240 + 10000 (relaxed) and 2X ≀ 180 ⟹ exactly one constraint is active in each case
  5. Step 5 β€” Restrictions X β‰₯ 0 and integer ; Y is binary (0, 1)
The big-M pattern: whenever a question says "either… or…, but not both", write both constraints and add + M(1 βˆ’ Y) to one and + MY to the other. The binary Y then switches which one is real.

H Β· Transportation & Assignment Unit 3

H1 β€” Unbalanced assignment (more workers than jobs)

A supervisor must assign jobs to workers. Costs (β‚Ή hundred):

J1J2J3
W113816
W291512
W312911
W461410

(1) Is it balanced? If not, how do you balance it? (2) Number of constraints, excluding NNC? (3) Number of variables?

  1. Step 1 β€” Identify the problem type No supply column, no demand row β€” each worker takes one job ⟹ ASSIGNMENT problem, m = 4 workers, n = 3 jobs
  2. Step 2 β€” Balance test For an assignment problem, balanced means rows = columns m = 4, n = 3, and 4 β‰  3 ⟹ NOT balanced
  3. Step 3 β€” How to balance it Columns are short by 1 Add ONE DUMMY JOB column with all costs = 0, making the matrix 4 Γ— 4

    The worker assigned to the dummy job is the one who stays idle β€” at zero cost, because no work is actually done.

  4. Step 4 β€” Counting, on the ORIGINAL matrix Number of constraints = m + n = 4 + 3 = 7 Number of variables = m Γ— n = 4 Γ— 3 = 12

H2 β€” Unbalanced transportation (supply exceeds demand)

D1D2D3Supply
S1861050
S2912760
S31491640
Demand405030
  1. Step 1 β€” Compute BOTH totals explicitly Total supply = 50 + 60 + 40 = 150 Total demand = 40 + 50 + 30 = 120
  2. Step 2 β€” Compare 150 β‰  120 β€” supply exceeds demand by 30 ⟹ NOT balanced
  3. Step 3 β€” Balance it on the correct side Add a DUMMY DESTINATION (column) with demand = 30 and all costs = 0

    Supply is the surplus side, so the dummy must absorb it β€” a dummy destination. The 30 units "shipped" there are simply the units never dispatched.

  4. Step 4 β€” Counting Constraints = m + n = 3 + 3 = 6 Variables = m Γ— n = 3 Γ— 3 = 9
Which side gets the dummy: add the dummy to the side that is short. Supply short β†’ dummy source (row). Demand short β†’ dummy destination (column). In H2 demand is short, so a column is added.

H3 β€” Full LPP conversion of a 2 Γ— 3 transportation problem

D1D2D3Supply
S147360
S265940
Demand304525
  1. Step 1 β€” Housekeeping lines (these carry marks) Total supply = 60 + 40 = 100 ; Total demand = 30 + 45 + 25 = 100 Balanced : YES Decision variable : Xα΅’β±Ό = units shipped from source i (1–2) to destination j (1–3) No. of variables = m Γ— n = 2 Γ— 3 = 6 No. of constraints = m + n = 2 + 3 = 5
  2. Step 2 β€” Objective function, read row by row Min Z = 4X₁₁ + 7X₁₂ + 3X₁₃ + 6X₂₁ + 5Xβ‚‚β‚‚ + 9X₂₃
  3. Step 3 β€” Supply constraints (one per row, ≀) X₁₁ + X₁₂ + X₁₃ ≀ 60 X₂₁ + Xβ‚‚β‚‚ + X₂₃ ≀ 40
  4. Step 4 β€” Demand constraints (one per column, =) X₁₁ + X₂₁ = 30 X₁₂ + Xβ‚‚β‚‚ = 45 X₁₃ + X₂₃ = 25
  5. Step 5 β€” Non-negativity, and the internal check Xα΅’β±Ό β‰₯ 0 2 supply + 3 demand = 5 constraints βœ“ matches m + n from Step 1

H4 β€” Transportation with a PROFIT objective

Two factories supply three showrooms. Production cost is β‚Ή20/unit at F1 and β‚Ή18/unit at F2. Selling prices are β‚Ή40, β‚Ή45 and β‚Ή38 at showrooms A, B, C. Transport costs per unit:

ABCCapacity
F1354100
F2627120
Demand809050
  1. Step 1 β€” Recognise the twist

    Selling prices are given, so the cell value is a profit and the objective is Max, not Min.

    Profit(iβ†’j) = Selling price(j) βˆ’ Production cost(i) βˆ’ Transport cost(iβ†’j)
  2. Step 2 β€” Compute the profit matrix, cell by cell
    CellWorkingProfit
    F1 β†’ A40 βˆ’ 20 βˆ’ 317
    F1 β†’ B45 βˆ’ 20 βˆ’ 520
    F1 β†’ C38 βˆ’ 20 βˆ’ 414
    F2 β†’ A40 βˆ’ 18 βˆ’ 616
    F2 β†’ B45 βˆ’ 18 βˆ’ 225
    F2 β†’ C38 βˆ’ 18 βˆ’ 713
  3. Step 3 β€” Balance test on the profit table Total capacity = 100 + 120 = 220 Total demand = 80 + 90 + 50 = 220 220 = 220 ⟹ BALANCED, no dummy needed
  4. Step 4 β€” Write the LPP Let Xα΅’β±Ό = units shipped from factory i to showroom j Max Z = 17X₁ₐ + 20X₁ᡦ + 14Xβ‚πšŒ + 16X₂ₐ + 25X₂ᡦ + 13Xβ‚‚πšŒ Supply: X₁ₐ + X₁ᡦ + Xβ‚πšŒ = 100 X₂ₐ + X₂ᡦ + Xβ‚‚πšŒ = 120 Demand: X₁ₐ + X₂ₐ = 80 X₁ᡦ + X₂ᡦ = 90 Xβ‚πšŒ + Xβ‚‚πšŒ = 50 NNC: Xα΅’β±Ό β‰₯ 0
  5. Step 5 β€” Counting Variables = m Γ— n = 2 Γ— 3 = 6 Constraints = m + n = 2 + 3 = 5

H5 β€” Assignment with a forbidden pairing

Four machines must be assigned to four operators. Operator 3 is not trained on Machine B, so that pairing is not allowed. Times (minutes):

ABCD
Op 11291411
Op 215131012
Op 38β€”139
Op 410111214
  1. Step 1 β€” Handle the forbidden cell

    A forbidden assignment is given a prohibitively large cost M so the optimiser will never choose it:

    Set cost(Op 3, Machine B) = M where M is a very large number

    The alternative is to write the explicit constraint X₃ᡦ = 0. Either is acceptable β€” state which you used.

  2. Step 2 β€” Balance test m = 4 operators, n = 4 machines, 4 = 4 ⟹ BALANCED, no dummy needed
  3. Step 3 β€” Variables and objective Let Xα΅’β±Ό = 1 if operator i is assigned to machine j, 0 otherwise Min Z = 12X₁ₐ + 9X₁ᡦ + 14Xβ‚πšŒ + 11Xβ‚πš + 15X₂ₐ + 13X₂ᡦ + 10Xβ‚‚πšŒ + 12Xβ‚‚πš + 8X₃ₐ + MΒ·X₃ᡦ + 13Xβ‚ƒπšŒ + 9Xβ‚ƒπš + 10X₄ₐ + 11X₄ᡦ + 12Xβ‚„πšŒ + 14Xβ‚„πš
  4. Step 4 β€” Constraints: each row = 1, each column = 1 Row (one machine per operator): Ξ£β±Ό Xα΅’β±Ό = 1 for i = 1…4 Column (one operator per machine): Ξ£α΅’ Xα΅’β±Ό = 1 for j = A…D Xα΅’β±Ό = 0 or 1
  5. Step 5 β€” Counting Variables = 4 Γ— 4 = 16 Constraints = 4 + 4 = 8