如何使用PuLP配置时态/时间线性规划约束？

Question

我试图用PuLP来解决一个假设的线性问题。这个问题的目的是在5年的时间内最小化一个操作的成本，同时最大化产品的形状和条件。这个问题必须产生5个成本，每年一次，同时优化整个系统和每年的运作。

total_cost = [(var_cost[year] + fix_cost[year] + cost_new_sensors[year]) for year in range(0,5)]

total_cost需要维护三种类型的传感器：

                   # units    price_new fixed_cost_per_unit_per_yr   variable_costs_pr_yr_pr_unit
sensor_type_a      300        $50       rent + insurance             power + maint
sensor_type_b      900        $75       rent + insurance             power + maint
sensor_type_c      1500       $90       maint + insurance            -     

• 这个问题必须考虑到，对于每一年，传感器处于比前一年更好的状态，并且不可能有超过12%的传感器条件为"Very poor"。
• 如果曝光不高，系统应该能够替换另一种传感器类型，或者降低新传感器购买的级别。(这句话与这篇文章无关)

用于sensor_type_a**:**的

• 固定费用：
  • 1至5年单位的租金为[50, 55, 55, 55, 60]
  • 1至5年的单位保险是[ 1.0, 1.2, 1.2, 1.8, 2.0]。

​

• 可变成本：
  • 功率是基于传感器测量的项目数：10+.05*each_measurement。价格每年上涨1%
  • 维护是基于$500 for the total number of sensors + each_measurement*2.45的。价格每年上涨2%

​

• 曝光指数表示每个传感器的状态，并基于下表：

_

exposure(# of measurements)    category
<=100                          excellent
250                            good
400                            poor
>=400                          very poor

用于sensor_type_b**:**的

• 固定费用：
  • 1至5年单位的租金为[60, 65, 65, 70, 75]
  • 1至5年的单位保险是[ 1.1, 1.3, 1.4, 1.7, 2.0]。

​

• 可变成本：
  • 功率是基于传感器测量的项目数：10+.08*each_measurement。价格每年上涨1%
  • 维护是基于$500 for the total number of sensors + each_measurement*2.65的。价格上涨了1.5%

​

• 曝光指数表示每个传感器的状态，并基于下表：

_

exposure(# of measurements)    category
<=200                          excellent
350                            good
500                            poor
>=500                          very poor 

用于sensor_type_c**:**的

• 固定费用：
  • 1至5年内所有单位的维修均为[5000, 5100, 5200, 5300, 5400]。
  • 1至5年的单位保险是[ 1.1, 1.3, 1.4, 1.7, 2.0]。

​

• 曝光指数表示每个传感器的状态，并基于下表：

_

exposure(# of measurements)    category
<=300                          excellent
450                            good
600                            poor
>=600                          very poor

我的目标函数/方程是极小化的：

problem = pulp.LpProblem(’Cost Minimization’, pulp.LpMinimize)

My约束：

我在设置约束函数时遇到了麻烦。以下是我在概念上想要做的事情(伪和python的混合)：

problem += sum([fixed_costs[yr][a] + var_costs[yr][a]
                               for a in sensor_type_a
                               for yr in years])

problem += sum([fixed_costs[yr][b] + var_costs[yr][b]
                               for a in sensor_type_b
                               for yr in years])

problem += sum([fixed_costs[yr][c] + var_costs[yr][c]
                               for a in sensor_type_c
                               for yr in years])

problem += sum(sensor_type_[a].condition('very poor') + \
               sensor_type_[b].condition('very poor') + \
               sensor_type_[c].condition('very poor')) <= 12%

problem += sum(sensor_type_[a].average_condition(yr) + \
               sensor_type_[b].average_condition(yr) + \
               sensor_type_[c].average_condition(yr) >=
               sensor_type_[a].average_condition(yr-1) + \
               sensor_type_[b].average_condition(yr-1) + \
               sensor_type_[c].average_condition(yr-1)

问题：

如果我的pseudo+python没有走上正确的轨道，我如何才能正确地设置约束以解决问题？

请注意，我为每个变量填写了一个表，其中包含适当的类别和数据点。

编辑反思以下评论：

总共有2 700个单位或地点有待测量。我有一张具有以下性质的表格：

   unit_ID  actual_2013   forecasted_2014   forecasted_2015   forecasted_2016   forecasted_2017
         1           25                30                40                35    50
         2          400               430               460               480    50
         n          x_1               x_2               x_3               x_4    x_5

该模型不能改变今年的传感器类型组成，但是，它应该能够为未来几年充分建模。这意味着包括更换成本等，以获得更好的传感器和降低整体成本。

单位是可互换的。

Answer 1

我就是这样处理这个的。

一般要点

首先，您希望将模型公式与PuLP中的代码实现或其他方面分开。

如果您得到正确的公式，它将变得更容易实现。(你正确地提到，你的问题中存在一些棘手的制约因素。)

在我们讨论这一表述之前，最后一个建议是:你有一套相当复杂和详细的成本和制约因素。我建议让基本公式和LP解决方案工作，然后分层限制和详细的成本(租金，维护等)。否则，您将花费大量时间调试和验证您的模型。

IP配方

决策变量与输入常数

我们有三种传感器s = {a, b, c}。我们的时间范围为5年= t = {1..5}我们大约有2700个地点l = {1..2700}

主要决策变量-决定哪种感觉类型在哪个位置

Let `X_lst` be 1 if the unit at location l gets assigned a sensor of type `s` in year `t`
           0 otherwise

 Let `N_st` be the total number of sensors of type s used in year t

X和N是决策变量。

我们还得到了许多“常量”(这些是您的输入表)。

Let E_lt be the total number of exposures in location l in year t. 

(请注意，E_lt是在问题之外给定或预测的。IP输出并不决定这一点。

需要最后一组决策变量：

设Y_lst_ctype为1，如果在时间周期t结束时，位置l中的传感器类型s最终是状态ctype，则根据该年所感知到的曝光量。

ctype可以是{优秀、好、穷、VeryPoor}的类型之一。

通过我们的表示法，Y_2b2_poor表示b型传感器连接到单元2上的决策变量，在第二年结束时，它将以poor状态结束。

约束条件

现在，让我们开始对您提到的众多约束进行建模：

覆盖约束每个位置必须在每年都有一个传感器。(求和超过s) X_lst =1，对于每个t，对于每个位置l。

全数约束对每种传感器类型，在每年，我们有一个方程的总数目。

N_st = X_1st + X_2st + ... + X_2700st for each sensor type s, and for each time period t

(这些约束有时被称为“定义”约束。它们确保N和X是内部一致的。)

起动条件

N_a1 <= 300
N_b1 <= 900
N_c1 <= 1500

传感器条件相关约束

这些都有点棘手，这就是为什么我们必须引入这么多0/1类型的Y变量。

每个传感器只能在一个条件下结束。

Y_lst_excellent + Y_lst_good + Y_lst_poor + Y_lst_verypoor = 1

现在，我们有一组线性约束，根据曝光的数量来确定传感器的状况。

技巧，我们必须使用大-M方法，以确保模型为它指定了正确的条件。

对于传感器类型a

E_lt x X_lat <= 100 + M (1- Y_lat_good)

E_lt x X_lat <= 250 + M (1- Y_lat_poor)

E_lt x X_lat <= 400 + M (1- Y_lat_verypoor)

如果你研究这一点，你会发现，取决于所经历的曝光次数，正确的条件会被分配，同时保持所有的线性。(M是一些大数字)

对b和c类型的传感器也这样做。

限制百分比到非常差的

Y_1st + Y_2st + Y_3st + ... + Y_2700st <= 0.12 x Nst (for each sensor type s, year t)

目标函数

你已经列出了，所以我只提一下目标函数的轮廓。

Min sum_all_cots x X_lst，该总和将包含与租金、维护和更换有关的组件。

Final Note是超级精确的，您还需要一个决策变量来决定是保留还是替换每个位置的新传感器。

R_lst = 1 if location l gets a NEW sensor of type s at the end of year t

根据“替换与零售”的成本权衡，你会增加更多的约束。但是模型本身很复杂，所以我没有写出这些约束。

您必须将其转换为Python模型并写出公式，以确定其是否有意义。在一个琐碎的问题上尝试一下，然后继续添加更多的约束和变量。

希望这能帮你继续前进。