Skip to main content

Linear Optimization Modeling and Solving Linear problems with Julia and WebCAS

Peter Staab

Section 7.4 General Applied Problems

Subsection 7.4.1 Traveling Salesperson

Sylvia has to travel to 5 towns in Massachusetts: Fitchburg, Boston, Lowell, Fall River and Worcester. The following weighted graph shows the distances between every pair of towns.
🔗
Figure 7.4.1.
🔗
She wishes to travel in a manner to minimize the total distance traveled and not travel through any town more than once.
🔗
One method of solving this problem is by setting up an LOP. First, we defined all of the paths between two towns and assign it to a variable that will be 1 if she travels between the towns and 0 otherwise. In particular:
🔗
\begin{equation*} \begin{aligned} x_1 = \amp \text{travel between F and L} \\ x_2 = \amp \text{travel between F and B} \\ x_3 = \amp \text{travel between F and FR} \\ x_4 = \amp \text{travel between F and W} \\ x_5 = \amp \text{travel between L and B} \\ x_6 = \amp \text{travel between L and FR} \\ x_7 = \amp \text{travel between L and W} \\ x_8 = \amp \text{travel between B and FR} \\ x_9 = \amp \text{travel between B and W} \\ x_{10} = \amp \text{travel between FR and W} \\ \end{aligned} \end{equation*}
🔗
and each of these values will be 0 or 1. The objective function is sum of each variable times the distance between the two cities. This is to be minimized so
🔗
\begin{equation*} \begin{aligned} w = \amp 32.4 x_1 + 46.9 x_2 + 83.4 x_3 + 27.5 x_4 + 31.2 x_5 + 77.5 x_6 + 41.0 x_7 \\ \amp \qquad + 54.2 x_8 + 43.3 x_9 + 56.1 x_{10} \end{aligned} \end{equation*}
🔗
The constraints are that each town must be entered once and leave once. In terms of the variables, the sum of all variables into a town must equal 2. Thus there are the constraints:
🔗
\begin{equation*} \begin{aligned} x_1 + x_2 + x_3 + x_4 = \amp 2 \\ x_1 + x_5 + x_6 + x_7 = \amp 2 \\ x_2 + x_5 + x_8 + x_9 = \amp 2 \\ x_3 + x_6 + x_8 + x_{10} = \amp 2 \\ x_4 + x_7 + x_9 + x_{10} = \amp 2 \end{aligned} \end{equation*}
🔗
Let’s try solving this with the adapted simplex method from this chapter. A small difference that we will use is that we multiply the objective by 10 to get integer coefficients. This will keep all numbers in the tableau as integers. The simplex tableau for this problem is
🔗
\begin{equation*} \left[\begin{array}{rrrrrrrrrrr|r} 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2\\ 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 2\\ \hline 324 \amp 469 \amp 834 \amp 275 \amp 312 \amp 775 \amp 410 \amp 542 \amp 433 \amp 561 \amp 1 \amp 0\\ \end{array} \right] \end{equation*}
🔗
and recall that there are no inequalities in this, so no slack variables. We now pivot to bring 4 variables into the basis—the basis is empty currently.
🔗
\begin{equation*} \emptyset \mapsto 1 \qquad \left[\begin{array}{rrrrrrrrrrr|r} 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp -1 \amp -1 \amp -1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 2\\ \hline 0 \amp 145 \amp 510 \amp -49 \amp 312 \amp 775 \amp 410 \amp 542 \amp 433 \amp 561 \amp 1 \amp -648\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} \emptyset \mapsto 2 \qquad \left[\begin{array}{rrrrrrrrrrr|r} 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp 1 \amp 1 \amp 1 \amp -1 \amp -1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp -1 \amp -1 \amp 2 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 2\\ \hline 0 \amp 0 \amp 365 \amp -194 \amp 457 \amp 920 \amp 555 \amp 542 \amp 433 \amp 561 \amp 1 \amp -648\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} \emptyset \mapsto 3 \qquad \left[\begin{array}{rrrrr|rrrrrr|r} 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 1 \amp 1 \amp -2 \amp -1 \amp -1 \amp -1 \amp -1 \amp 0 \amp 0 \amp -2\\ 0 \amp 0 \amp 0 \amp -1 \amp 2 \amp 2 \amp 1 \amp 2 \amp 1 \amp 1 \amp 0 \amp 4\\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 2\\ \hline 0 \amp 0 \amp 0 \amp -559 \amp 1187 \amp 1285 \amp 920 \amp 907 \amp 798 \amp 561 \amp 1 \amp 82\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} \emptyset \mapsto 4 \qquad \left[\begin{array}{rrrrr|rrrrrr|r} 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 1 \amp -2 \amp -2 \amp -1 \amp -2 \amp -1 \amp -1 \amp 0 \amp -4\\ 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 2 \amp 2 \amp 2 \amp 2 \amp 0 \amp 6\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 69 \amp 167 \amp 361 \amp -211 \amp 239 \amp 2 \amp 1 \amp -2154\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} \emptyset \mapsto 5 \qquad \left[\begin{array}{rrrrr|rrrrrr|r} 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2 \amp -2 \amp -2 \amp 0 \amp -2\\ 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp -2 \amp -2 \amp 0 \amp 0 \amp -2 \amp 0 \amp -2\\ 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp 4\\ 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2 \amp 2 \amp 0 \amp 4\\ 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 2 \amp 2 \amp 2 \amp 2 \amp 0 \amp 6\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 196 \amp 584 \amp -560 \amp 340 \amp -134 \amp 2 \amp -4722\\ \end{array} \right] \end{equation*}
🔗
And now there are five variables in the basis and this finishes Stage 0. There are two infeasible variable (\(x_1, x_2\)) and so we bring the first into the basis with the leftmost negative in the 1st row (\(x_8\)) into the basis.
🔗
\begin{equation*} 8 \mapsto 1 \qquad \left[\begin{array}{rrrrrr|rrrrr|r} -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 2 \amp 0 \amp 2\\ 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp -2 \amp -2 \amp 0 \amp 0 \amp -2 \amp 0 \amp -2\\ 2 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2 \amp 2 \amp 0 \amp 4\\ 2 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4\\ \hline -560 \amp 0 \amp 0 \amp 0 \amp 0 \amp 196 \amp 584 \amp 0 \amp 900 \amp 426 \amp 2 \amp -4162\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} 6 \mapsto 2 \qquad \left[\begin{array}{rrrrr|rrrrrr|r} -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 2 \amp 0 \amp 2\\ 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2\\ 2 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp -2 \amp -2 \amp 0 \amp 0\\ 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2 \amp 2 \amp 0 \amp 4\\ 2 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp 2\\ \hline -560 \amp 196 \amp 0 \amp 0 \amp 0 \amp 0 \amp 388 \amp 0 \amp 900 \amp 230 \amp 2 \amp -4358\\ \end{array} \right] \end{equation*}
🔗
There are no infeasible variables, so Stage I is also complete and we move onto Stage II. There is a negative in the objective row, so Stage II is not complete. Forming \(\boldsymbol{x}\)-ratios for variable \(x_1\) and taking the smallest nonnegative ratio is in the 3rd row so
🔗
\begin{equation*} 1 \mapsto 3 \qquad \left[\begin{array}{rrrrr|rrrrrr|r} 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp -2 \amp 2 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2\\ 2 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp -2 \amp -2 \amp 0 \amp 0\\ 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2 \amp 2 \amp 0 \amp 4\\ 0 \amp 0 \amp -2 \amp 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2\\ \hline 0 \amp 756 \amp 560 \amp 0 \amp 0 \amp 0 \amp -172 \amp 0 \amp 340 \amp -330 \amp 2 \amp -4358\\ \end{array} \right] \end{equation*}
🔗
And this is still not feasible so bring \(x_{10}\) into the basis.
🔗
\begin{equation*} 10 \mapsto 6 \qquad \left[\begin{array}{rrrrr|rrrrrr|r} 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp -2 \amp 2 \amp 0 \amp 0 \amp 0 \amp 2\\ 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 2\\ 2 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 2\\ 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp -2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp -2 \amp 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2\\ \hline 0 \amp 426 \amp 560 \amp 0 \amp 0 \amp 330 \amp 158 \amp 0 \amp 340 \amp 0 \amp 2 \amp -4028\\ \end{array} \right] \end{equation*}
🔗
This is no optimal and the basic solution is
🔗
\begin{equation*} \boldsymbol{x} = \left[ \begin{array}{rrrrrrrrrr} 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \end{array}\right]^{\intercal} \end{equation*}
🔗
This corresponds to the path Fitchburg \(\to\) Lowell \(\to\) Boston \(\to\) Fall River \(\to\) Worcester.
🔗

Note 7.4.2.

We got a bit lucky with this problem in two ways. First, we didn’t apply the binary constraint to the variables, they just happened to fall into either 0 or 1. Secondly, as we will see later, there is no guarantee that the result is a continuous loop. As these problems get larger, the optimal solution could be multiple loops. See below to handle problems like this.
🔗
🔗
🔗

Subsection 7.4.2 Minimizing Piecewise Linear Functions

Let’s consider minimizing \(f(x) = |2x-4|\text{,}\) which has the graph:
🔗
Figure 7.4.3.
🔗
This seems obvious looking at the graph (the minimum is 0 at \(x=2\)), however, we use this to explore more difficult problems. We are going to create a feasible set with the boundary as the function and then minimize the \(y\) value in this set. More specifically,
🔗
\begin{equation*} \begin{aligned} \text{Minimize} \amp \amp w = x_2 \amp \\ \text{subject to} \amp \amp x_2 \geq -2x_1 + 4, \\ \amp \amp x_2 \geq 2x_1 - 4, \end{aligned} \end{equation*}
🔗
and no constraints on \(x_1, x_2\) so these are free variables.
🔗
We can write this in standard form as
🔗
\begin{equation*} \begin{aligned} \text{Maximize} \amp \amp z = - x_2 \amp \\ \text{subject to} \amp \amp -2x_1 - x_2 \leq -4, \\ \amp \amp 2x_1 - x_2 \leq 4, \end{aligned} \end{equation*}
🔗
and then as a simplex tableau as
🔗
\begin{equation*} \left[\begin{array}{rr|rrr|r} {\small F} \amp {\small F} \\ -2 \amp -1 \amp 1 \amp 0 \amp 0 \amp -4\\ 2 \amp -1 \amp 0 \amp 1 \amp 0 \amp 4\\ \hline 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right] \end{equation*}
🔗
Because there are free variables that are not in the basis, this is in Stage 0. The first two steps will bring these into the basis.
🔗
\begin{equation*} 1 \mapsto 3 \qquad \left[\begin{array}{rr|rrr|r} {\small F} \amp {\small F} \\ 2 \amp 1 \amp -1 \amp 0 \amp 0 \amp 4\\ 0 \amp -4 \amp 2 \amp 2 \amp 0 \amp 0\\ \hline 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} 2 \mapsto 4 \qquad \left[\begin{array}{rr|rrr|r} {\small F} \amp {\small F} \\ 4 \amp 0 \amp -1 \amp 1 \amp 0 \amp 8\\ 0 \amp 4 \amp -2 \amp -2 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 2 \amp 2 \amp 4 \amp 0\\ \end{array} \right] \end{equation*}
🔗
And now that both \(x_1\) and \(x_2\) are in the basis, Stage 0 is finished. All other variables are feasible, so Stage I is done, and there are no negatives in the objective row, so Stage II is done. The basic and optimal solution is
🔗
\begin{equation*} \boldsymbol{x} = \left[\begin{array}{rr|rr} 2 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
🔗
or the expected value of \(x_1=2\) that we can see from the plot. The next example shows this same way to set up a problem in multiple dimensions.
🔗

Example 7.4.4.

Find the minimum of \(f(x,y) = |2x-4|+|3y+9|-2\)
🔗
Solution.
Similar to the previous problem, we will set \(u_{1} = 2x-4\) and \(u_{2} = 3y+9\) and then this is the following LOP:
🔗
\begin{equation*} \begin{aligned} \text{Min.}\amp\amp w = u_{1} + u_{2} -2\amp\\ \text{s.t.}\amp\amp u_{1}\amp\geq 2x-4 \\ \amp\amp u_{1}\amp\geq -(2x-4) \\ \amp\amp u_{2}\amp\geq 3y+9 \\ \amp\amp u_{2}\amp\geq - (3y+9) \\ \amp\amp u_{1}, u_{2}\amp\geq 0 \end{aligned} \end{equation*}
🔗
and \(x\) and \(y\) are free.
🔗
This in standard form is
🔗
\begin{equation*} \begin{aligned} \text{Max.}\amp\amp z = -u_{1}-u_{2}+2 \\ \text{s.t.}\amp\amp2x -u_{1}\amp\leq 4 \\ \amp\amp -2x -u_{1}\amp\leq 4 \\ \amp\amp 3y -u_{2}\amp\leq -9 \\ \amp\amp -3y -u_{2}\amp\leq -9\\ \amp\amp u_{1}, u_{2}\amp\geq 0 \end{aligned} \end{equation*}
🔗
The initial tableau is
🔗
\begin{equation*} \left[\begin{array}{rrrr|rrrrr|r} {\small F} \amp {\small F} \\ 2 \amp 0 \amp -1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4\\ -2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp -4\\ 0 \amp 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -9\\ 0 \amp -3 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 9\\ \hline 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 2\\ \end{array} \right] \end{equation*}
🔗
where the columns are \(x, y, u_1, u_2, x_5, x_6, x_7, x_8\text{,}\) where the last four are slack variables.
🔗
Bringing \(x\) and \(y\) into the basis:
🔗
\begin{equation*} 1 \mapsto 5 \qquad \left[\begin{array}{rrrr|rrrrr|r} {\small F} \amp {\small F} \\ 2 \amp 0 \amp -1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4\\ 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 6 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp -18\\ 0 \amp -6 \amp 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 18\\ \hline 0 \amp 0 \amp 2 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 4\\ \end{array} \right] \end{equation*}
🔗
\begin{equation*} 2 \mapsto 7 \qquad \left[\begin{array}{rrrr|rrrrr|r} {\small F} \amp {\small F} \\ 6 \amp 0 \amp -3 \amp 0 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 12\\ 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 6 \amp 0 \amp 2 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp -18\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp 6 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 6 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp 12\\ \end{array} \right] \end{equation*}
🔗
Since the two free variables in the basis, we are done with State 0. Also, non-free variables are feasible, so we are done with Stage I and there are no negative in the objective row, so we are done with Stage II.
🔗
The optimal basic solution is
🔗
\begin{equation*} \boldsymbol{x} = \left[\begin{array}{rrrr|rrrr} 2 \amp -3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
🔗
Returning back to the original problem, this is \(x=2, y=-3\) with \(w=-2\text{.}\)
🔗
🔗
🔗
🔗

Subsection 7.4.3 Best-Fit Lines

A common desire is to fine a line that best fits through some data. If we have the points \(\{(1,6), (2,4), (3,3), (5,2)\}\text{,}\) then a plot of this is
🔗
Figure 7.4.5.
🔗
where the line (in red) is possible best fit line.
🔗
A common way to find the line is to minimize the error between the line and the data in a least-squares sense, in which the sum of squares of differences between the data and the line or
🔗
\begin{equation*} E = \sum_{i=1}^N (a_1 x_i +a_0 - y_i)^2 \end{equation*}
🔗
is defined. The coefficients \(a_0\) and \(a_1\) are found by finding the minimum of the function \(E\text{.}\)
🔗
An alternative way to do this is to minimize
🔗
\begin{equation} E = \sum_{i=1}^N |a_1 x_i + a_0 - y_i |\tag{7.4.1} \end{equation}
🔗

Checkpoint 7.4.6.

Find the best-fit line through \(\{(1,6), (2,4), (3,3), (5,2)\}\) by setting up an LOP and solving it.
🔗
Solution.
We will introduce new variables \(u_1, u_2, u_3, u_4 \) that will satisfies (NOT QUITE RIGHT)
🔗
\begin{equation*} -(a_1 x_i + a_0 - y_i) \leq u_i \leq a_1 x_i + a_0 - y_i \end{equation*}
🔗
then the LOP can be written as
🔗
\begin{equation*} \begin{aligned} \text{Minimize} \amp \amp w = \amp u_1 + u_2 + u_3 + u_4 \\ \text{subject to} \amp \amp u_1 \amp \geq a_1 \cdot 1 + a_0 - 6 \\ \amp \amp u_1 \amp \geq -(a_1 \cdot 1 + a_0 - 6) \\ \amp \amp u_2 \amp \geq a_1 \cdot 2 + a_0 - 4 \\ \amp \amp u_2 \amp \geq -(a_1 \cdot 2 + a_0 - 4) \\ \amp \amp u_3 \amp \geq a_1 \cdot 3 + a_0 -3 \\ \amp \amp u_3 \amp \geq -(a_1 \cdot 3 + a_0 -3) \\ \amp \amp u_4 \amp \geq a_1 \cdot 5 + a_0 -2 \\ \amp \amp u_4 \amp \geq -(a_1 \cdot 5 + a_0 -2) \end{aligned} \end{equation*}
🔗
The variables for this are \(a_0, a_1, u_1, u_2, u_3, u_4\text{.}\) The first two are free and the last are restricted since each \(u_i\) is either \(a_1 x_i + a_0 - y_i\) or its negative, so much be positive. There will be 8 slack variables as well.
🔗
If this is put in standard form (not shown) then the simplex tableau is
🔗
\begin{equation*} {\small \left[\begin{array}{rr|rrrr|rrrrrrrrr|r} -1 \amp -1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -6\\ 1 \amp 1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6\\ -2 \amp -1 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -4\\ 2 \amp 1 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4\\ -3 \amp -1 \amp 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -3\\ 3 \amp 1 \amp 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 3\\ -5 \amp -1 \amp 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -2\\ 5 \amp 1 \amp 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 2\\ \hline 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right] } \end{equation*}
🔗
where the columns are \(a_1, a_0, u_1, u_2, u_3 u_4\) (which will also be labelled \(x_1, x_2, \ldots, x_6\)) and then the slack variables \(x_7, x_8, \ldots, x_{14}\text{.}\)
🔗
There are two steps of Stage 0 to get the first two columns into the basis, \(1 \mapsto 7\) then \(2 \mapsto 9\) to
🔗
\begin{equation*} {\small \left[\begin{array}{rr|rrrr|rrrrrrrrr|r} 1 \amp 0 \amp -1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2\\ 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 1 \amp 2 \amp -1 \amp 0 \amp 0 \amp -2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 8\\ 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp -1 \amp 2 \amp -1 \amp 0 \amp 1 \amp 0 \amp -2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1\\ 0 \amp 0 \amp 1 \amp -2 \amp -1 \amp 0 \amp -1 \amp 0 \amp 2 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1\\ 0 \amp 0 \amp -3 \amp 4 \amp 0 \amp -1 \amp 3 \amp 0 \amp -4 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -4\\ 0 \amp 0 \amp 3 \amp -4 \amp 0 \amp -1 \amp -3 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 4\\ \hline 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right] } \end{equation*}
🔗
and then stage I with the pivots recalling that \(x_1, x_2\) are free variables so they don’t leave the basis. \(3 \mapsto 13\) and \(4 \mapsto 12\) to get
🔗
\begin{equation*} {\small \left[\begin{array}{rr|rrrr|rrrrrrrrr|r} 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp -1 \amp -2 \amp 0 \amp 0 \amp -2\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp -1 \amp 1 \amp 0 \amp 0 \amp 2 \amp -2 \amp -2 \amp 0 \amp 0 \amp 4\\ 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp -6 \amp 0 \amp 0 \amp 0 \amp 0 \amp -5 \amp 5 \amp 6 \amp 0 \amp 0 \amp 18\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp -2 \amp 2 \amp 3 \amp -3 \amp -2 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp 2 \amp 0 \amp 0 \amp -4 \amp 0 \amp 3 \amp -3 \amp -2 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 1 \amp -1 \amp -1 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2 \amp 4 \amp 0 \amp 4 \amp 0 \amp -5 \amp 9 \amp 6 \amp 0 \amp 4 \amp -10\\ \end{array} \right] } \end{equation*}
🔗
Now this is ready for Phase II. To move through this, \(5 \mapsto 11\text{,}\) \(6 \mapsto 10\) and then \(10 \mapsto 5\text{,}\) resulting in
🔗
\begin{equation*} { \small \left[\begin{array}{rr|rrrr|rrrrrrrrr|r} 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 1 \amp -1 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp -4\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp -3 \amp 3 \amp 4 \amp -4 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 8\\ 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp -4 \amp 0 \amp 0 \amp -5 \amp 5 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp 32\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp -2 \amp 2 \amp 3 \amp -3 \amp -2 \amp 0 \amp 0 \amp 2\\ 0 \amp 0 \amp 0 \amp 0 \amp 3 \amp 1 \amp 0 \amp 0 \amp -1 \amp 1 \amp 0 \amp -3 \amp -1 \amp 0 \amp 0 \amp 1\\ 0 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 3 \amp 0 \amp 0 \amp 1 \amp -3 \amp 0 \amp 2 \amp -2 \amp 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 4\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp 6 \amp 0 \amp 1 \amp 5 \amp 0 \amp 6 \amp 4 \amp 0 \amp 6 \amp -10\\ \end{array} \right]} \end{equation*}
🔗
And this is optimal. We can pull all of the variables, but only the first two, \(a_1=-2/3\) and \(a_0=16/3\) are needed. Thus, the best fit line in the \(L^{1}\) sense is
🔗
\begin{equation*} y = -\frac{2}{3} x + \frac{16}{3} \end{equation*}
🔗
🔗
🔗

Checkpoint 7.4.7.

Solve the LOP in ??? using Julia.
🔗
🔗
🔗
🔗
PrevTopNext