运筹学应用实例ppt课件

例如，有五名运动员参加游泳比赛。下表给出了每个运动员参加的比赛项目，并询问如何安排比赛，以便每个运动员可以不连续地参加比赛。如果在两个比赛中没有相同的运动员，把两个比赛紧密地联系在一起。为了解决这个问题，只需要找到一个包含所有顶点的基本链。例如：v4，v1，v2，v3，v5是一个初级链，相应的比赛有：100米自由泳，50米仰泳，50米蛙泳，100米蝶泳，200米自由泳。顶点v1、v2、v3、v4、v5用于表示五个事件，边用于连接表示两个事件的顶点。通过这种方式，可以获得下图。这个问题的解决方案并不是唯一的。线路铺设问题，下图是一个城镇的地图。现在管道将铺设在城镇的各个地方。给定每个点之间的铺设成本(单位：千元)，如何设计和铺设线路以使每个点的总铺设成本最小化？解决方案：找出所有方面都连接的方案，总成本最小。事实上，找出最小的树来确保所有点之间的连接，并且成本最小。总成本是31，000元，例如3。设备更新问题。一个单位使用一种生产设备。每年年底，单位领导必须决定是购买新设备还是在下一年继续使用旧设备。如果你购买新设备，你需要支付购买费用。如果你继续使用旧的，你必须支付一定的维护费。一般来说，维护费用随着设备的使用寿命而增加。根据以往的统计数据，每年年初的设备价格和不同使用寿命的年维护费用已经估算出来，分别见表1和表2。为了解决这个问题，建立了如下网络模型，并用最短路径法进行求解。订单：VI-第一年年初购买新设备，i=1，2，3，4，5，6v6指第五年年末。(vi，VJ)-新设备在第一年年初推出，并一直使用到第一年年初。Wij在第一年年初至第一年年初购买新设备的总成本，从v1到v6的最短路径是v1-v3-v6，最短路径长度是51。设备更新计划是在第一年年初购买一台新设备，使用到第二年年底，在第三年年初购买一台新设备，使用到第五年年底，总成本为51。房屋设计问题下图是一栋建筑的平面图。它要求从建筑内的每个房间都可以到达所有其他房间。墙上至少要打开多少扇门？试着给出一个开门的计划。以每个房间为顶点。如果两个房间相邻(有一个共同的隔墙)，用边连接相应的两个顶点，从而得到一个无向图，如图所示。从一个房间到另一个房间相当于从一个顶点到另一个顶点有一条链。解决方案：任何连通生成的子图都可以通过打开对应于其所有边的隔墙上的门来满足要求。为了最小化打开的门的数量，我们必须最小化这个连通子图的生成子图的边的数量，也就是说，找到图的最小生成树。开门方案，最小生成树，对应的开门方案如图所示，共10扇门。有六个住宅区v1、v2、v3、v4、v5和v6。计划建一所夜校。众所周知，每一点参加研究的人数是25、20、30、10、35和45。道路如图所示。试着确定学校位于哪个住宅区，以尽量减少学习者的总距离。(图中边缘旁边的图是路段的长度)。解决方法：首先，计算每个点对之间的最短路径。每一个学习者都应该选择最短的路径来形成最短的路径。最短距离矩阵D0和相应的中间点矩阵C0通过如下迭代获得：考虑每一点的学习者人数，将矩阵D6的每一行乘以每一点的学习者人数，得到：最短距离为520，即夜校应设置在v4点，相应的路径从C6获得。第五颅神经的眼支.v4: v1-v2-v3-v4v2.v4: v2-v3-v4v3.v4: v3-v4v5.v4: V5-v4v6.v4: V6-V5-v4.示例6:网络传输仓库和市场之间的产能如下表所示(产能为零意味着两点之间没有直线)。确定现有线路容量是否能满足市场需求。如果没有，应该修改哪条线路的容量。嘿。三个仓库由点A1、A2和A3表示；B1点、B2、B3和B4点代表四个市场；如果在仓库和市场之间有一条线，那么在相应的点之间连接一个弧，弧的容量就是线的容量。增加一个发布点S来连接S和Ai，具有Ai供应能力；增加一个收集点T来连接Bi和T，其容量就是对Bi的需求。获得以下网络。问题转化为寻找从s到t的最大流量的问题。因为最大流量是110，总市场需求是120，所以现有的线路容量不能满足市场需求。从上图可以看出，B3市场的需求无法满足，A3仓库的供应仍有盈余。因此，考虑将arcs (A3，B3)的容量增加到50，以满足市场需求。某个飞行队有五名飞行员和五名副驾驶。由于各种原因，一些飞行员和副驾驶不能同时飞行，而另一些可以，如下表所示，(*表示他们可以同时飞行)每架飞机需要一名飞行员和一名副驾驶同时航行，最多能航行多少架飞机？我应该如何安排飞行员和副驾驶？顶点A1、A2、A3、A4、A5代表五个共驱动器；B1、B2、B3、B4和B5代表5个积极驱动因素；如果飞行员和副驾驶能在同一飞机上飞行，则相应的点之间连接一条弧线，方向为从A到B；将起点S和终点T相加，得到下图。每个弧的容量是1。然后问题变成了寻找从s到t的最大流量的问题。Fmax=4，知道最多4架飞机可以同时航行。分配方案为：A2-B1；A3-B4；A4-B2；A5-B5，例9:桥梁切断。下图A、B、C、D、E和F分别显示了陆地和岛屿。如果河的两岸分别被敌对势力占领，问一下可以切断哪些桥梁来阻止敌对势力过河？陆地、河流和桥梁的示意图，解：a、b、c、d、e、f分别用一个点表示，它们之间有一个由桥梁连接的连接弧；弧的容量是两点之间的桥的数量；让我们设定一个方向，并得到如下的网络图：切割是一组弧分开A和f。如果你切断对应于切割的所有弧的桥，你可以切断A和f之间的线。切断对应于包含在最小切割中的弧的桥是切断A和f之间的线的桥的最少数量。从上图， 我们知道标记点是A、B、C，而D、E、F不能得到标记，所以我们知道对应于最大流量的最小切口是(A、E)、(C、D)、(C、F)。 因此，切断三座桥，可以防止对方部队过河。根据最大流量和最小切割定理，分隔A和F的最小切割能力等于从A到F的最大流量。例如，11:生产计划问题，工厂与客户签订合同，并从该月开始连续三个月在每个月底向客户供应特定产品。工厂三个月的生产能力、单位生产成本和客户需求如下表所示。据了解，每积压一个月的单位产品要支付2元的仓储费。在签订合同时，工厂有5种产品库存，工厂希望在第三个月底合同完成后再储存10种。当满足上述条件时，询问工厂如何安排生产计划，以使总成本最小化。1月，正常生产能力，加班生产能力，需求，正常单位产品生产成本，加班单位产品