1、最全运筹学习题及答案共 1 页运筹学习题答案）1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max z?x1?x25x1+10x2?50x1+x2?1x2?4x1，x2?0（2）min z=x1+1.5x2x1+3x2?3x1+x2?2x1，x2?0（3）+2x2x1-x2?-0.5x1+x2x1，x2?0（4）max z=x1x2x1-x2?03x1-x2?-3x1，x2?0解：（1） （图略）有唯一可行解，max z=14（2） （图略）有唯一可行解，min z=9/4（3） （图略）无界解（4） （图略）无可行解1.2 将下列线
2、性规划问题变换成标准型，并列出初始单纯形表。共 2 页（1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2x1+x2+3x3-x4?14 -2x1+3x2-x3+2x4?2x1，x2 ，x3?0 ，x4 无约束 （2zk?i?xk?1mxik?（1Max s. t .-4x1xx1,x2共 3 页(2)解：加入人工变量 x1，x2，x3 ，xn ，得： Max s=(1/pk)?i?1n?k?1m?ikxik-Mx1-Mx2-.-Mxns.t.m（1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3
3、x1,x2,x3,x4?0(2)max z=5x1-2x2+3x3-6x4共 4 页x1+2x2+3x3+4x4=72x1+x2+x3+2x4=3x1x2x3x4?0（1）解：系数矩阵 A 是：?23?1?4?1?26?7? ?令 A=(P1，P2，P3，P4)P1 与 P2 线形无关，以（P1 ，P2 有 2x1+3x2=8+x3+4x4x1-2x2=-3-6x3+7x4令非基变量 x3，x4 解得：x1=1 ；x2=2基解 0， 0)T 为可行解z1=8(2)同理，以（P=（45/13，0，-14/13 ，0)T 是非可行解； 3 以（P1，P4X(3)=， ，7/5)T 是可行解，z3=
4、117/5；(4)以（P2，P=（，45/16，7/16 ，0)T 是可行解，z4=163/16； 3 以（P2，P4）为基，基解 X(5)0，68/29 ，0，-7/29)T 是非可行解；(6)TX 以（P4，P ）为基，基解 =（0，0，-68/31，-45/31 是非可行解；)3最大值为 z3=117/5；最优解 X(3)=（34/5， 0，0，7/5)T。（2）解：系数矩阵 A 是：?1234?2112? ?共 5 页令 A=(P1，P2，P3，P4)P1，P2 线性无关，以（P1 ，P2）为基，有：x1+2x2=7-3x3-4x42x1+x2=3-x3-2x4令 x3，x4=0 得x
5、1=-1/3，x2=11/3基解 X(1)=（-1/3，11/3 ，0，0)T(2)同理，以（P1，P=0，)Tz2=43/5； 3）为基，基解 X以（P1，P4）为基，基解 X(3)=0)T(4)以（P2，P=（2，0)Tz4=-1； 3）为基，基解 X(6)以（P4，P=（0，0 ，1)Tz6=-3 ； 3X最大值为 z2；最优解为=（0)T。1.4（1）+x23x1+5x2156x1+2x2?24x1，x2?0（2）max z=2x1+5x2x1?42x2?123x1+2x2?18x1，x2?0共 6 页解：（图略）（1）max z=33/4 最优解是(15/4,3/4) 单纯形法：标准
6、型是 max z=2x1+x2+0x3+0x4 s.t. 3x1+5x2+x3=15 6x1+2x2+x4=24x,x,x,x?0 Max 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=2x1+5x2+0x3+0x4+0x5共 7 页s.t. x1+x3=42x2+x4=123x1+2x2+x5=18x1,x2,x3,x4,x5?0(表略)最优解 X=（2，6，2，0，0 )TMax z=34迭代第一步得 X(1)=
7、（0 ，0，4，12，TX(2)= （0，6，4 ，0，6)T1.5 以1.4 题（1解：目标函数：max z=c1x1+c2x2(1)当 c2?0 时x2c1/c2）x1+z/2 k=-1/c2kAB，?k当 c2当 c2?当 c2当 c2?当 c2当 c2BC 时， 1，c2 0C 0kBCkkABc 时，1 0， 目标函数在 B 点有最大值； 0，目标函数在原点最大值。 kABk cc0 时，1 ， 2 同号。 0 时，目标函数在 A 点有最大值 0 时，目标函数在原点最大值。共 8 页?k当 c2当 c2cc0 时，1 ，2 异号。 c0，1 c0，1kAB0 时，目标函数在 A 点有
8、最大值； 0 时，目标函数在 C 点最大值。? k=当 c2当 c2cc 时，1， 2 同号 0 时，目标函数在 AB 线断上任一点有最大值 0，目标函数在原点最大值。? k=当 c2当 c2kBC 时， c1， c2 同号。 0 时，目标函数在 BC0c? k=0 时，1 当 c2当 c20A（2c2max z=? c1? c1x C c1c1=01.6 分别用单纯形法中的大 M 并指出属于哪类解。（1）max z=2x1+3x2-5x3x1+x2+x3?152x1-5x2+x3?24x1，x2?0（2）min z=2x1+3x2+x3共 9 页x1+4x2+2x3?83x1+2x2?6x1
9、，x2 ，x3?0（3）max z=10x1+15x2+12x3 5x1+3x2+x3?9-5x1+6x2+15x3?15 2x1+x2+x3?5x1，x2 ，x3?0（4）max z=2x1-x2+2x3 x1+x2+x3?6-2x1+x3?22x2-x3?0x1，x2?0解：（1 法Max z=2x1+324+0x5 s.t. x1+x2+x3+4=7 2x1-5x2+x3-x5+x6=10 x1,x2,x3,x5,x4,x6?0 M 是任意大整数。共 10 页目标函数最优值 min w=0共 11 页X=（45/7，4/7，0，0 ，0 )TMax z=102/7（2）解法一：大 M 法
10、z?=-z 有 max z?=-min （-z? ）=-min z 化成标准形：Max z?=-2x1-3x2-x3+0x4+0x5-Mx6-Mx7 S.T.x1+4x2+2x3-x4+x6=43x1+2x2-x5+x7=6x1,x2,x3,x4，x5,x6， x7?0（单纯性表计算略）线性规划最优解 X=（4/5，00 ，0 min z=7非基变量 x3X=（4/5，9/5 ，0，0，0 ，0 )T 是基本可行解 ,min w=04/5， ，0， ，)T min z=7 3?3（3）解：大 M 法Max z=10 x1+15 x2+12 3x4+0 x5+0 x6-M x7 s.t. 5 x
11、1+3 x2+ x3+ x4=9-5 x1+6 x2+15 x3+ x5=152 x1+ x2+ x3- x6+ x7=5x1,x2,x3,x4，x5,x6， x7?0单纯形表计算略共 12 页当所有非基变量为负数，人工变量 x7=0.5，所以原问题无可行解。两阶段法（略）（4）解法一：大 M 法单纯形法， （表略）非基变量 x4 的检验数大于零，此线性规划问题有无界解。两阶段法略1.7 求下述线性规划问题目标函数 z 的上界和下界；Max z=c1x1+c2x2a11x1?a12x2?b1a21x1?a22x2?b2其中：1?c1?3，4?c2?6，8?b1?b2?14?1?11?3，2?a12?5，2?a21?4 ，4?a22?6解：? 求 Z 的上界 Max z=3x1+6s.t. -1x2?12x12x1? X=（0 ，0 )T目标函数上界为 ? 求 z 的下界线性规划模型：Max Z= x1+4x2
