Мне нужно решить транспортную задачу с этими ограничениями (A — строка «Предложение», B — столбец «Спрос», матрица содержит цены на транспортировку):
Я нашел решение и код работает корректно, потому что задачу я решил и ответы те же. В скобках указан объем для перевозки. Например, в элементе (1, 2) нам нужно перевезти 10 тонн по цене 8 долларов США за тонну = всего 80 долларов США.
Однако в моей задаче есть ограничение. Для перевозки мне нужен 6-тонный грузовик. Например, в найденном решении в элементе (1, 2) мне нужно доставить 10 тонн по цене 8 долларов за тонну. Всего это означает 80 долларов, но с учетом моего ограничения это означает, что мне нужно забронировать 2 грузовика и заплатить 120 долларов.
Итак, принимая во внимание это ограничение и используя метод ветвей и границ, мне нужно найти оптимальное решение. Как мне это сделать?
import gurobipy as gp
from gurobipy import GRB
# Define data
supply = [17, 8, 10, 9] # Supply nodes
demand = [6, 15, 7, 8, 8] # Demand nodes
cost = [
[10, 8, 5, 9, 16],
[4, 3, 4, 11, 12],
[5, 10, 29, 7, 6],
[9, 2, 4, 1, 3]
] # Cost of transportation from supply i to demand j
m = gp.Model()
# Define decision variables
flow = m.addVars(len(supply), len(demand), lb=0, vtype=GRB.INTEGER, name = "flow")
# Define supply constraints
for i in range(len(supply)):
m.addConstr(gp.quicksum(flow[i, j] for j in range(len(demand))) <= supply[i], name=f"supply_{i}")
# Define demand constraints
for j in range(len(demand)):
m.addConstr(gp.quicksum(flow[i, j] for i in range(len(supply))) >= demand[j], name=f"demand_{j}")
# Define objective function
m.setObjective(gp.quicksum(flow[i, j] * cost[i][j] for i in range(len(supply)) for j in range(len(demand))), sense=GRB.MINIMIZE)
# Solve model
m.optimize()
# Print results
if m.status == GRB.OPTIMAL:
print(f"Optimal solution found with objective value {m.objVal:.2f}")
for i in range(len(supply)):
for j in range(len(demand)):
if flow[i, j].x > 0:
print(f"Flow from supply node {i+1} to demand node {j+1}: {flow[i, j].x:.0f}")
else:
print("No solution found or problem is infeasible.")
@Reinderien Я обновил свою таблицу. Да, мне приходится платить за вместимость грузовика, а в моей задаче грузовик может перевозить 6 тонн.
@Grismar Я обновил таблицу и надеюсь, что она станет более понятной.
Пожалуйста, отредактируйте, чтобы уточнить использование грузовиков. Приписан ли каждый грузовик к одной паре точек предложения/точки спроса?
@ Кэри Своуленд. Мы выбираем тип грузовика, в моем конкретном случае - 6-тонный грузовик - и нам нужно использовать его для доставки всех товаров. С учетом этого необходимо найти минимальную цену перевозки.
Присвойте количество грузовиков интегральной переменной и привяжите цену к количеству грузовиков. Когда решателю это дано, он может найти оптимальное решение, при котором на маршруте не используется более одного грузовика.
Кроме того, меньше беспокойтесь о конкретном алгоритме ветвей и границ; просто выберите категорию решателя (MILP) и позвольте ему сделать свою работу.
import pandas as pd
import pulp
truck_capacity = 6
suppliers = pd.RangeIndex(name='supplier', stop=4)
consumers = pd.RangeIndex(name='consumer', stop=5)
supply = pd.Series(
name='supply', index=suppliers, data=(17, 8, 10, 9),
)
demand = pd.Series(
name='demand', index=consumers, data=(6, 15, 7, 8, 8),
)
price_per_tonne = pd.DataFrame(
index=suppliers, columns=consumers,
data=(
(10, 8, 5, 9, 16),
( 4, 3, 4, 11, 12),
( 5, 10, 29, 7, 6),
( 9, 2, 4, 1, 3),
),
).stack()
price_per_tonne.name = 'price'
flow = pd.DataFrame(
index=suppliers, columns=consumers,
data=pulp.LpVariable.matrix(
name='flow_s%d_c%d', cat=pulp.LpContinuous, lowBound=0,
indices=(suppliers, consumers),
),
).stack()
flow.name = 'flow'
trucks = pd.DataFrame(
index=suppliers, columns=consumers,
data=pulp.LpVariable.matrix(
name='trucks_s%d_c%d', cat=pulp.LpInteger, lowBound=0,
indices=(suppliers, consumers),
)
).stack()
trucks.name = 'trucks'
price = truck_capacity * pulp.lpDot(price_per_tonne, trucks)
prob = pulp.LpProblem(name='transportation', sense=pulp.LpMinimize)
prob.setObjective(price)
# The flow must not exceed the supply
for supplier, group in flow.groupby('supplier'):
prob.addConstraint(
name=f'flow_supply_s{supplier}',
constraint=pulp.lpSum(group) <= supply[supplier],
)
# The flow must exactly meet the demand
for consumer, group in flow.groupby('consumer'):
prob.addConstraint(
name=f'flow_demand_c{consumer}',
constraint=pulp.lpSum(group) == demand[consumer],
)
# The capacity must be able to carry the flow
for (supplier, consumer), truck_flow in flow.items():
prob.addConstraint(
name=f'capacity_s{supplier}_c{consumer}',
constraint=truck_flow <= trucks[(supplier, consumer)] * truck_capacity
)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
print('Flow:')
flow = flow.apply(pulp.value).unstack(level='consumer')
print(flow)
print()
print('Trucks:')
trucks = trucks.apply(pulp.value).unstack(level='consumer')
print(trucks)
print()
transportation:
MINIMIZE
60*trucks_s0_c0 + 48*trucks_s0_c1 + 30*trucks_s0_c2 + 54*trucks_s0_c3 + 96*trucks_s0_c4 + 24*trucks_s1_c0 + 18*trucks_s1_c1 + 24*trucks_s1_c2 + 66*trucks_s1_c3 + 72*trucks_s1_c4 + 30*trucks_s2_c0 + 60*trucks_s2_c1 + 174*trucks_s2_c2 + 42*trucks_s2_c3 + 36*trucks_s2_c4 + 54*trucks_s3_c0 + 12*trucks_s3_c1 + 24*trucks_s3_c2 + 6*trucks_s3_c3 + 18*trucks_s3_c4 + 0
SUBJECT TO
flow_supply_s0: flow_s0_c0 + flow_s0_c1 + flow_s0_c2 + flow_s0_c3 + flow_s0_c4
<= 17
...
flow_demand_c0: flow_s0_c0 + flow_s1_c0 + flow_s2_c0 + flow_s3_c0 = 6
...
capacity_s0_c0: flow_s0_c0 - 6 trucks_s0_c0 <= 0
...
Result - Optimal solution found
Objective value: 276.00000000
Enumerated nodes: 0
Total iterations: 33
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.01
Flow:
consumer 0 1 2 3 4
supplier
0 0.0 6.0 5.0 6.0 0.0
1 0.0 6.0 2.0 0.0 0.0
2 6.0 0.0 0.0 0.0 4.0
3 0.0 3.0 0.0 2.0 4.0
Trucks:
consumer 0 1 2 3 4
supplier
0 0.0 1.0 1.0 1.0 0.0
1 0.0 1.0 1.0 0.0 0.0
2 1.0 0.0 0.0 0.0 1.0
3 0.0 1.0 0.0 1.0 1.0
Огромное спасибо за помощь) Большое спасибо)
"в квадрате 1\2 я должен поставить 10 тонн по цене 8$ за тонну" - это вообще не понятно из предоставленных вами данных. Существует один узел с поставкой 10 тонн, но ни один из узлов спроса не требует затрат в 8 долларов для этого узла, и не факт, что поставка пойдет на два узла спроса. Пожалуйста, уточните, что на самом деле означают ваши данные.