治理运筹学(第二版)课后习题参考答案.doc
《治理运筹学(第二版)课后习题参考答案.doc》由会员分享,可在线阅读,更多相关《治理运筹学(第二版)课后习题参考答案.doc(23页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、-_管理运筹学管理运筹学 (第二版)课后习题参考答案(第二版)课后习题参考答案第第 1 1 章章 线性规划(复习思考题)线性规划(复习思考题)1什么是线性规划?线性规划的三要素是什么?答:线性规划(Linear Programming,LP)是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标
2、,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。2求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误?答:(1)唯一最优解:只有一个最优点;(2)多重最优解:无穷多个最优解;(3)无界解:可行域无界,目标值无限增大;(4)没有可行解:线性规划问题的可行域是空集。当无界解和没有可行解时,可能是建模时有错。3什么是线性规划的标准型?松弛变量和剩余变量的管理含义是什么?答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项,0ib决策变量满足非负性。如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;
3、剩余变量取值为非零的话,则说明“”型约束的左边取值大于右边规划值,出现剩余量。4试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答:可行解:满足约束条件的解,称为可行解。0XbAX,基可行解:满足非负性约束的基解,称为基可行解。可行基:对应于基可行解的基,称为可行基。最优解:使目标函数最优的可行解,称为最优解。最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示:-_5用表格单纯形法求解如下线性规划。32124maxxxxZs.t. 0,86238321321321xxxxxxxxx解:标准化 32124maxxxxZs.t. 0,8623854321532
4、14321xxxxxxxxxxxxx列出单纯形表jc41200BCBXb1x2x3x4x5xi04x2831102/805x8611018/6j4120041x1/413/81/81/80(1/4)/(1/8)05x13/265/41/43/41(13/2)/(1/4)j01/23/2-1/2023x28311005x622011j125020故最优解为,即,此时最优值为TX)6 , 0 , 2 , 0 , 0(* 2, 0, 0321xxx4*)(XZ6表 115 中给出了求极大化问题的单纯形表,问表中为何值及变dccaa,2121量属于哪一类型时有:(1)表中解为唯一最优解;(2)表中解为
5、无穷多最优解之一;(3)下一步迭代将以代替基变量;(4)该线性规划问题具有无界解;(5)该线1x5x-_性规划问题无可行解。表 115 某极大化问题的单纯形表jc1c2c000BCBXb1x2x3x4x5xi03xd41a10004x21501005x32a3001j1c2c000解:(1);0, 0, 021ccd(2);中至少有一个为零)(2121,0, 0, 0ccccd(3);2213 4, 0, 0adac(4);0, 012ac(5)为人工变量,且为包含 M 的大于零的数,;或者为人工变量,1x1c23 4ad2x且为包含 M 的大于零的数,2c0, 01da7用大 M 法求解如下
6、线性规划。321635maxxxxZs.t. 0,101632182321321321321xxxxxxxxxxxx解:加入人工变量,进行人造基后的数学模型如下:65432100635maxMxxxxxxZs.t. )6 , 2 , 1(0 101632182632153214321ixxxxxxxxxxxxxi-_列出单纯形表jc53600MBCBXb1x2x3x4x5x6xi04x1812110018/105x1621301016/3M6x1011100110/1j5+M3+M6+M00004x38/31/35/3011/3038/563x16/32/31/3101/3016M6x14/3
7、1/32/3001/3114/2jM311M32100M312004x11/20011/25/263x31/20101/21/2632x71/21001/23/214j1/20003/2M2304x400111351x610201132x4011012j001021M故最优解为,即,此时最优值TX)0 , 0 , 4 , 0 , 4 , 6(* 0, 4, 6321xxx为42*)(XZ8A,B,C 三个城市每年需分别供应电力 320,250 和 350 单位,由 I,II 两个电站提供,它们的最大可供电量分别为 400 单位和 450 单位,单位费用如表 116 所示。由于需要量大于可供量,
8、决定城市 A 的供应量可减少 030 单位,城市 B 的供应-_量不变,城市 C 的供应量不能少于 270 单位。试建立线性规划模型,求将可供电量用完的最低总费用分配方案。表 116 单位电力输电费(单位:元)电站电站 城市城市ABCI151822II212516解:设为“第 i 电站向第 j 城市分配的电量” (i=1,2; j=1,2,3) ,建立模型如下:ijx232221131211162521221815maxxxxxxxZs.t. 3 , 2 , 1; 2 , 1, 0 35027025032029045040023132313221221112111232221131211jix
9、xxxxxxxxxxxxxxxxij9某公司在 3 年的计划期内,有 4 个建设项目可以投资:项目 I 从第一年到第三年年初都可以投资。预计每年年初投资,年末可收回本利 120%,每年又可以重新将所获本利纳入投资计划;项目 II 需要在第一年初投资,经过两年可收回本利 150%,又可以重新将所获本利纳入投资计划,但用于该项目的最大投资不得超过 20 万元;项目 III需要在第二年年初投资,经过两年可收回本利 160%,但用于该项目的最大投资不得超过 15 万元;项目 IV 需要在第三年年初投资,年末可收回本利 140%,但用于该项目的最大投资不得超过 10 万元。在这个计划期内,该公司第一年可
10、供投资的资金有 30 万元。问怎样的投资方案,才能使该公司在这个计划期获得最大利润?解:设表示第一次投资项目 i,设表示第二次投资项目 i,设表示第三)1( ix)2( ix)3( ix次投资项目 i, (i=1,2,3,4) ,则建立的线性规划模型为)1( 4)1( 3)3( 14 . 16 . 12 . 1maxxxxZ-_s.t. 4 , 3 , 2 , 1, 0,101520302 . 15 . 12 . 1302 . 130)3()2()1()1( 4)1( 3)1( 2)1( 3)2( 1)1( 2)1( 1)1( 1)1( 2)2( 1)1( 4)3( 1)1( 2)1( 1)1
11、( 1)1( 3)2( 1)1( 2)1( 1ixxxxxxxxxxxxxxxxxxxxxxiii通过 LINGO 软件计算得:44,12, 0,20,10)2( 1)2( 1)1( 3)1( 2)1( 1xxxxx10某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、上漆几道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具的利润由表 117 给出。问工厂应如何安排生产,使总利润最大?表 117 家具生产工艺耗时和利润表所需时间(小时)所需时间(小时) 生产工序生产工序 12345每道工序可用每道工序可用时间(小时)时间(小时)成型成型346233600打
12、磨打磨435643950上漆上漆233432800利润(百元)利润(百元)2.734.52.53解:设表示第 i 种规格的家具的生产量(i=1,2,5) ,则ix5432135 . 25 . 437 . 2maxxxxxxZs.t. 5 , 2 , 1, 0280034332395046534360032643543215432154321ixxxxxxxxxxxxxxxxi通过 LINGO 软件计算得:3181,642, 0,254,38, 054321Zxxxxx11某厂生产甲、乙、丙三种产品,分别经过 A,B,C 三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产
13、品的利润如表 210 所示。表 118 产品生产工艺消耗系数甲甲乙乙丙丙设备能力设备能力A(小时)(小时)111100-_B(小时)(小时)1045600C(小时)(小时)226300单位产品利润(元)单位产品利润(元) 1064(1)建立线性规划模型,求该厂获利最大的生产计划。(2)产品丙每件的利润增加到多大时才值得安排生产?如产品丙每件的利润增加到 6,求最优生产计划。(3)产品甲的利润在多大范围内变化时,原最优计划保持不变?(4)设备 A 的能力如为 100+10q,确定保持原最优基不变的 q 的变化范围。(5)如合同规定该厂至少生产 10 件产品丙,试确定最优计划的变化。解:(1)设分
14、别表示甲、乙、丙产品的生产量,建立线性规划模型321,xxx3214610maxxxxZs.t. 0,3006226005410100321321321321xxxxxxxxxxxx标准化得6543210004610maxxxxxxxZs.t. 0,3006226005410100654321632153214321xxxxxxxxxxxxxxxxxx列出单纯形表jc1064000BCBXb1x2x3x4x5x6xi04x10011110010005x60010450106006x300226001150j106400004x4003/51/211/100200/3-_101x6012/51/
15、201/10015006x18006/5501/51150j02101062x200/3015/65/31/60101x100/3101/62/31/6006x100004201j008/310/32/30故最优解为,又由于取整数,故四舍五入可0, 3/200, 3/100321xxx321,xxx得最优解为,0,67,33321xxx732maxZ(2)产品丙的利润变化的单纯形法迭代表如下:3cjc1063c000BCBXb1x2x3x4x5x6xi62x200/3015/65/31/60101x100/3101/62/31/6006x100004201j0020/33c10/32/30要使
16、原最优计划保持不变,只要,即故当产品丙032033 c67. 63263c每件的利润增加到大于 6.67 时,才值得安排生产。如产品丙每件的利润增加到 6 时,此时 66.67,故原最优计划不变。(3)由最末单纯形表计算出,0611, 03210, 0611151413ccc解得,即当产品甲的利润在范围内变化时,原最优计划保持不1561 c1c15, 6变。(4)由最末单纯形表找出最优基的逆为,新的最优解为 10206/13/206/13/51B-_0)20100(32010050200313006001010010206/13/206/13/51 qqqq bBXB解得,故要保持原最优基不变
17、的 q 的变化范围为54q5 , 4(5)如合同规定该厂至少生产 10 件产品丙,则线性规划模型变成3214610maxxxxZs.t. 0,1030062260054101003213321321321xxxxxxxxxxxxx通过 LINGO 软件计算得到:708,10,58,32321Zxxx第第 2 2 章章 对偶规划(复习思考题)对偶规划(复习思考题)1对偶问题和对偶向量(即影子价值)的经济意义是什么?答:原问题和对偶问题从不同的角度来分析同一个问题,前者从产品产量的角度来考察利润,后者则从形成产品本身所需要的各种资源的角度来考察利润,即利润是产品生产带来的,同时又是资源消耗带来的。
18、对偶变量的值表示第 i 种资源的边际价值,称为影子价值。可以把对偶问题的iy解 Y 定义为每增加一个单位的资源引起的目标函数值的增量。 2什么是资源的影子价格?它与相应的市场价格有什么区别?答:若以产值为目标,则是增加单位资源 i 对产值的贡献,称为资源的影子价iy格(Shadow Price) 。即有“影子价格=资源成本+影子利润” 。因为它并不是资源的实际价格,而是企业内部资源的配比价格,是由企业内部资源的配置状况来决定的,并不是由市场来决定,所以叫影子价格。可以将资源的市场价格与影子价格进行比较,当市场价格小于影子价格时,企业可以购进相应资源,储备或者投入生产;当市场价格大于影子价格时,
19、企业可以考虑暂不购进资源,减少不必要的损失。-_3如何根据原问题和对偶问题之间的对应关系,找出两个问题变量之间、解及检验数之间的关系?答:(1)最优性定理:设分别为原问题和对偶问题的可行解,且,YX,YbXCT则分别为各自的最优解。YX,(2)对偶性定理:若原问题有最优解,那么对偶问题也有最优解,而且两者的目标函数值相等。(3)互补松弛性:原问题和对偶问题的松弛变量为和,它们的可行解SXSY为最优解的充分必要条件是*,YX0, 0*XYXYSS(4)对偶问题的最优解对应于原问题最优单纯形表中,初始基变量的检验数的负值。若对应于原问题决策变量 x 的检验数,则对应于原问题松弛变量的检验SYYSx
20、数。4已知线性规划问题32124maxxxxZs.t. 0,86238321321321xxxxxxxxx (第二种资源)(第一种资源)(1)求出该问题产值最大的最优解和最优值。(2)求出该问题的对偶问题的最优解和最优值。(3)给出两种资源的影子价格,并说明其经济含义;第一种资源限量由 2 变为4,最优解是否改变?(4)代加工产品丁,每单位产品需消耗第一种资源 2 单位,消耗第二种资源 3 单位,应该如何定价?解:(1)标准化,并列出初始单纯形表jc41200BCBXb1x2x3x4x5xi-_04x2831102/805x8611018/6j4120041x1/413/81/81/80205
21、x13/265/41/43/4126j01/23/2-1/2023x28311005x622011j125020由最末单纯性表可知,该问题的最优解为:,即TX)6 , 0 , 2 , 0 , 0(*,最优值为2, 0, 0321xxx4Z(2)由原问题的最末单纯形表可知,对偶问题的最优解和最优值为:4, 0, 221wyy(3)两种资源的影子价格分别为 2、0,表示对产值贡献的大小;第一种资源限量由 2 变为 4,最优解不会改变。(4)代加工产品丁的价格不低于430225某厂生产 A,B,C,D4 种产品,有关资料如表 26 所示。表 26产品产品资源消耗资源消耗资源资源 ABCD资源供应量资
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 治理 运筹学 第二 课后 习题 参考答案
限制150内