下载掌阅APP，畅读海量书库
立即打开
定义1.2.1 不确定线性优化问题是集合
在给定的不确定性集
U
⊂ℝ
（
m
+1）×（
n
+1）
中，数据变化时的共同结构（即具有共同数量的
m
个约束和
n
个变量）的LO问题（实例）为
。
我们总假设不确定性集是通过扰动向量 ζ 在给定的扰动集 Z 中以仿射形式参数化的：
例如，1.1.2节的例子中使（Drug）成为一个不确定的LO问题，如下：
●决策向量： x =[RawⅠ；RawⅡ；DrugⅠ；DrugⅡ]；
●标准数据：
●两种基本转化：
●扰动集：
Z ={ ζ ∈ℝ 2 ：-1≤ ζ 1 ， ζ 2 ≤1}
该描述特别指出，（Drug）中唯一不确定的数据是平衡不等式中变量RawⅠ和RawⅡ的系数anⅠ和anⅡ（这是（Drug）中的第一个约束），并且这些系数在各自的段[0.01·（1-0.005），0.01·（1+0.005）]和[0.02·（1-0.02），0.02·（1+0.02）]中变化，系数的标准值是0.01和0.02，这正是1.1.2节所述的。
评注1.2.2
如果式（1.2.1）中的扰动集
Z
本身表示另一个集合
在仿射映射
下的像，那么我们可以将扰动
ζ
传递到扰动
ξ
：
由此可见，当讨论具有简单几何（超平行体、椭球等）的扰动集时，我们可以将这些集规范化为“标准”。例如，根据定义，平行体是单位盒{
ξ
∈ℝ
k
：-1≤
ξj
≤1，
j
=1，…，
k
}的仿射像，这使我们有可能使用单位盒，而不是一般的平行体。类似地，根据定义，椭球是单位欧几里得球
在仿射映射下的像，因此，我们可以使用标准球，而不是椭球等。我们将尽可能使用这种规范化。
注意，与单个优化问题相比，像（LO U ）这样的优化问题本身并不与可行/最优解和最优值的概念相关联。如何定义这些概念当然取决于潜在的“决策环境”。这里我们关注的环境具有以下特点：
A.1.（LO U ）中的所有决策变量都代表“此时此地”的决策；在实际数据显示之前，所有的决策都应作为解决问题的结果而获得特定的数值。
A.2．当且仅当实际数据在式（1.2.1）给出的预先指定的不确定性集 U 的范围内时，决策者对所做出决策的后果完全负责。
A.3.（LO U ）中的约束是“严格的”——当数据在 U 内时，我们不能容忍约束违背，即使是小的约束。
上述假设以或多或少独特的方式确定了不确定问题（LO U ）有意义的可行解。根据A.1，这些应该是固定的向量；根据A.2和A.3，它们应该是鲁棒可行的，也就是说，无论不确定性集的数据实现如何，它们应该满足所有的约束情况。因此我们可得出以下定义。
定义1.2.3 向量 x ∈ℝ n 是（LO U ）的鲁棒可行解，如果它满足不确定性集的所有约束，即
对于与有意义的（即鲁棒可行）解相关联的目标函数值，假设A.1～A.3不以独特的方式来规定它。然而，这些可能导致最坏情况的假设“本质上”自然会导致以下定义。
定义1.2.4
给定一个候选解
x
，在
x
处（LO
U
）中目标函数的鲁棒值
是“真实”目标函数
c
T
x
+
d
在以下不确定性集所有数据中的最大值：
在就不确定问题（LO U ）的有意义的候选解以及如何评估它们的质量达成共识之后，我们可以在问题的所有鲁棒可行解中寻找目标函数的最优鲁棒值。这就是本书的中心概念，即不确定优化问题的鲁棒对等，其定义如下。
定义1.2.5 不确定LO问题（LO U ）的鲁棒对等是在不确定问题的所有鲁棒可行解中，最小化目标函数的鲁棒值的优化问题：
鲁棒对等的最优解称为（LO U ）的鲁棒最优解，而鲁棒对等的最优值称为（LO U ）的鲁棒最优值。
简而言之，鲁棒最优解是我们可以与不确定问题关联起来的“最优不确定性免疫”解。
例1.1.1续 让我们找到解决不确定问题（Drug）的鲁棒最优解。数据中正好有一个受不确定性影响的“块”，即平衡约束中的RawⅠ系数、RawⅡ系数。因此，如果候选解满足（Drug）除了平衡约束的所有约束和平衡约束的“最差”实现，那么候选解是鲁棒可行的。由于RawⅠ、RawⅡ是非负的，平衡约束的最差实现条件是不确定系数anⅠ、anⅡ设置为不确定性集中的最小值（这些值分别为0.00995和0.0196）。由于目标函数不受不确定性的影响，鲁棒目标函数值与原始目标函数值相同。因此，我们的不确定问题的RC（鲁棒对等）是LO问题：
解决此问题，我们得到：
RobOpt=-8294.567；RawⅠ=877.732，RawⅡ=0，DrugⅠ=17.467，DrugⅡ=0
鲁棒性的“代价”是将期望利润从标准最优值8819.658减少到鲁棒最优值8294.567，即减少了5.954%。这远低于实际利润减少21%（值为6929），当“真实”数据“反对”它时，我们在坚持标准最优解时可能会遭受这种损失。还要注意的是，鲁棒最优解的结构与标准最优解有很大的不同：对于鲁棒解，我们将只购买原材料RawⅠ，而对于标准最优解，我们将只购买原材料RawⅡ。以下解释很清楚：根据标准数据，RawⅡ比RawⅠ的活性剂的单位价格略低（9995$/g与10000$/g）。这就是为什么对标准数据使用RawⅠ没有意义。鲁棒最优解考虑到anⅠ的不确定性（即RawⅠ中活性剂含量的可变性）为anⅡ的1/4（0.5%与2%），最终使用RawⅠ。
我们从几个有用的观察开始。
A .LO U 的鲁棒对等（1.2.4）同样可以改写为问题：
请注意，我们可以以另一种方式得出此问题：首先引入额外的变量 t ，并将不确定问题（LO U ）的重写实例等价为
因此，在变量 x ， t 中得出等价于（LO U ）的不确定问题，目标函数 t 完全不受不确定性的影响。重新表述的问题的RC正好是式（1.2.5）。我们看到了：一个不确定的LO问题总是可以重新表述为具有特定目标函数的不确定LO问题。重构问题的鲁棒对等与此问题具有相同的目标函数，等价于原始不确定问题的RC。
因此，当我们用不确定的LO程序和特定的目标函数作为约束时，是没有任何损失的，我们以后将经常使用此选择。
我们现在明白为什么不应忽视目标函数（1.1.1）的常数项
d
，或者更确切地说，如果不确定它的值，则不应忽视。若
d
是确定的，我们可以通过在松弛变量
t
中的变化
来解释它，它只影响最优值，而不影响鲁棒对等（1.2.5）的最优解。当
d
不确定时，没有一种“通用”的方法在不影响鲁棒对等最优解（其中
d
在原始约束的右侧发挥相同的作用）的情况下消除
d
。
B .假设（LO U ）具有特定的目标函数，则问题的鲁棒对等是
（请注意，不确定性集现在是约束数据[ A ， b ]空间中的一组集合）。
我们看到具有特定目标函数的不确定LO问题的鲁棒对等具有纯粹的“约束性”结构：为了获得RC，我们采取以下步骤：
●保留原有的特定目标函数
●替换所有原始约束条件
（
是
A
的第
i
行），其鲁棒对等为
其中， U i 是 U 在第 i 个约束的数据空间下的投影：
特别地，当不确定性集 U 扩展为直积
即其在各自约束的数据空间下的投影的直积时，具有确定目标函数的不确定LO问题的RC保持不变。
例1.2.6 在变量 x 1 ， x 2 处，不确定约束组
的RC是无限约束组
后者显然等同于以下这组约束
两个不确定约束（1.2.7）的数据空间的
U
的投影是分段
U
1
={
ζ
1
：0≤
ζ
1≤1}，
U
2
={
ζ
2
：0≤
ζ
2≤1}，式（1.2.7）关于不确定性集
的RC显然是式（1.2.8）。
我们得出的结论似乎是反常理的：不同约束条件下的数据扰动是否相互关联无关紧要，而按照常理，这种关联应该是重要的。我们将在后面（第14章）看到，当考虑更高级的可调鲁棒对等的概念时，这种直觉是有效的。
C
.如果
x
是（
C
i
）的鲁棒可行解，那么我们将不确定性集
U
i
扩展到其凸包Conv（
U
i
）时
x
仍是鲁棒可行解。的确，如果
，则
其中适当的选择
，比如
。我们现在有
其中不等式由以下事实给出：对于RC（
C
i
）和
来说，
x
是可行的。我们看到，对于所有
，证明完毕。
基于类似的原因，我们扩展 U i 到其闭包时，（ C i ）的鲁棒可行解保持不变。将这些观察和观察B相结合时，我们得出以下结论：当我们将相关约束的不确定数据集 U i 扩展到其封闭凸包，并扩展 U 到结果集的直积时，具有特定目标函数的不确定LO问题的鲁棒对等保持不变。换句话说，我们从一开始就假设约束不确定数据集 U i 是封闭和凸的，而 U 是这些集的直积，因此我们不会损失任何东西。
就不确定性集的参数化（1.2.1）而言，后一个结论意味着：当谈到具有特定目标函数的不确定LO问题的鲁棒对等时，假设第 i 个约束的不确定数据集 U i 为
其中有封闭的和凸扰动集 Z i 。
D . 一个重要的建模问题 。在通常（具有特定数据）的线性优化中，约束可以用各种等价形式建模。例如，我们可以写出：
或者，等价地
或者，等价地，通过添加一个松弛变量 s ，
但是，当（部分）数据 a 1 ，…， a 6 变得不确定时，并非所有这些等价都有效：目前受不确定性影响的约束组的RC并不是等价的。实际上，用 U 表示不确定性集，RC分别为：
可以立刻看到，虽然第一个和第二个RC彼此等价
，但是它们与第三个RC不等价。后一个RC比前两个RC更加保守，这意味着无论何时（
x
1
，
x
2
）可以通过适当选择
s
扩展到式（1.2.15）的可行解，（
x
1
，
x
2
）对于式（1.2.13）≡式（1.2.14）是可行的（这是明显的），但是反过来不一定。实际上，式（1.2.15）和式（1.2.13）≡式（1.2.14）之间的差距相当大。为了说明后一种说法，考虑不确定性集的情况：
U ={ a = a ζ =[1+ ζ ； 2+ ζ ； 4 -ζ ； 4+ ζ ； 5 -ζ ； 9]： -ρ ≤ ζ ≤ ρ }
其中 ζ 是数据扰动。在这种情况下， x 1 =1， x 2 =1是式（1.2.13）≡式（1.2.14）的一个可行解，条件是不确定性 ρ ≤1/3：
（4+ ζ ）· 1+（5 -ζ ）· 1=9，∀ ζ
同时，当 ρ ＞0时，我们的解（ x 1 =1， x 2 =1）不能推广到式（1.2.15）的一个可行解，因为后一个约束系统是不可行的，即使消除等式（1.2.15. b ）后仍然是不可行的。
的确，对于所有的 a ∈ U ，为了使 x 1 ， x 2 满足式（1.2.15. a ），应该有
当 ρ ＞0时，应该得到 x 1 + x 2 =-1，与式（1.2.15. c ）矛盾。
上述现象的根源是很清楚的。显然，不等式 a 1 x 1 + a 2 x 2 ≤ a 3 ，其中所有 a i 和 x i 是固定实数，当且仅当我们可以通指出一个实数 s ≥0来“证明”不等式，使 a 1 x 1 + a 2 x 2 + s = a 3 。当数据 a 1 ， a 2 ， a 3 变得不确定时，对于所有 a ∈ U 的不确定等式 a 1 x 1 + a 2 x 2 ≤ a 3 ，（ x 1 ， x 2 ）的约束变得鲁棒可行，“在证明方面”，依照
∀ a ∈ U ，∃ s ＞0： a 1 x 1 + a 2 x 2 + s = a 3
也就是说，应该证明 s 依赖于真实数据。与此相反，在式（1.2.15）中，我们要求决策变量 x 和松弛变量（“证明”） s 都独立于真实数据，这是非常保守的。
从上面的例子中可以学到的是，当建模一个不确定的LO问题时，应该尽可能避免将不等式约束转换为等式，除非问题约束中的所有数据都是确定的。除了避免松弛变量
，这意味着像“总支出不能超过预算”或者“供给应该至少是需求”这样的约束，在具有特定数据的LO问题中，可以利用等式来建模，在数据不确定的情况下，则应该用不等式来建模。这完全符合常识，例如，若需求是不确定的，则满足需求是必然的，禁止供应过剩是不明智的。有时候，RO方法建模需要通过相应的“状态方程”消除“状态变量”——这些变量很容易由代表实际决策的变量给出。例如，在最简单的情况下，用状态方程给出了库存的时间动态：
x 0 = c
x t +1 = x t + q t -d t ， t =0，1，…， T
其中， x t 是在时间 t 的库存水平， d t 为[ t ， t +1）时期的（不确定）需求，变量 q t 表示实际决策——在 t =0，1，…， T 时按照指令补充。对于此类库存问题进行RO处理的明智方法是通过设置
来消除状态变量
x
t
以及消除状态方程。因此，典型的约束状态变量（例如“
x
t
应该保持在给定的范围内”或“总持有成本不超过一个给定的值”）将成为实际决策
q
t
的不确定影响的不等式约束，通过其RC，我们可以处理由此产生的不等式约束的不确定LO问题
。
在引入不确定LO问题的鲁棒对等概念之后，我们面临两个主要问题：
●RC的“计算状态”是什么？什么时候才能有效地处理RC？
●如何产生有意义的不确定性集？
第一个问题是一个“结构”问题，将在1.3节中深入讨论：为了使RC在计算上易于处理，不确定性集的结构应该是什么？注意到，由式（1.2.5）和式（1.2.6）给出的是半无限LO规划，即一个优化规划具有简单的线性目标函数和无限多线性约束。原则上，这样的问题可能是“计算上难以处理的”——NP难问题。
例1.2.7 考虑一个不确定“本质是线性”的约束
其中，
，并假设矩阵
P
是确定的，而向量
p
是不确定的，并由单位盒的扰动参数化：
其中，
，
B
是一个给定的半正定矩阵。检验
x
=
0
是否鲁棒可行与当
时验证
与否相同，或者，由于明显关系
，与检验
与否相同。当
η
=
ζ
时（也许利用极化恒等式
来检查），双线性型
η
T
Bζ
的最大值总是在原点的凸对称邻域中取得，该双线性形式具有在
η
，
ζ
上的半正定矩阵
B
。因此，对于式（1.2.16）检查
x
=
0
是否鲁棒可行与检查给定的非负二次型
ζ
T
Bζ
在单位盒上的最大值是否≤1相同。后一个问题是熟知的NP难问题
[1]
，因此，式（1.2.16）的鲁棒可行性检验问题也是如此。
上述第二个问题是一个建模问题，因而超出了纯理论考虑的范围。然而，正如我们将在2.1节中看到的，理论对这个建模问题有重要贡献。
[1] 事实上，计算单位盒上的非负二次型的最大值是NP难问题，误差小于4% [61] 。