\documentclass[11pt]{article}
%\baselineskip 16pt
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\def\qed{\hfill $\Box$\medskip}

\def\IR{{\mathbb R}}
\def\IC{{\mathbb C}}
\def\IF{{\mathbb F}}
\def\II{{\mathbb I}}
\def\IN{{\mathbb N}}
\def\IQ{{\mathbb Q}}
\def\IZ{{\mathbb Z}}
\def\cB{{\mathcal B}}
\def\cR{{\mathcal R}}
\def\cF{{\mathcal F}}
\def\bC{{\bf C}}
\def\bP{{\bf P}}
\def\bM{{\bf M}}
\def\bd{{\bf d}}\def\({\left (}
\def\){\right )}
\def\logm{{\prec_{\rm log}}\,}
\def\diag{{\rm diag}\,}
\def\tr{{\rm tr}\,}
\def\rank{{\rm rank}\,}
\def\span{{\rm span}\,}
\def\dfrac{\displaystyle\frac}
\pagestyle{empty}
\begin{document}
\openup 1.2\jot

\noindent{\bf
Math 323 Operations Research \qquad Notes on Chapter 4.
\rm \hfill C.K. Li}


\medskip\noindent
{\bf The Simplex Algorithms}

\noindent
{\bf \S 4.1 - 4.6 The basic procedures and the theory behind}

\medskip\noindent
{\bf Standard form}

To apply simplex method, we will first change the problem
to a standard form:
$$\max Z = c_1 x_1 + \cdots + c_m x_n$$
Subject to
$$a_{i1} x_1 + \cdots + a_{in} x_n = b_i, \qquad i = 1, \dots, m.$$
$$x_1,\dots, x_n \ge 0. \hskip .5in \ $$

\begin{itemize}
\item For
$$\min Z = c_1 x_1 + \cdots + c_n x_n$$
we can change it to 
$$\max (-Z) = -(c_1x_1 + \cdots + c_n x_n).$$

\item For the inequalities 
$$c_{i1} x_1+ \cdots + c_{in} x_n \le b_i, \quad i = 1, \dots, p,$$
we can add slack variables $s_1,\dots, s_p \ge 0$ to get
$$c_{i1} x_1+ \cdots + c_{in} x_n + s_i = b_i, \quad i =1, \dots, p.$$

\item For the inequalities
$$c_{i1} x_1+ \cdots + c_{in} x_n \ge b_i, \quad i = p+1, \dots, m,$$
we can subtract excess variables $e_{p+1}, \dots, e_m \ge 0$ to get
$$c_{i1} x_1+ \cdots + c_{in} x_n - e_i = b_i, \quad i = p+1, \dots, m.$$


\end{itemize}

\medskip\noindent
{\bf Simplex algorithm when $m \le n$}

\medskip\noindent
Step 1. Start with a basic feasible solution ({\bf if it exists}).


\medskip\noindent
Step 2. Improve the basic feasible solution by finding another basic solution ({\bf if possible}) by 

\qquad changing  one of the basic variable
to go to an adjacent basic solution.

\medskip\noindent
Step 3. Repeat Step 2 until we cannot improve our solution.

\newpage
\medskip\noindent
{\bf Example}   \hskip 1.2in
$\max Z = 5x_1 + 2x_2 + 3x_3 - x_4 + x_5$

\hskip .7in
Subject to:
$$ x_1 + 2x_2 + 2x_3 + x_4  \qquad = 8$$
$$ 3x_1 + 4x_2 + x_3 + \quad + x_5 = 7$$
$$\qquad x_1, \dots, x_5 \ge 0.$$

\medskip\noindent
Step 1. Let  $(x_4,x_5)  = (8,7)$, $x_1 = x_2 = x_3 = 0.$

\medskip\noindent
Step 2. Let us bring in the nonbasic variable $x_1$, and consider
$$x_1 + x_4 = 8, \quad 3x_1 + x_5 = 7.$$

Increase $x_1 = 1$ to get the solution $(x_1, x_4, x_5) = (1,7,4)$
and $x_2 = x_3 = 0$.

The change in $Z$ value:
$$[5(1) + 2(0) + 3(0) -1(7) + 1(4)] -
[5(0) + 2(0) + 3(0) -1(8) + 1(7)] = 2 - (-1) = 3,$$

which is an improvement known as  the relative 
profit of the nonbasic variable $x_1$.

The maximum change limited by the change of $x_4, x_5$:

\medskip
\centerline{ $x_1 + x_4 = 8$ implies $x_1 \le 8$; \quad
$3x_1 + x_5 = 7$ implies $x_1 \le 7/3$.}

\medskip
So, we may consider the new basic solution $(x_1, x_4) = (7/3, 17/3)$
and $x_2 = x_3 = x_5 = 0$. 

The value $Z$ will increase by $(7/3)*3 = 7$.

Now repeat Step 2 if we can improve.

\medskip\noindent
Step 3.
If we cannot improve for any adjacent basic feasible solution,
then we get an optimal 

\quad solution. ({\bf Proof?})

\newpage
\noindent
{\bf Simplex methods in Tableau form}

\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(+5)x_1$&$(+2)x_2$&$(+3)x_3$&$(-1)x_4$
&$(+1)x_5$&{\rm constraints} \\
\hline
$-1$ & $x_4$ & 1 & 2 & 2 & 1 & 0 & 8\\
1  & $x_5$ & 3 & 4 & 1 & 0 & 1 & 7\\
\hline
\end{tabular}
}
$$Z = (-1,1) \begin{pmatrix} 8\cr 7\cr\end{pmatrix} = -1.$$
Check the relative profits for different nonbasic variables:
$$\tilde C_1 = 5 - (-1,1)\begin{pmatrix}1\cr 3\cr\end{pmatrix} = 3, 
\quad
\tilde C_2 = 2 - (-1,1)\begin{pmatrix}2\cr 4\cr\end{pmatrix} = 0, 
\quad
\tilde C_3 = 3 - (-1,1)\begin{pmatrix}2\cr 1\cr\end{pmatrix} = 4. 
$$
We can include the information in the tableau.

\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(+5)x_1$&$(+2)x_2$&$(+3)x_3$&$(-1)x_4$
&$(+1)x_5$&{\rm constraints} \\
\hline
$-1$ & $x_4$ & 1 & 2 & 2 & 1 & 0 & 8\\
1  & $x_5$ & 3 & 4 & 1 & 0 & 1 & 7\\
\hline
& $\tilde C$  & 3 & 0 & 4 & 0 & 0 & $Z= -1$\\
\hline
\end{tabular}
}

\medskip
\noindent
Because $\tilde C_3$ is largest, we bring in the nonbasic variable $x_3$.

\medskip
\noindent
The limit for $x_3$ increase is determined by the quotients of the 
entries in $\begin{pmatrix} x_4 \cr x_5\cr\end{pmatrix} = 
\begin{pmatrix} 8 \cr 7 \cr\end{pmatrix}$
divided by those of the vector under $x_3$ 
yielding $\begin{pmatrix} 8/2 \cr 7/1\cr \end{pmatrix}$.
So, we can increase $x_3$ by 4, and change $x_4$ to 0.

\medskip
\noindent
We can now update the tableau to by Gaussian elimination:


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(+5)x_1$&$(+2)x_2$&$(+3)x_3$&$(-1)x_4$
&$(+1)x_5$&{\rm constraints} \\
\hline
3 & $x_3$ & 1/2 & 1 & 1 & 1/2 & 0 & 4\\
1  & $x_5$ & 5/2 & 3 & 0 & -1/2 & 1 & 3\\
\hline
& $\tilde C$ & 1 & -4 & 0 & -2 & 0 & $Z= 15$\\
\hline
\end{tabular}
}


\medskip
\noindent
So, we can use $x_1$ as a basic variable. The increase of
$x_1$  is limited by 
$$8 \hbox { for } x_3,  \qquad   6/5  \hbox{ for } x_5.$$
We can increase $x_1 = 6/5$ and decrease $x_5 = 0$.

\medskip
\noindent
Update the tableau to by Gaussian elimination:


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(+5)x_1$&$(+2)x_2$&$(+3)x_3$&$(-1)x_4$
&$(+1)x_5$&{\rm constraints} \\
\hline
3 & $x_3$ & 0 & 2/5 & 1 & 3/5 & -1/5 & 17/5\\
5  & $x_1$ & 1 & 6/5 & 0 & -1/5 & 2/5 & 6/5\\
\hline
& $\tilde C$ &  0 & -26/5 & 0 & -9/5 & -2/5 & $Z= 81/5$\\
\hline
\end{tabular}
}

\medskip\noindent
As $\tilde C$ are all non-positive, we have an optimal solution.

\newpage
\noindent
{\bf Summary of Computational Steps}

\noindent
\begin{itemize}
\item[{\bf Step 1}]
Set up the problem in the standard form

\medskip
$\max Z = c \cdot x = (c_1, \dots, c_n)\cdot (x_1, \dots, x_n) = c_1x_1 +
\cdots + c_nx_n$

\medskip
Subject to  \qquad  $A x = b$ for an $m\times n$ matrix $A = (a_{ij})$ and $b \in \IR^m$.
$$x_1, \dots, x_n \ge 0.$$

\item[
{\bf Step 2}]
Find a feasible solution using $m$ basic variables, corresponding to the columns of 
$A$ forming the invertible matrix $B$.
In fact, if we know $B$, the center part of the updated tableau 
(without the first and last row, the first
and last column) has the form 
$$B^{-1}[A|b].$$

\item[
{\bf Step 3}] 
Compute $\tilde C$ vector. Again, it will be of the form $\tilde C = c - (c_B)B^{-1}A$.

\item[
{\bf Step 4}]
If $\tilde c$ is non-positive, then we have the optimal solution.

\medskip
Otherwise, go to Step 5.

\item[
{\bf Step 5}] Let $\tilde c_i$ be the maximum value in $\tilde c$ corresponding 
to the $i$th nonbasic variable, and let $A_i$ be the $i$th column of $A$.

\medskip
Let $B^{-1}b = \tilde b = (\tilde b_1, \dots, \tilde b_m)^T$
and $B^{-1} A_i = (\tilde a_1, \dots, \tilde a_n)^T$.
Then the reduced system with the potential new basic variable has 
augmented matrix 
$$[\tilde a | I_m | \tilde b]$$
In case all $\tilde a_i \le 0$, then we can increase $x_i$ as much as possible,
and we will get an {\bf unbounded} solution.

\medskip
If $\tilde a_j > 0$ for some $j = 1, \dots, m$, let 
$\tilde b_j/\tilde a_j$
be the maximum and replace the the basic variable $x_j$ by the nonbasic variable $x_i$.

\medskip
Return to Step 2. 

\end{itemize}
\newpage
\medskip\noindent
{\bf Example (of unbounded solution)} If in a maximization problem involving 
$x_1, \dots, x_5 \ge 0$ satisfying 2 equations.

Suppose  $(x_1, x_2, x_3, x_4, x_5) = (0,0,0,8,7)$ is a basic feasible solution.
If $\tilde C_1 = 1 > 0$ and the reduced system is
$$-x_1 + x_4 = 8, \qquad -3x_1 + x_5 = 7.$$
Then we can increase $x_1$ indefinitely, and conclude that we have an unbounded 
solution.

\medskip\noindent
{\bf Example of unbounded solution arising in the iteration process}

\medskip\centerline{
\begin{tabular}{|c|c| c c c c  |c|}
\hline 
$C_B$ & $B$ & $(2)x_1$ & $(+3)x_2$ & $(+0)x_3$ & $(+0)x_4$
&  {\rm constraints} \\
\hline
0 & $x_3$ & 1 & -1 &  1 & 0  & 2\\
0 & $x_4$ & -3 & 1 &  0 & 1  & 4\\
\hline
& $\tilde C$ &  2 & 3 & 0 & 0 & $Z= 0$\\
\hline
\end{tabular}
}

\medskip\centerline{
\begin{tabular}{|c|c| c c c c  |c|}
\hline 
$C_B$ & $B$ & $(2)x_1$ & $(+3)x_2$ & $(+0)x_3$ & $(+0)x_4$
&  {\rm constraints} \\
\hline
0 & $x_3$ & -2 & 0 &  1 & 1  & 6\\
3 & $x_2$ & -3 & 1 &  0 & 1  & 4\\
\hline
& $\tilde C$ &  11 & 0 & 0 & -3 & $Z= 12$\\
\hline
\end{tabular}
}

\bigskip
\noindent
\bf Special cases one may encounter

\medskip\noindent
Alternate Optima

\rm
Suppose the iteration leads to:

\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(+3)x_1$ &$(+2)x_2$ & $(+0)x_3$ &$(+0)x_4$
&$(+0)x_5$& {\rm constraints} \\
\hline
0 & $x_3$ & 0 & 0 & 1 & -1/5 & 8/5 &  6\\
2 & $x_2$ & 0 & 1 & 0 & 1/5 & -3/5 & 1\\
3 & $x_1$ & 1 & 0 & 0 & 1/5 & 2/5 & 4\\
\hline
& $\tilde C$ &  0 & 0 & 0 & -1 & 0 & $Z= 14$\\
\hline
\end{tabular}
}

\medskip
The non-basic variable $x_5$ has zero relative profit. 
We can use it to replace $x_3$ and get

\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(+3)x_1$ &$(+2)x_2$ & $(+0)x_3$ &$(+0)x_4$
&$(+0)x_5$& {\rm constraints} \\
\hline
0 & $x_5$ & 0 & 0 & 5/8 & -1/8 & 1 &  15/4\\
2 & $x_2$ & 0 & 1 & 3/8 & 1/8 & 0 & 13/4\\
3 & $x_1$ & 1 & 0 & -1/4 & 1/4 & 0 & 5/2\\
\hline
& $\tilde C$ &  0 & 0 & 0 & -1 & 0 & $Z= 14$\\
\hline
\end{tabular}
}

\medskip\noindent{\bf Unique optimum}

\medskip
If all the non-basic variables has negative relative profit, then 
the problem has a unique solution.

\medskip\noindent


\newpage
\bigskip\noindent
{\bf Ties in the selection of non-basic variable}

\medskip
Suppose $\tilde c_i$ is maximum and in the selection of basic variable $x_j$ to be
replaced, there are ties in the minimum ratio $\tilde b_j/\tilde a_j$, then 
we can choose any one of the $x_j$ to be replaced. 

\medskip
Other degeneracy occurs when a basic variable $x_i = 0$. Then a change of basic variable
may lead to no improvement even if we apply the simplex algorithm.

\medskip\noindent
{\bf Example}

{\hfill
\begin{tabular}{|c|c| c c c c c c |c|}
\hline 
$C_B$ & $B$ & $(0)x_1$ & $(+0)x_2$ & $(+0)x_3$ & $(+2)x_4$
& $(+0)x_5$ & $(+3/2) x_6$ & {\rm constraints} \\
\hline
0 & $x_1$ & 1 & 0 & 0 & 1* & -1 & 0 & 2\\
0 & $x_2$ & 0 & 1 & 0 & 2 & 0 & 1 & 4\\
0 & $x_3$ & 0 & 0 & 1 & 1 & 1 & 1 & 3\\
\hline
& $\tilde C$ &  0 & 0 & 0 & 2 & 0 & 3/2& $Z= 0$\\
\hline
\end{tabular}
}

\medskip{\hfill
\begin{tabular}{|c|c| c c c c c c |c|}
\hline 
$C_B$ & $B$ & $(0)x_1$ & $(+0)x_2$ & $(+0)x_3$ & $(+2)x_4$
& $(+0)x_5$ & $(+3/2) x_6$ & {\rm constraints} \\
\hline
2 & $x_4$ & 1 & 0 & 0 & 1 & -1 & 0 & 2\\
0 & $x_2$ & -2 & 1 & 0 & 0 & 2* & 1 & 0\\
0 & $x_3$ & -1 & 0 & 1 & 0 & 2 & 1 & 1\\
\hline
& $\tilde C$ &  -2 & 0 & 0 & 0 & 2 & 3/2& $Z= 4$\\
\hline
\end{tabular}
}

\medskip{\hfill
\begin{tabular}{|c|c| c c c c c c |c|}
\hline 
$C_B$ & $B$ & $(0)x_1$ & $(+0)x_2$ & $(+0)x_3$ & $(+2)x_4$
& $(+0)x_5$ & $(+3/2) x_6$ & {\rm constraints} \\
\hline
2 & $x_4$ & 0 & 1/2 & 0 & 1 & 0 & 1/2 & 2\\
0 & $x_5$ & -1 & 1/2 & 0 & 0 & 1 & 1/2 & 0\\
0 & $x_3$ & 1 & -1 & 1 & 0 & 0 & 0 & 1\\
\hline
& $\tilde C$ &  0 & -1 & 0 & 0 & 2 & 1/2& $Z= 4$\\
\hline
\end{tabular}
}

\begin{itemize}
\medskip\item
Two more iterations yield $(x_1, x_4, x_6) = (1,1,2)$ 
as the optimal solution with $Z = 5$.

\medskip\item
In really bad situation, we might even have cycling issue. 

\medskip\item
In practice, we are safe if basic feasible solutions always have positive entries
(non-degenerate problems).

\medskip\item
As long as there is a positive $\tilde c_i$, we should try to improve the solution
though 
it might increase the number of steps
in the calculation, but it will not affect the optimal value $Z$.
\end{itemize}

 
\newpage
\noindent{\bf \S 4.12 Finding an initial solution - Big M method, and detecting 
infeasible problem}

Suppose we solve an LP problem
$$ \max Z = c_1 x_1 + \cdots + c_nx_n$$
subject to 
$$Ax = b, \qquad x_1, \dots, x_n \ge 0,$$
where $A$ is $m\times n$ with $m \le n$.

If we have no obvious initial basic feasible solution,
we can introduce artificial variable $a_1, \dots, a_r \ge 0$ 
and study the problem
$$\max Z = c_1x_1 + \cdots + c_n x_n - M(a_1+ \cdots + a_r)$$
subject to 
$$a_{i1}x_1 + \cdots + a_{in} x_n + a_i = b_i, \qquad i \in R,$$
$$a_{i1}x_1 + \cdots + a_{in}x_n = b_j,  \qquad i \notin R,$$
$$x_1, \dots, x_n, a_1, \dots, a_r \ge 0$$
for a very large $M > 0$, and a suitable subset of $R \subseteq \{1, \dots, m\}$.

\bigskip\noindent
{\bf Example}  $\max Z = 2x_1 + 3x_3$ subject to 

\medskip
\hskip 1in $x_1 + x_2 \le 8$, 
\quad $x_1+3x_2 \ge 20$, \quad $x_1, x_2 \ge 0$. 

\medskip
\noindent
Then ...

\vskip 1in 

\bigskip \noindent
If we cannot get rid to the artificial variable $a_1, \dots, a_n$ at the end of the 
process, we have an infeasible problem!

\newpage
\bigskip\noindent
{\bf An example of using big M method for a minimization problems}

Consider $\min Z = -3x_1+x_2+x_3 + Mx_6 + Mx_7$

\smallskip\noindent
subject to 
 
\smallskip $x_1-2x_2+x_3 \le 11, \quad -4x_1+x_2+2x_3 \ge 3,
\quad 2x_1 - x_3 = -1,$ \quad $x_1, x_2, x_3 \ge 0$. 


\medskip
\noindent
Adding slack variable $x_4 \ge 0$, excess variable $x_5 \ge 0$
and artificial variables $x_6, x_7 \ge 0$, we get an initial 
basic feasible solution.


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(-3)x_1$ & $(+1)x_2$ & $(+1)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+M) x_6$ & $(+M)x_7$ & {\rm constraints} \\
\hline
0 & $x_4$ & 1 & -2 & 1 & 1 & 0 & 0 & 0 & 11\\
M & $x_6$ & -4 & 1 & 2 & 0 & -1 & 1 & 0 & 3\\
M & $x_7$ & -2 & 0 & 1* & 0 & 0 & 0 & 1 & 1\\
\hline
& $\tilde C$ &  -3+6M & 1-M & 1-3M & 0 & M & 0 & 0& $Z= 4M$\\
\hline
\end{tabular}
}


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(-3)x_1$ & $(+1)x_2$ & $(+1)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+M) x_6$ & $(+M)x_7$ & {\rm constraints} \\
\hline
0 & $x_4$ & 3 & -2 & 0 & 1 & 0 & 0 & -1 & 10\\
M & $x_6$ & 0 & 1* & 0 & 0 & -1 & 1 & -2 & 1\\
1 & $x_3$ & -2 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\
\hline
& $\tilde C$ &  -1 & 1-M & 0 & 0 & M & 0 & 3M-1& $Z= M+1$\\
\hline
\end{tabular}
}


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(-3)x_1$ & $(+1)x_2$ & $(+1)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+M) x_6$ & $(+M)x_7$ & {\rm constraints} \\
\hline
0 & $x_4$ & 3* & 0 & 0 & 1 & -2 & 2 & -5 & 12\\
1 & $x_2$ & 0 & 1 & 0 & 0 & -1 & 1 & -2 & 1\\
1 & $x_3$ & -2 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\
\hline
& $\tilde C$ &  -1 & 0 & 0 & 0 & 1 & M-1 & M+1& $Z= 2$\\
\hline
\end{tabular}
}


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(-3)x_1$ & $(+1)x_2$ & $(+1)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+M) x_6$ & $(+M)x_7$ & {\rm constraints} \\
\hline
-3 & $x_1$ & 1 & 0 & 0 & 1/3 & -2/3 & 2/3 & -5/3 & 4\\
1 & $x_2$ & 0 & 1 & 0 & 0 & -1 & 1 & -2 & 1\\
1 & $x_3$ & 0 & 0 & 1 & 2/3 & -4/3 & 4/3 & -7/3 & 9\\
\hline
& $\tilde C$ &  0 & 0 & 0 & 1/3 & 1/3 & M-1/3 & M-2/3& $Z= -2$\\
\hline
\end{tabular}
}
\newpage
\noindent
{\bf \S 4.13 The two-phase method}


\medskip\noindent
{\bf Phase one}

\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(0)x_1$ & $(0)x_2$ & $(0)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+1) x_6$ & $(+1)x_7$ & {\rm constraints} \\
\hline
0 & $x_4$ & 1 & -2 & 1 & 1 & 0 & 0 & 0 & 11\\
1 & $x_6$ & -4 & 1 & 2 & 0 & -1 & 1 & 0 & 3\\
1 & $x_7$ & -2 & 0 & 1* & 0 & 0 & 0 & 1 & 1\\
\hline
& $\tilde C$ &  6 & -1 & -3 & 0 & 1 & 0 & 0& $Z= 4$\\
\hline
\end{tabular}
}


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(0)x_1$ & $(+0)x_2$ & $(+0)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+1) x_6$ & $(+1)x_7$ & {\rm constraints} \\
\hline
0 & $x_4$ & 3 & -2 & 0 & 1 & 0 & 0 & -1 & 10\\
1 & $x_6$ & 0 & 1* & 0 & 0 & -1 & 1 & -2 & 1\\
0 & $x_3$ & -2 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\
\hline
& $\tilde C$ &  -1 & -1 & 0 & 0 & 1 & 0 & 3& $Z= 1$\\
\hline
\end{tabular}
}


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c c c|c|}
\hline 
$C_B$ & $B$ & $(0)x_1$ & $(+0)x_2$ & $(+0)x_3$ & $(+0)x_4$
& $(+0)x_5$ & $(+1) x_6$ & $(+1)x_7$ & {\rm constraints} \\
\hline
0 & $x_4$ & 3 & 0 & 0 & 1 & -2 & 2 & -5 & 12\\
0 & $x_2$ & 0 & 1 & 0 & 0 & -1 & 1 & -2 & 1\\
0 & $x_3$ & -2 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\
\hline
& $\tilde C$ &  -1 & 0 & 0 & 0 & 1 & 1 & 1 & $Z= 0$\\
\hline
\end{tabular}
}

\medskip\noindent
{\bf Now move to phase two.} \rm


\medskip\centerline{
\begin{tabular}{|c|c| c c c c c |c|}
\hline 
$C_B$ & $B$ & $(-3)x_1$ & $(+1)x_2$ & $(+1)x_3$ & $(+0)x_4$
& $(+0)x_5$  & {\rm constraints} \\
\hline
0 & $x_4$ & 3* & 0 & 0 & 1 & -2 & 12\\
1 & $x_2$ & 0  & 1 & 0 & 0 & -1 & 1\\
1 & $x_3$ & -2 & 0 & 1 & 0 & 0 & 1\\
\hline
& $\tilde C$ &  -1 & 0 & 0 & 0 & 1 & $Z= 2$\\
\hline
\end{tabular}
}

\medskip\centerline{
\begin{tabular}{|c|c| c c c c c|c|}
\hline 
$C_B$ & $B$ & $(-3)x_1$ & $(+1)x_2$ & $(+1)x_3$ & $(+0)x_4$
& $(+0)x_5$ &  {\rm constraints} \\
\hline
-3 & $x_1$ & 1 & 0 & 0 & 1/3 & -2/3  & 4\\
1  & $x_2$ & 0 & 1 & 0 & 0   & -1  & 1\\
1  & $x_3$ & 0 & 0 & 1 & 2/3 & -4/3 & 9\\
\hline
   & $\tilde C$ &  0 & 0 & 0 & 1/3 & 1/3 & $Z= -2$\\
\hline
\end{tabular}
}

\newpage

\noindent
{\bf Remarks}


\begin{itemize}
\item We may also consider variables without sign restriction. See \S 4.14.


\item There are other methods for solving LP:
Karmarkar's method, interior point method. 

For example, see \S 4.15 and wikipedia.

\item One can use build in
Matlab commands.

See https://www.mathworks.com/help/optim/ug/linprog.html

\begin{verbatim}
To solve minimization problem 
                min Z = c_1 x_1 + ... + c_n x_n
  Subject to    Ax \leq b,    AAx = bb,    L \leq x \leq U.
Input c = [c_1, ...., c_n], A, b, AA, bb, L, U. 
If no inequality constraints, set A = [], b = [].
Use one of the following commands
    x = linprog(c,A,b)
    x = linprog(c,A,b,AA,bb)
    x = linprog(c,A,b,AA,bb,L,U)
   [x,fval] = linprog(___)
\end{verbatim}
\end{itemize}

\bigskip
\noindent
{\bf Theory behind the simplex algorithm}

{\bf Theorem 1} \it A point in the feasible region of an LP is an extreme point 
if and only if it is a basic feasible solution of the LP. 

\it Proof. \rm Every point in $\IR^m$ is uniquely determine by $m$ linearly independent 
equation in $\IR^m$.  \qed

\medskip
{\bf Theorem 2} \it Suppose an LP in standard form have basic feasible solutions
$v_1, \dots, v_k$.
Then every point in the feasible region has the form 
$v  = v_0 + \sum_{j=1}^k p_j v_j,$
where $v_0$ is the zero vector or a vector in the unbounded direction,
$p_1, \dots, p_k$ are non-negative numbers summing up to one.

\it Proof. \rm By the theory of convex analysis. \qed

\medskip
{\bf Theorem 3} If an maximization 
LP has an optimal solution, then it has an optimal basic feasible
solution.

\it Proof. \rm If an $LP$ has an optimal solution $Z^*$
with objective function  
$$\max Z = c\cdot x = c_1x_1 + \cdots + c_n x_n,$$ 
then for any unbounded direction $v_0$, we have
$c\cdot (Mv_0) \le Z^*$ for any $M > 0$. So, $c\cdot v_0 = 0$. 
So, if $v = v_0 + \sum_{j=1}^k p_j v_j$
attains the maximum, we have
  $$c.(v_0 + \sum_{j=1}^k p_j v_j) = c\cdot (\sum_{j=1}^k p_j v_j) = 
\sum _{j=1}^k p_j c\cdot v_j \le \max\{ c\cdot v_j: 1 \le j \le k\}.$$
\vskip -.5in \qed

\newpage
\noindent
{\bf Variations of Simplex Algorithm}

\medskip
\noindent
{\bf Goal programming}

Suppose the feasible region for a set of constraints is empty.
One may want to set up an optimization problem to minimize
the damage caused by the artificial variables.


\medskip\noindent
Consider Example 10 in p. 191 in the textbook.

\noindent
Let $x_1$ be the number of minutes ad. in football game, and 
$x_2$ be the number of minutes of TV ad.

There are three targeted groups, HIM, LIP, HIW,
and the Budget constraints:
\begin{eqnarray*} 
 7 x_1 + 3x_2   &\ge& 40   \quad \ \hbox{ (HIM constraint) } \\
  10 x_1 + 5x_2 &\ge& 60 \quad \ \hbox{ (LIP constraint) } \\
  5 x_1 + 4x_2  &\ge& 35  \quad  \ \hbox{ (HIW constraint) } \\ 
100 x_1 + 60 x_2 &\le& 600  \quad \hbox{ (Budget constraint) } \\
 x_1, x_2 &\ge & 0 .
 \end{eqnarray*}

We can introduce deviational variables $s_i^+, s_i^-$ and solve the 
following.

\medskip\centerline{
$\min Z = 200 s_1^- + 200s_2^- + 50 s_3^-$}

\noindent
subject to:
\begin{eqnarray*} 
 7 x_1 + 3x_2 + s_1^- - s_1^+ &=& 40\quad \ \hbox{ (HIM constraint) } \\
10 x_1 + 5x_2 + s_2^- - s_2^+&=& 60 \quad \ \hbox{ (LIP constraint) } \\
 5 x_1 + 4x_2+ s_3^- - s_3^+  &=& 35  \quad  \ \hbox{ (HIW constraint) } \\ 
100 x_1 + 60 x_2 \qquad \qquad  
&\le& 600  \quad \hbox{ (Budget constraint) } \\
 x_1, x_2, + s_1^-, s_1^+,+ s_2^-, s_2^+, + s_3^-, s_3^+ &\ge & 0 .
 \end{eqnarray*}

Solving the LP problem, we see that $Z = 250$ with
$(x_1, x_2, s_1^+, s_3^-) = (6, 0, 2, 5)$ so that
Goal 1 and Goal 2 are satisfied. 

\medskip
If one has to pay for 
the extra budget  we can modify
the objective function and the budget constraint to:
$$\max Z = 200 s_1^- + 100 s_2^- + 50 s_3^-  + s_4^+$$
$$100 x_1 + 600 x_2 + s_4^- - s_4^+ = 600.$$

The solution becomes $Z = 100/3$
$(x_1, x_2, s_1^+, s_4^+) = (13,10, 1, 100)/3$;
all three goals are met.

One may also impose penalty for the value $s_i^+$  and add them
(with suitable weights) to the objective function.

\newpage
\noindent
{\bf Preemptive Goad Programming}

If one does not know the exact weights of the different goals, one may
consider the $\min Z = P_1 s_1^- + P_2s_2^- + P_3 s_3^-$
with $P_1 > \ > \ > P_2 > \ > \ > P_3$
and add the  constraints

\medskip
\centerline{
$z_1 - P_1 s_1^- = 0$, $z_2 - P_2 s_2^- = 0$ and $z_3 - P_3s_3^- = 0$.}

\medskip\noindent
Adding $P1 \cdot$ (HIM constraint), $P2\cdot$ (LIP constraint),
$P3 \cdot$ (HIW constraint) to these constraints, we get
$$z_1 + 7P_1 x_1 + 3P_1 x_2 - P_1 s_1^+ = 40 P_1, $$
$$z_2 + 10P_2 x_1 + 5P_2 x_2 - Ps_2^+ = 60 P_2, $$
$$z_3 + 5P_3x_1 + 4P_3x_2 - P_3s_3^+ = 35P_3.$$

Solving the LP problem, we get
$(z_1, z_2, z_3) = (0,0,5P_3)$ and 
$(x_1, x_2, s_1^+, s_3^-) = (6, 0, 2, 5)$
showing that Goal 1 and Goal 2 are met.

One may change the order of $P_1, P_2, P_3$ and get different
solutions. 


\medskip
\noindent
{\bf Scaling of the data}

For an LP: $\max Z = c \cdot x$ with 
$c = (c_1, \dots, c_n)$ and $x = (x_1, \dots, x_n)$
 s.t. $A x = b$,  $x \ge 0$.

\medskip  
One may replace $(c, [A|b])$ by $(\gamma c, D[A|b])$
for some suitable positive constant 
$\gamma$ and  diagonal matrix $D$ so that the entries in 
$\gamma c$ and $D(A|b)$ are of comparable magnitudes to avoid
unnecessary rounding error.

The optimal solution $x$ will not be changed,
and the optimal $Z$ value will be changed to $\gamma Z$.

\end{document}
