文档介绍：(P56)
§ 最小费用流问题
最小费用流是指对于给定的流通网络图,例如在一个由道路网络构成的交通网络中,每一条弧(道路)都有一定的容量(通过能力)和权(单位费用),在流量既定的条件下,从某一结点(地方)到另一结点(地方)走怎样的路线才能使费用达到最小。
最小费用流问题具有以下特征:
(1) 网络中所有流起源于一个叫做源的结点;
(2) 所有的流终止于一个叫做收点的结点;
(3) 通过每一条弧的流只允许沿着弧的箭头方向流动,通过弧的最大流量取决于该弧的容量;
(4)网络中有足够的弧提供足够容量,使得所有在源中产生的流都能够到达收点;
(5)在流的单位成本已知的前提下,通过每一条弧的流的成本和流量成正比。
(6)目标是使得从源到收点的总费用最小。
最小费用问题可以归结为一个线性规划问题,设表示第I个结点流向第j个结点的最大允许流量(容量),如果没有线路到达,则容量为0;设表示第I个结点流向第j个结点的单位费用;设表示第I个结点流向第j个结点的流量,如果没有线路到达或没有流量通过,则流量为0;要求从第1个结点达到第n个结点的流量为k,那么最小费用流问题可以归结为如下线性规划问题:
例2:P69 2(1)
§ 最短路程问题
最短路问题是求给定网络上任意两点之间的最短距离及所走的路线。
最短路问题可以化为线性规划问题来求解。
最短路问题具有以下特征:
(1)在网络中选择一条路,起始于某源点,终止于目的地;
(2)连接两个结点的连线叫做无向弧(允许任一个方向行进),有向弧(只允许沿着一个方向行进);
(3)和每条弧相关的一个非负数,叫做该弧的长度或权;
(4)目标是寻找从源点到目的地的最短路。
1、有向赋权网络图的最短路程问题
如果在赋权网络图中规定两个结点之间弧的方向,称为有向赋权网络图。
设路径矩阵的元素只能取0或1,其中1表示从第I个结点到第j个结点是有通路的,0表示从第I个结点到第j个结点是没有通路的。
设路程矩阵的元素表示第I个结点通向第j个结点的路程。
设工作表的元素只能取0或1,其中1表示从第I个结点到第j个结点在最短路程上,0表示从第I个结点到第j个结点不在最短路程上。
最短路问题可以归结为如下线性规划问题:
例题:P70 3(1)
3、混合赋权网络图的最短路问题
如果在赋权网络图中,既有有向弧又有无向弧,则称为混合赋权网络图。
混合赋权网络图的求解方法与无向赋权网络图的求解方法完全一样。
§ 关键路线技术
关键路线技术也称为网络计划技术。关键路线技术指的是一套用于计划和控制项目实施的图形技术。
关键路线技术用网络图形描述出一项工程的全貌,并提示要将注意力集中在关键路线上,因为它决定了项目的完成时间。关键路线技术是管理中工作计划编制的有效工具,是一种安排时间的方法。
应用该技术的项目必须具有如下特点:
(1)工作或任务可以明确定义,它们的完成标志着项目的结束;
(2)工作或任务相互独立,即它们可分别开始、结束和实施;
(3)工作或任务有一定的顺序,它们必须按顺序依次完成。
应用关键路线技术可分为三个基本阶段:
(1) 绘制计划网络图:
,图中的弧(连线)表示工序,弧上的数字表示工序完成所需要的时间;结点表示某些活动的完成和另一些活动的开始时间,箭头指向表示工序的前后顺序。
(2) 进度安排阶段是按照时间要求具体安排工程中各项活动的进度,计算每项活动和整个工程的开始与结束时间,以及机动时间,并特别指出影响整个工程的关键活动。
一般地说,关键路线就是在连接开始时间地和终点时间地的所有路线中,由关键工序组成的路线,它是计划网络图中最长的路线。关键路线不唯一,在一个计划网络图中可存在多条关键路线,但关键路线的时间总长度一样。
(3) 进度控制
关键路线问题可以化成线性规划问题来求解。
设工序矩阵的元素只能取0或1,1表示第个结点到第个结点存在工序,0表示从第个结点到第个结点不存在工序。
设工期矩阵的元素表示第个结点到第个结点的工序需要的完工时间
设工作表的元素只能取0或1,1表示从第个结点到第个结点的工序在关键路线上,0表示从第个结点到第个结点的工序不在关键路线上。由工序限制可知,工序矩阵的元素必须大于等于工作表的元素。