Simplex Method
Author:
Tushar Phatangare
Last Updated:
9 years ago
License:
Creative Commons CC BY 4.0
Abstract:
Lecture note on the Simplex Method
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
Lecture note on the Simplex Method
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\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}