Linear Programming

Linear programming is a combinatorial optimisation method to operate specific systems optimally under resource constraints

Problem Statement

A small manufacturer makes two products A and B, each of which requires two resources $R_1$ and $R_2$

• Each unit of A requires $1$ unit of $R_1$ and $3$ units of $R_2$
• Each unit of B requires $1$ unit of $R_1$ and $2$ units of $R_2$

But the manufacturer only has $5$ units of $R_1$ and $12$ units of $R_2$

On every unit of A sold the manufacturer makes $6 profit On every unit of B sold the manufacturer makes $5 profit

How many units of the product A and B should the manufacturer produce to maximize profit?

Formalising The Problem

Let x = num(A units produced) and y = num(B units produced) and the total profit $z=6x+5y$ (our objective function).

We now have constraints on the products:

• As the manufacturer only has $5$ units of $R_1$, then for $R_1$, we have $x+y\le 5$,
• As they only have $12$ units of $R_2$, then for $R_2$ we have $3x+2y\le 12$.
• A simple constraint additionally is that $x,y\ge 0$ as we can never lose products in our case.

We want to maximise our objective function subjected to certain constraints.

Most linear programming problems present themselves in terms of a linear objective function under linear and non-negative constraints.

Defining Jargon

• The variables $x$ and $y$ are called decision variables
• The profit function $z$ that is being optimised is called the objective function
• The restrictions below are called linear constraints. These restrict the values the decision variables can take.
  • $x+y\le 5$
  • $3x+2y\le 12$
  • $x,y\ge 0$

All Linear Programming (LP) problems have a linear objective function, a set of linear constraints and a non-negativity constraint on all decision variables.

Canonical Form Of A Linear Programming Problem

Linear Programming (LP) is a method to achieve the best outcome, such as maximum profit or lowest cost, in a mathematical model whose requirements are represented by linear relationships.

• Let $x_1,x_2,\dots ,x_n$ be the decision variables that represent the unknowns to solve for.

The goal is to maximise an objective function which is a linear function of the decision variables

$$\text{Maximize}z=c_1\cdot x_1+c_2\cdot x_2+\cdots +c_n\cdot x_n$$

Where $c_1,c_2,\dots ,c_n$ are known coefficients representing the contribution of each decision variable to the objective.

The decision variables are subject to a set of linear inequality constraints:

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n& \le b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n& \le b_2\\ ⋮& ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n& \le b_m\end{array}$$

Where $a_{ij}$ are known coefficients, and $b_1,b_2,\dots ,b_m$ are constants representing the right-hand side of each constraint.

Additionally, all decision variables must be non-negative, to ensure practical feasibility (e.g. you can’t produce a negative quantity of something.)

$x_1,x_2,\dots ,x_n\ge 0$

Graphical Solution

A graphical solution is applicable in practice to solutions involving 2 (or even 3 decision variables). It helps with gaining insight about solutions of general linear programs, otherwise its practically useless.

First, each constraint individually defines a half space, i.e. it divides a region that greater than and one that’s less than. This is the shaded region in each graph.

To satisfy all constraints, is equivalent to the intersection between all half spaces. Doing so, you will notice that all values are constrained in the first quadrant.

The feasible region is the region where the given linear program has feasible solutions satisfying all its constraints. This is the purple area (intersection of all half spaces).

This is the only region we care of, via the constraints, this is the area where the optimal solution exists in, including the border (<=)

The feasible region is a convex polygon/polyhedron.

Convex Polyhedrons

A definition of convexity is that, for any two points in a feasible region (closed region), drawing a line from one point to another (once again for ANY two points), returns a line that is completely contain within the region.

As long as the points are within the region, the line cannot be outside, it must be within or on the surface of the polyhedron.

Given any two points inside or on the surface/boundary of the polyhedron, the line segment connecting those two points always lies entirely within the polyhedron

For any point in the feasible region, there is always a point on the boundary/surface of the feasible region that will dominate it (i.e., will give a better evaluation of the objective function)

This lets us know that our search should only be on the boundary of the region, greatly constraining the search space.

Further, among all points on the boundary/surface of the feasible regions, there is at least one corner point of the feasible region that will always dominate, given the objective function.

This lets us reduce the search space further into the corners of the region.

If a point $x$ was perturbed by a neighbouring point $\Delta$ to $x+\Delta$, the objective function increases, as the coefficient of decision variables of the objective function is positive, you would have a objective function that increases by the coefficient times $\Delta$. If the coefficient was negative $x-\Delta$ would be greater. This also applies for $y$.

As you continue to do this $x+\Delta$ reaches the boundary and there is no neighbouring point $\Delta$ gt/lt $x$. So you would have a neighbouring point that dominates it. Taking this a little further, if you do this for both $x$ and $y$ you would reach the corners of the lines

The objective function $6x+5y=z$ is a family of lines depending on $z$. If $z$ is fixed, it will converge into one line with a slope. If viewing this family as a sweep of lines convering to $(0,0)$, the first point it touches is $(2,3)$, the point sticking out (as its convex).

In fact the largest value for $z$ that intersects with one of those points will be at $(x=2,y=3)$ which is $z=27$.

Approaching Graphical Solution Using Algebra

The graphical solution has no use for general purposes algorithms, it only provides insights.

To approach the solution algebraically is to convert the inequality constraints into equality constraints. This is achieved by adding slack variables.

Having a $LHS\le RHS$ means that there is some slack on the LHS for it to become a strict equality. For example, $x+y\le 5$ becomes $x+y+s=5$ for some slack $s\ge 0$, similarly the $3x+2y\le 12$ becomes $3x+2y+t=12$ for some slack $t\ge 0$

Additionally, in actuality when adding new variables, all formulas (inequalities) must contain those variables so $x+y+s+0t=5$ and $3x+2y+0s+t=12$ is more correct.

The objective function can thus be written as:

$$\text{Maximize}z=6x+4y+0s+0t$$

Subject to the constraints

• $x+y+s+0t=5$
• $3x+2y+0s+t=12$

Where $x,y,s,t\ge 0$

First of all we can represent the constraints in matrix form $AX=B$:

$$\left[\begin{array}{cccc}1& 1& 1& 0\\ 3& 2& 0& 1\end{array}\right]\left[\begin{array}{c}x\\ y\\ s\\ t\end{array}\right]=\left[\begin{array}{c}5\\ 12\end{array}\right]$$

Now there’s 4 variables and 2 equations, this is an undetermined system so a solution cannot be found using systems of linear equations. To do this we would need the same equations as variable. However, if we can fix two of variables to some value, which leaves two free variables, then we can solve for the free variables.

We are always fixing the values to $0$, because… In our problem we have $\left(\genfrac{}{}{0ex}{}{4}{2=6}\right)$ possible fixings.

By fixing these points to $0$, we enumerate through all possible corner points and some points being in the infeasible regions

Basic Vs Non Basic Variables

Bases are a collection of column vectors that define the space, e.g. x, y, z coordinates form the basis of 3 dimensions.

In the context of linear programming, basic variables are the free variables (not set to 0). They correspond to column (unit) vectors that form a basis (vector space) of the iterative linear programming solution (explained in Tableau Simplex).

Where are non-basic variables are the variable that are fixed to zero. They are so called, because they are outside the basis of the linear programming problem

Now let’s evaluate the objective function corresponding to all possible ways of fixing variables to become non-basic variables

Generalising The Algebraic Method

Let some general linear programming formulation contain $N$ decision variables and $m$ linear constraints. For $m$ linear constraints, there will be $m$ slack variables helping form $m$ linear equations (rather than inequalities).

To assign $N$ out of $N+m$ (decision+slack) variables to $0$, and solve for the remaining $m$ variables. There are $\left(\genfrac{}{}{0ex}{}{N+m}{N}\right)$ such possibilities.

Substitute the values of that $N$ decision variables take into the objective function. Once all possibilities are explored, choose the optimum over all the solutions.

The issues with this are this algorithm grows combinatorially for large $N$, evaluates infeasible solutions, doesn’t tell you if the optima has been reached as the search is exhaustive (brute-force), and does not give progressively better solutions (in terms of the objective function), the search is fairly random.

The Simplex Algorithm is a polynomial time algorithms (in practice) that optimises these issues.

A polynomial time algorithm is one whose running time grows at most as a polynomial function of the input size. I.e. an algorithm that runs in $O(n^k)$ for some input size $n$ and constant $k$.

This means the algorithm is considered efficient and scalable for large inputs.