<div align="center">
  <h1>Homework 5</h1>
    <p>
        <div align="center">
        <h2>Yutong Dai yutongd3@illinois.edu</h2>
        </div>
    </p>
</div>

## 5.2

Rewrite the problem in the standard form,

$$
\begin{align}
& \min \quad 2x_2  - x_3\\
& s.t \quad -x_1 + 2x_2 - x_3 + x_4 = 4\\
& \qquad x_1 + x_2 + x_3 + x_5 = 7\\
& \qquad 2x_1 -x_2 -x_3 + x_6 = 5 \\
& \qquad x_1,...,x_6\geq 0
\end{align}
$$

Note $z_j=C_B^TB^{-1}A_{.j}$

**Step 1:**

* $(c_1-z_1, c_2-z_2, c_3-z_3)=(0,2,-1)$ and $\delta=7$$\rightarrow$ Pivot on $x_5$.

|   | z | $x_4$ | $x_5$ | $x_6$ | RHS | $x_3$ |
| --- | --- | --- | --- | --- | --- | --- |
| z | -1 | 0 | 0 | 0 | 0 | -1 |
| $x_4$ | 0 | 1 | 0 | 0 | 4 | -1 |
| $x_5$ | 0 | 0 | 1 | 0 | 7 | 1 |
| $x_6$ | 0 | 0 | 0 | 1 | 5 | -1 |

**Step 2:**

* $(c_1-z_1, c_2-z_2, c_5-z_5)=(1,3,1)$. Stop 

|   | z | $x_4$ | $x_3$ | $x_6$ | RHS |
| --- | --- | --- | --- | --- | --- | 
| z | -1 | 0 | 1 | 0 |7 |  |
| $x_4$ | 0 | 1 | 1 | 0 | 11 | 
| $x_3$ | 0 | 0 | 1 | 0 | 7 |  
| $x_6$ | 0 | 0 | 1 | 1 | 12 |  

So the solution is $(0,0,7)$ and the optimal value is $7$

## 5.12

Rewrite the problem in the standard form,

$$
\begin{align}
& \min \quad x_1 + 2x_2  + x_3 - x_4\\
& s.t \quad 2x_1 - x_2 + x_3 - 2x_4 + x_5 = 6\\
& \qquad -x_1 + 2x_2 - x_3 + x_4 + x_6 = 8\\
& \qquad -2x_1 -x_2 +x_3 + x_7 = -2 \\
& \qquad 0\leq x_1\leq 3, 1\leq x_2 \leq 4, 0 \leq x_3 \leq 8, 2 \leq x_4 \leq 5 \\
& \qquad x_5,x_6,x_7 \geq 0
\end{align}
$$

**Setup the tableau as**

|  | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $x_6$ | $x_7$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | 1 | 2 | 3 | -1 | 0 | 0 | 0 | 0 |
| $x_5$ | 2 | -1 | 1 | -2 | 1 | 0 | 0 | 11 |
| $x_6$ | -1 | 2 | -1 | 1 | 0 | 1 | 0 | 5 |
| $x_7$ | -2 | -1 | 1 | 0  | 0 | 0 | 1 | 5 |
|  | 3 | 1 | 0 | 5 | 11 | 5 | 5 |  |
| lb | 0 | 1 | 0 | 2 | 0 | 0 | 0 |  |
| ub | 3 | 4 | 8 | 5 |  |  |  |  |

We can only decrease $x_1$ from its upper bound and pivot on $x_7$, $\delta=5/2$.


|  | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $x_6$ | $x_7$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | 0 | 3/2 | 7/2 | -1 | 0 | 0 | 1/2 | 5/2 |
| $x_5$ | 0 | -2 | 2 | -2 | 1 | 0 | 1 | 6 |
| $x_6$ | 0 | 5/2 | -3/2 | 1 | 0 | 0 | 1/2 | 15/2 |
| $x_1$ | 1 | 1/2 | -1/2 | 0 | 0 | 0 | -1/2 | 1/2 |
|  | 1/2 | 1 | 0 | 5 | 6 | 15/2 | 10 |  |
| lb | 0 | 1 | 0 | 2 | 0 | 0 | 0 |  |
| ub | 3 | 4 | 8 | 5 |  |  |  |  |

We are now at the optimal. The solution is $(1/2, 1,0,5)$ and the optimal value is $-5/2$.

## 5.28

Rewrite the problem in the standard form,

$$
\begin{align}
& \min \quad -3x_1  - 2x_2\\
& s.t \quad x_1 + 2x_2 + x_3  = 8\\
& \qquad x_1 + x_2 + x_4 = 5\\
& \qquad 2x_1 -x_2 -x_3 + x_6 = 5 \\
& \qquad 0\leq x_1\leq 3, 0\leq x_2 \leq 4 \\
& \qquad x_3,x_4 \geq 0
\end{align}
$$

**Setup the tableau**:

|  | $x_1$ | $x_2$ | $x_3$ | $x_4$ | RHS |
| --- | --- | --- | --- | --- | --- |
|  | -3 | -2 | 0 | 0 | 8  |
| $x_3$ | 1 | 2 | 1 | 0 | 0 |
| $x_4$ | 1 | 1 | 0 | 1 | 1 |
|  | 0 | 4 | 0 | 1 |  |
| lb | 0 | 0 | 0 | 0 |   |
| ub | 3 | 4 |   |   |  |


**Step 1**
We can increase $x_1$ from its lower bound and pivot on $x_3$. Note $\delta$=0

|  | $x_1$ | $x_2$ | $x_3$ | $x_4$ | RHS |
| --- | --- | --- | --- | --- | --- |
|  | 0 | 4 | 3 | 0 |  8 |
| $x_1$ | 1 | 2 | 1 | 0 | 0 |
| $x_4$ | 0 | -1 | -1 | 1 | 1 |
|  | 0 | 4 | 0 | 1 |  |
| lb | 0 | 0 | 0 | 0 |   |
| ub | 3 | 4 |   |   |  |

**Step 2**
We can decrease $x_2$ from its upper bound and pivot on $x_4$. Note $\delta$=1

|  | $x_1$ | $x_2$ | $x_3$ | $x_4$ | RHS |
| --- | --- | --- | --- | --- | --- |
|  | 0 | 0 | -1 | 4 | 12 |
| $x_1$ | 1 | 0 | -1 | 2 | 2 |
| $x_2$ | 0 | 1 | 1 | -1 | 3 |
|  | 2 | 3 | 0 | 0 |  |
| lb | 0 | 0 | 0 | 0 |  |
| ub | 3 | 4 |  |  |  |

**Step 3**
We can decrease $x_3$ from its lower bound and pivot on $x_1$. Note $\delta$=1


|  | $x_1$ | $x_2$ | $x_3$ | $x_4$ | RHS |
| --- | --- | --- | --- | --- | --- |
|  | -1 | 0 | 0 | 2 | -13 |
| $x_3$ | -1 | 0 | 1 | -2 | 1 |
| $x_2$ | 1 | 1 | 0 | 1 | 2 |
|  | 3 | 2 | 1 | 0 |  |
| lb | 0 | 0 | 0 | 0 |  |
| ub | 3 | 4 |  |  |  |


We stop at this point. So the solution is $(2,3)$ and the optimal value is $13$.

## 5.58

**Bounded Case**

$\Rightarrow$: Suppose $x_0$ is an extreme point has a minimal objective, then by definition, it has an objective that is smaller than or equal to that of any adjacent extreme point. Otherwise, its not the minimal.

$\Leftarrow$: Since this is a linear programming problem, we assume the objective function is $c^Tx$.

Note that for any $x\in P$, we have 

$$x=x_0 + \sum_{j=1}^k \mu_j(x_j-x_0),$$

where $P$ is a polytope and $x_0$ is an extreme points and $x_1,...,x_k$ are all of its adjacent extreme points. 

$$
c^Tx = c^Tx_0 + \sum_{j=1}^k \mu_jc^T(x_j-x_0) \geq c^Tx_0,
$$
where the inequality holds by the assumptions that $x_0$ has an objective that is smaller than or equal to that of any adjacent extreme point.

**Unbounded Case**:

Note that for any $x\in P$, we have 

$$x=x_0 + \sum_{j\in I} \mu_j(x_j-x_0) + \sum_{j\in J} \mu_jd_j$$

where 

1. $P$ is a unbounded polyhedral set.

2. $x_0$ is an extreme points and $\{x_j|j\in I\}$ are its adjacent extreme points. 

3. $\{d_j|j\in J\}$ are its adjacent extreme directions.

$$
c^Tx = c^Tx_0 + \sum_{j\in I} \mu_jc^T(x_j-x_0) +  \sum_{j\in J} \mu_jc^Td_j
$$

As it is not guaranteed that $\sum_{j\in J} \mu_jc^Td_j \geq 0$, this can not be generalized to the unbounded case.

## Exercise 3.33

Notice that the number of extreme points are finite and we can move from any basic feasible solution to an adjacent one in a single step, which means no cycling, therefore, we can go from the extreme point $x$ to another extreme point $y$ in finite number of stpes.

## (1)

**Lemma:** In the simplex method, if the variable $x_r$ is leaving the basis at the iteration $k$, then it cannot enter the basis at the iteration $k+1$.

Since the degree of the degeneracy is $1$, then the degenerated extreme points can have only two basis, which are adjacent. By the lemma above, the one out can not enter in the very next step, then there's no cycling issue.

5b10ccc5c4d77ba97bfa0662f234b63acdef2b91
ipynb
Jupyter Notebook
Python_IE411/hw5.ipynb
Rothdyt/codes-for-courses
a2dfea516ebc7cabef31a5169533b6da352e7ccb
MIT
2018-09-23T00:00:13.000Z
2018-11-02T22:56:35.000Z
Python_IE411/hw5.ipynb
Rothdyt/codes-for-courses
a2dfea516ebc7cabef31a5169533b6da352e7ccb
MIT
Python_IE411/hw5.ipynb
Rothdyt/codes-for-courses
a2dfea516ebc7cabef31a5169533b6da352e7ccb
MIT
Qwen/Qwen-72B
1. YES
2. YES