Problem 1

Determine whether the following statements are true or false, and explain why.

(1) For a standard linear programming problem with n variables and m constraints, the number of basic feasible solutions is $\binom{n}{m}$.

• False. For different bases, we may get the same basic feasible solution. For example, $\begin{bmatrix} 1 & 1 &1 \\ 1& 2 &3\end{bmatrix}x=\begin{bmatrix}1\\1\end{bmatrix},x\ge0$ can get a basic feasible solution $(1,0,0)$ from $\{x_1,x_2\}$ and $\{x_1,x_3\}$.

(2) The optimal solution to a linear programming problem must be a basic feasible solution.

• False. If the optimal solution is on a line of the constraint set, the optimal solution may not be basic, as the extreme points are finite and optimal solutions are infinite.

(3) If a linear programming problem has a feasible solution, the feasible region must contain the origin.

• False. If the origin is not in the constraint set, it can't be in the feasible region.

(4) If a linear programming problem has a feasible solution, then the feasible region of the problem is a convex set.

• True. Consider $F=\{x|Ax=b,x\ge0\}$ is the feasible region of a linear programming problem. Let $x,y\in F,t\in[0,1]$, we have $A(tx+(1-t)y)=tAx+(1-t)Ay=b$ and $tx+(1-t)y\ge t\cdot0+(1-t)\cdot 0=0$, which means $tx+(1-t)y\in F$. So $F$ is a convex set.

Problem 2

Consider the following linear programming problem:

        where $X^0$ is the optimal solution to the problem. If the objective function coefficient $C$ is replaced by $C^*$, and the optimal solution changes to $X^*$, prove that:

• As $X^0$ is the optimal solution to $C$ and $X^*$ is the optimal solution to $C^*$, we have $CX^0\ge CX^*$ and $C^*X^*\ge C^*X^0$. So $CX^0+C^*X^*\ge CX^*+C^*X^0$, which means $(C^*-C)(X^*-X^0)\ge0$.

Problem 3

Prove: $\sigma < 0\rightarrow$The current basic feasible solution has a higher objective value than all neighboring basic feasible solutions, thus the current solution is optimal.

• Following the assumption in PPT, we know that we can write the basis chosen as $(a_1,\dots,a_m)$, and $\sigma_j<0,\forall j$, which means for all neighboring way to change the basis $(a_1,\dots,a_m)$ to $(a_1,\dots,a_{l-1},a_{j},a_{l},\dots,a_m)$, we have $z^{(1)}-z^{(0)}=\theta\sigma_j<0$, thus objective function will decrease. As the bases is corresponding to the basic feasible solutions, we know that the current basic feasible solution has a higher objective value than all neighboring basic feasible solutions. And as the objective function is linear and the feasible region is convex, the local optimum must be a global optimum, thus the current solution is optimal.

Problem 4

For the following linear programming problem, determine all basic solutions, explain whether these basic solutions are basic feasible solutions, and plot each basic feasible solution on the feasible region’s graph.

subject to:

• Transform this problem to the stardard form, we have that:

, which can be written as

By calculating, we can get all basic solutions $(4,6,-17,0,0)$, $(-4.5,6,0,-8.5,0)$, $(4,1/3,0,0,17/3)$, $(4,0,1,0,6)$, $(4.5,0,0,0.5,6)$, $(0,6,-9,-4,0)$, $(0,3,0,-4,3)$, $(0,0,9,-4,6)$. And as $x\ge0$, $(4,1/3,0,0,17/3)$, $(4,0,1,0,6)$ and $(4.5,0,0,0.5,6)$ are three basic feasible solutions. Consider the feasible region in $\R^2$, we have three basic feasible solutions as $(4,1/3),(4,0),(4.5,0)$.

Problem 5

Use the Simplex Method to solve the following linear programming problems, and identify to which class the solution belongs.

• First convert it into standard form:

So we have coefficient matrix $A$ and feasible basis $B_1$:

So, we can draw table:

Notice that in $(3)$, $\sigma_7>0$ and $\mathbf a_7\leq0$, which means the problem is unbounded.

Problem 6

Use both the Big M method and the Two-Phase method to solve the following linear programming problems and identify which class the solution belongs to.

• Big M method: Convert it into M-method form:

Then, we can draw table:

As the optimal solution is $x^*=(1.5,0,1.5,0,0,0,0.5)^T$, still having $s_4$, which means that there is no feasible solution for the problem.

• Two-Phase method:

First phase:

As the optimal solution still has $s_4$, there is no feasible solution for the problem.

Problem 7

Given a linear programming problem that maximizes the objective function and contains two decision variables, its feasible region is shown in the figure below. Write the basic solution of the linear programming problem in vector form as $[x\enspace s]^T$, where $x$ and $s$ represent decision variables and slack variables, respectively. Explain why this linear programming problem exhibits degeneration.
(Hint: You can analyze the basic solution written, or explain from the perspective of the graph.)

• Notice that the point $(4,2)$ lies on three different lines, which means that it is constrained by three constraints. As we only have two decision variables, the basic solution $[4\enspace 2\enspace 0]^T$ can be generated by any two of these three constraints, which means that at least one of the slack variables must be $0$, thus this linear programming problem exhibits degeneration.