文档介绍：最大流量问题
某油田通过输油管道向港口输送原油,中间有4个泵站,每段管道上的输送能力如图所示,求这个系统的最大输送能力(泵站上没有贮存能力)?
油田S
泵站1 4
泵站3 12
码头T
泵站4
泵站2 7
10 8 11
9 6
5
最短路问题(适用于多阶段最优化)
某旅行者希望从s地起到t地,其间的道路系统如图所示,图上圆圈表示途径的地方,称为节点,连结两地的箭线表示道路,其上的数字表示该段道路长度,箭头表示通行的方向。试求s到t的最短路。
a
d
b
e
t
c
f
s
9
7
5
7
8
4
5
6
4
6
5
4
7
背包问题
货物
1
2
3
单位重量
2
3
1
单位价值
65
80
30
对于一个具体问题 W=5 用动态规划求解k=3
生产—库存问题
生产计划周期分为n个阶段,即k=1~n;
已知最初库存量为x1;
阶段需求量为dk;
单位产品的消耗费用为Lk;
单位产品的阶段库存费用为hk;
仓库容量为Mk;
阶段生产能力为Bk;
生产的准备费用为:
状态变量xk应选为阶段k的初始库存量,计划初期的库存量x1是已知的,末期的库存量通常也是给定的,为简单起见这里假定xn+1=0,于是问题是始端末端固定的问题。
即阶段k的库存既不能超过库存容量,也不应超过阶段k至阶段n的需求总量(dk+dk+1+…+dn),否则将与xn+1=0的假设相违背。
问:应如何安排各阶段产量,使计划期总费用最小。
关于状态xk的约束条件是
库容量限制
以后需求缺口
本期需求缺口
因此关于决策变量的约束条件就是
期末库存=期初库存+生产量-本期需求
决策变量uk选为阶段k的生产量。
阶段产量要在不超过生产能力Bk的条件下,充分满足该阶段的需求dk,同时还要满足计划末期的库存量为0的要求。
阶段k的生产费用是
库存费用按阶段k末期的库存量xk+1计算
求解生产-库存问题。已知其n=3,ck=8,Lk=2,hk=,x1=1,Mk=4,x4=0(计划周期末期的库存量为0),Bk=6,d1=3,d2=4,d3=3。
最小支撑树问题