[Mathematical optimization problem] Linear programming using PuLP

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

Formulation problem

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.

Transportation problems

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.

Multi-period planning problem

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

[Mathematical optimization problem] Linear programming using PuLP
Production planning optimization using linear programming (Python + PuLP)
Linear Programming with PuLP
Linear programming + hands-on of pulp
Mathematical Optimization Modeler (PuLP) Cheat Sheet (Python)
Mathematical optimization RPG
Optimization learned with OR-Tools [Linear programming: multi-stage model]
Optimization learned with OR-Tools [Linear programming: project management]
Optimization learned with OR-Tools [Linear programming: Let's refine oil]
Python optimization library Pulp
Programming problem "4 Queen Square"
Linear combination optimization (timetable)
Programming problem collection (Q31-Q35)
Calculation problem using mod
[Memo] I implemented a multi-product transportation problem (new mathematical optimization)