Exercise 4.5

Question

Consider a linear programming problem in standard form and assume that the rows of $\mathbf{A}$ are linearly independent. For each one of the following statements, provide either a proof or a counterexample.
\begin{enumerate}[label=(\alph*)]
\item Let $\mathbf{x}^{*}$ be a basic feasible solution. Suppose that for every basis corresponding to $x^{*}$, the associated basic solution to the dual is infeasible. Then, the optimal cost must be strictly less than $\mathbf{c}^{\prime} \mathbf{x}^{*}$.
\item The dual of the auxiliary primal problem considered in Phase I of the simplex method is always feasible.
\item Let $p_{i}$ be the dual variable associated with the $i$ th equality constraint in the primal. Eliminating the $i$ th primal equality constraint is equivalent to introducing the additional constraint $p_{i}=0$ in the dual problem.
\item If the unboundedness criterion in the primal simplex algorithm is satisfied, then the dual problem is infeasible.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item 	extit{Let $\mathbf{x}^{*}$ be a basic feasible solution. Suppose that for every basis corresponding to $x^{*}$, the associated basic solution to the dual is infeasible. Then, the optimal cost must be strictly less that $\mathbf{c}^{\prime} \mathbf{x}^{*}$.}
ewline
  	extbf{True.} Suppose for the sake of contradiction that $\mathbf{c}^{\prime}\mathbf{x}^*$ is the optimal cost of the problem. In other words, $\mathbf{x}^*$ is an optimal solution for the primal problem. Then the associated solution $\mathbf{p} := \mathbf{c}^{\prime}\mathbf{B}^{-1}$ for a basis $\mathbf{B}$ of $\mathbf{x}^*$ must be an optimal solution for the dual problem (cf. Theorem 4.4). This is a contradiction to the original assumption that for every basis corresponding to $\mathbf{x}^{*}$, the associated basic solution to the dual is infeasible.
  
\item 	extit{The dual of the auxiliary primal problem considered in Phase I of the simplex method is always feasible.}
ewline
  	extbf{True.} Recall that the auxiliary problem of the two-phase simplex method always has a solution, i.e, the auxiliary problem is always feasible. Furthermore, the objective function, which is the sum of the artificial variables, is always non-negative; thus, the auxiliary problem is a bounded minimization problem. These two facts imply that the auxiliary problem always possesses an optimal solution. By the strong duality (Theorem 4.4), the dual problem must have an optimal solution as well and is thus also feasible.
  
\item 	extit{Let $p_{i}$ be the dual variable associated with the $i$ th equality constraint in the primal. Eliminating the $i$ th primal equality constraint is equivalent to introducing the additional constraint $p_{i}=0$ in the dual problem.}
ewline
  	extbf{True.} Removing an equality constraint, we reduce the dimension $m$ of the dual problem to $m-1$. In other words, we remove $p_i \mathbf{a}_i$ from the constraint $\sum_{j=1}^{m}p_j\mathbf{a}_{j} \leq \mathbf{c}$, and we remove $p_ib_i$ from the objective value $\sum_{j=1}^{m}p_jb_j$. Notice that removing $p_i$ from those terms is result-wise equivalent to setting $p_i$ to zero.
  
\item 	extit{If the unboundedness criterion in the primal simplex algorithm is satisfied, then the dual problem is infeasible.}
ewline
  	extbf{True.} Of the primal is unbounded, its optimal cost is $-\infty$. By the weak duality (Corollary 4.1), the only possible case is for the dual to be infeasible.
  
\end{enumerate}

Exercise 4.5

Answers

Comments

Exercise 4.5

Answers

Comments

Add answer