A theoretical LPP can be typeset as
\begin{array}{ll}
\text{maximize} & c^T x \\
\text{subject to}& d^T x = \alpha \\
&0 \le x \le 1.
\end{array}
\begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to}& d^T x = \alpha \\ &0 \le x \le 1. \end{array}
To input a numerical LPP, use alignat instead of align to get better alignment between signs, variables and coefficients.
\begin{alignat}{5}
\max \quad & z = & x_1 & + & 12 x_2 & & & && \\
\mbox{s.t.} \quad & & 13 x_1 & + & x_2 & + & 12x_3 & \geq 5 && \tag{constraint 1} \\
& & x_1 & & & + & x_3 & \leq 16 && \tag{constraint 2} \\
& & 15 x_1 & + & 201 x_2 & & & = 14 && \tag{constraint 3} \\
& & \rlap{x_i \ge 0, i = 1, 2, 3}
\end{alignat}
\begin{alignat}{5} \max \quad & z = & x_1 & + & 12 x_2 & & & && \\ \mbox{s.t.} \quad & & 13 x_1 & + & x_2 & + & 12x_3 & \geq 5 && \tag{constraint 1} \\ & & x_1 & & & + & x_3 & \leq 16 && \tag{constraint 2} \\ & & 15 x_1 & + & 201 x_2 & & & = 14 && \tag{constraint 3} \\ & & \rlap{x_i \ge 0, i = 1, 2, 3} \end{alignat}
We treat $\max$, $z$, each variable, $\pm$ sign and RHS as one separate column, while leaving an extra empty column on the right. Then we count the number of separators &, add one into this number then divide it by two. (e.g. (9 + 1) รท 2 = 5)
\rlap is used so that the last row spans over one column.
Optional: \tag is used to label the constraints.
To get fractions, execute format rat at the beginning.
Writing manually the $\rm\LaTeX$ code for a matrix with many rows and columns in Octave is tedious. The Octave function
strcat("\\begin{bmatrix}\n",strrep(strrep(mat2str(A)," "," & "), ...
";"," \\\\\n")(2:end-1),"\n\\end{bmatrix}\n")
converts
A = [1 2 2; 2 3 4; 4 4 2]
A =
1 2 2
2 3 4
4 4 2
to
\begin{bmatrix}
1 & 2 & 2 \\
2 & 3 & 4 \\
4 & 4 & 2
\end{bmatrix}
so that pasting the generated code gives
$$ \begin{bmatrix} 1 & 2 & 2 \\ 2 & 3 & 4 \\ 4 & 4 & 2 \end{bmatrix}. $$
Simplex tableauxSince the coefficient of the objective value variable $z$ never changes, my habit is to omit the $z$-column to save ink.
Normal simplex tableau\begin{array}{rrrrrr|r}
& x_1 & x_2 & s_1 & s_2 & s_3 & \\ \hline
s_1 & 0 & 1 & 1 & 0 & 0 & 8 \\
s_2 & 1 & -1 & 0 & 1 & 0 & 4 \\
s_3 & 1 & 1 & 0 & 0 & 1 & 12 \\ \hline
& -1 & -1 & 0 & 0 & 0 & 0
\end{array}
\begin{array}{rrrrrr|r} & x_1 & x_2 & s_1 & s_2 & s_3 & \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 8 \\ s_2 & 1 & -1 & 0 & 1 & 0 & 4 \\ s_3 & 1 & 1 & 0 & 0 & 1 & 12 \\ \hline & -1 & -1 & 0 & 0 & 0 & 0 \end{array}
It can be stacked up to give an illustration of the entering of variables at different stages.
\begin{array}{rrrrrrr|rr}
& x_1 & x_2 & s_1 & s_2 & s_3 & w & & \text{ratio} \\ \hline
s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 & - \\
w & 1^* & -1 & 0 & -1 & 0 & 1 & 4 & 4 \\
s_3 & 1 & 1 & 0 & 0 & 1 & 0 & 12 & 12 \\ \hdashline
& 1 & -1 & 0 & -1 & 0 & 0 & 4 & \\ \hline
s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 & \\
x_1 & 1 & -1 & 0 & -1 & 0 & 1 & 4 & \\
s_3 & 0 & 2 & 0 & 2 & 1 & -1 & 8 & \\ \hdashline
& 0 & 0 & 0 & 0 & 0 & -1 & 0 &
\end{array}
\begin{array}{rrrrrrr|rr} & x_1 & x_2 & s_1 & s_2 & s_3 & w & & \text{ratio} \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 & - \\ w & 1^* & -1 & 0 & -1 & 0 & 1 & 4 & 4 \\ s_3 & 1 & 1 & 0 & 0 & 1 & 0 & 12 & 12 \\ \hdashline & 1 & -1 & 0 & -1 & 0 & 0 & 4 & \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 & \\ x_1 & 1 & -1 & 0 & -1 & 0 & 1 & 4 & \\ s_3 & 0 & 2 & 0 & 2 & 1 & -1 & 8 & \\ \hdashline & 0 & 0 & 0 & 0 & 0 & -1 & 0 & \end{array}
Dual simplex tableau\begin{array}{rrrrrrrr|r}
& x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline
x_4 & 0 & -3 & 7 & 1 & 0 & 0 & 2 & 2M -4 \\
x_5 & 0 & -9 & 0 & 0 & 1 & 0 & -1 & -M -3 \\
x_6 & 0 & 6 & -1 & 0 & 0 & 1 & -4^* & -4M +8 \\
x_1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline
& 0 & 1 & 1 & 0 & 0 & 0 & 2 & 2M \\
\text{ratio} & & & 1 & & & & 1/2 &
\end{array}
\begin{array}{rrrrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & -3 & 7 & 1 & 0 & 0 & 2 & 2M -4 \\ x_5 & 0 & -9 & 0 & 0 & 1 & 0 & -1 & -M -3 \\ x_6 & 0 & 6 & -1 & 0 & 0 & 1 & -4^* & -4M +8 \\ x_1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & 0 & 1 & 1 & 0 & 0 & 0 & 2 & 2M \\ \text{ratio} & & & 1 & & & & 1/2 & \end{array}
It can be stacked up to give a theoretical illustration of what happens in the upcoming steps.
\begin{array}{rrrrrrr|r} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \\ \hline s_1 & -2 & 0 & -2 & 1 & 0 & 0 & -60 \\ s_2 & -2 & -4^* & -5 & 0 & 1 & 0 & -70 \\ s_3 & 0 & -3 & -1 & 0 & 0 & 1 & -27 \\ \hdashline & 8 & 10 & 25 & 0 & 0 & 0 & 0 \\ \text{ratio} & -4 & -5/2 & -5 & & & & \\ \hline s_1 & -2^* & 0 & -2 & 1 & 0 & 0 & -60 \\ x_2 & 1/2 & 1 & 5/4 & 0 & -1/4 & 0 & 35/2 \\ s_3 & 3/2 & 0 & 11/4 & 0 & -3/4 & 1 & 51/2 \\ \hdashline & 3 & 0 & 25/2 & 0 & 5/2 & 0 & -175 \\ \text{ratio} & -3/2 & & 25/4 & & & & \\ \hline x_1 & 1 & 0 & 1 & -1/2 & 0 & 0 & 30 \\ x_2 & 0 & 1 & 3/4 & 1/4 & -1/4 & 0 & 5/2 \\ s_3 & 0 & 0 & 5/4 & 3/4 & -3/4^* & 1 & -39/2 \\ \hdashline & 0 & 0 & 19/2 & 3/2 & 5/2 & 0 & -265 \\ \text{ratio} & & & & & \dots & & \\ \hline x_1 & 1 & 0 & 1 & -1/2 & 0 & 0 & 30 \\ x_2 & 0 & 1 & 1/3 & 0 & 0 & -1/3 & 9 \\ s_2 & 0 & 0 & -5/3 & -1 & 1 & -4/3 & 26 \\ \hdashline & 0 & 0 & 41/3 & 4 & 0 & 10/3 & -330 \end{array}
DualityA picture is worth a thousand words.
$$ \require{extpfeil} % produce extensible horizontal arrows \begin{array}{ccc} % arrange LPPs % first row % first LPP \begin{array}{ll} \max & z = c^T x \\ \text{s.t.} & A x \le b \\ & x \ge 0 \end{array} & \xtofrom{\text{duality}} & % second LPP \begin{array}{ll} \min & v = b^T y \\ \text{s.t.} & A^T y \ge c \\ & y \ge 0 \end{array} \\ ({\cal PC}) & & ({\cal DC}) \\ \text{add } {\Large \downharpoonleft} \text{slack var} & & \text{minus } {\Large \downharpoonright} \text{surplus var}\\ % Change to your favorite arrow style % % second row % third LPP \begin{array}{ll} \max & z = c^T x \\ \text{s.t.} & A x + s = b \\ & x,s \ge 0 \end{array} & \xtofrom[\text{some steps skipped}]{\text{duality}} & % fourth LPP \begin{array}{ll} \min & v = b^T y \\ \text{s.t.} & A^T y - t = c \\ & y,t \ge 0 \end{array} \\ ({\cal PS}) & & ({\cal DS}) % \end{array} $$
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4