运筹学基础.ppt

《运筹学基础.ppt》由会员分享，可在线阅读，更多相关《运筹学基础.ppt（137页珍藏版）》请在三一文库上搜索。

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

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

3、乐部”在煤力、电力等部门推广应用运筹学 相继一些大学开设运筹学课程 1948年美国麻省理工学院 1950年英国伯明翰大学 1950年第一本运筹学杂志运筹学季刊在英国创刊 1952年第一个运筹学学会在美国成立 1947年丹齐克在研究美国空军资源优化配置时提出线性规划及其通用解法单纯形法,战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段： 1945至50年代初期创建时期 50年代初期至50年代末期成长时期,运筹学的产生和发展,战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段： 1945至50年代初期创建时期 50年代初期至50年代末期成长时期,运筹学的产生和发展,此阶段

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

5、版以及更多学校将运筹学课程纳入教学计划之中。第三代电子数字计算机的出现，促使运筹学得以用来研究一些大的复杂的系统如城市交通、环境污染、回民经济计划等。,战后这些研究成果被应用到生产、经济领域，其发展可以分为三个阶段： 1945至50年代初期创建时期 50年代初期至50年代末期成长时期 自60年代来，运筹学迅速普及和迅速发展时期。 运筹学在我国的发展,运筹学的产生和发展,运筹学的定义与特点,运筹学(Operations Research)直译 为“运作研究”。 美国运筹学会认为：运筹学所研究的问题，通常是在要求有限资源的条件下科学地决定如何最好地设计和运营人机系统。 中国大百科全书释义：它用数学

6、方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。,运筹学的定义与特点,还有人：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际问题中提出的专门问题，为决策者选择最优决策提供定量依据。,特点： 系统寻优、多学科综合、辅助决策,运筹学解决问题的过程,运筹学解决问题的过程主要包括以 下几个步骤： 分析和表述问题，这是对问题的定性分析过程。 建立模型。运筹学模型大都包括两个部分：目标和约束，建立模型的过程就是用参数、决策变量表达目标函数、约束条件。,运筹学解决问题

7、的过程,模型求解。用各种手段求解模型，解的精度要求可由决策者提出。 模型的测试：首先检查解的求解步骤和程序有无错误，然后检查解是否反映现实问题。 建立对解的有效控制。 方案实施：将方案应用的实践 中，并检验方案的可行性，若不可行重新进行上述过程。,运筹学解决问题的过程,例1.某工厂生产和两种型号计 算机，生产型和型计算机所需 要原料分别为2和3个单位，需要的 工时分别是4和2个单位。在计划期 内可以使用的原料的100个单位，工 时为120个单位。已知生产每台、 型计算机可获利润分别为6个单位 和4个单位，试确定获得最大利润的 生产方案。,运筹学解决问题的过程,目标函数：,约束条件：,设z为获得

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

9、策论 对策论,运筹学的主要研究内容,参 考 文献,胡运权.运筹学教程M.北京,清华大学出 版社,2002年。 钱颂迪.运筹学M.北京,清华大学出版社,1990年。 郭立夫.运筹学M.长春,吉林大学出版社,2002年。 胡运权.运筹学习题集M.北京,清华大学出 版社,1985年。 刘满凤、付波、聂高飞.运筹学模型与方法教程例题分析与题解M.北京,清华大学出版社,2001年。,线性规划与单纯形法,线性规划（Linear programming） 是运筹学的重要分支，是研究在一组 线性等式或者不等式约束下，使得某 一线性目标函数取得最大（最小）的 极值问题。 1947年美国人丹齐克提出了用于 求解线

10、性规划的单纯形法。,例1.美佳公司计划制造、两种家 电产品。各制造一件时分别占用的设 备A、B的台时、调试时间及每天这 两种家电可用能力、各售出一件时获 利情况如表所示：,问公司应制造两种家电各多少台，使获取的利润最大。,线性规划问题及其 数学模型,线性规划问题及其 数学模型,(1.1c),目标函数,约束条件,(1.1a),(1.1b),(1.1d),max: maximize的缩写， “最大化”， s.t. subject to的缩写， “受限制于”,运筹学基础,第三讲,主讲教师：郑黎黎 学时：48,线性规划问题及其 数学模型,例2 捷运公司在下一年度的14月的4个月内拟 租用仓库堆放物资。

11、已知各月份所需仓库面积 列于表1-2。仓库租借费用随合同期而定，期限 越长，折扣越大，具体数字见表1-3。租借仓库 的合同每月初都可办理，每份合同具体规定租 用面积和期限。因此该厂可根据需要，在任何 一个月初办理租借合同。每次办理时可签一份 合同，也可签若干份租用面积和租借期限不同 的合同，试确定该公司签订租借合同的最优决 策，目的是使所付租借费用最小。,表1-2,单位：100m2,表1-3,单位：元/100m2,月,份,1,2,3,4,所需仓库面积,15,10,20,12,线性规划问题及其 数学模型,用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面

12、积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：,min：minimize ， “最小化”,线性规划问题的特征： 每个问题都用一组未知变量 表示目标函数和约束条件，并且这些变量都是非负的。 有一个目标函数，并且这个目标可表示为一组未知量 的线性函数，目标函数可以是求最大也可以求最小。 存在一组约束条件，这些约束条件都可以用一组未知量线性等式或不等式表示。,线性规划问题及其 数学模型,目标函数：,约束条件：,线性规划问题数学模型的一般形式：,其中： 为价值系数； 为资源系数； 为技术系数，或约束 系

13、数 ；,线性规划问题及其 数学模型,若设： ,，,1. 矩阵式,线性规划问题及其 数学模型,，,2.向量式 3.和式,在后面的公式推导中矩阵式和向 量式用的比较多。,线性规划问题及其 数学模型,线性规划问题数学模型的标准型：,目标函数：,约束条件：,其中： 为价值系数； 为资源系数； 为技术系数，或约束 系数 ；,线性规划问题及其 数学模型,运筹学基础,第四讲,主讲教师：郑黎黎 学时：48,线性规划的标准形式有四个特点 ： 目标最大化、约束为等式、右端项 非负、决策变量均非负。 对于各种非标准形式的线性规划问 题，我们总可以通过以下变换，将 其转化为标准形式。,线性规划问题及其 数学模型,1.

14、极小化目标函数的问题 设目标函数为： 则可以令： ，该极小化问题 与下面的极大化问题有相同的最 优解：,线性规划问题及其 数学模型,2.约束条件不是等式的问题 设约束条件为： 则可在约束的左端加上一个非负 变量 使上面的约束这个不等式 约束变为等式约束：,松弛变量,线性规划问题及其 数学模型,同理，对于不等式约束： 则可在约束的左端减去一个非负变 量 ，则这个不等式约束变为： 这个非负变量称为松弛变量或剩余 变量。,线性规划问题及其 数学模型,线性规划问题的标准型,3.变量无符号限制的问题 在标准形式中，必须每一个变量均 有非负约束。当某一个变量 没有 非负约束时，可以令： 其中， 即用两个非

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

16、和解的概念,例1的可行域表示,利用图解法求解例1的最优解：,线性规划问题的标准型 和解的概念,例1的可行域表示,利用图解法求解例1的最优解：,线性规划问题的标准型 和解的概念,图示目标函数和最优解的确定,(1.1d),查看目标函数和可行域的关系，寻找线性规划问题的最优解。,先将目标函数变为：,求解Q2，得到问题最优值,线性规划问题的标准型 和解的概念,因此，美佳公司每天制造家电 3.5件，家电1.5件，能获得的最 大利润是8.5元。,线性规划问题的标准型 和解的概念, 无穷多个最优解情况,将例1的目标函数变为 ：,(1.1d),线性规划问题的标准型 和解的概念,无界解,例1只包含约束1.1a,

17、(1.1d),线性规划问题的标准型 和解的概念, 无可行解情况 如果约束条件中存在相互矛盾的约束 时，可行域为空，问题无可行解。,线性规划问题的标准型 和解的概念,从图解法可以看到： 当线性规划问题的可行域非空时，它的可行域是有界或无界凸多边形。 若线性规划存在最优解，它一定是在可行域的某个顶点得到；若在两个顶点同时得到，则它们连线上的任意一点都是最优解，即无穷多最优解。,线性规划问题的标准型 和解的概念,从图解法可以看到： 解题思路： 先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点

18、的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。,复习线性代数内容: 列向量 x=(x1，x2，xn）T为n维列向量。xRn 行向量 x=(x1，x2，xn）为n维列向量。xRn 矩阵(向量)运算规则 加减乘、求逆运算 线性相关 一组向量v1,vn,如果有一组不全为零的 系数1, ,n,使得: 1 v1+nvn=0 则称v1,vn 是线性相关的. 线性无关 一组向量v1,vn,如果对于任何数1,n, 若要满足: 1 v1+nvn=0 ,则必有系数 1=n=0,(全为零)则称v1,vn线性无关. 矩阵A的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列

19、向量个数为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中的列向量对应的变量为基变量，记为 其余变量为非基变量，记为 。,，,

20、，,线性规划解的概念,基解：在约束方程组(1.7）中令所有的 非基变量 ，又因为|B| ， 根据克来姆规则，由m个约束方 程可解出m个基变量的唯一解 。 将这个解加上非基变量取0的值有 称X为线性规划问题L的基本解。 基本解的非零分量个数 小于等于 m，当小于m时，则此基解是退化 解，这种现象不多。,，,，,线性规划问题的标准型 和解的概念,约束方程的 解空间,基本解,可行解,非可行解,基 可行解,退化解,线性规划标准型问题解的关系,基可行解： 若B对应的基本解 则称该 解为基本可行解，称B为可行基。,凸集及其顶点,凸集：设C是n维欧式空间的一个点 集，若任意两点的连线上的一切点 ( ),则称

21、 C为凸集。 凸集的特征是：连接任意两点 的线段整个都在集合之中。,凸集及其顶点,顶点：设K是凸集， ,若 不能表 示成任何 两点连线的内 点，则称 为K的一个顶点。,基 本 定 理,定理1：线性规划问题的可行域 是一个凸集. 设： 则 （1.9） 因为： (1.10) 所以： 又因为： 所以： 因此线性规划问题的可行域是凸 集。,基 本 定 理,引理1：线性规划的可行解 是基可行解的充要条件是 的正分量所对 应的系数列向量线性独立。 证明：必要性：根据定义即可证得。 充分性：设 的k个正分量的系数列向量 线性独立，若 ， 刚好构成一个基，从而X就是相应的基可 行解；若 ，则当秩A=m时，一定

22、可以 从A的剩余系数列向量中找到m-k个线性无 关的列与 构成最大线性无关向量 组，构成线性规划问题的一个基，其对应 的基本可行解恰为 。,基 本 定 理,定理2： 线性规划问题的基可行解 对应 线性规划问题的可行域（凸集）顶点。 证明：采用反证法,基 本 定 理,定理2： 线性规划问题的基可行解 对应 线性规划问题的可行域（凸集）顶点。 证明：采用反证法,基 本 定 理,定理2： 线性规划问题的基可行解 对应 线性规划问题的可行域（凸集）顶点。 证明：采用反证法 必要性：不失一般性，假设可行解 前k个 分量为正，故 (1.11) 设 是可行域的顶点，若 不是基可行解 则根据引理1，其正分量对

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

24、基 本 定 理,充分性：设X 是基可行解，则 必线性无关，若X不是可行域D的顶点， 则存在 ，且 ，及 有： 于是，对 有 则 另外： 由于 线性无关故 则 ，与 相矛盾，因此X必 是可行域的顶点。,基 本 定 理,充分性：若X不是可行域D的顶点， 则存在 ，且 ，及 有： 于是，对 有 则 另外： 则 因 ，所以 故 线性相关，即X不是基可行 解。,基 本 定 理,定理3 ：若线性规划问题有最优解，一定 存在一个基可行解（可行域顶点）是最优 解。 证明：设X是最优解， 是可行域的k个顶点 ，若X不是顶点，则X 可以表示为可行域k个顶点的凸组合，表 示为： 因此：,基 本 定 理,另外，在所有

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

26、,运筹学基础,第六讲,主讲教师：郑黎黎 学时：48,，,确定下面线性规划问题的初始基可行解,确定初始基可行解,大M法： 若给定问题标准化后，系数矩阵中 不存在m个线性无关的单位列向量， 则在某些约束的左端加入非负变量 （人工变量），使得变化后的系数 矩阵中恰有m个线性无关的单位列向 量，并且在目标函数中减去这些人 工变量与M的乘积（M是相当大的一 个正数）。对于变化后的问题，取 这m个单位列向量构成的单位矩阵为 初始基，该基对应的解一定是基可 行解。,确定初始基可行解,关于大M法的几点结论: 若原问题存在最优解X*，则变化 后的问题也存在最优解（X*，0）且后 者的最优解就是原问题的最优解。

27、若经过单纯形法迭代后变化后问 题的最优解中含有不等于零的人工 变量，则原问题无可行解。,用M法确定下面线性规划问题的初始基可行解,从一个基可行解转换为 相邻基可行解,定义：两个基可行解称为相邻的，如果它们之 间变换且仅变换一个基变量。 设初始基可行解中的前m个为基变量，即： （1.19）,带入等式约束中,因 是一个基，其他向量 可用 这个基的线形组合来表示，有 （1.） + （.）,从一个基可行解转换为 相邻基可行解,乘,由式（1.22）找到满足约束方程组 时 是非负的。,从一个基可行解转换为 相邻基可行解,因 ，故由上述矩阵元素组成的行列 式不为零， 是一个基 在上述增广矩阵中进行行的初等变

28、换， 将第行乘上（ ），再分别乘以（ ） 加到各行上去，则增广矩阵左半部变成 为单位矩阵，又因 故,从一个基可行解转换为 相邻基可行解,最优性检验和解的判别,将 和 分别带入目标函数得 ：,（） 或,最优性检验和解的判别,（1）当所有的 时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明及凸集的性质，可以判定现有顶点的基可行解即为最优解。 （2）当所有的 ，又对某个非基变量有 ，且按式（1.24）可以找到 ，这表明可以找到另一个顶点（基可行解）目标函数值也达到最大。由于该两点连续的点也属可行域内的点，且目标函数值相等，即该线

29、性规划问题有无穷多最优解。,最优性检验和解的判别,（3）如果存在某个 ，又 ，由式（1.23）看出对任意的 ，均有 ，因而 取值可为无限增大不受限制。由式（1.25）看到 也可无限增大，表明线性规划有无界解。,（）,定理4（最优性）对某基可行解 其余 ，若所有 ，则该解为最优解。 定理5 （无界解）若对某可行基 B，若存在 ，则该线性规 划问题无有限最优解（或称无最优 解）。,最优性检验和解的判别,求解例1的一个基可行解和相应的检 验数，并判断其是否最优解。,最优性检验和解的判别,单 纯 形 表,将式子（1.7a）和（1.6a）变化为，,增广矩阵,j =cj-CBB-1Pj,基变量值,基变量,

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

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

32、步骤,1.确定初始基B和初始基可行解 建立初始单纯形表； 2.检查非基变量的检验数，若所有 的 ，则已经得到最优解 计算停；否则求 确定xk为旋入变量； 3.若对于 ，则 此问题无有限最优解，计算停；否 则转入步骤4；,单纯形算法步骤,4. 计算 确定xBl为旋出变量。 5. 以 为主元做旋转变换得新的单纯形表，转步骤2。,解：,表1-7,cj,例5用单纯形法求解下面的线性规划问题,表1-7,cj,cj,0,1/6,0,2/6,1,4,x1,2,0,-1/3,0,1/3,0,1,-1/6,0,4/6,0,1,x5,0,0,0,1,5,0,15,x3,0,x5,x4,x3,x2,x1,B-1b,

33、0,0,0,1,2,XB,CB,表1-8,cj,x5,x4,x3,x2,x1,B-1b,0,0,0,1,2,XB,CB,cj,表1-9中所有j=0, 最优解 X=(7/2, 3/2, 15/2, 0, 0) ; 最优值 Z=17/2.,运筹学基础,第八讲,主讲教师：郑黎黎 学时：48,单纯形算法步骤,习题1 计算下列线性规划 取 为初始基 为初始基可行 解,例6用单纯形法求解下面的线性规划问题,cj,cj,运筹学基础,第九讲,主讲教师：郑黎黎 学时：48,cj,单纯形法的进一步讨论,如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时

34、取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。,单纯形法的进一步讨论,两阶段法： 第一阶段（目的是求解该问题的一个 初始基可行解）： 求解一个目标函数 中只包含人工变量的线性规划问题， 即令目标函数中其它变量的系数取 零，人工变量的系数取某个正的常数 (一般取1)，在保持原问题约束条件不 变的情况下求这个目标函数极小化时 的解。显然在第一阶段中，当人工变 量取值为0时，目标函数值也为0。这 时候的最优解就是原线性规划问题的 一个基可行解。,单纯形法的进一步讨论,两阶段法： 如果第一阶段求解结果最优解的目标 函数值不为0

35、，也即最优解的基变量 中含有非零的人工变量，表明原线性 规划问题无可行解。 第二阶段：将第一阶段得到的基可行 解作为原问题的初始基可行解，然后 按照单纯形法求解原问题的最优解。,例6 两阶段法,第一阶段：,cj,请注意: 第一阶段的最优解不是唯一的,cj,cj,第二阶段,cj,cj,第二阶段,cj,cj,单纯形法小解,线性规划应用举例,例9 混合配料问题 某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量、原料成本、各种原料的每月限制用量，三种牌号糖果的单位加工费及售价，如表1-17所示。问该厂每月生产这三种牌号糖果各多少kg，才能使其获利最大。试建立

36、这个问题的线性规划的数学模型。,运筹学基础,第十讲,主讲教师：郑黎黎 学时：48,解 用i=1,2,3分别代表原料A，B，C，用j=1,2,3分别代表甲、乙、丙三种糖果，xij为生产第j种糖果耗用的第i种原料的kg数量。该厂的获利为三种牌号糖果的售价减去相应的加工费和原料成本，三种糖果的生产量分别为： x甲，x乙，x丙,线性规划应用举例,解 用i=1,2,3分别代表原料A，B，C，用j=1,2,3分别代表甲、乙、丙三种糖果，xij为生产第j种糖果耗用的第i种原料的kg数量。该厂的获利为三种牌号糖果的售价减去相应的加工费和原料成本，三种糖果的生产量分别为： x甲，x乙，x丙,线性规划应用举例,线

37、性规划应用举例,线性规划应用举例,线性规划应用举例,例10 产品计划问题 某厂生产,三种产品，都分别经A，B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1, B2,和B3三种设备可用于完成B工序。已知产品I可在A和B任何一种设备上加工；产品可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品只能在A2 与B2设备上加工。加工单位产品所需工序时间及其它各项数据见表118，试安排最优生产计划，使该厂获利最大。,线性规划应用举例,线性规划应用举例,线性规划应用举例,例11 动态投资问题 宏银公司承诺为某建设项目从2003年起的4年中每年初提供以下数额贷款：2003年10

38、0万元，2004年150万元， 2005年120万元，2006年110万元。以上贷款资金均需于2002年底前筹集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目。 （1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元； （2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，但限购90万元； （3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元； 于每年初将任意数额的资金存放于银行，年息4%，于每年底取出。 问宏银公司如何运用好这笔资金，使2002年底需筹集到的资金额为最少。,