This is how we got the dual simplex method explained: With this method we solve a primary problem, not a dual one, in the primary simplex method (that is, in the standard method for the minimization problem) we have in each table (or iteration) an feasible non-negative basic solution (respectively, the so-called zero column of the variable denoted as $x_0$ is non-negative) and in this case we say that the table is primary feasible, we further know that the primary simplex method ends by finding the optimum if the vector of relative (reduced) costs (we denote it in the simplex tablue as zero row of the table) defined as the difference of the coefficient of the objective function and the scalar product of the coefficients of the objective function but only of basic variables and numbers in the given columns and for each column separately, is non-negative and in this case we say that the table is dually feasible. On the other hand, in the dual simplex method, we start right with a dually feasible table and we try to get a primary feasible table. So the dual simplex method algorithm works like this.
- 1st step: If there is a zero column (that is, the basic solution is also feasible because it is non-negative), then the table is also primarily feasible, that is, we have an optimal solution, and we finish and say that we found the optimal solution, if not then we continue with the 2nd step
- 2nd step: If the zero column is not non-negative, we select any row of the table (which corresponds to i-th component of the basic solution, or the coefficient of each variable in the i-th constraint of the given primary problem, while it is true that this element in the zeroth column and i-th row is negative, then row i exits the basis, but if for all columns of the table (respectively for each of the column marked with the letter j (the number of columns is equal to the number of other variables $x_1$ to $x_n$ and, of course, the additional variables of surplus or slack) applies that the element in this j-th column and in the i-th row that we have chosen (the i-th row, where the element in the zero column was negative) is non-negative, then the problem is infeasible (And this the problem of the second question - prove that this also applies), if there is some negative entry $x_ij$ (entry in i-th row and j-th column), then continue with the 3rd step.
- 3rd step: If this situation has not occurred (that is, the problem is not yet infeasible) then we select that s-th column from columns 1,2,...,j and denote it with $s$ that the denotion is $x_0s$ (that is, the element in the zeroth row and in the given s-th column) and the number $x_is$ (that is, the element in the appropriate ith row and in the sth column) was the maximum possible of all such divisions $x_0j/x_ij$ (where $x_ij$<0), and we pivot the table according to this of the element $x_is$ and then again go back to the first step.