第1章3线性规划及单纯形法.ppt

  1. 1、本文档共131页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第1章3线性规划及单纯形法

1.2 线性规划问题解的基本理论 一、LP问题的各种解 可行解、最优解(最优值) 1、可行解:满足约束条件和非负条件的决策变量的一组取值。 2、最优解: 使目标函数达到最优值的可行解。 3、最优值:最优解对应目标函数的取值。 即: 二、与线性规划问题解有关的基本概念 1.基:设A是约束方程组m×n的系数矩阵, A的秩R(A)=m,B是A中m×m阶非奇异子式, 即|B|≠0, 则称B是LP问题的一个基。 基向量、基变量、非基变量、基本解? 不妨设: 结合图形法分析 求解线性规划问题的基本思路 1、构造初始可行基; 2、求出一个基本可行解(顶点) 3、最优性检验:判断是否最优解; 4、基变化,转2。要保证目标函数值比原来更优。 练习2:教材p31 4(2)、2(1) 列出初始单纯形表: 列出初始单纯形表: (3)max z = 3x1 + 6x2 s.t. x1 - 2x2 ? -2 x1 + 2x2 ? 6 x1 , x2 ? 0 解:化问题为标准型 max z = 3x1 + 6x2 +0x3 +0x4 s.t. -x1+ 2x2 +x3 = 2 x1+2x2 + x4 = 6 x1 , x2 , x3 , x4 ? 0 因为检验数全小于等于零,得最优解: X (1) =(2/3,8/3,0,0)T , z*= 18. 又因为非基变量x3对应的检验数等于0,所以有无穷多最优解。 X(2)=(15,20,0,0)t 相当于Q2(15,20) 例2: 求解线性规划问题: min S = x1 - x2 s.t. -x1+ x2 ? 2 2x1- x2 ? 2 x1 , x2 ? 0 解:化标准型: max S? = -x1+x2 s.t. -x1+ x2 +x3 = 2 2x1 - x2 +x4 = 2 x1 , x2 , x3 , x4 ? 0 列出初始单纯形表: 计算检验数,确定进基变量、出基变量,找到主元: 进行初等行变换: 再计算检验数: 因为检验数全小于等于零,得最优解: X=(0,2,0,4) S?=2 S = -2 注意:虽然所有检验数全小于等于零,但非基变量x1对应的检验数=0,若以x1进基,x4出基,其最优值不变。 进行初等行变换 计算检验数: 因为检验数全小于等于零,得另一个最优解:X=(4,6,0,0)S?=2 S = -2 根据解的性质: 最优解 X(1)=(0,2,0,4)t, X(2) =(4,6,0,0)t 连线上的点仍是最优解: X=? X(1) +(1- ?) X(2) (0 ? ? ? 1) 因此,本题有无穷多组最优解。 例3 求解线性规划问题: max S= 2x1+x2 s.t. x1 - x2 ? -5 2x1 - 5x2 ? 10 x1 , x2 ? 0 解:化标准型: max S = 2x1 + x2 s.t. -x1+ x2 +x3 = 5 2x1 - 5x2 +x4 = 10 x1 , x2 , x3 , x4 ? 0 列出初始单纯形表: 计算检验数,确定进基变量、出基变量,找到主元: 进行初等行变换 再计算检验数,确定进基变量为x2: 由于进基变量X2所对应的系数全都小于0, 所以原问题无最优解. 课堂作业: 单纯形法求解线性规划问题 (1) min S = x1 - 3x2 + 2x3 + 4x4 s.t. 2x1+ 4x3 +x4 = 6

文档评论(0)

liudao + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档