0

When working with linear optimization, we often need to rewrite the problem in the standard form:

minimize $z=c^Tx$

subject to $Ax=b$ and $x\ge 0$

During that process, sometimes we introduce new variables ($x = x'-x''$) or use slack variables. My questions is, after doing these, will the extreme points of the original region change?

3x89g2
  • 7,542
  • We do need to be careful in introducing new variables (and the new constraints that accompany them) to make sure we are not imposing additional restrictions on the original variables. If we did, it would affect the feasible region and (potentially) the extreme points of the feasible region. – hardmath Oct 16 '15 at 02:52
  • I have a optimization problem. I rewrite it in standard form and solved for basic solutions. Then using these feasible basic solutions, I can find the extreme points of the new region. But I don't know how I can find the extreme points of the original region? – 3x89g2 Oct 16 '15 at 02:59
  • Typically in a two-phase simplex method we drive the rewritten problem to a feasible point, and from there to an optimal point (second phase). We have added new variables, but the "old" variables are still there. Thus there is no problem identifying the solution in terms of the old variables. Perhaps you are asking a different question about the simplex method, so please clarify the Question. – hardmath Oct 16 '15 at 03:02

0 Answers0