运筹学
本文最后更新于 2024年12月7日 晚上
目录（默认关闭，点击展开）：
展开目录找的更快
点击展开目录
课时安排：
运筹学：一周两次课
第一周：2024年9月7日15:03:07
第一次课在周三，完了！好像没有什么印象了（bushi）
介绍了运筹学的绪论，印象深刻的是，都江堰水利工程项目，田忌赛马，丁谓建宫等，好像是运筹学和资源分配有关系，起源于军事领域。运筹帷幄之中，决胜千里之外。
第二次课在周五，讲述了线性规划（LP）部分内容。
利益最大的问题，成本最少的问题，如何分配厂家和经销商之间的物资。
标准线性规划：
目标函数：为最大值max，常用字母Z表示。
\(MaxZ=ax+by\)其中x、y为设定的决策变量。
约束条件\(s.t.\)
标准化：
目标函数极小值转化为极大值：取负\(minZ=-max(-Z)\)
不等式约束条件转化：
小于等于：加上松驰变量
大于等于：减去剩余变量
非正变量：取负
自由变量：作差
细节问题：加上的松驰变量或减去的剩余变量要在原来的目标函数上写上0倍的该变量。
可行域：约束条件成立构成的可行区域（和高中的线性规划类似）
几种形式的线性规划：
第二周：2024年9月14日10:02:15
图解法：
单纯形法原理：
一、线性规划问题解的概念
标准形式：
可行解：变量满足所有条件的一组值（全部可行解的集合称为可行域）
可行解集：所以可行解构成的集合
可行域：可行解集构成的n维空间区域
最优解：使其目标函数达到最优的可行解
最优值：最优解对应的目标函数值
基：研究AX\(=b\)时：A为\(m\)X\(n\)(\(n>m\))阶系数矩阵，秩为\(m\)，B是矩阵A的一个\(m\)X\(m\)的满秩子矩阵，则B为线性规划问题的一个基。
基向量：基中每一个列向量
基变量：与基向量对应的变量\(x_j\)
非基：矩阵A去除B后剩下的可以化为0的部分就是非基
非基变量：与非基向量对应的变量
基解：约束方程的所有交点
基可行解：满足变量非负约束条件的基解称为基可行解（是基解的子集）
可行基：对应基可行解的基称为可行基
二、凸集及其顶点
凸集：对于简单的二维图形，通过任意两点连线都在范围内时称为凸集。但是对于高维空间，只能用点集的数学解析表达式判断。
如果集合\(C\)中任意两个点\(X_1,X_2\)其中连线上的点也都是集合\(C\)中的点，称C为凸集，其中连线可以表示为： \[ aX_1+(1-a)X_2 其中:(0<a<1) \] 顶点：凸集中不存在两个不同的点满足上式，则称\(X\)为凸集\(C\)的顶点。（顶点是孤立的点，不能线性表示）
三、几个基本定理（question）
定理一：若线性规划问题存在可行解，则问题的可行域是凸集。
证明：
引理：线性规划问题的可行解\(X=(x_1,...,x_n)\)为基可行解的充要条件是\(X\)的正分量所对应的系数列向量是线性独立的。
证明：
定理二：线性规划问题的基可行解\(X\)对应线性规划问题可行域（凸集）的顶点。
证明：
定理三：若线性规划问题有最优解，一定存在一个基可行解是最优解。
证明：略
四、单纯形法迭代原理
三步走
1、确定初始基可行解
2、从一个基可行解转化为相邻的基可行解
3、最优性检验和解的判别
应用题的一般解题思路
引例：
1、列出目标函数和约束条件
2、将其标准化
3、写出约束条件的系数矩阵
4、看出好计算的列向量（例如单位矩阵）（注意列向量之间线性独立）将其声明为一个基
5、列向量对应的变量也就为基变量（声明一下）
6、单独用基变量表示约束条件（其实就是移项，该加加，该减减）
7、非基变量令其等于0，求出基变量的值（注意非负）
8、将基变量和非基变量代入目标函数
9、基变量中选择一个（保证非负选择小的）变量出基，非基变量选择一个（系数大的）变量入基
10、再次列出基变量的约束条件（如同步骤6，其实就是移项，该加加，该减减）
11、新的非基变量令其等于0，求出基变量的值（注意非负）
12、将基变量和非基变量代入目标函数
如此多次迭代直到找出最优解
几何意义：
单纯形法一般步骤
1、找出初始可行基
直接观察法
从系数矩阵构成的列向量中找出初始可行基（一般为单位矩阵）
加松驰变量
对于\(\leq\)的等式：加松驰变量构成的系数为1的单位矩阵
加非负的人工变量
对于\(\geq\)的等式：减去一个非负的剩余变量构成系数为1的单位矩阵
对于\(=\)的等式：加上一个非负的人工变量
这样总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。
2、最优性检验与解的判别（理论）
目标函数：\(maxZ=\displaystyle\sum_{j=1}^{n}c_jx_j+\sum_{j=n+1}^{n+m}0x_j\)
第三周：2024年9月18日10:35:17
讲了好几道题的计算步骤，（如下步骤）
表格单纯形法计算步骤：
例题：
1、判断是否为标准形式（不是）
2、将其标准化（如下图所示）
3、列出单纯形表（看出\(σ\)不是负数，说明不是最优解）
可以得到一组解\(X=(0,0,4,2,2)^T\)，不是最优解。
4、换基（\(x_2\)入基，\(x_4\)出基）
入基变量和出基变量相交处的\(a\)为主元素（主元素要化为1，该列其他元素要化为0）（如下图所示）
5、再次计算\(σ\)和\(θ\)的值（如下图）
此时可得一组解为\(X=(0,1,3,0,3)^T\)，不是最优解
6、再次换基（如上图所示，选择\(x_1\)入基，\(x_3\)出基）
入基变量和出基变量相交处的\(a\)为主元素（主元素要化为1，该列其他元素要化为0）（如下图所示）
7、再次计算\(σ\)和\(θ\)的值（如下图）
此时可以得一组解为\(X=(2,2,0,0,2)^T\)
此时\(σ\)全为负值，是最优解。
8、代入目标函数
目标函数：\(maxZ=2x_1+5x_2+0x_3+0x_4+0x_5\)
将\(X=(2,2,0,0,2)^T\)代入得：\(maxZ=4+10=14\)
9、下图为实际线性规划做出的可行域图形（加以证明（2,2）就是最优解）
单纯形法的进一步讨论
（2024年9月20日12:44:28）
人工变量法（大M法）
M是一个任意大的正数
理论废话少说，我们直接上习题
例题：
1、判断是否为标准形式（不是）
2、化为标准形式（但是没必要，我们化一个假的标准形式，目标函数求最小）
3、将约束条件化为等式
正常标准形式来说：
目标函数大M法应该减去人工变量；即\((-Mx_{n+1})\)
约束条件应该减去人工变量；即\((-x_{n+1})\)
详见补充（下图）
选择\(x_4,x_6,x_7\)为初始基变量。（因为是构造的单位矩阵）
4、列出单纯形表
5、计算单纯形表
此时得一组初始解：\(X=(0,0,0,11,0,3,1)^T\)
由\(σ\)存在小于0，不是全大于等于零，可得不是最优解
6、进行换基：(\(x_3\)入基，\(x_7\)出基)
相交元素为主元素，主元素化为1，主元素该列其他元素化为0
此时可得一组解：\(X=(0,0,1,10,0,1,0)^T\)
存在\(σ\)小于0，不是全大于等于零，所以不是最优解，进行第二次换基。
7、第二次换基：
由下表可知，\(x_2\)入基，\(x_6\)出基
相交元素为主元素，主元素化为1，主元素该列其他元素化为0（如下图）
此时可得一组解：\(X=(0,1,1,0,0,0,0)^T\)
由下表得，存在\(σ\)小于0，不是全大于等于零，所以不是最优解，进行第三次换基。
8、第三次换基：(\(x_1\)入基，\(x_4\)出基）
相交元素为主元素，主元素化为1，主元素该列其他元素化为0（如下图）
此时可得一组解：\(X=(4,1,9,0,0,0,0)^T\)
由上表得，所有的\(σ\)都大于等于0，而且基变量中不含有人工变量，所以是最优解。
即最优解为：\(X=(4,1,9,0,0,0,0)^T\)，最优值为：\(minZ=-2\)
两阶段法：
两阶段法的出现是为了解决大M法用计算机计算时，对于M只能在计算机中输入一个最大数长的数字，如果线性规划的\(a_{ij}、b_i、c_j\)等值与M相近时或者远远小于这个数字，由于计算机取值上的误差，就有可能导致计算错误。故对添加人工变量的线性规划引入两阶段法。
我们废话不多说，直接开始做。
解：
第一阶段：（判断线性规划是否有解）
化为标准形式：
修改目标函数：\(max Z^` = -x_6-x_7\)（变量只有人工变量）
此时可得一组解：\(X=(0,0,0,4,0,1,9)^T\)由检验数得，不是最优解。
换基：（\(x_2\)入基，\(x_6\)出基）
此时可得一组解：\(X=(0,1,0,3,0,0,6)^T\)由检验数得，不是最优解。
再次换基：（\(x_1\)入基，\(x_7\)出基）
再次得到一组解：\(X=(1,3,0,0,0,0,0)^T\)
此时满足\(σ\)全部都小于等于零，将解带入目标函数\(max Z^` = -x_6-x_7\)
得\(Z^` = 0\)
故此时可判断该线性规划有解！
若解中含有人工变量，或者基变量中含有人工变量，或\(Z^` \neq 0\)，则该线性规划无解，无需进行第二阶段。
第二阶段：（接着第一阶段的表格，将人工变量去掉）
目标函数：\(maxZ=-3x_1+x_3+0x_4+0x_5\)
此时可得一组解：\(X=(1,3,0,0,0)^T\)由检验数得，不是最优解。
换基：（\(x_3\)入基，\(x_1\)出基）
此时可得一组解：\(\displaystyle X=(0,\frac{5}{2},\frac{3}{2},0,0)^T\)由检验数可得，是最优解。
将最优解带入目标函数得：\(maxZ=-3x_1+x_3+0x_4+0x_5=\frac{3}{2}\)
补充结论：
若基中含有人工变量，则无解
当\(θ\)值相同时：若存在人工变量，则优先选择人工变量出基；若不存在人工变量，则保持角码最大或最小出基。可以避免陷入循环。
第四周：2024年9月25日16:58:39
数据包络分析：
数据包络分析（\(Data\) \(envelopment\) \(analysis，DEA\)）是一种基于线性规划的用于评价同类型组织工作绩效相对有效的工具手段。
废话不多说，直接开始做（了解、会列式，知道思路即可）（运筹学教程第五版\(P37\)~\(P41\)）
例题：振华银行的4个分理处的投入产出情况如下图所示。要求分别确定各分理处的运行是否\(DEA\)有效。
解：
先确定分理处1的运行是否\(DEA\)有效：
\(minE\)
\(1800λ_1+1000λ_2+800λ_3+900λ_4 \geq 1800\)
\(200λ_1+350λ_2+450λ_3+420λ_4 \geq 200\)
\(1600λ_1+1000λ_2+1300λ_3+1500λ_4 \geq 1600\)
\(15λ_1+20λ_2+21λ_3+20λ_4 \leq 15E\)
\(140λ_1+130λ_2+120λ_3+135λ_4 \leq 140E\)
\(λ_1+λ_2+λ_3+λ_4=1\)
$λ_j (j=1,...,4) $
然后再列分理处2、分理处3、分理处4的方程，并分别计算\(E\)
若\(E=1\)，则\(DEA\)有效。
线性规划的对偶问题：
（2024年9月28日22:27:44）
1、线性规划的对偶问题：
对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。
例如：工厂最大化利润的线性规划对偶问题是——收购该工厂所用的最小的资金。
2、对称形式下对偶问题的一般形式：
定义:满足下列条件的线性规划问题称为具有对称形式:
（1）其变量均具有非负约束；
（2）其约束条件当目标函数求极大时均取“≤"号,当目标函数求极小时均取“≥”号。
原问题的对偶问题，对偶问题的对偶问题就变成原问题。
例：
解：由题可知
如下图，取约束条件的右端项向量，为目标函数的价值系数，得：
\(maxW=7y_1+11y_2+14y_3\)
如下图所示：
系数矩阵是转置关系，约束条件的符号由原变量的符号得到（对偶问题约束条件的符号与原问题变量符号相反），约束条件的资源限额由原目标函数的价值系数得到。故得：
\(4y_1+8y_2+12y_3 \geq 4\)
\(5y_1+-9y_2+13y_3 = 2\)
\(-6y_1+10y_2 \leq 3\)
最后是变量的符号判断（如下图）
对偶问题变量的符号与原问题的约束条件的符号相同
最后得对偶问题答案：
3、非对称形式的原—对偶问题关系：
利用\(x\geq 1\)和\(x\leq 1\)能得到\(x=1\)的思想，可拆分等号。但是这都不重要，直接上结论！
例题：（\(P75\)）
单纯形法计算的矩阵描述:
最后讲的，还没讲完。ლ(｡-﹏-｡ ლ)
第六周：2024年10月9日14:26:31
单纯形法计算的矩阵描述（接上）
废话不多说，直接上结论：原问题的检验数的相反数恰好是对偶问题的一个可行解。
上例题：
从上面的两个表格中可得：只需要求解其中一个问题，从最优解的单纯形表可得到另一个问题的最优解。
老师说的有问题的题：
\(P77-2.9\)第二问
故可以由表可得：根据对偶理论，对偶问题的最优解为
\(\displaystyle y_1=\frac{4}{5},y_2=\frac{3}{5},y_3=1\)
对偶问题的基本性质：
1、弱对偶性
\(\displaystyle \sum_{j=1}^{n}c_jx_j\leq \sum_{i=1}^{m}b_iy_i\)
原问题的最大值 小于等于 对偶问题的最小值
推论：
1、原问题最优解的目标函数值是其对偶函数目标函数值的下界；反之，对偶问题最优解的目标函数值是其原问题目标函数值的上界。
2、若原问题有无界解，则对偶问题无界；反之，若对偶问题有无界解，则原问题无界。（注意：若则反之不成立）
3、若原问题有解而对偶问题无解，则原问题目标函数值无界；反之，若对偶问题有解而原问题无解，则对偶问题目标函数值无界。
2、最优性
原问题和对偶问题的可行解相等时，则该可行解为最优解。
3、强对偶性（对偶定理）
若原问题及其对偶问题均具有可行解，则二者都具有最优解，且值相等。
4、互补松弛性
对偶变量与松弛变量相乘为零
影子价格：
ლ(｡-﹏-｡ ლ)
对偶单纯形法：
废话不多说，直接上结论：
1、根据线性规划问题，列出初始单纯形表。检查\(b\)列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算
若检查\(b\)列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。
2、确定换出变量。按\(min\{bi｜bi＜0\}\)对应的基变量\(x_i\)为换出变量
3、确定换入变量。在单纯形表中检查\(x_i\)所在行的各系数\(α_{ij}(j=1,2,…，n)\)。若所有\(α_{ij}≥0\)，则无可行解，停止计算。
若存在\(α_{ij}＜0 (j=1,2,…，n)\), 计算\(\displaystyle θ=\min(\frac{σ}{a_{ij}}|a_{ij}<0)\)按\(θ\)规则所对应的列的非基变量\(x_k\)为换入变量，这样才能保持得到的对偶问题解仍为可行解。
4、以\(a_{ik}\)为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。
灵敏度分析：
（2024年10月11日21:05:57）
当这些参数一个或者几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解或最优基不变。这就是灵敏度分析所要研究解决的问题。
灵敏度分析的步骤可归纳如下：
1.将参数的改变通过计算反映到最终单纯形表上来。
具体计算方法是，按下列公式计算出由参数\(a_{ij},b_i,c_j\)的变化而引起的最终单纯形表上有关数字的变化。
\(∆b^`=B^{-1}∆b\)
\(∆P_j^`=B^{-1}∆P_j\)
2.检查原问题是否仍为可行解。
3.检查对偶问题是否仍为可行解。
4.按下表所列情况得出结论或决定继续计算的步骤。
| 原问题 | 对偶问题 | 结论或继续计算的步骤 |
|---|---|---|
| 可行解 | 可行解 | 问题的最优解或最优基不变 |
| 可行解 | 非可行解 | 用单纯形法继续迭代求最优解 |
| 非可行解 | 可行解 | 用对偶单纯形法继续迭代求最优解 |
| 非可行解 | 非可行解 | 引进人工变量，编制新的单纯形表重新计算 |
若B是最优基，则最优表形式如下
看不懂？我们废话不多说，直接开始做。
1、分析\(c_j\)的变化：
线性规划目标函数中变量系数\(C_j\)的变化仅仅影响到检验数（\(c_j-z_j\)）的变化。所以将\(c_j\)的变化直接反映到最终单纯形表中，只可能出现（原问题可行解，对偶问题可行解）（原问题可行解，对偶问题非可行解）这两种情况。
在第一章美佳公司的例子中：
（1）若家电Ⅰ的利润降至1.5元/件，而家电Ⅱ的利润增至2元/件时，美佳公司最优生产计划有何变化?
（2）若家电Ⅰ的利润不变，则家电Ⅱ的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？
解：（1）\(\max z=2x_1+x_2\)
\(5x_2\leq 15\)
\(6x_1+2x_2 \leq24\)
\(x_1+x_2 \leq 5\)
\(x_1,x_2 \geq0\)
即美佳公司随家电Ⅰ，Ⅱ的利润变化应调整为生产2件Ⅰ，生产3件Ⅱ。
(2)设家电Ⅱ的利润为\(（1+λ）\)元，如下:
为保证最优解，$ -1/4+1/4λ≤0\(，\) -1/2-3/2λ ≤0$
解得:\(-1/3 ≤λ≤1\)
即家电Ⅱ的利润\(c_2\)的变化范围应满足:\(2/3 ≤ c_2 ≤2\)
2、分析\(b_i\)的变化：
在美佳公司的例子中：
（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到\(32h\)，分析公司最优计划的变化；
（2）设设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。
解：（1）
将上式反映到最终单纯形法中得到以下表格，并继续用对偶单纯形法进行计算，得：
由上表得，最优计划是只生产5件家电Ⅰ
设调试工序每天可用能力为\(（5+λ）h\)，因有：
将其反映到最终单纯形表中，其b列数字为：
因\(b>0\)时最优基不变，故\(-1≤λ≤1\)。调试工序的能力应在\(4h-6h\)之间。
3、增加一个变量\(x_j\)的分析：
增加一个变量在实际问题中反映为增加一种新的产品，其分析步骤如下：
1、计算\(\displaystyle σ_{j}^`=c_j-z_j=c_j-\sum_{i=1}^{m} a_{ij}y_i^*\)
2、计算\(P_j^`=B^{-1}P_j\)
3、若 \(σ_j^′≤0\)，原最优解不变，只需将计算得到的\(P_j^′\)和\(σ_j^′\)直接写入最终单纯形表中；
若\(σ_j^′>0\)，则按单纯形法继续迭代计算找出最优。
在美佳公司的例子中：
设美佳公司又计划推出新型号的家电Ⅲ，生产一件所需设备\(A、B\)及调试工序的时间分别为\(3h、4h、2h\)，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。
解：
设生产\(x_6\)件家电Ⅲ，有\(c_6=3，P_6=(3，4，2)^T\)
最优生产计划应为每天生产\(7/2\)件家电Ⅰ，\(3/4\)件家电Ⅲ
4、分析参数\(a_{ij}\)的变化:
\(a_{ij}\)的变化使得线性规划的约束条件系数矩阵A发生变化。
在美佳公司的例子中：
若家电Ⅱ每件需设备\(A,B\)和调试工时变为\(8h、4h、1h\)，该产品的利润变为3元/件，试重新确定该公司最优生产计划。
解：
设生产工时变化后的新家电Ⅱ的生产量为\(x_2^′\)，其中：
课本上是将\(x_2\)和\(x_2^′\)分开来写。但是结果都是一样的。
由于原问题和对偶问题都为非可行解，故先设法使得原问题变为可行解。
将第一行的约束同时乘以\(-1\)再加上人工变量\(x_6\)得下表：
最优生产计划为每天生产\(11/4\)台家电Ⅰ，\(15/8\)台家电Ⅱ
5、增加一个约束条件的分析:
在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响。若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。
增加一个约束条件在实际问题中相当于增添一道工序。分析的方法是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束未起到限制作用原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。
在美佳公司的例子中：
设家电Ⅰ，Ⅱ经调试后，还需经过一道环境试验工序。家电Ⅰ每件需环境试验\(3h\)，家电Ⅱ每件需\(2h\)，又环境试验工序每天生产能力为\(12h\)。试分析增加该工序后的美佳公司最优生产计划。
解：
（1）检验原问题的最优解是否仍适用。将\(x_1=7/2，x_2=3/2\)代入\(3x_1+2x_2≤12\)，因为\(27/2>12\)，所以不适用。
（2）加入松弛变量\(x_6\)，得\(3x_1+2x_2+x_6=12\)
（3）以\(x_6\)为基变量，将上述式子反映到单纯形表求解。
由表可得，添加环境试验工序后，美佳公司的的最优生产计划为只生产四件家电Ⅰ。
参数线性规划：
灵敏度分析中研究的是\(C_j,b_i\)等参数在保持最优解或最优基不变时的允许变化范围或改变到某一值对问题最优解的影响，若C按\((C+λC^*)\)或b按\((b+λb^*)\)连续变化，而目标函数值\(z(λ)\)是参数\(λ\)的线性函数时，下面两式被称为参数线性规划。
当目标函数中\(c_j\)连续变化时，其参数线性规划的形式为：
当约束条件右端项连续变化时，其参数线性规划的形式为：
分析步骤：
（1）令\(λ=0\)求解得最终单纯形表；
（2）将\(λC^*\)或\(λb^*\)项反映到最终单纯形表中去；
（3）随\(λ\)值的增大或减小，观察原问题或对偶问题，
一是确定表中现有解（基）允许λ值得变动范围，
二是当\(λ\)值的变动超出这个范围时，用单纯形法或对偶单纯形法求取新的解；
（4）重复（3），一直到\(λ\)值继续增大或减小时，表中的解（基）不再出现变化时为止。
老师说的参数线性规划就是要一直算到底。
例题：
分析\(λ\)值变化时，下述参数线性规划问题最优解的变化。
解：（1）令\(λ=0\)求得最优解，并将\(λC^*\)反映到最终单纯形表中，得下表
表中，当\(-1/5≤λ≤1\)时，表中解为最优，且\(z=17/2+13/2 λ\)。
（2）当\(λ>1\)时，\(x_4\)的检验数>0，用单纯形表继续迭代：
当\(λ≥1\)，表中解即为最优解。这时有\(z=7+8λ\)。
（3）当\(λ≤-1/5\)时，变量\(x_5\)的检验数>0，用单纯形法迭代：
当\(-2≤λ≤-1/5\)时，\(z=8+4λ\);当\(λ≤-2\)时，\(z=0\)。
下图表明了目标函数值\(z(λ)\)随\(λ\)变化的情况。
老师最后还没讲到的两页PPT
第七周：2024年10月16日15:29:28
运输问题：
如果运输问题的总产量等于其总销量，则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题（后面再讲）。
产销平衡运输问题的数学模型可表示如下：
产销平衡运输问题数学模型
1、运输问题一定有最优解；基变量的个数\(=m+n-1\)（运输问题有优先最优解）；
2、运输问题约束条件的系数矩阵
运输问题具有下述特点：
约束条件系数矩阵的元素等于0或1；
约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。
对产销平衡运输问题，除上述两个特点外，还有以下特点：
所有结构约束条件都是等式约束；
各产地产量之和等于各销地销量之和。
废话不多说，直接上例题：
【例1】\(P83\)：某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为\(t\))以及各工厂到各销售点的单位运价(元／t)示于下表中，要求研究产品如何调运才能使总运费最小?
解：由于总产量和总销量均为48，故得知这是一个产销平衡运输问题。
用\(x_{ij}\)表示由第\(i\)个产地到第\(j\)个销地的产品数量，即可写出数学模型，如下图：
用表上作业法求解运输问题：
1、给出运输问题的初始基可行解（初始调运方案）
基本思想：同单纯形法的基本思想
方法：西北角法、最小元素法、沃格尔法
西北角法：（从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。）
步骤：
1、先满足最左上角的，\(B_1\)需要8，\(A_1\)产量16可以一次满足，\(B_1\)满足则划去该列
2、再进行到下一步
3、
4、
5、
6、
由西北角法得一组初始基可行解：\(X_{11}=8,X_{12}=8,X_{22}=6,X_{23}=4,X_{33}=8,X_{34}=14\)。总费用：\(372\)
最小元素法：
由最小元素法得一组初始基可行解：\(X_{13}=10,X_{14}=6,X_{21}=8,X_{23}=2,X_{32}=14,X_{34}=8\)。总费用：\(246\)
沃格尔法：
罚数=次小费用-最小费用（行罚数和列罚数）；
找出最大的罚数行或列所对应的最小费用优先安排；
重复计算步骤
由沃格尔法得一组初始基可行解：\(X_{13}=12,X_{14}=4,X_{21}=8,X_{24}=2,X_{32}=14,X_{34}=8\)。总费用：\(244\)
2、解的最优性检验
解的最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。
方法： 闭回路法、位势法
闭回路法：
空格直行，数字直行或拐弯。奇加偶减（单位运价）
位势法（对偶变量法）：
（1）增加一位势列和位势行并计算位势
（2）计算位势
\(σ_j=c_{ij}-(u_i+v_j)\)
例如根据下表得基变量的检验数：\(σ_j=c_{13}-(u_1+v_3)=4-(u_1+v_3)=0\)
其他的变量以此类推。
为计算简便，常任意指定某一位势等于一个较小的整数或零。
（3）计算检验数
\(σ_j=c_{ij}-(u_i+v_j)\)
3、解的改进
方法：闭回路调整法
解改进的具体步骤为：
第一步：选出一个检验数为负的空格(一般选具有最负值的检验数的空格，如果两个空格的检验数一样，则任选一个)，然后做选出空格的闭回路。
第二步：从空格处，即闭回路的第1个顶点出发，沿闭回路前进，在闭回路的所有第偶数个顶点(即第奇数次拐角点)的调运量中选取一个最小的调运量。
第三步，在空格中填上所选的最小调运量，并使闭回路中所有第偶数个顶点(奇数次拐角)的调运量减去这个最小调运量，第奇数个顶点(偶数次拐角)的调运量加上最小调运量。
再用位势法或闭回路法求这个新解各非基变量的检验数，结果示于表中各空格的小圆圈内。
4、几点说明
1）多个空格（非基变量）的检验数为负，任何一个都可以作为换入变量。一般\(σ_{ij}<0\)中最小的对应变量作为换入变量。
2）最优解时，如果有某非基变量的检验数为0，则该运输问题有无穷多解。
3）退化解：当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，以使迭代过程中基变量个数始终恰好为\(（m+n-1）\)个。
运输问题的进一步讨论：
一、产销不平衡的运输问题
当产大于销时，加入假想销地（假想仓库），销量=产量减去销量，运费为0（强制运送运费为M）
当销大于产时，加入一个虚设的产地去生产不足的物资，产量=销量减去产量，运费为0
二、有运转的运输问题
例题：
图中给出了一个运输系统，它包括两个产地(①和②)、两个销地(④和⑤)及一个中间转运站(③)，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点连线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。
解：以M表示足够大的正数，可将该运输问题的运输表列出，如下所示：
\(Z=c_{14}x_{14}+c_{25}x_{25}+c_{23}x_{23}+c_{33}x_{33}+c_{34}x_{34} =2×10+4×20+2×20+3×20+5×20=300\)
第八周：2024年10月23日14:29:57
（续上）应用问题举例：（P99）
一句话：将其他不是运输问题的问题通过运输问题数学模型转化为运输问题求解。┑(￣Д ￣)┍ Ｏ(≧口≦)Ｏ
目标规划：
目标规划是由线性规划发展演变而来
线性规划是研究资源的有效分配和利用
目标规划是实行目标管理的有效工具，它依据企业制定的经营目标以及这些目标的轻重缓急次序，考虑将现有资源如何分配能达到规定目标或从总体上离规定目标的差距为最小。
目标规划的数学模型：
好！我们废话不多说，直接开始上例题：
例：某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据如下：
不需求解，只需列出目标规划：
\(min\{P_1d_1^-,P_2d_2^+,P_3d_3^-\}\)
目标规划的图解法：
还是上面的例题：通过特殊点带入得到\(d^+\)和\(d^-\)的方向。
第九周：2024年10月30日17:34:00
（续上）目标规划
解目标规划的单纯形法：
1、检验数分列的单纯形法
废话不多说，直接上例题：上面的例子
\(min\{P_1d_1^-,P_2d_2^+,P_3d_3^-\}\)
可列出下表：（老师课件上截的，我也懒得弄表格了）
目标函数：\(minZ=P_1d_1^-+P_2d_2^++P_3d_3^-\)
需要注意的点是，检验数和以往不同，这里的检验数是一个列向量。
由于非基变量\(d_1^+\)和\(d_3^+\)的检验数都是零，故知有多重最优解(满意解)。
如以\(d_1^+\)为换入变量继续迭代：
以\(d_3^+\)为换入变量继续迭代：
再从\(Ⅳ\)和\(Ⅴ\)的结果继续迭代，可得结果\(Ⅵ\)，将结果汇总如下：
2、对优先因子给定权重的计算方法
由前述目标规划中的优先因子应满足\(P_1\gg P_2 \gg P_3\)····，因此不妨在模型中假设优先因子\(P_k\)的权重等于\(10^{k-1}\)。
这样就不需要在单纯形法计算中将优先级分列，只需按一般单纯形法进行计算即可。
3、优先级分层优化的计算方法
因目标规划求解时,遵循从高优先级到低优先级逐层优化的原则,故为保证较低层级的优化在较高层级优化的约束范围内进行。可将上一层级目标的优化值作为约束,加到下一层的模型中,这种方法也称为字典序计算法。
1、先列出来第一层级的优化模型：
得：\(x_1=0,x_2=0,x_3=60,d_1^-=d_1^+=0,d_2^-=36,d_2^+=0,d_3^-=48,d_3^+=0\)
2、将\(d^-_1=0\)加到第一层级的优化模型中，写出第二层的模型：
得：\(x_1=0,x_2=0,x_3=60,d_1^-=d_1^+=0,d_2^-=36,d_2^+=0,d_3^-=48,d_3^+=0\)
3、将\(d^-_2=0\)加到第二层级的优化模型中，写出第三层的模型：
得：\(x_1=4.8,x_2=2.4,x_3=12,d_1^-=d_1^+=0,d_2^-=7.2,d_2^+=0,d_3^-=0,d_3^+=0\)
目标规划的灵敏度分析：
整数规划:
整数线性规划的数学模型及解的特点:
（2024年11月2日14:31:55）
1、整数规划（简称IP）
要求部分或全部决策变量取整数值的规划问题。
不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若该松弛问题是一个线性规划，则称该整数规划为整数线性规划，简称ILP。
2、整数线性规划的数学模型的一般形式：
\(\displaystyle max(min)z=\sum_{j=1}^{n}c_jx_j\)
就是比之前多了个\(x_1,x_2,...,x_n\)中部分或者全部取整数。
3、整数线性规划的分类：
如果所有的变量都限制为(非负)整数，就称为纯整数线性规划或称为全整数线性规划。
如果仅一部分变量限制为整数，则称为混合整数规划。
整数线性规划的一种特殊情形是0-1规划，即变量的取值仅限于0或1。本章中的指派问题就是一个0-1规划问题。
4、解的特点：
整数规划问题的解是松弛问题的解的子集
总的来说，先求整数规划的松弛问题的解，然后通过解的特点发现不是临近的整数点集。需要通过割平面法求得最优整数解。
解纯整数规划的割平面法：
推导过程在\(P126-P127\)
总结来说，重要的公式如下：
\(\displaystyle \sum_{j\in k}(-f_{i0·j})x_j\leq-f_{i0}\)
左边是非基变量的小数，右边是b值拆分出来的小数
其中：b值拆分出来的小数要求如下：
整数部分是不超过该数的最大整数，小数部分是非负真分数。
我们废话不多说，直接上例题：
例：用割平面法求解纯整数规划：
解：引入松弛变量\(x_3,x_4,x_5\),化为标准形式后，单纯形表如下：
显然，得出的解不是整数解：
拆分b值：\(x_1:\frac{13}{7}=1+\frac{6}{7}\)和\(x_2:\frac{9}{7}=1+\frac{2}{7}\)和\(x_3:\frac{31}{7}=4+\frac{3}{7}\)。要找出最大的小数部分所对应的那一行产生割平面约束。
因为\(x_1\)的小数部分最大，故选择\(x_1\)那一行：
又因\(x_3\)和\(x_5\)对应的为非负真分数，故无需拆分
得： \[ -\frac{1}{7}x_3-\frac{2}{7}x_5\leq-\frac{6}{7} \] 引入松弛变量\(x_6\)，得割平面方程： \[ -\frac{1}{7}x_3-\frac{2}{7}x_5+x_6=-\frac{6}{7} \] 将上述割平面方程带入表格中，用对偶单纯形法得：
经过对偶单纯形法迭代后（此处省略）得：
类似的继续割平面：
拆分b值：\(x_2:\frac{5}{4}=1+\frac{1}{4}\)和\(x_3:\frac{5}{2}=2+\frac{1}{2}\)和\(x_5:\frac{7}{4}=1+\frac{3}{4}\)
因为\(x_5\)的小数部分最大，故选择\(x_5\)那一行：
又因\(x_4\)对应的为非负真分数，\(x_6\)对应的为负小数，故只需对\(x_6\)拆分即可：\(-\frac{3}{4}=-1+\frac{1}{4}\)
得： \[ -\frac{1}{4}x_4-\frac{1}{4}x_6\leq-\frac{3}{4} \] 引入松弛变量\(x_7\),得割平面方程 \[ -\frac{1}{4}x_4-\frac{1}{4}x_6+x_7=-\frac{3}{4} \] 将上述割平面方程带入终表中：然后再用对偶单纯形法求解（此处仍然省略）
得最终解为：\(X=(1,2,4,3,1,0,0)^T\)
故：\(x_1=1,x_2=2,max z=1\)
第十周：2024年11月6日19:36:32
（续上）整数规划
分支定界法：
任意选一个非整数解的变量\(x_i\)在松弛问题中加上约束：\(x_i\leq [x_i]\)和\(x_i\geq[x_i]+1\) ，组成两个新的松弛问题，称为分支。
当原问题是求最大值时，松弛问题目标值是分支问题的上界;
当原问题是求最小值时，松弛问题目标值是分支问题的下界。
我们废话不多说，我们直接上例题：
\(P131\)求解:
\(max Z=x_1+x_2\)
\(s.t. \left\{ \begin{matrix} x_1+\frac{9}{14}x_2\leq\frac{51}{14} \\ -2x_1+x_2\leq \frac{1}{3} \\ x_1,x_2\geq0\\ x_1,x_2取整数 \end{matrix} \right.\)
解：
记整数规划问题为\(IP\),它的松弛问题为\(LP\)。
将\(LP\)标准化。
用单纯形法解\(LP\)得最优解为：\(x_1=\frac{3}{2},x_2=\frac{10}{3}\)最大值为：\(max Z=\frac{29}{6}\)
易知\(LP\)的最优解不符合整数要求，故可任选一个变量，如\(x_1=\frac{3}{2}\)进行分支。
可分为：\(x_1\geq 2\)和\(x_1\leq 1\)两个分支部分（如下图），中间的部分都是小数被舍去。
如上图，左侧绿色部分的分支求解为\(x_1=1,x_2=\frac{7}{3}\)，\(maxZ=\frac{10}{3}\)
右侧紫色部分的分支求解为\(x_1=2,x_2=\frac{23}{9}\),\(maxZ=\frac{41}{9}\)
由于\(\frac{41}{9}>\frac{10}{3}\),所以优先选择右侧紫色部分再次进行分支，对\(x_2\)进行分支。
可分为：\(x_2\geq3\)和\(x_2\leq2\)两个分支部分（如下图），可行域就只剩如图所示部分。
上面为\(x_2\geq 3\)没有交集，故无可行解
下面为\(x_2\leq2\)最优解为\(x_1=\frac{33}{14},x_2=2,maxZ=\frac{61}{14}\)
因为\(x_2\)为整数，故再次将\(x_1\)分支为\(x_1\leq2,x_1\geq3\)，二者之间的被舍去。（如下图）
左边\(x_1\leq2\)得最优解为\(x_1=2,x_2=2,maxZ=4\)
右边\(x_1\geq3\)得最优解为\(x_1=3,x_2=1,maxZ=4\)
这两个解都是该整数规划的最优解。
逻辑流程图：
0-1型整数规划：
背包问题模型：
\(\displaystyle maxZ=\sum_{i=1}^{n}c_ix_i\)
\(s.t. \left\{ \begin{matrix} \displaystyle\sum_{i=1}^{n}a_ix_i \leq b \\ x_{i}=0或1(i=1,2,3..n) \end{matrix} \right.\)
含有相互排斥的约束条件的问题
固定费用问题
工件排序问题
0-1型整数规划的求解方法：隐枚举法
指派问题：
指派问题的标准形式及其数学模型：
指派问题的标准形式（以人和事为例）是：有\(n\)个人和\(n\)件事，已知第\(i\)做第\(j\)件事的费用为\(c_{ij}\)，要求确定人和事一一对应的关系，使得完成这些事情的总费用最小。
\(min Z=\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}\)
\(s.t. \left\{ \begin{matrix} \displaystyle\sum_{i=1}^{n}x_{ij} = 1 \\ \displaystyle\sum_{j=1}^{n}x_{ij} = 1 \\x_{ij}=0或1(i=1,2,3..n) \end{matrix} \right.\)
匈牙利解法：（只针对最小化的目标函数）
各行元素分别减去本行最小元素，此时出现0元素；
对每行每列画零元素
继续变换系数矩阵；各行元素分别减去本行最小元素，此时出现负元素，加上该值的绝对值使其变为零；
再对每行每列画零元素
直到有全部的独立零元素
（非标准形式的指派问题化为标准形式即可（虚拟行，虚拟列））
第十一周：2024年11月13日22:20:18
动态规划：
注：非线性规划本科不讲
不考，所以不写
第十二周：实训
第十三周：实训
第十四周：2024年12月5日08:35:38
图与网络分析：
历史上的哥尼斯堡七桥问题（无解）和欧拉回路：
环球旅行问题（有解）：
图的定义：
图的分类：
有向图和无向图：
有向图：由点和边构成
无向图：由点和弧构成
一条边的两个端点是同一个点称为环
两个端点之间有两条及以上的边称为多重边
简单图和多重图和完全图和有向完全图：
简单图：无环，无多重边的图
多重图：无环，有多重边的图
完全图：每个顶点间都有边相连的无向简单图
有向简单图：任意两个顶点之间有且仅有一条有向边的简单图
二部图：一个图可以被分为两个部分，这两个部分的并集为该图，交集为空，使得每条边的两个端点一个属于那个，一个属于那个，则称该图为二部图。
顶点的次：
以点\(v\)为端点的边的个数称为点\(v\)的度（也叫次），记作\(d(v)\)
其中：环计为两度
孤立点：次为0
悬挂点：次为1
悬挂边：悬挂点关联的边
奇点：次为奇数
偶点：次为偶数
定理：
所有顶点度数之和等于所有边数的两倍
任意一个图中，奇点的个数为偶数
出次和入次：
出次：\(d^+(v_i)\)
入次：\(d^-(v_i)\)
有向图中：一个点的出次和入次之和就是该点的次，所有顶点的入次之和等于所有顶点的出次之和。
子图：
生成子图和支撑子图：
生成子图：含有部分顶点部分边
支撑子图：含有所有顶点部分边
网络的定义：
一个始点一个终点，中间部分叫中间点，每条弧上对应的数字叫做权，这样的图称为网络
链：点边点边交替排列。
链长：链中边的个数。
初等链：没有重复的点和边
圈：链的起点和终点为一个点。
初等圈：无重复点也无重复边
对于无向图来说，道路与链、回路与圈的意义相同。
连通图：一个图中任意两点至少有一条链相连。
欧拉回路：
经过每边一次且仅一次。
树：
连通且不含圈的无向图称为树
树叶：次为1的点
分枝点：次大于1的点
图的生成树：
顾名思义：图生出的树，这个树是这个图的支撑子图，图中属于生成树的边为树枝，不在生成树中的边为“弦”
一个图有生成树的充要条件是：图是连通图
最小生成树：
一个生成树上的所有树枝上的权总和为生成树的权，具有最小权的生成树称为最小生成树。
最小生成树的两种算法：
避圈法：
将权从小到大排列，避开圈选边
破圈法（管梅谷算法）：
麻烦
根树及其应用
（2024年12月7日22:10:05）
根树：
有向树中，恰好有一个节点的入次为0，其余节点入次都为1，则称该有向树为根树。
在根树中，若每个顶点的出次小于等于m，则称m叉树，若每个顶点的出次恰好等于m或0，则称完全m叉树。
最短路问题：
两个算法：
1、Dijkstra算法（迪杰斯特拉算法）
初始T标号都是无穷，相互比较将小的T标号该为P标号并记录路径，直到进行全部完毕
2、Floyd算法