运筹学整理笔记-revised

《运筹学基础 第二版 何坚勇》考试3-12章 共计10章

章节号 以下标红的为有配套例题

3构造基本可行解松弛变量：≦时加在左边的xn 人工变量：≥时加在左边的xn

目的：将不等式约束化为等式标准型 P68

判断是否最优最大化问题所有检验数σ小于0即达最优解

检验数计算公式：σj=cj-∑cia'ij

进行变换迭代找到|σj|最大的作为进基变量

b/a最小的为离基变量，只考虑a>0

单纯形表见右表

最优解中，人工变量都应取0值

大M法在目标函数中减去M*人工变量，M为大正数二阶段法先将目标函数改为求所有人工变量最小化

得到结果后再进入第二阶段求解原函数目标值

4对偶问题

只需记住max的约束与min的变量相反，其他均一样即可1同时取得最优解；2一个无界则另一个无解互补松弛定理x>0，则对偶问题约束取=号约束取>号，则对偶x=0影子价格的经济解释

对偶解称为影子价格，大小反应了该资源的稀缺程度先确定离基变量min bi，再进基变量min{σj/aij|aij<0}直到所有的检验数σ小于0即达最优解灵敏度分析

见右表5最小元素法确定初始可行解：在所有运价中找出最小运价

优先满足最小运价的调运，然后寻找下一个最小运价

位势法求检验数，要求非基变量的检验数全大于0

由基变量的检验数=0 即 cij-(ui+vj)=0 可得 ui vj

非基变量检验数的计算公式σij=cij-(ui+vj)

闭回路法调整可行解：找出最小的检验数，作其余顶点为

基变量的闭合回路，选出最小运量进行调整

进基格为1号格，依次编号，奇数加运量，偶数减

无穷多解非基变量的检验数为0

退化问题基变量取值为0，此时要在划去的行（列）中添0

产销不平衡的运输问题

假想销地：需求量为0；假想产地：运费为06套裁下料问题、配料问题、生产工艺优化问题、有配套约束的资源优化问题

多周期动态生产计划问题、投资问题 均为线性规划问题，转化后使用单纯形表求解 P175

7

计算步骤计算原问题的上界、下界，增加约束使原问题分枝求解并修改上下界

最优解性条件当所有分枝均查明、且上界=下界时，得到

通过添加约束来获取整数解

割平面的找法任选不满足整数要求的约束方程，分离其系数的整数和分数

取分数部分移至左端，右端归零并构造不等式约束 P205

特点xi的取值非0即1，可用来添加和控制约束（如矛盾的约束）

解法可用隐枚举法求解小规模0-1问题（逐个约束试）

匈牙利解法各行各列减去其最小元素，使得每行每列出现0元素

圈出独立0元素，进行试指派，用横线串起行0元素、竖线串起剩余0元素

取未被划去的数值中最小的元素，未被划去的元素共同减去它

横纵交叉点上的元素加上它-再次进行试指派

8基本概念与数学模型

绝对约束必须满足，目标约束尽量满足；区分各个目标之间的优先级

目标函数min Z = p1d1- + p2d2+ + p3(d3+ + d3-) pi为优先级2013-12-15对偶

理论应用运输问题整数规划单纯形法对偶单纯形法

表上作业法分枝定界法割平面法0-1型整数规划指派问题和匈牙利解法原理均为非负人工变量及处理方法对偶理论

标

规

划

在约束中，大于取d1-，小于取d2+，等于取解题步骤作图画出硬约束和目标约束，按照优先级逐步考虑目标函数依据偏差缩小搜索范围序贯式算法按照约束的优先级逐个求解，在此不赘述解题步骤将di-作为初始可行基，列表进行单纯形表计算 区别主要在于检验数，有多少个优先级即有多少行检验数，σj>0

若上一个优先级检验数为正，而下一个为负，则忽略不计

9必要条件一阶：局部最优解→▽f(x*)=0

二阶：局部最优解→▽f(x*)=0 且 ▽2f(x*)半正定 严格局部最优解→▽f(x*)=0 且 ▽2

充分条件二阶：▽f(x*)=0 且 ▽2f(x*)半正定→局部最优解定义f(αx1+(1-α)x2)≦αf(x1)+(1-α)f(x2)

直观任意拉一根线都在函数上面，见右图判别方法一阶f(x2)≥f(x1)+▽f(x1)*（x2-x1）

二阶▽2f(x)处处半正定

解非线性规划的基本思路选取初始点、构造搜索方向、确定步长、求出下一个迭代点

10黄金分割法初始点(a0,b0)迭代点：x1=a0+0.618(b0-a0) x1'=a0+0.382(b0-a0)

取远离期望的值做下一步迭代的初始点

加步探索法xn=x n-1+n*h0每一步方向正确后，步长加大

牛顿法迭代公式x (n+2)=x (n+1)-f'(x (n+1))/f''(x (n+1))

11变量轮换法思路将多变量函数优化转为单变量函数来解

定义多个方向，求导令为0，得λ值，带入得到下一个初始值，x2=x1+λ1e1

最速下降法思路认为p=-▽f(x)方向下降最快，故x n+1=x n -λn ▽f(x n )

思路p=-[▽2f(x k )]-1*▽f(x k )

修正牛顿法改进了步长恒取1的不足，此时λ值通过求导得到

思路化成标准型、p=-▽f(x)、标准型12库恩塔克条件约束全部改成大于等于0，对目标函数和约束分别求导得到▽f(x)，▽g1(x)、▽g2(x)等，令右方程成立并解出若是等式，则化为g(x)≥0，-g(x)≥0两个不等式可行方向法思路找到gi(x k )=0的点，构建线性规划问题，求解得出搜索方向近似规划法求解特定线性规划问题 见书P335外点法惩罚因子↑，从外部趋于最优解内点法惩罚因子↓，从内部趋于最优解，要求严格内点增广目标函数可用倒数或对数函数(选取原则是求导好处理）求导后，解之，得到含有r障碍因子的值，使r→0，得最优解

后记：很多公式无法在excel中打出，且不能输入上标，我均用小9号字体标出，具体还请见书为宜

图解法

牛顿法单纯形算法无约束问题的最优性条件凸函数与凸规划最优性条件制约函数法约

束

问

题

的

最

优

化

方目标

规划

非线性基本概念一维搜索无约束问题的最共轭梯度法(x )()k T k k k T k f p p Ap λ?=-1min ()2T T f x x Ax b x C =++

章 共计10章

附记

1考试范围共计10章，考7-8道计算大题，由此推断

减去剩余变量每章不会超过一题，每章不可能考细，只需掌握每章最主要的方法即可

标准型 P68尽量避免看书，多看题，将每章主要的题做会即可，教材写的太琐碎，浪费时间！

0即达最优解

2无穷解的判定：非基变量的检验数为0

无界解的判定：非基变量检验数大于0，但所有a均≦0

即：可找到进基变量，找不到离基变量

，M为大正数3单纯形表

变量最小化

解原函数目标值

aij|aij<0}4灵敏度分析涉及多个方面，因老师未布置相关作业，初步认为不考

但请各位知悉灵敏度分析的基本方法，归纳如下：

1cj的变化，若影响检验数则重算

2bi的变化，若B-1b>0则不变；若小于则用对偶单纯形法重新求解

中找出最小运价3增加一个变量xj，若影响检验数则重算

后寻找下一个最小运价4aij的变化，若是非基变量则继续算，基变量则重算

验数全大于0 5增加约束条件：看最优变量是否满足约束，不满足则继续算

(ui+vj)=0 可得 ui vj原问题对偶问题结论

ij=cij-(ui+vj)综上是可行解是可行解最优解或最优基不变

数，作其余顶点为归纳为右表是可行解非可行解单纯形法继续迭代

运量进行调整非可行解是可行解对偶单纯形法继续迭代

奇数加运量，偶数减非可行解非可行解引入人工变量，重新计算

去的行（列）中添0

5线性规划应用十分广泛，较难找出代表性例题并归纳出相应方法，故不给出习题

请各位细读书上给出的六个例题，揣摩从实际问题演化为抽象的数学问题的方法

单纯形表求解 P175

6割平面法和0-1整数规划法因未布置作业，初步认为不考，因此不给出习题

加约束使原问题分枝但请各位阅读原书例题，并知晓其思路及解题方法

下界时，得到

程，分离其系数的整数和分数7目标规划的单纯形表解法

造不等式约束 P205列表方式如下，注意P3行的第七列元素为-5，但上一行为正，故忽略不计，选-3为进基和控制约束（如矛盾的约束）

问题（逐个约束试）

得每行每列出现0元素

起行0元素、竖线串起剩余0元素

去的元素共同减去它

各个目标之间的优先级

(d3+ + d3-) pi为优先级

引语

取d2+，等于取d3+ + d3-按照优先级逐步考虑目标函数进行单纯形表计算有多少行检验数，σj>08凸函数

负，则忽略不计2f(x*)半正定

且 ▽2f(x*)正定

)半正定→局部最优解

(1-α)f(x2)

9补充正定矩阵的判别方法1特征值全为正x1)*（x2-x1）2各阶顺序主子式都为正

3合同于单位阵

下一个迭代点10非线性基本概念及凸函数的判别方法应当不会单独考，因此不给出习题

x1'=a0+0.382(b0-a0)请参照后面三章非线性优化问题对该章内容进行深入理解

11一维搜索中，前两种方法旨在收缩区间，后一种方法旨在函数逼近

一维搜索是求步长因子的方法，无约束问题解决搜索方向的问题12这几种方法其实就是搜索方向p不同的区别

到下一个初始值，x2=x1+λ1e1搜索方向p

n+1=x n -λn ▽f(x n )变量轮换法e k

最速下降法-▽f(x)

时λ值通过求导得到牛顿法-[▽2f(x k )]-1*▽f(x k )

共轭梯度法-▽f(x)

13库恩塔克条件需满足的方程

目标函数和约束分别求导x)等，令右方程成立并解出g(x)≥0两个不等式规划问题，求解得出搜索方向求严格内点

i=(1,2,..m)函数(选取原则是求导好处理）

碍因子的值，使r→0，得最优解

体标出，具体还请见书为宜

***1***(x )(x )0(x )00m i i

i i i i f g g γγγ=??-?=???=??≥???∑(x )()k T k k k T k f p p Ap λ?=-

太琐碎，浪费时间！

故不给出习题

的数学问题的方法

故忽略不计，选-3为进基变量