下载掌阅APP，畅读海量书库
立即打开
回想一下线性优化（LO）问题的形式：
其中 x ∈ℝ n 是决策变量的向量， c ∈ℝ n 和 d ∈ℝ形成目标函数， A 是 m × n 的约束矩阵， b ∈ℝ m 是不等式右侧向量。
显然，目标函数中的常数项 d 虽然影响最优值，但不影响最优解，这就是一般跳过它的原因。我们看到，在处理具有不确定数据的LO问题时，有充足理由不去忽略这个常数项。
问题（1.1.1）的结构由约束数量 m 和变量数量 n 给出，问题的数据是集合 （ c ， d ， A ， b ） ，我们将其排列成一个（ m +1）×（ n +1）的数据矩阵
通常，在应用程序中出现的LO程序的约束并不都以“ a T x ≤常数”的形式出现：可以有线性“≥”不等式和线性等式。显然，后两种类型的约束可以等价地用线性“≤”不等式表示，并且今后我们将假设这是问题中唯一的约束。
通常，实际线性优化问题的数据是不确定的。数据不确定最常见的原因如下：
●当问题被解决时，某些数据项（未来需求、回报等）并不存在，从而被它们的预测值所取代。因此，这些数据项会受到预测错误的约束。
●一些数据（技术设备/过程的参数、与原材料相关的内容等）无法精确测量——实际上，它们的值会在测量的“标准”值附近浮动，这些数据会受测量错误影响。
●一些决策变量（我们打算使用各种技术过程的强度、所设计的物理设备的参数等）无法完全按照计算实现。由此产生的实现错误相当于适当的人为数据不确定性。事实上，一个特定的决策变量
x
j
使约束
i
的左侧为
a
ij
x
j
。因此，附加实现错误
的结果好像根本没有实现错误，但约束的左侧得到了一个额外的附加项
，反过来，它又相当于扰动
约束的右侧。一个更典型的乘法实现错误是
，它似乎没有造成实现错误，但每个数据系数
a
ij
都会受到干扰
的影响。同样，
x
j
中的附加和乘法实现错误对目标函数值的影响可以通过
d
或
c
j
中适当的扰动来模仿。
在传统的LO方法中，只是忽略了小数据不确定性（比如1%或更少）。如果给定的（“标准”）数据是准确的，那么问题就解决了，因此标准最优解是建议使用的，希望小数据的不确定性不会显著影响这个解的可行性和最优性，或者对标准解进行微调就能使其可行。我们要证明的是，这些希望不一定是合理的，有时甚至是极小数据的不确定性也值得重视。
考虑以下非常简单的线性优化问题。
例1.1.1 某家公司生产两种药物，DrugⅠ和DrugⅡ含有从市场上购买的原料中提取的特定活性剂A。RawⅠ和RawⅡ两种原料可以作为活性剂的来源。表1-1给出了相关的生产、成本和资源数据。目标函数是找出能使公司利润最大化的生产计划。
表1-1 例1.1.1的数据
这个问题由下面线性规划的程序给出：
受限于
这个问题有四个变量——收购原材料RawⅠ和RawⅡ的量（单位：kg）和生产药物DrugⅠ和DrugⅡ的量（单位：1000包）。
LO问题的最优解是
Opt=-8819.658；RawⅠ=0，RawⅡ=438.789，DrugⅠ=17.552，DrugⅡ=0
注意，预算和平衡约束都是可变的（即生产过程利用全部预算和原材料中活性剂的全部量）。这个最优解为该公司带来了8.8%的利润，虽然不多，但相当可观。
显然，即使在上述简单的问题中，有些数据也不可能是“绝对可靠的”，例如，人们很难相信原材料RawⅠ中活性剂的含量为0.01g/kg，RawⅡ为0.02g/kg。实际上，这些内容因指示值而异。这里的一个自然假设是，RawⅠ中的活性剂aⅠ和RawⅡ中的活性剂aⅡ的实际含量是随机变量，这些变量以某种方式分布在“标准含量”anⅠ=0.01和anⅡ=0.02周围。更具体地说，假设aⅠ在anⅠ的0.5%边际范围内浮动，因此取区间[0.00995，0.01005]中的值。同样，假设aⅡ在anⅡ的2%边际范围内浮动，因此取区间[0.0196，0.0204]中的值。此外，假设aⅠ、aⅡ在各自的段取极端值，概率分别为0.5。活性剂含量的这些浮动是如何影响生产过程的？最优解规定购买438.8kg的RawⅡ和生产17.552K包DrugⅠ（K代表“千”）。在RawⅡ中活性剂含量出现上述随机波动的情况下，该生产计划将不可行的概率为0.5，即原材料中活性剂的实际含量将低于DrugⅠ计划生产的量所需的含量。这可以用最简单的方式解决：当原料活性剂的实际含量不足时，药物的产量就会相应减少。有了这个策略，DrugⅠ的实际生产就变成了一个随机变量，以相等的概率取17.552K包的标准值和17.201K包（少2%）。生产过程中这2%的波动也会影响利润：它成为一个随机的变量，概率为0.5，标准值为8820，而少于21%（！）的值为6929。期望利润为7843，比标准问题的最优解所承诺的标准利润8820少11%。
我们看到，在这个简单示例中，一个相当小的（在现实中是不可避免的）数据扰动，可能会使标准最优解不可行。此外，对实际数据标准最优解直接进行调整可能会严重影响解的质量。
在许多实用的线性程序中也会遇到类似的现象，其中至少有部分数据是不确切的，并且可能会围绕其标准值而变化。数据不确定性的后果可能比上述示例要严重得多。文献[7]的NETLIB集
中对线性优化问题的分析表明，对于94个NETLIB问题中的13个，不确定数据的随机0.01%的扰动就会使标准最优解严重不可行：具有不可忽略的概率，它违背了一些约束条件的50%甚至更高。应当补充的是，在一般情况下（与我们的示例相反），没有明确的方法通过简单修改来调整数据实际值的最优解，而且在某些情况下，这种调整实际上是不可能的：为了使扰动数据变得可行，标准最优解应“完全重构”。
结论如下：在LO的应用中，确实需要一种技术，在数据不确定性会严重影响标准解的质量时，能够检测出这种情况，并且在这种情况下，可以生成一个“可靠”的、不受不确定性影响的解。
我们即将引入针对不确定LO问题的鲁棒对等方法，以应对数据不确定性。