线性规划：objective 变量可以有约束吗？

Question

我遇到了 LP 问题。在解释问题之前，我将首先尝试以简化的方式解释问题。

基本问题

假设我有三种类型的机器，它们都只能运行两个时间段（T1、T2、T3 或 T4），如下表所示。

Machine T1    T2    T3   T4    Amount 
M1      0     1     1    0     x1     
M2      1     1     0    0     x2     
M3      0     0     1    1     x3

每台机器可以生产任意数量的物品（x1 到 x3；变量）。这是实现每个时间段所需的 MIMINUM 生产所需的：

            T1  T2  T3  T4
Required    2   3   1   1

要解决这个问题，我们需要：

M2 产生 2，
M3 产生 1，
要么M1要么M2产生1，结果分别在T3或T1产生一个太多。

这可能导致：

Machine T1    T2    T3   T4    Amount 
M1      0     0     0    0     0     
M2      3     3     0    0     3     
M3      0     0     1    1     1      

prod    3     3     1    1
Requ    2     3     1    1

约束

在T1和T4期间生产是不可取的，应该受到惩罚。在上面的示例中，这意味着应该使用 M1 来生成。

用简单的措辞来说，问题是至少生产所需的数量，但尽量减少任何多余的部分（尤其是在 T1 和 T4 中）。

这可以通过两种方式完成：

在这些期间运行的机器受到惩罚（M 的惩罚；M2 和 M3）。
每个时间段的产量受到惩罚（Punished by T; T1 and T4）

这将如下所示：

Machine T1    T2    T3   T4    Amount   Pm
M1      0     1     1    0     x1       0
M2      1     1     0    0     x2       0.5
M3      0     0     1    1     x3       0.5

Pt      0.5   0     0    0.5

问题: 我只能得到每台机器正常工作的惩罚。按时间惩罚并非不可行，但会给出不正确的输出（冗余机器太多）。

尝试与结果

我首先用 m (Pm) 的惩罚对求解器进行了编程。这里的 objective 函数（在 Python pulp 中）是：

amount = LpVariable.dicts("amount_",Machine,0,100000,LpInteger)
product_t = LpVariable.dicts("product_",time,0,100000,LpInteger)


prob += lpSum([amount[m]*(1+Pm[m]) for m in Machine]) # minimize

# constraint
for t in time:
    # production per time period; matrix[m,t] is the matrix with ones shown above
    product_t[t] = lpSum([amount[m] * matrix[m,t] for m in machine])
    # production must be higher than required. 
    prob += product_t[t] >= req[t]

这种情况下的结果是（机器，生产，惩罚）： M1 * 1 * (0+1) + M2 * 2 * (0.5+1) + M3 * 1 * (0.5+1) = 5.5 与次优解相比：M1 * 0 * (0+1) + M2 * 3 * (0.5+1) + M3 * 1 * (0.5+1) = 6

下面，因为这种方法在实际情况中有一些缺点，所以我想用t（Pt）的惩罚来计算它。

prob += lpSum([product_t[t]*(1+Pt[t]) for t in time]) #minimize

for t in time:  # same calculation of product_t and constraint as above
    product_t[t] = lpSum([amount[m] * matrix[m,t] for m in machine])
    prob += inzet_t[t] >= nodig[t]

然而，这种方法给了我一个可行但不正确的输出（production = 0.0）。

问题

怎么可能，完全一样的约束条件，时间的惩罚不起作用？难道objective函数中不允许包含变量(product_t) 有约束？

Answer 1

我开始越来越多地剖析代码，发现了以下内容： amount 和 product_t 的定义方式相同。然而，说 amount[m].varValue 是可能的，但说 product_t[t].varValue 是不可能的（LpAffineExpression 没有名为 varValue 的属性）。相反，我不得不说 value(product_t[t])。我认为这是因为 amount 用于计算 product_t，因此 product_t 是一种不同的变量。所以我知道我必须看看 objective 公式

中 product_t 的用法

尝试 1： 失败，但这是一次远射

prob +=  lpSum([value(product_t[t])*Pt[t] for t in time  ]) #added value() 
# Error: Unsupported operant * for NoneType and float`

尝试 2: 成功。

在目标函数prob += lpSum([product_t[t]*(1+Pt[t]) for t in time]) #minimize中我用公式替换了product_t来计算它。所以，objective 函数是：

prob += lpSum([product_t[t]*(1+Pt[t]) for t in time]) #OLD

成为

prob += lpSum([lpSum([amount[i] * timeblock_matrix[i,t] for i in dienst])*Pt[t] for t in time]) #NEW, minimize

如果有人能解释它为什么这样工作，为什么它不能有中间 LpVariable，将不胜感激。

Answer 2

据我了解，你的问题是

套数：

M = {m1, m2, m3} 台机器
T = {t1, t2, t3, t4} 个时间段

决策变量：

p[m,t] 二进制：机器 m 是否在时间段 t 运行？

约束：

最低产量：在您的问题中名为 required
- sum_m(t1)=2
- sum_m(t2)=3
- sum_m(t3)=1
- sum_m(t4)=1
最长运行时间
- sum_t(m1)=2
- sum_t(m2)=2
- sum_t(m3)=2

objective

min C sum_m(t1)+sum_m(t2)+sum_m(t3)+C sum_m(t4)，其中 C>1 是在第一个或最后一个时间段操作的惩罚。

我认为如果您同意这会解决您的问题，那么应该可以将此模型转换为代码。

线性规划：objective 变量可以有约束吗？

Linear programming: Can objective variable have a constraint?

python

linear-programming

pulp

问题