第4章线性规划的应用

1、第第4章章 线性规划的应用线性规划的应用 线性规划被誉为是在制定决策时最成功线性规划被誉为是在制定决策时最成功 的定量化方法之一。它几乎应用于各行各业的定量化方法之一。它几乎应用于各行各业 。它涉及的问题包括：生产计划、媒体选择。它涉及的问题包括：生产计划、媒体选择 、财务计划、资本预算、运输问题、配送系、财务计划、资本预算、运输问题、配送系 统设计、产品组合、人事管理以及混合问题统设计、产品组合、人事管理以及混合问题 等等。等等。 在本章我们介绍了线性规划的一系列应在本章我们介绍了线性规划的一系列应 用，包含一些来自于传统商业领域的商销、用，包含一些来自于传统商业领域的商销、 财务以及运作管

2、理等问题。而如何建模、利财务以及运作管理等问题。而如何建模、利 用计算机求解以及输出结果的阐明则是本章用计算机求解以及输出结果的阐明则是本章 的重点。本章中的大多数案例我们都是用管的重点。本章中的大多数案例我们都是用管 理科学家软件来求解的，而在附录中我们阐理科学家软件来求解的，而在附录中我们阐 明了如何利用明了如何利用excel工具来求解关于财务规工具来求解关于财务规 划的问题。划的问题。 4.1 市场营销应用 4.1.1 媒体选择媒体选择 在媒体选择中应用线性规划的目的在于帮在媒体选择中应用线性规划的目的在于帮 助营销经理将固定的广告预算分配到不同的媒助营销经理将固定的广告预算分配到不同的

3、媒 体中去。潜在的媒体有报纸、杂志、电台、电体中去。潜在的媒体有报纸、杂志、电台、电 视和直接的邮件等。在这些应用中，我们的目视和直接的邮件等。在这些应用中，我们的目 的就是借用媒体使宣传范围，频率和质量最大的就是借用媒体使宣传范围，频率和质量最大 化。在应用中的约束通常源于公司的政策、合化。在应用中的约束通常源于公司的政策、合 同的要求以及媒体的可用性等等。在接下来所同的要求以及媒体的可用性等等。在接下来所 介绍的应用中，我们将介绍如何利用线性规划介绍的应用中，我们将介绍如何利用线性规划 建立模型以求解关于媒体选择的问题。建立模型以求解关于媒体选择的问题。 rel发展公司正在私人湖边开发一个

4、发展公司正在私人湖边开发一个 环湖社区，湖边地带和住宅的主要市场是环湖社区，湖边地带和住宅的主要市场是 距开发区距开发区100英里以内的所有中上等收入家英里以内的所有中上等收入家 庭。庭。rel公司已经聘请公司已经聘请bp b1=(部门部门1最初的工时最初的工时)+(转移到部门转移到部门1的工时的工时)-（ 从部门从部门1转移出的工时）转移出的工时） 表表4-11表明，最初分配到部门表明，最初分配到部门1的工时是的工时是6500小小 时。我们用转移决策变量时。我们用转移决策变量tij来表示转移到部门来表示转移到部门1 的工时，的工时，t1j表示从部门表示从部门1转移出的工时。表转移出的工时。表

5、4-12 显示，涉及部门显示，涉及部门1的交叉培训被限定在只能从部的交叉培训被限定在只能从部 门门4转移过来（变量转移过来（变量t41）并且职能转移到部门）并且职能转移到部门2、 3中去（变量中去（变量t12或或t13）。这样，我们就能够表示）。这样，我们就能够表示 出部门出部门1的总的劳动力分配了：的总的劳动力分配了： b1=6 500+ t41- t12- t13 把劳动力转移决策变量放到等式左边，我们可以把劳动力转移决策变量放到等式左边，我们可以 得到劳动力平衡等式或者说约束条件如下：得到劳动力平衡等式或者说约束条件如下： b1- t41+t12+ t13=6500 我们必须把对我们必须

6、把对4 个部门的约束都写成这种形式个部门的约束都写成这种形式 。因此，接下来的部门。因此，接下来的部门2,3和和4的劳动力平衡约束也的劳动力平衡约束也 可以加入到模型中了。可以加入到模型中了。 b2-t12-t42+t23+t24=6 000 b3-t13- t23+t34 =7 000 b4-t24-t34+t41+t42=1 400 最后要注意的是，由于表最后要注意的是，由于表4-12所示每个部门可所示每个部门可 转移的时间是有限的，所以模型中必须加上转移的时间是有限的，所以模型中必须加上4个部个部 门的转移量的约束条件。额外的约束条件分别是：门的转移量的约束条件。额外的约束条件分别是：

7、t12+t13400 t23+t24800 t34 100 t41+t42200 完整的线性规划模型有完整的线性规划模型有2个生产决策变量个生产决策变量 （p1和和p2）,4个部门的劳动力分配变量（个部门的劳动力分配变量（b1， ，b2，b3 ，b4，），），7个转移变量（个转移变量（ t12,t13,t23,t24,t34,t41,t42）和）和12个约束条件。图个约束条件。图4- 8显示了该问题的最佳解决方案。显示了该问题的最佳解决方案。 通过交叉培训和劳动力转移，通过交叉培训和劳动力转移， mccormick公司的利润从公司的利润从73 590美元增加到美元增加到 84 011美元，增加

8、了美元，增加了10 421美元。如果部门美元。如果部门1 有有400个小时转移到部门个小时转移到部门3，部门，部门2有有651个小个小 时转移到部门时转移到部门3,149个小时拽一到部门个小时拽一到部门4，这，这 时的最优产品组合是时的最优产品组合是6 825单位的产品单位的产品1和和1 751单位的产品单位的产品2。4个部门将相应提供个部门将相应提供6 100,5 200,8 051.和和1 549小时的工作时间。小时的工作时间。 objective function value = 8299.80078 variable value reduced costs - - - p1 6824.

9、859 0.000 p2 1751.412 0.000 b1 6100.000 0.000 b2 5200.000 0.000 b3 8050.847 0.000 b4 1549.153 0.000 t12 0.000 8.249 t13 400.000 0.000 t23 650.847 0.000 t24 149.153 0.000 t34 0.000 0.000 t41 0.000 7.458 t42 0.000 8.249 constraint slack/surplus dual prices - - - 1 0.000 0.791 2 640.113 0.000 3 0.000 8

10、.249 4 0.000 8.249 5 0.000 0.791 6 0.000 0.000 7 0.000 8.249 8 0.000 8.249 9 0.000 7.458 10 0.000 8.249 11 100.000 0.000 12 200.000 0.000 4.4混合问题 当一个经理必须决定怎样混合两种以上的资当一个经理必须决定怎样混合两种以上的资 源来生产一种以上的产品时，混合问题就产生了。源来生产一种以上的产品时，混合问题就产生了。 在这些实际情况下，最终产品中包含资源中一种以在这些实际情况下，最终产品中包含资源中一种以 上的基本成分，而且成品包含一定比例的各种资源上的基

11、本成分，而且成品包含一定比例的各种资源 。在实际应用中，管理层必须决定每种资源的购买。在实际应用中，管理层必须决定每种资源的购买 量，以在成本最低的情况下满足产品的规格以及生量，以在成本最低的情况下满足产品的规格以及生 产该产品的需求。产该产品的需求。 混合问题经常发生在石油行业（如混合原油混合问题经常发生在石油行业（如混合原油 以生产辛烷汽油），化工行业（录用混合化学品制以生产辛烷汽油），化工行业（录用混合化学品制 造化肥和除草剂），食品行业（如混合各种原料生造化肥和除草剂），食品行业（如混合各种原料生 产软饮料和汤剂）。在这一节，我们将介绍怎样将产软饮料和汤剂）。在这一节，我们将介绍怎样将

12、 线性规划应用到石油行业的一个混合问题中去。线性规划应用到石油行业的一个混合问题中去。 grand strand石油公司为美国东南部独石油公司为美国东南部独 立的石油加油站生产一般规格和特殊规格的立的石油加油站生产一般规格和特殊规格的 汽油。汽油。grand strand石油公司精炼厂通过合石油公司精炼厂通过合 成成3种石油成分来生产汽油产品。这些汽油种石油成分来生产汽油产品。这些汽油 以不同的价格出售，而且这以不同的价格出售，而且这3种汽油成分的种汽油成分的 成本也不同。公司想通过决定一种混合这成本也不同。公司想通过决定一种混合这3 种石油成分以生产两种汽油产品的方案来获种石油成分以生产两种

13、汽油产品的方案来获 得最大的产品利润。得最大的产品利润。 现有的资料显示，一般规格汽油的售现有的资料显示，一般规格汽油的售 价是价是1.00美元美元加仑，而特殊汽油是加仑，而特殊汽油是1.08美元美元 加仑。在当前的生产计划期内，加仑。在当前的生产计划期内，grand strand石油公司可以得到的那石油公司可以得到的那3种石油成分种石油成分 每加仑的成本和总量见表每加仑的成本和总量见表4-13。 grand strand石油公司的混合问题就是要决石油公司的混合问题就是要决 定一般规格汽油和特殊规格汽油的每种石油成分定一般规格汽油和特殊规格汽油的每种石油成分 的用量分别为多少。对应用于表的用量

14、分别为多少。对应用于表4-13种可用的石种可用的石 油成分的总量的最佳方案应能实现公司的总利润油成分的总量的最佳方案应能实现公司的总利润 最大化。产品规格见表最大化。产品规格见表4-14，而且最少要生产，而且最少要生产10 000加仑的一般规格的汽油。加仑的一般规格的汽油。 表表4-13 grand strand石油公司混合问题的成本和供给量石油公司混合问题的成本和供给量 石油成分石油成分 单位成本单位成本 （美元）（美元） 最大供应量最大供应量 （加仑）（加仑） 12.505 000 22.6010 000 32.8410 000 表表4-14 grand strand石油公司混合问题的具体

15、要求石油公司混合问题的具体要求 产品产品 规格规格 一般规格汽油一般规格汽油 最多最多30%成分成分1 最少最少40%成分成分2 最多最多20%成分成分3 特殊规格汽油特殊规格汽油 最少最少25%成分成分1 最多最多45%成分成分2 最少最少30%成分成分3 我们定义决策变量如下：我们定义决策变量如下： xij石油石油j里面含有成分里面含有成分i的含量，的含量， i=1, 2或或3表示对应的石油成分表示对应的石油成分1,2或或3，并且，并且 一般汽油规格一般汽油规格j=r，特殊汽油规格的，特殊汽油规格的j=p。 则则6个决策变量为：个决策变量为： x1r 一般规格汽油中成分一般规格汽油中成分1

16、的用量；的用量； x2r 一般规格汽油中成分一般规格汽油中成分2的用量；的用量； x3r 一般规格汽油中成分一般规格汽油中成分3的用量；的用量； x1p 特殊规格汽油中成分特殊规格汽油中成分1的用量；的用量； x2p 特殊规格汽油中成分特殊规格汽油中成分2的用量；的用量； x3p 特殊规格汽油中成分特殊规格汽油中成分3的用量。的用量。 各种汽油的总产量等于通过使用那各种汽油的总产量等于通过使用那3种种 石油成分所生产的量。石油成分所生产的量。 总产量为：总产量为： 一般规格汽油一般规格汽油= x1r + x2r + x3r 特殊规格汽油特殊规格汽油= x1p + x2p + x3p 每种石油成

17、分使用的加仑数也可用类每种石油成分使用的加仑数也可用类 似的公式计算出。似的公式计算出。 总共使用的石油成分：总共使用的石油成分： 成分成分1= x1r + x1p 成分成分2= x2r + x2p 成分成分3= x3r+ x3p 我们通过找出这两种汽油生产的总收入我们通过找出这两种汽油生产的总收入 和和3种成分的总成本的不同来建立我们的目标种成分的总成本的不同来建立我们的目标 函数。一般规格汽油的加仑总量乘上它的价格函数。一般规格汽油的加仑总量乘上它的价格 2.90美元美元/加仑，特殊规格汽油的加仑总量乘上加仑，特殊规格汽油的加仑总量乘上 它的价格它的价格3.00美元美元/加仑，而总共使用的

18、每种石加仑，而总共使用的每种石 油成分乘上每加仑的成本（见表油成分乘上每加仑的成本（见表4-13），我们），我们 就得到了目标函数：就得到了目标函数： max 2.90(x1r + x2r + x3r)+3.00(x1p + x2p + x3p)-2.50(x1r + x1p)-2.60(x2r + x2p)-2.84(x3r+ x3p) 合并同类项，目标函数变为：合并同类项，目标函数变为： max 0.40 x1r +0.30 x2r +0.06 x3r +0.50 x1p +0.40 x2p +0.16 x3p 3种石油成分在总量上的约束条件是：种石油成分在总量上的约束条件是： x1r +

19、 x1p5 000 成分成分1 x2r + x2p10 000 成分成分2 x3r + x3p10 000 成分成分3 对于表对于表4-14中的产品规格，有中的产品规格，有6个约束条个约束条 件。第一条产品规格表明了成分件。第一条产品规格表明了成分1不能超过一不能超过一 般规格汽油总加仑数的般规格汽油总加仑数的30%，即：，即： x1r0.30(x1r + x2r + x3r) 将所有约束变量移到左边，常数移到右将所有约束变量移到左边，常数移到右 边，得：边，得： 0.70 x1r-0.30 x2r-0.30 x3r0 表表4-14中第二条产品规格有以下约束：中第二条产品规格有以下约束： x2

20、r0.40( x1r + x2r + x3r) 因此有：因此有： -0.40 x1r +0.60 x2r -0.40 x3r 0 类似地，我们根据表类似地，我们根据表4-14写出剩下的写出剩下的4个混合个混合 规格的约束条件规格的约束条件 -0.20 x1r -0.20 x2r +0.80 x3r 0 +0.75 x1r -0.25 x2r -0.25 x3r 0 -0.45 x1r +0.55 x2r -0.45 x3r 0 -0.30 x1r -0.30 x2r +0.70 x3r 0 至少生产至少生产10000加仑一般规格汽油的约束条件加仑一般规格汽油的约束条件 如下：如下： x1r +

21、 x2r + x3r10000 于是包括于是包括6个决策变量和个决策变量和10个约束条件的完整的线性规个约束条件的完整的线性规 划模型如下：划模型如下： max 0.40 x1r +0.30 x2r +0.06x3r +0.50 x1p +0.40 x2p +0.16x3p s.t. x1r + x1p 5 000 x2r + x2p 10 000 x3r + x3p10 000 0.70 x1r -0.30 x2r -0.30 x3r 0 -0.40 x1r+0.60 x2r -0.40 x3r 0 -0.20 x1r -0.20 x2r+0.80 x3r 0 0.75 x1p -0.25

22、x2p -0.25 x3p 0 -0.45 x1p +0.55 x2p -0.45 x3p 0 -0.30 x1p -0.30 x2p +0.70 x3p 0 x1r + x2r + x3r 10 000 x1r，x2r，x3r，x1p，x2p，x3p0 crand strand石油公司混合问题的最优解决石油公司混合问题的最优解决 方案见图方案见图4-9。最优方案提供了。最优方案提供了7 100美元的利润美元的利润 （见表（见表4-15）。最有混合生产策略显示，应生产）。最有混合生产策略显示，应生产 10000加仑的常规汽油。常规汽油由加仑的常规汽油。常规汽油由1 250加仑的成加仑的成 分分

23、1、6 750加仑的成分加仑的成分2和和2 000加仑的成分加仑的成分3混合混合 制成。而制成。而15 000加仑的特殊汽油由加仑的特殊汽油由3 750加仑的橙加仑的橙 盒版盒版1、3 250加仑的成分加仑的成分2和和8 000加仑的成分加仑的成分3混混 合制成。合制成。 表表4-15 石油公司混合问题的最优解决方案石油公司混合问题的最优解决方案 汽油汽油 每种成分的加仑数（所占比例）每种成分的加仑数（所占比例） 合计合计 成分成分1成分成分2成分成分3 一般规格一般规格 1 250 （12.5%） 6 750(67.5%)2 000(20%)10 000 特殊规格特殊规格3 750(25%)3 250(21.67%) 8 000(53.33%)15 000 objective function value = 7100.000 variable value reduced costs - - - x1r 1250.000 0.000 x2r 6750