09.3某公司打算向它的三个营业区增设六个销售店.每个营业区至少增设一个。从各区赚取的利润（单位：万元）与增设的销售店个数有关，其数据如下。表9—6销售店增加数A区利润B区利润C区利润01002001501200210160228022017032251803304340230200试求各区应分配几个增设的销售店，才能使总利润最大，其值是多少？解将问题按营业区数分为3个阶段.阶段变量k=12.3，第1、2、3个阶段分别为A、B、C营业区分配增设的销售店。状态变量s表示给第k至第3个营业区增设销售店的数量：决策变量表示给第k个营业区增设销售店的数量：状态转移方程：S+1=S一阶段指标P（）表示给第k个营业区增设个销售店赚取的利润：最优值函数f（s）表示给第k至第3个营业区增设S个销售店赚取的最大利润：f（s）=max[p（x）+fh+1（s+1)].k=3.2.1TS递推公式：f4(s4)=0
kpe()f#+1(st+1)fa(se)akp(a)+fh+1(st+1)Skk11600160160112221700170170333031801801804402002002004212101603703701-21017038033801.2222016038012101803901,2422203901703902322516038512102004102220180400514103225170395423016039012004106102280390670167103.433303807104710340370由计算表格的结果可以看出，赚取的最大利润为710万元按计算表格的顺序反推算，可知最优增设方案有三个：(1)x*=3,x2=1,3=2;(2)x*=3,x2=2,3=1;二（3)x*=4,2=1,α3=1。北京父通大学
北京交通大学经济管理学院nics and ManagomentSchool of EcononBoijing Jiaotong UniversityA区利润B区利润C区利润销售店增加数0200210160128022017023301802253340200230北京交通大学
销售店增加数 A区利润 B区利润 C区利润 0 1 2 3 200 280 330 340 210 220 225 230 160 170 180 200
北京交通大学经济管理学院School of Ecorhics andManagomentBojing Jiaotong University第10章图与网络优化Graph Theory and Network Optimization北京交通大学
第 10 章图与网络优化 Graph Theory and Network Optimization
北京交通大学经济管理学院提纲School of Econics andManagomentBojing Jiaotong University1.图的基本概念2.最小树问题3.最短路问题4.最大流问题5.最小费用最大流问题北京交通大学
提 纲 1.图的基本概念 2.最小树问题 3.最短路问题 4.最大流问题 5.最小费用最大流问题