Introdution to Linear Programming
Introdution to Linear Programming
Definitions
- Objective function: linear function,$z$, we want to optimise
- Variables: $x_j$ amounts we seek to assign values to, in order to optimise the objective function.
- Constraints: linear (in)equalities that must be satisfied by an assignment of variables
- Non-negativity constraints: constraints of the type $x_j≥0$
- Resource constraints: the other constraints are often termed as resource constraints(or just constraints when it’s clear from the context).
- Optimal solution: feasible point(s) at which the objective value is the largest (in case of maximisation) or smallest(in case of minimisation) among all feasible points.
- Feasible point: point $x$ is feasible for a linear program if it satisfies all its constraints.
- Feasible region: set of all feasible points of the problem.
Linear programming
Importantly, these problems are convex, and we use this property in Linear Programming
- That is, the space of feasible solutions is a convex polytope, and the optimal solution can be found by traversing the perimeter of the polytope in a systematic way.
Generally, in an optimisation problem we’re trying to minimise or maximise some quantity, called the objective.
The objective depends on a finite number of variables.
The variables might be related to one another by one or several constraints.
In linear programming, the objective function and the constraints are of linear form.
Questions on Anatomy of an LP
Burger Bar
A burger joint makes its burgers from a combination of some high quality meat and some cheaper meat with a higher fat content. The company keeps the precise meat sources secret but guarantees that its burgers have a fat content of less than 25%.
The high quality meat it uses contains 80% lean meat and 20% fat, and costs 80p per kilo. The cheaper meat contains 68% lean meat and 32% fat and costs 60p per kilo.
How much of each kind of meat should the burger joint use in each kilo of burger meat if it wants to minimise its cost and keep the fat content down to no more than 25%?Model
write problem in clear statement
convert or translate to mathmatical form- Two variables
$x_1$ :quanity (in kg) of high qulity meat to be used in 1 kilogram of burger meat
$x_2$ :quanity (in kg) of cheaper qulity meat to be used in 1 kilogram of burger meat - Minimise total cost(objective function)
min TC: $80x_1+60x_2$
- Fat contain (constraints):
subject to:
$0.2x_1+0.32x_2 ≤ 0.25$
$x_1+x_2=1$
$x_1≥0$,$x_2≥0$ non-negetivity constraints/intergret constraints
- Two variables
Furniture Production
A furniture factory produces 2 type of benches using steel and wood..
The benches are sold to furniture shops for 3k and 1k per dozen of units of each type, respectively.
wood is old used for benches of type 1 and steel is used in both, and it’s required it of steel to produce a dozen of benches of type 2, while the same amounnt of benches of type 1 requires 1t of steel and also it 1t of wood. In total, the factory has 3t of steel and 2t of wood available in the next month.
the question facing the factory is, given the limited availability of materials, what quantity(in dozens) of each product should the company produce in the next month, in order to achieve the maximum total profit?Type Price(per doz) Steel(per doz) Wood(per doz) 1 3k 1t 1t 2 1k 1t 0 Model
- two variables
x_1= number of benches of type 1(in dozens)
x_2= number of benches of type 2(in dozens) - Max: $z=3x_1+x_2$
- constraints
subject to:
$x_1+x_2≤3$
$1x_1+0x_2≤2$
$x_1≥0$
$x_2≥0$
- two variables
Graphical Solution
Questions on live examples
Burger Bar
Can we take values for $x_1$ annd $x_2$ from the entire set of real number?[-infinity to +infinity ]
ans: no, this problem has non-negetive constraints
Non-negativity constraints
These are crucial constraints as they significantly restrict the solution space and help direct the solution method. Also ensure solutions selected are sensible.
But why is that?
Considering the production example above, not restricting the quantity $ 𝑥_j $ to be positive only is very problematic:
Can not produce negative amount of product
- If a product j is not profitable, $i.e. 𝑐_j < 0$, then without the constraint the model could select a solution $𝑥_j < 0$ leading to profit, $i.e. 𝑐_j𝑥_j > 0$
- A negative amount of product$j,x_j$ would imply that it does not consume any material to be produced but it rather generates… is this possible?
Also that would imply infinite profit driving $𝑥_j 𝑡𝑜 − ∞$
Mobile phone manufacture
You are a manufacturer able to produce two types of mobile phone, a budget model and a high-end model, to be released in a particular region where you know the demand for these phone models.
For simplicity, reducing the problem scope to two dimensionns, aumme production requires just two resources to produce a phone:
the production lead time in minutes, and the material required.
Note that resources are subject to capacity constraints. Then assume 2500 minutes production lead time of in a month and 4800 units of input material.
The required resources per phone, the demand per month and the sales price for a phone of each model are given below:
| Prodution Lead Time | Material Quantity | Demand | Unite Sale Price | |
|---|---|---|---|---|
| Budget model | 5 | 5 | 400 | 200 |
| High-end model | 7 | 17 | 270 | 400 |
Model and solve as a linear program using the graphical method.
Answer can be seen in Quiz 2
Canonical Form
Whilst in the literature there are several variants, here we will use the form below:
$$ max C^TX $$
$$ s.t. AX = b$$
$$ X≥0 $$
Where A is an $m \times n$matrix, b is an m-dimensional vector and c, x are n-dimensional vectors.
Considerations:
- Objective function must be maximised - i.e. express as maximisation problem
- All resource constraints must be converted to equations/equality constraints
- All variables must be non-negative
- All constants b must be non-negative
Four Steps of transforming LPs to a canonical form
step 1
Let $P$ be your original linear programming problem.
Let $P’$ be the same problem in canonical form
If the objective function of $P$ if:
$$minimise\ C^TX$$
then the objective function of $P’$ will be:
$$maxmise -C^TX$$
Otherwise, objective function in $P’$ will be same as in P
step 2
Given an inequality constraint in $P$ in the following form in $P’$:
$$\sum^n_{j=1}{a_{ij}x_j≤b_i}$$
replace it with the following resource and non-negativity constraints:
$$\sum^n_{j=1}{a_{ij}x_j+s_i=b_i}$$
$$s_i≥0$$
Similarly for ≥ constraints of the following form in $P$:
$$\sum^n_{j=1}{a_{ij}x_j≥b_i}$$
replace with the following in $P’$
$$\sum^n_{j=1}{a_{ij}x_j-s_i=b_i}$$
$$s_i≥0$$
Any other resource constraint that is already annequality is just transfered to $P’$ as-is.
step 3
All resource constraints in $P’$ are now convereted to equality constraints with the respective slach or surplus variables added.
Next, we need to make sure that the right hand side (RHS)of all constrainnts is non-negative. To do this, any constraint where $b_i<0$, mutiply by -1 on both sides and throughout to obtain:
$$-\sum^n_{j=1}{a_{ij}x_j+s_i=-b_i}$$
step 4
Finally, replace any unconstraint variable in sign $x_j$, with $x^+_j-x^-_j$, and we require that these are non-negative by adding the relevant constraints $x^+_j≥0$ and $x^-_j≥0$ to $P’$.
Afterwards we have to go back to $x_j=x^+_j-x^-_j$ to find the value of $x_j$!
Example
LP:
$$min 3x_1+2x_2$$
$$ s.t. 2x_1≤3$$
$$ 5x_1+2x_2≥-27$$
$$ x_1≥0$$
- change minimisation to maximisation
- change ≥ and ≤ constraints to = and add surplus or slack variables.
$$max -3x_1-2x_2$$
$$ s.t. 2x_1+s_1=3$$
$$ 5x_1+2x_2-s_2=-27$$
$$ x_1≥0$$
$$ s_1≥0$$
$$ s_2≥0$$
- make bounds positive
$$max -3x_1-2x_2$$
$$ s.t. 2x_1+s_1=3$$
$$ -5x_1-2x_2+s_2=+27$$
$$ x_1≥0$$
$$ s_1≥0$$
$$ s_2≥0$$
- remove unrestricted variables
$$max -3x_1-2x^+_2+2x^-_2$$
$$ s.t. 2x_1+s_1=3$$
$$ -5x_1-2x^+_2+2x^-_2+s_2=+27$$
$$ x_1≥0$$
$$ x^+_2≥0$$
$$ x^-_2≥0$$
$$ s_1≥0$$
$$ s_2≥0$$
Some further definitions
Feasibility
A point x is feasible for a given LP if it satisfies all its constraints
The feasible region for that LP is the set of all its feasible points.
An LP is infeasible if its feasibility set is empty; otherwise, it is feasible.
An LP is unbounded if it is feasible but its objective function can be made arbitrarily “good”.
• For example, if an LP is a minimisation problem and unbounded, then its objective value can be made arbitrarily small while
maintaining feasibility. In other words, we can drive the objective value to negative infinity within the feasibility set. Similarly for an unbounded maximisation problem where we can drive the objective value to positive infinity.
A linear program is unbounded only if its feasibility set is an unbounded set. However, an unbounded feasibility set does not necessarily imply that the linear program itself is unbounded (sufficient but not necessary condition).
What is an Optimal Solution?
An assignment of variables that satisfies all the constraints and optimises the objective function is called an optimal solution.
• Given a maximisation LP problem, an optimal solution for the LP is a feasible point
whose value is the largest possible among all feasible points.
• Given a minimisation LP problem, an optimal solution for the LP is a feasible point
whose value is the smallest possible among all feasible points.
Possible outcomes of a LP
For any given linear program there are three possibilities:
- The linear program is infeasible: the feasible region is empty (there is no feasible solution), and so there is no optimal solution.
- The linear program is feasible but the objective is unbounded: the feasible region is an unbounded set, but there is no optimal solution.
- The linear program is feasible and has an optimal solution x* (unique or multiple) within its feasible region: the feasibility set can be either unbounded or bounded.