运筹学习题及答案.doc

最全运筹学习题及答案 共 1 页 运筹学习题答案 ） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max z?x1?x2 5x1+10x2?50 x1+x2?1 x2?4 x1，x2?0 （2）min z=x1+1.5x2 x1+3x2?3 x1+x2?2 x1，x2?0 （3）+2x2 x1-x2?-0.5x1+x2x1，x2?0 （4）max z=x1x2 x1-x2?0 3x1-x2?-3 x1，x2?0 解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。 共 2 页 （1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2 x1+x2+3x3-x4?14 -2x1+3x2-x3+2x4?2 x1，x2，x3?0，x4无约束 （2 zk?i?x k?1 m xik?（1Max s. t . -4x1xx1,x2 共 3 页 (2)解：加入人工变量x1，x2，x3，xn，得： Max s=(1/pk)? i?1n ? k?1 m ?ikxik-Mx1-Mx2-.-Mxn s.t. m （1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3 x1,x2,x3,x4?0 (2)max z=5x1-2x2+3x3-6x4 共 4 页 x1+2x2+3x3+4x4=7 2x1+x2+x3+2x4=3 x1x2x3x4?0 （1）解： 系数矩阵A是： ?23?1?4?1?26?7? ? 令A=(P1，P2，P3，P4) P1与P2线形无关，以（P1，P2有 2x1+3x2=8+x3+4x4 x1-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=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-4x4 2x1+x2=3-x3-2x4 令 x3，x4=0得 x1=-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）+x2 3x1+5x215 6x1+2x2?24 x1，x2?0 （2）max z=2x1+5x2 x1?4 2x2?12 3x1+2x2?18 x1，x2?0 共 6 页 解：（图略） （1）max z=33/4 最优解是(15/4,3/4) 单纯形法： 标准型是max z=2x1+x2+0x3+0x4 s.t. 3x1+5x2+x3=15 6x1+2x2+x4=24 x,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=4 2x2+x4=12 3x1+2x2+x5=18 x1,x2,x3,x4,x5?0 (表略) 最优解 X=（2，6，2，0，0 )T Max z=34 迭代第一步得X(1)=（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/c2 kAB，? k 当c2 当c2 ? 当c2 当c2 ? 当c2 当c2 BC 时， 1，c2 0C 0k BCkkABc时，1 0， 目标函数在B点有最大值； 0，目标函数在原点最大值。 kAB k cc0时，1， 2同号。 0时，目标函数在A点有最大值 0时，目标函数在原点最大值。 共 8 页 ? k 当c2 当c2 cc0时，1 ，2异号。 c 0，1 c 0，1 kAB0时，目标函数在A点有最大值； 0时，目标函数在C点最大值。 ? k= 当c2 当c2 cc时，1， 2同号 0时，目标函数在AB线断上任一点有最大值 0，目标函数在原点最大值。 ? k= 当c2 当c2 kBC时，c1， c2同号。 0时，目标函数在BC0c? k=0时，1当c2 当c2 0A （2c2max z= ? c1 ? ? c1x C c1 c1=0 1.6分别用单纯形法中的大M并指出属于哪类解。 （1）max z=2x1+3x2-5x3 x1+x2+x3?15 2x1-5x2+x3?24 x1，x2?0 （2）min z=2x1+3x2+x3 共 9 页 x1+4x2+2x3?8 3x1+2x2?6 x1，x2，x3?0 （3）max z=10x1+15x2+12x3 5x1+3x2+x3?9 -5x1+6x2+15x3?15 2x1+x2+x3?5 x1，x2，x3?0 （4）max z=2x1-x2+2x3 x1+x2+x3?6 -2x1+x3?2 2x2-x3?0 x1，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 )T Max z=102/7 （2）解法一：大M法 z?=-z 有max z?=-min （-z?）=-min z 化成标准形： Max z?=-2x1-3x2-x3+0x4+0x5-Mx6-Mx7 S.T. x1+4x2+2x3-x4+x6=4 3x1+2x2-x5+x7=6 x1,x2,x3,x4，x5,x6，x7?0 （单纯性表计算略） 线性规划最优解X=（4/5，00 ，0 min z=7 非基变量x3 X=（4/5，9/5，0，0，0，0 )T是基本可行解,min w=0 4/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 x1+3 x2+ x3+ x4=9 -5 x1+6 x2+15 x3+ x5=15 2 x1+ x2+ x3- x6+ x7=5 x1,x2,x3,x4，x5,x6，x7?0 单纯形表计算略 共 12 页 当所有非基变量为负数，人工变量x7=0.5，所以原问题无可行解。 两阶段法（略） （4）解法一：大M法 单纯形法，（表略）非基变量x4的检验数大于零，此线性规划问题有无界解。 两阶段法略 1.7求下述线性规划问题目标函数z的上界和下界； Max z=c1x1+c2x2 a11x1?a12x2?b1 a21x1?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?12 x12x1? X=（0，0 )T 目标函数上界为 ? 求z的下界 线性规划模型： Max Z= x1+4x2 s.t. 3x1+5x2?8 4x1+6x2?10 x2，x1?0 加入松弛变量，化成标准型，解得： 共 13 页 最优解为 X=（0，8/5，0，1/5 )T 目标函数下界是z=32/5 1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a1，a2，a3，d，c1，c2为待定常数，试说明这些常数分别取何值时，以下结论成立。 （1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为 x， 交线路至少配备多少司机和乘务人员。列出线型规划模型。 共 14 页 解 ： 设xk（k=1，2，3，4，5，6）为xk个司机和乘务人员第k班次开始上班。 建立模型： Min z=x1+x2+x3+x4+x5+x6 s.t. x1+x6?60 x+x?70 解: 解：设x1，x2，x3是甲糖果中的A，B，C成分，x4，x5，x6是乙糖果的A，B，C成分，x7，x8，x9是丙糖果的A，B，C成分。 线性规划模型： Max z=0.9x1+1.4x2+1.9x3+0.45x4+0.95x5+1.45x6-0.05 s.t. -0.4x1+0.6x2+0.6x3?0 x7+0.45x8+0.95x9 共 15 页 -0.2x1-0.2x2+0.8x3?0 -0.85x4+0.15x5+0.15x6?0 -0.6x4-0.6x5+0.4x6?0 -0.7 x7 -0.5 x8 +0.5 x9 ?0 x1+x4+x7 ?2000 解： 产品1，设A1,A2完成A工序的产品x1，x2件；B工序时，B1,B2，B3完成 共 16 页 B工序的x3，x4，x5件，产品?，设A1,A2完成A工序的产品x6，x7件；B工 序时， 工序的B1x9完成B的产品为件； x8件；产品111，A2完成A工序的x9件，B2完成B x1+ x2= x3+ x4+ x5 x6+ x7= x8 建立数学模型： Max z=(1.25-0.25)*( x1+ x2)+(2-0.35)*( 7)+(2.8-0.5) x9-(5 x1+10 x6)300/6000-(7 x2+9 x7+12 x938x4+11 x9)783/7000-7 x5*200/4000 s.t 5 x1+10 x6 ?6000 7 x2+9 6 x7x8+12 x9 ?4000 4 7 x5 x1+ x23x4x5 x6+ x7= x8 x1,x2,x3,x4,x5,x6,x7x8, 0 最优解为X=（1200，230，0，859，571，0，500，500，324 )T 最优值1147. 试题： 1. （2005年华南理工大学）设某种动物每天至少需要700克蛋白质、30克矿物质、100毫 克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价如下表所示： 试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。 共 17 页 解题过程：minz?0.2x1?0.7x2?0.4x3?0.3x4?0.8x5 ?3x1?2x2?x3?6x4?18x5?700?x?0.5x?0.2x?2x?234s.t?10.5x?x?0.2x?2x?1234?x1,x2,x3,x4,x5? ） 2.1 （1）Max z=6x1x2+3x3 2x1-x2+3x3?2 3?x1，2x3?0 （2）x1+x 3x1+x24x1+3x2?6 x1+2x2?3 x1,x2?0 解： （1） 先化成标准型： Max z=6x1-2x2+3x3+0x4+0x5 s.t. 2x1-x2+2x3+x4=2 共 18 页 x1+4x3+x5=4 x1,x2,x3,x4,x5 ?0 ?10?T令B0=（P4，P）=5? XB0=（x4,x5),CB0=(0,0) ?01? ?2?12?T)= , =（， N0=(P1,P2,Pxxx)X3123N0?104? ?10?2?,=bCN0=(6,-2,3)，B0?1=?0? 01?4? 非基变量的检验数 CN0CB0B0?1N0CN0-=?N=0 因为x1的检验数等于6x1B?1 0?2?2?1b0=?；BP1=? ?4?1? 由?规则得： ?=1 ?0?B1=(P5)=?,X1=（1B1?11? T), =（ N1=(P4,xxx23N1 ?0?1?,=bCN1=(0，-2，3)，?1=?1? ?0.51?3? 非基变量的检验数 ?N1=，1，-3） 因为x2的检验数为1，是正的最大数。所以x2为换入变量； ?0.5?B?1 0P2=? 0.5? 由?规则得： ?=6 所以x5是换出变量。 共 19 页 ?2?1?T ,=（,，CB2=(6,-2). B2=(P1，P2)=?xx)X12?B2 ?10? T N2=(P4,P5，P3), XN2=（x4，x5，x3) ?01?4?CN2=(0，0，3)，B2=?,b2=? ?12?6? ?1 非基变量的检验数 ?N2=（-2，-2，-9） ?4? 最优解X= ? ?6?即：X=（4,6,0)T 目标函数最优值 max （2） 解 ： Min z=2x1+x2x3+Mx4+Mx5+0x6 S.T. 3x1+=3 41x2-3x1+2x=3 x1,x2,x34, 6?0 M 原问题最优解是X=0.6，0） 目标函数最优值： 2.2 共 20 页 （1）min z= 2 x1+2 x2+4 x3 共 21 页 2 x1+3 x2+5 x3 ?2 3 x1+ x2+7 x3 ?3 x1+4 x2+6 x3 ?5 x1 ,x2, x3 ?0 （1） 解：对偶问题是： Max w=2y1-3y2-5y3 s.t. 2y1-3y2-y3?2 3y1-y2-4y3?2 5y1-7y2-6y3?4 y1,y2,y3?0 (2)max z= x1+2x2+3 x34-x1+x2346x1+7x2-5x48 12x1-9x2-93x4?20 x1,x2?0;x3 ?x4 解： 对偶问题： Min w=5y1+8y3+20S.t. -y1+6y3+12 y1+7y3-9y4 y4?1 y4?2 y4 -y1+3y3-9?3 =4 -3y1-5y3+9y4 共 22 页 y1无约束，y3?0； mny4?0 （3）min z=?cijxij i?1j?1 ?x j?1 mnij?ai i=1,m ?x i?1ij?bj j=1,n xij?0 解： 对偶问题: max w=?aiy+?j i i?1mns.t. yi+ym?j?cij yy i,m?j .m; j=1,2, ?cjj?1n ?axij j?1 nnj?m1?axij j?1j?i, i=11,m1?m xj?0,当j=1，.，n1?nxj无约束，当j=n1?1,.,n m解： Min w=?bjyi i?1 s.t. ?a i?1mijyi?cj j=1,2,3n1 共 23 页 ?a i?1mn1n1? j=+1, +2,.n ycijij yi?0 i=1,2. m1 yi无约束， i=m1+1, m1+2.m 2.4判断下列说法是否正确，并说明为什么. (1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。 （2 （3）则该线性规划问题一定有有限最优解。 (1) （2）错误， （3有无界解； 2.5设线性规划问题1是： Max z1=?cjxj j?1n ?axij j?1nj?bi ，i=1，xjj?n *（y1 2是 Max z2cjjj?1n ?axij j?1nj?bi +ki ，i=1，m xj?0,j?1,2.,n 其中ki是给定的常数，求证： max z2?max z1+?kiyi* i?1m 解： 证明：把原问题用矩阵表示： 共 24 页 Max z1=CX s.t. AX?b X?0 b=（b1,b2.bm)T 设 可行解为X1,对偶问题的最优解Y1=（y1，y2ym ）已知。 Max z2=CX s.t. AX?b+k X?0 k=（k1,k2.km)T 设可行解为X22,Min w=Y(b+k) S.t. YA ?C Y ?0 因为 Y2 Y2 （b+k）1） X2 z2XY ?；2A2?b+k）?Y1b+Yk 2.6 Max z=1c2x2c3x3 ?a11?a?x1?21?a12?a?x2?22?a13?x3?1?0?x4?b1?=x?1?5?b? ?2? xj?0,j?1,.,5 用单纯形法求解，得到最终单纯形表如表所示，要求： （1） 求a11，a12，a13，a21，a22，a23，b1，b2的值； （2） 求c1,c2,c3的值； 共 25 页 解： （1）初始单纯形表的增广矩阵是： a?aC1=?1112 ?a21a22a13a2310b1? 01b2? 最终单纯形表的增广矩阵为 ?1010.5?0.51.5? C2=?22?0.510?1 C2是C1作初等变换得来的，将 C2C2的第四列和第五列的矩阵成为C2 a11=9/2； a12=1； a13=4； a22=1 ； b1=9； b2=5 3=0 2.7 x+x23+6x4 s.t. 2x1+?2x1+2x23+2x4xj?0，j=1,4 *对偶变量y1，y2，其对偶问题的最优解是y1=4，y2?1，试应用对偶问题 的性质，求原问题的最优解。 解： 对偶问题是： Min w=8y1+12y2 s.t. 2y1+2y2?2 2y2?1 共 26 页 y1+y2?5 y1+2y2?6 y1，y2?0 ?，Y?是原问题和对偶问题的可行解，那么，Y?X=0互补松弛性可知，如XS 和 ?=0，当且仅当X?是最优解。 ?，YYSX 设 X,Y是原问题和对偶问题的可行解，YS有： Yy4，y5，y6） XS=0; 且 YSX=0 x5=x6=0x4最优解X=（0，0，4，4)T 44。 2.8 x1+x2 +x2 x12?7 x1,0 (2) min z=3x1+2x2+4x4 2x1+4x2+5x3+x4 ?0 3x1- x2+7x3-2x4 ?2 5x1+2x2+x3+10x4 ?15 x1 ,x2, x3, x4 ?0 解： （1） 取w=-z，标准形式： 共 27 页 Max w=-x1-x2+0x3+0x4 s.t. -2x1-x2+x3=-4 -x1-7x2+x4=-7 x1，x2，x3，x4?0 单纯形法求解（略）： 最优解： X=（21/13，10/13，0，0)T 目标函数最优值为31/13。 （2）令：w=-zMax w=-3x1-2x2-x3-4x4+06+0s.t. -2x1-4x2-5x3-x4x5=0 -3x1+x2-7x3+2x4+x612-3x4+x7=-15 x12x3xx5，x6 X=（300，6，7)T 。 2.9 max z=- 5x1+5x2+13x3 - x1+x2+3x3 ?20 12 x1+4x2+10x3 ?90 x1 ，x2， x3 ?0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？ （1） 约束条件1的右端常数20变为30 共 28 页 （2） 约束条件2的右端常数90变为70 （3） 目标函数中x3的系数变为8 ?1?（4） x1的系数向量变为? ?12? （5） 增加一个约束条件2x1+3x2+5x3?50 （6） 将约束条件2变为10x1+5x2+10x3?100 解： 把原问题化成标准型的： Max z=-5 x1+5 x2+13 x3+0 x4+0 5 s.t - x1+ x2+3 x3+ x5=20 12 x1+4 x2+10 x3+ x5=90 x1，x2，x3，x4，x5?0 单纯形法解得： 最优解： 0，0，0，10)T 100。 10 （1?30 有 ?Bb 因此 b?b?b? 单纯形法解得： 最优解： X=（0，0，9，3，0)T 目标函数最优值为117。 2右端常数变为70 （2）约束条件 有 ?b?B?1?b 因此 b?b?b? 单纯形法解得，最优解： X=（0，5，5，0，0)T 共 29 页 目标函数最优值为90。 （3）x3的系数变成8，x3是非基变量，检验数小于0，所以最优解不变。 ?0?（4）x1的系数向量变为? ?5? x1是非基变量，检验数等于-5，所以最优解不变。 3 （5）解：加入约束条件 设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元，问这对原计划有何影响？ 解： （1）设：产品三种产品的产量分别为，x1，x2，x3，建立数学模型： Max z=3x1+2x2+2.9x3 s.t. 共 30 页 8x1+2x2+10x3?300 10x1+5x2+8x3?400 2x1+13x2+10x3?420 x1,x2,x3?0 把上述问题化为标准型，用单纯形法解得： 最优解： X=（338/15，116/5，22/3，0，0，0)T 目标函数最优值为2029/15。 （2） 设备B的影子价格为4/15千元/千元每台时。 所以，借用B设备不合算。 （3） 设备?V,V生产的产量为x7x8TP7?(12,5,10) TP8?(4,4,12) 7，所以生产?V ?8合算。 X=（，0，0，0)T 。 （4）改进后,检验数?1?，大于零。 2.11分析下列参数规划中当t变化时最优解的变化情况。 （1）Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3 (t?0) s.t. x1+2x2+x3 ?430 3x1+2x3 ?460 共 31 页 x1+4x2 ?420 x1，x2，x3?0 （2）Max z(t)=(7+2t)x1+(12+t) x2+(10-t)x3 (t?0) s.t. x1+x2+x3 ?20 2x1+2x2+ x3 ?30 x1，x2，x3?0 （3）Max z(t)=2x1+x2 (0 ?t s.t. x1 ?10+2t x1 +x2 ?25-t x2 ?10+2t x1，（)x1+12x2+18x3+15x4 (0 ?t ?59) s.t. 6x1+3x3+3x4 ?6x1-3x2x3x4 ?78-t 9x1+3x2-6x3+9x4 x1，x2，x3，x4?0 解： （1）化成标准形式： Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3+0x4+0x5+0x6 (t?0) s.t. x1+2x2+x3+x4=430 3x1+2x3+x5=460 共 32 页 x1+4x2+x6=420 x1，x2，x3，x4，x5, x6?0 优解。 目标函数最优值Max z(t)=220，（0?t?8/3） 所以，t=8/3为第一临界点。 当8/3<t<5时， ?4 为换入变量，由?规则，x3为换出变量，使用单纯形法 继续迭代，t继续增大，当t>5，首先?1大于0，8/3<t?5的时候，最优解为： 共 33 页 X=（0，15，0，5)T 目标函数最优值为180+15t ，（8/3<t?5）。 所以，t=5为第二临界点。 当t>5时，x1是换入变量，x2为换出变量，单纯性法计算， 当t继续增大，所有检验数都非正，所以当t>5，最优解： X=（15，0，0，5)T 目标函数最优值为105+30t， t0 (3)化成标准型，令t=0,用单纯形法计算得： 当t开始增大，t大于5时，首先出现b20?t?5，最优解为： X=（10+2t，0，10+2t，5-t， 目标函数最优值为6t+30 ，（0所以t=5是第一临界点。 当t大于5时，x4x5 当t大于5 X=（10+2t，00，t-5)T t=0，用单纯形法计算，得： 当tt大于6b0，当0?t?6，有最优解： X=00，0，10+t/318-3t，45-5t)T （0。 当t大于b20，x6x2是换入变量，使用单纯形法计算得：t11时，b3首先小于零，x7是换出变量，x3 当 t59，有最优解： X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0)T 目标函数最优值为5t/2+345/2 ，（11<t59）。 试题： 1. （2006年西北工业大学）已知线性规划： maxz?3x1?2x2 共 34 页 ?x1?2x2?4?3x?2x?12?2s.t?1 ?x1?x2?3 ?x1,x2?0 （1） 用单纯形法求解该线性规划问题的最优解和最优值； （2） 写出线性规划的对偶问题； （3） 求解对偶问题的最优解和最优值。 解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。 T 2. （?123?y?y?y?2?3s.t?12 ?y?y?y?123?1 ?y1?0,y3?0,y2 由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的任一可行解 X都有 CX?Y b 共 35 页 ?2? ?1，所以的最大值不大于1。 1而Yb?010?z?2? ） 3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为什么？ 表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。 共 36 页 该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是： 共 37 页 表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者 2从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的 共 38 页 3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 12，直到求出初始解为止。得到下表：填入该标的最右列和最下行，重复步骤 共 39 页 又因为?34=0，此问题有无穷多最优解。 总运费min z=3*3+3*3+2*3+2*4=32 1上表中，数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1， 2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由 为基，下同）来确定 2由?ij= uivi +=cij（i，j?B，B ui v和i. cij -（ uivi +）（i，j?N）计算所有空格的检验数，并在每个格的右 上角填入单位运价，得到下表 共 40 页 1上表中，数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1， 共 41 页 2，3，4），在行中填入vj（j=1，2，3，4，5，6），先令u1=0，由 j?B，B为基，下同）来确定 2由?ij= uivi +=cij（i， ui v和i. cij -（ uivi +）（i，j?N）计算所有空格的检验数，并在每个格的右 上角填入单位运价。 由上表可以看出，所有的非基变量检验数0，此问题达到最优解。 又因为?14=0，此问题有无穷多最优解。 填入该标的最右列和最下行，重复步骤12，直到求出初始解为止。 共 42 页 又因为?31=0，此问题有无穷多最优解。 （1）（2） 2A2 到到 2B4 的单位运价22在什么范围变化时，上述最优方案不变？ 的单位运价变为何值时，有无穷多最优方案。除表1中方案 外，至少写出其他两个。 解： 1在对应表的数字格处（c22未知）填入单位运价，并增加一行，在列中(1) 填入ui（i=1，2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由 uivi +=cij 共 43 页 （i，j?B）来确定 2由?ij= ui v 和i. cij -（ uivi +）（i，j?N）计算所有空格的检验数，并在每个格的右 上角填入单位运价（c22未知）。 最优调运方案不变，则所有非基变量的检验数都是非负。所以： c22-3?0 c22+10?0 10-c22?0 24-c22?0 18-c22?0 解得: 3?c22?10 1c22（2） i（，3），在行中填入vj（j=1，2，3，4），u1=0，由 （i，j?B2由?ij= uivi +=cij i vi. cij -（ uivi +）（ijN）计算所有空格的检验数，并在每个格的右 22未知）。 0. 取c24-17=0时，该问题 有无穷多最优调运方案。 另外的两种调运方案： 1 共 44 页 2 1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。 2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。 3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤12，直到求出初始解为止。 共 45 页 1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）， 表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少030万吨，乙城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运费最低的调运方案。 共 46 页 解： 此问题的供应量小于需求量，假设供应地C，产量为70万吨。 来的可货轮如当年不交货，每艘积压一年造成积压损失40万元，在签合同时，该厂已经存储了2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费用加积压损失最少？ 解： 共 47 页 设A1，A2，A3是三年的需求订货，B1，B2，B3是三年的正常生产能力；B1?， ?，B3?是三年的加班能力，S是事先积压产生的供货能力。第三年的需求量是4B2 艘。此问题产销不平衡，增加设想销地A4，运价0，销量7. 使用伏格尔法求初始解：并用位势法检验： 此问题有无穷多最优解， 总运费 min z=4730万元 （1） 建立此运输问题的数学模型。 （2）将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。 解：（1）设xij某产品为从Ai发往销地Bj的吨数，则此运输问题的数学模型为： 共 48 页 maxz?50x11?40x12?60x13?245x21?30x22?65x23?20x31?10x32?50x33 ?x11?x12?x13?150?x21?x22?x23?200?x31?x32?x33?250?s.t?x11?x21?x31?150 ?x12?x22?x32?220?x13?x23?x33?180?xij?0,i,j?1,2,3 11（4）min z=d1?-d1? 解：（1）不正确 （2）正确 （3）正确 （4）正确 4.2 试用图解法找出以下目标函数的满意解； 共 49 页 ?（1）min z=P1（d1?+d1?）+P2（2d2+d3?） s.t. x1-10x2+d1?-d1?=50 ?3x1+5x2+d2-d2=20 8x1+6x2+d3?-d3?=100 ?，d2，d3?，d3?0 x1，x2，d1?，d1?，d2 ?（2）min z=P1（d3?+d4）+P2d1?+P3d2+P4(d3+1.54s.t. x1+x2+d1?-d1?=40 ?-d2=100 x1+x2+d2 x1+d3?-d3?=30 ?-d4=15 x2+d4 ?，23?，d3?,d4,d4x1，x2，d1?，d1?，d2?11d1?）+P2 d2+P3d3 s.t. x1+x2?-d1?3x1+4x2+d2d=50 8x1+10x2+d3?3?，d3?d3?0 x1，x2，d1?，d1?，d2 解 （1）满意解是：（50，0） （2）满意解是：（25，15） （3）满意解是：（10，0） 4.3使用单纯形法求解下列目标规划问题。 ?（1）min z=P1 d1?+P2 d2+P3（5d3+3 d4）+P4 d1 s.t. x1+x2+d1?-d1?=80 ?- d2=90 x1+x2+d2 共 50 页 x1+d3?-d3?=70 ?-d4=45 x2+d4 ?，d2，d3?，d3?,d4,d4x1，x2，d1?，d1?，d2?0 ?（2）min z=P1 d2+P1 d2+P2 d1? s.t. x1+2x2+d1?-d1?=10 ?10x1+12x2+d2-d2=62.4 x1+2x2?8 ?，d2 ?0 x1，x2，d1?，d1?，d2 ?（3）min z=P1（d1?+ d2）+P2 ?s.t. x1+x2+d1?-d1?=1 ?2x1+2x2+d2-d2=4 6x1-4x2+d3?-?=50 ?，d2，d3?，d3?0 x1，x2?，1解： （1 ?Min z=P1d2+1+P21 S.T. x1+2x2+d1?-d1?=10 ?10x1+12x2+d2-d2=62.4 2x1+x2+x3=8 ?，d2x1，x2，x3，d1?，d1?，d2?0 x3是松弛变量 共 51 页 ?-d4=10 d1?+d4 ? ，d2，d3?，d3?，d4，d4x1，x2，d1?，d1?，d2?0 （1）用单纯形法求解 ? （2）若目标函数变成min z=P1d1?+ P，3d4+P2（5d2+3 d3）+P2（5d3+3d2） 问原问题的解有什么变化？ （3）若第一个目标约束的右端改为120，原满意解有何变化？ 解： 共 52 页 （1） 单纯形法计算得到： x1=70，x2=45是满意解 （2） 实际上是对优先因子P2，P3进行调换，最优解不变。 ?0?0（3）?b?B?1?b?1?0011010100?40?0?0?0?0? 0?0?40?1?0?0? b列出现负数，d1?行的系数乘以-1，重新迭代，x1x2=45是满意解； 4.5某工厂生产两种产品，产品I每件获利10元，产品II每件获利8元。每生产1件产品I需要3小时，生产产品II需要2.5小时，每周的有效时间120小时，若加班生产，产品I每件利润少1.5元，每件产品II利润少1元，决策者希望在允许的时间和加班时间获取最大利润，试建立该问题的目标规划模型，并求解？ 解：条件不足，无法建立模型。 4.6如下表； 下表，决策者规定：2000kg 解： 设xi1i2i3，2，3）表示第i?Max z=P1(?2+d3?d4+d5d6?)+P28P7s.t. x31-0.1（x11+x31+d1?-d1? ?d2=0 x11-0.5（x11+x21+x31）+2 x32-0.7（x12+x22+x32）+d3?-d3?-d4=0 x12-0.2（x12+x22+x32）+d4 x33-0.5（x13+x23+x33）+d5?-d5?=0 ?-d6?=0 x13-0.1（x13+x23+x33）+d6 ?-d7?=2000 x11+x21+x31+d7 xij?0 (i=1,2,3;j=1,2,3) 共 53 页 其中， z=5.5(x11+x21+x31)+5(x12+x22+x32)+4.8（x13+x23+x33） -6(x11+x12+x13)-4.5(x21+x22+x23)-3(x31+x32+x33)+d8?-d8? 试题： 1. 某生产基地每天需从A、B两仓库中提取原材料用于生产，需提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120吨。已知：从A仓库每部货车能运回生产基地甲4件，乙2公斤，丙6吨，运费200元/部；从B仓库每部货车每天能运回生产基地甲7件，乙2公斤， 共 54 页 *x1?10,x2?30，恰 好是整数解。故x*?(10,30)*? A仓库B少为6800元。 第五章答案 5.1（1） x1xs.t. 2x1+3x2?4x1+x2?16.5 x1,x2?0 x1,x2是整数 （1） 解：将上述问题化为： Max z=3x1+2x2+0x3+0x4 s.t. 2x1+3x2+x3=14.5 4x1+x2+x4=16.5 共 55 页 x1,x2,x3,x4?0 x1,x2?N 2x1+3x2?14.5 4x1+x2?16.5 0?x1?3; x2?0 （II） s.t. max z2=3x1+2x2 共 56 页 2x1+3x2?14.5 4x1+x2?16.5 4?x1; x2?0 将上述问题化为标准型，使用单纯形法求解： x1=3，x2=2是最优整数解，z=13. （2）max z=3x1+2x2 s.t. 2x1+3x2?14 2x1+x2?9 x1,x2?0 x1,x2是整数 （2） 解： ，5/2） 目标函数最优值max z=59/4 1T,是可行解，； X2=(3,3) X3=(4,2)T X4=(4,3)T 令z=59/4，x1=x2=0 所以z=0，0?z*?59/4； 把原问题分解为两个问题： （a）max z1=3x1+2x2 s.t. 2x1+3x2?14 2x1+x2?9 共 57 页