《运筹学》课件 曾益 第6-9章 目标规划-决策分析

第六章目标规划线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。实际决策中，衡量方案优劣考虑多个目标生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。目标规划（GoalProgramming）在LP的基础上发展起来的解决多目标规划问题的最有效的方法之一。美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的《管理模型及线性规划的工业应用》一书中，首先提出的。

处理多种目标的关系，求得更切合实际要求的解只能处理一个目标目标规划线性规划可以在相互矛盾的约束条件下找到满意解满足所有约束条件的可行解找到的最优解是指尽可能地达到或接近一个或若干个已给定的指标值约束条件同等重要可根据实际需要给予轻重缓急或主次之分的考虑第6章内容提要6.1多目标线性规划6.2目标规划的数学模型6.3线形规划的解法6.4目标规划的应用6.1多目标线性规划

多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。

一、问题的提出产品资源甲乙现有资源

设备4324单位产品利润

54解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下：

maxZ=5x1+4x2

4x1+3x2≤24x1，x2≥0假设：该工厂根据市场需求或合同规定，希望尽量扩大甲产品的生产；减少乙产品的产量。这时又增加了二个目标，则可建立如下的模型：

maxZ1=5x1+4x2

maxZ2=x1minZ3=x24x1+3x2≤24x1，x2≥0

这些目标之间相互矛盾，一般的线性规划方法不能求解

加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。

优先等级法将各目标按其重要程度分成不同的优先等级，转化为单目标模型。

有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。二、求解思路加权系数法和优先等级法的结合对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；为区别各目标的重要程度，引入目标的优先等级和加权系数；对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件；从这组新的约束条件，寻找使组合偏差最小的方案。三、目标规划法

例2某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为2000，原材料2500公斤（每件产品耗原料2公斤），产品需求量为800件。要求制订一生产计划，使其尽可能达到以下三项指标：（1）满足需要量；（2）质量水平达到98%；（3）7000元的工时成本。正常生产加班生产转包合同临时工所需工时/件222.53成本费用元/工时101588质量水平99%98%95%90%生产条件约束:

欲达到的目标：

总工时限制：2000个；原材料限制：2500kg。满足需求800件；达到质量水平合格率98%；工时成本7000元。1）分析例2某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为2000，原材料2500公斤（每件产品耗原料2公斤），产品需求量为800件。要求制订一生产计划，使其尽可能达到以下三项指标：（1）满足需要量；（2）质量水平达到98%；（3）7000元的工时成本。2）组建约束确定决策变量：假设正常生产、加班生产、转包合同和雇临时工生产的量分别为x1，x2，x3和x4。确定约束：工时限制：2x1+2x2+2.5x3+3x4≤2000；原材料限制：2（x1+x2+x3+x4

）≤2500；非负限制：xi≥0（i=1，2，3，4）正常生产加班生产转包合同临时工所需工时/件222.53成本费用元/工时101588质量水平99%98%95%90%需要达到的目标：（1）满足需求量800件；（2）产品质量水平98%；（3）工时成本7000元。3）分析目标需求

三个目标要求，如何得到集中体现？是否需要建立三个目标函数？传统线性规划一般只建立一个目标函数，而有多个约束。→是否可以将三个目标以约束的形式表现出来，这样可解决多目标的问题？3）目标需求分析与目标向约束的转化需要达到的目标：→实际也变成了约束情况（1）满足需求量800件：在实际生产中，可能会出现两种情况，生产量不够800件或超过800件，则会产生不同的情况：0.98（x1+x2+x3+x4

）≤800；或0.98（x1+x2+x3+x4

）≥800；（2）产品质量水平98%：出现两种可能99%x1+98%x2+95%x3+90%x4≤98%（x1+x2+x3+x4

）；或

99%x1+98%x2+95%x3+90%x4

≥98%（x1+x2+x3+x4

）；

（3）工时成本7000元：可能出现两种可能：20x1+30x2+20x3+24x4≤7000；或20x1+30x2+20x3+24x4

≥7000。（1）满足需求量800件：两种情况不可能同时出现，化为标准型约束。0.98（x1+x2+x3+x4

）≤800；→0.98（x1+x2+x3+x4

）+S1=8000.98（x1+x2+x3+x4

）≥800；→0.98（x1+x2+x3+x4

）-S2=800（松弛变量S1和剩余变量S2中只可能出现一个）（2）产品质量水平98%：99%x1+98%x2+95%x3+90%x4≤98%（x1+x2+x3+x4）；→99%x1+98%x2+95%x3+90%x4+S3=98%（x1+x2+x3+x4）

99%x1+98%x2+95%x3+90%x4≥98%（x1+x2+x3+x4）；→99%x1+98%x2+95%x3+90%x4–S4=98%（x1+x2+x3+x4）（S3和S4中只可能出现一个）（3）工时成本7000元：20x1+30x2+20x3+24x4≤7000；→20x1+30x2+20x3+24x4+S5=700020x1+30x2+20x3+24x4≥7000。→20x1+30x2+20x3+24x4–S6=7000（S5和S6中只可能出现一个）如何综合考虑目标要求中可能会出现的两种情况？√√√√√√（1）满足需求量800件：归一化处理0.98（x1+x2+x3+x4

）+S1-S2=800（S1和S2中只可能出现一个，即其中至少有一个为零）（2）产品质量水平98%：99%x1+98%x2+95%x3+90%x4+S3–S4=98%（x1+x2+x3+x4

）（S3和S4中只可能出现一个，至少有一个为零）（3）工时成本7000元：

20x1+30x2+20x3+24x4+S5–S6=7000（S5和S6中只可能出现一个，至少有一个为零）如何综合考虑目标要求中可能会出现的两种情况？这里就在目标中引入了偏差量的概念，使多个目标要求转变成了约束→目标约束。S奇松弛变量，称为负偏差量（≥0）S偶剩余变量，称为正偏差量（≥0）目标要求转换成约束后的情形（1）满足需求量800件：归一化处理（2）产品质量水平98%（3）工时成本7000元

0.98（x1+x2+x3+x4

）+S1-S2=80099%x1+98%x2+95%x3+90%x4+S3–S4=98%（x1+x2+x3+x4

）

20x1+30x2+20x3+24x4+S5–S6=70000.98（x1+x2+x3+x4

）+d1-

-

d1+=8001%x1-3%x3-8%x4+d2-–d2+=020x1+30x2+20x3+24x4+d3-–d3+=7000di-，负偏差量di+，正偏差量目标约束4）相关概念引入

d+：正偏差量，可能实现值高于目标指标值的部分；

d-：负偏差量，可能实现值低于目标指标值的部分。实现目标的三种情况：（1）超过目标值

ｄk＋

>0，ｄk--＝0（2）达不到目标值ｄk＋

=0，ｄk-->0（3）刚好达到目标值

ｄk＋

=0，ｄk--＝0(d+*d—＝0)①

正、负偏差变量②

目标规划的约束形式

（1）绝对约束：也叫客观条件约束，为必须严格满足的约束。（2）目标约束：目标规划特有的约束，也叫软约束。（3）非负约束：要求所有决策变量和偏差量均≥0。如例2中的目标约束为：(1)满足需求800件；(2)达到质量水平合格率98%；(3)工时成本7000元；

(4)绝对约束

（5）非负约束:5）如何确定最终的目标方程？

设想：希望能尽量同时满足三个目标需求，即刚好达到800件产量，质量合格率刚好为98%，工时成本刚好为7000元。此时，所有的正偏差和负偏差量应均为0。但是，实际情况下，正偏差或负偏差量很难同时为0，即实际中不可能刚好同时达到目标要求。但是，应该尽力靠近目标要求，则需实际可能值应尽可能与目标要求值靠近，即使得所有目标约束的偏差量最小。由此，可建立新的目标函数：

原有目标变成了约束（目标约束），如何寻找新的目标方程？数学模型6.2目标规划的数学模型

目标函数的期望值每一个目标函数希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。偏差变量每个目标函数的期望值确定之后，目标的实际值和它的期望值之间就有正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标，它的取值不可能在超过期望值的同时，又没有达到期望值，所以在dk+和dk-中至少有一个必须为零。一、目标规划的基本概念

目标约束引入正、负偏差变量后，对各个目标建立的目标函数方程。原来的目标函数变成了约束条件的一部分，即目标约束(软约束)原来的约束条件称为系统约束(硬约束)。例1中，管理部门提出新要求：第一个目标是实现利润最大，计划部门规定利润目标是20；第二个目标是充分利用设备台时，但尽量少加班；第三个目标做如下规定，甲产品产量希望不少于3单位，乙产品产量比甲产品多2单位。对各目标函数引入正、负偏差变量：

5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2目标达成函数

各个目标函数引入正、负偏差变量，而被列入了目标约束条件。如何使各目标的实际值最接近于各自的期望值，构造一个新的目标函数以求得有关偏差变量的最小值。这个新的目标函数反映了各目标函数的期望值达到或实现的情况，故把这个新的目标函数称为目标达成函数。若要求尽可能达到规定的目标值，则正、负偏差变量dk+、dk-都尽可能最小，将dk+和dk-都列入目标函数中，即minSk=dk++dk-；若希望尽可能不低于期望值(允许超过)，则负偏差变量dk-尽可能的小，而不关心超出量dk+

，故只需将dk-列入目标函数，minSk=

dk-；若允许某个目标低于期望值，但希望不得超过期望值，则正偏差变量dk+

尽可能地小，而不关心低于量dk-，故只需将dk+列入目标函数，minSk=

dk+。优先等级和权数

目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。优先等级因子Pk是正的常数，Pk>>Pk+1。同一优先等级下的目标的相对重要性，赋以不同的加权系数w。例如第一个目标是实现利润最大，其优先级为P1

；第二个目标是充分利用设备台时，但尽量少加班，其优先级为P2

；第三个目标：甲的产量不少于3，乙的产量比甲多2，优先级为P3

。假设：甲产品产量希望不少于3单位的权数为3，乙产品产量比甲产品多2单位的权数为5。

minZ=P1d1-+P2(d2-+d2+

)+P3(3d3-+5d4-

)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0二、目标规划的数学模型

例某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。

小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,

xs

xa

xi

xs

xa

d约束条件绝对约束目标约束、绝对约束解最优最满意6.3目标规划的解法

只含有两个决策变量的目标规划模型

线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2

R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3

R2

R1)；如此继续，直到寻找到一个区域RK(RK

RK-1

…

R3

R2

R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。

一、目标规划的图解法

目标规划的图解法的步骤首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=20①4x1+3x2+d2--d2+=24②x1

+d3--d3+=3③-x1+x2+d4--d4+=2④x1,x2,dk-,dk+≥0⑤x1x2①d1+d1-②d2+d2-③d3+d3-④d4-d4+DABC满意解：x1=3,x2=15/4

Minz=P1d1++P2(d2-+d2+)+P3d3-

subjectto 2x1+x2≤11(1)硬约束

x1-x2+d1--d1+=0(2)

x1+2x2+d2--d2+=10(3) 8x1+10x2+d3--d3+=56(4)

x1,x2,di--di+>=0,i=1,2,3(5)例:线性规划模型为024A6810可行域x2非可行域12

B10

86

4

2x1满意解线段数学模型归结为：Minz=P1d1++P2(d2-+d2+)+P3d3-

subjectto 2x1+x2≤11(1)硬约束

x1-x2+d1--d1+=0(2)

x1+2x2+d2--d2+=10(3) 8x1+10x2+d3--d3+=56(4)

x1,x2,di--di+>=0,i=1,2,3ECDGd1-d1+d2+d3+d3-d2-D(10/3,10/3)G(2,4)P2(d2-+d2+)

P1d1+P3d3-

35用图解法求解下列目标规划问题36(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)046834622目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级Pk视为正常数(大Ｍ法

)正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形表检验数的计算完全相同，即

j=cj-CBiPj最优性判别准则类似于LP的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小二、目标规划的单纯形法

minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0划为标准型

maxZ=-P1d1--P2(d2-+d2+)-P3(3d3-+5d4-)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0cj

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

j00-P10-P2-P2-3P20-5P2020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--P1-P2-3P3-5P3+5P1+4P2-2P3+4P1+3P2+5P30-P10-2P20-3P30-5P3463-检验数

jd1-d2-x1d4--P1-P20-5P331000001-1005041-100-55001203001-1-440050100001-11-10+4P1+3P2+5P30-P10-2P2-5P1-4P2+2P3+5P1+4P2-5P30-5P313--cj00-P10-P2-P2-3P20-5P20

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

jd3+d2-x1d4-0-P20-5P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-10-P1000-1/5P2-4/5P2+4/5P2-2P2+9P3+P3-P3-3P3-5P3-10--检验数

jd3+d1+x1d4-000-5P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10-P1000-P2-P235/4P3+5/4P3-5/4P3-3P3-5P34-832/7cj00-P10-P2-P2-3P20-5P20

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

jx2d1+x1d4-000-5P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100-P100-P2-P2-5/3P3+5/3P326/3P3-35/3P3-5P3---3检验数

jx2d1+x1d3-000-3P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/700-P1000-P2-P2-3/7P3+3/7P3-3P3-26/7P3-9/7P36.4目标规划的应用经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？minZ=P1d1-+P2(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0

在目标管理中的应用

产品资源甲乙现有资源设备2010140售价108成本56最大需求量610x1x2x1=6x2=10③④d1+d1-d2+d2-CBD(6,5)满意解：x1=6,x2=5设备能力：需求：206+105=170，实际：140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%，甲产品的设备消耗降为20(1-18%)=16.4,

乙产品的设备消耗降为10(1-18%)=8.2。总利润：40单位甲：5单位乙：2生产部目标甲产品的产量：6，成本：5乙产品的产量：5，成本：6技术部目标甲产品的设备单耗：16.4乙产品的设备单耗：8.2销售部目标甲产品的销量：6，单价：10乙产品的销量：5，单价：8minZ=P2d1-+P1(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10④A(6,2)③d1+d1-d2+d2-E产品资源甲乙现有资源设备2010140售价108成本56最大需求量610降低设备消耗很困难，则调整经营目标的次序P1：充分利用设备能力，且尽量不超过140，P2：总利润不低于40如何安排生产？满意解：x1=6,x2=2利润指标：实际：56+22=34，期望：

40实现目标P1和P2，增加甲乙产品的单位利润:增长率(40-34)/34=18%产品售价由市场决定，为提高利润，应从降低成本入手：甲产品的成本由5降为10-5(1+18%)=4.12,

乙产品的成本由6降为8-2(1+18%)=5.63。总利润：40单位甲：5.88单位乙：2.26生产部目标甲产品的产量：6，成本：4.12乙产品的产量：2，成本：5.63技术部目标甲产品的设备单耗：20乙产品的设备单耗：10销售部目标甲产品的销量：6，单价：10乙产品的销量：2，单价：8某副食品批发店预测某商品今后4月的购进与售出价格如表：

在库存管理中的应用

月份1234成本(购价+库存)2.62.52.72.8售价2.92.73.13.3假设：该商品供不应求，最大销量受仓库容量限制；

正常库容3吨，机动库容2吨；月初批发销货，月中采购进货，进货所需资金完全来自销售收入；

1月初库存量2吨，成本2.5千元/吨，该月初无现金。经营目标：(1)每月都使用正常库容，尽量不超容；

(2)每月下旬都应储备1千元以备急用；

(3)4个月总盈利最大。决策变量：xj

第j月的采购量，yj第j月的销售量绝对约束条件各月销量约束：月初售货，各月销量不能多于其期初库存量。1月

y1≤22月

y2

≤2–y1+x1

→y1

+y2

–x1

≤23月

y3

≤2–y1

+x1

–y2

+x2

→y1

+y2

+y3

–x1

–x2

≤24月

y4≤2–y1

+x1

–y2

+x2

–y3

+x3

→y1

+y2

+y3

+y4

–x1

–x2

–x3

≤2各月采购量约束：每月采购量依赖月初的售货收入。1月

2.6x1

≤2.9y1→–

2.9y1

+2.6x1

≤02月–

2.9y1–2.7y2

+2.6x1

+2.5x2

≤03月

–

2.9y1–2.7y2–3.1y3

+2.6x1+2.5x2+2.7x3

≤04月–

2.9y1–2.7y2–3.1y3–3.3y4+2.6x1

+2.5x2+2.7x3+2.8x4≤0目标约束条件正常库容约束

1月2–y1+x1≤3→–y1+x1+d1-–d1+=12月–y1–y2+x1+x2+d2-–d2+=13月–y1–y2–y3+x1+x2+x3+d3-–d3+=14月–y1–y2–y3–y4+x1+x2+x3+x4+d4-–d4+=1各月储备金约束

1月

2.9y1-2.6x1

+d5-

–d5+=12月2.9y1+2.7y2

-

2.6x1-2.5x2+d6-

–d6+=1

3月

2.9y1+2.7y2+3.1y3

-

2.6x1-2.5x2-2.7x3+d7-

–d7+=14月

2.9y1+2.7y2+3.1y3+3.3y4-

2.6x1-2.5x2-2.7x3-2.8x4+d8-

–d8+=1总盈利约束：期望利润(3.3-2.5)×(3+2)×4=16

销售收入:2.9y1+2.7y2+3.1y3+3.3y4

销售成本:

2.5×2+2.6x1+2.5x2+2.7x3

2.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3+d9-–d9+=21目标达成函数

minZ=P1(d1+

+d2+

+d3+

+d4+

)+P2(d5-

+d6-

+d7-

+d8-

)+P3

d9-

图论第七章图与网络分析主要内容：7.1图的基本概念与基本定理7.2树和最小支撑树7.3最短路问题7.4最大流问题7.5最小费用流问题什麼是图？图论中所谓的图是由一些点(vertices)，和一些连接兩点的边(edges)所形成的7.1图的基本概念与基本定理

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡”七桥难题的论文；德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图所示图形的一笔画问题。Königsberg(Koenigsberg)哥尼斯堡，原为东普鲁士(Prussia)首府，现属俄罗斯(飞地)，名为加里宁格勒(Kaliningrad)现德国拜仁的哥尼斯堡哥尼斯堡七橋問題:要如何走過每座橋恰一次，再返回出發點？普瑞格爾河哥尼斯堡七橋問題可以看成是：對這樣一個封閉的圖形，是否可以一筆畫完成它並且回到原點數學家歐拉(Euler,1707-1783)於1736年嚴格地證明了上述哥尼斯堡七橋問題無解，並且由此開創了圖論的典型思維方式及論證方式即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。图论应用举例例如，在组织生产中，为完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设交通网络的合理分布等环游世界与Hamilton问题十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？Hamilton圈（环球旅行游戏）地图着色与四色问题任意一张地图，最少需要用多少颜色來着色，才能让相邻的两块涂上不同的颜色？1852年提出四色猜想1879年A.Kempe宣布证明了四色定理1890年Heawood发现Kempe的错误1976年美国数学家K.Appel及W.Haken在计算机的辅助下解決图论的应用广播频道与着色问题当两个广播电台距离太近时,若给它们相同的频道会产生干扰。如何设置每个电台的频道,使得它们既不相互干扰,又使频道总数最少?AB广播频道与着色问题图的点着色(Coloring)药品存放与无关集化学药品存放问题某些药品放置太近可能爆炸，有两个实验室，最多能有多少药品能放在一起碰!!药品存放与无关集配对问题与匹配(Matching)配对问题有一些机器人要分配任务，并不是所有机器人都能够完成所有的任务，要求每个机器人都要分配一项工作，怎么分？ABCcba信息流传与广播问题(Broadcasting)信息流传问题班上有一件事情要宣布，班长想打电話告訴全班。但若他一个个打似乎太慢了。假设一个班有五十人，打一通电话需要一分钟，那总共就需要四十九分钟。但若是他打了第一个电话后，便请第一个同学再打给別人；第二通电话打了之后，又再请第二个同学打给別人；依此类推，但问题是，也许某些同学沒有某些同学的电话，那么这时，怎样在最短时间內打完所有电话？5次6次计算机网络与连通度(Connectivity)问题计算机网络断线问题一公司内有多部计算机并连成网络,我们想知道其网络设计得好不好。考虑若有某线路毁损后,所有的机器是否仍可彼此互通?进一步,讨论该网络设计可保证在同时至多有几条线路毁损后仍互通?例6.1

图6.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆图6.2

例6.2

有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2

队，v2队战胜v3

队，v3队战胜v5队，如此等等。这个胜负情况，可以用图6.3所示的有向图反映出来图6.3v3v5v2v4v6v1

从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。

综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么，称为无向图，记作G=(V，E)，其中V表示图G

的点集合，E表示图G的边集合。连接点vi,vj

V的边记作[vi,vj]，或者[vj,vi]。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。例如.图6.4是一个无向图G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4图6.4图6.5

是一个有向图D=（V，A）其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}图6.5v7v5v3v4v2v6v1下面介绍一些常用的名词：一个图G或有向图D中的点数,记作P(G)或P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q。如果边[vi,vj]

E,那么称vi,vj

是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图6.4中的边[v3,v3]是环。如果两个端点之间有两条以上的边，那么称为它们为多重边，如图6.4中的边[v1

,v2],[v2

,v1]。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。

以点v为端点的边的个数称为点v的度，记作d(v),如图6.4中d(v1)=3，d(v2)=4,d(v3)=4,d(v4)=3。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。端点的度

d(v)：点v作为端点的边的个数奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=

，无边图v1v2v3v4v5v6v1v7v6v5v4v3v2V={v1,v2,v3,v4,v5,v6,v7}d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中v5

为悬挂点，v7为孤立点。

定理6.1

所有顶点度数之和等于所有边数的2倍。

证明：因为在计算各个点的度时，每条边被它的两个端点个用了一次。v1v5v4v3v2简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图（4）（6）（3）（3）（2）定理6.2

在任一图中，奇点的个数必为偶数。证明：设V1，V2

分别是图G中奇点和偶点的集合，由定理6.1，有因为是偶数，也是偶数，因此也必是偶数，从而V1

中的点数是偶数。图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。如:v0,e1

,v1

,e2

,v2，e3

,v3

,…,vn-1,en

，

vn;v0，vn分别为链的起点和终点

。记作（v0,v1

,v2，,v3

,…,vn-1,vn）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同,也称通路；圈：若v0≠vn则称该链为开链，否则称为闭链或回路或圈；简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点均不相同的圈；v1v2v4v3v5v6v7v5v9初等链:(v1,v2,v3,v6,v7,v5)初等圈：(v1,v2,v3,v5,v4,v1)简单链：(v1,v2,v3,v4,v5,v3)

简单圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)以后除特别声明，均指初等链和初等圈。v1v2v3v4v5不连通图v1v5v4v3v2v6连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。

连通图子图定义：如果V2

V1,E2

E1

称G2是G1

的子图；真子图：如果V2

V1,E2

E1

称G2

是G1

的真子图；部分图：如果V2=V1,E2

E1

称G2

是G1

的部分图或支撑子图；

导出子图：如果V2

V1,E2={[vi,vj]∣vi,vj

V2},称G2

是G1

中由V2

导出的导出子图。设G1=[V1,E1],G2=[V2,E2]G1G2真子图G3子图

部分图G4导出子图有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v；路：若有从u

到v

不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:

各顶点都不相同的路；初等回路:u=v

的初等路;连通图：

若不考虑方向是无向连通图;

强连通图：任两点有路;

基本概念点边,弧无向图链端点关联边有向图圈始点,终点多重边简单图初等链/圈次环多重图简单链/圈奇点,偶点连通图基础图悬挂点悬挂边不连通图路弧立点支撑子图回路

例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.

解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.

由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.

以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.

根据此图便可找到渡河方法.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)

将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.

从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.图的矩阵表示1.邻接矩阵Adjacencymatrix表示图中两点之间的相互关系两点之间有弧或边的，用1表示，否则用0表示，构成一个矩阵Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v6000110v1v2v3v4v5多重边v1v2v3v4v5v101100v210110v311001v401001v500110有向图v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v8000000000v9000010010矩阵A的元素全为0的行所对应的点称为汇点上图v8矩阵A的元素全为0的列所对应的点称为源点上图v1、v97.2树和最小支撑树一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。

例6.3

已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图6.2.1是一个不含圈的连通图，代表了一个电话线网。图6.2.1v6v3v4v2v5v1树及其性质树：既简单又很有用树：一个无圈的连通图组织结构图ManagerSubordSubord荣国公贾代善贾赦贾政贾琏贾珠贾宝玉贾环贾兰定理定理1：设G=(V,E)是一个树，p(G)>=2则G中至少有两个悬挂点。定理2：图G=(V,E)是一个树的充要条件是G不含圈，且恰有p-1条边。定理3：图G=(V,E)是一个树的充要条件是G是连通图，且q(G)=p(G)-1。定理4：图G=(V,E)是一个树的充要条件是任意两个顶点之间恰有一条链。推论从一个树中去掉任意一条边，则余下的图是不连通的。在树中不相邻的两个点间添上一条边，则恰好得到一个圈图的支撑树设图T=(V,E‘)是图G=(V,E)的一个支撑子图，如果T是一个树，则称T是G的一个支撑树定理5：图G有支撑树的充要条件是图G是连通的。破圈法：任取一个圈，从中去掉一条边，再对余下的图重复直到不再含圈时为止。破圈法避圈法在图中任取一条边，找到一条与之不构成圈的边，再找一条前两边不构成圈的边重复直到不再能进行为止取出的边数为p-1条避圈法最小支撑树问题给定图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图为赋权图wij称为边[vi,vj]上的权权是与边有关的数量指标，可以是距离、时间、费用等。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系广泛应用于解决工程技术及管理等领域的最优化问题最小支撑树问题就是赋权图上的最优化问题之一。设有一个连通图G=(V,E)，每一边e=[vi,vj]有一个非负权w(e)=wij(wij>0)如果T=(V,E’)，是G的一个支撑树，称E’中所有边的权之和为支撑树T

的权，记为w(T)如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树（最小树），即式中对G的所有支撑树T取最小最小支撑树问题就是要求G的最小支撑树。方法有二：避圈法Kruskal破圈法常见求赋权图的最小树。

例6.4某厂内联结六个车间的道路网如下所示，已知每条路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v1v2v4v6v3v5657152344避圈法求最小支撑树v1v2v4v6v3v515234i=1,E0=Φ。从E中选最小权边。依次选最小权边，并使之不构成圈。共选5条边v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3破圈法求最小支撑树任取一个圈，从中去掉一条权最大的边。依次重复，直到不含圈为止。v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3矩阵计算方法TTTTTTTTTTTTTTTTTTTTT矩阵计算结果一.引言最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。

7.3最短路问题例6.5已知如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从v1出发，通过这个交通网到达v8

，求使总距离最短的旅行线路。v1v7v2v5616321v32v4v610310v