运筹学总结课件

一、线性规划线性规划的标准形式： maxz=Σcjxj(1)s.t.Σaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)后续单纯形法求解中的判别针对以上标准形式

一、线性规划线性规划的标准形式：1一、线性规划单纯形法要求约束方程右端项bi非负（存在基可行解）构造初始可行基（有时需要加入人工变量）判断检验数所有非基变量检验数都小于零，有唯一解；某个非基变量检验数等于零，其余非基变量检验数小于零，无穷多最优解；某个非基变量检验数大于零，且其在约束方程中的系数小于等于零，无界解；所有非基变量检验数都小于零，同时基变量中包含人工变量，无可行解。改进的单纯形法（基于矩阵的单纯形法）一、线性规划单纯形法2一、线性规划对偶问题原问题与对偶问题的数学模型对偶问题的基本性质和基本定理对偶单纯形法一、线性规划对偶问题3一、线性规划原问题与对偶问题的数学模型原问题标准形式：对偶问题标准形式：一、线性规划原问题与对偶问题的数学模型原问题标准形式：对偶问4一、线性规划对偶问题的基本性质若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。原问题的检验数对应对偶问题的一个基本解。一、线性规划对偶问题的基本性质5一、线性规划对偶问题的基本定理对称性定理对偶问题的对偶是原问题弱对偶性定理若X(0)和Y(0)分别是原问题和对偶问题的可行解，则有CX(0)≤Y(0)b最优性定理若X(0)和Y(0)分别是原问题和对偶问题的可行解，且有CX(0)=Y(0)b,则X(0)和Y(0)分别是原问题和对偶问题的最优解。一、线性规划对偶问题的基本定理6一、线性规划对偶问题的基本定理对偶定理一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且目标函数值相等。互补松弛定理若X(0)和Y(0)分别是原问题和对偶问题的可行解，则X(0)和Y(0)都是最优解的充要条件是Y(0)Xs=0和YsX(0)=0。

其中Xs=(xs1,xs2,…,xsm)T，xs1,xs2,…,xsm是原问题的松弛变量，Ys=(ys1,ys2,…,ysn)T，ys1,ys2,…,ysn是对偶问题的剩余变量。

一、线性规划对偶问题的基本定理7一、线性规划对偶单纯形法初始单纯型表中所有检验数小于等于零，且约束方程右端项bi小于零的条件下，可应用对偶单纯形法；通常用于灵敏度分析。一、线性规划对偶单纯形法8练习(表上作业法,10月14日上课时交)：甲乙两煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市用煤量见表，各煤矿到各城市之间的运输价格也见表。问：甲、乙两地分别向A、B、C三地运输多少煤矿，使得煤矿运输的总体运费最低。(1)应用伏格尔法求出初始方案;(2)应用闭回路法和闭回路调整法进行最优解判别，给出最优方案。单位运价表

练习(表上作业法,10月14日上课时交)：9二、整数规划纯整数规划分枝定界法割平面法0-1整数规划二、整数规划纯整数规划10练习2:用割平面法求解下列整数规划问题练习2:用割平面法求解下列整数规划问题11用隐枚举法求解0-1规划问题用隐枚举法求解0-1规划问题12运筹学总结课件13三、动态规划动态规划基本方程动态规划逆序解法动态规划顺序解法三、动态规划动态规划基本方程14三、动态规划动态规划建模方法划分阶段，通常按照时间或空间特征划分阶段。确定决策变量，可以取问题中的变量为决策变量。确定状态变量：一般为累计量或随递推过程变化的量。列出状态转移方程定义指标函数列出边界条件动态规划基本方程三、动态规划动态规划建模方法15累加形式指标函数的动态规划基本方程边界条件：乘积形式指标函数的动态规划基本方程边界条件：累加形式指标函数的动态规划基本方程边界条件：乘积形式指标函数16运筹学总结课件17四、排队论不同类型排队系统数量指标的推导基于状态转移图列出状态转移方程求解状态转移方程得到状态概率基于状态概率推导排队系统的队长、队列长、等待时间、逗留时间不同类型排队系统数量指标的计算四、排队论不同类型排队系统数量指标的推导18五、对策论二人有限零和对策的求解五、对策论二人有限零和对策的求解19六、决策论不确定型决策根据收益矩阵按照不同准则选择方案风险型决策决策树法贝叶斯法六、决策论不确定型决策20六、决策论方案分枝概率分枝决策点方案点结果点方案点结果点结果点结果点决策树六、决策论方案分枝概率分枝决策点方案点结果方案点结果结果结果21按原工艺方案生产价低0.1-100-200-300-200-300中0.5050500-250价高0.4100150250200600买专利(0