运筹学期末复习

可作为复习资料打印

线性规划问题的单纯形法

线性规划的标准模型,下面给出一个例子

\[\max z = c_1x_1+c_2x_2+c_3x_3+c_4x_4\]

\[ \left\{\begin{array}{lr} a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1 &\\ a_{21}x_1+a_{22}x_2+a_{23}x_3+a_{24}x_4=b_2 &\\ a_{31}x_1+a_{32}x_2+a_{33}x_3+a_{34}x_4=b_3 &\\ a_{41}x_1+a_{42}x_2+a_{33}x_3+a_{44}x_4=b_4 &\\ x_1,x_2,x_3,x_4\ge 0 \end{array} \right. \]

  • \(\vec b\) 需要满足 \(\vec b \ge 0\)

单纯形法

对于一个线性规划问题如

r5ZdQf.png

可以作出以下的单纯形表

r5Z5mF.png 注:4800 改为 48000

单纯形表求解步骤

  1. 对原问题进行标准化
  2. 找到一个初始可行基\(\bar B\)(即对应的系数矩阵为一个单位矩阵)
  3. 求出此时每列变量\(x_i\)对应的 \(z_j = \sum c_Ba_{ij}\)\(\sigma_j=c_j-z_j\)
  4. \(\exist \sigma_j > 0\)时,说明不是最优解,继续进入第四步,反之结束迭代,进入步骤8.
  5. 选出\(\max\sigma_j\),选定该列对应的变量为换入变量
  6. 对于每一行,求得 \(\theta=b_j/\max{a_{ij}}\),其中要求\(a_{ij}>0\) 且 对应的列不能是基中的。选出\(\min\theta\)对应的一行的变量为换出变量
  7. 用高斯消元法,将对应的换入变量(方括号括中的)化为 1,对应列其余系数化为 0,得到新的表。
  8. 返回 步骤2.
  9. 最终解为表左边的基变量,对应的基变量的值为右方的\(b\)

有最优解 非基变量\(\sigma_j\le 0\),基变量 \(\sigma_j=0\)

唯一最优解 有最优解的情况下,所有非基变量的 \(\sigma_j<0\)

无穷多最优解 有最优解的情况下,存在非基变量的 \(\sigma_j=0\)

无最优解 所有的系数 \(a_{i,m+k}\le 0\),且仍有一个非基变量的 \(\sigma_j>0\)


线性规划的对偶 P65

若原问题为

\[\max\vec{c}^T\vec x\]

\[ \left\{\begin{array}{lr} \vec A \vec x\le \vec b &\\ \vec x \ge 0 \end{array}\right. \]

则其对应的对偶问题为

\[\min\vec{b}^T\vec y\]

\[ \left\{\begin{array}{lr} \vec A^T \vec y\ge \vec c &\\ \vec y \ge 0 \end{array}\right. \]

可以得出:原问题的每个不等式对应对偶问题中的一个变量,其具体关系如下表

r5nmJs.png

对偶定理 P68

对于一个问题及其对偶问题,有:

弱对偶定理 原问题的任意可行解的目标函数值是对偶问题的目标函数值的下界;反之,对偶问题的目标函数值为原问题的目标函数的上界

  • 即 max 为 min 的下界,min 为 max 的上界

最优解存在性定理 若原问题和对偶问题均存在可行解,则它们必定存在最优解

无界解定理 若两个问题的都有可行解,且其中一个目标函数无界,则其另一个无可行解

强对偶定理 若其中一个有最优解,则另一个也有,且目标函数的值相等

互补松弛定理(P71) 将问题化为标准形式,将最优解\(\vec x^*\)带入标准型中,求得松弛变量取值,再利用两个等式

\[\vec y^*\vec x_S = 0\]

\[\vec y_S\vec x^* = 0\]

将求出的值代入对偶问题的标准型,再求出剩下的变量的值。

对偶单纯形法(P75) 对于标准形式的线性规划问题(\(b\)可小于等于 0),若\(b\)中不存在负数,则跳出;反之选择其中绝对值最大的,对应行为出基变量,计算\(\sigma_j/a_{ij}, a_{ij}<0\wedge \sigma_j<0\)(如果所有\(a_{ij}>0\),则对偶问题没有可行解)比值最小的列对应变量为入基变量。

灵敏度分析 P79

资源系数 \(\vec b\) 变化 P80

\(\vec x = B^{-1}(b+\Delta b)\ge 0\)时,原最优解不变,其中\(B^{-1}\) 为原基变量的系数矩阵

已知资源系数的改变量\(\Delta b\) 直接用上式求出新的\(b\),用对偶单纯形法继续迭代。

价值系数 \(\vec c\) 发生变化 P81

非基变量 若要原解不变,只需要对应系数\(c_j\)使得\(\sigma_j\le0\)即可保持原最优解不变。

基变量 需要保证所有非基变量的检验数\(\sigma_j\le 0\)

如果题中有指出已经发生了变化,将变化的系数带入单纯形表中继续迭代即可。

技术系数 \(A\) 发生变化 P83

非基变量 对于该技术系数对应的列,左乘上一个\(C_B\)和原基变量的最终形表矩阵\(B^{-1}\),即\(c_BB^{-1}\),保证对应的\(\sigma_j\le 0\)即可保持原最优解不变。

基变量 见下表以及 P84 的详细讲解。

r5aO3V.png


运输问题 P92

表上作业法(P96)

表的每个格中,单位运费写在左上角,右下角若为基变量则写\(x_{ij}\)即调用的数目,若为非基变量则写\([\sigma_{ij}]\)(对应格的检验数)。

初始基可行解确定(最小元素法 P99) 每次选择费用最小的一个格,根据供应量在需求量减去对应的最大值,如果需求量减后为 0,则划去这列;如果对应的供应量减后为 0,则划去这列,反复迭代直到所有的需求都被满足。

检验最优性(闭回路法) P105 从一个非基变量格出发,画一个闭回路,要求回路上的其余所有顶点均为基变量,再将各个顶点从起点为 0 开始编号,对应非基变量的检验数\(\sigma = 偶数点运价和-奇数点运价和\),若所有检验数大于等于零,则对应的方案为最优方案。

  • 无穷多最优解:非基变量检验数为 0
  • 退化问题
    • 找基可行解时,导致列和行同时饱和,同时划去这一行和这一列,除了交叉的点以外其余\(x\)取 0,导致得到了退化的基可行解
    • 闭回路法调整时,有多个最小奇数顶点,只能取一个为换出变量,则得到了一个\(x_{ij}=0\)的退化解

方案调整 P109

  1. 选取负检验数中的最小者,作为换入变量
  2. 找闭回路并且编号,方法同上
  3. 找出奇数编号顶点中\(x\)最小的,作为调整量\(\theta\),作为换出变量
  4. 将回路中所有奇数点减去\(\theta\),偶数点加上\(\theta\),获得新的可行解
  5. 继续检验调整

指派问题 P129

已知每个人只能做一个工作,并且已知所有人做某个工作的费用,得到费用矩阵\(C\),需要求使得费用最小(\(\min z\))的解零一矩阵

匈牙利算法 P132

对于给定费用矩阵 \(C,\quad(n=r(C))\) 的指派问题

  1. 将费用矩阵\(C\)每行每列分别减去其对应行/列中的最小元素值得到\(C'\)
  2. 先逐行检验,若一行中只有一个未标记过或者只有一个没被叉标记的 0 元素,则将其括起,将其所在列的其他未标记 0 元素用叉X划去。重复进行直至每一行都没有被 0 标记或者有 2 个以上没有被标记的 0
  3. 列检验,同理 2.
  4. 将括了的(0)元素对应的解矩阵\(X\)中的元素置 1,其余元素置 0

步骤3结束后有可能会有如下几种情况 P133

  • 每一行都有被括的 0,个数\(m=n\)
    • 跳入步骤4
  • 存在未被标记的零元素,但是其对应的行或者列中未被标记过的零元素都至少有两个
    • 选择 0 元素少的行/列的某个 0 加括号
    • 用叉划去其他 0 元素,再进行行、列检验
  • 所有 0 均被标记,但是数量小于\(n\) P134(此处略过)

其他指派问题

最大化指派问题 P136 即需要求\(\max z\),可用矩阵中的最大元素减去矩阵中每个元素得到新矩阵,再使用匈牙利算法求解。

人数和事件数不等 P137 增加费用为 0 的人/事件,使用匈牙利算法求解

一个人可以同时做多件事 P138 将这个人的费用行复制一遍,再将人数和事件数调整至一致,使用匈牙利算法,求解得到的解矩阵为对应人需要做的多件事。

某事不能由某人去做 将这个人做这件事的费用取为一个足够大的 M


博弈论

两人有限零和博弈

游戏中有两个博弈者,每人均有有限个博弈策略可选,且两人的得失综合恒为 0。

博弈者分别有各自的策略集 \(S_\alpha=\{\alpha_1,\alpha_2,...,\alpha_n\}\)\(S_\beta=\{\beta_1,\beta_2,...,\beta_m\}\),则有博弈者的支付矩阵

\[ A=\begin{bmatrix} \alpha_{11} & ... &\alpha_{1n}\\ ... & ... & ...\\ \alpha_{m1} & ... &\alpha_{mn}\\ \end{bmatrix} \]

根据博弈者\(\alpha\)的支付矩阵,我们可以将该博弈记作 \(G=\{S_\alpha,S_\beta;A\}\)

最优纯策略与纳什均衡

即让自己在的选择在对方从博弈空间中任选博弈时,自己的收益相等。

例:美女硬币

男/美女 美女正面 美女反面
男正面 3 -3 -2 2
男反面 -2 2 1 -1

设男出正面的概率为\(x\),反面的概率为\(1-x\);(女出正面的概率为 y,出反面的概率为\(1-y\))。为使利益最大化,应该在对手出正面或反面的时候自己的收益相等(否则,对方就可以针对):

\[3x + (-2)\times(1-x)=(-2)\times x + 1\times(1-x)\]

\(x=3/8\);收益:\(-1/8\)。同理可列方程:

\[-3y+2(1-y) = 2y + (-1)\times(1-y)\]

\(y=3/8\);收益:\(1/8\)

最优混合策略

博弈者只能以一定的概率在策略集中随机地选择每个策略,则这种概率分布被称为混合策略。

\(x_i\)\(y_i\)为博弈者\(S_\alpha,S_\beta\)在各自策略集中选择\(\alpha_i,\beta_i\)的概率,则称\(x=(x_1...x_m)\)\(y=(y_1...y_m)\)为两个博弈者的混合策略。

\(E(x^*,y^*)=v=\min{\max{E(xy)}}=\max{min{E(xy)}}\) 时,称\(x^*,y^*\)为博弈人的最优混合策略(若\(v<0\),则需要给收益矩阵每个元素加上\(d\)使得\(v>0\)

最优混合策略求解方法 可以列出以下两个不等式组

\[ \left\{\begin{array}{lr} \sum_{i=1}^m\alpha_{ij}x_i\ge v\qquad j=1,2,...,n &\\ \sum_{i=1}^m x_i=1 &\\ x_i \ge 0\qquad i=1,2,...,m \end{array} \right. \]

\[ \left\{ \begin{array}{lr} \sum_{j=1}^n\alpha_{ij}y_j\le v\qquad i=1,2,...,m &\\ \sum_{j=1}^n y_i=1 &\\ y_j \ge 0\qquad j=1,2,...,m \end{array}\right. \]

将等式左右同时\(x_i'=\frac{x_i}{v}\),则可以得到线性规划

\[ \min S = \sum^m\_{i=1}x_i' \]

\[ \left\{\begin{array}{lr} \sum_{i=1}^m\alpha_{ij}x_i'\ge v\qquad j=1,2,...,n &\\ x_i' \ge 0\qquad i=1,2,...,m \end{array}\right. \]

\[ \min S' = \sum^m\_{i=1}y_i' \]

\[ \left\{\begin{array}{lr} \sum_{j=1}^n\alpha_{ij}y_i'\le 1\qquad i=1,2,...,m &\\ y_i' \ge 0\qquad i=1,2,...,n \end{array} \right. \]

例题,田忌赛马

r5TEB4.png

作者

Hyiker Hu

发布于

2020-12-27

更新于

2021-09-26

许可协议

评论