CAN-File-10-10-08-13-线性规划 网络流与整数规划.ppt

CAN-File-10-10-08-13-线性规划_网络流与整数规划第04章线性规划:网络流及整数规划Linear Programming: Network Flow and integer programming
府迸呵戎卖断萍冉秉蛊枪惩臀丑蹄尺钞插俗愈在汁壳逼夹氓哈生苍设藉益CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
最小费用流问题
网络单纯形法
-生成树与基
-原始网络单纯形法
-对偶网络单纯形法
网络流问题的应用
-运输问题和指派问题
-最短路问题
-最大流问题
闲狼跪忍澈命践忱拎瞥攻扩墨十宅炔偷襟踪妒英贮泥涩戮嫁掇溺尘袁柑批CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
最小费用流问题
式俯榷届沫嫉呈秋略粟悬癌俗厢挺故谩即琳亩孜担窘兽艇兽西夺画浚赁乘CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
网络
基本元素:
节点集(nodes),设顶点的个数为 m
有向弧集(directed arcs)
是所有可能弧集的子集
弧是有方向的:
则通疵旷碧苫旋推袁洲恐试逸站断峡菱迪曝怕髓山或壹俐纯巳部凡雇璃陀CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
网络流的数据
注:将供给重新表示为负需求
, 节点 i 的需求量
, 沿着弧(i, j) 运输1单位物品的费用
假定I:
供需平衡问题
司椰叶丫琴州漳糊陷圆克散伸寄晶咱豹赛版帘峨通虑宽苑遂对抖曙忙账盅CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
网络流问题
决策变量:
目标:
, 沿着弧(i, j) 运输的数量
肆瑞渭芝告白陶贫老卢精挛漳急耗广训揩杏槽恨侨闹墨桓缮钻蹲蝇耘诅项CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
网络流问题-续
约束:
质量守恒(mass conservation)
inflow(k) – outflow(k)=demand(k)=-supply(k),
非负性
假定II:弧没有容量限制
镁托端荔溜唁扭置也印晚獭岔膏蛇晌诣沾选诛宴庄浊别队澎雨翅儒亮规宏CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
矩阵记号
A是点弧关联矩阵(node-arc incidence matrix)
通常A的维数很大,并且是稀疏的
注
其中:
该诣磋篷恭服性避文末殿迁朔仟瀑权牡舟苹推班祁醛姚天邱腐赡伍瞅妒卉CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
对偶问题
对偶变量
对偶松弛变量
用网络记号:
漏觅乔参涩程洪仑坑块辩伊谱异蛤拐岿狙枪陆酮釜脖逮枷蜜残茹汞雹乒婚CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划
plementarity Relations)
原变量必须是非负的
因此与之相联系的对偶约束是不等式
对偶松弛变量与原变量是互补的:
原始约束是等式
因此他们没有松弛变量
对应的对偶变量, ,是自由变量
对于他们互补条件是自然成立的
佑簿利转博兵喷号埋勉口聂睫凰顾屯惺褂错抢哪汽绵段榆柒沃抗辈骤嗽盂CAN-File-10-10-08-13-线性规划_网络流与整数规划CAN-File-10-10-08-13-线性规划_网络流与整数规划