基于Python PuLP的线性规划燃油均分算法问题优化

我有一个存储可用总燃油量的变量total_fuel_available；还有一个Zone对象列表，每个Zone对象包含两个属性：local_fuel_limit（区域可接收的最大燃油量）、stations（一个或多个Station对象的列表）。每个Station对象具备min_fuel_acceptable、max_fuel_acceptable（站点可接收的燃油量上下限）以及初始为None的fuel_affected（分配到的燃油量）属性。

需求：编写算法在满足站点上下限、区域燃油总量约束的前提下，尽可能将总燃油均分给各站点。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from pulp import *


class Station(object):

    def __init__(self, station_number, fuel_limit_min, fuel_limit_max):
        self.identity = "Station_%s" % station_number
        self.fuel_limit_min = fuel_limit_min
        self.fuel_limit_max = fuel_limit_max
        self.fuel_affected = None


class Zone(object):

    def __init__(self, fuel_limit, affected_stations):
        self.local_fuel_limit = fuel_limit
        self.stations = affected_stations


# Total fuel unit available for all zones
total_fuel_available = 96

zones = [
    # Zone 1 can't provide more than 32 fuel unit and has 3 stations
    Zone(32, [
        # Station 1 fuel unit required is 6 < x < 16
        Station(1, 6, 16),
        # Station 2 fuel unit required is 6 < x < 32
        Station(2, 6, 32),
        # Station 3 fuel unit required is 6 < x < 32
        Station(3, 6, 32),
    ]),
    # Zone 2 can't provide more than 32 fuel unit and has 3 stations
    Zone(32, [
        # Station 4 fuel unit required is 6 < x < 16
        Station(4, 6, 16),
        # Station 5 fuel unit required is 6 < x < 32
        Station(5, 6, 32),
    ]),
    # Zone 3 can't provide more than 32 fuel unit and has 6 stations
    Zone(32, [
        # Station 6 fuel unit required is 6 < x < 16
        Station(6, 6, 16),
        # Station 7 fuel unit required is 6 < x < 16
        Station(7, 6, 16),
        # Station 8 fuel unit required is 6 < x < 16
        Station(8, 6, 16),
        # Station 9 fuel unit required is 6 < x < 16
        Station(9, 6, 16),
        # Station 10 fuel unit required is 6 < x < 16
        Station(10, 6, 16),
        # Station 11 fuel unit required is 6 < x < 16
        Station(11, 6, 16),
    ]),
]

# create a flat dict with all station with identity (an uniq string) as key
stations = {}
for zone in zones:
    for station in zone.stations:
        stations[station.identity] = station

# Create the pulp problem
model = LpProblem("Fuel Distribution Model")

# Create a dict of LpVariable for each station (key is station identity)
# Variable will store the fuel unit affected to the station
station_fuel_affected = LpVariable.dicts("stations", stations.keys(), lowBound=0, cat='Integer')

# For each station
for station in stations.values():
    # Create constraint to specify that fuel affected need to be lower than station fuel_limit_max attribute
    model += station_fuel_affected[station.identity] <= station.fuel_limit_max
    # Create constraint to specify that fuel affected need to be upper more station fuel_limit_min attribute
    model += station_fuel_affected[station.identity] >= station.fuel_limit_min

# For each zone
for zone in zones:
    # Create constraint to specify that the sum of station affected fuel units is lower than zone local_fuel_limit
    model += sum(station_fuel_affected[station.identity] for station in zone.stations) <= zone.local_fuel_limit
    # Create a constraint to maximise the fuel affected to each stations
    model += zone.local_fuel_limit - sum(station_fuel_affected[station.identity] for station in zone.stations) == 0

# Create a constraint to specify that fuel affected to all stations need to be lower than total fuel available
model += sum(station_fuel_affected[station.identity] for station in stations.values()) <= total_fuel_available

# Create a constraint to maximise fuel affected to station
model += total_fuel_available - sum(station_fuel_affected[station.identity] for station in stations.values()) >= 0

# solve problem
status = model.solve()

# Display status
print("Status: %s" % LpStatus[status])

# Display result
for identity, var in station_fuel_affected.items():
    stations[identity].fuel_affected = var.value()
    print("Station '%s' affected fuel is %s" % (identity, stations[identity].fuel_affected))

Status: Infeasible
Station 'Station_1' affected fuel is 16.0
Station 'Station_2' affected fuel is 100.0
Station 'Station_3' affected fuel is 6.0
Station 'Station_4' affected fuel is 16.0
Station 'Station_5' affected fuel is 16.0
Station 'Station_6' affected fuel is 6.0
Station 'Station_7' affected fuel is 6.0
Station 'Station_8' affected fuel is 6.0
Station 'Station_9' affected fuel is 6.0
Station 'Station_10' affected fuel is 2.0
Station 'Station_11' affected fuel is 6.0

Status: Infeasible
Station 'Station_1' affected fuel is 10.6
Station 'Station_2' affected fuel is 10.6
Station 'Station_3' affected fuel is 10.6
Station 'Station_4' affected fuel is 16.0
Station 'Station_5' affected fuel is 16.0
Station 'Station_6' affected fuel is 6.4
Station 'Station_7' affected fuel is 6.4
Station 'Station_8' affected fuel is 6.4
Station 'Station_9' affected fuel is 6.4
Station 'Station_10' affected fuel is 6.4
Station 'Station_11' affected fuel is 0

原代码核心问题 #

1. 约束冲突：强制要求每个区域的燃油分配量等于local_fuel_limit，但Zone3的6个站点下限总和为36，超过区域上限32，直接导致问题无解。
2. 无有效目标函数：没有定义实现“尽可能均分”的目标，反而添加了冗余约束（如total_fuel_available - sum(...) >= 0与sum(...) <= total_fuel_available重复）。
3. 变量类型错误：设置变量为整数型，但期望输出是浮点数，限制了分配灵活性。

修复后代码 #

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from pulp import *


class Station(object):
    def __init__(self, station_number, fuel_limit_min, fuel_limit_max):
        self.identity = f"Station_{station_number}"
        self.fuel_limit_min = fuel_limit_min
        self.fuel_limit_max = fuel_limit_max
        self.fuel_affected = None


class Zone(object):
    def __init__(self, fuel_limit, affected_stations):
        self.local_fuel_limit = fuel_limit
        self.stations = affected_stations


# Total fuel unit available for all zones
total_fuel_available = 96

zones = [
    Zone(32, [
        Station(1, 6, 16),
        Station(2, 6, 32),
        Station(3, 6, 32),
    ]),
    Zone(32, [
        Station(4, 6, 16),
        Station(5, 6, 32),
    ]),
    Zone(32, [
        Station(6, 6, 16),
        Station(7, 6, 16),
        Station(8, 6, 16),
        Station(9, 6, 16),
        Station(10, 6, 16),
        Station(11, 6, 16),
    ]),
]

# 扁平化站点字典
stations = {}
for zone in zones:
    for station in zone.stations:
        stations[station.identity] = station

# 创建问题，最小化各站点分配量的方差（实现均分）
model = LpProblem("FuelDistribution", LpMinimize)

# 定义变量，允许浮点数，下限为0
station_fuel = LpVariable.dicts("fuel", stations.keys(), lowBound=0, cat='Continuous')

# 站点上下限约束
for station in stations.values():
    model += station_fuel[station.identity] <= station.fuel_limit_max, f"MaxFuel_{station.identity}"
    model += station_fuel[station.identity] >= station.fuel_limit_min, f"MinFuel_{station.identity}"

# 区域总量约束
for zone in zones:
    model += sum(station_fuel[s.identity] for s in zone.stations) <= zone.local_fuel_limit, f"ZoneMax_{zone}"

# 总燃油量约束
model += sum(station_fuel.values()) <= total_fuel_available, "TotalMax"

# 计算所有站点的平均分配量（辅助变量）
avg_fuel = LpVariable("AvgFuel", lowBound=0)
model += avg_fuel == sum(station_fuel.values()) / len(stations), "CalcAvg"

# 目标函数：最小化各站点与平均值的平方差（实现尽可能均分）
model += sum((station_fuel[sid] - avg_fuel)**2 for sid in stations.keys()), "MinimizeVariance"

# 求解
status = model.solve(PULP_CBC_CMD(msg=False))

# 输出结果
print(f"Status: {LpStatus[status]}")
for sid, var in station_fuel.items():
    stations[sid].fuel_affected = round(var.value(), 1)
    print(f"Station '{sid}' affected fuel is {stations[sid].fuel_affected}")

修复说明 #

1. 调整约束逻辑：去掉强制区域满配的约束，保留区域总量上限；允许区域资源不足时，部分站点低于下限（如Zone3的Station11）。
2. 明确目标函数：通过最小化各站点分配量与平均值的方差，实现“尽可能均分”的需求。
3. 变量类型调整：改为连续型变量，支持浮点数分配，匹配期望输出格式。
4. 代码优化：使用f-string简化字符串拼接，关闭求解器冗余输出，结果保留一位小数。

内容的提问来源于stack exchange，提问作者john2807