线性规划与单纯形法练习.ppt

《线性规划与单纯形法练习.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章线性规划与单纯形法掌握图解法、图示解释、几何解释。掌握单纯形法的计算步骤。根据实际生产中的经济管理问题，建立线性规划模型，在计算机上求解。1将下述线性规划问题化成标准形式解：2已知线性规划问题：序号X1X2X3X4X5A24300B100-504C30274D14.540-0.5E02562F04520下表中所列的解均满足约束条件(1)-(3)，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。(1)(2)(3)(4)p1p2p3p4p5是基是基是基基解有(a)，(b)，(f)；基可行解有(a)，(f)。解：可行解有(a)，(c)，(e)，(f)；3已知某线性规划问题的约束条件为判断下

2、列各点是否为该线性规划问题可行域上的顶点：不是基，故不是基解，更不可能是基可行解。解：不是基，故不是基解，更不可能是基可行解4下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为约束形式为x3、x4为松弛变量，表中解代入目标函数后得Z=10。X1X2X3x4X32X1acd0e101/51Cj-Zjb-1fga~g的值。表中给出的解是否为最优解。因为目标函数值为10，而Z=5x1+3x2,由单纯形表可知x1=a,x2=0，故a=2。因为x1、x2为基变量，所以因当满足高斯消元的形式，故c=0,d=1,b=0,f=0。由检验数的定义可知：-1＝3-（0×0＋e×5）e=4/5g=0-（

3、0×1/5＋1×5）g=-5a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5由于所有检验非正，故该解是最优解这个表格为最终单纯形表综上所述：5已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到的表如下所示，试求括弧中未知数a~l值。Cj-ZJX1X2X3X4X5X4X561(b)(c)(d)10-13(e)01Cj-ZJX1X5(f)4(g)2-11/20(h)(i)11/21(a)-12000-7(j)(k)(l)首先由于x1、x5为基变量，故g=1,h=0,l=0再有那么½b=1½c=2½d=-1½c+3=i½d+e=1b=2c=4d=-2i=5e=2又有f=3还剩下检验数

4、a、j、k检验数的定义为如何求得c呢？初始单纯形表的检验数行即为目标函数中的系数C。对迭代后的单纯形表有：a=c1=3至此我们已获得所有的目标函数的系数j=2-（3×-1＋0×1）＝5k=0-（3×1/2＋0×1/2）＝-3/2a=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0i=5,j=5,k=-3/2,l=0综上所述：6设是线性规划问题的最优解。若目标函数中用代替C后，问题的最优解变为求证：证明：因为（1）（2）将（2）-（1）有课堂练习已知线性规划问题MaxZ=x1+5x2+3x3+4x42x1+3x2+x3+2x4≤8005x1+4x2+3x3+4x4≤12003x1+4

5、x2+5x3+3x4≤1000x1、x2、x3、x4≥0（1）求线性规划的最优解。（20分）参考答案最后一张单纯形表如下：CjCBXBb检验数jx5x4x20451002001001534000x1x2x3x4x5x6x71/40-13/4011/4-120-2101-1-3/4111/400-3/41-13/40-11/400-1/4-1