数学规划模型 鲁志浪 信息工程大学理学院
1 鲁志波 信息工程大学理学院 数学规划模型
主要内容 1规划模型的基本概念 2规划模型与 LINDO求解 Information Engineering University
2 1 规划模型的基本概念 2 规划模型与LINDO求解 主要内容
1规划模型的基本概念 规划模型的一般形式三要素 (1)决策变量,通常是该问题要求解的那些未知 量,不妨用n维向量x=(x1x2,,xn)表示,当 对x赋值后通常称为该问题的一个解 (2)目标函数通常是该问题要优化(最大或最小) 的那个目标的数学表达式它是决策变量x的函 数,可以记作fx) (3)约束条件由该问题对决策的限制条件给出, 即x允许取值的范围x∈Ω,称为可行城。通常 Information Engineering University
3 规划模型的一般形式 三要素 (1) 决策变量, 通常是该问题要求解的那些未知 量, 不妨用 n 维向量x =(x1 ,x2 ,…, xn ) T表示, 当 对 x 赋值后通常称为该问题的一个解 (2) 目标函数, 通常是该问题要优化 (最大或最小) 的那个目标的数学表达式, 它是决策变量 x 的函 数, 可以记作 f(x) 1 规划模型的基本概念 (3) 约束条件, 由该问题对决策的限制条件给出, 即x允许取值的范围x∈Ω, Ω称为可行域。通常
用一组关于x的等式g(x)=0(=1,2,k或不等式 b(x)≤0(=1,2,,l)来界定分别称为等式约束 和不等式约束 规划模型的一般数学飛式: opt zf(r) st.g/(x)=0(i=1,2,…,) (2) hx)≤0(=1,2,,D (3) 其中op是最优化的意思,可以是min或max两者 之一;.t是“受约束于”( subject to)的意思 Information Engineering University
4 用一组关于x的等式gi (x)=0(i=1,2,…, k)或不等式 hj (x)≤0(j= 1, 2,…, l )来界定, 分别称为等式约束 和不等式约束 规划模型的一般数学形式： opt z=f(x) (1) s.t. gi (x)=0 (i=1,2,…,k） (2) hj (x)≤0 (j= 1, 2,…,l) (3) 其中opt是最优化的意思, 可以是min或max两者 之一; s. t.是“受约束于”(subject to)的意思
可行解和最优解 同时满足约束条件(和(3)的解xx∈称为可行 解,否则称为不可行解 满足条件(1)的可行解x称为最优解在最优解 x处目标函数的取值f(x称为最优值 基本类型 线性规划 连续型规划 规划模型 非线性规划 整数视划 离散型规划 0-1规划 Information Engineering University
5 可行解和最优解 同时满足约束条件⑵和⑶的解x(xΩ)称为可行 解, 否则称为不可行解 满足条件(1)的可行解 x* 称为最优解, 在最优解 x* 处目标函数的取值 f (x*)称为最优值 基本类型 规 划 模 型 连续型规划 离散型规划 线性规划 非线性规划 整数规划 0-1规划
⊙2规划模型与 LINDO求解 例1加工奶制品的生产计划 牛奶212小份3千克A 1桶 获利24元/千克 8小时4千克A 2→获利16元千克 每天:50桶牛奶时间480小时至多加工100千克A1 制订生产计划使每天获利最大 35元可买到1桶牛奶,买吗?若买,每天最多买多少? 可聘用临时工人,付出的工资最多是每小时几元? A1的获利增加到30元千克,是否改变生产计划? Information Engineering University
6 例1 加工奶制品的生产计划 1桶 牛奶 3千克A1 12小时 8小时 4千克A2 或 获利24元/千克 获利16元/千克 制订生产计划,使每天获利最大 • 35元可买到1桶牛奶, 买吗? 若买, 每天最多买多少? • 可聘用临时工人, 付出的工资最多是每小时几元? • A1的获利增加到 30元/千克, 是否改变生产计划? 每天 50桶牛奶 时间480小时 至多加工100千克A1 : 2 规划模型与LINDO求解
模型建立 牛奶(12小时3千克获利2元午克 1桶 8小时 4千克A2→获利6元千克 每天:50桶牛奶时间480小时至多加工100千克A1 决策变量x桶牛奶生产A1x2桶牛奶生产A2 目标 获利24×3x1获利16×4x2 函数每天获利Maxz=72x1+64 x,+x<50 线性 约原料供应 规划 束劳动时间 12x1+8x2≤480 模型 条加工能力 3x,<100 (LP) 件 非负约束 x1,x2≥0 Information Engineering University
7 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 x1 + x2 50 劳动时间 12x1 +8x2 480 加工能力 3x1 100 决策变量 目标 函数 72 1 64 2 每天获利 Max z = x + x 约 束 条 件 非负约束 x1 , x2 0 线性 规划 模型 (LP) 每天 50桶牛奶 时间480小时 至多加工100千克A1 : 模型建立 1桶 牛奶 3千克A1 12小时 8小时 4千克A2 或 获利24元/千克 获利16元/千克
⑦模型求解图解法 x1+xn<50 x1+x2=50 约束条件 12x+8x,≤480口l2:12x1+8x2=480 3x1≤100 3x,=100 Z=3360 x1,x,≥0 =0,l5:x2=0 Is D 目标Maxx=72x+64x2 Z=2400 Z=0 函数z=c(常数)~等值线 在B(20,30)点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形最优解在凸多边形 目标函数的等值线为直线 的某个顶点取得 Information Engineering University
8 模型求解 图解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 x1 + x2 50 12x1 +8x2 480 3x1 100 x1 , x2 0 约 束 条 件 l 1 : x1 + x2 = 50 l 2 :12x1 +8x2 = 480 l 3 :3x1 =100 l 4 : x1 = 0, l 5 : x2 = 0 72 1 64 2 目标 Max z = x + x 函数 Z=0 Z=2400 Z=3360 z=c (常数) ~等值线 c 在B(20,30)点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解在凸多边形 的某个顶点取得
模型求解 软件实现- LINDO max 72x1+64x2 OBJECTIVE FUNCTION VALUE st 3360.000 2)x1+x2<50 VARIABLE VALUE REDUCED COST 3)12x1+8x2<480 20.000000 0.000000 X2 30.000000 0.000000 4)3x1<100 ROW SLACK OR SURPLUS DUAL PRICES end 2) 0.000000 48.000000 DO RANGE 0.000000 2.000000 (SENSITIVITY 40.000000 0.000000 ANALYSIS? NO NO. ITERATIONS 20桶牛奶生产A1,30桶生产A2,利润350元 Information Engineering University
9 模型求解 软件实现--LINDO max 72x1+64x2 st 2) x1+x2<50 3) 12x1+8x2<480 4) 3x1<100 end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUALPRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 DO RANGE (SENSITIVITY) ANALYSIS? No 20桶牛奶生产A1 , 30桶生产A2 , 利润3360元
结果解释 max 72x1+64X2 OBJECTIVE FUNCTION VALUE st 3360.000 2)x1+x2<50 VARIABLE VALUE REDUCED COST 3)12x1+8x2<480 XI 20.000000 0.000000 4)3x1<100 X2 30.000000 0.000000 end ROW SLACK OR SURPLUS DUAL PRICES 三原料无剩余2) 0.000000 48.000000 种时间无剩余3 0.000000 2.000000 资加工能力剩440000 0.000000 源余40 NO. ITERATIONS “資源”剩余为零的约束为紧约束有效约束) Information Engineering University
10 结果解释 原料无剩余 时间无剩余 三 种 资 源 “资源” 剩余为零的约束为紧约束(有效约束) OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUALPRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 加工能力剩 余 40 max 72x1+64x2 st 2) x1+x2<50 3) 12x1+8x2<480 4) 3x1<100 end