运筹学全册配套最完整精品课件2.ppt

1、运筹学全册配套最完整运筹学全册配套最完整 精品课件精品课件2 2 2 运筹学运筹学（第三版）（本科版）（第三版）（本科版） 教学课件教学课件 清华大学出版社 3 运筹学运筹学（第三版）（本科版）（第三版）（本科版）教学课件教学课件 清华大学出版社 4 一、绪论 n第1节 运筹学的简史 n第2节 运筹学的性质和特点 n第3节 运筹学的工作步骤 n第4节 运筹学的模型 n第5节 运筹学的应用 n第6节 运筹学的展望 清华大学出版社 5 运筹学运筹学（第三版）（本科版）（第三版）（本科版） 教学课件教学课件 清华大学出版社 6 第1节 运筹学的简史 v运筹学作为科学名字出现在20世纪30年代末。 v

2、第二次世界大战后，20世纪发展概况。 v在20世纪50年代中期钱学森、许国志等教授将运筹学由西 方引入我国，并结合我国的特点在国内推广应用。在此期 间以华罗庚教授为首的一大批数学家加入到运筹学的研究 队伍，使运筹数学的很多分支很快跟上当时的国际水平 v1959年，运筹学部门在中国科学院数学研究所成立，力学 所小组与数学所的小组于1960年合并成为数学研究所的一 个研究室，当时的主要研究方向为排队论、非线性规划和 图论，还有人专门研究运输理论、动态规划和经济分析 （例如投入产出方法）。在当时这些先遣者中，越民义先 生、刘源张院士、朱永津教授、桂湘云教授、陈锡康教授、 徐光煇教授、韩继业教授、李秉

3、全教授、郭绍僖教授等。 清华大学出版社 7 第2节 运筹学的性质和特点 v运筹学是一门应用科学，至今还没有统一且 确切的定义。 v莫斯(P.M.Morse)和金博尔(G.E.Kimball)曾对 运筹学下的定义是：“为决策机构在对其控 制下业务活动进行决策时，提供以数量化为 基础的科学方法。” v另一定义是：“运筹学是一门应用科学，它 广泛应用现有的科学技术知识和数学方法， 解决实际中提出的专门问题，为决策者选择 最优决策提供定量依据。” 清华大学出版社 8 前英国运筹学学会会长托姆林森提出六条原则 v(1) 合伙原则。是指运筹学工作者要和各方面人，尤 其是同实际部门工作者合作。 v(2) 催

4、化原则。在多学科共同解决某问题时，要引导 人们改变一些常规的看法。 v(3) 互相渗透原则。要求多部门彼此渗透地考虑问题， 而不是只局限于本部门。 v(4) 独立原则。在研究问题时，不应受某人或某部门 的特殊政策所左右，应独立从事工作。 v(5) 宽容原则。解决问题的思路要宽，方法要多，而 不是局限于某种特定的方法。 v(6) 平衡原则。要考虑各种矛盾的平衡，关系的平衡。 清华大学出版社 9 第3节 运筹学的工作步骤 v(1) 提出和形成问题。即要弄清问题的目标，可 能的约束，问题的可控变量以及有关参数，搜集 有关资料； v(2) 建立模型。即把问题中可控变量、参数和目 标与约束之间的关系用一

5、定的模型表示出来； v(3) 求解。用各种手段(主要是数学方法，也可 用其他方法)将模型求解。解可以是最优解、次 优解、满意解。复杂模型的求解需用计算机，解 的精度要求可由决策者提出； 清华大学出版社 10 v(4) 解的检验。首先检查求解步骤和程序有无 错误，然后检查解是否反映现实问题； v(5) 解的控制。通过控制解的变化过程决定对 解是否要作一定的改变； v(6) 解的实施。是指将解用到实际中必须考虑 到实施的问题，如向实际部门讲清解的用法， 在实施中可能产生的问题和修改。 v以上过程应反复进行。 第3节 运筹学的工作步骤 清华大学出版社 11 第4节 运筹学的模型 模型有三种基本形式：

6、 v形象模型； v模拟模型； v符号或数学模型。 清华大学出版社 12 构模的方法和思路有以下五种： v(1) 直接分析法 v(2) 类比法 v(3) 数据分析法 v(4) 试验分析法 v(5) 想定(构想)法(scenario) 清华大学出版社 13 模型的一般数学形式可用下列表达式描述： v目标的评价准则 U=f(xi,yj,k) v约束条件 g(xi,yj,k)0 v其中：xi可控变量； yj已知参数； k随机因素。 清华大学出版社 14 第5节 运筹学的应用 v(1) 市场销售 v(2) 生产计划 v(3) 库存管理 v(4) 运输问题 v(5) 财政和会计 v(6) 人事管理 v(7

7、) 设备维修、更新和可靠性、项目选择和评价 清华大学出版社 15 第5节 运筹学的应用 v(8) 工程的优化设计 v(9) 计算机和信息系统 v(10) 城市管理 v(11)军事 v(12)其他 清华大学出版社 16 第6节 运筹学的展望 美国前运筹学会主席邦特(S.Bonder)认为， 运筹学应在三个领域发展： v运筹学应用 v运筹科学 v运筹数学。 清华大学出版社 17 近几年来出现一种新的批评 v指出有些人只迷恋于数学模型的精巧、 复杂化，使用高深的数学工具，而不善 于处理面临大量新的不易解决的实际问 题。现代运筹学工作者面临的大量新问 题是经济、技术、社会、生态和政治等 因素交叉在一起

8、的复杂系统。 清华大学出版社 18 非数学的方法和理论引入运筹学 v在运筹学中除常用的数学方法以外，还引入 一些非数学方法和理论。 v美国运筹学家沙旦(T.L.Saaty)，在20世纪70 年代末提出了层次分析法(AHP)。 v切克兰特(P.B.Checkland)把传统的运筹学方 法称为硬系统思考，它适用于解决那种结构 明确的系统以及战术和技术性问题，而对于 结构不明确的，有人参与活动的系统就不太 胜任了。这就应采用软系统思考方法。 清华大学出版社 19 解的概念变化 v相应的一些概念和方法都应有所变化， 如将过分理想化的“最优解”换成“满 意解”。过去把求得的“解”看作精确 的、不能变的凝

9、固的东西，而现在要以 “易变性”的理念看待所得的“解”以 适应系统的不断变化 。 清华大学出版社 20 两个很重要的趋势 v一个趋势是软运筹学崛起。 v一个趋势是与优化有关的，即软计算。 这种方法不追求严格最优，具有启发式 思路。 清华大学出版社 21 二、线性规划与目标规划 n第1章 线性规划与单纯形法 n第2章 对偶理论与灵敏度分析 n第3章 运输问题 n第4章 目标规划 清华大学出版社 22 第1章 线性规划与单纯形法线性规划与单纯形法 n第1节 线性规划问题及其数学模型 n第2节 线性规划问题的几何意义 n第3节 单纯形法 n第4节 单纯形法的计算步骤 n第5节 单纯形法的进一步讨论

10、n第6节 应用举例 清华大学出版社 23 第1节 线性规划问题及其数学模型 v1.1 问题的提出 v1.2 图解法 v1.3 线性规划问题的标准形式 v1.4 线性规划问题的解的概念 清华大学出版社 24 第1节 线性规划问题及其数学模型 线性规划是运筹学的一个重要分支。线性规划在理线性规划是运筹学的一个重要分支。线性规划在理 论上比较成熟，在实用中的应用日益广泛与深入。特别论上比较成熟，在实用中的应用日益广泛与深入。特别 是在电子计算机能处理成千上万个约束条件和决策变量是在电子计算机能处理成千上万个约束条件和决策变量 的线性规划问题之后，线性规划的适用领域更为广泛了。的线性规划问题之后，线性

11、规划的适用领域更为广泛了。 从解决技术问题的最优化设计到工业、农业、商业、交从解决技术问题的最优化设计到工业、农业、商业、交 通运输业、军事、经济计划和管理决策等领域都可以发通运输业、军事、经济计划和管理决策等领域都可以发 挥作用。它已是现代科学管理的重要手段之一。解线性挥作用。它已是现代科学管理的重要手段之一。解线性 规划问题的方法有多种，以下仅介绍规划问题的方法有多种，以下仅介绍单纯形法单纯形法 。 清华大学出版社 25 1.1 问题的提出 1.1 1.1 问题的提出问题的提出 例例 1 某工厂在计划期内要安排生产、两种产品，已知 生产单位产品所需的设备台时及A、B两种原材料的消耗， 如表

12、1-1所示。 资源 产 品 拥有量 设 备1 2 8台时 原材料 A 40 16 kg 原材料 B04 12 kg 每生产一件产品每生产一件产品可获利可获利2 2元，每生产一件产品元，每生产一件产品可获利可获利 3 3元，问应如何安排计划使该工厂获利最多元，问应如何安排计划使该工厂获利最多? ? 清华大学出版社 26 1.1 问题的提出 称它们为决策变量。 产品的数量，分别表示计划生产设III, 21 xx 12416482 2121 21 x;x;xx ,x ,x 这是约束条件。即 有量的限制的数量多少，受资源拥生产 0 21 x,x,即生产的产品不能是负值 这是目标。最大如何安排生产，使利

13、润, 用数学关系式描述这个问题用数学关系式描述这个问题 清华大学出版社 27 1.1 问题的提出 0 124 164 82 32 21 2 1 21 21 x ,x x x xx : xxzmax 约束条件 目标函数 得到本问题的数学模型为: 这就是一个最简单的线性规划模型。这就是一个最简单的线性规划模型。 清华大学出版社 28 1.1 问题的提出 例例 2 靠近某河流有两个化工厂 (见图1-1)，流经第一化工厂的 河流流量为每天500万立方米， 在两个工厂之间有一条流量为 每天200万立方米的支流。 图1-1 化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天 排放的工业污水

14、为1.4万立方米。从化工厂1排出的污水流到化工厂2前， 有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于 0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本 是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问: 在满足环保要求的条件下，每厂各应处理多少工业污水，在满足环保要求的条件下，每厂各应处理多少工业污水， 使两个工厂处理工业污水的总费用最小。使两个工厂处理工业污水的总费用最小。 清华大学出版社 29 1.1 问题的提出 设设： 化工厂1每天处理的污水量为x1万立方米； 化工厂2每天处理的污水量为x2万立方米 1000 2 700 412

15、80 2 1000 2 500 2 2 21 1 )x.()x(. )x( 工厂后的水质要求：经第 工厂前的水质要求：经第 建模型之前的分析和计算 清华大学出版社 30 1.1 问题的提出 0, 4 . 1 2 6 . 18 . 0 1 8001000min 21 2 1 21 1 21 xx x x xx x xxz 约束条件 目标函数 得到本问题的数学模型为： 清华大学出版社 31 1.1 问题的提出 l每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。 一般这些变量的取值是非负且连续的； l都有关于各种资源和资源使用情况的技术数据，创造新 价值的数据；

16、l存在可以量化的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示; l都有一个达到某一目标的要求，可用决策变量的线性函 数(称为目标函数)来表示。按问题的要求不同，要求目 标函数实现最大化或最小化。 n x,x,x 21 )n,j;m,i (c;a jij 11 上述两个问题具有的共同特征：上述两个问题具有的共同特征： 清华大学出版社 32 1.1 问题的提出 n mmnmm n n n cc b b b aaa aaa aaa m xxx 21 2 1 21 22221 11211 21 c 2 1 价值系数 动 活 资源 决策变量 决策变量及各类系数之间的对应关系 清华大学出版

17、社 33 1.1 问题的提出 ).(x,x ,x b),(xaxaxa ).( b),(xaxaxa b),(xaxaxa ).(xcxcxczmax(min) n mnmmm nn nn nn 310 21 11 21 2211 22222121 11212111 2211 约束条件 目标函数 线性规划模型的一般形式 清华大学出版社 34 1.2 图解法 1.2 1.2 图解法图解法 例1是一个二维线性规划问题，因而可用作图法直观地进行求 解。 0, 124 164 82 32max 21 2 1 21 21 xx x x xx xxz 清华大学出版社 35 1.2 图解法 表示一簇平行线

18、33 2 12 z xx 21 32xxzmax 目标值在（4，2）点，达到最大值14 清华大学出版社 36 1.2 图解法 （1）无穷多最优解(多重最优解)，见图1-4。 （2）无界解，见图1-5-1。 （3）无可行解，见图1-5-2。 通过图解法，可观察到线性规划的解可能出现 的几种情况： 清华大学出版社 37 1.2 图解法 目标函数 max z=2x1+4x2 图1-4 无穷多最优解（多重最优解） 清华大学出版社 38 1.2 图解法 ox ,x xx xx xxzmax 21 21 1 21 2 42 图1-5-1 无界解 清华大学出版社 39 当存在相互矛盾的约束条件时，线性规划问

19、题的可 行域为空集。例如，如果在例1的数学模型中增加一 个约束条件: 则该问题的可行域即为空集空集，即无可行解， 85 . 1 21 xx 无可行解的情形 1.2 图解法 清华大学出版社 40 85 . 1 21 xx 增加的约束条件 图1-5-2 不存在可行域 1.2 图解法 清华大学出版社 41 1.3 线性规划问题的标准型式 0 a czmax 21 2211 22222121 11212111 2211 1 n nnmnmm nn nn nn x ,x ,x bxaxaxa bxaxaxa bxaxax xcxcx :M 约束条件： 目标函数： 1.3 线性规划问题的标准型式线性规划问

20、题的标准型式 清华大学出版社 42 1.3 线性规划问题的标准型式 n,j; b b b b; a a a P; x x x X ;c,c,cC n,j,x bxP CXzmax:M m mj j j j n n j n j jj 21 210 2 1 2 1 2 1 21 1 1 约束条件： 目标函数： 用向量形式表示的标准形式线性规划 线性规划问题的几种表示形式 清华大学出版社 43 1.3 线性规划问题的标准型式 用矩阵形式表示的标准形式线性规划用矩阵形式表示的标准形式线性规划 T n n mnm n x,x,xX ;P,P,P aa aa A X bAX CXzmax:M 21 m 1

21、 21 1 111 1 b b b 0 0 0 0 决策变量向量： ；资源向量：零向量： 系数矩阵： 约束条件： 目标函数： 清华大学出版社 44 1.3 线性规划问题的标准型式 kkk xxx (1) 若要求目标函数实现最小化，即min z =CX，则只需将目标函数最小 化变换求目标函数最大化，即令z= z，于是得到max z= CX。 (2) 约束条件为不等式。分两种情况讨论： l若约束条件为“”型不等式，则可在不等式左端加入非负松弛变 量，把原“”型不等式变为等式约束； l若约束条件为“”型不等式，则可在不等式左端减去一个非负剩 余变量(也称松弛变量)，把不等式约束条件变为等式约束。 (

22、3) 若存在取值无约束的变量xk,可令 0, kk xx 如何将一般线性规划转化为标准形式的线性规划如何将一般线性规划转化为标准形式的线性规划 清华大学出版社 45 1.3 线性规划问题的标准型式 例例3 将例1的数学模型化为标准形式的线性规划。 例1的数学模型在加入了松驰变量后变为 1212345 12312 141 252 121234 max23max23000 2828 416416 412412 ,0,0 zxxzxxxxx xxxxx xxx xxx x xx x x x x 清华大学出版社 46 1.3 线性规划问题的标准型式 例例4 将下述线性规划问题化为标准形式线性规划 为无

23、约束 321 321 321 321 321 0 53 3 7 32 x;x ,x xxx xxx xxx xxxzmin (1) 用x4x5替换x3，其中x4，x50； (2) 在第一个约束不等式左端加入松弛变量x6； (3) 在第二个约束不等式左端减去剩余变量x7； (4) 令z= z，将求min z 改为求max z 即可得到该问题的标准型。 清华大学出版社 47 1.3 线性规划问题的标准型式 例例4 例4的标准型 0, 5)(23 2)( 7)( 00)(32max 765421 421 75421 65421 765421 xxxxxx xxxx xxxxx xxxxx xxxxx

24、xz 清华大学出版社 48 1.4 线性规划问题的解概念 v1.可行解(Feasible Solution) v2.基(Basic) v3.基可行解(Basic Feasible Solution, BF) v4.可行基(Feasible Basis) 清华大学出版社 49 1.4 线性规划问题的解的概念 v定义 满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T， 称为线性规划问题的可行解，其中使目标函数达到最 大值的可行解可行解称为最优解最优解。 )(n ,j,x )(m,i ,bxa )(xczmax j n j ijij n j jj 61210 5121 41 1 1

25、 1. 可行解可行解 清华大学出版社 50 1.4 线性规划问题的解的概念 为基变量。 为基向量， 为线性规划问题的基。称 阶非奇异子矩阵中的是系数矩阵 ), 2 , 1(x ), 2 , 1(P , B 0BA j j 21 21 22221 11211 mj mj PPP aaa aaa aaa B mmB m mmmm m m 2. 基，基向量，基变量基，基向量，基变量 清华大学出版社 51 1.4 线性规划问题的解的概念 是基可行解 4321 0Q,Q,Q,Q, 满足非负条件（1-6）的基解，称为基可行解. 基可行解的非 零分量的数目不大于m，并且都是非负的。 3 基可行解基可行解 清

26、华大学出版社 52 1.4 线性规划问题的解的概念 l 对应于基可行解的基，称为可行基。 l 约束方程组(1-5)具有的基解的数目最多是 个，一般 基可行解的数目要小于基解的数目。 l 以上提到了几种解的概念，它们之间的关系可用图1-6 表明。 l 说明：当基解中的非零分量的个数小于m时，该基解是退化解。 在以下讨论时，假设不出现退化的情况。 m n C 4 可行基可行基 清华大学出版社 53 1.4 线性规划问题的解的概念 m n C 不同解之间的关系不同解之间的关系 清华大学出版社 54 第2节 线性规划问题的几何意义 v2.1 基本概念 v2.2 几个定理 清华大学出版社 55 2.1

27、基本概念 1. 凸集 2. 凸组合 3. 顶点 清华大学出版社 56 2.1 基本概念 v定义 设K是n维欧氏空间的一点集，若任意两点X(1)K， X(2)K的连线上的所有点X(1)+(1)X(2)K，(01)， 则称K为凸集。 图1-7 1.凸集凸集 清华大学出版社 57 2.1 基本概念 v实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。 从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7 中的(a)(b)是凸集，(c)不是凸集。 v图1-2中的阴影部分是凸集。 v任何两个凸集的交集是凸集，见图1-7(d) 清华大学出版社 58 2.1 基本概念 v设X(1)，X(2)，X(k)

28、是n维欧氏空间En中的k个点。若存 在1，2，k，且0i1, i=1,2,，k 使 X=1X(1)+2X(2)+kX(k) 则称X为X(1)，X(2)，X(k)的一个凸组合（当0i1时， 称为严格凸组合）。 k i i 1 1 2. 凸组合凸组合 清华大学出版社 59 2.1 基本概念 v设K是凸集，XK；若X不能用不同的两点X(1)K和 X(2)K的线性组合表示为 X=X(1)+(1)X(2)，(01) 则称X为K的一个顶点(或极点)。 图中的0，Q1,2,3,4都是顶点。 3. 顶点顶点 清华大学出版社 60 2.2 几个定理 v定理定理1 : 若线性规划问题存在可行域，则其可行域 是凸集

29、。 n j jjj xbxPXD 1 0, 清华大学出版社 61 2.2 几个定理 v定理1的证明：只需证明D中任意两点连线上的点必然在D内即可。设 是D内的任意两点；且X(1)X(2)。 T n T n xxxX xxxX 22 2 2 1 2 11 2 1 1 1 , , 则有 n j jjj n j jjj njxbxP njxbxP 1 22 1 11 , 2 , 1, 0, , 2 , 1, 0, 令 X=(x1，x2，xn) T 为 x (1),x(2)连线上的任意一点，即 X=X (1)+(1-)X(2) (01) X 的每一个分量是 21 )1 ( jjj xxx，将它代入约束

30、条件， 得到 清华大学出版社 62 2.2 几个定理 bbbb xPxPxP xxPxP n j n j jjjj n j jj n j n j jjjjj 11 22 1 1 11 21 1 又因 01 , 0, 0, 21 jj xx ，所以 xj0，j=1,2,n。 由此可见 XD，D 是凸集。 证毕。 清华大学出版社 63 2.2 几个定理 v引理引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行 解的充要条件是：X的正分量所对应的系数列向量是线 性独立的。 证证: : (1) 必要性由基可行解的定义可知。 (2) 充分性若向量P1，P2，Pk线性独立， 则必有 km；

31、当 k=m 时，它们恰构成一个基，从而 X=(x1,x2,xk,00)为相应的基可行解。当 km 时， 则一定可以从其余的列向量中取出 m-k 个与 P1，P2，Pk 构成最大的线性独立向量组，其对应的解恰为 X， 所以根据定义它是基可行解。 清华大学出版社 64 2.2 几个定理 定理定理2 线性规划问题的基可行解X对应于可行域D的顶点。 证：证：不失一般性，假设基可行解X的前m个分量为正。 故 现分两步来讨论，分别用反证法。 m j jj bxP 1 清华大学出版社 65 2.2 几个定理 (1) 若X不是基可行解，则它一定不是可行域D的顶点。 根据引理1，若X不是基可行解，则其正分量所对

32、应的系数 列向量P1，P2，Pm线性相关，即存在一组不全为零的 数i,i=1,2,m，使得 1P1+2P2+mPm=0 (1-9) 用一个数0乘(1-9)式再分别与(1-8)式相加和相减，得 (x11)P1+(x22)P2+(xm m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b 清华大学出版社 66 2.2 几个定理 因X 不是可行域D的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1) X(2) ， 01 设X是基可行解，对应的向量组P1Pm线性独立，故当

33、jm时，有 xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的两点，因而满足 m j m j jjjj bxPbxP 11 21 与 （2）若X不是可行域D的顶点，则它一定不是基可行解。 m j jjj xxP 1 21 0 将两式相减，得 因X(1)X(2)，所以上式中的系数不全为零，故向量组P1,P2,，Pm线 性相关，与假设矛盾，即X不是基可行解。 清华大学出版社 67 2.2 几个定理 v引理引理2 若K是有界凸集，则 任何一点XK可表示为K的 顶点的凸组合。 本引理的证明从略，用以下例 子说明本引理的结论。 v例例5 设X是三角形中任意一 点，X(1)，X(2)和X(

34、3)是三角形 的三个顶点，试用三个顶点 的坐标表示X(见图1-8) 图1-8 清华大学出版社 68 2.2 几个定理 解：解：任选一顶点X(2)，做一条连线XX(2)，并延长交于X(1)、X(3)连接线上 一点X。因为X是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示 为 X=X(1)+(1)X(3) 01 又因X是X与X(2)连线上的一个点，故 X=X+(1 )X(2) 01 将X的表达式代入上式得到 X=X(1)+(1)X(3)+(1)X(2) =X(1)+(1 )X(3)+(1)X(2) 令 1=,2=(1 ),3=(1 )，得到 X=1X(1)+2X(2)+3X(3

35、) ii=1, 0i1 清华大学出版社 69 2.2 几个定理 v定理定理 3 若可行域有界，则线性规划问题的目标函数 一定可以在其可行域的顶点上达到最优。 证：证： 设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是 顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是 z=max z)。 因X(0)不是顶点，所以它可以用D的顶点线性表示为 代入目标函数得 k i k i ii i iix X 11 0 1, 0, k i k i i i i i CXXCCX 11 0 清华大学出版社 70 2.2 几个定理 在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有

36、 CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，得到 m k i m i k i i i CXCXCX 11 由此得到 X(0)CX(m) 根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m) 即目标函数在顶点X(m)处也达到最大值。 清华大学出版社 71 2.2 几个定理 1 X， 2 X， k X k i k i ii i i XX 11 1, 0, 有时，目标函数可能在多个顶点处达到最大，这时在这些顶点 的凸组合上也达到最大值，这时线性规划问题有无限多个最优 解。 假设 是目标函数达到最大值的顶点，则对这些顶点的凸组合，有 k i i i k i i i

37、 XCXCXC 11 清华大学出版社 72 2.2 几个定理 kimXC i , 2 , 1, 设： 于是： 另外，若可行域为无界，则可能无最优解，也可能有最优解， 若有最优解，也必定在某顶点上得到。 mmXC k i i 1 清华大学出版社 73 基本结论 l线性规划问题的所有可行解构成的集合是凸集，也可能为无 界域，它们有有限个顶点，线性规划问题的每个基可行解对应 可行域的一个顶点。 l若线性规划问题有最优解，必在某顶点上得到。虽然顶点数 目是有限的，若采用“枚举法”找所有基可行解，然后一一比 较，最终必然能找到最优解。但当n,m较大时，这种办法是行 不通的，所以要继续讨论如何有效寻找最优

38、解的方法。本课程 将主要介绍单纯形法单纯形法(simplex method)。 l备注：单纯形备注：单纯形(单纯形是指单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的点，一维中的线段，二维中的三角形，三 维中的四面体，维中的四面体，n维空间中的有维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，个顶点的多面体。例如在三维空间中的四面体， 其顶点分别为其顶点分别为(0,0,0)，(1,0,0)，(0,1,0)，(0,0,1)。 清华大学出版社 74 第第3节节 单纯形法单纯形法 v3.1 举例 v3.2 初始基可行解的确定 v3.3 最优性检验与解的判断 v3.4 基变换

39、v3.5 迭代（旋转运算） 清华大学出版社 75 单纯形法求解线性规划的思路： 一般线性规划问题具有线性方程组的变量数大于一般线性规划问题具有线性方程组的变量数大于 方程个数，这时有不定的解。但可以从线性方程组中方程个数，这时有不定的解。但可以从线性方程组中 找出一个个的单纯形，找出一个个的单纯形，每一个单纯形可以求得一组解每一个单纯形可以求得一组解， 然后再判断该解使目标函数值是增大还是变小，决定然后再判断该解使目标函数值是增大还是变小，决定 下一步选择的单纯形。下一步选择的单纯形。这就是这就是迭代迭代，直到目标函数实，直到目标函数实 现最大值或最小值为止。这样，问题就得到了最优解，现最大值

40、或最小值为止。这样，问题就得到了最优解， 先举一例来说明。先举一例来说明。 清华大学出版社 76 3.1 举例 例例6 试以例1来讨论如何用单纯形法求解。 解：已知本例的标准型为： )111 (00032max 54321 xxxxxz 5 , 2 , 10 124 )121 (164 82 52 41 321 jx xx xx xxx j 清华大学出版社 77 3.1 举例 约束条件(1-12)式的系数矩阵为 从(1-12)式可看到x3,x4,x5的系数构成的列向量 1 0 0 0 1 0 040 004 121 , 54321 PPPPPA 1 0 0 , 0 1 0 , 0 0 1 54

41、3 PPP 清华大学出版社 78 3.1 举例 P3 ,P4,P5是线性独立的，这些向量构成一个基B 。 对应于B的变量x3,x4,x5为基变量. 124 )121 (164 82 52 41 321 xx xx xxx 从(1-12)式中可以得到（1-13） )131 ( 412 416 28 25 14 213 xx xx xxx 清华大学出版社 79 3.1 举例 将(1-13)式代入目标函数(1-11)： 得到 当令非基变量x1=x2=0，便得到z=0。这时得到一个基可 行解X(0) X(0)=(0,0,8,16,12)T 本基可行解的经济含义是：工厂没有安排生产产品、 ，资源都没有被

42、利用，所以工厂的利润为z=0。 )111 (00032max 54321 xxxxxz )141 (320 21 xxz 清华大学出版社 80 3.1 举例 从分析目标函数的表达式从分析目标函数的表达式(1-14)可以看到：可以看到： 非基变量非基变量x1,x2(即没有安排生产产品即没有安排生产产品，)的系的系 数都是正数，因此将非基变量变换为基变量，目标数都是正数，因此将非基变量变换为基变量，目标 函数的值就可能增大。从经济意义上讲，安排生产函数的值就可能增大。从经济意义上讲，安排生产 产品产品或或，就可以使工厂的利润指标增加。所以，就可以使工厂的利润指标增加。所以 只要在目标函数只要在目标

43、函数(1-14)的表达式中还存在有正系数的的表达式中还存在有正系数的 非基变量，这表示目标函数值还有增加的可能，就非基变量，这表示目标函数值还有增加的可能，就 需要将非基变量与基变量进行对换。需要将非基变量与基变量进行对换。 清华大学出版社 81 3.1 举例 v如何确定换入、换出变量 一般选择正系数最大的那个非基变量x2为换入变 量，将它换到基变量中，同时还要确定基变量中 哪一个换出来成为非基变量。 可按以下方法来确定换出变量： o分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5 中确定一个换出变量，并保证其余的变量仍然非负，即 x3,x4,x50。 清华大学出版社 82

44、3.1 举例 v如何确定换入、换出变量 当x1=0时，由(1-13)式得到 )151 ( 0412 016 028 25 4 23 xx x xx )131 ( 412 416 28 25 14 213 xx xx xxx 清华大学出版社 83 3.1 举例 v如何确定换入、换出变量 当x2取何值时，才能满足非负要求呢？ 从(1-15)式可看出，只有选择 x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。 因当x2=3时，基变量x5=0，这就决定用x2去替换x5。 以上数学描述说明，每生产一件产品，需要用 掉的各种资源数为(2，0，4)。由这些资源中的薄 弱环节，就确定了产

45、品的产量。 这里就是由原材料B的数量确定了产品的产量 x2=12/4=3件。 清华大学出版社 84 3.1 举例 v如何确定换入、换出变量 为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析 问题，需将(1-13)中x2的位置与x5的位置对换，得到 )131 ( 412 416 28 25 14 213 xx xx xxx )161 ( 3124 2416 182 52 14 123 xx xx xxx 清华大学出版社 85 3.1 举例 v将(1-16)式中x2的系数列向量变换为单位列向量。 其运算步骤是： v=/4；=-2;=, v并将结果仍按原顺序排列有： 171 3 4 1

46、3 2416 1 2 1 2 52 14 513 xx xx xxx 高斯消去法高斯消去法 清华大学出版社 86 3.1 举例 v再将(1-17)式代入目标函数(1-11)式得到 清华大学出版社 87 3.1 举例 从目标函数的表达式(1-18)可看到，非基变量x1的系数是正的，说明 目标函数值还可以增大，即X(1)还不是最优解。 于是，再用上述方法确定换入、换出变量，继续迭代，得到另一个 基可行解X(2) X(2)=(2,3,0,8,0)T 再经过一次迭代，又得到一个基可行解X(3) X(3)=(4,2,0,0,4)T 而这时得到目标函数的表达式是： z=141.5x3 0.125x4 (1

47、-19) 再检查(1-19)式，可见所有非基变量x3,x4的系数都是负数，这说明若 要用剩余资源x3,x4，就必须支付附加费用。 所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。 所以X(3)是最优解。即当产品生产4件，产品生产2件时，工厂可 以得到最大利润。 清华大学出版社 88 小结 v通过上例，可将每步迭代得到的结果与图解法做一对比。 v例1的线性规划问题是二维的，即有两个变量x1,x2。当加入松弛变量 x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域 是高维空间中的凸多面体(凸集)。该凸多面体上的顶点，就是基可行解。 初始基可行解为 X(0)=

48、(0,0,8,16,12)T，对应于图1-2中的原点(0，0)； X(1)=(0,3,2,16,0)T对应于图中的Q4点(0，3)； X(2)=(2，3，0，8，0)T对应 于Q3点(2，3)；最优解X(3)=(4，2，0，0，4)T相当于图中的 Q2点(4，2)。 从初始基可行解X(0)开始迭代， 依次得到X(1)，X(2)，X(3)，相当 于图中的目标函数平移时，从0 点开始，首先碰到Q4，然后碰到 Q3，最后达到Q2。 清华大学出版社 89 3.2 初始基可行解的确定 v为了确定初始基可行解，要首先找出初始可行基， 其方法如下。 (1)直接观察 (2)加松弛变量 (3)加非负的人工变量

49、清华大学出版社 90 3.2 初始基可行解的确定 从线性规划问题 的系数构成的列向量Pj(j=1,2,n)中，通过直接观察，找 出一个初始可行基 njx bxP xcz j n j jj n ij jj , 2 , 10 211 201max 1 1 1 1 , 21 m PPPB (1)直接观察直接观察 清华大学出版社 91 3.2 初始基可行解的确定 对所有约束条件为“”形式的不等式，利用化标准型的方 法，在每个约束条件的左端加上一个松弛变量。经过整理， 重新对xj及aij (i=1,2,m; j=1,2,n)进行编号，则可得下列 方程组（x1,x2,xm 为松弛变量）： njx bxax

50、ax bxaxax bxaxax j mnmmmmm nnmm nnmm , 2 , 1, 0 221 11, 2211,22 1111, 11 (2)加松弛变量加松弛变量 清华大学出版社 92 3.2 初始基可行解的确定 于是，(1-22)中含有一个mm阶单位矩阵，初始可行基 B即可取该单位矩阵。 将(1-22)式每个等式移项得 1 1 1 , 21 m PPPB nmmmmmm nnmm nnmm xaxabx xaxabx xaxabx 11, 211, 222 111, 111 231 清华大学出版社 93 3.2 初始基可行解的确定 令xm+1=xm+2=xn=0，由(1-23)式可