管理运筹学复习 - 图文

管理运筹学

对偶问题

基本可行解：满足非负条件的基本解。

【最优解不一定是基本可行解,因为问题有可能有无穷多最优解,最优解是两个基可行解】

可行解：对应于基本可行解的基。

最优基：是原问题的最优解对应初始单纯行表中列向量所组成的m阶方阵（B）。

对偶问题的基本性质

对称性：原问题与对偶问题是两个互为对偶的问题。 弱对偶性：两个问题的可行解对应的目标函数值互为上下界。 最优性：两个问题最优解的目标函数值一定相等。

强对偶性：两个问题都有可行解时则两个问题一定都有最优解。

互补松弛性：两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的某个约束条件必为紧约束。 若原问题的最优基为B，则其对偶问题的最优解为：

Y*?CB?B?1

对偶定理：

原问题P与对偶问题D

1.P有最优解，则D有最优解；

2.若X*与Y*分别为P和D的可行解，则它们分别也为P和D的最优解 且有CX*=Y*b。

影子价格：在其他条件不变的情况下，单位资源b变化所引起的目标函数

?f*?CBB?1?Y*的最优值的变化.f*?CBBb?Y*b，对b求导： ?b

?1

灵敏度分析

1、价值系数的灵敏度分析

假定目标函数只有一个Cj发生变化，模型中其他系数保持不变；确定Cj在什么范围内变化，原问题的最优解不变，称这个范围为Cj的可变范围. 依据：保证最优解不变?保证检验数≤0

2、资源系数的灵敏度分析

整数规划

分支定界法：是对有界的规划问题的可行域，以恰当的方式进行系数

的搜索的算法。

（求max是下界；求min是上界。）

指派问题：假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使完成n项任务的总效率最高。

匈牙利算法：求min，则各行/列减去本行/列最小值，且保证每行/列至少有一 个0元素；

求max，则各行/列减去本行/列最大值，且保证每行/列至少有一 个0元素。

运输问题模型的特点：[有可行解的条件]

a、有m个产地n个销地且产销平衡运输问题的基变量个数为m+n-1个 b、产销平衡的运输问题存在可行解。 c、平衡运输问题一定有最优解。

表上作业法：必须满足表中非空格的个数=m+n-1

最小运价法： 基本思想是就近供应，即从单位运价表中最小的运价开始确定 供销关系，然后次小。一直到给出初始基可行解为止。 【优点：简单】

差额法：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就 有一个差额。差额越大，说明不能按最小运费调运时，运费增加越 多。因而对差额最大处，就应当采用最小运费调运。 【优点：更接近最优解；缺点：过程较复杂。】

决策分析

确定型决策问题：在决策环境完全确定的条件下进行。

不确定型决策问题：在决策环境不确定的条件下进行，对各自然状态发生的概率一无所知。

风险型决策问题：在决策环境不确定的条件下进行，各自然状态发生的概率可以预测。

乐观准则（大中取大）：反映决策者对问题持乐观态度，认为每种情况都会出现最好的。

悲观准则（小中取大）：反映决策者对问题持保守悲观的态度，先做出最坏的打算，然后在此基础上择优。

风险型决策方法——决策树方法：

目标规划

＋

正偏差变量d 表示决策值超过目标值的部分；

负偏差变量d - 表示决策值未达到目标值的部分； 因决策值不可能既超过目标值同时又未达到目标 值，即恒有d+×d-=0。

绝对约束 : 是指必须严格满足的等式约束和不等式约束.

目标约束 : 是目标规划特有的，可把约束右端项看作要追求的目标值。

? 目标规划的目标函数 基本形式有三种：

? (1) 要求恰好达到目标值，即正、负偏差变量都要尽可能地小，

这时 min z=f(d++d-)

? (2) 要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小。这时min z=f(d+)

? (3) 要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时min z=f(d-)

本文来源：https://www.bwwdw.com/article/39it.html