第五章多目标规划
例题5.1 某工厂生产两种产品：A与B. 产品A每单位需装配时间3小时，而B 为2小时，每周总装配有效时间为120小时。
A产品的单位利润为100元，而B 产品的单位利润为80元。
工厂允许加班，但加班生产的产品单位利润各减10元。
根据合同，每周两种产品个需要提供30单位。
决策者，确定如下事实：
1.合同必须遵守，每周正常装配时间只有120小时；
2.尽可能少加班；
3.利润尽可能大。
建立其模型如下：
设：x1—每周正常时间生产的A产品数；
x2—每周加班时间生产的A产品数；
x3—每周正常时间生产的B产品数；
x4—每周加班时间生产的B产品数.
(VP) min 3x2+2x4,
max 100x1+90x2+80x3+70x4，
s.t. x1+x2≥30，
x3+x4≥30，
3x1+2x3≤120，
x1，x2，x3，x4≥0.
我们把这种目标函数多于一个的数学规划称为多目标规划，记为（VP）.
多目标规划问题，一般可以表示为
(VP)
p个目标函数minf1x；minf2x；
.
.
. minf p x。
m个约束条件g1（x）≥0，g2x≥0,
.
.
.
g m(x)≥0,
其中x=（x
1，
x2，x3，x4……x n）T，p≥2，m≥0。
若引进向量函数，可把多目标规划写成向量形式（VP）min F(x),
s.t. G(x)≥0,
其中
F(x)=(f1(x),f2(x),…,f p(x))T
G(x)=(g1(x),g2(x),…,g m(x))T.
若把可行域记为D，即
D=x|G(x)≥0,
则(VP)又可记为
F(x).
min
x∈D
5.2偏差概念的运用
例如某个问题包含有如下部分要求：甲、乙两种产品均使用原料A，其单消耗分别为a1和a2单位，且原料A现有库存400单位；另甲、乙产品的单位利润分别为c1和c2。
在制定生产计划时，要求尽量使用库存A，又期望得到利润500万。
若以x1、x2分别表示甲、乙的计划产量，则关于原料A的要求，利用偏差p1和n1表示为
min p1+n1，
s.t. a1x1+a2x2+p1-n1=400,
x1,x2,p1,n1≥0.
关于利润的要求，同样可引进偏差p2和n2，表示为
min p2+n2,
s.t. c1x1+c2x2+p2-n2=500(万),
x1,x2,p2,n2≥0，
其中p1，p2为正偏差量，若p1，p2>0而n1，n2=0，即意味着用完库存的A 和没有实现500万的利润；反之若p1，p2=0，n1，n2>0，则意味着A的使用量超过了现有库存，和利润超过了预期的500万。
整个问题合在一起就是一个多目标规划：
min p1+n1，
min p2+n2,
s.t. a1x1+a2x2+p1-n1=400,
c1x1+c2x2+p2-n2=500(万),
x1,x2,p1,p2,n1,n2≥0.
5.3多目标规划解的概念
(VP) min x1,
min x2,
s.t. x1+x2≥3,
x1+x2≤5,
0≤x1≤2.
若写成向量形式，即为
(x1,x2)T
min
x∈D
D=(x1,x2)T3≤x1+x2≤5,0≤x2≤2.
在x1,x2坐标平面中很容易画出可行域D：
若上述问题的最优解，要求在所有可行点(x1,x2)T∈D中的x1和x2都是最小的，即相当于我们对向量（a,b)T和（a1,b1)T大小的定义为：
当且仅当a1<a和b1<B时，才称为（a1,b1)T<（a,b)T.则这种最优解称为（VP）的绝对最优解.
所以对于多个目标规划还要引进一些解的概念.对于多目标规划：
(VP)
(f1x,f2x,…,f p(x))T.
min
x∈D
定义对于可行点x0∈D,若存在另一可行点x ∈D,使f k(x )<f k(x0),k=1,2,…,p,则称可行点x0为(VP)的劣解.
定义对于可行点x0∈D,若不存在另一可行点x ∈D,使f k(x )≤f k(x0),k=1,2,…,p,则称可行点x0为(VP)的有效解.
定义对于可行点x0∈D,若不存在另一可行点x ∈D,使f k(x )<f k(x0),k=1,2,…,p,则称可行点x0为(VP)的弱有效解.
5.4多目标线性规划的解法
一转化成一个单目标问题的解法
对于多目标规划
(VP) min
x∈D
(f1x,f2x,…,f p(x))T
按照p个目标f i(i=1,2,…,p)的重要程度，分别乘以权系数λi,以单目标规划
（P）min
xϵD
λi f i
P
i=1
(x)
的最优解作为(VP)的最优解.
二分层排序法
向量的的字典序定义为：先比较第一个分量，仅当第一个父女俩相同时，在比较第二个分量，一次类推.符号“L<”表示字典序意义下的小于.例如三维向量
1 2 5L<
2
1
7
L<
2
4
8
L<
2
4
9
.
若用这种方法求解多目标线性规划时，既可以一次性求解,也可以分段求解.
第六章离散型优化问题
6.1线性整数规划
背包问题有一只背包（泛指仓库、船仓、卫星仓等），最大装载重量为w 单位，现有k种物品，每种物品的数量无限.第i种物品每件质量为w i，价值为v i.每种物品各取多少个装入背包，使其中的物品价值最高.
设取第i种物品x i件(i=1,2,…,k),则
max z=v1x1+v2x2+…+v k x k,
s.t. w1x1+w2x2+…+w k x k≤w,
x i≥0，且为整数，i=1,2,,…,k.
线性整数规划的求解，很容易就想到先不考虑取整数的要求而用线性规划的办法求解，若求得最优解恰好取整数，也自然也即为线性整数规划的解，若不是整数，则凑成整数作为整数规划的近似解.这当然不失为一种办法，但在很多情况下，这样凑整的解或是不可行的、或是距真正的最优解很远.
6.3 网络优化
在网络中，边可以是有向的也可以是无向的.有向边(i,j),i是它的起点,j 是它的终点.
当然还有如下一些基本概念：
路径网络中一个前后相继并且方向相同的边序列
P={(i0,i1), (i1,i2),…, (i p−1,i p) }
称为路径
链网络中一个前后相继但方向不一定相同的边序列c={(i0,i1),
(i1,i2),…, (i p−1,i p) }称为链.
回路闭合的路径称为回路，回路中各边的反向都是方向一致的。
圈闭合的链称为圈。
连通图如果网络中任何两个节点之间都有一条链，则称为连通图。
树无圈的连通图称为树。
无相图的矩阵表示
（1）关联矩阵图G=（V,E）中顶点与边的关联关系，可用矩
阵A(G)=(a ij)表示，其中元素a ij定义为
a ij 0，表示v i和e j不关联，1，表示v i和e j关联.
矩阵A(G)称为图G的关联矩阵.
（2）邻接矩阵表示图G的顶点之间的邻接点系的矩阵B(b ij)称为邻接矩阵，其中
b ij
0,表示v i与v j无关联边N,表示v i与v j之间关联边数。
有向图的矩阵表示
（1）关联矩阵A’(G)=(a′ij),其中
a′ij
0,表示v i和e j不关联，
1，表示v i和e j关联，且
−1，表示v i和e j关联，且v i为终点。
v i为起点，
（2）邻接矩阵表示图G的顶点之间的邻接点系的矩阵B’(b′ij),其中b ij为以v i为起点和以v j为终点的边数。