![]() ![]() ![]() Maximize z = 3x1 + x2 Subject to 2x1 – x2 ≤ 2 x1 + 2x2 ≤ 5 x1, x2 ≥ 0 Example 2: Perform one iteration of Karmarkar’s method for the following LP Minimize z = 2x1 + 2x2 – 3x3 s.t x1 – 2x2 + 3x3 = 0 x1 + x2 + x3 = 1 x1, x2, x3 ≥ 0ĩ Computational Method Interior Point Methodsīarrier or interior-point methods, by contrast, visit points within the interior of the feasible region. Step 1: set up the dual form of the LP Step 2: apply the dual optimal condition to form the combined feasible region “=“ form Step 3: Convert the combined feasible region to the homogeneous form: AX = 0 Add the “ sum of all variables ≤ M” constraint Convert this constraint to “=“ form Introduce new dummy variable d2 = 1 to the system to convert the system to AX = 0 and 1X = M + 1 Step 4: convert the system to the form (1)-(3) Introduce the set of new variables xj = (M +1)xj’ to convert the system to the form AX’ = 0 and 1X’ = 1 Introduce new dummy variable d3’ to ensure (2) and (3)Ĩ Examples Example 1: convert the following LP to the Karmarkar’s LP Step 1: k = 0, start with the solution point and compute Step 2: stop if CXk < ε, else go to Step 3 Step 3: Define Compute Whereħ How to Transform any LP to the Karmarkar’s Form ![]() ![]() Subject to AX = 0 1X = (1) X ≥ 0 This LP must also satisfy satisfies AX = 0 (2) Optimal z-value = 0 (3) Where X= (x1, x2, …., xn)T, A is an m x n matrixĦ Karmarkar’s Method Suppose the LP is in the form (1) - (3) Moves through interior of feasible region Always improves objective function Theoretical interestĥ Karmarkar’s Method The LP form of Karmarkar’s method minimize z = CX Mata kuliah : K0164/ Pemrograman Matematika Tahun : 2008 Penyelesaian PL Dengan Karmarkar Pertemuan 9 :Ģ Learning Outcomes Mahasiswa dapat menyelesaikan PL dengan menggunakan metode Karmarkarģ Outline Materi: Model Karmarkar (Interior point method)Īlgoritma Karmarkar Contoh penyelesaian &diskusi Studi kasusĤ Interior Point Method x2 40 20 x1 30 Starts at feasible point 1 Penyelesaian PL Dengan Karmarkar Pertemuan 9 : ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |