运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用习题解答习题一P461.1(a)该问题有无穷多最优解，即满足210664221xxx且的所有21,xx，此时目标函数值3z。(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。1.2(a)约束方程组的系数矩阵1000030204180036312A基基解是否基可行解目标函数值654321xxxxxx321ppp00067-3160否421ppp0070010是10521ppp0270030是3014232x1x02x1x123413266421xx42421xx621ppp421000447否431ppp0082500否531ppp0802300是3631ppp3002101否541ppp053000是0641ppp415020045否最优解Tx0,0,7,0,10,0。(b)约束方程组的系数矩阵21224321A基基解是否基可行解目标函数值4321xxxx21pp002114否31pp0511052是54341pp6110031否32pp02210是542pp20210否43pp1100是5最优解Tx0,511,0,52。1.3(a)(1)图解法最优解即为8259432121xxxx的解23,1x，最大值235z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式825943..00510max4213214321xxxxxxtsxxxxz则43,PP组成一个基。令021xx得基可行解8,9,0,0x，由此列出初始单纯形表jc00501Bc基b4321xxxx903x0143804x102]5[jjzc0050121。5839,58minjc00501Bc基b4321xxxx51203x531514058101x51052102x1x1234132jjzc201002，2328,1421min新的单纯形表为jc00501Bc基b4321xxxx2352x143145101101x727101jjzc1425145000,21，表明已找到问题最优解0,0,231,4321xxxx。最大值235*z(b)(1)图解法最优解即为524262121xxxx的解23,27x，最大值217z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max2000515..62245zxxxxxxxstxxxxxx02x1x36912396521xx242621xx则3P，4P，5P组成一个基。令021xx得基可行解0,0,15,24,5x，由此列出初始单纯形表jc21000Bc基b1x2x3x4x5x03x1504x2405x505100[6]201011001jjzc2100021。245min,,461jc21000Bc基b1x2x3x4x5x03x1524x405x10510011301600230161jjzc013013002，1533min,24,522新的单纯形表为jc21000Bc基b1x2x3x4x5x03x1520015415224x7205x3210014120101432jjzc00014120,21，表明已找到问题最优解11x，272x，3152x，40x，50x。最大值*172z1.6(a)在约束条件中添加松弛变量或剩余变量，且令0,0''2'2''2'22xxxxx，zzxx',3'3该问题转化为0,,,,,633824124332x..0023'max54'3''2'21'3''2'215'3''2'214'3''2'2154'3''2'21xxxxxxxxxxxxxxxxxxxtsxxxxxxz其约束系数矩阵为003113102114014332A在A中人为地添加两列单位向量87,PP100031130110211400014332令7654'3''2'210023'maxMxMxxxxxxxz得初始单纯形表jcMM002113Bc基b7654'3''2'21xxxxxxxx2104x000143328M6x011-02-1146M7x10003-113jjzc00M0M52117M3(b)在约束条件中添加松弛变量或剩余变量，且令''''''333330,0xxxxx，'zz该问题转化为'''123345'''12334'''12335'''1233'''123345max'3500x2623316..5510,,,,,0zxxxxxxxxxxxxxxxstxxxxxxxxxx其约束系数矩阵为121110213301115500A在A中人为地添加两列单位向量87,PP121110102133010011550001令'''12334567max'3500zxxxxxxMxMx得初始单纯形表jc3-51-100-MMBc基b12334567xxxxxxxx66Mx121-1-10105016x213-30100710Mx115-50001jjzc32531+6-1-6-000MMMMM1.7(a)解1：大M法在上述线性规划问题中分别减去剩余变量468,,,xxx再加上人工变量579,,,xxx得123456789max22000zxxxxMxxMxxMx1234513672389123456789622,,20,,,,,,,,0xxxxxxxxxstxxxxxxxxxxxxx其中M是一个任意大的正数。据此可列出单纯形表jc212000MMMi   bcb基123456789xxxxxxxxx579620MxMxMx1111100002010011000[2]100001160jjcz2312000MMMMMM5726210MxMxx103/211001/21/220[1]001100011/200001/21/242jjcz531132000222222MMMMMM53232211Mxxx[4]00113/23/21/21/2201001100110001/21/21/21/23/4jjcz3353113450002222MMMMMM13223/427/217/4xxx1001/41/43/83/81/81/80011/21/21/41/41/41/40101/41/41/81/83/83/8jjcz53990005/43/84888MMM由单纯形表计算结果可以看出，40且40(1,2,3)iai，所以该线性规划问题有无界解解2：两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量468,,,xxx再加上人工变量579,,,xxx得第一阶段的数学模型据此可列出单纯形表jc000010101i   bcb基123456789xxxxxxxxx579161210xxx1111100002010011000[2]100001160jjcz131101010572161200xxx103/211001/21/220[1]001100011/200001/21/242jjcz13105/2101022532130201xxx[4]00113/23/21/21/2201001100110001/21/21/21/23/4jjcz00001010113223/427/217/4xxx1001/41/43/83/81/81/80011/21/21/41/41/41/40101/41/41/81/83/83/8jjcz000010101第一阶段求得的最优解*T377X(,,,0,0,0,0,0,0)442,目标函数的最优值*0。因人工变量5790xxx，所以*T377(,,,0,0,0,0,0,0)442X是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。jjcz2120000i   bcb基123468xxxxxx13223/427/217/4xxx1001/43/81/80011/21/41/40101/41/83/8jjcz0005/43/89/8由表中计算结果可以看出，40且40(1,2,3)iai，所以原线性规划问题有无界解。(b)解1：大M法在上述线性规划问题中分别减去剩余变量468,,,xxx再加上人工变量579,,,xxx得1234567min2300zxxxxxMxMx123461257123456789428326,,,,,,,,,,0xxxxxxxxxstxxxxxxxxx其中M是一个任意大的正数。据此可列出单纯形表jc212000MMMi   bcb基1234567xxxxxxx6786MxMx1[4]21010320010123jjcz24361200MMMMM27322xMx1/411/21/401/40[5/2]011/211/2184/5jjcz5513133004224224MMMMM2139/524/5xx013/53/101/103/101/10102/51/52/51/52/5jjcz0001/21/21/21/2MM由单纯形表计算结果可以看出，最优解*T49(,,0,0,0,0,0)55X，目标函数的最优解值*4923755z。X存在非基变量检验数30，故该线性规划问题有无穷多最优解。解2：两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量45,,xx再加上人工变量67,,xx得第一阶段的数学模型67minxx123461257123456789428326,,,,,,,,,,0xxxxxxxxxstxxxxxxxxx据此可列出单纯形表jc0000011i   bcb基1234567xxxxxxx671816xx1[4]21010320010123jjcz4621100270212xx1/411/21/401/40[5/2]011/211/2184/5jjcz5/2011/213/202109/504/5xx013/53/101/103/101/10102/51/52/51/52/5jjcz0000011第一阶段求得的最优解*T49(,,0,0,0,0,0)55X,目标函数的最优值*0。因人工变量670xx，所以T49(,,0,0,0,0,0)55是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。j