This pages tries to illustrate the use of Linear Programming (LP) to solve some optimization tasks. The first task is the problem example from LP wiki-page [1] solved using Simplex algorithm of Dantzig [2]. The second task is a clique covering problem represented as Integer Linear Programming (ILP) task or even as Zero-One Linear Programming (ZOLP) task.
The first is how to calculate how much to plant wheat and how much
barley when there are constraints on land area and on fertilizer and
pesticide amounts. The goal is to maximize potential income when
selling grain. Let's assume the following numbers (notation is the
same as in the original
example)
[1]:
x1 - area for wheat, x2 - area for
barley, L - total available area as a constraint
(e.g., in km2-s);
F - the amount of available fertilizer (e.g., in kilograms),
F1 - the amount of fertilizer needed for wheat per area
unit, F2 - the same for barley;
P - the amount of available pesticide (e.g., in kilograms),
P1 - the amount of pesticide needed for wheat per area
unit, P2 - the same for barley; and
S1 - the selling price of wheat per area unit,
S2 - the proce for barley, S - the total
income or reveneu (the obect of maximizing, the "objective
function").
Now the problem can be expressed as:
| Maximize: | S1 ∙ x1 + S2 ∙ x2 = S | (maximize the revenue) |
| Subjec to: | x1 + x2 ≤ L | (total area limit) |
| F1 ∙ x1 + F2 ∙ x2 ≤ F | (the amount of fertilizer that can be used) | |
| P1 ∙ x1 + P2 ∙ x2 ≤ P | (the amount of pesticide that can be used) | |
| x1 ≥ 0 , x2 ≥ 0 | (areas can not be negative) |
And in the matrix form as [1]:
| Maximize: | |
| Subjec to: | |
Let's assume that the following numbers are used (probably very
unrealistic but illustrate the solving pretty well):
L = 55 (total available area);
F = 200 (the total amount of available fertilizer),
F1 = 4 , F2 = 3 (the
amount of fertilizer needed per area unit for wheat and barley,
respectively);
P = 200 (the total amount of available pesticide),
P1 = 3 , P2 = 4 (the
amount of pesticide needed per area unit for wheat and barley,
respectively);
S1 = 5 , F2 = 6 (the
selling price per area unit of wheat and barley, respectively).
The equations can be rewritten as:
| Maximize: | 5 ∙ x1 + 6 ∙ x2 = S | (maximize the revenue) |
| Subjec to: | x1 + x2 ≤ 55 | (total area limit) |
| 4 ∙ x1 + 3 ∙ x2 ≤ 200 | (the amount of fertilizer that can be used) | |
| 3 ∙ x1 + 4 ∙ x2 ≤ 200 | (the amount of pesticide that can be used) | |
| x1 ≥ 0 , x2 ≥ 0 | (areas can not be negative) |
For solving, the
Simplex algorithm
of Dantzig [2] has been used. When combining both calculations and
polygons, the technique is quite obvious. It is clear, that x1
and x2 must both be between 0 and 55. Let assume two extreme
cases - the land is used only for wheat or only for balrey:
1)
Area: x1=0 ==> 0≤x2≤55
;
Fertilizer: 4∙0+3∙x2≤200 ==>
x2≤200/3 ==> x2≤66.(6)
;
Pesticide: 3∙0+4∙x2≤200 ==>
x2≤200/4 ==> x2≤50
.
2)
Area: x2=0 ==> 0≤x1≤55
;
Fertilizer: 4∙x1+3∙0≤200 ==>
x1≤200/4 ==> x1≤50
;
Pesticide: 3∙x1+4∙0≤200 ==>
x1≤200/3 ==> x1≤66.(6)
.
These constraints define three lines on x1-x2-graph right - area (black), fertilizer (blue) and pesticide (red). The area below these lines (gray) contains all legal solutions. The optimal solution is on the polygon boundary - walking through the corners the optimum can be found (unless there "cycles" like in some types of tasks). The table below shows results for all corners plus one random point inside the gray area. The corner 0-0 is not show because there will be no revenue.
| x1 (wheat area) |
x2 (barley area) |
L (total area) |
F (fertilizer used) |
P (pesticide used) |
S (revenue) |
Point |
| 50 | 0 | 50 | 200 | 150 | 250 | (1) |
| 35 | 20 | 55 | 200 | 185 | 295 | (2) |
| 25 | 25 | 50 | 175 | 175 | 275 | (x) |
| 20 | 35 | 55 | 185 | 200 | 310 | (3) |
| 0 | 50 | 50 | 150 | 200 | 300 | (4) |
It can be seen that the best solution is when the area for wheat is 20 and for barley 35. All of the land has been used. The same about the fertilizer.
An OpenDocument spreadsheet containing the same task can be found here. Input data can be changed, some constraint checking is done by conditional formatting.
[1] "Linear programming", Wikipedia, the free encyclopedia -
https://en.wikipedia.org/wiki/Linear_programming
(2020.02.14).
[2] "Simplex algorithm", Wikipedia, the free encyclopedia -
https://en.wikipedia.org/wiki/Simplex_algorithm
(2020.02.14).
 |
 |
The second example shows how to use Linear Programming (LP) to solve clique covering problem. The task is to find the smallest number of full sub-graphs (cliques) to cover all nodes of the symmetrical graph (see the figure right). To be precise, this is not LP anymore but Integer Linear Programming (ILP) that has combinatorial complexity. The main difference is that instead of real number, only integers are allowed thus making the calculations hard.
The graph has five cliques - A (nodes 2, 3 & 4), B (3, 4 & 6), C (1 & 3), D (1 & 5) and E (2 & 5). The coverage matrix right shows all nodes and cliques that cover them. Node 6 is the only one covered by one clique only (B). The other nodes are covered by two or more clique thus allowing to combine them. The legal solutions are as follows - A-B-D, B-D-E and B-C-E (found using with Petrik's method below).
As ILP task, the coverage matrix is represented as a zero-one matrix A (rows are nodes and columns are cliques). The solution to be found is a vector x of cliques to be selected (one column only). The multiplication result of A and x results in an one column matrix showing how many cliques are covering one or another node. For a legal solution, A ∙ x ≥ |1| - all nodes must be covered by a clique at least.
 |
For the solution of using cliques B, D & E, the matrices and their multiplication is shown right.
It should be noted that the clique covering problem can be solved as a Zero-One Linear Programming (ZOLP) task too. This would simplify calculations somewhat - instead of multiplications and additions, logical AND and OR operations can be used. The overall complexity is still the same - combinatorial. Also, with ILP, the result shows how many cliques are covering one or another node but with ZOLP, one can see only whether a node has been covered or not.
The idea of the Petrik's method is to express the task as a Boolean satisfiability problem - all nodes must be covered by at least one clique. For instance, to cover node 1, either clique C or D must be selected. To cover all nodes, the following product-of-sums must be true - (C+D)(A+E)(A+B+C)(A+B)(D+E)(B)==1. Since B is the only clique covering node 6, it must be selected anyway - B=1. Taking this into account and simplifying, the problem will be simpler - (C+D)(A+E)(D+E)==1. After rewriting the equation as sum-of-products, all legal combinations are found. After minimizing, the result is - AD+DE+CE==1. This means that in addition to cliques B, two other ones should be selected - either A & D, D & E or C & E.
Last modified 2020.03.25.