胡云权运筹学课件第一部分

运筹学基础第一讲主讲教师：郑黎黎学时：48运筹学的产生和发展运筹学的定义与特点运筹学解决问题的过程运筹学的主要研究内容参考文献绪论运筹学在英国被称为

运筹学的产生和发展运筹学在美国被称为1957年我国operationalresearchoperationsresearch，缩写为O.R.“夫运筹帷幄之中，决胜于千里之外”《汉书》1957年我国将O.R.译为“运筹学”运筹学思想的出现可以追溯到很早以前—“田忌齐王赛马”（对策论）、“丁谓修宫”（网络计划）等都体现了优化的思想。运筹学的产生和发展田忌赛马齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王 上 中 下 田忌 下 上 中

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

1948年美国麻省理工学院

1950年英国伯明翰大学1950年第一本运筹学杂志《运筹学季刊》在英国创刊1952年第一个运筹学学会在美国成立1947年丹齐克在研究美国空军资源优化配置时提出线性规划及其通用解法——单纯形法

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

运筹学(OperationsResearch)直译为“运作研究”。美国运筹学会认为：运筹学所研究的问题，通常是在要求有限资源的条件下科学地决定如何最好地设计和运营人机系统。中国大百科全书释义：它用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。

运筹学的定义与特点还有人：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际问题中提出的专门问题，为决策者选择最优决策提供定量依据。特点：系统寻优、多学科综合、辅助决策运筹学解决问题的过程运筹学解决问题的过程主要包括以下几个步骤：分析和表述问题，这是对问题的定性分析过程。建立模型。运筹学模型大都包括两个部分：目标和约束，建立模型的过程就是用参数、决策变量表达目标函数、约束条件。运筹学解决问题的过程模型求解。用各种手段求解模型，解的精度要求可由决策者提出。模型的测试：首先检查解的求解步骤和程序有无错误，然后检查解是否反映现实问题。建立对解的有效控制。方案实施：将方案应用的实践中，并检验方案的可行性，若不可行重新进行上述过程。运筹学解决问题的过程例1.某工厂生产Ⅰ和Ⅱ两种型号计算机，生产Ⅰ型和Ⅱ型计算机所需要原料分别为2和3个单位，需要的工时分别是4和2个单位。在计划期内可以使用的原料的100个单位，工时为120个单位。已知生产每台Ⅰ、Ⅱ型计算机可获利润分别为6个单位和4个单位，试确定获得最大利润的生产方案。运筹学解决问题的过程目标函数：

约束条件：

设z为获得的利润，和分别为生产Ⅰ型和Ⅱ型计算机台数线性规划运筹学的主要研究内容运筹学的主要研究内容运输问题运输问题线性规划非线性规划动态规划运筹学的主要研究内容

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

胡运权.运筹学教程[M].北京,清华大学出版社,2002年。钱颂迪.运筹学[M].北京,清华大学出版社,1990年。郭立夫.运筹学[M].长春,吉林大学出版社,2002年。胡运权.运筹学习题集[M].北京,清华大学出版社,1985年。刘满凤、付波、聂高飞.运筹学模型与方法教程例题分析与题解[M].北京,清华大学出版社,2001年。线性规划与单纯形法

线性规划（Linearprogramming）是运筹学的重要分支，是研究在一组线性等式或者不等式约束下，使得某一线性目标函数取得最大（最小）的极值问题。

1947年美国人丹齐克提出了用于求解线性规划的单纯形法。例1.美佳公司计划制造Ⅰ、Ⅱ两种家电产品。各制造一件时分别占用的设备A、B的台时、调试时间及每天这两种家电可用能力、各售出一件时获利情况如表所示：项目ⅠⅡ每天可用能力设备A(h)0515设备B(h)6224调试时间(h)115利润（元）21问公司应制造两种家电各多少台，使获取的利润最大。线性规划问题及其

数学模型线性规划问题及其

数学模型(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”，s.t.subjectto的缩写，“受限制于……”运筹学基础第三讲主讲教师：郑黎黎学时：48线性规划问题及其

数学模型例2捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表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，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：目标函数约束条件s.t.min：minimize，“最小化”线性规划问题的特征：每个问题都用一组未知变量表示目标函数和约束条件，并且这些变量都是非负的。有一个目标函数，并且这个目标可表示为一组未知量的线性函数，目标函数可以是求最大也可以求最小。存在一组约束条件，这些约束条件都可以用一组未知量线性等式或不等式表示。线性规划问题及其

数学模型目标函数：

约束条件：线性规划问题数学模型的一般形式：其中：为价值系数；为资源系数；为技术系数，或约束系数；线性规划问题及其

数学模型若设：,，1.矩阵式线性规划问题及其

数学模型，2.向量式3.和式在后面的公式推导中矩阵式和向量式用的比较多。线性规划问题及其

数学模型线性规划问题数学模型的标准型：目标函数：

约束条件：其中：为价值系数；为资源系数；为技术系数，或约束系数；线性规划问题及其

数学模型运筹学基础第四讲主讲教师：郑黎黎学时：48线性规划的标准形式有四个特点：目标最大化、约束为等式、右端项非负、决策变量均非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。线性规划问题及其

数学模型1.极小化目标函数的问题设目标函数为：则可以令：，该极小化问题与下面的极大化问题有相同的最优解：线性规划问题及其

数学模型2.约束条件不是等式的问题设约束条件为：则可在约束的左端加上一个非负变量使上面的约束这个不等式约束变为等式约束：——松弛变量

线性规划问题及其

数学模型同理，对于不等式约束：

则可在约束的左端减去一个非负变量，则这个不等式约束变为：这个非负变量称为松弛变量或剩余变量。线性规划问题及其

数学模型线性规划问题的标准型3.变量无符号限制的问题在标准形式中，必须每一个变量均有非负约束。当某一个变量没有非负约束时，可以令：其中，即用两个非负变量之差来表示一个无符号限制的变量，当然的符号取决于和的大小。4.对于可以令：显然

5.右端项有负值的问题在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如，则把该等式约束两端同时乘以-1，得到：

线性规划问题及其

数学模型线性规划问题的数学模型和图解法图解法求解线性规划问题的步骤:分别取决策变量x1,x2

为坐标向量建立直角坐标系。确定可行域：对每个不等式约束（包括非负约束）条件，先画出其等式在直角坐标系中的直线，然后确定约束不等式所决定的半平面，各约束半平面交出来的区域即为可行域。图示目标函数。最优解的确定。线性规划问题的标准型

和解的概念例1的可行域表示(1.1c)(1.1a)(1.1b)(1.1d)利用图解法求解例1的最优解：线性规划问题的标准型

和解的概念例1的可行域表示(1.1c)(1.1a)(1.1b)(1.1d)利用图解法求解例1的最优解：线性规划问题的标准型

和解的概念图示目标函数和最优解的确定(1.1d)查看目标函数和可行域的关系，寻找线性规划问题的最优解。

先将目标函数变为：求解Q2，得到问题最优值线性规划问题的标准型

和解的概念因此，美佳公司每天制造家电Ⅰ3.5件，家电Ⅱ1.5件，能获得的最大利润是8.5元。线性规划问题的标准型

和解的概念①无穷多个最优解情况

将例1的目标函数变为：(1.1d)线性规划问题的标准型

和解的概念②无界解例1只包含约束1.1a(1.1d)线性规划问题的标准型

和解的概念③无可行解情况如果约束条件中存在相互矛盾的约束时，可行域为空，问题无可行解。线性规划问题的标准型

和解的概念从图解法可以看到：当线性规划问题的可行域非空时，它的可行域是有界或无界凸多边形。若线性规划存在最优解，它一定是在可行域的某个顶点得到；若在两个顶点同时得到，则它们连线上的任意一点都是最优解，即无穷多最优解。线性规划问题的标准型

和解的概念从图解法可以看到：解题思路：

先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。复习线性代数内容:列向量x=(x1，x2，…，xn）T为n维列向量。xRn行向量x=(x1，x2，…，xn）为n维列向量。xRn矩阵(向量)运算规则加减乘、求逆运算

线性相关一组向量v1,…,vn,如果有一组不全为零的系数α1,…,αn,使得:α1v1+…+αnvn=0

则称v1,…,vn是线性相关的.线性无关一组向量v1,…,vn,如果对于任何数α1,…,αn,

若要满足:α1v1+…+αnvn=0,则必有系数

α1=…=αn=0,(全为零)则称v1,…,vn线性无关.矩阵A的秩设A为一个m×n阶矩阵(m<n)若矩阵中最大线性无关列向量个数为k,则称矩阵A的秩为k,记为rank(A)=k.线性规划解的概念线性规划数学模型标准型矩阵式：

(1.6)(1.7)(1.8)，可行解：满足约束条件(1.7)和非负条件(1.8)的解称为可行解。可行域：可行解的集合。最优解：满足条件(1.6)的可行解。(L)运筹学基础第五讲主讲教师：郑黎黎学时：48线性规划解的概念基：设A是阶系数矩阵()，秩A=m，则A中一定存在m个线性无关的列向量，称由m个线性无关的列向量构成的可逆矩阵为问题L的一个基，L最多有个基。基变量：称与基B中的列向量对应的变量为基变量，记为其余变量为非基变量，记为。，，线性规划解的概念基解：在约束方程组(1.7）中令所有的非基变量，又因为|B|，根据克来姆规则，由m个约束方程可解出m个基变量的唯一解。将这个解加上非基变量取0的值有称X为线性规划问题L的基本解。基本解的非零分量个数小于等于

m，当小于m时，则此基解是退化解，这种现象不多。，，线性规划问题的标准型

和解的概念约束方程的解空间基本解可行解非可行解基可行解退化解

线性规划标准型问题解的关系基可行解：若B对应的基本解则称该解为基本可行解，称B为可行基。凸集及其顶点凸集：设C是n维欧式空间的一个点集，若任意两点的连线上的一切点

(

),则称C为凸集。凸集的特征是：连接任意两点的线段整个都在集合之中。凸集及其顶点顶点：设K是凸集，,若不能表示成任何两点连线的内点，则称为K的一个顶点。基本定理定理1：线性规划问题的可行域是一个凸集.设：则（1.9）因为：(1.10)

所以：又因为：所以：因此线性规划问题的可行域是凸集。

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

基本定理定理2：线性规划问题的基可行解对应线性规划问题的可行域（凸集）顶点。证明：采用反证法

基本定理定理2：线性规划问题的基可行解对应线性规划问题的可行域（凸集）顶点。证明：采用反证法基本定理定理2：线性规划问题的基可行解对应线性规划问题的可行域（凸集）顶点。证明：采用反证法必要性：不失一般性，假设可行解前k个分量为正，故

(1.11)设是可行域的顶点，若不是基可行解则根据引理1，其正分量对应的系数列向量线性相关，即存在一组不全为0的数，使得：

(1.12)

基本定理定理2：线性规划问题的基可行解对应线性规划问题的可行域（凸集）顶点。证明：采用反证法必要性：不失一般性，假设可行解前k个分量为正，故

(1.11)若不是基可行解则根据引理1，其正分量对应的系数列向量线性相关，即存在一组不全为0的数，使得：

(1.12)

基本定理用一个非常小的正数乘（1.12）再分别与(1.11)相加减，这样得到：令：因为是一个非常小的正数，因此可以保证，即和是可行解。由和可以得到，即是和连线的中点，即不是可行域的顶点。基本定理充分性：设X是基可行解，则必线性无关，若X不是可行域D的顶点，则存在，且，及有：

于是，对有则另外：由于线性无关故则，与相矛盾，因此X必是可行域的顶点。

基本定理充分性：若X不是可行域D的顶点，则存在，且，及有：

于是，对有则另外：则因，所以故线性相关，即X不是基可行解。

基本定理定理3：若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解。证明：设X是最优解，是可行域的k个顶点，若X不是顶点，则X可以表示为可行域k个顶点的凸组合，表示为：因此：基本定理另外，在所有顶点上必然会找到一个顶点，使CX(s)是所有CX(j)

中最大的，则，由此得到根据假设是最大值，所以只能是即目标函数在顶点X(s)也取得最大值。，基本定理综上，得到结论：线性规划问题的可行域为凸集（定理1）；凸集的每个顶点对应一个基可行解（定理2），基可行解的个数是有限的，当然凸集的顶点个数也是有限的；若线性规划有最优解，必在可行域某顶点上达到，（定理3）亦即在有限个基可行解中间存在最优解。单纯形法迭代原理单纯形法求解思路：

，初始基可行解是否是最优解结束找一个较好基可行解NY由于基可行解数目有限（小于等于）因此，经过有限次迭代即可找到最优解。

，

确定下面线性规划问题的初始基可行解运筹学基础第六讲主讲教师：郑黎黎学时：48，

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

用M法确定下面线性规划问题的初始基可行解从一个基可行解转换为

相邻基可行解定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。设初始基可行解中的前m个为基变量，即：

（1.19）

带入等式约束中

因是一个基，其他向量可用这个基的线形组合来表示，有

（1.２０）

+

（１.２２）从一个基可行解转换为

相邻基可行解乘

由式（1.22）找到满足约束方程组

时是非负的。

从一个基可行解转换为

相邻基可行解

因，故由上述矩阵元素组成的行列式不为零，是一个基在上述增广矩阵中进行行的初等变换，将第行乘上（），再分别乘以（）加到各行上去，则增广矩阵左半部变成为单位矩阵，又因故

从一个基可行解转换为

相邻基可行解

最优性检验和解的判别

将和分别带入目标函数得：（１．２５）

或

最优性检验和解的判别

（1）当所有的时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明及凸集的性质，可以判定现有顶点的基可行解即为最优解。（2）当所有的，又对某个非基变量有，且按式（1.24）可以找到，这表明可以找到另一个顶点（基可行解）目标函数值也达到最大。由于该两点连续的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。最优性检验和解的判别

（3）如果存在某个，又，由式（1.23）看出对任意的，均有，因而取值可为无限增大不受限制。由式（1.25）看到也可无限增大，表明线性规划有无界解。（１．２５）

定理4（最优性）对某基可行解其余，若所有，则该解为最优解。定理5（无界解）若对某可行基B，若存在，则该线性规划问题无有限最优解（或称无最优解）。最优性检验和解的判别求解例1的一个基可行解和相应的检验数，并判断其是否最优解。(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)最优性检验和解的判别单纯形表将式子（1.7a）和（1.6a）变化为，

增广矩阵cjc1c2…cmcm+1…cnCBXBB-1bx1x2…xmxm+1…xnc1…cmx1…xma10…am00…0a1m+1

…

a1n

…1……………001amm+1…

amn00…0σm+1…

σnσj=cj-CBB-1PjB-1Pj≠Pj基变量值基变量基变量价值系数决策变量价值系数CB

XB

21000

B-1b

x1x2x3x4x50x315051000x424620100x551100121000解：表1-7c基的变换︱旋转变换就是对单纯形表中的元素做如下初等行变换，将一个非基变量xk旋入基变量中，同时将基变量xBl旋出，用xk取代xBl。设可行基B对应的单纯形表为{}表中，xk是非基变量，xBl是基变量运筹学基础第七讲主讲教师：郑黎黎学时：48基的变换︱旋转变换表中第l行都除以，即表中第i行（）元素减第l行对应新元素的倍，即单纯形表{}在上述初等行变换下变为{}基的变换︱旋转变换上述旋转变换中：

——旋转主元l——为旋转行，k为旋转列，旋转行对应的基变量xBl——旋出变量旋转列对应的非基变量xk——旋入变量CB

XB

21000B-1b

x1x2x3x4x50x315051000x424620100x551100121000表1-7cjCB

XB

21000B-1b

x1x2x3x4x5cj基的变换︱旋转变换上述旋转变换中：

——旋转主元l——为旋转行，k为旋转列，旋转行对应的基变量xBl——旋出变量旋转列对应的非基变量xk——旋入变量由上面的例子可以看出，旋转变换的实质就是用一系列的初等行变换将主元列变为单位列向量，其中主元变为1，主元列的其余元素都为零。基的变换︱旋转变换引理2若{}是以为基的单纯形表，则在旋转变换下得到的{}是以为基的单纯形表。由引理2可知，对单纯形表进行旋转变换就是实现基的变换，因而能从一个基本解求出另外一个基本解。如果按照一定规则选取旋入变量及旋出变量，就能保证基的变换始终在基可行解间进行，而且目标函数值不断改善。单纯形算法步骤1.确定初始基B和初始基可行解建立初始单纯形表；2.检查非基变量的检验数，若所有的，则已经得到最优解计算停；否则求确定xk为旋入变量；3.若对于，则此问题无有限最优解，计算停；否则转入步骤4；单纯形算法步骤4.计算确定xBl为旋出变量。5.以为主元做旋转变换得新的单纯形表，转步骤2。CB

XB

21000

B-1b

x1x2x3x4x50x315051000x424620100x551100121000解：表1-7cj

例5用单纯形法求解下面的线性规划问题CB

XB

21000B-1b

x1x2x3x4x50x315051000x424620100x551100121000表1-7cjCB

XB

21000B-1b

x1x2x3x4x5cj01/602/614x120-1/301/301-1/604/601x500015015x30x5x4x3x2x1B-1b

00012

XBCB表1-8cjx5x4x3x2x1B-1b

00012

XBCBcj表1-9中所有j<=0,

最优解X=(7/2,3/2,15/2,0,0);

最优值Z=17/2.运筹学基础第八讲主讲教师：郑黎黎学时：48单纯形算法步骤

习题1计算下列线性规划取为初始基为初始基可行解Ⅰcj6

400CBXBB-1bx1x2x3x400x3x41001202310[4]2016400Ⅰcj6

400CBXBB-1bx1x2x3x400x3x4100120231042016400Ⅱcjc1c2c3c4CBXBB-1bx1x2x3x406x3x14030021-1/211/201/4010-3/2Ⅱcjc1c2c3c4CBXBB-1bx1x2x3x406x3x140300[2]1-1/211/201/4010-3/2ⅢCc1c2c3c4CBXBB-1bx1x2x3x446x2x12020011/2-1/410-1/43/800-1/2-5/4

例6用单纯形法求解下面的线性规划问题-M0-10x500010x6-M00-11-21x6-M0014M-2M-3101309x7-M011114x40x7x4x3x2x1

B-1b

-M010-3cjXBCB表1-10cj-M0-10x500010x6-M00-1[1]-21x6-M0014M-2M-3101309x7-M011114x40x7x4x3x2x1

B-1b

-M010-3cjXBCB表1-10cjx50x6-M

x7x4x3x2x1

B-1b

-M010-3cjXBCBcj运筹学基础第九讲主讲教师：郑黎黎学时：48CBXBcj-30100-M-MB-1bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx76[6]0403-316M-304M+103M-4M0cj0x400011-1/2-1/2-1/20x2-3x11102/301/2-1/21/60x400011-1/2-1/2-1/20x23011/30001/3-3x11102/301/2-1/21/600303/2-M-3/2-M+1/2单纯形法的进一步讨论

如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。单纯形法的进一步讨论两阶段法：第一阶段（目的是求解该问题的一个初始基可行解）：

求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数(一般取1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原线性规划问题的一个基可行解。单纯形法的进一步讨论两阶段法：如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。第二阶段：将第一阶段得到的基可行解作为原问题的初始基可行解，然后按照单纯形法求解原问题的最优解。例6两阶段法第一阶段：-10-10x500010x6-100-1[1]-21x6-10004-21013-19x7-1011114x40x7x4x3x2x1B-1b-10000

XBCB表1-11cj33-11x50-4-31-1x6-100-11-21x20004061040[6]6x7-1012033x40x7x4x3x2x1B-1b-10000XBCB表1-11请注意:第一阶段的最优解不是唯一的01/20-1/2x50-1-1/201/2x6-11/301/3103x20-100001/602/3011x10-1/210000x40x7x4x3x2x1B-1b-10000

XBCBcjcj3/203001/20-1/2x5001/3103x2002/3011x1-310000x40x4x3x2x1B-1b010-3

XBCB表1-12第二阶段01/20-1/2x50-1-1/201/2x6-11/301/3103x20-100001/602/3011x10-1/210000x40x7x4x3x2x1B-1b-10000

XBCBcjcj3/203001/20-1/2x5001/3103x200[2/3]011x1-312000x40x4x3x2x1B-1b010-3

XBCB表1-12第二阶段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/20103/23/2x3110000x40x4x3x2x1B-1b0000