电力市场中凸壳价格的计算

值得注意的是，fi（^x[ni]i，^y[ni]i）和^x[ni]i是皮重参数，因此，目标函数和约束在z[ni]i中都是线性的。约束（6c）要求选择一个由二元变量z[ni]i表示的精确可行计划。因为UC问题（1）的最优解，比如（^x）*i、 ^y*（一）∈ Zi本身就是候选可行解之一——用z表示*i、 然后z*IOP临时解决问题（6），且（6a）的最佳目标函数值将等于（1a）的相应值。等价地，问题（6）可以被视为一个集合划分问题。乍一看，暴力解决（6）的努力似乎毫无希望，因为它不仅需要识别所有可行的计划，而且还需要解决一个巨大的整数问题—（6）是一个整数线性规划问题。我们澄清，我们不需要假设时间表的数量是有限的。证明可行集是有界的[36]。也就是说，我们自然地将（6）与D-W分解和CG联系起来——例如，参见[38]。然而，用CG解决一个大的UC问题似乎还没有希望——例如，见最近的研究[46]。幸运的是，我们提醒读者，我们的目标不是解决这个整数问题，而是LD（2）。考虑到这一点，我们回顾了一个可以追溯到70年代[35]的结果，即（6）的LP松弛解LD（2）；在[36]中也明确指出，广义LP——也称为DW分解——解决了对偶问题。换句话说，问题（6）的Lp松弛是UC问题的D-W表征——等价地表示为（1）或（6）——并解决UC问题的LD，其定价（双重化）系统约束。

事实上，我们知道D-W分解器CG本质上是一种应用于LD的割平面方法[47]，我们发现它对我们的问题设置特别有指导意义，希望能增强对CH价格形成的直觉。为了清楚起见，让我们提供下面问题（6）的LP松弛。minzg（z）=Xi∈一、 倪∈Nifi（^x[ni]i，^y[ni]i）z[ni]i，（7a）受制于：Xi∈一、 倪∈Ni^x[Ni]i，tz[Ni]i=Dt，T∈ T，（7b）Xni∈Niz[ni]i=1，我∈ 一、 （7c）z[ni]I≥ 0, 我∈ 一、 倪∈ 镍。（7d）注意，将上限限制为z[ni]i≤ 1由（7c）执行。在[36]之后，问题（7）等价于LDP问题（2）；（7）的解也解（2）。CH定价的许多方法涉及对目标函数[15]形式的限制，或对UCP问题的重新表述，如动态规划特征[48]，[49]。D-W方法从一个自然公式开始，它不需要改变UC功能或约束。这使得UC问题的解决具有很大的灵活性。这种表示法允许我们描述完整的CH[50]。本质上，相同的公式适用于增量调度问题[38]。如果我们必须处理所有可行点的完整列表，计算问题将是压倒性的。

但D-W方法提供了一种自然的CG技术，该技术使用子问题来产生实际中相对较少的可行点，并等同于描述CH弛豫的解决方案。直觉是，同样的方法也适用于UC问题，不需要对UC模型进行任何重新表述，但在相关的大型机组调度问题中观察到了计算可行性。LP问题（7）的解，即问题（6）的LP松弛，采用CG算法，进行如下操作。首先，考虑每个单元的可行计划子集，比如N（k）i Ni，其中k是一个迭代计数器，即N（k）i包含在迭代k处可获得的机组i的所有可行计划。使用这些计划，迭代k处的受限主问题（RMP），RMP（k）被公式化如下：RMP（k）：minzg（k）（z）=Xi∈一、 倪∈N（k）i^c[ni]iz[ni]i，（8a）受制于：Xi∈一、 倪∈N（k）i^x[ni]i，tz[ni]i=Dt，T∈ T→ λ（k）t，（8b）Xni∈N（k）iz[ni]i=1，我∈ 我→ π（k）i，（8c）与z[ni]i≥ 0, 我∈ 一、 倪∈ N（k）i和λ（k）t，π（k）i，分别是对偶约束（8b），（8c）。我们澄清了问题（8）被称为“受限”是因为和“主问题”相比，它只包含一个子集的时间表，就像通常被封装的问题（7）一样。（8）中初始RMP的公式假设是可行的。事实上，这可以通过使用UC可行解填充初始RMP来轻松实现，例如，如果（1）的解在当时可用，则使用由该解导出的可行时间表。或者，我们可以在初始RMP中为每个单元填充一个简单可行的时间表，例如，考虑到该单元具有灵活性。

为了确保问题（8）存在可行的解决方案，我们可以在约束中引入松弛变量，并进行适当的惩罚，就像我们在UC MILP公式中使用松弛变量一样。CG在实践中也是标准的。然后，CG“生成”新的列（可行的时间表），并将它们添加到RMP，只要它们具有负的降低成本。可行计划（xi，yi）的降低成本rc（·）由以下公式给出：rc（k）i（xi，yi）=fi（xi，yi）-Xt∈Tλ（k）txi，T- π（k）i.（9）因此，在迭代k时，对于每个单元i，通过求解以下子问题，可以获得具有潜在负成本的可行计划：子（k）i:minxi，yih（k）i（xi，yi）=fi（xi，yi）-Xt∈Tλ（k）txi，T，（10a）受制于：（xi，yi）∈ Zi，（10b）我们去掉了常数项-π（k）If来自Objective函数。如果通过（10）的解得到的进度计划具有负的降低成本，则使用（9）计算——基本上是通过加回该项-π（k）为目标函数值h（k）i，然后将一个新列添加到与此计划对应的RMP中。再次求解RMP，当无法找到成本为负的新可行计划时，算法终止。值得注意的是，RMP中已经存在的进度计划不能有负的降低成本，因此，RMP中不能重复添加任何可行的进度计划。显然，我们并不总是能够在所有单元的每次迭代中找到负的降低成本计划；这就是我们没有使用上标（k）而不是[ni]作为可行时间表的原因。由于混合整数的存在，CG算法的有限收敛性得到了保证。关于初始化和松弛变量的使用，请参阅以下章节中的示例。目标函数fi（·）和约束集Zi的线性表示。

（8）中LP问题的标准对偶表示对偶的值-π（k）i表示机组i的代表性收益，通过RMP中的最优时间表选择计算，从而得出价格λ（k）。给定这些价格λ（k），如果机组可以通过自调度做得更好，那么我们有：φi（xSi，ySi；λ（k））>-π（k）i。因此，在这种情况下，自调度会导致负成本降低——参见（13）。当利润最大化问题（10）等价地（11）产生一个在所有机组的RMP中已经存在的可行计划时，该算法终止，这意味着对于CH价格，总地点最小化，并且达到LD的最优解。因此，在终止时，我们得出确切的CH价格，即确切解决LD问题的价格。我们请感兴趣的读者参考[36]，以获得该方法在更一般的情况下的收敛证明，而不是解决定价问题所需的收敛证明。四、 关于程式化示例的说明本节使用[32]中的程式化示例作为有用的练习，其目的是（i）说明CG算法，以及（ii）通过D-W分解的镜头提供关于CH价格形成的直觉。我们请读者参考[32]，以详细讨论每个示例所示的CH priceproperties。A.示例1：两台发电机，1小时[32，示例1]G1和G2，在一个周期内为35 MW负载供电。G1在线，技术最低和最高分别为10兆瓦和50兆瓦，能源价格为50美元/兆瓦时。G2可以在线或在线，并以10美元/兆瓦时的价格提交50MW的整体报价。MILP配方如下：MILP:minx，x，yf=50x+10x，（14a）受制于：x+x=35，（14b）10≤ 十、≤ 50，（14c）x=50y，y∈ {0, 1}. （14d）本例只有一个可行解，G1提供35 MW，MILP目标函数值f*= $1750

其价格为每兆瓦时10美元，G1的定位码为1000美元。接下来，我们使用CG解决这个例子。考虑简单的初始计划：z[1]：^x[1]=10，^c[1]=500，以及z[1]：^x[1]=0，^c[1]=0。为了避免RMP不可行，我们在RMP能量平衡约束（8b）中引入松弛（deficit）变量s，并在目标函数（8a）中引入惩罚。假设平均值为1000美元/MWh，初始RMP如下：RMP（1）：minz[1]，z[1]，sg（1）=500z[1]+0z[1]+1000s，（15a）根据：10z[1]+0z[1]+s=35，→ λ（1），（15b）z[1]=1，→ π（1），（15c）z[1]=1，→ π（1），（15d）与z[1]，z[1]，s≥ 0.RMP（1）的解产生对偶λ（1）=1000，π（1）=-9500，π（1）=0。对于这些值，Sub（1）：min10≤十、≤50小时（1）=50倍- 1000x=-950x，收益率x=50，h（1）=-47500，rc（1）=h（1）- π(1)=-38000<0，因此z[2]：^x[2]=50，^c[2]=2500，其中sb（1）：minx=50y，y∈{0,1}h（1）=10x- 1000x=-990x，收益率x=50，y=1，h（1）=-49500，rc（1）=h（1）-π(1)= -49500<0，因此z[2]：^x[2]=50，^c[2]=500。TheRMP，在添加这两个新列后变成：RMP（2）：minz，sg（2）=500z[1]+0z[1]+2500z[2]+500z[2]+1000s，受制于：10z[1]+0z[1]+50z[2]+50z[2]+s=35，→ λ（2），z[1]+z[2]=1，→ π（2），z[1]+z[2]=1，→ π（2），带z[1]，z[1]，z[2]，z[2]，s≥ RMP（2）的解现在得到λ（2）=10，π（2）=400，π（2）=0。对于这些值，Sub（2）得到x=10，其中h（2）=400，rc（2）=h（2）-π（2）=0——注意，RMP中已经存在一个x=10的计划——而对于任何可行的计划，Sub（2）产生h（2）=0，rc（2）=h（2）- π(2)= 0. 由于没有找到负成本降低的可行计划，CG终止。CH价格为λ（2）=10美元/兆瓦时。RMP（2）的解是z[1]=1，z[1]=0.5，z[2]=0.5，目标函数的值是g（2）=g*= $因此，MIP和RMP之间的对偶差距是f*- G*= $1750-$750=1000美元，代表支付给G1的LOC（提升）。

请注意，在CH价格下，G1的最大利润将由x=10导出，而不是x=35，这是MILP发货数量。值得注意的是，当算法终止时，这个数量是G1子问题的最优解。另一方面，G2没有LOC，因为CH价格等于其成本。B.示例2：示例1有两个节点[32，示例2]该示例将示例1扩展到两个节点的设置。G1与节点1处的35 MW负荷并置，而G2位于节点2处，两个节点之间的输电线路的容量为10 MW。MILP公式如下（14），添加了变速箱约束：-10≤ 十、≤ 10.最佳解决方案保持不变（G1提供35 MW），输电线路沿线没有水流。然而，[32，Ex.2]显示，节点1的CH价格为50美元/MWh，节点2的CH价格为10美元/MWh，拥塞价格为40美元/MWh。考虑到上一个示例的初始计划，在不失去普遍性的情况下，只保留本示例中可能出现的一个方向，即x≤ 10，初始RMP遵循（15）添加传输约束：0z[1]≤ 10, -→ u(1).事实上，我们还应该包括一个松弛变量，类似于（15b），在目标函数中有一个适当的违反约束的代价，但为了简洁起见，我们省略了这个。由于传输约束在RMP（1）中未激活，因此会生成相同的列并将其添加到RMP（2）中，RMP（2）现在包括传输约束：0z[1]+50z[2]≤ 10, -→ u(2).RMP（2）对偶为λ（2）=50，u（2）=-40，π（2）=0，π（2）=0。G1子问题与前一个例子相同，rc（2）=0，而G2子问题的目标函数（现在包括传输约束Dual）由h（2）=10x给出- λ（2）x- u（2）x=10x-50x+40x=0。因此，rc（2）=h（2）- π（2）=0，且cG终止于前述CH价格。

Rmp（2）的解为z[1]=0.625，z[2]=0.375，z[1]=0.8，z[2]=0.2，目标函数的值为g（2）=g*= $1350.因此，二元性缺口为400美元，代表由于10 MW输电线路沿线的阻塞价格而产生的PRS。C.示例3：示例1的启动成本[32，Ex.3]该示例将100美元的启动成本添加到示例1中，即f（x，y）=10x+100y，产生等于12美元/MWh的CH价格，对应于G2的平均成本。然而，唯一可行的解决方案是在35MW时调度G1，MILP目标函数值为f*= $1750.假设初始计划相同，因此RMP（1）对偶相同，我们得到z[2]：^x[2]=50，^c[2]=2500，以及z[2]：^x[2]=50，^c[2]=600。RMP（2）产生对偶λ（2）=12、π（2）=380和π（2）=0，对于这些对偶，找不到负的降低成本计划。RMP（2）（z变量）的解与例1相同，但目标函数的值现在为g（2）=g*= $800.因此，二元差距为950美元，也就是G1 LOC。D.示例4：2发电机，2小时（连接）[32，示例4]该示例考虑了2小时，负载为45和80 MW。G1保持不变，两个小时内都应该在线。G2的最低功率为25兆瓦，最高功率为35兆瓦，每兆瓦时的能量消耗为100美元，并且应在两个小时内在线或在线。

MILP问题的公式如下：MILP:minx，yf=50x1,1+50x1,2+100x2,1+100x2,2，（16a）受制于：x1,1+x2,1=45，x1,2+x2,2=80，（16b）10≤ x1,1≤ 50, 10 ≤ x1,2≤ 50，（16c）25y≤ x2,1≤ 35岁，25岁≤ x2,2≤ （35D）16Y∈ {0,1}，（16e）产生x1,1=20，x1,2=50，x2,1=25，x2,2=30，y=1，MILP目标函数值为f*= $9000.跳过第一个CG步骤，最后一个RMP如下：RMP（3）：minz，sg（3）=1000z[1]+0z[1]+5000z[2]+7000z[2]+3000z[3]+6000z[3]+1000s+1000s，受制于：10z[1]+0z[1]+50z[2]+35z[2]+10z[3]+25z[3]+s=45，→ λ（3），10z[1]+0z[1]+50z[2]+35z[2]+50z[3]+25z[3]+s=80，→ λ（3），z[1]+z[2]+z[3]=1，→ π（3），z[1]+z[2]+z[3]=1，→ π（3），带z[1]，z[1]，z[2]，z[2]，z[3]，z[3]，s，s≥ 0.RMP（3）屈服阶λ（3）=50，λ（3）=135.714，π（3）=4285.714，π（3）=0，CG终止。RMP（3）的解为z[2]=0.339，z[3]=0.661，z[1]=0.143，z[3]=0.857，目标函数的值为g（3）=g*= $8821.429.因此，二元差距为178.571美元，代表G2 LOC。E.示例5：示例4，非链接小时[32，Ex.5]该示例考虑了之前的设置，但将其视为两个单周期问题。同样地，我们可以使用（16）并将（16d）–（16e）替换为：25y2,1来编写milp公式≤ x2,1≤ 35y2,1,25y2,2≤ x2,2≤ 35y2,2和y2,1,2∈ {0, 1}. CG以RMP（3）终止，产生对偶λ（3）=50和λ（3）=100，π（3）=-2500，π（3）=0，目标函数g（3）=g的A值*= $7750.因此，二元性差距为1250美元，代表G2 LOC。我们把这个例子留给感兴趣的读者作为练习。V.讨论和更现实的测试用例在本节中，我们将讨论所提出方法的比较优势，并继续进行更现实的测试用例。在V-A小节中，我们介绍了与其他方法的比较分析。我们用两个有代表性的例子来支持我们的分析。

在第V-B小节中，我们回顾了[29]中提供的一个示例，包括坡道约束，以强调适应功能的便利性，长期以来，这些功能一直被认为是“有问题的”在V-C小节中，我们在一个ISO大小的FERC数据集[41]上测试了24小时的UC公式，其中包含大约1000个生成器，以说明可扩展性。A.D-W特征的比较分析与计算CH价格的两种主要方法（即次梯度法和扩展公式）相比，所提出的方法具有若干优势。第一种方法指的是解决拉格朗日对偶问题的初始尝试（例如[20]、[22]），是基于次梯度方法的，无可否认没有太大成功。可以说，由于众所周知的收敛困难，次梯度方法不太适合CHP定价问题。另一方面，D-W特性结合了许多优点。它保持了小个子问题的复杂性——就像拉格朗日松弛一样——但同时它塑造了CH，并具有收敛性保证。MILP约束可行集（具有多面体）保证有限收敛。第二种方法是指最近的工作（例如，[28]、[29]、[31]），旨在确定每个单元的CH的扩展公式和成本函数的凸斜率，以导出与系统约束相关的LP问题，其中与系统约束相关的参数产生CH价格。早期作品没有捕捉到显著的特征，因此产生了近似的描述。例如，长期以来，rampingconstraints一直被认为是“有问题的”，在这些公式中无法适应。因此，在确定斜坡约束发电机的扩展公式[48]、[49]或应用析取编程[32]以满足更一般的设置方面投入了大量精力。