A question about the operation research and simplex method

Question

For the simplex method, we need to add slack variables. My question is how to determine how many slack variables should be considered in the LP problem? I don't quite get why in the cases to find out the minimum objective function with the lower bounded constraint, the number of slack variable is $2n$ where $n$ is the number of constraints. while in the max objective function with upper bounded constraint, the number of slack variable is $n$. Did I miss something about the simplex method?

Answer 1

Slack variables are introduced to convert your LP model into standard form. The design of the simplex method calls for your model to be of the standard form $Max/Min$ $z=c^Tx$ subject to $Ax=b, x\ge 0$. By introducing extra variables which take up the 'slack' in the inequality you get a model where there are only equalities and which is of the requisite standard form. It is easily established that both problems have the same feasible set, thereby the same solutions.

Your second question stems from confusing $\le$ type inequalities with $\ge$ inequalities. In case you have an inequality of the sort $2x+3y+4z\le 5$ you can add the slack variable $s$ on the left hand side to get an equation $2x+3y+4z+s=5$. In case your inequality was $2x+3y+4z\ge 5$ you can add the slack variable $s$ on the right hand side to get an equation $2x+3y+4z=5+s$ or equivalently $2x+3y+4z-s=5$. (We add the slack on the right since in this case the right hand side represented a quantity which was less and so needed the slack.)

Now the issue with $\ge$ is that it yields equations of the sort where the slack variable is being "subtracted" from the left hand side instead of being added. I will not go into details, but the usual application of the simplex algorithm fundamentally depends on the slack variable being "added" instead of being subtracted. Hence the $\ge$ represents the problem. To make the algorithm work "artificial variables" are further added to such equations. These behave just like the slack variables. So for example, $2x+3y+4z\ge 5$ will be changed to $2x+3y+4z-s+A= 5$ where $A$ is the new artificial variable. Introduction of these artificial variables is permitted since through a clever manipulation it is ensured that these variables are zero in the optimum solution. The net effect is that two variables per $\ge$ inequality are introduced in the problem, whereas only one variable per $\le$ inequality is introduced.

You have probably encountered maximization problems with only $\le$ constraints and minimization problems with only $\ge$ constraints. The number of slack variables has nothing to do with maximization or minimization, but as explained above has to do with the $\le$ or $\ge$ sign in the constraints.