西北大学茹少锋管理系统运筹课后问题详解.doc

《西北大学茹少锋管理系统运筹课后问题详解.doc》由会员分享，可在线阅读，更多相关《西北大学茹少锋管理系统运筹课后问题详解.doc（94页珍藏版）》请在三一文库上搜索。

1、word1用图解法求解两个变量线性规划问题的最优解和最优值。2用图解法求解以下线性规划问题，并指出哪个问题有惟一解、无穷多最优解、无界解或无可行解无可行解3某公司从中心制造地点向分别位于城区北、东、南、西方向的分配点运送材料。该公司有26辆卡车，用于从制造地点向分配点运送材料。其中有9辆，每辆能装5吨的大型卡车，12辆每辆能装2吨的中型卡车和5辆每辆能装1吨的小型卡车。北、东、南、西四个点分别需要材料14吨、10吨、20吨、8吨。每辆卡车向各分配点送材料一次的费用如表2-7所示。建立运送材料总费用最小的线性规划模型。表2-7 车辆运送一次的费用北东南西大80639275中50605542小20

2、153822解设大、中、小型车分别用表示，如此；东、南、西、北四个分点分别用表示，如此；向方向发出的型车数量为。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 产品使用的原材料、加工工序、资

3、源限制、本钱产品A产品B产品C资源限制工时或原材料本钱工序1212460015工序2311400010工序3232600010原料13241000020原料2432800040其他本钱101010解设工厂5月份为完成合同甲生产件A产品；为完成合同乙生产件B产品；为完成合同丙生产件 B产品，件C产品。5某公司从事某种商品的经营，现欲制定本年度10至12月的进货与销售计划。该种商品的初始库存量为2000件，公司仓库最多可存放10000件，公司拥有的经营资金80万元，据预测，10至12月的进货与销售价格如表2-9所示。假如每个月仅在1号进货1次，且要求年底时商品存量达到3000件，在以上条件下，建立

4、该问题的线性规划模型，使公司获得最大利润？注：不考虑库存费用表2-9 进货和销售价格月份101112进货价格/元/件909598销售价格/元/件100100115解，为每月购进的货物，为每月销售的货物。6某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量单价如表2-10所示。表2-10 饲料所含的营养成分与价格饲料蛋白质/g矿物质/g维生素/g价格/元13122314622518求这个问题的规划模型，使既满足动物生长的需要，又使费用最小的选用饲料的方案。解设各送这5钟饲料，kg。7某一企业家需要找人清理5间

5、会议室、12X桌子和18个货架。今有两个临时工A和B可供该企业家雇佣。A一天可清理1间会议室、3X桌子与3个货架；而B一天可清理1间会议室、2X桌子与6个货架。A的工资每天25元，B每天22元。为了使本钱最低，应雇佣A和B各多少天？用线性规划图解法求解解：设雇佣A和B分别为天由图知A点为最优解，联立方程：解得：=2, 3,即： Zmin=25+22=252+223=116因此，雇佣A工人2天，B工人3天。8某外贸公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表2-11所示。表2-11 第一季度杂粮

6、价格表进货价/元出货价/元1月2月3月如果买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款。公司希望本季度末库存为2000担，建立该问题的线性规划模型使三个月总的获利最大。解设一月份买入担，卖出担；二月份买入担，卖出担；三月份买入担，卖出担。1求如下线性规划问题的所有基解、基可行解、最优解解：由题意知：A= = b= c=3，1，31=，0，是基，是基变量，是非基变量，令=0，得=-2，=4 即=为基解，但不是根本可行解。2=，0，是基，是基变量，是非基变量。令=0，得=2/3，=3/4，即=为基解，同时为根本可行解，zmax=(2/3)*3+0+4/3*3=6。3，0，是基，是基变量

7、是非基变量，令=0，得=1，=1，即=为基解，同时为根本可行解， zmax=1+3=4。综上所述，基解为=，=，=其中第二个和第三个为根本可行解，=为最优解。2分别用图解法和单纯形法求解如下线形规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点解：1图解法有图解法知线性规划模型的可行域如阴影局部所示，令z=0，1，2时，max z逐渐增大，可行域是无界的，所以，此模型是无界解。2单纯形法：化为标准型为：A= C=2，3，0，02300b01-11010100122300对应图中原点。以1为轴心项，换基迭代，得2300b21-1101001-11105-20-2此时对应图中A点，坐标是

8、1，0以1为轴心项，换基迭代，得2300b210012301-1110035-7此时对应图中B点，坐标是2，3因为，=50,同时对应的列小于等于0，如此原模型有无界解。解：1图解法：可行域如上图阴影局部所示，令z=0，1，2做等值线，得出在c点取最大值，c点坐标为2，6，max z=342单纯形法：化为标准型为： = b= C=2，5，0，0，0取B=为可行基，=0，0，0单纯性表如下：25000b0101004002010120320011825000此时对应图中O点，坐标为0，0，以1为轴心项，换基迭代，得25000b210100400201012002-301605-200-8此时对应图

9、中A点，坐标为4，0以2为轴心项，换基迭代，得25000b210100400031-16501-3/201/230011/20-2/5-23此时对应图中B点，坐标为4，3以3为轴心项，换基迭代，得25000b2100-1/31/3200011/3-1/3250101/206000-11/6-2/3-34由于 =0，0,所以存在唯一解，也是最优解。此时对应图中C点，坐标为2，6，max z=2*2+5*6=34，解：1图解法：可行域如图阴影局部，当z=0，1，2做等值线，与直线的斜率一样，当z与这条直线重合时，该模型取最大值，因此该模型有无穷多个解，无穷多个解是B,C两点线段中的点，max z=

10、162单纯形法：化为标准型：= b=C=2，4，0，0，0 B=0，0，0单纯形表为：24000b022100120120108003001924000此时对应图中点O，坐标为0，0，以2为轴心项，换基迭代，得24000b2111/2006001-1/2102003001902-100-12此时对应图中点A，坐标为6，0以1为轴心项，换基迭代，得24000b2101-104401-1/21020002/3-313000-20-16此时对应图中点B，坐标为4，2由于0,又为非基变量，且=0，且此列存在正数，如此此线性规划模型有无穷解。其中一个根本最优解为，max z=2*4+4*2=163用单纯

11、形法求解如下线性规划问题解：化为标准型：A= b= C=-1，-2，1，0，0，0令B= B为可行基，=0，0，0单纯形表如下：-2000b021-1100401-22010801110015-1-21000以2为轴心项，换基迭代，得-2000b05/20011/20811/2-1101/20401/2200-1/211-2/3-100-1/20-4 =0，0，并且所对应的列全小于0，如此此线性规划模型的解是无界解。5. 线性规划问题，用单纯形法计算时得到的中间某两步的计算表见表3-16所示，试将表中空白处的数字填上。表3-16 单纯形迭代中的两步计算表10000510040104005010

12、400131000 106线性规划问题用单纯形法求解，得到最优单纯形表如表如表3-17所示：表3-17 最终单纯形表10110-122-3000-4求的值；求的值。解：由题意可知：初始的基变量是，将最终单纯形表的基变量通过迭代转换为，复原成最初单纯形表，如下：14108120153600从而得出： b= C=所以,=1 =4 =1 =2=8 =5，= =3 =67某公司生产1、2两种产品，市场对1、2两种产品的需求量为：产品1在1-4月每月需求10000件，5-9月每月30000件，10-12月每月100000件，产品2在3-9月每月需求15000件，其它月每月50000件，该公司生产这两种产

13、品的本钱为：产品1在1-5月内生产每件5元，6-12月内生产每件元；产品2在1-5月内生产每件8元，6-12月内生产每件7元。该公司每月生产这两种产品的能力总合不超过120000件。产品1容积每件立方米，产品2每件立方米，该公司仓库容量为15000立方米，占用公司仓库每月每立方米库容需1元；如该公司仓库不足时，可从外边租借，租用外面仓库每月每立方米库容需元。试问在满足市场需求的情况下，该厂应如何安排生产，使总的费用最小？8某炼油厂使用三种原料油甲、乙、丙混合加工成A、B、C三类不同的汽油产品，有关数据如下表3-18所示。另外，由于市场原因，A的产量不得低于产品总量的40%。问该厂应如何安排生产

14、才能使其总利润最大？表3-18 三种原料的信息产品产品规格原料ABC原料本钱千元/吨原料限量吨甲2000乙2500丙1200加工费千元/吨售价千元/吨解：设，分别为A产品中甲、乙、丙的成分；，分别为B产品中甲、乙、丙的成分；，分别为C产品中甲、乙、丙的成分。由题意，有max z=*+*+*+-1.800*+-1.350*+-0.900*+用计算机求解为：9线性规划的目标函数是求其值的极大化，在标准的单纯形法求解过程中得到如下表(其中是常数)表3-19 求解中某一步的单纯形表00302050-2-118-21在所有的空格上填上适当的数可包含参数2判断下面四种情况在什么时候成立，说明理由。1此解为

15、最优解，写出相应的基解和目标函数值；2此解为最优解，且此线性规划有无穷多最优解；3此规划有无界解；4此解不是最优解，但可用单纯形法得到下一个基可行解。解：100030002051000-20-111182-50-20-021)当2-5时，此线性规划模型有唯一解，基解为最优值为5。 22-5=0，即=时，大于0，此线性规划模型有无穷多最优解。 32-50且0，即0且0且0, 即00时，此解不是最优解。10表3-20是求某极大化线性规划问题计算得到的单纯形表。表中无人工变量，、为待定常数。试说明这些常数分别取何值时，以下结论成立。表3-20 极大化线性规划问题计算得到的单纯形表4100-1-301

16、102-500-41300-30表中解为惟一最优解；表中解为最优解，但存在无穷多最优解；该线性规划问题具有无界解；表中解非最优，为对解改良，换入变量为，换出变量为解：1当d0，0 且0, 此线性规划模型有唯一解。2当d0，=0 或=0，0 且0 且，表中解非最优，为对解改良，换入变量为，换出变量为。第四节1写出线性规划问题的对偶问题。解：12342判断如下说法是否正确，并说明理由。1如果线性规划的原问题存在可行解，如此其对偶问题也一定存在可行解2如果线性规划的对偶问题无可行解，如此其原问题也一定无可行解3在互为对偶问题的一对原问题与对偶问题中，不管原问题是求最大或最小，原问题可行解的目标函数

17、值一定不超过其对偶问题的可行解的目标函数值4任何线性规划问题具有唯一的对偶问题解：1不正确。因为当原模型存在可行解且目标函数值无界时，其对偶模型无可行解。2不正确。因为对偶模型无可行解，其原模型可能存在可行解且目标函数值无界。3不正确。当原模型求最小值时，原模型的目标函数值可能超过对偶模型的目标函数值。4正确。对偶模型具有对称性。3用计算机求解线性规划问题,说明每一种资源的影子价格。解：计算机求解结果如如下图所示：由图可知，原模型的最优解为50，250，其对偶模型的最优解为50，0，50，三个约束条件的影子价格分别为50，0，50 。4某企业生产甲、乙两种产品，其单位利润分别为2元和3元。每生

18、产一件甲产品需劳动力3个，原材料2个单位。每生产一件乙产品需劳动力6个，原材料1个单位。企业现有劳动力24个，原材料10单位。试问：1该企业应如何安排生产才能获得最大利润？2假如另一个企业想利用该企业的这两种资源劳动力和原材料，该企业最低应以多少价格转让？解：设该企业生产甲产品个，乙产品个，利润为z，建立模型为1化为标准型，(10,3,0,0)，,最初单纯形表2300b 2 5 1 0 24 2 1 0 0 10 2 3 0 0经过换基迭代后，形成最优单纯形表2300b 0 1 2/9 -1/3 2 1 0 -1/9 1/3 4 0 0 -4/9 -1/3由最优单纯形表可知，最优解为4，2，0

19、0，即应生产4个甲产品，2个乙产品，获利最大。2由1中最优单纯形表知对偶模型最优解为4/9,1/3，因此，最低转让价应为24*4/9+10*1/3=14 (元)。5线性规划问题1写出该问题的对偶问题2原问题的最优解为：。根据对偶理论，直接求出对偶问题的最优解。解：1对偶模型为2根据对偶模型的互补松弛性理论，可知原模型的松弛变量=0, =0, =0, =-1。设对偶模型最优解为，由互补松弛性可知，=0 ，所以=0。又设对偶模型剩余变量为，且均为正数，互补性有=0，于是得=0，此时对偶模型的约束条件为解之得=2 ，=10 ，=-2 ，=0 。6对线性规划问题(1)写出其对偶问题；(2)利用对偶问

20、题性质证明原问题目标函数值。解：1对偶模型为2取对偶模型的可行解0，1，0，求得对偶模型的目标函数值为1，根据弱对偶性中原模型可行解目标函数值不可能超过对偶模型可行解目标函数值，可证得原模型目标函数值z1。7给出线性规划问题利用对偶问题性质证明上述问题目标函数值无界。解：对偶模型为：由图解法可知该线型规划模型无可行解，对于原模型可取，说明原模型有可行解，根据弱对偶性可知原模型目标函数无界。8用对偶单纯形方法求解如下线性规划问题解：1化为标准型A=, c=(-4,-12,-18,0,0), b=用对偶单纯形法得初始单纯形表为-4-12-1800b-1 0 -3 1 0 -3 0 -2 0 1 -

21、5 -4 -12 -18 0 0由-4，-12，-18，0，00可知B为正如此基；以为轴心项，换基迭代得-4-12-1800b -1 0 1 0 -3 0 11 0 -1/2 5/2 -4 0 -6 0 -6以为轴心项，换基迭代得-4-12-1800b1/3 0 -1/3-1/3 0 1 -1/3 11/3 1/3 -1/2 3/2 -2 0 -2 -2 -6由于所有检验数b0，得到最优解为0, 3/2，1。2化为标准型A=, c=(-5,-2,-4,0,0)， b=初始单纯形表为-5-2-400b -1 -2 1 0 -4 -6-3 -5 0 1 -10 -5 -2 -4 0 0以为轴心项，

22、换基迭代得-5-2-400b1 1/3 2/3 -1/3 0 4/3 0 -1 -2 1 -2 0 -1/3 -2/3 -5/3 0以为轴心项，换基迭代得-5-2-400b1 0 1/3 -1 1/3 2/3 01 1 2 -1 2 0 0 -1/3 -1 -1/3由于所有检验数b0，得到最优解为 2/3 ，2 , 0 。9对如下线性规划问题(1) 写出对偶问题；2用对偶单纯形法求解原问题；3用单纯形法求解其对偶问题；4比拟2与3中每一步计算得到的结果。解：1对偶模型2原模型化为标准模型得对偶单纯形法得到的初始单纯形表-60-40-80000b -1 -1 1 0 0 -2 -4-1 -3 0

23、 1 0 -4 -2 -2 -2 0 0 1 -3 -60 -40 -80 0 0 0以为轴心项，换基迭代得-60-40-80000b 12/3 1/3 -1/3 0 0 2/3 0 5/3 -5/3 1 0 -4/3 0 -2/3 -4/3 -2/3 0 1 -5/3 0 0 -60 -20 0 0以为轴心项，换基迭代得-60-40-80000b 1 1/4 3/4 0 -1/4 0 1 0 -5/4 5/4 1 -3/4 0 1 0 -1/3 0 -1/2 1 -1 0 -25 -35 0 -15 0以为轴心项，换基迭代得-60-40-80000b 1 0 4/9 3/4 -1/12 -1

24、/12 5/6 0 0 55/36 1 -3/4 -5/6 11/6 01 2/9 0 1/3 -2/3 2/3 0 0 -260/9 0 -20/3 25全部的检验数b0，得到最优解为5/6,2/3,0。3对偶模型化为标准型得初始单纯形表为b 4 3 1 0 0 60 21 2 0 1 0 40 1 3 2 0 0 1 80 2 4 3 0 0 0以为轴心项，换基迭代得b1 2/3 1/3 0 0 20 0 -5/3 2/3 -2/3 1 0 0 0 5/3 4/3 -1/3 0 0 60 0 4 /3 5/3 -2/3 0 0以为轴心项，换基迭代得b 3/41 1/2 1/4 0 0 15

25、 5/4 0 -1/4 1 0 25 -5/4 0 1/2 -3/4 0 0 35 -4/3 0 1 -1 0 0以为轴心项，换基迭代得b 1/31 0 1/3 -1/3 0 20/3 5/6 01 -1/6 2/3 0 50/3 -5/3 0 0 -2/3 -1/3 0 85/3 -13/6 0 0 -5/6 -2/3 0由全部检验数0，得最优解为0，20/3,50/3。4比拟第五届1某公司制造甲、乙两种产品，甲、乙两种产品的产量每天分别为30个和120个。公司希望了解是否通过改变这两种产品的数量而提高公司的利润，制造每个产品所需的加工工时和各个车间的加工能力如表5-10所示。表5-10 产

26、品的相关数据假设每天甲、乙产品的生产产量分别为：，如此线性规划模型为使用QM软件求解并回答下面问题。1最优解是什么，最大利润是多少？2哪个车间的加工工时已用完？那个车间的加工工时还没用完？其松弛变量即没用完的加工工时各为多少？3四个车间的加工工时的对偶价格各为多少？请对此对偶的含义予以说明。4如果请你在这四个车间中选择一个车间进展加班生产，你会选择哪一个？为什么？5目标函数中的系数在什么X围内变化时，最优解不变。6目标函数中的系数从400提高到490时，最优解变了没有，为什么？7请解释右端常数项各值的上限和下限。8车间1的加工工时数从300增加到400时，总利润能增加多少，这时最优解变化了没有

27、9车间3的加工工时数从440增加到480时，能否求得总利润增加的数量？为什么？解：(1)将原模型变换成标准形CX0010003000030100540022001044000001300500400000050010000150003010054000-1010140000011200400-2500005001000015000010330400010070000011500-500-2000最优解为：最大利润：(2)由最终单纯形表知：，因此，一车间和三车间的加工工时已用完，二车间和四车间没有用完，分别剩余330和15个加工工时。(3)由最终单纯形表知：第一车间的影子价格为-(-50)，即

28、50，第二车间的影子价格为-(-200)，即200。这表示在一定X围内，第一车间每增加一个设备台时，目标函数增加50；第二车间每增加一个设备台时，目标函数增加200。(4)选择第三车间，因为第三车间的影子价格高，每增加一工时带来的利润大。(5)由最优单纯形表知：，=。的系数为基变量系数，因此，设：的波动为，令=500+，要使优解不变，如此：，即：解得：，=500+6设的波动为，令=400+，假如使最优解不变，如此：，即：解得：，。(7)常数项波动变化，当变化时，只要，如此仍是最优基。令，如此：，即：解得：,同理：分别令，；解得：，。(8)400在常数项变化X围200，440之间，因此，总利润变

29、化量：50(400-300)=5000；最优解变化为：(9)不能，因为常数项变化超出其变化X围300，460。2线性规划问题:的最终单纯形表如表5-11所示。表5-11 最优单纯形表1写出其对偶模型；2求出对偶模型的最优解；3写出最优基与其逆矩阵；4假如右端项变为，最优基是否变化？求出变化后的最优解与其最优值。解：(1)其对偶模型为：(2)原模型最优解为：，设对偶模型最优解为,知；设对偶模型的剩余变量为,由于剩余变量均为非负，故=0，=0，此时对偶模型的约束条件为：(3)最优基为(4)常数项波动变化，当变化时，只要，如此仍是最优基。令，如此：解得：当常数项在其变化X围中变化，故最优基不变；最优

30、解为,最优值为。3给出了如下线形规划：的最优单纯形表如表5-12所示。表5-12 最优单纯形表1求出最优基不变的的变化X围；2求出最优解不变的的变化X围；3在原线性规划的约束条件上，增加下面的约束条件：其最优解是否变化，如变化，求出最优解。解：(1)设的变化为，只要如此仍为最优基，即：，即上变化是最优基不变。(2)设的变化为，要是最优基不变，如此，即：3其最优解变化为。4有一标准型的线性规划问题：其最优单纯形表如表5-13所示：表5-13 最优单纯形表其中：是对用于初始单位矩阵的松弛变量。试求：1利用最优单纯形表求。2假定用代替，其中，要使现行最优基保持不变，的变化X围？当时，求最优解。3求约

31、束影响价格。解：1从最优单纯形表中得出：=由于，是松弛变量所以，均为0。根据=-知：得出：分别为2，3，1，0，0。2要使最优基不变，如此=b0，即0 得出：。当，在区间内，最优基不变，最优解为：3根据影子价格与松弛变量之间的关系知：，5有最大问题的最优单纯形表如下，其中为松弛变量。表5-14 最优单纯形表写出该问题的最优解。当为何值时，其对偶问题无解？并说明理由。解：1由以上的最优单纯表得出最优解为：2假如原模型有可行解但目标函数值无界，如此对偶模型无解。设C=(),因为为松弛变量，所以均为0 。C-=，0，0-解得：=0，=-4，=1 设=+，当C-0时，最优基不变，即C-=0，-4，1+，0，0-1+，00 解得：-13 即当-13时，最优基不变。此时=-4-+，0=-3+当0 且 -13 时，原模型有无界解，即=3时，对偶模型无可行解。6考虑如下线性规划：最优单纯形表如表5-15所示：表5-1