线性规划

线性规划的数学模型

数学模型包括三个共同的要素

1. 决策变量，即规划问题中需要确定能用数量表示的量
2. 目标函数，它是关于决策变量的函数，也是决策者优化的目标一般追求最大($max$)或者最小($min$)
3. 约束条件，即决策变量需要满足的限制条件，通常表达为关于决策变量的等式或者不等式

线性规划的标准型

标准型示例

$$ \begin{aligned} \text{max} \quad & z = 2x_1 + 3x_2 \\ \text{s.t.} \quad & \begin{cases} x_1 + 2x_2 + x_3 = 8, \\ 4x_1 + x_4 = 16, \\ 4x_2 + x_5 = 12, \\ x_1, x_2 \ge 0. \end{cases} \end{aligned} $$

目标函数要求是求最大值即$max \ z = 2x_{1} +3x_{2}$

复杂的讲：

1. 目标函数：线性规划的目标函数通常为求最大化或最小化某一线性表达式。在标准型中，更常见的是将其转化为求最大化的形式。如果原问题是求最小化，可以通过乘以-1转化为求最大化。
2. 约束条件：
   形式：约束条件通常为等式或不等式，但在标准型中，所有的约束条件都会被转化为等式约束。这通常是通过引入松弛变量（对于不等式≤的情况）或剩余变量（对于不等式≥的情况）来实现的。
   右端项：在等式约束中，右端项（即等号右边的常数项）必须是非负的。如果是负的可以左右乘以-1来进行转化。
3. 决策变量：所有的决策变量（即线性规划问题中的未知数）都必须满足非负性约束。这意味着在标准型中，不允许出现负的决策变量值。

简单的讲：

1. 目标函数为求最大化（或可转化为求最大化的形式）。
2. 约束条件转化为等式约束，且右端项非负。
3. 所有决策变量均满足非负性约束。

线性规划的图解法

针对只有两个决策变量的线性规划问题，图解法的步骤包括

1. 画二维直角坐标系，非负约束构成坐标系的第一象限
2. 画出每条约束所对应的区域，并确定线性规划问题的可行域
3. 根据目标优化方向平移目标函数等值线，直到不能平移为止，确定线性规划问题对应的最优点
4. 根据最优点满足等式构建联立方程组，从而求解出最优方案，并计算最优方案所对应的最优目标函数值

线性规划的性质

几个基本概念

可行解和最优解

满足线性规划约束条件的解，称为可行解；所有可行解构成的集合称为可行域，能够使目标函数达到最大的解称为最优解

基、基向量与基变量

工艺矩阵A的秩为m，在n*n的矩阵A中存在一个m*m的子矩阵B，其秩为m

我们称该满秩子矩阵$B$为一个基阵，简称为基。基阵中的每一个列向量$P_j(j=1,2,3 ,\dots,m)$称为一个基向量；与基向量$P_j$相对应的变量$x_j$称为基变量。工艺矩阵中除基向量以外的其他列向量则称为非基向量，除基变量以外的其他变量则称为非基变量。

基解、基可行解与可行基

我们将变量$X$分为两部分$X ={ \left [ X_B,X_N \right ]}^T $，其中$X_B=(x_1,x_2,\dots,x_m)^T，X_N=(x_{m+1},x_{m+2},\dots,x_n)^T$

考虑约束条件$AX=b$按照上述符号定义，方程组等价于$(B,N)[X_B,X_N]^T=b$即$BX_B+NX_N=b$考虑到$B$是可逆的我们有$X_B=B^{-1}(b-NX_N)$，对应于基$B$，如果令$X_N=0$，可以得到一个解$X=[B^{-1}b,0]$这个解是对应于基$B$的基解，只有当$B^{-1}b \ge 0$时解$X=[B^{-1}b,0]$称为基可行解，基可行解对应的基阵$B$称为一个可行基。

凸集与凸组合

设$D$是$n$维欧氏空间的一点集，若$D$中任意两点$X_1$和$X_2$的连线上的所有点也属于集合D，则称集合D为一个凸集。

设$X_i,i=1,2,\dots,k$，是$n$维欧氏空间中的k个点，若存在一组数$\mu_i,i=1,2,\dots,k$，满足$\mu_i \in [0,1]$，而且$\mu_1+\mu_2+\dots+\mu_k=1$，那么$X = \mu_1X_1+\mu_2X_2+\dots+\mu_kX_k$是点$X_1,X_2,\dots,X_k$的凸组合。

几个基本定理

如果一个线性规划问题的可行域非空，则其可行域$D = \left\{ X \middle| \sum\limits_{j=1}^{n} P_jx_j=b, x_j \ge 0 \right\}$是凸集。

如果线性规划问题的可行域有界，其最优值必在某个顶点处获得。

线性规划问题的基可行解$X$刚好对应于可行域上的某个顶点。

求解线性规划的单纯形法

单纯性法

1. 将线性规划化成标准型，如下 $ \begin{aligned} & \text{max} \quad z = 2x_1 + 3x_2 \\ & \text{s.t.} \quad \begin{cases} x_1 + 2x_2 + x_3 = 8 \\ 4x_1 + x_4 = 16 \\ 4x_2 + x_5 = 12 \\ x_1, x_2 \geq 0 \end{cases} \end{aligned} $
2. 找出单位矩阵对应的$B \left \{ P_{3}、P_{4} 、P_{5}\right\} $、剩余部分对应的$N\left \{P_{1}、P_{2}\right\}$、$C_{B}\left\{0,0,0\right\}$、$C_{N}\left\{2,3\right\}$以及$b\left\{8,16,12\right\}^{T}$对应的值
3. 求$\sigma_{N} = C_{N} - C_{B} \cdot B^{-1} \cdot N$中的值，$\sigma_{N}=\left\{\sigma_{1},\sigma_{2}\right\}$，如果$\sigma_{1},\sigma_{2}$大于零，则取其中的最大值对应的$X_{max}$作为换入变量，如果$\sigma_{1},\sigma_{2}$都小于零那么就不需要进行变换，本案例中为$X_{2}$
4. 将$b$中的值对应的除以$X_{max}$对应的$P_{max}$中对应的值如果$P_{max}$中的值为零或者负数则必不可能是换出变量即不用处理，将非零最小值作为换出变量$X_{min}$,本案例中为$X_{5}$
5. 构成新的单位矩阵对应的$B \left \{ P_{3}、P_{4} 、P_{2}\right\} $、剩余部分对应的$N\left \{P_{1}、P_{5}\right\}$、$C_{B}\left\{0,0,3\right\}$、$C_{N}\left\{2,0\right\}$以及$b\left\{2,16,3\right\}^{T}$对应的值
6. 然后按照3，4，2这样的顺序持续执行直到$\sigma_{1},\sigma_{2}$都小于零
7. 最后求出$Z$,$Z=C_{B} \cdot B^{-1} \cdot b$，此时的$Z$就是该方程的最优解。

$\lambda _i$为检验系数

单纯形表法

$\lambda _i$为检验系数

解的判断及类型

1、最优解判别：若对所有的非基变量，有$\sigma_j \le 0$，则现有顶点对应的基可行解即为最优解。

2、无穷多最优解：当所有的$\sigma \le 0$，而某个非基变量的检验系数为0，同时对应的列向量中至少有一个元素大于0，则存在无穷多最优解。

3、无有限最优解：若存在某个$\sigma > 0$，又所有$P_j < 0$，则$z^{(1)}$可无限增大，线性规划有无界解。

4、无可行解：当线性规划问题中添加了人工变量，问题满足最优解条件时，基变量仍含有人工变量，表明问题无可行解。

求解线性规划的人工变量法

大M法

M是人为设定的无穷大的数值，是给基变量人为规定的$C_B$的值，用于简化单纯形法的迭代次数

例如$
\begin{aligned}
& \text{max} \quad z = 2x_1 + 3x_2 - Mx_3 - Mx_4 - Mx_5 \
& \text{s.t.} \quad \begin{cases}
x_1 + 2x_2 + x_3 = 8 \
4x_1 + x_4 = 16 \
4x_2 + x_5 = 12 \
x_1, x_2 \geq 0
\end{cases}
\end{aligned}
$

线性规划问题的标准型式

松弛变量（slack variable）是线性规划中的一种辅助变量，通常用于将不等式约束转化为等式约束，从而便于使用求解方法（如单纯形法）。

人工变量（artificial variable）是在线性规划问题的两阶段法或大M法中引入的一种辅助变量，通常用于处理等式约束或者大于等于形式的不等式约束（即 $\geq$ 型不等式）。它们帮助我们将问题转化为可直接应用单纯形法求解的形式。

​ 对于$\leq $ 型不等式：

​ $a_1x_1 + a_2x_2 + \dots + a_nx_n \leq b$

​ 为了将其转化为单纯形法的标准形式，我们引入一个松弛变量$s \geq 0 $，使得约束变为

​ $a_1x_1 + a_2x_2 + \dots + a_nx_n + s = b$

​ 等式约束：
​ $a_1x_1 + a_2x_2 + \dots + a_nx_n = b$
​ 为了将其转化为单纯形法的标准形式，我们引入一个人工变量 $A \geq 0$ ，使得约束变为：
​ $a_1x_1 + a_2x_2 + \dots + a_nx_n + A = b$

​ $ \geq$ 型不等式：

​ $a_1x_1 + a_2x_2 + \dots + a_nx_n \geq b$

​ 先引入松弛变量 $ s \geq 0 $，将其转换为：

​ $a_1x_1 + a_2x_2 + \dots + a_nx_n - s = b$

​ 然后，为了得到一个初始可行解，我们再引入一个人工变量$ A \geq 0$ ，得到：

​ $a_1x_1 + a_2x_2 + \dots + a_nx_n - s + A = b$

对偶理论与敏感性分析

对偶线性规划问题

原问题和对偶问题之间的对称关系体现为：

• 原问题的每个约束对应对偶问题的一个决策变量
• 原问题为求极大（或极小），则对偶问题为求极小（或极大）
• 原问题的目标函数系数对应于对偶问题约束右边项
• 原问题的约束右边项对应于对偶问题的目标函数系数
• 原问题的系数矩阵和对偶问题的系数矩阵互为转置关系
• 原问题的约束条件为小于等于，其对偶问题的变量为大于等于
• 原问题的约束条件为大于等于，其对偶问题的变量为小于等于
• 原问题的约束条件为等于，其对偶问题的变量为无约束

用公式表达是这样的，其中通常问题（P）是指原问题，问题（D）是指对偶问题

原问题$
\begin{aligned}
& \text{max} \quad z = CX \
& (P) \quad \text{s.t.} \quad \begin{cases}
AX \leq b \
X \geq 0
\end{cases}
\end{aligned}
$ 对偶问题$\begin{aligned} & \text{min} \quad w = Yb \ & (D) \quad \text{s.t.} \quad \begin{cases} YA \geq C \ Y \geq 0 \end{cases} \end{aligned} $

其中$X$作为一个列向量，而对偶问题中$Y$是作为一个行向量

原问题与对偶问题之间的对应关系总结表

对偶问题的基本性质

对称性

对偶问题的对偶问题即为原问题

弱对偶性

若$\bar{X}$是原问题的任一可行解，$\bar{Y}$是对偶问题的任一可行解，则有$C\bar{X} \le \bar{Y}b$

最优性

如果$\hat{X}$，$\hat{Y}$分别是问题（P）和（D）的一个可行解，且满足$C\hat{X} = \hat{Y}b$，则他们分别是问题（P）和问题（D）的最优解

最优对偶解

若$B$为原问题（P）的最优基，则$\hat{Y} = C_{B}B^{-1}$即是对偶问题（D）的最优解

互补松弛性

若$\hat{X}$，$\hat{Y}$分别是如下标准化形式的原问题和对偶问题的可行解：

$\begin{aligned} & \text{max} \quad z = CX \\ & (P) \quad \text{s.t.} \quad \begin{cases} AX + X_s = b \\ X, \, X_s \geq 0 \end{cases} \end{aligned}$$\begin{aligned} & \text{min} \quad w = Yb \ & (D) \quad \text{s.t.} \quad \begin{cases} YA - Y_s = c \ Y, \, Y_s \geq 0 \end{cases} \end{aligned}$

那么$\hat{X}$和$\hat{Y}$是两个问题最优解的充分必要条件是

$\hat{Y}X_s = 0$而且 $Y_s\hat{X} = 0$

对偶解的经济意义——影子价格

在资源配置问题中，影子价格反映了各项资源在系统内的稀缺程度（资源越紧缺，影子价格越高）

在资源配置问题中$z = C_BB^{-1}b +(C_N-C_BB^{-1}N)X_N$如果把最优目标函数看作可用资源的函数，即$z^*=z(b)=C_BB^{-1}b$，影子价格刚好对应于$z^*$对资源量$b$的导数，即影子价格等同于对偶解$𝒀^∗=𝑪_𝑩 𝑩^{−𝟏}$

在纯市场经济条件下，当资源的市场价格低于影子价格时，可以买进种资源

对偶单纯形法

$\begin{aligned} & \text{min} \quad w = 2x_1 + 3x_2 + 4x_3 \\ & \text{s.t.} \quad \begin{cases} x_1 + 2x_2 + x_3 \geq 3 \\ 2x_1 - x_2 + 3x_3 \geq 4 \\ x_1, \, x_2, \, x_3 \geq 0 \end{cases} \end{aligned}$

1. 将线性规划化成标准型，如下 $\begin{aligned} & \text{max} \quad w = -2x_1 - 3x_2 - 4x_3 \\ & \text{s.t.} \quad \begin{cases} -x_1 - 2x_2 - x_3 + x_4 = -3 \\ -2x_1 + x_2 - 3x_3 + x_5 = -4 \\ x_1, \, x_2, \, x_3, \, x_4, \, x_5 \geq 0 \end{cases} \end{aligned}$
2. 找出单位矩阵对应的$B \left \{ P_{4} 、P_{5}\right\} $、剩余部分对应的$N\left \{P_{1}、P_{2}、P_3\right\}$、$C_{B}\left\{0,0\right\}$、$C_{N}\left\{2,3,4\right\}$以及$b\left\{-3,-4\right\}^{T}$对应的值
3. 检查$b$列的数字，若都非负，检验数$\lambda_i$都为非正，则已得到最优解。停止计算。若检查b列中还有一个负的，检验数$\lambda_i$保持非正，则找出最小的$b_i$本案例中最小的$b_i$为$b_2$则其对应的$x_2$最为换出变量
4. 在单纯形表中检查$x_2$所在行的各系数$a_{xj}(j=1,2,\dots,n)$若所有的$a_{2j}\ge0$，则无可行解。若存在$a_{2j}<0$，计算$\theta=min(\frac{c_j-z_j}{a_2j} )(j=1,2,\dots,n)$即$\theta=min(\frac{\sigma_j}{a_2j} )(j=1,2,\dots,n)$求得最小的$\theta$对应的$x$作为换入变量（注：$z=\sum _{j=1}^{n}C_{Bj}*a_{2j}$）
5. 然后按照3，4，2这样的顺序持续执行
6. 最后求出$Z$,$Z=C_{B} \cdot B^{-1} \cdot b$，此时的$Z$就是该方程的最优解。

最后的解尽量要用原式给的变量

线性规划的敏感性分析

当b变化时

当$\begin{aligned} & \text{max} \quad z = -5x_1 + 5x_2 + 13x_3 \\ & \text{s.t.} \quad \begin{cases} -x_1 + x_2 + x_3 \leq 20 \\ 12x_1 + 4x_2 + 10x_3 \leq 90 \\ x_1, \, x_2, \, x_3 \geq 0 \end{cases} \end{aligned}$中第一个约束条件右端常数由20变为30时,将原问题的最后一张单纯形表转换中$B^{-1}$与新变化的$\bigtriangleup b_i(i=1,2)$相乘即$B^{-1} \times \Delta b = \begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix} \times \begin{bmatrix} 10 \\ 0 \end{bmatrix}$,形成新的单纯形表其中新的$b$=旧的$b+B^{-1}\bigtriangleup b$即$b = b + B^{-1} \Delta b = \begin{bmatrix} 20 \\ 10 \end{bmatrix} + \begin{bmatrix} 10 \\ -40 \end{bmatrix}$

未变化的最后一张单纯形表如图所示

$B^{-1}$如图所示

新的单纯形表如图所示

然后通过对偶单纯形法进行计算

当C发生变化时

如果是基变量对应的目标函数系数

如果是非基变量对应的目标函数系数

当$\begin{aligned} & \text{max} \quad z = -5x_1 + 5x_2 + 13x_3 \\ & \text{s.t.} \quad \begin{cases} -x_1 + x_2 + 3x_3 \leq 20 \\ 12x_1 + 4x_2 + 10x_3 \leq 90 \\ x_1, \, x_2, \, x_3 \geq 0 \end{cases} \end{aligned}$中目标函数中$x_3$的系数由13变为8时，最优结果不改变，$\sigma_3$减少$\bigtriangleup C_3$

未变化的最后一张单纯形表如图所示

变化后的单纯形表如图所示

当列向量系数发生变化

当$\begin{aligned} \text{max} \quad & z = -5x_{1} + 5x_{2} + 13x_{3} \\ \text{s.t.} \quad & \begin{cases} -x_{1} + x_{2} + 3x_{3} \le 20 \\ 12x_{1} + 4x_{2} + 10x_{3} \le 90 \\ x_{1}, x_{2}, x_{3} \ge 0 \end{cases} \end{aligned}$中约束条件中$x_1$的系数由$(-1,12)^T$变为$(0,5)^T$将原问题中最后一张表中$B^{-1}$与$x_1$对应系数的差值相乘，得到的结果加到原问题最后一张表中然后进行最优化处理

即$B^{-1} \times \Delta C_1 = \begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix} \times \begin{bmatrix} 1 \\ -7 \end{bmatrix}$,形成新的单纯形表其中新的$C_1$=旧的$C_1+B^{-1}\bigtriangleup C_1 $即$C_1 = C_1 + B^{-1} \Delta C_1 = \begin{bmatrix} -1 \\ 16 \end{bmatrix} + \begin{bmatrix} 1 \\ -11 \end{bmatrix}$

未变化的最后一张单纯形表如图所示

变化后的单纯形表如图所示

当增加一个约束条件时

当$\begin{aligned} \text{max} \quad & z = -5x_{1} + 5x_{2} + 13x_{3} \\ \text{s.t.} \quad & \begin{cases} -x_{1} + x_{2} + 3x_{3} \le 20 \\ 12x_{1} + 4x_{2} + 10x_{3} \le 90 \\ x_{1}, x_{2}, x_{3} \ge 0 \end{cases} \end{aligned} $中约束条件中再增加一个约束条件$2x_1+3x_2+5x_3 \le50$，在最后一张表中直接加上相关的约束条件，然后按照单纯形法\对偶单纯形法进行变换到最优状态

直接加上的表如图所示

变换后的单纯形表图所示

运输问题

运输问题的数学模型

将产销平衡表和单位运价表合二为一

若用$x_{ij}$表示从$A_i$到$B_j$的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案

$$ minz=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}\\ \sum_{i=1}^{m}x_{ij}=b_j,j=1,2,\dots,n\\ \sum_{j=1}^{n}x_{ij}=a_i,i=1,2,\dots,m\\ x_{ij}\ge0 $$

表上作业法

1. 找出初始基可行解，即在$(m\times n)$格的产销平衡表上按一定的规则，给出$(m+n-1)$个数字，称为数字格。它们就是初始基变量的取值。
2. 求各自非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。已是最优解，则停止计算，否则转到下一步
3. 确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整。
4. 重复2、3直到得到最优解为止。

确定初始基可行解

两种方法：最小元素法和伏格尔法

最小元素法

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

伏格尔法

最小元素法的缺点是：可能开始时节省一处的费用，但随后在其他处要多花几倍的运费。

伏格尔法采用的是最小运费和次小运费的差额，差额越大就应当越优先采用。

1. 在表中分别计算出各行和各列的最小运费和次小运费的差额，并填入表的最右列和最下行
2. 从行或列差额中选出最大者，选择它所在行或列中的最小元素。满足其全部的需求
3. 对未划去的元素再分别计算出各行、各列的最小运费和次小运费的差额，并填入该表的最右列和最下行。重复第一步和第二步直到给出初始解为止

伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。一般地，伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。

最优解的判别

闭回路法

在给出调运方案的计算表上，从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直向前划，当碰到一数字格时可以转90°后继续前进，直到回到其实空格为止。简单的闭回路如下图所示，复杂的是这些图形的组合

在此表中闭回路各顶点所在格的右上角数字是单位运价。

当检验数存在负数时，说明原方案不是最优解，要继续改进。

位势法

1. 问题背景

假设我们有两个供应点（A和B）和两个需求点（C和D），以及它们的供应和需求情况：

• 供应点：

  • A供应10单位
  • B供应20单位

• 需求点：

  • C需求15单位
  • D需求15单位

2. 成本矩阵

这两个供应点到需求点的运输成本如下：

3. 初始可行解

我们需要找到一个可行的运输方案，使得每个供应点的供应量与每个需求点的需求量相匹配。我们可以用西北角法来找到初始解：

1. 从A到C运输10单位（满足C的需求，A的供应耗尽）。
2. 从B到D运输15单位（满足D的需求，B剩余5单位）。

初始运输计划如下：

• 从A到C：10单位
• 从B到C：0单位
• 从A到D：0单位
• 从B到D：15单位

4. 计算位势

现在我们要计算每个供应点和需求点的位势（潜在变量）。我们可以将第一个供应点A的位势设为0：

• ( $u_A $= 0 )
• ( $u_B$ )（未知）
• ( $v_C$ )（未知）
• ( $v_D$ )（未知）

根据运输成本矩阵，我们可以得到以下方程：

1. $( u_A + v_C = \text{cost}(A, C) = 4 ) ⇒ ( 0 + v_C = 4 ) ⇒ ( v_C = 4 )$
2. $( u_A + v_D = \text{cost}(A, D) = 6 ) ⇒ ( 0 + v_D = 6 ) ⇒ ( v_D = 6 )$
3. $( u_B + v_C = \text{cost}(B, C) = 2 ) ⇒ ( u_B + 4 = 2 ) ⇒ ( u_B = 2 - 4 = -2 )$
4. $( u_B + v_D = \text{cost}(B, D) = 3 ) ⇒ ( u_B + 6 = 3 ) ⇒ ( -2 + 6 = 4 )$

所以我们得到：

• $( u_A = 0 )$
• $( u_B = -2 )$
• $( v_C = 4 )$
• $( v_D = 6 )$

5. 判断是否最优

现在我们需要检查是否可以通过调整运输路线来降低成本。我们计算每条未使用的路径的潜在差：

• 从A到D：

  • $( u_A + v_D - \text{cost}(A, D) = 0 + 6 - 6 = 0 )$（成本不变）

• 从B到C：

  • $( u_B + v_C - \text{cost}(B, C) = -2 + 4 - 2 = 0 )$（成本不变）

• 从B到D：

  • $( u_B + v_D - \text{cost}(B, D) = -2 + 6 - 3 = 1 )$（可行且成本增加）

如果计算结果为负，说明可以通过调整运输路线来降低总成本。在这个例子中，从A到D的潜在差为0，说明没有进一步的改进空间。

6. 调整方案

一般使用闭回路法进行调整。

我们再次计算位势，并检查潜在差异，如果发现有负值，就继续调整，直到所有潜在差异均为非负值，表明已经找到了最优解。

闭回路调整法

当在表中空格处出现负检验数时，表明未得到最优解。若有两个和两个以上的负检验数时一般选取最小的那个然后将它对应的空格为调入格。下图中时（2，4）为调入格。

产销不平衡的运输问题

当产销不平衡时，设立虚拟产地或者虚拟销地，对应的运费为0。

线性目标规划

正、负偏差变量$d^+,d^-$

除$x_1,x_2$为决策变量，此外，引进正偏差变量$d^+$表示决策值超过目标值的部分；负偏差变量$d^-$表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有$d^+ · d^- =0$

绝对约束和目标约束

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

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

优先因子与权系数

一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同，要求第一位达到的目标赋予优先因子$P_1$，次位的目标赋予优先因子$P_2$，并规定$P_k \gg P_{k+1}$。

目标规划的目标函数

• 要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时$min\ z=f(d^++d^-)$
• 要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，这时$min \ z=f(d^+)$
• 要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时$min\ z=f(d^-)$

例题：例 5-1 某工厂生产 I、II 两种产品，已知有关数据见表 5-1。试求获得利润最大的生产方案。

但实际上工厂在作决策时，还要考虑市场等一系列其他条件：

1. 根据市场信息，产品 I 的销量有下降的趋势，故考虑产品 I 的产量不大于产品 II。
2. 超过计划供应的原材料时，需用高价采购，会使成本大幅度增加。
3. 应尽可能充分利用设备台时，但不希望加班。
4. 应尽可能达到并超过计划利润指标 56 元。

这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。

例 5-2 例 5-1 的决策者在原材料供应受严格限制的基础上考虑：首先是产品 II 的产量不低于产品 I 的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于 56 元。求决策方案。

解 按决策者所要求的，分别赋予这三个目标$ P_1 $,$ P_2 $,$ P_3 $ 优先因子。该问题的数学模型是

$$ \min z = P_1 d_1^+ + P_2 (d_2^- + d_2^+) + P_3 d_3^- $$

约束条件为：

$$ \begin{cases} 2x_1 + x_2 \leq 11 \\ x_2 + d_1^- - d_1^+ = 0 \\ x_1 + 2x_2 + d_2^- - d_2^+ = 10 \\ 8x_1 + 10x_2 + d_3^- - d_3^+ = 56 \\ x_1, x_2, d_i^-, d_i^+ \geq 0, \, i = 1, 2, 3 \end{cases} $$

目标规划的一般数学模型为

$$ \min z = \sum_{l=1}^L P_l \sum_{k=1}^K (\omega_{lk}^- d_k^- + \omega_{lk}^+ d_k^+) $$

$$ \text{} \begin{cases} \sum_{j=1}^n c_{kj} x_j + d_k^- - d_k^+ = g_k, \, k = 1, \dots, K \\ \sum_{j=1}^n a_{ij} x_j (\leq, =, \geq) b_i, \, i = 1, \dots, m \\ x_j \geq 0, \, j = 1, \dots, n \\ d_k^-, d_k^+ \geq 0, \, k = 1, \dots, K \end{cases} $$

其中$ \omega_{lk}^-, \omega_{lk}^+ $ 为权系数。

建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一定的主观性和模糊性，可以用专家评定法给予量化。

目标规划的图解法

对只具有两个决策变量的目标规划问题，可以用图解法来分析求解。

整数规划

隐枚举法

按目标值从优到劣依次排列出组合，逐个检验其可行性，最先满足所有$s.t.$的组合为最优解。

1. 变换目标函数和约束方程组

   1. 价值系数$C_j$前的符号统一：

      在目标要求极大时，统一带负号；求极小时统一带正号。

      在不满足上述要求时，用$X_j=1-\overline{X_j}$进行变换

   2. 按$|C_j|$值从小到大排列决策变量项：

      

2. 用目标函数值探索法求最优解

   以$Z_0$为上界，逐步向下搜索，直至获得可行解为止，即到最优解

分派问题与画圈法

分派问题是一种特殊的0-1规划问题，把m项工作分派给n个人去做。

画圈法

目标为min；系数矩阵即为方阵（即每项工作只能由一个人来做，每个人只能做一项工作）

原理：找出一组位于不同行不同列的零元素画圈，对应的$x_{ij}=1$；未画圈的元素，对应的$x_{ij}=0$此时目标函数最优。

求解步骤：

1. 变换系数矩阵：使每行每列都出现0元素。（每一行减去每行最小的数，然后如果有列没有0再减去列中最小的数）
2. 从只有一个0元素的行（列）开始，给这个0元素加圈，这表示对这行所代表的人，然后划去所在行（列）中的其他0元素；然后给剩下的只有一个0元素列（行）的0元素加圈；然后划去圈所在行（列）的0元素。若每行每列都只有一个圈时（对应的$x_{ij}=1$,其余的$x_{ij=0}$）得最优解。否则到下一步

3. 若零的个数少于方阵阶数时

   1. 若出现0元素闭回路；则任选一个0画圈破闭回路，并划去同行、列其他0元素，得最优解

   2. 若无0元素闭回路：用覆盖理论解决。

      1. 对没有圈的行打勾
      2. 对已打勾的行中所有划去的0元素所对应的列打勾
      3. 再对打有勾的列中圈所对应的行打勾
      4. 重复2、3直到得不出新的勾的行、列为止
      5. 对没有打勾的行划一横线，有打勾的列划一纵线
      6. 未覆盖区所有元素减去它们中的最小数；而覆盖区的交叉元素加上刚才的最小数，其余元素不变。
4. 循环执行到圈的个数等于方阵阶数为止。

图论

图的基本概念

图：由一些点及点之间的连线组成。

边：若点与点之间的连线没有方向，则称为边；有方向则称为弧

无向图：如果一个图G是由点和边构成的，则称为无向图，记为G=(V,E)其中V,E分别是G的点集合和边集合。一条连接点$v_i,v_j\in V$的边记为$[v_i,v_j]$或$[v_j,v_i]$

有向图：如果一个图D是由点和弧所构成，则称之为有向图，记为D=(V,A)，其中，V,A分别是D的点集合和弧集合。一条方向是从$v_i$指向$v_j$的弧记为$(v_i,v_j)$

图G或图D中的点数记为$p(G)$或$p(D)$边（弧）数记作$q(G)$或$q(D)$

端点：若边$e=[v_1,v_2]\in E$，则称$v_1,v_2$是$e$的端点，也称$v_1,v_2$是相邻的。称$e$是点$v_1(v_2)$的关联边。

环：若图G中，某个边e的两个端点相同，则称e是环。若两个点之间有多于一条的边，称这些边为多重边。

简单图：一个无环、无多重边的图称为简单图

多重图：一个无环、但允许有多重边的图称为多重图。

次：以点为端点的边的个数称为v的次，记为$d_{G}(v)$

悬挂点：称次为1的点为悬挂点，悬挂点的关联边称为悬挂边。

孤立点：称次为0的点为孤立点

奇点：次为奇数的点，称为奇点，否则为偶点

链：给定一个图$G=(V,E)$一个点、边交错序列$(v_1,e_1,v_2,e_2,\dots,v_{i-1},e_{i-1},v_{i})\quad i\in(1,2,\dots,k)$如果满足$e_{i-1}=[v_{i-1},v_{i}]$则称为一条连接$v_[i-1],v_i$的链，记作$(v_1,v_2,\dots,v_k)$，其中偶数点被称为中间点

圈：链$(v_1，v_2,\dots,v_k)$中若$v_1=v_i$则称之为一个圈

初等链：若链$(v_1,v_2,\dots,v_k)$中点$v_2,v_3,\dots,v_k$都是不同的，则称之为初等链

初等圈：若圈$(v_1,v_2,\dots,v_k)$中点$v_2,v_3,\dots,v_k$都是不同的，则称之为初等圈

简单圈：若圈中含的边均不相同则称之为简单圈

连通图：图G中，若任何两个点之间至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通部分称为G的一个连通分图。

最小支撑树问题

支撑树：图b为图a的支撑树

破圈法

找到一个圈然后将这个圈中的最大值去掉，如果有两个一样的最大值，则随机去掉其中的一个，循环往复直到这个图中没有圈为止

比如选$(v_1,v_2,v_3,v_1)$这个圈，其中$(v_1,v_3)$这条边上的值最大，所以将这条边划去，然后循环往复直到没有圈为止。

最短路问题

从起点出发依次找可通行的点，然后统一出发点找最短路径的那个点，并作表

从$v_1$到$v_8$探求最短路径

结果路径为$v_1v_3v_2v_5v_8$距离为12

最大流问题

用标号法来探求最大流问题

按照路线进行划分，可以为分为$v_sv_2$和$v_sv_1$这两条初等路线，其中括号中的第一个数字为容量，第二个数字为当前流量。

$$ v_s \to^3 v_2\to^3 v_4\to^3v_t\\ v_s \to^5 v_1\to^2 v_3\to^2v_t $$

所以从$v_s\to v_t$最大的流量为5