Linear Optimization Modeling and Solving Linear problems with Julia and WebCAS

The first issue that may arise is that the problem doesn’t have a solution because the feasible set is unbounded. Recall that bounded and unbounded feasible sets were discussed in Subsection 1.1.3. Consider the following LOP

We will use the simplex method to solve this. First, this problem is in standard form and we can write the initial tableau as

Since there are negatives in the last column, this tableau is infeasible and we can use phase I to solve it. To do this, select the row with the most negative in the last column or row 3. Thus the leaving variable in \(x_5\text{.}\) The entering variable is the leftmost negative parameter in the row. This occurs in the first column, so \(x_1\) is the entering variable.

There is still a negative in the last column (in the first row) and we take \(x_3\) as the leaving variable and the leftmost negative parameter in this row in is column 2, so we do a tableau pivot:

And noting that there are no negatives in the last column, so we are out of phase I and move to phase II. There is a negative in the objective row (column 5), so we do the \(\boldsymbol{b}\)-ratios, however, there are no positive \(\boldsymbol{b}\)-ratios. This is an indication that the problem is unbounded.

We can look at this geometrically with a plot of the feasible set.

It appears that the feasible set \(F\) is unbounded. Another way to look at this is if we look at the line \(y=x\) parametrically as \(x=t\text{,}\) \(y=t\text{,}\) then the line is in the feasible set if it is above the line \(x_5=0\text{,}\) which occurs when \(t \geq 75/8\text{.}\) Using this line, the objective function is \(z = 8t\text{,}\) which is unbounded as \(t \to \infty\text{.}\)

The other issue that can pop up is that the problem is infeasible, meaning that there is no feasible set (that is an empty set). Consider the following problem which is nearly the same, but importantly different than that in Problem 3.4.1

Let’s use the simplex method to solve this. First, this is in standard form, so we can write the tableau as

and we note that there is a negative in the last column, so this tableau is infeasible and we need to use phase I of the simplex method. The largest negative is in the third row, so \(x_5\) is the leaving variable. The leftmost negative parameter in this row is in column 1, so \(x_1\) is the entering variable. Perform the following tableau pivot:

and this last column still has a negative, so we’re still in phase I. We look at the second row (with the only negative number in the last column) thus \(x_4\) is the leaving variable and select the only negative parameter in that row or column 2, so \(x_2\) is the entering variable. We perform the tableau pivot:

and we note that there is still a negative in the last column, so still in phase I and note that this occurs in row 1, so \(x_3\) would be the leaving variable. However, there are no other negatives in this row, so no pivot will get this out of infeasibility. This happens when problem is infeasible.

Let’s take a look at the feasible set:

Notice that all regions of the plane are crossed out, so there is no feasible set.

And to examine the Simplex Method in this case, recall that at the beginning the basic solution is at the origin. The first step of \(1 \mapsto 5\) moves the basic solution to the point \((25,0)\text{.}\) The next step of \(2 \mapsto 4\) moves the basic solution to the intersection of \(x_3=0\) and \(x_5=0\) near the point \((10,8)\text{.}\) And as noted, no further pivots will get the solution to be feasible.