运筹学第二章线性规划的对偶理论复习题

第二章 线性规划的对偶理论 第二章 线性规划的对偶理论 习 题 习 题 1、某厂生产 A、B、C 三种产品，每种产品要 经过、三道工序加工，设每件产品在每道 工序上加工所消耗的工时， 每道工序可供利用的工 时上限，以及每件产品的利润如表 2-1 所示. 表 2-1 消 工序 耗 产品 单件 利润 （元） A B C 3 4 2 2 1 2 1 3 3 200 300 250 可用工时6040 20 试列出使总利润最大的线性规划模型， 并写出 它的对偶问题，同时，就这个对偶问题作出经济上 的解释. 解：设 123 xxx， ，分别表示 A、B、C 各产品的数量，Z 表示总产值则： 12 123 123 123 max200300250 .4260 240 3320 (1,2,3)0 i zxx stxxx xxx xxx x i =+ + + + = 3 2 3 x ymin604020 .2 300 23250 wyy styyy yyy yyy yyy =+ + + + 原问题的对偶问题为 3200 3 2 0，0，0 经济解释：y1，y2，y3分别表示给别人代工时所得收入，对厂方而言，w越大越好，但定 价不能太高，要对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理， 厂方不会吃亏，对方也容易接受。 2、写出下列线性规划问题的对偶问题： (1) 321 210maxxxxz+= s.t. 102 321 +xxx 20 321 +xxx 1 )3 , 2 , 1(0=jxj min1020 .10 1 2 wy styy yy yy yy =+ + + + 解： 2 0，0 y (2) 321 422minxxxz+= s.t. 2532 321 +xxx 373 321 +xxx 564 321 +xxx )3 , 2 , 1(0=jxj max235 .32 42 764 0 wyyy styyy yyy yyy yyy =+ + + + 解： 2 3 5 0，0， (3) 321 365maxxxxz+= s.t. 522 321 =+xxx 35 321 +xxx 8374 321 +xxx 1 x无约束，0 2 x0 3 x min538 .45 576 33 0 wyyy styyy yyy yyy yyy =+ += + + 解： 2 2 自由，0， (4) 4321 4323minxxxxz+= s.t. 3432 4321 +xxxx 2 543 432 +xxx 24732 4321 =xxxx 无约束 3241 , 0, 0 xxxx 解： 解： max3 .23 53 37 444 0 wyyy styy yyy yyy yyy yyy =+ + + + + 52 -22 -3-3 4 0，0， 3、应用对偶理论证明线性规划问题. 21 maxxxz+= s.t. 2 321 +xxx 12 321 +xxx 0, 321 xxx 有可行解，但无最优解. 证明： 是线性问题的可行解，即该问题存在可行解； 0 0 0 x = 又其对偶问题为： min2 .21 1 0 ,0201 wyy styy yy yy yy y yyy =+ + - 0，0 -这与约束条件（）不符 该对偶问题无可行解 原问题无最优解。 4、应用弱对偶定理，证明线性规划问题 3 321 2maxxxxz+= s.t. 2 321 +xxx 1 321 =+xxx 22 321 +xxx 无约束 321 , 0, 0 xxx 的最大值不超过 1. 证明：该线性问题的对偶问题为： 00 min22 .21 2 1 0 010 0 1 (2,1,2)1 0 max T wyyy styyy yyy yyy yyy Y cxy b z =+ + + += = = - 0， 自由， 易知（ ， ， ）是对偶问题的一个可行解， 由对偶问题的对偶定理可得： 即最大值不超过11 5、应用对偶理论，证明线性规划问题 21 23maxxxz+= s.t. 42 21 +xx 1423 21 + xx 3 21 xx 0, 21 xx 有最优解，并证明其对偶问题也有最优解. 证明：对偶问题 4 min4143 .33 24 0 23 wyyy styyy yyy yyy =+ + + T T - 2 0，0， 由题易知X=（3，0）是原问题的一个可行解， Y=（0，1，0）是对偶问题的一个可行解 由对偶问题的推论可得它们都有最优解。即得证。 2 6、已知标准线性规划问题 cxz =max s.t. Ax = b x0 具有最优解， 假设将右端向量 b 改为另一向量 d， 如果改变后的问题是可行的， 试证该问题一定有最优解. 7、考虑下列原始线性规划 321 32maxxxxz+= s.t. 52 321 +xxx 12432 321 =+xxx )3 , 2 , 1(0=jxj (1) 写出其对偶问题； (2) 已知（3,2,0）是上述原始问题的最优解，根据互补松弛定理，求出对偶 问题的最优解； (3) 如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格. 解： （1）对偶问题： min512 .22 31 43 wyy styy yy yy yy =+ + + + 2 0， 无符号限制 （2）由题知原问题的最优解为 * (3 2 0)Tx =， ， ； 5 由互补松弛定理得：在对偶问题中对应第一，二个约束为紧，第三个约束条件 为松，即， * 12 * 1* 12 * 2* 12 22 4 31 1 243 yy y yy y yy += = += = + 对偶规划问题的最优解 * 1 41y = （ ， ） （3）影子价格为 y1 = 4 ： 8、已知线性规划问题 4321 432maxxxxxz+= s.t. 20323 4321 +xxxx 20232 4321 +xxxx )4 , 1(0L=jxj 其对偶问题的最优解为， 试根据对偶理论求出原问题的最优解. 2 . 0, 2 . 1 * 2 * 1 =yy 解：先写出其对偶问题。 min2020 .21 2 83 324 wy styy yy y yy yy =+ + + + 3 0，0 yy+ 2 2y1+3y2 对偶规划问题的最优解 * 1 * 12 * 12 1.20.2 0 0 yy xx yy = = Q ，代入约束条件，知第1，2约束条件成立严格不等式， 由互补松弛定理，原规划最优解中相应变量 又， 不为 ，则在原问题规划中对应的约束条件为紧，得 * 334 * 34 4 42320 32204 xxx xxx = += += 原对偶规划问题的最优解 * 0,0,4,4x = （） 6 9、已知某线性规划问题的最优单纯形表如表 2-2 所示，表中为松弛变量，问题 的约束为形式 54,x x (1) 写出原线性规划问题； (2) 写出原问题的对偶问题； (3) 直接由表 2-2 写出对偶问题的最优解. 解： 1112 2122 1/210 011/6 1/2 1/2 xx NB xx = -1 -1 0 （1）由表知B； = 1/3 B令则 表 2-2 3 x 5 x B x 1 x 2 x 4 x 1112 2122 1/201020 1/61/30113 1/21/201 1/21/61/31 xx BB xx a NN b = = -1 -1 B B = b = 1 31 3 22 0125/25 3115/210 61/20 42 101/61/3 442 Ab C CC C CC = = = = + = = -1 ；B （， ）（， ） 1 （，-2）-1 123 23 123 max . 10 (1,2,3)0 i zxxx stxx xxx x i =+ + + = 原线性问题为： 6210 2 5 3 2 min510 .36 2 10 wyy sty yy yy yy =+ + （ ） 2 0，0 b 3 x0 1/21 1/2 0 5/2 1 x1 -1/20 -1/6 1/3 5/2 0 -4 0 -4 -2 7 * 4535 * 3(5/2 0 5/2)40; 00 34 22 4 T xZ xxyy yy yyyy yyy Y = = = = += = 2 4 T* （ ）， ，； 6 即 2 =10 （4，2） w =40； 10、某厂拟生产甲、乙、丙三种产品， 都需要在 A、B 两种设备上加工，有关数 据如表 2-3 所示. (1) 如何充分发挥设备能力，使产 品总产值最大？ (2) 若为了提高产量， 以每台时 350 元租金租用外厂 A 设备，问是否合算？ 解： （1）设 123 xxx， ，分别表示甲、乙、丙各产品的数量，Z 表示总产值则： 123 123 123 max32 .2 2500 (1,2,3)0 i zxxx stxxx xxx x i =+ + + = 2 400 化为标准形： 123 1234 1235 max32 .2400 2500 (1,2,3 4 5)0 i zxxx stxxxx xxxx x i =+ += += = + 2+ ， ， C 3 2 1 0 0 CBXBX1X2X3X4X5 b 0 X41 2 1 1 0 400 0 X521 2 0 1 500 检验数 3 2 1 0 0 0 X40 3/20 1 -1/2150 表 2-3 单耗（台时/件） 产品 设备 甲 乙 丙 设备有效 台时（每月） A 1 2 1 400 B 2 1 2 500 产值(千元/件)3 2 1 8 3 X11 1/2 1 0 1/2 250 检验数 0 1/2 -20 -3/2250 2 X20 1 0 2/3 -1/3100 3 X11 0 1 -1/3 2/3 200 检验数 0 0 -2-1/3 -4/3-800 * (200,100)800; T xZ=； 2 min400500 .23 2 21 wyy styy yy yy yy =+ + + + （ ）原问题的对偶问题为 2 0，0 此时，y1，y2分别表示出租A，B设备所得利润， 由（1）中的最优表得=1/3，即如出租 A 设备可获得 1000/3 元，而 1000/3350 * 1 y 所以不合算。 11、已知某实际问题的线性规划模型为 = = n j jjx cz 1 max s.t. = = n j ijij mibxa 1 ), 2 , 1(L ), 2 , 1(0njxjL= 若第i项资源的影子价格为 ), 2 , 1(miyiL= (1) 若第一个约束条件两端乘以 2，变为 ， = n j ijij bxa 1 2)2( 1 y 是对应于这个新约束条件的影子价格，求与的关系； 1 y 1 y 9 (2) 令，用替换模型中所有的，问影子价格是否变化？若不 可能在最优基中出现，问是否可能在最优基中出现； 11 3xx =3/1x 1 x i y 1 x 1 x (3) 如果目标函数变为 = = n j jjx cz 1 2max 问影子价格有何改变？ (4) 如果模型中约束条件变为 = = n j ijij mibxa 1 , 2 , 1L 问(1)、(2)、(3)中的结论是变化? 解： （1）由影子价格的定义可得： 111 11 11 2 1 2 ZZ yyb bb yy = = ，而 ； 1 b （2）由（1）可知y1只与bi的值有关当x1的系数由 3 变为x 的系数 1/3 时，y i的值并 不发生变化； x1不可能在最优基中出现， x 也不可能在最优基中出现 （3） 11 11 2 nn Jjii jj nn JjJjj jj zC Xb yw zC XzC XC = = = = i 当目标函数由变为时，增大了两倍 影子价格y 也增大了两倍。 （4）分别相同。 12、用对偶单纯形法求解下列线性规划问题： (1) 321 4510minxxxz+= s.t. 3323 321 +xxx 10 1024 31 + xx 0, 321 xxx 解：先将问题化为标准式 1234 1234 13 max105400 .233 21 (1,2,3,4,5)0 i zxxxxx stxxxx xxx x i = + += += = 5 5 -3 -4 0 取初始正则基 B = （p4 p5） = I 则原问题已化为关于基 B 的典式， C 2 3 1 0 0 CBXBX1X2X3X4X5 B 0 X4-3 -2 3 1 0 -3 0 X5-4 0-2 0 1 -10 检验数 -10 -5 -4 0 0 0 0 X4-9 -2 0 1 3/2 -18 -4 X32 0 1 0 -1/25 检验数 -2 -5 0 0 -2 20 -10 X11 2/9 0 -1/9 -1/62 -4 X30 -4/9 1 2/9 -1/61 检验数 0 -41/9 0 -2/9 -7/324 可得原问题的最优解为： * 2,0,1,0,0 ,24,24,(2/9,7/3),24.xZZyw= = T （） * = (2) 321 432minxxxz+= s.t. 32 321 +xxx 432 321 +xxx 0, 321 xxx 将问题化为： 11 123 1234 123 max234 .2 34 (1,2,3,4,5)0 i zxxx stxxxx xxxx x i = += += = 5 -2 3 C 3 2 1 0 0 CBXBX1X2X3X4X5 B 0 X4-1 -2 -1 1 0 -3 0 X5-21 -3 0 1 -4 检验数 -2 -3 -4 0 0 0 X40 -5/21/2 1 -1/2 -1 3 X11 -1/2 3/2 0 -1/2 2 检验数 0 -4 -1 0 -1 250 2 X20 1 -1/5 -2/5 1/5 2/5 3 X11 0 14/10 -1/5 -4/1011/5 检验数 0 0 -9/5 -8/5 -1/5 -28/5 * (11/5,2/5,0)28/5;28/5 T xZ= ； * Z = (3) 21 2minxxz+= s.t. 33 21 + xx 634 21 + xx 32 21 + xx 0, 21 xx 解： 12 124 13 12 (3)max2 .3 36 23 (1,2,3,4,5,6)0 i zxx stxxx xxx xxx x i = += += + = 5 6 - -4 3 = 12 C 3 5 0 0 0 0 CBXBX1X2X3X4X5X6 B 0 X4-3 -1 0 1 0 0-3 0 X5-4 0 -30 1 0-6 0 X61 2 0 0 0 13 检验数 -2 -1 0 0 0 0 0 X4-3-1 0 1 0 0-3 0 X34/3 0 1 0 -1/302 0 X61 2 0 0 0 13 检验数 -2 -1 0 0 0 0 -2 X11 1/3 0 -1/3 0 01 0 X30 -4/9 1 4/9 -1/302/3 0 X60 5/3 0 1/3 0 12 检验数 0 -1/3 0 -2/3 0 02 (4) 321 23minxxxz+= s.t. 6 321 +xxx 13 4xx+ = 3 32 xx )3 , 2 , 1(0=jxj 解：化为： 123 1234 13 23 max32 .6 4 3 (1,2,3,4,5,6)0 i zxxx stxxxx xxx xxx x i = += += + = 5 6 - + 13 C -3 -2 -10 0 0 CBXBX1X2X3X4X5X6 b 0 X41 1 1 1 0 0 6 0 X5-1 0 -10 1 0 -4 0 X60 -1 1 0 0 1 -3 检验数 -3 -2 -10 0 0 0 X40 1 0 1 1 0 2 -1 X31 0 1 0 -1 0 4 0 X6-1-1 0 0 1 1 -7 检验数 -2 -2 0 0 -1 0 0 X40 1 0 1 1 0 2 -1 X30 -11 0 0 1 -3 -3 X11 1 0 0 -1 -1 7 检验数 0 0 0 0 -3 -2 0 X40 0 1 1 1 1 -1 -2 X20 1 -10 0 -1 3 -3 X1 0 1 0 -1 0 4 1 检验数 0 0 0 0 -3 -2 由表知，此题无可行解。 表 2-3 j c 3 8 0 0 0 13、已知线性规划问题 b 3 x 5 x B c B x 1 x 2 x 4 x 1 x 21 83maxxxz+= 3 1 0 1/20 -2 100 4 x0 0 0 -3 1 10 500 2 x s.t. 8 0 1 0 0 1 350 检验数 0 0 -3/20 -2 -3100 160042 21 + xx 180026 21 + xx 350 2 x 0, 21 xx 用单纯形法求解时得最终单纯形表如表 2-3 所示. 14 （1）要保持现有最优解不变，分别求,的变化范围； 1 c 2 c （2）要保持现有最优解不变，分别求,，的变化范围； 1 b 2 b 3 b （3）当变为 500 时，求新的最优解. 3 b 解： （1）由表知，C1C2为基变量的系数 1 1 1 2 2 2 3/2 max3 1/2 2 min1 2 0,4 2 max2 1 3/2 min 0 6,) C C C C C C + + =+= =+= =+= =+= + （2）参见教材 P67 的方法求之 3 (3)500300,400b = 最优解将发生变化； ()0,0,150 T b = 1/2020300 311001500 001150150 b = -1 b =B C 3 8 0 0 0 b CXXXXXX BB12345 3 X1 0 1/2 0 -2-200 1 0 X0 0 -3 1 10 2000 4 8 X0 1 0 0 1 500 2 检验数 0 0 -3/2 0 -2 0 X-1/2 0 -1/4 0 1 100 5 0 X5 0 -1/2 1 0 1000 4 15 8 X1/2 1 4 0 0 400 2 检验数 -1 0 -2 0 0 -3200 * (0,400)3200; T xZ=； 14、已知线性规划问题 21 510maxxxz+= s.t. 943 21 + xx 825 21 + xx 0, 21 xx 用单纯形法求得最终单纯形表如表 2-4 所示，试用灵敏度分析的方法分别判断： (1) 目标函数系数或分别在什么范围内变动，现最优解不变； 1 c 2 c (2) 约束条件右端常数中，当保持一个不变时，另一个在什么范围内变化， 现有的最优基不变； 21,b b (3) 问题的目标函数变为 21 412maxxxz+= 时，最优解有什么变化； (4) 约束条件右端常数项由时，最优解有什么变化？ 19 11 8 9 变为 表 2-4 j c b 38 0 0 3 x B c B x 1 x 2 x 4 x 2 x 0 1 5/14-3/143/2 5 1 x 10 -1/72/7 1 10 检验数 00 -5/14-25/14-25/2 解：1）. C1变化时， 16 1 1 1 51 50 1525 147 3242 50 147 C C C + + C2变化时， 2 1 2 105 0 40 714 4 2033 0 714 C C C + 2）若b1不变，则b =8+b 2 11 33 3/25/143/140 214 0 211/72/7 1 7 B XB bBb b b b =+ =+ = + ? ? ? ? 3.574.515bb得： 12 9,bbb=+? 不变 11 35 3/25/143/14 214 0 111/72/70 1 7 B XB bBb b b b =+ + =+ = ? ? ? ? 4.274.816bb得： 3）初始表 C -3 -2 -1 0 b CXXXXX BB1234 0 X3 4 1 0 9 3 0 X5 2 0 1 8 4 检验数 12 4 0 0 0 0 X0 14/5 1 1 21/5 3 12 X1 2/5 0 0 8/5 1 检验数 0 -4/5 0 0 -96/5 17 * ,0,21/5,0 x= T （8/5） 4） b1 11 ，b2 9 C -3 -2 -1 0 b CXXXXX BB1234 0 X3 4 1 0 11 3 0 X5 2 0 1 9 4 检验数 10 5 0 0 0 0 X0 1 5/14 -3/14 2 3 12 X1 0 -1/7 1 1 1 检验数 0 0 -5/14 -25/14 -20 * ,2,0,0 x= T （1） 15、已知线性规划问题 表 2-5 321 2maxxxxz+= j c 3 8 0 0 0 b 3 x 5 x B c B x 1 x 2 x 4 x s.t. 1 x2 1 1 1 1 0 6 5 x0 0 3 1 1 1 10 6 321 +xxx 检验数 0 -3 -1 -2 0 -12 4 21 +xx )3 , 2 , 1(0=jxj用单纯形法求得最终单纯形表如表 2-5 所示， 试分别 求当下列情况发生时的最优解： 321 32maxxxxz+=； (1) 目标函数变为 (2) 约束条件右端项由； 4 3 4 6 变为 (3) 增加一个新的约束条件 22 21 +xx 18 解：由表知C2的影响范围为C2（-，2 12 max23 3 zxxx=+时，最优解将发生变化 当目标函数变为 C 2 3 1 0 0 B CXXXXXX BB12345 2 X1 1 1 1 6 6 1 0 X0 31 1 1 10 5 检验数 0 1 -1 -2 0 2 X1 0 2/3 2/3 -1/38/3 1 3 X0 1 1/3 1/3 1/3 10/3 2 检验数 0 0 -4/3-7/3 -1/3-46/3 * (8/3,10/3,0)46/3; T xZ=； 0 1 31 (2) 01 1033 1103 b bb = = = -1 -1 B B C 2 3 1 0 0 b CXXXXXX BB12345 2 X1 1 1 1 0 3 1 0 X0 31 1 1 7 5 检验数 0 -3 -1-2 0 -6 * (30 0,0 7)6; T xZ=， ， ， ； * 12 126 (6 0 0,010)32 02 22 T xx xxx = + += （3）把， ， ，代入约束条件 -6不成立， 该问题的最优解将发生变化， x+ C 2 -1 1 0 0 0 B CXXXXXXX BB123456 2 X1 1 1 1 0 0 6 1 0 X0 3 1 1 1 0 10 5 0 X1 -2 0 0 0 1 -2 6 19 检验数 0 -3 -1 -2 0 0 2 X1 1 1 1 0 0 6 1 0 X0 3 1 1 1 0 10 5 0 X0 -3 -1 -1 0 1 -8 6 检验数 0 -3 -1 -2 0 0 2 X1 0 2/32/3 0 1/3 10/3 1 0 X0 0 0 0 1 1 2 5 -1 X0 1 1/31/3 0 -1/38/3 2 检验数 0 0 0 0 0 -1 -12/3 * (10/38/30,0 2)4; T xZ=， ， ， ； 16、已知线性规划问题 321 1355maxxxxz+= 203 321 +xxx A s.t. 9010412 321 +xxx B )3 , 2 , 1(0=jxj 先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化： (1) 约束条件 B 的右端项由 90 变为 70； (2) 目标函数中的系数由 13 变为 8； 3 x (3) 变量的系数（包括目标函数）由变为； 12 1 5 5 0 2 1 x (4) 变量的系数（包括目标函数）由变为； 4 1 5 6 5 2 2 x 20 50532 321 +xxx(5) 增加一个约束条件 ； 10010510 321 +xxx. (6) 原约束条件（2）变为 123 1234 123 max5513 .32 4109 (1,2,3,4,5)0 i zxxx stxxxx xxxx x i = + += += = 5 解： 化为： 12 0 0 C -3 -2 -10 0B CXXXXXX BB12345 0 X-1 1 3 1 020 4 0 X12 4 100 190 5 检验数-5 5 130 0 13 X-1/3 1/3 1 1/3 020/3 3 0 X46/3 2/3 0 -10/3170/3 5 检验数-2/3 2/3 0 -1 0 5 X-1 1 3 1 020 2 0 X16 0 -2-4 110 5 检验数0 0 -2-5 0-100 * (0 20 0,010)100; T xZ=， ， ，； 01 (1) 2041 1000 412020 b bb = = = -1 -1 B B 0 C -5 5 130 0 b CXXXXXX BB12345 5 X-1 1 3 1 0 20 2 0 X16 0 -2-4 1 -10 5 检验数 0 0 -2-5 0 5 X23 1 0 -5 3/2 5 2 13 X-8 0 1 2 -1/2 5 3 21 检验数 -16 0 0 -1 -1 -90 （2） C -5 5 8 0 0 b CXXXXXX BB12345 5 X-1 1 3 1 0 20 2 0 X16 0 -2-4 1 -10 5 检验数 0 0 -70 0 -100 * (0 20 0,010)100; T xZ=， ， ，； 00 55 2 3 010