If I have a linear programming problem e.g. $$\max 2x_1 + x_2$$ with these constraints

$$x_1-2x_2 \leq 14$$ $$2x_1-x_2\leq 10$$ $$x_1-x_2 \leq 3$$

And I want to solve the problem starting from a specific point e.g. $A=(x1=5, x2=0)$ and $B=(x1=0, x2=5)$ .

How should I configure the initial tableau to allow to iterate simplex method starting from these points?

(Note that in standard form when I add the slack variables, the points must be calculated in function of the extra variables.)

  • $\begingroup$ Are these two separate starting points to set up? That is, for the first one you wish to start with $x_1=5,x_2=0$? $\endgroup$ – coffeemath Feb 4 '16 at 23:35
  • $\begingroup$ A=5,0 is a single starting point $\endgroup$ – AndreaF Feb 4 '16 at 23:35
  • $\begingroup$ That's what I meant, and also $B=(0,5)$ would be another starting point. What version of tableaus are you to use? Just thought, maybe you mean 5,0 as a decimal like usual 5.0 (some British use comma for decimal) $\endgroup$ – coffeemath Feb 4 '16 at 23:37
  • $\begingroup$ I usually convert the problem in the standard form and use the 2-phases method. No comma is a separator x1=5 x2=0 $\endgroup$ – AndreaF Feb 4 '16 at 23:41

One way would be, for a start at (5,0), to set up a new variable $x_1'$ and put the original $x_1$ equal to $5+x_1'$ in the objective and constraints. Then the usual simplex, starting at $(0,0)$ in the $x_1',x_2$ variables, would in effect be starting at $(5,0)$ in the $x_1,x_2$ variables.

  • $\begingroup$ you mean a new constraint $$x6=5+x1$$ that become $$-x1+x6=5$$ to start from $$x1=5$$ and $$x2=0$$ ??? Note: I have used $$x6$$ because $$x3$$, $$x4$$ and $$x5$$ are needed for slack Have I well understand? $\endgroup$ – AndreaF Feb 4 '16 at 23:51
  • $\begingroup$ Actually I just meant to substitute say $x_1=5+x_6$ into everything in the original objective and constraints, and then work from there, i.e. (since you want other lower index vars for slacks) the new system would be all in terms of $x_6,x_2$ rather than in $x_1,x_2,$ and would after the substitutions have different looking objective and constraints. The way I'm thinking of, there would be no constraint involving $x_1$ and $x_6,$ since $x_1$ would no longer appear in the "new" problem. $\endgroup$ – coffeemath Feb 5 '16 at 0:08
  • $\begingroup$ So my objective function will be $$2(5+x6)+x2$$, in the same way constraints eg. the first $$x1−2x2≤14$$ becomes $$5+x6−2x2≤14$$. Now is right? And when I have to put objective function in cost row how to deal with the constant introduced? I'm a bit confused about this approach, In addition I have just noted that $$A=(5,0)$$ in the standard form after that I put the slack becomes $$A=(5,0,9,0−2)$$ while the point $$B=(0,5)$$ becomes $$B=(0,5,4,10,8)$$ if you write the first tableau would be helpful. $\endgroup$ – AndreaF Feb 5 '16 at 2:20
  • $\begingroup$ I have edited the comment because not well written. Are you online? $\endgroup$ – AndreaF Feb 5 '16 at 22:02
  • 1
    $\begingroup$ thanks for the answer... without consider to start the iteration from specific point my first tableau is row1: [1 -2 1 0 0 14] row2: [2 -1 0 1 0 10] row3: [1 -1 0 0 1 3] row4: [2 1 0 0 0 0] $\endgroup$ – AndreaF Feb 7 '16 at 14:03

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.