《管理运筹学》茹少峰课后答案.pdf

1用图解法求解两个变量线性规划问题的最优解和最优值。 0, 1535 62 st. 32max 21 21 21 21 xx xx xx xxz 1 x 2 x 最优解12/715/7 最优值69/7 2用图解法求解以下线性规划问题并指出哪个问题有惟一解、无穷多最优解、无界 解或无可行解 0, 343 12 st. 46min 21 21 21 21 xx xx xx xxz 最优解1/5,3/5 最优值 3.6 11/2 0 3/4 1 1 x 2 x 0, 8 1022 st. 84max 21 21 21 21 xx xx xx xxz 1 x 2 x 无可行解 3某公司从中心制造地点向分别位于城区北、东、南、西方向的分配点运送材料。该 公司有 26 辆卡车用于从制造地点向分配点运送材料。其中有 9 辆每辆能装 5 吨的大型 卡车12 辆每辆能装 2 吨的中型卡车和 5 辆每辆能装 1 吨的小型卡车。北、东、南、西四 个点分别需要材料 14 吨、10 吨、20 吨、8 吨。每辆卡车向各分配点送材料一次的费用如表 2-7 所示。建立运送材料总费用最小的线性规划模型。 表 2-7 车辆运送一次的费用 北 东 南 西 大 80 63 92 75 中 50 60 55 42 小 20 15 38 22 解 设大、中、小型车分别用i表示则 3,2,1i 东、南、西、北四个分点分别用 j 表 示则 4,3,2,1j 向 j 方向发出的i型车数量为 ij x 。 34333231 2423222114131211 22381520 4255605075926380min xxxx xxxxxxxxZ 4,3,2,1,0 5 12 9 825 2025 1025 1425 . 34333231 24232221 14131211 342414 332313 322212 312111 jix xxxx xxxx xxxx xxx xxx xxx xxx st ij 4某工厂生产 A、B、C 三种产品现根据合同及生产状况制定 5 月份的生产计划。 已知合同甲为A 产品 1000 件每件价格为 500 元违约金为 100 元/每件合同乙B 产 品 500 件每件价格为 400 元违约金为 120 元/每件合同丙为B 产品 600 件每件价 格为 420 元违约金为 130 元/每件C 产品 600 件价格 400 元/每件违约金为 90 元/每 件。有关各产品生产过程所需工时以及原材料的情况如表 2-8 所示。试以利润为目标建立该 工厂生产计划的线性规划模型。 表 2-8 产品使用的原材料、加工工序、资源限制、成本 产品 A 产品 B 产品 C 资源限制 工时或原材料成本 工序 1 2 1 2 4600 15 工序 2 3 1 1 4000 10 工序 3 2 3 2 6000 10 原料 1 3 2 4 10000 20 原料 2 4 3 2 8000 40 其他成本 10 10 10 解 设工厂 5 月份为完成合同甲生产 1 x 件 A 产品为完成合同乙生产 2 x 件 B 产品为 完成合同丙生产 3 x 件 B 产品 4 x 件 C 产品。 292000260325295290 )10402 20420210152()()104032201031015( )10404203102103152(90)600(400130 )600(420120)500(400)1000(500max 4321 4 32 144 332211 xxxx x xx xxx xxxxxxZ ,6000 ,6000 ,5000 ,10000 80002)(34 100004)(23 60002332 400023 460022 . 4 3 2 1 4321 4321 4321 4321 4321 x x x x xxxx xxxx xxxx xxxx xxxx st 5某公司从事某种商品的经营现欲制定本年度 10 至 12 月的进货及销售计划。 已知该种商品的初始库存量为 2000 件公司仓库最多可存放 10000 件公司拥有的经 营资金 80 万元据预测10 至 12 月的进货及销售价格如表 2-9 所示。若每个月仅在 1 号进货 1 次且要求年底时商品存量达到 3000 件在以上条件下建立该问题的线性 规划模型使公司获得最大利润注不考虑库存费用 表 2-9 进货和销售价格 月份 10 11 12 进货价格/元/件 90 95 98 销售价格/元/件 100 100 115 解 12,11,10,ix i 为每月购进的货物 12,11,10,iy i 为每月销售的货物。 12,11,10,0 12,11,10,0 30002000 2000 2000 2000 100002000 100002000 100002000 80000989590 . 989590115100100max 121110101112 111010111212 10101111 1010 1110101112 101011 10 121110 121110121110 iy ix yyyxxx yyxxxy yxxy xy yyxxx yxx x xxx st xxxyyyZ i i 年底存量限制 销量限制 销量限制 销量限制 库容限制 库容限制 库容限制 资金限制 6某饲养场饲养动物出售设每头动物每天至少需 700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用各种饲料每公斤营养成分含量单价如表 2-10 所示。 表 2-10 饲料所含的营养成分及价格 饲料 蛋白质/g 矿物质/g 维生素/g 价格/元 1 kg 1 3 1 0.5 0.2 2 2 0.5 1.0 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 求这个问题的规划模型使既满足动物生长的需要又使费用最小的选用饲料的方案。 解 设各送这 5 钟饲料 1 x 2 x 3 x 4 x 5 x kg。 5,4,3,2,1, 1008.022.05.0 305.022.05.0 70018623 . 8.03.04.07.02.0min 54321 54321 54321 54321 ix xxxxx xxxxx xxxxx st xxxxxZ i 7某一企业家需要找人清理 5 间会议室、12 张桌子和 18 个货架。今有两个临时工 A 和 B 可供该企业家雇佣。A 一天可清理 1 间会议室、3 张桌子与 3 个货架而 B 一天可清 理 1 间会议室、2 张桌子与 6 个货架。A 的工资每天 25 元B 每天 22 元。为了使成本最低 应雇佣 A 和 B 各多少天用线性规划图解法求解 解设雇佣 A 和 B 分别为 yx , 天 为整数且yxyx yx yx yx st yxZ ,0; 1863 1223 5 . 2225min 0 4 56 3 5 6 x y A 3x+2y=12 x+y=5 3x+6y=18 由图知 A 点为最优解联立方程 5 1223 yx yx 解得 x=2, y 3,即 Zmin=25x+22 y =252+223=116 因此雇佣 A 工人 2 天B 工人 3 天。 8 某外贸公司专门经营某种杂粮的批发业务。 公司现有库容 5000 担的仓库。 1 月 1 日 公司拥有库存 1000 担杂粮并有资金 20000 元。估计第一季度杂粮价格如表 2-11 所示。 表 2-11 第一季度杂粮价格表 进货价/元 出货价/元 1 月 2.85 3.10 2 月 3.05 3.25 3 月 2.90 2.95 如果买进的杂粮当月到货但需到下月才能卖出且规定货到付款。公司希望本季度 末库存为 2000 担建立该问题的线性规划模型使三个月总的获利最大。 解 设一月份买入 1 x 担卖出 1 x 担二月份买入 2 x 担卖出 2 x 担三月份买入 3 x 担 卖出 3 x 担。 3,2,1,0;3,2,1,0 20001000 25.310.385.22000090.2 50001000 10.385.22000005.3 50001000 2000085.2 . 90.295.205.325.385.210.3max 3 32 21 1 2 113 2 21 1 112 1 1 1 3 32 21 1 jxix xxxxxx xxxx xxxx xxx xx x st xxxxxxZ ji 1求下列线性规划问题的所有基解、基可行解、最优解 0, 642 2 st. 33max 321 321 321 321 xxx xxx xxx xxxz 解由题意知A= 111 124 = 1 ,2 ,3 ppp b= 2 6 c=313 1 1 B = 1 ,2 pp 1 B 0 1 B 是基 1 x 2 x 是基变量 3 x 是非基变量令 3 x =0得 1 x =-2 2 x =4 即 1 2 3 x x x = 2 , 4 , 0 为基解但不是基本可行解。 2 2 B = 1 ,3 pp 2 B 0 2 B 是基 1 x 3 x 是基变量 2 x 是非基变量。令 2 x =0得 1 x =2/3 3 x =3/4即 1 2 3 x x x = 3 4 3 2 0 为基解同时为基本可行解 zmax=(2/3)*3+0+4/3*3=6。 3 32 ,3 ()Bpp 3 B 0 3 B 是基 2 x 3 x 是基变量 1 x 是非基变量令 1 x =0得 2 x =1 3 x =1即 1 2 3 x x x = 1 1 0 为基解同时为基本可行解 zmax=1+3=4。 综上所述基解为 1 2 3 x x x = 0 4 2 1 2 3 x x x = 3 4 3 2 0 1 2 3 x x x = 1 1 0 其中第二个和第三个 为基本可行解 1 2 3 x x x = 3 4 3 2 0 为最优解。 2分别用图解法和单纯形法求解下列线形规划问题并指出单纯形法迭代的每一步相 当于图形上哪一个顶点 0, 2 1 st. 32max 21 1 21 21 xx x xx xxz 解1图解法 o 1 x 2 x A 2 1 x B 1 21 xx 有图解法知线性规划模型的可行域如阴影部分所示令z=012时max z逐渐增大可行域是无界的所以此模型是无界解。 2单纯形法 化为标准型为 1234 123 14 123 ,4 m a x2300 1 2 s t. ,0 zxxxx xxx xx xxxx A= 1110 1001 2 1 b C=2300 B c B x 2 1 x 3 2 x 0 3 x 0 4 x b 0 3 x 1 -1 1 0 1 0 4 x 1 0 0 1 2 2 3 0 0 对应图中原点。以 1为轴心项换基迭代得 B c B x 2 1 x 3 2 x 0 3 x 0 4 x b 2 1 x 1 -1 1 0 1 0 4 x 0 1 -1 1 1 0 5 -2 0 -2 此时对应图中 A 点坐标是 10 以 1为轴心项换基迭代得 B c B x 2 1 x 3 2 x 0 3 x 0 4 x b 2 1 x 1 0 0 1 2 3 2 x 0 1 -1 1 1 0 0 3 5 -7 此时对应图中 B 点坐标是 23因为 3 =50,同时 3 x 对应的列小于等于 0则 原模型有无界解。 0, 1823 122 4 st. 52max 21 21 2 1 21 xx xx x x xxz 解 1图解法 可行域如上图阴影部分所示令 z=012做等值线得出在 c 点取最大值c 点 坐标为26 max z=34 2单纯形法化为标准型为 12345 13 24 125 m a x25000 4 21 2 s t. 321 8 0 ,1, 2 5 j zxxxxx xx xx xxx xj 10100 02010 32001 A = 1 ,2345 ,ppppp b= 4 1 2 8 C=25000 取 B= 345 ,ppp 为可行基 B C =000 单纯性表如下 B c B x 2 1 x 5 2 x 0 3 x 0 4 x 0 5 x b 0 3 x 1 0 1 0 0 4 0 4 x 0 2 0 1 0 12 0 5 x 3 2 0 0 1 18 2 5 0 0 0 此时对应图中 O 点坐标为00 以 1为轴心项换基迭代得 B c B x 2 1 x 5 2 x 0 3 x 0 4 x 0 5 x b 2 1 x 1 0 1 0 0 4 0 4 x 0 2 0 1 0 12 0 5 x 0 2 -3 0 1 6 0 5 -2 0 0 -8 此时对应图中 A 点坐标为40 以 2为轴心项换基迭代得 B c B x 2 1 x 5 2 x 0 3 x 0 4 x 0 5 x b 2 1 x 1 0 1 0 0 4 0 4 x 0 0 3 1 -1 6 5 2 x 0 1 -3/2 0 1/2 3 0 0 11/2 0 -2/5 -23 此时对应图中 B 点坐标为43 以 3为轴心项换基迭代得 B c B x 2 1 x 5 2 x 0 3 x 0 4 x 0 5 x b 2 1 x 1 0 0 -1/3 1/3 2 0 3 x 0 0 1 1/3 -1/3 2 5 2 x 0 1 0 1/2 0 6 0 0 0 -11/6 -2/3 -34 由于 基 =0非 基0 且 1 H 0 且 2 H 0, 即 0 1 H 0 时 此解不是最优解。 10表 3-20 是求某极大化线性规划问题计算得到的单纯形表。表中无人工变量 1 a 、 2 a 、 3 a 、d、 1 c 、 2 c 为待定常数。试说明这些常数分别取何值时以下结论成立。 表 3-20 极大化线性规划问题计算得到的单纯形表 B X 1 x 2 x 3 x 4 x 5 x 6 x b 3 x 4 x 6 x 4 1 a 1 0 2 a 0 d -1 -3 0 1 -1 0 2 3 a -5 0 0 -4 1 3 jj zc 1 c 2 c 0 0 -3 0 表中解为惟一最优解 表中解为最优解但存在无穷多最优解 该线性规划问题具有无界解 表中解非最优为对解改进换入变量为 1 x 换出变量为 6 x 解 1当 d0 1 c 1 2 d 表中解非最优为对解改进换入变量为 1 x 换出变 量为 6 x 。 第四节 1写出线性规划问题的对偶问题。 0, 734 1552 st. 5310max 321 31 321 321 xxx xx xxx xxxz 0,0 8374 35 522 st. 365max 321 321 321 321 321 xxx xxx xxx xxx xxxz 无约束 0,0, 05732 84 6253 st. 2423min 421 54321 532 5421 5321 xxx xxxxx xxx xxxx xxxxz ),2,1;,2,1( 0 ),2,1( ),2,1( st. min 1 1 11 minjx njbx miax xcz ij m i jij n j iij m i n j ijij 解 1 2 0, 53 35 104y2 st. 715min 21 21 1 21 21 yy yy y y yy 0,0, 332 6752 54y st. 835min 321 321 321 321 3 21 yyy yyy yyy yy yyy 无约束 3 无约束 321 321 32 321 31 3 21 ,0,0 252 074 235 323y st. 086max yyy yyy yy yyy y yyy 4 无约束njmij i m i i n j ji m i n j jjii uv cuv ubva ,2,1;,2,1 1 j 1 11 , st. max 2判断下列说法是否正确并说明理由。 1如果线性规划的原问题存在可行解则其对偶问题也一定存在可行解 2如果线性规划的对偶问题无可行解则其原问题也一定无可行解 3在互为对偶问题的一对原问题与对偶问题中不管原问题是求最大或最小原问 题可行解的目标函数值一定不超过其对偶问题的可行解的目标函数值 4任何线性规划问题具有唯一的对偶问题 解 1不正确。因为当原模型存在可行解且目标函数值无界时其对偶模型无可行解。 2不正确。因为对偶模型无可行解其原模型可能存在可行解且目标函数值无界。 3不正确。当原模型求最小值时原模型的目标函数值可能超过对偶模型的目标函 数值。 4正确。对偶模型具有对称性。 3用计算机求解线性规划问题,说明每一种资源的影子价格。 0, 250 4002 300 st. 10050max 21 2 21 21 21 xx x xx xx xxz 解计算机求解结果如下图所示 由图可知原模型的最优解为50250 其对偶模型的最优解为50050 三个约束条件的影子价格分别为 50050 。 4 某企业生产甲、乙两种产品其单位利润分别为 2 元和 3 元。每生产一件甲产品需 劳动力 3 个原材料 2 个单位。每生产一件乙产品需劳动力 6 个原材料 1 个单位。企业现 有劳动力 24 个原材料 10 单位。试问1该企业应如何安排生产才能获得最大利润 2若另一个企业想利用该企业的这两种资源劳动力和原材料该企业最低应以多少 价格转让 解设该企业生产甲产品 1 x 个乙产品 2 x 个利润为 z建立模型为 0, 102 2463 st. 32max 21 31 21 21 xx xx xx xxz 1化为标准型 0, 1034 2452 st. x00310max 4321 431 321 4321 xxxx xxx xxx xxxz 134 152 A c (10,3,0,0) b T 01024 , 最初单纯形表 b X 2 1 x 3 2 x 0 3 x 0 4 x b 经过换基迭代后形成最优单纯形表 由最优单纯形表可知最优解为4200 即应生产 4 个甲产品2 个乙产品获利 最大。 2 由1中最优单纯形表知对偶模型最优解为4/9,1/3 因此最低转让价应为 24*4/9+10*1/3=14 (元)。 5已知线性规划问题 4,3,2,1,0 2 2 63 32 st. 6368min 31 43 4321 421 4321 jx xx xx xxxx xxx xxxxz j 1写出该问题的对偶问题 2已知原问题的最优解为 T )0211(X 。根据对偶理论直接求出对偶问 题的最优解。 解 1对偶模型为 0,0 6 3 62 8y s t . 2263m a x 4321 321 432 21 421 43 21 yyyy yyy yyy yy yy yyyy 1 x 2 5 1 0 24 2 x 2 1 0 0 10 2 3 0 0 b X 2 1 x 3 2 x 0 3 x 0 4 x b 2 x 0 1 2/9 -1/3 2 1 x 1 0 -1/9 1/3 4 0 0 -4/9 -1/3 2根据对偶模型的互补松弛性理论可知原模型的松弛变量 5 x =0, 6 x =0, 7 x =0, 8 x =-1。 设对偶模型最优解为 * y 由互补松弛性可知 * y s x =0 所以 * 4 y =0。 又设对偶模型剩余变量为 5 y 6 y 7 y 8 y 且均为正数互补性有 s y * x =0于是 得 5 y = 6 y = 7 y = 8 y =0此时对偶模型的约束条件为 0 6 3 62 8 * 4 * 3 * 2 * 1 * 4 * 3 * 2 * 2 * 1 * 4 * 2 * 1 y yyy yyy yy yyy 解之得 * 1 y =2 * 2 y =10 * 3 y =-2 * 4 y =0 。 6对线性规划问题 无约束 321 321 321 321 321 ,0,0 22 1 2 st. 2max xxx xxx xxx xxx xxxz (1)写出其对偶问题 (2)利用对偶问题性质证明原问题目标函数值 1z。 解 1对偶模型为 0,0 1 2 12y s t . 22m i n 321 321 321 321 3 21 yyy yyy yyy yy yyy 无 约 束 2取对偶模型的可行解010 求得对偶模型的目标函数值为 1根据弱对 偶性中原模型可行解目标函数值不可能超过对偶模型可行解目标函数值 可证得原模型目标 函数值 z1。 7给出线性规划问题 0,0,0 12 2 st. max 321 321 321 21 xxx xxx xxx xxz 利用对偶问题性质证明上述问题目标函数值无界。 解对偶模型为 0, 0 1 12 2min 21 21 21 21 21 yy yy yy yy yy 由图解法可知该线型规划模型无可行解对于原模型可取 1 321 xxx 说明原 模型有可行解根据弱对偶性可知原模型目标函数无界。 8用对偶单纯形方法求解下列线性规划问题 0, 522 33 st. )1( 18124min 321 32 31 321 xxx xx xx xxxz 0, 10536 423 st. )2( 425min 321 321 321 321 xxx xxx xxx xxxz 解 1化为标准型 0, 522 33- st. 0 x018124max 54321 532 431 54321 xxxxx xxx xxx xxxxz A= 1122 0111 , c=(-4,-12,-18,0,0), b= T 53 用对偶单纯形法得初始单纯形表为 由-4-12-18000 可知 B 为正则基以 2为轴心项换基迭代得 b X -4 1 x -12 2 x -18 3 x 0 4 x 0 5 x b 1 x -1 0 -3 1 0 -3 2 x 0 2 -2 0 1 -5 -4 -12 -18 0 0 b X -4 1 x -12 2 x -18 3 x 0 4 x 0 5 x b 以 3 为轴心项换基迭代得 由于所有检验数 b0得到最优解为0, 3/21 。 2化为标准型 0, 10536 423- st. 0 x0425max 54321 5321 4321 54321 xxxxx xxxx xxxx xxxxz A= 11536 01213 , c=(-5,-2,-4,0,0) b= T 104 初始单纯形表为 4 x -1 0 3 1 0 -3 2 x 0 1 1 0 -1/2 5/2 -4 0 -6 0 -6 b X -4 1 x -12 2 x -18 3 x 0 4 x 0 5 x b 3 x 1/3 0 -1/3 -1/3 0 1 2 x -1/3 1 1/3 1/3 -1/2 3/2 -2 0 -2 -2 -6 b X -5 1 x -2 2 x -4 3 x 0 4 x 0 5 x b 4 x 3 -1 -2 1 0 -4 5 x -6 -3 -5 0 1 -10 -5 -2 -4 0 0 以 3 为轴心项换基迭代得 以 1为轴心项换基迭代得 由于所有检验数 b0得到最优解为 2/3 2 , 0 。 9对下列线性规划问题 0, 3222 434 223 st. 804060min 321 321 321 321 321 xxx xxx xxx xxx xxxz (1) 写出对偶问题 2用对偶单纯形法求解原问题 3用单纯形法求解其对偶问题 4比较2与3中每一步计算得到的结果。 解 1对偶模型 0, 8023 4022 60243y st. 342max 321 321 321 321 3 21 yyy yyy yyy yy yyy b X -5 1 x -2 2 x -4 3 x 0 4 x 0 5 x b 1 x 1 1/3 2/3 -1/3 0 4/3 5 x 0 1 -1 -2 1 -2 0 -1/3 -2/3 -5/3 0 b X -5 1 x -2 2 x -4 3 x 0 4 x 0 5 x b 1 x 1 0 1/3 -1 1/3 2/3 2 x 0 1 1 2 -1 2 0 0 -1/3 -1 -1/3 2原模型化为标准模型得 6,5,4,3,2,1,0 3222 434 23 st. 00x 0804060max 6321 5321 4321 654321 ix xxxx xxxx xxxx xxxxxz i 对偶单纯形法得到的初始单纯形表 以 3 为轴心项换基迭代得 以 3/4 为轴心项换基迭代得 b X -60 1 x -40 2 x -80 3 x 0 4 x 0 5 x 0 6 x b 4 x 3 -1 -1 1 0 0 -2 5 x -4 -1 -3 0 1 0 -4 6 x -2 -2 -2 0 0 1 -3 -60 -40 -80 0 0 0 b X -60 1 x -40 2 x -80 3 x 0 4 x 0 5 x 0 6 x b 1 x 1 2/3 1/3 -1/3 0 0 2/3 5 x 0 5/3 -5/3 3/4 1 0 -4/3 6 x 0 -2/3 -4/3 -2/3 0 1 -5/3 0 0 -60 -20 0 0 b X -60 1 x -40 2 x -80 3 x 0 4 x 0 5 x 0 6 x b 1 x 1 1/4 3/4 0 -1/4 0 1 4 x 0 -5/4 5/4 1 -3/4 0 1 6 x 0 2/3 -1/3 0 -1/2 1 -1 0 -25 -35 0 -15 0 以 2/3 为轴心项换基迭代得 全部的检验数 b0得到最优解为5/6,2/3,0 。 3对偶模型化为标准型得 6,5,4,3,2,1,0 8023 4022 60243y st. 000342max 6321 5321 4321 6543 21 iy yyyy yyyy yyy yyyyyy i 初始单纯形表为 以 3 为轴心项换基迭代得 b X -60 1 x -40 2 x -80 3 x 0 4 x 0 5 x 0 6 x b 1 x 1 0 4/9 3/4 -1/12 -1/12 5/6 4 x 0 0 55/36 1 -3/4 -5/6 11/6 2 x 0 1 2/9 0 1/3 -2/3 2/3 0 0 -260/9 0 -20/3 25 B y 12 y 24 y 3 3 y 4 0 y 5 0 y 6 0 y b 4 y 3 4 3 1 0 0 60 5 y 2 1 2 0 1 0 40 6 y 1 3 2 0 0 1 80 2 4 3 0 0 0 B y 12 y 24 y 3 3 y 4 0 y 5 0 y 6 0 y b 1 y 1 3/4 2/3 1/3 0 0 20 5 y 0 -5/3 2/3 -2/3 1 0 0 以 3/4 为轴心项换基迭代得 以 2/3 为轴心项换基迭代得 由全部检验数 0得最优解为020/3,50/3 。 4比较 第五届 1某公司制造甲、乙两种产品甲、乙两种产品的产量每天分别为 30 个和 120 个。公 司希望了解是否通过改变这两种产品的数量而提高公司的利润 制造每个产品所需的加工工 时和各个车间的加工能力如表 5-10 所示。 表 5-10 产品的相关数据 6 y 0 5/3 4/3 -1/3 0 0 60 0 4 /3 5/3 -2/3 0 0 B y 12 y 24 y 3 3 y 4 0 y 5 0 y 6 0 y b 2 y 3/4 1 1/2 1/4 0 0 15 5 y 5/4 0 2/3 -1/4 1 0 25 6 y -5/4 0 1/2 -3/4 0 0 35 -4/3 0 1 -1 0 0 B y 12 y 24 y 3 3 y 4 0 y 5 0 y 6 0 y b 2 y 1/3 1 0 1/3 -1/3 0 20/3 3 y 5/6 0 1 -1/6 2/3 0 50/3 6 y -5/3 0 0 -2/3 -1/3 0 85/3 -13/6 0 0 -5/6 -2/3 0 400500 3001214 440223 540302 300021 /每个产品元利润 时数车间能力每天加工工产品乙产品甲车间 假设每天甲、乙产品的生产产量分别为 21 , xx 则线性规划模型为 0, 3005.12.1 44022 5403 3002 st. 400500max 21 21 21 2 1 21 xx xx xx x x xxz 使用 QM 软件求解并回答下面问题。 1最优解是什么最大利润是多少 2哪个车间的加工工时已用完那个车间的加工工时还没用完其松弛变量即没用 完的加工工时各为多少 3四个车间的加工工时的对偶价格各为多少请对此对偶的含义予以说明。 4 如果请你在这四个车间中选择一个车间进行加班生产 你会选择哪一个为什么 5目标函数中 1 x 的系数在什么范围内变化时最优解不变。 6目标函数中 2 x 的系数从 400 提高到 490 时最优解变了没有为什么 7请解释右端常数项各值的上限和下限。 8车间 1 的加工工时数从 300 增加到 400 时总利润能增加多少这时最优解变化 了没有 9 车间3的加工工时数从440增加到480时 能否求得总利润增加的数量为什么 解(1)将原模型变换成标准形 6,5,4,3,2,1,0 3005.12.1 44022 5403 3002 st. 0000400500max 621 521 42 31 654321 ix xxx xxx xx xx xxxxxxz i 得到最初单纯形表为 为可行基则取 CABCC AABBCCppppB CbA B BB 1 11 6543 0b0000 0000400500 300 440 540 300 10005.12.1 010022 001030 000102 CB XB 1 500x 2 400x 3 0 x 4 0 x 5 0 x 6 0 x b 0 3 x 2 0 1 0 0 0 300 0 4 x 0 3 0 1 0 0 540 0 5 x 2 2 0 0 1 0 440 0 6 x 1.2 1.5 0 0 0 1 300 jj zc 500 400 0 0 0 0 500 1 x 1 0 0.5 0 0 0 150 0 4 x 0 3 0 1 0 0 540 0 5 x 0 2 -1 0 1 0 140 0 6 x 0 1.5 -0.6 0 0 1 120 jj zc 0 400 -250 0 0 0 500 1 x 1 0 0.5 0 0 0 150 0 4 x 0 0 1.5 1 -1.5 0 330 400 2 x 0 1 -0.5 0 0.5 0 70 0 6 x 0 0 0.15 0 -0.75 1 15 jj zc 0 0 -50 0 -200 0 最优解为 70150 21 xx 最大利润 1030070400150500400500max 21 xxZ (2)由最终单纯形表知 153300 6453 xxxx 因此一车间和三车间的加工工 时已用完二车间和四车间没有用完分别剩余 330 和 15 个加工工时。 (3)由最终单纯形表知第一车间的影子价格为-(-50) 即 50第二车间的影子价格为-(-200) 即 200。这表示在一定范围内第一车间每增加一个设备台时目标函数增加 50第二车间 每增加一个设备台时目标函数增加 200。 (4)选择第三车间因为第三车间的影子价格高每增加一工时带来的利润大。 (5)由最优单纯形表知 )04000500(0000400500 B CC AB 1 = 175.0015.000 05.005.010 05.115.100 0005.001 。 1 x 的系数为基变量系数因此设 1 c 的波动为令 1 c =500+要使优解不变则 0 1 ABCC B即 0 175.0015.000 05.005.010 05.115.100 0005.001 )04000500(0000400500 解得 100 1 c =500+ 400c 1 6设 2 c 的波动为令 2 c =400+若使最优解不变则 0 1 ABCC B即 0 175.0015.000 05.005.010 05.115.100 0005.001 )04000500(0000400500 解得 100400 100 500c0 2 。 (7)常数项波动变化当 i b 变化时只要 0 1 bB 则B仍是最优基。令 11 300b 则 0b 1 B 即 300 440 540 300 175.0015.0 05.005.0 05.115.1 0005.0 0 解得 140100 , 11 300b , 440200 1 b 同理分别令 22 300b 33 300b 44 300b 解得 210 2 b 460300 3 b 285 4 b 。 (8)400 在常数项变化范围200440之间因此总利润变化量50(400-300)=5000 最优解变化为 (9)不能因为常数项变化超出其变化范围300460 。 2已知线性规划问题: 0, 3 72 22 st. 2max 21 1 21 21 21 xx x xx xx xxz 的最终单纯形表如表 5-11所示。 表 5-11 最优单纯形表 21000 31000 3100011 50102 0002 2 3 2 1 3 1 2 1 2 1 2 54321 jj zc x x x xxxxxbXc BB 1写出其对偶模型 2求出对偶模型的最