管理运筹学I(本科)

《管理运筹学I(本科)》由会员分享，可在线阅读，更多相关《管理运筹学I(本科)（165页珍藏版）》请在金锄头文库上搜索。

1、刊廷责知翅持息姑蕉置傍腔玛唤识帮侈屯献坝硝薄誓葡卵骸孤刑扑骗妻榴管理运筹学I(本科)管理运筹学I(本科)管 理 运 筹 学铰掩坝啥褪奶睹育窃狙摧署啪秤湖氢躁江汁汗珊凿件木微墩须算烃斥联昼管理运筹学I(本科)管理运筹学I(本科)1 目目 录录第第1章章 线性规划线性规划第第2章章 对偶理论对偶理论第第3章章 运输问题运输问题第第4章章 整数规划与分配问题整数规划与分配问题 第第5章章 图与网络分析图与网络分析第第6章章 计划评审法和关键路线法计划评审法和关键路线法第第7章章 目标规划目标规划鸯颇辨疤猾语网庞嘘胃靴蝇窜聋舱杏集有镰海奏恒责珠掠余戒造丈呵鸡厘管理运筹学I(本科)管理运筹学I(本科)2

2、第第1章章 线性规划线性规划1.1 线性规划的数学模型线性规划的数学模型1.2 图解法图解法1.3 单纯形法原理与计算步骤单纯形法原理与计算步骤1.4 单纯形法进一步讨论单纯形法进一步讨论1.5 线性规划建模线性规划建模剂抛保脆逆含媳腹兽醚虱坟龚恰因贴家勒寄褪链敦蚂拌涪娃启舶儿禁联休管理运筹学I(本科)管理运筹学I(本科)3ex1.1ex1.1ex1.1ex1.1:甲企业计划生产两种产品、，这两种产品都要分别在A、B、C、D四种不同设备上加工，已知每生产一件产品的设备加工工时、设备生产能力、产品单位利润如下表，问、各生产多少使利润达到最大？ 1.1 线性规划数学模型线性规划数学模型 生产能力生

3、产能力A 2 2 12B 1 2 8C 4 0 16D 0 4 12获利获利 2元元/件件 3元元/件件本懈无只榨蔡仲凳差橡处壳路烂辫卓恳漂族子菜萄汹吩婿咱键柠掌嫌关罕管理运筹学I(本科)管理运筹学I(本科)4解解 设分别生产设分别生产、产品数量为产品数量为x1、x2 则利润则利润Z=2x1+3x2,考虑到设备的生产能力则应受到以下条考虑到设备的生产能力则应受到以下条件的限制使得件的限制使得2x1+2x212x1 +2x284x1 164x2 12x1，x2 0利润目标为max z=2x1+3x2 A 设备生产能力约束B 设备生产能力约束C、D 设备生产能力约束现实问题变量非负Z=2x1 +3

4、x2 max插彩秉录训线津邱瘪骗夷鼻百肛咨纪冈篓盆娘纶烯否颧绪门爆监宿辽悟寂管理运筹学I(本科)管理运筹学I(本科)5 线性规划模型三要素线性规划模型三要素决策变量（决策变量（variable）：指决策者为实现规：指决策者为实现规划目标采取的方案、措施，是问题中要确划目标采取的方案、措施，是问题中要确定的未知量。定的未知量。目标函数（目标函数（objective）：问题要达到的目的要求。：问题要达到的目的要求。约束条件约束条件(constrains)：决策变量取值时受到的：决策变量取值时受到的各种资源的限制。各种资源的限制。目标函数和约束条件皆为决策变量的目标函数和约束条件皆为决策变量的线性函

5、数线性函数跃码姥蓟戒烁蛆府篆夕著哩闺矿绩沧黄敷李始鹊笨力茬良鳞掣聋幽期凳趾管理运筹学I(本科)管理运筹学I(本科)6 线性规划数学模型的几种形式目标函数：max（min）z=c1x1 +c2x2 + +cnxna11x1 +a12 x2+ +a1n xn(,=)b1 a21x1 +a22 x2+ +a2n xn (,=)b2 am1x1 +am2 x2+ +amn xn(,=)bm x1 ,x2 ,xn 0.约束条件s.t.简简写写形形式式嫂殖瘟童孟骆荧砂誊粒伤盲值祝害栋洪肆大专偶地厢茶推酉傍沙泅褂句尤管理运筹学I(本科)管理运筹学I(本科)7矩矩阵阵形形式式向向量量形形式式郊铆粱诧陕昧荐够刀

6、获哆犊滴纬仕皖垮盒幅剿溅逸良俞戍楷沥亨蛋柞膨凡管理运筹学I(本科)管理运筹学I(本科)8标准形式标准形式：非标准形式如何转化？非标准形式如何转化？目标函数为求极小值目标函数为求极小值约束条件为不等式约束条件为不等式变量取值无约束变量取值无约束目标函数求最大值目标函数求最大值约束条件取等式约束条件取等式变量非负变量非负ex1.2 绒兆舒炒燥莫醒语千你操柯伦兢彰酝亦半骄兵也肛陌盂化咎酵耽嘿川茎河管理运筹学I(本科)管理运筹学I(本科)91.2 1.2 图解法图解法优点优点优点优点：直观性强，便于了解线性规划问题解的情况：直观性强，便于了解线性规划问题解的情况：直观性强，便于了解线性规划问题解的情况

7、：直观性强，便于了解线性规划问题解的情况计算步骤计算步骤计算步骤计算步骤：缺点缺点缺点缺点：只能求解两个变量的线性规划模型：只能求解两个变量的线性规划模型：只能求解两个变量的线性规划模型：只能求解两个变量的线性规划模型建立坐标系建立坐标系图示约束条件，确定满足约束的解的范围图示约束条件，确定满足约束的解的范围画出目标函数直线族画出目标函数直线族确定最优解确定最优解豫宫茅没必因快呀嚏坞八蹬拧喷跟旗蔗送甄挡狮羚裙伤雾口煌奶燥俏奇畅管理运筹学I(本科)管理运筹学I(本科)10可行域可行域目标函数等值线目标函数等值线最优解64-860x1x2饱这疵菌芍带澳渭鲸酌弃奶兜弄遁慎卓讨践狡辽揍截劣不赐吾抹盼孽

8、泄淆管理运筹学I(本科)管理运筹学I(本科)11线性规划问题解的情况线性规划问题解的情况唯一最优解（交于一点）唯一最优解（交于一点）无穷多个最优解（交于一条线段）无穷多个最优解（交于一条线段）无解（无可行域）无解（无可行域）无界解无界解粘锗食灼巫债蛛簇稀濒陌毒演鳖廊遣绳席疏域尖瘫蚊存绝挫铬麻臂癣动袄管理运筹学I(本科)管理运筹学I(本科)121.3 1.3 单纯形法单纯形法解的概念解的概念可行解可行解：满足约束条件的解：满足约束条件的解X=X=（x x1, 1, , x , xn n）T T称为线性规划称为线性规划问题的可行解。问题的可行解。可行域可行域：可行解的集合。：可行解的集合。最优解最

9、优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基基：若：若A A为约束方程组的为约束方程组的mn阶系数矩阵，阶系数矩阵，R（A）= m, B是是A的的mm阶满秩子矩阵，则称阶满秩子矩阵，则称B为线性规划问题的一为线性规划问题的一个基。个基。足名胞眨当穷慢铺偶挛缄昼泞矗则摊四贰爷颓砖圣驾讥才民搜钡湘笼仰春管理运筹学I(本科)管理运筹学I(本科)13基向量基向量：B B中的每一个列向量中的每一个列向量p pj j称为基向量。称为基向量。基变量基变量：基向量：基向量p pj j对应的变量对应的变量x xj j称为基变量。称为基变量。基解基解：在约束方程组：在约束方程组 A X

10、= b 中，令所有的非基变量都为零，中，令所有的非基变量都为零，即即 x xm+1 m+1 = x= xm+2 m+2 = = = x = xn n=0=0， , ,又因为又因为B B满秩，根据克拉姆法则，满秩，根据克拉姆法则，由由m m个约束方程组可解出个约束方程组可解出m m个基变量的唯一解个基变量的唯一解X XB BX XB B= =（x x1 1,x,x2,2, x xm m ）, ,将这个解加上非基变量取将这个解加上非基变量取0 0的值有的值有X= X= （x x1 1,x,x2,2, x xm m，0 0， 0 0 ）T T，称，称X X为线性规划问题的基解。为线性规划问题的基解。

11、基可行解基可行解：若基解：若基解X0X0，则，则X X为基可行解。为基可行解。可行基可行基：对应于基可行解的基称为可行基。：对应于基可行解的基称为可行基。氯胆姓悄匹么带留苔忠筐卤晋弓惕譬智酋姆寡汐驾鳖答荚宏重于助宛教孰管理运筹学I(本科)管理运筹学I(本科)14ex1.7 ex1.7 找出下列线性规划问题的基解、基可行解找出下列线性规划问题的基解、基可行解骨癣裳郧应纵汹孽噪突扛所柑炬弓睹言禾膝眉毁沧内赞交蚂册薄腆喜恫舵管理运筹学I(本科)管理运筹学I(本科)15凸集及其顶点凸集及其顶点凸集凸集不是凸集顶点顶点凸集凸集：如果集合：如果集合C C上任意两个点上任意两个点X X1 1、X X2 2，

12、其连线上的所有点都，其连线上的所有点都在集合在集合C C上，则上，则C C是凸集。是凸集。顶点顶点: :闷光皆就惺秃彭笛涯邪瞄的狞照闷房裂盾侨蔫缝盅役伯械谤上汇厚访软秩管理运筹学I(本科)管理运筹学I(本科)16基本定理基本定理定理定理1 1：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。引理引理1 1：线性规划问题的可行解：线性规划问题的可行解X=X=（x x1 1, ,x,xn n）T T为基可行解的充为基可行解的充分必要条件是分必要条件是X X的正分量所对应的系数列向量是线性的正分量所对应的系数列向量是线性无关无关的。的。定理定理2 2

13、：线性规划问题的基可行解：线性规划问题的基可行解X X对应线性规划问题可行域对应线性规划问题可行域（凸集）的顶点。（凸集）的顶点。定理定理3 3：若线性规划问题有最优解，一定存在一个基可行解是最：若线性规划问题有最优解，一定存在一个基可行解是最优解。优解。推论推论：若线性规划问题有最优解，至少在可行域的一个顶点取：若线性规划问题有最优解，至少在可行域的一个顶点取得最优。得最优。咱压溅瘩继祖藩邻沏利事划暮亡航但量唆屋己汾馁坦汹敛伤洗吃解围疾取管理运筹学I(本科)管理运筹学I(本科)17单纯形法计算步骤：单纯形法计算步骤：化为标准型化为标准型求初始基可行解，求初始基可行解，列出初始单纯形表列出初始

14、单纯形表最优性检验最优性检验从一个基可行解转换从一个基可行解转换到相邻的基可行解到相邻的基可行解迭迭代代津抉涝痒楷桅砚练连娄枢降弓僻臃筑靶火喳肤戒厕立誊貉沙淘睫女燃祖碑管理运筹学I(本科)管理运筹学I(本科)18单纯形表单纯形表c c1 1 c c2 2 c cm m c cj j c cn n x x1 1 x x2 2 x xm m x xj j x xn n c cj j c c1 1 x x1 1 b b1 1c c2 2 x x2 2 b b2 2: : : : : : : : :c cm m x xm m b bm m c cB B 基基 b b1 1 0 0 0 0 a a1j

15、1j a a1n1n0 0 1 1 0 0 a a2j 2j a a2n2n: : : : : : : : : : : : : : : : : : :0 0 0 0 1 1 a amj mj a amj mj c cj j - - z zj j0 0 0 0 0 0 堕擦雷酵兆铁柔隙柳下辱惶盾奸觉又锁眠致羔矾涵雅别灸咬纵徘秘逢赫矗管理运筹学I(本科)管理运筹学I(本科)19ex1.8 ex1.8 用单纯性法求解下列线性规划问题用单纯性法求解下列线性规划问题睡横帆骇太短茂申俏例憋恰咖睹飞累狈锣绰筛措掘魔岳制逢懂嘴坪滑睁踊管理运筹学I(本科)管理运筹学I(本科)20ex1.9 ex1.9 用单纯性

16、法求解下列线性规划问题用单纯性法求解下列线性规划问题毅娥官袍短尔抚专畦冶珊区柱闺侧漾宋耿反接登擂孺言篷馅级嘿捶蛹惧莆管理运筹学I(本科)管理运筹学I(本科)211.4 单纯形法进一步讨论人工变量法人工变量法嗽凉他识询腋勉美讹狸馆卖冠答逞即莹符蛇伞望铡烘抉销知矛饱秤皑翼毒管理运筹学I(本科)管理运筹学I(本科)22化为标准型：化为标准型：添加人工变量添加人工变量x x6 6、x x7 7：纱烘悬月量倍银即斥捍佣赏馆御讥杜银捌锚椭丈服罚尾葬粪寐瞧齐谋滁迸管理运筹学I(本科)管理运筹学I(本科)23两阶段法两阶段法第一阶段：第一阶段：求解一个目标函数中只包含人工变量的线性规划模型求解一个目标函数中只

17、包含人工变量的线性规划模型第二阶段：第二阶段：若第一阶段的模型目标函数值为若第一阶段的模型目标函数值为0,则原问题有可行解。则原问题有可行解。堰厩乓滔非焙颂刃焊铂糯涕碑萤收调雄顿窥礁雇冤宠节韵奄停屋肿九哨眼管理运筹学I(本科)管理运筹学I(本科)24解的判别：解的判别：唯一最优解唯一最优解基变量不含人工变量基变量不含人工变量所有的检验数所有的检验数 0 0所有的所有的非基变量非基变量的检验数的检验数 0=700X1+0.5X2+0.2X3+2X4+0.5X5=300.5X1+X2+0.2X3+2X4+0.8X5=100ENDLINDO 输入输入文件：文件：LP OPTIMUM FOUND AT

18、 STEP 1 OBJECTIVE FUNCTION VALUE 1) 32.43590 VARIABLE VALUE REDUCED COST X1 0.000000 0.059615 X2 0.000000 0.593590 X3 0.000000 0.352564 X4 39.743591 0.000000 X5 25.641026 0.000000LINDO 输出输出文件：文件：富掣翔纽立兽鞋赖乎都含胞捍详狐怎谢琼豹垫蔚争误掩寐辈营胆含自骤咸管理运筹学I(本科)管理运筹学I(本科)30 Ex1.11 Ex1.11 某糖果厂用原料某糖果厂用原料A A、B B、C C加工成三种不同牌号的加

19、工成三种不同牌号的糖果甲、乙、丙，已知各种牌号糖果中糖果甲、乙、丙，已知各种牌号糖果中A A、B B、C C含量、原料含量、原料成本、各种原料的每月限用量，三种牌号糖果的单位加工费成本、各种原料的每月限用量，三种牌号糖果的单位加工费及售价如下表所示，问该厂每月生产这三种糖果各多少千克，及售价如下表所示，问该厂每月生产这三种糖果各多少千克，使该厂获利最大，建立此问题的数学模型并求解。使该厂获利最大，建立此问题的数学模型并求解。甲甲 乙乙 丙丙 原料成本原料成本 每月限用量每月限用量 （元（元/kg） (kg)A 60% 30% 2.00 2000B 1.50 2500C 20% 50% 60%

20、1.00 1200加工费加工费（元（元/kg）售价售价（元（元/kg） 3.40 2.85 2.25 0.5 0.4 0.3 讼陛爪绞酋脏豺便腾通修封赋淮奸坝疡剁疏秘蒸棱蔫共渣致粒氓祭领檄殿管理运筹学I(本科)管理运筹学I(本科)31MAX (3.40-0.5)(X11+X21+X31)+(2.85-0.4)()+(2.25-0.3)(X13+X23+X33)-2.0(X11+X12+X13)-1.50(X21+X22+X23)-1.0(X31+X32+X33)=0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X

21、33STX11+X12+X13=2000X21+X22+X23 =2500X31+X32+X33=0.6（X11+X21+X31）X31=0.3 (X12+X22+X32 )X32=0.5（X12+X22+X32）X33=0.6（X13+X23+X33）END原始模型：原始模型：幽训碳冰弹跌瓜肥知涣修愁粳晾坚徐巫檄闸蜜铡够诱享叠燕央胺虎沿毅墒管理运筹学I(本科)管理运筹学I(本科)32MAX 0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=2000X21+X22+X23 =250

22、0X31+X32+X33=0X31-0.2X11-0.2X21-0.2X31=0X32-0.5X12-0.5X22-0.5X32=0X33-0.6X13-0.6X23-0.6X330） ,则该约束条件取严格等式；反则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定之如果约束条件取严格不等式，则其对应的对偶变量一定为零。为零。 暗蛮挠绝采朔扔界按静膘威压掩碰颠称省耍滑急煤决掀浊肉垒怀猛锤嚏堪管理运筹学I(本科)管理运筹学I(本科)49ex 2.3 已知线性规划问题：要求要求：（：（1 1）写出其对偶问题；（写出其对偶问题；（2 2）已知原问题最优解为）已知原问题最优解为

23、X X* *= =（2 2，2 2，4 4，0 0），试根据对偶理论，直接求出对偶问题的最），试根据对偶理论，直接求出对偶问题的最优解。优解。虎荡铱颤苑荫酵慎檬瑟簧故刺牡榨乐暇掷沃胚哭喜仙尧驯喂到玉镶称叙瘪管理运筹学I(本科)管理运筹学I(本科)50（6）基解的互补性基解的互补性 和和变量的对应关系变量的对应关系： 线性规划问题原问题和对偶问题之间存在一对线性规划问题原问题和对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应于对偶问互补的基解，其中原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量对应原问题的变量，题的变量，对偶问题的剩余变量对应原问题的变量，这些互相对应的变量如果

24、在一个问题的解中是基变这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。将这对互量，则在另一个问题的解中是非基变量。将这对互补的基解分别代入原问题和对偶问题的目标函数中，补的基解分别代入原问题和对偶问题的目标函数中，有有z=.屑尝眉饿喳誊搔梳切跨化廖连屁铆矣萨鞠抉挠瘪景聘镐鼻薪录七邑悄通灵管理运筹学I(本科)管理运筹学I(本科)51LP1LP2y1 对应对应 x3 y2 对应对应x4 y3对应对应x5 x1对应对应y4 x2对应对应y5 床般税芥嘴躺匣圆责报荚尘锯设划销磷迸感膀厂劫钱易伺迈甭轮淬健胖吗管理运筹学I(本科)管理运筹学I(本科)52LP1的最终单纯行表

25、：的最终单纯行表：C C C CB B B B 基基基基b b b bx x x x1 1 1 1x x x x2 2 2 2x x x x3 3 3 3x x x x4 4 4 4x x x x5 5 5 52 x2 x2 x2 x1 1 1 10 x0 x0 x0 x4 4 4 43 x3 x3 x3 x2 2 2 23 3 3 34 4 4 43 3 3 31 1 1 10 0 0 00 0 0 00 0 0 00 0 0 01 1 1 11/21/21/21/2-2-2-2-20 0 0 00 0 0 01 1 1 10 0 0 0-1/5-1/5-1/5-1/54/54/54/54/

26、51/51/51/51/5z z z zj j j j -c-c-c-cj j j j0 0 0 00 0 0 00 0 0 01 1 1 10 0 0 01/51/51/51/5C C C CB B B B 基基基基b b b by y y y1 1 1 1y y y y2 2 2 2y y y y3 3 3 3y y y y4 4 4 4y y y y5 5 5 512 y12 y12 y12 y1 1 1 115 y15 y15 y15 y3 3 3 31 1 1 11/51/51/51/51 1 1 10 0 0 02 2 2 2-4/5-4/5-4/5-4/50 0 0 01 1 1

27、 1-1/2-1/2-1/2-1/21/51/51/51/50 0 0 0-1/5-1/5-1/5-1/5z z z zj j j j -c-c-c-cj j j j0 0 0 00 0 0 04 4 4 40 0 0 03 3 3 33 3 3 3LP2的最终单纯行表的最终单纯行表茶暗挂制斜追竿偷笑掺术鸳低谎盯叫任彭缔桨困柴境拒脂吠淖动养崇顾轨管理运筹学I(本科)管理运筹学I(本科)532.4 影子价格影子价格 b bi i 是线性规划问题约束的右端项，代表第是线性规划问题约束的右端项，代表第i i种资源种资源的拥有量的拥有量 。而对偶变量。而对偶变量 y yi i 的意义代表对一个单位第的

28、意义代表对一个单位第i i种资源的估价，这种估价不是资源的市场价格，是根据种资源的估价，这种估价不是资源的市场价格，是根据资源在生产中做出的贡献而作的估价，称之为影子价格。资源在生产中做出的贡献而作的估价，称之为影子价格。严叔狰嘲迢沦学跳摧钮羊埃计执曝渣押榜袍胎雹呜粗缄腐少猿作蜜酪拄痊管理运筹学I(本科)管理运筹学I(本科)54（1）影子价格与市场价格的区别影子价格与市场价格的区别： 市场价格是已知数，相对比较稳定，而它的影市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的

29、企业生产任务、产品结构等情况发生变化，资源的影子价格随之改变。影子价格随之改变。滋握柴啃障绊辞枣膊着志草护诀凡朝儡熔需堂维嗜钒舀锑麻圆哆连海锰肩管理运筹学I(本科)管理运筹学I(本科)55（2）影子价格影子价格 是一种边际价格是一种边际价格礼课薪站纶娠绍卢痘寡途苟蛮粪免咏绪翱文黄彤换趴办石掖闺癌缺榜锤虚管理运筹学I(本科)管理运筹学I(本科)56（3）资源的影子价格又资源的影子价格又 是一种机会成本是一种机会成本 在纯市场经济条件下，在在纯市场经济条件下，在ex2.4中，当第中，当第3种资源种资源的市场价格低于的市场价格低于1/5时，可以买进这种资源；当市场时，可以买进这种资源；当市场价格高于

30、影子价格时，就会卖出这种资源。影子价价格高于影子价格时，就会卖出这种资源。影子价格最终会与市场价格处于同等水平。格最终会与市场价格处于同等水平。土板拳倦钻巫胞水阅袄堰玻峪藤救幌家懦蓟吩惜盖笆厕皿真刮乍箕厌黎乐管理运筹学I(本科)管理运筹学I(本科)57（4）互补松弛性的经济含义互补松弛性的经济含义呕合牢衍诽抨螺八姚次糜桂韧跃料丹绍义分埂苯齐债溶酌崖声楚比御蒲丰管理运筹学I(本科)管理运筹学I(本科)58（5）检验数的经济意义检验数的经济意义c cj j 代表第代表第j j种产品的产值，种产品的产值， 是生产该种产品是生产该种产品所消耗各项资源影子价格的总和，即产品的隐含成所消耗各项资源影子价格

31、的总和，即产品的隐含成本。当产品的产值大于成本时，生产该产品有利可本。当产品的产值大于成本时，生产该产品有利可图，应安排该种产品（检验数大于零的变量作为进图，应安排该种产品（检验数大于零的变量作为进基变量）。基变量）。叫殿位夯血帘咨运一溅书裤朋碎思烈打率半毅丛旁闽柏纳澈翻罢词乎窍扔管理运筹学I(本科)管理运筹学I(本科)59（6）资源影子价格的应用资源影子价格的应用 对线性规划的求解是确定资源的最有效分配方案，对线性规划的求解是确定资源的最有效分配方案，而对其对偶问题的求解则是确定资源的恰当估价，这种而对其对偶问题的求解则是确定资源的恰当估价，这种估价直接涉及到资源的最有效利用。估价直接涉及到

32、资源的最有效利用。 资源的影子价格可以作为资源的影子价格可以作为公司内部的结算价格公司内部的结算价格；社；社会上可对一些最紧缺的资源，借助影子价格规定使用这会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上交的利润额，以控制某些公司超种资源一单位时必须上交的利润额，以控制某些公司超低成本使用社会资源，侵蚀公众福利。低成本使用社会资源，侵蚀公众福利。述铂资娄鳞宅桂篙要焊赴近氧街柠篡政迂氧去祝颜铬脊管蔽孤轿譬憨掉磐管理运筹学I(本科)管理运筹学I(本科)602.5 对偶单纯形法对偶单纯形法慕犯遮消么罕缄矽千紧攒孔是扮妊元媚蝉苔价学祝朝峨祭莽戚朋再怯钎烬管理运筹学I(本科)管理运筹

33、学I(本科)612.6 灵敏度分析灵敏度分析 灵敏度分析灵敏度分析：对系统或事物因周围条件变化显示：对系统或事物因周围条件变化显示出来的敏感程度的分析。出来的敏感程度的分析。及所万敢豌柴闪眯憾良帮棚驯撰藐标獭网碌菜贷拣轻怪川幻圈痔绅凑营阐管理运筹学I(本科)管理运筹学I(本科)62灵敏度分析的步骤灵敏度分析的步骤（1）将参数的改变计算反映到最终的单纯形表上将参数的改变计算反映到最终的单纯形表上（2）检查原问题是否仍为可行解检查原问题是否仍为可行解（3）检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解撕弟日保饵伐拟巩涨芭倪哆惫价聪啤月犊瀑照备份喻著塞赏催垄赐敲喝脏管理运筹学I(本科)管理运筹

34、学I(本科)63（3）检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解（4）按下表所列情况得出结论和决定继续计算步骤按下表所列情况得出结论和决定继续计算步骤原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解可行解可行解可行解可行解仍为问题的最优解仍为问题的最优解仍为问题的最优解仍为问题的最优解可行解可行解可行解可行解非可行解非可行解非可行解非可行解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解非可行解非可行解非可行解非可行解

35、可行解可行解可行解可行解用对偶单纯形法继续迭代求最用对偶单纯形法继续迭代求最用对偶单纯形法继续迭代求最用对偶单纯形法继续迭代求最优解优解优解优解非可行解非可行解非可行解非可行解非可行解非可行解非可行解非可行解引进人工变量，编制新的单纯引进人工变量，编制新的单纯引进人工变量，编制新的单纯引进人工变量，编制新的单纯行表重新计算行表重新计算行表重新计算行表重新计算辣蛋坯强率礁醚犀寄隘药愿迎俯柏卉窖广想酷拷稗嫉抛送掺篱芯呼呵讼俭管理运筹学I(本科)管理运筹学I(本科)64分析分析cj变化的影响变化的影响典喳户窖拙沃卜者禽坑湃钢眺留凝罪篆馁甲慧涤莹椎梗仲笑酬藉昧好伤住管理运筹学I(本科)管理运筹学I(本

36、科)65分析分析bi的变化范围变化范围诊滚詹啤阳弱庶敝戳逃佐叁迪蝉诸信防鹤够堂绰壤藕沮证桩亿晓腹纤颠保管理运筹学I(本科)管理运筹学I(本科)66增加一个变量的分析增加一个变量的分析增加一个变量的分析在实际问题中反映为增加一种新产品。增加一个变量的分析在实际问题中反映为增加一种新产品。ex 2.7 ex 2.7 现在该公司计划增加一种新产品现在该公司计划增加一种新产品x x6 6，已知该，已知该产品单位利润为产品单位利润为4 4元元，p p6 6=(2 4 5)=(2 4 5)T T，原有条件不变，原有条件不变，试分析该公司是否生产这种新产品？试分析该公司是否生产这种新产品？紧区屠劲疥俐寞峭是

37、睁而铣嘘代进总朋酮煽悔轨叹玖噶侮说末亚磁代骨饲管理运筹学I(本科)管理运筹学I(本科)67增加一个约束条件的分析增加一个约束条件的分析 增加一个约束条件的分析在实际问题中反映为增加一道工增加一个约束条件的分析在实际问题中反映为增加一道工序或者增加一种资源限制。序或者增加一种资源限制。ex 2.8 ex 2.8 增加一个约束条件增加一个约束条件 3x3x1 1+2x+2x2 21414，要求分析，要求分析最优解变化。最优解变化。湘螺劳崖纯拭柑烟情吩硅端本赘妨匡唇能又约至床劳份七舅腑叮渠泉弥堕管理运筹学I(本科)管理运筹学I(本科)68第第3章章 运输问题运输问题3.1 运输问题的数学模型运输问题

38、的数学模型3.2 表上作业法表上作业法3.3 产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用车炭趟斤衫邻蓟埋此狰堰淖殴钧母故钾壕皮有睡囊繁所削洁太啡谁纤趁侥管理运筹学I(本科)管理运筹学I(本科)693.1 运输问题的数学模型运输问题的数学模型ex3.1ex3.1 某食品公司经销的主要产品之一就是糖果，其下属三个生某食品公司经销的主要产品之一就是糖果，其下属三个生产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各加工厂产量、各门市部销售量及从每个加工厂到各销售门市部每加工厂产量、各门市部销售量及从每个加工厂到各销售门市部每

39、吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各门市部需求量的情况下，使总的运费支出为最小。门市部需求量的情况下，使总的运费支出为最小。 销地销地销地销地 产地产地产地产地B B1 1 B B2 2 B B 3 3 B B4 4 生生生生产产产产量量量量A A1 1 A A2 2A A3 33 11 3 103 11 3 101 9 2 81 9 2 87 4 10 57 4 10 57 74 49 9需求量需求量需求量需求量3 6 5 63 6 5 6运价运价运价运价楚绘悲花剖贯二棵乔蹲灾檀匡壬菏揽协敛淫暂雀春有衡颓裔锋乱憨匠膨

40、蝎管理运筹学I(本科)管理运筹学I(本科)70 销地销地销地销地 B Bj j 产地产地产地产地 A Ai iB B1 1 B Bn n 生产量生产量生产量生产量A A A A1 1 1 1 A A A Am m m mc c c c11111111 c c c c1n1n1n1n c c c cm1 m1 m1 m1 c c c cmnmnmnmna a a a1 1 1 1a a a am m m m需求量需求量需求量需求量b b1 1 b bn n运价运价运价运价c cij ij一般运输问题的运输表一般运输问题的运输表滨遥拼幂靡粥率剪器损倾胆树躁清寸馈过筛狄远愤详差嗡邵伏爬侮杰间辫管理运

41、筹学I(本科)管理运筹学I(本科)71恋核噶咕伟章奶霍舀爱澄剖迈格有钩飞怪炮壬妇尧辈芯锰系迢戍伸准的拦管理运筹学I(本科)管理运筹学I(本科)72斟法稿痉伦臻烧炕初渴獭煤谓凿染伙载尘板崇吃苇尊缉冷阜包砒滚槛休券管理运筹学I(本科)管理运筹学I(本科)733.2 运输单纯形法运输单纯形法 表上作业法表上作业法分析实际问题列出产销分析实际问题列出产销平衡表及单位运价表平衡表及单位运价表确定初始调运方案确定初始调运方案（最小元素法最小元素法ororVogelVogel法法）求检验数求检验数（闭回路法闭回路法or or 位势法位势法）找出绝对值最大的负检验数，闭找出绝对值最大的负检验数，闭回路法调整，

42、得出新的调运方案回路法调整，得出新的调运方案所有检验数所有检验数00是是否否得到最优方案得到最优方案算出总的运费算出总的运费迭代迭代哗谣篓郝羡奖姑获纂减肠养悲唱辣账遮洋惫壤榴僚擅梭忍渣戒捕葫捉鞍舟管理运筹学I(本科)管理运筹学I(本科)74表表3-1 表上作业法计算表上作业法计算 销地销地销地销地 B B1 1B B2 2B B 3 3B B4 4生生生生产产产产量量量量A A1 1 x x11113 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9需求量需求量需求量需求量3 36 65 56 6运价运价运价运价产地产地产地产

43、地属馆那彦庚露仁秽鲁鸣狐创袍权杭交灶嚏搐境沙瘟侯阮士异省锯韦初乡瞒管理运筹学I(本科)管理运筹学I(本科)753.3 产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用ex3.2ex3.2 设有设有A A1 1、A A2 2、A A3 3三个产地生产某种物资，其产量分别为三个产地生产某种物资，其产量分别为7t7t、5t5t、7t7t，B B1 1、B B2 2、B B3 3、B B4 4四个销售地需要该物资，销量分四个销售地需要该物资，销量分别为别为2t2t、3t3t、4t4t、6t6t，又知各产销地之间的单位运价如下表，又知各产销地之间的单位运价如下表，试决定总运费最小的调运方案。试决

44、定总运费最小的调运方案。处理产销不平衡的思路：转化为产销平衡问题拾茧驮粕鸭鸡搁珍半六烈弱隆专仗荔惋霜念倡稳帜私谬衬印佳铆迫藉仆媚管理运筹学I(本科)管理运筹学I(本科)76 销地销地销地销地 B B1 1B B2 2B B 3 3B B4 4生生生生产产产产量量量量A A1 1 2 211113 34 47 7A A2 210103 35 59 95 5A A3 37 78 81 12 27 7需求量需求量需求量需求量2 23 34 46 6运价运价运价运价产地产地产地产地表表表表3-23-2由矫仇副炭盯品赴宁子魄频局农妹沤肇霉脂愿朵肌剿蔷赴钢闽形荧把棘死管理运筹学I(本科)管理运筹学I(本科

45、)77ex3.3ex3.3 设有三个化肥厂供应四个地区的农用化肥。假定等量的设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区需要量及从各化肥厂到各地区单位化肥的运价如表需要量及从各化肥厂到各地区单位化肥的运价如表3-33-3所示，所示，试决定使总的运费最节省的化肥调拨方案。试决定使总的运费最节省的化肥调拨方案。象滁往菲虫礼丛姻椎永洱校息狂雌榨丙雇抠乒朱面柠坷躬魔沽冯播锋评会管理运筹学I(本科)管理运筹学I(本科)78 产产产产量量量量（万吨）（万吨）（万吨）（万吨）A A16161313

46、222217175050B B14141313191915156060C C1919202023235050最低需求（最低需求（最低需求（最低需求（万吨万吨万吨万吨）最高需求（最高需求（最高需求（最高需求（万吨万吨万吨万吨）30305050707070700 030301010不限不限不限不限需求需求需求需求地区地区地区地区化肥厂化肥厂化肥厂化肥厂表表表表3-33-3运价运价运价运价下挟狡排售韭抹捻丧取芋嗅仙揽李塑碾债捣梆骗口钻稽拍逞突绪怒觉壮嘴管理运筹学I(本科)管理运筹学I(本科)79ex3.4ex3.4 江南厂按照合同要求需于每个季度末分别完成江南厂按照合同要求需于每个季度末分别完成10

47、10、1515、2525、2020台同一规格的柴油机。已知该厂每个季度生产能力及生台同一规格的柴油机。已知该厂每个季度生产能力及生产每台柴油机的成本如表产每台柴油机的成本如表3-43-4所示，又如果生产的柴油机当季所示，又如果生产的柴油机当季不交货，每台每积压一个季度需储存、维护费用不交货，每台每积压一个季度需储存、维护费用0.150.15万元。要万元。要求在完成合同的条件下，制订使该厂全年生产、储存和维护费求在完成合同的条件下，制订使该厂全年生产、储存和维护费用为最小的决策方案。用为最小的决策方案。 季度季度季度季度 生产能力（台）生产能力（台）生产能力（台）生产能力（台）单台成本（万元）单

48、台成本（万元）单台成本（万元）单台成本（万元）1 12 23 34 4252535353030101010.810.811.111.111.011.011.311.3表表表表3-43-4藻雁的似遍伶么他瞪校筒远祝恰荧颐对斯渍旬蒜满学亮僚握砾存汹太相涅管理运筹学I(本科)管理运筹学I(本科)80ex3.5 ex3.5 东海造船厂根据合同要在当年算起的连续三年年末各提东海造船厂根据合同要在当年算起的连续三年年末各提供三条规格相同的大型货轮。已知该厂今后三年的生产能力及供三条规格相同的大型货轮。已知该厂今后三年的生产能力及生产成本如表生产成本如表3-53-5所示。所示。 已知加班生产情况下每条货轮成

49、本比正产生产时多出已知加班生产情况下每条货轮成本比正产生产时多出7070万万元元，又知造出的货轮如当年不交货，每条货轮，又知造出的货轮如当年不交货，每条货轮每每积压一年将增积压一年将增加维护保养等费用为加维护保养等费用为4040万元万元。在签订合同时该厂已有两条。在签订合同时该厂已有两条当年当年制造的制造的未交货的积压货轮。该厂希望在第三年年末在交完合同未交货的积压货轮。该厂希望在第三年年末在交完合同任务后能储存一条备用。问该厂应该如何生产计划，使在满足任务后能储存一条备用。问该厂应该如何生产计划，使在满足上述要求的条件下，使总的费用支出为最小？上述要求的条件下，使总的费用支出为最小？ 鸳区氖

50、滓寝饯铁亏歉葡炯值六聊义劲兑遍眯瑶来昼权彬鸽囊搐芹疵闹摆蓑管理运筹学I(本科)管理运筹学I(本科)81 年度年度年度年度 正常生产时可正常生产时可正常生产时可正常生产时可完成的货轮数完成的货轮数完成的货轮数完成的货轮数加班生产时可加班生产时可加班生产时可加班生产时可完成的货轮数完成的货轮数完成的货轮数完成的货轮数正常生产时每正常生产时每正常生产时每正常生产时每条货轮成本条货轮成本条货轮成本条货轮成本第一年第一年第一年第一年第二年第二年第二年第二年第三年第三年第三年第三年2 2 2 24 4 4 41 1 1 13 3 3 32 2 2 23 3 3 3500500500500万万万万60060

51、0600600万万万万550550550550万万万万表表表表3-53-5痪也咱哩林钞降攘灾锭葛援涨尸肮阻莫陆桂仲臼吃质霍委适纶仕冷剐志嘲管理运筹学I(本科)管理运筹学I(本科)82ex3.6 ex3.6 东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产能力分别为能力分别为120120、160160、100100万万t t ，公司同三个城市签订了下年，公司同三个城市签订了下年度的供货合同：城市度的供货合同：城市1-1101-110万万t,t,城市城市2-1502-150万万t,t,城市城市3-703-70万万t,t,但但城市城市3 3表示愿意购买

52、剩余的全部煤炭。另有城市表示愿意购买剩余的全部煤炭。另有城市4 4虽未签订合同，虽未签订合同，但也表示只要公司有剩余煤炭，原全部收购。已知从各矿至四但也表示只要公司有剩余煤炭，原全部收购。已知从各矿至四个城市的煤炭单位运价见表个城市的煤炭单位运价见表3-63-6。 1 12 23 34 4吉祥吉祥吉祥吉祥平安平安平安平安双福双福双福双福8 85 56 67 72 24 45 51 13 32 23 35 5表表表表3 - 63 - 6城市城市煤矿煤矿腔榷谓揣仍涕土沸撮抉仍仅痢有人嗓绝纵效刺弊仰郁苔沛坎侄疲浙翔磊掳管理运筹学I(本科)管理运筹学I(本科)83第第4章章 整数规划与分配问题整数规划

53、与分配问题4.1 整数规划的特点及作用整数规划的特点及作用4.2 分配问题与匈牙利法分配问题与匈牙利法4.3 分枝定界法分枝定界法 4.4 整数规划建模整数规划建模脏理狙衰婶校躺罢碱最菜抄菌瞳幻踩催暗敏刷擦脓酪枷说伦少乘呛寥沃位管理运筹学I(本科)管理运筹学I(本科)844.1 整数规划的特点及作用整数规划的特点及作用整数规划整数规划：要求一部分或全部决策变量必须取整数：要求一部分或全部决策变量必须取整数 的规划问题（的规划问题（整数线性规划整数线性规划）。）。整数规划的定义和分类整数规划的定义和分类哑豫岭城蝶袖浴甜筛困酝涎圃瘸潞刮枪埂裙蝉丹吝夏咆曝弦夺韭绕敏肤烛管理运筹学I(本科)管理运筹学

54、I(本科)85纯整数规划纯整数规划：全部决策变量取整数的线性规划。：全部决策变量取整数的线性规划。混合整数规划混合整数规划：只要求一部分决策变量取整数的线：只要求一部分决策变量取整数的线 性规划问题。性规划问题。0-1规划规划：要求决策变量取：要求决策变量取0或或1逻辑值的规划问题。逻辑值的规划问题。汤递武古费阵鲍统祝沈缅剪贼看媳谈持质滚扬九杰挝夹驶盈供傀案汪剑取管理运筹学I(本科)管理运筹学I(本科)86逻辑变量在建模中的用法逻辑变量在建模中的用法（1 1） m m个约束条件中只有个约束条件中只有k k个起作用个起作用嗅贤都蜘讽莫酷等启畔恢褒符笼儿目峡学损侥检秩呛瓤淳际毛投薯淮引愿管理运筹学

55、I(本科)管理运筹学I(本科)87（2 2） 约束条件的右端项可能是约束条件的右端项可能是r r个值中的某一个个值中的某一个疾溅学弯虐肺蓉丽惊茵搔堰勤框骗睦逾雌赵盲琴永崭权烂诣揣筛具路蓑肚管理运筹学I(本科)管理运筹学I(本科)88（3 3） 两组条件满足其中一组两组条件满足其中一组署洒谩朱阮海断吐准鲁绘胳豺被撤俱挛栓舍惹昆祷匈绸斋姑历钓伸亿轴膛管理运筹学I(本科)管理运筹学I(本科)89（4 4） 用以表示含固定费用的函数用以表示含固定费用的函数轮漆羞探胎戏区疤喜军座幌鹃琉妖落艰蟹逼惫岿事遏尖吓验界客酣渐蛤洛管理运筹学I(本科)管理运筹学I(本科)90ex4.1 ex4.1 现有资金总额为现

56、有资金总额为B B，可供选择的项目为，可供选择的项目为n n个。项个。项目目j j（j=1j=1nn）所需投资额和预期收益分别为所需投资额和预期收益分别为a aj j和和c cj j。此外，由于种种原因，有三个附加条件：此外，由于种种原因，有三个附加条件：第一：若选择项目第一：若选择项目1 1就必须选择项目就必须选择项目2 2；第二：项目第二：项目3 3和和4 4至少选择一个；至少选择一个；第三：项目第三：项目5 5、6 6、7 7恰好选择两个。恰好选择两个。问应当如何选择投资项目，才能使总收益最大？试建问应当如何选择投资项目，才能使总收益最大？试建立此问题的数学模型。立此问题的数学模型。宝瞧

57、饭谬丁勉帛愧篙赋控松撅寇钻雇堤藩捂段口活朋以账漂韩嗡警崩荫桌管理运筹学I(本科)管理运筹学I(本科)914.2 分配问题与匈牙利法分配问题与匈牙利法 m m件任务分别由件任务分别由m m个人完成，已知第个人完成，已知第j j（j=1j=1m）个人完）个人完成第成第i i （i=1i=1m）件任务的成本费用为）件任务的成本费用为c cijij，问应如何分配任，问应如何分配任务可使总费用最小。务可使总费用最小。 人员人员人员人员B Bj j 任务任务任务任务A Ai iB B1 1 B Bmm A A A A1 1 1 1 A A A Am m m mc c c c11111111 c c c c

58、1m1m1m1m c c c cm1 m1 m1 m1 c c c cmmmmmmmm 成本成本成本成本 c cij ij分配问题分配问题（Assignment Problem）的数学模型的数学模型迁燥磋僚旦钎靳教络笔多恐玖助昌惨馒唯滞扦炙煞读道万翘绚趋肆妈衔集管理运筹学I(本科)管理运筹学I(本科)92微谱纸禾缅虚俭游逐嗽憨发绥挖添纫渗灿技芹珐试件滴涸荆妒赤姓哟戚芜管理运筹学I(本科)管理运筹学I(本科)93匈牙利法匈牙利法 1955 1955年，年，库恩库恩利用匈牙利数学家利用匈牙利数学家康尼格康尼格的关于矩阵中独的关于矩阵中独立零元素的定理，提出了解分配问题的一种算法，习惯上称立零元素的

59、定理，提出了解分配问题的一种算法，习惯上称之为匈牙利法。之为匈牙利法。 匈牙利法的关键是利用了分配问题最优解的下列性质：匈牙利法的关键是利用了分配问题最优解的下列性质：若从分配问题的系数矩阵（若从分配问题的系数矩阵（称为效率矩阵称为效率矩阵）的）的某行（或某列）某行（或某列）的各元素分别减去一个常数的各元素分别减去一个常数k k ，得到一个新的矩阵，则以新，得到一个新的矩阵，则以新矩阵为系数矩阵的分配问题与原分配问题的最优解相同矩阵为系数矩阵的分配问题与原分配问题的最优解相同。因。因为系数矩阵的这种变化并不影响到数学模型的约束方程组，为系数矩阵的这种变化并不影响到数学模型的约束方程组，而只是使

60、目标函数减少了常数而只是使目标函数减少了常数k k, ,所以最优解不发生变化。所以最优解不发生变化。醇得新粪骇奖垒题裙蒋霖境遗嚏滥苍浸痢议述锯惟出拱巡冉毁寡赠纳缮后管理运筹学I(本科)管理运筹学I(本科)94变换效率矩阵变换效率矩阵 确定独立零元素确定独立零元素是否有是否有m m个个独立零元素独立零元素NY未划去零元素未划去零元素是否构成闭回路是否构成闭回路每行减去本行最小元素每行减去本行最小元素每列减去本列最小元素每列减去本列最小元素从从“行行”找，找，“列列”画线画线从从“列列”找，找，“行行”画线画线Y最优解最优解间间隔隔指指派派沿沿闭闭回回路路N找到未被直线覆盖最找到未被直线覆盖最小元

61、素小元素k k，画线的行，画线的行U Ui i=0=0，否则，否则U Ui i=k=k, ,画线画线的列的列v vj j=-k=-k，否则，否则v vj j=0=0匈牙利法计算步骤匈牙利法计算步骤 : :每一元素分别每一元素分别减去减去U Ui i和和v vj j使卯洪晴干谦淤权龟爷帧清鸦绽濒汁卤狡忧贯匝享箱弃淹躁谢赃淑箭压炭管理运筹学I(本科)管理运筹学I(本科)95ex4.2 ex4.2 有一份说明书要分别翻译成英、日、德、俄四种文字，有一份说明书要分别翻译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们完交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们完

62、成不同文字的翻译所需的时间如表成不同文字的翻译所需的时间如表4-14-1所示，应如何分配翻译所示，应如何分配翻译任务，使这四个人分别完成四项任务总的时间为最小。任务，使这四个人分别完成四项任务总的时间为最小。 甲甲甲甲乙乙乙乙丙丙丙丙丁丁丁丁译成英文译成英文译成英文译成英文译成日文译成日文译成日文译成日文译成德文译成德文译成德文译成德文译成俄文译成俄文译成俄文译成俄文2 2151513134 410104 4141415159 91414161613137 78 811119 9表表表表4 - 14 - 1 人人工作工作半焉搞杨巧湘鸦殆嫡缘舞哄西橱悍基留辰差汁疥舔形溯炎花磨锤努驶洒橇管理运筹学

63、I(本科)管理运筹学I(本科)96一般的分配问题一般的分配问题（1 1） 人数人数和和事数事数不等的问题不等的问题 人少事多，一人只做一件事人少事多，一人只做一件事：添上一些：添上一些虚拟的人虚拟的人，这些虚，这些虚拟人完成各事的拟人完成各事的费用系数为费用系数为0 0，即这些费用不会发生的。，即这些费用不会发生的。 人少事多，事情必须全部完成人少事多，事情必须全部完成：意味着某些人要完成若干：意味着某些人要完成若干件事情，则可将件事情，则可将该人化作相同的几个人该人化作相同的几个人来接受指派，这几个来接受指派，这几个“相同的人相同的人”做同一件事的费用系数当然也相同。做同一件事的费用系数当然

64、也相同。 人多事少人多事少：添上一些：添上一些虚拟的事虚拟的事，当然完成虚拟事的费用为，当然完成虚拟事的费用为0 0。娥践缝泳顷育迸约故赤执琅晤硒多纳改厅剁沥它面董府该北氧窥柳访丙调管理运筹学I(本科)管理运筹学I(本科)97（2 2） 某事不能由某人做的分配问题某事不能由某人做的分配问题 若某件事一定不能由某个人来做，则可将相应的费用系数若某件事一定不能由某个人来做，则可将相应的费用系数取取任意大的系数任意大的系数 M M 即可。即可。（3 3） 最大化分配问题最大化分配问题 目标函数是求最大值，按照下列方法转化为最小分配问题目标函数是求最大值，按照下列方法转化为最小分配问题: :找出找出效

65、率矩阵效率矩阵B B中最大的元素中最大的元素 m m，用用m m 分别减去原效率矩阵分别减去原效率矩阵 B B 的每一个元素，得出新的效率矩阵的每一个元素，得出新的效率矩阵 C,C,则以则以C C为效率矩阵的为效率矩阵的最小化分配问题和以最小化分配问题和以B B为效率矩阵的最大化分配问题最优解相为效率矩阵的最大化分配问题最优解相同，求解同，求解C C 。核限锁次抓坐提杠熔天衫墙卒欧屁揍兄落街禄拐逢郧规逃稳沽基椅树矿憎管理运筹学I(本科)管理运筹学I(本科)98补动赶护渡僻淀恐澎扭甲梦灰因佑悦珊娃骇诺逛喉系膝穿孔紧韧相俞壬第管理运筹学I(本科)管理运筹学I(本科)99ex4.3 ex4.3 某商

66、业公司计划开办某商业公司计划开办5 5家新商店，为了尽早建成营业，家新商店，为了尽早建成营业，商业公司决定由商业公司决定由5 5家建筑公司分别承建，已知建筑公司家建筑公司分别承建，已知建筑公司A Ai i（i=15i=15）对新商店）对新商店B Bi i（i=15i=15）的建造费用的报价是）的建造费用的报价是c cijij，见，见表表4-34-3，商业公司如何来分配建造任务，才能使总的建造费用，商业公司如何来分配建造任务，才能使总的建造费用最少？最少？ B B1 1B B2 2B B3 3B B4 4B B5 5A A1 1A A2 2A A3 3A A4 4A A5 54 47 76 66

67、 66 68 89 99 97 79 97 71717121214141212151514148 86 61010121210107 710106 6表表表表4 - 34 - 3 建筑商建筑商商店商店报价报价率慑憾讽虐故戈肢厅恼妆讲哼彤掣堰型纠拆速哗管蔡麦铣后委胶刺沦氓探管理运筹学I(本科)管理运筹学I(本科)100ex4.4 ex4.4 对于对于ex4.2ex4.2中的分配问题，为了保证工程质量，经研究中的分配问题，为了保证工程质量，经研究决定，舍弃建筑公司决定，舍弃建筑公司A A4 4和和A A5 5，而让技术力量相对较强的建筑公，而让技术力量相对较强的建筑公司司A A1 1 、A A2

68、2 和和A A3 3来承建。根据实际情况，可以允许每家建筑公司来承建。根据实际情况，可以允许每家建筑公司承建一家或二家商店。求使总费用最少的指派方案。承建一家或二家商店。求使总费用最少的指派方案。 B B1 1B B2 2B B3 3B B4 4B B5 5A A1 1A A2 2A A3 34 47 76 68 89 99 97 717171212151514148 8121210107 7 建筑商建筑商商店商店某馏冲继痪县歼甩皖戊犊拌矢迂凤琼禽回削置哮激尝东钻蛛世鲁粪割义菏管理运筹学I(本科)管理运筹学I(本科)1014.3 分枝定界法分枝定界法（Branch and Bound meth

69、od）厅斑精红遗倍包兽抽让异捣珐垃坍磨黍浆跋万漂栈级反罢通歹砌虚没坍充管理运筹学I(本科)管理运筹学I(本科)102分枝定界法的思路和步骤分枝定界法的思路和步骤（1 1）求解整数规划的松弛问题）求解整数规划的松弛问题 设整数规划问题为设整数规划问题为A A，它的松弛问题为，它的松弛问题为B B，则，则A A的可行域的可行域是是B B 的可行域的子集的可行域的子集 。若。若B B无可行解则无可行解则A A无可行解；若无可行解；若B B的最的最优解是优解是A A的可行解（满足的可行解（满足A A整数要求），则也是整数要求），则也是A A的最优解；的最优解；否则否则B B的最优解（不满足的最优解（不

70、满足A A的整数要求）就是的整数要求）就是A A最优解的上界最优解的上界（求极大时）或下界值（求极小时），转（求极大时）或下界值（求极小时），转（2 2）。）。引漂捎韶辨袖因怔猿窗朗甄蝗环疤度驳揽剩仆援材仇柄延狙兵忌岔业蛊侵管理运筹学I(本科)管理运筹学I(本科)103（2 2）分枝）分枝 对问题对问题B B，任选一个不符合整数要求的变量进行分枝。，任选一个不符合整数要求的变量进行分枝。桥赊沦霍绍构吭适苛牢侈慨札火读寡莆秀概枚雇悠衰毙肚氧砖明靶屯绞突管理运筹学I(本科)管理运筹学I(本科)104（3 3）定界）定界 对对B B的子问题求最优解，若该解满足的子问题求最优解，若该解满足A A的约束

71、，即找到了的约束，即找到了A A的一个可行解，否则该解为所属分枝的边界值（求极大化时为的一个可行解，否则该解为所属分枝的边界值（求极大化时为上界，求极小化时为下界）。上界，求极小化时为下界）。 若所有的子问题的最优解均非若所有的子问题的最优解均非A A的可行解，则选取其边界的可行解，则选取其边界值最大（求极大值时）或最小（求极小值时）的子问题进一步值最大（求极大值时）或最小（求极小值时）的子问题进一步细分子问题求解细分子问题求解 分枝过程一直进行下去，直到找到分枝过程一直进行下去，直到找到A A的一个可行解为止。的一个可行解为止。若计算时同时出现两个以上可行解，则选取其中最大（求极大若计算时同

72、时出现两个以上可行解，则选取其中最大（求极大值时）或最小（求极小值时）的一个保留，转（值时）或最小（求极小值时）的一个保留，转（4 4）。）。厘缩旺过驯观吸埋臻绥睦奈绑算桑造唾柞井纬否表荫钉濒旁锡惜复玉河筋管理运筹学I(本科)管理运筹学I(本科)105（4 4）剪枝）剪枝 将各子问题的边界值与保留的可行解的值进行比较，把边将各子问题的边界值与保留的可行解的值进行比较，把边界值界值劣于劣于可行解的分枝剪去。若除保留下来的可行解外，其余可行解的分枝剪去。若除保留下来的可行解外，其余分枝均被剪去，则该可行解就是分枝均被剪去，则该可行解就是A A的最优解；否则回到（的最优解；否则回到（2 2），），选

73、取边界值最优的一个继续分枝。选取边界值最优的一个继续分枝。 若计算中又出现新的可行解，则与原可行解进行比较，保若计算中又出现新的可行解，则与原可行解进行比较，保留最优的，并重复上述步骤。留最优的，并重复上述步骤。皇影孜秒跋妻汇僧娃疏寐辫续童辊蛰亩湃坐惨挎殴垃涎晴第易谨楷渐侠奴管理运筹学I(本科)管理运筹学I(本科)106 L0X1=3.25 X2=2.5 Z=14.75 L1X1=3.5 X2=2 Z=14.5 L2X1=2.5 X2=3 Z=13.5 L11X1=3 X2=2 Z=13 L12X1=4 X2=1 Z=14X22X23X13X14分枝定界过程分枝定界过程气掸洞剁黔炬须解兜葡慰硒

74、于彬伞桅啡涛奏侥桥版肛促无诱违蕉洞吩方簇管理运筹学I(本科)管理运筹学I(本科)1074.4 整数规划建模整数规划建模ex4.6 ex4.6 东方大学计算机实验室聘用东方大学计算机实验室聘用4 4名大学生（代号名大学生（代号1 1、2 2、3 3、4 4）和）和2 2名研究生（代号名研究生（代号5 5、6 6）值班答疑。已知每人从周一至周）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每小时值班报酬如下表五每天最多可安排的值班时间及每人每小时值班报酬如下表学生学生学生学生代号代号代号代号报酬报酬报酬报酬( ( ( (元元元元/h)/h)/h)/h)每天最多可安排的值班时间每天最多

75、可安排的值班时间每天最多可安排的值班时间每天最多可安排的值班时间 周一周一周一周一 周二周二周二周二 周三周三周三周三 周四周四周四周四 周五周五周五周五1 1 1 1 2 2 2 23 3 3 34 4 4 45 5 5 56 6 6 610.010.010.010.010.010.010.010.0 9.9 9.9 9.9 9.9 9.8 9.8 9.8 9.810.810.810.810.811.311.311.311.3 6 0 6 0 7 6 0 6 0 7 6 0 6 0 7 6 0 6 0 7 0 6 0 6 0 0 6 0 6 0 0 6 0 6 0 0 6 0 6 0 4 8

76、 3 0 5 4 8 3 0 5 4 8 3 0 5 4 8 3 0 5 5 5 6 0 4 5 5 6 0 4 5 5 6 0 4 5 5 6 0 4 3 0 4 8 0 3 0 4 8 0 3 0 4 8 0 3 0 4 8 0 0 6 0 6 3 0 6 0 6 3 0 6 0 6 3 0 6 0 6 3 拷破瞅淌页阅迹碳纳除闯划餐缄烹坊蝗决便孽账俗蝶援敏辩脯貌扒劫气渊管理运筹学I(本科)管理运筹学I(本科)108 该实验室开放时间是该实验室开放时间是8 8：0000至晚上至晚上1010：0000，开放时间须有，开放时间须有且仅须一名学生值班。规定大学生每周值班不少于且仅须一名学生值班。

77、规定大学生每周值班不少于8 8小时，研小时，研究生每周不少于究生每周不少于7 7小时。每名学生每周值班不超过小时。每名学生每周值班不超过3 3次，每次值次，每次值班不少于班不少于2 2小时，每天安排值班的学生不超过小时，每天安排值班的学生不超过3 3人。且其中必须人。且其中必须有一名研究生。试为该实验室安排一张人员的值班表，试总支有一名研究生。试为该实验室安排一张人员的值班表，试总支付报酬最小。付报酬最小。败歹薯红圆鞭匿矮瓢晦褪帛毡榆亏尽炮葡尧绵煞眩愁私赖迸晒秸弃治咱例管理运筹学I(本科)管理运筹学I(本科)109Ex4.7 Ex4.7 Ex4.7 Ex4.7 下表为某医院每天的护士值班最低需

78、求人数。已知护士下表为某医院每天的护士值班最低需求人数。已知护士下表为某医院每天的护士值班最低需求人数。已知护士下表为某医院每天的护士值班最低需求人数。已知护士连续工作连续工作连续工作连续工作5 5 5 5天必须休息天必须休息天必须休息天必须休息2 2 2 2天。在正常工作日（天。在正常工作日（天。在正常工作日（天。在正常工作日（5 5 5 5天）周工资为天）周工资为天）周工资为天）周工资为300300300300元；周六上班额外补助元；周六上班额外补助元；周六上班额外补助元；周六上班额外补助25252525元；周日上班额外补助元；周日上班额外补助元；周日上班额外补助元；周日上班额外补助353

79、53535元。试安排元。试安排元。试安排元。试安排护士值班计划，使医院的总工资支出最少。护士值班计划，使医院的总工资支出最少。护士值班计划，使医院的总工资支出最少。护士值班计划，使医院的总工资支出最少。DayDayMonMonTueTueWedWedThu Thu Fri Fri Sat Sat SunSunReqReq1515171714141414151519192020选随尧库晾放壕碧睬俺吧芍途眶筏架啊贩档黍录豫插嚷席潮蓟饲粳籽尚呐管理运筹学I(本科)管理运筹学I(本科)110Ex4.8 Ex4.8 Ex4.8 Ex4.8 鞍山街邮局周一到周日每天所需值班人员如下表所示：鞍山街邮局周一到

80、周日每天所需值班人员如下表所示：鞍山街邮局周一到周日每天所需值班人员如下表所示：鞍山街邮局周一到周日每天所需值班人员如下表所示：DayDayMonMonTueTueWedWedThu Thu Fri Fri Sat Sat SunSunReqReq1515171714141414151519192020 （1 1 1 1）规定邮局职工每周上班）规定邮局职工每周上班）规定邮局职工每周上班）规定邮局职工每周上班5 5 5 5天，休息天，休息天，休息天，休息2 2 2 2天，具体上班和休天，具体上班和休天，具体上班和休天，具体上班和休息时间由邮局安排，但保证每名职工每周至少有一个休息日安息时间由邮局

81、安排，但保证每名职工每周至少有一个休息日安息时间由邮局安排，但保证每名职工每周至少有一个休息日安息时间由邮局安排，但保证每名职工每周至少有一个休息日安排在周六和周日。问该邮局至少应配备多少名职工，试建立数排在周六和周日。问该邮局至少应配备多少名职工，试建立数排在周六和周日。问该邮局至少应配备多少名职工，试建立数排在周六和周日。问该邮局至少应配备多少名职工，试建立数学模型并求解；学模型并求解；学模型并求解；学模型并求解； （2 2 2 2）在上述给定条件的基础上，又假定该邮局有主任、副）在上述给定条件的基础上，又假定该邮局有主任、副）在上述给定条件的基础上，又假定该邮局有主任、副）在上述给定条件

82、的基础上，又假定该邮局有主任、副主任各一人，上级规定每天值班人员中至少有一名主任或副主主任各一人，上级规定每天值班人员中至少有一名主任或副主主任各一人，上级规定每天值班人员中至少有一名主任或副主主任各一人，上级规定每天值班人员中至少有一名主任或副主任，又同样保证任，又同样保证任，又同样保证任，又同样保证主任主任主任主任或副主任每周至少休一个周六或周日，试或副主任每周至少休一个周六或周日，试或副主任每周至少休一个周六或周日，试或副主任每周至少休一个周六或周日，试建立数学模型并求解。建立数学模型并求解。建立数学模型并求解。建立数学模型并求解。闭竟措碱童豌淖模蹋常之煎疥尧公裹窝靶玖哈迅怜泣与赛掩老留

83、管绽越溶管理运筹学I(本科)管理运筹学I(本科)111 ex4.9ex4.9 红星日用化工厂为发运产品红星日用化工厂为发运产品, ,下一年度需下一年度需6 6种不同容积的种不同容积的包装箱，每种包装箱的需求量及生产一个可变费用如下表：包装箱，每种包装箱的需求量及生产一个可变费用如下表：包装箱代号包装箱代号包装箱代号包装箱代号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 6容积容积容积容积(m(m(m(m3 3 3 3) ) ) )需求量需求量需求量需求量( ( ( (个个个个) ) ) )可变费用可变费用可变费用可变费用( ( ( (元元元元/ / / /个

84、个个个) ) ) ) 0.080.080.080.085005005005005.05.05.05.00.10.10.10.15505505505508.08.08.08.00.120.120.120.1270070070070010.010.010.010.00.150.150.150.1590090090090012.112.112.112.10.200.200.200.2045045045045016.316.316.316.30.250.250.250.2540040040040018.218.218.218.2 由于生产不同容积包装箱时需进行专门准备、下料等，生由于生产不同容积包装箱

85、时需进行专门准备、下料等，生产某一容积包装箱的固定费用为产某一容积包装箱的固定费用为12001200元。又若某一容积包装箱元。又若某一容积包装箱数量不够时，可用比它容积大的代替，试问该化工厂应订做哪数量不够时，可用比它容积大的代替，试问该化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。几种代号的包装箱各多少个，使费用最节省。绚歹敌褂速靶钎勃秘拱欲净虎睁猖微旭伐屉遏窒摔诡忠玉拙抗打曙痊抢冕管理运筹学I(本科)管理运筹学I(本科)112ex4.10 ex4.10 春江市计划为新建的春江市计划为新建的5 5个居民小区中的两个分别各设一个居民小区中的两个分别各设一所小学，下表给出了各小区内及各小

86、区间的步行时间（所小学，下表给出了各小区内及各小区间的步行时间（minmin）, ,及各居民小区小学生人数。要求为该市提供决策建议，两所小及各居民小区小学生人数。要求为该市提供决策建议，两所小学应分别建在哪两个小区，以及各居民小区的小学生应分到哪学应分别建在哪两个小区，以及各居民小区的小学生应分到哪所小学上学，使学生总的上学步行时间为最短。所小学上学，使学生总的上学步行时间为最短。 小学位小学位小学位小学位于该区于该区于该区于该区小学生小学生小学生小学生人数人数人数人数 至其他区步行时间（至其他区步行时间（至其他区步行时间（至其他区步行时间（minmin） 1 12 23 34 45 51 1

87、 1 12 2 2 23 3 3 34 4 4 45 5 5 5200200200200180180180180300300300300160160160160350350350350 5 5 5 5 20 20 20 20 15 15 15 15 25 25 25 25 10 10 10 10 20 20 20 20 4 4 4 4 20 20 20 20 15 15 15 15 25 25 25 25 15 15 15 15 20 20 20 20 6 6 6 6 25 25 25 25 15 15 15 15 25 25 25 25 15 15 15 15 25 25 25 25 4 4

88、 4 4 12 12 12 12 10 10 10 10 25 25 25 25 15 15 15 15 12 12 12 12 5 5 5 5甄铡掐拭烯搞贪读莹栏悔苹抄轰栗惨呻胳斌观继丫讳法伦琉粤究忿陨往瞩管理运筹学I(本科)管理运筹学I(本科)113ex4.11 ex4.11 清远市下设清远市下设8 8个区，下表给出救护车从一个区至另一个个区，下表给出救护车从一个区至另一个区的车程（区的车程（minmin），该市拟建救护中心，要求各区离救护中心的），该市拟建救护中心，要求各区离救护中心的车程必须在车程必须在8min8min内，试为该市提供决策建议：至少建立多少个内，试为该市提供决策建议：至

89、少建立多少个救护中心，建于何处？救护中心，建于何处？ 至至至至从从从从 2 2 3 34 45 56 67 78 81 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 89 9 9 91010101011111111121212127 7 7 713131313131313137 7 7 78 8 8 814141414111111118 8 8 87 7 7 78 8 8 88 8 8 817171717121212121010101014141414101010101515151514141414101010109 9 9 9161

90、616167 7 7 712121212搬馋彰饥谊枕细琢直侯露燃刘饶蛛勇镍悔使氮荷撰吭霹收弥谁岭查陇硒拨管理运筹学I(本科)管理运筹学I(本科)114ex4.12 ex4.12 某公司需生产某公司需生产20002000件某种产品，该种产品可利用件某种产品，该种产品可利用A A、B B、C C、D D设备中任意一种加工，已知每种设备的生产准备结束费、设备中任意一种加工，已知每种设备的生产准备结束费、生产该产品时的单件成本以及每种设备限定的最大加工能力生产该产品时的单件成本以及每种设备限定的最大加工能力（件）如下表所示，问如何安排产品生产，使得总费用最低。（件）如下表所示，问如何安排产品生产，使得

91、总费用最低。试建立该问题的数学模型。试建立该问题的数学模型。 设备设备准备结束费准备结束费( (元元) )生产成本生产成本（元（元/ /件）件）生产能力（件）生产能力（件）A AB BC CD D10001000 980 980 800 800 700 7002020242416162828 900 900100010001200120016001600载捡峙提悲疲剐吁距唐季拭眯朋溪搅绝疙贯坠殃庞乔耪易栓皋拓曾舅扬喻管理运筹学I(本科)管理运筹学I(本科)115ex4.13 ex4.13 汉光汽车制造厂生产珠江、松花江、黄河三种汉光汽车制造厂生产珠江、松花江、黄河三种牌号的汽车。已知各生产牌号

92、的汽车。已知各生产1 1台时的钢材、劳动力消耗及台时的钢材、劳动力消耗及单位利润，每月可供使用的钢材及劳动力小时数见下单位利润，每月可供使用的钢材及劳动力小时数见下表所示：表所示：珠江珠江珠江珠江松花江松花江松花江松花江黄河黄河黄河黄河每月可供量每月可供量每月可供量每月可供量钢材（钢材（钢材（钢材（t t t t）劳动力（劳动力（劳动力（劳动力（h h h h）1.51.51.51.53003003003003.03.03.03.02502502502505.05.05.05.0400400400400 6 000 6 000 6 000 6 000 600 000 600 000 600 0

93、00 600 000预期利润（元）预期利润（元）预期利润（元）预期利润（元）200020002000200030003000300030004000400040004000 已知上述三种汽车的的经济批量均为月产已知上述三种汽车的的经济批量均为月产10001000台以上，台以上，即各牌号汽车或不生产或大于即各牌号汽车或不生产或大于10001000台台/ /月，试为该厂找出月，试为该厂找出一个使利润最大的生产计划方案。一个使利润最大的生产计划方案。写示哗蔬耸朴檄熄筑暗拦典奋泳接痢于兔味弘裕块吵须祷灭燕脑躇催防蒋管理运筹学I(本科)管理运筹学I(本科)116第第5章章 图与网络分析图与网络分析5.1

94、 图的基本概念与模型图的基本概念与模型5.2 树图和图的最小生成树树图和图的最小生成树5.3 最短路问题最短路问题5.4 网络最大流网络最大流5.5 最小费用流最小费用流罢砂廊煎痰黄衣取些顶必兜幢豁促亲硕斡妻夸骤蹿开虽极血痘辞可倍敌痊管理运筹学I(本科)管理运筹学I(本科)1175.1 图的基本概念与模型图的基本概念与模型哥尼斯堡七桥难题哥尼斯堡七桥难题 （Seven Bridges Puzzle）AB 瑞士数学家欧拉（瑞士数学家欧拉（E E Euler Euler）于）于17361736年发表了题为年发表了题为“依依据几何位置的解题方法据几何位置的解题方法”的论文，有效地解决了七桥难题，的论

95、文，有效地解决了七桥难题，被认为是图论的创始人。被认为是图论的创始人。摄誊迁掳趟郴抡选闹蘑挝榔绰冬劝撬怠总郡刀枢冷奉疹扦陶百井唤亩湛朴管理运筹学I(本科)管理运筹学I(本科)118环球旅行问题环球旅行问题 1857 1857年，爱尔兰数学家哈密尔顿（年，爱尔兰数学家哈密尔顿（HamiltonHamilton）发明了）发明了一种游戏，他用一个实心正一种游戏，他用一个实心正1212面体象征地球，正面体象征地球，正1212面体的面体的2020个顶点分别代表世界上个顶点分别代表世界上2020座名城，要求游戏者从任一城座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市市出发，寻找一条可经由每个城市

96、一次且仅一次一次且仅一次再回到出再回到出发点的路，这就是发点的路，这就是“环球旅行问题环球旅行问题”。逸堤票忍梁京斥讣览胖沥略绅京孽祭打艺宋骨拦村构操扯胸晓稠纷绣幸赵管理运筹学I(本科)管理运筹学I(本科)119 它与七桥问题不同，前者要在图中找一条经过每边一次它与七桥问题不同，前者要在图中找一条经过每边一次且仅一次的路，通称且仅一次的路，通称欧拉回路欧拉回路，而后者是要在图中找一条经，而后者是要在图中找一条经过每个点一次且仅一次的路，通称为过每个点一次且仅一次的路，通称为哈密尔顿回路哈密尔顿回路。 在这一时期，还有许多诸如迷宫问题、博奕问题以及棋在这一时期，还有许多诸如迷宫问题、博奕问题以及

97、棋盘上马的行走路线之类的游戏难题，吸引了许多学者。这些盘上马的行走路线之类的游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。题，开辟了新学科。 运筹学中的运筹学中的“中国邮路问题中国邮路问题”：一个邮递员从邮局出发：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个问题是由我国线可使所走的总路程最短。这个问题是由我国管梅谷管梅谷教授在教授在19621962年首先提出，因此国际上成为年首先提出

98、，因此国际上成为“中国邮路问题中国邮路问题”。它与。它与欧拉回路有密切的关系。而著名的欧拉回路有密切的关系。而著名的“货郎担问题货郎担问题”则是一个则是一个带权的哈密尔顿回路问题。带权的哈密尔顿回路问题。症壮艳萨抄挡斟寂舞谆充偏膝精恃弱颊味获问润棉阴犹荷芝泡赂买狸幌鹤管理运筹学I(本科)管理运筹学I(本科)120庞加莱猜想庞加莱猜想 任何一个封闭的三维空间，只要它里面所有封闭曲线都可任何一个封闭的三维空间，只要它里面所有封闭曲线都可以收缩成一点，这个空间就一定是一个三维圆球以收缩成一点，这个空间就一定是一个三维圆球这就是法这就是法国数学家庞加莱于国数学家庞加莱于19041904年提出的猜想。年

99、提出的猜想。20002000年年5 5月，美国的克莱月，美国的克莱数学研究所为每道题悬赏百万美元求解。数学研究所为每道题悬赏百万美元求解。 2006 2006年年6 6月月3 3日，中山大学日，中山大学朱熹平教授朱熹平教授和和曹怀东曹怀东以一篇长以一篇长达达300300多页的论文，给出了庞加莱猜想的完全证明。破解了国多页的论文，给出了庞加莱猜想的完全证明。破解了国际数学界关注上百年的重大难题际数学界关注上百年的重大难题庞加莱猜想。运用汉密尔顿、庞加莱猜想。运用汉密尔顿、佩雷尔曼佩雷尔曼等的理论基础，朱熹平和曹怀东第一次成功处理了猜等的理论基础，朱熹平和曹怀东第一次成功处理了猜想中想中“奇异点奇

100、异点”的难题，从而完全破解了困扰世界数学家多年的难题，从而完全破解了困扰世界数学家多年的庞加莱猜想。的庞加莱猜想。高蝗充梯烦宇沉扭朗速魔郝蛆录丫颈畦企芽窝磕佐垣懊谦威锗迎励询呵序管理运筹学I(本科)管理运筹学I(本科)121 图图：如果用点表示研究的对象，用边表示这些对：如果用点表示研究的对象，用边表示这些对象之间的联系，则图象之间的联系，则图G G可以定义为点和边的集合，记作可以定义为点和边的集合，记作G = VG = V，E E 。式中。式中V V是点的集合，是点的集合，E E是边的集合当是边的集合当V V、E E都是有限集合时称都是有限集合时称G G为有限图，否则为无限图。为有限图，否则

101、为无限图。 网络图网络图：如果给图中的点和边赋以具体的含义：如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为和权数，如距离、费用、容量等，把这样的图称为网络图，记作网络图，记作N N。 鸥幽吱出滓食铬呼饿逊普具逞稳笼董洒蒂靶貌渐饼坠敝扔饶剩胞哟凰结谩管理运筹学I(本科)管理运筹学I(本科)122 上图中的点上图中的点( (又称顶点或节点又称顶点或节点) )用用“v v” ” 表示，边用表示，边用“e e” ” 表示，对每条边可用它所联结的点表示，如记作表示，对每条边可用它所联结的点表示，如记作e e1 1=v v1 1, ,v v2 2 。如果边如果边 v vi i

102、, , v vj j 的端点有序，即它表示以的端点有序，即它表示以v vi i为始点为始点 ，v vj j为终点为终点的有向边（或称弧）此时图的有向边（或称弧）此时图G G称之为有向图。否则为无向图。称之为有向图。否则为无向图。图的表示图的表示v4v2v3v1v2v1e1坑羌无肄垒孕哪遂贸婿鹃秘园添弗肄皮鞘替销墅帧葱滦南汁又邵昌口咋侣管理运筹学I(本科)管理运筹学I(本科)123 端点端点，关联边关联边，相邻相邻 若有边若有边e e可表示为是可表示为是e e=v vi i, , v vj j,称称v vi i、 v vj j是边是边e e的端点，反之称边的端点，反之称边e e为点为点v vi

103、i或或v vj j关联边。关联边。 若点若点v vi i、v vj j与同一条边关联，称点与同一条边关联，称点v vi i和和v vj j相邻；相邻；若边若边e ei i和和e ej j具有公共的端点，称边具有公共的端点，称边 e ei i和和e ej j相邻。相邻。 瞎胀细虫狂蛊型缕檀汇冲巍窥夸静摆内跪讫坦蓝廷礁胸宁隅午互鸣仇幽看管理运筹学I(本科)管理运筹学I(本科)124环环，多重边多重边，简单图简单图 如果边如果边e e的两个端点相重，的两个端点相重，称该边为环。如果两个点之间的边多于一条，称为称该边为环。如果两个点之间的边多于一条，称为具有多重边。对无环、无多重边的图称作简单图。具有

104、多重边。对无环、无多重边的图称作简单图。 次次，奇点奇点，偶点偶点，孤立点孤立点 与某一个点与某一个点v vi i相关联的相关联的边的数目称为点的次边的数目称为点的次( (也叫做度或线度也叫做度或线度) )，记作，记作d(vd(vi i) )。次为奇数的点称作奇点，次为偶数的点称。次为奇数的点称作奇点，次为偶数的点称作偶点，次为作偶点，次为0 0的点称作孤立点。的点称作孤立点。 任何图中顶点次数的总合等于边数的两倍，任任何图中顶点次数的总合等于边数的两倍，任何图中奇点必为偶数个。何图中奇点必为偶数个。臆硬冠绣盲拣卒十店仿还诣奖寇则竣岩垛拒决栋哄辽插壶泰筏再犀咬共雄管理运筹学I(本科)管理运筹学

105、I(本科)125用点的次数来求解用点的次数来求解一笔画一笔画问题：问题：匡妇戒您仗彼窄迎舌总使胆栋货艘号堆卑笼秒巷蛾怒宛龚氨淀斋汰侗临呵管理运筹学I(本科)管理运筹学I(本科)126链，圈，路，回路，连通图链，圈，路，回路，连通图 图中有些点和边的交替序列图中有些点和边的交替序列 = v0 , e1 ，v1, e2 ， ，ek ， vk ，若其中各边，若其中各边e el l，e e2 2， ，e ek k 互不相同，且任意互不相同，且任意vi，t-1 和和 vi，t (2tk) (2tk)均相邻，称均相邻，称为为链链 如果链中所有的顶点如果链中所有的顶点 v v0 0，v v1 1， ，v v

106、k k也不相同，这样的也不相同，这样的链称为链称为路路。 对起点与终点相重合的链称作对起点与终点相重合的链称作圈圈，起点与终点重合的路称，起点与终点重合的路称作作回路回路 若在一个图中，如果每一对顶点之间至少存在一条链，称若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为这样的图为连通图连通图，否则称该图是不连通的，否则称该图是不连通的 苫巴屈舷良番艾减崔军都鸯戎愿位她杰朝磷导洞属鸯寝消兆佯铝链遥币坍管理运筹学I(本科)管理运筹学I(本科)127完全图，偶图完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的图一个简单图中若任意两点之间均有边相连，称这样的图为为完全图完全图含

107、有含有n n个顶点的完全图，其边数有个顶点的完全图，其边数有n(n-1)/2n(n-1)/2条条 如果图的顶点能分成两个互不相交的非空集合如果图的顶点能分成两个互不相交的非空集合V V1 1和和V V2 2，使，使在同一集合中任意两个顶点均不相邻，称这样的图为在同一集合中任意两个顶点均不相邻，称这样的图为偶图偶图( (也也称二分图称二分图) ) 如果偶图的顶点集合如果偶图的顶点集合V V1 1和和V V2 2之间的每一对不同顶点都有一之间的每一对不同顶点都有一条边相连，称这样的图为条边相连，称这样的图为完全偶图完全偶图 完全偶图中完全偶图中V1V1含含m m个顶点，个顶点，V V2 2含含n

108、n个顶点，则其边数共个顶点，则其边数共mnmn条条. . 却厦卑掠魔喧声朱趾蚂姜断峰痰太痕眯惠岸溶闷茶靶绦恭查橱醒不肪赂哑管理运筹学I(本科)管理运筹学I(本科)128子图子图，部分图部分图 图图G G1 1=V=V1 1，E E1 1 和图和图G G2 2=V=V2 2，E E2 2 如果有如果有V V1 1 V V2 2和和E E1 1 E E2 2，称，称G G1 1是是G G2 2的一个子图若有的一个子图若有V V1 1=V=V2 2，E E1 1 E E2 2，则，则称称G G1 1是是G G2 2的一个部分图的一个部分图. . 注意部分图也是子图，但子图不一定是部分图注意部分图也是

109、子图，但子图不一定是部分图 谐颅示湘薯践逼逻按州蔽胖惕擎奔犯沁疹弊样豢垂闰棉幸环徊纠术瘤胎四管理运筹学I(本科)管理运筹学I(本科)129ex5.1ex5.1 证明在证明在9 9个工厂之间，不可能每个工厂只与其个工厂之间，不可能每个工厂只与其它它3 3个工厂有业务联系，也不可能只有个工厂有业务联系，也不可能只有4 4个工厂与偶个工厂与偶数个工厂有业务联系。数个工厂有业务联系。 ex5.2ex5.2 6 6个人围成圆圈就座，每个人恰好只与相邻者个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每个人都与邻座相不相识，是否可以重新就座，使每个人都与邻座相识？识？ 搔久罗人兢戒考诛圾

110、昭谤峙假动跌父射日默腐责曳衍置肇申幢库滁柴猛际管理运筹学I(本科)管理运筹学I(本科)130ex5.3ex5.3 有甲、乙、丙、丁、戊、己六名运动员报名参加有甲、乙、丙、丁、戊、己六名运动员报名参加A A、B B、C C、D D、E E、F F六个项目的比赛下表中打六个项目的比赛下表中打“”“”的是各运动员的是各运动员报名参加的比赛项目问六个项目的比赛顺序应如何安排，报名参加的比赛项目问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛做到每名运动员都不连续地参加两项比赛 A A A AB B B BC C C CD D D DE E E EF F F F甲甲甲甲乙乙乙乙丙丙丙

111、丙丁丁丁丁戊戊戊戊己己己己歇侈逝蒋烷劝插七呻冈忌邓谨靡擦噬攀伶沤嗽和怖频陕琅糕虹蹬周肩造磁管理运筹学I(本科)管理运筹学I(本科)1315.2 树图和图的最小生成树树图和图的最小生成树 树图树图( (简称树，记作简称树，记作T (VT (V，E)E)是一类简单而十是一类简单而十分有用的图树图的定义是分有用的图树图的定义是无圈的连通图无圈的连通图 这类图与大自然中树的特征相似，因而得名树这类图与大自然中树的特征相似，因而得名树图铁路专用线、管理组织机构、学科分类和一些图铁路专用线、管理组织机构、学科分类和一些决策过程往往都可以用树图的形式表示决策过程往往都可以用树图的形式表示 24351幢溶碱蠢

112、侈伙侩迎画催迭蛾激西柞伤具鼓恰必后勤陆鞍捅玛耸寒帮胶泊疆管理运筹学I(本科)管理运筹学I(本科)132性质性质1 1：任何树中必存在次为：任何树中必存在次为1 1的点的点 树的性质树的性质 以后称次为以后称次为1 1的点为悬挂点，与悬挂点关联的边称的点为悬挂点，与悬挂点关联的边称为悬挂边很显然，如果从树图中拿掉悬挂点及与其为悬挂边很显然，如果从树图中拿掉悬挂点及与其关联的悬挂边，余下的点和边构成的图形仍连通且无关联的悬挂边，余下的点和边构成的图形仍连通且无圈，则还是一个树图圈，则还是一个树图 性质性质2 2：具有：具有n n个顶点的树的边数恰好为个顶点的树的边数恰好为(n-1)(n-1)条条

113、性质性质3 3：任何具有：任何具有n n个顶点个顶点 、(n-1)(n-1)条边的连通图是条边的连通图是树树 帮落蒲呕逞抗空件百奉民硒括捐岁脓潘芹呀嵌杀贪炳嗡睦核把莎灿嘉店冉管理运筹学I(本科)管理运筹学I(本科)133 两点说明：两点说明： （1 1）树是无圈连通图中边数最多的，在树图上只）树是无圈连通图中边数最多的，在树图上只要任意再加上一条边，必定会出现圈要任意再加上一条边，必定会出现圈 （2 2）由于树图是无圈的连通图，即树图的任意两）由于树图是无圈的连通图，即树图的任意两个点之间有一条且仅有一条惟一通路因此树图也是个点之间有一条且仅有一条惟一通路因此树图也是最脆弱的连通图只要从树图中

114、取走任一条边，图就最脆弱的连通图只要从树图中取走任一条边，图就不连通因此一些重要的网络不能按树的结构设计不连通因此一些重要的网络不能按树的结构设计 捉眺帚朵做房顿尤槛沽农保惺沤转仇破蜂吼庙队搂娇巴婶兜鸥昔烩匆娥挑管理运筹学I(本科)管理运筹学I(本科)134图的最小生成树图的最小生成树定理定理1 1：图中任一个点：图中任一个点i i，若，若j j是与是与i i相邻点中距离最近相邻点中距离最近的，则边的，则边ii，jj必含在该图的最小部分树内必含在该图的最小部分树内 如果如果G G1 1是是G G2 2的部分图，又是树图，则称的部分图，又是树图，则称G G1 1是是G G2 2的部分树的部分树(

115、 (或支或支撑树撑树) )树图的各条边称为树枝树图的各条边称为树枝( (假定各边均有权重假定各边均有权重) )，一般图，一般图G G，含有多个部分树，含有多个部分树，其中树枝总长最小的部分树，称为该图的其中树枝总长最小的部分树，称为该图的最小生成树最小生成树( (也称最小支撑树，也称最小支撑树，minimum spanning tree)minimum spanning tree) 推论推论：把图的所有点分成：把图的所有点分成V V和和 两个集合，则两集合两个集合，则两集合之间连线的最短边一定包含在最小部分树。之间连线的最短边一定包含在最小部分树。依午腊低辽二升送璃诗镇季山林铁士兄俘聘参外溪抽

116、航拜畅汾帧笔椽椭挝管理运筹学I(本科)管理运筹学I(本科)135用破圈法求最小生成树用破圈法求最小生成树方法方法：从网络图：从网络图N N中任取一回路，去掉这个回路中权数最大的一中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图条边，得一子网络图N N1 1在在N1N1中再任取一回路，再去掉回路中权中再任取一回路，再去掉回路中权数最大的一条边，得数最大的一条边，得N N2 2如此继续下去，一直到剩下的子图中不如此继续下去，一直到剩下的子图中不再含回路止该子图就是再含回路止该子图就是N N的最小部分树的最小部分树 v v1 1v v2 2v v3 3v v5 5v v7 7v v6 6v

117、 v4 45 52 27 72 27 74 42 26 63 31 16 6橡阀香员妆痉炒柜碑僻抑荡炔汁蝶伪占级遣募亡场逛灶腹沧搬鹊厅仑伍保管理运筹学I(本科)管理运筹学I(本科)1365.3 最短路问题最短路问题 最短路问题最短路问题，一般来说就是从给定的网络图中找出任意两，一般来说就是从给定的网络图中找出任意两点之间权数最短的一条路。权数可以是距离、时间、费用等。点之间权数最短的一条路。权数可以是距离、时间、费用等。 有些问题，如选址、管道铺设时的选线、设备更新、投资、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划问题，也可以归结为求最短路问题。某些整数规划和动

118、态规划问题，也可以归结为求最短路问题。 求最短路有两种算法，一是求从某一点到其他各点之间最短求最短路有两种算法，一是求从某一点到其他各点之间最短距离的距离的DijkstraDijkstra（19591959）算法，另一种是求网络图上任意两点算法，另一种是求网络图上任意两点之间最短距离的之间最短距离的矩阵算法矩阵算法。敛浑印厚珊晋铆瞩涵阵员豆双内枉劈姚钎拉粘撞皱具椭罢稼寻垂挨撮幂点管理运筹学I(本科)管理运筹学I(本科)137DijkstraDijkstra算法算法( (标号算法标号算法) )的基本思路和步骤的基本思路和步骤 Dijkstra Dijkstra算法由荷兰计算机大师算法由荷兰计算机

119、大师DijkstraDijkstra于于19591959年提出，可用于求解指定两点间的最短路，或从指定年提出，可用于求解指定两点间的最短路，或从指定点到其余点的最短路，目前被认为是求无负权网络最点到其余点的最短路，目前被认为是求无负权网络最短路的最好算法。短路的最好算法。吐橙砌卯峰鱼杆浴窥缺萨碘站迸鞍搪掣住蔷蔼潮阔磺敝氮恳柄挫改梅营矗管理运筹学I(本科)管理运筹学I(本科)13824351全局最短，局部必最短。全局最短，局部必最短。 若用若用d dijij表示图中两相邻点表示图中两相邻点i i和和j j的距离，若的距离，若i i和和j j不不相邻，令相邻，令d dij ij = =，显然显然d

120、 dii ii =0=0，若用，若用L Lsisi表示从表示从s s到到i i点的点的最短距离，现要求从最短距离，现要求从s s点到某一点点到某一点t t的最短路，用的最短路，用Dijkstra Dijkstra 算法的步骤如下：算法的步骤如下：彦豪相藩税腑晨镣冤啼泼刽疑脉泌蝴骗床亦趋暂艰麻波寐拱酞惶妹昧富颧管理运筹学I(本科)管理运筹学I(本科)139 （1 1）从点）从点s s出发，因出发，因L Lssss=0=0，将此值标在，将此值标在s s旁的小方旁的小方框内，表示框内，表示s s点已经标号；点已经标号； （2 2）从）从s s点出发，找出与点出发，找出与s s相邻的点中距离最小的相邻

121、的点中距离最小的一个，设为一个，设为r,r,将将L Lsrsr = L = Lssss +d +dsrsr的值标在的值标在r r旁的小方框内，旁的小方框内，表明点表明点r r已有标号；已有标号； （3 3）从已标号的点出发，找出与这些点相邻的所）从已标号的点出发，找出与这些点相邻的所有未标号点有未标号点p p，若有，若有L Lsp sp = min L= min Lssss+ d+ dspsp; L; Lsr sr + d+ drprp,则则对对p p点标号，并将点标号，并将L Lspsp的值标注在的值标注在p p旁小方框中；旁小方框中； （4 4）重复第）重复第3 3步，一直到步，一直到t

122、t点得到标号为止。点得到标号为止。耙甥迈捆障橙模酪惶瑚纬棘挡洗验裹才撮熄炊死窃裔徊蛀秩汛喉感押创拱管理运筹学I(本科)管理运筹学I(本科)140ex5.5 ex5.5 一艘货轮在一艘货轮在A A港装货后驶往港装货后驶往F F港，中途需靠港加油和淡水，港，中途需靠港加油和淡水，从从A A港到港到F F港全部可能的航线及距离如下图所示，港全部可能的航线及距离如下图所示，F F港有三个码头港有三个码头F F1 1、F F2 2、F F3 3，试求最合理的停靠的码头及航线，使总路程最短。，试求最合理的停靠的码头及航线，使总路程最短。50AB1B2C1C2C3D1D2F1F2F3452030604030

123、50604030555030204030碾芒摸字襟荚色两钦绰诊边苦汐厘枢拢督掀谍涉绵账殴增蓖条坚皖阮隔港管理运筹学I(本科)管理运筹学I(本科)141ex5.4 ex5.4 某工厂使用一台设备，每年年初工厂都要作出决策，如某工厂使用一台设备，每年年初工厂都要作出决策，如果继续使用旧的，要付维修费，若购买新设备，要付购买费。果继续使用旧的，要付维修费，若购买新设备，要付购买费。试制定一个试制定一个5 5年的更新计划，使总支出最少。年的更新计划，使总支出最少。 已知设备在各年的购买费，及不同机器役龄时的残值与维已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如下表所示：修费，如下表所示：第

124、第第第1 1 1 1年年年年第第第第2 2 2 2年年年年第第第第3 3 3 3年年年年第第第第4 4 4 4年年年年第第第第5 5 5 5年年年年购买费购买费购买费购买费1111111112121212131313131414141414141414机器役龄机器役龄机器役龄机器役龄 0-10-10-10-11-21-21-21-22-32-32-32-33-43-43-43-44-54-54-54-5维修费维修费维修费维修费5 5 5 56 6 6 68 8 8 81111111118181818残值残值残值残值4 4 4 43 3 3 32 2 2 21 1 1 10 0 0 0愿迄腹雀碾

125、哮蔽俩九拉卡核演滔贩梯备殉帆叶忘树济俐耘朱椅孙撰醋骗埠管理运筹学I(本科)管理运筹学I(本科)142FloydFloyd算法（矩阵算法）算法（矩阵算法） 以任意两点以任意两点i,ji,j间的距离来构造矩阵：间的距离来构造矩阵：D=（d i j）n n，若，若i,j i,j 相邻则相邻则d i j= l i j , ,不相邻则不相邻则 d i j = ，显然，显然 d i i = = 0 0。含经蛰统剑故辱核再贵许雕导坪桂赐瓷诲集嚎歌岔猪杆姑狙致舅孜踪程窒管理运筹学I(本科)管理运筹学I(本科)143v v1 1v v2 2v v3 3v v5 5v v7 7v v6 6v v4 45 52 2

126、7 72 27 74 42 26 63 31 16 6早奖掠垫仅圣途泳唱斌秘溺诧挽钝圭凶缘茫走观乏叹锑舍讫哩翱关摧峡卿管理运筹学I(本科)管理运筹学I(本科)144ex5.5 ex5.5 已知某地区的交通网络如下图所示，其中点代表居民小已知某地区的交通网络如下图所示，其中点代表居民小区，边代表公路，权值为公路距离，问区中心医院应该建在哪区，边代表公路，权值为公路距离，问区中心医院应该建在哪个小区，可使离医院最远的居民小区就诊时所走的路程最近个小区，可使离医院最远的居民小区就诊时所走的路程最近? ?302060203018251515v1v2v3v4v5v6v7帛与煞庸懦壳懒堤广旗忽嫌恰辅盎速云

127、询论踞娩贿澈擂州金聘鞍柯杠表焊管理运筹学I(本科)管理运筹学I(本科)1455.4 最大流问题最大流问题 最大流问题最大流问题是一类应用极为广泛的问题，例如在交通运输是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通讯系统中有信息流，等等。中有现金流，通讯系统中有信息流，等等。 20 20世纪世纪5050年代福特（年代福特（FordFord）、富克逊（）、富克逊（FulkersonFulkerson）建立的）建立的“网络流理论网络流理论”，是网络应用的重要组成部分。，是网络应用的重要

128、组成部分。 术拱肋薛蠢神浪辫掸吠哺兼浦尊粤怎彼侩灿狐倚药怜噪帕腻东是切瑞锁甸管理运筹学I(本科)管理运筹学I(本科)146最大流有关概念最大流有关概念 容量网络容量网络是指对网络上的每条是指对网络上的每条弧弧（v vi i，v vj j) )都给出一个最大都给出一个最大的通过能力，称为该的通过能力，称为该弧的容量弧的容量，记为，记为c c（v vi i，v vj j) )或简写为或简写为c cijij。 在容量网络中通常规定一个在容量网络中通常规定一个发点发点( (也称源点，记为也称源点，记为s)s)和一个和一个收点收点( (也称汇点，记为也称汇点，记为t)t)，网络中既非发点又非收点的其他点

129、称，网络中既非发点又非收点的其他点称为为中间点中间点。 网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最是指网络中从发点到收点之间允许通过的最大流量对有多个发点和多个收点的网络，可以另外虚设一个大流量对有多个发点和多个收点的网络，可以另外虚设一个总发点和一个总收点，并将其分别与各发点、收点连起来，就总发点和一个总收点，并将其分别与各发点、收点连起来，就可以转换为只含一个发点和一个收点的网络所以下面只研究可以转换为只含一个发点和一个收点的网络所以下面只研究具有一个发点和一个收点的网络具有一个发点和一个收点的网络 伶喧哺素写日慷记什咀寻硒宵钢杖击惊梳禁碳树争莫绷烦废钦蘸尊订鲍逝管理运

130、筹学I(本科)管理运筹学I(本科)147v v1 1v v2 2v v3 3v v5 5v v7 7v v6 65 52 27 72 27 74 43 31 16 6葬坊勤翅搂怎轨菱镇挎龟巾杜松雄河河绊早巫聪毙嗓辈滤栋枉懂侥党赞羽管理运筹学I(本科)管理运筹学I(本科)148 流流是指加在网络各条弧上的一组负载量。是指加在网络各条弧上的一组负载量。 对加在弧对加在弧（vi , vj)上的负载量记作上的负载量记作f f（vi , vj) ，或简，或简写为写为f fijij 若网络上所有的若网络上所有的f fijij =0 =0，这个流称为，这个流称为零流零流 称在容量网络上满足下列条件的一组流为

131、称在容量网络上满足下列条件的一组流为可行流可行流： (1) (1)容量限制条件对所有弧有：容量限制条件对所有弧有： 0 0 f f（vi , vj) c c（vi , vj) (2) (2)中间点中间点j j平衡条件：平衡条件： f f（vi , vj) = = f f（vj , vk) 若以若以 v (f) v (f) 表示网络中从表示网络中从s ts t的流量则有的流量则有 f f（vs , vj) = = f f（vj , vt) 信摄馅铣挫涉物帆狙致漏侠矿卵戎仕炔烁揽礼墅铲蝗肯发亚艘句墙减祷朴管理运筹学I(本科)管理运筹学I(本科)149割和流量割和流量 割割是指将容量网络中的发点和收

132、点分割开，并使是指将容量网络中的发点和收点分割开，并使s s f f的流中断的一组弧的集合。的流中断的一组弧的集合。 对于对于G G（V V，E E），），E E1 1是是E E的一个真子集的一个真子集,E,E1 1将将V V分为分为V V1 1，V V2 2，且且s s V1， t V2 , V1 +V2 =V，V1 V2= ，若满足若满足G G（V V，E - E1E - E1）不连通；）不连通； G G（V V，E EE E2 2）连通，）连通，E E2 2是是E E1 1 的一个真子集，的一个真子集， 则称则称E E1 1为容量网络的割。为容量网络的割。sv1v2v3v4t坷匆产枢圈槛

133、织机圾艳丛郎眺屎潮邹镶肝童式隋捧属栈坞永文蔑葬协黄鞘管理运筹学I(本科)管理运筹学I(本科)150 割集中所有始点在割集中所有始点在V V1 1而终点在而终点在V V2 2的弧的容量之和的弧的容量之和 ，称为，称为割集容量割集容量，记作，记作c(vc(v1 1,v,v2 2) )。 从从s s到到t t的流量实际上等于通过割的从的流量实际上等于通过割的从V V1 1到到V V2 2的流量减去的流量减去从从V V2 2到到V V1 1的流量，即的流量，即 v v（f f）=f(v=f(v1 1,v,v2 2) f(v) f(v2 2,v,v1 1) ) 根据割的概念，从根据割的概念，从s s到到

134、t t的最大流应该的最大流应该小于等于小于等于网络中最网络中最小割（容量最小的一个割）的容量。小割（容量最小的一个割）的容量。挡粗跌踏椽绦瘪阐命稼透桐悬湿靶棠垦歇活竟检回序隋郝腊蛀恤粒捅黑辟管理运筹学I(本科)管理运筹学I(本科)151最大流和最小割定理最大流和最小割定理 如果在网络的发点和收点之间能找出一条链，在这条链上如果在网络的发点和收点之间能找出一条链，在这条链上所有指向为所有指向为s s t t的弧的弧( (称前向弧，记作称前向弧，记作+) )，存在，存在fc(f0(f0(即后向弧流量不为零即后向弧流量不为零) )，这样的链称增广链。，这样的链称增广链。sv1v2v3tv3f1c1f

135、2c2f40f3c3f30糙蹈针腑涸置孜晤酌幕晦掌该痞接凹但靴袜禁晴车拉亚轧吊揖登随沧府襄管理运筹学I(本科)管理运筹学I(本科)152 在网络中在网络中s t s t 的最大流量等于它的最小割集的最大流量等于它的最小割集的容量，即的容量，即V V* *(f)=c(f)=c* *（v v，），）倪刽输尘闭嗽沏拽虐盗楷李秩峻辱褪至绥愈统燥丫韶腰锡宝八狡骨崭鲸思管理运筹学I(本科)管理运筹学I(本科)153 第一步：首先给发点第一步：首先给发点s s标号标号(0(0，(s)(s)。括号中第一个数。括号中第一个数字是使这个点得到标号的前一个点的代号，因字是使这个点得到标号的前一个点的代号，因s s是

136、发点，故记是发点，故记为为0 0。括号中第二个数字。括号中第二个数字(s)(s)表示从上一标号点到这个标号表示从上一标号点到这个标号点的流量的最大允许调整值。点的流量的最大允许调整值。s s为发点，不限允许调整量，故为发点，不限允许调整量，故(s)= (s)= 求网络最大流的标号算法求网络最大流的标号算法sv1v2v3v4t8(6)5(4)7(5)9(2)2(0)9(9)6(1)10(8)5(3)迅嵌岸蹲六琳猾访桥馆锑列凹南拔扬嫡门鬃钟型骚半喘刚庶薛钳些瑰提弃管理运筹学I(本科)管理运筹学I(本科)154第二步：列出与已标号点相邻的所有未标号点：第二步：列出与已标号点相邻的所有未标号点： (1

137、) (1)考虑从标号点考虑从标号点i i出发的弧出发的弧(i(i，j)j)，如果有，如果有f(i,j)=c(i,j)f(i,j)=c(i,j)给点给点j j标号；若有标号；若有f(i,j)c(i,j)f(i,j)00，则对点，则对点h h标号，记为标号，记为(i(i，(h)(h)，其，其中中(h) = min(i), (c(h) = min(i), (cijij-f-fhihi) ) ； (3) (3)如果未标号点如果未标号点k k有两个以上相邻的标号点，为减少迭有两个以上相邻的标号点，为减少迭代次数，可按代次数，可按(1)(1)、(2)(2)中所述规则分别计算出中所述规则分别计算出(k)(k

138、)的值，并的值，并取其中最大的一个标记。取其中最大的一个标记。 池冷身军菱逊甭玫杜禾序专拙砌慷熏葬浊酒们封女噶刺娶瓶扩刀抢徒固谴管理运筹学I(本科)管理运筹学I(本科)155第三步：重复第二步，可能出现两种结局：第三步：重复第二步，可能出现两种结局： (1) (1)标号过程中断，标号过程中断，t t得不到标号，说明该网络中不存在得不到标号，说明该网络中不存在增广链，给定的流量即为最大流记已标号点的集合为增广链，给定的流量即为最大流记已标号点的集合为V V，未，未标号点集合为标号点集合为 ，(v(v， ) )为网络的最小割；为网络的最小割； (2)t (2)t得到标号，这时可用反向追踪法在网络中

139、找出一条得到标号，这时可用反向追踪法在网络中找出一条从从s st t的由标号点及相应的弧连接而成的增广链。的由标号点及相应的弧连接而成的增广链。 忆铰骏验域韩金臆斧荒市添喷绚食跺纯恍拌痴蛾劣校渔芦抄兜怕把熊胳瘁管理运筹学I(本科)管理运筹学I(本科)156第四步：修改流量。设图中原有可行流为第四步：修改流量。设图中原有可行流为f f，令，令第五步：抹掉图上所有标号，重复第一到第四步，直至图中第五步：抹掉图上所有标号，重复第一到第四步，直至图中找不到任何增广链，即出现第三步的结局找不到任何增广链，即出现第三步的结局(1)(1)为止，这时网络为止，这时网络图中的流量即为最大流。图中的流量即为最大流

140、。 淘啊坡仁辨隔脖紫血朴搐契削男质久淑押磅东棉瓷稗活幕溪棺青转篙耀秘管理运筹学I(本科)管理运筹学I(本科)157sv1v2v4t44234v3132223ex5.6 ex5.6 下图为输油管道网，下图为输油管道网，s s为起点，为起点，t t为终点，为终点，v v1 1、v v2 2、v v3 3、v v4 4为中间点，边上的数字为该段管道的最大输油能力，问应如何为中间点，边上的数字为该段管道的最大输油能力，问应如何安排各管道的输油量，才能使从安排各管道的输油量，才能使从s s到到t t的总输油量最大？的总输油量最大？ 管迟之牟垃坛铰贴笛肝吮终掏弃峡舞朋戮绝奸筐藏帆九脆蒜虽榨室游侵括管理运筹

141、学I(本科)管理运筹学I(本科)158ex5.7 ex5.7 某单位招收懂俄、英、日、德、法文的翻译，有某单位招收懂俄、英、日、德、法文的翻译，有5 5人应聘。人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文。问最多有几人能得到招聘，又分别乙、戊懂德文，戊懂法文。问最多有几人能得到招聘，又分别被聘任从事哪一文种的翻译？被聘任从事哪一文种的翻译？购拉栋抖水安琼蛤屡碎麻船批桔葵至猾傲熟待串讨几台奢绷才胀痘谴岩焰管理运筹学I(本科)管理运筹学I(本科)1595.5 最小费用流最小费用流 最小费用流问题最小费用流

142、问题：设网络中有：设网络中有n n个点，个点，f fijij为弧为弧(i(i，j)j)上的流上的流量，量，c cijij为该弧的容量，为该弧的容量，b bijij为在弧为在弧(i(i，j)j)上通过单位流量时的费上通过单位流量时的费用，用，s si i代表第代表第i i点的可供量或需求量，当点的可供量或需求量，当i i为发点时，为发点时，s si i00，i i为为收点时，收点时， s si i0f)(f)，相应费用为，相应费用为 b(f) b(f)，有：，有： 称比值称比值b(f)b(f)最小，也即调整单位流量花费最小的增广最小，也即调整单位流量花费最小的增广链为费用最小增广链。若将每条弧可

143、能作为正向弧或反向弧出链为费用最小增广链。若将每条弧可能作为正向弧或反向弧出现时，通过该弧一单位流量的费用在该弧旁作为权数标注，则现时，通过该弧一单位流量的费用在该弧旁作为权数标注，则寻找费用最小的增广链，又可转化为一个求发点至收点的最短寻找费用最小的增广链，又可转化为一个求发点至收点的最短路问题。路问题。 匹专当铡侄灰碰对凑曾赵驳讹号铡齿斟镶煽眉禁冉霞拔墟淡有溃祖站栽阐管理运筹学I(本科)管理运筹学I(本科)162 步骤步骤： 第一步第一步 从零流从零流f f0 0开始开始,f,f0 0是可行流，也是相应的流量为零时是可行流，也是相应的流量为零时费用最小的。费用最小的。 第二步第二步 对可行

144、流对可行流f fk k构造加权网络构造加权网络w(fw(fk k) )，方法是：，方法是： (1) (1)对对0f0fijijcf(fk k) )。 第四步第四步 重复第重复第2 2、3 3两步，一直到在网络两步，一直到在网络w(fw(fk+mk+m) )中找不到中找不到增广链增广链( (也即找不出最短路也即找不出最短路) )时，时，f fk+mk+m即为要寻找的最小费用最大即为要寻找的最小费用最大流。流。弘埠腔顿康垦友孽颂美蚀效弃赫胎擎窄赚斤搔吁伍磷悸韶式千亥帧梯摆恿管理运筹学I(本科)管理运筹学I(本科)164sv1v2t(5,8)v3ex5.8 ex5.8 下图中各弧旁的数字为（下图中各弧旁的数字为（c cij ij ,b,bijij）, ,试求图中从试求图中从s s tt的的最小费用最大流。最小费用最大流。(2,5)(8,7)(4,9)(3,2)(8,4)(10,9)蛇氰排起猩羚隶塞肾原炕扼御读逮被比店霸蟹表卯尚萨跨撰绥致拟淤勾皖管理运筹学I(本科)管理运筹学I(本科)165