《运筹学教程》第二章习题答案.doc
运筹学教程第二章习题答案1、（1）解：引入松弛变量x40,x50,化不等式为等式为：minz=2X1 +3X2+4X3s.t. X1+3X2+2X3+X4=74X1+2X2+X5=9X1,X2,X4,X50化自由变量为非负，令X3=X3-X3，X3，X30 ：minz=2X1 +3X2+4X3-4X3s.t. X1+3X2+2 X3-2 X3+X4=74X1+2X2+X5=9X1,X2, X3，X3，X4,X5 0(2)解：引入松弛变量x50,剩余变量X60，化不等式为等式为：maxz=X1 -5X2+4X3- X4s.t. X1+2X3+X5=7X2-2X4-X6=9X1,X2，X4,X5 ，X60化自由变量为非负，令X3=X3-X3，X3，X30 ：maxz=X1 -5X2+4X3-4X3- X4s.t. X1+2 X3-2 X3+X5=7X2-2X4-X6=9X1,X2, X3，X3，X4,X5 , X60化极大的目标函数为极小的目标函数：minz=-X1+5X2-4X3+4X3+X4s.t. X1+2 X3-2 X3+X5=7X2-2X4-X6=9X1,X2, X3，X3，X4,X5 , X602、(1)是 不等式表示下图阴影区域，过阴影部分任意两点的直线仍在该区域内。 (2)不是 不等式表示下图阴影区域，过阴影部分且通过曲线上部的直线上的点不完全在该区域内。 (3)不是 不等式表示下图阴影区域，过阴影部分且通过圆内部的直线上的点不完全在该区域内。3、在以下问题中，指出一组基础变量，求出所有基础可行解以及最优解。（1）解：将上式化成标准形式，如下：从上式中可以得出系数矩阵为，取基础变量为，令非基变量=0，解方程组得基础可行解同理得基础解：，。其中基础可行解为：，。将上解逐一带入原目标函数，得=0，=-3，=1，=，=8，=。其中=最大，所以，最优解为，最优值为=。（2）解：将上式化成标准形式，如下：从上式中可以得出系数矩阵为，取基础变量为，令非基变量=0，解方程组得基础可行解。当基变量为时，子矩阵为奇异矩阵，不是该题的基，其他的都为非奇异矩阵，共有19个基。类似上述，得其他基础解：，x(14)=(8/5,0,21/5,0,0,8/5)T，。其中基础可行解为：，x(14)=(8/5,0,21/5,0,0,8/5)T，。将上解逐一带入原目标函数，得=-9，=-1，=-9，=，Z14=3/5 , ，=-3，。其中=最小，所以，最优解为，最优值为=。4.用图解法和单纯形法求如下线性规划问题的最优解（1）解：解法（一）如图可知最优解为，最优值为。解法（二）将原线性规划问题化成标准形式：不难发现，这个标准形式已经是一个正规定价方程组了，它给出了一个初始基础可行解为,目标值为，列出单纯形初始表如下： 基础变量x1x2x3x4常数项x313107x442019-p-4-1000x305/21-1/419/4x111/201/49/4-p01019从初始表可以看出，,且负判别数对应列元素均有元素大于零者，故可求下一个基础可行解。选作进基变量，计算后得，定作旋转项，出基变量为，作一次旋转运算后得第二表，此时，第二表对应的基础可行解为，目标值。因此原LP问题的最优解为，最优值为。（2）解法（一）由图可知该线性规划的最优解为，它与可行域的顶点相对应，最优目标值。解法（二）将线性规划问题化成标准形式该线性规划问题没有基础可行解，故先增设非负人工变量，构造新的线性规划问题：列出的单纯形表如下：由基础表的最后一行判别数不难发现，基础变量的判别数不是零，这是不允许的，必须把它们冲零后，才可用非基础变量的判别数的正负来判定现行基础可行解是否最优，把表1、2、3行分别乘以-1后加到第四行上，得第二表。根据第二表有多个负判别数，取最小者-4所在列的作进基变量，比值最小者的，用1作旋转项进行旋转运算。如此迭代下去，直至所有判别式非负，得第五表。即为的最优解表，其最优解为，最优值。基础变量原有变量人工变量常数项x1x2x3x4x5x6x7x8x611-100100350x7100-10010125x821001001600-w000001110x611-100100350x7100-10010125x821001001600-w-4-211-1000-1075x601-1101-10225x1100-10010125x8010210-21350-w0-21-3-1040-575x601/2-10-1/210-1/250x111/2001/2001/2300x401/2011/20-11/2175-w0-1/2101/2013/2-50x201-20-120-1100x110101-101250x400111-1-11125-w000001110舍去第五表的人工变量部分，加上原目标函数系数于最后一行得原LP问题的单纯形表，该LP问题的初始可行解为，目标值为。基础变量x1x2x3x4x5常数项x201-20-1100x110101250x400111125-z230000x201-20-1100x110101250x400111125-z00401-800把基础变量列的判别系数冲零，得到第二表，所有判别式非负，此时的基础可行解即是最优解，最优目标值。（3）解法（一）由图可知该线性规划的最优解为，它与可行域的顶点对应，最优目标值。解法（二）构造新的线性规划：将初始表中基础变量的判别数冲零，变为第二表，迭代后得到第四表，第四表即为的最优解表，最优解为，目标值。基础变量原有变量人工变量常数项x1x2x3x4x5x6x521-10101x6340-1013/2-w0000110x521-10101x6340-1013/2-w-5-51100-5/2x111/2-1/201/201/2x605/23/2-1-3/210-w0-5/2-3/215/200x110-4/51/54/5-1/51/2x2013/5-2/5-3/52/50-w0000110舍去第四表的人工变量部分，加上目标函数系数于最后一行得原LP问题的单纯形表。将基础变量系数冲零得到第二表，判别数均为非负。此时的基础可行解是最优解，目标值。基础变量x1x2x3x4常数项x110-4/51/51/2x2013/5-2/50-z64000x211-4/51/51/2x1013/5-2/50-z0012/52/5-3（4）解：作图法知该线性规划问题无可行域，因此无最优解。（5）解法（一）由图可知该线性规划的目标函数等值线与其中一条边界平行，因此该线性规划问题有无穷多个最优解，最优目标值。解法（二）将原线性规划问题化为标准形式基础可行解为，目标值为0，经过迭代，得到一组最优解，目标值为。原LP问题的一组最优解为，最优目标值。5、某工厂生产过程中需要长度为3.2m、2.4m和1.6m的同种棒料毛坯分别为200根、100根和300根。现有的原料为9m长棒材，问如何下料可使废料最少？解：由题意可得出如下的下料方案表： 单位：根方案1方案2方案3方案4方案5方案6方案7方案8方案93.2m0000111222.4m0312012011.6m514232010废料1m0.2m0.2m1m1m0.2m1m1m0.2m现考虑九种下料方案的可行性。九种方案产生的废料有1m和0.2m两种区分，而本题从废料最少的角度出发，所以废料为0.2m的方案严格优于废料为1m的方案，理性的厂商会选择废料为0.2m的方案，故可行的下料方案表如下： 单位：根方案1方案2方案3方案43.2m21002.4m11311.6m0214废料0.2m0.2m0.2m0.2m设四种下料方案所用的原料棒材根数分别为X1、X2、X3、X4，根据题意及上表可以得出线性规划模型：Min Z=0.2 X1+0.2X2+0.2X3+0.2X4s.t. 2 X1+ X2 200 X1+ X2+3 X3+ X4 100 2 X2+ X3+4 X4 300 Xi0（i=1,2,3,4）运用对偶单纯形法求解上述数学模型：先将此问题化为下列形式：Max P=0.2 X10.2X20.2X30.2X4s.t. 2 X1X2 + X5 =200 X1X23 X3X4 + X6 =100 2 X2X34 X4+ X7=300 Xi0（i=1,2,3,7）建立此问题的初始单纯形表并进行运算如下：Cj-0.2-0.2-0.2-0.2000CBXBbX1X2X3X4X5X6X70X5-200-2-1001000X6-100-1-1-3-10100X7-3000-2-1-4001-0.2-0.2-0.2-0.20000.10.20.05Cj-0.2-0.2-0.2-0.2000CBXBbX1X2X3X4X5X6X70X5-200-2-1001000X6-25-1-1/2-11/4001-1/4-0.2X47501/21/4100-1/4-0.2-0.1-0.15000-0.050.10.1Cj-0.2-0.2-0.2-0.2000CBXBbX1X2X3X4X5X6X7-0.2X110011/200-1/2000X67500-11/40-1/21-1/4-0.2X47501/21/4100-1/400-0.150-0.10-0.05所以：X* = (100，0，0，75)T Z* = 100×（-0.2）+75×（-0.2）=35即：按照方案1下料100根，按照方案4下料75根，可使废料最少，为35m 。6、某贸易公司需要4个月的销售旺季租用仓库，各个月所需仓库面积如表2-16所示，仓库租借合同月初可以办理，租借费用随租借时间和面积的不同而不同，同样的面积，连续租用时间越长，费用折扣越大，具体价格如表2-17所示。根据上述条件，建立一个线性规划的数学模型，使得仓库租借费用最小（不求解）。表2-16 月份1234仓库面积/ m21500200022001500表2-17合同租借期限1个月2个月3个月4个月仓库面积/ m220365062解：设在i月租j个月的仓库的面积为Xij，由题意得：租用时长1个月2个月3个月4个月1月X11X12X13X142月X21X22X233月X31X324月X41决策时点根据上表可以建立如下线性规划模型：Min Z=20（X11+ X21+ X31+ X41）+36（X12+ X22+ X32）+50（X13+ X23）+62 X14s.t. X11 +X12 +X13 +X14=1500 X12 +X13 +X14 +X21 +X22 +X23=2000 X13 +X14+X22 +X23+ X31 +X32=2200 X14 +X23+ X32+ X41=1500 Xij0（i，j=1,2,3,4）答案为：第1月租1500平方米，租期4个月；第2月租500平方米，租期2个月；第3月租200平方米，租期1个月；租借费用最小，11500元。7.解：设应采用的电视台（a）、电视台（b）、每日晨报、星期日报、广播电台的次数分别为，构造线性规划如下：将原线性规划分为两个子线性规划：和用图解法解这两个子线性规划，由图知最优解分别为：，因此取。原规划的最优解为：，最优值为。8.把推销人员最高可用公式改成2500h.设公司下月在航空商场经销台，在铁路商场经销台，在水上商场经销台，可以得到：解得：
