\part{Linear Programming} \chapter{Linear programs} A class of optimization problems that tackle a decent range of real life applications are linear programs. Indeed, linear programs form the basic theory for more complex optimation problems. \begin{definition} A \emph{linear program} (LP) is an optimization problem 'equivalent' to some $(X,f,\min)$, with matrix $\mathbf{A}$ and vectors $\mathbf{b},\mathbf{c}$ such that: \[X = \{ \mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} \geq \mathbf{b} \land \mathbf{x} \geq \mathbf{0}\}\] Similarly, for $(X,f,\max)$ we have the following. \[X = \{ \mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} \leq \mathbf{b} \land \mathbf{x} \geq \mathbf{0}\}\] \[f(\mathbf{x})=\mathbf{c}^{\intercal}\mathbf{x}\] Since this matrix and pair of vectors can define a linear program, the 4-tuple $(\mathbf{A},\mathbf{b},\mathbf{c},g)$ may be used to refer to LPs. \begin{itemize} \item $\mathbf{A} : n \times m$ is the constraint matrix \item $\mathbf{b} : m$ is the constraint vector \item $\mathbf{c} : n$ is the cost vector \end{itemize} \end{definition} The use of the word 'equivalent' roughly means that the feasible region, optimal solution and optimal parameters are the same as some optimization problem constructed by the definition of an LP. We will delve into this idea of LP equivalence soon. We are already familiar with some basic LPs. Take the example from the last chapter; we can formally represent it as an LP in the following way. - represent the optimization prob as an LP here Often it is the case where a real-life problem has dependent variables that are not restricted in sign (i.e they violate $\mathbf{x} \geq 0 $). Fortunately, thefollowing fact can be used to transform it into the standard form for an LP. \begin{proposition} Any real number is the difference of two nonnegative real numbers. \[x \in \mathbb{R} \iff \exists x_1,x_2 \in [0,\infty) [ x = x_1 -x_2 ]\] \end{proposition} \section{Graphical method} \begin{itemize} \item Change all inequality constraints to \end{itemize} \section{Canonical form} In our definition, the condition we imposed on our matrix and vectors to form the feasible region is called the \emph{normal form of an LP}. Indeed, one can define LPs with respect to different 'forms' which are 'equivalent' to the normal form; every LP in normal form has an 'equivalent' LP with respect to another form (note that this LP may use a different matrix than $\mathbf{A}$ and vector than $\mathbf{b}$); we define equivalence inthe following manner. \begin{definition} Let $(X,f,g)$ and $(Y,f,h)$ be two LPs with the same OF, then the pair of LPs is an \emph{pair of equivalent LPs} iff the feasible regions $X,Y$ form the same set and the LPs have the same optimal solution and optimal parameters. \end{definition} An extremely useful form to deal with LPs is the \emph{canonical form}; it will be required for an algorithm that we will investigate later. \begin{definition} An LP $(X,f,g)$ is in \emph{canonical form} iff \[X = \{ \mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} = \mathbf{b} \land \mathbf{x} \geq \mathbf{0} \land \mathbf{b} \geq \mathbf{0} \}\] \end{definition} The proof equating canonical and normal forms is omitted, however it will be a simple consequence of the techniques listed in this chapter. Note that its use of equalities allows for a much easier analysis since direct methods from linear algebra can be applied! However how does one convert inequalities of the normal form to equalities in the canonical form? Any inequality can be made into an equality, albeit at the cost of introducing new nonnegative variables. These variables introduced are called \emph{slack and excess variables}. \begin{proposition} If for two nonnegative variables we have $x\leq y$, a nonnegative \emph{slack variable} may be added to $x$ to acheive equality. \[x,y \in [0,\infty) \implies [ x \leq y \iff \exists s \in [0,\infty) (x+s=y) ]\] If for two nonnegative variables we have $x\geq y$, a nonnegative \emph{excessvariable} may be subtracted to $x$ to acheive equality. \[x,y \in [0,\infty) \implies [ x \geq y \iff \exists e \in [0,\infty) (x-e=y) ]\] \end{proposition} Slack variables are dummy variables used to represent remaining addable quantity to reach equality. Surplus variables are dummy variables that represent excess quantity from equality. \section{Application of convex analysis} Now that we are able to convert any problem to canonical form, we turn to some results from convex analysis that affect the field of linear programming. \begin{proposition} For any LP $(X,f,g)$, $X$ is convex, \[ (X,f,g) \text{ is an LP } \implies X \text{ is convex} \] \end{proposition} \begin{proposition} feasible sets have optimal solution at an extreme point feasible sets have finite extreme points \end{proposition} These results mean that if any extreme point can be calculated, any LP can theoretically be solved by calculating the finite amount of extreme points, passing them through the OF, and taking the most optimal value of this set. Hence extreme points in an LP are called \emph{basic feasilbe solutions}, due to their potential of being a solution by the proposition. \begin{definition} \emph{basic feasible solution} (BFS) of an LP is an extreme point of its feasible region. \end{definition} Unfortunately, larger problems have astronomical amounts of BFSs; for $n$ variables and $m$ constraints, one has $\binom{n}{m} $ BFSs in the worst case(depending on factors such as linear dependence etc.). For a practical algorithm, one must reduce the amount of BFSs involved. \chapter{Simplex method} We shall develop a greedy algorithm that starts with some initial BFS and seeks an 'adjacent' BFS that is 'more optimal'. Consider $m$ constraints and $n$ variables, where $n \geq m$. Then we have $n-m$ redundant variables that may be set to zero. The remaining $m$ variables are called the \emph{basis elements}, let them form the set $B$. It is most conventient to make the initial BFS that where the slack variables are the basis elements. For a given basis $B$, let us define the following notations: \begin{itemize} \item $\mathbf{B}$ is the matrix of columns of $\mathbf{A}$ corresponding to basis elements \item $\mathbf{N}$ is the matrix of columns of $\mathbf{A}$ corresponding to non-basis elements \item $\mathbf{x}_{B}$ is the vector of variables corresponding to basis elements (which we set as zeros) \item $\mathbf{x}_{N}=\mathbf{0}$ is the vector of variables corresponding to non-basis elements \item $\mathbf{c}_{B}$ is the vector of cost coefficients corresponding to basis elements \item $\mathbf{c}_{N}=\mathbf{0}$ is the vector of cost coefficients corresponding to non-basis elements \end{itemize} Adjacent BFSs are those that differ by a single variable; our algorithm should jump to an adjacent BFS by determining the most optimal nonbasis variable to enter the BFS and utilize this variable until it renders another basis element equal to $0$, essentially booting it from our BFS. \section{Calculating arbitrary BFS} Assume that our LP is in canonical form, feasible solutions are solutions to this equality. \[\mathbf{A}\mathbf{x}=\mathbf{b}\] Since $A$ is not necessarily square (so there may not exist an $\mathbf{A}^{-1}$), we consider breaking it up in the following manner. \[\mathbf{B}\mathbf{x}_{B}+ \mathbf{N}\mathbf{x}_{N}=\mathbf{b}\] Recall that we set $\mathbf{x}_{N}=\mathbf{0}$ \[\mathbf{B}\mathbf{x}_{B}=\mathbf{b}\] \[\mathbf{x}_{B}=\mathbf{B}^{-1}\mathbf{b}\] Hence the solution of the current BFS: \[\mathbf{x}_{B}=\mathbf{B}^{-1}\mathbf{b}\] \section{Determining 'optimal' variable} In order to consider which nonbasis element is ideal to add to the BFS, we consider rewriting the OF to include the nonbasis elements. Although we have officially set all these nonbasis elements to 0, it's inclusion in the OF gives algebraic hints as to which variable would improve our solution if we were to include it in the BFS. To begin along this train of though, we start by rewriting basis elements with respect to non-basis elements. \[\mathbf{B}\mathbf{x}_{B}+ \mathbf{N}\mathbf{x}_{N}=\mathbf{b}\] \[\mathbf{x}_{B} =\mathbf{B}^{-1}(\mathbf{b} - \mathbf{N}\mathbf{x}_{N})\] \[\mathbf{x}_{B} =\mathbf{B}^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N}\] Now to consider what the OF results to \[z=\mathbf{c}^{\intercal}\mathbf{x}\] \[z=\mathbf{c}_{B}^{\intercal}\mathbf{x}_{B}+\mathbf{c}_{N}^{\intercal}\mathbf{x}_{N}\] \[z=\mathbf{c}_{B}^{\intercal}(\mathbf{B}^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N}) + \mathbf{c}_{N}^{\intercal}\mathbf{x}_{N}\] \[z=\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{b} - \mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N} + \mathbf{c}_{N}^{\intercal}\mathbf{x}_{N}\] \[z=\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{b} - (\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N} - \mathbf{c}_{N}^{\intercal})\mathbf{x}_{N}\] \[z+ (\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N} - \mathbf{c}_{N}^{\intercal})\mathbf{x}_{N} =\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{b} \] We define the addend to $z$ as the \emph{reduced cost vector}. Notice that although $\mathbf{x}_N = \mathbf{0}$, we could hypothetically 'switch on' a nonbasis element to the basis to potentially minimize futher. How do we choose which element will be beneficial to add to the basis? The one associated with the largest coefficient in the reduced cost vector is the ideal candidate; this is because the larger the coefficient, the larger a value will be subtracted from our current 'solution'. This gives us a method to determine which nonbasis element it would be most desirable to 'switch on'. \[\hat{\mathbf{c}^{\intercal}}= \mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N} - \mathbf{c}_{N}^{\intercal} \] \section{Ratio test} Let $x_j$ be the entering variable. Now that we know that the larger we make $x_{j}$, the better our 'solution' will become; this is essentially sending us greedily to the next BFS. We want to make $x_{j}$ large enough until the constraints force one of the basis elements to become $0$; this is the sign that tells us that we have reached the next extreme point (remember; optimal solutions are at extreme points). To do this, we analyze this previously derived formula linking the basis and nonbasis variables. \[\mathbf{x}_{B} =\mathbf{B}^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N}\] We are trying to find out which basis element is the first to hit 0 when increasing $x_j$, so we can set $\mathbf{x}_{B} = \mathbf{0}$ and look for the smallest increase in $x_j$ until one basis element concedes to zero; this is the basis element leaving the basis. \[ \mathbf{0} = \mathbf{B}^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N}\] \[ \mathbf{0} = \hat{\mathbf{b}} - \hat{\mathbf{N}}\mathbf{x}_{N}\] \[ \hat{\mathbf{b}} = \hat{\mathbf{N}}\mathbf{x}_{N}\] We then analyze each basis element individually to see which one will be the first to buckle down to 0. \[ \hat{\mathbf{b}}_i = \hat{\mathbf{A}_{ij}} x_j\] \[ \frac{ \hat{\mathbf{b}}_i }{ \hat{\mathbf{A}_{ij}} } = x_j\] This formula states how large we can make $x_j$ until basis element $x_i$ becomes 0. Therefore the first $x_i$ to become 0 is the one associated with the smallest $x_j$. This is known as the \emph{ratio test}; it is used to determine which variable leaves. The polished result is as follows. \[ i = \mathrm{argmin}_{i} \{ \frac{\hat{\mathbf{b}}_i}{\hat{\mathbf{A}}_{ij}} : \hat{\mathbf{A}}_{ij} > 0 \} \] Now that we know how to start an LP at an initial BFS, and jump between BFS' in an efficient way, we can synthesize this information into a concrete algorithm. \section{Simplex method} We shall now formally define the process of the simplex method. Here is the sketch of what the algorithm should do. \begin{itemize} \item Set initial BFS where slack variables are the only nonzero variables \item Add most helpful variable to BFS (allow it to be nonzero in new BFS) \item Drop least helpful variable from BFS (force it to be zero in new BFS) \item Repeat until optimal solution acquired \end{itemize} The simplex method below updates the basis set $B$ and the basis matrix $\mathbf{B}$ according to the Simplex algorithm for a minimization LP in standard form. \begin{algorithm} \begin{algorithmic} \WHILE{$\max_{i} \{ (\mathbf{c}^{\intercal}_{\mathbf{B}} \mathbf{B}^{-1} \mathbf{N} - \mathbf{c}^{\intercal}_{\mathbf{N}})_{i} \} > 0$} \STATE $e \gets \mathrm{argmax}_{i} \{ (\mathbf{c}^{\intercal}_{\mathbf{B}} \mathbf{B}^{-1} \mathbf{N} - \mathbf{c}^{\intercal}_{\mathbf{N}})_{i} \}$ \STATE $l \gets \mathrm{argmin}_{i} \{ \frac{(\mathbf{B}^{-1}\mathbf{b})_{i}}{(\mathbf{B}^{-1}\mathbf{A})_{ie}} : (\mathbf{B}^{-1}\mathbf{A})_{ie} > 0 \}$ \STATE $B \gets B \cup \{x_e\}$ \STATE $B \gets B \setminus \{x_l\}$ \STATE $\text{Update }\mathbf{B} \text{ as columns of } \mathbf{A} \text{ corresponding to elements of }B$ \ENDWHILE \STATE $\mathbf{x}_{\mathbf{B}} \gets \mathbf{B}^{-1}\mathbf{b}$ \STATE $z \gets \mathbf{c}^{\intercal}_{\mathbf{B}} \mathbf{x}_{\mathbf{B}}$ \end{algorithmic} \end{algorithm} This is relatively straightforward to program on a modern computer, however the linear algebra required can be quite demanding if all components are calculated directly. A \emph{simplex method tableau} is often used for human computers so that instead of directly doing operations such as inverting $\mathbf{B}$ and matrix multiplication, one finds only the necessary row reduction steps required to preserve the following. \begin{itemize} \item Ensure columns of $\hat{\mathbf{A}}$ relating to basis elements are colums of identity matrix \item Ensure indexes of $\hat{\mathbf{c}^{\intercal}}$ relating to basis elements are equal to 0 \item Ensure simplex method tableau is in \emph{cannonical form} \end{itemize} - simplex method tableau - canonical form simplex method tableau \chapter{Simplex method revisions} \section{Artificial variables} \section{Big M simplex method} \begin{itemize} \item Arrange LP into canonical form \item Add an artificial variable $a_i$ to each constraint without a slack variable \item Update OF to $z = \mathbf{c}^{\intercal}\mathbf{x} + \sum_{i} M a_i$ (where $M$ is treated as a 'large' constant) \item Solve the new LP with the simplex method \end{itemize} \section{Two phase simplex method} \begin{itemize} \item Arrange LP into canonical form \item Add an artificial variable $a_i$ to each constraint without a slack variable \item Solve the LP using the same constraints but an OF of $ w = \sum_{i} a_i$ \item If $w=0$, drop the nonbasic $a_i$, reintroduce the OF as $z=\mathbf{c}^{\intercal}\mathbf{x}$ and continue solve using the simplex method \item If $w \neq 0$, the LP is infeasible \end{itemize} \section{Revised simplex method} Manipulating the simplex method tableau is actually implicitly calculating $\mathbf{B}^{-1}$ for the new BFS, and the tabelau updates how $\hat{\mathbf{A}},\hat{\mathbf{b}},\hat{\mathbf{c}^{\intercal}}$ based on this new $\mathbf{B}$. The columns of $\hat{\mathbf{A}}$ corresponding to the initial BFS actually equals the latest $\mathbf{B}^{-1}$. This is because the basis elements have columns of the identity matrix, and the initial BFS columns were originally the columns of the identity matrix, therefore the must have been multiplied by $\mathbf{B}^{-1}$. \chapter{Duality theory} Every LP is mathematically associated with some other 'similar' LP called is 'dual problem'. \begin{definition} Given an LP $(\mathbf{A},\mathbf{b},\mathbf{c},\min)$, $\mathbf{A},\mathbf{c},\mathbf{b},\max)$ is called its \emph{dual LP} and the original LP is called the \emph{primal LP}. \end{definition} Dual LPs might arise naturally in application due to having two related LPs that work with the same values, however there is much theory that can be stated about how the two LPs relate to one another in a mathematical sense. - optimality gap -The \emph{duality gap} of an LP is the difference between the optimal solutions of a prime LP and its dual LP. We will later see that this gap iz \begin{lemma} The dual of the primal's dual is the primal. \end{lemma} This is basically because swapping $\mathbf{b},\mathbf{c}$ in the 4-tuple an even amount of times leaves the LP unchanged from the primal, swapping $\min,\max$ an even amount of times does the same thing. \section{Asymmetric dual problems} When $\mathbf{A}$ is not square, the dual will have more (or less) constraints and less (or more) variables. This may cause issues with the LP being able to be stated in canonical form; however there is a following trick to relieve the burden of cleaning up a dual problem into canonical form. \begin{itemize} \item nonnegative primal variables means dual constraint in normal form \item nonpositive primal variables means dual inequality in constraint is opposite that of the normal form \item Unrestricted primal variables mean equality in dual constraint. \end{itemize} After applying this proposition, one can use the familiar tricks of transforming problems into canonical form to finish the job! \section{Theorems of duality} \begin{theorem}[Weak Duality Theorem; WDT] Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},g)$ be a primal problem and $D$ the dual of $P$. If $\mathbf{x}$ and $\mathbf{y}$ are feasible for $P$ and $D$ respectively, then the following inequality holds. \[ \mathbf{c}^{\intercal}\mathbf{x} \geq \mathbf{b}^{\intercal}\mathbf{y}\] \end{theorem} \begin{corollary} Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},g)$ be a primal problem and $D$ the dual of $P$. If $P$ is unbounded, then $D$ is infeasible. \end{corollary} \begin{theorem}[Strong Duality Theorem for Linear Programs; SDT] Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},\min)$ be a primal problem and $D$ the dual of $P$. $\mathbf{x}$ and $\mathbf{y}$ are optimal for $P$ and $D$ respectively iff the following equality holds. \[ \mathbf{c}^{\intercal}\mathbf{x} = \mathbf{b}^{\intercal}\mathbf{y}\] \end{theorem} This result is quite powerful; it essentially says the dual LP has the same optimal solution as its primal! When constraints are mixed and the LP seems generally difficult, one technique is to \emph{use the simplex method on the dual instead of the primal}. The SDT ensures us that we will get the same optimal solution as the primal, however the only thing that remains is the optimal parameters; how can we revover them? Assume that using SDT we have just recovered the optimal solution $z^{*}$, we're reduced only to the constraints $z^{*}=\mathbf{c}^{\intercal}\mathbf{x}$ and the primal's constraints regarding $\mathbf{A}$ and $\mathbf{b}$. From here, we could use slack and surplus variables to make all constraints equalities and solve using Gaussian-Jordan elimination! But we're mathematicians; the chances are that we're too lazy to deal with matrixes after all that simplex method (that's assuming you were bothered enough to do it by hand and not delegate the task to a computer). There is a way to reduce the final set of constraints significantly, and it is by the grace of the \emph{complementary slackness theorem} (which really should be thought of as a corollary of SDT rather than a theorem). \begin{theorem}[Complementary Slackness Theorem; CST] Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},\min)$ be a primal problem and $D$ the dual of $P$. If $\mathbf{x}$ and $\mathbf{y}$ are optimal for $P$ and $D$ respectively, then the following equality holds. \[ (\mathbf{c}^{\intercal}-\mathbf{y}^{\intercal}\mathbf{A})\mathbf{x}=0 \land \mathbf{y}^{\intercal}(\mathbf{b}-\mathbf{A}\mathbf{x})=0\] \[\mathbf{x} \text{ optimizes }P \land \mathbf{y} \text{ optimizes } D \iff (\mathbf{c}^{\intercal}-\mathbf{y}^{\intercal}\mathbf{A})\mathbf{x}=0 \land \mathbf{y}^{\intercal}(\mathbf{b}-\mathbf{A}\mathbf{x})=0 \] \end{theorem} Perhaps this 'theorem' initially seems like a jungle of algebra that feels intuitive, but useless. However, this theorem gives the insight to the following corollary. \begin{corollary} Let $\mathbf{y}$ be the optimal parameter for the dual and $\mathbf{A}: n \times m$ be the primal constraint matrix for the primal. $\mathbf{y}_i \neq 0$ iff $\sum^{n}_{k=1}\mathbf{A}_{ik}\mathbf{x}_i = \mathbf{b}_i$, where $\mathbf{x}$ is the primal optimal parameter. Essentially the $i$th constraint becomes an equality; this is knwon as a constraint becoming 'active'. \end{corollary} Using this fact, we only need to solve the system of equations including these 'active' equality constraints and $z^{*}=\mathbf{c}^{\intercal}\mathbf{x}$! \section{Dual simplex method} As previously mentined, we can leverage our duality theorems to solve a primal by solving the dual with the simplex method, and applying SDT and CST to reduce the problem to a (relatively) small system of linear equations. However there is yet another way that duality theory can be used to solve LPs. The simplex method tries to iteratively optimize a BFS while keeping in the feasible region, however since feasibility of a primal problem is equivalent to feasibility of a dual problem, could one iterate a simplex method that ensures dual feasibility? This is known as the \emph{dual simplex method}; it works almost identically to the simplex method, except that one finds the leaving variable first using $\hat{\mathbf{b}}$ and the entering variable second using the ratio test with $\hat{\mathbf{c}^{\intercal}}$. \[ i = \mathrm{argmin}\{ |\frac{\mathbf{c}_j}{\mathbf{A}_j}| : \mathbf{A}_j < 0\}\] \begin{itemize} \item When optimal but not feasible, apply simplex method but by finding leaving variable by choosing optimal element in $\hat{\mathbf{b}}$ and find entering variable by ratio test on $\hat{\mathbf{c}}^{\intercal}$. Ensure that \item When feasible but not optimal, apply regular simplex method. \end{itemize} \chapter{Sensitivity analysis on LPs} Often one may need to make slight adjustments to an optimization problem to reflect new conditions (cost of resource rises, amount of resources available depletes etc.). Sensitivity analysis studies how an optimization problem may be modified while retaining its feasible region, optimal solution or both. Here we discuss sensitivity analysis in the context of LPs; of which common modifications are the following. \begin{itemize} \item Small changes for entries of $\mathbf{c}$ \item Small changes for entries of $\mathbf{b}$ \item Small changes for entries of $\mathbf{A}$ \item Appending a new constraint \item Appending a new variable \end{itemize} The main idea is that given an LP in standard form, we have the following conditions we can rely upon. \begin{itemize} \item $\hat{\mathbf{c}^{\intercal}} \leq \mathbf{0} $ is required to preserve optimality (for minimization problems). \item $\mathbf{B}^{-1}\mathbf{b} \geq \mathbf{0} $ is required to preserve feasibility. \end{itemize} Given that we have the $\mathbf{B}, \mathbf{N}$ of the optimal solution, we can create inequalities to determine how far entries can be changed while preserving optimality and feasibility. \section{Cost vector entries $\mathbf{c}$} Small changes in $\mathbf{c}$ change the LP in different ways depending on whether the entry of $\mathbf{c}$ being changed is associated with a basis variable in the final tableau. Hence we will discuss the case of modifying nonbasis coefficients and basis coefficients separately. \subsection{Nonbasis} Denote changes in nonbasic cost vector entries as such. \[ \mathbf{c}_{\mathbf{N}}'^{\intercal}= \mathbf{c}_{\mathbf{N}}^{\intercal} + (\Delta \mathbf{c}_{\mathbf{N}})^{\intercal} \] If the cost vector entry being modified is not related to a basic variable in the final BFS, we have the following bound. \[ (\Delta \mathbf{c}_{\mathbf{N}})^{\intercal} - \hat{\mathbf{c}_{\mathbf{N}}} \geq \mathbf{0} \implies \text{ doesn't change optimal solution} \] \subsection{Basis} Denote changes in basic cost vector entries as such. \[ \mathbf{c}_{\mathbf{B}}'^{\intercal}= \mathbf{c}_{\mathbf{B}}^{\intercal} + (\Delta \mathbf{c}_{\mathbf{B}})^{\intercal} \] If the cost vector entry being modified is related to a basic variable in the final BFS, we have the following bound. \[ (\Delta \mathbf{c}_{\mathbf{B}})^{\intercal} \mathbf{B}^{-1}\mathbf{N} + \hat{\mathbf{c}_{\mathbf{N}}}^{\intercal} \leq \mathbf{0} \implies \text{ doesn't change optimal solution} \] \section{Constraint vector entries $\mathbf{b}$} Since $\mathbf{b}$ has no bearing on the reduced cost vector, changes in $\mathbf{b}$ will have no effect on optimality, but could disrupt feasibility. Denote changes in the constraint vector as such. \[ \mathbf{b}' = \mathbf{b}+ \Delta\mathbf{b} \] Modifications to the constraint vector retain feasibility under the following condition. \[ \mathbf{B}^{-1} (\mathbf{b}+ \Delta \mathbf{b}) \geq \mathbf{0} \implies \text{ doesn't change feasible region} \] \section{Constraint matrix entries $\mathbf{A}$} \subsection{Nonbasis} \[ \mathbf{A}'_{j} = \mathbf{A}_{j} +\Delta \mathbf{A}_j \] \[ \hat{\mathbf{c}}^{\intercal}_{j} + \mathbf{c}_{\mathbf{B}}^{\intercal} \mathbf{B}^{-1} ( \Delta\mathbf{A}_j ) \geq 0\] \subsection{Basis} The case where the entry is in a basis column is a bit more complex since our matrix $\mathbf{B}$ is being modified but we have $\mathbf{B}^{-1}$ on our formulae; we require a way to view how increments to a matrix entry modifies its inverse. A naiive approach is to calculate $\mathbf{B}$ from $\mathbf{B}$, and then calculate $(\mathbf{B}+\Delta\mathbf{B})^{-1}$. Then substitute this into the two inequalities we have been repeatedly using. Unfortunately, this approach is computationally expensive, however there exists a formula to assist in this situation. The \emph{Sherman-Morrison formula} can be employed to view how the inverse is effected by incremental arguments, and it can be used to derive the following. \[\] \section{Additional constraint} Check that optimal solution satisfies new constraint, if so optimal solution unchanged. if not, use row reductions to get in canonical form and add to tableau as a basis element. Note that it may be infeasible; in this case, continue using dual simplex method. \section{Additional variable} When appending a new variable to the LP, our main concern is whether the new variable's reduced cost entry of this variable retains optimality (i.e negative for min problems). If (for a min problem) $\mathbf{c}^{\intercal}_{\mathbf{B}} \mathbf{B}^{-1} \mathbf{A}_{j} - \mathbf{c}_{j} \leq 0$, it can safely be entered into nonbasis without changing optimal solution, otherwise enter column $\mathbf{B}^{-1} \mathbf{A}_{j}$ into final tabealu and $\mathbf{c}^{\intercal}_{\mathbf{B}} \mathbf{B}^{-1} \mathbf{A}_{j} - \mathbf{c}_{j}$ into reduced cost and continue simplex method. \[ \hat{\mathbf{c}_{\mathbf{B}}}^{\intercal} \mathbf{B}^{-1} \mathbf{A}_{j} - \mathbf{c}^{\intercal}_{j} \leq 0 \implies \text{ nonbasis entry doesn't change optimal solution} \]