第一章线性规划及单纯形法

第一章 线性规划及单纯形法1.1 用图解法求解下列线性规划问题。并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。(a) min z=2x1+3x2 (b) max z=3x1+2x2s.t. 4x1+6x26 s.t. 2x1+x224x1+2x2 4 3x1+4x212x1, x20 x1,x20(c) max z=x1+x2 (d) max z=5x1+6x2s.t. 6x1+10x2120 s.t. 2x1-x225x 110 -2x1+3x223x 28 x1,x20解：1 2x2x1L1L2Lz(a)3121 2x2L1L2Lz(b)33 4x110510 2015x2x1Lz1-2-1 12x2x1Lz12(c)(d)如图所示：(a) 有无穷多最优解；(b) 无可行解；(c) 有唯一最优解; (d) 无界解1.3 用单纯形法求解下述线性规划问题max z=10x1+5x2s.t. 3x1+4x295x1+2x28x1, x20解：将此问题化成标准形式，max z=10x1+5x2+0x3+0x4s.t. 3x1+4x2+x3 =95x1+2x2 +x4=8x1, x2, x3, x40其约束系数矩阵： 102543431P单纯形法求解的过程见表如下单纯形法的求解过程Cj 10 5 0 0CB 基 b X1 X2 X3 X40 X3 9 3 4 1 00 X4 8 5 2 0 1Cj-zj 10 5 0 0由于 105, 选择 x1 作为换入基的变量。对于 P1 有：=min b1/a11, b2/a21 | a11,a210 =min9/3, 8/5 =8/5. 确定 x4 为换出基变量。5为主元素单纯形法的求解过程Cj 10 5 0 0CB 基 b X1 X2 X3 X40 X3 21/5 0 14/5 1 -3/510 X1 8/5 1 2/5 0 1/5Cj-zj 0 1 0 -2由于 10, 选择 x2 作为换入基的变量。对于 P2 有：=min b1/a12, b2/a22 | a12,a220 =min(21/5)/(14/5),(8/5)/(2/5) =21/14. 确定 x3为换出基变量。2/5 为主元素单纯形法的求解过程Cj 10 5 0 0CB 基 b X1 X2 X3 X45 X2 3/2 0 1 5/14 -3/1410 X1 1 1 0 -1/7 10/35Cj-zj 0 0 -5/14 -25/14至此，所有检验数 j0，表明已找到最优解 x1=1, x2=1.5, x3=0, x4=0max z=10x1+5x2=17.52123x2x1Lz1(c)2861010104L1L21.8 已知某线性规划问题的初始单纯性表(1-23)和用单纯形法迭代后得到的表(1-24)如下，试求括弧中未知数 ql 的值。表 1-23x1 x2 x3 x4 x5x4 6 (b) (c) (d) 1 0x5 1 -1 3 (e) 0 1cj-zj (a) -1 2 0 0表 1-24x1 x2 x3 x4 x5x1 (f) (g) 2 -1 1/2 0x5 4 (h) (i) 1 1/2 1cj-zj 0 -7 (j) (k) (l)解：由表 1-23 和 1-24 可知换出变量为 x4，换入变量为 x1。又因为 a21=-10所以，主元只能是 b。所以有 g=1, h=0, c/b=2, d/b=-1, 1/b=1/2. 6/b=f于是 b=2, c=4, d=-2, f=3。将这些数值代入相应参数，表 1-23 变成 表 1-23bx1 x2 x3 x4 x5x4 6 2 4 -2 1 0x5 1 -1 3 (e) 0 1cj-zj (a) -1 2 0 0主元所在行除 2 得：表 1-23cx1 x2 x3 x4 x5x1 3 1 2 -1 1/2 0x5 1 -1 3 (e) 0 1cj-zj (a) -1 2 0 0由表 1-23c 将 a21 化为 0 得表 1-23dx1 x2 x3 x4 x5x1 3 1 2 -1 1/2 0x5 4 0 5 （ e-1） 1/2 1cj-zj 0 -2a-1 a+2 -a/2 0将表 1-23d 与表 1-24 比较后有：e-1=1, e=2, i=5. 由检验数关系得-2a-1=-7,a=3; j=a+2=5; k=-a/2=-3/2; l=0最终表 2-24 结果为表 1-24ax1 x2 x3 x4 x5x1 3 1 2 -1 1/2 0x5 4 0 5 1 1/2 1cj-zj 0 -7 5 -3/2 01.12 已知线性规划问题max z=c1x1+c2x2+c3x3s.t. x1+2x2+x3b2x1+x2+3x3 2bxj0 (j=1,2,3)用单纯形法求解得最终单纯形表 1-25，表中 x4, x5 为松弛变量表 1-25x1 x2 x3 x4 x5x2 1 1/5 1 0 3/5 -1/5x3 3 3/5 0 1 -1/5 2/5cj-zj -7/10 0 0 -3/5 -4/5试计算确定 c1, c2, c3 和 b 的值。解：因为 x4, x5 为松弛变量，所以 c4=c5=0.由书中式 1-23，对应 x1,x4,x5 检验数计算可有 10731)(2213211 cacacmii550)( 3224312414ii4)1()( 3225312515 caccacmii其增广矩阵： 5/4/25/1030/7/经初等变换得：