- 1、本文档共100页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
运筹与组合
(注意:本文件的显示、打印需要公式编辑器的支持。)
运 筹 与 组 合
山东大学学院
二OO年月
:
刁在筠等,运筹学,高等教育出版社,2001
Richard A. Brualdi, Introductory Combinatorics, Printice Hall, Inc., 1999
卢开澄,组合数学,清华大学出版社
朱大铭,算法设计与分析,高教出版社。
目 录
第一篇 运筹学 1
第一章 线性规划 1
§1 线性规划问题及数学模型 1
§2 图解法 6
§3 单纯形法解LP问题 8
§4 对偶线性规划 13
第二章 整数规划 17
§1 整数线性规划问题 17
§2 整数线性规划问题解法 18
第三章 动态规划 20
§1 最优化原理 20
§2 用最优化原理解非线性规划问题 22
§3 动态规划算法设计 23
第四章 网络分析 30
§1 图及网络 30
§2 网络上的优化问题 31
第二篇 组合数学 43
第五章 排列组合 43
§1 和、积的原则 43
§2 排列 44
§3 重复排列 46
§4 组合 51
§5 组合等式及意义 54
§6 排列与组合的生成 54
第六章 容斥原理与鸽巢原理 57
§1 容斥原理 57
§2 鸽巢原理 62
§3 有重复元素的圆排列问题 66
第七章 母函数与递推关系 71
§1 用母函数解递推关系 71
§2 用母函数解整数拆分问题 76
§3 用指数型母函数解错排问题 79
第八章 Polya 计数定理 82
§1 Burnside引理 82
§2 Polya定理 88
运筹学
线性规划
§1 线性规划问题及数学模型
例2 某工厂用3种原料P1,P2,P3生产3种产品Q1,Q2,Q3。已知的条件如下表所示,制定出总利润最大的生产计划。
Q1 Q2 Q3 原料可用量
(kg /日) P1 2 3 0 1500 P2 0 2 4 800 P3 3 2 5 2000 单位产品利润
(千元) 3 5 4
线性规划(LP)问题的一般形式
(等式不都在前面怎么办?非负变量不都在前面怎么办?)
目标函数
价值系数 , 价值向量
决策变量 , 决策向量
约束,约束矩阵
右端向量
Ax = ? b
非负约束
自由变量
可行解、可行点 满足约束的点
可行域D
最优解
LP问题的规范形式
一般形式中p=0, q=n 时,称为规范形式。
一般形式与规范形式的转化
将化为
令
例:将下面的线性规划转化为规范形式
解:
,
,,
,
LP问题的标准形式
一般形式中p=m, q=n 时,称为标准形式。
一般形式与标准形式的转化
对
,,
令
这里的称为剩余变量。
例:将下面的线性规划转化为标准形式
解:
,
§2 图解法
z在(1,4)点达到最大值3。
例2 用图解法解线性规划
例3 用图解法解线性规划
无最优解
关于可行域D与最优解的讨论:D=?,无解、不可行;D≠?,无界;D≠?,有最优解。
§3 单纯形法
设r(A)=m,A的前m列为线性无关。(注意各向量、矩阵的维数)
将A分为左右两块,左边m列为可逆方阵B,右边记为N。(左面m列是不是一定可逆?)
对应将价值向量c和决策向量x的前m行与后n-m行分开,
,,
,
令,则
,
且
。
原LP问题变形为
若取,则得一个满足等式约束的解
,
其对应的指标值为 。
B称为基,
B的列称为基向量,
称为基本解,
时称为基本可行解,此时B称为可行基
时称为非退化的基本可行解。
下面假设我们要讨论的LP问题对所有的可行基B,都有。
定理 若标准LP问题有可行解,则必有基本可行解;若有最优解,则一定存在一个基本可行解是最优解。(证明略)
定理 若,则是最优解。
证 。
定理 若的第k个分量,且,则该LP问题无界。这里Ak表示矩阵A的第k列。
证 取,(这是一个n维的列向量,第k个分量为1,其余分量为0。)令取(下面说明此x是可行解,且其指标值要多小有多小。)
定理 若的第k个分量,且中存在正分量,则,使得且。
证 令(见前面定理中的定义,这里但不能任意取。)
1)可以适当取使得为可行解:
由
知道;
要使得即,只需
,
设 由等知道
取即可。
2)
这里,但因为不能任意取大数,所以指标不能任意小。
§4 对偶线性规划
是约束矩阵A的第i行,Aj是约束矩阵A的第j列。
规范形式的对偶问题为
标准形式的对偶问题为
2.对偶理论
定理 如果一个LP问题有最优解,则它
您可能关注的文档
- 迁想妙得教学设计.doc
- 过程模式example.doc
- 过空间任意点引条直线,它们所确定的平面的个数.doc
- 迎春杯分类计数与数论答案及详解.doc
- 迈克耳孙干涉仪的调和使用实验报告.doc
- 迎考复习.doc
- 运动神经元病例.doc
- 运放稳定性.doc
- 运筹与决策最优解问题.doc
- 运筹学B卷期末考试.doc
- 教科版(2017秋)科学二年级上册2.6 做一顶帽子 教学设计.docx
- 河北高频考点专训四 质量守恒定律的应用教学设计---2024-2025学年九年级化学人教版(2024)上册.docx
- 大单元教学【核心素养目标】6.3 24时计时法教学设计 人教版三年级下册.docx
- 河南省商城县李集中学2023-2024学年下学期九年级历史中考模拟八(讲评教学设计).docx
- 第18章 第25课时 正方形的性质2023-2024学年八年级下册数学课时分层作业教学设计( 人教版).docx
- Module 8 模块测试 教学设计 2024-2025学年英语外研版八年级上册.docx
- 2024-2025学年小学数学五年级下册浙教版教学设计合集.docx
- 2024-2025学年小学劳动四年级下册人民版《劳动》(2022)教学设计合集.docx
- 2024-2025学年小学数学三年级上册冀教版(2024)教学设计合集.docx
- 2024-2025学年高中生物学必修1《分子与细胞》人教版教学设计合集.docx
最近下载
- 第四单元跨学科实践活动3水质检测及自制净水器课件---2024-2025学年九年级化学人教版(2024)上册.pptx VIP
- 小学英语教科版四年级上册 Module 6 Occupations 大单元整体教学.docx
- 消防文员岗位履职能力考核(新闻宣传岗位)理论考试题库 (含答案).docx
- 小学语文下册《真理诞生于一百个问号之后》第二课时说课稿及教学反思.pdf
- 从庆余年看优秀网络文学IP如何影视化.docx
- 2024年新北师大版七年级上册数学课件 第二章 2.5 第1课时 有理数的混合运算.pptx
- 睡眠障碍:改善睡眠质量的策略.pptx VIP
- 2024秋苏教版七年级生物(上册)全册教案.pdf
- 2021-2022学年江苏省扬州市仪征市七年级上学期期末考试数学试卷(含详解).docx VIP
- 帕金森病睡眠障碍.pptx VIP
文档评论(0)