University:
Whitman College
Course:
MATH-339 | Operations Research
Academic year:

2024
Views:

118

Pages:

2
Author:

Manuel Bernard

Previously, we had the Dual Theorem, which stated that if we had an optimal basis B for the solution to our primal, then the solution to the dual can be computed by taking y = (cTB B −1 )T In Section 6.7, we saw that we can find the solution to the dual by looking at the optimal tableau for the primal. For example, suppose we have a primal given by the tableau to the left, and we obtain the optimal tableau by the usual simplex method (the result is to the right). x1 x2 s1 s2 rhs x1 x2 s1 s2 rhs −2 1 0 0 0 0 0 4/3 1/3 10/3 → 1 −1 1 0 1 0 1/3 1/3 7/3 2 1 0 1 6 0 1 −2/3 1/3 4/3 We found that the entry under the slack variables in the optimal tableau give the values of the dual. In this case, y1 = 4/3, y2 = 1/3 Why? We can work that computation out. In the initial tableau, the slack variable column would have 0 in Row 0 and ~ej in its column. Therefore, in the optimal tableau, the column under the slack variable becomes B −1~ej = (B −1 )j (which is the j th column of the inverse of B), and the entry in Row 0 becomes cTB (B −1 )j = yj = j th value of the dual 6.8: Shadow Prices • Recall the definition: The shadow price of the ith constraint is the amount by which the optimal z−value is improved if we increase bi by 1 unit. To compute the shadow price for the first constraint, for example, the RHS vector b becomes b + ~e1 , and in the final tableau, the RHS becomes: B −1 (b + ~e1 ) = B −1 b + (B −1 )1 To compute the new z value using this RHS, we have znew = cTB (B −1 b + (B −1 )1 ) = cTB B −1 b + cTB (B −1 )1 = zold + y1 This says that the shadow price of the first constraint is y1 . We can similarly show that the shadow price of constraint i is yi , which is the theorem below. • The main theorem is the following: The shadow price of the ith constraint (of a max primal) is the optimal value of the ith dual variable. • Here’s an interesting Lemma that may give some insight into shadow prices (bottom of p. 315) 1 Given a maximization problem, and given a “≤” constraint, the shadow price will ALWAYS be NON-negative. Here’s an intuitive reason: Suppose the constraint is given by: ai1 x1 + · · · ain xn ≤ bi ⇒ ai1 x1 + · · · ain xn ≤ (bi + 1) Then, any feasible point for the constraint on the left is also a solution to the constraint on the right. In a maximization problem, the maximum (in terms of z) solution for the left constraint gives a lower bound on the possible values that solve the constraint on the right, so that z must always be as good or better. • Similarly, what happens with a ≥ constraint? That is, compare the sets of x where ai1 x1 + · · · ain xn ≥ bi ⇒ ai1 x1 + · · · ain xn ≥ (bi + 1) One way to think about this is that the constraint on the right is more restrictive than than the constraint on the left, therefore there is “less” data that satisfies the right, and our maximum would either stay the same or decrease. Computing the solution to the dual Here’s a quick example. The primal is shown, together with its final tableau. x1 x2 s1 s2 rhs 0 −6 −5 0 0 1 1 1 0 5 3 2 0 1 12 → x1 x2 s1 s2 rhs 0 0 3 1 27 1 0 −2 1 2 0 1 3 −1 3 The solution to the dual is y = [3, 1]T . This was straightforward to compute because if the initial column has 0 in Row 0, and the column is ei , then at the final tableau, we will have the ith value of cTB B −1 , which is the ith value of y. 2

Operations Research - Study Notes

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock