整数规划(运筹学).ppt

文档介绍：前两章内容回顾和总结
1,线性规划模型
2,线性规划的建模实例分析
3,线性规划的求解-图解法和Lindo
4,对偶问题
5,敏感性分析
2018/4/15
1
总结1:
目标函数用决策变量的线性函数来表示。按问题的不同,要求目标函数实现最大化和最小化。
线性规划问题(LP问题)的共同特征:
每一个问题变量都用一组决策变量(x1, x2, …, xn)表示某一方案,这组决策变量的值代表一个具体方案,这些变量是非负的。
存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示。
若LP问题有最优解,则要么最优解唯一,要么有无
穷多最优解。
2018/4/15
2
总结2:
LP问题
有可行解
有最优解
唯一解
无穷多解
无最优解(可行域为无界)
无可行解(无解)
规律1:
2018/4/15
3
规律2:
线性规划问题的可行域为一凸集
线性规划问题凸集的顶点个数是有限的
最优解肯定可在凸集的某顶点处达到
2018/4/15
4
总结3: 线性规划问题的标准型
1. 标准型
2018/4/15
5
2. 所有LP问题均可化为标准型
2018/4/15
6
3,标准型LP问题的解
2018/4/15
7
线性规划对偶的一般形式
2018/4/15
8
敏感性分析
很多软件可以生成目标函数系数或者约束右端参数的灵敏度报告,可以很快计算出最优域;
运用目标函数系数的百分百法则,可进一步方便地检验所有参数同时变动的情况;
通过影子价格分析,发现改变决策会产生的影响,从而为管理层更好的决策提供指导;
用约束右端值变动的百分百法则来判断变动的幅度。
2018/4/15
9
第四章整数规划
整数规划问题的提出
整数规划的求解-分支定界法
0-1规划建模
2018/4/15
10