《运筹学》复习参考资料.pdf

《《运筹学》复习参考资料.pdf》由会员分享，可在线阅读，更多相关《《运筹学》复习参考资料.pdf（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 第一部分 线性规划问题的求解 重要算法：图解法、单纯形迭代、大 M 法单纯形迭代、对偶问题、表上作业法（找初始可行解：西北角法，最小元素法；最优性检验：闭回路法，位势法；）、目标规划：图解法、整数规划：分支定界法（次重点），匈牙利法（重点）、第二部分 动态规划问题的求解 重要算法：图上标号法 第三部分 网络分析问题的求解 重要算法：破圈法、TP 标号法、寻求网络最大流的标号法 第一部分 线性规划问题的求解 一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。图解法：图解法采用直角坐标求解：x1横轴；x

2、2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例 1：某厂生产甲、乙两种产品，这两种产品均需在 A、B、C 三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：A B C 利润（万元）甲 乙 3 5 9 9 5 3 70 30 有效总工时 540 450 720 问：该厂应

3、如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大 M 法求解）解：设 x1、x2为生产甲、乙产品的数量。max z=70 x1+30 x2 s.t.设 备 消 耗 产 品 072039450555409321212121xxxxxxxx，可行解域为 oabcd0，最优解为 b 点。由方程组 72039450552121xxxx 解出 x1=75，x2=15 X*=21xx=（75，15）T max z=Z*=7075+3015=5700 例 2：用图解法求解 max z=6x1+4x2 s.t.、0781022122121xxxxxxx，可

4、行解域为 oabcd0，最优解为 b 点。由方程组 81022121xxxx 解出 x1=2，x2=6 X*=21xx=（2，6）T max z=62+46=36 例 3：用图解法求解 min z=3x1+x2 s.t.、08212523421212121xxxxxxxx，解：可行解域为 bcdefb，最优解为 b 点。由方程组12524211xxx 解出 x1=4，x2=54 X*=21xx=（4，54）T min z=34+54=1151 、二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转

5、入 3；3、根据L规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入 3，直至最优解。具体做法（可化归标准型的情况）：设已知 max z=c1x1+c2x2+cnxn s.t.njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn，.210.22112222212111212111 对第 i 个方程加入松弛变量 xn+i，i=1，2，m，得到 njxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn，.210.2211222222121111212111 列表计算，格式、算

6、法如下：CB XB b c1 c2 cn+m L x1 x2 xn+m cn+1 xn+1 b1 a11 a12 a1 n+m c n+2 xn+2 b2 a21 a22 a2 n+m .cn+m xn+m bn am1 am2 am n+m z1 z2 zn+m 1 2 n+m 注：zj=cn+1 a1j+cn+2 a2j+cn+m amj=miijinac1，（j=1，2，n+m）j=cjzj,当j 0 时，当前解最优。注：由 maxj确定所对应的行的变量为“入基变量”；由L=0minikikiiaab确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为 1，此

7、列其余元素变为 0。例 1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）max z=70 x1+30 x2 s.t.072039450555409321212121xxxxxxxx，解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z=70 x1+30 x2+0 x3+0 x4+0 x5 s.t.5,.,2,1,0720394505554093521421321jxxxxxxxxxxj 列表计算如下：CB XB b 70 30 0 0 0 L x1 x2 x3 x4 x5 0 x3 540 3 9 1 0 0 540/3 =180 0 x

8、4 450 5 5 0 1 0 450/5 =90 0 x5 720（9）3 0 0 1 720/9 =80 0 0 0 0 0 70 30 0 0 0 0 x3 300 0 8 1 0-1/3 300/8 =37.5 0 x4 50 0（10/3）0 1 -5/9 50/10/3 =15 70 x1 80 1 1/3 0 0 1/9 80/1/3 =240 70 70/3 0 0 70/9 0 20/3 0 0 70/9 0 x3 180 0 0 1 12/5 1 30 x2 15 0 1 0 3/10-1/6 70 x1 75 1 0 0-1/10 1/6 5700 70 30 0 2 2

9、0/3 0 0 0-2 20/3 X*=（75，15，180，0，0）T max z=7075+3015=5700 例 2：用单纯形法求解 max z=7x1+12x2 s.t.0300103200543604921212121xxxxxxxx，解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z=7x1+12x2+0 x3+0 x4+0 x5 s.t.5,.,2,1,03001032005436049521421321jxxxxxxxxxxj 列表计算如下：CB XB b 7 12 0 0 0 L x1 x2 x3 x4 x5 0 x3 360 9 4 1 0 0 360/4=

10、90 0 x4 200 4 5 0 1 0 200/5=40 0 x5 300 3（10）0 0 1 300/10=30 0 0 0 0 0 7 12 0 0 0 0 x3 240 78/10 0 1 0-2/5 240/78/10=2400/78 0 x4 50（5/2）0 0 1-1/2 50/5/2=20 12 x2 30 3/10 1 0 0 1/10 30/3/10=100 18/5 12 0 0 6/5 17/5 0 0 0 6/5 0 x3 84 0 0 1 78/25 29/25 7 x1 20 1 0 0 2/5-1/5 12 x2 24 0 1 0 3/25 4/28 42

11、8 7 12 0 34/25 11/35 0 0 0 34/25 11/35 X*=（20，24，84，0，0）T max z=720+1224=428 三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“”，则加松弛变量，使方程成为“”；若为“”，则减松弛变量，使方程成为“”。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：由目标函数 min z=njjjxc1变成等价的目标函数 max（z）=njjjxc1)(令z=z/，min z=max z/2、等式约束大 M 法：通过加人工变量的方法，构造人造基，从而产生初始可行基

12、。人工变量的价值系数为M，M 是很大的正数，从原理上理解又称为“惩罚系数”。（课本 P29）类型一：目标函数仍为 max z，约束条件组与。例 1：max z=3x1+5x2 s.t.018231224212121xxxxxx，解：加入松弛变量 x3，x4，得到等效的标准模型：max z=3x1+5x2 s.t.4,3,2,1,018231224214231jxxxxxxxj 其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量 x5，得到：max z=3x1+5x2Mx5 s.t.5,.,2,1,0182312245214231jxxxxxxxxj 单纯形表求解过程如下：CB X

13、B b 3 5 0 0 M L x1 x2 x3 x4 x5 0 x3 4（1）0 1 0 0 4/1=4 0 x4 12 0 2 0 1 0 M x5 18 3 2 0 0 1 18/3=6 3M 2M 0 0 M 3M3 52M 0 0 0 3 x1 4 1 0 1 0 0 0 x4 12 0 2 0 1 0 12/2=6 M x5 6 0（2）3 0 1 6/2=3 3 2M 33M 0 M 0 5 33M 0 0 3 x1 4 1 0 1 0 0 4/1=4 0 x4 6 0 0（3）1 1 6/3=2 5 x2 3 0 1 3/2 0 1/2 3/(2/3)=9/2 3 5 9/2

14、0 5/2 0 0 9/2 0 M5/2 3 x1 2 1 0 0 1/3 1/3 x3 2 0 0 1 1/3 1/3 0 5 x2 6 0 1 0 1/2 0 36 3 5 0 3/2 1 0 0 0 3/2 M1 X*=（2，6，2，0）T max z=32+56=36 类型二：目标函数 min z，约束条件组与。例 2：用单纯形法求解 min z=4x1+3x2 s.t.012231642212121xxxxxx，解：减去松弛变量 x3，x4，并化为等效的标准模型：max z/=4x13x2 s.t.4,3,2,1,012231642421321jxxxxxxxj 增加人工变量 x5、

15、x6，得到：max z/=4x13x2Mx5Mx6 s.t 6,.,2,1,01223164264215321jxxxxxxxxxj 单纯形表求解过程如下：CB XB b 4 0 0 M M L x1 x2 x3 x4 x5 x6 M x5 16 2（4）1 0 1 0 16/4=4 M x6 12 3 2 0 1 0 1 12/2=6 5M 6M M M M M 5M4 6M3 M M 0 0 3 x2 4 1/2 1 1/4 0 1/4 0 4/1/2=8 M x6 4（2）0 1/2 1 1/2 1 4/2=2 2M3/2 3 3/4M/2 M M/23/4 M 2M5/2 0 M/23

16、/4 M 3/43M/2 0 3 x2 3 0 1 3/8 1/4 3/8 1/4 4 x1 2 1 0 1/4 1/2 1/4 1/2 17 4 3 1/8 5/4 1/8 5/4 0 0 1/8 5/4 M1/8 M5/4 X*=（2，3，0，0）T min z=max z/=（17）=17 四、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例（与本资料P2例1“图解法”、P7例1“单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在 A、B、C 三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售

17、后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：A B C 利润（万元）甲 乙 3 5 9 9 5 3 70 30 有效总工时 540 450 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？解：原问题 设 x1、x2为生产甲、乙产品的数量。max z=70 x1+30 x2 s.t.设 备 消 耗 产 品 072039450555409321212121xxxxxxxx，将这个原问题化为它的对偶问题 设 y1、y2、y2分别为设备 A、B、C 单位工时数的加工费。min w=540y1+450y2+720y3 s.t.32103035

18、970953321321，iyyyyyyyi 用大 M 法，先化为等效的标准模型：max w/=540y1450y2720y3 s.t.5,.,2,1,0303597095353214321jyyyyyyyyyj 增加人工变量 y6、y7，得到：max z/=540y1450y2720y3My6My7 s.t 5,.,2,1,030359709537532164321jyyyyyyyyyyyj 大 M 法单纯形表求解过程如下：CB XB b 540 450 720 0 0 M M L y1 y2 y3 y4 y5 y6 y7 M y6 70 3 5 9 1 0 1 0 70/3 M y7 30

19、（9）5 3 0 1 0 1 30/9=10/3 12M 10M 12M M M M M 12M540 10M450 12M720 M M 0 0 M y6 60 0 10/3（8）1 1/3 1 1/3 60/8=2.5 540 y1 10/3 1 5/9 1/3 0 1/9 0 1/9 10/3/1/3=10 -300+10/3M-8M180 M M/3+60 M M/360 0-150+10/3M 8M-540 M M/360 0 M/3+60 720 y3 15/2 0 5/12 1 1/8 1/24 1/8 1/24 15/2/5/12=18 540 y1 5/6 1（5/12）0

20、1/24 1/8 1/24 1/8 5/6/5/12=2 540 572 720 135/2 475/12 135/2 75/2 0 125 0 135/2 475/12 135/2M 75/2M 720 450 y3 20/3 1 0 1 1/6 1/6 1/6 1/6 y2 2 12/5 1 0 1/10 3/10 1/10 3/10 5700 360 450 720 75 15 75 15 180 0 0 75 15 75M 15M 该对偶问题的最优解是 y*=（0，2，320，0，0）T 最优目标函数值 min w=（5700）=5700 五、运输规划问题：运输规划问题的特殊解法“表上

21、作业法”解题步骤：1、找出初始调运方案。即在(mn)产销平衡表上给出 m+n-1 个数字格。（最小元素法）2、（对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（闭回路法）3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用表上闭回路法调整即迭代计算，得新的基本可行解）4、重复 2、3，再检验、再迭代，直到求得最优调运方案。类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例：某钢铁公司有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为 100 万吨、80 万吨和 50 万吨，炼铁厂年需矿石量分别为 50 万吨、70 万吨、80 万吨

22、和 30 万吨，这三个铁矿与四个炼铁厂的距离如下：B1 B2 B3 B4 A1 A2 A3 15 20 3 30 70 8 14 20 12 3 20 15 问：该公司应如何组织运输，既满足各炼铁厂需要，又使总的运输费用为最小（按吨.公里计）？解：用“表上作业法”求解。用最低费用法（最小元素法）求此问题的初始基础可行解：炼 铁 距 离 铁 矿 厂 B1 B2 B3 B4 产量 Si A1 15 20 67 3 30 65 100 20 80 A2 70 8 14 44 20 80 30 20 30 A3 12 53 3 20 33 25 10 50 50 销量 dj 50 70 80 30 2

23、30 230 初始方案：Z=1520+380+7030+820+2030+350=3550（吨.公里）的初始可行解进行迭代（表上闭回路法），求最优解：B1 B2 B3 B4 产量 Si A1 15 20 14 3 30 12 100 20 80 A2 70 53 8 14 9 20 80 50 30 A3 12 3 20 20 25 10 50 销 地 费 用 产 地 20 80 B1 B3 A1 B2 20 30 30 B1 B3 A2 B2 50 A3 销 地 费 用 产 地 30 20 销量 dj 50 70 80 30 230 230 用表上闭回路法调整后，从上表可看出，所有检验数=0

24、，已得最优解。最优方案：Z=1520+380+850+2030+1230+320=1960（吨.公里）解法分析：如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打的空格称为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算 0 故为偶点。找出所有空格的闭回路后计算它们的检验数偶点奇点ijijijcc，必须ij0，才得到最优解。否则，应选所有中正的最大者对应的变量 xj为入基变量进行迭代（调整）。检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。重复以上两步，再检验、再调整，直到求得最优运输方案。求下面运

25、输问题的最小值解：1 2 3 4 1 3 11 3 10 7 2 1 9 2 3 4 3 7 4 10 5 9 3 6 5 6 解：由最小元素法得到初始解：v1=2 v2=9 v3=3 v4=10 1 9 3 4 u1=0 1 3 11 3 10 7 4 3 20 80 B1 B3 A1 50 30 B2 B4 A2 30 20 B1 B2 A3 u2=-1 2 1 9 2 3 4 3 1 u3=-5 3 7 4 10 5 9 6 3 3 6 5 6 则：1112222431331,2,1,6,10,12，最小值为-6，非基变量为24x，闭回路242423131424:xxxxxx，最大调整量

26、为 1，得新解：1314212432345,2,3,1,6,3xxxxxx，重新计算位势及影响系数，得下表：v1=8 v2=9 v3=3 v4=10 1 2 3 4 u1=0 1 3 11 3 10 7 5 2 u2=-7 2 1 9 2 3 4 3 1 u3=-5 3 7 4 10 5 9 6 3 3 6 5 6 1112222331335,2,7,6,4,12，最 小 值 为-5，非 基 变 量 为11x，闭 回 路111114242111:xxxxxx，最大调整为 2，得新解：1113212432342,5,1,3,6,3xxxxxx 重新计算位势及影响系数，得下表：v1=3 v2=4

27、v3=3 v4=5 1 2 3 4 u1=0 1 3 11 3 10 7 2 5 u2=-2 2 1 9 2 3 4 1 3 u3=0 3 7 4 10 5 9 6 3 3 6 5 6 1214222331337,5,7,1,4,7，此时，0ij，故当前解为最优解。最优解值为：3 2 3 5 1 1 3 3 4 6 5 370Y 。六、目标规划问题 已知目标规划问题 min z=p1 d1-+p2d2-+p3（5d3-+3d4-）+p4 d1+x1+2x2+d1-d1+=6 x1+2x2+d2-d2+=9 x1-2x2+d3-d3+=4 x2 +d4-d4+=2 x1，x20，di-,di+0

28、 (i=1,2,3,4)分别用图解法和单纯形法求解 x2 5 4 3 2 1 0 d1+d4-d1-d3+d3-d4d2+d2-B A 2 4 6 8 x1 七（1）、整数规划问题（分枝定界法）：用分枝定界法求解整数规划 12max zxx 121212951,141412,3,0 xxxxx x且为整数.七（2）、工作指派问题：工作指派问题的数学模型假定有 n 项工作需要完成，恰好有 n 个人每人可去完成其中一项工作，效果要好。工作指派问题的特殊解法“匈牙利法”（考！）解题步骤：1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法：行约简系数矩阵各行元素减去所在行的最小元素，列约简再从所得矩

29、阵的各列减去所在列最小元素。2、试求最优解。如能找出 n 个位于不同行不同列的零元素，令对应的 xij=1，其余 xij=0，得最优解，结束；否则下一步。作法：由独立 0 元素的行（列）开始，独立 0 元素处画（）标记，在有（）的行列中划去（也可打*）其它 0元素；再在剩余的 0 元素中重复此做法，直至不能标记（）为止。3、作能覆盖所有 0 元素的最少数直线集合。作法：对没有（）的行打号；对已打号的行中所有 0 元素的所在列打号；再对打有号的列中 0元素的所在行打号；重复、直到得不出新的打号的行(列)为止；对没有打号的行画一横线，对打号的列画一纵线，这就得到覆盖所有 0 元素的最少直线数。未被

30、直线覆盖的最小元素为 cij,在未被直线覆盖处减去 cij,在直线交叉处加上 cij。4、重复 2、3，直到求得最优解。类型一：求极小值的匈牙利法：（重点掌握这种基本问题）例 1：有甲、乙、丙、丁四个人，要派去完成 A、B、C、D 四项工作，他们完成的工时如下表：A B C D 甲 乙 丙 丁 6 12 13 4 10 3 12 14 7 14 13 16 8 8 12 10 试问：应如何分配任务可使总工时为最少？解：用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为：（cij）=10128816131471412310413126 24009670119070982 20009270

31、115070582 2)0(00927)0(115)0(7)0(582*使总工时为最少的分配任务方案为：甲D，乙B，丙A，丁C 此时总工时数 W=4+3+7+12=26 例 2：求效率矩阵 54325645778587910的最优解。列约简 任 务 工 时 人 行约简 标号 甲 乙 丙 丁 A B C D 解：54325645778587910 3210120122301023 2210020112300023 221002)0(1123)0(0)0(23*所画（）0 元素少于 n，未得到最优解，需要继续变换矩阵（求能覆盖所有 0 元素的最少数直线集合）：221002)0(1123)0(0)0

32、(23*未被直线覆盖的最小元素为 cij=1,在未被直线覆盖处减去 1,在直线交叉处加上 1。1100020201200024 11000202012)0(0)0(24*）（）（得最优解：0010100000010100 类型二：求极大值的匈牙利法：min z=max（z）（cij）（Mcij）=（bij），（cij）中最大的元素为 M max z=jijijixc=jijijixcM)(=jijijixcM)(jijijixc 标号 列约简 行约简 标号 第二部分 动态规划 只要求掌握动态规划的最短路问题用“图上标号法”解决：具体解题步骤请参看教材（这是本套资料少见的与教材完全相同的算法类型

33、之一，务必看书掌握）只有完全理解了这种作法（思路：逆向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解！第二部分到此结束 第三部分 网络分析 一、求最小生成树（最小支撑树、最小树）问题：破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。参考例题：例：求下图的最小生成树：解：用“破圈法”求得最小生成树为：6 7 9 4 1 5 10 v2 v1 v3 v5 v4 v6 3 2 8 9 4 1 5 v2 v1 v3 v5 v4 v6 2 已得最小树，此时权

34、w=1+2+4+5+9=21 为最小。二、最短路问题：（有向图）TP 标号法（狄克斯托算法）具体解题步骤请参看教材 P125（这是本套资料少见的与教材完全相同的算法类型之一，务必看书掌握）只有完全理解了这种作法（思路：顺向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解！参考例题：例：教材 P124 图 48 的例子（略）三、网络最大流问题：寻求网络最大流的标号法（福特富克尔逊算法）具体解题步骤请参看教材 P130。（教材用有序数对（fij，cij）表示（流量，容量），但我们解题算法格式按南邮要求，用大多数运筹学书籍中的标准格式，即用有序数对（cij，fij）表示（容量，流量）。解法

35、本质是相同的。）只有完全理解了这种作法（思路：标号检查、迭代调整）才有可能做题，考试时数字无论如何变化都能作出正确求解！第三部分到 第四部分 存储论（简介）随机存储模型参考例题：例：一食品店要决定每天牛奶的进货量，该店根据过去的销售经验，知道需求量的概率分布如下：需求 x（箱）25 26 27 28 p（x）0.1 0.3 0.5 0.1 若进货每箱 80 元，售价 100 元，又若当天不能售出因牛奶变质而全部损失，试确定每天进货量。解法一：已知 C=80，p=100，g=0，需求 x（箱）25 26 27 28 概率 p（x）0.1 0.3 0.5 0.1 累计概率 0.1 0.4 0.9 1 根据单周期随机型存储模型（“报童模型”）之离散型随机存储模型公式，可得 00100080100)(*sgpsCpQxp0.2 即可以确定进货 26 箱，获利的期望值最大。解法二：k=10080=20，h=80.khk=10020=0.2 Px=25=0.10.2Px=25+Px=26=0.4 可以确定进货 26 箱，获利的期望值最大。注：该问题即“报童问题”（关于报童进报纸问题的数学模型），即是相当于将上题的进“牛奶”改为进“报纸”等等，解法思路是完全一致的，请注意！