运筹学基础学习培训课件.ppt

1、运筹学基础运筹学基础第一讲第一讲&运筹学的产生和发展&运筹学的定义与特点&运筹学解决问题的过程&运筹学的主要研究内容&参考文献绪绪 论论|运筹学在英国被称为|运筹学在美国被称为|1957年我国operational researchoperations research，缩写为O.R.“夫运筹帷幄之中，决胜于千里之外”汉书|1957年我国将O.R.译为“运筹学”|运筹学思想的出现可以追溯到很早以前“田忌齐王赛马”（对策论）、“丁谓修宫”（网络计划）等都体现了优化的思想。田忌赛马齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导

2、下，以以下安排：齐王 上中下田忌 下上中最终净胜一局，赢得1000金。|运筹学思想的出现可以追溯到很早以前“田忌齐王赛马”（对策论）、“丁谓修宫”（网络计划）等都体现了优化的思想。|“运筹学”作为科学概念最早出现在第二次世界大战期间 美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的，如水雷的布置、对深水潜艇的袭击、商船护航的规模等等。|战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段：1945至50年代初期创建时期J1948年英国成立“运筹学俱乐部”在煤力、电力等部门推广应用运筹学J相继一些大学开设运筹学课程 1948年美国麻省理工学院 195

3、0年英国伯明翰大学J1950年第一本运筹学杂志运筹学季刊在英国创刊J1952年第一个运筹学学会在美国成立J1947年丹齐克在研究美国空军资源优化配置时提出线性规划及其通用解法单纯形法|战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段：1945至50年代初期创建时期50年代初期至50年代末期成长时期|战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段：1945至50年代初期创建时期50年代初期至50年代末期成长时期J此阶段的一个特点是电子计算机技术的迅速发展，使得运筹学中一些方法如单纯形法、动态规划方法等，得以用来解决实际管理统中的优化问题，促进了运筹学的推广应用。J5

4、0年代未，美国大约有半数的公司在自己的经营管理中应用运筹学，如用于制订生产计划、资源分配、设备更新等方面的决策。J另一个特点是有更多刊物、学会出现。|战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段：1945至50年代初期创建时期50年代初期至50年代末期成长时期自60年代来，运筹学迅速普及和迅速发展时期。J此阶段的特点是运筹学进一步细分为各个分支，专业学术团体的迅速增多，更多期刊的创办，运筹学书籍的大量出版以及更多学校将运筹学课程纳入教学计划之中。第三代电子数字计算机的出现，促使运筹学得以用来研究一些大的复杂的系统如城市交通、环境污染、回民经济计划等。|战后这些研究成果被应用到

5、生产、经济领域，其发展可以分为三个阶段：1945至50年代初期创建时期50年代初期至50年代末期成长时期自60年代来，运筹学迅速普及和迅速发展时期。|运筹学在我国的发展运筹学的定义与特点 运筹学(Operations Research)直译为“运作研究”。|美国运筹学会认为：运筹学所研究的问题，通常是在要求有限资源的条件下科学地决定如何最好地设计和运营人机系统。|中国大百科全书释义：它用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。运筹学的定义与特点|还有人：运筹学是一门

6、应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际问题中提出的专门问题，为决策者选择最优决策提供定量依据。特点：系统寻优、多学科综合、辅助决策运筹学解决问题的过程运筹学解决问题的过程主要包括以下几个步骤：|分析和表述问题，这是对问题的定性分析过程。|建立模型。运筹学模型大都包括两个部分：目标和约束，建立模型的过程就是用参数、决策变量表达目标函数、约束条件。运筹学解决问题的过程|模型求解。用各种手段求解模型，解的精度要求可由决策者提出。|模型的测试：首先检查解的求解步骤和程序有无错误，然后检查解是否反映现实问题。|建立对解的有效控制。|方案实施：将方案应用的实践 中，并检验方案的可行性，

7、若不可行重新进行上述过程。运筹学解决问题的过程例1.某工厂生产和两种型号计算机，生产型和型计算机所需要原料分别为2和3个单位，需要的工时分别是4和2个单位。在计划期内可以使用的原料的100个单位，工时为120个单位。已知生产每台、型计算机可获利润分别为6个单位和4个单位，试确定获得最大利润的生产方案。运筹学解决问题的过程2146maxxxz0,1202410032212121xxxxxx目标函数：约束条件：设z为获得的利润，和 分别为生产型和型计算机台数1x2x|线性规划运筹学的主要研究内容运筹学的主要研究内容运输问题运输问题|线性规划|非线性规划|动态规划运筹学的主要研究内容 某厂新购某种机

8、床125台。据估计，这种设备5年后将被其它设备所取代。此机床如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得最大利润。|线性规划|非线性规划|动态规划|图与网络分析运筹学的主要研究内容运筹学基础运筹学基础第二讲第二讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48|线性规划|非线性规划|动态规划|图与网络分析|存贮论|排队论|决策论|对策论运筹学的主要研究内容参 考 文献|胡运权.运筹学教程M.北京,清华大学出 版社,2002年。|钱颂迪.运筹学M.北京,清华大学出版社,1990年

9、。|郭立夫.运筹学M.长春,吉林大学出版社,2002年。|胡运权.运筹学习题集M.北京,清华大学出 版社,1985年。|刘满凤、付波、聂高飞.运筹学模型与方法教程例题分析与题解M.北京,清华大学出版社,2001年。线性规划（Linear programming）是运筹学的重要分支，是研究在一组线性等式或者不等式约束下，使得某一线性目标函数取得最大（最小）的极值问题。1947年美国人丹齐克提出了用于求解线性规划的单纯形法。例1.美佳公司计划制造、两种家电产品。各制造一件时分别占用的设备A、B的台时、调试时间及每天这两种家电可用能力、各售出一件时获利情况如表所示：项目每天可用能力设备A(h)051

10、5设备B(h)6224调试时间(h)115利润（元）21问公司应制造两种家电各多少台，使获取的利润最大。(1.1c)122121212max25156224.5,0zxxxxxstxxx x目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”，s.t.subject to的缩写，“受限制于”运筹学基础运筹学基础第三讲第三讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48例2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都

11、可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2月 份 1 2 3 4 所需仓库面积 15 10 20 12 合同租赁期限 1 个月 2 个月 3 个月 4 个月 合同期内的租费 2800 4500 6000 7300 用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，

12、x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：ijmin a0(i=1,.,m;j=1,.,n)112131411222321323141112131412131421222313142223313214233241z=2 800(x+x+x+x)+4 500(x+x+x)+6 000(x+x)+7 300 xx+x+x+x15x+x+x+x+x+x10 x+x+x+x+x+x20 x+x+x+x12目标函数约束条件 s.t.min：minimize，“最小化”）（njmixij,2,1;,2,10线性规划问题的特征：|每个问题都用一组未知变量 表示目标函数和约

13、束条件，并且这些变量都是非负的。|有一个目标函数，并且这个目标可表示为一组未知量 的线性函数，目标函数可以是求最大也可以求最小。|存在一组约束条件，这些约束条件都可以用一组未知量线性等式或不等式表示。nxxx,21nxxx,21nnxcxcxcZ2211max(min)0,),(),(),(2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa目标函数：约束条件：线性规划问题数学模型的一般形式：其中：为价值系数；为资源系数；为技术系数，或约束 系数；njcj2,1,mibi2,1,njmiaij2,1,2,1,nm 若设：,Tnxxx

14、)(21X)(21ncccCTnbbb)(21bmnmmnnnaaaaaaaaaA2122221112112)(ppp1，1.矩阵式maxminZ CX（或）AXbX0（或，），2.向量式向量式 3.和式和式 maxminZ CX（或）1njjjx PbX0（或，）11maxmin,1,2,0,1,2,njjjnijjijjZc xa xbimxjn（或）（或，）在后面的公式推导中矩阵式矩阵式和向向量式量式用的比较多。线性规划问题数学模型的标准型：目标函数：约束条件：其中：为价值系数；为资源系数；为技术系数，或约束 系数；njcj2,1,mibi2,1,njmiaij2,1,2,1,nm nn

15、xcxcxcZ2211max0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa运筹学基础运筹学基础第四讲第四讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48线性规划的标准形式有四个特点：目标最大化、约束为等式、右端项非负、决策变量均非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。1.极小化目标函数的问题 设目标函数为：则可以令：，该极小化问题 与下面的极大化问题有相同的最 优解：nnxcxcxcZ2211minZZ)(max2211nnxcxcxcZ）（的最优优目标最优优目标ZZnnxcx

16、cxc22112.约束条件不是等式的问题 设约束条件为：则可在约束的左端加上一个非负 变量 使上面的约束这个不等式 约束变为等式约束：ininiibxaxaxa22111nxinniniibxxaxaxa122111nx松弛变量 同理，对于不等式约束：则可在约束的左端减去一个非负变量 ，则这个不等式约束变为：这个非负变量称为松弛变量或剩余变量。1nxinniniibxxaxaxa12211ininiibxaxaxa22113.变量无符号限制的问题 在标准形式中，必须每一个变量均 有非负约束。当某一个变量 没有 非负约束时，可以令：其中，即用两个非负变量之差来表示一个 无符号限制的变量，当然 的

17、符号取决于 和 的大小。jjjxxx0,jjxxjxjxjxjx4.对于 可以令：显然 0jxjjxx0jx5.右端项有负值的问题 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 ，则把该等式约束两端同时乘以-1，得到：0ibininiibxaxaxa2211图解法求解线性规划问题的步骤:|分别取决策变量x1,x2 为坐标向量建立直角坐标系。|确定可行域：对每个不等式约束（包括非负约束）条件，先画出其等式在直角坐标系中的直线，然后确定约束不等式所决定的半平面，各约束半平面交出来的区域即为可行域。|图示目标函数。|最优解的确定。2x例1的可行域表示(1.1c)12212

18、1212max25156224.5,0zxxxxxstxxx x(1.1a)(1.1b)(1.1d)利用图解法求解例1的最优解：O1x2x1x例1的可行域表示(1.1c)122121212max25156224.5,0zxxxxxstxxx x(1.1a)(1.1b)(1.1d)利用图解法求解例1的最优解：O2x1x3Q2Q4Q1Q图示目标函数和最优解的确定122zxx(1.1d)O1Q3Q2Q4Q2x1x|查看目标函数和可行域的关系，寻找线性规划问题的最优解。先将目标函数变为：212xxz 求解Q2，得到问题最优值 123.5,1.5xx因此，美佳公司每天制造家电3.5件，家电1.5件，能获

19、得的最大利润是8.5元。121262245xxxx 无穷多个最优解情况 将例1的目标函数变为：(1.1d)O1Q3Q2Q4Q2x1x122zxx213xxz 212xxz 无界解例1只包含约束1.1a(1.1d)O2x1x 无可行解情况如果约束条件中存在相互矛盾的约束时，可行域为空，问题无可行解。2146maxxxz121212231 0 0231 2 0,0 xxxxxx从图解法可以看到：|当线性规划问题的可行域非空时，它的可行域是有界或无界凸多边形。|若线性规划存在最优解，它一定是在可行域的某个顶点得到；若在两个顶点同时得到，则它们连线上的任意一点都是最优解，即无穷多最优解。从图解法可以看

20、到：|解题思路：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。复习线性代数内容复习线性代数内容:列向量列向量 x=(x1，x2，xn）T为n维列向量。xRn行向量行向量 x=(x1，x2，xn）为n维列向量。xRn矩阵矩阵(向量向量)运算规则运算规则 加减乘、求逆运算 线性相关线性相关 一组向量v1,vn,如果有一组不全为零的 系数1,n,使得:1 v1+nvn=0 则称v1,vn 是线性相关的.线性

21、无关线性无关 一组向量v1,vn,如果对于任何数1,n,若要满足:1 v1+nvn=0,则必有系数 1=n=0,(全为零)则称v1,vn线性无关.矩阵矩阵A A的秩的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k.线性规划数学模型标准型矩阵式：(1.6)(1.7)(1.8)，CXZmax0XbAX可行解：满足约束条件(1.7)和非负条件(1.8)的解称为可行解。可行域：可行解的集合。最优解：满足条件(1.6)的可行解。(L)运筹学基础运筹学基础第五讲第五讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48基：设A是 阶系数矩阵(

22、)，秩A=m，则A中一定存在m个线性无关的列向量，称由m个线性无关的列向量构成的可逆矩阵 为问题L的一个基，L最多有 个基。基变量：称与基B中的列向量对应的变量为基变量，记为 其余变量为非基变量，记为 。，nm nm),(jmj2j1PPPBmnCTjmjjxxx),(21BXNX，基解：在约束方程组(1.7）中令所有的非基变量 ，又因为|B|，根据克来姆规则，由m个约束方程可解出m个基变量的唯一解 。将这个解加上非基变量取0的值有称X为线性规划问题L的基本解。基本解的非零分量个数 小于等于 m，当小于m时，则此基解是退化解，这种现象不多。，0bBXB1120jmjmjnxxx)0()(1bB

23、XXXNB，约束方程的约束方程的解空间解空间基本解基本解可行解可行解非可行解非可行解基基可行解可行解退化解退化解基可行解：若B对应的基本解 则称该解为基本可行解，称B为可行基。01bBXB凸集：设C是n维欧式空间的一个点集，若任意两点的连线上的一切点 (),则称C为凸集。凸集的特征是：连接任意两点的线段整个都在集合之中。(1)(2)(1)CXXX10顶点：设K是凸集，,若 不能表示成任何 两点连线的内点，则称 为K的一个顶点。KX KXKX)2()1(,XX定理1：线性规划问题的可行域 是一个凸集.设：则 （1.9）因为：(1.10)所以：又因为：所以：因此线性规划问题的可行域是凸集。0,|X

24、bAXXDDD)2()1(,XX)2()1(XX0XbAX)1()1(,0XbAX)2()2(,10,)1()2()1(XXXbbbAXAXAX)1()1()2()1(0XXX)2()1()1(DX引理1：线性规划的可行解是基可行解的充要条件是 的正分量所对应的系数列向量线性独立。证明：必要性：根据定义即可证得。充分性：设 的k个正分量的系数列向量 线性独立，若 ，刚好构成一个基，从而X就是相应的基可行解；若 ，则当秩A=m时，一定可以从A的剩余系数列向量中找到m-k个线性无关的列与 构成最大线性无关向量组，构成线性规划问题的一个基，其对应的基本可行解恰为 。),(21nxxxXXkppp12

25、Xmkkppp12mk kppp12X定理2：线性规划问题的基可行解 对应线性规划问题的可行域（凸集）顶点。证明：采用反证法 XXX是可行域顶点是基可行解定理2：线性规划问题的基可行解 对应线性规划问题的可行域（凸集）顶点。证明：采用反证法XXX不是可行域顶点不是基可行解定理2：线性规划问题的基可行解 对应线性规划问题的可行域（凸集）顶点。证明：采用反证法必要性：不失一般性，假设可行解 前k个分量为正，故 (1.11)设 是可行域的顶点，若 不是基可行解则根据引理1，其正分量对应的系数列向量线性相关，即存在一组不全为0的数 ，使得：(1.12)XXbpkjjjx1kppp1,2kii,2,1,

26、0221kkppp1XXXX不 是 基 可 行 解不 是 可 行 域 顶 点定理2：线性规划问题的基可行解 对应线性规划问题的可行域（凸集）顶点。证明：采用反证法必要性：不失一般性，假设可行解 前k个分量为正，故 (1.11)若 不是基可行解则根据引理1，其正分量对应的系数列向量线性相关，即存在一组不全为0的数 ，使得：(1.12)XXbpkjjjx1kppp1,2kii,2,1,0221kkppp1X用一个非常小的正数 乘（1.12）再分别与(1.11)相加减，这样得到：令：因为 是一个非常小的正数，因此可以保证 ，即 和 是可行解。由 和 可以得到，即 是 和 连线的中点，即 不是可行域的

27、顶点。bpppbppp11kkkkkkxxxxxx)()()()()()(22211222110,0),(,),(),(0,0),(,),(),(2211)2(2211)1(kkkkxxxxxxXXkixii,2,1,0)1(X)2(X)1(X)2(X)2()1(2121XXX)1(X)2(XX充分性：设X 是基可行解，则 必线性无关，若X不是可行域D的顶点，则存在 ，且 ，及 有：于是，对 有 则另外：由于 线性无关故 则 ，与 相矛盾，因此X必是可行域的顶点。kppp1,2DD)2()1(,XX)2()1(XX10)2()1()1(XXXnkkj,2,1,)1(0)2()1(jjjxxx0

28、)2()1(jjxxbpbpkjjjkjjjxx1)2(1)1(,0)(1)2()1(kjjjjxxpmppp1,2kjxxjj,2,1,)2()1()2()1(XX)2()1(XXXX不 是 可 行 域 顶 点不 是 基 可 行 解充分性：若X不是可行域D的顶点，则存在 ，且 ，及 有：于是，对 有 则另外：则因 ，所以故 线性相关，即X不是基可行解。kppp1,2DD)2()1(,XX)2()1(XX10)2()1()1(XXXnkkj,2,1,)1(0)2()1(jjjxxx0)2()1(jjxxbpbpkjjjkjjjxx1)2(1)1(,0)(1)2()1(kjjjjxxp)2()1

29、(XX(1)(2)()0(1,2,)jjxxjk定理3：若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解。证明：设X是最优解，是可行域的k个顶点，若X不是顶点，则X可以表示为可行域k个顶点的凸组合，表示为：因此：)()2()1(,kXXX10,1)(1kjjjjkjj且XX)(1)(1jkjjjkjjXCXCCX另外，在所有顶点上必然会找到一个顶点 ，使CX(s)是所有 CX(j)中最大的，则，由此得到根据假设 是最大值，所以只能是即目标函数在顶点X(s)也取得最大值。，)(sX)()(1)(1sskjjjkjjCXXCXC)(sCXCX CX)(sCXCX 综上，得到结论：

30、|线性规划问题的可行域为凸集（定理1）；|凸集的每个顶点对应一个基可行解（定理2），基可行解的个数是有限的，当然凸集的顶点个数也是有限的；若线性规划有最优解，必在可行域某顶点上达到，（定理3）亦即在有限个基可行解中间存在最优解。单纯形法求解思路 ：，初始基可行解初始基可行解是否是是否是最优解最优解结束结束找一个较好找一个较好 基可行解基可行解NY由于基可行解数目有限（小于等于 ）因此，经过有限次迭代即可找到最优解。mnC，确定下面线性规划问题的初始基可行解2146maxxxz0,1202410032212121xxxxxx运筹学基础运筹学基础第六讲第六讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学

31、时：48，确定下面线性规划问题的初始基可行解313axxxZm123123231234-2+1s.t.39,0 xxxxxxxxxxx大M法：若给定问题标准化后，系数矩阵中不存在m个线性无关的单位列向量，则在某些约束的左端加入非负变量（人工变量），使得变化后的系数矩阵中恰有m个线性无关的单位列向量，并且在目标函数中减去这些人工变量与M的乘积（M是相当大的一个正数）。对于变化后的问题，取这m个单位列向量构成的单位矩阵为初始基，该基对应的解一定是基可行解。关于大M法的几点结论:|若原问题存在最优解X*，则变化后的问题也存在最优解（X*，0）且后者的最优解就是原问题的最优解。|若经过单纯形法迭代后变

32、化后问题的最优解中含有不等于零的人工变量，则原问题无可行解。用M法确定下面线性规划问题的初始基可行解313axxxZm123123231234-2+1s.t.39,0 xxxxxxxxxxx定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。设初始基可行解中的前m个为基变量，即：（1.19）(0)00012(,0,0)Tmxxxx01miiiP xb带入等式约束中bni1jjxp121mmjnP PPPPPb 1,11112,1222,11 000 10001mjnmjnmmmm jm naaabaaabbaaa 因是一个基，其他向量可用这个基的线形组合来表示，有（1.）+（.）

33、mpp1乘 1mjijiiPa P10mjijiiPa Pjp1()0mjij iiPa P01()miijijixaPPb01miiiP xb由式（1.22）找到满足约束方程组时是非负的。bni1jjxp 0011x0,0TjmmjX（1）（-a,，x-a,0,）00min0ilijijljxxaaa)1(X 121111221,11,100000100000100000000000000000ljlmjjljmll jlljmm jPPPPPPbabababbababa 因，故由上述矩阵元素组成的行列式不为零，是一个基在上述增广矩阵中进行行的初等变换，将第行乘上（），再分别乘以（）加到各行

34、上去，则增广矩阵左半部变成为单位矩阵，又因 故 0ija121,1,ljlmP PPP PP1/ijaija/iijba1111,11,(,)Tjlljlljmmjbbbbbaaaa(0)01xmiiizc(1)01011(0)1(x)x()()miiijjimmiijiijiimjiijizccccczcca-aa 将和分别带入目标函数得：X（0）X（1）（）或j()jjcz （1）当所有的时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明及凸集的性质，可以判定现有顶点的基可行解即为最优解。（2）当所有的，又对某个非基变量

35、有，且按式（1.24）可以找到，这表明可以找到另一个顶点（基可行解）目标函数值也达到最大。由于该两点连续的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。0j0j0jjcz （3）如果存在某个，又，由式（1.2 3）看 出 对 任 意 的 ，均 有，因而取值可为无限增大不受限制。由式（1.25）看到也可无限增大，表明线性规划有无界解。0j0jP 00 x0iij-a(1)z（）(1)01011(0)1(x)x()()miiijjimmiijiijiimjiijizccccczcca-aa定理4（最优性）对某基可行解 其余 ，若所有，则该解为最优解。定理5（无界解）若对某可

36、行基B，若存在 ，则该线性规划问题无有限最优解（或称无最优解）。,1bBXB0jx01jBpBCjjc0,0kkPB1求解例1的一个基可行解和相应的检验数，并判断其是否最优解。(1.1c)122121212max25156224.5,0zxxxxxstxxx x目标函数约束条件(1.1a)(1.1b)(1.1d)12345max2000Zxxxxx2312412523455156224s.t.5,0 xxxxxxxxx xxxx12345max2000Zxxxxx2312412523455156224s.t.5,0 xxxxxxxxx xxxx将式子（1.7a）和（1.6a）变化为，bBXXN

37、BEbBNXBEX1NB1NBZ)0(11bBCXXbBCXbBCpBCpBCbBC1BNB1BN1BjBjB1BZZxcZxcZjjjj)01()()()(n1mj1n1mj1)010(1bBCbBNBE1B1增广矩阵cjc1 c2 cm cm+1 cn CBXBB-1bx1 x2 xm xm+1 xnc1cmx1xma10am01 0 0 a1m+1 a1n 1 0 0 1 amm+1 amn0 0 0 m+1 nj=cj-CBB-1PjB-1PjPj基变量值基变量值基变量基变量基基变变量量价价值值系系数数决策变量价值系数决策变量价值系数 CB XB 21000 B-1b x1x2x3x4

38、x50 x315051000 x424620100 x55110012100012345max2000Zxxxxx2312412523455156224s.t.5,0 xxxxxxxxx xxxx12212122max235156224s.t.5,0Zxxxxxxxx x解：表1-734515245xxx1B b c就是对单纯形表中的元素做如下初等行变换，将一个非基变量xk旋入基变量中，同时将基变量xBl旋出，用xk取代xBl。设可行基B对应的单纯形表为 表中 ，xk是非基变量，xBl是基变量ija0lka运筹学基础运筹学基础第七讲第七讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48|表中第

39、l行都除以 ，即|表中第i行（）元素减第l行对应新元素的 倍，即单纯形表 在上述初等行变换下变为 lkaikali njaaalkljlj,2,1,0,njliaaaaaiklkljijij,2,1,0,ijaija上述旋转变换中：|旋转主元|l为旋转行，k为旋转列，|旋转行对应的基变量xBl旋出变量|旋转列对应的非基变量xk旋入变量lka CB XB 21000B-1b x1x2x3x4x50 x315051000 x424620100 x551100121000表1-7 cj CB XB 21000B-1b x1x2x3x4x5 cj上述旋转变换中：|旋转主元|l为旋转行，k为旋转列，|旋

40、转行对应的基变量xBl旋出变量|旋转列对应的非基变量xk旋入变量由上面的例子可以看出，旋转变换的实质就是用一系列的初等行变换将主元列变为单位列向量，其中主元变为1，主元列的其余元素都为零。lka引理2 若 是以 为基的单纯形表，则在旋转变换下得到的 是以 为基的单纯形表。由引理2可知，对单纯形表进行旋转变换就是实现基的变换，因而能从一个基本解求出另外一个基本解。如果按照一定规则选取旋入变量及旋出变量，就能保证基的变换始终在基可行解间进行，而且目标函数值不断改善。ija),(jmj2j1PPPija),(11jmjjjj2j1PPPPPPlkl1.确定初始基B和初始基可行解 建立初始单纯形表；2

41、.检查非基变量的检验数，若所有的 ，则已经得到最优解计算停；否则求确定xk为旋入变量；3.若对于 ，则此问题无有限最优解，计算停；否则转入步骤4；bBX1B01jBpBCjjc0maxkjj1j0,0jjmjaa1BP4.计算 确定xBl为旋出变量。5.以 为主元做旋转变换得新的单纯形表，转步骤2。lklikikiabaab)(0)(min11BBlka CB XB 21000 B-1b x1x2x3x4x50 x315051000 x424620100 x55110012100012345m ax2000Zxxxxx23124125234551 5622 4s.t.5,0 xxxxxxxxx

42、xxxx12212122m ax235156224s.t.5,0Zxxxxxxxx x解：表1-734515245xxx1B b cj 例5用单纯形法求解下面的线性规划问题 CB XB 21000B-1b x1x2x3x4x50 x315051000 x424620100 x551100121000表1-7 cj CB XB 21000B-1b x1x2x3x4x5 cj01/602/614x120-1/301/301-1/604/601x500015015x30 x5x4x3x2x1B-1b 00012 XB CB表1-8cjx5x4x3x2x1B-1b 00012 XB CBcj表1-9中

43、所有j=0,最优解 X=(7/2,3/2,15/2,0,0);最优值 Z=17/2.运筹学基础运筹学基础第八讲第八讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48 习题1 计算下列线性规划取 为初始基 为初始基可行解0,120241003246max432142132121xxxxxxxxxxxxZ1001)(43pp0,2143xxxx120100bB1cj6 4 0 0 CBXBB-1bx1 x2 x3 x4 00 x3x4100120 2 3 1 0 4 2 0 16 4 0 0cj6 4 0 0 CBXBB-1bx1 x2 x3 x4 00 x3x4100120 2 3 1 0 4

44、2 0 16 4 0 0cjc1 c2 c3 c4 CBXBB-1b x1 x2 x3 x4 06x3x14030 0 2 1 -1/2 1 1/2 0 1/4 0 1 0 -3/2cjc1 c2 c3 c4 CBXBB-1b x1 x2 x3 x4 06x3x14030 0 2 1 -1/2 1 1/2 0 1/4 0 1 0 -3/2Cc1 c2 c3 c4 CBXBB-1b x1 x2 x3 x4 46x2x12020 0 1 1/2 -1/4 1 0 -1/4 3/8 0 0 -1/2 -5/4 例6用单纯形法求解下面的线性规划问题313axxxZm123123231234-2+1s.

45、t.39,0 xxxxxxxxxxx-M0-10 x500010 x6-M00-11-21x6-M0014M-2M-3101309x7-M011114x40 x7x4x3x2x1 B-1b -M010-3 cjXB CB表1-10cj313axxxZm0,93124s.t.32132321321xxxxxxxxxxx765431-003maxMxMxxxxxZ)7,.,1(0931-2-4.j732653214321jxxxxxxxxxxxxxts-M0-10 x500010 x6-M00-11-21x6-M0014M-2M-3101309x7-M011114x40 x7x4x3x2x1 B-

46、1b -M010-3 cjXB CBcjx50 x6-M x7x4x3x2x1 B-1b -M010-3 cjXB CBcj运筹学基础运筹学基础第九讲第九讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48CBXB cj-30100-M-MB-1b x1x2x3x4x5x6x70 x4330211-100 x21-21-10-110-Mx7660403-316M-30 4M+103M-4M0cj0 x400011-1/2-1/2-1/20 x2-3x11102/301/2-1/21/60 x400011-1/2-1/2-1/20 x23011/30001/3-3x11102/301/2-1/21

47、/600303/2-M-3/2-M+1/2 如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。两阶段法：第一阶段（目的是求解该问题的一个初始基可行解）：求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数(一般取1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原线

48、性规划问题的一个基可行解。两阶段法：如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。第二阶段：将第一阶段得到的基可行解作为原问题的初始基可行解，然后按照单纯形法求解原问题的最优解。例6 两阶段法313axxxZm123123231234-2+1s.t.39,0 xxxxxxxxxxx第一阶段：67min wxx123412356237421.390(1,.,7)jxxxxxxxxxs txxxxj-10-10 x500010 x6-100-11-21x6-10004-21013-19x7-1011114x40 x7x4x3x2x

49、1 B-1b-10000 XB CB表1-11cj33-11x50-4-31-1x6-100-11-21x2000406104066x7-1012033x40 x7x4x3x2x1 B-1b-10000 XB CB表1-11请注意:第一阶段的最优解不是唯一的01/20-1/2x50-1-1/201/2x6-11/301/3103x20-100001/602/3011x10-1/210000 x40 x7x4x3x2x1 B-1b-10000 XB CBcjcj3/203001/20-1/2x5001/3103x2002/3011x1-310000 x40 x4x3x2x1 B-1b 010-3

50、 XB CB表1-1212345max3000zxxxxx 第二阶段01/20-1/2x50-1-1/201/2x6-11/301/3103x20-100001/602/3011x10-1/210000 x40 x7x4x3x2x1B-1b-10000 XB CBcjcj3/203001/20-1/2x5001/3103x2002/3011x1-312000 x40 x4x3x2x1 B-1b 010-3 XB CB表1-1212345max3000zxxxxx 第二阶段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/20103/23/2x3110000 x40 x4