Linear Programming Model For Minimizing Distribution Costs

Objective Function and Constraints

Let p₁ be the number of units of product A transported to Edinburgh, q₁ be the number of units of product A transported to Sheffield, r₁ be the number of units of product A transported to London and s₁ be the number of units of product A transported to Cardiff from Southampton.

Let p₂be the number of units of product A transported to Edinburgh, q₂ be the number of units of product A transported to Sheffield, r₂ be the number of units of product A transported to London and s₂ be the number of units of product A transported to Cardiff from Liverpool.

Let p₃ be the number of units of product A transported to Edinburgh, q₃ be the number of units of product A transported to Sheffield, r₃ be the number of units of product A transported to London and s₃ be the number of units of product A transported to Cardiff from Glasgow.

Let Z₁ be the cost of distribution from Southampton, Z₂ be the cost of distribution from Liverpool and Z₃ be the cost of distribution from Glasgow.

The objective of this problem is to minimize the total distribution cost. Thus, according to Dantzig (2016),the objective function is given by:

Minimize Z = Z₁ + Z₂ + Z₃

Now, for Southampton, the distribution cost of one unit of product A is to Edinburgh is £5, the distribution cost of one unit of product A is to Sheffield is £1.5, the distribution cost of one unit of product A is to London is £1 and the distribution cost of one unit of product A is to Cardiff is £2.

Thus, the objective function in this case can be framed as:

Z₁ = 5 p₁ + 2 q₁ + r₁ + 2s₁

The production capacity for Southampton is 4000 units. Therefore,

p₁ + q₁ + r₁ + s₁ ≤ 4000.

The demand for the product A in Edinburgh is 2000 units. Therefore,

p₁ + p₂ + p₃≥ 2000

The demand for the product A in Sheffield is 3000 units. Therefore,

q₁ + q₂ + q₃≥ 2000

The demand for the product A in London is 1000 units. Therefore,

r₁ + r₂ + r₃≥ 1000

The demand for the product A in Edinburgh is 3000 units. Therefore,

s₁ + s₂ + s₃≥ 3000

Now, for Liverpool, the distribution cost of one unit of product A is to Edinburgh is £1.5, the distribution cost of one unit of product A is to Sheffield is £1.2, the distribution cost of one unit of product A is to London is £2.5 and the distribution cost of one unit of product A is to Cardiff is £3.

Distribution Costs and Production Capacity

Thus, the objective function in this case can be framed as:

Z₂ = 1.5 p₂ + 1.2 q₂ + 2.5 r₂ + 3 s₂

The production capacity for Liverpool is 2000 units. Therefore,

p₂ + q₂ + r₂ + s₂ ≤ 2000.

The demand for the product A in Edinburgh is 2000 units. Therefore,

p₁ + p₂ + p₃≥ 2000

The demand for the product A in Sheffield is 3000 units. Therefore,

q₁ + q₂ + q₃≥ 2000

The demand for the product A in London is 1000 units. Therefore,

r₁ + r₂ + r₃≥ 1000

The demand for the product A in Edinburgh is 3000 units. Therefore,

s₁ + s₂ + s₃≥ 3000

Now, for Glasgow, the distribution cost of one unit of product A is to Edinburgh is £1, the distribution cost of one unit of product A is to Sheffield is £2, the distribution cost of one unit of product A is to London is £3 and the distribution cost of one unit of product A is to Cardiff is £5.

Thus, the objective function in this case can be framed as:

Z₃ = p₃ + 2 q₃ + 3 r₃ + 5 s₃

The production capacity for Glasgow is 4000 units. Therefore,

p₃ + q₃ + r₃ + s₃≤ 4000.

The demand for the product A in Edinburgh is 2000 units. Therefore,

p₁ + p₂ + p₃≥ 2000

The demand for the product A in Sheffield is 3000 units. Therefore,

q₁ + q₂ + q₃≥ 2000

The demand for the product A in London is 1000 units. Therefore,

r₁ + r₂ + r₃≥ 1000

The demand for the product A in Edinburgh is 3000 units. Therefore,

s₁ + s₂ + s₃≥ 3000

Thus, the whole problem can be formulated as follows (Vanderbei, 2015):

Minimize Z = (5 p₁ + 2 q₁ + r₁ + 2 s₁) + (1.5 p₂ + 1.2 q₂ + 2.5 r₂ + 3 s₂) + (p₃ + 2 q₃ + 3 r₃ + 5 s₃)

Subject to the constraints: p₁ + q₁ + r₁ + s₁ ≤ 4000

p₂ + q₂ + r₂ + s₂ ≤ 2000

p₃ + q₃ + r₃ + s₃ ≤ 4000

p₁ + p₂ + p₃≥ 2000

q₁ + q₂ + q₃≥ 2000

r₁ + r₂ + r₃≥ 1000

s₁ + s₂ + s₃≥ 3000

and the non-negativity constraints such as p₁, p₂, p₃, p₄, q₁, q₂, q₃, q₄, r₁, r₂, r₃, r₄, s₁, s₂, s₃ ands₄≥ 0 (Zhu&Ukkusuri, 2015).

To solve the given linear programing model using graphical method, at first, the constraints have to be drawn (Rardin&Rardin, 2016).

Let L₁: 4 x₁ + x₂ = 60

Now, the origin, O: (0, 0) satisfies (4 * 0) + (1 * 0) = 0 < 60

Therefore, origin satisfies the inequality 4 x₁ + x₂ ≤ 60

Hence, 4 x₁ + x₂ ≥ 60 is satisfied by all points on L₁ and on the non-origin side of L₁

Linear Programming Formulation

Let L₂: 2 x₁ = 20

Now, the origin, O: (0, 0) satisfies (2 * 0) = 0 < 20

Therefore, origin satisfies the inequality 2 x₁≤ 20

Hence, 2 x₁≥ 20 is satisfied by all points on L₂ and on the non-origin side of L₂

Let L₃: 4 x₁ + 6 x₂ = 240

Now, the origin, O: (0, 0) satisfies (4 * 0) + (6 * 0) = 0 < 240

Therefore, origin satisfies the inequality 4 x₁ + 6 x₂≤ 240

Hence, 4 x₁ + 6 x₂≤ 240 is satisfied by all points on L₃ and on the origin side of L₃

The feasible region is the quadrilateral ABCD in the graph.

Therefore, optimal feasible solution exists and is attained at some extreme points of the feasible region.

Extreme Points	Co-Ordinates	Value of z
A	(10, )	(8 * 10) + (4 * ) = 213.33
B	(10, 20)	(8 * 10) + (4 * 20) = 160
C	(15, 0)	(8 * 15) + (4 * 0) = 120
D	(60, 0)	(8 * 60) + (4 * 0) = 480

The minimum value of z is attained at C.

Therefore, the optimal solution is x₁ = 15, x₂ = 0 and maximum profit = 120.

To solve the same linear programming model with the help of excel solver, the following steps has to be followed. At first the Linear programming model has to be constructed in excel. The constructed model in excel with the appropriate excel formulas is given below in figure 1.

For further analysis using solver, the solver add-in has to be added in excel. After addition of the add-in, the option will be available in the data tab in excel from where the option of solver has been selected and in the solver window that appears, all the necessary information has been inputed. After selecting all the cells correctly and adding the necessary constraints, the solve button is clicked and excel thus gives the following solution as given in figure 2.

It can be seen from the analysis that the minimum cost that is involved for the production of the two types of desks A and B is £120. To complete the production within this cost, the manufacturer can produce 15 desks of type A and no desks of type B. There is n left over time for cutting the desks to their respective sizes. The time allowed for assembling of the desks was more than 20 hours and the assembling work will take 30 hours in order to complete the task in time and within the minimum cost. It can also be seen that there is 180 hours of time left for finishing the work but if more time is taken for finishing the work, the cost will be increased.

Graphical Method and Excel Solver Analysis

Two types of desks are produced by the workshop of a company. Desk type A and desk type B. Cutting the desks, assembling the desks and finishing the desks are the three types of actions that are required to build a desk. The cutting, assembling and finishing time required by desk type A are respectively 4 hours, 2 hours and 4 hours. Desk B requires 1 hour of cutting and 6 hours of finishing. No assembling time is required to produce each unit of desk B. More than 60 hours is available for cutting, more than 20 hours is available for assembling and less than 240 hours is available for finishing. Cost of producing each unit of desk A is £8 and that of desk B is £4. Considering all these factors, the minimum total cost of production will be £120 with the production of 15 units of desk A. No production of desk B is required. Production of desk will increase the total cost of production. Thus, the preparation of only desk A is necessary for the profit of the company.

It can be seen that the minimum cost of production obtained from the solver method is the same as that obtained from the graphical method. Thus, the obtained solution does not have any errors.

The different activities conducted by the manager of the distribution company, their previous activities and the duration of running those activities are given in the table below:  

Activity	Immediate Predecessor(s)	Duration (in weeks)
A	–	4
B	–	3
C	–	8
D	A	10
E	A	8
F	B, D	5
G	C, E	6
H	G	15
I	B	10

An AOA (Activity on Arrow) network diagram for this project can be described as follows (Agyei, 2015):

The calculations for the shortest completion path is shown in the table given below.

Activities A, B and C has no immediate predecessors. Thus, these three are the first activities in the project. Therefore, the earliest start time for these activities will be 0. D has a predecessor A. Thus, the earliest start time for D will be the maximum time taken by A (Levy & Wiest, 2016).

Thus, EST (D) = Time taken by A + EST (A) = 4

Similarly, EST (E) = 4

EST (F) = MAX ((time taken by B + EST (B)), (time taken by D + EST (D)) = MAX (3, 14) = 14

EST (G) = MAX ((time taken by C + EST (C)), (time taken by E + EST (E)) = MAX (8, 12) = 12

EST (H) = Time taken by G + EST (G) = 6 + 12 = 18

Optimal Solution

EST (I) = Time taken by B + EST (B) = 3 + 0 = 3

Thus, the maximum EST has been obtained as 18 + 15 = 33.

Maximum LFT = 33.

LST (I) = LFT (I) – Activity Time = 33 – 0 = 33

LST (H) = LFT (H) – Activity Time = 33 – 0 = 33

LST (G) = LFT (H) – Activity Time = 33 – 15 = 18

LST (F) = LFT (F) – Activity Time = 33 – 0 = 33

LST (E) = LFT (G) – Activity Time = 18 – 6 = 12

LST (D) = LFT (F) – Activity Time = 33 – 5 = 28

LST (C) = LFT (G) – Activity Time = 18 – 6 = 12

LST (B) = MIN {(LFT (I) – Activity Time), (LFT (F) – Activity Time)} = MIN {23, 20} = 20

LST (A) = MIN {(LFT (D) – Activity Time), (LFT (E) – Activity Time)} = MIN {18, 4} = 4

Thus, the minimum slack has been obtained from A, E, G, H. Hence, the critical path will be A – E – G – H

Activity	Immediate Predecessor	Time (Week)	EST	EFT	LST	LFT	Slack   (LST-EST)
A	—	4	0	4	0	4	0
B	—	3	0	3	20	23	20
C	—	8	0	8	4	12	4
D	A	10	4	14	18	28	14
E	A	8	4	12	4	12	0
F	B, D	5	14	19	28	33	14
G	C,E	6	12	18	12	18	0
H	G	15	18	33	18	33	0
I	B	10	3	13	23	33	20
		69	33				A – E- G- H

The slack variable denotes the length of time an activity can be delayed without delaying the entire project. Here, it can be seen that the slack is zero for the points A, E, G and H. Thus, by running the project with these paths, there will be no delay in the process.

Automating the warehouse operations was the decision taken by the management of a distribution company. The manager of the project is also the director of the materials management for the company. The director has consulted with some of the engineer staffs of the company along with some of the personnel who manages the warehouses of the company. Based on the consultation, the director made a list of activities that are related with the project. The activities along with their immediate predecessors and their weekly duration has been presented in the table described above. The warehouse automation process was given a time of 40 weeks to complete the project by the director. The arrow diagram shown in answer 1 gives the possible paths from starting node 1 to the end node 6. The warehouse automation process can be run on any of the paths starting from node 1 and ending at node 6, but time taken by following different paths are different. From the analysis conducted above, it can be said that if the process is followed using the path A – E – G – H, the time taken will be maximum. This is the path following which the maximum time will be taken to complete the automation process in order to finish it on time. Thus the goal of finishing the process within the estimated time can be achieved by following this path A – E – G – H.

Thus, the company must follow this path to complete the process in time. If the company follows some other paths, the time required to complete the process might be longer than the estimated time as the slack time obtained from the other activities is more than the estimated. Thus, the time taken to complete the process will be higher and the process will not be completed in time.

References

Agyei, W. (2015). Project planning and scheduling using PERT and CPM techniques with linear programming: case study. International Journal of Scientific & Technology Research, 4(8), 222-227.

Dantzig, G. (2016). Linear programming and extensions. Princeton university press.

Levy, F. K., & Wiest, J. D. (2016). Management guide to PERT/CPM; with GERT/PDM/DCPM and other networks. Prentice-Hall of India (1979).

Rardin, R. L., &Rardin, R. L. (2016). Optimization in operations research (p. 919). Prentice Hall.

Vanderbei, R. J. (2015). Linear programming. Heidelberg: Springer.

Zhu, F., &Ukkusuri, S. V. (2015). A linear programming formulation for autonomous intersection control within a dynamic traffic assignment and connected vehicle environment. Transportation Research Part C: Emerging Technologies, 55, 363-378.