运筹学复习2012
- 格式：pdf
- 大小：323.33 KB
- 文档页数：14
文档推荐
-
运筹学清华版习题答案(第五章)页数:34
-
管理运筹学选择题题库页数:6
-
20192020运筹学期末考试试题及答案页数:6
-
运筹学试题与答案(武汉理工大学)页数:11
-
2012年运筹学期末考试复习题(含答案)页数:5
-
运筹学上机习题(2012)页数:3
下载文档原格式
合集下载
运筹学复习课件
b1 b2 … bn
销地 1 产地
2… n
1
c11 c12 … c1n
2
c21 c22 … c2n
┆
┆ ┆ ┆┆
m
cm1 cm2 … cmn
产量 xij为产地i运往
a1 销地j的物资数量 a2
┆ 产销平衡表
am
xij和cij一一对应
单位运价表
销地 B1 B2 B3 B4 产地
A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5
σj
2 0 0 0 -3/5
23000
CB XB b 2 x1 3 0 x4 4 3 x2 3
σj
x1 x2 x3 x4 x5
1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5
最优解为：X*=(3,3,0,4,0)T， 最优值为：Z*=14
解的情况判别
步骤如下： 1.确定换出基变量
其对应变量xr为换出基的变量。 2.确定换入基变量
令 xs为换入基的变量，ars为主元素。
3.迭代 用换入替换换出变量，得到一个新的基。
再检查
(i=1, …,m) ？
灵敏度分析
bi c j
参数变化后，问题的最优解如何变化？
bi的变化
b b' b b B 1b B 1b' B 1b b
《运筹学》复习课 ------你懂得
考试题型
填空题（20） 选择题（18） 判断题（20） 计算与应用（42）
考试时间
拟定于元月5号，具体时间请等候通知！ 请稍安勿躁！ 做好自己的事情，同时加强复习！！ 祝大家都能通过！
销地 1 产地
2… n
1
c11 c12 … c1n
2
c21 c22 … c2n
┆
┆ ┆ ┆┆
m
cm1 cm2 … cmn
产量 xij为产地i运往
a1 销地j的物资数量 a2
┆ 产销平衡表
am
xij和cij一一对应
单位运价表
销地 B1 B2 B3 B4 产地
A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5
σj
2 0 0 0 -3/5
23000
CB XB b 2 x1 3 0 x4 4 3 x2 3
σj
x1 x2 x3 x4 x5
1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5
最优解为：X*=(3,3,0,4,0)T， 最优值为：Z*=14
解的情况判别
步骤如下： 1.确定换出基变量
其对应变量xr为换出基的变量。 2.确定换入基变量
令 xs为换入基的变量，ars为主元素。
3.迭代 用换入替换换出变量，得到一个新的基。
再检查
(i=1, …,m) ？
灵敏度分析
bi c j
参数变化后，问题的最优解如何变化？
bi的变化
b b' b b B 1b B 1b' B 1b b
《运筹学》复习课 ------你懂得
考试题型
填空题（20） 选择题（18） 判断题（20） 计算与应用（42）
考试时间
拟定于元月5号，具体时间请等候通知！ 请稍安勿躁！ 做好自己的事情，同时加强复习！！ 祝大家都能通过！
运筹学 本(复习资料)
《运筹学》课程复习资料一、判断题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
[ ]2.线性规划问题的每一个基本解对应可行解域的一个顶点。
[ ]3.任何线性规划问题存在并具有惟一的对偶问题。
[ ]4.已知y i*为线性规划的对偶问题的最优解，若y i*＞0，说明在最优生产计划中第i种资源已完全耗尽。
[ ] 5.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。
[ ]6.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。
[ ]7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。
[ ]8.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。
[ ]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。
[ ]10.用大M法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。
[ ]11.如图中某点vi 有若干个相邻点,与其距离最远的相邻点为vj,则边[vi,vj]必不包含在最小支撑树内。
[ ]12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。
[ ] 13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。
[ ] 14.在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。
[ ]15.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。
[ ]16.订购费为每订一次货所发生的费用，它同每次订货的数量无关。
[ ]17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。
《运筹学》总复习
三、LP建模
（1）产品计划问题 （2）产品配套问题 （3）合理下料问题 （4）合理配料问题
（5）进货与销售计划问题
求解算法
单纯形法 大M法 两阶段法
思考讨论题
（1）判断是否为可行域的顶点
（2）标准型及其转化方法 （3）从最优单纯形表格中，如何确定原问题
有唯一解、无穷多个最优解、无解、无有限 最优解？
（9）LP的标准型，其可行解不一定是基本可行
解； （10）最优解一定是可行解； （11）最优解一定可以在可行域的顶点上达到； （12）最优解不一定是基本可行解； （13）线性规划标准型 （14）大M法和两阶段法的原理
二、判断正误（√or
×）
（1）若线性规划问题的可行域无界，则该现系
表7.10 设备的年初购置费 年分
购置费（万元）
1 11
2 11
3 11
4 12
5 13
表7.11 设备维修费 使用年限 0～1 1～2 2～3 3～4 4～5 6 9 11 18
年维修费（万元） 5
（3）最小费用最大流问题的实质是当最大流
不唯一时，在这些最大流中求一个费用最小 的流。试问： ①能否判断最大流的唯一性？ ②如果在所有的可行流中选择费用尽量小、 流量尽量大的一个流，这就成了一个两个目 标的多目标规划问题，试建立一个这样的多 目标规划模型。 （4）最大流问题中，若将目标函数改成min 的最小费用问题，试考虑求最大流的方法是 否同样适用。
第3章 运输问题
一、选择填空
闭回路的特点 有关闭回路的理论结果 运输问题系数矩阵的秩 m n 1 个变量构成基变量的充要条件
二、求解算法
初始基本可行解（最小元素法和西北角法） 求检验数（闭回路法和位势法）
运筹学复习题及参考答案
《运筹学》一、判断题：在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“T”，错误者写“F”。
1. T2. F3. T4.T5.T6.T7. F8. T9. F10.T 11. F 12. F 13.T 14. T 15. F1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。
( T )2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C j-Z j≤0，则问题达到最优。
( F )3. 若线性规划的可行域非空有界，则其顶点中必存在最优解。
( T )4. 满足线性规划问题所有约束条件的解称为可行解。
( T )5. 在线性规划问题的求解过程中，基变量和非机变量的个数是固定的。
( T )6. 对偶问题的对偶是原问题。
( T )7. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的。
( F )8. 运输问题的可行解中基变量的个数不一定遵循m＋n－1的规则。
( T )9. 指派问题的解中基变量的个数为m＋n。
( F )10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。
( T )11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。
( F)12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往是不相等。
( F )13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。
(T )14. 单目标决策时，用不同方法确定的最佳方案往往是不一致的。
( T )15. 动态规则中运用图解法的顺推方法和网络最短路径的标号法上是一致的。
( F )二、单项选择题1.A2.B3.D4.B5.A6.C7.B8.C9. D 10.B11.A 12.D 13.C 14.C 15.B1、对于线性规划问题标准型：maxZ=CX, AX=b, X≥0, 利用单纯形法求解时，每作一次迭代，都能保证它相应的目标函数值Z必为（ A ）。
运筹学2012年复习
•
• • • • • • • • • • • •
NO. ITERATIONS=
2
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 13.500000 1.750000 INFINITY X2 8.800000 1.400000 1.800000 X3 10.500000 2.700000 0.700000 RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 350.000000 202.000000 43.333332 460.000000 65.000000 168.333328
运筹学： 线性规划
x1 x2 x3 1 x2 x4 x1 x3 1
运筹学： 线性规划
<习题7> 某校篮球队准备从六名预备队 员中选拔三名为正式队员，并 使平均身高尽可能高。这六名 预备队员情况如表所示，队员 的挑选要满足如下条件： （１）至少补充一名后卫对员； （２）大李和小田之间只能入选 一个 （３）最多补充一名中锋 （４）只要大李或小赵入选，小 周就不能入选
运筹学： 线性规划
某个中型百货商场对售货人员（周工资200元）的 需求经统计如下表； 为了保证销售人员充分休息，销售人员每周连续工作5 天，连续休息2天。问应如何安排销售人员的工作时 间，使得所配售货人员的总费用最小？
星期
人数
一
12
二
15
三
12
(完整word版)最全的运筹学复习题及答案
5、线性规划数学模型具备哪几个要素？答：（1）.求一组决策变量x i或x ij的值（i =1，2，…m j=1，2…n）使目标函数达到极大或极小；（2）。
表示约束条件的数学式都是线性等式或不等式；(3）。
表示问题最优化指标的目标函数都是决策变量的线性函数第二章线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。
2．图解法适用于含有两个变量的线性规划问题.3．线性规划问题的可行解是指满足所有约束条件的解。
4．在线性规划问题的基本解中，所有的非基变量等于零.5．在线性规划问题中,基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。
7．线性规划问题有可行解，则必有基可行解。
8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解.9．满足非负条件的基本解称为基本可行解。
10．在将线性规划问题的一般形式转化为标准形式时,引入的松驰数量在目标函数中的系数为零。
11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。
12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。
13．线性规划问题可分为目标函数求极大值和极小_值两类。
14．线性规划问题的标准形式中，约束条件取等式,目标函数求极大值,而所有变量必须非负。
15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时,如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解. 17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。
18。
如果某个约束条件是“≤"情形,若化为标准形式，需要引入一松弛变量。
19。
如果某个变量X j 为自由变量，则应引进两个非负变量X j ′ ， X j 〞， 同时令X j ＝X j ′－ X j 。
运筹学课程复习
m z = ∑ j xj ax c
j =1 n
n , , ∑aij xj =bi (i =1 2,L m) j=1 xj ≥0 ( j =1 2,L n) , ,
式的解称为可行解。 (1 ) 全部可行解的集合称为可 可 行域。 行域 最优解：使目标函数（1） 最优解 (2) 达到最大值的可行解称为最优 (3) 解。
重点复习内容
第一章 线性规划及单纯形法
§1 - 1 §1 - 2 §1 - 3 §1 - 4 §1 - 5 线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论
2012-5-15
2
组成线性规划模型的三个要素
目标函数：max Z＝2x1＋x2 5x2≤15 6x1＋2x2≤24 约束条件 x1＋x2≤5 x1，x2≥0 （3）约束条件： 约束条件： 指决策变量取值时受到的各种 资源条件的限制，通常用等式 或不等式来表达。 其中， 叫做非负约束。 其中，xij≥0叫做非负约束。
二、线性规划模型的一般形式
假设线性规划问题中含有n个变量，m个约束方程。则线性规 划模型的一般形式为： 向量形式： 向量形式： max(或min)z＝c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn≤（或＝，≥）b1 m 或m z =CX ax( in) a21x1+a22x2+…+a2nxn≤（或＝，≥）b2 n ∑Pj xj ≤(或=,≥)b ………………………………………… j=1 am1x1+am2x2+…+amnxn≤（或＝，≥）bm xj ≥ 0 ≥0 x1,x2,…,xn≥0 简写为： 简写为： n m 或m z = ∑cj xj ax( in)
j =1 n
n , , ∑aij xj =bi (i =1 2,L m) j=1 xj ≥0 ( j =1 2,L n) , ,
式的解称为可行解。 (1 ) 全部可行解的集合称为可 可 行域。 行域 最优解：使目标函数（1） 最优解 (2) 达到最大值的可行解称为最优 (3) 解。
重点复习内容
第一章 线性规划及单纯形法
§1 - 1 §1 - 2 §1 - 3 §1 - 4 §1 - 5 线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论
2012-5-15
2
组成线性规划模型的三个要素
目标函数：max Z＝2x1＋x2 5x2≤15 6x1＋2x2≤24 约束条件 x1＋x2≤5 x1，x2≥0 （3）约束条件： 约束条件： 指决策变量取值时受到的各种 资源条件的限制，通常用等式 或不等式来表达。 其中， 叫做非负约束。 其中，xij≥0叫做非负约束。
二、线性规划模型的一般形式
假设线性规划问题中含有n个变量，m个约束方程。则线性规 划模型的一般形式为： 向量形式： 向量形式： max(或min)z＝c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn≤（或＝，≥）b1 m 或m z =CX ax( in) a21x1+a22x2+…+a2nxn≤（或＝，≥）b2 n ∑Pj xj ≤(或=,≥)b ………………………………………… j=1 am1x1+am2x2+…+amnxn≤（或＝，≥）bm xj ≥ 0 ≥0 x1,x2,…,xn≥0 简写为： 简写为： n m 或m z = ∑cj xj ax( in)
运筹学期末复习及答案
《运筹学》期末复习及答案(总14页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--运筹学概念部分一、填空题1．运筹学的主要研究对象是各种有组织系统的管理问题，经营活动。
2．运筹学的核心主要是运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
3．模型是一件实际事物或现实情况的代表或抽象。
4通常对问题中变量值的限制称为约束条件，它可以表示成一个等式或不等式的集合。
5．运筹学研究和解决问题的基础是最优化技术，并强调系统整体优化功能。
6．运筹学用系统的观点研究功能之间的关系。
7．运筹学研究和解决问题的优势是应用各学科交叉的方法，具有典型综合应用特性。
8．运筹学的发展趋势是进一步依赖于_计算机的应用和发展。
9．运筹学解决问题时首先要观察待决策问题所处的环境。
10．用运筹学分析与解决问题，是一个科学决策的过程。
11.运筹学的主要目的在于求得一个合理运用人力、物力和财力的最佳方案。
12．运筹学中所使用的模型是数学模型。
用运筹学解决问题的核心是建立数学模型，并对模型求解。
13用运筹学解决问题时，要分析，定义待决策的问题。
14．运筹学的系统特征之一是用系统的观点研究功能关系。
15.数学模型中，“s·t”表示约束（subject to 的缩写）。
16．建立数学模型时，需要回答的问题有性能的客观量度，可控制因素，不可控因素。
17．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。
18. 1940年8月，英国管理部门成立了一个跨学科的11人的运筹学小组，该小组简称为OR。
二、单选题19．建立数学模型时，考虑可以由决策者控制的因素是（ A ）A．销售数量 B．销售价格 C．顾客的需求 D．竞争价格20．我们可以通过（ C）来验证模型最优解。
A．观察 B．应用 C．实验 D．调查21．建立运筹学模型的过程不包括（ A ）阶段。
A．观察环境 B．数据分析 C．模型设计 D．模型实施22.建立模型的一个基本理由是去揭晓那些重要的或有关的（B ）A数量 B变量 C约束条件 D 目标函数23.模型中要求变量取值（ D ）A可正 B可负 C非正 D非负24.运筹学研究和解决问题的效果具有（A ）A 连续性 B整体性 C 阶段性 D再生性25.运筹学运用数学方法分析与解决问题，以达到系统的最优目标。
运筹学-总复习(整理全部重点题目)-
《管理运筹学》总复习第一天：1)（★★★★★）课本Page59第5题（租赁问题）：某公司在今后四个月内需租用仓库堆放物资。
已知各个月所需的仓库面积数字如下所示：设第个月签订的打算租用个月合同仓库面积为，那么这个月共有可能有如下合同：第一个月：第二个月：第三个月：第一个月：因此目标函数为：约束条件为：2)（★★★）讲义Page8例1（人力资源问题）：福安商场是个中型百货商场，他对销售员的需求经过统计分析如下表。
为了保证售货人员充分的休息，售货人员每周工作5天，休息2天，并且要求休息的两天是连续的。
问如何安排售货人员的工作作息，才能做到既满足工作需要，又使配备的工作人员最少？解：设在星期开始休息的人数为，表示星期一到星期日那么，目标函数为：约束条件为：周一：周二：周三：周四：周五：周六：周日：非负约束：3)（★）【据说出题时会和整数规划相融合】讲义Page10例5（投资问题）：某部门现有资金200万，今后五年内考虑给以下项目投资。
已知，项目A：从第一年到第五年都每年年初都可以投资，当年末能收回本利110%；项目B：从第一年到第四年都每年年初都可以投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万；项目C：需在第三年初投资，第五年末收回本利140%，但规定最大投资额不能超过80万；项目D：须知第二年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万；据测定每万元每次投资的风险指数如下表：1)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？2)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万的基础上使得其投资总的风险系数最小？解：设第年初投资在项目上的金额为，其中，。
第一年初：，，不能浪费资金，所以有，第一年年末收回：第二年初：，，，用第一年年末的收回投资，所以有：，第二年年末收回：第三年初：，，，用第二年年末收回投资，所以有：，第三年年末收回：第四年初：，，用第三年年末收回进行投资，所以有：，第四年年末收回：第五年初：用第四年年末回收进行投资，所以有：，第五年年末收回：同时，根据项目的要求，有：第（1）问答如下：目标函数为：约束条件为：第（2）问答如下：目标函数为：约束条件为：4)（★★★★）讲义Page11分析讨论题3（工厂布局问题）：设有某种原料产地A1,A2,A3，把这种原料经过加工，制成成品，再运往销地。
最全的运筹学复习题及答案教学提纲
最全的运筹学复习题及答案2、minZ=2x1-x 2+2x3五、按各题要求。
建立线性规划数学模型1、某工厂生产A、B、 C 三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：根据客户订货，三种产品的最低月需要量分别为200， 250 和 100 件，最大月销售量分别为 250， 280和 120 件。
月销售分别为250， 280 和 120件。
问如何安排生产计划，使总利润最大。
2、某建筑工地有一批长度为10 米的相同型号的钢筋，今要截成长度为 3 米的钢筋90 根，长度为 4 米的 钢筋 60 根，问怎样下料，才能使所使用的原材料最省起运时间 服务员数 2 —6 4 6 — 10 8 10 一 14 10 14 — 18 7 18 — 22 12 22 — 2 4每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少 ?五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相六、用单纯形法求解下列线性规划问题：七、用大M 法求解下列线性规划问题。
并指出问题的解属于哪一类。
maxZ=5x1+3x2，约束形式为八、下表为用单纯形法计算时某一步的表格。
已知该线性规划的目标函数为34Z=10X l X2 X3 X4—10 b -1 f gX3 2 C O 1 1／ 5X l a d e 0 1(1) a～g 的值(2) 表中给出的解是否为最优解?( 1 ) a=2 b=0 c=0 d=1 e=4/5 f=0 g= － 5 ( 2) 表中给出的解为最优解第四章线性规划的对偶理论五、写出下列线性规划问题的对偶问题1．minZ=2x1+2x 2+4x3应用对偶理论证明该问题最优解的目标函数值不大于 25七、已知线性规划问题 maxZ=2x 1+x 2+5x 3+6x 4其对偶问题的最优解为 Y l ﹡ =4， Y 2﹡=1，试应用对偶问题的性质求原问题的最优解。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
五、 决策分析
1. 决策分析的基本概念：
自然状态、 行动方案、 赢得函数、 决策准则
2.决策分析问题的分类：
确定型决策分析、 风险型决策分析、 不确定型决策分析
3. 风险型决策分析问题的决策方法：
最大可能性法、 期望值法、 决策树法
4. 不确定型决策分析方法：
乐观法、 悲观法、 乐观系数法、 后悔值法、 等可能性法
A2 x (������) − b2 = ������(A2 x 0 − b2 ) + (1 − ������)(A2 x * − b2 ) > 0.
因此x (������) 是原问题的可行解， 但
cx (������) = ������cx 0 + (1 − ������)cx * < ������cx * + (1 − ������)cx * = cx * ,
2
x2 ≥ 0
所以
(︃ B = (A3 , A1 ) = 1 −1/5 0 1 )︃ ,
(︃ ¯ ¯ B −1 = (A3 , A4 ) =
1 1/5 0 1
)︃
整数规划
3. 分枝定界法： 步骤P97
对max 类型问题: 1）选择目标函数值最大的子问题进行分枝； 2) 分枝过程在某个点上由下述两个原因之一而停止: 2-1) 找到了问题在这个子域内的整数最优解 2-2) 相应松弛LP问题是不可行的 3）定界: z ←− 当前最好的整数可行解对应的目标函数 值。 4)剪枝： 利用对ILP目标函数界的估值z “巧妙”地删去 一些不必要的点的分枝
最优指标函数fk (xk )： 在第k 年年初有xk 头牲畜、 N 年 第 末还有z 头牲畜的前提下， 畜牧场能够获得的最大收入 递推公式:
⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩
fk (xk ) = maxuk ∈[0,xk ] {������(uk ) + fk+1 [a(xk − uk )]}, k = N − 1, · {︃ maxuN ∈[0,xN −z] ������(uN ), xN ≥ z fN (xN ) = −∞, xN < z
第一阶段min g = g0 . g0 = 0时， 原问题有可行解. g0 > 0时， 原问题无可行解.
6. 对偶理论：
对偶问题、 对偶单纯形法、 对偶定理、 松弛互补条件、 影子价格
三、 整数规划
1. 割平面法: 先求松弛问题的最优解x 0 , 再对其最优解
中非整变量xBℓ 引进割平面. 设xBℓ 所对应的约束方程是
¯ br ¯rk a bi = min { ¯ik | ¯ik > 0, i ∈ [1, m]} −→ xBr 为出基变量 a a ¯
xB 0 I
xN ������N ¯ N
RHS z0 ¯ b
1 0
下降速度： k , 下降量： · ������k ������ ������
线性规划
5. 两阶段法：
(1) ⎧ ⎪ min ⎪ ⎨ ⎪ ⎪ ⎩ z = cx s.t. A1 x x ≥ b1 ≥ 0 (2) ⎧ ⎪ min ⎪ ⎨ ⎪ ⎪ ⎩ z s.t. = cx A1 x x = b1 ≥ 0
证法一: 原问题和对偶问题为
⎧ ⎧ ⎪ max ⎪ min ⎪ ⎪ z = cx ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎨ s.t. A1 x ≥ b1 (D) (P) ⎪ ⎪ A2 x ≥ b2 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎩ x ≥ 0 g = u1 b1 + u2 b2 s.t.
T u1 ≥ 0 T u2 ≥ 0
u1 A1 + u2 A2 ≤ c
* * 设u * = (u1 , u2 )是(D)的最优解， u1 , u2 ≥ 0且 则 * * * * u1 A1 + u2 A2 ≤ c. * * 因为A2 x * > b2 , 由松弛互补条件得(u2 )T = 0, 所以u2 = 0, * * * * 进而u1 A1 ≤ c. 又由对偶定理， * = u1 b1 + u2 b2 = u1 b1 . cx 易见x * 是(1)、 的可行解， 1 是(1)、 的对偶问题的 (2) u* (2) 可行解, 并且它们对应的目标函数值相等(即: * cx * = u1 b1 ), 所以x * 是(1)、 的最优解. (2)
有个畜牧场,每年出售部分牲畜， 出售y 头牲畜可获得利������(y )元。 留t 头牲畜繁殖， 一年后可得到at(a > 1)头牲畜。已知该畜牧场 年初有x 头牲畜， 每年应出售多少， 留下多少， N 年末还有z 头 使 牲畜并且获得的收入总和最大. 把该问题当作多阶段决策问题， 利用最优化原理找出递推公式。
与x * 是原问题的最优解矛盾.
例2 P75 15 有一LP问题， 目标函数 为min z = −5x1 − 3x2 ,约束条件为≤型的线性不等 式， 3 , x4 为松弛变量， x 经过一次迭代后得到下表
x1 x2 x3 z x3 x1 b c d 1 0 e f 0 x4 RHS g 1 −10 2 a
x1 z x4 ⎧ ⎪ ⎪ ⎨ −g 1 −g x3 −1/5 x2 1 − eg −e/5 e = 5 x3 x4 0 1 0 0 0 1 RHS −10 − ag 2 − a/5 a
=⇒
1 − eg ⎪ ⎪ ⎩ −10 − ag
⎧ ⎪ g = −5 ⎪ ⎨ =⇒ = 3 e = 2/5 ⎪ ⎪ ⎩ a = 2 = 0
动态规划–例
阶段： 每年为一个阶段， N 个阶段 共 第k 阶段状态变量xk : 第k 年年初牲畜数 第k 阶段决策变量uk : 第k 年出售牲畜数 容许决策集合:
Uk (xk ) = {uk |uk ∈ [0, xk ]}, k = 1, 2, . . . , N − 1 UN (xN ) = {uN |uN ∈ [0, xN − z]}.
原问题
min z s.t. = −5x1 −
1 − 5 x1
−
x1 + x1 , (︃
3x2 2 25 x2 2 5 x2
≤ ︃ )︃
已求出原问题
min z s.t. = −5x1 −
1 − 5 x1
−
x1 + x1 ,
3x2 2 25 x2 2 5 x2
≤ ≤
8 5
运筹学复习
一、 题型： 选择题、 解答题、 填空题、 简述题、 计算题、 应用题、 证明题 二、 线性规划 1. 数学模型： P10 例2.1.1 生产的组织与安排问题 2. 线性规划的标准形式: P15 例2.1.3 3. 图解法: P16 例2.2.1
4.单纯形法
(1) 基、 基本可行解 (2) 典式、 单纯形表: z z xB (3) 换基迭代： ������k > 0 −→ xk 为进基变量 ������ =
xBℓ + ∑︁
j∈R
¯ ¯ℓj xj = bℓ . a
对应于 生成行ℓ的Gomory割平面条件:
∑︁
j∈R
fℓj xj ≥ fℓ .
其中fℓj 是¯ℓj 的分数部分， ℓ 是bℓ 的分数部分. a f ¯
2. 割平面法的特点： 割去了包含松弛问题最优解x 0 在内
的一块， 但未割去IP的任何整数可行解
四、 动态规划
1. 状态变量、 决策变量、 状态转移方程、 指标函数、 逆
推公式 2. 后向最优化原理(P163): 作为整个过程的最优策略具有这样的性质: 对于最优策 略过程中的任一状态而言， 无论其过去的状态和决策如 何， 其余下的诸决策必然构成一个最优的子策略. 3. 最短线路问题： P160 图5.2.1 4. 多阶段资源连续分配问题： P181 3， 6
证法二: 设x * 不是(1)的最优解， 则存在（1）的可行 0 使cx 0 < cx * . 易知x (������) = ������x 0 + (1 − ������)x * 解x (0 < ������ < 1)也是(1)的可行解. 因为A2 x * > b2 , 所以对充 分小的������ > 0,
5. 信息的价值、 效用函数
六、 例子
例1. 考虑如下的LP问题
⎧ ⎪ min ⎪ ⎨ ⎪ ⎪ ⎩ z s.t. = cx Ax x ≥ b ≥ 0 (︀ )︀
令x * 为它的一个最优解. 假设A能分解成 A1 , B 对应地 A2 (︀ )︀ 分解成 b1 使A1 x * = b1 , A2 x * > b2 , 证明A* 也是下面两个 b2 问题的最优解.
1 1/5
试写出原问题， 并写出这张单纯表所对应的B 和B −1 . 解: B = (A3 , A1 )为基=⇒ b = c = 0, d = 1,f = 0. 经过一次迭代后的表为
x1 x2 x3 z x3 x1 0 0 1 1 0 e 0 1 0 x4 g 1/5 1 RHS −10 2 a
以¯24 为旋转元换基， a 得