What to do if, when solving the LLP by the artificial basis method, there are penalties in the vector estimates?

Question

Linear algebra

I solve the following problem of integer programming using the Gomory method:

F(X) = 3x_1 + x_2 -> max;
4x_1 + x_2 <= 19,
5x_1 - 2x_2 <= 15,
x_1 + x_3 <= 10;
x_1, x_2 >= 0.

Solved the weakened problem by the usual simplex method, introducing the basic variables x_3, x_4 and x_5 - nothing complicated. The resulting simplex table:



Since the solution is not integer, found the variable with the largest fractional part x_1: {65/17} = 14/17. Having received a new constraint 3/17x_4 + 2/17x_5 >= 14/17, he introduced a free variable x_6 with a coefficient of -1 and a basic x_7. The objective function has taken the form:

F(X) = 3x_1 + x_2 -Mx_7 -> max.

Solved the resulting problem by the simplex method with an artificial basis and obtained an acceptable basic solution. However, although all variables with penalties M left the basis, in the delta j=7 the penalty M remained:



I am sure that the solution obtained is correct, I even double-checked it with two online solvers.

Although this would be acceptable if the usual LLP were to be solved, in my case it prevents me from moving on to the next iteration of the Gomori method. And it is necessary, because the resulting value of the objective function F(X) = 3*3 + 1*7/3 = 34/3 is not integer. In principle, it would be possible to score and solve with a dual simplex, but I would like to get to the bottom of the reasons for what is happening. I understand that I have no right to ask to repeat all the tedious iterations of the simplex method, so I only ask you to indicate in general terms where the problem may lie.

Answer 1

The issue resolved itself: just keep solving, introducing new basic variables with penalties. Penalties from previous iterations will not affect the solution.