0

ILP:

$max$ $3x-2y+z$,

$st$ $x+5y-z <= 4$,

$2x-2y+4z <= 6$

$x,y,z >= 0$

I was trying the simplex method for a maximisation problem, and I got the solution $x=(19/6,1/6,0)$ and cost in tableau$=(-55/6)$.

Then I converted the objective function from max to min, and converted the sign as well. After doing the tableau, I found solution $x=(19/6,1/6,0)$ and cost in tableau$=(55/6)$.

Pluging the solution into the main objective function, will give me $55/6$.

My question if simplex method is only for min problem? Or I am missing something?

Mo Farouk
  • 1

1 Answers1

1

As you have noticed, $$\max c^Tx = - \min (-c^Tx)$$

It depends on the convention that you adopt. Look at the reduced cost $c_j-p'A_j$ in your algorithm. If it terminate when the reduced cost is is nonnegative, then it is written with minimization in mind.

What is inconsistent now is your main objective function and the cost of the tableu. Of which, I can't tell for sure unless you are willing to share your objective function.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Problem: max 3x-2y+z, st x+5y-z <= 4, 2x-2y+4z <= 6 So I made the tableau computations once with this objective function coefficients (3,-2,1), and once with inverted signs (-3,2,-1). PS: solution values and cost value are divided by 6. Just for simplicty, I ignored it. – Mo Farouk Aug 14 '17 at 17:46
  • How did you get $7$? – Siong Thye Goh Aug 14 '17 at 18:07
  • I am sorry, the 7 is typo mistake. Pluging (19/6, 1/6, 0) into the objective function gives 55/6. Tableau computations with initial coefficients gives -55/6. Tableau computations with inverted coefficients gives 55/6. – Mo Farouk Aug 14 '17 at 18:19
  • http://www.math.wsu.edu/faculty/dzhang/201/Guideline%20to%20Simplex%20Method.pdf example of an implementation of a version of simplex method. Notice that in the first step, they rewrite the objective function from $P=3x_1+x_2$ to $-3x_1-x_2+P=0$ and the objective function is the one that is just showned in the tableu. – Siong Thye Goh Aug 14 '17 at 19:26
  • So, this means either max or min problem, we should invert the signs of the objective function. Right? – Mo Farouk Aug 14 '17 at 19:52
  • Try to pick a convention and stick to it so that you don't get confused. It seems to me that you are doing what the link that I shared is doing right? In that case, you are doing maximization. Invert the signs of objective function. – Siong Thye Goh Aug 14 '17 at 19:57
  • Let us continue this discussion in chat. – Mo Farouk Aug 14 '17 at 20:04