We will solve the mathematical optimization problem. This time, we will solve it using the linear programming method. A library called PuLP is a major library for solving linear programming, so we will use it. Click here if you want to know about mathematical optimization and PuLP Introduction to solving linear programming problems with PuLP
Sample problems are quoted from this site NTT Data Mathematical Optimizer Sample Problem Collection
See next page for examples 2.1 Mixing problem
The question is how to get the minimum cost of 30%: 30%: 40% from nine alloys with different lead, zinc and tin blends.
Formulation problem
#Set for the purpose of minimizing the function
problem1 = pulp.LpProblem("Problem-1", pulp.LpMinimize)
#Variable setting(Variable name, minimum value, maximum value, type)
#Percentage of 9 alloys
x1 = pulp.LpVariable('X1', 0, 1, 'Continuous')
x2 = pulp.LpVariable('X2', 0, 1, 'Continuous')
x3 = pulp.LpVariable('X3', 0, 1, 'Continuous')
x4 = pulp.LpVariable('X4', 0, 1, 'Continuous')
x5 = pulp.LpVariable('X5', 0, 1, 'Continuous')
x6 = pulp.LpVariable('X6', 0, 1, 'Continuous')
x7 = pulp.LpVariable('X7', 0, 1, 'Continuous')
x8 = pulp.LpVariable('X8', 0, 1, 'Continuous')
x9 = pulp.LpVariable('X9', 0, 1, 'Continuous')
#Objective function(Define the cost you want to minimize)
problem1 += 7.3*x1 + 6.9*x2 + 7.3*x3 + 7.5*x4 + 7.6*x5 + 6.0*x6 + 5.8*x7 + 4.3*x8 + 4.1*x9
#Constraint setting
#1 in total(100％)To
problem1 += x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 == 1
#Mixing ratio of lead
problem1 += 20*x1 + 50*x2 + 30*x3 +30*x4 + 30*x5 + 60*x6 + 40*x7 + 10*x8 + 10*x9 == 30
#Mixing ratio of zinc
problem1 += 30*x1 + 40*x2 + 20*x3 +40*x4 + 30*x5 + 30*x6 + 50*x7 + 30*x8 + 10*x9 == 30
#Mixing ratio of tin
problem1 += 50*x1 + 10*x2 + 50*x3 +30*x4 + 40*x5 + 10*x6 + 10*x7 + 60*x8 + 80*x9 == 40
#Confirmation of problem definition
print(problem1)
#Run
result = problem1.solve()
#Check the result
print("X1:" ,pulp.value(x1))
print("X2:" ,pulp.value(x2))
print("X3:" ,pulp.value(x3))
print("X4:" ,pulp.value(x4))
print("X5:" ,pulp.value(x5))
print("X6:" ,pulp.value(x6))
print("X7:" ,pulp.value(x7))
print("X8:" ,pulp.value(x8))
print("X9:" ,pulp.value(x9))
print("Cost:" ,pulp.value(problem1.objective))
Output when confirmed by the defined problem print function.
Formulation problem output 1
#Confirmation of problem definition
Problem-1:
MINIMIZE
7.3*X1 + 6.9*X2 + 7.3*X3 + 7.5*X4 + 7.6*X5 + 6.0*X6 + 5.8*X7 + 4.3*X8 + 4.1*X9 + 0.0
SUBJECT TO
_C1: X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 = 1
_C2: 20 X1 + 50 X2 + 30 X3 + 30 X4 + 30 X5 + 60 X6 + 40 X7 + 10 X8 + 10 X9
= 30
_C3: 30 X1 + 40 X2 + 20 X3 + 40 X4 + 30 X5 + 30 X6 + 50 X7 + 30 X8 + 10 X9
= 30
_C4: 50 X1 + 10 X2 + 50 X3 + 30 X4 + 40 X5 + 10 X6 + 10 X7 + 60 X8 + 80 X9
= 40
VARIABLES
X1 <= 1 Continuous
X2 <= 1 Continuous
X3 <= 1 Continuous
X4 <= 1 Continuous
X5 <= 1 Continuous
X6 <= 1 Continuous
X7 <= 1 Continuous
X8 <= 1 Continuous
X9 <= 1 Continuous
Formulation problem output 2
#Check the result
X1: 0.0
X2: 0.0
X3: 0.0
X4: 0.0
X5: 0.0
X6: 0.4
X7: 0.0
X8: 0.6
X9: 0.0
Cost: 4.98
Looking at the results, the cost is minimized with 40% of alloy No. 6 and 60% of alloy No. 8, which is 4.98.
See next page for examples 2.2 Transport issues
Transport packages from two factories (1, 2) to three stores (a, b, c). The problem of minimizing transportation costs, as the amount of supply and demand is fixed for each.
Transportation problems
#Set for the purpose of minimizing the function
problem2 = pulp.LpProblem("Problem-2", pulp.LpMinimize)
#Variable setting(Variable name, minimum value, maximum value, type)
#The amount of delivery from the factory to the store was used as a variable, and the maximum amount of supply was set as the maximum value.
x1a = pulp.LpVariable('X1a', 0, 200, 'Continuous')
x1b = pulp.LpVariable('X1b', 0, 200, 'Continuous')
x1c = pulp.LpVariable('X1c', 0, 200, 'Continuous')
x2a = pulp.LpVariable('X2a', 0, 200, 'Continuous')
x2b = pulp.LpVariable('X2b', 0, 200, 'Continuous')
x2c = pulp.LpVariable('X2c', 0, 200, 'Continuous')
#Objective function(Define the cost you want to minimize)
problem2 += 3.4*x1a + 2.2*x1b + 2.9*x1c + 3.4*x2a + 2.4*x2b + 2.5*x2c
#Constraint setting
#Supply capacity of each factory
problem2 += x1a + x1b + x1c <= 250
problem2 += x2a + x2b + x2c <= 450
#Demand for each store
problem2 += x1a + x2a == 200
problem2 += x1b + x2b == 200
problem2 += x1c + x2c == 200
#Confirmation of problem definition
print(problem2)
#Run
result = problem2.solve()
#Check the result
print("X1a:" ,pulp.value(x1a))
print("X1b:" ,pulp.value(x1b))
print("X1c:" ,pulp.value(x1c))
print("X2a:" ,pulp.value(x2a))
print("X2b:" ,pulp.value(x2b))
print("X2c:" ,pulp.value(x2c))
print("Cost:" ,pulp.value(problem2.objective))
Output when confirmed by the defined problem print function.
Transport problem output 1
#Confirmation of problem definition
Problem-2:
MINIMIZE
3.4*X1a + 2.2*X1b + 2.9*X1c + 3.4*X2a + 2.4*X2b + 2.5*X2c + 0.0
SUBJECT TO
_C1: X1a + X1b + X1c <= 250
_C2: X2a + X2b + X2c <= 450
_C3: X1a + X2a = 200
_C4: X1b + X2b = 200
_C5: X1c + X2c = 200
VARIABLES
X1a <= 200 Continuous
X1b <= 200 Continuous
X1c <= 200 Continuous
X2a <= 200 Continuous
X2b <= 200 Continuous
X2c <= 200 Continuous
Transport problem output 2
#Check the result
X1a: -0.0
X1b: 200.0
X1c: -0.0
X2a: 200.0
X2b: 0.0
X2c: 200.0
Cost: 1620.0
200 from factory 1 to store b From factory 2, 200 to store a, 200 to store c The result is that the minimum cost is 1620. Looking at the answer to the example, the cost is the same, but the transportation volume is different. However, I think that there is no problem with this answer because the purpose (minimization of cost) has been achieved.
See next page for examples 2.3 Multi-period planning problem
There is a factory that processes two types of raw materials A and B to produce two types of products I and II. The problem of making a production plan for the next three months. The amount of raw materials used to produce one unit of each product, the production / inventory cost of each product, the monthly shipment amount of each product, and the monthly available amount of each raw material are given.
Multi-period planning problem
#Set for the purpose of minimizing the function
problem3 = pulp.LpProblem("Problem-3", pulp.LpMinimize)
#Variable setting(Variable name, minimum value, maximum value, type)
#production(Prodution)I
Pi1 = pulp.LpVariable('Prodution I_1', 0, 170, 'Integer')
Pi2 = pulp.LpVariable('Prodution I_2', 0, 170, 'Integer')
Pi3 = pulp.LpVariable('Prodution I_3', 0, 170, 'Integer')
#production(Prodution)II
Pii1 = pulp.LpVariable('Prodution II_1', 0, 160, 'Integer')
Pii2 = pulp.LpVariable('Prodution II_2', 0, 160, 'Integer')
Pii3 = pulp.LpVariable('Prodution II_3', 0, 160, 'Integer')
#stock(Stock)I
Si1 = pulp.LpVariable('Stock I_1', 0, 170, 'Integer')
Si2 = pulp.LpVariable('Stock I_2', 0, 170, 'Integer')
#stock(Stock)II
Sii1 = pulp.LpVariable('Stock II_1', 0, 160, 'Integer')
Sii2 = pulp.LpVariable('Stock II_2', 0, 160, 'Integer')
#Objective function(Define the cost you want to minimize)
problem3 += (75*Pi1 + 50*Pii1 + 8*Si1 + 7*Sii1) + (75*Pi2 + 50*Pii2 + 8*Si2 + 7*Sii2) + (75*Pi2 + 50*Pii2)
#Constraint setting
#Restriction on the number of production by material
problem3 += 2*Pi1 + 7*Pii1 <= 920
problem3 += 5*Pi1 + 3*Pii1 <= 790
problem3 += 2*Pi2 + 7*Pii2 <= 750
problem3 += 5*Pi2 + 3*Pii2 <= 600
problem3 += 2*Pi3 + 7*Pii3 <= 500
problem3 += 5*Pi3 + 3*Pii3 <= 480
#Shipment and inventory constraints
problem3 += Pi1 - Si1 == 30
problem3 += Pii1 - Sii1 == 20
problem3 += Pi2 + Si1 - Si2 == 60
problem3 += Pii2 + Sii1 - Sii2 == 50
problem3 += Pi3 + Si2 == 80
problem3 += Pii3 + Sii2 == 90
#Confirmation of problem definition
print(problem3)
#Run
result = problem3.solve()
#Check the result
print("---1st month---")
print("Prodution I_1:" ,pulp.value(Pi1))
print("Prodution II_1:" ,pulp.value(Pii1))
print("Stock I_1:" ,pulp.value(Si1))
print("Stock II_1:" ,pulp.value(Sii1))
print("---2nd month---")
print("Prodution I_2:" ,pulp.value(Pi2))
print("Prodution II_2:" ,pulp.value(Pii2))
print("Stock I_2:" ,pulp.value(Si2))
print("Stock II_2:" ,pulp.value(Sii2))
print("---3rd month---")
print("Prodution I_3:" ,pulp.value(Pi3))
print("Prodution II_3:" ,pulp.value(Pii3))
print("Cost:" ,pulp.value(problem3.objective))
Output when confirmed by the defined problem print function.
Multi-period planning problem output 1
#Confirmation of problem definition
Problem-3:
MINIMIZE
50*Prodution_II_1 + 100*Prodution_II_2 + 75*Prodution_I_1 + 150*Prodution_I_2 + 7*Stock_II_1 + 7*Stock_II_2 + 8*Stock_I_1 + 8*Stock_I_2 + 0
SUBJECT TO
_C1: 7 Prodution_II_1 + 2 Prodution_I_1 <= 920
_C2: 3 Prodution_II_1 + 5 Prodution_I_1 <= 790
_C3: 7 Prodution_II_2 + 2 Prodution_I_2 <= 750
_C4: 3 Prodution_II_2 + 5 Prodution_I_2 <= 600
_C5: 7 Prodution_II_3 + 2 Prodution_I_3 <= 500
_C6: 3 Prodution_II_3 + 5 Prodution_I_3 <= 480
_C7: Prodution_I_1 - Stock_I_1 = 30
_C8: Prodution_II_1 - Stock_II_1 = 20
_C9: Prodution_I_2 + Stock_I_1 - Stock_I_2 = 60
_C10: Prodution_II_2 + Stock_II_1 - Stock_II_2 = 50
_C11: Prodution_I_3 + Stock_I_2 = 80
_C12: Prodution_II_3 + Stock_II_2 = 90
VARIABLES
0 <= Prodution_II_1 <= 160 Integer
0 <= Prodution_II_2 <= 160 Integer
0 <= Prodution_II_3 <= 160 Integer
0 <= Prodution_I_1 <= 170 Integer
0 <= Prodution_I_2 <= 170 Integer
0 <= Prodution_I_3 <= 170 Integer
0 <= Stock_II_1 <= 160 Integer
0 <= Stock_II_2 <= 160 Integer
0 <= Stock_I_1 <= 170 Integer
0 <= Stock_I_2 <= 170 Integer
Multi-period planning problem output 2
#Check the result
---1st month---
Prodution I_1: 98.0
Prodution II_1: 100.0
Stock I_1: 68.0
Stock II_1: 80.0
---2nd month---
Prodution I_2: 8.0
Prodution II_2: 7.0
Stock I_2: 16.0
Stock II_2: 37.0
---3rd month---
Prodution I_3: 64.0
Prodution II_3: 53.0
Cost: 15741.0
The result was output that such a production plan should be made. The cost is lower than the answer to the example. You may have gotten better results than the example tool.
Recommended Posts