[理学]线性规划上课课件.ppt

Max Z = CX s.t. AX=b X 0,基，基解，基可行解，可行基。 线性规划问题的可行域D是凸集。 顶点与基可行解相对应 线性规划问题的最优解，必定在D的顶点上达到。 目标函数在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）。,第3节 线性规划-单纯形方法 单纯形方法基本思路： 从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。,线性规划（2）-单纯形方法 单纯形方法基本思路： 从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。 如可能，从可行域中求出具有更优目标函数值的另一个基可行解（另一个顶点），以改进初始解。,线性规划（2）-单纯形方法 单纯形方法基本思路： 从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。 如可能，从可行域中求出具有更优目标函数值的另一个基可行解（另一个顶点），以改进初始解。 继续寻找更优的基可行解，进一步改进目标函数值。当某一个基可行解不能再改善时，该解就是最优解。,第三节 线性规划-单纯形方法 单纯形方法基本思路： 1.从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。,2.如可能，从可行域中求出具有更优目标函数值的另一个基可行解（另一个顶点），以改进初始解。,3.继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基可行解不能再改善时，该解就是最优解。,一、消去法 例1：一个企业需要同一两种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：数学模型 max Z = 2x1 + 3x2 s.t. x1+2x2 8 4x1 16 4x2 12 x1,x20,解：引进松弛变量x3,x4 ,x5 = 0 数学模型标准形式： max Z = 2x1 +3x2 s.t. x1+2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1 , x2 , x3 , x4 ,x5 0,约束条件的增广矩阵为： 1 2 1 0 0 8 （A b)= 4 0 0 1 0 16 0 4 0 0 1 12 显然 r(A) = r(Ab) = 3 5,该问题有无穷多组解。,令A=（P1，P2，P3，P4 ，P5） = 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 X=（x1, x2, x3, x4 , x5),A=（P1，P2，P3，P4 ，P5 ） = 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 X=（x1, x2, x3, x4 , x5)T B=(P3，P4 ，P5 ）= 1 0 0 0 1 0 0 0 1 x3, x4 , x5是基变量，x1, x2,是非基变量。,用非基变量表示的方程： x3 = 8- x1 - 2x2 x4 = 16- 4x1 (I) x5 = 12 - 4x2 Z = 0+ 2x1 +3x2 称(I) 为消去系统，,令非基变量 （ x1 , x2）T=（0，0） T 得基可行解： x(1)=(0,0,8,16,12) T Z1=0 经济含义：不生产产品甲乙，利润为零。 分析：Z = 0+ 2x1 + 3x2 （分别增加单位产品甲、乙，目标函数分别增加2、3，即利润分别增加2百元、 3百元。） 增加单位产品对目标函数的贡献，这就是检验数的概念。,增加单位产品乙（x2）比甲对目标函数的贡献大（检验数最大），把非基变量x2换成基变量，称x2为换入基变量，而把基变量x5换成非基变量，称x5为换出基变量。 （在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）,增加单位产品甲（x2）比乙对目标函数的贡献大（检验数最大），把非基变量x2换成基变量，称x2为换入基变量，而把基变量x5换成非基变量，称x5为换出基变量。 （在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则） 事实上，当x1 =0，有 x3 = 8- 2x20 x4 = 160 （） x5 = 12 - 4 x2 0 min(8/2,12/4)=3, 当x2=0时，x5=0。x5换出基变量。,确定了换入变量x2 ，换出变量x5 以后，得到新的消去系统： x3+2 x2 = 8- x1 （1） x3 = 2- x1+（1/2） x5 x4 = 16-4x1 （2） ()即： x4 = 16-4 x1 4x2 = 12- x5 （3） x2= 3 - （1/4）x5 其中（1）1/2（3） Z= 92 x1 -（3/4）x5 令新的非基变量（ x1，x5 ）=（0，0）T 得到新的基可行解： x(2)=(0,3,2, 16 , 0) T S2= 9 经济含义：生产乙产品3个，获得利润9百元。,这个方案比前方案好，但是否是最优？,这个方案比前方案好，但是否是最优？ 分析： Z= 92 x1 -（3/4）x5 非基变量x1系数仍为正数，确定x1为换入变量。在保证正消去系统的情况下，确定x3为换出变量。得到新的消去系统：,这个方案比前方案，但是否是最优？ 分析：Z=-180-x2+（3/2）x4 非基变量x2系数仍为负数，确定x2为换入变量。在保证常数项非负的情况下， x1 换入， x5=0 。有 x3 = 2-x10 x4 = 16 -4x1 0 () x2= 3 0 min2,4,- =2 确定x3为换出变量。得到新的消去系统：,x1 = 2-x3+（1/2)x5 x1 = 2-x3+（1/2)x5 4x1 + x4 = 16 （）即 x4 = 8+ 4x3 -2 x5 x2 =3-(1/4) x5 x2 =3-(1/4) x5 Z = 13-2x3+（1/4）x5 令新的非基变量（ x3，x5 ）=（0，0）T 得到新的基可行解： x(3)=(2,3,0, 16 , 0) T S3=13 经济含义：生产甲产品2个，乙产品3个，获得利润1300元。,分析： Z = 13-2x3+（1/4）x5 x5系数仍为正数，确定x5为换入变量。在保证常数项非负的情况下， x5换入， x3=0 。有 x1 = 2+（1/2）x50 x4 = 8 -2x5 0 () x2= 3-（1/4）x5 0 min- ,4,12 = 4 确定x4为换出变量。有 x1 -（1/2）x5 =2-x3 2x5= 8 +4 x3 -x4 x2 +（1/4）x5 = 3,即： x1 =4-（1/4）x4 x5=4 +2 x3 -（1/2）x4 （） x2 =2-（1/2）x3 +（1/8）x4 Z = 14-（3/2）x3-（1/8）x4 得到新的消去系统 目标函数中的非基变量的系数无正数， S4 = 14 是最优值， x(4)=(4,2, 0, 0，4) T是最优解。 该企业分别生产甲产品4个，乙产品2个可获得利润1400元。,x2,50,40,30,20,10,x1,max Z = 2x1 +3x2 s.t. x1+2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1 , x2 , x3 , x4 ,x5 0,Q1,Q2 X4,X2 Q4,X1 O,X3 Q3,4x2 = 12,4x1 = 16,x1+2x2 = 8,X1 （0，0）， X2 （0，3） X3 （2，3）， X4 （4，2）,二、已知初始可行基求最优解 线性规划标准型的矩阵形式： MAX Z = CX (1) s.t. AX=b (2) X=0 (3),a11 a12 . a1n b1 A= a21 a22 . a2n b = b2 am1 am2 . amn bn,c1 x1 0 c2 x2 0 Ct= X= 0= cn xn 0 并且 r(A)=mn.,1.初始可行基的确定和最优解判别： 不妨假设 A=（B , N）（B为一个基） 相应地有 XT= (XB , XN) C= (CB , CN) 由（1-17）（1-18） Z= (CB , CN) (XB , XN) T= CB XB+CN XN AX=（ B , N） (XB , XN) T = B XB+ N XN = b,因为B为一个基, |B|0 有 XB = B-1b- B-1N XN Z=CB XB+CN XN = CB B-1b + (CN- CB B-1N )XN 令非基变量XN = 0 则 X = (XB , XN) T =（ B-1b , 0）T为基解，其目标函数值为 Z = CB B-1b 只要XB = B-1b = 0, X=（ B-1b , 0) T =0 X为基可行解, B就是可行基。,另外，若满足 CN- CB B-1N 0 或 CB B-1N - CN 0 则对任意的 x = 0 有 Z = CX CB B-1b 即对应可行基B的可行解x为最优解。,定理（最优解判别准则） 对于可行基B ,若 C -CB B-1A 0 则对应于基B的基可行解x就是基最优解，此时的可行基就是最优基。 =C - CB B-1A为检验数。 基变量的检验数： CB- CB B-1B = 0 C - CB B-1A =（0， CN - CB B-1N ）,换入基变量中，得到基可行解,定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况） 证明：某个非基变量,为最优解。故线性规划问题有无穷多最优解。,为一基可行解，有一个变量Xm+k对应,因,为可行解。,定理：若存在检验数大于零，但所对应的换入变量Xm+k的系数向量Pm+k0,则原问题无最优解。（无界解的情况） 证明：,构造一个新的解 ，分量为,定理：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。,定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。,定理：若某一个非基变量的检验数大于0，其系数列向量Pm+k0,则原问题无最优解。（无界解的情况）,线性规划为求最大化的标准型：,线性规划为求最小化的标准型时，相应的结果？,单纯形表： T（B）= B-1b B-1A CB B-1b C-CB B-1A = B-1b I B-1N CB B-1b 0 CN - CB B-1N 注意： A=（B，N）,检验数=C - CB B-1A= （0， CN - CB B-1N ） 非基变量检验数= CN - CB B-1N,时,达到最优。,单纯形表格：,单纯形解题步骤：（已知初始可行基） 求最大化时 一、作对应B的单纯形表： T（B）= B-1b B-1A CB B-1b C -CB B-1A = B-1b I B-1N CB B-1b 0 CN - CB B-1N,单纯形解题步骤： 二、判别 若检验数全小于等于零，则基B所对应的基础可行解X就是最优解，终止。 若存在检验数大于零，但所对应的换入变量Xk的系数向量Pk0,则原问题无最优解，终止。 若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。,三、换基迭代 确定换入变量Xk，其中 max(j 0)= k, xk为换入变量 j=1,2,m 确定换出基变量Xr,根据最小比值原则 min (bi/aik , aik 0 , 1im) = bl/blk alk为主元素, Xl为换出基变量。,对单纯形表T（B）进行初等行变换（主元运算）得到新的单纯形表。 经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。,例1-19 求线性规划问题： max Z = 2x1 + 3x2 s.t. x1+2x2 =0,解：对目标函数标准化 max Z = 2x1 +3x2 s.t. x1+2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1 , x2 , x3 , x4 ,x5 = 0 1 2 1 0 0 A= 4 0 0 1 0 0 4 0 0 1 （ x1 x2 x3 x4 x5 ） =（ N B ）,解： 1 0 0 B= 0 1 0 = I b = (8,16,12)T 0 0 1 x3 x4,x5为基变量，CB=（0，0, 0） x1 ,x2为非基变量。 有B-1=I, B-1b=b, B-1A=A,单纯性表如下：,初始单纯性表TAB(1)为：,x2换入,x5 换出；得TAB(2)为：,x1换入,x3换出；得TAB(3)为：,x5换入,x4 换出；得TAB(4)为：,此时所有的检验数小于等于零，此时的基可行解 X=（4，2，0，0,4）T 就是最优解，对应的目标函数值： Z = 14 就是最优值，对应的B4就是最优基。,求最大化LP问题单纯形表解题步骤： 一. LP问题化成标准型,列初始单纯形表,二.判别 1.若检验数全小于等于零，则基B所对应的基础可行解X就是最优解，终止。 2.若存在检验数大于零，但所对应的换入变量Xk的系数向量Pk0,则原问题无最优解，终止。 3.若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。,三.换基迭代 1.确定换入变量Xk，其中 max(j 0)= k, xk为换入变量 j=1,2,m 2.确定换出基变量Xr,根据最小比值原则 min (bi/aik , aik 0 , 1im) = bl/blk alk为主元素, Xl为换出基变量。,对单纯形表T（B）进行初等行变换（主元运算）得到新的单纯形表。 经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。,定理（求最小化的最优解判别准则） （1）若= C -CB B-1A 0 ，则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。 （2）若检验数全大于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况） （3）若存在检验数小于零，但所对应的换入变量Xm+k的系数向量Pm+k0,则原问题无最优解。（无界解的情况） 确定换入变量时，找小于0中的最小者。,例8 线性规划问题,一.大M法,当原问题求最大化时，假定人工变量在目标函数中的系数为（- M）（M为任意大正数），目标函数求最大化，必须把人工变量从基变量换出，否则，不可能实现最大化。,当原问题求最小化时，假定人工变量在目标函数中的系数为M（M为任意大正数），目标函数求最小化，必须把人工变量从基变量换出，否则，不可能实现最小化。,例8 线性规划问题,-3 1 1 0 0 M M,cj,cj,-3 1 1 0 0 M M,线性规划问题达到最优,最优解及最优值为:,二.两阶段法,当用计算机求解含人工变量的线性规划问题时，只能用很大的数代替M，否则，会造成计算机的错误。而两阶段法避免了这一错误。,第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，构造目标函数为人工变量的和，约束是原问题的约束。 用单纯形法求解上述模型，若目标函数值为0，说明原问题有基可行解，进行第二阶段计算，否则，原问题无可行解。,第二阶段：将第一阶段计算得到的最终表，除 去人工变量，将目标函数行的系数，换为原问 题的目标函数系数，作为第二阶段计算的初始表。,例9 线性规划问题,解：加入人工变量，给出第一阶段的线性规划模型:,人工变量已经换出，则=0，得到基可行解，将第一阶段的人工变量取消，填入原问题的目标函数的系数，进行第二阶段运算。,cj,0 0 0 0 0 1 1,人工变量已经换出，则=0，得到基可行解，将第一阶段的人工变量取消，即上表中划去人工变量所在列，填入原问题的目标函数的系数，进行第二阶段运算。,cj -3 1 1 0 0,最优解为：x 1,=4 ,x 2,=1, x 3=9, 最优值z=-2.,应用举例,例1 配料问题 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价见下表。该厂应如何安排生产，使利润收入为最大？,解：设xij为产品A、B、D中含C、P、H的公斤数。列表如下：,解：数学模型为：,例2 连续投资问题 某部门有100万元，在今后五年内考虑给下列项目进行投资 项目A:从第一年到第四年每年年初需要投资，并于次年末回收 本利104； 项目B:从第三年初投资，到第五年末回收 本利105；但规定 最大投资额不超过40万元； 项目C:从第二年初投资，到第五年末回收 本利108；但规定 最大投资额不超过30万元； 项目D:五年内每年可购买国债，于当年末归还，并加息3； 问该部门如何确定每年的投资计划，使五年末拥有的本金最大？,解：设xiA, xiB, xiC, xiD,分别表示第i年年初给项目A、B、C、D的投资额。列表如下：,数学模型为：,人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数：Min Z=x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0,