运筹学
2022-05-07 15:30:04 61 举报运筹学是一门研究决策问题的科学，主要使用数学模型和计算机技术来帮助决策者在复杂的环境中做出最优的决策。它的主要目标是通过优化资源分配，提高系统的效率和效果。运筹学的应用范围非常广泛，包括生产管理、物流、金融、军事、医疗等各个领域。运筹学的基本原理包括建立数学模型、确定目标函数、选择合适的决策变量、制定约束条件等步骤。通过这些步骤，运筹学可以帮助决策者找到最优的解决方案，实现资源的最大化利用，提高系统的整体性能。
作者其他创作
大纲/内容
| 绪论
概况简述：一门应用学科，它广泛应用现有的科学技术知识和数学方法解决实际中提出的专门问题，为决策者选择最优决策提供量化依据。
最优化技术：依照给定条件和目标，从众多方案中选择最佳方案。
发展概况：
二战以前--萌芽（军事运筹学的作战模型、存储论的最优批量公式、埃尔朗公式）；
二战期间--产生（运作研究Operational Research小组解决复杂的战略和战术问题）；
五六十年代--发展（从事研究的人数不多，范围较小，人员从军事转为民用——电子计算机技术迅速发展促进了推广应用——进一步细分为各个分支，学术团体、期刊、书籍、课程出现）；
七八十年代--成熟（第三代电子数字计算机出现促使运筹学得以研究大的复杂的系统）；
中国于上世纪50年代开始研究运筹学（西方引入），中国运筹学于1980年成立。
基本特点
系统的整体最优化：把相互影响的各方面作为一个统一体，从整体利益出发，寻找优化协调方案。
未来发展趋势：成熟的学科分支向纵深发展；新的研究领域产生；与新的技术结合；与其他学科的结合加强；传统优化观念不断变化；
对研究的问题进行分析，归纳出决策的目标及相关限制
多学科的配合：不同学科领域专家共同配合。
分析与表述问题
重点：弄清要解决的问题；明确实现目标；分析所处的环境和约束条件；取得统计数据资料
模型方法的应用：需要建立问题的数学和模拟模型。
表达问题中可控的决策变量、不可控变量、工艺技术条件及目标有效度量之间的相互关系
主要刊物：国际：Management Science,Operations Research,Interfaces...国内：运筹学学报、运筹与管理、系统工程学报、系统科学与数学...
工作流程
建立数学模型
重点：确定决策变量；建立目标函数；构造约束方程
对问题求解
用数学方法或其他工具对模型求解
提示：解可以是最优解、次优解、满意解；复杂模型求解需用计算机；精度由决策者提出
对模型和解进行检验
将实际问题的数据资料带入模型，找出的精确的或近似的解且要进行检验
提示：检查求解步骤和程序是否有错；检查解是否反映现实问题；敏感度检验；改变模型及其输入-观察输出（不满意则要回到第一步）
建立起对解的有效控制
任何模型都有一定的适用范围，需要确定最优解保持稳定时的参数变化范围
提示：依据灵敏度确定参数的变化范围；对模型和导出解进行修正
线性规划
决策变量；目标函数；约束条件（目标函数或约束条件均为线性）
方案的实施
提示：解的实施；实施最优解
主要解决生产计划问题，最优投资问题，合理下料问题...
在预定的任务目标下，如何耗用最少的人力物力财力去实现
主要分支
非线性规划
目标函数或约束条件不全是线性
整数规划
指派问题等
动态规划
研究多阶段决策过程的整体最优化
在线性规划的基础上，要求变量取整数值
资源分配问题、生产与存储问题、背包问题、货郎担问题（TSP）等
图论与网络
把一些研究对象用节点表示，对象间联系用线表示并赋予权重，通过对图与网络性质及优化的研究，解决实际问题
中国邮递员问题、哥尼斯堡七桥问题、最短路、最大流问题、最小费用流等
存储论
研究在各种供应和需求条件下，应当在什么时间，提出多大的订货值来补充储备，使得用于采购、储存和可能发生的短缺的费用损失的总和为最少等问题
排队论
主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量，一般考虑随机因素
博弈论
研究具有对抗局势的模型，参与每一方均有一组策略可供选择，通过博弈论选择对自己最有利的策略
典型问题：烧水沏茶、产品加工问题（线性规划）、0-1规划问题（整数规划）、戈尼斯堡七桥问题（图论）、最短路问题（动态规划）、洗刷餐具问题（排队论）、囚徒困境问题（博弈论）雪堆博弈、小鸡博弈、海盗分金币
| 线性规划及单纯形法
规划问题：1. 当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源去完成确定的任务或目标；2. 在一定的资源条件限制下，如何组织安排生产获得最大的经济效益。
线性规划问题
特征：目标函数是多个决策变量的线性函数，通常是求最大值或最小值；约束条件是一组多个决策变量的线性不等式或等式。
建模条件
优化条件：目标线性，且能用极值表示
限定条件：约束条件能用决策变量的线性不等式或等式表示
选择条件：多种可选择的方案以便找出最优方案
建模步骤
确定决策变量
找出约束条件
写出目标函数
数学模型的一般形式
向量形式
矩阵形式
标准形式
特点：1）目标函数求最大值；2）约束条件都为等式方程且右端常数项bi都大于或等于零；3）决策变量xi为非负。
1）目标函数求极小值，可将目标函数乘以（-1），化为极大值问题；
转化方法：
2）若存在取值无约束的变量xi，可令xi=xj-xk，其中xj、xk大于零；
3）约束方程小于等于，左端加上松弛变量变成等式；约束方程大于等于，左端减去剩余变量变成等式；
最优解
解：
可行解
基：m阶满秩子方阵
基解：令非基变量等于零，解等式约束方程。
4）约束方程右端常量bi小于零时，两边乘以（-1）。
基可行解：满足非负的基解。（可行基）
求解方法：
图解法：两个变量、直角坐标；三个变量、立体坐标 (？？怎么画)
解题步骤：1.画出约束等式，找到可行域；2.标出目标函数；3.平行移动目标函数，找到所需最大值或最小值交点；4.将最优解带入目标函数，求出最优值。
几种情况说明：
启示：
单纯形法：适用于任意变量(三个以上可）、但必需将一般形式变成标准形式。
凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。
顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点，则X称为顶点。
基本原理：
定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。
定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。
引理1 线性规划问题的可行解 为基可行解的的充要条件是X的正分量所对应的系数列向量是线性独立的。
定理3：若问题存在最优解，一定存在一个基可行解是最优解。（即在某个顶点取得）。
引理2 若K是有界凸集，则任何一点X∈K均可表示成为K的顶点的凸组合.
思路：
找出一个初始基本可行解（系数矩阵、人工变量法）
从初始基可行解转化为另一基可行解
注意：可行基的维数、基变量的维数、基向量的维数不论如何变换都是固定的。而且每次变化后基都是一个单位阵。
最优性检验和解的判别
计算步骤：
2）求出线性规划的初始基可行解，列出初始单纯形表
3）进行最优性检验（检验数小于等于0，即最优）
4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表
一般选择最大的一个检验数对应的变量作为换入变量。
再计算比值，得到θ，选择最小的θ对应基变量作为换出变量。（a/b=θ，若b<=0,则不考虑；若a=0,则θ=0；）
5）重复3）、4）步直到计算结束为止。
大M法：
条件：最优解中的人工变量应该为0。同时新目标函数应与原目标函数一致。
M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值。
选择最大的检验数，计算出θ，再选择最小的θ。
1）将问题化为标准型
人工变量法：在约束条件的等式左端加一组虚拟变量，得到一组对应于基向量的基变量。
两阶段法：
第一阶段：在原线性规划问题中加入人工变量，构造新的LP问题（最小化问题）。对上述模型求解（单纯形法），此时的检验数选择最小，最优性的检验数大于0。仍然选择最小的θ。若得到ω=0，说明问题存在基可行解，可以进行第二个阶段；否则，说明最优解的基变量中含有人工变量，那么原问题无可行解，停止运算。
第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。
解的判别：（记住！）
1）唯一最优解的判别：最优表中所有非基变量的检验数非零,基变量的检验数小于零，则线性规划具有唯一最优解。
2）多重最优解的判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解（或无穷多最优解）。
3）无界解的判别：某个sk>0且aik≤0（i=1,2,…,m）则线性规划具有无界解。在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解。
4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在非零的人工变量作为基变量，则表明原线性规划无可行解。
5）退化的判别：存在某个基变量为零的基本可行解。
三要素：决策变量Decision variables，目标函数Objective function，约束条件Constraints
| 对偶理论
每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。
对称形式：
LP目标函数求极大值时，所有约束条件为≤号，变量非负；
DP目标函数求极小值时，所有约束条件为≥号，变量非负。
非对称形式
若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按下表中的对应关系写出非对称形式的对偶问题。（下表很重要！！）
对偶性质
性质1 对称性定理：对偶问题的对偶是原问题。
若（LP）与（DP）都有可行解，则两者都有最优解，且它们最优解的目标函数值相等；若一个问题最优解不存在，则另一问题也不存在最优解。
该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊，或已知X＊求Y＊。
由于松弛变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：
若y＊≠0，则对应的xs必为0；若x＊≠0，则对应的ys必为0；
若xs ≠0，则对应的y＊必为0；若ys ≠0，则对应的x＊必为0；
利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。
若y＊≠0，则对应的xs必为0；若x＊≠0，则对应的ys必为0；
若xs ≠0，则对应的y＊必为0；若ys ≠0，则对应的x＊必为0；
利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。
性质6 线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量Xs对应对偶问题的决策变量Y，对偶问题的剩余变量Ys对应原问题的决策变量X。
这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量。将这对互补的基解分别带入原问题和对偶问题的目标函数有z=w。
这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量。将这对互补的基解分别带入原问题和对偶问题的目标函数有z=w。
影子价格
定义：在一对 LP和DP中，若 LP 某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于DP问题中对偶变量的最优值yi*。
影子价格的经济意义
1）影子价格不同于资源的市场价格
2）影子价格是一种边际价格
1）影子价格不同于资源的市场价格
2）影子价格是一种边际价格
影子价格的大小反映了资源的稀缺程度。影子价格越大，资源越稀缺。
对偶单纯形法
对偶单纯形法是求解线性规划的另一个基本方法。用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解。如果得到对偶问题的一个基可行解，则将这两个解分别带入各自的目标函数时其值相等（同时达到最优解）。
在原单纯形表上，找出一个对偶问题的可行基，在保持对偶问题为可行解的条件下，判断XB是否可行（XB=b是否非负），若可行则原问题达到最优解。否则，通过变换基解，直到找到原问题的基可行解（即XB为非负），这时由性质4可得原问题与对偶问题同时达到可行解。
用对偶单纯性法要保持检验数行都是非正的。
选择最小的b所对应的行变量为换出变量，计算比值（检验数一行/最小b对应行），选择最小比值所对应的列变量为换入变量。（若出现了该最小比值等于零的情形那意味着对偶问题有无穷多解）（如果最小b对应行中对应的是非负值，则不计算该比值。）
直到b那一列全为大于等于0，可以解出原问题的最优解（即b对应的那一列系数）。
| 整数规划
要求一部分或全部决策变量取整数值的规划问题称为整数规划。
不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
种类：
纯数
混合
0-1型
分支定界法
1.求解松弛问题最优解：若某一松弛问题的最优解满足整数要求，且没有其他可行分枝，得到整数规划的最优解，否则转下一步；
2.分枝与定界：任选一个非整数解的变量xi，在松弛问题中加上约束：xi≤[xi] 和 xi≥[xi]+1，组成两个新的松弛问题。
3.剪支：
若还存在非整数解并且相应的目标值大于已有整数解的最大目标值，（需要返回2）继续分枝，再检查，直到得到最优解。如果有新的原问题可行解出现，则对比后保留最优的。
若某分枝的解是整数并且目标函数值大于等于其它分枝的目标值，则将其它分枝剪去不再计算；
割平面法
1.求解松弛问题最优解；
2.若不能满足整数要求，考虑将最优解可行域中的分数部分割去，但不割去任何一个整数可行解，再求最优解。
求一个切割方程的步骤：
（1）令xi是相应线性规划最优解中为分数值（或分数部分最大）的一个基变量，由单纯形表的最终表得到（xi-基变量，xj-非基变量）
(2) 将bi和aij都分解成整数部分N与非负真分数f之和，即
得到割平面方程：（松弛变量si ）
3. 把割平面方程加到最终表中，用对偶单纯形法进行迭代，若得出的最优解为整数解，则它就是整数规划问题的最优解，停止；否则，返回第（2）步继续迭代。
指派问题及匈牙利法
已有的求解0-1 型整数规划的方法一般都属于隐枚举法。
指派问题的标准形式为：分配n 个人去完成n 项任务，每个人只能完成一项任务，每项任务只能由一个人来完成，第i 个人来完成第j 项任务的费用或时间为cij ，问如何安排才能使总费用或总时间最小？
定理 如果对系数矩阵C =（cij ） n ×n 的任一行（列）各元素减去该行（列）的最小元素，得到新矩阵B =（bij ） n ×n ，则以B 为系数矩阵的指派问题的最优解X * 也是原问题的最优解。
匈牙利法的基本思路是：根据指派问题的性质对原问题做一系列同解变换，从而得到一系列等价（同解）的指派问题，最后可得到一个只需直接观察其效率矩阵就可得到最优解的派生指派问题，该问题的最优解即原指派问题的最优解（但目标函数值不同）。
步骤：
1.变换矩阵：行列各减去最小元素；
2.行列检验：该行/列只有一个零元素，就对这个零元素打上（），对打括号的零元素所在的列/行画一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行；
3.变换：找出所有没有被覆盖元素中的最小元素，这里是2；不在覆盖线上的元素都减去2，覆盖线交叉点上的元素都加上2，其余元素不变；
4.调整：回到第二步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。
非标准型的指派问题：
1. 最大化指派问题：设L为最大化指派问题系数矩阵C中最大元素。令矩阵B＝（L-cij）nn则以B为系数矩阵的最小化指派问题和原问题有相同的最优解。
2. 不平衡的指派问题：当人数m大于工作数n时，加上m－n项虚拟工作，费用系数为0；当人数m小于工作数n时，加上n－m个虚拟的人，费用系数为0。
3. 一个人可做几件事的指派问题：若某人可做几件事，则将该人化作“相同的几个人”来接受指派，且费用系数取值相同。
4. 某事一定不能由某人做的指派问题：将该人做此事的效率系数取做足够大的数，可用M表示。
| 图与网络
相关概念
若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点(顶点)和边的集合，V—点集 E—边集。
任一条边的端点无序，即(vi, vj)与(vj, vi)是同一条边，则称它为无向边，此时图称为无向图。
边(vi, vj)的端点是有序的，则称它是有向边（或弧），vi与vj分别称为这条有向边的始点和终点，相应的图称为有向图。
如果边e的两个端点相重，称该边为环。如果两个点之间多于一条，称为多重边。对无环、无多重边的图称作简单图。含多重边的图称为多重图。
每一对顶点间都有边相连的无向简单图称为无向完全图；有向完全图是指每一对顶点间有且仅有一条有向边的简单图。
点集V可以分为两个非空子集X，Y，同一集合中任意两个顶点均不相邻，称这样的图为二分图（偶图）。
与某一个点vi相关联的边的数目称为点vi的次（也叫做度）。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。
网络--赋权图，端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。
简单链：没有重复边；初等链：既无重复边也无重复点。若在无向图中，一条链的第一个点与最后一个点重合，则称这条链为圈。无向图：链、圈；有向图：道路、回路。
一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图总可以分为若干个连通子图，每一个称为原图的一个分图（连通分支）。
图的基本性质
定理1 任何图中，顶点次数之和等于所有边数的2倍。
定理2 任何图中，次为奇数的顶点必为偶数个。
图的矩阵表示
邻接矩阵：行权矩阵列均为点，有连接就写入1。
关联矩阵：行为点，列为边，有连接写1，可知每一列必有两个1。
权矩阵：行权矩阵列均为点，有连接就写入该边权值。
树：连通且不含（简单）圈的无向图。次为1的点（悬挂点）为树叶，次大于1的点为分枝点。
图T=(V, E)是一棵树，|V|=n≥2，则T中至少有两个悬挂点；
图T=(V, E)， |V|=n，|E|=m ，则下列说法等价：(1) T是一个树；(2) T无圈，且m=n-1；(3) T连通，且m=n-1 ；(4) T无圈，但每加一条新边即得惟一一个圈；(5) T连通，但去掉任意一边就不连通；(6) T中任意两点，有惟一链相连；---->点集合相同的所有图中，树是一种含边数最少的连通图。
若图G的生成子图(支撑子图)是一棵树，则称该树为G的生成树。图G有生成树的充要条件是G是连通图。
寻求图的生成树的方法
避圈法(加边法)—在图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止。
破圈法—在图G中任意取一个圈，从圈上舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止。
具有最小权的生成树称为最小生成树(最小支撑树，最小部分树，minimum spanning tree)，简称最小树。
最小树问题：（无向图）
避圈法：
Kruskal算法 : 选最小权边
开始选一条最小的边，以后每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。
MST(Minimum Spanning Tree最小生成树)存在性定理：连通图的最小权边至少存在于图的某棵最小生成树中。
第1步：从图中任选一点vi，让vi∈U，图中其余点都包含在U’中。
故适合边数较少（相对点数）的稀疏图
Prim算法(及Dijkstra算法)
Prim：画圈找最小
第4步：重复2，3步，一直到图中所有点都包含在U中为止。
第2步：从U与U’的连线中找出最小边，这条边一定包含在最小生成树内，不妨设最小边为[vi, vj]，将[vi, vj]加粗，以标记这是最小生成树内的边。
第3步：令U∪vj→U，U’\vj →U’。
适合顶点数目稀少（相对边数）的图，即密集图
Dijkstra：标号算法，找最短邻近点
从起点开始，在与起点为端点的所有线路上，寻找与起点构成最短线路的邻近点，起点与邻近点的线路一定是整个最短线路上的一部分。然后，以邻近点为新的起点，再找出一个与它有最短线路的邻近点，依次下去，直到终点，最后得出一个从起点到终点的最短线路。若两点不相邻，则其距离就是无穷。
P标号——永久性标号(permanent label)，给vi 点一个P标号时，表示从U到vi 的最小权， vi 的标号不再改变。
T标号——试探性标号(tentative label)，给vi 点一个T标号时，表示从U 到vi 的估计最小权的上界，是临时性标号，凡没有得到P标号的点都有T标号，在变为P标号前要进行更新。
算法每一步都把某一点的T标号改为P标号，当终点vt 得到P标号时，全部计算结束。
破圈法：
算法一
从网络N中任取一个回路，去掉这个回路中权数最大的一条边，得到一个子网络N1。在N1中再任取一个回路，再去掉回路中权数最大的一条边，得N2。如此继续下去，一直到剩下的子图中不再含有回路为止，就得到了N的最小生成树。
算法二
从图G中任选一棵树T1，加上一条边e1， T1+e1中立即生成一个圈，去掉此圈中的最大权边，得到新树T2，以T2代替T1，重复(2)再检查剩余的边，直到全部边检查完为止。
最短路径问题：（可以是有向图）
最短路：总权最小的道路
求最短路有两种算法:
狄克斯屈拉(Dijkstra)标号算法（只适用于全部权为非负)
开始，先给v 1 标上P 标号P （v 1 ）=0，其余各点标上T 标号T （vj ）=+∞（j ≠1）
如果刚刚得到P 标号的点是vi ，考虑以vi 为始点的所有弧段（vi ，vj ），当vj 是P 标号时，对vj 不标号；当vj 是T 标号时，对vj 的标号进行如下修改：（括号内的T （vj ）是v 1 原有的T 标号）
T （vj ）=min{T （vj ），P （vi ）+wij }；
T （vj ）=min{T （vj ），P （vi ）+wij }；
在现有的T 标号中，寻找最小者，并将它改为新的P 标号。
重复上述过程，直到所有的T 标号都变成P 标号为止。
补充：最小树的Prim算法与最短路的Dijkstra区别
最短路只是两点之间，并不是原图的支撑子图，而最小树一定是支撑子图。
最小树是两个集合之间的最短距离，最短路关心的是终点及中间可能路过点的最短距离。
逐次逼近算法(权可以为负)
二者的标号过程基本相同，区别是Floyd标号法的P 标号不是永久性的标号，在标号过程中，它可以被其他数值所代替，改为T 标号
最大流问题
相关概念：
对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij；
流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的流量（负载量）记为fij；
满足以下条件的一组流称为可行流：1.容量限制条件，容量网络上所有的弧满足：0≤fij≤cij；2.中间点平衡条件。
任何网络上一定存在可行流。（零流即是可行流）；
割是指容量网络中的发点和收点分割开，并使s→t的流（不包括t->s）中断的一组弧的集合。割容量是组成割的集合中的各弧的容量之和，用c(v,v')表示。
网络的最大流指网络中从发点到收点之间允许通过的最大流量。 网络最大流问题指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。
在链上所有指向为s→t的弧，称为前向弧；所有指向为t→s的弧，称为后向弧；若 f 流量>0，则称这样的链为增广链；
定理：
设网络N中一个从 s 到 t 的流 f 的流量为v(f )， (V, V´)为任意一个割，则v(f ) = f(V, V´) -f(V´, V)；
最大流量v＊ (f )不大于最小割的容量，即：v＊ (f ) <=min{c(V, V´)}；
定理2（最大流最小割定理） 在网络中s→t的最大流量等于它的最小割的容量，即 v＊ (f ) = c ＊(V, V´)；
标号算法（Ford-Fulkerson）
由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。
（1）找出第一个可行流（例如所有弧的流量fij =0。）；
（2）用标号的方法找一条增广链；
首先给发点s标号(∞)，标号中的数字表示允许的最大调整量。
选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：
如果弧的起点为vi，并且有fij<Cij，则给vj标号为(Cij－fij)【容量-流量】；
如果弧的方向指向vi，并且有fji>0，则vj标号为(fji)【后向弧】；
(3) 重复第(2)步，可能出现两种结局：
标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V，未标号的点集合为V′，(V,V′)为网络的最小割。
t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步；
(4) 修改流量。设原图可行流为f，令----，得到网络上一个新的可行流f’；
(5) 擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。
| 动态规划
相关概念：
各阶段决策受制于当前面临的状态，又影响以后的发展。
这种把一个问题看做一个前后关联具有链状结构的过程，就被称为多阶段决策过程。
这种把一个问题看做一个前后关联具有链状结构的过程，就被称为多阶段决策过程。
随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。
动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法。必须对具体问题进行具体分析处理。
当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。
1、阶段（stage）：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用下标 k 表示阶段变量。
2、状态（state）：各阶段开始时的客观条件叫做状态，表示某一阶段决策面临的条件或所处位置及运动特征的量。
3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。
4、策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n{x1(s1),x2(s2),...,xn(sn)}表示。
5、状态转移方程：若第k阶段的状态sk，本阶段决策为xk(sk)，则第k+1阶段的状态sk+1也就完全确定，它们的关系一般可用公式表示：sk+1=Tk(sk , xk)；背包问题等多阶段决策问题的状态转移方程都是简单的线性形式：sk+1=sk+ xk(sk)；
6、指标函数：用来衡量策略或子策略或决策的效果的某种数量指标。分为阶段指标函数和过程指标函数。
特点：
1、可以将全过程求解分为若干阶段求解；------多阶段决策问题
2、在全过程最短路径中，将会出现当前阶段及对应状态下的的最优路径；------递推性
3、当前面的终点确定时，则之后路径的确定与前面的路径（如何找到的这个终点）无关； ------无后效性
3、逐段地求解最优路径，势必会找到一个全过程最优路径。------动态规划
2、在全过程最短路径中，将会出现当前阶段及对应状态下的的最优路径；------递推性
3、当前面的终点确定时，则之后路径的确定与前面的路径（如何找到的这个终点）无关； ------无后效性
3、逐段地求解最优路径，势必会找到一个全过程最优路径。------动态规划
适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的MDP。
思想：
将多阶段决策问题转变为一系列互相联系的单阶段决策问题，然后逐个阶段予以解决，最后达到解决整个问题的目的。
最优性原理 : 最优策略的子策略总是最优的。
求解方法：
最简单的方法－－穷举法。遍历所有可能的路径（策略），依次计算并比较。
动态规划标号法－－一般是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。
基于最优化原理，计算动态规划问题第 k 阶段和第 k+1 阶段间的递推关系式（基本方程）可表示为:
当过程指标函数为下列“和”的形式时
当过程指标函数为下列“积”的形式时
建立动态规划模型的步骤：
1. 识别问题的多阶段特性，将问题按时间或空间先后顺序划分为满足递推关系的若干阶段, 对非时序问题可人为地引入“时段”概念;
2. 正确选择状态变量 sk，满足:1.可知性：正确描述动态过程的演变, 可直接或间接确定状态变量的值;2.无后效性：到达这个状态前的过程的决策将不影响到该状态以后的决策;
3. 确定决策变量 xk以及允许决策集合Xk；
4. 写出状态转移方程 sk+1 = T (sk , xk);
5. 根据题意明确过程指标函数Vk,n，包括k阶段指标函数vk(sk,xk) 以及最优指标函数fk(sk) ;
6. 写出过程指标函数（阶段函数）的递推关系及边界条件（基本方程），应满足:a) 是定义在所有阶段上的数量函数；b) 具有可分离性，并满足递推关系；c) 过程指标函数应严格单调。
基本方程分段求解时的几种常用算法
1．离散变量的分段穷举算法
最重要的是正确地确定每段状态变量取值范围和允许决策集合的范围。列表
2．连续变量的解法
根据方程的具体情况灵活选取求解方法
0 条评论
下一页
