# ORF307 Precept 9


## Optimality Conditions Review
primal and dual solutions are optimal if and only if the following are true:


1.   $x$ is primal feasible
2.   $y$ is dual feasible
3.   duality gap is zero



## Primal and Dual Simplex Takeaways



*   Primal simplex maintains primal feasibility and duality gap of zero, dual becomes feasible when converges
*   Dual simplex maintains dual feasibility and dualitgy gap of zero, primal becomes feasible when converges



## Sensitivity Analysis - Adding a New Variable


1.   $(x^*,0)$ is still primal feasible
2.   Dual problem has an extra constraint, is $A^T_{n+1}y^* + c_{n+1} \ge 0$ still dual feasible? 
3.   If yes, $(x^*,0)$ is still optimal; If no, run primal simplex.



## Sensitivity Analysis - Adding a New Constraint

1.   Translates to having extra variable in dual problem, thus $(y^*,0)$ is still dual feasible
2.   Is $a^T_{m+1} x^* = b_{m+1}$ still primal feasible?
3.   If yes, $(y^*,0)$ is still optimal; If no, run dual simplex.

## Global/Local Sensitivity Analysis - Changing the Data

## Example 1

Consider the problem

$$
\begin{array}{ll}
\mbox{minimize} &-5x_1 - x_2 + 12x_3\\
\text{subject to} &3x_1 + 2x_2 + x_3 = 10\\
&5x_1 + 3x_2 + x_4 = 16\\
&x_1, \dots, x_4 \ge 0.
\end{array}
$$

An optimal solution to this problem is given by $x=(2,2,0,0)$. Suppose we change $a_{11}$ from 3 to $3 + \delta$. Keeping $x_1$ and $x_2$ as the basic variables, and let $A_B(\delta)$ be the corresponding basis matrix, as a function of $\delta$.


(a) Compute $A_B(\delta)^{-1}b$. For which values of $\delta$ is $A_B(\delta)$ a feasible basis?

(b) Compute $c_B^TA_B(\delta)^{-1}$. For which values of $\delta$ is $A_B(\delta)$ an optimal basis?

## Network Flows - Arc-Node Incidence Matrix

$m$ x $n$ matrix $A$ with entries

$$
\begin{align}
A_{ij} = \begin{cases}
1 &\mbox{if arc $j$ starts at node $i$}\\
-1 &\mbox{if arc $j$ starts at node $i$}\\
0 &\mbox{otherwise}
\end{cases}
\end{align}.
$$

Each column has one -1 and one 1

## Network Flows - Total Unimodularity

*   A matrix is totally unimodular if all its minors are -1, 0 or 1
*   Key property: the inverse of an nonsingular square submatrix of A has entires +1, -1, or 0
*   Above property, along with $b$ being an integer vector implies all the extreme points of the polyhedron $P = \{x \in \mathbf{R}^n \vert Ax=b, \mkern9mu x\ge0\}$ are integer vectors



## Example 2

A catering company must provide to a client $r_i$ tablecloths on each of $N$ consecutive days. The catering company can buy new tablecloths at a price of $p$ dollars each, or launder the used ones. Laundering can be done at a fast service facility that makes the tablecloths unavailable for the next $n$ days and cost $f$ dollars per tablecloth, or at a slower facility that makes tablecloths unavailable for the next $m$ days (with $m > n$) at a cost of $g$ dollars per tablecloth ($g<f$). The caterer's problem is to decide how to meet the client's demand at minimum cost, starting with no tablecloths and under the assumption that any leftover tablecloths have no value. Show that the problem can be formulated as a network flow problem.


81de417c2bc18979b22f1e6a7a4a42d1d04e7523
ipynb
Jupyter Notebook
precepts/09_precept/09_precept.ipynb
bpushner/ORF307
d8d337cc89e6781b7ef852c8c0f967c1bd1d629a
MIT
2021-01-12T08:56:54.000Z
2022-02-09T01:01:34.000Z
precepts/09_precept/09_precept.ipynb
bpushner/ORF307
d8d337cc89e6781b7ef852c8c0f967c1bd1d629a
MIT
precepts/09_precept/09_precept.ipynb
bpushner/ORF307
d8d337cc89e6781b7ef852c8c0f967c1bd1d629a
MIT
2021-01-31T00:44:40.000Z
2022-03-25T12:43:56.000Z
Qwen/Qwen-72B
1. YES
2. YES