运筹学总结课件.ppt
一、线性规划一、线性规划 线性规划的标准形式：线性规划的标准形式：max z=cjxj (1) s.t.aijxj=bi i=1,2,m (2) xj0 j=1,2,n (3) 后续单纯形法求解中的判别针对以上标准后续单纯形法求解中的判别针对以上标准形式形式 一、线性规划一、线性规划 单纯形法单纯形法 要求约束方程右端项要求约束方程右端项bi非负（存在基可行解）非负（存在基可行解） 构造初始可行基（有时需要加入人工变量）构造初始可行基（有时需要加入人工变量） 判断检验数判断检验数 所有非基变量检验数都小于零，有唯一解；所有非基变量检验数都小于零，有唯一解； 某个非基变量检验数等于零，其余非基变量检验数小于零，某个非基变量检验数等于零，其余非基变量检验数小于零，无穷多最优解；无穷多最优解； 某个非基变量检验数大于零，且其在约束方程中的系数小某个非基变量检验数大于零，且其在约束方程中的系数小于等于零，无界解；于等于零，无界解； 所有非基变量检验数都小于零，同时基变量中包含人工变所有非基变量检验数都小于零，同时基变量中包含人工变量，无可行解。量，无可行解。 改进的单纯形法（基于矩阵的单纯形法）改进的单纯形法（基于矩阵的单纯形法）一、线性规划一、线性规划 对偶问题对偶问题原问题与对偶问题的数学模型原问题与对偶问题的数学模型 对偶问题的基本性质和基本定理对偶问题的基本性质和基本定理 对偶单纯形法对偶单纯形法一、线性规划一、线性规划 原问题与对偶问题的数学模型原问题与对偶问题的数学模型原问题标准形式：原问题标准形式：对偶问题标准形式对偶问题标准形式：nmijTnaAxxxXXbAXtsCXz)(,),(0. .max21),(0.min21nyyyYYCYAtsYb一、线性规划一、线性规划 对偶问题的基本性质对偶问题的基本性质 若原问题（对偶问题）为无界解，则其对偶问题若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（原问题）无可行解。 原问题的检验数对应对偶问题的一个基本解。原问题的检验数对应对偶问题的一个基本解。一、线性规划一、线性规划 对偶问题的基本定理对偶问题的基本定理 对称性定理对称性定理 对偶问题的对偶是原问题对偶问题的对偶是原问题 弱对偶性定理弱对偶性定理 若若X(0)和和Y(0)分别是原问题和对偶问题的可行解，则有分别是原问题和对偶问题的可行解，则有CX(0)Y(0)b 最优性定理最优性定理 若若 X(0)和和Y(0)分别是原问题和对偶问题的可行解，且有分别是原问题和对偶问题的可行解，且有CX(0) =Y(0)b , 则则X(0) 和和Y(0)分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。一、线性规划一、线性规划 对偶问题的基本定理对偶问题的基本定理 对偶定理对偶定理 一对对偶的线性规划问题，若其中有一个有最优解，则另一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且目标函数值相等。一个也有最优解，且目标函数值相等。 互补松弛定理互补松弛定理 若若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是对偶问题的剩是对偶问题的剩余变量。余变量。 一、线性规划一、线性规划 对偶单纯形法对偶单纯形法 初始单纯型表中所有检验数小于等于零，且约初始单纯型表中所有检验数小于等于零，且约束方程右端项束方程右端项bi小于零的条件下，可应用对偶小于零的条件下，可应用对偶单纯形法；单纯形法； 通常用于灵敏度分析。通常用于灵敏度分析。练习练习(表上作业法, 10月14日上课时交)：甲乙两煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市用煤量见表，各煤矿到各城市之间的运输价格也见表。 问：甲、乙两地分别向A、B、C三地运输多少煤矿， 使得煤矿运输的总体运费最低。 (1)应用伏格尔法求出初始方案; (2)应用闭回路法和闭回路调整法进行最优解判别， 给出最优方案。 单位运价表 二、整数规划二、整数规划 纯整数规划纯整数规划 分枝定界法分枝定界法 割平面法割平面法 0-1整数规划整数规划练习2: 用割平面法求解下列整数规划问题取整数,0,32/12054.34max2121212121xxxxxxxxtsxxZ用隐枚举法求解0-1规划问题12312312323123min z = 4x +3x +2x2x -5x +3x44x +x +3x3 x +x1x ,x ,x0 1或 三、动态规划三、动态规划 动态规划基本方程动态规划基本方程 动态规划逆序解法动态规划逆序解法 动态规划顺序解法动态规划顺序解法三、动态规划三、动态规划 动态规划建模方法动态规划建模方法 划分阶段，通常按照时间或空间特征划分阶段。划分阶段，通常按照时间或空间特征划分阶段。 确定决策变量，可以取问题中的变量为决策变量。确定决策变量，可以取问题中的变量为决策变量。 确定状态变量：一般为累计量或随递推过程变化的量。确定状态变量：一般为累计量或随递推过程变化的量。 列出状态转移方程列出状态转移方程 定义指标函数定义指标函数 列出边界条件列出边界条件 动态规划基本方程动态规划基本方程 kk1kkkkkoptsDukksufsusvsfkkk,累加形式指标函数的动态规划基本方程累加形式指标函数的动态规划基本方程0sf1n1n边界条件：边界条件： kk1kkkkkoptsDukksufsusvsfkkk,乘积形式指标函数的动态规划基本方程乘积形式指标函数的动态规划基本方程边界条件：边界条件：1sf1n1n四、排队论四、排队论 不同类型排队系统数量指标的推导不同类型排队系统数量指标的推导 基于状态转移图列出状态转移方程基于状态转移图列出状态转移方程 求解状态转移方程得到状态概率求解状态转移方程得到状态概率 基于状态概率推导排队系统的队长、队列长、基于状态概率推导排队系统的队长、队列长、等待时间、逗留时间等待时间、逗留时间 不同类型排队系统数量指标的计算不同类型排队系统数量指标的计算五、对策论五、对策论 二人有限零和对策的求解二人有限零和对策的求解六、决策论六、决策论 不确定型决策不确定型决策 根据收益矩阵按照不同准则选择方案根据收益矩阵按照不同准则选择方案 风险型决策风险型决策 决策树法决策树法 贝叶斯法贝叶斯法六、决策论六、决策论方案分枝方案分枝概率分枝概率分枝决策点方案点结果点方案点结果点结果点结果点决策树决策树按原工按原工艺方案艺方案生产生产价低价低 0.1 -100 -200 -300 -200 -300 中中 0.5 0 50 50 0 -250价高价高 0.4 100 150 250 200 600买专利买专利(0.8)自研自研(0.6)产量产量不变不变增产增产产量产量不变不变增产增产(万元万元)84219561073 买 专 利 自 研 制 成 功 0 .8 失 败 0.2 失 败 0.4 成 功 0 .6 原 产 增 产0.50.40.10.50.4 原 产 量 增 产 价 低 0 .1 中 0 . 5 高 0 . 4 价 低 0 .1 中 0 . 5 高 0 . 40.10.50.40.10.50.4-20050150-30050250-1000100-1000100-2000200-300-250600110.1精品课件精品课件！精品课件精品课件！解：解：8421956107382 买 专 利 自 研 制8263 成 功 0 .8 失 败 0.2 失 败 0.4 成 功 0 .695303085 原 产 增 产0.50.40.10.50.4 原 产 量 增 产65956085 价 低 0 .1 中 0 . 5 高 0 . 4 价 低 0 .1 中 0 . 5 高 0 . 40.10.50.40.10.50.4-20050150-30050250-1000100-1000100-2000200-300-250600110.1
