- 1、本文档共20页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
第一章线性规划与单纯性法
1、线性规划问题的数学模型及各要素的基本特征
线性规划问题的三个要素的基本特征
(1)决策变量:每一个问题都用一组决策变量(x1,x2,…,xn)表示某一方案,这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的。
(2)约束条件:存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示。
(3)目标函数:都有一个要求达到的目标,它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同,要求目标函数实现最大化或最小化。
数学模型,其一般形式为:
标准型式为:
其中,xj(j=1,2,...,n)为决策变量,aij(i=1,2,...,m;j=1,2,...,n)为工艺系数,bi(i=1,2,..,m)为资源系数,cj(j=1,2,...,n)为价值系数。
2、如何将线性规划问题转变为标准型
若目标函数要实现最小化,minZ=CX。需将最小化转变为最大化,令Z’=-Z,的maxZ’=-CX。
约束方程为不等式
A:约束方程为≤的不等式,左端加入非负松弛变量。
B:约束方程为≥的不等式,左端减去非负松弛变量。
若变量xk无约束时,令xk=xk’-xk’’,xk’,xk’’≥0
3、可行解,基,基可行解,可行基的概念及相互关系
可行解:满足约束方程不等式,并且满足xk≥0,称为线性规划问题的可行解。其中使目标函数达到最大值的可行解称为最优解。
基:设A是约束方程组m×n维系数矩阵,其秩为m,B是矩阵A中的m×m阶的非奇异子矩阵,则称B为线性规划问题的一个基。
基可行解:满足非负条件(xk≥0)的基解,称为基可行解。
可行基:基可行解对应的基,称为可行基。
解的几何意义
5、线性规划问题的几何意义
定理1:“若线性规划问题存在可行域,则其可行域是凸集”,要会证明。
引理1:“线性规划问题的可行解X=(x1,x2,?,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的”,要会证明(记住从必要性和充分性两方面证明)。
定理2“线性规划问题的基可行解X对应于可行域D的顶点。”要会证明(利用反证法,从两个方面证明)。
定理3“若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优”要会证明。
6、单纯形法求解线性规划的思路
一般线性规划问题具有线性方程组的变量数大于方程个数,这时有不定的解。但可以从线性方程组中找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小,决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。(从可行域中的某个基可行解开始到另一个基可行解,直到目标函数达到最优)
7、线性规划解的判别定理
8、单纯形法的计算步骤
9、单纯形法的进一步讨论
(1)大M法
在一个线性规划问题的约束条件中加进人工变量后,要求人工变量对目标函数取值不受影响,为此假定人工变量在目标函数中的系数为(-M)(M为任意大的正数),这样目标函数要实现最大化时,必须把人工变量从基变量换出。否则目标函数不可能实现最大化。
(2)两阶段法
第一阶段:不考虑原问题是否存在基可行解;给原线性规划问题加入人工变量,并构造仅含人工变量的目标函数和要求实现最小化。
然后用单纯形法求解上述模型,若得到ω=0,这说明原问题存在基可行解,可以进行第二段计算。否则原问题无可行解,应停止计算。
第二阶段:将第一阶段计算得到的最终表,除去人工变量。将目标函数行的系数,换原问题的目标函数系数,作为第二阶段计算的初始表。
10、退化解及勃兰特规则
退化:单纯形法计算中用θ规则确定换出变量时,有时存在两个和两个以上最小比值,这样在下一次的迭代中就有一个或者几个基变量等于零,这就出现退化解。
勃兰特规则:(1)选取cj-zj0中下标最小的非基变量xk为换入变量。
(2)当按θ规则存在两个和两个以上最小比值时,选取下标最小的基变量为换出变量时。
11、(实际问题)建立线性规划模型的条件
(1)要求解问题的目标函数能用数值指标来反映,且为线性函数;
(2)存在着多种方案;
(3)要求达到的目标是在一定约束条件下实现的,这些约束条件可用线性等式或不等式来描述。
12、图解法
第二章对偶理论和灵敏度分析
1、对偶问题的基本性质
(1)对称性:对偶问题的对偶是原问题。
(2)弱对偶性:若X是原问题
您可能关注的文档
- 八年级物理学法指导.pptx
- 硬件研发岗位笔试试题.pdf
- 咳嗽完整版本.ppt
- 幼儿园保健宣传小常识.docx
- 《安徒生童话》读后感(6篇).docx
- 建筑垃圾采购合同书.doc
- 班委申请表完整版本.doc
- 2024班主任第一学期工作总结(2篇).docx
- 电商培训课程课件.pptx
- 常见病的影像学诊断课件.pptx
- 2024至2030年中国液晶可视对讲门铃行业投资前景及策略咨询研究报告.docx
- 2024年5月广东深圳市龙华区区属公办中小学招考聘用教师186人笔试历年典型考点解题思路附带答案详解.docx
- 2024年08月广东中共广州市越秀区纪律检查委员会第二次公开招聘工作人员4人笔试历年典型考点解题思路.docx
- 2024年中国地坛钟市场调查研究报告.docx
- 2024年08月云南省曲靖市能源局公开招考1名编外聘用人员笔试历年典型考点解题思路附带答案详解.docx
- 2024至2030年中国天鹅绒九分裤袜数据监测研究报告.docx
- 2024至2030年中国水果橱行业投资前景及策略咨询研究报告.docx
- 2024年08月广西河池市南丹县信息中心就业见习基地公开招聘见习大学生5人笔试历年典型考点解题思路附.docx
- 2024至2030年中国封堵行业投资前景及策略咨询研究报告.docx
- 2024至2030年中国蒸汽压力测控系统行业投资前景及策略咨询研究报告.docx
最近下载
- 东华大学-配位化学-期末复习试卷.pdf VIP
- 1.3.太空探索课件-初中地理商务星球版(2024)七年级上册.pptx VIP
- 人才引进计划加速区域一体化的重要方式.pptx
- 高考语文理解性默写题.doc VIP
- 通桥(2018)5401-08高速铁路钢筋混凝土框架箱涵.pdf
- 离婚协议书(完整版)范本.docx VIP
- 2024楼顶发光字制作安装合同.docx
- 无线覆盖施工方案.docx VIP
- PEP英语五年级下册Unit 2 My favourite season单元整体作业设计.pdf VIP
- 《深度报道:理论、实践与案例》课件ppt张志安 第一章 深度报道的内涵及操作路径.pptx VIP
文档评论(0)