#mathematical programming

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.

$\begin{aligned} a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n \leq b_1 \\\ a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n \leq b_2 \\\ ... \\\ a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n \leq b_m \\\ x1, x2, ..., x_n \geq 0 \end{aligned}$

$a_{11}, a_{12}, ..., a_{1n}, a_{m1}, a_{m2}, ..., a_{mn}$ are the constraint coefficients.

$\leq, \geq, \lt, \gt$ are the relations between both sides in inequalities form.

$b_1, b_2, ..., b_m$ are the righthand side values.

3) Bounds

Bounds are the special contraints to define lower and upper boundaries.

$l_1 \leq x_1 \leq u1,\ ...,\ l_n \leq x_n \leq u_n$

$u_1, u_2, ..., u_n$ are the upper bounds.

$l_1, l_2, ..., l_n$ are the lower bounds.

This is the Simplest Structure of a Model with the conventional form or typical symbolic representation of a LP.

Minimize (or Maximize) c1 x1 + c2 x2 + ... + cn xn Subject To a11 x1 + a12 x2 + ... + a1n xn = 0 l1 = 0

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.

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)

nLorry30, nLorry40 >= 0 - (5)

Which is:

$\begin{aligned} \min 400 * nLorry30 + 500 * nLorry40 \quad (0) \\\ 30 * nLorry30 + 40 * nLorry40 \geq 300 \quad (1) \\\ nLorry30, nLorry40 \geq 0 \quad (2) \end{aligned}$

For the purpose of plotting, we need the coordinates of any 2 points from the above equation.

In order to find the coordinates, simply insert a random value for either nLorry30 or nLorry40.

Solving the equation after inserting the random values could then be used to find the value of the other coordinate.

To solve this graphically we nullify each variable. This means that we assume that all boxes are loaded to each type of lorry separately.

For example, we can find the value of nLorry30 when nLorry40 = 0 by inserting zero in place of nLorry40 and solving the equation as follows:

Capacity: 30*nLorry30 + 40*(0) = 300 30*nLorry30 + 0 = 300 30*nLorry30 = 300 nLorry30 = 300/30 = 10

So the coordinates of the second point are nLorry40 = 0 and nLorry30 = 10 which can be written as (10, 0).

Similarly, we can find the value of nLorry40 when nLorry30 = 0 by inserting zero in place of nLorry30:

Capacity: 30*(0) + 40*nLorry40 = 300 0 + 40*nLorry40 = 300 40*nLorry40 = 300 nLorry40 = 300/40 = 7.5

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.