下载掌阅APP，畅读海量书库
立即打开
在对一个给定的系统进行优化时，描述这一问题的数学规划中决策的方案是通过一组已知的约束条件来间接定义的。也就是说，优化问题中所需资源的数量是由决策者以外的某个人以优化技术以外的某种方法事先给定的，并没有作为优化分析的一部分。显然，这一假设往往与实际情况不符。因为在现实问题中，多数资源的局部供应量取决于决策的需要，应该是决策的结果，而不是决策的前提。换而言之，优化理论的最终目的是要设计一个优化的系统，而不仅仅是优化一个已知的系统。这两者之间的差异正日益受到研究人员与管理人员的重视。
为了说明“系统优化”和“优化系统”之间的差异与联系，我们先看一个生动的小故事(Zeleny, 1982)。
某小公司最近几年来一直在生产两种利润很高的圣诞节装饰品，分别记为X和Y。制造装饰品所需材料的品种、数量和价格见表 3 -6。
表 3 -6圣诞装饰品用料情况
目前，装饰品X的单位利润是＄400, Y的单位利润是＄300。为了能维持目前的利润不致下降，公司的高层经理不打算扩大现有的生产规模，并规定了两个原则：一是不允许材料购置经费超过＄2 600;二是确保所生产的装饰品能如数售出，不被积压。由于不同的生产经理组织生产工具的方式不同，公司的总利润一直在上下波动。以下是四位主管人员的经营情况:
(1)经理A是该生产系统的第一个负责人。她运用库存—成本分析制订了购买 20 单位金线,24 单位丝线,60 单位丝绒,10.5 单位银线和 26 单位尼龙线的采购计划，共耗资20 × 30 + 24 × 40 + 60 × 9.5 + 10.5 × 20 + 26 × 10 = ＄2 600,正好用完了全部预算。然后，经理A提议了一个简单的策略：尽可能多地生产装饰品X。这意味着 x = 5, y = 0,其总利润为＄2 000,但留下了价值＄560 的昂贵丝线没有使用，这显然不能令人满意。于是，经理A决定将策略改变为：在用完全部丝线的前提下，生产尽可能多的装饰品X。她计算出 x =3.75, y =2.75,从而避免了丝线这一较贵材料的浪费，使总利润在现有材料下提高到400 ×3.75 +300 ×2.75 = ＄2 325。经理A将为什么较高利润的装饰品X比以前生产少了，总利润反而有所增加的原因向公司董事会作了汇报，从而受到赏识并被提升到更高的职位。
(2)其后，经理B接管了生产的经营管理工作。这是一个年轻的MBA,在线性规划方面受过良好的训练。他很快厌倦了一再听说前经理如何充分利用贵重的丝线以增加效益的说教，决定采用线性规划技术检查当前的生产系统是否最优。为此，经理B建立了下面的数学模型:
解得: x = 4.25, y = 2.25,余留 2 单位的丝线，总利润 400 × 4.25 + 300 × 2.25 =＄2 375,高于原来的＄2 325。因此，经理B对经理A的丝线策略作出了如下的评价：“如果你想使总利润最大化，就不要担心丝线会剩余；新的生产方案才是最佳方案，我们不可能比这做得更好了，除非能增加经费预算，给我们更多的钱。”经理B的高效与自信甚至使经理A也不能不佩服，因此他也得到了提拔。
(3)经理B雇用了经理C作为他的后任，并希望C能继续按照他的方式运作。经理C是一个真正的线性规划专家。他很快发现丝绒和尼龙线的影子价格分别是＄12.5 和＄62.5,这意味着增加一个单位的尼龙线可增加＄62.5 的利润，而尼龙线的价格只是＄10,故纯利润达＄52.5。于是经理C与经理B一起向经理A建议增加预算经费，以便将尼龙线的采购数量提高到 27 单位，则总利润可达＄2 437.5。但经理A不同意增加预算，要求他们在现有的经费基础上解决效益问题。这时，经理A也学会了运用线性规划技术。她按照经理C和B的建议把尼龙线的数量提高到 27,自己摸索着建立了以下的模型:
解得: x = 4.062 5, y = 2.625,总利润为 400 × 4.062 5 + 300 × 2.625 = ＄2 412.5,正好是两位年轻经理提出的利润目标。然后，经理A进一步检查此时的经费预算:16.25 ×30 + 24 × 40 + 60 × 9.5 + 7.875 × 20 + 27 × 10 = ＄2 452.5!这不仅不需要增加预算，甚至比目前预算还节约了＄147.5。于是经理B和经理C都被解雇了，而线性规划技术从此以后在该公司变得流行起来。由于经理B和经理C被解雇，经理A不得不自己安排当年的生产计划。她经过再三的比较和修改，最终确定了下面的线性规划问题:
相应生产计划为: x =4.062 5, y =2.812 5,实现了迄今为止的最高利润 400 × 4.062 5 +300 ×2.812 5 = ＄2 468.75,且预算仅为 16.25 ×30 +25 ×40 +60 ×9.5 +8.437 5 × 20 + 27.5 ×10 = ＄2 501.25!这使得公司中的每个人都说：“经理A又成功了!”
(4)经理A于是再一次得到了提升，她被要求找到一个适当的人选接替经理B和经理C留下的空缺。这一次，经理A尽量避开那些MBA,以免他们又用什么影子价格之类的东西来要求提高经费开支。她最终物色到了一个系统工程方面的博士。这名年轻的博士抱怨说：目前在大多数的商学院里都没有开设系统课程，而工厂也都不喜欢接收博士，因为在经理们的眼里，博士们都读书读过了头，这些人不会安分守己。经理A决定试用这位博士，并给他讲述了自己以前的经验。但年轻的博士听后毫不客气地说：“如果你想得到最大的利润，你现在的系统并不是好系统。事实上，它是一个很差的准优化系统。你应该只生产X,忘掉银线材料和装饰品Y。只要购置 29.4 单位金线,14.7 单位丝线,88 单位丝绒，和 29.4 单位尼龙线就行了。”经理A对于这样的谈话毫无思想准备，于是第二天便解雇了这位经理D。
事后，在一个周末的晚上，经理A决定试一试年轻博士曾经提出的建议。列出的线性规划为:
结果发现, x =7.34, y =0,总利润达 400 ×7.34 = ＄2 936!比她曾经获得的最好效益还高出＄434.75!而此时的经费开支 29.4 × 30 + 14.7 × 40 + 88 × 9.5 + 29.4 × 10 = ＄2 600 正好等于额定预算，并没有增加一分钱。经理A感到既兴奋，又茫然。兴奋的是今年又有了一个高效的生产计划，茫然的是她始终不清楚博士的这些数字是怎样拼凑出来的。
Zeleny讲述的故事到这里就结束了，虽然它还可以往下延续好几页。读者从这个故事里唯一应该记住的是：优化一个给定的系统不同于设计一个优化的系统!
思考：如何优化一个系统。以本案例为例，如何优化这个生产计划系统?
1.写出下列线性规划问题的对偶问题:
(1)
(2)
(3)
(4)
2.判断下列说法是否正确，为什么?
(1)若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值相等。
(2)若一对对偶问题其中之一无可行解，则另一个问题无界。
(3)若原问题有可行解，对偶问题无可行解，则原问题具有无界解。
(4)若某种资源的影子价格等于 q ,在其他条件不变的情况下，当该种资源增加 8 个单位时，相应的目标函数最优值将增大 8 q 。
(5)设(SLP)的对偶最优解为 Y ∗ ,若把(SLP)的目标函数 Z 乘以非零常数 λ ,则其对偶最优解变为 λY ∗ 。
3.给出一个简单的线性规划，使它和它的对偶问题均无可行解。
4.考虑第 2 章例 3 给出的线性规划模型(不考虑变量取整数值条件），要求:
(1)写出对偶问题。
(2)通过解对偶问题求出原问题的最优解。
(3)说明用第(2)小题的求解方法比直接求解原问题有何优越之处。
5.已知表 3 -7 为求解某线性规划问题的最优单纯形表，表中 x 4 , x 5 为松弛变量，问题的约束为“≤”形式。
(1)写出原线性规划问题及其对偶问题。
(2)直接由表 3 -7 写出对偶问题的最优解。
表 3 -7
6.使用单纯形法求解线性规划问题:
并分析在下列各种条件下，原问题的最优解、最优基以及目标函数最优值有什么变化(注意使用灵敏度分析的结果，有需要时可借助计算机求解)。
(1)目标函数中 x 3 的系数由 13 变为 6。
(2)目标函数中 x 2 的系数由 5 变为 4.5。
(3)第二个约束条件的右端项由 90 变为 80。
(4)第一个约束条件的右端项由 20 变为 30。
(5)
x
1
的系数列向量由
变为
。
(6)增加一个新约束条件 2 x 1 + 3 x 2 + 5 x 3 ≤50。
(7)将第二个约束改变为 10 x 1 + 5 x 2 + 10 x 3 ≤100。
(8)目标函数中
x
1
的系数由-5 变为 3,同时增加一个新变量，其目标函数系数为 4,系数列向量为
。
7.给定线性规划问题:
(1)写出其对偶问题。
(2)使用QM软件求解原问题，并直接由最优单纯形表写出对偶问题的最优解。
8.已知线性规划问题:
它的最优单纯形表如表 3 -8 所示。
(1)求原问题和对偶问题的最优解。
(2)求变量 x 1 , x 2 和 x 3 的目标函数系数的可变范围。
(3)求各右端项的可变范围。
表 3 -8
9.某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，各产品都需要经过A、 B、 C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每单位产品的利润如表 3 -9所示。
表 3 -9
(1)求获利最大的产品生产计划。
(2)产品Ⅲ的单位利润在哪个范围变化，最优生产方案保持不变?
(3)若产品Ⅱ的单位利润从 2 000 元增至 2 200 元，最优生产计划有什么变化？总利润会有什么变化?
(4)如果设备A的加工能力增加到 400 台时，当前基是否仍保持最优?
(5)如果设备C的加工能力减少到 180 台时，最优生产计划会发生什么变化?
(6)若为了增加产量，可租借别的工厂的设备B,单位台时的租金是多少才是合算的？应租借多少台时?
(7)如果合同规定产品Ⅲ至少要生产 10 单位，那么生产计划应如何修改?
(8)若另外有两种新产品Ⅳ、Ⅴ,其中每生产单位产品Ⅳ需要A 12 台时, B 5 台时,C 10 台时，可获利 2 100 元；产品V需要设备A 4 台时, B 4 台时, C 12 台时，可获利1 870元。如果A、 B、 C设备台时不增加，分别回答这两种新产品投产在经济上是否合算?
(9)对产品工艺重新进行设计，优化结构。改进后生产每单位产品Ⅰ,需要设备A 9台时，设备B 12 台时，设备C 4 台时，单位产品赢利 4 500 元，问这对原计划有何影响?
10.一家工厂把从四个不同地点运来的铁矿石混合起来，产生一种合适的配料。这种配料对三种基本元素A、 B、 C要有一个最低需要量。表 3 -10 给出从各地点运来的每吨矿石所含各基本元素的千克数，每吨最终配料中各基本元素的最低需要量和各个地点来的矿石每吨的成本。
表 3 -10
(1)求成本最低的混料配比。
(2)每吨最优混合料中各种基本元素的含量是多少?
(3)若把每吨配料中基本元素A的最低需要量降低到 4.75 千克或者提高到 8 千克。最优混合料的成本各有什么变化?
(4)降低配料基本元素B的最低需要量能否降低成本?
(5)若从地点 2 来的矿石的成本从 400 元增加到 450 元，最优混料配比和总成本有什么变化?
(6)从地点 4 来的矿石的成本要降低多少才能使最优混合料中含有该种矿石?
11.一家妇女装饰品公司制作女用流行式产品。根据大量市场调查结果，计划生产七种类型的产品，公司确信能全部售出。财会部门提供了材料与生产费用的资料，市场与销售部门提出了每种产品的批发价格(如表 3 -11 所示)。
表 3 -11 原料费用和批发价格
生产部门报告有三种控制性资源：针织机工时、环织机工时和检验工时。针织机工时有42 000 小时可供使用，每小时成本10 元；环织机工时有5 000 小时，每小时成本20 元；检验工时 3 600小时，每小时成本 30 元。各部门对每类产品所需的工时与费用，如表3 -12所示。
表 3 -12 各部门对每类产品需用的工时与费用
经验表明，在季度高峰时期每种产品所用的材料要有 1 /3 的库存，而公司的政策是无论何时库存的材料价值都不得超过 350 000元。
根据上述资料，装饰品公司需要确定每种产品的最佳生产量。销售部门愿为该公司销售全部产品，但必须保证每种产品至少售出 1 000 单位，目标是公司的利润达到最大值。
请根据计算机求解后的输出结果回答下列问题，并简单说明理由。
(1)最优生产方案是否唯一?
(2)产品 5 的单位价格在哪个范围变动，现行生产方案保持最优?
(3)在最优基不变的条件下，要提高总利润，应优先增加哪种资源的限额？能增加多少？为增加该资源所支付的单位费用应是多少才是合算的?
(4)若第二种产品的最低销售量从 1 000 减少到 950,总利润有什么变化?
(5)能否通过增加针织机工时来提高总利润?
(6)若环织机工时的限额提高到 5 010 小时，最优生产方案有什么变化?
(7)若第一种产品的单价从 50 元增至 55 元，最优生产方案和总利润有什么变化?
每一个线性规划都伴随着一个被称为其对偶问题的线性规划，它们之间有着十分密切的关系。本章介绍了产生对偶问题的实际背景，给出对偶问题的建立规则和基本性质，并讨论了对偶最优解(常称为影子价格）的计算方法及经济解释。
当一个线性规划问题解完后，研究该问题中的某一参数发生变化对求解结果的影响是十分有用的。灵敏度分析(也称为优化后分析）可用来确定某一参数(目标函数系数、右端项等）不影响最优解或最优基变量的可变范围，也可用于考察增加或减少变量和约束条件所带来的变化。
本章列举了一个使用计算机求解和分析的例子。书中的例子着重分析的是系统优化，但更重要的是我们还要优化系统。