How to Solve Linear Programming with Two-Phase Method

TL;DR

The two-phase method effectively addresses linear programming problems involving greater than or equal to and equal to constraints. It starts by converting these constraints to equality and introducing artificial variables to find a feasible solution. The first phase minimizes the artificial variables, while the second phase solves the original problem based on the optimal solution from phase one.

Transcript

hello everybody and welcome to lesson 9 linear programming solution using two-phase method the objective of this lesson is to solve the linear programming problem using two-phase method as we know the simplex method algorithm requires an initial basis feasible solution initial basic visible solution is the slack variables put on the columns of the ... Read More

Key Insights

• 🟰 The two-phase method is used to solve linear programming problems with constraints involving greater than or equal to and equal to inequalities.
• 🛰️ In phase one, the objective is to minimize the artificial variables until they become zero.
• ➖ Optimal solutions are achieved when the cj minus zj values are greater than or equal to zero.
• 🤨 The two-phase method involves standardizing the constraints, introducing artificial variables, and conducting row operations to obtain the optimal solution.
• ↗️ The pivot column is determined based on the maximum negative value in the cj minus zj row, while the pivot row is determined by the least positive ratio of the right-hand side with the values in the pivot column.
• 🛰️ After phase one, the artificial variables are eliminated, and the original problem is solved in phase two.
• ➖ The optimality of the solution in phase two is checked using the cj minus zj values, with negative or zero values indicating optimality.

Summary & Key Takeaways

• The two-phase method is used to solve linear programming problems with greater than or equal to and equal to constraints.

• The first step is to bring the constraints into equality form and introduce artificial variables.

• In phase one, the goal is to minimize the sum of the artificial variables until they become zero. In phase two, the original problem is solved starting from the basic feasible solution found in phase one.