系统工程与运筹学1-9章修改.ppt

系统工程与运筹学Systems Engineering and Operation Research,西北农林科技大学经济管理学院 淮建军 手机：,教学设计与课程要求,学时70，基本实现大纲的要求，突出学生的主体地位，培养学生自学与演讲能力，实现研究型团队的组织学习；教学形式包括老师教授、学生讲座和作业讲解；考核方式：考勤10%，个人作业20%，考试70%。,主要参考书,梁军,赵勇.系统工程导论.化学工业出版社.2005.3陈宏民.系统工程导论.高等教育出版社.2006.4月汪应洛.系统工程(第四版).机械工业出版社.2008.8梁迪,董海.系统工程.机械工业出版社.2005.6王福林.农业系统工程.中国农业出版社.2006.12杨印生.经济系统定量分析方法.吉林科学技术出版社.2001.4董肇君.系统工程与运筹学(第二版).国防工业出版社.2007.5,第1章系统科学方法论与系统,1.1系统科学方法论1.2系统的概念和属性1.3系统的分类,案例1：都江堰水利工程,战国时期秦国李冰父子设计修建的都江堰水利工程，它包括“鱼嘴”岷江分水工程，“飞沙堰”分洪排沙工程，“宝瓶口”引水工程三大主体工程和120个附属渠堰工程，工程之间的联系处理得恰到好处，形成一个有机整体，兼有防洪、排沙、灌溉、漂木、行舟等多种功能，渠道上设置了水尺，根据测得的水位，多级分水，合理控制分水流量，使汹涌急流的岷江化害为利，灌溉了成都平原上14个县的几百万亩粮田。工程完工后，又建立了一套岁修养护制度，每年按规定淘沙修堤，因此，虽然该工程经历二千多年，至今仍发挥着效益，该工程堪称我国古代运用系统思想解决实际问题的典范。,1.1系统科学方法论,系统科学方法论的产生与发展古代方法论（整体论）：应用、基础、特征和局限近代科学方法论（还原论）：应用、基础、特征和局限现代系统科学方法论（整体论与还原论的有机结合）：应用、基础、特征和局限现代系统科学方法论的特征和基本原则特征：整体性、综合性、定量化、信息化和人机方式原则：整体论与还原论结合、定性和定量结合、局部和整体结合、分析和综合结合、确定性和不确定性结合,1.1系统科学方法论,系统思想极其形成系统思想的含义系统思为方法与传统思维方法的区别人类思维的一般模式第五项修炼,1.2系统的概念和属性,概念：系统是由相互联系、相互依赖、相互制约、相互作用的若干部分，是按照一定的方式，为了一定的目的组合而成的存在于特定环境之中并具有一定功能能的有机整体。属性：整体性、有序性、集合性、关联性、目的性和环境适应性运行模式分类,第2章系统科学与系统工程,2.1系统科学体系2.2系统工程2.3系统工程的基础理论和工具2.4系统工程方法论2.5系统工程的应用和发展,2.1 系统科学体系系统科学的体系结构,哲学,桥梁,基础科学,技术科学,工程技术,(社会实践),自然辩证法,物理学、化学、生物学等,建筑学、水力学,水利工程、土木工程,(社会实践),哲学,图1.1 自然科学的三个层次结构（三层次一桥梁结构模式）70s 贝塔朗菲纲领（贝塔朗菲，一般系统理论家）,哲学,（社会实践）80s 钱学森的系统科学体系（钱学森，1996）,2.1.2 系统理论,一般系统理论耗散结构学说协同说复杂适应系统理论开放复杂系统理论,2.2系统工程,定义与观点系统工程是一门新兴的工程技术学科，是应用科学。它不仅定性，而且定量的微系统的规划与设计、实验与研究、制造与使用、管理与决策提供科学方法的方法论科学，他的最终目的实时系统运行在最优状态基本观点：整体性、综合性、科学性、关联性、实践性,2.3系统工程的基础理论,运筹学控制论以计算机为基础的信息科学系统工程的的力工具计算机,2.4 系统工程方法论,霍耳三维结构三阶段法“调查学习”模式并行工程方法,第3章系统工程的主要方法,3.1模型化3.2系统分析与综合评价3.3层次分析法 3.4 模糊综合评价法,3.1模型化,模型与模型化系统模型的基本理论、方法与程序四种理论四种方法五步建模模型化的基本原则模型化的程序,3.2系统分析与综合评价,系统分析与综合评价概述系统综合评价方法技术路线指标权重的确定方法单项指标定量评价方法评价值的标准化综合评价,3.3层次分析法,层次分析法概述基本原理建立分层递阶结构模型构建判断矩阵单排序总排序例题,3.4 模糊综合评价法,模糊综合评审的基本原理模糊综合评审方法应用,层次分析法的应用举例,第4章系统工程常用预测方法和模型,4.1预测科学4.2定性预测技术4.3定量预测技术4.4带定性变量的线性回归预测模型4.5判别分析预测模型4.6时间序列预测4.7灰色预测GN（1，1模型）,4.1预测科学,在调研的基础上对事物的未来进行科学的分析，研究其发展变化的规律性叫预测分析。预测的原理有：整体性、可知性、可能性、相似性和反馈性预测的步骤：确定目标选择预测方法收集和分析数据建立预测模型分析模型利用模型预测分析预测结果,4.2定性预测技术:德尔菲法,德尔菲法：预测机构或人员预先选定与预测问题有关的专家10-15人，采用信件来往的方式与其联系，将他们的意见进行整理、综合、归纳后在匿名樊哙给各位专家再次征求意见，按这种方式多次反复，直到是专家们的意见趋于一致为止，最后得出预测结论。步骤：选择专家、编制和邮递“专家应答表”、分析整理“专家应答表”、与专家反复交换意见、将最终预测结论函告各位专家并致谢。,4.3定量预测技术,一元线性回归模型：用于分析一个自变量（X）与一个因变量（Y）之间线性关系的数学方程。分类：一类是反映因果关系的模型；一类是反映时间序列的模型。最小二乘法：,线性回归预测模型的检验过程及预测精度,相关系数检验：不相关、正相关、负相关显著性检验：T检验：检验回归方程中参数b的估计值在某一显著水平上是否为0；F检验：检验整个回归方程是否显著r检验：两个变量相关性的检验方差分析：估计预测精度（提高精度的方法）,线性回归的方法与步骤,整理占有的现有数据（xi,yi）求解预测方程进行检验利用模型预测,线性回归的理论假设,自变量x与应变量y之间存在线性关系；正态性：随机误差（即残差）e服从均值为 0，方差为的正态分布；等方差：对于所有的自变量x，残差e的条件方差为，且为常数；独立性：在给定自变量x的条件下，残差e的条件期望值为0（本假设又称零均值假设）；无自相关性：各随机误差项e互不相关；残差e与自变量x不相关：随机误差项e与相应的自变量x不相关；无共线性：自变量x之间相互独立,4.3.1 一元线性回归,1、应变量（dependent variable)2、自变量（independent variable）3、一元线性回归直线回归方程的模型是：yi=a+bxi+ei其中（）a是截距（）b是回归系数(regression coefficient)（回归直线的斜率）回归系数的统计学意义是：自变量每变化一个单位，应变量平均变化的单位数（）ei是残差因此直线回归方程的一般形式是：其中 是应变量y的预测值或称估计值。,基本概念,一元非线性回归模型,化一元非线性函数为线性函数（确定曲线类型是关键）化一般一元非线性函数为线性函数（应用泰勒级数展开，并用多元替代）,多元线性回归,多元线性回归是简单线性回归的直接推广，其包含一个因变量和二个或二个以上的自变量。简单线性回归是研究一个因变量（Y）和一个自变量（X）之间数量上相互依存的线性关系。而多元线性回归是研究一个因变量（Y）和多个自变量（Xi）之间数量上相互依存的线性关系。简单线性回归的大部分内容可用于多元回归，因其基本概念是一样的。,多元线性回归模型与参数估计,设有自变量x1,x2,xp和因变量Y以及一份由n个个体构成的随机样本(x1i,x2i,xpi,，Yi），且有如下关系：y=B0+B1x1+B2x2+Bp xp+(模型）B0、B1、B2和Bp为待估参数，为残差。由一组样本数据，可求出等估参数的估计值b0、b1、b2和bp,，得到如下回归方程：i=b0+b1x1+b2x2+bp xp 由此可见，建立回归方程的过程就是对回归模型中的参数（常数项和偏回归系数）进行估计的过程。,回归方程的建立,散点图奇异点（ouliers）最小二乘法（least square,LS）残差平方和（sum of squares for residuals）,一元线性回归时，计算比较简单：多元线性回归时，比较复杂，一般需要用计算机处理。,线性回归的检验,、回归方程的检验方差分析法：应变量的总变异可分解为回归平方和(regression sum of squares)：可用线性回归解释的部分,剩余平方和(residual sum of squares)：即残差平方和，不能用线性回归解释的部分以上三部分的自由度分别为n-1，m和n-m-1。其中，n为样本数，m为自变量数。方差分析的假设为一元线性回归：H0:=0 H1:0多元线性回归：H0:1=2=m=0H1:1，2，m中至少有一个不等于零因此方差分析的结论是线性回归方程是否显著，是否有意义。,、回归偏回归系数的检验 检验回归系数是否为零，每一个偏回归系数是否为零。用t检验方法。统计量 自由度结论：回归偏回归系数是否有意义，是否为零；对应的自变量是否有意义。,、常数项（截距）的检验 检验常数项（截距）是否为零。用t检验方法。一元线性回归：H0:=0 H1:0,多元线性回归：H0:0=0 H1:00,模型的预测效果检验 亦称回归模型的拟合优度检验。检验回归模型对样本数据的拟合程度。决定系数（determination coefficient）（R square）调整（校正）决定系数（adjusted R square）复相关系数R（multiple correlation coefficient）,线性回归适用性检验（）回归模型残差的正态性检验残差的直方图残差的累积概率图（P-P图）（）回归模型残差的独立性检验用Durbin-Watson检验，其参数称为Dw或D。D的取值范围是02，残差与自变量负相关。,（）残差的方差齐性检验 以上都是对残差的分析，称为残差分析。残差分析还可以）检出奇异点）评判预测效果。（）共线性诊断共线性（collinearity）共线性的危害共线性的鉴别容差（tolerance）方差膨胀因子（variance inflation factor）,多元线性回归方程的评价 评价回归方程的优劣、好坏可用确定系数R2和剩余标准差Sy,x1,2.p。Sy,x1,2.p SQRT（SS误差n-p-1）如用于预测，重要的是组外回代结果。,确定系数：简记为R2，即回归平方和SS回归与总离均差平方和SS总的比例。R2 SS回归 SS总 可用来定量评价在Y的总变异中，由P个X变量建立的线性回归方程所能解释的比例。,选择变量的统计学标准,R2最大 R2 SS回归 SS总adjR2最大：adjR21MS误差/MS总Cp值最小 Cp（n-p-1)(MS误差.p/MS误差.全部1）（p+1),回归方程中自变量的选择,多元线性回归方程中并非自变量越多越好，原因是自变量越多剩余标准差可能变大；同时也增加收集资料的难度。故需寻求“最佳”回归方程，逐步回归分析是寻求“较佳”回归方程的一种方法。,选择变量的方法,最优子集回归分析法：p个变量有2p1个方程逐步回归分析向前引入法(forward selection)向后剔除法(backward selection)逐步引入剔除法(stepwise selection)H0：K个自变 量为好 H1：K1个自变量为好,向前引入法（forward selection)自变量由少到多一个一个引入回归方程。将 corr(y,xj)最大而又能拒绝H0者，最先引入方程，余此类推。至不能再拒绝H0为止。,向后剔除法（backward selection)自变量先全部选入方程，每次剔除一个使上述检验最不能拒绝H0者，直到不能剔除为止。,逐步引入剔除法（stepwise selection)先规定两个阀值F引入和F剔除，当候选变量中最大F值F引入时，引入相应变量；已进入方程的变量最小FF剔除时，剔除相应变量。如此交替进行直到无引入和无剔除为止。（计算复杂）,最小二乘法的矩阵表示,最小二乘估计量的性质,（1）线性（估计量都是被解释变量观测值的线性组合）（2）无偏性（估计量的数学期望=被估计的真值）（3）有效性（估计量的方差是所有线性无偏估计中最小的）,OLS估计量的性质（续）,线性,无偏性,有效性,3.偏回归系数的意义,多元回归模型中的回归系数称为偏回归系数某解释变量前回归系数的含义是，在其他解释变量保持不变的条件下，该变量变化一个单位，被解释变量将平均发生偏回归系数大小的变动,4.正规方程,由最小二乘法得到的用以估计回归系数的线性方程组，称为正规方程,正规方程的结构,Y 被解释变量观测值 n x 1X 解释变量观测值（含虚拟变量n x(k+1)）XX 设计矩阵（实对称(k+1)x(k+1)矩阵）XY 正规方程右端 n x 1 回归系数矩阵（(k+1)x 1）高斯乘数矩阵，设计矩阵的逆 残差向量（n x 1）被解释变量的拟合（预测）向量 n x 1,3.5多元线性回归模型的预测,时间序列预测,时间序列的形成：长期趋势变化、季节性周期变化、循环变化、随机变化时间序列模型：加法模型、乘法模型趋势分析：移动平均数法、加权移动平均数法、修正移动平均数法、指数平滑法,确定性时序分析的目的,克服其它因素的影响，单纯测度出某一个确定性因素对序列的影响推断出各种确定性因素彼此之间的相互作用关系及它们对序列的综合影响,趋势分析,目的有些时间序列具有非常显著的趋势，我们分析的目的就是要找到序列中的这种趋势，并利用这种趋势对序列的发展作出合理的预测 常用方法趋势拟合法平滑法,趋势拟合法,趋势拟合法就是把时间作为自变量，相应的序列观察值作为因变量，建立序列值随时间变化的回归模型的方法 分类线性拟合非线性拟合,线性拟合,使用场合长期趋势呈现出线形特征模型结构,平滑法,平滑法是进行趋势分析和预测时常用的一种方法。它是利用修匀技术，削弱短期随机波动对序列的影响，使序列平滑化，从而显示出长期趋势变化的规律 常用平滑方法移动平均法指数平滑法,移动平均法,基本思想假定在一个比较短的时间间隔里，序列值之间的差异主要是由随机波动造成的。根据这种假定，我们可以用一定时间间隔内的平均值作为某一期的估计值 分类n期中心移动平均n期移动平均,移动平均期数确定的原则,事件的发展有无周期性以周期长度作为移动平均的间隔长度，以消除周期效应的影响对趋势平滑的要求移动平均的期数越多，拟合趋势越平滑对趋势反映近期变化敏感程度的要求 移动平均的期数越少，拟合趋势越敏感,移动平均预测,灰色系统模型,研究一个系统，一般应首先建立系统的数学模型，进而对系统的整体功能，协调功能以及系统各因素之间的关联关系，因果关系进行具体的量化研究。这种研究必须以定性分析为先导，定量与定性紧密结合。系统模型的建立，一般要经过思想开发，因素分析，量化，动态化，优化五个步骤。即语言模型，网络模型，量化模型，动态模型，优化模型。在建模过程中，要不断的将下一阶段中所得的结果回馈，经过多次循环往返，使整个模型逐步趋于完善。,2.1 灰色生成,将原始数据列中的数据,按某种要求作数据处理称为生成.客观世界尽管复杂,表述其行为的数据可能是杂乱无章的,然而它必然是有序的,都存在着某种内在规律,不过这些规律被纷繁复杂的现象所掩盖,人们很难直接从原始数据中找到某种内在的规律.对原始数据的生成就是企图从杂乱无章的现象中去发现内在规律.,常用的灰色系统生成方式有:累加生成,累减生成,均值生成,级比生成等,下面对这几种生成做简单介绍.,2.1.1 累加生成,累加生成,即通过数列间各时刻数据的依个累加以得到新的数据与数列.累加前的数列称原始数列,累加后的数列称为生成数列.累加生成是使灰色过程由灰变白的一种方法,它在灰色系统理论中占有极其重要地位,通过累加生成可以看出灰量积累过程的发展态势,使离乱的原始数据中蕴含的积分特性或规律加以显化.累加生成是对原始数据列中各时刻的数据依次累加,从而生成新的序列的一种手段.,2.2 GM(1.1)模型建模机理,第5章投入产出综合平衡模型,5.1部门间投入产出综合平衡模型5.2部门间投入产出综合平衡模型的应用5.3企业投入产出模型,5.1部门间投入产出综合平衡模型,“投入”与“产出”的关系（图）国民经济各部门既是生产者，又是消费者投入产出表的定义价值型投入产出表的结构：主栏包括生产资料转移价值和活劳动创造价值两大部分，它反映了社会产品的价值构成；宾栏包括中间产品和最终产品两大部分，它反映了社会产品的分配和使用去向。,投入产出法简介,投入产出分析，又称“部门平衡”法，或称“产业联系”分析，是由美国经济学家瓦列昂捷夫在20世纪30 年代最早提出来的。它主要通过编制投入产出表及建立相应的数学模型，反映经济系统各个部门(产业间)的关系投入、产出和部门之间的联系分析，投入是指社会产品在生产过程中所消耗的劳动力、劳动手段和劳动对象等；“产出”是指社会产品生产出来后分配的去向和数量，它包括生产消耗、消费、出口、增加储备、基本建设等,劳动者,固定资产,自然资源,流动资产,劳动力,消费品,出口,积累,原材料,动力燃料,辅助材料,劳动手段,劳动对象,国民经济系统,生产资料,消费资料,中间产品,最终产品,基建,投入与产出的关系,一、投入产出表,投入产出分析从一般均衡理论中吸收了有关经济活动的相互依存性的观点，并用代数联立方程体系来描述这种相互依存关系。根据国民经济各部门既是生产者又是消费者的特点，将各部门生产需要的各种投入与所生产的产品分配去向有规律的排列在一张纵横交错的棋盘式表格中，就形成了一张反映国民经济各部门之间投入、产出关系的表格，该表格叫投入产出表。其特点是：在考察部门间错综复杂的投入产出关系时，能够发现任何局部的最初变化对经济体系各个部分的影响。编制投入产出表是进行投入产出分析的前提,表7.1.2 价值型投入产出表,投入-产出模型及其计算方法,投入-产出表水平方向：产品和生产要素的中间使用者和最终使用者垂直方向：生产部门和支出部门四个象限：左上象限：部门间交易左下象限：各部门购买生产要素的支出和对外国的支出右上象限：产品、服务、生产要素的最终需求（国内和国际需求）右下象限：生产要素和资本品对最终使用者的直接供给,左上象限每一行：各个部门的产出如何分配，加总是各个部门产出的总需求每一列：各个部门投入品的来源，加总是各个部门投入的总供给左下象限每一行加总是各种要素支出的总和每一列底部是各部门购买的投入品的总支出,四个重要的加总方程,（3）投入和产出的平衡关系,行、列各部门的关系如下：总供给=总产出+进口=中间使用合计+最终使用合计=总需求总产出=中间使用合计+最终使用合计-进口=中间投入合计+增加值合计=总投入中间投入合计=中间使用合计增加值合计=最终使用合计-进口和成立的条件是每行或每列；和成立的条件是全部产业部门的合计或者说是总量平衡关系。,4.6.1 应 用（二）投入产出分析,技术参数,直接消耗系数,同理，有直接折旧系数、劳动报酬系数、社会纯收入系数、国民收入系数、劳动消耗系数等,综合平衡模型,直接消耗系数aij,i,j=1,2,n表示部门j生产单位产品j所需直接消耗的部门i的产品i的数量.然而，一般而言，部门j除直接消耗部门i的产品外，还要通过一系列中间环节间接消耗部门i的产品.直接消耗与间接消耗的和称为完全消耗.,（完全消耗系数矩阵），,完全消耗系数,则由完全消耗的定义知,即,或,解之得,小结：部门间投入产出综合平衡模型,技术参数：直接消耗系数aij或A、直接折旧系数aDj、劳动报酬系数aVj、社会纯收入系数aMj、国民收入系数aNj、劳动消耗系数aLj模型：按行Xi-aij*Xj=Yi(5.1.13)(I-A)X=Y(5.1.14)按列1-(aij+aDj)*Xj=Nj(5.1.15)I-CX=N(5.1.16)完全消耗系数=直接消耗+间接消耗的总和 bij=aij+bik*akj B=(I-A)-1-I求解：已知Y,X=(I-A)-1Y;已知N,X=(I-C)-1N,部门间投入产出综合平衡模型的假设,(1)国民经济各部门投入与产出是唯一的线性关系;(2)同意物质生产部门投入结构必须相同;(3)产品分类有限;,投入产出模型求解的基本条件,经济条件,数学条件（I-A）-1必须存在,必须存在,投入产出模型的应用:分析国民经济各种比例关系,计算分析两大部类的比例和扩大再生产的规模分析确定积累和消费的比例分析国民经济各部门的比例及其各部门对国民经济的影响:直接消耗系数完全消耗系数、中间消耗系数、部门间联系程度系数、影响系数,投入产出模型的应用:产品价格模型和产品价格变动的影响,产品价格模型：P=(I-A)-1(AD+AV+AM),价格变动的影响,设定第k个部门价格变化为Pk，则其他（n-1）个部门为保持本部门社会纯收入不变，价格调整幅度为：,设定第k个部门价格变化为Pk，则其他部门价格不变，各部门社会纯收入调整幅度为：,分析税收、利润、工资、折旧的波动对产品价格的影响,表,第6章静态线性系统最优化模型及求解,6.1最优化及最优化模型的建立方法6.2系统线性规划模型6.3 Lingo软件简介6.4线性规划的求解方法6.5灵敏度分析和参数规划6.6对偶规划及影子价格6.7整数规划6.8模糊线性规划及其应用6.9灰色线性规划及其应用,6.1最优化及最优化模型的建立方法,优化过程从系统思想出发对系统评价目标的定性和定量分析对系统约束条件的定性和定量分析建立最优化模型模型求解对求解结果进行分析和系统因素的变化时对求解结果影响的分析,线性规划模型的建立方法问题的提出编制原始数据设置变量与各种参数建立目标函数确定约束条件,6.2.1.生产任务分配问题运输问题生产能力配置问题资源利用问题下料问题与配套问题人员分配问题经济系统建立目标函数和约束条件应注意的问题,返回,6.2系统线性规划模型,生产任务分配问题,生产任务在各基层单位的分配生产任务明确之后制定日历生产计划,生产任务在基层单位的分配,生产任务在基层单位的分配,制定日历计划问题,制定日历计划问题,运输问题：,问题分析,模 型,返回,运输问题,表6.2.2 各企业生产能力、单位产品生产成本表,表6.2.8 最优调运方案,生产能力配置问题,考虑原料供应费用的生产能力配置模型,考虑原料供应费用的生产能力配置模型,经济系统建立目标函数和约束条件应注意的问题,选择目标函数应注意的问题：理解指标内涵主要指标与次要指标的关系量纲和数量级采用综合指标线性与非线性目标,选择约束条件应注意的问题：依据系统目标研究约束条件减少无用的约束数量注意结构性约束避免矛盾约束综合考虑目标与约束条件之间的关系,6.3 LinGo软件,Lingo语言：Model:Sets:Endsets;!设置段 Data:Enddata;!数据段 目标 约束；!目标约束段 Calc:Endcalc;!计算段 Init:EndInit;!初始段End,返回,LinGo模式,Model:Sets:!定义集合 Endsets Data:！定义数据 Enddata 调用函数与计算 end,返回,集合部分,model:！开始sets:！定义集合ve/1.3/:c,x;co/1.3/:b;ma(co,ve):a;endsets！注：集表达式：名称/成员/：属性 名称（初始集）：属性,返回,定义数据,data:！定义数据c=3 5 4;b=1500 800 2000;a=2 3 0 0 2 4 3 2 5;Enddata！注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号；,返回,调用函数,max=sum(ve(j):c(j)*x(j);for(co(i):sum(ve(j):a(i,j)*x(j)=b(i);主要函数：for(set(set_index_list)|condition:expression)sum(set(set_index_list)|condition:expression)min(max)(set(set_index_list)|condition:expression),返回,结果,Global optimal solution found at iteration:3Objective value:2675.000Variable Value Reduced CostC(1)3.000000 0.000000C(2)5.000000 0.000000C(3)4.000000 0.000000X(1)375.0000 0.000000X(2)250.0000 0.000000X(3)75.00000 0.000000,B(1)1500.000 0.000000B(2)800.0000 0.000000B(3)2000.000 0.000000A(1,1)2.000000 0.000000A(1,2)3.000000 0.000000A(1,3)0.000000 0.000000A(2,1)0.000000 0.000000A(2,2)2.000000 0.000000A(2,3)4.000000 0.000000A(3,1)3.000000 0.000000A(3,2)2.000000 0.000000A(3,3)5.000000 0.000000,Row Slack or Surplus Dual Price1 2675.000 1.0000002 0.000000 1.0500003 0.000000 0.62500004 0.000000 0.3000000,返回,6.4 线性规划的求解方法,6.4.1 运输问题的特殊求解方法表上作业法 6.4.2 线性规划的标准形式 6.4.3 线性规划解的基本定义、定理及图解法,表上作业法的程序：(1)确定初始可行方案。(2)检验方案是否最优,若是最优解,则停止计算;否则转下一步。(3)改进，得新的方案。(4)重复(2),(3)直到求出最优方案。,6.4.1 运输问题的特殊求解方法,例题6.7：运输问题,（1）给出初始调运方案最常用的方法最小元素法,表上作业法要求，调运方案的数字格必须为m+n-1个，且有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。,300,100,400,600,300,300,最小元素法中的退化情况,300,600,0,500,400,200,出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。,位势表,0,检验数表,若所有检验数非负则是最优解,(2)最优性检验的方法位势法,3,10,-5,-1,9,2,(2),(-3),(9),(8),(-2),(9),（1）从一个检验数为负数且最小的空格出发，和其它数字格构成闭回路。可证，此闭回路存在且唯一。,（2）在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。,（3）运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。,(3)方案调整的方法闭回路法,位势表,1,0,2,1,9,-4,8,（2）,（9）,（8）,（9）,（-3）,（-2）,检验数表,有检验数为负,不是最优解。,2.2.4 表上作业法举例,位势表,1,0,1,2,8,-3,7,（3）,（9）,（7）,（1）,（-2）,（-2）,检验数表,表上作业法举例(续),检验数都非负，得最优解。,表上作业法是以产销平衡为前提的，即当实际问题产销不平衡时，需要转化为产销平衡的运输问题，具体来说有两种情况：,（1）产大于销，即,此时增加一个假想的销地n+1，该销地的销量为，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。,（2）销大于产，即,此时增加一个假想的产地m+1，该产地的产量为，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。,2.3 产销不平衡的运输问题,产销不平衡的运输问题举例,设有三个化肥厂供应四个地区的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送化肥的单位运价如又表：,试求出总运费最省的花费调运方案。,解：三个厂的总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。地区每年最多能分配到60万吨，这样四个地区最高需求为210万吨，销大于产。于是，增加虚产地D，产量为50万吨。还要把地区和的产量分为两部分。建立如下表格模型：,50 20 10 3030 20 0 30 20,例 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。又知如果生产出来的柴油机当季度不交货，每台每季度的存储维护费为0.15万元。试安排全年生产计划，使总费用最低。,2.4 应用举例,解：各季度都产出产品，都可看作产地；各季度都有定货，都可看作销地。这是一个产大于销的运输问题，需增加虚销地D。表格模型如下：,产销平衡表,10.8,10.95,11.10,11.25,0,M,11.10,11.25,11.40,0,M,M,11.00,11.15,0,M,M,M,11.30,0,单位运价表,10 15 0 5 30 20 10 10,例 某航运公司承担六个港口城市A,B,C,D，E,F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：,假定各航线使用的船只相同，各城市间的航程天数如下：,又知每条船每次装卸货时间各需1天，问该公司至少应配备多少条船？,为使配备船只数尽可能少，建立如下运输模型:,1 1 1 1 1,调度需要的船只数为 2+5+13+17+3=40条,解 所需船只分成两部分：,(1)载货航行需要的船只数.,3*19+2*5+9+15=91条.,(2)各港口间调度需要的船只数.,各港口每天船只的余缺数为:,一 般形式,目标函数,约束条件,线性规划,注 释,返回,线性规划,规范形式,返回,线性规划,标 准形式,返回,线性规划,概念,线性规划,模 型转换,变量转换 目标转换约束转换实例,返回,线性规划,约 束转换,等式变不等式不等式变等式不等式变不等式,返回,线性规划,