1、第 1 页 共 20 页第一 部分 线性规划问题的求解重要算法：图解法、单纯形迭代、大 M 法单纯形迭代、对偶问题、表上作业法（找初始可行解：西北角法，最小元素法；最优性检验：闭回路法，位势法；） 、目标规划：图解法、整数规划：分支定界法（次重点） ，匈牙利法（重点） 、第二部分 动态规划问题的求解重要算法：图上标号法第三 部分 网络分析问题的求解重要算法：破圈法、TP 标号法、寻求网络最大流的标号法第一部分 线性规划问题的求解一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。图解法：图解法采用直角坐
2、标求解：x 1横轴；x 2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线） ，确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例 1：某厂生产甲、乙两种产品，这两种产品均需在 A、B、C 三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：A B C 利润（万元）甲乙3 5 99 5 37030有效总工时 540 450 72
3、0 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯 形法”或化“对 偶问题”用大 M 法求解）解：设 x1、x 2 为生产甲、乙产品的数量。max z = 70x1+30x2s.t. 0723945502112xx，设备消耗产品、第 2 页 共 20 页可行解域为 oabcd0，最优解为 b 点。由方程组解出 x1=75，x 2=15720394551xX *= =（75，15） T21xmax z =Z *= 7075+3015=5700例 2：用图解法求解max z = 6x1+4x2s.t. 07802121xx，可行解域为 oabcd0，最优解为
4、 b 点。由方程组、第 3 页 共 20 页解出 x1=2，x 2=6810212xX *= =（2，6） T1xmax z = 62+46=36例 3：用图解法求解min z =3x 1+x2s.t. 08215341121xx，解：可行解域为 bcdefb，最优解为 b 点。由方程组 解出 x1=4，x 2=125241x54X *= =（4， ） T2min z =34+ =1151、第 4 页 共 20 页二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入 3；3、根据 L 规则确定改
5、进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入 3，直至最优解。具体做法（可化归标准型的情况）：设已知max z = c1x1+ c2x2+ cnxns.t. njxbxaaxbaaj mmn， .210.21 22212 11对第 i 个方程加入松弛变量 xn+i，i =1，2，m ，得到 njx bxxaabxaaj mnmmnn， .210.21 22212 11列表计算，格式、算法如下：c1 c2 cn+mCB XB b x1 x2 xn+m Lcn+1 xn+1 b1 a11 a12 a1 n+mc n+2 xn
6、+2 b2 a21 a22 a2 n+m. cn+m xn+m bn am1 am2 am n+mz1 z2 zn+m1 2 n+m注： zj =cn+1 a1j+ cn+2 a2j + cn+m amj= ， （j=1 ，2，n+m）miijnac1j =cjzj ,当 j 0 时，当前解最优。注： 由 max j确定所对应的行的变量为“入基变量”；第 5 页 共 20 页由 L= 确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主0minikab元素变为 1，此列其余元素变为 0。例 1：用单纯形法求解 （本题即是本资料 P2“图 解 法 ”例 1 的单纯形解法 ；
7、也可化 “对偶 问 题 ”求解）max z =70x1+30x2s.t. 0723945502112xx，解：加入松弛变量 x3，x 4，x 5，得到等效的标准模型：max z =70x1+30x2+0 x3+0 x4+0 x5s.t. 5,.21,072039514231jxxj列表计算如下：70 30 0 0 0CB XB bx1 x2 x3 x4 x5 L0 x3 540 3 9 1 0 0 540/3 =1800 x4 450 5 5 0 1 0 450/5 =900 x5 720 （9） 3 0 0 1 720/9 =800 0 0 0 070 30 0 0 00 x3 300 0
8、8 1 0 - 1/3 300/8 =37.50 x4 50 0 （10/3） 0 1 - 5/9 50/10/3 =1570 x1 80 1 1/3 0 0 1/9 80/1/3 =24070 70/3 0 0 70/90 20/3 0 0 70/90 x3 180 0 0 1 12/5 130 x2 15 0 1 0 3/10 - 1/670 x1 75 1 0 0 - 1/10 1/670 30 0 2 20/357000 0 0 -2 20/3X *=（ 75，15 ，180，0，0） Tmax z =7075+3015=5700第 6 页 共 20 页例 2：用单纯形法求解max z
9、 =7x1+12x2s.t. 031354609221xx，解：加入松弛变量 x3，x 4，x 5，得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t. 5,.21,0303546914231jxxj列表计算如下：7 12 0 0 0CB XB bx1 x2 x3 x4 x5 L0 x3 360 9 4 1 0 0 360/4 =900 x4 200 4 5 0 1 0 200/5 =400 x5 300 3 （10） 0 0 1 300/10 =300 0 0 0 07 12 0 0 00 x3 240 78/10 0 1 0 - 2/5 240/78/1
10、0 =2400/780 x4 50 （5/2） 0 0 1 - 1/2 50/5/2 =2012 x2 30 3/10 1 0 0 1/10 30/3/10 =10018/5 12 0 0 6/517/5 0 0 0 6/50 x3 84 0 0 1 78/25 29/257 x1 20 1 0 0 2/5 - 1/512 x2 24 0 1 0 3/25 4/287 12 0 34/25 11/354280 0 0 34/25 11/35X *=（ 20，24 ，84，0，0） Tmax z =720+1224=428第 7 页 共 20 页三、非标准型线性规划问题的解法：1、一般地，对于约
11、束条件组：若为“” ，则加松弛变量，使方程成为“” ；若为“” ，则减松弛变量，使方程成为“” 。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：由目标函数 min z= 变成等价的目标函数 max（z）=njjxc1 njjxc1)(令z=z /，min z=max z /2、等式约束大 M 法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为M，M 是很大的正数，从原理上理解又称为“惩罚系数” 。 （课本 P29）类型一 ：目标函数仍为 max z，约束条件组与。例 1：max z =3x 1+5x2s.t.
12、 01823411xx，解：加入松弛变量 x3，x 4，得到等效的标准模型：max z =3x1+5x2s.t. 4,321,08314231jxj其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量 x5，得到： max z =3x1+5x2Mx 5s.t. 5,.21,08321431jxxj第 8 页 共 20 页单纯形表求解过程如下：3 5 0 0 MCB XB bx1 x2 x3 x4 x5 L0 x3 4 （1） 0 1 0 0 4/1 =40 x4 12 0 2 0 1 0 M x5 18 3 2 0 0 1 18/3 =63M 2M 0 0 M3M3 52M 0 0
13、 03 x1 4 1 0 1 0 0 0 x4 12 0 2 0 1 0 12/2 =6M x5 6 0 （2） 3 0 1 6/2 =33 2M 33M 0 M0 5 33M 0 03 x1 4 1 0 1 0 0 4/1 =40 x4 6 0 0 （3） 1 1 6/3 =25 x2 3 0 1 3/2 0 1/2 3/(2/3) = 9/23 5 9/2 0 5/20 0 9/2 0 M5/2x1 2 1 0 0 1/3 1/3x3 2 0 0 1 1/3 1/3305x2 6 0 1 0 1/2 03 5 0 3/2 1360 0 0 3/2 M1X *=（ 2，6， 2，0） Tma
14、x z =32+56=36类型二 ：目标函数 min z，约束条件组与。例 2：用单纯形法求解min z =4x1+3x2s.t. 03642121x，第 9 页 共 20 页解：减去松弛变量 x3，x 4，并化为等效的标准模型：max z/ =4x 1 3x2s.t. 4,321,0362132jxxj增加人工变量 x5、x 6，得到：max z/ =4x 1 3x2Mx 5Mx 6s.t 6,.21,012342641 532jxxj单纯形表求解过程如下：4 0 0 M MCB XB bx1 x2 x3 x4 x5 x6LM x5 16 2 （4） 1 0 1 0 16/4=4M x6 1
15、2 3 2 0 1 0 1 12/2=65M 6 M M M M M5M 4 6M3 M M 0 03 x2 4 1/2 1 1/4 0 1/4 0 4/1/2=8M x6 4 （2） 0 1/2 1 1/2 1 4/2=22M3/2 3 3/4M/2 M M/2 3/4 M2M5/2 0 M/23/4 M 3/43M/2 03 x2 3 0 1 3/8 1/4 3/8 1/44 x1 2 1 0 1/4 1/2 1/4 1/24 3 1/8 5/4 1/8 5/4170 0 1/8 5/4 M 1/8 M5/4X *=（ 2，3， 0，0） Tmin z =max z / =（17）=17四
16、、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例 （与本资料 P2 例 1 “图 解 法 ”、 P7 例 1 “单纯 形 法 ”同） ：某工厂生产甲、乙两种产品，这些产品均需在A、B、C 三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：第 10 页 共 20 页A B C 利润（万元）甲乙3 5 99 5 37030有效总工时 540 450 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？解：原
17、问题设 x1、x 2 为生产甲、乙产品的数量。max z = 70x1+30x2s.t. 0723945502112xx，将这个原问题化为它的对偶问题设 y1、y 2、y 2 分别为设备 A、 B、C 单位工时数的加工费。min w = 540y1+450y2+720y3s.t. 3210059793132， iyyi用大 M 法，先化为等效的标准模型：max w/ =540y 1450y 2720y 3s.t. 5,.21,00359793142jyyj增加人工变量 y6、y 7，得到：max z/ =540y 1450y 2720y 3My 6My 7s.t 5,.21,0305993731 642jy yyj设备消耗产品
