导图社区 运筹学 2023.8.9
是大学运筹学课程的复习总结,主要涉及教材中的难点问题和考点,如最大流问题、最小费用最大流问题、最短路问题、单纯形法、大M法、对偶问题、对偶单纯形法、一般线性规划问题解的四种情况等
编辑于2023-08-09 11:09:17 北京市1)如果不可避免地还是会被伤害,而受害者不需要过了几十年才敢讲出来,而是在事件发生当时,就知道自己受委屈了,立刻找人求助,向人倾吐,这也是一种进步。最起码,受害者知道“我不应该被如此对待”。 2)能看见自己的“不幸”,意味着他们对生活是充满更高期望的。 3)就是他们意识到,这不是他们想要的生活,他们不能再这样下去了。 4)一个人在痛哭的时候,他在用自己的方式争取一次喘息,固然痛苦,但他消化完痛苦的味道,就可以继续上路。
1)现如今,一个人可以通过很多方式来展示自己的影响力,比如通过展示智慧或善良。但在人类社会早期,展示影响力最有效的方式是通过暴力。是的,智慧的确很重要,但在过去,四肢发达的人比头脑发达的人更容易存活。但通过蛮力和侵略获得影响力的人,很少能同时具备亲和力。所以,如果某人能兼备影响力与亲和力,那他就是个“稀有物种”:在生死关头,手握生杀大权又待人友善的大人物往往会给人活路。所以在过去,找到这种人作为领导者,是人类的生存之道。 2)真诚的微笑需要调动面部的两大肌肉群:嘴角的肌肉和眼角的肌肉。嘴角的肌肉微微向上提起,而眼角的肌肉则会放松,并略微向下弯曲。而假装出来的微笑只有嘴角的肌肉会动,眼部的肌肉几乎不动。 3)如果内心处于正确的状态,充满魅力的行为和肢体语言就会自然而然地流露出来。
1)一时学好难免有作秀之嫌,但一路学好就一定是真的。因为很多事情不是事情本身决定性质,而是做这件事情的时间。坚持就要忍受痛苦。一家企业之所以能够忍受巨大的痛苦,就是因为它有理想,对自己的事业有一种崇高感。没有理想和毅力,就不能坚持,没有行动,就不能发展下去。 2)有两句话特别好地反映了我们当时和现在选择商业伙伴的标准。第一是价值观上要趋同,第二能力上要互补。能力不互补那就不用合作了,价值观不趋同就合作不好。这两句话要贯穿到我们在外部商业伙伴和内部商业伙伴的选择上。 3)品牌的作用就是让消费者在面对很多商品无法作出放心选择的时候,可以帮助消费者解决识别困难的问题。一般商品的品牌是质量、服务的一种标准化体现,消费者凭借商品的品牌就可以放心简便地购买。
社区模板帮助中心,点此进入>>
1)如果不可避免地还是会被伤害,而受害者不需要过了几十年才敢讲出来,而是在事件发生当时,就知道自己受委屈了,立刻找人求助,向人倾吐,这也是一种进步。最起码,受害者知道“我不应该被如此对待”。 2)能看见自己的“不幸”,意味着他们对生活是充满更高期望的。 3)就是他们意识到,这不是他们想要的生活,他们不能再这样下去了。 4)一个人在痛哭的时候,他在用自己的方式争取一次喘息,固然痛苦,但他消化完痛苦的味道,就可以继续上路。
1)现如今,一个人可以通过很多方式来展示自己的影响力,比如通过展示智慧或善良。但在人类社会早期,展示影响力最有效的方式是通过暴力。是的,智慧的确很重要,但在过去,四肢发达的人比头脑发达的人更容易存活。但通过蛮力和侵略获得影响力的人,很少能同时具备亲和力。所以,如果某人能兼备影响力与亲和力,那他就是个“稀有物种”:在生死关头,手握生杀大权又待人友善的大人物往往会给人活路。所以在过去,找到这种人作为领导者,是人类的生存之道。 2)真诚的微笑需要调动面部的两大肌肉群:嘴角的肌肉和眼角的肌肉。嘴角的肌肉微微向上提起,而眼角的肌肉则会放松,并略微向下弯曲。而假装出来的微笑只有嘴角的肌肉会动,眼部的肌肉几乎不动。 3)如果内心处于正确的状态,充满魅力的行为和肢体语言就会自然而然地流露出来。
1)一时学好难免有作秀之嫌,但一路学好就一定是真的。因为很多事情不是事情本身决定性质,而是做这件事情的时间。坚持就要忍受痛苦。一家企业之所以能够忍受巨大的痛苦,就是因为它有理想,对自己的事业有一种崇高感。没有理想和毅力,就不能坚持,没有行动,就不能发展下去。 2)有两句话特别好地反映了我们当时和现在选择商业伙伴的标准。第一是价值观上要趋同,第二能力上要互补。能力不互补那就不用合作了,价值观不趋同就合作不好。这两句话要贯穿到我们在外部商业伙伴和内部商业伙伴的选择上。 3)品牌的作用就是让消费者在面对很多商品无法作出放心选择的时候,可以帮助消费者解决识别困难的问题。一般商品的品牌是质量、服务的一种标准化体现,消费者凭借商品的品牌就可以放心简便地购买。
运筹学
图与网络
最大流问题
可行流
(1)容量限制条件:每条弧上的流量都不超过其容量
(2)中间点流量平衡条件:对于容量网络中任意中间点,其总输出量等于总输入量
(3)总流量守恒条件:发点的总流出量等于收点的总流入量
增广链
同时满足下列两个条件,则称该链为容量网络的可增广链,简称增广链:(1)前向弧流量可增条件;(2)后向弧流量可减条件。也就是说,增广链上的前向弧均为非饱和弧,后向弧均为非零流弧。它的实际含义是可以增大流量的链。因此,在一个容量网络中,如果存在增广链,那么就可以用来改善当前的可行流
前向弧、后向弧
单看一条弧本身,不存在前向弧或后向弧的说法,只有相对于某条链的方向来说,该链上的某条弧才分为前向弧或后向弧;如果要增加某条链上的流量,必须增加前向弧的流量,同时减少后向弧的流量。这就意味着,如果某条链上所有前向弧的流量可以增加,所有后向弧的流量可以减少,沿着这条链就可以增加当前流的流量,使得总流量增大
如果弧实际的方向与规定的链的方向一致,则称该弧为关于链的前向弧,否则,称为关于链的后向弧。在不引起混淆的情况下,简称前向弧或后向弧
截集
对于容量网络,将顶点集合V分成两个互不相交的子集V1和V2,称所有起点在v1中、终点在v2中的弧(jie 相当于分割成的两个系统的从第1个系统到第2个系统的路径【命运的漏网之鱼】,起点在第一个系统和终点在第2个系统这两个条件同时满足的弧才属于截集,同时有除起点和终点的个数的2的个数次方个截集,截集数量与图的连接方式无关,与点的个数有关,如共6个点,有C40+C41+C42+C43+C44=1+4+6+4+1=2的4次方=16个截集,最好画圈圈而不是画条线确定分成的两个系统)构成的集合为对应于v1和v2的截集,简称截,记作(v1,v2),进一步,将截集(v1,v2)中所有弧的容量之和称为截集的截量,记作c(v1,v2);进一步,容量网络D的所有截集中截量最小的截集称为最小截集
根据定义,如果将一个截集从网络中去掉,则从发点到收点的一切通路都将切断。也就是说,任意截集都是容量网络中从发点到收点的“必经之路”,任意可行流的流量都不会比任意截集的截量更大。特别地,最小截集指示了网络的最薄弱之处,所包含的弧实际上是网络中的“瓶颈”所在,要想让网络的总流量增大,必须优先考虑增大相应弧的容量
在容量网络中寻找最大流的过程和寻找最小截集的过程是一致的,只要找到其中之一,同时会得到另一个
定理
1、在网络流图中,对于可行流,若存在增广链,则该可行流一定可以改进,使得流量增大
逆定理也成立,即当可行流的流量可以增加时,一定存在关于该流的增广链
2、(最大流判定定理)在网络流图中,可行流是最大流的充分必要条件为不存在关于可行流的增广链
根据定理2,网络中的最大流问题就转化成寻找增广链的问题。如果能够找到增广链,则可以沿着增广链增加流量,这样的过程可以不断重复,直到再也找不到增广链为止。这实际上给出了最大流求解的一种算法思想
3、容量网络的任意一个可行流所对应的流量不大于任何一个截集的截量(jie 包括最小截集,即最薄弱的截集)
根据定理3,任何可行流的流量都是截量的下界;反之,任何截量都是流量的上界。如果两者能够相等,则相应的流一定是最大流,截集也一定为最小截集
定理4(最大流最小截定理)在容量网络中,从发点到收点的最大流的流量一定等于分离发点和收点的最小截集的截量
最大流标号算法
第1步:通过标号寻找增广链
首先,从发点开始,寻找其相邻顶点,按照相应弧的方向将所有相邻顶点进行标号;然后,考虑刚获得标号的顶点,寻找其没有获得标号的相邻顶点,进行标号;这样不断重复进行,直到收点得到标号(得到增广链)或者无法使收点得到标号且标号无法再进行(迭代终止)
第2步:沿增广链增加流量
检查第1步的最终结果,如果收点得到标号,说明增广链存在,反向追溯标号的获得过程得到增广链,沿着增广链调整流量。调整后得到一个新的可行流,回到第1步,通过标号寻找关于新流的增广链,如此不断迭代,直到达到终止条件
第一步 给出一个初始可行流,应尽量接近最大流
可按以下原则调整各弧的流量,使其尽量接近最大流
(1)找出容量网络中的回路或圈,给回路或圈上各弧同一流量值,使回路或圈上容量最小的弧优先达到饱和
(2)找出从起点到终点的路,给路上各弧同一流量值,使路上容量最小的弧优先达到饱和
第二步 给顶点标号找增广链,同时求出这条链可调整的最大流量值
(1)首先对起点v1标号(0, ∞)
(2)从v1可达v2、v3:(v1, v2)为正向饱和弧,不能入链,故v2不标号;(v1,v3)为正向非饱和弧,可以入链,v3标(+v1,4)
(3)从v3可达v2、v5:(v3, v2)为反向非零弧,可以入链,v2标(-v3,1); (v3,v5)为正向饱和弧,不能入链,v5不标号
(4)从v2可达v4、v5:(v2, v4)为正向非饱和弧,可以入链,v4标(+v2,1); (v2,v5)为反向非零弧,可以入链,v5标(-v2,1)
(5)从v4可达v6:(v4, v6)为正向非饱和弧,可以入链,v6标(+v4,2),得一条增广链:L1={v1、v3、v2、v4、v6}
(6)从v5可达v6:(v5, v6)为正向非饱和弧,入链,v6标(+v5,1),得另一条增广链:L2={v1、v3、v2、v5、v6}
故当前可行流非最大流,沿增广链L1方向调整流量1(正向弧增加流量1,反向弧减少流量1),其余弧流量不变,得一新可行流
第三步 继续给新可行流各顶点标号找增广链
(1)给起点v1标号(0, ∞)
(2)从v1可达v2、v3:(v1, v2)为正向饱和弧,v2不能标号;(v1, v3)为正向非饱和弧,v3标号(+v1,3)
(3)从v3可达v2、v5:(v3, v2)为反向零弧,v2不能标号;(v3, v5)为正向饱和弧,v5不标号
标号过程中断,找不到增广链,故当前可行流为最大流
第四步 确定最小割和最大流量
(1)最小割:将已标号的顶点v1、v3构成非空集V*={v1, v3},未标号的其它顶点v2、v4、v5、v6构成补集,形成最小割。 Smin={(v1,v2), (v3,v5)},其容量为3+2=5(2)最大流量Q(F*):根据最大流-最小割定理有最大流量Q(F*)=5。 最小割Smin所包含的弧(v1, v2)、(v3, v5)为网络关键弧,若要增大网络最大流,必须首先设法改善这些关键弧的容量配置状况,提高它们的容量。另一方面,如果最小割中弧的通过能力降低,则会使总流量减小。另外,在各弧容量一定的网络中,最大流的总流量是唯一的,但最大流F*却不一定是唯一的
最小费用最大流问题
把增广链上调整一个单位的流量时所发生的总的费用改变量称为增广链的费用
定理:若f是流量为v(f)的所有可行流中的费用最小者,而μ是关于f的所有增广链中费用最小的增广链,那么沿μ去调整f,得到的可行流f',就是流量为v(f')的所有可行流中的最小费用流
用“最短路法"求解
求解思路:把各条弧上单位流量的费用看成长度,用求最短路问题的方法确定一条自vs至vt的最短路,再将这条最短路作为增广链,用求解最大流问题的方法,将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定。如此多次迭代,最终得到最小费用最大流。值得注意的是,这里将遇到求解带负权的最短路问题。
赋权图法
最小费用增广链对应剩余网络的最短路
剩余网络又叫长度网络, 本教材叫做赋 权图
生成最小费用可行流的剩余网络
将饱和弧反向
将非饱和非零流弧加一反向弧
零流弧不变
所有正向弧的权为该弧的费用, 反向弧的 权为该弧费用的相反数
第一次剩余网络最短路
第一次调整网络流
第二次剩余网络最短路
第二次调整网络流
第三次剩余网络的最短路
第三次调整网络流
剩余网络已不存在最短路
已获最小费用最大流
若规定网络流为7, 则第二次调整量应为 2, 而不是3
最小费用与网络流的关系是凸的, 即随 着流的增加, 单位流的费用在增加
求解最小费用流的复合标号法
将求最短路的标号法和求最大流的标号 法相结合, 即在求增广链的标号后加上 一个距离标号, 成为一组三标号, 距离 标号应采用修正标号法。 并采用T标号 和P标号的记法
最短路问题、 最大流问题可以看作最小 费用流的特殊情况
最短路
从以上求解过程中还可以得到从起点v1到其他任意顶点的最短路及其路权
最短路的矩阵算法,最多经过k=[{lg(n-1)}/lg2]+1次迭代即可得到结果,n表示点的总数。比较网络中任意两点直接到达和经过一个中间点到达所比较出的最短路程;通过矩阵算法可得任意两点间的最短路线
整数规划
指派问题
设n 个人被分配去做n 件工作, 规定每个人只做一件工作, 每件工作只有一个人去做。 已知第i 个人去做第j 件工作的的效率( 时间或费用 ) 为C ij (i=1.2…n;j=1.2…n)并假设C ij ≥0 应指派哪个人去完成哪项任务, 使完成 n项任务的总效率最高( 或所需时间最少) , 这类问题称为指派问题或分派问题
某一个分配问题的效率矩阵, 其中a ij 表示 第i个人完成第j项工作需要的时间
引 入0—1变量 x ij, 并令x ij = 1(当 指派第 i人去完成第j项工作时) 或0( 当不指派第 i人去完成第j项工作时) . 这可以表示为一个0--1整数规划问题: Minz=15 x 11 +18 x 12 +21 x 13 +24 x 14 +19 x 21 +23 x 22 +22 x 23 +18 x 24 +26 x 31 +17 x 32 +16 x 33 +19 x 34 +19 x 41 +21 x 42 +23 x 43 +17 x 44 s. t. x 11 + x 12 + x 13 + x 14 = 1 (甲只能干一项工作) x 21 + x 22 + x 23 + x 24 = 1 (乙只能干一项工作) x 31 + x 32 + x 33 + x 34 = 1 (丙只能干一项工作) x 41 + x 42 + x 43 + x 44 = 1 (丁只能干一项工作) x 11 + x 21 + x 31 + x 41 = 1 ( A工作只能一人干) x 12 + x 22 + x 32 + x 42 = 1 ( B工作只能一人干) x 13 + x 23 + x 33 + x 43 = 1 ( C工作只能一人干) x 14 + x 24 + x 34 + x 44 = 1 ( D工作只能一人干) x ij 为0--1变量 , i, j = 1, 2, 3, 4
指派问题是0-1 规划的特例, 也是运输问题的特例, 当然可用 整数规划, 0-1 规划或运输问题的解法去求 解, 这就如同用 单纯型法求解运输问题一样是不合算 的。 利用 指派问题的特点可有更简便的解法, 这就是 匈牙利法, 即系数矩阵中独立 0 元素的最多 个数等于 能覆盖所有 0 元素的最少直线数
指派问题用匈牙利法计算, (1 ) 效益矩阵必须是n阶方阵 (2) 效益矩阵中每个元素C i j ≥0, 且是 常数(匈牙利法要求效率矩阵的每个元素都是非负的) (3) 会出现多个最优解的情况
对应(2)如果把消耗时间数据看成创造效益的数据, 那么应如何指派, 可使得总的效益最大? 解决办法: 转化成最小化问题, 找出最大元素, 用最大元素分别减去表中各元素求解 (将原系数矩阵的各个元素用其最大值去减)
对应(1)思考:仿产销不平衡的运输问题,对于人数与任务数不等的指派问题,如何转换为标准的指派问题 jie 加上虚拟行或列使其成方阵,虚拟行或列元素为0(需有一行或列为无穷大,不然可能划去全部元素,从而无法求解),得到方阵的解后即可对应得出非方阵的解,即有人没有工作或有工作没人去完成,因为它不是方阵
对应(3),因为选取的0元素的位置可能不同,因此得出的最优解可能不同
匈牙利法的基本原理
1.如果(cij)是指派问题的价值系数矩阵,则在该矩阵的任一行或任列的全部元素上同时加或减去一个常数,结果并不影响最优分配方案
2.如果在价值系数矩阵(Cij)n*n中,位于不同行不同列的零元素共有m个(1<=m<=n),则覆盖所有0元素所需的最少直线(水平线或竖直线)数恰好为m条
3.如果在价值系数矩阵中,位于不同行不同列的零元素的个数与价值系数矩阵的阶数 n 相同,则显然只要令对应于这些零元素位置的xij=1,其余的xij=0,则此解就是问题的最优解
具体求解步骤
第一步 变换价值系数矩阵,使各行各列中都出现0元素
1.将系数矩阵的每行都减去本行的最小元素
jie 如果行或列中有无穷大,即时间无限长或任务不可能通过该路径完成,加上或减去行或列最小元素后其值不变
2.将上述所得系数矩阵的每列都减去本列的最小元素
第二步 选取0元素
1.从0元素最少的行或0元素最少的列中括起(即选取)一个0(若0元素最少的列所含的0元素的个数比行中的0元素少,则从此列中选取0,否则从0元素最少的行中选0),并划去此0所在行和所在列上的其他0元素
jie 其实只要圈出需要的0元素就可以了,可以不划去其他的0元素
2.重复此步中的1.,直到所有的0元素或被括起来或被划去
经过此步后,若括起的0元素的个数等于矩阵的阶数,则矩阵中所有括起的0元素的位置即为最优指派位置,写出最优解,结束;否则转第三步。此例中括起的0元素只有三个,小于矩阵阶数4,故需转第三步
第三步 以最少数目的直线覆盖矩阵中所有0元素
1.对没有括号的行打
2.对打三角符号行上所有0元素对应的列打三角
3.对打三角列上有括起的0元素的,即在(0)对应的行上打三角
4.反复执行2.3.,直至标号行上再无新的0元素,标号列上无新的(0)为止
5.对没有打三角的行划横线,对所有打三角的列划竖线
第四步 进一步变换
1.在未划线的元素中找最小者,设为
2.对未被直线覆盖的各元素减去最小者
3.对两条直线交叉点覆盖的元素加上最小者
4.只有一条直线覆盖的元素保持不变
5.抹除所有标记,回到第二步,重新选取0元素
至此,括起的0元素的个数已经等于矩阵的阶数4,从而得到最优解,最优解以矩阵形式表示;若不满足,则转第一步的变换
分支定界法
分支定界法每次分支后都增加了一个约束条件,最终由增加的约束条件边界得出或者说是逐步逼近整数规划的最优解,且该整数解中必有一个解为增加的约束边界
割平面解法
割平面法的基本思想是不考虑整数要求,先求解对应的线性规划问题(松弛问题),如果没有得到满足整数要求的解,那么依次引进更多线性约束条件(几何意义上,称为“割平面”,其实是在“裁剪”问题的可行域),使问题的可行域逐步缩小,如此反复进行,直到得到整数最优解
3个方面的要求
(1)割平面切割有效,即每次一定真正割去可行域中的一部分
(2)在切割过程中,保证没有割去任何整数可行解
(3)最终一定会收敛,即能够恰好割出这样的可行域,使符合整数要求的最优解正好在顶点上
过程
数学模型称为问题A,把不考虑整数约束的线性规划问题称为问题B(问题A的松弛问题),先求解问题B,转化如下的标准形式
用单纯形法求解线性规划问题B,得到最终单纯形表 松弛问题的最优解不满足整数要求,进行迭代求解
第1次迭代
首先,利用求解松弛问题的最终单纯形表,构造割平面。从单纯形表中得到两个等式,将等式中所有系数均分解为整数部分和非负真分数部分; 代入式①、式②中,并将整数和整数系数部分移至左端,把小数和小数系数部分移至右端,得;让右端项小于等于0,得到; 任取其中之一,称为割平面方程,如取式④,整理得;其次,将得到的割平面方程作为新的约束条件加入计算,加到线性规划问题B中,得到问题B1。
继续求解问题B1,注意到问题B1相比问题B的变化,可以在求解B的最终单纯形表(见表7-3-1)的基础上进行迭代求解。将新约束条件添加进去,将式④化为;把作为新的基变量,得到表7-3-2。表7-3-2 求解问题B1的初始单纯形表; 这里所有检验数均非正,b存在负数,符合对偶单纯形法的条件,使用对偶单纯形法进行迭代,得到如表7-3-3所示的最终单纯形表。表7-3-3 求解问题B1的最终单纯形表; 得到问题B1的最优解为不满足整数要求,按照如上办法继续求解
第2次迭代
在表7-3-3中寻找一个割平面方程,如第一个等式
对系数进行分解,整数和整数系数部分放在左端,小数和小数系数部分放在右端,得
新的割平面方程为
将它作为新的约束条件,加到问题B1中,得到问题B2
将新的约束条件转化为等式后,反映到表7-3-3中,得到表7-3-4。表7-3-4 求解问题B2的初始单纯形表
继续用对偶单纯形法求解得到表7-3-5。表7-3-5 求解问题B2的最终单纯形表
得到问题B2的最优解为不满足整数要求,按照如上逻辑继续求解,选取新的割平面方程继续求解,会得到最优解为
求解步骤
第1步:求解松弛问题
不考虑整数约束,求相应松弛问题的最优解。若最优解恰为整数,则停止计算;若最优解不为整数,进入第2步
第2步:寻找割平面方程
(1)令xi为相应线性规划最优解中不符合整数条件的一个基变量
(2)将bi和aik都分解成整数部分N与非负真分数f之和
(3)令右侧小数和小数系数部分小于0,得到新的线性约束条件
第3步:迭代求解
把第2步中得到的割平面方程加入松弛问题中,使用单纯形法或对偶单纯形法求解。若解为满足整数条件的最优解,停止计算;否则返回第2步,重新寻找新的割平面方程,以此类推,直到得到整数最优解
0-1型整数规划和隐枚举法
可以通过设定过滤条件来减少检查量,方便地找到最优解。这个求解0-1型整数规划的办法称为隐枚举法
第1步:确定一个可行解并设定过滤条件
作为初始条件,可以先试探找出一个可行解,并将相应目标函数值设定为过滤条件
从本题容易看出是可行解,算出相应的目标函数值。此问题是极大化问题,当然希望最终的优化解大于3,故增加约束条件并称其为过滤条件
第2步:依次检查可行解并不断更新过滤条件
将过滤条件作为第一个约束条件,依次列出其他约束条件,将各解依次代入检查,看是否适合相应约束条件,如某个条件不合适,以下各条件就不必再检查
若遇到某可行解的值已超过条件右边的值,应该更新过滤条件,使右边始终为目前发现的最好目标值
可以使用一些技巧来改进这一过程,以加速迭代,最大可能减少计算量。这些技巧包括
(1)初始可行解不一定取作原点,可以从其他可行解开始,让初始目标函数值更优,提高过滤的门槛
(2)可以重新排列变量的顺序,使目标函数中各系数递增或者递减,有意识地先选取可能让目标函数得到最优解的点,从而减少计算量
目标规划
引入正负偏差变量d+,d-,其中,d-=低于所定目标的数量,d+=高于所定目标的数量 在任何解中,都应有d+d-=0,因为一个单一解不能在两个方向都偏离一个所定的目标 若想尽可能准确地实现目标,则正负偏差应同时引入目标函数中,其目标函数形式为minZ=d++d-,如果想避免低于某一目标,而接受超过目标,则可将d+从目标函数中删去,为minZ=d-(jie 有d-说明目标定得高,通常难以完成)
8x 1 +10x 2 +d 1- -d 1+ =56
可加班,加班时间要控制,低于,mind+ 既充分利用又尽可能不加班,mind++d-
解目标规划的单纯形法
目标规划的数学模型结构与线性规划的数学模 型结构形式上没有本质的区别, 所以可用单纯形法 求解。 但要考虑目标规划的数学模型一些特点
灵敏度分析
目标规划的灵敏度分析方法与线性规划相似, 只是除分析各项系数的变化外, 还有优先因子的变化问题
动态规划
无后效性(马尔可夫性) : 是指如果某阶段 状态给定后, 则在这个阶段以后过程的发展不 受这个阶段以前各段状态的影响; 构造动态规 划模型时, 要充分注意是否满足无后效性的要 求; 状态变量要满足无后效性的要求; 如果状 态变量不能满足无后效性的要求, 应适当改变 状态的定义或规定方法
在已知初始状态s 1 下, 求解动态规划模型 时采用逆序解法(逆向递归)
引例的求解, 就是把A看作始端, E为终端, 规定从A到E为过程的行进方向, 而寻优则是从E 到A逆过程进行, 所以是采用了逆序法
线性规划
单纯形法
“单纯形法”(Simplex Method或Simplex Algorithm)
第1步:找到一个初始解
注意3个新变量x3、x4、x5的系数列向量为单位向量,按照“主元消去法”的过程,首先考虑这3个变量的表达式,在表达式中直接取其他变量x1、x2为零,这3个变量取值就是右端项,得到一个初始解
第2步:建立单纯形表
其实,这一步计算,包括“检验数”的计算和上面“主元消去法”过程中的式实质上是一样的,各检验数实际上就是式中目标函数各变量的系数,称非基变量在目标函数中的系数为——检验数,σj ——为基可行解X的检验数
根据计算结果,选取一个检验数为正(很多时候选其中最大的)的变量作为换入变量
第3步:解的判别
如果发现所有检验数均小于等于0,那么迭代终止(说明目标函数无法再增加)。如发现某个未选入变量检验数大于0,说明当前解还不是最优解
存在一个检验数σ =0 则线性规划问题有无穷多最优解
无最优解是指线性规划问题存在可行解,但是 可行解的目标函数达不到最优值,即目标函数在可行 域内可以趋于无穷小或者无穷大 。 无最优解也称 为无有限最优解或无界解
第4步:解变换
根据检验数行的计算结果,这里选取一个检验数大的变量作为换入变量,进一步计算相应的θ值
第5步:旋转运算
这一步的任务是计算新变量组的取值,并将变换后得到的新解反映到一个新的单纯形表中
首先,在上一步单纯形表的系数矩阵部分确定一个主元素(换入变量对应的系数列和换出变量对应的系数行交叉处的系数称为“主元素”),方便起见,在单纯形表中用“[ ]”把这一元素圈出
其次,围绕主元素进行“消去法”计算,单纯形称之为旋转运算,使得在主元素所在的列中,主元素位置变为1,同列中的其他位置变为0。通过两种运算来达成这一目的:第1种运算是将某一行同时乘以某一非零数值,第2种运算是将某一行乘以某一数值后加到另一行上去。借助旋转运算就可以等价地把主元素所在的新变量的系数列变为单位列向量,同时不改变其他原有选入变量的系数列向量(仍为单位列向量)
最后,在XB列把新的变量写入,相应地把CB列价值系数更新,重新计算检验数
重复第3步至第5步,直到目标函数再也无法增加为止
满足以下3个条件的形式为线性规划数学模型的标准形式
(1)目标函数最大化
(2)约束条件等式化
(3)决策变量非负化
丹捷格给出的通用解法的基础是线性代数中求线性方程组的“主元消去法”
变换操作实际是线性方程组求解中的“主元消去”过程
上面的过程非常固定,可以利用表格进行简化计算,更直观,更简洁。而在一个统一规定的表格上遂行如上计算的方法就是求解线性规划的通用代数解法——单纯形法
初始单纯形表中基变量不一定为最后几个变量,而是看哪些变量系数为1及变量的位置
人工变量法
直接通过线性规划模型得到初始可行基,它只适用于约束不等式右端的常数项是非负数,而且约束不等式是"<="的情况。如果约束不等式是">="或者是约束方程式,则可用大M法和两阶段法寻求初始可行基
加入人工变量后的约束方程组与原约束方程 组是不等价的
加上人工变量以后线性规划的基本可行解不一定是 原线性规划的问题的基本可行解
只有当基本可行解中所有人工变量都为取零值的非基 变量时该基本可行解对原线性规划才有意义。因为此时 只需去掉基本可行解中的人工变量部分剩余部分即为原 线性规划的一个基本可行解而这正是我们引入人工变量 的主要目 的
大M法
无可行解
通过大M法求初始的基本可行解。 但是如果在大M法的最优单纯形表的基变量中仍含有人工变量那么该线性规划就不存在可行解
检验数小于等于0且人工变量不在基变量中,则存在可行解
人工变量的值不能取零说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。 此时线性规划问题的可行域为空集
基变量 X1、 X2 的检验数全部为负, 得到最优解为(0, 0,-350, -125, 600), 不是可行解。 因此, 用负的单位向量作基向量求得的基本解一般不满足非负条件, 不是可行解, 通过加上人工变量构造初始单位矩阵的方法, 可以克服这一问题。 当然, 如果不通过使用单纯型法表, 不从将单位矩阵作为初始基变量开始迭代, 而是用等式移项的方法, 也可能可以不加人工变量而求得最优解
目标函数为求极小值,化为极大值的目标函数加入的为-M;目标函数求极大值,目标函数中加入的为M。至于加入多少个人工变量,视约束条件的个数和基变量的个数决定,若差两个系数为1的基变量且约束等式为二个,则加入两个人工变量。
jie目标函数求最大值,选sigma最大的,其中2M大于M,看M前面的系数判断大小,再看theta,选theta最小的,最优解中表中x等于b,其余为0 注意M在目标函数的系数中,不在约束条件的系数中,所以不存在M^2的情况
两阶段法
用两个阶段的办法来处理人工变量,使得在计算过程中不出现大M
两阶段法引入人工变量的目的和原则与大M法相同,所不同的是处理人工变量的方法
两阶段法的步骤
1. 求解一个辅助线性规划。目标函数取所有人工变量之和并取极小化
2. 如果辅助线性规划存在一个基本可行解使目标函数的最小值等于零,则所有人工变量都已经“离 基” 。 表明原问题已经得了 一个初始的基本可行解,可转入第二阶段继续计算;否则说明原问题没有可行解,可停止计算
第1阶段:判断是否存在可行解
不考虑原问题是否存在可行解,给原线性规划问题加入松弛变量和人工变量将其标准化,构造仅含人工变量的目标函数并要求实现最小化。用单纯形法求解上述模型,若最终求解结果中目标函数值为0,这说明原问题存在可行解,转入第2阶段;否则原问题无可行解,停止计算
第2阶段:求解原问题的最优解
对第1阶段得到的最终单纯形表进行两个操作:一是去掉其中的人工变量,二是将目标函数行的系数换成原问题的目标函数系数,将修改后的单纯形表作为第2阶段计算的初始表,继续迭代求解,直到满足迭代终止条件
本问题为无穷多最优解,可以通过强行继续迭代得到另一个最优解
对偶问题
把一个问题化为它的对偶问题:min则y(约束条件的符号)不变(从约束条件出发的对偶问题的变量的符号不变),x反号
对偶问题的基本性质
定理4.1(对称性)对偶问题的对偶是原问题
定理4.2(弱对偶性)设X ̄是原问题的任意可行解,Y ̄是对偶问题的任意可行解,则必有Y ̄b>=CX ̄ 也就是说,无论哪种形式,虽然原问题目标函数求最大,对偶问题目标函数求最小,但原问题目标函数值却是对偶问题目标函数值的下界,对偶问题目标函数值是原问题目标函数值的上界
推论4.1 如果原问题和对偶问题中有一个为无界解,则另一个无可行解
推论4.2 如果原问题和对偶问题都有可行解,则它们都有最优解
jie 证明原问题无最优解:首先看到该问题存在可行解;而上述问题的对偶问题为:由第一约束条件可知对偶问题无可行解, 因而无最优解。 由此, 原问题也无最优解 故原问题有可行解时对偶问题可能无可行解,从而对偶问题无最优解,得到原问题也无最优解
定理4.3(最优性)设X^是原问题的可行解,Y^是原对偶问题的可行解。则X^和Y^分别是原问题和对偶问题的最优解的充要条件是CX^=Y^b
定理4.4(强对偶性,也称对偶定理)原问题和对偶问题中有一个问题有最优解,那么另一个问题也必然有最优解,且目标函数值相等
定理4.5(最优解对称性,也称单纯形乘子定理)如果原问题有最优解,最优基为B,则Y*=CB*B-1(CB乘以B的逆)就是对偶问题的一个最优解
推论4.3 在求解原问题的最终单纯形表中,检验数行对应对偶问题的最优解
对偶问题最优解对应于最终单纯形表的检验数行,等于初始基变量对应的目标函数系数减去相应变量的检验数
对偶问题最优解也就完全等于最终单纯形表中相应变量检验数的相反数
推论4.4 对偶问题最优解中各分量为相应资源限额发生变化时目标函数的相对变化率
推论4.5 原问题最优基的逆在最终单纯形表中初始基对应的位置
定理4.6(互补松弛性,也称互补松弛定理)设X*和Y*分别是线性规划原问题和对偶问题的可行解,则它们分别是相应问题最优解的充要条件是Y*(b-AX*)=0和(Y*A-C)X*=0同时成立
解释对偶问题的实际含义
在保证原工厂利益不降低的情况下,总的价格尽可能的低 租赁生产两种产品的原料加价不应低于自己生产所得的利润; 为了不亏本,各种加价不能为负值
对偶是什么: 对同一事物(或问题) , 从不同的角度(或立场)提出对立的两种不同的表述 例如:在平面内, 矩形的面积与其周长之间的关系, 有两种不同的表述方法 • (1) 周长一定, 面积最大的矩形是正方形。 • (2) 面积一定, 周长最短的矩形是正方形 这种表述有利于加深对事物的认识和理解
若第i 种资源的单位市场价格为m i , 当y i > m i 时,企业愿意购进这种资源, 单位纯利为y i - m i , 则有利可图; 如果y i < m i , 则企业有偿转让这种资源, 可获单位纯利m i - y i , 否则, 企业无利可图, 甚至亏损
确定既满足动物生长的营养需求, 又使费用最省的选用饲料的方案
对 偶 单 纯 形 法
对偶单纯形法是求解线性规划的另 一的基本方法。它是根据对偶原理和单纯形法的原理而设计出 来的,因此称为对偶单纯形法。 不要简单理解为是求解对偶问题的单纯形法。
转化成适合对偶解法的标准型,目标函数取极大,b值取负数,检验数取负数中的极大值,theta取极小值;b列全是非负,则得到最优解,最优解为b列值,最优函数值为-z;若在确定换入变量时a均为正,则无可行解
解的4种情况
对于一般线性规划问题,求解结果可能出现以下几种情况
(1)唯一的最优解
(2)无穷多最优解(多重解)
(3)无界解,指线性规划问题的目标函数可以趋向无穷大(求最大化)或者趋向无穷小(求最小化)的情况
(4)无可行解
从图解法中可以直观地看到,当线性规划问题的可行域非空时,它是有界或无界凸多边形;若线性规划问题存在最优解,它一定在可行域的某个顶点得到;若在两个顶点同时得到最优解,则它们连线上的任意一点都是最优解,即有无穷最优解