第一章-线性规划问题及单纯型解法.ppt

运筹学OperationalResearch,运筹帷幄，决胜千里史记张良传,2,目录,绪论第一章线性规划问题及单纯型解法第二章线性规划的对偶理论及其应用第三章运输问题数学模型及其解法第四章整数规划第五章动态规划第六章图与网路分析第七章随机服务理论概论第八章生灭服务系统第九章特殊随机服务系统第十章存储理论,3,绪论,一、运筹学的起源与发展二、运筹学的特点及研究对象三、运筹学解决问题的方法步骤四、运筹学的发展趋势,4,一、运筹学的起源与发展,起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为OperationalResearch美国称为OperationsResearch战后在经济、管理和机关学校及科研单位继续研究1952年，Morse和Kimball出版运筹学方法1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会,5,二、运筹学的特点及研究对象,运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法Morse和Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience,6,二、运筹学的特点及研究对象,运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等图论与网路理论随机服务理论：排队论存储理论决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论金融工程,7,三、运筹学解决问题的方法步骤,明确问题建立模型设计算法整理数据求解模型评价结果,明确问题,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,满意？,Yes,No,No,8,四、运筹学的发展趋势,运筹学的危机脱离实际应用，陷入数学陷阱IT对运筹学的影响MIS,DSS,MRP-II,CIMS,ERPORDept.-Dept.OfOR&IS运筹学与行为科学结合群决策和谈判对策理论多层规划合理性分析服务行业中的应用金融服务业信息、电信服务业医院管理,9,四、运筹学的发展趋势,软计算面向强复杂系统的计算、实时控制、知识推理智能算法：模拟退火、遗传算法、人工神经网络、戒律算法等系统仿真面向问题后勤(Logistics)全球供应链管理电子商务：集成特性随机和模糊OR问题本身的不确定性人类知识的局限性,10,第一章线性规划问题及单纯型解法,1.1线性规划问题及其一般数学模型1.1.1线性规划问题举例例1、多产品生产问题（Max,）设x1,x2分别代表甲、乙两种电缆的生产量，,11,例2、配料问题（min,),设x1,x2分别代表每粒胶丸中甲、乙两种原料的用量,12,例3、合理下料问题设xj分别代表采用切割方案18的套数，,13,1.1.2线性规划数学模型的一般表示方式,14,1、和式,15,2、向量式,16,3、矩阵式,17,1.1.3线性规划的图解法,f(x)=36,18,线性规划问题的几个特点：,线性规划问题的可性解的集合是凸集线性规划问题的基础可行解一般都对应于凸集的极点凸集的极点的个数是有限的最优解只可能在凸集的极点上，而不可能发生在凸集的内部,19,1.2线性规划问题的单纯型解法1.2.1线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式,20,变换的方法：,目标函数为min型，价值系数一律反号。令f(x)=-f(x)=-CX,有minf(x)=-max-f(x)=-maxf(x)第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0若xj0，令xj=-xj，代入非标准型，则有xj0若xj不限，令xj=xj-xj，xj0，xj0，代入非标准型,21,变换举例：,22,关于标准型解的若干基本概念：,标准型有n+m个变量，m个约束行“基”的概念在标准型中，技术系数矩阵有n+m列，即A=(P1,P2,Pn+m)A中线性独立的m列，构成该标准型的一个基，即B=(P1,P2,Pm)，|B|0P1,P2,Pm称为基向量与基向量对应的变量称为基变量，记为XB=(x1,x2,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,xm+n)T，故有X=XB+XN最多有个基,23,关于标准型解的若干基本概念：,可行解与非可行解满足约束条件和非负条件的解X称为可行解，满足约束条件但不满足非负条件的解X称为非可行解基础解令非基变量XN=0，求得基变量XB的值称为基础解即XB=B1bXB是基础解的必要条件为XB的非零分量个数m基础可行解基础解XB的非零分量都0时，称为基础可行解，否则为基础非可行解基础可行解的非零分量个数0,则未达到最优,30,1.2.4标准型的单纯型算法,找初始基础可行基对于(max,)，松弛变量对应的列构成一个单位阵若有bi0中找最大者，选中者称为入变量，xj*第j*列称为主列确定入变量的最大值和出变量最小比例原则,31,1.2.4标准型的单纯型算法,确定入变量的最大值和出变量设第i*行使最小，则第i*行对应的基变量称为出变量，第i*行称为主行迭代过程主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行,32,1.2.4标准型的单纯型算法,迭代过程(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)四角算法公式：,33,1.2.4标准型的单纯型算法,5、迭代过程(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤2,34,表1.2.4例1.2.2单纯型表的迭代过程,答：最优解为x1=20,x2=20,x3=0,OBJ=1700,35,单纯型表中元素的几点说明,任何时候，基变量对应的列都构成一个单位矩阵当前表中的b列表示当前基变量的解值，通过变换B1b得到(资源已变成产品)当前非基变量对应的向量可通过变换B1AN得到，表示第j个变量对第i行对应的基变量的消耗率非基变量的机会成本由给出注意基变量所对应的行,36,1.3人工变量的引入及其解法1.3.1当约束条件为“”型，引入剩余变量和人工变量,由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定两种方法大M法二阶段法,37,1.3.2大M法的求解过程例1.3.1,38,表1.3.1例1.3.1的单纯型表迭代过程,答：最优解为x1=2,x2=2,x3=0,OBJ=36,39,大M法的一些说明,大M法实质上与原单纯型法一样，M可看成一个很大的常数人工变量被迭代出去后一般就不会再成为基变量当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解大M法手算很不方便因此提出了二阶段法计算机中常用大M法二阶段法手算可能容易,40,1.3.3二阶段法的求解过程,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解若第一阶段结束时，人工变量仍在基变量中，则原问题无解为了简化计算，在第一阶段重新定义价值系数如下：,41,表1.3.2用二阶段法求解例1.3.1的第一阶段,42,表1.3.2用二阶段法求解例1.3.1的第二阶段,最优解对应的B1在哪？,43,1.5单纯型法的一些具体问题,1.5.1关于无界解问题可行区域不闭合(约束条件有问题)单纯型表中入变量xj*对应的列中所有,44,表1.5.1例1.5.1的单纯型表及其迭代过程,45,1.5.2关于退化问题,退化问题的原因很复杂，当原问题存在平衡约束时当单纯型表中同时有多个基变量可选作出变量时退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法,46,1.5.3关于多重解问题,多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行最优单纯型表中有非基变量的检验数为0最优解的线性组合仍是最优解，即X=aX1+bX2，a+b=1,47,表1.5.3例1.5.3的单纯型表及其迭代过程,48,1.5.4关于无可行解问题,约束条件互相矛