La méthode GRAND M / BIG M

Summary

This video tutorial explains the Big M method for solving linear programming problems with constraints that are not in canonical form. The method introduces artificial variables to convert inequalities into equalities, enabling the use of the simplex algorithm. The process includes adjusting the objective function to penalize artificial variables and ensuring they are driven to zero in the final solution. Through step-by-step iterations and tableau updates, the video illustrates how to find an optimal solution, focusing on the importance of handling artificial variables and ensuring the feasibility of the solution.

Takeaways

• 😀 The Big M method is a technique used to solve linear programming problems with constraints that are not in canonical form.
• 😀 The method starts by transforming constraints into a form suitable for the simplex algorithm, adding artificial variables where necessary.
• 😀 For constraints in the form of 'greater than or equal to', an artificial variable is added to simulate an identity column.
• 😀 For equality constraints, no artificial variables are needed as they are already in a suitable form.
• 😀 Artificial variables are added to the objective function with a large negative coefficient (denoted as -M) to ensure they do not interfere with the solution.
• 😀 After introducing artificial variables, the problem is transformed into a maximization problem, with the goal of driving artificial variables to zero.
• 😀 The initial tableau for the simplex algorithm may not include an identity matrix, so artificial variables are used to create one.
• 😀 The tableau is updated through iterations using the simplex method, checking for optimality at each stage.
• 😀 The solution is deemed feasible if no artificial variables are in the solution and all basic variables are positive.
• 😀 The 'Big M' method is used to handle linear programming problems where constraints require the introduction of artificial variables, allowing the simplex algorithm to function correctly.
• 😀 In practice, very large values (such as M = 10^9) are used for artificial variables, ensuring they do not affect the optimal solution when the algorithm converges.

Q & A

What is the Big M method in linear programming?

The Big M method is a technique used to solve linear programming problems that involve constraints not in canonical form. It introduces artificial variables to the system and adjusts the objective function with a large penalty term (-M) to drive these artificial variables to zero in the optimal solution.

Why are artificial variables necessary in the Big M method?

Artificial variables are necessary when constraints do not fit into the required canonical form (e.g., equality or greater-than constraints). They help simulate the identity matrix in the constraint matrix, allowing the simplex algorithm to proceed with an initial feasible solution.

How does the Big M method handle an 'equal to' constraint?

In the case of an 'equal to' constraint, no additional artificial variable is needed because the constraint is already in the required form. However, a variable of slack or surplus may be introduced depending on the specific nature of the constraint.

What is the role of the large constant M in the objective function?

The constant M is a very large value that is added (or subtracted) to the objective function to penalize the artificial variables. The idea is to force the artificial variables to zero in the optimal solution, ensuring that only the original decision variables are used in the final solution.

What is the significance of the initial tableau in the simplex method?

The initial tableau in the simplex method is used to represent the system of linear equations. It includes the constraints and the objective function, and the first iteration of the simplex algorithm is performed to find an initial basic feasible solution.

How do you determine which variable enters the basis in the simplex method?

In the simplex method, the variable with the most negative coefficient in the objective function row is chosen to enter the basis. This corresponds to the variable that can increase the objective function the most.

What happens if a tableau shows a positive value in the objective function row?

If a tableau shows a positive value in the objective function row, it indicates that the solution is not optimal. The algorithm will continue by selecting a variable to enter the basis and performing further iterations to improve the objective function.

How is the leaving variable chosen in the simplex method?

The leaving variable is chosen based on the minimum ratio test. For each positive entry in the column of the entering variable, the ratio of the right-hand side value to the corresponding coefficient in the entering variable's column is calculated. The smallest ratio determines which variable leaves the basis.

What does it mean when a solution is not feasible in the Big M method?

A solution is not feasible in the Big M method when the artificial variables do not converge to zero, indicating that there is no feasible solution that satisfies all constraints.

What is the final test for optimality in the Big M method?

The final test for optimality in the Big M method is to check if all the artificial variables are zero and whether there are no negative coefficients in the objective function row. If these conditions are met, the solution is optimal.