线性规划及单纯形法含绪论课件.ppt

1、线性规划及单纯形法含绪论|“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。大英百科全书|运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”中国大百科全书|运筹学“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力”辞海|运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统

2、筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。中国企业管理百科全书|运筹学所研究的，通常是在必须分配稀缺资源的条件下，科学地决定如何最佳地设计和运营人机系统|对象：人机系统|条件：资源稀缺|方法：模型化，定量化|特点：最优化|目的：决策支持|起源古代战争、娱乐、建设|田忌赛马|丁渭修皇宫|学科产生第二次世界大战|问题合理利用稀缺战争资源保护自己、消灭敌人|1938年7月，波得塞雷达站的负责人罗伊用Operational Research命名防空作战系统运行的研究|1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组|l 942年美国和加拿大也都相继

3、成立运筹学小组z反潜艇战z库普曼(Koopmans)搜索论z肖克莱(Shockley)z对策论z商船编队和舰队护航z扩展战后用于民用事业z成型各个分支成熟z成熟计算机、信息技术结合z发展学科结合、渗透 应用广度和深度、方法和算法的完善特点系统的整体观念多学科的综合模型方法的应用符号语言、便于交流事前分析、减少失误抽象反映实际、突出共性优点：确定目标，明确约束 抓主要矛盾、舍次要矛盾 选择模型、设定变量 描述约束和目标、确定参数 选择求解方法、求解问题 灵敏度分析、评价 汇总、解释结果、报告 提出问题建立模型求解、优化测试、控制方案实施|规划理论规划理论 线性规划线性规划 非线性规划非线性规划

4、运输问题运输问题 整数规划整数规划 动态规划动态规划 目标规划目标规划|图论与网络理论图论与网络理论|排队论排队论|存储论存储论|决策论决策论|对策论对策论|冲突分析|可靠性理论|计划协调技术|图解协调技术已知各月份所需仓库面积列于表12。非基变量：其余变量即xl出基，目标改善k，换基过程没有有限最优解的判断；理由为：若将28%的分理处1同72%分理处3组合，其各项产出不低于分理处2的各项产出，但其投入只有分理处2的96.线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点发展学科结合、渗透 应用广度和深度、方法和算法的完善z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为

5、目标函数。线性规划的可行域是凸集；xjmin：minimize，“最小化”仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表13。问该厂每月生产这三种牌号糖果各多少kg，才能使其获利最大。抽象反映实际、突出共性此时，进一步分析引入x1或x3是否会更好？引入哪一个更好？对约束条件加以图解，找出可行域。v线性规划问题及数学模型v图解法v单纯形法原理v单纯形法计算步骤v单纯形法进一步讨论v数据包络分析v其他应用例子|问题的提出|线性规划问题的数学模型|线性规划概念和模型 例例1 美佳公司计划制造美佳公司计划制造、两种两种家电产品。已知各制造一件时分家电产品。已知各制造一件时分别占用的设备别占

6、用的设备A，B的台时、调试的台时、调试工序时间及每天可用于这两种家工序时间及每天可用于这两种家电的能力、各售出一件时的获利电的能力、各售出一件时的获利情况，如表情况，如表11所示。问该公司应所示。问该公司应制造两种家电各多少件，使获取制造两种家电各多少件，使获取的利润为最大。的利润为最大。表表11例1中先用变量x1和x2分别表示美佳公司制造家电和的数量。这时该公司可获取的利润为(2x1+x2)元，令z=2x1+x2，因问题中要求获取的利润为最大，即max z。z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制

7、条件的数学表达式称为约束条件。由此例1的数学模型可表为(1.1c)0,52426155.2max212121221xxxxxxxt sxxz目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”，s.t.subject to的缩写，“受限制于”线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。描述约束和目标、确定参数线性规划问题及数学模型如何判断没有有限最优解？b计算增加单位x1所创增的净经济价值基本可行解X(1)=(0,9/4,0,3/4,0),n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。第

8、一章线性规划及单纯形法基本可行解的非零分量均为正分量，以第一阶段最优基作为初始基本可行解,继续迭代.可行基对应于基可行解的基若有不止一个最小比值时，只能选取其中之一行对应的基变量出基；基本解（0，0，0，3，9）也是可行的抓主要矛盾、舍次要矛盾运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。首先考虑引入x1，由于1 目标标准化令 非基变量XN=0 得BXB=b例例2 捷运公司在下一年度的捷运公司在下一年度的14月的月的4个个月内拟租用仓库堆放物资。已知各月月内拟租用仓库堆放物资。已知各月份所需仓库面积列于

9、表份所需仓库面积列于表12。仓库租借。仓库租借费用随合同期而定，期限越长，折扣费用随合同期而定，期限越长，折扣越大，具体数字见表越大，具体数字见表13。租借仓库的。租借仓库的合同每月初都可办理，每份合同具体合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最最优决策，

10、目的是使所付租借费用最小。小。表1-2单位：100m2表1-3单位：元/100m2ijmin a0(i=1,.,m;j=1,.,n)112131411222321323141112131412131421222313142223313214233241z=2 800(x+x+x+x)+4 500(x+x+x)+6 000(x+x)+7 300 xx+x+x+x15x+x+x+x+x+x10 x+x+x+x+x+x20 x+x+x+x12例2中若用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，

11、x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：目标函数约束条件 s.t.min：minimize，“最小化”定义定义 对于求取一组变量对于求取一组变量xj(j=1,2,.,n)，使之既满足线性，使之既满足线性约束条件，又使具有线性的目标约束条件，又使具有线性的目标函数取得极值的一类最优化问题函数取得极值的一类最优化问题称为线性规划问题。称为线性规划问题。max（或min）nnxcxcxcZ2211自由,00,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats一般形式m

12、ax（或min）自由,00,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxatsnnxcxcxcZ2211目标函数约束条件非负约束称为决策变量),2,1(njxj称为价值系数或目标函数系数),2,1(njcj称为资源常数或约束右端常数),2,1(mibi称为技术系数或约束系数 ija0(i=1,.,m;j=1,.,n)紧缩形式max（或min）njjjxcZ1）（njxmibxatsxcjnjijijnjjj,2,10),.,1(),(.zmax 11矩阵形式max（或min）称为决策变量向量 称为价值系数向

13、量或目标函数系数向量 称为资源常数向量或约束右端常数向量 称为技术系数或约束系数矩阵 CXZ0XbAXts),(.nxxxX21),(21ncccCmnmmnnaaaaaaaaaA212222111211mbbbb21标准型的主要特征 目标最大；约束等式；变量非负；右端非负。nnxcxcxcZ2211max0,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxat s标准型的紧缩形式njjjxcZ1maxnjxmibxatsjnjijij,2,10,2,1.1标准型的矩阵形式：CXZ max0.XbAXts选择模型、设定变量X=X

14、（1）+（1）X（2）（01）b为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。5单纯形法进一步讨论凸集及其顶点成熟计算机、信息技术结合例2中若用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。可行基对应于基可行解的基此时，为x4退出变量。此时，进一步分析引入x1或x3是否会更好？引入哪一个更好？5单纯形法进一步讨论把一般的LP化成标准型的过程称为线性规划问题的标准化z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。可行基对应于基可行解的基该公司希望总的租借费用为最小，故有如下数学模型：

15、则称X为K的一个顶点（也称为极点或角点）。X(2)=(1,2,0,0,0)理由为：若将28%的分理处1同72%分理处3组合，其各项产出不低于分理处2的各项产出，但其投入只有分理处2的96.运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”中国大百科全书z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。标准型的向量形式njjjxcZ1maxnjxbxptsjnjjj,2,10.1其中：mjjjjaaap21把一般的LP化成标准型的过程称为线性规划

16、问题的标准化 方法 1 目标标准化 min Z 等价于 max(Z)max Z=cjxj 2 化约束为等式 加松弛变量、减剩余变量 3 变量非负化 做变换 或 4 右端非负jjxxjjjxxx 0 jx0jx标准化举例（例3）32132minxxxZ123346max223300Zxxxxxx 取值无约束321321321321,0,063-24423-92-.xxxxxxxxxxxxts123341233512331233462293224.42336,0 xxxxxxxxxxstxxxxxxx xxxv线性规划问题及数学模型v图解法v单纯形法原理v单纯形法计算步骤v单纯形法进一步讨论v数据

17、包络分析v其他应用例子1什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。2.2.图解法图解法(例例1)1)运用图解法，以求出运用图解法，以求出生产计划生产计划（）。(1.1c)0,52426155.2max212121221xxxxxxxt sxxz(1.1a)(1.1b)(1.1d)由于线性规划模型中只有两个决策由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就变量，因此只需建立平面直角坐标系就可以进行图解了。可以进行图解了。建立平

18、面直角坐标系，标出建立平面直角坐标系，标出,和和。对约束条件加以图解，找出可行域。对约束条件加以图解，找出可行域。画出目标函数等值线。画出目标函数等值线。4.结合目标函数的要求求出最优解。结合目标函数的要求求出最优解。(1.1c)0,52426155.2max212121221xxxxxxxt sxxz(1.1a)(1.1b)(1.1d)(a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界 唯一最优解唯一最优解多个最优解多个最优解 唯一最优解唯一最优解 (d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目

19、标函数无界目标函数无界 无可行解无可行解v线性规划问题及数学模型v图解法v单纯形法原理v单纯形法计算步骤v单纯形法进一步讨论v数据包络分析v其他应用例子|线性规划问题的解的概念|凸集及其顶点|几个基本定理可行解 变量满足所有约束条件的一组值可行解集 所有可行解构成的集合可行域 可行解集构成n维空间的区域 0 xbAX0 xb,Ax|xD）（njxmibxatsxcjnjijijnjjj,2,10),.,1(.zmax 11线性规划问题最优解 使得目标函数达到最优的可行解最优值 最优解对应的目标函数值目的 求最优解和最优值求解方法 单纯形法CXZ max0.XbAXts先研究AX=b设 系数矩阵

20、A是mn矩阵，秩为m，B是A中mm阶非奇异子矩阵（即|B|0），则称B是线性规划问题的一个基基。B 是由m个线性独立的列向量组成),(21mrrrpppB),2,1(mjxrj基向量 基变量非基变量：其余变量AX=BXB+NXN=b令令 非基变量非基变量XN=0 得得BXB=b和特解和特解XB=B1b 结合结合XN=0 称为对应于称为对应于B的基本解；的基本解；基本解个数基本解个数=基的个数基的个数Cnm基可行解基可行解 可行的基本解可行的基本解 XB0 XN=0 可行基对应于基可行解的基可行基对应于基可行解的基NBTnXXxxxX),(21A=（B|N）最优基 对应的基本可行解也是最优基本可

21、行解个数基的个数Cnm基本可行解的非零分量均为正分量，其正分量个数 m。退化的基本可行解 基本可行解的非零分量个数小于m时，也就是在基本可行解中一个或多于一个的基变量取零值时1、基本概念、基本概念 凸集凸集设设K是是n维欧氏空间维欧氏空间的一个点集，若任意两点的一个点集，若任意两点X（1）K，X（2）K的连线上的一的连线上的一切点切点 X（1）+（1）X（2）K （00,此时非基变量检验数均为负，解最优基本可行解个数基的个数Cnm最优值 Z=17/2.z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提

22、供决策目标和数量分析的工具”。线性规划问题的可行解x(x1,x2,xn)为基可行解的充要条件是x的正分量所对应的系数列向量是线性独立的。x5=2 人工变量不为零,表示原问题无可行解此时1=028,3=0.xjb对于分理处2，有E=0.抓主要矛盾、舍次要矛盾不是xjb猜想1 线性规划的可行域是凸集；猜想2 最优解若存在，则可以在可行域的顶点上得到；猜想3 可行域的顶点的个数是有限的；猜想4 若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个 猜想5 对于标准型的线性规划X是可行域顶点的充分必要条件是X是基本可行解。求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标

23、得到改善的基本可行解 是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？v线性规划问题及数学模型v图解法v单纯形法原理v单纯形法计算步骤v单纯形法进一步讨论v数据包络分析v其他应用例子|单纯形方法引例|单纯形法的一般描述|表格单纯形法|一般问题的处理|单纯形法矩阵描述|几点注意事项用单纯形法的思想求解线性规划问题321332maxxxxZ0,9743321321321)()(xxxxxxxxx材料约束工时约束5432100332maxxxxxxZ097435153214321xxxxxxxxxx931074101111bA54321xxxxxx)0,0,3,3,2(C例

24、5432100332maxxxxxxZ097435153214321xxxxxxxxxx931074101111bA54321xxxxxx)0,0,3,3,2(C014p105p基本解（0，0，0，3，9）也是可行的 9,354xx321,xxx例5432100332maxxxxxxZ097435153214321xxxxxxxxxx初始基本可行解X(0)=（0，0，0，3，9）含义：不生产任何产品，工时剩余为3，材料剩余为9，利润为 Z(0)=0 初始基本可行解是否最优解?是否可以生产某种产品使目标提高？当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位 例5432100332

25、maxxxxxxZ097435153214321xxxxxxxxxx初始基本可行解X(0)=（0，0，0，3，9）当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位考虑将x1（或x2,x3）并为非零变量，x2,x3价值系数加大，将x2变为基变量引入变量。例5432100332maxxxxxxZ097435153214321xxxxxxxxxx初始基本可行解X(0)=（0，0，0，3，9）当x2作为引入变量，为使新解X(1)仍为基可行解，必须使049030002524321xxxxxxx且使x4或x5中有一个等于零退出变量（1-1）例5432100332maxxxxxxZ09743

26、5153214321xxxxxxxxxx由(1-1)第四、第五式，得49322xx为使新解X(1)为基可行解4949,3min2x此时，变为零，x5为退出变量新的基可行解为X(1)=(0,9/4,0,3/4,0)目标函数值Z(1)=27/4 Z(0)例5432100332maxxxxxxZ04941474434343515321431xxxxxxxxx系数列向量410471410143043,54321AAAAA此时，进一步分析引入x1或x3是否会更好？引入哪一个更好？首先考虑引入x1，由于计算增加单位x1所创增的净经济价值410471410143043,54321AAAAA2414143AA

27、A453410432111zc同理，可计算增加单位x3所创增的净经济价值493470433333zc检验数例基本可行解X(1)=(0,9/4,0,3/4,0)取x1进基，同样，5432100332maxxxxxxZ04941474434343515321431xxxxxxxxx14149,4343min1x此时，为x4退出变量。新的基可行解为X(2)=(1,2,0,0,0)目标函数Z(2)=2+6=8 27/4=Z(0)此时非基变量检验数均为负，解最优求解结果为E=1，说明分理处1的运行为DEA有效。选择求解方法、求解问题称为技术系数或约束系数可行基对应于基可行解的基(d)可行域无界 (e)可

28、行域无界 (f)可行域为空集肖克莱(Shockley)处理方法二 两阶段法令 非基变量XN=0 得BXB=b目标函数Z(2)=2+6=8 27/4=Z(0)如何判断没有有限最优解？如何判断没有有限最优解？选择模型、设定变量主元变换（枢变换或旋转变换）(Data Envelopment Analysis,DEA),线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位结合XN=0若不存在,则Z，没有有限最优解。z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。当x2作为引入变量，为使新解X(1)仍为基可行

29、解，必须使称为技术系数或约束系数矩阵1.初始基本可行解的确定（观察法）；njjjxcZ1maxnjxbpxtsjnjjj,2,10.1mnnjjnjjjxxcZ110max0,.212211222222121111212111mnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxats1.初始基本可行解的确定（观察法）；mnnjjnjjjxxcZ110max0,.212211222222121111212111mnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxats100010001),(21mnnnpppB),0,0,0(21m

30、bbbX基基本可行解2.从约束中解出基变量；mixabxnjjijiin,2,11mnnjjnjjjxxcZ110max0,.212211222222121111212111mnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxats3.代入目标消去基变量，得到非基变量xj的检验数 j；miininnjjjxcxcZ1111,2,nn iiijjjxba ximnjjijimiinnjjjxabcxcZ1111111mnmnn iijjn iijjijijcbc xca x111()mnmn iijn iijjijicbccax3.代入目标消去基变量，得到非基变量

31、xj的检验数 j；111nmnjjn iiijjjijZc xcba x1111mnmnn iijjn iijjijijcbc xca x111()mnmn iijn iijjijicbccaxnjjjjxzcZZ10)(miiinbcZ101mjn iijizcajjjzc njjjxZZ104.判断最优；最优性判别定理若是对应于B的基本可行解，j是用非基变量表示目标函数的表达式 中非基变量xj的检验数，若对于一 切非基变量的角指数j均有j 0 则当前基本可行解为最优解。010ZxZZnjjj对于任意可行解X，对于基本可行解X0，0ZZ 012X(0,0,0,)mb bb5.没有有限最优解的

32、判断；无最优解判别定理若是对应于B的基本可行解，非基变量x k的检验数k 0,且对于i=1,2,m 均有aik 0,则问题没有有限最优解。),0,0,0(21)0(mbbbXmixabxnjjijiin,2,11mixabxkikiin,2,1kkxZZ06.改进目标 若k 0，则选xk进基;用最小比值法确定xk的最大值，使基变量xl取0值，其它基变量非负；lklikikiabaab0minmixabxkikiin,2,10即xl出基，目标改善k，换基过程若不存在,则Z，没有有限最优解。7.主元变换（枢变换或旋转变换）xk进基，xl出基，解出新的基变量mmnmkmmiinikiinkbaaaa

33、baaaabaaaa1001.000121211111211ljlkikijijlkljljaaaaaaaa标准型mnmnnnnnxcxcxcxcxcZ112211max0,.1212211222222121111212111mnnnmmnnmnmmnnnnnnxxxxxbxxaxaxabxxaxaxabxxaxaxats0.1122112211222222121111212111mnmnnnnnmmnnmnmmnnnnnnxcxcxcxcxcZbxxaxaxabxxaxaxabxxaxaxats标准型mnmnnnnnxcxcxcxcxcZ112211max0,.121221122222212

34、1111212111mnnnmmnnmnmmnnnnnnxxxxxbxxaxaxabxxaxaxabxxaxaxatsbxxxxxxZmnnnn212101100001000010212121222221111211nmnnnmmnmmnnccccccbaaabaaabaaa考虑将x1（或x2,x3）并为非零变量，x2,x3价值系数加大，将x2变为基变量引入变量。对约束条件加以图解，找出可行域。5单纯形法进一步讨论可行基对应于基可行解的基且使x4或x5中有一个等于零退出变量求使目标得到改善的基本可行解产出单位：处理笔数/月x5=2 人工变量不为零,表示原问题无可行解线性规划问题的数学模型可行解

35、集构成n维空间的区域基本可行解的非零分量均为正分量，最优值 Z=17/2.b把一般的LP化成标准型的过程称为线性规划问题的标准化基本解个数=基的个数Cnm中国企业管理百科全书bz是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。基本可行解个数基的个数CnmbxxxxxxZmnnnn212101100001000010212121222221111211nmnnnmmnmmnnccccccbaaabaaabaaa022112122222111121121210001100001000010ZZcZcZcbaaabaaabaaabxxxxxxZnnmnmmmnnmnnnnmii

36、inbcZ10njacZmiijinj,.2,11miiinbcZ10njacZmiijinj,.2,11基变量检验数最小比值列 基变量系数右端常数 CB 基 cj21000 b x1x2x3x4x50 x315051000 x424620100 x5511001cj-zj210005432100012maxxxxxxZ2312412523455156224s.t.5,0 xxxxxxxxx x x x x12212122max25156224s.t.5,0Zxxxxxxxx x解：表1-701/602/614x120-1/301/30cj-zj1-1/604/601x500015015x30

37、 x5x4x3x2x1b 00012 cj 基 CB表1-8-1/21/40017/2x12-1/2-1/4000cj-zj3/2-1/40103/2x21-15/25/410015/2x30 x5x4x3x2x1 b 00012 cj 基CB表1-9表19中所有j=0,且基变量中不含人工变量，最优解 X=(7/2,3/2,15/2,0,0);最优值 Z=17/2.练习1：求解线性规划2152maxxxZ0,02224.21212121xxxxxxxxts2152maxxxZ0,2224.54321521421321xxxxxxxxxxxxxxts CB XB cj25000 xj b x1x

38、2x3x4x50 x34111004/10 x42-1201010 x521-1001-cj-zj25向右迭代一步 CB XB cj25000 xj b x1x2x3x4x50 x333/201-1/2025x21-1/2101/20-0 x531/2001/216cj-zj59/200-5/202x12102/3-1/305x22011/31/300 x5201-1/32/31cj-zj1400-3-10练习2：求解线性规划0,302.432141321xxxxxxxxxts CB XB cj1200 xj b x1x2x3x40 x301-2100 x43100112212maxxxZ0,

39、0302.21121xxxxxts212maxxxZ没有有限最优解 求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解 是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？nnxcxcxcZ2211max0,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxat s0,0.112211222222121111212111mnnnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxatsmnnnnnMxMxMxxcxcxcZ212211ma

40、x处理方法一处理方法一 大法大法人造基 添加人工变量造成基 去掉人工变量人工变量0,0.112211222222121111212111mnnnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxatsmnnnnnMxMxMxxcxcxcZ212211max),()0()0(2)0(1)0(nxxxX)0,0,()0()0(2)0(1)1(nxxxX原问题的可行解新问题的可行解目标值)0()0(110,nnxcxcZ结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解例6 大M法313axxxZm0,93124s.t.321

41、32321321xxxxxxxxxxx765431-003maxMxMxxxxxZ)7,.,1(0931-2-4.j732653214321jxxxxxxxxxxxxxts-M0-10 x500010 x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40 x7x4x3x2x1 b -M010-3 cjXB CB表1-100 x400001-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXB cj-30100-M-M b x1x2x3x4x5x6x7

42、0 x4330211-100 x21-21-10-110-Mx7660403-31cj-zj6M-30 4M+103M-4M00 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-9/2000-3/4-M+3/4-M-1/4最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2 CB XB cj1200-M b x1x2x3x4x50 x4111010-Mx54-12-101cj-zj-4M-M2M+2-M00大M法举例54321002maxMxxxxxZ0,142543214215321x

43、xxxxxxxxxxx212maxxxZ0,0142.212121xxxxxxts CB XB cj1200-M b x1x2x3x4x52x2111010-Mx52-30-1-21cj-zj2-2M-1-3M0-M-2-2M0所有检验数0 已经是最优解x5=2 人工变量不为零,表示原问题无可行解参照图解法结果nnxcxcxcZ2211max0,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats0,0.112211222222121111212111mnnnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxa

44、bxxaxaxatsmnnnxxxZ21max处理方法二处理方法二 两阶段法两阶段法人造基添加人工变量造成基去掉人工变量人工变量 如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。0,0.112211222222121111212111mnnnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxatsmnnnxxxZ21max第一阶段第一阶段第一阶段最优解中:如果Z0,则原问题没有基

45、本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本可行解.第二阶段第二阶段以第一阶段最优基作为初始基本可行解,继续迭代.nnxcxcxcZ2211max0,0.112211222222121111212111mnnnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxatsmnnnxxxZ21max第一阶段第一阶段例 6 两阶段法313axxxZm123123231234-2+1s.t.39,0 xxxxxxxxxxx第一阶段：67minwxx123412356237421.390(1,.,7)jx

46、xxxxxxxxs txxxxj-10-10 x500010 x6-100-11-21x6-10004-2cj-zj1013-19x7-1011114x40 x7x4x3x2x1 b -10000 cj XB CB表1-11请注意:第一阶段的最优解不是唯一的33-11x50-4-31-1x6-100-11-21x2000406cj-zj104066x7-1012033x40 x7x4x3x2x1 b -10000 cj XB CB表1-1101/20-1/2x50-1-1/201/2x6-11/301/3103x20-10000cj-zj1/602/3011x10-1/210000 x40 x

47、7x4x3x2x1 b -10000 cj XB CB3/20300cj-zj1/20-1/2x5001/3103x2002/3011x1-312000 x40 x4x3x2x1 b 010-3 cj XB CB表1-1212345max3000zxxxxx 第二阶段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/2cj-zj0103/23/2x3110000 x40 x4x3x2x1 b 0000 cj XB CBCXZ max0.XbAXts)(),(2121222211211NBpppaaaaaaaaaAnmnmmnnNBTnXXxxxX),(21)(NBCCC

48、bNXBXXXNBAXNBNB)(NNBNXBbBNXbBX111)(CXZ max0.XbAXtsNNBNXBbBNXbBX111)(NNBBNBNBXCXCXXCCCXZ)(NBNBNNNBXNBCCbBCXCNXBbBC)()(1111NBCCBNN1NNBXbBCZ1NNBNXBbBNXbBX111)(NNBBNBNBXCXCXXCCCXZ)(NBNBNNNBXNBCCbBCXCNXBbBC)()(1111NBCCBNN1NNBXbBCZ11BCB01BBBBBXBCXCXAcbZ)(|检验数的计算；|进基变量的选取；若有不止一个变量可以进基时,只取一个；|最小比值；若有不止一个最小比

49、值时，只能选取其中之一行对应的基变量出基；|没有有限最优解的情况；|最优解是否唯一 ；最优表中非基变量检验数等于零时,可能最优解不唯一。v线性规划问题及数学模型v图解法v单纯形法原理v单纯形法计算步骤v单纯形法进一步讨论v数据包络分析v其他应用例子|数据包络分析(Data Envelopment Analysis,DEA),根据多项投入指标和多项产出指标,利用线性规划的方法,对具有可比性的同类型单位进行相对有效性评价的一种数量分析方法。生产前沿面DEA有效97在DEA中通常称被衡量绩效的组织为决策单元（decision making unit,DMU)。snssrjnnmnmmijnnyyyy

50、yyyyyyxxxxxxxxxx.21222211121121222211121112m12s投入产出1 2 n决策单元数学模型njjjnjjijjnjrjrjjnjmiExixsryytsE111),.,1(0,1),.,1(),.,1(.min00当求解结果有E1时，则j0决策单元非DEA有效，否则j0决策单元DEA有效。例例8 振华银行的4个分理处的投入产出情况如表1-16所示。要求分别确定各分理处的运行是否DEA有效。150042090013520分理处4130045080012021分理处31000350100013020分理处21600200180014015分理处1中间业务贷款储