熊伟运筹学第第二课后习题答案.pdf

目录 教材习题答案 错误！未定义书签。 习题一 1 习题二 3 习题三 3 习题四 3 习题五 错误！未定义书签。 习题六 错误！未定义书签。 习题七 错误！未定义书签。 习题八 错误！未定义书签。 部分有图形的答案附在各章PPT文档的后面，请留意。 习题一 1.1 讨论下列问题： （1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5 台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型 怎样变化 （2）在例1.2中，如果设xj(j=1，2，7)为工作了5天后星期一到星期 日开始休息的营业员，该模型如何变化 （3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学 模型如何变化；简述板材下料的思路 （4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1，模型 如何变化 （5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要 求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小 时，模型如何变化 1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台 时的消耗量、资源限量及单件产品利润如表122所示 表122 产品 资源 ABC资源限量 材料(kg)1.51.242500 设备(台时)31.61.21400 利润(元/件)101412 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月 需求是250、310和130.试建立该问题的数学模型,使每月利润最大 【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为 1.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架两种窗 架所需材料规格及数量如表123所示： 表123 窗架所需材料规格及数量 型号A型号B 每套窗架 需要材料 长度 （m） 数量(根) 长度 (m) 数量 (根) A1： 1.7 2 B1：2.7 2 A2： 1.3 3 B1：2.0 3 需要量（套） 200150 问怎样下料使得（1）用料最少；（2）余料最少 【解】 第一步：求下料方案，见下表。 方案一 二 三 四 五 六 七 八 九 十 十 一 十 二 十 三 十 四 需 要 量 B1:2.7m 2 1 11 0 000 0 00 0 00300 B2:2m0 1 00 3 221 1 10 0 00450 A1:1.7m 0 0 10 0 102 1 03 2 10400 A2:1.3m 0 1 12 0 010 1 30 2 34600 余料0.6 0 0.30.7 0 0.30.70.6 1 0.10.9 0 0.40.8 第二步：建立线性规划数学模型 设xj（j=1,2,，14）为第j种方案使用原材料的根数，则 （1）用料最少数学模型为 用单纯形法求解得到两个基本最优解 X(1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X(2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为 用单纯形法求解得到两个基本最优解 X(1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 1.4 A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A 需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2 小时和后道工序3小时可供利用的前道工序有11小时，后道工序有17 小时 每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要 任何费用，产品C一部分可出售赢利，其余的只能加以销毁 出售单位产品A、B、C的利润分别为3、7、2元，每单位产品C的销毁费 为1元预测表明，产品C最多只能售出13个单位试建立总利润最大的 生产计划数学模型 解】设x1,x2分别为产品A、B的产量，x3为副产品C的销售量,x4为副产品 C的销毁量，有x3+x4=2x2,Z为总利润，则数学模型为 1.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计 利息）可供投资： 方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率 是20，下一年可继续将本息投入获利； 方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率 是50，下一年可继续将本息投入获利，这种投资最多不超过2万元； 方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率 是60，这种投资最多不超过1.5万元； 方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益 率是30，这种投资最多不超过1万元 投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型. 【解】是设xij为第i年投入第j项目的资金数，变量表如下 项目 一 项目 二 项目 三 项目 四 第1 年 第2 年 第3 年 x11 x21 x31 x12 x23 x34 数学模型为 最优解X=(30000，0，66000，0，109200，0)；Z84720 1.6 IV发展公司是商务房地产开发项目的投资商公司有机会在三个建 设项目中投资：高层办公楼、宾馆及购物中心，各项目不同年份所需资 金和净现值见表124三个项目的投资方案是：投资公司现在预付项 目所需资金的百分比数，那么以后三年每年必须按此比例追加项目所需 资金，也获得同样比例的净现值例如，公司按10投资项目1，现在 必须支付400万，今后三年分别投入600万、900万和100万，获得净现值 450万 公司目前和预计今后三年可用于三个项目的投资金额是：现有2500万， 一年后2000万，两年后2000万，三年后1500万当年没有用完的资金可 以转入下一年继续使用 IV公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分 比，使其投资获得的净现值最大 表124 年份 10项目所需资金（万 元） 项目1项目2项目3 0400800900 1600800500 2900800200 3100700600 净现值450700500 【解】以1为单位，计算累计投资比例和可用累计投资额，见表 （2）。 表（2） 年份 每种活动单位资源使用量（每个百分点投资的 累计数） 项目1项目2项目3累计可用资 金(万元) 04080902500 11001601404500 21902401606500 32003102208000 净现 值 457050 设xj为j项目投资比例，则数学模型： 最优解X（0，16.5049，13.1067）；Z=1810.68万元 年份 实际投资 项目1比 例：0 项目2比 例： 16.5049 项目3比 例： 13.1067 累计投资(万 元) 001320.3921179.6032499.995 102640.7841834.9384475.722 203961.1762097.0726058.248 305116.5192883.4747999.993 净现值01155.343655.335 1.7 图解下列线性规划并指出解的形式： (1) 【解】最优解X（1/2，1/2）；最优值Z=1/2 (2) 【解】最优解X（3/4，7/2）；最优值Z=45/4 (3) 【解】最优解X（4，1）；最优值Z=10 (4) 【解】最优解X（3/2，1/4）；最优值Z=7/4 (5) 【解】最优解X（3，0）；最优值Z=3 (6) 【解】无界解。 (7) 【解】无可行解。 (8) 【解】最优解X（2，4）；最优值Z=13 1.8 将下列线性规划化为标准形式 (1) 【解】（1）令为松驰变量 ，则标准形式为 (2) 【解】（2）将绝对值化为两个不等式，则标准形式为 (3) 【解】方法1： 方法2：令 则标准型为 (4) 【解】令，线性规划模型变为 标准型为 1.9 设线性规划 取基分别指出对应的基变量和非基变量，求出基本解，并说明是不是可 行基 【解】B1：x1，x3为基变量，x2，x4为非基变量,基本解为X=（15，0， 20，0）T，B1是可行基。B2：x1,x4是基变量，x2,x3为非基变量，基本解 X=（25，0，0，40）T，B2不是可行基。 1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的 每一步的基可行解对应于图形上的那一个极点 (1) 【解】图解法 单纯形法： C(j)1300b Ratio C(i) Basis X1X2X3X4 0X3-211022 0X42301124 C(j)-Z(j)13000 3X2-21102M 0X480-3160.75 C(j)-Z(j)70-306 3X2010.250.257/2 1X110-0.3750.1253/4 C(j)-Z(j)00-0.375 -0.87511.25 对应的顶点： 基可行解可行域的顶点 X(1)=（0，0，2，12）、 X(2)=（0，2，0，6，）、 X(3)=（、 （0，0） （0，2） 最优解 (2) 【解】图解法 单纯形法： C(j)-3-5000 b Ratio Basis C(i) X1X2X3X4X5 X301210063 X4014010102.5 X501100144 C(j)-Z(j)-3-50000 X300.501-0.5012 X2-50.25100.2502.510 X500.7500-0.2511.52 C(j)-Z(j)-1.75001.250-12.5 X1-3102-102M X2-501-0.50.5024 X5000-1.50.5100 C(j)-Z(j)003.5-0.50-16 X1-310-1022 X2-50110-12 X4000-3120 C(j)-Z(j)00201-16 对应的顶点： 基可行解可行域的顶点 X(1)=（0，0，6，10，4）、 X(2)=（0，2.5，1，0， 1.5，）、 X(3)=（2，2，0，0，0） X(4)=（2，2，0，0，0） （0，0） （0，2.5） (2，2) （2，2） 最优解：X=（2，2，0，0，0）；最优值Z16 该题是退化基本可行解，5个基本可行解对应4个极点。 1.11用单纯形法求解下列线性规划 (1) 【解】单纯形表： C(j)34100R. H. S. Ratio BasisC(i)X1X2X3X4X5 X402311011/3 X501220133/2 C(j)-Z(j)341000 X242/311/31/301/31/2 X50-1/304/3-2/317/3M C(j)-Z(j)1/30-1/3-4/30-4/3 X1313/21/21/201/2 X5001/23/2-1/215/2 C(j)-Z(j)0-1/2-1/2-3/20-3/2 最优解：X=（1/2，0，0，0，5/2）；最优值Z3/2 (2) 【解】单纯形表： C(j)21-35000 R. H. S.Ratio BasisC(i)X1X2X3 X4 X5X6X7 X50153-710030M X603-1110101010 X702-6-14001205 C(j)-Z(j)21-35000 X509/2-11/2 5/40107/465M X60 5/2 1/2 5/4 0 01 -1/4510 X451/2-3/2 -1/41001/45M C(j)-Z(j)-1/217/2 -7/4 000-5/4 X50320150111-1120M X21515/2 002-1/21010 X45807/2 103-1/220M C(j)-Z(j)-430-2300-173 因为730并且ai70,原问题无可行解。 两阶段法 第一阶段：数学模型为 C(j)000001 R. H. S. Ratio Basis C(i) X1X2X4X5 X6X7 X4053100091.8 X50-56010015M X712100-1152.5 C(j)-Z(j)-2-10010514 X1013/51/50009/5 X5009110024 X710-1/5-2/50-117/5 C(j)-Z(j)01/52/5010 因为X70,原问题无可行解。图解法如下： (4) 【解】大M法。数学模型为 C(j)23-11 -M-M-MR.H.S. Ratio Basis C(i)X1X2X3X4X5X6X7X8X9X10X11 X9-M1-121-1 1 94.5 X6 21-1 1 55 X10 -M2-13-1 -1 1 10.3333 X11 -M1 1 -1 133 C(j)-Z(j)23-11 * Big M4-26 -1 -1-1 X9-M-1/3-1/3 1.67-1 2/3 1-2/3 8.335 X6 -2/32.33 -2/3 11/3 -1/3 4.67M X3-12/3-1/31-1/3 -1/3 1/3 1/3M X11 -M1/31/3 1/3 1/3-1 -1/312.678 C(j)-Z(j)2.672.67 2/3 -1/3 1/3 -1/3 * Big M 2-1 1-1 -2 X41-1/5-1/5 1-3/5 0.4 3/5-0.4 5M X6 -0.82.2 -0.413/5 0.4-3/5 83.6364 X3-13/5-0.41 -1/5 -1/5 1/51/5 2M X11 -M0.40.4 1/5 1/5-1-1/5-1/5112.5 C(j)-Z(j)2.82.8 0.4 -3/5 -0.43/5 3 * Big M0.40.4 1/5 1/5-1-1.2-1.2 X41 1-0.5 0.5-0.50.5-0.50.55.5M X6 -3 -1.51-0.55.51.50.5-5.52.50.4545 X3-11 1 -1 13M X2311 0.5 0.5-2.5-0.5-0.52.52.5M C(j)-Z(j) -1 -2712-710 * Big M -1-1-1 X41-0.27 1.00 -0.64 0.090.45 0.64 -0.45 5.73M X8 -0.55 -0.27 0.18 -0.09 1.000.270.09 -1.000.45M X3-1 0.45 1.00 -0.27 0.18 -0.09 0.270.09 3.457.6 X23-0.36 1.00 -0.18 0.450.27 0.18 -0.27 3.64M C(j)-Z(j)3.82 0.91 -1.27 -1.36 -0.91 1.36 13.18 * Big M -1-1-1 X41 3/51-0.81/50.4 0.8-0.4 7.8M X8 1.2 -3/50.4-1/513/51/5-14.6M X121 2.2 -3/50.4-1/5 3/51/5 7.6M X23 10.8 -0.43/51/5 0.4-1/5 6.4M C(j)-Z(j) -8.4 3.2-2.8-3/5 -3.23/5 42.2 * Big M -1-1-1 无界解。 两阶段法。第一阶段： C(j) 111R.H.S. Ratio Basis C(i)X1X2X3X4X5X6X7X8X9X10X11 X911-121-1 1 99/2 X6 21-1 1 55 X1012-13-1 -1 1 11/3 X1111 1 -1 133 C(j)-Z(j)-42-6 1 11 13 X91-1/3-1/3 5/3-1 2/3 1-2/3 25/35 X6 -2/37/3 -2/3 11/3 -1/3 14/3M X3 2/3-1/31-1/3 -1/3 1/3 1/3M X1111/31/3 1/3 1/3-1 -1/318/38 C(j)-Z(j) -21 -11 2 11 X4 -1/5-1/5 1-3/5 2/5 3/5-2/5 5M X6 -4/511/5 -2/513/5 2/5-3/5 840/11 X3 3/5-2/51 -1/5 -1/5 1/51/5 2M X1112/52/5 1/5 1/5-1-1/5-1/5115/2 C(j)-Z(j)-2/5-2/5 -1/5 -1/516/56/5 1 X4 1-1/2 1/2-1/21/2-1/21/211/2M X6 -3 -3/21-1/211/23/21/2-11/25/25/11 X3 1 1 -1 13M X2 11 1/2 1/2-5/2-1/2-1/25/25/2M C(j)-Z(j) 111 第二阶段： C(j)23-11 R.H.S. Ratio Basis C(i)X1X2X3X4X5X6X7X8 X41 1-1/2 1/2-1/211/2M X6 -3 -3/21-1/2 11/25/25/11 X3-11 1 -13M X2311 1/2 1/2-5/25/2M C(j)-Z(j) -1 -2710 X41-3/11 1-7/111/115/11 63/11M X8 -6/11 -3/112/11-1/1115/11M X3-15/11 1 -3/112/11-1/11 38/11 38/5 X23-4/111 -2/115/113/11 40/11M C(j)-Z(j)42/11 1-14/11-15/11 13.18 X41 3/51-4/51/52/5 39/5M X8 6/5 -3/52/5-1/5123/5M X121 11/5 -3/52/5-1/5 38/5M X23 14/5 -2/53/51/5 32/5M C(j)-Z(j) -42/5 16/5-14/5-3/5 42.2 原问题无界解。 1.13 在第1.9题中，对于基求所有变量的检验数,并判断B是不是最优基 【解】, B不是最优基，可以证明B是可行基。 1.14已知线性规划 的最优基为，试用矩阵公式求（1）最优解；(2)单纯形乘子；(3)(4) 【解】 则 (1) (2) (3) (4) 注：该题有多重解： X(1)=(0，5，0，5/2) X(2)=(0，10/3，10/3，0) X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解 Z50 1.15 已知某线性规划的单纯形表125, 求价值系数向量C及目标函数 值Z 表125 Cjc1c2c3c4c5c6c7b CBXBx1x2x3x4x5x6x7 3x401213024 4x110102010 0x60 1 404123/2 010102 j1 【解】由有 c21（31400（1）2 c31（324（1）04）1 c51（3（3）420（4）0 则(4,2,1,3,0,0,0,)，Z=CBXB=12 1.16 已知线性规划 的最优单纯形表如表126所示，求原线性规划矩阵C、A、及b，最优 基B及 表126 Cjc1c2c3c4c5b CBXBx1x2x3x4x5 c1x11041/61/156 c2x201301/52 j00123 【解】，c4c50， 仿照第15题方法可求出c112，c211，c314 由 得 由 得 则有 ， 1.17 已知线性规划的单纯形表127 表127 Cj3a11b CBXBx1x2x3x4 1x32210b1 1x43101b2 j1234 当=（ ）,=（ ）,a=（ ）时，为唯一最优解. 当=（ ）,=（ ）,a=（ ）时，有多重解，此时（ ） 【解】(1)b10,b20,a6时X1出基X4进基得到下表： C(j)35000R.H.S. BasisC(i)X1X2X3X4X5 X40-3001-1-12+2 X253/21001/29- X30101004+ C(j)-Z(j) 9时最优解X=(0，0，13，6，0)，Z=0；9时无可行解。 综合分析如下表所示。 FromToFromToLeaving Entering Range(Vector)(Vector) OBJ Value OBJ Value SlopeVariable Variable 10027273X5X3 2062715-2X1X2 369150-5X2 49Infinity Infeasible 50-427153X1 6-4-InfinityInfeasible 目标值变化如下图所示。 习题三 1设 最优解X(1,1,1,0,1)，Z=110万元。 2设xj为投资第j个点的状态，xj=1或0，j=1,2,12 最优解：x1x5=x12=0，其余xj=1,总收益Z=3870万元，实际完成投资 额8920万元。 3设xj为装载第j件货物的状态，xj=1表示装载第j件货物，xj=0表示不装 载第j件货物，有 4设xij（i=1，2，5；j1，2，3，4）为第i人参赛j项目的状态， 即 记第i人参赛j项目的成绩为Cij,，目标函数 每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条 件： 每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条 件： xij1或0，i=1，2，5；j1，2，3，4 5. 6 7(1)X=(1,2),Z=3 (2) X=(5,0),Z=5 8(1)X=(3,3),Z=15 (2)X=(5,2),Z=16 9教材原题遗漏，请补上。 （1） （2） 答案：(1)X=(1,1,1),Z=8 (2)X=(1,1,1,0),Z=4 10(1)X=(1,0,1,1),Z=8 (2)X=(1,1,0,0,0),Z=2 习题四 4.1 工厂生产甲、乙两种产品，由、二组人员来生产。组人员熟 练工人比较多，工作效率高，成本也高；组人员新手较多工作效率比 较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本 是50元有关资料如表4.21所示。 表4.21 产品甲产品乙 效率(件/小 时) 成本(元/ 件) 效率(件/小 时) 成本(元/ 件) A组1050845 B组845540 产品售价 (元/件) 8075 二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以 加班10小时，加班生产的产品每件增加成本5元。 工厂根据市场需求、利润及生产能力确定了下列目标顺序： P1：每周供应市场甲产品400件，乙产品300件 P2：每周利润指标不低于500元 P3：两组都尽可能少加班，如必须加班由组优先加班 建立此生产计划的数学模型。 4.1【解】 解法一：设x1, x2分别为A组一周内正常时间生产产品甲、乙 的产量，x3, x4分别为A组一周内加班时间生产产品甲、乙的产量；x5, x6 分别为B组一周内正常时间生产产品甲、乙的产量，x7, x8分别为B组一 周内加班时间生产产品甲、乙的产量。 总利润为 生产时间为 A组： B组： 数学模型为： 解法二：设x1, x2分别为A组一周内生产产品甲、乙的正常时间，x3, x4分 别为A组一周内生产产品甲、乙的加班时间；x5, x6分别为B组一周内生 产产品甲、乙的正常时间，x7, x8分别为B组一周内生产产品甲、乙的加