复习书目:<运筹学导论-初级篇>-Hamdy A. Taha

1.什么是运筹学

1.1 运筹学模型

运筹学模型的3个主要构成部分:备选方案、目标评判标准和约束条件。
一般的运筹学模型可以组织成下面的通用格式:
$max\quad or\quad min\quad Objective$
$s.t.\qquad constraints$
一个模型的解如果满足所有的约束条件，则称它是可行的(feasible)，如果既是可行的，且又取得了目标函数的最佳(最大或最小)值，则称它是最优(optimal)的。一个模型的“最优”解只是对这个模型是最好的，只有当这个模型恰当地表达了实际问题时，它的解对于实际问题才是最优的。

1.2 运筹学模型的求解

数学模型类型的多样性和复杂程度的各异性决定了求解方法迥异的特性。
线性规划(Linear Programming)是最常用的OR技术，专门用于带有线性目标函数和约束函数的模型，其他方法还有整数规划(Integer Programming)、动态规划(Dynamic Programming)(初始模型可分解成多个较小的子问题)、网络规划(Network Programming)，以及非线性规划(Nonlinear Programming)等。
大多数运筹学技术的一个特性是，问题的解常常不是通过某种闭形式得到的，而是利用某些算法求出来的。

1.3 排队模型和模拟模型

排队和模拟用于研究等待队列，它们不属于最优化技术，而是用来度量等待队列的性能。

1.4 建模的艺术

本质上，从现实世界到假定现实世界的简化，是通过把多个现实世界变量“简化“成某个单一的假定现实世界变量来实现的。

1.5 仅有数学是不够的

由于大多数决策问题总是会受到人的因素的影响，对人类心理的研究可能就成为解决问题的关键。解决问题要考虑的关键是人而不是技术。

1.6 运用运筹学的几个步骤

在实际中运用运筹学的主要步骤包括:
(1) 问题定义；
(2) 模型构造；
(3) 模型求解；
(4) 模型验证；
(5) 解决方案实施。

2. 线性规划建模

2.1 二维变量的线性规划模型

LP必须满足3条基本性质:
(1) 比例性；
(2) 可加性；
(3) 确定性。

2.2 线性规划的图解法

图解法的过程包括以下两步:
(1) 可行解空间的确定；
(2) 从可行解空间所有可行点中确定最优解。

3.单纯形方法和灵敏度分析

3.1 等式形式的线性规划模型

可以通过对问题约束施加下面两个要求来方便单纯形法的计算:
(1) 所有的约束都是等式(变量的非负限制除外)，并且具有非负的右端项。
(2) 所有变量是非负的。

3.1.1 将不等式转化为带有非负右端项的等式约束

• ($\leq$)约束:在约束的左端，增加非负的松弛变量(slack variable)。
• ($\geq$)约束:在约束的左端减去非负的剩余变量(surplus variable)。

  3.2 从图形解到代数解的转换

  在单纯形法中，解空间由$m$ 个同时成立的线性方程和$n$ 个非负变量表示。

角点的代数定义:
在$m \times n(m<n)$ 阶的方程组中，如果令$(n-m)$ 个变量等于0，然后求解其余的含$m$ 个变量的$m$ 个方程，如果有唯一解，则称相应的解为基本解(basic solution)，它是对应解空间的一个(可行或不可行)角点。这意味着角点的最大数目是$C_n^m$。

为概括从图形解到代数解的转换，我们称$(n-m)$个零变量为非基变量(nonbasic variable)；称余下的$m$ 个变量为基变量(basic variable),它的解(由解$m$ 个方程得到)称为基本解。
单纯形法通过借助于考察解空间中所有可能的基本可行解(角点)的一小部分，极大地减轻了计算负担。本质上，单纯形法利用一个智能的搜索过程，用有效的方法查找最优角点的位置。

3.3 单纯形法

3.3.1 单纯形法的迭代本质

正常情况下，单纯形法从原点开始，在这个初始点，目标函数值是零，因此合乎逻辑的问题是，能否在当前零值得基础上，通过增加非基变量的值来改进目标函数值。
单纯形法的设计要求每次增加一个变量，并且选择使目标函数值有最大改善率的那个变量。

初级单纯形法步骤

参考书目：Optimization in Operations Research, 2nd Edition, Ronald L.Rardin

中文翻译：《运筹学》，肖勇波等译

1. 初始化。任选一个初始的可行基，即非基变量为0，计算相应的基本解$\textbf{x}^{(0)}$，并令该基本解序号$t=0$。
2. 单纯形方向。在当前基本可行解处，找出每个非基变量$x_j$对应的单纯形方向$\Delta \textbf{x}$，并计算对应的成本减少$\overline{c}_j=c*\Delta \textbf{x}$。

与非基变量$x_j$相关的成本减少为：（）

$$\overline{c}_j=c*\Delta \textbf{x}$$

其中，$\Delta \textbf{x}$是增加$x_j$得到的单纯形方向。

在其他非基变量不变的情况下，增加一个非基变量的值，并计算为了满足约束，基需要进行什么变化，就可以获得单纯形方向。也就是说，需要增加的非基变量出的$\Delta x_j=1$，其他非基变量处$\Delta x_j=0$，而基中的元素要通过解方程组$A \Delta \textbf{x}=0$来获得。

1. 最优性。如果没有单纯形方向可以优化目标函数（求最大化的问题中没有$\overline{c}_j>0$，求最小化的问题中没有$\overline{c}_j<0$），则计算结束，当前解$\textbf{x}^{(t)}$为最优。否则，任选一个优化性的单纯形方向作为$\Delta \textbf{x}^{(t+1)}$，相应变量$x_p$入基。

2. 确定步长。如果单纯形方向所有元素均为非负，则计算结束，该模型可行域无界。否则，找出满足：

   $$\frac{x^{(t)}_r}{-\Delta x^{(t+1)}_r} = \text{min}\{\frac{x^{(t)}_r}{-\Delta x^{(t+1)}_r}\Delta x^{(t+1)}_j<0\}$$

   的基变量$x_r$，并令：

   $$\lambda=\frac{x^{(t)}_r}{-\Delta x^{(t+1)}_r}$$

3. 新顶点和基。计算出新解：$\textbf{x}^{(t+1)}=\textbf{x}^{(t)}+\lambda \Delta\textbf{x}^{(t+1)}$，并且用$x_p$替换基中的$x_r$。然后令$t=t+1$，再回到第一步。