1、运筹学基础及应用 习题解答习题一 P46 1.1 (a)02x 1x1 2 34132 6421x41x该问题有无穷多最优解，即满足 的所有 ，此时目标函数值0且 21,x。3z(b) 0 1 4232x 1x用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。1.2 (a) 约束方程组的系数矩阵 103241862A基解基 654321 xx是否基可行解 目标函数值 321p 067-0否 4 是 10521 23是 3621p 421 0 4 7否 43 8 250 否 51p 0 3 是 3 63 3 210 否 541p 05是 06 41 45否最优解 。Tx0,71,(b
2、) 约束方程组的系数矩阵 243A基解基 4321xx是否基可行解 目标函数值 21p04否 3 5 0是 543 41p61 31否 32 0 2 0是 5 4p 1 否 3 0是 5最优解 。Tx,5121.3 (a)(1) 图解法02x 1x1 2 34132最优解即为 的解 ，最大值8259431x2,1x235z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式 825943 . 010max34xtsz则 组成一个基。令43,P021x得基可行解 ，由此列出初始单纯形表8,90xjc 0 51基 Bb432xx903x 4 38 4 105jzc 1。215839,
3、minjc 0 01基 Bb432xx52 03x 5 154 058 10x 51 0 521jzc2 0，02238,14min新的单纯形表为 jc 0 50基 Bb4321xx23 5x 1 010 72 1jzc145 0，表明已找到问题最优解 。最大值 0,21 0 , ,23 , 41 xx 235*z(b) (1) 图解法02x 1x3 6 912396521x最优解即为 的解 ，最大值52461x23,7x27z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式461x123451245max 0. 6zxxst则 ， ， 组成一个基。令3P4 021x得基可
4、行解 ，由此列出初始单纯形表0,4,xjc2 1 0 0 0基 Bb x34x50 153x0 2440 5x0 5 1 0 06 2 0 1 01 1 0 0 1jzc2 1 0 0 0。2145min,61jc2 1 0 0 0基 Bb x34x50 153x2 40 15x0 5 1 0 01 0 0360 0 12jzc0 0 03，0215min,24新的单纯形表为 jc2 1 0 0 0基 Bcb 1x234x50 3x522 470 5x0 0 1 21 0 0 40 1 0 3jzc0 0 0 12，表明已找到问题最优解 ， ， ， ， 。最0,211x73152x405x大值
5、 *7z1.6(a) 在约束条件中添加松弛变量或剩余变量，且令 ，0, 222xxzx ,3该问题转化为 0,633824142x . 0 ma541 1 543 xts xxz其约束系数矩阵为 03131242A在 中人为地添加两列单位向量 87,P103132442令 765432 max Mxxxz 得初始单纯形表 jc 0 2 1 3 基 Bcb 7654321 xxxx2 04x 0138M6 - 0- 4 7 131jzc 0 M 52 7M3(b) 在约束条件中添加松弛变量或剩余变量，且令 ，333 0,xxz该问题转化为 1234512354max 5061. ,0xxstxx
6、其约束系数矩阵为 121350A在 中人为地添加两列单位向量 87,P121305令 1234567max 0zxxMx得初始单纯形表 jc -5 1 - 0 - 基 Bb1234567xxxx6 Mx - 1 1 050 07 10x 5 - jzc32 5 1+6 - 0 MM1.7(a)解 1：大 M 法在上述线性规划问题中分别减去剩余变量 再加上人工变量 得468,x579,x1234579max00zxM1367289452,0stxx其中 M 是一个任意大的正数。据此可列出单纯形表jc21200MMb基 123456789xxxxxi579620xM 10010 0160jjcz3
7、12MM572610x0/1/2/20101/201/ 42jjcz53 30 2M 5321Mx413/20101 /1/ /4jjcz 353345022MM132/7/4x11/4/8/18/14400/3/jjcz 53900/4/88MM由单纯形表计算结果可以看出， 且 ，所以该线性规划问题有无界4(1,23)ia解解 2：两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量 再加上人工变量468,x得第一阶段的数学模型579,x据此可列出单纯形表jc0010101b基 123456789xxxxxi5791620x10010 0160jjcz131572160x0/21/2/
8、20101/ 0/1/42jjcz 30521253210x4 3/20101 /1/ /4jjcz0 0132/47/x101/43/8/18/21440/3/jjcz0001第一阶段求得的最优解 ,目标函数的最优值 。* T37X(,)42 *因人工变量 ，所以 是原线性规划问题的基可579x* T7(,)4行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。 jjcz21200b基 123468xxxi132/47/x01/3/1/24/jjcz0054389由表中计算结果可以看出， 且 ，所以原线性规划问题有无界解。44(1,2)ia(b)解 1：大 M 法在上述线性规划问题中分别减去剩余变量 再加上人工变量 得468,x579,x123457min0zxxM61257234689,0stxxx其中 M 是一个任意大的正数。据此可列出单纯形表jc 1200MMb基 1234567xxxxi678x41130023jjcz24612MM273xM1/401/4050284/5jjcz133422
