Operation Research 11: Linear Programming Solution: Two phase method

TL;DR

This lesson explains how to solve linear programming problems involving greater than or equal to and equal to constraints using the two-phase method.

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.

Questions & Answers

Q: What is the purpose of the two-phase method in linear programming?

The two-phase method is used to solve linear programming problems that have greater than or equal to and equal to constraints. It introduces artificial variables to obtain a starting basic feasible solution.

Q: How does the two-phase method differ from the simplex method?

The two-phase method is a modified version of the simplex method that can handle constraints with greater than or equal to and equal to inequalities. It involves introducing artificial variables and has two phases: minimizing their value and then solving the original problem.

Q: How is the pivot column determined in the two-phase method?

The pivot column is determined by selecting the maximum negative value in the cj minus zj row, as the goal is to minimize the artificial variables in phase one.

Q: How is the pivot row determined in the two-phase method?

The pivot row is determined by taking the least positive ratio of the right-hand side with the values in the pivot column. The ratio is calculated for each row, and the row with the smallest positive ratio is chosen as the pivot row.

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.