运筹学课件_林齐宁_第一章_线性规划与单纯形法 (2)

1、管理与人文学院管理与人文学院 忻展红忻展红 1999，4运筹学Operational Research英英 Operations Research美美运筹帷幄之中，决胜千里之外运筹帷幄之中，决胜千里之外 史记史记留侯世家留侯世家2目目 录录绪绪 论论第一章第一章 线性规划问题及单纯型解法线性规划问题及单纯型解法第二章第二章 线性规划的对偶理论及其应用线性规划的对偶理论及其应用第三章第三章 运输问题数学模型及其解法运输问题数学模型及其解法第四章第四章 整数规划整数规划第五章第五章 动态规划动态规划第六章第六章 图与网路分析图与网路分析第七章第七章 随机服务理论概论随机服务理论概论第八章第八章 生

2、灭服务系统生灭服务系统第九章第九章 特殊随机服务系统特殊随机服务系统第十章第十章 存储理论存储理论3第一章第一章 线性规划问题及单纯型解法线性规划问题及单纯型解法1.1 线性规划问题及其一般数学模型线性规划问题及其一般数学模型1.1.1 1.1.1 线性规划问题举例线性规划问题举例例例1 1、多产品生产问题、多产品生产问题（Max, ）设设x1, x2 分别代表甲、乙两种电缆的生产量，分别代表甲、乙两种电缆的生产量，.36)(max, 6, 2:0,78102.46)(max:21212212121xfxxxxxxxxxtsxxxfOBJ最优解最优解产量不允许为负值产量不允许为负值产量约束产量

3、约束铅资源约束铅资源约束铜资源约束铜资源约束4例例2、配料问题（、配料问题（min, ) )原原料料甲甲 原原料料乙乙 最最低低含含量量VA0.50.52VB11.00.33VB20.20.61.2VD0.50.22单单价价0.30.5设设 x1, x2分别代表每粒胶丸中甲、分别代表每粒胶丸中甲、乙两种原料的用量乙两种原料的用量0,22 . 05 . 02 . 16 . 02 . 033 . 00 . 125 . 05 . 0. .5 . 03 . 0)(min212121212121xxxxxxxxxxtsxxxf5例例3、合理下料问题、合理下料问题 设设 xj 分别代表采用切割方案分别代表

4、采用切割方案18的套数，的套数，方方案案2.9m2.1m1.5m合合计计余余料料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.2根，但购买最优解为则有零料最少若目标函数为使裁剪后15010,50,100:0,100231002321002.2 . 01 . 109 . 03 . 01 . 0)(min,64654321643165324321654321OBJxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf616 ;90,30,50,10:0,100231002321002. .)(min,421654321643

5、165324321654321但余料为最优解则有钢筋最少若目标函数为使购买的OBJxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf7 1.1.2 线性规划数学模型的一般表示方式线性规划数学模型的一般表示方式技技术术系系数数右右端端项项价价值值系系数数线线性性规规划划问问题题的的规规模模约约束束行行数数变变量量个个数数: ;: ;: ;: ;:0,),(),(),(.)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf8 1、和式和式njxmibx

6、atsxcxfjinjjijnjjj, 2 , 1 , 0, 2 , 1 ,.)(max119 2、向量式向量式0000 ),( );,( .)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj10 3、矩阵式矩阵式 ),(),();,(.)(max212121212222111211TmTnnmnmmnnbbbbxxxXcccCaaaaaaaaaA0XbAXtsCXxf11 1.1.3 线性规划的图解法线性规划的图解法1187654322x1876543O109x2A BCEDFGH123f(x)=0f(x)=12.36)(max

7、, 6, 2:0,78102.46)(max21212212121xfxxxxxxxxxtsxxxf最优解最优解1187654322x1876543O109x2A BCEDFGH123f(x)=3612 线性规划问题的几个特点：线性规划问题的几个特点： 线性规划问题的可性解的集合是凸集线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解都对应于凸集的极线性规划问题的基础可行解都对应于凸集的极点点 凸集的极点的个数是有限的凸集的极点的个数是有限的 最优解必然在凸集的极点上，而不可能发生在最优解必然在凸集的极点上，而不可能发生在凸集的内部凸集的内部131.2 线性规划问题的单纯型解法线性规划

8、问题的单纯型解法1.2.1 解解线性规划问题的标准形式线性规划问题的标准形式为了使线性规划问题的解法标准化，就要把一般形为了使线性规划问题的解法标准化，就要把一般形式化为标准形式式化为标准形式njxmibxatsxcxfjinjjijnjjj,2, 1 ),0(0,2, 1 ,),(.)(max(min)11不不限限njmixbmibxatsxcxfjiimnjjijmnjjj,2, 1 ,2, 1 ,0,2, 1 ,.)(max1114 变换的方法：变换的方法：目标函数为目标函数为min型，价值系数一律反号。令型，价值系数一律反号。令 f (x) = - -f(x) = - -CX, 有有

9、min f(x) = - - max - - f(x) = - - max f (x)第第i 个约束的个约束的bi 为负值，则该行左右两端系数同时反号，为负值，则该行左右两端系数同时反号，同时不等号也要反向同时不等号也要反向第第i 个约束为个约束为 型，在不等式左边增加一个非负的变型，在不等式左边增加一个非负的变量量xn+i ，称为松弛变量；同时令称为松弛变量；同时令 cn+i = 0第第i 个约束为个约束为 型，在不等式左边减去一个非负的变型，在不等式左边减去一个非负的变量量xn+i ，称为剩余变量；同时令称为剩余变量；同时令 cn+i = 0若若xj 0，令，令 xj= - -xj ，代入

10、非标准型，则有，代入非标准型，则有xj 0若若xj 不限，令不限，令 xj= xj - - xj ， xj 0，xj 0，代入非标代入非标准型准型15 变换举例：变换举例：0, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非标准型原非标准型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型16 关于标准型解的若干基本概念：关于标准型解的若干基本概念： 标准型有标

11、准型有 n+m 个变量，个变量， m 个约束行个约束行 “基基”的概念的概念 在标准型中，技术系数矩阵有在标准型中，技术系数矩阵有 n+m 列，即列，即 A = ( P1, P2 , , Pn+m ) A中线性独立的中线性独立的 m 列，构成该标准型的一个列，构成该标准型的一个基基，即，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 称为称为基向量基向量 与与基向量基向量对应的变量称为对应的变量称为基变量基变量，记为，记为 XB = ( x1 , x2 , , xm )T，其余的变量称为，其余的变量称为非基变量非基变量，记为记为 XN = (

12、xm+1 , xm+2 , , xm+n ) T ， 故有故有 X = XB + XN 最多有最多有 个基个基mnmC17 关于标准型解的若干基本概念：关于标准型解的若干基本概念： 可行解可行解与与非可行解非可行解 满足约束条件和非负条件的解满足约束条件和非负条件的解 X 称为称为可行解可行解，满足，满足约束条件但不满足非负条件的解约束条件但不满足非负条件的解 X 称为称为非可行解非可行解 基础解基础解 令令非基变量非基变量 XN = 0，求得，求得基变量基变量 XB的值称为的值称为基础解基础解 即即 XB = B 1 b XB 是是基础解基础解的的必要条件必要条件为为XB 的非零分量个数的非

13、零分量个数 m 基础可行解基础可行解 基础解基础解 XB 的非零分量都的非零分量都 0 时，称为时，称为基础可行解基础可行解，否则为否则为基础非可行解基础非可行解 基础可行解基础可行解的非零分量个数的非零分量个数 0, 则未达到最优则未达到最优(5) (4) )3( )()()(2) )(1) )(1jjmiijijNN1BN1BNN1BNNNN1BNNBBNNBBNNzcaczXABCCbBCXAbBCXCxfXAbBXXAbBXbBXXAXCXCxf检验数检验数机会成本机会成本24 1.2.4 标准型的单纯型算法标准型的单纯型算法1 找初始基础可行基找初始基础可行基 对于对于(max, )

14、，松弛变量对应的列构成一个单位阵，松弛变量对应的列构成一个单位阵 若有若有 bi 0 中找最大者，选中者称为中找最大者，选中者称为入变量入变量， xj* 第第j*列称为列称为主列主列4 确定确定入变量入变量的最大值和的最大值和出变量出变量 最小比例原则最小比例原则(1.2.4) 0min*ijijiiaab 25 1.2.4 标准型的单纯型算法标准型的单纯型算法4 确定确定入变量入变量的最大值和的最大值和出变量出变量 设第设第 i* 行使行使 最小，则第最小，则第 i* 行对应的基变量称为行对应的基变量称为出变量出变量，第，第 i* 行称为行称为主行主行5 迭代过程迭代过程 主行主行 i* 行

15、与行与主列主列 j* 相交的元素相交的元素ai*j* 称为称为主元主元，迭代，迭代以以主元主元为中心进行为中心进行 迭代的实质是线性变换，即要将迭代的实质是线性变换，即要将主元主元 ai*j*变为变为1，主主列列上其它元素变为上其它元素变为0，变换步骤如下：，变换步骤如下：(1)变换主行变换主行nmjaaajijiji, 2 , 1*26 1.2.4 标准型的单纯型算法标准型的单纯型算法5 迭代过程迭代过程(2)变换主列变换主列除除主元主元保留为保留为1，其余都置，其余都置0(3)变换非主行、主列元素变换非主行、主列元素 aij (包括包括 bi)四角算法公式四角算法公式：数数据据表表示示当当

16、前前单单纯纯型型表表中中的的的的数数据据表表示示上上一一个个单单纯纯型型表表中中 ,(1.2.5b) (1.2.5a) *ijijijiijjiijijjiijiiiaabaaaaaaabbb27 1.2.4 标准型的单纯型算法标准型的单纯型算法5、迭代过程、迭代过程(4)变换变换CB，XB(5)计算目标函数、机会成本计算目标函数、机会成本 zj 和检验数和检验数 cj zj 6、返回步骤、返回步骤 2aijai*jaij*ai*j*主主行行主主列列主主元元四四角角算算法法图图示示28 表表1.2.4 例例1.2.2 单纯型表的迭代过程单纯型表的迭代过程x1x2x3x4x5序序号号CBXBb4

17、0452400bi/aij*0 x41002(3)110(33.3)0 x51203320140 OBJ = 000000I初初始始解解cj- -zj4045240045x2100/3 2/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -zj1009 15045x22001 1/31 2/340 x120101 11 OBJ = 1700404525510III最最优优解解cj- -zj00 1 5 10答：最优解为答：最优解为 x1=20, x2=20, x3=0, OBJ=170029 单纯型表中元素的几点说明单纯型表中元素的

18、几点说明 任何时候，基变量对应的列都构成一个单位矩阵任何时候，基变量对应的列都构成一个单位矩阵 当前表中的当前表中的 b 列表示当前基变量的解值，通过变换列表示当前基变量的解值，通过变换 B 1 b 得到得到 (资源已变成产品资源已变成产品) 当前非基变量对应的向量可通过变换当前非基变量对应的向量可通过变换 B 1 AN 得到，得到， 表示第表示第 j 个变量对第个变量对第 i 行对应的基变量的消耗率行对应的基变量的消耗率 非基变量的机会成本由非基变量的机会成本由 给出给出 注意基变量所对应的行注意基变量所对应的行x1x2x3x4x5序序号号CBXBb40452400bi/aij*45x210

19、0/3 2/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -zj1009 150ijamiijijacz1 301.3 人工变量的引入及其解法人工变量的引入及其解法 1.3.1 当约束条件为当约束条件为“ ”型，引入剩余变量和人工变型，引入剩余变量和人工变量量 由于所添加的剩余变量的技术系数为由于所添加的剩余变量的技术系数为 1，不能作为初，不能作为初始可行基变量，为此引入一个人为的变量（注意，此始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为时约束条件已为“=”型），以便取得初始基变量，故型），以便取得初始基变量，故

20、称为人工变量称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定法而定 两种方法两种方法 大大M法法 二阶段法二阶段法31 1.3.2 大大M法的求解过程法的求解过程 例例1.3.10,46 2.7810)(min32132121321xxxxxxxxtsxxxxf0,4 6 2. .)7810max()(max654321532164216321xxx

21、xxxxxxxxxxxtsMxxxxxf32 表表1.3.1 例例1.3.1的单纯型表迭代过程的单纯型表迭代过程x1x2x3x4x5x6序序号号CBXBb 10 8 700 M bi/aij* Mx66(2)10 101(3) 7x341110 104 6M 28 2M 7 M 7 7M7 MI初初始始解解cj zj2M 3M 10 M 70 10 x1311/20 1/201/26 7x310(1/2)11/2 1 1/2(2) 37 10 17/2 73/27 3/2IIcj zj01/20 3/2 7 M+3/2 10 x1210 1 111 8x220121 2 1 36 10 8 6

22、26 2III最最优优解解cj zj00 1 2 6 M+2答：最优解为答：最优解为 x1=2, x2=2, x3=0, OBJ=3633 大大M法的一些说明法的一些说明 大大M法实质上与原单纯型法一样，法实质上与原单纯型法一样，M 可看成一个很可看成一个很大的常数大的常数 人工变量被迭代出去后一般就不会再成为基变量人工变量被迭代出去后一般就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题量，说明原线性规划问题无可行解无可行解 大大M法手算很不方便法手算很不方便 因此提出了二阶段法因此提出了二阶段法 计算机中常用大

23、计算机中常用大M法法 二阶段法手算可能容易二阶段法手算可能容易34 1.3.3 二阶段法的求解过程二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去，从而第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原若第一阶段结束时，人工变量仍在基变量中，则原问题无解问题无解 为了简化计算，在第一阶段重新定义价值系数如下：为了简化计算，在第一阶段重新定义价值系数如下：不不

24、是是人人工工变变量量时时当当为为人人工工变变量量时时当当时时目目标标函函数数为为不不是是人人工工变变量量时时当当为为人人工工变变量量时时当当时时目目标标函函数数为为jjjjjjjjxcxcxcxc01max01min35 表表1.3.2 用二阶段法求解例用二阶段法求解例1.3.1的第一阶段的第一阶段x1x2x3x4x5x6序序号号CBXBb00000 1bi/aij* 1x66(2)10 101(3)0 x341110 104 6 2 1010 1Icj zj210 1000 x1311/20 1/201/20 x3101/211/2 1 1/2 0000000IIcj zj00000 136

25、 表表1.3.2 用二阶段法求解例用二阶段法求解例1.3.1的第二阶段的第二阶段x1x2x3x4x5序序号号CBXBb 10 8 700bi/aij* 10 x1311/20 1/206 7x310(1/2)11/2 1(2) 37 10 17/2 73/27Icj zj01/20 3/2 7 10 x1210 1 11 8x220121 2 36 10 8 626IIcj zj00 1 2 6最优解对应的最优解对应的B1在哪？在哪？371.5 单纯型法的一些具体问题单纯型法的一些具体问题1.5.1 关于无界解问题关于无界解问题 可行区域不闭合可行区域不闭合(约束条件有问题约束条件有问题) 单

26、纯型表中入变量单纯型表中入变量 xj* 对应的列中所有对应的列中所有0a*ij0,501002.)(max1 . 5 . 1 21212121xxxxxxtsxxxf例例f(x)=x1+x2x1x2505050100 x1-x2=50-2x1+x2=10038 表表1.5.1 例例1.5.1 的单纯型表及其迭代过程的单纯型表及其迭代过程x1x2x3x4序号CBXBb1100bi/aij*0 x310021100 x450(1)101(50) OBJ = 00000I初始解cj-zj11000 x32001121x1501101 OBJ = 50101IIcj-zj020 39 1.5.2 关于

27、退化问题关于退化问题 退化问题的原因很复杂，当原问题存在平衡约束时退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环，克服死循环的退化的严重性在于可能导致死循环，克服死循环的方法有方法有“字典序字典序”法法0, 060240.43)(max1.5.2 2121212121xxxxxxxxtsxxxf例例x1x2x3x4序号CBXBb3400bi/aij*0 x340(2)10(20)0 x460001(20)3x10100 OBJ = 03300IIcj-zj07004x22011/

28、200 x4003/213x12011/20 OBJ = 14033.50IIIcj-zj003.540 1.5.3 关于多重解问题关于多重解问题 多个基础可行解都是最优解，这些解在同一个超平多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行面上，且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为最优单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=10,12023310032.254540)(max 1.5.3 321321321321xxxxxxxxxtsxxxxf多重最优解多重最优解例例41 表表1.5.3 例例1.5.3 的单纯型表及其迭代过程的单纯型表及其迭代过程x1x2x3x4x5序序号号CBXBb40452500bi/aij*0 x41002(3)110(33.3)0 x51203320140 OBJ = 000000I初初始始解解cj- -zj40452500 迭迭代代 过过程程45x22001 1/31 2/3 40 x12010(1) 11(20) OBJ = 1700404525510III最最优优解解cj- -zj000 5 1045x226.67 1/3102/3 1/325