线性规划的求解。
线性规划的**法。
1. 第一步,得到可行域,也就是满足所有约束条件的自变量组成的集合。
2. 第二步,在可行域中找到使目标函数最大的那一点,也就是最优解。
3. 第三步,通过最优解,求出目标函数的最优值。
化标准型:松弛变量、剩余变量、右端项为正、变量为正、变量无约束化变量有约束、min化max
线形规划解的分析。
可行域: 空集非空 ( 有界、 无界)
最优解: 无解唯一最优解无穷多最优解无界解。
线性规划的**法的敏感性分析。
目标系数的灵敏度分析。
右端值的灵敏度分析。
1. 对偶**的含义。
2. 对偶**与松弛变量、剩余变量的关系。
3. 对偶**与影子**。
4. 对偶**的经济学解释。
reduced cost
百分百定理。
线性规划建模案例。
建模步骤。1. step 1. 理解及分析实际问题、资源状况、该问题要实现的目标;
2. step 2. 确定决策变量。
3. step 3.确定目标函数及约束条件;
4. step 4.应用线性规划软件求解;
5. step 5.检验所求得的解决方案是否可行:如可行,则开始实施,否则,转step 1或step 2修改模型。
建模案例。1. 劳动力安排问题;
2. 线材的套裁问题;
3. 投资问题;
4. 混合问题。
运输问题模型;
运输问题拓展。
目标函数求最大,如:利润最大或营业额最大的调运方案;
运输能力的限制。
当生产总量不等于销量总量,即产销不平衡时,要增加一个假想的仓库或生产基地来化成产销平衡问题。
5. 供大于求:设虚拟销点配平或者让其成为松弛变量。
6. 供不应求:设虚拟产地配平(0/m),变动约束条件(产地取等号、销地取小于等于)
7. 有刚性需求时,将刚性需求单独剥离,运用m阻止虚拟产地向之运输。
运输问题的应用。
生产与库存。
**问题。目标函数。
发点。中转点。
收点。分枝定界法。
一个整数规划a,对应的线性规划问题为b,则首先求b,若b最优解不符合a的整数条件,则b的最优目标函数为a的上界x,a任意可行解的目标函数值为下界y。分枝定界法就可以将b的可行域分为子区域,逐步减少x,增大y。最终得到最优解。
0-1整数规划。
整数规划应用(end后的符号gin、int、sub、slb)
1. 投资场所的选择、指派任务(0-1变量的组合:至少选m个,至多选n个,k选n)
2. 固定成本(固定成本约束yi*m)
3. 相互排斥的约束条件(约束条件的n选1:bi+yi*m, yi和为n-1)
4. 折扣问题(划分自变量:x1<=m, x1>=my, x2<=ny)
最小生成树问题:避圈法、破圈法。
最短路问题:双标号法、0-1规划(有向图)[公式1]
最大流问题:截集法、lp法[公式2]
最小费用(最大)流问题。
先求最大流、再求最小费用(第二步将目标函数换为最小化费用,再约束条件中增加f的值)
一起求[公式3]
车间作业计划模型(排序问题)
对于一台机器n个零件的排序问题,按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。
两台机器,n个零件:
1.从未安排的零件中,选取最短的加工时间的零件。若该时间是在车床上(第一台机器上),该零件排在最前面,若是在磨床上(第二台机器上) ,该零件排在最后面。
2.将该零件排除。
3.若所有零件已安排,结束;否则,回到阶段 1。
4.计算总加工时间:车床-磨床-车床-磨床(若车床加工时间短于磨床,则省略该步骤,反之则加上时间差)
关键路线法。
画网络图的要点:
1. 两点之间只有一条弧;
2. 不能有缺口:除发点和收点外,其他各个点的前后都应有弧连接。即从发点经过任何路线都可以到达收点,必要时可以添加虚工序。
3. 不能产生回路,否则将使组成的工序永远不能结束。
关键路线法:
4. 从起点开始,计算各工序最早开工时间、最早完工时间。
5. 从终点开始向前,计算最晚开工时间、最晚完工时间。
6. 关键路线上的工序:最早开工时间等于最晚开工时间,或者最早完工时间等于最晚完工时间。工序时差等于零。
7. 工序时差ts=ls-es=lf-ef
用lindo求解关键路线法:
8. 弧求法:0-1变量、**问题与最大化。
9. 点求法:相邻点相减大于等于所需时间、虚工序大于等于0,求最后时点的最小化问题。结果中对偶**不为0的是关键路线。
工序时间不确定的关键路线法:
10. 期望时间与方差的公式。
11. 总工期为关键路线期望时间之和,方差为关键路线方差之和。
12. 使用2的数据计算完工概率。
网络优化。13. 时间资源优化。
从非关键路线节省资源,优先安排关键路线。
采取技术措施,缩短关键工序完工时间。
利用非关键路线总时差,错开各工序开始时间,拉平资源需要量的高峰。
14. 时间费用优化。
点求法的改版:变量为每个工序的缩短时间,目标函数为最小化缩小费用(注意使用单位费用);约束条件右端是原工时减去缩短时间。
不确定型决策。
1)悲观主义准则(最大最小准则):
2)乐观主义准则(最大最大准则)
3)等可能性准则;各种概率1/事件数(1/n),计算各方案的期望收益,选择期望收益值最大的。
4)后悔值准则(最小机会损失准则):(最大后悔值中选择小的)中批量生产。
风险型决策。
最大可能准则(概率差距比较大)
期望值准则(概率差距不大,不能判断何者更可能发生)
期望效用准则(不考)
决策树法。决策点:以□表示;从它引出的分支叫方案分支,分支数反映可能的行动方案数;
方案点:以○表示;其上方的数字表示该方案的收益的期望值。
概率枝:每条分支的上面标明自然状态及出现的概率;其数目表明方案可能的自然状态。
树梢: 或“节点”,每一个方案在相应状态下的收益值。
运用决策树方法进行决策,其主要计算步骤是:
1) 画出决策树;
2) 从树梢开始往前逐级计算各方案枝的期望值,将各数值写在方案点旁边;
3) 对各期望值进行比较,选出最大的期望值写在决策点的上方,该方案作为最优方案;
4) 在其它期望值较小的方案枝上打上删除号“ ”删除掉或称为剪枝。
运筹学大纲
运筹学大学纲。课程名称 中文 英文名称 运筹学 operationsresearch课程 0921016005学分 总学时 3 54 开课单位 数学与信息科学学院。面向专业 数学与应用数学专业 信息与计算科学专业和统计学专业。一 课程的性质 目的和任务。本课程是数学与应用数学专业和统计学专业的一门专...
运筹学大纲
mba教材。运筹学。大纲。北京邮电大学经济管理学院。2001年6月。运筹学 教学大纲。一 课程目的与要求。本课程目的在于培养mba学员通过模型定性定量解决问题的能力,特别是掌握优化的思想和基本手段,提高解决工作中实际问题的能力。课程通过案例使学员能够理解所学的理论和方法。本课程讲授学时应在40 48...
运筹学大纲
课程编号 832课程名称 运筹学基础。一 考试的总体要求。要求考生应能对运筹学的基本内容有比较系统全面的了解,基本概念清楚,基本理论的掌握比较牢固并能融会贯通,基本方法和运算熟练。二 考试的内容及比例 150分 1 线性规划。模型 法 单纯形法原理 单纯形表计算 对偶理论 灵敏度分析 运输问题 线性...