*NURSING > EXAM > FTEC 2101/ESTR2520 Optimization Methods (All)

FTEC 2101/ESTR2520 Optimization Methods

Document Content and Description Below

Problem 1. (25%) Consider the following linear programming problem in standard form: max x1,x2,x3 −x1 + 2x2 + 3x3 s.t. −x1 + x2 ≤ 3 −x2 + 2x3 ≤ 2 x1 − 3x3 ≤ 6, x1, x2, ... x3 ≥ 0. Apply the simplex method to find an optimal solution to the LP problem or to show that the LP problem is unbounded. You may initialize the simplex method with a solution satisfying (x1, x2, x3) = (0, 0, 0). Solution. We begin by introducing the slack variables and rewriting the problem in the canonical form: max z x1,x2,x3,s1,s2,s3,z s.t. z + x1 − 2x2 − 3x3 = 0 −x1 + x2 + s1 = 3 −x2 + 2x3 + s2 = 2 x1 − 3x3 + s3 = 6, x1, x2, x3, s1, s2, s3 ≥ 0. It is clear that we can take s1, s2, s3 as the initial basis which will lead to a feasible CPF solution. We thus form the simplex table: BV z x1 x2 x3 s1 s2 s3 RHS z 1 1 -2 -3 0 0 0 0 s1 0 -1 1 0 1 0 0 3 s2 0 0 -1 2 0 1 0 2 s3 0 1 0 -3 0 0 1 6 1 We select x3 as the entering variable and s2 as the leaving variable. Observe the following row opera- tions: −2 −3 0 0 0 0  1 1 −2 −3 0 0 0 0  1 0 1 0 0 3 R2/2→R2 0 −1 1 0 1 0 0 3    −1 2 0 1 0 2  R3+−3R→2→R3  0 0 −1/2 1 0 1/2 0 1  0 3 0 0 1 6 1 1 −7/2 0 0 3/2 0 3  0 1 −3/2 0 0 3/2 1 9 R0+3R2→R0 0 −1 1 0 1 0 0 3 0 0 −1/2 1 0 1/2 0 1 0 1 −3/2 0 0 3/2 1 9 Resulting in the table: BV z x1 x2 x3 s1 s2 s3 RHS z 1 1 -7/2 0 0 3/2 0 3 s1 0 -1 1 0 1 0 0 3 x3 0 0 -1/2 1 0 1/2 0 1 s3 0 1 -3/2 0 0 3/2 1 9 We now choose x2 as the entering variable, and s1 is the leaving variable: 1 1 −7/2 0 0 3/2 0 3 1 1 −7/2 0 0 3/2 0 3  0 −1/2 0 1 1/2 1/2 0 5/2 0 −1/2 0 0 3/2 3/2 1 27/2  0 −1 1 0 1 0 0 3  R2+R1/2→R2  0 −1 1 0 1 0 0 3  0 0 −1/2 1 0 1/2 0 1 R3+3−R→1/2→R3 0 1 −3/2 0 0 3/2 1 9 R0+7R1/2→R0  0 −1 1 0 1 0 0 3  −→ 0 −1/2 0 1 1/2 1/2 0 5/2 0 −1/2 0 0 3/2 3/2 1 27/2 Notice that the 2nd column consists of only negative coefficients. Thus the LP problem is unbounded. [Show More]

Last updated: 2 years ago

Preview 1 out of 8 pages

Buy Now

Instant download

We Accept: