University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

118

Pages:

12
Author:

innosancta5nq

Recitation about LP 1 Linear Program Minimize c’x Subject to Ax ≥ b, Bx ≥ d, Cx ≤ f, The variables can be non negative, non positive or free. 2 An example of Linear Program Minimize – x1 – x2 Subject to And x1 + 2x2 ≤ 4 , 2x1 + x2 ≤ 3, 0 ≤ x1, x2 3 Example (cont’d) x2 3 (2/3,5/3) is the optimal solution 2 1 0 0 1 2 3 4 x1 4 Simplex method We need the LP to be in standard form in order to run simplex method. This means that the LP has: -Only equality constraints -Non negative RHS -Non negative variables We need an initial basic feasible solution to start the method. 5 Standard form of the example We add extra non negative variables s1, s2 to transform the inequality constraints into equality constraints. The standard form: Minimize – x1 – x2 Subject to And x1 + 2x2 + s1 = 4, 2x1 + x2 + s2 = 3, 0 ≤ x1, x2, s1, s2 6 Basic Feasible Solutions Suppose there are m constraints, n variables A basic solution is found by setting n - m variables to 0 and solving the remaining system with n variables and n constraints. •The n – m variables are called non-basic variables •The m variables are called basic variables In our example, n = 4 and m = 2. A basic feasible solution is (x1, x2 , s1 , s2) = (0, 0, 4, 3) 7 Simplex Method in our example Initial Basic Feasible solution: (0, 0, 4, 3), Cost: 0 -z x1 x2 s1 s2 1 -11 -4 -1 -1 1 6 -1 0 1 2 0 = 0 8 0 -7 1 5 2 1 1 0 = 8 4 0 12 -2 2 4 6 1 2 0 -3 1 = 10 -6 3 x1 will enter to the basis because it has negative reduced cost s2 will leave the basis. 8 Next iteration Basic Feasible solution: (3/2, 0, 5/2, 0), Cost: -3/2 -z x1 x2 s1 s2 1 -11 -4 0 -1/2 1 6 -1 0 1/2 1 2 = 3/2 0 8 0 -7 0 3/2 5 1 -1/2 1 = 5/2 8 0 12 -2 1 1/2 4 6 2 0 1/2 -3 = 3/2 10 -6 x2 will enter to the basis because it has negative reduced cost s1 will leave the basis. 9 Last iteration Basic Feasible solution: (5/3, 2/3, 0, 0), Cost: -7/3 -z x1 x2 s1 s2 1 -11 -4 0 1 6 0 1/3 -1 0 1/3 1 2 = 7/3 0 8 0 -7 0 5 1 2/3 1 -1/3 1 = 5/3 8 0 12 -2 1 4 6 0 -1/3 2 1/3 0 -3 = 2/3 10 -6 This solution is optimal because all the reduced costs are non negative. 10 Duality Primal Problem P minimize z = cx subject to Ax = b x≥0 Dual Problem maximize subject to D v = πb πA ≤ c optimum value is z* optimum value is v* Theorem. (Strong Duality) If both P and D are feasible, then z* = v*. 11 Duality Complementary Slackness: Let x, π be feasible solutions to the primal and dual problem, respectively. Then they are optimal solutions for the two respective problems if and only if: πi (ai’x - bi) = 0 for all i, (cj – π’Aj)xj = 0 for all j. 12