第一章线性规划 1．1将下述线性规划问题化成标准形式 1)min z＝－3x1＋4x2－2x3＋5 x4 －x2＋2x3－x4＝－2 4x st. x1＋x2－x3＋2 x4 ≤14 －2x1＋3x2＋x3－x4 ≥ 2 x1，x2，x3≥0，x4无约束 2)min z ＝2x1－2x2＋3x3 ＋x2＋x3＝4 －x st. －2x1＋x2－x3≤6 x1≤0 ，x2≥0，x3无约束 1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 1)min z＝2x1＋3x2 4x1＋6x2≥6 st2x1＋2x2≥4 x1，x2≥0 2)max z＝3x1＋2x2 2x1＋x2≤2 st3x1＋4x2≥12 x1，x2≥0 3)max z＝3x1＋5x2 6x1＋10x2≤120 st5≤x1≤10 3≤x2≤8 4)max z＝5x1＋6x2 2x1－x2≥2 st－2x1＋3x2≤2 x1，x2≥0 1．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解 （1）min z＝5x1－2x2＋3x3＋2x4 x1＋2x2＋3x3＋4x4＝7 st2x1＋2x2＋x3 ＋2x4＝3 x1，x2，x3，x4≥0
1．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。 1) maxz ＝10x 1＋5x 2 3x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥0 2) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥0 1．5 分别用大M 法与两阶段法求解下列LP 问题。 1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥0 2) max z ＝4x 1＋5x 2＋ x 3 . 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4 x 1＋ x 2－ x 3＝5 3) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥0 123123 123123123 4)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤??-++≤?? ++ ≥??≥? 1．6
工程优化设计中单纯形法的基本原理 张云龙 （大连海洋大学土木工程学院辽宁大连116023) 摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。 关键词：线性规划图解法单纯形法大M法 THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN ZHANG Y un-long (Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023) Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method. Key W ords: Linear programming；Graphic method；Simplex Method; Big M Method 1引言 在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。 虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误！未找到引用源。。 因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。 2线性规划问题 2.1数学模型 线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？ 表1-1 工时及利润简表
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
单纯形法求解线性规划的思路及重要参数 的推导 在求解线性规划问题的算法中，单纯形法是一种成熟、简便、有效的算法，在目前应用最为广泛。因此，我们组通过查阅资料以及小组讨论的形式，分工合作，共同探讨出单纯形法求解线性规划的思路。 一般线性规划问题有时具有线性方程组的变量数大于方程个数 的情况, 这时就使得方程有不定的解。这时就可以使用单纯形法来求解，从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步 选择的单纯形。在这其中每一个单纯形所对应的解其实都相当于n维空间图形中的一个顶点，我们就是要一个顶点，一个顶点的找到使目标函数值更好的顶点, 直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。 具体的求解步骤来说有6步：1：建立基本可行解。2：计算变量的检验数。3：判断是否最优。4：若不是最优解，则换基。5：计算新的基本可行解。6：迭代计算直到求的最优解或者可判断无最优解为止。 接下来，我们通过具体的事例来详细介绍具体的求解步骤，并列出重要参数以及定理的推导过程。 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品, 已知生产单位产品所需的设备台时及A、B 两种原材料的消耗, 如下表所示。
该工厂每生产一件产品Ⅰ可获利2 元, 每生产一件产品Ⅱ可获利3元, 问应如何安排计划使该工厂获利最多? 解：根据题意建立其标准型： max z = 2x1 + 3x2 + 0x3 + 0x4 + 0x5 (1) x1 +2x2 +x3 = 8 4x1 + x4 = 16 (2) 4x2 +x5 = 12 x j ≥0 , j = 1 , 2 , ? , 5 一、建立基本可行解 在标准型中x3 , x4 , x5为转化为标准型时加入的松弛变量，从(2)式中可以看到x3, x4 , x5的系数列向量 1 0 0 P3 = 0 , P4 = 1 , P5 = 0 0 0 1 而这些列向量就可以看做一个初始可行基 1 0 0 B = ( P3 , P4 , P5 ) = 0 1 0 0 0 1
科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6
大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z
%%%%%%%%%%考虑外部性%%%%%%%%% K=[0.238982596 0.287307802 0.316082138 0.41731 0.44684 0.554375 0.7433476 -0.5]; Ae=[]; be=[]; Au=[-4312.03 -4428.81 -4762.01 -3621 -1742 -1125 -7042 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 16.99234332 15.49032101 16.29521726 0 0 0 0 0 28.69966647 24.77171169 25.46127697 0 0 0 0 0 0.374634341 0.243236446 0.217269563 0 0 0 0 0 3.709548964 3.549331817 3.764874154 0 0 0 0 0 0.519208086 0.439245837 0.453720507 -0.687558374 -0.330772352 -0.213615899 -1.337140588 0 0.800693399 0.626156548 0.637213949 -0.754544082 -0.362998009 -0.234427532 -1.467412158 0 1.389212223 0.956314404 0.910849795 -1.243454189 -0.598204142 -0.386325867 -2.418228224 0 0.02072254 0.007129367 0.003239074 -0.01405806 -0.006763088 -0.004367666 -0.027339646 0 1.481346246 1.260784084 1.304148318 -1.871119181 -0.900162832 -0.581333631 -3.638890162 0 -4070.125117 -4222.427454 -4572.482002 -3578.6343 -1688.3464 -1097.6625 -6592.7204 0 -0.87848773 -0.8804649 -0.87608648 -0.9171424 -0.9362472 -0.95345404 -0.9357319 0]; bu=[0;6.76;2.53;5022.16;300;250;40;36.351;0;0;0;0;0;-59200;-12.3074]; B1=[0;0;0;0;0;0;0;0]; X=linprog(K,Au,bu,Ae,be,B1); X %%%%%%%%%%%%%%%%%%%% %%%%%%不考虑外部性%%%%%%%%%%% K=[0.232622352 0.281860365 0.310653447 0.574625 0.46229 0.56 0.7433476 -0.5]; Ae=[]; be=[]; Au=[-4312.03 -4428.81 -4762.01 -3621 -1742 -1125 -7042 1 0 0 0 1 0 0 0 0
单纯形法 需要解决的问题： 如何确定初始基本可行解； 如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降； 如何判断一个基本可行解是否为最优解。 min f(X)=-60x1-120x2 s.t. 9x1+4x2+x3=360 3x1+10x2+x4=300 4x1+5x2+x5=200 x i≥0 (i=1,2,3,4,5) (1) 初始基本可行解的求法。当用添加松弛变量的方法把不等式约 束换成等式约束时，我们往往会发现这些松弛变量就可以作为 初始基本可行解中的一部分基本变量。 例如：x1-x2+x3≤5 x1+2x2+x3≤10 x i≥0 引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式 x1-x2+x3+x4=5 x1+2x2+x3+x5=10 x i≥0 (i=1,2,3,4,5) 令x1=x2=x3=0，则可立即得到一组基本可行解 x1=x2=x3=0，x4=5，x5=10 同理在该实例中，从约束方程式的系数矩阵 中可以看出其中有个标准基，即 与B对应的变量x3，x4，x5为基本变量，所以可将约束方程写成 X3=360-9x1-4x2 x4=300-3x1-10x2 x5=200-4x1-5x2 若令非基变量x1=x2=0，则可得到一个初始基本可行解X0 X0=[0,0,360,300,200] T 判别初始基本可行解是否是最优解。此时可将上式代入到目标函数中，得：
F(X)=-60x1-120x2 对应的函数值为f(X0)=0。 由于上式中x1,x2系数为负，因而f(X0)=0不是最小值。因此所得的解不是最优解。 (2) 从初始基本可行解X0迭代出另一个基本可行解X1，并判断X1是否 为最优解。从一个基本可行解迭代出另一个基本可行解可分为 两步进行： 第一步，从原来的非基变量中选一个（称为进基变量）使其成为基本变量； 第二步，从原来的基本变量中选一个（称为离基变量）使其成为新的非基变量。 选择进基和离基变量的原则是使目标函数值得到最快的下降和使所有的基本变量值必须是非负。 在目标函数表达式中，非基变量x1,x2的系数是负值可知，若x1,x2不取零而取正值时，则目标函数还可以下降。因此，只要目标函数式中还存在负系数的非基变量，就表明目标函数还有下降的可能。也就还需要将非基本变量和基本变量进行对换。一般选择目标函数式中系数最小的（即绝对值最大的负系数）非基变量x2换入基本变量，然后从x3，x4，x5中换出一个基本变量，并保证经变换后得到的基本变量均为非负。 当x1=0，约束表达式为： X3=360-4x2≥0 x4=300-10x2≥0 x5=200-5x2≥0 从上式中可以看出，只有选择 x2=min{}=30 才能使上式成立。由于当x2=30时，原基本变量x4=0，其余x3和x5都满足非负要求。因此，可以将x2，x4互换。于是原约束方程式可得到：4x2+x3=360-9x1 10x2 =300-3x1-x4 5x2+x5=200-4x1 用消元法将上式中x2的系数列向量变[4,10,5]T换成标准基向量[0,1,0]T。其具体运算过程如下： -*4/10 : x3=240-78x1/10+4 x4/10 /10 : x2 =30-3x1/10-x4/10
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14
机械优化设计 课程作业 题目：单纯形程序算法学院：机电工程学院专业：机械工程 姓名：郑璐颖 学号：2015020287 指导老师：王玉林
2016年 4 月 24 日 基于MATLAB 的单纯形算法实现 一.算法简述 为求解下面线性规划问题： ?? ?≥≥≤0 ,0..min b x b Ax t s cx 其中初始可行基为松弛变量对应的列组成. 对于一般标准线性规划问题: ?? ?≥≥=0 ,0..min b x b Ax t s cx １．求解上述一般标准线性规划的单纯形算法步骤如下： 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤： (1).解 B Bx b =,求得 1 B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w, B wB C =,得到1B w C B -=,对于非基变量，计算判别数1i i i B i i z c c B p c σ-=-=-,可直接计算 σ =1B A c c B --令 max{}k i R σσ∈=,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一步 (3).解 k k By p =,得到 1k k y B p -=；若0k y ≤,即k y 的每个分量均非正数， 则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量, ,r k B x p k 为进基变量,用p 替换得到新的基矩阵B,还回步骤(1)
1、线性规划问题及其表示 线性规划问题可表示为如下形式： 变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得极值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况下可能不存在最优解。 通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集； (2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界。 例：
这个问题的解为(x1,x2,x3,x4) = (0,3.5,4.5,1)；最优值为16。 2、线性规划基本定理 约束条件(8.2)-(8.5)中n个约束以等号满足的可行解称为线性规划问题的基本可行解。 若n>m，则基本可行解中至少有n-m个分量为0，也就是说，基本可行解中最多有m个分量非零。 线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。 上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在(8.2) -(8.5)式的m+n个约束条件中，确定最优解应满足其中哪n个约束条件的问题。 由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，直到找到最优解。 Dantzig于1948年提出了线性规划问题的单纯形算法。 单纯形算法的特点是： （1）只对约束条件的若干组合进行测试，测试的每一步都使目标函
数的值增加； （2）一般经过不大于m或n次迭代就可求得最优解。 3、约束标准型线性规划问题的单纯形算法 当线性规划问题中没有不等式约束(8.2)和(8.4)式，而只有等式约束(8.3)和变量非负约束(8.5)时，称该线性规划问题具有标准形式。 先考察一类更特殊的标准形式线性规划问题。这一类线性规划问题中，每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。 在每一约束方程中选择一个这样的变量，并以它作为变量求解该约 束方程。这样选出来的变量称为左端变量或基本变量，其总数为m个。剩 下的n-m个变量称为右端变量或非基本变量。 这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题。 虽然约束标准型线性规划问题非常特殊，但是对于理解线性规划问 题的单纯形算法是非常重要的。 任意一个线性规划问题可以转换为约束标准型线性规划问题。 例：
网络流专题研究 福州一中肖汉骏 预备知识(参见Amber论文) 网络和流 残留网络和增广路径 最大流和最小割 主要算法 最大流 增广路方法Ford-Fulkerson method 一般增广路算法Labeling algorithm 连续增广路算法 由陈启峰提出，竞赛中相当实用，近于O(m) 容量缩放增广路算法Capacity scaling algorithm 最短增广路算法Edmonds-Karp algorithm 连续最短增广路算法Successive shortest augmenting path algorithm (Dinic augorithm) 预流推进方法Preflow-push method 一般预流推进算法Generic preflow-push algorithm 先进先出预流推进算法FIFO preflow-push algorithm 最高标号预流推进算法Highest-label preflow-push algorithm (Relabel-to-Front algorithm) 最小费用流 最小费用路方法 一般最小费用路算法(SPFA找增广路，复杂度近于O(mf)，竞赛中实用) 注意：初始流的费用必须保证是在所有同流量流中最小的。
原始-对偶算法 消圈方法 一般消圈算法 网络单纯形法 常见变形 多源多汇问题 可通过增添超级源和超级汇解决。 点有容量或费用 可以尝试拆一个点为一入点一出点，将点的限制转移到入点到出点的边上。 重边、无向边和自环的处理 对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。 而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。 而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连，得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。 给定流值的情况 可以增设一个源，向原来的源连一条容量为给定流值的边。 或者在每次增广的时候，直接将源的可改进量设为到给定流值的差。 或在回溯增广的时候，将路径的增广量同到给定流值的差比较后取小。 有上下界的流问题 注意到下界必须被满足，可以将所有必要弧抽取，经过新建的源和汇。但这时必须为原来的汇到源增添一条容量为无穷大的边，使之成为满足流量平衡条件的普通节点(注意，汇到源的流量实际上就是原网络的流值)。再运行最大流算法得到一个可行流。 另一方面，可以先满足下界，此时有一些点不满足流量平衡条件。而这可以用多源多汇问题解决。 若求的是最大流，则可以在可行流的基础上进行增广。 如果求的是最小可行流，则可以通过交换源汇，去除新增的点和边后运行最大流，将多余的流抵消。也可以通过二分汇到源的容量，运行可行流。 最大费用流 将费用取负，运行最小费用流算法。 或将SPFA的大于号反向。 可行最小费用流 从T向S连边，在这基础上找负权圈增广。
运筹学习题答案 第一章（39页） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max 12z x x =+ 51x +102x ≤50 1x +2x ≥1 2x ≤4 1x ，2x ≥0 （2）min z=1x +1.52x 1x +32x ≥3 1x +2x ≥2 1x ，2x ≥0 （3）max z=21x +22x 1x -2x ≥-1 -0.51x +2x ≤2 1x ，2x ≥0 （4）max z=1x +2x 1x -2x ≥0 31x -2x ≤-3 1x ，2x ≥0 解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
（1）min z=-31x +42x -23x +54x 41x -2x +23x -4x =-2 1x +2x +33x -4x ≤14 -21x +32x -3x +24x ≥2 1x ，2x ，3x ≥0，4x 无约束 （2）max k k z s p = 11 n m k ik ik i k z a x ===∑∑ 1 1(1,...,)m ik k x i n =-=-=∑ ik x ≥0 (i=1…n; k=1,…,m) （1）解：设z=-z ',4x =5x -6x , 5x ,6x ≥0 标准型： Max z '=31x -42x +23x -5(5x -6x )+07x +08x -M 9x -M 10x s. t . -41x +2x -23x +5x -6x +10x =2 1x +2x +33x -5x +6x +7x =14 -21x +32x -3x +25x -26x -8x +9x =2 1x ,2x ,3x ,5x ,6x ,7x ,8x ,9x ,10x ≥0
单纯形法原理及步骤 单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。 概述： 根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止
目标函数的值无限增大（或向负的方向无限增大）。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。 求解步骤： （1）确定初始基可行解 ①从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量； ②对约束条件全为“<=”连接的LP，化为标准形，左端添加松弛变量后即形成一个单位子矩阵； ③约束条件中含有“<=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用
单纯形算法的一般原理 单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。 考虑到如下线性规划问题： 其中Ａ一个m ×n 矩阵，且秩为m ，ｂ总可以被调整为一个m 维非负列向量，Ｃ为n 维行向量，Ｘ为n 维列向量。 根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。 这个重要的定理启发了Dantzig 的单纯形法， 即将寻优的目标集中在D 的各个顶点上。 Dantzig 的单纯形法把寻优的目标集中在所有基本可行解 （即可行域顶点）中。 其基本思路是从一个初始的基本可行解出发，寻找一条达到 最优基本可行解的最佳途径。 单纯形法的一般步骤如下： （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（2）。 求解思想如下图所示： maxZ=CX AX=b X 0??≥?
确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m 个系数列向量恰好构成一个可行基，即 Ａ=（ＢＮ），其中 Ｂ=（Ｐ1，Ｐ2，…Ｐm ）为基变量x1，x2，…xm 的系数列向量 构成的可行基， Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn 的 系数列向量构成的矩阵。 那么约束方程AX=b 就可表示为： 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 若令所有非基变量 ，则基变量 由此可得初始的基本可行解 B B N N X AX=(BN)=BX +NX =b X ?? ???-1-1B N X =B b-B NX N X =0-1B X =B b 1B b X=0-?? ???-1-1-1B N B N N B AX=b BX +NX =b X =B b-B NX X =0,X =B b →→→