NO - Summary of Chapter 3

NO - Summary of Chapter 3 (Part I)

Given the constraints of a LP:

$$\begin{array}{rl}& \overline{\overline{A}}\cdot \overline{x}=\overline{b}\\ & \overline{x}\ge 0\end{array}$$

we can divide the matrix $\overline{\overline{A}}$ and the vector $\overline{b}$ in bases and non-bases, where:

A base $B$ is a set of linearly independent $m$ columns of $\overline{\overline{A}}$

So we can always write

$$\overline{\overline{A}}=\left[\overline{\overline{B}},\overline{\overline{N}}\right]$$

where: $\overline{\overline{B}}$ is the base of $\overline{\overline{A}}$ and $\overline{\overline{N}}$ is the non-base

So we have separate $x$ in the same way:

$$\overline{x}=\left[{\overline{x}}_B,{\overline{x}}_N\right]$$

where: ${\overline{x}}_B$ (basic variables) is the part of $\overline{x}$ that multiplies $\overline{\overline{B}}$, and ${\overline{x}}_N$ (non-basic variables) is the part that multiplies $\overline{\overline{N}}$.

Link to original

NO - Summary of Chapter 3 (Part II)

Given the base $\overline{\overline{B}}$, we can set non-basic variables ${\overline{x}}_N=0$ and compute

$${\overline{x}}_B={\overline{\overline{B}}}^{-1}\cdot \overline{b}$$

If ${\overline{x}}_B<0$ the basis is unfeasible. Else if ${\overline{x}}_B\ge 0$ the basis is feasible. → So we have that a BFS (Basic Feasible Solution) is obtained setting ${\overline{x}}_B={\overline{\overline{B}}}^{-1}\cdot \overline{b}$

NOTE: It can be proven that each vertex corresponds to a BFS

Link to original

NO - Summary of Chapter 3 (Part III)

If we have that at least one element of ${\overline{x}}_B={\overline{\overline{B}}}^{-1}\cdot \overline{b}$ is equal to $0$ than we say that this BFS is degenerate.

Geometrically if a BFS is degenerate multiple solutions correspond to the same vertex.

Link to original

NO - Summary of Chapter 3 (Part IV)

After we define $\left[{\overline{c}}_B,{\overline{c}}_N\right]$ in the same way we defined $\overline{x}=\left[{\overline{x}}_B,{\overline{x}}_N\right]$, we can write the LP:

$$\begin{array}{rl}& \min \overline{c}{}^t\cdot \overline{x}\\ & \overline{\overline{A}}\cdot \overline{x}=\overline{b}\\ & \overline{x}\ge 0\end{array}$$

as:

$$\begin{array}{rl}& \min {\overline{c}}_B{}^t\cdot {\overline{x}}_B+{\overline{c}}_N{}^t\cdot {\overline{x}}_N\\ & \overline{\overline{B}}\cdot {\overline{x}}_B+\overline{\overline{N}}\cdot {\overline{x}}_N=\overline{b}\\ & {\overline{x}}_B\ge 0\\ & {\overline{x}}_N\ge 0\end{array}$$

From the equation we obtain that:

$${\overline{x}}_B={\overline{\overline{B}}}^{-1}\cdot \left(\overline{b}-\overline{\overline{N}}\cdot {\overline{x}}_N\right)$$

So the LP becomes:

$$\begin{array}{rl}& \min {\overline{c}}_B{}^t\cdot {\overline{\overline{B}}}^{-1}\cdot \left(\overline{b}-\overline{\overline{N}}\cdot {\overline{x}}_N\right)+{\overline{c}}_N\cdot {\overline{x}}_N\\ & {\overline{x}}_B\ge 0\\ & {\overline{x}}_N\ge 0\end{array}$$Link to original

NO - Summary of Chapter 3 (Part V)

Given the basis/non-basis formulation of an LP: (dropping overlines cdots)

$$\begin{array}{rl}& \min c_B^t{B}^{-1}\left(b-N{x}_N\right)+c_N{x}_N\\ & x_N\ge 0\\ & x_N\ge 0\end{array}$$

We can say that, if $x$ is a vertex, then:

$$\begin{array}{rl}& x_B=B^{-1}b\\ & x_N=0\end{array}$$

Also one of the constraints enforces that:

$$x_N\ge 0$$

If we increase $x_N$ we have a change in the whole $A$ matrix, such that $B$ and $N$ exchange variables, so with these changes we can re-calculate $x_B=B^{-1}b-B^{-1}N{x}_N$

NOTE: $x_B$ can increase or decrease but we need to have $x_B\ge 0$ (constraint)

And find a new vertex of the problem, which might be a better solution.

Link to original

NO - Summary of Chapter 3 (Part VI)

Knowing that the objective function of the basis/non-basis formulation of an LP is:

$$\min c_B^t{B}^{-1}\left(b-N{x}_N\right)+c_N{x}_N$$

we can define a reduced cost:

$$c_N^t-c_B^t{B}^{-1}N$$

Which is the part of the objective function that changes when increasing $x_N$. Then we can say that if the reduced cost is $<0$ than there exist a descent direction of $x_N$ such that we can find a better solution. Because, multiplying the reduced cost, which we have said is $<0$ , with $x_N$, which is $\ge 0$ (because of the constraint), then the objective function will decrease, so we have found a better solution.

Link to original

NO - Summary of Chapter 3 (Part VII)

A more complex, but resource-efficient method is the pivot operation: ==Select a non-basic variable inside $x_N$ with a negative value and bring it in the basic variables ($x_B$)== As a result one of the basic variable will turn to $0$ and exit the base or the problem is unbounded.

Link to original

NO - Summary of Chapter 3 (Part VIII)

The simplex method is an easy algorithm that let us find the optimal solution to any LP.

To find a starting vertex we can use the AP (Auxiliary Problem): We take the matrix $A$ and variables $x$ from the original problem and we add $x_a$ new variables (same dimension as $x$). The AP is defined as follows:

$$\begin{array}{lc}& \min \sum x_a\\ & Ax+I{x}_a=b\\ & x\ge 0\\ & x_a\ge 0\end{array}$$

Then we have that:

• If the optimal solution of the AP is $=0$: then we have that $x$ is a vertex of the original problem.
• If the optimal solution of the AP is $>0$: then the original problem is unfeasible.

Link to original