《人大经典讲义《运筹学》全套课件-PPT.ppt》由会员分享，可在线阅读，更多相关《人大经典讲义《运筹学》全套课件-PPT.ppt（564页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 运运 筹筹 学学 1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析 8.图与网络分析 1运运筹筹学学中国人民大学中国人民大学2010.102第一章 绪 论3运筹学概况简述运筹学概况简述运筹学(OperationsResearch)直译为“运作研究”。运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。4运筹学概况简述运筹学概况简述 运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，
2、避开最劣的方案。5运筹学在工商管理中的应用运筹学在工商管理中的应用生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。库存管理：多种物资库存量的管理，库存方式、库存量等。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。6运筹学在工商管理中的应用运筹学在工商管理中的应用人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。7运筹学在工商管理中的应用运筹学在工商管理中的应用 财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。其他：设备维修
3、、更新，项目选择、评价，工程优化设计与管理等。8运筹学的产生和发展运筹学的产生和发展l运筹学思想的出现可以追溯到很早“田忌齐王赛马”（对策论）、孙子兵法等都体现了优化的思想。l“OperationalResearch”这一名词最早出现在第二次世界大战期间美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的。9运筹学的产生和发展运筹学的产生和发展 战后这些研究成果被应用到生产、经济领域，并得到迅速发展有关理论和方法的研究、实践不断深入。1947年美国数学家丹捷格(G.B.Dantzig）提出了求解线性规划的有效方法单纯形法。10运筹学的产生和发展运筹学的产生和发展
4、数学对运筹学的作用是有关理论和方法的研究基础，是建立运筹学模型的工具。计算机的发展，促进运筹学的进一步发展高速、可靠的计算是运筹学解决问题的基本保障。11运筹学的分支运筹学的分支l线性规划l非线性规划l整数规划l动态规划l多目标规划l随机规划l模糊规划等12运筹学的分支运筹学的分支l图与网络理论l存储论l排队论l决策论l对策论l排序与统筹方法l可靠性理论等13运筹学方法使用情况运筹学方法使用情况(美美1983)1983)14 运筹学方法在中国使用情况运筹学方法在中国使用情况 (随机抽样随机抽样)15运筹学的推广应用前景运筹学的推广应用前景l 据美劳工局1992年统计预测:社会对运筹学应用分析人
5、员的需求从1990年到2005年，其增长百分比预测为73%,增长速度排到各项职业的前三位。16运筹学的推广应用前景运筹学的推广应用前景结论:-运筹学在国内或国外的推广应用前景是非常广阔的。-工商企业对运筹学应用的需求是很大的。-在工商企业推广运筹学方面有大量的工作要做。17运筹学解决问题的过程运筹学解决问题的过程 1）提出问题：认清问题。2）寻求可行方案：建模、求解。3）确定评估目标及方案的标准或方法、途径。4）评估各个方案：解的检验、灵敏性分析等。18运筹学解决问题的过程运筹学解决问题的过程 5）选择最优方案：决策。6）方案实施：回到实践中。7）后评估：考察问题是否得到完满解决。1）2）3）
6、形成问题；4）5）分析问题：定性分析与定量分析相结合，构成决策。19如何学习运筹学课程如何学习运筹学课程学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎么进行等。自学时要掌握三个重要环节：20如何学习运筹学课程如何学习运筹学课程 1.认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好。21 2.要在理解了基本概念和理论的基础上要在理解
7、了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、研究例题，注意例题是为了帮助理解概念、理论的。作业练习的主要作用也是这样，它理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会有内在联系，只要学到一定程度，知识融会贯通起来，你自己就能够对所做题目的正确贯通起来，你自己就能够对所做题目的正确性作出判断。性作出判断。如何学习运筹学课程如
8、何学习运筹学课程22 3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来概述该书所讲内容。这样，你才能够从较高的角度来看问题，更深刻地理解有关知识和内容。这就称作“把书读薄”，若能够结合相关参考文献并深入理解，把相关知识从更深入、广泛的角度进行论述，则称为“把书读厚”。如何学习运筹学课程如何学习运筹学课程23 第二章 线性规划建模及单纯形法本章内容重点w线性规划模型与解的主要概念w线性规划的单纯形法，线性规划多解分析w线性规划应用建模241.1.线性规划的概念线性规划的概念 例2.1:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，
9、每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）150015002500250025 问题：工厂应如何安排生产可获得最大的总利润？解：设变量 xi 为第 i 种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2 x2 65；对设备B：两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1+x2 40；1.1.线性规划
10、的概念线性规划的概念26 对设备C：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75；另外，产品数不可能为负，即 x1,x2 0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2 综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：1.1.线性规划的概念线性规划的概念27目标函数 Max z=1500 x1+2500 x2约束条件 s.t.3x1+2x2 65 2x1+x2 40 3x2 75 x1,x2 0 1.1.
11、线性规划的概念线性规划的概念28 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最 大 化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z 达到最大的x1,x2 的取值。1.1.线性规划的概念线性规划的概念29一般形式 目标函数：Max(Min)z=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2 .am1x1+am2x2+amnxn(=,)bm x1，x2，xn 01.1.线性规
12、划的概念线性规划的概念30标准形式目标函数：Max z=c1x1+c2x2+cnxn 约束条件：A11x1 +a12x2 +a1nxn=b1a21x1 +a22x2 +a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 01.1.线性规划的概念线性规划的概念31 可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1.1.线性规划的概念线性规划的概念32 1.极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z
13、 -f，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f -Max z1.1.线性规划的概念线性规划的概念33 2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi1.1.线性规划的概念线性规划的概念34
14、当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi 1.1.线性规划的概念线性规划的概念35 为了使约束由不等式成为等式而引进的变量 s 称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。1.1.线性规划的概念线性规划的概念36 例2.2：将以下线性规划问题转化为标准形式 Min f =3.6 x1-5.2 x2+1.8 x3 s.t.2.3 x1 +
15、5.2 x2-6.1 x3 15.7 4.1 x1 +3.3 x3 8.9 x1+x2+x3 =38 x1,x2,x3 0 1.1.线性规划的概念线性规划的概念 解：首先,将目标函数转换成极大化：令 z=-f=-3.6x1+5.2x2-1.8x3 37其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题：Max z=-3.6 x1+5.2 x2-1.8 x3s.t.2.3x1+5.2x2-6.1x3+x4=15.7 4.1x1+3.3x3-x5=8.9 x1+x2+x3=38 x1,x2,x3,x4,x5 01.1.线性规划的概念线性规划的概
16、念38 3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。1.1.线性规划的概念线性规划的概念39 4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bim，秩(A A)=m，b b Rm。在约束等式中，令n维空间的解向量：x x=(x1，x2，xn)T 2.2.线性规划解的概念线性规划解的概念 78 中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，
17、则这n个变量的值组成的向量x x就对应于n维空间Rn中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。根据以上分析，我们建立以下概念：（1）线性规划的基基：对于线性规划的约束条件 AxAx=b b，x x0 0 2.2.线性规划解的概念线性规划解的概念 79 设B B是A A矩阵中的一个非奇异（可逆）的mm子矩阵，则称B B为线性规划的一个基基。用前文的记号，A A=(p p1 1，p p2 2，p pn n)，其中 p pj j=(a1j，a2j，amj)T Rm，任取A A中的m个线性无关列向量 p pj j Rm 构成矩阵 B B=(p pj1
18、j1，p pj2 j2，p pjmjm)。那么B B为线性规划的一个基基。我们称对应于基B B的变量xj1，xj2，xjm为基基变变量量；而其他变量称为非非基基变量变量。2.2.线性规划解的概念线性规划解的概念 80 可以用矩阵来描述这些概念。设B B是线性规划的一个基，则A A可以表示为 A A=B,NB,N x x也可相应地分成 x xB B x x=x xN N 其中x xB为m维列向量，它的各分量称为基基变变量量，与基B B的列向量对应；x xN为n-m列向量，它的各分量称为非非基基变变量量，与非基矩阵N N的列向量对应。这时约束等式AxAx=b b可表示为 2.2.线性规划解的概念线
19、性规划解的概念 81 x xB B,N =b b x xN 或 BxBxB+NxNxN=b b 如果对非基变量x xN取确定的值，则xB有唯一的值与之对应 x xB=B B-1b b -B B-1NxNxN 特别，当取x xN=0 0，这时有x xB=B B-1b b。关于这类特别的解，有以下概念。2.2.线性规划解的概念线性规划解的概念 82 （2）线性规划问题的基本解基本解、基基本可行解本可行解和可行基可行基：对于线性规划问题，设矩阵B B=(p pj1j1，p pj2j2，p pjmjm)为一个基，令所有非基变量为零，可以得到m个关于基变量xj1，xj2，xjm的线性方程，解这个线性方程
20、组得到基变量的值。我们称这个解为一个基基本本解解；若得到的基变量的值均非负，则称为基基本本可可行解行解，同时称这个基B B为可行基可行基。2.2.线性规划解的概念线性规划解的概念 83 矩阵描述为，对于线性规划的解 x xB B B-1b b x x=x xN 0 称为线性规划与基B B对应的基本解。若其中B B-1b b0 0，则称以上的基本解为一基本可行解，相应的基B B称为可行基。2.2.线性规划解的概念线性规划解的概念 84 我们可以证明以下结论：线性规划的基本可行解就是可行域的极点。这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系
21、起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。2.2.线性规划解的概念线性规划解的概念 85 例2.9:考虑例2.8的线性规划模型 Max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3=65 2 x1+x2 +x4=40 3 x2+x5 =75 x1,x2,x3,x4,x5 0 注意，线性规划的基本解、基本可行 解（极点）和可行基只与线性规划问 题标准形式的约束条件有关。2.2.线性规划解的概念线性规划解的概念 86 3 2 1 0 0A A=P1,P2,P3,P4,P5P1,P2,P3,P4,P5=2 1 0 1
22、0 0 3 0 0 1 A A矩阵包含以下10个33的子矩阵：B B1 1=p p1 1，p p2 2，p p3 3 B B2 2=p p1 1，p p2 2，p p4 4 B B3 3=p p1 1，p p2 2，p p5 5 B B4 4=p p1 1，p p3 3，p p4 4 B B5 5=p p1 1，p p3 3，p p5 5 B B6 6=p p1 1，p p4 4，p p5 5 B B7 7=p p2 2，p p3 3，p p4 4 B B8 8=p p2 2，p p3 3，p p5 5 B B9 9=p p2 2，p p4 4，p p5 5 B B1010=p p3 3，p
23、p4 4，p p5 5 2.2.线性规划解的概念线性规划解的概念 87 其中B B4=0，因而B B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B B3=p p1 1，p p2 2，p p5 5，令非基变量x3 3=0，x4=0，在等式约束中令x3=0，x4=0，解线性方程组：3 x1+2 x2+0 x5 =65 2 x1+x2+0 x5 =40 0 x1+3 x2+x5 =75 得到x1=15，x2=10，x5=45，对应的基本可行解：x x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。于是对应的基B B3是一个可行基。2.2.线性规划解
24、的概念线性规划解的概念 88 类似可得到 x x(2)=(5,25,0,5,0)T （对应B B2）x x(7)=(20,0,5,0,75)T （对应B B5）x x(8)=(0,25,15,15,0)T（对应B B7）x x(9)=(0,0,65,40,75)T（对应B B10）是基本可行解；而x x(3)=(0,32.5,0,7.5,-22.5)T（对应B B9）x x(4)=(65/3,0,0,-10/3,75)T（对应B B6）x x(5)=(7.5,25,-7.5,0,0)T （对应B B1）x x(6)=(0,40,-15,0,-45)T （对应B B8）是基本解。2.2.线性规划
25、解的概念线性规划解的概念 89 因此，对应基本可行解（极点）的B B2 B B3 B B5 B B7 B B10都是可行基。这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。2.2.线性规划解的概念线性规划解的概念 90 利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值
26、差。3.3.单单 纯纯 形形 法法91 由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加，而其他非基变量的值都保持0不变。3.3.单单 纯纯 形形 法法923.3.单单 纯纯 形形 法法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解?结束结束沿边界找新沿边界找新的基本可行解的
27、基本可行解NY单纯形法的基本过程93考虑标准形式的线性规划问题：Max z=c1x1+c2x2+cnxn s.t.a11 x1+a12 x2+a1n xn=b1 a21 x1+a22 x2+a2n xn=b2 .am1 x1+am2 x2+amn xn=bm x1,x2,xn 0 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx x=.C C=.B B=.A A=.xn cn bn am1 am2.amn 3.3.单单 纯纯 形形 法法94这里，矩阵A A表示为：A A=(p p1 1，p p2 2，p pn n)，其中 p pj j=(a a1j 1j，a
28、 a2j 2j，a amjmj)T Rm。若找到一个可行基，无防设B B=(p p1 1，p p2 2，p pm m)，则m个基变量为 x1,x2,xm，n-m个非基变量为 xm+1，xm+2，xn。通过运算，所有的基变量都可以用非基变量来表示：3.3.单单 纯纯 形形 法法953.3.单单 纯纯 形形 法法 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn）x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）(2-11).xm=bm-（amm+1xm+1+amm+2xm+2+amnxn）把它们代入目标函数，得 z=z+m+1xm+1+m+2xm+2+nxn (2
29、-12)其中 j=cj-（c1a1j+c2a2j+cm amj）我们把由非基变量表示的目标函数形式称为基B B相应的目标函数典式典式。96单纯形法的基本步骤可描述如下：（1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示；3.3.单单 纯纯 形形 法法97 （2）在用非基变量表示的目标函数表达式（2-12）中，我们称非基变量xj的系数（或其负值）为检验数记为 j。若 j 0，那么相应的非基变量xj，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转
30、（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有 j 非正，则当前的基本可行解就是最优解，计算结束；3.3.单单 纯纯 形形 法法98 （3）在用非基变量表示的基变量的表达式（2-11）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr，满足，=minbi/aij aij 0=br/arj这个基变量xr称为“出基变量”。当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。3.3.单单 纯纯 形形 法法99如果进基变量的值增加时，所有基变量的值都不减少，即所有aij 非正，则表示可
31、行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。3.3.单单 纯纯 形形 法法100 例2.10：用单纯形法的基本思路解例2.8的线性规划问题 Max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3=65 2 x1+x2 +x4=40 3 x2+x5 =75 x1,x2,x3,x4,x5 03.3.单单 纯纯 形形 法法101第一次迭代：（1）取初始可行基B B10=(p p3 3,p
32、p4 4,p p5 5)，那么x3，x4，x5为基变量，x1，x2为非基变量。将基变量和目标函数用非基变量表示：z z=1500 x1+2500 x2 x3=65-3 x1-2 x2 x4=40-2 x1-x2 x5=75-3 x2当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5=75，z=0，得到当前的基本可行解：x x=(0,0,65,40,75)T，z=0。这个解对应于图2-7的D、E交点。3.3.单单 纯纯 形形 法法102 （2）选择进基变量。在目标函数z z=1500 x1+2500 x2中，非基变量x1，x2的系数都是正数，因此 x1，x2进基都
33、可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2的值从0开始增加，另一个非基变量x1保持零值不变。3.3.单单 纯纯 形形 法法103 （3）确定出基变量。在约束条件 x3=65-3 x1-2 x2 x4=40-2 x1-x2 x5=75-3 x2中，由于进基变量x2在3个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3、x4、x5的值分别从当前的值65、40和75开始减少，当x2增加到25时，x5首先下降为0成为非基变量。这时，新的基变量为x3、x4、x2，新的非基变量为x1、
34、x5，当前的基本可行解和目标函数值为：x x=(0，25，15，15，0)T，z=62500。这个解对应于图中的C、D交点。3.3.单单 纯纯 形形 法法104第二次迭代：（1）当前的可行基为B B7=(p p2 2,p p3 3,p p4 4)，那么x2，x3，x4为基变量，x1，x5为非基变量。将基变量和目标函数用非基变量表示：z=62500+1500 x1 (2500/3)x5 x2=25 (1/3)x5x3=15-3 x1+(2/3)x5 x4=15-2 x1+(1/3)x5 3.3.单单 纯纯 形形 法法105 （2）选择进基变量。在目标函数z=62500+1500 x1 (2500
35、/3)x5 中，非基变量x1的系数是正数，因此 x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加,另一个非基变量x5保持零值不变。(3)确定出基变量。在约束条件 x2=25 (1/3)x5x3=15-3 x1+(2/3)x5 x4=15-2 x1+(1/3)x53.3.单单 纯纯 形形 法法106中，由于进基变量x1在两个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。这时，新的基变量为x1、x2、x4，新的非基变量为x3、x5，当前的基本可行解和目标函数值为：x x
36、=(5，25，0，5，0)T，z=70000。这个解对应于图中的A、C交点。3.3.单单 纯纯 形形 法法107第三次迭代：（1）当前的可行基为B B2=(p p1 1,p p2 2,p p4 4)，那么x1，x2，x4为基变量，x3，x5为非基变量。将基变量和目标函数用非基变量表示：z=70000 500 x3 500 x5x1=5 (1/3)x3+(2/9)x5 x2=25 (1/3)x5x4=5+(2/3)x3 (1/9)x5 3.3.单单 纯纯 形形 法法108 （2）选择进基变量。在目标函数z=70000 500 x3 500 x5 中，非基变量x3、x5的系数均不是正数，因此进基都
37、不可能使目标函数z增大，于是得到最优解，x x*=(5，25，0，5，0)T，最优目标值为z*=70000。这个解对应于图2-7的A、C交点。我们也称相应的基B B2=(p p1 1,p p2 2,p p4 4)为最最优优基基。计算结束。3.3.单单 纯纯 形形 法法1093 3、单单 纯纯 形形 法法l表格单纯形法表格单纯形法l考虑：考虑：bi0i=1,mMaxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbm x1，x2，xn01103 3、单单 纯纯 形形 法法l加入松弛变量：加入松弛
38、变量：Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bm x1，x2，xn，xn+1，xn+m0111显然，显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解对应的基是单位矩阵。以下是初始单纯形表：mm其中：f=-cn+ibij=cj-cn+iaij为检验数cn+i=0i=1,mi=1i=1an+i,i=1,an+i,j=0(ji)i,j=1,m3 3、单单 纯纯 形形 法法1123 3、单单 纯纯 形形 法法 例例2.10。化标准形式：
39、。化标准形式：Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=70000113l注意：单纯形法中，注意：单纯形法中，1、每一步运算只能用矩阵初等、每一步运算只能用矩阵初等行变换；行变换；2、表中第、表中第3列的数总应保持非负列的数总应保持非负（0）；）；3、当所有检验数均非正（、当所有检验数均非正（0）时，得到最优单纯形表。时，得到最优单纯形表。3 3、线线 性性 规规 划划 114 一般情况的处理及注意事项的强调
40、：主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。考虑一般问题：bi 0 i=1,m3.3.单单 纯纯 形形 法法115Max z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn =bm x1，x2，xn 03.3.单单 纯纯 形形 法法116大大M M法：法：引入人工变量 xn+i 0（i=1,m）及充分大正数 M。得到：Max Max z=c1x1+c2x2+cnxn-Mxn+1-Mxn+m s.t.s.t.a1
41、1 x1+a12 x2+a1n xn+xn+1 =b1 a21 x1+a22 x2+a2n xn+xn+2 =b2 .am1 x1+am2 x2+amn xn+xn+m =bm x1，x2，xn ，xn+1，xn+m 0 03.3.单单 纯纯 形形 法法117显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足 xn+i=0 i=1,m 则是原问题的最优解；否则，原问题无可行解。3.3.单单 纯纯 形形 法法118l 两阶段法：l 引入人工变量 xn+i 0，i=1,m；l 构造:Max z=-xn+1-xn+2-xn+m s.t.
42、a11x1+a12x2+a1nxn+xn+1=b1 a21x1+a22x2+a2nxn+xn+2=b2 .am1x1+am2x2+amnxn+xn+m=bm x1,x2.xn,xn+1,xn+m 03.3.单单 纯纯 形形 法法119 第一阶段求解上述问题：显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行解,它对应的基 是单位矩阵。结论：若得到的最优解满足 xn+i=0 i=1,m 则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。3.3.单单 纯纯 形形 法法120例2.11：（LP）Max z=5x1+2x2+3x3-x4 s.t
43、.x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4 03.3.单单 纯纯 形形 法法121 Max z=5x1+2x2+3x3-x4-Mx5-Mx6 s.t.x1+2x2+3x3+x5=15 2x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4,x5,x6 03.3.单单 纯纯 形形 法法122大大M M法法 （LP-M）得到最优解：(25/3，10/3，0，11)T 最优目标值：112/33.3.单单 纯纯 形形 法法123 第一阶段问题（LP-1）Max z=-x5-x6 s.t.x1
44、+2x2+3x3+x5 =15 2x1+x2+5x3+x6=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4,x5,x6 03.3.单单 纯纯 形形 法法124第一阶段第一阶段 (LP-1）得到原问题的基本可行解:(0，15/7，25/7，52/7)T 3.3.单单 纯纯 形形 法法125第二阶段第二阶段 把基本可行解填入表中得到原问题的最优解:(25/3，10/3，0，11)T 最优目标值：112/33.3.单单 纯纯 形形 法法126 注意：单纯形法中 1、每一步运算只能用矩阵初等行变换；2、表中第3列(b列)的数总应保持非负（0）；3、当所有检验数均非正（0）时，得到最
45、优单纯形表。若直接对目标求最h，要求所有检验数均非负；4、当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；3.3.单单 纯纯 形形 法法127 5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xBi=0(i=1,2,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。3.3.单单 纯纯 形形 法法128 可能出现以下情况：进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行
46、若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。3.3.单单 纯纯 形形 法法129 在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wol
47、fe又提出了“字典序法”，3.3.单单 纯纯 形形 法法130 这些方法都比较复杂，同时也降低了迭代的速度。1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定：在选择进基变量时，在所有 j 0的非基变量中选取下标最小的进基；当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。3.3.单单 纯纯 形形 法法131 合理利用线材问题：合理利用线材问题：如何下如何下料使用材最少。料使用材最少。配料问题：配料问题：在原料供应量的在原料供应量的限制下如何获取最大利润。限制下如何获取最大
48、利润。投资问题：投资问题：从投资项目中选从投资项目中选取方案，使投资回报最大。取方案，使投资回报最大。4.4.线性规划应用线性规划应用 一、线性规划一、线性规划-132 产品生产计划：产品生产计划：合理利用人合理利用人力、物力、财力等，使获利最力、物力、财力等，使获利最大。大。劳动力安排：劳动力安排：用最少的劳动用最少的劳动力来满足工作的需要。力来满足工作的需要。运输问题：运输问题：如何制定调运方如何制定调运方案，使总运费最小。案，使总运费最小。4.4.线性规划应用线性规划应用133 数学规划的建模有许多共同点，要遵循下列原则：(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解
49、。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。4.4.线性规划应用线性规划应用134 (3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。4.4.线性规划应用线性规划应用135 建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量；(2)明确约束条件并用决策变量的线性等式或不等式表示；(3)用决策变量的线性函数表示目标，并确定是求极大（Ma
50、x）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性。4.4.线性规划应用线性规划应用136 例2.12：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：人力资源分配的问题人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?137 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：目标函数：Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 约束条件：约束条件：s.t