1

1

S={1,2,3,4,5,6}S=\{1,2,3,4,5,6\}S1={1,3,4}S_1=\{1,3,4\}
S2={2,5}S_2=\{2,5\} , S3={6}S_3=\{6\}

SS 111S1S_11,3,4

C={1,2,...,n}C=\{1,2,...,n\}R={1,2,...,m}R=\{1,2,...,m\}RRrr1rrcrc_rrr0-1xrx_rxrx_r rr10


rRcrxr\sum_{r \in R} c_r x_r

1

rR:rは顧客iを含むxr=1\sum_{r \in R:r\text{は顧客}i\text{を含む}} x_r = 1 for iCi \in C

C={1,2,3,4,5}C=\{1,2,3,4,5\}, R={1,2,3,4,5,6,7,8,9,10}R=\{1,2,3,4,5,6,7,8,9,10\},
c=[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10]=[10,20,30,40,50,60,70,80,90,100]]c=[c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9,c_{10}]=[10,20,30,40,50,60,70,80,90,100]]

- 1. [1,2][1,2]
- 2. [2,3][2,3]
- 3. [3,4][3,4]
- 4. [4,5][4,5]
- 5. [1,3][1,3]
- 6. [2,4][2,4]
- 7. [3,5][3,5]
- 8. [1,2,3][1,2,3]
- 9. [2,3,4][2,3,4]
- 10. [3,4,5][3,4,5]

pyhon
google colaboratorypyhon1 !pip install pulp

!pip install pulp
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpStatus, value
# Initialize the model
prob = LpProblem("SetPartition", LpMinimize)
# Parameters
routes = range(10)
customers = range(5)
# c: route costs
c = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
# Binary decision variables
x = LpVariable.dicts("x", routes, 0, 1, cat='Binary')
# Objective function
prob += lpSum([c[r]*x[r] for r in routes])
# Constraints
customer_route_matrix = [
[1, 0, 0, 0, 1, 0, 0, 1, 0, 0], # customer 0
[1, 1, 0, 0, 0, 1, 0, 1, 1, 0], # customer 1
[0, 1, 1, 0, 1, 0, 1, 1, 1, 1], # customer 2
[0, 0, 1, 1, 0, 1, 0, 0, 1, 1], # customer 3
[0, 0, 0, 1, 0, 0, 1, 0, 0, 1] # customer 4
]
for i in customers:
prob += lpSum([x[r]*customer_route_matrix[i][r] for r in routes]) == 1
# Solve the problem
prob.solve()
print(f"Status: {LpStatus[prob.status]}")
print(f"Optimal Value: {value(prob.objective)}")
for v in prob.variables():
print(f"{v.name} = {v.varValue}")

x0=x9=1x_0=x_9=1 Python0x0x_01x9x_910

11,2103,4,51101,2,3,4,5,110+100=110

48140+80=120