Optimization Methods - Recitation 1 - Solutions

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

2023
Views:

331

Pages:

3
Author:

seoul882k

Example Solutions 1 Example 1 Multicommodity path-ﬂow formulation In a given network, there are K origin-destination(OD) pair. Each OD pair k has a set of paths P k and a demand dk . Each edge e in the network is associated with a cost ce and a capacity ue. The problem is to minimize the total cost while satisfying the demand. Solution K Decision variables: xP , the ﬂow carried on the path P , P ∈ P k k=1 Objective function: ( k e∈P P∈ K k=1 P Capacity constraint: k P∈ K k=1 P :e∈P Demand constraint: ce )xP (1) xP ≤ ue xP ≥ dk ∀e (2) ∀k = 1, K (3) P ∈P k Nonnegative constraint: xP ≥ 0 ∀P ∈ K Pk (4) k=1 Example 2 Formulation with absolute values min s.t. x1 (5) |x1 + 2| + |x2 | ≤ 5 Solution ⎧ x1 + x2 ≤ 3 ⎪ ⎪ ⎨ x1 − x2 ≤ 3 |x1 + 2| + |x2 | ≤ 5 ⇔ −x ⎪ 1 + x2 ≤ 7 ⎪ ⎩ −x1 − x2 ≤ 7 1 x1 x1 x1 x1 ≥ −2, x2 ≥ −2, x2 ≤ −2, x2 ≤ −2, x2 ≥0 ≤0 ≥0 ≤0 (6) @ 6 @ @ @ @ @ @ � � @ B� @� �@ @ � @ � @ � @ III I @ A � @ � @ @ @ � @ �C � � @ � � @ IV II � � @ � � @ � @ � @� �@ @ � @ D @ � � � � � - Figure 1 Feasible region of the problem The feasible region is the square ABCD. Thus the constraints can be written as below: Example 3 x1 + x2 ≤ 3 (7) x1 − x2 ≤ 3 (8) −x1 + x2 ≤ 7 (9) −x1 − x2 ≤ 7 (10) Basic feasible solutions, optimal basis, and degeneracy min s.t. x1 x1 + x2 ≤ 2 −x1 + x2 ≤ 0 x1 , x2 ≥ 0 (11) Solution The standard form with slack variables: min s.t. x1 + x2 x1 + x2 + s1 = 2 −x1 + x2 + s2 = 0 x1 , x2 , s1 , s2 ≥ 0 2 (12) 6 @ @ � � @ � @ � @ A � @ � � @ � @ � @ O � @ � @ B � @ - Figure 2 Feasible region of the original problem From the graph, we have: the feasible region is the triangle OAB with three extreme points O(0, 0), A(1, 1), and B(2, 0). The matrix A for the problem in standard form is: 1 1 1 0 A= −1 1 0 1 1 1 . −1 1 1 0 . B(2, 0): basic feasible solution (2, 0, 0, 2), nondegenerate with the basis B2 = −1 1 1 1 1 1 , B4 = , O(0, 0): basic feasible solution (0, 0, 2, 0), degenerate with three bases B3 = −1 0 1 0 1 0 . and B5 = 0 1 The optimal solution is (0, 0, 2, 0). In order to check optimal bases, we need to use the optimality condition: c = c −cB B−1 A ≥ 0 . For example, the basic B4 is not an optimal basis: c4 = c −cB4 B−1 4 A= (2, 0, 0, −1). A(1, 1): basic feasible solution (1, 1, 0, 0), nondegenerate with the basis B1 = 3