Linear Programming

In this post, we would demonstrate how to solve linear programming problem using the simplex method of Mathcalc8.
Here is the standard form of linear programming problem that can be solved by simplex :

Maximize p = ∑i=0n-1 ci xi subject to

m constraints of the form

∑i=0n aji xi <= bj

j is from 0 to m-1

with all xi >= 0

Here is an example of problem that is formulated as standard form :

Maximize p = x + y subject to

x + 2 y <= 5

3 x + 4 y <= 6

x, y >= 0

To solve this problem, we define the matrix a, the list b and the list c as follows :

Input 1 : a=((1,2),(3,4))

The first list of a is (1, 2) which is the coefficients of the first constraint on the left handed side. The second list (3, 4) is the coefficients of the second constraint.

Input 2 : b=(5,6)

b is the values in the constraints' right handed side.

Input 3 : c=(1,1)

c is the coefficients for the objective function of p.
Using the function 'simplex', the solution is calculated :

Input 4 : simplex(a,b,c)
Ans. 2, 0, 3, 0, 2

The answer is a matrix with two lists. The first list is (2, 0, 3, 0) which contains the values of the variables x and y. In this case, x is equal to 2 and y is equal to 0. The other two variables are 'slack' variables which are 3 and 0. The second list always has only one number. It is the maximium value p for the problem and it is equal to 2.
In many situation, linear programming problems may not formulated like the standard form. In those cases, we need to do a re-formulation of the problem.
Here is a problem that is not in standard form but we can change it to standard form :

Minimize p = z subject to

x + 2 y + z <= 20

z >= (x + y)/2 

2 x + z = 8

x, y, z >= 0

To re-formulate this problem to standard form :

1. Change 'Minimize p = z' to 'Maximize -p = -z'
2. Change 'z >= (x + y)/2' to '1/2 x + 1/2 y - z <= 0'
3. Change '2 x + z = 8' to two constraints '2 x + z <= 8' and '2 x + z >= 8'. The second constraint is further change to '-2 x - z <= -8'

With the above modifications, the problem becames :

Maximize -p = -z subject to

x + 2 y + z <= 20

1/2 x + 1/2 y - z <= 0

2 x + z <= 8

-2 x - z <= -8

x, y, z >= 0

There are three unknowns x, y and z. To solve the problem :

Input 5 : a=((1,2,1),(1/2,1/2,-1),(2,0,1),(-2,0,-1))

Input 6 : b=(20,0,8,-8)

Input 7 : c=(0,0,-1)

Put a, b, c into the function 'simplex' and the solution is calculated :

Input 8 : simplex(a,b,c)
Ans. 3.2, 0, 1.6, 15.2, 0, 0, 0, -1.6

Therefore, the solution is x = 3.2, y = 0 and z = 1.6, the maximium value -p is equal to the last value -1.6. This means that the minimium value p of the original problem is 1.6.
Next, we try to solve a transportation problem.
There are three factories producing a product A and supply three cities. Below is the cost table showing the manufacturing and delivery cost per A from the three factories to the three cities :

	City 1	City 2	City 3
Factory 1	1.5	2	3
Factory 2	2	3	2
Factory 3	4	3	2.5

There are constraints on the number of A that a factory can produce and there are a requirment of A for each city. If x_ij is the number of A produced by Factory i to City j per month, a constraints table can be stated as below :

	City 1	City 2	City 3	Factory Capability
Factory 1	x11	x12	x13	<= 1000
Factory 2	x21	x22	x23	<= 1500
Factory 3	x31	x32	x33	<= 2000
Total Requirment	= 1500	= 1000	= 1000

We can stated the problem as a linear programming problem below :

Minimize p = 1.5 x11 + 2 x12 + 3 x13 
 + 2 x21 + 3 x22 + 2 x23
 + 4 x31 + 3 x32 + 2.5 x33
   
with constraints,

x11 + x21 + x31 <= 1000
x21 + x22 + x23 <= 1500
x31 + x32 + x33 <= 2000

x11 + x21 + x31 = 1500
x12 + x22 + x32 = 1000
x13 + x21 + x31 = 1000

To solve the problem :

Input 9 : d=one(9)-1

This creates a list of nine 0s.

Input 10 : d(0)=1

Input 11 : d(1)=1

Input 12 : d(2)=1

Input 13 : d1=d

d1 is the list of coefficients for first constraint to be input to matrix a. Repeat the procedure input 9 to 13 with different d(i) set to 1 or -1, we can define d2, d3 ... d6 and d7 = -d4, d8= -d5 and d9 = -d6. Matrix a can then be set as follows :

Input 14 : a=(d1,d2,d3,d4,d7,d5,d8,d6,d9)

Input 15 : b=(1000,1500,2000,1500,-1500,1000,-1000,1000,-1000)

Input 16 : c=(1.5,2,3,2,3,2,4,3,2.5)*-1

Input 17 : simplex(a,b,c)
Ans. 0, 1000, 0, 1500, 0, 0, 0, 0, 1000, 0, 0, 1000, 0, 0, 0, 0, 0, 0, -7500

The solution is :

	City 1	City 2	City 3
Factory 1	0	1000	0
Factory 2	1500	0	0
Factory 3	0	0	1000

The minimium value p is 7500.