数据.模型与决策— 管理运筹学 第3章 规划扩展.doc

—管理运筹学第3章规划扩展

—管理运筹学
四川大学工商管理学院
汪贤裕

第3章规划扩展
§ 整数规划
§ 非线性规划
§ 目标规划
§
§
1. 纯整数规划:所有决策变量取整数值;
2. 混合整数规划:部分决策变量取整数值;
3. 0-1 整数规划:决策变量只能取 0 或 1 ;
0-1 整数规划又可分为0-1纯整数规划和
0-1 混合整数规划。
注:在LI N DO软件中,可在 end 后加:
g i n 变量名——非负整数 i n t 变量名——0-1变量
§ 一般整数规划案例
工业原科的合理利用
要制作100套钢管架子,、、。。问应如何切割,使原料最省。
x6

3
6
x8
6
4
8
x7

3
1
7
x4

1
1
1
4
x5
x3
x2
x1
用原料数




有效用料
1
2
2
100
2
3

100
2
2

100
1
1

需求量
5
3
1
切割方案
解:设第i个方案用原料xi 根。
则有下列线性规划模型:
Min z = x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8
. x1+ 2x2 + x3 + x4 + 0x5 + 0x6 +0 x7 +0x8 ??100
0 x1+ 0x2 + 2x3 + x4 + 2x5 +3 x6 +x7+ 0x8 ?? 100
. 3 x1+ x2 + 0x3 + x4 + 2x5 + 0 x6+3x7 +4x8 ?? 100
xi ?? 0 ,且取整数,i =1,2,……,8。
求解得最优解为:x*=(30,10,50,0,0,0,0,0)

解2:设第i个方案用原料xi 根。
则有下列线性规划模型:
Min z=0x1+++++++
. x1+ 2x2 + x3 + x4 + 0x5 + 0x6 +0 x7 +0x8 ?? 100
0 x1+ 0x2 + 2x3 + x4 + 2x5 +3 x6 +x7+ 0x8 ?? 100
. 3 x1+ x2 + 0x3 + x4 + 2x5 + 0 x6+3x7 +4x8 ?? 100
xi ?? 0 ,且取整数,i =1,2,……,8。
求解得最优解为:x*=(100,0, 0,0,50,0,0,0)
(解2和解1有什么不同,那一个正确?为什么?)
0-1整数规划案例
匹配问题
某公司有甲乙丙三个销售员,需分别派到A、B、C三地工作。已知不同销售员在不同地点的收益预测为:
现要求每个地点只能派 1名销售员,且一名销售员只能到一个地点。问应如何安排工作,使总收益最大。
60
50
40
丙
40
10
30
乙
40
40
20
甲
C
B
A
人员\地点

某集团公司有1400万资金,拟在西藏自治区内进行藏药厂的投资建设。现有7个藏药厂项目通过初评,可以作为预选方案。各项目的年收益及所需投资额如下表:

由于2、4、5三项目生产产品相同,只能建其中一个;5、6、7三项目在同一地区,最多只能建两个。问该团公司应如何安排投资项目,使年收益最大。
100
500
2
20
150
7
110
500
5
50
90
200
30
预计年收益(万元)
300
400
700
200
所需投资额(万元)
6
4
3
1
序号
解:设 x I 为对第 i 个项目投资(i = 1,2,…,7.)。
x i = 0 表示对第 i 个项目不投资,
x i = 1 表示对第 i 个项目投资。
我们可以建立如下0-1整数规划模型:
Max z = 30x1+100x2+200x3+90x4+110x5+50x6+20x7
. 200x1+500x2+700x3+400x4+500x5+300x6+150x7≤1400
x2+x4+x5≤1
x5+x6+x7≤2
xi 取 0 或 1,i =1,2,…,7.
§ 特殊约束的处理

(1)矛盾约束两个相互矛盾的约束,只要求其中一个起作