0
$\begingroup$

I am studying the dual simplex method from Lieberman - 10e. An approach called dual simplex method was described that is "applied" on the "primal table" itself, i.e., We do not convert it into its dual problem. For the Primal problem, I know how to find an initial basis using Big-M method or Two phase method. Such a basis is called primal feasible and it may not be dual feasible(i.e., optimal or all function coefficient non-negative). However, from that table itself, is there any way to find an initial dual feasible or optimal solution. So that we can even apply the dual simplex algorithm?

"Initialization: After converting any functional constraints in $\geq$ form to $\leq$ form (by multiplying through both sides by -1), introduce slack variables as needed to construct a set of equations describing the problem. Find a basic solution such that the coefficients in Eq. (0) are zero for basic variables and nonnegative for nonbasic variables (so the solution is optimal if it is feasible). Go to the feasibility test. "


How to find such a basic solution which may be optimal but not feasible in the primal sense? I.e., how can I make all nonbasic functional coefficients non-negative by using the given constraints?

Edit: This is an example.

Suppose we have the problem.

$$\text{max} \;\;2x-3y+4z \\ x+y+z\leq8 \\ 2x+y-z\leq4 \\-x+2y-z\leq-3$$

Then in Tableau form we have,

$$ \begin{matrix} Z & x & y & z & s1 & s2 & s3 & b \\ 1 & -2 & 3 & -4 & 0 & 0 & 0 & 0 && eq(0) \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 8 && eq(1)\\ 0 & 2 & 1 & -1 & 0 & 1 & 0 & 4 && eq(2) \\ 0 & -1 & 2 & -1 & 0 & 0 & 1 & -3 && eq(3) \end{matrix} $$

Please note that here it's obvious by adding eq(1) to eq(0) required number of times. I want a more general way.

How can I initialize it for Dual simplex algorithm, i.e., how can I make all coefficients in eq(0) non-negative? Or simply put, how to initialize any table for the dual simplex algorithm?

Edit2: I propose the following conjecture, will it work?

1) Find the most negative coefficient in $eq(0)$ and choose it as our entering variable.
2) Choose max positive ratio and choose that as our leaving variable. (This way we will proceed toward an optimal solution fastest without caring for primal feasibility).
3) If no positive ratio exists for $a_{i, enter}>0$ where $i$ represent row index, the problem is dual infeasible.

$\endgroup$
2
$\begingroup$

As far as I know, in the dual simplex method, we start from a dual feasible (all elements in the objective row are nonnegative) and in each iteration, we try to achieve primal feasibility (all elements of the right-hand side are nonnegative).

In your example, you have both primal and dual infeasibility. I think in this situation, you better use the generalized simplex algorithm. Or if possible, replace $y' = -y$ and then solve your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.