7随机规划模型 7.1引言 多期计划很困难的主要理由就是未来的情况不确定。一般来说，我们今天要做的某个行 为或决策应该是未来可能出现各种情况下最好决策的一个折衷。例如，如你预计下一年产品 需求量可能很大，而且原材料价格将迅速上涨，那么，你今天购买大量原材料以备下一年使 用的举动就是一个明智和理性的决策。然而另一方面，如果万一下一年的产品和原材料市场 都消失了，那么，公司的股东决不会认为你的行为只是运气不好而己。 7.2不确定举例 在现实问题中，我们常常会遇到一些典型的不确定情况，现举例如下： 1)与气候有关的不确定情况： ●要为即将到来的冬季决定存储汽油的数量和地点： ●考虑到水力发电、航运和灌溉，要决定春天的放水计划。 2)与金融有关的不确定情况： ●市场价格的变动（例如，股票价格，投资利率和汇率的变动）： ●贸易伙伴的消失（例如，主要客户的破产）。 3)与政治有关的不确定情况： ·政府的更迭： ●敌意的爆发。 4)与技术有关的不确定情况： ●一种新技术何时被采用要等到下一代产品列入计划才可以确定。 5)与行情有关的不确定情况： ●品味与时尚的转移 ●人口的移动
1 7 随机规划模型 7.1 引言 多期计划很困难的主要理由就是未来的情况不确定。一般来说，我们今天要做的某个行 为或决策应该是未来可能出现各种情况下最好决策的一个折衷。例如，如你预计下一年产品 需求量可能很大，而且原材料价格将迅速上涨，那么，你今天购买大量原材料以备下一年使 用的举动就是一个明智和理性的决策。然而另一方面，如果万一下一年的产品和原材料市场 都消失了，那么，公司的股东决不会认为你的行为只是运气不好而已。 7.2 不确定举例 在现实问题中，我们常常会遇到一些典型的不确定情况，现举例如下： 1）与气候有关的不确定情况: ⚫ 要为即将到来的冬季决定存储汽油的数量和地点； ⚫ 考虑到水力发电、航运和灌溉，要决定春天的放水计划。 2）与金融有关的不确定情况: ⚫ 市场价格的变动(例如，股票价格，投资利率和汇率的变动)； ⚫ 贸易伙伴的消失(例如，主要客户的破产)。 3）与政治有关的不确定情况: ⚫ 政府的更迭; ⚫ 敌意的爆发。 4）与技术有关的不确定情况: ⚫ 一种新技术何时被采用要等到下一代产品列入计划才可以确定。 5）与行情有关的不确定情况: ⚫ 品味与时尚的转移; ⚫ 人口的移动
2 6)与竞争有关的不确定情况： 。为下一年的竞争而准备的各种策略。 7)与不可抗拒力有关的不确定情况 ·可能的飓风，龙卷风，地震和火灾， ●可能的设备故障。 在不确定决策分析的过程中，我们首先要鉴别哪些项目与我们的决策有关（例如上边列 出的项目)。在特殊情况下，气候也可以是一个大的不确定源。例如，有报告说：某个水电 站在以后的3年内，由于降雨量的变化使得每年的发电量可以从8,350亿瓦小时下降到2,100 亿瓦小时。 在汽车工业和公共事业领域也会出现不确定情况。由于未来需求不确定，汽车工业就面 临着要对下属的工厂做出开或关的决定。在公共事业方面，由于未来气候不确定，政府要为 以后数年购买多少燃料做出决定。 7.3状态方法 我们首先来研究一个2周期的计划问题，这类问题需要分3个步骤来完成： 步骤1：做出第1期决策。 步骤2：自然地（就如同市场情况一样常常知道结果）做出一个随机决策。 步骤3：根据(2)做出第2期决策。该决策试图改善最坏的结果。 状态方法假定：自然地做出随机决定的数目是有限的。我们称可能出现的自然情况称为 “状态”。例如，在实践中，多数人愿意将产品的需求分为低、中、高3个状态：或者愿意 将冬季分为严冬、正常、暖冬3个状态，而不愿意用60个地点的日平均温度或降雪量取而 代之。历史上，通用汽车公司就使用低、中、高3个状态来描述需求的不确定性。如果一 个LP模型含有不确定性，那么就称这个LP模型是一个“随机规划”。 下面介绍本章的第1个例子。在对这个例子进行分析的过程中，步骤(1)和(2)非常重要。 例1假设有一个农民可以在他的地里种植玉米、高粱或大豆。他愿意将种植季节化分为 旱季和雨季。为了简单起见，我们假设他的划分成立。就是说除了旱季和雨季，不会出现其 它的情况。如果出现雨季，种植玉米的利润多一些：否则，种植高粱的利润多一些。具体的 数据可以从下面的表格中得到： 利润亩（迭策的函数）
2 6) 与竞争有关的不确定情况: ⚫ 为下一年的竞争而准备的各种策略。 7) 与不可抗拒力有关的不确定情况: ⚫ 可能的飓风，龙卷风，地震和火灾; ⚫ 可能的设备故障。 在不确定决策分析的过程中，我们首先要鉴别哪些项目与我们的决策有关（例如上边列 出的项目）。在特殊情况下，气候也可以是一个大的不确定源。例如，有报告说：某个水电 站在以后的3年内，由于降雨量的变化使得每年的发电量可以从 8,350 亿瓦小时下降到2,100 亿瓦小时。 在汽车工业和公共事业领域也会出现不确定情况。由于未来需求不确定，汽车工业就面 临着要对下属的工厂做出开或关的决定。在公共事业方面，由于未来气候不确定，政府要为 以后数年购买多少燃料做出决定。 7.3 状态方法 我们首先来研究一个 2 周期的计划问题，这类问题需要分 3 个步骤来完成： 步骤 1：做出第 1 期决策。 步骤 2：自然地 (就如同市场情况一样常常知道结果)做出一个随机决策。 步骤 3：根据（2）做出第 2 期决策。该决策试图改善最坏的结果。 状态方法假定：自然地做出随机决定的数目是有限的。我们称可能出现的自然情况称为 “状态”。例如，在实践中，多数人愿意将产品的需求分为低、中、高 3 个状态；或者愿意 将冬季分为严冬、正常、暖冬 3 个状态，而不愿意用 60 个地点的日平均温度或降雪量取而 代之。 历史上，通用汽车公司就使用低、中、高 3 个状态来描述需求的不确定性。如果一 个 LP 模型含有不确定性，那么就称这个 LP 模型是一个“随机规划”。 下面介绍本章的第 1 个例子。在对这个例子进行分析的过程中，步骤(1)和(2)非常重要。 例 1 假设有一个农民可以在他的地里种植玉米、高粱或大豆。他愿意将种植季节化分为 旱季和雨季。为了简单起见，我们假设他的划分成立。就是说除了旱季和雨季，不会出现其 它的情况。如果出现雨季，种植玉米的利润多一些；否则，种植高粱的利润多一些。具体的 数据可以从下面的表格中得到： 利润/亩（决策的函数）
3 我们的迭策 自然状态 都种玉米 都种高粱 都种大豆 雨季 $100 $70 $80 旱季 -$10 $40 $35 在步骤(1)中，农民要决定各种农作物种植的数量。对于步骤(2)，如果出现旱季或 雨季，农民要做出相应的决定。就这个问题来说，步骤(3)并不重要。该农民希望利润最 大或损失最小。 如果都种大豆，则不可能得到最优解。你也可以试一试不考虑种植大豆的情况。当然， 我们会看到也得不到最优解。 从图71的曲线中可以看到：某些自然状态下，恰好有两个决策具有同样的效果。 图7.1纯策略下的期望利润 100 都种玉米 都种大豆 75 每亩的 都种高粱 50 润 25 0 -25 雨季的概率 三条直线表示：在纯策略下条件下（只种植一种作物），种植农作物的期望利润是雨季 概率的线性函数。如果假设雨季的概率是，那么，各种农作物的期望利润是： 玉米 高粱 大豆 期望利润 -10+110p40+30p 35+45p 假设我们的目标是期望利润达到最大。那么，当雨季的概率p=1/3时种植高粱和大豆都 达到最大利润：当雨季的概率p=9/13时，种植大豆和玉米也都达到最大利润。因此，如果 雨季的概率小于13，就应该都种植高粱：如果雨季的概率大于913，这时就应该都种植玉 米：如果雨季的概率在13到9/13之间，这时就应该都种植大豆。所有这些结论都是在农民
3 我们的决策 自然状态 都种玉米 都种高粱 都种大豆 雨季 $100 $70 $80 旱季 -$10 $40 $35 在步骤（1）中，农民要决定各种农作物种植的数量。对于步骤（2），如果出现旱季或 雨季，农民要做出相应的决定。就这个问题来说，步骤（3）并不重要。该农民希望利润最 大或损失最小。 如果都种大豆，则不可能得到最优解。你也可以试一试不考虑种植大豆的情况。当然， 我们会看到也得不到最优解。 从图 7.1 的曲线中可以看到：某些自然状态下，恰好有两个决策具有同样的效果。 图 7.1 纯策略下的期望利润 三条直线表示：在纯策略下条件下（只种植一种作物），种植农作物的期望利润是雨季 概率的线性函数。如果假设雨季的概率是 p，那么，各种农作物的期望利润是: 玉米 高粱 大豆 期望利润 -10+ 110p 40 + 30p 35 +45p 假设我们的目标是期望利润达到最大。那么，当雨季的概率 p = 1/3 时种植高粱和大豆都 达到最大利润；当雨季的概率 p = 9/13 时，种植大豆和玉米也都达到最大利润。因此，如果 雨季的概率小于 1/3，就应该都种植高粱；如果雨季的概率大于 9/13，这时就应该都种植玉 米；如果雨季的概率在 1/3 到 9/13 之间，这时就应该都种植大豆。所有这些结论都是在农民
只对最大利润感兴趣而不考虑风险问题这一假设基础之上而得到的。就是说，如果农民只追 求利润最大，那么，最优策略一定是一个纯策略：都种植玉米，或都种植高粱，或都种植大 豆。 针对可能出现的各种自然状态，人们也许试着用“条件最优”决策的加权平均来进行第 1期的决策。对于这个例子，如果我们知道自然状态是雨季，最优解就是都种植玉米：如果 我们知道自然状态是旱季，最优解就是都种植高粱。假设雨季的概率是3/8。因此，"加权" 的决策是每亩种植3/8的玉米和5/8的高粱。这时，每亩的期望利润是(3/8)(3/8)100+(5/8)70] +(5/8)[(3/8)(-10)+(5/8)40]=$43.75 我们将这个结果与期望利润最大的决策进行比较。如果雨季的概率等于3/8，每亩都种 植大豆的期望利润是(3/8)80+(5/8)35=$51.875。这个最优值比前面所谓的“合理”结果多 20%。 从这个例子中，我们可以得到下面实质性的结论： 如果未来有多种状态，今天的最优决策一般情况下不等于各种状态下最 优决策的“加权平均”。 对于这个简单的问题，人们并非一定要用LP求解。然而，为了今后处理更为复杂的问 题，我们还是用LP来演示一下。这里，第1期有3个决策变量： C=玉米种植的数量（亩）， S=高粱种植的数量（亩）， B=大豆种植的数量（亩）。 假设未来出现雨季的概率为3/8，目标函数是： Maximize(3/8)(100c+70s+80B)+(5/8)(-10c+40S+35B) subject to C+s B <1 上面唯一的约束是表示：我们只考虑在一亩地里种植何种作物。将目标函数简化，就得 到： Maximize31.25c+51.25S+51.875B subject to C+S+B<=1。 解答是B=1(就是都种植大豆)。 注意，目标函数中玉米和高粱的系数分别是相应作物的期望利润（每亩）
4 只对最大利润感兴趣而不考虑风险问题这一假设基础之上而得到的。就是说，如果农民只追 求利润最大，那么，最优策略一定是一个纯策略：都种植玉米，或都种植高粱，或都种植大 豆。 针对可能出现的各种自然状态，人们也许试着用“条件最优”决策的加权平均来进行第 1 期的决策。对于这个例子，如果我们知道自然状态是雨季，最优解就是都种植玉米；如果 我们知道自然状态是旱季，最优解就是都种植高粱。假设雨季的概率是 3/8。因此，"加权" 的决策是每亩种植 3/8 的玉米和 5/8 的高粱。这时，每亩的期望利润是(3/8)[(3/8)100 + (5/8)70] + (5/8) [(3/8)(-10) + (5/8)40] = $43.75. 我们将这个结果与期望利润最大的决策进行比较。如果雨季的概率等于 3/8，每亩都种 植大豆的期望利润是(3/8)80 + (5/8)35 = $51.875。这个最优值比前面所谓的“合理”结果多 20%。 从这个例子中，我们可以得到下面实质性的结论： 如果未来有多种状态，今天的最优决策一般情况下不等于各种状态下最 优决策的“加权平均”。 对于这个简单的问题，人们并非一定要用 LP 求解。然而，为了今后处理更为复杂的问 题，我们还是用 LP 来演示一下。这里，第 1 期有 3 个决策变量： C = 玉米种植的数量（亩）， S = 高粱种植的数量（亩）， B = 大豆种植的数量（亩）。 假设未来出现雨季的概率为 3/8，目标函数是： Maximize (3/8)(100C + 70S + 80B) + (5/8)(-10C + 40S + 35B) subject to C + S + B <= 1 上面唯一的约束是表示：我们只考虑在一亩地里种植何种作物。将目标函数简化，就得 到： Maximize 31.25 C + 51.25 S + 51.875 B subject to C + S + B <= 1。 解答是 B = 1 (就是都种植大豆)。 注意，目标函数中玉米和高粱的系数分别是相应作物的期望利润（每亩）
7.4一个更为复杂的2周期计划问题 在前面的例子中，第2期决策不是很重要。自然状态给出后，相应的决策显而易见。 然而在下面的例子中，就需要做出第2期的决策。 例2假设某个北方城市已经到了夏季的后期（假设没有秋季）。道路主管要为即将来到 的冬季购买清除道路积雪用的燃料和食盐。如果出现严冬，燃料和食盐未必能保证供应，而 且价格可能要上涨。清除道路积雪有两种方法：一种方法是铲雪，一种方法是撒盐。相对来 说，撒盐要便宜一些，尤其是在暖冬季节更是如此。然而，暖冬季节之后，多余的食盐一定 要等到下一个冬季来临才能使用，而多余的燃料可以用做它用，无须存储到下一个冬季。所 以，如果准备的燃料多了也不会造成太大的浪费。 道路主管愿意将冬季分为暖冬和严冬，并假设暖冬和严冬出现的概率分别为0.4和0.6。 在下面的表格里列出了食盐和燃料的成本和回收价值。在冬季之前就要做第1期决策，在冬 季来临之后就要做第2期决策。为读者方便，所有的数据都用“车天”表示。1“车天”就 是一辆清雪车一天的费用。 成本或价值 食盐 燃料 成本/车天 第1期购买 S20 S70 第2期购买 暖 S30 S73 S110 寒 S32 S73 $120 第2期末的回收价值 S15 S65 注意，食盐第2期的价格是一个随机变量（取决于气候）。如果冬季寒冷，我们预计食 盐的价格将会上涨。 在暖冬季节，每天出动一辆车的成本（除了燃料和食盐）是$110，而在严冬季节是$120。 整个冬季可以出动的车天数为5,000。如果只是铲雪，一个暖冬除雪大约需要3,500车天：而 一个严冬除雪大约需要5,100车天。一般来说，撒盐除雪的效率要高一点。在暖冬，一辆清 雪车撒盐除雪的效率是铲雪的1.2倍：在严冬，一辆清雪车撒盐除雪的效率是铲雪的1.1倍。 所以，在严冬季节，必须有一定数量的清雪车从事撒盐除雪。 下面定义各个时间段的变量： BF1=第1期购买燃料的数量（车天） BS1=第1期购买食盐的数量（车天）：
5 7.4 一个更为复杂的 2 周期计划问题 在前面的例子中， 第 2 期决策不是很重要。自然状态给出后，相应的决策显而易见。 然而在下面的例子中，就需要做出第 2 期的决策。 例 2 假设某个北方城市已经到了夏季的后期（假设没有秋季）。道路主管要为即将来到 的冬季购买清除道路积雪用的燃料和食盐。如果出现严冬，燃料和食盐未必能保证供应，而 且价格可能要上涨。清除道路积雪有两种方法：一种方法是铲雪，一种方法是撒盐。相对来 说，撒盐要便宜一些，尤其是在暖冬季节更是如此。然而，暖冬季节之后，多余的食盐一定 要等到下一个冬季来临才能使用，而多余的燃料可以用做它用，无须存储到下一个冬季。所 以，如果准备的燃料多了也不会造成太大的浪费。 道路主管愿意将冬季分为暖冬和严冬，并假设暖冬和严冬出现的概率分别为 0.4 和 0.6。 在下面的表格里列出了食盐和燃料的成本和回收价值。在冬季之前就要做第 1 期决策，在冬 季来临之后就要做第 2 期决策。为读者方便，所有的数据都用“车天”表示。1“车天”就 是一辆清雪车一天的费用。 成本 或 价值 食盐 燃料 成本/车天 第 1 期购买 $20 $70 第 2 期购买 暖 $30 $73 $110 寒 $32 $73 $120 第 2 期末的回收价值 $15 $65 注意，食盐第 2 期的价格是一个随机变量（取决于气候）。如果冬季寒冷，我们预计食 盐的价格将会上涨。 在暖冬季节，每天出动一辆车的成本（除了燃料和食盐）是$110，而在严冬季节是$120。 整个冬季可以出动的车天数为 5,000。如果只是铲雪，一个暖冬除雪大约需要 3,500 车天；而 一个严冬除雪大约需要 5,100 车天。一般来说，撒盐除雪的效率要高一点。在暖冬，一辆清 雪车撒盐除雪的效率是铲雪的 1.2 倍；在严冬，一辆清雪车撒盐除雪的效率是铲雪的 1.1 倍。 所以，在严冬季节，必须有一定数量的清雪车从事撒盐除雪。 下面定义各个时间段的变量： BF1 = 第 1 期购买燃料的数量（车天） BS1 = 第 1 期购买食盐的数量（车天）；