资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
快乐运筹学基础及应用习题解答习题一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精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 1 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐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) 图解法精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 2 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐最优解即为8259432121xxxx的解23, 1x,最大值235z(2)单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式825943.00510max4213214321xxxxxxtsxxxxz则43,PP组成一个基。令021xx得基可行解8, 9,0,0 x,由此列出初始单纯形表jc00501Bc基b4321xxxx903x0143804x102 5jjzc0050121。5839,58minjc00501Bc基b4321xxxx51203x531514058101x5105210 2x1x1 2 3 4 1 3 2 精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 3 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐jjzc201002,2328,1421min新的单纯形表为jc00501Bc基b4321xxxx2352x143145101101x727101jjzc1425145000,21,表明已找到问题最优解0,0,231,4321xxxx。最大值235*z(b) (1) 图解法最优解即为524262121xxxx的解23,27x,最大值217z(2) 单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式1234523124125max2000515. . 62245zxxxxxxxstxxxxxx0 2x1x3 6 9 12 3 9 6 521xx242621xx精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 4 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐则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 3x15 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精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 5 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐2 4x720 5x321 0 0 14120 1 0 1432jjzc0 0 0 14120,21,表明已找到问题最优解11x,272x,3152x,40 x,50 x。最大值*172z1.6 (a) 在 约 束 条 件 中 添 加 松 弛 变 量 或 剩 余 变 量 , 且 令0,0 22 222xxxxx,zzxx,33该问题转化为0,633824124332x. .0023max543 2213 22153 22143 221543 221xxxxxxxxxxxxxxxxxxxtsxxxxxxz其约束系数矩阵为003113102114014332A在A中人为地添加两列单位向量87,PP100031130110211400014332令76543 2210023maxMxMxxxxxxxz得初始单纯形表jcMM002113Bc基b76543 221xxxxxxxx2104x000143328M6x011-02-1146M7x10003-113精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 6 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐jjzc00M0M52117M3(b) 在约束条件中添加松弛变量或剩余变量,且令333330,0 xxxxx, zz该问题转化为12334512334123351233123345max3500 x2623316. . 5510,0zxxxxxxxxxxxxxxxstxxxxxxxxxx其约束系数矩阵为121110213301115500A在A中人为地添加两列单位向量87,PP121110102133010011550001令12334567max3500zxxxxxxMxMx得初始单纯形表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得精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 7 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐123456789max22000zxxxxMxxMxxMx1234513672389123456789622, ,20,0 xxxxxxxxxs txxxxx xxxx xx xx其中 M 是一个任意大的正数。据此可列出单纯形表jc212000MMMibcb基123456789xxxxxxxxx579620MxMxMx11111000020100110002100001160jjcz2312000MMMMMM5726210MxMxx103/ 211001/ 21/ 2201001100011/ 200001/ 21/ 242jjcz531132000222222MMMMMM53232211Mxxx400113/ 23/ 21/ 21/ 2201001100110001/ 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再 加上 人 工 变 量精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 8 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐579,xxx得第一阶段的数学模型据此可列出单纯形表jc000010101ibcb基123456789xxxxxxxxx579161210 xxx11111000020100110002100001160jjcz131101010572161200 xxx103/ 211001/ 21/ 2201001100011/ 200001/ 21/ 242jjcz13105/ 2101022532130201xxx400113/ 23/ 21/ 21/ 2201001100110001/ 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。因人工变量5790 xxx,所以*T3 7 7(,0,0,0,0,0,0)4 4 2X是原线性规划问题的基可行解。 于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消,并填入原问题的目标函数的系数,进行第二阶段的运算,见下表。jjcz2120000ibcb基123468xxxxxx精品p d f 资料 - - - 欢迎下载 - - - - - - - - - - - - - - -欢迎下载 名师归纳 - - - - - - - - - -第 9 页,共 24 页 - - - - - - - - - - 精品学习资料 - - -p d f 精品资料 - - - - - - - - - - - - - - -快乐13223/ 427 / 217/ 4xx
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号