《2022年运筹学基础及应用第四版胡运权主编课后练习答案【精】》由会员分享,可在线阅读,更多相关《2022年运筹学基础及应用第四版胡运权主编课后练习答案【精】(24页珍藏版)》请在金锄头文库上搜索。
1、快乐运筹学基础及应用习题解答习题一P46 1.1 (a) 该问题有无穷多最优解,即满足210664221xxx且的所有21,xx,此时目标函数值3z。(b) 用图解法找不到满足所有约束条件的公共范围,所以该问题无可行解。1.2 (a)约束方程组的系数矩阵1000030204180036312A基基解是否基可行解目标函数值654321xxxxxx321ppp00067-3160否421ppp0070010是10 521ppp0270030是3 0 1 4 2 3 2x1x0 2x1x1 2 3 4 1 3 2 66421xx42421xx精选学习资料 - - - - - - - - - 名师归纳
2、总结 - - - - - - -第 1 页,共 24 页快乐621ppp421000447否431ppp0082500否531ppp0802300是3 631ppp3002101否541ppp053000是0 641ppp415020045否最优解Tx0 ,0,7, 0,10, 0。(b) 约束方程组的系数矩阵21224321A基基解是否基可行解目标函数值4321xxxx21pp002114否31pp0511052是54341pp6110031否32pp02210是542pp20210否43pp1100是5最优解Tx0,511,0,52。1.3(a) (1) 图解法精选学习资料 - - - -
3、 - - - - - 名师归纳总结 - - - - - - -第 2 页,共 24 页快乐最优解即为8259432121xxxx的解23, 1x,最大值235z(2)单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式825943.00510max4213214321xxxxxxtsxxxxz则43,PP组成一个基。令021xx得基可行解8, 9,0,0x,由此列出初始单纯形表jc00501Bc基b4321xxxx903x0143804x102 5jjzc0050121。5839,58minjc00501Bc基b4321xxxx51203x531514058101x5105210 2x
4、1x1 2 3 4 1 3 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 24 页快乐jjzc201002,2328,1421min新的单纯形表为jc00501Bc基b4321xxxx2352x143145101101x727101jjzc1425145000,21,表明已找到问题最优解0,0,231,4321xxxx。最大值235*z(b) (1) 图解法最优解即为524262121xxxx的解23,27x,最大值217z(2) 单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式1234523124125max2000
5、515. . 62245zxxxxxxxstxxxxxx0 2x1x3 6 9 12 3 9 6 521xx242621xx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页,共 24 页快乐则3P,4P,5P组成一个基。令021xx得基可行解0,0,15,24,5x,由此列出初始单纯形表jc2 1 0 0 0Bc基b1x2x3x4x5x0 3x15 0 4x24 0 5x5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 jjzc2 1 0 0 021。24 5min,461jc2 1 0 0 0Bc基b1x2x3x4x5x0 3
6、x15 2 4x4 0 5x1 0 5 1 0 0 1 130 160 0 230 161 jjzc0 130 13002,1533min,24,522新的单纯形表为jc2 1 0 0 0Bc基b1x2x3x4x5x0 3x1520 0 1 54152精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 24 页快乐2 4x720 5x321 0 0 14120 1 0 1432jjzc0 0 0 14120,21,表明已找到问题最优解11x,272x,3152x,40x,50x。最大值*172z1.6 (a) 在 约 束 条 件 中 添 加
7、 松 弛 变 量 或 剩 余 变 量 , 且 令0,0 22 222xxxxx,zzxx,33该问题转化为0,633824124332x. .0023max543 2213 22153 22143 221543 221xxxxxxxxxxxxxxxxxxxtsxxxxxxz其约束系数矩阵为003113102114014332A在A中人为地添加两列单位向量87,PP100031130110211400014332令76543 2210023maxMxMxxxxxxxz得初始单纯形表jcMM002113Bc基b76543 221xxxxxxxx2104x000143328M6x011-02-114
8、6M7x10003-113精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 24 页快乐jjzc00M0M52117M3(b) 在约束条件中添加松弛变量或剩余变量,且令333330,0xxxxx, zz该问题转化为12334512334123351233123345max3500x2623316. . 5510,0zxxxxxxxxxxxxxxxstxxxxxxxxxx其约束系数矩阵为121110213301115500A在A中人为地添加两列单位向量87,PP121110102133010011550001令12334567max3500
9、zxxxxxxMxMx得初始单纯形表jc3 -5 1 -1 0 0 -M MBc基b12334567xxxxxxxx6 6Mx1 2 1 -1 -1 0 1 050 16x2 1 3 -3 0 1 0 07 10Mx1 1 5 -5 0 0 0 1jjzc32 53 1+6 -1-6 - 0 0 0MMMMM1.7 (a)解 1:大 M 法在上述线性规划问题中分别减去剩余变量468,xxx再加上人工变量579,xxx得精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 24 页快乐123456789max22000zxxxxMxxMxxMx
10、1234513672389123456789622, ,20,0xxxxxxxxxs txxxxx xxxx xx xx其中 M 是一个任意大的正数。据此可列出单纯形表jc212000MMMibcb基123456789xxxxxxxxx579620MxMxMx11111000020100110002100001160jjcz2312000MMMMMM5726210MxMxx103/ 211001/ 21/ 2201001100011/ 200001/ 21/ 242jjcz531132000222222MMMMMM53232211Mxxx400113/ 23/ 21/ 21/ 22010011
11、00110001/ 2 1/ 21/ 21/ 23/ 4jjcz33531 13450002222MMMMMM13223/ 427 / 217/ 4xxx1001/ 41/ 43/ 83/ 81/ 81/ 80011/ 21/ 21/ 41/ 41/ 41/ 40101/ 41/ 41/ 81/ 83/ 83/8jjcz53990005 / 43/ 84888MMM由单纯形表计算结果可以看出,40且40(1,2,3)iai,所以该线性规划问题有无界解解 2:两阶段法。现 在 上 述 线 性 规 划 问 题 的 约 束 条 件 中 分 别 减 去 剩 余 变 量468,xxx再 加 上 人 工
12、变 量精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 24 页快乐579,xxx得第一阶段的数学模型据此可列出单纯形表jc000010101ibcb基123456789xxxxxxxxx579161210xxx11111000020100110002100001160jjcz131101010572161200xxx103/ 211001/ 21/ 2201001100011/ 200001/ 21/ 242jjcz13105/ 2101022532130201xxx400113/ 23/ 21/ 21/ 220100110011000
13、1/ 2 1/ 21/ 21/ 23/ 4jjcz00001010113223/ 427 / 217/ 4xxx1001/ 41/ 43/ 83/ 81/ 81/ 80011/ 21/ 21/ 41/ 41/ 41/ 40101/ 41/ 41/ 81/ 83/ 83/8jjcz000010101第一阶段求得的最优解*T3 7 7X(,0,0,0,0,0,0)4 4 2,目标函数的最优值*0。因人工变量5790xxx,所以*T3 7 7(,0,0,0,0,0,0)4 4 2X是原线性规划问题的基可行解。 于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消,并填入原问题的目标函数的系数
14、,进行第二阶段的运算,见下表。jjcz2120000ibcb基123468xxxxxx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 24 页快乐13223/ 427 / 217/ 4xxx1001/ 43/81/ 80011/ 21/ 41/ 40101/ 41/ 83/8jjcz0005 /43 / 89 /8由表中计算结果可以看出,40且40(1,2,3)iai,所以原线性规划问题有无界解。(b)解 1:大 M 法在上述线性规划问题中分别减去剩余变量468,xxx再加上人工变量579,xxx得1234567min2300zxxxx
15、xMxMx123461257123456789428326, ,0xxxxxxxxxs tx xxxx xx xx其中 M 是一个任意大的正数。据此可列出单纯形表jc212000MMMibcb基1234567xxxxxxx6786MxMx1421010320010123jjcz24361200MMMMM27322xMx1/ 411 / 21/ 401/ 405 / 2011 / 211/ 2184 / 5jjcz5513133004224224MMMMM2139 /524 / 5xx013 / 53 /101 /103 /101 /10102 / 51/ 52 / 51/ 52 / 5jjcz
16、0001/ 21 / 21/ 21/ 2MM由单纯形表计算结果可以看出,最优解*T4 9(,0,0,0,0,0)5 5X,目标函数的最优解值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 24 页快乐*4923755z。X 存在非基变量检验数30, 故该线性规划问题有无穷多最优解。解 2:两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量45,xx再加上人工变量67,xx得第一阶段的数学模型67minxx123461257123456789428326, ,0xxxxxxxxxs tx xxxx xx xx据此可列出单纯形表j
17、c0000011ibcb基1234567xxxxxxx671816xx1421010320010123jjcz4621100270212xx1/ 411 / 21/ 401/ 405 / 2011/ 211/ 2184 / 5jjcz5 / 2011 / 213 / 202109 / 504 / 5xx013 /53 /101 /103 /101 /10102 / 51/ 52 / 51 / 52 / 5jjcz0000011第一阶段求得的最优解*T4 9(,0,0,0,0,0)5 5X,目标函数的最优值*0。因人工变量670xx,所以T4 9(,0,0,0,0,0)5 5是原线性规划问题的基
18、可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消,并填入原问题的目标函数的系数,进行第二阶段的运算,见下表。jjcz23100ibcb基12345xxxxx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 24 页快乐2139 / 524 / 5xx013 /53 /101/ 10102 / 51/ 52 / 5jjcz0001/ 21/ 2由单纯形表计算结果可以看出,最优解*T4 9(,0,0,0,0,0)5 5X,目标函数的最优解值*4923755z。由于存在非基变量检验数30,故该线性规划问题有无穷多最优解。1
19、.8 表 1-23 54321xxxxx64x012-4215x10231jjzc00213表 1-24 54321xxxxx31x02112115x121150jjzc0235701.10 000453654321xxxxxx3852x0031013231405x0132503432906x10324035jjzc00354031654321xxxxxx3852x00310132151443x05115210154精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 24 页快乐158906x154152001541jjzc0541517
20、001511654321xxxxxx415052x41104184115010416243x414415416100418931x41154112412001jjzc411141244145000最后一个表为所求。习题二P76 2.1写出对偶问题(a) 无约束3213214321321321,0,534332243. .422minxxxxxxyxxxxxxtsxxxz对偶问题为:无约束321321321321321, 0,0433424322. .532max yyyyyyyyyyyytsyyyw(b) 0,0,837435522. .365max 321321321321321xxxxxx
21、xxxxxxtsxxxz无约束对偶问题为:0,0,332675254. .835min321321321321321yyyyyyyyyyyytsyyyw无约束2.2 (a)错误。原问题存在可行解,对偶问题可能存在可行解,也可能无可行解。(b)错误。线性规划的对偶问题无可行解,则原问题可能无可行解,也可能为无界解。(c)错误。(d)正确。2.6 对偶单纯形法(a) 0,52233. .18124min3213231321xxxxxxxtsxxxz解:先将问题改写为求目标函数极大化,并化为标准形式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页
22、,共 24 页快乐5, 1052233. .0018124max 53243154321ixxxxxxxtsxxxxxzi列单纯形表,用对偶单纯形法求解,步骤如下jc0018124Bc基b54321xxxxx304x01301505x10220jjzc0018124304x0130125122x210110jjzc606041183x031103123122x21310131jjzc62002最优解为Tx23, 1 ,0, 目标值39z。(b) 0,10536423. .425min321321321321xxxxxxxxxtsxxxz解:先将问题改写为求目标函数极大化,并化为标准形式5, 1
23、010536423. .00425max 5321432154321ixxxxxxxxxtsxxxxxzi列单纯形表,用对偶单纯形法求解jc00425精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页,共 24 页快乐Bc基b54321xxxxx404x012131005x10536jjzc004253204x311310131022x3103512jjzc3203201243x13103022x25013jjzc02001最优解为Tx2,0 ,0, 目标值8z。2.8 将该问题化为标准形式:5, 10426. .002max52143215
24、4321ixxxxxxxxtsxxxxxzi用单纯形表求解jc00112Bc基b54321xxxxx604x01111405x10021jjzc001126Bc基b54321xxxxx621x011110105x11130jjzc021-30精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页,共 24 页快乐由于0j,所以已找到最优解10, 0, 0,0,6*X,目标函数值12*z(a) 令目标函数112233max2zxxx()(-1+)(1+ )(1)令230,将1反映到最终单纯形表中jc121 1 0 0Bc基b54321xxxxx62
25、41x1 1 1 1 01005x11130jjzc0-2-1-3-0111表中解为最优的条件:0-3-1,0-1-1,0-21,从而11(2)令031,将2反映到最终单纯形表中jc001122Bc基b54321xxxxx621x1 1 1 1 01005x11130jjzc021-3-02表中解为最优的条件:03-2, 从而32(3) 令021,将3反映到最终单纯形表中jc001123Bc基b54321xxxxx621x1 1 1 1 01005x11130jjzc021-3-03表中解为最优的条件:01-3, 从而13精选学习资料 - - - - - - - - - 名师归纳总结 - -
26、- - - - -第 16 页,共 24 页快乐(b) 令线性规划问题为3, 10426.2max5214321321ixxxxxxtsxxxzi(1)先分析的变化111101101bBb使问题最优基不变的条件是010611bb,从而61(2)同理有01062,从而102(c) 由于)10, 0, 0, 0, 6(x代入26231xx,所以将约束条件减去剩余变量后的方程22631xxx直接反映到最终单纯形表中jc2 -1 1 0 0 0 Bc基b1x2x3x4x5x6x2 1x6 0 5x10 1 1 1 1 0 0 0 3 1 1 1 0 0 6x-2 1 0 -2 0 0 1 jjzc0
27、-3 -1 -2 0 0 对表中系数矩阵进行初等变换,得jc2 -1 1 0 0 0 Bc基b1x2x3x4x5x6x2 1x6 0 5x10 111 1 0 0 0 3 1 1 1 0 0 6x-8 0 -1 -3 -1 0 1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页,共 24 页快乐jjzc0 -3 -1 -2 0 0 jc2 -1 1 0 0 0 Bc基b1x2x3x4x5x6x2 1x1030 5x2231 230 230 130 830 231 130 6x830 131 130 13jjzc0 830 530 13因此
28、增加约束条件后,新的最优解为1103x,383x,5223x,最优值为2832.12 (a) 线性规划问题0,3054345536. .43max321321321321xxxxxxxxxtsxxxz单纯形法求解Bc基b54321xxxxx5404x015360305x10543jjzc004135104x11013643x51015453jjzc540051153531x31310311343x5251110精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页,共 24 页快乐jjzc5351020最优解为3,0,5,321xxx,目标值27
29、z。(a) 设产品 A 的利润为 3,线性规划问题变为0,3054345536. .43max321321321321xxxxxxxxxtsxxxz单纯形法求解基b54321xxxxx544x01536035x10543jjzc00413514x1101363x51015453jjzc54005115351x3131031133x5251110jjzc3533510320为保持最优计划不变,应使32,3151,3153都小于等于0,解得5953。(b) 线性规划问题变为0,302543458536.343max4321432143214321xxxxxxxxxxxxtsxxxxz单纯形法求解B
30、c基b654321xxxxxx5405x0185360306x102543精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页,共 24 页快乐jjzc0034135104x116013643x5105215453jjzc54057051153531x313120311343x525154110jjzc5351510202504x6161106121543x15815101151352jjzc3017307001529101此时最优解为5,0, 0,321xxx,目标值20z,小于原最优值,因此该种产品不值得生产 。(c) 设购买材料数量为y
31、,则规划问题变为0,3054345536. .4.043max321321321321yxxxyxxxxxxtsyxxxz单纯形法求解Bc基b54321xxyxxx5405x0105360306x101543jjzc00524135104x111013643x5105115453jjzc54052051153531x3131310311精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页,共 24 页快乐343x525152110jjzc535151020510y111013943x051015356jjzc5252005953此时最优解为15
32、, 9, 0, 0,321yxxx,目标值30z,大于原最优值,因此应该购进原材料扩大生产,以购材料15 单位为宜。第三章3.1 表 3.36 用 vogel 法求解得B A B1 B2 B3 B4 A1 A2 A3 A4 144 24 60 11 用位势法检验,把上表中有数字的地方换成运价B A B1 B2 B3 B4 Ui A1 A2 A3 A4 8 13 12 8 11 11 12 8 8 7 7 产地销地B1 B2 B3 B4 产量A1 A2 A3 A4 9 8 12 13 10 10 12 14 8 9 11 12 10 10 11 12 18 24 6 12 销量6 14 35 5
33、 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页,共 24 页快乐Vj 1 0 4 5 令 v1=1 则 u1+v2=8 所以 u3=7 u1+v4=13 v3=4 u2+v3=12 u4=7 u3+v1=8 v5=8 u3+v3=11 u2=8 u4+v3=11 v2=0 u4+v4=12 得检验数表B A B1 B2 B3 B4 A1 A2 A3 A4 00 1 2 1 2 0 2 3 表中所有的数字均大于等于零,故所求方案为最优方案3.3 解: (a)用运价代替表3.39 中有数字的地方,求出位势和检验数B A B1 B2 B3 B
34、4 Ui A1 A2 A3 1 11 12 k 9 2 12-k 11 1 Vj 1 k-11 -2 k-1 令 v1=1 则 u1+v2=1 故 v3=-2 u1+v4=11 u2=11 u2+v1=12 v2=k-11 u2+v2=k u1=12-k u2+v3=9 v4=k-1 u3+v1=2 u3=1 得检验数表B A B1 B2 B3 B4 A1 A2 A3 k-3 10-k 30-k 24-k 15 18-k 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页,共 24 页快乐令表中所有的检验数均大于等于零,得3k10 (b)由表
35、 3.39 和表 3.40 计算出位势和检验数,令C24=M 位势表B A B1 B2 B3 B4 Ui A1 A2 A3 1 11 12 7 9 2 5 11 1 Vj 1 -4 -2 6 检验数表B A B1 B2 B3 B4 A1 A2 A3 417 M-17 17 17 11 当存在某非基变量的检验数大于等于零的时候有无穷多最优解则 M-17=0 所以 M=17 故运价 C24=17 3.5 销地产地A1 A2 A3 供应量B1 B1B2 B2B3 B3S 500 540 580 570 610 650 M 600 640 M 670 710 M M 550 M M 620 40 80
36、 120 2 3 4 2 1 3 2 销量3 3 4 由于产大于销,设有一个理想的销地A4,则销地产地A1 A2 A3 A4 供应量精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页,共 24 页快乐B1 B1B2 B2B3 B3S 500 540 580 0 570 610 650 0 M 600 640 0 M 670 710 0 M M 550 0 M M 620 0 40 80 120 0 2 3 4 2 1 3 2 销量3 3 4 7 第四章略第五章5.4 解:Min z=P1 d1- +P2(d2-+d2+) s.t. 11x1+
37、3x225 100 x1+50x2 + d1- - d1+ =1900 10x1+16x2 + d2- - d2+ =200 x1,x2, d1- ,d1+ , d2- ,d2+ 0 5.6 解:目标规划模型为Min z = P1 d1- +P2(d2-+d2+) +P2(d3-+d3+) +P3(d4-+d4+) +P3d5+s.t. 300 x1+450x2 + d1- - d1+ =10000 x1+ d2- - d2+ =10x2 + d3- - d3+ =154x1+6x2 + d4- - d4+ =1503x1+2x2 + d5- - d5+ =75x1,x2, d1- ,di+ , di-0 ,i=1, 5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页,共 24 页