管理运筹学课后答案.doc

2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。（1） 解：（1）令，则得到标准型为（其中M为一个任意大的正数）初始单纯形表如表2-1所示： 表2-1cj-224-400-M-MqCBXBbx2x4x5x6x70x419322-2100019/3-Mx614 4 34-40-11014/4-Mx726524-4000126/5-z-2+9M2+5M4+8M-4-8M0-M00 2.3 用单纯形法求解下列线性规划问题。 （1） （2） 解：（1）最优解为。（2） 最优解为。2.4 分别用大M法和两阶段法求解下列线性规划问题。（1） （2） 解：（1）最优解为。 （2）最优解为。2.6 已知线性规划问题其对偶问题最优解为。试用对偶理论找出原问题最优解。 解：先写出它的对偶问题将代入约束条件可知，第2、3、4个约束为严格不等式，因此，由互补松弛性得。又因为，所以原问题的两个约束条件应取等式，因此有 故原问题最优解为。2.12 现有线性规划问题先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？ （1）约束条件的右端项系数由20变为30；（2）约束条件的右端项系数由90变为70；（3）目标函数中的系数由13变为8；（4）的系数列向量由变为；（5）将原约束条件改变为；（6）增加一个约束条件。 解：在上述LP问题的第、个约束条件中分别加入松弛变量x4,x5得列出此问题的初始单纯形表并进行迭代运算，过程如表2-11所示。由表2-11中的计算结果可知，LP问题的最优解X*=(0,20,0,0,10)T，z*=5*20=100。（1）约束条件的右端项系数由20变为30，则有列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。表2-11cj-551300iCBXBbx1x2x3x4x50x420-11 3 1020/30x59012410019cj-zj-55130013x320/3-1/3 1/3 11/30200x570/346/32/30-10/3135cj-zj-2/32/30-13/305x220-113100x510160-2-41cj-zj00-2-50表2-12cj-551300CBXBbx1x2x3x4x55x230-113100X5-30160 -2 -41cj-zj00-2-505x2-152310 -5 3/213x315-8012-1/2cj-zj-1600-1-10x43-23/5-1/501-3/1013x396/52/5101/10cj-zj-103/5-1/500-13/10由表2-12中计算结果可知，LP问题的最优解变为。（2）约束条件的右端常数由90变为70，则有列出单纯形表，并利用对偶单纯形法求解，结果如表2-13所示。 表2-13cj-551300CBXBbx1x2x3x4x55x220-113100X5-10160 -2 -41cj-zj00-2-505x252310-53/213x35-8012-1/2cj-zj-1600-1-1由表2-13结果知，LP问题的最优解变为。（3）目标函数中x3的系数由13变为8，由于x3是非基变量，其检验数变为所以LP问题的最优解不变。（4）x1的系数列向量由(-1,12)T变为(0,5) T，则x1在最终单纯形表中的系数列向量变为从而x1在最终单纯形表中的检验数变为所以LP问题的最优解保持不变。（5）将原约束条件改变为10x1+5x2+10x3100，则x1在最终单纯形表中系数列向量变为，检验数x2在最终单纯形表中系数列向量变为，检验数。又因的各分量均大于0，故LP问题的最优解不变。 （6）增加一个约束条件2x1+3x2+5x350，则在此约束条件中加入松弛变量x6，并将此约束加入到最终单纯形表中，继续迭代，过程如表2-14所示。由表2-14中计算结果可知，LP问题的最优解变为，。表2-14cj-5513000CBXBbx1x2x3x4x5x65x220-1131000x510160-2-4100x6502350015x220-1131000x510160-2-4100x6-1050 -4 -301cj - zj00-2-5005x225/211/410-5/403/40x51527/200-5/21-1/213x35/2-5/4013/40-1/4cj - zj-5/200-7/20-1/23.1 分别用分支定界法和割平面法求解下列整数规划模型。（1） （2） 解：（1）求解得到最优解。（计算步骤略）（2）仅写出利用割平面法求解的过程。在原IP问题约束条件中加入松弛变量x3,x4，化为标准型，可得不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如表3-1所示。表3-1cj1100qiCBXBbx1x2x3x40x36211060x4204 5 014cj-zj11000x32 6/5 01-1/55/31x244/5101/55cj-zj1/500-1/51x15/3105/6-1/61x28/301-2/31/3cj-zj00-1/6-1/30因此，松弛问题的最优解为x1=5/3,x2=8/3,x3=0,x4=0;z=13/3。由于x2不为整数，因此在最终单纯形表中根据x2所在的行作割平面即将它作为约束条件，引入松弛变量后加到最终单纯形表中，并采用对偶单纯形法继续迭代，计算过程如表3-2所示。表3-2cj11000CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/300x5-200-1 -1 1cj-zj00-1/6-1/3001x121010-1/61x2201-101/30x420011-1cj-zj0000-1/6 由于的值均为整数，所以得到原问题的最优解为3.4 某厂新购4台不同类型机器，可以把它们安装在4个不同的地点。由于对特定的机器而言，某些地方可能安装起来特别方便且合适，所以不同的机器安装在不同的地点费用是不同的。估计的费用见表3-3，试制定使得总安装费用最小的安装方案。表3-3 （费用单位：元） 地点机器1234机器总数1109871234561321121443561需要量1111解：设 cij机器i安装在地点j所需的费用。建立该问题的数学模型如下：目标函数：约束条件：(1)每一部机器只分配在一个地点，即 (2)每一个地点只能有一台机器，即 (3) 工作指派问题可以看成是一类特殊的运输问题，每个供应点的供应量为1，每个需求点的需求量也为1。因此，本题可以采用表上作业法进行计算，也可以利用匈牙利法进行计算。计算得到的最佳安装方案为：机器1安装在地点4、机器2安装在地点1、机器3安装在地点3、机器4安装在地点2，最小总安装费为14元。3.9 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如表3-17所示。试确定使总运费最少的化肥调拨方案。表3-17 需求产地IIIIIIIV产量(万吨)A1613221750B1413191560C192023-50最低需求(万吨)最高需求(万吨)3050707003010不限解：这是一个产销不平衡的运输问题，总产量为160万t，四个地区的最低需求为110万t，最高需求为无限。根据现有产量，第IV个地区每年最多能分配到60万t，这样最高需求就为210万t，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万t。由于各地区的需求量包含两部分，如地区I，其中30万t是最低需求，故不能由假想化肥厂D供给，令相应的单位运价为M（任意大的正数）；而另一部分20万t满足或不满足均可以，因此可以由假想化肥厂D供给，按前述，可令相应的单位运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表（表3-18）和单位运价表（表3-19）。并根据表上作业法，可以求得这个问题的最优解，如表3-20所示。表3-18 销地产地IIIIIIIIVIV产量A50B60C50D50销量302070301050表3-19 销地产地IIIIIIIIVIVA161613221717B141413191515C19192023MMDM0M0M0表3-20 销地产地IIIIIIIIVIV产量A5050B20103060C3020050D302050销量3020703010504.2 利用单纯形法求解下列目标规划模型。（1）解：（1）本题的三个约束条件都是目标约束，有三个负偏差变量，因此选择负偏差变量为初始基变量。并计算出各非基变量的检验数，得到初始的单纯形表如表4-1所示。非基变量x1,x2的检验数分别为1= -P1-2P2和2= -2P1 -2P2，它们的最高优先级的系数都小于零，但2中P1的系数等于-2，其绝对值等于2，大于1中P1的系数的绝对值1，因此x2应当进基。用最小比值法确定应当出基。换基后，通过计算求得新的基本可行解，如表4-2所示。表4-1cj00P100P1P20qCBXBbx1x2P1501 2 1-100002504021001-10040P2802200001-140jP1-1-2010100P2-2-2000001表4-2cj00P100P1P20qCBXBbx1x20x2251/211/2-1/2000050015 3/2 0-1/21/21-10010P23010-11001-130jP100100100P2-101-10001尽管x1与具有相同的负检验数，但根据前面讨论的原则，由于x1是决策变量，选择x1进基，用最小比值法确定出基，换基后，计算所得新的基本可行解如表4-3所示。表4-3cj00P100P1P20qCBXBbx1x20x220012/3-2/3-1/31/3000x11010-1/3 1/3 2/3-2/30030P22000-2/32/3-2/32/31-130jP100100100P2002/3-2/32/3-2/301首项系数小于零的检验数只有的为，因此应当进基，由于存在两个最小比值，取下标最小的变量出基，因此x1出基，换基后，再计算新的基本可行解，如表4-4所示。表4-4cj00P100P1P20qCBXBbx1x20x24021001-10003030-112-200P20-2000-221-1jP100100100P220002-201此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：x1=0,x2 =40,=30，其他偏差变量都等于零。4.3 某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。 解：该问题的数学模型如下：5.2 计算从A到B、C和D的最短路。已知各段路线的长度如图5-1所示。图5-1解：求从A到B、C和D的最短路等价于求从B、C和D到A的最短路。设阶段变量k=1,2,3,4，依次表示4个阶段选路得过程，第1阶段从B、C或D出发到B3、C3或D3，第2阶段从B3、C3或D3出发到B2、C2或D2，第3阶段从B2、C2或D2出发到B1、C1或D1，第4阶段从B1、C1或D1出发到A；状态变量sk表示k阶段初可能处的位置；决策变量xk表示k阶段可能选择的路线；阶段指标vk表示k阶段与所选择的路线相应的路长；指标函数表示k至第4阶段的总路长；递推公式计算过程如表5-1所示。 由表中计算结果可以看出：从B到A的最短路线为BC3C2B1A，最距离为16；从C到A的最短路线为CC3C2B1A或CD3C2B1A，最短距离为21；从D到A的最短路线为DD3C2B1A，最短距离为20。表5-1kskxkvkvk4=vk+fk+1fkxk*4B1A33+03AC1A88+08AD1A77+07A3B2B144+37B1C122+8C2B133+36B1C188+8D177+7D2C144+812C1D166+72B3B21010+717B2C21313+6C3B21212+711C2C255+6D266+12D3C277+613C2D288+121BB399+1716C3C355+11CB31010+1721C3、D3C31010+11D388+13DC31515+1120D3D377+135.3 某工业部门根据国家计划的安排，拟将某种高效率的设备5台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表5-2所示。表5-2 设备数工厂012345甲03791213乙0510111111丙046111212问：这5台设备如何分配给各工厂，才能使国家得到的盈利最大？解：将问题按工厂分为3个阶段，甲、乙、丙3个工厂分别编号为1、2、3；设sk表示分配给第k个工厂至第n个工厂的设备台数；xk表示分配给第k个工厂的设备台数；则sk+1=sk - xk为分配给第k+1个工厂至第n个工厂的设备台数；Pk(xk)表示xk台设备分配给第k个工厂所得得盈利值；fk(sk)表示sk台设备分配给第k个工厂至第n个工厂时所得到得最大赢利值。由以上的假设可写出逆推关系式为下面采用逆推法进行计算。第3阶段：设s3台设备(s3=0,1,2,3,4,5)全部分配给工厂丙时，则最大赢利值为其中x3=s3=0,1,2,3,4,5。 因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值。其数值计算如表5-3所示。表5-3表中表示使为最大值时的最优决策。第2阶段：设把s2台设备(s2=0,1,2,3,4,5)分配给工厂乙和工厂丙时，则对每个s2值有一种最优分配方案，使最大盈利值为其中x2=0,1,2,3,4,5。因为给乙工厂x2台，其盈利为P2(x2)，余下的s2-x2台就给丙工厂，则它的盈利最大值为f3(s2-x2)。现要选择x2的值使取最大值。其数值计算如表5-4所示。表5-4第1阶段：设把s1台(这里只有s1=5的情况)设备分配给甲乙丙3个工厂，则最大盈利值为其中x1=0,1,2,3,4,5。 因为给甲工厂x1台，其盈利为P1(x1)，剩下的5-x1台就分给一合丙两个工厂，则它的盈利最大值为f2(5-x1)。现要选择x1值使取最大值，它就是所求的总盈利最大值，其数值计算如表5-5所示。表5-5然后按计算表格的顺序反推算，可知最优方案有两个：（1）由于，根据s2=s1 -=5 - 0=5，查表5-4知，由s3=s2 -=5-2=3，故。即甲工厂分配0台、乙工厂分配2台、丙工厂分配3台。（2）由于，根据s2=s1 -=5 - 2=3，查表5-4知，由s3=s2 -=3-2=1，故。即甲工厂分配2台、乙工厂分配2台、丙工厂分配1台。以上两个分配方案所得的总盈利均为21万元。在此问题中，如果原设备的太熟不是5台，而是4台或3台，用其他方法求解时，往往需要从头再算，但用动态规划求解时，这些列出的表仍旧有用，只需要修改最后的表格就可得到：当设备台数位4台时，最优分配方案为或，总盈利为17万元。当设备台数位3台时，最优分配方案为：，总盈利为14万元。5.4设有一辆载重量为15吨的卡车，要装运4种货物。已知4种货物的单位重量和价值如表5-6所示，在装载重量许可的情况下每辆车装载某种货物的条件不限，试问如何搭配这4种货物才能使每辆车装载货物的价值最大？ 表5-6货物代号重量(吨)价值(千元)货物代号重量(吨)价值(千元)123345234456解：设决策变量分别为4种货物的装载件数，则问题为一线性整数规划： 将其转化为动态规划问题，分为4个阶段，每个阶段的指标函数记为， ， ， 状态变量sk表示第k种至第4种货物总允许载重量，即允许状态集合为，最优值函数表示装载第k种至第4中货物的价值，则动态规划模型为状态转移方程为允许决策集合为即表示在载重量允许的范围内可能装载第k种货物的件数。 用逆推方法求解如下：；。最后得到问题的最优解为，最优值为22千克。7.1 求解下列矩阵对策，其中赢得矩阵A分别为 （1） （2） （3） （4）解：（1）由于，所以A所对应的支付矩阵没有纯对策。即局中人1以(0.36,0.36,0.27)的概率分别出策略1、2和3，其赢得值为-0.4545。（2）由于，所以A所对应的支付矩阵没有纯对策。即局中人1以0.56、0.44的概率分别出策略1和策略2，赢得值为0.67.（3）根据赢得矩阵有，所以G的解为。（4）根据赢得矩阵有，所以G的解为。7.2 甲、乙两家公司生产同一种产品，争夺市场的占有率。假设两家公司市场占有率之和为100，即顾客只购买这两家公司的产品，无其他选择。若公司甲可以采用的商业策略为A1、A2、A3，公司乙可以采用的商业策略为B1、B2、B3。表7-1给出在不同策略下公司甲的市场占有率。在此情况下，请为这两家公司选择他们的最优策略。 表7-1B1B2B3A10.40.80.6A20.30.70.4A30.50.90.5解：若完全采用二人常数和对策的方法确定最优纯策略，则由可得，局中人甲采用策略A3、局中人乙采用策略B1，各获得50%的市场占有率。从计算结果可以看出，局中人甲采用策略A3、局中人乙采用策略B1，各获得50%的市场占有率。10.1某一决策问题的损益矩阵如表10-1所示，其中矩阵元素值为年利润。表10-1 单位：元 （1）若各事件发生的概率是未知的，分别用max min决策准则、max max决策准则、拉普拉斯准则和最小机会损失准则选出决策方案。 （2）若值仍是未知的，并且是乐观系数，问取何值时，方案S1和S3是不偏不倚的？（3）若P1=0.2,P2=0.7,P3=0.1,那么用EMV准则会选择哪个方案？解：（1）采用maxmin准则应选择方案S2，采用maxmax决策准则应选择方案S1，采用Laplace准则应选择方案S1，采用最小机会损失准则应选择方案S1。（2）0.10256； （3）方案S1或S3。10.8假设有外表完全相同的木盒100只，将其分为两组，一组内装白球，有70盒，另一组