针对最长行驶距离进行优化

Question

我有一个关于优化最长旅行距离的问题。

假设有一条高速公路，我们可以根据一组涉及 3 种代币的费用规则x, y, z行驶特定距离。 您将获得每种类型的代币的固定数量，并且费用规则采用以下形式，并被要求最大化行驶距离，

30x's + 10y's + 10z's -> d_1km
30x's + 10y's + 0z's  -> d_2km
30x's + 0y's + 0z's   -> d_3km
5x's + 0y's + 0z's    -> d_4km
5x's + 3y's + 3z's    -> d_5km

我最初的想法是从大到小的距离进行排序，并尝试按该顺序使用我的代币，但我相信这将导致我错过一些边缘交易，这将使我走得更远。我相信我已经看到了一些数学概念来优化这种类型的问题，但我记不清这叫什么了。有关如何解决此问题的任何提示或指示，我们将不胜感激！

Answer 1

这里可能也有一种动态规划方法，但解决此类问题的标准方法是将其设置为整数线性规划 (ILP)，因为决策变量自然是整数。 有几个python包可以建立模型(pulp，pyomo，CVXOPT，其他)，以及几个自由求解器，可以使用"分支和绑定"或类似的算法解决ILP问题，例如CBC和glpk。 大多数可以设置模型的框架都独立于求解器。

下面是使用单独安装的cbc求解器在pyomo中的问题设置示例。

法典

import pyomo.environ as pyo
# DATA
#                  dist  X   Y   Z
highways = { 'h1': (24, (30, 10, 10)),
'h2': (17, (30, 10, 0 )),
'h3': (22, (30, 0,  0 )),
'h4': (8,  (5,  0,  0 )),
'h5': (13, (5,  3,  3 ))}
tokens = {'X': 64, 'Y': 15, 'Z': 12}
# a convenience...
token_types = list('XYZ')
costs = {}
for idx, t in enumerate(token_types):
for h in highways.keys():
costs[(h, t)] = highways[h][1][idx]
# set up ILP
m = pyo.ConcreteModel()
# SETS
m.H = pyo.Set(initialize=highways.keys())
m.T = pyo.Set(initialize=token_types)      # token types
# PARAMS
m.tokens_avail = pyo.Param(m.T, initialize=tokens)
m.dist         = pyo.Param(m.H, initialize={k:v[0] for k, v in highways.items()})
m.cost         = pyo.Param(m.H, m.T, initialize=costs)
# VARS
m.pay    = pyo.Var(m.H, m.T, domain=pyo.NonNegativeIntegers)   # pay this many tokens of type t on highway h
m.travel = pyo.Var(m.H, domain=pyo.NonNegativeIntegers)        # travel on highway h this many times
# OBJECTIVE
# maximize distance traveled, add some tiny penalty to prevent spending unneeded tokens
m.obj = pyo.Objective(expr=pyo.sum_product(m.dist, m.travel) - 0.01 * pyo.sum_product(m.pay), sense=pyo.maximize)
# CONSTRAINTS
# limit token use to available, for each type
def token_limit(m, t):
return sum(m.pay[h, t] for h in highways) <= m.tokens_avail[t]
m.C1 = pyo.Constraint(m.T, rule=token_limit)
# pay the cost of each trip
def pay_tokens(m, h, t):
if not m.cost[h, t]:
return pyo.Constraint.Skip
return m.travel[h] <= m.pay[h, t] / m.cost[h, t]
m.C2 = pyo.Constraint(m.H, m.T, rule=pay_tokens)
# check the model...
m.pprint()

solver = pyo.SolverFactory('cbc')
res = solver.solve(m)
print(res)
tot_distance = pyo.sum_product(m.dist, m.travel)
print(f'total distance achieved: {pyo.value(tot_distance)}')
for idx in m.travel.index_set():
if m.travel[idx]:
print(f'travel {idx} {pyo.value(m.travel[idx])} times')
for idx in m.pay.index_set():
if m.pay[idx]:
print(f'pay {pyo.value(m.pay[idx])} {idx[1]} tokens on {idx[0]}')

输出(部分)

Problem: 
- Name: unknown
Lower bound: -115.16
Upper bound: -115.16
Number of objectives: 1
Number of constraints: 13
Number of variables: 20
Number of binary variables: 0
Number of integer variables: 20
Number of nonzeros: 20
Sense: maximize
Solver: 
- Status: ok
User time: -1.0
System time: 0.0
Wallclock time: 0.01
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics: 
Branch and bound: 
Number of bounded subproblems: 0
Number of created subproblems: 0
Black box: 
Number of iterations: 2
Error rc: 0
Time: 0.01609015464782715
Solution: 
- number of solutions: 0
number of solutions displayed: 0
total distance achieved: 116.0
travel h4 8.0 times
travel h5 4.0 times
pay 40.0 X tokens on h4
pay 20.0 X tokens on h5
pay 12.0 Y tokens on h5
pay 12.0 Z tokens on h5

Answer 2

我认为您正在寻找的是单纯形算法，通常用于解决此类运筹学问题：https://en.m.wikipedia.org/wiki/Simplex_algorithm

您可以自己实现这样的算法，但有几个"求解器"库已经实现了这种算法。