最大和最小费用流问题模型

《最大和最小费用流问题模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最大流和最小费用流的作业1.在下图中A、B为发点，分别有50和40单位物资往外发送，D和E是为收点，分别需要物资30和60单位，C为中转站，各弧旁数字为（Cij，Bij），求满足上述收发量要求的最小费用流。解：把问题转化为网络图：DA(20,90)C(50,40)E(10,20)(30,20)(10,30)B(40,30)(80,10)决策变量：设A运到B为L1,A运到C为L2，A运到D为L3，B运到C为L4，C到E为L5D到E为L6，E到D为L7。目标函数：MinZ=L1×20+L2×40+L3×90+L4×30+L

2、5×10+L6×30+L7×20约束条件：L1<=10,L2<=50,L3<=20,L4<=40,L5<=80,L6<=30,L7<=20L1+L2+L3=50L4=40+L1L2+L4=L5L3+L7=30L5+L6=60Li为整数（i=1，2，3，4，5，6，7）；结果如下：解得L1=0L2=40L3=10L4=40L5=80L6=0L7=20MinZ=49002、下图是描述一个水渠系统，其中R1，R2，R3,代表三个水库，A,B,C,D,E,F,代表水渠的交汇点，T表示水渠终点的一个城市，水渠各段每日允许通过的最

3、大流量（1000m3）分别见表6-10和6-11.城市水资源管理部门希望制定一个方案，使每天输送到城市的水流量为最大，请将此问题归结为求最大流问题。R1DAEBR2TR3FC表6-10到从ABCR17365_R2405060R3_8070表6-11到到从DEF从TA6045_D120B705545E190C_7090F130解：决策变量：设：R1->A的流量为Ｋ１R1->B的流量为Ｋ2，R2->A的流量为Ｋ3，R2->B的流量为Ｋ4，R2->C的流量为Ｋ5，R3->B的流量为Ｋ6，R3->C的流量为Ｋ7，A->D的流量

4、为Ｋ8，A->E的流量为Ｋ9，B->D的流量为Ｋ10，B->E的流量为Ｋ11，B->F的流量为Ｋ12，C->E的流量为Ｋ13，C->F的流量为Ｋ14，D->T的流量为Ｋ15，E->T的流量为Ｋ16，F->T的流量为Ｋ17。目标函数：（=流入终点T的水流量）最大MaxZ=K15+K16+K17约束条件：1）每条弧上的实际流量不能超过其最大通过能力Ｋ1<=73;Ｋ2<=65;Ｋ3<=40;Ｋ4<=50;Ｋ5<=60;Ｋ6<=80;Ｋ7<=70;Ｋ8<=60;Ｋ9<=45;Ｋ10<=70;Ｋ11<=55;Ｋ12<=45;Ｋ1

5、3<=70;Ｋ14<=90;Ｋ15<=120;Ｋ16<=190;Ｋ17<=130;2）起点的流出量等于终点的流入量K1+K2+K3+K4+K5+K6+K7=K15+K16+K173）非负约束：Ｋi>=0(i=1,2......16,17)fr1a+fr2a=fad+fae4）中间结点的水流入量等于水流出量Ｋ1+Ｋ3=Ｋ8+Ｋ9;结点A　　Ｋ2+Ｋ4+Ｋ6=Ｋ10+Ｋ11+Ｋ12;结点B　　Ｋ5+Ｋ7=Ｋ13+Ｋ14;结点C　　Ｋ8+Ｋ10=Ｋ15;结点D　　Ｋ9+Ｋ11+Ｋ13=Ｋ16;结点E　　Ｋ12+Ｋ14=Ｋ17

6、;结点F解得：最大流为414.