运筹学 (05第五讲)第五次课单纯形法.pptVIP

  1. 1、本文档共84页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
[ ] [ ] (请解释其实际意义) 练习:用单纯形法求解下面的线性规划 [ ] 注:1. 表上每一列的含义: 2. 每张表上B-1的位置在哪?——对应于初表中I 的位置。 [ ] [ ] [ ] 例6: 填表: 练习:用单纯形法求解下面的线性规划 [ ] 问题:本题的单纯形终表检验数有何特点? —— 非基变量x2 的检验数等于零。 注:(1)解的几种情况在单纯形表上的体现(Max型): - 唯一最优解:终表非基变量检验数均小于零; - 多重最优解:终表非基变量检验数中有等于零的; - 无界解:任意表有正检验数相应的系数列均非正。 (2) Min型单纯形表与Max型的区别仅在于:检验数反号,即 - 令负检验数中最小的对应的变量进基; - 当检验数均大于等于零时为最优。 几个定理 定理1 若线性规划问题存在可行域,则其可行域 是凸集 引理 1 线性规划问题的可行解X=(x1,x2,…,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。 定理2 线性规划问题的基可行解X对应于可行 D的顶点。 引理2 若K是有界凸集,则任何一点X∈K可表示为K的顶点的凸组合。 本引理证明从略,用以下例子说明这引理。 例5 设X是三角形中任意一点,X(1),X(2)和X(3)是三角形的三个顶点,试用三个顶点的坐标表示X(见图1-8) 解 任选一顶点X(2),做一条连线XX(2);并延长交于X(1)、X(3)连接线上一点X′。因X′是X(1)、X(3)连线上一点,故可用X(1)、X(3)线性组合表示为 X′=αX(1)+(1-α)X(3) 0<α<1 又因X是X′与X(2)连线上的一个点,故 X=λX′+(1-λ)X(2) 0<λ<1 将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) ∑iμi=1,0<μi<1 定理 3 若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。 * * 三、单纯形表 单纯形表是基于单纯形法的步骤设计的计算格式,是单纯形法的具体实现。 回顾单纯形法步骤 单纯形表的主要结构: 问题:第一张表的B-1=? ——单位阵I。 检验数的公式是什么? 例5:用单纯形法求解例1 问题:标准模型的A中是否含I? ——松弛变量系数恰好构成I。 [ ] [ ] 中表示进基列与出基行的交叉元,下一张表将实行以它为主元的初等行变换(称高斯消去)。方法是:先将主元消成1,再用此1将其所在列的其余元消成0。 单纯形法 单纯形法是求解线性规划的主要算法,1947 年由美国斯坦福大学教授丹捷格(G.B.Danzig) 提出。 尽管在其后的几十年中,又有一些算法问世, 但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率。 1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型: 标准型的特征:Max型、等式约束、非负约束 一、单纯形法的预备知识 非标准形式如何化为标准 1) Min型化为Max型 加负号 因为,求一个函数 的极小点,等价于求该 函数的负函数的极大点。 注意: Min型化为Max型求解后,最优解不变,但最优值差负号。 2) 不等式约束化为等式约束 分析:以例1中煤的约束为例 之所以“不等”是因为左右两边有一个差额,称为“松 弛量”,若在左边加上这个松弛量,则化为等式。而这 个松弛量也是变量,记为X3 ,则有 X3称为松弛变量。问题:它的实际意义是什么? —— 煤资源的“剩余”。 练习:请将例1的约束化为标准型 解:增加松弛变量 则约束化为 易见,增加的松弛变量的系数恰构成一个单位阵I。 一般地,记松弛变量的向量为 Xs,则 问题:松弛变量在目标中的系数为何? —— 0。 3) 当模型中有某变量 xk 没有非负要求,称 为自由变量, 则可令 化为标准型。 2.基本概念 (1)可行解与最优解 直观上,可行解是可行域中的点,是一个可行的

文档评论(0)

***** + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档