《管理运筹学》讲稿（第1 2章）概述课件.ppt

《《管理运筹学》讲稿（第1 2章）概述课件.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》讲稿（第1 2章）概述课件.ppt（88页珍藏版）》请在三一办公上搜索。

1、管理运筹学 第1章,李存芳 博士/副教授/硕士生导师研究领域：战略管理、组织行为、运营管理讲授课程：管理运筹学、管理系统工程、运营管理 经济学单 位：江苏师范大学管理学院 物流管理系 E-mail：,2,教材与参考书籍,教材：魏晓平等编.管理运筹学， 中国矿业大学出版社，2011参考书：钱颂迪,甘应爱等. 运筹学, 清华大学出版社，2001宁宣熙. 运筹学实用教程, 科学出版社，2007徐辉,张延飞. 管理运筹学, 同济大学出版社,2011郭耀煌等. 运筹学. 西南交通大学出版社,1995,3,讲授提纲,第一章 绪论第二章 线性规划的基本问题第三章 线性规划的对偶问题第四章 线性规划的灵敏度分

2、析第五章 运输问题分析第六章 目标规划第七章 整数规划第八章 图与网络第九章 网络计划技术,4,考核方式,结课考试：笔试（ 闭卷） 70%作业与案例研究：结合企业实际进行应用 30%,5,管理运筹学的称谓,管理运筹学是一门研究如何最优安排的学科。 Operations Research日本译作“运用学”香港、台湾译为“作业研究”我国译作“运筹学”源于史记中刘邦赞誉张良“运筹帷幄中,决胜千里外”。取“运筹”二字，体现运心筹谋、策略取胜,司马迁,6,第一章 绪 论,一、发展历史二、学科作用 三、学科性质四、工作程序五、学科体系六、学习要求,7,1-1 发展历史,1. 早期的运筹思想 (1) 齐王赛

3、马,孙膑(约公元前380-432),孙武的后世子孙,战国中期著名军事家,担任齐国将领田忌的军师. 齐将田忌与齐王赛马,孙膑献策:以下马对齐王上马,以上马对齐王中马,以中马对齐王下马. 结果田忌以一负两胜而获胜.,8,(2) 渭修皇宫,宋真宗年间(公元1008一1017年),都城开封里的皇宫失火,需要重建. 丁渭受命负责限期重新营造.丁渭将挖土、运送物材、处理废弃瓦砾等三件工程一蹴而成,节省的工费数以亿万计.,9,(3) 沈括运粮,沈括(1031-1095年),北宋时期大科学家、军事家.在率兵抗击西夏侵扰的征途中,曾经从行军中各类人员可以背负粮食的基本数据出发,分析计算了后勤人员与作战士兵在不同

4、行军天数中的不同比例关系；同时也分析计算了用各种牲畜运粮与人力运粮之间的利弊,最后做出了从敌国就地征粮,保障前方供应的重要决策.从而减少了后勤人员的比例,增强了 前方作战的兵力.,10,2. 军事运筹学阶段 20世纪40年代（二战期间）诞生于英美。问题与对策：1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。拟建立空防预警系统。 为对付德国海军的潜艇拟以深水炸弹代替飞机射击。解决方案：成立运筹学小组，称Operational Research，意为作战研究。著名的“Blackett马戏团”：由3位生理学家、2位数学物理学家、1位天体物理学家、1位陆军军官、1位测量员、

5、1位普通物理学家、2位数学家组成。,11,成效：英美等国蠃得英伦三岛空战、太平洋岛战、北大西洋战争的胜利。 3. 管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。1947年美国数学家乔治伯纳德丹兹格（G.B.Dant- zig）提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。被称为“线性规划之父”。如“配餐问题”。,12, 1951年美国经济学家库普曼斯（J.C.Koopmans）把线性规划应用到经济领域，为此与利奥尼德康托罗维奇(L.V.Kantorovich，苏联数学家) ，一起因“最优资源

6、配置理论的贡献”获1975年诺贝尔经济学奖。20世纪50年代中期钱学森、许国志等将管理运筹学引入中国 ，取得了很大成就。,13,1-2 学科作用,1. 量化管理的重要性 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。目的：用科学方法分析管理问题，为管理者决策提供依据目标：在企业经营内外环境的限制下，实现资源效用最大,量化管理是第一步,它导致控制,并最终实现改进如果不能量化某些事情，那么就不能理解它如果不能理解它，那么就不能控制它如果不能控制它，那么就不能改进它 H. James Harrington,定性到定量分析，数量界限的重要性：量变引起质变,14,听一

7、场音乐会：情况1：网络订票的票价500元，不去可退票。在你马上要出发的时候，发现你把最近的价值500元的电话卡弄丢了。你是否还会去听这场音乐会？情况2：假设昨天花500元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必须再花500元钱买张票，去还会不去？,2. 量化思考使人理性,实验表明，大部分的回答者仍旧会去听,结果却是，大部分人回答说不去了,15,1-3 学科性质,1. 研究对象美国运筹学会给出定义：“运筹学是一门在紧缺资源的情况下，如何设计与运行一个人机系统的决策科学。”一般定义：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的

8、专门问题，为决策者选择最优决策提供定量依据。”研究对象：经济和管理活动中能用“数量关系”描述的如运营、规划与组织管理问题。2. 学科特点强调科学性和定量化强调应用性和实践性强调整体性和系统性,16,1-4 工作程序,17,1-5 学科体系,1. 管理问题,18,2. 学科内容,19,3. 学科应用管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术,20,1-6 学习要求,如何学习,重点在结合实际的应用发挥自己理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化对于解决问题

9、的方案或模型的解的分析与应用能力,21,第2 章 线性规划的基本问题,Sub title,内容提要,第一节 线性规划问题及其数学模型第二节 线性规划问题的解第三节 线性规划的单纯形解法第四节 确定初始基本可行解的大M法,22,2-1 线性规划问题及其数学模型,线性规划研究两类问题： 一类，给定了一定数量的人力、物力、财力等资源，研究如何运用这些资源使完成的任务最多； 另一类，给定了一项任务，研究如何统筹安排，才能以最少的人力、物力、财力等资源来完成该项任务。本质上就是寻求某个整体指标的最优化问题。,23,生产计划问题,例1 某企业生产甲、乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B

10、加工，最后都需在设备C上装配。经测算得到相关数据如表所示。问题：应如何制定生产计划，使总利润为最大。 据市场分析，单位甲、乙产品的销售收益分别为3和5元，试确定获利最大的产品生产计划。,2.1.1 线性规划问题,2.1.1.1 典型问题,24,(1)设x1为甲产品的产量，x2为乙产品的产量。（决策变量）(2)产量会受设备加工能力制约。（约束条件）设备A的加工能力约束条件表达为： 2 x1 16同理，设备B的加工能力约束条件表达为： 2x2 10设备C的装配能力也有限，其约束条件为 3x1+ 4x2 32(3)目标是企业利润最大化。（目标函数） max Z= 3x1 +5x2 (4)另外，甲乙产

11、品的产量为非负 x1 0， x2 0,综上，问题的LP模型：求一组变量x1 、x2,25,物资调运问题,例2 某产品商有3个工厂（产地）A1、A2、A3，其经销商有4个需求市场（销地）B1、B2、B3、B4。已知各厂的日产量、各经销商的日销售量及从Ai 到Bj 的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,26,(1)设从Ai（i=1,2,3）到Bj(j=1,2,3,4)的调运量为xij（决策变量）(2)目标是运费最小（目标函数）Min Z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x3

12、4 (3)实现供需平衡：产量之和等于销量之和（约束条件）供应平衡条件（当日产量全部运走）,x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30,销售平衡条件（当日送货全部售完）,x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40,非负性约束 xij0 (i=1,2,3；j=1,2,3,4),27,归纳起来，此问题的LP模型为： 求一组变量xij（i=1,2,3； j=1,2,3,4)，满足下列约束条件,x11+x12+x13+x14=50 x21+x22+x23+x

13、24=20 x31+x32+x33+x34 =30,x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40,xij0 (i=1,2,3；j=1,2,3,4),使目标函数 Z（x）=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34达到最小,28,混合问题,例3 某合金产品由A、B两种金属混合制成，按合金性能要求，金属A不能超过6%，金属B不能少于92%（其它杂质不计）。若金属A、B的价格分别为2元/千克和5元/千克。那么，本合金应该按怎样的比例混合配料才能使其原料

14、成本最低？ （1）设1千克合金产品中A、B两种金属含量分别为x1、x2(决策变量) （2）为满足合金对金属A、B含量的限制，应有：（约束条件）,x1 0.06 x20.92 而金属A、B构成合金的含量总平衡关系式为（平衡条件） x1+ x2=1 当然，金属A、B的含量均不能为负值，即有 x1 0， x2 0,29,（3）目标是使原料成本 Z（x）=2x1+5x2达到最低。 于是，得此问题的LP模型为： 求一组变量x1、x2，满足下列约束条件 x1 0.06 x20.92 x1+ x2=1 x1 ，x2 0使目标函数 Z（x）=2x1+5x2达到最小。,30,2.1.1.2 问题特征 上述三个案

15、例，尽管其实际问题的背景有所不同，但讨论的都是资源的最优配置问题。它们的共同特征：目标明确。决策者寻求某个整体目标最优。如最大收益、最小成本等。多种方案。决策者可从多种可供选择的方案中选取最佳方案。如不同产品的生产方案和物资调运方案等。资源有限。决策者的行为必须受到限制。如产品的生产数量受到资源供应量的限制；物资调运既要满足各销地的销售量，又不能超过各产地的生产量。线性关系。约束条件及目标函数均保持线性关系。 具有以上特征的决策问题，被称为线性规划问题。,31,用一组非负决策变量（x1,x2,xn ）表示的一个决策问题；决策变量是决策问题待定的量值。 存在一组等式或不等式的线性约束条件；任何管

16、理决策问题都是限定在一定的条件下求解；约束条件是决策方案可行的保障。 有一个希望达到的目标，可表示成决策变量的极值线性函数。目标函数是衡量决策优劣的准则，如时间最省、利润最大、成本最低；有的目标要实现极大，有的则要求极小。,2.1.2 线性规划的数学模型,2.1.2.1 数学模型的共同特征,32,2.1.2.2 数学模型的一般形式,式中：cj（j=1,2, ,n） 价值系数；bi（i=1,2, ,m） 限定系数；aij（i=1,2, ,m; j=1,2, ,n） 技术系数.,xj（j=1,2, ,n） 决策变量；S.t“Subject to”（在-条件下）的缩写。每一个约束条件只持有一种符号（

17、或=或）。,33,由于线性规划模型有多种形式，为了讨论和求解的方便，需要在这多种形式中规定一种形式（标准形式）。 线性规划模型的标准型为,2.1.3 线性规划模型的标准形式,Max Z（x） = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1J xJ + + a1n xn = b1 a21 x1 + a22 x2 + + a2J xJ + + a2n xn = b2 am1 x1 + am2 x2 + + amJ xJ + + amn xn = bm x1 ，x2 ， ，xn 0,34,2.1.3.1 线性规划模型标准形式的特点,（1）目

18、标函数是求极大值的(Max)；（2）所有决策变量都是非负的(xJ0 )；（3）所有约束条件都是“=”型的(方程)；（4）所有常数项都是非负的(bi 0 ).,2.1.3.2 线性规划模型标准形式的简缩形式,(1)代数式,(2)向量式,35,(3) 矩阵式,A：技术系数矩阵，简称系数矩阵（mn）；一般 mn， m、n为正整数b：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。,36,(1)对于极小化原问题 minZ=CX， 则令 Z=-Z，转为求 maxZ=-CX (2)若某个bi0， 则以1乘该约束两端，使之满足非负性的要求。(3)对于型约束， 则在左端加上一个非

19、负松弛变量，使其为等式。 (4)对于型约束， 则在左端减去一个非负剩余变量，使其为等式。 (5)若某决策变量xk无非负约束（自由变量）， 则令xk=xk - xk ，(xk0, xk 0) 。,2.1.4 线性规划标准型转换方法,37,举例,例4 把例1的模型化为标准型例1的数学模型为,解：在各个不等式的左边分别加上松驰骋变量，使之变成等式，从而化为标准型：,38,解：通过以下四个步骤：,例5 把下列线性规划的模型化为标准型,39,（1）目标函数两边乘上-1化为求最大值；（2）以 代入目标函数和所有的约束条件中，其中 ；（3）在第一个约束条件的左边加上松驰变量x4 ； （4）在第二个约束条件的

20、左边减去剩余变量x5 。可得标准型,40,2.2.1 线性规划问题解的概念 由上节分析可知线性规划模型的标准型为,2-2 线性规划问题的解,Max Z（x） = c1 x1 + c2 x2 + + cn xn （2-1） s.t. a11 x1 + a12 x2 + + a1J xJ + + a1n xn = b1 a21 x1 + a22 x2 + + a2J xJ + + a2n xn = b2 （2-2） am1 x1 + am2 x2 + + amJ xJ + + amn xn = bm x1 ，x2 ， ，xn 0 （2-3）,41,（1）可行解 满足约束条件AX=b和X0的解X=(

21、x1,x2, ,xn)T称为线性规划问题的可行解，而所有可行解的集合称为可行域。（2）最优解 使目标函数最优的可行解，称为最优解。（3）基本解 设A是约束方程组（2-2）的mn阶系数矩阵，其秩为m，则A中任意m个线性无关的列向量组成的mm阶子矩阵称为线性规划的一个基矩阵（简称为一个基，最多有 个），记为B。显然，B为非奇异矩阵，即B0。,42,组成基矩阵的m个列向量称为基向量，其余n-m个向量称为非基向量；与m个基向量对应的m个变量称为基变量，其余的n-m个变量则被称为非基变量。显然，基变量随着基的变化而改变，当基被确定以后，基变量和非基变量也随之确定。 若令约束方程组（2-2）中的n-m个非

22、基变量为0，再对余下的m个基变量求解，所得到的约束方程组的解称为基本解。 问题的实质：一个基矩阵（mm）对应一组基向量（P1, P2, , Pm）对应一组基变量（x1, x2, , xm）令相应一组非基变量为0（0, 0, , 0）由克莱姆法则求出唯一解再加上非基变量（0, 0, , 0） 便得一个基本解。,43,引例： 设B=（P1, P2, Pm）为线性规划的一个基，于是xi (i=1,2,m)为一组基变量，xj (j=m+1, m+2,n)就为相应的非基变量。 现令非基变量xm+1=xm+2=xn=0，方程组（2-2）就变为,a11 x1 + a12 x2 + + a1J xJ + +

23、a1mxm = b1 a21 x1 + a22 x2 + + a2J xJ + + a2m xm = b2 am1 x1 + am2 x2 + + amJ xJ + + amm xm = bm,此时方程组有m个方程、m个未知数，可唯一地解出(克莱姆法则)： x1 ,x2 , xm,44,则向量 X=(x1, x2, , xm, 0, ,0 )T (其中含有n-m个0)就是对应于基B的基本解。（4）基本可行解 满足非负条件（2-3）的基本解称为基本可行解；对应于基本可行解的的基，称为可行基。 显然，基本可行解既是基本解，又是可行解。 由于约束方程组（2-2）的基的数目最多为 ，而且基本解与基一一

24、对应，故基本解的数目也不多于 。 一般，基本可行解的数目要小于基本解的数目，最多两者相等。,45,其相互关系图示如下：,46,解：将已知模型化为标准型：,例6 求下列线性规划问题的所有基本解，并指出哪些是基本可行解。,47,显然，m=2；秩=2 由于其中任意两个列向量都是线性无关的，故有 个不同的基，对应着6个不同的基本解（表2-4）。 由于 满足非负条件（2-3），所以为基本可行解；而 两个基本解不满足非负条件，因此为非可行解。,其系数矩阵为,48,表2-4,49,2.2.2 线性规划问题的图解法,仍以例1为例分析：（1）确定线性规划的可行域,可行域：满足所有约束条件的解的集合，即所有约束条

25、件共同围成的区域。,maxZ(x)= 3x1 +5 x2 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 0 图中阴影区域上任何一点的坐标（x1,x2）都同时满足所有约束条件。,S.t.,50,(2)寻找线性规划的最优解点,目标函数 Z= 3x1 +5 x2 代表以 Z 为参数的一族平行线。,目标函数线, 通过原点时Z=0;距离原点越远Z值越大;即将脱离可行域的最后一点Z值最大,图中的C点就是最优解点.,51,通过求解方程组:便得C点坐标:x1=4;x2=5代入目标函数得:z=37结论:安排甲产品生产4件、乙产品生产5件，可使总利润达到最大为37。,52,2.2.3

26、线性规划解的几种特殊情况,1、唯一最优解：只有一个最优点(上节的案例),2、多重最优解：无穷多个最优解,在例1中,当乙产品市场收益下降到4元，其数学模型变为,53,在一批等值线中,离原点最远又与可行域有交点的直线恰与BC重合,这表明以BC为端点的线段上的任意点都使目标函数取得相同的最大值-该线性规划有多重最优解.,3、无界解：可行域无界，目标值无限增大 (缺乏必要约束),54,其最优解为：X1=0，X2=0，目标函数值Z=0（有下界） -因此，要根据具体模型来分析无界可行域与无界解间的关系。,可行域的拓展方向与目标函数的拓展方向一致-目标函数无上界，Z（x）。问题的原因可能是遗漏了约束条件。

27、需要指出的是，无界可行域并不一定意味着目标函数无界。如将本例的目标函数改为,55,4、没有可行解：线性规划问题的可行域是空集 (约束条件相互矛盾),由上图可知：没有能同时满足所有约束条件的点，可行域是空集 -没有可行解。,56,2.2.4 线性规划解的基本性质,(1) 由线性不等式组成的可行域是凸多边形(凸多边形是凸集);凸集定义：集合内部任意两点连线上的点都属于这个集合,(2) 凸多边形的顶点与基本可行解一一对应;(3) 如有可行解,一定有基本可行解(凸多边形必有顶点);(4) 基本可行解的个数是有限的(凸多边形的顶点个数有限) ;(5) 线性规划问题若有最优解,一定会在凸多边形某个顶点上取

28、得(可以在基本可行解中找到).,57,-因此,求解线性规划问题,只需在基本可行解(凸多边形的顶点)中寻找即可.,58,2-3 线性规划问题的单纯形解法,2.3.1 线性规划解题思路,先找到一个初始基可行解，也就是找到一个初始可行基，设法判断这个基可行解是不是最优解。 如果是最优解，就得到这个线性规划问题的最优解； 如果判断出不是最优解，就设法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解； 如果还不是，再接着进行下一个可行基变化，直到得到最优解。,59,仍以例1来讨论,该问题的数学模型为,2.3.2 单纯形法的基本求解思路,maxZ(x)= 3x1 +5 x2

29、 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 0,分析:首先将约束条件中加入松驰变量,化成标准型:,maxZ(x)= 3x1 +5 x2+0 x3+0 x4+0 x5 （2-4） 2 x1 + x3 =16 （2-5） 2x2 +x4 =10 （2-6） 3x1 +4 x2 + x5 =32 （2-7） x1 , x2 , x3 , x4 , x50,60,（1）找出一个基本可行解作为初始解 在约束条件中，x3,x4,x5的系数向量构成单位矩阵，成为线性规划的一个基。x3,x4,x5就是基变量，x1,x2为非基变量。若令非基变量x1=0,x2=0，可得x3=16,

30、x4=10,x5=32。显然，这就是一个基本可行解： X（0）=（0,0,16,10,32） （2）检验判断是否为最优解 将X（0）=（0,0,16,10,32）代入目标函数,可知x1=0, x2=0，Z(X（0）)=0,即为图中的原点.-两种产品产量为0,收益也为0.显然不会是最优解. 需要考虑寻求一个新的基本可行解,且使目标函数值增加.,61,（3）选择进基变量 从目标函数可以看出, 由于x1,x2前面的系数均为正，当x1或x2由现在的0变成非0时，均可使目标函数值增加. 由于x2的系数比x1的系数大（收益增长率高）。 -故选择x2为进基变量。(大进)那么，为了保证新解仍为基本可行解，在x

31、3,x4,x5中让谁作为出基变量呢？为此，可把约束条件中的原基变量x3,x4,x5用非基变量表示出来，即有,62,x3 =16- 2x1 x4 =10- 2x2 x5 =32- 3x1 -4 x2 因为 x1仍为非基变量（因为x2要进基），可令x1=0，于是有 x3 =16 x4 =10- 2x2 x5 =32-4 x2若取x4=0，则x2 =10/2；若取x5=0，则x2 =32/4。为了保证新解中的x3 , x4 , x50，一定有 x2 =min 10/2, 32/4 =5,63,因此，选择x4 为出基变量-最小比值法。换言之，出基变量应选择随着进基变量增大而最先变为0者。（小出） 为了

32、简便地得到一个新的基本可行解，可对约束方程组进行变换，即将（2-6）式中的x2 的系数变成1，（2-5）和（2-7） 两式中的x2 的系数变成0。其变换过程为： 以1/2乘（2-6）式，得（2-9）； 以-2乘（2-6）式加到（2-7），得（2-10）。 于是，新的约束方程组为：,2 x1 + x3 =16 （2-8） 1 x2 +（1/2）x4 =5 （2-9） 3x1 -2x4 + x5 =12 （2-10）,64,（4）推出新的基本可行解 若令此时的非基变量x1=0, x4=0；基变量x3, x2, x5的值可以从右边常数项直接得到.所以推出新的基本可行解: X（1）=（0,5,16,0

33、,12）该解对应于图示可行域的顶点 D. 相应地将目标函数用非基变量表示,变成:,Z(X（1）)= 25+3x1 (5/2 )x4 （2-11）,而当x1=0, x4=0时， Z(X（1）)= 25。 显然， Z(X（1）) Z(X（0）) 结果表明：生产产品乙5个单位，可获得的收益为25。,65,（5）选择新的进基变量 从（2-11）式可以看出，当非基变量x1 的值增加（由0变成非0）时，仍可使目标函数值增加。因此，还没有得到最优解。（当且仅当非基变量的系数均为负，目标函数才能达到最优） 进而，将x1作为新的进基变量，分析约束方程组（2-8）、（2-9）、（2-10）式可知， x1=min

34、16/2, 12/3 =4，故选择x5作为新的出基变量。 重复上述变换过程，得：,+ x3 + （4/3）x4 - （ 2/3）x5 =8 （2-12） x2 +（1/2）x4 =5 （2-13） 1 x1 -（2/3）x4 +（ 1/3）x5 =4 （2-14）,66,令此时的非基变量x4=0, x5=0；基变量x3, x2, x1的值可以从右边常数项直接得到.所以推出新的基本可行解: X（2）=（4,5,8,0,0） -该解对应于图示可行域的顶点 C.（6）检验判断是否为最优解（返回（2）继续检验） 将目标函数用非基变量表示,（2-11）式变成: Z(X（2）)= 37 -（1/2）x4

35、x5 （2-15） 由于目标函数（2-15）的所有非基变量的系数均为负，故当x4 或x5 增加时，目标函数值只会减少，而无法再使目标函数值增大。因此X（2）=（4,5,8,0,0）就是最优解，目标函数的最大值为37。,67,2.3.3 单纯形表 从前面代数解法中可以看出，求最优解的过程是一种迭代选优的过程，即从一个基本可行解迭代到另一个基本可行解，且使目标函数值一次比一次好。而在几何上则是从可行域的一个顶点迭代到另一个相邻的顶点。 为了方便运算，可以将代数运算表格化。,分析结果表明，企业应安排计划甲生产4个单位、乙生产5个单位，可获取最大收益为37个单位。,68,仍以例1来讨论,该问题的数学模

36、型为,maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32,可以推导,后选：小出,先选：大进,69,单纯形表内涵说明：, cj行的数字是目标凼数中各变量的系数，下面一行是与之相对应的变量； XB列填入的是基变量， CB列填入的是与基变量相对应的目标凼数中的系数，它们随着基变量的改变而变化； b/列填入的是约束方程组右端的常数，即非基变量为0时，基变量的取值； 中间为约束条件中的变量系数； 比值i列是在确定出基变量时，用于最小比值法计算的数字。,70, 最后一行称为检验数（j）行，它是把目标函数用

37、非基变量表示时的非基变量的系数。利用检验数便可以判断此表所对应的基本可行解是否为最优解。 当所有的检验数均不大于0时，表明目标凼数值不可能再增加，即得到最优解。,71,最优解 :X*=(4,5,8,0,0)T，Z*=37,后选：小出,先选：大进,72,2.3.4 单纯形法的计算步骤,（1）确定初始基本可行解，建立初始单纯形表。 （2）进行最优性检验。若所有的检验数j0，则已得到最优解，停止运算。否则，转下一步。 （3）确定进基变量Xk 。在所有的正检验数中选择最大的检验数所对应的非基变量为进基变量(大进)。如果进基变量Xk所在列的所有系数都0，则该问题为无界解，停止运算；否则，进行下一步。 （

38、4）确定出基变量Xs 。按最小比值法则求出故Xs为出基变量（小出）。转下一步。,73,（5）以ask为主元素，进行变换，得到新的单纯形表。将主元素变成1，同列的其它元素变成0，可得一组新的基本可行解，返回第二步，重新进行判别运算，直到取得最优解或判定无解。 一般说来，凡是在最优单纯形表中出现检验数为0的非基变量，就存在多个最优解多重最优解；凡是进基变量所在列的所有系数均小于0，此线性规划问题为无界解。,74,2.3.5 单纯形的管理启示,2x1=16,X0=(0,0,16,10,32)T,X1=(0,5,16,0,12)T,X1=(4,5,8,0,0)T,企业管理过程也是如此，把现有方案作为初

39、始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求完美。,75,2-4 确定初始基本可行解的大M法,2.4.1 问题的提出 在用单纯形法求解线性规划问题时，首先要确定出一个初始基本可行解。但是，对于任意一个线性规划问题，在化成标准模型后，一般来说不易直接得到一个初始的基本可行解。例如 线性规划模型（右侧）：其标准型为L1：,76,可见，标准型中没有一个单位矩阵为基，也就没有一个初始基本可行解。为此，在模型L1的后两个约束条件左边，引入非负的人工变量，得到下列方程组（2-16

40、）：,可见，构成了一个单位矩阵，也就可以得到一个初始基本可行解。,77,应该指出，由于人工变量的引入，破坏了原有模型（L1）的约束条件，故前面得到的不再是L1的基本可行解。如果在求解迭代过程中，将人工变量从基变量中退出，变为非基变量，则上述方程组（2-16）的基本可行解就成为原有模型L1的基本可行解了。为此提出一种方法大M法。2.4.2 大M法 对于没有明显初始基本可行解的标准型，将人工变量引入模型，并取人工变量的价值系数为-M（M为惩罚因子，是个很大的正数，是对引入不为0的人工变量的一种惩罚，即只要有一个人工变量不为0，目标函数无法实现最大化。）,78,显然，只要人工变量从基变量中退出，L2

41、的最优解也就是L1的最优解，且两个模型具有相同的目标函数值。因此可借助L2来求解L1。,引例：对标准型L1构造一个新模型L2：,79,求解L2的单纯形表为下表（2-15）。,后选：小出,先选：大进,后选：小出,先选：大进,80,后选：小出,先选：大进,81,从表2-15的最终表可以看出，所有的人工变量都已从基变量中退出，且检验数均小于或等于0。于是，可得L2的最优解：,L1的最优解：,82,如果经过多次迭代以后，检验数均满足最优判别条件，但仍有人工变量为基变量，且其值不为0，则说明所求问题无可行解。,83,作业,2.1. 金洋公司要加工两种产品I、，需要使用两种原材料及某专用生产设备等三种资源

42、，分别记为A、B、C。生产这两种产品的单位资源消耗、这些资源的每周可使用量及每单位产品可获利润如下表所示。问该公司每周应生产产品I与产品各多少单位，才能使每周的获利达到最大？（仅列出数学模型）,84,2.2. 某企业计划在下一个生产周期内用钢、铁、橡胶三种原料生产A、B两种产品，其有关资料见下表问该企业在下一周期内应如何安排生产计划，使得既能充分利用现有原料，又使总利润最大？（仅列出数学模型）,85,2.3. 某地区有3个矿山Al，A2，A3，生产同一种矿物。另外有4个这种矿物的消费地（铁厂）B1，B2，B3，B4。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表2-7所示。问：应如何调运，才使总运费最省？（仅列出数学模型）,86,2.4. 将如下的线性规划问题模型转化为标准形式,2.5将下列线性规划问题化为标准形,87,2.6用图解法求解,2.7. 用单纯形表法计算,88,2.8求解如下的线性规划问题,2.9用单纯形法(大M法)求解线性规划问题,