Optimization Methods - Recitation 2

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

2023
Views:

172

Pages:

2
Author:

lacieabellaot

Recitation 2 1 Linear Algebra Review An m × n matrix A is a two-dimensional array aij : ⎡ a11 a12 ⎢ a21 a22 A=⎢ ⎣ ... ... am1 am2 A vector x ∈ Rn : ⎤ . . . a1n ⎥ . . . a2n ⎥ ... ... ⎦ . . . amn ⎡ ⎤ x1 ⎢ x2 ⎥ ⎥ x=⎢ ⎣ ... ⎦ xn The transpose matrix A of an m × n matrix A is an n × m matrix: [A ]ij = [A]ji The inner product of two vectors x and y in Rn is the value: x y = y x = n xi y i i=1 A matrix-vector product of an m × n matrix A and a vector x in Rn is: ⎡ ⎤ a1 x n ⎢ a2 x ⎥ ⎢ ⎥ = xj Aj Ax = ⎣ ... ⎦ j=1 am x The matrix multiplication of an m × n matrix A and an n × k matrix B results in an m × k matrix: [AB]ij = n aik bkj k=1 The identity matrix I is a square matrix with 1 s on the main diagonal and 0 s everywhere else. A is a square matrix. If there exists a matrix B such that AB = I then A is called invertible and B is the inverse of A, B = A−1 . 1 Example 1 x is a basic feasible solution to the standard form problem with corresponding basis B. Consider a direction d such that y = x + d is also a feasible solution. Find the change in the objective cost. Example 2 If dN is a unit vector in Rn−m . Find the direction d. 2 Full Tableau Simplex Question 1 How do you check whether there are multiple optimal solutions with the simplex method? Question 2 Given the initial tableau and the current tableau. How do you ﬁnd the basis B and its inverse? Example 3 Solve the following problem using the full tableau simplex method: x1 min s.t. x1 + x2 ≤ 2 −x1 + x2 ≤ 0 x1 , x2 ≥ 0 3 (1) Duality Theory I Question 3 Given the genereal linear programming problem: c x min s.t. (2) Ax ≥ b Construct its dual problem using Lagrange multiplier method. Example 4 Construct the dual of the following problem and then the dual of its dual: min s.t. 2x1 + 3x2 + 8x3 x1 − x2 − x3 ≥ 1 3x2 + x3 = 4 x3 ≤ 1 x1 , x2 , x3 ≥ 0 2 (3)