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

参考答案 最后一张单纯形表如下： 第1章 线性规划与单纯形法 掌握图解法、图示解释、几何解释。 掌握单纯形法的计算步骤。 根据实际生产中的经济管理问题，建立线性规划模型，在计算机上求解。 1 将下述线性规划问题化成标准形式 解： 2 已知线性规划问题： 序号 X1 X2 X3 X4 X5 A 2 4 3 0 0 B 10 0 -5 0 4 C 3 0 2 7 4 D 1 4.5 4 0 -0.5 E 0 2 5 6 2 F 0 4 5 2 0 下表中所列的解均满足约束条件(1)-(3)，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。 (1) (2) (3) (4) p1 p2 p3 p4 p5 是基 是基 是基 基解有(a)，(b)，(f)；基可行解有(a)，(f)。 解：可行解有(a)，(c)，(e)，(f)； 3 已知某线性规划问题的约束条件为 判断下列各点是否为该线性规划问题可行域上的顶点： 不是基，故 不是基解，更不可能是基可行解。 解： 不是基，故 不是基解，更不可能是基可行解 4 下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 约束形式为 x3、x4为松弛变量，表中解代入目标函数后得Z=10。 X1 X2 X3 x4 X3 2 X1 a c d 0 e 1 0 1/5 1 Cj-Zj b -1 f g a~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/5 g=0-（0×1/5＋1×5） g=-5 a=2, b=0, c=0, d=1, e=4/5, f=0, g=-5 由于所有检验非正，故该解是最优解 这个表格为最终单纯形表 综上所述： 5 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到的表如下所示，试求括弧中未知数a~l值。 Cj-ZJ X1 X2 X3 X4 X5 X4 X5 6 1 (b) (c) (d) 1 0 -1 3 (e) 0 1 Cj-ZJ X1 X5 (f) 4 (g) 2 -1 1/2 0 (h) (i) 1 1/2 1 (a) -1 2 0 0 0 -7 (j) (k) (l) 首先由于x1、x5为基变量，故g=1, h=0, l = 0 再有 那么 ? b=1 ? c=2 ? d=-1 ? c+3=i ? d+e=1 b=2 c=4 d=-2 i=5 e=2 又有 f=3 还剩下检验数 a、j、k 检验数的定义为 如何求得c呢？ 初始单纯形表的检验数行即为目标函数中的系数C。 对迭代后的单纯形表有： a=c1=3 至此我们已获得所有的目标函数的系数 j=2-（3×-1＋0×1）＝5 k=0-（3×1/2＋0×1/2）＝-3/2 a=3, b=2, c=4, d=-2, e=2, f=3, g=1, h=0 i=5, j=5, k=-3/2, l=0 综上所述： 6 设 是线性规划问题 的最优解。若目标函数中用 代替 C 后，问题的最优解变为 求证： 证明：因为 （1） （2） 将（2）-（1）有 课堂练习 已知线性规划问题 Max Z=x1+5x2+3x3+4x4 2x1+3x2+ x3+2x4 ≤ 800 5x1+4x2+3x3+4x4 ≤ 1200 3x1+4x2+5x3+3x4 ≤ 1000 x1、x2、x3、x4 ≥0 （1）求线性规划的最优解。（20分） Cj CB XB b 检验数?j x5 x4 x2 0 4 5 100 200 100 1 5 3 4 0 0 0 x1 x2 x3 x4 x5 x6 x7 1/4 0 -13/4 0 1 1/4 -1 2 0 -2 1 0 1 -1 -3/4 1 11/4 0 0 -3/4 1 -13/4 0 -11/4 0 0 -1/4 -1