第二十三讲 运筹学模型（7）——图论模型

yunjiang

　图论（GraphTheory）是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具，用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题.由于这种数学模型和方法直观形象，富有启发性和趣味性，得到了广泛应用。<></P>
　　这一节,所列问题都比较简单化和理想化,故不再步步写出建模过程.当然思路仍然是不变的.<></P>
　　<>
</P>

yunjiang

　<b>例1</b>(节目排序问题)一场文艺演出共有8个节目,全体演员中有10人须参加两个以上的节目演出,情况如表4－15中的√号所示,如演员1要参加三个节目A、B和H.若节目主办单位希望首尾两个节目为A和H,或为H和A,并且希望每个演员不连续参加两个节目的演出,试为主办单位安排一个节目顺序表.<></P>
<a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/02.htm#" target="_blank" ><FONT color=#0000cc>表4－15</FONT></A><></P><></P>
　　所谓开头为节目A（或H），结尾为H（或A），可以认定是一个图的出发点和结束点，由此考虑，以8个节目为顶点构图. 又每个演员不连续参加两个节目的演出,意味着八个顶点联线时要注意相邻顶点的演员关系.于是决定,若两个节目无同一名演员<P></P>
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image003.jpg">        <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image005.jpg"> <P></P>
    图4—4                        图4—5<P></P>
　　参加,则可连一条边,表示这两个节目可以紧排,否则不连边,便构成一个图模型（图4—4）.剩下的问题就应该是从A(或H)出发,寻求一条从A到H(或H到A)的,并且经过所有顶点的路径. <P></P>
<SUB>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image007.gif"> </SUB>的两个节目表为：                  <P></P>
　　方案Ⅰ：<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image009.gif"> </SUB><P></P>
<OBJECT codeBase=http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,29,0 height=250 width=350 classid=clsid27CDB6E-AE6D-11cf-96B8-444553540000><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM>                        <embed src="../images/flash/4-4-1.swf" quality="high" pluginspage="http://www.macromedia.com/go/getflashplayer" type="application/x-shockwave-flash" width="550" height="400"></embed></OBJECT>

yunjiang

<TABLE height=364 cellSpacing=0 cellPadding=0 width=476 align=center border=0><TR vAlign=top align=left><TD colSpan=2 height=347>　　方案Ⅱ：<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image011.gif"> </SUB><></P>
　　从而一共可有四种节目排序表供选择。
<OBJECT codeBase=http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,29,0 height=300 width=350 classid=clsid27CDB6E-AE6D-11cf-96B8-444553540000><ARAM><ARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM>                        <embed src="../images/flash/4-4-2.swf" quality="high" pluginspage="http://www.macromedia.com/go/getflashplayer" type="application/x-shockwave-flash" width="550" height="400"></embed></OBJECT></TD></TR><TR><TD vAlign=bottom align=middle height=15>　　　</TD></TR></TABLE>

yunjiang

<>　　<b>例2 </b>有八种化学药品A、B、C、D、P、R、S和T要放进贮藏室保管,出于安全原因,下列各组药品不能贮在同一室内:A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D.试为这八种药品设计一个使用房间数最少的贮藏方案.                           <></P>
　　从题设可见,总共有14个不配伍的药品时,要想从能够放入一室角度研究将是很困难的,因此本题与前两个题的构模思想和方法不尽相同.于是,自然想到可否逆其道而行之?即仍以8种药品为研究对象而做为顶点出现,连线方法则反之,    不能放入一室的连一条边,然后再去寻求没有连线的顶点,那么这些顶点（药品）便可以考虑放到一个室里贮藏,问题获得解决.图4－5是连线结果.<></P>
　　可见,T、C、P间无连线,A、B、S间无连线,R与D无连线,由此立刻得到一个贮藏方案:TCP;ABS;RD,故至少需要三个贮藏室.是否还有其它方案,读者可自行寻找.<P></P>
　　从本例可见,用图模型解决问题时,确定了顶点的代表物后,连边的方法各异.要根据问题的提法和要求具体问题具体对待,不可千频一律.</P>

yunjiang

<>　　<b>例3</b>（中国邮路问题）一个邮递员每次送信都从邮局出发，必须至少一次地走过他负责投递的范围的每一条街道，待完成任务后仍回到邮局。问他如何选择一条投递路线，使他所走的路程最短？<></P>
　　这个问题是由我国的著名数学家管梅谷教授在1962年首先提出的，因此被称为“中国邮路问题.”“中国邮路问题”本质上属于“一笔画”类问题，有一套成形的作法，本例中仅对其中较简单的部分给予较为直观的作法.<></P>
　　如图4－6。设邮递员从邮局A出发,沿方格形街路走遍能有街路后回到邮局.若方格形路的每条路长均为1(km),邮递员至少要走多少路程?<P></P>
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image013.jpg"><P></P>
　　图4—6<P></P>
　　易见,若视该路线图中各街路交点为顶点,相连接街路为边,邮路就成为一个赋权无向图,从而只要该图能一笔画出,则其总长度最短. <P></P>
　　那麽，一个图满足甚麽条件才能一笔画出呢？<P></P>
　　首先,如果这个图能够一笔画出,则只有两种情况出现,其一是从某一顶点出发走遍所有边一次而回到该顶点(图论中称为简单闭链),其二是从一顶点出发走遍所有边一次后到达另一顶点(图论中称为简单开链).<P></P>
　　其次,图中顶点可分为两种点,一种是过路点,另一种是出发点或结束点.所谓过路点是指沿某条边到达该点后,又从该点沿另一条边走向其它顶点,因此与过路顶点相连接的边的个数必为偶数,称这种点为偶点.非偶点的顶点称为奇点.<P></P>
　　最后,若一笔画问题是第一种情况,那么,其顶点均应为偶点.事实上,过路点必为偶点,而出发点和结束点重合,必亦为偶点,这时该图中无奇点.如果一笔画问题属于第二种情况,即首尾不重合,过路点仍必为偶点,而出发点与结束点不重合,则意味着出发点与结束点均应为奇点.这时,图中奇点个数应为2.于是欧拉给出以下的定理.<P></P>
　　一个连通图能够一笔画的充分必要条件是图中奇点个数为0或2.<P></P>
　　根据上一段介绍的一笔画原理,一个图能否一笔画,只要看图中顶点中的奇点个数即可确定.本例中要求从A出发返回到A,故其奇点个数应为零.但本例中奇点计16个,因此不可能一笔画出,即邮递员肯定要重复走某些街路.为此,考虑到图中各边长均相同,设法将奇点都变为偶点即能求得最短路程。将奇点全部变为偶点只须在奇点处加边,而怎样加边有多种作法,留给读者。</P>

yunjiang

<>　下面是统筹技术的一个应用事例。<></P>
　　<b>例4</b>（第五届北京高中数学知识应用竞赛题）机床的大修有如下的工作项目：拆卸③，清洗④，电器检修④，部件检查①，零件加工④，零件修理⑤，床身和工作台研合②，部件组装（不含电器）②，变速器组装①，试车③.<></P>
每个工作项目后面圆圈中给出的数字是完成该项工作所需的时间（小时）.首先的工作是“拆卸”,然后才能“清洗”和“电器检修”，这两项工作可独立地同时进行.“部件检查”要在“清洗”之后进行.然后才可以“零件加工”和“零件修理”,这两项工作也可以独立地同时进行.“变速器组装”和“床身和工作台研合”可以同时进行,但要等到“零件修理”和“零件加工”都完成后才能开始.“床身和工作台研合”后就可以直接进行“部件组装”，而“试车”要等其它工作都完成后才能开始。回答下列问题：<P></P>
　　1．画出工序的流程图，即用图表示出各项工作的衔接关系.<P></P>
　　2．假定大修期间没有耽误任何时间，并把开始拆卸时刻记为0，试问：大修完成的时刻最早是多少？<P></P>
　　3．在不影响最短时间完工的条件下，每个工作项目最早和最迟开工时间各是多少？<P></P>
<B normal">　　</B>1．关于工序流程图画法的说明<B normal"><P></P>
</B>　　按照工程网络图的严格画法，应有以下具体要求：<P></P>
　　（1）“拆卸”，“清洗”等这些具体工作称为工序，用实箭线“→”来表示。工序名称写在箭线上方，完成这项工序的时间写在箭线下面，箭线的方向代表了工序时间的流向.<P></P>
　　（2）工序之间交接处表示的圆圈称为事项或结点，用以标志前面工序的结束和允许后面工序的开始，是工序完成或开始的瞬间符号，具有承上启下、把工序衔接起来的作用.<P></P>
　　（3）若A工序必须在B工序完成之后才有条件进行，则称A是B的紧后工序，或称B是A的紧前工序.另外，同一对结点间不能表示两个及其以上个工序，如4－7（<I normal">a</I>）的画法是不允许的，为此引进了虚工序概念而将此表示式画成图4－7（<I normal">b</I>）的形式.<P></P>
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/image015.jpg"> <P></P>
                    图4—7<P></P>
　　其中的③到②的虚箭线即表示虚工序.虚工序仅用来说明一项工序与另几项工序的先后关系，其所需时间为零.图中的表示方法把三道工序关系画得非常清楚：A与B工序同时开工；C工序是A、B工序的紧后工序；工序A、B是C的紧前工序.<P></P>
　　有了这些画法规定，便容易画出本例第1问的各工序的衔接关系<a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/06.htm#" target="_blank" ><FONT color=#0000cc>图4—8</FONT></A>。</P><P><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_23/htm/sxjm23.files/2.gif"></P>

yunjiang

<>　　2. 关于并行工序问题的说明<></P>
　　在没有耽误任何时间条件下，大修完成的时刻最早是拆卸开   始的第20个小时，也即整个大修最低需要20小时.注意,这里并未将工序“电器检修”、“零件加工”和“变速器组装”的时间计9个小时计算在内，这是因为这三个工序分别与其它至少一个工序可同时进行（称它们为并行工序），故不影响总工期.这恰是统筹方法能大大提高工作效率的基本原因。<></P>
　　3.关于项目最早和最迟开工时间概念. <P></P>
　　（1）以下各工作项目（工序）不能提前也不能退后：<P></P>
　　0时“折卸”，3时“清洗”，7时“部件检查”，8时“零件修理”，13时“床身与工作台研合”，15时“部件组装”，17时“试车”.<P></P>
　　（2）以下各工序开工时间可早可晚，但有最早与最迟开工时间限制：<P></P>
　　“电器检修”最早3时与“清洗”同时开工，最迟在13时开工，否则要影响下一工序；“零件加工”最早8时与“零件修理”同时开工，最迟9时必须开工；“变速器组装”最早13时开工，最迟在16时开工.<P></P>
　　并行工序外的其它工序组成的工序路线是不能随意改动的，称之为关键路线，关键路线上的各工序也称为关键工序.本题中关键路线为<P></P>
　　①→②→③→④→⑥→⑧→⑨→11<P></P>
　　其上各工序为关键工序，计七道，所用总时间便是整个工程完工的最短时间.<P></P></P>

duanshumo

谢谢你的帖子

跳跳

谢了

coeeoc

谢谢