第一章图与网络分析。
例1-1 试求图1-2中从到的最短距离。
图1-2 解：
1）给起始点标以（0,s），表示从到的距离为，为起始点。
2）这时已标定点的集合，未标定点的集合，弧集合，并有。
这样我们给弧的终点标以（2，1），表示从到的距离为2，并且在到的最短路径中的前面一个点是。
3）这时已标定点的集合，未标定点的集合，弧集合，并有。
这样我们给弧的终点标以（3，1），表示从到的距离为3，并且在到的最短路径中的前面一个点是；我们给弧的终点标以（3，3），表示从到的距离为3，并且在到的最短路径中的前面一个点是。
4）这时已标定点的集合，未标定点的集合，弧集合，并有。
这样我们给弧的终点标以（8，4），表示从到的距离为8，并且在到的最短路径中的前面一个点是。
5）这时，，弧集合，计算结束。此时，也即还未标号，说明从到没有有向路。
6）得到了一族最优结果。
根据终点的标号（8，4）可知从到的距离是8，其最短路径中的前面一点是，从的标号（3，3）可知的前面一点是，从的标号（2，1）可知的前面一点为，即此最短路径为。
同样，可得到从各点的标号得到从到的距离及从到的最短路径，由于没能标号，所以不存在从到的有向路。
例1-2 p209
图1-4 p210
图1-5 p212
例1-3 用破圈算法在图1-6（a）中，求一个最小生成树。p217
图1-6例1-6，p219
图1-8解：这是一个网络上最大流问题。而网络上最大流问题也是一个线性规划的问题。我们可以为此例建立数学模型。
设弧上的流量为，网络上的总的流量为，则有。
目标函数：
约束条件：1） 流量守恒条件：
2） 流量的可行条件：
满足守恒条件和流量可行条件的一组网络流称之为可行流，流量最大的可行流称之为最大流（即线性规划的最优解）。
一、 最大流问题的网络图论解法。
第一次迭代：
选择路为，弧的顺流容量为2，决定了，改进的网络流量如图1-12所示。
图1-12第二次迭代：
选择路为，弧的顺流容量为3，决定了，改进的网络流量如图1-13所示。
图1-13第三次迭代：
选择路为，弧的顺流容量为1，决定了，改进的网络流量如图1-14所示。
图1-14第四次迭代：
选择路为，弧的顺流容量为2，决定了，改进的网络流量如图1-15所示。
图1-15第五次迭代：
选择路为，弧的顺流容量为2，决定了，改进的网络流量如图1-16所示。
图1-16通过第五次迭代后，在图1-16中已找不到从发点到收点的一条路，中处的每一条弧顺流容量都大于零，运算停止，已得到此网络从到的最大流量，最大流量为10。由此可得到例1-6的最大流量图如图1-17所示。
图1-17例1-7，p225
图1-18解：我们用线性规划来求解此题，可以分两步走：
第一步，先求此网络图中的最大流量，这已在例1-6中建立了线性规划模型：
目标函数：
约束条件：3） 流量守恒条件：
4） 流量的可行条件：
第二步，在最大流量的所有解中，找出一个最小费用解，我们来建立第二步的线性规划的模型。
仍然设弧上的流量为，这时已知网络上的最大流量为，只要将例1-6的约束条件上，再加上总流量必须等于的约束条件：，即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用：，由此得到线性规划模型如下：
二、最小费用最大流的网络图论解法。
第一次迭代：
找到最短路（找最短过程省略），此路的总单位费用为3+3+4=10，弧的顺流容量为1，决定了，改进的网络流量图如图1-21所示。
图1-21第一次迭代后总流量为1，总的费用为。
第二次迭代：
找到最短路，此路的总单位费用为3+8=11，弧的顺流容量为1，决定了，改进的网络流量图如图1-22所示。
图1-22第一次迭代后总流量为3，总的费用为。
第三次迭代：
找到最短路，此路的总单位费用为3+2+3+4=12，弧的顺流容量为2，决定了，改进的网络流量图如图1-22所示。
图1-22第三次迭代后总流量为5，总的费用为。
第四次迭代：
找到最短路，此路的总单位费用为3+2+4+7=16，弧的顺流容量为1，决定了1，改进的网络流量图如图1-23所示。
图1-23第四次迭代后总流量为6，总的费用为。
第五次迭代：
找到最短路，此路的总单位费用为6+4+7=17，弧的顺流容量为3，决定了，改进的网络流量图如图1-24所示。
图1-24第五次迭代后总流量为9，总的费用为。
第六次迭代：
找到最短路，此路的总单位费用为6+5+4+7=22，弧的顺流容量为1，决定了，改进的网络流量图如图1-25所示。
图1-25第六次迭代后总流量为10，总的费用为。
因已找不到从到的每条弧容量都大于零的路了，故已求得最小费用最大流了，其最小费用最大流量图如图1-16所示。
例1-8 某设备有一个部件损坏，为进行抢修需突击制造一个铸件。该铸件利用木模造型，并需安放1型和2 型泥芯各四个，才能合箱浇铸。各项活动内容和计划时间见表1-1。
试求完成表上安排计划活动内容，即从收到图纸、木模开始算起到准备合箱，最少需多长时间。并计算网络图各项参数。
表1-1解：画出pert网络图，如图1-32所示。
图1-32图1-32中标在箭线上面的时间是完成各项活动的计划时间。为了对网络图进行分析，需要计算活动的：
1） 最早开始时间；
2） 最早结束时间；
3） 最迟开始时间；
4） 最迟结束时间。
5） 时差值。
1、活动的最早开始时间：是它的各项紧前活动最早结束时间中的最大一个值；活动的最早结束时间：是它的最早开始时间加上该项活动的计划时间的值。用公式表示时有：
本例中假定最初事件在时刻零实现，则有：
由此计算得到：
完成网络上各项活动的最短周期为：
2、活动的最迟结束时间：是它的各项紧后活动最迟开始时间中的最小一个，各项活动它的紧后活动的开始时间应以不延误整个工期为原则。活动的最迟开始时间：
是它的最迟结束时间减去该项活动的时间。用公式来表示有：
在本例中要求全部活动必须在17.5小时内结束，故有：
由此可计算得到：
事件①是整个网络的初始事件，以它为起点的有三项活动。由此事件①的最迟实现时间为：
3、时差。时差按性质可区分为活动的总时差和活动的自由时差。
（1）活动的总时差：是指网络上可利用时差的总数，可用下面的公式计算：
或。注意当某项活动利用了总时差后，将影响到与它有关联的其它活动的总时差。如。
实际上，7.5是上述三项活动可利用时差的总和，其中任何一项活动占用一部分后，将减少其它两项活动可利用的时差数。
2）活动自由时差，是指不影响它的各项紧后活动最早开工时间的可利用的时差，但规定这项活动必须在最早开始时间开工。用公式表示时，可写成：
或。例如，二、pert网络图的图上计算法。
直接在网络上计算时，在图上一般只标出，，和，如图1-33所示。因为，，和等参数可得用已标注的参数比较容易推出来。
图中标记为：
图1-33三、网络图的表上计算法。
直接在网络上计算优点是比较直观，但缺点是图上数字标注过多，不够清晰。对比较复杂的pert网络较多的利用**进行计算。**形式和计算过程有关数据列于下表。
几点说明：1） 表的第一栏填写网络图上的全部活动。从起点事件中编号最小的填写，对起点事件编号相同的活动，按终点事件由小到大填写；
2） 表第2栏填写各项活动的计划时间；
3） 依据公式计算得出第3,4两栏的数字，其中第4栏数字为第2,3两栏数字之和，计算时假定。
4） 依据公式计算第5,6两栏数字，其中第5栏数字为第6栏数字与第2栏数字之差。
计算时假定，并从表的最下端往上推算。
5） 表中第7栏数字为表中第6栏减去第4栏，或第5栏去第3栏数字之差；
6） 表中第8栏数字按公式：
或。计算得到。
例1-9 如果例1-8中损坏的设备为一台关键设备，为加快抢修进度，要求表1-8中列出的各项工作必须在15小时内结束。又已知为完成各项工作的最短需求时间（注：某些工作无法缩短时间，未列入）及分别比原计划缩短一个小时所增加的费用见表1-2，问应如重新安排计划，使全部工作在15小时内完成，而增加的费用又最少？
表1-2解：考虑这个问题的步骤可按下面框图的顺序进行。
第一步，本例中关键路线上的活动有四项：芯骨浇铸、芯骨装配、造2号芯与2号芯烘干，其中造2号芯缩短一小时增加费用最少。工期要求缩短工2.
5小时，该项活动最多可缩短3小时，但活动(4,7)的自由时差为2.1小时，即缩短2.1小时后将出现新的关键路线。
因此有，故决定将造2号芯时间缩短2.1小时，比原计划需增加的费用为：。
第二步，重复上述步骤，但注意到现在有两条关键路线，持续时间均为15.4小时，由于缩短芯骨装配时间增加的费用最少，故考虑缩短这项活动的时间，现工期尚要求缩短0.4小时，该项活动最多可缩短1小时，又整个工期缩短4.
5小时会出现新关键路线，由min=0.4，决定将芯骨装配时间缩短0.4小时，需增加额外费用。
高级运筹学题集
1.某厂有资金50 000元，生产由a和b合成的产品，同时表示为非线性优化的标准形式。a b单价分别为10 000和5 000元，设分别为a b的用量，产品产量可表示为。试写出产量最大化的数学模型并表示成非线性优化的标准形式，并判断是否为凸规划。2.假设有一百万元可以投资到三支 上，设随机变量表示投...
运筹学例题
例 1 20 生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表1 45所示，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存储费0.2万元，现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。表1 45例 1 ...
运筹学例题
一 绪论 例。一个班级的学生共计选修a b c d e f六门课程，其中一部分人同时选修d c a，一部分人同时选修b c f，一部分人同时选修b e，还有一部分人同时选修a b，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不连续参加考试，试设计一个考试日程表。二 法。例1.某...