运筹学OperationalResearch

《运筹学OperationalResearch》由会员分享，可在线阅读，更多相关《运筹学OperationalResearch（51页珍藏版）》请在装配图网上搜索。

1、运筹学Operational Research运筹帷幄，决胜千里运筹帷幄，决胜千里 史记史记张良传张良传2目目 录录绪绪 论论第一章第一章 线性规划问题及单纯型解法线性规划问题及单纯型解法第二章第二章 线性规划的对偶理论及其应用线性规划的对偶理论及其应用第三章第三章 运输问题数学模型及其解法运输问题数学模型及其解法第四章第四章 整数规划整数规划第五章第五章 动态规划动态规划第六章第六章 图与网路分析图与网路分析第七章第七章 随机服务理论概论随机服务理论概论第八章第八章 生灭服务系统生灭服务系统第九章第九章 特殊随机服务系统特殊随机服务系统第十章第十章 存储理论存储理论3绪 论一、运筹学的起源与

2、发展一、运筹学的起源与发展二、运筹学的特点及研究对象二、运筹学的特点及研究对象三、运筹学解决问题的方法步骤三、运筹学解决问题的方法步骤四、运筹学的发展趋势四、运筹学的发展趋势4一、运筹学的起源与发展一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科起源于二次大战的一门新兴交叉学科 与作战问题相关与作战问题相关 如雷达的设置、运输船队的护航、反潜作战中深水炸弹如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等的深度、飞行员的编组、军事物资的存储等 英国称为英国称为 Operational Research 美国称为美国称为 Operations Rese

3、arch 战后在经济、管理和机关学校及科研单位继续研究战后在经济、管理和机关学校及科研单位继续研究 1952年，年，Morse 和和 Kimball出版出版运筹学方法运筹学方法 1948年英国首先成立运筹学会年英国首先成立运筹学会 1952年美国成立运筹学会年美国成立运筹学会 1959年成立国际运筹学联合会年成立国际运筹学联合会(IFORS)我国于我国于1982年加入年加入IFORS，并于，并于1999年年8月组织了第月组织了第15届大会届大会5二、运筹学的特点及研究对象二、运筹学的特点及研究对象 运筹学的定义运筹学的定义 为决策机构对所控制的业务活动作决策时，提供以数量为决策机构对所控制的业

4、务活动作决策时，提供以数量为基础的科学方法为基础的科学方法Morse 和和 Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针及其产生的后果，以帮助主管人员科学地决定工作方针和政策和政策英国运筹学会英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统运筹学是应用分析、试验、量化的方法对经

5、济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理供有根据的最优方案，以实现最有效的管理中国百中国百科全书科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science6二、运筹学的特点及研究对象二、运筹学的特点及研究对象 运筹学的分支运筹学的分支 数学规划：线性规划、非线性规划、整数规划、动态规数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等划、目标规划等 图论与网路理论图论与网路理论 随机服务理论：排队论随机

6、服务理论：排队论 存储理论存储理论 决策理论决策理论 对策论对策论 系统仿真：随机模拟技术、系统动力学系统仿真：随机模拟技术、系统动力学 可靠性理论可靠性理论 金融工程金融工程7三、运筹学解决问题的方法步骤三、运筹学解决问题的方法步骤 明确问题明确问题 建立模型建立模型 设计算法设计算法 整理数据整理数据 求解模型求解模型 评价结果评价结果明确问题明确问题建立模型建立模型设计算法设计算法整理数据整理数据求解模型求解模型评价结果评价结果简化？简化？满意？满意？YesNoNo8四、运筹学的发展趋势四、运筹学的发展趋势 运筹学的危机运筹学的危机 脱离实际应用，陷入数学陷阱脱离实际应用，陷入数学陷阱

7、IT对运筹学的影响对运筹学的影响 MIS,DSS,MRP-II,CIMS,ERP OR Dept.-Dept.Of OR&IS 运筹学与行为科学结合运筹学与行为科学结合 群决策和谈判群决策和谈判 对策理论对策理论 多层规划多层规划 合理性分析合理性分析 服务行业中的应用服务行业中的应用 金融服务业金融服务业 信息、电信服务业信息、电信服务业 医院管理医院管理9四、运筹学的发展趋势四、运筹学的发展趋势 软计算软计算 面向强复杂系统的计算、实时控制、知识推理面向强复杂系统的计算、实时控制、知识推理 智能算法：模拟退火、遗传算法、人工神经网络、戒律智能算法：模拟退火、遗传算法、人工神经网络、戒律算法

8、等算法等 系统仿真系统仿真 面向问题面向问题 后勤后勤(Logistics)全球供应链管理全球供应链管理 电子商务：集成特性电子商务：集成特性 随机和模糊随机和模糊 OR 问题本身的不确定性问题本身的不确定性 人类知识的局限性人类知识的局限性10第一章第一章 线性规划问题及单纯型解法线性规划问题及单纯型解法1.1 线性规划问题及其一般数学模型线性规划问题及其一般数学模型1.1.1 1.1.1 线性规划问题举例线性规划问题举例例例1 1、多产品生产问题、多产品生产问题（Max,）设设x1,x2 分别代表甲、乙两种电缆的生产量，分别代表甲、乙两种电缆的生产量，.36)(max,6,2:0,7810

9、2.46)(max:21212212121xfxxxxxxxxxtsxxxfOBJ最优解最优解产量不允许为负值产量不允许为负值产量约束产量约束铅资源约束铅资源约束铜资源约束铜资源约束11例例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)(min212121212121xxxxxxxxxxtsx

10、xxf12例例3、合理下料问题、合理下料问题 设设 xj 分别代表采用切割方案分别代表采用切割方案18的套数，的套数，方方案案2.9m2.1m1.5m合合计计余余料料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.210,50,100:0,100231002321002.2.01.109.03.01.0)(min,64654321643165324321654321OBJxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf最优解为则有零料最少若目标函数为使裁剪后16,30,50,10:0,100231002321002.

11、)(min,421654321643165324321654321OBJxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf则有最优解为则有钢筋最少若目标函数为使购买的13 1.1.2 线性规划数学模型的一般表示方式线性规划数学模型的一般表示方式技技术术系系数数右右端端项项价价值值系系数数线线性性规规划划问问题题的的规规模模约约束束行行数数变变量量个个数数:;:;:;:;:0,),(),(),(.)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf1

12、4 1、和式和式njxmibxatsxcxfjinjjijnjjj,2,1 ,0,2,1 ,.)(max1115 2、向量式向量式0000 ),();,(.)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj16 3、矩阵式矩阵式 ),(),();,(.)(max212121212222111211TmTnnmnmmnnbbbbxxxXcccCaaaaaaaaaA0XbAXtsCXxf17 1.1.3 线性规划的图解法线性规划的图解法1187654322x1876543O109x2A BCEDFGH123f(x)=0f(x)=12.

13、36)(max,6,2:0,78102.46)(max21212212121xfxxxxxxxxxtsxxxf最优解最优解1187654322x1876543O109x2A BCEDFGH123f(x)=3618 线性规划问题的几个特点：线性规划问题的几个特点：线性规划问题的可性解的集合是凸集线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的凸集的极点的个数是有限的 最优解只可能在凸集的极点上，而不可能发生在凸集最优解只可能在凸集的极点上，而不可能发生在凸集的内部的内部191.2 线性规划问题

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

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

16、，令 xj=xj -xj，xj 0，xj 0，代入非标代入非标准型准型21 变换举例：变换举例：0,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非标准型原非标准型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型22 关于标准型解的若干基本概念：关于标准型解的若干基本概念：标准型有标准型有 n+m 个变量，个变量，m 个约束行个约束行“基基”的概念的概念 在标准型

17、中，技术系数矩阵有在标准型中，技术系数矩阵有 n+m 列，即列，即 A=(P1,P2 ,Pn+m )A中线性独立的中线性独立的 m 列，构成该标准型的一个列，构成该标准型的一个基基，即，即 B=(P1 ,P2 ,Pm )，|B|0 P1 ,P2 ,Pm 称为称为基向量基向量 与与基向量基向量对应的变量称为对应的变量称为基变量基变量，记为，记为 XB=(x1 ,x2 ,xm )T，其余的变量称为，其余的变量称为非基变量非基变量，记为记为 XN=(xm+1 ,xm+2 ,xm+n )T，故有故有 X=XB+XN 最多有最多有 个基个基mnmC23 关于标准型解的若干基本概念：关于标准型解的若干基本

18、概念：可行解可行解与与非可行解非可行解 满足约束条件和非负条件的解满足约束条件和非负条件的解 X 称为称为可行解可行解，满足，满足约束条件但不满足非负条件的解约束条件但不满足非负条件的解 X 称为称为非可行解非可行解 基础解基础解 令令非基变量非基变量 XN=0，求得，求得基变量基变量 XB的值称为的值称为基础解基础解 即即 XB=B 1 b XB 是是基础解基础解的的必要条件必要条件为为XB 的非零分量个数的非零分量个数 m 基础可行解基础可行解 基础解基础解 XB 的非零分量都的非零分量都 0 时，称为时，称为基础可行解基础可行解，否则为否则为基础非可行解基础非可行解 基础可行解基础可行解

19、的非零分量个数的非零分量个数 0,则未达到最优则未达到最优(5)(4)3()()()(2)(1)(1jjmiijijNN1BN1BNN1BNNNN1BNNBBNNBBNNzcaczXABCCbBCXAbBCXCxfXAbBXXAbBXbBXXAXCXCxf检验数检验数机会成本机会成本30 1.2.4 标准型的单纯型算法标准型的单纯型算法1 找初始基础可行基找初始基础可行基 对于对于(max,)，松弛变量对应的列构成一个单位阵，松弛变量对应的列构成一个单位阵 若有若有 bi 0 中找最大者，选中者称为中找最大者，选中者称为入变量入变量，xj*第第j*列称为列称为主列主列4 确定确定入变量入变量的

20、最大值和的最大值和出变量出变量 最小比例原则最小比例原则(1.2.4)0min*ijijiiaab 31 1.2.4 标准型的单纯型算法标准型的单纯型算法4 确定确定入变量入变量的最大值和的最大值和出变量出变量 设第设第 i*行使行使 最小，则第最小，则第 i*行对应的基变量称为行对应的基变量称为出变量出变量，第，第 i*行称为行称为主行主行5 迭代过程迭代过程 主行主行 i*行与行与主列主列 j*相交的元素相交的元素ai*j*称为称为主元主元，迭代，迭代以以主元主元为中心进行为中心进行 迭代的实质是线性变换，即要将迭代的实质是线性变换，即要将主元主元 ai*j*变为变为1，主主列列上其它元素

21、变为上其它元素变为0，变换步骤如下：，变换步骤如下：(1)变换主行变换主行nmjaaajijiji,2,1*32 1.2.4 标准型的单纯型算法标准型的单纯型算法5 迭代过程迭代过程(2)变换主列变换主列除除主元主元保留为保留为1，其余都置，其余都置0(3)变换非主行、主列元素变换非主行、主列元素 aij(包括包括 bi)四角算法公式四角算法公式：数数据据表表示示当当前前单单纯纯型型表表中中的的的的数数据据表表示示上上一一个个单单纯纯型型表表中中 ,(1.2.5b)(1.2.5a)*ijijijiijjiijijjiijiiiaabaaaaaaabbb33 1.2.4 标准型的单纯型算法标准型

22、的单纯型算法5、迭代过程、迭代过程(4)变换变换CB，XB(5)计算目标函数、机会成本计算目标函数、机会成本 zj 和检验数和检验数 cj zj 6、返回步骤、返回步骤 2aijai*jaij*ai*j*主主行行主主列列主主元元四四角角算算法法图图示示34 表表1.2.4 例例1.2.2 单纯型表的迭代过程单纯型表的迭代过程x1x2x3x4x5序序号号CBXBb40452400bi/aij*0 x41002(3)110(33.3)0 x51203320140 OBJ=000000I初初始始解解cj-zj4045240045x2100/3 2/311/31/30500 x520(1)01 11(

23、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=170035 单纯型表中元素的几点说明单纯型表中元素的几点说明 任何时候，基变量对应的列都构成一个单位矩阵任何时候，基变量对应的列都构成一个单位矩阵 当前表中的当前表中的 b 列表示当前基变量的解值，通过变换列表示当前基变量的解值，通过变换 B 1 b 得到得到(资源已变成产品资源已变成产品)当前非基变量对应的向量可通

24、过变换当前非基变量对应的向量可通过变换 B 1 AN 得到，得到，表示第表示第 j 个变量对第个变量对第 i 行对应的基变量的消耗率行对应的基变量的消耗率 非基变量的机会成本由非基变量的机会成本由 给出给出 注意基变量所对应的行注意基变量所对应的行x1x2x3x4x5序序号号CBXBb40452400bi/aij*45x2100/3 2/311/31/30500 x520(1)01 11(20)OBJ=1500304515150IIcj-zj1009 150ijamiijijacz1 361.3 人工变量的引入及其解法人工变量的引入及其解法 1.3.1 当约束条件为当约束条件为“”型，引入剩余

25、变量和人工变型，引入剩余变量和人工变量量 由于所添加的剩余变量的技术系数为由于所添加的剩余变量的技术系数为 1，不能作为初，不能作为初始可行基变量，为此引入一个人为的变量（注意，此始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为时约束条件已为“=”型），以便取得初始基变量，故型），以便取得初始基变量，故称为人工变量称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解系数应具有惩罚性，称为罚系数

26、。罚系数的取值视解法而定法而定 两种方法两种方法 大大M法法 二阶段法二阶段法37 1.3.2 大大M法的求解过程法的求解过程 例例1.3.10,46 2.7810)(min32132121321xxxxxxxxtsxxxxf0,4 6 2.)7810max()(max654321532164216321xxxxxxxxxxxxxxtsMxxxxxf38 表表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

27、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 626 2III最最优优解解cj zj00 1 2 6 M+2答：最优解为答：最优解为 x1=2,x2=2,x3=0,OBJ=3639 大大M法的一些说明法的一些说明大大M法实质上与原单纯型法一样，法实质上与原单纯型法一样，M 可看成一个很可看成一个很大的常数大的常数 人工变量被迭代出去后一般就

28、不会再成为基变量人工变量被迭代出去后一般就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题量，说明原线性规划问题无可行解无可行解大大M法手算很不方便法手算很不方便因此提出了二阶段法因此提出了二阶段法 计算机中常用大计算机中常用大M法法 二阶段法手算可能容易二阶段法手算可能容易40 1.3.3 二阶段法的求解过程二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去，从而第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解

29、为初始解，第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原若第一阶段结束时，人工变量仍在基变量中，则原问题无解问题无解 为了简化计算，在第一阶段重新定义价值系数如下：为了简化计算，在第一阶段重新定义价值系数如下：不不是是人人工工变变量量时时当当为为人人工工变变量量时时当当时时目目标标函函数数为为不不是是人人工工变变量量时时当当为为人人工工变变量量时时当当时时目目标标函函数数为为jjjjjjjjxcxcxcxc01max01min41 表表1.3.2 用二阶段法求解例用二阶段法求解例1.3.1的第一阶段的第一阶段x1x

30、2x3x4x5x6序序号号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 142 表表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

31、 1 11 8x220121 2 36 10 8 626IIcj zj00 1 2 6最优解对应的最优解对应的B1在哪？在哪？431.5 单纯型法的一些具体问题单纯型法的一些具体问题1.5.1 关于无界解问题关于无界解问题 可行区域不闭合可行区域不闭合(约束条件有问题约束条件有问题)单纯型表中入变量单纯型表中入变量 xj*对应的列中所有对应的列中所有0a*ij0,501002.)(max1.5.1 21212121xxxxxxtsxxxf例例f(x)=x1+x2x1x2505050100 x1-x2=50-2x1+x2=10044 表表1.5.1 例例1.5.1 的单纯型表及其迭代过程的单纯型

32、表及其迭代过程x1x2x3x4序号CBXBb1100bi/aij*0 x310021100 x450(1)101(50)OBJ=00000I初始解cj-zj11000 x32001121x1501101 OBJ=50101IIcj-zj020 45 1.5.2 关于退化问题关于退化问题 退化问题的原因很复杂，当原问题存在平衡约束时退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环，克服死循环的退化的严重性在于可能导致死循环，克服死循环的方法有方法有“字典序字典序”法法0,060240

33、.43)(max1.5.2 2121212121xxxxxxxxtsxxxf例例x1x2x3x4序号CBXBb3400bi/aij*0 x340(2)10(20)0 x460001(20)3x10100 OBJ=03300IIcj-zj07004x22011/200 x4003/213x12011/20 OBJ=14033.50IIIcj-zj003.546 1.5.3 关于多重解问题关于多重解问题 多个基础可行解都是最优解，这些解在同一个超平多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行面上，且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为最优

34、单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=10,12023310032.254540)(max 1.5.3 321321321321xxxxxxxxxtsxxxxf多重最优解多重最优解例例47 表表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

35、/3 40 x12010(1)11(20)OBJ=1700404525510III最最优优解解cj-zj000 5 1045x226.67 1/3102/3 1/325x320101 11 OBJ=1700404525510IV最最优优解解cj-zj000 5 1048 1.5.4 关于无可行解问题关于无可行解问题 约束条件互相矛盾，无可行域约束条件互相矛盾，无可行域 单纯型表达到最优解检验条件时，人工变量仍在基单纯型表达到最优解检验条件时，人工变量仍在基变量中变量中0,1212.2)(max1.5.4 321321321321321xxxxxxxxxxxxtsxxxxf例例49 表表1.5.

36、4 例例1.5.4 第一阶段的单纯型表第一阶段的单纯型表x1x2x3x4x5x6x7x8x9序序号号CBXBb000000 1 1 1 bi/aij*1x7111(2)100100(1/2)1x821 1 10 10010 1x91 11100 10011 OBJ=4 1 1 2111 1 1 1I初初始始解解cj-zj112 1 1 1000 x31/2 1/2 1/21-1/2 001/200 1x85/2 3/2-1/2 -1/2 101/210 1x91/2-3/2 1/201/20 1-1/2 01 OBJ=3 0110 1 1IIcj-zj000 1 1 100501.4 修正单纯

37、型法修正单纯型法 原单纯型法迭代所需存储量大原单纯型法迭代所需存储量大 原单纯型法有不必要的计算量原单纯型法有不必要的计算量 1.4.1 修正单纯型的原理修正单纯型的原理jjBjNBNNBBNNNNNBNBNNBPPCzACAABCBCXACbXABCCbBCxfXAbBX )()()()(11111机机会会成成本本分分量量机机会会成成本本单单纯纯型型因因子子51 1.4.1 修正单纯型的原理修正单纯型的原理 关键是求新基的逆矩阵关键是求新基的逆矩阵 B 1 仍然可以采用四角算法仍然可以采用四角算法 混合算法混合算法 当前基的逆矩阵当前基的逆矩阵 B1 在原单纯型表的什么位置上？在原单纯型表的什么位置上？在初始可行基向量位置上在初始可行基向量位置上 (AN|I)(I|AN 1)0)()()(min 1111ij*ij*iij*jjjjPBPBbBPBPczc最小比例原则最小比例原则主列向量主列向量检验数分量检验数分量