*§5最小费用最大流问题解：我们用线性规划来求解此题，可以分两步。第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。第二步，在最大流量F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：仍然设弧（vi,vj）上的流量为fij，这时已知网络中最大流量为F，只要在例6的约束条件上，再加上总流量必须等于F的约束条件：f12+f14=F，即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用。*§2最短路问题（0,s）V1（甲地）1517624431065(13,3)V2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)*§2最短路问题例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118*§2最短路问题解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6§2最短路问题把所有弧的权数计算如下表：*123456116223041592162230413172331417235186*§2最短路问题把权数赋到图中，再用Dijkstra算法求最短路。v1v2v3v4v5v6162230415916223041312317181723§2最短路问题*§2最短路问题*§2最短路问题*§2最短路问题*§2最短路问题**§2最短路问题V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)标号如下图所示：§2最短路问题因此，v1到v6的距离是53，最短路径有两条：v1→v3→v6或v1→v4→v6。也就是说第一个方案为第1年初购置新设备使用到第2年底（第3年初），第3年初再购置新设备使用到第5年底（第6年初）。第二个方案为第1年初购置新设备使用到第3年底（第4年初），第4年初再购置新设备使用到第5年底（第6年初）。这两个方案使得总费用最小，均为53。**§3最小生成树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)*§3最小生成树问题给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。图11-12(a)(b)(c)*§3最小生成树问题一、求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否