Linear Programming is a mathematical technique to find the optimal value for a linear system of objective function and constraints.
Modeling is an art, not a precise science. All mathematical models necessarily contain some degree of simplification of the real world that we are attempting to describe.
Different modelers will make different assumptions, and come up with different models of more or less precision, and certainly of different sizes, having different numbers of decision variables.
Linear Programming (LP)
Linear programming (LP) is the best known mathematical optimization technique to allocate scarce resources to competing activities in an optimal manner when the problem can be expressed with continuous decision variables, linear in both objective function and inequality constraints.
LP is the first category of optimization problems that were considered by early scientists and researchers in the OR field.
It turns out that many models can be cast in the form of LP models, without too many wild assumptions.
To solve an optimization problem, a model file contains at least the elements, i.e Objective Function, Constraints and Bounds.
1) Objective Functions
Objective function is a mathematical representation of the business objectives or goals to be achieved. It always starts with maximize or minimize of the outputs, for minimizing costs or maximizing revenue.
$\min c_1 x_1 + c_2 x_2 +\ ...\ +\ c_n x_n$
min means minimize. It can be maximize based on modeler's logic.
$c_1, c_2, ..., c_n$ are the objective function coefficients.
$x_1, x_2, ..., x_n$ are the variables or unknowns.
2) Constraints
Constraints are the elements that limit or restrict the decision variables in some way.
model starts with the objective, i.e. to minimize a linear function.
c is the vector of objective coefficients.
s.t. means subject to constraints in the form of linear expressions.
b is the vector of right-hand side constants of constraints.
A is the matrix of constraint coefficient.
x is the decision variable.
$x \geq 0$ is the variable domain.
This example shows how to a general linear programming problem, and illustrates how scripting can be combined with the model to display results and obtain details on the solution. The problem we want to solve can be written in matrix form as
$\begin{aligned} \max c^T x \\\ s.t.\ A_x \leq b \\\ x \geq 0 \\\ \end{aligned}$
Simplest form of a LP
min c^T x s. t. Ax = b x >= 0
$c^T$ is the c transpose x.
if y represents the dual variables for a given basic solution, the reduced costs are defined as $c - y^T A$.
the basic solution is optimal if $c - y^T A \geq 0$.
if all reduced costs for this LP are non-negative, it follows that the objective value can only increase with a change in variable value and therefore the solution when minimizing is optimal.
for large LPs, the reduced costs can be used to determine whether multiple optimal solutions exist.
Multiple solutions exist when at least one non-basic variable with a zero reduced cost exists in an optimal solution, that is, the variables values that can change without affecting the objective values.
It is possible that a LP has multiple optimal solutions. This can happen when the slope of the objective function is the same as the slope of the constraints.
We have stressed the linearity condition, where the objective function and all of the constraints must be linear in the decision variables. But there are two further properties that we must have, which are Divisibility and Determinism.
Divisibility means that in an acceptable solution any values of the decision variables are allowed within the restrictions imposed by the linear constraints. In particular, we are not constrained to accept only whole number (integer) values for some or all of the decision variables.
Deterministic requires all the coefficients in the constraints and the objective function are known exactly. Determinism is sometimes a very strong assumption, particularly if we are building planning models which extend some way into the future.
Problems where we must consider the Variability in objective function coefficients, right hand sides or coefficients in the constraints are Stochastic Programming problems. In fact, it can be argued that all planning models have stochastic elements and we will later demonstrate some methods for dealing with uncertainty in an LP framework.
Nowadays Linear Programming is still frequently taught from a very academic perspective. With the exception of a few students in applied mathematics who have learned to deal with applications, the others do not retain much.
In the coming lessons, we will show you the possible applications, readily available software tools and most importantly, the best practice on how to model.
Before the computers and the optimization software are available to public, students are restricted to solving linear programming problems in two variables graphically.
Graphical method of linear programming is used to solve problems by finding the highest or lowest point of intersection between the objective function line and the feasible region on a graph.
Consider the following problem from Linear Programming with Minizinc Introduction:
300 boxes need to be loaded and shipped to a supermarket from a warehouse. We may rent lorries that can accommodate 30 boxes and 40 boxes, costing us RM 400 and RM 500 respectively. How many lorries of each type to load all boxes while minimizing the cost?
Our goal (also known as objective function), is to minimize the cost of loading these boxes by selecting the right amount of the different lorries.
We found that with 6 lorries of 40 boxes (240 boxes @ RM 3000) and 2 lorries with 30 boxes (60 boxes @ RM 800), we can load all the boxes and pay only RM 3800.
Here is the summary of the information we have:
We can use 2 kinds of lorries, which can accommodate 30 boxes and 40 boxes. We label their amount as nLorry30 and nLorry40 respectively.
lorry30 and lorry40 are charged for RM 400 and RM 500 each respectively.
Our objective is to minimize the cost, by allocating just enough lorries of different kinds.
The total capacity from the lorries must be equal to the number of boxes, which is 300.
The number of lorries of each type must be zero or more than zero. That's because we cannot have negative lorry.
We can turn the information into mathematical representations.
Minimize Cost = 400 x nLorry30 + 500 x nLorry40 - (1), (2) and (3)
Capacity: 30 x nLorry30 + 40 x nLorry40 = 300 - (4)
So the coordinates of the first point are nLorry30 = 0 and nLorry40 = 7.5 which can be written as (0, 7.5).
Once we have determined the coordinates of any 2 points from the equation, we simply mark them on the graph and draw a straight line across them, which is a linear function graph.
It is a 2 dimensional graph using x and y axes represent 2 variables.
The sign of the inequalities determine which side of the lines define the constraints.
Feasible Region
Feasible Region is the set of all points that satisfy all the constraints. One of them will be our optimal solution point.
We can shade the area on graph, according to our constraints, which lies on or below the linear equation line and above zero for x/y axes.
A feasible region is the region where the shaded area intersect satisfies all three constraints.
In this region, the solutions satisfy the constraints and all are feasible solutions.
To find the optimum point, we need to slide a ruler across the graph.
For maximization problem, we will use isoprofit line, the parallel lines with all the points along such a line represent the same profit, move up to find optimal solution. While for minimization problem, we will move down the isocost line.
The last isocost line that touches the feasible region (extreme point, vertex or edge) is the smallest value possible for the objective function.
To minimize the cost, we must slide the ruler up to the point within the area that is nearest to the origin.
Optimal Solution
The optimal solution to the LP is the point for the decision variables within feasible region AND minimize our cost (defined by objective function).
A corner point is a point that falls along the corner of a feasible region.
We have 3 corner points, which are (0,0), (10, 0) and (0. 7.5).
These 3 corner points are the potential point that is minimizing our costs.
We can now calculate the cost for these three points, using the straight parallel line, by substituting in values for the objective.
Cost = 400 * nLorry30 + 500 * nLorry40
For point 0 (0, 0):
Cost = 400(0) + 500(0) = RM 0
So, our cost is RM 0?
Yes, our cost is zero because we do not load any boxes to any lorries.
This is not a solution.
For point B (10, 0):
Cost = 400(10) + 500(0) = RM 4000
Not bad!
How's about point A (0, 7.5)?
Cost = 400(0) + 500(7.5) = RM 3750
Better! Lower cost!
So, we just need 7.5 lorries that can accommodate 40 boxes each.
This is a very simple linear programming problem with only 2 variables, which are 2 types of lorries.
The next application of linear programming again concerns food (which should not be surprising, given the importance of food in life and the difficulties in optimizing sleep or love).
Jiri Matousek & Bernd Gärtner, Understanding and Using Linear Programming
After doing the MIT SICP lectures over the summer, I'm always amazed at how language development frequently attempts to implement functionality implementable in LISP. It seems like LISP really was a consummately expressive language, and it's frustrating sometimes to not have simple things I got used to when learning the functionals like Scheme and Haskell.
That aside, this macro capability is amazing, and it's illustrated here to quite the effect. The stupidly simple knapsack I implemented is done here in three lines that are much more semantically meaningful than my larger program. They macros are extended at run time into full expressions, and their data structure is much better for the solution of general knapsack problems.
My implementation would not quite win out in a diff battle.
This paper by Miles Lubin at MIT really demonstrates the ability of these macros to reduce general overhead and waste for IP/MIP. I'd really recommend a read, if you're interested in math programming. The more I learn about this language, the more I'm convinced it's posed, from an infrastructural perspective, to replace at least R. But, then again, I'm not getting my degree in telling futures to the present.
