运筹学Ch1线性规划.ppt

进基列 出基行 bi /ai2，ai20 θi 表1-6 (a) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3/2 0 1 30 λj 300 400 0 0 ? ? (b) x3 x2 λj ? ? (c) x1 ? x2 10 ? λj ? ? 基变量 1 20 0 0 2/3 0 2/3 20 4/3 1 -2/3 40 100/3 0 -800/3 30 1 0 3/4 -1/2 15 0 1 -1/2 1 10 0 0 -25 -250 将3/2化为1 1.5 单纯形法 Simplex Method 20 15 最优解X=(15，10，0，0)T，最优值Z=8500 X(1)=(0,0) x1 1.5 单纯形法 Simplex Method x1 x2 O 10 20 30 40 10 20 30 40 X(2)=(0,20) X(3)=(15,10) 单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表1-6）。 计算步骤： 1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零； 2.判断： （a）若λj≤０（j＝１，２，…，n）得到最优解； （b）某个λk0且aik≤０（i=1，2,…,m）则线性规划具有无界解(见例1-18)。 （c）若存在λk0且aik (i=1,…,m)不全非正，则进行换基； 1.5 单纯形法 Simplex Method 第Ｌ个比值最小 ，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素； (c）求新的基可行解：用初等行变换方法将aLk 化为１,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。 （b）选出基变量 ，求最小比值： 1.5 单纯形法 Simplex Method 3.换基： （a）选进基变量 设λk=max｛ λj | λj 0｝,xk为进基变量 【例1-16】 用单纯形法求解 【解】将数学模型化为标准形式： 不难看出x4、x5可作为初始基变量，单纯法计算结果如表 1-7所示 。 1.5 单纯形法 Simplex Method Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 －3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 ? ? 0 x4 2 x2 λj ? ? 1 x1 ? 2 x2 ? λj ? ? 表1－7 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 －9 0 －2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 －1/9 2/3 35/3 0 0 －98/9 －1/9 －7/3 最优解X=(25，35/3，0，0，0)T，最优值Z=145/3 1.5 单纯形法 Simplex Method 【例1-17】用单纯形法求解 【解】 这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是：λj≥0(j=1，…，n)时得到最优解。 容易观察到,系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量x4,由第二个约束得到x4=6+x1－x2，并代入目标函数消去x4得 1.5 单纯形法 Simplex Method XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 -1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 -1↑ 0 0 0 ? ? x2 x4 x5 1 -2 4 1 0 0 1 -1 -2 0 1 0 0 0 1 5 1 11 ? λj 2 0 1 0 0 ? ? 表中λj≥0,j=1,2,…,5所以最优解为X=(0,5,0,1,11,)最优值 Z=2x1－2x2－x4=－2×5－1=－11 极小值问题,注意判断标准,选进基变量时,应选λj0的变量x