下载文档原格式
(一）基本知识一、图1、图的概念：图是反应对象之间关系的一种工具。
图由点和线构成，一般称为点线图，点代表所研究的对象，线代表对象之间的关联性质。
注：在一般情况下，图中的点对应的位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系，并不重要。
2、图的分类：（1）无向图：图中线不带表示关联方向的箭头，称这样的线为边，这种图叫无向图。
（2）有向图：图中线带有表示关联方向的箭头，称这样的线为弧，这样的图叫有向图。
3、图的表示：G={V,E}其中V={V1,V2,……，Vn}为点集E={e1,e2,……，en}为边集（1）点的次数(度数）：与点Vi关联的边数称为点Vi的次数，记为d(Vi)（2）一些特殊的点：悬挂点：次数为1的点。
孤立点：次数为0的点。
奇点：次数为奇数的点。
偶点：次数为偶数的点。
（3）一些特殊的边相邻边：与同一顶点关联的两条边。
多重边：与共同的两个相邻点关联的边。
悬挂边：与悬挂点关联的边。
环：与同一个点关联的边4、连通图：任意两点之间可用至少一条链连接起来相通的图叫连通图。
（1）所有点的次数之和为边数的二倍：因为计算个点的次数时，每条边均用了两次。
（2）奇点的个数必为偶数：所有点的次数之和为偶数，故所有奇点的次数之和也为偶数，即奇点成对出现。
5、设G1={V1，E1},G2={V2，E2}（1）子图：若V2包含于V1，E2包含于E1,则称G2是G1的子图。
（2）部分图：若V1=V2，E1包含于E2，则G2是G1的部分图，即包含原图全部顶点的子图。
（3）零图：由许多孤立点构成的图。
（4）空图：顶点个数为0的零图,。
二、树1、概念：无圈的连通图为树v2 v3 v2 v3v1 v6 v5 v4 v1 v6 v5 v42、组成：（1）树枝：树的边称为树枝。
（2）树叶：次数为1的点称为树叶，如V1，V4。
3、树的性质：任何树必有树叶树中任意两点之间有且仅有一条链连接相通，任意去掉一条树枝该树就被分割成两个互不连通的子图。
运筹学最大流问题例题
以下是一个关于运筹学最大流问题的例题：
假设有一个有向图，有两个特殊的节点，分别是源点（S）和
汇点（T）。
图中还有一些其他的节点，表示各个任务或工作。
节点之间有一些带有容量限制的边，表示各个任务之间的关系。
假设需要将尽可能多的任务从源点发送到汇点，但要满足以下条件：
1. 每个任务只能由一个人来执行；
2. 每个人只能执行一个任务；
3. 每个任务只能在特定的时间完成；
4. 每个人只能在特定的时间段内工作。
问题：设计一个算法来确定可以完成的最大任务数。
解法：
1. 为了建立最大流问题的模型，我们需要将图中的节点和边进行转换。
首先，将源点和汇点分别用两个特殊的节点S和T
表示。
2. 对于每个任务节点，将其分解为两个节点v_in和v_out，以
表示任务开始和任务结束的时间点。
3. 对于每个容量限制的边(a, b)，我们将其转换为两条边
(v_out_a, v_in_b)和(v_out_b, v_in_a)，容量为边(a, b)上的容量
限制。
4. 然后，将所有节点和边加入到一个图中，并运用最大流算法（如Ford-Fulkerson算法）来找到从S到T的最大流。
5. 最终的最大流就是可以完成的最大任务数。
这是一个应用最广泛的最大流问题的例题，通过建立合适的模型，可以将实际问题转化为最大流问题，并通过最大流算法来解决。
大工19春《运筹学》在线作业123参考答案大工19春《运筹学》在线作业1数学规划的研究对象为()。
A.数值最优化问题B.最短路问题C.整数规划问题D.最大流问题正确答案:A运筹学的基本特点不包括()。
A.考虑系统的整体优化B.多学科交叉与综合C.模型方法的应用D.属于行为科学正确答案:D()是解决多目标决策的定量分析的数学规划方法。
A.线性规划B.非线性规划C.目标规划D.整数规划正确答案:C线性规划问题中决策变量应为()。
A.连续变量B.离散变量C.整数变量D.随机变量正确答案:A数学规划模型的三个要素不包括()。
A.决策变量B.目标函数C.约束条件D.最优解正确答案:D数学规划的应用极为普遍,它的理论和方法已经渗透到自然科学、社会科学和工程技术中。
T.对F.错正确答案:A存储论的对象是一个由补充、存储和需求三个环节构成的现实运行系统,且以存储为中心环节,故称为存储系统。
T.对F.错正确答案:A满足目标要求的可行解称为最优解。
T.对F.错正确答案:A运筹学是运用数学方法,对需要进行管理的问题统筹规划,为决策机构进行决策时提供以数量化为基础的科学方法。
T.对F.错正确谜底:A线性规划的建模是指将用语言文字描述的应用问题转化为用线性规划模型描述的数学问题。
T.对F.错正确答案:A在国际上,通常认为“运筹学”与“管文科学”是具有相同或附近涵义。
T.对F.错正确谜底:A整数规划问题中的整数变量可以分为一般离散型整数变量和连续型整数变量。
T.对F.错正确答案:B线性规划数学模型的三要素包括目标函数、约束条件和解。
T.对F.错正确谜底:B基本解的概念适用于所有的线性规划问题。
T.对F.错正确谜底:B线性规划问题的可行解是满足约束条件的解。
T.对F.错正确谜底:A存储策略是决定多长时间补充一次货物以及每次补充多少数量的策略。
T.对F.错正确谜底:A线性规划的最优解是指使目标函数达到最优的可行解。
T.对F.错正确答案:A线性规划的求解方法包括图解法、纯真形法、椭球法、内点法等。
§5.3 多阶段有向图中的最短路问题 5个部分：
{}{
}{}{}{}E D D D C C B B B A ,,,,,,,,,32121321 初态、终态、始态、末态、状态I
赋权多阶段有向图
图5.7
解： 8356676m i n ),(1=⎪⎭
⎪⎬⎫⎪⎩⎪⎨⎧+++=E C l ，31)(D C d =， 53264min ),(2=⎭
⎬⎫
⎩⎨
⎧++=E C l ，32)(D C d =， 85386min ),(3),(6min ),(211=⎭⎬⎫
⎩⎨⎧++=⎭
⎬⎫⎩⎨
⎧++=E C l E C l E B l ,21)(C B d =，
类似：125785min ),(7),(5min ),(212
=⎭⎬⎫
⎩⎨⎧++=⎭
⎬⎫⎩⎨⎧++=E C l E C l E B l ,22)(C B d =， 95481m i n ),(4),(1m i n ),(213=⎭⎬⎫⎩⎨⎧++=⎭
⎬⎫⎩⎨
⎧++=E C l E C l E B l ,.,)(213C C B d =
99812481min ),(8),(4),(1min ),(321=⎪
⎭
⎪
⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=E B l E B l E B l E A l ，1)(B A d =，
因此：最短路 .,,,,321E D C B A 路长：9
原则：最短路中每节为最短。
§5.4 摹矩阵 表上作业法
摹矩阵的乘规则：乘法=对应元素乘积的和；将乘积摹为求和，将和摹为取小 ),,(⊗⊕S 对应),,(⨯+R ⊕叫摹和，⊗叫摹积
零元素：z ：在非负数中为最小，加什么等于什么：{}a z a z a ==⊕,min 单位元素1：e ：乘什么等于什么：z z a z a =+=⊗；a e a e a =+=⊗ 半域),,(⊗⊕S ：不可逆
极小代数：)min,,(+R 代数；+∞=z ，0=e ；{}{}R R S =∞+= ⎥
⎦
⎤
⎢⎣⎡--=⎥⎦⎤⎢⎣⎡⊕⎥⎦⎤⎢
⎣⎡--723213426251753312对应元素取小（摹和） ⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⊗⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡574624361344348732513 {
}763,34,48min 633448=+++=⊗⊕⊗⊕⊗， 关于最长路问题：只需在最短路问题基础上作三点修改 一、)max ,,(+R 即),,(+∨R 是一个半域，也称为极大代数 {}
{}∞-= 实数R ，单位元素0，零元素∞- 二、摹乘法为：“相加取大”
三、零元素为∞-，而非∞+
也可规定路长为各边路长之积，且要求最小 可以在)min,,(⨯R 上计算就可以了。
因此多阶段有向图的最短路问题的求解过程可以采用：表上作业法
表5.1
添入参数，采用摹矩阵用算可得
表5.2
§5.5 决策数确定型动态规划 §5.5.1 Bellman 最优化原理 Bellman 最优化原理：
最优策略有以下的性质：无论其初态和初始决策如何，其今后的决策序列对以第一个决策所形成的状态所为初态的系统而言，必须构成最优策略。
§5.5.2 Bellman 递推公式
{}10,)(),(min )(1-≤≤+=+n j t f t x g x f j j （5.5）
如果终态只有一个元素v，还有
f
(
v
)
（5.6）n
（5.5）叫做Bellman递推公式，（5.6）是它的边界条件。
