运筹学数学建模7-9

A1 A2 现有资源
一
设备 1 2 8台时
、
甲 4 0 16公斤
从
表： 制订生产计划,使 每天获利最大
乙 0 4 12 公斤 利润 20 30 （元）
设生产A1、A2分别x1、x2公斤 决策变量
现 实 问 题 到
max z= 20x1+30x2 (1)
目标函数
线 性
x1 2x2 8, (2)
约
a21 x1 a22 x2 L a2n xn (, )b2 , L
am1 x1
am2 x2
L
amn xn
(, )bm ,
xi 0, x j 0, i i1 ,L , ik , j j1,L , jl .
线性规划模型标准型:
线性规划模型标准型矩阵表示：
maxz= c1 x1 +c2x2 +…+cnxn
max z= cX
s.t . AX b
(LP)
s.t
.
a11 x1 a12 x2 L a21 x1 a22 x2 L
L
a1n xn a2n xn
b1 , b2 ,
X 0
c [c1, c2,L , cn ], A [aij ]mn.
am1
x1
am 2
x2
L
amn xn
bm ,
运筹学理论与建模
河北联合大学理学院 肖继先
主要内容
第一部分 线性规划建模方法 第二部分 整数规划建模方法 第三部分 指派问题 第四部分 动态规划建模 第五部分 图论与网络优化
第一部分 线性规划建模方法
一、从现实问题到线性规划模型 二、线性规划模型的求解 三、线性规划建模实例
一、从现实问题到线性规划模型
(3) ai1 x1 ai 2 x2 L ain xn bi 加剩余变量yi
ai1 x1 ai 2 x2 L ain xn yi bi
(4) 若存在可正可负变量xi 令
xi xi1 xi2 , xi1 , xi 2 0.
例 将下述线性规划问题化为标准型 标准型 min z = x1 +2x2 3x3 maxz = x12x2 +3(x4 –x5 )+0x6 +0x7
min z= x1+x2 +x3 +x4
式，所需总用料最省? 解：可能的下料方式：
s.t
.
3 x1 2 x2 x3 2x2 4x3 6x4
100, 200,
xi 0, i 1, 2, 3, 4.
2.5 1.3 13 0 22 2 31 4
有一组决策变量,约束条件是决 策变量的线性等式或不等式,目 标函数是决策变量的线性函数, 这样的规划问题称为线性规划.
连续性无关xi取值连续
线性规划模型
A1,A2每公斤的获利是与各 自产量无关的常数
每桶牛奶加工出A1,A2的数量 和时间是与各自产量无关的常 数 A1,A2每公斤的获利是与相 互产量无关的常数
每桶牛奶加工出A1,A2的数量和 是与时间相互产量无关的常数
加工A1,A2的牛奶桶数是实数
例2 工厂生产两种 产品A1,A2,已知生 产单位产品情况如
x1 x2 x3 7,
s.t
x1 x2 x3 3x1 x2 2x3
2,
5,
x1, x2 0, x3 无约束
x1 x2 x4 x5 x6 7,
s.t
x31
x1
x2
x2
x4
x5 x7 2x4 2x5
2, 5,
x1 , x2 , x4 , x5 , x6 , x7 0.
例1 加工奶制品的生产计划
1桶 牛奶 或
12小时 8小时
3公斤A1 4公斤A2
获利24元/公斤 获利16元/公斤
每天: 50桶牛奶 时间480小时 至多加工100公斤A1
制订生产计划，使每天获利最大
• 35元可买到1桶牛奶，买吗？若买，每天最多买多少? • 可聘用临时工人，付出的工资最多是每小时几元? • A1的获利增加到 30元/公斤，应否改变生产计划？
X [x1, x2,L , xn ]T ,
xi 0, i 1,L , n.
b [b1, b2 ,L , bm ]T , b 0,
1.线性规划的一般形化为标准型的一般步骤 (1) Min f = cX 转化为max z = cX
(2) ai1 x1 ai 2 x2 L ain xn bi 加松弛变量yi ai1 x1 ai2 x2 L ain xn yi bi
s.t. 04 xx11
0 x2 4 x2
16, 12,
(3) (4)
束 条
规 划 模 型
x1 0, x2 0. (5)
件
线性规划模型一般形式：
max(min) z= c1 x1 +c2x2 +…+cnxn
a11 x1 a12 x2 L a1n xn (, )b1 ,
s.t
.
(1) x3 = x4 x5 , x4 , x5 0 (2) x1 +x2 +x3 +x6 =7 (3) x1 x2 +x3 x7 =2
合理下料问题
设按第i种下料方式的
有长度为8米的某型号圆钢， 现需要长度为2.5米的毛坯
圆钢xi根，i=1,2,3,4
100根，长度为1.3米的毛 坯200根，如何选者下料方
线性 规划
劳动时间
12x1 8x2 480
模型
加工能力 非负约束
3x1 100
x1, x2 0
(LP)
模型分析与假设
比 xi对目标函数的
例 “贡献”与xi取值
性 成 xi对正约比束条件的
“贡献”与xi取值
可 加
成 xi对正目比标函数的 “贡献”与xj取值
性 无 xi对关约束条件的
“贡献”与xj取值
40 6
记为（LP）
例.某小区一个24小时营业便利店,一 天各时段所需服务员最少人数如下 min z= x1+x2+ x3+x4+x5+x6
表.根据实际情况,要求每个服务员必
须连续工作八小时,试建立需服务员
总人数最少的排班方案数学模型.
s.t
.
班次 1 2 3 4 5 6
x6 x1 4, x1 x2 8, x2 x3 10, x3 x4 7, x4 x5 12,
1桶 牛奶 或
12小时 8小时
3公斤A1 4公斤A2
每天 50桶牛奶 时间480小时
获利24元/公斤 获利16元/公斤 至多加工100公斤A1
决策变量 目标函数
约束条件
x来自百度文库桶牛奶生产A1 x2桶牛奶生产A2
获利 24×3x1
获利 16×4 x2
每天获利 Max z 72x1 64x2
原料供应
x1 x2 50