运筹学习题及答案.doc

1、运筹学习题答案第一章（39 页）1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max 12zx5 +10 50x2+ 142x， 01（2）min z= +1.51x2+3 31x+ 2， 01x（3）max z=2 +21x2- -11x2-0.5 + 2， 01x（4）max z= +1x2- 01x23 - -3， 01x2解：（1） （图略）有唯一可行解，max z=14（2） （图略）有唯一可行解，min z=9/4（3） （图略）无界解（4） （图略）无可行解1.2 将下列线性规划问题变换成标准型，并列出初始单纯形表。（1

2、）min z=-3 +4 -2 +51x234x4 - +2 - =-2x234+ +3 - 141-2 +3 - +2 2x234x， ， 0， 无约束1（2）max kzsp1nmkikizax1(,.)ikn0 (i=1n; k=1,m)ikx（1）解：设 z=- , = - , , 0z4x565x6标准型：Max =3 -4 +2 -5( - )+0 +0 -M -Mz12356789x10s. t .-4 + -2 + - + =21x235x610+ +3 - + + =147-2 +3 - +2 -2 - + =21x235x689x, , , , , , , , 023567

3、891初始单纯形表: jc3 -4 2 -5 5 0 0 -M -MBCXb 1x23x56x78x910xi-M 10x2 -4 1 -2 1 -1 0 0 0 1 20 714 1 1 3 -1 1 1 0 0 0 14-M 9x2 -2 3 -1 2 -2 0 -1 1 0 2/3- z4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 0(2)解：加入人工变量 ， ， ， ，得：1x23nxMax s=(1/ ) -M -M -.-Mkp1nimkik12ns.t. (i=1,2,3,n)1miikx0, 0, (i=1,2,3n; k=1,2.,m)ikiM 是任意

4、正整数初始单纯形表：jc-M-M -M1kap12k 1mkap 1nk2nkap mnkapBCXb 1x2 nx112x 1x 1nx2n nxi-M 11 1 0 0 1 1 0 0 0-M 2x1 0 1 0 0 0 0 0 -M n1 0 0 1 0 0 0 1 1 1-s nM0 0 0 kaMp12k 1mkaMp nk2nkaMp mnkap1.3 在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）max z=2 +3 +4 +71x234x2 +3 - -4 =8-2 +6 -7 =-31x34x, , , 02(2)ma

5、x z=5 -2 +3 -61x34x+2 +3 +4 =71x234x2 + + +2 =301x34（1）解：系数矩阵 A 是：267令 A=( ， ， ， )1P234与 线形无关，以（ ， ）为基， ， 为基变量。1P21x2有 2 +3 =8+ +41x23x4-2 =-3-6 +7令非基变量 ， =03x4解得： =1； =212基解 =（ 1，2，0，0 为可行解()X)T=81z同理，以（ ， ）为基，基解 =（45/13，0，-14/13 ，0 是非可行解；1P3(2)X)T以（ ， ）为基，基解 =（34/5，0，0，7/5 是可行解， =117/5；4(3) )T3z以（

6、 ， ）为基，基解 =（0，45/16，7/16，0 是可行解， =163/16；23(4) 4以（ ， ）为基，基解 =（0，68/29，0，-7/29 是非可行解；P4(5)X)T以（ ， ）为基，基解 =（0，0，-68/31，-45/31 是非可行解；3(6)最大值为 =117/5；最优解 =（34/5，0，0，7/5 。z(3) )T（2）解：系数矩阵 A 是：134令 A=( ， ， ， )1P234， 线性无关，以（ ， ）为基，有：1P2+2 =7-3 -41x23x42 + =3- -2令 ， =0 得3x4=-1/3， =11/3 12基解 =（ -1/3，11/3，0，0

7、 为非可行解；()X)T同理，以（ ， ）为基，基解 =（2/5，0，11/5 ，0 是可行解 =43/5；1P3(2)X)T2z以（ ， ）为基，基解 =（-1/3，0，0，11/6 是非可行解；4(3)以（ ， ）为基，基解 =（0，2，1，0 是可行解， =-1；23(4) )T4z以（ ， ）为基，基解 =（0，0，1，1 是 =-3；4P(6)X6最大值为 =43/5；最优解为 =（2/5，0，11/5，0 。2z(2) )T1.4 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。（1）max z=2 +1x23 +5 156 +2 241x2，

8、 0（2）max z=2 +51x241x2 123 +2 181x2， 0解：（图略）（1）max z=33/4 最优解是(15/4,3/4)单纯形法：标准型是 max z=2 + +0 +01x234xs.t. 3 +5 + =151x236 +2 + =244, , , 01x23单纯形表计算： jc2 1 0 0BCBXb 1x23x4i0 3x15 3 5 1 0 50 424 6 2 0 1 4-z 0 2 1 0 00 3x3 0 4 1 -1/2 3/42 14 1 1/3 0 1/6 12-z -8 0 1/3 0 -1/31 2x3/4 0 1 1/4 -1/82 115/

9、4 1 0 -1/12 5/24-z -33/4 0 0 -1/12 -7/24解为：（15/4，3/4，0，0 )TMax z=33/4迭代第一步表示原点；第二步代表 C 点（4，0，3，0 ；)T第三步代表 B 点（15/4，3/4，0，0 。)T（2）解：（图略）Max z=34 此时坐标点为（2，6）单纯形法，标准型是：Max z=2 +5 +0 +0 +01x234x5s.t. + =41x32 + =1243 +2 + =181x25, , , , 024(表略)最优解 X=（2，6，2， 0，0 )TMax z=34迭代第一步得 =（0，0，4，12，18 表示原点，迭代第二步得

10、(1)X)T=（ 0，6 ，4，0，6 ，第三步迭代得到最优解的点。(2) T1.5 以 1.4 题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目标函数：max z= +1cx2(1)当 0 时2c=-（ / ） +z/ 其中，k=- /x1c21x2c1c2=-3/5， =-3ABkBCk k 时， 1c， 2同号。当 0 时，目标函数在 C 点有最大值2c当 0 时，目标函数在原点最大值。 BCkk AB时， 1c， 2同号。当 0， 目标函数在 B 点有最大值；2c当 0，目标函数在原点最大值。 ABk k 0

11、 时， 1c， 2同号。当 0 时，目标函数在 A 点有最大值2c当 0 时，目标函数在原点最大值。 k 0 时， 1c ， 2异号。当 0， 0 时，目标函数在 A 点有最大值；2c当 0， 1 0 时，目标函数在 C 点最大值。 k= ABk时， c， 2同号当 0 时，目标函数在 AB 线断上任一点有最大值2c当 0，目标函数在原点最大值。 k= BCk时， 1c， 2同号。当 0 时，目标函数在 BC 线断上任一点有最大值2c当 0 时，目标函数在原点最大值。 k=0 时， 1c=0当 0 时，目标函数在 A 点有最大值2当 0，目标函数在 OC 线断上任一点有最大值c（2）当 =0

12、时，max z= 1c2x 0 时，目标函数在 C 点有最大值1c 0 时，目标函数在 OA 线断上任一点有最大值 1c=0 时，在可行域任何一点取最大值。1.6 分别用单纯形法中的大 M 法和两阶段法求解下列线性问题，并指出属于哪类解。（1）max z=2 +3 -51x23+ + 15x232 -5 + 241， 0x（2）min z=2 +3 +1x23+4 +2 81x233 +2 6， ， 01x23（3）max z=10 +15 +121x23x5 +3 + 91x23-5 +6 +15 15x2 + + 51x3， ， 0（4）max z=2 - +21x23+ + 61x23-

13、2 + 22 - 0x3， ， 01解：（1）解法一：大 M 法化为标准型：Max z=2 +3 -5 -M +0 -M1x234x56s.t. + + + =742 -5 + - + =101x35x6, , , , , 0 M 是任意大整数。4单纯形表： jc2 3 -5 -M 0 -MBCXb 1x23x45x6i-M 4x7 1 1 1 1 0 0 7-M 6x10 2 -5 1 0 -1 1 5-z 17M 3M+2 3-4M 2M-5 0 -M 0-M 42 0 7/2 1/2 1 1/2 -1/2 4/72 1x5 1 -5/2 1/2 0 -1/2 1/2 -z 2M-10 0

14、 (7/2)M+8 0.5M-6 0 0.5M+1 -1.5M-13 2x4/7 0 1 1/7 2/7 1/7 -1/72 145/7 1 0 6/7 5/7 -1/7 1/7-z -102/7 0 0 -50/7 -M-16/7 -1/7 -M+1/7最优解是： X=（45/7 ，4/7 ，0，0，0 )T目标函数最优值 max z=102/7有唯一最优解。解法二：第一阶段数学模型为 min w= + 4x6S.t. + + + =71x234x2 -5 + - + =1056, , , ， , 01x34x（单纯形表略）最优解X=（45/7 ，4/7 ，0，0，0 )T目标函数最优值 min w=0第二阶段单纯形表为： jc2 3 -5 0BCBXb 1x23x5i3 2x4/7 0 1 1/7 1/72 145/7 1 0 6/7 -1/7