University:
The University Of Western Ontario
Course:
MATH 3020A | Introduction to Abstract Algebra
Academic year:

2024
Views:

234

Pages:

2
Author:

Kyuwon J.

Linear Programming: Questions and Solutions Q1: Complementary Slackness Conditions for Primal and Dual Problems Question: What is the set of complementary slackness conditions for the given pair of primal (P) and dual (D) problems? 1 0 1 1 (P ) : Maximize (1 2 1)x, subject to x= , x ≥ 0. 1 2 1 0     1 2 1    (D) : Minimize y1 + y2 , subject to 0 1 y ≥ 2 , y ≥ 0. 1 0 1 Solution: A pair of feasible solutions x̄ for (P) and ȳ for (D) satisfy the complementary slackness conditions if: 1. For each i ∈ {1, 2, 3}, x̄i = 0 or the i-th dual constraint is satisfied with equality: x̄i · (A⊤ ȳ)i − ci = 0. 2. For each j ∈ {1, 2}, ȳj = 0 or the j-th primal constraint is satisfied with equality: ȳj · ((Ax̄)j − bj ) = 0. This ensures that primal variables correspond to active dual constraints, and dual variables correspond to active primal constraints. Q2: Duality and Unboundedness Question: T/F: There is no y such that A⊤ y ≥ c if and only if max{c⊤ x : Ax = 0, x ≥ 0} is unbounded. Solution: This statement is True. According to Farkas’ Lemma, the infeasibility of the dual problem A⊤ y ≥ c is equivalent to the primal problem max{c⊤ x : Ax = 0, x ≥ 0} being unbounded. This relationship directly follows from the theory of linear programming duality. Q3: Dual Optimality Question: T/F: If an LP has an optimal solution, then its dual has an optimal solution. Solution: This statement is True. According to the Strong Duality Theorem, if the primal problem is feasible and bounded, it has an optimal solution, and so does its dual. Additionally, the objective values of the primal and dual are equal at optimality. Q4: Cone of Tight Constraints Question: Consider the LP: Maximize 50x1 + 60x2 , 2x1 + 4x2 3x1 + 2x2 subject to −x1 −x2 At x̄ = (0, 15), what is the cone of the tight constraints? 1 ≤ 60, ≤ 40, ≤ 0, ≤ 0. Solution: At x̄ = (0, 15), the tight constraints are: 2x1 + 4x2 = 60 and − x1 = 0. These constraints are expressed as: 2 4 −1 0 x1 0 = . x2 0 The cone of the tight constraints is spanned by the rows of this matrix, giving: 2 −1 Cone: span , . 4 0 Q5: Complementary Slackness for Numerical Pair Question: What is the set of complementary slackness conditions for the following pair of primal and dual problems? (P ) : Maximize c⊤ x, subject to Ax = b, x ≥ 0, (D) : Minimize b⊤ y, subject to A⊤ y ≥ c. Solution: The complementary slackness conditions are: 1. For each xi : xi > 0 ⇒ the i-th dual constraint is satisfied with equality. 2. For each yj : yj > 0 ⇒ the j-th primal constraint is satisfied with equality. 2