Consider the primal problem:
Maximize z = 5x1 + 12x2 + 4x3
subject to x1 + 2x2 + x3 = 10
2x1 − x2 + 3x3 = 8
x1, x2, x3 ≥ 0
Its dual problem is
Minimize w = 10y1 + 8y2
subject to y1 + 2y2 ≥ 5
2y1 − y2 ≥ 12
y1 + 3y2 ≥ 4
Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. y1 ≥ 0, y2 unrestricted
Explanation
A ≤ constraint in a max problem gives a dual variable ≥ 0, and an equality constraint gives an unrestricted dual variable. The official answer (A) treats the first constraint as x1 + 2x2 + x3 ≤ 10 and the second as an equality. If both are read as equalities, both y1 and y2 would be unrestricted.More Discrete Structures and Optimization questions
- The logic expression (P′ ∧ Q) ∨ (P ∧ Q′) ∨ (P ∧ Q) is equivalent to
- Consider α, β, γ as logical variables. Which of the following are correct logical equivalences? (A) α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ) (B) α ∨…
- Let ({a, b}, *) be a semigroup where a * a = b. Consider: (A) a * b = b * a (B) b * b = b Choose the most appropriate answer from the optio…
- Let ε = 0.0005 and let Rε = {(x, y) ∈ ℝ2 : |x − y| < ε}, which can be interpreted as 'approximately equal'. Rε is (A) Reflexive (B) Symmetr…
- Consider the following in Boolean algebra: X: a ∨ (b ∧ (a ∨ c)) = (a ∨ b) ∧ (a ∨ c) Y: a ∧ (b ∨ (a ∧ c)) = (a ∧ b) ∨ (a ∧ c) The identity a…
- Given below are two statements: Assertion (A) and Reason (R). Assertion (A): ¬p Reason (R): (r → ¬q, r ∨ s, s → ¬q, p → q) In the light of…