Good morning! I'm absolutely new to linear programing since this year, yet I'm struggling to understand and learn.

I was given during my lecture that to chose the initial vertice we had to determine a vertice of $U$ if it is not empty or to show that this set was empty indeed.

To a set $U=\{v\in\mathbb{R}^+|Av=b\}$ we associate the following linear program: find $(u,\tilde u)$ (I'm not quite sure of what $\tilde u$ is. such that:

\begin{cases} (u,\tilde u)\in \tilde U=\{(v,\tilde v)\in \mathbb{R}^{+^n}\times \mathbb{R}^{+^m}|Av+\tilde v=b\}\\ \min\limits_{(u,\tilde u)\in \tilde U}\sum\limits_{i=1}^{m}\tilde u_i \end{cases}

Tis set is empty iif this $\min$ is negative. We thus had to apply the Simplex algorithm to solve this new linear programming problem. $(0,b)$ is a vertice of $\tilde U$ and we can the initialize this method but I don't understand neither know how.

in practice,

Its a minimizing case: considering the linear program: if we have to find $x_1,x_2$ and $x_3$ such that

\begin{cases} \min_xf(x)=x_1 -3x_2 +2x_3\\ 3x_1 -x_2 +2x_3\le 7\\ -2x_1 + 4x_2\le 12\\ -4x_1 + 3x_2 + 8x_3\le 10\\ x\ge 0 \end{cases}

which can be writen as:

$A=\begin{pmatrix} 3 & -1 & 2 & 1 & 0 & 0 & 0 \\ -2 & 4 & 0 & 0 & 1 & 0\\ -4 & 3 & 8 & 0 & 0 & 1\\ \end{pmatrix}$

$b=\begin{pmatrix} 7\\12\\ 10\\ \end{pmatrix}$

and $c=\begin{pmatrix} 1,-3,2,0,0,0 \end{pmatrix}^T$

We first have $u_0=\begin{pmatrix} 0,0,0,7,12,10 \end{pmatrix}$, okay, I think I understand

Yet, do we find the inital vertice to start from? how do we initialise?

Why do we first have $I_0=(4,5,6)$?


and what about

\begin{cases} \max_xf(x)=x_1+x_2\\ x_1 +x_2\ge 2\\ x_1 + x_2\le 7\\ 3x_2 -x_1\le 9\\ 3x_1 +2x_2\le 18\\ x\ge 0 \end{cases}

The vertice of the realisable area are

\begin{array}{lll} A=(2,0) \\ B=(0,2) \\ C=(0,3)\\ D=(3,4)\\ E=(4,3)\\ F=(6,0) \end{array}

Here I clearly see that the origin isn't a feasible starting point. I thus have to find a realisable vertice Do I have to solve another program to find it? Why?


you mentioned that $I_0 = (4,5,6)$.

So, did you meant that $(x_1,x_2,x_3)_{initial} = (4,5,6)$ ?

Initialize means that you have to choose a proper "start value"

since you will have to do several iterations to optimize the objective function(al)

There is no FIXED way to choose a start point, but generally, you select your initial value of your variable such that the objective function(al) is relatively close to the target value, which may be measured by $L^2$ or $L^\infty$ norm, etc.

back to your question,

the initial value of variable(s) is NOT UNIQUE,

you can choose some other values, for instance $(3,4,6)$, just avoid too big or small magnitude. In some cases, different initial values lead to different results.

  • $\begingroup$ Thank you for this answer but how to chose it then? I used to chose the origin but in the second example, it's not possible... $\endgroup$ – IggyPass Mar 5 '16 at 14:44
  • 1
    $\begingroup$ since you give the exact realisable area, you have to choose a point inside it, as initial value. If you choose a point outside the realisable area, it is surely meaningless $\endgroup$ – J. Yu Mar 5 '16 at 14:59
  • $\begingroup$ Actually it can't be $(4,5,6)=(x_1,x_2,x_3)$ because it violate the first constraint in the first example. $3x_1-x_2+2x_3\ge 7$. How to find then what is the realisable area? Is there a method? $\endgroup$ – IggyPass Mar 6 '16 at 15:56

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.