Simplex Method
Author
Tushar Phatangare
Last Updated
6 years ago
License
Creative Commons CC BY 4.0
Abstract
Lecture note on the Simplex Method
Lecture note on the Simplex Method
\documentclass[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
%
% ADD PACKAGES here:
%
\usepackage{amsmath,amsfonts,amssymb,graphicx,mathtools,flexisym}
%
% The following commands set up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf SC-607: Optimization
\hfill Spring 2016} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Lecture #1: #2 \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Lecturer: #3 \hfill Scribes: #4} }
\vspace{2mm}}
}
\end{center}
\markboth{Lecture #1: #2}{Lecture #1: #2}
{\bf Note}: {\it LaTeX template courtesy of UC Berkeley EECS dept.}
{\bf Disclaimer}: {\it These notes have not been subjected to the
usual scrutiny reserved for formal publications. They may be distributed
outside this class only with the permission of the Instructor.}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
% Also commands that create a suitable format for the reference list.
\renewcommand{\cite}[1]{[#1]}
\def\beginrefs{\begin{list}%
{[\arabic{equation}]}{\usecounter{equation}
\setlength{\leftmargin}{2.0truecm}\setlength{\labelsep}{0.4truecm}%
\setlength{\labelwidth}{1.6truecm}}}
\def\endrefs{\end{list}}
\def\bibentry#1{\item[\hbox{[#1]}]}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
\newcommand{\fig}[3]{
\vspace{#2}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\newcommand\E{\mathbb{E}}
\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{11}{February 16}{Ankur Kulkarni}{Tushar Phatangare, Mayur Vangujar}
%\footnotetext{These notes are partially based on those of Nigel Mansell.}
% **** YOUR NOTES GO HERE:
\section{Simplex Algorithm (Continued)}
\subsection*{11.1.1 Assumptions}So far we have made the following assumptions:
\begin{enumerate}
\item The LP is in the standard form i.e.\\
\begin{eqnarray*}
\min c^T x \\
\mbox{s.t}\ Ax=b,
\newline
\\x\geq 0
\end{eqnarray*}
\\
where $C,x\in{\mathbb R^{n}}$, $A \in {\mathbb R^{m\times n}} $ , $b \in{\mathbb R^{m}}$ and $rank(A)= m$
\item Every Basic Feasible Solution i.e. BFS is non-degenerate
\item BFS is in the form
\begin{equation}
[I \mid Y] \left[ \begin{matrix}
x
\end{matrix}\right] = y_0
\label{eq1}
\end{equation}
where I is $m \times m$ Identity Matrix,
$ x = \left[ \begin{array}{cc}
x_{B} \\
x_{NB} \end{array} \right]$,~~$x_B \in R^n $ and $x_{NB} \in R^{n-m}$
\end{enumerate}
\section{Basic Steps of Algorithm}
\begin{itemize}
\item Generic step of the algorithm is to swap a basic variable with a non basic variable. For now assume
that we have selected basic variable $x_p$ and non-basic variable $x_q$ to swap
\item $x_p$ can be swapped with $x_q$ if and only if $Y_{pq} \ne 0$ because if $Y_{pq}$ is equal to 0 then column vector $Y_q$
can be represented as linear combination of m − 1 basis vectors i.e.
\[ Y_q=\sum_{i=1~i \neq p}^m y_{iq} \ast I_i\]
and hence $Y_q$ cannot be included in basic solution
\item Now make $q^{th}$ column as $ \left[ \begin{array}{ccccccc}
0 & ... & 0 & 1_p & 0 & ... & 0
\end{array} \right]$ where $1_p$
signifies 1 at
$p^{th}$
position. For that
divide$p_{th}$row of matrix$ \left[ \begin{array}{cc}
I &
Y \end{array} \right]$
and matrix $ \left[ \begin{array}{cc}
Y(0) \end{array} \right]$
by
$Y_{pq}$ and apply the row operation $R_i \Rightarrow R_i - Y_{iq} \ast R_p$
\end{itemize}
\section{Determining the Leaving Variable p}
\begin{itemize}
\item While applying row transformation of
$ \left[ \begin{array}{cc}
I &
Y \end{array} \right]$ rows of $ \left[ \begin{array}{c}
I \end{array} \right]$ also changes and are given by
\[Y_{i0}\textprime =Y_{i0}-Y_{iq}\ast Y_{p0} / Y_{i0} \]
Condition $Y_{i0}\textprime \ge 0 $ must satisfy otherwise $x_q$ would not be a BFS.
\item So choose p such that
\[p \in S = \underset{i}{\operatorname{argmin}} \{Y_{i0}/Y_{iq} | Y_{iq} \ge 0\}\]
\item If number of elements in S is $>$ 1 then the would become degenerate. Since non-degeneracy is assumed
\[p = \underset{i}{\operatorname{argmin}}\{Y_{i0}/Y_{iq} | Y_{iq} \ge 0\}\]
\end{itemize}
\section{Determining the Entering Variable q}
\begin{itemize}
\item We Know that
\[ \left[ \begin{array}{cc}
I &
Y \end{array} \right] \left[ \begin{array}{cc}
x_B \\
x_{NB} \end{array} \right]= \left[ \begin{array}{c}
Y(0) \end{array} \right] \]
\[ x_B=Y_0-Yx_{NB} \]
\[Where \left[ \begin{array}{cc}
x_B \\
x_{NB} \end{array} \right] \ge 0 \]
\item Initial Cost:
\[c^T\left[ \begin{array}{cc}
x_B \\
x_{NB} \end{array} \right] =c_B^Tx_B+c_{NB}^Tx_{NB} \]
\[=c_B^Tx_B\]
\[=c_B^T Y_0\]
\[since~~x_{NB}=0 ~~and~~ I \ast x_B + Y \ast x_{NB}= Y_0\]
\item Now cost is
\[c^T\left[ \begin{array}{cc}
x_B \\
x_{NB} \end{array} \right] =c_B^Tx_B+c_{NB}^Tx_{NB} \]
\[=c_B^T(Y_0-Yx_{NB})+c_{NB}^Tx_{NB}\]
\[ =c_B^TY_0+(c_{NB-Y^Tc_B})^Tx_{NB} \]
\item Now we can choose q such for which $(c_{NB}-Y^Tc_B)_q<0$
\item Formalizing the above concept
\[ \left[ \begin{array}{cccccccc}
1 & 0 & ... & 0 & Y_{1,m+1} &Y_{1,m+2} & ... & Y_{1,n} \\
0 & 1 & ... & 0 & Y_{2,m+1} &Y_{2,m+2} & ... & Y_{2,n} \\
. & . & . & . & . & . & ... & . \\
. & . & . & . & . & . & ... & . \\
. & . & . & . & . & . & ... & . \\
0 & 0 & ... & 1 & Y_{m,m+1} &Y_{m,m+2} & ... & Y_{m,n} \\
\end{array} \right] \left[ \begin{array}{c}
x_1\\ .\\ .\\ .\\ x_m\\ .\\ .\\ .\\x_n \end{array} \right] = \left[ \begin{array}{c}
y_{10}\\ .\\ .\\ .\\ y_{m0}\\ .\\ .\\ .\\y_{n0} \end{array} \right] \]
and
\[(c_{NB}-Y^Tc_B)^Tx_{NB}=\sum_{j=m+1}^n(c_j-Z_j)\ast x_j\]
\[Where ~~ Z_j=\sum_{i=1}^m(Y_{i,j}\ast c_i)\]
\item To determine the entering variable choose j such that $(c_j - Z_j ) < 0$
\end{itemize}
\subsection{Theorem 8.1.} Given a non-degenerate Basic Feasible Solution with objective value $Z\textprime$ . Suppose $c_j - Z_j\textprime < 0$
for some j there is a feasible solution with objective value $< Z\textprime$ . Also if variable $x_j$ can be substituted for
a variable in the basis for a new BFS, we get new BFS with value $Z_0 < 0$. If this cannot be done then the
solution is unbounded.
\section{Optimality condition}
The Basic Feasible Solution is optimal if
\[\forall,~~~~ c_j - Z_j \ge 0\]
\section{Some Points to Ponder}
\begin{itemize}
\item f there does not exist p to replace then we have founded the recession direction and the cost can be
reduced to $-\infty$
\item In the worst case the Simplex Algorithm might visit all the extreme points. Example - Klee Minty cube
\end{itemize}
\pagebreak
\section{Duality}
Every linear programming problem, referred to as a primal problem, can be converted into a dual problem,
which provides an upper bound to the optimal value of the primal problem. The primal problem is:
\[\underset{x}{\operatorname{min}} ~c^Tx\]
\[Ax=b\]
\[x \ge 0\]
\[Where ~~ A \in R^{m \times n},~Rank(A)=m\]
with the corresponding symmetric dual problem,
\[\underset{y}{\operatorname{max}} ~ b^Ty\]
\[A^Ty \le c\]
\[Where ~~ A \in R^{m \times n},~Rank(A)=m\]
\end{document}