How Does the Big M Method Solve Linear Programming?

TL;DR

The Big M Method is a strategy for solving linear programming problems with greater than or equal to and equal to constraints by introducing artificial variables. These variables help establish a basic feasible solution, which is then minimized to achieve optimality; if the final solution has no artificial variables, the problem is feasible.

Transcript

hello everybody and welcome to lesson 10. so far we have discussed different methods of solving linear programming some of the methods that we have discussed are the graphical method the general simplex method the duality and so on so today we are going to discuss about linear programming solution using big m method and the objective of this partic... Read More

Key Insights

• 🟰 The Big M Method is used to solve linear programming problems with greater than or equal to and equal to constraints.
• 🛰️ Artificial variables are added to the constraints to obtain a starting basic feasible solution.
• 🛰️ The objective is to minimize the artificial variables and make them zero in the final solution.
• 🛰️ If all the artificial variables are zero, the problem is feasible; otherwise, it is infeasible.
• 🤶 The Big M Method is an extension of the simplex method and requires standardizing the problem by converting inequalities to equalities and adding surplus and slack variables.
• 🤨 The pivot column and pivot row are determined to perform row operations in order to reach optimality.
• ✖️ Cj values are calculated by multiplying the coefficients of the basic variables with the corresponding Xn values.
• 🟰 The optimality is checked by comparing Cj values with Zj values, and if all Cj - Zj values are less than or equal to zero, the optimal solution is achieved.

Questions & Answers

Q: What is the objective of using the Big M Method in linear programming?

The objective of the Big M Method is to solve linear programming problems with greater than or equal to and equal to constraints, where the usual simplex method does not work. It introduces artificial variables to obtain a starting basic feasible solution and minimize them to achieve optimality.

Q: How are artificial variables used in the Big M Method?

Artificial variables are added to the constraints of linear programming problems with greater than or equal to and equal to constraints. They have no real meaning and are only added to facilitate the solution process. The goal is to minimize their values to zero in the final solution.

Q: How does the Big M Method determine if a linear programming problem is feasible or infeasible?

If all the artificial variables in the final solution equal zero, the problem is feasible. However, if any artificial variable has a positive value in the final solution, the problem is infeasible and has no solution.

Q: How does the Big M Method minimize the artificial variables?

A very large value, denoted as M, is assigned to the artificial variables in the objective function. For a maximization problem, M is subtracted from the artificial variables, and for a minimization problem, M is added. By minimizing the coefficients of the artificial variables, their values are reduced to zero in the optimal solution.

Summary & Key Takeaways

• The Big M Method is a modified version of the simplex method used to solve linear programming problems with greater than or equal to and equal to constraints.

• Artificial variables are introduced to obtain a starting basic feasible solution, and their values are minimized to zero in the final solution.

• The objective is to eliminate or minimize the artificial variables, as they are not part of the original linear programming problem.