Operation Research 11: Linear Programming Solution: Two phase method
2.6 هزار بار بازدید -
3 سال پیش
-
Linear Programming Solution using Two
Linear Programming Solution using Two phase method
The simplex method algorithm requires a initial basic feasible solution (BFS).
Initial BFS is the slack variables put on the column of BV in the initial simplex tableau.
This doesn't work in LPP having ≥ and = constraints.
Two phase method is modified version of the simplex method that will solve LPP having ≥ and = constraints.
Thus, artificial variables are added to get starting basic feasible solutions.
Steps of Two Phase Method
Bring the constraints into equality form. For each constraint in which the slack variable and the right-hand side have opposite signs, or in which there is no slack variable, add a new artificial variable that has the same sign as the right-hand side.
Phase I: minimize the sum of the artificial variables, starting from the BFS where the absolute value of the artificial variable for each constraint, or of the slack variable in case there is no artificial variable, is equal to that of the right-hand side.
If some artificial variable has a positive value in the optimal solution, the original problem is infeasible;
Phase II: solve the original problem, starting from the BFS found in phase I.
The simplex method algorithm requires a initial basic feasible solution (BFS).
Initial BFS is the slack variables put on the column of BV in the initial simplex tableau.
This doesn't work in LPP having ≥ and = constraints.
Two phase method is modified version of the simplex method that will solve LPP having ≥ and = constraints.
Thus, artificial variables are added to get starting basic feasible solutions.
Steps of Two Phase Method
Bring the constraints into equality form. For each constraint in which the slack variable and the right-hand side have opposite signs, or in which there is no slack variable, add a new artificial variable that has the same sign as the right-hand side.
Phase I: minimize the sum of the artificial variables, starting from the BFS where the absolute value of the artificial variable for each constraint, or of the slack variable in case there is no artificial variable, is equal to that of the right-hand side.
If some artificial variable has a positive value in the optimal solution, the original problem is infeasible;
Phase II: solve the original problem, starting from the BFS found in phase I.
3 سال پیش
در تاریخ 1400/10/08 منتشر شده
است.
2,603
بـار بازدید شده