运筹学习题.doc

习题课1(1) 假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10x16x23x32x4(2) 将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0解：首先,将目标函数转换成极大化：令 z= -f = -3.6x1+5.2x2-1.8x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 0(3)用图解法求解下列线性规划问题本例中目标函数与凸多边形的切点是B(2,5)，则X*=(2,5)为最优解，maxZ=20(4) 找出下列线性规划问题的全部基解，基可行解，并找出最优解基本解：X1=(0,1,4,12,18) X2=(4,0,0,12,6) X3=(6,0,-2,12,0) X4 =(4,3,0,6,0) X5=(0,6,4,0,6) X6=(2,6,2,0,0) X7=(4,6,0,0,-6) X8=(0,9,4,-6,0)其中基本可行解为： X1， X2， X4， X5 ，X6最优解为X*X6 =(2,6,2,0,0) Z*=36习题课2(1) 用单纯形表求解LP问题Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示B设备有5个机时的剩余） 最优值 z* = 70000 (2) 用单纯形法解线性规划问题 (唯一解)解：化为标准型列出单纯形表Cj21000CBXBbx1x2x3x4x5000x3x4x51524506152110001000145-Z021000020x3x1x5154101051/32/310001/6-1/60013123/2-Z-801/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2-Z-20000-1/4-1/2Z*=17/2, X*=(7/2,3/2, 15/2,0,0)习题课3(1) 用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表Cj30100M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x74191-201131-111000-10010001-Z10M-2M-34M10-M0000-Mx4x2x73163-260102-141001-13-11-3001-Z6M6M-304M+103M-4M000-3x4x2x103100101001/32/3100-1/201/2-1/20-1/21/21/31/6-Z300303/2-M-3/2-M+1/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/41/21/4-3/4-1/21/41/4-Z-3/2-9/2000-3/4-M+3/4-M-1/4人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0) Z*=3/2注意：(1)在LP问题的最优解中，人工变量都处在非基变量位置(即取0值)，则原问题有最优解，且去掉人工变量后的解为原问题的最优解。(2)若在最优解中，包含有非零的人工变量，则原问题无可行解。(3)若最优解的基变量中，包含人工变量，但该人工变量的取值为0，这时可将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解。(2) 用单纯形法求解线性规划问题解 化为标准形式有列表计算Cj3200MCBXBbx1x2x3x4x50Mx3x52122314100-10123-Z-12M3M+34M+20-M0-2Mx2x5242-5101-40-101-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4) Z*=4M-4 说明原问题无解(3) 用两阶段法求解例1加入人工变量则为解：第一阶段列单纯形表Cj0000011CBXBbx1x2x3x4x5x6x7011x4x6x74191-201131-111000-10010001-Z-102-400100001x4x2x73163-260102-141001-13-11-3001-Z-6-60-40-340000x4x2x103100101001/32/3100-1/201/21/20-1/21/21/31/6-Z00000011所有的j0(求极小值)，且人工变量已从基变量中换出，因此第一阶段的最优解为X*=(1,3,0,0,0,0,0),将最优表中的人工变量去掉，即可作为第二阶段的初始单纯形表。X0=(1,3,0,0,0),为第2阶段的初始基可行解。第二阶段：将表中的人工变量x6,x7除去，目标函数改为Max z=-3x1+0x2+x3+0x4+0x5 再从第一阶段所得最优表出发，继续用单纯形法计算。Cj30100CBXBbx1x2x3x4x5003x4x2x103100101001/32/3100-1/201/2-Z300303/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/4-Z-3/2-9/2000-3/4X*=(0，5/2，3/2，0，0),Z*=3/2习题课4(1) 人力资源分配的问题 某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下：班次i时间至少所需人数xi16:00-10:0060x1210:00-14:0070x2314:00-18:0060x3418:00-22:0050x4522:00-2:0030x562:00-6:0030x6xi： 实际安排司乘人员数 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时问该公交线路怎样安排司机和乘务人员，既能足工作需要，又配备最少司机和乘务员？ 解：设xi表示第i班次时开始上班的司机和乘务人员数，这样可以知道在第i班工作的人数应包括第i-1班次时开始上班的人员数和第班次时开始上班的人员数，例如有x1 +x270。又要求这六个班次时开始上班的所有人员最少，既要求x1 +x2 +x3+x4 +x5 +x6最小，这样建立如下的数学模型：目标函数：min z = (x1 +x2 +x3+x4 +x5 +x6)约束条件：(2) 将以下线性规划问题转化为标准形式 Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0解：首先，将目标函数转换成极大化： 令 z = -f = 3x15x28x3+7x4 ； 其次考虑约束，有3个不等式约束，引进松弛变量x5 ,x6 ,x7 0 ；由于x2无非负限制，可令x2=x2-x2”,其中x20，x2”0 ； 由于第3个约束右端项系数为-58，于是把该式两端乘以-1 。 于是，我们可以得到以下标准形式的线性规划问题： Max z = 3x15x2+5x2”8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6x4+x5= 28 4x1+2x2-2x2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0(3) 用图解法求解LP问题Max Z = 34 x1 + 40 x24 x1 + 6 x2 48 2 x1 + 2 x2 182 x1 + x2 16x1、 x2 0最优解 (3,6)(4)下表是用单纯形法计算时某一表格，已知目标函数为maxZ=28x4+x5+2x6，约束形式为，x1， x2， x3为松弛变量，当前目标函数值为14：(1)计算a-g的值 (2)表中解是否为最优解CjCBXBbx1x2x3x4x5x6x6x2x4a503600de-14/32f00115/20100-Zbc00-1g（1） 7，6，0，1，0，1/3，0（2）表中解是最优解习题课5v 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。 v 解：先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4表3-3 单位运价表 表3-4 产销平衡表与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有确定初始基可行解. 最小元素法基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例1进行讨论。第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2b1，A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-6。表 3-5 表3-6第二步：在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。第三步：在表3-8未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表3-9。这方案的总运费为86元。 2. 伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。v 伏格尔法的步骤是：v 第一步：在表3-3中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表3-10。v 第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-10中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表3-11同时将运价表中的B2列数字划去。如表3-12所示。v 第三步：对表3-12中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。用此法给出例1的初始解列于表3-13。v 由以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。v 本例用伏格尔法给出的初始解就是最优解。设有A1，A2，A3三个产地生产某种物资，其产量分别为7吨，5吨，7吨。B1，B2，B3，B4四个销地需要该种物资，销量分别为2吨，3吨，4吨，6吨。又知各产销地之间的单位运价表如表5-12，试决定总运输费用最小的调运方案。表4-12 销地产地B1B2B3B4产量/tA1A2A321071138351492757销量/t2346解：产地总产量为19吨，销地总销量为15吨，所以这是一个产大于销的运输问题。按上述方法转化为产销平衡的运输问题，见表5-13。在表5-13右虚设一个销地B5，其销量为1915=4t，从各产地到B5的运价为零。表4-13 销地产地B1B2B3B4B5产量/tA1A2A321071138351492000757销量/t23464 对表5-13可用表上作业法计算出最优方案为： x11=2，x14=3，x15=2，x22=3，x25=2，x33=4，x34=3，其余xij=0，z=35元习题课6习题课7l 例：下示图G1是图G的子图，图G2是图G的生成子图。v 例8 某工厂内联结六个车间的道路网如图10-17(a)所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v 解 这个问题就是求如图10-17(a)所示的赋权图上的最小树，用避圈法求解。 i=1,E0=，从E中选最小权边v2，v3，E1=v2，v3； i=2,从EE1中选最小权边v2，v4(v2，v4与v2，v3不构成圈)，E2=v2，v3，v2，v4； i=3，从EE2中选v4，v5(V，E2v4，v5)不含圈)，令E3=v2，v3，v2，v4，v4，v5； i=4，从EE3中选v5，v6(或选v4，v6)(V，E3v5，v6)不含圈)，令E4=v2，v3，v2，v4，v4，v5，v5，v6； i=5，从EE4中选v1，v2(V，E4v1，v2)不含圈)。注意，因v4，v6与已选边v4，v5，v5，v6构成圈，所以虽然v4，v6的权小于v1，v2的权，但这时不能选v4，v6)，令E5=v2，v3，v2，v4，v4，v5，v5，v6，v1，v2； i=6，这时，任一条未选的边都与已选的边构成圈，所以算法终止。 (V，E5)就是要求的最小树，即电话线总长最小的电话线网方案(图10-17(b)，电话线总长为15单位。v 用Dijkstra方法求图10-19所示的赋权图中，从v1到v8的最短路v 解 计算的最后结果为 P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。 (v1)=0，(v4)=1，(v5)=1，(v2)=3，(v5)=2，(v9)=5，(v7)=5，(v6)=5，(v8)=9。 这样从v1到v8的最短链为(v1，v3，v2，v5，v9，v8)，总权为11。习题课8某电视机厂打算生产一种新产品，现有三种方案可供选择。：改造原有的生产线；：新建一条生产线；：与其他企业合作生产。根据以往的市场经验信息，产品投入市场后可能有三种自然状态，：畅销；：销路适中；：滞销。各自然状态发生的概率分别为：，。各方案在各自然状态下的损益值如表13.3所示。试确定最佳的决策方案。【解】，。表13.3 某电视机厂生产决策损益表 行动方案自然状态及其概率 ：畅销 ：销路适中 ：滞销=0.3 =0.4 =0.3损益值（万元） 600 400 -250800 350 -500380 240 -50由于方案的期望值最大，所以方案，即改造原有的生产线为该厂选择的最佳方案。若假定各状态的概率相等，则各方案的期望收益值分别为：，。所以方案为最佳方案。根据上述原理，可以制作例13.1的决策树图，如图13.2所示。畅销（0.3）销路适中(0.4)滞销(0.3)600400-250改造新建合作畅销（0.3）销路适中(0.4)滞销(0.3)800350-500畅销（0.3）销路适中(0.4)滞销(0.3)380240-50265万元230万元195万元265万元图13.2 某电视机厂生产方案决策树图利用决策树图进行分析是从损益值开始由右向左进行推导的，通常称为反推决策树法。以“改造”这一方案为例，把三种自然状态下的损益值和相应概率的乘积相加，就可得到这一行动方案的期望值。即：，将它标注在“改造”这一方案枝上。用同样的方法可计算其他两个方案的期望值，并标在相应的方案枝上。根据这些期望值，处在决策点的决策者就可以进行选择。由于“改造”这一方案的期望收益值最大，因此，舍弃其他两个方案，选取“改造”为最佳方案。某人才咨询公司用一套“销售能力测试”来帮助企业选择销售人员。过去经验表明：在所有申请销售人员职位的人中，仅有65%的人在实际销售中“符合要求”，其余则“不符合要求”。“符合要求”的人在能力测试中有80%成绩合格，“不符合要求”的人中，及格的仅30%。已知一投考者在能力考试中成绩合格，那么，他将是一个“符合要求”的销售员的概率是多少？【解】设：表示一个“符合要求”的销售员，：表示通过考试，那么，一投考者在能力考试中成绩合格，他将是一个“符合要求”的销售员的概率为：。从计算的结果可以看出，假定提出申请销售人员一职的投考者的类型没有变化，从申请人中随机挑选一人，他“符合要求”的概率是0.65；如果企业只接受通过考试的申请人，这个概率将提高到0.83。贝叶斯定理能够解决后验概率的计算问题。某DVD生产厂家要研制开发一种新型DVD，其所要解决的首要问题是这种新产品的销路和竞争者的情况。经过必要的风险估计后，他们估计出：当新产品销路好时，采用新产品可赢利80万元，不采用新产品而生产老产品时，则因其他竞争者会开发新产品，而使老产品滞销，工厂可能亏损40万元；当新产品销路不好时，使用新产品就要亏损30万元，当不采用新产品，就有可能用更多的资金来发展老产品，可获利润100万元。现估计销路好的概率为0.6，销路差的概率为0.4。根据过去市场调查的经验，企业的市场研究人员知道市场调查不可能是完全准确的，但一般能估计出调查的准确程度。与真实自然状态的调查结果的一些主观条件概率如表13.5所示。表13.5 调查结果的条件概率条件概率 调查结果自然状态（销路好）（销路差）（不确定）（销路好）0.800.100.10（销路差）0.100.750.15在这种情况下，有两个问题需要进行决策：（1）是否值得作一次市场调查，以获得市场需求的后验概率；（2）是否生产这种新产品。【解】根据题意，可得在不考虑市场调查的情况下，企业生产新型DVD的损益矩阵表，如表13-6所示。根据表13-6中的期望值作为决策标准，应选择行动方案。当可能的调查结果为已知时，可由贝叶斯公式求后验概率和（），如：。表13.6 企业生产新型DVD的损益矩阵表损益值（万元） 自然状态行动方案（销路好）（销路差）期望值采用新产品80-3036不采用新产品-4010016 其他后验概率同理进行计算，具体结果见表13-7。表13.7 后验概率调查结果0.9230.1670.500.0770.8330.50 由表13.7可知：当调查结果也为销路好时，市场销路好的概率为0.923，即由原来的先验概率0.6提高到0.923；其他后验概率可作相应的解释。 下面利用决策树进行分析。不作进一步调查研究，采用最佳方案可得期望利润值36万元。当采用进一步调查研究时，有可能达到的期望利润值为：71.530.52+76.620.36+300.12=68.38万元，两者相差32.38万元。这就是获得信息的价值。（1）当调查费用小于32.38万元时，该企业才会去搜集新的信息，如果多于或等于32.38万元，企业不会去进行市场调查，因为他只要选择最佳方案，就可以获得更大收益；（2）是否生产新