● QT · TERM END
🔍 /
QUANTITATIVE TECHNIQUES›ASSIGNMENTS›ASSIGNMENT 4

Assignment 4 — Duality — Primal to Dual

Five primals converted to their duals with the course's canonical method — every wrong-way constraint flipped, every equality split — and each dual checked against its primal by strong duality.

PROBLEMS: 5 UNIT: UNIT 01 — DUALITY Original: Assignment 4
◆ The method for every problem on this page
  1. Count the dual variables first: one per primal constraint, an equality counts twice.
  2. Canonical form: a Max primal needs every constraint ≤, a Min primal every constraint ≥. Multiply a wrong-way constraint by −1 (every coefficient and the RHS flip). Split each = into a ≤ and a ≥, and flip whichever half is the wrong way.
  3. Dual objective: Max ↔ Min; the canonical RHS values become the objective coefficients.
  4. Dual constraints: one per primal variable, reading down its column; RHS = that variable's objective coefficient; direction ≥ for a Max primal, ≤ for a Min primal.
  5. Sign restriction: all Y ≥ 0 (in canonical form).

Full procedure with the exam example: Unit 1 · Duality.

★ Tricks that save time in the exam
  • The shortcut answer for an equality: the pair Y₃ − Y₄ (both ≥ 0) is the same as one unrestricted variable Y₃′. Either form earns full marks; the course writes the pair, so write the pair.
  • Shape check before you hand it in: dual variables = primal constraints (equalities ×2); dual constraints = primal variables.
  • Strong duality as a self-check: if both problems have optima, their values are equal. All three solvable pairs below were checked this way.

Q1 — Max Z = 7X₁ + 5X₂

Question
Maximise Z = 7X₁ + 5X₂ X₁ + 2X₂ ≤ 10 3X₁ + X₂ ≥ 12 2X₁ + 3X₂ ≤ 18 X₁ + X₂ = 7 2X₁ − X₂ ≤ 6 X₁, X₂ ≥ 0

Assignment 4 p. 1

Solution
  1. Step 1 — Count 5 constraints, 1 equality ⟹ the dual has 6 variables (Y₁, Y₂, Y₃, Y₄, Y₅, Y₆) and 2 constraints
  2. Step 2 — Canonical form
    OriginalActionCanonicalDual var
    X₁ + 2X₂ ≤ 10already ≤X₁ + 2X₂ ≤ 10Y₁
    3X₁ + X₂ ≥ 12× (−1)−3X₁ − X₂ ≤ −12Y₂
    2X₁ + 3X₂ ≤ 18already ≤2X₁ + 3X₂ ≤ 18Y₃
    X₁ + X₂ = 7the ≤ halfX₁ + X₂ ≤ 7Y₄
    the other half, × (−1)−X₁ − X₂ ≤ −7Y₅
    2X₁ − X₂ ≤ 6already ≤2X₁ − X₂ ≤ 6Y₆
  3. Step 3 — Dual objective (RHS values become coefficients) Min W = 10Y₁ − 12Y₂ + 18Y₃ + 7Y₄ − 7Y₅ + 6Y₆
  4. Step 4 — Dual constraints (one per primal variable, read down its column) Y₁ − 3Y₂ + 2Y₃ + Y₄ − Y₅ + 2Y₆ ≥ 7 2Y₁ − Y₂ + 3Y₃ + Y₄ − Y₅ − Y₆ ≥ 5
  5. Step 5 — The complete dual Min W = 10Y₁ − 12Y₂ + 18Y₃ + 7Y₄ − 7Y₅ + 6Y₆ Subject to: Y₁ − 3Y₂ + 2Y₃ + Y₄ − Y₅ + 2Y₆ ≥ 7 2Y₁ − Y₂ + 3Y₃ + Y₄ − Y₅ − Y₆ ≥ 5 Y₁, Y₂, Y₃, Y₄, Y₅, Y₆ ≥ 0Check (strong duality): primal optimum Z = 43.67; dual optimum W = 43.67 ✓

Q2 — Min Z = 5X₁ + 4X₂

Question
Minimise Z = 5X₁ + 4X₂ 2X₁ + X₂ ≥ 8 X₁ + 3X₂ ≤ 12 3X₁ + 2X₂ = 10 X₁, X₂ ≥ 0

Assignment 4 p. 1

Solution
  1. Step 1 — Count 3 constraints, 1 equality ⟹ the dual has 4 variables (Y₁, Y₂, Y₃, Y₄) and 2 constraints
  2. Step 2 — Canonical form
    OriginalActionCanonicalDual var
    2X₁ + X₂ ≥ 8already ≥2X₁ + X₂ ≥ 8Y₁
    X₁ + 3X₂ ≤ 12× (−1)−X₁ − 3X₂ ≥ −12Y₂
    3X₁ + 2X₂ = 10the ≥ half3X₁ + 2X₂ ≥ 10Y₃
    the other half, × (−1)−3X₁ − 2X₂ ≥ −10Y₄
  3. Step 3 — Dual objective (RHS values become coefficients) Max W = 8Y₁ − 12Y₂ + 10Y₃ − 10Y₄
  4. Step 4 — Dual constraints (one per primal variable, read down its column) 2Y₁ − Y₂ + 3Y₃ − 3Y₄ ≤ 5 Y₁ − 3Y₂ + 2Y₃ − 2Y₄ ≤ 4
  5. Step 5 — The complete dual Max W = 8Y₁ − 12Y₂ + 10Y₃ − 10Y₄ Subject to: 2Y₁ − Y₂ + 3Y₃ − 3Y₄ ≤ 5 Y₁ − 3Y₂ + 2Y₃ − 2Y₄ ≤ 4 Y₁, Y₂, Y₃, Y₄ ≥ 0

    Worth knowing: this primal has no feasible solution — solving it leaves an artificial variable in the basis — and its dual is correspondingly unbounded. That is the duality theorem at work: if one problem is infeasible, the other is unbounded or infeasible. The question only asks for the formulation, which is unaffected.

Q3 — Max Z = 4X₁ + 6X₂ + 3X₃

Question
Maximise Z = 4X₁ + 6X₂ + 3X₃ 2X₁ + X₂ + 3X₃ ≤ 12 X₁ + 3X₂ + 2X₃ ≥ 15 3X₁ + 2X₂ + X₃ = 10 X₁, X₂, X₃ ≥ 0

Assignment 4 p. 1

Solution
  1. Step 1 — Count 3 constraints, 1 equality ⟹ the dual has 4 variables (Y₁, Y₂, Y₃, Y₄) and 3 constraints
  2. Step 2 — Canonical form
    OriginalActionCanonicalDual var
    2X₁ + X₂ + 3X₃ ≤ 12already ≤2X₁ + X₂ + 3X₃ ≤ 12Y₁
    X₁ + 3X₂ + 2X₃ ≥ 15× (−1)−X₁ − 3X₂ − 2X₃ ≤ −15Y₂
    3X₁ + 2X₂ + X₃ = 10the ≤ half3X₁ + 2X₂ + X₃ ≤ 10Y₃
    the other half, × (−1)−3X₁ − 2X₂ − X₃ ≤ −10Y₄
  3. Step 3 — Dual objective (RHS values become coefficients) Min W = 12Y₁ − 15Y₂ + 10Y₃ − 10Y₄
  4. Step 4 — Dual constraints (one per primal variable, read down its column) 2Y₁ − Y₂ + 3Y₃ − 3Y₄ ≥ 4 Y₁ − 3Y₂ + 2Y₃ − 2Y₄ ≥ 6 3Y₁ − 2Y₂ + Y₃ − Y₄ ≥ 3
  5. Step 5 — The complete dual Min W = 12Y₁ − 15Y₂ + 10Y₃ − 10Y₄ Subject to: 2Y₁ − Y₂ + 3Y₃ − 3Y₄ ≥ 4 Y₁ − 3Y₂ + 2Y₃ − 2Y₄ ≥ 6 3Y₁ − 2Y₂ + Y₃ − Y₄ ≥ 3 Y₁, Y₂, Y₃, Y₄ ≥ 0Check (strong duality): primal optimum Z = 30; dual optimum W = 30 ✓

Q4 — Min Z = 6X₁ + 3X₂ + 5X₃

Question
Minimise Z = 6X₁ + 3X₂ + 5X₃ X₁ + X₂ + 2X₃ ≥ 9 2X₁ + 3X₂ + X₃ ≤ 15 X₁ + 2X₂ + X₃ ≥ 8 3X₁ + X₂ + 2X₃ = 12 X₁ − X₂ + X₃ ≤ 5 X₁, X₂, X₃ ≥ 0

Assignment 4 p. 1

Solution
  1. Step 1 — Count 5 constraints, 1 equality ⟹ the dual has 6 variables (Y₁, Y₂, Y₃, Y₄, Y₅, Y₆) and 3 constraints
  2. Step 2 — Canonical form
    OriginalActionCanonicalDual var
    X₁ + X₂ + 2X₃ ≥ 9already ≥X₁ + X₂ + 2X₃ ≥ 9Y₁
    2X₁ + 3X₂ + X₃ ≤ 15× (−1)−2X₁ − 3X₂ − X₃ ≥ −15Y₂
    X₁ + 2X₂ + X₃ ≥ 8already ≥X₁ + 2X₂ + X₃ ≥ 8Y₃
    3X₁ + X₂ + 2X₃ = 12the ≥ half3X₁ + X₂ + 2X₃ ≥ 12Y₄
    the other half, × (−1)−3X₁ − X₂ − 2X₃ ≥ −12Y₅
    X₁ − X₂ + X₃ ≤ 5× (−1)−X₁ + X₂ − X₃ ≥ −5Y₆
  3. Step 3 — Dual objective (RHS values become coefficients) Max W = 9Y₁ − 15Y₂ + 8Y₃ + 12Y₄ − 12Y₅ − 5Y₆
  4. Step 4 — Dual constraints (one per primal variable, read down its column) Y₁ − 2Y₂ + Y₃ + 3Y₄ − 3Y₅ − Y₆ ≤ 6 Y₁ − 3Y₂ + 2Y₃ + Y₄ − Y₅ + Y₆ ≤ 3 2Y₁ − Y₂ + Y₃ + 2Y₄ − 2Y₅ − Y₆ ≤ 5
  5. Step 5 — The complete dual Max W = 9Y₁ − 15Y₂ + 8Y₃ + 12Y₄ − 12Y₅ − 5Y₆ Subject to: Y₁ − 2Y₂ + Y₃ + 3Y₄ − 3Y₅ − Y₆ ≤ 6 Y₁ − 3Y₂ + 2Y₃ + Y₄ − Y₅ + Y₆ ≤ 3 2Y₁ − Y₂ + Y₃ + 2Y₄ − 2Y₅ − Y₆ ≤ 5 Y₁, Y₂, Y₃, Y₄, Y₅, Y₆ ≥ 0Check (strong duality): primal optimum Z = 28.67; dual optimum W = 28.67 ✓

Q5 — Max Z = 3X₁ + 8X₂ + 6X₃

Question
Maximise Z = 3X₁ + 8X₂ + 6X₃ 2X₁ + X₂ + X₃ ≥ 10 X₁ + 3X₂ + 2X₃ ≤ 15 3X₁ + 2X₂ + X₃ = 12 X₁ + X₂ − X₃ ≥ 4 X₁, X₂, X₃ ≥ 0

Assignment 4 p. 2

Solution
  1. Step 1 — Count 4 constraints, 1 equality ⟹ the dual has 5 variables (Y₁, Y₂, Y₃, Y₄, Y₅) and 3 constraints
  2. Step 2 — Canonical form
    OriginalActionCanonicalDual var
    2X₁ + X₂ + X₃ ≥ 10× (−1)−2X₁ − X₂ − X₃ ≤ −10Y₁
    X₁ + 3X₂ + 2X₃ ≤ 15already ≤X₁ + 3X₂ + 2X₃ ≤ 15Y₂
    3X₁ + 2X₂ + X₃ = 12the ≤ half3X₁ + 2X₂ + X₃ ≤ 12Y₃
    the other half, × (−1)−3X₁ − 2X₂ − X₃ ≤ −12Y₄
    X₁ + X₂ − X₃ ≥ 4× (−1)−X₁ − X₂ + X₃ ≤ −4Y₅
  3. Step 3 — Dual objective (RHS values become coefficients) Min W = −10Y₁ + 15Y₂ + 12Y₃ − 12Y₄ − 4Y₅
  4. Step 4 — Dual constraints (one per primal variable, read down its column) −2Y₁ + Y₂ + 3Y₃ − 3Y₄ − Y₅ ≥ 3 −Y₁ + 3Y₂ + 2Y₃ − 2Y₄ − Y₅ ≥ 8 −Y₁ + 2Y₂ + Y₃ − Y₄ + Y₅ ≥ 6
  5. Step 5 — The complete dual Min W = −10Y₁ + 15Y₂ + 12Y₃ − 12Y₄ − 4Y₅ Subject to: −2Y₁ + Y₂ + 3Y₃ − 3Y₄ − Y₅ ≥ 3 −Y₁ + 3Y₂ + 2Y₃ − 2Y₄ − Y₅ ≥ 8 −Y₁ + 2Y₂ + Y₃ − Y₄ + Y₅ ≥ 6 Y₁, Y₂, Y₃, Y₄, Y₅ ≥ 0

    Worth knowing: this primal has no feasible solution — solving it leaves an artificial variable in the basis — and its dual is correspondingly unbounded. That is the duality theorem at work: if one problem is infeasible, the other is unbounded or infeasible. The question only asks for the formulation, which is unaffected.