The Zoutendijk method of feasible directions for the optimization with non-linear constraints involves a step where a linear program is solved. In a particular example, the linear program is defined as follows:
$$
\hbox{Minimize}_{d_1,d_2,z}\quad z\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(*)\\ \hbox{subject to:}\\
\begin{align*}
\qquad\qquad\qquad-5.5d_1-3d_2-z&\leq 0\\
\qquad\qquad\qquad-d_1-z&\leq 0\\
\qquad\qquad\qquad-1\leq d_1&\leq 1\\
\qquad\qquad\qquad-1\leq d_2&\leq 1\\
\end{align*}
$$
where $z$ is $\hbox{Max}\{\nabla^tf(x)d,\, \nabla^tg_i(x)d\}$; $f$ is the function to be optimized and $g_i$ the restrictions that are active for the current parameter values.
According to the textbook, the problem above can be solved by means of the simplex method and the following solution is obtained: $d_1=1, d_2=-1, z=-1$.
I am stuck trying to solve this linear program. What I have done is the following. First, transform the variables $d_1$, $d_2$ and substitute them respectively by $y_1=(1-d_1)/2$ and $y_2=(1-d_2)/2$. As $d_1,d_2\in[-1,1]$, the variables $y_1,y_2\in[0,1]$. In particular $y_1,y_2$ are nonnegative and so, I understand they are suitable for the simplex method.
For the new variables, the program is (after including stack variables to transform the $\leq$ inequalities into equalities):
Edit:
I have realized that $z$ should be allowed to take positive, zero or negative values. By means of new variables $s_5,s_6\geq 0$ I define now $z=s_5-s_6$, so that now $z$ is a free variable.
$$
\hbox{Minimize}_{y_1,y_2,z,s_1,s_2,s_3,s_4,s_5,s_6}\quad z\color{red}{=s_5-s_6}\\ \hbox{subject to:}\\
\begin{align*}
\qquad\qquad\qquad 11y_1+6y_2-s_5+s_6+s_1&=8.5\\
\qquad\qquad\qquad 2y_1-s_5+s_6+s_2&= 1\\
\qquad\qquad\qquad y_1+s_3&= 1\\
\qquad\qquad\qquad y_2+s_4&= 1\\
\qquad\qquad\qquad y_1,\,y_2,s_1,s_2,s_3,s_4,s_5,s_6&\geq 0\\
\end{align*}
$$
Now, I proceed with the simplex method, starting as follows:
Edit: The initial Tableau becomes now:
$$
\begin{eqnarray*}
\begin{array}{cc|cccccccc|c}
&&s_5&s_6&y_1&y_2&s_1&s_2&s_3&s_4\\
&&1&-1&0&0&0&0&0&0\\
\hline
s_1&0&-1&1&11&6&1&0&0&0&8.5\\
s_2&0&-1&1&2&0&0&1&0&0&1\\
s_3&0&0&0&1&0&0&0&1&0&1\\
s_4&0&0&0&0&1&0&0&0&1&1\\
\hline
&&1&-1&0&0&0&0&0&0
\end{array}
\end{eqnarray*}
$$
Edit:
I choose the starting values proposed in the textbook, $d_1=0$, $d_2=0.75$, which imply $y_1=0.5$, $y_2=0.125$ and $z=\hbox{Max}\{\nabla^tf(x)d,\, \nabla^tg_i(x)d\}=0$. Thus, the values for the stack variables compatible with the constraints are the values marked in red.Those starting values are actually proposed in the book for the original non linear program (not for the search of the direction sought in this linear program). I choose initial values setting the slack variables equal zero. I'm not sure if this is the right approach.
Applying the steps of the simplex, I obtain the following Tableau:
$$
\begin{eqnarray*}
\begin{array}{c|cccccccc|c}
&s_5&s_6&y_1&y_2&s_1&s_2&s_3&s_4\\
\hline
\color{red}{s_1}&\color{red}{0}&0&9&6&1&-1&0&0&7.5\\
\color{red}{s_6}&\color{red}{-1}&1&2&0&0&1&0&0&1\\
\color{red}{s_3}&\color{red}{0}&0&1&0&0&0&1&0&1\\
\color{red}{s_4}&\color{red}{0}&0&0&1&0&0&0&1&1\\
\hline
&0&0&0&0&0&0&0&0&
\end{array}
\end{eqnarray*}
$$
This is the final Tableau, as there are no negative elements in the last row. The values for the solutions indicated in red imply: $z=s_5-s_6=0-1=-1$ and $y_1=y_2=0$, which imply in turn $d_1=d_2=1-2\times 0=1$. This is not the solution reported in the textbook, but according to the answer by RobPratt it is an admissible solution. It can be checked that the constraints are met.
Yet, I'm not completely sure whether the above calculations are correct. I thought that the slack variables should be initialized to the elements in the right-hand-side of the constraint they belong to, i.e.: $s_1=8.5$, $s_2=1$, $s_3=1$, $s_4=1$. I tried this option, it generates many more Tableaus until no more negative elements show up in the last row. In that case I obtained the other solution mentioned in the answer by RobPratt and in the textbook, $d_1=1$, $d_2=-1$, but the value for $z$ turned out to be $5/2>-1$, so something was not correct. Maybe I made some mistake in the calculations since several Tableaus were generated, but I'm not sure if it could bee some other type of mistake.
Edit: My questions are more concrete now:
1. Are the above calculations and solution obtained correctly?
2. How should I adjust the initial Tableu in order to get the other solution?
It seems I made a mistake in the calculations, but I am not sure either about the approach I took for solving program (*) above. I am not familiar with software tools to solve this program. It would be helpful to me if someone could check the solution of the program described above. If it yields the solution of the textbook $d_1=1$, $d_2=-1$, then I would at least know that my interpretation of the program is most likely correct and could focus on checking the calculations.
Best Answer
Your transformation is correct. Both $(d_1,d_2,y_1,y_2,z)=(1,-1,0,1,-1)$ and $(d_1,d_2,y_1,y_2,z)=(1,1,0,0,-1)$ are optimal, and so is every point on the line segment that joins them.